| //! Unification and canonicalization logic. |
| |
| use std::{fmt, mem}; |
| |
| use chalk_ir::{ |
| cast::Cast, fold::TypeFoldable, interner::HasInterner, CanonicalVarKind, FloatTy, IntTy, TyVariableKind, |
| }; |
| use either::Either; |
| use hir_def::{AdtId, lang_item::LangItem}; |
| use hir_expand::name::Name; |
| use intern::sym; |
| use rustc_hash::{FxHashMap, FxHashSet}; |
| use rustc_next_trait_solver::solve::HasChanged; |
| use rustc_type_ir::{inherent::Span, relate::{solver_relating::RelateExt, Relate}, solve::{Certainty, NoSolution}, FloatVid, IntVid, TyVid}; |
| use smallvec::SmallVec; |
| use triomphe::Arc; |
| |
| use super::{InferOk, InferResult, InferenceContext, TypeError}; |
| use crate::{ |
| consteval::unknown_const, db::HirDatabase, fold_generic_args, fold_tys_and_consts, next_solver::{infer::{canonical::canonicalizer::OriginalQueryValues, snapshot::CombinedSnapshot, DbInternerInferExt, InferCtxt}, mapping::{ChalkToNextSolver, InferenceVarExt}, DbInterner, ParamEnvAnd, SolverDefIds}, to_chalk_trait_id, traits::{next_trait_solve, next_trait_solve_canonical, next_trait_solve_in_ctxt, FnTrait, NextTraitSolveResult}, AliasEq, AliasTy, BoundVar, Canonical, Const, ConstValue, DebruijnIndex, DomainGoal, GenericArg, GenericArgData, Goal, GoalData, InEnvironment, InferenceVar, Interner, Lifetime, OpaqueTyId, ParamKind, ProjectionTy, ProjectionTyExt, Scalar, Substitution, TraitEnvironment, TraitRef, Ty, TyBuilder, TyExt, TyKind, VariableKind, WhereClause |
| }; |
| |
| impl<'db> InferenceContext<'db> { |
| pub(super) fn canonicalize<T>(&mut self, t: T) -> rustc_type_ir::Canonical<DbInterner<'db>, T> |
| where |
| T: rustc_type_ir::TypeFoldable<DbInterner<'db>>, |
| { |
| self.table.canonicalize(t) |
| } |
| |
| pub(super) fn clauses_for_self_ty( |
| &mut self, |
| self_ty: InferenceVar, |
| ) -> SmallVec<[WhereClause; 4]> { |
| self.table.resolve_obligations_as_possible(); |
| |
| let root = InferenceVar::from_vid(self.table.infer_ctxt.root_var(self_ty.to_vid())); |
| let pending_obligations = mem::take(&mut self.table.pending_obligations); |
| let obligations = pending_obligations |
| .iter() |
| .filter_map(|obligation| match obligation.goal.data(Interner) { |
| GoalData::DomainGoal(DomainGoal::Holds(clause)) => { |
| let ty = match clause { |
| WhereClause::AliasEq(AliasEq { |
| alias: AliasTy::Projection(projection), |
| .. |
| }) => projection.self_type_parameter(self.db), |
| WhereClause::Implemented(trait_ref) => { |
| trait_ref.self_type_parameter(Interner) |
| } |
| WhereClause::TypeOutlives(to) => to.ty.clone(), |
| _ => return None, |
| }; |
| let ty = self.resolve_ty_shallow(&ty); |
| if matches!(ty.kind(Interner), TyKind::InferenceVar(iv, TyVariableKind::General) if *iv == root) { |
| Some(clause.clone()) |
| } else { |
| None |
| } |
| } |
| _ => None, |
| }) |
| .collect(); |
| self.table.pending_obligations = pending_obligations; |
| |
| obligations |
| } |
| } |
| |
| #[derive(Debug, Clone)] |
| pub(crate) struct Canonicalized<T> |
| where |
| T: HasInterner<Interner = Interner>, |
| { |
| pub(crate) value: Canonical<T>, |
| free_vars: Vec<GenericArg>, |
| } |
| |
| impl<T: HasInterner<Interner = Interner>> Canonicalized<T> { |
| pub(crate) fn apply_solution( |
| &self, |
| ctx: &mut InferenceTable<'_>, |
| solution: Canonical<Substitution>, |
| ) { |
| // the solution may contain new variables, which we need to convert to new inference vars |
| let new_vars = Substitution::from_iter( |
| Interner, |
| solution.binders.iter(Interner).map(|k| match &k.kind { |
| VariableKind::Ty(TyVariableKind::General) => ctx.new_type_var().cast(Interner), |
| VariableKind::Ty(TyVariableKind::Integer) => ctx.new_integer_var().cast(Interner), |
| VariableKind::Ty(TyVariableKind::Float) => ctx.new_float_var().cast(Interner), |
| // Chalk can sometimes return new lifetime variables. We just replace them by errors |
| // for now. |
| VariableKind::Lifetime => ctx.new_lifetime_var().cast(Interner), |
| VariableKind::Const(ty) => ctx.new_const_var(ty.clone()).cast(Interner), |
| }), |
| ); |
| for (i, v) in solution.value.iter(Interner).enumerate() { |
| let var = &self.free_vars[i]; |
| if let Some(ty) = v.ty(Interner) { |
| // eagerly replace projections in the type; we may be getting types |
| // e.g. from where clauses where this hasn't happened yet |
| let ty = ctx.normalize_associated_types_in(new_vars.apply(ty.clone(), Interner)); |
| tracing::debug!("unifying {:?} {:?}", var, ty); |
| ctx.unify(var.assert_ty_ref(Interner), &ty); |
| } else { |
| let v = new_vars.apply(v.clone(), Interner); |
| tracing::debug!("try_unifying {:?} {:?}", var, v); |
| let _ = ctx.try_unify(var, &v); |
| } |
| } |
| } |
| } |
| |
| /// Check if types unify. |
| /// |
| /// Note that we consider placeholder types to unify with everything. |
| /// This means that there may be some unresolved goals that actually set bounds for the placeholder |
| /// type for the types to unify. For example `Option<T>` and `Option<U>` unify although there is |
| /// unresolved goal `T = U`. |
| pub fn could_unify( |
| db: &dyn HirDatabase, |
| env: Arc<TraitEnvironment>, |
| tys: &Canonical<(Ty, Ty)>, |
| ) -> bool { |
| unify(db, env, tys).is_some() |
| } |
| |
| /// Check if types unify eagerly making sure there are no unresolved goals. |
| /// |
| /// This means that placeholder types are not considered to unify if there are any bounds set on |
| /// them. For example `Option<T>` and `Option<U>` do not unify as we cannot show that `T = U` |
| pub fn could_unify_deeply( |
| db: &dyn HirDatabase, |
| env: Arc<TraitEnvironment>, |
| tys: &Canonical<(Ty, Ty)>, |
| ) -> bool { |
| let mut table = InferenceTable::new(db, env); |
| let vars = make_substitutions(tys, &mut table); |
| let ty1_with_vars = vars.apply(tys.value.0.clone(), Interner); |
| let ty2_with_vars = vars.apply(tys.value.1.clone(), Interner); |
| let ty1_with_vars = table.normalize_associated_types_in(ty1_with_vars); |
| let ty2_with_vars = table.normalize_associated_types_in(ty2_with_vars); |
| table.resolve_obligations_as_possible(); |
| table.propagate_diverging_flag(); |
| let ty1_with_vars = table.resolve_completely(ty1_with_vars); |
| let ty2_with_vars = table.resolve_completely(ty2_with_vars); |
| table.unify_deeply(&ty1_with_vars, &ty2_with_vars) |
| } |
| |
| pub(crate) fn unify( |
| db: &dyn HirDatabase, |
| env: Arc<TraitEnvironment>, |
| tys: &Canonical<(Ty, Ty)>, |
| ) -> Option<Substitution> { |
| let mut table = InferenceTable::new(db, env); |
| let vars = make_substitutions(tys, &mut table); |
| let ty1_with_vars = vars.apply(tys.value.0.clone(), Interner); |
| let ty2_with_vars = vars.apply(tys.value.1.clone(), Interner); |
| if !table.unify(&ty1_with_vars, &ty2_with_vars) { |
| return None; |
| } |
| // default any type vars that weren't unified back to their original bound vars |
| // (kind of hacky) |
| let find_var = |iv| { |
| vars.iter(Interner).position(|v| match v.data(Interner) { |
| GenericArgData::Ty(ty) => ty.inference_var(Interner), |
| GenericArgData::Lifetime(lt) => lt.inference_var(Interner), |
| GenericArgData::Const(c) => c.inference_var(Interner), |
| } == Some(iv)) |
| }; |
| let fallback = |iv, kind, default, binder| match kind { |
| chalk_ir::VariableKind::Ty(_ty_kind) => find_var(iv) |
| .map_or(default, |i| BoundVar::new(binder, i).to_ty(Interner).cast(Interner)), |
| chalk_ir::VariableKind::Lifetime => find_var(iv) |
| .map_or(default, |i| BoundVar::new(binder, i).to_lifetime(Interner).cast(Interner)), |
| chalk_ir::VariableKind::Const(ty) => find_var(iv) |
| .map_or(default, |i| BoundVar::new(binder, i).to_const(Interner, ty).cast(Interner)), |
| }; |
| Some(Substitution::from_iter( |
| Interner, |
| vars.iter(Interner).map(|v| table.resolve_with_fallback(v.clone(), &fallback)), |
| )) |
| } |
| |
| fn make_substitutions( |
| tys: &chalk_ir::Canonical<(chalk_ir::Ty<Interner>, chalk_ir::Ty<Interner>)>, |
| table: &mut InferenceTable<'_>, |
| ) -> chalk_ir::Substitution<Interner> { |
| Substitution::from_iter( |
| Interner, |
| tys.binders.iter(Interner).map(|it| match &it.kind { |
| chalk_ir::VariableKind::Ty(_) => table.new_type_var().cast(Interner), |
| // FIXME: maybe wrong? |
| chalk_ir::VariableKind::Lifetime => table.new_type_var().cast(Interner), |
| chalk_ir::VariableKind::Const(ty) => table.new_const_var(ty.clone()).cast(Interner), |
| }), |
| ) |
| } |
| |
| bitflags::bitflags! { |
| #[derive(Default, Clone, Copy)] |
| pub(crate) struct TypeVariableFlags: u8 { |
| const DIVERGING = 1 << 0; |
| const INTEGER = 1 << 1; |
| const FLOAT = 1 << 2; |
| } |
| } |
| |
| type ChalkInferenceTable = chalk_solve::infer::InferenceTable<Interner>; |
| |
| #[derive(Clone)] |
| pub(crate) struct InferenceTable<'a> { |
| pub(crate) db: &'a dyn HirDatabase, |
| pub(crate) interner: DbInterner<'a>, |
| pub(crate) trait_env: Arc<TraitEnvironment>, |
| pub(crate) tait_coercion_table: Option<FxHashMap<OpaqueTyId, Ty>>, |
| infer_ctxt: InferCtxt<'a>, |
| diverging_tys: FxHashSet<Ty>, |
| pending_obligations: Vec<InEnvironment<Goal>>, |
| } |
| |
| pub(crate) struct InferenceTableSnapshot { |
| ctxt_snapshot: CombinedSnapshot, |
| diverging_tys: FxHashSet<Ty>, |
| pending_obligations: Vec<InEnvironment<Goal>>, |
| } |
| |
| impl<'a> InferenceTable<'a> { |
| pub(crate) fn new(db: &'a dyn HirDatabase, trait_env: Arc<TraitEnvironment>) -> Self { |
| let interner = DbInterner::new_with(db, Some(trait_env.krate), trait_env.block); |
| InferenceTable { |
| db, |
| interner, |
| trait_env, |
| tait_coercion_table: None, |
| infer_ctxt: interner.infer_ctxt().build(rustc_type_ir::TypingMode::Analysis { defining_opaque_types_and_generators: SolverDefIds::new_from_iter(interner, []) }), |
| diverging_tys: FxHashSet::default(), |
| pending_obligations: Vec::new(), |
| } |
| } |
| |
| /// Chalk doesn't know about the `diverging` flag, so when it unifies two |
| /// type variables of which one is diverging, the chosen root might not be |
| /// diverging and we have no way of marking it as such at that time. This |
| /// function goes through all type variables and make sure their root is |
| /// marked as diverging if necessary, so that resolving them gives the right |
| /// result. |
| pub(super) fn propagate_diverging_flag(&mut self) { |
| let mut new_tys = FxHashSet::default(); |
| for ty in self.diverging_tys.iter() { |
| match ty.kind(Interner) { |
| TyKind::InferenceVar(var, kind) => { |
| match kind { |
| TyVariableKind::General => { |
| let root = InferenceVar::from(self.infer_ctxt.root_var(TyVid::from_u32(var.index())).as_u32()); |
| if root.index() != var.index() { |
| new_tys.insert(TyKind::InferenceVar(root, *kind).intern(Interner)); |
| } |
| } |
| TyVariableKind::Integer => { |
| let root = InferenceVar::from(self.infer_ctxt.inner.borrow_mut().int_unification_table().find(IntVid::from_usize(var.index() as usize)).as_u32()); |
| if root.index() != var.index() { |
| new_tys.insert(TyKind::InferenceVar(root, *kind).intern(Interner)); |
| } |
| } |
| TyVariableKind::Float => { |
| let root = InferenceVar::from(self.infer_ctxt.inner.borrow_mut().float_unification_table().find(FloatVid::from_usize(var.index() as usize)).as_u32()); |
| if root.index() != var.index() { |
| new_tys.insert(TyKind::InferenceVar(root, *kind).intern(Interner)); |
| } |
| } |
| } |
| } |
| _ => {} |
| } |
| } |
| self.diverging_tys.extend(new_tys.into_iter()); |
| } |
| |
| pub(super) fn set_diverging(&mut self, iv: InferenceVar, kind: TyVariableKind, diverging: bool) { |
| self.diverging_tys.insert(TyKind::InferenceVar(iv, kind).intern(Interner)); |
| } |
| |
| fn fallback_value(&self, iv: InferenceVar, kind: TyVariableKind) -> Ty { |
| let is_diverging = self.diverging_tys.contains(&TyKind::InferenceVar(iv, kind).intern(Interner)); |
| if is_diverging { |
| return TyKind::Never.intern(Interner); |
| } |
| match kind { |
| TyVariableKind::General => TyKind::Error, |
| TyVariableKind::Integer => TyKind::Scalar(Scalar::Int(IntTy::I32)), |
| TyVariableKind::Float => TyKind::Scalar(Scalar::Float(FloatTy::F64)), |
| } |
| .intern(Interner) |
| } |
| |
| pub(crate) fn canonicalize_with_free_vars<T>(&mut self, t: ParamEnvAnd<'a, T>) -> (rustc_type_ir::Canonical<DbInterner<'a>, ParamEnvAnd<'a, T>>, OriginalQueryValues<'a>) |
| where |
| T: rustc_type_ir::TypeFoldable<DbInterner<'a>>, |
| { |
| // try to resolve obligations before canonicalizing, since this might |
| // result in new knowledge about variables |
| self.resolve_obligations_as_possible(); |
| |
| let mut orig_values = OriginalQueryValues::default(); |
| let result = self.infer_ctxt.canonicalize_query(t, &mut orig_values); |
| (result.canonical, orig_values) |
| } |
| |
| pub(crate) fn canonicalize<T>(&mut self, t: T) -> rustc_type_ir::Canonical<DbInterner<'a>, T> |
| where |
| T: rustc_type_ir::TypeFoldable<DbInterner<'a>>, |
| { |
| // try to resolve obligations before canonicalizing, since this might |
| // result in new knowledge about variables |
| self.resolve_obligations_as_possible(); |
| self.infer_ctxt.canonicalize_response(t) |
| } |
| |
| /// Recurses through the given type, normalizing associated types mentioned |
| /// in it by replacing them by type variables and registering obligations to |
| /// resolve later. This should be done once for every type we get from some |
| /// type annotation (e.g. from a let type annotation, field type or function |
| /// call). `make_ty` handles this already, but e.g. for field types we need |
| /// to do it as well. |
| #[tracing::instrument(skip(self), ret)] |
| pub(crate) fn normalize_associated_types_in<T>(&mut self, ty: T) -> T |
| where |
| T: HasInterner<Interner = Interner> + TypeFoldable<Interner>, |
| { |
| fold_tys_and_consts( |
| ty, |
| |e, _| match e { |
| Either::Left(ty) => { |
| let ty = self.resolve_ty_shallow(&ty); |
| tracing::debug!(?ty); |
| Either::Left(match ty.kind(Interner) { |
| TyKind::Alias(AliasTy::Projection(proj_ty)) => { |
| let ty = self.normalize_projection_ty(proj_ty.clone()); |
| self.resolve_ty_shallow(&ty) |
| } |
| TyKind::AssociatedType(id, subst) => { |
| return Either::Left(self.resolve_ty_shallow(&ty)); |
| if ty.data(Interner).flags.intersects( |
| chalk_ir::TypeFlags::HAS_TY_INFER |
| | chalk_ir::TypeFlags::HAS_CT_INFER, |
| ) { |
| return Either::Left(ty); |
| } |
| let var = self.new_type_var(); |
| let proj_ty = chalk_ir::ProjectionTy { |
| associated_ty_id: *id, |
| substitution: subst.clone(), |
| }; |
| let normalize = chalk_ir::Normalize { |
| alias: AliasTy::Projection(proj_ty), |
| ty: var.clone(), |
| }; |
| let goal = chalk_ir::Goal::new( |
| Interner, |
| chalk_ir::GoalData::DomainGoal(chalk_ir::DomainGoal::Normalize( |
| normalize, |
| )), |
| ); |
| let in_env = InEnvironment::new(&self.trait_env.env, goal); |
| let goal = in_env.to_nextsolver(self.interner); |
| let goal = ParamEnvAnd { param_env: goal.param_env, value: goal.predicate }; |
| |
| let (canonical_goal, _orig_values) = { |
| let mut orig_values = OriginalQueryValues::default(); |
| let result = self.infer_ctxt.canonicalize_query(goal, &mut orig_values); |
| (result.canonical, orig_values) |
| }; |
| let canonical_goal = rustc_type_ir::Canonical { |
| max_universe: canonical_goal.max_universe, |
| variables: canonical_goal.variables, |
| value: crate::next_solver::Goal { param_env: canonical_goal.value.param_env, predicate: canonical_goal.value.value }, |
| }; |
| let solution = next_trait_solve_canonical( |
| self.db, |
| self.trait_env.krate, |
| self.trait_env.block, |
| canonical_goal.clone(), |
| ); |
| if let NextTraitSolveResult::Certain(canonical_subst) = solution { |
| // This is not great :) But let's just assert this for now and come back to it later. |
| if canonical_subst.value.subst.len(Interner) != 1 { |
| ty |
| } else { |
| let normalized = canonical_subst.value.subst.as_slice(Interner) |
| [0] |
| .assert_ty_ref(Interner); |
| match normalized.kind(Interner) { |
| TyKind::Alias(AliasTy::Projection(proj_ty)) => { |
| if id == &proj_ty.associated_ty_id |
| && subst == &proj_ty.substitution |
| { |
| ty |
| } else { |
| normalized.clone() |
| } |
| } |
| TyKind::AssociatedType(new_id, new_subst) => { |
| if new_id == id && new_subst == subst { |
| ty |
| } else { |
| normalized.clone() |
| } |
| } |
| _ => normalized.clone(), |
| } |
| } |
| } else { |
| ty |
| } |
| } |
| _ => ty, |
| }) |
| } |
| Either::Right(c) => Either::Right(match &c.data(Interner).value { |
| chalk_ir::ConstValue::Concrete(cc) => match &cc.interned { |
| crate::ConstScalar::UnevaluatedConst(c_id, subst) => { |
| // FIXME: Ideally here we should do everything that we do with type alias, i.e. adding a variable |
| // and registering an obligation. But it needs chalk support, so we handle the most basic |
| // case (a non associated const without generic parameters) manually. |
| if subst.len(Interner) == 0 { |
| if let Ok(eval) = self.db.const_eval(*c_id, subst.clone(), None) { |
| eval |
| } else { |
| unknown_const(c.data(Interner).ty.clone()) |
| } |
| } else { |
| unknown_const(c.data(Interner).ty.clone()) |
| } |
| } |
| _ => c, |
| }, |
| _ => c, |
| }), |
| }, |
| DebruijnIndex::INNERMOST, |
| ) |
| } |
| |
| /// Works almost same as [`Self::normalize_associated_types_in`], but this also resolves shallow |
| /// the inference variables |
| pub(crate) fn eagerly_normalize_and_resolve_shallow_in<T>(&mut self, ty: T) -> T |
| where |
| T: HasInterner<Interner = Interner> + TypeFoldable<Interner>, |
| { |
| fn eagerly_resolve_ty<const N: usize>( |
| table: &mut InferenceTable<'_>, |
| ty: Ty, |
| mut tys: SmallVec<[Ty; N]>, |
| ) -> Ty { |
| if tys.contains(&ty) { |
| return ty; |
| } |
| tys.push(ty.clone()); |
| |
| match ty.kind(Interner) { |
| TyKind::Alias(AliasTy::Projection(proj_ty)) => { |
| let ty = table.normalize_projection_ty(proj_ty.clone()); |
| eagerly_resolve_ty(table, ty, tys) |
| } |
| TyKind::InferenceVar(..) => { |
| let ty = table.resolve_ty_shallow(&ty); |
| eagerly_resolve_ty(table, ty, tys) |
| } |
| _ => ty, |
| } |
| } |
| |
| fold_tys_and_consts( |
| ty, |
| |e, _| match e { |
| Either::Left(ty) => { |
| Either::Left(eagerly_resolve_ty::<8>(self, ty, SmallVec::new())) |
| } |
| Either::Right(c) => Either::Right(match &c.data(Interner).value { |
| chalk_ir::ConstValue::Concrete(cc) => match &cc.interned { |
| crate::ConstScalar::UnevaluatedConst(c_id, subst) => { |
| // FIXME: same as `normalize_associated_types_in` |
| if subst.len(Interner) == 0 { |
| if let Ok(eval) = self.db.const_eval(*c_id, subst.clone(), None) { |
| eval |
| } else { |
| unknown_const(c.data(Interner).ty.clone()) |
| } |
| } else { |
| unknown_const(c.data(Interner).ty.clone()) |
| } |
| } |
| _ => c, |
| }, |
| _ => c, |
| }), |
| }, |
| DebruijnIndex::INNERMOST, |
| ) |
| } |
| |
| pub(crate) fn normalize_projection_ty(&mut self, proj_ty: ProjectionTy) -> Ty { |
| let var = self.new_type_var(); |
| let alias_eq = AliasEq { alias: AliasTy::Projection(proj_ty), ty: var.clone() }; |
| let obligation = alias_eq.cast(Interner); |
| self.register_obligation(obligation); |
| var |
| } |
| |
| fn new_var(&mut self, kind: TyVariableKind, diverging: bool) -> Ty { |
| let var = match kind { |
| TyVariableKind::General => { |
| let var = self.infer_ctxt.next_ty_vid(); |
| InferenceVar::from(var.as_u32()) |
| } |
| TyVariableKind::Integer => { |
| let var = self.infer_ctxt.next_int_vid(); |
| InferenceVar::from(var.as_u32()) |
| } |
| TyVariableKind::Float => { |
| let var = self.infer_ctxt.next_float_vid(); |
| InferenceVar::from(var.as_u32()) |
| } |
| }; |
| |
| let ty = var.to_ty(Interner, kind); |
| if diverging { |
| self.diverging_tys.insert(ty.clone()); |
| } |
| ty |
| } |
| |
| pub(crate) fn new_type_var(&mut self) -> Ty { |
| self.new_var(TyVariableKind::General, false) |
| } |
| |
| pub(crate) fn new_integer_var(&mut self) -> Ty { |
| self.new_var(TyVariableKind::Integer, false) |
| } |
| |
| pub(crate) fn new_float_var(&mut self) -> Ty { |
| self.new_var(TyVariableKind::Float, false) |
| } |
| |
| pub(crate) fn new_maybe_never_var(&mut self) -> Ty { |
| self.new_var(TyVariableKind::General, true) |
| } |
| |
| pub(crate) fn new_const_var(&mut self, ty: Ty) -> Const { |
| let var = self.infer_ctxt.next_const_vid(); |
| let var = InferenceVar::from(var.as_u32()); |
| var.to_const(Interner, ty) |
| } |
| |
| pub(crate) fn new_lifetime_var(&mut self) -> Lifetime { |
| let var = self.infer_ctxt.next_region_vid(); |
| let var = InferenceVar::from(var.as_u32()); |
| var.to_lifetime(Interner) |
| } |
| |
| pub(crate) fn resolve_with_fallback<T>( |
| &mut self, |
| t: T, |
| fallback: &dyn Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg, |
| ) -> T |
| where |
| T: HasInterner<Interner = Interner> + TypeFoldable<Interner>, |
| { |
| self.resolve_with_fallback_inner(t, &fallback) |
| } |
| |
| pub(crate) fn fresh_subst(&mut self, binders: &[CanonicalVarKind<Interner>]) -> Substitution { |
| Substitution::from_iter( |
| Interner, |
| binders.iter().map(|kind| match &kind.kind { |
| chalk_ir::VariableKind::Ty(ty_variable_kind) => self.new_var(*ty_variable_kind, false).cast(Interner), |
| chalk_ir::VariableKind::Lifetime => self.new_lifetime_var().cast(Interner), |
| chalk_ir::VariableKind::Const(ty) => self.new_const_var(ty.clone()).cast(Interner), |
| }), |
| ) |
| } |
| |
| pub(crate) fn instantiate_canonical<T>(&mut self, canonical: Canonical<T>) -> T |
| where |
| T: HasInterner<Interner = Interner> + TypeFoldable<Interner> + std::fmt::Debug, |
| { |
| let subst = self.fresh_subst(canonical.binders.as_slice(Interner)); |
| subst.apply(canonical.value, Interner) |
| } |
| |
| pub(crate) fn instantiate_canonical_ns<T>(&mut self, canonical: rustc_type_ir::Canonical<DbInterner<'a>, T>) -> T |
| where |
| T: rustc_type_ir::TypeFoldable<DbInterner<'a>>, |
| { |
| self.infer_ctxt.instantiate_canonical(&canonical).0 |
| } |
| |
| fn resolve_with_fallback_inner<T>( |
| &mut self, |
| t: T, |
| fallback: &dyn Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg, |
| ) -> T |
| where |
| T: HasInterner<Interner = Interner> + TypeFoldable<Interner>, |
| { |
| let mut var_stack = &mut vec![]; |
| t.fold_with( |
| &mut resolve::Resolver { table: self, var_stack, fallback }, |
| DebruijnIndex::INNERMOST, |
| ) |
| } |
| |
| pub(crate) fn resolve_completely<T>(&mut self, t: T) -> T |
| where |
| T: HasInterner<Interner = Interner> + TypeFoldable<Interner>, |
| { |
| let t = self.resolve_with_fallback(t, &|_, _, d, _| d); |
| let t = self.normalize_associated_types_in(t); |
| // Resolve again, because maybe normalization inserted infer vars. |
| self.resolve_with_fallback(t, &|_, _, d, _| d) |
| } |
| |
| /// Apply a fallback to unresolved scalar types. Integer type variables and float type |
| /// variables are replaced with i32 and f64, respectively. |
| /// |
| /// This method is only intended to be called just before returning inference results (i.e. in |
| /// `InferenceContext::resolve_all()`). |
| /// |
| /// FIXME: This method currently doesn't apply fallback to unconstrained general type variables |
| /// whereas rustc replaces them with `()` or `!`. |
| pub(super) fn fallback_if_possible(&mut self) { |
| let int_fallback = TyKind::Scalar(Scalar::Int(IntTy::I32)).intern(Interner); |
| let float_fallback = TyKind::Scalar(Scalar::Float(FloatTy::F64)).intern(Interner); |
| |
| let int_vars = self.infer_ctxt.inner.borrow_mut().int_unification_table().len(); |
| for v in 0..int_vars { |
| let var = InferenceVar::from(v as u32).to_ty(Interner, TyVariableKind::Integer); |
| let maybe_resolved = self.resolve_ty_shallow(&var); |
| if let TyKind::InferenceVar(_, kind) = maybe_resolved.kind(Interner) { |
| // I don't think we can ever unify these vars with float vars, but keep this here for now |
| let fallback = match kind { |
| TyVariableKind::Integer => &int_fallback, |
| TyVariableKind::Float => &float_fallback, |
| TyVariableKind::General => unreachable!(), |
| }; |
| self.unify(&var, fallback); |
| } |
| } |
| let float_vars = self.infer_ctxt.inner.borrow_mut().float_unification_table().len(); |
| for v in 0..float_vars { |
| let var = InferenceVar::from(v as u32).to_ty(Interner, TyVariableKind::Integer); |
| let maybe_resolved = self.resolve_ty_shallow(&var); |
| if let TyKind::InferenceVar(_, kind) = maybe_resolved.kind(Interner) { |
| // I don't think we can ever unify these vars with float vars, but keep this here for now |
| let fallback = match kind { |
| TyVariableKind::Integer => &int_fallback, |
| TyVariableKind::Float => &float_fallback, |
| TyVariableKind::General => unreachable!(), |
| }; |
| self.unify(&var, fallback); |
| } |
| } |
| } |
| |
| /// Unify two relatable values (e.g. `Ty`) and register new trait goals that arise from that. |
| pub(crate) fn unify<T: ChalkToNextSolver<'a, U>, U: Relate<DbInterner<'a>>>(&mut self, ty1: &T, ty2: &T) -> bool { |
| let result = match self.try_unify(ty1, ty2) { |
| Ok(r) => r, |
| Err(_) => return false, |
| }; |
| self.register_infer_ok(result); |
| true |
| } |
| |
| /// Unify two relatable values (e.g. `Ty`) and check whether trait goals which arise from that could be fulfilled |
| pub(crate) fn unify_deeply<T: ChalkToNextSolver<'a, U>, U: Relate<DbInterner<'a>>>(&mut self, ty1: &T, ty2: &T) -> bool { |
| let result = match self.try_unify(ty1, ty2) { |
| Ok(r) => r, |
| Err(_) => return false, |
| }; |
| result.goals.iter().all(|goal| { |
| let goal = goal.to_nextsolver(self.interner); |
| match next_trait_solve_in_ctxt(&self.infer_ctxt, goal) { |
| Ok((_, Certainty::Yes)) => true, |
| _ => false, |
| } |
| }) |
| } |
| |
| /// Unify two relatable values (e.g. `Ty`) and return new trait goals arising from it, so the |
| /// caller needs to deal with them. |
| pub(crate) fn try_unify<T: ChalkToNextSolver<'a, U>, U: Relate<DbInterner<'a>>>( |
| &mut self, |
| t1: &T, |
| t2: &T, |
| ) -> InferResult<()> { |
| let param_env = self.trait_env.env.to_nextsolver(self.interner); |
| let lhs = t1.to_nextsolver(self.interner); |
| let rhs = t2.to_nextsolver(self.interner); |
| let variance = rustc_type_ir::Variance::Invariant; |
| let span = crate::next_solver::Span::dummy(); |
| match self.infer_ctxt.relate(param_env, lhs, variance, rhs, span) { |
| Ok(res) => { |
| let goals = res.into_iter().map(|g| ChalkToNextSolver::from_nextsolver(g, self.interner)).collect(); |
| Ok(InferOk { goals, value: () }) |
| } |
| Err(_) => { |
| Err(TypeError) |
| } |
| } |
| } |
| |
| /// If `ty` is a type variable with known type, returns that type; |
| /// otherwise, return ty. |
| #[tracing::instrument(skip(self))] |
| pub(crate) fn resolve_ty_shallow(&mut self, ty: &Ty) -> Ty { |
| if !ty.data(Interner).flags.intersects(chalk_ir::TypeFlags::HAS_FREE_LOCAL_NAMES) { |
| return ty.clone(); |
| } |
| self.resolve_obligations_as_possible(); |
| ChalkToNextSolver::from_nextsolver(self.infer_ctxt.resolve_vars_if_possible(ty.to_nextsolver(self.interner)), self.interner) |
| } |
| |
| pub(crate) fn snapshot(&mut self) -> InferenceTableSnapshot { |
| let ctxt_snapshot = self.infer_ctxt.start_snapshot(); |
| let diverging_tys = self.diverging_tys.clone(); |
| let pending_obligations = self.pending_obligations.clone(); |
| InferenceTableSnapshot {ctxt_snapshot, pending_obligations, diverging_tys } |
| } |
| |
| #[tracing::instrument(skip_all)] |
| pub(crate) fn rollback_to(&mut self, snapshot: InferenceTableSnapshot) { |
| self.infer_ctxt.rollback_to(snapshot.ctxt_snapshot); |
| self.diverging_tys = snapshot.diverging_tys; |
| self.pending_obligations = snapshot.pending_obligations; |
| } |
| |
| #[tracing::instrument(skip_all)] |
| pub(crate) fn run_in_snapshot<T>(&mut self, f: impl FnOnce(&mut InferenceTable<'_>) -> T) -> T { |
| let snapshot = self.snapshot(); |
| let result = f(self); |
| self.rollback_to(snapshot); |
| result |
| } |
| |
| pub(crate) fn commit_if_ok<T, E>(&mut self, f: impl FnOnce(&mut InferenceTable<'_>) -> Result<T, E>) -> Result<T, E> { |
| let snapshot = self.snapshot(); |
| let result = f(self); |
| match result { |
| Ok(_) => {} |
| Err(_) => { |
| self.rollback_to(snapshot); |
| } |
| } |
| result |
| } |
| |
| /// Checks an obligation without registering it. Useful mostly to check |
| /// whether a trait *might* be implemented before deciding to 'lock in' the |
| /// choice (during e.g. method resolution or deref). |
| #[tracing::instrument(level = "debug", skip(self))] |
| pub(crate) fn try_obligation(&mut self, goal: Goal) -> NextTraitSolveResult { |
| let in_env = InEnvironment::new(&self.trait_env.env, goal); |
| let canonicalized = self.canonicalize(in_env.to_nextsolver(self.interner)); |
| |
| next_trait_solve_canonical(self.db, self.trait_env.krate, self.trait_env.block, canonicalized) |
| } |
| |
| #[tracing::instrument(level = "debug", skip(self))] |
| pub(crate) fn solve_obligation(&mut self, goal: Goal) -> Result<Certainty, NoSolution> { |
| let goal = InEnvironment::new(&self.trait_env.env, goal); |
| let Some(goal) = self.unify_opaque_instead_of_solve(goal) else { |
| return Ok(Certainty::Yes); |
| }; |
| |
| let goal = goal.to_nextsolver(self.interner); |
| let result = next_trait_solve_in_ctxt(&self.infer_ctxt, goal); |
| result.map(|m| m.1) |
| } |
| |
| pub(crate) fn register_obligation(&mut self, goal: Goal) { |
| let in_env = InEnvironment::new(&self.trait_env.env, goal); |
| self.register_obligation_in_env(in_env) |
| } |
| |
| // If this goal is an `AliasEq` for an opaque type, just unify instead of trying to solve (since the next-solver is lazy) |
| fn unify_opaque_instead_of_solve(&mut self, goal: InEnvironment<Goal>) -> Option<InEnvironment<Goal>> { |
| match goal.goal.data(Interner) { |
| chalk_ir::GoalData::DomainGoal(chalk_ir::DomainGoal::Holds( |
| chalk_ir::WhereClause::AliasEq(chalk_ir::AliasEq { alias, ty }), |
| )) => { |
| if ty.inference_var(Interner).is_some() { |
| match alias { |
| chalk_ir::AliasTy::Opaque(opaque) => { |
| if self.unify( |
| &chalk_ir::TyKind::OpaqueType( |
| opaque.opaque_ty_id, |
| opaque.substitution.clone(), |
| ) |
| .intern(Interner), |
| ty, |
| ) { |
| return None; |
| } |
| } |
| _ => {} |
| } |
| } |
| } |
| _ => {} |
| } |
| Some(goal) |
| } |
| |
| #[tracing::instrument(level = "debug", skip(self))] |
| fn register_obligation_in_env(&mut self, goal: InEnvironment<Goal>) { |
| let Some(goal) = self.unify_opaque_instead_of_solve(goal) else { return }; |
| let result = next_trait_solve_in_ctxt(&self.infer_ctxt, goal.to_nextsolver(self.interner)); |
| tracing::debug!(?result); |
| match result { |
| Ok((_, Certainty::Yes)) => {} |
| Err(rustc_type_ir::solve::NoSolution) => {} |
| Ok((_, Certainty::Maybe(_))) => { |
| self.pending_obligations.push(goal); |
| } |
| } |
| } |
| |
| pub(crate) fn register_infer_ok<T>(&mut self, infer_ok: InferOk<T>) { |
| infer_ok.goals.into_iter().for_each(|goal| self.register_obligation_in_env(goal)); |
| } |
| |
| pub(crate) fn resolve_obligations_as_possible(&mut self) { |
| let _span = tracing::info_span!("resolve_obligations_as_possible").entered(); |
| let mut changed = true; |
| while mem::take(&mut changed) { |
| let mut obligations = mem::take(&mut self.pending_obligations); |
| |
| for goal in obligations.drain(..) { |
| tracing::debug!(obligation = ?goal); |
| |
| let Some(goal) = self.unify_opaque_instead_of_solve(goal) else { |
| changed = true; |
| continue; |
| }; |
| |
| let result = next_trait_solve_in_ctxt(&self.infer_ctxt, goal.to_nextsolver(self.interner)); |
| let (has_changed, certainty) = match result { |
| Ok(result) => result, |
| Err(_) => { |
| continue; |
| } |
| }; |
| |
| if matches!(has_changed, HasChanged::Yes) { |
| changed = true; |
| } |
| |
| match certainty { |
| Certainty::Yes => {} |
| Certainty::Maybe(_) => self.pending_obligations.push(goal), |
| } |
| } |
| } |
| } |
| |
| pub(crate) fn fudge_inference<T: TypeFoldable<Interner>>( |
| &mut self, |
| f: impl FnOnce(&mut Self) -> T, |
| ) -> T { |
| use chalk_ir::fold::TypeFolder; |
| |
| #[derive(chalk_derive::FallibleTypeFolder)] |
| #[has_interner(Interner)] |
| struct VarFudger<'a, 'b> { |
| table: &'a mut InferenceTable<'b>, |
| highest_known_var: InferenceVar, |
| } |
| impl TypeFolder<Interner> for VarFudger<'_, '_> { |
| fn as_dyn(&mut self) -> &mut dyn TypeFolder<Interner> { |
| self |
| } |
| |
| fn interner(&self) -> Interner { |
| Interner |
| } |
| |
| fn fold_inference_ty( |
| &mut self, |
| var: chalk_ir::InferenceVar, |
| kind: TyVariableKind, |
| _outer_binder: chalk_ir::DebruijnIndex, |
| ) -> chalk_ir::Ty<Interner> { |
| if var < self.highest_known_var { |
| var.to_ty(Interner, kind) |
| } else { |
| self.table.new_type_var() |
| } |
| } |
| |
| fn fold_inference_lifetime( |
| &mut self, |
| var: chalk_ir::InferenceVar, |
| _outer_binder: chalk_ir::DebruijnIndex, |
| ) -> chalk_ir::Lifetime<Interner> { |
| if var < self.highest_known_var { |
| var.to_lifetime(Interner) |
| } else { |
| self.table.new_lifetime_var() |
| } |
| } |
| |
| fn fold_inference_const( |
| &mut self, |
| ty: chalk_ir::Ty<Interner>, |
| var: chalk_ir::InferenceVar, |
| _outer_binder: chalk_ir::DebruijnIndex, |
| ) -> chalk_ir::Const<Interner> { |
| if var < self.highest_known_var { |
| var.to_const(Interner, ty) |
| } else { |
| self.table.new_const_var(ty) |
| } |
| } |
| } |
| |
| let snapshot = self.snapshot(); |
| let highest_known_var = self.new_type_var().inference_var(Interner).expect("inference_var"); |
| let result = f(self); |
| self.rollback_to(snapshot); |
| result |
| .fold_with(&mut VarFudger { table: self, highest_known_var }, DebruijnIndex::INNERMOST) |
| } |
| |
| #[tracing::instrument(level = "debug", skip(self))] |
| fn try_resolve_obligation( |
| &mut self, |
| canonicalized: &Canonicalized<InEnvironment<Goal>>, |
| ) -> NextTraitSolveResult { |
| let solution = next_trait_solve( |
| self.db, |
| self.trait_env.krate, |
| self.trait_env.block, |
| canonicalized.value.clone(), |
| ); |
| |
| tracing::debug!(?solution, ?canonicalized); |
| match &solution { |
| NextTraitSolveResult::Certain(v) => { |
| canonicalized.apply_solution( |
| self, |
| Canonical { |
| binders: v.binders.clone(), |
| // FIXME handle constraints |
| value: v.value.subst.clone(), |
| }, |
| ); |
| } |
| // ...so, should think about how to get some actually get some guidance here |
| NextTraitSolveResult::Uncertain(v) => { |
| canonicalized.apply_solution(self, v.clone()); |
| } |
| NextTraitSolveResult::NoSolution => {} |
| } |
| |
| solution |
| } |
| |
| pub(crate) fn callable_sig( |
| &mut self, |
| ty: &Ty, |
| num_args: usize, |
| ) -> Option<(Option<FnTrait>, Vec<Ty>, Ty)> { |
| match ty.callable_sig(self.db) { |
| Some(sig) => Some((None, sig.params().to_vec(), sig.ret().clone())), |
| None => { |
| let (f, args_ty, return_ty) = self.callable_sig_from_fn_trait(ty, num_args)?; |
| Some((Some(f), args_ty, return_ty)) |
| } |
| } |
| } |
| |
| fn callable_sig_from_fn_trait( |
| &mut self, |
| ty: &Ty, |
| num_args: usize, |
| ) -> Option<(FnTrait, Vec<Ty>, Ty)> { |
| for (fn_trait_name, output_assoc_name, subtraits) in [ |
| (FnTrait::FnOnce, sym::Output, &[FnTrait::Fn, FnTrait::FnMut][..]), |
| (FnTrait::AsyncFnMut, sym::CallRefFuture, &[FnTrait::AsyncFn]), |
| (FnTrait::AsyncFnOnce, sym::CallOnceFuture, &[]), |
| ] { |
| let krate = self.trait_env.krate; |
| let fn_trait = fn_trait_name.get_id(self.db, krate)?; |
| let trait_data = fn_trait.trait_items(self.db); |
| let output_assoc_type = |
| trait_data.associated_type_by_name(&Name::new_symbol_root(output_assoc_name))?; |
| |
| let mut arg_tys = Vec::with_capacity(num_args); |
| let arg_ty = TyBuilder::tuple(num_args) |
| .fill(|it| { |
| let arg = match it { |
| ParamKind::Type => self.new_type_var(), |
| ParamKind::Lifetime => unreachable!("Tuple with lifetime parameter"), |
| ParamKind::Const(_) => unreachable!("Tuple with const parameter"), |
| }; |
| arg_tys.push(arg.clone()); |
| arg.cast(Interner) |
| }) |
| .build(); |
| |
| let b = TyBuilder::trait_ref(self.db, fn_trait); |
| if b.remaining() != 2 { |
| return None; |
| } |
| let mut trait_ref = b.push(ty.clone()).push(arg_ty).build(); |
| |
| let projection = TyBuilder::assoc_type_projection( |
| self.db, |
| output_assoc_type, |
| Some(trait_ref.substitution.clone()), |
| ) |
| .fill_with_unknown() |
| .build(); |
| |
| let goal: Goal = trait_ref.clone().cast(Interner); |
| if !self.try_obligation(goal.clone()).no_solution() { |
| self.register_obligation(goal); |
| let return_ty = self.normalize_projection_ty(projection); |
| for &fn_x in subtraits { |
| let fn_x_trait = fn_x.get_id(self.db, krate)?; |
| trait_ref.trait_id = to_chalk_trait_id(fn_x_trait); |
| let goal = trait_ref.clone().cast(Interner); |
| if !self.try_obligation(goal).no_solution() { |
| return Some((fn_x, arg_tys, return_ty)); |
| } |
| } |
| return Some((fn_trait_name, arg_tys, return_ty)); |
| } |
| } |
| None |
| } |
| |
| pub(super) fn insert_type_vars<T>(&mut self, ty: T) -> T |
| where |
| T: HasInterner<Interner = Interner> + TypeFoldable<Interner>, |
| { |
| fold_generic_args( |
| ty, |
| |arg, _| match arg { |
| GenericArgData::Ty(ty) => GenericArgData::Ty(self.insert_type_vars_shallow(ty)), |
| // FIXME: insert lifetime vars once LifetimeData::InferenceVar |
| // and specific error variant for lifetimes start being constructed |
| GenericArgData::Lifetime(lt) => GenericArgData::Lifetime(lt), |
| GenericArgData::Const(c) => { |
| GenericArgData::Const(self.insert_const_vars_shallow(c)) |
| } |
| }, |
| DebruijnIndex::INNERMOST, |
| ) |
| } |
| |
| /// Replaces `Ty::Error` by a new type var, so we can maybe still infer it. |
| pub(super) fn insert_type_vars_shallow(&mut self, ty: Ty) -> Ty { |
| match ty.kind(Interner) { |
| TyKind::Error => self.new_type_var(), |
| TyKind::InferenceVar(..) => { |
| let ty_resolved = self.resolve_ty_shallow(&ty); |
| if ty_resolved.is_unknown() { self.new_type_var() } else { ty } |
| } |
| _ => ty, |
| } |
| } |
| |
| /// Replaces ConstScalar::Unknown by a new type var, so we can maybe still infer it. |
| pub(super) fn insert_const_vars_shallow(&mut self, c: Const) -> Const { |
| let data = c.data(Interner); |
| match &data.value { |
| ConstValue::Concrete(cc) => match &cc.interned { |
| crate::ConstScalar::Unknown => self.new_const_var(data.ty.clone()), |
| // try to evaluate unevaluated const. Replace with new var if const eval failed. |
| crate::ConstScalar::UnevaluatedConst(id, subst) => { |
| if let Ok(eval) = self.db.const_eval(*id, subst.clone(), None) { |
| eval |
| } else { |
| self.new_const_var(data.ty.clone()) |
| } |
| } |
| _ => c, |
| }, |
| _ => c, |
| } |
| } |
| |
| /// Check if given type is `Sized` or not |
| pub(crate) fn is_sized(&mut self, ty: &Ty) -> bool { |
| fn short_circuit_trivial_tys(ty: &Ty) -> Option<bool> { |
| match ty.kind(Interner) { |
| TyKind::Scalar(..) |
| | TyKind::Ref(..) |
| | TyKind::Raw(..) |
| | TyKind::Never |
| | TyKind::FnDef(..) |
| | TyKind::Array(..) |
| | TyKind::Function(..) => Some(true), |
| TyKind::Slice(..) | TyKind::Str | TyKind::Dyn(..) => Some(false), |
| _ => None, |
| } |
| } |
| |
| let mut ty = ty.clone(); |
| ty = self.eagerly_normalize_and_resolve_shallow_in(ty); |
| if let Some(sized) = short_circuit_trivial_tys(&ty) { |
| return sized; |
| } |
| |
| { |
| let mut structs = SmallVec::<[_; 8]>::new(); |
| // Must use a loop here and not recursion because otherwise users will conduct completely |
| // artificial examples of structs that have themselves as the tail field and complain r-a crashes. |
| while let Some((AdtId::StructId(id), subst)) = ty.as_adt() { |
| let struct_data = id.fields(self.db); |
| if let Some((last_field, _)) = struct_data.fields().iter().next_back() { |
| let last_field_ty = self.db.field_types(id.into())[last_field] |
| .clone() |
| .substitute(Interner, subst); |
| if structs.contains(&ty) { |
| // A struct recursively contains itself as a tail field somewhere. |
| return true; // Don't overload the users with too many errors. |
| } |
| structs.push(ty); |
| // Structs can have DST as its last field and such cases are not handled |
| // as unsized by the chalk, so we do this manually. |
| ty = last_field_ty; |
| ty = self.eagerly_normalize_and_resolve_shallow_in(ty); |
| if let Some(sized) = short_circuit_trivial_tys(&ty) { |
| return sized; |
| } |
| } else { |
| break; |
| }; |
| } |
| } |
| |
| let Some(sized) = LangItem::Sized.resolve_trait(self.db, self.trait_env.krate) else { |
| return false; |
| }; |
| let sized_pred = WhereClause::Implemented(TraitRef { |
| trait_id: to_chalk_trait_id(sized), |
| substitution: Substitution::from1(Interner, ty), |
| }); |
| let goal = GoalData::DomainGoal(chalk_ir::DomainGoal::Holds(sized_pred)).intern(Interner); |
| self.try_obligation(goal).certain() |
| } |
| } |
| |
| impl fmt::Debug for InferenceTable<'_> { |
| fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| f.debug_struct("InferenceTable").finish() |
| } |
| } |
| |
| mod resolve { |
| use super::InferenceTable; |
| use crate::{ |
| next_solver::mapping::ChalkToNextSolver, ConcreteConst, Const, ConstData, ConstScalar, ConstValue, DebruijnIndex, GenericArg, InferenceVar, Interner, Lifetime, Ty, TyVariableKind, VariableKind |
| }; |
| use chalk_ir::{ |
| cast::Cast, |
| fold::{TypeFoldable, TypeFolder}, |
| }; |
| use rustc_type_ir::{FloatVid, IntVid, TyVid}; |
| |
| #[derive(Copy, Clone, PartialEq, Eq)] |
| pub(super) enum VarKind { |
| Ty(TyVariableKind), |
| Const, |
| } |
| |
| #[derive(chalk_derive::FallibleTypeFolder)] |
| #[has_interner(Interner)] |
| pub(super) struct Resolver< |
| 'a, |
| 'b, |
| F: Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg, |
| > { |
| pub(super) table: &'a mut InferenceTable<'b>, |
| pub(super) var_stack: &'a mut Vec<(InferenceVar, VarKind)>, |
| pub(super) fallback: F, |
| } |
| impl<F> TypeFolder<Interner> for Resolver<'_, '_, F> |
| where |
| F: Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg, |
| { |
| fn as_dyn(&mut self) -> &mut dyn TypeFolder<Interner> { |
| self |
| } |
| |
| fn interner(&self) -> Interner { |
| Interner |
| } |
| |
| fn fold_inference_ty( |
| &mut self, |
| var: InferenceVar, |
| kind: TyVariableKind, |
| outer_binder: DebruijnIndex, |
| ) -> Ty { |
| match kind { |
| TyVariableKind::General => { |
| let vid = self.table.infer_ctxt.root_var(TyVid::from(var.index())); |
| let var = InferenceVar::from(vid.as_u32()); |
| if self.var_stack.contains(&(var, VarKind::Ty(kind))) { |
| // recursive type |
| let default = self.table.fallback_value(var, kind).cast(Interner); |
| return (self.fallback)(var, VariableKind::Ty(kind), default, outer_binder) |
| .assert_ty_ref(Interner) |
| .clone(); |
| } |
| if let Ok(known_ty) = self.table.infer_ctxt.probe_ty_var(vid) { |
| let known_ty: Ty = ChalkToNextSolver::from_nextsolver(known_ty, self.table.interner); |
| // known_ty may contain other variables that are known by now |
| self.var_stack.push((var, VarKind::Ty(kind))); |
| let result = known_ty.fold_with(self, outer_binder); |
| self.var_stack.pop(); |
| result |
| } else { |
| let default = self.table.fallback_value(var, kind).cast(Interner); |
| (self.fallback)(var, VariableKind::Ty(kind), default, outer_binder) |
| .assert_ty_ref(Interner) |
| .clone() |
| } |
| } |
| TyVariableKind::Integer => { |
| let vid = self.table.infer_ctxt.inner.borrow_mut().int_unification_table().find(IntVid::from(var.index())); |
| let var = InferenceVar::from(vid.as_u32()); |
| if self.var_stack.contains(&(var, VarKind::Ty(kind))) { |
| // recursive type |
| let default = self.table.fallback_value(var, kind).cast(Interner); |
| return (self.fallback)(var, VariableKind::Ty(kind), default, outer_binder) |
| .assert_ty_ref(Interner) |
| .clone(); |
| } |
| if let Some(known_ty) = self.table.infer_ctxt.resolve_int_var(vid) { |
| let known_ty: Ty = ChalkToNextSolver::from_nextsolver(known_ty, self.table.interner); |
| // known_ty may contain other variables that are known by now |
| self.var_stack.push((var, VarKind::Ty(kind))); |
| let result = known_ty.fold_with(self, outer_binder); |
| self.var_stack.pop(); |
| result |
| } else { |
| let default = self.table.fallback_value(var, kind).cast(Interner); |
| (self.fallback)(var, VariableKind::Ty(kind), default, outer_binder) |
| .assert_ty_ref(Interner) |
| .clone() |
| } |
| } |
| TyVariableKind::Float => { |
| let vid = self.table.infer_ctxt.inner.borrow_mut().float_unification_table().find(FloatVid::from(var.index())); |
| let var = InferenceVar::from(vid.as_u32()); |
| if self.var_stack.contains(&(var, VarKind::Ty(kind))) { |
| // recursive type |
| let default = self.table.fallback_value(var, kind).cast(Interner); |
| return (self.fallback)(var, VariableKind::Ty(kind), default, outer_binder) |
| .assert_ty_ref(Interner) |
| .clone(); |
| } |
| if let Some(known_ty) = self.table.infer_ctxt.resolve_float_var(vid) { |
| let known_ty: Ty = ChalkToNextSolver::from_nextsolver(known_ty, self.table.interner); |
| // known_ty may contain other variables that are known by now |
| self.var_stack.push((var, VarKind::Ty(kind))); |
| let result = known_ty.fold_with(self, outer_binder); |
| self.var_stack.pop(); |
| result |
| } else { |
| let default = self.table.fallback_value(var, kind).cast(Interner); |
| (self.fallback)(var, VariableKind::Ty(kind), default, outer_binder) |
| .assert_ty_ref(Interner) |
| .clone() |
| } |
| } |
| } |
| } |
| |
| fn fold_inference_const( |
| &mut self, |
| ty: Ty, |
| var: InferenceVar, |
| outer_binder: DebruijnIndex, |
| ) -> Const { |
| let vid = self.table.infer_ctxt.root_const_var(rustc_type_ir::ConstVid::from_u32(var.index())); |
| let var = InferenceVar::from(vid.as_u32()); |
| let default = ConstData { |
| ty: ty.clone(), |
| value: ConstValue::Concrete(ConcreteConst { interned: ConstScalar::Unknown }), |
| } |
| .intern(Interner) |
| .cast(Interner); |
| if self.var_stack.contains(&(var, VarKind::Const)) { |
| // recursive |
| return (self.fallback)(var, VariableKind::Const(ty), default, outer_binder) |
| .assert_const_ref(Interner) |
| .clone(); |
| } |
| if let Ok(known_const) = self.table.infer_ctxt.probe_const_var(vid) { |
| let known_const: Const = ChalkToNextSolver::from_nextsolver(known_const, self.table.interner); |
| // known_ty may contain other variables that are known by now |
| self.var_stack.push((var, VarKind::Const)); |
| let result = known_const.fold_with(self, outer_binder); |
| self.var_stack.pop(); |
| result |
| } else { |
| (self.fallback)(var, VariableKind::Const(ty), default, outer_binder) |
| .assert_const_ref(Interner) |
| .clone() |
| } |
| } |
| |
| fn fold_inference_lifetime( |
| &mut self, |
| _var: InferenceVar, |
| _outer_binder: DebruijnIndex, |
| ) -> Lifetime { |
| // fall back all lifetimes to 'error -- currently we don't deal |
| // with any lifetimes, but we can sometimes get some lifetime |
| // variables through Chalk's unification, and this at least makes |
| // sure we don't leak them outside of inference |
| crate::error_lifetime() |
| } |
| } |
| } |
