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

object_rainbow/
lib.rs
