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 trait Inline<Extra = ()>:
967    Object<Extra> + InlineOutput + for<'a> ParseInline<Input<'a, Extra>>
968{
969}
970
971impl<T: Object<Extra> + InlineOutput + for<'a> ParseInline<Input<'a, Extra>>, Extra> Inline<Extra>
972    for T
973{
974}
975
976pub trait Component: InlineOutput + Traversible + Clone {}
977
978impl<T: InlineOutput + Traversible + Clone> Component for T {}
979
980pub struct Tags(pub &'static [&'static str], pub &'static [&'static Self]);
981
982const fn bytes_compare(l: &[u8], r: &[u8]) -> std::cmp::Ordering {
983    let mut i = 0;
984    while i < l.len() && i < r.len() {
985        if l[i] > r[i] {
986            return std::cmp::Ordering::Greater;
987        } else if l[i] < r[i] {
988            return std::cmp::Ordering::Less;
989        } else {
990            i += 1;
991        }
992    }
993    if l.len() > r.len() {
994        std::cmp::Ordering::Greater
995    } else if l.len() < r.len() {
996        std::cmp::Ordering::Less
997    } else {
998        std::cmp::Ordering::Equal
999    }
1000}
1001
1002const fn str_compare(l: &str, r: &str) -> std::cmp::Ordering {
1003    bytes_compare(l.as_bytes(), r.as_bytes())
1004}
1005
1006impl Tags {
1007    const fn min_out(&self, strict_min: Option<&str>, min: &mut Option<&'static str>) {
1008        {
1009            let mut i = 0;
1010            while i < self.0.len() {
1011                let candidate = self.0[i];
1012                i += 1;
1013                if let Some(strict_min) = strict_min
1014                    && str_compare(candidate, strict_min).is_le()
1015                {
1016                    continue;
1017                }
1018                if let Some(min) = min
1019                    && str_compare(candidate, min).is_ge()
1020                {
1021                    continue;
1022                }
1023                *min = Some(candidate);
1024            }
1025        }
1026        {
1027            let mut i = 0;
1028            while i < self.1.len() {
1029                self.1[i].min_out(strict_min, min);
1030                i += 1;
1031            }
1032        }
1033        if let Some(l) = min
1034            && let Some(r) = strict_min
1035        {
1036            assert!(str_compare(l, r).is_gt());
1037        }
1038    }
1039
1040    const fn min(&self, strict_min: Option<&str>) -> Option<&'static str> {
1041        let mut min = None;
1042        self.min_out(strict_min, &mut min);
1043        min
1044    }
1045
1046    const fn const_hash(&self, mut hasher: sha2_const::Sha256) -> sha2_const::Sha256 {
1047        let mut last = None;
1048        let mut i = 0;
1049        while let Some(next) = self.min(last) {
1050            i += 1;
1051            if i > 1000 {
1052                panic!("{}", next);
1053            }
1054            hasher = hasher.update(next.as_bytes());
1055            last = Some(next);
1056        }
1057        hasher
1058    }
1059
1060    const fn hash(&self) -> Hash {
1061        Hash::from_sha256(self.const_hash(sha2_const::Sha256::new()).finalize())
1062    }
1063}
1064
1065#[test]
1066fn min_out_respects_bounds() {
1067    let mut min = None;
1068    Tags(&["c", "b", "a"], &[]).min_out(Some("a"), &mut min);
1069    assert_eq!(min, Some("b"));
1070}
1071
1072#[test]
1073fn const_hash() {
1074    assert_ne!(Tags(&["a", "b"], &[]).hash(), Tags(&["a"], &[]).hash());
1075    assert_eq!(
1076        Tags(&["a", "b"], &[]).hash(),
1077        Tags(&["a"], &[&Tags(&["b"], &[])]).hash(),
1078    );
1079    assert_eq!(Tags(&["a", "b"], &[]).hash(), Tags(&["b", "a"], &[]).hash());
1080    assert_eq!(Tags(&["a", "a"], &[]).hash(), Tags(&["a"], &[]).hash());
1081}
1082
1083pub trait Topology: Resolve {
1084    fn len(&self) -> usize;
1085    fn get(&self, index: usize) -> Option<&Arc<dyn Singular>>;
1086
1087    fn is_empty(&self) -> bool {
1088        self.len() == 0
1089    }
1090}
1091
1092pub trait Singular: Send + Sync + FetchBytes {
1093    fn hash(&self) -> Hash;
1094}
1095
1096pub trait SingularFetch: Singular + Fetch {}
1097
1098impl<T: ?Sized + Singular + Fetch> SingularFetch for T {}
1099
1100impl ToOutput for dyn Singular {
1101    fn to_output(&self, output: &mut impl Output) {
1102        self.hash().to_output(output);
1103    }
1104}
1105
1106impl InlineOutput for dyn Singular {}
1107
1108impl ListHashes for Arc<dyn Singular> {
1109    fn list_hashes(&self, f: &mut impl FnMut(Hash)) {
1110        f(self.hash());
1111    }
1112
1113    fn point_count(&self) -> usize {
1114        1
1115    }
1116}
1117
1118pub type TopoVec = Vec<Arc<dyn Singular>>;
1119
1120impl PointVisitor for TopoVec {
1121    fn visit(&mut self, point: &(impl 'static + SingularFetch<T: Traversible> + Clone)) {
1122        self.push(Arc::new(point.clone()));
1123    }
1124}
1125
1126impl Resolve for TopoVec {
1127    fn resolve<'a>(
1128        &'a self,
1129        address: Address,
1130        _: &'a Arc<dyn Resolve>,
1131    ) -> FailFuture<'a, ByteNode> {
1132        Box::pin(async move {
1133            let singular = self.get(address.index).ok_or(Error::AddressOutOfBounds)?;
1134            if singular.hash() != address.hash {
1135                Err(Error::FullHashMismatch)
1136            } else {
1137                singular.fetch_bytes().await
1138            }
1139        })
1140    }
1141
1142    fn resolve_data(&'_ self, address: Address) -> FailFuture<'_, Vec<u8>> {
1143        Box::pin(async move {
1144            let singular = self.get(address.index).ok_or(Error::AddressOutOfBounds)?;
1145            if singular.hash() != address.hash {
1146                Err(Error::FullHashMismatch)
1147            } else {
1148                singular.fetch_data().await
1149            }
1150        })
1151    }
1152
1153    fn try_resolve_local(
1154        &self,
1155        address: Address,
1156        _: &Arc<dyn Resolve>,
1157    ) -> Result<Option<ByteNode>> {
1158        let singular = self.get(address.index).ok_or(Error::AddressOutOfBounds)?;
1159        if singular.hash() != address.hash {
1160            Err(Error::FullHashMismatch)
1161        } else {
1162            singular.fetch_bytes_local()
1163        }
1164    }
1165
1166    fn topology_hash(&self) -> Option<Hash> {
1167        Some(self.data_hash())
1168    }
1169
1170    fn into_topovec(self: Arc<Self>) -> Option<TopoVec> {
1171        Some((*self).clone())
1172    }
1173}
1174
1175impl Topology for TopoVec {
1176    fn len(&self) -> usize {
1177        self.len()
1178    }
1179
1180    fn get(&self, index: usize) -> Option<&Arc<dyn Singular>> {
1181        (**self).get(index)
1182    }
1183}
1184
1185pub trait ParseSliceRefless: for<'a> Parse<ReflessInput<'a>> {
1186    fn parse_slice_refless(slice: &[u8]) -> crate::Result<Self> {
1187        let input = ReflessInput {
1188            data: Some(ReflessData {
1189                slice,
1190                prefix: Vec::new(),
1191            }),
1192        };
1193        let object = Self::parse(input)?;
1194        Ok(object)
1195    }
1196}
1197
1198impl<T: for<'a> Parse<ReflessInput<'a>>> ParseSliceRefless for T {}
1199
1200pub trait ReflessObject:
1201    'static + Sized + Send + Sync + ToOutput + Tagged + for<'a> Parse<ReflessInput<'a>>
1202{
1203}
1204
1205impl<T: 'static + Sized + Send + Sync + ToOutput + Tagged + for<'a> Parse<ReflessInput<'a>>>
1206    ReflessObject for T
1207{
1208}
1209
1210pub trait ReflessInline:
1211    ReflessObject + InlineOutput + for<'a> ParseInline<ReflessInput<'a>>
1212{
1213}
1214
1215impl<T: ReflessObject + InlineOutput + for<'a> ParseInline<ReflessInput<'a>>> ReflessInline for T {}
1216
1217pub trait Output {
1218    fn write(&mut self, data: &[u8]);
1219    fn is_mangling(&self) -> bool {
1220        false
1221    }
1222    fn is_real(&self) -> bool {
1223        !self.is_mangling()
1224    }
1225    fn as_write(&mut self) -> AsWrite<'_, Self> {
1226        AsWrite { output: self }
1227    }
1228}
1229
1230pub struct AsWrite<'a, O: ?Sized> {
1231    output: &'a mut O,
1232}
1233
1234impl<O: ?Sized + Output> std::io::Write for AsWrite<'_, O> {
1235    fn write(&mut self, data: &[u8]) -> std::io::Result<usize> {
1236        self.output.write(data);
1237        Ok(data.len())
1238    }
1239
1240    fn flush(&mut self) -> std::io::Result<()> {
1241        Ok(())
1242    }
1243}
1244
1245impl Output for Vec<u8> {
1246    fn write(&mut self, data: &[u8]) {
1247        self.extend_from_slice(data);
1248    }
1249}
1250
1251struct MangleOutput<'a, T: ?Sized>(&'a mut T);
1252
1253impl<'a, T: Output> MangleOutput<'a, T> {
1254    fn new(output: &'a mut T) -> Self {
1255        assert!(output.is_real());
1256        assert!(!output.is_mangling());
1257        Self(output)
1258    }
1259}
1260
1261impl<T: ?Sized + Output> Output for MangleOutput<'_, T> {
1262    fn write(&mut self, data: &[u8]) {
1263        self.0.write(data);
1264    }
1265
1266    fn is_mangling(&self) -> bool {
1267        true
1268    }
1269}
1270
1271pub struct Mangled<T: ?Sized>(T);
1272
1273impl<T: ?Sized + ToOutput> ToOutput for Mangled<T> {
1274    fn to_output(&self, output: &mut impl Output) {
1275        self.0.to_output(&mut MangleOutput::new(output));
1276    }
1277}
1278
1279pub trait Size {
1280    const SIZE: usize = <Self::Size as Unsigned>::USIZE;
1281    type Size: Unsigned;
1282}
1283
1284pub trait SizeExt: Size<Size: ArrayLength> + ToOutput {
1285    fn to_array(&self) -> GenericArray<u8, Self::Size> {
1286        struct ArrayOutput<'a> {
1287            data: &'a mut [u8],
1288            offset: usize,
1289        }
1290
1291        impl ArrayOutput<'_> {
1292            fn finalize(self) {
1293                assert_eq!(self.offset, self.data.len());
1294            }
1295        }
1296
1297        impl Output for ArrayOutput<'_> {
1298            fn write(&mut self, data: &[u8]) {
1299                self.data[self.offset..][..data.len()].copy_from_slice(data);
1300                self.offset += data.len();
1301            }
1302        }
1303
1304        let mut array = GenericArray::default();
1305        let mut output = ArrayOutput {
1306            data: &mut array,
1307            offset: 0,
1308        };
1309        self.to_output(&mut output);
1310        output.finalize();
1311        array
1312    }
1313
1314    fn reinterpret<T: FromSized<Size = Self::Size>>(&self) -> T {
1315        T::from_sized(&self.to_array())
1316    }
1317}
1318
1319impl<T: Size<Size: ArrayLength> + ToOutput> SizeExt for T {}
1320
1321pub trait FromSized: Size<Size: ArrayLength> {
1322    fn from_sized(data: &GenericArray<u8, Self::Size>) -> Self;
1323}
1324
1325impl<
1326    A: FromSized<Size = An>,
1327    B: FromSized<Size = Bn>,
1328    An,
1329    Bn: Add<An, Output: ArrayLength + Sub<An, Output = Bn>>,
1330> FromSized for (A, B)
1331{
1332    fn from_sized(data: &GenericArray<u8, Self::Size>) -> Self {
1333        let (a, b) = data.split();
1334        (A::from_sized(a), B::from_sized(b))
1335    }
1336}
1337
1338pub trait RainbowIterator: Sized + IntoIterator {
1339    fn iter_to_output(self, output: &mut impl Output)
1340    where
1341        Self::Item: InlineOutput,
1342    {
1343        self.into_iter().for_each(|item| item.to_output(output));
1344    }
1345
1346    fn iter_list_hashes(self, f: &mut impl FnMut(Hash))
1347    where
1348        Self::Item: ListHashes,
1349    {
1350        self.into_iter().for_each(|item| item.list_hashes(f));
1351    }
1352
1353    fn iter_traverse(self, visitor: &mut impl PointVisitor)
1354    where
1355        Self::Item: Topological,
1356    {
1357        self.into_iter().for_each(|item| item.traverse(visitor));
1358    }
1359
1360    fn iter_bytes_cmp(self, other: impl IntoIterator<Item = Self::Item>) -> Ordering
1361    where
1362        Self::Item: ByteOrd,
1363    {
1364        self.into_iter()
1365            .map(OrderedByBytes)
1366            .cmp(other.into_iter().map(OrderedByBytes))
1367    }
1368}
1369
1370pub trait ParseInput: Sized {
1371    type Data: AsRef<[u8]> + Deref<Target = [u8]> + Into<Vec<u8>>;
1372    fn push_front(&mut self, data: impl Into<Vec<u8>>) -> crate::Result<()>;
1373    fn read(&mut self, data: &mut [u8]) -> crate::Result<()>;
1374    fn parse_chunk<const N: usize>(&mut self) -> crate::Result<[u8; N]> {
1375        let mut chunk = [0; _];
1376        self.read(&mut chunk)?;
1377        Ok(chunk)
1378    }
1379    fn split_n(&mut self, n: usize) -> crate::Result<Self>;
1380    fn skip_n(&mut self, n: usize) -> crate::Result<()>;
1381    fn find_zero(&mut self) -> crate::Result<usize>;
1382    fn parse_n_ahead(&mut self, n: usize) -> crate::Result<Vec<u8>>;
1383    fn compare_ahead(&mut self, c: &[u8]) -> crate::Result<bool>;
1384    fn split_parse<T: Parse<Self>>(&mut self, n: usize) -> crate::Result<T> {
1385        self.split_n(n)?.parse()
1386    }
1387    fn parse_zero_terminated<T: Parse<Self>>(&mut self) -> crate::Result<(Vec<u8>, T)> {
1388        let n = self.find_zero()?;
1389        let data = self.parse_n_ahead(n)?;
1390        let value = self.split_parse(n)?;
1391        self.skip_n(1)?;
1392        Ok((data, value))
1393    }
1394    fn parse_compare<T: Parse<Self>>(&mut self, c: &[u8]) -> Result<Option<T>> {
1395        if self.compare_ahead(c)? {
1396            self.skip_n(c.len())?;
1397            Ok(None)
1398        } else {
1399            Ok(Some(self.split_parse(c.len())?))
1400        }
1401    }
1402    fn parse_all(self) -> crate::Result<Self::Data>;
1403    fn empty(self) -> crate::Result<()>;
1404    fn non_empty(self) -> crate::Result<Option<Self>>;
1405
1406    fn consume(self, f: impl FnMut(&mut Self) -> crate::Result<()>) -> crate::Result<()> {
1407        self.collect(f)
1408    }
1409
1410    fn parse_collect<T: ParseInline<Self>, B: FromIterator<T>>(self) -> crate::Result<B> {
1411        self.collect(|input| input.parse_inline())
1412    }
1413
1414    fn collect<T, B: FromIterator<T>>(
1415        self,
1416        f: impl FnMut(&mut Self) -> crate::Result<T>,
1417    ) -> crate::Result<B> {
1418        self.iter(f).collect()
1419    }
1420
1421    fn iter<T>(
1422        self,
1423        mut f: impl FnMut(&mut Self) -> crate::Result<T>,
1424    ) -> impl Iterator<Item = crate::Result<T>> {
1425        let mut state = Some(self);
1426        std::iter::from_fn(move || {
1427            let mut input = match state.take()?.non_empty() {
1428                Ok(input) => input?,
1429                Err(e) => return Some(Err(e)),
1430            };
1431            let item = f(&mut input);
1432            state = Some(input);
1433            Some(item)
1434        })
1435    }
1436
1437    fn parse_inline<T: ParseInline<Self>>(&mut self) -> crate::Result<T> {
1438        T::parse_inline(self)
1439    }
1440
1441    fn parse<T: Parse<Self>>(self) -> crate::Result<T> {
1442        T::parse(self)
1443    }
1444
1445    fn parse_vec<T: ParseInline<Self>>(self) -> crate::Result<Vec<T>> {
1446        T::parse_vec(self)
1447    }
1448
1449    fn parse_vec_n<T: ParseInline<Self>>(&mut self, n: usize) -> crate::Result<Vec<T>> {
1450        T::parse_vec_n(self, n)
1451    }
1452
1453    fn parse_array<T: ParseInline<Self>, const N: usize>(&mut self) -> crate::Result<[T; N]> {
1454        T::parse_array(self)
1455    }
1456
1457    fn parse_generic_array<T: ParseInline<Self>, N: ArrayLength>(
1458        &mut self,
1459    ) -> crate::Result<GenericArray<T, N>> {
1460        T::parse_generic_array(self)
1461    }
1462
1463    fn as_read<T, E>(
1464        &mut self,
1465        f: impl FnOnce(AsRead<'_, Self>) -> std::result::Result<T, E>,
1466    ) -> crate::Result<T>
1467    where
1468        Error: From<E>,
1469    {
1470        let result = f(AsRead { input: self })?;
1471        self.noop()?;
1472        Ok(result)
1473    }
1474
1475    fn noop(&mut self) -> crate::Result<()> {
1476        self.read(&mut [])
1477    }
1478
1479    fn parse_refless_inline<T: for<'r> ParseInline<ReflessInput<'r>>>(
1480        &mut self,
1481    ) -> crate::Result<T>;
1482
1483    fn parse_refless<T: for<'r> Parse<ReflessInput<'r>>>(self) -> crate::Result<T>;
1484}
1485
1486pub struct AsRead<'a, I> {
1487    input: &'a mut I,
1488}
1489
1490impl<I: ParseInput> std::io::Read for AsRead<'_, I> {
1491    fn read(&mut self, data: &mut [u8]) -> std::io::Result<usize> {
1492        self.read_exact(data)?;
1493        Ok(data.len())
1494    }
1495
1496    fn read_exact(&mut self, data: &mut [u8]) -> std::io::Result<()> {
1497        self.input.read(data)?;
1498        Ok(())
1499    }
1500
1501    fn read_to_end(&mut self, _: &mut Vec<u8>) -> std::io::Result<usize> {
1502        Err(std::io::ErrorKind::Unsupported.into())
1503    }
1504}
1505
1506pub trait PointInput: ParseInput {
1507    type Extra: 'static + Clone;
1508    type WithExtra<E: 'static + Clone>: PointInput<Extra = E, WithExtra<Self::Extra> = Self>;
1509    fn next_index(&mut self) -> usize;
1510    fn resolve_arc_ref(&self) -> &Arc<dyn Resolve>;
1511    fn resolve(&self) -> Arc<dyn Resolve> {
1512        self.resolve_arc_ref().clone()
1513    }
1514    fn resolve_ref(&self) -> &dyn Resolve {
1515        self.resolve_arc_ref().as_ref()
1516    }
1517    fn with_resolve(self, resolve: Arc<dyn Resolve>) -> Self;
1518    /// Get [`Self::Extra`].
1519    fn extra(&self) -> &Self::Extra;
1520    /// Project the `Extra`. Under some circumstances, prevents an extra [`Clone::clone`].
1521    fn map_extra<E: 'static + Clone>(
1522        self,
1523        f: impl FnOnce(&Self::Extra) -> &E,
1524    ) -> Self::WithExtra<E>;
1525    /// Return the old [`Self::Extra`], give a new [`PointInput`] with `E` as `Extra`.
1526    fn replace_extra<E: 'static + Clone>(self, extra: E) -> (Self::Extra, Self::WithExtra<E>);
1527    /// [`Self::replace_extra`] but discarding [`Self::Extra`].
1528    fn with_extra<E: 'static + Clone>(self, extra: E) -> Self::WithExtra<E> {
1529        self.replace_extra(extra).1
1530    }
1531    /// [`ParseInput::parse`] with a different `Extra`.
1532    fn parse_extra<E: 'static + Clone, T: Parse<Self::WithExtra<E>>>(
1533        self,
1534        extra: E,
1535    ) -> crate::Result<T> {
1536        self.with_extra(extra).parse()
1537    }
1538    /// [`ParseInput::parse_inline`] with a different `Extra`.
1539    fn parse_inline_extra<E: 'static + Clone, T: ParseInline<Self::WithExtra<E>>>(
1540        &mut self,
1541        extra: E,
1542    ) -> crate::Result<T>;
1543}
1544
1545impl<T: Sized + IntoIterator> RainbowIterator for T {}
1546
1547/// This can be parsed by consuming the whole rest of the input.
1548///
1549/// Nothing can be parsed after this. It's implementation's responsibility to ensure there are no
1550/// leftover bytes.
1551pub trait Parse<I: ParseInput>: Sized {
1552    /// Parse consuming the whole stream.
1553    fn parse(input: I) -> crate::Result<Self>;
1554}
1555
1556/// This can be parsed from an input, after which we can correctly parse something else.
1557///
1558/// When parsed as the last object, makes sure there are no bytes left in the input (fails if there
1559/// are).
1560pub trait ParseInline<I: ParseInput>: Parse<I> {
1561    /// Parse without consuming the whole stream. Errors on unexpected EOF.
1562    fn parse_inline(input: &mut I) -> crate::Result<Self>;
1563    /// For implementing [`Parse::parse`].
1564    fn parse_as_inline(mut input: I) -> crate::Result<Self> {
1565        let object = Self::parse_inline(&mut input)?;
1566        input.empty()?;
1567        Ok(object)
1568    }
1569    /// Parse a `Vec` of `Self`. Customisable for optimisations.
1570    fn parse_vec(input: I) -> crate::Result<Vec<Self>> {
1571        input.parse_collect()
1572    }
1573    /// Parse a `Vec` of `Self` of length `n`. Customisable for optimisations.
1574    fn parse_vec_n(input: &mut I, n: usize) -> crate::Result<Vec<Self>> {
1575        (0..n).map(|_| input.parse_inline()).collect()
1576    }
1577    /// Parse an array of `Self`. Customisable for optimisations.
1578    fn parse_array<const N: usize>(input: &mut I) -> crate::Result<[Self; N]> {
1579        let mut scratch = std::array::from_fn(|_| None);
1580        for item in scratch.iter_mut() {
1581            *item = Some(input.parse_inline()?);
1582        }
1583        Ok(scratch.map(Option::unwrap))
1584    }
1585    /// Parse a [`GenericArray`] of `Self`. Customisable for optimisations.
1586    fn parse_generic_array<N: ArrayLength>(input: &mut I) -> crate::Result<GenericArray<Self, N>> {
1587        let mut scratch = GenericArray::default();
1588        for item in scratch.iter_mut() {
1589            *item = Some(input.parse_inline()?);
1590        }
1591        Ok(scratch.map(Option::unwrap))
1592    }
1593}
1594
1595/// Implemented if both types have the exact same layout.
1596/// This implies having the same [`MaybeHasNiche::MnArray`].
1597///
1598/// This is represented as two-way conversion for two reasons:
1599/// - to highlight that the conversion is actual equivalence
1600/// - to increase flexibility (mostly to go around the orphan rule)
1601pub trait Equivalent<T>: Sized {
1602    /// Inverse of [`Equivalent::from_equivalent`].
1603    fn into_equivalent(self) -> T;
1604    /// Inverse of [`Equivalent::into_equivalent`].
1605    fn from_equivalent(object: T) -> Self;
1606}
1607
1608pub trait EquivalentFor<U>: Sized {
1609    fn equivalent_for(self) -> U;
1610}
1611
1612impl<T, U: Equivalent<T>> EquivalentFor<U> for T {
1613    fn equivalent_for(self) -> U {
1614        U::from_equivalent(self)
1615    }
1616}
1617
1618pub fn from_equivalent<U>(object: impl EquivalentFor<U>) -> U {
1619    object.equivalent_for()
1620}
1621
1622/// This `Extra` can be used to parse `T` via [`ParseSliceExtra::parse_slice_extra`].
1623pub trait ExtraFor<T> {
1624    /// [`ParseSliceExtra::parse_slice_extra`].
1625    fn parse(&self, data: &[u8], resolve: &Arc<dyn Resolve>) -> Result<T>;
1626
1627    /// [`Self::parse`], then check that [`FullHash::full_hash`] matches.
1628    fn parse_checked(&self, hash: Hash, data: &[u8], resolve: &Arc<dyn Resolve>) -> Result<T>
1629    where
1630        T: FullHash,
1631    {
1632        let object = self.parse(data, resolve)?;
1633        if object.full_hash() != hash {
1634            Err(Error::FullHashMismatch)
1635        } else {
1636            Ok(object)
1637        }
1638    }
1639}
1640
1641impl<T: for<'a> Parse<Input<'a, Extra>>, Extra: Clone> ExtraFor<T> for Extra {
1642    fn parse(&self, data: &[u8], resolve: &Arc<dyn Resolve>) -> Result<T> {
1643        T::parse_slice_extra(data, resolve, self)
1644    }
1645}
1646
1647impl<T> ToOutput for dyn Send + Sync + ExtraFor<T> {
1648    fn to_output(&self, _: &mut impl Output) {}
1649}
1650
1651impl<T: Tagged> Tagged for dyn Send + Sync + ExtraFor<T> {
1652    const TAGS: Tags = T::TAGS;
1653    const HASH: Hash = T::HASH;
1654}
1655
1656impl<T> Size for dyn Send + Sync + ExtraFor<T> {
1657    type Size = typenum::U0;
1658    const SIZE: usize = 0;
1659}
1660
1661impl<T> InlineOutput for dyn Send + Sync + ExtraFor<T> {}
1662impl<T> ListHashes for dyn Send + Sync + ExtraFor<T> {}
1663impl<T> Topological for dyn Send + Sync + ExtraFor<T> {}
1664
1665impl<T, I: PointInput<Extra: Send + Sync + ExtraFor<T>>> Parse<I>
1666    for Arc<dyn Send + Sync + ExtraFor<T>>
1667{
1668    fn parse(input: I) -> crate::Result<Self> {
1669        Self::parse_as_inline(input)
1670    }
1671}
1672
1673impl<T, I: PointInput<Extra: Send + Sync + ExtraFor<T>>> ParseInline<I>
1674    for Arc<dyn Send + Sync + ExtraFor<T>>
1675{
1676    fn parse_inline(input: &mut I) -> crate::Result<Self> {
1677        Ok(Arc::new(input.extra().clone()))
1678    }
1679}
1680
1681impl<T> MaybeHasNiche for dyn Send + Sync + ExtraFor<T> {
1682    type MnArray = NoNiche<ZeroNoNiche<<Self as Size>::Size>>;
1683}
1684
1685assert_impl!(
1686    impl<T, E> Inline<E> for Arc<dyn Send + Sync + ExtraFor<T>>
1687    where
1688        T: Object<E>,
1689        E: 'static + Send + Sync + Clone + ExtraFor<T>,
1690    {
1691    }
1692);
1693
1694#[doc(hidden)]
1695pub trait BoundPair: Sized {
1696    type T;
1697    type E;
1698}
1699
1700impl<T, E> BoundPair for (T, E) {
1701    type T = T;
1702    type E = E;
1703}
1704
1705#[test]
1706fn options() {
1707    type T0 = ();
1708    type T1 = Option<T0>;
1709    type T2 = Option<T1>;
1710    type T3 = Option<T2>;
1711    type T4 = Option<T3>;
1712    type T5 = Option<T4>;
1713    assert_eq!(T0::SIZE, 0);
1714    assert_eq!(T1::SIZE, 1);
1715    assert_eq!(T2::SIZE, 1);
1716    assert_eq!(T3::SIZE, 1);
1717    assert_eq!(T4::SIZE, 1);
1718    assert_eq!(T5::SIZE, 1);
1719    assert_eq!(Some(Some(Some(()))).vec(), [0]);
1720    assert_eq!(Some(Some(None::<()>)).vec(), [1]);
1721    assert_eq!(Some(None::<Option<()>>).vec(), [2]);
1722    assert_eq!(None::<Option<Option<()>>>.vec(), [3]);
1723
1724    assert_eq!(false.vec(), [0]);
1725    assert_eq!(true.vec(), [1]);
1726    assert_eq!(Some(false).vec(), [0]);
1727    assert_eq!(Some(true).vec(), [1]);
1728    assert_eq!(None::<bool>.vec(), [2]);
1729    assert_eq!(Some(Some(false)).vec(), [0]);
1730    assert_eq!(Some(Some(true)).vec(), [1]);
1731    assert_eq!(Some(None::<bool>).vec(), [2]);
1732    assert_eq!(None::<Option<bool>>.vec(), [3]);
1733    assert_eq!(Some(Some(Some(false))).vec(), [0]);
1734    assert_eq!(Some(Some(Some(true))).vec(), [1]);
1735    assert_eq!(Some(Some(None::<bool>)).vec(), [2]);
1736    assert_eq!(Some(None::<Option<bool>>).vec(), [3]);
1737    assert_eq!(None::<Option<Option<bool>>>.vec(), [4]);
1738    assert_eq!(Option::<Hash>::SIZE, HASH_SIZE);
1739    assert_eq!(Some(()).vec(), [0]);
1740    assert_eq!(Some(((), ())).vec(), [0]);
1741    assert_eq!(Some(((), true)).vec(), [1]);
1742    assert_eq!(Some((true, true)).vec(), [1, 1]);
1743    assert_eq!(Some((Some(true), true)).vec(), [1, 1]);
1744    assert_eq!(Some((None::<bool>, true)).vec(), [2, 1]);
1745    assert_eq!(Some((true, None::<bool>)).vec(), [1, 2]);
1746    assert_eq!(None::<(Option<bool>, bool)>.vec(), [3, 2]);
1747    assert_eq!(None::<(bool, Option<bool>)>.vec(), [2, 3]);
1748    assert_eq!(Some(Some((Some(true), Some(true)))).vec(), [1, 1],);
1749    assert_eq!(Option::<Hash>::SIZE, HASH_SIZE);
1750    assert_eq!(Option::<Option<Hash>>::SIZE, HASH_SIZE);
1751    assert_eq!(Option::<Option<Option<Hash>>>::SIZE, HASH_SIZE);
1752}
object_rainbow/lib.rs

object_rainbow/
lib.rs
