### Checkpoint Pruning Repeated Test Setup Source: https://docs.rs/shardtree/0.6.1/x86_64-apple-darwin/src/shardtree/lib.rs.html Sets up a ShardTree with several appended elements and prepares for testing repeated checkpointing and pruning. This is a setup for a more complex test scenario. ```rust #[test] fn checkpoint_pruning_repeated() { // Create a tree with some leaves. let mut tree = new_tree(10); for c in 'a'..='c' { tree.append(c.to_string(), Retention::Ephemeral).unwrap(); } // Repeatedly checkpoint the tree at the same position until the checkpoint cache ``` -------------------------------- ### Test Setup for Root Hashes Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/src/shardtree/store/caching.rs.html Initializes MemoryShardStore and CachingShardStore instances for testing root hash operations. ```rust #[test] fn root_hashes() { use Retention::*; { let mut lhs = MemoryShardStore::<_, u64>::empty(); let mut rhs = CachingShardStore::load(MemoryShardStore::empty()).unwrap(); let mut tree = CombinedTree::::new( ShardTree::<_, 4, 3>::new(&mut lhs, 100), ShardTree::<_, 4, 3>::new(&mut rhs, 100), ); ``` -------------------------------- ### ShardTree Checkpoint Pruning Repeated Test Setup Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/src/shardtree/lib.rs.html Sets up a ShardTree with appended elements for testing repeated checkpoint pruning. ```rust let mut tree = new_tree(10); for c in 'a'..='c' { tree.append(c.to_string(), Retention::Ephemeral).unwrap(); } ``` -------------------------------- ### Testing CachingShardStore with CombinedTree Source: https://docs.rs/shardtree/0.6.1/src/shardtree/store/caching.rs.html This snippet demonstrates the test setup for CachingShardStore. It initializes MemoryShardStore and CachingShardStore, combines them into a CombinedTree, and then checks operations against these trees. ```rust for (i, sample) in samples.iter().enumerate() { let mut lhs = MemoryShardStore::empty(); let mut rhs = CachingShardStore::load(MemoryShardStore::empty()).unwrap(); let tree = CombinedTree::new( ShardTree::<_, 4, 3>::new(&mut lhs, 100), ShardTree::<_, 4, 3>::new(&mut rhs, 100), ); let result = check_operations(tree, sample); assert!( matches!(result, Ok(())), "Reference/Test mismatch at index {}: {:?}", i, result ); check_equal(lhs, rhs); } ``` -------------------------------- ### Insert Roots and Construct Witness Source: https://docs.rs/shardtree/0.6.1/i686-unknown-linux-gnu/src/shardtree/testing.rs.html Demonstrates inserting initial shard roots and then using `batch_insert` to simulate discovering a note. It concludes by constructing a witness for this note and asserting its path elements. This is useful for testing witness generation with pruned subtrees. ```rust let shard_root_level = Level::from(3); for idx in 0u64..4 { let root = if idx == 3 { "abcdefgh".to_string() } else { idx.to_string() }; tree.insert(Address::from_parts(shard_root_level, idx), root) .unwrap(); } tree.batch_insert( Position::from(24), ('a'..='h').map(|c| { ( c.to_string(), match c { 'c' => Retention::Marked, 'h' => Retention::Checkpoint { id: 3, marking: Marking::None, }, _ => Retention::Ephemeral, }, ) }), ) .unwrap(); let witness = tree .witness_at_checkpoint_depth(Position::from(26), 0) .unwrap(); assert_eq!( witness.expect("can produce a witness").path_elems(), &[ "d", "ab", "efgh", "2", "01", "________________________________" ] ); ``` -------------------------------- ### Batch Insert Values into LocatedTree Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/shardtree/struct.LocatedTree.html Inserts a range of values into the LocatedTree at a specified start position. Returns an error if the start position is invalid or a conflict is detected. ```rust pub fn batch_insert)>>( &self, start: Position, values: I, ) -> Result>, InsertionError> ``` -------------------------------- ### batch_insert Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/shardtree/type.LocatedPrunableTree.html Inserts a range of values into the subtree from a given iterator, starting at a specified position. The start position must be within the subtree's range. Unconsumed iterator items are returned if the end position is outside the subtree's range. Returns Ok(None) if the iterator is empty, Ok(Some(BatchInsertionResult)) on success, or an error for invalid start position or root conflicts. ```APIDOC ## batch_insert ### Description Inserts a range of values into the subtree by consuming the given iterator, starting at the specified position. The start position must exist within the position range of this subtree. If the position at the end of the iterator is outside of the subtree’s range, the unconsumed part of the iterator will be returned as part of the result. Returns `Ok(None)` if the provided iterator is empty, `Ok(Some(BatchInsertionResult))` if values were successfully inserted, or an error if the start position provided is outside of this tree’s position range or if a conflict with an existing subtree root is detected. ### Method `batch_insert` ### Parameters * `start`: The starting `Position` for insertion. * `values`: An iterator yielding `(H, Retention)` pairs. ### Returns * `Result>, InsertionError>` ``` -------------------------------- ### ShardTree Batch Insert Example Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/src/shardtree/batch.rs.html Demonstrates performing an out-of-order batch insertion into a ShardTree. This is useful for inserting elements at arbitrary positions within an existing tree structure. ```rust let out_of_order = base .batch_insert::<(), _>( Position::from(3), vec![("d".to_string(), Retention::Ephemeral)].into_iter(), ) .unwrap() .unwrap(); assert_eq!( out_of_order.subtree, LocatedPrunableTree { root_addr: Address::from_parts(2.into(), 0), root: parent( parent(leaf(("a".to_string(), RetentionFlags::EPHEMERAL)), nil()), parent(nil(), leaf(("d".to_string(), RetentionFlags::EPHEMERAL))) ) } ); ``` -------------------------------- ### batch_insert Source: https://docs.rs/shardtree/0.6.1/i686-unknown-linux-gnu/src/shardtree/batch.rs.html Inserts a range of values into the ShardTree starting at a specified position. Returns `Ok(None)` if the iterator is empty, `Ok(Some(BatchInsertionResult))` if values were inserted, or an error if the start position is out of range or a conflict is detected. ```APIDOC ## batch_insert ### Description Inserts a range of values into the ShardTree starting at a specified position. Returns `Ok(None)` if the iterator is empty, `Ok(Some(BatchInsertionResult))` if values were inserted, or an error if the start position is out of range or a conflict is detected. The unconsumed part of the iterator is returned if its end position is outside the subtree's range. ### Method `pub fn batch_insert)>>(&self, start: Position, values: I) -> Result>, InsertionError>` ### Parameters * `start` - The starting `Position` for the insertion. * `values` - An iterator yielding `(H, Retention)` pairs to be inserted. ``` -------------------------------- ### ShardTree Caching Store Operation Examples Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/src/shardtree/store/caching.rs.html Demonstrates various sequences of operations on a CachingShardStore, verifying their correctness against a MemoryShardStore. This includes append_str, Checkpoint, unmark, Rewind, and witness operations. ```rust vec![ append_str("f", Retention::Ephemeral), witness(0, 1), ] ``` ```rust vec![ append_str("g", Retention::Marked), Checkpoint(1), unmark(0), append_str("h", Retention::Ephemeral), witness(0, 0), ] ``` ```rust vec![ append_str("i", Retention::Marked), Checkpoint(1), unmark(0), append_str("j", Retention::Ephemeral), witness(0, 0), ] ``` ```rust vec![ append_str("i", Retention::Marked), append_str("j", Retention::Ephemeral), Checkpoint(1), append_str("k", Retention::Ephemeral), witness(0, 1), ] ``` ```rust vec![ append_str("l", Retention::Marked), Checkpoint(1), Checkpoint(2), append_str("m", Retention::Ephemeral), Checkpoint(3), witness(0, 2), ] ``` ```rust vec![ Checkpoint(1), append_str("n", Retention::Marked), witness(0, 1), ] ``` ```rust vec![ append_str("a", Retention::Marked), Checkpoint(1), unmark(0), Checkpoint(2), append_str("b", Retention::Ephemeral), witness(0, 1), ] ``` ```rust vec![ append_str("a", Retention::Marked), append_str("b", Retention::Ephemeral), unmark(0), Checkpoint(1), witness(0, 0), ] ``` ```rust vec![ append_str("a", Retention::Marked), Checkpoint(1), unmark(0), Checkpoint(2), Rewind(1), append_str("b", Retention::Ephemeral), witness(0, 0), ] ``` ```rust vec![ append_str("a", Retention::Marked), Checkpoint(1), Checkpoint(2), Rewind(1), append_str("a", Retention::Ephemeral), unmark(0), witness(0, 1), ] ``` ```rust vec![ append_str("o", Retention::Ephemeral), append_str("p", Retention::Marked), append_str("q", Retention::Ephemeral), Checkpoint(1), unmark(1), witness(1, 1), ] ``` ```rust vec![ append_str("r", Retention::Ephemeral), append_str("s", Retention::Ephemeral), append_str("t", Retention::Marked), Checkpoint(1), unmark(2), Checkpoint(2), witness(2, 2), ] ``` ```rust vec![ append_str("u", Retention::Marked), append_str("v", Retention::Ephemeral), append_str("w", Retention::Ephemeral), Checkpoint(1), unmark(0), append_str("x", Retention::Ephemeral), Checkpoint(2), Checkpoint(3), witness(0, 3), ] ``` -------------------------------- ### batch_insert Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/type.LocatedPrunableTree.html Inserts a range of values into the subtree starting at a specified position. It handles iterators and returns unconsumed items if the end position is out of range. Errors can occur if the start position is invalid or if a conflict is detected. ```APIDOC ## batch_insert ### Description Inserts a range of values into the subtree by consuming the given iterator, starting at the specified position. The start position must exist within the position range of this subtree. If the position at the end of the iterator is outside of the subtree’s range, the unconsumed part of the iterator will be returned as part of the result. Returns `Ok(None)` if the provided iterator is empty, `Ok(Some(BatchInsertionResult))` if values were successfully inserted, or an error if the start position provided is outside of this tree’s position range or if a conflict with an existing subtree root is detected. ### Method `batch_insert` ### Parameters - `start`: The starting `Position` for insertion. - `values`: An iterator yielding `(H, Retention)` pairs. ### Returns - `Result>, InsertionError>`: Ok with insertion result, Ok(None) if iterator is empty, or an error. ``` -------------------------------- ### type_id Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/shardtree/struct.RetentionFlags.html Gets the TypeId of the RetentionFlags. ```APIDOC ## type_id ### Description Gets the `TypeId` of `self`. ### Method `type_id` ### Returns - `TypeId` - The `TypeId` of the value. ``` -------------------------------- ### Basic Checkpoint and Rewind Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/src/shardtree/store/caching.rs.html Demonstrates the basic checkpoint and rewind operations on a CombinedTree with CachingShardStore. This is useful for verifying state persistence and rollback capabilities. ```rust { let mut lhs = MemoryShardStore::empty(); let mut rhs = CachingShardStore::load(MemoryShardStore::empty()).unwrap(); let mut t = CombinedTree::new( ShardTree::<_, 4, 3>::new(&mut lhs, 100), ShardTree::<_, 4, 3>::new(&mut rhs, 100), ); assert!(t.checkpoint(1)); assert!(t.rewind(0)); check_equal(lhs, rhs); } ``` -------------------------------- ### batch_insert Source: https://docs.rs/shardtree/0.6.1/x86_64-apple-darwin/type.LocatedPrunableTree.html Inserts a range of values from an iterator into the subtree starting at a specified position. Returns unconsumed iterator parts if the end position is outside the subtree's range. Errors can occur if the start position is invalid or a conflict is detected. ```APIDOC ## batch_insert ### Description Inserts a range of values into the subtree by consuming the given iterator, starting at the specified position. The start position must exist within the position range of this subtree. If the position at the end of the iterator is outside of the subtree’s range, the unconsumed part of the iterator will be returned as part of the result. Returns `Ok(None)` if the provided iterator is empty, `Ok(Some(BatchInsertionResult))` if values were successfully inserted, or an error if the start position provided is outside of this tree’s position range or if a conflict with an existing subtree root is detected. ### Method `&self` ### Parameters * `start`: The starting `Position` for insertion. * `values`: An iterator yielding `(H, Retention)` pairs. ### Returns `Result>, InsertionError>` - `Ok(None)` if the iterator was empty. - `Ok(Some(BatchInsertionResult))` if values were successfully inserted. - `Err(InsertionError)` if the start position is invalid or a conflict is detected. ``` -------------------------------- ### ShardTree Sequential Batch Insert Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/src/shardtree/batch.rs.html Shows how to perform a sequential batch insertion into a ShardTree after an out-of-order insertion. This example inserts multiple elements at a specific position, demonstrating the handling of sequential additions. ```rust let complete = out_of_order .subtree .batch_insert::<(), _>( Position::from(1), vec![ ("b".to_string(), Retention::Ephemeral), ("c".to_string(), Retention::Ephemeral), ] .into_iter(), ) .unwrap() .unwrap(); assert_eq!(complete.subtree.right_filled_root(), Ok("abcd".to_string())); ``` -------------------------------- ### Any for T Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/shardtree/store/memory/struct.MemoryShardStore.html Provides the `type_id` method to get the `TypeId` of the type. ```APIDOC ## Any for T ### Description Provides the `type_id` method to get the `TypeId` of the type. ### fn type_id(&self) -> TypeId Gets the `TypeId` of `self`. ``` -------------------------------- ### Initialize and Append Operations in CachingShardStore Source: https://docs.rs/shardtree/0.6.1/x86_64-apple-darwin/src/shardtree/store/caching.rs.html Demonstrates initializing a CachingShardStore with a MemoryShardStore and performing multiple append operations. It checks the root after appends and verifies the state consistency between the underlying stores. ```rust { let mut lhs = MemoryShardStore::empty(); let mut rhs = CachingShardStore::load(MemoryShardStore::empty()).unwrap(); let mut tree = CombinedTree::new( ShardTree::<_, 4, 3>::new(&mut lhs, 100), ShardTree::<_, 4, 3>::new(&mut rhs, 100), ); assert!(t.append( String::from_u64(0), Checkpoint { id: 1, marking: Marking::Marked, }, )); for _ in 0..3 { assert!(t.append(String::from_u64(0), Ephemeral)); } assert_eq!( t.root(None).unwrap(), String::combine_all(t.depth(), &[0, 0, 0, 0]) ); check_equal(lhs, rhs); } ``` -------------------------------- ### Get Root of LocatedTree Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/shardtree/struct.LocatedTree.html Returns a reference to the root of the LocatedTree. ```rust pub fn root(&self) -> &Tree ``` -------------------------------- ### CloneToUninit (Experimental) Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/shardtree/enum.Node.html An experimental, nightly-only API for performing copy-assignment to uninitialized memory. ```rust unsafe fn clone_to_uninit(&self, dest: *mut u8) ``` -------------------------------- ### type_id Source: https://docs.rs/shardtree/0.6.1/shardtree/struct.ShardTree.html Gets the `TypeId` of the current object. This is part of the `Any` trait implementation. ```APIDOC ## fn type_id(&self) -> TypeId ### Description Gets the `TypeId` of `self`. ### Returns - TypeId - The unique identifier for the type of the object. ``` -------------------------------- ### ShardTree Append and Witness Operations Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/src/shardtree/store/caching.rs.html Demonstrates appending checkpoints and querying witness states in a ShardTree. This example shows how the witness output changes after multiple appends and different checkpoint markings. ```rust assert!(tree.append( String::from_u64(1), Checkpoint { id: 1, marking: Marking::None } )); assert_eq!( tree.witness(0.into(), 0), Some(vec![ String::from_u64(1), String::empty_root(1.into()), String::empty_root(2.into()), String::empty_root(3.into()) ]) ); assert!(tree.append( String::from_u64(2), Checkpoint { id: 2, marking: Marking::Marked } )); assert_eq!( tree.witness(Position::from(2), 0), Some(vec![ String::empty_root(0.into()), String::combine_all(1, &[0, 1]), String::empty_root(2.into()), String::empty_root(3.into()) ]) ); assert!(tree.append( String::from_u64(3), Checkpoint { id: 3, marking: Marking::None } )); assert_eq!( tree.witness(Position::from(2), 0), Some(vec![ String::from_u64(3), String::combine_all(1, &[0, 1]), String::empty_root(2.into()), String::empty_root(3.into()) ]) ); assert!(tree.append( String::from_u64(4), Checkpoint { id: 4, marking: Marking::None } )); assert_eq!( tree.witness(Position::from(2), 0), Some(vec![ String::from_u64(3), String::combine_all(1, &[0, 1]), String::combine_all(2, &[4]), String::empty_root(3.into()) ]) ); check_equal(lhs, rhs); } ``` -------------------------------- ### GetTypeId Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/shardtree/enum.Node.html Gets the TypeId of the Node, useful for runtime type identification. ```rust fn type_id(&self) -> TypeId ``` -------------------------------- ### Load CachingShardStore from Backend Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/src/shardtree/store/caching.rs.html Initializes a CachingShardStore by loading all shard roots, capacity, and checkpoints from a given backend ShardStore into an in-memory cache. ```rust pub fn load(mut backend: S) -> Result { let mut cache = MemoryShardStore::empty(); for shard_root in backend.get_shard_roots()? { let _ = cache.put_shard(backend.get_shard(shard_root)?.expect("known address")); } let _ = cache.put_cap(backend.get_cap()?); backend.with_checkpoints(backend.checkpoint_count()?, |checkpoint_id, checkpoint| { // TODO: Once MSRV is at least 1.82, replace this (and similar `expect()`s below) with: // `let Ok(_) = cache.add_checkpoint(checkpoint_id.clone(), checkpoint.clone());` cache .add_checkpoint(checkpoint_id.clone(), checkpoint.clone()) .expect("error type is Infallible"); Ok(()) })?; // This line is missing in the original code, but is required for the function to compile. Ok(Self { backend, cache, deferred_actions: vec![], }) } ``` -------------------------------- ### Get Root Address of LocatedTree Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/shardtree/struct.LocatedTree.html Returns the root address of the LocatedTree. ```rust pub fn root_addr(&self) -> Address ``` -------------------------------- ### Batch Insert Values at Specific Position in ShardTree Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/src/shardtree/batch.rs.html Inserts a range of values from an iterator starting at a specified position. The start position must be within the subtree's range. Returns Ok(None) for an empty iterator, Ok(Some(BatchInsertionResult)) on success, or an error for out-of-range positions or detected conflicts. ```rust pub fn batch_insert)>>( &self, start: Position, values: I, ) -> Result>, InsertionError> { trace!("Batch inserting into {:?} from {:?}", self.root_addr, start); let subtree_range = self.root_addr.position_range(); let contains_start = subtree_range.contains(&start); if contains_start { let position_range = Range { start, end: subtree_range.end, }; Self::from_iter(position_range, self.root_addr.level(), values) .map(|mut res| { let (subtree, mut incomplete) = self .clone() .insert_subtree(res.subtree, res.contains_marked)?; res.subtree = subtree; res.incomplete.append(&mut incomplete); Ok(res) }) .transpose() } else { Err(InsertionError::OutOfRange(start, subtree_range)) } } ``` -------------------------------- ### Checkpoint Creation Methods Source: https://docs.rs/shardtree/0.6.1/x86_64-apple-darwin/shardtree/store/struct.Checkpoint.html Methods for creating a new Checkpoint instance. ```APIDOC ## `Checkpoint::tree_empty()` ### Description Creates a `Checkpoint` representing an empty `ShardTree`. ### Method `pub fn tree_empty() -> Self` ## `Checkpoint::at_position(position: Position)` ### Description Creates a `Checkpoint` at a specific `Position`. ### Method `pub fn at_position(position: Position) -> Self` ## `Checkpoint::from_parts(tree_state: TreeState, marks_removed: BTreeSet)` ### Description Creates a `Checkpoint` from its constituent parts: the tree's state and a set of removed marks. ### Method `pub fn from_parts(tree_state: TreeState, marks_removed: BTreeSet) -> Self` ``` -------------------------------- ### ShardStore::truncate_shards Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/src/shardtree/store/memory.rs.html Removes all shards from the store starting from the specified shard index. ```APIDOC ## ShardStore::truncate_shards ### Description Removes all shards from the store whose index is greater than or equal to the provided `shard_index`. ### Parameters #### Path Parameters - **shard_index** (`u64`) - The index from which to truncate the shards. All shards at or after this index will be removed. ### Returns - `Result<(), Self::Error>` - An `Ok` if truncation was successful, or `Err` if an error occurred. ### Example ```rust match store.truncate_shards(5) { Ok(_) => println!("Shards truncated successfully."), Err(e) => println!("Error truncating shards: {:?}", e), } ``` ``` -------------------------------- ### LocatedTree Constructor Methods Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/shardtree/struct.LocatedTree.html Methods for creating new LocatedTree instances with default or specific root values. ```APIDOC ## pub fn empty(root_addr: Address) -> Self ### Description Constructs a new empty tree with its root at the provided address. ### Parameters - `root_addr`: The `Address` for the root of the empty tree. ### Returns - `Self`: A new, empty `LocatedTree`. ``` ```APIDOC ## pub fn with_root_value(root_addr: Address, value: V) -> Self ### Description Constructs a new tree consisting of a single leaf with the provided value, and the specified root address. ### Parameters - `root_addr`: The `Address` for the root of the tree. - `value`: The `V` value for the single leaf node. ### Returns - `Self`: A new `LocatedTree` with a single leaf. ``` -------------------------------- ### ShardTree Get Store Reference Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/shardtree/struct.ShardTree.html Returns an immutable reference to the underlying ShardStore. ```rust pub fn store(&self) -> &S ``` -------------------------------- ### Load CachingShardStore from Backend Source: https://docs.rs/shardtree/0.6.1/x86_64-apple-darwin/src/shardtree/store/caching.rs.html Initializes a CachingShardStore by loading all existing shards, capacity, and checkpoints from a backend ShardStore into an in-memory cache. Handles potential errors during backend access. ```rust pub fn load(mut backend: S) -> Result { let mut cache = MemoryShardStore::empty(); for shard_root in backend.get_shard_roots()? { let _ = cache.put_shard(backend.get_shard(shard_root)?.expect("known address")); } let _ = cache.put_cap(backend.get_cap()?); backend.with_checkpoints(backend.checkpoint_count()?, |checkpoint_id, checkpoint| { // TODO: Once MSRV is at least 1.82, replace this (and similar `expect()`s below) with: // `let Ok(_) = cache.add_checkpoint(checkpoint_id.clone(), checkpoint.clone());` cache .add_checkpoint(checkpoint_id.clone(), checkpoint.clone()) .expect("error type is Infallible"); Ok(()) })?; Ok(Self { backend, cache, deferred_actions: vec![], }) } ``` -------------------------------- ### MemoryShardStore::truncate_shards Source: https://docs.rs/shardtree/0.6.1/x86_64-pc-windows-msvc/src/shardtree/store/memory.rs.html Removes shards from the store starting from the specified shard index up to the end. ```APIDOC ## MemoryShardStore::truncate_shards ### Description Removes shards from the store starting from the specified shard index up to the end. ### Method `truncate_shards` ### Parameters #### Path Parameters - **shard_index** (u64) - The index from which to start truncating shards. ### Returns - `Result<(), Self::Error>` - An `Ok` on success, or `Err` if an error occurred. ``` -------------------------------- ### Initialize CombinedTree for Testing Source: https://docs.rs/shardtree/0.6.1/i686-unknown-linux-gnu/src/shardtree/store/caching.rs.html Sets up a CombinedTree with two ShardTree instances, one backed by MemoryShardStore and the other by a CachingShardStore wrapping a MemoryShardStore, for testing purposes. ```rust { let mut lhs = MemoryShardStore::<_, u64>::empty(); let mut rhs = CachingShardStore::load(MemoryShardStore::empty()).unwrap(); let mut tree = CombinedTree::::new( ShardTree::<_, 4, 3>::new(&mut lhs, 100), ShardTree::<_, 4, 3>::new(&mut rhs, 100), ); ``` -------------------------------- ### ShardTree Get Mutable Store Reference Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/shardtree/struct.ShardTree.html Returns a mutable reference to the underlying ShardStore. ```rust pub fn store_mut(&mut self) -> &mut S ``` -------------------------------- ### Load and Verify Caching Shard Store Operations Source: https://docs.rs/shardtree/0.6.1/x86_64-apple-darwin/src/shardtree/store/caching.rs.html This snippet demonstrates loading a caching shard store and verifying a series of operations against it using a reference implementation. It iterates through predefined samples, applies operations, and asserts the correctness of the results and the final state of the stores. ```rust vec![ append_str("f", Retention::Ephemeral), witness(0, 1), ], vec![ append_str("g", Retention::Marked), Checkpoint(1), unmark(0), append_str("h", Retention::Ephemeral), witness(0, 0), ], vec![ append_str("i", Retention::Marked), Checkpoint(1), unmark(0), append_str("j", Retention::Ephemeral), witness(0, 0), ], vec![ append_str("i", Retention::Marked), append_str("j", Retention::Ephemeral), Checkpoint(1), append_str("k", Retention::Ephemeral), witness(0, 1), ], vec![ append_str("l", Retention::Marked), Checkpoint(1), Checkpoint(2), append_str("m", Retention::Ephemeral), Checkpoint(3), witness(0, 2), ], vec![ Checkpoint(1), append_str("n", Retention::Marked), witness(0, 1), ], vec![ append_str("a", Retention::Marked), Checkpoint(1), unmark(0), Checkpoint(2), append_str("b", Retention::Ephemeral), witness(0, 1), ], vec![ append_str("a", Retention::Marked), append_str("b", Retention::Ephemeral), unmark(0), Checkpoint(1), witness(0, 0), ], vec![ append_str("a", Retention::Marked), Checkpoint(1), unmark(0), Checkpoint(2), Rewind(1), append_str("b", Retention::Ephemeral), witness(0, 0), ], vec![ append_str("a", Retention::Marked), Checkpoint(1), Checkpoint(2), Rewind(1), append_str("a", Retention::Ephemeral), unmark(0), witness(0, 1), ], // Unreduced examples vec![ append_str("o", Retention::Ephemeral), append_str("p", Retention::Marked), append_str("q", Retention::Ephemeral), Checkpoint(1), unmark(1), witness(1, 1), ], vec![ append_str("r", Retention::Ephemeral), append_str("s", Retention::Ephemeral), append_str("t", Retention::Marked), Checkpoint(1), unmark(2), Checkpoint(2), witness(2, 2), ], vec![ append_str("u", Retention::Marked), append_str("v", Retention::Ephemeral), append_str("w", Retention::Ephemeral), Checkpoint(1), unmark(0), append_str("x", Retention::Ephemeral), Checkpoint(2), Checkpoint(3), witness(0, 3), ], ]; for (i, sample) in samples.iter().enumerate() { let mut lhs = MemoryShardStore::empty(); let mut rhs = CachingShardStore::load(MemoryShardStore::empty()).unwrap(); let tree = CombinedTree::new( ShardTree::<_, 4, 3>::new(&mut lhs, 100), ShardTree::<_, 4, 3>::new(&mut rhs, 100), ); let result = check_operations(tree, sample); assert!( matches!(result, Ok(())), "Reference/Test mismatch at index {}: {:?}", i, result ); check_equal(lhs, rhs); } ``` -------------------------------- ### ShardTree Append and Witness Operations Source: https://docs.rs/shardtree/0.6.1/x86_64-pc-windows-msvc/src/shardtree/store/caching.rs.html Demonstrates appending checkpoints and ephemeral data to a ShardTree and verifying the state using witness queries. This example showcases the tree's ability to manage different types of data and their impact on witness results. ```rust assert!(tree.append( String::from_u64(1), Checkpoint { id: 1, marking: Marking::None } )); assert_eq!( tree.witness(0.into(), 0), Some(vec![ String::from_u64(1), String::empty_root(1.into()), String::empty_root(2.into()), String::empty_root(3.into()) ]) ); assert!(tree.append( String::from_u64(2), Checkpoint { id: 2, marking: Marking::Marked } )); assert_eq!( tree.witness(Position::from(2), 0), Some(vec![ String::empty_root(0.into()), String::combine_all(1, &[0, 1]), String::empty_root(2.into()), String::empty_root(3.into()) ]) ); assert!(tree.append( String::from_u64(3), Checkpoint { id: 3, marking: Marking::None } )); assert_eq!( tree.witness(Position::from(2), 0), Some(vec![ String::from_u64(3), String::combine_all(1, &[0, 1]), String::empty_root(2.into()), String::empty_root(3.into()) ]) ); assert!(tree.append( String::from_u64(4), Checkpoint { id: 4, marking: Marking::None } )); assert_eq!( tree.witness(Position::from(2), 0), Some(vec![ String::from_u64(3), String::combine_all(1, &[0, 1]), String::combine_all(2, &[4]), String::empty_root(3.into()) ]) ); ``` -------------------------------- ### Retrieving a Specific Checkpoint Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/src/shardtree/store/memory.rs.html Gets a clone of a checkpoint associated with the given checkpoint ID, if it exists. ```rust fn get_checkpoint( &self, checkpoint_id: &Self::CheckpointId, ) -> Result, Self::Error> { Ok(self.checkpoints.get(checkpoint_id).cloned()) } ``` -------------------------------- ### Getting All Shard Root Addresses Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/src/shardtree/store/memory.rs.html Collects and returns the root addresses of all shards currently in the store. ```rust fn get_shard_roots(&self) -> Result, Self::Error> { Ok(self.shards.iter().map(|s| s.root_addr).collect()) } ``` -------------------------------- ### CachingShardStore Methods Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/src/shardtree/store/caching.rs.html Demonstrates various methods of the CachingShardStore for managing shards and checkpoints, interacting with an underlying cache. ```rust fn truncate_shards(&mut self, shard_index: u64) -> Result<(), Self::Error> { self.deferred_actions .push(Action::TruncateShards(shard_index)); self.cache.truncate_shards(shard_index) } fn get_cap(&self) -> Result, Self::Error> { self.cache.get_cap() } fn put_cap(&mut self, cap: PrunableTree) -> Result<(), Self::Error> { self.cache.put_cap(cap) } fn add_checkpoint( &mut self, checkpoint_id: Self::CheckpointId, checkpoint: Checkpoint, ) -> Result<(), Self::Error> { self.cache.add_checkpoint(checkpoint_id, checkpoint) } fn checkpoint_count(&self) -> Result { self.cache.checkpoint_count() } fn get_checkpoint( &self, checkpoint_id: &Self::CheckpointId, ) -> Result, Self::Error> { self.cache.get_checkpoint(checkpoint_id) } fn get_checkpoint_at_depth( &self, checkpoint_depth: usize, ) -> Result, Self::Error> { self.cache.get_checkpoint_at_depth(checkpoint_depth) } fn min_checkpoint_id(&self) -> Result, Self::Error> { self.cache.min_checkpoint_id() } fn max_checkpoint_id(&self) -> Result, Self::Error> { self.cache.max_checkpoint_id() } fn with_checkpoints(&mut self, limit: usize, callback: F) -> Result<(), Self::Error> where F: FnMut(&Self::CheckpointId, &Checkpoint) -> Result<(), Self::Error>, { self.cache.with_checkpoints(limit, callback) } fn for_each_checkpoint(&self, limit: usize, callback: F) -> Result<(), Self::Error> where F: FnMut(&Self::CheckpointId, &Checkpoint) -> Result<(), Self::Error>, { self.cache.for_each_checkpoint(limit, callback) } fn update_checkpoint_with( &mut self, checkpoint_id: &Self::CheckpointId, update: F, ) -> Result where F: Fn(&mut Checkpoint) -> Result<(), Self::Error>, { self.cache.update_checkpoint_with(checkpoint_id, update) } fn remove_checkpoint(&mut self, checkpoint_id: &Self::CheckpointId) -> Result<(), Self::Error> { self.deferred_actions .push(Action::RemoveCheckpoint(checkpoint_id.clone())); self.cache.remove_checkpoint(checkpoint_id) } fn truncate_checkpoints_retaining( &mut self, checkpoint_id: &Self::CheckpointId, ) -> Result<(), Self::Error> { self.deferred_actions .push(Action::TruncateCheckpointsRetaining(checkpoint_id.clone())); self.cache.truncate_checkpoints_retaining(checkpoint_id) } ``` -------------------------------- ### Initialize and Append Data to Combined Tree Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/src/shardtree/store/caching.rs.html Demonstrates initializing a CombinedTree with MemoryShardStore and CachingShardStore, appending various data types (Ephemeral, Marked, Checkpoint), and asserting the witness state. ```rust { let mut lhs = MemoryShardStore::empty(); let mut rhs = CachingShardStore::load(MemoryShardStore::empty()).unwrap(); let mut tree = CombinedTree::new( ShardTree::<_, 4, 3>::new(&mut lhs, 100), ShardTree::<_, 4, 3>::new(&mut rhs, 100), ); for i in 0..10 { assert!(tree.append(String::from_u64(i), Ephemeral)); } assert!(tree.append(String::from_u64(10), Marked)); assert!(tree.append( String::from_u64(11), Checkpoint { id: 0, marking: Marking::None } )); assert_eq!( tree.witness(Position::from(10), 0), Some(vec![ String::from_u64(11), String::combine_all(1, &[8, 9]), String::empty_root(2.into()), String::combine_all(3, &[0, 1, 2, 3, 4, 5, 6, 7]) ]) ); check_equal(lhs, rhs); } ``` -------------------------------- ### Get Marked Positions in LocatedPrunableTree Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/shardtree/type.LocatedPrunableTree.html Returns a set of all positions that are marked as leaves within the tree. ```rust pub fn marked_positions(&self) -> BTreeSet ``` -------------------------------- ### ShardTree Get Marked Leaf Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/shardtree/struct.ShardTree.html Retrieves the value of a marked leaf at a specific position, if it exists. ```rust pub fn get_marked_leaf( &self, position: Position, ) -> Result, ShardTreeError> ``` -------------------------------- ### pub fn empty(root_addr: Address) -> Self Source: https://docs.rs/shardtree/0.6.1/i686-unknown-linux-gnu/type.LocatedPrunableTree.html Constructs a new empty tree with its root at the provided address. ```APIDOC ## pub fn empty(root_addr: Address) -> Self ### Description Constructs a new empty tree with its root at the provided address. ### Parameters #### Path Parameters - **root_addr** (Address) - Required - The address for the root of the new tree. ``` -------------------------------- ### Get Value at Position in LocatedTree Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/shardtree/struct.LocatedTree.html Returns the value at the specified position within the LocatedTree, if it exists. ```rust pub fn value_at_position(&self, position: Position) -> Option<&V> ``` -------------------------------- ### Witness Generation with Pruned Subtrees Source: https://docs.rs/shardtree/0.6.1/x86_64-apple-darwin/src/shardtree/testing.rs.html Demonstrates how to construct a witness for a specific position in the tree, considering pruned subtrees. This is useful for verifying path elements and understanding how the tree handles incomplete data. ```rust let shard_root_level = Level::from(3); for idx in 0u64..4 { let root = if idx == 3 { "abcdefgh".to_string() } else { idx.to_string() }; tree.insert(Address::from_parts(shard_root_level, idx), root) .unwrap(); } // simulate discovery of a note tree.batch_insert( Position::from(24), ('a'..='h').map(|c| { ( c.to_string(), match c { 'c' => Retention::Marked, 'h' => Retention::Checkpoint { id: 3, marking: Marking::None, }, _ => Retention::Ephemeral, }, ) }), ) .unwrap(); // construct a witness for the note let witness = tree .witness_at_checkpoint_depth(Position::from(26), 0) .unwrap(); assert_eq!( witness.expect("can produce a witness").path_elems(), &[ "d", "ab", "efgh", "2", "01", "________________________________" ] ); ``` -------------------------------- ### Construct Empty MemoryShardStore Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/shardtree/store/memory/struct.MemoryShardStore.html Creates a new, empty instance of MemoryShardStore. This is the primary way to initialize the in-memory store. ```rust pub fn empty() -> Self ``` -------------------------------- ### Get a specific checkpoint from MemoryShardStore Source: https://docs.rs/shardtree/0.6.1/i686-unknown-linux-gnu/shardtree/store/memory/struct.MemoryShardStore.html Retrieves a checkpoint using its identifier. Returns None if the checkpoint does not exist. ```rust fn get_checkpoint( &self, checkpoint_id: &Self::CheckpointId, ) -> Result, Self::Error> ``` -------------------------------- ### CachingShardStore with Mixed Appends and Witness Query Source: https://docs.rs/shardtree/0.6.1/x86_64-pc-windows-msvc/src/shardtree/store/caching.rs.html Demonstrates appending a mix of Marked and Ephemeral data, followed by a Checkpoint, to a ShardTree managed by CachingShardStore. It then uses a witness query to verify the resulting state, highlighting how different data types are handled. ```rust let mut lhs = MemoryShardStore::empty(); let mut rhs = CachingShardStore::load(MemoryShardStore::empty()).unwrap(); let mut tree = CombinedTree::new( ShardTree::<_, 4, 3>::new(&mut lhs, 100), ShardTree::<_, 4, 3>::new(&mut rhs, 100), ); assert!(tree.append(String::from_u64(0), Marked)); assert!(tree.append(String::from_u64(1), Ephemeral)); assert!(tree.append(String::from_u64(2), Ephemeral)); assert!(tree.append(String::from_u64(3), Marked)); assert!(tree.append(String::from_u64(4), Marked)); assert!(tree.append(String::from_u64(5), Marked)); assert!(tree.append( String::from_u64(6), Checkpoint { id: 0, marking: Marking::None } )); assert_eq!( tree.witness(Position::from(5), 0), Some(vec![ String::from_u64(4), ``` -------------------------------- ### Get Tree State Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/src/shardtree/store.rs.html Returns the current tree state of the Checkpoint. The state can be either Empty or AtPosition. ```rust pub fn tree_state(&self) -> TreeState { self.tree_state } ``` -------------------------------- ### Getting the Maximum Checkpoint ID Source: https://docs.rs/shardtree/0.6.1/i686-pc-windows-msvc/src/shardtree/store/memory.rs.html Returns the largest checkpoint ID currently in the store, if any checkpoints exist. ```rust fn max_checkpoint_id(&self) -> Result, Self::Error> { Ok(self.checkpoints.keys().last().cloned()) } ```