tycho_types/dict/
aug.rs

1use std::borrow::Borrow;
2use std::collections::BTreeMap;
3use std::marker::PhantomData;
4
5use super::raw::*;
6use super::typed::*;
7use super::{
8    DictKey, LoadDictKey, SearchByExtra, SetMode, StoreDictKey, aug_dict_find_by_extra,
9    aug_dict_insert, aug_dict_merge_siblings, aug_dict_modify_from_sorted_iter,
10    aug_dict_remove_owned, build_aug_dict_from_sorted_iter, read_label,
11};
12use crate::cell::*;
13use crate::error::*;
14use crate::util::*;
15
16/// A trait for values that can be used as augmented values in an augmented dictionary.
17pub trait AugDictExtra: Default {
18    /// Merges two augmented values.
19    ///
20    /// # Parameters
21    /// - `left` - The left branch (should start with `extra`).
22    /// - `right` - The right branch (should start with `extra`).
23    /// - `b` - The builder to store the result (only `extra`).
24    /// - `cx` - The cell context.
25    fn comp_add(
26        left: &mut CellSlice,
27        right: &mut CellSlice,
28        b: &mut CellBuilder,
29        cx: &dyn CellContext,
30    ) -> Result<(), Error>;
31}
32
33/// Typed augmented dictionary with fixed length keys.
34///
35/// # TLB scheme
36///
37/// ```text
38/// ahm_edge#_ {n:#} {V:Type} {A:Type} {l:#} {m:#}
39///   label:(HmLabel ~l n) {n = (~m) + l}
40///   node:(HashmapAugNode m V A) = HashmapAug n V A;
41///
42/// ahmn_leaf#_ {V:Type} {A:Type} extra:A value:V = HashmapAugNode 0 V A;
43/// ahmn_fork#_ {n:#} {V:Type} {A:Type} left:^(HashmapAug n V A)
44///   right:^(HashmapAug n V A) extra:A = HashmapAugNode (n + 1) V A;
45///
46/// ahme_empty$0 {n:#} {V:Type} {A:Type} extra:A = HashmapAugE n V A;
47/// ahme_root$1 {n:#} {V:Type} {A:Type} root:^(HashmapAug n V A) extra:A = HashmapAugE n V A;
48/// ```
49pub struct AugDict<K, A, V> {
50    dict: Dict<K, (A, V)>,
51    extra: A,
52    _key: PhantomData<K>,
53    _value: PhantomData<(A, V)>,
54}
55
56impl<K, A: ExactSize, V> ExactSize for AugDict<K, A, V> {
57    #[inline]
58    fn exact_size(&self) -> Size {
59        self.dict.exact_size() + self.extra.exact_size()
60    }
61}
62
63impl<'a, K, A: Load<'a>, V> Load<'a> for AugDict<K, A, V> {
64    #[inline]
65    fn load_from(slice: &mut CellSlice<'a>) -> Result<Self, Error> {
66        Ok(Self {
67            dict: ok!(Dict::load_from(slice)),
68            extra: ok!(A::load_from(slice)),
69            _key: PhantomData,
70            _value: PhantomData,
71        })
72    }
73}
74
75impl<K, A: Store, V> Store for AugDict<K, A, V> {
76    #[inline]
77    fn store_into(
78        &self,
79        builder: &mut CellBuilder,
80        context: &dyn CellContext,
81    ) -> Result<(), Error> {
82        ok!(self.dict.store_into(builder, context));
83        self.extra.store_into(builder, context)
84    }
85}
86
87impl<K, A: Default, V> Default for AugDict<K, A, V> {
88    #[inline]
89    fn default() -> Self {
90        Self::new()
91    }
92}
93
94impl<K, A: Clone, V> Clone for AugDict<K, A, V> {
95    fn clone(&self) -> Self {
96        Self {
97            dict: self.dict.clone(),
98            extra: self.extra.clone(),
99            _key: PhantomData,
100            _value: PhantomData,
101        }
102    }
103}
104
105impl<K, A: Eq, V> Eq for AugDict<K, A, V> {}
106
107impl<K, A: PartialEq, V> PartialEq for AugDict<K, A, V> {
108    fn eq(&self, other: &Self) -> bool {
109        self.dict.eq(&other.dict) && self.extra.eq(&other.extra)
110    }
111}
112
113impl<K, A: std::fmt::Debug, V> std::fmt::Debug for AugDict<K, A, V> {
114    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
115        debug_struct_field2_finish(f, "AugDict", "dict", &self.dict, "extra", &self.extra)
116    }
117}
118
119impl<K, A: Default, V> AugDict<K, A, V> {
120    /// Creates an empty dictionary
121    pub fn new() -> Self {
122        Self {
123            dict: Dict::new(),
124            extra: A::default(),
125            _key: PhantomData,
126            _value: PhantomData,
127        }
128    }
129
130    /// Manually constructs the dictionaty from parts.
131    pub const fn from_parts(dict: Dict<K, (A, V)>, extra: A) -> Self {
132        Self {
133            dict,
134            extra,
135            _key: PhantomData,
136            _value: PhantomData,
137        }
138    }
139
140    /// Returns an underlying dictionary and the extra value.
141    pub fn into_parts(self) -> (Dict<K, (A, V)>, A) {
142        (self.dict, self.extra)
143    }
144
145    /// Converts into a dictionary with an equivalent value type.
146    #[inline]
147    pub fn cast_into<Q, T>(self) -> AugDict<Q, A, T>
148    where
149        Q: EquivalentRepr<K>,
150        (A, T): EquivalentRepr<(A, V)>,
151    {
152        AugDict {
153            dict: self.dict.cast_into(),
154            extra: self.extra,
155            _key: PhantomData,
156            _value: PhantomData,
157        }
158    }
159}
160
161impl<K: DictKey, A, V> AugDict<K, A, V> {
162    /// Loads a non-empty dictionary from a root cell.
163    pub fn load_from_root_ext<'a>(
164        slice: &mut CellSlice<'a>,
165        context: &dyn CellContext,
166    ) -> Result<Self, Error>
167    where
168        A: Load<'a>,
169        V: Load<'a>,
170    {
171        let (extra, root) = ok!(load_from_root::<A, V>(slice, K::BITS, context));
172
173        Ok(Self {
174            dict: Dict::from(Some(root)),
175            extra,
176            _key: PhantomData,
177            _value: PhantomData,
178        })
179    }
180}
181
182impl<K, A, V> AugDict<K, A, V>
183where
184    K: DictKey,
185    for<'a> A: Default + Load<'a>,
186{
187    /// Recomputes the root extra value.
188    pub fn update_root_extra(&mut self) -> Result<(), Error> {
189        self.extra = match &self.dict.root {
190            Some(root) => {
191                let slice = &mut ok!(root.as_slice());
192                let prefix = ok!(read_label(slice, K::BITS));
193                if prefix.size_bits() != K::BITS {
194                    ok!(slice.skip_first(0, 2));
195                }
196                ok!(A::load_from(slice))
197            }
198            None => A::default(),
199        };
200        Ok(())
201    }
202}
203
204fn load_from_root<'a, A, V>(
205    slice: &mut CellSlice<'a>,
206    key_bit_len: u16,
207    context: &dyn CellContext,
208) -> Result<(A, Cell), Error>
209where
210    A: Load<'a>,
211    V: Load<'a>,
212{
213    let root = *slice;
214
215    let label = ok!(read_label(slice, key_bit_len));
216    let extra = if label.size_bits() != key_bit_len {
217        ok!(slice.skip_first(0, 2));
218        ok!(A::load_from(slice))
219    } else {
220        let extra = ok!(A::load_from(slice));
221        ok!(V::load_from(slice));
222        extra
223    };
224
225    let root_bits = root.size_bits() - slice.size_bits();
226    let root_refs = root.size_refs() - slice.size_refs();
227
228    let mut b = CellBuilder::new();
229    ok!(b.store_slice(root.get_prefix(root_bits, root_refs)));
230    match b.build_ext(context) {
231        Ok(cell) => Ok((extra, cell)),
232        Err(e) => Err(e),
233    }
234}
235
236impl<K, A, V> AugDict<K, A, V> {
237    /// Returns `true` if the dictionary contains no elements.
238    pub const fn is_empty(&self) -> bool {
239        self.dict.is_empty()
240    }
241
242    /// Returns the underlying dictionary.
243    #[inline]
244    pub const fn dict(&self) -> &Dict<K, (A, V)> {
245        &self.dict
246    }
247
248    /// Returns the root augmented value.
249    #[inline]
250    pub const fn root_extra(&self) -> &A {
251        &self.extra
252    }
253}
254
255impl<K, A, V> AugDict<K, A, V>
256where
257    K: StoreDictKey,
258{
259    /// Returns `true` if the dictionary contains a value for the specified key.
260    pub fn contains_key<Q>(&self, key: Q) -> Result<bool, Error>
261    where
262        Q: Borrow<K>,
263    {
264        self.dict.contains_key(key)
265    }
266}
267
268impl<K, A, V> AugDict<K, A, V>
269where
270    K: StoreDictKey,
271{
272    /// Returns the value corresponding to the key.
273    pub fn get<'a: 'b, 'b, Q>(&'a self, key: Q) -> Result<Option<(A, V)>, Error>
274    where
275        Q: Borrow<K> + 'b,
276        (A, V): Load<'a>,
277    {
278        self.dict.get(key)
279    }
280}
281
282impl<K, A, V> AugDict<K, A, V>
283where
284    K: LoadDictKey,
285{
286    /// Searches for an item using a predicate on extra values.
287    ///
288    /// Used as a secondary index.
289    pub fn find_by_extra<'a, S>(&'a self, flow: S) -> Result<Option<(K, A, V)>, Error>
290    where
291        S: SearchByExtra<A>,
292        A: Load<'a>,
293        V: Load<'a>,
294    {
295        let Some((key, extra, mut value)) = ok!(aug_dict_find_by_extra::<A, S>(
296            self.dict.root.as_ref(),
297            K::BITS,
298            flow
299        )) else {
300            return Ok(None);
301        };
302
303        let Some(key) = K::load_from_data(&key) else {
304            return Err(Error::CellUnderflow);
305        };
306        let value = ok!(V::load_from(&mut value));
307        Ok(Some((key, extra, value)))
308    }
309}
310
311impl<K, A, V> AugDict<K, A, V>
312where
313    K: StoreDictKey,
314    for<'a> A: AugDictExtra + Store + Load<'a>,
315    V: Store,
316{
317    /// Builds a dictionary from a sorted collection.
318    pub fn try_from_btree<Q, E, T>(sorted: &BTreeMap<Q, (E, T)>) -> Result<Self, Error>
319    where
320        Q: Borrow<K>,
321        E: Borrow<A>,
322        T: Borrow<V>,
323        K: DictKey + Ord,
324    {
325        let root = ok!(build_aug_dict_from_sorted_iter(
326            sorted
327                .iter()
328                .map(|(k, (a, v))| (k.borrow(), a.borrow(), v.borrow())),
329            A::comp_add,
330            Cell::empty_context()
331        ));
332
333        let mut result = Self {
334            dict: Dict::from_raw(root),
335            extra: A::default(),
336            _key: PhantomData,
337            _value: PhantomData,
338        };
339        ok!(result.update_root_extra());
340        Ok(result)
341    }
342
343    /// Builds a dictionary from a sorted slice.
344    pub fn try_from_sorted_slice<Q, E, T>(sorted: &[(Q, E, T)]) -> Result<Self, Error>
345    where
346        Q: Borrow<K>,
347        E: Borrow<A>,
348        T: Borrow<V>,
349        K: Ord,
350    {
351        let root = ok!(build_aug_dict_from_sorted_iter(
352            sorted
353                .iter()
354                .map(|(k, a, v)| (k.borrow(), a.borrow(), v.borrow())),
355            A::comp_add,
356            Cell::empty_context()
357        ));
358
359        let mut result = Self {
360            dict: Dict::from_raw(root),
361            extra: A::default(),
362            _key: PhantomData,
363            _value: PhantomData,
364        };
365        ok!(result.update_root_extra());
366        Ok(result)
367    }
368
369    /// Applies a sorted list of inserts/removes to the dictionary.
370    /// Use this when you have a large set of known changes.
371    ///
372    /// Uses custom extracts for values.
373    pub fn modify_with_sorted_iter<I>(&mut self, entries: I) -> Result<bool, Error>
374    where
375        I: IntoIterator<Item = (K, Option<(A, V)>)>,
376        K: Clone + Ord,
377    {
378        self.modify_with_sorted_iter_ext(
379            entries,
380            |(key, _)| key.clone(),
381            |(_, value)| Ok(value),
382            Cell::empty_context(),
383        )
384    }
385
386    /// Applies a sorted list of inserts/removes to the dictionary.
387    /// Use this when you have a large set of known changes.
388    ///
389    /// Uses custom extracts for values.
390    pub fn modify_with_sorted_iter_ext<T, I, FK, FV>(
391        &mut self,
392        entries: I,
393        extract_key: FK,
394        extract_value: FV,
395        context: &dyn CellContext,
396    ) -> Result<bool, Error>
397    where
398        I: IntoIterator<Item = T>,
399        K: Ord,
400        for<'a> FK: FnMut(&'a T) -> K,
401        FV: FnMut(T) -> Result<Option<(A, V)>, Error>,
402    {
403        let modified = ok!(aug_dict_modify_from_sorted_iter(
404            &mut self.dict.root,
405            entries,
406            extract_key,
407            extract_value,
408            A::comp_add,
409            context,
410        ));
411
412        if modified {
413            ok!(self.update_root_extra());
414        }
415
416        Ok(modified)
417    }
418
419    /// Sets the augmented value associated with the key in the aug dictionary.
420    ///
421    /// Use [`set_ext`] if you need to use a custom cell context.
422    ///
423    /// [`set_ext`]: AugDict::set_ext
424    pub fn set<Q, E, T>(&mut self, key: Q, aug: E, value: T) -> Result<bool, Error>
425    where
426        Q: Borrow<K>,
427        E: Borrow<A>,
428        T: Borrow<V>,
429    {
430        self.set_ext(key, aug, value, Cell::empty_context())
431    }
432
433    /// Sets the value associated with the key in the dictionary.
434    pub fn set_ext<Q, E, T>(
435        &mut self,
436        key: Q,
437        aug: E,
438        value: T,
439        context: &dyn CellContext,
440    ) -> Result<bool, Error>
441    where
442        Q: Borrow<K>,
443        E: Borrow<A>,
444        T: Borrow<V>,
445    {
446        self.insert_impl(
447            key.borrow(),
448            aug.borrow(),
449            value.borrow(),
450            SetMode::Set,
451            context,
452        )
453    }
454
455    /// Sets the augmented value associated with the key in the aug dictionary
456    /// only if the key was already present in it.
457    ///
458    /// Use [`replace_ext`] if you need to use a custom cell context.
459    ///
460    /// [`replace_ext`]: AugDict::replace_ext
461    pub fn replace<Q, E, T>(&mut self, key: Q, aug: E, value: T) -> Result<bool, Error>
462    where
463        Q: Borrow<K>,
464        E: Borrow<A>,
465        T: Borrow<V>,
466    {
467        self.replace_ext(key, aug, value, Cell::empty_context())
468    }
469
470    /// Sets the value associated with the key in the dictionary
471    /// only if the key was already present in it.
472    pub fn replace_ext<Q, E, T>(
473        &mut self,
474        key: Q,
475        aug: E,
476        value: T,
477        context: &dyn CellContext,
478    ) -> Result<bool, Error>
479    where
480        Q: Borrow<K>,
481        E: Borrow<A>,
482        T: Borrow<V>,
483    {
484        self.insert_impl(
485            key.borrow(),
486            aug.borrow(),
487            value.borrow(),
488            SetMode::Replace,
489            context,
490        )
491    }
492
493    /// Sets the value associated with key in aug dictionary,
494    /// but only if it is not already present.
495    ///
496    /// Use [`add_ext`] if you need to use a custom cell context.
497    ///
498    /// [`add_ext`]: AugDict::add_ext
499    pub fn add<Q, E, T>(&mut self, key: Q, aug: E, value: T) -> Result<bool, Error>
500    where
501        Q: Borrow<K>,
502        E: Borrow<A>,
503        T: Borrow<V>,
504    {
505        self.add_ext(key, aug, value, Cell::empty_context())
506    }
507
508    /// Sets the value associated with key in dictionary,
509    /// but only if it is not already present.
510    pub fn add_ext<Q, E, T>(
511        &mut self,
512        key: Q,
513        aug: E,
514        value: T,
515        context: &dyn CellContext,
516    ) -> Result<bool, Error>
517    where
518        Q: Borrow<K>,
519        E: Borrow<A>,
520        T: Borrow<V>,
521    {
522        self.insert_impl(
523            key.borrow(),
524            aug.borrow(),
525            value.borrow(),
526            SetMode::Add,
527            context,
528        )
529    }
530
531    /// Removes the value associated with key in aug dictionary.
532    /// Returns an optional removed value as cell slice parts.
533    pub fn remove<Q>(&mut self, key: Q) -> Result<Option<(A, V)>, Error>
534    where
535        Q: Borrow<K>,
536        for<'a> A: Load<'a> + 'static,
537        for<'a> V: Load<'a> + 'static,
538    {
539        match ok!(self.remove_raw_ext(key, Cell::empty_context())) {
540            Some(parts) => {
541                let mut slice = ok!(CellSlice::apply(&parts));
542                let extra = ok!(A::load_from(&mut slice));
543                let value = ok!(V::load_from(&mut slice));
544                Ok(Some((extra, value)))
545            }
546            None => Ok(None),
547        }
548    }
549
550    /// Removes the value associated with key in dictionary.
551    /// Returns an optional removed value as cell slice parts.
552    pub fn remove_raw<Q>(&mut self, key: Q) -> Result<Option<CellSliceParts>, Error>
553    where
554        Q: Borrow<K>,
555    {
556        self.remove_impl(key.borrow(), Cell::empty_context())
557    }
558
559    /// Removes the value associated with key in dictionary.
560    /// Returns an optional removed value as cell slice parts.
561    pub fn remove_raw_ext<Q>(
562        &mut self,
563        key: Q,
564        context: &dyn CellContext,
565    ) -> Result<Option<CellSliceParts>, Error>
566    where
567        Q: Borrow<K>,
568    {
569        self.remove_impl(key.borrow(), context)
570    }
571
572    fn insert_impl(
573        &mut self,
574        key: &K,
575        extra: &A,
576        value: &V,
577        mode: SetMode,
578        context: &dyn CellContext,
579    ) -> Result<bool, Error> {
580        let mut key_builder = CellDataBuilder::new();
581        ok!(key.store_into_data(&mut key_builder));
582        let inserted = ok!(aug_dict_insert(
583            &mut self.dict.root,
584            &mut key_builder.as_data_slice(),
585            K::BITS,
586            extra,
587            value,
588            mode,
589            A::comp_add,
590            context,
591        ));
592
593        if inserted {
594            ok!(self.update_root_extra());
595        }
596
597        Ok(inserted)
598    }
599
600    fn remove_impl(
601        &mut self,
602        key: &K,
603        context: &dyn CellContext,
604    ) -> Result<Option<CellSliceParts>, Error> {
605        let mut key_builder = CellDataBuilder::new();
606        ok!(key.store_into_data(&mut key_builder));
607        let res = ok!(aug_dict_remove_owned(
608            &mut self.dict.root,
609            &mut key_builder.as_data_slice(),
610            K::BITS,
611            false,
612            A::comp_add,
613            context,
614        ));
615
616        if res.is_some() {
617            ok!(self.update_root_extra());
618        }
619
620        Ok(res)
621    }
622
623    /// Split dictionary into 2 dictionaries by the first key bit.
624    pub fn split(&self) -> Result<(Self, Self), Error> {
625        self.split_by_prefix_ext(&Default::default(), Cell::empty_context())
626    }
627
628    /// Split dictionary into 2 dictionaries by the first key bit.
629    pub fn split_ext(&self, context: &dyn CellContext) -> Result<(Self, Self), Error> {
630        self.split_by_prefix_ext(&Default::default(), context)
631    }
632
633    /// Split dictionary into 2 dictionaries at the prefix.
634    pub fn split_by_prefix(&self, key_prefix: &CellSlice<'_>) -> Result<(Self, Self), Error> {
635        self.split_by_prefix_ext(key_prefix, Cell::empty_context())
636    }
637
638    /// Split dictionary into 2 dictionaries at the prefix.
639    pub fn split_by_prefix_ext(
640        &self,
641        key_prefix: &CellSlice<'_>,
642        context: &dyn CellContext,
643    ) -> Result<(Self, Self), Error> {
644        let (left, right) = ok!(self.dict.split_by_prefix_ext(key_prefix, context));
645
646        let mut left = Self {
647            dict: left,
648            extra: A::default(),
649            _key: PhantomData,
650            _value: PhantomData,
651        };
652        ok!(left.update_root_extra());
653
654        let mut right = Self {
655            dict: right,
656            extra: A::default(),
657            _key: PhantomData,
658            _value: PhantomData,
659        };
660        ok!(right.update_root_extra());
661
662        Ok((left, right))
663    }
664
665    /// Merge dictionary with its right sibling.
666    pub fn merge_with_right_sibling(&self, right: &AugDict<K, A, V>) -> Result<Self, Error> {
667        let dict = self.merge_with_right_sibling_ext(right, Cell::empty_context())?;
668        Ok(dict)
669    }
670
671    /// Merge dictionary with its sibling
672    pub fn merge_with_right_sibling_ext(
673        &self,
674        right: &AugDict<K, A, V>,
675        context: &dyn CellContext,
676    ) -> Result<Self, Error> {
677        let merged = ok!(aug_dict_merge_siblings(
678            self.dict().root(),
679            right.dict().root(),
680            K::BITS,
681            A::comp_add,
682            context,
683        ));
684
685        let mut res = Self {
686            dict: Dict::from_raw(merged),
687            extra: A::default(),
688            _key: PhantomData,
689            _value: PhantomData,
690        };
691        ok!(res.update_root_extra());
692
693        Ok(res)
694    }
695}
696
697impl<K, A, V> AugDict<K, A, V>
698where
699    K: DictKey,
700{
701    /// Gets an iterator over the entries of the dictionary, sorted by key.
702    /// The iterator element type is `Result<(K, A, V)>`.
703    ///
704    /// If the dictionary is invalid, finishes after the first invalid element,
705    /// returning an error.
706    ///
707    /// # Performance
708    ///
709    /// In the current implementation, iterating over dictionary builds a key
710    /// for each element. Use [`values`] or [`raw_values`] if you don't need keys from an iterator.
711    ///
712    /// [`values`]: Dict::values
713    /// [`raw_values`]: Dict::raw_values
714    pub fn iter<'a>(&'a self) -> AugIter<'a, K, A, V>
715    where
716        V: Load<'a>,
717    {
718        AugIter::new(self.dict.root())
719    }
720
721    /// Gets an iterator over the keys of the dictionary, in sorted order.
722    /// The iterator element type is `Result<K>`.
723    ///
724    /// If the dictionary is invalid, finishes after the first invalid element,
725    /// returning an error.
726    ///
727    /// # Performance
728    ///
729    /// In the current implementation, iterating over dictionary builds a key
730    /// for each element. Use [`values`] if you don't need keys from an iterator.
731    ///
732    /// [`values`]: Dict::values
733    pub fn keys(&'_ self) -> Keys<'_, K> {
734        Keys::new(self.dict.root())
735    }
736}
737
738impl<K, A, V> AugDict<K, A, V>
739where
740    K: DictKey,
741{
742    /// Gets an iterator over the augmented values of the dictionary, in order by key.
743    /// The iterator element type is `Result<V>`.
744    ///
745    /// If the dictionary is invalid, finishes after the first invalid element,
746    /// returning an error.
747    pub fn values<'a>(&'a self) -> Values<'a, (A, V)>
748    where
749        V: Load<'a>,
750    {
751        Values::new(self.dict.root(), K::BITS)
752    }
753}
754
755impl<K, A, V> AugDict<K, A, V>
756where
757    K: Store + DictKey,
758{
759    /// Gets an iterator over the raw entries of the dictionary, sorted by key.
760    /// The iterator element type is `Result<(CellBuilder, CellSlice)>`.
761    ///
762    /// If the dictionary is invalid, finishes after the first invalid element,
763    /// returning an error.
764    ///
765    /// # Performance
766    ///
767    /// In the current implementation, iterating over dictionary builds a key
768    /// for each element. Use [`values`] or [`raw_values`] if you don't need keys from an iterator.
769    ///
770    /// [`values`]: AugDict::values
771    /// [`raw_values`]: AugDict::raw_values
772    pub fn raw_iter(&'_ self) -> RawIter<'_> {
773        RawIter::new(self.dict.root(), K::BITS)
774    }
775
776    /// Gets an iterator over the raw keys of the dictionary, in sorted order.
777    /// The iterator element type is `Result<CellBuilder>`.
778    ///
779    /// If the dictionary is invalid, finishes after the first invalid element,
780    /// returning an error.
781    ///
782    /// # Performance
783    ///
784    /// In the current implementation, iterating over dictionary builds a key
785    /// for each element. Use [`values`] or [`raw_values`] if you don't need keys from an iterator.
786    ///
787    /// [`values`]: AugDict::values
788    /// [`raw_values`]: AugDict::raw_values
789    pub fn raw_keys(&'_ self) -> RawKeys<'_> {
790        RawKeys::new(self.dict.root(), K::BITS)
791    }
792}
793
794impl<K, A, V> AugDict<K, A, V>
795where
796    K: DictKey,
797{
798    /// Gets an iterator over the raw values of the dictionary, in order by key.
799    /// The iterator element type is `Result<CellSlice>`.
800    ///
801    /// If the dictionary is invalid, finishes after the first invalid element,
802    /// returning an error.
803    pub fn raw_values(&'_ self) -> RawValues<'_> {
804        RawValues::new(self.dict.root(), K::BITS)
805    }
806}
807
808#[cfg(feature = "serde")]
809impl<K, A, V> serde::Serialize for AugDict<K, A, V>
810where
811    K: serde::Serialize + LoadDictKey,
812    for<'a> A: serde::Serialize + Store + Load<'a>,
813    for<'a> V: serde::Serialize + Load<'a>,
814{
815    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
816    where
817        S: serde::Serializer,
818    {
819        use serde::ser::{Error, SerializeMap};
820
821        #[derive(serde::Serialize)]
822        struct AugDictHelper<'a, K, A, V>
823        where
824            K: serde::Serialize + LoadDictKey,
825            A: serde::Serialize + Store + Load<'a>,
826            V: serde::Serialize + Load<'a>,
827        {
828            #[serde(serialize_with = "serialize_dict_entries")]
829            entires: &'a AugDict<K, A, V>,
830            extra: &'a A,
831        }
832
833        fn serialize_dict_entries<'a, K, A, V, S>(
834            dict: &'a AugDict<K, A, V>,
835            serializer: S,
836        ) -> Result<S::Ok, S::Error>
837        where
838            S: serde::Serializer,
839            K: serde::Serialize + LoadDictKey,
840            A: serde::Serialize + Store + Load<'a>,
841            V: serde::Serialize + Load<'a>,
842        {
843            let mut ser = serializer.serialize_map(None)?;
844            for ref entry in dict.iter() {
845                let (key, extra, value) = match entry {
846                    Ok(entry) => entry,
847                    Err(e) => return Err(Error::custom(e)),
848                };
849                ok!(ser.serialize_entry(key, &(extra, value)));
850            }
851            ser.end()
852        }
853
854        if serializer.is_human_readable() {
855            AugDictHelper {
856                entires: self,
857                extra: &self.extra,
858            }
859            .serialize(serializer)
860        } else {
861            crate::boc::BocRepr::serialize(self, serializer)
862        }
863    }
864}
865
866/// An iterator over the entries of an [`AugDict`].
867///
868/// This struct is created by the [`iter`] method on [`AugDict`]. See its documentation for more.
869///
870/// [`iter`]: AugDict::iter
871pub struct AugIter<'a, K, A, V> {
872    inner: Iter<'a, K, (A, V)>,
873}
874
875impl<K, A, V> Clone for AugIter<'_, K, A, V> {
876    fn clone(&self) -> Self {
877        Self {
878            inner: self.inner.clone(),
879        }
880    }
881}
882
883impl<'a, K, A, V> AugIter<'a, K, A, V>
884where
885    K: DictKey,
886{
887    /// Creates an iterator over the entries of a dictionary.
888    pub fn new(root: &'a Option<Cell>) -> Self {
889        Self {
890            inner: Iter::new(root),
891        }
892    }
893
894    /// Changes the direction of the iterator to descending.
895    #[inline]
896    pub fn reversed(mut self) -> Self {
897        self.inner = self.inner.reversed();
898        self
899    }
900
901    /// Changes the behavior of the iterator to reverse the high bit.
902    #[inline]
903    pub fn signed(mut self) -> Self {
904        self.inner = self.inner.signed();
905        self
906    }
907}
908
909impl<'a, K, A, V> Iterator for AugIter<'a, K, A, V>
910where
911    K: LoadDictKey,
912    (A, V): Load<'a>,
913{
914    type Item = Result<(K, A, V), Error>;
915
916    fn next(&mut self) -> Option<Self::Item> {
917        match self.inner.next()? {
918            Ok((key, (aug, value))) => Some(Ok((key, aug, value))),
919            Err(e) => Some(Err(e)),
920        }
921    }
922}
923
924#[cfg(test)]
925mod tests {
926    use std::collections::VecDeque;
927
928    use anyhow::Context;
929    use tycho_types::models::ShardIdent;
930
931    use super::*;
932    use crate::boc::Boc;
933    use crate::models::{DepthBalanceInfo, ShardAccount, ShardAccounts};
934
935    #[derive(Debug, Default, Load, Store, Eq, PartialEq)]
936    struct OrCmp(bool);
937
938    impl AugDictExtra for OrCmp {
939        fn comp_add(
940            left: &mut CellSlice,
941            right: &mut CellSlice,
942            b: &mut CellBuilder,
943            _: &dyn CellContext,
944        ) -> Result<(), Error> {
945            let left = left.load_bit()?;
946            let right = right.load_bit()?;
947            b.store_bit(left | right)
948        }
949    }
950
951    #[derive(Debug, Default, Load, Store, Eq, PartialEq)]
952    struct SomeValue(u32);
953
954    impl AugDictExtra for SomeValue {
955        fn comp_add(
956            left: &mut CellSlice,
957            right: &mut CellSlice,
958            b: &mut CellBuilder,
959            _: &dyn CellContext,
960        ) -> Result<(), Error> {
961            let left = left.load_u32()?;
962            let right = right.load_u32()?;
963            b.store_u32(left.saturating_add(right))
964        }
965    }
966
967    impl rand9::distr::Distribution<SomeValue> for rand9::distr::StandardUniform {
968        #[inline]
969        fn sample<R: rand9::Rng + ?Sized>(&self, rng: &mut R) -> SomeValue {
970            SomeValue(rng.random())
971        }
972    }
973
974    #[derive(Debug, Default, Load, Store, Eq, PartialEq)]
975    struct ValueWithCell(u32, Cell);
976
977    impl ValueWithCell {
978        fn new(num: u32, cell: u32) -> Self {
979            Self(num, CellBuilder::build_from(cell).unwrap())
980        }
981    }
982
983    impl AugDictExtra for ValueWithCell {
984        fn comp_add(
985            left: &mut CellSlice,
986            right: &mut CellSlice,
987            b: &mut CellBuilder,
988            ctx: &dyn CellContext,
989        ) -> Result<(), Error> {
990            // println!(
991            //     "LEFT EXTRA: {}",
992            //     Boc::encode_base64(CellBuilder::build_from(*left)?),
993            // );
994            // println!(
995            //     "RIGHT EXTRA: {}",
996            //     Boc::encode_base64(CellBuilder::build_from(*right)?),
997            // );
998
999            let left_num = left.load_u32()?;
1000            let left_cell = left.load_reference_as_slice()?.load_u32()?;
1001
1002            let right_num = right.load_u32()?;
1003            let right_cell = right.load_reference_as_slice()?.load_u32()?;
1004
1005            ValueWithCell::new(
1006                left_num.saturating_add(right_num),
1007                left_cell.saturating_add(right_cell),
1008            )
1009            .store_into(b, ctx)
1010        }
1011    }
1012
1013    #[test]
1014    fn dict_set() {
1015        let mut dict = AugDict::<u32, OrCmp, u16>::new();
1016        assert_eq!(*dict.root_extra(), OrCmp(false));
1017
1018        dict.set(123, OrCmp(false), 0xffff).unwrap();
1019        assert_eq!(dict.get(123).unwrap(), Some((OrCmp(false), 0xffff)));
1020        assert_eq!(*dict.root_extra(), OrCmp(false));
1021
1022        dict.set(123, OrCmp(true), 0xcafe).unwrap();
1023        assert_eq!(dict.get(123).unwrap(), Some((OrCmp(true), 0xcafe)));
1024        assert_eq!(*dict.root_extra(), OrCmp(true));
1025    }
1026
1027    #[test]
1028    fn dict_set_complex() {
1029        let mut dict = AugDict::<u32, OrCmp, u32>::new();
1030        assert_eq!(*dict.root_extra(), OrCmp(false));
1031
1032        for i in 0..520 {
1033            dict.set(i, OrCmp(true), 123).unwrap();
1034        }
1035        assert_eq!(*dict.root_extra(), OrCmp(true));
1036    }
1037
1038    #[test]
1039    fn dict_replace() {
1040        let mut dict = AugDict::<u32, OrCmp, u16>::new();
1041        assert_eq!(*dict.root_extra(), OrCmp(false));
1042        dict.replace(123, OrCmp(false), 0xff).unwrap();
1043        assert!(!dict.contains_key(123).unwrap());
1044        assert_eq!(*dict.root_extra(), OrCmp(false));
1045
1046        dict.set(123, OrCmp(false), 0xff).unwrap();
1047        assert_eq!(dict.get(123).unwrap(), Some((OrCmp(false), 0xff)));
1048        assert_eq!(*dict.root_extra(), OrCmp(false));
1049
1050        dict.replace(123, OrCmp(true), 0xaa).unwrap();
1051        assert_eq!(dict.get(123).unwrap(), Some((OrCmp(true), 0xaa)));
1052        assert_eq!(*dict.root_extra(), OrCmp(true));
1053    }
1054
1055    #[test]
1056    fn dict_add() {
1057        let mut dict = AugDict::<u32, OrCmp, u16>::new();
1058        assert_eq!(*dict.root_extra(), OrCmp(false));
1059
1060        dict.add(123, OrCmp(false), 0x12).unwrap();
1061        assert_eq!(dict.get(123).unwrap(), Some((OrCmp(false), 0x12)));
1062        assert_eq!(*dict.root_extra(), OrCmp(false));
1063
1064        dict.add(123, OrCmp(true), 0x11).unwrap();
1065        assert_eq!(dict.get(123).unwrap(), Some((OrCmp(false), 0x12)));
1066        assert_eq!(*dict.root_extra(), OrCmp(false));
1067    }
1068
1069    #[test]
1070    fn dict_remove() {
1071        let mut dict = AugDict::<u32, OrCmp, u32>::new();
1072        assert_eq!(*dict.root_extra(), OrCmp(false));
1073
1074        for i in 0..10 {
1075            assert!(dict.set(i, OrCmp(i % 2 == 0), i).unwrap());
1076        }
1077        assert_eq!(*dict.root_extra(), OrCmp(true));
1078
1079        let mut check_remove = |n: u32, expected: Option<(OrCmp, u32)>| -> anyhow::Result<()> {
1080            let removed = dict.remove(n).context("Failed to remove")?;
1081            anyhow::ensure!(removed == expected);
1082            Ok(())
1083        };
1084
1085        check_remove(0, Some((OrCmp(true), 0))).unwrap();
1086
1087        check_remove(4, Some((OrCmp(true), 4))).unwrap();
1088
1089        check_remove(9, Some((OrCmp(false), 9))).unwrap();
1090        check_remove(9, None).unwrap();
1091
1092        check_remove(5, Some((OrCmp(false), 5))).unwrap();
1093        check_remove(5, None).unwrap();
1094
1095        check_remove(100, None).unwrap();
1096
1097        check_remove(1, Some((OrCmp(false), 1))).unwrap();
1098        check_remove(2, Some((OrCmp(true), 2))).unwrap();
1099        check_remove(3, Some((OrCmp(false), 3))).unwrap();
1100        check_remove(6, Some((OrCmp(true), 6))).unwrap();
1101        check_remove(7, Some((OrCmp(false), 7))).unwrap();
1102        check_remove(8, Some((OrCmp(true), 8))).unwrap();
1103
1104        assert!(dict.is_empty());
1105    }
1106
1107    #[test]
1108    fn dict_iter() {
1109        let mut dict = AugDict::<u32, SomeValue, u32>::new();
1110        assert_eq!(*dict.root_extra(), SomeValue(0));
1111
1112        let mut expected_extra = 0;
1113        for i in 0..10 {
1114            expected_extra += i;
1115            dict.set(i, SomeValue(i), 9 - i).unwrap();
1116        }
1117        assert_eq!(*dict.root_extra(), SomeValue(expected_extra));
1118
1119        let size = dict.values().count();
1120        assert_eq!(size, 10);
1121
1122        for (i, entry) in dict.iter().enumerate() {
1123            let (key, aug, value) = entry.unwrap();
1124            assert_eq!(SomeValue(key), aug);
1125            assert_eq!(key, i as u32);
1126            assert_eq!(value, 9 - i as u32);
1127        }
1128    }
1129
1130    #[cfg(feature = "models")]
1131    #[test]
1132    fn aug_test() {
1133        use crate::models::{AccountBlock, CurrencyCollection};
1134        use crate::prelude::Boc;
1135
1136        let boc = Boc::decode(include_bytes!("./tests/account_blocks_aug_dict.boc")).unwrap();
1137
1138        let original_dict = boc
1139            .parse::<AugDict<HashBytes, CurrencyCollection, AccountBlock>>()
1140            .unwrap();
1141
1142        let mut data = Vec::new();
1143        for entry in original_dict.iter() {
1144            data.push(entry.unwrap());
1145        }
1146        data.reverse();
1147
1148        let mut new_dict: AugDict<HashBytes, CurrencyCollection, AccountBlock> = AugDict::new();
1149        for (key, aug, value) in data.iter() {
1150            new_dict.add(key, aug, value).unwrap();
1151        }
1152        assert_eq!(new_dict.root_extra(), original_dict.root_extra());
1153
1154        let serialized = CellBuilder::build_from(&new_dict).unwrap();
1155        assert_eq!(serialized.repr_hash(), boc.repr_hash());
1156
1157        for (key, _, _) in data.iter() {
1158            new_dict.remove(key).unwrap();
1159        }
1160        assert!(new_dict.is_empty());
1161        assert_eq!(new_dict.root_extra(), &CurrencyCollection::ZERO);
1162    }
1163
1164    #[test]
1165    fn build_from_array() {
1166        for entries in [
1167            &[
1168                (0u32, SomeValue(123), 1u32),
1169                (1, SomeValue(10), 2),
1170                (2, SomeValue(20), 4),
1171                (2, SomeValue(20), 3),
1172                (3, SomeValue(40), 4),
1173                (4, SomeValue(50), 5),
1174            ][..],
1175            &[
1176                (534837844, SomeValue(331123), 3117028142),
1177                (1421713188, SomeValue(5345345), 3155891450),
1178                (1526242096, SomeValue(567567), 2789399854),
1179                (1971086295, SomeValue(5345), 1228713494),
1180                (4258889371, SomeValue(4956495), 3256452222),
1181            ],
1182        ] {
1183            let result = AugDict::<u32, SomeValue, u32>::try_from_sorted_slice(entries).unwrap();
1184
1185            let mut dict = AugDict::<u32, SomeValue, u32>::new();
1186            for (k, a, v) in entries {
1187                dict.add(k, a, v).unwrap();
1188            }
1189
1190            println!("{}", result.dict.root.as_ref().unwrap().display_tree());
1191            println!(
1192                "BOC: {}",
1193                crate::boc::BocRepr::encode_base64(&result).unwrap()
1194            );
1195
1196            assert_eq!(result, dict);
1197        }
1198    }
1199
1200    #[test]
1201    fn compare_sorted_res() -> anyhow::Result<()> {
1202        let mut dict = AugDict::<u32, SomeValue, u64>::new();
1203        dict.add(268445184, SomeValue(269488144), 18446744073693827088)?;
1204        dict.add(4294934527, SomeValue(4294967295), 1224979098644774911)?;
1205
1206        let mut other = AugDict::<u32, SomeValue, u64>::try_from_sorted_slice(&[
1207            (268445184, SomeValue(269488144), 18446744073693827088),
1208            (4294934527, SomeValue(4294967295), 1224979098644774911),
1209        ])?;
1210        assert_eq!(other, dict);
1211
1212        other.remove(0)?;
1213        assert_eq!(other, dict);
1214
1215        other.modify_with_sorted_iter([(0, None)])?;
1216        assert_eq!(other, dict);
1217
1218        Ok(())
1219    }
1220
1221    #[test]
1222    fn modify_aug_with_cells() -> anyhow::Result<()> {
1223        let mut dict = AugDict::<u32, ValueWithCell, u64>::new();
1224        dict.add(
1225            16729856,
1226            ValueWithCell::new(1111, 123),
1227            18381441879129409280,
1228        )?;
1229        dict.add(
1230            3607101952,
1231            ValueWithCell::new(2060965847, 234),
1232            8851780914645041664,
1233        )?;
1234
1235        let mut other = AugDict::<u32, ValueWithCell, u64>::try_from_sorted_slice(&[
1236            (
1237                16729856,
1238                ValueWithCell::new(1111, 123),
1239                18381441879129409280,
1240            ),
1241            (
1242                3607101952,
1243                ValueWithCell::new(2060965847, 234),
1244                8851780914645041664,
1245            ),
1246        ])?;
1247        assert_eq!(other, dict);
1248
1249        println!(
1250            "INITIAL: {:?}",
1251            dict.dict.root.as_ref().map(Boc::encode_base64),
1252        );
1253
1254        dict.set(0, ValueWithCell::new(0, 0), 0)?;
1255        println!(
1256            "TARGET: {:?}",
1257            dict.dict.root.as_ref().map(Boc::encode_base64),
1258        );
1259
1260        other.modify_with_sorted_iter([(0, Some((ValueWithCell::new(0, 0), 0)))])?;
1261        println!(
1262            "RESULT: {:?}",
1263            other.dict.root.as_ref().map(Boc::encode_base64),
1264        );
1265        assert_eq!(other, dict);
1266
1267        Ok(())
1268    }
1269
1270    #[test]
1271    fn modify_aug_with_cells_remove() -> anyhow::Result<()> {
1272        let mut dict = AugDict::<u32, ValueWithCell, u64>::new();
1273        dict.add(66024, ValueWithCell::new(0, 123), 4108413175295410176)?;
1274        dict.add(
1275            2575203966,
1276            ValueWithCell::new(67108922, 234),
1277            16710326059140383999,
1278        )?;
1279        dict.add(
1280            3907577831,
1281            ValueWithCell::new(3907578088, 345),
1282            144121978453491944,
1283        )?;
1284
1285        let mut other = AugDict::<u32, ValueWithCell, u64>::try_from_sorted_slice(&[
1286            (66024, ValueWithCell::new(0, 123), 4108413175295410176),
1287            (
1288                2575203966,
1289                ValueWithCell::new(67108922, 234),
1290                16710326059140383999,
1291            ),
1292            (
1293                3907577831,
1294                ValueWithCell::new(3907578088, 345),
1295                144121978453491944,
1296            ),
1297        ])?;
1298        assert_eq!(other, dict);
1299
1300        println!(
1301            "INITIAL: {:?}",
1302            dict.dict.root.as_ref().map(Boc::encode_base64),
1303        );
1304
1305        dict.remove(0)?;
1306        dict.remove(71)?;
1307        assert_eq!(other, dict);
1308
1309        other.modify_with_sorted_iter([(0, None), (71, None)])?;
1310        println!(
1311            "RESULT: {:?}",
1312            other.dict.root.as_ref().map(Boc::encode_base64),
1313        );
1314        assert_eq!(other, dict);
1315
1316        Ok(())
1317    }
1318
1319    #[test]
1320    fn build_from_any_array() {
1321        for _ in 0..100 {
1322            let n = 1 + rand9::random::<u32>() % 1000;
1323            let mut entries = (0..n)
1324                .map(|_| {
1325                    (
1326                        rand9::random::<u32>(),
1327                        rand9::random::<SomeValue>(),
1328                        rand9::random::<u32>(),
1329                    )
1330                })
1331                .collect::<Vec<_>>();
1332            entries.sort_by_key(|(k, _, _)| *k);
1333
1334            let built_from_dict =
1335                AugDict::<u32, SomeValue, u32>::try_from_sorted_slice(&entries).unwrap();
1336
1337            let mut dict = AugDict::<u32, SomeValue, u32>::new();
1338            for (k, a, v) in entries {
1339                dict.add(k, a, v).unwrap();
1340            }
1341
1342            // println!("{}", built_from_dict.as_ref().unwrap().display_tree());
1343
1344            assert_eq!(built_from_dict, dict);
1345        }
1346    }
1347
1348    #[test]
1349    fn search_by_lt() {
1350        #[derive(Debug, Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Store, Load)]
1351        struct MaxValue(u64);
1352
1353        impl AugDictExtra for MaxValue {
1354            fn comp_add(
1355                left: &mut CellSlice,
1356                right: &mut CellSlice,
1357                b: &mut CellBuilder,
1358                _: &dyn CellContext,
1359            ) -> Result<(), Error> {
1360                let left = left.load_u64()?;
1361                let right = right.load_u64()?;
1362                b.store_u64(left.max(right))
1363            }
1364        }
1365
1366        let mut items = AugDict::<u32, MaxValue, u32>::new();
1367        items.set(0, MaxValue(100), 123).unwrap();
1368        items.set(2, MaxValue(150), 234).unwrap();
1369        items.set(4, MaxValue(200), 345).unwrap();
1370        items.set(6, MaxValue(350), 456).unwrap();
1371        items.set(7, MaxValue(300), 567).unwrap();
1372        items.set(8, MaxValue(250), 678).unwrap();
1373
1374        // Search by ordering
1375        let highest = items.find_by_extra(std::cmp::Ordering::Greater).unwrap();
1376        assert_eq!(highest, Some((6, MaxValue(350), 456)));
1377    }
1378
1379    #[test]
1380    fn split_merge_aug_test() -> anyhow::Result<()> {
1381        let mut dict = AugDict::<u32, OrCmp, u32>::new();
1382        dict.add(1, OrCmp(true), 1)?;
1383        dict.add(2, OrCmp(true), 1)?;
1384        dict.add(3, OrCmp(true), 1)?;
1385        dict.add(u32::MAX - 2, OrCmp(false), 4)?;
1386        dict.add(u32::MAX - 1, OrCmp(false), 5)?;
1387        dict.add(u32::MAX, OrCmp(false), 6)?;
1388
1389        let (d1, d2) = dict.split()?;
1390
1391        let merged = d1.merge_with_right_sibling(&d2)?;
1392        for i in merged.iter() {
1393            let _ = i?;
1394        }
1395        assert_eq!(dict, merged);
1396
1397        Ok(())
1398    }
1399
1400    #[test]
1401    fn merge_with_none() -> anyhow::Result<()> {
1402        let cell = Boc::decode_base64(
1403            "te6ccgECCgEAAcMAAQ+BlrzEHpAAEAEBoaACN33l61Vk62GrjymKAv197LmrqqmfcDpXYIKjXocJzABlrzEHpAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAICc8/xG77y9aqydbDVx5TFAX6+9lzV1VTPuB0rsEFRr0OE5gIQgkNAAAAAAAAAAAAAAAABlrzEHpAAE0AEAwBQiSKga9Z+zeO4A1bGS5OIEoMIyhKQn+Fzzir2sgDX9BQAAAAAAAAAAAEU/wD0pBP0vPLICwUCASAJBgLm8nHXAQHAAPJ6gwjXGO1E0IMH1wHXCz/I+CjPFiPPFsn5AANx1wEBwwCagwfXAVETuvLgZN6AQNcBgCDXAYAg1wFUFnX5EPKo+CO78nlmvvgjgQcIoIED6KhSILyx8nQCIIIQTO5kbLrjDwHIy//LP8ntVAgHAD6CEBaePhG6jhH4AAKTINdKl3jXAdQC+wDo0ZMy8jziAJgwAtdM0PpAgwbXAXHXAXjXAddM+ABwgBAEqgIUscjLBVAFzxZQA/oCy2ki0CHPMSHXSaCECbmYM3ABywBYzxaXMHEBywASzOLJAfsAAATSMA==",
1404        )?;
1405        let cell2 = Boc::decode_base64("te6ccgEBAQEABAAAAwAQ")?;
1406
1407        let accounts = ShardAccounts::load_from(&mut cell.as_slice()?)?;
1408        let accounts2 = ShardAccounts::load_from(&mut cell2.as_slice()?)?;
1409
1410        for i in accounts.iter() {
1411            let _ = i?;
1412        }
1413
1414        for i in accounts2.iter() {
1415            let _ = i?;
1416        }
1417
1418        let merged = accounts.merge_with_right_sibling(&accounts2)?;
1419        let merged2 = accounts2.merge_with_right_sibling(&accounts)?;
1420
1421        assert_eq!(merged, merged2);
1422        Ok(())
1423    }
1424
1425    #[test]
1426    fn split_merge_multiple() -> anyhow::Result<()> {
1427        let cell = Boc::decode_base64(
1428            "te6ccgICASoAAQAAJqgAAAEVgkFa8hv72kj0ABAAAQIVASCteQ397SR6AAgACQACAg8A1rzEHpAACAAGAAMBob+8acQzfPfesANweTwdZXUyOCZ9yXBMXTvjxPvAVzFv/wMteYg9IAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAIAAEAnPP/8acQzfPfesANweTwdZXUyOCZ9yXBMXTvjxPvAVzFv/yEIJDQAAAAAAAAAAAAAAAAZa8xB6QABNAARoABQBQ4pEYpaANiimLi8ulTwtbktSad7UtpAkT+h1rup9OAyAAAAAAAAAAAAGhv4d+eU4H0n/wpgFeJlr+InBuc4h6j1IGdrPoRm0KoQdiAy15iD0gAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAgAAcCc8/4d+eU4H0n/wpgFeJlr+InBuc4h6j1IGdrPoRm0KoQdiIQgkNAAAAAAAAAAAAAAAABlrzEHpAAE0ABGgAIAFDzVT6+77rUGpVMk2DSGOnwwERDiiRh1dFTcJeAbPOM0gAAAAAAAAAAAhUBIK1490EpBeoACACuAAoCFQEgrXjr1DmsUQAIAA4ACwGnv26sO7JAP7yIMfmbcnt4xhQX39fBSeYXWHmNPuVvb8q+CQVrx14tYxAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAwCec/3dWHdkgH95EGPzNuT28YwoL7+vgpPMLrDzGn3K3t+VfIQgklAAAAAAAAAAAAAAAACQVrx14tYxAAAE0ABGgANAFBBL1h1hgUZNWijPk2MZ8rg7aURM1qP2K02LpsE3HqBKQAAAAAAAAAAAZ+/aqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqoFdGpSiAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAQAAPAnHP9VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVSYpCtwAAAAAAAAAAAAAAAAV0alKIAFdAAggAQAUkAAAAA8RNW+L2R7Xk3c1zzKsavlKKoKGVSRjnw4xviReBY1BRAABECA81AABwAEgIBSAAVABMBAbcAFABKAgAgAAAAACAAAAAD6AIAAAD//wIAAAEAAAP/AAAAAAEAAAABAAEBtQAWASsSaDA0jWgwNI0AAwADAAAAAAAAAAPAABcCAs4AGQAYAFtFOOgSeKTXp3A2sU63eRJ8ZWdnt72s+oqmiM10bhcy6TfIF3qUkAAAAAAAAAAYAgEgABsAGgBbFOOgSeKCJuwFX8hvURNj7MTKxHwmtMT2YH6RvKm5rhk3pwSVEIAAAAAAAAAAYABbFOOgSeKHGrtnug9jSGYbE42s6womsPELoN4Xh0vXx1kkOYntTIAAAAAAAAAAYAIBIABJAB0CASAAMgAeAgEgAC0AHwIBIAAlACABAVgAIQEBwAAiAgFiACQAIwBBv2ZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZnAAPfsAIBIAAoACYBASAAJwA02BOIAAwAAAAUAIwA0gMgAAAAlgAZAgEEA0gBASAAKQHnpoAABOIAAHUwD4AAAAAjw0YAAIAAE4gAMgAFAB4AMgAAYagAAAnEQAAJxAAAAAHoSAAAAAAAMgTiAH0AJYAAAG9UGGoF3AAACcQC7gLuAu4ABAAA+gB9AH0AfQA5OHAA+gH0ADk4cAB9AfQAAAAAAAAAACAAKgICzwAsACsAAwKgAAMUIAIBSAAwAC4BASAALwBC6gAAAAAAD0JAAAAAAAPoAAAAAAABhqAAAAABgABVVVVVAQEgADEAQuoAAAAAAJiWgAAAAAAnEAAAAAAAD0JAAAAAAYAAVVVVVQIBIAA+ADMCASAAOQA0AgEgADcANQEBIAA2AFBdwwACAAAACAAAABAAAMMADbugABJPgATEtADDAAAD6AAAE4gAACcQAQEgADgAUF3DAAIAAAAIAAAAEAAAwwANu6AAEk+AAB6EgMMAAAPoAAATiAAAJxACASAAPAA6AQEgADsAlNEAAAAAAAAD6AAAAAAAD0JA3gAAAAAD6AAAAAAAAAAPQkAAAAAAAA9CQAAAAAAAACcQAAAAAACYloAAAAAABfXhAAAAAAA7msoAAQEgAD0AlNEAAAAAAAAD6AAAAAAAmJaA3gAAAAAnEAAAAAAAAAAPQkAAAAAABfXhAAAAAAAAACcQAAAAAACn2MAAAAAABfXhAAAAAAA7msoAAgEgAEQAPwIBIABCAEABASAAQQAIAAAAAAEBIABDAE3QZgAAAAAAAAAAAAAAAIAAAAAAAAD6AAAAAAAAAfQAAAAAAAPQkEACASAARwBFAQEgAEYAMWCRhOcqAAcjhvJvwQAAZa8xB6QAAAAwAAgBASAASAAMA+gAZAANAgEgAHcASgIBIABUAEsCASAAUQBMAgEgAE8ATQEBIABOACAAAQAAAACAAAAAIAAAAIAAAQEgAFAAFGtGVT8QBDuaygABAUgAUgEBwABTALfQUwAAAAAAAAHwAFMclHHEkkRaeeMmEGCRKlBxBLcinsKGf1E09UQ6ATv+Drv1gtpXTXsR7WKKGFhvtjRXlraU5dh8OXjhB/jWiHwAAAAACAAAAAAAAAAAAAAABAIBIABgAFUCASAAWgBWAQEgAFcCApEAWQBYACo2BAcEAgBMS0ABMS0AAAAAAgAAA+gAKjYCAwICAA9CQACYloAAAAABAAAB9AEBIABbAgPNQABeAFwCAWIAXQBnAgEgAHEAcQIBIABsAF8CAc4AdAB0AgEgAHUAYQEBIABiAgPNQABkAGMAA6igAgEgAGwAZQIBIABpAGYCASAAaABnAAHUAgFIAHQAdAIBIABrAGoCASAAbwBvAgEgAG8AcQIBIABzAG0CASAAcABuAgEgAHEAbwIBIAB0AHQCASAAcgBxAAFIAAFYAgHUAHQAdAABIAEBIAB2ABrEAAAAIAAAAAAAABauAgEgAHoAeAEB9AB5AAFAAgEgAH0AewEBSAB8AEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAIBIACAAH4BASAAfwBAMzMzMzMzMzMzMzMzMzMzMzMzMzMzMzMzMzMzMzMzMzMBASAAgQBAVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVUBFP8A9KQT9LzyyAsAgwIBIACLAIQCAvEAiACFAtkgwjXGCDTH9Mf0x8B+CO58mMg12SDBrzyZ+1E0NTTH9P/9ATRUVK68qElghBWb3RluuMCBvkBVBB2+RDyovgABaSpOB9UdQQlA8jMEssfy//0AMntVPgPEDVEVds8QwMDyMwSyx/L//QAye1UgAIcAhgCmIYIQQ2ZQIbqcMdIf1NFAE4Ag9BUB4CGCEE5Db2S6jhMx1CH7BO1DAtDtHu1TAfEGgvIA4CGCEFBiSyG6lWwh0//R4CGCEE5D7wW6kzHwC+Aw8mACkjUC0w/T/9Eh2zww0weAILMSsMBT8qnTHwGCEI6BJ4q68qnT/9M/MEiZ+RHyovgAAqSpOB9VEgPIzBLLH8v/9ADJ7VT4D1jbPDAA/QCgAc0MO1E0NTTH9P/9ATRgCCAJFNR9GpwIW6SbCGONyHQINdJwieOKdMH1wsf+CO7AcASsI4XMIAiWFFm9G5UVSH0bjCAJEAV9FowA3+SbCHikxNfA+LijoLbPN8DyMwSyx/L//QAye1UgAIkBTPgQIYMH9H1vpZFb4VIC2zyOESBulzABgwf0WzCVAoMH9BbikVviAIoDojHbPDAB+QAi2zwzJfgju5RfCW1/4Ca6k18HcOA3VBBm2zxtBXOptAEhbpRfB21/4BA1ECQQNkYGgM7IygcWyx8UzBLKAPQAyj/L/wHPFsnQfwD+AKsApRIBf5mN0iw1J3EDxwy2mOt5/BeKx0vuH4jd3aAdZnc92KkACkgAlACMAgEgAI4AjQFpvRwXaiaGppj+n/+gJothjCf7bHTqiJQYP6PzfSkEdGAW2eKQg3gSgBt4EBSJlxANmJczYQwAkQIBIACTAI8CASAAkgCQATe2EX2omhqaY/p//oCaLYYwYP6BzfQyRg28O2eQAJECYNs8bYMfjhIlgBD0fm+lMiGVUgNvAgLeAbPmMDTTB9MH0wfRB9s8bwMGBxA1EDRvCQCrAK0AEbWS/aiaGuFj8AFdulRe1E0NdMgAsBgCD0ahTbPGxEUlS5k18Gf+BQRLYIAoMJoBOoA6YCEqgSoAGogArAICxQCWAJUABqqCWwIBzQCaAJcCAUgAmQCYAFtXH4M9DXC//4I4IQTkNvZHCCAMT/yMsQFMv/gx36AhPLahLLH8s/Ac8WyXD7AIACtHCAGMjLBVAFzxYUy27LH8s/yQH7AIAgEgAJwAmwAz9oaYOA4Al5ROmP6Y/ph+mHmBBhAHlE33lEwCAUgAngCdACU7UTQ1FAzgCD0FcjMAc8Wye1UgAvUAdDTA/pAMCD6RAGkA3GwE7EjxwCxkl8E4ALTH9M/IoIQTlZTVLqORDI01NFx+DMgbpIwf5TQ1wv/4gJwA7qcMSDwByH4I7wCvLAB3gGOEIAkAfABAYIQ7nZPS4BA8AjgMAGCEO52T2+AQPAI4DMhghBuVlBSuuMCNCCAApgCfAsSCEFZvdGW6j0wwgwjXGCDTH9MP0//RAoIQVm90RbrypSDbPDDTB4AgsxKwwFPyqdMfAYIQjoEnirryqdP/0z8wRFX5EfKiAts8ghDWdFJAoBKAQPAI4GwxIMAAAYMesLHypQD9AKADxO1E0NTTH9P/9ATRRhNQVNs8VHNUJQPIzBLLH8v/9ADJ7VQhbpJsUY84diGhREDbPFRyZSYDyMwSyx/L//QAye1UIY6X+A8QIxAl2zxEAwPIzBLLH8v/9ADJ7VSUEEZfBuLiAKMAogChAIIhgfwZup1sISBukjBwlNDXC//i4CBukVvgIYH8GLqOFDHQ1CH7BO1DAtDtHu1TAfEGgvIA4AGB/Be6k9DwC5Ew4gGqAds8UySAIPRqIG6SMHCS+QDiIb0Bwv+wlF8DcG3geSSAIPRqUiCAIPQMb6ExIW6wlF8DcG3geiSAIPRqUiCAIPQMb6ExUAO5k1twbeBUYQSAIPQVWQCtBNpTI4MH9A5voZRfBG1/4ds8MAH5AALbPCb4I7uaXwsBgwf0WzBtf+BTGL2OjDEyIts8bQVzqbQBFZI3N+IlbppfCQGDB/RbMG1/4FOBgBD0Dm+hMZRfCm1+4PgjyMsfUJKAEPRDJ1CHoVIHssL/AP4AqwClAKQB7o4fVSOAzsjKBxbLHxTMEsoA9ADKP8v/Ac8WAoMH9ENtcuAggAv4M9s8EFdfBwTTB9MH0wcwAaRSB76OEFtQVl8FUCODB/RbMHZYoRLgEEUQNBAjSHaAzsjKBxbLHxTMEsoA9ADKP8v/EssHEssHywcCgwf0Q21yAKwBYoAL+DPbPBBHXwcC0wfTB9MHMAPC/xOhUgS8k18DbeClIMEAk18DbeDIywfLB8sHydAArAE+MQPbPIBAIaMiwv+cW3T7AoIQ7lZQUoMGkTLiECPwCACnAvYB0x/U0gAwIqsdlQL4I6EC3iHbPCDC/44XIvgzIG6SMHCS+QDiIb2XMIIXHZucqt6OFXn4M1IwgCD0DG+hMZcwghcyr5GU3uIh12WDBr6XMIIXPZ6bqt4gwf+SbGHgI5EyjhR6+DMTgCD0DG+hMZeCFzyNlqwy3uIhwf8ArQCoBO6TFV8F4DEhgAv4M9s8NDQ1UoC5mF8Jghc6h4+X4FBztggDgwn5QTKDCaAXqAamAhKoFaBTAagC+COg7UTQ1NMf0//0BNEo+QBTAYMH9A5voeMCMDZRpqGDHbmYXwqCFw+ehtzg2zwwc6m0AXBtA/kAEFcQSxpDMACsAKoA/gCpAFqAzsjKBxbLHxTMEsoA9ADKP8v/F8sHFMsPQBaDB/RDEgPIzBLLH8v/9ADJ7VQB1Dg5OQXbPFJNvZhfD4IXPI2Wq+BTWL6YXw+CFz6TjbvgUoahgw2gGahR3aGDHbmYXw2CFw+ehtzgEFZAFFB3A4DOyMoHFssfFMwSygD0AMo/y/9QBM8WQEWDB/RDEwPIzBLLH8v/9ADJ7VQAqwAk0gcBwM7yrNMf1NIA9ATSP9P/AFTQ0wcBgQCRuvKsAZLUMd7XTNDTBwHANvKs0wfTB9MH0wfTH9Mf0x/TH9EALtDSBwHA8/Ks0h/0BNIAAZLT/5J/AeLRAg8Ay2zvWZkACAEWAK8Bn79mZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZgV0alKIAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAALACcc/zMzMzMzMzMzMzMzMzMzMzMzMzMzMzMzMzMzMzMzMzMzLMm3QAAAAAAAAAAAAAAAABXRqUogAW0ACyALEASQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEBFP8A9KQT9LzyyAsAswIBIAC1ALQAUaX//xh2omh6AnoCETdKrPgVeSBOKjgQ+BL5ICz4FHkgcXgTeSB4FJhAAgFIAM8AthIBFZ4Bx7G/KpJus1iacA41Fg0e9ne2K9D4fxiDVZZRJ78AByAAvAC3AgEgALsAuAIBWAC6ALkAM7PgO1E0PQEMfQEMIMH9A5voZP6ADCSMHDigAW2wpXtRND0BSBukjBt4Ns8ECZfBm2E/44bIoMH9H5vpSCdAvoAMFIQbwJQA28CApEy4gGz5jAxgAQwBSbmHXbPBA1XwWDH22OFFESgCD0fm+lMiGVUgNvAgLeAbMS5mwhgBFQIBIADGAL0CASAAvwC+ATO30/tngLBhNAA1AHTASgCVAlQANQA0EGO0EADuAgFqAMEAwAFCqyztRND0BSBukltw4Ns8ECZfBoMH9A5voZP6ADCSMHDiAQwCASAAxQDCAgFIAMQAwwGHuq7UTQ9AUgbpgwcFRwAG1TEeDbPG2E/44nJIMH9H5vpSCOGAL6ANMfMdMf0//T/9FvBFIQbwJQA28CApEy4gGz5jAzgBDAAjuH7UTQ9AUgbpIwcJTQ1wsf4oAQOnyQDOAgEgAMwAxwIBIADLAMgCASAAygDJAl2vS22eCBqvgsGPtsdPKIlAEHo/N9KQR0aBbZ4TqrA3hCgBt4EBSJlxANmJczYQwAEVARMCJ6wOgO2eQYP6BzfQx0FtnkkYNvFAAM4AzQJhsKI2zwQNV8Fgx9tjqBREoAg9H5vpSCOjwLbPF8EI0MTbwRQA28CApEy4gGzEuZsIYAEVARMCU7ZIW2eQn+2x06oiUGD+j830pBHRgFtnikIN4EoAbeBAUiZcQDZiXM2EMADOAM0CSts8bYMfjhIkgBD0fm+lMiGVUgNvAgLeAbPmMDMD0Ns8bwgDbwQA/AD5AijbPBA1XwWAIPQOb6GSMG3h2zxsYQEVARMCAsUA0QDQASqqgjGCEE5Db2SCEM5Db2RZcIBA2zwBDgIByQDpANISAW4a85Q1ufW1LEXymEEC7IZbucuD3mjLjoAesLeX8QB6AAhIANkA0wIBSADVANQB3UMYAk+DNukltw4XH4M9DXC//4KPpEAaQCvbGSW3DggCL4MyBuk18DcODwDTAyAtCAKNch1wsf+CNRE6FcuZNfBnDgXKHBPJExkTDigBH4M9D6ADADoFICoXBtEDQQI3Bw2zzI9AD0AAHPFsntVH+AELAgEgANcA1gN5Ns8f48yJIAg9HxvpSCPIwLTHzD4I7tTFL2wjxUxVBVE2zwUoFR2E1RzWNs8A1BUcAHekTLiAbPmbGFus4AEVAQABFAOTAHbPGxRk18DcOEC9ARRMYAg9A5voZNfBHDhgEDXIdcL/4Ai+DMh2zyAJPgzWNs8sY4TcMjKABL0APQAAc8Wye1U8CYwf+BfA3CABDADYANgAGCFukltwlQH5AAG64gIBIADoANoCASAA3QDbA6dNs8gCL4M/kAUwG6k18HcOAiji9TJIAg9A5voY4g0x8xINMf0/8wUAS68rn4I1ADoMjLH1jPFkAEgCD0QwKTE18D4pJsIeJ/iuYgbpIwcN4B2zx/gBFQDcARQAliOAIPR8b6UgjjwC0z/T/1MVuo4uNAP0BPoA+gAoqwJRmaFQKaAEyMs/Fsv/EvQAAfoCAfoCWM8WVCAFgCD0QwNwAZJfA+KRMuIBswIBIADhAN4D9QB2zw0+CMluZNfCHDgcPgzbpRfCPAi4IAR+DPQ+gD6APoA0x/RU2G5lF8M8CLgBJRfC/Ai4AaTXwpw4CMQSVEyUHfwJCDAACCzKwYQWxBKEDlN3ds8I44QMWxSyPQA9AABzxbJ7VTwIuHwDTL4IwGgpsQptgmAEPgz0IAEMAQsA3wK6gBDXIdcLD1JwtghTE6CAEsjLB1Iwyx/LHxjLDxfLDxrLPxP0AMlw+DPQ1wv/UxjbPAn0BFBToCigCfkAEEkQOEBlcG3bPEA1gCD0QwPI9AAS9AAS9AABzxbJ7VR/AOABEgBGghBOVlNUcIIAxP/IyxAVy/+DHfoCFMtqE8sfEss/zMlx+wAD9yAEPgz0NMP0w8x0w/RcbYJcG1/jkEpgwf0fG+lII4yAvoA0x/TH9P/0//RA6MEyMt/FMofUkDL/8nQURq2CMjLHxPL/8v/QBSBAaD0QQOkQxORMuIBs+YwNFi2CFMBuZdfB21wbVMR4G2K5jM0pVySbxHkcCCK5jY2WyKAA5wDlAOIBXsAAUkO5ErGXXwRtcG1TEeBTAaWSbxHkbxBvEHBTAG1tiuY0NDQ2UlW68rFQREMTAOMB/gZvIgFvJFMdgwf0Dm+h8r36ADHTPzHXC/9TnLmOXVE6qKsPUkC2CFFEoSSqOy6pBFGVoFGJoIIQjoEniiOSgHOSgFPiyMsHyx9SQMv/UqDLPyOUE8v/ApEz4lQiqIAQ9ENwJMjL/xrLP1AF+gIYygBAGoMH9EMIEEUTFJJsMeIA5AEiIY6FTADbPAqRW+IEpCRuFRcBAwFIAm8iAW8QBKRTSL6OkFRlBts8UwK8lGwiIgKRMOKRNOJTNr4TAOYANHACjhMCbyIhbxACbxEkqKsPErYIEqBY5DAxAGQDgQGg9JJvpSCOIQHTf1EZtggB0x8x1wv/A9Mf0/8x1wv/QTAUbwRQBW8CBJJsIeKzFAADacISAemGadAphsmxdMUOMXCf1iWrDQ6VEnJkCR7R77ZRX1Z0AAkgAO8A6gTjpwF9IgDSSa+Bv/AQ67JBg19Jr4G+8G2eCBqvgoFpj6mJwBB6BzfQya+DP3CQa4WP/BHQkGCAya+DvnARbZ42ERn8Ee2eBcGF/KGZQYTQLFQA0wEoBdQNUCgD1CgEUBBBjtAoBlzJr4W98CoKAaoc25PAARUA+QDuAOsEpNs8yQLbPFGzgwf0Dm+hlF8OgPrhgQFA1yH6ADBSCKm0HxmgUge8lF8MgPngUVu7lF8LgPjgbXBTB1Ug2zwG+QBGCYMH9FOUXwqA9+FGUBA3ECcA7QETAPsA7AMi2zwCgCD0Q9s8MxBFEDRY2zwBEgEVARQANIC8yMoHGMv/FswUyx8SywfL/wH6AgH6AssfADyADfgzIG6WMIMjcYMIn9DTBwHAGvKJ+gD6APoA0eICASAA8QDwAB27AB/wZ6GkP6Q/pD+uFD8Ef9gOhpgYC42EkvgfB9IBgQ44BHQhiA7Z5wAOmPkOAAR0ItgO2ecGmfkUEIJzm6Jd1HQpkIEe2ecBFBCCOyuhJdQBDwEPAQYA8hR6O7bC18pLFeJspnxnWzreBD9yhFBd4GwkesCc8+sHs/MABo6ENBPbPOAighBOQ29kuo8YNFRSRNs8loIQzkNvZJKEH+JAM3CAQNs84CKCEO52T0u6I4IQ7nZPb7pSELEBBQEEAQ4A8wSWjoYzNEMA2zzgMCKCEFJnQ3C6jqZUQxXwHoBAIaMiwv+XW3T7AnCDBpEy4gGCEPJnY1CgA0REcAHbPOA0IYIQVnRDcLrjAjMggx6wAP8BDgD1APQBHI6JhB9AM3CAQNs84V8DAQ4DogODCNcYINMf0w/TH9P/0QOCEFZ0Q1C68qUh2zww0weAILMSsMBT8qnTHwGCEI6BJ4q68qnT/9M/MEVm+RHyolUC2zyCENZ0UkCgQDNwgEDbPAD9APYBDgRQ2zxTk4Ag9A5voTsKk18KfuEJ2zw0W2wiSTcY2zwyIcEBkxhfCOAgbgEVARMA+gD3AiqSMDSOiUNQ2zwxFaBQROJFE0RG2zwA+AEUAprQ2zw0NDRTRYMH9A5voZNfBnDh0//TP/oA0gDRUhaptB8WoFJQtghRVaECyMv/yz8B+gISygBARYMH9EMjqwICqgIStghRM6FEQ9s8WQD5AQMALtIHAcC88onT/9TTH9MH0//6APoA0x/RA75TI4MH9A5voZRfBG1/4ds8MAH5AALbPFMVvZlfA20Cc6nUAAKSNDTiU1CAEPQOb6ExlF8HbXDg+CPIyx9AZoAQ9ENUIAShUTOyJFAzBNs8QDSDB/RDAcL/kzFtceABcgD+APwA+wAcgC3IywcUzBL0AMv/yj8AHtMHAcAt8onU9ATT/9I/0QEY2zwyWYAQ9A5voTABAP4ALIAi+DMg0NMHAcAS8qiAYNch0z/0BNECoDIC+kRw+DPQ1wv/7UTQ9AQEpFq9sSFusZJfBODbPGxRUhW9BLMUsZJfA+D4AAGRW46d9AT0BPoAQzTbPHDIygAT9AD0AFmg+gIBzxbJ7VTiAQwBAANEAYAg9GZvoZIwcOHbPDBsMyDCAI6EEDTbPI6FMBAj2zziEgETAQIBAQFycCB/jq0kgwf0fG+lII6eAtP/0z8x+gDSANGUMVEzoI6HVBiI2zwHA+JQQ6ADkTLiAbPmMDMBuvK7AQMBmHBTAH+OtyaDB/R8b6UgjqgC0//TPzH6ANIA0ZQxUTOgjpFUdwiphFFmoFIXoEuw2zwJA+JQU6AEkTLiAbPmMDUDulMhu7DyuxKgAaEBAwAyUxKDB/QOb6GU+gAwoJEw4sgB+gICgwf0QwBucPgzIG6TXwRw4NDXC/8j+kQBpAK9sZNfA3Dg+AAB1CH7BCDHAJJfBJwB0O0e7VMB8QaC8gDifwLWMSH6RAGkjo4wghD////+QBNwgEDbPODtRND0BPQEUDODB/Rmb6GOj18EghD////+QBNwgEDbPOE2BfoA0QHI9AAV9AABzxbJ7VSCEPlvcyRwgBjIywVQBM8WUAT6AhLLahLLH8s/yYBA+wABDgEOFMSmEoNV0EkU8RbT/FxufXrFh+9I54/+m6SdoO2WrKUNxwAFI/pE7UTQ9AQhbgSkFLGOhxA1XwVw2zzgBNP/0x/TH9P/1AHQgwjXGQHRghBlTFB0yMsfUkDLH1Iwyx9SYMv/UiDL/8nQURX5EY6HEGhfCHHbPOEhgw+5jocQaF8Idts84AcBDQENAQ0BBwRW2zwxDYIQO5rKAKEgqgsjuY6HEL1fDXLbPOBRIqBRdb2OhxCsXwxz2zzgDAEMAQ0BDQEIBMCOhxCbXwtw2zzgU2uDB/QOb6EgnzD6AFmgAdM/MdP/MFKAvZEx4o6HEJtfC3TbPOBTAbmOhxCbXwt12zzgIPKs+AD4I8hY+gLLHxTLHxbL/xjL/0A4gwf0QxBFQTAWcHABDQENAQ0BCQIm2zzI9ABYzxbJ7VQgjoNw2zzgWwELAQoBIIIQ83RITFmCEDuaygBy2zwBDgAqBsjLHxXLH1AD+gIB+gL0AMoAygDJACDQ0x/TH/oA+gD0BNIA0gDRARiCEO5vRUxZcIBA2zwBDgBEcIAYyMsFUAfPFlj6AhXLahPLH8s/IcL/kssfkTHiyQH7AARU2zwH+kQBpLEhwACxjogFoBA1VRLbPOBTAoAg9A5voZQwBaAB4w0QNUFDARUBFAERARABBNs8ARQCINs8DKBVBQvbPFQgU4Ag9EMBEwESACgGyMsfFcsfE8v/9AAB+gIB+gL0AAAe0x/TH9P/9AT6APoA9ATRACgFyPQAFPQAEvQAAfoCyx/L/8ntVAAg7UTQ9AT0BPQE+gDTH9P/0QIPAMteYg9IAAgBIAEXAaC/FCUScvzNAB3pILVPbk8apfJz/bMjNL4/A7X/ieTTCjwMteYg9IAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEYAnPP8VCUScvzNAB3pILVPbk8apfJz/bMjNL4/A7X/ieTTCjyEIJDQAAAAAAAAAAAAAAAAZa8xB6QABNAARoBGQBQJN3dyvu8mmnC7bx8AQTEe5QasCr6hwUXwpMMObigzz4AAAAAAAAAAAEU/wD0pBP0vPLICwEbAgEgAR8BHALm8nHXAQHAAPJ6gwjXGO1E0IMH1wHXCz/I+CjPFiPPFsn5AANx1wEBwwCagwfXAVETuvLgZN6AQNcBgCDXAYAg1wFUFnX5EPKo+CO78nlmvvgjgQcIoIED6KhSILyx8nQCIIIQTO5kbLrjDwHIy//LP8ntVAEeAR0APoIQFp4+EbqOEfgAApMg10qXeNcB1AL7AOjRkzLyPOIAmDAC10zQ+kCDBtcBcdcBeNcB10z4AHCAEASqAhSxyMsFUAXPFlAD+gLLaSLQIc8xIddJoIQJuZgzcAHLAFjPFpcwcQHLABLM4skB+wAABNIwAVXfgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEASEDZ8/wAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAISgY9AAAAAAAAAAAAAAAAAE8ABKQEoASICAWIBJgEjAUK/QSQpIF6mbW8gBO36Vw9vVrPoXlm6ob77xzt9pdVb3GABJAEEEjQBJQAEVngBQr9aLu9QVndfW5Vy/zrWPdKnHR+ygcoXel4cdHMOzLLlEwEnAA+rrKutq6yrqABIAAAAAPETVvi9ke15N3Nc8yrGr5SiqChlUkY58OMb4kXgWNQUAJj/ACDdIIIBTJe6lzDtRNDXCx/gpPJggQIA1xgg1wsf7UTQ0x/T/9FRErryoSL5AVQQRPkQ8qL4AAHTHzHTB9TRAfsApMjLH8v/ye1U",
1429        )?;
1430        let accounts = ShardAccounts::load_from(&mut cell.as_slice()?)?;
1431        let mut shards = BTreeMap::new();
1432        let shard = ShardIdent::new(-1, u64::from_str_radix("8000000000000000", 16)?).unwrap();
1433        split_shard_accounts(&shard, &accounts, 3, &mut shards)?;
1434        let merged = merge(shards)?;
1435        assert_eq!(accounts, merged);
1436        Ok(())
1437    }
1438
1439    fn merge(
1440        shard_accounts: BTreeMap<u64, ShardAccounts>,
1441    ) -> anyhow::Result<AugDict<HashBytes, DepthBalanceInfo, ShardAccount>> {
1442        let shard_accounts = {
1443            let mut stack = VecDeque::with_capacity(16);
1444            for accounts in shard_accounts.values() {
1445                for account in accounts.iter() {
1446                    let _ = account?;
1447                }
1448                stack.push_back(accounts);
1449            }
1450
1451            let d2 = stack[0].merge_with_right_sibling(stack[1])?;
1452            let d1 = stack[2].merge_with_right_sibling(stack[3])?;
1453            let d3 = stack[4].merge_with_right_sibling(stack[5])?;
1454            let d4 = stack[6].merge_with_right_sibling(stack[7])?;
1455
1456            let x1 = d2.merge_with_right_sibling(&d1)?;
1457            let x2 = d3.merge_with_right_sibling(&d4)?;
1458            x1.merge_with_right_sibling(&x2)?
1459        };
1460        Ok(shard_accounts)
1461    }
1462
1463    fn split_shard_accounts(
1464        shard: &ShardIdent,
1465        accounts: &ShardAccounts,
1466        depth: u8,
1467        shards: &mut BTreeMap<u64, ShardAccounts>,
1468    ) -> anyhow::Result<()> {
1469        fn split_shard_accounts_impl(
1470            shard: &ShardIdent,
1471            accounts: &ShardAccounts,
1472            depth: u8,
1473            shards: &mut BTreeMap<u64, ShardAccounts>,
1474            builder: &mut CellBuilder,
1475        ) -> anyhow::Result<()> {
1476            let (left_shard_ident, right_shard_ident) = 'split: {
1477                if depth > 0 {
1478                    if let Some((left, right)) = shard.split() {
1479                        break 'split (left, right);
1480                    }
1481                }
1482                shards.insert(shard.prefix(), accounts.clone());
1483                return Ok(());
1484            };
1485
1486            let (left_accounts, right_accounts) = {
1487                builder.clear_bits();
1488                let prefix_len = shard.prefix_len();
1489                if prefix_len > 0 {
1490                    builder.store_uint(shard.prefix() >> (64 - prefix_len), prefix_len)?;
1491                }
1492
1493                let (a1, a2) = accounts.split_by_prefix(&builder.as_data_slice())?;
1494                (a1, a2)
1495            };
1496
1497            split_shard_accounts_impl(
1498                &left_shard_ident,
1499                &left_accounts,
1500                depth - 1,
1501                shards,
1502                builder,
1503            )?;
1504            split_shard_accounts_impl(
1505                &right_shard_ident,
1506                &right_accounts,
1507                depth - 1,
1508                shards,
1509                builder,
1510            )
1511        }
1512
1513        split_shard_accounts_impl(shard, accounts, depth, shards, &mut CellBuilder::new())
1514    }
1515}
tycho_types/dict/aug.rs

tycho_types/dict/
aug.rs
