How version control works: commits, history, and merge bases

A version control system records the history of a project as snapshots called commits. In Git, each commit stores its content, a message, and pointers to its parent commits. Because a commit points to its parents, history forms a directed acyclic graph (DAG): a commit with one parent is ordinary, and a merge commit has two or more.

Python

import hashlib
import json

commits = {}


def commit(message, parents):
    body = json.dumps({"message": message, "parents": parents}, sort_keys=True)
    commit_id = hashlib.sha256(body.encode()).hexdigest()[:8]
    commits[commit_id] = {"message": message, "parents": parents}
    return commit_id


def ancestors(commit_id):
    seen = {commit_id}
    stack = [commit_id]
    while stack:
        for parent in commits[stack.pop()]["parents"]:
            if parent not in seen:
                seen.add(parent)
                stack.append(parent)
    return seen


def depth(commit_id):
    parents = commits[commit_id]["parents"]
    return 0 if not parents else 1 + max(depth(parent) for parent in parents)


root = commit("init", [])
parser = commit("add parser", [root])
main = commit("add tests", [parser])
feature = commit("add lexer", [parser])
merged = commit("merge feature", [main, feature])

common = ancestors(main) & ancestors(feature)
base = max(common, key=depth)
print(commits[base]["message"])
print(sorted(commits[c]["message"] for c in ancestors(merged)))
print(commit("init", []) == root)

Read the full lesson