Git in the page (P35)

Loom is Git written in plain JavaScript that runs in the page. It reads and writes Git's own formats, so a repository Loom makes is one Git accepts, and a repository Git makes is one Loom reads.

The objects

Git stores four kinds of object: a blob holds a file's bytes, a tree lists names with their modes and ids, a commit names its tree, its parents, its author and committer and its message, and an annotated tag names an object. An object's id is the SHA-1 of its kind, its size and its bytes.

Loom has its own SHA-1, its own inflate and deflate, and its own Adler-32 and CRC-32. It sorts a tree the way Git does: by name as bytes, with a folder compared as if its name ended in a slash.

Packs

A pack holds many objects one after another, each a small header and a zlib stream, with no lengths between them. Many objects are stored as a delta against another object: a list of copies from the base and new bytes. Loom's inflate reports where each stream ended, so Loom can read a pack from its first byte. It resolves every delta, works out every id and writes the .idx, the index Git uses to find an object in the pack. Loom also writes packs, with deltas from an encoder of its own.

The working tree

The repository page has a working tree of files, the index and the objects, kept in IndexedDB in the browser. You edit a file, see it as changed, stage it and commit it. You create and switch branches, tag a commit and reset a branch. The history is drawn as lanes, with each commit's message, author and id.

Diff

The diff is Git's xdiff written again. Before Myers' algorithm runs, the lines both files share at the start and the end are set aside, and so are lines that have no match on the other side. Patience and histogram diff are there too. After the diff, each group of changed lines is moved up or down to where Git's indent heuristic puts it. The output is git diff's: hunk headers with three lines of context, the function line Git shows after each header, "No newline at end of file", binary files and renames.

Merge

A merge works as Git's ort strategy does. It finds the merge bases of the two commits. When there is more than one, as after criss-cross merges, it merges the bases first into a virtual base. Renames are found on each side first, exact ones and then files at least half alike. A file renamed on one side and changed on the other is merged at its new name. Then each file is merged: a side that did not change takes the other side's version, a file both sides changed is merged line by line, and a file one side changed and the other deleted is a conflict. A file renamed to two names, renamed on one side and deleted on the other, or renamed to a name the other side added, is a conflict as Git reports it. Conflicts are written with Git's markers, and you resolve them in the page.

Blame

Blame starts with every line belonging to the newest commit. Commits are taken newest first, and each one passes the lines it did not change on to its parents, found by diffing each parent's file against its own. The lines no parent takes belong to that commit. When a parent does not have the file, blame looks for the name it had there, as git blame follows a rename.

Download

Download gives the whole repository as a zip or a tar of a folder with its .git inside and its files beside it. Unpack it and run git log, git status or git fsck. The same archive opens again in Loom.

Clone

Clone speaks Git's protocol version 2 over HTTP. It asks for the refs with ls-refs, then for the objects with fetch, want and done. The pack comes back on side-band 64k with the server's progress messages, and a Web Worker inflates it and resolves its deltas. GitHub does not let a browser call its Git server, so the clone goes through this site's Worker. The Worker passes Git's protocol on to github.com for public repositories, and keeps nothing.

Held against Git

A script builds 19 scripted histories, five of them merges with renames, and 70 random ones with Git 2.50.1, with fixed authors, dates and time zones. It records Git's answers: every object id, git log, git diff with Myers and patience, git merge-base, git merge-tree and git blame. The page against Git builds the same histories with Loom and compares every answer, character for character.

The other way, Loom writes each history as loose objects and as a pack with its own deltas, and Git checks it with git fsck --strict, git verify-pack, git log and git status.

Previous: RISC-V computer (P34). Next: Verifiable election (P36).