Struct VerMap 

pub struct VerMap<K, V> { /* private fields */ }

A persistent, versioned, ordered key-value map.

VerMap provides Git-style version control for a typed key-value store: branching, committing, three-way merge, rollback, and garbage collection, all backed by a persistent B+ tree with copy-on-write structural sharing.

Lifecycle

A typical workflow mirrors the Git mental model:

1. Create — VerMap::new() gives you a map with a single main branch and an empty working state.
2. Write — insert / remove mutate the working state of a branch (analogous to editing files in a Git working directory).
3. Commit — commit snapshots the current working state into an immutable Commit. Each commit records the B+ tree root, parent linkage, and a wall-clock timestamp.
4. Branch — create_branch forks a lightweight branch from any existing branch. The new branch shares all history via structural sharing — no data is copied.
5. Merge — merge(source, target) performs a three-way merge. Deletion is treated as “assigning ∅”, so all conflicts are resolved uniformly: source wins — whether source wrote a new value or deleted the key.
6. Rollback — rollback_to rewinds a branch to an earlier commit; discard throws away uncommitted changes.
7. History — log, get_at_commit, iter_at_commit let you inspect any historical snapshot.
8. GC — gc reclaims commits and B+ tree nodes that are no longer reachable from any live branch.

Quick start

use vsdb::versioned::map::VerMap;
use vsdb::versioned::NO_COMMIT;
use vsdb::{vsdb_set_base_dir, vsdb_get_base_dir};
use std::fs;

let dir = format!("/tmp/vsdb_testing/{}", rand::random::<u128>());
vsdb_set_base_dir(&dir).unwrap();

let mut m: VerMap<u32, String> = VerMap::new();
let main = m.main_branch();

// 1. Write on the default "main" branch.
m.insert(main, &1, &"hello".into()).unwrap();
m.insert(main, &2, &"world".into()).unwrap();
let c1 = m.commit(main).unwrap();

// 2. Fork a feature branch from main.
let feat = m.create_branch("feature", main).unwrap();
m.insert(feat, &1, &"hi".into()).unwrap();
let c2 = m.commit(feat).unwrap();

// 3. Branches are isolated — main is unchanged.
assert_eq!(m.get(main, &1).unwrap(), Some("hello".into()));
assert_eq!(m.get(feat, &1).unwrap(), Some("hi".into()));

// 4. Merge feature → main (source wins on conflict).
m.merge(feat, main).unwrap();
assert_eq!(m.get(main, &1).unwrap(), Some("hi".into()));

// 5. Clean up: delete the feature branch and run GC.
m.delete_branch(feat).unwrap();
m.gc();

fs::remove_dir_all(&dir).unwrap();

Implementations

impl<K, V> VerMap<K, V>

where K: KeyEnDeOrdered, V: ValueEnDe,

pub fn new() -> Self

Creates a new, empty versioned map with a default main branch.

Equivalent to new_with_main("main").

pub fn instance_id(&self) -> u64

Returns the unique instance ID of this VerMap.

pub fn save_meta(&self) -> Result<u64>

Persists this instance’s metadata to disk so that it can be recovered later via from_meta.

Returns the instance_id that should be passed to from_meta.

pub fn from_meta(instance_id: u64) -> Result<Self>

Recovers a VerMap instance from previously saved metadata.

The caller must ensure that the underlying VSDB database still contains the data referenced by this instance ID.

pub fn new_with_main(name: &str) -> Self

Creates a new, empty versioned map whose initial branch has the given name (e.g. "genesis", "canonical").

The initial branch is automatically designated as the main branch and cannot be deleted until another branch is promoted via set_main_branch.

pub fn main_branch(&self) -> BranchId

Returns the BranchId of the current main branch.

pub fn set_main_branch(&mut self, branch: BranchId) -> Result<()>

Designates branch as the new main branch.

The previous main branch becomes an ordinary branch (deletable). The new main branch is protected from deletion.

pub fn create_branch( &mut self, name: &str, source_branch: BranchId, ) -> Result<BranchId>

Creates a new branch forked from source_branch.

The new branch inherits both the committed head and the current working state (uncommitted changes, if any) of the source branch.

pub fn delete_branch(&mut self, branch: BranchId) -> Result<()>

Deletes a branch and automatically cleans up orphaned commits.

Decrements the ref-count on the branch’s HEAD commit. If it reaches zero, the commit is hard-deleted and the decrement cascades to its parents.

B+ tree node reclamation requires a separate gc call (or happens automatically in VerMapWithProof::from_map).

pub fn list_branches(&self) -> Vec<(BranchId, String)>

Lists all branches as (BranchId, name).

pub fn branch_id(&self, name: &str) -> Option<BranchId>

Looks up a branch by name, returning its ID if it exists.

pub fn branch_name(&self, branch: BranchId) -> Option<String>

Returns the name of a branch given its ID.

pub fn has_uncommitted(&self, branch: BranchId) -> Result<bool>

Returns true if the branch has uncommitted changes (dirty state differs from the head commit’s snapshot).

pub fn get(&self, branch: BranchId, key: &K) -> Result<Option<V>>

Reads a value from the working state of branch.

pub fn get_at_commit(&self, commit_id: CommitId, key: &K) -> Result<Option<V>>

Reads a value at a specific historical commit.

pub fn contains_key(&self, branch: BranchId, key: &K) -> Result<bool>

Checks if key exists in the working state of branch.

pub fn iter( &self, branch: BranchId, ) -> Result<impl Iterator<Item = (K, V)> + '_>

Iterates all entries on branch in ascending key order.

pub fn range( &self, branch: BranchId, lo: Bound<&K>, hi: Bound<&K>, ) -> Result<impl Iterator<Item = (K, V)> + '_>

Iterates entries in [lo, hi) on branch in ascending key order.

pub fn iter_at_commit( &self, commit_id: CommitId, ) -> Result<impl Iterator<Item = (K, V)> + '_>

Iterates all entries at a specific historical commit.

pub fn range_at_commit( &self, commit_id: CommitId, lo: Bound<&K>, hi: Bound<&K>, ) -> Result<impl Iterator<Item = (K, V)> + '_>

Iterates entries in [lo, hi) at a specific historical commit in ascending key order.

pub fn raw_iter( &self, branch: BranchId, ) -> Result<impl Iterator<Item = (Vec<u8>, Vec<u8>)> + '_>

Iterates all raw (untyped) key-value pairs on a branch.

Returns (Vec<u8>, Vec<u8>) without decoding, useful for feeding into external consumers (e.g. MPT hash computation).

pub fn raw_iter_at_commit( &self, commit_id: CommitId, ) -> Result<impl Iterator<Item = (Vec<u8>, Vec<u8>)> + '_>

Iterates all raw (untyped) key-value pairs at a historical commit.

pub fn contains_key_at_commit( &self, commit_id: CommitId, key: &K, ) -> Result<bool>

Checks if key exists at a specific historical commit.

pub fn insert(&mut self, branch: BranchId, key: &K, value: &V) -> Result<()>

Inserts a key-value pair into the working state of branch.

pub fn remove(&mut self, branch: BranchId, key: &K) -> Result<()>

Removes a key from the working state of branch.

pub fn commit(&mut self, branch: BranchId) -> Result<CommitId>

Commits the current working state of branch, creating a new immutable Commit. Returns the commit ID.

pub fn discard(&mut self, branch: BranchId) -> Result<()>

Discards uncommitted changes, resetting the working state to the branch head.

pub fn rollback_to(&mut self, branch: BranchId, target: CommitId) -> Result<()>

Rolls back branch to a previous commit, discarding all commits after target on this branch.

target must be an ancestor of the branch’s current head. The discarded commits are not deleted (they may be reachable from other branches). Call gc to reclaim them.

pub fn merge(&mut self, source: BranchId, target: BranchId) -> Result<CommitId>

Merges source branch into target branch using three-way merge.

Both branches must be committed (no uncommitted changes).

Conflict resolution: source wins on conflicts

First, non-conflicting single-sided changes are preserved using the ancestor snapshot. If both sides changed the same key differently, source wins. A deletion is treated as “assigning ∅”, so delete-vs-modify is also resolved by source priority.

source	target	result
unchanged (A)	changed to T	T (target-only change preserved)
changed to S	unchanged (A)	S (source-only change preserved)
changed to S	changed to T	S (conflict → source wins)
deleted (∅)	changed to T	∅ (conflict → source wins → delete)
changed to S	deleted (∅)	S (conflict → source wins → keep)

The caller controls priority by choosing which branch to pass as source vs target.

If target has no commits, performs a fast-forward (no merge commit is created). Otherwise creates a merge commit on target with two parents.

pub fn fork_point(&self, a: CommitId, b: CommitId) -> Option<CommitId>

Returns the lowest common ancestor (fork point) of two commits.

Useful for blockchain scenarios: given two chain tips, this finds the block where they diverged. Returns None only if the two commits share no common history.

pub fn commit_distance(&self, from: CommitId, ancestor: CommitId) -> Option<u64>

Counts the number of first-parent commits between from and ancestor (exclusive).

Walks the first-parent chain starting at from until ancestor is reached. Returns None if ancestor is not a first-parent ancestor of from.

Example — comparing fork lengths

let lca = map.fork_point(tip_a, tip_b).unwrap();
let ahead_a = map.commit_distance(tip_a, lca).unwrap();
let ahead_b = map.commit_distance(tip_b, lca).unwrap();
// The longer fork wins.

pub fn get_commit(&self, commit_id: CommitId) -> Option<Commit>

Retrieves a commit by its ID.

pub fn head_commit(&self, branch: BranchId) -> Result<Option<Commit>>

Returns the commit at the head of branch.

pub fn log(&self, branch: BranchId) -> Result<Vec<Commit>>

Walks the first-parent commit history of branch from head to root.

For merge commits, only the first parent (the target branch at merge time) is followed — analogous to git log --first-parent.

pub fn diff_commits( &self, from: CommitId, to: CommitId, ) -> Result<Vec<DiffEntry>>

Computes the diff between two commits.

Returns a list of DiffEntry in ascending key order, describing every key that was added, removed, or modified between from and to.

pub fn diff_uncommitted(&self, branch: BranchId) -> Result<Vec<DiffEntry>>

Computes the diff of uncommitted (working) changes on branch.

Analogous to git diff (unstaged changes relative to HEAD).

pub fn gc(&mut self)

Reclaims B+ tree nodes that are no longer reachable.

Commit lifecycle is handled automatically by reference counting (see delete_branch, rollback_to). This method performs:

1. Crash recovery — if a ref-count cascade was interrupted, rebuilds all ref counts from scratch and removes orphaned commits.
2. B+ tree sweep — mark-and-sweep over the node pool, keeping only nodes reachable from live commit roots and dirty (uncommitted) roots.

Trait Implementations

impl<K: Clone, V: Clone> Clone for VerMap<K, V>

fn clone(&self) -> VerMap<K, V>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K: Debug, V: Debug> Debug for VerMap<K, V>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K, V> Default for VerMap<K, V>

where K: KeyEnDeOrdered, V: ValueEnDe,

fn default() -> Self

Returns the “default value” for a type.

impl<'de, K, V> Deserialize<'de> for VerMap<K, V>

fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<K, V> Serialize for VerMap<K, V>

fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>

where S: Serializer,

Serialize this value into the given Serde serializer.