Struct Prolly 

pub struct Prolly<S: Store> { /* private fields */ }

Prolly tree manager

Provides the high-level API for working with Prolly trees. Generic over the storage backend S.

Example

use prolly::{Prolly, MemStore, Config};

let store = MemStore::new();
let prolly = Prolly::new(store, Config::default());
let tree = prolly.create();

Implementations

impl<S: Store> Prolly<S>

pub fn prove_key(&self, tree: &Tree, key: &[u8]) -> Result<KeyProof, Error>

Build a root-to-leaf proof for key.

The returned proof is self-contained and can be verified without access to this store. A valid proof may prove either key presence or absence.

pub fn prove_keys<K: AsRef<[u8]>>( &self, tree: &Tree, keys: &[K], ) -> Result<MultiKeyProof, Error>

Build one shared proof for multiple keys.

The returned proof de-duplicates shared path nodes while preserving the input key order. A valid proof may prove a mix of key presence and absence.

pub fn prove_range( &self, tree: &Tree, start: &[u8], end: Option<&[u8]>, ) -> Result<RangeProof, Error>

Build a complete proof for every entry in [start, end).

The returned proof contains all overlapping child subtrees needed to verify range completeness without access to this store.

pub fn prove_prefix( &self, tree: &Tree, prefix: &[u8], ) -> Result<RangeProof, Error>

Build a complete proof for every entry whose key starts with prefix.

This is equivalent to calling Prolly::prove_range with bounds from crate::prefix_range, but makes prefix/namespace proofs explicit at API boundaries.

pub fn prove_range_page( &self, tree: &Tree, cursor: &RangeCursor, end: Option<&[u8]>, limit: usize, ) -> Result<ProvedRangePage, Error>

Read a bounded range page and build a proof for exactly that page window.

The proof uses the cursor’s exclusive after bound instead of converting it into an inclusive key. This preserves raw byte-key semantics even when the cursor key is a prefix of later keys.

pub fn prove_diff_page( &self, base: &Tree, other: &Tree, cursor: &RangeCursor, end: Option<&[u8]>, limit: usize, ) -> Result<ProvedDiffPage, Error>

Read a bounded diff page and build a proof for exactly that page.

Verification recomputes the page from two range-page proofs and, when the result has a continuation cursor, two key proofs for the first omitted diff key.

impl<S: Store> Prolly<S>

pub fn snapshots(&self, namespace: SnapshotNamespace) -> SnapshotManager<'_, S>

Return a snapshot manager for the provided namespace.

pub fn branch_snapshots(&self) -> SnapshotManager<'_, S>

Return a branch snapshot manager using refs/heads/ names.

pub fn tag_snapshots(&self) -> SnapshotManager<'_, S>

Return a tag snapshot manager using refs/tags/ names.

pub fn checkpoint_snapshots(&self) -> SnapshotManager<'_, S>

Return a checkpoint snapshot manager using refs/checkpoints/ names.

impl<S> Prolly<S>

where S: Store + ManifestStore + TransactionalStore,

pub fn begin_transaction(&self) -> Result<ProllyTransaction<'_, S>, Error>

Start a strict optimistic transaction.

pub fn begin_owned_transaction( &self, ) -> Result<OwnedProllyTransaction<S>, Error>

where S: Clone,

Start a strict optimistic transaction that owns a cloned store handle.

This variant is intended for FFI bindings and other APIs that cannot hold Rust borrows across calls.

pub fn transaction<T>( &self, f: impl FnOnce(&mut ProllyTransaction<'_, S>) -> Result<T, Error>, ) -> Result<T, Error>

Run a closure in a transaction, committing on success and rolling back automatically when the closure returns an error or commit validation fails.

impl<S: Store> Prolly<S>

pub fn new(store: S, config: Config) -> Self

Create a new Prolly tree manager with the given store and configuration.

Arguments

• store - Storage backend implementing the Store trait
• config - Tree configuration (chunking parameters, encoding, etc.)

pub fn create(&self) -> Tree

Create a new empty tree.

Returns a Tree with no root (empty tree).

pub fn build_from_entries( &self, entries: Vec<(Vec<u8>, Vec<u8>)>, ) -> Result<Tree, Error>

where S: Clone + Send + Sync, S::Error: Send + Sync,

Build a tree from key/value entries using [BatchBuilder].

The builder sorts entries by byte-lexicographic key order before chunking, so callers may provide unsorted input. Duplicate keys are preserved with the same semantics as [BatchBuilder].

pub fn build_from_sorted_entries( &self, entries: Vec<(Vec<u8>, Vec<u8>)>, ) -> Result<Tree, Error>

where S: Clone + Send + Sync, S::Error: Send + Sync,

Build a tree from entries that are already sorted by key.

This delegates to [SortedBatchBuilder] and returns Error::UnsortedInput if any key is lower than the previous key.

pub fn get(&self, tree: &Tree, key: &[u8]) -> Result<Option<Vec<u8>>, Error>

Get value by key from the tree.

Traverses from root to leaf using binary search at each level.

Arguments

• tree - The tree to search
• key - The key to look up

Returns

• Ok(Some(value)) if the key exists
• Ok(None) if the key does not exist
• Err on storage or deserialization errors

pub fn first_entry( &self, tree: &Tree, ) -> Result<Option<(Vec<u8>, Vec<u8>)>, Error>

Return the first key-value entry in key order.

pub fn last_entry( &self, tree: &Tree, ) -> Result<Option<(Vec<u8>, Vec<u8>)>, Error>

Return the last key-value entry in key order.

pub fn lower_bound( &self, tree: &Tree, key: &[u8], ) -> Result<Option<(Vec<u8>, Vec<u8>)>, Error>

Return the first entry whose key is greater than or equal to key.

pub fn upper_bound( &self, tree: &Tree, key: &[u8], ) -> Result<Option<(Vec<u8>, Vec<u8>)>, Error>

Return the first entry whose key is strictly greater than key.

pub fn get_value_ref( &self, tree: &Tree, key: &[u8], ) -> Result<Option<ValueRef>, Error>

Get a stored large-value reference by key.

Non-envelope values are returned as blob::ValueRef::Inline, so this can inspect trees that mix ordinary raw values and offloaded blob references.

pub fn get_large_value<B>( &self, blob_store: &B, tree: &Tree, key: &[u8], ) -> Result<Option<Vec<u8>>, Error>

where B: BlobStore,

Get a value by key, resolving offloaded blob references when present.

pub fn get_many<K: AsRef<[u8]>>( &self, tree: &Tree, keys: &[K], ) -> Result<Vec<Option<Vec<u8>>>, Error>

Get multiple values from the tree while preserving caller order.

This descends the tree level-by-level and batches node loads for the current lookup frontier. It is useful for random read-after-write verification and merge conflict checks because shared ancestors and leaves are loaded once instead of once per key.

Duplicate keys are allowed; each output slot corresponds to the input key at the same index.

Arguments

• tree - The tree to search
• keys - Keys to look up

Returns

A vector of values in the same order as keys.

Example

use prolly::{Config, MemStore, Prolly};

let prolly = Prolly::new(MemStore::new(), Config::default());
let tree = prolly.create();
let tree = prolly.put(&tree, b"a".to_vec(), b"1".to_vec()).unwrap();
let tree = prolly.put(&tree, b"b".to_vec(), b"2".to_vec()).unwrap();

let values = prolly.get_many(&tree, &[b"b".to_vec(), b"missing".to_vec(), b"a".to_vec()]).unwrap();
assert_eq!(values, vec![Some(b"2".to_vec()), None, Some(b"1".to_vec())]);

pub fn put( &self, tree: &Tree, key: Vec<u8>, val: Vec<u8>, ) -> Result<Tree, Error>

Insert or update a key-value pair in the tree.

This operation is immutable - it returns a new tree rather than modifying the existing one.

Arguments

• tree - The tree to modify
• key - The key to insert/update
• val - The value to associate with the key

Returns

• Ok(new_tree) with the updated tree
• Err on storage or deserialization errors

Idempotence

If the key already exists with the same value, returns the original tree unchanged.

pub fn put_large_value<B>( &self, blob_store: &B, tree: &Tree, key: Vec<u8>, value: Vec<u8>, config: LargeValueConfig, ) -> Result<Tree, Error>

where B: BlobStore,

Insert or update a value, offloading large payloads to a blob store.

Values larger than config.inline_threshold are written to blob_store and represented in the tree by a compact content-addressed reference. Smaller values are stored as raw leaf bytes unless they start with the value-reference magic prefix, in which case they are escaped with an inline envelope.

pub fn delete(&self, tree: &Tree, key: &[u8]) -> Result<Tree, Error>

Delete a key from the tree.

This operation is immutable - it returns a new tree rather than modifying the existing one.

Arguments

• tree - The tree to modify
• key - The key to delete

Returns

• Ok(new_tree) with the key removed (or unchanged if key didn’t exist)
• Err on storage or deserialization errors

Idempotence

If the key doesn’t exist, returns the original tree unchanged.

pub fn range<'a>( &'a self, tree: &Tree, start: &[u8], end: Option<&[u8]>, ) -> Result<RangeIter<'a, S>, Error>

Iterate over a range of key-value pairs.

Returns an iterator that yields (key, value) pairs in lexicographic order, starting from start (inclusive) up to end (exclusive). Supports both inclusive start bounds and exclusive end bounds.

Arguments

• tree - The tree to iterate over
• start - The starting key (inclusive). Use &[] to start from the beginning.
• end - Optional ending key (exclusive). Use None to iterate to the end.

Returns

• Ok(RangeIter) - An iterator over the range
• Err on storage or deserialization errors during path finding

Example

use prolly::{Prolly, MemStore, Config};

let store = MemStore::new();
let prolly = Prolly::new(store, Config::default());
let tree = prolly.create();

// Insert some data
let tree = prolly.put(&tree, b"a".to_vec(), b"1".to_vec()).unwrap();
let tree = prolly.put(&tree, b"b".to_vec(), b"2".to_vec()).unwrap();
let tree = prolly.put(&tree, b"c".to_vec(), b"3".to_vec()).unwrap();

// Iterate over all keys
for result in prolly.range(&tree, &[], None).unwrap() {
    let (key, val) = result.unwrap();
    println!("{:?} -> {:?}", key, val);
}

// Iterate over a specific range [b, c)
for result in prolly.range(&tree, b"b", Some(b"c")).unwrap() {
    let (key, val) = result.unwrap();
    println!("{:?} -> {:?}", key, val);
}

pub fn prefix<'a>( &'a self, tree: &Tree, prefix: &[u8], ) -> Result<RangeIter<'a, S>, Error>

Create a range iterator over all keys that start with prefix.

pub fn prefix_page( &self, tree: &Tree, prefix: &[u8], cursor: &RangeCursor, limit: usize, ) -> Result<RangePage, Error>

Read a bounded page over all keys that start with prefix.

A start cursor begins at the prefix start. A resumed cursor continues strictly after its stored key while the prefix end remains exclusive.

pub fn range_after<'a>( &'a self, tree: &Tree, after_key: &[u8], end: Option<&[u8]>, ) -> Result<RangeIter<'a, S>, Error>

Create a range iterator that resumes strictly after after_key.

Persist the last key successfully processed, then resume with this method to avoid yielding that key again. The end bound remains exclusive.

pub fn range_from_cursor<'a>( &'a self, tree: &Tree, cursor: &RangeCursor, end: Option<&[u8]>, ) -> Result<RangeIter<'a, S>, Error>

Create a range iterator from a stable range cursor.

pub fn range_page( &self, tree: &Tree, cursor: &RangeCursor, end: Option<&[u8]>, limit: usize, ) -> Result<RangePage, Error>

Read a bounded page from a range scan.

cursor is either RangeCursor::start or a cursor returned by a previous page. end is exclusive. When limit is zero this returns an empty page with the original cursor so callers can treat zero-sized requests as no-ops.

pub fn reverse_page( &self, tree: &Tree, cursor: &ReverseCursor, start: &[u8], limit: usize, ) -> Result<ReversePage, Error>

Read a bounded page in descending key order.

start is an inclusive lower bound. A start cursor scans from the end of the range; a resumed cursor scans keys strictly before its stored key.

pub fn prefix_reverse_page( &self, tree: &Tree, prefix: &[u8], cursor: &ReverseCursor, limit: usize, ) -> Result<ReversePage, Error>

Read a bounded page over keys that start with prefix in descending key order.

A start cursor scans from the end of the prefix range. A resumed cursor continues strictly before its stored key while the prefix start and end remain enforced.

pub fn diff(&self, base: &Tree, other: &Tree) -> Result<Vec<Diff>, Error>

Compute the difference between two trees.

Returns a vector of Diff entries representing the changes needed to transform base into other. Yields Added entries for keys that exist in other but not in base, Changed entries for keys with different values, and Removed entries for keys that exist in base but not in other.

Arguments

• base - The base tree to compare from
• other - The other tree to compare to

Returns

• Ok(Vec<Diff>) - A vector of differences
• Err on storage or deserialization errors

Short-circuit

If both trees have the same root CID, returns an empty vector immediately.

Example

use prolly::{Prolly, MemStore, Config};

let store = MemStore::new();
let prolly = Prolly::new(store, Config::default());
let base = prolly.create();

let base = prolly.put(&base, b"a".to_vec(), b"1".to_vec()).unwrap();
let other = prolly.put(&base, b"b".to_vec(), b"2".to_vec()).unwrap();

let diffs = prolly.diff(&base, &other).unwrap();
// diffs contains Added { key: b"b", val: b"2" }

pub fn range_diff( &self, base: &Tree, other: &Tree, start: &[u8], end: Option<&[u8]>, ) -> Result<Vec<Diff>, Error>

Compute the difference between two trees within a half-open key range.

Returns only changes whose key is in [start, end). Unlike collecting two ranges and comparing them, this walks the tree shape directly and skips equal or out-of-range subtrees by CID and key span.

pub fn diff_from_cursor( &self, base: &Tree, other: &Tree, cursor: &RangeCursor, end: Option<&[u8]>, ) -> Result<Vec<Diff>, Error>

Compute diffs from a stable cursor.

This resumes strictly after the cursor key, so callers can persist the last processed diff key and avoid re-processing it on the next scan. end remains an exclusive upper bound.

pub fn diff_page( &self, base: &Tree, other: &Tree, cursor: &RangeCursor, end: Option<&[u8]>, limit: usize, ) -> Result<DiffPage, Error>

Read a bounded page of diffs from a stable cursor.

cursor is either RangeCursor::start or a cursor returned by a previous page. end is exclusive. When limit is zero this returns an empty page with the original cursor so callers can treat zero-sized requests as no-ops.

pub fn structural_diff_page( &self, base: &Tree, other: &Tree, cursor: Option<&StructuralDiffCursor>, limit: usize, ) -> Result<StructuralDiffPage, Error>

Read a bounded page from the structural diff traversal.

This preserves the CID frontier between pages instead of resuming from a key. It is better suited to long-running sync or indexing jobs where preserving subtree pruning across checkpoints matters. Pass None to start, then pass the returned cursor until next_cursor is None.

pub fn merge( &self, base: &Tree, left: &Tree, right: &Tree, resolver: Option<Resolver>, ) -> Result<Tree, Error>

Merge two trees using three-way merge.

Performs a three-way merge using base as the common ancestor. Changes from both left and right are combined into a single tree. Uses the diff algorithm to efficiently identify entries to add.

Arguments

• base - The common ancestor tree
• left - The left branch tree
• right - The right branch tree
• resolver - Optional conflict resolver function

Returns

• Ok(merged_tree) - The merged tree
• Err(Error::Conflict) - If a conflict occurs and no resolver is provided or the resolver returns Resolution::Unresolved

Conflict Handling

A conflict occurs when both left and right modify the same key differently from base. When this happens:

• If a resolver is provided, it’s called with the conflict information
• If the resolver returns Resolution::Value, that value is used
• If the resolver returns Resolution::Delete, the key is removed
• If the resolver returns Resolution::Unresolved or no resolver is provided, an error is returned

Keys that have the same value in both trees are included once in the result.

Example

use prolly::{Prolly, MemStore, Config};

let store = MemStore::new();
let prolly = Prolly::new(store, Config::default());
let base = prolly.create();

// Create base tree
let base = prolly.put(&base, b"a".to_vec(), b"1".to_vec()).unwrap();

// Create divergent branches
let left = prolly.put(&base, b"b".to_vec(), b"2".to_vec()).unwrap();
let right = prolly.put(&base, b"c".to_vec(), b"3".to_vec()).unwrap();

// Merge without conflicts
let merged = prolly.merge(&base, &left, &right, None).unwrap();

// Merged tree has all keys
assert!(prolly.get(&merged, b"a").unwrap().is_some());
assert!(prolly.get(&merged, b"b").unwrap().is_some());
assert!(prolly.get(&merged, b"c").unwrap().is_some());

pub fn merge_explain( &self, base: &Tree, left: &Tree, right: &Tree, resolver: Option<Resolver>, ) -> MergeExplanation

Perform a three-way merge and return structured diagnostic trace events.

This is the diagnostics-oriented counterpart to Prolly::merge. The returned crate::MergeExplanation keeps its trace even when the merge result is an error, which is useful for custom resolver debugging and sync-job observability.

Example

use prolly::{Config, MemStore, MergeTraceEvent, Prolly};

let prolly = Prolly::new(MemStore::new(), Config::default());
let base = prolly
    .put(&prolly.create(), b"a".to_vec(), b"1".to_vec())
    .unwrap();
let left = prolly
    .put(&base, b"b".to_vec(), b"2".to_vec())
    .unwrap();
let right = prolly
    .put(&base, b"c".to_vec(), b"3".to_vec())
    .unwrap();

let explanation = prolly.merge_explain(&base, &left, &right, None);
assert!(explanation
    .trace
    .events
    .iter()
    .any(|event| matches!(event, MergeTraceEvent::BatchMerge { .. })));

let merged = explanation.into_result().unwrap();
assert!(prolly.get(&merged, b"c").unwrap().is_some());

pub fn merge_range( &self, base: &Tree, left: &Tree, right: &Tree, start: &[u8], end: Option<&[u8]>, resolver: Option<Resolver>, ) -> Result<Tree, Error>

Merge only right-side changes whose keys are in [start, end).

Keys outside the range are left exactly as they are in left. Conflict detection and resolver behavior match Prolly::merge, but only for keys inside the requested range.

Example

use prolly::{Config, MemStore, Prolly};

let prolly = Prolly::new(MemStore::new(), Config::default());
let base = prolly
    .put(&prolly.create(), b"doc/1/title".to_vec(), b"old".to_vec())
    .unwrap();
let left = prolly
    .put(&base, b"doc/2/title".to_vec(), b"local".to_vec())
    .unwrap();
let right = prolly
    .put(&base, b"doc/1/title".to_vec(), b"remote".to_vec())
    .unwrap();

let merged = prolly
    .merge_range(&base, &left, &right, b"doc/1/", Some(b"doc/2/"), None)
    .unwrap();

assert_eq!(
    prolly.get(&merged, b"doc/1/title").unwrap(),
    Some(b"remote".to_vec())
);
assert_eq!(
    prolly.get(&merged, b"doc/2/title").unwrap(),
    Some(b"local".to_vec())
);

pub fn merge_prefix( &self, base: &Tree, left: &Tree, right: &Tree, prefix: &[u8], resolver: Option<Resolver>, ) -> Result<Tree, Error>

Merge only right-side changes whose keys start with prefix.

This is a convenience wrapper over Prolly::merge_range using the lexicographic prefix bounds from crate::prefix_range.

pub fn collect_stats(&self, tree: &Tree) -> Result<TreeStats, Error>

Collect comprehensive statistics about a tree

Traverses the entire tree once, gathering metrics about structure, size, distribution, and efficiency.

Arguments

• tree - The tree to analyze

Returns

• Ok(TreeStats) - Collected statistics
• Err(Error) - On storage or deserialization errors

Example

use prolly::{Prolly, MemStore, Config};

let store = MemStore::new();
let prolly = Prolly::new(store, Config::default());
let tree = prolly.create();

let tree = prolly.put(&tree, b"key".to_vec(), b"value".to_vec()).unwrap();
let stats = prolly.collect_stats(&tree).unwrap();
println!("{:?}", stats);

pub fn debug_tree(&self, tree: &Tree) -> Result<TreeDebugView, Error>

Return a deterministic debug view of the tree grouped by level.

This is intended for diagnostics, CLI inspection, and tests that need to inspect tree shape without depending on private node traversal code. Levels are ordered from root to leaves, and each node includes its CID, entry count, fill factor, encoded size, and key range.

Example

use prolly::{Config, MemStore, Prolly};

let prolly = Prolly::new(MemStore::new(), Config::default());
let tree = prolly.put(&prolly.create(), b"k".to_vec(), b"v".to_vec()).unwrap();

let view = prolly.debug_tree(&tree).unwrap();
assert!(view.to_text().contains("level 0"));

pub fn debug_compare_trees( &self, left: &Tree, right: &Tree, ) -> Result<TreeDebugComparison, Error>

Compare two trees by CID sharing and rewritten subtrees.

Shared nodes are counted once. Left-only and right-only nodes represent subtrees that were rewritten, added, or removed between the two roots.

Example

use prolly::{Config, MemStore, Prolly};

let prolly = Prolly::new(MemStore::new(), Config::default());
let before = prolly.put(&prolly.create(), b"k".to_vec(), b"v1".to_vec()).unwrap();
let after = prolly.put(&before, b"k".to_vec(), b"v2".to_vec()).unwrap();

let comparison = prolly.debug_compare_trees(&before, &after).unwrap();
assert_eq!(comparison.left_only_nodes, 1);
assert_eq!(comparison.right_only_nodes, 1);

pub fn stats_diff( &self, before: &Tree, after: &Tree, ) -> Result<StatsComparison, Error>

Compare structural statistics between two trees.

This collects TreeStats for both trees and returns a combined report with the baseline stats, candidate stats, absolute deltas, and percentage deltas. Deltas are computed as after - before.

Example

use prolly::{Config, MemStore, Prolly};

let prolly = Prolly::new(MemStore::new(), Config::default());
let before = prolly.create();
let after = prolly.put(&before, b"key".to_vec(), b"value".to_vec()).unwrap();

let comparison = prolly.stats_diff(&before, &after).unwrap();
assert_eq!(comparison.absolute.total_key_value_pairs_diff, 1);

pub fn mark_reachable(&self, roots: &[Tree]) -> Result<GcReachability, Error>

Mark all content-addressed nodes reachable from retained tree roots.

This is the safe first phase of garbage collection. Empty roots are ignored, duplicate roots and shared subtrees are counted once, and the returned CID list is sorted for deterministic planning.

Example

use prolly::{Config, MemStore, Prolly};

let prolly = Prolly::new(MemStore::new(), Config::default());
let tree = prolly.create();
let tree = prolly.put(&tree, b"k".to_vec(), b"v".to_vec()).unwrap();

let reachable = prolly.mark_reachable(&[tree]).unwrap();
assert_eq!(reachable.live_nodes, reachable.cids().len());

pub fn plan_missing_nodes<D>( &self, tree: &Tree, destination: &D, ) -> Result<MissingNodePlan, Error>

where D: Store,

Plan which content-addressed nodes a destination store is missing for a tree.

This is the dry-run phase for Merkle-style store synchronization. The source tree is walked from its root, the destination is checked with an ordered batch read, and any present destination bytes are verified against their requested CID. Missing source bytes are also verified before their byte weight is counted.

Example

use prolly::{Config, MemStore, Prolly};
use std::sync::Arc;

let source = Arc::new(MemStore::new());
let destination = Arc::new(MemStore::new());
let prolly = Prolly::new(source, Config::default());

let tree = prolly.create();
let tree = prolly.put(&tree, b"k".to_vec(), b"v".to_vec()).unwrap();

let plan = prolly.plan_missing_nodes(&tree, &destination).unwrap();
assert_eq!(plan.missing_nodes, plan.missing_cids().len());

pub fn copy_missing_nodes<D>( &self, tree: &Tree, destination: &D, ) -> Result<MissingNodeCopy, Error>

where D: Store,

Copy all destination-missing nodes required by tree.

The destination receives only immutable content-addressed node bytes it does not already have. Source and destination bytes are verified by CID before the copy succeeds.

Example

use prolly::{Config, MemStore, Prolly};
use std::sync::Arc;

let source = Arc::new(MemStore::new());
let destination = Arc::new(MemStore::new());
let source_prolly = Prolly::new(source, Config::default());

let tree = source_prolly.create();
let tree = source_prolly
    .put(&tree, b"k".to_vec(), b"v".to_vec())
    .unwrap();

let copied = source_prolly.copy_missing_nodes(&tree, &destination).unwrap();
assert_eq!(copied.copied_nodes, copied.plan.missing_nodes);

let destination_prolly = Prolly::new(destination, tree.config.clone());
assert_eq!(destination_prolly.get(&tree, b"k").unwrap(), Some(b"v".to_vec()));

pub fn export_snapshot(&self, tree: &Tree) -> Result<SnapshotBundle, Error>

Export one tree and all reachable serialized node bytes as a portable bundle.

The returned bundle is self-contained: importing it into an empty store makes the returned bundle.tree readable by a manager using that store. Node entries are sorted by raw CID bytes for deterministic transport and each node byte payload is verified against its CID before the export succeeds.

pub fn import_snapshot(&self, bundle: &SnapshotBundle) -> Result<Tree, Error>

Import a portable tree snapshot bundle into this manager’s store.

Import validates that the bundle is exactly self-contained for its tree root before mutating the destination store. It deduplicates identical repeated node entries, rejects conflicting duplicates, verifies every node byte payload against its CID, then writes the validated node set.

pub fn plan_gc<I, C>( &self, roots: &[Tree], candidates: I, ) -> Result<GcPlan, Error>

where I: IntoIterator<Item = C>, C: Borrow<Cid>,

Build a dry-run garbage-collection plan from retained roots and caller-supplied candidate CIDs.

The generic Store trait cannot list all stored nodes, so callers provide the candidate set. Pass every content CID that may be swept, and pass every tree root that must be retained. Unreachable candidates that are present in the store are reported as reclaimable; missing candidates are counted separately and never treated as reclaimable bytes.

pub fn sweep_gc<I, C>( &self, roots: &[Tree], candidates: I, ) -> Result<GcSweep, Error>

where I: IntoIterator<Item = C>, C: Borrow<Cid>,

Delete unreachable candidate nodes from the backing store.

This runs Prolly::plan_gc first, then deletes exactly the plan’s reclaimable candidates with a single store batch. The manager cache is cleared after deletion so swept nodes are not still readable from this process’ in-memory cache.

pub fn mark_reachable_blobs( &self, roots: &[Tree], ) -> Result<BlobGcReachability, Error>

Mark all offloaded blobs reachable from retained tree roots.

This scans reachable leaf values for blob::ValueRef::Blob envelopes. Ordinary raw values and escaped inline values are ignored. Empty roots, duplicate roots, shared subtrees, and duplicate blob references are counted once where appropriate.

pub fn plan_blob_gc<B, I, C>( &self, blob_store: &B, roots: &[Tree], candidates: I, ) -> Result<BlobGcPlan, Error>

where B: BlobStore, I: IntoIterator<Item = C>, C: Borrow<BlobRef>,

Build a dry-run garbage-collection plan for offloaded blobs.

The generic BlobStore trait does not require blob listing, so callers provide candidate blob references. Pass every blob reference that may be swept, and every tree root that must be retained. Unreachable candidates that are present in the blob store are reported as reclaimable; missing candidates are counted separately.

pub fn sweep_blob_gc<B, I, C>( &self, blob_store: &B, roots: &[Tree], candidates: I, ) -> Result<BlobGcSweep, Error>

where B: BlobStore, I: IntoIterator<Item = C>, C: Borrow<BlobRef>,

Delete unreachable candidate blobs from the backing blob store.

This runs Prolly::plan_blob_gc first, then deletes exactly the plan’s reclaimable blob references. Missing candidates are ignored.

pub fn plan_blob_store_gc<B>( &self, blob_store: &B, roots: &[Tree], ) -> Result<BlobGcPlan, Error>

where B: BlobStoreScan,

Build a dry-run blob garbage-collection plan using the blob store’s full blob-reference listing.

This is available only when the blob backend implements BlobStoreScan. It is equivalent to calling BlobStoreScan::list_blob_refs and then Prolly::plan_blob_gc.

pub fn sweep_blob_store_gc<B>( &self, blob_store: &B, roots: &[Tree], ) -> Result<BlobGcSweep, Error>

where B: BlobStoreScan,

Sweep unreachable blobs from every blob reference listed by the blob store.

This is available only when the blob backend implements BlobStoreScan.

pub fn plan_store_gc(&self, roots: &[Tree]) -> Result<GcPlan, Error>

where S: NodeStoreScan,

Build a dry-run garbage-collection plan using the store’s full node-CID listing.

This is available only when the backing store implements NodeStoreScan. It is equivalent to calling NodeStoreScan::list_node_cids and then Prolly::plan_gc.

pub fn sweep_store_gc(&self, roots: &[Tree]) -> Result<GcSweep, Error>

where S: NodeStoreScan,

Sweep unreachable nodes from every node CID listed by the backing store.

This is available only when the backing store implements NodeStoreScan. The manager cache is cleared if any nodes are deleted.

pub fn plan_store_gc_for_retention( &self, retention: &NamedRootRetention, ) -> Result<GcPlan, Error>

where S: NodeStoreScan + ManifestStoreScan,

Build a store-wide GC plan using roots selected from named-root manifests.

This combines Prolly::load_retained_named_roots with Prolly::plan_store_gc. Exact-name policies fail with Error::MissingNamedRoots if any requested name is absent so a typo cannot silently drop a retained branch from the GC plan.

pub fn sweep_store_gc_for_retention( &self, retention: &NamedRootRetention, ) -> Result<GcSweep, Error>

where S: NodeStoreScan + ManifestStoreScan,

Sweep store-wide unreachable nodes using roots selected from manifests.

This combines Prolly::load_retained_named_roots with Prolly::sweep_store_gc. Exact-name policies fail with Error::MissingNamedRoots if any requested name is absent.

pub fn cursor(&self, tree: &Tree, key: &[u8]) -> Result<Cursor, Error>

Create a cursor positioned at the given key.

Returns a cursor that can be used for efficient traversal through the tree. The cursor is positioned at the key if it exists, or at the greatest key less than or equal to the target key.

Arguments

• tree - The tree to navigate
• key - The key to position at

Returns

• Ok(Cursor) - A cursor positioned at or near the key
• Err - If a storage error occurs

Example

use prolly::{Prolly, MemStore, Config};

let store = std::sync::Arc::new(MemStore::new());
let prolly = Prolly::new(store.clone(), Config::default());
let mut tree = prolly.create();

tree = prolly.put(&tree, b"a".to_vec(), b"1".to_vec()).unwrap();
tree = prolly.put(&tree, b"b".to_vec(), b"2".to_vec()).unwrap();

let cursor = prolly.cursor(&tree, b"a").unwrap();
assert!(cursor.is_valid());
assert_eq!(cursor.get_key(), Some(b"a".as_slice()));

pub fn cursor_window( &self, tree: &Tree, key: &[u8], end: Option<&[u8]>, limit: usize, ) -> Result<CursorWindow, Error>

Seek with the internal cursor and read a bounded forward window.

This is the stateless, binding-friendly form of cursor navigation. It reports the cursor landing position for key, whether that position is an exact match, and up to limit entries starting at the first key greater than or equal to key. When entries are emitted, next_cursor resumes strictly after the last emitted key.

pub fn range_cursor<'a>( &'a self, tree: &Tree, start: &[u8], end: Option<&[u8]>, ) -> Result<CursorIterator<'a, S>, Error>

Create a cursor iterator for range queries.

Returns an iterator that yields (key, value) pairs in lexicographic order, starting from start (inclusive) up to end (exclusive).

Arguments

• tree - The tree to iterate over
• start - The starting key (inclusive). Use &[] to start from the beginning.
• end - Optional ending key (exclusive). Use None to iterate to the end.

Returns

• Ok(CursorIterator) - An iterator over the range
• Err - If a storage error occurs during cursor creation

Example

use prolly::{Prolly, MemStore, Config};

let store = std::sync::Arc::new(MemStore::new());
let prolly = Prolly::new(store.clone(), Config::default());
let mut tree = prolly.create();

tree = prolly.put(&tree, b"a".to_vec(), b"1".to_vec()).unwrap();
tree = prolly.put(&tree, b"b".to_vec(), b"2".to_vec()).unwrap();
tree = prolly.put(&tree, b"c".to_vec(), b"3".to_vec()).unwrap();

// Iterate over range [a, c)
let iter = prolly.range_cursor(&tree, b"a", Some(b"c")).unwrap();
let entries: Vec<_> = iter.collect();
assert_eq!(entries.len(), 2); // "a" and "b"

pub fn diff_cursor<'a>( &'a self, base: &Tree, other: &Tree, ) -> Result<DiffCursor<'a, S>, Error>

Create a streaming diff iterator between two trees.

Returns an iterator that yields Diff entries representing the changes needed to transform base into other. More memory-efficient than diff() for large trees as it doesn’t collect all differences upfront.

Arguments

• base - The base tree to compare from
• other - The other tree to compare to

Returns

• Ok(DiffCursor) - A streaming diff iterator
• Err(Error) - If cursor initialization fails

Example

use prolly::{Prolly, MemStore, Config, Diff};
use std::sync::Arc;

let store = Arc::new(MemStore::new());
let prolly = Prolly::new(store.clone(), Config::default());

let base = prolly.create();
let other = prolly.put(&base, b"key".to_vec(), b"val".to_vec()).unwrap();

// Stream differences
for diff in prolly.diff_cursor(&base, &other).unwrap() {
    println!("{:?}", diff);
}

// Or collect into Vec (equivalent to diff())
let diffs: Vec<Diff> = prolly.diff_cursor(&base, &other).unwrap().collect();

pub fn stream_diff<'a>( &'a self, base: &Tree, other: &Tree, ) -> Result<Box<dyn Iterator<Item = Result<Diff, Error>> + 'a>, Error>

Create a streaming diff iterator between two trees.

Returns an iterator that yields Result<Diff, Error> entries representing the changes needed to transform base into other. This method walks the same content-addressed structure as eager diff, so equal subtrees are skipped by CID and only changed subtrees are visited.

Arguments

• base - The base tree to compare from
• other - The other tree to compare to

Returns

• Ok(impl Iterator) - A streaming diff iterator yielding Result<Diff, Error>
• Err(Error) - If cursor initialization fails

Short-circuit

If both trees have the same root CID, returns an empty iterator immediately.

Example

use prolly::{Prolly, MemStore, Config, Diff};
use std::sync::Arc;

let store = Arc::new(MemStore::new());
let prolly = Prolly::new(store.clone(), Config::default());

let base = prolly.create();
let other = prolly.put(&base, b"key".to_vec(), b"val".to_vec()).unwrap();

// Stream differences with error handling
for diff_result in prolly.stream_diff(&base, &other).unwrap() {
    match diff_result {
        Ok(diff) => println!("{:?}", diff),
        Err(e) => eprintln!("Error: {}", e),
    }
}

// Collect successful diffs
let diffs: Vec<Diff> = prolly.stream_diff(&base, &other)
    .unwrap()
    .filter_map(|r| r.ok())
    .collect();

pub fn stream_conflicts<'a>( &'a self, base: &Tree, left: &'a Tree, right: &Tree, ) -> Result<Box<dyn Iterator<Item = Result<Conflict, Error>> + 'a>, Error>

Create a streaming merge-conflict iterator for a three-way merge.

This walks the same structural diff path as Prolly::stream_diff, compares each right-side change with left, and yields only keys that would require a resolver during Prolly::merge. Non-conflicting changes are skipped, and each yielded conflict preserves absence and deletion as None.

This is useful for UIs, background agents, and sync workflows that need to inspect or ask about conflicts before choosing a resolver strategy.

Example

use prolly::{Config, MemStore, Prolly};

let prolly = Prolly::new(MemStore::new(), Config::default());
let base = prolly
    .put(&prolly.create(), b"title".to_vec(), b"base".to_vec())
    .unwrap();
let left = prolly
    .put(&base, b"title".to_vec(), b"left".to_vec())
    .unwrap();
let right = prolly
    .put(&base, b"title".to_vec(), b"right".to_vec())
    .unwrap();

let conflicts = prolly
    .stream_conflicts(&base, &left, &right)
    .unwrap()
    .collect::<Result<Vec<_>, _>>()
    .unwrap();

assert_eq!(conflicts.len(), 1);
assert_eq!(conflicts[0].key, b"title".to_vec());

pub fn clear_cache(&self)

Clear the in-process immutable node cache.

This is mostly useful after external store maintenance or tests that intentionally mutate the backing store outside the Prolly API.

pub fn cache_len(&self) -> usize

Return the number of cached nodes in this Prolly manager.

pub fn cache_bytes_len(&self) -> usize

Return the serialized-node byte weight retained by this manager cache.

pub fn cache_pinned_len(&self) -> usize

Return the number of pinned nodes currently retained by this manager.

Pinned nodes are a cache hint only. They may temporarily keep the cache above configured node or byte limits, and cache misses still fall back to the backing store.

pub fn cache_pinned_bytes_len(&self) -> usize

Return the serialized-node byte weight of pinned cache entries.

pub fn pin_tree_root(&self, tree: &Tree) -> Result<usize, Error>

Pin the root node of a tree in this manager’s node cache.

This is useful for hot snapshots where repeated reads are expected to start from the same root. Empty trees pin nothing. The return value is the number of nodes that became newly pinned.

pub fn pin_tree_path(&self, tree: &Tree, key: &[u8]) -> Result<usize, Error>

Pin the root-to-leaf lookup path for key in this manager’s node cache.

The path is the same traversal that a lookup or point mutation would use for the key, including the would-be leaf for missing keys. Empty trees pin nothing. The return value is the number of nodes that became newly pinned.

pub fn publish_prefix_path_hint( &self, tree: &Tree, prefix: &[u8], ) -> Result<bool, Error>

Persist a correctness-optional root-to-leaf path hint for a hot prefix.

The hint records the path a range scan would use to seek to prefix. Durable stores that support hints can use it to warm a fresh manager’s cache before repeatedly scanning a hot tenant, document, workspace, or index shard. Empty trees and stores without hint support return Ok(false).

Hints are performance sidecars only. A missing, stale, or malformed hint is ignored by Prolly::hydrate_prefix_path_hint, and all tree operations retain their normal traversal fallback.

pub fn hydrate_prefix_path_hint( &self, tree: &Tree, prefix: &[u8], ) -> Result<bool, Error>

Hydrate this manager’s node cache from a persisted prefix path hint.

Returns Ok(true) when a valid hint was found and loaded. Returns Ok(false) when the tree is empty, the store does not support hints, no hint exists, or the hint cannot be validated for this exact root and prefix. Store I/O errors are still returned.

pub fn publish_changed_spans_hint<I>( &self, base: &Tree, changed: &Tree, spans: I, ) -> Result<bool, Error>

where I: IntoIterator<Item = ChangedSpan>,

Persist recently changed key spans for a root transition.

This is useful when a writer already knows the affected key ranges and wants a later sync or indexing job to prioritize those ranges. Spans are sorted and coalesced before storage. Empty span sets, unchanged roots, and stores without hint support return Ok(false).

Changed-span hints are correctness-optional. Callers that need an authoritative diff should still use Prolly::diff, Prolly::range_diff, or Prolly::structural_diff_page.

pub fn load_changed_spans_hint( &self, base: &Tree, changed: &Tree, ) -> Result<Option<ChangedSpanHint>, Error>

Load recently changed key spans for a root transition.

Returns Ok(Some(_)) only when a well-formed hint exists for this exact (base, changed) root pair. Missing, stale, malformed, or invalid span hints return Ok(None), preserving the caller’s normal diff fallback.

pub fn unpin_all_cache_nodes(&self) -> usize

Unpin all pinned node-cache entries for this manager.

After unpinning, normal cache eviction runs immediately. Returns the number of entries that were pinned before this call.

pub fn metrics(&self) -> ProllyMetricsSnapshot

Return cumulative cache and node I/O metrics for this manager.

pub fn reset_metrics(&self)

Reset cumulative manager metrics to zero.

This does not clear the node cache; call Prolly::clear_cache when you want the next operation to run from a cold manager cache.

pub fn load_named_root(&self, name: &[u8]) -> Result<Option<Tree>, Error>

where S: ManifestStore,

Load a named root as a Tree through the underlying manifest store.

This is available when the store implements both Store and ManifestStore. Missing names return Ok(None).

pub fn load_named_roots<I, N>( &self, names: I, ) -> Result<NamedRootSelection, Error>

where S: ManifestStore, I: IntoIterator<Item = N>, N: AsRef<[u8]>,

Load explicit named roots and report names that were absent.

Duplicate names are ignored after their first occurrence. Missing names are reported in NamedRootSelection::missing_names instead of being silently dropped so callers can decide whether to continue.

pub fn list_named_root_manifests(&self) -> Result<Vec<NamedRootManifest>, Error>

where S: ManifestStoreScan,

List every named root in the manifest store.

Results are sorted by raw name bytes when the backing store implements the ManifestStoreScan contract.

pub fn list_named_roots(&self) -> Result<Vec<NamedRoot>, Error>

where S: ManifestStoreScan,

List every named root in the manifest store.

Results are sorted by raw name bytes when the backing store implements the ManifestStoreScan contract.

pub fn load_retained_named_roots( &self, retention: &NamedRootRetention, ) -> Result<NamedRootSelection, Error>

where S: ManifestStoreScan,

Select named roots according to a retention policy.

Prefix and newest-by-name policies use manifest scanning. Exact policies load the requested names and report absent names explicitly.

pub fn publish_named_root(&self, name: &[u8], tree: &Tree) -> Result<(), Error>

where S: ManifestStore,

Publish a tree handle under a durable name.

This unconditionally replaces the existing named root. Use Prolly::compare_and_swap_named_root when coordinating concurrent writers.

pub fn publish_named_root_at_millis( &self, name: &[u8], tree: &Tree, timestamp_millis: u64, ) -> Result<(), Error>

where S: ManifestStore,

Publish a tree handle under a durable name with explicit timestamp metadata.

created_at_millis is preserved from the existing manifest when present; otherwise it is initialized to timestamp_millis. updated_at_millis is always set to timestamp_millis.

pub fn delete_named_root(&self, name: &[u8]) -> Result<(), Error>

where S: ManifestStore,

Delete a durable named root.

Deleting a missing name is not an error. This removes the mutable name only; it does not garbage-collect content-addressed nodes.

pub fn compare_and_swap_named_root( &self, name: &[u8], expected: Option<&Tree>, new: Option<&Tree>, ) -> Result<NamedRootUpdate, Error>

where S: ManifestStore,

Atomically update a named root when the current tree matches expected.

expected == None means the name must be absent. new == None deletes the name after a successful compare.

pub fn compare_and_swap_named_root_at_millis( &self, name: &[u8], expected: Option<&Tree>, new: Option<&Tree>, timestamp_millis: u64, ) -> Result<NamedRootUpdate, Error>

where S: ManifestStore,

Atomically update a named root with explicit timestamp metadata.

Tree-level compare-and-swap compares expected against the current tree handle, then performs the backend CAS against the exact current manifest. This keeps tree CAS stable even as manifests gain metadata fields.

pub fn store(&self) -> &S

Borrow the underlying store.

pub fn batch( &self, tree: &Tree, mutations: Vec<Mutation>, ) -> Result<Tree, Error>

Apply multiple mutations to a tree in a single optimized operation.

This method enables efficient bulk modifications (upserts and deletes) to an existing tree. Mutations are sorted by key, deduplicated (last-write-wins), grouped by affected leaf, and applied with a single atomic batch write.

Arguments

• tree - The tree to modify
• mutations - Vector of mutations to apply

Returns

• Ok(Tree) - New tree with all mutations applied
• Err(Error) - On storage or processing errors

Behavior

• Mutations are sorted by key for efficient processing
• Duplicate keys use last-write-wins semantics
• All new nodes are written atomically via Store::batch
• The input tree is not modified (immutable operation)

Example

use prolly::{Prolly, MemStore, Config, Mutation};

let store = MemStore::new();
let prolly = Prolly::new(store, Config::default());
let tree = prolly.create();

let mutations = vec![
    Mutation::Upsert { key: b"a".to_vec(), val: b"1".to_vec() },
    Mutation::Upsert { key: b"b".to_vec(), val: b"2".to_vec() },
    Mutation::Delete { key: b"c".to_vec() },
];

let new_tree = prolly.batch(&tree, mutations).unwrap();

pub fn batch_with_stats( &self, tree: &Tree, mutations: Vec<Mutation>, ) -> Result<BatchApplyResult, Error>

Apply batch mutations and return store-neutral execution stats.

The returned counters describe tree-level work such as affected leaves, write amplification, and which internal write path was selected.

pub fn append_batch( &self, tree: &Tree, mutations: Vec<Mutation>, ) -> Result<Tree, Error>

Apply append-heavy mutations using the optimized append path when safe.

If the mutations overlap existing data or cannot be applied as a pure append, this falls back to the regular batch implementation for correctness.

pub fn append_batch_with_stats( &self, tree: &Tree, mutations: Vec<Mutation>, ) -> Result<BatchApplyResult, Error>

Apply append-heavy mutations and return store-neutral execution stats.

If the append fast path cannot be used, the operation falls back to the regular batch implementation and reports the fallback path stats.

pub fn crdt_merge( &self, base: &Tree, left: &Tree, right: &Tree, config: &CrdtConfig, ) -> Result<Tree, Error>

Merge two trees using CRDT semantics for automatic conflict resolution.

Unlike the standard merge() method which can return Error::Conflict, this method uses CRDT (Conflict-free Replicated Data Type) semantics to automatically resolve all conflicts. This makes it suitable for distributed systems where concurrent modifications are common.

Arguments

• base - The common ancestor tree
• left - The left branch tree
• right - The right branch tree
• config - CRDT configuration specifying merge strategy and policies

Returns

• Ok(Tree) - The merged tree (never returns Error::Conflict)
• Err(Error) - Only on storage or deserialization errors

Merge Strategies

• LastWriterWins (LWW): Value with higher timestamp wins
• MultiValue (MV): Preserve all concurrent values as a set
• Custom: User-provided merge function

Example

use prolly::{Prolly, MemStore, Config, CrdtConfig, MergeStrategy};
use std::sync::Arc;

let store = Arc::new(MemStore::new());
let prolly = Prolly::new(store.clone(), Config::default());

let base = prolly.create();
let base = prolly.put(&base, b"key".to_vec(), b"value".to_vec()).unwrap();

// Create divergent branches
let left = prolly.put(&base, b"key".to_vec(), b"left".to_vec()).unwrap();
let right = prolly.put(&base, b"key".to_vec(), b"right".to_vec()).unwrap();

// CRDT merge - never fails with conflict
let config = CrdtConfig::default();
let merged = prolly.crdt_merge(&base, &left, &right, &config).unwrap();

pub fn parallel_batch( &self, tree: &Tree, mutations: Vec<Mutation>, config: &ParallelConfig, ) -> Result<Tree, Error>

Apply batch mutations with tunable batched route hydration.

This method uses the production batch writer with a [ParallelConfig] adapter. Stores that prefer batched reads use max_threads as the ordered route-hydration width once the mutation count reaches parallelism_threshold; smaller batches use a narrow route path to avoid unnecessary batching overhead.

Arguments

• tree - The tree to modify
• mutations - Vector of mutations to apply
• config - Parallel configuration controlling thread count and threshold

Returns

• Ok(Tree) - New tree with all mutations applied
• Err(Error) - On storage or processing errors

Behavior

• Uses append and coalesced-rebuild fast paths from the standard batch writer
• Bounds batched route hydration with max_threads when configured
• Uses batch_put for efficient I/O
• Maintains all tree invariants

Example

use prolly::{Prolly, MemStore, Config, Mutation, ParallelConfig};
use std::sync::Arc;

let store = Arc::new(MemStore::new());
let prolly = Prolly::new(store.clone(), Config::default());
let tree = prolly.create();

let mutations = vec![
    Mutation::Upsert { key: b"a".to_vec(), val: b"1".to_vec() },
    Mutation::Upsert { key: b"b".to_vec(), val: b"2".to_vec() },
];

let config = ParallelConfig::default();
let new_tree = prolly.parallel_batch(&tree, mutations, &config).unwrap();

pub fn parallel_batch_with_stats( &self, tree: &Tree, mutations: Vec<Mutation>, config: &ParallelConfig, ) -> Result<BatchApplyResult, Error>

Apply batch mutations with [ParallelConfig] and return execution stats.

The returned counters mirror Prolly::batch_with_stats and make the parallel-batch route observable across storage backends and language bindings.