Come funziona 'git log --graph' o 'hg graphlog'?

Question

So che la cronologia di Git è memorizzata in una struttura dati chiamata DAG. Ho sentito parlare di DFS e so che è in qualche modo correlato.

Sono curioso, come programmi come git log --graph o hg graphlog disegnano la cronologia? Ho sempre pensato che fosse piuttosto complicato disegnare le corsie e tutto in un modo così carino.

Qualcuno potrebbe scrivere qualche pseudo codice che lo dimostra?

nota: ho provato a guardare il codice di Git o hg ma è molto difficile da seguire e avere un'idea generale di cosa sta succedendo.

Answer 1

Questo particolare problema non è difficile, rispetto al display grafico in generale. Perché vuoi mantenere i nodi nell'ordine in cui sono stati commessi, il problema diventa molto più semplice.

Si noti inoltre che il modello di visualizzazione è basato sulla griglia, le righe sono commit e le colonne sono spigoli nel passato/futuro.

Mentre non ho letto la sorgente git, probabilmente si cammina semplicemente nell'elenco di commit, a partire dal più recente, e si mantiene un elenco di spigoli aperti nel passato. Seguire i bordi porta naturalmente alla divisione/fusione delle colonne e si finisce con il tipo di visualizzazione dell'albero git/hg.

Quando si uniscono i bordi, si desidera evitare di attraversare altri bordi, quindi è necessario cercare di ordinare le colonne in anticipo. Questa è in pratica l'unica parte che potrebbe non essere semplice. Ad esempio si potrebbe fare un algoritmo a due passaggi, creando un ordine di colonna per i bordi nel primo passaggio e facendo il disegno nel secondo passaggio.

Answer 2

Ho provato a cercare il codice di Git o hg ma è molto difficile da seguire e avere un'idea generale di cosa sta succedendo.

Per hg, hai provato a seguire il codice in hg stesso o in graphlog?

Perché il codice di graphlog è piuttosto breve. Lo puoi trovare in hgext/graphlog.py, e in realtà la parte più importante sono le prime ~ 200 linee, il resto è il bootstrap dell'estensione e trovare il grafico di revisione selezionato. La funzione di generazione del codice è ascii, con il suo ultimo parametro è il risultato di una chiamata al asciiedge (chiamata stesso viene svolta nell'ultima riga della generate, la funzione essendo previsto per generate da graphlog)

Answer 3

Innanzitutto, si ottiene una elenco di commit (come con git rev-list) e genitori di ogni commit. Una "lista di prenotazione di colonne" viene mantenuta in memoria.

Per ogni commit poi:

• Se il commit non ha una colonna riservata per esso, assegnarlo a una colonna libera. In questo modo inizieranno le diramazioni.
• Stampa la grafica ad albero in base all'elenco di prenotazione della colonna e quindi il messaggio di commit
• La voce di elenco della prenotazione per la colonna/commit corrente viene aggiornata con il primo genitore del commit corrente, in modo tale che il genitore stia per essere stampato nella stessa colonna
• Altri genitori ricevono una nuova colonna gratuita.
• Se questo fosse un unione, la riga successiva tenta di collegare il secondo genitore per una colonna in cui il commit viene previsto (questo rende per i loop e la "≡ ponte")

Esempio di uscita git-forest su aufs2-util con un commit aggiuntivo per avere più di un ramo).

Con lookahead, si può anticipare quanto in basso il punto di fusione sarà e spremere il legno tra due colonne per dare un risultato esteticamente più gradevole.