miniGit

A Data Structures and Algorithms Course Project

---

Key Features

Core Git Operations

• Repository initialization (init)
• Object storage (blobs, trees, commits)
• Staging area and add command
• Committing changes (commit)
• Commit history (log)
• Checking out commits and branches (checkout)
• Working directory status (status)
• Branch management (branch, switch)

Merkle Tree Features

• Fast Change Detection: O(1) working directory status using Merkle root comparison
• Efficient Branch Comparison: Instantly compare two branches using Merkle roots
• Integrity Verification: Detect corruption/tampering by recursively validating all objects

Special Commands:

miniGit verify-integrity           # Verify repository integrity
miniGit compare-branches main dev  # Compare branch contents

---

Data Structures & Algorithms

• std::map (Red-Black Tree): Used for index and commit history (ordered, O(log n) lookup)
• Merkle Tree: Used for fast change detection, branch comparison, and integrity verification
• Linked List: Commit parent chains for history traversal
• std::string: For hash storage and manipulation
• structs: For index entries and commit objects (POD types)
• Content-Addressable Storage: 2-level directory sharding for object database

See docs/internals.md for format specs and rationale.

---

Project Structure

miniGit/
├── include/         # Header files (public APIs)
├── src/             # Implementation files
│   ├── main.cpp         # Entry point
│   ├── repository.cpp   # Repo management + Merkle features
│   ├── objects.cpp      # Object database
│   ├── commands.cpp     # Command handlers
│   ├── branch.cpp       # Branch operations
│   ├── index.cpp        # Staging area
│   ├── merkle.cpp       # Merkle tree operations
│   └── utils.cpp        # Utilities
├── docs/            # Documentation
│   └── internals.md      # Internal format/design
├── tests/           # Test suite
│   └── run_tests.sh        # Comprehensive test script (19 tests)
└── build/           # Build artifacts

---

Building

Requires: C++20 compiler and optionally CMake 3.16+ (no external library dependencies!)

Method A: Direct Compilation (No CMake required)

If you don't have CMake, you can compile directly using Clang or GCC:

mkdir -p build
clang++ -std=c++20 -Iinclude src/*.cpp -o build/miniGit

Method B: Using CMake

mkdir -p build
cd build
cmake ..
make
cd ..

---

Testing

miniGit includes a comprehensive test suite covering 19 test scenarios:

chmod +x tests/run_tests.sh
./tests/run_tests.sh

---

Usage

All commands are run relative to the project root directory via the compiled binary:

./build/miniGit <command> [options]

1. Basic Repository Commands

# Initialize a new miniGit repository (.minigit/)
./build/miniGit init

# Check working tree status (ignored files can be defined in .minigitignore)
./build/miniGit status

# Stage a file for commit
./build/miniGit add <file>

# Record staged changes into history
./build/miniGit commit -m "message"

# Display commit log history
./build/miniGit log

2. Branching & Merging

# List or create branches
./build/miniGit branch
./build/miniGit branch <branch-name>

# Switch tracking to another branch
./build/miniGit switch <branch-name>

# Checkout a branch or specific commit hash (detached HEAD)
./build/miniGit checkout <commit-hash-or-branch-name>

# Merge another branch into your current branch
./build/miniGit merge <branch-name>

3. Stashing Area

# Stash current uncommitted changes away
./build/miniGit stash save

# List saved stash entries
./build/miniGit stash list

# Apply and drop the latest stash
./build/miniGit stash pop

4. Merkle Tree & Integrity Features

# Verify the cryptographic integrity of all repo objects
./build/miniGit verify-integrity

# View the hierarchical Merkle Tree of the working directory
./build/miniGit verify-tree --working-dir

# View the Merkle Tree structure of a specific tree object hash
./build/miniGit verify-tree <tree-hash>

# Instantly compare two branches using their Merkle roots
./build/miniGit compare-branches <branch1> <branch2>

# Diff two tree hashes or compare working directory with a commit hash
./build/miniGit diff-tree <tree-hash1> <tree-hash2>
./build/miniGit diff-tree --working-dir <commit-hash>

5. Plumbing Commands (Debugging)

# Compute SHA-1 object ID of a file
./build/miniGit hash-object <file>

# Display content of a hashed object (blob, tree, or commit)
./build/miniGit cat-file <hash>

---

Merkle Tree Use Cases

1. Quick Status Checks: O(1) working directory status comparisons using Merkle root hashes.
2. Branch Comparison: Instantly detect divergence between branches.
3. Corruption Detection: Recursively verify repository integrity checking all hashes and files.

---

Team & Documentation

• Internals: docs/internals.md covers index format, object database, Merkle tree, and rationale.
• SHA-1 Implementation: See sha1.hpp for a fully documented cryptographic hash algorithm.

---

License

MIT