老趙點滴 - 追求編程之美 先做人，再做技術人員，最后做程序員。打造國內最好的.NET技術博客。

談到使用表達式樹作為key進行緩存，您腦海中最早浮現出來的解決方案是什么？老趙看來，大部分朋友的第一反應自然就是將作為key的表達式樹，使用一定規則生成一個字符串。簡而言之，這個生成字符串的規則F需要能夠保證：

1. 在同一個緩存空間內，同樣的表達式樹能夠生成相同的字符串。
2. 在同一個緩存空間內，不同的表達式樹生成不同的字符串。

似乎有些羅嗦，朋友們明白便是。其中“在同一個緩存空間”的前提，其實只是放寬了后續要求的條件。因為在不同的緩存空間內，即使不同的表達式樹生成了同樣的字符串，它們也不會沖突；同理，不同緩存空間內的相同表達式樹，也不一定非要得到相同的字符串——事實上，不同的緩存空間很可能對于字符串有不同的要求，這一點強求不得。

例如，在上一篇文章的例子中，構建“GetUserByID_100”和“GetUserByName_jeffz”兩個字符串一般已經足夠了。因為我們往往會將它們放在同一個緩存空間中（例如，UserService中的Cache容器），而與其它的緩存空間（例如AdminService）完全隔離。而如果打破了這個限制，那么這樣的字符串生成規則就不夠用了，我們就要設計新的字符串規則（如UserService_GetUserByID_100）。

對于之前的例子來說，構造簡單的“GetUserByID_100”這種字符串已經足夠進行緩存了，不過如果要把一個表達式樹轉化為一個字符串，并不是一件容易的事情。有朋友在我上一篇的文章后面回復到“直接用Expression<T>的ToString方法不行么？”答案是顯而易見的（希望朋友們能夠少猜測，多實踐），例如：

Expression<Func<int, int>> exp1 = i => i;
Expression<Func<long, long>> exp2 = i => i;

Console.WriteLine(exp1.ToString());
Console.WriteLine(exp2.ToString());

您會發現兩個明顯不同的表達式樹ToString后得到了同樣的內容。表達式樹的ToString方法是丟失信息的。例如，如果表達式樹中涉及方法調用，那么ToString也只會包含方法名，而無法表現出方法所屬的類，以及它的返回值。如果要把一個表達式樹完整地生成字符串，自然要用到ExpressionVisitor。我們這里把轉化用的類稱為是SimpleKeyBuilder：

public class SimpleKeyBuilder : ExpressionVisitor
{
    public string Build(Expression exp)
    {
        this.m_builder = new StringBuilder();
        this.Visit(exp);
        return this.Key;
    }

    public string Key { get { return this.m_builder.ToString(); } }

    private StringBuilder m_builder;
}

Visit方法的訪問是一個遞歸的過程，其中會調用不同的VisitXxx方法，而各VisitXxx方法又會再次調用Visit方法，最終遍歷整個表達式樹，而我們要做的，就是在遍歷時記錄足夠的信息，使得兩個表達式樹“當且僅當”完全相同時才生成同樣的字符串。嗯？“在同一緩存空間內”不見了？沒錯，為了保證解決方案的通用性，我們在這里假設緩存區間只有一個。

值得一提的是，整個遍歷操作形成了一個完整的遍歷序列，而這個序列有個重要的特點：“只有結構完全相同的兩個表達式樹，其各節點的遍歷序列完全相同，反之亦然”。請注意，“結構完全相同”是“遍歷序列相同”的“充分并必要條件”，但是“結構完全相同”是“完全相同”的“必要但不充分條件”。因此“遍歷序列相同”并不能保證“完全相同”，這是因為ExpressionVisitor在遍歷表達式樹時只關注其結構，而不關注其細節。例如某個參數的類型，某個常量的值，都不屬于“結構”的范疇。因此我們在生成字符串時，需要記錄的并不只是遍歷的路徑，還需要包括各詳細信息。

方便起見，我們先準備一些輔助方法，它們會將“各信息”一一放入StringBuilder中：

protected virtual SimpleKeyBuilder Accept(int value)
{
    this.m_builder.Append(value).Append("|");
    return this;
}

protected virtual SimpleKeyBuilder Accept(bool value)
{
    this.m_builder.Append(value ? "1|" : "0|");
    return this;
}

protected virtual SimpleKeyBuilder Accept(Type type)
{
    this.m_builder.Append(type == null ? "null" : type.FullName).Append("|");
    return this;
}

protected virtual SimpleKeyBuilder Accept(MemberInfo member)
{
    if (member == null)
    {
        this.m_builder.Append("null|");
        return this;
    }

    return this.Accept(member.DeclaringType).Accept(member.Name);
}

protected virtual SimpleKeyBuilder Accept(object value)
{
    this.m_builder.Append(value == null ? "null" : value.ToString()).Append("|");
    return this;
}

然后再遍歷每個節點的時候，我們將數據不斷地推入：

protected override Expression Visit(Expression exp)
{
    if (exp == null) return exp;

    this.Accept("$b$").Accept((int)exp.NodeType).Accept(exp.Type);
    var result = base.Visit(exp);
    this.Accept("$e$");

    return result;
}

protected override Expression VisitBinary(BinaryExpression b)
{
    this.Accept(b.IsLifted).Accept(b.IsLiftedToNull).Accept(b.Method);
    return base.VisitBinary(b);
}

protected override Expression VisitConstant(ConstantExpression c)
{
    this.Accept(c.Value);
    return base.VisitConstant(c);
}

protected override Expression VisitMemberAccess(MemberExpression m)
{
    this.Accept(m.Member);
    return base.VisitMemberAccess(m);
}

...

完整的代碼不止如此，雖然我們不需要覆蓋（override）所有ExpressionVisitor的方法，但是一些必要的元素還是不可或缺的。不過，關鍵之處并不在這里。假設我們的VisitXxx方法已經能夠完整地描述各數據，但是那些Accept方法足夠詳細嗎？答案是否定的，至少之前的代碼便有幾點問題：

1. 在描述一個Type時，FullName提供的信息完整嗎？是否需要AssemblyQualifiedName？（這點請朋友們自行思考，或者一起討論一下）。
2. 在描述一個MemberInfo時，難道只記錄它的DeclaringType和Name就夠了嗎？
3. 在描述一個Object時，會使用ToString方法來進行記錄。

顯而易見，第三個問題是無法滿足要求的。因此，如果您需要在正式場合使用這個方法，就必須根據您自己的需求來修改一下這方面的問題——例如，使用Serialize？亦或是，約定在此出現的每個相同類型的對象，它們的ToString方法都進行了合適地重載。

如果您的“嗅覺”比較靈敏，應該已經發現這個解決方案的缺點了：那就是字符串會特別龐大。這點并非無法改進，例如您可以把一些重復的，占用數據量大的信息替換成數據量小的信息——其實就是傳統的進行數據壓縮的算法。不過這方面編程相對較為復雜，且屬于優化階段而不能說明解決方案的真正思路，因此這就留給朋友們作為練習吧。

如果您感興趣的話，還可以看一下http://code.msdn.microsoft.com/exprserialization，它提供了表達式樹的完整的序列化功能，它可以把一個表達式樹對象與XML進行雙向轉化。不過其字符串體積也無可避免的龐大，誰讓表達式樹天生就那么復雜呢？

當然，如之前所說，Key的生成規則與緩存的劃分密切相關。換句話說，如果您能在項目里對緩存空間進行適當的劃分，那么在這樣的前提下您也可以使用“不那么詳細”的生成規則，這有可能會進一步壓縮字符串的體積。

實現了SimpleKeyBuilder，那么SimpleKeyCache的編寫自然易如反掌，不加贅述：

public class SimpleKeyCache<T> : IExpressionCache<T> where T : class
{
    private ReaderWriterLockSlim m_rwLock = new ReaderWriterLockSlim();
    private Dictionary<string, T> m_storage = new Dictionary<string, T>();

    public T Get(Expression key, Func<Expression, T> creator)
    {
        T value;
        string cacheKey = new SimpleKeyBuilder().Build(key);

        this.m_rwLock.EnterReadLock();
        try
        {
            if (this.m_storage.TryGetValue(cacheKey, out value))
            {
                return value;
            }
        }
        finally
        {
            this.m_rwLock.ExitReadLock();
        }

        this.m_rwLock.EnterWriteLock();
        try
        {
            if (this.m_storage.TryGetValue(cacheKey, out value))
            {
                return value;
            }

            value = creator(key);
            this.m_storage.Add(cacheKey, value);
            return value;
        }
        finally
        {
            this.m_rwLock.ExitWriteLock();
        }
    }
}

那么這個解決方案的時間復雜度是多少呢？假設表達式樹有m個節點，緩存里有n個對象。那么從理論上說，構造一個Key的時間復雜度是O(m)，而通過Key從字典里進行查詢的時間復雜度是O(1)，因此該解決方案的時間復雜度是O(m)。

不過這是個理論值，其實際的結果呢？大家不妨思考一下，老趙在介紹完全部5種解決方案之后會單獨開篇討論一下這方面的問題。

完整代碼下載：http://code.msdn.microsoft.com/ExpressionCache

相關文章：

• 談表達式樹的緩存（1）：引言
• 談表達式樹的緩存（3）：使用前綴樹
• 談表達式樹的緩存（4）：使用二叉搜索樹（AVL樹）
• 談表達式樹的緩存（5）：引入散列值
• 談表達式樹的緩存（6）：五種緩存方式的性能比較
• 談表達式樹的緩存（7）：五種緩存方式的總體分析及改進方案