1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
//! Unification and canonicalization logic.
use crate::db::HirDatabase;
use crate::ty::{Ty, Canonical, TraitRef, InferTy};
use super::InferenceContext;
impl<'a, D: HirDatabase> InferenceContext<'a, D> {
pub(super) fn canonicalizer<'b>(&'b mut self) -> Canonicalizer<'a, 'b, D>
where
'a: 'b,
{
Canonicalizer { ctx: self, free_vars: Vec::new(), var_stack: Vec::new() }
}
}
pub(super) struct Canonicalizer<'a, 'b, D: HirDatabase>
where
'a: 'b,
{
ctx: &'b mut InferenceContext<'a, D>,
free_vars: Vec<InferTy>,
/// A stack of type variables that is used to detect recursive types (which
/// are an error, but we need to protect against them to avoid stack
/// overflows).
var_stack: Vec<super::TypeVarId>,
}
pub(super) struct Canonicalized<T> {
pub value: Canonical<T>,
free_vars: Vec<InferTy>,
}
impl<'a, 'b, D: HirDatabase> Canonicalizer<'a, 'b, D>
where
'a: 'b,
{
fn add(&mut self, free_var: InferTy) -> usize {
self.free_vars.iter().position(|&v| v == free_var).unwrap_or_else(|| {
let next_index = self.free_vars.len();
self.free_vars.push(free_var);
next_index
})
}
fn do_canonicalize_ty(&mut self, ty: Ty) -> Ty {
ty.fold(&mut |ty| match ty {
Ty::Infer(tv) => {
let inner = tv.to_inner();
if self.var_stack.contains(&inner) {
// recursive type
return tv.fallback_value();
}
if let Some(known_ty) = self.ctx.var_unification_table.probe_value(inner).known() {
self.var_stack.push(inner);
let result = self.do_canonicalize_ty(known_ty.clone());
self.var_stack.pop();
result
} else {
let root = self.ctx.var_unification_table.find(inner);
let free_var = match tv {
InferTy::TypeVar(_) => InferTy::TypeVar(root),
InferTy::IntVar(_) => InferTy::IntVar(root),
InferTy::FloatVar(_) => InferTy::FloatVar(root),
};
let position = self.add(free_var);
Ty::Bound(position as u32)
}
}
_ => ty,
})
}
fn do_canonicalize_trait_ref(&mut self, trait_ref: TraitRef) -> TraitRef {
let substs = trait_ref
.substs
.iter()
.map(|ty| self.do_canonicalize_ty(ty.clone()))
.collect::<Vec<_>>();
TraitRef { trait_: trait_ref.trait_, substs: substs.into() }
}
fn into_canonicalized<T>(self, result: T) -> Canonicalized<T> {
Canonicalized {
value: Canonical { value: result, num_vars: self.free_vars.len() },
free_vars: self.free_vars,
}
}
pub fn canonicalize_ty(mut self, ty: Ty) -> Canonicalized<Ty> {
let result = self.do_canonicalize_ty(ty);
self.into_canonicalized(result)
}
pub fn canonicalize_trait_ref(mut self, trait_ref: TraitRef) -> Canonicalized<TraitRef> {
let result = self.do_canonicalize_trait_ref(trait_ref);
self.into_canonicalized(result)
}
}
impl<T> Canonicalized<T> {
pub fn decanonicalize_ty(&self, ty: Ty) -> Ty {
ty.fold(&mut |ty| match ty {
Ty::Bound(idx) => {
if (idx as usize) < self.free_vars.len() {
Ty::Infer(self.free_vars[idx as usize].clone())
} else {
Ty::Bound(idx)
}
}
ty => ty,
})
}
pub fn apply_solution(
&self,
ctx: &mut InferenceContext<'_, impl HirDatabase>,
solution: Canonical<Vec<Ty>>,
) {
// the solution may contain new variables, which we need to convert to new inference vars
let new_vars =
(0..solution.num_vars).map(|_| ctx.new_type_var()).collect::<Vec<_>>().into();
for (i, ty) in solution.value.into_iter().enumerate() {
let var = self.free_vars[i].clone();
ctx.unify(&Ty::Infer(var), &ty.subst_bound_vars(&new_vars));
}
}
}
|
