Roslyn语法节点是否重用？

Question

我一直在研究Roslyn CTP,虽然它解决了与Expression树API类似的问题,但它们都是不可变的,但Roslyn以一种完全不同的方式这样做:

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

• SyntaxNode另一方面,Roslyn 有一个对其父级的引用,因此所有节点都有效地成为一个无法重用的块.类似的方法Update,ReplaceNode等等,提供了进行修改.

这到底在哪里？Document？Project？ISolution？API促进树的逐步更改(而不是按钮向上),但每个步骤是否完整复制？

为什么他们这样做了？我有什么有趣的伎俩吗？

Answer 1

更新:这个问题是我的博客2012年6月8日的主题.谢谢你这个好问题!

好问题.我们长期讨论你提出的问题.

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

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

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

现在,当您尝试将所有这些内容放入一个数据结构时,您会立即遇到问题:

• 你如何建立一个节点？父母和孩子都互相引用,并且是不可变的,所以首先建立哪一个？
• 假设你设法解决这个问题:你如何使它持久化？您不能在另一个父级中重用子节点,因为这会告诉孩子它有一个新父级.但孩子是不变的.
• 假设您设法解决该问题:当您将新字符插入编辑缓冲区时,映射到该点之后的位置的每个节点的绝对位置都会发生变化.这使得构建持久数据结构变得非常困难,因为任何编辑都可以改变大多数节点的跨度!

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

"红色"树是一个不变的立面,围绕绿树建造; 它根据需要 "自上而下"构建,并在每次编辑时丢弃.它通过在从顶部向下穿过树时按需制造它们来计算父引用.它通过从宽度计算它们来制造绝对位置,同样,当你下降时.

你,用户,只看到红树; 绿树是一个实现细节.如果您查看解析节点的内部状态,您实际上会看到对另一个解析节点的引用属于不同类型; 这是绿树节点.

顺便提一下,这些被称为"红/绿树",因为它们是我们在设计会议中用于绘制数据结构的白板标记颜色.颜色没有其他意义.

这种策略的好处是我们可以获得所有这些伟大的东西:不变性,持久性,父引用等等.成本是这个系统很复杂,如果"红色"外墙变大,可能会占用大量内存.我们目前正在做实验,看看我们是否可以在不失去收益的情况下降低部分成本.