c# - ¿Son Roslyn SyntaxNodes reutilizados?

expression-trees

Question

He estado echando un vistazo a Roslyn CTP y, aunque resuelve un problema similar a la API del árbol Expression , ambos son inmutables, pero Roslyn lo hace de una manera bastante diferente:

• Expression nodos de Expression no tienen referencia al nodo padre, se modifican usando un ExpressionVisitor y es por eso que las partes grandes se pueden reutilizar.

• Roslyn''s SyntaxNode , en el otro lado, tiene una referencia a su padre, 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 el tema de mi blog el 8 de junio de 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 tenga las siguientes características:

• Inmutable.
• La forma de un árbol
• Acceso barato a los nodos principales desde los nodos secundarios.
• Es posible mapear desde un nodo en el árbol a un desplazamiento de caracteres en el texto.
• Persistente

Por persistencia me refiero a la capacidad de reutilizar la mayoría de los nodos existentes en el árbol cuando se realiza una edición en el búfer 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 tratas de poner las cinco cosas en una estructura de datos, inmediatamente encuentras problemas:

• ¿Cómo se construye un nodo en 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 cada nodo que se asigna a una posición después de ese punto cambia. 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. En realidad hacemos lo imposible manteniendo dos árboles de análisis. El árbol "verde" es inmutable, persistente, no tiene referencias principales, está construido "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 se construye alrededor del árbol verde; se construye "de arriba hacia abajo" a pedido y se descarta en cada edición. Calcula las referencias principales al fabricarlas según 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 miras en el estado interno de un nodo de análisis verás que hay una referencia a otro nodo de análisis de un tipo diferente; ese es el nodo del árbol verde.

Incidentalmente, 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 maravillosas: inmutabilidad, persistencia, referencias de 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.