PredicateBuilder revisited 20 Jul 2010

If you're querying a LINQ provider, and if you're dynamically creating the query, you probably stumbled upon the PredicateBuilder class. It gives you a simple API to get a predicate in the form of an Expression Tree that a LINQ provider expects. You simply And (or Or) them together. For instance:

Expression> is_underage = u => u.Age < 18;
Expression> name_starts_with_a = u => u.Name [0] == 'A'

Expression> a_is_underage = is_underage.And (name_starts_with_a);

Easy and effective. But let's have a look at their And implementation:

public static Expression> And (this Expression> expr1, Expression> expr2)
{
    var invokedExpr = Expression.Invoke (expr2, expr1.Parameters.Cast ());
    return Expression.Lambda>
        (Expression.AndAlso (expr1.Body, invokedExpr), expr1.Parameters);
}

It creates a new expression tree (they are immutable), but the right hand side of the AndAlso node is an invocation of the second expression. If it works great if you compile the expression into an delegate, most LINQ providers won't be able to optimize this form, as they'll expect a more simple form, without nested lambdas. I added to Mono.Linq.Expressions my own version of a PredicateBuilder which doesn't have this issue. Let's examine the implementation:

public static class PredicateBuilder {

	public static Expression> True ()
	{
		return Expression.Lambda> (Expression.Constant (true), Expression.Parameter (typeof (T)));
	}

	public static Expression> False ()
	{
		return Expression.Lambda> (Expression.Constant (false), Expression.Parameter (typeof (T)));
	}

	public static Expression> OrElse (this Expression> self, Expression> expression)
	{
		return Combine (self, expression, Expression.OrElse);
	}

	public static Expression> AndAlso (this Expression> self, Expression> expression)
	{
		return Combine (self, expression, Expression.AndAlso);
	}

	static Expression> Combine (Expression> self, Expression> expression, Func selector)
	{
		CheckSelfAndExpression (self, expression);

		var parameter = CreateParameterFrom (self);

		return Expression.Lambda> (
			selector (
				RewriteLambdaBody (self, parameter),
				RewriteLambdaBody (expression, parameter)),
			parameter);
	}

	static Expression RewriteLambdaBody (LambdaExpression expression, ParameterExpression parameter)
	{
		return new ParameterRewriter (expression.Parameters [0], parameter).Visit (expression.Body);
	}

	class ParameterRewriter : ExpressionVisitor {

		readonly ParameterExpression candidate;
		readonly ParameterExpression replacement;

		public ParameterRewriter (ParameterExpression candidate, ParameterExpression replacement)
		{
			this.candidate = candidate;
			this.replacement = replacement;
		}

		protected override Expression VisitParameter (ParameterExpression expression)
		{
			return ReferenceEquals (expression, candidate) ? replacement : expression;
		}
	}

	static ParameterExpression CreateParameterFrom (Expression> left)
	{
		var template = left.Parameters [0];

		return Expression.Parameter (template.Type, template.Name);
	}

	static void CheckSelfAndExpression (Expression> self, Expression> expression)
	{
		if (self == null)
			throw new ArgumentNullException ("self");
		if (expression == null)
			throw new ArgumentNullException ("expression");
	}
}

Instead of nesting lambdas, it simply rewrites a lambda and inlines the two previous expressions bodies in it. This way, you can compose predicates and make sure they'll be usable by any LINQ provider without having to deal with it explicitely. I also named the method AndAlso and OrElse as it's the terminology used in the Expression Tree API for the logical And (&&) and Or (||). What's next for Mono.Linq.Expressions? Probably an IEqualityComparer<Expression> implementation. Any other useful feature you can think of?