MyVCS - A Git-like Version Control System

Overview

MyVCS is a sophisticated C++ implementation of a distributed version control system inspired by Git. It provides enterprise-grade functionality for managing code repositories with content-addressable storage, intelligent branching and merging, and cryptographic integrity verification.

Key Features

Core Functionality

• Content-Addressable Storage: All objects indexed by SHA-256 cryptographic hashes for immutable, verifiable storage
• Git-Compatible Object Model: Full support for Blobs (file content), Trees (directory structure), Commits (version snapshots), and Tags (named references)
• Advanced Branching: Complete branch management with efficient reference tracking and branch operations
• Intelligent Merging: Three-way merge algorithm with automatic conflict detection and manual resolution support
• Staging Area: Index-based workflow enabling selective commit preparation
• Commit History: DAG-based commit graph supporting linear and merge commit history
• Comprehensive Diff: Myers' longest common subsequence algorithm for minimal, readable diffs

Architecture Highlights

• Separation of Concerns: Layered architecture with distinct storage, object model, algorithm, and command layers
• Object Immutability: Cryptographic hash validation ensuring data integrity
• Efficient Caching: In-memory LRU cache for frequently accessed objects reducing disk I/O
• Binary Serialization: Optimized binary index format for fast loading and minimal file size
• Merkle Tree Structure: Deterministic tree hashing enabling deduplication and integrity verification

Quick Start

Installation & Building

# Clone repository
git clone <repository-url>
cd MyVCS

# Create build directory
mkdir build
cd build

# Configure and build
cmake -G Ninja ..
ninja

# Verify installation
./bin/myvcs --help

Setting Up Custom Alias (Windows PowerShell)

For easier command-line usage, you can set up a custom alias using the provided PowerShell script:

# Navigate to Scripts directory
cd Scripts

# Run setup script (default alias: 'slate')
powershell -ExecutionPolicy Bypass -File setup_alias.ps1

# Or customize the alias name by editing ALIAS_NAME in setup_alias.ps1
# Example: Change "slate" to "vcs" or any preferred name

What the script does:

• Creates a PowerShell alias for MyVCS (default: slate)
• Adds the alias to your PowerShell profile for persistence
• Allows customization by editing the $ALIAS_NAME variable in the script

Usage after setup:

slate init .              # Instead of myvcs init .
slate add .               # Instead of myvcs add .
slate commit -m "..."     # Instead of myvcs commit -m "..."

Note: Restart PowerShell after running the script for changes to take effect permanently.

Initial Setup

# Navigate to project directory
cd /path/to/project

# Initialize new repository
myvcs init .

# Configure user identity (optional)
myvcs config user.name "Your Name"
myvcs config user.email "your@email.com"

Basic Workflow

# Stage files for commit
myvcs add .

# View staging status
myvcs status

# Create commit with message
myvcs commit -m "Initial commit"

# View commit history
myvcs log
myvcs log --oneline

# Create and switch to feature branch
myvcs branch feature-xyz
myvcs checkout feature-xyz

# Make changes and commit
myvcs add modified-file.cpp
myvcs commit -m "Implement feature XYZ"

# Switch back to main and merge
myvcs checkout main
myvcs merge feature-xyz

# Clean up feature branch
myvcs branch -d feature-xyz

Project Structure

MyVCS/
├── include/myvcs/              # Public API headers
│   ├── core/                   # Repository, Index, Config, References
│   ├── objects/                # Blob, Tree, Commit, Tag classes
│   ├── storage/                # ObjectStore, Serializer
│   ├── algorithms/             # Diff, Merge, Graph traversal
│   ├── commands/               # CLI command implementations
│   └── utils/                  # Utilities, exceptions, logging
├── src/                        # Implementation files
├── tests/                      # Unit and integration tests
├── docs/                       # Comprehensive documentation
│   ├── ARCHITECTURE.md         # System architecture details
│   ├── ALGORITHMS.md           # Algorithm complexity analysis
│   ├── API_REFERENCE.md        # C++ API documentation
│   └── complexity_analysis.md  # Space and Time Complexity
├── examples/                   # Example scripts
├── Scripts/                    # Utility scripts
│   └── setup_alias.ps1         # PowerShell alias setup script
└── CMakeLists.txt             # Build configuration

Command Reference

Repository Initialization

init

Initialize a new MyVCS repository in the specified directory.

myvcs init [directory]

Creates: .myvcs/ directory with complete repository structure including object storage, reference files, index, and configuration.

Example:

myvcs init .                    # Current directory
myvcs init /path/to/project    # Specific directory

---

Staging & Committing

add

Stage files for the next commit.

myvcs add <files...>

Arguments:

• . - Stage all files in current directory
• *.cpp - Pattern matching
• path/to/file - Specific files or directories

What happens:

1. Reads file content and computes SHA-256 hash
2. Creates Blob object and stores in ObjectStore
3. Adds entry to staging Index
4. Saves Index to disk for next commit

Examples:

myvcs add .                     # Stage everything
myvcs add src/main.cpp          # Single file
myvcs add include/*.h           # Pattern
myvcs add src/ tests/           # Multiple paths

commit

Create a new commit from staged changes.

myvcs commit -m <message> [-a <author>]

Options:

• -m, --message - Commit message (required)
• -a, --author - Override author identity (optional)

What happens:

1. Loads all staged files from Index
2. Builds Merkle tree reflecting directory structure
3. Creates Commit object with tree reference and metadata
4. Updates branch reference to new commit
5. Clears Index for next staging cycle

Examples:

myvcs commit -m "Initial commit"
myvcs commit -m "Fix critical bug in parser"
myvcs commit -m "Refactor utility functions" -a "Jane Doe <jane@example.com>"

---

History & Inspection

log

Display commit history.

myvcs log [--oneline] [-n <count>]

Options:

• --oneline - Condensed format (hash + message)
• -n, --max-count - Limit number of commits displayed

Output:

• Full format: Commit hash, parent, author, date, and message
• Oneline format: 7-char hash and message first line

Examples:

myvcs log                       # Full history
myvcs log --oneline             # Condensed view
myvcs log --oneline -n 10       # Last 10 commits

status

Show repository state and pending changes.

myvcs status

Displays:

• Current branch
• Staged changes (ready for commit)
• Unstaged changes (modified but not staged)
• Untracked files (new files not in repository)

Color coding:

• Green: Staged changes
• Red: Unstaged or untracked

diff

Show differences between versions.

myvcs diff [--staged] [<commit1> <commit2>]

Modes:

• No args: Working directory vs. Index (staged)
• --staged: Index vs. HEAD (staged changes)
• <commit1> <commit2>: Two specific commits

Format: Unified diff with context lines and change indicators.

Examples:

myvcs diff                      # Changes since last commit
myvcs diff --staged             # Staged changes
myvcs diff abc1234 def5678      # Compare commits
myvcs diff main feature-branch  # Compare branch tips

show

Display detailed information about objects.

myvcs show <hash>

Shows:

• Commits: Full metadata and message
• Blobs: File content
• Trees: Directory structure with entries
• Tags: Tag information

---

Branching

branch

Manage branches (create, list, delete, rename).

myvcs branch [<n>] [-d <n>] [-m <old> <new>] [-f]

Operations:

• No arguments: List all branches (current marked with *)
• <n>: Create new branch at current commit
• -d, --delete: Delete branch
• -m, --move: Rename branch
• -f, --force: Force operation (e.g., delete unmerged branch)

Examples:

myvcs branch                    # List branches
myvcs branch feature-xyz        # Create branch
myvcs branch -d old-feature     # Delete branch
myvcs branch -m old-name new    # Rename
myvcs branch -d -f unmerged     # Force delete

checkout

Switch to a different branch or commit.

myvcs checkout <branch|commit> [-f]

Arguments:

• branch - Switch to branch
• commit - Checkout specific commit (detached HEAD state)
• -f - Force, discarding local changes

What happens:

1. Resolves target to commit
2. Checks for conflicts with local changes
3. Updates working directory to match commit
4. Updates HEAD and Index

Examples:

myvcs checkout main             # Switch to main
myvcs checkout feature-branch   # Switch to feature
myvcs checkout abc1234          # Specific commit
myvcs checkout -f main          # Force switch

---

Merging

merge

Merge a branch into current branch.

myvcs merge <branch> [--no-commit]

Options:

• --no-commit - Prepare merge without creating commit

Algorithm:

1. Finds merge base (Lowest Common Ancestor)
2. Performs three-way merge on each file
3. Detects conflicts (all three versions different)
4. Creates merge commit if successful

Outcomes:

• Fast-forward: Linear history, no merge commit needed
• Regular merge: Creates merge commit with 2 parents
• Conflicts: Requires manual resolution

Conflict markers:

<<<<<<< HEAD
// Your version
int x = 42;
=======
// Their version
int x = 100;
>>>>>>> feature-branch

Examples:

myvcs merge feature-branch      # Standard merge
myvcs merge release-1.0 --no-commit  # Preview merge

---

Resetting & Cleanup

reset

Reset repository state to a specific commit.

myvcs reset [<commit>] [--soft|--mixed|--hard]

Modes:

• --soft - Move HEAD only (keep staged changes)
• --mixed - Move HEAD and update Index (default)
• --hard - Move HEAD, Index, and restore working directory

Examples:

myvcs reset HEAD~1              # Undo last commit (soft)
myvcs reset --mixed abc1234     # Reset to commit
myvcs reset --hard origin       # Discard all changes

⚠️ Warning: --hard discards changes permanently!

---

Tags

tag

Create and manage lightweight tags.

myvcs tag [<n>] [<commit>] [-d <n>]

Operations:

• No args: List all tags
• <n>: Tag current commit
• <n> <commit>: Tag specific commit
• -d: Delete tag

Examples:

myvcs tag                       # List tags
myvcs tag v1.0.0                # Tag current
myvcs tag v1.0.0 abc1234        # Tag specific
myvcs tag -d v1.0.0             # Delete tag

---

Configuration

config

Manage repository configuration.

myvcs config <section> <key> [value]

Common settings:

• user.name - Author name
• user.email - Author email
• core.filemode - Track file permissions

Examples:

myvcs config user.name "Your Name"
myvcs config user.email "you@example.com"
myvcs config user.name             # Read value

---

Performance Characteristics

Operation	Complexity	Real-World Performance
Add single file	O(N)	~5-10 ms per MB
Add directory	O(m × N)	~100 ms for 1000 files
Commit	O(n log n)	~100 ms for 1000 files
Branch operations	O(1)	<1 ms
Diff (100 lines)	O(N×M)	~10 ms
Merge	O(N)	~5 ms for 100 KB
Checkout	O(m × N)	~200 ms for 1000 files
ObjectStore lookup	O(1) avg	<1 µs with cache hits
Index search	O(log n)	<1 µs for 100K entries
Log traversal	O(n)	~50 ms for 10K commits

System Requirements

Build Requirements

• C++ Standard: C++17 or later
• Compiler: GCC 9+, Clang 10+, or MSVC 2019+
• Build System: CMake 3.15+
• Build Tool: Ninja or Make

Dependencies

• OpenSSL: For SHA-256 cryptographic hashing
• Standard Library: STL containers and algorithms

Runtime Requirements

• OS: Linux, macOS, or Windows
• Disk Space: Depends on repository size (stores full file history)
• Memory: 50 MB base + object cache (configurable, default 1000 objects ~10 MB)

Building & Testing

Build Instructions

# Create build directory
mkdir build && cd build

# Configure with CMake
cmake -G Ninja -DCMAKE_BUILD_TYPE=Release ..

# Build
ninja

# Build with tests
ninja test

Build Options

# Debug build with symbols
cmake -DCMAKE_BUILD_TYPE=Debug ..

# Release build with optimizations
cmake -DCMAKE_BUILD_TYPE=Release ..

# Custom installation prefix
cmake -DCMAKE_INSTALL_PREFIX=/usr/local ..

# With static linking
cmake -DBUILD_SHARED_LIBS=OFF ..

Running Tests

# Run all tests
ninja test

# Run specific test
./bin/test_objects

# Run with verbose output
ctest --verbose

Documentation

Core Documentation

• ARCHITECTURE.md - Detailed system architecture, design decisions, and data flow
• ALGORITHMS.md - Algorithm complexity analysis (Diff, Merge, Graph traversal)
• complexity_analysis.md - time and space complexity analysis for all MyVCS operations, with real-world performance metrics and optimization strategies.
• API_REFERENCE.md - Complete C++ API documentation for library usage

Architecture Overview

Layered Design

┌─────────────────────────────────┐
│     CLI Commands Layer          │
│  (init, add, commit, merge...)  │
├─────────────────────────────────┤
│   Repository Management Layer   │
│ (Repository, Index, Config)     │
├─────────────────────────────────┤
│    Algorithm Layer              │
│ (Diff, Merge, Graph Traversal)  │
├─────────────────────────────────┤
│    Object Model Layer           │
│ (Blob, Tree, Commit, Tag)       │
├─────────────────────────────────┤
│    Storage Layer                │
│ (ObjectStore, Serializer)       │
└─────────────────────────────────┘

Key Components

Component	Purpose	Key Operations
ObjectStore	Content-addressable storage	store(), load(), exists()
Index	Staging area (BST)	add(), getEntry(), save()
Repository	Main coordinator	All operations routing
CommitGraph	History traversal	DFS, BFS, LCA finding
DiffAlgorithm	Change detection	Myers' LCS algorithm
MergeAlgorithm	Conflict resolution	Three-way merge logic

Data Structures

Primary Data Structures

• Hash Table (unordered_map): ObjectStore cache - O(1) lookup
• Binary Search Tree (std::map): Index entries - O(log n) operations
• DAG (Commit graph): Version history - O(V+E) traversal
• Merkle Tree: Directory structures - O(1) hash verification
• Dynamic Programming Table: Diff computation - O(N×M)

For detailed analysis, see ALGORITHMS.md.

Algorithms

Core Algorithms

Diff: Myers' Longest Common Subsequence

• Complexity: O(N×M) time, O(N×M) space
• Purpose: Compute minimal edit script between files
• Optimization: Can be reduced to O(min(N,M)) space with two-row DP

Merge: Three-Way Merge

• Complexity: O(max(N,M,K)) time, O(max) space
• Purpose: Combine changes from two branches using common base
• Conflict Detection: Automatic identification of conflicting regions

Graph Traversal: DFS/BFS/LCA

• Complexity: O(V+E) time, O(V) space
• Purpose: History queries, ancestry checks, merge base finding
• Use Cases: log, merge, diff operations

For detailed analysis, see ALGORITHMS.md.

Design Principles

1. Content Addressability: Objects indexed by SHA-256 hash ensures immutability and integrity
2. Separation of Concerns: Distinct layers for storage, objects, algorithms, and commands
3. Object Immutability: Once created, objects never change (new version = new object)
4. DAG Structure: Commits form directed acyclic graph supporting merge history
5. Efficient Caching: In-memory LRU cache reduces disk I/O significantly
6. Deterministic Hashing: Trees sorted by name enable reproducible hashes

Current Limitations

• No delta encoding - Every version stored fully (future enhancement)
• Linear history only - log follows first parent chain
• Basic merge only - Three-way merge without advanced strategies
• No .gitignore support - All files staged with add
• Local only - No remote operations (push/pull/fetch)
• Limited permissions - Only text/executable distinction

Future Roadmap

• Delta compression for efficient storage
• Advanced merge strategies (patience, recursive, resolve)
• Rebase support for linear history
• Remote operations (push/pull/fetch)
• .gitignore pattern support
• Hook system (pre/post commit scripts)
• Garbage collection and object pruning
• Shallow clones and partial checkouts
• Multi-threaded operations for performance
• Submodule support

Contributing

Development Setup

# Fork and clone repository
git clone <your-fork-url>
cd MyVCS

# Create feature branch
git checkout -b feature/your-feature

# Make changes and test
mkdir build && cd build
cmake -DCMAKE_BUILD_TYPE=Debug ..
ninja && ninja test

Code Style

• Follow C++17 standard practices
• Use PascalCase for classes, snake_case for functions
• Document public APIs with doxygen-style comments
• Write unit tests for new functionality

Submitting Changes

1. Ensure all tests pass: ninja test
2. Follow code style guidelines
3. Add tests for new features
4. Update documentation
5. Submit pull request with detailed description

Acknowledgments

MyVCS is inspired by Git's elegant design and implements proven algorithms for version control. Special thanks to the open-source community and academic research in version control systems.