Application Expressions

Good day.

Looking through recently someone else's code, I came across a rather interesting task about IQueryable and Expession trees. I hope the decision will be useful to someone.

The task is to reuse some Expression inside another Expression, for example, we have some f :
')

Expression<Func<int, int, int>> f = (a, b) => a + b; 

And we would like to use this f inside another expression, like this:

 Expression<Func<int, int, int, int>> g = (a, b, c) => f(a+b,b)*c; 

Moreover, it is necessary that the resulting expression be “pure”, i.e. suitable for use inside IQueryable (without compiled functions, etc.)



If you try to compile these two lines, it turns out that the definition of g is wrong: 'f' is a 'variable' but it is used like a 'method' , which, in general, is understandable, f is the root of the expression tree, and as not a function or functor. You can try to write like this:

 Expression<Func<int, int, int, int>> g = (a, b, c) => f.Compile()(a+b,b)*c; 

But then our expression will look like this:

(a, b, c) => (Invoke(value(ExpressionReducer.Program+<>c__DisplayClass0).f.Compile(), (a + b), b) * c)

Naturally, our IQueryable will not understand this.

The simplest and most obvious idea is to simply substitute f for its very body - roughly speaking, to make an “application” of the term f to g (Honestly, I’m not at all strong at lambda refining, but in my opinion it will be the application).

For such an “application,” we need to rewrite the expression tree for g a little, specifically, replace the Invoke (Compile ()) call with the body of the function f, and in the body of f replace its parameters with the values ​​of the Invoke arguments, that is, from:

 (a, b, c) => f.Compile()(a+b,b)*c 

receive

 (a, b, c) => ((a+b)+b)*c 

First, let's get rid of the cumbersome Invoke (Compile) and replace it with this extension method:

 public static T Apply<T,T1,T2>(this Expression<Func<T1,T2,T>> expression, T1 t1, T2 t2) { return expression.Compile()(t1, t2); } //... Expression<Func<int, int, int, int>> g = (a, b, c) => f.Apply(a + b, b) * c; 

In fact, the body of the Apply function is not important - it will never be called when converting, but it is useful to have a valid body if someone uses g without simplification.

Now carefully look at the resulting tree:


Actually, here are the steps to be taken:

1. Find a call to the Apply method.
2. Get the lambda function f from the first argument of the Apply function.
3. Replace the arguments in the body of the lambda with the remaining parameters of the Apply function.
4. Replace the .Call tree with a body f.

The first point is quite easy to do - use the ExpressionVisitor class from the System.Linq.Expressions namespace. This is a very convenient class that allows you not only to visit all the nodes of the expression tree, but also to rewrite a part of it (for more details, see http://msdn.microsoft.com/en-us/library/bb546136%28v=vs.90%29.aspx ) We assume that the Apply method is in the ExpressionReductor class:

 private class InvokerVisitor : ExpressionVisitor { protected override Expression VisitMethodCall(MethodCallExpression node) { if (node.Method.DeclaringType == typeof (ExpressionReductor) && node.Method.Name == "Apply") { //     } return base.VisitMethodCall(node); } } 

The second paragraph is somewhat more complicated. As can be seen from the tree, f became the field of the autogenerated class ExpressionReducer.Program + <> c__DisplayClass0 - this is how C # comes with all functors or expressions declared in the body of methods or which come as method parameters. Among other possible options, this is a field or a property of a named class or the result of a function call.
For simplicity, we will consider only the first case (the rest can be implemented similarly): f is a field of some class.

 class FieldLambdaFinder : ExpressionVisitor { protected override Expression VisitMember(MemberExpression node) { var constantExpression = (ConstantExpression) node.Expression; var info = (FieldInfo) node.Member; var fieldValue = (Expression)info.GetValue(constantExpression.Value); return fieldValue; } public Expression Find(Expression expression) { return Visit(expression); } } 

The third point is quite simple - we compose a Dictionary (parameter f -> Apply parameter) and replace all ParameterExpression in the body of f:

 internal class Replacer : ExpressionVisitor { private Dictionary<ParameterExpression, Expression> _replacements; public Replacer(IEnumerable<ParameterExpression> what, IEnumerable<Expression> with) { _replacements = what.Zip(with, (param, expr) => new { param, expr }).ToDictionary(x => x.param, x => x.expr); } public Expression Replace(Expression body) { return Visit(body); } protected override Expression VisitParameter(ParameterExpression node) { Expression replacement; return _replacements.TryGetValue(node, out replacement) ? replacement : base.VisitParameter(node); } } 

The last item will show everything in the collection:

 private class InvokerVisitor : ExpressionVisitor { protected override Expression VisitMethodCall(MethodCallExpression node) { if (node.Method.DeclaringType == typeof (ExpressionReductor) && node.Method.Name == "Apply") { var lambda = GetLambda(node.Arguments[0]); return Replace(lambda, node.Arguments.Skip(1)); } return base.VisitMethodCall(node); } private Expression Replace(LambdaExpression lambda, IEnumerable<Expression> arguments) { var replacer = new Replacer(lambda.Parameters, arguments); return replacer.Replace(lambda.Body); } private LambdaExpression GetLambda(Expression expression) { var finder = new FieldLambdaFinder(); return (LambdaExpression) finder.Find(expression); } } 

Simplify method itself:

 public static Expression<T> Simplify<T>(this Expression<T> expression) { var invoker = new InvokerVisitor(); return (Expression<T>) invoker.Visit(expression); } 

All at once can be found here .

As a result, we got what we wanted:

 Expression<Func<int, int, int>> f = (a, b) => a + b; Expression<Func<int, int, int, int>> g = (a, b, c) => f.Apply(a + b, b)*c; g = g.Simplify(); 

Remaining problems:

1. How to get f in other cases.
2. If the Apply parameters are calls to other functions that have side effects, the substitution is incorrect. In our case, this can not be, since we operate with IQueryable, but it is worth having it in mind.
3. The Simplify function does not minimize the calculation: f.Apply (5, 5) will be simplified to (5 + 5), and not to (10).
4. The Simplify function is not recursive, that is, in such examples - f.Apply (a, f.Apply (b, c)) - it will have to be called several times.