object_rainbow/
lib.rs

1#![forbid(unsafe_code)]
2#![cfg_attr(docsrs, feature(doc_cfg))]
3#![cfg_attr(docsrs, doc(cfg_hide(doc)))]
4
5extern crate self as object_rainbow;
6
7use std::{
8    any::Any,
9    borrow::Cow,
10    cell::Cell,
11    cmp::Ordering,
12    convert::Infallible,
13    future::ready,
14    marker::PhantomData,
15    ops::{Add, Deref, DerefMut, Sub},
16    pin::Pin,
17    sync::Arc,
18};
19
20pub use anyhow::anyhow;
21use generic_array::{ArrayLength, GenericArray, functional::FunctionalSequence, sequence::Split};
22pub use object_rainbow_derive::{
23    Enum, InlineOutput, ListHashes, MaybeHasNiche, Parse, ParseAsInline, ParseInline, Size, Tagged,
24    ToOutput, Topological, derive_for_wrapped,
25};
26use sha2::{Digest, Sha256};
27#[doc(hidden)]
28pub use typenum;
29use typenum::Unsigned;
30
31#[doc(hidden)]
32pub use self::niche::{MaybeNiche, MnArray, NicheFoldOrArray, NicheOr};
33pub use self::{
34    enumkind::Enum,
35    error::{Error, Result},
36    hash::{Hash, OptionalHash},
37    monostate::Monostate,
38    niche::{
39        AutoEnumNiche, AutoNiche, HackNiche, MaybeHasNiche, MinNiche, Niche, NicheForUnsized,
40        NoNiche, OneNiche, SomeNiche, ZeroNiche, ZeroNoNiche,
41    },
42    ordering::{ByteOrd, OrderedByBytes, SignificantLength},
43};
44
45pub mod ascii;
46mod assert_impl;
47pub mod decr_byte_niche;
48pub mod default_chain;
49pub mod default_terminated;
50pub mod enumkind;
51mod error;
52pub mod extras;
53pub mod ff;
54mod hash;
55pub mod hashed;
56mod impls;
57pub mod incr_byte_niche;
58pub mod inline_extra;
59pub mod length_prefixed;
60pub mod map_extra;
61mod monostate;
62pub mod monostate_headers;
63pub mod nested_mut;
64mod niche;
65pub mod niche_cut;
66pub mod none_terminated;
67pub mod numeric;
68pub mod object_marker;
69mod ordering;
70pub mod parse_extra;
71pub mod partial_byte_tag;
72pub mod sequence;
73pub mod tuple_extra;
74pub mod tuple_of_arrays;
75pub mod u63;
76pub mod with_repr;
77pub mod zero_terminated;
78
79/// SHA-256 hash size in bytes.
80pub const HASH_SIZE: usize = sha2_const::Sha256::DIGEST_SIZE;
81
82/// Address within a [`PointInput`].
83///
84/// This was introduced:
85/// - to avoid using a [`Hash`]-only map
86/// - to differentiate between separate [`Hash`]es within a context
87#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, ParseAsInline)]
88pub struct Address {
89    /// Monotonically incremented index. This is not present at all in the actual format.
90    pub index: usize,
91    /// Only this part is part of the parsed/generated input.
92    pub hash: Hash,
93}
94
95impl Address {
96    /// Construct an address which is invalid within parsing context, but can be used in map-based
97    /// [`Resolve`]s.
98    pub fn from_hash(hash: Hash) -> Self {
99        Self {
100            index: usize::MAX,
101            hash,
102        }
103    }
104}
105
106impl ToOutput for Address {
107    fn to_output(&self, output: &mut impl Output) {
108        self.hash.to_output(output);
109    }
110}
111
112impl InlineOutput for Address {}
113
114impl ListHashes for Address {
115    fn list_hashes(&self, f: &mut impl FnMut(Hash)) {
116        f(self.hash);
117    }
118}
119
120impl<I: PointInput> ParseInline<I> for Address {
121    fn parse_inline(input: &mut I) -> crate::Result<Self> {
122        Ok(Self {
123            index: input.next_index(),
124            hash: input.parse_inline()?,
125        })
126    }
127}
128
129/// Fallible future type yielding either `T` or [`Error`].
130pub type FailFuture<'a, T> = Pin<Box<dyn 'a + Send + Future<Output = Result<T>>>>;
131
132pub type Node<T> = (T, Arc<dyn Resolve>);
133
134/// Returned by [`Resolve`] and [`FetchBytes`]. Represents traversal through the object graph.
135pub type ByteNode = Node<Vec<u8>>;
136
137/// Trait for contextually using [`Any`]. Can itself be implemented for non-`'static` and `?Sized`
138/// types, and is `dyn`-compatible.
139pub trait AsAny {
140    /// Get a shared RTTI reference.
141    fn any_ref(&self) -> &dyn Any
142    where
143        Self: 'static;
144    /// Get an exclusive RTTI reference.
145    fn any_mut(&mut self) -> &mut dyn Any
146    where
147        Self: 'static;
148    /// Get an RTTI [`Box`].
149    fn any_box(self: Box<Self>) -> Box<dyn Any>
150    where
151        Self: 'static;
152    /// Get an RTTI [`Arc`].
153    fn any_arc(self: Arc<Self>) -> Arc<dyn Any>
154    where
155        Self: 'static;
156    /// Get an RTTI [`Arc`] which is also [`Send`].
157    fn any_arc_sync(self: Arc<Self>) -> Arc<dyn Send + Sync + Any>
158    where
159        Self: 'static + Send + Sync;
160}
161
162impl<T> AsAny for T {
163    fn any_ref(&self) -> &dyn Any
164    where
165        Self: 'static,
166    {
167        self
168    }
169
170    fn any_mut(&mut self) -> &mut dyn Any
171    where
172        Self: 'static,
173    {
174        self
175    }
176
177    fn any_box(self: Box<Self>) -> Box<dyn Any>
178    where
179        Self: 'static,
180    {
181        self
182    }
183
184    fn any_arc(self: Arc<Self>) -> Arc<dyn Any>
185    where
186        Self: 'static,
187    {
188        self
189    }
190
191    fn any_arc_sync(self: Arc<Self>) -> Arc<dyn Send + Sync + Any>
192    where
193        Self: 'static + Send + Sync,
194    {
195        self
196    }
197}
198
199/// Something that can resolve [`Address`]es to [`ByteNode`]s.
200pub trait Resolve: Send + Sync + AsAny {
201    /// Resolve the address. For an [`Object`], this is what gets used as [`PointInput`].
202    fn resolve<'a>(
203        &'a self,
204        address: Address,
205        this: &'a Arc<dyn Resolve>,
206    ) -> FailFuture<'a, ByteNode>;
207    fn resolve_data(&'_ self, address: Address) -> FailFuture<'_, Vec<u8>>;
208    fn try_resolve_local(
209        &self,
210        address: Address,
211        this: &Arc<dyn Resolve>,
212    ) -> Result<Option<ByteNode>> {
213        let _ = address;
214        let _ = this;
215        Ok(None)
216    }
217    fn topology_hash(&self) -> Option<Hash> {
218        None
219    }
220    fn into_topovec(self: Arc<Self>) -> Option<TopoVec> {
221        None
222    }
223}
224
225impl ToOutput for dyn Resolve {
226    fn to_output(&self, _: &mut impl Output) {}
227}
228
229impl InlineOutput for dyn Resolve {}
230
231impl<I: PointInput> Parse<I> for Arc<dyn Resolve> {
232    fn parse(input: I) -> crate::Result<Self> {
233        Self::parse_as_inline(input)
234    }
235}
236
237impl<I: PointInput> ParseInline<I> for Arc<dyn Resolve> {
238    fn parse_inline(input: &mut I) -> crate::Result<Self> {
239        Ok(input.resolve())
240    }
241}
242
243pub trait FetchBytes: AsAny {
244    fn fetch_bytes(&'_ self) -> FailFuture<'_, ByteNode>;
245    fn fetch_data(&'_ self) -> FailFuture<'_, Vec<u8>>;
246    fn fetch_bytes_local(&self) -> Result<Option<ByteNode>> {
247        Ok(None)
248    }
249    fn fetch_data_local(&self) -> Option<Vec<u8>> {
250        None
251    }
252    fn as_inner(&self) -> Option<&dyn Any> {
253        None
254    }
255    fn as_resolve(&self) -> Option<&Arc<dyn Resolve>> {
256        None
257    }
258    fn try_unwrap_resolve(self: Arc<Self>) -> Option<Arc<dyn Resolve>> {
259        None
260    }
261}
262
263pub trait Fetch: Send + Sync + FetchBytes {
264    type T;
265    fn fetch_full(&'_ self) -> FailFuture<'_, Node<Self::T>>;
266    fn fetch(&'_ self) -> FailFuture<'_, Self::T>;
267    fn try_fetch_local(&self) -> Result<Option<Node<Self::T>>> {
268        Ok(None)
269    }
270    fn fetch_local(&self) -> Option<Self::T> {
271        None
272    }
273    fn get(&self) -> Option<&Self::T> {
274        None
275    }
276    fn get_mut(&mut self) -> Option<&mut Self::T> {
277        None
278    }
279    fn get_mut_finalize(&mut self) {}
280    fn try_unwrap(self: Arc<Self>) -> Option<Self::T> {
281        None
282    }
283    fn into_dyn_fetch<'a>(self) -> Arc<dyn 'a + Fetch<T = Self::T>>
284    where
285        Self: 'a + Sized,
286    {
287        Arc::new(self)
288    }
289}
290
291pub trait PointVisitor {
292    fn visit(&mut self, point: &(impl 'static + SingularFetch<T: Traversible> + Clone));
293}
294
295struct ReflessData<'d> {
296    slice: &'d [u8],
297    prefix: Vec<Vec<u8>>,
298}
299
300impl<'a> ReflessData<'a> {
301    fn split_at_checked(&self, mut n: usize) -> Option<(Self, Self)> {
302        let mut prefix_l = Vec::new();
303        let mut prefix_r = self.prefix.clone();
304        while n > 0
305            && let Some(front) = prefix_r.last_mut()
306        {
307            if n < front.len() {
308                n = 0;
309                prefix_l.push(Vec::from(&front[..n]));
310                front.drain(..n);
311            } else {
312                n -= front.len();
313                prefix_l.push(prefix_r.pop().expect("last element is known to exist"));
314            }
315        }
316        prefix_l.reverse();
317        self.slice.split_at_checked(n).map(|(slice_l, slice_r)| {
318            (
319                Self {
320                    slice: slice_l,
321                    prefix: prefix_l,
322                },
323                Self {
324                    slice: slice_r,
325                    prefix: prefix_r,
326                },
327            )
328        })
329    }
330
331    fn len(&self) -> usize {
332        self.slice.len() + self.prefix.iter().map(|v| v.len()).sum::<usize>()
333    }
334
335    fn is_empty(&self) -> bool {
336        self.slice.is_empty() && self.prefix.iter().all(|v| v.is_empty())
337    }
338
339    fn starts_with(&self, mut prefix: &[u8]) -> bool {
340        for chunk in self.prefix.iter().rev() {
341            if chunk.starts_with(prefix) {
342                return true;
343            }
344            if let Some(rest) = prefix.strip_prefix(&**chunk) {
345                prefix = rest;
346            } else {
347                return false;
348            }
349        }
350        self.slice.starts_with(prefix)
351    }
352
353    fn cow(&self) -> Cow<'a, [u8]> {
354        if self.prefix.iter().all(|v| v.is_empty()) {
355            Cow::from(self.slice)
356        } else {
357            let mut vec = Vec::with_capacity(self.len());
358            for v in self.prefix.iter().rev() {
359                vec.extend_from_slice(v);
360            }
361            vec.extend_from_slice(self.slice);
362            Cow::from(vec)
363        }
364    }
365
366    fn iter(&self) -> impl Iterator<Item = &u8> {
367        self.prefix.iter().rev().flatten().chain(self.slice)
368    }
369}
370
371pub struct ReflessInput<'d> {
372    data: Option<ReflessData<'d>>,
373}
374
375pub struct Input<'d, Extra: Clone = ()> {
376    refless: ReflessInput<'d>,
377    resolve: Cow<'d, Arc<dyn Resolve>>,
378    index: &'d Cell<usize>,
379    extra: Cow<'d, Extra>,
380}
381
382impl<'a, Extra: Clone> Deref for Input<'a, Extra> {
383    type Target = ReflessInput<'a>;
384
385    fn deref(&self) -> &Self::Target {
386        &self.refless
387    }
388}
389
390impl<Extra: Clone> DerefMut for Input<'_, Extra> {
391    fn deref_mut(&mut self) -> &mut Self::Target {
392        &mut self.refless
393    }
394}
395
396impl<'a> ReflessInput<'a> {
397    fn data(&self) -> crate::Result<&ReflessData<'a>> {
398        self.data.as_ref().ok_or(Error::EndOfInput)
399    }
400
401    fn data_mut(&mut self) -> crate::Result<&mut ReflessData<'a>> {
402        self.data.as_mut().ok_or(Error::EndOfInput)
403    }
404
405    fn make_error<T>(&mut self, e: crate::Error) -> crate::Result<T> {
406        self.data = None;
407        Err(e)
408    }
409
410    fn end_of_input<T>(&mut self) -> crate::Result<T> {
411        self.make_error(Error::EndOfInput)
412    }
413}
414
415impl<'d> ParseInput for ReflessInput<'d> {
416    type Data = Cow<'d, [u8]>;
417
418    fn push_front(&mut self, data: impl Into<Vec<u8>>) -> crate::Result<()> {
419        let data = data.into();
420        if !data.is_empty() {
421            self.data_mut()?.prefix.push(data);
422        }
423        Ok(())
424    }
425
426    fn read(&mut self, mut data: &mut [u8]) -> crate::Result<()> {
427        match self.data()?.split_at_checked(data.len()) {
428            Some((chunk, rest)) => {
429                self.data = Some(rest);
430                for v in chunk.prefix.iter().rev() {
431                    let part;
432                    (part, data) = data.split_at_mut(v.len());
433                    part.copy_from_slice(v);
434                }
435                data.copy_from_slice(chunk.slice);
436                Ok(())
437            }
438            None => self.end_of_input(),
439        }
440    }
441
442    fn split_n(&mut self, n: usize) -> crate::Result<Self> {
443        match self.data()?.split_at_checked(n) {
444            Some((chunk, rest)) => {
445                self.data = Some(rest);
446                Ok(Self { data: Some(chunk) })
447            }
448            None => self.end_of_input(),
449        }
450    }
451
452    fn skip_n(&mut self, n: usize) -> crate::Result<()> {
453        match self.data()?.split_at_checked(n) {
454            Some((_, rest)) => {
455                self.data = Some(rest);
456                Ok(())
457            }
458            None => self.end_of_input(),
459        }
460    }
461
462    fn find_zero(&mut self) -> crate::Result<usize> {
463        let found = self.data()?.iter().enumerate().find(|(_, x)| **x == 0);
464        match found {
465            Some((at, _)) => Ok(at),
466            None => self.end_of_input(),
467        }
468    }
469
470    fn parse_n_ahead(&mut self, n: usize) -> crate::Result<Vec<u8>> {
471        match self.data()?.split_at_checked(n) {
472            Some((data, _)) => Ok(data.cow().into_owned()),
473            None => self.end_of_input(),
474        }
475    }
476
477    fn compare_ahead(&mut self, c: &[u8]) -> crate::Result<bool> {
478        let data = self.data()?;
479        if data.len() < c.len() {
480            self.end_of_input()
481        } else {
482            Ok(data.starts_with(c))
483        }
484    }
485
486    fn parse_all(self) -> crate::Result<Self::Data> {
487        self.data().map(|data| data.cow())
488    }
489
490    fn empty(self) -> crate::Result<()> {
491        if self.data()?.is_empty() {
492            Ok(())
493        } else {
494            Err(Error::ExtraInputLeft)
495        }
496    }
497
498    fn non_empty(self) -> crate::Result<Option<Self>> {
499        Ok(if self.data()?.is_empty() {
500            None
501        } else {
502            Some(self)
503        })
504    }
505
506    fn remaining(self) -> crate::Result<(Self, usize)> {
507        let len = self.data()?.len();
508        Ok((self, len))
509    }
510
511    fn parse_refless_inline<T: for<'r> ParseInline<ReflessInput<'r>>>(
512        &mut self,
513    ) -> crate::Result<T> {
514        self.parse_inline()
515    }
516
517    fn parse_refless<T: for<'r> Parse<ReflessInput<'r>>>(self) -> crate::Result<T> {
518        self.parse()
519    }
520}
521
522impl<'d, Extra: Clone> ParseInput for Input<'d, Extra> {
523    type Data = Cow<'d, [u8]>;
524
525    fn push_front(&mut self, data: impl Into<Vec<u8>>) -> crate::Result<()> {
526        (**self).push_front(data)
527    }
528
529    fn read(&mut self, data: &mut [u8]) -> crate::Result<()> {
530        (**self).read(data)
531    }
532
533    fn split_n(&mut self, n: usize) -> crate::Result<Self> {
534        Ok(Self {
535            refless: self.refless.split_n(n)?,
536            resolve: self.resolve.clone(),
537            index: self.index,
538            extra: self.extra.clone(),
539        })
540    }
541
542    fn skip_n(&mut self, n: usize) -> crate::Result<()> {
543        (**self).skip_n(n)
544    }
545
546    fn find_zero(&mut self) -> crate::Result<usize> {
547        (**self).find_zero()
548    }
549
550    fn parse_n_ahead(&mut self, n: usize) -> crate::Result<Vec<u8>> {
551        (**self).parse_n_ahead(n)
552    }
553
554    fn compare_ahead(&mut self, c: &[u8]) -> crate::Result<bool> {
555        (**self).compare_ahead(c)
556    }
557
558    fn parse_all(self) -> crate::Result<Self::Data> {
559        self.refless.parse_all()
560    }
561
562    fn empty(self) -> crate::Result<()> {
563        self.refless.empty()
564    }
565
566    fn non_empty(mut self) -> crate::Result<Option<Self>> {
567        self.refless = match self.refless.non_empty()? {
568            Some(refless) => refless,
569            None => return Ok(None),
570        };
571        Ok(Some(self))
572    }
573
574    fn remaining(mut self) -> crate::Result<(Self, usize)> {
575        let remaining;
576        (self.refless, remaining) = self.refless.remaining()?;
577        Ok((self, remaining))
578    }
579
580    fn parse_refless_inline<T: for<'r> ParseInline<ReflessInput<'r>>>(
581        &mut self,
582    ) -> crate::Result<T> {
583        (**self).parse_refless_inline()
584    }
585
586    fn parse_refless<T: for<'r> Parse<ReflessInput<'r>>>(self) -> crate::Result<T> {
587        self.refless.parse_refless()
588    }
589}
590
591impl<'d, Extra: 'static + Clone> PointInput for Input<'d, Extra> {
592    type Extra = Extra;
593    type WithExtra<E: 'static + Clone> = Input<'d, E>;
594
595    fn next_index(&mut self) -> usize {
596        let index = self.index.get();
597        self.index.set(index + 1);
598        index
599    }
600
601    fn resolve_arc_ref(&self) -> &Arc<dyn Resolve> {
602        &self.resolve
603    }
604
605    fn with_resolve(mut self, resolve: Arc<dyn Resolve>) -> Self {
606        self.resolve = Cow::Owned(resolve);
607        self
608    }
609
610    fn extra(&self) -> &Self::Extra {
611        &self.extra
612    }
613
614    fn map_extra<E: 'static + Clone>(
615        self,
616        f: impl FnOnce(&Self::Extra) -> &E,
617    ) -> Self::WithExtra<E> {
618        let Self {
619            refless,
620            resolve,
621            index,
622            extra,
623        } = self;
624        Input {
625            refless,
626            resolve,
627            index,
628            extra: match extra {
629                Cow::Borrowed(extra) => Cow::Borrowed(f(extra)),
630                Cow::Owned(extra) => Cow::Owned(f(&extra).clone()),
631            },
632        }
633    }
634
635    fn replace_extra<E: 'static + Clone>(self, e: E) -> (Extra, Self::WithExtra<E>) {
636        let Self {
637            refless,
638            resolve,
639            index,
640            extra,
641        } = self;
642        (
643            extra.into_owned(),
644            Input {
645                refless,
646                resolve,
647                index,
648                extra: Cow::Owned(e),
649            },
650        )
651    }
652
653    fn with_extra<E: 'static + Clone>(self, extra: E) -> Self::WithExtra<E> {
654        let Self {
655            refless,
656            resolve,
657            index,
658            ..
659        } = self;
660        Input {
661            refless,
662            resolve,
663            index,
664            extra: Cow::Owned(extra),
665        }
666    }
667
668    fn parse_inline_extra<E: 'static + Clone, T: ParseInline<Self::WithExtra<E>>>(
669        &mut self,
670        extra: E,
671    ) -> crate::Result<T> {
672        let Self {
673            refless,
674            resolve,
675            index,
676            ..
677        } = self;
678        let data = refless.data.take();
679        let resolve = resolve.clone();
680        let mut input = Input {
681            refless: ReflessInput { data },
682            resolve,
683            index,
684            extra: Cow::Owned(extra),
685        };
686        let value = input.parse_inline()?;
687        refless.data = input.refless.data.take();
688        Ok(value)
689    }
690}
691
692/// Values of this type can be uniquely represented as a `Vec<u8>`.
693pub trait ToOutput {
694    fn to_output(&self, output: &mut impl Output);
695
696    #[must_use]
697    fn data_hash(&self) -> Hash {
698        #[derive(Default)]
699        struct HashOutput {
700            hasher: Sha256,
701            at: usize,
702        }
703
704        impl Output for HashOutput {
705            fn write(&mut self, data: &[u8]) {
706                self.hasher.update(data);
707                self.at += data.len();
708            }
709        }
710
711        impl HashOutput {
712            fn hash(self) -> Hash {
713                Hash::from_sha256(self.hasher.finalize().into())
714            }
715        }
716
717        let mut output = HashOutput::default();
718        self.to_output(&mut output);
719        output.hash()
720    }
721
722    fn mangle_hash(&self) -> Hash {
723        Mangled(self).data_hash()
724    }
725
726    fn output<T: Output + Default>(&self) -> T {
727        let mut output = T::default();
728        self.to_output(&mut output);
729        output
730    }
731
732    fn vec(&self) -> Vec<u8> {
733        self.output()
734    }
735}
736
737/// Marker trait indicating that [`ToOutput`] result cannot be extended (no value, when represented
738/// as a `Vec<u8>`, may be a prefix of another value).
739pub trait InlineOutput: ToOutput {
740    fn slice_to_output(slice: &[Self], output: &mut impl Output)
741    where
742        Self: Sized,
743    {
744        slice.iter_to_output(output);
745    }
746}
747
748pub trait OptionOutput {
749    fn to_option_output(option: Option<&Self>, output: &mut impl Output);
750}
751
752pub trait ListHashes {
753    fn list_hashes(&self, f: &mut impl FnMut(Hash)) {
754        let _ = f;
755    }
756
757    fn topology_hash(&self) -> Hash {
758        let mut hasher = Sha256::new();
759        self.list_hashes(&mut |hash| hasher.update(hash));
760        Hash::from_sha256(hasher.finalize().into())
761    }
762
763    fn point_count(&self) -> usize {
764        let mut count = 0;
765        self.list_hashes(&mut |_| count += 1);
766        count
767    }
768}
769
770pub trait Topological: ListHashes {
771    fn traverse(&self, visitor: &mut impl PointVisitor) {
772        let _ = visitor;
773    }
774
775    fn topology(&self) -> TopoVec {
776        let mut topology = TopoVec::with_capacity(self.point_count());
777        self.traverse(&mut topology);
778        topology
779    }
780}
781
782pub trait Tagged {
783    const TAGS: Tags = Tags(&[], &[]);
784    const HASH: Hash = Self::TAGS.hash();
785}
786
787pub trait ParseSlice: for<'a> Parse<Input<'a>> {
788    fn parse_slice(slice: &[u8], resolve: &Arc<dyn Resolve>) -> crate::Result<Self> {
789        Self::parse_slice_extra(slice, resolve, &())
790    }
791
792    fn reparse(&self) -> crate::Result<Self>
793    where
794        Self: Traversible,
795    {
796        self.reparse_extra(&())
797    }
798}
799
800impl<T: for<'a> Parse<Input<'a>>> ParseSlice for T {}
801
802pub trait ParseSliceExtra<Extra: Clone>: for<'a> Parse<Input<'a, Extra>> {
803    fn parse_slice_extra(
804        slice: &[u8],
805        resolve: &Arc<dyn Resolve>,
806        extra: &Extra,
807    ) -> crate::Result<Self> {
808        let input = Input {
809            refless: ReflessInput {
810                data: Some(ReflessData {
811                    slice,
812                    prefix: Vec::new(),
813                }),
814            },
815            resolve: Cow::Borrowed(resolve),
816            index: &Cell::new(0),
817            extra: Cow::Borrowed(extra),
818        };
819        let object = Self::parse(input)?;
820        Ok(object)
821    }
822
823    fn reparse_extra(&self, extra: &Extra) -> crate::Result<Self>
824    where
825        Self: Traversible,
826    {
827        Self::parse_slice_extra(&self.vec(), &self.to_resolve(), extra)
828    }
829}
830
831impl<T: for<'a> Parse<Input<'a, Extra>>, Extra: Clone> ParseSliceExtra<Extra> for T {}
832
833pub trait ParseAs<'a> {
834    fn parse_as<T: ParseSlice>(&self) -> crate::Result<T>;
835}
836
837impl<'a> ParseAs<'a> for &'a [u8] {
838    fn parse_as<T: ParseSlice>(&self) -> crate::Result<T> {
839        T::parse_slice(self, &(Arc::new(Vec::new()) as _))
840    }
841}
842
843pub trait ParseAsExtra<'a, Extra: Clone> {
844    fn parse_as_extra<T: ParseSliceExtra<Extra>>(&self, extra: &Extra) -> crate::Result<T>;
845}
846
847impl<'a, Extra: Clone> ParseAsExtra<'a, Extra> for &'a [u8] {
848    fn parse_as_extra<T: ParseSliceExtra<Extra>>(&self, extra: &Extra) -> crate::Result<T> {
849        T::parse_slice_extra(self, &(Arc::new(Vec::new()) as _), extra)
850    }
851}
852
853#[derive(Debug, ToOutput)]
854pub struct DiffHashes {
855    pub tags: Hash,
856    pub topology: Hash,
857    pub mangle: Hash,
858}
859
860#[derive(Debug, ToOutput)]
861pub struct WithHash<'a, T: ?Sized> {
862    pub diff: Hash,
863    pub data: &'a T,
864}
865
866pub trait FullHash: ToOutput + ListHashes + Tagged {
867    fn diff_hashes(&self) -> DiffHashes {
868        DiffHashes {
869            tags: Self::HASH,
870            topology: self.topology_hash(),
871            mangle: self.mangle_hash(),
872        }
873    }
874
875    fn with_hash(&self) -> WithHash<'_, Self> {
876        WithHash {
877            diff: self.diff_hashes().data_hash(),
878            data: self,
879        }
880    }
881
882    fn full_hash(&self) -> Hash {
883        self.with_hash().data_hash()
884    }
885}
886
887impl<T: ?Sized + ToOutput + ListHashes + Tagged> FullHash for T {}
888
889pub trait DefaultHash: FullHash + Default {
890    fn default_hash() -> Hash {
891        Self::default().full_hash()
892    }
893}
894
895impl<T: FullHash + Default> DefaultHash for T {}
896
897pub trait Traversible: 'static + Sized + Send + Sync + FullHash + Topological {
898    fn to_resolve(&self) -> Arc<dyn Resolve> {
899        struct ByTopology {
900            topology: TopoVec,
901            topology_hash: Hash,
902        }
903
904        impl Drop for ByTopology {
905            fn drop(&mut self) {
906                while let Some(singular) = self.topology.pop() {
907                    if let Some(resolve) = singular.try_unwrap_resolve()
908                        && let Some(topology) = &mut resolve.into_topovec()
909                    {
910                        self.topology.append(topology);
911                    }
912                }
913            }
914        }
915
916        impl ByTopology {
917            fn try_resolve(&'_ self, address: Address) -> Result<FailFuture<'_, ByteNode>> {
918                let point = self
919                    .topology
920                    .get(address.index)
921                    .ok_or(Error::AddressOutOfBounds)?;
922                if point.hash() != address.hash {
923                    Err(Error::ResolutionMismatch)
924                } else {
925                    Ok(point.fetch_bytes())
926                }
927            }
928
929            fn try_resolve_data(&'_ self, address: Address) -> Result<FailFuture<'_, Vec<u8>>> {
930                let point = self
931                    .topology
932                    .get(address.index)
933                    .ok_or(Error::AddressOutOfBounds)?;
934                if point.hash() != address.hash {
935                    Err(Error::ResolutionMismatch)
936                } else {
937                    Ok(point.fetch_data())
938                }
939            }
940        }
941
942        impl Resolve for ByTopology {
943            fn resolve(
944                &'_ self,
945                address: Address,
946                _: &Arc<dyn Resolve>,
947            ) -> FailFuture<'_, ByteNode> {
948                self.try_resolve(address)
949                    .map_err(Err)
950                    .map_err(ready)
951                    .map_err(Box::pin)
952                    .unwrap_or_else(|x| x)
953            }
954
955            fn resolve_data(&'_ self, address: Address) -> FailFuture<'_, Vec<u8>> {
956                self.try_resolve_data(address)
957                    .map_err(Err)
958                    .map_err(ready)
959                    .map_err(Box::pin)
960                    .unwrap_or_else(|x| x)
961            }
962
963            fn try_resolve_local(
964                &self,
965                address: Address,
966                _: &Arc<dyn Resolve>,
967            ) -> Result<Option<ByteNode>> {
968                let point = self
969                    .topology
970                    .get(address.index)
971                    .ok_or(Error::AddressOutOfBounds)?;
972                if point.hash() != address.hash {
973                    Err(Error::ResolutionMismatch)
974                } else {
975                    point.fetch_bytes_local()
976                }
977            }
978
979            fn topology_hash(&self) -> Option<Hash> {
980                Some(self.topology_hash)
981            }
982
983            fn into_topovec(self: Arc<Self>) -> Option<TopoVec> {
984                Arc::try_unwrap(self)
985                    .ok()
986                    .as_mut()
987                    .map(|Self { topology, .. }| std::mem::take(topology))
988            }
989        }
990
991        let topology = self.topology();
992        let topology_hash = topology.data_hash();
993        for singular in &topology {
994            if let Some(resolve) = singular.as_resolve()
995                && resolve.topology_hash() == Some(topology_hash)
996            {
997                return resolve.clone();
998            }
999        }
1000        Arc::new(ByTopology {
1001            topology,
1002            topology_hash,
1003        })
1004    }
1005}
1006
1007impl<T: 'static + Send + Sync + FullHash + Topological> Traversible for T {}
1008
1009pub trait Object<Extra = ()>: Traversible + for<'a> Parse<Input<'a, Extra>> {}
1010
1011impl<T: Traversible + for<'a> Parse<Input<'a, Extra>>, Extra> Object<Extra> for T {}
1012
1013pub trait Inline<Extra = ()>:
1014    Object<Extra> + InlineOutput + for<'a> ParseInline<Input<'a, Extra>>
1015{
1016}
1017
1018impl<T: Object<Extra> + InlineOutput + for<'a> ParseInline<Input<'a, Extra>>, Extra> Inline<Extra>
1019    for T
1020{
1021}
1022
1023pub trait Component: InlineOutput + Traversible + Clone {}
1024
1025impl<T: InlineOutput + Traversible + Clone> Component for T {}
1026
1027pub struct Tags(pub &'static [&'static str], pub &'static [&'static Self]);
1028
1029const fn bytes_compare(l: &[u8], r: &[u8]) -> std::cmp::Ordering {
1030    let mut i = 0;
1031    while i < l.len() && i < r.len() {
1032        if l[i] > r[i] {
1033            return std::cmp::Ordering::Greater;
1034        } else if l[i] < r[i] {
1035            return std::cmp::Ordering::Less;
1036        } else {
1037            i += 1;
1038        }
1039    }
1040    if l.len() > r.len() {
1041        std::cmp::Ordering::Greater
1042    } else if l.len() < r.len() {
1043        std::cmp::Ordering::Less
1044    } else {
1045        std::cmp::Ordering::Equal
1046    }
1047}
1048
1049const fn str_compare(l: &str, r: &str) -> std::cmp::Ordering {
1050    bytes_compare(l.as_bytes(), r.as_bytes())
1051}
1052
1053impl Tags {
1054    const fn min_out(&self, strict_min: Option<&str>, min: &mut Option<&'static str>) {
1055        {
1056            let mut i = 0;
1057            while i < self.0.len() {
1058                let candidate = self.0[i];
1059                i += 1;
1060                if let Some(strict_min) = strict_min
1061                    && str_compare(candidate, strict_min).is_le()
1062                {
1063                    continue;
1064                }
1065                if let Some(min) = min
1066                    && str_compare(candidate, min).is_ge()
1067                {
1068                    continue;
1069                }
1070                *min = Some(candidate);
1071            }
1072        }
1073        {
1074            let mut i = 0;
1075            while i < self.1.len() {
1076                self.1[i].min_out(strict_min, min);
1077                i += 1;
1078            }
1079        }
1080        if let Some(l) = min
1081            && let Some(r) = strict_min
1082        {
1083            assert!(str_compare(l, r).is_gt());
1084        }
1085    }
1086
1087    const fn min(&self, strict_min: Option<&str>) -> Option<&'static str> {
1088        let mut min = None;
1089        self.min_out(strict_min, &mut min);
1090        min
1091    }
1092
1093    const fn const_hash(&self, mut hasher: sha2_const::Sha256) -> sha2_const::Sha256 {
1094        let mut last = None;
1095        let mut i = 0;
1096        while let Some(next) = self.min(last) {
1097            i += 1;
1098            if i > 1000 {
1099                panic!("{}", next);
1100            }
1101            hasher = hasher.update(next.as_bytes());
1102            last = Some(next);
1103        }
1104        hasher
1105    }
1106
1107    const fn hash(&self) -> Hash {
1108        Hash::from_sha256(self.const_hash(sha2_const::Sha256::new()).finalize())
1109    }
1110}
1111
1112#[test]
1113fn min_out_respects_bounds() {
1114    let mut min = None;
1115    Tags(&["c", "b", "a"], &[]).min_out(Some("a"), &mut min);
1116    assert_eq!(min, Some("b"));
1117}
1118
1119#[test]
1120fn const_hash() {
1121    assert_ne!(Tags(&["a", "b"], &[]).hash(), Tags(&["a"], &[]).hash());
1122    assert_eq!(
1123        Tags(&["a", "b"], &[]).hash(),
1124        Tags(&["a"], &[&Tags(&["b"], &[])]).hash(),
1125    );
1126    assert_eq!(Tags(&["a", "b"], &[]).hash(), Tags(&["b", "a"], &[]).hash());
1127    assert_eq!(Tags(&["a", "a"], &[]).hash(), Tags(&["a"], &[]).hash());
1128}
1129
1130pub trait Topology: Resolve {
1131    fn len(&self) -> usize;
1132    fn get(&self, index: usize) -> Option<&Arc<dyn Singular>>;
1133
1134    fn is_empty(&self) -> bool {
1135        self.len() == 0
1136    }
1137}
1138
1139pub trait Singular: Send + Sync + FetchBytes {
1140    fn hash(&self) -> Hash;
1141}
1142
1143pub trait SingularFetch: Singular + Fetch {}
1144
1145impl<T: ?Sized + Singular + Fetch> SingularFetch for T {}
1146
1147impl ToOutput for dyn Singular {
1148    fn to_output(&self, output: &mut impl Output) {
1149        self.hash().to_output(output);
1150    }
1151}
1152
1153impl InlineOutput for dyn Singular {}
1154
1155impl ListHashes for Arc<dyn Singular> {
1156    fn list_hashes(&self, f: &mut impl FnMut(Hash)) {
1157        f(self.hash());
1158    }
1159
1160    fn point_count(&self) -> usize {
1161        1
1162    }
1163}
1164
1165pub type TopoVec = Vec<Arc<dyn Singular>>;
1166
1167impl PointVisitor for TopoVec {
1168    fn visit(&mut self, point: &(impl 'static + SingularFetch<T: Traversible> + Clone)) {
1169        self.push(Arc::new(point.clone()));
1170    }
1171}
1172
1173impl Resolve for TopoVec {
1174    fn resolve<'a>(
1175        &'a self,
1176        address: Address,
1177        _: &'a Arc<dyn Resolve>,
1178    ) -> FailFuture<'a, ByteNode> {
1179        Box::pin(async move {
1180            let singular = self.get(address.index).ok_or(Error::AddressOutOfBounds)?;
1181            if singular.hash() != address.hash {
1182                Err(Error::FullHashMismatch)
1183            } else {
1184                singular.fetch_bytes().await
1185            }
1186        })
1187    }
1188
1189    fn resolve_data(&'_ self, address: Address) -> FailFuture<'_, Vec<u8>> {
1190        Box::pin(async move {
1191            let singular = self.get(address.index).ok_or(Error::AddressOutOfBounds)?;
1192            if singular.hash() != address.hash {
1193                Err(Error::FullHashMismatch)
1194            } else {
1195                singular.fetch_data().await
1196            }
1197        })
1198    }
1199
1200    fn try_resolve_local(
1201        &self,
1202        address: Address,
1203        _: &Arc<dyn Resolve>,
1204    ) -> Result<Option<ByteNode>> {
1205        let singular = self.get(address.index).ok_or(Error::AddressOutOfBounds)?;
1206        if singular.hash() != address.hash {
1207            Err(Error::FullHashMismatch)
1208        } else {
1209            singular.fetch_bytes_local()
1210        }
1211    }
1212
1213    fn topology_hash(&self) -> Option<Hash> {
1214        Some(self.data_hash())
1215    }
1216
1217    fn into_topovec(self: Arc<Self>) -> Option<TopoVec> {
1218        Some((*self).clone())
1219    }
1220}
1221
1222impl Topology for TopoVec {
1223    fn len(&self) -> usize {
1224        self.len()
1225    }
1226
1227    fn get(&self, index: usize) -> Option<&Arc<dyn Singular>> {
1228        (**self).get(index)
1229    }
1230}
1231
1232pub trait ParseSliceRefless: for<'a> Parse<ReflessInput<'a>> {
1233    fn parse_slice_refless(slice: &[u8]) -> crate::Result<Self> {
1234        let input = ReflessInput {
1235            data: Some(ReflessData {
1236                slice,
1237                prefix: Vec::new(),
1238            }),
1239        };
1240        let object = Self::parse(input)?;
1241        Ok(object)
1242    }
1243}
1244
1245impl<T: for<'a> Parse<ReflessInput<'a>>> ParseSliceRefless for T {}
1246
1247pub trait ReflessObject:
1248    'static + Sized + Send + Sync + ToOutput + Tagged + for<'a> Parse<ReflessInput<'a>>
1249{
1250}
1251
1252impl<T: 'static + Sized + Send + Sync + ToOutput + Tagged + for<'a> Parse<ReflessInput<'a>>>
1253    ReflessObject for T
1254{
1255}
1256
1257pub trait ReflessInline:
1258    ReflessObject + InlineOutput + for<'a> ParseInline<ReflessInput<'a>>
1259{
1260}
1261
1262impl<T: ReflessObject + InlineOutput + for<'a> ParseInline<ReflessInput<'a>>> ReflessInline for T {}
1263
1264pub trait Output {
1265    fn write(&mut self, data: &[u8]);
1266    fn is_mangling(&self) -> bool {
1267        false
1268    }
1269    fn is_real(&self) -> bool {
1270        !self.is_mangling()
1271    }
1272    fn as_write(&mut self) -> AsWrite<'_, Self> {
1273        AsWrite { output: self }
1274    }
1275}
1276
1277pub struct AsWrite<'a, O: ?Sized> {
1278    output: &'a mut O,
1279}
1280
1281impl<O: ?Sized + Output> std::io::Write for AsWrite<'_, O> {
1282    fn write(&mut self, data: &[u8]) -> std::io::Result<usize> {
1283        self.output.write(data);
1284        Ok(data.len())
1285    }
1286
1287    fn flush(&mut self) -> std::io::Result<()> {
1288        Ok(())
1289    }
1290}
1291
1292impl Output for Vec<u8> {
1293    fn write(&mut self, data: &[u8]) {
1294        self.extend_from_slice(data);
1295    }
1296}
1297
1298struct MangleOutput<'a, T: ?Sized>(&'a mut T);
1299
1300impl<'a, T: Output> MangleOutput<'a, T> {
1301    fn new(output: &'a mut T) -> Self {
1302        assert!(output.is_real());
1303        assert!(!output.is_mangling());
1304        Self(output)
1305    }
1306}
1307
1308impl<T: ?Sized + Output> Output for MangleOutput<'_, T> {
1309    fn write(&mut self, data: &[u8]) {
1310        self.0.write(data);
1311    }
1312
1313    fn is_mangling(&self) -> bool {
1314        true
1315    }
1316}
1317
1318pub struct Mangled<T: ?Sized>(T);
1319
1320impl<T: ?Sized + ToOutput> ToOutput for Mangled<T> {
1321    fn to_output(&self, output: &mut impl Output) {
1322        self.0.to_output(&mut MangleOutput::new(output));
1323    }
1324}
1325
1326pub trait Size {
1327    const SIZE: usize = <Self::Size as Unsigned>::USIZE;
1328    type Size: Unsigned;
1329}
1330
1331pub trait SizeExt: Size<Size: ArrayLength> + ToOutput {
1332    fn to_array(&self) -> GenericArray<u8, Self::Size> {
1333        struct ArrayOutput<'a> {
1334            data: &'a mut [u8],
1335            offset: usize,
1336        }
1337
1338        impl ArrayOutput<'_> {
1339            fn finalize(self) {
1340                assert_eq!(self.offset, self.data.len());
1341            }
1342        }
1343
1344        impl Output for ArrayOutput<'_> {
1345            fn write(&mut self, data: &[u8]) {
1346                self.data[self.offset..][..data.len()].copy_from_slice(data);
1347                self.offset += data.len();
1348            }
1349        }
1350
1351        let mut array = GenericArray::default();
1352        let mut output = ArrayOutput {
1353            data: &mut array,
1354            offset: 0,
1355        };
1356        self.to_output(&mut output);
1357        output.finalize();
1358        array
1359    }
1360
1361    fn reinterpret<T: FromSized<Size = Self::Size>>(&self) -> T {
1362        T::from_sized(&self.to_array())
1363    }
1364}
1365
1366impl<T: Size<Size: ArrayLength> + ToOutput> SizeExt for T {}
1367
1368pub trait FromSized: Size<Size: ArrayLength> {
1369    fn from_sized(data: &GenericArray<u8, Self::Size>) -> Self;
1370}
1371
1372impl<
1373    A: FromSized<Size = An>,
1374    B: FromSized<Size = Bn>,
1375    An,
1376    Bn: Add<An, Output: ArrayLength + Sub<An, Output = Bn>>,
1377> FromSized for (A, B)
1378{
1379    fn from_sized(data: &GenericArray<u8, Self::Size>) -> Self {
1380        let (a, b) = data.split();
1381        (A::from_sized(a), B::from_sized(b))
1382    }
1383}
1384
1385macro_rules! from_sized_tuple {
1386    (($($t:ident),*), ($($x:ident),*) $(,)?) => {
1387        impl<A, $($t),*, N> FromSized for (A, $($t),*)
1388        where
1389            (A, ($($t),*)): FromSized<Size = N>,
1390            Self: Size<Size = N>,
1391        {
1392            fn from_sized(data: &GenericArray<u8, Self::Size>) -> Self {
1393                let (a, ($($x),*)) = FromSized::from_sized(data);
1394                (a, $($x),*)
1395            }
1396        }
1397    };
1398}
1399
1400from_sized_tuple!((B, C), (b, c));
1401from_sized_tuple!((B, C, D), (b, c, d));
1402from_sized_tuple!((B, C, D, E), (b, c, d, e));
1403from_sized_tuple!((B, C, D, E, F), (b, c, d, e, f));
1404from_sized_tuple!((B, C, D, E, F, G), (b, c, d, e, f, g));
1405from_sized_tuple!((B, C, D, E, F, G, H), (b, c, d, e, f, g, h));
1406from_sized_tuple!((B, C, D, E, F, G, H, I), (b, c, d, e, f, g, h, i));
1407from_sized_tuple!((B, C, D, E, F, G, H, I, J), (b, c, d, e, f, g, h, i, j));
1408from_sized_tuple!(
1409    (B, C, D, E, F, G, H, I, J, K),
1410    (b, c, d, e, f, g, h, i, j, k),
1411);
1412from_sized_tuple!(
1413    (B, C, D, E, F, G, H, I, J, K, L),
1414    (b, c, d, e, f, g, h, i, j, k, l),
1415);
1416
1417pub trait RainbowIterator: Sized + IntoIterator {
1418    fn iter_to_output(self, output: &mut impl Output)
1419    where
1420        Self::Item: InlineOutput,
1421    {
1422        self.into_iter().for_each(|item| item.to_output(output));
1423    }
1424
1425    fn iter_list_hashes(self, f: &mut impl FnMut(Hash))
1426    where
1427        Self::Item: ListHashes,
1428    {
1429        self.into_iter().for_each(|item| item.list_hashes(f));
1430    }
1431
1432    fn iter_traverse(self, visitor: &mut impl PointVisitor)
1433    where
1434        Self::Item: Topological,
1435    {
1436        self.into_iter().for_each(|item| item.traverse(visitor));
1437    }
1438
1439    fn iter_bytes_cmp(self, other: impl IntoIterator<Item = Self::Item>) -> Ordering
1440    where
1441        Self::Item: ByteOrd,
1442    {
1443        self.into_iter()
1444            .map(OrderedByBytes)
1445            .cmp(other.into_iter().map(OrderedByBytes))
1446    }
1447}
1448
1449pub trait ParseInput: Sized {
1450    type Data: AsRef<[u8]> + Deref<Target = [u8]> + Into<Vec<u8>>;
1451    fn push_front(&mut self, data: impl Into<Vec<u8>>) -> crate::Result<()>;
1452    fn read(&mut self, data: &mut [u8]) -> crate::Result<()>;
1453    fn parse_chunk<const N: usize>(&mut self) -> crate::Result<[u8; N]> {
1454        let mut chunk = [0; _];
1455        self.read(&mut chunk)?;
1456        Ok(chunk)
1457    }
1458    fn split_n(&mut self, n: usize) -> crate::Result<Self>;
1459    fn skip_n(&mut self, n: usize) -> crate::Result<()>;
1460    fn find_zero(&mut self) -> crate::Result<usize>;
1461    fn parse_n_ahead(&mut self, n: usize) -> crate::Result<Vec<u8>>;
1462    fn compare_ahead(&mut self, c: &[u8]) -> crate::Result<bool>;
1463    fn split_parse<T: Parse<Self>>(&mut self, n: usize) -> crate::Result<T> {
1464        self.split_n(n)?.parse()
1465    }
1466    fn parse_zero_terminated<T: Parse<Self>>(&mut self) -> crate::Result<(Vec<u8>, T)> {
1467        let n = self.find_zero()?;
1468        let data = self.parse_n_ahead(n)?;
1469        let value = self.split_parse(n)?;
1470        self.skip_n(1)?;
1471        Ok((data, value))
1472    }
1473    fn compare_skip(&mut self, c: &[u8]) -> Result<bool> {
1474        let matches = self.compare_ahead(c)?;
1475        if matches {
1476            self.skip_n(c.len())?
1477        }
1478        Ok(matches)
1479    }
1480    fn parse_compare<T: Parse<Self>>(mut self, c: &[u8]) -> Result<Option<T>> {
1481        if self.compare_skip(c)? {
1482            self.empty()?;
1483            Ok(None)
1484        } else {
1485            Ok(Some(self.parse()?))
1486        }
1487    }
1488    fn parse_compare_inline<T: ParseInline<Self>>(&mut self, c: &[u8]) -> Result<Option<T>> {
1489        if self.compare_skip(c)? {
1490            Ok(None)
1491        } else {
1492            Ok(Some(self.parse_inline()?))
1493        }
1494    }
1495    fn parse_all(self) -> crate::Result<Self::Data>;
1496    fn empty(self) -> crate::Result<()>;
1497    fn non_empty(self) -> crate::Result<Option<Self>>;
1498    fn remaining(self) -> crate::Result<(Self, usize)>;
1499
1500    fn consume(self, f: impl FnMut(&mut Self) -> crate::Result<()>) -> crate::Result<()> {
1501        self.collect(f)
1502    }
1503
1504    fn parse_collect<T: ParseInline<Self>, B: FromIterator<T>>(self) -> crate::Result<B> {
1505        self.collect(|input| input.parse_inline())
1506    }
1507
1508    fn collect<T, B: FromIterator<T>>(
1509        self,
1510        f: impl FnMut(&mut Self) -> crate::Result<T>,
1511    ) -> crate::Result<B> {
1512        self.iter(f).collect()
1513    }
1514
1515    fn iter<T>(
1516        self,
1517        mut f: impl FnMut(&mut Self) -> crate::Result<T>,
1518    ) -> impl Iterator<Item = crate::Result<T>> {
1519        let mut state = Some(self);
1520        std::iter::from_fn(move || {
1521            let mut input = match state.take()?.non_empty() {
1522                Ok(input) => input?,
1523                Err(e) => return Some(Err(e)),
1524            };
1525            let item = f(&mut input);
1526            state = Some(input);
1527            Some(item)
1528        })
1529    }
1530
1531    fn parse_inline<T: ParseInline<Self>>(&mut self) -> crate::Result<T> {
1532        T::parse_inline(self)
1533    }
1534
1535    fn parse<T: Parse<Self>>(self) -> crate::Result<T> {
1536        T::parse(self)
1537    }
1538
1539    fn parse_vec<T: ParseInline<Self>>(self) -> crate::Result<Vec<T>> {
1540        T::parse_vec(self)
1541    }
1542
1543    fn parse_vec_n<T: ParseInline<Self>>(&mut self, n: usize) -> crate::Result<Vec<T>> {
1544        T::parse_vec_n(self, n)
1545    }
1546
1547    fn parse_array<T: ParseInline<Self>, const N: usize>(&mut self) -> crate::Result<[T; N]> {
1548        T::parse_array(self)
1549    }
1550
1551    fn parse_generic_array<T: ParseInline<Self>, N: ArrayLength>(
1552        &mut self,
1553    ) -> crate::Result<GenericArray<T, N>> {
1554        T::parse_generic_array(self)
1555    }
1556
1557    fn as_read<T, E>(
1558        &mut self,
1559        f: impl FnOnce(AsRead<'_, Self>) -> std::result::Result<T, E>,
1560    ) -> crate::Result<T>
1561    where
1562        Error: From<E>,
1563    {
1564        let result = f(AsRead { input: self })?;
1565        self.noop()?;
1566        Ok(result)
1567    }
1568
1569    fn noop(&mut self) -> crate::Result<()> {
1570        self.read(&mut [])
1571    }
1572
1573    fn parse_refless_inline<T: for<'r> ParseInline<ReflessInput<'r>>>(
1574        &mut self,
1575    ) -> crate::Result<T>;
1576
1577    fn parse_refless<T: for<'r> Parse<ReflessInput<'r>>>(self) -> crate::Result<T>;
1578}
1579
1580pub struct AsRead<'a, I> {
1581    input: &'a mut I,
1582}
1583
1584impl<I: ParseInput> std::io::Read for AsRead<'_, I> {
1585    fn read(&mut self, data: &mut [u8]) -> std::io::Result<usize> {
1586        self.read_exact(data)?;
1587        Ok(data.len())
1588    }
1589
1590    fn read_exact(&mut self, data: &mut [u8]) -> std::io::Result<()> {
1591        self.input.read(data)?;
1592        Ok(())
1593    }
1594
1595    fn read_to_end(&mut self, _: &mut Vec<u8>) -> std::io::Result<usize> {
1596        Err(std::io::ErrorKind::Unsupported.into())
1597    }
1598}
1599
1600pub trait PointInput: ParseInput {
1601    type Extra: 'static + Clone;
1602    type WithExtra<E: 'static + Clone>: PointInput<Extra = E, WithExtra<Self::Extra> = Self>;
1603    fn next_index(&mut self) -> usize;
1604    fn resolve_arc_ref(&self) -> &Arc<dyn Resolve>;
1605    fn resolve(&self) -> Arc<dyn Resolve> {
1606        self.resolve_arc_ref().clone()
1607    }
1608    fn resolve_ref(&self) -> &dyn Resolve {
1609        self.resolve_arc_ref().as_ref()
1610    }
1611    fn with_resolve(self, resolve: Arc<dyn Resolve>) -> Self;
1612    /// Get [`Self::Extra`].
1613    fn extra(&self) -> &Self::Extra;
1614    /// Project the `Extra`. Under some circumstances, prevents an extra [`Clone::clone`].
1615    fn map_extra<E: 'static + Clone>(
1616        self,
1617        f: impl FnOnce(&Self::Extra) -> &E,
1618    ) -> Self::WithExtra<E>;
1619    /// Return the old [`Self::Extra`], give a new [`PointInput`] with `E` as `Extra`.
1620    fn replace_extra<E: 'static + Clone>(self, extra: E) -> (Self::Extra, Self::WithExtra<E>);
1621    /// [`Self::replace_extra`] but discarding [`Self::Extra`].
1622    fn with_extra<E: 'static + Clone>(self, extra: E) -> Self::WithExtra<E> {
1623        self.replace_extra(extra).1
1624    }
1625    /// [`ParseInput::parse`] with a different `Extra`.
1626    fn parse_extra<E: 'static + Clone, T: Parse<Self::WithExtra<E>>>(
1627        self,
1628        extra: E,
1629    ) -> crate::Result<T> {
1630        self.with_extra(extra).parse()
1631    }
1632    /// [`ParseInput::parse_inline`] with a different `Extra`.
1633    fn parse_inline_extra<E: 'static + Clone, T: ParseInline<Self::WithExtra<E>>>(
1634        &mut self,
1635        extra: E,
1636    ) -> crate::Result<T>;
1637}
1638
1639impl<T: Sized + IntoIterator> RainbowIterator for T {}
1640
1641/// This can be parsed by consuming the whole rest of the input.
1642///
1643/// Nothing can be parsed after this. It's implementation's responsibility to ensure there are no
1644/// leftover bytes.
1645pub trait Parse<I: ParseInput>: Sized {
1646    /// Parse consuming the whole stream.
1647    fn parse(input: I) -> crate::Result<Self>;
1648}
1649
1650/// This can be parsed from an input, after which we can correctly parse something else.
1651///
1652/// When parsed as the last object, makes sure there are no bytes left in the input (fails if there
1653/// are).
1654pub trait ParseInline<I: ParseInput>: Parse<I> {
1655    /// Parse without consuming the whole stream. Errors on unexpected EOF.
1656    fn parse_inline(input: &mut I) -> crate::Result<Self>;
1657    /// For implementing [`Parse::parse`].
1658    fn parse_as_inline(mut input: I) -> crate::Result<Self> {
1659        let object = Self::parse_inline(&mut input)?;
1660        input.empty()?;
1661        Ok(object)
1662    }
1663    /// Parse a `Vec` of `Self`. Customisable for optimisations.
1664    fn parse_vec(input: I) -> crate::Result<Vec<Self>> {
1665        input.parse_collect()
1666    }
1667    /// Parse a `Vec` of `Self` of length `n`. Customisable for optimisations.
1668    fn parse_vec_n(input: &mut I, n: usize) -> crate::Result<Vec<Self>> {
1669        (0..n).map(|_| input.parse_inline()).collect()
1670    }
1671    /// Parse an array of `Self`. Customisable for optimisations.
1672    fn parse_array<const N: usize>(input: &mut I) -> crate::Result<[Self; N]> {
1673        let mut scratch = std::array::from_fn(|_| None);
1674        for item in scratch.iter_mut() {
1675            *item = Some(input.parse_inline()?);
1676        }
1677        Ok(scratch.map(Option::unwrap))
1678    }
1679    /// Parse a [`GenericArray`] of `Self`. Customisable for optimisations.
1680    fn parse_generic_array<N: ArrayLength>(input: &mut I) -> crate::Result<GenericArray<Self, N>> {
1681        let mut scratch = GenericArray::default();
1682        for item in scratch.iter_mut() {
1683            *item = Some(input.parse_inline()?);
1684        }
1685        Ok(scratch.map(Option::unwrap))
1686    }
1687}
1688
1689/// Implemented if both types have the exact same layout.
1690/// This implies having the same [`MaybeHasNiche::MnArray`].
1691///
1692/// This is represented as two-way conversion for two reasons:
1693/// - to highlight that the conversion is actual equivalence
1694/// - to increase flexibility (mostly to go around the orphan rule)
1695pub trait Equivalent<T>: Sized {
1696    /// Inverse of [`Equivalent::from_equivalent`].
1697    fn into_equivalent(self) -> T;
1698    /// Inverse of [`Equivalent::into_equivalent`].
1699    fn from_equivalent(object: T) -> Self;
1700}
1701
1702pub trait EquivalentFor<U>: Sized {
1703    fn equivalent_for(self) -> U;
1704}
1705
1706impl<T, U: Equivalent<T>> EquivalentFor<U> for T {
1707    fn equivalent_for(self) -> U {
1708        U::from_equivalent(self)
1709    }
1710}
1711
1712pub fn from_equivalent<U>(object: impl EquivalentFor<U>) -> U {
1713    object.equivalent_for()
1714}
1715
1716/// This `Extra` can be used to parse `T` via [`ParseSliceExtra::parse_slice_extra`].
1717pub trait ExtraFor<T> {
1718    /// [`ParseSliceExtra::parse_slice_extra`].
1719    fn parse(&self, data: &[u8], resolve: &Arc<dyn Resolve>) -> Result<T>;
1720
1721    /// [`Self::parse`], then check that [`FullHash::full_hash`] matches.
1722    fn parse_checked(&self, hash: Hash, data: &[u8], resolve: &Arc<dyn Resolve>) -> Result<T>
1723    where
1724        T: FullHash,
1725    {
1726        let object = self.parse(data, resolve)?;
1727        if object.full_hash() != hash {
1728            Err(Error::FullHashMismatch)
1729        } else {
1730            Ok(object)
1731        }
1732    }
1733}
1734
1735impl<T: for<'a> Parse<Input<'a, Extra>>, Extra: Clone> ExtraFor<T> for Extra {
1736    fn parse(&self, data: &[u8], resolve: &Arc<dyn Resolve>) -> Result<T> {
1737        T::parse_slice_extra(data, resolve, self)
1738    }
1739}
1740
1741impl<T> ToOutput for dyn Send + Sync + ExtraFor<T> {
1742    fn to_output(&self, _: &mut impl Output) {}
1743}
1744
1745impl<T: Tagged> Tagged for dyn Send + Sync + ExtraFor<T> {
1746    const TAGS: Tags = T::TAGS;
1747    const HASH: Hash = T::HASH;
1748}
1749
1750impl<T> Size for dyn Send + Sync + ExtraFor<T> {
1751    type Size = typenum::U0;
1752    const SIZE: usize = 0;
1753}
1754
1755impl<T> InlineOutput for dyn Send + Sync + ExtraFor<T> {}
1756impl<T> ListHashes for dyn Send + Sync + ExtraFor<T> {}
1757impl<T> Topological for dyn Send + Sync + ExtraFor<T> {}
1758
1759impl<T, I: PointInput<Extra: Send + Sync + ExtraFor<T>>> Parse<I>
1760    for Arc<dyn Send + Sync + ExtraFor<T>>
1761{
1762    fn parse(input: I) -> crate::Result<Self> {
1763        Self::parse_as_inline(input)
1764    }
1765}
1766
1767impl<T, I: PointInput<Extra: Send + Sync + ExtraFor<T>>> ParseInline<I>
1768    for Arc<dyn Send + Sync + ExtraFor<T>>
1769{
1770    fn parse_inline(input: &mut I) -> crate::Result<Self> {
1771        Ok(Arc::new(input.extra().clone()))
1772    }
1773}
1774
1775impl<T> MaybeHasNiche for dyn Send + Sync + ExtraFor<T> {
1776    type MnArray = NoNiche<ZeroNoNiche<<Self as Size>::Size>>;
1777}
1778
1779assert_impl!(
1780    impl<T, E> Inline<E> for Arc<dyn Send + Sync + ExtraFor<T>>
1781    where
1782        T: Object<E>,
1783        E: 'static + Send + Sync + Clone + ExtraFor<T>,
1784    {
1785    }
1786);
1787
1788#[doc(hidden)]
1789pub trait BoundPair: Sized {
1790    type T;
1791    type E;
1792}
1793
1794impl<T, E> BoundPair for (T, E) {
1795    type T = T;
1796    type E = E;
1797}
1798
1799#[test]
1800fn options() {
1801    type T0 = ();
1802    type T1 = Option<T0>;
1803    type T2 = Option<T1>;
1804    type T3 = Option<T2>;
1805    type T4 = Option<T3>;
1806    type T5 = Option<T4>;
1807    assert_eq!(T0::SIZE, 0);
1808    assert_eq!(T1::SIZE, 1);
1809    assert_eq!(T2::SIZE, 1);
1810    assert_eq!(T3::SIZE, 1);
1811    assert_eq!(T4::SIZE, 1);
1812    assert_eq!(T5::SIZE, 1);
1813    assert_eq!(Some(Some(Some(()))).vec(), [0]);
1814    assert_eq!(Some(Some(None::<()>)).vec(), [1]);
1815    assert_eq!(Some(None::<Option<()>>).vec(), [2]);
1816    assert_eq!(None::<Option<Option<()>>>.vec(), [3]);
1817
1818    assert_eq!(false.vec(), [0]);
1819    assert_eq!(true.vec(), [1]);
1820    assert_eq!(Some(false).vec(), [0]);
1821    assert_eq!(Some(true).vec(), [1]);
1822    assert_eq!(None::<bool>.vec(), [2]);
1823    assert_eq!(Some(Some(false)).vec(), [0]);
1824    assert_eq!(Some(Some(true)).vec(), [1]);
1825    assert_eq!(Some(None::<bool>).vec(), [2]);
1826    assert_eq!(None::<Option<bool>>.vec(), [3]);
1827    assert_eq!(Some(Some(Some(false))).vec(), [0]);
1828    assert_eq!(Some(Some(Some(true))).vec(), [1]);
1829    assert_eq!(Some(Some(None::<bool>)).vec(), [2]);
1830    assert_eq!(Some(None::<Option<bool>>).vec(), [3]);
1831    assert_eq!(None::<Option<Option<bool>>>.vec(), [4]);
1832    assert_eq!(Option::<Hash>::SIZE, HASH_SIZE);
1833    assert_eq!(Some(()).vec(), [0]);
1834    assert_eq!(Some(((), ())).vec(), [0]);
1835    assert_eq!(Some(((), true)).vec(), [1]);
1836    assert_eq!(Some((true, true)).vec(), [1, 1]);
1837    assert_eq!(Some((Some(true), true)).vec(), [1, 1]);
1838    assert_eq!(Some((None::<bool>, true)).vec(), [2, 1]);
1839    assert_eq!(Some((true, None::<bool>)).vec(), [1, 2]);
1840    assert_eq!(None::<(Option<bool>, bool)>.vec(), [3, 2]);
1841    assert_eq!(None::<(bool, Option<bool>)>.vec(), [2, 3]);
1842    assert_eq!(Some(Some((Some(true), Some(true)))).vec(), [1, 1],);
1843    assert_eq!(Option::<Hash>::SIZE, HASH_SIZE);
1844    assert_eq!(Option::<Option<Hash>>::SIZE, HASH_SIZE);
1845    assert_eq!(Option::<Option<Option<Hash>>>::SIZE, HASH_SIZE);
1846}
1847
1848pub trait TryDefault: Sized {
1849    fn try_default() -> crate::Result<Self>;
1850}
1851
1852impl<T: Default> TryDefault for T {
1853    fn try_default() -> crate::Result<Self> {
1854        Ok(Self::default())
1855    }
1856}
object_rainbow/lib.rs

object_rainbow/
lib.rs
