Tree Objects: Directory Snapshots

Blobs are anonymous content with no names and no permissions. Trees are where names live: a tree object is a directory listing whose entries point at blobs (files) or other trees (subdirectories) by hash. One tree hash therefore names an entire directory snapshot, recursively. After this lesson your program takes a directory listing and prints the exact tree hash real git computes for it.

The entry format

A tree's payload is a run of entries with nothing between them:

<mode as octal text> SP <name> NUL <20 raw hash bytes>

A one-file directory, hello.txt holding the blob 3b18e512dba79e4c8300dd08aeb37f8e728b8dad, has a 37-byte payload:

31 30 30 36 34 34 20            "100644" and a space
68 65 6c 6c 6f 2e 74 78 74 00   "hello.txt" and a zero byte
3b 18 e5 12 ... 8b 8d ad        the hash as 20 raw bytes (not 40 hex characters)

Wrap that in tree 37 and a zero byte, take the SHA-1, and you get 68aba62e560c0ebc3396e8ae9335232cd93a3f60, which is what git mktree prints for it.

Three format facts decide whether your hashes match git's:

• The hash is 20 raw bytes, not 40 hex digits. Hex-in-a-tree is the classic first bug. Convert before writing.
• Modes are octal text with no leading zero: 100644 regular file, 100755 executable, 120000 symlink, 160000 submodule, and 40000 for a directory. Git's own listings print the directory as 040000, so the input you receive may carry the zero. The bytes you hash must not.
• No separators between entries. The fixed 20-byte hash is what tells the parser where the next entry starts.

The sort rule

Entries are sorted by name, compared as bytes, with directories compared as if their name ended in /. Canonical form is the price of content addressing: the same directory must always produce the same bytes.

foo-bar   file         sorts as "foo-bar"       ('-' is 0x2d)
foo.txt   file         sorts as "foo.txt"       ('.' is 0x2e)
foo       directory    sorts as "foo/"          ('/' is 0x2f)
foo0      file         sorts as "foo0"          ('0' is 0x30)

So the stored order is foo-bar, foo.txt, foo, foo0. A plain sort by name gives foo first and every hash after that is wrong. Comparing bytes also means Z comes before a and an accented letter (two UTF-8 bytes starting at 0xc3) comes after every ASCII letter.

Bottom up

To hash a project you hash leaves first: blobs for files, then each directory's tree from its children's hashes, then the parent. Your tree hash for a directory changes if any file below it changes, in any depth, and equals another directory's hash only if every name, mode and byte below is the same. A commit (next lesson) needs only one tree hash to pin a whole project state.

Common mistakes

• Writing the 40 hex characters of the hash instead of the 20 bytes behind them.
• Writing the mode 040000 for directories, which gives a different hash from git's 40000.
• Sorting by name alone, ignoring that a directory sorts as if followed by a slash.
• Splitting an input line on every space when a name contains one. The name is everything after the second space.
• Comparing names as text in a language where that is not bytewise, so a non-ASCII name lands in the wrong place.

Your exercise

The input lists several directories. For each one, build the entries, sort them, wrap them in the header and print the SHA-1. The starter reads the listings for you and gives you the entries unsorted, exactly as typed; you write hash_tree. The expected answers were produced by real git mktree.