tinymist_query/analysis/
tyck.rs

1//! Type checking on source file
2
3use std::sync::OnceLock;
4
5use rustc_hash::{FxHashMap, FxHashSet};
6use tinymist_derive::BindTyCtx;
7
8use super::{
9    BuiltinTy, DynTypeBounds, FlowVarKind, SharedContext, TyCtxMut, TypeInfo, TypeVar,
10    TypeVarBounds, prelude::*,
11};
12use crate::{
13    syntax::{Decl, DeclExpr, Expr, ExprInfo, UnaryOp},
14    ty::*,
15};
16
17mod apply;
18mod docs;
19mod select;
20mod syntax;
21
22pub(crate) use apply::*;
23pub(crate) use select::*;
24
25#[derive(Default)]
26pub struct TypeEnv {
27    visiting: FxHashMap<TypstFileId, Arc<TypeInfo>>,
28    exprs: FxHashMap<TypstFileId, Option<ExprInfo>>,
29}
30
31/// Type checking at the source unit level.
32#[typst_macros::time(span = ei.source.root().span())]
33pub(crate) fn type_check(
34    ctx: Arc<SharedContext>,
35    ei: ExprInfo,
36    env: &mut TypeEnv,
37) -> Arc<TypeInfo> {
38    let mut info = TypeInfo::default();
39    info.valid = true;
40    info.fid = Some(ei.fid);
41    info.revision = ei.revision;
42
43    env.visiting.insert(ei.fid, Arc::new(TypeInfo::default()));
44
45    // Retrieve expression information for the source.
46    let root = ei.root.clone();
47
48    let mut checker = TypeChecker {
49        ctx,
50        ei,
51        info,
52        env,
53        call_cache: Default::default(),
54        module_exports: Default::default(),
55    };
56
57    let type_check_start = tinymist_std::time::Instant::now();
58
59    checker.check(&root);
60
61    let exports = checker
62        .ei
63        .exports
64        .clone()
65        .into_iter()
66        .map(|(k, v)| (k.clone(), checker.check(v)))
67        .collect();
68    checker.info.exports = exports;
69
70    let elapsed = type_check_start.elapsed();
71    crate::log_debug_ct!("Type checking on {:?} took {elapsed:?}", checker.ei.fid);
72
73    checker.env.visiting.remove(&checker.ei.fid);
74
75    Arc::new(checker.info)
76}
77
78type CallCacheDesc = (
79    Interned<SigTy>,
80    Interned<SigTy>,
81    Option<Vec<Interned<SigTy>>>,
82);
83
84pub(crate) struct TypeChecker<'a> {
85    ctx: Arc<SharedContext>,
86    ei: ExprInfo,
87
88    info: TypeInfo,
89    module_exports: FxHashMap<(TypstFileId, Interned<str>), OnceLock<Option<Ty>>>,
90
91    call_cache: FxHashSet<CallCacheDesc>,
92
93    env: &'a mut TypeEnv,
94}
95
96impl TyCtx for TypeChecker<'_> {
97    fn global_bounds(&self, var: &Interned<TypeVar>, pol: bool) -> Option<DynTypeBounds> {
98        self.info.global_bounds(var, pol)
99    }
100
101    fn local_bind_of(&self, var: &Interned<TypeVar>) -> Option<Ty> {
102        self.info.local_bind_of(var)
103    }
104}
105
106impl TyCtxMut for TypeChecker<'_> {
107    type Snap = <TypeInfo as TyCtxMut>::Snap;
108
109    fn start_scope(&mut self) -> Self::Snap {
110        self.info.start_scope()
111    }
112
113    fn end_scope(&mut self, snap: Self::Snap) {
114        self.info.end_scope(snap)
115    }
116
117    fn bind_local(&mut self, var: &Interned<TypeVar>, ty: Ty) {
118        self.info.bind_local(var, ty);
119    }
120
121    fn type_of_func(&mut self, func: &Func) -> Option<Interned<SigTy>> {
122        Some(self.ctx.type_of_func(func.clone()).type_sig())
123    }
124
125    fn type_of_value(&mut self, val: &Value) -> Ty {
126        self.ctx.type_of_value(val)
127    }
128
129    fn check_module_item(&mut self, fid: TypstFileId, name: &StrRef) -> Option<Ty> {
130        self.module_exports
131            .entry((fid, name.clone()))
132            .or_default()
133            .clone()
134            .get_or_init(|| {
135                let ei = self
136                    .env
137                    .exprs
138                    .entry(fid)
139                    .or_insert_with(|| self.ctx.expr_stage_by_id(fid))
140                    .clone()?;
141
142                Some(self.check(ei.exports.get(name)?))
143            })
144            .clone()
145    }
146}
147
148impl TypeChecker<'_> {
149    fn check(&mut self, expr: &Expr) -> Ty {
150        self.check_syntax(expr).unwrap_or(Ty::undef())
151    }
152
153    fn copy_doc_vars(
154        &mut self,
155        fr: &TypeVarBounds,
156        var: &Interned<TypeVar>,
157        base: &Interned<Decl>,
158    ) -> Ty {
159        let mut gen_var = var.as_ref().clone();
160        let encoded = Interned::new(Decl::docs(base.clone(), var.clone()));
161        gen_var.def = encoded.clone();
162        crate::log_debug_ct!("copy var {fr:?} as {encoded:?}");
163        let bounds = TypeVarBounds::new(gen_var, fr.bounds.bounds().read().clone());
164        let var = bounds.as_type();
165        self.info.vars.insert(encoded, bounds);
166        var
167    }
168
169    fn get_var(&mut self, decl: &DeclExpr) -> Interned<TypeVar> {
170        crate::log_debug_ct!("get_var {decl:?}");
171        let entry = self.info.vars.entry(decl.clone()).or_insert_with(|| {
172            let name = decl.name().clone();
173            let decl = decl.clone();
174
175            // Check External variables
176            let init = decl.file_id().and_then(|fid| {
177                if fid == self.ei.fid {
178                    return None;
179                }
180
181                crate::log_debug_ct!("import_ty {name} from {fid:?}");
182
183                let ext_def_use_info = self.ctx.expr_stage_by_id(fid)?;
184                let source = &ext_def_use_info.source;
185                // todo: check types in cycle
186                let ext_type_info = if let Some(scheme) = self.env.visiting.get(&source.id()) {
187                    scheme.clone()
188                } else {
189                    self.ctx.clone().type_check_(source, self.env)
190                };
191                let ext_def = ext_def_use_info.exports.get(&name)?;
192
193                // todo: rest expressions
194                let def = match ext_def {
195                    Expr::Decl(decl) => {
196                        let ext_ty = ext_type_info.vars.get(decl)?.as_type();
197                        if let Some(ext_docs) = ext_type_info.var_docs.get(decl) {
198                            self.info.var_docs.insert(decl.clone(), ext_docs.clone());
199                        }
200
201                        ext_type_info.simplify(ext_ty, false)
202                    }
203                    _ => return None,
204                };
205
206                Some(ext_type_info.to_bounds(def))
207            });
208
209            TypeVarBounds::new(TypeVar { name, def: decl }, init.unwrap_or_default())
210        });
211
212        let var = entry.var.clone();
213
214        let s = decl.span();
215        if !s.is_detached() {
216            // todo: record decl types
217            // let should_record = matches!(root.kind(), SyntaxKind::FuncCall).then(||
218            // root.span());
219            // if let Some(s) = should_record {
220            //     self.info.witness_at_least(s, w.clone());
221            // }
222
223            TypeInfo::witness_(s, Ty::Var(var.clone()), &mut self.info.mapping);
224        }
225        var
226    }
227
228    fn constrain_sig_inputs(
229        &mut self,
230        sig: &Interned<SigTy>,
231        args: &Interned<SigTy>,
232        with: Option<&Vec<Interned<SigTy>>>,
233    ) {
234        let call_desc = (sig.clone(), args.clone(), with.cloned());
235        if !self.call_cache.insert(call_desc) {
236            return;
237        }
238
239        for (arg_recv, arg_ins) in sig.matches(args, with) {
240            self.constrain(arg_ins, arg_recv);
241        }
242    }
243
244    fn constrain(&mut self, lhs: &Ty, rhs: &Ty) {
245        static FLOW_STROKE_DICT_TYPE: LazyLock<Ty> =
246            LazyLock::new(|| Ty::Dict(FLOW_STROKE_DICT.clone()));
247        static FLOW_MARGIN_DICT_TYPE: LazyLock<Ty> =
248            LazyLock::new(|| Ty::Dict(FLOW_MARGIN_DICT.clone()));
249        static FLOW_INSET_DICT_TYPE: LazyLock<Ty> =
250            LazyLock::new(|| Ty::Dict(FLOW_INSET_DICT.clone()));
251        static FLOW_OUTSET_DICT_TYPE: LazyLock<Ty> =
252            LazyLock::new(|| Ty::Dict(FLOW_OUTSET_DICT.clone()));
253        static FLOW_RADIUS_DICT_TYPE: LazyLock<Ty> =
254            LazyLock::new(|| Ty::Dict(FLOW_RADIUS_DICT.clone()));
255        static FLOW_TEXT_FONT_DICT_TYPE: LazyLock<Ty> =
256            LazyLock::new(|| Ty::Dict(FLOW_TEXT_FONT_DICT.clone()));
257
258        fn is_ty(ty: &Ty) -> bool {
259            match ty {
260                Ty::Builtin(BuiltinTy::Type(..)) => true,
261                Ty::Value(val) => matches!(val.val, Value::Type(..)),
262                _ => false,
263            }
264        }
265
266        if lhs == rhs {
267            return;
268        }
269
270        match (lhs, rhs) {
271            (Ty::Var(v), Ty::Var(w)) => {
272                if v.def == w.def {
273                    return;
274                }
275
276                // todo: merge
277
278                let _ = v.def;
279                let _ = w.def;
280            }
281            (Ty::Var(v), rhs) => {
282                crate::log_debug_ct!("constrain var {v:?} ⪯ {rhs:?}");
283                let w = self.info.vars.get_mut(&v.def).unwrap();
284                // strict constraint on upper bound
285                let bound = rhs.clone();
286                match &w.bounds {
287                    FlowVarKind::Strong(w) | FlowVarKind::Weak(w) => {
288                        let mut w = w.write();
289                        w.ubs.insert_mut(bound);
290                    }
291                }
292            }
293            (lhs, Ty::Var(v)) => {
294                let w = self.info.vars.get(&v.def).unwrap();
295                let bound = self.weaken_constraint(lhs, &w.bounds);
296                crate::log_debug_ct!("constrain var {v:?} ⪰ {bound:?}");
297                match &w.bounds {
298                    FlowVarKind::Strong(v) | FlowVarKind::Weak(v) => {
299                        let mut v = v.write();
300                        v.lbs.insert_mut(bound);
301                    }
302                }
303            }
304            (Ty::Union(types), rhs) => {
305                for ty in types.iter() {
306                    self.constrain(ty, rhs);
307                }
308            }
309            (lhs, Ty::Union(types)) => {
310                for ty in types.iter() {
311                    self.constrain(lhs, ty);
312                }
313            }
314            (lhs, Ty::Builtin(BuiltinTy::Stroke)) => {
315                // empty array is also a constructing dict but we can safely ignore it during
316                // type checking, since no fields are added yet.
317                if lhs.is_dict() {
318                    self.constrain(lhs, &FLOW_STROKE_DICT_TYPE);
319                }
320            }
321            (Ty::Builtin(BuiltinTy::Stroke), rhs) => {
322                if rhs.is_dict() {
323                    self.constrain(&FLOW_STROKE_DICT_TYPE, rhs);
324                }
325            }
326            (lhs, Ty::Builtin(BuiltinTy::Margin)) => {
327                if lhs.is_dict() {
328                    self.constrain(lhs, &FLOW_MARGIN_DICT_TYPE);
329                }
330            }
331            (Ty::Builtin(BuiltinTy::Margin), rhs) => {
332                if rhs.is_dict() {
333                    self.constrain(&FLOW_MARGIN_DICT_TYPE, rhs);
334                }
335            }
336            (lhs, Ty::Builtin(BuiltinTy::Inset)) => {
337                if lhs.is_dict() {
338                    self.constrain(lhs, &FLOW_INSET_DICT_TYPE);
339                }
340            }
341            (Ty::Builtin(BuiltinTy::Inset), rhs) => {
342                if rhs.is_dict() {
343                    self.constrain(&FLOW_INSET_DICT_TYPE, rhs);
344                }
345            }
346            (lhs, Ty::Builtin(BuiltinTy::Outset)) => {
347                if lhs.is_dict() {
348                    self.constrain(lhs, &FLOW_OUTSET_DICT_TYPE);
349                }
350            }
351            (Ty::Builtin(BuiltinTy::Outset), rhs) => {
352                if rhs.is_dict() {
353                    self.constrain(&FLOW_OUTSET_DICT_TYPE, rhs);
354                }
355            }
356            (lhs, Ty::Builtin(BuiltinTy::Radius)) => {
357                if lhs.is_dict() {
358                    self.constrain(lhs, &FLOW_RADIUS_DICT_TYPE);
359                }
360            }
361            (Ty::Builtin(BuiltinTy::Radius), rhs) => {
362                if rhs.is_dict() {
363                    self.constrain(&FLOW_RADIUS_DICT_TYPE, rhs);
364                }
365            }
366            (lhs, Ty::Builtin(BuiltinTy::TextFont)) => {
367                if lhs.is_dict() {
368                    self.constrain(lhs, &FLOW_TEXT_FONT_DICT_TYPE);
369                }
370            }
371            (Ty::Builtin(BuiltinTy::TextFont), rhs) => {
372                if rhs.is_dict() {
373                    self.constrain(&FLOW_TEXT_FONT_DICT_TYPE, rhs);
374                }
375            }
376            (Ty::Dict(lhs), Ty::Dict(rhs)) => {
377                for (key, lhs, rhs) in lhs.common_iface_fields(rhs) {
378                    crate::log_debug_ct!("constrain record item {key} {lhs:?} ⪯ {rhs:?}");
379                    self.constrain(lhs, rhs);
380                    // if !sl.is_detached() {
381                    //     self.info.witness_at_most(*sl, rhs.clone());
382                    // }
383                    // if !sr.is_detached() {
384                    //     self.info.witness_at_least(*sr, lhs.clone());
385                    // }
386                }
387            }
388            (Ty::Unary(lhs), Ty::Unary(rhs)) if lhs.op == rhs.op => {
389                // todo: more information could be extracted from unary constraint structure
390                // e.g. type(l) == type(r)
391                self.constrain(&lhs.lhs, &rhs.lhs);
392            }
393            (Ty::Unary(lhs), rhs) if lhs.op == UnaryOp::TypeOf && is_ty(rhs) => {
394                crate::log_debug_ct!("constrain type of {lhs:?} ⪯ {rhs:?}");
395
396                self.constrain(&lhs.lhs, rhs);
397            }
398            (lhs, Ty::Unary(rhs)) if rhs.op == UnaryOp::TypeOf && is_ty(lhs) => {
399                crate::log_debug_ct!(
400                    "constrain type of {lhs:?} ⪯ {rhs:?} {:?}",
401                    matches!(lhs, Ty::Builtin(..)),
402                );
403                self.constrain(lhs, &rhs.lhs);
404            }
405            (Ty::Func(lhs), Ty::Func(rhs)) => {
406                crate::log_debug_ct!("constrain func {lhs:?} ⪯ {rhs:?}");
407                self.constrain_sig_inputs(lhs, rhs, None);
408            }
409            (Ty::Value(lhs), rhs) => {
410                crate::log_debug_ct!("constrain value {lhs:?} ⪯ {rhs:?}");
411                let _ = TypeInfo::witness_at_most;
412                // if !lhs.1.is_detached() {
413                //     self.info.witness_at_most(lhs.1, rhs.clone());
414                // }
415            }
416            (lhs, Ty::Value(rhs)) => {
417                crate::log_debug_ct!("constrain value {lhs:?} ⪯ {rhs:?}");
418                // if !rhs.1.is_detached() {
419                //     self.info.witness_at_least(rhs.1, lhs.clone());
420                // }
421            }
422            _ => {
423                crate::log_debug_ct!("constrain {lhs:?} ⪯ {rhs:?}");
424            }
425        }
426    }
427
428    fn check_comparable(&self, lhs: &Ty, rhs: &Ty) {
429        let _ = lhs;
430        let _ = rhs;
431    }
432
433    fn check_assignable(&self, lhs: &Ty, rhs: &Ty) {
434        let _ = lhs;
435        let _ = rhs;
436    }
437
438    fn check_containing(&mut self, container: &Ty, elem: &Ty, expected_in: bool) {
439        let rhs = if expected_in {
440            match container {
441                Ty::Tuple(elements) => Ty::Union(elements.clone()),
442                _ => Ty::Unary(TypeUnary::new(UnaryOp::ElementOf, container.clone())),
443            }
444        } else {
445            // todo: remove not element of
446            Ty::Unary(TypeUnary::new(UnaryOp::NotElementOf, container.clone()))
447        };
448
449        self.constrain(elem, &rhs);
450    }
451
452    fn possible_ever_be(&mut self, lhs: &Ty, rhs: &Ty) {
453        // todo: instantiataion
454        match rhs {
455            Ty::Builtin(..) | Ty::Value(..) | Ty::Boolean(..) => {
456                self.constrain(rhs, lhs);
457            }
458            _ => {}
459        }
460    }
461
462    fn weaken(&mut self, v: &Ty) {
463        match v {
464            Ty::Var(v) => {
465                let w = self.info.vars.get_mut(&v.def).unwrap();
466                w.weaken();
467            }
468            Ty::Any | Ty::Boolean(_) | Ty::Builtin(_) | Ty::Value(_) => {}
469            Ty::Param(v) => {
470                self.weaken(&v.ty);
471            }
472            Ty::Func(v) | Ty::Args(v) | Ty::Pattern(v) => {
473                for ty in v.inputs() {
474                    self.weaken(ty);
475                }
476            }
477            Ty::With(v) => {
478                self.weaken(&v.sig);
479                for ty in v.with.inputs() {
480                    self.weaken(ty);
481                }
482            }
483            Ty::Dict(v) => {
484                for (_, ty) in v.interface() {
485                    self.weaken(ty);
486                }
487            }
488            Ty::Array(v) => {
489                self.weaken(v);
490            }
491            Ty::Tuple(v) => {
492                for ty in v.iter() {
493                    self.weaken(ty);
494                }
495            }
496            Ty::Select(v) => {
497                self.weaken(&v.ty);
498            }
499            Ty::Unary(v) => {
500                self.weaken(&v.lhs);
501            }
502            Ty::Binary(v) => {
503                let [lhs, rhs] = v.operands();
504                self.weaken(lhs);
505                self.weaken(rhs);
506            }
507            Ty::If(v) => {
508                self.weaken(&v.cond);
509                self.weaken(&v.then);
510                self.weaken(&v.else_);
511            }
512            Ty::Union(v) => {
513                for ty in v.iter() {
514                    self.weaken(ty);
515                }
516            }
517            Ty::Let(v) => {
518                for ty in v.lbs.iter() {
519                    self.weaken(ty);
520                }
521                for ty in v.ubs.iter() {
522                    self.weaken(ty);
523                }
524            }
525        }
526    }
527
528    fn weaken_constraint(&self, term: &Ty, kind: &FlowVarKind) -> Ty {
529        if matches!(kind, FlowVarKind::Strong(_)) {
530            return term.clone();
531        }
532
533        if let Ty::Value(ins_ty) = term {
534            return BuiltinTy::from_value(&ins_ty.val);
535        }
536
537        term.clone()
538    }
539}
540
541struct Joiner {
542    break_or_continue_or_return: bool,
543    definite: Ty,
544    possibles: Vec<Ty>,
545}
546impl Joiner {
547    fn finalize(self) -> Ty {
548        crate::log_debug_ct!("join: {:?} {:?}", self.possibles, self.definite);
549        if self.possibles.is_empty() {
550            return self.definite;
551        }
552        if self.possibles.len() == 1 {
553            return self.possibles.into_iter().next().unwrap();
554        }
555
556        // let mut definite = self.definite.clone();
557        // for p in &self.possibles {
558        //     definite = definite.join(p);
559        // }
560
561        // crate::log_debug_ct!("possibles: {:?} {:?}", self.definite, self.possibles);
562
563        Ty::Any
564    }
565
566    fn join(&mut self, child: Ty) {
567        if self.break_or_continue_or_return {
568            return;
569        }
570
571        match (child, &self.definite) {
572            (Ty::Builtin(BuiltinTy::Space | BuiltinTy::None), _) => {}
573            (Ty::Builtin(BuiltinTy::Clause | BuiltinTy::FlowNone), _) => {}
574            (Ty::Any, _) | (_, Ty::Any) => {}
575            (Ty::Var(var), _) => self.possibles.push(Ty::Var(var)),
576            // todo: check possibles
577            (Ty::Array(arr), Ty::Builtin(BuiltinTy::None)) => self.definite = Ty::Array(arr),
578            (Ty::Array(..), _) => self.definite = Ty::undef(),
579            (Ty::Tuple(elems), Ty::Builtin(BuiltinTy::None)) => self.definite = Ty::Tuple(elems),
580            (Ty::Tuple(..), _) => self.definite = Ty::undef(),
581            // todo: mystery flow none
582            // todo: possible some style (auto)
583            (Ty::Builtin(ty), Ty::Builtin(BuiltinTy::None)) => self.definite = Ty::Builtin(ty),
584            (Ty::Builtin(..), _) => self.definite = Ty::undef(),
585            // todo: value join
586            (Ty::Value(ins_ty), Ty::Builtin(BuiltinTy::None)) => self.definite = Ty::Value(ins_ty),
587            (Ty::Value(..), _) => self.definite = Ty::undef(),
588            (Ty::Func(func), Ty::Builtin(BuiltinTy::None)) => self.definite = Ty::Func(func),
589            (Ty::Func(..), _) => self.definite = Ty::undef(),
590            (Ty::Dict(dict), Ty::Builtin(BuiltinTy::None)) => self.definite = Ty::Dict(dict),
591            (Ty::Dict(..), _) => self.definite = Ty::undef(),
592            (Ty::With(with), Ty::Builtin(BuiltinTy::None)) => self.definite = Ty::With(with),
593            (Ty::With(..), _) => self.definite = Ty::undef(),
594            (Ty::Args(args), Ty::Builtin(BuiltinTy::None)) => self.definite = Ty::Args(args),
595            (Ty::Args(..), _) => self.definite = Ty::undef(),
596            (Ty::Pattern(pat), Ty::Builtin(BuiltinTy::None)) => self.definite = Ty::Pattern(pat),
597            (Ty::Pattern(..), _) => self.definite = Ty::undef(),
598            (Ty::Select(sel), Ty::Builtin(BuiltinTy::None)) => self.definite = Ty::Select(sel),
599            (Ty::Select(..), _) => self.definite = Ty::undef(),
600            (Ty::Unary(unary), Ty::Builtin(BuiltinTy::None)) => self.definite = Ty::Unary(unary),
601            (Ty::Unary(..), _) => self.definite = Ty::undef(),
602            (Ty::Binary(binary), Ty::Builtin(BuiltinTy::None)) => {
603                self.definite = Ty::Binary(binary)
604            }
605            (Ty::Binary(..), _) => self.definite = Ty::undef(),
606            (Ty::If(if_ty), Ty::Builtin(BuiltinTy::None)) => self.definite = Ty::If(if_ty),
607            (Ty::If(..), _) => self.definite = Ty::undef(),
608            (Ty::Union(types), Ty::Builtin(BuiltinTy::None)) => self.definite = Ty::Union(types),
609            (Ty::Union(..), _) => self.definite = Ty::undef(),
610            (Ty::Let(bounds), Ty::Builtin(BuiltinTy::None)) => self.definite = Ty::Let(bounds),
611            (Ty::Let(..), _) => self.definite = Ty::undef(),
612            (Ty::Param(param), Ty::Builtin(BuiltinTy::None)) => self.definite = Ty::Param(param),
613            (Ty::Param(..), _) => self.definite = Ty::undef(),
614            (Ty::Boolean(b), Ty::Builtin(BuiltinTy::None)) => self.definite = Ty::Boolean(b),
615            (Ty::Boolean(..), _) => self.definite = Ty::undef(),
616        }
617    }
618}
619impl Default for Joiner {
620    fn default() -> Self {
621        Self {
622            break_or_continue_or_return: false,
623            definite: Ty::Builtin(BuiltinTy::None),
624            possibles: Vec::new(),
625        }
626    }
627}
tinymist_query/analysis/tyck.rs

tinymist_query/analysis/
tyck.rs
