drive/util/grove_operations/
mod.rs

1//! Grove Operations.
2//!
3//! Defines and implements in Drive functions pertinent to groveDB operations.
4//!
5
6/// Grove insert operation
7pub mod grove_insert;
8
9/// Grove insert operation into an empty tree
10pub mod grove_insert_empty_tree;
11
12/// Grove insert operation, but only if it doesn't already exist
13pub mod grove_insert_if_not_exists;
14
15/// Grove delete operation
16pub mod grove_delete;
17
18/// Fetch raw grove data
19pub mod grove_get_raw;
20
21/// Fetch raw grove data and match that is item
22pub mod grove_get_raw_item;
23
24/// Fetch raw grove data if it exists
25pub mod grove_get_raw_optional;
26
27/// Fetch u64 value from encoded variable vector in raw grove data
28pub mod grove_get_raw_value_u64_from_encoded_var_vec;
29
30/// Grove get operation
31pub mod grove_get;
32
33/// Serialized results from grove path query
34pub mod grove_get_path_query_serialized_results;
35
36/// Grove path query operation
37pub mod grove_get_path_query;
38
39/// Grove path query operation with optional return value
40pub mod grove_get_path_query_with_optional;
41
42/// Fetch raw data from grove path query with optional return value
43pub mod grove_get_raw_path_query_with_optional;
44
45/// Fetch raw data from grove path query
46pub mod grove_get_raw_path_query;
47
48/// Proved path query in grove
49pub mod grove_get_proved_path_query;
50
51/// V1 proved path query in grove (supports BulkAppendTree/CommitmentTree)
52pub mod grove_get_proved_path_query_v1;
53
54/// Get total count from a CommitmentTree
55pub mod grove_commitment_tree_count;
56
57/// Proved branch chunk query in grove
58pub mod grove_get_proved_branch_chunk_query;
59
60/// Proved trunk chunk query in grove
61pub mod grove_get_proved_trunk_chunk_query;
62
63/// Get total value from sum tree in grove
64pub mod grove_get_sum_tree_total_value;
65
66/// Check if raw data exists in grove
67pub mod grove_has_raw;
68
69/// Batch insert operation into empty tree
70pub mod batch_insert_empty_tree;
71
72/// Batch insert operation into empty sum tree
73pub mod batch_insert_empty_sum_tree;
74
75/// Batch insert operation into empty count tree (O(1) total count)
76pub mod batch_insert_empty_count_tree;
77
78/// Batch insert operation into empty count-sum tree (O(1) totals for both
79/// count and sum, no per-node aggregation). Used when a document type
80/// opts into BOTH `documentsCountable` and `documentsSummable` without
81/// any range-* flags.
82pub mod batch_insert_empty_count_sum_tree;
83
84/// Batch insert operation into empty provable count tree (range-countable)
85pub mod batch_insert_empty_provable_count_tree;
86
87/// Batch insert operation into empty provable sum tree (range-summable).
88/// Mirrors [`batch_insert_empty_provable_count_tree`] for the sum surface
89/// — commits per-node aggregated sums to every internal merk node so
90/// range queries land on an O(log n) `AggregateSumOnRange` proof.
91pub mod batch_insert_empty_provable_sum_tree;
92
93/// Batch insert operation into empty provable count-sum tree (combined
94/// count+sum surface). Used when an index opts into both `rangeCountable`
95/// and `rangeSummable` — a single tree carries both metrics per-node.
96/// Lights up once grovedb PR 670 ships `Element::ProvableCountSumTree`
97/// as a callable element variant.
98pub mod batch_insert_empty_provable_count_sum_tree;
99
100/// Batch insert operation into empty provable-count + provable-sum tree
101/// (PCPS, the fully-provable combined surface). Used when an index opts
102/// into BOTH `rangeCountable: true` AND `rangeSummable: true` —
103/// per-node counts AND per-node sums are committed to every internal
104/// merk node so range queries can answer
105/// `AggregateCountOnRange`/`AggregateSumOnRange` (and the combined
106/// variant once grovedb PR 670 ships) over the same tree.
107pub mod batch_insert_empty_provable_count_provable_sum_tree;
108
109/// Batch insert operation into an empty provable count-**indexed** tree
110/// (PCIT, grovedb PR 657). Same primary node shape as
111/// [`batch_insert_empty_provable_count_tree`], plus one ordered secondary
112/// Merk keyed by each child's aggregate count — the storage primitive behind
113/// `rankedCountable`.
114pub mod batch_insert_empty_provable_count_indexed_tree;
115
116/// Batch insert operation into an empty provable sum-**indexed** tree
117/// (PSIT, grovedb PR 657). Sum-axis mirror of
118/// [`batch_insert_empty_provable_count_indexed_tree`] — the storage primitive
119/// behind `rankedSummable` on a sum-only range layout.
120pub mod batch_insert_empty_provable_sum_indexed_tree;
121
122/// Batch insert operation into an empty provable-count + provable-sum
123/// **indexed** tree (PCPSIT, grovedb PR 657). Primary mirrors
124/// [`batch_insert_empty_provable_count_provable_sum_tree`]; the element
125/// carries a canonical TLV of 1..=3 ordered secondaries (Count / Sum / Avg).
126/// This is the arm every ranked index takes whose range layout is PCPS.
127pub mod batch_insert_empty_provable_count_provable_sum_indexed_tree;
128
129/// Batch insert operation into empty tree, but only if it doesn't already exist
130pub mod batch_insert_empty_tree_if_not_exists;
131
132/// Batch insert operation into empty tree, but only if it doesn't exist and check existing operations
133pub mod batch_insert_empty_tree_if_not_exists_check_existing_operations;
134
135/// Batch insert operation
136pub mod batch_insert;
137
138/// Batch replace operation
139pub mod batch_replace;
140
141/// Batch insert operation, but only if it doesn't already exist
142pub mod batch_insert_if_not_exists;
143
144/// Batch insert operation, but only if the value has changed
145pub mod batch_insert_if_changed_value;
146
147/// Batch delete operation
148pub mod batch_delete;
149
150/// Batch remove raw data operation
151pub mod batch_remove_raw;
152
153/// Batch delete operation up the tree while it's empty
154pub mod batch_delete_up_tree_while_empty;
155
156/// Batch refresh reference operation
157pub mod batch_refresh_reference;
158
159/// Apply grove operation
160pub mod grove_apply_operation;
161
162/// Apply batch grove operation
163pub mod grove_apply_batch;
164
165/// Apply batch grove operation with additional costs
166pub mod grove_apply_batch_with_add_costs;
167
168/// Apply partial batch grove operation
169pub mod grove_apply_partial_batch;
170
171/// Apply partial batch grove operation with additional costs
172pub mod grove_apply_partial_batch_with_add_costs;
173
174/// Get cost of grove batch operations
175pub mod grove_batch_operations_costs;
176
177/// Clear a subtree in grovedb
178pub mod grove_clear;
179
180/// Provides functionality to delete items in a path based on a query.
181pub mod batch_delete_items_in_path_query;
182
183/// Inserts an element if it does not exist and returns the existing element if it does.
184pub mod batch_insert_if_not_exists_return_existing_element;
185
186/// Inserts a sum item or adds to it if it already exists.
187pub mod batch_insert_sum_item_or_add_to_if_already_exists;
188
189/// Retrieves serialized or sum results from a path query in GroveDB.
190mod grove_get_path_query_serialized_or_sum_results;
191
192/// Executes a proved path query in GroveDB with an optional conditional query.
193pub mod grove_get_proved_path_query_with_conditional;
194
195/// Inserts an element if it does not exist and returns the existing element if it does in GroveDB.
196pub mod grove_insert_if_not_exists_return_existing_element;
197
198/// Batch inserts sum item if not already existing
199pub mod batch_insert_sum_item_if_not_exists;
200/// Moved items that are found in a path query to a new path.
201pub mod batch_move_items_in_path_query;
202
203/// Batch inserts item with sum item if not already existing
204pub mod batch_insert_item_with_sum_item_if_not_exists;
205/// Keeps the item, but inserts or adds to the sum item if it already exists
206pub mod batch_keep_item_insert_sum_item_or_add_to_if_already_exists;
207mod batch_move;
208/// Get the total value from a big sum tree
209pub mod grove_get_big_sum_tree_total_value;
210/// Get total value from sum tree in grove if it exists
211pub mod grove_get_optional_sum_tree_total_value;
212/// Fetch raw grove data if it exists, None otherwise
213pub mod grove_get_raw_optional_item;
214
215use grovedb_costs::CostContext;
216
217use grovedb::{EstimatedLayerInformation, MaybeTree, TreeType};
218
219use crate::error::Error;
220use crate::fees::op::LowLevelDriveOperation;
221use crate::fees::op::LowLevelDriveOperation::CalculatedCostOperation;
222
223use grovedb::Error as GroveError;
224
225use intmap::IntMap;
226
227/// Pushes an operation's `OperationCost` to `drive_operations` given its `CostContext`
228/// and returns the operation's return value.
229fn push_drive_operation_result<T>(
230    cost_context: CostContext<Result<T, GroveError>>,
231    drive_operations: &mut Vec<LowLevelDriveOperation>,
232) -> Result<T, Error> {
233    let CostContext { value, cost } = cost_context;
234    if !cost.is_nothing() {
235        drive_operations.push(CalculatedCostOperation(cost));
236    }
237    value.map_err(Error::from)
238}
239
240/// Pushes an operation's `OperationCost` to `drive_operations` given its `CostContext`
241/// if `drive_operations` is given. Returns the operation's return value.
242fn push_drive_operation_result_optional<T>(
243    cost_context: CostContext<Result<T, GroveError>>,
244    drive_operations: Option<&mut Vec<LowLevelDriveOperation>>,
245) -> Result<T, Error> {
246    let CostContext { value, cost } = cost_context;
247    if let Some(drive_operations) = drive_operations {
248        drive_operations.push(CalculatedCostOperation(cost));
249    }
250    value.map_err(Error::from)
251}
252/// Is subtree?
253pub type IsSubTree = bool;
254/// Is sum subtree?
255pub type IsSumSubTree = bool;
256/// Is sum tree?
257pub type IsSumTree = bool;
258
259/// Batch delete apply type
260#[derive(Debug, Copy, Clone)]
261pub enum BatchDeleteApplyType {
262    /// Stateless batch delete
263    StatelessBatchDelete {
264        /// Are we deleting in a sum tree
265        in_tree_type: TreeType,
266        /// What is the estimated key size
267        estimated_key_size: u32,
268        /// What is the estimated value size
269        estimated_value_size: u32,
270    },
271    /// Stateful batch delete
272    StatefulBatchDelete {
273        /// Are we known to be in a subtree and does this subtree have sums
274        is_known_to_be_subtree_with_sum: Option<MaybeTree>,
275    },
276}
277
278/// Batch move apply type
279#[derive(Debug, Copy, Clone)]
280pub enum BatchMoveApplyType {
281    /// Stateless batch move
282    StatelessBatchMove {
283        /// What type of tree are we in for the move
284        in_tree_type: TreeType,
285        /// Are we moving a trees?
286        tree_type: Option<TreeType>,
287        /// What is the estimated key size
288        estimated_key_size: u32,
289        /// What is the estimated value size
290        estimated_value_size: u32,
291        /// The flags length
292        flags_len: FlagsLen,
293    },
294    /// Stateful batch move
295    StatefulBatchMove {
296        /// Are we known to be in a subtree and does this subtree have sums
297        is_known_to_be_subtree_with_sum: Option<MaybeTree>,
298    },
299}
300
301#[derive(Clone)]
302/// Batch delete up tree apply type
303pub enum BatchDeleteUpTreeApplyType {
304    /// Stateless batch delete
305    StatelessBatchDelete {
306        /// The estimated layer info
307        estimated_layer_info: IntMap<u16, EstimatedLayerInformation>,
308    },
309    /// Stateful batch delete
310    StatefulBatchDelete {
311        /// Are we known to be in a subtree and does this subtree have sums
312        is_known_to_be_subtree_with_sum: Option<MaybeTree>,
313    },
314}
315
316/// batch insert tree apply type
317#[derive(Clone, Copy)]
318/// Batch insert tree apply type
319pub enum BatchInsertTreeApplyType {
320    /// Stateless batch insert tree
321    StatelessBatchInsertTree {
322        /// Does this tree use sums?
323        in_tree_type: TreeType,
324        /// Are we inserting in a sum tree
325        tree_type: TreeType,
326        /// The flags length
327        flags_len: FlagsLen,
328    },
329    /// Stateful batch insert tree
330    StatefulBatchInsertTree,
331}
332
333/// Represents the types for batch insert operations in a tree structure.
334impl BatchInsertTreeApplyType {
335    /// Converts the current `BatchInsertTreeApplyType` into a corresponding `DirectQueryType`.
336    ///
337    /// # Returns
338    ///
339    /// - A variant of `DirectQueryType::StatelessDirectQuery` if the current type is `BatchInsertTreeApplyType::StatelessBatchInsertTree`.
340    /// - `DirectQueryType::StatefulDirectQuery` if the current type is `BatchInsertTreeApplyType::StatefulBatchInsertTree`.
341    /// ```
342    pub(crate) fn to_direct_query_type(self) -> DirectQueryType {
343        match self {
344            BatchInsertTreeApplyType::StatelessBatchInsertTree {
345                in_tree_type,
346                tree_type,
347                flags_len,
348            } => DirectQueryType::StatelessDirectQuery {
349                in_tree_type,
350                query_target: QueryTarget::QueryTargetTree(flags_len, tree_type),
351            },
352            BatchInsertTreeApplyType::StatefulBatchInsertTree => {
353                DirectQueryType::StatefulDirectQuery
354            }
355        }
356    }
357}
358
359/// Batch insert apply type
360#[derive(Clone, Copy)]
361pub enum BatchInsertApplyType {
362    /// Stateless batch insert
363    StatelessBatchInsert {
364        /// Does this tree use sums?
365        in_tree_type: TreeType,
366        /// the type of Target (Tree or Value)
367        target: QueryTarget,
368    },
369    /// Stateful batch insert
370    StatefulBatchInsert,
371}
372
373impl BatchInsertApplyType {
374    /// Converts the current `BatchInsertApplyType` into a corresponding `DirectQueryType`.
375    ///
376    /// # Returns
377    ///
378    /// - A variant of `DirectQueryType::StatelessDirectQuery` if the current type is `BatchInsertApplyType::StatelessBatchInsert`.
379    /// - `DirectQueryType::StatefulDirectQuery` if the current type is `BatchInsertApplyType::StatefulBatchInsert`.
380    /// ```
381    // TODO: Not using
382    #[allow(dead_code)]
383    #[allow(clippy::wrong_self_convention)]
384    pub(crate) fn to_direct_query_type(&self) -> DirectQueryType {
385        match self {
386            BatchInsertApplyType::StatelessBatchInsert {
387                in_tree_type: in_tree_using_sums,
388                target,
389            } => DirectQueryType::StatelessDirectQuery {
390                in_tree_type: *in_tree_using_sums,
391                query_target: *target,
392            },
393            BatchInsertApplyType::StatefulBatchInsert => DirectQueryType::StatefulDirectQuery,
394        }
395    }
396}
397
398/// Flags length
399pub type FlagsLen = u32;
400
401/// query target
402#[derive(Clone, Copy)]
403/// Query target
404pub enum QueryTarget {
405    /// tree
406    QueryTargetTree(FlagsLen, TreeType),
407    /// value
408    QueryTargetValue(u32),
409}
410
411impl QueryTarget {
412    /// Length
413    pub(crate) fn len(&self) -> u32 {
414        match self {
415            QueryTarget::QueryTargetTree(flags_len, tree_type) => {
416                *flags_len + tree_type.inner_node_type().cost() + 3
417            }
418            QueryTarget::QueryTargetValue(len) => *len,
419        }
420    }
421}
422
423/// direct query type
424#[derive(Clone, Copy)]
425/// Direct query type
426pub enum DirectQueryType {
427    /// Stateless direct query
428    StatelessDirectQuery {
429        /// Does this tree use sums?
430        in_tree_type: TreeType,
431        /// the type of Target (Tree or Value)
432        query_target: QueryTarget,
433    },
434    /// Stateful direct query
435    StatefulDirectQuery,
436}
437
438impl From<DirectQueryType> for QueryType {
439    fn from(value: DirectQueryType) -> Self {
440        match value {
441            DirectQueryType::StatelessDirectQuery {
442                in_tree_type,
443                query_target,
444            } => QueryType::StatelessQuery {
445                in_tree_type,
446                query_target,
447                estimated_reference_sizes: vec![],
448            },
449            DirectQueryType::StatefulDirectQuery => QueryType::StatefulQuery,
450        }
451    }
452}
453
454impl DirectQueryType {
455    /// Converts the current `DirectQueryType` into a corresponding `QueryType`
456    /// while associating it with the given reference sizes.
457    ///
458    /// # Parameters
459    ///
460    /// * `reference_sizes`: A vector of `u32` values representing the reference sizes
461    ///   associated with the query.
462    ///
463    /// # Returns
464    ///
465    /// - A variant of `QueryType::StatelessQuery` with the provided reference sizes if
466    ///   the current type is `DirectQueryType::StatelessDirectQuery`.
467    /// - `QueryType::StatefulQuery` if the current type is `DirectQueryType::StatefulDirectQuery`.
468    ///
469    /// # Example
470    ///
471    /// ```ignore
472    /// let direct_query = DirectQueryType::StatelessDirectQuery {
473    ///     in_tree_using_sums: true,
474    ///     query_target: SomeTarget, // Replace with an actual target instance.
475    /// };
476    ///
477    /// let ref_sizes = vec![100, 200, 300];
478    /// let query_type = direct_query.add_reference_sizes(ref_sizes);
479    /// ```
480    #[allow(dead_code)]
481    #[deprecated(note = "This function is marked as unused.")]
482    #[allow(deprecated)]
483    pub(crate) fn add_reference_sizes(self, reference_sizes: Vec<u32>) -> QueryType {
484        match self {
485            DirectQueryType::StatelessDirectQuery {
486                in_tree_type: in_tree_using_sums,
487                query_target,
488            } => QueryType::StatelessQuery {
489                in_tree_type: in_tree_using_sums,
490                query_target,
491                estimated_reference_sizes: reference_sizes,
492            },
493            DirectQueryType::StatefulDirectQuery => QueryType::StatefulQuery,
494        }
495    }
496}
497
498/// Query type
499#[derive(Clone)]
500pub enum QueryType {
501    /// Stateless query
502    StatelessQuery {
503        /// Does this tree use sums?
504        in_tree_type: TreeType,
505        /// the type of Target (Tree or Value)
506        query_target: QueryTarget,
507        /// The estimated sizes of references
508        estimated_reference_sizes: Vec<u32>,
509    },
510    /// Stateful query
511    StatefulQuery,
512}
513
514impl From<BatchDeleteApplyType> for QueryType {
515    fn from(value: BatchDeleteApplyType) -> Self {
516        match value {
517            BatchDeleteApplyType::StatelessBatchDelete {
518                in_tree_type: is_sum_tree,
519                estimated_value_size,
520                ..
521            } => QueryType::StatelessQuery {
522                in_tree_type: is_sum_tree,
523                query_target: QueryTarget::QueryTargetValue(estimated_value_size),
524                estimated_reference_sizes: vec![],
525            },
526            BatchDeleteApplyType::StatefulBatchDelete { .. } => QueryType::StatefulQuery,
527        }
528    }
529}
530
531impl From<&BatchDeleteApplyType> for QueryType {
532    fn from(value: &BatchDeleteApplyType) -> Self {
533        match value {
534            BatchDeleteApplyType::StatelessBatchDelete {
535                in_tree_type: is_sum_tree,
536                estimated_value_size,
537                ..
538            } => QueryType::StatelessQuery {
539                in_tree_type: *is_sum_tree,
540                query_target: QueryTarget::QueryTargetValue(*estimated_value_size),
541                estimated_reference_sizes: vec![],
542            },
543            BatchDeleteApplyType::StatefulBatchDelete { .. } => QueryType::StatefulQuery,
544        }
545    }
546}
547
548impl From<BatchDeleteApplyType> for DirectQueryType {
549    fn from(value: BatchDeleteApplyType) -> Self {
550        match value {
551            BatchDeleteApplyType::StatelessBatchDelete {
552                in_tree_type: is_sum_tree,
553                estimated_value_size,
554                ..
555            } => DirectQueryType::StatelessDirectQuery {
556                in_tree_type: is_sum_tree,
557                query_target: QueryTarget::QueryTargetValue(estimated_value_size),
558            },
559            BatchDeleteApplyType::StatefulBatchDelete { .. } => {
560                DirectQueryType::StatefulDirectQuery
561            }
562        }
563    }
564}
565
566impl From<&BatchDeleteApplyType> for DirectQueryType {
567    fn from(value: &BatchDeleteApplyType) -> Self {
568        match value {
569            BatchDeleteApplyType::StatelessBatchDelete {
570                in_tree_type: is_sum_tree,
571                estimated_value_size,
572                ..
573            } => DirectQueryType::StatelessDirectQuery {
574                in_tree_type: *is_sum_tree,
575                query_target: QueryTarget::QueryTargetValue(*estimated_value_size),
576            },
577            BatchDeleteApplyType::StatefulBatchDelete { .. } => {
578                DirectQueryType::StatefulDirectQuery
579            }
580        }
581    }
582}
583
584/// Specifies which GroveDB instance to use for a query
585#[derive(Debug, Clone, Copy, PartialEq, Eq)]
586pub enum GroveDBToUse {
587    /// Use the current (main) GroveDB
588    Current,
589    /// Use the latest checkpoint
590    LatestCheckpoint,
591    /// Use a specific checkpoint at the given block height
592    Checkpoint(u64),
593}
drive/util/grove_operations/mod.rs

drive/util/grove_operations/
mod.rs
