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

object_rainbow/
lib.rs
