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.