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::{resolver, Conflict, Diff, Error, Mutation, Resolution, Resolver};
298pub use prolly::format::{
299    BoundaryInput, BoundaryRule, ChunkMeasure, ChunkingSpec, HashAlgorithm, NodeLayoutSpec,
300    TreeFormat,
301};
302pub use prolly::gc::{
303    BlobGcPlan, BlobGcReachability, BlobGcSweep, GcPlan, GcReachability, GcSweep,
304};
305pub use prolly::key::{
306    debug_key, decode_segments, encode_segment, encode_segment_prefix, i128_key, i64_key,
307    prefix_end, prefix_range, timestamp_millis_key, u128_key, u64_key, KeyBuilder, KeyDecodeError,
308};
309pub use prolly::manifest::{AsyncManifestStore, AsyncManifestStoreScan};
310pub use prolly::manifest::{
311    ManifestStore, ManifestStoreScan, ManifestUpdate, NamedRoot, NamedRootManifest,
312    NamedRootRetention, NamedRootSelection, NamedRootUpdate, RootManifest,
313};
314pub use prolly::node::{Node, NodeBuilder};
315pub use prolly::parallel::ParallelConfig;
316pub use prolly::patch::{LogicalPatch, StructuralEdit, StructuralPatch};
317pub use prolly::policy::{
318    MergePolicyFn, MergePolicyRegistry, MergePolicyRule, MergePolicyRuleLabel,
319};
320pub use prolly::proof::{
321    inspect_proof_bundle, sign_proof_bundle_hmac_sha256, verify_authenticated_proof_bundle,
322    verify_authenticated_proof_envelope, verify_diff_page_proof, verify_key_proof,
323    verify_multi_key_proof, verify_proof_bundle, verify_range_page_proof, verify_range_proof,
324    AuthenticatedProofBundleVerification, AuthenticatedProofEnvelope,
325    AuthenticatedProofEnvelopeVerification, DiffPageProof, DiffPageProofVerification, KeyProof,
326    KeyProofVerification, MultiKeyProof, MultiKeyProofVerification, ProofBundleKind,
327    ProofBundleSummary, ProofBundleVerification, ProvedDiffPage, ProvedRangePage, RangePageProof,
328    RangePageProofVerification, RangeProof, RangeProofVerification,
329};
330pub use prolly::proximity::{
331    AcceleratorCatalog, AcceleratorCatalogEntry, AcceleratorSet, AdaptiveQuality,
332    ApproximatePreference, BuildParallelism, CatalogAcceleratorKind, CompositeAccelerator,
333    CompositeAcceleratorConfig, CompositeBase, CompositeBaseKind, CompositeBuildLimits,
334    CompositeBuildOrRebuildOutcome, CompositeBuildOutcome, CompositeBuildStats,
335    CompositeRebuildOptions, DistanceMetric, ExactProximityRecord, FullRebuildReason,
336    HierarchyConfig, HnswBuildLimits, HnswBuildStats, HnswConfig, HnswIndex,
337    HnswRoutingVectorEncoding, HnswSearchOptions, Neighbor, OverflowConfig, PlannerPolicy,
338    PqSearchOptions, ProductQuantizationBuildLimits, ProductQuantizationBuildStats,
339    ProductQuantizationConfig, ProductQuantizationQuality, ProductQuantizer, ProximityBuildStats,
340    ProximityConfig, ProximityFilter, ProximityMap, ProximityMembershipProof,
341    ProximityMembershipVerification, ProximityMutation, ProximityMutationStats,
342    ProximityProofFilter, ProximityReadSession, ProximityRecord, ProximityRecordRef,
343    ProximitySearchClaim, ProximitySearchEvent, ProximitySearchProof, ProximitySearchRequest,
344    ProximitySearchStats, ProximitySearchVerification, ProximityStructuralProof,
345    ProximityStructuralVerification, ProximityTree, ProximityVectorRef, ProximityVerification,
346    QueryKernel, ScalarQuantizationConfig, SearchBackend, SearchBudget, SearchCompletion, SearchIo,
347    SearchOptions, SearchPlan, SearchPlanSummary, SearchPolicy, SearchRequest, SearchResult,
348    SearchRuntime, SearchRuntimePolicy, StoreCacheNamespace, VectorStorageConfig,
349    SEARCH_PLAN_FORMAT_VERSION,
350};
351pub use prolly::proximity::{
352    AsyncAcceleratorCatalog, AsyncAcceleratorSet, AsyncCompositeAccelerator, AsyncHnswIndex,
353    AsyncIoConfig, AsyncProductQuantizer, AsyncProximityMap, AsyncSearchControl, CancellationToken,
354};
355pub use prolly::range::{AsyncRangeIter, AsyncRangePage, AsyncReversePage};
356pub use prolly::range::{
357    CursorWindow, RangeCursor, RangeIter, RangePage, ReverseCursor, ReversePage,
358};
359pub use prolly::read::AsyncReadSession;
360pub use prolly::read::{
361    BorrowedMergeResolver, ConflictRef, DiffRef, EntryRef, MergeDecision, OwnedRangeScanSession,
362    OwnedReadSession, OwnedValueLease, ReadSession, ScanOutcome, ValueRefView,
363};
364pub use prolly::remote::{
365    conformance as remote_conformance, RemoteAdapterError, RemoteBatchOp, RemoteManifestUpdate,
366    RemoteNamedRoot, RemoteProllyStore, RemoteRootCondition, RemoteRootWrite, RemoteStoreBackend,
367    RemoteStoreConfig, RemoteTransactionConflict, RemoteTransactionUpdate,
368};
369pub use prolly::secondary_index::{
370    catalog_checkpoint_key, catalog_checkpoints_prefix, catalog_current_key,
371    catalog_descriptor_key, catalog_format_key, catalog_map_id, catalog_retired_key,
372    control_record_key, control_root_name, decode_physical_index_key,
373    decode_physical_index_key_ref, descriptor_fingerprint, index_map_id, physical_index_key,
374    term_bounds_exact, term_bounds_prefix, term_bounds_range, ActiveIndexControl,
375    ActiveIndexHealth, DecodedPhysicalIndexKey, DecodedPhysicalIndexKeyRef, IndexBuildResult,
376    IndexCheckpoint, IndexControl, IndexProjection, IndexValue, IndexValueRef, IndexVerification,
377    IndexedHeadRecord, IndexedMap, IndexedMapEditor, IndexedMapHealth, IndexedMapMetricsSnapshot,
378    IndexedMapUpdate, IndexedRetentionResult, IndexedSnapshot, IndexedSnapshotBundle,
379    IndexedSnapshotBundleIndex, IndexedSnapshotBundleSummary, IndexedSnapshotBundleVerification,
380    IndexedSnapshotId, IndexedSourceRecord, IndexedSourceRecordRef, IndexedVersion,
381    ProjectedIndexEntry, SecondaryIndex, SecondaryIndexBuilder, SecondaryIndexCursor,
382    SecondaryIndexDescriptor, SecondaryIndexDirection, SecondaryIndexEntry, SecondaryIndexEntryRef,
383    SecondaryIndexError, SecondaryIndexExtractor, SecondaryIndexLimits, SecondaryIndexMatch,
384    SecondaryIndexMatchRef, SecondaryIndexPage, SecondaryIndexRegistry, SecondaryIndexSnapshot,
385    StreamingSecondaryIndexExtractor, TermBounds, INDEXED_SNAPSHOT_BUNDLE_FORMAT_VERSION,
386    INDEX_PHYSICAL_LAYOUT_VERSION, SECONDARY_INDEX_FORMAT_VERSION,
387};
388pub use prolly::snapshot::{
389    snapshot_id_from_name, snapshot_root_name, SnapshotManager, SnapshotNamespace, SnapshotRoot,
390    SnapshotSelection, SNAPSHOT_BRANCH_PREFIX, SNAPSHOT_CHECKPOINT_PREFIX, SNAPSHOT_TAG_PREFIX,
391};
392pub use prolly::splice::{splice, SpliceStats};
393pub use prolly::stats::{StatsComparison, StatsDiff, StatsPercentageChange, TreeStats};
394pub use prolly::store::{AsyncStore, SyncStoreAsAsync};
395pub use prolly::store::{
396    BatchOp, FileNodeStore, FileNodeStoreError, MemStore, MemStoreError, NodePublication,
397    NodePublicationHint, NodeStoreScan, PublicationOrigin, 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};
408pub use prolly::transaction::{
409    AsyncProllyTransaction, AsyncTransactionOverlayStore, AsyncTransactionalStore,
410    OwnedAsyncProllyTransaction, OwnedAsyncTransactionOverlayStore,
411};
412pub use prolly::transaction::{
413    OwnedProllyTransaction, ProllyTransaction, RootCondition, RootWrite, TransactionConflict,
414    TransactionNodeWrite, TransactionOverlayError, TransactionUpdate, TransactionalStore,
415};
416pub use prolly::tree::Tree;
417pub use prolly::value::{
418    decode_cbor, decode_json, encode_cbor, encode_json, CborCodec, JsonCodec, ValueCodec,
419    VersionedCborCodec, VersionedJsonCodec, VersionedValue,
420};
421pub use prolly::versioned_map::{AsyncMapChangeSubscription, AsyncMapSnapshot, AsyncVersionedMap};
422pub use prolly::versioned_map::{
423    BytesKeyCodec, KeyCodec, MapBackupVersion, MapCatalogVerification, MapChangeEvent,
424    MapChangeSubscription, MapComparison, MapMerge, MapReverseIter, MapSnapshot, MapVersion,
425    MapVersionId, ProofAuthentication, StringKeyCodec, TypedMigrationResult, TypedVersionedMap,
426    VersionPruneResult, VersionedMap, VersionedMapBackup, VersionedMapBatchResult,
427    VersionedMapEditor, VersionedMapUpdate, VersionedMapsTransaction,
428    DEFAULT_VERSIONED_MAP_RETRIES, VERSIONED_MAP_ROOT_PREFIX,
429};
430pub use prolly::write::WriteStats;
431pub use prolly::write_session::{PendingValue, Savepoint, WriteSession};
432pub use prolly::AsyncProlly;
433pub use prolly::{ChangedSpan, ChangedSpanHint, KeyValue, Prolly, ProllyMetricsSnapshot};
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
