typeck_lang/error.rs
1//! Why a check could not run to completion, and the budgets that bound it.
2//!
3//! Type errors in the program are not errors of the check: they are
4//! [`Diagnostic`](crate::Diagnostic)s in a successful [`Typed`](crate::Typed).
5//! A [`CheckError`] means the checker refused to start or stopped early.
6
7use core::fmt;
8
9use hir_lang::{Hir, IdKind};
10
11use crate::profile::Discipline;
12
13/// Limits on the work one check may do.
14///
15/// Every algorithm in the checker is linear or near-linear in the HIR and its
16/// types, so these are not expected to bind on real programs; they turn a
17/// hostile or pathological input into an error instead of a hang or an
18/// out-of-memory abort.
19///
20/// # Examples
21///
22/// ```
23/// use typeck_lang::Budget;
24///
25/// let tight = Budget { steps: 10_000, ..Budget::default() };
26/// assert_eq!(tight.steps, 10_000);
27/// ```
28#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
29pub struct Budget {
30 /// Checker steps: one per task, unification pair, occurs-check visit,
31 /// constant-evaluation step, and pattern node.
32 pub steps: u64,
33 /// Type-store size: nodes plus pooled children.
34 pub type_nodes: usize,
35 /// How deep interface resolution may nest: goals arising from the
36 /// bounds of the implementation that satisfies another goal,
37 /// associated types defined through other associated types, and the
38 /// chain of generic instances in the monomorphization plan. A cyclic or
39 /// ever-growing resolution reaches it instead of looping.
40 pub trait_depth: u32,
41}
42
43impl Default for Budget {
44 /// 50 million steps, 64 million type-store entries, and a trait depth
45 /// of 256.
46 fn default() -> Self {
47 Self {
48 steps: 50_000_000,
49 type_nodes: 1 << 26,
50 trait_depth: 256,
51 }
52 }
53}
54
55impl Budget {
56 /// A budget scaled to `hir`: a fixed floor plus 256 steps and 64 type
57 /// entries per HIR node, never less than [`Budget::default`].
58 ///
59 /// # Examples
60 ///
61 /// ```
62 /// use hir_lang::Builder;
63 /// use typeck_lang::Budget;
64 ///
65 /// let mut b = Builder::new();
66 /// let root = b.module(None, &[]);
67 /// let hir = b.finish(root)?;
68 /// assert_eq!(Budget::for_hir(&hir), Budget::default());
69 /// # Ok::<(), hir_lang::HirError>(())
70 /// ```
71 #[must_use]
72 pub fn for_hir(hir: &Hir) -> Self {
73 let nodes: usize = [
74 IdKind::Item,
75 IdKind::Expr,
76 IdKind::Stmt,
77 IdKind::Pat,
78 IdKind::Ty,
79 IdKind::Path,
80 IdKind::Field,
81 IdKind::Variant,
82 IdKind::Param,
83 IdKind::Binder,
84 ]
85 .into_iter()
86 .map(|k| hir.count(k))
87 .sum();
88 let base = Self::default();
89 Self {
90 steps: base.steps.max((nodes as u64).saturating_mul(256)),
91 type_nodes: base.type_nodes.max(nodes.saturating_mul(64)),
92 trait_depth: base.trait_depth,
93 }
94 }
95}
96
97/// Which budget ran out.
98///
99/// # Examples
100///
101/// ```
102/// use typeck_lang::Limit;
103///
104/// assert_ne!(Limit::Steps, Limit::TypeNodes);
105/// ```
106#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
107#[non_exhaustive]
108pub enum Limit {
109 /// [`Budget::steps`].
110 Steps,
111 /// [`Budget::type_nodes`].
112 TypeNodes,
113 /// [`Budget::trait_depth`].
114 TraitDepth,
115}
116
117/// Why a check did not produce a [`Typed`](crate::Typed).
118///
119/// # Examples
120///
121/// ```
122/// use hir_lang::Builder;
123/// use typeck_lang::{check, CheckError, Discipline, Profile};
124///
125/// let mut b = Builder::new();
126/// let root = b.module(None, &[]);
127/// let hir = b.finish(root)?;
128/// let err = check(&hir, &Profile::hm()).unwrap_err();
129/// assert_eq!(err, CheckError::NotImplemented { discipline: Discipline::Hm });
130/// # Ok::<(), hir_lang::HirError>(())
131/// ```
132#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
133#[non_exhaustive]
134pub enum CheckError {
135 /// The profile's discipline is designed but not implemented in this
136 /// version (see [`Discipline::is_implemented`]). Use `Dynamic`,
137 /// `StaticExplicit`, or `StaticInferred`, or a later version of the
138 /// crate.
139 NotImplemented {
140 /// The requested discipline.
141 discipline: Discipline,
142 },
143 /// The profile is inconsistent: `default_int` is not an integer type or
144 /// `default_float` not a float type. Fix the profile.
145 InvalidProfile,
146 /// A budget ran out before the check finished. The input is pathological
147 /// or hostile; raise the budget only if the program is trusted and
148 /// genuinely that large.
149 BudgetExceeded {
150 /// Which limit.
151 limit: Limit,
152 },
153}
154
155impl fmt::Display for CheckError {
156 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
157 match self {
158 Self::NotImplemented { discipline } => write!(
159 f,
160 "the `{}` discipline is not implemented in this version",
161 discipline.name()
162 ),
163 Self::InvalidProfile => f.write_str(
164 "invalid profile: the literal defaults must be an integer and a float type",
165 ),
166 Self::BudgetExceeded { limit } => write!(
167 f,
168 "type checking exceeded its {} budget",
169 match limit {
170 Limit::Steps => "step",
171 Limit::TypeNodes => "type-store",
172 Limit::TraitDepth => "trait-resolution depth",
173 }
174 ),
175 }
176 }
177}
178
179#[cfg(feature = "std")]
180impl std::error::Error for CheckError {}
181
182/// The running step count against a budget.
183#[derive(Clone, Copy, Debug)]
184pub(crate) struct Meter {
185 pub(crate) used: u64,
186 pub(crate) budget: Budget,
187}
188
189impl Meter {
190 pub(crate) const fn new(budget: Budget) -> Self {
191 Self { used: 0, budget }
192 }
193
194 /// Charges `n` steps.
195 #[inline]
196 pub(crate) fn tick(&mut self, n: u64) -> Result<(), CheckError> {
197 self.used = self.used.saturating_add(n);
198 if self.used > self.budget.steps {
199 Err(CheckError::BudgetExceeded {
200 limit: Limit::Steps,
201 })
202 } else {
203 Ok(())
204 }
205 }
206}