Werden Roslyn SyntaxNodes wiederverwendet?

Question

Ich habe einen Blick auf Roslyn CTP nehmen und, während es ein ähnliches Problem mit dem Expression tree API löst, beide unveränderlich sind aber Roslyn tut dies auf eine ganz andere Art und Weise:

• Expression Knoten haben keinen Hinweis auf die Elternknoten, werden mit einem ExpressionVisitor modifiziert und deshalb können große Teile wiederverwendet werden.

• Roslyns SyntaxNode, auf der anderen Seite, hat einen Verweis auf seine Eltern, so dass alle Knoten effektiv zu einem Block werden, der nicht wiederverwendet werden kann. Methoden wie Update, ReplaceNode usw. werden bereitgestellt, um Änderungen vorzunehmen.

Wo endet das? Document? Project? ISolution? Die API fördert eine schrittweise Änderung der Struktur (anstelle einer Schaltfläche), aber macht jeder Schritt eine vollständige Kopie?

Warum haben sie eine solche Wahl getroffen? Gibt es einen interessanten Trick, den ich vermisse?

Answer 1

UPDATE: Diese Frage war the subject of my blog on June 8th, 2012. Danke für die tolle Frage!

---

Große Frage. Wir haben die Probleme diskutiert, die Sie für eine lange Zeit haben.

Wir würden gerne eine Datenstruktur haben, die folgende Merkmale aufweist:

• Immutable.
• Die Form eines Baumes.
• Günstiger Zugriff auf übergeordnete Knoten von untergeordneten Knoten.
• Möglich, von einem Knoten in der Struktur auf einen Zeichenversatz im Text zu mappen.
• Persistent.

Durch Ausdauer meine ich die Fähigkeit, Wiederverwendung meisten des bestehenden Knoten im Baum, wenn eine Bearbeitung auf den Textpuffer gemacht wird. Da die Knoten unveränderlich sind, gibt es keine Barriere für die Wiederverwendung. Wir brauchen das für die Leistung; Wir können nicht jedes Mal, wenn Sie einen Schlüssel drücken, erneut große Lücken in der Datei analysieren. Wir müssen die Teile des Baums, die von der Bearbeitung betroffen waren, erneut lexen und erneut analysieren.

Wenn Sie nun versuchen, alle fünf dieser Dinge in eine Datenstruktur setzen Sie sofort auf Probleme stoßen:

• Wie baut man einen Knoten in erster Linie? Das Elternteil und das Kind beziehen sich aufeinander und sind unveränderlich, also was wird zuerst gebaut?
• Angenommen, Sie schaffen es, dieses Problem zu lösen: Wie machen Sie es persistent? Sie können einen untergeordneten Knoten in einem anderen übergeordneten Element nicht erneut verwenden, da dies bedeuten würde, dem untergeordneten Element mitzuteilen, dass es ein neues übergeordnetes Element besitzt. Aber das Kind ist unveränderlich.
• Angenommen, Sie lösen dieses Problem: Wenn Sie ein neues Zeichen in den Bearbeitungspuffer einfügen, ändert sich die absolute Position von jeder Knoten, der auf eine Position nach diesem Punkt zugeordnet ist. Dies macht es sehr schwierig, eine persistente Datenstruktur zu erstellen, da jede Bearbeitung die Spannen der meisten Knoten verändern kann!

Aber im Roslyn-Team machen wir routinemäßig unmögliche Dinge. Wir machen das Unmögliche, indem wir zwei Parse Bäume halten. Der "grüne" Baum ist unveränderlich, persistent, hat keine Elternreferenzen, ist "von unten nach oben" aufgebaut und jeder Knoten verfolgt seine Breite, aber nicht seine absolute Position. Wenn eine Bearbeitung stattfindet, erstellen wir nur die Teile des grünen Baums neu, die von der Bearbeitung betroffen waren. Dies ist in der Regel etwa O (log n) der gesamten Parse-Knoten in der Struktur.

Der "rote" Baum ist eine unveränderliche Fassade, die um den grünen Baum herum gebaut wird; es ist "top-down" auf Anfrage gebaut und auf jeder Bearbeitung weggeworfen. Er berechnet übergeordnete Referenzen durch , die sie auf Nachfrage herstellt, während Sie durch den Baum von der Spitze hinuntersteigen. Er erzeugt absolute Positionen, indem er sie beim Abstieg aus den Breiten berechnet.

Sie, der Benutzer, sehen immer nur den roten Baum; Der grüne Baum ist ein Implementierungsdetail. Wenn Sie in den internen Zustand eines Parsing-Knotens schauen, sehen Sie tatsächlich, dass es einen Verweis auf einen anderen Parse-Knoten in einem anderen Typ gibt; das ist der grüne Baumknoten.

Übrigens werden diese "rot/grünen Bäume" genannt, weil das die Whiteboard-Marker Farben waren, die wir verwendet haben, um die Datenstruktur in der Design-Sitzung zu zeichnen. Die Farben haben keine andere Bedeutung.

Der Vorteil dieser Strategie ist, dass wir all diese großartigen Dinge bekommen: Unveränderlichkeit, Persistenz, Elternreferenzen und so weiter. Die Kosten sind, dass dieses System komplex ist und viel Speicher verbrauchen kann, wenn die "roten" Fassaden groß werden. Wir machen derzeit Experimente, um zu sehen, ob wir einen Teil der Kosten reduzieren können, ohne die Vorteile zu verlieren.