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                n = 0;
320                prefix_l.push(Vec::from(&front[..n]));
321                front.drain(..n);
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
703/// Values of this type can be uniquely represented as a `Vec<u8>`.
704pub trait ToOutput {
705    fn to_output(&self, output: &mut impl Output);
706
707    #[must_use]
708    fn data_hash(&self) -> Hash {
709        #[derive(Default)]
710        struct HashOutput {
711            hasher: Sha256,
712            at: usize,
713        }
714
715        impl Output for HashOutput {
716            fn write(&mut self, data: &[u8]) {
717                self.hasher.update(data);
718                self.at += data.len();
719            }
720        }
721
722        impl HashOutput {
723            fn hash(self) -> Hash {
724                Hash::from_hasher(self.hasher)
725            }
726        }
727
728        let mut output = HashOutput::default();
729        self.to_output(&mut output);
730        output.hash()
731    }
732
733    fn mangle_hash(&self) -> Hash {
734        Mangled(self).data_hash()
735    }
736
737    fn output<T: Output + Default>(&self) -> T {
738        let mut output = T::default();
739        self.to_output(&mut output);
740        output
741    }
742
743    fn vec(&self) -> Vec<u8> {
744        self.output()
745    }
746}
747
748/// Marker trait indicating that [`ToOutput`] result cannot be extended (no value, when represented
749/// as a `Vec<u8>`, may be a prefix of another value). Effectively means prefix property.
750pub trait InlineOutput: ToOutput {
751    fn slice_to_output(slice: &[Self], output: &mut impl Output)
752    where
753        Self: Sized,
754    {
755        slice.iter_to_output(output);
756    }
757}
758
759pub trait OptionOutput {
760    fn to_option_output(option: Option<&Self>, output: &mut impl Output);
761}
762
763pub trait OptionParse<I: ParseInput>: Parse<I> {
764    fn parse_option(input: I) -> crate::Result<Option<Self>>;
765}
766
767pub trait OptionParseInline<I: ParseInput>: OptionParse<I> + ParseInline<I> {
768    fn parse_option_inline(input: &mut I) -> crate::Result<Option<Self>>;
769}
770
771pub trait ListHashes {
772    fn list_hashes(&self, f: &mut impl FnMut(Hash)) {
773        let _ = f;
774    }
775
776    fn topology_hash(&self) -> Hash {
777        let mut hasher = Sha256::new();
778        self.list_hashes(&mut |hash| hasher.update(hash));
779        Hash::from_hasher(hasher)
780    }
781
782    fn point_count(&self) -> usize {
783        let mut count = 0;
784        self.list_hashes(&mut |_| count += 1);
785        count
786    }
787}
788
789pub trait Topological: ListHashes {
790    fn traverse(&self, visitor: &mut impl PointVisitor) {
791        let _ = visitor;
792    }
793
794    fn topology(&self) -> TopoVec {
795        let mut topology = TopoVec::with_capacity(self.point_count());
796        self.traverse(&mut topology);
797        topology
798    }
799}
800
801pub trait Tagged {
802    const TAGS: Tags = Tags(&[], &[]);
803    const HASH: Hash = Self::TAGS.hash();
804}
805
806pub trait ParseSlice: for<'a> Parse<Input<'a>> {
807    fn parse_slice(slice: &[u8], resolve: &Arc<dyn Resolve>) -> crate::Result<Self> {
808        Self::parse_slice_extra(slice, resolve, &())
809    }
810
811    fn reparse(&self) -> crate::Result<Self>
812    where
813        Self: Traversible,
814    {
815        self.reparse_extra(&())
816    }
817}
818
819impl<T: for<'a> Parse<Input<'a>>> ParseSlice for T {}
820
821pub trait ParseSliceExtra<Extra: Clone>: for<'a> Parse<Input<'a, Extra>> {
822    fn parse_slice_extra(
823        slice: &[u8],
824        resolve: &Arc<dyn Resolve>,
825        extra: &Extra,
826    ) -> crate::Result<Self> {
827        let input = Input {
828            refless: ReflessInput {
829                data: Some(ReflessData {
830                    slice,
831                    prefix: Vec::new(),
832                }),
833            },
834            resolve: Cow::Borrowed(resolve),
835            index: &Cell::new(0),
836            extra: Cow::Borrowed(extra),
837        };
838        let object = Self::parse(input)?;
839        Ok(object)
840    }
841
842    fn reparse_extra(&self, extra: &Extra) -> crate::Result<Self>
843    where
844        Self: Traversible,
845    {
846        Self::parse_slice_extra(&self.vec(), &self.to_resolve(), extra)
847    }
848}
849
850impl<T: for<'a> Parse<Input<'a, Extra>>, Extra: Clone> ParseSliceExtra<Extra> for T {}
851
852pub trait ParseAs<'a> {
853    fn parse_as<T: ParseSlice>(&self) -> crate::Result<T>;
854}
855
856impl<'a> ParseAs<'a> for &'a [u8] {
857    fn parse_as<T: ParseSlice>(&self) -> crate::Result<T> {
858        T::parse_slice(self, &(Arc::new(Vec::new()) as _))
859    }
860}
861
862pub trait ParseAsExtra<'a, Extra: Clone> {
863    fn parse_as_extra<T: ParseSliceExtra<Extra>>(&self, extra: &Extra) -> crate::Result<T>;
864}
865
866impl<'a, Extra: Clone> ParseAsExtra<'a, Extra> for &'a [u8] {
867    fn parse_as_extra<T: ParseSliceExtra<Extra>>(&self, extra: &Extra) -> crate::Result<T> {
868        T::parse_slice_extra(self, &(Arc::new(Vec::new()) as _), extra)
869    }
870}
871
872#[derive(Debug, ToOutput, Default)]
873pub struct DiffHashes {
874    pub tags: Hash,
875    pub topology: Hash,
876    pub mangle: Hash,
877}
878
879#[derive(Debug, ToOutput)]
880pub struct WithHash<'a, T: ?Sized> {
881    pub diff: Hash,
882    pub data: &'a T,
883}
884
885pub trait FullHash: ToOutput + ListHashes + Tagged {
886    fn diff_hashes(&self) -> DiffHashes {
887        DiffHashes {
888            tags: Self::HASH,
889            topology: self.topology_hash(),
890            mangle: self.mangle_hash(),
891        }
892    }
893
894    fn with_hash(&self) -> WithHash<'_, Self> {
895        WithHash {
896            diff: self.diff_hashes().data_hash(),
897            data: self,
898        }
899    }
900
901    fn full_hash(&self) -> Hash {
902        self.with_hash().data_hash()
903    }
904}
905
906impl<T: ?Sized + ToOutput + ListHashes + Tagged> FullHash for T {}
907
908pub trait DefaultHash: FullHash + Default {
909    fn default_hash() -> Hash {
910        Self::default().full_hash()
911    }
912}
913
914impl<T: FullHash + Default> DefaultHash for T {}
915
916pub trait Traversible: 'static + Sized + Send + Sync + FullHash + Topological {
917    fn to_resolve(&self) -> Arc<dyn Resolve> {
918        struct ByTopology {
919            topology: TopoVec,
920            topology_hash: Hash,
921        }
922
923        impl Drop for ByTopology {
924            fn drop(&mut self) {
925                while let Some(singular) = self.topology.pop() {
926                    if let Some(resolve) = singular.try_unwrap_resolve()
927                        && let Some(topology) = &mut resolve.into_topovec()
928                    {
929                        self.topology.append(topology);
930                    }
931                }
932            }
933        }
934
935        impl ByTopology {
936            fn try_resolve(&'_ self, address: Address) -> Result<FailFuture<'_, ByteNode>> {
937                let point = self
938                    .topology
939                    .get(address.index)
940                    .ok_or(Error::AddressOutOfBounds)?;
941                if point.hash() != address.hash {
942                    Err(Error::ResolutionMismatch)
943                } else {
944                    Ok(point.fetch_bytes())
945                }
946            }
947
948            fn try_resolve_data(&'_ self, address: Address) -> Result<FailFuture<'_, Vec<u8>>> {
949                let point = self
950                    .topology
951                    .get(address.index)
952                    .ok_or(Error::AddressOutOfBounds)?;
953                if point.hash() != address.hash {
954                    Err(Error::ResolutionMismatch)
955                } else {
956                    Ok(point.fetch_data())
957                }
958            }
959        }
960
961        impl Resolve for ByTopology {
962            fn resolve(
963                &'_ self,
964                address: Address,
965                _: &Arc<dyn Resolve>,
966            ) -> FailFuture<'_, ByteNode> {
967                self.try_resolve(address)
968                    .map_err(Err)
969                    .map_err(ready)
970                    .map_err(Box::pin)
971                    .unwrap_or_else(|x| x)
972            }
973
974            fn resolve_data(&'_ self, address: Address) -> FailFuture<'_, Vec<u8>> {
975                self.try_resolve_data(address)
976                    .map_err(Err)
977                    .map_err(ready)
978                    .map_err(Box::pin)
979                    .unwrap_or_else(|x| x)
980            }
981
982            fn try_resolve_local(
983                &self,
984                address: Address,
985                _: &Arc<dyn Resolve>,
986            ) -> Result<Option<ByteNode>> {
987                let point = self
988                    .topology
989                    .get(address.index)
990                    .ok_or(Error::AddressOutOfBounds)?;
991                if point.hash() != address.hash {
992                    Err(Error::ResolutionMismatch)
993                } else {
994                    point.fetch_bytes_local()
995                }
996            }
997
998            fn topology_hash(&self) -> Option<Hash> {
999                Some(self.topology_hash)
1000            }
1001
1002            fn into_topovec(self: Arc<Self>) -> Option<TopoVec> {
1003                Arc::try_unwrap(self)
1004                    .ok()
1005                    .as_mut()
1006                    .map(|Self { topology, .. }| std::mem::take(topology))
1007            }
1008        }
1009
1010        let topology = self.topology();
1011        let topology_hash = topology.data_hash();
1012        for singular in &topology {
1013            if let Some(resolve) = singular.as_resolve()
1014                && resolve.topology_hash() == Some(topology_hash)
1015            {
1016                return resolve.clone();
1017            }
1018        }
1019        Arc::new(ByTopology {
1020            topology,
1021            topology_hash,
1022        })
1023    }
1024
1025    fn local_fetch(self) -> Arc<dyn Fetch<T = Self>>
1026    where
1027        Self: Clone,
1028    {
1029        self::local_fetch::LocalFetch::new(self).into_dyn_fetch()
1030    }
1031}
1032
1033impl<T: 'static + Send + Sync + FullHash + Topological> Traversible for T {}
1034
1035pub trait Object<Extra = ()>: Traversible + for<'a> Parse<Input<'a, Extra>> {}
1036
1037impl<T: Traversible + for<'a> Parse<Input<'a, Extra>>, Extra> Object<Extra> for T {}
1038
1039pub trait Inline<Extra = ()>:
1040    Object<Extra> + InlineOutput + for<'a> ParseInline<Input<'a, Extra>>
1041{
1042}
1043
1044impl<T: Object<Extra> + InlineOutput + for<'a> ParseInline<Input<'a, Extra>>, Extra> Inline<Extra>
1045    for T
1046{
1047}
1048
1049pub trait Component: InlineOutput + Traversible + Clone {}
1050
1051impl<T: InlineOutput + Traversible + Clone> Component for T {}
1052
1053pub struct Tags(pub &'static [&'static str], pub &'static [&'static Self]);
1054
1055const fn bytes_compare(l: &[u8], r: &[u8]) -> std::cmp::Ordering {
1056    let mut i = 0;
1057    while i < l.len() && i < r.len() {
1058        if l[i] > r[i] {
1059            return std::cmp::Ordering::Greater;
1060        } else if l[i] < r[i] {
1061            return std::cmp::Ordering::Less;
1062        } else {
1063            i += 1;
1064        }
1065    }
1066    if l.len() > r.len() {
1067        std::cmp::Ordering::Greater
1068    } else if l.len() < r.len() {
1069        std::cmp::Ordering::Less
1070    } else {
1071        std::cmp::Ordering::Equal
1072    }
1073}
1074
1075const fn str_compare(l: &str, r: &str) -> std::cmp::Ordering {
1076    bytes_compare(l.as_bytes(), r.as_bytes())
1077}
1078
1079impl Tags {
1080    const fn min_out(&self, strict_min: Option<&str>, min: &mut Option<&'static str>) {
1081        {
1082            let mut i = 0;
1083            while i < self.0.len() {
1084                let candidate = self.0[i];
1085                i += 1;
1086                if let Some(strict_min) = strict_min
1087                    && str_compare(candidate, strict_min).is_le()
1088                {
1089                    continue;
1090                }
1091                if let Some(min) = min
1092                    && str_compare(candidate, min).is_ge()
1093                {
1094                    continue;
1095                }
1096                *min = Some(candidate);
1097            }
1098        }
1099        {
1100            let mut i = 0;
1101            while i < self.1.len() {
1102                self.1[i].min_out(strict_min, min);
1103                i += 1;
1104            }
1105        }
1106        if let Some(l) = min
1107            && let Some(r) = strict_min
1108        {
1109            assert!(str_compare(l, r).is_gt());
1110        }
1111    }
1112
1113    const fn min(&self, strict_min: Option<&str>) -> Option<&'static str> {
1114        let mut min = None;
1115        self.min_out(strict_min, &mut min);
1116        min
1117    }
1118
1119    const fn const_hash(&self, mut hasher: sha2_const::Sha256) -> sha2_const::Sha256 {
1120        let mut last = None;
1121        let mut i = 0;
1122        while let Some(next) = self.min(last) {
1123            i += 1;
1124            if i > 1000 {
1125                panic!("{}", next);
1126            }
1127            hasher = hasher.update(next.as_bytes());
1128            last = Some(next);
1129        }
1130        hasher
1131    }
1132
1133    const fn hash(&self) -> Hash {
1134        Hash::from_sha256(self.const_hash(sha2_const::Sha256::new()).finalize())
1135    }
1136}
1137
1138#[test]
1139fn min_out_respects_bounds() {
1140    let mut min = None;
1141    Tags(&["c", "b", "a"], &[]).min_out(Some("a"), &mut min);
1142    assert_eq!(min, Some("b"));
1143}
1144
1145#[test]
1146fn const_hash() {
1147    assert_ne!(Tags(&["a", "b"], &[]).hash(), Tags(&["a"], &[]).hash());
1148    assert_eq!(
1149        Tags(&["a", "b"], &[]).hash(),
1150        Tags(&["a"], &[&Tags(&["b"], &[])]).hash(),
1151    );
1152    assert_eq!(Tags(&["a", "b"], &[]).hash(), Tags(&["b", "a"], &[]).hash());
1153    assert_eq!(Tags(&["a", "a"], &[]).hash(), Tags(&["a"], &[]).hash());
1154}
1155
1156pub trait Topology: Resolve {
1157    fn len(&self) -> usize;
1158    fn get(&self, index: usize) -> Option<&Arc<dyn Singular>>;
1159
1160    fn is_empty(&self) -> bool {
1161        self.len() == 0
1162    }
1163}
1164
1165pub trait Singular: Send + Sync + FetchBytes {
1166    fn hash(&self) -> Hash;
1167}
1168
1169pub trait SingularFetch: Singular + Fetch {}
1170
1171impl<T: ?Sized + Singular + Fetch> SingularFetch for T {}
1172
1173impl ToOutput for dyn Singular {
1174    fn to_output(&self, output: &mut impl Output) {
1175        self.hash().to_output(output);
1176    }
1177}
1178
1179impl InlineOutput for dyn Singular {}
1180
1181impl ListHashes for Arc<dyn Singular> {
1182    fn list_hashes(&self, f: &mut impl FnMut(Hash)) {
1183        f(self.hash());
1184    }
1185
1186    fn point_count(&self) -> usize {
1187        1
1188    }
1189}
1190
1191pub type TopoVec = Vec<Arc<dyn Singular>>;
1192
1193impl PointVisitor for TopoVec {
1194    fn visit(&mut self, point: &(impl 'static + SingularFetch<T: Traversible> + Clone)) {
1195        self.push(Arc::new(point.clone()));
1196    }
1197}
1198
1199impl Resolve for TopoVec {
1200    fn resolve<'a>(
1201        &'a self,
1202        address: Address,
1203        _: &'a Arc<dyn Resolve>,
1204    ) -> FailFuture<'a, ByteNode> {
1205        Box::pin(async move {
1206            let singular = self.get(address.index).ok_or(Error::AddressOutOfBounds)?;
1207            if singular.hash() != address.hash {
1208                Err(Error::FullHashMismatch)
1209            } else {
1210                singular.fetch_bytes().await
1211            }
1212        })
1213    }
1214
1215    fn resolve_data(&'_ self, address: Address) -> FailFuture<'_, Vec<u8>> {
1216        Box::pin(async move {
1217            let singular = self.get(address.index).ok_or(Error::AddressOutOfBounds)?;
1218            if singular.hash() != address.hash {
1219                Err(Error::FullHashMismatch)
1220            } else {
1221                singular.fetch_data().await
1222            }
1223        })
1224    }
1225
1226    fn try_resolve_local(
1227        &self,
1228        address: Address,
1229        _: &Arc<dyn Resolve>,
1230    ) -> Result<Option<ByteNode>> {
1231        let singular = self.get(address.index).ok_or(Error::AddressOutOfBounds)?;
1232        if singular.hash() != address.hash {
1233            Err(Error::FullHashMismatch)
1234        } else {
1235            singular.fetch_bytes_local()
1236        }
1237    }
1238
1239    fn topology_hash(&self) -> Option<Hash> {
1240        Some(self.data_hash())
1241    }
1242
1243    fn into_topovec(self: Arc<Self>) -> Option<TopoVec> {
1244        Some((*self).clone())
1245    }
1246}
1247
1248impl Topology for TopoVec {
1249    fn len(&self) -> usize {
1250        self.len()
1251    }
1252
1253    fn get(&self, index: usize) -> Option<&Arc<dyn Singular>> {
1254        (**self).get(index)
1255    }
1256}
1257
1258pub trait ParseSliceRefless: for<'a> Parse<ReflessInput<'a>> {
1259    fn parse_slice_refless(slice: &[u8]) -> crate::Result<Self> {
1260        let input = ReflessInput {
1261            data: Some(ReflessData {
1262                slice,
1263                prefix: Vec::new(),
1264            }),
1265        };
1266        let object = Self::parse(input)?;
1267        Ok(object)
1268    }
1269}
1270
1271impl<T: for<'a> Parse<ReflessInput<'a>>> ParseSliceRefless for T {}
1272
1273pub trait ReflessObject:
1274    'static + Sized + Send + Sync + ToOutput + Tagged + for<'a> Parse<ReflessInput<'a>>
1275{
1276}
1277
1278impl<T: 'static + Sized + Send + Sync + ToOutput + Tagged + for<'a> Parse<ReflessInput<'a>>>
1279    ReflessObject for T
1280{
1281}
1282
1283pub trait ReflessInline:
1284    ReflessObject + InlineOutput + for<'a> ParseInline<ReflessInput<'a>>
1285{
1286}
1287
1288impl<T: ReflessObject + InlineOutput + for<'a> ParseInline<ReflessInput<'a>>> ReflessInline for T {}
1289
1290pub trait Output {
1291    fn write(&mut self, data: &[u8]);
1292    fn is_mangling(&self) -> bool {
1293        false
1294    }
1295    fn is_real(&self) -> bool {
1296        !self.is_mangling()
1297    }
1298    fn as_write(&mut self) -> AsWrite<'_, Self> {
1299        AsWrite { output: self }
1300    }
1301}
1302
1303pub struct AsWrite<'a, O: ?Sized> {
1304    output: &'a mut O,
1305}
1306
1307impl<O: ?Sized + Output> std::io::Write for AsWrite<'_, O> {
1308    fn write(&mut self, data: &[u8]) -> std::io::Result<usize> {
1309        self.output.write(data);
1310        Ok(data.len())
1311    }
1312
1313    fn flush(&mut self) -> std::io::Result<()> {
1314        Ok(())
1315    }
1316}
1317
1318impl Output for Vec<u8> {
1319    fn write(&mut self, data: &[u8]) {
1320        self.extend_from_slice(data);
1321    }
1322}
1323
1324struct MangleOutput<'a, T: ?Sized>(&'a mut T);
1325
1326impl<'a, T: Output> MangleOutput<'a, T> {
1327    fn new(output: &'a mut T) -> Self {
1328        assert!(output.is_real());
1329        assert!(!output.is_mangling());
1330        Self(output)
1331    }
1332}
1333
1334impl<T: ?Sized + Output> Output for MangleOutput<'_, T> {
1335    fn write(&mut self, data: &[u8]) {
1336        self.0.write(data);
1337    }
1338
1339    fn is_mangling(&self) -> bool {
1340        true
1341    }
1342}
1343
1344pub struct Mangled<T: ?Sized>(T);
1345
1346impl<T: ?Sized + ToOutput> ToOutput for Mangled<T> {
1347    fn to_output(&self, output: &mut impl Output) {
1348        self.0.to_output(&mut MangleOutput::new(output));
1349    }
1350}
1351
1352pub trait Size {
1353    const SIZE: usize = <Self::Size as Unsigned>::USIZE;
1354    type Size: Unsigned;
1355}
1356
1357pub trait SizeExt: Size<Size: ArrayLength> + ToOutput {
1358    fn to_array(&self) -> GenericArray<u8, Self::Size> {
1359        struct ArrayOutput<'a> {
1360            data: &'a mut [u8],
1361            offset: usize,
1362        }
1363
1364        impl ArrayOutput<'_> {
1365            fn finalize(self) {
1366                assert_eq!(self.offset, self.data.len());
1367            }
1368        }
1369
1370        impl Output for ArrayOutput<'_> {
1371            fn write(&mut self, data: &[u8]) {
1372                self.data[self.offset..][..data.len()].copy_from_slice(data);
1373                self.offset += data.len();
1374            }
1375        }
1376
1377        let mut array = GenericArray::default();
1378        let mut output = ArrayOutput {
1379            data: &mut array,
1380            offset: 0,
1381        };
1382        self.to_output(&mut output);
1383        output.finalize();
1384        array
1385    }
1386
1387    fn reinterpret<T: FromSized<Size = Self::Size>>(&self) -> T {
1388        T::from_sized(&self.to_array())
1389    }
1390}
1391
1392impl<T: Size<Size: ArrayLength> + ToOutput> SizeExt for T {}
1393
1394pub trait FromSized: Size<Size: ArrayLength> {
1395    fn from_sized(data: &GenericArray<u8, Self::Size>) -> Self;
1396}
1397
1398impl<
1399    A: FromSized<Size = An>,
1400    B: FromSized<Size = Bn>,
1401    An,
1402    Bn: Add<An, Output: ArrayLength + Sub<An, Output = Bn>>,
1403> FromSized for (A, B)
1404{
1405    fn from_sized(data: &GenericArray<u8, Self::Size>) -> Self {
1406        let (a, b) = data.split();
1407        (A::from_sized(a), B::from_sized(b))
1408    }
1409}
1410
1411macro_rules! from_sized_tuple {
1412    (($($t:ident),*), ($($x:ident),*) $(,)?) => {
1413        impl<A, $($t),*, N> FromSized for (A, $($t),*)
1414        where
1415            (A, ($($t),*)): FromSized<Size = N>,
1416            Self: Size<Size = N>,
1417        {
1418            fn from_sized(data: &GenericArray<u8, Self::Size>) -> Self {
1419                let (a, ($($x),*)) = FromSized::from_sized(data);
1420                (a, $($x),*)
1421            }
1422        }
1423    };
1424}
1425
1426from_sized_tuple!((B, C), (b, c));
1427from_sized_tuple!((B, C, D), (b, c, d));
1428from_sized_tuple!((B, C, D, E), (b, c, d, e));
1429from_sized_tuple!((B, C, D, E, F), (b, c, d, e, f));
1430from_sized_tuple!((B, C, D, E, F, G), (b, c, d, e, f, g));
1431from_sized_tuple!((B, C, D, E, F, G, H), (b, c, d, e, f, g, h));
1432from_sized_tuple!((B, C, D, E, F, G, H, I), (b, c, d, e, f, g, h, i));
1433from_sized_tuple!((B, C, D, E, F, G, H, I, J), (b, c, d, e, f, g, h, i, j));
1434from_sized_tuple!(
1435    (B, C, D, E, F, G, H, I, J, K),
1436    (b, c, d, e, f, g, h, i, j, k),
1437);
1438from_sized_tuple!(
1439    (B, C, D, E, F, G, H, I, J, K, L),
1440    (b, c, d, e, f, g, h, i, j, k, l),
1441);
1442
1443pub trait RainbowIterator: Sized + IntoIterator {
1444    fn iter_to_output(self, output: &mut impl Output)
1445    where
1446        Self::Item: InlineOutput,
1447    {
1448        self.into_iter().for_each(|item| item.to_output(output));
1449    }
1450
1451    fn iter_list_hashes(self, f: &mut impl FnMut(Hash))
1452    where
1453        Self::Item: ListHashes,
1454    {
1455        self.into_iter().for_each(|item| item.list_hashes(f));
1456    }
1457
1458    fn iter_traverse(self, visitor: &mut impl PointVisitor)
1459    where
1460        Self::Item: Topological,
1461    {
1462        self.into_iter().for_each(|item| item.traverse(visitor));
1463    }
1464
1465    fn iter_bytes_cmp(self, other: impl IntoIterator<Item = Self::Item>) -> Ordering
1466    where
1467        Self::Item: ByteOrd,
1468    {
1469        self.into_iter()
1470            .map(OrderedByBytes)
1471            .cmp(other.into_iter().map(OrderedByBytes))
1472    }
1473}
1474
1475pub trait ParseInput: Sized {
1476    type Data: AsRef<[u8]> + Deref<Target = [u8]> + Into<Vec<u8>>;
1477    fn push_front(&mut self, data: impl Into<Vec<u8>>) -> crate::Result<()>;
1478    fn read(&mut self, data: &mut [u8]) -> crate::Result<()>;
1479    fn parse_chunk<const N: usize>(&mut self) -> crate::Result<[u8; N]> {
1480        let mut chunk = [0; _];
1481        self.read(&mut chunk)?;
1482        Ok(chunk)
1483    }
1484    fn split_n(&mut self, n: usize) -> crate::Result<Self>;
1485    fn skip_n(&mut self, n: usize) -> crate::Result<()>;
1486    fn find_zero(&mut self) -> crate::Result<usize>;
1487    fn parse_n_ahead(&mut self, n: usize) -> crate::Result<Vec<u8>>;
1488    fn compare_ahead(&mut self, c: &[u8]) -> crate::Result<bool>;
1489    fn split_parse<T: Parse<Self>>(&mut self, n: usize) -> crate::Result<T> {
1490        self.split_n(n)?.parse()
1491    }
1492    fn parse_zero_terminated<T: Parse<Self>>(&mut self) -> crate::Result<(Vec<u8>, T)> {
1493        let n = self.find_zero()?;
1494        let data = self.parse_n_ahead(n)?;
1495        let value = self.split_parse(n)?;
1496        self.skip_n(1)?;
1497        Ok((data, value))
1498    }
1499    fn compare_skip(&mut self, c: &[u8]) -> Result<bool> {
1500        let matches = self.compare_ahead(c)?;
1501        if matches {
1502            self.skip_n(c.len())?
1503        }
1504        Ok(matches)
1505    }
1506    fn parse_compare<T: Parse<Self>>(mut self, c: &[u8]) -> Result<Option<T>> {
1507        if self.compare_skip(c)? {
1508            self.empty()?;
1509            Ok(None)
1510        } else {
1511            Ok(Some(self.parse()?))
1512        }
1513    }
1514    fn parse_compare_inline<T: ParseInline<Self>>(&mut self, c: &[u8]) -> Result<Option<T>> {
1515        if self.compare_skip(c)? {
1516            Ok(None)
1517        } else {
1518            Ok(Some(self.parse_inline()?))
1519        }
1520    }
1521    fn parse_all(self) -> crate::Result<Self::Data>;
1522    fn empty(self) -> crate::Result<()>;
1523    fn non_empty(self) -> crate::Result<Option<Self>>;
1524    fn remaining(self) -> crate::Result<(Self, usize)>;
1525
1526    fn consume(self, f: impl FnMut(&mut Self) -> crate::Result<()>) -> crate::Result<()> {
1527        self.collect(f)
1528    }
1529
1530    fn parse_collect<T: ParseInline<Self>, B: FromIterator<T>>(self) -> crate::Result<B> {
1531        self.collect(|input| input.parse_inline())
1532    }
1533
1534    fn collect<T, B: FromIterator<T>>(
1535        self,
1536        f: impl FnMut(&mut Self) -> crate::Result<T>,
1537    ) -> crate::Result<B> {
1538        self.iter(f).collect()
1539    }
1540
1541    fn iter<T>(
1542        self,
1543        mut f: impl FnMut(&mut Self) -> crate::Result<T>,
1544    ) -> impl Iterator<Item = crate::Result<T>> {
1545        let mut state = Some(self);
1546        std::iter::from_fn(move || {
1547            let mut input = match state.take()?.non_empty() {
1548                Ok(input) => input?,
1549                Err(e) => return Some(Err(e)),
1550            };
1551            let item = f(&mut input);
1552            state = Some(input);
1553            Some(item)
1554        })
1555    }
1556
1557    fn parse_inline<T: ParseInline<Self>>(&mut self) -> crate::Result<T> {
1558        T::parse_inline(self)
1559    }
1560
1561    fn parse<T: Parse<Self>>(self) -> crate::Result<T> {
1562        T::parse(self)
1563    }
1564
1565    fn parse_vec<T: ParseInline<Self>>(self) -> crate::Result<Vec<T>> {
1566        T::parse_vec(self)
1567    }
1568
1569    fn parse_vec_n<T: ParseInline<Self>>(&mut self, n: usize) -> crate::Result<Vec<T>> {
1570        T::parse_vec_n(self, n)
1571    }
1572
1573    fn parse_array<T: ParseInline<Self>, const N: usize>(&mut self) -> crate::Result<[T; N]> {
1574        T::parse_array(self)
1575    }
1576
1577    fn parse_generic_array<T: ParseInline<Self>, N: ArrayLength>(
1578        &mut self,
1579    ) -> crate::Result<GenericArray<T, N>> {
1580        T::parse_generic_array(self)
1581    }
1582
1583    fn as_read<T, E>(
1584        &mut self,
1585        f: impl FnOnce(AsRead<'_, Self>) -> std::result::Result<T, E>,
1586    ) -> crate::Result<T>
1587    where
1588        Error: From<E>,
1589    {
1590        let result = f(AsRead { input: self })?;
1591        self.noop()?;
1592        Ok(result)
1593    }
1594
1595    fn noop(&mut self) -> crate::Result<()> {
1596        self.read(&mut [])
1597    }
1598
1599    fn parse_refless_inline<T: for<'r> ParseInline<ReflessInput<'r>>>(
1600        &mut self,
1601    ) -> crate::Result<T>;
1602
1603    fn parse_refless<T: for<'r> Parse<ReflessInput<'r>>>(self) -> crate::Result<T>;
1604
1605    fn parse_as_inline<T>(
1606        mut self,
1607        f: impl FnOnce(&mut Self) -> crate::Result<T>,
1608    ) -> crate::Result<T> {
1609        let object = f(&mut self)?;
1610        self.empty()?;
1611        Ok(object)
1612    }
1613}
1614
1615pub struct AsRead<'a, I> {
1616    input: &'a mut I,
1617}
1618
1619impl<I: ParseInput> std::io::Read for AsRead<'_, I> {
1620    fn read(&mut self, data: &mut [u8]) -> std::io::Result<usize> {
1621        self.read_exact(data)?;
1622        Ok(data.len())
1623    }
1624
1625    fn read_exact(&mut self, data: &mut [u8]) -> std::io::Result<()> {
1626        self.input.read(data)?;
1627        Ok(())
1628    }
1629
1630    fn read_to_end(&mut self, _: &mut Vec<u8>) -> std::io::Result<usize> {
1631        Err(std::io::ErrorKind::Unsupported.into())
1632    }
1633}
1634
1635pub trait PointInput: ParseInput {
1636    type Extra: 'static + Clone;
1637    type WithExtra<E: 'static + Clone>: PointInput<Extra = E, WithExtra<Self::Extra> = Self>;
1638    fn next_index(&mut self) -> usize;
1639    fn resolve_arc_ref(&self) -> &Arc<dyn Resolve>;
1640    fn resolve(&self) -> Arc<dyn Resolve> {
1641        self.resolve_arc_ref().clone()
1642    }
1643    fn resolve_ref(&self) -> &dyn Resolve {
1644        self.resolve_arc_ref().as_ref()
1645    }
1646    fn with_resolve(self, resolve: Arc<dyn Resolve>) -> Self;
1647    /// Get [`Self::Extra`].
1648    fn extra(&self) -> &Self::Extra;
1649    /// Project the `Extra`. Under some circumstances, prevents an extra [`Clone::clone`].
1650    fn map_extra<E: 'static + Clone>(
1651        self,
1652        f: impl FnOnce(&Self::Extra) -> &E,
1653    ) -> Self::WithExtra<E>;
1654    /// Return the old [`Self::Extra`], give a new [`PointInput`] with `E` as `Extra`.
1655    fn replace_extra<E: 'static + Clone>(self, extra: E) -> (Self::Extra, Self::WithExtra<E>);
1656    /// [`Self::replace_extra`] but discarding [`Self::Extra`].
1657    fn with_extra<E: 'static + Clone>(self, extra: E) -> Self::WithExtra<E> {
1658        self.replace_extra(extra).1
1659    }
1660    /// [`ParseInput::parse`] with a different `Extra`.
1661    fn parse_extra<E: 'static + Clone, T: Parse<Self::WithExtra<E>>>(
1662        self,
1663        extra: E,
1664    ) -> crate::Result<T> {
1665        self.with_extra(extra).parse()
1666    }
1667    /// [`ParseInput::parse_inline`] with a different `Extra`.
1668    fn parse_inline_extra<E: 'static + Clone, T: ParseInline<Self::WithExtra<E>>>(
1669        &mut self,
1670        extra: E,
1671    ) -> crate::Result<T>;
1672}
1673
1674impl<T: Sized + IntoIterator> RainbowIterator for T {}
1675
1676/// This can be parsed by consuming the whole rest of the input.
1677///
1678/// Nothing can be parsed after this. It's implementation's responsibility to ensure there are no
1679/// leftover bytes.
1680pub trait Parse<I: ParseInput>: Sized {
1681    /// Parse consuming the whole stream.
1682    fn parse(input: I) -> crate::Result<Self>;
1683}
1684
1685/// This can be parsed from an input, after which we can correctly parse something else.
1686///
1687/// When parsed as the last object, makes sure there are no bytes left in the input (fails if there
1688/// are).
1689pub trait ParseInline<I: ParseInput>: Parse<I> {
1690    /// Parse without consuming the whole stream. Errors on unexpected EOF.
1691    fn parse_inline(input: &mut I) -> crate::Result<Self>;
1692    /// For implementing [`Parse::parse`].
1693    fn parse_as_inline(input: I) -> crate::Result<Self> {
1694        input.parse_as_inline(|input| input.parse_inline())
1695    }
1696    /// Parse a `Vec` of `Self`. Customisable for optimisations.
1697    fn parse_vec(input: I) -> crate::Result<Vec<Self>> {
1698        input.parse_collect()
1699    }
1700    /// Parse a `Vec` of `Self` of length `n`. Customisable for optimisations.
1701    fn parse_vec_n(input: &mut I, n: usize) -> crate::Result<Vec<Self>> {
1702        (0..n).map(|_| input.parse_inline()).collect()
1703    }
1704    /// Parse an array of `Self`. Customisable for optimisations.
1705    fn parse_array<const N: usize>(input: &mut I) -> crate::Result<[Self; N]> {
1706        let mut scratch = std::array::from_fn(|_| None);
1707        for item in scratch.iter_mut() {
1708            *item = Some(input.parse_inline()?);
1709        }
1710        Ok(scratch.map(Option::unwrap))
1711    }
1712    /// Parse a [`GenericArray`] of `Self`. Customisable for optimisations.
1713    fn parse_generic_array<N: ArrayLength>(input: &mut I) -> crate::Result<GenericArray<Self, N>> {
1714        let mut scratch = GenericArray::default();
1715        for item in scratch.iter_mut() {
1716            *item = Some(input.parse_inline()?);
1717        }
1718        Ok(scratch.map(Option::unwrap))
1719    }
1720}
1721
1722/// Implemented if both types have the exact same layout.
1723/// This implies having the same [`MaybeHasNiche::MnArray`].
1724///
1725/// This is represented as two-way conversion for two reasons:
1726/// - to highlight that the conversion is actual equivalence
1727/// - to increase flexibility (mostly to go around the orphan rule)
1728pub trait Equivalent<T>: Sized {
1729    /// Inverse of [`Equivalent::from_equivalent`].
1730    fn into_equivalent(self) -> T;
1731    /// Inverse of [`Equivalent::into_equivalent`].
1732    fn from_equivalent(object: T) -> Self;
1733}
1734
1735pub trait EquivalentFor<U>: Sized {
1736    fn equivalent_for(self) -> U;
1737}
1738
1739impl<T, U: Equivalent<T>> EquivalentFor<U> for T {
1740    fn equivalent_for(self) -> U {
1741        U::from_equivalent(self)
1742    }
1743}
1744
1745pub fn from_equivalent<U>(object: impl EquivalentFor<U>) -> U {
1746    object.equivalent_for()
1747}
1748
1749/// This `Extra` can be used to parse `T` via [`ParseSliceExtra::parse_slice_extra`].
1750pub trait ExtraFor<T> {
1751    /// [`ParseSliceExtra::parse_slice_extra`].
1752    fn parse(&self, data: &[u8], resolve: &Arc<dyn Resolve>) -> Result<T>;
1753
1754    /// [`Self::parse`], then check that [`FullHash::full_hash`] matches.
1755    fn parse_checked(&self, hash: Hash, data: &[u8], resolve: &Arc<dyn Resolve>) -> Result<T>
1756    where
1757        T: FullHash,
1758    {
1759        let object = self.parse(data, resolve)?;
1760        if object.full_hash() != hash {
1761            Err(Error::FullHashMismatch)
1762        } else {
1763            Ok(object)
1764        }
1765    }
1766}
1767
1768impl<T: for<'a> Parse<Input<'a, Extra>>, Extra: Clone> ExtraFor<T> for Extra {
1769    fn parse(&self, data: &[u8], resolve: &Arc<dyn Resolve>) -> Result<T> {
1770        T::parse_slice_extra(data, resolve, self)
1771    }
1772}
1773
1774impl<T> ToOutput for dyn Send + Sync + ExtraFor<T> {
1775    fn to_output(&self, _: &mut impl Output) {}
1776}
1777
1778impl<T: Tagged> Tagged for dyn Send + Sync + ExtraFor<T> {
1779    const TAGS: Tags = T::TAGS;
1780    const HASH: Hash = T::HASH;
1781}
1782
1783impl<T> Size for dyn Send + Sync + ExtraFor<T> {
1784    type Size = typenum::U0;
1785    const SIZE: usize = 0;
1786}
1787
1788impl<T> InlineOutput for dyn Send + Sync + ExtraFor<T> {}
1789impl<T> ListHashes for dyn Send + Sync + ExtraFor<T> {}
1790impl<T> Topological for dyn Send + Sync + ExtraFor<T> {}
1791
1792impl<T, I: PointInput<Extra: Send + Sync + ExtraFor<T>>> Parse<I>
1793    for Arc<dyn Send + Sync + ExtraFor<T>>
1794{
1795    fn parse(input: I) -> crate::Result<Self> {
1796        Self::parse_as_inline(input)
1797    }
1798}
1799
1800impl<T, I: PointInput<Extra: Send + Sync + ExtraFor<T>>> ParseInline<I>
1801    for Arc<dyn Send + Sync + ExtraFor<T>>
1802{
1803    fn parse_inline(input: &mut I) -> crate::Result<Self> {
1804        Ok(Arc::new(input.extra().clone()))
1805    }
1806}
1807
1808impl<T> MaybeHasNiche for dyn Send + Sync + ExtraFor<T> {
1809    type MnArray = NoNiche<ZeroNoNiche<<Self as Size>::Size>>;
1810}
1811
1812assert_impl!(
1813    impl<T, E> Inline<E> for Arc<dyn Send + Sync + ExtraFor<T>>
1814    where
1815        T: Object<E>,
1816        E: 'static + Send + Sync + Clone + ExtraFor<T>,
1817    {
1818    }
1819);
1820
1821#[doc(hidden)]
1822pub trait BoundPair: Sized {
1823    type T;
1824    type E;
1825}
1826
1827impl<T, E> BoundPair for (T, E) {
1828    type T = T;
1829    type E = E;
1830}
1831
1832#[test]
1833fn options() {
1834    type T0 = ();
1835    type T1 = Option<T0>;
1836    type T2 = Option<T1>;
1837    type T3 = Option<T2>;
1838    type T4 = Option<T3>;
1839    type T5 = Option<T4>;
1840    assert_eq!(T0::SIZE, 0);
1841    assert_eq!(T1::SIZE, 1);
1842    assert_eq!(T2::SIZE, 1);
1843    assert_eq!(T3::SIZE, 1);
1844    assert_eq!(T4::SIZE, 1);
1845    assert_eq!(T5::SIZE, 1);
1846    assert_eq!(Some(Some(Some(()))).vec(), [0]);
1847    assert_eq!(Some(Some(None::<()>)).vec(), [1]);
1848    assert_eq!(Some(None::<Option<()>>).vec(), [2]);
1849    assert_eq!(None::<Option<Option<()>>>.vec(), [3]);
1850
1851    assert_eq!(false.vec(), [0]);
1852    assert_eq!(true.vec(), [1]);
1853    assert_eq!(Some(false).vec(), [0]);
1854    assert_eq!(Some(true).vec(), [1]);
1855    assert_eq!(None::<bool>.vec(), [2]);
1856    assert_eq!(Some(Some(false)).vec(), [0]);
1857    assert_eq!(Some(Some(true)).vec(), [1]);
1858    assert_eq!(Some(None::<bool>).vec(), [2]);
1859    assert_eq!(None::<Option<bool>>.vec(), [3]);
1860    assert_eq!(Some(Some(Some(false))).vec(), [0]);
1861    assert_eq!(Some(Some(Some(true))).vec(), [1]);
1862    assert_eq!(Some(Some(None::<bool>)).vec(), [2]);
1863    assert_eq!(Some(None::<Option<bool>>).vec(), [3]);
1864    assert_eq!(None::<Option<Option<bool>>>.vec(), [4]);
1865    assert_eq!(Option::<Hash>::SIZE, HASH_SIZE);
1866    assert_eq!(Some(()).vec(), [0]);
1867    assert_eq!(Some(((), ())).vec(), [0]);
1868    assert_eq!(Some(((), true)).vec(), [1]);
1869    assert_eq!(Some((true, true)).vec(), [1, 1]);
1870    assert_eq!(Some((Some(true), true)).vec(), [1, 1]);
1871    assert_eq!(Some((None::<bool>, true)).vec(), [2, 1]);
1872    assert_eq!(Some((true, None::<bool>)).vec(), [1, 2]);
1873    assert_eq!(None::<(Option<bool>, bool)>.vec(), [3, 2]);
1874    assert_eq!(None::<(bool, Option<bool>)>.vec(), [2, 3]);
1875    assert_eq!(Some(Some((Some(true), Some(true)))).vec(), [1, 1],);
1876    assert_eq!(Option::<Hash>::SIZE, HASH_SIZE);
1877    assert_eq!(Option::<Option<Hash>>::SIZE, HASH_SIZE);
1878    assert_eq!(Option::<Option<Option<Hash>>>::SIZE, HASH_SIZE);
1879}
1880
1881pub trait TryDefault: Sized {
1882    fn try_default() -> crate::Result<Self>;
1883}
1884
1885impl<T: Default> TryDefault for T {
1886    fn try_default() -> crate::Result<Self> {
1887        Ok(Self::default())
1888    }
1889}
1890
1891pub trait CanonicalExtra {
1892    type Extra;
1893    fn canonical_extra(&self) -> Self::Extra;
1894}
1895
1896impl<A: CanonicalExtra, B> CanonicalExtra for (A, B) {
1897    type Extra = A::Extra;
1898
1899    fn canonical_extra(&self) -> Self::Extra {
1900        self.0.canonical_extra()
1901    }
1902}
object_rainbow/lib.rs

object_rainbow/
lib.rs
