I love expression trees. They were a great addition to the .NET Framework. I do get a sense from the community that they are somewhat underutilized, however that may just be the nature of things that lack triviality. Let’s spend some time on expression trees and talk a bit about how one might go about comparing one expression tree to another.
Expressions and Reference Equality
If you’ve ever spent some time pouring over the MSDN documentation for the Expression
class, you may have noticed that it does not override Object.Equals
. This means, then, that only reference equality will be checked when comparing two Expression
objects. It will not check equality in the sense that the expression trees deriving from the Expression
objects look and function the same.
Take a look at an example of this below:
1 2 3 4 | Expression < Func < string , bool >> first = x => x.Length == 4; Expression < Func < string , bool >> second = x => x.Length == 4; Console .WriteLine(first.Equals(second)); // Output is "False" |
There is nothing wrong with this; this is all expected when you forego overriding Object.Equals
. But what if we want to be able to tell whether or not two separately provided expression trees are, in essence, “the same” in the sense that saying x.Length == 4
is the same as saying x.Length == 4
?
An example where this would be nice is if we were maintaining a dictionary of ImportantStuff
that used Expression
objects representing conditions as keys. Let’s call this an ExpressiveDictionary
. An example of its use is below:
1 2 3 4 5 6 7 8 | // ExpressiveDictionary implements IDictionary<Expression<Func<TKey,bool>>, TValue> ExpressiveDictionary<HumorlessKey> dictionary = new ExpressiveDictionary<HumorlessKey>(); ImportantStuff stuff = new ImportantStuff(); dictionary.Add(x => x.EasilyOffended, stuff); Console .WriteLine(stuff.Equals(dictionary[x => x.EasilyOffended])); // Output is "True" |
I’m not saying that something like the above example is something you want to have in your product necessarily, rather it is there for demonstrative purposes. Personally, I decided to figure out a solution for this as the new platform I’m developing had presented a problem which merited its use.
I’m going to present a portion of that solution in this article; the remaining portions will be covered in a future article.
A Custom Equality Comparer : ExpressionEqualityComparer
We’re going to need to go full throttle with this one. We’re going to need to essentially override the standard Equals
logic, and we want our logic to be able to be used in a Dictionary
-like class. This means, then, that we’re going to need to implement our own custom IEqualityComparer<T>
. Starting there will tell us quickly what exactly we need to do.
During one of my forays into the bowels of the Internet, I stumbled upon a solution to this problem that is part of a larger project known asLINQ to db40. Other than its name, there isn’t much else I know about this project. The source code for this project may be found here. The solution to this particular problem offered by this project was helpful in getting me started, however it was designed to work against the first incarnation of the Expression
type, which came out with .NET Framework 3.5. Attempting to use this solution with .NET Framework 4.0 wouldn’t end up working out too well for you.
The Expression
type has undergone many changes with .NET 4.0, and a lot of new expression types have been added. The solution I’m going to present is one that will work with .NET 4.0, with many other changes as well (not just ones for Framework version compatibility purposes).
So, let’s take a look at this equality comparer:
ExpressionEqualityComparer.cs
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | /// <summary> /// Provides methods to compare <see cref="Expression"/> objects for equality. /// </summary> public class ExpressionEqualityComparer : IEqualityComparer< Expression > { private static readonly ExpressionEqualityComparer _Instance = new ExpressionEqualityComparer(); /// <summary> /// Gets the default <see cref="ExpressionEqualityComparer"/> instance. /// </summary> public static ExpressionEqualityComparer Instance { get { return _Instance; } } /// <inheritdoc/> public bool Equals( Expression x, Expression y) { return new ExpressionComparison(x, y).AreEqual; } /// <inheritdoc/> public int GetHashCode( Expression obj) { return new ExpressionHashCodeCalculator(obj).Output; } } |
I rarely use singletons, but felt that one was justified here as we have precedent with the Microsoft-provided EqualityComparer<T>
class, which offers a default instance with its Default
property.
Not much going on here, but we can plainly see what we need to implement in order to realize this solution. We’re going to need to create a class which will handle the actual comparison between two Expression
objects, and then we also need to create a class which will guarantee unique hash codes for different (looking) expression trees.
Given that we are dealing with expression trees here, it should make sense that both of these classes are going to be expression visitors, or rather: subclasses of the (now) Microsoft-provided ExpressionVisitor
class (new to .NET 4.0; it was internal previously).
This article is concerned with implementing the first required type shown above, namely the ExpressionComparison object. A second article may come in the future that deals with how we implement the hash code calculator.
Custom Expression Tree Comparison: ExpressionComparison
The first class we’re going to implement is an ExpressionVisitor
that determines whether two expression trees are equal (in content, not only by reference). It does this by walking down both trees simultaneously, comparing each node along the way.
A note about the code before we proceed. All the code I’m providing tonight has received 100% coverage in testing from myself (let me tell you…took a lot of testing code to hit all the areas, but it sure got me acquainted with all the various flavors of expression types out there), however that does not mean the code is necessarily 100% tested, of course. I’m fairly certain that it does the job reliably, however I make no guarantees. If you have any questions about a specific part of the code, let me know.
ExpressionComparison.cs
Update: Thanks to Denis in the comments for pointing out that there was a lack of support for constant collections; code has now been updated to support constant collections.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 | /// <summary> /// Provides a visitor that determines whether two expression trees are equal (by content, not /// only by reference) by walking down both trees simultaneously and comparing each node. /// </summary> public sealed class ExpressionComparison : ExpressionVisitor { private Expression _comparand; private readonly Queue < Expression > _comparands; /// <summary> /// Initializes a new instance of the <see cref="ExpressionComparison"/> class. /// </summary> /// <param name="firstExpression">The first expression tree to compare.</param> /// <param name="secondExpression">The second expression tree to compare.</param> public ExpressionComparison( Expression firstExpression, Expression secondExpression) { ExpressionsAreEqual = true ; _comparands = new Queue < Expression >( new ExpressionCollection(secondExpression)); Visit(firstExpression); if (0 < _comparands.Count) ExpressionsAreEqual = false ; } /// <summary> /// Gets a value indicating if the two provided expression trees were found to be equal in /// content. /// </summary> public bool ExpressionsAreEqual { get ; private set ; } /// <summary> /// Processes the provided <see cref="Expression"/> object by loading the next node coming /// from the expression tree being compared against and then dispatching both to more /// specialized visitors for more specific comparison. /// </summary> /// <param name="node">The expression to process and dispatch.</param> /// <returns> /// The modified expression, assuming the expression was modified; otherwise, returns the /// original expression. /// </returns> public override Expression Visit( Expression node) { if ( null == node || !ExpressionsAreEqual) return node; if (0 == _comparands.Count) return Fail(node); _comparand = _comparands.Peek(); if (_comparand.NodeType != node.NodeType || _comparand. Type != node. Type ) return Fail(node); _comparands.Dequeue(); return base .Visit(node); } /// <inheritdoc/> protected override Expression VisitBinary(BinaryExpression node) { BinaryExpression comparand = (BinaryExpression) _comparand; if (!AreEqual(node, comparand, x => x.Method)) return Fail(node); return AreEqual(node, comparand, x => x.IsLifted, x => x.IsLiftedToNull) ? base .VisitBinary(node) : Fail(node); } /// <inheritdoc/> protected override Expression VisitConstant(ConstantExpression node) { ConstantExpression comparand = (ConstantExpression)_comparand; IEnumerable nodeSequence = node.Value as IEnumerable ; IEnumerable comparandSequence = comparand.Value as IEnumerable ; // The SequenceEqual method seen here is a custom extension method. I'll post it sometime. bool areEqual = null != nodeSequence && null != comparandSequence ? nodeSequence.SequenceEqual(comparandSequence) : AreEqual(node, comparand, x => x.Value); return areEqual ? base .VisitConstant(node) : Fail(node); } /// <inheritdoc/> protected override Expression VisitDebugInfo(DebugInfoExpression node) { DebugInfoExpression comparand = (DebugInfoExpression) _comparand; if (!AreEqual(node, comparand, x => x.IsClear)) return Fail(node); return AreEqual(node, comparand, x => x.EndColumn, x => x.EndLine, x => x.StartLine, x => x.StartColumn) ? base .VisitDebugInfo(node) : Fail(node); } /// <inheritdoc/> protected override Expression VisitDynamic(DynamicExpression node) { DynamicExpression comparand = (DynamicExpression) _comparand; if (!AreEqual(node, comparand, x => x.DelegateType)) return Fail(node); return AreEqual(node, comparand, x => x.Binder) ? base .VisitDynamic(node) : Fail(node); } /// <inheritdoc/> protected override Expression VisitGoto(GotoExpression node) { GotoExpression comparand = (GotoExpression) _comparand; if (!AreEqual(node, comparand, x => x.Kind)) return Fail(node); return AreEqual(node.Target, comparand.Target) ? base .VisitGoto(node) : Fail(node); } /// <inheritdoc/> protected override Expression VisitIndex(IndexExpression node) { IndexExpression comparand = (IndexExpression) _comparand; return AreEqual(node, comparand, x => x.Indexer) ? base .VisitIndex(node) : Fail(node); } /// <inheritdoc/> protected override Expression VisitLabel(LabelExpression node) { LabelExpression comparand = (LabelExpression) _comparand; return AreEqual(comparand.Target, node.Target) ? base .VisitLabel(node) : Fail(node); } /// <inheritdoc/> protected override Expression VisitLambda<T>( Expression <T> node) { LambdaExpression comparand = (LambdaExpression) _comparand; // If lambda expression differs in return type, the expression's type property itself // is different. Thus, there is no need to compare return types since all expressions // have their types compared before anything else. if (!AreEqual(node, comparand, x => x.Name)) return Fail(node); return AreEqual(node, comparand, x => x.TailCall) ? base .VisitLambda(node) : Fail(node); } /// <inheritdoc/> protected override Expression VisitListInit(ListInitExpression node) { ListInitExpression comparand = (ListInitExpression) _comparand; return AreEqual(node, comparand, x => x.Initializers, AreEqual) ? base .VisitListInit(node) : Fail(node); } /// <inheritdoc/> protected override Expression VisitLoop(LoopExpression node) { LoopExpression comparand = (LoopExpression) _comparand; if (!AreEqual(comparand.BreakLabel, node.BreakLabel)) return Fail(node); return AreEqual(comparand.ContinueLabel, node.ContinueLabel) ? base .VisitLoop(node) : Fail(node); } /// <inheritdoc/> protected override Expression VisitMember( MemberExpression node) { MemberExpression comparand = ( MemberExpression ) _comparand; return AreEqual(node, comparand, x => x.Member) ? base .VisitMember(node) : Fail(node); } ///<inheritdoc/> protected override Expression VisitMemberInit(MemberInitExpression node) { MemberInitExpression comparand = (MemberInitExpression) _comparand; return AreEqual(node, comparand, x => x.Bindings, AreEqual) ? base .VisitMemberInit(node) : Fail(node); } /// <inheritdoc/> protected override Expression VisitMethodCall(MethodCallExpression node) { MethodCallExpression comparand = (MethodCallExpression)_comparand; return AreEqual(node, comparand, x => x.Method) ? base .VisitMethodCall(node) : Fail(node); } /// <inheritdoc/> protected override Expression VisitNew(NewExpression node) { NewExpression comparand = (NewExpression)_comparand; if (!AreEqual(node, comparand, x => x.Constructor)) return Fail(node); return AreEqual(node, comparand, x => x.Members) ? base .VisitNew(node) : Fail(node); } /// <inheritdoc/> protected override Expression VisitSwitch(SwitchExpression node) { SwitchExpression comparand = (SwitchExpression) _comparand; return AreEqual(node, comparand, x => x.Comparison) ? base .VisitSwitch(node) : Fail(node); } /// <inheritdoc/> protected override Expression VisitTry(TryExpression node) { TryExpression comparand = (TryExpression) _comparand; return AreEqual(node, comparand, x => x.Handlers, AreEqual) ? base .VisitTry(node) : Fail(node); } /// <inheritdoc/> protected override Expression VisitTypeBinary(TypeBinaryExpression node) { TypeBinaryExpression comparand = (TypeBinaryExpression) _comparand; return AreEqual(node, comparand, x => x.TypeOperand) ? base .VisitTypeBinary(node) : Fail(node); } /// <inheritdoc/> protected override Expression VisitUnary(UnaryExpression node) { UnaryExpression comparand = (UnaryExpression)_comparand; if (!AreEqual(node, comparand, x => x.Method)) return Fail(node); return AreEqual(node, comparand, x => x.IsLifted, x => x.IsLiftedToNull) ? base .VisitUnary(node) : Fail(node); } /// <summary> /// Verifies that the provided <see cref="LabelTarget"/> objects are equal. /// </summary> /// <param name="first">The first <see cref="LabelTarget"/> object to compare.</param> /// <param name="second">The second <see cref="LabelTarget"/> object to compare.</param> /// <returns>True if <c>first</c> and <c>second</c> are equal; otherwise, false.</returns> private static bool AreEqual(LabelTarget first, LabelTarget second) { // Label targets are commonly exist individually and many times can left at null // without invalidating the expression. if ( null == first || null == second) { return first == second; } return first.Name == second.Name && first. Type == second. Type ; } /// <summary> /// Verifies that the provided <see cref="CatchBlock"/> objects are equal. /// </summary> /// <param name="first">The first <see cref="CatchBlock"/> object to compare.</param> /// <param name="second">The second <see cref="CatchBlock"/> object to compare.</param> /// <returns>True if <c>first</c> and <c>second</c> are equal; otherwise, false.</returns> private static bool AreEqual(CatchBlock first, CatchBlock second) { return first.Test == second.Test; } /// <summary> /// Verifies that the provided <see cref="ElementInit"/> objects are equal. /// </summary> /// <param name="first">The first <see cref="ElementInit"/> object to compare.</param> /// <param name="second">The second <see cref="ElementInit"/> object to compare.</param> /// <returns>True if <c>first</c> and <c>second</c> are equal; otherwise, false.</returns> private static bool AreEqual(ElementInit first, ElementInit second) { return first.AddMethod == second.AddMethod; } /// <summary> /// Verifies that the provided <see cref="MemberBinding"/> objects are equal. /// </summary> /// <param name="first">The first <see cref="MemberBinding"/> object to compare.</param> /// <param name="second">The second <see cref="MemberBinding"/> object to compare.</param> /// <returns>True if <c>first</c> and <c>second</c> are equal; otherwise, false.</returns> private static bool AreEqual(MemberBinding first, MemberBinding second) { if (first.BindingType != second.BindingType || first.Member != second.Member) return false ; if (MemberBindingType.ListBinding != first.BindingType) return true ; MemberListBinding firstList = (MemberListBinding)first; MemberListBinding secondList = (MemberListBinding)second; return AreEqual(firstList, secondList, x => x.Initializers, AreEqual); } /// <summary> /// Verifies property values from two items are equal. /// </summary> /// <typeparam name="T"> /// The type of item that the properties being compared belong to. /// </typeparam> /// <typeparam name="TMember">The type of the properties being compared.</typeparam> /// <param name="first">The first item having one of its properties compared.</param> /// <param name="second">The second item having one of its properties compared.</param> /// <param name="reader"> /// Method able to extract the property values being compared from the provided items. /// </param> /// <returns>True if the two item property values are equal; otherwise, false.</returns> private static bool AreEqual<T,TMember>(T first, T second, params Func <T,TMember>[] reader) { return reader.All(r => EqualityComparer<TMember>.Default.Equals(r(first), r(second))); } /// <summary> /// Verifies that specified collections coming from the two provided items are equal in /// content using the provided reader to retrieve the collections as well as the /// provided comparer to perform the comparison. /// </summary> /// <typeparam name="T"> /// The type of the items hosting the collections being compared. /// </typeparam> /// <typeparam name="TMember"> /// The type of items that make up the collections being compared. /// </typeparam> /// <param name="first">The first item that has a collection to compare.</param> /// <param name="second">The second item that has a collection to compare.</param> /// <param name="reader"> /// Method able to extract the collections from the provided items. /// </param> /// <param name="comparer"> /// The comparer to use to compare the content of the collections. /// </param> /// <returns> /// True if the collections are equal according to <c>comparer</c>; otherwise, false. /// </returns> private static bool AreEqual<T, TMember>( T first, T second, Func <T, ReadOnlyCollection<TMember>> reader, Func <TMember, TMember, bool > comparer = null ) { if ( null == comparer) comparer = (x, y) => EqualityComparer<TMember>.Default.Equals(x, y); ReadOnlyCollection<TMember> firstCollection = reader(first); ReadOnlyCollection<TMember> secondCollection = reader(second); if ( null == firstCollection || null == secondCollection) { return firstCollection == secondCollection; } return !firstCollection.Where((t, i) => !comparer(t, secondCollection[i])).Any(); } /// <summary> /// Fails the comparison operation, setting the outcome of the comparison to be that the /// two expression trees are "not equal", as well as returning an <see cref="Expression"/> /// value which, if returned by a visitor operation, will result in all operations coming /// to a stop. /// </summary> /// <param name="node">The current node being visited.</param> /// <returns> /// An <see cref="Expression"/> value which should be returned by the calling visitor /// operation. /// </returns> private Expression Fail( Expression node) { ExpressionsAreEqual = false ; return node; } } |
What our ExpressionComparison
visitor does walk down a provided expression tree while comparing each node it encounters with nodes from another tree that are stored in a queue. The queue is created through the use of another visitor known as an ExpressionCollection
, which basically converts an expression tree into an IEnumerable<T>
sequence of the nodes found on that tree. The code for that class will be provided at the end of this article.
In each visitor method, certain data points are compared between the two comparand nodes. If any points of data do not match, we fail the comparison check by setting the outcome of the check to false
and aborting our walk.
As you may have already known, we saw additional types of Expression
nodes added to .NET Framework 4.0. Our visitor overrides almost all possible overrides in order to compare every type of node possible. The ExpressionComparison
type, as it is presented, should be able to support any expression tree found in the universal set of all possible expression trees.
How can this be true if we don’t override all possible Visit*
methods? Well, we don’t need to; not all Expression
object types have data unique to their class. Many Expression
object types also simply contain other Expression
instances, which are taken care of by the more general visitor overrides when walking further down the tree anyways.
A Visitor To Collect Expressions: ExpressionCollection
Briefly referenced in the last section, we also employ a simple expression visitor that will take an expression tree and provide all nodes belonging to that tree in the form of an IEnumerable<T>
sequence. The code for that will now be provided:
ExpressionCollection.cs
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | /// <summary> /// Provides an <see cref="IEnumerable{Expression}"/> created by walking through an expression /// tree. /// </summary> public sealed class ExpressionCollection : ExpressionVisitor, IEnumerable < Expression > { private readonly List < Expression > _expressions = new List < Expression >(); /// <summary> /// Initializes a new instance of the <see cref="ExpressionCollection"/> class. /// </summary> /// <param name="expression"> /// The expression tree to walk when populating this collection. /// </param> public ExpressionCollection( Expression expression) { Visit(expression); } IEnumerator IEnumerable .GetEnumerator() { return GetEnumerator(); } /// <inheritdoc/> public IEnumerator< Expression > GetEnumerator() { return _expressions.GetEnumerator(); } /// <summary> /// Processes the provided <see cref="Expression"/> object by adding it to this collection /// and then walking further down the tree. /// </summary> /// <param name="node"> /// The expression to process to add to this collection and walk through. /// </param> /// <returns> /// The modified expression, assuming the expression was modified; otherwise, returns the /// original expression. /// </returns> public override Expression Visit( Expression node) { if ( null != node) _expressions.Add(node); return base .Visit(node); } } |
In the next article, we can talk about the ExpressionHashCodeCalculator
, if I get around to posting it!
Hello there, thanks for the tip, but where is Part II?
Excellent job! Thanks for the article! What about part 2?
Thanks for your interest. I’ll be sure to write a second part to this soon.
[...] a previous article I wrote, I introduced a way to compare expressions on the basis of their makeup as opposed to simple [...]
I’m impressed, I must say. Seldom do I encounter a blog that’s both
equally educative and engaging, and without
a doubt, you have hit the nail on the head.
The problem is something too few folks are speaking intelligently
about. I am very happy that I came across this during
my hunt for something concerning this.