Skip to main content

typeck_lang/
typed.rs

1//! The result of a check: side tables keyed by HIR ids, and diagnostics.
2
3use alloc::{string::String, vec::Vec};
4
5use core::fmt::Write as _;
6
7use hir_lang::{BinderId, Def, ExprId, ItemId, PatId, PathId, Prim, Symbol, TyId, VariantId};
8use intern_lang::Lookup;
9
10use crate::{
11    diag::{Diagnostic, DiagnosticKind, Severity},
12    mono::{Dispatch, Instantiation, MonoPlan},
13    profile::Profile,
14    types::{TypeDisplay, TypeId, Types},
15};
16
17/// An implicit conversion the checker accepted where a value meets a
18/// context of another type. Lowering must materialise it.
19///
20/// # Examples
21///
22/// ```
23/// use typeck_lang::Coercion;
24///
25/// assert_ne!(Coercion::Widen, Coercion::ToAny);
26/// ```
27#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
28#[non_exhaustive]
29pub enum Coercion {
30    /// A lossless numeric widening (`i32` to `i64`, `i32` to `f64`).
31    Widen,
32    /// A value boxed into the dynamic type `any`.
33    ToAny,
34    /// `T` used as `T?`.
35    WrapNullable,
36    /// `null` used as a nullable or (without null safety) reference type.
37    Null,
38    /// A subclass used as one of its base classes.
39    Subclass,
40    /// A structural record used as a record with fewer fields.
41    RecordWidth,
42    /// An array used as a slice (`[T; n]` to `[T]`, also behind `&`).
43    Unsize,
44    /// `&mut T` used as `&T`.
45    Reborrow,
46    /// A method receiver borrowed automatically (`x.m()` with `fn m(&self)`).
47    AutoRef,
48    /// A method receiver dereferenced automatically.
49    AutoDeref,
50    /// A value used as a union containing its type.
51    ToUnion,
52    /// A value of an intersection type used as one of its members.
53    FromIntersection,
54    /// A value used as a `dyn` interface type (or a `dyn` type used as one
55    /// with fewer interfaces): lowering builds the vtable.
56    ToDyn,
57    /// A `?` failure converted to the enclosing function's failure type
58    /// through [`TryHook`](crate::TryHook)'s conversion interface.
59    ErrorConvert,
60}
61
62/// How an OPS operation was resolved by its operand types (HIR leaves this
63/// open: the same `add` is integer, IEEE, or string concatenation).
64///
65/// # Examples
66///
67/// ```
68/// use hir_lang::Prim;
69/// use typeck_lang::OpClass;
70///
71/// assert_ne!(OpClass::Int(Prim::I32), OpClass::Float(Prim::F64));
72/// ```
73#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
74#[non_exhaustive]
75pub enum OpClass {
76    /// Integer semantics (OPS §3) on this type.
77    Int(Prim),
78    /// IEEE semantics (OPS §4) on this type.
79    Float(Prim),
80    /// Logical operations on `bool`.
81    Bool,
82    /// Comparisons of `char`.
83    Char,
84    /// String comparison or concatenation (a runtime-library operation).
85    Str,
86    /// `x == null` / `x != null`.
87    NullCheck,
88    /// Dispatched at run time on dynamic values.
89    Dynamic,
90}
91
92/// Work counters of a finished check.
93///
94/// # Examples
95///
96/// ```
97/// use hir_lang::Builder;
98/// use typeck_lang::{check, Profile};
99///
100/// let mut b = Builder::new();
101/// let root = b.module(None, &[]);
102/// let hir = b.finish(root)?;
103/// let typed = check(&hir, &Profile::static_explicit()).unwrap();
104/// assert!(typed.stats().steps < 100);
105/// # Ok::<(), hir_lang::HirError>(())
106/// ```
107#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
108pub struct Stats {
109    /// Steps charged against [`Budget::steps`](crate::Budget::steps).
110    pub steps: u64,
111    /// Final type-store size (nodes plus pooled children).
112    pub type_nodes: usize,
113}
114
115pub(crate) const NONE: u32 = u32::MAX;
116
117/// One node of a stored witness (a value no arm matches), in preorder.
118#[derive(Clone, Copy, Debug, PartialEq, Eq)]
119pub(crate) struct WNode {
120    pub(crate) kind: WKind,
121    pub(crate) arity: u32,
122    /// Field names of a named-field record or variant: a range of
123    /// `Typed::wsyms`.
124    pub(crate) names: (u32, u32),
125}
126
127#[derive(Clone, Copy, Debug, PartialEq, Eq)]
128pub(crate) enum WKind {
129    Wild,
130    Null,
131    /// A present value of a nullable type.
132    Value,
133    /// A union member (matched by a type test).
134    Member(TypeId),
135    Variant(VariantId),
136    /// A record item's constructor.
137    Item(ItemId),
138    Tuple,
139    Ref,
140    Bool(bool),
141    Int(i128, i128),
142    Char(char, char),
143    Slice(u32),
144    SliceRest(u32, u32),
145}
146
147/// The result of checking one HIR unit.
148///
149/// Every live expression, pattern, and bound binder has a type (dense side
150/// tables, indexed by HIR id); a type is [`TypeId::ERROR`] where something
151/// was reported. Dead nodes (unreachable error forms left by lenient
152/// validation) have none.
153///
154/// # Examples
155///
156/// ```
157/// use hir_lang::{Builder, Name, OpKind, Prim};
158/// use intern_lang::Interner;
159/// use typeck_lang::{check, Profile, TypeId};
160///
161/// let mut names = Interner::new();
162/// let mut b = Builder::new();
163/// let (one, two) = (b.int(1), b.int(2));
164/// let sum = b.op(OpKind::Add, &[one, two]);
165/// let body = b.block(&[], Some(sum));
166/// let main = b.func(Name::new(names.intern("main")), &[], body);
167/// let root = b.module(None, &[main]);
168/// let hir = b.finish(root)?;
169///
170/// // `main` has no declared return type: its body must be unit.
171/// let typed = check(&hir, &Profile::static_explicit()).unwrap();
172/// assert_eq!(typed.expr(sum), Some(TypeId::prim(Prim::I64)));
173/// assert_eq!(typed.diagnostics().len(), 1);
174/// assert_eq!(
175///     typed.message(&typed.diagnostics()[0], &names),
176///     "mismatched types: expected `()`, found `i64`",
177/// );
178/// # Ok::<(), hir_lang::HirError>(())
179/// ```
180#[derive(Clone, Debug, PartialEq, Eq)]
181pub struct Typed {
182    pub(crate) types: Types,
183    pub(crate) exprs: Vec<u32>,
184    pub(crate) pats: Vec<u32>,
185    pub(crate) binders: Vec<u32>,
186    pub(crate) path_defs: Vec<(PathId, Def)>,
187    pub(crate) methods: Vec<(ExprId, ItemId)>,
188    pub(crate) coercions: Vec<(ExprId, Coercion, TypeId)>,
189    pub(crate) op_classes: Vec<(ExprId, OpClass)>,
190    /// Uses of generic items: (expression, item, args range, dispatch).
191    pub(crate) insts: Vec<(ExprId, ItemId, u32, u32, Dispatch)>,
192    pub(crate) inst_args: Vec<TypeId>,
193    pub(crate) mono: MonoPlan,
194    /// Hidden types of `impl Trait` results, by the `impl` type node.
195    pub(crate) opaque: Vec<(TyId, TypeId)>,
196    /// Witnesses of non-exhaustive matches: (match, node range).
197    pub(crate) witnesses: Vec<(ExprId, u32, u32)>,
198    pub(crate) wnodes: Vec<WNode>,
199    pub(crate) wsyms: Vec<Symbol>,
200    /// Names of variants and record items, for witnesses.
201    pub(crate) wnames: Vec<(u32, Symbol)>,
202    pub(crate) witems: Vec<(u32, Symbol)>,
203    pub(crate) diagnostics: Vec<Diagnostic>,
204    pub(crate) profile: Profile,
205    pub(crate) stats: Stats,
206}
207
208fn lookup<K: Ord + Copy, V: Copy>(table: &[(K, V)], key: K) -> Option<V> {
209    table
210        .binary_search_by(|(k, _)| k.cmp(&key))
211        .ok()
212        .and_then(|i| table.get(i))
213        .map(|&(_, v)| v)
214}
215
216fn dense(table: &[u32], index: usize) -> Option<TypeId> {
217    table
218        .get(index)
219        .copied()
220        .filter(|&raw| raw != NONE)
221        .map(TypeId::from_raw)
222}
223
224impl Typed {
225    /// The type of a live expression.
226    ///
227    /// # Examples
228    ///
229    /// ```
230    /// use hir_lang::{Builder, Lit, Name, Prim};
231    /// use intern_lang::Interner;
232    /// use typeck_lang::{check, Profile, TypeId};
233    ///
234    /// let mut names = Interner::new();
235    /// let mut b = Builder::new();
236    /// let c = b.lit(Lit::Char('x'));
237    /// let s = b.expr_stmt(c);
238    /// let body = b.block(&[s], None);
239    /// let main = b.func(Name::new(names.intern("main")), &[], body);
240    /// let root = b.module(None, &[main]);
241    /// let hir = b.finish(root)?;
242    /// let typed = check(&hir, &Profile::static_explicit()).unwrap();
243    /// assert_eq!(typed.expr(c), Some(TypeId::prim(Prim::Char)));
244    /// # Ok::<(), hir_lang::HirError>(())
245    /// ```
246    #[must_use]
247    pub fn expr(&self, id: ExprId) -> Option<TypeId> {
248        dense(&self.exprs, id.index())
249    }
250
251    /// The type a live pattern matches.
252    ///
253    /// # Examples
254    ///
255    /// ```
256    /// use hir_lang::{Builder, Name};
257    /// use intern_lang::Interner;
258    /// use typeck_lang::{check, Profile, TypeId};
259    ///
260    /// let mut names = Interner::new();
261    /// let mut b = Builder::new();
262    /// let x = b.new_binder(Name::new(names.intern("x")), hir_lang::BinderKind::Local);
263    /// let pat = b.bind(x);
264    /// let init = b.lit(hir_lang::Lit::Bool(true));
265    /// let stmt = b.let_stmt(pat, Some(init));
266    /// let body = b.block(&[stmt], None);
267    /// let main = b.func(Name::new(names.intern("main")), &[], body);
268    /// let root = b.module(None, &[main]);
269    /// let hir = b.finish(root)?;
270    /// let typed = check(&hir, &Profile::static_explicit()).unwrap();
271    /// assert_eq!(typed.pat(pat), Some(TypeId::prim(hir_lang::Prim::Bool)));
272    /// assert_eq!(typed.binder(x), Some(TypeId::prim(hir_lang::Prim::Bool)));
273    /// # Ok::<(), hir_lang::HirError>(())
274    /// ```
275    #[must_use]
276    pub fn pat(&self, id: PatId) -> Option<TypeId> {
277        dense(&self.pats, id.index())
278    }
279
280    /// The type of a bound binder (a variable, parameter, or capture).
281    ///
282    /// # Examples
283    ///
284    /// ```
285    /// use hir_lang::{Builder, Lit, Name, Prim};
286    /// use intern_lang::Interner;
287    /// use typeck_lang::{check, Profile, TypeId};
288    ///
289    /// let mut names = Interner::new();
290    /// let mut b = Builder::new();
291    /// let x = b.new_binder(Name::new(names.intern("x")), hir_lang::BinderKind::Local);
292    /// let pat = b.bind(x);
293    /// let init = b.lit(Lit::Bool(false));
294    /// let s = b.let_stmt(pat, Some(init));
295    /// let body = b.block(&[s], None);
296    /// let main = b.func(Name::new(names.intern("main")), &[], body);
297    /// let root = b.module(None, &[main]);
298    /// let hir = b.finish(root)?;
299    /// let typed = check(&hir, &Profile::static_explicit()).unwrap();
300    /// assert_eq!(typed.binder(x), Some(TypeId::prim(Prim::Bool)));
301    /// # Ok::<(), hir_lang::HirError>(())
302    /// ```
303    #[must_use]
304    pub fn binder(&self, id: BinderId) -> Option<TypeId> {
305        dense(&self.binders, id.index())
306    }
307
308    /// The type store the side tables point into.
309    ///
310    /// # Examples
311    ///
312    /// ```
313    /// use hir_lang::Builder;
314    /// use typeck_lang::{check, Profile, Type, TypeId};
315    ///
316    /// let mut b = Builder::new();
317    /// let root = b.module(None, &[]);
318    /// let hir = b.finish(root)?;
319    /// let typed = check(&hir, &Profile::dynamic()).unwrap();
320    /// assert_eq!(typed.types().get(TypeId::ANY), Type::Any);
321    /// # Ok::<(), hir_lang::HirError>(())
322    /// ```
323    #[must_use]
324    pub fn types(&self) -> &Types {
325        &self.types
326    }
327
328    /// The diagnostics, in source order (span start, then discovery).
329    ///
330    /// # Examples
331    ///
332    /// ```
333    /// use hir_lang::{Builder, Lit, Name, Prim};
334    /// use intern_lang::Interner;
335    /// use typeck_lang::{check, Profile, TypeId};
336    ///
337    /// let mut names = Interner::new();
338    /// let mut b = Builder::new();
339    /// // let x: bool = 1;
340    /// let one = b.int(1);
341    /// let ann = b.ty(hir_lang::Ty::Prim(Prim::Bool));
342    /// let x = b.new_binder(Name::new(names.intern("x")), hir_lang::BinderKind::Local);
343    /// let pat = b.bind(x);
344    /// let s = b.stmt(hir_lang::Stmt::Let { pat, ty: Some(ann), init: Some(one), else_: None });
345    /// let body = b.block(&[s], None);
346    /// let main = b.func(Name::new(names.intern("main")), &[], body);
347    /// let root = b.module(None, &[main]);
348    /// let hir = b.finish(root)?;
349    /// let typed = check(&hir, &Profile::static_explicit()).unwrap();
350    /// let d = typed.diagnostics()[0];
351    /// assert_eq!(d.node, hir_lang::NodeRef::Expr(one));
352    /// assert_eq!(d.kind.code(), "T0001");
353    /// # Ok::<(), hir_lang::HirError>(())
354    /// ```
355    #[must_use]
356    pub fn diagnostics(&self) -> &[Diagnostic] {
357        &self.diagnostics
358    }
359
360    /// `true` if no error was reported (warnings, such as unreachable
361    /// `match` arms, do not count).
362    ///
363    /// # Examples
364    ///
365    /// ```
366    /// use hir_lang::Builder;
367    /// use typeck_lang::{check, Profile};
368    ///
369    /// let mut b = Builder::new();
370    /// let root = b.module(None, &[]);
371    /// let hir = b.finish(root)?;
372    /// assert!(check(&hir, &Profile::static_explicit()).unwrap().is_ok());
373    /// # Ok::<(), hir_lang::HirError>(())
374    /// ```
375    #[must_use]
376    pub fn is_ok(&self) -> bool {
377        self.diagnostics
378            .iter()
379            .all(|d| d.severity != Severity::Error)
380    }
381
382    /// The definition the checker resolved a path's unresolved tail to
383    /// (`Shape::Circle` to a variant, `Point::new` to an impl function).
384    /// `None` for paths resolution resolved completely.
385    ///
386    /// # Examples
387    ///
388    /// ```
389    /// use hir_lang::{Builder, Def, Expr, Ident, Item, ItemKind, List, Name, Ns, Path, Res, Segment, Shape, Span, SumDef, Variant};
390    /// use intern_lang::Interner;
391    /// use typeck_lang::{check, Profile};
392    ///
393    /// let mut names = Interner::new();
394    /// let mut b = Builder::new();
395    /// // enum Shape { Empty }   fn main() { Shape::Empty; }
396    /// let empty = b.variant(Variant {
397    ///     name: Ident::new(names.intern("Empty"), Span::empty(0)),
398    ///     shape: Shape::Unit,
399    ///     fields: List::EMPTY,
400    ///     discriminant: None,
401    /// });
402    /// let variants = b.list(&[empty]);
403    /// let shape = b.item(Item::new(
404    ///     Some(Name::new(names.intern("Shape"))),
405    ///     ItemKind::Sum(SumDef { variants, ..SumDef::default() }),
406    /// ));
407    /// // `Shape` resolved by name; `Empty` left to the checker.
408    /// let origin = b.origin();
409    /// let segments = b.list(&[
410    ///     Segment::new(Name::new(names.intern("Shape")), origin),
411    ///     Segment::new(Name::new(names.intern("Empty")), origin),
412    /// ]);
413    /// let def = b.def(Def::Item(shape));
414    /// let path = b.path(Path { res: Res::Def(def), unresolved: 1, ..Path::new(segments, Ns::Value) });
415    /// let e = b.expr(Expr::Path(path));
416    /// let s = b.expr_stmt(e);
417    /// let body = b.block(&[s], None);
418    /// let main = b.func(Name::new(names.intern("main")), &[], body);
419    /// let root = b.module(None, &[shape, main]);
420    /// let hir = b.finish(root)?;
421    /// let typed = check(&hir, &Profile::static_explicit()).unwrap();
422    /// assert_eq!(typed.path_def(path), Some(Def::Variant(empty)));
423    /// # Ok::<(), hir_lang::HirError>(())
424    /// ```
425    #[must_use]
426    pub fn path_def(&self, path: PathId) -> Option<Def> {
427        lookup(&self.path_defs, path)
428    }
429
430    /// The function item a method call dispatches to statically.
431    ///
432    /// # Examples
433    ///
434    /// ```
435    /// use hir_lang::{Arg, BinderKind, Builder, Def, Expr, FieldDef, FnDef, Ident, ImplDef, Item, ItemKind, List, Name, Ns, Param, ParamKind, Prim, RecordDef, Res, Span, Ty};
436    /// use intern_lang::Interner;
437    /// use typeck_lang::{check, Profile, TypeId};
438    ///
439    /// let mut names = Interner::new();
440    /// let mut b = Builder::new();
441    /// // struct P { x: i64 }  impl P { fn get(self) -> i64 { self.x } }
442    /// let i64_ty = b.ty(Ty::Prim(Prim::I64));
443    /// let x = names.intern("x");
444    /// let field = b.field(FieldDef { ty: Some(i64_ty), ..FieldDef::named(Ident::new(x, Span::empty(0))) });
445    /// let fields = b.list(&[field]);
446    /// let p = b.item(Item::new(Some(Name::new(names.intern("P"))), ItemKind::Record(RecordDef { fields, ..RecordDef::default() })));
447    /// let me = b.new_binder(Name::new(names.intern("self")), BinderKind::Param);
448    /// let me_pat = b.bind(me);
449    /// let recv = b.param(Param { kind: ParamKind::Receiver, ..Param::new(me_pat) });
450    /// let base = b.use_binder(me);
451    /// let read = b.expr(Expr::Field { base, member: hir_lang::Member::Named(x), span: Span::empty(0) });
452    /// let get_body = b.block(&[], Some(read));
453    /// let ret = b.ty(Ty::Prim(Prim::I64));
454    /// let params = b.list(&[recv]);
455    /// let get = b.item(Item::new(Some(Name::new(names.intern("get"))), ItemKind::Fn(FnDef { params, ret: Some(ret), body: Some(get_body), ..FnDef::default() })));
456    /// let p_def = b.def(Def::Item(p));
457    /// let p_path = b.resolved_path(Name::new(names.intern("P")), Ns::Type, Res::Def(p_def));
458    /// let self_ty = b.ty(Ty::Path(p_path));
459    /// let items = b.list(&[get]);
460    /// let imp = b.item(Item::new(None, ItemKind::Impl(ImplDef { items, ..ImplDef::new(self_ty) })));
461    /// // fn main(v: P) { v.get(); }
462    /// let p_path2 = b.resolved_path(Name::new(names.intern("P")), Ns::Type, Res::Def(p_def));
463    /// let v_ty = b.ty(Ty::Path(p_path2));
464    /// let v = b.new_binder(Name::new(names.intern("v")), BinderKind::Param);
465    /// let v_pat = b.bind(v);
466    /// let v_param = b.param(Param { ty: Some(v_ty), ..Param::new(v_pat) });
467    /// let receiver = b.use_binder(v);
468    /// let args = b.list::<Arg>(&[]);
469    /// let call = b.expr(Expr::MethodCall { receiver, method: Ident::new(names.intern("get"), Span::empty(0)), generic_args: List::EMPTY, args });
470    /// let s = b.expr_stmt(call);
471    /// let body = b.block(&[s], None);
472    /// let main = b.func(Name::new(names.intern("main")), &[v_param], body);
473    /// let root = b.module(None, &[p, imp, main]);
474    /// let hir = b.finish(root)?;
475    /// let typed = check(&hir, &Profile::static_explicit()).unwrap();
476    /// assert!(typed.is_ok());
477    /// assert_eq!(typed.method(call), Some(get));
478    /// assert_eq!(typed.expr(call), Some(TypeId::prim(Prim::I64)));
479    /// # Ok::<(), hir_lang::HirError>(())
480    /// ```
481    #[must_use]
482    pub fn method(&self, call: ExprId) -> Option<ItemId> {
483        lookup(&self.methods, call)
484    }
485
486    /// The implicit conversion applied to an expression's value, and the
487    /// type it was converted to.
488    ///
489    /// # Examples
490    ///
491    /// ```
492    /// use hir_lang::{Builder, Lit, Name, Prim};
493    /// use intern_lang::Interner;
494    /// use typeck_lang::{check, Coercion, Profile, TypeId};
495    ///
496    /// let mut names = Interner::new();
497    /// let mut b = Builder::new();
498    /// // let x: f64 = 2i32;   accepted with numeric widening
499    /// let two = b.lit(Lit::Int(hir_lang::IntLit::new(2).with_suffix(Prim::I32)));
500    /// let ann = b.ty(hir_lang::Ty::Prim(Prim::F64));
501    /// let x = b.new_binder(Name::new(names.intern("x")), hir_lang::BinderKind::Local);
502    /// let pat = b.bind(x);
503    /// let s = b.stmt(hir_lang::Stmt::Let { pat, ty: Some(ann), init: Some(two), else_: None });
504    /// let body = b.block(&[s], None);
505    /// let main = b.func(Name::new(names.intern("main")), &[], body);
506    /// let root = b.module(None, &[main]);
507    /// let hir = b.finish(root)?;
508    /// let profile = Profile::static_explicit().with_numeric_widening(true);
509    /// let typed = check(&hir, &profile).unwrap();
510    /// assert!(typed.is_ok());
511    /// assert_eq!(typed.coercion(two), Some((Coercion::Widen, TypeId::prim(Prim::F64))));
512    /// # Ok::<(), hir_lang::HirError>(())
513    /// ```
514    #[must_use]
515    pub fn coercion(&self, expr: ExprId) -> Option<(Coercion, TypeId)> {
516        self.coercions
517            .binary_search_by(|(e, _, _)| e.cmp(&expr))
518            .ok()
519            .and_then(|i| self.coercions.get(i))
520            .map(|&(_, c, t)| (c, t))
521    }
522
523    /// How an `Op` expression's operation was resolved.
524    ///
525    /// # Examples
526    ///
527    /// ```
528    /// use hir_lang::{Builder, Name, OpKind, Prim};
529    /// use intern_lang::Interner;
530    /// use typeck_lang::{check, OpClass, Profile};
531    ///
532    /// let mut names = Interner::new();
533    /// let mut b = Builder::new();
534    /// let (x, y) = (b.int(1), b.int(2));
535    /// let lt = b.op(OpKind::Lt, &[x, y]);
536    /// let s = b.expr_stmt(lt);
537    /// let body = b.block(&[s], None);
538    /// let main = b.func(Name::new(names.intern("main")), &[], body);
539    /// let root = b.module(None, &[main]);
540    /// let hir = b.finish(root)?;
541    /// let typed = check(&hir, &Profile::static_explicit()).unwrap();
542    /// assert_eq!(typed.op_class(lt), Some(OpClass::Int(Prim::I64)));
543    /// # Ok::<(), hir_lang::HirError>(())
544    /// ```
545    #[must_use]
546    pub fn op_class(&self, op: ExprId) -> Option<OpClass> {
547        lookup(&self.op_classes, op)
548    }
549
550    /// The values a non-exhaustive `match` misses, as patterns (`Some(false)`,
551    /// `Shape::Rect { w: _, h: _ }`, `3..=9`), at most eight; empty when the
552    /// match is exhaustive or the profile does not require it.
553    ///
554    /// # Examples
555    ///
556    /// ```
557    /// use hir_lang::{Arm, Builder, Expr, Lit, Name, Pat};
558    /// use intern_lang::Interner;
559    /// use typeck_lang::{check, Profile};
560    ///
561    /// let mut names = Interner::new();
562    /// let mut b = Builder::new();
563    /// // fn main() { match true { true => {} } }
564    /// let scrutinee = b.lit(Lit::Bool(true));
565    /// let pat = b.pat(Pat::Lit(Lit::Bool(true)));
566    /// let body = b.block(&[], None);
567    /// let arms = b.list(&[Arm { pat, guard: None, body }]);
568    /// let m = b.expr(Expr::Match { scrutinee, arms });
569    /// let s = b.expr_stmt(m);
570    /// let main_body = b.block(&[s], None);
571    /// let main = b.func(Name::new(names.intern("main")), &[], main_body);
572    /// let root = b.module(None, &[main]);
573    /// let hir = b.finish(root)?;
574    ///
575    /// let typed = check(&hir, &Profile::static_explicit()).unwrap();
576    /// assert_eq!(typed.witnesses(m, &names), ["false"]);
577    /// assert_eq!(
578    ///     typed.message(&typed.diagnostics()[0], &names),
579    ///     "non-exhaustive match: `false` not covered",
580    /// );
581    /// # Ok::<(), hir_lang::HirError>(())
582    /// ```
583    #[must_use]
584    pub fn witnesses<L: Lookup>(&self, match_expr: ExprId, names: &L) -> Vec<String> {
585        let lo = self.witnesses.partition_point(|&(e, _, _)| e < match_expr);
586        self.witnesses
587            .get(lo..)
588            .unwrap_or(&[])
589            .iter()
590            .take_while(|&&(e, _, _)| e == match_expr)
591            .map(|&(_, start, len)| {
592                let nodes = self
593                    .wnodes
594                    .get(start as usize..(start as usize).saturating_add(len as usize))
595                    .unwrap_or(&[]);
596                let mut out = String::new();
597                self.render_witness(nodes, names, &mut out);
598                out
599            })
600            .collect()
601    }
602
603    /// The generic item an expression uses and its arguments: a path to a
604    /// generic function, a method call (also on non-generic methods, for
605    /// the dispatch), a constructor or literal of a generic type.
606    ///
607    /// # Examples
608    ///
609    /// ```
610    /// use hir_lang::{Builder, Name};
611    /// use intern_lang::Interner;
612    /// use typeck_lang::{check, Profile};
613    ///
614    /// let mut b = Builder::new();
615    /// let root = b.module(None, &[]);
616    /// let hir = b.finish(root)?;
617    /// let typed = check(&hir, &Profile::static_inferred()).unwrap();
618    /// let e = hir_lang::ExprId::from_index(0).unwrap();
619    /// assert!(typed.instantiation(e).is_none());
620    /// # Ok::<(), hir_lang::HirError>(())
621    /// ```
622    #[must_use]
623    pub fn instantiation(&self, expr: ExprId) -> Option<Instantiation<'_>> {
624        let i = self.insts.binary_search_by(|&(e, ..)| e.cmp(&expr)).ok()?;
625        let &(_, item, start, len, dispatch) = self.insts.get(i)?;
626        Some(Instantiation {
627            item,
628            args: self
629                .inst_args
630                .get(start as usize..(start as usize).saturating_add(len as usize))
631                .unwrap_or(&[]),
632            dispatch,
633        })
634    }
635
636    /// The monomorphization plan: every instance of a generic function the
637    /// program reaches, with how it is compiled (see
638    /// [`MonoPolicy`](crate::MonoPolicy)).
639    ///
640    /// # Examples
641    ///
642    /// ```
643    /// use hir_lang::Builder;
644    /// use typeck_lang::{check, Profile};
645    ///
646    /// let mut b = Builder::new();
647    /// let root = b.module(None, &[]);
648    /// let hir = b.finish(root)?;
649    /// assert!(check(&hir, &Profile::static_inferred()).unwrap().mono_plan().is_empty());
650    /// # Ok::<(), hir_lang::HirError>(())
651    /// ```
652    #[must_use]
653    pub fn mono_plan(&self) -> &MonoPlan {
654        &self.mono
655    }
656
657    /// The hidden type of a function's `impl Trait` result, named by the
658    /// `impl` type node of its return type (in the function's own
659    /// placeholders). Callers see only the bounds; lowering needs the type.
660    ///
661    /// # Examples
662    ///
663    /// ```
664    /// use hir_lang::{Builder, TyId};
665    /// use typeck_lang::{check, Profile};
666    ///
667    /// let mut b = Builder::new();
668    /// let root = b.module(None, &[]);
669    /// let hir = b.finish(root)?;
670    /// let typed = check(&hir, &Profile::static_inferred()).unwrap();
671    /// assert!(typed.opaque_type(TyId::from_index(0).unwrap()).is_none());
672    /// # Ok::<(), hir_lang::HirError>(())
673    /// ```
674    #[must_use]
675    pub fn opaque_type(&self, origin: TyId) -> Option<TypeId> {
676        lookup(&self.opaque, origin)
677    }
678
679    /// The profile the program was checked under.
680    ///
681    /// # Examples
682    ///
683    /// ```
684    /// use hir_lang::Builder;
685    /// use typeck_lang::{check, Profile};
686    ///
687    /// let mut b = Builder::new();
688    /// let root = b.module(None, &[]);
689    /// let hir = b.finish(root)?;
690    /// let typed = check(&hir, &Profile::dynamic()).unwrap();
691    /// assert_eq!(*typed.profile(), Profile::dynamic());
692    /// # Ok::<(), hir_lang::HirError>(())
693    /// ```
694    #[must_use]
695    pub fn profile(&self) -> &Profile {
696        &self.profile
697    }
698
699    /// Work counters.
700    ///
701    /// # Examples
702    ///
703    /// ```
704    /// use hir_lang::{Builder, Name};
705    /// use intern_lang::Interner;
706    /// use typeck_lang::{check, Profile};
707    ///
708    /// let mut b = Builder::new();
709    /// let one = b.int(1);
710    /// let s = b.expr_stmt(one);
711    /// let body = b.block(&[s], None);
712    /// let main = b.func(Name::new(Interner::new().intern("main")), &[], body);
713    /// let root = b.module(None, &[main]);
714    /// let hir = b.finish(root)?;
715    /// let stats = check(&hir, &Profile::static_explicit()).unwrap().stats();
716    /// assert!(stats.steps > 0 && stats.type_nodes >= 20);
717    /// # Ok::<(), hir_lang::HirError>(())
718    /// ```
719    #[must_use]
720    pub fn stats(&self) -> Stats {
721        self.stats
722    }
723
724    /// Renders a type; see [`Types::display`].
725    ///
726    /// # Examples
727    ///
728    /// ```
729    /// use hir_lang::Builder;
730    /// use intern_lang::Interner;
731    /// use typeck_lang::{check, Profile, TypeId};
732    ///
733    /// let mut b = Builder::new();
734    /// let root = b.module(None, &[]);
735    /// let hir = b.finish(root)?;
736    /// let typed = check(&hir, &Profile::dynamic()).unwrap();
737    /// assert_eq!(typed.display(TypeId::ANY, &Interner::new()).to_string(), "any");
738    /// # Ok::<(), hir_lang::HirError>(())
739    /// ```
740    #[must_use]
741    pub fn display<'a, L: Lookup>(&'a self, ty: TypeId, names: &'a L) -> TypeDisplay<'a, L> {
742        self.types.display(ty, names)
743    }
744
745    /// Renders a diagnostic's message (without code or location).
746    ///
747    /// # Examples
748    ///
749    /// ```
750    /// use hir_lang::{Builder, Lit, Name, Prim};
751    /// use intern_lang::Interner;
752    /// use typeck_lang::{check, Profile, TypeId};
753    ///
754    /// let mut names = Interner::new();
755    /// let mut b = Builder::new();
756    /// // let x: bool = 1;
757    /// let one = b.int(1);
758    /// let ann = b.ty(hir_lang::Ty::Prim(Prim::Bool));
759    /// let x = b.new_binder(Name::new(names.intern("x")), hir_lang::BinderKind::Local);
760    /// let pat = b.bind(x);
761    /// let s = b.stmt(hir_lang::Stmt::Let { pat, ty: Some(ann), init: Some(one), else_: None });
762    /// let body = b.block(&[s], None);
763    /// let main = b.func(Name::new(names.intern("main")), &[], body);
764    /// let root = b.module(None, &[main]);
765    /// let hir = b.finish(root)?;
766    /// let typed = check(&hir, &Profile::static_explicit()).unwrap();
767    /// let d = typed.diagnostics()[0];
768    /// assert_eq!(typed.message(&d, &names), "mismatched types: expected `bool`, found `i64`");
769    /// # Ok::<(), hir_lang::HirError>(())
770    /// ```
771    #[must_use]
772    pub fn message<L: Lookup>(&self, diagnostic: &Diagnostic, names: &L) -> String {
773        let mut out = String::new();
774        diagnostic.kind.render(&self.types, names, &mut out);
775        if let (DiagnosticKind::NonExhaustive { .. }, hir_lang::NodeRef::Expr(m)) =
776            (diagnostic.kind, diagnostic.node)
777        {
778            let ws = self.witnesses(m, names);
779            if let Some((first, rest)) = ws.split_first() {
780                let _ = write!(out, ": `{first}`");
781                match rest.len() {
782                    0 => out.push_str(" not covered"),
783                    1 => {
784                        let _ = write!(
785                            out,
786                            " and `{}` not covered",
787                            rest.first().map_or("", |s| s.as_str())
788                        );
789                    }
790                    n => {
791                        let _ = write!(out, " and {n} more not covered");
792                    }
793                }
794            }
795        }
796        out
797    }
798
799    fn name_of(&self, key: u32) -> Option<Symbol> {
800        lookup(&self.wnames, key)
801    }
802
803    /// Renders one witness, iteratively: each node prints its head, then its
804    /// fields between brackets.
805    fn render_witness<L: Lookup>(&self, nodes: &[WNode], names: &L, out: &mut String) {
806        enum Piece {
807            Node(usize),
808            Text(&'static str),
809            Field(Symbol),
810        }
811        let push_sym = |s: Symbol, out: &mut String| {
812            if names.resolve_with(s, |t| out.push_str(t)).is_none() {
813                out.push('?');
814            }
815        };
816        // Subtree sizes (preorder: a node's fields follow it).
817        let mut size = alloc::vec![1usize; nodes.len()];
818        for i in (0..nodes.len()).rev() {
819            let arity = nodes.get(i).map_or(0, |n| n.arity as usize);
820            let mut child = i + 1;
821            let mut total = 1;
822            for _ in 0..arity {
823                let s = size.get(child).copied().unwrap_or(1);
824                total += s;
825                child += s;
826            }
827            if let Some(slot) = size.get_mut(i) {
828                *slot = total;
829            }
830        }
831        let mut stack = alloc::vec![Piece::Node(0)];
832        while let Some(piece) = stack.pop() {
833            if out.len() > 200 {
834                out.push('…');
835                return;
836            }
837            let i = match piece {
838                Piece::Text(t) => {
839                    out.push_str(t);
840                    continue;
841                }
842                Piece::Field(s) => {
843                    push_sym(s, out);
844                    out.push_str(": ");
845                    continue;
846                }
847                Piece::Node(i) => i,
848            };
849            let Some(n) = nodes.get(i).copied() else {
850                continue;
851            };
852            let mut kids = Vec::with_capacity(n.arity as usize);
853            let mut child = i + 1;
854            for _ in 0..n.arity {
855                kids.push(child);
856                child += size.get(child).copied().unwrap_or(1);
857            }
858            let fields: &[Symbol] = self
859                .wsyms
860                .get(n.names.0 as usize..(n.names.0 as usize).saturating_add(n.names.1 as usize))
861                .unwrap_or(&[]);
862            let named = !fields.is_empty() && fields.len() == kids.len();
863            let push_fields = |stack: &mut Vec<Piece>, open: &'static str, close: &'static str| {
864                stack.push(Piece::Text(close));
865                for (k, &c) in kids.iter().enumerate().rev() {
866                    stack.push(Piece::Node(c));
867                    if named {
868                        if let Some(&f) = fields.get(k) {
869                            stack.push(Piece::Field(f));
870                        }
871                    }
872                    if k > 0 {
873                        stack.push(Piece::Text(", "));
874                    }
875                }
876                stack.push(Piece::Text(open));
877            };
878            match n.kind {
879                WKind::Wild => out.push('_'),
880                WKind::Null => out.push_str("null"),
881                WKind::Value => {
882                    if let Some(&c) = kids.first() {
883                        stack.push(Piece::Node(c));
884                    }
885                }
886                WKind::Member(t) => {
887                    out.push_str("is ");
888                    self.types.render(t, names, out);
889                    if let Some(&c) = kids.first() {
890                        if nodes.get(c).is_some_and(|x| x.kind != WKind::Wild) {
891                            stack.push(Piece::Node(c));
892                            out.push(' ');
893                        }
894                    }
895                }
896                WKind::Variant(v) => {
897                    let key = u32::try_from(v.index()).unwrap_or(NONE);
898                    match self.name_of(key) {
899                        Some(s) => push_sym(s, out),
900                        None => {
901                            let _ = write!(out, "#{}", v.index());
902                        }
903                    }
904                    if !kids.is_empty() {
905                        if named {
906                            push_fields(&mut stack, " { ", " }");
907                        } else {
908                            push_fields(&mut stack, "(", ")");
909                        }
910                    }
911                }
912                WKind::Item(item) => {
913                    let key = u32::try_from(item.index()).unwrap_or(NONE);
914                    if let Some(s) = lookup(&self.witems, key) {
915                        push_sym(s, out);
916                    }
917                    if named {
918                        push_fields(&mut stack, " { ", " }");
919                    } else {
920                        push_fields(&mut stack, "(", ")");
921                    }
922                }
923                WKind::Tuple => {
924                    if named {
925                        push_fields(&mut stack, "{ ", " }");
926                    } else if kids.len() == 1 {
927                        push_fields(&mut stack, "(", ",)");
928                    } else {
929                        push_fields(&mut stack, "(", ")");
930                    }
931                }
932                WKind::Ref => {
933                    out.push('&');
934                    if let Some(&c) = kids.first() {
935                        stack.push(Piece::Node(c));
936                    }
937                }
938                WKind::Bool(b) => out.push_str(if b { "true" } else { "false" }),
939                WKind::Int(lo, hi) => {
940                    if lo == hi {
941                        let _ = write!(out, "{lo}");
942                    } else {
943                        let _ = write!(out, "{lo}..={hi}");
944                    }
945                }
946                WKind::Char(lo, hi) => {
947                    if lo == hi {
948                        let _ = write!(out, "{lo:?}");
949                    } else {
950                        let _ = write!(out, "{lo:?}..={hi:?}");
951                    }
952                }
953                WKind::Slice(_) => push_fields(&mut stack, "[", "]"),
954                WKind::SliceRest(prefix, _) => {
955                    // `[a, .., z]`: the elements with `..` at the rest.
956                    let mut seq: Vec<Piece> = alloc::vec![Piece::Text("[")];
957                    let total = kids.len() + 1;
958                    let mut k = 0usize;
959                    for pos in 0..total {
960                        if pos > 0 {
961                            seq.push(Piece::Text(", "));
962                        }
963                        if pos == prefix as usize {
964                            seq.push(Piece::Text(".."));
965                        } else if let Some(&c) = kids.get(k) {
966                            seq.push(Piece::Node(c));
967                            k += 1;
968                        }
969                    }
970                    seq.push(Piece::Text("]"));
971                    stack.extend(seq.into_iter().rev());
972                }
973            }
974        }
975    }
976}