c# - How do I create an expression tree calling IEnumerable<TSource>.Any(...)?

Question

I am trying to create an expression tree that represents the following:

myObject.childObjectCollection.Any(i => i.Name == "name");

Shortened for clarity, I have the following:

//'myObject.childObjectCollection' is represented here by 'propertyExp'
//'i => i.Name == "name"' is represented here by 'predicateExp'
//but I am struggling with the Any() method reference - if I make the parent method
//non-generic Expression.Call() fails but, as per below, if i use <T> the 
//MethodInfo object is always null - I can't get a reference to it

private static MethodCallExpression GetAnyExpression<T>(MemberExpression propertyExp, Expression predicateExp)
{
    MethodInfo method = typeof(Enumerable).GetMethod("Any", new[]{ typeof(Func<IEnumerable<T>, Boolean>)});
    return Expression.Call(propertyExp, method, predicateExp);
}

What am I doing wrong? Anyone have any suggestions?

Answer 1

There are several things wrong with how you're going about it.

1. You're mixing abstraction levels. The T parameter to GetAnyExpression<T> could be different to the type parameter used to instantiate propertyExp.Type. The T type parameter is one step closer in the abstraction stack to compile time - unless you're calling GetAnyExpression<T> via reflection, it will be determined at compile time - but the type embedded in the expression passed as propertyExp is determined at runtime. Your passing of the predicate as an Expression is also an abstraction mixup - which is the next point.

2. The predicate you are passing to GetAnyExpression should be a delegate value, not an Expression of any kind, since you're trying to call Enumerable.Any<T>. If you were trying to call an expression-tree version of Any, then you ought to pass a LambdaExpression instead, which you would be quoting, and is one of the rare cases where you might be justified in passing a more specific type than Expression, which leads me to my next point.

3. In general, you should pass around Expression values. When working with expression trees in general - and this applies across all kinds of compilers, not just LINQ and its friends - you should do so in a way that's agnostic as to the immediate composition of the node tree you're working with. You are presuming that you're calling Any on a MemberExpression, but you don't actually need to know that you're dealing with a MemberExpression, just an Expression of type some instantiation of IEnumerable<>. This is a common mistake for people not familiar with the basics of compiler ASTs. Frans Bouma repeatedly made the same mistake when he first started working with expression trees - thinking in special cases. Think generally. You'll save yourself a lot of hassle in the medium and longer term.

4. And here comes the meat of your problem (though the second and probably first issues would have bit you if you had gotten past it) - you need to find the appropriate generic overload of the Any method, and then instantiate it with the correct type. Reflection doesn't provide you with an easy out here; you need to iterate through and find an appropriate version.

So, breaking it down: you need to find a generic method (Any). Here's a utility function that does that:

static MethodBase GetGenericMethod(Type type, string name, Type[] typeArgs, 
    Type[] argTypes, BindingFlags flags)
{
    int typeArity = typeArgs.Length;
    var methods = type.GetMethods()
        .Where(m => m.Name == name)
        .Where(m => m.GetGenericArguments().Length == typeArity)
        .Select(m => m.MakeGenericMethod(typeArgs));

    return Type.DefaultBinder.SelectMethod(flags, methods.ToArray(), argTypes, null);
}

However, it requires the type arguments and the correct argument types. Getting that from your propertyExp Expression isn't entirely trivial, because the Expression may be of a List<T> type, or some other type, but we need to find the IEnumerable<T> instantiation and get its type argument. I've encapsulated that into a couple of functions:

static bool IsIEnumerable(Type type)
{
    return type.IsGenericType
        && type.GetGenericTypeDefinition() == typeof(IEnumerable<>);
}

static Type GetIEnumerableImpl(Type type)
{
    // Get IEnumerable implementation. Either type is IEnumerable<T> for some T, 
    // or it implements IEnumerable<T> for some T. We need to find the interface.
    if (IsIEnumerable(type))
        return type;
    Type[] t = type.FindInterfaces((m, o) => IsIEnumerable(m), null);
    Debug.Assert(t.Length == 1);
    return t[0];
}

So, given any Type, we can now pull the IEnumerable<T> instantiation out of it - and assert if there isn't (exactly) one.

With that work out of the way, solving the real problem isn't too difficult. I've renamed your method to CallAny, and changed the parameter types as suggested:

static Expression CallAny(Expression collection, Delegate predicate)
{
    Type cType = GetIEnumerableImpl(collection.Type);
    collection = Expression.Convert(collection, cType);

    Type elemType = cType.GetGenericArguments()[0];
    Type predType = typeof(Func<,>).MakeGenericType(elemType, typeof(bool));

    // Enumerable.Any<T>(IEnumerable<T>, Func<T,bool>)
    MethodInfo anyMethod = (MethodInfo)
        GetGenericMethod(typeof(Enumerable), "Any", new[] { elemType }, 
            new[] { cType, predType }, BindingFlags.Static);

    return Expression.Call(
        anyMethod,
            collection,
            Expression.Constant(predicate));
}

Here's a Main() routine which uses all the above code and verifies that it works for a trivial case:

static void Main()
{
    // sample
    List<string> strings = new List<string> { "foo", "bar", "baz" };

    // Trivial predicate: x => x.StartsWith("b")
    ParameterExpression p = Expression.Parameter(typeof(string), "item");
    Delegate predicate = Expression.Lambda(
        Expression.Call(
            p,
            typeof(string).GetMethod("StartsWith", new[] { typeof(string) }),
            Expression.Constant("b")),
        p).Compile();

    Expression anyCall = CallAny(
        Expression.Constant(strings),
        predicate);

    // now test it.
    Func<bool> a = (Func<bool>) Expression.Lambda(anyCall).Compile();
    Console.WriteLine("Found? {0}", a());
    Console.ReadLine();
}