The Index (Staging Area)

Every git tutorial says "git add stages your changes". Here is what that means. Git juggles three snapshots of your project, the index is the middle one, and git status is nothing but two comparisons among the three. After this lesson your program reads a real .git/index file byte by byte, lists its entries the way git ls-files -s does, and produces the output of git status.

The three trees

1. HEAD: the snapshot you last committed, frozen in the object store.
2. The index: the snapshot your next commit will be. A real file, .git/index: a sorted list of path -> mode, hash entries plus file metadata.
3. The working tree: the actual files you are editing. Unhashed bytes on disk.

git add file hashes the file's current contents into a blob and updates that path's entry in the index. The file is not moved; a snapshot of it entered the index. Edit it again and the index still holds the old snapshot. git commit writes the index out as tree objects, wraps a commit around the top tree and advances the branch. The index is not a queue of changes. It is the draft of the next tree.

The index file

"DIRC"            4 bytes   signature
version           4 bytes   big-endian, 2 here
entry count       4 bytes   big-endian
entries           one per path, sorted by path
extensions        zero or more: 4-byte name, 4-byte size, data   (TREE, REUC, ...)
checksum          20 bytes  SHA-1 of every byte before it

Each version-2 entry is 62 fixed bytes, then the path, then zero bytes until the entry's total length is a multiple of 8 (at least one zero byte always follows the path):

ctime  seconds, nanoseconds        8 bytes     (file metadata, used to spot changes cheaply)
mtime  seconds, nanoseconds        8 bytes
dev, ino                           8 bytes
mode                               4 bytes     type bits and permissions, 0x81a4 is octal 100644
uid, gid                           8 bytes
size                               4 bytes
hash                              20 bytes     the blob's SHA-1, raw
flags                              2 bytes     bits 12-13 stage, low 12 bits path length
path                               n bytes, then 1 to 8 zero bytes

A real entry for a six-byte file a.txt, in hex: 6ac82d62 025037d0 ctime, 6ac82d62 026091c0 mtime, 00000000 00000000 dev and ino, 000081a4 mode, 00000000 00000000 uid and gid, 00000006 size, ce013625030ba8dba906f756967f9e9ca394464a hash, 0005 flags (path length 5, stage 0), 612e747874 the path, and 0000000000 five zero bytes of padding that bring the entry to 72 bytes. The stage is 0 for a normal entry. During a merge conflict the same path appears three times, with stages 1 (base), 2 (ours) and 3 (theirs). A path of 4095 bytes or more stores 0xfff in the length field and is found by looking for its terminating zero byte. Version 3 and 4 files add and compress fields and are not handled here.

git status = two diffs and a scan

• HEAD vs index is "Changes to be committed": a path in the index with a different hash than in HEAD is a staged modification; in the index but not HEAD is a new file; in HEAD but not the index is a staged deletion.
• Index vs working tree is "Changes not staged for commit": hash the working file and compare it with the index entry; missing means deleted.
• In the working tree but not in the index is "Untracked files".

One path can appear in both of the first two lists. Stage an edit, then edit again, and both comparisons are true. They are independent.

Common mistakes

• Reading the 4-byte numbers little-endian. Everything in the index is big-endian.
• Padding every entry by a fixed amount instead of rounding it up to a multiple of 8, or reading the path length with the stage bits still in the field.
• Treating extension bytes after the last entry as more entries. The entry count says where the entries stop.
• Reporting a staged-then-edited file in only one section.

Your exercise

The starter reads commands and prints for you. You write parse_index, which turns the file's bytes into entries or one of the error messages, and status_lines, the three comparisons. The index files in the tests were written by real git add, including ones with a TREE extension, a conflict, a symlink, a submodule and a very long path, and the status cases were compared with git status --porcelain.