Expression Equality Comparer: Part I

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:

    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:

    // 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

    /// <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.

    /// <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

    /// <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!