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, BoundaryDetector};
282pub use prolly::builder::{BatchBuilder, SortedBatchBuilder};
283pub use prolly::canonical::CanonicalWriteStats;
284pub use prolly::canonical_splice::{canonical_splice, CanonicalSpliceStats};
285pub use prolly::chunking;
286pub use prolly::cid::Cid;
287pub use prolly::config::{Config, ConfigBuilder, RuntimeConfig};
288pub use prolly::content_graph::{
289    compare_and_swap_named_content_root, compare_and_swap_named_content_root_with_limits,
290    content_references, copy_and_publish_content_graph, copy_content_graph,
291    load_named_content_root, load_named_content_root_with_limits, plan_content_gc,
292    put_named_content_root, put_named_content_root_with_limits, sweep_content_gc,
293    sweep_content_gc_with_invalidator, walk_content_graph, ContentGcPlan, ContentGcSweep,
294    ContentGraphCopy, ContentGraphLimits, ContentGraphWalk, ContentManifestUpdate,
295    ContentObjectKind, ContentRootManifest, ContentRootPublication, TypedContentObject,
296    TypedContentRoot,
297};
298pub use prolly::crdt::{
299    ConflictFreeMerger, CrdtConfig, CrdtResolution, CustomMergeFn, DefaultConflictFreeMerger,
300    DeletePolicy, MergeStrategy, MultiValueSet, TimestampExtractor, TimestampedValue,
301};
302pub use prolly::cursor::{Cursor, CursorIterator, DiffCursor};
303pub use prolly::debug::{
304    TreeDebugComparedNode, TreeDebugComparison, TreeDebugComparisonLevel, TreeDebugLevel,
305    TreeDebugNode, TreeDebugNodeStatus, TreeDebugView,
306};
307#[cfg(feature = "async-store")]
308pub use prolly::diff::{AsyncConflictIter, AsyncDiffIter};
309pub use prolly::diff::{
310    DiffPage, DiffTraversalStats, MergeExplanation, MergeFallbackReason, MergeFastPath,
311    MergeResolutionKind, MergeReuseReason, MergeTrace, MergeTraceEvent, MergeTraceStage,
312    StructuralDiffCursor, StructuralDiffMarker, StructuralDiffPage,
313};
314pub use prolly::encoding::Encoding;
315pub use prolly::error::{resolver, Conflict, Diff, Error, Mutation, Resolution, Resolver};
316pub use prolly::format::{
317    BoundaryInput, BoundaryRule, ChunkMeasure, ChunkingSpec, HashAlgorithm, NodeLayoutSpec,
318    TreeFormat,
319};
320pub use prolly::gc::{
321    BlobGcPlan, BlobGcReachability, BlobGcSweep, GcPlan, GcReachability, GcSweep,
322};
323pub use prolly::key::{
324    debug_key, decode_segments, encode_segment, encode_segment_prefix, i128_key, i64_key,
325    prefix_end, prefix_range, timestamp_millis_key, u128_key, u64_key, KeyBuilder, KeyDecodeError,
326};
327#[cfg(feature = "async-store")]
328pub use prolly::manifest::{AsyncManifestStore, AsyncManifestStoreScan};
329pub use prolly::manifest::{
330    ManifestStore, ManifestStoreScan, ManifestUpdate, NamedRoot, NamedRootManifest,
331    NamedRootRetention, NamedRootSelection, NamedRootUpdate, RootManifest,
332};
333pub use prolly::node::{Node, NodeBuilder};
334pub use prolly::parallel::{DefaultParallelRebalancer, ParallelConfig, ParallelRebalancer};
335pub use prolly::patch::{LogicalPatch, StructuralEdit, StructuralPatch};
336pub use prolly::policy::{
337    MergePolicyFn, MergePolicyRegistry, MergePolicyRule, MergePolicyRuleLabel,
338};
339pub use prolly::proof::{
340    inspect_proof_bundle, sign_proof_bundle_hmac_sha256, verify_authenticated_proof_bundle,
341    verify_authenticated_proof_envelope, verify_diff_page_proof, verify_key_proof,
342    verify_multi_key_proof, verify_proof_bundle, verify_range_page_proof, verify_range_proof,
343    AuthenticatedProofBundleVerification, AuthenticatedProofEnvelope,
344    AuthenticatedProofEnvelopeVerification, DiffPageProof, DiffPageProofVerification, KeyProof,
345    KeyProofVerification, MultiKeyProof, MultiKeyProofVerification, ProofBundleKind,
346    ProofBundleSummary, ProofBundleVerification, ProvedDiffPage, ProvedRangePage, RangePageProof,
347    RangePageProofVerification, RangeProof, RangeProofVerification,
348};
349pub use prolly::proximity::{
350    AdaptiveQuality, BuildParallelism, DistanceMetric, ExactProximityRecord, HierarchyConfig,
351    HnswBuildStats, HnswConfig, HnswIndex, Neighbor, OverflowConfig, ProductQuantizationBuildStats,
352    ProductQuantizationConfig, ProductQuantizationQuality, ProductQuantizer, ProximityBuildStats,
353    ProximityConfig, ProximityFilter, ProximityMap, ProximityMembershipProof,
354    ProximityMembershipVerification, ProximityMutation, ProximityMutationStats,
355    ProximityProofFilter, ProximityRecord, ProximitySearchClaim, ProximitySearchEvent,
356    ProximitySearchProof, ProximitySearchRequest, ProximitySearchStats,
357    ProximitySearchVerification, ProximityStructuralProof, ProximityStructuralVerification,
358    ProximityTree, ProximityVerification, QueryKernel, ScalarQuantizationConfig, SearchBackend,
359    SearchBudget, SearchCompletion, SearchPolicy, SearchRequest, SearchResult, VectorStorageConfig,
360};
361#[cfg(feature = "async-store")]
362pub use prolly::proximity::{
363    AsyncIoConfig, AsyncProximityMap, AsyncSearchControl, CancellationToken,
364};
365pub use prolly::range::{
366    CursorWindow, RangeCursor, RangeIter, RangePage, ReverseCursor, ReversePage,
367};
368pub use prolly::secondary_index::{
369    catalog_checkpoint_key, catalog_checkpoints_prefix, catalog_current_key,
370    catalog_descriptor_key, catalog_format_key, catalog_map_id, catalog_retired_key,
371    control_record_key, control_root_name, decode_physical_index_key, descriptor_fingerprint,
372    index_map_id, physical_index_key, term_bounds_exact, term_bounds_prefix, term_bounds_range,
373    ActiveIndexControl, ActiveIndexHealth, DecodedPhysicalIndexKey, IndexBuildResult,
374    IndexCheckpoint, IndexControl, IndexProjection, IndexValue, IndexVerification,
375    IndexedHeadRecord, IndexedMap, IndexedMapEditor, IndexedMapHealth, IndexedMapMetricsSnapshot,
376    IndexedMapUpdate, IndexedRetentionResult, IndexedSnapshot, IndexedSnapshotBundle,
377    IndexedSnapshotBundleIndex, IndexedSnapshotBundleSummary, IndexedSnapshotBundleVerification,
378    IndexedSnapshotId, IndexedSourceRecord, IndexedVersion, ProjectedIndexEntry, SecondaryIndex,
379    SecondaryIndexBuilder, SecondaryIndexCursor, SecondaryIndexDescriptor, SecondaryIndexDirection,
380    SecondaryIndexEntry, SecondaryIndexError, SecondaryIndexExtractor, SecondaryIndexLimits,
381    SecondaryIndexMatch, SecondaryIndexPage, SecondaryIndexRegistry, SecondaryIndexSnapshot,
382    TermBounds, INDEXED_SNAPSHOT_BUNDLE_FORMAT_VERSION, INDEX_PHYSICAL_LAYOUT_VERSION,
383    SECONDARY_INDEX_FORMAT_VERSION,
384};
385pub use prolly::snapshot::{
386    snapshot_id_from_name, snapshot_root_name, SnapshotManager, SnapshotNamespace, SnapshotRoot,
387    SnapshotSelection, SNAPSHOT_BRANCH_PREFIX, SNAPSHOT_CHECKPOINT_PREFIX, SNAPSHOT_TAG_PREFIX,
388};
389pub use prolly::streaming::{DefaultStreamingDiffer, StreamingDiffer};
390pub use prolly::{ChangedSpan, ChangedSpanHint, KeyValue, Prolly, ProllyMetricsSnapshot};
391
392#[cfg(feature = "async-store")]
393pub use prolly::range::{AsyncRangeIter, AsyncRangePage, AsyncReversePage};
394#[cfg(feature = "async-store")]
395pub use prolly::remote::{
396    conformance as remote_conformance, RemoteAdapterError, RemoteBatchOp, RemoteManifestUpdate,
397    RemoteNamedRoot, RemoteProllyStore, RemoteRootCondition, RemoteRootWrite, RemoteStoreBackend,
398    RemoteStoreConfig, RemoteTransactionConflict, RemoteTransactionUpdate,
399};
400pub use prolly::stats::{StatsComparison, StatsDiff, StatsPercentageChange, TreeStats};
401#[cfg(feature = "async-store")]
402pub use prolly::store::{AsyncStore, SyncStoreAsAsync};
403pub use prolly::store::{
404    BatchOp, FileNodeStore, FileNodeStoreError, MemStore, MemStoreError, NodeStoreScan, Store,
405};
406#[cfg(feature = "tokio")]
407pub use prolly::store::{TokioBlockingStore, TokioBlockingStoreError};
408pub use prolly::sync::{
409    MissingNodeCopy, MissingNodePlan, SnapshotBundle, SnapshotBundleNode, SnapshotBundleSummary,
410    SnapshotBundleVerification, SNAPSHOT_BUNDLE_FORMAT_VERSION,
411};
412pub use prolly::tombstone::{
413    is_tombstone_value, tombstone_compaction, tombstone_upsert, Tombstone,
414};
415#[cfg(feature = "async-store")]
416pub use prolly::transaction::{
417    AsyncProllyTransaction, AsyncTransactionOverlayStore, AsyncTransactionalStore,
418};
419pub use prolly::transaction::{
420    OwnedProllyTransaction, OwnedTransactionOverlayStore, ProllyTransaction, RootCondition,
421    RootWrite, TransactionConflict, TransactionNodeWrite, TransactionOverlayError,
422    TransactionUpdate, TransactionalStore,
423};
424pub use prolly::tree::Tree;
425pub use prolly::value::{
426    decode_cbor, decode_json, encode_cbor, encode_json, CborCodec, JsonCodec, ValueCodec,
427    VersionedCborCodec, VersionedJsonCodec, VersionedValue,
428};
429#[cfg(feature = "async-store")]
430pub use prolly::versioned_map::{AsyncMapChangeSubscription, AsyncMapSnapshot, AsyncVersionedMap};
431pub use prolly::versioned_map::{
432    BytesKeyCodec, KeyCodec, MapBackupVersion, MapCatalogVerification, MapChangeEvent,
433    MapChangeSubscription, MapComparison, MapMerge, MapReverseIter, MapSnapshot, MapVersion,
434    MapVersionId, ProofAuthentication, StringKeyCodec, TypedMigrationResult, TypedVersionedMap,
435    VersionPruneResult, VersionedMap, VersionedMapBackup, VersionedMapBatchResult,
436    VersionedMapEditor, VersionedMapUpdate, VersionedMapsTransaction,
437    DEFAULT_VERSIONED_MAP_RETRIES, VERSIONED_MAP_ROOT_PREFIX,
438};
439pub use prolly::write_session::{PendingValue, Savepoint, WriteSession};
440#[cfg(feature = "async-store")]
441pub use prolly::AsyncProlly;
442
443// Re-export constants
444pub use prolly::encoding::{
445    DEFAULT_CHUNKING_FACTOR, DEFAULT_HASH_SEED, DEFAULT_MAX_CHUNK_SIZE, DEFAULT_MIN_CHUNK_SIZE,
446    INIT_LEVEL,
447};
prolly/lib.rs

prolly/
lib.rs
