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

object_rainbow/
lib.rs
