Friday, April 06, 2007 8:14 AM bart

The IQueryable tales - LINQ to LDAP - Part 1: Key concepts

Introduction

Welcome to the first real part of our LINQ-to-LDAP series. So far, we've been discussing:

In this post, a few key concepts of LINQ concerning the way queries are compiled are discussed. More specifically, we'll talk about IEnumerable<T>, IQueryable<T> and expression trees from a 10,000 feet view. In subsequent posts, we'll dig into more details on the latter portion around IQueryable<T> and expression tree parsing to end up with a nice and smooth translation of LINQ queries to LDAP queries.

To get started, open up Visual Studio 2005 "Orcas" March 2007 CTP and create a new Console Application project. Give it whatever name you see fit, e.g. LINQtoLDAP. For the sake of the demo, we're going to do something rather extraordinary. Instead of running the application, we'll make ourselves happy with the compilation result only, in order to do some ILDASM inspection.

Start by creating a simple "entity" object, which is a class defined like this:

A simple entity object - Copy Code
1 class MyObject 2 { 3 public string Name { get; set; } 4 }

Notice the use of the C# 3.0 automatic properties feature.

 

IEnumerable<T>

In the first demo, we'll focus on the LINQ-to-Objects "query provider". When the compiler encounters a class that implements IEnumerable<T>, the System.Linq.Enumerable extension methods come into play to support query operations. An example will make much clear; change the Main method as follows:

An IEnumerable query - Copy Code
1 static void Main(string[] args) 2 { 3 var lst = new List<MyObject>(); 4 var res = from o in lst 5 where o.Name == "Bart" 6 select o; 7 }

The LINQ query that spans lines 4 to 6 gets translated into the following by the compiler:

static void Main(string[] args) { var lst = new List<MyObject>(); var res = lst.Where(o => o.Name == "Bart").Select(o => o); }

In here, Where and Select are so-called extension methods. In reality the code above translates into:

static void Main(string[] args) { var lst = new List<MyObject>(); var res = System.Linq.Enumerable.Select(System.Linq.Enumerable.Where(lst, o => o.Name == "Bart"), o => o); }

using static method calls. What remains are the lambda expressions that get translated into anonymous methods via delegates:

static void Main(string[] args) { var lst = new List<MyObject>(); var res = System.Linq.Enumerable.Select(System.Linq.Enumerable.Where(lst, delegate(MyObject o) { return o.Name == "Bart"; }), delegate (MyObject o) { return o; }); }

Finally, the local type inference (keyword "var") is resolved, which is pretty simple in this case because we didn't do any projections using anonymous types:

An IEnumerable query's C# 2.0 equivalent - Copy Code
1 static void Main(string[] args) 2 { 3 List<MyObject> lst = new List<MyObject>(); 4 IEnumerable<MyObject> res = System.Linq.Enumerable.Select(System.Linq.Enumerable.Where(lst, delegate(MyObject o) { return o.Name == "Bart"; }), delegate (MyObject o) { return o; }); 5 } 6

As you can see, the syntactical sugar of C# 3.0 makes the query much more like a query. The extension methods Where and Select are implemented as enumerators, making the whole thing lazy evaluated (deferred execution). A sample implementation of both is shown below (you can take this piece of code and compile it in Visual Studio 2005; it's C# 3.0 free):

LINQ in C# 2.0 style - Copy Code
1 using System; 2 using System.Collections.Generic; 3 4 namespace LINQtoLDAP 5 { 6 class Program 7 { 8 static void Main(string[] args) 9 { 10 List<MyObject> lst = new List<MyObject>(); 11 IEnumerable<MyObject> res = Select(Where(lst, delegate(MyObject o) { return o.Name == "Bart"; }), delegate(MyObject o) { return o; }); 12 } 13 14 public delegate TResult Func<TArg0, TResult>(TArg0 arg0); 15 16 public static IEnumerable<TSource> Where<TSource>(IEnumerable<TSource> source, Func<TSource, bool> predicate) 17 { 18 foreach (TSource item in source) 19 if (predicate(item)) 20 yield return item; 21 } 22 23 public static IEnumerable<TResult> Select<TSource, TResult>(IEnumerable<TSource> source, Func<TSource, TResult> selector) 24 { 25 foreach (TSource item in source) 26 yield return selector(item); 27 } 28 } 29 30 class MyObject 31 { 32 private string name; 33 public string Name { get { return name; } set { name = value; } } 34 } 35 }

Basically, we've created a pipeline of enumerators that feed their output in the next one's input. It's only when a foreach loop iterates over the output of the pipeline that the whole thing starts to work; therefore, no more processing is done than strictly required. Notice that if we would provide e.g. a sorting enumerator however, we'd need to suck the whole result from the predecessor in the pipeline in order to be able to sort it to the output. Therefore, laziness has its restrictions too.

Now, let's revisit our original C# 3.0 stylish query definition:

C# 3.0 LINQ style query
static void Main(string[] args) { var lst = new List<MyObject>(); var res = from o in lst where o.Name == "Bart" select o; }

Make sure to import the System.Linq namespace again, which is required to resolve the extension method calls. Compile the application and open up a "Visual Studio Codename Orcas command prompt". Navigate to the bin\Debug output folder of your newly created project and run ildasm.exe against the .exe assembly file. You should see the following output:

We're not going to focus on the MyObject class definition which is just some automatic property magic. We're much more interested in the Program class however. So, open up the Main : void(string[]) method right now. Here's the result:

Main method IL
.method private hidebysig static void Main(string[] args) cil managed { .entrypoint // Code size 46 (0x2e) .maxstack 4 .locals init ([0] class [mscorlib]System.Collections.Generic.List`1<class LINQtoLDAP.MyObject> lst, [1] class [mscorlib]System.Collections.Generic.IEnumerable`1<class LINQtoLDAP.MyObject> res) IL_0000: nop IL_0001: newobj instance void class [mscorlib]System.Collections.Generic.List`1<class LINQtoLDAP.MyObject>::.ctor() IL_0006: stloc.0 IL_0007: ldloc.0 IL_0008: ldsfld class [System.Core]System.Linq.Func`2<class LINQtoLDAP.MyObject,bool> LINQtoLDAP.Program::'<>9__CachedAnonymousMethodDelegate2' IL_000d: brtrue.s IL_0022 IL_000f: ldnull IL_0010: ldftn bool LINQtoLDAP.Program::'<Main>b__1'(class LINQtoLDAP.MyObject) IL_0016: newobj instance void class [System.Core]System.Linq.Func`2<class LINQtoLDAP.MyObject,bool>::.ctor(object, native int) IL_001b: stsfld class [System.Core]System.Linq.Func`2<class LINQtoLDAP.MyObject,bool> LINQtoLDAP.Program::'<>9__CachedAnonymousMethodDelegate2' IL_0020: br.s IL_0022 IL_0022: ldsfld class [System.Core]System.Linq.Func`2<class LINQtoLDAP.MyObject,bool> LINQtoLDAP.Program::'<>9__CachedAnonymousMethodDelegate2' IL_0027: call class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0> [System.Core]System.Linq.Enumerable::Where<class LINQtoLDAP.MyObject>(class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0>, class [System.Core]System.Linq.Func`2<!!0,bool>) IL_002c: stloc.1 IL_002d: ret } // end of method Program::Main

Time to reconstruct this piece of code back to C# terms. Don't worry about the IL_0000 line which happens to be debugger supporting. In a release build, you'd see slightly different code. A quick analysis:

  • IL_0001 creates the generic List<MyObject> object, as defined in line 3 of the original source.
  • IL_0008 pushes the static field <>9__CachedAnonymousMethodDelegate2 on the stack. This is an anonymous delegate, which will be discussed in a minute. It will be null however, causing IL_000d to fall through to IL_000f.
  • IL_0010 gets a function pointer to the static method <Main>b__1, an anonymous method, as discussed below.
  • IL_0016 finally creates the delegate object that used to be null previously (IL_0008 and IL_000d decided this). As you can see, it's of type System.Linq.Func<MyObject, bool> which is the signature for a predicate (see line 16 of the C# 2.0 style LINQ query code). IL_001b stores the delegate as a static field (as used in IL_0008).
  • IL_0022 is where we end up finally. Here's the predicate delegate is retrieved again.
  • IL_0027 now makes a call to System.Linq.Enumerable.Where passing in two parameters from the stack; the first was loaded on the stack in line IL_0007; the second one is the predicate loaded in line IL_0022.
  • IL_002c stores the result, which is of type System.Collections.Generic.IEnumerable<MyObject> in a local variable, ready to be returned to the caller in line IL_002d.

To clarify things, a little stack transition diagram:

  • IL_0000: {} -> {}
  • IL_0001: {} -> { System.Collections.Generic.List<MyObject> }
  • IL_0006: { System.Collections.Generic.List<MyObject> } -> {}
  • IL_0007: {} -> { System.Collections.Generic.List<MyObject> }
  • IL_0008: { System.Collections.Generic.List<MyObject> } -> { System.Collections.Generic.List<MyObject>, System.Linq.Func<MyObject,bool> }
  • IL_000d: { System.Collections.Generic.List<MyObject>, System.Linq.Func<MyObject,bool> } -> { System.Collections.Generic.List<MyObject> }
    • False
      • IL_000f: { System.Collections.Generic.List<MyObject> } -> { System.Collections.Generic.List<MyObject>, null }
      • IL_0010: { System.Collections.Generic.List<MyObject>, null } -> { System.Collections.Generic.List<MyObject>, null, native int } (top of stack is function pointer)
      • IL_0016: { System.Collections.Generic.List<MyObject>, null, native int } -> { System.Collections.Generic.List<MyObject>, System.Linq.Func<MyObject,bool> }
      • IL_001b: { System.Collections.Generic.List<MyObject>, System.Linq.Func<MyObject,bool> } -> { System.Collections.Generic.List<MyObject> }
      • IL_0020: { System.Collections.Generic.List<MyObject> } -> { System.Collections.Generic.List<MyObject> }
      • (Fall through to IL_0022)
  • IL_0022: { System.Collections.Generic.List<MyObject> } -> { System.Collections.Generic.List<MyObject>, System.Linq.Func<MyObject,bool> }
  • IL_0027: { System.Collections.Generic.List<MyObject>, System.Linq.Func<MyObject,bool> } -> { System.Collections.Generic.IEnumerable<MyObject> }
  • IL_002c: { System.Collections.Generic.IEnumerable<MyObject> } -> {}
  • IL_002d: {} -> {} (= void)

Now let's take a look at the anonymous method definition in <Main>b__1:

.method private hidebysig static bool '<Main>b__1'(class LINQtoLDAP.MyObject o) cil managed { .custom instance void [mscorlib]System.Runtime.CompilerServices.CompilerGeneratedAttribute::.ctor() = ( 01 00 00 00 ) // Code size 21 (0x15) .maxstack 2 .locals init ([0] bool CS$1$0000) IL_0000: ldarg.0 IL_0001: callvirt instance string LINQtoLDAP.MyObject::get_Name() IL_0006: ldstr "Bart" IL_000b: call bool [mscorlib]System.String::op_Equality(string, string) IL_0010: stloc.0 IL_0011: br.s IL_0013 IL_0013: ldloc.0 IL_0014: ret } // end of method Program::'<Main>b__1'

This is our predicate function that takes in a MyObject as its parameter and returns true or false depending on the condition (o.Name == "Bart"). The code is straightforward to understand and consist of a property getter call (IL_0001) and an equality test (IL_000b). As an exercise you can try to reconstruct the stack transition diagram for this one too :-).

One remarkable thing is that the Select method doesn't appear in here at all; this is a little optimization that eliminates identity projections (o => o). If we'd perform a projection using an anonymous type, things would look different:

Query with projection - Copy Code
1 static void Main(string[] args) 2 { 3 var lst = new List<MyObject>(); 4 var res = from o in lst 5 where o.Name == "Bart" 6 select new { CapitalizedName = o.Name.ToUpper() }; 7 }

The result is this:

At the bottom, there's an anonymous type with the easy-to-remember (not!) name <>f__AnonymousType0`1<'<>__AnonymousTypeTypeParameter1'>. Feel free to inspect it in more detail; you'll see that a property CapitalizedName was created as defined in line 6 of the original source. Much more magic happens inside e.g. the Equals method (compares all fields for equality), the GetHashCode method and the ToString method (yes, it has a nice string representation that's built automagically using a StringBuilder object). However, we shift our focus on the projection operation itself, which is represented as a delegate of type System.Linq.Func<MyObject, the anonymous type with the nasty name>:

.field private static class [System.Core]System.Linq.Func`2<class LINQtoLDAP.MyObject,class '<>f__AnonymousType0`1'<string>> '<>9__CachedAnonymousMethodDelegate5' .custom instance void [mscorlib]System.Runtime.CompilerServices.CompilerGeneratedAttribute::.ctor() = ( 01 00 00 00 )

Our projection logic lives in the <Main>b__3 method:

.method private hidebysig static class '<>f__AnonymousType0`1'<string> '<Main>b__3'(class LINQtoLDAP.MyObject o) cil managed { .custom instance void [mscorlib]System.Runtime.CompilerServices.CompilerGeneratedAttribute::.ctor() = ( 01 00 00 00 ) // Code size 30 (0x1e) .maxstack 2 .locals init ([0] class '<>f__AnonymousType0`1'<string> '<>g__initLocal1', [1] class '<>f__AnonymousType0`1'<string> CS$1$0000) IL_0000: newobj instance void class '<>f__AnonymousType0`1'<string>::.ctor() IL_0005: stloc.0 IL_0006: ldloc.0 IL_0007: ldarg.0 IL_0008: callvirt instance string LINQtoLDAP.MyObject::get_Name() IL_000d: callvirt instance string [mscorlib]System.String::ToUpper() IL_0012: callvirt instance void class '<>f__AnonymousType0`1'<string>::set_CapitalizedName(!0) IL_0017: nop IL_0018: ldloc.0 IL_0019: stloc.1 IL_001a: br.s IL_001c IL_001c: ldloc.1 IL_001d: ret } // end of method Program::'<Main>b__3'

Again, little surprising. Now our Main methods looks like this:

.method private hidebysig static void Main(string[] args) cil managed { .entrypoint // Code size 82 (0x52) .maxstack 4 .locals init ([0] class [mscorlib]System.Collections.Generic.List`1<class LINQtoLDAP.MyObject> lst, [1] class [mscorlib]System.Collections.Generic.IEnumerable`1<class '<>f__AnonymousType0`1'<string>> res) IL_0000: nop IL_0001: newobj instance void class [mscorlib]System.Collections.Generic.List`1<class LINQtoLDAP.MyObject>::.ctor() IL_0006: stloc.0 IL_0007: ldloc.0 IL_0008: ldsfld class [System.Core]System.Linq.Func`2<class LINQtoLDAP.MyObject,bool> LINQtoLDAP.Program::'<>9__CachedAnonymousMethodDelegate4' IL_000d: brtrue.s IL_0022 IL_000f: ldnull IL_0010: ldftn bool LINQtoLDAP.Program::'<Main>b__2'(class LINQtoLDAP.MyObject) IL_0016: newobj instance void class [System.Core]System.Linq.Func`2<class LINQtoLDAP.MyObject,bool>::.ctor(object, native int) IL_001b: stsfld class [System.Core]System.Linq.Func`2<class LINQtoLDAP.MyObject,bool> LINQtoLDAP.Program::'<>9__CachedAnonymousMethodDelegate4' IL_0020: br.s IL_0022 IL_0022: ldsfld class [System.Core]System.Linq.Func`2<class LINQtoLDAP.MyObject,bool> LINQtoLDAP.Program::'<>9__CachedAnonymousMethodDelegate4' IL_0027: call class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0> [System.Core]System.Linq.Enumerable::Where<class LINQtoLDAP.MyObject>(class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0>, class [System.Core]System.Linq.Func`2<!!0,bool>) IL_002c: ldsfld class [System.Core]System.Linq.Func`2<class LINQtoLDAP.MyObject,class '<>f__AnonymousType0`1'<string>> LINQtoLDAP.Program::'<>9__CachedAnonymousMethodDelegate5' IL_0031: brtrue.s IL_0046 IL_0033: ldnull IL_0034: ldftn class '<>f__AnonymousType0`1'<string> LINQtoLDAP.Program::'<Main>b__3'(class LINQtoLDAP.MyObject) IL_003a: newobj instance void class [System.Core]System.Linq.Func`2<class LINQtoLDAP.MyObject,class '<>f__AnonymousType0`1'<string>>::.ctor(object, native int) IL_003f: stsfld class [System.Core]System.Linq.Func`2<class LINQtoLDAP.MyObject,class '<>f__AnonymousType0`1'<string>> LINQtoLDAP.Program::'<>9__CachedAnonymousMethodDelegate5' IL_0044: br.s IL_0046 IL_0046: ldsfld class [System.Core]System.Linq.Func`2<class LINQtoLDAP.MyObject,class '<>f__AnonymousType0`1'<string>> LINQtoLDAP.Program::'<>9__CachedAnonymousMethodDelegate5' IL_004b: call class [mscorlib]System.Collections.Generic.IEnumerable`1<!!1> [System.Core]System.Linq.Enumerable::Select<class LINQtoLDAP.MyObject,class '<>f__AnonymousType0`1'<string>>(class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0>, class [System.Core]System.Linq.Func`2<!!0,!!1>) IL_0050: stloc.1 IL_0051: ret } // end of method Program::Main

The new stuff starts on line IL_002c where similar logic as for the Where-method call is present, this time to serve the Select clause. Based on this analysis, you can conclude that LINQ queries against IEnumerable<T> implementations (like List<MyObject>) are completely transformed into corresponding IL code. Feel free to make queries more complicated (orderby, groupby, join, ...) and take the challenge to parse the resulting IL code :-).

If you want to learn more about the extension standard query operator methods that are implemented in System.Linq.Enumerable, download my LINQSQO project that contains a full custom implementation of all these operators (it can even be compiled using C# 2.0 in Visual Studio 2005!).

 

IQueryable<T>

Now, let's swap to the big brother of IEnumerable<T>: enter LINQ's IQuerable<T> interface. The definition is displayed below:

Generic IQueryable definition - Copy Code
1 using System.Collections; 2 using System.Collections.Generic; 3 using System.Linq.Expressions; 4 5 namespace System.Linq 6 { 7 // Summary: 8 // Provides functionality to evaluate queries against a specific data source 9 // wherein the type of the data is known. 10 public interface IQueryable<T> : IEnumerable<T>, IQueryable, IEnumerable 11 { 12 // Summary: 13 // Constructs an System.Linq.IQueryable<T> object that can evaluate the query 14 // represented by the specified expression tree. 15 // 16 // Parameters: 17 // expression: 18 // The System.Linq.Expressions.Expression representing the query to be encompassed. 19 // 20 // Returns: 21 // An System.Linq.IQueryable<T> that can evaluate the query represented by the 22 // specified expression tree. 23 IQueryable<TElement> CreateQuery<TElement>(Expression expression); 24 // 25 // Summary: 26 // Executes the query represented by the specified expression tree. 27 // 28 // Parameters: 29 // expression: 30 // The System.Linq.Expressions.Expression that represents the query to be executed. 31 // 32 // Returns: 33 // A value of type TResult representing the result of the specified query. 34 TResult Execute<TResult>(Expression expression); 35 } 36 }

Notice that this interface extends on IEnumerable<T>; that is, every IQueryable<T> is also IEnumerable<T>, meaning that you can iterate over it. As usual, the generic interface has a non-generic counterpart IQueryable, just like IEnumerable<T> has a non-generic variant of IEnumerable. The main difference between pure IEnumerable<T>'s and IQueryable<T>'s is the fact that the latter ones are based on expressions. Essentially, such an expression is a data-based representation of a piece of code (in this case a query, hence the name IQueryable) that can be parsed at runtime in order to be translated into a domain-specific query language like LDAP. This is done via the CreateQuery method that takes an expression and returns another IQueryable<TElement> object (where T and TElement can be possibly different, e.g. to serve projections). This result is IQueryable<>, thus it's IEnumerable<> too, meaning that we can iterate over it. However, the results won't be created by means on System.Linq.Enumerable extension methods this time; instead, the underlying implementation of the IQuerable<> implementor will perform lots of plumbing to translate the given expression in a suitable query expression that's sent to the underlying data source, getting the results back. We won't focus on Execute for now.

As an example, consider LINQ-to-SQL. Go to our project in Visual Studio "Orcas" and add a new item to the project - a LINQ to SQL File:

In Server Explorer, make a connection to a database that contains some table (note: the March 07 "Orcas" CTP VPC contains a SQLEXPRESS instance with default databases; feel free to add your own database in there for testing). On my machine, I've created a simple Users table in the msdb database. Drag-and-drop the table to the Object Relational Designer surface of Orcas:

Now, in the Main method, add the following:

LINQ-to-SQL sample - Copy Code
1 static void Main(string[] args) 2 { 3 DemoDataContext ctx = new DemoDataContext(); 4 ctx.Log = Console.Out; 5 6 var res = from usr in ctx.Users 7 where usr.Name.Contains("Bart") 8 select usr; 9 10 foreach (var user in res) 11 Console.WriteLine(user.ID + " - " + user.Name); 12 }

The LINQ query doesn't reveal we're talking to another type of data source (i.e. SQL Server). However, behind the scenes all sorts of magic happens to translate the query to an appropriate SQL statement. The Log property in line 4 can be used to display what's happening at runtime:

 

Indeed, the LINQ query was translated into a SQL statement at runtime (in contrast to lots of O/R mapping tools that perform this task at design time). As the matter in fact, the C# compiler encountered an IQueryable<> object this time ... ctx.Users. When you go to the definition of this property, you'll see something like this inside the DemoDataContext class:

public global::System.Data.Linq.Table<User> Users { get { return this.GetTable<User>(); } }

The GetTable<T> method is derived from System.Linq.Data.DataContext and returns a Table<T>. In our case, T equals User, as defined below:

[global::System.Data.Linq.Table(Name="dbo.Users")] public partial class User : global::System.Data.Linq.INotifyPropertyChanging, global::System.ComponentModel.INotifyPropertyChanged { private int _ID; private string _Name; [global::System.Diagnostics.DebuggerNonUserCodeAttribute()] public User() { this._ID = default(int); } [global::System.Data.Linq.Column(Storage="_ID", Name="ID", DBType="Int NOT NULL IDENTITY", IsPrimaryKey=true, IsDBGenerated=true, CanBeNull=false)] public int ID { get { return this._ID; } } [global::System.Data.Linq.Column(Storage="_Name", Name="Name", DBType="NVarChar(50) NOT NULL", CanBeNull=false)] public string Name { get { return this._Name; } set { if ((this._Name != value)) { this.OnPropertyChanging("Name"); this._Name = value; this.OnPropertyChanged("Name"); } } } public event global::System.ComponentModel.PropertyChangedEventHandler PropertyChanging; public event global::System.ComponentModel.PropertyChangedEventHandler PropertyChanged; [global::System.Diagnostics.DebuggerNonUserCodeAttribute()] protected void OnPropertyChanging(string propertyName) { if ((this.PropertyChanging != null)) { this.PropertyChanging(this, new global::System.ComponentModel.PropertyChangedEventArgs(propertyName)); } } [global::System.Diagnostics.DebuggerNonUserCodeAttribute()] protected void OnPropertyChanged(string propertyName) { if ((this.PropertyChanged != null)) { this.PropertyChanged(this, new global::System.ComponentModel.PropertyChangedEventArgs(propertyName)); } } }

This mapping was done by the designer and contains all the information needed to construct SQL statements for querying and updating at runtime, based on various attributes like TableAttribute and ColumnAttribute. We'll come back to this in one of the subsequent posts, when talking about "entity class" generation (in our case for Active Directory objects). However, let's revisit System.Data.Linq.Table<T> for a minute and generate its definition using the IDE:

Just focus on the declaration:

// Summary: // Represents a table for a particular type in the underlying database. public sealed class Table<T> : IQueryable<T>, IEnumerable<T>, ITable, IQueryable, IEnumerable, IListSource {

Indeed, implementing IQueryable<T>! Right, time for some IL. Strip the Main method definition to the following (unless you want to see more more IL than necessary for the demo :-)):

LINQ-to-SQL simplified - Copy Code
1 static void Main(string[] args) 2 { 3 DemoDataContext ctx = new DemoDataContext(); 4 5 var res = from usr in ctx.Users 6 where usr.Name.Contains("Bart") 7 select usr; 8 }

Compile and go back to the command prompt to open the assembly with ILDASM. Again, open the Main method; notice that all anonymous methods and types are gone. Here's Main's IL code:

.method private hidebysig static void Main(string[] args) cil managed { .entrypoint // Code size 133 (0x85) .maxstack 7 .locals init ([0] class LINQtoLDAP.DemoDataContext ctx, [1] class [System.Core]System.Linq.IQueryable`1<class LINQtoLDAP.User> res, [2] class [System.Core]System.Linq.Expressions.ParameterExpression CS$0$0000, [3] class [System.Core]System.Linq.Expressions.Expression[] CS$0$0001, [4] class [System.Core]System.Linq.Expressions.ParameterExpression[] CS$0$0002) IL_0000: nop IL_0001: newobj instance void LINQtoLDAP.DemoDataContext::.ctor() IL_0006: stloc.0 IL_0007: ldloc.0 IL_0008: callvirt instance class [System.Data.Linq]System.Data.Linq.Table`1<class LINQtoLDAP.User> LINQtoLDAP.DemoDataContext::get_Users() IL_000d: ldtoken LINQtoLDAP.User IL_0012: call class [mscorlib]System.Type [mscorlib]System.Type::GetTypeFromHandle(valuetype [mscorlib]System.RuntimeTypeHandle) IL_0017: ldstr "usr" IL_001c: call class [System.Core]System.Linq.Expressions.ParameterExpression [System.Core]System.Linq.Expressions.Expression::Parameter(class [mscorlib]System.Type, string) IL_0021: stloc.2 IL_0022: ldloc.2 IL_0023: ldtoken method instance string LINQtoLDAP.User::get_Name() IL_0028: call class [mscorlib]System.Reflection.MethodBase [mscorlib]System.Reflection.MethodBase::GetMethodFromHandle(valuetype [mscorlib]System.RuntimeMethodHandle) IL_002d: castclass [mscorlib]System.Reflection.MethodInfo IL_0032: call class [System.Core]System.Linq.Expressions.MemberExpression [System.Core]System.Linq.Expressions.Expression::Property(class [System.Core]System.Linq.Expressions.Expression, class [mscorlib]System.Reflection.MethodInfo) IL_0037: ldtoken method instance bool [mscorlib]System.String::Contains(string) IL_003c: call class [mscorlib]System.Reflection.MethodBase [mscorlib]System.Reflection.MethodBase::GetMethodFromHandle(valuetype [mscorlib]System.RuntimeMethodHandle) IL_0041: castclass [mscorlib]System.Reflection.MethodInfo IL_0046: ldc.i4.1 IL_0047: newarr [System.Core]System.Linq.Expressions.Expression IL_004c: stloc.3 IL_004d: ldloc.3 IL_004e: ldc.i4.0 IL_004f: ldstr "Bart" IL_0054: ldtoken [mscorlib]System.String IL_0059: call class [mscorlib]System.Type [mscorlib]System.Type::GetTypeFromHandle(valuetype [mscorlib]System.RuntimeTypeHandle) IL_005e: call class [System.Core]System.Linq.Expressions.ConstantExpression [System.Core]System.Linq.Expressions.Expression::Constant(object, class [mscorlib]System.Type) IL_0063: stelem.ref IL_0064: ldloc.3 IL_0065: call class [System.Core]System.Linq.Expressions.MethodCallExpression [System.Core]System.Linq.Expressions.Expression::Call(class [System.Core]System.Linq.Expressions.Expression, class [mscorlib]System.Reflection.MethodInfo, class [System.Core]System.Linq.Expressions.Expression[]) IL_006a: ldc.i4.1 IL_006b: newarr [System.Core]System.Linq.Expressions.ParameterExpression IL_0070: stloc.s CS$0$0002 IL_0072: ldloc.s CS$0$0002 IL_0074: ldc.i4.0 IL_0075: ldloc.2 IL_0076: stelem.ref IL_0077: ldloc.s CS$0$0002 IL_0079: call class [System.Core]System.Linq.Expressions.Expression`1<!!0> [System.Core]System.Linq.Expressions.Expression::Lambda<class [System.Core]System.Linq.Func`2<class LINQtoLDAP.User,bool>>(class [System.Core]System.Linq.Expressions.Expression, class [System.Core]System.Linq.Expressions.ParameterExpression[]) IL_007e: call class [System.Core]System.Linq.IQueryable`1<!!0> [System.Core]System.Linq.Queryable::Where<class LINQtoLDAP.User>(class [System.Core]System.Linq.IQueryable`1<!!0>, class [System.Core]System.Linq.Expressions.Expression`1<class [System.Core]System.Linq.Func`2<!!0,bool>>) IL_0083: stloc.1 IL_0084: ret } // end of method Program::Main

Whoosh, pretty scary isn't it? No worries, again it's plain simple :-). This piece of code shows how lazy the C# compiler was (well, sort of) because it didn't translate the code of the query to IL at all; instead it dumped its expression tree in code (which, however, takes another big implementation effort of course). This means that the tree parsing will be up to the query provider implementation, for example to translate it to SQL (or in our case to LDAP). Let's take a quick look:

  • IL_0008 represents the from clause on line 5; it gets the users table back (from usr in ctx.Users).
  • IL_001c creates a ParameterExpression which takes a parameter from type LINQtoLDAP.User (line IL_000d gets the token for the type while IL_0012 converts it to a Type instance, this is standard output for a typeof(T) instruction) and a parameter name ("usr"). Essentially, this is the part of line 5 indicated as bold: from usr in ctx.Users. The expression is kept in slot 2 of the local variables on line IL_0021.
  • IL_0032 creates a MemberExpression that takes two parameters. The first parameter comes from lne IL_0022 where we stored the ParameterExpression on the stack; the second one comes from IL_0028 (indirectly after a cast on line IL_002d) where we get a MethodInfo (reflection) object for the get_Name property getter. Basically this is the translation for where usr.Name.Contains("Bart").
  • IL_0065 then creates a MethodCallExpression that takes three parameters. This is the translation of where usr.Name.Contains("Bart"). An overview of the parameters:
    • The first one refers to the MemberExpression created above.
    • The second one is a MethodInfo object that represent the method to be called; this is constructed in lines IL_0037 to IL_0041.
    • The last one is an array of parameters that needs to be passed to the method call at runtime. This array is constructed in line IL_0047 with a dimension of 1 (IL_0046). The first element of the array is supplied in lines IL_004e to IL_0063 where a ConstantExpression is created for the literal "Bart" in where usr.Name.Contains("Bart").
  • IL_0079 creates a lambda expression representing a Func<LINQtoLDAP.User, bool> predicate delegate, based on two parameters:
    • An expression representing the body of the lambda; which is the MethodCallExpression from above.
    • A parameter, which is the ParameterExpression from above.
  • IL_007e finally calls System.Linq.Queryable.Where which is a factory method to create yet another series of nodes in the expression tree, representing a Where method call. Here the IQueryable<T> instance is passed in and ultimately this will result in a call being made to the IQueryable's methods to parse the tree (see future posts).

At runtime, you can inspect the expression tree which is represented in variable res:

In here, I've only shown a few levels in the tree, up to the Where method call. The tree looks like this (simplified):

  • [System.Linq.Expressions.MethodCallExpression] = {Table(dbo.Users).Where(usr => usr.Name.Contains("Bart"))}
    • Method = {System.Linq.IQueryable`1[LINQtoLDAP.User] Where[User](System.Linq.IQueryable`1[LINQtoLDAP.User], System.Linq.Expressions.Expression`1[System.Linq.Func`2[LINQtoLDAP.User,System.Boolean]])}
    • Object = null
    • Arguments[0] = [System.Linq.Expressions.ConstantExpression] = {Table(dbo.Users)}
    • Arguments[1] = [System.Linq.Expressions.UnaryExpression] = {usr => usr.Name.Contains("Bart")}
      • Operand = [System.Linq.Expressions.LambdaExpression] = {usr => usr.Name.Contains("Bart")}
        • Body = [System.Linq.Expressions.MethodCallExpression] = {usr.Name.Contains("Bart")}
          • Method = {Boolean Contains(System.String)}
          • Object = [System.Linq.Expressions.MemberExpression] = {usr.Name}
          • Arguments[0] = [System.Linq.Expressions.ConstantExpression] = {"Bart"}

The picture below (click to enlarge) shows the expression tree (partially!) in the debugger:

 

Notice that the resulting tree altready contains some parsing results, such as Table(dbo.Users), which have been created by the query provider for LINQ-to-SQL at runtime by inspecting various attributes (such as TableAttribute applied on the User class). Ultimately, the provide is capable of translating the whole tree into a SQL statement:

SELECT [t0].[ID], [t0].[Name]
FROM [dbo].[Users] AS [t0]
WHERE [t0].[Name] LIKE @p0

which is finally sent to the database based on project configuration properties that were auto-generated (app.config):

<?xml version="1.0" encoding="utf-8" ?> <configuration> <configSections> </configSections> <connectionStrings> <add name="LINQtoLDAP.Properties.Settings.msdbConnectionString" connectionString="Data Source=.\SQLEXPRESS;Initial Catalog=msdb;Integrated Security=True" providerName="System.Data.SqlClient" /> </connectionStrings> </configuration>

To conclude this discussion, always think of IQueryable<T> implementations as tree parsers. From the compiler's point of view, IL code to create a tree is generated. From a provider's point of view, the CreateQuery method will be called, given that expression tree, for further processing, ultimately yielding a translation into a domain-specific query language like SQL or XPath/XQuery or LDAP or WQL or CAML or ... you name it. We'll focus on creating a query provider for LDAP in the next posts that will do similar things as LINQ-to-SQL. Time to refresh your tree traversal algorithms :-).

Read on ... The IQueryable tales - LINQ to LDAP - Part 2: Getting started with IQueryable<T>

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Filed under: ,

Comments

# The IQueryable tales - LINQ to LDAP - Part 2: Getting started with IQueryable<T>

Friday, April 06, 2007 5:45 PM by B# .NET Blog

Introduction Welcome back to the LINQ-to-LDAP series. So far, we've been discussing: Part 0: Introduction

# New and Notable 156

Saturday, April 07, 2007 5:50 AM by Sam Gentile

A light day out there for the Holiday weekend. LINQ Bart has another series going with The IQueryable

# re: The IQueryable tales - LINQ to LDAP - Part 1: Key concepts

Saturday, April 07, 2007 12:24 PM by Roger Jennings

# LINQ to LDAP - Implementation Details

Saturday, April 07, 2007 1:04 PM by ((Research + Development) - Sleep) > 24

Today, Sam Gentile noted a series of posts by Bart De Smet describing (in great detail) how LINQ queries

# The IQueryable tales - LINQ to LDAP - Part 3: Why do we need entities?

Saturday, April 07, 2007 6:31 PM by B# .NET Blog

Introduction Welcome back to the LINQ-to-LDAP series. So far, we've been discussing: Part 0: Introduction

# New "Orcas" Language Feature: Lambda Expressions

Sunday, April 08, 2007 4:22 PM by ScottGu's Blog

Last month I started a series of posts covering some of the new VB and C# language features that are

# New "Orcas" Language Feature: Lambda Expressions

Sunday, April 08, 2007 4:39 PM by BusinessRx Reading List

Last month I started a series of posts covering some of the new VB and C# language features that are

# New "Orcas" Language Feature: Lambda Expressions

Sunday, April 08, 2007 4:40 PM by ASP.NET

Last month I started a series of posts covering some of the new VB and C# language features that are

# The IQueryable tales - LINQ to LDAP - Part 0: Introduction

Monday, April 09, 2007 6:35 PM by B# .NET Blog

Here we are again for some cool LINQ stuff. In the past I've been blogging on C# 3.0 language innovation

# 新Orcas语言特性:Lambda表达式

Monday, April 09, 2007 10:36 PM by shoutor

什么是Lambda表达式?Lambda表达式为编写匿名方法提供了更简明的函数式的句法,但结果却在编写LINQ查询表达式时变得极其有用,因为它们提供了一个非常紧凑的而且类安全的方式来编写可以当作参数来传递,在以后作运算的函数。

# 新Orcas语言特性:Lambda表达式

Monday, April 09, 2007 10:38 PM by shoutor

什么是Lambda表达式?Lambda表达式为编写匿名方法提供了更简明的函数式的句法,但结果却在编写LINQ查询表达式时变得极其有用,因为它们提供了一个非常紧凑的而且类安全的方式来编写可以当作参数来传递,在以后作运算的函数。

# The IQueryable tales - LINQ to LDAP - Part 4: Parsing and executing queries

Tuesday, April 10, 2007 3:15 PM by B# .NET Blog

Introduction Welcome back to the LINQ-to-LDAP series. So far, we've been discussing: Part 0: Introduction

# Nueva caracter??stica de "Orcas": Expresiones Lambda &laquo; Thinking in .NET

# The IQueryable tales - LINQ to LDAP - Part 5: Supporting updates

Tuesday, April 10, 2007 6:29 PM by B# .NET Blog

Introduction Welcome back to the LINQ-to-LDAP series. So far, we've been discussing: Part 0: Introduction

# Coming soon - The return of IQueryable<T> - LINQ to SharePoint

Friday, April 13, 2007 4:09 PM by B# .NET Blog

Earlier this week, "The IQueryable Tales" were published on my blog, with great success. This series

# Building Custom LINQ Enabled Data Providers using IQueryable<T>

Friday, April 20, 2007 6:16 AM by Tom's MSDN Belux Corner

Bart De Smet wrote a hands-on tutorial that explains quite in-depth how one can build a custom data provider

# New "Orcas" Language Feature: Lambda Expressions

Tuesday, May 08, 2007 1:22 AM by Tyrannosaurus Rex

Last month I started a series of posts covering some of the new VB and C# language features that are

# Community Convergence XXVII

Sunday, May 13, 2007 11:13 PM by Charlie Calvert's Community Blog

Welcome to the 27th Community Convergence. I use this column to keep you informed of events in the C#

# 新Orcas语言特性:Lambda表达式。

Sunday, June 24, 2007 9:38 AM by 勤勤同学

随VS 2005发布的C#2.0引进了匿名方法的概念,允许在预期代理(delegate)值的地方用“行内(in-line)”代码块(code blocks)来做替代。

# The IQueryable tales - LINQ to LDAP - Part 5: Supporting updates

Friday, July 27, 2007 5:42 AM by B# .NET Blog

Introduction Welcome back to the LINQ-to-LDAP series. So far, we&#39;ve been discussing: Part 0: Introduction

# LINQ to Active Directory (formerly known as LINQ to LDAP) is here

Sunday, November 25, 2007 11:23 PM by B# .NET Blog

Within a few seconds from now I&#39;ll hit the &quot;Publish This Project&quot; button in CodePlex. Back

# LINQ to Active Directory (formerly known as LINQ to LDAP) is here

Sunday, November 25, 2007 11:23 PM by Elan Hasson's Favorite Blogs

Within a few seconds from now I&#39;ll hit the &quot;Publish This Project&quot; button in CodePlex. Back

# LINQ to Active Directory (formerly known as LINQ to LDAP) is here

Friday, December 21, 2007 7:44 AM by Developer Blogs

Within a few seconds from now I&#39;ll hit the &quot;Publish This Project&quot; button in CodePlex. Back

# .NET3.5?????????,Lambda????????? | Richie's Blog

Monday, January 21, 2008 8:57 PM by .NET3.5?????????,Lambda????????? | Richie's Blog

Pingback from  .NET3.5?????????,Lambda????????? | Richie's Blog

# [转贴].NET3.5新特性,Lambda表达式

Wednesday, February 13, 2008 5:03 AM by 菩提树下的杨过

【原文地址】New

# New and Notable 156

A light day out there for the Holiday weekend. LINQ Bart has another series going with The IQueryable

# New and Notable 156

Tuesday, December 02, 2008 11:01 AM by Sam Gentile's Blog

A light day out there for the Holiday weekend. LINQ Bart has another series going with The IQueryable Tales - LINQ to LDAP. Part 1 is Key Concepts and Part 2 is Getting Started with IQueryable . CLR Jason continues Disassembling .NET with Appendix B

# New and Notable 156

Tuesday, December 02, 2008 7:43 PM by Sam Gentile's Blog

A light day out there for the Holiday weekend. LINQ Bart has another series going with The IQueryable Tales - LINQ to LDAP. Part 1 is Key Concepts and Part 2 is Getting Started with IQueryable . CLR Jason continues Disassembling .NET with Appendix B

# ???Orcas???????????????Lambda????????? | A18??????

Monday, December 28, 2009 4:56 PM by ???Orcas???????????????Lambda????????? | A18??????

Pingback from  ???Orcas???????????????Lambda?????????  | A18??????

# ???Orcas???????????????Lambda????????? - Java??????

Thursday, September 02, 2010 6:44 AM by ???Orcas???????????????Lambda????????? - Java??????

Pingback from  ???Orcas???????????????Lambda????????? - Java??????

# C# 3.0 &#8211; LINQ | Eugene&#039;s blog

Tuesday, March 12, 2013 9:44 AM by C# 3.0 – LINQ | Eugene's blog

Pingback from  C# 3.0 &#8211; LINQ | Eugene&#039;s blog