Version Control System Core (Java)

Overview

Version Control System Core is a from-scratch implementation of a local version control system written in Java, designed to demonstrate core data structures, algorithms, and systems-level reasoning.

Unlike typical “Git clone” projects that focus on surface-level commands, this project focuses on the internal mechanics of a VCS:

• Content-addressable storage
• Immutable snapshots
• Commit graph traversal
• Branching and merging
• Three-way merge with conflict detection
• Disk persistence

The system is built incrementally: first fully in-memory, then extended with on-disk persistence, mirroring real-world systems engineering practices inspired conceptually by :contentReference[oaicite:0]{index=0}.

---

Key Design Principles

1. Immutability

   • Blobs, trees, and commits are immutable once created.
   • Any modification produces a new object.

2. Content-Addressable Storage

   • Objects are identified by cryptographic hashes.
   • Identical content is stored only once.

3. Separation of Concerns

   • In-memory logic is cleanly separated from disk persistence.
   • Commands do not perform raw file I/O directly.

4. Data-Structure-Driven Design

   • Every VCS concept maps directly to a fundamental data structure.

---

Architecture Overview

---

Core Components Explained

1. Repository

Purpose
Acts as the single source of truth for the VCS state.

Responsibilities

• Maintains the staging area
• Tracks the current HEAD commit
• Coordinates commit creation

Data Structures Used

• HashMap<String, Blob> for staging (O(1) access)
• Linked commit references for history traversal

---

2. Blob (File Snapshot)

Purpose
Represents an immutable snapshot of a file’s content.

Key Properties

• Stores raw content as byte[]
• Computes a SHA-1 hash from content
• Enforces immutability (no setters)

Why this matters
Files are treated as content, not filenames, enabling deduplication and integrity checks.

---

3. Tree (Directory Snapshot)

Purpose
Represents the complete directory structure at a commit.

Implementation

• N-ary tree using HashMap<String, TreeNode>
• Nodes represent either directories or files (Blob references)

Why a tree
Filesystem structure is hierarchical; trees allow efficient snapshotting and traversal.

---

4. Commit (History Node)

Purpose
Represents a snapshot in time.

Contains

• Commit message
• Timestamp
• Parent commit reference
• Root tree snapshot

Graph Model

• Commits form a Directed Acyclic Graph (DAG)
• Enables history traversal, branching, and merging

---

5. Branching

Concept
A branch is a named pointer to a commit, not a copy of history.

Implementation

• HashMap<String, Commit> mapping branch names to commit heads
• Branch switching only reassigns pointers

Result

• O(1) branch operations
• No data duplication

---

6. Merge System (Advanced)

This project implements a true three-way merge, not a naïve overwrite.

Merge Inputs

• BASE: Lowest Common Ancestor (LCA)
• OURS: Current branch HEAD
• THEIRS: Target branch HEAD

Process

1. Find the LCA using graph traversal
2. Compare changes:
   • BASE → OURS
   • BASE → THEIRS
3. Apply deterministic merge rules
4. Detect conflicts when both sides diverge differently

Algorithms Used

• Graph traversal with HashSet for LCA detection
• Three-way comparison logic
• Standard conflict markers

---

7. Diff Engine

Purpose
Compares different versions of file content.

Algorithm

• Longest Common Subsequence (LCS)

Complexity

• Time: O(m × n)
• Space: O(m × n)

This demonstrates dynamic programming fundamentals.

---

Persistence Layer

After completing the in-memory system, disk persistence was added.

Disk Layout