Introducing libvctrl: A Content‑Addressed Version Control Engine for Rust Applications

libvctrl is an open‑source library that provides a complete, content‑addressed version control engine designed to be embedded directly into Rust applications. It offers the full machinery of modern version control – objects, references, commits, merges, cryptographic signatures, garbage collection, and much more – all without depending on an external CLI tool or shelling out to Git.

The library is built on a clean trait‑based architecture. Every major component (hashing, encoding, storage, merging, signing) is defined as a trait, allowing you to plug in custom implementations or use the robust defaults. The default hasher is SHA‑512, the default encoding is a compact binary format with versioning, and the reference store can be backed by memory, an append‑only file, or wrapped in Arc<Mutex<>> for thread‑safe access.

Whether you are building a collaborative editor, a game that needs to version its assets, a document management system, or a custom DevOps tool, libvctrl gives you a production‑ready foundation for versioning arbitrary data.

---

Feature Overview

• Complete object model – Blob, Tree, Commit, and Tag. All objects are identified by a 64‑byte SHA‑512 hash.
• Pluggable hashing – Hasher trait; default Sha512Hasher uses type‑prefixed SHA‑512.
• Pluggable encoding – Encoder / Decoder traits; default binary format with strict size limits to prevent malformed input attacks.
• Full version control operations
  • Commit creation, checkout, diff, log, log with graph topology, blame, stash
  • Merge (three‑way, octopus), rebase, cherry‑pick, revert
  • Branch and tag management (lightweight and annotated, with cryptographic signing)
• Storage backends
  • MemoryStore – hash‑map‑based store, ideal for testing and in‑memory usage.
  • FileStore – append‑only binary file with tombstone deletion for garbage collection.
  • SyncAdapter – wraps any ObjectStore / RefStore in Arc<Mutex<>> for safe concurrent access.
• Cryptographic signing & verification – trait‑based Signer / Verifier (example with Ed25519 included in tests).
• Advanced merging – recursive three‑way merge with pluggable ConflictResolver trait.
• Merge base detection – BFS‑based find_merge_base and is_ancestor helpers with a configurable search limit.
• Reflog – optional log of all reference changes; MemoryRefStore implements ReflogStore.
• RevWalk – timestamp‑ordered commit iterator that returns (Hash, Commit) pairs.
• Patch generation & application – binary patches for tree‑to‑tree transformations (blob‑only).
• Garbage collection – mark‑and‑sweep reachable objects; removes unreachable ones and writes tombstones in the file store.
• Index – a staging‑area abstraction (Index) to incrementally build a tree before committing.
• Extensibility – custom encoders, hashers, merge strategies, conflict resolvers, and transport layers.

---

Data Model

All objects are content‑addressed. A Hash is a fixed 64‑byte array, displayed as a 128‑character hex string.

Type	Description
Blob	Raw byte content.
TreeEntry	A named entry (name, kind – Blob or Tree, hash).
Tree	An immutable, sorted list of TreeEntry. Duplicate names are rejected.
Commit	Points to a tree, lists parent commits, and stores author, committer, timestamp, message, an optional signature, and custom headers (key‑value pairs).
Tag	Lightweight (a direct ref) or annotated (a full object with tagger, message, timestamp, optional signature).
Object	Enum Blob, Tree, Commit, or Tag.
UserID	Name and email, each 1–255 characters.

---

Hashing & Encoding

Hasher Trait

pub trait Hasher {
    fn hash_blob(&self, data: &[u8]) -> Hash;
    fn hash_tree_encoded(&self, data: &[u8]) -> Hash;
    fn hash_commit_encoded(&self, data: &[u8]) -> Hash;
    fn hash_tag_encoded(&self, data: &[u8]) -> Hash;
}

The default Sha512Hasher follows the pattern type SP length NUL data, hashed with SHA‑512. The HashVerifier extension trait (auto‑implemented) adds verify_* methods that recompute the hash and compare it to the expected value.

Encoder / Decoder Traits

pub trait Encoder {
    fn encode_tree(&self, tree: &Tree, buf: &mut Vec<u8>) -> Result<(), VctrlError>;
    fn encode_commit(&self, commit: &Commit, buf: &mut Vec<u8>) -> Result<(), VctrlError>;
    fn encode_tag(&self, tag: &Tag, buf: &mut Vec<u8>) -> Result<(), VctrlError>;
}

pub trait Decoder {
    fn decode_tree(&self, data: &[u8]) -> Result<Tree, VctrlError>;
    fn decode_commit(&self, data: &[u8]) -> Result<Commit, VctrlError>;
    fn decode_tag(&self, data: &[u8]) -> Result<Tag, VctrlError>;
}

The default binary encoder/decoder uses a compact, versioned format. Commit version 2 and tag version 2 support additional headers and signatures, while enforcing tight limits on field sizes (e.g., max tree entries 100 000, max message length 1 MiB) to prevent resource exhaustion.

---

Storage Abstraction

libvctrl separates concerns: object storage is handled by ObjectStore, reference management by RefStore.

ObjectStore Trait

pub trait ObjectStore {
    fn put(&mut self, hash: &Hash, obj: &Object) -> Result<(), VctrlError>;
    fn get(&self, hash: &Hash) -> Result<Option<Object>, VctrlError>;
    fn exists(&self, hash: &Hash) -> Result<bool, VctrlError>;
    fn all_hashes(&self) -> Result<Vec<Hash>, VctrlError>;
    fn remove(&mut self, hash: &Hash) -> Result<(), VctrlError>;
}

RefStore Trait

pub trait RefStore {
    fn set_ref(&mut self, name: &str, hash: &Hash) -> Result<(), VctrlError>;
    fn get_ref(&self, name: &str) -> Result<Option<Hash>, VctrlError>;
    fn delete_ref(&mut self, name: &str) -> Result<(), VctrlError>;
    fn set_head(&mut self, target: &str) -> Result<(), VctrlError>;
    fn head(&self) -> Result<Option<Hash>, VctrlError>;
    fn head_ref_name(&self) -> Result<Option<String>, VctrlError>;
    fn list_refs(&self, prefix: &str) -> Result<Vec<String>, VctrlError>;
}

Extension Trait ObjectStoreExt

Provides convenient helper methods:

fn get_commit(&self, hash: &Hash) -> Result<Commit, VctrlError>;
fn get_tree(&self, hash: &Hash) -> Result<Tree, VctrlError>;
fn get_blob(&self, hash: &Hash) -> Result<Vec<u8>, VctrlError>;
fn get_verified(&self, hash: &Hash, encoder: &dyn Encoder, hasher: &dyn Hasher) -> Result<Object, VctrlError>;

get_verified recomputes the hash of the encoded object and returns a Corrupted error on mismatch, enabling integrity checks.

Built‑in Backends

• MemoryStore + MemoryRefStore – Fast, in‑memory hash maps. MemoryRefStore also implements ReflogStore.
• FileStore – Append‑only binary file with a magic header, versioning, and record types for objects, ref operations, and tombstone deletions. It is crash‑safe and reads the entire file at startup to rebuild indices.
• SyncAdapter<S> – Generic wrapper that takes an ObjectStore or RefStore and exposes SyncObjectStore / SyncRefStore with &self methods, using an internal Arc<Mutex<S>>. Mutex poisoning is mapped to a Backend error.

---

The Command Trait

Every operation is encapsulated as a struct that implements the Command trait. This design keeps the library free of side effects and makes it straightforward to integrate with different runtimes.

pub trait Command {
    type Output;
    fn execute(
        &self,
        store: &mut dyn ObjectStore,
        refs: &mut dyn RefStore,
    ) -> Result<Self::Output, VctrlError>;
}

Available Commands

Command	Struct Fields (abbreviated)	Output
Init	author, encoder, hasher	Hash (initial commit)
CreateCommit	tree_hash, parents, author, committer, message, encoder, hasher	Hash (new commit)
Checkout	tree_hash	Vec<(String, Vec<u8>)>
Log	(none)	Vec<Commit>
LogGraph	head	Vec<GraphCommit> (includes parent indices)
DiffCommits	old_commit, new_commit	Vec<DiffEntry>
DiffPatch	old_tree_hash, new_tree_hash	Vec<u8> (binary patch)
ApplyPatch	base_tree_hash, patch_data, encoder, hasher	Hash (new tree)
CherryPick	commit_hash, author, committer, merger, resolver, encoder, hasher	Hash (new commit)
Revert	commit_hash, author, committer, encoder, hasher	Hash (revert commit)
MergeCommand	base, ours, theirs, merger, resolver, encoder, hasher	Hash (merged tree)
MergeBranch	branch_name, author, committer, merger, resolver, encoder, hasher	Hash (merge commit)
OctopusMerge	branch_names, author, committer, merger, resolver, encoder, hasher	Hash (merge commit)
Rebase	upstream, onto, author, committer, merger, resolver, encoder, hasher	Hash (new HEAD)
CreateBranch	name (must start with refs/heads/), hash	()
DeleteBranch	name	()
GetBranch	name	Option<Hash>
SetHead	target (branch name or hash)	()
ListBranches	(none)	Vec<(String, Hash, bool)>
CreateLightweightTag	name, target	()
CreateAnnotatedTag	name, target, tagger, message, encoder, hasher, optional signer	Hash (tag object)
DeleteTag	name	()
ListTags	(none)	Vec<String>
VerifyCommit	commit_hash, verifier, encoder, hasher	bool
VerifyTag	tag_hash, verifier, encoder, hasher	bool
Describe	commit_hash, max_commits_to_search	Option<String>
StashPush	tree_hash, author, message, encoder, hasher	Hash (stash commit)
StashPop	(none)	Option<Hash> (tree hash)
StashList	(none)	Vec<(String, Hash)>
Annotate (Blame)	start_commit, path	Vec<BlameEntry>
Show	commit_hash	ShowOutput { commit, diff }
Fsck	encoder, hasher	Vec<VctrlError>

All commands are synchronous and return a Result with the appropriate output type.

---

Diff & Merge

Tree Diffing

The TreeDiff trait is implemented by TreeDiffer. It compares two trees and returns a list of DiffEntry, each with a DiffKind of Added, Removed, or Modified.

pub enum DiffKind {
    Added { new_hash: Hash },
    Removed,
    Modified { old_hash: Hash, new_hash: Hash },
}

Three‑Way Merge

The ThreeWayMerge trait is implemented by ThreeWayMerger. It performs a recursive tree merge and uses a ConflictResolver for blob conflicts.

pub trait ConflictResolver {
    fn resolve(&self, base: &[u8], ours: &[u8], theirs: &[u8]) -> Option<Vec<u8>>;
}

The resolver can be a simple “ours” or “theirs” strategy, a line‑based merger, or any custom logic. When a conflict cannot be resolved, the merge returns a VctrlError::MergeConflict.

Merge Base

Two utility functions assist with merging:

• find_merge_base(store, a, b) – returns the best common ancestor, using a BFS limited to 100 000 steps.
• is_ancestor(store, ancestor, descendant) – checks fast‑forward conditions.

---

Additional Components

Reflog

The ReflogStore trait and ReflogEntry struct provide an audit trail of reference updates. MemoryRefStore implements this trait automatically, recording every set_ref.

RevWalk

RevWalk is a timestamp‑ordered iterator over commits. Starting from one or more tips, it yields (Hash, Commit) pairs using a binary heap. It is an efficient way to traverse history in chronological order.

Patch

generate_patch and apply_patch create and apply binary patches between two trees. The patch format is versioned and currently limited to blob changes (tree‑level patches return an error). These operations are exposed as DiffPatch and ApplyPatch commands.

Garbage Collection

• mark_reachable – collects the set of all objects reachable from any ref and HEAD.
• gc – removes unreachable objects. In FileStore, removal writes a tombstone record so that the object stays deleted across restarts.

---

Usage Example

Below is a minimal example that initializes a repository, adds a blob and a tree, and creates a commit – all using the in‑memory backends.

use libvctrl::*;

fn main() -> Result<(), VctrlError> {
    let mut store = MemoryStore::new();
    let mut refs = MemoryRefStore::new();

    // Initialize the repository
    let init = Init {
        author: UserID::new("Alice".into(), "[e-mail]".into())?,
        encoder: Box::new(BinaryEncoder),
        hasher: Box::new(Sha512Hasher),
    };
    let root_commit = init.execute(&mut store, &mut refs)?;

    // Create a blob
    let blob_data = b"Hello, libvctrl!";
    let blob = Blob::new(blob_data.to_vec());
    let hasher = Sha512Hasher;
    let blob_hash = hasher.hash_blob(blob_data);
    store.put(&blob_hash, &Object::Blob(blob))?;

    // Build a tree
    let entry = TreeEntry::new("README.md".into(), EntryKind::Blob, blob_hash)?;
    let tree = Tree::new(vec![entry])?;
    let mut buf = Vec::new();
    let encoder = BinaryEncoder;
    encoder.encode_tree(&tree, &mut buf)?;
    let tree_hash = hasher.hash_tree_encoded(&buf);
    store.put(&tree_hash, &Object::Tree(tree))?;

    // Create a commit on top of the initial commit
    let commit_cmd = CreateCommit {
        tree_hash,
        parents: vec![root_commit],
        author: UserID::new("Alice".into(), "[e-mail]".into())?,
        committer: UserID::new("Alice".into(), "[e-mail]".into())?,
        message: "Add README".into(),
        encoder: Box::new(BinaryEncoder),
        hasher: Box::new(Sha512Hasher),
    };
    let new_commit = commit_cmd.execute(&mut store, &mut refs)?;

    println!("New commit: {}", new_commit);
    Ok(())
}

The same pattern can be used with FileStore for persistent storage – just replace MemoryStore::new() with FileStore::open("myrepo.vctrl")?.

---

Error Handling

All fallible functions return Result<T, VctrlError>. The error type is exhaustive:

pub enum VctrlError {
    Hash(HashError),
    Tree(TreeError),
    NotFound(String),
    InvalidRef(String),
    MergeConflict { entry: String, reason: String },
    Io(std::io::Error),
    Serialization(String),
    Backend(String),
    Other(String),
    Corrupted(String),
    Unsupported(String),
}

There are no hidden panics in the library. Every error path is propagated cleanly.

---

Minimum Supported Rust Version

libvctrl requires Rust 1.85.0 (stable) or later.

---

License

Licensed under the MIT License. See the LICENSE file for details.

---

Repository & Contribution

The source code, full documentation, and issue tracker are available on GitHub:

github.com/mroczect/libvcrtl

Contributions, bug reports, and feature suggestions are welcome. If you are building an application that requires embedded version control, give libvctrl a try – it is ready for real‑world use and open to extension.