概述

在.NET Framework 3.5中提供了LINQ 支持后，LINQ就以其強(qiáng)大而優(yōu)雅的編程方式贏得了開(kāi)發(fā)人員的喜愛(ài)，而各種LINQ Provider更是滿天飛，如LINQ to NHibernate、LINQ to Google等，大有“一切皆LINQ”的趨勢(shì)。LINQ本身也提供了很好的擴(kuò)展性，使得我們可以輕松的編寫屬于自己的LINQ Provider。

本文為打造自己的LINQ Provider系列文章第一篇，主要介紹表達(dá)式目錄樹(shù)（Expression Tree）的相關(guān)知識(shí)。

認(rèn)識(shí)表達(dá)式目錄樹(shù)

究竟什么是表達(dá)式目錄樹(shù)（Expression Tree），它是一種抽象語(yǔ)法樹(shù)或者說(shuō)它是一種數(shù)據(jù)結(jié)構(gòu)，通過(guò)解析表達(dá)式目錄樹(shù)，可以實(shí)現(xiàn)我們一些特定的功能（后面會(huì)說(shuō)到），我們首先來(lái)看看如何構(gòu)造出一個(gè)表達(dá)式目錄樹(shù)，最簡(jiǎn)單的方法莫過(guò)于使用Lambda表達(dá)式，看下面的代碼：

Expression<Func<int, int, int>> expression = (a, b) => a * b + 2;

在我們將Lambda表達(dá)式指定給Expression<TDelegate>類型的變量（參數(shù)）時(shí)，編譯器將會(huì)發(fā)出生成表達(dá)式目錄樹(shù)的指令，如上面這段代碼中的Lambda表達(dá)式(a, b) => a * b + 2將創(chuàng)建一個(gè)表達(dá)式目錄樹(shù)，它表示的是一種數(shù)據(jù)結(jié)構(gòu)，即我們把一行代碼用數(shù)據(jù)結(jié)構(gòu)的形式表示了出來(lái)，具體來(lái)說(shuō)最終構(gòu)造出來(lái)的表達(dá)式目錄樹(shù)形狀如下圖所示：

這里每一個(gè)節(jié)點(diǎn)都表示一個(gè)表達(dá)式，可能是一個(gè)二元運(yùn)算，也可能是一個(gè)常量或者參數(shù)等，如上圖中的ParameterExpression就是一個(gè)參數(shù)表達(dá)式，ConstantExpression是一個(gè)常量表達(dá)式，BinaryExpression是一個(gè)二元表達(dá)式。我們也可以在Visual Studio中使用Expression Tree Visualizer來(lái)查看該表達(dá)式目錄樹(shù)：

查看結(jié)果如下圖所示：

這里說(shuō)一句，Expression Tree Visualizer可以從MSDN Code Gallery上的LINQ Sample中得到?，F(xiàn)在我們知道了表達(dá)式目錄樹(shù)的組成，來(lái)看看.NET Framework到底提供了哪些表達(dá)式？如下圖所示：

它們都繼承于抽象的基類Expression，而泛型的Expression<TDelegate>則繼承于LambdaExpression。在Expression類中提供了大量的工廠方法，這些方法負(fù)責(zé)創(chuàng)建以上各種表達(dá)式對(duì)象，如調(diào)用Add()方法將創(chuàng)建一個(gè)表示不進(jìn)行溢出檢查的算術(shù)加法運(yùn)算的BinaryExpression對(duì)象，調(diào)用Lambda方法將創(chuàng)建一個(gè)表示lambda 表達(dá)式的LambdaExpression對(duì)象，具體提供的方法大家可以查閱MSDN。上面構(gòu)造表達(dá)式目錄樹(shù)時(shí)我們使用了Lambda表達(dá)式，現(xiàn)在我們看一下如何通過(guò)這些表達(dá)式對(duì)象手工構(gòu)造出一個(gè)表達(dá)式目錄樹(shù)，如下代碼所示：

static void Main(string[] args)
{
    ParameterExpression paraLeft = Expression.Parameter(typeof(int), "a");
    ParameterExpression paraRight = Expression.Parameter(typeof(int), "b");

    BinaryExpression binaryLeft = Expression.Multiply(paraLeft, paraRight);
    ConstantExpression conRight = Expression.Constant(2, typeof(int));

    BinaryExpression binaryBody = Expression.Add(binaryLeft, conRight);

    LambdaExpression lambda = 
        Expression.Lambda<Func<int, int, int>>(binaryBody, paraLeft, paraRight);

    Console.WriteLine(lambda.ToString());

    Console.Read();
}

這里構(gòu)造的表達(dá)式目錄樹(shù)，仍然如下圖所示：

運(yùn)行這段代碼，看看輸出了什么：

可以看到，通過(guò)手工構(gòu)造的方式，我們確實(shí)構(gòu)造出了同前面一樣的Lambda表達(dá)式。對(duì)于一個(gè)表達(dá)式目錄樹(shù)來(lái)說(shuō)，它有幾個(gè)比較重要的屬性：

Body：指表達(dá)式的主體部分；

Parameters：指表達(dá)式的參數(shù)；

NodeType：指表達(dá)式的節(jié)點(diǎn)類型，如在上面的例子中，它的節(jié)點(diǎn)類型是Lambda；

Type：指表達(dá)式的靜態(tài)類型，在上面的例子中，Type為Fun<int,int,int>。

在Expression Tree Visualizer中，我們可以看到表達(dá)式目錄樹(shù)的相關(guān)屬性，如下圖所示：

表達(dá)式目錄樹(shù)與委托

大家可能經(jīng)?？吹饺缦逻@樣的語(yǔ)言，其中第一句是直接用Lambda表達(dá)式來(lái)初始化了Func委托，而第二句則使用Lambda表達(dá)式來(lái)構(gòu)造了一個(gè)表達(dá)式目錄樹(shù)，它們之間的區(qū)別是什么呢？

static void Main(string[] args)
{
    Func<int, int, int> lambda = (a, b) => a + b * 2;

    Expression<Func<int, int, int>> expression = (a, b) => a + b * 2;
} 

其實(shí)看一下IL就很明顯，其中第一句直接將Lambda表達(dá)式直接編譯成了IL，如下代碼所示：

.method private hidebysig static void  Main(string[] args) cil managed
{
  .entrypoint
  .maxstack  3
  .locals init ([0] class [System.Core]System.Func`3<int32,int32,int32> lambda)
  IL_0000:  nop
  IL_0001:  ldsfld     class [System.Core]System.Func`3<int32,int32,int32> 
                        TerryLee.LinqToLiveSearch.Program::'CS$<>9__CachedAnonymousMethodDelegate1'
  IL_0006:  brtrue.s   IL_001b
  IL_0008:  ldnull
  IL_0009:  ldftn      int32 TerryLee.LinqToLiveSearch.Program::'<Main>b__0'(int32,
                                                                             int32)
  IL_000f:  newobj     instance void class [System.Core]System.Func`3<int32,int32,int32>::.ctor(object,
                                                                                                native int)
  IL_0014:  stsfld     class [System.Core]System.Func`3<int32,int32,int32> 
                    TerryLee.LinqToLiveSearch.Program::'CS$<>9__CachedAnonymousMethodDelegate1'
  IL_0019:  br.s       IL_001b
  IL_001b:  ldsfld     class [System.Core]System.Func`3<int32,int32,int32> 
                    TerryLee.LinqToLiveSearch.Program::'CS$<>9__CachedAnonymousMethodDelegate1'
  IL_0020:  stloc.0
  IL_0021:  ret
}

而第二句，由于告訴編譯器是一個(gè)表達(dá)式目錄樹(shù)，所以編譯器會(huì)分析該Lambda表達(dá)式，并生成表示該Lambda表達(dá)式的表達(dá)式目錄樹(shù)，即它與我們手工創(chuàng)建表達(dá)式目錄樹(shù)所生成的IL是一致的，如下代碼所示，此處為了節(jié)省空間省略掉了部分代碼：

.method private hidebysig static void  Main(string[] args) cil managed
{
  .entrypoint
  .maxstack  4
  .locals init ([0] class [System.Core]System.Linq.Expressions.Expression`1<
                class [System.Core]System.Func`3<int32,int32,int32>> expression,
           [1] class [System.Core]System.Linq.Expressions.ParameterExpression CS$0$0000,
           [2] class [System.Core]System.Linq.Expressions.ParameterExpression CS$0$0001,
           [3] class [System.Core]System.Linq.Expressions.ParameterExpression[] CS$0$0002)
  IL_0000:  nop
  IL_0001:  ldtoken    [mscorlib]System.Int32
  IL_0006:  call       class [mscorlib]System.Type [mscorlib]System.Type::GetTypeFromHandle(...)
  IL_000b:  ldstr      "a"
  IL_0010:  call       class [System.Core]System.Linq.Expressions.ParameterExpression 
                        [System.Core]System.Linq.Expressions.Expression::Parameter(
                        class [mscorlib]System.Type,

  IL_0038:  call    class [mscorlib]System.Type [mscorlib]System.Type::GetTypeFromHandle()
  IL_003d:  call    class [System.Core]System.Linq.Expressions.ConstantExpression 
                    [System.Core]System.Linq.Expressions.Expression::Constant(object,
                    class [mscorlib]System.Type)
  IL_0042:  call    class [System.Core]System.Linq.Expressions.BinaryExpression 
                    [System.Core]System.Linq.Expressions.Expression::Multiply(class [System.Core]System.Linq.Expressions.Expression,
                    class [System.Core]System.Linq.Expressions.Expression)
  IL_0047:  call    class [System.Core]System.Linq.Expressions.BinaryExpression
                    [System.Core]System.Linq.Expressions.Expression::Add(class [System.Core]System.Linq.Expressions.Expression,
                    class [System.Core]System.Linq.Expressions.Expression)
  IL_004c:  ldc.i4.2
  IL_004d:  newarr     [System.Core]System.Linq.Expressions.ParameterExpression
}

現(xiàn)在相信大家都看明白了，這里講解它們的區(qū)別主要是為了加深大家對(duì)于表達(dá)式目錄樹(shù)的區(qū)別。

執(zhí)行表達(dá)式目錄樹(shù)

前面已經(jīng)可以構(gòu)造出一個(gè)表達(dá)式目錄樹(shù)了，現(xiàn)在看看如何去執(zhí)行表達(dá)式目錄樹(shù)。我們需要調(diào)用Compile方法來(lái)創(chuàng)建一個(gè)可執(zhí)行委托，并且調(diào)用該委托，如下面的代碼：

static void Main(string[] args)
{
    ParameterExpression paraLeft = Expression.Parameter(typeof(int), "a");
    ParameterExpression paraRight = Expression.Parameter(typeof(int), "b");

    BinaryExpression binaryLeft = Expression.Multiply(paraLeft, paraRight);
    ConstantExpression conRight = Expression.Constant(2, typeof(int));

    BinaryExpression binaryBody = Expression.Add(binaryLeft, conRight);

    Expression<Func<int, int, int>> lambda = 
        Expression.Lambda<Func<int, int, int>>(binaryBody, paraLeft, paraRight);

    Func<int, int, int> myLambda = lambda.Compile();

    int result = myLambda(2, 3);
    Console.WriteLine("result:" + result.ToString());

    Console.Read();
}

運(yùn)行后輸出的結(jié)果：

這里我們只要簡(jiǎn)單的調(diào)用Compile方法就可以了，事實(shí)上在.NET Framework中是調(diào)用了一個(gè)名為ExpressionCompiler的內(nèi)部類來(lái)做表達(dá)式目錄樹(shù)的執(zhí)行（注意此處的Compiler不等同于編譯器的編譯）。另外，只能執(zhí)行表示Lambda表達(dá)式的表達(dá)式目錄樹(shù)，即LambdaExpression或者Expression<TDelegate>類型。如果表達(dá)式目錄樹(shù)不是表示Lambda表達(dá)式，需要調(diào)用Lambda方法創(chuàng)建一個(gè)新的表達(dá)式。如下面的代碼：

static void Main(string[] args)
{
    BinaryExpression body = Expression.Add(
        Expression.Constant(2),
        Expression.Constant(3));

    Expression<Func<int>> expression = 
        Expression.Lambda<Func<int>>(body, null);

    Func<int> lambda = expression.Compile();

    Console.WriteLine(lambda());
}

訪問(wèn)與修改表達(dá)式目錄樹(shù)

在本文一開(kāi)始我就說(shuō)過(guò)， 通過(guò)解析表達(dá)式目錄樹(shù)，我們可以實(shí)現(xiàn)一些特定功能，既然要解析表達(dá)式目錄樹(shù)，對(duì)于表達(dá)式目錄樹(shù)的訪問(wèn)自然是不可避免的。在.NET Framework中，提供了一個(gè)抽象的表達(dá)式目錄樹(shù)訪問(wèn)類ExpressionVisitor，但它是一個(gè)internal的，我們不能直接訪問(wèn)。幸運(yùn)的是，在MSDN中微軟給出了ExpressionVisitor類的實(shí)現(xiàn)，我們可以直接拿來(lái)使用。該類是一個(gè)抽象類，微軟旨在讓我們?cè)诩蒃xpressionVisitor的基礎(chǔ)上，實(shí)現(xiàn)自己的表達(dá)式目錄樹(shù)訪問(wèn)類?，F(xiàn)在我們來(lái)看簡(jiǎn)單的表達(dá)式目錄樹(shù)：

static void Main(string[] args)
{
    Expression<Func<int, int, int>> lambda = (a, b) => a + b * 2;

    Console.WriteLine(lambda.ToString());
} 

輸出后為：

現(xiàn)在我們想要修改表達(dá)式目錄樹(shù)，讓它表示的Lambda表達(dá)式為(a,b)=>(a - (b * 2))，這時(shí)就需要編寫自己的表達(dá)式目錄樹(shù)訪問(wèn)器，如下代碼所示：

public class OperationsVisitor : ExpressionVisitor
{
    public Expression Modify(Expression expression)
    {
        return Visit(expression);
    }

    protected override Expression VisitBinary(BinaryExpression b)
    {
        if (b.NodeType == ExpressionType.Add)
        {
            Expression left = this.Visit(b.Left);
            Expression right = this.Visit(b.Right);
            return Expression.Subtract(left,right);
        }

        return base.VisitBinary(b);
    }
}

使用表達(dá)式目錄樹(shù)訪問(wèn)器來(lái)修改表達(dá)式目錄樹(shù)，如下代碼所示：

static void Main(string[] args)
{
    Expression<Func<int, int, int>> lambda = (a, b) => a + b * 2;

    var operationsVisitor = new OperationsVisitor();
    Expression modifyExpression = operationsVisitor.Modify(lambda);

    Console.WriteLine(modifyExpression.ToString());
}

運(yùn)行后可以看到輸出：

似乎我們是修改表達(dá)式目錄樹(shù)，其實(shí)也不全對(duì)，我們只是修改表達(dá)式目錄樹(shù)的一個(gè)副本而已，因?yàn)楸磉_(dá)式目錄樹(shù)是不可變的，我們不能直接修改表達(dá)式目錄樹(shù)，看看上面的OperationsVisitor類的實(shí)現(xiàn)大家就知道了，在修改過(guò)程中復(fù)制了表達(dá)式目錄樹(shù)的節(jié)點(diǎn)。

為什么需要表達(dá)式目錄樹(shù)

通過(guò)前面的介紹，相信大家對(duì)于表達(dá)式目錄樹(shù)已經(jīng)有些了解了，還有一個(gè)很重要的問(wèn)題，就是為什么需要表達(dá)式目錄樹(shù)？在本文開(kāi)始時(shí)，就說(shuō)過(guò)通過(guò)解析表達(dá)式目錄樹(shù)，可以實(shí)現(xiàn)我們一些特定的功能，就拿LINQ to SQL為例，看下面這幅圖：

當(dāng)我們?cè)贑#語(yǔ)言中編寫一個(gè)查詢表達(dá)式時(shí)，它將返回一個(gè)IQueryable類型的值，在該類型中包含了兩個(gè)很重要的屬性Expression和Provider，如下面的代碼：

我們編寫的查詢表達(dá)式，將封裝為一種抽象的數(shù)據(jù)結(jié)構(gòu)，這個(gè)數(shù)據(jù)結(jié)構(gòu)就是表達(dá)式目錄樹(shù)，當(dāng)我們?cè)谑褂蒙厦娣祷氐闹禃r(shí)，編譯器將會(huì)以該值所期望的方式進(jìn)行翻譯，這種方式就是由Expression和Provider來(lái)決定?？梢钥吹剑@樣將會(huì)非常的靈活且具有良好的可擴(kuò)展性，有了表達(dá)式目錄樹(shù)，可以自由的編寫自己的Provider，去查詢我們希望的數(shù)據(jù)源。經(jīng)常說(shuō)LINQ為訪問(wèn)各種不同的數(shù)據(jù)源提供了一種統(tǒng)一的編程方式，其奧秘就在這里。然而需要注意的是LINQ to Objects并不需要任何特定的LINQ Provider，因?yàn)樗⒉环g為表達(dá)式目錄樹(shù)，后面會(huì)說(shuō)到這一點(diǎn)。

總結(jié)

本為詳細(xì)介紹了表達(dá)式目錄樹(shù)的相關(guān)知識(shí)，為我們編寫自己的LINQ Provider打下一個(gè)基礎(chǔ)，希望對(duì)于大家有所幫助。查看目前網(wǎng)上的各種lINQ Provider，請(qǐng)?jiān)L問(wèn)萬(wàn)般皆LINQ。

相關(guān)文章：打造自己的LINQ Provider（中）：IQueryable和IQueryProvider