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

object_rainbow/
lib.rs
