Skip to main content

typeck_lang/
types.rs

1//! Interned type terms.
2//!
3//! Every type is a node in one [`Types`] store, and structurally equal nodes
4//! are the same node (hash-consing): `(i32, i32)` built twice is one
5//! [`TypeId`]. Equality of finished types is therefore an integer compare, and
6//! a type that mentions the same sub-type twice stores it once, so shared
7//! structure never multiplies (ISSUES M39: the `Pair(v, v)` doubling chain is a
8//! DAG of `n` nodes here, never a tree of `2^n`).
9//!
10//! The store also holds inference variables while a check runs. They never
11//! reach the output: [`Typed`](crate::Typed) side tables only name
12//! variable-free types.
13
14use alloc::{string::String, vec::Vec};
15use core::fmt;
16
17use hir_lang::{BinderId, Def, DefId, Effects, ItemId, Prim, Symbol, TyId, UnitId, VariantId};
18use intern_lang::Lookup;
19
20/// A type in a [`Types`] store.
21///
22/// Ids are dense and only meaningful for the store that issued them. The
23/// fixed ids below exist in every store.
24///
25/// # Examples
26///
27/// ```
28/// use typeck_lang::{TypeId, Types};
29/// use hir_lang::Prim;
30///
31/// let mut types = Types::new();
32/// let pair = types.tuple(&[TypeId::prim(Prim::I32), TypeId::prim(Prim::I32)]);
33/// // Hash-consed: building the same type again yields the same id.
34/// assert_eq!(pair, types.tuple(&[TypeId::prim(Prim::I32), TypeId::prim(Prim::I32)]));
35/// assert_ne!(pair, TypeId::UNIT);
36/// ```
37#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
38pub struct TypeId(u32);
39
40/// The number of [`Prim`] variants; their types have the fixed ids after the
41/// five builtins.
42const PRIMS: [Prim; 15] = [
43    Prim::Bool,
44    Prim::I8,
45    Prim::I16,
46    Prim::I32,
47    Prim::I64,
48    Prim::Isize,
49    Prim::U8,
50    Prim::U16,
51    Prim::U32,
52    Prim::U64,
53    Prim::Usize,
54    Prim::F32,
55    Prim::F64,
56    Prim::Char,
57    Prim::Str,
58];
59
60/// Builtin nodes that precede the primitives.
61const FIRST_PRIM: u32 = 5;
62
63const fn prim_code(p: Prim) -> u8 {
64    match p {
65        Prim::Bool => 0,
66        Prim::I8 => 1,
67        Prim::I16 => 2,
68        Prim::I32 => 3,
69        Prim::I64 => 4,
70        Prim::Isize => 5,
71        Prim::U8 => 6,
72        Prim::U16 => 7,
73        Prim::U32 => 8,
74        Prim::U64 => 9,
75        Prim::Usize => 10,
76        Prim::F32 => 11,
77        Prim::F64 => 12,
78        Prim::Char => 13,
79        Prim::Str => 14,
80    }
81}
82
83impl TypeId {
84    /// The error type `{error}`: the type of anything already reported. Every
85    /// check that meets it succeeds silently, so one root cause produces one
86    /// diagnostic.
87    pub const ERROR: Self = Self(0);
88    /// The dynamic type: any value, checked at run time.
89    pub const ANY: Self = Self(1);
90    /// The type of expressions that never produce a value (`return`, `break`,
91    /// `throw`, an endless loop). It coerces to every type.
92    pub const NEVER: Self = Self(2);
93    /// The type of the `null` literal.
94    pub const NULL: Self = Self(3);
95    /// The empty tuple `()`.
96    pub const UNIT: Self = Self(4);
97
98    /// The type of a primitive.
99    ///
100    /// # Examples
101    ///
102    /// ```
103    /// use typeck_lang::{Type, TypeId, Types};
104    /// use hir_lang::Prim;
105    ///
106    /// let types = Types::new();
107    /// assert_eq!(types.get(TypeId::prim(Prim::Bool)), Type::Prim(Prim::Bool));
108    /// ```
109    #[must_use]
110    pub const fn prim(p: Prim) -> Self {
111        Self(FIRST_PRIM + prim_code(p) as u32)
112    }
113
114    /// The dense index of this id in its store.
115    ///
116    /// # Examples
117    ///
118    /// ```
119    /// use typeck_lang::TypeId;
120    ///
121    /// assert_eq!(TypeId::ERROR.index(), 0);
122    /// ```
123    #[must_use]
124    pub const fn index(self) -> usize {
125        self.0 as usize
126    }
127
128    pub(crate) const fn raw(self) -> u32 {
129        self.0
130    }
131
132    pub(crate) const fn from_raw(raw: u32) -> Self {
133        Self(raw)
134    }
135}
136
137impl fmt::Debug for TypeId {
138    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
139        write!(f, "TypeId({})", self.0)
140    }
141}
142
143/// A named field of a structural record type.
144///
145/// # Examples
146///
147/// ```
148/// use typeck_lang::{Field, TypeId, Types, Type};
149/// use intern_lang::Interner;
150///
151/// let mut names = Interner::new();
152/// let mut types = Types::new();
153/// let x = Field { name: names.intern("x"), ty: TypeId::UNIT };
154/// let rec = types.record(&[x]);
155/// assert_eq!(types.get(rec), Type::Record(&[x]));
156/// ```
157#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
158pub struct Field {
159    /// The field name.
160    pub name: Symbol,
161    /// The field type.
162    pub ty: TypeId,
163}
164
165/// A read-only view of one type node.
166///
167/// `#[non_exhaustive]`: later disciplines add forms.
168///
169/// # Examples
170///
171/// ```
172/// use typeck_lang::{Type, TypeId, Types};
173/// use hir_lang::Prim;
174///
175/// let mut types = Types::new();
176/// let arr = types.array(TypeId::prim(Prim::U8), 4);
177/// assert_eq!(types.get(arr), Type::Array { elem: TypeId::prim(Prim::U8), len: 4 });
178/// assert_eq!(types.get(TypeId::UNIT), Type::Tuple(&[]));
179/// ```
180#[derive(Clone, Copy, Debug, PartialEq, Eq)]
181#[non_exhaustive]
182pub enum Type<'a> {
183    /// `{error}`: already reported.
184    Error,
185    /// The dynamic type.
186    Any,
187    /// The type of diverging expressions.
188    Never,
189    /// The type of `null`.
190    Null,
191    /// A primitive.
192    Prim(Prim),
193    /// A tuple; the empty tuple is unit.
194    Tuple(&'a [TypeId]),
195    /// A fixed-length array.
196    Array {
197        /// The element type.
198        elem: TypeId,
199        /// The length.
200        len: u64,
201    },
202    /// An array whose length is not a known constant: a constant generic
203    /// parameter (`[T; N]` inside the item that declares `N`).
204    ParamArray {
205        /// The element type.
206        elem: TypeId,
207        /// The length: a [`Type::Param`] of a constant parameter.
208        len: TypeId,
209    },
210    /// A slice (an array of statically unknown length).
211    Slice(TypeId),
212    /// A reference.
213    Ref {
214        /// `&mut`.
215        mutable: bool,
216        /// The referenced type.
217        inner: TypeId,
218    },
219    /// A raw pointer.
220    Ptr {
221        /// `*mut`.
222        mutable: bool,
223        /// The pointed-to type.
224        inner: TypeId,
225    },
226    /// A function type: positional parameters, a result, declared effects.
227    Fn {
228        /// Parameter types, in order.
229        params: &'a [TypeId],
230        /// The return type.
231        ret: TypeId,
232        /// Declared effects (`ASYNC` makes a call produce an awaitable).
233        effects: Effects,
234    },
235    /// `T?`: a value of `T` or `null`.
236    Nullable(TypeId),
237    /// An ordered key-to-value map (map literals, named-argument rests).
238    Map {
239        /// The key type.
240        key: TypeId,
241        /// The value type.
242        value: TypeId,
243    },
244    /// An anonymous structural record, fields sorted by symbol.
245    Record(&'a [Field]),
246    /// A nominal type declared in this unit (a record, sum, or class item),
247    /// with its generic arguments.
248    Adt {
249        /// The declaring item.
250        item: ItemId,
251        /// Generic arguments, in the order of the item's type and constant
252        /// parameters (region parameters are erased).
253        args: &'a [TypeId],
254    },
255    /// A nominal type declared in another unit, with its generic arguments.
256    Foreign {
257        /// The definition.
258        def: DefId,
259        /// Generic arguments.
260        args: &'a [TypeId],
261    },
262    /// A host type named by an `Extern` resolution, with its generic
263    /// arguments (`Vec<i32>`).
264    Extern {
265        /// The host symbol.
266        name: Symbol,
267        /// Generic arguments.
268        args: &'a [TypeId],
269    },
270    /// A rigid generic parameter, inside the item that declares it.
271    Param(BinderId),
272    /// An `impl Trait` parameter type (`fn f(x: impl Show)`): an anonymous
273    /// generic parameter, named by the HIR type node that declares it.
274    ImplParam(TyId),
275    /// `Self` inside an interface: the implementing type, unknown here.
276    SelfOf(ItemId),
277    /// A union `A | B` (members in canonical order, at least two, none a
278    /// union or nullable).
279    Union(&'a [TypeId]),
280    /// An intersection `A & B` (members in canonical order, at least two).
281    Intersection(&'a [TypeId]),
282    /// An interface (trait) applied to arguments, as it appears in a bound
283    /// or inside `dyn`.
284    Trait {
285        /// The interface item.
286        item: ItemId,
287        /// Its generic arguments; inside `dyn`, followed by the values of
288        /// its associated types in declaration order.
289        args: &'a [TypeId],
290    },
291    /// A trait object `dyn A + B`: any value whose type implements every
292    /// listed interface, dispatched at run time.
293    Dyn(&'a [TypeId]),
294    /// An associated type of a generic parameter that no bound fixes:
295    /// `<T as Iterator>::Item`.
296    Projection {
297        /// The interface declaring the associated type.
298        interface: ItemId,
299        /// The associated type item.
300        assoc: ItemId,
301        /// The self type, then the interface's arguments.
302        args: &'a [TypeId],
303    },
304    /// The opaque result of a function returning `impl Trait`, applied to
305    /// the function's generic arguments. Callers see only its bounds.
306    Opaque {
307        /// The `impl` type node of the function's return type.
308        origin: TyId,
309        /// The function's generic arguments.
310        args: &'a [TypeId],
311    },
312    /// A constant generic argument (`Buf<4>`).
313    Const(i64),
314    /// The awaitable a call of an `ASYNC` function returns.
315    Async(TypeId),
316    /// The handle `spawn` returns; awaiting it yields the task's result.
317    Task(TypeId),
318    /// The generator a call of a `YIELD` function returns.
319    Generator {
320        /// The type of the yielded values.
321        item: TypeId,
322        /// An async generator (`ASYNC + YIELD`).
323        is_async: bool,
324    },
325}
326
327/// The node kinds, as stored.
328#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
329#[repr(u8)]
330pub(crate) enum Tag {
331    Error,
332    Any,
333    Never,
334    Null,
335    Tuple,
336    Prim,
337    Array,
338    Slice,
339    Ref,
340    Ptr,
341    Fn,
342    Nullable,
343    Map,
344    Record,
345    Adt,
346    Foreign,
347    Extern,
348    Param,
349    ImplParam,
350    SelfOf,
351    Union,
352    Inter,
353    Trait,
354    Dyn,
355    Proj,
356    Opaque,
357    Const,
358    Async,
359    Task,
360    Gen,
361    AsyncGen,
362    Var,
363}
364
365impl Tag {
366    /// Tags whose children are the pooled `kids` (and nothing else).
367    const fn pooled(self) -> bool {
368        matches!(
369            self,
370            Tag::Tuple
371                | Tag::Adt
372                | Tag::Foreign
373                | Tag::Extern
374                | Tag::Union
375                | Tag::Inter
376                | Tag::Trait
377                | Tag::Dyn
378                | Tag::Proj
379                | Tag::Opaque
380        )
381    }
382
383    /// Tags whose single child is stored in `x`.
384    const fn one_child(self) -> bool {
385        matches!(
386            self,
387            Tag::Slice
388                | Tag::Ref
389                | Tag::Ptr
390                | Tag::Nullable
391                | Tag::Async
392                | Tag::Task
393                | Tag::Gen
394                | Tag::AsyncGen
395        )
396    }
397
398    /// Placeholders: substituted when a generic item is instantiated.
399    pub(crate) const fn is_placeholder(self) -> bool {
400        matches!(self, Tag::Param | Tag::ImplParam | Tag::SelfOf)
401    }
402}
403
404/// One stored node. Scalars `x y z` are per-tag; `start`/`len` name a range of
405/// the children pool (pooled tags, `Fn` params) or the field pool (`Record`).
406#[derive(Clone, Copy, Debug, PartialEq, Eq)]
407pub(crate) struct Node {
408    pub(crate) tag: Tag,
409    /// Prim code, mutability, effect bits, variable class, or array kind.
410    pub(crate) small: u8,
411    /// The node mentions an inference variable somewhere below it.
412    pub(crate) has_var: bool,
413    /// The node mentions a placeholder (generic parameter, `impl`
414    /// parameter, interface `Self`) somewhere below it.
415    pub(crate) has_param: bool,
416    /// The node mentions a projection somewhere below it.
417    pub(crate) has_proj: bool,
418    pub(crate) x: u32,
419    pub(crate) y: u32,
420    pub(crate) z: u32,
421    pub(crate) start: u32,
422    pub(crate) len: u32,
423}
424
425impl Node {
426    const fn leaf(tag: Tag) -> Self {
427        Self {
428            tag,
429            small: 0,
430            has_var: false,
431            has_param: false,
432            has_proj: false,
433            x: 0,
434            y: 0,
435            z: 0,
436            start: 0,
437            len: 0,
438        }
439    }
440}
441
442/// A node being interned: its pooled children are passed as slices so a
443/// duplicate is found before anything is pushed.
444struct Key<'k> {
445    tag: Tag,
446    small: u8,
447    x: u32,
448    y: u32,
449    z: u32,
450    kids: &'k [TypeId],
451    fields: &'k [Field],
452}
453
454const EMPTY: u32 = u32::MAX;
455
456pub(crate) fn effects_bits(e: Effects) -> u8 {
457    let mut bits = 0u8;
458    for (i, flag) in [
459        Effects::THROWS,
460        Effects::ASYNC,
461        Effects::YIELD,
462        Effects::UNSAFE,
463    ]
464    .into_iter()
465    .enumerate()
466    {
467        if e.contains(flag) {
468            bits |= 1 << i;
469        }
470    }
471    bits
472}
473
474pub(crate) fn effects_from_bits(bits: u8) -> Effects {
475    let mut e = Effects::NONE;
476    for (i, flag) in [
477        Effects::THROWS,
478        Effects::ASYNC,
479        Effects::YIELD,
480        Effects::UNSAFE,
481    ]
482    .into_iter()
483    .enumerate()
484    {
485        if bits & (1 << i) != 0 {
486            e = e.union(flag);
487        }
488    }
489    e
490}
491
492fn raw_of(index: usize) -> u32 {
493    u32::try_from(index).unwrap_or(u32::MAX)
494}
495
496/// The store of interned type terms.
497///
498/// A [`Typed`](crate::Typed) result owns the store its side tables point into;
499/// [`Checker::types_mut`](crate::Checker::types_mut) exposes the store before a
500/// check, to build the types of host declarations.
501///
502/// # Examples
503///
504/// ```
505/// use typeck_lang::{Type, TypeId, Types};
506/// use hir_lang::{Effects, Prim};
507///
508/// let mut types = Types::new();
509/// let i32_ = TypeId::prim(Prim::I32);
510/// let f = types.func(&[i32_, i32_], i32_, Effects::NONE);
511/// match types.get(f) {
512///     Type::Fn { params, ret, .. } => {
513///         assert_eq!(params, &[i32_, i32_]);
514///         assert_eq!(ret, i32_);
515///     }
516///     other => panic!("{other:?}"),
517/// }
518/// ```
519#[derive(Clone, Debug, PartialEq, Eq)]
520pub struct Types {
521    nodes: Vec<Node>,
522    kids: Vec<TypeId>,
523    fields: Vec<Field>,
524    /// Open-addressing hash table of node indices; `EMPTY` marks a free slot.
525    table: Vec<u32>,
526    /// Interned nodes in `table` (variables are never interned).
527    interned: usize,
528    /// Display names of nominal items, generic parameters, and `impl` type
529    /// nodes, by index (`0` = unnamed). Not part of type identity.
530    item_names: Vec<u32>,
531    binder_names: Vec<u32>,
532    impl_names: Vec<u32>,
533}
534
535fn set_name(names: &mut Vec<u32>, index: usize, name: Symbol) {
536    if index >= names.len() {
537        names.resize(index + 1, 0);
538    }
539    if let Some(slot) = names.get_mut(index) {
540        *slot = name.as_u32();
541    }
542}
543
544impl Default for Types {
545    fn default() -> Self {
546        Self::new()
547    }
548}
549
550impl Types {
551    /// A store holding only the fixed types.
552    ///
553    /// # Examples
554    ///
555    /// ```
556    /// use typeck_lang::{Type, TypeId, Types};
557    ///
558    /// let types = Types::new();
559    /// assert_eq!(types.get(TypeId::NEVER), Type::Never);
560    /// ```
561    #[must_use]
562    pub fn new() -> Self {
563        let mut types = Self {
564            nodes: Vec::with_capacity(64),
565            kids: Vec::new(),
566            fields: Vec::new(),
567            table: alloc::vec![EMPTY; 64],
568            interned: 0,
569            item_names: Vec::new(),
570            binder_names: Vec::new(),
571            impl_names: Vec::new(),
572        };
573        // The fixed ids, in order: ERROR ANY NEVER NULL UNIT, then the prims.
574        for tag in [Tag::Error, Tag::Any, Tag::Never, Tag::Null] {
575            let _ = types.simple(tag, 0, 0, 0, 0);
576        }
577        let _ = types.tuple(&[]);
578        for p in PRIMS {
579            let _ = types.simple(Tag::Prim, prim_code(p), 0, 0, 0);
580        }
581        types
582    }
583
584    /// Returns the number of nodes in the store (variables included).
585    ///
586    /// # Examples
587    ///
588    /// ```
589    /// use typeck_lang::Types;
590    ///
591    /// let mut types = Types::new();
592    /// let before = types.len();
593    /// let _ = types.slice(typeck_lang::TypeId::UNIT);
594    /// assert_eq!(types.len(), before + 1);
595    /// ```
596    #[must_use]
597    pub fn len(&self) -> usize {
598        self.nodes.len()
599    }
600
601    /// Returns `true` if the store holds no nodes (never: the fixed types are
602    /// always present).
603    ///
604    /// # Examples
605    ///
606    /// ```
607    /// assert!(!typeck_lang::Types::new().is_empty());
608    /// ```
609    #[must_use]
610    pub fn is_empty(&self) -> bool {
611        self.nodes.is_empty()
612    }
613
614    /// Size of the store in elements, including pooled children: what the
615    /// type budget counts.
616    pub(crate) fn footprint(&self) -> usize {
617        self.nodes.len() + self.kids.len() + self.fields.len()
618    }
619
620    // ------------------------------------------------------------ reading
621
622    pub(crate) fn node(&self, id: TypeId) -> Node {
623        self.nodes
624            .get(id.index())
625            .copied()
626            .unwrap_or(Node::leaf(Tag::Error))
627    }
628
629    pub(crate) fn kids_of(&self, n: &Node) -> &[TypeId] {
630        if n.tag == Tag::Record {
631            return &[];
632        }
633        let start = n.start as usize;
634        self.kids
635            .get(start..start.saturating_add(n.len as usize))
636            .unwrap_or(&[])
637    }
638
639    pub(crate) fn fields_of(&self, n: &Node) -> &[Field] {
640        if n.tag != Tag::Record {
641            return &[];
642        }
643        let start = n.start as usize;
644        self.fields
645            .get(start..start.saturating_add(n.len as usize))
646            .unwrap_or(&[])
647    }
648
649    /// The pooled children of `id` (generic arguments, members, elements).
650    pub(crate) fn kids(&self, id: TypeId) -> &[TypeId] {
651        let n = self.node(id);
652        self.kids_of(&n)
653    }
654
655    /// Calls `f` on every direct child of `id` (element, parameter, field,
656    /// argument, inner type), in a fixed order.
657    pub(crate) fn for_each_child(&self, id: TypeId, mut f: impl FnMut(TypeId)) {
658        let n = self.node(id);
659        match n.tag {
660            t if t.pooled() => self.kids_of(&n).iter().for_each(|&k| f(k)),
661            Tag::Fn => {
662                self.kids_of(&n).iter().for_each(|&k| f(k));
663                f(TypeId(n.z));
664            }
665            Tag::Record => self.fields_of(&n).iter().for_each(|fl| f(fl.ty)),
666            t if t.one_child() => f(TypeId(n.x)),
667            Tag::Map | Tag::Array => {
668                f(TypeId(n.x));
669                f(TypeId(n.y));
670            }
671            _ => {}
672        }
673    }
674
675    /// Returns a view of a type. Ids from another store, and inference
676    /// variables (which never appear in results), read as [`Type::Error`].
677    ///
678    /// # Examples
679    ///
680    /// ```
681    /// use typeck_lang::{Type, TypeId, Types};
682    ///
683    /// let mut types = Types::new();
684    /// let n = types.nullable(TypeId::UNIT);
685    /// assert_eq!(types.get(n), Type::Nullable(TypeId::UNIT));
686    /// ```
687    #[must_use]
688    pub fn get(&self, id: TypeId) -> Type<'_> {
689        let n = self.node(id);
690        let kids = || self.kids_of_ref(id);
691        match n.tag {
692            Tag::Error | Tag::Var => Type::Error,
693            Tag::Any => Type::Any,
694            Tag::Never => Type::Never,
695            Tag::Null => Type::Null,
696            Tag::Prim => Type::Prim(
697                PRIMS
698                    .get(usize::from(n.small))
699                    .copied()
700                    .unwrap_or(Prim::Bool),
701            ),
702            Tag::Tuple => Type::Tuple(kids()),
703            Tag::Array => {
704                let len = self.node(TypeId(n.y));
705                if len.tag == Tag::Const {
706                    Type::Array {
707                        elem: TypeId(n.x),
708                        len: const_value(&len) as u64,
709                    }
710                } else {
711                    Type::ParamArray {
712                        elem: TypeId(n.x),
713                        len: TypeId(n.y),
714                    }
715                }
716            }
717            Tag::Slice => Type::Slice(TypeId(n.x)),
718            Tag::Ref => Type::Ref {
719                mutable: n.small != 0,
720                inner: TypeId(n.x),
721            },
722            Tag::Ptr => Type::Ptr {
723                mutable: n.small != 0,
724                inner: TypeId(n.x),
725            },
726            Tag::Fn => Type::Fn {
727                params: kids(),
728                ret: TypeId(n.z),
729                effects: effects_from_bits(n.small),
730            },
731            Tag::Nullable => Type::Nullable(TypeId(n.x)),
732            Tag::Map => Type::Map {
733                key: TypeId(n.x),
734                value: TypeId(n.y),
735            },
736            Tag::Record => Type::Record(self.fields_of_ref(id)),
737            Tag::Adt => ItemId::from_index(n.x as usize)
738                .map_or(Type::Error, |item| Type::Adt { item, args: kids() }),
739            Tag::Foreign => {
740                foreign_def(&n).map_or(Type::Error, |def| Type::Foreign { def, args: kids() })
741            }
742            Tag::Extern => Symbol::from_u32(n.x)
743                .map_or(Type::Error, |name| Type::Extern { name, args: kids() }),
744            Tag::Param => BinderId::from_index(n.x as usize).map_or(Type::Error, Type::Param),
745            Tag::ImplParam => TyId::from_index(n.x as usize).map_or(Type::Error, Type::ImplParam),
746            Tag::SelfOf => ItemId::from_index(n.x as usize).map_or(Type::Error, Type::SelfOf),
747            Tag::Union => Type::Union(kids()),
748            Tag::Inter => Type::Intersection(kids()),
749            Tag::Trait => ItemId::from_index(n.x as usize)
750                .map_or(Type::Error, |item| Type::Trait { item, args: kids() }),
751            Tag::Dyn => Type::Dyn(kids()),
752            Tag::Proj => match (
753                ItemId::from_index(n.x as usize),
754                ItemId::from_index(n.y as usize),
755            ) {
756                (Some(interface), Some(assoc)) => Type::Projection {
757                    interface,
758                    assoc,
759                    args: kids(),
760                },
761                _ => Type::Error,
762            },
763            Tag::Opaque => {
764                TyId::from_index(n.x as usize).map_or(Type::Error, |origin| Type::Opaque {
765                    origin,
766                    args: kids(),
767                })
768            }
769            Tag::Const => Type::Const(const_value(&n)),
770            Tag::Async => Type::Async(TypeId(n.x)),
771            Tag::Task => Type::Task(TypeId(n.x)),
772            Tag::Gen => Type::Generator {
773                item: TypeId(n.x),
774                is_async: false,
775            },
776            Tag::AsyncGen => Type::Generator {
777                item: TypeId(n.x),
778                is_async: true,
779            },
780        }
781    }
782
783    fn kids_of_ref(&self, id: TypeId) -> &[TypeId] {
784        let n = self.node(id);
785        self.kids_of(&n)
786    }
787
788    fn fields_of_ref(&self, id: TypeId) -> &[Field] {
789        let n = self.node(id);
790        self.fields_of(&n)
791    }
792
793    // ----------------------------------------------------------- interning
794
795    fn hash(key: &Key<'_>) -> u64 {
796        // FxHash-style mixing: fixed, platform-independent, so ids are
797        // deterministic everywhere.
798        const K: u64 = 0x51_7c_c1_b7_27_22_0a_95;
799        let mut h = 0u64;
800        let mut add = |v: u64| h = (h.rotate_left(5) ^ v).wrapping_mul(K);
801        add(key.tag as u64);
802        add(u64::from(key.small));
803        add(u64::from(key.x));
804        add(u64::from(key.y));
805        add(u64::from(key.z));
806        add(key.kids.len() as u64);
807        for k in key.kids {
808            add(u64::from(k.0));
809        }
810        add(key.fields.len() as u64);
811        for f in key.fields {
812            add(u64::from(f.name.as_u32()));
813            add(u64::from(f.ty.0));
814        }
815        h
816    }
817
818    fn matches(&self, n: &Node, key: &Key<'_>) -> bool {
819        n.tag == key.tag
820            && n.small == key.small
821            && n.x == key.x
822            && n.y == key.y
823            && n.z == key.z
824            && if n.tag == Tag::Record {
825                key.kids.is_empty() && self.fields_of(n) == key.fields
826            } else {
827                key.fields.is_empty() && self.kids_of(n) == key.kids
828            }
829    }
830
831    fn intern(&mut self, key: Key<'_>) -> TypeId {
832        let hash = Self::hash(&key);
833        let mask = self.table.len() - 1;
834        let mut slot = (hash as usize) & mask;
835        loop {
836            match self.table.get(slot).copied() {
837                Some(EMPTY) | None => break,
838                Some(existing) => {
839                    if let Some(n) = self.nodes.get(existing as usize) {
840                        if self.matches(n, &key) {
841                            return TypeId(existing);
842                        }
843                    }
844                }
845            }
846            slot = (slot + 1) & mask;
847        }
848        let id = self.push(&key);
849        if let Some(s) = self.table.get_mut(slot) {
850            *s = id.0;
851        }
852        self.interned += 1;
853        if self.interned * 2 > self.table.len() {
854            self.grow();
855        }
856        id
857    }
858
859    fn push(&mut self, key: &Key<'_>) -> TypeId {
860        let mut has_var = key.tag == Tag::Var;
861        let mut has_param = key.tag.is_placeholder();
862        let mut has_proj = key.tag == Tag::Proj;
863        let mut note = |n: Node| {
864            has_var |= n.has_var;
865            has_param |= n.has_param;
866            has_proj |= n.has_proj;
867        };
868        for &k in key.kids {
869            note(self.node(k));
870        }
871        for f in key.fields {
872            note(self.node(f.ty));
873        }
874        for raw in self.scalar_children(key) {
875            note(self.node(TypeId(raw)));
876        }
877        let (start, len) = if key.fields.is_empty() {
878            let start = self.kids.len();
879            self.kids.extend_from_slice(key.kids);
880            (start, key.kids.len())
881        } else {
882            let start = self.fields.len();
883            self.fields.extend_from_slice(key.fields);
884            (start, key.fields.len())
885        };
886        let id = TypeId(raw_of(self.nodes.len()));
887        self.nodes.push(Node {
888            tag: key.tag,
889            small: key.small,
890            has_var,
891            has_param,
892            has_proj,
893            x: key.x,
894            y: key.y,
895            z: key.z,
896            start: raw_of(start),
897            len: u32::try_from(len).unwrap_or(0),
898        });
899        id
900    }
901
902    /// The scalar-encoded children (`x`, `y`, `z` of the tags that store
903    /// type ids there).
904    fn scalar_children(&self, key: &Key<'_>) -> impl Iterator<Item = u32> {
905        let (a, b) = match key.tag {
906            t if t.one_child() => (Some(key.x), None),
907            Tag::Map | Tag::Array => (Some(key.x), Some(key.y)),
908            Tag::Fn => (Some(key.z), None),
909            _ => (None, None),
910        };
911        a.into_iter().chain(b)
912    }
913
914    fn grow(&mut self) {
915        let cap = self.table.len() * 2;
916        let mut table = alloc::vec![EMPTY; cap];
917        let mask = cap - 1;
918        for (i, n) in self.nodes.iter().enumerate() {
919            if n.tag == Tag::Var {
920                continue;
921            }
922            let key = Key {
923                tag: n.tag,
924                small: n.small,
925                x: n.x,
926                y: n.y,
927                z: n.z,
928                kids: self.kids_of(n),
929                fields: self.fields_of(n),
930            };
931            let mut slot = (Self::hash(&key) as usize) & mask;
932            while table.get(slot).is_some_and(|&s| s != EMPTY) {
933                slot = (slot + 1) & mask;
934            }
935            if let Some(s) = table.get_mut(slot) {
936                *s = raw_of(i);
937            }
938        }
939        self.table = table;
940    }
941
942    fn simple(&mut self, tag: Tag, small: u8, x: u32, y: u32, z: u32) -> TypeId {
943        self.intern(Key {
944            tag,
945            small,
946            x,
947            y,
948            z,
949            kids: &[],
950            fields: &[],
951        })
952    }
953
954    fn pooled(&mut self, tag: Tag, x: u32, y: u32, kids: &[TypeId]) -> TypeId {
955        self.intern(Key {
956            tag,
957            small: 0,
958            x,
959            y,
960            z: 0,
961            kids,
962            fields: &[],
963        })
964    }
965
966    /// A fresh inference variable of the given class (never interned: each
967    /// call is a distinct variable).
968    pub(crate) fn fresh_var(&mut self, class: u8) -> TypeId {
969        let n = raw_of(self.nodes.len());
970        self.push(&Key {
971            tag: Tag::Var,
972            small: class,
973            x: n,
974            y: 0,
975            z: 0,
976            kids: &[],
977            fields: &[],
978        })
979    }
980
981    // -------------------------------------------------------- constructors
982
983    /// A tuple type; `tuple(&[])` is [`TypeId::UNIT`].
984    ///
985    /// # Examples
986    ///
987    /// ```
988    /// use typeck_lang::{TypeId, Types};
989    ///
990    /// assert_eq!(Types::new().tuple(&[]), TypeId::UNIT);
991    /// ```
992    pub fn tuple(&mut self, elems: &[TypeId]) -> TypeId {
993        self.pooled(Tag::Tuple, 0, 0, elems)
994    }
995
996    /// A fixed-length array type.
997    ///
998    /// # Examples
999    ///
1000    /// ```
1001    /// use typeck_lang::{Type, TypeId, Types};
1002    /// use hir_lang::Prim;
1003    ///
1004    /// let mut types = Types::new();
1005    /// let a = types.array(TypeId::prim(Prim::I32), 3);
1006    /// assert_eq!(types.get(a), Type::Array { elem: TypeId::prim(Prim::I32), len: 3 });
1007    /// ```
1008    pub fn array(&mut self, elem: TypeId, len: u64) -> TypeId {
1009        let len = self.constant(len as i64);
1010        self.array_of(elem, len)
1011    }
1012
1013    /// `[elem; len]` with the length as a type: a constant, a constant
1014    /// parameter, or (while checking) a variable.
1015    pub(crate) fn array_of(&mut self, elem: TypeId, len: TypeId) -> TypeId {
1016        self.simple(Tag::Array, 0, elem.0, len.0, 0)
1017    }
1018
1019    /// A slice type.
1020    ///
1021    /// # Examples
1022    ///
1023    /// ```
1024    /// use typeck_lang::{Type, TypeId, Types};
1025    ///
1026    /// let mut types = Types::new();
1027    /// let s = types.slice(TypeId::UNIT);
1028    /// assert_eq!(types.get(s), Type::Slice(TypeId::UNIT));
1029    /// ```
1030    pub fn slice(&mut self, elem: TypeId) -> TypeId {
1031        self.simple(Tag::Slice, 0, elem.0, 0, 0)
1032    }
1033
1034    /// A reference type.
1035    ///
1036    /// # Examples
1037    ///
1038    /// ```
1039    /// use typeck_lang::{Type, TypeId, Types};
1040    ///
1041    /// let mut types = Types::new();
1042    /// let r = types.reference(true, TypeId::UNIT);
1043    /// assert_eq!(types.get(r), Type::Ref { mutable: true, inner: TypeId::UNIT });
1044    /// ```
1045    pub fn reference(&mut self, mutable: bool, inner: TypeId) -> TypeId {
1046        self.simple(Tag::Ref, u8::from(mutable), inner.0, 0, 0)
1047    }
1048
1049    /// A raw pointer type.
1050    ///
1051    /// # Examples
1052    ///
1053    /// ```
1054    /// use typeck_lang::{Type, TypeId, Types};
1055    ///
1056    /// let mut types = Types::new();
1057    /// let p = types.pointer(false, TypeId::UNIT);
1058    /// assert_eq!(types.get(p), Type::Ptr { mutable: false, inner: TypeId::UNIT });
1059    /// ```
1060    pub fn pointer(&mut self, mutable: bool, inner: TypeId) -> TypeId {
1061        self.simple(Tag::Ptr, u8::from(mutable), inner.0, 0, 0)
1062    }
1063
1064    /// A function type with positional parameters.
1065    ///
1066    /// # Examples
1067    ///
1068    /// ```
1069    /// use typeck_lang::{TypeId, Types};
1070    /// use hir_lang::Effects;
1071    ///
1072    /// let mut types = Types::new();
1073    /// let thunk = types.func(&[], TypeId::UNIT, Effects::NONE);
1074    /// assert_eq!(thunk, types.func(&[], TypeId::UNIT, Effects::NONE));
1075    /// ```
1076    pub fn func(&mut self, params: &[TypeId], ret: TypeId, effects: Effects) -> TypeId {
1077        self.intern(Key {
1078            tag: Tag::Fn,
1079            small: effects_bits(effects),
1080            x: 0,
1081            y: 0,
1082            z: ret.0,
1083            kids: params,
1084            fields: &[],
1085        })
1086    }
1087
1088    /// `T?`. Nullable types do not nest: `nullable(T?)` is `T?`, and
1089    /// `nullable(null)` is `null`.
1090    ///
1091    /// # Examples
1092    ///
1093    /// ```
1094    /// use typeck_lang::{TypeId, Types};
1095    ///
1096    /// let mut types = Types::new();
1097    /// let once = types.nullable(TypeId::UNIT);
1098    /// assert_eq!(types.nullable(once), once);
1099    /// ```
1100    pub fn nullable(&mut self, inner: TypeId) -> TypeId {
1101        match self.node(inner).tag {
1102            Tag::Nullable | Tag::Null | Tag::Error | Tag::Any => inner,
1103            Tag::Never => TypeId::NULL,
1104            _ => self.simple(Tag::Nullable, 0, inner.0, 0, 0),
1105        }
1106    }
1107
1108    /// A map type.
1109    ///
1110    /// # Examples
1111    ///
1112    /// ```
1113    /// use typeck_lang::{Type, TypeId, Types};
1114    /// use hir_lang::Prim;
1115    ///
1116    /// let mut types = Types::new();
1117    /// let m = types.map(TypeId::prim(Prim::Str), TypeId::prim(Prim::I64));
1118    /// assert!(matches!(types.get(m), Type::Map { .. }));
1119    /// ```
1120    pub fn map(&mut self, key: TypeId, value: TypeId) -> TypeId {
1121        self.simple(Tag::Map, 0, key.0, value.0, 0)
1122    }
1123
1124    /// A structural record type. Fields are sorted by symbol; a repeated name
1125    /// keeps its first type.
1126    ///
1127    /// # Examples
1128    ///
1129    /// ```
1130    /// use typeck_lang::{Field, TypeId, Types};
1131    /// use intern_lang::Interner;
1132    ///
1133    /// let mut names = Interner::new();
1134    /// let (a, b) = (names.intern("a"), names.intern("b"));
1135    /// let mut types = Types::new();
1136    /// let ab = types.record(&[Field { name: a, ty: TypeId::UNIT }, Field { name: b, ty: TypeId::NULL }]);
1137    /// let ba = types.record(&[Field { name: b, ty: TypeId::NULL }, Field { name: a, ty: TypeId::UNIT }]);
1138    /// assert_eq!(ab, ba);
1139    /// ```
1140    pub fn record(&mut self, fields: &[Field]) -> TypeId {
1141        let mut sorted: Vec<Field> = fields.to_vec();
1142        sorted.sort_by_key(|f| f.name);
1143        sorted.dedup_by_key(|f| f.name);
1144        self.record_sorted(&sorted)
1145    }
1146
1147    pub(crate) fn record_sorted(&mut self, sorted: &[Field]) -> TypeId {
1148        if sorted.is_empty() {
1149            // An empty field pool range is indistinguishable from "no
1150            // fields", which the interner keys as the kids pool; tag keeps
1151            // it distinct from unit.
1152            return self.simple(Tag::Record, 0, 0, 0, 0);
1153        }
1154        self.intern(Key {
1155            tag: Tag::Record,
1156            small: 0,
1157            x: 0,
1158            y: 0,
1159            z: 0,
1160            kids: &[],
1161            fields: sorted,
1162        })
1163    }
1164
1165    /// The nominal type of a record, sum, or class item of the checked unit,
1166    /// without generic arguments.
1167    ///
1168    /// # Examples
1169    ///
1170    /// ```
1171    /// use typeck_lang::{Type, Types};
1172    /// use hir_lang::ItemId;
1173    ///
1174    /// let mut types = Types::new();
1175    /// let item = ItemId::from_index(3).unwrap();
1176    /// let t = types.adt(item);
1177    /// assert_eq!(types.get(t), Type::Adt { item, args: &[] });
1178    /// ```
1179    pub fn adt(&mut self, item: ItemId) -> TypeId {
1180        self.adt_with(item, &[])
1181    }
1182
1183    /// The nominal type of a generic record, sum, or class item applied to
1184    /// `args`.
1185    ///
1186    /// # Examples
1187    ///
1188    /// ```
1189    /// use typeck_lang::{Type, TypeId, Types};
1190    /// use hir_lang::{ItemId, Prim};
1191    ///
1192    /// let mut types = Types::new();
1193    /// let item = ItemId::from_index(3).unwrap();
1194    /// let i32_ = TypeId::prim(Prim::I32);
1195    /// let t = types.adt_with(item, &[i32_]);
1196    /// assert_eq!(types.get(t), Type::Adt { item, args: &[i32_] });
1197    /// assert_ne!(t, types.adt(item));
1198    /// ```
1199    pub fn adt_with(&mut self, item: ItemId, args: &[TypeId]) -> TypeId {
1200        self.pooled(Tag::Adt, raw_of(item.index()), 0, args)
1201    }
1202
1203    /// Remembers an item's name, for display of its nominal type.
1204    pub(crate) fn name_item(&mut self, item: ItemId, name: Symbol) {
1205        set_name(&mut self.item_names, item.index(), name);
1206    }
1207
1208    /// Remembers a generic parameter's name, for display.
1209    pub(crate) fn name_binder(&mut self, binder: BinderId, name: Symbol) {
1210        set_name(&mut self.binder_names, binder.index(), name);
1211    }
1212
1213    /// Remembers the interface an `impl Trait` type node names first, for
1214    /// display.
1215    pub(crate) fn name_impl(&mut self, ty: TyId, name: Symbol) {
1216        set_name(&mut self.impl_names, ty.index(), name);
1217    }
1218
1219    /// The nominal type of another unit's definition, without generic
1220    /// arguments.
1221    ///
1222    /// # Examples
1223    ///
1224    /// ```
1225    /// use typeck_lang::{Type, Types};
1226    /// use hir_lang::{Def, DefId, ItemId, UnitId};
1227    ///
1228    /// let mut types = Types::new();
1229    /// let def = DefId::foreign(UnitId::new(2), Def::Item(ItemId::from_index(0).unwrap()));
1230    /// let t = types.foreign(def);
1231    /// assert_eq!(types.get(t), Type::Foreign { def, args: &[] });
1232    /// ```
1233    pub fn foreign(&mut self, def: DefId) -> TypeId {
1234        self.foreign_with(def, &[])
1235    }
1236
1237    /// The nominal type of another unit's generic definition applied to
1238    /// `args`.
1239    ///
1240    /// # Examples
1241    ///
1242    /// ```
1243    /// use typeck_lang::{Type, TypeId, Types};
1244    /// use hir_lang::{Def, DefId, ItemId, UnitId};
1245    ///
1246    /// let mut types = Types::new();
1247    /// let def = DefId::foreign(UnitId::new(2), Def::Item(ItemId::from_index(0).unwrap()));
1248    /// let t = types.foreign_with(def, &[TypeId::UNIT]);
1249    /// assert_eq!(types.get(t), Type::Foreign { def, args: &[TypeId::UNIT] });
1250    /// ```
1251    pub fn foreign_with(&mut self, def: DefId, args: &[TypeId]) -> TypeId {
1252        let (kind, index) = match def.def() {
1253            Def::Item(i) => (0, i.index()),
1254            Def::Variant(v) => (1, v.index()),
1255        };
1256        self.intern(Key {
1257            tag: Tag::Foreign,
1258            small: kind,
1259            x: def.unit().as_u32(),
1260            y: raw_of(index),
1261            z: 0,
1262            kids: args,
1263            fields: &[],
1264        })
1265    }
1266
1267    /// The nominal type of a host symbol (`Res::Extern`), without generic
1268    /// arguments.
1269    ///
1270    /// # Examples
1271    ///
1272    /// ```
1273    /// use typeck_lang::{Type, Types};
1274    /// use intern_lang::Interner;
1275    ///
1276    /// let mut names = Interner::new();
1277    /// let vec = names.intern("Vec");
1278    /// let mut types = Types::new();
1279    /// let t = types.external(vec);
1280    /// assert_eq!(types.get(t), Type::Extern { name: vec, args: &[] });
1281    /// ```
1282    pub fn external(&mut self, name: Symbol) -> TypeId {
1283        self.external_with(name, &[])
1284    }
1285
1286    /// A generic host type applied to `args` (`Vec<i32>`).
1287    ///
1288    /// # Examples
1289    ///
1290    /// ```
1291    /// use typeck_lang::{Type, TypeId, Types};
1292    /// use hir_lang::Prim;
1293    /// use intern_lang::Interner;
1294    ///
1295    /// let mut names = Interner::new();
1296    /// let vec = names.intern("Vec");
1297    /// let mut types = Types::new();
1298    /// let t = types.external_with(vec, &[TypeId::prim(Prim::I32)]);
1299    /// assert_eq!(types.display(t, &names).to_string(), "Vec<i32>");
1300    /// ```
1301    pub fn external_with(&mut self, name: Symbol, args: &[TypeId]) -> TypeId {
1302        self.pooled(Tag::Extern, name.as_u32(), 0, args)
1303    }
1304
1305    pub(crate) fn param(&mut self, binder: BinderId) -> TypeId {
1306        self.simple(Tag::Param, 0, raw_of(binder.index()), 0, 0)
1307    }
1308
1309    pub(crate) fn impl_param(&mut self, ty: TyId) -> TypeId {
1310        self.simple(Tag::ImplParam, 0, raw_of(ty.index()), 0, 0)
1311    }
1312
1313    pub(crate) fn self_of(&mut self, item: ItemId) -> TypeId {
1314        self.simple(Tag::SelfOf, 0, raw_of(item.index()), 0, 0)
1315    }
1316
1317    pub(crate) fn trait_ref(&mut self, item: ItemId, args: &[TypeId]) -> TypeId {
1318        self.pooled(Tag::Trait, raw_of(item.index()), 0, args)
1319    }
1320
1321    /// `dyn A + B` over trait nodes, sorted and deduplicated.
1322    pub(crate) fn dyn_of(&mut self, traits: &[TypeId]) -> TypeId {
1323        let mut sorted = traits.to_vec();
1324        sorted.sort_unstable();
1325        sorted.dedup();
1326        self.pooled(Tag::Dyn, 0, 0, &sorted)
1327    }
1328
1329    /// `<args[0] as interface<args[1..]>>::assoc`.
1330    pub(crate) fn projection(
1331        &mut self,
1332        interface: ItemId,
1333        assoc: ItemId,
1334        args: &[TypeId],
1335    ) -> TypeId {
1336        self.pooled(
1337            Tag::Proj,
1338            raw_of(interface.index()),
1339            raw_of(assoc.index()),
1340            args,
1341        )
1342    }
1343
1344    pub(crate) fn opaque(&mut self, origin: TyId, args: &[TypeId]) -> TypeId {
1345        self.pooled(Tag::Opaque, raw_of(origin.index()), 0, args)
1346    }
1347
1348    pub(crate) fn constant(&mut self, value: i64) -> TypeId {
1349        let bits = value as u64;
1350        self.simple(Tag::Const, 0, bits as u32, (bits >> 32) as u32, 0)
1351    }
1352
1353    /// A union of `members`, in canonical form: nested unions are
1354    /// flattened, `null` and nullable members make the whole union nullable
1355    /// (`A | B | null` is `(A | B)?`), members are sorted by id and
1356    /// deduplicated, a single member is itself, `!` members vanish (an empty
1357    /// union is `!`), and `any` or `{error}` absorb the union.
1358    ///
1359    /// # Examples
1360    ///
1361    /// ```
1362    /// use typeck_lang::{Type, TypeId, Types};
1363    /// use hir_lang::Prim;
1364    ///
1365    /// let mut types = Types::new();
1366    /// let (i, s) = (TypeId::prim(Prim::I64), TypeId::prim(Prim::Str));
1367    /// let a = types.union(&[s, i]);
1368    /// assert_eq!(a, types.union(&[i, s, i]));
1369    /// assert!(matches!(types.get(a), Type::Union(&[_, _])));
1370    /// let n = types.union(&[i, TypeId::NULL]);
1371    /// assert_eq!(n, types.nullable(i));
1372    /// ```
1373    pub fn union(&mut self, members: &[TypeId]) -> TypeId {
1374        let mut flat: Vec<TypeId> = Vec::with_capacity(members.len());
1375        let mut nullable = false;
1376        for &m in members {
1377            let n = self.node(m);
1378            match n.tag {
1379                Tag::Error | Tag::Any => return m,
1380                Tag::Never => {}
1381                Tag::Null => nullable = true,
1382                Tag::Nullable => {
1383                    nullable = true;
1384                    let inner = TypeId(n.x);
1385                    match self.node(inner).tag {
1386                        Tag::Union => flat.extend_from_slice(self.kids(inner)),
1387                        _ => flat.push(inner),
1388                    }
1389                }
1390                Tag::Union => flat.extend_from_slice(self.kids_of(&n)),
1391                _ => flat.push(m),
1392            }
1393        }
1394        flat.sort_unstable();
1395        flat.dedup();
1396        let body = match flat.as_slice() {
1397            [] => TypeId::NEVER,
1398            [one] => *one,
1399            _ => self.pooled(Tag::Union, 0, 0, &flat),
1400        };
1401        if nullable { self.nullable(body) } else { body }
1402    }
1403
1404    /// An intersection of `members`, in canonical form: nested intersections
1405    /// are flattened, members sorted by id and deduplicated, a single member
1406    /// is itself, and `!` or `{error}` absorb it.
1407    ///
1408    /// # Examples
1409    ///
1410    /// ```
1411    /// use typeck_lang::{Type, TypeId, Types};
1412    /// use hir_lang::ItemId;
1413    ///
1414    /// let mut types = Types::new();
1415    /// let a = types.adt(ItemId::from_index(1).unwrap());
1416    /// let b = types.adt(ItemId::from_index(2).unwrap());
1417    /// let ab = types.intersection(&[b, a]);
1418    /// assert_eq!(types.get(ab), Type::Intersection(&[a, b]));
1419    /// assert_eq!(types.intersection(&[a]), a);
1420    /// ```
1421    pub fn intersection(&mut self, members: &[TypeId]) -> TypeId {
1422        let mut flat: Vec<TypeId> = Vec::with_capacity(members.len());
1423        for &m in members {
1424            let n = self.node(m);
1425            match n.tag {
1426                Tag::Error | Tag::Never => return m,
1427                Tag::Inter => flat.extend_from_slice(self.kids_of(&n)),
1428                _ => flat.push(m),
1429            }
1430        }
1431        flat.sort_unstable();
1432        flat.dedup();
1433        match flat.as_slice() {
1434            [] => TypeId::ANY,
1435            [one] => *one,
1436            _ => self.pooled(Tag::Inter, 0, 0, &flat),
1437        }
1438    }
1439
1440    /// The awaitable a call of an `ASYNC` function returns.
1441    ///
1442    /// # Examples
1443    ///
1444    /// ```
1445    /// use typeck_lang::{Type, TypeId, Types};
1446    ///
1447    /// let mut types = Types::new();
1448    /// let a = types.awaitable(TypeId::UNIT);
1449    /// assert_eq!(types.get(a), Type::Async(TypeId::UNIT));
1450    /// ```
1451    pub fn awaitable(&mut self, result: TypeId) -> TypeId {
1452        self.simple(Tag::Async, 0, result.0, 0, 0)
1453    }
1454
1455    /// The handle `spawn` returns.
1456    ///
1457    /// # Examples
1458    ///
1459    /// ```
1460    /// use typeck_lang::{Type, TypeId, Types};
1461    ///
1462    /// let mut types = Types::new();
1463    /// let t = types.task(TypeId::UNIT);
1464    /// assert_eq!(types.get(t), Type::Task(TypeId::UNIT));
1465    /// ```
1466    pub fn task(&mut self, result: TypeId) -> TypeId {
1467        self.simple(Tag::Task, 0, result.0, 0, 0)
1468    }
1469
1470    /// A generator yielding `item`.
1471    ///
1472    /// # Examples
1473    ///
1474    /// ```
1475    /// use typeck_lang::{Type, TypeId, Types};
1476    ///
1477    /// let mut types = Types::new();
1478    /// let g = types.generator(TypeId::UNIT, false);
1479    /// assert_eq!(types.get(g), Type::Generator { item: TypeId::UNIT, is_async: false });
1480    /// ```
1481    pub fn generator(&mut self, item: TypeId, is_async: bool) -> TypeId {
1482        let tag = if is_async { Tag::AsyncGen } else { Tag::Gen };
1483        self.simple(tag, 0, item.0, 0, 0)
1484    }
1485
1486    /// Rebuilds node `id` with new children (same tag and scalars), in
1487    /// `for_each_child` order. Used by zonking and substitution; unions and
1488    /// intersections are brought back into canonical form.
1489    pub(crate) fn rebuild(&mut self, id: TypeId, kids: &[TypeId]) -> TypeId {
1490        let n = self.node(id);
1491        let first = |i: usize| kids.get(i).copied().unwrap_or(TypeId::ERROR);
1492        match n.tag {
1493            Tag::Union => self.union(kids),
1494            Tag::Inter => self.intersection(kids),
1495            Tag::Dyn => self.dyn_of(kids),
1496            t if t.pooled() => self.intern(Key {
1497                tag: t,
1498                small: n.small,
1499                x: n.x,
1500                y: n.y,
1501                z: n.z,
1502                kids,
1503                fields: &[],
1504            }),
1505            Tag::Fn => {
1506                let (params, ret) = kids.split_at(kids.len().saturating_sub(1));
1507                let ret = ret.first().copied().unwrap_or(TypeId::ERROR);
1508                self.intern(Key {
1509                    tag: Tag::Fn,
1510                    small: n.small,
1511                    x: 0,
1512                    y: 0,
1513                    z: ret.0,
1514                    kids: params,
1515                    fields: &[],
1516                })
1517            }
1518            Tag::Record => {
1519                let fields: Vec<Field> = self
1520                    .fields_of(&n)
1521                    .iter()
1522                    .zip(kids)
1523                    .map(|(f, &ty)| Field { name: f.name, ty })
1524                    .collect();
1525                self.record_sorted(&fields)
1526            }
1527            Tag::Array => self.array_of(first(0), first(1)),
1528            Tag::Nullable => self.nullable(first(0)),
1529            Tag::Map => self.map(first(0), first(1)),
1530            t if t.one_child() => self.simple(t, n.small, first(0).0, 0, 0),
1531            _ => id,
1532        }
1533    }
1534
1535    // ------------------------------------------------------------ display
1536
1537    /// Renders a type for messages, resolving names with `names`.
1538    ///
1539    /// Rendering is iterative and capped (about 200 characters, then `…`), so
1540    /// a type of any depth or sharing renders in bounded time.
1541    ///
1542    /// # Examples
1543    ///
1544    /// ```
1545    /// use typeck_lang::{TypeId, Types};
1546    /// use hir_lang::Prim;
1547    /// use intern_lang::Interner;
1548    ///
1549    /// let names = Interner::new();
1550    /// let mut types = Types::new();
1551    /// let t = types.tuple(&[TypeId::prim(Prim::I32), TypeId::prim(Prim::Bool)]);
1552    /// let s = types.slice(t);
1553    /// assert_eq!(types.display(s, &names).to_string(), "[(i32, bool)]");
1554    /// ```
1555    #[must_use]
1556    pub fn display<'a, L: Lookup>(&'a self, id: TypeId, names: &'a L) -> TypeDisplay<'a, L> {
1557        TypeDisplay {
1558            types: self,
1559            id,
1560            names,
1561        }
1562    }
1563
1564    pub(crate) fn render<L: Lookup>(&self, id: TypeId, names: &L, out: &mut String) {
1565        render(self, id, names, out);
1566    }
1567}
1568
1569fn const_value(n: &Node) -> i64 {
1570    (u64::from(n.x) | (u64::from(n.y) << 32)) as i64
1571}
1572
1573fn foreign_def(n: &Node) -> Option<DefId> {
1574    let unit = UnitId::new(n.x);
1575    let def = if n.small == 0 {
1576        Def::Item(ItemId::from_index(n.y as usize)?)
1577    } else {
1578        Def::Variant(VariantId::from_index(n.y as usize)?)
1579    };
1580    Some(DefId::foreign(unit, def))
1581}
1582
1583/// A type rendered for display; see [`Types::display`].
1584///
1585/// # Examples
1586///
1587/// ```
1588/// use typeck_lang::{TypeId, Types};
1589/// use intern_lang::Interner;
1590///
1591/// let names = Interner::new();
1592/// let types = Types::new();
1593/// assert_eq!(types.display(TypeId::ERROR, &names).to_string(), "{error}");
1594/// ```
1595pub struct TypeDisplay<'a, L> {
1596    types: &'a Types,
1597    id: TypeId,
1598    names: &'a L,
1599}
1600
1601impl<L: Lookup> fmt::Display for TypeDisplay<'_, L> {
1602    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1603        let mut out = String::new();
1604        render(self.types, self.id, self.names, &mut out);
1605        f.write_str(&out)
1606    }
1607}
1608
1609/// Output cap for one rendered type.
1610const RENDER_CAP: usize = 200;
1611
1612enum Piece {
1613    Ty(TypeId),
1614    Text(&'static str),
1615    Name(u32),
1616    Len(u64),
1617    Signed(i64),
1618}
1619
1620fn push_name<L: Lookup>(names: &L, raw: u32, out: &mut String) {
1621    let resolved = Symbol::from_u32(raw).and_then(|s| {
1622        names.resolve_with(s, |text| {
1623            out.push_str(text);
1624        })
1625    });
1626    if resolved.is_none() {
1627        out.push('#');
1628        push_u64(u64::from(raw), out);
1629    }
1630}
1631
1632fn push_u64(mut v: u64, out: &mut String) {
1633    let mut digits = [0u8; 20];
1634    let mut i = digits.len();
1635    loop {
1636        i -= 1;
1637        if let Some(d) = digits.get_mut(i) {
1638            *d = b'0' + (v % 10) as u8;
1639        }
1640        v /= 10;
1641        if v == 0 || i == 0 {
1642            break;
1643        }
1644    }
1645    for &d in digits.get(i..).unwrap_or(&[]) {
1646        out.push(char::from(d));
1647    }
1648}
1649
1650/// Pushes a display name from `table` (or `fallback#index`).
1651fn push_table_name<L: Lookup>(
1652    table: &[u32],
1653    index: u32,
1654    fallback: &str,
1655    names: &L,
1656    out: &mut String,
1657) {
1658    match table.get(index as usize).copied().filter(|&raw| raw != 0) {
1659        Some(raw) => push_name(names, raw, out),
1660        None => {
1661            out.push_str(fallback);
1662            push_u64(u64::from(index), out);
1663        }
1664    }
1665}
1666
1667/// Pushes `items` separated by `sep`, in reverse so they pop in order.
1668fn push_seq(stack: &mut Vec<Piece>, items: &[TypeId], sep: &'static str) {
1669    for (i, &k) in items.iter().enumerate().rev() {
1670        stack.push(Piece::Ty(k));
1671        if i > 0 {
1672            stack.push(Piece::Text(sep));
1673        }
1674    }
1675}
1676
1677/// Pushes `<args>` (nothing when empty).
1678fn push_args(stack: &mut Vec<Piece>, args: &[TypeId]) {
1679    if !args.is_empty() {
1680        stack.push(Piece::Text(">"));
1681        push_seq(stack, args, ", ");
1682        stack.push(Piece::Text("<"));
1683    }
1684}
1685
1686#[allow(clippy::too_many_lines)]
1687fn render<L: Lookup>(types: &Types, id: TypeId, names: &L, out: &mut String) {
1688    let mut stack = alloc::vec![Piece::Ty(id)];
1689    while let Some(piece) = stack.pop() {
1690        if out.len() > RENDER_CAP {
1691            out.push('…');
1692            return;
1693        }
1694        let id = match piece {
1695            Piece::Text(t) => {
1696                out.push_str(t);
1697                continue;
1698            }
1699            Piece::Name(raw) => {
1700                push_name(names, raw, out);
1701                continue;
1702            }
1703            Piece::Len(len) => {
1704                push_u64(len, out);
1705                continue;
1706            }
1707            Piece::Signed(v) => {
1708                if v < 0 {
1709                    out.push('-');
1710                }
1711                push_u64(v.unsigned_abs(), out);
1712                continue;
1713            }
1714            Piece::Ty(id) => id,
1715        };
1716        let n = types.node(id);
1717        let kids = types.kids_of(&n);
1718        match n.tag {
1719            Tag::Error => out.push_str("{error}"),
1720            Tag::Var => out.push_str(match n.small {
1721                1 => "{integer}",
1722                2 => "{float}",
1723                _ => "_",
1724            }),
1725            Tag::Any => out.push_str("any"),
1726            Tag::Never => out.push('!'),
1727            Tag::Null => out.push_str("null"),
1728            Tag::Prim => out.push_str(
1729                PRIMS
1730                    .get(usize::from(n.small))
1731                    .copied()
1732                    .unwrap_or(Prim::Bool)
1733                    .name(),
1734            ),
1735            Tag::Tuple => {
1736                stack.push(Piece::Text(")"));
1737                if kids.len() == 1 {
1738                    stack.push(Piece::Text(","));
1739                }
1740                push_seq(&mut stack, kids, ", ");
1741                stack.push(Piece::Text("("));
1742            }
1743            Tag::Array => {
1744                stack.push(Piece::Text("]"));
1745                let len = types.node(TypeId(n.y));
1746                if len.tag == Tag::Const {
1747                    stack.push(Piece::Len(const_value(&len) as u64));
1748                } else {
1749                    stack.push(Piece::Ty(TypeId(n.y)));
1750                }
1751                stack.push(Piece::Text("; "));
1752                stack.push(Piece::Ty(TypeId(n.x)));
1753                stack.push(Piece::Text("["));
1754            }
1755            Tag::Slice => {
1756                stack.push(Piece::Text("]"));
1757                stack.push(Piece::Ty(TypeId(n.x)));
1758                stack.push(Piece::Text("["));
1759            }
1760            Tag::Ref | Tag::Ptr => {
1761                stack.push(Piece::Ty(TypeId(n.x)));
1762                stack.push(Piece::Text(match (n.tag, n.small != 0) {
1763                    (Tag::Ref, false) => "&",
1764                    (Tag::Ref, true) => "&mut ",
1765                    (_, false) => "*const ",
1766                    (_, true) => "*mut ",
1767                }));
1768            }
1769            Tag::Fn => {
1770                stack.push(Piece::Ty(TypeId(n.z)));
1771                stack.push(Piece::Text(") -> "));
1772                push_seq(&mut stack, kids, ", ");
1773                stack.push(Piece::Text("fn("));
1774                if n.small & 0b10 != 0 {
1775                    stack.push(Piece::Text("async "));
1776                }
1777            }
1778            Tag::Nullable => {
1779                stack.push(Piece::Text("?"));
1780                let inner = TypeId(n.x);
1781                let compound = matches!(types.node(inner).tag, Tag::Union | Tag::Inter | Tag::Fn);
1782                if compound {
1783                    stack.push(Piece::Text(")"));
1784                }
1785                stack.push(Piece::Ty(inner));
1786                if compound {
1787                    stack.push(Piece::Text("("));
1788                }
1789            }
1790            Tag::Map => {
1791                stack.push(Piece::Text("}"));
1792                stack.push(Piece::Ty(TypeId(n.y)));
1793                stack.push(Piece::Text(": "));
1794                stack.push(Piece::Ty(TypeId(n.x)));
1795                stack.push(Piece::Text("{"));
1796            }
1797            Tag::Record => {
1798                stack.push(Piece::Text(" }"));
1799                let fields = types.fields_of(&n);
1800                for (i, fl) in fields.iter().enumerate().rev() {
1801                    stack.push(Piece::Ty(fl.ty));
1802                    stack.push(Piece::Text(": "));
1803                    stack.push(Piece::Name(fl.name.as_u32()));
1804                    if i > 0 {
1805                        stack.push(Piece::Text(", "));
1806                    }
1807                }
1808                stack.push(Piece::Text("{ "));
1809            }
1810            Tag::Adt => {
1811                push_args(&mut stack, kids);
1812                push_table_name(&types.item_names, n.x, "item#", names, out);
1813            }
1814            Tag::Trait => {
1815                // Inside `dyn`, the associated-type values follow the
1816                // arguments; they are shown as arguments too.
1817                push_args(&mut stack, kids);
1818                push_table_name(&types.item_names, n.x, "item#", names, out);
1819            }
1820            Tag::Param => push_table_name(&types.binder_names, n.x, "param#", names, out),
1821            Tag::ImplParam => {
1822                out.push_str("impl ");
1823                push_table_name(&types.impl_names, n.x, "#", names, out);
1824            }
1825            Tag::Opaque => {
1826                out.push_str("impl ");
1827                push_table_name(&types.impl_names, n.x, "#", names, out);
1828            }
1829            Tag::Foreign => {
1830                push_args(&mut stack, kids);
1831                out.push('u');
1832                push_u64(u64::from(n.x), out);
1833                out.push_str(if n.small == 0 { ":item#" } else { ":variant#" });
1834                push_u64(u64::from(n.y), out);
1835            }
1836            Tag::Extern => {
1837                push_args(&mut stack, kids);
1838                push_name(names, n.x, out);
1839            }
1840            Tag::SelfOf => out.push_str("Self"),
1841            Tag::Union => push_seq(&mut stack, kids, " | "),
1842            Tag::Inter => push_seq(&mut stack, kids, " & "),
1843            Tag::Dyn => {
1844                push_seq(&mut stack, kids, " + ");
1845                stack.push(Piece::Text("dyn "));
1846            }
1847            Tag::Proj => {
1848                // `<T as Tr<A>>::Item`
1849                stack.push(Piece::Name(
1850                    types.item_names.get(n.y as usize).copied().unwrap_or(0),
1851                ));
1852                stack.push(Piece::Text(">::"));
1853                push_args(&mut stack, kids.get(1..).unwrap_or(&[]));
1854                stack.push(Piece::Name(
1855                    types.item_names.get(n.x as usize).copied().unwrap_or(0),
1856                ));
1857                stack.push(Piece::Text(" as "));
1858                stack.push(Piece::Ty(kids.first().copied().unwrap_or(TypeId::ERROR)));
1859                stack.push(Piece::Text("<"));
1860            }
1861            Tag::Const => stack.push(Piece::Signed(const_value(&n))),
1862            Tag::Async | Tag::Task | Tag::Gen | Tag::AsyncGen => {
1863                stack.push(Piece::Text(">"));
1864                stack.push(Piece::Ty(TypeId(n.x)));
1865                stack.push(Piece::Text(match n.tag {
1866                    Tag::Async => "async<",
1867                    Tag::Task => "task<",
1868                    Tag::Gen => "generator<",
1869                    _ => "async-generator<",
1870                }));
1871            }
1872        }
1873    }
1874}
1875
1876#[cfg(test)]
1877mod tests {
1878    use alloc::string::ToString;
1879
1880    use hir_lang::{BinderId, Def, DefId, Effects, ItemId, Prim, UnitId, VariantId};
1881    use intern_lang::Interner;
1882
1883    use super::*;
1884
1885    fn item(i: usize) -> ItemId {
1886        ItemId::from_index(i).unwrap_or_else(|| item(0))
1887    }
1888
1889    #[test]
1890    fn test_fixed_ids_are_the_builtins() {
1891        let t = Types::new();
1892        assert_eq!(t.get(TypeId::ERROR), Type::Error);
1893        assert_eq!(t.get(TypeId::ANY), Type::Any);
1894        assert_eq!(t.get(TypeId::NEVER), Type::Never);
1895        assert_eq!(t.get(TypeId::NULL), Type::Null);
1896        assert_eq!(t.get(TypeId::UNIT), Type::Tuple(&[]));
1897        for p in PRIMS {
1898            assert_eq!(t.get(TypeId::prim(p)), Type::Prim(p));
1899        }
1900        assert_eq!(t.len(), 20);
1901    }
1902
1903    #[test]
1904    fn test_hash_consing_survives_table_growth() {
1905        let mut t = Types::new();
1906        let mut ids = alloc::vec::Vec::new();
1907        let mut cur = TypeId::UNIT;
1908        for _ in 0..5_000 {
1909            cur = t.slice(cur);
1910            ids.push(cur);
1911        }
1912        // Rebuilding every type yields the same ids, after many regrowths.
1913        let mut again = TypeId::UNIT;
1914        for &id in &ids {
1915            again = t.slice(again);
1916            assert_eq!(again, id);
1917        }
1918        assert_eq!(t.len(), 20 + 5_000);
1919    }
1920
1921    #[test]
1922    fn test_distinct_shapes_are_distinct() {
1923        let mut t = Types::new();
1924        let i32_ = TypeId::prim(Prim::I32);
1925        let a = t.array(i32_, 3);
1926        let b = t.array(i32_, 4);
1927        let c = t.array(i32_, 3 + (1 << 32));
1928        assert_ne!(a, b);
1929        assert_ne!(a, c);
1930        assert_eq!(
1931            t.get(c),
1932            Type::Array {
1933                elem: i32_,
1934                len: 3 + (1 << 32)
1935            }
1936        );
1937        let r = t.reference(false, i32_);
1938        let m = t.reference(true, i32_);
1939        let p = t.pointer(false, i32_);
1940        assert_ne!(r, m);
1941        assert_ne!(r, p);
1942        let f = t.func(&[i32_], i32_, Effects::NONE);
1943        let g = t.func(&[i32_], i32_, Effects::ASYNC);
1944        assert_ne!(f, g);
1945        assert_eq!(
1946            t.get(g),
1947            Type::Fn {
1948                params: &[i32_],
1949                ret: i32_,
1950                effects: Effects::ASYNC
1951            }
1952        );
1953        let empty_record = t.record(&[]);
1954        assert_ne!(empty_record, TypeId::UNIT);
1955        assert_eq!(t.get(empty_record), Type::Record(&[]));
1956    }
1957
1958    #[test]
1959    fn test_effect_bits_round_trip() {
1960        for e in [
1961            Effects::NONE,
1962            Effects::THROWS,
1963            Effects::ASYNC.union(Effects::YIELD),
1964            Effects::UNSAFE,
1965        ] {
1966            assert_eq!(effects_from_bits(effects_bits(e)), e);
1967        }
1968    }
1969
1970    #[test]
1971    fn test_nominal_and_host_types() {
1972        let mut t = Types::new();
1973        let it = item(7);
1974        let a = t.adt(it);
1975        assert_eq!(
1976            t.get(a),
1977            Type::Adt {
1978                item: it,
1979                args: &[]
1980            }
1981        );
1982        assert_eq!(a, t.adt(it));
1983        let def = DefId::foreign(UnitId::new(3), Def::Item(it));
1984        let f = t.foreign(def);
1985        assert_eq!(t.get(f), Type::Foreign { def, args: &[] });
1986        let v = VariantId::from_index(2)
1987            .map(Def::Variant)
1988            .unwrap_or(Def::Item(it));
1989        let fv = t.foreign(DefId::foreign(UnitId::new(3), v));
1990        assert_ne!(f, fv);
1991        if let Some(b) = BinderId::from_index(1) {
1992            let p = t.param(b);
1993            assert_eq!(t.get(p), Type::Param(b));
1994        }
1995        let s = t.self_of(it);
1996        assert_eq!(t.get(s), Type::SelfOf(it));
1997        let g = t.generator(TypeId::UNIT, true);
1998        assert_eq!(
1999            t.get(g),
2000            Type::Generator {
2001                item: TypeId::UNIT,
2002                is_async: true
2003            }
2004        );
2005    }
2006
2007    #[test]
2008    fn test_rendering_covers_every_form() {
2009        let mut names = Interner::new();
2010        let x = names.intern("x");
2011        let vec = names.intern("Vec");
2012        let mut t = Types::new();
2013        let i32_ = TypeId::prim(Prim::I32);
2014        let cases: alloc::vec::Vec<(TypeId, &str)> = alloc::vec![
2015            (TypeId::ERROR, "{error}"),
2016            (TypeId::ANY, "any"),
2017            (TypeId::NEVER, "!"),
2018            (TypeId::NULL, "null"),
2019            (TypeId::UNIT, "()"),
2020            (t.tuple(&[i32_]), "(i32,)"),
2021            (t.tuple(&[i32_, i32_]), "(i32, i32)"),
2022            (t.array(i32_, 4), "[i32; 4]"),
2023            (t.slice(i32_), "[i32]"),
2024            (t.reference(false, i32_), "&i32"),
2025            (t.reference(true, i32_), "&mut i32"),
2026            (t.pointer(false, i32_), "*const i32"),
2027            (t.pointer(true, i32_), "*mut i32"),
2028            (
2029                t.func(&[i32_], TypeId::UNIT, Effects::ASYNC),
2030                "async fn(i32) -> ()"
2031            ),
2032            (t.nullable(i32_), "i32?"),
2033            (t.map(i32_, i32_), "{i32: i32}"),
2034            (t.record(&[Field { name: x, ty: i32_ }]), "{ x: i32 }"),
2035            (t.external(vec), "Vec"),
2036            (t.external_with(vec, &[i32_]), "Vec<i32>"),
2037            (t.awaitable(i32_), "async<i32>"),
2038            (t.task(i32_), "task<i32>"),
2039            (t.generator(i32_, false), "generator<i32>"),
2040        ];
2041        for (id, want) in cases {
2042            assert_eq!(t.display(id, &names).to_string(), want);
2043        }
2044        let it = item(4);
2045        let adt = t.adt(it);
2046        assert_eq!(t.display(adt, &names).to_string(), "item#4");
2047        t.name_item(it, x);
2048        assert_eq!(t.display(adt, &names).to_string(), "x");
2049        let args = t.adt_with(it, &[i32_, TypeId::UNIT]);
2050        assert_eq!(t.display(args, &names).to_string(), "x<i32, ()>");
2051        let u = t.union(&[i32_, TypeId::prim(Prim::Str)]);
2052        assert_eq!(t.display(u, &names).to_string(), "i32 | str");
2053        let nu = t.nullable(u);
2054        assert_eq!(t.display(nu, &names).to_string(), "(i32 | str)?");
2055        let k = t.constant(-4);
2056        assert_eq!(t.display(k, &names).to_string(), "-4");
2057    }
2058
2059    #[test]
2060    fn test_union_canonical_form() {
2061        let mut t = Types::new();
2062        let (a, b, c) = (
2063            TypeId::prim(Prim::I32),
2064            TypeId::prim(Prim::Str),
2065            TypeId::prim(Prim::Bool),
2066        );
2067        let ab = t.union(&[b, a]);
2068        let abc = t.union(&[ab, c]);
2069        assert_eq!(abc, t.union(&[c, b, a, a]));
2070        assert_eq!(t.union(&[a]), a);
2071        assert_eq!(t.union(&[]), TypeId::NEVER);
2072        assert_eq!(t.union(&[TypeId::NEVER, a]), a);
2073        assert_eq!(t.union(&[a, TypeId::ANY]), TypeId::ANY);
2074        let na = t.nullable(a);
2075        let n = t.union(&[na, b]);
2076        let ab2 = t.union(&[a, b]);
2077        assert_eq!(t.get(n), Type::Nullable(ab2));
2078        assert_eq!(t.union(&[TypeId::NULL]), TypeId::NULL);
2079        let i1 = t.intersection(&[a, b]);
2080        let i2 = t.intersection(&[i1, c]);
2081        assert_eq!(i2, t.intersection(&[c, b, a]));
2082        assert_eq!(t.intersection(&[a, TypeId::NEVER]), TypeId::NEVER);
2083    }
2084
2085    #[test]
2086    fn test_rendering_is_capped() {
2087        let names = Interner::new();
2088        let mut t = Types::new();
2089        let mut cur = TypeId::prim(Prim::I32);
2090        for _ in 0..64 {
2091            cur = t.tuple(&[cur, cur]);
2092        }
2093        let s = t.display(cur, &names).to_string();
2094        assert!(s.ends_with('\u{2026}'));
2095        assert!(s.len() < 300);
2096    }
2097}