Roslyn 的 SyntaxNodes 是否被重用？

Question

128

我一直在了解 Roslyn CTP，虽然它解决了与表达式树API类似的问题，但两者都是不可变的，但Roslyn通过一种完全不同的方式实现：

Expression节点没有对父节点的引用，使用ExpressionVisitor进行修改，因此可以重复使用大部分内容。
另一方面，Roslyn的SyntaxNode有一个对其父节点的引用，因此所有节点实际上成为一个不可能被重复使用的块。提供了诸如Update、ReplaceNode等方法来进行修改。

这会到哪里？Document？Project？ISolution？该API鼓励逐步更改树（而不是向上按钮），但每个步骤是否都会进行完整的复制？

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

- Olmo

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eric Lippert · Accepted Answer

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

很好的问题。我们讨论了你提出的问题很长时间。

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

通过持久性，我指的是当编辑文本缓冲区时，重用大部分现有节点的能力。由于节点是不可变的，因此没有重用它们的障碍。我们需要这个功能来提高性能；每次按键时，我们不能重新解析文件的大块内容。我们只需要重新词法分析和解析受编辑影响的树部分。

现在，当你试图将这五个要素放入一个数据结构中时，你会立即遇到问题：

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

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

“红色”树是围绕绿色树构建的不可变“外观”，它是按需“自上而下”构建的，并在每次编辑时被丢弃。它通过从顶部向下遍历时“按需制造”父引用来计算父引用。它通过再次从宽度计算绝对位置来制造绝对位置，同样是在向下遍历时。

您作为用户只能看到红色树；绿色树是实现细节。如果您查看解析节点的内部状态，实际上会发现其中有一个指向另一个不同类型的解析节点的引用；那就是绿色树节点。

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

这种策略的好处是，我们获得了所有这些伟大的东西：不变性、持久性、父引用等等。成本是，如果“红色”外观变大，这个系统会变得复杂并且可能消耗大量内存。我们目前正在进行实验，以查看是否可以减少一些成本而不失去利益。