How do Linq Expressions determine equality?

Question

I am considering using a Linq Expression as a key in a dictionary. However, I am concerned that I will get strange results, because I don't know how Equality is determined by Linq expressions.

Does a class derived from Expression compare value equality or reference equality? Or in other words,

        Expression<Func<object>> first = () => new object(); 
        Expression<Func<object>> second = ()=>new object();
        bool AreTheyEqual = first == second;

Answer 1

As others have noted, Expression's == operator uses the default "reference equality" check - "Are they both a reference to the same place in the heap?". This means that code like your example will likely return false, since your expression literals will be instantiated as different Expression instances regardless of any semantic equality. There are similar frustrations with using lambdas as event handlers:

MyEvent += (s, a) => DoSomething();
...
MyEvent -= (s, a) => DoSomething(); //<-- will NOT remove the added handler

Checking for semantic equality is tricky. In this particular case, you might be able to visit all the nodes of the expression tree and compare all strings, value types and method references to determine that they do the same thing. However, by inspection, the two lambdas in the following example are semantically equivalent, but you'd have a hard time writing a method to prove it:

   public void MyMethod() {...}
   public void AnotherMethod { MyMethod(); };

   ...

   Action one = () => MyMethod();
   Action two = () => AnotherMethod();

   var equal = one == two; // false

Answer 2

Your test compares expressions. Expressions themselves offer only reference equality; your test will probably show "false". To cheek for semantic equality you would need to do a lot of work, for example - are:

x => 123

And

y => 123

Equivalent? As a crude test you can compare ToString(), but this will be exceptionally brittle.

Answer 3

Comparing any two objects that aren't value types (including an Expression) with == compares object references, so they won't be equal. As a commenter noted, though, a dictionary would be using Equals and GetHashCode to determine equality, which would still by default end up determining that they were not equal.

You could probably create a class that inherits System.Linq.Expression and override GetHashCode and Equals to use the result somehow, though, and use that as the key for your dictionary.