¿Se reutilizan los sintaxis de Roslyn?

124

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

  • Expressionlos nodos no tienen referencia al nodo padre, se modifican usando a ExpressionVisitory es por eso que las partes grandes se pueden reutilizar.

  • Roslyn's SyntaxNode, por 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, ReplaceNodeetc., 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 hacia arriba), pero ¿cada paso hace una copia completa?

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

Olmo
fuente

Respuestas:

181

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.
  • 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. Como los nodos son inmutables, no hay ninguna barrera para reutilizarlos. Necesitamos esto para el rendimiento; no podemos volver a analizar grandes cantidades de archivos cada vez que presionas una tecla. Necesitamos volver a analizar y volver a analizar solo las partes del árbol que fueron afectadas por la edición.

Ahora, cuando intentas poner las cinco cosas en una estructura de datos, inmediatamente tienes problemas:

  • ¿Cómo se construye un nodo en primer lugar? El padre y el hijo se refieren entre sí y son inmutables, entonces, ¿cuál se construye primero?
  • Supongamos que logras resolver ese problema: ¿cómo lo haces persistente? No puede reutilizar un nodo hijo en un padre diferente porque eso implicaría decirle al niño que tiene un nuevo padre. 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 crear 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 hacemos rutinariamente cosas imposibles. Realmente hacemos lo imposible al mantener dos árboles de análisis. El árbol "verde" es inmutable, persistente, no tiene referencias primarias, 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 fueron afectadas por la edición, que generalmente se trata de 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 hacia abajo" bajo demanda y se desecha en cada edición. Calcula referencias de padres al fabricarlas a pedido a medida que desciende a través del árbol desde la parte superior . Fabrica posiciones absolutas al calcularlas a partir de los anchos, nuevamente, a medida que desciende.

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 de un tipo diferente; ese es el nodo del árbol verde.

Por cierto, estos se llaman "árboles rojos / verdes" porque esos fueron los colores de 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 agrandan. Actualmente estamos haciendo experimentos para ver si podemos reducir algunos de los costos sin perder los beneficios.

Eric Lippert
fuente
3
Y para abordar la parte de su pregunta sobre IProjects e IDocuments: utilizamos un modelo similar en la capa de servicios. Internamente hay tipos "DocumentState" y "ProjectState" que son moralmente equivalentes a los nodos verdes del árbol de sintaxis. Los objetos de IProject / IDocument que obtienes son las fachadas de nodo rojo para estos. Si observa la implementación de Roslyn.Services.Project en un descompilador, verá que casi todas las llamadas reenvían a los objetos de estado interno.
Jason Malinowski
@ Eric, perdón por el comentario, pero te estás contradiciendo. The expense and difficulty of building a complex persistent data structure doesn't pay for itself.ref: stackoverflow.com/questions/6742923/… Si tenía objetivos de alto rendimiento, ¿por qué lo hizo inmutable en primer lugar? ¿Hay solo otra razón aparte de las obvias? por ejemplo, es más fácil hacer hilos seguros, razonar sobre etc.
Lukasz Madon
2
@lukas Estás sacando esa cita fuera de contexto. La oración anterior era "Porque cuando se miran las operaciones que generalmente se realizan en cadenas en programas .NET, en todos los aspectos relevantes no es peor en absoluto crear una cadena completamente nueva". OTOH, cuando observa las operaciones que generalmente se realizan en un árbol de expresión, por ejemplo, escribiendo algunos caracteres en el archivo fuente, es significativamente peor construir un árbol de expresión completamente nuevo. Entonces solo construyen la mitad.
Timbo
1
@lukas Mi conjetura: dado que se supone que Roslyn opera en subprocesos en segundo plano, la inmutabilidad permite que varios subprocesos analicen el mismo código fuente al mismo tiempo sin preocuparse de que se cambie cuando el usuario presiona una tecla. En respuesta a la entrada del usuario, los árboles inmutables se pueden actualizar sin detener las tareas de análisis que se ejecutan. Así que imagino que el objetivo principal de la inmutabilidad es hacer que Roslyn sea más fácil de escribir (y quizás más fácil de usar para los clientes).
Qwertie
3
@lukas Las estructuras de datos persistentes son más eficientes que la copia, cuando la estructura de datos suele ser mucho más grande que los cambios en ella. Tu punto, si tienes uno, está perdido para mí.
Qwertie