¿Se reutilizan los Sintaxis de Roslyn?

c# expression-trees roslyn

Pregunta

He echado un vistazo al CTP de Roslyn y, aunque resuelve un problema similar al API del árbol de expresiones , ambos son inmutables, pero Roslyn lo hace de una manera muy diferente:

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

  • El SyntaxNode de Roslyn, 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. Métodos como Update , ReplaceNode , etc., se proporcionan 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 arriba), pero ¿cada paso hace una copia completa?

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

Respuesta aceptada

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 temas 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 nodos padres desde nodos hijos.
  • Es 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 reutilizar la mayoría de los nodos existentes en el árbol cuando se realiza una edición en el búfer de texto. Dado que los nodos son inmutables, no hay barrera para reutilizarlos. Necesitamos esto para el rendimiento; No podemos volver a analizar grandes cantidades de archivos cada vez que pulsas una tecla. Necesitamos volver a leer y volver a analizar solo las partes del árbol que fueron afectadas por la edición.

Ahora, cuando intenta colocar las cinco cosas en una estructura de datos, inmediatamente se encuentra con problemas:

  • ¿Cómo construir un nodo en primer lugar? El padre y el niño se refieren entre sí y son inmutables, entonces, ¿cuál se construye primero?
  • Suponiendo que logres resolver ese problema: ¿cómo lo haces persistente? No puede reutilizar un nodo secundario en un padre diferente porque eso implicaría decirle al niño que tiene un padre nuevo. Pero el niño es inmutable.
  • Suponiendo que logre 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 la extensión de la mayoría de los nodos!

Pero en el equipo de Roslyn, habitualmente hacemos cosas imposibles. Realmente hacemos lo imposible manteniendo dos árboles de parse. 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 generalmente es O (log n) del total de nodos de análisis en el árbol.

El árbol "rojo" es una fachada inmutable que se construye alrededor del árbol verde; se construye "de arriba abajo" a pedido y se desecha en cada edición. Calcula las referencias principales al fabricarlas a pedido a medida que desciende por el árbol desde la parte superior . Fabrica posiciones absolutas al calcularlas desde los anchos, nuevamente, a medida que desciendes.

Tú, el usuario, solo ves 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 de otro tipo; Ese es el nodo del árbol verde.

Incidentalmente, estos se denominan "árboles rojos / verdes" porque eran los colores del marcador de pizarra que utilizamos 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 grandes cosas: 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 vuelven grandes. Actualmente estamos realizando experimentos para ver si podemos reducir algunos de los costos sin perder los beneficios.



Licencia bajo: CC-BY-SA with attribution
No afiliado con Stack Overflow
Licencia bajo: CC-BY-SA with attribution
No afiliado con Stack Overflow