How to Parse and Convert a Delegate into an Expression Tree

• Download source - 6.94 KB

Introduction

As far as you have been working with C# 3.0 or higher, and / or LINQ, concepts like "delegates", "lambda expressions", and "expressions trees" should not be new to you. Among many other interesting things, they permit you to represent code as a tree of logical expressions. If you wish, you can later compile those trees at run-time and execute them. Let's see an example:

Expression<Action<int>> func = x => Console.WriteLine( "Value= {0}", x );
func.Compile().Invoke( 7 );

The first line creates the logical expression tree for the code you wrote in the lambda expression at the right. The second line compiles this expression tree, and then executes the code producing what you can expect (printing in the console "Value= 7").

Note that if you don't use the Expression<...> construct, what you obtain is a compiled delegate, a regular function that can be used the way they are used with any other function. But obtaining an expression tree from the compiled code is not an easy task, so for any real purposes, you need to use the Expression<> construction.

And why would you need an expression tree instead of its actual compiled code? Because its real power comes when you realize that those expressions can be useful by themselves (and not only because the actual code they might produce): the logical representation they hold can be used for many other useful purposes. Indeed, this is precisely one of the major things a LINQ provider does: it translates those logical trees into something that a database-like component can understand (doing so by translating from C# code into the SQL dialect you are using).

Ok, it is starting to sound good. But I believe that there are some problems not solved with this mechanism the way it works today. They come from the fact that you have to use actual C# objects when writing those expressions, so you are restricted to the properties and methods supported by these objects. So what? Well, actually, I want to have a solution that will allow me to obtain these logical expression trees so that I can use them later regardless of what specific type or class I have used to write them.

In this C# 4.0 days, you start soon in thinking to use the new C# 4.0 dynamic objects. Why? Because when you declare an object with the dynamic keyword, you are instructing the compiler to use a late-binding mechanism – and the checks on whether the properties and methods used are valid or not are postponed until run-time, when the expression is actually executed. This permits you to write code against objects whose properties and methods can be not completely known when writing your program, or even worse, when they can change dynamically (as for instance adding or removing members and properties) while the object is alive.

So, you wonder, “if I use a dynamic parameter to write an expression tree, I have solved these problems, right?” ... Well, sorry, actually not. If you try something like this:

Expression< Action<dynamic> > func = x => Console.WriteLine( "Value: {0}", x );

the compiler is not happy and raises the error “An expression tree may not contain a dynamic operation”. Oops! But, on the flip side, it does allow you to write a delegate whose parameters can be dynamic ones. So for instance:

Action<dynamic> func = x => Console.WriteLine( "Value: {0}", x );

is a perfectly valid construction, and you obtain the compiled code of the "dynamic" delegate. Ok, you think, "is there any way to use this compiled dynamic delegate to obtain its expression tree?" I found no solutions on the internet that have met my expectations so I decided to develop my own one. So the answer is yes, there is, the DelegateParser class I introduce in this article.

The DelegateParser Solution

The DelegateParser class provides the static Parse() method that can be used to obtain the logical expression tree from a dynamic compiled delegate. Let's take a look at the following example:

Func< dynamic, object > func = x => x.Id >= "foo";
var exp = DelegateParser.Parse( func );
Console.WriteLine( "Expression: {0}", exp );

But... Have I used the >= operator to write a comparison between two string objects? This is not allowed! The point here is that, because the left part of the comparison is a dynamic object, the compiler does not perform any check at compile-time about whether this is a valid logical operation between the left and right parts of the operator, or by the way, if the object itself has or not the Id member.

Once executed, we obtain:

Expression: (T0.Id GreaterThanOrEqual foo)

This is good: I have obtained the expression tree from a dynamic compiled delegate. Later, I'll show you how to manipulate it, but for now let's try to understand what has happened. In the first line, I have obtained the compiled code of a delegate that takes a dynamic argument and returns an object. I could have obtained it with an Action<>, or by any other way, it doesn't matter. And, well, there is nothing new here... yet.

In the second line, I have used the Parse() method with this delegate as its argument. This method returns the root node of the expression tree. By default, the ToString() method of such node objects produces a very plain logical representation of the node or tree it holds, that can be used for tracing or identification purposes.

The DelegateParser.Parse() method requires that the delegate to parse should have at least one dynamic argument; otherwise it will throw an error. On the other hand, there is no limit at the number of dynamic arguments you can use, it is prepared to understand how many of them are used, and it assigns to each of them a given tag (T0, T1, and so forth).

Parse() also accepts an arbitrary number of additional string arguments: in this case each of these string arguments is assigned, in order, to the corresponding dynamic argument. For example, if the delegate has the Action<dynamic,dynamic> signature, when parsed using DelegateParser.Parse( func, "x", "y" ) invocation, then "x" is assigned as the prefix for the first dynamic argument, and "y" is assigned to the second one.

Before entering into the deeper details on how it works and how you can use the expression tree, let me bring a second example that shows how complex the expressions you wish to parse can be:

string id = "ID";
int val = 0;

Func< dynamic, object > func = 
  x => !( x.Alpha[ 34 ].Beta[ "ZZ" + val, 4 ] = "ABC" ) || 
		x( ++val ) == null && x.Gamma( id ) >= 9;
  		
for( int i = 0; i < 3; i++ )
  Console.WriteLine( "{0}\n", DelegateParser.Parse( func, "x" ) );

Here, we have used not only dynamic parameters, but also "external" objects as the string and int ones, whose values have been used in the expression, and even altered when in each iteration the Parse() function is invoked (as you expect in from the ++val statement). Note that those "external" objects are "invoked" to get their actual values. Finally, we obtain:

((Not::(x.Alpha[34].Beta[ZZ0,4]=ABC)) Or 
	(((1) Equal null) And (x.Gamma(ID) GreaterThanOrEqual 9)))

((Not::(x.Alpha[34].Beta[ZZ1,4]=ABC)) Or 
	(((2) Equal null) And (x.Gamma(ID) GreaterThanOrEqual 9)))

((Not::(x.Alpha[34].Beta[ZZ2,4]=ABC)) Or (((3) Equal null) 
	And (x.Gamma(ID) GreaterThanOrEqual 9)))

The Returned Expression Tree

The object returned from the Parse() is an instance of a DelegateNode derived class. This base class provides the NodeName property, a string that is either the tag assigned to the dynamic parameter, the name of the member or method, or null if having a name has no sense (it depends on the specific class we will be talking about). It does also provide the NodeParent property that keeps what is the parent node of the current one, if this concept applies, and a NodeLevel() function that calculates the "level" of the node: 0 for those that correspond to the dynamic parameters, 1 for the first level members, 2 for the members of the previous members, and so one.

Initially, the DelegateNode base class represents a dynamic parameter, and in its NodeName property should appear the tag assigned to it. Then, there are two types of specific derived classes. The first one if those classes that applies to values, members or methods of the dynamic parameters:

• The DelegateNode.Value class: this merely holds a value, represented by its object's NodeValue property. For instance, it is the result of expressions like: x => 7;

• The DelegateNode.MemberGet class: this is used to represent a member in a given parent (NodeParent). It has no other interesting property or method. It is typically the result of expressions like: x => x.Id;

• The DelegateNode.MemberSet class: this represents an assignment operation. The value to assign to the member is an object hold in the NodeValue property. Typically, it corresponds to expressions like: x => x.Alfa = var;

• The DelegateNode.IndexGet class: represents an index accessor on a given parent member, (in the NodeParent property). The actual indexes and their values are kept in the object[] NodeIndexes property. For instance: x => x.Id[24];

• The DelegateNode.IndexSet class: represents an assignment operation on an index accessor of a parent given member. It has the NodeParent, NodeValue, and NodeIndexes properties as the ones explained above. For instance: x => x.Id[24] = 9;

• The DelegateNode.Method class: represents a method invocation. Its NodeName property contains in this case the name of the method. Its NodeArguments property is an array of objects that keeps the argument to be used for its invocation. For instance: x => x.MyMethod( param );

• The DelegateNode.Invoke class: represents an invocation of the NodeTarget object with the NodeArguments given, as for instance in: x => x( param1, param2, ... );

The second category is formed by logical operations against dynamic objects:

• The DelegateNode.Binary class: represents a binary logical operation between a NodeLeft dynamic object, and a NodeRight generic object, that can be a constant, another object, or null. The NodeOperation property holds the ExpressionType operation, as defined in System.Linq.Expressions namespace. For instance: x => x.Id > "foo";

• The DelegateNode.Unary class: represents a unary logical operation against a given NodeTarget node. The operation is kept in its NodeOperation property, the same way as defined above. For instance: x => !x.Id;

• And finally, the DelegateNode.Convert class: represent a conversion operation between the logical type of the NodeTarget (not the type of the node itself, but the type it should carry as the consequence of the logical operations it holds) and the given NodeType type. For instance: x => (string)x.Id;

To use an expression tree, the best way is to use the Visitor pattern that, recursively, visits each node and parse them accordingly with their characteristics. I have used this pattern in my KyneticORM project to parse logical expressions and translate them into a given SQL dialect. The key classes to look at are the IKDBParser derived ones.

How DelegateParse Works

The basic idea is to use the fact that when a delegate with dynamic arguments is executed (using its DynamicInvoke() method), the DLR (Dynamic Language Runtime) machinery kicks-in and performs the required bindings at run-time, using for this activity a set of infrastructure methods that we can override to take note of what exact bindings it has done against our set of dynamic parameters.

The trick sits in how to maintain the ball rolling, so to speak, once a given binding is performed. If the dynamic object derives from the DynamicObject class, I found no way to make it happen. But after a lot of research (and experimentation), I have found that if the dynamic parameter is a class that implements the IDynamicMetaObjectProvider interface, and if the DynamicMetaObject its GetMetaObject() method returns overrides its BindXXX() methods in a given way, then the "execution" of the dynamic delegate flows in such a way that it is never interrupted and I can intercept each logical binding and instantiate the objects that will form the returned expression tree.

What way is it? Essentially is that each BindXXX()operation should return a new DelegateMetaNode object built such a way its Expression and Restrictions permits this newly created object to be used in the next binding operation. A simplified example is as follows:

public override DynamicMetaObject BindGetMember( GetMemberBinder binder )
{
  var @this = (DelegateNode)Value;
  var node = new DelegateNode.MemberGet( @this, binder.Name ) { _parser = @this._parser };
  node._parser.LastNode = node;

  var par = Expression.Variable( typeof( DelegateNode.MemberGet ), "ret" );
  var exp = Expression.Block(
    new ParameterExpression[] { par },
    Expression.Assign( par, Expression.Constant( node ) )
  );
  var restr = this.Restrictions;
  var ret = node;
  return new DelegateMetaNode( exp, restr, ret );
}

If you take a look at the code in the download, you'll see that the trickiest and hardest ones to implement were the BindConvert() and BindUnary() methods.

The first one because I had to return a DelegateMetaNode that it is compatible with the type expected by the conversion operation, and to that end, I have to create an appropriate "real" object of the correct type. But strings, for instance, don't have a default parameterless constructor. I ended up treating strings as an special case, and trying for any other types some default possibilities.

The second one was harder, because the binding mechanism produced the IsFalse and IsTrue ExpressionTypes that initially I was not aware of. So the overall schema kept failing till I realized that those unary expressions where injected into the flow by the binding mechanism, and I learnt how to deal with them.

Points of Interest

This is the third major version of DelegateParser. One extremely important thing this version solves is that, in its previous incarnation, once the dynamic delegate is executed one time, its compiled code is cached and it is not parsed (bound) again. This is very unfortunate because it meant that, if you use "external" objects, it doesn’t matter if their values have changed among different invocations of the delegate: the original value used in the first "execution" was the one that was used again and again.

In this version, the new DynamicMetaObject that is returned from each binding is constructed in such a way that the code the delegate holds is not cached: that’s the reason why the iteration you have seen in the second example works the way it was supposed to work.

References

[1] KyneticORM: "An ORM without configuration using C# 4.0 Dynamics, Generics and Reflection", describes an ORM library with no need for external mapping or configuration files, support of natural SQL-like query syntax, and full support for POCO objects, using C# 4.0 dynamics, generics and reflection. It uses DelegateParser to translate the logical expressions used into the given SQL dialect of choice. It can be found at: KyneticORM.

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)