Skip to main content

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.

CallerRepositoryBranchCommitcommit(branchName, snapshot, message)1new Commit(snapshot, [branch.head])2moveTo(newCommit)3merge("feature", "main")4new Commit(merged, [main.head, feature.head])5
  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​

Repository- branches: Map<string, Branch>+ createBranch(name, fromBranch): void+ commit(branchName, snapshot, message): Commit+ merge(sourceBranch, targetBranch): Commit+ findMergeBase(a, b): CommitBranch- name: string- head: Commit+ moveTo(commit): voidCommit- id: string- snapshot: Map<string, string>- parents: List<Commit>- message: string+ isAncestorOf(other): bool
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.
0%0 of 122 pages studied