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

object_rainbow/
lib.rs
