我一直在看Roslyn CTP，虽然它解决了与Expression tree API类似的问题，但两者都是不可改变的，但Roslyn以一种完全不同的方式这样做：
Expression节点没有对父节点的引用，使用ExpressionVisitor进行修改，这就是为什么可以重用大部件的原因 .
另一方面，Roslyn的 SyntaxNode 引用了它的父节点，因此所有节点实际上都成为一个无法重用的块 . 提供诸如 Update ， ReplaceNode 等方法以进行修改 .
这到底在哪里？ Document ？ Project ？ ISolution ？ API促进树的逐步更改（而不是按钮向上），但每个步骤是否完整复制？
为什么他们这样做了？我有什么有趣的伎俩吗？
1 回答
更新：这个问题是the subject of my blog on June 8th, 2012 . 谢谢你这个好问题！
好问题 . 我们长期讨论你提出的问题 .
我们希望有一个具有以下特征的数据结构：
不变 .
树的形式 .
从子节点对父节点的廉价访问 .
可以从树中的节点映射到文本中的字符偏移量 .
Persistent .
通过持久性，我指的是在对文本缓冲区进行编辑时重用树中大多数现有节点的能力 . 由于节点是不可变的，因此重用它们没有任何障碍 . 我们需要这个来表现;每次按键时我们都无法重新解析文件的大量文件 . 我们需要重新解析并重新解析受编辑影响的树的部分 .
现在，当您尝试将所有这些内容放入一个数据结构时，您会立即遇到问题：
如何在第一时间构建节点？父母和孩子都互相引用，并且是不可变的，所以首先 Build 哪一个？
假设您设法解决了这个问题：如何让它持久化？您不能在另一个父级中重用子节点，因为这会告诉孩子它有一个新父级 . 但孩子是不变的 .
假设您设法解决该问题：当您将新字符插入编辑缓冲区时，映射到该点之后的位置的每个节点的绝对位置都会发生变化 . 这使得构建持久数据结构变得非常困难，因为任何编辑都可以改变大多数节点的 Span ！
但在Roslyn团队中，我们经常做不可能的事情 . 我们实际上通过保留两个解析树来做不可能的事 . "green"树是不可变的，持久的，没有父引用，构建"bottom-up"，并且每个节点都跟踪它的宽度但不是它的绝对位置 . 当编辑发生时，我们只重建受编辑影响的绿树部分，这通常是树中总解析节点的O（log n） .
"red"树是一个不变的立面，围绕绿树建造;它按需构建"top-down"并在每次编辑时丢弃 . 它通过在从顶部向下穿过树时按需制造它们来计算父引用 . 它通过从宽度计算它们来制造绝对位置，同样，当你下降时 .
你，用户，只看到红树;绿树是一个实现细节 . 如果您查看解析节点的内部状态，您实际上会看到对另一个解析节点的引用属于不同类型;这是绿树节点 .
顺便提一下，这些被称为“红/绿树”，因为它们是我们在设计 Session 中用于绘制数据结构的白板标记颜色 . 颜色没有其他意义 .
这种策略的好处是我们可以获得所有这些伟大的东西：不变性，持久性，父引用等等 . 成本是这个系统很复杂，如果“红色”外墙变大，可能会占用大量内存 . 我们目前正在做实验，看看我们是否可以在不失去收益的情况下降低部分成本 .