Sono stati riutilizzati i SyntaxNode di Roslyn?

AGGIORNAMENTO: questa domanda è stata oggetto del mio blog l'8 giugno 2012 . Grazie per la bella domanda!

Grande domanda. Abbiamo discusso dei problemi che sollevavi per molto, molto tempo.

Ci piacerebbe avere una struttura dati che abbia le seguenti caratteristiche:

• Immutabile.
• La forma di un albero.
• Accesso economico ai nodi principali dai nodi figlio.
• È possibile mappare da un nodo nell'albero a un offset di carattere nel testo.
• Persistente .

Per persistenza intendo la capacità di riutilizzare la maggior parte dei nodi esistenti nell'albero quando viene apportata una modifica al buffer di testo. Poiché i nodi sono immutabili, non c'è alcun ostacolo al loro riutilizzo. Ne abbiamo bisogno per le prestazioni; non possiamo essere ri-analizzare gli enormi wodges del file ogni volta che colpisci un tasto. Abbiamo bisogno di ri-lessare e ri-analizzare solo le parti dell'albero che sono state interessate dalla modifica.

Ora quando provi a mettere tutte e cinque le cose in una struttura dati, ti imbatti immediatamente in problemi:

• Come si costruisce un nodo in primo luogo? Il genitore e il bambino si riferiscono entrambi, e sono immutabili, quindi quale si costruisce per primo?
• Supponiamo che tu riesca a risolvere quel problema: come lo fai persistente? Non è possibile riutilizzare un nodo figlio in un genitore diverso perché ciò implicherebbe dire al figlio che ha un nuovo genitore. Ma il bambino è immutabile.
• Supponendo che tu riesca a risolvere il problema: quando inserisci un nuovo carattere nel buffer di modifica, la posizione assoluta di ogni nodo mappato su una posizione dopo quel punto cambia. Ciò rende molto difficile creare una struttura di dati persistente, poiché qualsiasi modifica può modificare gli span della maggior parte dei nodi!

Ma sul team di Roslyn facciamo cose routinariamente impossibili. Effettivamente facciamo l'impossibile mantenendo due alberi di analisi. L'albero "verde" è immutabile, persistente, non ha riferimenti principali, è costruito "dal basso verso l'alto" e ogni nodo ne traccia la larghezza ma non la sua posizione assoluta . Quando si verifica una modifica, ricostruiamo solo le parti dell'albero verde che sono state interessate dalla modifica, che in genere corrisponde a O (log n) dei nodi di analisi totali nella struttura.

L'albero "rosso" è una facciata immutabile costruita intorno all'albero verde; è costruito "dall'alto verso il basso" su richiesta e gettato via su ogni modifica. Calcola i riferimenti dei genitori producendoli su richiesta mentre si scende dall'albero dall'alto . Produce posizioni assolute calcolandole dalle larghezze, ancora una volta, mentre si scende.

Tu, l'utente, vedi sempre l'albero rosso; l'albero verde è un dettaglio di implementazione. Se si scruta nello stato interno di un nodo di analisi, si vedrà infatti che esiste un riferimento a un altro nodo di analisi in un altro tipo; questo è il nodo dell'albero verde.

Per inciso, questi sono chiamati "alberi rossi / verdi" perché quelli erano i colori dei marcatori lavagna che usavamo per disegnare la struttura dei dati nella riunione di progettazione. Non c'è altro significato per i colori.

Il vantaggio di questa strategia è che otteniamo tutte quelle grandi cose: immutabilità, persistenza, riferimenti dei genitori e così via. Il costo è che questo sistema è complesso e può consumare molta memoria se le facciate "rosse" diventano grandi. Al momento stiamo facendo esperimenti per vedere se possiamo ridurre alcuni dei costi senza perdere i benefici.