aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--crates/hir_ty/src/infer/unify.rs165
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
330mod 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}