Skip to main content

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}