1use 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
28fn 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
45fn describes_subtrees(layer: &EstimatedLayerInformation) -> bool {
49 layer.estimated_layer_sizes.layered_flags_size().is_ok()
50}
51
52fn 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
123fn 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
250fn 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#[derive(Clone, Debug, Default, PartialEq)]
282pub struct EstimatedLayers {
283 last_written: HashMap<KeyInfoPath, EstimatedLayerInformation>,
285 other_descriptions: HashMap<KeyInfoPath, Vec<EstimatedLayerInformation>>,
287}
288
289impl EstimatedLayers {
290 pub fn new() -> Self {
292 Self::default()
293 }
294
295 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 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 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 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 pub fn get(&self, path: &KeyInfoPath) -> Option<&EstimatedLayerInformation> {
371 self.last_written.get(path)
372 }
373
374 pub fn len(&self) -> usize {
376 self.last_written.len()
377 }
378
379 pub fn is_empty(&self) -> bool {
381 self.last_written.is_empty()
382 }
383
384 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 pub(crate) fn into_layers(self) -> HashMap<KeyInfoPath, EstimatedLayerInformation> {
404 self.last_written
405 }
406}
407
408pub(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
418pub(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 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 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 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 #[test]
507 fn should_keep_the_costliest_description_of_a_layer_in_every_order() {
508 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 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 let deeper_wide = at_level(4, AllItems(32, 64, None));
527 assert_eq!(kept_in_every_order(&[items, deeper_wide]), deeper_wide);
528
529 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 #[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 #[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 #[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 #[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 #[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 #[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 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 #[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}