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

object_rainbow/
lib.rs
