git : i rebuilt git so it would teach me about itself
I use git every day. I had no idea what was actually inside .git. That bothered me. So I rebuilt it myself, the object model, from scratch.
(turns out it's just files and folders, that's getting hashed and encrypted)
blob 12\0hello world
Type, space, length, a null byte, then the content. That's the entire format of a git object.
Why the header looks like that
Okay so why not just store "hello world" directly. Because git needs to know two things before it can read the content back: what kind of object this is (blob, tree, commit) and how many bytes to read. The type comes first. Then the length, so git knows exactly where the content ends, useful for binary content that might contain anything including more null bytes. Then the null byte marks the end of the header, unambiguous because the length is decimal digits, a null byte can't be mistaken for part of a number.
Byte by byte, that first line looks like this:
b'blob' + b' ' + b'12' + b'\x00' + b'hello world'
4 1 2 1 12 <- bytes
Take that whole string, header and content together, and hash it:
(hashing the header too, not just the content, means a blob and a tree with identical bytes still get different hashes. type is part of the identity)
Then gzip the result with zlib, and write it to disk at .git/objects/xx/rest, where xx is the first two hex characters of the hash and rest is the other 38.
Why the folder split
Splitting on the first two hex chars isn't required for correctness, it's just to avoid dumping every object a repo has ever created into one folder. Two hex chars gives 256 possible subfolders, so a repo with even a few hundred thousand objects still only has a manageable number of files per folder.
Read it back with cat-file and it's the same thing in reverse. Unzip, read up to the null byte, get the type and length, read exactly that many bytes of content. Done. The whole "object database" of git is just compressed files named after their own hash.
Now the more interesting part. write-tree.
Trees are a graph, not a file
A directory becomes a tree object. A tree is a list of entries, and each entry is a mode, a name, and a hash. A regular file gets mode 100644. A folder gets mode 40000, and its hash points to another tree object, not a blob.
So write_tree walks a directory, and for every subfolder it finds, it recurses into that subfolder first, writes that as its own tree object, gets a hash back, and only then writes the entry for it in the parent tree. Bottom up. By the time you're back at the root, every folder underneath it has already been turned into an object.
blobs at the bottom, trees pointing at trees, the root tree on topThe bug that ate an evening
A tree entry doesn't store the hash as the 40 character hex string you're used to seeing. It stores the raw 20 bytes. Hex is for humans, for typing into cat-file, for folder names. Raw bytes are for machines, for what actually goes inside a tree entry.
I only ever returned the hex string from my hash function. So every tree entry got 40 ASCII bytes shoved into a slot meant for 20 raw bytes. The tree object wrote fine, no crash, nothing obviously wrong. It just pointed at references that didn't exist. Took a while to notice because the failure was silent.
(there should be a warning light for this. hex string walks into a function expecting raw bytes, everything just... continues)
Fixed it by keeping both forms around. Compute the raw 20 byte digest once, hex-encode it only when I need to print it or build a folder path, use the raw bytes everywhere else.
Commands working right now: init, hash-object, cat-file, write-tree. Commit and ls-tree are next. (empty files in the repo, just sitting there)
Do I need any of this to use git day to day. No, git already works. But now when git does something odd, I know which folder it's looking in and roughly what it's going to write there. That part isn't a mystery to me anymore.