Ho dato un'occhiata a Roslyn CTP e, mentre risolve un problema simile all'API di Expression Tree , entrambi sono immutabili ma Roslyn lo fa in un modo completamente diverso:
Expression
nodi di Expression
non hanno alcun riferimento al nodo genitore, vengono modificati utilizzando un ExpressionVisitor
ed è per questo che le parti grandi possono essere riutilizzate.
Il SyntaxNode
di Roslyn, dall'altra parte, ha un riferimento al suo genitore, quindi tutti i nodi diventano effettivamente un blocco impossibile da riutilizzare. Metodi come Update
, ReplaceNode
, ecc. Vengono forniti per apportare modifiche.
Dove finisce questo? 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?
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:
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:
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.