diff options
Diffstat (limited to 'crates/ra_hir/src/ty/infer')
-rw-r--r-- | crates/ra_hir/src/ty/infer/unify.rs | 81 |
1 files changed, 81 insertions, 0 deletions
diff --git a/crates/ra_hir/src/ty/infer/unify.rs b/crates/ra_hir/src/ty/infer/unify.rs new file mode 100644 index 000000000..7918b007b --- /dev/null +++ b/crates/ra_hir/src/ty/infer/unify.rs | |||
@@ -0,0 +1,81 @@ | |||
1 | //! Unification and canonicalization logic. | ||
2 | |||
3 | use super::{InferenceContext, Ty, TraitRef, InferTy, HirDatabase}; | ||
4 | |||
5 | impl<'a, D: HirDatabase> InferenceContext<'a, D> { | ||
6 | pub(super) fn canonicalizer<'b>(&'b mut self) -> Canonicalizer<'a, 'b, D> | ||
7 | where | ||
8 | 'a: 'b, | ||
9 | { | ||
10 | Canonicalizer { ctx: self, free_vars: Vec::new() } | ||
11 | } | ||
12 | } | ||
13 | |||
14 | // TODO improve the interface of this | ||
15 | |||
16 | // TODO move further up? | ||
17 | #[derive(Debug, Clone, PartialEq, Eq, Hash)] | ||
18 | pub(crate) struct Canonical<T> { | ||
19 | pub value: T, | ||
20 | pub num_vars: usize, | ||
21 | } | ||
22 | |||
23 | pub(super) struct Canonicalizer<'a, 'b, D: HirDatabase> | ||
24 | where | ||
25 | 'a: 'b, | ||
26 | { | ||
27 | pub ctx: &'b mut InferenceContext<'a, D>, | ||
28 | pub free_vars: Vec<InferTy>, | ||
29 | } | ||
30 | |||
31 | impl<'a, 'b, D: HirDatabase> Canonicalizer<'a, 'b, D> | ||
32 | where | ||
33 | 'a: 'b, | ||
34 | { | ||
35 | fn add(&mut self, free_var: InferTy) -> usize { | ||
36 | self.free_vars.iter().position(|&v| v == free_var).unwrap_or_else(|| { | ||
37 | let next_index = self.free_vars.len(); | ||
38 | self.free_vars.push(free_var); | ||
39 | next_index | ||
40 | }) | ||
41 | } | ||
42 | |||
43 | pub fn canonicalize_ty(&mut self, ty: Ty) -> Canonical<Ty> { | ||
44 | let value = ty.fold(&mut |ty| match ty { | ||
45 | Ty::Infer(tv) => { | ||
46 | let inner = tv.to_inner(); | ||
47 | // TODO prevent infinite loops? => keep var stack | ||
48 | if let Some(known_ty) = self.ctx.var_unification_table.probe_value(inner).known() { | ||
49 | self.canonicalize_ty(known_ty.clone()).value | ||
50 | } else { | ||
51 | let free_var = InferTy::TypeVar(self.ctx.var_unification_table.find(inner)); | ||
52 | let position = self.add(free_var); | ||
53 | Ty::Bound(position as u32) | ||
54 | } | ||
55 | } | ||
56 | _ => ty, | ||
57 | }); | ||
58 | Canonical { value, num_vars: self.free_vars.len() } | ||
59 | } | ||
60 | |||
61 | pub fn canonicalize_trait_ref(&mut self, trait_ref: TraitRef) -> Canonical<TraitRef> { | ||
62 | let substs = trait_ref | ||
63 | .substs | ||
64 | .0 | ||
65 | .iter() | ||
66 | .map(|ty| self.canonicalize_ty(ty.clone()).value) | ||
67 | .collect::<Vec<_>>(); | ||
68 | let value = TraitRef { trait_: trait_ref.trait_, substs: substs.into() }; | ||
69 | Canonical { value, num_vars: self.free_vars.len() } | ||
70 | } | ||
71 | |||
72 | pub fn apply_solution(&mut self, solution: Canonical<Vec<Ty>>) { | ||
73 | // the solution may contain new variables, which we need to convert to new inference vars | ||
74 | let new_vars = | ||
75 | (0..solution.num_vars).map(|_| self.ctx.new_type_var()).collect::<Vec<_>>().into(); | ||
76 | for (i, ty) in solution.value.into_iter().enumerate() { | ||
77 | let var = self.free_vars[i].clone(); | ||
78 | self.ctx.unify(&Ty::Infer(var), &ty.subst_bound_vars(&new_vars)); | ||
79 | } | ||
80 | } | ||
81 | } | ||