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;

Malony

Did you try it? LinqPad is great to test small snippets of code. – Dumpcart

The question isn't based on a correct premise; a Dictionary<,> does not use the == operator for key-equality. – Diphosgene

In this case you have they have neither the same reference nor value. – Bedpost

@Bedpost seems to me like their value is the same (even though they use reference equality semantics): the expression tree generated will have objects with the same types and with the same values. Even their string representation will be the same. – Dumpcart

Answer 1

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.

Annulus

No. The name of the ParameterExpression would be different. But I get your drift. I would think the behavior should be that my expressions return true and that your expression would return false, since an implementation could depend on the name of the parameter. – Malony

@Malony even allowing for "innocent" changes like this, I think it would be a real struggle to do this in the general case. – Annulus

@smartcaveman: if you don't want semantic equality like Marc showed, and want everything to be exactly equal, including parameters names and such, you could write your own ExpressionVisitor for the comparison. – Dumpcart

@Marc, yup, I agree with you. I was just kinda hoping it was already baked in there for me. – Malony

@Martinho @Malony - indeed; a full visitor is a lot of work, especially in 4.0 – Annulus

@Marc Do you know if any examples of such "full visitors" exist freely available? – Aegospotami

@cottsak - one is built into .NET 4.0: ExpressionVisitor - if you clarify what you want to do, I might be able to be more specific – Annulus

Oh wow. I simply want to create a function that returns bool if one Expression<Func<T, bool>> is equal to another. Equal in the syntactical semantics of the expression tree sense. It's for my unit tests. I'm checking to see if some dynamic expression building code is working correctly. – Aegospotami

@cottsak - that is pretty hard to do robustly. I've spent huge amounts of time with Expression, and personally I would try to sidestep that requirement - that is brittle and tricky – Annulus

@Marc As i guessed. I also have been trying to side-step it by writing tests that assert matching elements of mocked source and unmatching elements of the same mocked source. Then asserting the same matches and non-matches from the source with the generated expressions applied to it and mandating the same results for the mock as the generated expressions. Do you think this is reasonable or is there a much simpler way to meet half-way between say (a) plugging values into expected and actual delegates verses (b) going the full hog and building the visitor to compare equality? – Aegospotami

Answer 2

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.

Salomon

Your first statement is misleading. Types can provide static == operators – Annulus

Also, there are a myriad of Expression classes; the subclass route is not an option here. – Annulus

Is that better? Or are you referring to something I don't understand? – Salomon

This is not true with all objects. (Consider String). I don't think overriding would get the functionality I want, but I could create a wrapper that evaluates the expression, but as Marc noted that would probably result in more work than value. – Malony

@jamietre no, even a class can define an == operator. If it does, the compiler will use the defined operator instead of referenceequals. – Annulus

What do you mean by subclassing isn't an option? The generic expression inherits Expression. – Salomon

@Malony - string is immutable. I really didn't mean to get into a value vs. reference type thing and all that, sorry my language is not precise. – Salomon

@jamietre yes, but an outermost lambda expression is composed of lots and lots of others - you might be surprised how many objects are in even the simple examples above. – Annulus

Marc, I'm with you, but still not understanding why you couldn't use a derived class in this way. If the object you create to add to the dictionary is of your derived type, while the inner Expressions would not be, the dictionary will only be asking the outermost object for it's hash code won't it? – Salomon

Oh... ok, a minute of tinkering revealed that the generic Expression is sealed. – Salomon

Final note: while you could still accomplish this by creating a wrapper class instead of trying to inherit, in the end we're still facing the same issue as your answer: how to compare the functions for equality. So I suppose it doesn't really matter. – Salomon

Answer 3

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

Kain

I think that these two methods should not evaluate to be equal. But, do you know of a way to inspect a method body? – Malony

You can get the method body reflectively by obtaining a MethodInfo for the method in question. There may also be a way to examine it using a PartialEvaluator (from the IQToolkit); I know Linq2SQL and some other ORMs with Linq providers seem to be able to convert user-defined extension methods, I just don't know how easy it would be to replicate that (probably not easy at all). – Kain