diff options
Diffstat (limited to 'crates/hir_ty/src/infer/unify.rs')
-rw-r--r-- | crates/hir_ty/src/infer/unify.rs | 266 |
1 files changed, 153 insertions, 113 deletions
diff --git a/crates/hir_ty/src/infer/unify.rs b/crates/hir_ty/src/infer/unify.rs index 6e7b0f5a6..a887e20b0 100644 --- a/crates/hir_ty/src/infer/unify.rs +++ b/crates/hir_ty/src/infer/unify.rs | |||
@@ -2,13 +2,17 @@ | |||
2 | 2 | ||
3 | use std::borrow::Cow; | 3 | use std::borrow::Cow; |
4 | 4 | ||
5 | use chalk_ir::{FloatTy, IntTy, TyVariableKind, UniverseIndex, VariableKind}; | 5 | use chalk_ir::{ |
6 | cast::Cast, fold::Fold, interner::HasInterner, FloatTy, IntTy, TyVariableKind, UniverseIndex, | ||
7 | VariableKind, | ||
8 | }; | ||
6 | use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue}; | 9 | use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue}; |
7 | 10 | ||
8 | use super::{DomainGoal, InferenceContext}; | 11 | use super::{DomainGoal, InferenceContext}; |
9 | use crate::{ | 12 | use crate::{ |
10 | AliasEq, AliasTy, BoundVar, Canonical, CanonicalVarKinds, DebruijnIndex, FnPointer, | 13 | fold_tys, static_lifetime, AliasEq, AliasTy, BoundVar, Canonical, CanonicalVarKinds, |
11 | InEnvironment, InferenceVar, Interner, Scalar, Substitution, Ty, TyKind, TypeWalk, WhereClause, | 14 | DebruijnIndex, FnPointer, FnSubst, InEnvironment, InferenceVar, Interner, Scalar, Substitution, |
15 | Ty, TyExt, TyKind, WhereClause, | ||
12 | }; | 16 | }; |
13 | 17 | ||
14 | impl<'a> InferenceContext<'a> { | 18 | impl<'a> InferenceContext<'a> { |
@@ -33,7 +37,10 @@ where | |||
33 | } | 37 | } |
34 | 38 | ||
35 | #[derive(Debug)] | 39 | #[derive(Debug)] |
36 | pub(super) struct Canonicalized<T> { | 40 | pub(super) struct Canonicalized<T> |
41 | where | ||
42 | T: HasInterner<Interner = Interner>, | ||
43 | { | ||
37 | pub(super) value: Canonical<T>, | 44 | pub(super) value: Canonical<T>, |
38 | free_vars: Vec<(InferenceVar, TyVariableKind)>, | 45 | free_vars: Vec<(InferenceVar, TyVariableKind)>, |
39 | } | 46 | } |
@@ -47,11 +54,16 @@ impl<'a, 'b> Canonicalizer<'a, 'b> { | |||
47 | }) | 54 | }) |
48 | } | 55 | } |
49 | 56 | ||
50 | fn do_canonicalize<T: TypeWalk>(&mut self, t: T, binders: DebruijnIndex) -> T { | 57 | fn do_canonicalize<T: Fold<Interner, Result = T> + HasInterner<Interner = Interner>>( |
51 | t.fold_binders( | 58 | &mut self, |
52 | &mut |ty, binders| match ty.interned(&Interner) { | 59 | t: T, |
60 | binders: DebruijnIndex, | ||
61 | ) -> T { | ||
62 | fold_tys( | ||
63 | t, | ||
64 | |ty, binders| match ty.kind(&Interner) { | ||
53 | &TyKind::InferenceVar(var, kind) => { | 65 | &TyKind::InferenceVar(var, kind) => { |
54 | let inner = var.to_inner(); | 66 | let inner = from_inference_var(var); |
55 | if self.var_stack.contains(&inner) { | 67 | if self.var_stack.contains(&inner) { |
56 | // recursive type | 68 | // recursive type |
57 | return self.ctx.table.type_variable_table.fallback_value(var, kind); | 69 | return self.ctx.table.type_variable_table.fallback_value(var, kind); |
@@ -65,7 +77,7 @@ impl<'a, 'b> Canonicalizer<'a, 'b> { | |||
65 | result | 77 | result |
66 | } else { | 78 | } else { |
67 | let root = self.ctx.table.var_unification_table.find(inner); | 79 | let root = self.ctx.table.var_unification_table.find(inner); |
68 | let position = self.add(InferenceVar::from_inner(root), kind); | 80 | let position = self.add(to_inference_var(root), kind); |
69 | TyKind::BoundVar(BoundVar::new(binders, position)).intern(&Interner) | 81 | TyKind::BoundVar(BoundVar::new(binders, position)).intern(&Interner) |
70 | } | 82 | } |
71 | } | 83 | } |
@@ -75,7 +87,10 @@ impl<'a, 'b> Canonicalizer<'a, 'b> { | |||
75 | ) | 87 | ) |
76 | } | 88 | } |
77 | 89 | ||
78 | fn into_canonicalized<T>(self, result: T) -> Canonicalized<T> { | 90 | fn into_canonicalized<T: HasInterner<Interner = Interner>>( |
91 | self, | ||
92 | result: T, | ||
93 | ) -> Canonicalized<T> { | ||
79 | let kinds = self | 94 | let kinds = self |
80 | .free_vars | 95 | .free_vars |
81 | .iter() | 96 | .iter() |
@@ -102,25 +117,18 @@ impl<'a, 'b> Canonicalizer<'a, 'b> { | |||
102 | DomainGoal::Holds(wc) => { | 117 | DomainGoal::Holds(wc) => { |
103 | DomainGoal::Holds(self.do_canonicalize(wc, DebruijnIndex::INNERMOST)) | 118 | DomainGoal::Holds(self.do_canonicalize(wc, DebruijnIndex::INNERMOST)) |
104 | } | 119 | } |
120 | _ => unimplemented!(), | ||
105 | }; | 121 | }; |
106 | self.into_canonicalized(InEnvironment { goal: result, environment: obligation.environment }) | 122 | self.into_canonicalized(InEnvironment { goal: result, environment: obligation.environment }) |
107 | } | 123 | } |
108 | } | 124 | } |
109 | 125 | ||
110 | impl<T> Canonicalized<T> { | 126 | impl<T: HasInterner<Interner = Interner>> Canonicalized<T> { |
111 | pub(super) fn decanonicalize_ty(&self, mut ty: Ty) -> Ty { | 127 | pub(super) fn decanonicalize_ty(&self, ty: Ty) -> Ty { |
112 | ty.walk_mut_binders( | 128 | crate::fold_free_vars(ty, |bound, _binders| { |
113 | &mut |ty, binders| { | 129 | let (v, k) = self.free_vars[bound.index]; |
114 | if let &mut TyKind::BoundVar(bound) = ty.interned_mut() { | 130 | TyKind::InferenceVar(v, k).intern(&Interner) |
115 | if bound.debruijn >= binders { | 131 | }) |
116 | let (v, k) = self.free_vars[bound.index]; | ||
117 | *ty = TyKind::InferenceVar(v, k).intern(&Interner); | ||
118 | } | ||
119 | } | ||
120 | }, | ||
121 | DebruijnIndex::INNERMOST, | ||
122 | ); | ||
123 | ty | ||
124 | } | 132 | } |
125 | 133 | ||
126 | pub(super) fn apply_solution( | 134 | pub(super) fn apply_solution( |
@@ -129,29 +137,30 @@ impl<T> Canonicalized<T> { | |||
129 | solution: Canonical<Substitution>, | 137 | solution: Canonical<Substitution>, |
130 | ) { | 138 | ) { |
131 | // the solution may contain new variables, which we need to convert to new inference vars | 139 | // the solution may contain new variables, which we need to convert to new inference vars |
132 | let new_vars = Substitution( | 140 | let new_vars = Substitution::from_iter( |
133 | solution | 141 | &Interner, |
134 | .binders | 142 | solution.binders.iter(&Interner).map(|k| match k.kind { |
135 | .iter(&Interner) | 143 | VariableKind::Ty(TyVariableKind::General) => { |
136 | .map(|k| match k.kind { | 144 | ctx.table.new_type_var().cast(&Interner) |
137 | VariableKind::Ty(TyVariableKind::General) => ctx.table.new_type_var(), | 145 | } |
138 | VariableKind::Ty(TyVariableKind::Integer) => ctx.table.new_integer_var(), | 146 | VariableKind::Ty(TyVariableKind::Integer) => { |
139 | VariableKind::Ty(TyVariableKind::Float) => ctx.table.new_float_var(), | 147 | ctx.table.new_integer_var().cast(&Interner) |
140 | // HACK: Chalk can sometimes return new lifetime variables. We | 148 | } |
141 | // want to just skip them, but to not mess up the indices of | 149 | VariableKind::Ty(TyVariableKind::Float) => { |
142 | // other variables, we'll just create a new type variable in | 150 | ctx.table.new_float_var().cast(&Interner) |
143 | // their place instead. This should not matter (we never see the | 151 | } |
144 | // actual *uses* of the lifetime variable). | 152 | // Chalk can sometimes return new lifetime variables. We just use the static lifetime everywhere |
145 | VariableKind::Lifetime => ctx.table.new_type_var(), | 153 | VariableKind::Lifetime => static_lifetime().cast(&Interner), |
146 | _ => panic!("const variable in solution"), | 154 | _ => panic!("const variable in solution"), |
147 | }) | 155 | }), |
148 | .collect(), | ||
149 | ); | 156 | ); |
150 | for (i, ty) in solution.value.into_iter().enumerate() { | 157 | for (i, ty) in solution.value.iter(&Interner).enumerate() { |
151 | let (v, k) = self.free_vars[i]; | 158 | let (v, k) = self.free_vars[i]; |
152 | // eagerly replace projections in the type; we may be getting types | 159 | // eagerly replace projections in the type; we may be getting types |
153 | // e.g. from where clauses where this hasn't happened yet | 160 | // e.g. from where clauses where this hasn't happened yet |
154 | let ty = ctx.normalize_associated_types_in(ty.clone().subst_bound_vars(&new_vars)); | 161 | let ty = ctx.normalize_associated_types_in( |
162 | new_vars.apply(ty.assert_ty_ref(&Interner).clone(), &Interner), | ||
163 | ); | ||
155 | ctx.table.unify(&TyKind::InferenceVar(v, k).intern(&Interner), &ty); | 164 | ctx.table.unify(&TyKind::InferenceVar(v, k).intern(&Interner), &ty); |
156 | } | 165 | } |
157 | } | 166 | } |
@@ -163,22 +172,23 @@ pub fn could_unify(t1: &Ty, t2: &Ty) -> bool { | |||
163 | 172 | ||
164 | pub(crate) fn unify(tys: &Canonical<(Ty, Ty)>) -> Option<Substitution> { | 173 | pub(crate) fn unify(tys: &Canonical<(Ty, Ty)>) -> Option<Substitution> { |
165 | let mut table = InferenceTable::new(); | 174 | let mut table = InferenceTable::new(); |
166 | let vars = Substitution( | 175 | let vars = Substitution::from_iter( |
176 | &Interner, | ||
167 | tys.binders | 177 | tys.binders |
168 | .iter(&Interner) | 178 | .iter(&Interner) |
169 | // we always use type vars here because we want everything to | 179 | // we always use type vars here because we want everything to |
170 | // fallback to Unknown in the end (kind of hacky, as below) | 180 | // fallback to Unknown in the end (kind of hacky, as below) |
171 | .map(|_| table.new_type_var()) | 181 | .map(|_| table.new_type_var()), |
172 | .collect(), | ||
173 | ); | 182 | ); |
174 | let ty1_with_vars = tys.value.0.clone().subst_bound_vars(&vars); | 183 | let ty1_with_vars = vars.apply(tys.value.0.clone(), &Interner); |
175 | let ty2_with_vars = tys.value.1.clone().subst_bound_vars(&vars); | 184 | let ty2_with_vars = vars.apply(tys.value.1.clone(), &Interner); |
176 | if !table.unify(&ty1_with_vars, &ty2_with_vars) { | 185 | if !table.unify(&ty1_with_vars, &ty2_with_vars) { |
177 | return None; | 186 | return None; |
178 | } | 187 | } |
179 | // default any type vars that weren't unified back to their original bound vars | 188 | // default any type vars that weren't unified back to their original bound vars |
180 | // (kind of hacky) | 189 | // (kind of hacky) |
181 | for (i, var) in vars.iter().enumerate() { | 190 | for (i, var) in vars.iter(&Interner).enumerate() { |
191 | let var = var.assert_ty_ref(&Interner); | ||
182 | if &*table.resolve_ty_shallow(var) == var { | 192 | if &*table.resolve_ty_shallow(var) == var { |
183 | table.unify( | 193 | table.unify( |
184 | var, | 194 | var, |
@@ -186,11 +196,11 @@ pub(crate) fn unify(tys: &Canonical<(Ty, Ty)>) -> Option<Substitution> { | |||
186 | ); | 196 | ); |
187 | } | 197 | } |
188 | } | 198 | } |
189 | Some( | 199 | Some(Substitution::from_iter( |
190 | Substitution::builder(tys.binders.len(&Interner)) | 200 | &Interner, |
191 | .fill(vars.iter().map(|v| table.resolve_ty_completely(v.clone()))) | 201 | vars.iter(&Interner) |
192 | .build(), | 202 | .map(|v| table.resolve_ty_completely(v.assert_ty_ref(&Interner).clone())), |
193 | ) | 203 | )) |
194 | } | 204 | } |
195 | 205 | ||
196 | #[derive(Clone, Debug)] | 206 | #[derive(Clone, Debug)] |
@@ -204,17 +214,17 @@ impl TypeVariableTable { | |||
204 | } | 214 | } |
205 | 215 | ||
206 | pub(super) fn set_diverging(&mut self, iv: InferenceVar, diverging: bool) { | 216 | pub(super) fn set_diverging(&mut self, iv: InferenceVar, diverging: bool) { |
207 | self.inner[iv.to_inner().0 as usize].diverging = diverging; | 217 | self.inner[from_inference_var(iv).0 as usize].diverging = diverging; |
208 | } | 218 | } |
209 | 219 | ||
210 | fn is_diverging(&mut self, iv: InferenceVar) -> bool { | 220 | fn is_diverging(&mut self, iv: InferenceVar) -> bool { |
211 | self.inner[iv.to_inner().0 as usize].diverging | 221 | self.inner[from_inference_var(iv).0 as usize].diverging |
212 | } | 222 | } |
213 | 223 | ||
214 | fn fallback_value(&self, iv: InferenceVar, kind: TyVariableKind) -> Ty { | 224 | fn fallback_value(&self, iv: InferenceVar, kind: TyVariableKind) -> Ty { |
215 | match kind { | 225 | match kind { |
216 | _ if self.inner[iv.to_inner().0 as usize].diverging => TyKind::Never, | 226 | _ if self.inner[from_inference_var(iv).0 as usize].diverging => TyKind::Never, |
217 | TyVariableKind::General => TyKind::Unknown, | 227 | TyVariableKind::General => TyKind::Error, |
218 | TyVariableKind::Integer => TyKind::Scalar(Scalar::Int(IntTy::I32)), | 228 | TyVariableKind::Integer => TyKind::Scalar(Scalar::Int(IntTy::I32)), |
219 | TyVariableKind::Float => TyKind::Scalar(Scalar::Float(FloatTy::F64)), | 229 | TyVariableKind::Float => TyKind::Scalar(Scalar::Float(FloatTy::F64)), |
220 | } | 230 | } |
@@ -231,6 +241,7 @@ pub(crate) struct TypeVariableData { | |||
231 | pub(crate) struct InferenceTable { | 241 | pub(crate) struct InferenceTable { |
232 | pub(super) var_unification_table: InPlaceUnificationTable<TypeVarId>, | 242 | pub(super) var_unification_table: InPlaceUnificationTable<TypeVarId>, |
233 | pub(super) type_variable_table: TypeVariableTable, | 243 | pub(super) type_variable_table: TypeVariableTable, |
244 | pub(super) revision: u32, | ||
234 | } | 245 | } |
235 | 246 | ||
236 | impl InferenceTable { | 247 | impl InferenceTable { |
@@ -238,6 +249,7 @@ impl InferenceTable { | |||
238 | InferenceTable { | 249 | InferenceTable { |
239 | var_unification_table: InPlaceUnificationTable::new(), | 250 | var_unification_table: InPlaceUnificationTable::new(), |
240 | type_variable_table: TypeVariableTable { inner: Vec::new() }, | 251 | type_variable_table: TypeVariableTable { inner: Vec::new() }, |
252 | revision: 0, | ||
241 | } | 253 | } |
242 | } | 254 | } |
243 | 255 | ||
@@ -245,7 +257,7 @@ impl InferenceTable { | |||
245 | self.type_variable_table.push(TypeVariableData { diverging }); | 257 | self.type_variable_table.push(TypeVariableData { diverging }); |
246 | let key = self.var_unification_table.new_key(TypeVarValue::Unknown); | 258 | let key = self.var_unification_table.new_key(TypeVarValue::Unknown); |
247 | assert_eq!(key.0 as usize, self.type_variable_table.inner.len() - 1); | 259 | assert_eq!(key.0 as usize, self.type_variable_table.inner.len() - 1); |
248 | TyKind::InferenceVar(InferenceVar::from_inner(key), kind).intern(&Interner) | 260 | TyKind::InferenceVar(to_inference_var(key), kind).intern(&Interner) |
249 | } | 261 | } |
250 | 262 | ||
251 | pub(crate) fn new_type_var(&mut self) -> Ty { | 263 | pub(crate) fn new_type_var(&mut self) -> Ty { |
@@ -282,7 +294,9 @@ impl InferenceTable { | |||
282 | substs2: &Substitution, | 294 | substs2: &Substitution, |
283 | depth: usize, | 295 | depth: usize, |
284 | ) -> bool { | 296 | ) -> bool { |
285 | substs1.0.iter().zip(substs2.0.iter()).all(|(t1, t2)| self.unify_inner(t1, t2, depth)) | 297 | substs1.iter(&Interner).zip(substs2.iter(&Interner)).all(|(t1, t2)| { |
298 | self.unify_inner(t1.assert_ty_ref(&Interner), t2.assert_ty_ref(&Interner), depth) | ||
299 | }) | ||
286 | } | 300 | } |
287 | 301 | ||
288 | fn unify_inner(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool { | 302 | fn unify_inner(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool { |
@@ -297,12 +311,12 @@ impl InferenceTable { | |||
297 | let ty1 = self.resolve_ty_shallow(ty1); | 311 | let ty1 = self.resolve_ty_shallow(ty1); |
298 | let ty2 = self.resolve_ty_shallow(ty2); | 312 | let ty2 = self.resolve_ty_shallow(ty2); |
299 | if ty1.equals_ctor(&ty2) { | 313 | if ty1.equals_ctor(&ty2) { |
300 | match (ty1.interned(&Interner), ty2.interned(&Interner)) { | 314 | match (ty1.kind(&Interner), ty2.kind(&Interner)) { |
301 | (TyKind::Adt(_, substs1), TyKind::Adt(_, substs2)) | 315 | (TyKind::Adt(_, substs1), TyKind::Adt(_, substs2)) |
302 | | (TyKind::FnDef(_, substs1), TyKind::FnDef(_, substs2)) | 316 | | (TyKind::FnDef(_, substs1), TyKind::FnDef(_, substs2)) |
303 | | ( | 317 | | ( |
304 | TyKind::Function(FnPointer { substs: substs1, .. }), | 318 | TyKind::Function(FnPointer { substitution: FnSubst(substs1), .. }), |
305 | TyKind::Function(FnPointer { substs: substs2, .. }), | 319 | TyKind::Function(FnPointer { substitution: FnSubst(substs2), .. }), |
306 | ) | 320 | ) |
307 | | (TyKind::Tuple(_, substs1), TyKind::Tuple(_, substs2)) | 321 | | (TyKind::Tuple(_, substs1), TyKind::Tuple(_, substs2)) |
308 | | (TyKind::OpaqueType(_, substs1), TyKind::OpaqueType(_, substs2)) | 322 | | (TyKind::OpaqueType(_, substs1), TyKind::OpaqueType(_, substs2)) |
@@ -310,9 +324,11 @@ impl InferenceTable { | |||
310 | | (TyKind::Closure(.., substs1), TyKind::Closure(.., substs2)) => { | 324 | | (TyKind::Closure(.., substs1), TyKind::Closure(.., substs2)) => { |
311 | self.unify_substs(substs1, substs2, depth + 1) | 325 | self.unify_substs(substs1, substs2, depth + 1) |
312 | } | 326 | } |
313 | (TyKind::Ref(_, ty1), TyKind::Ref(_, ty2)) | 327 | (TyKind::Array(ty1, c1), TyKind::Array(ty2, c2)) if c1 == c2 => { |
328 | self.unify_inner(ty1, ty2, depth + 1) | ||
329 | } | ||
330 | (TyKind::Ref(_, _, ty1), TyKind::Ref(_, _, ty2)) | ||
314 | | (TyKind::Raw(_, ty1), TyKind::Raw(_, ty2)) | 331 | | (TyKind::Raw(_, ty1), TyKind::Raw(_, ty2)) |
315 | | (TyKind::Array(ty1), TyKind::Array(ty2)) | ||
316 | | (TyKind::Slice(ty1), TyKind::Slice(ty2)) => self.unify_inner(ty1, ty2, depth + 1), | 332 | | (TyKind::Slice(ty1), TyKind::Slice(ty2)) => self.unify_inner(ty1, ty2, depth + 1), |
317 | _ => true, /* we checked equals_ctor already */ | 333 | _ => true, /* we checked equals_ctor already */ |
318 | } | 334 | } |
@@ -322,8 +338,8 @@ impl InferenceTable { | |||
322 | } | 338 | } |
323 | 339 | ||
324 | pub(super) fn unify_inner_trivial(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool { | 340 | pub(super) fn unify_inner_trivial(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool { |
325 | match (ty1.interned(&Interner), ty2.interned(&Interner)) { | 341 | match (ty1.kind(&Interner), ty2.kind(&Interner)) { |
326 | (TyKind::Unknown, _) | (_, TyKind::Unknown) => true, | 342 | (TyKind::Error, _) | (_, TyKind::Error) => true, |
327 | 343 | ||
328 | (TyKind::Placeholder(p1), TyKind::Placeholder(p2)) if *p1 == *p2 => true, | 344 | (TyKind::Placeholder(p1), TyKind::Placeholder(p2)) if *p1 == *p2 => true, |
329 | 345 | ||
@@ -360,7 +376,14 @@ impl InferenceTable { | |||
360 | == self.type_variable_table.is_diverging(*tv2) => | 376 | == self.type_variable_table.is_diverging(*tv2) => |
361 | { | 377 | { |
362 | // both type vars are unknown since we tried to resolve them | 378 | // both type vars are unknown since we tried to resolve them |
363 | self.var_unification_table.union(tv1.to_inner(), tv2.to_inner()); | 379 | if !self |
380 | .var_unification_table | ||
381 | .unioned(from_inference_var(*tv1), from_inference_var(*tv2)) | ||
382 | { | ||
383 | self.var_unification_table | ||
384 | .union(from_inference_var(*tv1), from_inference_var(*tv2)); | ||
385 | self.revision += 1; | ||
386 | } | ||
364 | true | 387 | true |
365 | } | 388 | } |
366 | 389 | ||
@@ -395,9 +418,10 @@ impl InferenceTable { | |||
395 | ) => { | 418 | ) => { |
396 | // the type var is unknown since we tried to resolve it | 419 | // the type var is unknown since we tried to resolve it |
397 | self.var_unification_table.union_value( | 420 | self.var_unification_table.union_value( |
398 | tv.to_inner(), | 421 | from_inference_var(*tv), |
399 | TypeVarValue::Known(other.clone().intern(&Interner)), | 422 | TypeVarValue::Known(other.clone().intern(&Interner)), |
400 | ); | 423 | ); |
424 | self.revision += 1; | ||
401 | true | 425 | true |
402 | } | 426 | } |
403 | 427 | ||
@@ -447,9 +471,9 @@ impl InferenceTable { | |||
447 | if i > 0 { | 471 | if i > 0 { |
448 | cov_mark::hit!(type_var_resolves_to_int_var); | 472 | cov_mark::hit!(type_var_resolves_to_int_var); |
449 | } | 473 | } |
450 | match ty.interned(&Interner) { | 474 | match ty.kind(&Interner) { |
451 | TyKind::InferenceVar(tv, _) => { | 475 | TyKind::InferenceVar(tv, _) => { |
452 | let inner = tv.to_inner(); | 476 | let inner = from_inference_var(*tv); |
453 | match self.var_unification_table.inlined_probe_value(inner).known() { | 477 | match self.var_unification_table.inlined_probe_value(inner).known() { |
454 | Some(known_ty) => { | 478 | Some(known_ty) => { |
455 | // The known_ty can't be a type var itself | 479 | // The known_ty can't be a type var itself |
@@ -470,55 +494,63 @@ impl InferenceTable { | |||
470 | /// be resolved as far as possible, i.e. contain no type variables with | 494 | /// be resolved as far as possible, i.e. contain no type variables with |
471 | /// known type. | 495 | /// known type. |
472 | fn resolve_ty_as_possible_inner(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty { | 496 | fn resolve_ty_as_possible_inner(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty { |
473 | ty.fold(&mut |ty| match ty.interned(&Interner) { | 497 | fold_tys( |
474 | &TyKind::InferenceVar(tv, kind) => { | 498 | ty, |
475 | let inner = tv.to_inner(); | 499 | |ty, _| match ty.kind(&Interner) { |
476 | if tv_stack.contains(&inner) { | 500 | &TyKind::InferenceVar(tv, kind) => { |
477 | cov_mark::hit!(type_var_cycles_resolve_as_possible); | 501 | let inner = from_inference_var(tv); |
478 | // recursive type | 502 | if tv_stack.contains(&inner) { |
479 | return self.type_variable_table.fallback_value(tv, kind); | 503 | cov_mark::hit!(type_var_cycles_resolve_as_possible); |
480 | } | 504 | // recursive type |
481 | if let Some(known_ty) = | 505 | return self.type_variable_table.fallback_value(tv, kind); |
482 | self.var_unification_table.inlined_probe_value(inner).known() | 506 | } |
483 | { | 507 | if let Some(known_ty) = |
484 | // known_ty may contain other variables that are known by now | 508 | self.var_unification_table.inlined_probe_value(inner).known() |
485 | tv_stack.push(inner); | 509 | { |
486 | let result = self.resolve_ty_as_possible_inner(tv_stack, known_ty.clone()); | 510 | // known_ty may contain other variables that are known by now |
487 | tv_stack.pop(); | 511 | tv_stack.push(inner); |
488 | result | 512 | let result = self.resolve_ty_as_possible_inner(tv_stack, known_ty.clone()); |
489 | } else { | 513 | tv_stack.pop(); |
490 | ty | 514 | result |
515 | } else { | ||
516 | ty | ||
517 | } | ||
491 | } | 518 | } |
492 | } | 519 | _ => ty, |
493 | _ => ty, | 520 | }, |
494 | }) | 521 | DebruijnIndex::INNERMOST, |
522 | ) | ||
495 | } | 523 | } |
496 | 524 | ||
497 | /// Resolves the type completely; type variables without known type are | 525 | /// Resolves the type completely; type variables without known type are |
498 | /// replaced by TyKind::Unknown. | 526 | /// replaced by TyKind::Unknown. |
499 | fn resolve_ty_completely_inner(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty { | 527 | fn resolve_ty_completely_inner(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty { |
500 | ty.fold(&mut |ty| match ty.interned(&Interner) { | 528 | fold_tys( |
501 | &TyKind::InferenceVar(tv, kind) => { | 529 | ty, |
502 | let inner = tv.to_inner(); | 530 | |ty, _| match ty.kind(&Interner) { |
503 | if tv_stack.contains(&inner) { | 531 | &TyKind::InferenceVar(tv, kind) => { |
504 | cov_mark::hit!(type_var_cycles_resolve_completely); | 532 | let inner = from_inference_var(tv); |
505 | // recursive type | 533 | if tv_stack.contains(&inner) { |
506 | return self.type_variable_table.fallback_value(tv, kind); | 534 | cov_mark::hit!(type_var_cycles_resolve_completely); |
507 | } | 535 | // recursive type |
508 | if let Some(known_ty) = | 536 | return self.type_variable_table.fallback_value(tv, kind); |
509 | self.var_unification_table.inlined_probe_value(inner).known() | 537 | } |
510 | { | 538 | if let Some(known_ty) = |
511 | // known_ty may contain other variables that are known by now | 539 | self.var_unification_table.inlined_probe_value(inner).known() |
512 | tv_stack.push(inner); | 540 | { |
513 | let result = self.resolve_ty_completely_inner(tv_stack, known_ty.clone()); | 541 | // known_ty may contain other variables that are known by now |
514 | tv_stack.pop(); | 542 | tv_stack.push(inner); |
515 | result | 543 | let result = self.resolve_ty_completely_inner(tv_stack, known_ty.clone()); |
516 | } else { | 544 | tv_stack.pop(); |
517 | self.type_variable_table.fallback_value(tv, kind) | 545 | result |
546 | } else { | ||
547 | self.type_variable_table.fallback_value(tv, kind) | ||
548 | } | ||
518 | } | 549 | } |
519 | } | 550 | _ => ty, |
520 | _ => ty, | 551 | }, |
521 | }) | 552 | DebruijnIndex::INNERMOST, |
553 | ) | ||
522 | } | 554 | } |
523 | } | 555 | } |
524 | 556 | ||
@@ -542,6 +574,14 @@ impl UnifyKey for TypeVarId { | |||
542 | } | 574 | } |
543 | } | 575 | } |
544 | 576 | ||
577 | fn from_inference_var(var: InferenceVar) -> TypeVarId { | ||
578 | TypeVarId(var.index()) | ||
579 | } | ||
580 | |||
581 | fn to_inference_var(TypeVarId(index): TypeVarId) -> InferenceVar { | ||
582 | index.into() | ||
583 | } | ||
584 | |||
545 | /// The value of a type variable: either we already know the type, or we don't | 585 | /// The value of a type variable: either we already know the type, or we don't |
546 | /// know it yet. | 586 | /// know it yet. |
547 | #[derive(Clone, PartialEq, Eq, Debug)] | 587 | #[derive(Clone, PartialEq, Eq, Debug)] |