Inside Git: trees and commits

Intermediate

Introduction

Blobs store file contents but not names. Trees add the names and the folder structure, and commits add the history: who, when, why, and what came before. Together they form a simple structure in which one commit id fingerprints the entire project and its whole past. This is why Git can tell instantly whether two repositories have the same history.

How it works

A tree object lists the entries of one directory. Each entry has a mode (100644 for a normal file, 100755 for an executable, 040000 for a subdirectory), a name and the id of a blob or another tree. Entries are sorted by name, and each is stored as mode name\0 followed by the 20 raw bytes of the id. The tree's id is the hash of tree <size>\0 plus the entries. A snapshot of a whole project is its root tree.

A commit object is plain text:

tree 18eb80fbbbf9160491c007668d5298f1e86cd40a
parent 2c623d019401c86e05e6f585ee783b71d4992287
author Ada <ada@example.com> 1700000000 +0000
committer Ada <ada@example.com> 1700000000 +0000

Add the world file

It names the root tree, zero or more parents, the author (who wrote the change) and the committer (who recorded it), each with a Unix timestamp and a time zone, then a blank line and the message. Its id is the hash of commit <size>\0 plus that text. The first commit has no parent; a merge commit has two or more.

Because every id is a hash of content that includes other ids, the structure is a Merkle tree: changing one file changes its blob id, which changes its tree's entry and so the tree id, which changes the commit id, which changes the parent line of every later commit. You cannot alter old history without every following commit id changing, which everyone sharing the repository would notice.

git cat-file -p HEAD            # print the current commit object
git cat-file -p HEAD^{tree}     # print its root tree
git ls-tree -r HEAD             # every file in the snapshot with its blob id

Example

import hashlib


def object_id(kind, data):
    return hashlib.sha1(kind.encode() + b" " + str(len(data)).encode() + b"\0" + data).hexdigest()


def tree_id(files):
    entries = b""
    for name in sorted(files):
        blob = object_id("blob", files[name].encode())
        entries += b"100644 " + name.encode() + b"\0" + bytes.fromhex(blob)
    return object_id("tree", entries)


def commit(tree, parents, message, when):
    who = f"Ada <ada@example.com> {when} +0000"
    text = f"tree {tree}\n" + "".join(f"parent {p}\n" for p in parents)
    text += f"author {who}\ncommitter {who}\n\n{message}\n"
    return object_id("commit", text.encode()), text


files = {"a.txt": "hello\n", "b.txt": "world\n"}
first_tree = tree_id(files)
first, text = commit(first_tree, [], "First commit", 1700000000)
print(text, end="")
print("-> commit id", first)
files["b.txt"] = "world!\n"
second_tree = tree_id(files)
second, _ = commit(second_tree, [first], "Excite the world", 1700000600)
print("changing b.txt gives a new tree:", first_tree[:10], "->", second_tree[:10])
print("and a new commit whose parent is the first:", second[:10])
same_again, _ = commit(first_tree, [], "First commit", 1700000000)
print("the same tree, parents, author, date and message give the same id:", same_again == first)
Open in compiler

Line by line

  1. object_id hashes any object type with Git's header.
  2. tree_id sorts the names and joins one binary entry per file, as Git does for a directory.
  3. commit writes the commit text with tree, parents, author, committer and message, and hashes it.
  4. Changing one file gives a new tree id and therefore a new commit, whose parent line points to the first commit.
  5. Building the same commit again gives the same id: ids depend only on content.

Expected result

tree 18eb80fbbbf9160491c007668d5298f1e86cd40a
author Ada <ada@example.com> 1700000000 +0000
committer Ada <ada@example.com> 1700000000 +0000

First commit
-> commit id eb724ba0412d2ab72f128254f8fc6a6c9fdb9341
changing b.txt gives a new tree: 18eb80fbbb -> 710a439aac
and a new commit whose parent is the first: b7cbf28b69
the same tree, parents, author, date and message give the same id: True

In the real world

Signed commits and tags rely on this structure: signing one commit id vouches for the whole history behind it. Tools that rewrite history, such as git rebase or git filter-repo, necessarily produce new ids, which is why rewriting shared history causes trouble. Blockchains use the same Merkle idea to make their history tamper-evident.

Common mistakes

  • Thinking a commit stores only the changes: it points to a complete snapshot.
  • Confusing author and committer: they differ, for example, when someone applies another person's patch.
  • Expecting the same commit id after amending or rebasing: any change to the commit text changes its id.
  • Reading a timestamp as local time without its time zone.

Best practices

  • Use git cat-file -p to look at real tree and commit objects; they are small and readable.
  • Never rewrite commits that others have already fetched.
  • Keep author information correct in git config, because it becomes part of every commit id.

Summary

Trees map names to blob and subtree ids; commits point to a root tree, their parents, an author, a committer and a message. Every id is a hash of content containing other ids, so one commit id fingerprints the whole project and its history, and changing anything old changes every later id.

Quick check

1. What does a tree object store for each entry?
2. How many parents does a merge commit have?
3. You change one file in an old commit. What happens to later commit ids?
4. What is the difference between author and committer?

Key takeaways

  • A commit points to one tree, the snapshot of the project root, and to zero or more parents.
  • A change to any file changes its blob, every tree above it and the commit, so ids fingerprint whole histories.
  • Commits with two or more parents are merge commits; the first commit has none.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.