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
252mod prolly;
253
254// Re-export public API from prolly module
255pub use prolly::batch::{
256    append_batch, BatchApplyResult, BatchApplyStats, BatchWriter, MutationBuffer,
257};
258#[cfg(feature = "async-store")]
259pub use prolly::blob::{AsyncBlobStore, SyncBlobStoreAsAsync};
260pub use prolly::blob::{
261    BlobRef, BlobStore, BlobStoreScan, FileBlobStore, FileBlobStoreError, LargeValueConfig,
262    MemBlobStore, MemBlobStoreError, ValueRef, DEFAULT_INLINE_VALUE_THRESHOLD,
263};
264#[cfg(feature = "tokio")]
265pub use prolly::blob::{TokioBlockingBlobStore, TokioBlockingBlobStoreError};
266pub use prolly::boundary::BoundaryDetector;
267pub use prolly::builder::{BatchBuilder, SortedBatchBuilder};
268pub use prolly::chunking;
269pub use prolly::cid::Cid;
270pub use prolly::config::{Config, ConfigBuilder, RuntimeConfig};
271pub use prolly::content_graph::{
272    compare_and_swap_named_content_root, compare_and_swap_named_content_root_with_limits,
273    content_references, copy_and_publish_content_graph, copy_content_graph,
274    load_named_content_root, load_named_content_root_with_limits, plan_content_gc,
275    put_named_content_root, put_named_content_root_with_limits, sweep_content_gc,
276    sweep_content_gc_with_invalidator, walk_content_graph, ContentGcPlan, ContentGcSweep,
277    ContentGraphCopy, ContentGraphLimits, ContentGraphWalk, ContentManifestUpdate,
278    ContentObjectKind, ContentRootManifest, ContentRootPublication, TypedContentObject,
279    TypedContentRoot,
280};
281pub use prolly::crdt::{
282    ConflictFreeMerger, CrdtConfig, CrdtResolution, CustomMergeFn, DefaultConflictFreeMerger,
283    DeletePolicy, MergeStrategy, MultiValueSet, TimestampExtractor, TimestampedValue,
284};
285pub use prolly::cursor::{Cursor, CursorIterator, DiffCursor};
286pub use prolly::debug::{
287    TreeDebugComparedNode, TreeDebugComparison, TreeDebugComparisonLevel, TreeDebugLevel,
288    TreeDebugNode, TreeDebugNodeStatus, TreeDebugView,
289};
290#[cfg(feature = "async-store")]
291pub use prolly::diff::{AsyncConflictIter, AsyncDiffIter};
292pub use prolly::diff::{
293    DiffPage, DiffTraversalStats, MergeExplanation, MergeFallbackReason, MergeFastPath,
294    MergeResolutionKind, MergeReuseReason, MergeTrace, MergeTraceEvent, MergeTraceStage,
295    StructuralDiffCursor, StructuralDiffMarker, StructuralDiffPage,
296};
297pub use prolly::encoding::Encoding;
298pub use prolly::error::{resolver, Conflict, Diff, Error, Mutation, Resolution, Resolver};
299pub use prolly::format::{
300    BoundaryInput, BoundaryRule, ChunkMeasure, ChunkingSpec, HashAlgorithm, NodeLayoutSpec,
301    TreeFormat,
302};
303pub use prolly::gc::{
304    BlobGcPlan, BlobGcReachability, BlobGcSweep, GcPlan, GcReachability, GcSweep,
305};
306pub use prolly::key::{
307    debug_key, decode_segments, encode_segment, encode_segment_prefix, i128_key, i64_key,
308    prefix_end, prefix_range, timestamp_millis_key, u128_key, u64_key, KeyBuilder, KeyDecodeError,
309};
310#[cfg(feature = "async-store")]
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};
353#[cfg(feature = "async-store")]
354pub use prolly::proximity::{
355    AsyncAcceleratorCatalog, AsyncAcceleratorSet, AsyncCompositeAccelerator, AsyncHnswIndex,
356    AsyncIoConfig, AsyncProductQuantizer, AsyncProximityMap, AsyncSearchControl, CancellationToken,
357};
358pub use prolly::range::{
359    CursorWindow, RangeCursor, RangeIter, RangePage, ReverseCursor, ReversePage,
360};
361#[cfg(feature = "async-store")]
362pub use prolly::read::AsyncReadSession;
363pub use prolly::read::{
364    BorrowedMergeResolver, ConflictRef, DiffRef, EntryRef, MergeDecision, OwnedRangeScanSession,
365    OwnedReadSession, OwnedValueLease, ReadSession, ScanOutcome, ValueRefView,
366};
367pub use prolly::secondary_index::{
368    catalog_checkpoint_key, catalog_checkpoints_prefix, catalog_current_key,
369    catalog_descriptor_key, catalog_format_key, catalog_map_id, catalog_retired_key,
370    control_record_key, control_root_name, decode_physical_index_key,
371    decode_physical_index_key_ref, descriptor_fingerprint, index_map_id, physical_index_key,
372    term_bounds_exact, term_bounds_prefix, term_bounds_range, ActiveIndexControl,
373    ActiveIndexHealth, DecodedPhysicalIndexKey, DecodedPhysicalIndexKeyRef, IndexBuildResult,
374    IndexCheckpoint, IndexControl, IndexProjection, IndexValue, IndexValueRef, IndexVerification,
375    IndexedHeadRecord, IndexedMap, IndexedMapEditor, IndexedMapHealth, IndexedMapMetricsSnapshot,
376    IndexedMapUpdate, IndexedRetentionResult, IndexedSnapshot, IndexedSnapshotBundle,
377    IndexedSnapshotBundleIndex, IndexedSnapshotBundleSummary, IndexedSnapshotBundleVerification,
378    IndexedSnapshotId, IndexedSourceRecord, IndexedSourceRecordRef, IndexedVersion,
379    ProjectedIndexEntry, SecondaryIndex, SecondaryIndexBuilder, SecondaryIndexCursor,
380    SecondaryIndexDescriptor, SecondaryIndexDirection, SecondaryIndexEntry, SecondaryIndexEntryRef,
381    SecondaryIndexError, SecondaryIndexExtractor, SecondaryIndexLimits, SecondaryIndexMatch,
382    SecondaryIndexMatchRef, SecondaryIndexPage, SecondaryIndexRegistry, SecondaryIndexSnapshot,
383    StreamingSecondaryIndexExtractor, TermBounds, INDEXED_SNAPSHOT_BUNDLE_FORMAT_VERSION,
384    INDEX_PHYSICAL_LAYOUT_VERSION, SECONDARY_INDEX_FORMAT_VERSION,
385};
386pub use prolly::snapshot::{
387    snapshot_id_from_name, snapshot_root_name, SnapshotManager, SnapshotNamespace, SnapshotRoot,
388    SnapshotSelection, SNAPSHOT_BRANCH_PREFIX, SNAPSHOT_CHECKPOINT_PREFIX, SNAPSHOT_TAG_PREFIX,
389};
390pub use prolly::splice::{splice, SpliceStats};
391pub use prolly::streaming::{DefaultStreamingDiffer, StreamingDiffer};
392pub use prolly::write::WriteStats;
393pub use prolly::{ChangedSpan, ChangedSpanHint, KeyValue, Prolly, ProllyMetricsSnapshot};
394
395#[cfg(feature = "async-store")]
396pub use prolly::range::{AsyncRangeIter, AsyncRangePage, AsyncReversePage};
397#[cfg(feature = "async-store")]
398pub use prolly::remote::{
399    conformance as remote_conformance, RemoteAdapterError, RemoteBatchOp, RemoteManifestUpdate,
400    RemoteNamedRoot, RemoteProllyStore, RemoteRootCondition, RemoteRootWrite, RemoteStoreBackend,
401    RemoteStoreConfig, RemoteTransactionConflict, RemoteTransactionUpdate,
402};
403pub use prolly::stats::{StatsComparison, StatsDiff, StatsPercentageChange, TreeStats};
404#[cfg(feature = "async-store")]
405pub use prolly::store::{AsyncStore, SyncStoreAsAsync};
406pub use prolly::store::{
407    BatchOp, FileNodeStore, FileNodeStoreError, MemStore, MemStoreError, NodeStoreScan, Store,
408};
409#[cfg(feature = "tokio")]
410pub use prolly::store::{TokioBlockingStore, TokioBlockingStoreError};
411pub use prolly::sync::{
412    MissingNodeCopy, MissingNodePlan, SnapshotBundle, SnapshotBundleNode, SnapshotBundleSummary,
413    SnapshotBundleVerification, SNAPSHOT_BUNDLE_FORMAT_VERSION,
414};
415pub use prolly::tombstone::{
416    is_tombstone_value, tombstone_compaction, tombstone_upsert, Tombstone,
417};
418#[cfg(feature = "async-store")]
419pub use prolly::transaction::{
420    AsyncProllyTransaction, AsyncTransactionOverlayStore, AsyncTransactionalStore,
421    OwnedAsyncProllyTransaction, OwnedAsyncTransactionOverlayStore,
422};
423pub use prolly::transaction::{
424    OwnedProllyTransaction, OwnedTransactionOverlayStore, ProllyTransaction, RootCondition,
425    RootWrite, TransactionConflict, TransactionNodeWrite, TransactionOverlayError,
426    TransactionUpdate, TransactionalStore,
427};
428pub use prolly::tree::Tree;
429pub use prolly::value::{
430    decode_cbor, decode_json, encode_cbor, encode_json, CborCodec, JsonCodec, ValueCodec,
431    VersionedCborCodec, VersionedJsonCodec, VersionedValue,
432};
433#[cfg(feature = "async-store")]
434pub use prolly::versioned_map::{AsyncMapChangeSubscription, AsyncMapSnapshot, AsyncVersionedMap};
435pub use prolly::versioned_map::{
436    BytesKeyCodec, KeyCodec, MapBackupVersion, MapCatalogVerification, MapChangeEvent,
437    MapChangeSubscription, MapComparison, MapMerge, MapReverseIter, MapSnapshot, MapVersion,
438    MapVersionId, ProofAuthentication, StringKeyCodec, TypedMigrationResult, TypedVersionedMap,
439    VersionPruneResult, VersionedMap, VersionedMapBackup, VersionedMapBatchResult,
440    VersionedMapEditor, VersionedMapUpdate, VersionedMapsTransaction,
441    DEFAULT_VERSIONED_MAP_RETRIES, VERSIONED_MAP_ROOT_PREFIX,
442};
443pub use prolly::write_session::{PendingValue, Savepoint, WriteSession};
444#[cfg(feature = "async-store")]
445pub use prolly::AsyncProlly;
446
447// Re-export constants
448pub use prolly::encoding::{
449    DEFAULT_CHUNKING_FACTOR, DEFAULT_HASH_SEED, DEFAULT_MAX_CHUNK_SIZE, DEFAULT_MIN_CHUNK_SIZE,
450    INIT_LEVEL,
451};
prolly/lib.rs

prolly/
lib.rs
