Exercises — Git internals — objects (blob, tree, commit, tag), DAG structure

1. blob — pure content, no name.
2. tree — a directory listing entry (mode, type, hash, name).
3. commit — snapshot pointer (tree + parents + author + message).
4. tag (annotated) — a named, signed pointer to another object.

(a) 0 parents (root commit). (b) 1 parent. (c) 2 parents (this is the only place history fans in). Octopus merges can have more, but the standard two-branch merge is exactly 2.

Content is "" (zero bytes), so $\text{size}=0$: $\text{store}=\text{"blob 00"}$ $SHA1(\text{"blob 00"})=\text{e69de29bb2d1d6434b8b29ae775ad8c2e48c5391}$ It is recognisable because every empty file in every Git repo produces this same hash — content-addressing means identical (here, empty) content ⇒ identical key. See Hashing & SHA-1 for why one flipped bit changes the whole digest.

The content is 3 bytes: h i \n. So: $\text{store}=\text{"blob 30hin"}$ Git computes $SHA1(\text{store})$. The point of the exercise is the framing: the header is blob 3\0 where 3 is the content length, not the store length. Feeding just hi\n (no header) to a raw SHA-1 tool gives a different, wrong hash.

First commit: 1 new blob (hi\n → B), 1 new tree (T listing hello.txt→B), 1 new commit (C, 0 parents). Second commit: 0 new blobs — notes.txt has the same bytes hi\n, so same store, same hash B, already stored. 1 new tree (T2 now lists two entries; its bytes changed so its hash changed). 1 new commit (C2 with tree=T2, parent=C). Totals across both commits: 1 blob, 2 trees, 2 commits.

A commit's hash is $SHA1(\text{store})$ where store includes the parent hashes. To make commit $X$ list commit $Y$ as parent, $Y$'s hash must already exist — i.e. $Y$ was created before $X$. For a cycle you'd need $X$'s hash to appear inside $Y$'s content, but $Y$ was hashed before $X$ existed. You cannot embed a hash of content that mentions your own not-yet-computed hash — that's a fixed-point you cannot solve for SHA-1. Hence edges only ever point backward in time: directed + acyclic = a DAG. This is the same argument that makes persistent structures safe to share.

Blob reused: content is unchanged, so hash B is identical — no new blob. New tree: the directory listing now says ... B summary.txt instead of ... B report.txt; the tree's bytes changed → new tree hash. New commit: points to the new tree, parent = previous commit. Rename detection works because the same blob hash B appears under a different name in old vs new tree. Git sees "a name disappeared, an identical-content name appeared" and reports a rename. If the name were baked into the blob, B would differ and this heuristic would fail.

The blob's content changed → its hash changes. Its parent tree lists that blob's hash, so that tree changes. Every ancestor tree up to the root tree changes in turn. The commit lists the root tree hash → the commit hash changes. Every later commit lists its parent's hash → all descendant commits change. Finally the branch ref (a pointer, see Branches and HEAD) would have to be re-pointed. This is the Merkle tree property: a single leaf change propagates hash changes all the way to the root — tamper-evidence. You cannot secretly edit history; every hash above the edit betrays it.

Edges (each is "child points to parent"):

• $C1\to C0$
• $C2\to C1$
• $C3\to C1$
• $C4\to C3$ and $C4\to C2$ (merge → two edges)

Parent counts: $C0$: 0 (root). $C1,C2,C3$: 1 each. $C4$: 2 (merge, history fans in). Note $C1$ is where history fans out (two children $C2$, $C3$) and $C4$ is where it fans in. Fan-out is branching; fan-in is merging. It is still acyclic — every arrow points to an earlier commit.

git branch -d feature deletes only the ref .git/refs/heads/feature — a 40-char pointer file, not any object. C2 is still reachable: C4 lists C2 as a parent, and C4 is reachable from main. So C2 (and its tree/blobs) survive fully. C2 becomes lost only if it were left unreachable from all refs and HEAD (e.g. an abandoned commit that no branch or merge references) and then git gc prunes it after its reflog entries expire. Reachable objects are never collected.

Walk from C:

1. Read commit C → get its root tree hash T (and parent list, empty here).
2. Read tree T → each entry gives (mode=100644, type=blob, hash=B, name=app.py).
3. For each blob entry, read blob B → write its content print("hi")\n to a file named app.py with mode 100644. For any sub-tree entry, recurse into that tree, creating a subdirectory.

The commit needs to store only the root tree hash because the tree is a full recursive snapshot: names, modes, and child hashes all live in trees (Merkle DAG). No diffs are needed because each commit is a complete snapshot — you reconstruct state directly, never by replaying changes. That is the whole payoff of the content-addressed, snapshot-based model.

The tree hash is $SHA1(\text{store})$ over the directory listing bytes (modes, names, child hashes) only. If both projects have identical layout and identical file contents, every blob hash matches, so every tree entry matches, so the root tree's store bytes are identical → same tree hash T. This is deduplication one level up from blobs. Yet C_a \ne C_b because a commit's store also includes the message, author, committer timestamps, and parent hash — all different here. So the same tree can be shared by many commits while each commit stays unique. The single unifying fact: hashing is over exactly the bytes you frame, nothing more — trees hash their listing, commits hash their metadata + tree + parents. Same input bytes ⇒ same hash; any differing byte ⇒ different hash (Hashing & SHA-1).

"A blob is nameless bytes. A tree is a labelled tray of hashes. A commit is a photo of the whole room that also points at the previous photo. Because each photo points backward, I can walk history but never circle — you can't photograph a photo that doesn't exist yet. Deleting a branch tears up a sticky-note pointer, not the photos; the photos vanish only when nothing points to them and the cleaner (gc) comes by."