diff options
Diffstat (limited to 'crates/ra_hir_ty/src/infer/unify.rs')
-rw-r--r-- | crates/ra_hir_ty/src/infer/unify.rs | 272 |
1 files changed, 266 insertions, 6 deletions
diff --git a/crates/ra_hir_ty/src/infer/unify.rs b/crates/ra_hir_ty/src/infer/unify.rs index f3a875678..ff50138f5 100644 --- a/crates/ra_hir_ty/src/infer/unify.rs +++ b/crates/ra_hir_ty/src/infer/unify.rs | |||
@@ -1,9 +1,15 @@ | |||
1 | //! Unification and canonicalization logic. | 1 | //! Unification and canonicalization logic. |
2 | 2 | ||
3 | use std::borrow::Cow; | ||
4 | |||
5 | use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue}; | ||
6 | |||
7 | use test_utils::tested_by; | ||
8 | |||
3 | use super::{InferenceContext, Obligation}; | 9 | use super::{InferenceContext, Obligation}; |
4 | use crate::{ | 10 | use crate::{ |
5 | db::HirDatabase, utils::make_mut_slice, Canonical, InEnvironment, InferTy, ProjectionPredicate, | 11 | db::HirDatabase, utils::make_mut_slice, Canonical, InEnvironment, InferTy, ProjectionPredicate, |
6 | ProjectionTy, Substs, TraitRef, Ty, TypeWalk, | 12 | ProjectionTy, Substs, TraitRef, Ty, TypeCtor, TypeWalk, |
7 | }; | 13 | }; |
8 | 14 | ||
9 | impl<'a, D: HirDatabase> InferenceContext<'a, D> { | 15 | impl<'a, D: HirDatabase> InferenceContext<'a, D> { |
@@ -24,7 +30,7 @@ where | |||
24 | /// A stack of type variables that is used to detect recursive types (which | 30 | /// A stack of type variables that is used to detect recursive types (which |
25 | /// are an error, but we need to protect against them to avoid stack | 31 | /// are an error, but we need to protect against them to avoid stack |
26 | /// overflows). | 32 | /// overflows). |
27 | var_stack: Vec<super::TypeVarId>, | 33 | var_stack: Vec<TypeVarId>, |
28 | } | 34 | } |
29 | 35 | ||
30 | pub(super) struct Canonicalized<T> { | 36 | pub(super) struct Canonicalized<T> { |
@@ -53,14 +59,14 @@ where | |||
53 | return tv.fallback_value(); | 59 | return tv.fallback_value(); |
54 | } | 60 | } |
55 | if let Some(known_ty) = | 61 | if let Some(known_ty) = |
56 | self.ctx.var_unification_table.inlined_probe_value(inner).known() | 62 | self.ctx.table.var_unification_table.inlined_probe_value(inner).known() |
57 | { | 63 | { |
58 | self.var_stack.push(inner); | 64 | self.var_stack.push(inner); |
59 | let result = self.do_canonicalize_ty(known_ty.clone()); | 65 | let result = self.do_canonicalize_ty(known_ty.clone()); |
60 | self.var_stack.pop(); | 66 | self.var_stack.pop(); |
61 | result | 67 | result |
62 | } else { | 68 | } else { |
63 | let root = self.ctx.var_unification_table.find(inner); | 69 | let root = self.ctx.table.var_unification_table.find(inner); |
64 | let free_var = match tv { | 70 | let free_var = match tv { |
65 | InferTy::TypeVar(_) => InferTy::TypeVar(root), | 71 | InferTy::TypeVar(_) => InferTy::TypeVar(root), |
66 | InferTy::IntVar(_) => InferTy::IntVar(root), | 72 | InferTy::IntVar(_) => InferTy::IntVar(root), |
@@ -153,10 +159,264 @@ impl<T> Canonicalized<T> { | |||
153 | solution: Canonical<Vec<Ty>>, | 159 | solution: Canonical<Vec<Ty>>, |
154 | ) { | 160 | ) { |
155 | // the solution may contain new variables, which we need to convert to new inference vars | 161 | // the solution may contain new variables, which we need to convert to new inference vars |
156 | let new_vars = Substs((0..solution.num_vars).map(|_| ctx.new_type_var()).collect()); | 162 | let new_vars = Substs((0..solution.num_vars).map(|_| ctx.table.new_type_var()).collect()); |
157 | for (i, ty) in solution.value.into_iter().enumerate() { | 163 | for (i, ty) in solution.value.into_iter().enumerate() { |
158 | let var = self.free_vars[i]; | 164 | let var = self.free_vars[i]; |
159 | ctx.unify(&Ty::Infer(var), &ty.subst_bound_vars(&new_vars)); | 165 | ctx.table.unify(&Ty::Infer(var), &ty.subst_bound_vars(&new_vars)); |
166 | } | ||
167 | } | ||
168 | } | ||
169 | |||
170 | pub fn unify(ty1: Canonical<&Ty>, ty2: &Ty) -> Substs { | ||
171 | let mut table = InferenceTable::new(); | ||
172 | let vars = Substs::builder(ty1.num_vars) | ||
173 | .fill(std::iter::repeat_with(|| table.new_type_var())).build(); | ||
174 | let ty_with_vars = ty1.value.clone().subst_bound_vars(&vars); | ||
175 | table.unify(&ty_with_vars, ty2); | ||
176 | Substs::builder(ty1.num_vars).fill(vars.iter().map(|v| table.resolve_ty_completely(v.clone()))).build() | ||
177 | } | ||
178 | |||
179 | #[derive(Clone, Debug)] | ||
180 | pub(crate) struct InferenceTable { | ||
181 | pub(super) var_unification_table: InPlaceUnificationTable<TypeVarId>, | ||
182 | } | ||
183 | |||
184 | impl InferenceTable { | ||
185 | pub fn new() -> Self { | ||
186 | InferenceTable { | ||
187 | var_unification_table: InPlaceUnificationTable::new(), | ||
188 | } | ||
189 | } | ||
190 | |||
191 | pub fn new_type_var(&mut self) -> Ty { | ||
192 | Ty::Infer(InferTy::TypeVar(self.var_unification_table.new_key(TypeVarValue::Unknown))) | ||
193 | } | ||
194 | |||
195 | pub fn new_integer_var(&mut self) -> Ty { | ||
196 | Ty::Infer(InferTy::IntVar(self.var_unification_table.new_key(TypeVarValue::Unknown))) | ||
197 | } | ||
198 | |||
199 | pub fn new_float_var(&mut self) -> Ty { | ||
200 | Ty::Infer(InferTy::FloatVar(self.var_unification_table.new_key(TypeVarValue::Unknown))) | ||
201 | } | ||
202 | |||
203 | pub fn new_maybe_never_type_var(&mut self) -> Ty { | ||
204 | Ty::Infer(InferTy::MaybeNeverTypeVar( | ||
205 | self.var_unification_table.new_key(TypeVarValue::Unknown), | ||
206 | )) | ||
207 | } | ||
208 | |||
209 | pub fn resolve_ty_completely(&mut self, ty: Ty) -> Ty { | ||
210 | self.resolve_ty_completely_inner(&mut Vec::new(), ty) | ||
211 | } | ||
212 | |||
213 | pub fn resolve_ty_as_possible(&mut self, ty: Ty) -> Ty { | ||
214 | self.resolve_ty_as_possible_inner(&mut Vec::new(), ty) | ||
215 | } | ||
216 | |||
217 | pub fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool { | ||
218 | self.unify_inner(ty1, ty2, 0) | ||
219 | } | ||
220 | |||
221 | pub fn unify_substs(&mut self, substs1: &Substs, substs2: &Substs, depth: usize) -> bool { | ||
222 | substs1.0.iter().zip(substs2.0.iter()).all(|(t1, t2)| self.unify_inner(t1, t2, depth)) | ||
223 | } | ||
224 | |||
225 | fn unify_inner(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool { | ||
226 | if depth > 1000 { | ||
227 | // prevent stackoverflows | ||
228 | panic!("infinite recursion in unification"); | ||
229 | } | ||
230 | if ty1 == ty2 { | ||
231 | return true; | ||
232 | } | ||
233 | // try to resolve type vars first | ||
234 | let ty1 = self.resolve_ty_shallow(ty1); | ||
235 | let ty2 = self.resolve_ty_shallow(ty2); | ||
236 | match (&*ty1, &*ty2) { | ||
237 | (Ty::Apply(a_ty1), Ty::Apply(a_ty2)) if a_ty1.ctor == a_ty2.ctor => { | ||
238 | self.unify_substs(&a_ty1.parameters, &a_ty2.parameters, depth + 1) | ||
239 | } | ||
240 | _ => self.unify_inner_trivial(&ty1, &ty2), | ||
241 | } | ||
242 | } | ||
243 | |||
244 | pub(super) fn unify_inner_trivial(&mut self, ty1: &Ty, ty2: &Ty) -> bool { | ||
245 | match (ty1, ty2) { | ||
246 | (Ty::Unknown, _) | (_, Ty::Unknown) => true, | ||
247 | |||
248 | (Ty::Infer(InferTy::TypeVar(tv1)), Ty::Infer(InferTy::TypeVar(tv2))) | ||
249 | | (Ty::Infer(InferTy::IntVar(tv1)), Ty::Infer(InferTy::IntVar(tv2))) | ||
250 | | (Ty::Infer(InferTy::FloatVar(tv1)), Ty::Infer(InferTy::FloatVar(tv2))) | ||
251 | | ( | ||
252 | Ty::Infer(InferTy::MaybeNeverTypeVar(tv1)), | ||
253 | Ty::Infer(InferTy::MaybeNeverTypeVar(tv2)), | ||
254 | ) => { | ||
255 | // both type vars are unknown since we tried to resolve them | ||
256 | self.var_unification_table.union(*tv1, *tv2); | ||
257 | true | ||
258 | } | ||
259 | |||
260 | // The order of MaybeNeverTypeVar matters here. | ||
261 | // Unifying MaybeNeverTypeVar and TypeVar will let the latter become MaybeNeverTypeVar. | ||
262 | // Unifying MaybeNeverTypeVar and other concrete type will let the former become it. | ||
263 | (Ty::Infer(InferTy::TypeVar(tv)), other) | ||
264 | | (other, Ty::Infer(InferTy::TypeVar(tv))) | ||
265 | | (Ty::Infer(InferTy::MaybeNeverTypeVar(tv)), other) | ||
266 | | (other, Ty::Infer(InferTy::MaybeNeverTypeVar(tv))) | ||
267 | | (Ty::Infer(InferTy::IntVar(tv)), other @ ty_app!(TypeCtor::Int(_))) | ||
268 | | (other @ ty_app!(TypeCtor::Int(_)), Ty::Infer(InferTy::IntVar(tv))) | ||
269 | | (Ty::Infer(InferTy::FloatVar(tv)), other @ ty_app!(TypeCtor::Float(_))) | ||
270 | | (other @ ty_app!(TypeCtor::Float(_)), Ty::Infer(InferTy::FloatVar(tv))) => { | ||
271 | // the type var is unknown since we tried to resolve it | ||
272 | self.var_unification_table.union_value(*tv, TypeVarValue::Known(other.clone())); | ||
273 | true | ||
274 | } | ||
275 | |||
276 | _ => false, | ||
277 | } | ||
278 | } | ||
279 | |||
280 | /// If `ty` is a type variable with known type, returns that type; | ||
281 | /// otherwise, return ty. | ||
282 | pub fn resolve_ty_shallow<'b>(&mut self, ty: &'b Ty) -> Cow<'b, Ty> { | ||
283 | let mut ty = Cow::Borrowed(ty); | ||
284 | // The type variable could resolve to a int/float variable. Hence try | ||
285 | // resolving up to three times; each type of variable shouldn't occur | ||
286 | // more than once | ||
287 | for i in 0..3 { | ||
288 | if i > 0 { | ||
289 | tested_by!(type_var_resolves_to_int_var); | ||
290 | } | ||
291 | match &*ty { | ||
292 | Ty::Infer(tv) => { | ||
293 | let inner = tv.to_inner(); | ||
294 | match self.var_unification_table.inlined_probe_value(inner).known() { | ||
295 | Some(known_ty) => { | ||
296 | // The known_ty can't be a type var itself | ||
297 | ty = Cow::Owned(known_ty.clone()); | ||
298 | } | ||
299 | _ => return ty, | ||
300 | } | ||
301 | } | ||
302 | _ => return ty, | ||
303 | } | ||
304 | } | ||
305 | log::error!("Inference variable still not resolved: {:?}", ty); | ||
306 | ty | ||
307 | } | ||
308 | |||
309 | /// Resolves the type as far as currently possible, replacing type variables | ||
310 | /// by their known types. All types returned by the infer_* functions should | ||
311 | /// be resolved as far as possible, i.e. contain no type variables with | ||
312 | /// known type. | ||
313 | fn resolve_ty_as_possible_inner(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty { | ||
314 | ty.fold(&mut |ty| match ty { | ||
315 | Ty::Infer(tv) => { | ||
316 | let inner = tv.to_inner(); | ||
317 | if tv_stack.contains(&inner) { | ||
318 | tested_by!(type_var_cycles_resolve_as_possible); | ||
319 | // recursive type | ||
320 | return tv.fallback_value(); | ||
321 | } | ||
322 | if let Some(known_ty) = | ||
323 | self.var_unification_table.inlined_probe_value(inner).known() | ||
324 | { | ||
325 | // known_ty may contain other variables that are known by now | ||
326 | tv_stack.push(inner); | ||
327 | let result = self.resolve_ty_as_possible_inner(tv_stack, known_ty.clone()); | ||
328 | tv_stack.pop(); | ||
329 | result | ||
330 | } else { | ||
331 | ty | ||
332 | } | ||
333 | } | ||
334 | _ => ty, | ||
335 | }) | ||
336 | } | ||
337 | |||
338 | /// Resolves the type completely; type variables without known type are | ||
339 | /// replaced by Ty::Unknown. | ||
340 | fn resolve_ty_completely_inner(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty { | ||
341 | ty.fold(&mut |ty| match ty { | ||
342 | Ty::Infer(tv) => { | ||
343 | let inner = tv.to_inner(); | ||
344 | if tv_stack.contains(&inner) { | ||
345 | tested_by!(type_var_cycles_resolve_completely); | ||
346 | // recursive type | ||
347 | return tv.fallback_value(); | ||
348 | } | ||
349 | if let Some(known_ty) = | ||
350 | self.var_unification_table.inlined_probe_value(inner).known() | ||
351 | { | ||
352 | // known_ty may contain other variables that are known by now | ||
353 | tv_stack.push(inner); | ||
354 | let result = self.resolve_ty_completely_inner(tv_stack, known_ty.clone()); | ||
355 | tv_stack.pop(); | ||
356 | result | ||
357 | } else { | ||
358 | tv.fallback_value() | ||
359 | } | ||
360 | } | ||
361 | _ => ty, | ||
362 | }) | ||
363 | } | ||
364 | } | ||
365 | |||
366 | /// The ID of a type variable. | ||
367 | #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)] | ||
368 | pub struct TypeVarId(pub(super) u32); | ||
369 | |||
370 | impl UnifyKey for TypeVarId { | ||
371 | type Value = TypeVarValue; | ||
372 | |||
373 | fn index(&self) -> u32 { | ||
374 | self.0 | ||
375 | } | ||
376 | |||
377 | fn from_index(i: u32) -> Self { | ||
378 | TypeVarId(i) | ||
379 | } | ||
380 | |||
381 | fn tag() -> &'static str { | ||
382 | "TypeVarId" | ||
383 | } | ||
384 | } | ||
385 | |||
386 | /// The value of a type variable: either we already know the type, or we don't | ||
387 | /// know it yet. | ||
388 | #[derive(Clone, PartialEq, Eq, Debug)] | ||
389 | pub enum TypeVarValue { | ||
390 | Known(Ty), | ||
391 | Unknown, | ||
392 | } | ||
393 | |||
394 | impl TypeVarValue { | ||
395 | fn known(&self) -> Option<&Ty> { | ||
396 | match self { | ||
397 | TypeVarValue::Known(ty) => Some(ty), | ||
398 | TypeVarValue::Unknown => None, | ||
399 | } | ||
400 | } | ||
401 | } | ||
402 | |||
403 | impl UnifyValue for TypeVarValue { | ||
404 | type Error = NoError; | ||
405 | |||
406 | fn unify_values(value1: &Self, value2: &Self) -> Result<Self, NoError> { | ||
407 | match (value1, value2) { | ||
408 | // We should never equate two type variables, both of which have | ||
409 | // known types. Instead, we recursively equate those types. | ||
410 | (TypeVarValue::Known(t1), TypeVarValue::Known(t2)) => panic!( | ||
411 | "equating two type variables, both of which have known types: {:?} and {:?}", | ||
412 | t1, t2 | ||
413 | ), | ||
414 | |||
415 | // If one side is known, prefer that one. | ||
416 | (TypeVarValue::Known(..), TypeVarValue::Unknown) => Ok(value1.clone()), | ||
417 | (TypeVarValue::Unknown, TypeVarValue::Known(..)) => Ok(value2.clone()), | ||
418 | |||
419 | (TypeVarValue::Unknown, TypeVarValue::Unknown) => Ok(TypeVarValue::Unknown), | ||
160 | } | 420 | } |
161 | } | 421 | } |
162 | } | 422 | } |