¿Cómo funciona 'git loggraph' o 'hg graphlog'?

Question

Sé que el historial en Git se almacena en una estructura de datos llamada DAG. He oído hablar de DFS y sé que está relacionado de alguna manera.

Tengo curiosidad, ¿cómo los programas tales como git log --graph o hg graphlog dibujan la historia? Siempre pensé que era bastante complicado dibujar los carriles y todo de una manera tan agradable.

¿Podría alguien escribir algún pseudo código que lo demuestre?

nota: Intenté buscar el código de Git o hg, pero es muy difícil de seguir y tener una idea general de lo que está sucediendo.

Answer 1

Este problema en particular no es tan difícil, en comparación con la visualización de gráficos en general. Como desea mantener los nodos en el orden en que se cometieron, el problema se vuelve mucho más simple.

También tenga en cuenta que el modelo de visualización se basa en la cuadrícula, las filas son compromisos y las columnas son bordes en el pasado/futuro.

Si bien no leí la fuente de git, probablemente solo recorra la lista de confirmaciones, empezando por la más reciente y manteniendo una lista de bordes abiertos en el pasado. Seguir los bordes conduce naturalmente a dividir/fusionar columnas y terminas con el tipo de visualización tree git/hg.

Al fusionar bordes que desea evitar cruzar otros bordes, deberá intentar ordenar sus columnas con anticipación. Esta es, actalmente, la única parte que puede no ser sencilla. Por ejemplo, uno podría hacer un algoritmo de dos pasos, componiendo un orden de columnas para los bordes en el primer pase y haciendo el dibujo en el segundo pase.

Answer 2

He intentado buscar el código de Git o hg, pero es muy difícil de seguir y tener una idea general de lo que está sucediendo.

Para hg, ¿trataste de seguir el código en hg, o en el registro de gráficos?

Porque el código de graphlog es bastante corto. Puede encontrarlo en hgext/graphlog.py, y realmente la parte más importante es el top ~ 200 líneas, el resto es la inicialización de la extensión y encontrar el gráfico de revisión seleccionado. La función de generación de código es ascii, con su último parámetro es el resultado de una llamada a asciiedge (la llamada en sí se lleva a cabo en la última línea de generate, la función que se proporciona a generate por graphlog)

Answer 3

En primer lugar, se obtiene una lista de confirmaciones (como con git rev-list) y los padres de cada confirmación. Una "lista de reserva de columna" se mantiene en la memoria.

Para cada confirmación a continuación:

• Si la confirmación no tiene una columna que tiene reservado, asignarlo a una columna libre. Así es como comenzarán las cabezas de las ramas.
• Imprima los gráficos de árbol según la lista de reserva de columna y luego el mensaje de confirmación
• La entrada de la lista de reserva para la columna/confirmación actual se actualiza con el primer padre de la confirmación actual, de modo que el padre vaya a estar impreso en la misma columna.
• Otros padres obtienen una nueva columna gratuita.
• Si esto era una fusión, la siguiente línea se intenta vincular el segundo padre a una columna en la confirmación se espera que el (esto hace que para los bucles y el "≡ puente")

Ejemplo mostrando la salida de git-forest en aufs2-util con un compromiso adicional para tener más de una sucursal).

Con búsqueda hacia delante, se puede anticipar a qué distancia del punto de fusión será y exprimir la madera entre dos columnas para dar un resultado más estético.