prolly/
lib.rs

1//! # Prolly Trees
2//!
3//! A Rust implementation of Prolly Trees - content-addressable ordered search indexes
4//! that combine the efficiency of B+ trees with deterministic merging capabilities.
5//!
6//! ## Features
7//!
8//! - **Ordered key-value storage**: Keys are sorted lexicographically (byte comparison)
9//! - **Content-addressable nodes**: Each node has a unique CID (Content Identifier) derived from its content
10//! - **Deterministic structure**: Same content always produces the same tree structure
11//! - **Efficient diff/merge**: Compare trees by comparing root hashes, skip identical subtrees
12//! - **Pluggable storage**: Implement the [`Store`] trait for custom backends
13//!
14//! ## Quick Start
15//!
16//! ```rust
17//! use prolly::{Prolly, MemStore, Config};
18//!
19//! // Create a store and tree manager
20//! let store = MemStore::new();
21//! let prolly = Prolly::new(store, Config::default());
22//!
23//! // Create an empty tree
24//! let tree = prolly.create();
25//!
26//! // Insert key-value pairs (returns a new tree - immutable)
27//! let tree = prolly.put(&tree, b"name".to_vec(), b"Alice".to_vec()).unwrap();
28//! let tree = prolly.put(&tree, b"age".to_vec(), b"30".to_vec()).unwrap();
29//!
30//! // Retrieve values
31//! let name = prolly.get(&tree, b"name").unwrap();
32//! assert_eq!(name, Some(b"Alice".to_vec()));
33//!
34//! // Delete keys
35//! let tree = prolly.delete(&tree, b"age").unwrap();
36//! assert!(prolly.get(&tree, b"age").unwrap().is_none());
37//! ```
38//!
39//! ## Range Iteration
40//!
41//! ```rust
42//! use prolly::{Prolly, MemStore, Config};
43//!
44//! let store = MemStore::new();
45//! let prolly = Prolly::new(store, Config::default());
46//! let mut tree = prolly.create();
47//!
48//! // Insert some data
49//! tree = prolly.put(&tree, b"a".to_vec(), b"1".to_vec()).unwrap();
50//! tree = prolly.put(&tree, b"b".to_vec(), b"2".to_vec()).unwrap();
51//! tree = prolly.put(&tree, b"c".to_vec(), b"3".to_vec()).unwrap();
52//!
53//! // Iterate over all keys
54//! for result in prolly.range(&tree, &[], None).unwrap() {
55//!     let (key, val) = result.unwrap();
56//!     println!("{:?} -> {:?}", String::from_utf8_lossy(&key), String::from_utf8_lossy(&val));
57//! }
58//!
59//! // Iterate over a specific range [b, c)
60//! for result in prolly.range(&tree, b"b", Some(b"c")).unwrap() {
61//!     let (key, val) = result.unwrap();
62//!     // Only yields "b" -> "2"
63//! }
64//! ```
65//!
66//! ## Diff and Merge
67//!
68//! ```rust
69//! use prolly::{Prolly, MemStore, Config, Diff};
70//!
71//! let store = MemStore::new();
72//! let prolly = Prolly::new(store, Config::default());
73//!
74//! // Create base tree
75//! let base = prolly.create();
76//! let base = prolly.put(&base, b"a".to_vec(), b"1".to_vec()).unwrap();
77//!
78//! // Create two divergent branches
79//! let left = prolly.put(&base, b"b".to_vec(), b"2".to_vec()).unwrap();
80//! let right = prolly.put(&base, b"c".to_vec(), b"3".to_vec()).unwrap();
81//!
82//! // Compute diff
83//! let diffs = prolly.diff(&base, &left).unwrap();
84//! // diffs contains: Added { key: b"b", val: b"2" }
85//!
86//! // Three-way merge (no conflicts since changes are disjoint)
87//! let merged = prolly.merge(&base, &left, &right, None).unwrap();
88//!
89//! // Merged tree has all keys: a, b, c
90//! assert!(prolly.get(&merged, b"a").unwrap().is_some());
91//! assert!(prolly.get(&merged, b"b").unwrap().is_some());
92//! assert!(prolly.get(&merged, b"c").unwrap().is_some());
93//! ```
94//!
95//! ## Batch Building
96//!
97//! For bulk loading data, use [`BatchBuilder`] for parallel tree construction:
98//!
99//! ```rust
100//! use prolly::{BatchBuilder, MemStore, Config, Prolly};
101//! use std::sync::Arc;
102//!
103//! let store = Arc::new(MemStore::new());
104//! let config = Config::default();
105//!
106//! // Build tree from many entries in parallel
107//! let mut builder = BatchBuilder::new(store.clone(), config.clone());
108//! for i in 0..1000 {
109//!     builder.add(format!("key{:04}", i).into_bytes(), format!("val{}", i).into_bytes());
110//! }
111//! let tree = builder.build().unwrap();
112//!
113//! // Use the tree with Prolly
114//! let prolly = Prolly::new(store, config);
115//! let val = prolly.get(&tree, b"key0042").unwrap();
116//! assert!(val.is_some());
117//! ```
118//!
119//! ## Named Roots
120//!
121//! Use named-root helpers when an application needs durable names for immutable
122//! tree snapshots:
123//!
124//! A named root is a mutable pointer, not a live view. `put`, `delete`, `batch`,
125//! and `merge` return new immutable [`Tree`] handles and do not automatically
126//! advance any name. Publish the replacement tree explicitly, preferably with
127//! `compare_and_swap_named_root` when another writer could update the same
128//! name.
129//!
130//! ```rust
131//! use prolly::{Config, MemStore, Prolly};
132//! use std::sync::Arc;
133//!
134//! let store = Arc::new(MemStore::new());
135//! let prolly = Prolly::new(store.clone(), Config::default());
136//! let tree = prolly.create();
137//! let tree = prolly.put(&tree, b"name".to_vec(), b"Trail".to_vec()).unwrap();
138//!
139//! let update = prolly
140//!     .compare_and_swap_named_root(b"main", None, Some(&tree))
141//!     .unwrap();
142//! assert!(update.is_applied());
143//!
144//! let loaded = prolly.load_named_root(b"main").unwrap().unwrap();
145//! assert_eq!(prolly.get(&loaded, b"name").unwrap(), Some(b"Trail".to_vec()));
146//! ```
147//!
148//! ## Custom Storage Backend
149//!
150//! Implement the [`Store`] trait for custom storage:
151//!
152//! ```rust
153//! use prolly::{Store, BatchOp};
154//!
155//! struct MyStore {
156//!     // Your storage implementation
157//! }
158//!
159//! impl Store for MyStore {
160//!     type Error = std::io::Error;
161//!
162//!     fn get(&self, key: &[u8]) -> Result<Option<Vec<u8>>, Self::Error> {
163//!         // Implement get
164//!         Ok(None)
165//!     }
166//!
167//!     fn put(&self, key: &[u8], value: &[u8]) -> Result<(), Self::Error> {
168//!         // Implement put
169//!         Ok(())
170//!     }
171//!
172//!     fn delete(&self, key: &[u8]) -> Result<(), Self::Error> {
173//!         // Implement delete
174//!         Ok(())
175//!     }
176//!
177//!     fn batch(&self, ops: &[BatchOp]) -> Result<(), Self::Error> {
178//!         // Implement batch operations
179//!         Ok(())
180//!     }
181//! }
182//! ```
183//!
184//! ## Configuration
185//!
186//! Customize tree behavior with [`Config`]:
187//!
188//! ```rust
189//! use prolly::{Config, Encoding};
190//!
191//! let config = Config::builder()
192//!     .min_chunk_size(4)        // Min entries before considering split
193//!     .max_chunk_size(1024)     // Max entries per node
194//!     .chunking_factor(128)     // Controls average node size
195//!     .hash_seed(42)            // Seed for boundary detection
196//!     .encoding(Encoding::Raw)  // Value encoding type
197//!     .node_cache_max_nodes(50_000) // Optional decoded-node cache cap
198//!     .node_cache_max_bytes(256 * 1024 * 1024) // Optional serialized-byte cap
199//!     .build();
200//! ```
201//!
202//! ## Advanced Extensibility
203//!
204//! The library provides extensible traits for advanced use cases:
205//!
206//! ### Streaming Diff
207//!
208//! Use [`StreamingDiffer`] for memory-efficient diff operations on large trees:
209//!
210//! ```rust
211//! use prolly::{Prolly, MemStore, Config, Diff};
212//! use std::sync::Arc;
213//!
214//! let store = Arc::new(MemStore::new());
215//! let prolly = Prolly::new(store.clone(), Config::default());
216//!
217//! let base = prolly.create();
218//! let other = prolly.put(&base, b"key".to_vec(), b"val".to_vec()).unwrap();
219//!
220//! // Stream differences lazily (memory-efficient for large trees)
221//! for diff_result in prolly.stream_diff(&base, &other).unwrap() {
222//!     match diff_result {
223//!         Ok(diff) => println!("{:?}", diff),
224//!         Err(e) => eprintln!("Error: {}", e),
225//!     }
226//! }
227//! ```
228//!
229//! ### CRDT Merge
230//!
231//! Use [`ConflictFreeMerger`] for automatic conflict resolution:
232//!
233//! ```rust
234//! use prolly::{CrdtConfig, CrdtResolution, MergeStrategy, DeletePolicy, TimestampedValue};
235//!
236//! // Last-Writer-Wins strategy
237//! let lww_config = CrdtConfig::lww();
238//!
239//! // Multi-Value strategy (preserves all concurrent values)
240//! let mv_config = CrdtConfig::multi_value();
241//!
242//! // Custom merge function
243//! let custom_config = CrdtConfig::custom(|conflict| {
244//!     match &conflict.left {
245//!         Some(value) => CrdtResolution::value(value.clone()),
246//!         None => CrdtResolution::delete(),
247//!     }
248//! });
249//! ```
250//!
251//! ### Parallel Processing
252//!
253//! Use [`ParallelRebalancer`] for multi-threaded batch operations:
254//!
255//! ```rust
256//! use prolly::{ParallelConfig, DefaultParallelRebalancer};
257//!
258//! // Configure parallel processing
259//! let config = ParallelConfig {
260//!     max_threads: 4,           // Use 4 threads (0 = auto)
261//!     parallelism_threshold: 50, // Parallelize when > 50 items
262//! };
263//!
264//! let rebalancer = DefaultParallelRebalancer::new();
265//! ```
266
267mod prolly;
268
269// Re-export public API from prolly module
270pub use prolly::batch::{
271    append_batch, BatchApplyResult, BatchApplyStats, BatchWriter, BatchWriterConfig, MutationBuffer,
272};
273#[cfg(feature = "async-store")]
274pub use prolly::blob::{AsyncBlobStore, SyncBlobStoreAsAsync};
275pub use prolly::blob::{
276    BlobRef, BlobStore, BlobStoreScan, FileBlobStore, FileBlobStoreError, LargeValueConfig,
277    MemBlobStore, MemBlobStoreError, ValueRef, DEFAULT_INLINE_VALUE_THRESHOLD,
278};
279#[cfg(feature = "tokio")]
280pub use prolly::blob::{TokioBlockingBlobStore, TokioBlockingBlobStoreError};
281pub use prolly::boundary::{is_boundary, is_boundary_config};
282pub use prolly::builder::{BatchBuilder, SortedBatchBuilder};
283pub use prolly::canonical_splice::{canonical_splice, CanonicalSpliceStats};
284pub use prolly::cid::Cid;
285pub use prolly::config::{Config, ConfigBuilder};
286pub use prolly::content_graph::{
287    compare_and_swap_named_content_root, compare_and_swap_named_content_root_with_limits,
288    content_references, copy_and_publish_content_graph, copy_content_graph,
289    load_named_content_root, load_named_content_root_with_limits, plan_content_gc,
290    put_named_content_root, put_named_content_root_with_limits, sweep_content_gc,
291    sweep_content_gc_with_invalidator, walk_content_graph, ContentGcPlan, ContentGcSweep,
292    ContentGraphCopy, ContentGraphLimits, ContentGraphWalk, ContentManifestUpdate,
293    ContentObjectKind, ContentRootManifest, ContentRootPublication, TypedContentObject,
294    TypedContentRoot,
295};
296pub use prolly::crdt::{
297    ConflictFreeMerger, CrdtConfig, CrdtResolution, CustomMergeFn, DefaultConflictFreeMerger,
298    DeletePolicy, MergeStrategy, MultiValueSet, TimestampExtractor, TimestampedValue,
299};
300pub use prolly::cursor::{Cursor, CursorIterator, DiffCursor};
301pub use prolly::debug::{
302    TreeDebugComparedNode, TreeDebugComparison, TreeDebugComparisonLevel, TreeDebugLevel,
303    TreeDebugNode, TreeDebugNodeStatus, TreeDebugView,
304};
305#[cfg(feature = "async-store")]
306pub use prolly::diff::{AsyncConflictIter, AsyncDiffIter};
307pub use prolly::diff::{
308    DiffPage, DiffTraversalStats, MergeExplanation, MergeFallbackReason, MergeFastPath,
309    MergeResolutionKind, MergeReuseReason, MergeTrace, MergeTraceEvent, MergeTraceStage,
310    StructuralDiffCursor, StructuralDiffMarker, StructuralDiffPage,
311};
312pub use prolly::encoding::Encoding;
313pub use prolly::error::{resolver, Conflict, Diff, Error, Mutation, Resolution, Resolver};
314pub use prolly::gc::{
315    BlobGcPlan, BlobGcReachability, BlobGcSweep, GcPlan, GcReachability, GcSweep,
316};
317pub use prolly::key::{
318    debug_key, decode_segments, encode_segment, encode_segment_prefix, i128_key, i64_key,
319    prefix_end, prefix_range, timestamp_millis_key, u128_key, u64_key, KeyBuilder, KeyDecodeError,
320};
321#[cfg(feature = "async-store")]
322pub use prolly::manifest::{AsyncManifestStore, AsyncManifestStoreScan};
323pub use prolly::manifest::{
324    ManifestStore, ManifestStoreScan, ManifestUpdate, NamedRoot, NamedRootManifest,
325    NamedRootRetention, NamedRootSelection, NamedRootUpdate, RootManifest,
326};
327pub use prolly::node::{Node, NodeBuilder};
328pub use prolly::parallel::{DefaultParallelRebalancer, ParallelConfig, ParallelRebalancer};
329pub use prolly::policy::{
330    MergePolicyFn, MergePolicyRegistry, MergePolicyRule, MergePolicyRuleLabel,
331};
332pub use prolly::proof::{
333    inspect_proof_bundle, sign_proof_bundle_hmac_sha256, verify_authenticated_proof_bundle,
334    verify_authenticated_proof_envelope, verify_diff_page_proof, verify_key_proof,
335    verify_multi_key_proof, verify_proof_bundle, verify_range_page_proof, verify_range_proof,
336    AuthenticatedProofBundleVerification, AuthenticatedProofEnvelope,
337    AuthenticatedProofEnvelopeVerification, DiffPageProof, DiffPageProofVerification, KeyProof,
338    KeyProofVerification, MultiKeyProof, MultiKeyProofVerification, ProofBundleKind,
339    ProofBundleSummary, ProofBundleVerification, ProvedDiffPage, ProvedRangePage, RangePageProof,
340    RangePageProofVerification, RangeProof, RangeProofVerification,
341};
342pub use prolly::proximity::{
343    AdaptiveQuality, BuildParallelism, DistanceMetric, ExactProximityRecord, HierarchyConfig,
344    HnswBuildStats, HnswConfig, HnswIndex, Neighbor, OverflowConfig, ProductQuantizationBuildStats,
345    ProductQuantizationConfig, ProductQuantizationQuality, ProductQuantizer, ProximityBuildStats,
346    ProximityConfig, ProximityFilter, ProximityMap, ProximityMembershipProof,
347    ProximityMembershipVerification, ProximityMutation, ProximityMutationStats,
348    ProximityProofFilter, ProximityRecord, ProximitySearchClaim, ProximitySearchEvent,
349    ProximitySearchProof, ProximitySearchRequest, ProximitySearchStats,
350    ProximitySearchVerification, ProximityStructuralProof, ProximityStructuralVerification,
351    ProximityTree, ProximityVerification, QueryKernel, ScalarQuantizationConfig, SearchBackend,
352    SearchBudget, SearchCompletion, SearchPolicy, SearchRequest, SearchResult, VectorStorageConfig,
353};
354#[cfg(feature = "async-store")]
355pub use prolly::proximity::{
356    AsyncIoConfig, AsyncProximityMap, AsyncSearchControl, CancellationToken,
357};
358pub use prolly::range::{
359    CursorWindow, RangeCursor, RangeIter, RangePage, ReverseCursor, ReversePage,
360};
361pub use prolly::secondary_index::{
362    catalog_checkpoint_key, catalog_checkpoints_prefix, catalog_current_key,
363    catalog_descriptor_key, catalog_format_key, catalog_map_id, catalog_retired_key,
364    control_record_key, control_root_name, decode_physical_index_key, descriptor_fingerprint,
365    index_map_id, physical_index_key, term_bounds_exact, term_bounds_prefix, term_bounds_range,
366    ActiveIndexControl, ActiveIndexHealth, DecodedPhysicalIndexKey, IndexBuildResult,
367    IndexCheckpoint, IndexControl, IndexProjection, IndexValue, IndexVerification,
368    IndexedHeadRecord, IndexedMap, IndexedMapEditor, IndexedMapHealth, IndexedMapMetricsSnapshot,
369    IndexedMapUpdate, IndexedRetentionResult, IndexedSnapshot, IndexedSnapshotBundle,
370    IndexedSnapshotBundleIndex, IndexedSnapshotBundleSummary, IndexedSnapshotBundleVerification,
371    IndexedSnapshotId, IndexedSourceRecord, IndexedVersion, ProjectedIndexEntry, SecondaryIndex,
372    SecondaryIndexBuilder, SecondaryIndexCursor, SecondaryIndexDescriptor, SecondaryIndexDirection,
373    SecondaryIndexEntry, SecondaryIndexError, SecondaryIndexExtractor, SecondaryIndexLimits,
374    SecondaryIndexMatch, SecondaryIndexPage, SecondaryIndexRegistry, SecondaryIndexSnapshot,
375    TermBounds, INDEXED_SNAPSHOT_BUNDLE_FORMAT_VERSION, INDEX_PHYSICAL_LAYOUT_VERSION,
376    SECONDARY_INDEX_FORMAT_VERSION,
377};
378pub use prolly::snapshot::{
379    snapshot_id_from_name, snapshot_root_name, SnapshotManager, SnapshotNamespace, SnapshotRoot,
380    SnapshotSelection, SNAPSHOT_BRANCH_PREFIX, SNAPSHOT_CHECKPOINT_PREFIX, SNAPSHOT_TAG_PREFIX,
381};
382pub use prolly::streaming::{DefaultStreamingDiffer, StreamingDiffer};
383pub use prolly::{ChangedSpan, ChangedSpanHint, KeyValue, Prolly, ProllyMetricsSnapshot};
384
385#[cfg(feature = "async-store")]
386pub use prolly::range::{AsyncRangeIter, AsyncRangePage, AsyncReversePage};
387#[cfg(feature = "async-store")]
388pub use prolly::remote::{
389    conformance as remote_conformance, RemoteAdapterError, RemoteBatchOp, RemoteManifestUpdate,
390    RemoteNamedRoot, RemoteProllyStore, RemoteRootCondition, RemoteRootWrite, RemoteStoreBackend,
391    RemoteStoreConfig, RemoteTransactionConflict, RemoteTransactionUpdate,
392};
393pub use prolly::stats::{StatsComparison, StatsDiff, StatsPercentageChange, TreeStats};
394#[cfg(feature = "async-store")]
395pub use prolly::store::{AsyncStore, SyncStoreAsAsync};
396pub use prolly::store::{
397    BatchOp, FileNodeStore, FileNodeStoreError, MemStore, MemStoreError, NodeStoreScan, Store,
398};
399#[cfg(feature = "tokio")]
400pub use prolly::store::{TokioBlockingStore, TokioBlockingStoreError};
401pub use prolly::sync::{
402    MissingNodeCopy, MissingNodePlan, SnapshotBundle, SnapshotBundleNode, SnapshotBundleSummary,
403    SnapshotBundleVerification, SNAPSHOT_BUNDLE_FORMAT_VERSION,
404};
405pub use prolly::tombstone::{
406    is_tombstone_value, tombstone_compaction, tombstone_upsert, Tombstone,
407};
408#[cfg(feature = "async-store")]
409pub use prolly::transaction::{
410    AsyncProllyTransaction, AsyncTransactionOverlayStore, AsyncTransactionalStore,
411};
412pub use prolly::transaction::{
413    OwnedProllyTransaction, OwnedTransactionOverlayStore, ProllyTransaction, RootCondition,
414    RootWrite, TransactionConflict, TransactionNodeWrite, TransactionOverlayError,
415    TransactionUpdate, TransactionalStore,
416};
417pub use prolly::tree::Tree;
418pub use prolly::value::{
419    decode_cbor, decode_json, encode_cbor, encode_json, CborCodec, JsonCodec, ValueCodec,
420    VersionedCborCodec, VersionedJsonCodec, VersionedValue,
421};
422#[cfg(feature = "async-store")]
423pub use prolly::versioned_map::{AsyncMapChangeSubscription, AsyncMapSnapshot, AsyncVersionedMap};
424pub use prolly::versioned_map::{
425    BytesKeyCodec, KeyCodec, MapBackupVersion, MapCatalogVerification, MapChangeEvent,
426    MapChangeSubscription, MapComparison, MapMerge, MapReverseIter, MapSnapshot, MapVersion,
427    MapVersionId, ProofAuthentication, StringKeyCodec, TypedMigrationResult, TypedVersionedMap,
428    VersionPruneResult, VersionedMap, VersionedMapBackup, VersionedMapBatchResult,
429    VersionedMapEditor, VersionedMapUpdate, VersionedMapsTransaction,
430    DEFAULT_VERSIONED_MAP_RETRIES, VERSIONED_MAP_ROOT_PREFIX,
431};
432#[cfg(feature = "async-store")]
433pub use prolly::AsyncProlly;
434
435// Re-export constants
436pub use prolly::encoding::{
437    DEFAULT_CHUNKING_FACTOR, DEFAULT_HASH_SEED, DEFAULT_MAX_CHUNK_SIZE, DEFAULT_MIN_CHUNK_SIZE,
438    INIT_LEVEL,
439};
prolly/lib.rs

prolly/
lib.rs
