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.

Answer 2

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.

For hg, did you try to follow the code in hg itself, or in graphlog?

Because the code of graphlog is pretty short. You can find it in hgext/graphlog.py, and really the important part is the top ~200 lines, the rest is the extension's bootstrapping and finding the revision graph selected. The code generation function is ascii, with its last parameter being the result of a call to asciiedge (the call itself is performed on the last line of generate, the function being provided to generate by graphlog)