leo_ast/types/
type_.rs

1// Copyright (C) 2019-2026 Provable Inc.
2// This file is part of the Leo library.
3
4// The Leo library is free software: you can redistribute it and/or modify
5// it under the terms of the GNU General Public License as published by
6// the Free Software Foundation, either version 3 of the License, or
7// (at your option) any later version.
8
9// The Leo library is distributed in the hope that it will be useful,
10// but WITHOUT ANY WARRANTY; without even the implied warranty of
11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12// GNU General Public License for more details.
13
14// You should have received a copy of the GNU General Public License
15// along with the Leo library. If not, see <https://www.gnu.org/licenses/>.
16
17use crate::{
18    ArrayType,
19    CompositeType,
20    FutureType,
21    Identifier,
22    IntegerType,
23    Location,
24    MappingType,
25    OptionalType,
26    Path,
27    ProgramId,
28    TupleType,
29    Type,
30    TypeInterner,
31    VectorType,
32};
33
34use itertools::Itertools;
35use leo_span::Span;
36use serde::Serialize;
37use snarkvm::prelude::{
38    LiteralType,
39    Network,
40    PlaintextType,
41    PlaintextType::{Array, ExternalStruct, Literal, Struct},
42};
43use std::fmt;
44
45/// AST-level type annotation: the source-shaped `kind` with its cached canonical [`Type`]
46/// handle. `kind` and `type_` are private to preserve the invariant
47/// `type_ == interner.intern(&kind)`, which only [`TypeNode::new`] can establish.
48#[derive(Clone, Debug, Eq, Serialize)]
49pub struct TypeNode {
50    kind: TypeKind,
51    pub span: Span,
52    #[serde(skip)]
53    type_: Type,
54}
55
56impl TypeNode {
57    pub fn new(interner: &TypeInterner, kind: TypeKind, span: Span) -> Self {
58        let type_ = interner.intern(&kind);
59        Self { kind, span, type_ }
60    }
61
62    /// Escape hatch that skips interning. `type_` is `Type::ERR`; the value must reach an
63    /// interner before it can be compared or hashed. `PartialEq` / `Hash` `assert!` this.
64    pub fn unchecked(kind: TypeKind, span: Span) -> Self {
65        Self { kind, span, type_: Type::default() }
66    }
67
68    pub fn kind(&self) -> &TypeKind {
69        &self.kind
70    }
71
72    pub fn ty(&self) -> Type {
73        self.type_
74    }
75
76    pub fn into_parts(self) -> (TypeKind, Span, Type) {
77        (self.kind, self.span, self.type_)
78    }
79
80    /// Bypass the interner. The caller is responsible for `type_ == interner.intern(&kind)`;
81    /// only safe when `kind` is being canonicalized (span/id scrub) without shape change.
82    pub fn from_parts(kind: TypeKind, span: Span, type_: Type) -> Self {
83        Self { kind, span, type_ }
84    }
85
86    /// Fast path via the canonical handle; falls back to structural [`TypeKind::types_equivalent`]
87    /// for equivalences that don't imply identity — implicit `Future`, undetermined array length,
88    /// pending const-generic arguments.
89    pub fn types_equivalent(&self, other: &TypeNode) -> bool {
90        if self.type_ != Type::ERR && self.type_ == other.type_ {
91            return true;
92        }
93        self.kind.types_equivalent(&other.kind)
94    }
95}
96
97impl Default for TypeNode {
98    fn default() -> Self {
99        Self::unchecked(TypeKind::Err, Span::default())
100    }
101}
102
103impl PartialEq for TypeNode {
104    fn eq(&self, other: &Self) -> bool {
105        assert!(
106            self.kind == TypeKind::Err || self.type_ != Type::ERR,
107            "TypeNode with non-Err kind must have been interned before equality use",
108        );
109        assert!(
110            other.kind == TypeKind::Err || other.type_ != Type::ERR,
111            "TypeNode with non-Err kind must have been interned before equality use",
112        );
113        self.type_ == other.type_
114    }
115}
116
117impl std::hash::Hash for TypeNode {
118    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
119        assert!(
120            self.kind == TypeKind::Err || self.type_ != Type::ERR,
121            "TypeNode with non-Err kind must have been interned before hashing",
122        );
123        self.type_.hash(state);
124    }
125}
126
127impl fmt::Display for TypeNode {
128    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
129        self.kind.fmt(f)
130    }
131}
132
133/// Explicit type used for defining a variable or expression type
134#[derive(Clone, Debug, Default, PartialEq, Eq, Hash, Serialize)]
135pub enum TypeKind {
136    /// The `address` type.
137    Address,
138    /// The array type.
139    Array(ArrayType),
140    /// The `bool` type.
141    Boolean,
142    /// The composite type.
143    Composite(CompositeType),
144    /// The `field` type.
145    Field,
146    /// The `future` type.
147    Future(FutureType),
148    /// The `group` type.
149    Group,
150    /// The `identifier` type.
151    Identifier,
152    /// The `dyn record` type.
153    DynRecord,
154    /// A reference to a built in type.
155    Ident(Identifier),
156    /// An integer type.
157    Integer(IntegerType),
158    /// A mapping type.
159    Mapping(MappingType),
160    /// A nullable type.
161    Optional(OptionalType),
162    /// The `scalar` type.
163    Scalar,
164    /// The `signature` type.
165    Signature,
166    /// The `string` type.
167    String,
168    /// A static tuple of at least one type.
169    Tuple(TupleType),
170    /// The vector type.
171    Vector(VectorType),
172    /// Numeric type which should be resolved to `Field`, `Group`, `Integer(_)`, or `Scalar`.
173    Numeric,
174    /// The `unit` type.
175    Unit,
176    /// Placeholder for a type that could not be resolved or was not well-formed.
177    /// Will eventually lead to a compile error.
178    #[default]
179    Err,
180}
181
182impl TypeKind {
183    /// Are the types considered equal as far as the Leo user is concerned?
184    ///
185    /// In particular, any comparison involving an `Err` is `true`, and Futures which aren't explicit compare equal to
186    /// other Futures.
187    ///
188    /// An array with an undetermined length (e.g., one that depends on a `const`) is considered equal to other arrays
189    /// if their element types match. This allows const propagation to potentially resolve the length before type
190    /// checking is performed again.
191    ///
192    /// Composite types are considered equal if their names and resolved program names match. If either side still has
193    /// const generic arguments, they are treated as equal unconditionally since monomorphization and other passes of
194    /// type-checking will handle mismatches later.
195    pub fn types_equivalent(&self, other: &TypeKind) -> bool {
196        match (self, other) {
197            (TypeKind::Err, _)
198            | (_, TypeKind::Err)
199            | (TypeKind::Address, TypeKind::Address)
200            | (TypeKind::Boolean, TypeKind::Boolean)
201            | (TypeKind::Field, TypeKind::Field)
202            | (TypeKind::Group, TypeKind::Group)
203            | (TypeKind::Scalar, TypeKind::Scalar)
204            | (TypeKind::Signature, TypeKind::Signature)
205            | (TypeKind::String, TypeKind::String)
206            | (TypeKind::Identifier, TypeKind::Identifier)
207            | (TypeKind::DynRecord, TypeKind::DynRecord)
208            | (TypeKind::Unit, TypeKind::Unit) => true,
209            (TypeKind::Array(left), TypeKind::Array(right)) => {
210                (match (left.length.as_u32(), right.length.as_u32()) {
211                    (Some(l1), Some(l2)) => l1 == l2,
212                    _ => {
213                        // An array with an undetermined length (e.g., one that depends on a `const`) is considered
214                        // equal to other arrays because their lengths _may_ eventually be proven equal.
215                        true
216                    }
217                }) && left.element_type().types_equivalent(right.element_type())
218            }
219            (TypeKind::Ident(left), TypeKind::Ident(right)) => left.name == right.name,
220            (TypeKind::Integer(left), TypeKind::Integer(right)) => left == right,
221            (TypeKind::Mapping(left), TypeKind::Mapping(right)) => {
222                left.key.types_equivalent(&right.key) && left.value.types_equivalent(&right.value)
223            }
224            (TypeKind::Optional(left), TypeKind::Optional(right)) => left.inner.types_equivalent(&right.inner),
225            (TypeKind::Tuple(left), TypeKind::Tuple(right)) if left.length() == right.length() => left
226                .elements()
227                .iter()
228                .zip_eq(right.elements().iter())
229                .all(|(left_type, right_type)| left_type.types_equivalent(right_type)),
230            (TypeKind::Vector(left), TypeKind::Vector(right)) => {
231                left.element_type.types_equivalent(&right.element_type)
232            }
233            (TypeKind::Composite(left), TypeKind::Composite(right)) => {
234                // If either composite still has const generic arguments, treat them as equal;
235                // monomorphization and a subsequent type-checking pass will handle mismatches.
236                if !left.const_arguments.is_empty() || !right.const_arguments.is_empty() {
237                    return true;
238                }
239
240                // Two composite types are the same if their global locations match.
241                match (&left.path.try_global_location(), &right.path.try_global_location()) {
242                    (Some(l), Some(r)) => l == r,
243                    _ => false,
244                }
245            }
246
247            (TypeKind::Future(left), TypeKind::Future(right)) if !left.is_explicit || !right.is_explicit => true,
248            (TypeKind::Future(left), TypeKind::Future(right)) if left.inputs.len() == right.inputs.len() => left
249                .inputs()
250                .iter()
251                .zip_eq(right.inputs().iter())
252                .all(|(left_type, right_type)| left_type.types_equivalent(right_type)),
253            _ => false,
254        }
255    }
256
257    pub fn from_snarkvm<N: Network>(t: &PlaintextType<N>, program_id: ProgramId) -> Self {
258        match t {
259            Literal(lit) => (*lit).into(),
260            Struct(s) => TypeKind::Composite(CompositeType {
261                path: {
262                    let ident = Identifier::from(s);
263                    Path::from(ident).to_global(Location::new(program_id.as_symbol(), vec![ident.name]))
264                },
265                const_arguments: Vec::new(),
266            }),
267            ExternalStruct(l) => TypeKind::Composite(CompositeType {
268                path: {
269                    let external_program = ProgramId::from(l.program_id());
270                    let name = Identifier::from(l.resource());
271                    Path::from(name)
272                        .with_user_program(external_program)
273                        .to_global(Location::new(external_program.as_symbol(), vec![name.name]))
274                },
275                const_arguments: Vec::new(),
276            }),
277            Array(array) => TypeKind::Array(ArrayType::from_snarkvm(array, program_id)),
278        }
279    }
280
281    // Attempts to convert `self` to a snarkVM `PlaintextType`.
282    pub fn to_snarkvm<N: Network>(&self) -> anyhow::Result<PlaintextType<N>> {
283        match self {
284            TypeKind::Address => Ok(PlaintextType::Literal(snarkvm::prelude::LiteralType::Address)),
285            TypeKind::Boolean => Ok(PlaintextType::Literal(snarkvm::prelude::LiteralType::Boolean)),
286            TypeKind::Field => Ok(PlaintextType::Literal(snarkvm::prelude::LiteralType::Field)),
287            TypeKind::Group => Ok(PlaintextType::Literal(snarkvm::prelude::LiteralType::Group)),
288            TypeKind::Integer(int_type) => match int_type {
289                IntegerType::U8 => Ok(PlaintextType::Literal(snarkvm::prelude::LiteralType::U8)),
290                IntegerType::U16 => Ok(PlaintextType::Literal(snarkvm::prelude::LiteralType::U16)),
291                IntegerType::U32 => Ok(PlaintextType::Literal(snarkvm::prelude::LiteralType::U32)),
292                IntegerType::U64 => Ok(PlaintextType::Literal(snarkvm::prelude::LiteralType::U64)),
293                IntegerType::U128 => Ok(PlaintextType::Literal(snarkvm::prelude::LiteralType::U128)),
294                IntegerType::I8 => Ok(PlaintextType::Literal(snarkvm::prelude::LiteralType::I8)),
295                IntegerType::I16 => Ok(PlaintextType::Literal(snarkvm::prelude::LiteralType::I16)),
296                IntegerType::I32 => Ok(PlaintextType::Literal(snarkvm::prelude::LiteralType::I32)),
297                IntegerType::I64 => Ok(PlaintextType::Literal(snarkvm::prelude::LiteralType::I64)),
298                IntegerType::I128 => Ok(PlaintextType::Literal(snarkvm::prelude::LiteralType::I128)),
299            },
300            TypeKind::Scalar => Ok(PlaintextType::Literal(snarkvm::prelude::LiteralType::Scalar)),
301            TypeKind::Signature => Ok(PlaintextType::Literal(snarkvm::prelude::LiteralType::Signature)),
302            TypeKind::Array(array_type) => Ok(PlaintextType::<N>::Array(array_type.to_snarkvm()?)),
303            _ => anyhow::bail!("Converting from type {self} to snarkVM type is not supported"),
304        }
305    }
306
307    // A helper function to get the size in bits of the input type.
308    pub fn size_in_bits<N: Network, F0, F1>(
309        &self,
310        is_raw: bool,
311        get_structs: F0,
312        get_external_structs: F1,
313    ) -> anyhow::Result<usize>
314    where
315        F0: Fn(&snarkvm::prelude::Identifier<N>) -> anyhow::Result<snarkvm::prelude::StructType<N>>,
316        F1: Fn(&snarkvm::prelude::Locator<N>) -> anyhow::Result<snarkvm::prelude::StructType<N>>,
317    {
318        match is_raw {
319            false => self.to_snarkvm::<N>()?.size_in_bits(&get_structs, &get_external_structs),
320            true => self.to_snarkvm::<N>()?.size_in_bits_raw(&get_structs, &get_external_structs),
321        }
322    }
323
324    /// Determines whether `self` can be coerced to the `expected` type.
325    ///
326    /// This method checks if the current type can be implicitly coerced to the expected type
327    /// according to specific rules:
328    /// - `Optional<T>` can be coerced to `Optional<T>`.
329    /// - `T` can be coerced to `Optional<T>`.
330    /// - Arrays `[T; N]` can be coerced to `[Optional<T>; N]` if lengths match or are unknown,
331    ///   and element types are coercible.
332    /// - Falls back to an equality check for other types.
333    ///
334    /// # Arguments
335    /// * `expected` - The type to which `self` is being coerced.
336    ///
337    /// # Returns
338    /// `true` if coercion is allowed; `false` otherwise.
339    pub fn can_coerce_to(&self, expected: &TypeKind) -> bool {
340        use TypeKind::*;
341
342        match (self, expected) {
343            // Allow Optional<T> → Optional<T>
344            (Optional(actual_opt), Optional(expected_opt)) => actual_opt.inner.can_coerce_to(&expected_opt.inner),
345
346            // Allow T → Optional<T>
347            (a, Optional(opt)) => a.can_coerce_to(&opt.inner),
348
349            // Allow [T; N] → [Optional<T>; N]
350            (Array(a_arr), Array(e_arr)) => {
351                let lengths_equal = match (a_arr.length.as_u32(), e_arr.length.as_u32()) {
352                    (Some(l1), Some(l2)) => l1 == l2,
353                    _ => true,
354                };
355
356                lengths_equal && a_arr.element_type().can_coerce_to(e_arr.element_type())
357            }
358
359            // Fallback: check for exact match
360            _ => self.types_equivalent(expected),
361        }
362    }
363
364    pub fn is_optional(&self) -> bool {
365        matches!(self, Self::Optional(_))
366    }
367
368    pub fn is_vector(&self) -> bool {
369        matches!(self, Self::Vector(_))
370    }
371
372    pub fn is_mapping(&self) -> bool {
373        matches!(self, Self::Mapping(_))
374    }
375
376    pub fn to_optional(&self) -> TypeKind {
377        TypeKind::Optional(OptionalType { inner: Box::new(self.clone()) })
378    }
379
380    pub fn is_empty(&self) -> bool {
381        match self {
382            TypeKind::Unit => true,
383            TypeKind::Array(array_type) => {
384                if let Some(length) = array_type.length.as_u32() {
385                    length == 0
386                } else {
387                    false
388                }
389            }
390            _ => false,
391        }
392    }
393
394    /// Whether this type is allowed as the declared type of a const generic parameter.
395    /// The const-generic monomorphization backend can only substitute a fixed set of literal
396    /// shapes; adding another case here requires backend support.
397    pub fn is_valid_const_generic_type(&self) -> bool {
398        matches!(
399            self,
400            TypeKind::Boolean
401                | TypeKind::Integer(_)
402                | TypeKind::Address
403                | TypeKind::Scalar
404                | TypeKind::Group
405                | TypeKind::Field
406                | TypeKind::Identifier
407        )
408    }
409}
410
411impl From<LiteralType> for TypeKind {
412    fn from(value: LiteralType) -> Self {
413        match value {
414            LiteralType::Identifier => TypeKind::Identifier,
415            LiteralType::Address => TypeKind::Address,
416            LiteralType::Boolean => TypeKind::Boolean,
417            LiteralType::Field => TypeKind::Field,
418            LiteralType::Group => TypeKind::Group,
419            LiteralType::U8 => TypeKind::Integer(IntegerType::U8),
420            LiteralType::U16 => TypeKind::Integer(IntegerType::U16),
421            LiteralType::U32 => TypeKind::Integer(IntegerType::U32),
422            LiteralType::U64 => TypeKind::Integer(IntegerType::U64),
423            LiteralType::U128 => TypeKind::Integer(IntegerType::U128),
424            LiteralType::I8 => TypeKind::Integer(IntegerType::I8),
425            LiteralType::I16 => TypeKind::Integer(IntegerType::I16),
426            LiteralType::I32 => TypeKind::Integer(IntegerType::I32),
427            LiteralType::I64 => TypeKind::Integer(IntegerType::I64),
428            LiteralType::I128 => TypeKind::Integer(IntegerType::I128),
429            LiteralType::Scalar => TypeKind::Scalar,
430            LiteralType::Signature => TypeKind::Signature,
431            LiteralType::String => TypeKind::String,
432        }
433    }
434}
435
436impl fmt::Display for TypeKind {
437    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
438        match *self {
439            TypeKind::Address => write!(f, "address"),
440            TypeKind::Identifier => write!(f, "identifier"),
441            TypeKind::DynRecord => write!(f, "dyn record"),
442            TypeKind::Array(ref array_type) => write!(f, "{array_type}"),
443            TypeKind::Boolean => write!(f, "bool"),
444            TypeKind::Field => write!(f, "field"),
445            TypeKind::Future(ref future_type) => write!(f, "{future_type}"),
446            TypeKind::Group => write!(f, "group"),
447            TypeKind::Ident(ref variable) => write!(f, "{variable}"),
448            TypeKind::Integer(ref integer_type) => write!(f, "{integer_type}"),
449            TypeKind::Mapping(ref mapping_type) => write!(f, "{mapping_type}"),
450            TypeKind::Optional(ref optional_type) => write!(f, "{optional_type}"),
451            TypeKind::Scalar => write!(f, "scalar"),
452            TypeKind::Signature => write!(f, "signature"),
453            TypeKind::String => write!(f, "string"),
454            TypeKind::Composite(ref composite_type) => write!(f, "{composite_type}"),
455            TypeKind::Tuple(ref tuple) => write!(f, "{tuple}"),
456            TypeKind::Vector(ref vector_type) => write!(f, "{vector_type}"),
457            TypeKind::Numeric => write!(f, "numeric"),
458            TypeKind::Unit => write!(f, "()"),
459            TypeKind::Err => write!(f, "error"),
460        }
461    }
462}
463
464#[cfg(test)]
465mod tests {
466    use super::*;
467
468    #[test]
469    #[should_panic(expected = "TypeNode with non-Err kind must have been interned")]
470    fn eq_panics_on_unchecked_non_err_kind() {
471        let interner = TypeInterner::new();
472        let unchecked = TypeNode::unchecked(TypeKind::Address, Span::default());
473        let interned = TypeNode::new(&interner, TypeKind::Boolean, Span::default());
474        let _ = unchecked == interned;
475    }
476
477    #[test]
478    #[should_panic(expected = "TypeNode with non-Err kind must have been interned")]
479    fn hash_panics_on_unchecked_non_err_kind() {
480        use std::hash::Hash;
481
482        let unchecked = TypeNode::unchecked(TypeKind::Address, Span::default());
483        let mut hasher = std::collections::hash_map::DefaultHasher::new();
484        unchecked.hash(&mut hasher);
485    }
486
487    #[test]
488    fn eq_accepts_defaulted_err_nodes() {
489        // Default (`Err`, `Type::ERR`) values must remain comparable — the invariant
490        // is scoped to *non-Err* kinds.
491        let a = TypeNode::default();
492        let b = TypeNode::default();
493        assert_eq!(a, b);
494    }
495}
leo_ast/types/type_.rs

leo_ast/types/
type_.rs
