Roslyn语法节点是否被重用?

我一直在看Roslyn CTP ,虽然它解决了Expression树API的类似问题,但两者都是不可变的,但Roslyn以一种完全不同的方式做到这一点:

  • Expression节点没有对父节点的引用,使用ExpressionVisitor进行修改,这就是为什么大部分可以被重用。

  • SyntaxNode ,Roslyn的SyntaxNode有一个对父节点的引用,所以所有的节点都有效地成为一个不可能重用的块。 像UpdateReplaceNode等方法被提供来进行修改。

这到底在哪里? DocumentProjectISolution ? API促进树的逐步改变(而不是一个button),但是每个步骤都做了一个完整的副本?

他们为什么做出这样的select? 我有一些有趣的技巧吗?

更新:这个问题是我的博客在2012年6月8日的主题 。 感谢您的好问题!


伟大的问题。 我们争论了很长时间以来提出的问题。

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

  • 不可改变的。
  • 树的forms。
  • 从子节点访问父节点的便利性。
  • 可能从树中的节点映射到文本中的字符偏移量。
  • 持久

持久性是指在对文本缓冲区进行编辑时, 重用树中大部分现有节点的能力。 由于节点是不可改变的,因此重用它们没有任何障碍。 我们需要这样的performance。 每当你点击一个键时,我们都不能重新parsing文件的大量文件。 我们需要重新parsing并重新parsing受编辑影响的树的部分。

现在,当您尝试将所有这五种东西放入一个数据结构中时,您会立即遇到问题:

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

但在Roslyn团队中,我们经常做不可能的事情。 我们实际上通过保留两个parsing树来做不可能的事情。 “绿色”树是不变的,持久的,没有父参考,是“自下而上”的,每个节点都跟踪它的宽度而不是绝对位置 。 当编辑发生时,我们只重build受编辑影响的绿色树的部分,这通常是树中全部parsing节点的O(log n)。

“红”树是围绕绿树build造的一个不变的门面 ; 它是根据需要 “自上而下”构build的并在每一次编辑时抛弃。 它通过按需制造父代引用来计算父引用, 当你从顶端通过树下降 。 它通过从宽度计算绝对位置,再次下降。

你,用户,只有看到红色的树; 绿树是一个实现细节。 如果你同步到一个parsing节点的内部状态,你实际上会看到另一个parsing节点有一个不同types的引用。 那是绿色的树节点。

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

这个策略的好处是我们可以得到所有这些伟大的东西:不变性,持久性,父亲引用等等。 成本是这个系统是复杂的,如果“红”门面变大,会消耗大量的内存。 目前我们正在做一些实验,看看我们是否可以减less一些成本而不损失好处。