diff options
-rw-r--r-- | crates/hir_ty/src/infer/unify.rs | 165 |
1 files changed, 117 insertions, 48 deletions
diff --git a/crates/hir_ty/src/infer/unify.rs b/crates/hir_ty/src/infer/unify.rs index 00066975f..896d084f4 100644 --- a/crates/hir_ty/src/infer/unify.rs +++ b/crates/hir_ty/src/infer/unify.rs | |||
@@ -118,16 +118,13 @@ pub(crate) fn unify( | |||
118 | chalk_ir::GenericArgData::Const(c) => c.inference_var(&Interner), | 118 | chalk_ir::GenericArgData::Const(c) => c.inference_var(&Interner), |
119 | } == Some(iv)) | 119 | } == Some(iv)) |
120 | }; | 120 | }; |
121 | let fallback = |iv, kind, default| match kind { | 121 | let fallback = |iv, kind, default, binder| match kind { |
122 | chalk_ir::VariableKind::Ty(_ty_kind) => find_var(iv).map_or(default, |i| { | 122 | chalk_ir::VariableKind::Ty(_ty_kind) => find_var(iv) |
123 | BoundVar::new(DebruijnIndex::INNERMOST, i).to_ty(&Interner).cast(&Interner) | 123 | .map_or(default, |i| BoundVar::new(binder, i).to_ty(&Interner).cast(&Interner)), |
124 | }), | 124 | chalk_ir::VariableKind::Lifetime => find_var(iv) |
125 | chalk_ir::VariableKind::Lifetime => find_var(iv).map_or(default, |i| { | 125 | .map_or(default, |i| BoundVar::new(binder, i).to_lifetime(&Interner).cast(&Interner)), |
126 | BoundVar::new(DebruijnIndex::INNERMOST, i).to_lifetime(&Interner).cast(&Interner) | 126 | chalk_ir::VariableKind::Const(ty) => find_var(iv) |
127 | }), | 127 | .map_or(default, |i| BoundVar::new(binder, i).to_const(&Interner, ty).cast(&Interner)), |
128 | chalk_ir::VariableKind::Const(ty) => find_var(iv).map_or(default, |i| { | ||
129 | BoundVar::new(DebruijnIndex::INNERMOST, i).to_const(&Interner, ty).cast(&Interner) | ||
130 | }), | ||
131 | }; | 128 | }; |
132 | Some(Substitution::from_iter( | 129 | Some(Substitution::from_iter( |
133 | &Interner, | 130 | &Interner, |
@@ -212,7 +209,7 @@ impl<'a> InferenceTable<'a> { | |||
212 | pub(crate) fn resolve_with_fallback<T>( | 209 | pub(crate) fn resolve_with_fallback<T>( |
213 | &mut self, | 210 | &mut self, |
214 | t: T, | 211 | t: T, |
215 | fallback: impl Fn(InferenceVar, VariableKind, GenericArg) -> GenericArg, | 212 | fallback: impl Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg, |
216 | ) -> T::Result | 213 | ) -> T::Result |
217 | where | 214 | where |
218 | T: HasInterner<Interner = Interner> + Fold<Interner>, | 215 | T: HasInterner<Interner = Interner> + Fold<Interner>, |
@@ -224,50 +221,25 @@ impl<'a> InferenceTable<'a> { | |||
224 | &mut self, | 221 | &mut self, |
225 | var_stack: &mut Vec<InferenceVar>, | 222 | var_stack: &mut Vec<InferenceVar>, |
226 | t: T, | 223 | t: T, |
227 | fallback: &impl Fn(InferenceVar, VariableKind, GenericArg) -> GenericArg, | 224 | fallback: &impl Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg, |
228 | ) -> T::Result | 225 | ) -> T::Result |
229 | where | 226 | where |
230 | T: HasInterner<Interner = Interner> + Fold<Interner>, | 227 | T: HasInterner<Interner = Interner> + Fold<Interner>, |
231 | { | 228 | { |
232 | fold_tys( | 229 | t.fold_with( |
233 | t, | 230 | &mut resolve::Resolver { |
234 | |ty, _| match ty.kind(&Interner) { | 231 | type_variable_table: &self.type_variable_table, |
235 | &TyKind::InferenceVar(tv, kind) => { | 232 | var_unification_table: &mut self.var_unification_table, |
236 | if var_stack.contains(&tv) { | 233 | var_stack, |
237 | cov_mark::hit!(type_var_cycles_resolve_as_possible); | 234 | fallback, |
238 | // recursive type | ||
239 | let default = | ||
240 | self.type_variable_table.fallback_value(tv, kind).cast(&Interner); | ||
241 | return fallback(tv, VariableKind::Ty(kind), default) | ||
242 | .assert_ty_ref(&Interner) | ||
243 | .clone(); | ||
244 | } | ||
245 | if let Some(known_ty) = self.var_unification_table.probe_var(tv) { | ||
246 | // known_ty may contain other variables that are known by now | ||
247 | var_stack.push(tv); | ||
248 | let result = self.resolve_with_fallback_inner( | ||
249 | var_stack, | ||
250 | known_ty.assert_ty_ref(&Interner).clone(), | ||
251 | fallback, | ||
252 | ); | ||
253 | var_stack.pop(); | ||
254 | result | ||
255 | } else { | ||
256 | let default = | ||
257 | self.type_variable_table.fallback_value(tv, kind).cast(&Interner); | ||
258 | fallback(tv, VariableKind::Ty(kind), default) | ||
259 | .assert_ty_ref(&Interner) | ||
260 | .clone() | ||
261 | } | ||
262 | } | ||
263 | _ => ty, | ||
264 | }, | 235 | }, |
265 | DebruijnIndex::INNERMOST, | 236 | DebruijnIndex::INNERMOST, |
266 | ) | 237 | ) |
238 | .expect("fold failed unexpectedly") | ||
267 | } | 239 | } |
268 | 240 | ||
269 | pub(crate) fn resolve_ty_completely(&mut self, ty: Ty) -> Ty { | 241 | pub(crate) fn resolve_ty_completely(&mut self, ty: Ty) -> Ty { |
270 | self.resolve_with_fallback(ty, |_, _, d| d) | 242 | self.resolve_with_fallback(ty, |_, _, d, _| d) |
271 | } | 243 | } |
272 | 244 | ||
273 | // FIXME get rid of this, instead resolve shallowly where necessary | 245 | // FIXME get rid of this, instead resolve shallowly where necessary |
@@ -316,9 +288,7 @@ impl<'a> InferenceTable<'a> { | |||
316 | } | 288 | } |
317 | 289 | ||
318 | /// Resolves the type as far as currently possible, replacing type variables | 290 | /// Resolves the type as far as currently possible, replacing type variables |
319 | /// by their known types. All types returned by the infer_* functions should | 291 | /// by their known types. |
320 | /// be resolved as far as possible, i.e. contain no type variables with | ||
321 | /// known type. | ||
322 | fn resolve_ty_as_possible_inner(&mut self, tv_stack: &mut Vec<InferenceVar>, ty: Ty) -> Ty { | 292 | fn resolve_ty_as_possible_inner(&mut self, tv_stack: &mut Vec<InferenceVar>, ty: Ty) -> Ty { |
323 | fold_tys( | 293 | fold_tys( |
324 | ty, | 294 | ty, |
@@ -356,3 +326,102 @@ impl<'a> fmt::Debug for InferenceTable<'a> { | |||
356 | .finish() | 326 | .finish() |
357 | } | 327 | } |
358 | } | 328 | } |
329 | |||
330 | mod resolve { | ||
331 | use super::{ChalkInferenceTable, TypeVariableTable}; | ||
332 | use crate::{ | ||
333 | ConcreteConst, Const, ConstData, ConstValue, DebruijnIndex, GenericArg, InferenceVar, | ||
334 | Interner, Ty, TyVariableKind, VariableKind, | ||
335 | }; | ||
336 | use chalk_ir::{ | ||
337 | cast::Cast, | ||
338 | fold::{Fold, Folder}, | ||
339 | Fallible, | ||
340 | }; | ||
341 | use hir_def::type_ref::ConstScalar; | ||
342 | |||
343 | pub(super) struct Resolver<'a, F> { | ||
344 | pub type_variable_table: &'a TypeVariableTable, | ||
345 | pub var_unification_table: &'a mut ChalkInferenceTable, | ||
346 | pub var_stack: &'a mut Vec<InferenceVar>, | ||
347 | pub fallback: F, | ||
348 | } | ||
349 | impl<'a, 'i, F> Folder<'i, Interner> for Resolver<'a, F> | ||
350 | where | ||
351 | F: Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg + 'i, | ||
352 | { | ||
353 | fn as_dyn(&mut self) -> &mut dyn Folder<'i, Interner> { | ||
354 | self | ||
355 | } | ||
356 | |||
357 | fn interner(&self) -> &'i Interner { | ||
358 | &Interner | ||
359 | } | ||
360 | |||
361 | fn fold_inference_ty( | ||
362 | &mut self, | ||
363 | var: InferenceVar, | ||
364 | kind: TyVariableKind, | ||
365 | outer_binder: DebruijnIndex, | ||
366 | ) -> Fallible<Ty> { | ||
367 | let var = self.var_unification_table.inference_var_root(var); | ||
368 | if self.var_stack.contains(&var) { | ||
369 | cov_mark::hit!(type_var_cycles_resolve_as_possible); | ||
370 | // recursive type | ||
371 | let default = self.type_variable_table.fallback_value(var, kind).cast(&Interner); | ||
372 | return Ok((self.fallback)(var, VariableKind::Ty(kind), default, outer_binder) | ||
373 | .assert_ty_ref(&Interner) | ||
374 | .clone()); | ||
375 | } | ||
376 | let result = if let Some(known_ty) = self.var_unification_table.probe_var(var) { | ||
377 | // known_ty may contain other variables that are known by now | ||
378 | self.var_stack.push(var); | ||
379 | let result = | ||
380 | known_ty.fold_with(self, outer_binder).expect("fold failed unexpectedly"); | ||
381 | self.var_stack.pop(); | ||
382 | result.assert_ty_ref(&Interner).clone() | ||
383 | } else { | ||
384 | let default = self.type_variable_table.fallback_value(var, kind).cast(&Interner); | ||
385 | (self.fallback)(var, VariableKind::Ty(kind), default, outer_binder) | ||
386 | .assert_ty_ref(&Interner) | ||
387 | .clone() | ||
388 | }; | ||
389 | Ok(result) | ||
390 | } | ||
391 | |||
392 | fn fold_inference_const( | ||
393 | &mut self, | ||
394 | ty: Ty, | ||
395 | var: InferenceVar, | ||
396 | outer_binder: DebruijnIndex, | ||
397 | ) -> Fallible<Const> { | ||
398 | let var = self.var_unification_table.inference_var_root(var); | ||
399 | let default = ConstData { | ||
400 | ty: ty.clone(), | ||
401 | value: ConstValue::Concrete(ConcreteConst { interned: ConstScalar::Unknown }), | ||
402 | } | ||
403 | .intern(&Interner) | ||
404 | .cast(&Interner); | ||
405 | if self.var_stack.contains(&var) { | ||
406 | cov_mark::hit!(type_var_cycles_resolve_as_possible); | ||
407 | // recursive | ||
408 | return Ok((self.fallback)(var, VariableKind::Const(ty), default, outer_binder) | ||
409 | .assert_const_ref(&Interner) | ||
410 | .clone()); | ||
411 | } | ||
412 | let result = if let Some(known_ty) = self.var_unification_table.probe_var(var) { | ||
413 | // known_ty may contain other variables that are known by now | ||
414 | self.var_stack.push(var); | ||
415 | let result = | ||
416 | known_ty.fold_with(self, outer_binder).expect("fold failed unexpectedly"); | ||
417 | self.var_stack.pop(); | ||
418 | result.assert_const_ref(&Interner).clone() | ||
419 | } else { | ||
420 | (self.fallback)(var, VariableKind::Const(ty), default, outer_binder) | ||
421 | .assert_const_ref(&Interner) | ||
422 | .clone() | ||
423 | }; | ||
424 | Ok(result) | ||
425 | } | ||
426 | } | ||
427 | } | ||