Werden Roslyn SyntaxNodes wiederverwendet?

124

Ich habe mir Roslyn CTP angesehen und obwohl es ein ähnliches Problem wie die Expression Tree-API löst , sind beide unveränderlich, aber Roslyn tut dies auf ganz andere Weise:

  • ExpressionKnoten haben keinen Verweis auf den übergeordneten Knoten, werden mit a geändert ExpressionVisitorund deshalb können große Teile wiederverwendet werden.

  • Roslyns SyntaxNodeauf der anderen Seite hat einen Verweis auf sein übergeordnetes Element, sodass alle Knoten effektiv zu einem Block werden, der nicht mehr wiederverwendet werden kann. Methoden wie Update, ReplaceNodeusw., vorgesehen sind , Änderungen vorzunehmen.

Wo endet das? Document? Project? ISolution? Die API fördert eine schrittweise Änderung des Baums (anstelle einer Schaltfläche nach oben). Erstellt jeder Schritt jedoch eine vollständige Kopie?

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

Olmo
quelle

Antworten:

181

UPDATE: Diese Frage war das Thema meines Blogs am 8. Juni 2012 . Danke für die tolle Frage!


Gute Frage. Wir haben die Themen, die Sie ansprechen, lange, lange diskutiert.

Wir möchten eine Datenstruktur mit folgenden Merkmalen:

  • Unveränderlich.
  • Die Form eines Baumes.
  • Günstiger Zugriff auf übergeordnete Knoten von untergeordneten Knoten.
  • Es ist möglich, einen Knoten im Baum einem Zeichenversatz im Text zuzuordnen.
  • Hartnäckig .

Mit Persistenz meine ich die Möglichkeit, die meisten vorhandenen Knoten im Baum wiederzuverwenden, wenn der Textpuffer bearbeitet wird. Da die Knoten unveränderlich sind, gibt es keine Barriere für ihre Wiederverwendung. Wir brauchen das für die Leistung; Wir können nicht jedes Mal, wenn Sie eine Taste drücken, große Mengen der Datei erneut analysieren. Wir müssen nur die Teile des Baums neu lexen und analysieren, die von der Bearbeitung betroffen waren.

Wenn Sie nun versuchen, alle fünf dieser Dinge in einer Datenstruktur zusammenzufassen, treten sofort Probleme auf:

  • Wie baut man überhaupt einen Knoten? Das Elternteil und das Kind beziehen sich beide aufeinander und sind unveränderlich. Welches wird also zuerst gebaut?
  • Angenommen, Sie schaffen es, dieses Problem zu lösen: Wie machen Sie es dauerhaft? Sie können einen untergeordneten Knoten in einem anderen übergeordneten Knoten nicht wiederverwenden, da dies dem Kind mitteilen würde, dass es einen neuen übergeordneten Knoten hat. Aber das Kind ist unveränderlich.
  • Angenommen, Sie schaffen es, dieses Problem zu lösen: Wenn Sie ein neues Zeichen in den Bearbeitungspuffer einfügen , ändert sich die absolute Position jedes Knotens, der nach diesem Punkt einer Position zugeordnet wird . Dies macht es sehr schwierig, eine dauerhafte Datenstruktur zu erstellen, da jede Bearbeitung die Bereiche der meisten Knoten ändern kann!

Aber im Roslyn-Team machen wir routinemäßig unmögliche Dinge. Wir tun tatsächlich das Unmögliche, indem wir zwei Analysebäume halten. Der "grüne" Baum ist unveränderlich, persistent, hat keine übergeordneten Referenzen, ist "bottom-up" 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 entspricht normalerweise etwa O (log n) der gesamten Analyseknoten im Baum.

Der "rote" Baum ist eine unveränderliche Fassade , die um den grünen Baum herum gebaut ist. Es wird bei Bedarf "von oben nach unten" erstellt und bei jeder Bearbeitung weggeworfen. Es berechnet übergeordnete Referenzen, indem es sie bei Bedarf herstellt, während Sie von oben durch den Baum absteigen . Es stellt absolute Positionen her, indem es sie beim Abstieg wieder aus den Breiten berechnet.

Sie als Benutzer sehen immer nur den roten Baum. Der grüne Baum ist ein Implementierungsdetail. Wenn Sie in den internen Status eines Analyseknotens blicken, werden Sie tatsächlich feststellen, dass dort ein Verweis auf einen anderen Analyseknoten eines anderen Typs vorhanden ist. Das ist der grüne Baumknoten.

Diese werden übrigens als "rot / grüne Bäume" bezeichnet, da dies die Whiteboard-Markierungsfarben waren, mit denen wir die Datenstruktur in der Entwurfsbesprechung gezeichnet haben. Die Farben haben keine andere Bedeutung.

Der Vorteil dieser Strategie ist, dass wir all diese großartigen Dinge erhalten: Unveränderlichkeit, Beharrlichkeit, Referenzen der Eltern und so weiter. Die Kosten sind, dass dieses System komplex ist und viel Speicher verbrauchen kann, wenn die "roten" Fassaden groß werden. Derzeit führen wir Experimente durch, um festzustellen, ob wir einen Teil der Kosten senken können, ohne die Vorteile zu verlieren.

Eric Lippert
quelle
3
Und um den Teil Ihrer Frage zu IProjects und IDocuments zu beantworten: Wir verwenden ein ähnliches Modell in der Serviceschicht. Intern gibt es die Typen "DocumentState" und "ProjectState", die den grünen Knoten des Syntaxbaums moralisch entsprechen. Die IProject / IDocument-Objekte, die Sie erhalten, sind die roten Knotenfassaden für diese. Wenn Sie sich die Implementierung von Roslyn.Services.Project in einem Dekompiler ansehen, werden Sie feststellen, dass fast alle Aufrufe an die internen Statusobjekte weitergeleitet werden.
Jason Malinowski
@ Eric Entschuldigung für die Bemerkung, aber Sie widersprechen sich. The expense and difficulty of building a complex persistent data structure doesn't pay for itself.ref: stackoverflow.com/questions/6742923/… Wenn Sie hohe Leistungsziele hatten, warum haben Sie es überhaupt unveränderlich gemacht? Gibt es außer den offensichtlichen nur einen anderen Grund? zB einfacher, threadsicher zu machen, darüber nachzudenken usw.
Lukasz Madon
2
@lukas Du nimmst dieses Zitat aus dem Zusammenhang. Der vorige Satz lautete: "Wenn Sie sich Operationen ansehen, die normalerweise für Zeichenfolgen in .NET-Programmen ausgeführt werden, ist es in jeder relevanten Hinsicht kaum schlimmer, einfach eine völlig neue Zeichenfolge zu erstellen." OTOH, wenn Sie sich Operationen ansehen, die normalerweise für einen Ausdrucksbaum ausgeführt werden - z. B. das Eingeben einiger Zeichen in die Quelldatei -, ist es erheblich schlimmer, einen völlig neuen Ausdrucksbaum zu erstellen. Sie bauen also nur die Hälfte davon.
Timbo
1
@lukas Meine Vermutung: Angesichts der Tatsache, dass Roslyn Hintergrundthreads verarbeiten soll, ermöglicht die Unveränderlichkeit mehreren Threads, denselben Quellcode gleichzeitig zu analysieren, ohne befürchten zu müssen, dass er geändert wird, wenn der Benutzer eine Taste drückt. Als Reaktion auf Benutzereingaben können unveränderliche Bäume aktualisiert werden, ohne dass laufende Analyseaufgaben gestoppt werden. Daher stelle ich mir vor, dass das Hauptziel der Unveränderlichkeit darin besteht, Roslyn einfacher zu schreiben (und möglicherweise für Kunden einfacher zu verwenden).
Qwertie
3
@lukas Persistente Datenstrukturen sind effizienter als das Kopieren, wenn die Datenstruktur in der Regel viel größer ist als die Änderungen. Ihr Punkt, wenn Sie einen haben, geht mir verloren.
Qwertie