C# 测试 lambda 表达式相等性的最有效方法

Most efficient way to test equality of lambda expressions

提问by JontyMC

Given a method signature:

给定一个方法签名：

public bool AreTheSame<T>(Expression<Func<T, object>> exp1, Expression<Func<T, object>> exp2)

What would be the most efficient way to say if the two expressions are the same? This only needs to work for simple expressions, by this I mean all that would be "supported" would be simple MemberExpressions, eg c => c.ID.

如果两个表达式相同，最有效的说法是什么？这只需要对简单的表达式起作用，我的意思是所有“支持”的都是简单的 MemberExpressions，例如 c => c.ID。

An example call might be:

一个示例调用可能是：

AreTheSame<User>(u1 => u1.ID, u2 => u2.ID); --> would return true

采纳答案by Marc Gravell

Hmmm... I guess you'd have to parse the tree, checking the node-type and member of each. I'll knock up an example...

嗯...我猜你必须解析树，检查每个节点的类型和成员。我举个例子...

using System;
using System.Linq.Expressions;
class Test {
    public string Foo { get; set; }
    public string Bar { get; set; }
    static void Main()
    {
        bool test1 = FuncTest<Test>.FuncEqual(x => x.Bar, y => y.Bar),
            test2 = FuncTest<Test>.FuncEqual(x => x.Foo, y => y.Bar);
    }

}
// this only exists to make it easier to call, i.e. so that I can use FuncTest<T> with
// generic-type-inference; if you use the doubly-generic method, you need to specify
// both arguments, which is a pain...
static class FuncTest<TSource>
{
    public static bool FuncEqual<TValue>(
        Expression<Func<TSource, TValue>> x,
        Expression<Func<TSource, TValue>> y)
    {
        return FuncTest.FuncEqual<TSource, TValue>(x, y);
    }
}
static class FuncTest {
    public static bool FuncEqual<TSource, TValue>(
        Expression<Func<TSource,TValue>> x,
        Expression<Func<TSource,TValue>> y)
    {
        return ExpressionEqual(x, y);
    }
    private static bool ExpressionEqual(Expression x, Expression y)
    {
        // deal with the simple cases first...
        if (ReferenceEquals(x, y)) return true;
        if (x == null || y == null) return false;
        if (   x.NodeType != y.NodeType
            || x.Type != y.Type ) return false;

        switch (x.NodeType)
        {
            case ExpressionType.Lambda:
                return ExpressionEqual(((LambdaExpression)x).Body, ((LambdaExpression)y).Body);
            case ExpressionType.MemberAccess:
                MemberExpression mex = (MemberExpression)x, mey = (MemberExpression)y;
                return mex.Member == mey.Member; // should really test down-stream expression
            default:
                throw new NotImplementedException(x.NodeType.ToString());
        }
    }
}

回答by neleus

UPDATE:Due to interest to my solution, I have updated the code so it supports arrays, new operators and other stuff and compares the ASTs in more elegant way.

更新：由于对我的解决方案感兴趣，我更新了代码，使其支持数组、新运算符和其他内容，并以更优雅的方式比较 AST。

Here is an improved version of Marc's code and now it's available as a nuget package:

这是 Marc 代码的改进版本，现在它可以作为nuget 包使用：

public static class LambdaCompare
{
    public static bool Eq<TSource, TValue>(
        Expression<Func<TSource, TValue>> x,
        Expression<Func<TSource, TValue>> y)
    {
        return ExpressionsEqual(x, y, null, null);
    }

    public static bool Eq<TSource1, TSource2, TValue>(
        Expression<Func<TSource1, TSource2, TValue>> x,
        Expression<Func<TSource1, TSource2, TValue>> y)
    {
        return ExpressionsEqual(x, y, null, null);
    }

    public static Expression<Func<Expression<Func<TSource, TValue>>, bool>> Eq<TSource, TValue>(Expression<Func<TSource, TValue>> y)
    {
        return x => ExpressionsEqual(x, y, null, null);
    }

    private static bool ExpressionsEqual(Expression x, Expression y, LambdaExpression rootX, LambdaExpression rootY)
    {
        if (ReferenceEquals(x, y)) return true;
        if (x == null || y == null) return false;

        var valueX = TryCalculateConstant(x);
        var valueY = TryCalculateConstant(y);

        if (valueX.IsDefined && valueY.IsDefined)
            return ValuesEqual(valueX.Value, valueY.Value);

        if (x.NodeType != y.NodeType
            || x.Type != y.Type)
        {
            if (IsAnonymousType(x.Type) && IsAnonymousType(y.Type))
                throw new NotImplementedException("Comparison of Anonymous Types is not supported");
            return false;
        }

        if (x is LambdaExpression)
        {
            var lx = (LambdaExpression)x;
            var ly = (LambdaExpression)y;
            var paramsX = lx.Parameters;
            var paramsY = ly.Parameters;
            return CollectionsEqual(paramsX, paramsY, lx, ly) && ExpressionsEqual(lx.Body, ly.Body, lx, ly);
        }
        if (x is MemberExpression)
        {
            var mex = (MemberExpression)x;
            var mey = (MemberExpression)y;
            return Equals(mex.Member, mey.Member) && ExpressionsEqual(mex.Expression, mey.Expression, rootX, rootY);
        }
        if (x is BinaryExpression)
        {
            var bx = (BinaryExpression)x;
            var by = (BinaryExpression)y;
            return bx.Method == @by.Method && ExpressionsEqual(bx.Left, @by.Left, rootX, rootY) &&
                   ExpressionsEqual(bx.Right, @by.Right, rootX, rootY);
        }
        if (x is UnaryExpression)
        {
            var ux = (UnaryExpression)x;
            var uy = (UnaryExpression)y;
            return ux.Method == uy.Method && ExpressionsEqual(ux.Operand, uy.Operand, rootX, rootY);
        }
        if (x is ParameterExpression)
        {
            var px = (ParameterExpression)x;
            var py = (ParameterExpression)y;
            return rootX.Parameters.IndexOf(px) == rootY.Parameters.IndexOf(py);
        }
        if (x is MethodCallExpression)
        {
            var cx = (MethodCallExpression)x;
            var cy = (MethodCallExpression)y;
            return cx.Method == cy.Method
                   && ExpressionsEqual(cx.Object, cy.Object, rootX, rootY)
                   && CollectionsEqual(cx.Arguments, cy.Arguments, rootX, rootY);
        }
        if (x is MemberInitExpression)
        {
            var mix = (MemberInitExpression)x;
            var miy = (MemberInitExpression)y;
            return ExpressionsEqual(mix.NewExpression, miy.NewExpression, rootX, rootY)
                   && MemberInitsEqual(mix.Bindings, miy.Bindings, rootX, rootY);
        }
        if (x is NewArrayExpression)
        {
            var nx = (NewArrayExpression)x;
            var ny = (NewArrayExpression)y;
            return CollectionsEqual(nx.Expressions, ny.Expressions, rootX, rootY);
        }
        if (x is NewExpression)
        {
            var nx = (NewExpression)x;
            var ny = (NewExpression)y;
            return
                Equals(nx.Constructor, ny.Constructor)
                && CollectionsEqual(nx.Arguments, ny.Arguments, rootX, rootY)
                && (nx.Members == null && ny.Members == null
                    || nx.Members != null && ny.Members != null && CollectionsEqual(nx.Members, ny.Members));
        }
        if (x is ConditionalExpression)
        {
            var cx = (ConditionalExpression)x;
            var cy = (ConditionalExpression)y;
            return
                ExpressionsEqual(cx.Test, cy.Test, rootX, rootY)
                && ExpressionsEqual(cx.IfFalse, cy.IfFalse, rootX, rootY)
                && ExpressionsEqual(cx.IfTrue, cy.IfTrue, rootX, rootY);
        }

        throw new NotImplementedException(x.ToString());
    }

    private static Boolean IsAnonymousType(Type type)
    {
        Boolean hasCompilerGeneratedAttribute = type.GetCustomAttributes(typeof(CompilerGeneratedAttribute), false).Any();
        Boolean nameContainsAnonymousType = type.FullName.Contains("AnonymousType");
        Boolean isAnonymousType = hasCompilerGeneratedAttribute && nameContainsAnonymousType;

        return isAnonymousType;
    }

    private static bool MemberInitsEqual(ICollection<MemberBinding> bx, ICollection<MemberBinding> by, LambdaExpression rootX, LambdaExpression rootY)
    {
        if (bx.Count != by.Count)
        {
            return false;
        }

        if (bx.Concat(by).Any(b => b.BindingType != MemberBindingType.Assignment))
            throw new NotImplementedException("Only MemberBindingType.Assignment is supported");

        return
            bx.Cast<MemberAssignment>().OrderBy(b => b.Member.Name).Select((b, i) => new { Expr = b.Expression, b.Member, Index = i })
            .Join(
                  by.Cast<MemberAssignment>().OrderBy(b => b.Member.Name).Select((b, i) => new { Expr = b.Expression, b.Member, Index = i }),
                  o => o.Index, o => o.Index, (xe, ye) => new { XExpr = xe.Expr, XMember = xe.Member, YExpr = ye.Expr, YMember = ye.Member })
                   .All(o => Equals(o.XMember, o.YMember) && ExpressionsEqual(o.XExpr, o.YExpr, rootX, rootY));
    }

    private static bool ValuesEqual(object x, object y)
    {
        if (ReferenceEquals(x, y))
            return true;
        if (x is ICollection && y is ICollection)
            return CollectionsEqual((ICollection)x, (ICollection)y);

        return Equals(x, y);
    }

    private static ConstantValue TryCalculateConstant(Expression e)
    {
        if (e is ConstantExpression)
            return new ConstantValue(true, ((ConstantExpression)e).Value);
        if (e is MemberExpression)
        {
            var me = (MemberExpression)e;
            var parentValue = TryCalculateConstant(me.Expression);
            if (parentValue.IsDefined)
            {
                var result =
                    me.Member is FieldInfo
                        ? ((FieldInfo)me.Member).GetValue(parentValue.Value)
                        : ((PropertyInfo)me.Member).GetValue(parentValue.Value);
                return new ConstantValue(true, result);
            }
        }
        if (e is NewArrayExpression)
        {
            var ae = ((NewArrayExpression)e);
            var result = ae.Expressions.Select(TryCalculateConstant);
            if (result.All(i => i.IsDefined))
                return new ConstantValue(true, result.Select(i => i.Value).ToArray());
        }
        if (e is ConditionalExpression)
        {
            var ce = (ConditionalExpression)e;
            var evaluatedTest = TryCalculateConstant(ce.Test);
            if (evaluatedTest.IsDefined)
            {
                return TryCalculateConstant(Equals(evaluatedTest.Value, true) ? ce.IfTrue : ce.IfFalse);
            }
        }

        return default(ConstantValue);
    }

    private static bool CollectionsEqual(IEnumerable<Expression> x, IEnumerable<Expression> y, LambdaExpression rootX, LambdaExpression rootY)
    {
        return x.Count() == y.Count()
               && x.Select((e, i) => new { Expr = e, Index = i })
                   .Join(y.Select((e, i) => new { Expr = e, Index = i }),
                         o => o.Index, o => o.Index, (xe, ye) => new { X = xe.Expr, Y = ye.Expr })
                   .All(o => ExpressionsEqual(o.X, o.Y, rootX, rootY));
    }

    private static bool CollectionsEqual(ICollection x, ICollection y)
    {
        return x.Count == y.Count
               && x.Cast<object>().Select((e, i) => new { Expr = e, Index = i })
                   .Join(y.Cast<object>().Select((e, i) => new { Expr = e, Index = i }),
                         o => o.Index, o => o.Index, (xe, ye) => new { X = xe.Expr, Y = ye.Expr })
                   .All(o => Equals(o.X, o.Y));
    }

    private struct ConstantValue
    {
        public ConstantValue(bool isDefined, object value)
            : this()
        {
            IsDefined = isDefined;
            Value = value;
        }

        public bool IsDefined { get; private set; }

        public object Value { get; private set; }
    }
}

Note that it does not compare full AST. Instead, it collapses constant expressions and compares their values rather than their AST. It is useful for mocks validation when the lambda has a reference to local variable. In his case the variable is compared by its value.

请注意，它不会比较完整的 AST。相反，它会折叠常量表达式并比较它们的值而不是它们的 AST。当 lambda 引用局部变量时，它对模拟验证很有用。在他的情况下，变量是按其值进行比较的。

Unit tests:

单元测试：

[TestClass]
public class Tests
{
    [TestMethod]
    public void BasicConst()
    {
        var f1 = GetBasicExpr1();
        var f2 = GetBasicExpr2();
        Assert.IsTrue(LambdaCompare.Eq(f1, f2));
    }

    [TestMethod]
    public void PropAndMethodCall()
    {
        var f1 = GetPropAndMethodExpr1();
        var f2 = GetPropAndMethodExpr2();
        Assert.IsTrue(LambdaCompare.Eq(f1, f2));
    }

    [TestMethod]
    public void MemberInitWithConditional()
    {
        var f1 = GetMemberInitExpr1();
        var f2 = GetMemberInitExpr2();
        Assert.IsTrue(LambdaCompare.Eq(f1, f2));
    }

    [TestMethod]
    public void AnonymousType()
    {
        var f1 = GetAnonymousExpr1();
        var f2 = GetAnonymousExpr2();
        Assert.Inconclusive("Anonymous Types are not supported");
    }

    private static Expression<Func<int, string, string>> GetBasicExpr2()
    {
        var const2 = "some const value";
        var const3 = "{0}{1}{2}{3}";
        return (i, s) =>
            string.Format(const3, (i + 25).ToString(CultureInfo.InvariantCulture), i + s, const2.ToUpper(), 25);
    }

    private static Expression<Func<int, string, string>> GetBasicExpr1()
    {
        var const1 = 25;
        return (first, second) =>
            string.Format("{0}{1}{2}{3}", (first + const1).ToString(CultureInfo.InvariantCulture), first + second,
                "some const value".ToUpper(), const1);
    }

    private static Expression<Func<Uri, bool>> GetPropAndMethodExpr2()
    {
        return u => Uri.IsWellFormedUriString(u.ToString(), UriKind.Absolute);
    }

    private static Expression<Func<Uri, bool>> GetPropAndMethodExpr1()
    {
        return arg1 => Uri.IsWellFormedUriString(arg1.ToString(), UriKind.Absolute);
    }

    private static Expression<Func<Uri, UriBuilder>> GetMemberInitExpr2()
    {
        var isSecure = true;
        return u => new UriBuilder(u) { Host = string.IsNullOrEmpty(u.Host) ? "abc" : "def" , Port = isSecure ? 443 : 80 };
    }

    private static Expression<Func<Uri, UriBuilder>> GetMemberInitExpr1()
    {
        var port = 443;
        return x => new UriBuilder(x) { Port = port, Host = string.IsNullOrEmpty(x.Host) ? "abc" : "def" };
    }

    private static Expression<Func<Uri, object>> GetAnonymousExpr2()
    {
        return u => new { u.Host , Port = 443, Addr = u.AbsolutePath };
    }

    private static Expression<Func<Uri, object>> GetAnonymousExpr1()
    {
        return x => new { Port = 443, x.Host, Addr = x.AbsolutePath };
    }
}

回答by jnm2

A canonical solution would be great. In the meantime, I created an IEqualityComparer<Expression>version. This is rather a verbose implementation, so I created a gist for it.

规范的解决方案会很棒。与此同时，我创建了一个IEqualityComparer<Expression>版本。这是一个相当冗长的实现，所以我为它创建了一个要点。

It is intended to be a comprehensive abstract syntax tree comparer. To that end, it compares every expression type including expressions that aren't yet supported by C# like Tryand Switchand Block. The only types it does not compare are Goto, Label, Loopand DebugInfodue to my limited knowledge of them.

它旨在成为一个全面的抽象语法树比较器。为此，它比较了每种表达式类型，包括 C# 尚不支持的表达式，如TryandSwitch和Block。它不比较的唯一类型是Goto, Label,Loop并且DebugInfo由于我对它们的了解有限。

You can specify whether and how names of parameters and lambdas should be compared, as well as how to handle ConstantExpression.

您可以指定是否以及如何比较参数和 lambda 的名称，以及如何处理ConstantExpression.

It tracks parameters positionally by context. Lambdas inside lambdas and catch block variable parameters are supported.

它根据上下文在位置上跟踪参数。支持 lambdas 内的 Lambdas 和 catch 块变量参数。

回答by Ryan.Bartsch

I know this is an old question, but I rolled my own expression tree equality comparer - https://github.com/yesmarket/yesmarket.Linq.Expressions

我知道这是一个老问题，但我推出了自己的表达式树相等比较器 - https://github.com/yesmarket/yesmarket.Linq.Expressions

The implementation makes heavy use of the ExpressionVisitor class to determine whether two expression trees are equal. As the nodes in the expression tree are traversed, individual nodes are compared for equality.

该实现大量使用 ExpressionVisitor 类来确定两个表达式树是否相等。当遍历表达式树中的节点时，会比较各个节点是否相等。

回答by Sebastian Xawery Wi?niowiecki

I think most efficiency out of Lambdasyou getting when you will use lambda-efficient collection- what I mean is column-based collectionthat can be enumerated by only one or more selected columns achieving this by implementing IEnumerableon each column separately - let's call it first step;)

我认为Lambdas当您使用lambda 高效的集合时，您会获得最大的效率- 我的意思是基于列的集合，它只能被一个或多个选定的列枚举，通过IEnumerable分别在每列上实现来实现这一点- 让我们称之为 第一步;)

That is only my idea that I want to do some day. I have no clues at the moment but I think many will agree with me that enumerating to check value through single variables list in compare to checking some property in list of objects is like proving itself.

这只是我的想法，我想有一天做。我目前没有任何线索，但我认为很多人会同意我的观点，与检查对象列表中的某些属性相比，通过单个变量列表枚举来检查值就像证明自己。

Next second stepto get more from functional programming: use as a collections representing columns use sorted-list, hash-tableor any other search-efficient collection.

接下来第二步，从函数式编程获得更多的：作为代表列的集合使用分类列表，哈希表或其他任何搜索有效的收集。

class LambdaReadyColumn<int> : HashTable<int> 

And another third stepconnect items between columns with some pointers so instead of keeping under-hood columns in:

另一个第三步使用一些指针连接列之间的项目，而不是将引擎盖下的列保留在：

class LambdaReadyColumn<int> : IEnumabrable<int> 

keep data in something closer to:

将数据保存在更接近的地方：

class LambdaReadyColumn<LambdaReadyColumnItem<T, int>> : IEnumabrable<int> 
//with example constructor like: 
public LambdaReadyColumn<LambdaReadyColumnItem<T, int>>(Hash, LambdaReadyColumnItem, LambdaReadyColumnItem, T, int); 

where:

在哪里：

• CollectionItem - references to right and left column items of same T item
• Hash - to make search faster
• int - type representing column
• T - fourth stepwhole LambdaReadyCollection in column collection easily understanding simply to make Select(T)at the returning item descriptor faster but also avoiding traversing few references left/right for items with many properties.

• CollectionItem - 对同一 T 项的左右列项的引用
• 哈希 - 使搜索更快
• int - 表示列的类型
• T -列集合中的整个 LambdaReadyCollection 的第四步很容易理解，只是为了使Select(T)返回的项目描述符更快，但也避免为具有许多属性的项目向左/向右遍历很少的引用。

Finally with all the step we have collection with double data: row-based and collection based additionally lot of reference data. Of course row-based HashTable can keep data and column-based only references but than building every collection to return from the statement would use lot of referencing.

最后，在所有步骤中，我们收集了双重数据：基于行和基于收集的额外大量参考数据。当然，基于行的 HashTable 可以只保留数据和基于列的引用，但比构建每个集合以从语句返回将使用大量引用。

To achieve it you need to use reflections, dynamic types or other advanced technique depending on the language.

要实现它，您需要根据语言使用反射、动态类型或其他高级技术。