algorithm - How does 'git log --graph' or 'hg graphlog' work?

Question

I know that the history in Git is stored in a data structure called a DAG. I've heard about DFS and know it's somewhat related.

I'm curious, how do programs such as git log --graph or hg graphlog draw the history? I always thought it's quite complicated to draw the lanes and everything in such a nice way.

Could someone write some pseudo code that demonstrates it?

note: I tried looking around Git or hg's code but it's very hard to follow and get a general idea of what's going on.

Answer 1

First, one obtains a list of commits (as with git rev-list), and parents of each commit. A "column reservation list" is kept in memory.

For each commit then:

• If the commit has no column reserved for it, assign it to a free column. This is how the branch heads will start.
• Print the tree graphics according to the column reservation list, and then the commit message
• The reservation's list entry for the current column/commit is updated with the first parent of the current commit, such that the parent is going to be printed in the same column.
• Other parents get a new free column.
• If this was a merge, the next line will try to link the second parent to a column where the commit is expected (this makes for the loops and the "≡ bridge")

Example showing output of git-forest on aufs2-util with an extra commit to have more than one branch).

With lookahead, one can anticipate how far down the merge point will be and squeeze the wood between two columns to give a more aesthetically pleasing result.