Linq provider : an attempt… part 4

Using the Visitor pattern to manipulate expression trees

In the previous posts of this series, I started to describe a partial implementation of a Linq provider. The aim of this provider is to get data from a service, and in order to actually return that data to the caller, it implies some expression tree manipulations. After we obtained the data from the service, we want to inject an access to that actual data in the query expression tree, instead of the QueryableDummyData<Person> instance, which is in fact only a placeholder.

In order to replace that QueryableDummyData<Person> by a Person[] array, we use a class called ExpressionTreeConstantReplacer, which derives from the .NET 4.0 built-in ExpressionVisitor class, which in turn is based upon the Visitor pattern.

Applied to expression trees, the Visitor pattern can be used to generate an expression tree from the visited one, to accumulate some data while visiting the tree, or even both at the same time. Each visit method overload returns an expression, which is by default the unchanged expression it has just visited. It can return a new tree, but is should not modify the visited expression. This approach has the advantage to have no side-effect on the visited expression tree.

As a sample, the visitor pattern can be used to transform the following expression tree :

to this expression tree, which is the same but without the p => p.Age >= 21 where clause :

The ExpressionVisitor class is meant to be derived from, in order to create tree-manipulation classes. When the ExpressionVisitor’s Visit method is called, it determines the type of the node given as an entry parameter, and recursively visits the node and all his children, using each time the method corresponding to the node’s type.

This allows the developer of a derived class to override only the methods that needs to be. For instance, as we want to replace a Constant node with an other one, the class ExpressionTreeConstantReplacer derives from ExpressionVisitor and overrides the method VisitConstant.

internal class ExpressionTreeConstantReplacer<TReplacement>
    : ExpressionVisitor
{
    private Type originalType;
    private TReplacement replacementConstant;

    internal ExpressionTreeConstantReplacer(
        Type originalType, TReplacement replacementConstant)
    {
        this.originalType = originalType;
        this.replacementConstant = replacementConstant;
    }

    protected override Expression VisitConstant(
        ConstantExpression c)
    {
        if (c.Type == this.originalType)
            return Expression.Constant(this.replacementConstant);
        else
            return c;
    }
}

The constructor of this class takes two arguments : the type of the original constant to replace, and the new value. Then during the expression tree visiting process, when a node of type Constant is detected, the VisitConstant method is called, and if its type matches the type to replace, a new Constant node encapsulating the replacement value is returned.

In order to make the replacement call more expressive, a helper class is also introduced, in order to take advantage of C#’s type inference, which is available on static methods but not on constructors :

internal class ExpressionTreeConstantReplacer
{
    internal static Expression CopyAndReplace<TReplacement>(
        Expression expression,
        Type originalType,
        TReplacement replacementConstant)
    {
        var modifier =
            new ExpressionTreeConstantReplacer<TReplacement>(
                originalType,
                replacementConstant);
        return modifier.Visit(expression);
    }
}

This is what allows us to write the final replacement call this way :

Expression finalExpressionTree =
    ExpressionTreeConstantReplacer
        .CopyAndReplace(
            filteredExpressionTree,
            typeof(QueryableDummyData<Person>),
            queryablePersons);

Next time, I’ll describe the TreeVisualizer class I wrote to generate the expression trees visualizations in this post.