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

Model a commit graph as hashes and parents, and find the common ancestor used to merge branches.

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)

Output

add parser
['add lexer', 'add parser', 'add tests', 'init', 'merge feature']
True

Explanation

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.

Commits are content-addressed: an identifier is computed by hashing the commit's content. Identical content gives an identical identifier, and changing anything, including a parent, changes the identifier. A branch is just a movable name that points at one commit, so creating a branch is cheap. This model hashes JSON with SHA-256 and keeps only messages and parents. Real Git hashes its own object format (SHA-1 by default, with SHA-256 repositories supported) and also stores file snapshots.

To merge two branches, Git finds their merge base: the nearest commit that is an ancestor of both. A three-way merge compares each branch's changes against that base and combines them, and it reports a conflict only where both sides changed the same lines differently. The program builds a small history with a feature branch and a merge, computes ancestors with a graph traversal, and finds the merge base as the deepest commit in the common-ancestor set.

Explore the dry run

Guided walkthroughReady

1import hashlib

2import json

4commits = {}

7def commit(message, parents):

8 body = json.dumps({"message": message, "parents": parents}, sort_keys=True)

9 commit_id = hashlib.sha256(body.encode()).hexdigest()[:8]

10 commits[commit_id] = {"message": message, "parents": parents}

11 return commit_id

14def ancestors(commit_id):

15 seen = {commit_id}

16 stack = [commit_id]

17 while stack:

18 for parent in commits[stack.pop()]["parents"]:

19 if parent not in seen:

20 seen.add(parent)

21 stack.append(parent)

22 return seen

25def depth(commit_id):

26 parents = commits[commit_id]["parents"]

27 return 0 if not parents else 1 + max(depth(parent) for parent in parents)

30root = commit("init", [])

31parser = commit("add parser", [root])

32main = commit("add tests", [parser])

33feature = commit("add lexer", [parser])

34merged = commit("merge feature", [main, feature])

36common = ancestors(main) & ancestors(feature)

37base = max(common, key=depth)

38print(commits[base]["message"])

39print(sorted(commits[c]["message"] for c in ancestors(merged)))

40print(commit("init", []) == root)

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
The identifier is a hash of the commit's content, including its parents, so it names exactly that history.	`—`	—
A merge commit has two parents: the tips of both branches.	`merged has parents main and feature`	—
Commits reachable from both branch tips are init and add parser.	`common = {init, add parser}`	—
The merge base is the deepest common ancestor, 'add parser', where the branches diverged.	`common = {init, add parser}`	—
Identical content produces the identical identifier: content addressing.	`common = {init, add parser}`	add parser ['add lexer', 'add parser', 'add tests', 'init', 'merge feature'] True

Cost and common mistakes

Finding ancestors is O(V + E) over commits and parent links. depth is recomputed here for clarity; caching it makes the whole search linear.

A branch is only a pointer to a commit. Deleting a branch does not delete the commits unless nothing else reaches them.
The simple 'deepest common ancestor' works for this history. Git's algorithm also handles criss-cross merges, where more than one candidate base can exist.
Rewriting published history (for example force-pushing after a rebase) changes commit identifiers and can confuse collaborators.

Try it yourself

What is the merge base of merged and feature in the example?

Reveal answer and reasoning

feature itself. It is an ancestor of merged, and it is the deepest commit reachable from both, so the merge base is 'add lexer'.

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

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading