How to Check If Two Expression<Func<T, Bool>> Are the Same

How to check if two ExpressionFuncT, bool are the same

You can have a look at the type ExpressionEqualityComparer that is used inside Linq to db4o. It implements the interface IEqualityComparer<T>, so it's usable for generic collections, as well as for a standalone usage.

It uses the type ExpressionComparison to compare two Expressions for equality, and HashCodeCalculation, to compute a hashcode from an Expression.

It all involves visiting the expression tree, so it can be pretty costly if you do it repeatedly, but it can also be quite handy.

The code is available under the GPL or the dOCL

For instance, here's your test:

using System;
using System.Linq.Expressions;

using Db4objects.Db4o.Linq.Expressions;

class Test {

    static void Main ()
    {
        Expression<Func<int, bool>> a = x => false;
        Expression<Func<int, bool>> b = x => false;
        Expression<Func<int, bool>> c = x => true;
        Expression<Func<int, bool>> d = x => x == 5;

        Func<Expression, Expression, bool> eq =
            ExpressionEqualityComparer.Instance.Equals;

        Console.WriteLine (eq (a, b));
        Console.WriteLine (eq (a, c));
        Console.WriteLine (eq (a, d));
    }
}

And it indeed prints True, False, False.

Combining two expressions (ExpressionFuncT, bool)

Well, you can use Expression.AndAlso / OrElse etc to combine logical expressions, but the problem is the parameters; are you working with the same ParameterExpression in expr1 and expr2? If so, it is easier:

var body = Expression.AndAlso(expr1.Body, expr2.Body);
var lambda = Expression.Lambda<Func<T,bool>>(body, expr1.Parameters[0]);

This also works well to negate a single operation:

static Expression<Func<T, bool>> Not<T>(
    this Expression<Func<T, bool>> expr)
{
    return Expression.Lambda<Func<T, bool>>(
        Expression.Not(expr.Body), expr.Parameters[0]);
}

Otherwise, depending on the LINQ provider, you might be able to combine them with Invoke:

// OrElse is very similar...
static Expression<Func<T, bool>> AndAlso<T>(
    this Expression<Func<T, bool>> left,
    Expression<Func<T, bool>> right)
{
    var param = Expression.Parameter(typeof(T), "x");
    var body = Expression.AndAlso(
            Expression.Invoke(left, param),
            Expression.Invoke(right, param)
        );
    var lambda = Expression.Lambda<Func<T, bool>>(body, param);
    return lambda;
}

Somewhere, I have got some code that re-writes an expression-tree replacing nodes to remove the need for Invoke, but it is quite lengthy (and I can't remember where I left it...)

---

Generalized version that picks the simplest route:

static Expression<Func<T, bool>> AndAlso<T>(
    this Expression<Func<T, bool>> expr1,
    Expression<Func<T, bool>> expr2)
{
    // need to detect whether they use the same
    // parameter instance; if not, they need fixing
    ParameterExpression param = expr1.Parameters[0];
    if (ReferenceEquals(param, expr2.Parameters[0]))
    {
        // simple version
        return Expression.Lambda<Func<T, bool>>(
            Expression.AndAlso(expr1.Body, expr2.Body), param);
    }
    // otherwise, keep expr1 "as is" and invoke expr2
    return Expression.Lambda<Func<T, bool>>(
        Expression.AndAlso(
            expr1.Body,
            Expression.Invoke(expr2, param)), param);
}

Starting from .NET 4.0, there is the ExpressionVisitor class which allows you to build expressions that are EF safe.

    public static Expression<Func<T, bool>> AndAlso<T>(
        this Expression<Func<T, bool>> expr1,
        Expression<Func<T, bool>> expr2)
    {
        var parameter = Expression.Parameter(typeof (T));

        var leftVisitor = new ReplaceExpressionVisitor(expr1.Parameters[0], parameter);
        var left = leftVisitor.Visit(expr1.Body);

        var rightVisitor = new ReplaceExpressionVisitor(expr2.Parameters[0], parameter);
        var right = rightVisitor.Visit(expr2.Body);

        return Expression.Lambda<Func<T, bool>>(
            Expression.AndAlso(left, right), parameter);
    }

    private class ReplaceExpressionVisitor
        : ExpressionVisitor
    {
        private readonly Expression _oldValue;
        private readonly Expression _newValue;

        public ReplaceExpressionVisitor(Expression oldValue, Expression newValue)
        {
            _oldValue = oldValue;
            _newValue = newValue;
        }

        public override Expression Visit(Expression node)
        {
            if (node == _oldValue)
                return _newValue;
            return base.Visit(node);
        }
    }

Combining two expressions (ExpressionFuncT, bool) in a single one

You have missed parameters replacement. It is a tricky with visitors.
Trying to simplify your life, I would suggest to use popular library LINQKit
and rewrite your expression building.

public Expression<Func<AnyType, bool>> BuildExpression(int id, string filtreA, string filtreB)
{
    var predicate = PredicateBuilder.New<AnyType>(true);

    predicate = predicate.And(a => a.ID == id);

    if (!string.IsNullOrEmpty(filtreA))
    {
        predicate = predicate.And(a => a.TYPE == filtreA);
    }

    if (!string.IsNullOrEmpty(filtreB))
    {
        predicate = predicate.And(a => a.TYPE == filtreB);
    }
    
    return predicate;
}

How to combine expressions ExpressionFuncT1, T2, bool to a single ExpressionFuncT2, bool

Your Expression<Func<TNumbering, TConfiguration, bool>> is a generic type whose open generic type is Expression<TDelegate>, where TDelegate is some delegate type; in this case Func<TNumbering, TConfiguration, bool>.

Expression<TDelegate> inherits from LambdaExpression, which represents a C# (or VB.NET) lambda expression.

Just like you couldn't write the following code:

var result = 
    (n, c) => criteria.ConfigurationField(c) != criteria.NumberingField(n) ||
    (n1, c1) => criteria.ConfigurationField(c1) != criteria.NumberingField(n1);

trying to combine two LambdaExpressions with OrElse would throw an exception at runtime.

Your code isn't even compiling, because expression is typed as BinaryExpression, meaning an expression corresponding to this:

criteria.ConfigurationField(c) != criteria.NumberingField(n) ||
criteria.ConfigurationField(c1) != criteria.NumberingField(n1)

into which you're trying to put a full Expression<TDelegate>, which includes (for example) the parameter list.

---

Every LambdaExpression has a Body property, which extracts from an expression corresponding to this:

(n, c) => criteria.ConfigurationField(c) != criteria.NumberingField(n)

the body of the LambdaExpression, or an expression corresponding to this:

criteria.ConfigurationField(c) != criteria.NumberingField(n)

which, in theory, you could then combine into a BinaryExpression corresponding to this:

criteria.ConfigurationField(c) != criteria.NumberingField(n) ||
criteria.ConfigurationField(c1) != criteria.NumberingField(n1)

But this wouldn't work either, because each iteration introduces multiple new parameters, all of which you'd have to pass in to the final lambda.

---

It's possible to work around this problem, but I would suggest first and foremost you map each element in SelectionCriteria to an expression corresponding to the criteria evaluation, using the factory methods at System.Linq.Expressions.Expression. You could then combine those expressions into a BinaryExpression which you could then wrap up in a LambdaExpression or even an Expression.

It might look something like this (making some assumptions):

class Criteria<TConfiguration, TNumbering> {
    public Func<TConfiguration, string> ConfigurationField { get;}
    public Func<TNumbering, string> NumberingField { get; }
}

// using static System.Linq.Expressions.Expression;

var SelectionCritera = new List<Criteria>();

/*
 * populate list here
 */

var configParam = Parameter(typeof(TConfiguration));
var numberingParam = Parameter(typeof(TNumbering));
var expressions =
    SelectionCriteria.Select(criteria => {
        var criteriaExpr = Constant(criteria);

        return NotEqual(                   // !=
            Invoke(                        // ( ... )
                PropertyOrField(           // .ConfigurationField
                    criteriaExpr,          // criteria
                    "ConfigurationField"
                ),
                configParam                // c
            ),
            Invoke(                        // ( ... )
                PropertyOrField(           // .NumberingField
                    criteriaExpr,          // criteria
                    "NumberingField"
                ),
                numberingParam             // n
            )
        );  
    })
    .ToList();

if (!expressions.Any) { return Result.Failure("Expression not defined")); }

// Combine all the subexpressions using ||
var body = expressions.Aggregate((prev, next) => OrElse(prev, next));

// Create a LambdaExpression
var lmbd = Lambda<Func<TConfiguration, TNumbering, bool>>(body, configParam, numberingParam);

// Create a .NET method from the LambdaExpression
var mthd = lmbd.Compile();

// Apply the method to each config/numbering pair
var result = (
    from config in configs
    from numbering in numbering
    select (config, numbering)
).All(x => mthd(config, numbering));

ExpressionFuncT,bool vs FuncT,bool in method overloading

The expression that the compiler is complaining about is the argument to "CallTo" method:

A.CallTo(() => mandrill.SendMessageTemplate(A<SendMessageTemplateRequest>.That.Matches(...)));

So it doesn't matter which overload of Matches is chosen.

Composing invocations with ExpressionFuncT,bool the same way as FuncT,bool

Unfortunately, C# does not currently provide a way to compose expressions from Expression<Func<...>> objects. You have to use expression trees, which is quite a bit longer:

static Expression<Func<T,bool>> CheckExpr<T>(Expression<Func<T,Customer>> conv, string first, string last) {
    var arg = Expression.Parameter(typeof(T));
    var get = Expression.Invoke(conv, arg);
    return Expression.Lambda<Func<T,bool>>(
        Expression.MakeBinary(
            ExpressionType.AndAlso
        ,   Expression.MakeBinary(
                ExpressionType.Equal
            ,   Expression.Property(get, nameof(Customer.FirstName))
            ,   Expression.Constant(first)
            )
        ,   Expression.MakeBinary(
                ExpressionType.Equal
            ,   Expression.Property(get, nameof(Customer.LastName))
            ,   Expression.Constant(last)
            )
        )
    ,   arg
    );
}

Complex edit of a body ExpressionFuncT,bool

From how I see it, what you need is ExpressionVisitor to traverse and modify ExpressionTree. One thing I would change is the way you call Any.
Instead of

e.Entity != null && 
((e.Entity.ListA != null && e.Entity.ListA.Any(...)) 
|| (e.Entity.ListB != null && e.Entity.ListB.Any(...)))

I'd go for

(
    e.Entity != null && e.Entity.ListA != null && e.Entity.ListB != null
        ? e.Entity.ListA.Union(e.Entity.ListB)
        : e.Entity != null && e.Entity.ListA != null
            ? e.Entity.ListA
            : e.Entity.ListB != null
                ? e.Entity.ListB
                : new Entity[0]
).Any(...)

I find it easier to construct ExpressionTree and the outcome will be the same.

Example code:

public class OptionalCallFix : ExpressionVisitor
{
    private readonly List<Expression> _conditionalExpressions = new List<Expression>();
    private readonly Type _contextType;
    private readonly Type _entityType;

    private OptionalCallFix(Type contextType, Type entityType)
    {
        this._contextType = contextType;
        this._entityType = entityType;
    }

    protected override Expression VisitMethodCall(MethodCallExpression node)
    {
        // Replace Queryable.Union(left, right) call with:
        //     left == null && right == null ? new Entity[0] : (left == null ? right : (right == null ? left : Queryable.Union(left, right)))
        if (node.Method.DeclaringType == typeof(Queryable) && node.Method.Name == nameof(Queryable.Union))
        {
            Expression left = this.Visit(node.Arguments[0]);
            Expression right = this.Visit(node.Arguments[1]);

            // left == null
            Expression leftIsNull = Expression.Equal(left, Expression.Constant(null, left.Type));

            // right == null
            Expression rightIsNull = Expression.Equal(right, Expression.Constant(null, right.Type));

            // new Entity[0].AsQueryable()
            Expression emptyArray = Expression.Call
            (
                typeof(Queryable),
                nameof(Queryable.AsQueryable),
                new [] { this._entityType },
                Expression.NewArrayInit(this._entityType, new Expression[0])
            );

            // left == null && right == null ? new Entity[0] : (left == null ? right : (right == null ? left : Queryable.Union(left, right)))
            return Expression.Condition
            (
                Expression.AndAlso(leftIsNull, rightIsNull),
                emptyArray,
                Expression.Condition
                (
                    leftIsNull,
                    right,
                    Expression.Condition
                    (
                        rightIsNull,
                        left,
                        Expression.Call
                        (
                            typeof(Queryable), 
                            nameof(Queryable.Union), 
                            new [] { this._entityType }, 
                            left, 
                            Expression.Convert(right, typeof(IEnumerable<>).MakeGenericType(this._entityType))
                        )
                    )
                )
            );
        }

        return base.VisitMethodCall(node);
    }

    protected override Expression VisitMember(MemberExpression node)
    {
        Expression expression = this.Visit(node.Expression);

        // Check if expression should be fixed
        if (this._conditionalExpressions.Contains(expression))
        {
            // replace e.XXX with e == null ? null : e.XXX
            ConditionalExpression condition = Expression.Condition
            (
                Expression.Equal(expression, Expression.Constant(null, expression.Type)),
                Expression.Constant(null, node.Type),
                Expression.MakeMemberAccess(expression, node.Member)
            );

            // Add fixed expression to the _conditionalExpressions list
            this._conditionalExpressions.Add(condition);

            return condition;
        }

        return base.VisitMember(node);
    }

    protected override Expression VisitParameter(ParameterExpression node)
    {
        if (node.Type == this._contextType)
        {
            // Add ParameterExpression to the _conditionalExpressions list
            // It is used in VisitMember method to check if expression should be fixed this way
            this._conditionalExpressions.Add(node);
        }

        return base.VisitParameter(node);
    }

    public static IQueryable<TEntity> Fix<TContext, TEntity>(TContext context, in Expression<Func<TContext, IQueryable<TEntity>>> method)
    {
        return ((Expression<Func<TContext, IQueryable<TEntity>>>)new OptionalCallFix(typeof(TContext), typeof(TEntity)).Visit(method)).Compile().Invoke(context);
    }
}

You can call it like this:

OptionalCallFix.Fix(context, ctx => ctx.Entity.ListA.Union(ctx.ListB));

Combining multiple expressions (ExpressionFuncT,bool) not working with variables. Why?

The "how to fix" answer. Change this:

string col;
foreach(string c in columns) {
    col = c;
    Queries.Add(dr=> dr.Field<string>(col) == "somestring");
} 

to this:

foreach(string c in columns) {
    string col = c;
    Queries.Add(dr=> dr.Field<string>(col) == "somestring");
} 

Enjoy. The "what & why" answer was given by Brian.

Combine Expression (ExpressionFuncTIn,TOut with ExpressionFuncTOut, bool)

Using the common ExpressionVisitor for replacing one Expression with another, my standard Compose function (in the more common mathematical order, I think), substitutes the Body of one LambdaExpression for the parameter in another:

public static class ExpressionExt {
    // Compose: (y => f(y)).Compose(x => g(x)) -> x => f(g(x))
    /// <summary>
    /// Composes two LambdaExpression into a new LambdaExpression
    /// </summary>
    /// <param name="Tpg">Type of parameter to gFn, and type of parameter to result lambda.</param>
    /// <param name="Tpf">Type of result of gFn and type of parameter to fFn.</param>
    /// <param name="TRes">Type of result of fFn and type of result of result lambda.</param>
    /// <param name="fFn">The outer LambdaExpression.</param>
    /// <param name="gFn">The inner LambdaExpression.</param>
    /// <returns>LambdaExpression representing outer composed with inner</returns>
    public static Expression<Func<Tpg, TRes>> Compose<Tpg, Tpf, TRes>(this Expression<Func<Tpf, TRes>> fFn, Expression<Func<Tpg, Tpf>> gFn) =>
        Expression.Lambda<Func<Tpg, TRes>>(fFn.Body.Replace(fFn.Parameters[0], gFn.Body), gFn.Parameters[0]);

    /// <summary>
    /// Replaces an Expression (reference Equals) with another Expression
    /// </summary>
    /// <param name="orig">The original Expression.</param>
    /// <param name="from">The from Expression.</param>
    /// <param name="to">The to Expression.</param>
    /// <returns>Expression with all occurrences of from replaced with to</returns>
    public static Expression Replace(this Expression orig, Expression from, Expression to) => new ReplaceVisitor(from, to).Visit(orig);
}

/// <summary>
/// ExpressionVisitor to replace an Expression (that is Equals) with another Expression.
/// </summary>
public class ReplaceVisitor : ExpressionVisitor {
    readonly Expression from;
    readonly Expression to;

    public ReplaceVisitor(Expression from, Expression to) {
        this.from = from;
        this.to = to;
    }

    public override Expression Visit(Expression node) => node == from ? to : base.Visit(node);
}

With this available, your example is straightforward:

Expression<Func<One, Two>> convert = p1 => new Two(p1);
Expression<Func<Two, bool>> predicate = p2 => p2 == new Two();
Expression<Func<One, bool>> filter = predicate.Compose(convert);

However, especially with EF expressions, it may be preferable to use my replacement for Invoke, which handles null propogation, in cases where your arguments may be null. It also uses the same Replace ExpressionVisitor as above:

public static class ExpressionExt2 {   
    public static Expression PropagateNull(this Expression orig) => new NullVisitor().Visit(orig);

    // Apply: (x => f).Apply(args)
    /// <summary>
    /// Substitutes an array of Expression args for the parameters of a lambda, returning a new Expression
    /// </summary>
    /// <param name="e">The original LambdaExpression to "call".</param>
    /// <param name="args">The Expression[] of values to substitute for the parameters of e.</param>
    /// <returns>Expression representing e.Body with args substituted in</returns>
    public static Expression Apply(this LambdaExpression e, params Expression[] args) {
        var b = e.Body;

        foreach (var pa in e.Parameters.Zip(args, (p, a) => (p, a)))
            b = b.Replace(pa.p, pa.a);

        return b.PropagateNull();
    }
}

/// <summary>
/// ExpressionVisitor to replace a null.member Expression with a null
/// </summary>
public class NullVisitor : System.Linq.Expressions.ExpressionVisitor {
    public override Expression Visit(Expression node) {
        if (node is MemberExpression nme && nme.Expression is ConstantExpression nce && nce.Value == null)
            return Expression.Constant(null, nce.Type.GetMember(nme.Member.Name).Single().GetMemberType());
        else
            return base.Visit(node);
    }
}

public static class MeberInfoExt {
    public static Type GetMemberType(this MemberInfo member) {
        switch (member) {
            case FieldInfo mfi:
                return mfi.FieldType;
            case PropertyInfo mpi:
                return mpi.PropertyType;
            case EventInfo mei:
                return mei.EventHandlerType;
            default:
                throw new ArgumentException("MemberInfo must be if type FieldInfo, PropertyInfo or EventInfo", nameof(member));
        }
    }    
}

Given Apply, your Compose is simply:

public static Expression<Func<T1, bool>> Compose<T1, T2>(this Expression<Func<T1, T2>> convertExpr, Expression<Func<T2, bool>> predicate)
    => Expression.Lambda<Func<T1, bool>>(predicate.Apply(convertExpr.Body), convertExpr.Parameters.First());

---

Related Topics