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//! ### Streaming Diff
205//!
206//! Use [`Prolly::stream_diff`] for memory-efficient diff operations on large trees:
207//!
208//! ```rust
209//! use prolly::{Prolly, MemStore, Config, Diff};
210//! use std::sync::Arc;
211//!
212//! let store = Arc::new(MemStore::new());
213//! let prolly = Prolly::new(store.clone(), Config::default());
214//!
215//! let base = prolly.create();
216//! let other = prolly.put(&base, b"key".to_vec(), b"val".to_vec()).unwrap();
217//!
218//! // Stream differences lazily (memory-efficient for large trees)
219//! for diff_result in prolly.stream_diff(&base, &other).unwrap() {
220//!     match diff_result {
221//!         Ok(diff) => println!("{:?}", diff),
222//!         Err(e) => eprintln!("Error: {}", e),
223//!     }
224//! }
225//! ```
226//!
227//! ### CRDT Merge
228//!
229//! Use [`ConflictFreeMerger`] for automatic conflict resolution:
230//!
231//! ```rust
232//! use prolly::{CrdtConfig, CrdtResolution, MergeStrategy, DeletePolicy, TimestampedValue};
233//!
234//! // Last-Writer-Wins strategy
235//! let lww_config = CrdtConfig::lww();
236//!
237//! // Multi-Value strategy (preserves all concurrent values)
238//! let mv_config = CrdtConfig::multi_value();
239//!
240//! // Custom merge function
241//! let custom_config = CrdtConfig::custom(|conflict| {
242//!     match &conflict.left {
243//!         Some(value) => CrdtResolution::value(value.clone()),
244//!         None => CrdtResolution::delete(),
245//!     }
246//! });
247//! ```
248//!
249
250mod prolly;
251
252// Re-export public API from prolly module
253pub use prolly::batch::{
254    append_batch, BatchApplyResult, BatchApplyStats, BatchWriter, MutationBuffer,
255};
256pub use prolly::blob::{AsyncBlobStore, SyncBlobStoreAsAsync};
257pub use prolly::blob::{
258    BlobRef, BlobStore, BlobStoreScan, FileBlobStore, FileBlobStoreError, LargeValueConfig,
259    MemBlobStore, MemBlobStoreError, ValueRef, DEFAULT_INLINE_VALUE_THRESHOLD,
260};
261#[cfg(feature = "tokio")]
262pub use prolly::blob::{TokioBlockingBlobStore, TokioBlockingBlobStoreError};
263pub use prolly::boundary::BoundaryDetector;
264pub use prolly::builder::{
265    AsyncBatchBuilder, AsyncSortedBatchBuilder, BatchBuilder, SortedBatchBuilder,
266};
267pub use prolly::chunking;
268pub use prolly::cid::Cid;
269pub use prolly::config::{Config, ConfigBuilder, RuntimeConfig};
270pub use prolly::content_graph::{
271    compare_and_swap_named_content_root, compare_and_swap_named_content_root_with_limits,
272    content_references, copy_and_publish_content_graph, copy_content_graph,
273    load_named_content_root, load_named_content_root_with_limits, plan_content_gc,
274    put_named_content_root, put_named_content_root_with_limits, sweep_content_gc,
275    sweep_content_gc_with_invalidator, walk_content_graph, ContentGcPlan, ContentGcSweep,
276    ContentGraphCopy, ContentGraphLimits, ContentGraphWalk, ContentManifestUpdate,
277    ContentObjectKind, ContentRootManifest, ContentRootPublication, TypedContentObject,
278    TypedContentRoot,
279};
280pub use prolly::crdt::{
281    ConflictFreeMerger, CrdtConfig, CrdtResolution, CustomMergeFn, DefaultConflictFreeMerger,
282    DeletePolicy, MergeStrategy, MultiValueSet, TimestampExtractor, TimestampedValue,
283};
284pub use prolly::debug::{
285    TreeDebugComparedNode, TreeDebugComparison, TreeDebugComparisonLevel, TreeDebugLevel,
286    TreeDebugNode, TreeDebugNodeStatus, TreeDebugView,
287};
288pub use prolly::diff::{AsyncConflictIter, AsyncDiffIter};
289pub use prolly::diff::{
290    DiffPage, DiffTraversalStats, MergeExplanation, MergeFallbackReason, MergeFastPath,
291    MergeResolutionKind, MergeReuseReason, MergeTrace, MergeTraceEvent, MergeTraceStage,
292    StructuralDiffCursor, StructuralDiffMarker, StructuralDiffPage,
293};
294pub use prolly::encoding::Encoding;
295pub use prolly::engine::execution::ExecutionConfig;
296pub use prolly::engine::ProllyEngine;
297pub use prolly::error::{
298    resolver, Conflict, Diff, Error, IndexErrorCode, Mutation, Resolution, Resolver, RetryAdvice,
299};
300pub use prolly::format::{
301    BoundaryInput, BoundaryRule, ChunkMeasure, ChunkingSpec, HashAlgorithm, NodeLayoutSpec,
302    TreeFormat,
303};
304pub use prolly::gc::{
305    BlobGcPlan, BlobGcReachability, BlobGcSweep, GcPlan, GcReachability, GcSweep,
306};
307pub use prolly::key::{
308    debug_key, decode_segments, encode_segment, encode_segment_prefix, i128_key, i64_key,
309    prefix_end, prefix_range, timestamp_millis_key, u128_key, u64_key, KeyBuilder, KeyDecodeError,
310};
311pub use prolly::manifest::{AsyncManifestStore, AsyncManifestStoreScan};
312pub use prolly::manifest::{
313    ManifestStore, ManifestStoreScan, ManifestUpdate, NamedRoot, NamedRootManifest,
314    NamedRootRetention, NamedRootSelection, NamedRootUpdate, RootManifest,
315};
316pub use prolly::node::{Node, NodeBuilder};
317pub use prolly::parallel::ParallelConfig;
318pub use prolly::patch::{LogicalPatch, StructuralEdit, StructuralPatch};
319pub use prolly::policy::{
320    MergePolicyFn, MergePolicyRegistry, MergePolicyRule, MergePolicyRuleLabel,
321};
322pub use prolly::proof::{
323    inspect_proof_bundle, sign_proof_bundle_hmac_sha256, verify_authenticated_proof_bundle,
324    verify_authenticated_proof_envelope, verify_diff_page_proof, verify_key_proof,
325    verify_multi_key_proof, verify_proof_bundle, verify_range_page_proof, verify_range_proof,
326    AuthenticatedProofBundleVerification, AuthenticatedProofEnvelope,
327    AuthenticatedProofEnvelopeVerification, DiffPageProof, DiffPageProofVerification, KeyProof,
328    KeyProofVerification, MultiKeyProof, MultiKeyProofVerification, ProofBundleKind,
329    ProofBundleSummary, ProofBundleVerification, ProvedDiffPage, ProvedRangePage, RangePageProof,
330    RangePageProofVerification, RangeProof, RangeProofVerification,
331};
332pub use prolly::proximity::{
333    AcceleratorCatalog, AcceleratorCatalogEntry, AcceleratorSet, AdaptiveQuality,
334    ApproximatePreference, BuildParallelism, CatalogAcceleratorKind, CompositeAccelerator,
335    CompositeAcceleratorConfig, CompositeBase, CompositeBaseKind, CompositeBuildLimits,
336    CompositeBuildOrRebuildOutcome, CompositeBuildOutcome, CompositeBuildStats,
337    CompositeRebuildOptions, DistanceMetric, ExactProximityRecord, FullRebuildReason,
338    HierarchyConfig, HnswBuildLimits, HnswBuildStats, HnswConfig, HnswIndex,
339    HnswRoutingVectorEncoding, HnswSearchOptions, Neighbor, OverflowConfig, PlannerPolicy,
340    PqSearchOptions, ProductQuantizationBuildLimits, ProductQuantizationBuildStats,
341    ProductQuantizationConfig, ProductQuantizationQuality, ProductQuantizer, ProximityBuildStats,
342    ProximityConfig, ProximityFilter, ProximityMap, ProximityMembershipProof,
343    ProximityMembershipVerification, ProximityMutation, ProximityMutationStats,
344    ProximityProofFilter, ProximityReadSession, ProximityRecord, ProximityRecordRef,
345    ProximitySearchClaim, ProximitySearchEvent, ProximitySearchProof, ProximitySearchRequest,
346    ProximitySearchStats, ProximitySearchVerification, ProximityStructuralProof,
347    ProximityStructuralVerification, ProximityTree, ProximityVectorRef, ProximityVerification,
348    QueryKernel, ScalarQuantizationConfig, SearchBackend, SearchBudget, SearchCompletion, SearchIo,
349    SearchOptions, SearchPlan, SearchPlanSummary, SearchPolicy, SearchRequest, SearchResult,
350    SearchRuntime, SearchRuntimePolicy, StoreCacheNamespace, VectorStorageConfig,
351    SEARCH_PLAN_FORMAT_VERSION,
352};
353pub use prolly::proximity::{
354    AsyncAcceleratorCatalog, AsyncAcceleratorSet, AsyncCompositeAccelerator, AsyncHnswIndex,
355    AsyncIoConfig, AsyncProductQuantizer, AsyncProximityMap, AsyncSearchControl, CancellationToken,
356};
357pub use prolly::range::{AsyncRangeIter, AsyncRangePage, AsyncReversePage};
358pub use prolly::range::{
359    CursorWindow, RangeCursor, RangeIter, RangePage, ReverseCursor, ReversePage,
360};
361pub use prolly::read::AsyncReadSession;
362pub use prolly::read::{
363    BorrowedMergeResolver, ConflictRef, DiffRef, EntryRef, MergeDecision, OwnedRangeScanSession,
364    OwnedReadSession, OwnedValueLease, ReadSession, ScanOutcome, ValueRefView,
365};
366pub use prolly::remote::{
367    conformance as remote_conformance, RemoteAdapterError, RemoteBatchOp, RemoteManifestUpdate,
368    RemoteNamedRoot, RemoteProllyStore, RemoteRootCondition, RemoteRootWrite, RemoteStoreBackend,
369    RemoteStoreConfig, RemoteTransactionConflict, RemoteTransactionUpdate,
370};
371pub use prolly::secondary_index::{
372    decode_physical_index_key, decode_physical_index_key_ref, indexed_collection_root_name,
373    physical_index_key, term_bounds_exact, term_bounds_prefix, term_bounds_range,
374    ActiveIndexHealth, CollectionIndexPolicy, DecodedPhysicalIndexKey, DecodedPhysicalIndexKeyRef,
375    IndexBuildResult, IndexDescriptor, IndexProjection, IndexSemanticLimits, IndexSnapshotRef,
376    IndexValue, IndexValueRef, IndexVerification, IndexedCollectionState, IndexedCoordinationScope,
377    IndexedGcSafety, IndexedMap, IndexedMapEditor, IndexedMapHealth, IndexedMapMetricsSnapshot,
378    IndexedMapUpdate, IndexedRetentionResult, IndexedSnapshot, IndexedSnapshotBundle,
379    IndexedSnapshotBundleIndex, IndexedSnapshotBundleSummary, IndexedSnapshotBundleVerification,
380    IndexedSnapshotId, IndexedSnapshotRecord, IndexedSourceRecord, IndexedSourceRecordRef,
381    IndexedStore, IndexedStoreProfile, IndexedVersion, IndexedWriteVisibility, MaintenanceBudget,
382    MutationBudget, ProductionIndexedStoreCapabilities, ProjectedIndexEntry, QueryBudget,
383    SecondaryIndex, SecondaryIndexBuilder, SecondaryIndexCursor, SecondaryIndexDirection,
384    SecondaryIndexEntry, SecondaryIndexEntryRef, SecondaryIndexError, SecondaryIndexExtractor,
385    SecondaryIndexLimits, SecondaryIndexMatch, SecondaryIndexMatchRef, SecondaryIndexPage,
386    SecondaryIndexQuery, SecondaryIndexRegistry, SecondaryIndexSnapshot, SnapshotPin,
387    SnapshotPinGuard, SourceSnapshotRef, StreamingSecondaryIndexExtractor, TermBounds,
388    TransferBudget, INDEXED_COLLECTION_FORMAT, INDEXED_SNAPSHOT_BUNDLE_FORMAT_VERSION,
389    INDEX_PHYSICAL_LAYOUT_VERSION,
390};
391pub use prolly::snapshot::{
392    snapshot_id_from_name, snapshot_root_name, SnapshotManager, SnapshotNamespace, SnapshotRoot,
393    SnapshotSelection, SNAPSHOT_BRANCH_PREFIX, SNAPSHOT_CHECKPOINT_PREFIX, SNAPSHOT_TAG_PREFIX,
394};
395pub use prolly::splice::{splice, SpliceStats};
396pub use prolly::stats::{StatsComparison, StatsDiff, StatsPercentageChange, TreeStats};
397pub use prolly::store::{AsyncStore, SyncStoreAsAsync};
398pub use prolly::store::{
399    BatchOp, FileNodeStore, FileNodeStoreError, MemStore, MemStoreError, NodePublication,
400    NodePublicationHint, NodeStoreScan, PublicationOrigin, Store,
401};
402#[cfg(feature = "tokio")]
403pub use prolly::store::{TokioBlockingStore, TokioBlockingStoreError};
404pub use prolly::sync::{
405    MissingNodeCopy, MissingNodePlan, SnapshotBundle, SnapshotBundleNode, SnapshotBundleSummary,
406    SnapshotBundleVerification, SNAPSHOT_BUNDLE_FORMAT_VERSION,
407};
408pub use prolly::tombstone::{
409    is_tombstone_value, tombstone_compaction, tombstone_upsert, Tombstone,
410};
411pub use prolly::transaction::{
412    AsyncProllyTransaction, AsyncTransactionOverlayStore, AsyncTransactionalStore,
413    OwnedAsyncProllyTransaction, OwnedAsyncTransactionOverlayStore,
414};
415pub use prolly::transaction::{
416    OwnedProllyTransaction, ProllyTransaction, RootCondition, RootWrite, TransactionConflict,
417    TransactionNodeWrite, TransactionOverlayError, TransactionUpdate, TransactionalStore,
418};
419pub use prolly::tree::Tree;
420pub use prolly::value::{
421    decode_cbor, decode_json, encode_cbor, encode_json, CborCodec, JsonCodec, ValueCodec,
422    VersionedCborCodec, VersionedJsonCodec, VersionedValue,
423};
424pub use prolly::versioned_map::{AsyncMapChangeSubscription, AsyncMapSnapshot, AsyncVersionedMap};
425pub use prolly::versioned_map::{
426    BytesKeyCodec, KeyCodec, MapBackupVersion, MapCatalogVerification, MapChangeEvent,
427    MapChangeSubscription, MapComparison, MapMerge, MapReverseIter, MapSnapshot, MapVersion,
428    MapVersionId, ProofAuthentication, StringKeyCodec, TypedMigrationResult, TypedVersionedMap,
429    VersionPruneResult, VersionedMap, VersionedMapBackup, VersionedMapBatchResult,
430    VersionedMapEditor, VersionedMapUpdate, VersionedMapsTransaction,
431    DEFAULT_VERSIONED_MAP_RETRIES, VERSIONED_MAP_ROOT_PREFIX,
432};
433pub use prolly::write::WriteStats;
434pub use prolly::write_session::{PendingValue, Savepoint, WriteSession};
435pub use prolly::AsyncProlly;
436pub use prolly::{ChangedSpan, ChangedSpanHint, KeyValue, Prolly, ProllyMetricsSnapshot};
437
438// Re-export constants
439pub use prolly::encoding::{
440    DEFAULT_CHUNKING_FACTOR, DEFAULT_HASH_SEED, DEFAULT_MAX_CHUNK_SIZE, DEFAULT_MIN_CHUNK_SIZE,
441    INIT_LEVEL,
442};
prolly/lib.rs

prolly/
lib.rs
