Walking History (git log)

You've built commits — objects pointing at trees and at parent commits. Stack enough of them and you own a data structure: history is a directed acyclic graph (DAG), and git log is nothing more mysterious than a graph traversal starting from where you stand. This lesson makes you the one doing the walking.

History is a graph, not a list

Each commit stores zero or more parent hashes:

• 0 parents — the root commit (there's exactly one way to have no history).
• 1 parent — the normal case: a straight line of work.
• 2+ parents — a merge commit: two histories flowing together.

A ← B ← C ← D        (main)
     ↖
       E ← F         (feature)

Arrows point backward — children know their parents, parents know nothing of their children. This is a profound design choice: commits are immutable, and since a parent hash is baked into a commit's content (and therefore its SHA), you couldn't add "child pointers" without changing every ancestor's hash. History only grows forward; it can only be read backward. Every git operation that "looks at history" — log, blame, bisect, merge-base — is a backward walk over this graph.

The walk

To list history from a starting commit: read the commit object, emit it, look up its parents, repeat. For a straight line that's just pointer-chasing. Merges make it a real traversal:

frontier = [start]
seen = {}
while frontier not empty:
    take the commit C from the frontier
    if C in seen: continue          ← the crucial line
    mark C seen, emit C
    add C's parents to the frontier

The seen set is not an optimization — it's correctness. Below a merge, both parent lines eventually reach common ancestors; without the set you'd emit shared history twice (or loop forever in your test's diamond graphs). Any commit reachable through two paths — and every commit below a merge is — must be emitted exactly once. This is textbook graph traversal (BFS with the frontier as a queue, DFS with a stack), applied to version control.

What order does real git use?

If you've stared at git log, you know it interleaves branches by commit date (a priority queue on timestamp, newest first) — good for humans, but dates are set by the committer's clock and can lie. For algorithms, git walks in topological order (git log --topo-order): every commit appears before any of its parents — children first, ancestors after. Your exercise specifies its expected order precisely; implement exactly that. The deliverable skill is the same one underneath all orderings: a correct, deduplicated reachability walk.

Your exercise: Walk a Commit Graph

You're given commits with parent lists and a starting point; emit the reachable history in the specified order. The three bugs that produce almost every wrong answer: forgetting the seen set (duplicates below merges), visiting parents in the wrong sequence when a commit has several (the spec fixes first-parent-first or similar — read it), and starting the walk after instead of at the start commit (log includes where you stand). Get this walk right and you've implemented the engine inside git log, git rev-list, and half of git merge — the same fifteen lines, wearing different flags.