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.cano_local_cache.clear();
25        cache.positives.clear();
26        cache.negatives.clear();
27
28        let mut worker = TypeSimplifier {
29            principal,
30            vars: &self.vars,
31            cano_cache: &mut cache.cano_cache,
32            cano_local_cache: &mut cache.cano_local_cache,
33
34            positives: &mut cache.positives,
35            negatives: &mut cache.negatives,
36        };
37
38        worker.simplify(ty, principal)
39    }
40}
41
42/// A simplifier to simplify a type.
43struct TypeSimplifier<'a, 'b> {
44    principal: bool,
45
46    vars: &'a FxHashMap<DeclExpr, TypeVarBounds>,
47
48    cano_cache: &'b mut FxHashMap<(Ty, bool), Ty>,
49    cano_local_cache: &'b mut FxHashMap<(DeclExpr, bool), Ty>,
50    negatives: &'b mut FxHashSet<DeclExpr>,
51    positives: &'b mut FxHashSet<DeclExpr>,
52}
53
54impl TypeSimplifier<'_, '_> {
55    /// Simplifies the given type.
56    fn simplify(&mut self, ty: Ty, principal: bool) -> Ty {
57        if let Some(cano) = self.cano_cache.get(&(ty.clone(), principal)) {
58            return cano.clone();
59        }
60
61        self.analyze(&ty, true);
62
63        self.transform(&ty, true)
64    }
65
66    /// Analyzes the given type.
67    fn analyze(&mut self, ty: &Ty, pol: bool) {
68        match ty {
69            Ty::Var(var) => {
70                let w = self.vars.get(&var.def).unwrap();
71                match &w.bounds {
72                    FlowVarKind::Strong(w) | FlowVarKind::Weak(w) => {
73                        let bounds = w.read();
74                        let inserted = if pol {
75                            self.positives.insert(var.def.clone())
76                        } else {
77                            self.negatives.insert(var.def.clone())
78                        };
79                        if !inserted {
80                            return;
81                        }
82
83                        if pol {
84                            for lb in bounds.lbs.iter() {
85                                self.analyze(lb, pol);
86                            }
87                        } else {
88                            for ub in bounds.ubs.iter() {
89                                self.analyze(ub, pol);
90                            }
91                        }
92                    }
93                }
94            }
95            Ty::Func(func) => {
96                for input_ty in func.inputs() {
97                    self.analyze(input_ty, !pol);
98                }
99                if let Some(ret_ty) = &func.body {
100                    self.analyze(ret_ty, pol);
101                }
102            }
103            Ty::Dict(record) => {
104                for member in record.types.iter() {
105                    self.analyze(member, pol);
106                }
107            }
108            Ty::Tuple(elems) => {
109                for elem in elems.iter() {
110                    self.analyze(elem, pol);
111                }
112            }
113            Ty::Array(arr) => {
114                self.analyze(arr, pol);
115            }
116            Ty::With(with) => {
117                self.analyze(&with.sig, pol);
118                for input in with.with.inputs() {
119                    self.analyze(input, pol);
120                }
121            }
122            Ty::Args(args) => {
123                for input in args.inputs() {
124                    self.analyze(input, pol);
125                }
126            }
127            Ty::Pattern(pat) => {
128                for input in pat.inputs() {
129                    self.analyze(input, pol);
130                }
131            }
132            Ty::Unary(unary) => self.analyze(&unary.lhs, pol),
133            Ty::Binary(binary) => {
134                let [lhs, rhs] = binary.operands();
135                self.analyze(lhs, pol);
136                self.analyze(rhs, pol);
137            }
138            Ty::If(if_expr) => {
139                self.analyze(&if_expr.cond, pol);
140                self.analyze(&if_expr.then, pol);
141                self.analyze(&if_expr.else_, pol);
142            }
143            Ty::Union(types) => {
144                for ty in types.iter() {
145                    self.analyze(ty, pol);
146                }
147            }
148            Ty::Select(select) => {
149                self.analyze(&select.ty, pol);
150            }
151            Ty::Let(bounds) => {
152                for lb in bounds.lbs.iter() {
153                    self.analyze(lb, !pol);
154                }
155                for ub in bounds.ubs.iter() {
156                    self.analyze(ub, pol);
157                }
158            }
159            Ty::Param(param) => {
160                self.analyze(&param.ty, pol);
161            }
162            Ty::Value(_v) => {}
163            Ty::Any => {}
164            Ty::Boolean(_) => {}
165            Ty::Builtin(_) => {}
166        }
167    }
168
169    /// Transforms the given type.
170    fn transform(&mut self, ty: &Ty, pol: bool) -> Ty {
171        match ty {
172            Ty::Let(bounds) => self.transform_let(bounds.lbs.iter(), bounds.ubs.iter(), None, pol),
173            Ty::Var(var) => {
174                if let Some(cano) = self
175                    .cano_local_cache
176                    .get(&(var.def.clone(), self.principal))
177                {
178                    return cano.clone();
179                }
180                // todo: avoid cycle
181                self.cano_local_cache
182                    .insert((var.def.clone(), self.principal), Ty::Any);
183
184                let res = match &self.vars.get(&var.def).unwrap().bounds {
185                    FlowVarKind::Strong(w) | FlowVarKind::Weak(w) => {
186                        let w = w.read();
187
188                        self.transform_let(w.lbs.iter(), w.ubs.iter(), Some(&var.def), pol)
189                    }
190                };
191
192                self.cano_local_cache
193                    .insert((var.def.clone(), self.principal), res.clone());
194
195                res
196            }
197            Ty::Func(func) => Ty::Func(self.transform_sig(func, pol)),
198            Ty::Dict(record) => {
199                let mut mutated = record.as_ref().clone();
200                mutated.types = self.transform_seq(&mutated.types, pol);
201
202                Ty::Dict(mutated.into())
203            }
204            Ty::Tuple(tup) => Ty::Tuple(self.transform_seq(tup, pol)),
205            Ty::Array(arr) => Ty::Array(self.transform(arr, pol).into()),
206            Ty::With(with) => {
207                let sig = self.transform(&with.sig, pol).into();
208                // Negate the pol to make correct covariance
209                let mutated = self.transform_sig(&with.with, !pol);
210
211                Ty::With(SigWithTy::new(sig, mutated))
212            }
213            // Negate the pol to make correct covariance
214            // todo: negate?
215            Ty::Args(args) => Ty::Args(self.transform_sig(args, !pol)),
216            Ty::Pattern(pat) => Ty::Pattern(self.transform_sig(pat, !pol)),
217            Ty::Unary(unary) => {
218                Ty::Unary(TypeUnary::new(unary.op, self.transform(&unary.lhs, pol)))
219            }
220            Ty::Binary(binary) => {
221                let [lhs, rhs] = binary.operands();
222                let lhs = self.transform(lhs, pol);
223                let rhs = self.transform(rhs, pol);
224
225                Ty::Binary(TypeBinary::new(binary.op, lhs, rhs))
226            }
227            Ty::If(if_ty) => Ty::If(IfTy::new(
228                self.transform(&if_ty.cond, pol).into(),
229                self.transform(&if_ty.then, pol).into(),
230                self.transform(&if_ty.else_, pol).into(),
231            )),
232            Ty::Union(types) => {
233                let seq = types.iter().map(|ty| self.transform(ty, pol));
234                let seq_no_any = seq.filter(|ty| !matches!(ty, Ty::Any));
235                let seq = seq_no_any.collect::<Vec<_>>();
236                Ty::from_types(seq.into_iter())
237            }
238            Ty::Param(param) => {
239                let mut param = param.as_ref().clone();
240                param.ty = self.transform(&param.ty, pol);
241
242                Ty::Param(param.into())
243            }
244            Ty::Select(sel) => {
245                let mut sel = sel.as_ref().clone();
246                sel.ty = self.transform(&sel.ty, pol).into();
247
248                Ty::Select(sel.into())
249            }
250
251            Ty::Value(ins_ty) => Ty::Value(ins_ty.clone()),
252            Ty::Any => Ty::Any,
253            Ty::Boolean(truthiness) => Ty::Boolean(*truthiness),
254            Ty::Builtin(ty) => Ty::Builtin(ty.clone()),
255        }
256    }
257
258    /// Transforms the given sequence of types.
259    fn transform_seq(&mut self, types: &[Ty], pol: bool) -> Interned<Vec<Ty>> {
260        let seq = types.iter().map(|ty| self.transform(ty, pol));
261        seq.collect::<Vec<_>>().into()
262    }
263
264    /// Transforms the given let type.
265    #[allow(clippy::mutable_key_type)]
266    fn transform_let<'a>(
267        &mut self,
268        lbs_iter: impl ExactSizeIterator<Item = &'a Ty>,
269        ubs_iter: impl ExactSizeIterator<Item = &'a Ty>,
270        decl: Option<&DeclExpr>,
271        pol: bool,
272    ) -> Ty {
273        let mut lbs = HashSet::with_capacity(lbs_iter.len());
274        let mut ubs = HashSet::with_capacity(ubs_iter.len());
275
276        crate::log_debug_ct!("transform let [principal={}]", self.principal);
277
278        if !self.principal || ((pol) && !decl.is_some_and(|decl| self.negatives.contains(decl))) {
279            for lb in lbs_iter {
280                lbs.insert(self.transform(lb, pol));
281            }
282        }
283        if !self.principal || ((!pol) && !decl.is_some_and(|decl| self.positives.contains(decl))) {
284            for ub in ubs_iter {
285                ubs.insert(self.transform(ub, !pol));
286            }
287        }
288
289        if ubs.is_empty() {
290            if lbs.len() == 1 {
291                return lbs.into_iter().next().unwrap();
292            }
293            if lbs.is_empty() {
294                return Ty::Any;
295            }
296        } else if lbs.is_empty() && ubs.len() == 1 {
297            return ubs.into_iter().next().unwrap();
298        }
299
300        // todo: bad performance
301        let mut lbs: Vec<_> = lbs.into_iter().collect();
302        lbs.sort();
303        let mut ubs: Vec<_> = ubs.into_iter().collect();
304        ubs.sort();
305
306        Ty::Let(TypeBounds { lbs, ubs }.into())
307    }
308
309    /// Transforms the given signature.
310    fn transform_sig(&mut self, sig: &SigTy, pol: bool) -> Interned<SigTy> {
311        let mut sig = sig.clone();
312        sig.inputs = self.transform_seq(&sig.inputs, !pol);
313        if let Some(ret) = &sig.body {
314            sig.body = Some(self.transform(ret, pol));
315        }
316
317        // todo: we can reduce one clone by early compare on sig.types
318        sig.into()
319    }
320}
tinymist_analysis/ty/simplify.rs

tinymist_analysis/ty/
simplify.rs
