Comment fonctionnent 'git log --graph' ou 'hg graphlog'?

Question

Je sais que l'histoire de Git est stocké dans une structure de données appelée un DAG. J'ai entendu parler de DFS et de savoir que c'est un peu lié.

Je suis curieux, comment faire des programmes tels que git log --graph ou hg graphlog tirer de l'histoire? J'ai toujours pensé que c'est assez compliqué à dessiner les voies et tout comme une belle façon.

Quelqu'un pourrait-il écrire le pseudo-code qui le démontre?

note: j'ai essayé de regarder autour de Git ou hg du code, mais il est très difficile de suivre et d'obtenir une idée générale de ce qu'il se passe.

Answer 1

Tout d'abord, on obtient une liste de commits (comme avec git rev-list), et les parents de chaque commit. Une colonne "liste de réserve" est conservé en mémoire.

Pour chaque commit alors:

• Si la validation n'a pas de colonne qui lui est réservé, l'attribuer à un libre de la colonne. C'est la façon dont les chefs de direction va commencer.
• Imprimer l'arborescence des graphiques en fonction de la colonne de la liste de réserve, et puis le message de commit
• La réserve de l'entrée de la liste pour la colonne/la validation est mis à jour avec le premier parent du commit courant, tels que le parent va être imprimé dans la même colonne.
• D'autres parents d'obtenir une nouvelle colonne libre.
• Si c'était une opération de fusion, la ligne suivante tente de lier le deuxième parent dans une colonne où la livraison est prévu (ce qui rend pour les boucles et le "≡ pont")

Exemple montrant la sortie de l' git-forest sur aufs2-util avec un bonus supplémentaire de s'engager à avoir plus d'une branche).[1]

Avec d'anticipation, on peut prévoir jusqu'à quel point de fusion point et à serrer le bois entre les deux colonnes pour donner un plus esthétique résultat [2].

Answer 2

J'ai essayé de regarder autour de Git ou hg du code, mais il est très difficile de suivre et d'obtenir une idée générale de ce qu'il se passe.

Pour hg, as-tu essayer de suivre le code de la hg lui-même, ou en graphlog?

Parce que le code de graphlog est assez court. Vous pouvez le trouver dans hgext/graphlog.pyet vraiment, l'important, c'est le top ~200 lignes, le reste est de l'extension de l'amorçage et de trouver la révision graphique sélectionné. La génération de code de la fonction est - ascii, avec son dernier paramètre étant le résultat d'un appel à l' asciiedge (l'appel lui-même est effectuée sur la dernière ligne de l' generate, la fonction fournie generate par graphlog)

Answer 3

Vous trouverez un autre exemple de graphe de journal git (en mode texte) avec tig ,
avec le code en tig.c .

Answer 4

Ce problème n'est pas si difficile que ça, par rapport à l'affichage graphique en général. Parce que vous voulez garder les nœuds dans l'ordre où ils ont été commis, le problème devient beaucoup plus simple.

Notez également que le modèle d'affichage est grille, les lignes sont les validations et les colonnes sont les bords dans le passé/futur.

Alors que je n'ai pas lu la source de git vous avez probablement juste de marcher sur la liste des commits, en commençant par le plus récent, et de maintenir une liste d'arêtes ouvertes dans le passé. Suivant les bords conduit naturellement à découpage/fusion de colonnes et vous vous retrouvez avec le genre de l'arbre git/hg affichage.

Lors de la fusion d'arêtes que vous souhaitez afin d'éviter la traversée d'autres bords, de sorte que vous aurez à essayer de commander vos colonnes à l'avance. C'est actally la seule partie qui peut ne pas être simple. Par exemple on pourrait faire un algorithme de deux passes, une colonne de commande pour les bords lors de la première passe et de faire le dessin dans la deuxième passe.

Answer 5

Je viens d'écrire un outil capable de générer de jolis graphes de commits git à l'aide de HTML / Canvas. Et la mise en œuvre de l'algorithme en python.

• code backend
• code frontal