Skip to main content

drive/util/
estimated_layers.rs

1//! The layer descriptions a cost estimate hands GroveDB ([`EstimatedLayers`]).
2//!
3//! GroveDB prices every operation at a layer's path with one description, and a layer's
4//! description gives the level the written key sits on, which sets how many ancestors an update
5//! propagates through. When two writes of one estimate reach keys at different depths of the
6//! same layer, the estimate must be priced at the deeper one, whichever write registers its
7//! description first; a write may be a nested estimator of an operation (a token mint describes
8//! the root for its supply and then for its balance) as well as an operation of its own. Which
9//! of two descriptions GroveDB prices dearer can change with the depth they are priced at, so an
10//! estimate that is resolved waits until all of them are known, and only then picks one
11//! ([`costliest_layer`]).
12
13use crate::error::drive::DriveError;
14use crate::error::Error;
15use crate::fees::op::DriveCost;
16use dpp::fee::Credits;
17use dpp::version::PlatformVersion;
18use grovedb::batch::KeyInfoPath;
19use grovedb::EstimatedLayerCount::EstimatedLevel;
20use grovedb::{
21    EstimatedLayerCount, EstimatedLayerInformation, EstimatedLayerSizes, EstimatedSumTrees,
22    TreeType,
23};
24use grovedb_merk::estimated_costs::average_case_costs::average_case_merk_propagate;
25use std::collections::hash_map::Entry;
26use std::collections::HashMap;
27
28/// What GroveDB's own estimator charges to carry a change through a layer described as `layer`
29/// (`average_case_merk_propagate`: the nodes it rewrites, the bytes it loads and replaces, the
30/// hashes), in credits at `platform_version`'s fees. Drive keeps no cost model of its own for a
31/// description: GroveDB prices it, and Drive only compares the prices.
32fn propagation_credits(
33    layer: &EstimatedLayerInformation,
34    platform_version: &PlatformVersion,
35) -> Result<Credits, Error> {
36    let propagation = average_case_merk_propagate(layer, &platform_version.drive.grove_version);
37    propagation
38        .value
39        .map_err(|error| Error::GroveDB(Box::new(error.into())))?;
40    propagation
41        .cost
42        .ephemeral_cost(&platform_version.fee_version)
43}
44
45/// Whether `layer` describes subtrees: GroveDB prices a tree operation at a layer's path (a
46/// subtree's new root key, a subtree's deletion) with the subtree sizes, and
47/// `layered_flags_size` is GroveDB's own check that a description carries them.
48fn describes_subtrees(layer: &EstimatedLayerInformation) -> bool {
49    layer.estimated_layer_sizes.layered_flags_size().is_ok()
50}
51
52/// The description a resolved estimate keeps for a layer its writes describe as `candidates`
53/// (distinct). GroveDB gives every operation at the layer's path this one description, so it
54/// must cover each of them: it is as deep as the deepest (`estimate_levels`, which gives a
55/// description by element count a depth too), as the depth sets how many nodes every use of the
56/// description touches, and at that depth it has the nodes GroveDB prices dearest
57/// ([`propagation_credits`]), each candidate being priced at every count that reaches that depth.
58/// The kept description can so combine one candidate's nodes with another's depth. When a write
59/// describes the layer as holding subtrees ([`describes_subtrees`]), the nodes are picked among
60/// the descriptions that do, as a tree operation there needs the subtree sizes. No two writes
61/// of a protocol version 15 batch disagree on whether a layer holds subtrees, so this choice
62/// changes nothing there; it keeps an estimate from failing should they. Two priced
63/// alike are told apart by their contents ([`layer_key`]). The pick is a maximum over the whole
64/// set, so it is the same whatever order the candidates were gathered in; picking between two
65/// at a time would not be, as a description priced alike or cheaper at a shallow depth can be
66/// the dearer at a deeper one.
67fn costliest_layer(
68    candidates: &[EstimatedLayerInformation],
69    platform_version: &PlatformVersion,
70) -> Result<EstimatedLayerInformation, Error> {
71    if let [only] = candidates {
72        return Ok(*only);
73    }
74    let no_candidate = || {
75        Error::Drive(DriveError::CorruptedCodeExecution(
76            "a layer is described by at least one candidate",
77        ))
78    };
79    let deepest = candidates
80        .iter()
81        .map(|candidate| candidate.estimated_layer_count.estimate_levels())
82        .max()
83        .ok_or_else(no_candidate)?;
84    let mut deepest_counts: Vec<EstimatedLayerCount> = vec![];
85    for count in candidates
86        .iter()
87        .map(|candidate| candidate.estimated_layer_count)
88        .filter(|count| count.estimate_levels() == deepest)
89    {
90        if !deepest_counts.contains(&count) {
91            deepest_counts.push(count);
92        }
93    }
94    let any_subtrees = candidates.iter().any(describes_subtrees);
95    let priced = candidates
96        .iter()
97        .filter(|candidate| !any_subtrees || describes_subtrees(candidate))
98        .flat_map(|candidate| {
99            deepest_counts
100                .iter()
101                .map(move |count| EstimatedLayerInformation {
102                    estimated_layer_count: *count,
103                    ..*candidate
104                })
105        })
106        .map(|at_depth| {
107            Ok((
108                propagation_credits(&at_depth, platform_version)?,
109                layer_key(&at_depth),
110                at_depth,
111            ))
112        })
113        .collect::<Result<Vec<_>, Error>>()?;
114    priced
115        .into_iter()
116        .max_by(|(price, key, _), (other_price, other_key, _)| {
117            (price, key).cmp(&(other_price, other_key))
118        })
119        .map(|(_, _, layer)| layer)
120        .ok_or_else(no_candidate)
121}
122
123/// A total order on descriptions, for two GroveDB prices alike: every field in turn, each enum
124/// by the position of its variant. The matches name every variant, so a description GroveDB adds
125/// cannot fall into an ordering by accident; and unlike a formatted string, the key does not
126/// change with a dependency's `Debug` output.
127fn layer_key(layer: &EstimatedLayerInformation) -> Vec<u64> {
128    let mut key = vec![];
129    tree_type_key(layer.tree_type, &mut key);
130    match layer.estimated_layer_count {
131        EstimatedLayerCount::PotentiallyAtMaxElements => key.push(0),
132        EstimatedLayerCount::ApproximateElements(count) => key.extend([1, count as u64]),
133        EstimatedLayerCount::EstimatedLevel(level, to_be_empty) => {
134            key.extend([2, level as u64, to_be_empty as u64])
135        }
136    }
137    let flags = |flags: Option<u32>| flags.map_or(0, |flags| flags as u64 + 1);
138    let sized = |key: &mut Vec<u64>, entry: Option<(u8, u32, Option<u32>, u8)>| match entry {
139        None => key.push(0),
140        Some((key_size, value_size, flags_size, weight)) => key.extend([
141            1,
142            key_size as u64,
143            value_size as u64,
144            flags(flags_size),
145            weight as u64,
146        ]),
147    };
148    match layer.estimated_layer_sizes {
149        EstimatedLayerSizes::AllSubtrees(key_size, sum_trees, flags_size) => {
150            key.extend([0, key_size as u64]);
151            sum_trees_key(sum_trees, &mut key);
152            key.push(flags(flags_size));
153        }
154        EstimatedLayerSizes::AllItems(key_size, value_size, flags_size) => {
155            key.extend([1, key_size as u64, value_size as u64, flags(flags_size)])
156        }
157        EstimatedLayerSizes::AllReference(key_size, value_size, flags_size) => {
158            key.extend([2, key_size as u64, value_size as u64, flags(flags_size)])
159        }
160        EstimatedLayerSizes::AllItemsWithSumItem(key_size, value_size, flags_size) => {
161            key.extend([3, key_size as u64, value_size as u64, flags(flags_size)])
162        }
163        EstimatedLayerSizes::AllReferencesWithSumItem(key_size, value_size, flags_size) => {
164            key.extend([4, key_size as u64, value_size as u64, flags(flags_size)])
165        }
166        EstimatedLayerSizes::Mix {
167            subtrees_size,
168            items_size,
169            references_size,
170            items_with_sum_item_size,
171            references_with_sum_item_size,
172        } => {
173            key.push(5);
174            match subtrees_size {
175                None => key.push(0),
176                Some((key_size, sum_trees, flags_size, weight)) => {
177                    key.extend([1, key_size as u64]);
178                    sum_trees_key(sum_trees, &mut key);
179                    key.extend([flags(flags_size), weight as u64]);
180                }
181            }
182            sized(&mut key, items_size);
183            sized(&mut key, references_size);
184            sized(&mut key, items_with_sum_item_size);
185            sized(&mut key, references_with_sum_item_size);
186        }
187    }
188    key
189}
190
191fn tree_type_key(tree_type: TreeType, key: &mut Vec<u64>) {
192    let (variant, parameter) = match tree_type {
193        TreeType::NormalTree => (0, 0),
194        TreeType::SumTree => (1, 0),
195        TreeType::BigSumTree => (2, 0),
196        TreeType::CountTree => (3, 0),
197        TreeType::CountSumTree => (4, 0),
198        TreeType::ProvableCountTree => (5, 0),
199        TreeType::ProvableCountSumTree => (6, 0),
200        TreeType::CommitmentTree(chunk_power) => (7, chunk_power),
201        TreeType::MmrTree => (8, 0),
202        TreeType::BulkAppendTree(chunk_power) => (9, chunk_power),
203        TreeType::DenseAppendOnlyFixedSizeTree(height) => (10, height),
204        TreeType::ProvableSumTree => (11, 0),
205        TreeType::ProvableCountProvableSumTree => (12, 0),
206        TreeType::ProvableSumIndexedTree => (13, 0),
207        TreeType::ProvableCountIndexedTree => (14, 0),
208        TreeType::ProvableCountProvableSumIndexedTree => (15, 0),
209        TreeType::PrivateDocumentStore(parameter) => (16, parameter),
210    };
211    key.extend([variant, parameter as u64]);
212}
213
214fn sum_trees_key(sum_trees: EstimatedSumTrees, key: &mut Vec<u64>) {
215    match sum_trees {
216        EstimatedSumTrees::NoSumTrees => key.push(0),
217        EstimatedSumTrees::SomeSumTrees {
218            sum_trees_weight,
219            big_sum_trees_weight,
220            count_trees_weight,
221            count_sum_trees_weight,
222            non_sum_trees_weight,
223            provable_sum_trees_weight,
224            provable_count_trees_weight,
225            provable_count_sum_trees_weight,
226            provable_count_provable_sum_trees_weight,
227        } => key.extend([
228            1,
229            sum_trees_weight as u64,
230            big_sum_trees_weight as u64,
231            count_trees_weight as u64,
232            count_sum_trees_weight as u64,
233            non_sum_trees_weight as u64,
234            provable_sum_trees_weight as u64,
235            provable_count_trees_weight as u64,
236            provable_count_sum_trees_weight as u64,
237            provable_count_provable_sum_trees_weight as u64,
238        ]),
239        EstimatedSumTrees::AllSumTrees => key.push(2),
240        EstimatedSumTrees::AllBigSumTrees => key.push(3),
241        EstimatedSumTrees::AllCountTrees => key.push(4),
242        EstimatedSumTrees::AllCountSumTrees => key.push(5),
243        EstimatedSumTrees::AllProvableSumTrees => key.push(6),
244        EstimatedSumTrees::AllProvableCountTrees => key.push(7),
245        EstimatedSumTrees::AllProvableCountSumTrees => key.push(8),
246        EstimatedSumTrees::AllProvableCountProvableSumTrees => key.push(9),
247    }
248}
249
250/// Records `layer` among the descriptions of `path` the estimate did not keep, each once.
251fn keep_other_description(
252    other_descriptions: &mut HashMap<KeyInfoPath, Vec<EstimatedLayerInformation>>,
253    path: &KeyInfoPath,
254    layer: EstimatedLayerInformation,
255) {
256    let others = other_descriptions.entry(path.clone()).or_default();
257    if !others.contains(&layer) {
258        others.push(layer);
259    }
260}
261
262/// The layer descriptions a cost estimate hands GroveDB, one per layer path.
263///
264/// Each write describes the layer at a path, and the description written last is the one
265/// GroveDB prices ([`EstimatedLayers::into_layers`]) and the one the estimate's own reads see
266/// ([`EstimatedLayers::get`]); [`EstimatedLayers::insert_if_absent`] writes only a path nothing
267/// described yet. Every estimate before protocol version 15 is priced that way.
268///
269/// For a path described more than one way, the estimate also keeps the descriptions it did not
270/// keep: those a later write replaced, and those `insert_if_absent` did not write. Only
271/// `apply_drive_operations` 2 (protocol version 15) resolves an estimate
272/// ([`EstimatedLayers::resolve`]): once the whole batch is described, each such path is
273/// described by the costliest of all its descriptions ([`costliest_layer`]), so the estimate does
274/// not depend on the order the writes came in, and no write is priced at a shallower depth than
275/// its own description.
276///
277/// A read during lowering (`stateless_delete_of_non_tree_for_costs`) sees the description
278/// written last, not the resolved one, and GroveDB prices what it reads at once. A reader so
279/// reads only layers its own operation described just before reading them; the read is then the
280/// same in every order.
281#[derive(Clone, Debug, Default, PartialEq)]
282pub struct EstimatedLayers {
283    /// The last description written for each path.
284    last_written: HashMap<KeyInfoPath, EstimatedLayerInformation>,
285    /// For a path described more than one way, every other description a write gave it.
286    other_descriptions: HashMap<KeyInfoPath, Vec<EstimatedLayerInformation>>,
287}
288
289impl EstimatedLayers {
290    /// An estimate describing no layer yet.
291    pub fn new() -> Self {
292        Self::default()
293    }
294
295    /// Describes the layer at `path` as `layer`, replacing the last description written for it.
296    pub fn insert(&mut self, path: KeyInfoPath, layer: EstimatedLayerInformation) {
297        match self.last_written.entry(path) {
298            Entry::Occupied(mut written) => {
299                let replaced = written.insert(layer);
300                if replaced != layer {
301                    keep_other_description(&mut self.other_descriptions, written.key(), replaced);
302                }
303            }
304            Entry::Vacant(unwritten) => {
305                unwritten.insert(layer);
306            }
307        }
308    }
309
310    /// Describes the layer at `path` as `layer` unless a description of it was written; the
311    /// estimate keeps `layer` among the path's other descriptions either way.
312    pub fn insert_if_absent(&mut self, path: KeyInfoPath, layer: EstimatedLayerInformation) {
313        match self.last_written.entry(path) {
314            Entry::Occupied(written) => {
315                if *written.get() != layer {
316                    keep_other_description(&mut self.other_descriptions, written.key(), layer);
317                }
318            }
319            Entry::Vacant(unwritten) => {
320                unwritten.insert(layer);
321            }
322        }
323    }
324
325    /// Keeps, for the described layer at `path`, its last description at `level` among the
326    /// path's other descriptions, so a resolved estimate describes the layer at least that deep.
327    /// Does nothing for a path no write described.
328    pub(crate) fn keep_at_level(&mut self, path: &KeyInfoPath, level: u32) {
329        if let Some(written) = self.last_written.get(path) {
330            let at_level = EstimatedLayerInformation {
331                estimated_layer_count: EstimatedLevel(level, false),
332                ..*written
333            };
334            if at_level != *written {
335                keep_other_description(&mut self.other_descriptions, path, at_level);
336            }
337        }
338    }
339
340    /// Describes the layer at `path` as `layer` unless the description written last for it is
341    /// at least as deep (`estimate_levels`, which gives a description by element count a depth
342    /// too: one that may hold the most elements a layer can is 32 levels deep, the worst case);
343    /// the estimate keeps the description it does not write among the path's other
344    /// descriptions either way.
345    pub(crate) fn insert_keeping_deeper(
346        &mut self,
347        path: KeyInfoPath,
348        layer: EstimatedLayerInformation,
349    ) {
350        match self.last_written.entry(path) {
351            Entry::Occupied(mut written) => {
352                let kept = if written.get().estimated_layer_count.estimate_levels()
353                    >= layer.estimated_layer_count.estimate_levels()
354                {
355                    layer
356                } else {
357                    written.insert(layer)
358                };
359                if kept != *written.get() {
360                    keep_other_description(&mut self.other_descriptions, written.key(), kept);
361                }
362            }
363            Entry::Vacant(unwritten) => {
364                unwritten.insert(layer);
365            }
366        }
367    }
368
369    /// The last description written for the layer at `path`.
370    pub fn get(&self, path: &KeyInfoPath) -> Option<&EstimatedLayerInformation> {
371        self.last_written.get(path)
372    }
373
374    /// How many paths are described.
375    pub fn len(&self) -> usize {
376        self.last_written.len()
377    }
378
379    /// Whether no path is described.
380    pub fn is_empty(&self) -> bool {
381        self.last_written.is_empty()
382    }
383
384    /// The estimate with each path described more than one way described by the costliest of
385    /// its descriptions ([`costliest_layer`]); a path described one way keeps its description.
386    pub(crate) fn resolve(mut self, platform_version: &PlatformVersion) -> Result<Self, Error> {
387        for (path, mut descriptions) in std::mem::take(&mut self.other_descriptions) {
388            let written = self.last_written.get_mut(&path).ok_or(Error::Drive(
389                DriveError::CorruptedCodeExecution(
390                    "a path with other descriptions has a description written",
391                ),
392            ))?;
393            if !descriptions.contains(written) {
394                descriptions.push(*written);
395            }
396            *written = costliest_layer(&descriptions, platform_version)?;
397        }
398        Ok(self)
399    }
400
401    /// The descriptions GroveDB prices the estimate with: the last written for each path, or,
402    /// once [`EstimatedLayers::resolve`]d, the costliest.
403    pub(crate) fn into_layers(self) -> HashMap<KeyInfoPath, EstimatedLayerInformation> {
404        self.last_written
405    }
406}
407
408/// Describes the layer at `path` as `layer`, unless the estimate already describes it at least as
409/// deep ([`EstimatedLayers::insert_keeping_deeper`]).
410pub(crate) fn insert_estimated_layer_keeping_deeper(
411    estimated_costs_only_with_layer_info: &mut EstimatedLayers,
412    path: KeyInfoPath,
413    layer: EstimatedLayerInformation,
414) {
415    estimated_costs_only_with_layer_info.insert_keeping_deeper(path, layer);
416}
417
418/// Runs `register`, an estimation that overwrites the descriptions of the layers at `paths`, and
419/// puts back each description it replaced that was deeper.
420pub(crate) fn register_keeping_deeper_estimated_layers(
421    estimated_costs_only_with_layer_info: &mut EstimatedLayers,
422    paths: &[KeyInfoPath],
423    register: impl FnOnce(&mut EstimatedLayers),
424) {
425    let before: Vec<(KeyInfoPath, EstimatedLayerInformation)> = paths
426        .iter()
427        .filter_map(|path| {
428            estimated_costs_only_with_layer_info
429                .get(path)
430                .map(|layer| (path.clone(), *layer))
431        })
432        .collect();
433    register(estimated_costs_only_with_layer_info);
434    for (path, layer) in before {
435        insert_estimated_layer_keeping_deeper(estimated_costs_only_with_layer_info, path, layer);
436    }
437}
438
439#[cfg(test)]
440mod tests {
441    use super::*;
442    use grovedb::EstimatedLayerCount::{ApproximateElements, PotentiallyAtMaxElements};
443    use grovedb::EstimatedLayerSizes::{AllItems, AllReference, AllSubtrees, Mix};
444    use grovedb::EstimatedSumTrees::{AllBigSumTrees, NoSumTrees};
445    use grovedb::TreeType;
446
447    /// Every order of `layers`, each from an operation of its own.
448    fn orders(layers: &[EstimatedLayerInformation]) -> Vec<Vec<EstimatedLayerInformation>> {
449        if layers.len() <= 1 {
450            return vec![layers.to_vec()];
451        }
452        let mut all = vec![];
453        for (index, layer) in layers.iter().enumerate() {
454            let mut rest = layers.to_vec();
455            rest.remove(index);
456            for mut order in orders(&rest) {
457                order.insert(0, *layer);
458                all.push(order);
459            }
460        }
461        all
462    }
463
464    /// The description a resolved estimate keeps for a layer its writes describe as `layers`,
465    /// in that order.
466    fn kept(layers: &[EstimatedLayerInformation]) -> EstimatedLayerInformation {
467        let path = KeyInfoPath::from_known_path([[1u8].as_slice()]);
468        let mut estimate = EstimatedLayers::new();
469        for layer in layers {
470            estimate.insert(path.clone(), *layer);
471        }
472        *estimate
473            .resolve(PlatformVersion::latest())
474            .expect("expected to pick a description")
475            .get(&path)
476            .expect("expected the layer to be described")
477    }
478
479    /// The description `layers` give a layer, the same in every order they come in.
480    fn kept_in_every_order(layers: &[EstimatedLayerInformation]) -> EstimatedLayerInformation {
481        let mut every_order = orders(layers).into_iter();
482        let kept_first = kept(&every_order.next().expect("expected an order"));
483        for order in every_order {
484            assert_eq!(kept(&order), kept_first, "order {order:?}");
485        }
486        kept_first
487    }
488
489    fn credits(layer: &EstimatedLayerInformation) -> Credits {
490        propagation_credits(layer, PlatformVersion::latest()).expect("expected a price")
491    }
492
493    fn at_level(
494        level: u32,
495        estimated_layer_sizes: EstimatedLayerSizes,
496    ) -> EstimatedLayerInformation {
497        EstimatedLayerInformation {
498            tree_type: TreeType::NormalTree,
499            estimated_layer_count: EstimatedLevel(level, false),
500            estimated_layer_sizes,
501        }
502    }
503
504    /// The deepest depth, the nodes GroveDB's propagation estimate prices dearest at that depth,
505    /// then, for two it prices alike, a fixed choice; the same in every order.
506    #[test]
507    fn should_keep_the_costliest_description_of_a_layer_in_every_order() {
508        // Items under 32-byte keys cost more to carry a change through than items of the same
509        // size under 1-byte keys.
510        let items = at_level(3, AllItems(32, 8, None));
511        let narrow_items = at_level(3, AllItems(1, 8, None));
512        assert!(credits(&items) > credits(&narrow_items));
513        assert_eq!(kept_in_every_order(&[items, narrow_items]), items);
514
515        // A deeper description of narrower nodes, priced below the shallower one: the batch
516        // keeps the deeper depth and the dearer nodes, a description neither write gave, so
517        // neither write is priced below its own description.
518        let deeper_narrow = at_level(4, AllItems(1, 1, None));
519        assert!(credits(&deeper_narrow) < credits(&items));
520        let deeper_items = at_level(4, AllItems(32, 8, None));
521        assert_eq!(kept_in_every_order(&[items, deeper_narrow]), deeper_items);
522        assert!(credits(&deeper_items) >= credits(&items));
523        assert!(credits(&deeper_items) >= credits(&deeper_narrow));
524
525        // The deeper one's nodes are kept when they are the dearer at its depth.
526        let deeper_wide = at_level(4, AllItems(32, 64, None));
527        assert_eq!(kept_in_every_order(&[items, deeper_wide]), deeper_wide);
528
529        // Two different descriptions GroveDB prices alike.
530        let references = at_level(3, AllReference(32, 8, None));
531        assert_ne!(items, references);
532        assert_eq!(credits(&items), credits(&references));
533        kept_in_every_order(&[items, references]);
534    }
535
536    /// At level 0 GroveDB prices every description alike, so a choice between two level 0
537    /// descriptions made before a deeper one arrives would rest on the tie-break (which keeps
538    /// the references), and could keep the nodes that are the cheaper at the deeper depth. The
539    /// batch keeps all three until the deepest depth is known, then the nodes dearest there, in
540    /// every order.
541    #[test]
542    fn should_pick_among_shallow_descriptions_at_the_deepest_depth() {
543        let items = at_level(0, AllItems(32, 8, None));
544        let references = at_level(0, AllReference(1, 8, None));
545        let deep_narrow = at_level(4, AllItems(1, 1, None));
546        assert_eq!(credits(&items), credits(&references));
547        let items_at_4 = at_level(4, AllItems(32, 8, None));
548        assert!(credits(&items_at_4) > credits(&at_level(4, AllReference(1, 8, None))));
549        assert!(credits(&items_at_4) > credits(&deep_narrow));
550        assert_eq!(
551            kept_in_every_order(&[items, references, deep_narrow]),
552            items_at_4
553        );
554    }
555
556    /// Items of 8 bytes under 32-byte keys cost more to carry a change through than big sum
557    /// subtrees under the same keys (GroveDB counts the item's two stored hashes), but a write
558    /// that describes the layer as holding subtrees keeps a description of subtrees: GroveDB
559    /// prices a tree operation there with the subtree sizes, and refuses a description of items
560    /// alone. The depth is still the deepest any write gives, and a `Mix` holding subtrees is a
561    /// description of subtrees.
562    #[test]
563    fn should_describe_a_layer_holding_subtrees_with_subtrees() {
564        let items = at_level(3, AllItems(32, 8, None));
565        let subtrees = at_level(2, AllSubtrees(32, AllBigSumTrees, None));
566        let subtrees_at_3 = at_level(3, AllSubtrees(32, AllBigSumTrees, None));
567        assert!(credits(&items) > credits(&subtrees_at_3));
568        assert_eq!(kept_in_every_order(&[items, subtrees]), subtrees_at_3);
569
570        let mix = at_level(
571            1,
572            Mix {
573                subtrees_size: Some((1, NoSumTrees, None, 1)),
574                items_size: Some((1, 8, None, 1)),
575                references_size: None,
576                items_with_sum_item_size: None,
577                references_with_sum_item_size: None,
578            },
579        );
580        let mix_at_3 = EstimatedLayerInformation {
581            estimated_layer_count: EstimatedLevel(3, false),
582            ..mix
583        };
584        assert_eq!(kept_in_every_order(&[items, mix]), mix_at_3);
585    }
586
587    /// Two descriptions of one depth with different counts: each candidate is priced at each
588    /// count, and the batch keeps the dearest, in either order.
589    #[test]
590    fn should_price_every_candidate_at_every_count_of_the_deepest_depth() {
591        let items = at_level(2, AllItems(32, 8, None));
592        let by_count = EstimatedLayerInformation {
593            estimated_layer_count: ApproximateElements(3),
594            ..at_level(2, AllItems(1, 8, None))
595        };
596        assert_eq!(by_count.estimated_layer_count.estimate_levels(), 2);
597        let kept = kept_in_every_order(&[items, by_count]);
598        assert_eq!(kept.estimated_layer_sizes, AllItems(32, 8, None));
599        assert!(credits(&kept) >= credits(&items));
600        assert!(credits(&kept) >= credits(&by_count));
601    }
602
603    /// A layer every write describes alike is kept as described.
604    #[test]
605    fn should_keep_a_layer_described_alike_as_it_is() {
606        let items = at_level(3, AllItems(32, 8, None));
607        assert_eq!(kept(&[items, items, items]), items);
608    }
609
610    /// GroveDB prices the description written last unless the estimate is resolved, as every
611    /// estimate before `apply_drive_operations` 2 is priced; `insert_if_absent` writes only an
612    /// undescribed path. Resolving picks the costliest of every description the writes gave,
613    /// the one `insert_if_absent` did not write included.
614    #[test]
615    fn should_keep_the_last_description_written_until_resolved() {
616        let path = KeyInfoPath::from_known_path([[1u8].as_slice()]);
617        let deep = at_level(3, AllItems(32, 8, None));
618        let shallow = at_level(1, AllItems(1, 8, None));
619        let mut estimate = EstimatedLayers::new();
620        estimate.insert(path.clone(), shallow);
621        estimate.insert_if_absent(path.clone(), deep);
622        assert_eq!(estimate.get(&path), Some(&shallow));
623        assert_eq!(
624            estimate.clone().into_layers(),
625            HashMap::from([(path.clone(), shallow)])
626        );
627        assert_eq!(
628            estimate
629                .resolve(PlatformVersion::latest())
630                .expect("expected to resolve")
631                .into_layers(),
632            HashMap::from([(path, deep)])
633        );
634    }
635
636    /// A described layer kept at a deeper level is resolved at that level, with the nodes of
637    /// its description; an undescribed layer stays undescribed.
638    #[test]
639    fn should_resolve_a_layer_kept_at_a_level_at_least_that_deep() {
640        let path = KeyInfoPath::from_known_path([[1u8].as_slice()]);
641        let undescribed = KeyInfoPath::from_known_path([[2u8].as_slice()]);
642        let mut estimate = EstimatedLayers::new();
643        estimate.insert(path.clone(), at_level(3, AllSubtrees(1, NoSumTrees, None)));
644        estimate.keep_at_level(&path, 4);
645        estimate.keep_at_level(&undescribed, 4);
646        let resolved = estimate
647            .resolve(PlatformVersion::latest())
648            .expect("expected to resolve");
649        assert_eq!(
650            resolved.get(&path),
651            Some(&at_level(4, AllSubtrees(1, NoSumTrees, None)))
652        );
653        assert_eq!(resolved.get(&undescribed), None);
654    }
655
656    fn layer(level: u32) -> EstimatedLayerInformation {
657        at_level(level, AllSubtrees(1, NoSumTrees, None))
658    }
659
660    fn level_at(estimation: &EstimatedLayers, path: &KeyInfoPath) -> Option<u32> {
661        estimation
662            .get(path)
663            .and_then(|layer| match layer.estimated_layer_count {
664                EstimatedLevel(level, _) => Some(level),
665                _ => None,
666            })
667    }
668
669    #[test]
670    fn should_insert_unless_a_deeper_or_equal_level_is_described() {
671        let path = KeyInfoPath::from_known_path([[1u8].as_slice()]);
672        let mut estimation = EstimatedLayers::new();
673        insert_estimated_layer_keeping_deeper(&mut estimation, path.clone(), layer(1));
674        assert_eq!(level_at(&estimation, &path), Some(1));
675        insert_estimated_layer_keeping_deeper(&mut estimation, path.clone(), layer(2));
676        assert_eq!(level_at(&estimation, &path), Some(2));
677        insert_estimated_layer_keeping_deeper(&mut estimation, path.clone(), layer(1));
678        assert_eq!(level_at(&estimation, &path), Some(2));
679        // A description by element count has a depth too: one that may hold the most elements
680        // a layer can (32 levels, the worst case) is kept over a shallower level, and one of a
681        // few elements gives way to a deeper level.
682        let at_max = EstimatedLayerInformation {
683            estimated_layer_count: PotentiallyAtMaxElements,
684            ..layer(0)
685        };
686        estimation.insert(path.clone(), at_max);
687        insert_estimated_layer_keeping_deeper(&mut estimation, path.clone(), layer(5));
688        assert_eq!(estimation.get(&path), Some(&at_max));
689        estimation.insert(
690            path.clone(),
691            EstimatedLayerInformation {
692                estimated_layer_count: ApproximateElements(3),
693                ..layer(0)
694            },
695        );
696        insert_estimated_layer_keeping_deeper(&mut estimation, path.clone(), layer(5));
697        assert_eq!(level_at(&estimation, &path), Some(5));
698    }
699
700    /// `insert_estimated_layer_keeping_deeper` writes the deeper of two descriptions and keeps
701    /// the other: a shallower description of wider nodes and a deeper one of narrower nodes
702    /// resolve to the wider nodes at the deeper depth, in either order.
703    #[test]
704    fn should_resolve_with_the_nodes_of_a_description_not_kept_deeper() {
705        let path = KeyInfoPath::from_known_path([[1u8].as_slice()]);
706        let shallow_wide = at_level(3, AllItems(32, 8, None));
707        let deep_narrow = at_level(4, AllItems(1, 1, None));
708        let deep_wide = at_level(4, AllItems(32, 8, None));
709        assert!(credits(&deep_wide) > credits(&deep_narrow));
710        for order in orders(&[shallow_wide, deep_narrow]) {
711            let mut estimation = EstimatedLayers::new();
712            for description in &order {
713                insert_estimated_layer_keeping_deeper(&mut estimation, path.clone(), *description);
714            }
715            assert_eq!(estimation.get(&path), Some(&deep_narrow), "order {order:?}");
716            let resolved = estimation
717                .resolve(PlatformVersion::latest())
718                .expect("expected to resolve");
719            assert_eq!(resolved.get(&path), Some(&deep_wide), "order {order:?}");
720        }
721    }
722
723    #[test]
724    fn should_put_back_a_deeper_level_an_estimation_overwrote() {
725        let deep = KeyInfoPath::from_known_path([[1u8].as_slice()]);
726        let shallow = KeyInfoPath::from_known_path([[2u8].as_slice()]);
727        let mut estimation = EstimatedLayers::new();
728        estimation.insert(deep.clone(), layer(2));
729        estimation.insert(shallow.clone(), layer(0));
730        register_keeping_deeper_estimated_layers(
731            &mut estimation,
732            &[deep.clone(), shallow.clone()],
733            |estimation| {
734                estimation.insert(deep.clone(), layer(1));
735                estimation.insert(shallow.clone(), layer(1));
736            },
737        );
738        assert_eq!(level_at(&estimation, &deep), Some(2));
739        assert_eq!(level_at(&estimation, &shallow), Some(1));
740    }
741}