[解決済み] RoslynのSyntaxNodeは再利用できますか？

質問

私はこれまで Roslyn CTP と似たような問題を解決している一方で 式木 API と同じような問題を解決しますが、どちらも不変ですが、Roslyn は全く異なる方法でそれを行います。

• Expression ノードは、親ノードへの参照を持たず、変更する場合は ExpressionVisitor を使って変更され、そのために大きな部品が再利用できるのです。

• ロスリンの SyntaxNode はその親への参照を持つので、すべてのノードは事実上再利用が不可能なブロックになります。のようなメソッドは Update , ReplaceNode などが用意されており、修正することができます。

これはどこで終わるのでしょうか？ Document ? Project ? ISolution ? APIは、ツリーのステップバイステップの変更（ボタンアップの代わりに）を促進しますが、各ステップは完全なコピーを作成するのでしょうか？

なぜ彼らはそのような選択をしたのでしょうか？私が見逃している何か興味深いトリックがあるのでしょうか?

どのように解決するのですか？

UPDATE: この質問は のブログで取り上げました。 . 素晴らしい質問をありがとうございました。

素晴らしい質問ですね。私たちは、あなたが提起した問題について、長い間、長い間、議論しました。

次のような特徴を持つデータ構造を持ちたいと考えています。

• 不変である。
• 木の形をしています。
• 子ノードから親ノードへの安価なアクセス。
• ツリー内のノードからテキスト内の文字オフセットにマップすることが可能です。
• 永続的 .

で 永続性 の能力を意味します。 ツリー内の既存のノードのほとんどを再利用する というのは、テキスト バッファに編集が加えられたときに、ツリーの既存のノードのほとんどを再利用する機能です。ノードは不変であるため、ノードを再利用するための障壁はありません。キーを押すたびにファイルの膨大な部分を再解析するわけにはいかないので、パフォーマンスのためにこれが必要です。編集によって影響を受けたツリーの部分のみを再レキシングおよび再パースする必要があります。

さて、これらの 5 つの事柄をすべて 1 つのデータ構造にまとめようとすると、すぐに問題にぶつかります。

• そもそも、ノードをどのように構築するのでしょうか。親と子の両方がお互いを参照し、不変なので、どちらが先に構築されるのでしょうか？
• 仮にその問題を解決できたとして、それを永続化するにはどうしたらいいでしょうか？子ノードを別の親で再利用することはできません。なぜなら、子ノードに新しい親がいることを伝えることになるからです。しかし、子ノードは不変です。
• 仮にその問題を解決できたとして、編集バッファに新しい文字を挿入するとき、絶対位置が の絶対位置は、その時点以降の位置にマップされるすべてのノード の絶対位置が変わってしまいます。このため、永続的なデータ構造を作ることは非常に困難です。なぜなら、編集によってほとんどのノードのスパンが変更されてしまうからです

しかし、Roslynチームでは、日常的に不可能なことを行っています。実際に不可能を可能にするために 2 解析ツリーを保持することで不可能を可能にしています。緑色の木は不変で、永続的で、親を参照せず、ボトムアップで構築され、各ノードがその 幅 を追跡しますが、その 絶対位置 . 編集が発生した場合、編集によって影響を受けた緑樹の部分のみを再構築します。これは通常、樹木の全解析ノードの約 O(log n) です。

red" ツリーは不変の ファサード であり、緑の木の周囲に構築され、トップダウンで構築されます。 オンデマンド で構築され、編集のたびに破棄されます。これは、親リファレンスを ツリーを上から下へ降りていくときに、必要に応じてそれらを生成します。 . また、絶対位置は、幅から計算することによって生成されます。

ユーザーは赤いツリーしか見ることができず、緑のツリーは実装の詳細です。解析ノードの内部状態を覗き込むと、実際に 別の への参照があることがわかります。それが緑の木ノードです。

ちなみに、これらを「赤・緑の木」と呼んでいるのは、設計会議でデータ構造を描くときに使ったホワイトボードマーカーの色に由来しています。それ以外の意味はありません。

この戦略の利点は、不変性、永続性、親参照など、すばらしいものをすべて手に入れられることです。しかし、このシステムは複雑で、quot;red" ファサードが大きくなると、多くのメモリを消費する可能性があるという代償があります。私たちは現在、利点を失うことなくコストの一部を削減できるかどうかを確認するための実験を行っています。