read-tree: Walking a Snapshot

Trees nest: a directory holds subdirectories, which hold more. git ls-tree -r walks a tree recursively and prints every file with its full path. After this lesson your program stores real tree objects, finds them by hash, and prints exactly what git ls-tree and git ls-tree -r print for them.

One level at a time

A tree stores only the leaf name of each entry, never a path. The parent tree holds util as a subtree entry, and the subtree holds str.c. The full path app/util/str.c exists only in the head of the walker that joined the pieces. This is what lets one directory tree be shared by many commits and many places: its bytes do not depend on where it sits.

git ls-tree <tree> prints one line per entry of that one tree:

<mode, 6 digits> SP <type> SP <hash> TAB <name>

The mode is zero padded to six digits (040000), and the type comes from the mode: 40000 is tree, 160000 is commit (a submodule), everything else is blob. A tab, not a space, separates the hash from the name, because a name may contain spaces.

The recursion

-r replaces every tree entry by what is inside it, and prints only the leaves. A tree is stored once and addressed by hash, so recursing means: look the hash up, decode that tree, and walk its entries with a longer prefix. In words:

walk(tree, prefix):
    for each entry of the tree, in stored order:
        path = prefix + name
        if the entry is a tree: walk(that tree, path + "/")
        else: print the entry with its path

This is pseudocode for the order of operations; each language spells it differently. Take a small project and its output:

Makefile            100644
app.txt             100644
app/                040000   (a subtree)
    main.c          100644
    util/           040000   (a subtree)
        str.c       100644

ls-tree -r prints Makefile, app.txt, app/main.c and app/util/str.c in that order. Notice app.txt comes before app/. In the stored tree a directory sorts as if its name ended in /, and the walk keeps stored order, so the output is already sorted by full path. You never sort; if you do, you risk breaking git's order.

Special entries

• Submodules (mode 160000) point at a commit in another repository. There is no tree to open. -r prints the entry itself, with type commit, and does not recurse.
• Symlinks (mode 120000) are blobs whose content is the link target. They print as blobs.
• A subtree can be empty. It contributes no lines to -r.

Why a flat list matters

-r produces the project as a flat list of (path, mode, hash). Almost everything later compares two such lists: checkout, status and diff all start by flattening trees. The index you meet soon is exactly this list, stored on disk.

Common mistakes

• Printing the subtree entry as well as its contents under -r.
• Joining paths with the wrong separator or forgetting the slash between the prefix and the name.
• Printing the mode as stored. 40000 must read 040000.
• Sorting the output yourself with a plain string sort of names, which moves app before app.txt.
• Recursing into a submodule entry, which has no tree.

Your exercise

The starter decodes a tree payload into entries for you, as you did for cat-file -p. You write ls_tree, which prints one tree, or the whole walk with -r, and reports the missing-object cases listed in the exercise. The trees in the tests were written by real git, including a five-level nesting, a submodule, a symlink and a directory whose name sorts around a file's.