私はRoslynCTPを調べてきました。これは、式ツリーAPIと同様の問題を解決しますが、どちらも不変ですが、Roslynはまったく異なる方法でそれを行います。
Expressionノードには親ノードへの参照がなく、を使用して変更されるExpressionVisitorため、大きな部分を再利用できます。
SyntaxNode反対側のRoslynは、その親への参照を持っているため、すべてのノードが事実上、再利用できないブロックになります。、などのメソッドはUpdate、ReplaceNode変更を加えるために提供されています。
これはどこで終わりますか？Document？Project？ISolution？APIは（ボタンを押す代わりに）ツリーの段階的な変更を促進しますが、各段階で完全なコピーが作成されますか？
なぜ彼らはそのような選択をしたのですか？私が見逃している興味深いトリックはありますか？
更新：この質問は、2012年6月8日の私のブログの主題でした。素晴らしい質問をありがとう！
素晴らしい質問です。私たちはあなたが提起する問題について長い間議論しました。
次のような特徴を持つデータ構造が必要です。
永続性とは、テキストバッファが編集されたときに、ツリー内の既存のノードのほとんどを再利用できることを意味します。ノードは不変であるため、ノードを再利用するための障壁はありません。パフォーマンスのためにこれが必要です。キーを押すたびにファイルの巨大な塊を再解析することはできません。編集の影響を受けたツリーの部分のみを再レックスして再解析する必要があります。
これらの5つすべてを1つのデータ構造にまとめようとすると、すぐに問題が発生します。
しかし、Roslynチームでは、日常的に不可能なことを行っています。実際には、2つの解析ツリーを保持することで不可能を実行します。「グリーン」ツリーは不変で永続的であり、親参照がなく、「ボトムアップ」で構築され、すべてのノードはその幅を追跡しますが、絶対位置は追跡しません。編集が行われると、編集の影響を受けた緑色のツリーの部分のみが再構築されます。これは通常、ツリー内の解析ノード全体の約O（log n）です。
「赤い」木は、緑の木の周りに構築された不変のファサードです。オンデマンドで「トップダウン」で構築され、編集のたびに破棄されます。親参照は、ツリーを上から下るときにオンデマンドで作成することで計算されます。下降するときに、幅から絶対位置を計算することによって絶対位置を作成します。
ユーザーであるあなたは、赤い木しか見えません。緑の木は実装の詳細です。解析ノードの内部状態を調べると、実際には、別のタイプの別の解析ノードへの参照があることがわかります。それがグリーンツリーノードです。
ちなみに、これらは設計会議でデータ構造を描くために使用したホワイトボードマーカーの色であるため、「赤/緑の木」と呼ばれます。色には他に意味はありません。
この戦略の利点は、不変性、永続性、親参照など、これらすべての優れた機能を利用できることです。コストは、このシステムが複雑で、「赤い」ファサードが大きくなると大量のメモリを消費する可能性があることです。現在、メリットを失うことなくコストの一部を削減できるかどうかを確認するための実験を行っています。