leo_ast/types/
interner.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
17//! Per-session arena assigning each canonical [`TypeKind`] a stable [`Type`] handle. Ground
18//! variants are pre-interned at fixed ids ([`Type::ADDRESS`] etc.); id 0 is [`Type::ERR`], so
19//! `Type::default()` is the error sentinel.
20
21use crate::{Canonicalize, IntegerType, TypeKind};
22
23use fxhash::FxBuildHasher;
24use indexmap::IndexSet;
25use std::cell::RefCell;
26
27/// Canonical type identity. `Copy`, id-equality. Ground variants are pre-interned at fixed
28/// positions so `Type::ADDRESS`, `Type::U32`, etc. are `const`. For the source-shaped view,
29/// see [`crate::TypeNode`].
30#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Default)]
31pub struct Type(u32);
32
33impl Type {
34    pub const ADDRESS: Type = Type(1);
35    pub const BOOLEAN: Type = Type(2);
36    pub const DYN_RECORD: Type = Type(11);
37    // Every `TypeInterner::new()` pre-fills these in this exact order.
38    pub const ERR: Type = Type(0);
39    pub const FIELD: Type = Type(3);
40    pub const GROUP: Type = Type(4);
41    pub const I128: Type = Type(21);
42    pub const I16: Type = Type(18);
43    pub const I32: Type = Type(19);
44    pub const I64: Type = Type(20);
45    pub const I8: Type = Type(17);
46    pub const IDENTIFIER: Type = Type(10);
47    pub const NUMERIC: Type = Type(9);
48    pub const NUM_PREINTERNED: u32 = 22;
49    pub const SCALAR: Type = Type(5);
50    pub const SIGNATURE: Type = Type(6);
51    pub const STRING: Type = Type(7);
52    pub const U128: Type = Type(16);
53    pub const U16: Type = Type(13);
54    pub const U32: Type = Type(14);
55    pub const U64: Type = Type(15);
56    pub const U8: Type = Type(12);
57    pub const UNIT: Type = Type(8);
58
59    pub fn index(self) -> usize {
60        self.0 as usize
61    }
62}
63
64/// `IndexSet` of canonical [`TypeKind`] keys; the insertion index is the [`Type`].
65pub struct TypeInterner {
66    storage: RefCell<IndexSet<TypeKind, FxBuildHasher>>,
67}
68
69impl TypeInterner {
70    /// The pre-intern order MUST match the `Type::*` consts; `assert_preintern_layout` guards it.
71    pub fn new() -> Self {
72        let preintern = [
73            TypeKind::Err,
74            TypeKind::Address,
75            TypeKind::Boolean,
76            TypeKind::Field,
77            TypeKind::Group,
78            TypeKind::Scalar,
79            TypeKind::Signature,
80            TypeKind::String,
81            TypeKind::Unit,
82            TypeKind::Numeric,
83            TypeKind::Identifier,
84            TypeKind::DynRecord,
85            TypeKind::Integer(IntegerType::U8),
86            TypeKind::Integer(IntegerType::U16),
87            TypeKind::Integer(IntegerType::U32),
88            TypeKind::Integer(IntegerType::U64),
89            TypeKind::Integer(IntegerType::U128),
90            TypeKind::Integer(IntegerType::I8),
91            TypeKind::Integer(IntegerType::I16),
92            TypeKind::Integer(IntegerType::I32),
93            TypeKind::Integer(IntegerType::I64),
94            TypeKind::Integer(IntegerType::I128),
95        ];
96        let mut storage: IndexSet<TypeKind, FxBuildHasher> = IndexSet::with_hasher(FxBuildHasher::default());
97        for d in preintern {
98            storage.insert(d);
99        }
100        assert_eq!(storage.len(), Type::NUM_PREINTERNED as usize);
101        Self { storage: RefCell::new(storage) }
102    }
103
104    /// `&self`, not `&mut`, so callers can intern mid-expression without restructuring borrows.
105    pub fn intern(&self, data: &TypeKind) -> Type {
106        let canonical = data.clone().canonicalize();
107        let mut s = self.storage.borrow_mut();
108        if let Some(idx) = s.get_index_of(&canonical) {
109            return Type(idx as u32);
110        }
111        let (idx, _) = s.insert_full(canonical);
112        Type(idx as u32)
113    }
114
115    /// Resolve a canonical [`Type`] handle back to a cloned [`TypeKind`]. Panics if `ty`
116    /// is not a valid handle for this interner (shouldn't happen in practice — see
117    /// [`Type::default`] which uses the pre-interned `Type::ERR`).
118    pub fn resolve(&self, ty: Type) -> TypeKind {
119        self.storage.borrow().get_index(ty.index()).expect("Invalid Type handle").clone()
120    }
121}
122
123impl Default for TypeInterner {
124    fn default() -> Self {
125        Self::new()
126    }
127}
128
129#[cfg(test)]
130mod tests {
131    use super::*;
132
133    #[test]
134    fn err_is_pre_interned_at_id_zero() {
135        let i = TypeInterner::new();
136        assert_eq!(i.intern(&TypeKind::Err), Type::ERR);
137        assert_eq!(Type::ERR.index(), 0);
138    }
139
140    /// If this fails, the pre-intern order in `TypeInterner::new` and the `Type::*` consts
141    /// have fallen out of sync.
142    #[test]
143    fn assert_preintern_layout() {
144        let i = TypeInterner::new();
145        assert_eq!(i.intern(&TypeKind::Err), Type::ERR);
146        assert_eq!(i.intern(&TypeKind::Address), Type::ADDRESS);
147        assert_eq!(i.intern(&TypeKind::Boolean), Type::BOOLEAN);
148        assert_eq!(i.intern(&TypeKind::Field), Type::FIELD);
149        assert_eq!(i.intern(&TypeKind::Group), Type::GROUP);
150        assert_eq!(i.intern(&TypeKind::Scalar), Type::SCALAR);
151        assert_eq!(i.intern(&TypeKind::Signature), Type::SIGNATURE);
152        assert_eq!(i.intern(&TypeKind::String), Type::STRING);
153        assert_eq!(i.intern(&TypeKind::Unit), Type::UNIT);
154        assert_eq!(i.intern(&TypeKind::Numeric), Type::NUMERIC);
155        assert_eq!(i.intern(&TypeKind::Identifier), Type::IDENTIFIER);
156        assert_eq!(i.intern(&TypeKind::DynRecord), Type::DYN_RECORD);
157        assert_eq!(i.intern(&TypeKind::Integer(IntegerType::U8)), Type::U8);
158        assert_eq!(i.intern(&TypeKind::Integer(IntegerType::U16)), Type::U16);
159        assert_eq!(i.intern(&TypeKind::Integer(IntegerType::U32)), Type::U32);
160        assert_eq!(i.intern(&TypeKind::Integer(IntegerType::U64)), Type::U64);
161        assert_eq!(i.intern(&TypeKind::Integer(IntegerType::U128)), Type::U128);
162        assert_eq!(i.intern(&TypeKind::Integer(IntegerType::I8)), Type::I8);
163        assert_eq!(i.intern(&TypeKind::Integer(IntegerType::I16)), Type::I16);
164        assert_eq!(i.intern(&TypeKind::Integer(IntegerType::I32)), Type::I32);
165        assert_eq!(i.intern(&TypeKind::Integer(IntegerType::I64)), Type::I64);
166        assert_eq!(i.intern(&TypeKind::Integer(IntegerType::I128)), Type::I128);
167        assert_eq!(i.storage.borrow().len() as u32, Type::NUM_PREINTERNED);
168    }
169
170    #[test]
171    fn intern_is_idempotent() {
172        let i = TypeInterner::new();
173        let a = i.intern(&TypeKind::Field);
174        let b = i.intern(&TypeKind::Field);
175        assert_eq!(a, b);
176    }
177
178    #[test]
179    fn distinct_data_gets_distinct_ids() {
180        let i = TypeInterner::new();
181        let a = i.intern(&TypeKind::Field);
182        let b = i.intern(&TypeKind::Boolean);
183        assert_ne!(a, b);
184    }
185
186    #[test]
187    fn default_id_is_err() {
188        assert_eq!(Type::default(), Type::ERR);
189    }
190}
leo_ast/types/interner.rs

leo_ast/types/
interner.rs
