Comparison of multivariate boolean functions
The application I am writing uses parsing of a parsing in boolean lambda expressions. For testing purposes, I need to make sure this parsing happens correctly. To do this, I wrote a procedure for comparing a recursive expression tree bool ExpressionComparison.EquvalentTo(this Expression self, Expression other)
. If self
and other
are both logical operators and they have the same set of operands, EquvalentTo
must return true.
My current algorithm uses ExpressionVisitor
. I pass the body of the lambda expression to this visitor and replaces all operands (expressions that are not boolean operators) with boolean parameters. I call this on both lambdas, compare the operands, reorder the binary parameters for the second lambda if necessary, so they match the same operands, compile the two binary functions, and compare the results exhaustively.
Is there a more efficient way to compare the logical equivalence of two Boolean functions?
public static class ExpressionComparison
{
public static bool Equals(this Expression left, Expression right)
{
return Compare(left, right, Equals);
}
public static bool EquvalentTo(this Expression self, Expression other)
{
if (Object.Equals(self, other))
return true;
if (self == null || other == null)
return false;
if ((self.NodeType == ExpressionType.Not || self.NodeType == ExpressionType.AndAlso || self.NodeType == ExpressionType.OrElse) &&
(other.NodeType == ExpressionType.Not || other.NodeType == ExpressionType.AndAlso || other.NodeType == ExpressionType.OrElse))
return new Visitor(self).Compare(new Visitor(other), EquvalentTo);
else if (self.NodeType != other.NodeType)
return false;
if (self.NodeType == ExpressionType.Constant)
{
var _self = (ConstantExpression)self;
var _other = (ConstantExpression)other;
if (Object.ReferenceEquals(_self.Value, _other.Value))
return true;
}
if (self.Type != other.Type)
return false;
switch (self.NodeType)
{
case ExpressionType.Add:
case ExpressionType.AddChecked:
case ExpressionType.Multiply:
case ExpressionType.MultiplyChecked:
case ExpressionType.And:
case ExpressionType.Or:
case ExpressionType.ExclusiveOr:
var selfsubs = ((BinaryExpression)self).Linearize().ToList();
var othersubs = ((BinaryExpression)other).Linearize().ToList();
foreach (var leftsub in selfsubs)
{
int i;
for (i = othersubs.Count - 1; i >= 0; i--)
if (EquvalentTo(leftsub, othersubs[i]))
{
othersubs.RemoveAt(i);
break;
}
if (i < 0)
return false;
}
return othersubs.Count == 0;
}
return Compare(self, other, EquvalentTo);
}
private static bool Compare(Expression self, Expression other, Func<Expression, Expression, bool> comparer)
{
if (Object.Equals(self, other))
return true;
if (self == null || other == null)
return false;
if (self.NodeType != other.NodeType)
return false;
if (self.Type != other.Type)
return false;
if (self is BinaryExpression)
{
var _left = (BinaryExpression)self;
var _right = (BinaryExpression)other;
return comparer(_left.Left, _right.Left) && comparer(_left.Right, _right.Right);
}
else if (self is ConditionalExpression)
{
var _left = (ConditionalExpression)self;
var _right = (ConditionalExpression)other;
return comparer(_left.IfFalse, _right.IfFalse) && comparer(_left.IfTrue, _right.IfTrue) && comparer(_left.Test, _right.Test);
}
else if (self is ConstantExpression)
{
var _left = (ConstantExpression)self;
var _right = (ConstantExpression)other;
if (!Object.Equals(_left.Value, _right.Value))
return false;
return true;
}
else if (self is DefaultExpression)
{
return true;
}
else if (self is IndexExpression)
{
var _left = (IndexExpression)self;
var _right = (IndexExpression)other;
if (_left.Arguments.Count != _right.Arguments.Count)
return false;
if (!Object.Equals(_left.Object, _right.Object))
return false;
if (!Object.Equals(_left.Indexer, _right.Indexer))
return false;
for (var i = _left.Arguments.Count - 1; i >= 0; i--)
if (!comparer(_left.Arguments[i], _right.Arguments[i]))
return false;
return true;
}
else if (self is InvocationExpression)
{
var _left = (InvocationExpression)self;
var _right = (InvocationExpression)other;
if (_left.Arguments.Count != _right.Arguments.Count)
return false;
if (!comparer(_left.Expression, _right.Expression))
return false;
for (var i = _left.Arguments.Count - 1; i >= 0; i--)
if (!comparer(_left.Arguments[i], _right.Arguments[i]))
return false;
return true;
}
else if (self is LambdaExpression)
{
var _left = (LambdaExpression)self;
var _right = (LambdaExpression)other;
if (_left.Parameters.Count != _right.Parameters.Count)
return false;
for (var i = _left.Parameters.Count - 1; i >= 0; i--)
if (!comparer(_left.Parameters[i], _right.Parameters[i]))
return false;
if (!Object.Equals(_left.ReturnType, _right.ReturnType))
return false;
return comparer(_left.Body, _right.Body);
}
else if (self is ListInitExpression)
{
var _left = (ListInitExpression)self;
var _right = (ListInitExpression)other;
if (comparer(_left.NewExpression, _right.NewExpression))
return false;
for (var i = _left.Initializers.Count - 1; i >= 0; i--)
{
var leftinit = _left.Initializers[i];
var rightinit = _right.Initializers[i];
if (Object.Equals(leftinit, rightinit))
continue;
if (!Object.Equals(leftinit.AddMethod, rightinit.AddMethod))
return false;
if (leftinit.Arguments.Count != rightinit.Arguments.Count)
return false;
for (var j = leftinit.Arguments.Count - 1; j >= 0; j--)
if (!leftinit.Arguments[i].EquvalentTo(rightinit.Arguments[i]))
return false;
}
return true;
}
else if (self is MemberExpression)
{
var _left = (MemberExpression)self;
var _right = (MemberExpression)other;
if (!Object.Equals(_left.Member, _right.Member))
return false;
return comparer(_left.Expression, _right.Expression);
}
else if (self is MemberInitExpression)
{
}
else if (self is MethodCallExpression)
{
var _left = (MethodCallExpression)self;
var _right = (MethodCallExpression)other;
if (!Object.Equals(_left.Method, _right.Method))
return false;
if (!comparer(_left.Object, _right.Object))
return false;
for (var i = _left.Arguments.Count - 1; i >= 0; i--)
if (!comparer(_left.Arguments[i], _right.Arguments[i]))
return false;
return true;
}
else if (self is NewArrayExpression)
{
var _left = (NewArrayExpression)self;
var _right = (NewArrayExpression)other;
for (var i = _left.Expressions.Count - 1; i >= 0; i--)
if (!comparer(_left.Expressions[i], _right.Expressions[i]))
return false;
return true;
}
else if (self is NewExpression)
{
var _left = (NewExpression)self;
var _right = (NewExpression)other;
if (!Object.Equals(_left.Constructor, _right.Constructor))
return false;
for (var i = _left.Members.Count - 1; i >= 0; i--)
if (!Object.Equals(_left.Members[i], _right.Members[i]))
return false;
for (var i = _left.Arguments.Count - 1; i >= 0; i--)
if (!comparer(_left.Arguments[i], _right.Arguments[i]))
return false;
return true;
}
else if (self is ParameterExpression)
{
return true;
}
else if (self is TypeBinaryExpression)
{
var _left = (TypeBinaryExpression)self;
var _right = (TypeBinaryExpression)other;
if (_left.TypeOperand != _right.TypeOperand)
return false;
return comparer(_left.Expression, _right.Expression);
}
else if (self is UnaryExpression)
{
var _left = (UnaryExpression)self;
var _right = (UnaryExpression)other;
if (!Object.Equals(_left.Method, _right.Method))
return false;
return comparer(_left.Operand, _right.Operand);
}
throw new Exception("Unhandled expression type: " + self.GetType());
}
private static IEnumerable<Expression> Linearize(this BinaryExpression expr)
{
var type = expr.NodeType;
if (expr.Left.NodeType == type)
foreach (Expression subexpr in ((BinaryExpression)expr.Left).Linearize())
yield return subexpr;
else
yield return expr.Left;
if (expr.Right.NodeType == type)
foreach (Expression subexpr in ((BinaryExpression)expr.Right).Linearize())
yield return subexpr;
else
yield return expr.Right;
}
class Visitor : ExpressionVisitor
{
IList<Expression> _expressions = new List<Expression>();
IList<ParameterExpression> _parameters = new List<ParameterExpression>();
ParameterExpression _next(Expression expression)
{
var parameter = Expression.Parameter(typeof(Boolean));
_expressions.Add(expression);
_parameters.Add(parameter);
return parameter;
}
public override Expression Visit(Expression node)
{
switch (node.NodeType)
{
case ExpressionType.Not:
case ExpressionType.AndAlso:
case ExpressionType.OrElse:
return base.Visit(node);
default:
return _next(node);
}
}
public Expression Visited { get; private set; }
public Expression[] Expressions { get; private set; }
public ParameterExpression[] Parameters { get; private set; }
public Visitor(Expression node)
{
Visited = Visit(node);
Expressions = _expressions.ToArray();
Parameters = _parameters.ToArray();
}
private Delegate NaturalOrder()
{
return Expression.Lambda(Visited, Parameters).Compile();
}
private Delegate ForcedOrder(int[] order)
{
return Expression.Lambda(Visited, order.Select(i => Parameters[i])).Compile();
}
public bool Compare(Visitor that, Func<Expression, Expression, bool> comparer)
{
if (this.Expressions.Length != that.Expressions.Length)
return false;
var order = new int[this.Expressions.Length];
var CompareExpr = that.Expressions.ToArray();
for (int i = Expressions.Length - 1, j; i >= 0; i--)
if (comparer(Expressions[i], CompareExpr[i]))
order[i] = i;
else
{
for (j = CompareExpr.Length - 1; j >= 0; j--)
if (i == j)
continue;
else if (comparer(Expressions[i], CompareExpr[j]))
{
order[i] = j;
CompareExpr[j] = null;
break;
}
if (j < 0)
return false;
}
dynamic thisd = this.NaturalOrder();
dynamic thatd = that.ForcedOrder(order);
var args = new bool[order.Length];
for (var i = ((ulong)1 << order.Length); i > 0; i--)
{
for (var j = (byte)order.Length - 1; j >= 0; j--)
args[j] = ((i - 1) & ((ulong)1 << j)) != 0;
if (!FuncHelper.Exec(thisd, thatd, args))
return false;
}
return true;
}
}
}
Asside / Update: I am comparing Expression<Func<TModel, bool>>
which I am using in WHERE clauses for LINQ to Entities. I want to know that a given text string is correctly parsed into a lambda, and for that I am comparing the generated lambda against the lambda I am expecting. I want to know that both lambdas will return the same result set. I can't actually test the data, as some of the queries are deliberately absurd, making sure my parser is robust to the end.Also, the data changes, query A may be subtly different from query B, but at the time both of them return one the same set, etc. So I am testing lambdas for equivalence.
I define two expressions to be equivalent if one of the following:
-
Object.Equals(a, b)
returns true -
a
andb
are logically equivalent (only applicable to nodesNot
,AndAlso
andOrElse
, defined below) -
a
andb
two commutative equivalent (only applicable toAdd
,Multiply
(bitwise)And
,Or
andExclusiveOr
nodes defined below) - They are
ExpressionType
froma
andb
exactly equal, and all of their operands, operators, parameters, arguments, etc. are equivalent (for expressions) or equal (for other objects).
I define two expressions as logically equivalent if: their "operands" are equivalent and if I replace each boolean operand with a boolean parameter, the two resulting n-ary boolean functions have the same truth tables. The process looks like this:
- For each: Visit the expression by skipping any NodeType nodes
Not
,AndAlso
orOrElse
by replacing other nodes with a new boolean parameter. Boolean parameters and replaceable expressions are captured in arrays. - Make sure to commit the same number of expressions.
- Compare the captured expressions a and b, determining whether they are equivalent sets, and determining the relative ordering (
paramA.PropA == 1 && paramB.PropB == 2
considered equivalentparamB.PropB == 2 && paramA.PropA == 1
, but in more complex cases, different ordering of parameters may result in a different truth table). - Reorder the boolean parameters b so
b.Parameters[i]
matches some expressionb.Expressions[j]
that is itself equivalenta.Expressions[i]
. - Compile the resulting expressions into two logical functions and compare their truth tables.
I define two expressions as commutatively equivalent if: their ExpressionType
of a
and b
are exactly equal, and if for a and b I go down the tree, stopping at any Expression
that is not the same ExpressionType
as a / b, and put that expression in the list, the list for a
and for b
contains the same set Expressions
(defined by equivalence).
source to share
No one has answered this question yet
Check out similar questions: