Most people learn Git as a set of commands and a few scary ones to avoid. Under the commands is a much smaller thing: a directory of compressed files, each named by the hash of its contents, plus a handful of text files that point at some of them. Branches, history, merges and stashes are all built from that.
Building your own makes that small thing visible. You'll write a program that
stores files as blobs, directories as trees and snapshots as commits, in exactly
Git's format, so git log works on repositories your tool created. Then you'll
add the index, a commit command, log, diff and checkout, and finish by reading
the packfiles that real repositories keep most of their objects in.
01Why build this
You use Git every day, and when it surprises you, the explanation is almost always in the object model. Knowing it changes how you work:
- Scary commands stop being scary. A rebase makes new commits and moves a
ref. A reset moves a ref. Once you've written both operations,
reflogrecovery is obvious. - "Detached HEAD" becomes a sentence you understand.
HEADis a text file, and you'll have written the code that reads it. - Content addressing clicks. The same idea sits under Docker images, Nix, IPFS and deduplicating backup tools. See Chapter 32 for how object stores use it at scale.
- Monorepo performance makes sense. You'll know what the index caches,
why
git statusstats every file, and what a packfile saves.
It's probably the most satisfying project here to test, because there's a reference implementation on your machine. Every milestone ends with real Git agreeing with you, byte for byte.
02What you're building
Here's what your tool does when you run commit -m "fix" after staging a change:
?Why can't anyone change an old commit?
Because a commit's name is the hash of its contents, and those contents include its tree's hash and its parent's hash. Change one byte in an old file and its blob gets a new hash, so its tree does, so the commit does, and so does every commit after it. "Rewriting history" in Git always means writing new objects and moving refs to point at them.
03Before you start
| You need | Why | Where to get it |
|---|---|---|
| A language with SHA-1 and zlib | Every object is hashed and compressed | Standard library in Python and Go; crates in Rust |
The real git installed | It's your test oracle for every milestone | Your package manager |
| Comfort with binary formats | Trees, the index and packfiles aren't text | Practice with xxd on a few objects |
| A scratch directory per test | You'll create and delete many repos | mktemp -d |
| Basic filesystem knowledge | add and status rely on stat data | Chapter 08 |
04The roadmap
Nine milestones. The first four build the object model, the next four the commands on top, and the last one reads the packed format real repositories use.
Blobs and the object store
1 eveninginit creates .git/objects, .git/refs/heads and a HEAD file. An object is
a header (the type, a space, the size in bytes and a NUL) followed by the content.
Hash the header plus content with SHA-1, compress the same bytes with zlib, and
store them at objects/ plus the first two hex digits as a directory and the
remaining 38 as the filename.
Then write cat-file, which reverses it. Test both directions against real Git
before going on; nearly every later bug traces back to a header that's off by
one byte.
hash-object -w prints the same hash as git hash-object, and git cat-file -p prints your object back.Trees
1 weekendA tree lists a directory. Each entry is a mode, a space, a name, a NUL and then the child's hash as 20 raw bytes, not hex. Subdirectories are trees themselves, so you write them recursively from the bottom up.
The details decide whether your hash matches. Modes are written as 100644,
100755, 120000 for symlinks, and 40000 for directories, with no leading
zero. Entries are sorted by name, but a directory sorts as if its name ended in
/, which puts foo.txt before the directory foo.
write-tree on a nested directory produces the same root hash as git add -A then git write-tree in a copy of it.Commits, refs and HEAD
1 eveningA commit is plain text: a tree line, zero or more parent lines, author and
committer lines with a name, email, Unix timestamp and timezone offset, a blank
line, then the message. Write it as an object like any other.
Then make it reachable. A branch is a file under refs/heads/ holding a hash.
HEAD normally holds ref: refs/heads/main, a pointer to a pointer. Write a
resolve function that follows symbolic refs to a hash, and handle a HEAD that
holds a raw hash directly: that's detached HEAD.
git log in your repo shows your commit with the right author, date and message, and git fsck reports nothing.Log
1 eveningStart at HEAD, read the commit, print it, follow its first parent, and repeat
until a commit has no parent. That's --first-parent, and it's enough to get
going.
Merge commits have two or more parents, so full history is a graph walk. Use a
priority queue ordered by commit date and a set of visited hashes, or you'll print
shared ancestors twice. A clone will fail to read at first because its objects
are packed; run git unpack-objects on a copy, or jump ahead to milestone 9.
log on a clone of a small real project prints the same commits in the same order as git log --first-parent.The index
1–2 weekendsThe index (.git/index) is a binary file: a DIRC header, a version, an entry
count, then one entry per path with ctime, mtime, device, inode, mode, uid, gid,
size, the blob hash, flags and the path, padded with NULs. Optional extensions
may follow (skip any you don't know), and a SHA-1 of everything before it sits at
the end. Parse Git's own index before writing yours.
The stat fields are there for speed. If a file's size and mtime still match its
entry, Git assumes it hasn't changed and skips hashing it. Write them correctly,
or git status will think every file you touched is modified.
ls-files --stage matches git ls-files --stage, and after your add, real git status shows the file as staged and nothing else changed.Commit and status
1 weekendcommit builds trees from the index, not from the working directory. Group
entries by directory, write trees bottom up as in milestone 2, write the commit
with HEAD's commit as parent, and update the branch ref.
status compares three things: the HEAD tree against the index gives "staged",
the index against the working tree gives "not staged", and files in neither are
"untracked". Implementing it is probably the moment the staging area stops
feeling like an odd extra step.
add then commit makes a commit that real Git shows in git log -p, and your status lists staged, unstaged and untracked files the same way Git does.Diff
1–2 weekendsDiff in two layers. First compare trees: walk two trees in step, skip any subtree whose hash is the same on both sides (that's why diffing huge repos is fast), and collect paths that were added, removed or changed.
Then diff each changed file line by line. Implement Myers' algorithm, which finds a shortest edit script, and print it as unified hunks with three lines of context. Your output might differ slightly from Git's on ambiguous cases even with a correct algorithm, so test with edits whose minimal diff is unique.
diff between two commits prints the same unified hunks as git diff for a set of test edits: inserts, deletes, a moved block, and a change at the last line.Checkout and branches
1 weekendbranch writes a new ref file with the current commit hash. checkout diffs
the current tree against the target tree, then writes, deletes and changes the
mode of only the paths that differ, rebuilds the index, and points HEAD at the
new branch.
Before touching any file, check that it has no uncommitted changes. Git refuses a checkout that would overwrite local work, and yours has to as well, or the first real use destroys an afternoon of someone's edits.
branch dev, commit on it, checkout main and back again leaves the working tree and git status exactly matching each branch.Stretch: read packfiles
1–2 weekendsReal repositories keep most objects in .git/objects/pack/. The .idx file
has a 256-entry fanout table and sorted hashes, so you can binary search for an
object's offset. At that offset in the .pack, a variable-length header gives
the type and size, followed by zlib data.
Many objects, probably most in a large repository, are deltas: a reference to a base object (by offset or by hash) plus instructions to copy ranges from the base or insert new bytes. Resolve the base recursively, apply the instructions, and cache results, since delta chains can be long.
cat-file and log work on a fresh git clone of a real project without unpacking it first.05Traps that catch everyone
| Symptom | Cause | Fix |
|---|---|---|
| Your blob hash never matches Git's | Hashed the content without the header, or hashed the compressed bytes | Hash the header plus raw content, then compress |
| Tree hashes differ on nested directories | Wrong sort order, 040000 instead of 40000, or hex hashes instead of raw bytes | Sort directories as name/, drop the leading zero, write 20 raw bytes |
git log shows a wrong date or fails to parse | Timestamp written as a formatted date, or missing timezone | Write seconds since the epoch followed by an offset like +0000 |
git status shows every file as modified after your add | Stat fields in the index are zero or stale | Write real ctime, mtime, size and inode from stat |
| Git says the index is corrupt | Bad entry padding or a missing trailing checksum | Pad each entry with NULs to a multiple of 8 bytes; append the SHA-1 |
| Objects missing in a cloned repo | They're in packfiles, not loose | Look in packs, or unpack a copy while developing |
| Delta objects decode to garbage | The offset for OFS_DELTA uses a special varint | Add one before each shift, as in the pack format docs |
06Stretch goals
- Merge. Find the merge base, do a three-way merge per file, and write conflict markers when both sides changed the same lines.
- Clone over HTTP. Speak the smart HTTP protocol to fetch a packfile from a real server, then index it yourself.
- Write packfiles. Pack loose objects with delta compression, and compare your
pack size with
git gc. - SHA-256 repositories. Support Git's newer object format and see how much of your code assumed 20-byte hashes.
- Rebase. Replay a range of commits onto a new base, which is really a loop of diffs, applies and new commit objects.
07References worth your time
A literate Python implementation of objects, refs, the index and log. Short, readable, and close to this roadmap.
The chapter on plumbing, objects, refs and packfiles. Free online, and the best overview before you start.
A whole book that builds a Git clone in Ruby, including the index, diff, merge and packs, with the reasoning behind each design.
An essay that explains the object graph by showing how each command changes it. Her Gitlet is a heavily annotated Git in JavaScript.
The authoritative byte layouts for packfiles, pack indexes and the index. You'll need them for milestones 5 and 9.
The 1986 paper behind Git's default diff. Readable once you've drawn the edit graph for a small example.