I nodi sintattici di Roslyn sono riutilizzati?

Question

ho preso uno sguardo al Roslyn CTP e, mentre si risolve un problema simile a quello Expression tree API, entrambi sono immutabili ma Roslyn lo fa in un modo del tutto diverso:

• Expression nodi non hanno alcun riferimento alla nodo genitore, vengono modificati utilizzando un ExpressionVisitor ed è per questo che le parti grandi possono essere riutilizzate.

• Roslyn's SyntaxNode, sull'altro lato, ha un riferimento al relativo genitore, quindi tutti i nodi diventano effettivamente un blocco impossibile da riutilizzare. Metodi come Update, ReplaceNode, ecc. Vengono forniti per apportare modifiche.

Da dove viene questo fine? Document? Project? ISolution? L'API promuove una modifica graduale dell'albero (anziché un pulsante in alto), ma ogni passaggio fa una copia completa?

Perché hanno fatto una scelta del genere? C'è qualche trucco interessante che mi manca?

Answer 1

AGGIORNAMENTO: Questa domanda era the subject of my blog on June 8th, 2012. Grazie per la bella domanda!

---

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

Vorremmo avere una struttura dati che ha le seguenti caratteristiche:

• immutabile.
• La forma di un albero.
• Accesso economico ai nodi padre dai nodi figlio.
• È possibile eseguire la mappatura da un nodo nell'albero a un offset di carattere nel testo.
• Persistente.

Con persistenza intendo la capacità di riutilizzo la maggior parte dei nodi esistenti nella struttura quando una modifica è fatta per il 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 si tenta di mettere tutti e cinque di queste cose in una struttura di dati si esegue 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 questo 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.
• Supponiamo di riuscire a risolvere il problema: quando si inserisce un nuovo carattere nel buffer di modifica, la posizione assoluta di ogni nodo mappato su una posizione dopo tale 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 di routine cose impossibili. Effettivamente facciamo l'impossibile mantenendo due alberi di analisi. L'albero "verde" è immutabile, persistente, non ha riferimenti parentali, è 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 attorno all'albero verde; è costruito "dall'alto in basso" su richiesta e gettato via ad ogni modifica. Calcola i riferimenti principali tramite producendoli su richiesta mentre si scende attraverso l'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 esegui il peer nello stato interno di un nodo di analisi, noterai 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 dati nella riunione di progettazione. Non c'è altro significato per i colori.

Il vantaggio di questa strategia è che otteniamo tutte queste grandi cose: immutabilità, persistenza, riferimenti ai 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.