How to use the DLR to build Expression Trees
Intermediate
With the introduction of LINQ Expressions, generating code from a .NET application became much less cumbersome and error-prone. Instead of using Reflection.Emit to generate individual CLR instructions, an application now builds a tree of expressions much like the syntax tree used by a typical compiler, and then calls a simple Compile method on the final tree to generate a dynamic function or to populate a MethodBuilder. Expression trees form a Turing Complete language, meaning that an expression tree can be used to generate the equivalent of any C# function.
While code that builds expression trees is more readable than code that uses Reflection.Emit directly, it is still a bit noisy when used to generate significant bodies of code. Building an expression tree that uses methods, fields, or properties requires those members to be referenced with MemberInfo objects or with strings. Literal values used in an expression tree must be wrapped in ConstantExpression instances. The Expression building API does not include any operator overloading, so building up arithmetic expressions requires a function call to build each step.
// Generates an expression for: param1.Prop1.Length
Expression result = Expression.PropertyOrField(
Expression.PropertyOrField(expParam1, "Prop1"), "Length");.NET introduces the Dynamic Language Runtime (DLR). It allows programmers to define and use "dynamic types"; that is, types that can have members added and removed at runtime. When using such a type, the validity and definition of members will be evaluated at runtime. Naturally, this imposes a substantial performance penalty compared to using members of a regular type, but it does allow the decision of which members a given type supports to be postponed until runtime.There are three basic flavors of dynamic objects, defined by three types that live in the System.Dynamic namespace:
ExpandoObject and DynamicObject are both implemented behind-the-scenes using IDynamicMetaObjectProvider, which is the lowest level at which a programmer can implement a dynamic object.
For our expression tree building library, we will define implementations of IDynamicMetaObjectProvider. As noted above, an IDynamicMetaObjectProvider must produce instances of DynamicMetaObject subclasses, and those DynamicMetaObject subclass instances must then respond to DLR requests in order to allow the overall dynamic type to be used. The IDynamicMetaObjectProvider implementation itself is relatively simple:
public CGValue : IDynamicMetaObjectProvider
{
public Expression Expr {get; private set;}
public CGValue(Expression expr)
{
Expr = expr;
}
// Implicit wrapping and unwrapping
public static implicit operator Expression(CGValue v)
{
return v.Expr;
}
public static implicit operator CGValue(Expression x)
{
return new CGValue(x);
}
// Implementation of IDynamicMetaObjectProvider.GetMetaObject
public DynamicMetaObject GetMetaObject(Expression parameter)
{
// For "parameter", the DLR passes a LINQ expression representing
// this CGValue instance.
return new CGValueMetaObject(parameter, BindingRestrictions.Empty, this);
}
// ...Here, CGValue is a wrapper for a System.Linq.Expression instance that implements IDynamicMetaObjectProvider. The DLR doesn't provide a way to directly turn a regular class into a dynamic class (although it will happily let you use regular classes as if they were dynamic, while rejecting any attempts to add members to them), so we have to define our own class to wrap it.
The DynamicMetaObject subclass, however, is much more involved. Each of the overridable member-getting operations must return not a member, but another DynamicMetaObject containing an Expression tree representing the member's value (which in our case is itself an Expression tree). In our case, that means we will be building expression trees that represent expression tree building code. In other words, in our DynamicMetaObject method overrides, we are writing code that generates code that generates code.For instance, our override of BindGetMember must build an expression tree that represents a direct or indirect call to Expression.PropertyOrField. Here we'll add a method to CGValue that simply calls Expression.PropertyOrField with the wrapped Expression instance:
public CGValue Get(string name)
{
return Expression.PropertyOrField(this.Expr, name);
}and have the tree built by BindGetMember represent a call to CGValue.Get:
public override DynamicMetaObject BindGetMember(GetMemberBinder binder)
{
// DynamicMetaObject.Expression is a LINQ expression representing the
// dynamic object instance (the CGValue instance). But its declared type
// is Object; we need to cast it to CGValue before we can call anything
// on it.
Expression instanceExprExpr = Expression.Convert(Expression, LimitType);
// Build an expression representing a call to CGValue.Get
Expression memberExprExpr = Expression.Call(instanceExprExpr, "Get", null,
Expression.Constant(binder.Name));
// Package it up in a new DynamicMetaObject
// NOTE: The binding restriction parameter pertains to the dynamic object whose
// member is being accessed, not the dynamic object resulting from the member
// access. So as a general rule, just pass through the binding restrictions
// for this DynamicMetaObject instance, which matches the dynamic object whose
// member is being accessed.
return new DynamicMetaObject(memberExprExpr, BindingRestrictions.GetTypeRestriction(Expression, LimitType));
}By doing it that way, we don't have to include code to build expression tree nodes to extract the Expression instance from the CGValue instance.With this in place, we can replace this application code to build a member access expression:
// Assume TestInstance has a String
property named Prop1
Expression expTestInstance = ...;
// result becomes an Expression representing TestInstance.Prop1
Expression result = Expression.PropertyOrField(expTestInstance, "Prop1");with this code that uses our new CGValue wrapper to do the same thing:
// Assume TestInstance has a String property named Prop1
// expTestInstance is a CGValue
dynamic expTestInstance = ...;
// result becomes a CGValue wrapping an Expression representing TestInstance.Prop1
dynamic result = expTestInstance.Prop1;At runtime, when expTestInstance.Prop1 is evaluated:
This can be chained any number of times:
// Now result becomes a
CGValue wrapping an expression representing
// TestInstance.Prop1.Length
dynamic result = expTestInstance.Prop1.Length;Here, expTestInstance.Prop1 is evaluated as above, and the result has the member "Length" accessed. The DLR simply repeats the process, calling IDynamicMetaObjectProvider.GetMetaObject on expTestInstance.Prop1, calling BindGetMember on the returned DynamicMetaObject, executing the expression tree contained in that returned DynamicMetaObject, and using the result as the runtime-evaluated value of the Length property, which in this case is a CGValue instance wrapping an Expression representing the member Length of System.String.
A set member operation uses BindSetMember. When we return a DynamicMetaObject, the expression tree it contains needs to evaluate to a CGValue wrapping the result of calling Expression.Assign. That way, we can take the assignment expression and include it in a BlockExpression so we can execute it and code that depends on it:
Expression[] statements = new Expression[]
{
// The whole set expression here needs to evaluate to an AssignExpression so
// that the assignment will run as part of the block.
expTestInstance.Prop1 = expNewStringValue,
// expressions to use the updated test instance
// ...
};
Expression block = Expression.Block(statements);This is the reason we needed to implement an IDynamicMetaObjectProvider. When using either of the other two methods of defining dynamic objects, you cannot make the member set operation evaluate to anything other than the runtime value being assigned to that member. In this case, we need for the member set expression to not evaluate to the expression on the right, but instead evaluate to an assignment expression derived from it:
public CGValue Set(String name, Expression xval)
{
Expression member = Get(name);
return Expression.Assign(member, xval);
}public override DynamicMetaObject BindSetMember(SetMemberBinder binder,
DynamicMetaObject value)
{
// Expression representing the CGValue instance whose member is being set
Expression instanceExprExpr = Expression.Convert(Expression, LimitType);
// Expression representing a call to CGValue.Set with the member name
// and a CGValue wrapping an Expression representing the value to assign
// to the member. CGValue.Set will return an expression representing
// the assignment.
Expression assignExprExpr = Expression.Call(instanceExprExpr, "Set", null,
Expression.Constant(binder.Name),value.Expression);
// Package up the result
return new DynamicMetaObject(assignExprExpr, BindingRestrictions.GetTypeRestriction(Expression, LimitType));
}Our CGValue class can be used to build expression trees, but it doesn't help you define lambda parameters to be used in it. We still need to call Expression.Parameter for each one to get parameters to be fed to the dynamic expression builders we defined above and to Expression.Lambda to get a lambda expression that can be turned into a delegate and executed.To simplify this, let's define a CGFunc class. It will wrap a set of parameters, a set of variables, and a set of LINQ expressions, all of which will be used to construct a lambda expression. Since we're defining CGFunc as another implementation of IDynamicMetaObjectProvider, we get to choose the set of members it exposes at runtime. In this case, we'll have one named member for each lambda parameter and each internal variable we define. That way, client code can go like this:
Type arg0Type = ...;
Type arg1Type = ...;
// Create a function that returns the Length property of the Prop1 property of
// the argument. Note that the only requirement for this part to work is that
// arg0Type have a Prop1 property whose declared type has a Length property,
// and arg0Type also have a Prop2 property assignable from type arg1Type.
// So long as those requirements are met, arg0Type does not have to be, or
// derive from, any particular named type. Since 'lambda' represents ordinary
// early-bound .NET code without any DLR overheads, we get this type flexibility
// without adding any runtime overhead to 'lambda'.
dynamic fn = new CGFunc(arg0Type, "arg0", arg1Type, "arg1");
fn.Eval(
fn.arg0.Prop2 = arg1,
// etc.
// ...
// Last expression in the body of a lambda becomes the lambda's return value.
fn.arg0.Prop1.Length); LambdaExpression lambda = fn.CreateLambda();
// Now we can create a delegate from 'lambda' or populate a MethodBuilder with it.
// ...To make that happen, we'll make CGFunc expose public methods to create expressions that get and set arguments and variables, a method to add Expressions to an internal list, and of course an implementation of IDynamicMetaObjectProvider that returns a CGFuncMetaObject:
public class CGFunc : IDynamicMetaObjectProvider
{
// Mapping from name to the corresponding ParameterExpression
public IDictionary<string, parameterexpression> ParameterMap { get; private set; }
// Ordered list of ParameterExpression representing the arguments
public IList<parameterexpression> Parameters { get; private set; }
// Ordered list of ParameterExpressions representing local variables
public IList<parameterexpression> Variables { get; private set; }
// The expressions making up the body of the resulting function
List<expression> _members = new List<expression>();
// This is only run only at construction time
private void Init()
{
ParameterMap = new Dictionary<string, parameterexpression>();
Parameters = new List<parameterexpression>();
Variables = new List<parameterexpression>();
}
// Constructors for various numbers of parameters
public CGFunc()
{
Init();
}
public CGFunc(Type pt0, String pn0)
{
Init();
AddParam(pt0, pn0);
}
public CGFunc(Type pt0, String pn0, Type pt1, String pn1)
{
Init();
AddParam(pt0, pn0);
AddParam(pt1, pn1);
}
// Implementation of IDynamicMetaObjectProvider.GetMetaObject
public DynamicMetaObject GetMetaObject(System.Linq.Expressions.Expression parameter)
{
return new CGFuncMetaObject(parameter, this);
}
// Adds a parameter.
public void AddParam(Type pt, String pn)
{
var p = Expression.Parameter(pt, pn);
Parameters.Add(p);
ParameterMap[pn] = p;
}
// Adds a local variable
public void Var(Type vt, String vn)
{
var p = Expression.Parameter(vt, vn);
Variables.Add(p);
ParameterMap[vn] = p;
}
// Gets a CGValue whose Expr represents the named argument or variable
public CGValue Get(String name)
{
return ParameterMap[name];
}
// Gets a CGValue whose Expr represents an assignment to the named
// argument or variable
public CGValue Set(String name, Expression xval)
{
ParameterExpression p;
// This part creates the variable if it didn't previously exist.
// If that's not the behavior you want, skip this whole if block.
if (!ParameterMap.TryGetValue(name, out p))
{
p = Expression.Parameter(xval.Type, name);
Variables.Add(p);
ParameterMap[name] = p;
}
return Expression.Assign(p, xval);
}
// Adds expressions to the body of the function
public void Eval(params Expression[] instrs)
{
_members.AddRange(instrs);
}
// Call this to create a LambdaExpression after you are done
// adding statements.
public LambdaExpression CreateLambda()
{
return Expression.Lambda(
Expression.Block(Variables, _members), Parameters);
}
}The CGFuncMetaObject only needs definitions for BindGetMember and BindSetMember, since we only need to intercept get and set operations on the CGFunc instance to make them evaluate to the corresponding named argument or variable:
public class CGFuncMetaObject : DynamicMetaObject
{
public CGFuncMetaObject(Expression parameter, object value)
: base(parameter, BindingRestrictions.Empty, value)
{
}
public override DynamicMetaObject BindGetMember(GetMemberBinder binder)
{
// Build Expression representing this CGFunc instance
Expression fnExp = Expression.Convert(Expression, LimitType);
// Build Expression representing a call to CGFunc.Get
Expression getResult = Expression.Call(fnExp, "Get", null, Expression.Constant(binder.Name));
// Package up the result
return new DynamicMetaObject(getResult, BindingRestrictions.GetTypeRestriction(Expression, LimitType));
}
public override DynamicMetaObject BindSetMember(SetMemberBinder binder, DynamicMetaObject value)
{
// Build Expression representing this CGFunc instance
Expression fnExp = Expression.Convert(Expression, LimitType);
// Build Expression representing a call to CGFunc.Set
// CGFunc.Set will return an expression representing the assignment to
// the argument or local variable.
Expression setResult = Expression.Call(fnExp, "Set", null,
Expression.Constant(binder.Name),
value.Expression);
// Package up the result
return new DynamicMetaObject(setResult, BindingRestrictions.GetTypeRestriction(Expression, LimitType));
}
}What about BindInvokeMember? Aren't we calling methods on CGFunc in our client code? Yes, but the default implementation of each overridable method on DynamicMetaObject uses reflection on the corresponding dynamic object instance to find the corresponding member definition of its runtime type. That means that the default implementation of BindInvokeMember uses reflection to get the corresponding method of CGFunc and uses that in the expression it builds. That lets calls to methods defined directly on CGFunc to do what one would normally expect; that's the behavior we want, so we don't override it.
While the DLR offers flexibility and a convenient syntax, it comes at a run-time cost. However, in this case, the DLR's run-time cost happens while generating code; the final generated code is ordinary non-DLR .NET code, meaning we get many of the benefits of the DLR without the runtime cost usually associated with it.In my next article, I'll extend CGValue to support method calls, operators (such as +, -, etc.), and so on, and introduce a new dynamic class to support building expressions to represent static member and constructor usage. I'll also add support for implicit conversions from literals to ConstantExpressions so you can write code like:
cgfunc.Eval(
// ...,
expTestInstance.Prop1 = "Blah blah",
// ...
);instead of:
cgfunc.Eval(
// ...,
expTestInstance.Prop1 = new CGValue(Expression.Constant("Blah blah"));
// ...
);