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::cid::Cid;
284pub use prolly::config::{Config, ConfigBuilder};
285pub use prolly::crdt::{
286    ConflictFreeMerger, CrdtConfig, CrdtResolution, CustomMergeFn, DefaultConflictFreeMerger,
287    DeletePolicy, MergeStrategy, MultiValueSet, TimestampExtractor, TimestampedValue,
288};
289pub use prolly::cursor::{Cursor, CursorIterator, DiffCursor};
290pub use prolly::debug::{
291    TreeDebugComparedNode, TreeDebugComparison, TreeDebugComparisonLevel, TreeDebugLevel,
292    TreeDebugNode, TreeDebugNodeStatus, TreeDebugView,
293};
294#[cfg(feature = "async-store")]
295pub use prolly::diff::{AsyncConflictIter, AsyncDiffIter};
296pub use prolly::diff::{
297    DiffPage, DiffTraversalStats, MergeExplanation, MergeFallbackReason, MergeFastPath,
298    MergeResolutionKind, MergeReuseReason, MergeTrace, MergeTraceEvent, MergeTraceStage,
299    StructuralDiffCursor, StructuralDiffMarker, StructuralDiffPage,
300};
301pub use prolly::encoding::Encoding;
302pub use prolly::error::{resolver, Conflict, Diff, Error, Mutation, Resolution, Resolver};
303pub use prolly::gc::{
304    BlobGcPlan, BlobGcReachability, BlobGcSweep, GcPlan, GcReachability, GcSweep,
305};
306pub use prolly::key::{
307    debug_key, decode_segments, encode_segment, i128_key, i64_key, prefix_end, prefix_range,
308    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::{DefaultParallelRebalancer, ParallelConfig, ParallelRebalancer};
318pub use prolly::policy::{
319    MergePolicyFn, MergePolicyRegistry, MergePolicyRule, MergePolicyRuleLabel,
320};
321pub use prolly::proof::{
322    inspect_proof_bundle, sign_proof_bundle_hmac_sha256, verify_authenticated_proof_bundle,
323    verify_authenticated_proof_envelope, verify_diff_page_proof, verify_key_proof,
324    verify_multi_key_proof, verify_proof_bundle, verify_range_page_proof, verify_range_proof,
325    AuthenticatedProofBundleVerification, AuthenticatedProofEnvelope,
326    AuthenticatedProofEnvelopeVerification, DiffPageProof, DiffPageProofVerification, KeyProof,
327    KeyProofVerification, MultiKeyProof, MultiKeyProofVerification, ProofBundleKind,
328    ProofBundleSummary, ProofBundleVerification, ProvedDiffPage, ProvedRangePage, RangePageProof,
329    RangePageProofVerification, RangeProof, RangeProofVerification,
330};
331pub use prolly::range::{
332    CursorWindow, RangeCursor, RangeIter, RangePage, ReverseCursor, ReversePage,
333};
334pub use prolly::snapshot::{
335    snapshot_id_from_name, snapshot_root_name, SnapshotManager, SnapshotNamespace, SnapshotRoot,
336    SnapshotSelection, SNAPSHOT_BRANCH_PREFIX, SNAPSHOT_CHECKPOINT_PREFIX, SNAPSHOT_TAG_PREFIX,
337};
338pub use prolly::streaming::{DefaultStreamingDiffer, StreamingDiffer};
339pub use prolly::{ChangedSpan, ChangedSpanHint, Prolly, ProllyMetricsSnapshot};
340
341#[cfg(feature = "async-store")]
342pub use prolly::range::{AsyncRangeIter, AsyncRangePage, AsyncReversePage};
343#[cfg(feature = "async-store")]
344pub use prolly::remote::{
345    conformance as remote_conformance, RemoteAdapterError, RemoteBatchOp, RemoteManifestUpdate,
346    RemoteNamedRoot, RemoteProllyStore, RemoteRootCondition, RemoteRootWrite, RemoteStoreBackend,
347    RemoteStoreConfig, RemoteTransactionConflict, RemoteTransactionUpdate,
348};
349pub use prolly::stats::{StatsComparison, StatsDiff, StatsPercentageChange, TreeStats};
350#[cfg(feature = "async-store")]
351pub use prolly::store::{AsyncStore, SyncStoreAsAsync};
352pub use prolly::store::{
353    BatchOp, FileNodeStore, FileNodeStoreError, MemStore, MemStoreError, NodeStoreScan, Store,
354};
355#[cfg(feature = "rocksdb")]
356pub use prolly::store::{CompressionType, RocksDBConfig, RocksDBStore, RocksDBStoreError};
357#[cfg(feature = "pglite")]
358pub use prolly::store::{PgliteStore, PgliteStoreConfig, PgliteStoreError};
359#[cfg(feature = "slatedb")]
360pub use prolly::store::{SlateDbStore, SlateDbStoreConfig, SlateDbStoreError};
361#[cfg(feature = "sqlite")]
362pub use prolly::store::{SqliteStore, SqliteStoreConfig, SqliteStoreError};
363#[cfg(feature = "tokio")]
364pub use prolly::store::{TokioBlockingStore, TokioBlockingStoreError};
365pub use prolly::sync::{
366    MissingNodeCopy, MissingNodePlan, SnapshotBundle, SnapshotBundleNode, SnapshotBundleSummary,
367    SnapshotBundleVerification, SNAPSHOT_BUNDLE_FORMAT_VERSION,
368};
369pub use prolly::tombstone::{
370    is_tombstone_value, tombstone_compaction, tombstone_upsert, Tombstone,
371};
372#[cfg(feature = "async-store")]
373pub use prolly::transaction::{
374    AsyncProllyTransaction, AsyncTransactionOverlayStore, AsyncTransactionalStore,
375};
376pub use prolly::transaction::{
377    OwnedProllyTransaction, OwnedTransactionOverlayStore, ProllyTransaction, RootCondition,
378    RootWrite, TransactionConflict, TransactionNodeWrite, TransactionOverlayError,
379    TransactionUpdate, TransactionalStore,
380};
381pub use prolly::tree::Tree;
382pub use prolly::value::{
383    decode_cbor, decode_json, encode_cbor, encode_json, CborCodec, JsonCodec, ValueCodec,
384    VersionedCborCodec, VersionedJsonCodec, VersionedValue,
385};
386#[cfg(feature = "async-store")]
387pub use prolly::AsyncProlly;
388
389// Re-export constants
390pub use prolly::encoding::{
391    DEFAULT_CHUNKING_FACTOR, DEFAULT_HASH_SEED, DEFAULT_MAX_CHUNK_SIZE, DEFAULT_MIN_CHUNK_SIZE,
392    INIT_LEVEL,
393};
prolly/lib.rs

prolly/
lib.rs
