tinymist_analysis/ty/
bound.rs

1use std::ops::Deref;
2
3use typst::foundations::{self, Func};
4
5use crate::syntax::DeclExpr;
6use crate::ty::prelude::*;
7
8/// A trait for checking the bounds of a type.
9pub trait BoundChecker: Sized + TyCtx {
10    /// Collects the bounds of a type.
11    fn collect(&mut self, ty: &Ty, pol: bool);
12
13    /// Checks the bounds of a variable.
14    fn check_var(&mut self, u: &Interned<TypeVar>, pol: bool, ctx: &mut BoundCheckContext) {
15        ctx.check_var_rec(u, pol, self);
16    }
17
18    /// Checks the bounds of a variable recursively.
19    fn check_var_rec(&mut self, u: &Interned<TypeVar>, pol: bool) {
20        let mut ctx = BoundCheckContext::default();
21        ctx.check_var_rec(u, pol, self);
22    }
23}
24
25/// A predicate for checking the bounds of a type.
26#[derive(BindTyCtx)]
27#[bind(0)]
28pub struct BoundPred<'a, T: TyCtx, F>(pub &'a T, pub F);
29
30impl<'a, T: TyCtx, F> BoundPred<'a, T, F> {
31    /// Creates a new bound predicate.
32    pub fn new(t: &'a T, f: F) -> Self {
33        Self(t, f)
34    }
35}
36
37impl<T: TyCtx, F> BoundChecker for BoundPred<'_, T, F>
38where
39    F: FnMut(&Ty, bool),
40{
41    fn collect(&mut self, ty: &Ty, pol: bool) {
42        self.1(ty, pol);
43    }
44}
45
46/// A source of documentation.
47#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
48pub enum DocSource {
49    /// A variable source.
50    Var(Interned<TypeVar>),
51    /// An (value) instance source.
52    Ins(Interned<InsTy>),
53    /// A builtin type source.
54    Builtin(BuiltinTy),
55}
56
57impl DocSource {
58    /// Casts doc source to a function.
59    pub fn as_func(&self) -> Option<Func> {
60        match self {
61            Self::Var(..) => None,
62            Self::Builtin(BuiltinTy::Type(ty)) => Some(ty.constructor().ok()?),
63            Self::Builtin(BuiltinTy::Element(ty)) => Some((*ty).into()),
64            Self::Builtin(..) => None,
65            Self::Ins(ins_ty) => match &ins_ty.val {
66                foundations::Value::Func(func) => Some(func.clone()),
67                foundations::Value::Type(ty) => Some(ty.constructor().ok()?),
68                _ => None,
69            },
70        }
71    }
72}
73
74impl Ty {
75    /// Checks if the given type has bounds (is combinated).
76    pub fn has_bounds(&self) -> bool {
77        matches!(self, Ty::Union(_) | Ty::Let(_) | Ty::Var(_))
78    }
79
80    /// Converts a type to doc source.
81    pub fn as_source(&self) -> Option<DocSource> {
82        match self {
83            Ty::Builtin(ty @ (BuiltinTy::Type(..) | BuiltinTy::Element(..))) => {
84                Some(DocSource::Builtin(ty.clone()))
85            }
86            Ty::Value(ty) => match &ty.val {
87                foundations::Value::Type(..) | foundations::Value::Func(..) => {
88                    Some(DocSource::Ins(ty.clone()))
89                }
90                _ => None,
91            },
92            _ => None,
93        }
94    }
95
96    /// Gets the sources of the given type.
97    pub fn sources(&self) -> Vec<DocSource> {
98        let mut results = vec![];
99        fn collect(ty: &Ty, results: &mut Vec<DocSource>) {
100            use Ty::*;
101            if let Some(src) = ty.as_source() {
102                results.push(src);
103                return;
104            }
105            match ty {
106                Any | Boolean(_) | If(..) | Builtin(..) | Value(..) => {}
107                Dict(..) | Array(..) | Tuple(..) | Func(..) | Args(..) | Pattern(..) => {}
108                Unary(..) | Binary(..) => {}
109                Param(ty) => {
110                    // todo: doc source can be param ty
111                    collect(&ty.ty, results);
112                }
113                Union(ty) => {
114                    for ty in ty.iter() {
115                        collect(ty, results);
116                    }
117                }
118                Let(ty) => {
119                    for ty in ty.ubs.iter() {
120                        collect(ty, results);
121                    }
122                    for ty in ty.lbs.iter() {
123                        collect(ty, results);
124                    }
125                }
126                Var(ty) => {
127                    results.push(DocSource::Var(ty.clone()));
128                }
129                With(ty) => collect(&ty.sig, results),
130                Select(ty) => {
131                    // todo: do this correctly
132                    if matches!(ty.select.deref(), "with" | "where") {
133                        collect(&ty.ty, results);
134                    }
135
136                    // collect(&ty.ty, results)
137                }
138            }
139        }
140
141        collect(self, &mut results);
142        results
143    }
144
145    /// Profiles the bounds of the given type.
146    pub fn bounds(&self, pol: bool, checker: &mut impl BoundChecker) {
147        let mut ctx = BoundCheckContext::default();
148        ctx.ty(self, pol, checker);
149    }
150}
151
152/// A context for checking the bounds of a type.
153#[derive(Default)]
154pub struct BoundCheckContext {
155    visiting: FxHashSet<(DeclExpr, bool)>,
156    steps: usize,
157}
158
159impl BoundCheckContext {
160    const STEP_BUDGET: usize = 100_000;
161
162    fn enter(&mut self) -> bool {
163        self.steps += 1;
164        self.steps <= Self::STEP_BUDGET
165    }
166
167    /// Checks the bounds of multiple types.
168    fn tys<'a>(&mut self, tys: impl Iterator<Item = &'a Ty>, pol: bool, c: &mut impl BoundChecker) {
169        for ty in tys {
170            self.ty(ty, pol, c);
171        }
172    }
173
174    /// Recursively checks a variable while preserving this traversal's cycle guard.
175    pub fn check_var_rec(
176        &mut self,
177        u: &Interned<TypeVar>,
178        pol: bool,
179        checker: &mut impl BoundChecker,
180    ) {
181        if !self.enter() {
182            return;
183        }
184
185        let key = (u.def.clone(), pol);
186        if !self.visiting.insert(key.clone()) {
187            return;
188        }
189
190        if let Some(w) = checker.global_bounds(u, pol) {
191            self.tys(w.ubs.iter(), pol, checker);
192            self.tys(w.lbs.iter(), !pol, checker);
193        }
194
195        self.visiting.remove(&key);
196    }
197
198    /// Checks the bounds of a type.
199    fn ty(&mut self, ty: &Ty, pol: bool, checker: &mut impl BoundChecker) {
200        if !self.enter() {
201            return;
202        }
203
204        match ty {
205            Ty::Union(u) => {
206                self.tys(u.iter(), pol, checker);
207            }
208            Ty::Let(u) => {
209                self.tys(u.ubs.iter(), pol, checker);
210                self.tys(u.lbs.iter(), !pol, checker);
211            }
212            Ty::Var(u) => checker.check_var(u, pol, self),
213            // todo: calculate these operators
214            // Ty::Select(_) => {}
215            // Ty::Unary(_) => {}
216            // Ty::Binary(_) => {}
217            // Ty::If(_) => {}
218            ty => checker.collect(ty, pol),
219        }
220    }
221}
222
223#[cfg(test)]
224mod tests {
225    use super::*;
226    use crate::syntax::Decl;
227
228    struct HookChecker {
229        bounds: FxHashMap<DeclExpr, DynTypeBounds>,
230        hooks: Vec<DeclExpr>,
231    }
232
233    impl TyCtx for HookChecker {
234        fn local_bind_of(&self, _var: &Interned<TypeVar>) -> Option<Ty> {
235            None
236        }
237
238        fn global_bounds(&self, var: &Interned<TypeVar>, _pol: bool) -> Option<DynTypeBounds> {
239            self.bounds.get(&var.def).cloned()
240        }
241    }
242
243    impl BoundChecker for HookChecker {
244        fn collect(&mut self, _ty: &Ty, _pol: bool) {}
245
246        fn check_var(&mut self, var: &Interned<TypeVar>, pol: bool, ctx: &mut BoundCheckContext) {
247            self.hooks.push(var.def.clone());
248            ctx.check_var_rec(var, pol, self);
249        }
250    }
251
252    #[test]
253    fn custom_var_hook_preserves_cycle_guard() {
254        let a = TypeVar::new("a".into(), Decl::lit("a").into());
255        let b = TypeVar::new("b".into(), Decl::lit("b").into());
256
257        let mut a_bounds = DynTypeBounds::default();
258        a_bounds.ubs.insert_mut(Ty::Var(b.clone()));
259        let mut b_bounds = DynTypeBounds::default();
260        b_bounds.ubs.insert_mut(Ty::Var(a.clone()));
261
262        let mut checker = HookChecker {
263            bounds: [(a.def.clone(), a_bounds), (b.def.clone(), b_bounds)]
264                .into_iter()
265                .collect(),
266            hooks: vec![],
267        };
268
269        Ty::Var(a.clone()).bounds(true, &mut checker);
270
271        assert_eq!(
272            checker.hooks,
273            vec![a.def.clone(), b.def.clone(), a.def.clone()]
274        );
275    }
276}
tinymist_analysis/ty/bound.rs

tinymist_analysis/ty/
bound.rs
