Skip to content
Tutorials Center
My learning

Topics

Lesson 73 of 78 ยท Projects

Project: Build a Tiny Git

Build a working mini version control system in about 160 lines of Bash: a content-addressable object store, index, commits, log, status, restore and integrity check, compared with real Git.

The best way to understand a tool is to build a small version of it. Git looks like a huge pile of commands, but its core is surprisingly small: a store where every piece of content is filed under the hash of that content, plus a few conventions for turning a set of files into a snapshot and a chain of snapshots into history. If you can write to a file and compute a SHA-1, you can write a version control system.

In this project you will build tg, a toy Git written in Bash with the tools every Linux system has: sha1sum, gzip, awk and sed. It supports init, add, commit, log, status, restore, verify and a way to look at stored objects. It is not meant to replace Git. It is meant to make the lessons on Git Objects, References and HEAD and The Index and Packfiles concrete. At the end you will compare your objects with real Git, and the ids will match.

This project is a toy for learning: it has one branch, no merging, no directories in trees and no packfiles, and its trees are plain text. Never store anything important in it. Real Git does all of this properly, quickly and safely.

Step 1: the object id

Everything in Git is an object, and every object has an id: the SHA-1 hash of a small header (<type> <size> followed by a NUL byte) and the content. Two files with identical content get the same id wherever and whenever they are hashed, and different content gives a different id. The id is the object's name and its address.

Before writing the tool, check that you can compute Git's ids yourself:

Bash Computing Git object ids by hand

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with read or cat), it gets the next line from this box.

The object_id function reproduces git hash-object exactly: for all four files the two lines match. Notice three things. hello.txt and copy.txt are different files with the same content, so they have one id: this is why Git stores duplicates only once. A missing trailing newline changes the content and so the id (no-newline.txt). And the empty file has the famous id e69de29..., which exists in every Git repository in the world. The last line shows that the plain sha1sum of the content is something else: the header matters, because it makes ids unique per type and size.

Step 2: the object store

tg keeps its data in a .tg directory. Objects are files named after their id, in a subdirectory made of the first two hex characters, as in Git: .tg/objects/ab/cdef.... That "fan-out" keeps any single directory from getting enormous. Each file contains the header, a NUL byte and the content, compressed (Git uses zlib, we use gzip).

Terminal
header() { printf '%s %d\0' "$1" "$(wc -c < "$2")"; }          # "<type> <size>" + NUL

hash_only() {                                                    # hash_only <type> <file>
  { header "$1" "$2"; cat "$2"; } | sha1sum | cut -d' ' -f1
}

store() {                                                        # store <type> <file> -> id
  local id path
  id=$(hash_only "$1" "$2")
  path=$GD/objects/${id:0:2}/${id:2}
  if [[ ! -e $path ]]; then
    mkdir -p "$GD/objects/${id:0:2}"
    { header "$1" "$2"; cat "$2"; } | gzip -n > "$path"
  fi
  echo "$id"
}

store computes the id and writes the object only if it does not exist yet. That one if is the whole deduplication feature, and it is also why an unchanged file costs nothing in a new commit. (gzip -n leaves out the file name and timestamp, so the compressed bytes are reproducible.) Reading is the reverse: decompress, read up to the NUL byte for the header, then the rest is the body. That is what object_type and object_body do with read -d '', which in Bash reads up to a NUL.

The same store function is used for all three kinds of object we need: blobs (file contents), trees (a snapshot listing) and commits.

Step 3: the index, trees and commits

The index is a plain text file with one path<TAB>id line per file. tg add hashes each file with store blob and updates its line in the index; that is all staging is.

tg commit does three things:

  1. It turns the index into a tree object: a text file with one blob <id> <path> line per entry. The tree is stored like any other object, so its id depends on every file name and every file id in it.
  2. It writes a commit object: the line tree <id>, a parent <id> line (unless this is the first commit), an author line with a timestamp, an empty line and the message.
  3. It writes the new commit id into .tg/refs/heads/main, the file .tg/HEAD says is the current branch.
Terminal
cmd_commit() {
  [[ ${1:-} == -m && -n ${2:-} ]] || die "usage: tg commit -m <message>"
  local tmp tree parent id
  tmp=$(mktemp)
  awk -F'\t' '{ printf "blob %s %s\n", $2, $1 }' "$GD/index" > "$tmp"
  tree=$(store tree "$tmp")
  parent=$(head_id)
  {
    echo "tree $tree"
    if [[ -n $parent ]]; then echo "parent $parent"; fi
    echo "author ${TG_AUTHOR:-Ada} ${TG_TIME:-$(date +%s)}"
    echo
    echo "$2"
  } > "$tmp"
  id=$(store commit "$tmp")
  rm -f "$tmp"
  echo "$id" > "$GD/$(sed 's/^ref: //' "$GD/HEAD")"
  echo "[main ${id:0:7}] $2"
}

The commit id therefore depends on the tree, the parent, the author and time, and the message. Change anything and you get a different id. History is a linked list through parent ids, and tg log simply follows parent lines until there is none. A branch is nothing but a file holding a commit id; that is why branches in real Git are so cheap.

Step 4: a first session

The example below writes the complete tg script with a here-document (read it from top to bottom, every function from this lesson is in it) and then uses it. Because the commit time comes from the TG_TIME variable, set by the tg wrapper function, every id in the output is reproducible.

Bash The complete tg script and a first session

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with read or cat), it gets the next line from this box.

Look at the output:

  • Both commits report an abbreviated id, like Git does ([main add0351] ...).
  • tg log walks from the newest commit back through the parent link. tg cat HEAD shows a commit object: the tree line, the parent line pointing to add0351..., the author and the message. Its tree lists two blobs: docs/notes.txt and hello.txt.
  • 7 objects were stored: the first commit created 2 blobs, 1 tree and 1 commit; the second commit created only 1 new blob (the changed hello.txt), a new tree and a new commit. notes.txt was not copied: its blob is shared by both trees. Snapshots, with deduplication, is the whole trick.

Step 5: status, restore and verify

Three more commands show why this design is powerful.

  • tg status compares three things: the files on disk, the index, and the tree of the last commit. A line starting with a letter in the first column (A, M) is staged, a letter in the second column ( M, D) is a change in the working directory, and ?? is an untracked file. This is the same two-column layout as git status -s. It is the three areas from How Git Works in about twenty lines of code.
  • tg restore HEAD reads the commit's tree and writes every file back. Deleted files reappear. This is git restore or git checkout in miniature: a commit is a complete snapshot, so recovering it is just reading the blobs.
  • tg verify re-hashes every object and compares the result with the object's name. If someone (or a failing disk) changes an object, the hash no longer matches. This is git fsck.
Bash tg status, restore and verify

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with read or cat), it gets the next line from this box.

The first status lists M hello.txt (changed on disk, not staged) and ?? todo.txt (not tracked). After tg add, both are staged: A todo.txt and M hello.txt. After deleting two files, they show as D. tg restore HEAD rewrites them from the stored blobs, and the cat proves the old content is back.

Then the tamper test: the script overwrites one object with different content. tg verify reports CORRUPT e38d7f... and exits with status 1. Think about what this means for history: a commit contains the id of its tree, the tree contains the ids of its blobs, and the next commit contains the id of its parent. Changing one old file means a different blob id, a different tree id, a different commit id and different ids for every later commit. You cannot alter the past without everybody noticing. Hashes chained like this are called a Merkle DAG, and it is the reason a signed tag or a single commit id can vouch for an entire project history.

Step 6: compare with real Git

The last test: store the same files in tg and in real Git and compare. The blobs are byte-for-byte compatible, because we used Git's header and SHA-1.

Bash Comparing tg with real Git

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with read or cat), it gets the next line from this box.

The two blob lines are identical: our tree object names the same ids as git ls-files -s, and diff prints identical. The trees and commits differ, for good reasons:

Part tg Git
Blob id SHA-1 of header and content the same
Compression gzip zlib (deflate)
Tree text, one flat list of full paths binary entries of mode, name and 20-byte id, one tree per directory
Commit author name and timestamp name, email, timestamp and timezone, plus a separate committer
Storage one file per object, always loose objects at first, packfiles with deltas later
Refs one branch, main many branches, tags, remote-tracking refs, packed refs
Extras none merges, rebases, diffs, hooks, remotes...

That is why tree 61f5860... in Git's commit differs from our tree id: the tree bytes are different, so the hash is different. Nothing about the idea differs. If you want to see Git's own binary trees, Git Objects shows how to build a commit by hand with the plumbing commands.

Ideas to extend your tiny Git

  1. Add tg branch <name> and tg switch <name>: a branch is a file in .tg/refs/heads/, and HEAD holds ref: refs/heads/<name>. Switching is a restore of that commit's tree.
  2. Make tg log --oneline print abbreviated-id message lines.
  3. Add tg diff, comparing the working file with the stored blob using diff on object_body output.
  4. Make trees nested (one tree object per directory) so that unchanged directories share a tree id.
  5. Make tg verify also check that every tree and parent id mentioned in a commit exists (a connectivity check, as git fsck does).
  6. Replace sha1sum with sha256sum and see how every id changes; real Git can do this too (git init --object-format=sha256, when your Git was built with it).

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why do hello.txt and copy.txt, two different files with the same content, produce one object?

    Objects are addressed by a hash of their content. The same content always hashes to the same id, so storing it again is a no-op.
  2. 2. What does a tree object contain in tg (and, in a binary form, in Git)?

    A tree is a directory listing: names with the ids of the blobs (and sub-trees) they refer to. A commit then points at one tree.
  3. 3. You change one byte of a file in the very first commit of a repository. What happens to the ids?

    Each commit includes its parent's id, so a change ripples forward through the whole chain. That is why history is tamper-evident.
  4. 4. What does tg verify (like git fsck) check?

    It decompresses each object, hashes it again and compares the result with the file name. A mismatch means the object was altered or damaged.
  5. 5. Which part of tg is byte-compatible with real Git?

    Blob ids use Git's own format (type, size, NUL, content, SHA-1), so they match git hash-object. Trees, commits and compression differ.

Summary

  • Git is a content-addressable store: an object's id is the SHA-1 of <type> <size>, a NUL byte and the content, and the object is filed under ab/cdef....
  • There are three object types you need: blob (file content), tree (a snapshot listing) and commit (tree, parents, author, message).
  • The index is just a sorted list of path and blob id; add stores blobs and updates it, commit turns it into a tree and a commit.
  • A branch is a file containing a commit id; HEAD says which one is current; log follows parent ids.
  • Identical content is stored once, and a change anywhere changes every id after it, so history is tamper-evident (fsck/verify).
  • Real Git adds binary nested trees, zlib, packfiles with deltas, many refs, merging and a network protocol, but the model is the one you just built.

Next: Project: Quality Gates with Hooks