How to check if two Expression<Func<T, bool>> are the same [duplicate]

Question

Is it possible to find out if two expressions are the same?

Like given the following four expressions:

        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;

Then, at least we can see that:

• a == b
• a != c
• a != d

But can I do anything to find this out in my code?

Took a peek in the msdn library, where it says that

Equals: Determines whether the specified Object is equal to the current Object. (Inherited from Object.)

which I guess means that at least the Expression class hasn't overrided the equals method to become Equatable? So how would you do this? Or am I asking too much here? :p

Casebook

If there is a MemberInfo involved there, I mean some method, property of field, then you can get the memberinfo first, and compute its hash – Harmonious

Answer 1

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.

Bawd

Did look promising, but what are these ExpressionComparison(a, b).AreEqual and HashCodeCalculation(expression).HashCode? – Casebook

You can browse the implementation, they're in the same folder. – Bawd

I think I'll just try to find another way to solve what I am trying to figure out :p But your answer seems to provide a working solution, so I'll mark it as Accepted =) – Casebook

You have to pull in great swathes of code to get this to work,such as the reimplementation of ExpressionVisitor :( – Lackey

@JohnNolan, you do. For .net 3.5, ExpressionVisitor is not exposed, so you have to roll your own. For .net 4.0, this code needs to be updated to new types of expressions. As it's not a built-in, it's not surprising it's quite a bit of work. – Bawd

indeed a huge efforts has gone into this solution. – Lackey

@JbEvain The solution seems fine but source are no more available :-( – Heymann

Answer 2

As a lazy answer, you can check ToString() - it should at least indicate where they are clearly different (although it will include the var-name in there, so that would have to be the same).

For checking equivalence accurately... much harder - a lot of work, over a lot of different node types.

Rubricate

Lol, now that may actually kind of work... :D – Casebook

No, not every expression has a usable string representation. Convert for instance doesn't indicate which types it converts to. – Bawd

Exactly - I said it would find obviously wrong answers, but that is about it. You'd need to walk the tree properly, checking the actual operators used, etc, to do a thorough job. – Rubricate

Still thanks for sharing. Might be good in some simple scenarios. – Fraternity

Actually it did not work for me on expression. I used LambdaCompare and Explosuress for that task. But that solution did work for Func<> equality. – Covariance

Answer 3

It strikes me that this might be difficult to do, except in the simplest of cases.

For example:

var numbers1 = Enumerable.Range(1, 20);
Expression<Func<int, IEnumerable<int>>> a = x => numbers1;
var numbers2 = Enumerable.Range(1, 20);
Expression<Func<int, IEnumerable<int>>> b = x => numbers2;

Technically, these are equal, but how could it be determined without evaluating the IEnuemrable returned in each expression?

Themistocles

I'm asking you guys here :p hehe. But yes, I can see the problem.. but I can also.. not see it. Cause like you said, technically those are in fact equal. And, at least I, would think that one expression tree should be comparable to another expression tree based on their nodes and data types. – Casebook

In your example I think I might have considered those expressions unequal though, since they contain a reference to an object which are not the same... – Casebook

numbers1 or numbers2 will be serialized as a ConstantExpression node, whose values won't be equal. – Bawd

@Jb: are Expressions serializeable? – Casebook

But there is hope. In this post I explain how to serialize linq expressions - shunra.com/shunrablog/index.php/2009/07/16/… – Hygrometry

I would consider your expression of the question more or less equal to the OP's. – Ause

Those are are not equal by definition, because both reference a different instance of IEnumerable<int> in a closure which turns into a ConstantExpression holding a reference to a RangeEnumerable in Value property, and those do not implement neither Equals, nor GetHashCode in a sensible way. – Package

the returned value is unimportnat for expression equality. Consider () => DateTime.Now, which will return different value each time called. – Sequel