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

object_rainbow/
lib.rs
