simfony/
types.rs

1use std::fmt;
2use std::str::FromStr;
3use std::sync::Arc;
4
5use miniscript::iter::{Tree, TreeLike};
6use simplicity::types::{CompleteBound, Final};
7
8use crate::array::{BTreeSlice, Partition};
9use crate::num::{NonZeroPow2Usize, Pow2Usize};
10use crate::str::AliasName;
11
12/// Primitives of the Simfony type system, excluding type aliases.
13#[derive(Debug, PartialEq, Eq, Hash, Clone)]
14#[non_exhaustive]
15pub enum TypeInner<A> {
16    /// Sum of the left and right types
17    Either(A, A),
18    /// Option of the inner type
19    Option(A),
20    /// Boolean type
21    Boolean,
22    /// Unsigned integer type
23    UInt(UIntType),
24    /// Tuple of potentially different types
25    Tuple(Arc<[A]>),
26    /// Array of the same type
27    Array(A, usize),
28    /// List of the same type
29    List(A, NonZeroPow2Usize),
30}
31
32impl<A> TypeInner<A> {
33    /// Helper method for displaying type primitives based on the number of yielded children.
34    ///
35    /// We cannot implement [`fmt::Display`] because `n_children_yielded` is an extra argument.
36    fn display(&self, f: &mut fmt::Formatter<'_>, n_children_yielded: usize) -> fmt::Result {
37        match self {
38            TypeInner::Either(_, _) => match n_children_yielded {
39                0 => f.write_str("Either<"),
40                1 => f.write_str(","),
41                n => {
42                    debug_assert_eq!(n, 2);
43                    f.write_str(">")
44                }
45            },
46            TypeInner::Option(_) => match n_children_yielded {
47                0 => f.write_str("Option<"),
48                n => {
49                    debug_assert_eq!(n, 1);
50                    f.write_str(">")
51                }
52            },
53            TypeInner::Boolean => f.write_str("bool"),
54            TypeInner::UInt(ty) => write!(f, "{ty}"),
55            TypeInner::Tuple(elements) => match n_children_yielded {
56                0 => {
57                    f.write_str("(")?;
58                    if 0 == elements.len() {
59                        f.write_str(")")?;
60                    }
61                    Ok(())
62                }
63                n if n == elements.len() => {
64                    if n == 1 {
65                        f.write_str(",")?;
66                    }
67                    f.write_str(")")
68                }
69                n => {
70                    debug_assert!(n < elements.len());
71                    f.write_str(", ")
72                }
73            },
74            TypeInner::Array(_, size) => match n_children_yielded {
75                0 => f.write_str("["),
76                n => {
77                    debug_assert_eq!(n, 1);
78                    write!(f, "; {size}]")
79                }
80            },
81            TypeInner::List(_, bound) => match n_children_yielded {
82                0 => f.write_str("List<"),
83                n => {
84                    debug_assert_eq!(n, 1);
85                    write!(f, ", {bound}>")
86                }
87            },
88        }
89    }
90}
91
92/// Unsigned integer type.
93#[derive(PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Copy)]
94#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
95pub enum UIntType {
96    /// 1-bit unsigned integer
97    U1,
98    /// 2-bit unsigned integer
99    U2,
100    /// 4-bit unsigned integer
101    U4,
102    /// 8-bit unsigned integer
103    U8,
104    /// 16-bit unsigned integer
105    U16,
106    /// 32-bit unsigned integer
107    U32,
108    /// 64-bit unsigned integer
109    U64,
110    /// 128-bit unsigned integer
111    U128,
112    /// 256-bit unsigned integer
113    U256,
114}
115
116impl UIntType {
117    /// Take `n` and return the `2^n`-bit unsigned integer type.
118    pub const fn two_n(n: u32) -> Option<Self> {
119        match n {
120            0 => Some(UIntType::U1),
121            1 => Some(UIntType::U2),
122            2 => Some(UIntType::U4),
123            3 => Some(UIntType::U8),
124            4 => Some(UIntType::U16),
125            5 => Some(UIntType::U32),
126            6 => Some(UIntType::U64),
127            7 => Some(UIntType::U128),
128            8 => Some(UIntType::U256),
129            _ => None,
130        }
131    }
132
133    /// Return the bit width of values of this type.
134    pub const fn bit_width(self) -> Pow2Usize {
135        let bit_width: usize = match self {
136            UIntType::U1 => 1,
137            UIntType::U2 => 2,
138            UIntType::U4 => 4,
139            UIntType::U8 => 8,
140            UIntType::U16 => 16,
141            UIntType::U32 => 32,
142            UIntType::U64 => 64,
143            UIntType::U128 => 128,
144            UIntType::U256 => 256,
145        };
146        debug_assert!(bit_width.is_power_of_two());
147        Pow2Usize::new_unchecked(bit_width)
148    }
149
150    /// Create the unsigned integer type for the given `bit_width`.
151    pub const fn from_bit_width(bit_width: Pow2Usize) -> Option<Self> {
152        match bit_width.get() {
153            1 => Some(UIntType::U1),
154            2 => Some(UIntType::U2),
155            4 => Some(UIntType::U4),
156            8 => Some(UIntType::U8),
157            16 => Some(UIntType::U16),
158            32 => Some(UIntType::U32),
159            64 => Some(UIntType::U64),
160            128 => Some(UIntType::U128),
161            256 => Some(UIntType::U256),
162            _ => None,
163        }
164    }
165
166    /// Return the byte width of values of this type.
167    ///
168    /// Return 0 for types that take less than an entire byte: `u1`, `u2`, `u4`.
169    pub const fn byte_width(self) -> usize {
170        self.bit_width().get() / 8
171    }
172}
173
174impl fmt::Debug for UIntType {
175    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
176        write!(f, "{}", self)
177    }
178}
179
180impl fmt::Display for UIntType {
181    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
182        match self {
183            UIntType::U1 => f.write_str("u1"),
184            UIntType::U2 => f.write_str("u2"),
185            UIntType::U4 => f.write_str("u4"),
186            UIntType::U8 => f.write_str("u8"),
187            UIntType::U16 => f.write_str("u16"),
188            UIntType::U32 => f.write_str("u32"),
189            UIntType::U64 => f.write_str("u64"),
190            UIntType::U128 => f.write_str("u128"),
191            UIntType::U256 => f.write_str("u256"),
192        }
193    }
194}
195
196impl TryFrom<&StructuralType> for UIntType {
197    type Error = ();
198
199    fn try_from(value: &StructuralType) -> Result<Self, Self::Error> {
200        let mut current = value.as_ref();
201        let mut n = 0;
202        while let Some((left, right)) = current.as_product() {
203            if left.tmr() != right.tmr() {
204                return Err(());
205            }
206            current = left;
207            n += 1;
208        }
209        if let Some((left, right)) = current.as_sum() {
210            if left.is_unit() && right.is_unit() {
211                return UIntType::two_n(n).ok_or(());
212            }
213        }
214        Err(())
215    }
216}
217
218impl TryFrom<&ResolvedType> for UIntType {
219    type Error = ();
220
221    fn try_from(value: &ResolvedType) -> Result<Self, Self::Error> {
222        UIntType::try_from(&StructuralType::from(value))
223    }
224}
225
226macro_rules! construct_int {
227    ($name: ident, $ty: ident, $text: expr) => {
228        #[doc = "Create the type of"]
229        #[doc = $text]
230        #[doc = "integers."]
231        fn $name() -> Self {
232            Self::from(UIntType::$ty)
233        }
234    };
235}
236
237/// Various type constructors.
238pub trait TypeConstructible: Sized + From<UIntType> {
239    /// Create a sum of the given `left` and `right` types.
240    fn either(left: Self, right: Self) -> Self;
241
242    /// Create an option of the given `inner` type.
243    fn option(inner: Self) -> Self;
244
245    /// Create the Boolean type.
246    fn boolean() -> Self;
247
248    /// Create a tuple from the given `elements`.
249    ///
250    /// The empty tuple is the unit type.
251    /// A tuple of two types is a product.
252    fn tuple<I: IntoIterator<Item = Self>>(elements: I) -> Self;
253
254    /// Create the unit type.
255    fn unit() -> Self {
256        Self::tuple([])
257    }
258
259    /// Create a product of the given `left` and `right` types.
260    fn product(left: Self, right: Self) -> Self {
261        Self::tuple([left, right])
262    }
263
264    /// Create an array with `size` many values of the `element` type.
265    fn array(element: Self, size: usize) -> Self;
266
267    /// Create an array of `size` many bytes.
268    fn byte_array(size: usize) -> Self {
269        Self::array(Self::u8(), size)
270    }
271
272    /// Create a list with less than `bound` many values of the `element` type.
273    fn list(element: Self, bound: NonZeroPow2Usize) -> Self;
274
275    construct_int!(u1, U1, "1-bit");
276    construct_int!(u2, U2, "2-bit");
277    construct_int!(u4, U4, "4-bit");
278    construct_int!(u8, U8, "8-bit");
279    construct_int!(u16, U16, "16-bit");
280    construct_int!(u32, U32, "32-bit");
281    construct_int!(u64, U64, "64-bit");
282    construct_int!(u128, U128, "128-bit");
283    construct_int!(u256, U256, "256-bit");
284}
285
286/// Various type destructors for types that maintain the structure in which they were created.
287///
288/// [`StructuralType`] collapses its structure into Simplicity's units, sums and products,
289/// which is why it does not implement this trait.
290pub trait TypeDeconstructible: Sized {
291    /// Access the left and right types of a sum.
292    fn as_either(&self) -> Option<(&Self, &Self)>;
293
294    /// Access the inner type of an option.
295    fn as_option(&self) -> Option<&Self>;
296
297    /// Check if the type is Boolean.
298    fn is_boolean(&self) -> bool;
299
300    /// Access the internals of an integer type.
301    fn as_integer(&self) -> Option<UIntType>;
302
303    /// Access the element types of a tuple.
304    fn as_tuple(&self) -> Option<&[Arc<Self>]>;
305
306    /// Check if the type is the unit (empty tuple).
307    fn is_unit(&self) -> bool {
308        matches!(self.as_tuple(), Some(components) if components.is_empty())
309    }
310
311    /// Access the element type and size of an array.
312    fn as_array(&self) -> Option<(&Self, usize)>;
313
314    /// Access the element type and bound of a list.
315    fn as_list(&self) -> Option<(&Self, NonZeroPow2Usize)>;
316}
317
318/// Simfony type without type aliases.
319#[derive(PartialEq, Eq, Hash, Clone)]
320pub struct ResolvedType(TypeInner<Arc<Self>>);
321
322impl ResolvedType {
323    /// Access the inner type primitive.
324    pub fn as_inner(&self) -> &TypeInner<Arc<Self>> {
325        &self.0
326    }
327}
328
329impl TypeConstructible for ResolvedType {
330    fn either(left: Self, right: Self) -> Self {
331        Self(TypeInner::Either(Arc::new(left), Arc::new(right)))
332    }
333
334    fn option(inner: Self) -> Self {
335        Self(TypeInner::Option(Arc::new(inner)))
336    }
337
338    fn boolean() -> Self {
339        Self(TypeInner::Boolean)
340    }
341
342    fn tuple<I: IntoIterator<Item = Self>>(elements: I) -> Self {
343        Self(TypeInner::Tuple(
344            elements.into_iter().map(Arc::new).collect(),
345        ))
346    }
347
348    fn array(element: Self, size: usize) -> Self {
349        Self(TypeInner::Array(Arc::new(element), size))
350    }
351
352    fn list(element: Self, bound: NonZeroPow2Usize) -> Self {
353        Self(TypeInner::List(Arc::new(element), bound))
354    }
355}
356
357impl TypeDeconstructible for ResolvedType {
358    fn as_either(&self) -> Option<(&Self, &Self)> {
359        match self.as_inner() {
360            TypeInner::Either(ty_l, ty_r) => Some((ty_l, ty_r)),
361            _ => None,
362        }
363    }
364
365    fn as_option(&self) -> Option<&Self> {
366        match self.as_inner() {
367            TypeInner::Option(ty) => Some(ty),
368            _ => None,
369        }
370    }
371
372    fn is_boolean(&self) -> bool {
373        matches!(self.as_inner(), TypeInner::Boolean)
374    }
375
376    fn as_integer(&self) -> Option<UIntType> {
377        match self.as_inner() {
378            TypeInner::UInt(ty) => Some(*ty),
379            _ => None,
380        }
381    }
382
383    fn as_tuple(&self) -> Option<&[Arc<Self>]> {
384        match self.as_inner() {
385            TypeInner::Tuple(components) => Some(components),
386            _ => None,
387        }
388    }
389
390    fn as_array(&self) -> Option<(&Self, usize)> {
391        match self.as_inner() {
392            TypeInner::Array(ty, size) => Some((ty, *size)),
393            _ => None,
394        }
395    }
396
397    fn as_list(&self) -> Option<(&Self, NonZeroPow2Usize)> {
398        match self.as_inner() {
399            TypeInner::List(ty, bound) => Some((ty, *bound)),
400            _ => None,
401        }
402    }
403}
404
405impl TreeLike for &ResolvedType {
406    fn as_node(&self) -> Tree<Self> {
407        match &self.0 {
408            TypeInner::Boolean | TypeInner::UInt(..) => Tree::Nullary,
409            TypeInner::Option(l) | TypeInner::Array(l, _) | TypeInner::List(l, _) => Tree::Unary(l),
410            TypeInner::Either(l, r) => Tree::Binary(l, r),
411            TypeInner::Tuple(elements) => Tree::Nary(elements.iter().map(Arc::as_ref).collect()),
412        }
413    }
414}
415
416impl fmt::Debug for ResolvedType {
417    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
418        write!(f, "{}", self)
419    }
420}
421
422impl fmt::Display for ResolvedType {
423    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
424        for data in self.verbose_pre_order_iter() {
425            data.node.0.display(f, data.n_children_yielded)?;
426        }
427        Ok(())
428    }
429}
430
431impl From<UIntType> for ResolvedType {
432    fn from(value: UIntType) -> Self {
433        Self(TypeInner::UInt(value))
434    }
435}
436
437#[cfg(feature = "arbitrary")]
438impl crate::ArbitraryRec for ResolvedType {
439    fn arbitrary_rec(u: &mut arbitrary::Unstructured, budget: usize) -> arbitrary::Result<Self> {
440        use arbitrary::Arbitrary;
441
442        match budget.checked_sub(1) {
443            None => match u.int_in_range(0..=1)? {
444                0 => Ok(Self::boolean()),
445                1 => UIntType::arbitrary(u).map(Self::from),
446                _ => unreachable!(),
447            },
448            Some(new_budget) => match u.int_in_range(0..=6)? {
449                0 => Ok(Self::boolean()),
450                1 => UIntType::arbitrary(u).map(Self::from),
451                2 => Self::arbitrary_rec(u, new_budget).map(Self::option),
452                3 => {
453                    let left = Self::arbitrary_rec(u, new_budget)?;
454                    let right = Self::arbitrary_rec(u, new_budget)?;
455                    Ok(Self::either(left, right))
456                }
457                4 => {
458                    let len = u.int_in_range(0..=3)?;
459                    (0..len)
460                        .map(|_| Self::arbitrary_rec(u, new_budget))
461                        .collect::<arbitrary::Result<Vec<Self>>>()
462                        .map(Self::tuple)
463                }
464                5 => {
465                    let element = Self::arbitrary_rec(u, new_budget)?;
466                    let size = u.int_in_range(0..=3)?;
467                    Ok(Self::array(element, size))
468                }
469                6 => {
470                    let element = Self::arbitrary_rec(u, new_budget)?;
471                    let bound = NonZeroPow2Usize::arbitrary(u)?;
472                    Ok(Self::list(element, bound))
473                }
474                _ => unreachable!(),
475            },
476        }
477    }
478}
479
480#[cfg(feature = "arbitrary")]
481impl<'a> arbitrary::Arbitrary<'a> for ResolvedType {
482    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
483        <Self as crate::ArbitraryRec>::arbitrary_rec(u, 3)
484    }
485}
486
487/// Simfony type with type aliases.
488#[derive(PartialEq, Eq, Hash, Clone)]
489pub struct AliasedType(AliasedInner);
490
491/// Type alias or primitive.
492///
493/// Private struct to allow future changes.
494#[derive(Debug, PartialEq, Eq, Hash, Clone)]
495enum AliasedInner {
496    /// Type alias.
497    Alias(AliasName),
498    /// Builtin type alias.
499    Builtin(BuiltinAlias),
500    /// Type primitive.
501    Inner(TypeInner<Arc<AliasedType>>),
502}
503
504/// Type alias with predefined definition.
505#[derive(Copy, Clone, PartialEq, Eq, Hash)]
506#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
507pub enum BuiltinAlias {
508    Ctx8,
509    Pubkey,
510    Message,
511    Message64,
512    Signature,
513    Scalar,
514    Fe,
515    Ge,
516    Gej,
517    Point,
518    Height,
519    Time,
520    Distance,
521    Duration,
522    Lock,
523    Outpoint,
524    Confidential1,
525    ExplicitAsset,
526    Asset1,
527    ExplicitAmount,
528    Amount1,
529    ExplicitNonce,
530    Nonce,
531    TokenAmount1,
532}
533
534impl AliasedType {
535    /// Access a user-defined alias.
536    pub const fn as_alias(&self) -> Option<&AliasName> {
537        match &self.0 {
538            AliasedInner::Alias(name) => Some(name),
539            _ => None,
540        }
541    }
542
543    /// Access a buitlin alias.
544    pub const fn as_builtin(&self) -> Option<&BuiltinAlias> {
545        match &self.0 {
546            AliasedInner::Builtin(builtin) => Some(builtin),
547            _ => None,
548        }
549    }
550
551    /// Create a type alias from the given `identifier`.
552    pub const fn alias(name: AliasName) -> Self {
553        Self(AliasedInner::Alias(name))
554    }
555
556    /// Create a builtin type alias.
557    pub const fn builtin(builtin: BuiltinAlias) -> Self {
558        Self(AliasedInner::Builtin(builtin))
559    }
560
561    /// Resolve all aliases in the type based on the given map of `aliases` to types.
562    pub fn resolve<F>(&self, mut get_alias: F) -> Result<ResolvedType, AliasName>
563    where
564        F: FnMut(&AliasName) -> Option<ResolvedType>,
565    {
566        let mut output = vec![];
567        for data in self.post_order_iter() {
568            match &data.node.0 {
569                AliasedInner::Alias(name) => {
570                    let resolved = get_alias(name).ok_or(name.clone())?;
571                    output.push(resolved);
572                }
573                AliasedInner::Builtin(builtin) => {
574                    let resolved = builtin.resolve();
575                    output.push(resolved);
576                }
577                AliasedInner::Inner(inner) => match inner {
578                    TypeInner::Either(_, _) => {
579                        let right = output.pop().unwrap();
580                        let left = output.pop().unwrap();
581                        output.push(ResolvedType::either(left, right));
582                    }
583                    TypeInner::Option(_) => {
584                        let inner = output.pop().unwrap();
585                        output.push(ResolvedType::option(inner));
586                    }
587                    TypeInner::Boolean => output.push(ResolvedType::boolean()),
588                    TypeInner::UInt(integer) => output.push(ResolvedType::from(*integer)),
589                    TypeInner::Tuple(_) => {
590                        let size = data.node.n_children();
591                        let elements = output.split_off(output.len() - size);
592                        debug_assert_eq!(elements.len(), size);
593                        output.push(ResolvedType::tuple(elements));
594                    }
595                    TypeInner::Array(_, size) => {
596                        let element = output.pop().unwrap();
597                        output.push(ResolvedType::array(element, *size));
598                    }
599                    TypeInner::List(_, bound) => {
600                        let element = output.pop().unwrap();
601                        output.push(ResolvedType::list(element, *bound));
602                    }
603                },
604            }
605        }
606        debug_assert_eq!(output.len(), 1);
607        Ok(output.pop().unwrap())
608    }
609
610    /// Resolve all aliases in the type based on the builtin type aliases only.
611    pub fn resolve_builtin(&self) -> Result<ResolvedType, AliasName> {
612        self.resolve(|_| None)
613    }
614}
615
616impl TypeConstructible for AliasedType {
617    fn either(left: Self, right: Self) -> Self {
618        Self(AliasedInner::Inner(TypeInner::Either(
619            Arc::new(left),
620            Arc::new(right),
621        )))
622    }
623
624    fn option(inner: Self) -> Self {
625        Self(AliasedInner::Inner(TypeInner::Option(Arc::new(inner))))
626    }
627
628    fn boolean() -> Self {
629        Self(AliasedInner::Inner(TypeInner::Boolean))
630    }
631
632    fn tuple<I: IntoIterator<Item = Self>>(elements: I) -> Self {
633        Self(AliasedInner::Inner(TypeInner::Tuple(
634            elements.into_iter().map(Arc::new).collect(),
635        )))
636    }
637
638    fn array(element: Self, size: usize) -> Self {
639        Self(AliasedInner::Inner(TypeInner::Array(
640            Arc::new(element),
641            size,
642        )))
643    }
644
645    fn list(element: Self, bound: NonZeroPow2Usize) -> Self {
646        Self(AliasedInner::Inner(TypeInner::List(
647            Arc::new(element),
648            bound,
649        )))
650    }
651}
652
653impl TypeDeconstructible for AliasedType {
654    fn as_either(&self) -> Option<(&Self, &Self)> {
655        match &self.0 {
656            AliasedInner::Inner(TypeInner::Either(ty_l, ty_r)) => Some((ty_l, ty_r)),
657            _ => None,
658        }
659    }
660
661    fn as_option(&self) -> Option<&Self> {
662        match &self.0 {
663            AliasedInner::Inner(TypeInner::Option(ty)) => Some(ty),
664            _ => None,
665        }
666    }
667
668    fn is_boolean(&self) -> bool {
669        matches!(&self.0, AliasedInner::Inner(TypeInner::Boolean))
670    }
671
672    fn as_integer(&self) -> Option<UIntType> {
673        match &self.0 {
674            AliasedInner::Inner(TypeInner::UInt(ty)) => Some(*ty),
675            _ => None,
676        }
677    }
678
679    fn as_tuple(&self) -> Option<&[Arc<Self>]> {
680        match &self.0 {
681            AliasedInner::Inner(TypeInner::Tuple(components)) => Some(components),
682            _ => None,
683        }
684    }
685
686    fn as_array(&self) -> Option<(&Self, usize)> {
687        match &self.0 {
688            AliasedInner::Inner(TypeInner::Array(ty, size)) => Some((ty, *size)),
689            _ => None,
690        }
691    }
692
693    fn as_list(&self) -> Option<(&Self, NonZeroPow2Usize)> {
694        match &self.0 {
695            AliasedInner::Inner(TypeInner::List(ty, bound)) => Some((ty, *bound)),
696            _ => None,
697        }
698    }
699}
700
701impl TreeLike for &AliasedType {
702    fn as_node(&self) -> Tree<Self> {
703        match &self.0 {
704            AliasedInner::Alias(_) | AliasedInner::Builtin(_) => Tree::Nullary,
705            AliasedInner::Inner(inner) => match inner {
706                TypeInner::Boolean | TypeInner::UInt(..) => Tree::Nullary,
707                TypeInner::Option(l) | TypeInner::Array(l, _) | TypeInner::List(l, _) => {
708                    Tree::Unary(l)
709                }
710                TypeInner::Either(l, r) => Tree::Binary(l, r),
711                TypeInner::Tuple(elements) => {
712                    Tree::Nary(elements.iter().map(Arc::as_ref).collect())
713                }
714            },
715        }
716    }
717}
718
719impl fmt::Debug for AliasedType {
720    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
721        write!(f, "{}", self)
722    }
723}
724
725impl fmt::Display for AliasedType {
726    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
727        for data in self.verbose_pre_order_iter() {
728            match &data.node.0 {
729                AliasedInner::Alias(alias) => write!(f, "{alias}")?,
730                AliasedInner::Builtin(builtin) => write!(f, "{builtin}")?,
731                AliasedInner::Inner(inner) => inner.display(f, data.n_children_yielded)?,
732            }
733        }
734        Ok(())
735    }
736}
737
738impl From<UIntType> for AliasedType {
739    fn from(value: UIntType) -> Self {
740        Self(AliasedInner::Inner(TypeInner::UInt(value)))
741    }
742}
743
744impl From<AliasName> for AliasedType {
745    fn from(value: AliasName) -> Self {
746        Self::alias(value)
747    }
748}
749
750impl From<BuiltinAlias> for AliasedType {
751    fn from(value: BuiltinAlias) -> Self {
752        Self::builtin(value)
753    }
754}
755
756#[cfg(feature = "arbitrary")]
757impl crate::ArbitraryRec for AliasedType {
758    fn arbitrary_rec(u: &mut arbitrary::Unstructured, budget: usize) -> arbitrary::Result<Self> {
759        use arbitrary::Arbitrary;
760
761        match budget.checked_sub(1) {
762            None => match u.int_in_range(0..=3)? {
763                0 => AliasName::arbitrary(u).map(Self::alias),
764                1 => BuiltinAlias::arbitrary(u).map(Self::builtin),
765                2 => Ok(Self::boolean()),
766                3 => UIntType::arbitrary(u).map(Self::from),
767                _ => unreachable!(),
768            },
769            Some(new_budget) => match u.int_in_range(0..=8)? {
770                0 => AliasName::arbitrary(u).map(Self::alias),
771                1 => BuiltinAlias::arbitrary(u).map(Self::builtin),
772                2 => Ok(Self::boolean()),
773                3 => UIntType::arbitrary(u).map(Self::from),
774                4 => Self::arbitrary_rec(u, new_budget).map(Self::option),
775                5 => {
776                    let left = Self::arbitrary_rec(u, new_budget)?;
777                    let right = Self::arbitrary_rec(u, new_budget)?;
778                    Ok(Self::either(left, right))
779                }
780                6 => {
781                    let len = u.int_in_range(0..=3)?;
782                    (0..len)
783                        .map(|_| Self::arbitrary_rec(u, new_budget))
784                        .collect::<arbitrary::Result<Vec<Self>>>()
785                        .map(Self::tuple)
786                }
787                7 => {
788                    let element = Self::arbitrary_rec(u, new_budget)?;
789                    let size = u.int_in_range(0..=3)?;
790                    Ok(Self::array(element, size))
791                }
792                8 => {
793                    let element = Self::arbitrary_rec(u, new_budget)?;
794                    let bound = NonZeroPow2Usize::arbitrary(u)?;
795                    Ok(Self::list(element, bound))
796                }
797                _ => unreachable!(),
798            },
799        }
800    }
801}
802
803#[cfg(feature = "arbitrary")]
804impl<'a> arbitrary::Arbitrary<'a> for AliasedType {
805    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
806        <Self as crate::ArbitraryRec>::arbitrary_rec(u, 3)
807    }
808}
809
810impl BuiltinAlias {
811    pub fn resolve(self) -> ResolvedType {
812        use BuiltinAlias as B;
813        use UIntType::*;
814
815        match self {
816            B::Ctx8 => ResolvedType::tuple([
817                ResolvedType::list(U8.into(), NonZeroPow2Usize::new(64).unwrap()),
818                ResolvedType::tuple([U64.into(), U256.into()]),
819            ]),
820            B::Pubkey | B::Message | B::Scalar | B::Fe | B::ExplicitAsset | B::ExplicitNonce => {
821                U256.into()
822            }
823            B::Message64 | B::Signature => ResolvedType::array(U8.into(), 64),
824            B::Ge => ResolvedType::tuple([U256.into(), U256.into()]),
825            B::Gej => {
826                ResolvedType::tuple([ResolvedType::tuple([U256.into(), U256.into()]), U256.into()])
827            }
828            B::Point | B::Confidential1 => ResolvedType::tuple([U1.into(), U256.into()]),
829            B::Height | B::Time | B::Lock => U32.into(),
830            B::Distance | B::Duration => U16.into(),
831            B::Outpoint => ResolvedType::tuple([U256.into(), U32.into()]),
832            B::Asset1 | B::Nonce => {
833                ResolvedType::either(ResolvedType::tuple([U1.into(), U256.into()]), U256.into())
834            }
835            B::ExplicitAmount => U64.into(),
836            B::Amount1 | B::TokenAmount1 => {
837                ResolvedType::either(ResolvedType::tuple([U1.into(), U256.into()]), U64.into())
838            }
839        }
840    }
841}
842
843impl fmt::Debug for BuiltinAlias {
844    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
845        write!(f, "{}", self)
846    }
847}
848
849impl fmt::Display for BuiltinAlias {
850    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
851        match self {
852            BuiltinAlias::Ctx8 => f.write_str("Ctx8"),
853            BuiltinAlias::Pubkey => f.write_str("Pubkey"),
854            BuiltinAlias::Message => f.write_str("Message"),
855            BuiltinAlias::Message64 => f.write_str("Message64"),
856            BuiltinAlias::Signature => f.write_str("Signature"),
857            BuiltinAlias::Scalar => f.write_str("Scalar"),
858            BuiltinAlias::Fe => f.write_str("Fe"),
859            BuiltinAlias::Ge => f.write_str("Ge"),
860            BuiltinAlias::Gej => f.write_str("Gej"),
861            BuiltinAlias::Point => f.write_str("Point"),
862            BuiltinAlias::Height => f.write_str("Height"),
863            BuiltinAlias::Time => f.write_str("Time"),
864            BuiltinAlias::Distance => f.write_str("Distance"),
865            BuiltinAlias::Duration => f.write_str("Duration"),
866            BuiltinAlias::Lock => f.write_str("Lock"),
867            BuiltinAlias::Outpoint => f.write_str("Outpoint"),
868            BuiltinAlias::Confidential1 => f.write_str("Confidential1"),
869            BuiltinAlias::ExplicitAsset => f.write_str("ExplicitAsset"),
870            BuiltinAlias::Asset1 => f.write_str("Asset1"),
871            BuiltinAlias::ExplicitAmount => f.write_str("ExplicitAmount"),
872            BuiltinAlias::Amount1 => f.write_str("Amount1"),
873            BuiltinAlias::ExplicitNonce => f.write_str("ExplicitNonce"),
874            BuiltinAlias::Nonce => f.write_str("Nonce"),
875            BuiltinAlias::TokenAmount1 => f.write_str("TokenAmount1"),
876        }
877    }
878}
879
880impl FromStr for BuiltinAlias {
881    type Err = String;
882
883    fn from_str(s: &str) -> Result<Self, Self::Err> {
884        match s {
885            "Ctx8" => Ok(BuiltinAlias::Ctx8),
886            "Pubkey" => Ok(BuiltinAlias::Pubkey),
887            "Message" => Ok(BuiltinAlias::Message),
888            "Message64" => Ok(BuiltinAlias::Message64),
889            "Signature" => Ok(BuiltinAlias::Signature),
890            "Scalar" => Ok(BuiltinAlias::Scalar),
891            "Fe" => Ok(BuiltinAlias::Fe),
892            "Ge" => Ok(BuiltinAlias::Ge),
893            "Gej" => Ok(BuiltinAlias::Gej),
894            "Point" => Ok(BuiltinAlias::Point),
895            "Height" => Ok(BuiltinAlias::Height),
896            "Time" => Ok(BuiltinAlias::Time),
897            "Distance" => Ok(BuiltinAlias::Distance),
898            "Duration" => Ok(BuiltinAlias::Duration),
899            "Lock" => Ok(BuiltinAlias::Lock),
900            "Outpoint" => Ok(BuiltinAlias::Outpoint),
901            "Confidential1" => Ok(BuiltinAlias::Confidential1),
902            "ExplicitAsset" => Ok(BuiltinAlias::ExplicitAsset),
903            "Asset1" => Ok(BuiltinAlias::Asset1),
904            "ExplicitAmount" => Ok(BuiltinAlias::ExplicitAmount),
905            "Amount1" => Ok(BuiltinAlias::Amount1),
906            "ExplicitNonce" => Ok(BuiltinAlias::ExplicitNonce),
907            "Nonce" => Ok(BuiltinAlias::Nonce),
908            "TokenAmount1" => Ok(BuiltinAlias::TokenAmount1),
909            _ => Err("Unknown alias".to_string()),
910        }
911    }
912}
913
914/// Internal structure of a Simfony type.
915/// 1:1 isomorphism to Simplicity.
916#[derive(Clone, PartialEq, Eq, Hash)]
917pub struct StructuralType(Arc<Final>);
918
919impl AsRef<Final> for StructuralType {
920    fn as_ref(&self) -> &Final {
921        &self.0
922    }
923}
924
925impl From<StructuralType> for Arc<Final> {
926    fn from(value: StructuralType) -> Self {
927        value.0
928    }
929}
930
931impl From<Arc<Final>> for StructuralType {
932    fn from(value: Arc<Final>) -> Self {
933        Self(value)
934    }
935}
936
937impl TreeLike for StructuralType {
938    fn as_node(&self) -> Tree<Self> {
939        match self.0.bound() {
940            CompleteBound::Unit => Tree::Nullary,
941            CompleteBound::Sum(l, r) | CompleteBound::Product(l, r) => {
942                Tree::Binary(Self(l.clone()), Self(r.clone()))
943            }
944        }
945    }
946}
947
948impl fmt::Debug for StructuralType {
949    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
950        write!(f, "{}", &self.0)
951    }
952}
953
954impl fmt::Display for StructuralType {
955    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
956        write!(f, "{}", &self.0)
957    }
958}
959
960impl From<UIntType> for StructuralType {
961    fn from(value: UIntType) -> Self {
962        let inner = match value {
963            UIntType::U1 => Final::two_two_n(0),
964            UIntType::U2 => Final::two_two_n(1),
965            UIntType::U4 => Final::two_two_n(2),
966            UIntType::U8 => Final::two_two_n(3),
967            UIntType::U16 => Final::two_two_n(4),
968            UIntType::U32 => Final::two_two_n(5),
969            UIntType::U64 => Final::two_two_n(6),
970            UIntType::U128 => Final::two_two_n(7),
971            UIntType::U256 => Final::two_two_n(8),
972        };
973        Self(inner)
974    }
975}
976
977impl From<&ResolvedType> for StructuralType {
978    fn from(value: &ResolvedType) -> Self {
979        let mut output = vec![];
980        for data in value.post_order_iter() {
981            match &data.node.0 {
982                TypeInner::Either(_, _) => {
983                    let right = output.pop().unwrap();
984                    let left = output.pop().unwrap();
985                    output.push(StructuralType::either(left, right));
986                }
987                TypeInner::Option(_) => {
988                    let inner = output.pop().unwrap();
989                    output.push(StructuralType::option(inner));
990                }
991                TypeInner::Boolean => output.push(StructuralType::boolean()),
992                TypeInner::UInt(integer) => output.push(StructuralType::from(*integer)),
993                TypeInner::Tuple(_) => {
994                    let size = data.node.n_children();
995                    let elements = output.split_off(output.len() - size);
996                    debug_assert_eq!(elements.len(), size);
997                    output.push(StructuralType::tuple(elements));
998                }
999                TypeInner::Array(_, size) => {
1000                    let element = output.pop().unwrap();
1001                    output.push(StructuralType::array(element, *size));
1002                }
1003                TypeInner::List(_, bound) => {
1004                    let element = output.pop().unwrap();
1005                    output.push(StructuralType::list(element, *bound));
1006                }
1007            }
1008        }
1009        debug_assert_eq!(output.len(), 1);
1010        output.pop().unwrap()
1011    }
1012}
1013
1014impl TypeConstructible for StructuralType {
1015    fn either(left: Self, right: Self) -> Self {
1016        Self(Final::sum(left.0, right.0))
1017    }
1018
1019    fn option(inner: Self) -> Self {
1020        Self::either(Self::unit(), inner)
1021    }
1022
1023    fn boolean() -> Self {
1024        Self::either(Self::unit(), Self::unit())
1025    }
1026
1027    fn tuple<I: IntoIterator<Item = Self>>(elements: I) -> Self {
1028        let elements: Vec<_> = elements.into_iter().collect();
1029        let tree = BTreeSlice::from_slice(&elements);
1030        tree.fold(Self::product).unwrap_or_else(Self::unit)
1031    }
1032
1033    // Keep this implementation to prevent an infinite loop in <Self as TypeConstructible>::tuple
1034    fn unit() -> Self {
1035        Self(Final::unit())
1036    }
1037
1038    // Keep this implementation to prevent an infinite loop in <Self as TypeConstructible>::tuple
1039    fn product(left: Self, right: Self) -> Self {
1040        Self(Final::product(left.0, right.0))
1041    }
1042
1043    fn array(element: Self, size: usize) -> Self {
1044        // Cheap clone because Arc<Final> consists of Arcs
1045        let elements = vec![element; size];
1046        let tree = BTreeSlice::from_slice(&elements);
1047        tree.fold(Self::product).unwrap_or_else(Self::unit)
1048    }
1049
1050    fn list(element: Self, bound: NonZeroPow2Usize) -> Self {
1051        // Cheap clone because Arc<Final> consists of Arcs
1052        let el_vector = vec![element.0; bound.get() - 1];
1053        let partition = Partition::from_slice(&el_vector, bound);
1054        debug_assert!(partition.is_complete());
1055        let process = |block: &[Arc<Final>], size: usize| -> Arc<Final> {
1056            debug_assert_eq!(block.len(), size);
1057            let tree = BTreeSlice::from_slice(block);
1058            let array = tree.fold(Final::product).unwrap();
1059            Final::sum(Final::unit(), array)
1060        };
1061        let inner = partition.fold(process, Final::product);
1062        Self(inner)
1063    }
1064}
1065
1066impl StructuralType {
1067    /// Convert into an unfinalized type that can be used in Simplicity's unification algorithm.
1068    pub fn to_unfinalized(
1069        &self,
1070        inference_context: &simplicity::types::Context,
1071    ) -> simplicity::types::Type {
1072        simplicity::types::Type::complete(inference_context, self.0.clone())
1073    }
1074}
1075
1076#[cfg(test)]
1077mod tests {
1078    use super::*;
1079
1080    #[test]
1081    fn display_type() {
1082        let unit = ResolvedType::unit();
1083        assert_eq!("()", &unit.to_string());
1084        let singleton = ResolvedType::tuple([ResolvedType::u1()]);
1085        assert_eq!("(u1,)", &singleton.to_string());
1086        let pair = ResolvedType::tuple([ResolvedType::u1(), ResolvedType::u8()]);
1087        assert_eq!("(u1, u8)", &pair.to_string());
1088        let triple =
1089            ResolvedType::tuple([ResolvedType::u1(), ResolvedType::u8(), ResolvedType::u16()]);
1090        assert_eq!("(u1, u8, u16)", &triple.to_string());
1091        let empty_array = ResolvedType::array(ResolvedType::unit(), 0);
1092        assert_eq!("[(); 0]", &empty_array.to_string());
1093        let array = ResolvedType::array(ResolvedType::unit(), 3);
1094        assert_eq!("[(); 3]", &array.to_string());
1095        let list = ResolvedType::list(ResolvedType::unit(), NonZeroPow2Usize::TWO);
1096        assert_eq!("List<(), 2>", &list.to_string());
1097    }
1098}
simfony/types.rs

simfony/
types.rs
