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}