谈表达式树的缓存（2）：由表达式树生成字符串
2009-03-17 00:58 by 老赵, 11145 visits谈到使用表达式树作为key进行缓存，您脑海中最早浮现出来的解决方案是什么？老赵看来，大部分朋友的第一反应自然就是将作为key的表达式树，使用一定规则生成一个字符串。简而言之，这个生成字符串的规则F需要能够保证：
- 在同一个缓存空间内，同样的表达式树能够生成相同的字符串。
- 在同一个缓存空间内，不同的表达式树生成不同的字符串。
似乎有些罗嗦，朋友们明白便是。其中“在同一个缓存空间”的前提，其实只是放宽了后续要求的条件。因为在不同的缓存空间内，即使不同的表达式树生成了同样的字符串，它们也不会冲突；同理，不同缓存空间内的相同表达式树，也不一定非要得到相同的字符串——事实上，不同的缓存空间很可能对于字符串有不同的要求，这一点强求不得。
例如，在上一篇文章的例子中，构建“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方法足够详细吗？答案是否定的，至少之前的代码便有几点问题：
- 在描述一个Type时，FullName提供的信息完整吗？是否需要AssemblyQualifiedName？（这点请朋友们自行思考，或者一起讨论一下）。
- 在描述一个MemberInfo时，难道只记录它的DeclaringType和Name就够了吗？
- 在描述一个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
相关文章：
刚好逛到首页，沙发完再看