Skip to main content

typeck_lang/check/
mod.rs

1//! The checker: context, driver, and the public `Checker`.
2//!
3//! Layout:
4//! - [`index`]: one pre-pass over the tree (live nodes, item owners, method,
5//!   field, and variant tables, class bases).
6//! - [`lower`]: annotations to types, constant evaluation, signatures.
7//! - [`engine`]: the iterative expression and statement checker.
8//! - [`pat`], [`call`], [`ops`], [`coerce`]: pattern, argument, operation, and
9//!   coercion rules.
10//! - [`dynamic`]: the `Dynamic` discipline.
11//! - [`generics`]: placeholders, bounds, substitution, instantiation.
12//! - [`traits`]: the impl index, obligations, normalization, member lookup,
13//!   coherence, conformance.
14//! - [`exhaust`]: exhaustiveness and usefulness through match-lang.
15//! - [`plan`]: the monomorphization plan.
16//! - [`finalize`]: literal defaults, inference failures, and resolving every
17//!   recorded type.
18
19mod call;
20mod coerce;
21mod dynamic;
22mod engine;
23mod exhaust;
24mod finalize;
25mod generics;
26mod index;
27mod items;
28mod lower;
29mod ops;
30mod pat;
31mod paths;
32mod plan;
33mod traits;
34
35use alloc::{collections::BTreeMap, vec::Vec};
36
37use hir_lang::{
38    BinderId, Def, DefId, ExprId, Hir, IdKind, IntLit, ItemId, NodeRef, PatId, PathId, Prim,
39    Symbol, TyId,
40};
41
42use crate::{
43    diag::{Diagnostic, DiagnosticKind, Severity},
44    error::{Budget, CheckError, Meter},
45    infer::{Infer, UnifyCfg},
46    mono::{Strategy, Use},
47    profile::{Profile, RecordTyping},
48    typed::{Coercion, NONE, Typed, WNode},
49    types::{Field, Tag, TypeId, Types},
50};
51
52pub(crate) use index::Index;
53
54/// The hard cap on re-entrant lowering and normalization (each level is a
55/// few stack frames; chains of associated types defined through others are
56/// rarely more than a handful deep).
57const NEST_CAP: u32 = 32;
58
59/// The configured path: declare host types, set a budget, then check.
60///
61/// [`check`](crate::check) is this with no declarations and the default
62/// budget scaled to the HIR.
63///
64/// # Examples
65///
66/// ```
67/// use hir_lang::{Builder, Effects, Name, Prim, Res};
68/// use intern_lang::Interner;
69/// use typeck_lang::{Checker, Profile, TypeId};
70///
71/// let mut names = Interner::new();
72/// let print = names.intern("print");
73/// let mut b = Builder::new();
74/// // fn main() { print("hi") }   with `print` bound by the host.
75/// let path = b.resolved_path(Name::new(print), hir_lang::Ns::Value, Res::Extern(print));
76/// let callee = b.expr(hir_lang::Expr::Path(path));
77/// let hi = b.str_lit("hi");
78/// let call = b.call(callee, &[hi]);
79/// let s = b.expr_stmt(call);
80/// let body = b.block(&[s], None);
81/// let main = b.func(Name::new(names.intern("main")), &[], body);
82/// let root = b.module(None, &[main]);
83/// let hir = b.finish(root)?;
84///
85/// let mut checker = Checker::new(&hir, Profile::static_explicit());
86/// let print_ty = checker.types_mut().func(&[TypeId::prim(Prim::Str)], TypeId::UNIT, Effects::NONE);
87/// checker.declare_extern(print, print_ty);
88/// let typed = checker.check().unwrap();
89/// assert!(typed.is_ok());
90/// assert_eq!(typed.expr(call), Some(TypeId::UNIT));
91/// # Ok::<(), hir_lang::HirError>(())
92/// ```
93#[derive(Debug)]
94pub struct Checker<'h> {
95    hir: &'h Hir,
96    profile: Profile,
97    budget: Budget,
98    types: Types,
99    host: Host,
100}
101
102/// Declarations the host makes about names the unit does not define.
103#[derive(Debug, Default)]
104pub(crate) struct Host {
105    /// Value types of `Res::Extern` symbols.
106    pub(crate) externs: Vec<(Symbol, TypeId)>,
107    /// Value types of other units' definitions.
108    pub(crate) foreign: Vec<(DefId, TypeId)>,
109    /// Types of `Intrinsic::Named` intrinsics (function types).
110    pub(crate) intrinsics: Vec<(Symbol, TypeId)>,
111    /// Methods and associated items of host types: (owner, name, type).
112    pub(crate) members: Vec<(TypeId, Symbol, TypeId)>,
113    /// Attributes that force a monomorphization strategy, by name.
114    pub(crate) mono_attrs: Vec<(Symbol, Strategy)>,
115}
116
117fn upsert<K: Ord + Copy, V>(table: &mut Vec<(K, V)>, key: K, value: V) {
118    match table.binary_search_by(|(k, _)| k.cmp(&key)) {
119        Ok(i) => {
120            if let Some(slot) = table.get_mut(i) {
121                slot.1 = value;
122            }
123        }
124        Err(i) => table.insert(i, (key, value)),
125    }
126}
127
128fn find<K: Ord + Copy, V: Copy>(table: &[(K, V)], key: K) -> Option<V> {
129    table
130        .binary_search_by(|(k, _)| k.cmp(&key))
131        .ok()
132        .and_then(|i| table.get(i))
133        .map(|&(_, v)| v)
134}
135
136impl<'h> Checker<'h> {
137    /// A checker for `hir` under `profile`, with [`Budget::for_hir`].
138    ///
139    /// # Examples
140    ///
141    /// ```
142    /// use hir_lang::{Builder, Effects, Expr, Name, Ns, Prim, Res};
143    /// use intern_lang::Interner;
144    /// use typeck_lang::{Checker, Profile, TypeId};
145    ///
146    /// let mut names = Interner::new();
147    /// let pi = names.intern("pi");
148    /// let mut b = Builder::new();
149    /// // fn main() { pi; }   with `pi` bound by the host
150    /// let path = b.resolved_path(Name::new(pi), Ns::Value, Res::Extern(pi));
151    /// let use_pi = b.expr(Expr::Path(path));
152    /// let s = b.expr_stmt(use_pi);
153    /// let body = b.block(&[s], None);
154    /// let main = b.func(Name::new(names.intern("main")), &[], body);
155    /// let root = b.module(None, &[main]);
156    /// let hir = b.finish(root)?;
157    ///
158    /// let mut checker = Checker::new(&hir, Profile::static_explicit());
159    /// checker.declare_extern(pi, TypeId::prim(Prim::F64));
160    /// let typed = checker.check().unwrap();
161    /// assert!(typed.is_ok());
162    /// assert_eq!(typed.expr(use_pi), Some(TypeId::prim(Prim::F64)));
163    /// # Ok::<(), hir_lang::HirError>(())
164    /// ```
165    #[must_use]
166    pub fn new(hir: &'h Hir, profile: Profile) -> Self {
167        Self {
168            hir,
169            profile,
170            budget: Budget::for_hir(hir),
171            types: Types::new(),
172            host: Host::default(),
173        }
174    }
175
176    /// Replaces the budget.
177    ///
178    /// # Examples
179    ///
180    /// ```
181    /// use hir_lang::Builder;
182    /// use typeck_lang::{Budget, CheckError, Checker, Limit, Profile};
183    ///
184    /// let mut b = Builder::new();
185    /// let one = b.int(1);
186    /// let body = b.block(&[], Some(one));
187    /// let f = b.func(hir_lang::Name::new(intern_lang::Interner::new().intern("f")), &[], body);
188    /// let root = b.module(None, &[f]);
189    /// let hir = b.finish(root)?;
190    /// let mut checker = Checker::new(&hir, Profile::static_explicit());
191    /// checker.set_budget(Budget { steps: 2, ..Budget::default() });
192    /// assert_eq!(checker.check(), Err(CheckError::BudgetExceeded { limit: Limit::Steps }));
193    /// # Ok::<(), hir_lang::HirError>(())
194    /// ```
195    pub fn set_budget(&mut self, budget: Budget) -> &mut Self {
196        self.budget = budget;
197        self
198    }
199
200    /// The type store, to build the types of host declarations.
201    ///
202    /// # Examples
203    ///
204    /// ```
205    /// use hir_lang::{Builder, Effects, Expr, Name, Ns, Prim, Res};
206    /// use intern_lang::Interner;
207    /// use typeck_lang::{Checker, Profile, TypeId};
208    ///
209    /// let mut names = Interner::new();
210    /// let pi = names.intern("pi");
211    /// let mut b = Builder::new();
212    /// // fn main() { pi; }   with `pi` bound by the host
213    /// let path = b.resolved_path(Name::new(pi), Ns::Value, Res::Extern(pi));
214    /// let use_pi = b.expr(Expr::Path(path));
215    /// let s = b.expr_stmt(use_pi);
216    /// let body = b.block(&[s], None);
217    /// let main = b.func(Name::new(names.intern("main")), &[], body);
218    /// let root = b.module(None, &[main]);
219    /// let hir = b.finish(root)?;
220    ///
221    /// let mut checker = Checker::new(&hir, Profile::static_explicit());
222    /// // A host type built in the checker's own store.
223    /// let f64_ty = TypeId::prim(Prim::F64);
224    /// let wrapped = checker.types_mut().tuple(&[f64_ty]);
225    /// assert_ne!(wrapped, f64_ty);
226    /// checker.declare_extern(pi, f64_ty);
227    /// let typed = checker.check().unwrap();
228    /// assert!(typed.is_ok());
229    /// assert_eq!(typed.expr(use_pi), Some(TypeId::prim(Prim::F64)));
230    /// # Ok::<(), hir_lang::HirError>(())
231    /// ```
232    pub fn types_mut(&mut self) -> &mut Types {
233        &mut self.types
234    }
235
236    /// Declares the value type of a host symbol (`Res::Extern(name)` in a
237    /// value path). A later declaration of the same name replaces it.
238    ///
239    /// # Examples
240    ///
241    /// ```
242    /// use hir_lang::{Builder, Effects, Expr, Name, Ns, Prim, Res};
243    /// use intern_lang::Interner;
244    /// use typeck_lang::{Checker, Profile, TypeId};
245    ///
246    /// let mut names = Interner::new();
247    /// let pi = names.intern("pi");
248    /// let mut b = Builder::new();
249    /// // fn main() { pi; }   with `pi` bound by the host
250    /// let path = b.resolved_path(Name::new(pi), Ns::Value, Res::Extern(pi));
251    /// let use_pi = b.expr(Expr::Path(path));
252    /// let s = b.expr_stmt(use_pi);
253    /// let body = b.block(&[s], None);
254    /// let main = b.func(Name::new(names.intern("main")), &[], body);
255    /// let root = b.module(None, &[main]);
256    /// let hir = b.finish(root)?;
257    ///
258    /// let mut checker = Checker::new(&hir, Profile::static_explicit());
259    /// checker.declare_extern(pi, TypeId::prim(Prim::F64));
260    /// let typed = checker.check().unwrap();
261    /// assert!(typed.is_ok());
262    /// assert_eq!(typed.expr(use_pi), Some(TypeId::prim(Prim::F64)));
263    /// # Ok::<(), hir_lang::HirError>(())
264    /// ```
265    pub fn declare_extern(&mut self, name: Symbol, ty: TypeId) -> &mut Self {
266        upsert(&mut self.host.externs, name, ty);
267        self
268    }
269
270    /// Declares the value type of another unit's definition (a value path
271    /// resolved to a `DefId` of another unit).
272    ///
273    /// # Examples
274    ///
275    /// ```
276    /// use hir_lang::{Builder, Def, DefId, ItemId, UnitId};
277    /// use typeck_lang::{Checker, Profile, TypeId};
278    ///
279    /// let mut b = Builder::new();
280    /// let root = b.module(None, &[]);
281    /// let hir = b.finish(root)?;
282    /// let other = DefId::foreign(UnitId::new(7), Def::Item(ItemId::from_index(0).unwrap()));
283    /// let mut checker = Checker::new(&hir, Profile::static_explicit());
284    /// checker.declare_foreign(other, TypeId::UNIT);
285    /// assert!(checker.check().unwrap().is_ok());
286    /// # Ok::<(), hir_lang::HirError>(())
287    /// ```
288    pub fn declare_foreign(&mut self, def: DefId, ty: TypeId) -> &mut Self {
289        upsert(&mut self.host.foreign, def, ty);
290        self
291    }
292
293    /// Declares the function type of a named intrinsic
294    /// (`Intrinsic::Named(name)`).
295    ///
296    /// # Examples
297    ///
298    /// ```
299    /// use hir_lang::{Builder, Effects, Prim};
300    /// use intern_lang::Interner;
301    /// use typeck_lang::{Checker, Profile, TypeId};
302    ///
303    /// let mut names = Interner::new();
304    /// let mut b = Builder::new();
305    /// let root = b.module(None, &[]);
306    /// let hir = b.finish(root)?;
307    /// let mut checker = Checker::new(&hir, Profile::static_explicit());
308    /// let ty = checker.types_mut().func(&[], TypeId::prim(Prim::U64), Effects::NONE);
309    /// checker.declare_intrinsic(names.intern("rdtsc"), ty);
310    /// assert!(checker.check().is_ok());
311    /// # Ok::<(), hir_lang::HirError>(())
312    /// ```
313    pub fn declare_intrinsic(&mut self, name: Symbol, ty: TypeId) -> &mut Self {
314        upsert(&mut self.host.intrinsics, name, ty);
315        self
316    }
317
318    /// Declares a method or associated item of a type (typically a host
319    /// type such as `types_mut().external(vec)`): `owner::name` in a path,
320    /// and `value.name(..)` in a method call when `ty` is a function whose
321    /// first parameter is the receiver.
322    ///
323    /// # Examples
324    ///
325    /// ```
326    /// use hir_lang::{Builder, Effects, Prim};
327    /// use intern_lang::Interner;
328    /// use typeck_lang::{Checker, Profile, TypeId};
329    ///
330    /// let mut names = Interner::new();
331    /// let vec = names.intern("Vec");
332    /// let mut b = Builder::new();
333    /// let root = b.module(None, &[]);
334    /// let hir = b.finish(root)?;
335    /// let mut checker = Checker::new(&hir, Profile::static_explicit());
336    /// let vec_ty = checker.types_mut().external(vec);
337    /// let len = checker.types_mut().func(&[vec_ty], TypeId::prim(Prim::Usize), Effects::NONE);
338    /// checker.declare_member(vec_ty, names.intern("len"), len);
339    /// assert!(checker.check().is_ok());
340    /// # Ok::<(), hir_lang::HirError>(())
341    /// ```
342    pub fn declare_member(&mut self, owner: TypeId, name: Symbol, ty: TypeId) -> &mut Self {
343        let key = (owner, name);
344        match self
345            .host
346            .members
347            .binary_search_by(|&(o, n, _)| (o, n).cmp(&key))
348        {
349            Ok(i) => {
350                if let Some(slot) = self.host.members.get_mut(i) {
351                    slot.2 = ty;
352                }
353            }
354            Err(i) => self.host.members.insert(i, (owner, name, ty)),
355        }
356        self
357    }
358
359    /// Makes an attribute named `name` on a generic item force `strategy`
360    /// in the monomorphization plan, whatever the profile's
361    /// [`MonoPolicy`](crate::MonoPolicy) says (a language's `@inline` or
362    /// `@hot` copies; `@shared` shares). A later declaration of the same
363    /// name replaces it.
364    ///
365    /// # Examples
366    ///
367    /// ```
368    /// use hir_lang::Builder;
369    /// use intern_lang::Interner;
370    /// use typeck_lang::{Checker, Profile, Strategy};
371    ///
372    /// let mut names = Interner::new();
373    /// let mut b = Builder::new();
374    /// let root = b.module(None, &[]);
375    /// let hir = b.finish(root)?;
376    /// let mut checker = Checker::new(&hir, Profile::static_inferred());
377    /// checker.declare_mono_attribute(names.intern("hot"), Strategy::Copy);
378    /// assert!(checker.check().unwrap().is_ok());
379    /// # Ok::<(), hir_lang::HirError>(())
380    /// ```
381    pub fn declare_mono_attribute(&mut self, name: Symbol, strategy: Strategy) -> &mut Self {
382        upsert(&mut self.host.mono_attrs, name, strategy);
383        self
384    }
385
386    /// Runs the check.
387    ///
388    /// # Errors
389    ///
390    /// [`CheckError::NotImplemented`] for a discipline this version does not
391    /// implement, [`CheckError::InvalidProfile`] for inconsistent literal
392    /// defaults, and [`CheckError::BudgetExceeded`] when the budget runs out.
393    /// Type errors in the program are diagnostics in the `Ok` result.
394    ///
395    /// # Examples
396    ///
397    /// ```
398    /// use hir_lang::{Builder, Effects, Expr, Name, Ns, Prim, Res};
399    /// use intern_lang::Interner;
400    /// use typeck_lang::{Checker, Profile, TypeId};
401    ///
402    /// let mut names = Interner::new();
403    /// let pi = names.intern("pi");
404    /// let mut b = Builder::new();
405    /// // fn main() { pi; }   with `pi` bound by the host
406    /// let path = b.resolved_path(Name::new(pi), Ns::Value, Res::Extern(pi));
407    /// let use_pi = b.expr(Expr::Path(path));
408    /// let s = b.expr_stmt(use_pi);
409    /// let body = b.block(&[s], None);
410    /// let main = b.func(Name::new(names.intern("main")), &[], body);
411    /// let root = b.module(None, &[main]);
412    /// let hir = b.finish(root)?;
413    ///
414    /// let mut checker = Checker::new(&hir, Profile::static_explicit());
415    /// checker.declare_extern(pi, TypeId::prim(Prim::F64));
416    /// let typed = checker.check().unwrap();
417    /// assert!(typed.is_ok());
418    /// assert_eq!(typed.expr(use_pi), Some(TypeId::prim(Prim::F64)));
419    /// # Ok::<(), hir_lang::HirError>(())
420    /// ```
421    pub fn check(self) -> Result<Typed, CheckError> {
422        let profile = self.profile;
423        if !profile.discipline.is_implemented() {
424            return Err(CheckError::NotImplemented {
425                discipline: profile.discipline,
426            });
427        }
428        if !profile.default_int.is_int() || !profile.default_float.is_float() {
429            return Err(CheckError::InvalidProfile);
430        }
431        let mut cx = Ctx::new(self.hir, profile, self.budget, self.types, self.host);
432        cx.meter.tick(1)?;
433        cx.build_index()?;
434        if profile.is_static() {
435            cx.check_static()?;
436        } else {
437            cx.check_dynamic()?;
438        }
439        cx.into_typed()
440    }
441}
442
443/// A function or closure being checked.
444#[derive(Clone, Copy, Debug)]
445pub(crate) struct Frame {
446    /// The declared result before generator and opaque rewriting (what a
447    /// `?` must propagate into).
448    pub(crate) declared: TypeId,
449    /// What `return` values must be.
450    pub(crate) ret: TypeId,
451    /// The declared thrown type, if any.
452    pub(crate) throws: Option<TypeId>,
453    /// What `yield` values must be, in a generator.
454    pub(crate) yields: Option<TypeId>,
455}
456
457/// A loop or labelled block that `break` can target.
458#[derive(Clone, Copy, Debug)]
459pub(crate) struct Target {
460    /// The join of the break values so far.
461    pub(crate) result: Option<TypeId>,
462    /// Whether this is a loop (unlabelled `break` targets the innermost one).
463    pub(crate) is_loop: bool,
464}
465
466/// The shared state of one check.
467pub(crate) struct Ctx<'h> {
468    pub(crate) hir: &'h Hir,
469    pub(crate) profile: Profile,
470    pub(crate) types: Types,
471    pub(crate) infer: Infer,
472    pub(crate) meter: Meter,
473    pub(crate) host: Host,
474    pub(crate) idx: Index,
475
476    // Output side tables (dense, by HIR index).
477    pub(crate) expr_ty: Vec<u32>,
478    pub(crate) pat_ty: Vec<u32>,
479    pub(crate) binder_ty: Vec<u32>,
480    /// The pattern that binds each binder, for diagnostics.
481    pub(crate) binder_site: Vec<u32>,
482    pub(crate) diags: Vec<Diagnostic>,
483    pub(crate) methods: Vec<(ExprId, ItemId)>,
484    pub(crate) coercions: Vec<(ExprId, Coercion, TypeId)>,
485
486    // Checking state.
487    /// The type each expression must coerce to, set by its parent.
488    pub(crate) expect: Vec<u32>,
489    /// Expressions reported against their context; parents read them as
490    /// `{error}` so the report is not repeated.
491    pub(crate) poisoned: Vec<bool>,
492    /// Unsuffixed integer literals and their variables, range-checked once
493    /// the variables are resolved.
494    pub(crate) int_lits: Vec<(NodeRef, TypeId, IntLit)>,
495    pub(crate) frames: Vec<Frame>,
496    pub(crate) targets: Vec<Target>,
497    /// Binder index -> index into `targets`, for labelled targets.
498    pub(crate) label_pos: Vec<u32>,
499    /// The `Self` type of the item being checked.
500    pub(crate) cur_self: Option<TypeId>,
501
502    // Lowering memos.
503    pub(crate) ty_memo: Vec<u32>,
504    /// Per item: 0 untouched, 1 lowering in progress, 2 done (aliases).
505    pub(crate) alias_state: Vec<u8>,
506    pub(crate) sigs: Vec<u32>,
507    pub(crate) sig_arena: Vec<lower::Sig>,
508    /// Per const/global item: its declared type.
509    pub(crate) decl_memo: Vec<u32>,
510    /// Sorted field lists of named-field record items (structural records
511    /// and record literals).
512    pub(crate) record_fields: Vec<Option<(u32, u32)>>,
513    pub(crate) field_pool: Vec<Field>,
514    /// Per field: its declared type.
515    pub(crate) field_memo: Vec<u32>,
516    /// Per const item: constant-evaluation state and value.
517    pub(crate) const_memo: Vec<(u8, i128)>,
518    /// Innermost-last indices into `targets` of the enclosing loops.
519    pub(crate) loops: Vec<u32>,
520    /// Scratch: which parameters an argument list filled.
521    pub(crate) filled: Vec<bool>,
522    /// Operands whose type was unknown at their operation: re-checked once
523    /// inference is done.
524    pub(crate) deferred_ops: Vec<(ExprId, hir_lang::OpKind, ops::Want)>,
525    /// `x == null` comparisons (their op class).
526    pub(crate) null_checks: Vec<ExprId>,
527    /// Expressions whose expectation moved to their branches (stack).
528    pub(crate) delegated: Vec<(ExprId, TypeId)>,
529    /// Record literals' targets and instance types between entry and exit
530    /// (stack).
531    pub(crate) record_targets: Vec<(ExprId, paths::RecordRef, TypeId)>,
532    /// `let` annotations between entry and the pattern (stack).
533    pub(crate) let_types: Vec<(hir_lang::StmtId, TypeId)>,
534    /// Closure types between entry and exit (stack).
535    pub(crate) closure_types: Vec<TypeId>,
536    /// Per path: the definition the checker resolved its tail to.
537    pub(crate) path_def: Vec<Option<Def>>,
538    /// Per expression: the (instantiated) signature a callee path names
539    /// (`NONE`).
540    pub(crate) callee_sigs: Vec<u32>,
541    /// Call targets between a call's preparation and its finish.
542    pub(crate) call_stack: Vec<call::CallTarget>,
543    /// Expectations for a call's arguments derived from its expected
544    /// result, between its preparation and its finish (stack).
545    pub(crate) probes: Vec<(ExprId, Vec<Option<TypeId>>)>,
546    /// The engine's task stack, reused across roots.
547    pub(crate) tasks: Vec<engine::Task>,
548    /// Visited marks for walks over class hierarchies (epoch-stamped, so a
549    /// new walk costs nothing to start).
550    pub(crate) item_stamp: Vec<u32>,
551    pub(crate) item_epoch: u32,
552
553    // Generics.
554    /// The item whose body is being checked (its bounds are in scope).
555    pub(crate) cur_item: Option<ItemId>,
556    /// The item whose annotations are being lowered, when not `cur_item`.
557    pub(crate) lower_ctx: Option<ItemId>,
558    pub(crate) param_lists: Vec<generics::ParamList>,
559    pub(crate) params_memo: Vec<u32>,
560    pub(crate) bound_lists: Vec<generics::BoundList>,
561    pub(crate) bounds_memo: Vec<u32>,
562    /// While an item's bounds are being lowered: the list being filled.
563    pub(crate) bounds_partial: Vec<u32>,
564    /// `impl Trait` type nodes of function signatures: (type node, function,
565    /// return position), sorted by function; and (type node, position in
566    /// that table), sorted by type node.
567    pub(crate) impl_tys: Vec<(TyId, ItemId, bool)>,
568    pub(crate) impl_ty_index: Vec<(TyId, u32)>,
569    pub(crate) subst_memo: Vec<u32>,
570    pub(crate) subst_stamp: Vec<u32>,
571    pub(crate) subst_epoch: u32,
572
573    // Interfaces.
574    pub(crate) tr: traits::TraitIndex,
575    pub(crate) pending: Vec<traits::Obligation>,
576    /// Obligations still undecided at the end of their item.
577    pub(crate) stuck: Vec<traits::Obligation>,
578    pub(crate) solve_depth: u32,
579    pub(crate) norm_depth: u32,
580    /// Hidden types of `impl Trait` results.
581    pub(crate) hidden: Vec<(TyId, TypeId)>,
582
583    /// Where the coercion being checked happens (for the goals a `dyn`
584    /// coercion queues).
585    pub(crate) coerce_site: NodeRef,
586    /// Re-entrance depth of type lowering.
587    pub(crate) lower_depth: u32,
588    /// Visited marks for walks over type DAGs (epoch-stamped).
589    pub(crate) walk_stamp: Vec<u32>,
590    pub(crate) walk_epoch: u32,
591    /// The conversion interface of the `?` hook, once looked up.
592    pub(crate) try_iface: Option<Option<ItemId>>,
593
594    // Plan.
595    pub(crate) uses: Vec<Use>,
596    /// Values coerced to `dyn` types: (item, type, interface): the plan
597    /// adds the implementation's methods (the vtable).
598    pub(crate) dyn_uses: Vec<(Option<ItemId>, TypeId, TypeId)>,
599    pub(crate) use_args: Vec<TypeId>,
600    /// Live HIR nodes per item (its own body, not nested items).
601    pub(crate) item_size: Vec<u32>,
602
603    // Exhaustiveness.
604    pub(crate) matches: Vec<ExprId>,
605    pub(crate) lit_ids: BTreeMap<Vec<u8>, u64>,
606    pub(crate) witnesses: Vec<(ExprId, u32, u32)>,
607    pub(crate) wnodes: Vec<WNode>,
608    pub(crate) wsyms: Vec<Symbol>,
609}
610
611impl<'h> Ctx<'h> {
612    fn new(hir: &'h Hir, profile: Profile, budget: Budget, types: Types, host: Host) -> Self {
613        let n = |k| hir.count(k);
614        Self {
615            hir,
616            profile,
617            types,
618            infer: Infer::default(),
619            meter: Meter::new(budget),
620            host,
621            idx: Index::default(),
622            expr_ty: alloc::vec![NONE; n(IdKind::Expr)],
623            pat_ty: alloc::vec![NONE; n(IdKind::Pat)],
624            binder_ty: alloc::vec![NONE; n(IdKind::Binder)],
625            binder_site: alloc::vec![NONE; n(IdKind::Binder)],
626            diags: Vec::new(),
627            methods: Vec::new(),
628            coercions: Vec::new(),
629            expect: alloc::vec![NONE; n(IdKind::Expr)],
630            poisoned: alloc::vec![false; n(IdKind::Expr)],
631            int_lits: Vec::new(),
632            frames: Vec::new(),
633            targets: Vec::new(),
634            label_pos: alloc::vec![NONE; n(IdKind::Binder)],
635            cur_self: None,
636            ty_memo: alloc::vec![NONE; n(IdKind::Ty)],
637            alias_state: alloc::vec![0; n(IdKind::Item)],
638            sigs: alloc::vec![NONE; n(IdKind::Item)],
639            sig_arena: Vec::new(),
640            decl_memo: alloc::vec![NONE; n(IdKind::Item)],
641            record_fields: alloc::vec![None; n(IdKind::Item)],
642            field_pool: Vec::new(),
643            field_memo: alloc::vec![NONE; n(IdKind::Field)],
644            const_memo: alloc::vec![(0, 0); n(IdKind::Item)],
645            loops: Vec::new(),
646            filled: Vec::new(),
647            deferred_ops: Vec::new(),
648            delegated: Vec::new(),
649            record_targets: Vec::new(),
650            let_types: Vec::new(),
651            closure_types: Vec::new(),
652            path_def: alloc::vec![None; n(IdKind::Path)],
653            null_checks: Vec::new(),
654            callee_sigs: alloc::vec![NONE; n(IdKind::Expr)],
655            call_stack: Vec::new(),
656            probes: Vec::new(),
657            tasks: Vec::new(),
658            item_stamp: alloc::vec![0; n(IdKind::Item)],
659            item_epoch: 0,
660            cur_item: None,
661            lower_ctx: None,
662            param_lists: Vec::new(),
663            params_memo: alloc::vec![NONE; n(IdKind::Item)],
664            bound_lists: Vec::new(),
665            bounds_memo: alloc::vec![NONE; n(IdKind::Item)],
666            bounds_partial: alloc::vec![NONE; n(IdKind::Item)],
667            impl_tys: Vec::new(),
668            impl_ty_index: Vec::new(),
669            subst_memo: Vec::new(),
670            subst_stamp: Vec::new(),
671            subst_epoch: 0,
672            tr: traits::TraitIndex::default(),
673            pending: Vec::new(),
674            stuck: Vec::new(),
675            solve_depth: 0,
676            norm_depth: 0,
677            hidden: Vec::new(),
678            coerce_site: NodeRef::Item(hir.root()),
679            lower_depth: 0,
680            try_iface: None,
681            walk_stamp: Vec::new(),
682            walk_epoch: 0,
683            uses: Vec::new(),
684            dyn_uses: Vec::new(),
685            use_args: Vec::new(),
686            item_size: alloc::vec![0; n(IdKind::Item)],
687            matches: Vec::new(),
688            lit_ids: BTreeMap::new(),
689            witnesses: Vec::new(),
690            wnodes: Vec::new(),
691            wsyms: Vec::new(),
692        }
693    }
694
695    // ------------------------------------------------------------ helpers
696
697    pub(crate) fn report(&mut self, node: NodeRef, kind: DiagnosticKind) {
698        self.report_with(node, kind, Severity::Error);
699    }
700
701    pub(crate) fn report_with(&mut self, node: NodeRef, kind: DiagnosticKind, severity: Severity) {
702        let origin = self.hir.origin(node);
703        self.diags.push(Diagnostic {
704            kind,
705            node,
706            origin,
707            severity,
708        });
709    }
710
711    /// Records a use of `callee` with `args` at `at`, for the plan and
712    /// [`Typed::instantiation`].
713    pub(crate) fn record_use(
714        &mut self,
715        at: ExprId,
716        callee: ItemId,
717        args: &[TypeId],
718        dispatch: crate::mono::Dispatch,
719    ) {
720        let start = u32::try_from(self.use_args.len()).unwrap_or(NONE);
721        self.use_args.extend_from_slice(args);
722        self.uses.push(Use {
723            at,
724            owner: self.cur_item,
725            callee,
726            args: (start, u32::try_from(args.len()).unwrap_or(0)),
727            dispatch,
728        });
729    }
730
731    pub(crate) fn fresh(&mut self, class: u8) -> TypeId {
732        self.infer.fresh(&mut self.types, class)
733    }
734
735    /// The node representing `t`'s class (one level: a bound variable reads
736    /// as its binding).
737    pub(crate) fn resolve(&self, t: TypeId) -> TypeId {
738        self.infer.resolve(t)
739    }
740
741    pub(crate) fn tag(&self, t: TypeId) -> Tag {
742        self.types.node(self.resolve(t)).tag
743    }
744
745    pub(crate) fn is_err(&self, t: TypeId) -> bool {
746        self.tag(t) == Tag::Error
747    }
748
749    /// The primitive `t` resolves to, if any.
750    pub(crate) fn prim_of(&self, t: TypeId) -> Option<Prim> {
751        match self.types.get(self.resolve(t)) {
752            crate::types::Type::Prim(p) => Some(p),
753            _ => None,
754        }
755    }
756
757    pub(crate) fn unify(&mut self, a: TypeId, b: TypeId) -> Result<bool, CheckError> {
758        let cfg = UnifyCfg {
759            int_to_float: self.profile.numeric_widening,
760            structural: self.profile.records == RecordTyping::Structural,
761            record_fields: &self.record_fields,
762            field_pool: &self.field_pool,
763        };
764        self.infer.unify(&self.types, &cfg, &mut self.meter, a, b)
765    }
766
767    pub(crate) fn ety(&self, e: ExprId) -> TypeId {
768        self.expr_ty
769            .get(e.index())
770            .copied()
771            .filter(|&r| r != NONE)
772            .map_or(TypeId::ERROR, TypeId::from_raw)
773    }
774
775    /// An expression's type as its parent sees it: `{error}` if it was
776    /// already reported against its context.
777    pub(crate) fn child(&self, e: ExprId) -> TypeId {
778        if self.poisoned.get(e.index()).copied().unwrap_or(false) {
779            TypeId::ERROR
780        } else {
781            self.ety(e)
782        }
783    }
784
785    pub(crate) fn typed(&self, e: ExprId) -> bool {
786        self.expr_ty.get(e.index()).is_some_and(|&r| r != NONE)
787    }
788
789    pub(crate) fn poison(&mut self, e: ExprId) {
790        if let Some(p) = self.poisoned.get_mut(e.index()) {
791            *p = true;
792        }
793    }
794
795    pub(crate) fn set_expect(&mut self, e: ExprId, t: TypeId) {
796        if let Some(slot) = self.expect.get_mut(e.index()) {
797            *slot = t.raw();
798        }
799    }
800
801    pub(crate) fn take_expect(&mut self, e: ExprId) -> Option<TypeId> {
802        let slot = self.expect.get_mut(e.index())?;
803        let v = core::mem::replace(slot, NONE);
804        (v != NONE).then(|| TypeId::from_raw(v))
805    }
806
807    pub(crate) fn peek_expect(&self, e: ExprId) -> Option<TypeId> {
808        self.expect
809            .get(e.index())
810            .copied()
811            .filter(|&v| v != NONE)
812            .map(TypeId::from_raw)
813    }
814
815    pub(crate) fn set_binder(&mut self, b: BinderId, t: TypeId, site: PatId) {
816        if let Some(slot) = self.binder_ty.get_mut(b.index()) {
817            *slot = t.raw();
818        }
819        if let Some(slot) = self.binder_site.get_mut(b.index()) {
820            if *slot == NONE {
821                *slot = u32::try_from(site.index()).unwrap_or(NONE);
822            }
823        }
824    }
825
826    pub(crate) fn binder_type(&self, b: BinderId) -> Option<TypeId> {
827        self.binder_ty
828            .get(b.index())
829            .copied()
830            .filter(|&v| v != NONE)
831            .map(TypeId::from_raw)
832    }
833
834    pub(crate) fn host_extern(&self, name: Symbol) -> Option<TypeId> {
835        find(&self.host.externs, name)
836    }
837
838    pub(crate) fn host_foreign(&self, def: DefId) -> Option<TypeId> {
839        find(&self.host.foreign, def)
840    }
841
842    pub(crate) fn host_intrinsic(&self, name: Symbol) -> Option<TypeId> {
843        find(&self.host.intrinsics, name)
844    }
845
846    pub(crate) fn host_member(&self, owner: TypeId, name: Symbol) -> Option<TypeId> {
847        let key = (owner, name);
848        self.host
849            .members
850            .binary_search_by(|&(o, n, _)| (o, n).cmp(&key))
851            .ok()
852            .and_then(|i| self.host.members.get(i))
853            .map(|&(_, _, t)| t)
854    }
855
856    pub(crate) fn record_path_def(&mut self, path: PathId, def: Def) {
857        if let Some(slot) = self.path_def.get_mut(path.index()) {
858            *slot = Some(def);
859        }
860    }
861
862    /// How deep the re-entrant steps (lowering through generic defaults,
863    /// normalizing associated types defined through others) may nest: the
864    /// budget's trait depth, but never more than [`NEST_CAP`], so they
865    /// stay well inside any thread's stack.
866    pub(crate) fn nest_limit(&self) -> u32 {
867        self.meter.budget.trait_depth.min(NEST_CAP)
868    }
869
870    /// Starts a new walk over items (see [`visit`](Self::visit)).
871    pub(crate) fn new_visit(&mut self) {
872        self.item_epoch = self.item_epoch.wrapping_add(1);
873        if self.item_epoch == 0 {
874            self.item_stamp.iter_mut().for_each(|s| *s = 0);
875            self.item_epoch = 1;
876        }
877    }
878
879    /// Marks `item` visited in the current walk; `false` if it already was.
880    pub(crate) fn visit(&mut self, item: ItemId) -> bool {
881        match self.item_stamp.get_mut(item.index()) {
882            Some(s) if *s == self.item_epoch => false,
883            Some(s) => {
884                *s = self.item_epoch;
885                true
886            }
887            None => false,
888        }
889    }
890
891    /// The display name of an item, remembered for type rendering.
892    pub(crate) fn name_item(&mut self, item: ItemId) {
893        if let Some(name) = self.hir.get_item(item).and_then(|it| it.name) {
894            self.types.name_item(item, name.sym);
895        }
896    }
897
898    /// An item's kind; `Err` for an id this unit did not issue (a host can
899    /// build nominal types naming any item id).
900    pub(crate) fn item_kind(&self, item: ItemId) -> hir_lang::ItemKind {
901        self.hir
902            .get_item(item)
903            .map_or(hir_lang::ItemKind::Err, |it| it.kind)
904    }
905}