Tree Objects: Directory Snapshots

Blobs are anonymous content — no names, no permissions. Trees are where names live: a tree object is a directory listing, each entry pointing at a blob (a file) or another tree (a subdirectory) by hash. One tree hash therefore names an entire directory snapshot, recursively, forever. This is the object that turns a content store into a filesystem snapshot machine.

The entry format (binary — bring last lesson's discipline)

A tree's payload is a sequence of entries, each:

<mode> <name>\0<20-byte-binary-sha>

Concretely, a directory with README.md and src/:

100644 README.md\0⟨20 raw bytes⟩40000 src\0⟨20 raw bytes⟩

Three format facts that decide whether your hashes match real Git's:

• The SHA is 20 raw bytes, not 40 hex characters. The single most common build-your-own-git bug. Convert hex → binary before writing (bytes.fromhex / hex.DecodeString).
• Modes are ASCII octal, no leading zero on directories: 100644 regular file, 100755 executable, 120000 symlink, 40000 directory — written as 40000, not 040000 (Git is quirky here; match the quirk or mismatch every tree hash).
• No separators between entries — the fixed 20-byte SHA is what tells the parser where the next entry begins. (And now you see why parsing on strings dies: those 20 bytes can contain \0, newlines, anything.)

The sort rule — the other famous gotcha

Entries must be sorted by name, byte-wise — but directories sort as if their name ended with /. So foo.txt sorts before directory foo-bar but after directory foo … work an example:

foo      (dir  → sorts as "foo/")
foo.txt  (file → sorts as "foo.txt")

"foo.txt" < "foo/" byte-wise (. is 0x2E, / is 0x2F) — so the file comes first. Get the sort wrong and your tree's bytes differ → its hash differs → nothing you build agrees with Git ever again. Canonical form is the price of content addressing: same directory must always produce the same bytes.

Hash it like everything else

A tree is an object like any other: wrap the payload in tree <size>\0, SHA-1, store via your round-trip code. Nesting composes naturally — to hash a directory:

1. Recursively hash subdirectories (getting their tree hashes) and files (blob hashes).
2. Build this directory's entry list, sorted per the rule.
3. Hash the resulting tree payload.

Bottom-up, leaves first. And notice what one top-level tree hash now means: it cryptographically pins the entire project state — every filename, every mode, every byte of every file, recursively. Two trees with the same hash are the same project state, guaranteed. A commit (next lesson) needs only to point at one tree hash to snapshot everything.

Your exercise: Hash a Tree Object

Given a directory description, produce its Git tree hash: build entries (mode, name, NUL, raw-20-byte sha), sort with the directory-slash rule, wrap in the header, SHA-1. The graders probe exactly the classic mistakes: hex-instead-of-binary SHAs, 040000, and the file-vs-directory sort order — all three now labeled and defused. When it passes, run git ls-tree <hash> mentally: you can reconstruct the listing from bytes you know cold.