126

我一直在看Roslyn CTP，虽然它解决了与Expression tree API类似的问题，但两者都是不可变的，但 Roslyn 以完全不同的方式这样做：

  • Expression节点没有对父节点的引用，使用 a 进行修改ExpressionVisitor，这就是可以重用大部件的原因。

  • SyntaxNode另一方面，Roslyn 的具有对其父级的引用，因此所有节点实际上都变成了一个无法重用的块。Update提供了,ReplaceNode等方法来进行修改。

这在哪里结束？Document? Project? ISolution? API 促进了树的逐步更改（而不是向上按钮），但是每个步骤都会制作完整的副本吗？

他们为什么会做出这样的选择？我错过了一些有趣的技巧吗？

4

1 回答 1

183

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

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

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

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

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

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

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

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

“红”树是围绕绿树建造的不可变外观；它是根据需要“自上而下”构建的，并且在每次编辑时都被丢弃。当您从顶部向下穿过树时，它通过按需制造父引用来计算父引用。当您下降时，它再次通过宽度计算绝对位置来制造绝对位置。

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

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

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

于 2012-05-02T16:05:29.800 回答