LINQ to Whatever - Expression Trees

LINQ to SQL, LINQ to XML, LINQ to Objects – all pretty powerful features added with .NET 3.0 that let you write in-line, intellisense-supported queries against collections of data without having to mess with data adapters, complex filters like XPath, or foreach loops. But how do they work!?

The root of it all is in Expression Trees (ha… Trees… root… get it?). An expression tree is basically an object that expresses the query you want to perform against a set of data. In LINQ, you can write a query as follows:

1
2
3
var customers = from c in dataContext.Customers
                      where c.City == "London"
                      select c;

And if you look at the compiled code, what you’ll actually see is this:

1
2
3
4
5
6
7
8
ParameterExpression pc = Expression.Parameter(typeof(Customer), "c");
IQueryable<Customer> q3 =
    dc.Customers.Where<Customer>(
      Expression.Lambda<Func<Customer, bool>>(
        Expression.Equal(
        Expression.Property(pc,   typeof(Customer).GetProperty("City")),
          Expression.Constant("London", typeof(string))
      ), new   ParameterExpression[] { pc }));

As with a lot of the new features in .NET 3/3.5, most of the new language constructs are really just shortcuts that expand into standard C# code (i.e. the { get; set; } parameter shortcut does actually make a private variable and set/return it like we used to have to do, we just don’t see it without decompiling). So what this is actually doing is creating a Expression object and using the filter we specified to populate properties of that object, which then gets passed to our data source.

.NET supplies a few data source providers for us, i.e. SQL, XML, Objects. What those built-in providers do is take that Expression object and translate it into something it can execute against the datasource. So for our expression above, the SQL provider would translate that into an SQL query it could run against the database, or the XML provider would turn it into a matching XPath query. So if we wanted to make our very own provider, all we would have to do is parse and interpret the Expression object as something we can execute against our data source. For example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class SomeNewProvider : IQueryProvider<T>
{
    //method that we have to implement from IQueryProvider
    public T Execute(Expression expression)
    {
        //our own class used to contain a query
        UseableQuery query;
        if(expression is ParameterExpression)
        {
            //private method to translate expression to query object
            query = TranslateParameterExpression(expression);
        }
        //private method to execute our query object 
      //against our datasource
        return (T)ExecuteAgainstData(query);
    }
}

Of course this only covers one part of the whole puzzle, we still have to visit result to object mapping & change tracking, but it’s a good start to understanding how LINQ Expression Trees work.

Comments