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

Sé que la historia 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 progtwigs tales como git log --graph o hg graphlog dibujan el historial? 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é search el código de Git o hg, pero es muy difícil de seguir y tener una idea general de lo que está sucediendo.

Traté de search en 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 logging de charts?

Porque el código de graphlog es bastante corto. Puedes encontrarlo en hgext / graphlog.py , y realmente la parte más importante son las 200 líneas superiores, el rest es la initialization de la extensión y encontrar el gráfico de revisión seleccionado. La function de generación de código es ascii , siendo su último parámetro el resultado de una llamada a asciiedge (la llamada en sí misma se realiza en la última línea de generate , la function que se proporciona para generate mediante el graphlog de graphlog )

Primero, uno obtiene una list de commits (como con git rev-list ) y los padres de cada commit. Una "list de reserva de columna" se mantiene en la memory.

Para cada compromiso, entonces:

  • Si el compromiso no tiene una columna reservada para él, asígnelo a una columna libre. Así es como comenzarán las cabezas de las twigs.
  • Imprima los charts del tree de acuerdo con la list de reserva de columnas, y luego el post de confirmación
  • La input de la list de reserva para la columna / confirmación actual se actualiza con el primer padre de la confirmación actual, de modo que el padre se imprima en la misma columna.
  • Otros padres obtienen una nueva columna gratuita.
  • Si se trata de una fusión, la siguiente línea intentará vincular el segundo padre con una columna donde se espera el compromiso (esto hace que los loops y el "puente ≡")

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

Ejemplo

Con anticipación, uno puede anticipar cuán lejos estará el punto de fusión y exprimir la madera entre dos columnas para get un resultado más estético.

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

También tenga en count que el model 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 recorras la list de confirmaciones, empezando por la más reciente y manteniendo una list 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, debe evitar cruzar otros bordes, por lo que deberá tratar de orderar sus columnas con anticipación. Esta es, actalmente, la única parte que puede no ser sencilla. Por ejemplo, uno podría hacer un algorithm de dos pasos, componiendo un order de columnas para los bordes en el primer pase y haciendo el dibujo en el segundo pase.