Dynamic LINQ (A little more dynamic)

It seems I’ve become (in)famous in the last two days. With all the buzz around Microsoft.Data, I figure I’d post on something else that is somewhat related.

There were a bunch of comments on my previous posts that said we should do something to this effect:

dynamic db = Database.Open("name");
var q = from p in db.Products
        where p.UnitsInStock < 20
        select p;
Which looks like LINQ but it would be over a dynamic object. Of course you don’t get the strong typing benefits of LINQ since there are no classes, but at least the 
syntax is nice and the user is protected from SQL injection.

Disclaimer

This blog post is a technical discussion about the limitations that exist today around LINQ and dynamic and interesting ways to get around it. Nothing more. Continue reading.

Unfortunately when we try to compile this the compiler screams:

Query expressions over source type 'dynamic' or with a join sequence of type 'dynamic' are not allowed

Maybe it’s better if we just use a real ORM now, or the other Dynamic LINQ library, but now I’m curious and want to figure out if this is even possible. Let’s try it another way:

dynamic db = Database.Open("name");
var q = db.Products.Where(p => p.UnitsInStock < 20);

The compiler complains again, but this time with a different error:

Cannot use a lambda expression as an argument to a dynamically dispatched operation without first casting it to a delegate or expression tree type

So we’re being blocked in two different ways. Can we work around this somehow?

Since we can’t query over a dynamic object we’ll give the Database and the Products property static types:

class Database {
    private string _databaseName;
    public Database(string databaseName) {
        _databaseName = databaseName;
    }

    public static Database Open(string name) {
        return new Database(name);
    }

    public Query Products {
        get {
            return new Query();
        }
    }
}

class Query {

}

Now we can do this:

var db = Database.Open("name");
var q = from p in db.Products
        where p.UnitsInStock < 20
        select p;

Changing dynamic to var lets type inference take over so that db is typed as a Database instead of dynamic. Now we try to compile again:

Could not find an implementation of the query pattern for source type 'Query'.

This is a problem we can solve. The compiler translates code written using the query syntax:

var q = from p in db.Products
        where p.UnitsInStock < 20
        select p;

Into this:

var q = db.Products.Where(p => p.UnitsInStock < 20);

Bart de Smet has a great explanation on how this works. What this means is that we can implement the Select, Where, SelectMany or any other methods on our dynamic object that will make the compiler happy.

Given that, we can implement a dummy Where method to try to get this code to compile:

class Query { 
    public dynamic Where(Expression<Func<dynamic, dynamic>> predicate) {
        return null;
    }
}
Turns out that trying to compile this yields yet another error:
An expression tree may not contain a dynamic operation
Three different compiler errors, all to do with LINQ and dynamic. Looks like the compiler team went out of their way to block this. Let’s see if removing the 
expression works:
class Query {
    public dynamic Where(Func<dynamic, dynamic> predicate) {
        return null;
    }
}

Finally we’ve gotten the code to compile, now what? Well if this was LINQ to SQL/EF/SharePoint/etc., the query would be translated into an expression tree and executed on the server when we enumerated the results. I’m more interested in the first part of that, i.e. can we build an expression tree using dynamic LINQ.

Normally when you declare a lambda it can act like an expression tree or a delegate:

Expression<Func<int, int, int>> expr = (a, b) => a + b;
Func<int, int, int> add = (a, b) => a + b;
Console.WriteLine(expr);
Console.WriteLine(add);
The above code prints out (a, b) => (a + b) and System.Func`3[System.Int32,System.Int32,System.Int32], as expected. The compiler does all the hard work of figuring 
out how to build an expression tree from the code the user writes, but we don’t have this luxury since we’re in the dynamic world.

Enter Dynamic Expression

NOTE: If you aren’t familiar with the new dynamic in C#/VB feature, read up on it here.

We introduce a new class called DynamicExpression that we will use to make the compiler do our bidding:

class DynamicExpression : DynamicObject {
   
}
Before we dig into the implementation of this class, we have to figure out what kind of expressions we are going to build. How can we represent p.UnitsInStock in an
expression tree. Normally that would be a PropertyExpression that represents the UnitsInStock property on the Product class generated by either LINQ to SQL or

LINQ to Entities. We can’t do this since we don’t have any strong types.
For simplicity, we’re going to assume that all of the properties are integers, and that property access will be represented by a call to a Property method defined 
on DynamicExpression i.e. p.UnitsInStock will become a call to Property(“UnitsInStock”).
Now that we have that our of the way, we can get to the implemention. Lets start with TryGetMember:
class DynamicExpression : DynamicObject {
    public DynamicExpression(Expression expression) {
        GeneratedExpression = expression;
    }

    public Expression GeneratedExpression { get; private set; }

    public override bool TryGetMember(GetMemberBinder binder, out object result) {
        MethodInfo propertyMethod = typeof(DynamicExpression).GetMethod("Property", BindingFlags.NonPublic | BindingFlags.Static);
        var expression = Expression.Call(propertyMethod, Expression.Constant(binder.Name));
        result = new DynamicExpression(expression);
        return true;
    }

    private static int Property(string propertyName) {
        return 0;
    }
}
We’re storing the generated expression in a property so we can grab it after doing a bunch of manipulation. The Property method doesn’t actually have to do anything since 
its sole purpose is to represent property access.
Next we move on to simple binary expressions:
public override bool TryBinaryOperation(BinaryOperationBinder binder, object arg, out object result) {
    DynamicExpression dynamicExpression = arg as DynamicExpression;
    Expression rhs = null;
    if (dynamicExpression != null) {
        rhs = dynamicExpression.GeneratedExpression;
    }
    else {
        rhs = Expression.Constant(arg);
    }
    var expression = Expression.MakeBinary(binder.Operation, GeneratedExpression, rhs);
    result = new DynamicExpression(expression);
    return true;
}
First we are checking to see if the right hand side of the expression is itself a DynamicExpression and unwrapping the underlying expression if that is the case. Otherwise it
takes the right hand side to be a constant.
Some people may have already put the big picture together, if you haven’t as yet don’t worry, it isn’t exactly obvious how this works. We are trying to create an expression
tree using dynamic dispatch, that is, using the execution of the dynamic operations to build an expression tree.

Putting the pieces together

Remember how the compiler complained earlier when we tried to use dynamic in an expression tree? That’s why our overload of Where doesn’t take a Expression<Func<dynamic, dynamic>> but instead it takes a Func<dynamic, dynamic>. We’re going to fill in that blank implementation of the Where method we left off earlier.

class Query {
    public Query(Expression expression) {
        GeneratedExpression = expression;
    }

    public Expression GeneratedExpression { get; private set; }

    public Query Where(Func<dynamic, dynamic> predicate) {
        DynamicExpression expr = predicate(new DynamicExpression(GeneratedExpression));
        return new Query(expr.GeneratedExpression);
    }
}
Let’s we go back to the original query:
dynamic db = Database.Open("name");
var q = from p in db.Products
        where p.UnitsInStock < 20
        select p;
The compiler is going to turn this into a call to db.Products.Where(p => p.UnitsInStock < 20). When this calls our implementation of Where, we construct a DynamicExpression 
and execute the lambda (p.UnitsInStock < 20) on it. While executing the lambda, the compiler sees a member access(p.UnitsInStock) on a dynamic object p and calls our
implementation of TryGetMember. Instead of TryGetMember returning a value for p.UnitsInStock, it returns an Expression that represents a member access and wraps
it in another DynamicExpression so that the process continues. The compiler then sees the less than operator and calls our implementation of TryBinaryOperation. We use the
same trick for this as we did for member access (return an expression instead of a value). This could be done for all of the operators but I chose to two for brevity.
Now that we’ve done this, we can print out the generated expression. Here is the full program:
using System;
using System.Dynamic;
using System.Linq.Expressions;
using System.Reflection;

class Program {
    static void Main(string[] args) {
        var db = Database.Open("name");
        var q = from p in db.Products
                where p.UnitsInStock < p.Price + 1
                select p;

        Console.WriteLine(q.GeneratedExpression);
    }
}

class Database {
    private string _databaseName;
    public Database(string databaseName) {
        _databaseName = databaseName;
    }

    public static Database Open(string name) {
        return new Database(name);
    }

    public Query Products {
        get {
            return new Query(null);
        }
    }
}

class Query {
    public Query(Expression expression) {
        GeneratedExpression = expression;           
    }

    public Expression GeneratedExpression { get; private set; }

    public Query Where(Func<dynamic, dynamic> predicate) {
        DynamicExpression expr = predicate(new DynamicExpression(GeneratedExpression));
        return new Query(expr.GeneratedExpression);
    }
}

class DynamicExpression : DynamicObject {
    public DynamicExpression(Expression expression) {
        GeneratedExpression = expression;
    }

    public Expression GeneratedExpression { get; private set; }

    public override bool TryGetMember(GetMemberBinder binder, out object result) {
        MethodInfo propertyMethod = typeof(DynamicExpression).GetMethod("Property", BindingFlags.NonPublic | BindingFlags.Static);
        var expression = Expression.Call(propertyMethod, Expression.Constant(binder.Name));
        result = new DynamicExpression(expression);
        return true;
    }

    public override bool TryBinaryOperation(BinaryOperationBinder binder, object arg, out object result) {
        DynamicExpression dynamicExpression = arg as DynamicExpression;
        Expression rhs = null;
        if (dynamicExpression != null) {
            rhs = dynamicExpression.GeneratedExpression;
        }
        else {
            rhs = Expression.Constant(arg);
        }
        var expression = Expression.MakeBinary(binder.Operation, GeneratedExpression, rhs);
        result = new DynamicExpression(expression);
        return true;
    }

    public override bool TryUnaryOperation(UnaryOperationBinder binder, out object result) {
        if (binder.Operation == ExpressionType.IsFalse || binder.Operation == ExpressionType.IsTrue) {
            result = false;
            return true;
        }
        return base.TryUnaryOperation(binder, out result);
    }

    private static int Property(string propertyName) {
        return 0;
    }
}

Caveats

So we were able to get some expression tree support while combining LINQ and dynamic, but there are things to be aware of.

If the lhs of any operation isn’t dynamic then our TryBinaryOperation will never get called:

var q = from p in db.Products
        where 1 > p.UnitsInStock
        select p;

This would fail since 1 isn’t a dynamic object, we need something to bootstrap the dynamic dispatch.  Exercise for the reader, can we get around this limitation?

Nested queries won’t work without casting:

var q = from c in db.Categories
        from p in c.Products
        where p.UnitsInStock < 20
        select p;
This doesn’t work right now because we didn’t implement SelectMany, but also because of the first compiler error we encountered (Query expressions over source 
type 'dynamic' are not allowed). The nested query (from p in c.Products) would be trying to query over a dynamic source.
Query syntax doesn’t work in VB. VB does semantic translation instead of syntactic translation:
Dim q = From p In db.Products
        Where p.UnitsInStock < 20
        Select p
When the VB compiler generates the method for p.UnitsInStock < 20, it injects a type check for a boolean result which completely breaks this approach. 
You can however still use the lambda syntax to work around this.
There are probably other quirks that come with using this approach, and it is clear that the C# team took time to block certain scenarios, so don’t expect this to 
be a 100% solution.
We’ve successfully abused the new dynamic feature to get it working with LINQ. Hopefully in some future version of C# and VB we get deeper integration with 
LINQ and dynamic.
Published Wednesday, August 4, 2010 1:15 AM by davidfowl
Filed under: , ,

Comments

# re: Dynamic LINQ (A little more dynamic)

Wednesday, August 4, 2010 4:51 AM by kristofera

Neat, but how about taking a step back from 'dynamic'/IDispatch in the first place...?

Considering the target audience and usage area, here's an alternative approach:

1) Generate a L2S datacontext before the page is compiled, through e.g. a page-level directive:

<%@ WebMatrix.Database Database="Northwind.mdf" Alias="NWind" %>

That page level directive could trigger a datacontext and entity classes to be runtime-generated from the appropriate database (but before the C#/VB code in or behind the page is compiled).

Once generated it can be kept for the lifetime of the appdomain, and/or cached on disk if we want to give it a longer lifespan.

2) Use normal strongly-typed code against the runtime-generated DC.

Then the sample would become:

var db = Database.Open("NWind");

var q = db.Products.Where(p => p.UnitsInStock < 20);

...and 'dynamic' is out of the picture.

What do you think?

# re: Dynamic LINQ (A little more dynamic)

Wednesday, August 4, 2010 5:15 AM by davidfowl

@kristofera Even though it doesn't have much to do with the blog post, it is a valid idea. You are really talking about a custom build provider that runs sqlmetal.exe or uses some api's to generate the l2s classes on the fly. The other way to do it would be to IL Emit classes at runtime instead of compile time. In in the latter case you get no intellisense, and your back to dynamic linq.

# re: Dynamic LINQ (A little more dynamic)

Thursday, September 22, 2011 11:47 AM by Jacob

Did you ever solve:

"This would fail since 1 isn’t a dynamic object, we need something to bootstrap the dynamic dispatch.  Exercise for the reader, can we get around this limitation?"