Czy Roslyn SyntaxNodes jest ponownie używany?

124

Przyjrzałem się Roslyn CTP i chociaż rozwiązuje problem podobny do interfejsu API drzewa wyrażeń , oba są niezmienne, ale Roslyn robi to w zupełnie inny sposób:

  • Expressionwęzły nie mają odniesienia do węzła nadrzędnego, są modyfikowane za pomocą ExpressionVisitora, dlatego duże części można ponownie wykorzystać.

  • SyntaxNodeZ drugiej strony Roslyn's ma odniesienie do swojego rodzica, więc wszystkie węzły skutecznie stają się blokiem, którego nie można ponownie wykorzystać. Metody takie jak Update, ReplaceNodeitp, są odchylenia.

Gdzie to się kończy? Document? Project? ISolution? API promuje krok po kroku zmianę drzewa (zamiast przycisku w górę), ale czy każdy krok tworzy pełną kopię?

Dlaczego dokonali takiego wyboru? Czy brakuje mi jakiejś interesującej sztuczki?

Olmo
źródło

Odpowiedzi:

181

AKTUALIZACJA: To pytanie było tematem mojego bloga 8 czerwca 2012 roku . Dzięki za świetne pytanie!


Świetne pytanie. Długo debatowaliśmy nad poruszanymi przez Ciebie kwestiami.

Chcielibyśmy mieć strukturę danych, która ma następujące cechy:

  • Niezmienny.
  • Forma drzewa.
  • Tani dostęp do węzłów nadrzędnych z węzłów podrzędnych.
  • Możliwe do odwzorowania z węzła w drzewie na przesunięcie znaku w tekście.
  • Trwałe .

Przez trwałość mam na myśli możliwość ponownego wykorzystania większości istniejących węzłów w drzewie podczas edycji bufora tekstowego. Ponieważ węzły są niezmienne, nie ma przeszkód w ich ponownym wykorzystaniu. Potrzebujemy tego do wydajności; nie możemy ponownie analizować ogromnych fragmentów pliku za każdym razem, gdy naciśniesz klawisz. Musimy ponownie leksować i ponownie przeanalizować tylko te części drzewa, na które wpłynęła edycja.

Teraz, gdy spróbujesz umieścić wszystkie pięć z tych rzeczy w jednej strukturze danych, natychmiast napotkasz problemy:

  • Jak w ogóle budujesz węzeł? Rodzic i dziecko odnoszą się do siebie nawzajem i są niezmienni, więc który z nich zostanie zbudowany jako pierwszy?
  • Przypuśćmy, że uda ci się rozwiązać ten problem: jak sprawić, by był trwały? Nie możesz ponownie użyć węzła podrzędnego w innym rodzicu, ponieważ wymagałoby to poinformowania dziecka, że ​​ma nowego rodzica. Ale dziecko jest niezmienne.
  • Przypuśćmy, że uda ci się rozwiązać ten problem: po wstawieniu nowego znaku do bufora edycji zmienia się bezwzględna pozycja każdego węzła, który jest mapowany na pozycję po tym punkcie . To sprawia, że ​​bardzo trudno jest stworzyć trwałą strukturę danych, ponieważ każda edycja może zmienić rozpiętość większości węzłów!

Ale w zespole Roslyn rutynowo robimy rzeczy niemożliwe. W rzeczywistości dokonujemy niemożliwego, zachowując dwa drzewa parsowania. Drzewo „zielone” jest niezmienne, trwałe, nie ma odniesień do rodziców, jest budowane „od dołu do góry”, a każdy węzeł śledzi swoją szerokość, ale nie swoją pozycję bezwzględną . Kiedy następuje edycja, przebudowujemy tylko te części zielonego drzewa, na które miała wpływ edycja, czyli zazwyczaj około O (log n) wszystkich węzłów analizy w drzewie.

„Czerwone” drzewo to niezmienna fasada zbudowana wokół zielonego drzewa; jest budowany „z góry na dół” na żądanie i wyrzucany przy każdej edycji. Oblicza referencje nadrzędne, wytwarzając je na żądanie, gdy schodzisz po drzewie od góry . Wytwarza pozycje absolutne, obliczając je na podstawie szerokości, ponownie, gdy schodzisz.

Ty, użytkownik, widzisz tylko czerwone drzewo; zielone drzewo to szczegół implementacji. Jeśli zajrzysz do stanu wewnętrznego węzła parsowania, w rzeczywistości zobaczysz, że istnieje tam odwołanie do innego węzła analizy innego typu; to jest zielony węzeł drzewa.

Nawiasem mówiąc, nazywane są one „czerwonymi / zielonymi drzewami”, ponieważ były to kolory markerów tablicy, których użyliśmy do narysowania struktury danych podczas spotkania projektowego. Kolory nie mają innego znaczenia.

Zaletą tej strategii jest to, że otrzymujemy wszystkie te wspaniałe rzeczy: niezmienność, wytrwałość, odniesienia do rodziców i tak dalej. Koszt jest taki, że ten system jest złożony i może zajmować dużo pamięci, jeśli „czerwone” fasady staną się duże. Obecnie prowadzimy eksperymenty, aby sprawdzić, czy możemy obniżyć niektóre koszty bez utraty korzyści.

Eric Lippert
źródło
3
Odpowiadając na część Twojego pytania o IProjects i IDocuments: używamy podobnego modelu w warstwie usług. Wewnętrznie istnieją typy „DocumentState” i „ProjectState”, które są moralnym odpowiednikiem zielonych węzłów drzewa składni. Otrzymane obiekty IProject / IDocument to czerwone fasady węzłów. Jeśli spojrzysz na implementację Roslyn.Services.Project w dekompilatorze, zobaczysz, że prawie wszystkie wywołania są przekazywane do wewnętrznych obiektów stanu.
Jason Malinowski
@Eric przepraszam za uwagę, ale sam sobie zaprzeczasz. The expense and difficulty of building a complex persistent data structure doesn't pay for itself.ref: stackoverflow.com/questions/6742923/… Gdybyś miał cele związane z wysoką wydajnością, dlaczego uczyniłeś je niezmiennym? Czy oprócz tych oczywistych jest tylko inny powód? np. łatwiej jest zabezpieczyć wątki, uzasadnić itp.
Łukasz Madon
2
@lukas Wyciągasz ten cytat z kontekstu. Poprzednie zdanie brzmiało: „Ponieważ kiedy spojrzymy na operacje, które są zwykle wykonywane na łańcuchach w programach .NET, nie jest wcale gorsze, jeśli chodzi o po prostu utworzenie zupełnie nowego ciągu”. OTOH, kiedy patrzysz na operacje, które są zwykle wykonywane na drzewie wyrażeń - np. Wpisanie kilku znaków do pliku źródłowego - znacznie gorzej jest zbudować zupełnie nowe drzewo wyrażeń. Więc budują tylko połowę.
Timbo
1
@lukas Zgaduję: biorąc pod uwagę, że Roslyn ma działać na wątkach w tle, niezmienność pozwala wielu wątkom analizować ten sam kod źródłowy w tym samym czasie, bez obawy, że zostanie on zmieniony, gdy użytkownik naciśnie klawisz. W odpowiedzi na dane wejściowe użytkownika niezmienne drzewa można aktualizować bez zatrzymywania uruchomionych zadań analitycznych. Więc wyobrażam sobie, że głównym celem niezmienności jest uczynienie Roslyn łatwiejszym do pisania (i być może łatwiejszym w użyciu dla klientów).
Qwertie
3
@lukas Trwałe struktury danych są bardziej wydajne niż kopiowanie, gdy struktura danych jest zwykle znacznie większa niż wprowadzone w niej zmiany. Twój punkt widzenia, jeśli go masz, jest dla mnie stracony.
Qwertie