¿Se vuelven a utilizar los SyntaxNodes de Roslyn?

Question

he estado echando un vistazo a Roslyn CTP y, mientras se resuelve un problema similar a la Expression tree API, ambos son inmutables, pero Roslyn lo hace de una manera muy diferente:

• Expression nodos tienen ninguna referencia a la nodo padre, se modifican utilizando un ExpressionVisitor y es por eso que las piezas grandes se pueden reutilizar.

• Roslyn's SyntaxNode, en el otro lado, tiene una referencia a su elemento principal, por lo que todos los nodos se convierten efectivamente en un bloque que es imposible de reutilizar. Se proporcionan métodos como Update, ReplaceNode, etc. para realizar modificaciones.

¿Dónde termina esto? Document? Project? ISolution? La API promueve un cambio paso a paso del árbol (en lugar de un botón para arriba), pero ¿cada paso hace una copia completa?

¿Por qué hicieron esa elección? ¿Hay algún truco interesante que me falta?

Answer 1

ACTUALIZACIÓN: Esta pregunta fue the subject of my blog on June 8th, 2012. Gracias por la gran pregunta!

---

Gran pregunta. Debatimos los problemas que plantea durante mucho, mucho tiempo.

Nos gustaría tener una estructura de datos que tiene las siguientes características:

• inmutable.
• La forma de un árbol.
• Acceso barato a los nodos principales desde los nodos secundarios.
• Posible asignar desde un nodo en el árbol a un desplazamiento de caracteres en el texto.
• persistente.

Por persistencia me refiero a la capacidad de reutilización la mayoría de los nodos existentes en el árbol cuando se hace una edición al tampón de texto. Como los nodos son inmutables, no hay barrera para reutilizarlos. Necesitamos esto para el rendimiento; no podemos volver a analizar grandes wodges del archivo cada vez que presionas una tecla. Necesitamos volver a leer y analizar solo las partes del árbol que se vieron afectadas por la edición.

Ahora, cuando se intenta poner los cinco de esas cosas en una estructura de datos se ejecuta inmediatamente en problemas:

• ¿Cómo se construye un nodo en el primer lugar? El padre y el hijo se refieren el uno al otro, y son inmutables, entonces, ¿cuál se construye primero?
• Supongamos que logra resolver ese problema: ¿cómo lo hace persistente? No puede volver a utilizar un nodo secundario en un elemento primario diferente porque eso implicaría decirle al niño que tiene un elemento primario nuevo. Pero el niño es inmutable.
• Supongamos que logra resolver ese problema: cuando inserta un nuevo carácter en el búfer de edición, la posición absoluta de cambia cada nodo asignado a una posición después de ese punto. Esto hace que sea muy difícil hacer una estructura de datos persistente, porque cualquier edición puede cambiar los tramos de la mayoría de los nodos.

Pero en el equipo de Roslyn rutinariamente hacemos cosas imposibles. De hecho, hacemos lo imposible manteniendo dos árboles de análisis. El árbol "verde" es inmutable, persistente, no tiene referencias principales, se construye "de abajo hacia arriba" y cada nodo rastrea su ancho pero no su posición absoluta. Cuando ocurre una edición, reconstruimos solo las partes del árbol verde que se vieron afectadas por la edición, que normalmente es aproximadamente O (log n) del total de los nodos de análisis del árbol.

El árbol "rojo" es una fachada inmutable que está construida alrededor del árbol verde; está construido "de arriba hacia abajo" bajo demanda y desechado en cada edición. Calcula las referencias principales por fabricándolas bajo demanda a medida que desciende por el árbol desde la parte superior. Fabrica posiciones absolutas informándolas de los anchos, de nuevo, a medida que desciendes.

Usted, el usuario, solo ve el árbol rojo; el árbol verde es un detalle de implementación. Si observa el estado interno de un nodo de análisis, de hecho verá que hay una referencia a otro nodo de análisis que tiene un tipo diferente; ese es el nodo del árbol verde.

Por cierto, estos se llaman "árboles rojos/verdes" porque esos eran los colores del marcador de pizarra que usamos para dibujar la estructura de datos en la reunión de diseño. No hay otro significado para los colores.

El beneficio de esta estrategia es que obtenemos todas esas cosas excelentes: inmutabilidad, persistencia, referencias de los padres, etc. El costo es que este sistema es complejo y puede consumir mucha memoria si las fachadas "rojas" se agrandan. Actualmente estamos haciendo experimentos para ver si podemos reducir algunos de los costos sin perder los beneficios.