diff options
Diffstat (limited to 'crates/ra_hir/src/ty/infer/unify.rs')
-rw-r--r-- | crates/ra_hir/src/ty/infer/unify.rs | 166 |
1 files changed, 0 insertions, 166 deletions
diff --git a/crates/ra_hir/src/ty/infer/unify.rs b/crates/ra_hir/src/ty/infer/unify.rs deleted file mode 100644 index e27bb2f82..000000000 --- a/crates/ra_hir/src/ty/infer/unify.rs +++ /dev/null | |||
@@ -1,166 +0,0 @@ | |||
1 | //! Unification and canonicalization logic. | ||
2 | |||
3 | use super::{InferenceContext, Obligation}; | ||
4 | use crate::{ | ||
5 | db::HirDatabase, | ||
6 | ty::{ | ||
7 | Canonical, InEnvironment, InferTy, ProjectionPredicate, ProjectionTy, Substs, TraitRef, Ty, | ||
8 | TypeWalk, | ||
9 | }, | ||
10 | util::make_mut_slice, | ||
11 | }; | ||
12 | |||
13 | impl<'a, D: HirDatabase> InferenceContext<'a, D> { | ||
14 | pub(super) fn canonicalizer<'b>(&'b mut self) -> Canonicalizer<'a, 'b, D> | ||
15 | where | ||
16 | 'a: 'b, | ||
17 | { | ||
18 | Canonicalizer { ctx: self, free_vars: Vec::new(), var_stack: Vec::new() } | ||
19 | } | ||
20 | } | ||
21 | |||
22 | pub(super) struct Canonicalizer<'a, 'b, D: HirDatabase> | ||
23 | where | ||
24 | 'a: 'b, | ||
25 | { | ||
26 | ctx: &'b mut InferenceContext<'a, D>, | ||
27 | free_vars: Vec<InferTy>, | ||
28 | /// A stack of type variables that is used to detect recursive types (which | ||
29 | /// are an error, but we need to protect against them to avoid stack | ||
30 | /// overflows). | ||
31 | var_stack: Vec<super::TypeVarId>, | ||
32 | } | ||
33 | |||
34 | pub(super) struct Canonicalized<T> { | ||
35 | pub value: Canonical<T>, | ||
36 | free_vars: Vec<InferTy>, | ||
37 | } | ||
38 | |||
39 | impl<'a, 'b, D: HirDatabase> Canonicalizer<'a, 'b, D> | ||
40 | where | ||
41 | 'a: 'b, | ||
42 | { | ||
43 | fn add(&mut self, free_var: InferTy) -> usize { | ||
44 | self.free_vars.iter().position(|&v| v == free_var).unwrap_or_else(|| { | ||
45 | let next_index = self.free_vars.len(); | ||
46 | self.free_vars.push(free_var); | ||
47 | next_index | ||
48 | }) | ||
49 | } | ||
50 | |||
51 | fn do_canonicalize_ty(&mut self, ty: Ty) -> Ty { | ||
52 | ty.fold(&mut |ty| match ty { | ||
53 | Ty::Infer(tv) => { | ||
54 | let inner = tv.to_inner(); | ||
55 | if self.var_stack.contains(&inner) { | ||
56 | // recursive type | ||
57 | return tv.fallback_value(); | ||
58 | } | ||
59 | if let Some(known_ty) = | ||
60 | self.ctx.var_unification_table.inlined_probe_value(inner).known() | ||
61 | { | ||
62 | self.var_stack.push(inner); | ||
63 | let result = self.do_canonicalize_ty(known_ty.clone()); | ||
64 | self.var_stack.pop(); | ||
65 | result | ||
66 | } else { | ||
67 | let root = self.ctx.var_unification_table.find(inner); | ||
68 | let free_var = match tv { | ||
69 | InferTy::TypeVar(_) => InferTy::TypeVar(root), | ||
70 | InferTy::IntVar(_) => InferTy::IntVar(root), | ||
71 | InferTy::FloatVar(_) => InferTy::FloatVar(root), | ||
72 | InferTy::MaybeNeverTypeVar(_) => InferTy::MaybeNeverTypeVar(root), | ||
73 | }; | ||
74 | let position = self.add(free_var); | ||
75 | Ty::Bound(position as u32) | ||
76 | } | ||
77 | } | ||
78 | _ => ty, | ||
79 | }) | ||
80 | } | ||
81 | |||
82 | fn do_canonicalize_trait_ref(&mut self, mut trait_ref: TraitRef) -> TraitRef { | ||
83 | for ty in make_mut_slice(&mut trait_ref.substs.0) { | ||
84 | *ty = self.do_canonicalize_ty(ty.clone()); | ||
85 | } | ||
86 | trait_ref | ||
87 | } | ||
88 | |||
89 | fn into_canonicalized<T>(self, result: T) -> Canonicalized<T> { | ||
90 | Canonicalized { | ||
91 | value: Canonical { value: result, num_vars: self.free_vars.len() }, | ||
92 | free_vars: self.free_vars, | ||
93 | } | ||
94 | } | ||
95 | |||
96 | fn do_canonicalize_projection_ty(&mut self, mut projection_ty: ProjectionTy) -> ProjectionTy { | ||
97 | for ty in make_mut_slice(&mut projection_ty.parameters.0) { | ||
98 | *ty = self.do_canonicalize_ty(ty.clone()); | ||
99 | } | ||
100 | projection_ty | ||
101 | } | ||
102 | |||
103 | fn do_canonicalize_projection_predicate( | ||
104 | &mut self, | ||
105 | projection: ProjectionPredicate, | ||
106 | ) -> ProjectionPredicate { | ||
107 | let ty = self.do_canonicalize_ty(projection.ty); | ||
108 | let projection_ty = self.do_canonicalize_projection_ty(projection.projection_ty); | ||
109 | |||
110 | ProjectionPredicate { ty, projection_ty } | ||
111 | } | ||
112 | |||
113 | // FIXME: add some point, we need to introduce a `Fold` trait that abstracts | ||
114 | // over all the things that can be canonicalized (like Chalk and rustc have) | ||
115 | |||
116 | pub(crate) fn canonicalize_ty(mut self, ty: Ty) -> Canonicalized<Ty> { | ||
117 | let result = self.do_canonicalize_ty(ty); | ||
118 | self.into_canonicalized(result) | ||
119 | } | ||
120 | |||
121 | pub(crate) fn canonicalize_obligation( | ||
122 | mut self, | ||
123 | obligation: InEnvironment<Obligation>, | ||
124 | ) -> Canonicalized<InEnvironment<Obligation>> { | ||
125 | let result = match obligation.value { | ||
126 | Obligation::Trait(tr) => Obligation::Trait(self.do_canonicalize_trait_ref(tr)), | ||
127 | Obligation::Projection(pr) => { | ||
128 | Obligation::Projection(self.do_canonicalize_projection_predicate(pr)) | ||
129 | } | ||
130 | }; | ||
131 | self.into_canonicalized(InEnvironment { | ||
132 | value: result, | ||
133 | environment: obligation.environment, | ||
134 | }) | ||
135 | } | ||
136 | } | ||
137 | |||
138 | impl<T> Canonicalized<T> { | ||
139 | pub fn decanonicalize_ty(&self, mut ty: Ty) -> Ty { | ||
140 | ty.walk_mut_binders( | ||
141 | &mut |ty, binders| match ty { | ||
142 | &mut Ty::Bound(idx) => { | ||
143 | if idx as usize >= binders && (idx as usize - binders) < self.free_vars.len() { | ||
144 | *ty = Ty::Infer(self.free_vars[idx as usize - binders]); | ||
145 | } | ||
146 | } | ||
147 | _ => {} | ||
148 | }, | ||
149 | 0, | ||
150 | ); | ||
151 | ty | ||
152 | } | ||
153 | |||
154 | pub fn apply_solution( | ||
155 | &self, | ||
156 | ctx: &mut InferenceContext<'_, impl HirDatabase>, | ||
157 | solution: Canonical<Vec<Ty>>, | ||
158 | ) { | ||
159 | // the solution may contain new variables, which we need to convert to new inference vars | ||
160 | let new_vars = Substs((0..solution.num_vars).map(|_| ctx.new_type_var()).collect()); | ||
161 | for (i, ty) in solution.value.into_iter().enumerate() { | ||
162 | let var = self.free_vars[i]; | ||
163 | ctx.unify(&Ty::Infer(var), &ty.subst_bound_vars(&new_vars)); | ||
164 | } | ||
165 | } | ||
166 | } | ||