Roslyn SyntaxNodes是否重用

更新：这个问题是我在2012年6月8日博客的主题。谢谢你的好问题！

<小时 />

好问题。我们对你提出的问题进行了很长时间的辩论。

我们希望有一个具有以下特征的数据结构：

• 变。
• 树的形状。
• 从子节点廉价访问父节点。
• 可以从树中的节点映射到文本中的字符偏移量。
• 持久。

持久性是指在对文本缓冲区进行编辑时重用树中大多数现有节点的能力。由于节点是不可变的，因此重用它们没有障碍。我们需要这个来提高性能;我们不能在每次按下键时都重新解析大量的文件。我们需要重新 lex 并重新解析受编辑影响的树部分。

现在，当您尝试将所有这五件事放入一个数据结构中时，您会立即遇到问题：

• 首先如何构建节点？父项和子项都是相互引用的，并且是不可变的，那么哪个先构建呢？
• 假设你设法解决了这个问题：你如何让它持久？不能重用其他父节点中的子节点，因为这将涉及告诉子节点它有新的父节点。但孩子是一成不变的。
• 假设您设法解决了这个问题：当您将新字符插入编辑缓冲区时，映射到该点之后位置的每个节点的绝对位置都会发生变化。这使得制作持久数据结构变得非常困难，因为任何编辑都会改变大多数节点的跨度！

但在罗斯林团队中，我们经常做不可能的事情。我们实际上通过保留两个解析树来做不可能的事情。"绿色"树是不可变的，持久的，没有父引用，是"自下而上"构建的，每个节点都跟踪其宽度而不是其绝对位置。 当编辑发生时，我们只重建受编辑影响的绿树部分，这通常是树中总解析节点的O(log n(。

"红色"树是围绕绿树构建的不可变立面;它是按需"自上而下"构建的，并在每次编辑时丢弃。它通过按需制造父引用来计算父引用，当您从顶部下降到树中时。它通过从宽度计算它们来制造绝对位置，再次，当你下降时。

你，用户，只能看到红树;绿树是一个实现细节。如果您窥视解析节点的内部状态，您实际上会看到其中存在对另一个不同类型的解析节点的引用;这就是绿树节点。

顺便说一下，这些被称为"红/绿树"，因为这些是我们在设计会议中用来绘制数据结构的白板标记颜色。颜色没有其他含义。

这种策略的好处是，我们得到了所有这些伟大的东西：不变性、持久性、父引用等等。成本是这个系统很复杂，如果"红色"立面变大，可能会消耗大量内存。我们目前正在做实验，看看我们是否可以在不失去收益的情况下降低一些成本。