tinymist_analysis/ty/
simplify.rs

1#![allow(unused)]
2
3use ecow::EcoVec;
4
5use crate::{syntax::DeclExpr, ty::prelude::*};
6
7/// A compact type.
8#[derive(Default)]
9struct CompactTy {
10    equiv_vars: HashSet<DefId>,
11    primitives: HashSet<Ty>,
12    recursives: HashMap<DefId, CompactTy>,
13    signatures: Vec<Interned<SigTy>>,
14
15    is_final: bool,
16}
17
18impl TypeInfo {
19    /// Simplifies (canonicalizes) the given type with the given type scheme.
20    pub fn simplify(&self, ty: Ty, principal: bool) -> Ty {
21        let mut cache = self.cano_cache.lock();
22        let cache = &mut *cache;
23
24        cache.transform_cache.clear();
25        cache.cano_local_cache.clear();
26        cache.positives.clear();
27        cache.negatives.clear();
28
29        let mut worker = TypeSimplifier {
30            principal,
31            vars: &self.vars,
32            cano_cache: &mut cache.cano_cache,
33            transform_cache: &mut cache.transform_cache,
34            cano_local_cache: &mut cache.cano_local_cache,
35
36            positives: &mut cache.positives,
37            negatives: &mut cache.negatives,
38        };
39
40        worker.simplify(ty, principal)
41    }
42}
43
44/// A simplifier to simplify a type.
45struct TypeSimplifier<'a, 'b> {
46    principal: bool,
47
48    vars: &'a FxHashMap<DeclExpr, TypeVarBounds>,
49
50    cano_cache: &'b mut FxHashMap<(Ty, bool), Ty>,
51    transform_cache: &'b mut FxHashMap<(Ty, bool), Ty>,
52    cano_local_cache: &'b mut FxHashMap<(DeclExpr, bool), Ty>,
53    negatives: &'b mut FxHashSet<DeclExpr>,
54    positives: &'b mut FxHashSet<DeclExpr>,
55}
56
57impl TypeSimplifier<'_, '_> {
58    /// Simplifies the given type.
59    fn simplify(&mut self, ty: Ty, principal: bool) -> Ty {
60        if let Some(cano) = self.cano_cache.get(&(ty.clone(), principal)) {
61            return cano.clone();
62        }
63
64        self.analyze(&ty, true);
65        let cano = self.transform(&ty, true);
66        self.cano_cache.insert((ty, principal), cano.clone());
67        cano
68    }
69
70    /// Analyzes the given type.
71    fn analyze(&mut self, ty: &Ty, pol: bool) {
72        match ty {
73            Ty::Var(var) => {
74                let w = self.vars.get(&var.def).unwrap();
75                match &w.bounds {
76                    FlowVarKind::Strong(w) | FlowVarKind::Weak(w) => {
77                        let bounds = w.read();
78                        let inserted = if pol {
79                            self.positives.insert(var.def.clone())
80                        } else {
81                            self.negatives.insert(var.def.clone())
82                        };
83                        if !inserted {
84                            return;
85                        }
86
87                        if pol {
88                            for lb in bounds.lbs.iter() {
89                                self.analyze(lb, pol);
90                            }
91                        } else {
92                            for ub in bounds.ubs.iter() {
93                                self.analyze(ub, pol);
94                            }
95                        }
96                    }
97                }
98            }
99            Ty::Func(func) => {
100                for input_ty in func.inputs() {
101                    self.analyze(input_ty, !pol);
102                }
103                if let Some(ret_ty) = &func.body {
104                    self.analyze(ret_ty, pol);
105                }
106            }
107            Ty::Dict(record) => {
108                for member in record.types.iter() {
109                    self.analyze(member, pol);
110                }
111            }
112            Ty::Tuple(elems) => {
113                for elem in elems.iter() {
114                    self.analyze(elem, pol);
115                }
116            }
117            Ty::Array(arr) => {
118                self.analyze(arr, pol);
119            }
120            Ty::With(with) => {
121                self.analyze(&with.sig, pol);
122                for input in with.with.inputs() {
123                    self.analyze(input, pol);
124                }
125            }
126            Ty::Args(args) => {
127                for input in args.inputs() {
128                    self.analyze(input, pol);
129                }
130            }
131            Ty::Pattern(pat) => {
132                for input in pat.inputs() {
133                    self.analyze(input, pol);
134                }
135            }
136            Ty::Unary(unary) => self.analyze(&unary.lhs, pol),
137            Ty::Binary(binary) => {
138                let [lhs, rhs] = binary.operands();
139                self.analyze(lhs, pol);
140                self.analyze(rhs, pol);
141            }
142            Ty::If(if_expr) => {
143                self.analyze(&if_expr.cond, pol);
144                self.analyze(&if_expr.then, pol);
145                self.analyze(&if_expr.else_, pol);
146            }
147            Ty::Union(types) => {
148                for ty in types.iter() {
149                    self.analyze(ty, pol);
150                }
151            }
152            Ty::Select(select) => {
153                self.analyze(&select.ty, pol);
154            }
155            Ty::Let(bounds) => {
156                for lb in bounds.lbs.iter() {
157                    self.analyze(lb, !pol);
158                }
159                for ub in bounds.ubs.iter() {
160                    self.analyze(ub, pol);
161                }
162            }
163            Ty::Param(param) => {
164                self.analyze(&param.ty, pol);
165            }
166            Ty::Value(_v) => {}
167            Ty::Any => {}
168            Ty::Boolean(_) => {}
169            Ty::Builtin(_) => {}
170        }
171    }
172
173    /// Transforms the given type.
174    fn transform(&mut self, ty: &Ty, pol: bool) -> Ty {
175        if let Some(cano) = self.transform_cache.get(&(ty.clone(), pol)) {
176            return cano.clone();
177        }
178
179        let cano = match ty {
180            Ty::Let(bounds) => self.transform_let(bounds.lbs.iter(), bounds.ubs.iter(), None, pol),
181            Ty::Var(var) => {
182                if let Some(cano) = self
183                    .cano_local_cache
184                    .get(&(var.def.clone(), self.principal))
185                {
186                    return cano.clone();
187                }
188                // todo: avoid cycle
189                self.cano_local_cache
190                    .insert((var.def.clone(), self.principal), Ty::Any);
191
192                let res = match &self.vars.get(&var.def).unwrap().bounds {
193                    FlowVarKind::Strong(w) | FlowVarKind::Weak(w) => {
194                        let w = w.read();
195
196                        self.transform_let(w.lbs.iter(), w.ubs.iter(), Some(&var.def), pol)
197                    }
198                };
199
200                self.cano_local_cache
201                    .insert((var.def.clone(), self.principal), res.clone());
202
203                res
204            }
205            Ty::Func(func) => Ty::Func(self.transform_sig(func, pol)),
206            Ty::Dict(record) => {
207                let mut mutated = record.as_ref().clone();
208                mutated.types = self.transform_seq(&mutated.types, pol);
209
210                Ty::Dict(mutated.into())
211            }
212            Ty::Tuple(tup) => Ty::Tuple(self.transform_seq(tup, pol)),
213            Ty::Array(arr) => Ty::Array(self.transform(arr, pol).into()),
214            Ty::With(with) => {
215                let sig = self.transform(&with.sig, pol).into();
216                // Negate the pol to make correct covariance
217                let mutated = self.transform_sig(&with.with, !pol);
218
219                Ty::With(SigWithTy::new(sig, mutated))
220            }
221            // Negate the pol to make correct covariance
222            // todo: negate?
223            Ty::Args(args) => Ty::Args(self.transform_sig(args, !pol)),
224            Ty::Pattern(pat) => Ty::Pattern(self.transform_sig(pat, !pol)),
225            Ty::Unary(unary) => {
226                Ty::Unary(TypeUnary::new(unary.op, self.transform(&unary.lhs, pol)))
227            }
228            Ty::Binary(binary) => {
229                let [lhs, rhs] = binary.operands();
230                let lhs = self.transform(lhs, pol);
231                let rhs = self.transform(rhs, pol);
232
233                Ty::Binary(TypeBinary::new(binary.op, lhs, rhs))
234            }
235            Ty::If(if_ty) => Ty::If(IfTy::new(
236                self.transform(&if_ty.cond, pol).into(),
237                self.transform(&if_ty.then, pol).into(),
238                self.transform(&if_ty.else_, pol).into(),
239            )),
240            Ty::Union(types) => {
241                let seq = types.iter().map(|ty| self.transform(ty, pol));
242                let seq_no_any = seq.filter(|ty| !matches!(ty, Ty::Any));
243                let seq = seq_no_any.collect::<Vec<_>>();
244                Ty::from_types(seq.into_iter())
245            }
246            Ty::Param(param) => {
247                let mut param = param.as_ref().clone();
248                param.ty = self.transform(&param.ty, pol);
249
250                Ty::Param(param.into())
251            }
252            Ty::Select(sel) => {
253                let mut sel = sel.as_ref().clone();
254                sel.ty = self.transform(&sel.ty, pol).into();
255
256                Ty::Select(sel.into())
257            }
258
259            Ty::Value(ins_ty) => Ty::Value(ins_ty.clone()),
260            Ty::Any => Ty::Any,
261            Ty::Boolean(truthiness) => Ty::Boolean(*truthiness),
262            Ty::Builtin(ty) => Ty::Builtin(ty.clone()),
263        };
264
265        self.transform_cache.insert((ty.clone(), pol), cano.clone());
266        cano
267    }
268
269    /// Transforms the given sequence of types.
270    fn transform_seq(&mut self, types: &[Ty], pol: bool) -> Interned<Vec<Ty>> {
271        let seq = types.iter().map(|ty| self.transform(ty, pol));
272        seq.collect::<Vec<_>>().into()
273    }
274
275    /// Transforms the given let type.
276    #[allow(clippy::mutable_key_type)]
277    fn transform_let<'a>(
278        &mut self,
279        lbs_iter: impl ExactSizeIterator<Item = &'a Ty>,
280        ubs_iter: impl ExactSizeIterator<Item = &'a Ty>,
281        decl: Option<&DeclExpr>,
282        pol: bool,
283    ) -> Ty {
284        let mut lbs = HashSet::with_capacity(lbs_iter.len());
285        let mut ubs = HashSet::with_capacity(ubs_iter.len());
286
287        crate::log_debug_ct!("transform let [principal={}]", self.principal);
288
289        if !self.principal || ((pol) && !decl.is_some_and(|decl| self.negatives.contains(decl))) {
290            for lb in lbs_iter {
291                lbs.insert(self.transform(lb, pol));
292            }
293        }
294        if !self.principal || ((!pol) && !decl.is_some_and(|decl| self.positives.contains(decl))) {
295            for ub in ubs_iter {
296                ubs.insert(self.transform(ub, !pol));
297            }
298        }
299
300        if ubs.is_empty() {
301            if lbs.len() == 1 {
302                return lbs.into_iter().next().unwrap();
303            }
304            if lbs.is_empty() {
305                return Ty::Any;
306            }
307        } else if lbs.is_empty() && ubs.len() == 1 {
308            return ubs.into_iter().next().unwrap();
309        }
310
311        // todo: bad performance
312        let mut lbs: Vec<_> = lbs.into_iter().collect();
313        lbs.sort();
314        let mut ubs: Vec<_> = ubs.into_iter().collect();
315        ubs.sort();
316
317        Ty::Let(TypeBounds { lbs, ubs }.into())
318    }
319
320    /// Transforms the given signature.
321    fn transform_sig(&mut self, sig: &SigTy, pol: bool) -> Interned<SigTy> {
322        let mut sig = sig.clone();
323        sig.inputs = self.transform_seq(&sig.inputs, !pol);
324        if let Some(ret) = &sig.body {
325            sig.body = Some(self.transform(ret, pol));
326        }
327
328        // todo: we can reduce one clone by early compare on sig.types
329        sig.into()
330    }
331}
332
333#[cfg(test)]
334mod tests {
335    use super::*;
336    use crate::syntax::Decl;
337
338    /// See https://github.com/typst/typst/issues/6285
339    #[test]
340    fn test_simplify_sort() {
341        fn ch(it: &str) -> Ty {
342            Ty::Value(InsTy::new(Value::Str(it.into())))
343        }
344
345        fn val(it: Value) -> Ty {
346            Ty::Value(InsTy::new(it))
347        }
348
349        fn test_sort_ty(mut tys: Vec<Ty>) {
350            tys.sort();
351        }
352
353        let abcdef = vec![ch("a"), ch("b"), ch("c"), ch("d"), ch("e"), ch("f")];
354
355        let mut res = vec![];
356        res.extend(abcdef.clone());
357        res.extend(abcdef.clone());
358        res.extend(abcdef.clone());
359        res.extend(vec![ch("c"), val(Value::None), ch("a")]);
360
361        test_sort_ty(res);
362    }
363
364    fn var(name: &str) -> TypeVarBounds {
365        TypeVarBounds::new(
366            TypeVar {
367                name: name.into(),
368                def: Decl::lit(name).into(),
369            },
370            DynTypeBounds::default(),
371        )
372    }
373
374    fn recursive_fun(root: &Interned<TypeVar>, depth: usize) -> Ty {
375        let mut body = Ty::Var(root.clone());
376        for _ in 0..depth {
377            body = Ty::Func(SigTy::unary(Ty::Any, body));
378        }
379        body
380    }
381
382    #[test]
383    fn test_recursive_cycle_union_is_not_aligned_like_simple_sub() {
384        let mut info = TypeInfo::default();
385
386        let one = var("one");
387        let two = var("two");
388
389        let one_ty = one.as_type();
390        let two_ty = two.as_type();
391
392        info.vars.insert(one.var.def.clone(), one.clone());
393        info.vars.insert(two.var.def.clone(), two.clone());
394
395        info.vars
396            .get(&one.var.def)
397            .unwrap()
398            .bounds
399            .bounds()
400            .write()
401            .lbs
402            .insert_mut(recursive_fun(&one.var, 1));
403        info.vars
404            .get(&two.var.def)
405            .unwrap()
406            .bounds
407            .bounds()
408            .write()
409            .lbs
410            .insert_mut(recursive_fun(&two.var, 2));
411
412        let merged = Ty::from_types([one_ty, two_ty].into_iter());
413        let simplified = info.simplify(merged, true);
414        assert_eq!(
415            format!("{simplified:?}"),
416            "((Any) => Any | (Any) => (Any) => Any)"
417        );
418    }
419
420    #[test]
421    fn test_simplify_populates_top_level_cache() {
422        let mut info = TypeInfo::default();
423        let one = var("one");
424        let one_ty = one.as_type();
425        info.vars.insert(one.var.def.clone(), one.clone());
426        info.vars
427            .get(&one.var.def)
428            .unwrap()
429            .bounds
430            .bounds()
431            .write()
432            .lbs
433            .insert_mut(recursive_fun(&one.var, 1));
434
435        let _ = info.simplify(one_ty.clone(), true);
436        let first_cache_len = info.cano_cache.lock().cano_cache.len();
437        let _ = info.simplify(one_ty, true);
438        let second_cache_len = info.cano_cache.lock().cano_cache.len();
439        assert!(
440            first_cache_len > 0,
441            "simplify should memoize the top-level result"
442        );
443        assert_eq!(first_cache_len, second_cache_len);
444    }
445}
tinymist_analysis/ty/simplify.rs

tinymist_analysis/ty/
simplify.rs
