object_rainbow_append_tree/
lib.rs

1use std::{fmt::Debug, future::ready, marker::PhantomData};
2
3use object_rainbow::{
4    Enum, ExtraFor, Fetch, FullHash, Inline, InlineOutput, ListHashes, Object, Output, Parse,
5    ParseAsInline, ParseInline, ParseInput, PointInput, Tagged, ToOutput, Topological, Traversible,
6    assert_impl, numeric::Be,
7};
8use object_rainbow_point::{IntoPoint, Point};
9use typenum::{U256, Unsigned};
10
11#[derive(ToOutput, InlineOutput, Tagged, ListHashes, Topological, Parse)]
12#[topology(recursive)]
13struct Node<T, N, M> {
14    _capacity: PhantomData<N>,
15    _marker: PhantomData<M>,
16    #[tags(skip)]
17    #[parse(unchecked)]
18    #[topology(unchecked)]
19    prev: Option<Point<Self>>,
20    items: Vec<T>,
21}
22
23impl<T, N, M> Drop for Node<T, N, M> {
24    fn drop(&mut self) {
25        self.items.drain(..).rev().for_each(|_| {});
26        while let Some(prev) = self.prev.take()
27            && let Some(node) = prev.try_unwrap()
28        {
29            *self = node;
30        }
31    }
32}
33
34impl<T: std::fmt::Debug, N, M> std::fmt::Debug for Node<T, N, M> {
35    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
36        f.debug_struct("Node")
37            .field("_capacity", &self._capacity)
38            .field("_marker", &self._marker)
39            .field("prev", &self.prev)
40            .field("items", &self.items)
41            .finish()
42    }
43}
44
45assert_impl!(
46    impl<E, T, N, M> Object<E> for Node<T, N, M>
47    where
48        E: 'static + Send + Sync + Clone,
49        N: 'static + Send + Sync + Clone,
50        M: 'static + Send + Sync + Clone,
51        T: Inline<E>,
52    {
53    }
54);
55
56impl<T: PartialEq, N, M> PartialEq for Node<T, N, M> {
57    fn eq(&self, other: &Self) -> bool {
58        self.prev == other.prev && self.items == other.items
59    }
60}
61
62impl<T: Eq, N, M> Eq for Node<T, N, M> {}
63
64trait History: Sized + Send + Sync {
65    type History: Send + Sync;
66    type Block: Send + Sync;
67    const CAPACITY: u64;
68}
69
70trait ToContiguousOutput: History {
71    fn to_contiguous_output(&self, history: &Self::History, output: &mut impl Output);
72}
73
74trait ParseWithLen<I: ParseInput>: History {
75    fn parse_with_len(input: &mut I, len: u64) -> object_rainbow::Result<(Self, Self::History)>;
76}
77
78#[derive(Debug, thiserror::Error)]
79pub enum PushError<T> {
80    #[error("leaf overflow")]
81    LeafOverflow(T),
82    #[error("non-leaf overflow")]
83    NonLeafOverflow(T),
84    #[error("root overflow")]
85    RootOverflow(T),
86}
87
88impl<T> PushError<T> {
89    pub fn into_value(self) -> T {
90        match self {
91            PushError::LeafOverflow(value) => value,
92            PushError::NonLeafOverflow(value) => value,
93            PushError::RootOverflow(value) => value,
94        }
95    }
96}
97
98impl<T: 'static + Send + Sync + Debug> From<PushError<T>> for object_rainbow::Error {
99    fn from(value: PushError<T>) -> Self {
100        Self::operation(value)
101    }
102}
103
104trait Push: Clone + History {
105    type T: Send + Sync;
106    fn get(
107        &self,
108        index: u64,
109        history: Option<&Self::History>,
110    ) -> impl Send + Future<Output = object_rainbow::Result<Self::T>>;
111    fn push(
112        &mut self,
113        len: u64,
114        value: Self::T,
115        history: &mut Self::History,
116    ) -> Result<(), PushError<Self::T>>;
117    fn last<'a>(&'a self, history: &'a Self::History) -> Option<&'a Self::T>;
118    fn from_value(prev: Point<Self>, history: &mut Self::History, value: Self::T) -> Self;
119    fn to_point(&self, history: &Self::History) -> Point<Self>;
120}
121
122impl<T: Clone, N, M> Clone for Node<T, N, M> {
123    fn clone(&self) -> Self {
124        Self {
125            _capacity: PhantomData,
126            _marker: PhantomData,
127            prev: self.prev.clone(),
128            items: self.items.clone(),
129        }
130    }
131}
132
133impl<T, N, M> Default for Node<T, N, M> {
134    fn default() -> Self {
135        Self::new(None, Vec::new())
136    }
137}
138
139impl<T, N, M> Node<T, N, M> {
140    const fn new(prev: Option<Point<Self>>, items: Vec<T>) -> Self {
141        Self {
142            _capacity: PhantomData,
143            _marker: PhantomData,
144            prev,
145            items,
146        }
147    }
148}
149
150struct Leaf;
151
152impl<T: Send + Sync, N: Send + Sync + Unsigned> History for Node<T, N, Leaf> {
153    type History = ();
154    type Block = Self;
155    const CAPACITY: u64 = N::U64;
156}
157
158impl<T: InlineOutput + Send + Sync, N: Send + Sync + Unsigned> ToContiguousOutput
159    for Node<T, N, Leaf>
160{
161    fn to_contiguous_output(&self, (): &Self::History, output: &mut impl Output) {
162        self.to_output(output);
163    }
164}
165
166impl<T: ParseInline<I> + Send + Sync, N: Send + Sync + Unsigned, I: ParseInput> ParseWithLen<I>
167    for Node<T, N, Leaf>
168where
169    Point<Self>: ParseInline<I>,
170{
171    fn parse_with_len(input: &mut I, len: u64) -> object_rainbow::Result<(Self, Self::History)> {
172        if len > N::U64 {
173            return Err(object_rainbow::error_parse!("overflow"));
174        }
175        Ok((
176            Self::new(
177                input.parse_inline()?,
178                input.parse_vec_n(
179                    len.try_into()
180                        .map_err(|_| object_rainbow::error_parse!("overflow"))?,
181                )?,
182            ),
183            (),
184        ))
185    }
186}
187
188impl<T: Send + Sync + Clone + Traversible + InlineOutput, N: Send + Sync + Unsigned> Push
189    for Node<T, N, Leaf>
190{
191    type T = T;
192
193    fn get(
194        &self,
195        index: u64,
196        _: Option<&Self::History>,
197    ) -> impl Send + Future<Output = object_rainbow::Result<Self::T>> {
198        ready(
199            usize::try_from(index)
200                .map_err(|_| object_rainbow::Error::UnsupportedLength)
201                .and_then(|index| {
202                    self.items.get(index).cloned().ok_or_else(|| {
203                        object_rainbow::error_consistency!(
204                            "out of bounds L {index}/{}",
205                            self.items.len()
206                        )
207                    })
208                }),
209        )
210    }
211
212    fn push(
213        &mut self,
214        len: u64,
215        value: Self::T,
216        (): &mut Self::History,
217    ) -> Result<(), PushError<Self::T>> {
218        if len != (self.items.len() as u64) {
219            panic!("a node has been parsed with invalid length")
220        } else if self.items.len() >= N::USIZE {
221            Err(PushError::LeafOverflow(value))
222        } else {
223            self.items.push(value);
224            Ok(())
225        }
226    }
227
228    fn last<'a>(&'a self, (): &'a Self::History) -> Option<&'a Self::T> {
229        self.items.last()
230    }
231
232    fn from_value(prev: Point<Self>, (): &mut Self::History, value: Self::T) -> Self {
233        Self::new(Some(prev), vec![value])
234    }
235
236    fn to_point(&self, (): &Self::History) -> Point<Self> {
237        self.clone().point()
238    }
239}
240
241struct NonLeaf;
242
243impl<T: Send + Sync + History, N: Send + Sync + Unsigned> History for Node<Point<T>, N, NonLeaf> {
244    type History = (T, T::History);
245    type Block = T::Block;
246    const CAPACITY: u64 = N::U64.saturating_mul(T::CAPACITY);
247}
248
249impl<T: ToContiguousOutput, N: Send + Sync + Unsigned> ToContiguousOutput
250    for Node<Point<T>, N, NonLeaf>
251{
252    fn to_contiguous_output(&self, (child, history): &Self::History, output: &mut impl Output) {
253        self.prev.to_output(output);
254        self.items.to_output(output);
255        child.to_contiguous_output(history, output);
256    }
257}
258
259impl<
260    T: 'static + Send + Sync + ParseWithLen<I> + FullHash,
261    N: Send + Sync + Unsigned,
262    I: PointInput<Extra: Send + Sync + ExtraFor<T>>,
263> ParseWithLen<I> for Node<Point<T>, N, NonLeaf>
264where
265    Point<T>: ParseInline<I>,
266    Point<Self>: ParseInline<I>,
267{
268    fn parse_with_len(input: &mut I, len: u64) -> object_rainbow::Result<(Self, Self::History)> {
269        let own = len / T::CAPACITY
270            + if len.is_multiple_of(T::CAPACITY) {
271                0
272            } else {
273                1
274            };
275        if own > N::U64 {
276            return Err(object_rainbow::error_parse!("overflow"));
277        }
278        let prev = input.parse_inline()?;
279        let items = input.parse_vec_n::<Point<T>>(
280            own.saturating_sub(1)
281                .try_into()
282                .map_err(|_| object_rainbow::error_parse!("overflow"))?,
283        )?;
284        let history = T::parse_with_len(
285            input,
286            if len.is_multiple_of(T::CAPACITY) {
287                T::CAPACITY
288            } else {
289                len % T::CAPACITY
290            },
291        )?;
292        Ok((Self::new(prev, items), history))
293    }
294}
295
296impl<T: Push + Traversible, N: Send + Sync + Unsigned> Push for Node<Point<T>, N, NonLeaf> {
297    type T = T::T;
298
299    fn get(
300        &self,
301        index: u64,
302        history: Option<&Self::History>,
303    ) -> impl Send + Future<Output = object_rainbow::Result<Self::T>> {
304        async move {
305            let n = usize::try_from(index / T::CAPACITY)
306                .map_err(|_| object_rainbow::Error::UnsupportedLength)?;
307            let r = index % T::CAPACITY;
308            println!("g {n} {}", self.items.len());
309            if let Some((node, history)) = history
310                && n == self.items.len()
311            {
312                println!("AAA");
313                node.get(r, Some(history)).await
314            } else {
315                println!("BBB");
316                self.items
317                    .get(n)
318                    .ok_or_else(|| {
319                        object_rainbow::error_consistency!(
320                            "out of bounds N {n}/{}",
321                            self.items.len(),
322                        )
323                    })?
324                    .fetch()
325                    .await?
326                    .get(r, None)
327                    .await
328            }
329        }
330    }
331
332    fn push(
333        &mut self,
334        len: u64,
335        value: Self::T,
336        (node, history): &mut Self::History,
337    ) -> Result<(), PushError<Self::T>> {
338        if len.is_multiple_of(T::CAPACITY) {
339            if len / T::CAPACITY != (self.items.len() as u64 + 1) {
340                panic!("a node has been parsed with invalid length");
341            }
342            if (self.items.len() + 1) >= N::USIZE {
343                return Err(PushError::NonLeafOverflow(value));
344            }
345            let node =
346                std::mem::replace(node, T::from_value(node.to_point(history), history, value));
347            self.items.push(node.point());
348            Ok(())
349        } else {
350            node.push(len % T::CAPACITY, value, history)?;
351            Ok(())
352        }
353    }
354
355    fn last<'a>(&'a self, (node, history): &'a Self::History) -> Option<&'a Self::T> {
356        node.last(history)
357    }
358
359    fn from_value(prev: Point<Self>, (child, history): &mut Self::History, value: Self::T) -> Self {
360        *child = T::from_value(child.clone().point(), history, value);
361        Self::new(Some(prev), vec![])
362    }
363
364    fn to_point(&self, (child, history): &Self::History) -> Point<Self> {
365        let mut node = self.clone();
366        node.items.push(child.to_point(history));
367        node.point()
368    }
369}
370
371impl<T: Push<History: Clone> + Traversible, N: Send + Sync + Unsigned> Node<Point<T>, N, NonLeaf> {
372    fn from_inner(
373        inner: T,
374        history: &mut T::History,
375        value: T::T,
376    ) -> (Self, <Self as History>::History) {
377        let inner = inner.point();
378        let next = T::from_value(inner.clone(), history, value);
379        let parent = Self::new(None, vec![inner]);
380        (parent, (next, history.clone()))
381    }
382}
383
384type N1<T> = Node<T, U256, Leaf>;
385type N2<T> = Node<Point<N1<T>>, U256, NonLeaf>;
386type N3<T> = Node<Point<N2<T>>, U256, NonLeaf>;
387type N4<T> = Node<Point<N3<T>>, U256, NonLeaf>;
388type N5<T> = Node<Point<N4<T>>, U256, NonLeaf>;
389type N6<T> = Node<Point<N5<T>>, U256, NonLeaf>;
390type N7<T> = Node<Point<N6<T>>, U256, NonLeaf>;
391type N8<T> = Node<Point<N7<T>>, U256, NonLeaf>;
392
393assert_impl!(
394    impl<T> Push for N1<T> where T: Send + Sync + Clone + Traversible + InlineOutput {}
395);
396assert_impl!(
397    impl<T> Push for N2<T> where T: Send + Sync + Clone + Traversible + InlineOutput {}
398);
399assert_impl!(
400    impl<T> Push for N3<T> where T: Send + Sync + Clone + Traversible + InlineOutput {}
401);
402assert_impl!(
403    impl<T> Push for N4<T> where T: Send + Sync + Clone + Traversible + InlineOutput {}
404);
405assert_impl!(
406    impl<T> Push for N5<T> where T: Send + Sync + Clone + Traversible + InlineOutput {}
407);
408assert_impl!(
409    impl<T> Push for N6<T> where T: Send + Sync + Clone + Traversible + InlineOutput {}
410);
411assert_impl!(
412    impl<T> Push for N7<T> where T: Send + Sync + Clone + Traversible + InlineOutput {}
413);
414assert_impl!(
415    impl<T> Push for N8<T> where T: Send + Sync + Clone + Traversible + InlineOutput {}
416);
417
418type H1 = ();
419type H2<T> = (N1<T>, H1);
420type H3<T> = (N2<T>, H2<T>);
421type H4<T> = (N3<T>, H3<T>);
422type H5<T> = (N4<T>, H4<T>);
423type H6<T> = (N5<T>, H5<T>);
424type H7<T> = (N6<T>, H6<T>);
425type H8<T> = (N7<T>, H7<T>);
426
427#[derive(Enum, Tagged, ListHashes, Topological, Clone, PartialEq, Eq, Debug)]
428enum TreeKind<T> {
429    N1((N1<T>, H1)),
430    N2((N2<T>, H2<T>)),
431    N3((N3<T>, H3<T>)),
432    N4((N4<T>, H4<T>)),
433    N5((N5<T>, H5<T>)),
434    N6((N6<T>, H6<T>)),
435    N7((N7<T>, H7<T>)),
436    N8((N8<T>, H8<T>)),
437}
438
439#[derive(Tagged, ListHashes, Topological, Clone, ParseAsInline, PartialEq, Eq, Debug)]
440pub struct AppendTree<T> {
441    len: Be<u64>,
442    kind: TreeKind<T>,
443}
444
445impl<T: Send + Sync + InlineOutput> ToOutput for AppendTree<T> {
446    fn to_output(&self, output: &mut impl Output) {
447        self.len.to_output(output);
448        match &self.kind {
449            TreeKind::N1((node, history)) => node.to_contiguous_output(history, output),
450            TreeKind::N2((node, history)) => node.to_contiguous_output(history, output),
451            TreeKind::N3((node, history)) => node.to_contiguous_output(history, output),
452            TreeKind::N4((node, history)) => node.to_contiguous_output(history, output),
453            TreeKind::N5((node, history)) => node.to_contiguous_output(history, output),
454            TreeKind::N6((node, history)) => node.to_contiguous_output(history, output),
455            TreeKind::N7((node, history)) => node.to_contiguous_output(history, output),
456            TreeKind::N8((node, history)) => node.to_contiguous_output(history, output),
457        }
458    }
459}
460
461impl<T: Send + Sync + InlineOutput> InlineOutput for AppendTree<T> {}
462
463const C1: u64 = 256;
464const C2: u64 = 256 * C1;
465const C3: u64 = 256 * C2;
466const C4: u64 = 256 * C3;
467const C5: u64 = 256 * C4;
468const C6: u64 = 256 * C5;
469const C7: u64 = 256 * C6;
470const C8: u64 = C7.saturating_mul(256);
471const C2_MIN: u64 = C1 + 1;
472const C3_MIN: u64 = C2 + 1;
473const C4_MIN: u64 = C3 + 1;
474const C5_MIN: u64 = C4 + 1;
475const C6_MIN: u64 = C5 + 1;
476const C7_MIN: u64 = C6 + 1;
477const C8_MIN: u64 = C7 + 1;
478
479impl<T, I: ParseInput> ParseInline<I> for AppendTree<T>
480where
481    N1<T>: ParseWithLen<I, History = H1>,
482    N2<T>: ParseWithLen<I, History = H2<T>>,
483    N3<T>: ParseWithLen<I, History = H3<T>>,
484    N4<T>: ParseWithLen<I, History = H4<T>>,
485    N5<T>: ParseWithLen<I, History = H5<T>>,
486    N6<T>: ParseWithLen<I, History = H6<T>>,
487    N7<T>: ParseWithLen<I, History = H7<T>>,
488    N8<T>: ParseWithLen<I, History = H8<T>>,
489{
490    fn parse_inline(input: &mut I) -> object_rainbow::Result<Self> {
491        let len = input.parse_inline::<Be<u64>>()?;
492        let kind = match len.0 {
493            0..=C1 => TreeKind::N1(N1::<T>::parse_with_len(input, len.0)?),
494            C2_MIN..=C2 => TreeKind::N2(N2::<T>::parse_with_len(input, len.0)?),
495            C3_MIN..=C3 => TreeKind::N3(N3::<T>::parse_with_len(input, len.0)?),
496            C4_MIN..=C4 => TreeKind::N4(N4::<T>::parse_with_len(input, len.0)?),
497            C5_MIN..=C5 => TreeKind::N5(N5::<T>::parse_with_len(input, len.0)?),
498            C6_MIN..=C6 => TreeKind::N6(N6::<T>::parse_with_len(input, len.0)?),
499            C7_MIN..=C7 => TreeKind::N7(N7::<T>::parse_with_len(input, len.0)?),
500            C8_MIN..=C8 => TreeKind::N8(N8::<T>::parse_with_len(input, len.0)?),
501        };
502        Ok(Self { len, kind })
503    }
504}
505
506assert_impl!(
507    impl<T, E> Inline<E> for AppendTree<T>
508    where
509        E: 'static + Send + Sync + Clone,
510        T: Inline<E>,
511    {
512    }
513);
514
515impl<T: Send + Sync + Clone + Traversible + InlineOutput> AppendTree<T> {
516    pub const fn new() -> Self {
517        Self {
518            len: Be::<u64>::new(0u64),
519            kind: TreeKind::N1((Node::new(None, Vec::new()), ())),
520        }
521    }
522
523    pub async fn get(&self, index: u64) -> object_rainbow::Result<Option<T>> {
524        if index < self.len.0 {
525            match &self.kind {
526                TreeKind::N1((node, history)) => node.get(index, Some(history)).await,
527                TreeKind::N2((node, history)) => node.get(index, Some(history)).await,
528                TreeKind::N3((node, history)) => node.get(index, Some(history)).await,
529                TreeKind::N4((node, history)) => node.get(index, Some(history)).await,
530                TreeKind::N5((node, history)) => node.get(index, Some(history)).await,
531                TreeKind::N6((node, history)) => node.get(index, Some(history)).await,
532                TreeKind::N7((node, history)) => node.get(index, Some(history)).await,
533                TreeKind::N8((node, history)) => node.get(index, Some(history)).await,
534            }
535            .map(Some)
536        } else {
537            Ok(None)
538        }
539    }
540
541    pub fn push(&mut self, value: T) -> Result<(), PushError<T>> {
542        let len = self.len.0;
543        macro_rules! upgrade {
544            ($history:ident, $node:ident, $child:ident, $parent:ident) => {
545                if len == $child::<T>::CAPACITY {
546                    self.kind =
547                        TreeKind::$parent(Node::from_inner(std::mem::take($node), $history, value));
548                } else {
549                    $node.push(len, value, $history)?;
550                }
551            };
552        }
553        match &mut self.kind {
554            TreeKind::N1((node, history)) => upgrade!(history, node, N1, N2),
555            TreeKind::N2((node, history)) => upgrade!(history, node, N2, N3),
556            TreeKind::N3((node, history)) => upgrade!(history, node, N3, N4),
557            TreeKind::N4((node, history)) => upgrade!(history, node, N4, N5),
558            TreeKind::N5((node, history)) => upgrade!(history, node, N5, N6),
559            TreeKind::N6((node, history)) => upgrade!(history, node, N6, N7),
560            TreeKind::N7((node, history)) => upgrade!(history, node, N7, N8),
561            TreeKind::N8((node, history)) => {
562                if len == N8::<T>::CAPACITY {
563                    return Err(PushError::RootOverflow(value));
564                } else {
565                    node.push(len, value, history)?;
566                }
567            }
568        }
569        self.len.0 += 1;
570        Ok(())
571    }
572
573    pub fn is_empty(&self) -> bool {
574        self.len.0 == 0
575    }
576
577    pub fn len(&self) -> u64 {
578        self.len.0
579    }
580
581    pub fn last(&self) -> Option<&T> {
582        match &self.kind {
583            TreeKind::N1((node, history)) => Push::last(node, history),
584            TreeKind::N2((node, history)) => Push::last(node, history),
585            TreeKind::N3((node, history)) => Push::last(node, history),
586            TreeKind::N4((node, history)) => Push::last(node, history),
587            TreeKind::N5((node, history)) => Push::last(node, history),
588            TreeKind::N6((node, history)) => Push::last(node, history),
589            TreeKind::N7((node, history)) => Push::last(node, history),
590            TreeKind::N8((node, history)) => Push::last(node, history),
591        }
592    }
593}
594
595impl<T: Send + Sync + Clone + Traversible + InlineOutput> Default for AppendTree<T> {
596    fn default() -> Self {
597        Self::new()
598    }
599}
600
601#[cfg(test)]
602mod test {
603    use macro_rules_attribute::apply;
604    use object_rainbow::{ParseSlice, numeric::Le};
605    use smol_macros::test;
606
607    use crate::AppendTree;
608
609    #[apply(test!)]
610    async fn reparse() -> object_rainbow::Result<()> {
611        let mut tree = AppendTree::<Le<u64>>::new();
612        for i in 0..100_000u64 {
613            tree.push(Le(i))?;
614            let new = tree.reparse()?;
615            assert_eq!(new, tree);
616            tree = new;
617            assert_eq!(tree.get(i).await?.unwrap().0, i);
618        }
619        Ok(())
620    }
621
622    #[apply(test!)]
623    async fn get() -> object_rainbow::Result<()> {
624        let mut tree = AppendTree::<Le<u64>>::new();
625        for i in 0..100_000u64 {
626            tree.push(Le(i))?;
627            assert_eq!(tree.get(i).await?.unwrap().0, i);
628            assert_eq!(tree.get(i / 2).await?.unwrap().0, i / 2);
629            assert_eq!(tree.get(i / 3).await?.unwrap().0, i / 3);
630            assert_eq!(tree.get(i / 17).await?.unwrap().0, i / 17);
631            assert_eq!(tree.get(i / 101).await?.unwrap().0, i / 101);
632        }
633        Ok(())
634    }
635}
object_rainbow_append_tree/lib.rs

object_rainbow_append_tree/
lib.rs
