How LINQ Works – Creating Queries
Introduction
In recent weeks I’ve been decompiling LINQ with Reflector to try to better understand how expression trees get converted into code. I had some doubts about Reflector’s analysis capabilities, but Matt Warren and Nigel Watson assure me that it can resolve everything that gets generated by the C# 3.0 compiler. I am going to continue disassembling typical usage of LINQ to Objects, and will use whatever tools are available to allow me to peer beneath the hood. I’ll follow the flow of control from creation of a query to getting the first object out of that query. At least that way I’ll know if there’s something fishy going on in LINQ or Resharper.
What I’ve found from my researches is that there is a lot going on under the hood of LINQ. To begin to understand how LINQ achieves what it does, we will need to understand the following:
-
What the C# 3.0 compiler does to your queries.
-
Building and representing expression trees.
-
Code generation for anonymous types, and delegates and iterators.
-
Converting Expression trees into IL code.
-
What happens when the query is enumerated.
I’ll try to answer some of these questions. I’ve already made a start in some of my earlier LINQ posts to give an outline of the strategies LINQ uses to get things done. As a rule, it tends to use a lot of IL code generation to produce anonymous types to do its bidding. In this post, I’ll try to show you how it generates expression trees and turns them into code. In some cases, to prevent you from falling asleep, I’ll have to gloss over the details a little. I read through early drafts of this post and had to admit that describing every line of code was pretty much out of the question. I hope that at the very least, you’ll come away with a better idea of how to use LINQ.
What happens to your Queries
The way your queries are compiled depends on whether your data source is an enumerable sequence or a queryable.The handling for IEnumerable is much simpler and immediate than for IQueryable. I covered much of what happens in a previous post. The next section will show you how queries look behind the scenes.
Querying a Sequence
To illustrate what happens when you write a query in LINQ, I produced a couple of test methods with different types of query. Here’s the first:
Example 1
<span class="kwrd">private</span> <span class="kwrd">static</span> <span class="kwrd">void</span> Test3()
{
<span class="kwrd">int</span>[] primes = {1, 3, 13,17, 23, 5, 7, 11};
var smallPrimes = from q <span class="kwrd">in</span> primes
<span class="kwrd">where</span> q < 11
select q;
<span class="kwrd">foreach</span> (<span class="kwrd">int</span> i <span class="kwrd">in</span> smallPrimes)
{
Debug.WriteLine(i.ToString());
}
}
It enumerates an array of integers using a clause to filter out any that are greater than or equal to 11. The bit I’m going to look at is
Example 3
from q in primes where q < 11 select q
which is a query that we store in a variable smallPrimes. When this gets compiled, the C# 3.0 deduces the type of smallPrimes by working back through the query from primes through to the output of where and the output of select. The type flows through the various invocations of the extension methods to end up in an IEnumerable
Example 3
primes.Where(new delegate(int a){return a < 11;});
It has been translated into familar C# 2.0 syntax by the C# 3.0 compiler. By the time the C# 3.0 compiler has gotten through with Example 2, the code has been converted into this:
Example 4
<span class="kwrd">private</span> <span class="kwrd">static</span> <span class="kwrd">void</span> Test3()
{
<span class="kwrd">int</span>[] primes = <span class="kwrd">new</span> <span class="kwrd">int</span>[] { 1, 3, 13, 0x11, 0x17, 5, 7, 11 };
<span class="kwrd">if</span> (Program.<>9__CachedAnonymousMethodDelegate2 == <span class="kwrd">null</span>)
{
Program.<>9__CachedAnonymousMethodDelegate2 = <span class="kwrd">
new</span> Func<<span class="kwrd">int</span>, <span class="kwrd">bool</span>>(Program.<Test3>b__0);
}
IEnumerable<<span class="kwrd">int</span>> smallPrimes = Sequence.Where<<span class="kwrd">int</span>>(primes, Program.<>9__CachedAnonymousMethodDelegate2);
<span class="kwrd">foreach</span> (<span class="kwrd">int</span> i <span class="kwrd">in</span> smallPrimes)
{
Debug.WriteLine(i.ToString());
}
}
Most of it looks the same as before, but the LINQ query has been expanded out into two private static fields on the class called Program.<>9__CachedAnonymousMethodDelegate2. The first is a generic specification of Func<Type, bool> and other is a specialisation for type int (i.e. Func<int, bool>), which is how Test3 will use it. The anonymous delegate is initialised with Program.
Example 5
[CompilerGenerated]
<span class="kwrd">private</span> <span class="kwrd">static</span> <span class="kwrd">bool</span> <Test3>b__0(<span class="kwrd">int</span> q)
{
<span class="kwrd">return</span> (q < 11);
}
You can see that the query has been transformed into the code needed to test whether elements coming from an enumerator are less than 11. My previous post explains what happens inside of the call to Where (It’s a call to the static extension method Sequence.Where(this IEnumerable
Querying a SequenceQuery
As you’ve probably also noticed, the previous example is a straightforward example of LINQ in its guise as a nice way of filtering over an enumerable. It’s all done using IEnumerable
Lets see what happens when we convert the IEnumerable
Example 6
<span class="kwrd">private</span> <span class="kwrd">static</span> <span class="kwrd">void</span> Test4()
{
<span class="kwrd">int</span>[] primes = {1, 3, 13,17, 23, 5, 7, 11};
IQueryable<<span class="kwrd">int</span>> smallPrimes = from q <span class="kwrd">in</span> primes.ToQueryable()
<span class="kwrd">where</span> q < 11
select q;
<span class="kwrd">foreach</span> (<span class="kwrd">int</span> i <span class="kwrd">in</span> smallPrimes)
{
Debug.WriteLine(i.ToString());
}
}
I converted the array of integers into an` IQueryable
Example 7
<span class="kwrd">private</span> <span class="kwrd">static</span> <span class="kwrd">void</span> Test4()
{
ParameterExpression q = Expression.Parameter(<span class="kwrd">
typeof</span>(<span class="kwrd">int</span>), <span class="str">"q"</span>);
IQueryable<<span class="kwrd">int</span>> smallPrimes = Queryable.Where<<span class="kwrd">int</span>>(
Queryable.ToQueryable<<span class="kwrd">int</span>>( <span class="kwrd">new</span> <span class="kwrd">int</span>[] { 1, 3, 13, 0x11, 0x17, 5, 7, 11 }),
Expression.Lambda<Func<<span class="kwrd">int</span>, <span class="kwrd">bool</span>>>(Expression.LT(q,
Expression.Constant(11, <span class="kwrd">typeof</span>(<span class="kwrd">int</span>))),
<span class="kwrd">new</span> ParameterExpression[] { q }));
<span class="kwrd">foreach</span> (<span class="kwrd">int</span> i <span class="kwrd">in</span> smallPrimes)
{
Debug.WriteLine(i.ToString());
}
}
Quite a difference in the outputs! The call to ToQueryable has led the compiler to generate altogether different output. It inlined the primes collection, converted smallPrimes into a SequenceQuery and created a Lambda Expression containing a BinaryExpression for the less-than comparison rather than a simple anonymous delegate. As we know from the outline in this post, the Expression will eventually get converted into an anonymous delegate through a call to System.Reflection.Emit.DynamicMethod. That bit happens later on when the IEnumerator
Building the Expression Tree
This section describes what the LINQ runtime does with the expression tree to convert it into code. In this section I will guide you through a simple example of how the expression tree gets built out of example 9. The sequence of nested calls that eventually produces smallPrimes, each creates a node for insertion into the tree. By tracing through the calls to _Queryable.Where, Queryable.ToQueryable _and _Expression.Lambda _we can see that it constructs a tree as in Figure 1 below. It seems large, for a simple query. But, as Ander Hejlsberg pointed out, the elements of these trees are tiny (around 16 bytes each) so we get a lot of bang for our buck. The root of the tree, after calling Where, is a MethodCallExpression. In my previous post, I showed some of what happens when you try to get an enumerator from a SequenceQuery - an anonymous type is generated that iterates through the collection deciding whether or not to yield elements depending on the result from the predicate. This post I have a more or less accurate expression tree to work with, and I’ll explore how the GetEnumerator in SequenceQuery generates code by walking the expression tree.
If you are already familiar with the ideas of Abstract Syntax trees (ASTs) or object query languages, you could probably skip this part. If you’re one of those hardy souls who can withstand any quantity of detail, no matter how dry, then refer to sidebar for a more detailed breakdown of how an expression tree gets created.
**Figure 1. The Expression tree generated by method Test4. **
Example 8
[Extension]
<span class="kwrd">public</span> <span class="kwrd">static</span> IQueryable<T> Where<T>(IQueryable<T> source, Expression<Func<T, <span class="kwrd">bool</span>>> predicate)
{
<span class="rem">// validates args</span>
<span class="kwrd">return</span> source.CreateQuery<T>(
Expression.Call(
((MethodInfo)MethodBase.GetCurrentMethod()).MakeGenericMethod(<span class="kwrd">new</span> Type[] { <span class="kwrd">typeof</span>(T) }),
<span class="kwrd">null</span>,
<span class="kwrd">new</span> Expression[] { source.Expression, predicate }
)
);
}
Generating Code from an Expression Tree
This section describes what the LINQ runtime does with the expression tree to convert it into code. I think that the code generation phase is the most important part to understand in LINQ. It’s a tour de force of ingenuity that effectively converts C# into a strongly typed, declarative scripting language. It brings a lot of new power to the language. If you’re interested in seeing how the CodeDOM ought to be used, you couldn’t find a better example. It’s a must for anyone interested in code generation.
The code generation phase begins when the user calls GetEnumerator on the SequenceQuery. Till that point, all you have is a tree shaped data structure that declares the kind of results that you are after and where you want to get them from. This data structure can’t do anything. But when it is compiled, it suddenly gains power. LINQ interprets what you want, and generates the code to find it. That power is what I wanted to understand when I started digging into the LINQ with Reflector. I’d built a couple of ORM systems in the past so I had an inkling of what might get done with the expression trees - you have to turn them into queries that are comprehensible to the data source. That is easy enough with an ORM system, but how can you use the same code to query in-memory objects as for database bound ones. Well, you don’t use the same code - the extension methods allow LINQ to seem like that is what is happening, In truth what happens is that the code that processes your query is very different for each type of data source - the common syntax of LINQ hides different query engines.
The algorithm of the code generation system is simple:
-
Create a dynamic method (DM) as a template for later code generation
-
Find all parameters in the expression tree and use them as parameters of the method
-
Generate the Body of the dynamic method:
-
Walk the expression tree
-
Generate IL for each node according to it’s type - i.e. a MethodCallExpression will yield IL to call a method, whereas a LE BinaryExpression will conjoin its two halves using the less than or equal operator (Cle).
-
-
Create a Multicast Delegate to store the dynamic method in.
-
iterate the source collection, passing each element to the multicast delegate - if it returns true yield the element otherwise, ignore it.
Inside GetEnumerator for the query, the ExpressionCompiler class is invoked to create the code. It has a Compile methodperforms the algorithm above. The Compile method initially generates a top-level LambdaExpression. This lambda expression is a specification for a function - it tells the code generator what parameters the function needs to take, and how the result of the function is to be calculated. As with lambda calculus, these functions are nameless entities that can be nested. What that means for developers is that we can compose new queries from other queries. That is ideal for ad hoc query generators that add criteria to a query that is stored until they hit search.
Example 9
<span class="kwrd">internal</span> Delegate Compile(LambdaExpression lambda)
{
<span class="kwrd">this</span>.lambdas.Clear();
<span class="kwrd">this</span>.globals.Clear();
<span class="kwrd">int</span> num2 = <span class="kwrd">this</span>.GenerateLambda(lambda);
ExpressionCompiler.LambdaInfo info2 = <span class="kwrd">this</span>.lambdas[num2];
ExpressionCompiler.ExecutionScope scope2 =
<span class="kwrd">new</span> ExpressionCompiler.ExecutionScope(
<span class="kwrd">null</span>,
lambda,
<span class="kwrd">this</span>.lambdas.ToArray(),
<span class="kwrd">this</span>.globals.ToArray(),
info2.HasLiftedParameters);
<span class="kwrd">return</span> info2.Method.CreateDelegate(lambda.Type, scope2);
}
The first important thing that the Compile method does is create the top level lambda. As Example 10 shows, it first creates a compilation scope. The scope defines the visibility of variables in the method that is to be generated. We know from Example 9 that it maintains a couple of collections called lambdas and globals. Lambdas would define the parameters to the method (and recursively, would do the same for any sub method calls that are buried deeper in the expression tree). Globals maintains a list of references that will be visible to all dynamic methods.
Example 10
<span class="kwrd">private</span> <span class="kwrd">int</span> GenerateLambda(LambdaExpression lambda)
{
<span class="kwrd">this</span>.scope = <span class="kwrd">new</span> ExpressionCompiler.CompileScope(<span class="kwrd">this</span>.scope, lambda);
DynamicMethod method2 = <span class="kwrd">new</span> DynamicMethod(<span class="str">"lambda_"</span> + ExpressionCompiler.iMethod++,
lambda.Body.Type,
<span class="kwrd">this</span>.GetParameterTypes(lambda),
<span class="kwrd">typeof</span>(ExpressionCompiler.ExecutionScope),
<span class="kwrd">true</span>);
ILGenerator generator2 = method2.GetILGenerator();
<span class="kwrd">this</span>.GenerateInitLiftedParameters(generator2);
<span class="kwrd">this</span>.Generate(generator2, lambda.Body, ExpressionCompiler.StackType.Value);
generator2.Emit(OpCodes.Ret);
<span class="kwrd">int</span> num2 = <span class="kwrd">this</span>.lambdas.Count;
<span class="kwrd">this</span>.lambdas.Add(<span class="kwrd">new</span> ExpressionCompiler.LambdaInfo(lambda,
method2,
<span class="kwrd">this</span>.scope.HasLiftedParameters));
<span class="kwrd">this</span>.scope = <span class="kwrd">this</span>.scope.Parent;
<span class="kwrd">return</span> num2;
}
Next, the code generator creates the outline of an anonymous delegate using a DynamicMethod. It then goes on to generate the body of the anonymous delegate. The call to GenerateInitLiftedParameters should be familiar from my previous posts – it emits code for loading the parameters to the the lambda into the evaluation stack.
Next GenerateLambda will create the body for the anonymous method that has just been created. It is using the same code generator, so the body is inserted into the method as it goes along. It recurses through the expression tree to generate the code for the expression. As each element is visited it has code generated for the node, then each sub tree or leaf node is also passed to ExpressionCompiler.Generate. ExpressionCompiler.Generate is a huge switch statement that passes control off to a method dedicated to each node type. In processing the expression shown in Figure 1 we will end up calling GenerateLambda, GenerateBinaryExpression, and GenerateConstant. Each of these methods emits a bit of IL needed to flesh out the body of the Dynamic Method.
In Generate, each of the parameters of the the lambda are each passed through the code in example 11:
Example 11
ExpressionCompiler.StackType type1 = info1.IsOut ?
ExpressionCompiler.StackType.Address :
ExpressionCompiler.StackType.Value;
ExpressionCompiler.StackType type2 = <span class="kwrd">this</span>.Generate(gen, expression1, type1);
<span class="kwrd">if</span> ((type1 == ExpressionCompiler.StackType.Address) &&
(type2 != ExpressionCompiler.StackType.Address))
{
LocalBuilder builder1 = gen.DeclareLocal(info1.ParameterType);
gen.Emit(OpCodes.Stloc, builder1);
gen.Emit(OpCodes.Ldloca, builder1);
}
This piece walks the expression tree. The parameters of the lambda expression contain the terms of the comparison function to be performed (i.e. things like_ ‘_int q’ and ‘q < 11’). Eventually the generator will reach the sub expressions of the lambda – the LT BinaryExpression. GenerateBinary will be called on the ExpressionCompiler. I won’t include the code for that here, it’s 450 lines long – essentially a giant switch statement on the operator type. In this case it’s ExpressionType.LT. As a result the generator produces code for evaluating the left and right sides of the operation then emits a Clt opcode that will perform the signed comparison leaving 1 or 0 on the evaluation stack.
Enough code has now been generated to allow the production of the anonymous delegate. It’s applied to the elements of the array of ints. At the beginning of SequenceQuery.GetEnumerator() a lambda was produced from the (unmodified) Expression tree in Figure 1. The lambda was passed to the Compile function that invoked GenerateLambda that caused the whole recursive code generation process. Now, the Compile method creates an ExecutionsScope, and the DynamicMethod created during the recursive code generation process previously is given the scope to create a delegate. It has access to all of the byproducts of the code generation process so far, stored in a LambdaInfo class.
A Multicast delegate is then created following the format of the DynamicMethod created at the beginning. That DynamicMethod was not just a template for later use though, it passed the dynamic method that was created from the expression tree to add to its invocation list. We now have a delegate that we can call for each element in the collection, and a newly minted predicate from the expression tree to attach to the delegate.
The result of Compile is an IEnumerable
Conclusions
That’s it! The expression tree has been generated. It’s been used to create an anonymous method that was attached to a multicast delegate called when the source data store is enumerated. Each element that matched the predicate defined in the expression tree was yield returned. When you consider what this whole process has achieved, you’ll see how it is to produce something that does the same as the Sequence.While extension method that I described in my previous LINQ posts. The difference has been the use of expression trees to store the intent till the query needed to be interpretted. It is a lot more useful than a simple storable query - after all storing a delegate would have done that. The point of all this massive abstraction is to provide an opportunity to give our own implementation. There is no rule of LINQ that says we have to generate IL code in the way described here - we could generate SQL commands as must be done by LINQ to SQL. In future posts I aim to show how you can provide your own interpreter of expression trees.
Some might argue that since C# 3.0 concepts can be turned into C# 2.0 easily enough, yet C# 2.0 can’t be turned into C# 1.2, that C# 2.0 is a more significant advance. After reading some of the code that backs up the functional programming changes in C# 3.0 I’m not so sure. I think it just demonstrates that the C# 2.0 platform was rich enough not to require significant low-level changes this time around.
BTW: I tried valiantly to get a peek at the original source for LINQ, but the LINQ team are holding their cards very close to their chests at the moment, so no dice. Consequently, this article is my best guess, and should be taken under advisement that the source may change prior to release, and the abstractions may have clouded my view of the mechanism at work.
Andrew Matthews
C# LINQ ORM