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

object_rainbow/
lib.rs
