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::TypeFoldable, interner::HasInterner, zip::Zip, CanonicalVarKind, FloatTy,
   7     IntTy, NoSolution, TyVariableKind, UniverseIndex,
   8 };
   9 use chalk_solve::infer::ParameterEnaVariableExt;
  10 use ena::unify::UnifyKey;
  11 use hir_expand::name;
  12 use stdx::never;
  13
  14 use super::{InferOk, InferResult, InferenceContext, TypeError};
  15 use crate::{
  16     db::HirDatabase, fold_tys, static_lifetime, traits::FnTrait, AliasEq, AliasTy, BoundVar,
  17     Canonical, Const, DebruijnIndex, GenericArg, GenericArgData, Goal, Guidance, InEnvironment,
  18     InferenceVar, Interner, Lifetime, ParamKind, ProjectionTy, ProjectionTyExt, Scalar, Solution,
  19     Substitution, TraitEnvironment, Ty, TyBuilder, TyExt, TyKind, VariableKind,
  20 };
  21
  22 impl<'a> InferenceContext<'a> {
  23     pub(super) fn canonicalize<T: TypeFoldable<Interner> + HasInterner<Interner = Interner>>(
  24         &mut self,
  25         t: T,
  26     ) -> Canonicalized<T>
  27     where
  28         T: HasInterner<Interner = Interner>,
  29     {
  30         self.table.canonicalize(t)
  31     }
  32 }
  33
  34 #[derive(Debug, Clone)]
  35 pub(crate) struct Canonicalized<T>
  36 where
  37     T: HasInterner<Interner = Interner>,
  38 {
  39     pub(crate) value: Canonical<T>,
  40     free_vars: Vec<GenericArg>,
  41 }
  42
  43 impl<T: HasInterner<Interner = Interner>> Canonicalized<T> {
  44     pub(super) fn apply_solution(
  45         &self,
  46         ctx: &mut InferenceTable<'_>,
  47         solution: Canonical<Substitution>,
  48     ) {
  49         // the solution may contain new variables, which we need to convert to new inference vars
  50         let new_vars = Substitution::from_iter(
  51             Interner,
  52             solution.binders.iter(Interner).map(|k| match &k.kind {
  53                 VariableKind::Ty(TyVariableKind::General) => ctx.new_type_var().cast(Interner),
  54                 VariableKind::Ty(TyVariableKind::Integer) => ctx.new_integer_var().cast(Interner),
  55                 VariableKind::Ty(TyVariableKind::Float) => ctx.new_float_var().cast(Interner),
  56                 // Chalk can sometimes return new lifetime variables. We just use the static lifetime everywhere
  57                 VariableKind::Lifetime => static_lifetime().cast(Interner),
  58                 VariableKind::Const(ty) => ctx.new_const_var(ty.clone()).cast(Interner),
  59             }),
  60         );
  61         for (i, v) in solution.value.iter(Interner).enumerate() {
  62             let var = self.free_vars[i].clone();
  63             if let Some(ty) = v.ty(Interner) {
  64                 // eagerly replace projections in the type; we may be getting types
  65                 // e.g. from where clauses where this hasn't happened yet
  66                 let ty = ctx.normalize_associated_types_in(new_vars.apply(ty.clone(), Interner));
  67                 ctx.unify(var.assert_ty_ref(Interner), &ty);
  68             } else {
  69                 let _ = ctx.try_unify(&var, &new_vars.apply(v.clone(), Interner));
  70             }
  71         }
  72     }
  73 }
  74
  75 pub fn could_unify(
  76     db: &dyn HirDatabase,
  77     env: Arc<TraitEnvironment>,
  78     tys: &Canonical<(Ty, Ty)>,
  79 ) -> bool {
  80     unify(db, env, tys).is_some()
  81 }
  82
  83 pub(crate) fn unify(
  84     db: &dyn HirDatabase,
  85     env: Arc<TraitEnvironment>,
  86     tys: &Canonical<(Ty, Ty)>,
  87 ) -> Option<Substitution> {
  88     let mut table = InferenceTable::new(db, env);
  89     let vars = Substitution::from_iter(
  90         Interner,
  91         tys.binders.iter(Interner).map(|x| match &x.kind {
  92             chalk_ir::VariableKind::Ty(_) => {
  93                 GenericArgData::Ty(table.new_type_var()).intern(Interner)
  94             }
  95             chalk_ir::VariableKind::Lifetime => {
  96                 GenericArgData::Ty(table.new_type_var()).intern(Interner)
  97             } // FIXME: maybe wrong?
  98             chalk_ir::VariableKind::Const(ty) => {
  99                 GenericArgData::Const(table.new_const_var(ty.clone())).intern(Interner)
 100             }
 101         }),
 102     );
 103     let ty1_with_vars = vars.apply(tys.value.0.clone(), Interner);
 104     let ty2_with_vars = vars.apply(tys.value.1.clone(), Interner);
 105     if !table.unify(&ty1_with_vars, &ty2_with_vars) {
 106         return None;
 107     }
 108     // default any type vars that weren't unified back to their original bound vars
 109     // (kind of hacky)
 110     let find_var = |iv| {
 111         vars.iter(Interner).position(|v| match v.interned() {
 112             chalk_ir::GenericArgData::Ty(ty) => ty.inference_var(Interner),
 113             chalk_ir::GenericArgData::Lifetime(lt) => lt.inference_var(Interner),
 114             chalk_ir::GenericArgData::Const(c) => c.inference_var(Interner),
 115         } == Some(iv))
 116     };
 117     let fallback = |iv, kind, default, binder| match kind {
 118         chalk_ir::VariableKind::Ty(_ty_kind) => find_var(iv)
 119             .map_or(default, |i| BoundVar::new(binder, i).to_ty(Interner).cast(Interner)),
 120         chalk_ir::VariableKind::Lifetime => find_var(iv)
 121             .map_or(default, |i| BoundVar::new(binder, i).to_lifetime(Interner).cast(Interner)),
 122         chalk_ir::VariableKind::Const(ty) => find_var(iv)
 123             .map_or(default, |i| BoundVar::new(binder, i).to_const(Interner, ty).cast(Interner)),
 124     };
 125     Some(Substitution::from_iter(
 126         Interner,
 127         vars.iter(Interner).map(|v| table.resolve_with_fallback(v.clone(), &fallback)),
 128     ))
 129 }
 130
 131 #[derive(Copy, Clone, Debug)]
 132 pub(crate) struct TypeVariableData {
 133     diverging: bool,
 134 }
 135
 136 type ChalkInferenceTable = chalk_solve::infer::InferenceTable<Interner>;
 137
 138 #[derive(Clone)]
 139 pub(crate) struct InferenceTable<'a> {
 140     pub(crate) db: &'a dyn HirDatabase,
 141     pub(crate) trait_env: Arc<TraitEnvironment>,
 142     var_unification_table: ChalkInferenceTable,
 143     type_variable_table: Vec<TypeVariableData>,
 144     pending_obligations: Vec<Canonicalized<InEnvironment<Goal>>>,
 145 }
 146
 147 pub(crate) struct InferenceTableSnapshot {
 148     var_table_snapshot: chalk_solve::infer::InferenceSnapshot<Interner>,
 149     pending_obligations: Vec<Canonicalized<InEnvironment<Goal>>>,
 150     type_variable_table_snapshot: Vec<TypeVariableData>,
 151 }
 152
 153 impl<'a> InferenceTable<'a> {
 154     pub(crate) fn new(db: &'a dyn HirDatabase, trait_env: Arc<TraitEnvironment>) -> Self {
 155         InferenceTable {
 156             db,
 157             trait_env,
 158             var_unification_table: ChalkInferenceTable::new(),
 159             type_variable_table: Vec::new(),
 160             pending_obligations: Vec::new(),
 161         }
 162     }
 163
 164     /// Chalk doesn't know about the `diverging` flag, so when it unifies two
 165     /// type variables of which one is diverging, the chosen root might not be
 166     /// diverging and we have no way of marking it as such at that time. This
 167     /// function goes through all type variables and make sure their root is
 168     /// marked as diverging if necessary, so that resolving them gives the right
 169     /// result.
 170     pub(super) fn propagate_diverging_flag(&mut self) {
 171         for i in 0..self.type_variable_table.len() {
 172             if !self.type_variable_table[i].diverging {
 173                 continue;
 174             }
 175             let v = InferenceVar::from(i as u32);
 176             let root = self.var_unification_table.inference_var_root(v);
 177             if let Some(data) = self.type_variable_table.get_mut(root.index() as usize) {
 178                 data.diverging = true;
 179             }
 180         }
 181     }
 182
 183     pub(super) fn set_diverging(&mut self, iv: InferenceVar, diverging: bool) {
 184         self.type_variable_table[iv.index() as usize].diverging = diverging;
 185     }
 186
 187     fn fallback_value(&self, iv: InferenceVar, kind: TyVariableKind) -> Ty {
 188         match kind {
 189             _ if self
 190                 .type_variable_table
 191                 .get(iv.index() as usize)
 192                 .map_or(false, |data| data.diverging) =>
 193             {
 194                 TyKind::Never
 195             }
 196             TyVariableKind::General => TyKind::Error,
 197             TyVariableKind::Integer => TyKind::Scalar(Scalar::Int(IntTy::I32)),
 198             TyVariableKind::Float => TyKind::Scalar(Scalar::Float(FloatTy::F64)),
 199         }
 200         .intern(Interner)
 201     }
 202
 203     pub(crate) fn canonicalize<T: TypeFoldable<Interner> + HasInterner<Interner = Interner>>(
 204         &mut self,
 205         t: T,
 206     ) -> Canonicalized<T>
 207     where
 208         T: HasInterner<Interner = Interner>,
 209     {
 210         // try to resolve obligations before canonicalizing, since this might
 211         // result in new knowledge about variables
 212         self.resolve_obligations_as_possible();
 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(crate) 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(crate) 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
 296     where
 297         T: HasInterner<Interner = Interner> + TypeFoldable<Interner>,
 298     {
 299         self.resolve_with_fallback_inner(&mut Vec::new(), t, &fallback)
 300     }
 301
 302     pub(crate) fn fresh_subst(&mut self, binders: &[CanonicalVarKind<Interner>]) -> Substitution {
 303         Substitution::from_iter(
 304             Interner,
 305             binders.iter().map(|kind| {
 306                 let param_infer_var =
 307                     kind.map_ref(|&ui| self.var_unification_table.new_variable(ui));
 308                 param_infer_var.to_generic_arg(Interner)
 309             }),
 310         )
 311     }
 312
 313     pub(crate) fn instantiate_canonical<T>(&mut self, canonical: Canonical<T>) -> T
 314     where
 315         T: HasInterner<Interner = Interner> + TypeFoldable<Interner> + std::fmt::Debug,
 316     {
 317         let subst = self.fresh_subst(canonical.binders.as_slice(Interner));
 318         subst.apply(canonical.value, Interner)
 319     }
 320
 321     fn resolve_with_fallback_inner<T>(
 322         &mut self,
 323         var_stack: &mut Vec<InferenceVar>,
 324         t: T,
 325         fallback: &dyn Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg,
 326     ) -> T
 327     where
 328         T: HasInterner<Interner = Interner> + TypeFoldable<Interner>,
 329     {
 330         t.fold_with(
 331             &mut resolve::Resolver { table: self, var_stack, fallback },
 332             DebruijnIndex::INNERMOST,
 333         )
 334         .expect("fold failed unexpectedly")
 335     }
 336
 337     pub(crate) fn resolve_completely<T>(&mut self, t: T) -> T
 338     where
 339         T: HasInterner<Interner = Interner> + TypeFoldable<Interner>,
 340     {
 341         self.resolve_with_fallback(t, &|_, _, d, _| d)
 342     }
 343
 344     /// Unify two types and register new trait goals that arise from that.
 345     pub(crate) fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
 346         let result = match self.try_unify(ty1, ty2) {
 347             Ok(r) => r,
 348             Err(_) => return false,
 349         };
 350         self.register_infer_ok(result);
 351         true
 352     }
 353
 354     /// Unify two types and return new trait goals arising from it, so the
 355     /// caller needs to deal with them.
 356     pub(crate) fn try_unify<T: Zip<Interner>>(&mut self, t1: &T, t2: &T) -> InferResult<()> {
 357         match self.var_unification_table.relate(
 358             Interner,
 359             &self.db,
 360             &self.trait_env.env,
 361             chalk_ir::Variance::Invariant,
 362             t1,
 363             t2,
 364         ) {
 365             Ok(result) => Ok(InferOk { goals: result.goals, value: () }),
 366             Err(chalk_ir::NoSolution) => Err(TypeError),
 367         }
 368     }
 369
 370     /// If `ty` is a type variable with known type, returns that type;
 371     /// otherwise, return ty.
 372     pub(crate) fn resolve_ty_shallow(&mut self, ty: &Ty) -> Ty {
 373         self.resolve_obligations_as_possible();
 374         self.var_unification_table.normalize_ty_shallow(Interner, ty).unwrap_or_else(|| ty.clone())
 375     }
 376
 377     pub(crate) fn snapshot(&mut self) -> InferenceTableSnapshot {
 378         let var_table_snapshot = self.var_unification_table.snapshot();
 379         let type_variable_table_snapshot = self.type_variable_table.clone();
 380         let pending_obligations = self.pending_obligations.clone();
 381         InferenceTableSnapshot {
 382             var_table_snapshot,
 383             pending_obligations,
 384             type_variable_table_snapshot,
 385         }
 386     }
 387
 388     pub(crate) fn rollback_to(&mut self, snapshot: InferenceTableSnapshot) {
 389         self.var_unification_table.rollback_to(snapshot.var_table_snapshot);
 390         self.type_variable_table = snapshot.type_variable_table_snapshot;
 391         self.pending_obligations = snapshot.pending_obligations;
 392     }
 393
 394     pub(crate) fn run_in_snapshot<T>(&mut self, f: impl FnOnce(&mut InferenceTable<'_>) -> T) -> T {
 395         let snapshot = self.snapshot();
 396         let result = f(self);
 397         self.rollback_to(snapshot);
 398         result
 399     }
 400
 401     /// Checks an obligation without registering it. Useful mostly to check
 402     /// whether a trait *might* be implemented before deciding to 'lock in' the
 403     /// choice (during e.g. method resolution or deref).
 404     pub(crate) fn try_obligation(&mut self, goal: Goal) -> Option<Solution> {
 405         let in_env = InEnvironment::new(&self.trait_env.env, goal);
 406         let canonicalized = self.canonicalize(in_env);
 407         let solution = self.db.trait_solve(self.trait_env.krate, canonicalized.value);
 408         solution
 409     }
 410
 411     pub(crate) fn register_obligation(&mut self, goal: Goal) {
 412         let in_env = InEnvironment::new(&self.trait_env.env, goal);
 413         self.register_obligation_in_env(in_env)
 414     }
 415
 416     fn register_obligation_in_env(&mut self, goal: InEnvironment<Goal>) {
 417         let canonicalized = self.canonicalize(goal);
 418         if !self.try_resolve_obligation(&canonicalized) {
 419             self.pending_obligations.push(canonicalized);
 420         }
 421     }
 422
 423     pub(crate) fn register_infer_ok<T>(&mut self, infer_ok: InferOk<T>) {
 424         infer_ok.goals.into_iter().for_each(|goal| self.register_obligation_in_env(goal));
 425     }
 426
 427     pub(crate) fn resolve_obligations_as_possible(&mut self) {
 428         let _span = profile::span("resolve_obligations_as_possible");
 429         let mut changed = true;
 430         let mut obligations = Vec::new();
 431         while changed {
 432             changed = false;
 433             mem::swap(&mut self.pending_obligations, &mut obligations);
 434             for canonicalized in obligations.drain(..) {
 435                 if !self.check_changed(&canonicalized) {
 436                     self.pending_obligations.push(canonicalized);
 437                     continue;
 438                 }
 439                 changed = true;
 440                 let uncanonical = chalk_ir::Substitute::apply(
 441                     &canonicalized.free_vars,
 442                     canonicalized.value.value,
 443                     Interner,
 444                 );
 445                 self.register_obligation_in_env(uncanonical);
 446             }
 447         }
 448     }
 449
 450     pub(crate) fn fudge_inference<T: TypeFoldable<Interner>>(
 451         &mut self,
 452         f: impl FnOnce(&mut Self) -> T,
 453     ) -> T {
 454         use chalk_ir::fold::TypeFolder;
 455         struct VarFudger<'a, 'b> {
 456             table: &'a mut InferenceTable<'b>,
 457             highest_known_var: InferenceVar,
 458         }
 459         impl<'a, 'b> TypeFolder<Interner> for VarFudger<'a, 'b> {
 460             type Error = NoSolution;
 461
 462             fn as_dyn(&mut self) -> &mut dyn TypeFolder<Interner, Error = Self::Error> {
 463                 self
 464             }
 465
 466             fn interner(&self) -> Interner {
 467                 Interner
 468             }
 469
 470             fn fold_inference_ty(
 471                 &mut self,
 472                 var: chalk_ir::InferenceVar,
 473                 kind: TyVariableKind,
 474                 _outer_binder: chalk_ir::DebruijnIndex,
 475             ) -> chalk_ir::Fallible<chalk_ir::Ty<Interner>> {
 476                 Ok(if var < self.highest_known_var {
 477                     var.to_ty(Interner, kind)
 478                 } else {
 479                     self.table.new_type_var()
 480                 })
 481             }
 482
 483             fn fold_inference_lifetime(
 484                 &mut self,
 485                 var: chalk_ir::InferenceVar,
 486                 _outer_binder: chalk_ir::DebruijnIndex,
 487             ) -> chalk_ir::Fallible<chalk_ir::Lifetime<Interner>> {
 488                 Ok(if var < self.highest_known_var {
 489                     var.to_lifetime(Interner)
 490                 } else {
 491                     self.table.new_lifetime_var()
 492                 })
 493             }
 494
 495             fn fold_inference_const(
 496                 &mut self,
 497                 ty: chalk_ir::Ty<Interner>,
 498                 var: chalk_ir::InferenceVar,
 499                 _outer_binder: chalk_ir::DebruijnIndex,
 500             ) -> chalk_ir::Fallible<chalk_ir::Const<Interner>> {
 501                 Ok(if var < self.highest_known_var {
 502                     var.to_const(Interner, ty)
 503                 } else {
 504                     self.table.new_const_var(ty)
 505                 })
 506             }
 507         }
 508
 509         let snapshot = self.snapshot();
 510         let highest_known_var = self.new_type_var().inference_var(Interner).expect("inference_var");
 511         let result = f(self);
 512         self.rollback_to(snapshot);
 513         result
 514             .fold_with(&mut VarFudger { table: self, highest_known_var }, DebruijnIndex::INNERMOST)
 515             .expect("fold_with with VarFudger")
 516     }
 517
 518     /// This checks whether any of the free variables in the `canonicalized`
 519     /// have changed (either been unified with another variable, or with a
 520     /// value). If this is not the case, we don't need to try to solve the goal
 521     /// again -- it'll give the same result as last time.
 522     fn check_changed(&mut self, canonicalized: &Canonicalized<InEnvironment<Goal>>) -> bool {
 523         canonicalized.free_vars.iter().any(|var| {
 524             let iv = match var.data(Interner) {
 525                 chalk_ir::GenericArgData::Ty(ty) => ty.inference_var(Interner),
 526                 chalk_ir::GenericArgData::Lifetime(lt) => lt.inference_var(Interner),
 527                 chalk_ir::GenericArgData::Const(c) => c.inference_var(Interner),
 528             }
 529             .expect("free var is not inference var");
 530             if self.var_unification_table.probe_var(iv).is_some() {
 531                 return true;
 532             }
 533             let root = self.var_unification_table.inference_var_root(iv);
 534             iv != root
 535         })
 536     }
 537
 538     fn try_resolve_obligation(
 539         &mut self,
 540         canonicalized: &Canonicalized<InEnvironment<Goal>>,
 541     ) -> bool {
 542         let solution = self.db.trait_solve(self.trait_env.krate, canonicalized.value.clone());
 543
 544         match solution {
 545             Some(Solution::Unique(canonical_subst)) => {
 546                 canonicalized.apply_solution(
 547                     self,
 548                     Canonical {
 549                         binders: canonical_subst.binders,
 550                         // FIXME: handle constraints
 551                         value: canonical_subst.value.subst,
 552                     },
 553                 );
 554                 true
 555             }
 556             Some(Solution::Ambig(Guidance::Definite(substs))) => {
 557                 canonicalized.apply_solution(self, substs);
 558                 false
 559             }
 560             Some(_) => {
 561                 // FIXME use this when trying to resolve everything at the end
 562                 false
 563             }
 564             None => {
 565                 // FIXME obligation cannot be fulfilled => diagnostic
 566                 true
 567             }
 568         }
 569     }
 570
 571     pub(crate) fn callable_sig(&mut self, ty: &Ty, num_args: usize) -> Option<(Vec<Ty>, Ty)> {
 572         match ty.callable_sig(self.db) {
 573             Some(sig) => Some((sig.params().to_vec(), sig.ret().clone())),
 574             None => self.callable_sig_from_fn_trait(ty, num_args),
 575         }
 576     }
 577
 578     fn callable_sig_from_fn_trait(&mut self, ty: &Ty, num_args: usize) -> Option<(Vec<Ty>, Ty)> {
 579         let krate = self.trait_env.krate;
 580         let fn_once_trait = FnTrait::FnOnce.get_id(self.db, krate)?;
 581         let output_assoc_type =
 582             self.db.trait_data(fn_once_trait).associated_type_by_name(&name![Output])?;
 583
 584         let mut arg_tys = vec![];
 585         let arg_ty = TyBuilder::tuple(num_args)
 586             .fill(|x| {
 587                 let arg = match x {
 588                     ParamKind::Type => self.new_type_var(),
 589                     ParamKind::Const(ty) => {
 590                         never!("Tuple with const parameter");
 591                         return GenericArgData::Const(self.new_const_var(ty.clone()))
 592                             .intern(Interner);
 593                     }
 594                 };
 595                 arg_tys.push(arg.clone());
 596                 GenericArgData::Ty(arg).intern(Interner)
 597             })
 598             .build();
 599
 600         let projection = {
 601             let b = TyBuilder::assoc_type_projection(self.db, output_assoc_type);
 602             if b.remaining() != 2 {
 603                 return None;
 604             }
 605             b.push(ty.clone()).push(arg_ty).build()
 606         };
 607
 608         let trait_env = self.trait_env.env.clone();
 609         let obligation = InEnvironment {
 610             goal: projection.trait_ref(self.db).cast(Interner),
 611             environment: trait_env,
 612         };
 613         let canonical = self.canonicalize(obligation.clone());
 614         if self.db.trait_solve(krate, canonical.value.cast(Interner)).is_some() {
 615             self.register_obligation(obligation.goal);
 616             let return_ty = self.normalize_projection_ty(projection);
 617             Some((arg_tys, return_ty))
 618         } else {
 619             None
 620         }
 621     }
 622 }
 623
 624 impl<'a> fmt::Debug for InferenceTable<'a> {
 625     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 626         f.debug_struct("InferenceTable").field("num_vars", &self.type_variable_table.len()).finish()
 627     }
 628 }
 629
 630 mod resolve {
 631     use super::InferenceTable;
 632     use crate::{
 633         ConcreteConst, Const, ConstData, ConstValue, DebruijnIndex, GenericArg, InferenceVar,
 634         Interner, Lifetime, Ty, TyVariableKind, VariableKind,
 635     };
 636     use chalk_ir::{
 637         cast::Cast,
 638         fold::{TypeFoldable, TypeFolder},
 639         Fallible, NoSolution,
 640     };
 641     use hir_def::type_ref::ConstScalar;
 642
 643     pub(super) struct Resolver<'a, 'b, F> {
 644         pub(super) table: &'a mut InferenceTable<'b>,
 645         pub(super) var_stack: &'a mut Vec<InferenceVar>,
 646         pub(super) fallback: F,
 647     }
 648     impl<'a, 'b, 'i, F> TypeFolder<Interner> for Resolver<'a, 'b, F>
 649     where
 650         F: Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg + 'i,
 651     {
 652         type Error = NoSolution;
 653
 654         fn as_dyn(&mut self) -> &mut dyn TypeFolder<Interner, Error = Self::Error> {
 655             self
 656         }
 657
 658         fn interner(&self) -> Interner {
 659             Interner
 660         }
 661
 662         fn fold_inference_ty(
 663             &mut self,
 664             var: InferenceVar,
 665             kind: TyVariableKind,
 666             outer_binder: DebruijnIndex,
 667         ) -> Fallible<Ty> {
 668             let var = self.table.var_unification_table.inference_var_root(var);
 669             if self.var_stack.contains(&var) {
 670                 // recursive type
 671                 let default = self.table.fallback_value(var, kind).cast(Interner);
 672                 return Ok((self.fallback)(var, VariableKind::Ty(kind), default, outer_binder)
 673                     .assert_ty_ref(Interner)
 674                     .clone());
 675             }
 676             let result = if let Some(known_ty) = self.table.var_unification_table.probe_var(var) {
 677                 // known_ty may contain other variables that are known by now
 678                 self.var_stack.push(var);
 679                 let result =
 680                     known_ty.fold_with(self, outer_binder).expect("fold failed unexpectedly");
 681                 self.var_stack.pop();
 682                 result.assert_ty_ref(Interner).clone()
 683             } else {
 684                 let default = self.table.fallback_value(var, kind).cast(Interner);
 685                 (self.fallback)(var, VariableKind::Ty(kind), default, outer_binder)
 686                     .assert_ty_ref(Interner)
 687                     .clone()
 688             };
 689             Ok(result)
 690         }
 691
 692         fn fold_inference_const(
 693             &mut self,
 694             ty: Ty,
 695             var: InferenceVar,
 696             outer_binder: DebruijnIndex,
 697         ) -> Fallible<Const> {
 698             let var = self.table.var_unification_table.inference_var_root(var);
 699             let default = ConstData {
 700                 ty: ty.clone(),
 701                 value: ConstValue::Concrete(ConcreteConst { interned: ConstScalar::Unknown }),
 702             }
 703             .intern(Interner)
 704             .cast(Interner);
 705             if self.var_stack.contains(&var) {
 706                 // recursive
 707                 return Ok((self.fallback)(var, VariableKind::Const(ty), default, outer_binder)
 708                     .assert_const_ref(Interner)
 709                     .clone());
 710             }
 711             let result = if let Some(known_ty) = self.table.var_unification_table.probe_var(var) {
 712                 // known_ty may contain other variables that are known by now
 713                 self.var_stack.push(var);
 714                 let result =
 715                     known_ty.fold_with(self, outer_binder).expect("fold failed unexpectedly");
 716                 self.var_stack.pop();
 717                 result.assert_const_ref(Interner).clone()
 718             } else {
 719                 (self.fallback)(var, VariableKind::Const(ty), default, outer_binder)
 720                     .assert_const_ref(Interner)
 721                     .clone()
 722             };
 723             Ok(result)
 724         }
 725
 726         fn fold_inference_lifetime(
 727             &mut self,
 728             _var: InferenceVar,
 729             _outer_binder: DebruijnIndex,
 730         ) -> Fallible<Lifetime> {
 731             // fall back all lifetimes to 'static -- currently we don't deal
 732             // with any lifetimes, but we can sometimes get some lifetime
 733             // variables through Chalk's unification, and this at least makes
 734             // sure we don't leak them outside of inference
 735             Ok(crate::static_lifetime())
 736         }
 737     }
 738 }