¿Cómo mantenemos actualizadas las estructuras de datos dependientes?

Suponga que tiene un árbol de análisis, un árbol de sintaxis abstracta y un gráfico de flujo de control, cada uno derivado lógicamente del anterior. En principio, es fácil construir cada gráfico dado el árbol de análisis, pero ¿cómo podemos gestionar la complejidad de actualizar los gráficos cuando se modifica el árbol de análisis? Sabemos exactamente cómo se ha modificado el árbol, pero ¿cómo se puede propagar el cambio a los otros árboles de una manera que no sea difícil de manejar?

Naturalmente, el gráfico dependiente puede actualizarse simplemente reconstruyéndolo desde cero cada vez que cambia el primer gráfico, pero entonces no habría forma de conocer los detalles de los cambios en el gráfico dependiente.

Actualmente tengo cuatro formas de intentar resolver este problema, pero cada una tiene dificultades.

1. Los nodos del árbol dependiente observan los nodos relevantes del árbol original, actualizándose a sí mismos y las listas de observadores de los nodos del árbol original según sea necesario. La complejidad conceptual de esto puede ser desalentadora.
2. Cada nodo del árbol original tiene una lista de los nodos del árbol dependiente que dependen específicamente de él, y cuando el nodo cambia, establece una marca en los nodos dependientes para marcarlos como sucios, incluidos los padres de los nodos dependientes hasta el fondo a la raíz Después de cada cambio, ejecutamos un algoritmo que se parece mucho al algoritmo para construir el gráfico dependiente desde cero, pero omite cualquier nodo limpio y reconstruye cada nodo sucio, haciendo un seguimiento de si el nodo reconstruido es realmente diferente del nodo sucio. Esto también puede ser complicado.
3. Podemos representar la conexión lógica entre el gráfico original y el gráfico dependiente como una estructura de datos, como una lista de restricciones, tal vez diseñada usando un lenguaje declarativo. Cuando el gráfico original cambia, solo necesitamos escanear la lista para descubrir qué restricciones se violan y cómo debe cambiar el árbol dependiente para corregir la violación, todo codificado como datos.
4. Podemos reconstruir el gráfico dependiente desde cero como si no hubiera un gráfico dependiente existente, y luego comparar el gráfico existente y el nuevo gráfico para descubrir cómo ha cambiado. Estoy seguro de que esta es la forma más fácil porque sé que hay algoritmos disponibles para detectar diferencias, pero todos son bastante costosos desde el punto de vista informático y, en principio, parece innecesario, por lo que evito deliberadamente esta opción.

¿Cuál es la forma correcta de lidiar con este tipo de problemas? Seguramente debe haber un patrón de diseño que haga que todo esto sea casi fácil. Sería bueno tener una buena solución para cada problema de esta descripción general. ¿Esta clase de problema tiene un nombre?

Permítanme detallar los problemas que causa este problema. Este problema aparece en varios lugares, cada vez que dos partes de un proyecto operan en gráficos, y cada gráfico es una representación diferente de lo mismo que cambia mientras se ejecuta el software. Es como hacer un adaptador para una interfaz, pero en lugar de envolver un solo objeto o un número fijo de objetos, necesitamos envolver un gráfico completo de tamaño arbitrario.

Cada vez que intento esto termino con un desorden confuso e imposible de mantener. El flujo de control de los observadores puede ser difícil de seguir cuando se complica, y el algoritmo para convertir un gráfico en otro suele ser lo suficientemente complicado como para seguirlo cuando se presenta de manera simple y no se extiende a través de múltiples clases. El problema es que parece que no hay forma de usar un algoritmo de conversión de gráfico simple y directo cuando el gráfico original está cambiando.

Naturalmente, no podemos usar un algoritmo de conversión de gráficos ordinario directamente porque eso no puede responder a los cambios de otra manera que no sea comenzar desde cero, entonces, ¿cuáles son las alternativas? Quizás el algoritmo podría escribirse en un estilo de paso continuo donde cada paso del algoritmo se represente como un objeto con un método para cada tipo de nodo en el gráfico original, como un visitante. Luego, el algoritmo puede ensamblarse componiendo varios visitantes simples.

Otro ejemplo: suponga que tiene una GUI que se presenta como lo haría en Java Swing, utilizando JPanels y gestores de diseño. Puede simplificar ese proceso mediante el uso de JPanels anidados en lugar de complejos administradores de diseño, por lo que terminará con un árbol de varios contenedores que incluye nodos que existen solo para fines de diseño y que, de lo contrario, no tienen sentido. Ahora suponga que el mismo árbol que se usa para generar su GUI también se usa en otra parte de su aplicación, pero en lugar de diseñar el árbol gráficamente, está trabajando con una biblioteca que generará un árbol de representación abstracta como un sistema de carpetas. Para usar esta biblioteca, necesitamos tener una versión del árbol que no tenga los nodos de diseño; los nodos de diseño deben aplanarse en sus nodos principales,

Otra forma de verlo: el concepto mismo de trabajar con árboles mutables viola la Ley de Demeter . Realmente no sería una violación de la ley si el árbol fuera un valor como lo son normalmente los árboles de análisis y los árboles de sintaxis, pero en ese caso no habría ningún problema ya que no sería necesario mantener actualizado. Entonces, este problema existe como resultado directo de la violación de la Ley de Demeter, pero ¿cómo se evita eso en general cuando su dominio parece estar relacionado con la manipulación de árboles o gráficos?

El patrón compuesto es una herramienta maravillosa para convertir un gráfico en un solo objeto y obedecer la Ley de Demeter. ¿Es posible usar el patrón Compuesto para convertir efectivamente un tipo de árbol en otro? ¿Se puede hacer un árbol de análisis compuesto para que actúe como un árbol de sintaxis abstracta e incluso un gráfico de flujo de control? ¿Hay alguna manera de hacerlo sin violar el principio de responsabilidad única ? El patrón compuesto tiende a hacer que las clases absorban todas las responsabilidades que tocan, pero tal vez podría combinarse con el patrón de la estrategia de alguna manera.

Creo que sus escenarios están discutiendo variaciones sobre el Patrón de Observador . Cada nodo original (" sujeto ") tiene (al menos) los dos métodos siguientes:

• registerObserver(observer) - agrega un nodo dependiente a la lista de observadores.
• notifyObservers()- llama x.notify(this)a cada observador

Y cada nodo dependiente (" observador ") tiene un notify(original)método. Comparando sus escenarios:

1. El notifymétodo reconstruye inmediatamente un subárbol dependiente.
2. El notifymétodo establece una bandera, la recalculación ocurre después de cada conjunto de actualizaciones.
3. El notifyObserversmétodo es inteligente y solo notifica a aquellos observadores cuyas limitaciones se invalidan. Esto probablemente usaría el Patrón de visitante , de modo que los nodos dependientes puedan ofrecer un método que decida esto.
4. (este patrón no tiene relación con la reconstrucción de la fuerza bruta)

Como las tres primeras ideas son solo variaciones en el patrón del observador, su diseño tendrá una complejidad similar (como sucede, en realidad están ordenadas en mayor complejidad; creo que №1 es el más simple de implementar).

Puedo pensar en una mejora: construir los árboles dependientes perezosamente . Cada nodo dependiente tendría una bandera booleana que se establece en valido invalid. Cada método de acceso verificará este indicador y, si es necesario, volverá a calcular el subárbol. La diferencia con №2 es que el recálculo ocurre en el acceso, no en el cambio. Esto probablemente resultaría en la menor cantidad de cálculos, pero puede generar dificultades significativas si el tipo de nodo tuviera que cambiar al acceder.

También me gustaría desafiar la necesidad de múltiples árboles dependientes. Por ejemplo, siempre estructuro mis analizadores de manera que emitan inmediatamente un AST. La información que solo es relevante durante la construcción de este árbol no tiene que almacenarse en ninguna estructura de datos permanente. Del mismo modo, también puede elegir sus objetos de tal manera que el AST tenga una interpretación como un gráfico de flujo de control.

Para un ejemplo de la vida real, la parte del compilador dentro del perlintérprete hace esto: el AST se construye de abajo hacia arriba, durante el cual algunos nodos se pliegan constantemente. En una segunda ejecución, los nodos se conectan en orden de ejecución, durante el cual las optimizaciones omiten algunos nodos. El resultado es un análisis muy rápido (y pocas asignaciones), pero optimizaciones muy limitadas. Cabe señalar que si bien dicho diseño es posible , probablemente no sea algo por lo que deba esforzarse: es uncompensación calculada violación completa del Principio de responsabilidad única .

Si realmente necesita varios árboles, también debe considerar si realmente deben construirse simultáneamente. En la mayoría de los casos, un árbol de análisis es constante después del análisis. Del mismo modo, un AST probablemente se mantendrá constante después de que se resuelvan las macros y se hayan ejecutado las optimizaciones de nivel AST.

Parece que está pensando en un caso general de 2 gráficos, donde el segundo se puede derivar por completo del primero, y desea volver a calcular de manera eficiente el segundo gráfico cuando una parte del primero cambia.

Esto no parece conceptualmente diferente al problema de minimizar el recálculo en solo el primer gráfico, aunque supongo que cuando se implementan en un sistema en particular, probablemente sean diferentes tipos en cada gráfico.

Se trata básicamente de rastrear dependencias, tanto dentro como entre gráficos. Para cada nodo que se cambia, actualice todos los dependientes, de forma recursiva.

Por supuesto, antes de hacer cualquier actualización, desea ordenar topológicamente su gráfico de dependencia. Esto le permite saber si tiene dependencias circulares que crean una ola potencialmente infinita de actualizaciones, y también asegura que para cualquier nodo actualizará todas sus dependencias antes de actualizar ese nodo, evitando así el cálculo sin sentido que tendrá que rehacerse más tarde.

En particular, no tiene que expresar las dependencias en un lenguaje declarativo, pero puede hacerlo, es un problema completamente independiente.

Este es un algoritmo general, y en casos particulares puede haber más que pueda hacer para acelerarlo. Puede ser que parte del trabajo que está haciendo para actualizar una dependencia también sea útil para actualizar otras dependencias, y un buen algoritmo se aprovecharía de eso.

En la medida en que el algoritmo de conversión de gráficos sea un desastre imposible de mantener, la solución es algo específica del lenguaje, pero un enfoque orientado a objetos podría ser tener algunas clases que se ocupen exclusivamente de actualizar las dependencias en general, representando dependencias, haciendo un tipo topológico y activando cálculos . Para hacer el cálculo, delegan a sus clases reales, posiblemente usando una función de primera clase que se les entregó cuando se crearon, posiblemente porque las clases a las que entregan deben implementar una interfaz (como de costumbre si no pueden, porque ejemplo, no los creaste, puedes usar un adaptador). Supongo que, en algunos casos, podría usar la reflexión para recopilar la información del gráfico del gráfico de relaciones de objeto y llamar a los métodos de esa manera, si eso es más fácil de configurar y no lo hace '

Mencionaste que sabes exactamente cómo se modificó el árbol, ¿sabrías cuándo?

¿Qué tal experimentar con HashTrees o cadenas Hash ( Merkle Tree ) o, en general, el concepto de detección de errores . Si los árboles son enormes, puede dividir, digamos, el primer gráfico en zonas N / 2 o raíz N y asignar hashes / sumas de comprobación a esas zonas. Los árboles dependientes mantendrían su propio conjunto de N / 2 o zonas de raíz N que dependen de las zonas de los primeros árboles. Cuando se detectan cambios en el primer árbol, actualice los nodos correspondientes en el árbol dependiente utilizando una búsqueda simple (ya que sabe lo que ha cambiado y, posteriormente, la suma de comprobación / hash para esa zona).

Otra representación del problema: tiene algunos datos (gráfico) y diferentes representaciones del mismo (por ejemplo, paneles de diseño / vista de árbol). Desea estar seguro de que cada representación sea coherente con otras representaciones.

Entonces, ¿por qué no tratas de llegar a la mayoría de las representaciones básicas y cambias la representación para ver la básica? Entonces es suficiente para cambiar uno básico, y las vistas seguirán siendo consistentes.

En el ejemplo de diseño: la primera representación es, digamos:

panelA(
    panelB(
        panelC(
            widget1
            widget2
        )
        panelD(
            widget3
        )
    )
    widget4
)

Entonces, lo convierte en una representación "más simple", lista de las siguientes tuplas:

[
    (panelA, panelB, panelC, widget1),
    (panelA, panelB, panelC, widget2),
    (panelA, panelB, panelD, widget3),
    (panelA, widget4),
]

Luego, mientras usa este gráfico con Swing, crea una vista, que convierte la representación anterior en un árbol especializado, y cuando la usa con una vista de árbol, tiene una vista que le devuelve solo una lista de los últimos elementos de la tupla.

¿Qué significa "simple" o "básico"? Lo más importante: debe ser fácil recurrir a cualquier vista (para que el cálculo de cada vista sea económico). Además, debe ser fácil de modificar desde cualquier vista.

Digamos que ahora queremos modificar esta estructura usando la vista de diseño. Debe traducir la llamada "panelC.parent = panelD" para "buscar cualquier lista que tenga panelD en ella, encontrar todas las listas que contengan panelC, reemplazar todos los elementos de esa lista, que van antes que panelC con parte de la primera lista antes de panelD con ella" .

Como señalaron otras personas, el observador PUEDE ser útil.

Si estamos hablando de árboles de análisis / AST / gráficos de flujo de control, no tenemos que notificar a ninguna vista que el gráfico haya cambiado, porque al usarlo lo inspeccionará, y la inspección activará dinámicamente la representación "básica" para ver la representación.

Si estamos hablando de Swing, el cambio a una vista debe notificarse en otras vistas, para que el usuario pueda ver el cambio.

Al final, esta es una pregunta muy específica para cada caso. Yo diría que la solución completa será muy diferente cuando la use para el diseño y para el análisis del lenguaje, y la solución completamente genérica será fea y cara como el infierno.

PD. La representación anterior es fea, creada ad-hoc, etc. Está destinada únicamente a mostrar el concepto, no la solución de la vida real.