Walking History (git log)

You can now build commits, objects that point at trees and at parent commits. Stack enough of them and you own a data structure, and git log is nothing more mysterious than a traversal of it. After this lesson your program reads real commit objects, rebuilds their graph and prints history in the order git log does.

History is a graph, not a list

Each commit stores zero or more parent hashes:

• 0 parents: the root commit.
• 1 parent: the normal case, a straight line of work.
• 2 or more: a merge, where two histories flow together.

A <- B <- C <- M        (main)
      \       /
       D ----+          (feature)

Arrows point backward. A commit knows its parents, and a parent knows nothing of its children, because a parent's hash is baked into the child's bytes and cannot gain a child pointer without changing its own name. History only grows forward and can only be read backward. Every command that looks at history (log, blame, bisect, merge-base) is a backward walk over this graph.

The walk, with a priority queue

git log shows the newest commit first, by committer timestamp. The walk keeps a frontier, the commits that are known but not yet printed:

1. Put the starting commit in the frontier and mark it as seen.
2. Take the commit with the newest timestamp out of the frontier and print it.
3. For each of its parents that has not been seen, mark it seen and add it to the frontier.
4. Repeat until the frontier is empty (or enough commits were printed).

A worked trace on commits you will not meet in the tests. Times are in parentheses. A (10) is the root, B (20) its child, C (30) and D (25) both children of B, and M (40) merges C and D:

frontier         pop   print   add
[M40]            M     M       C30, D25
[C30, D25]       C     C       B20
[D25, B20]       D     D       (B already seen)
[B20]            B     B       A10
[A10]            A     A

The result is M, C, D, B, A. The seen set is not an optimisation, it is correctness: below a merge both parent lines reach the shared ancestors (B above is reached twice), and without it you would print B twice.

Order is a policy

Timestamps come from people's clocks, and clocks lie. If a commit is dated earlier than its parent, the queue still prints the child first, because the parent only joins the frontier after the child is printed. A solution that sorts all commits by time and prints them in one go gets this wrong. Git also offers other orders (--topo-order guarantees children before parents, --first-parent follows only the first parent of each merge, ignoring the branch that was merged in). This exercise asks for the date-ordered walk and the first-parent variant. When two commits have equal timestamps, print the smaller hash first.

Reading a commit

You read the same format you wrote last lesson. The header lines come first, up to the first empty line. Lines starting with parent there are parents. The committer line ends with a timestamp and a zone after the closing >. Everything after the first empty line is the message, and its first line is the subject. Be careful about the order: a message line that happens to begin with the word parent is not a parent, and a header can be spread over several lines (a signature continues on lines that start with a space).

Common mistakes

• Printing a commit twice below a merge because there is no seen set.
• Sorting all commits once by timestamp instead of walking from the start, which breaks when a clock was wrong.
• Taking parent lines from the message as well as the header, or the author's time instead of the committer's.
• Starting after the start commit instead of at it.
• Following a parent that was never provided. This exercise says what to do.

Your exercise

The starter stores every commit you are given under its real hash and prints your walk. You write parse_commit and walk. The commits in the tests come from real repositories, including one with a skewed clock and one with a signature header, and the expected order for the ordinary graphs was checked against git log.