crates/hir_ty/src/infer/unify.rs

   1 //! Unification and canonicalization logic.
   2
   3 use std::{fmt, mem, sync::Arc};
   4
   5 use chalk_ir::{
   6     cast::Cast, fold::Fold, interner::HasInterner, zip::Zip, FloatTy, IntTy, TyVariableKind,
   7     UniverseIndex,
   8 };
   9 use chalk_solve::infer::ParameterEnaVariableExt;
  10 use ena::unify::UnifyKey;
  11
  12 use super::{InferOk, InferResult, InferenceContext, TypeError};
  13 use crate::{
  14     db::HirDatabase, fold_tys, static_lifetime, AliasEq, AliasTy, BoundVar, Canonical, Const,
  15     DebruijnIndex, GenericArg, Goal, Guidance, InEnvironment, InferenceVar, Interner, Lifetime,
  16     ProjectionTy, Scalar, Solution, Substitution, TraitEnvironment, Ty, TyKind, VariableKind,
  17 };
  18
  19 impl<'a> InferenceContext<'a> {
  20     pub(super) fn canonicalize<T: Fold<Interner> + HasInterner<Interner = Interner>>(
  21         &mut self,
  22         t: T,
  23     ) -> Canonicalized<T::Result>
  24     where
  25         T::Result: HasInterner<Interner = Interner>,
  26     {
  27         // try to resolve obligations before canonicalizing, since this might
  28         // result in new knowledge about variables
  29         self.resolve_obligations_as_possible();
  30         self.table.canonicalize(t)
  31     }
  32 }
  33
  34 #[derive(Debug, Clone)]
  35 pub(super) struct Canonicalized<T>
  36 where
  37     T: HasInterner<Interner = Interner>,
  38 {
  39     pub(super) value: Canonical<T>,
  40     free_vars: Vec<GenericArg>,
  41 }
  42
  43 impl<T: HasInterner<Interner = Interner>> Canonicalized<T> {
  44     /// this method is wrong and shouldn't exist
  45     pub(super) fn decanonicalize_ty(&self, table: &mut InferenceTable, ty: Canonical<Ty>) -> Ty {
  46         let mut vars = self.free_vars.clone();
  47         while ty.binders.len(&Interner) > vars.len() {
  48             vars.push(table.new_type_var().cast(&Interner));
  49         }
  50         chalk_ir::Substitute::apply(&vars, ty.value, &Interner)
  51     }
  52
  53     pub(super) fn apply_solution(
  54         &self,
  55         ctx: &mut InferenceTable,
  56         solution: Canonical<Substitution>,
  57     ) {
  58         // the solution may contain new variables, which we need to convert to new inference vars
  59         let new_vars = Substitution::from_iter(
  60             &Interner,
  61             solution.binders.iter(&Interner).map(|k| match k.kind {
  62                 VariableKind::Ty(TyVariableKind::General) => ctx.new_type_var().cast(&Interner),
  63                 VariableKind::Ty(TyVariableKind::Integer) => ctx.new_integer_var().cast(&Interner),
  64                 VariableKind::Ty(TyVariableKind::Float) => ctx.new_float_var().cast(&Interner),
  65                 // Chalk can sometimes return new lifetime variables. We just use the static lifetime everywhere
  66                 VariableKind::Lifetime => static_lifetime().cast(&Interner),
  67                 _ => panic!("const variable in solution"),
  68             }),
  69         );
  70         for (i, v) in solution.value.iter(&Interner).enumerate() {
  71             let var = self.free_vars[i].clone();
  72             if let Some(ty) = v.ty(&Interner) {
  73                 // eagerly replace projections in the type; we may be getting types
  74                 // e.g. from where clauses where this hasn't happened yet
  75                 let ty = ctx.normalize_associated_types_in(new_vars.apply(ty.clone(), &Interner));
  76                 ctx.unify(var.assert_ty_ref(&Interner), &ty);
  77             } else {
  78                 let _ = ctx.try_unify(&var, &new_vars.apply(v.clone(), &Interner));
  79             }
  80         }
  81     }
  82 }
  83
  84 pub fn could_unify(
  85     db: &dyn HirDatabase,
  86     env: Arc<TraitEnvironment>,
  87     tys: &Canonical<(Ty, Ty)>,
  88 ) -> bool {
  89     unify(db, env, tys).is_some()
  90 }
  91
  92 pub(crate) fn unify(
  93     db: &dyn HirDatabase,
  94     env: Arc<TraitEnvironment>,
  95     tys: &Canonical<(Ty, Ty)>,
  96 ) -> Option<Substitution> {
  97     let mut table = InferenceTable::new(db, env);
  98     let vars = Substitution::from_iter(
  99         &Interner,
 100         tys.binders
 101             .iter(&Interner)
 102             // we always use type vars here because we want everything to
 103             // fallback to Unknown in the end (kind of hacky, as below)
 104             .map(|_| table.new_type_var()),
 105     );
 106     let ty1_with_vars = vars.apply(tys.value.0.clone(), &Interner);
 107     let ty2_with_vars = vars.apply(tys.value.1.clone(), &Interner);
 108     if !table.unify(&ty1_with_vars, &ty2_with_vars) {
 109         return None;
 110     }
 111     // default any type vars that weren't unified back to their original bound vars
 112     // (kind of hacky)
 113     let find_var = |iv| {
 114         vars.iter(&Interner).position(|v| match v.interned() {
 115             chalk_ir::GenericArgData::Ty(ty) => ty.inference_var(&Interner),
 116             chalk_ir::GenericArgData::Lifetime(lt) => lt.inference_var(&Interner),
 117             chalk_ir::GenericArgData::Const(c) => c.inference_var(&Interner),
 118         } == Some(iv))
 119     };
 120     let fallback = |iv, kind, default, binder| match kind {
 121         chalk_ir::VariableKind::Ty(_ty_kind) => find_var(iv)
 122             .map_or(default, |i| BoundVar::new(binder, i).to_ty(&Interner).cast(&Interner)),
 123         chalk_ir::VariableKind::Lifetime => find_var(iv)
 124             .map_or(default, |i| BoundVar::new(binder, i).to_lifetime(&Interner).cast(&Interner)),
 125         chalk_ir::VariableKind::Const(ty) => find_var(iv)
 126             .map_or(default, |i| BoundVar::new(binder, i).to_const(&Interner, ty).cast(&Interner)),
 127     };
 128     Some(Substitution::from_iter(
 129         &Interner,
 130         vars.iter(&Interner)
 131             .map(|v| table.resolve_with_fallback(v.assert_ty_ref(&Interner).clone(), &fallback)),
 132     ))
 133 }
 134
 135 #[derive(Copy, Clone, Debug)]
 136 pub(crate) struct TypeVariableData {
 137     diverging: bool,
 138 }
 139
 140 type ChalkInferenceTable = chalk_solve::infer::InferenceTable<Interner>;
 141
 142 #[derive(Clone)]
 143 pub(crate) struct InferenceTable<'a> {
 144     pub(crate) db: &'a dyn HirDatabase,
 145     pub(crate) trait_env: Arc<TraitEnvironment>,
 146     var_unification_table: ChalkInferenceTable,
 147     type_variable_table: Vec<TypeVariableData>,
 148     pending_obligations: Vec<Canonicalized<InEnvironment<Goal>>>,
 149 }
 150
 151 pub(crate) struct InferenceTableSnapshot {
 152     var_table_snapshot: chalk_solve::infer::InferenceSnapshot<Interner>,
 153     // FIXME: snapshot type_variable_table, pending_obligations?
 154 }
 155
 156 impl<'a> InferenceTable<'a> {
 157     pub(crate) fn new(db: &'a dyn HirDatabase, trait_env: Arc<TraitEnvironment>) -> Self {
 158         InferenceTable {
 159             db,
 160             trait_env,
 161             var_unification_table: ChalkInferenceTable::new(),
 162             type_variable_table: Vec::new(),
 163             pending_obligations: Vec::new(),
 164         }
 165     }
 166
 167     /// Chalk doesn't know about the `diverging` flag, so when it unifies two
 168     /// type variables of which one is diverging, the chosen root might not be
 169     /// diverging and we have no way of marking it as such at that time. This
 170     /// function goes through all type variables and make sure their root is
 171     /// marked as diverging if necessary, so that resolving them gives the right
 172     /// result.
 173     pub(super) fn propagate_diverging_flag(&mut self) {
 174         for i in 0..self.type_variable_table.len() {
 175             if !self.type_variable_table[i].diverging {
 176                 continue;
 177             }
 178             let v = InferenceVar::from(i as u32);
 179             let root = self.var_unification_table.inference_var_root(v);
 180             if let Some(data) = self.type_variable_table.get_mut(root.index() as usize) {
 181                 data.diverging = true;
 182             }
 183         }
 184     }
 185
 186     pub(super) fn set_diverging(&mut self, iv: InferenceVar, diverging: bool) {
 187         self.type_variable_table[iv.index() as usize].diverging = diverging;
 188     }
 189
 190     fn fallback_value(&self, iv: InferenceVar, kind: TyVariableKind) -> Ty {
 191         match kind {
 192             _ if self
 193                 .type_variable_table
 194                 .get(iv.index() as usize)
 195                 .map_or(false, |data| data.diverging) =>
 196             {
 197                 TyKind::Never
 198             }
 199             TyVariableKind::General => TyKind::Error,
 200             TyVariableKind::Integer => TyKind::Scalar(Scalar::Int(IntTy::I32)),
 201             TyVariableKind::Float => TyKind::Scalar(Scalar::Float(FloatTy::F64)),
 202         }
 203         .intern(&Interner)
 204     }
 205
 206     pub(super) fn canonicalize<T: Fold<Interner> + HasInterner<Interner = Interner>>(
 207         &mut self,
 208         t: T,
 209     ) -> Canonicalized<T::Result>
 210     where
 211         T::Result: HasInterner<Interner = Interner>,
 212     {
 213         let result = self.var_unification_table.canonicalize(&Interner, t);
 214         let free_vars = result
 215             .free_vars
 216             .into_iter()
 217             .map(|free_var| free_var.to_generic_arg(&Interner))
 218             .collect();
 219         Canonicalized { value: result.quantified, free_vars }
 220     }
 221
 222     /// Recurses through the given type, normalizing associated types mentioned
 223     /// in it by replacing them by type variables and registering obligations to
 224     /// resolve later. This should be done once for every type we get from some
 225     /// type annotation (e.g. from a let type annotation, field type or function
 226     /// call). `make_ty` handles this already, but e.g. for field types we need
 227     /// to do it as well.
 228     pub(super) fn normalize_associated_types_in(&mut self, ty: Ty) -> Ty {
 229         fold_tys(
 230             ty,
 231             |ty, _| match ty.kind(&Interner) {
 232                 TyKind::Alias(AliasTy::Projection(proj_ty)) => {
 233                     self.normalize_projection_ty(proj_ty.clone())
 234                 }
 235                 _ => ty,
 236             },
 237             DebruijnIndex::INNERMOST,
 238         )
 239     }
 240
 241     pub(super) fn normalize_projection_ty(&mut self, proj_ty: ProjectionTy) -> Ty {
 242         let var = self.new_type_var();
 243         let alias_eq = AliasEq { alias: AliasTy::Projection(proj_ty), ty: var.clone() };
 244         let obligation = alias_eq.cast(&Interner);
 245         self.register_obligation(obligation);
 246         var
 247     }
 248
 249     fn extend_type_variable_table(&mut self, to_index: usize) {
 250         self.type_variable_table.extend(
 251             (0..1 + to_index - self.type_variable_table.len())
 252                 .map(|_| TypeVariableData { diverging: false }),
 253         );
 254     }
 255
 256     fn new_var(&mut self, kind: TyVariableKind, diverging: bool) -> Ty {
 257         let var = self.var_unification_table.new_variable(UniverseIndex::ROOT);
 258         // Chalk might have created some type variables for its own purposes that we don't know about...
 259         self.extend_type_variable_table(var.index() as usize);
 260         assert_eq!(var.index() as usize, self.type_variable_table.len() - 1);
 261         self.type_variable_table[var.index() as usize].diverging = diverging;
 262         var.to_ty_with_kind(&Interner, kind)
 263     }
 264
 265     pub(crate) fn new_type_var(&mut self) -> Ty {
 266         self.new_var(TyVariableKind::General, false)
 267     }
 268
 269     pub(crate) fn new_integer_var(&mut self) -> Ty {
 270         self.new_var(TyVariableKind::Integer, false)
 271     }
 272
 273     pub(crate) fn new_float_var(&mut self) -> Ty {
 274         self.new_var(TyVariableKind::Float, false)
 275     }
 276
 277     pub(crate) fn new_maybe_never_var(&mut self) -> Ty {
 278         self.new_var(TyVariableKind::General, true)
 279     }
 280
 281     pub(crate) fn new_const_var(&mut self, ty: Ty) -> Const {
 282         let var = self.var_unification_table.new_variable(UniverseIndex::ROOT);
 283         var.to_const(&Interner, ty)
 284     }
 285
 286     pub(crate) fn new_lifetime_var(&mut self) -> Lifetime {
 287         let var = self.var_unification_table.new_variable(UniverseIndex::ROOT);
 288         var.to_lifetime(&Interner)
 289     }
 290
 291     pub(crate) fn resolve_with_fallback<T>(
 292         &mut self,
 293         t: T,
 294         fallback: &dyn Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg,
 295     ) -> T::Result
 296     where
 297         T: HasInterner<Interner = Interner> + Fold<Interner>,
 298     {
 299         self.resolve_with_fallback_inner(&mut Vec::new(), t, &fallback)
 300     }
 301
 302     fn resolve_with_fallback_inner<T>(
 303         &mut self,
 304         var_stack: &mut Vec<InferenceVar>,
 305         t: T,
 306         fallback: &dyn Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg,
 307     ) -> T::Result
 308     where
 309         T: HasInterner<Interner = Interner> + Fold<Interner>,
 310     {
 311         t.fold_with(
 312             &mut resolve::Resolver { table: self, var_stack, fallback },
 313             DebruijnIndex::INNERMOST,
 314         )
 315         .expect("fold failed unexpectedly")
 316     }
 317
 318     pub(crate) fn resolve_completely<T>(&mut self, t: T) -> T::Result
 319     where
 320         T: HasInterner<Interner = Interner> + Fold<Interner>,
 321     {
 322         self.resolve_with_fallback(t, &|_, _, d, _| d)
 323     }
 324
 325     /// Unify two types and register new trait goals that arise from that.
 326     pub(crate) fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
 327         let result = match self.try_unify(ty1, ty2) {
 328             Ok(r) => r,
 329             Err(_) => return false,
 330         };
 331         self.register_infer_ok(result);
 332         true
 333     }
 334
 335     /// Unify two types and return new trait goals arising from it, so the
 336     /// caller needs to deal with them.
 337     pub(crate) fn try_unify<T: Zip<Interner>>(&mut self, t1: &T, t2: &T) -> InferResult<()> {
 338         match self.var_unification_table.relate(
 339             &Interner,
 340             &self.db,
 341             &self.trait_env.env,
 342             chalk_ir::Variance::Invariant,
 343             t1,
 344             t2,
 345         ) {
 346             Ok(result) => Ok(InferOk { goals: result.goals, value: () }),
 347             Err(chalk_ir::NoSolution) => Err(TypeError),
 348         }
 349     }
 350
 351     /// If `ty` is a type variable with known type, returns that type;
 352     /// otherwise, return ty.
 353     pub(crate) fn resolve_ty_shallow(&mut self, ty: &Ty) -> Ty {
 354         self.var_unification_table.normalize_ty_shallow(&Interner, ty).unwrap_or_else(|| ty.clone())
 355     }
 356
 357     pub(crate) fn snapshot(&mut self) -> InferenceTableSnapshot {
 358         let snapshot = self.var_unification_table.snapshot();
 359         InferenceTableSnapshot { var_table_snapshot: snapshot }
 360     }
 361
 362     pub(crate) fn rollback_to(&mut self, snapshot: InferenceTableSnapshot) {
 363         self.var_unification_table.rollback_to(snapshot.var_table_snapshot);
 364     }
 365
 366     pub(crate) fn register_obligation(&mut self, goal: Goal) {
 367         let in_env = InEnvironment::new(&self.trait_env.env, goal);
 368         self.register_obligation_in_env(in_env)
 369     }
 370
 371     fn register_obligation_in_env(&mut self, goal: InEnvironment<Goal>) {
 372         let canonicalized = self.canonicalize(goal);
 373         if !self.try_resolve_obligation(&canonicalized) {
 374             self.pending_obligations.push(canonicalized);
 375         }
 376     }
 377
 378     pub(crate) fn register_infer_ok<T>(&mut self, infer_ok: InferOk<T>) {
 379         infer_ok.goals.into_iter().for_each(|goal| self.register_obligation_in_env(goal));
 380     }
 381
 382     pub(crate) fn resolve_obligations_as_possible(&mut self) {
 383         let _span = profile::span("resolve_obligations_as_possible");
 384         let mut changed = true;
 385         let mut obligations = Vec::new();
 386         while changed {
 387             changed = false;
 388             mem::swap(&mut self.pending_obligations, &mut obligations);
 389             for canonicalized in obligations.drain(..) {
 390                 if !self.check_changed(&canonicalized) {
 391                     self.pending_obligations.push(canonicalized);
 392                     continue;
 393                 }
 394                 changed = true;
 395                 let uncanonical = chalk_ir::Substitute::apply(
 396                     &canonicalized.free_vars,
 397                     canonicalized.value.value,
 398                     &Interner,
 399                 );
 400                 self.register_obligation_in_env(uncanonical);
 401             }
 402         }
 403     }
 404
 405     pub(crate) fn fudge_inference<T: Fold<Interner>>(
 406         &mut self,
 407         f: impl FnOnce(&mut Self) -> T,
 408     ) -> T::Result {
 409         use chalk_ir::fold::Folder;
 410         struct VarFudger<'a, 'b> {
 411             table: &'a mut InferenceTable<'b>,
 412             highest_known_var: InferenceVar,
 413         }
 414         impl<'a, 'b> Folder<'static, Interner> for VarFudger<'a, 'b> {
 415             fn as_dyn(&mut self) -> &mut dyn Folder<'static, Interner> {
 416                 self
 417             }
 418
 419             fn interner(&self) -> &'static Interner {
 420                 &Interner
 421             }
 422
 423             fn fold_inference_ty(
 424                 &mut self,
 425                 var: chalk_ir::InferenceVar,
 426                 kind: TyVariableKind,
 427                 _outer_binder: chalk_ir::DebruijnIndex,
 428             ) -> chalk_ir::Fallible<chalk_ir::Ty<Interner>> {
 429                 Ok(if var < self.highest_known_var {
 430                     var.to_ty(&Interner, kind)
 431                 } else {
 432                     self.table.new_type_var()
 433                 })
 434             }
 435
 436             fn fold_inference_lifetime(
 437                 &mut self,
 438                 var: chalk_ir::InferenceVar,
 439                 _outer_binder: chalk_ir::DebruijnIndex,
 440             ) -> chalk_ir::Fallible<chalk_ir::Lifetime<Interner>> {
 441                 Ok(if var < self.highest_known_var {
 442                     var.to_lifetime(&Interner)
 443                 } else {
 444                     self.table.new_lifetime_var()
 445                 })
 446             }
 447
 448             fn fold_inference_const(
 449                 &mut self,
 450                 ty: chalk_ir::Ty<Interner>,
 451                 var: chalk_ir::InferenceVar,
 452                 _outer_binder: chalk_ir::DebruijnIndex,
 453             ) -> chalk_ir::Fallible<chalk_ir::Const<Interner>> {
 454                 Ok(if var < self.highest_known_var {
 455                     var.to_const(&Interner, ty)
 456                 } else {
 457                     self.table.new_const_var(ty)
 458                 })
 459             }
 460         }
 461
 462         let snapshot = self.snapshot();
 463         let highest_known_var =
 464             self.new_type_var().inference_var(&Interner).expect("inference_var");
 465         let result = f(self);
 466         self.rollback_to(snapshot);
 467         result
 468             .fold_with(&mut VarFudger { table: self, highest_known_var }, DebruijnIndex::INNERMOST)
 469             .expect("fold_with with VarFudger")
 470     }
 471
 472     /// This checks whether any of the free variables in the `canonicalized`
 473     /// have changed (either been unified with another variable, or with a
 474     /// value). If this is not the case, we don't need to try to solve the goal
 475     /// again -- it'll give the same result as last time.
 476     fn check_changed(&mut self, canonicalized: &Canonicalized<InEnvironment<Goal>>) -> bool {
 477         canonicalized.free_vars.iter().any(|var| {
 478             let iv = match var.data(&Interner) {
 479                 chalk_ir::GenericArgData::Ty(ty) => ty.inference_var(&Interner),
 480                 chalk_ir::GenericArgData::Lifetime(lt) => lt.inference_var(&Interner),
 481                 chalk_ir::GenericArgData::Const(c) => c.inference_var(&Interner),
 482             }
 483             .expect("free var is not inference var");
 484             if self.var_unification_table.probe_var(iv).is_some() {
 485                 return true;
 486             }
 487             let root = self.var_unification_table.inference_var_root(iv);
 488             iv != root
 489         })
 490     }
 491
 492     fn try_resolve_obligation(
 493         &mut self,
 494         canonicalized: &Canonicalized<InEnvironment<Goal>>,
 495     ) -> bool {
 496         let solution = self.db.trait_solve(self.trait_env.krate, canonicalized.value.clone());
 497
 498         match solution {
 499             Some(Solution::Unique(canonical_subst)) => {
 500                 canonicalized.apply_solution(
 501                     self,
 502                     Canonical {
 503                         binders: canonical_subst.binders,
 504                         // FIXME: handle constraints
 505                         value: canonical_subst.value.subst,
 506                     },
 507                 );
 508                 true
 509             }
 510             Some(Solution::Ambig(Guidance::Definite(substs))) => {
 511                 canonicalized.apply_solution(self, substs);
 512                 false
 513             }
 514             Some(_) => {
 515                 // FIXME use this when trying to resolve everything at the end
 516                 false
 517             }
 518             None => {
 519                 // FIXME obligation cannot be fulfilled => diagnostic
 520                 true
 521             }
 522         }
 523     }
 524 }
 525
 526 impl<'a> fmt::Debug for InferenceTable<'a> {
 527     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 528         f.debug_struct("InferenceTable").field("num_vars", &self.type_variable_table.len()).finish()
 529     }
 530 }
 531
 532 mod resolve {
 533     use super::InferenceTable;
 534     use crate::{
 535         ConcreteConst, Const, ConstData, ConstValue, DebruijnIndex, GenericArg, InferenceVar,
 536         Interner, Lifetime, Ty, TyVariableKind, VariableKind,
 537     };
 538     use chalk_ir::{
 539         cast::Cast,
 540         fold::{Fold, Folder},
 541         Fallible,
 542     };
 543     use hir_def::type_ref::ConstScalar;
 544
 545     pub(super) struct Resolver<'a, 'b, F> {
 546         pub(super) table: &'a mut InferenceTable<'b>,
 547         pub(super) var_stack: &'a mut Vec<InferenceVar>,
 548         pub(super) fallback: F,
 549     }
 550     impl<'a, 'b, 'i, F> Folder<'i, Interner> for Resolver<'a, 'b, F>
 551     where
 552         F: Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg + 'i,
 553     {
 554         fn as_dyn(&mut self) -> &mut dyn Folder<'i, Interner> {
 555             self
 556         }
 557
 558         fn interner(&self) -> &'i Interner {
 559             &Interner
 560         }
 561
 562         fn fold_inference_ty(
 563             &mut self,
 564             var: InferenceVar,
 565             kind: TyVariableKind,
 566             outer_binder: DebruijnIndex,
 567         ) -> Fallible<Ty> {
 568             let var = self.table.var_unification_table.inference_var_root(var);
 569             if self.var_stack.contains(&var) {
 570                 // recursive type
 571                 let default = self.table.fallback_value(var, kind).cast(&Interner);
 572                 return Ok((self.fallback)(var, VariableKind::Ty(kind), default, outer_binder)
 573                     .assert_ty_ref(&Interner)
 574                     .clone());
 575             }
 576             let result = if let Some(known_ty) = self.table.var_unification_table.probe_var(var) {
 577                 // known_ty may contain other variables that are known by now
 578                 self.var_stack.push(var);
 579                 let result =
 580                     known_ty.fold_with(self, outer_binder).expect("fold failed unexpectedly");
 581                 self.var_stack.pop();
 582                 result.assert_ty_ref(&Interner).clone()
 583             } else {
 584                 let default = self.table.fallback_value(var, kind).cast(&Interner);
 585                 (self.fallback)(var, VariableKind::Ty(kind), default, outer_binder)
 586                     .assert_ty_ref(&Interner)
 587                     .clone()
 588             };
 589             Ok(result)
 590         }
 591
 592         fn fold_inference_const(
 593             &mut self,
 594             ty: Ty,
 595             var: InferenceVar,
 596             outer_binder: DebruijnIndex,
 597         ) -> Fallible<Const> {
 598             let var = self.table.var_unification_table.inference_var_root(var);
 599             let default = ConstData {
 600                 ty: ty.clone(),
 601                 value: ConstValue::Concrete(ConcreteConst { interned: ConstScalar::Unknown }),
 602             }
 603             .intern(&Interner)
 604             .cast(&Interner);
 605             if self.var_stack.contains(&var) {
 606                 // recursive
 607                 return Ok((self.fallback)(var, VariableKind::Const(ty), default, outer_binder)
 608                     .assert_const_ref(&Interner)
 609                     .clone());
 610             }
 611             let result = if let Some(known_ty) = self.table.var_unification_table.probe_var(var) {
 612                 // known_ty may contain other variables that are known by now
 613                 self.var_stack.push(var);
 614                 let result =
 615                     known_ty.fold_with(self, outer_binder).expect("fold failed unexpectedly");
 616                 self.var_stack.pop();
 617                 result.assert_const_ref(&Interner).clone()
 618             } else {
 619                 (self.fallback)(var, VariableKind::Const(ty), default, outer_binder)
 620                     .assert_const_ref(&Interner)
 621                     .clone()
 622             };
 623             Ok(result)
 624         }
 625
 626         fn fold_inference_lifetime(
 627             &mut self,
 628             _var: InferenceVar,
 629             _outer_binder: DebruijnIndex,
 630         ) -> Fallible<Lifetime> {
 631             // fall back all lifetimes to 'static -- currently we don't deal
 632             // with any lifetimes, but we can sometimes get some lifetime
 633             // variables through Chalk's unification, and this at least makes
 634             // sure we don't leak them outside of inference
 635             Ok(crate::static_lifetime())
 636         }
 637     }
 638 }