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, TypeId},
9    borrow::Cow,
10    cell::Cell,
11    convert::Infallible,
12    future::ready,
13    marker::PhantomData,
14    ops::{Deref, DerefMut},
15    pin::Pin,
16    sync::Arc,
17};
18
19pub use anyhow::anyhow;
20use generic_array::{ArrayLength, GenericArray, functional::FunctionalSequence};
21pub use object_rainbow_derive::{
22    Enum, InlineOutput, ListHashes, MaybeHasNiche, Parse, ParseAsInline, ParseInline, Size, Tagged,
23    ToOutput, Topological,
24};
25use sha2::{Digest, Sha256};
26#[doc(hidden)]
27pub use typenum;
28use typenum::Unsigned;
29
30pub use self::enumkind::Enum;
31pub use self::error::{Error, Result};
32pub use self::hash::{Hash, OptionalHash};
33pub use self::niche::{
34    AutoEnumNiche, AutoNiche, HackNiche, MaybeHasNiche, Niche, NicheForUnsized, NoNiche, OneNiche,
35    SomeNiche, ZeroNiche, ZeroNoNiche,
36};
37#[doc(hidden)]
38pub use self::niche::{MaybeNiche, MnArray, NicheFoldOrArray, NicheOr};
39
40mod assert_impl;
41pub mod enumkind;
42mod error;
43mod hash;
44pub mod hashed;
45mod impls;
46pub mod incr_byte_niche;
47pub mod length_prefixed;
48mod niche;
49pub mod numeric;
50pub mod partial_byte_tag;
51pub mod zero_terminated;
52
53/// SHA-256 hash size in bytes.
54pub const HASH_SIZE: usize = sha2_const::Sha256::DIGEST_SIZE;
55
56/// Address within a [`PointInput`].
57///
58/// This was introduced:
59/// - to avoid using a [`Hash`]-only map
60/// - to differentiate between separate [`Hash`]es within a context
61#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, ParseAsInline)]
62pub struct Address {
63    /// Monotonically incremented index. This is not present at all in the actual format.
64    pub index: usize,
65    /// Only this part is part of the parsed/generated input.
66    pub hash: Hash,
67}
68
69impl Address {
70    /// Construct an address which is invalid within parsing context, but can be used in map-based
71    /// [`Resolve`]s.
72    pub fn from_hash(hash: Hash) -> Self {
73        Self {
74            index: usize::MAX,
75            hash,
76        }
77    }
78}
79
80impl<I: PointInput> ParseInline<I> for Address {
81    fn parse_inline(input: &mut I) -> crate::Result<Self> {
82        Ok(Self {
83            index: input.next_index(),
84            hash: input.parse_inline()?,
85        })
86    }
87}
88
89/// Fallible future type yielding either `T` or [`Error`].
90pub type FailFuture<'a, T> = Pin<Box<dyn 'a + Send + Future<Output = Result<T>>>>;
91
92pub type Node<T> = (T, Arc<dyn Resolve>);
93
94/// Returned by [`Resolve`] and [`FetchBytes`]. Represents traversal through the object graph.
95pub type ByteNode = Node<Vec<u8>>;
96
97/// Trait for contextually using [`Any`]. Can itself be implemented for non-`'static` and `?Sized`
98/// types, and is `dyn`-compatible.
99pub trait AsAny {
100    /// Get a shared RTTI reference.
101    fn any_ref(&self) -> &dyn Any
102    where
103        Self: 'static;
104    /// Get an exclusive RTTI reference.
105    fn any_mut(&mut self) -> &mut dyn Any
106    where
107        Self: 'static;
108    /// Get an RTTI [`Box`].
109    fn any_box(self: Box<Self>) -> Box<dyn Any>
110    where
111        Self: 'static;
112    /// Get an RTTI [`Arc`].
113    fn any_arc(self: Arc<Self>) -> Arc<dyn Any>
114    where
115        Self: 'static;
116    /// Get an RTTI [`Arc`] which is also [`Send`].
117    fn any_arc_sync(self: Arc<Self>) -> Arc<dyn Send + Sync + Any>
118    where
119        Self: 'static + Send + Sync;
120}
121
122impl<T> AsAny for T {
123    fn any_ref(&self) -> &dyn Any
124    where
125        Self: 'static,
126    {
127        self
128    }
129
130    fn any_mut(&mut self) -> &mut dyn Any
131    where
132        Self: 'static,
133    {
134        self
135    }
136
137    fn any_box(self: Box<Self>) -> Box<dyn Any>
138    where
139        Self: 'static,
140    {
141        self
142    }
143
144    fn any_arc(self: Arc<Self>) -> Arc<dyn Any>
145    where
146        Self: 'static,
147    {
148        self
149    }
150
151    fn any_arc_sync(self: Arc<Self>) -> Arc<dyn Send + Sync + Any>
152    where
153        Self: 'static + Send + Sync,
154    {
155        self
156    }
157}
158
159/// Something that can resolve [`Address`]es to [`ByteNode`]s.
160pub trait Resolve: Send + Sync + AsAny {
161    /// Resolve the address. For an [`Object`], this is what gets used as [`PointInput`].
162    fn resolve<'a>(
163        &'a self,
164        address: Address,
165        this: &'a Arc<dyn Resolve>,
166    ) -> FailFuture<'a, ByteNode>;
167    fn resolve_data(&'_ self, address: Address) -> FailFuture<'_, Vec<u8>>;
168    fn try_resolve_local(
169        &self,
170        address: Address,
171        this: &Arc<dyn Resolve>,
172    ) -> Result<Option<ByteNode>> {
173        let _ = address;
174        let _ = this;
175        Ok(None)
176    }
177    /// Get a dynamic extension for a specific [`Address`].
178    fn resolve_extension(&self, address: Address, typeid: TypeId) -> crate::Result<&dyn Any> {
179        let _ = address;
180        let _ = typeid;
181        Err(Error::UnknownExtension)
182    }
183    /// Get a dynamic extension.
184    fn extension(&self, typeid: TypeId) -> crate::Result<&dyn Any> {
185        let _ = typeid;
186        Err(Error::UnknownExtension)
187    }
188    fn topology_hash(&self) -> Option<Hash> {
189        None
190    }
191    fn into_topovec(self: Arc<Self>) -> Option<TopoVec> {
192        None
193    }
194}
195
196pub trait FetchBytes: AsAny {
197    fn fetch_bytes(&'_ self) -> FailFuture<'_, ByteNode>;
198    fn fetch_data(&'_ self) -> FailFuture<'_, Vec<u8>>;
199    fn fetch_bytes_local(&self) -> Result<Option<ByteNode>> {
200        Ok(None)
201    }
202    fn fetch_data_local(&self) -> Option<Vec<u8>> {
203        None
204    }
205    fn as_inner(&self) -> Option<&dyn Any> {
206        None
207    }
208    fn as_resolve(&self) -> Option<&Arc<dyn Resolve>> {
209        None
210    }
211    fn try_unwrap_resolve(self: Arc<Self>) -> Option<Arc<dyn Resolve>> {
212        None
213    }
214}
215
216pub trait Fetch: Send + Sync + FetchBytes {
217    type T;
218    fn fetch_full(&'_ self) -> FailFuture<'_, Node<Self::T>>;
219    fn fetch(&'_ self) -> FailFuture<'_, Self::T>;
220    fn try_fetch_local(&self) -> Result<Option<Node<Self::T>>> {
221        Ok(None)
222    }
223    fn fetch_local(&self) -> Option<Self::T> {
224        None
225    }
226    fn get(&self) -> Option<&Self::T> {
227        None
228    }
229    fn get_mut(&mut self) -> Option<&mut Self::T> {
230        None
231    }
232    fn get_mut_finalize(&mut self) {}
233    fn try_unwrap(self: Arc<Self>) -> Option<Self::T> {
234        None
235    }
236    fn into_dyn_fetch<'a>(self) -> Arc<dyn 'a + Fetch<T = Self::T>>
237    where
238        Self: 'a + Sized,
239    {
240        Arc::new(self)
241    }
242}
243
244#[derive(ToOutput, InlineOutput, ListHashes, Topological, Parse, ParseInline)]
245pub struct ObjectMarker<T: ?Sized> {
246    object: PhantomData<fn() -> T>,
247}
248
249impl<T: ?Sized> Clone for ObjectMarker<T> {
250    fn clone(&self) -> Self {
251        *self
252    }
253}
254
255impl<T: ?Sized> Copy for ObjectMarker<T> {}
256
257impl<T: ?Sized> Default for ObjectMarker<T> {
258    fn default() -> Self {
259        Self::new()
260    }
261}
262
263impl<T: ?Sized> ObjectMarker<T> {
264    pub const fn new() -> Self {
265        Self {
266            object: PhantomData,
267        }
268    }
269}
270
271impl<T: ?Sized + Tagged> Tagged for ObjectMarker<T> {}
272
273pub trait PointVisitor {
274    fn visit<T: Traversible>(&mut self, point: &(impl 'static + SingularFetch<T = T> + Clone));
275}
276
277pub struct ReflessInput<'d> {
278    data: Option<&'d [u8]>,
279}
280
281pub struct Input<'d, Extra: Clone = ()> {
282    refless: ReflessInput<'d>,
283    resolve: &'d Arc<dyn Resolve>,
284    index: &'d Cell<usize>,
285    extra: Cow<'d, Extra>,
286}
287
288impl<'a, Extra: Clone> Deref for Input<'a, Extra> {
289    type Target = ReflessInput<'a>;
290
291    fn deref(&self) -> &Self::Target {
292        &self.refless
293    }
294}
295
296impl<Extra: Clone> DerefMut for Input<'_, Extra> {
297    fn deref_mut(&mut self) -> &mut Self::Target {
298        &mut self.refless
299    }
300}
301
302impl<'a> ReflessInput<'a> {
303    fn data(&self) -> crate::Result<&'a [u8]> {
304        self.data.ok_or(Error::EndOfInput)
305    }
306
307    fn make_error<T>(&mut self, e: crate::Error) -> crate::Result<T> {
308        self.data = None;
309        Err(e)
310    }
311
312    fn end_of_input<T>(&mut self) -> crate::Result<T> {
313        self.make_error(Error::EndOfInput)
314    }
315}
316
317impl<'d> ParseInput for ReflessInput<'d> {
318    type Data = &'d [u8];
319
320    fn parse_chunk<'a, const N: usize>(&mut self) -> crate::Result<&'a [u8; N]>
321    where
322        Self: 'a,
323    {
324        match self.data()?.split_first_chunk() {
325            Some((chunk, data)) => {
326                self.data = Some(data);
327                Ok(chunk)
328            }
329            None => self.end_of_input(),
330        }
331    }
332
333    fn parse_n(&mut self, n: usize) -> crate::Result<Self::Data> {
334        match self.data()?.split_at_checked(n) {
335            Some((chunk, data)) => {
336                self.data = Some(data);
337                Ok(chunk)
338            }
339            None => self.end_of_input(),
340        }
341    }
342
343    fn parse_until_zero(&mut self) -> crate::Result<Self::Data> {
344        let data = self.data()?;
345        match data.iter().enumerate().find(|(_, x)| **x == 0) {
346            Some((at, _)) => {
347                let (chunk, data) = data.split_at(at);
348                self.data = Some(&data[1..]);
349                Ok(chunk)
350            }
351            None => self.end_of_input(),
352        }
353    }
354
355    fn reparse<T: Parse<Self>>(&mut self, data: Self::Data) -> crate::Result<T> {
356        let input = Self { data: Some(data) };
357        T::parse(input)
358    }
359
360    fn parse_all(self) -> crate::Result<Self::Data> {
361        self.data()
362    }
363
364    fn empty(self) -> crate::Result<()> {
365        if self.data()?.is_empty() {
366            Ok(())
367        } else {
368            Err(Error::ExtraInputLeft)
369        }
370    }
371
372    fn non_empty(self) -> crate::Result<Option<Self>> {
373        Ok(if self.data()?.is_empty() {
374            None
375        } else {
376            Some(self)
377        })
378    }
379}
380
381impl<'d, Extra: Clone> ParseInput for Input<'d, Extra> {
382    type Data = &'d [u8];
383
384    fn parse_chunk<'a, const N: usize>(&mut self) -> crate::Result<&'a [u8; N]>
385    where
386        Self: 'a,
387    {
388        (**self).parse_chunk()
389    }
390
391    fn parse_n(&mut self, n: usize) -> crate::Result<Self::Data> {
392        (**self).parse_n(n)
393    }
394
395    fn parse_until_zero(&mut self) -> crate::Result<Self::Data> {
396        (**self).parse_until_zero()
397    }
398
399    fn reparse<T: Parse<Self>>(&mut self, data: Self::Data) -> crate::Result<T> {
400        let input = Self {
401            refless: ReflessInput { data: Some(data) },
402            resolve: self.resolve,
403            index: self.index,
404            extra: self.extra.clone(),
405        };
406        T::parse(input)
407    }
408
409    fn parse_all(self) -> crate::Result<Self::Data> {
410        self.refless.parse_all()
411    }
412
413    fn empty(self) -> crate::Result<()> {
414        self.refless.empty()
415    }
416
417    fn non_empty(mut self) -> crate::Result<Option<Self>> {
418        self.refless = match self.refless.non_empty()? {
419            Some(refless) => refless,
420            None => return Ok(None),
421        };
422        Ok(Some(self))
423    }
424}
425
426impl<'d, Extra: 'static + Clone> PointInput for Input<'d, Extra> {
427    type Extra = Extra;
428    type WithExtra<E: 'static + Clone> = Input<'d, E>;
429
430    fn next_index(&mut self) -> usize {
431        let index = self.index.get();
432        self.index.set(index + 1);
433        index
434    }
435
436    fn resolve_arc_ref(&self) -> &Arc<dyn Resolve> {
437        self.resolve
438    }
439
440    fn extra(&self) -> &Self::Extra {
441        &self.extra
442    }
443
444    fn map_extra<E: 'static + Clone>(
445        self,
446        f: impl FnOnce(&Self::Extra) -> &E,
447    ) -> Self::WithExtra<E> {
448        let Self {
449            refless,
450            resolve,
451            index,
452            extra,
453        } = self;
454        Input {
455            refless,
456            resolve,
457            index,
458            extra: match extra {
459                Cow::Borrowed(extra) => Cow::Borrowed(f(extra)),
460                Cow::Owned(extra) => Cow::Owned(f(&extra).clone()),
461            },
462        }
463    }
464
465    fn replace_extra<E: 'static + Clone>(self, e: E) -> (Extra, Self::WithExtra<E>) {
466        let Self {
467            refless,
468            resolve,
469            index,
470            extra,
471        } = self;
472        (
473            extra.into_owned(),
474            Input {
475                refless,
476                resolve,
477                index,
478                extra: Cow::Owned(e),
479            },
480        )
481    }
482
483    fn with_extra<E: 'static + Clone>(self, extra: E) -> Self::WithExtra<E> {
484        let Self {
485            refless,
486            resolve,
487            index,
488            ..
489        } = self;
490        Input {
491            refless,
492            resolve,
493            index,
494            extra: Cow::Owned(extra),
495        }
496    }
497
498    fn parse_inline_extra<E: 'static + Clone, T: ParseInline<Self::WithExtra<E>>>(
499        &mut self,
500        extra: E,
501    ) -> crate::Result<T> {
502        let Self {
503            refless,
504            resolve,
505            index,
506            ..
507        } = self;
508        let data = refless.data.take();
509        let mut input = Input {
510            refless: ReflessInput { data },
511            resolve,
512            index,
513            extra: Cow::Owned(extra),
514        };
515        let value = input.parse_inline()?;
516        refless.data = input.refless.data.take();
517        Ok(value)
518    }
519}
520
521/// Values of this type can be uniquely represented as a `Vec<u8>`.
522pub trait ToOutput {
523    fn to_output(&self, output: &mut dyn Output);
524
525    fn data_hash(&self) -> Hash {
526        let mut output = HashOutput::default();
527        self.to_output(&mut output);
528        output.hash()
529    }
530
531    fn mangle_hash(&self) -> Hash {
532        Mangled(self).data_hash()
533    }
534
535    fn output<T: Output + Default>(&self) -> T {
536        let mut output = T::default();
537        self.to_output(&mut output);
538        output
539    }
540
541    fn vec(&self) -> Vec<u8> {
542        self.output()
543    }
544}
545
546/// Marker trait indicating that [`ToOutput`] result cannot be extended (no value, when represented
547/// as a `Vec<u8>`, may be a prefix of another value).
548pub trait InlineOutput: ToOutput {
549    fn slice_to_output(slice: &[Self], output: &mut dyn Output)
550    where
551        Self: Sized,
552    {
553        slice.iter_to_output(output);
554    }
555}
556
557pub trait ListHashes {
558    fn list_hashes(&self, f: &mut impl FnMut(Hash)) {
559        let _ = f;
560    }
561
562    fn topology_hash(&self) -> Hash {
563        let mut hasher = Sha256::new();
564        self.list_hashes(&mut |hash| hasher.update(hash));
565        Hash::from_sha256(hasher.finalize().into())
566    }
567
568    fn point_count(&self) -> usize {
569        let mut count = 0;
570        self.list_hashes(&mut |_| count += 1);
571        count
572    }
573}
574
575pub trait Topological: ListHashes {
576    fn traverse(&self, visitor: &mut impl PointVisitor) {
577        let _ = visitor;
578    }
579
580    fn topology(&self) -> TopoVec {
581        let mut topology = TopoVec::with_capacity(self.point_count());
582        self.traverse(&mut topology);
583        topology
584    }
585}
586
587pub trait Tagged {
588    const TAGS: Tags = Tags(&[], &[]);
589    const HASH: Hash = Self::TAGS.hash();
590}
591
592pub trait ParseSlice: for<'a> Parse<Input<'a>> {
593    fn parse_slice(data: &[u8], resolve: &Arc<dyn Resolve>) -> crate::Result<Self> {
594        Self::parse_slice_extra(data, resolve, &())
595    }
596
597    fn reparse(&self) -> crate::Result<Self>
598    where
599        Self: Traversible,
600    {
601        self.reparse_extra(&())
602    }
603}
604
605impl<T: for<'a> Parse<Input<'a>>> ParseSlice for T {}
606
607pub trait ParseSliceExtra<Extra: Clone>: for<'a> Parse<Input<'a, Extra>> {
608    fn parse_slice_extra(
609        data: &[u8],
610        resolve: &Arc<dyn Resolve>,
611        extra: &Extra,
612    ) -> crate::Result<Self> {
613        let input = Input {
614            refless: ReflessInput { data: Some(data) },
615            resolve,
616            index: &Cell::new(0),
617            extra: Cow::Borrowed(extra),
618        };
619        let object = Self::parse(input)?;
620        Ok(object)
621    }
622
623    fn reparse_extra(&self, extra: &Extra) -> crate::Result<Self>
624    where
625        Self: Traversible,
626    {
627        Self::parse_slice_extra(&self.vec(), &self.to_resolve(), extra)
628    }
629}
630
631impl<T: for<'a> Parse<Input<'a, Extra>>, Extra: Clone> ParseSliceExtra<Extra> for T {}
632
633#[derive(ToOutput)]
634pub struct DiffHashes {
635    pub tags: Hash,
636    pub topology: Hash,
637    pub mangle: Hash,
638}
639
640#[derive(ToOutput)]
641pub struct ObjectHashes {
642    pub diff: Hash,
643    pub data: Hash,
644}
645
646pub trait FullHash: ToOutput + ListHashes + Tagged {
647    fn diff_hashes(&self) -> DiffHashes {
648        DiffHashes {
649            tags: Self::HASH,
650            topology: self.topology_hash(),
651            mangle: self.mangle_hash(),
652        }
653    }
654
655    fn hashes(&self) -> ObjectHashes {
656        ObjectHashes {
657            diff: self.diff_hashes().data_hash(),
658            data: self.data_hash(),
659        }
660    }
661
662    fn full_hash(&self) -> Hash {
663        self.hashes().data_hash()
664    }
665}
666
667impl<T: ?Sized + ToOutput + ListHashes + Tagged> FullHash for T {}
668
669pub trait DefaultHash: FullHash + Default {
670    fn default_hash() -> Hash {
671        Self::default().full_hash()
672    }
673}
674
675pub trait Traversible: 'static + Sized + Send + Sync + FullHash + Topological {
676    fn to_resolve(&self) -> Arc<dyn Resolve> {
677        let topology = self.topology();
678        let topology_hash = topology.data_hash();
679        for singular in &topology {
680            if let Some(resolve) = singular.as_resolve()
681                && resolve.topology_hash() == Some(topology_hash)
682            {
683                return resolve.clone();
684            }
685        }
686        Arc::new(ByTopology {
687            topology,
688            topology_hash,
689        })
690    }
691}
692
693impl<T: 'static + Send + Sync + FullHash + Topological> Traversible for T {}
694
695pub trait Object<Extra = ()>: Traversible + for<'a> Parse<Input<'a, Extra>> {}
696
697impl<T: Traversible + for<'a> Parse<Input<'a, Extra>>, Extra> Object<Extra> for T {}
698
699pub struct Tags(pub &'static [&'static str], pub &'static [&'static Self]);
700
701const fn bytes_compare(l: &[u8], r: &[u8]) -> std::cmp::Ordering {
702    let mut i = 0;
703    while i < l.len() && i < r.len() {
704        if l[i] > r[i] {
705            return std::cmp::Ordering::Greater;
706        } else if l[i] < r[i] {
707            return std::cmp::Ordering::Less;
708        } else {
709            i += 1;
710        }
711    }
712    if l.len() > r.len() {
713        std::cmp::Ordering::Greater
714    } else if l.len() < r.len() {
715        std::cmp::Ordering::Less
716    } else {
717        std::cmp::Ordering::Equal
718    }
719}
720
721const fn str_compare(l: &str, r: &str) -> std::cmp::Ordering {
722    bytes_compare(l.as_bytes(), r.as_bytes())
723}
724
725impl Tags {
726    const fn min_out(&self, strict_min: Option<&str>, min: &mut Option<&'static str>) {
727        {
728            let mut i = 0;
729            while i < self.0.len() {
730                let candidate = self.0[i];
731                i += 1;
732                if let Some(strict_min) = strict_min
733                    && str_compare(candidate, strict_min).is_le()
734                {
735                    continue;
736                }
737                if let Some(min) = min
738                    && str_compare(candidate, min).is_ge()
739                {
740                    continue;
741                }
742                *min = Some(candidate);
743            }
744        }
745        {
746            let mut i = 0;
747            while i < self.1.len() {
748                self.1[i].min_out(strict_min, min);
749                i += 1;
750            }
751        }
752        if let Some(l) = min
753            && let Some(r) = strict_min
754        {
755            assert!(str_compare(l, r).is_gt());
756        }
757    }
758
759    const fn min(&self, strict_min: Option<&str>) -> Option<&'static str> {
760        let mut min = None;
761        self.min_out(strict_min, &mut min);
762        min
763    }
764
765    const fn const_hash(&self, mut hasher: sha2_const::Sha256) -> sha2_const::Sha256 {
766        let mut last = None;
767        let mut i = 0;
768        while let Some(next) = self.min(last) {
769            i += 1;
770            if i > 1000 {
771                panic!("{}", next);
772            }
773            hasher = hasher.update(next.as_bytes());
774            last = Some(next);
775        }
776        hasher
777    }
778
779    const fn hash(&self) -> Hash {
780        Hash::from_sha256(self.const_hash(sha2_const::Sha256::new()).finalize())
781    }
782}
783
784#[test]
785fn min_out_respects_bounds() {
786    let mut min = None;
787    Tags(&["c", "b", "a"], &[]).min_out(Some("a"), &mut min);
788    assert_eq!(min, Some("b"));
789}
790
791#[test]
792fn const_hash() {
793    assert_ne!(Tags(&["a", "b"], &[]).hash(), Tags(&["a"], &[]).hash());
794    assert_eq!(
795        Tags(&["a", "b"], &[]).hash(),
796        Tags(&["a"], &[&Tags(&["b"], &[])]).hash(),
797    );
798    assert_eq!(Tags(&["a", "b"], &[]).hash(), Tags(&["b", "a"], &[]).hash());
799    assert_eq!(Tags(&["a", "a"], &[]).hash(), Tags(&["a"], &[]).hash());
800}
801
802pub trait Inline<Extra = ()>:
803    Object<Extra> + InlineOutput + for<'a> ParseInline<Input<'a, Extra>>
804{
805}
806
807impl<T: Object<Extra> + InlineOutput + for<'a> ParseInline<Input<'a, Extra>>, Extra> Inline<Extra>
808    for T
809{
810}
811
812pub trait Topology: Send + Sync {
813    fn len(&self) -> usize;
814    fn get(&self, index: usize) -> Option<&Arc<dyn Singular>>;
815
816    fn is_empty(&self) -> bool {
817        self.len() == 0
818    }
819}
820
821pub trait Singular: Send + Sync + FetchBytes {
822    fn hash(&self) -> Hash;
823}
824
825pub trait SingularFetch: Singular + Fetch {}
826
827impl<T: ?Sized + Singular + Fetch> SingularFetch for T {}
828
829impl ToOutput for dyn Singular {
830    fn to_output(&self, output: &mut dyn Output) {
831        self.hash().to_output(output);
832    }
833}
834
835impl InlineOutput for dyn Singular {}
836
837pub type TopoVec = Vec<Arc<dyn Singular>>;
838
839impl PointVisitor for TopoVec {
840    fn visit<T: Traversible>(&mut self, point: &(impl 'static + SingularFetch<T = T> + Clone)) {
841        self.push(Arc::new(point.clone()));
842    }
843}
844
845impl Topology for TopoVec {
846    fn len(&self) -> usize {
847        self.len()
848    }
849
850    fn get(&self, index: usize) -> Option<&Arc<dyn Singular>> {
851        (**self).get(index)
852    }
853}
854
855pub trait ParseSliceRefless: for<'a> Parse<ReflessInput<'a>> {
856    fn parse_slice_refless(data: &[u8]) -> crate::Result<Self> {
857        let input = ReflessInput { data: Some(data) };
858        let object = Self::parse(input)?;
859        Ok(object)
860    }
861}
862
863impl<T: for<'a> Parse<ReflessInput<'a>>> ParseSliceRefless for T {}
864
865pub trait ReflessObject:
866    'static + Sized + Send + Sync + ToOutput + Tagged + for<'a> Parse<ReflessInput<'a>>
867{
868}
869
870impl<T: 'static + Sized + Send + Sync + ToOutput + Tagged + for<'a> Parse<ReflessInput<'a>>>
871    ReflessObject for T
872{
873}
874
875pub trait ReflessInline:
876    ReflessObject + InlineOutput + for<'a> ParseInline<ReflessInput<'a>>
877{
878}
879
880impl<T: ReflessObject + InlineOutput + for<'a> ParseInline<ReflessInput<'a>>> ReflessInline for T {}
881
882pub trait Output {
883    fn write(&mut self, data: &[u8]);
884    fn is_mangling(&self) -> bool {
885        false
886    }
887    fn is_real(&self) -> bool {
888        !self.is_mangling()
889    }
890}
891
892impl Output for Vec<u8> {
893    fn write(&mut self, data: &[u8]) {
894        self.extend_from_slice(data);
895    }
896}
897
898struct MangleOutput<'a>(&'a mut dyn Output);
899
900impl<'a> MangleOutput<'a> {
901    fn new(output: &'a mut dyn Output) -> Self {
902        assert!(output.is_real());
903        assert!(!output.is_mangling());
904        Self(output)
905    }
906}
907
908impl Output for MangleOutput<'_> {
909    fn write(&mut self, data: &[u8]) {
910        self.0.write(data);
911    }
912
913    fn is_mangling(&self) -> bool {
914        true
915    }
916}
917
918pub struct Mangled<T: ?Sized>(T);
919
920impl<T: ?Sized + ToOutput> ToOutput for Mangled<T> {
921    fn to_output(&self, output: &mut dyn Output) {
922        self.0.to_output(&mut MangleOutput::new(output));
923    }
924}
925
926#[derive(Default)]
927struct HashOutput {
928    hasher: Sha256,
929    at: usize,
930}
931
932impl Output for HashOutput {
933    fn write(&mut self, data: &[u8]) {
934        self.hasher.update(data);
935        self.at += data.len();
936    }
937}
938
939impl HashOutput {
940    fn hash(self) -> Hash {
941        Hash::from_sha256(self.hasher.finalize().into())
942    }
943}
944
945struct ByTopology {
946    topology: TopoVec,
947    topology_hash: Hash,
948}
949
950impl Drop for ByTopology {
951    fn drop(&mut self) {
952        while let Some(singular) = self.topology.pop() {
953            if let Some(resolve) = singular.try_unwrap_resolve()
954                && let Some(topology) = &mut resolve.into_topovec()
955            {
956                self.topology.append(topology);
957            }
958        }
959    }
960}
961
962impl ByTopology {
963    fn try_resolve(&'_ self, address: Address) -> Result<FailFuture<'_, ByteNode>> {
964        let point = self
965            .topology
966            .get(address.index)
967            .ok_or(Error::AddressOutOfBounds)?;
968        if point.hash() != address.hash {
969            Err(Error::ResolutionMismatch)
970        } else {
971            Ok(point.fetch_bytes())
972        }
973    }
974
975    fn try_resolve_data(&'_ self, address: Address) -> Result<FailFuture<'_, Vec<u8>>> {
976        let point = self
977            .topology
978            .get(address.index)
979            .ok_or(Error::AddressOutOfBounds)?;
980        if point.hash() != address.hash {
981            Err(Error::ResolutionMismatch)
982        } else {
983            Ok(point.fetch_data())
984        }
985    }
986}
987
988impl Resolve for ByTopology {
989    fn resolve(&'_ self, address: Address, _: &Arc<dyn Resolve>) -> FailFuture<'_, ByteNode> {
990        self.try_resolve(address)
991            .map_err(Err)
992            .map_err(ready)
993            .map_err(Box::pin)
994            .unwrap_or_else(|x| x)
995    }
996
997    fn resolve_data(&'_ self, address: Address) -> FailFuture<'_, Vec<u8>> {
998        self.try_resolve_data(address)
999            .map_err(Err)
1000            .map_err(ready)
1001            .map_err(Box::pin)
1002            .unwrap_or_else(|x| x)
1003    }
1004
1005    fn try_resolve_local(
1006        &self,
1007        address: Address,
1008        _: &Arc<dyn Resolve>,
1009    ) -> Result<Option<ByteNode>> {
1010        let point = self
1011            .topology
1012            .get(address.index)
1013            .ok_or(Error::AddressOutOfBounds)?;
1014        if point.hash() != address.hash {
1015            Err(Error::ResolutionMismatch)
1016        } else {
1017            point.fetch_bytes_local()
1018        }
1019    }
1020
1021    fn topology_hash(&self) -> Option<Hash> {
1022        Some(self.topology_hash)
1023    }
1024
1025    fn into_topovec(self: Arc<Self>) -> Option<TopoVec> {
1026        Arc::try_unwrap(self)
1027            .ok()
1028            .as_mut()
1029            .map(|Self { topology, .. }| std::mem::take(topology))
1030    }
1031}
1032
1033pub trait Size {
1034    const SIZE: usize = <Self::Size as Unsigned>::USIZE;
1035    type Size: Unsigned;
1036}
1037
1038pub trait SizeExt: Size<Size: ArrayLength> + ToOutput {
1039    fn to_array(&self) -> GenericArray<u8, Self::Size> {
1040        let mut array = GenericArray::default();
1041        let mut output = ArrayOutput {
1042            data: &mut array,
1043            offset: 0,
1044        };
1045        self.to_output(&mut output);
1046        output.finalize();
1047        array
1048    }
1049}
1050
1051impl<T: Size<Size: ArrayLength> + ToOutput> SizeExt for T {}
1052
1053struct ArrayOutput<'a> {
1054    data: &'a mut [u8],
1055    offset: usize,
1056}
1057
1058impl ArrayOutput<'_> {
1059    fn finalize(self) {
1060        assert_eq!(self.offset, self.data.len());
1061    }
1062}
1063
1064impl Output for ArrayOutput<'_> {
1065    fn write(&mut self, data: &[u8]) {
1066        self.data[self.offset..][..data.len()].copy_from_slice(data);
1067        self.offset += data.len();
1068    }
1069}
1070
1071pub trait RainbowIterator: Sized + IntoIterator {
1072    fn iter_to_output(self, output: &mut dyn Output)
1073    where
1074        Self::Item: InlineOutput,
1075    {
1076        self.into_iter().for_each(|item| item.to_output(output));
1077    }
1078
1079    fn iter_list_hashes(self, f: &mut impl FnMut(Hash))
1080    where
1081        Self::Item: ListHashes,
1082    {
1083        self.into_iter().for_each(|item| item.list_hashes(f));
1084    }
1085
1086    fn iter_traverse(self, visitor: &mut impl PointVisitor)
1087    where
1088        Self::Item: Topological,
1089    {
1090        self.into_iter().for_each(|item| item.traverse(visitor));
1091    }
1092}
1093
1094pub trait ParseInput: Sized {
1095    type Data: AsRef<[u8]> + Deref<Target = [u8]> + Into<Vec<u8>> + Copy;
1096    fn parse_chunk<'a, const N: usize>(&mut self) -> crate::Result<&'a [u8; N]>
1097    where
1098        Self: 'a;
1099    fn parse_n(&mut self, n: usize) -> crate::Result<Self::Data>;
1100    fn parse_until_zero(&mut self) -> crate::Result<Self::Data>;
1101    fn parse_n_compare(&mut self, n: usize, c: &[u8]) -> crate::Result<Option<Self::Data>> {
1102        let data = self.parse_n(n)?;
1103        if *data == *c {
1104            Ok(None)
1105        } else {
1106            Ok(Some(data))
1107        }
1108    }
1109    fn reparse<T: Parse<Self>>(&mut self, data: Self::Data) -> crate::Result<T>;
1110    fn parse_ahead<T: Parse<Self>>(&mut self, n: usize) -> crate::Result<T> {
1111        let data = self.parse_n(n)?;
1112        self.reparse(data)
1113    }
1114    fn parse_zero_terminated<T: Parse<Self>>(&mut self) -> crate::Result<T> {
1115        let data = self.parse_until_zero()?;
1116        self.reparse(data)
1117    }
1118    fn parse_compare<T: Parse<Self>>(&mut self, n: usize, c: &[u8]) -> Result<Option<T>> {
1119        self.parse_n_compare(n, c)?
1120            .map(|data| self.reparse(data))
1121            .transpose()
1122    }
1123    fn parse_all(self) -> crate::Result<Self::Data>;
1124    fn empty(self) -> crate::Result<()>;
1125    fn non_empty(self) -> crate::Result<Option<Self>>;
1126
1127    fn consume(self, f: impl FnMut(&mut Self) -> crate::Result<()>) -> crate::Result<()> {
1128        self.collect(f)
1129    }
1130
1131    fn parse_collect<T: ParseInline<Self>, B: FromIterator<T>>(self) -> crate::Result<B> {
1132        self.collect(|input| input.parse_inline())
1133    }
1134
1135    fn collect<T, B: FromIterator<T>>(
1136        self,
1137        f: impl FnMut(&mut Self) -> crate::Result<T>,
1138    ) -> crate::Result<B> {
1139        self.iter(f).collect()
1140    }
1141
1142    fn iter<T>(
1143        self,
1144        mut f: impl FnMut(&mut Self) -> crate::Result<T>,
1145    ) -> impl Iterator<Item = crate::Result<T>> {
1146        let mut state = Some(self);
1147        std::iter::from_fn(move || {
1148            let mut input = match state.take()?.non_empty() {
1149                Ok(input) => input?,
1150                Err(e) => return Some(Err(e)),
1151            };
1152            let item = f(&mut input);
1153            state = Some(input);
1154            Some(item)
1155        })
1156    }
1157
1158    fn parse_inline<T: ParseInline<Self>>(&mut self) -> crate::Result<T> {
1159        T::parse_inline(self)
1160    }
1161
1162    fn parse<T: Parse<Self>>(self) -> crate::Result<T> {
1163        T::parse(self)
1164    }
1165
1166    fn parse_vec<T: ParseInline<Self>>(self) -> crate::Result<Vec<T>> {
1167        T::parse_vec(self)
1168    }
1169
1170    fn parse_vec_n<T: ParseInline<Self>>(&mut self, n: usize) -> crate::Result<Vec<T>> {
1171        T::parse_vec_n(self, n)
1172    }
1173
1174    fn parse_array<T: ParseInline<Self>, const N: usize>(&mut self) -> crate::Result<[T; N]> {
1175        T::parse_array(self)
1176    }
1177
1178    fn parse_generic_array<T: ParseInline<Self>, N: ArrayLength>(
1179        &mut self,
1180    ) -> crate::Result<GenericArray<T, N>> {
1181        T::parse_generic_array(self)
1182    }
1183}
1184
1185pub trait PointInput: ParseInput {
1186    type Extra: 'static + Clone;
1187    type WithExtra<E: 'static + Clone>: PointInput<Extra = E, WithExtra<Self::Extra> = Self>;
1188    fn next_index(&mut self) -> usize;
1189    fn resolve_arc_ref(&self) -> &Arc<dyn Resolve>;
1190    fn resolve(&self) -> Arc<dyn Resolve> {
1191        self.resolve_arc_ref().clone()
1192    }
1193    fn resolve_ref(&self) -> &dyn Resolve {
1194        self.resolve_arc_ref().as_ref()
1195    }
1196    fn extension<T: Any>(&self) -> crate::Result<&T> {
1197        self.resolve_ref()
1198            .extension(TypeId::of::<T>())?
1199            .downcast_ref()
1200            .ok_or(Error::ExtensionType)
1201    }
1202    /// Get [`Self::Extra`].
1203    fn extra(&self) -> &Self::Extra;
1204    /// Project the `Extra`. Under some circumstances, prevents an extra [`Clone::clone`].
1205    fn map_extra<E: 'static + Clone>(
1206        self,
1207        f: impl FnOnce(&Self::Extra) -> &E,
1208    ) -> Self::WithExtra<E>;
1209    /// Return the old [`Self::Extra`], give a new [`PointInput`] with `E` as `Extra`.
1210    fn replace_extra<E: 'static + Clone>(self, extra: E) -> (Self::Extra, Self::WithExtra<E>);
1211    /// [`Self::replace_extra`] but discarding [`Self::Extra`].
1212    fn with_extra<E: 'static + Clone>(self, extra: E) -> Self::WithExtra<E> {
1213        self.replace_extra(extra).1
1214    }
1215    /// [`ParseInput::parse`] with a different `Extra`.
1216    fn parse_extra<E: 'static + Clone, T: Parse<Self::WithExtra<E>>>(
1217        self,
1218        extra: E,
1219    ) -> crate::Result<T> {
1220        self.with_extra(extra).parse()
1221    }
1222    /// [`ParseInput::parse_inline`] with a different `Extra`.
1223    fn parse_inline_extra<E: 'static + Clone, T: ParseInline<Self::WithExtra<E>>>(
1224        &mut self,
1225        extra: E,
1226    ) -> crate::Result<T>;
1227}
1228
1229impl<T: Sized + IntoIterator> RainbowIterator for T {}
1230
1231/// This can be parsed by consuming the whole rest of the input.
1232///
1233/// Nothing can be parsed after this. It's implementation's responsibility to ensure there are no
1234/// leftover bytes.
1235pub trait Parse<I: ParseInput>: Sized {
1236    /// Parse consuming the whole stream.
1237    fn parse(input: I) -> crate::Result<Self>;
1238}
1239
1240/// This can be parsed from an input, after which we can correctly parse something else.
1241///
1242/// When parsed as the last object, makes sure there are no bytes left in the input (fails if there
1243/// are).
1244pub trait ParseInline<I: ParseInput>: Parse<I> {
1245    /// Parse without consuming the whole stream. Errors on unexpected EOF.
1246    fn parse_inline(input: &mut I) -> crate::Result<Self>;
1247    /// For implementing [`Parse::parse`].
1248    fn parse_as_inline(mut input: I) -> crate::Result<Self> {
1249        let object = Self::parse_inline(&mut input)?;
1250        input.empty()?;
1251        Ok(object)
1252    }
1253    /// Parse a `Vec` of `Self`. Customisable for optimisations.
1254    fn parse_vec(input: I) -> crate::Result<Vec<Self>> {
1255        input.parse_collect()
1256    }
1257    /// Parse a `Vec` of `Self` of length `n`. Customisable for optimisations.
1258    fn parse_vec_n(input: &mut I, n: usize) -> crate::Result<Vec<Self>> {
1259        (0..n).map(|_| input.parse_inline()).collect()
1260    }
1261    /// Parse an array of `Self`. Customisable for optimisations.
1262    fn parse_array<const N: usize>(input: &mut I) -> crate::Result<[Self; N]> {
1263        let mut scratch = std::array::from_fn(|_| None);
1264        for item in scratch.iter_mut() {
1265            *item = Some(input.parse_inline()?);
1266        }
1267        Ok(scratch.map(Option::unwrap))
1268    }
1269    /// Parse a [`GenericArray`] of `Self`. Customisable for optimisations.
1270    fn parse_generic_array<N: ArrayLength>(input: &mut I) -> crate::Result<GenericArray<Self, N>> {
1271        let mut scratch = GenericArray::default();
1272        for item in scratch.iter_mut() {
1273            *item = Some(input.parse_inline()?);
1274        }
1275        Ok(scratch.map(Option::unwrap))
1276    }
1277}
1278
1279/// Implemented if both types have the exact same layout.
1280/// This implies having the same [`MaybeHasNiche::MnArray`].
1281///
1282/// This is represented as two-way conversion for two reasons:
1283/// - to highlight that the conversion is actual equivalence
1284/// - to increase flexibility (mostly to go around the orphan rule)
1285pub trait Equivalent<T>: Sized {
1286    /// Inverse of [`Equivalent::from_equivalent`].
1287    fn into_equivalent(self) -> T;
1288    /// Inverse of [`Equivalent::into_equivalent`].
1289    fn from_equivalent(object: T) -> Self;
1290}
1291
1292/// This `Extra` can be used to parse `T` via [`ParseSliceExtra::parse_slice_extra`].
1293pub trait ExtraFor<T> {
1294    /// [`ParseSliceExtra::parse_slice_extra`].
1295    fn parse(&self, data: &[u8], resolve: &Arc<dyn Resolve>) -> Result<T>;
1296
1297    /// [`Self::parse`], then check that [`FullHash::full_hash`] matches.
1298    fn parse_checked(&self, hash: Hash, data: &[u8], resolve: &Arc<dyn Resolve>) -> Result<T>
1299    where
1300        T: FullHash,
1301    {
1302        let object = self.parse(data, resolve)?;
1303        if object.full_hash() != hash {
1304            Err(Error::FullHashMismatch)
1305        } else {
1306            Ok(object)
1307        }
1308    }
1309}
1310
1311impl<T: for<'a> Parse<Input<'a, Extra>>, Extra: Clone> ExtraFor<T> for Extra {
1312    fn parse(&self, data: &[u8], resolve: &Arc<dyn Resolve>) -> Result<T> {
1313        T::parse_slice_extra(data, resolve, self)
1314    }
1315}
1316
1317#[doc(hidden)]
1318pub trait BoundPair: Sized {
1319    type T;
1320    type E;
1321}
1322
1323impl<T, E> BoundPair for (T, E) {
1324    type T = T;
1325    type E = E;
1326}
1327
1328/// Parses `Extra`, then provides it to `T`'s parser.
1329#[derive(Debug, ToOutput, InlineOutput, Tagged, ListHashes, Topological, Clone, Copy)]
1330pub struct InlineExtra<T, Extra = ()>(pub Extra, pub T);
1331
1332impl<
1333    E: 'static + Send + Sync + Clone + ParseInline<I>,
1334    X: 'static + Send + Sync + Clone,
1335    T: Parse<J>,
1336    I: PointInput<Extra = X, WithExtra<(E, X)> = J>,
1337    J: ParseInput,
1338> Parse<I> for InlineExtra<T, E>
1339{
1340    fn parse(mut input: I) -> crate::Result<Self> {
1341        let e = input.parse_inline::<E>()?;
1342        let x = input.extra().clone();
1343        let t = input.parse_extra((e.clone(), x))?;
1344        Ok(Self(e, t))
1345    }
1346}
1347
1348impl<
1349    E: 'static + Send + Sync + Clone + ParseInline<I>,
1350    X: 'static + Send + Sync + Clone,
1351    T: ParseInline<J>,
1352    I: PointInput<Extra = X, WithExtra<(E, X)> = J>,
1353    J: ParseInput,
1354> ParseInline<I> for InlineExtra<T, E>
1355{
1356    fn parse_inline(input: &mut I) -> crate::Result<Self> {
1357        let e = input.parse_inline::<E>()?;
1358        let x = input.extra().clone();
1359        let t = input.parse_inline_extra((e.clone(), x))?;
1360        Ok(Self(e, t))
1361    }
1362}
1363
1364#[test]
1365fn options() {
1366    type T0 = ();
1367    type T1 = Option<T0>;
1368    type T2 = Option<T1>;
1369    type T3 = Option<T2>;
1370    type T4 = Option<T3>;
1371    type T5 = Option<T4>;
1372    assert_eq!(T0::SIZE, 0);
1373    assert_eq!(T1::SIZE, 1);
1374    assert_eq!(T2::SIZE, 1);
1375    assert_eq!(T3::SIZE, 1);
1376    assert_eq!(T4::SIZE, 1);
1377    assert_eq!(T5::SIZE, 1);
1378    assert_eq!(Some(Some(Some(()))).vec(), [0]);
1379    assert_eq!(Some(Some(None::<()>)).vec(), [1]);
1380    assert_eq!(Some(None::<Option<()>>).vec(), [2]);
1381    assert_eq!(None::<Option<Option<()>>>.vec(), [3]);
1382
1383    assert_eq!(false.vec(), [0]);
1384    assert_eq!(true.vec(), [1]);
1385    assert_eq!(Some(false).vec(), [0]);
1386    assert_eq!(Some(true).vec(), [1]);
1387    assert_eq!(None::<bool>.vec(), [2]);
1388    assert_eq!(Some(Some(false)).vec(), [0]);
1389    assert_eq!(Some(Some(true)).vec(), [1]);
1390    assert_eq!(Some(None::<bool>).vec(), [2]);
1391    assert_eq!(None::<Option<bool>>.vec(), [3]);
1392    assert_eq!(Some(Some(Some(false))).vec(), [0]);
1393    assert_eq!(Some(Some(Some(true))).vec(), [1]);
1394    assert_eq!(Some(Some(None::<bool>)).vec(), [2]);
1395    assert_eq!(Some(None::<Option<bool>>).vec(), [3]);
1396    assert_eq!(None::<Option<Option<bool>>>.vec(), [4]);
1397    assert_eq!(Option::<Hash>::SIZE, HASH_SIZE);
1398    assert_eq!(Some(()).vec(), [0]);
1399    assert_eq!(Some(((), ())).vec(), [0]);
1400    assert_eq!(Some(((), true)).vec(), [1]);
1401    assert_eq!(Some((true, true)).vec(), [1, 1]);
1402    assert_eq!(Some((Some(true), true)).vec(), [1, 1]);
1403    assert_eq!(Some((None::<bool>, true)).vec(), [2, 1]);
1404    assert_eq!(Some((true, None::<bool>)).vec(), [1, 2]);
1405    assert_eq!(None::<(Option<bool>, bool)>.vec(), [3, 2]);
1406    assert_eq!(None::<(bool, Option<bool>)>.vec(), [2, 3]);
1407    assert_eq!(Some(Some((Some(true), Some(true)))).vec(), [1, 1],);
1408    assert_eq!(Option::<Hash>::SIZE, HASH_SIZE);
1409    assert_eq!(Option::<Option<Hash>>::SIZE, HASH_SIZE);
1410    assert_eq!(Option::<Option<Option<Hash>>>::SIZE, HASH_SIZE);
1411}
object_rainbow/lib.rs

object_rainbow/
lib.rs
