Version Control System

A simplified Git: commits form a graph, branches are just movable labels pointing into that graph, and merging is "find where two labels diverged and combine what happened since." None of it needs a real diff algorithm to get the class model right.

Requirements

Functional

• Committing snapshots the current set of tracked files under a message, with a pointer back to the commit(s) it came from.
• A branch is a named pointer to a commit; committing on a branch moves that branch's pointer forward.
• Checking out a branch switches the working set to that branch's commit's snapshot.
• Merging branch B into branch A creates a new commit on A with two parents: A's tip and B's tip.

Non-functional

• Finding the common ancestor of two branches for a merge should walk the commit graph from both tips, not scan every commit ever made.
• Creating a branch must be a cheap pointer creation, not a copy of the repository's history.

Design

Commit is an immutable node with a snapshot and a list of parent commits (one parent for a normal commit, two for a merge) - the entire history is just commits chained by parent pointers, which is a graph, not a special "history" data structure. Branch is nothing more than a name and a mutable reference to one Commit; Repository owns the branches and does the walking.

1. 1The caller commits on a named branch - it never touches a Commit object directly.
2. 2A new commit is created with the branch's current tip as its single parent.
3. 3The branch pointer moves forward to the new commit - the old commit is still reachable, just no longer the tip.
4. 4To merge, the caller names two branches; the repository finds where they diverged.
5. 5The merge commit is the one place a commit gets two parents instead of one.

Finding a merge base is a graph problem solved with two graph tools: walk back from each tip collecting ancestor commit ids, then intersect - the first commit found in both walks (closest to the tips) is the merge base.

Class diagram

usescreates

Repository owns Branches; each Branch points at a Commit; Commits chain to their parents, forming the graph a merge walks.

Code

import java.util.*;

 

class Commit {

final String id;

final Map<String, String> snapshot;

final List<Commit> parents;

final String message;

 

Commit(String id, Map<String, String> snapshot, List<Commit> parents, String message) {

this.id = id;

this.snapshot = snapshot;

this.parents = parents;

this.message = message;

}

}

 

class Branch {

final String name;

private Commit head;

 

Branch(String name, Commit head) {

this.name = name;

this.head = head;

}

 

Commit getHead() { return head; }

void moveTo(Commit commit) { this.head = commit; }

}

 

class Repository {

private final Map<String, Branch> branches = new HashMap<>();

private int nextCommitId = 1;

 

Repository() {

Commit root = new Commit("c0", new HashMap<>(), List.of(), "initial commit");

branches.put("main", new Branch("main", root));

}

 

void createBranch(String name, String fromBranch) {

branches.put(name, new Branch(name, branches.get(fromBranch).getHead()));

}

 

Commit commit(String branchName, Map<String, String> snapshot, String message) {

Branch branch = branches.get(branchName);

Commit newCommit = new Commit("c" + (nextCommitId++), snapshot, List.of(branch.getHead()), message);

branch.moveTo(newCommit);

return newCommit;

}

 

private Set<String> ancestorIds(Commit start) {

Set<String> seen = new HashSet<>();

Deque<Commit> stack = new ArrayDeque<>(List.of(start));

while (!stack.isEmpty()) {

Commit current = stack.pop();

if (!seen.add(current.id)) continue;

stack.addAll(current.parents);

}

return seen;

}

 

Commit findMergeBase(String branchA, String branchB) {

Commit tipA = branches.get(branchA).getHead();

Commit tipB = branches.get(branchB).getHead();

Set<String> ancestorsOfA = ancestorIds(tipA);

 

Deque<Commit> queue = new ArrayDeque<>(List.of(tipB));

Set<String> visited = new HashSet<>();

while (!queue.isEmpty()) {

Commit current = queue.poll();

if (!visited.add(current.id)) continue;

if (ancestorsOfA.contains(current.id)) return current;

queue.addAll(current.parents);

}

throw new NoSuchElementException("No common ancestor for " + branchA + " and " + branchB);

}

 

Commit merge(String sourceBranch, String targetBranch) {

Branch target = branches.get(targetBranch);

Branch source = branches.get(sourceBranch);

findMergeBase(sourceBranch, targetBranch);

 

Map<String, String> mergedSnapshot = new HashMap<>(target.getHead().snapshot);

mergedSnapshot.putAll(source.getHead().snapshot);

 

Commit mergeCommit = new Commit(

"c" + (nextCommitId++),

mergedSnapshot,

List.of(target.getHead(), source.getHead()),

"merge " + sourceBranch + " into " + targetBranch

);

target.moveTo(mergeCommit);

return mergeCommit;

}

}

Design decisions

• Commits are immutable and only ever gain new commits pointing back at them - nothing is ever rewritten in place. A commit's parents, snapshot, and id never change once created; "undoing" a commit in a real system means creating a new commit that reverts it, never editing history, which is what keeps every branch's pointer trustworthy without a lock.
• A branch is a pointer, not a copy of history. Branch holds one Commit reference; creating a branch is assigning that reference to wherever the source branch currently points, which is why branching is fast regardless of how much history exists behind it.
• A merge commit has two parents instead of the model trying to represent one "primary" history. Once a commit can have more than one parent, the commit graph is a DAG rather than a straight line, and every question about history ("what's the common ancestor," "what changed since we diverged") becomes a graph traversal instead of a special case.
• What's missing for a real system: this page models the commit graph and merge-base discovery, not the merge itself - actually combining two snapshots' content into one (line-level diffing, conflict markers) is a separate, much larger algorithm that sits on top of this structure rather than inside it; a real VCS would also need the object store itself to be content-addressed so identical file content across commits is stored once.

Common follow-ups

• How would you support rebase instead of just merge? Rebase doesn't add a two-parent commit; it walks the commits unique to the source branch (since the merge base) and replays each one as a new single-parent commit on top of the target's tip, then moves the source branch pointer to the last replayed commit. The graph stays a clean line instead of gaining a merge node - the cost is that every replayed commit gets a new id, so anything referencing the old ids (a code review comment, a CI run) now points at commits that no longer exist on the branch.
• findMergeBase walks every ancestor of one tip into a set before touching the other - what's the cost on a repository with years of history? Both walks are O(history size) in the worst case since ancestorIds doesn't stop early. A real VCS bounds this with generation numbers or commit-date heuristics so the search can prune whole subtrees once it's clear they're older than any possible common ancestor, rather than walking the entire graph from both tips.
• What happens if createBranch is called concurrently with a commit on the source branch? As written, Branch.head is read once when the new branch is created; if a commit lands on the source branch in between the read and the write, the new branch could point at a commit that's about to be superseded, or (in a naive implementation) miss the update entirely. Branch.head needs to be read and copied atomically relative to moveTo, which in practice means both operations taking the same lock on the branch map.
• How would you detect a fast-forward merge and skip creating a merge commit? Before creating a two-parent commit, check whether the target branch's tip is itself an ancestor of the source branch's tip (isAncestorOf). If it is, no divergence happened - moving the target branch's pointer straight to the source's tip is correct and a merge commit would only add a needless node to an otherwise-linear history.

Check yourself

Question 1 of 3

Why does a merge commit have two parents instead of the model designating one branch as a "primary" history?