Roslyn的发布版本是如何实现不可变树的
本文关键字:何实现 实现 不可变 布版本 版本 Roslyn | 更新日期: 2023-09-27 18:23:53
我知道Roslyn的预发布版本实现了不可变树,正如Eric Lippert在这篇优秀的博客文章中所描述的那样。然而,这篇文章的结尾是:
成本是该系统是复杂的,并且如果";红色";外墙变得很大。我们目前正在做实验,看看是否可以在不损失收益的情况下降低一些成本。
我想问一下发布版本的结果是什么。我已经开始检查Roslyn的源代码,但是代码相当复杂。
我感兴趣的是关于上述成本的低级设计结果。
- 就红/绿节点而言,一次编辑的成本是多少
- 对其他操作(如删除、撤消)进行了哪些优化
在这里的讨论论坛上,您可以看到Roslyn的性能以及VSadov对不可变树的实现:https://roslyn.codeplex.com/discussions/541953
在高层,他讨论了并发性、绿色节点的重复数据消除、终端的重复数据删除和这些树中字符串的重复数据清除。
他还谈到了红树的懒惰。不是在每次文本更改后计算红树,而是只有当有人请求时才计算红树
最后,他讨论了这棵红色的树和它很弱的事实。我从未使用或见过WeakReference
类,VSadov提供了一个很好的概述,说明它是如何在红树中使用的。基本上,垃圾收集器可以清理红树的部分,如果需要,可以稍后重新创建它们。我不熟悉实现,但Eric Lippert指出,红树外观可能会导致占用大量内存。我想这些WeakReferences
在一定程度上有助于缓解这个问题。
目前我们仍在做与Eric描述的基本相同的事情。我们尝试了一些实验,但发现API澄清度的成本太高,无法支付。相反,我们所做的主要更改是通过将SyntaxToken
变成红色模型中的结构来减少堆分配和GC成本。这是一个显著的节省,因为在平均源文件中,语法树中大约有一半的节点是终端(SyntaxToken
s)。绿色节点不是structs,而是另一方面,由于它们不包含父指针或位置,因此它们是被插入的——我们为所有相同的节点共享相同的绿色节点实例(相同的琐事和文本)。
我不知道你说的"编辑成本"是什么意思。时间/空间/复杂性等。一般来说,我们有一个增量lexer,它可以重新扫描受编辑影响的区域。然后我们有一个增量解析器,在最好的情况下,它会重新解析与新lexed标记相交的语句,然后重新构建绿色树的"脊椎",直到根,同时重新使用树中的其余绿色节点。根据定义,没有一个红色节点是可重用的。新树有一个新的根节点,它可以从任何其他节点访问。
编译器中没有进行其他优化。撤消后,我们在IDE中重用缓存的树,但我不确定。