bendns' repos / rust-analyzer
Unnamed repository; edit this file 'description' to name the repository.
Diffstat (limited to 'crates/hir-ty/src/infer/unify.rs')
-rw-r--r--crates/hir-ty/src/infer/unify.rs1194
1 files changed, 710 insertions, 484 deletions
diff --git a/crates/hir-ty/src/infer/unify.rs b/crates/hir-ty/src/infer/unify.rs
index c07755535f..1687857ae1 100644
--- a/crates/hir-ty/src/infer/unify.rs
+++ b/crates/hir-ty/src/infer/unify.rs
@@ -1,125 +1,118 @@
//! Unification and canonicalization logic.
-use std::{fmt, mem};
+use std::fmt;
use chalk_ir::{
- CanonicalVarKind, FloatTy, IntTy, TyVariableKind, UniverseIndex, cast::Cast,
- fold::TypeFoldable, interner::HasInterner, zip::Zip,
+ CanonicalVarKind, FloatTy, IntTy, TyVariableKind, cast::Cast, fold::TypeFoldable,
+ interner::HasInterner,
};
-use chalk_solve::infer::ParameterEnaVariableExt;
use either::Either;
-use ena::unify::UnifyKey;
use hir_def::{AdtId, lang_item::LangItem};
use hir_expand::name::Name;
use intern::sym;
-use rustc_hash::FxHashMap;
+use rustc_hash::{FxHashMap, FxHashSet};
+use rustc_type_ir::inherent::Ty as _;
+use rustc_type_ir::{
+ FloatVid, IntVid, TyVid, TypeVisitableExt,
+ inherent::{IntoKind, Span, Term as _},
+ relate::{Relate, solver_relating::RelateExt},
+ solve::{Certainty, GoalSource, NoSolution},
+};
use smallvec::SmallVec;
use triomphe::Arc;
-use super::{InferOk, InferResult, InferenceContext, TypeError};
+use super::{InferResult, InferenceContext, TypeError};
+use crate::next_solver::ErrorGuaranteed;
use crate::{
- AliasEq, AliasTy, BoundVar, Canonical, Const, ConstValue, DebruijnIndex, DomainGoal,
- GenericArg, GenericArgData, Goal, GoalData, Guidance, InEnvironment, InferenceVar, Interner,
- Lifetime, OpaqueTyId, ParamKind, ProjectionTy, ProjectionTyExt, Scalar, Solution, Substitution,
- TraitEnvironment, TraitRef, Ty, TyBuilder, TyExt, TyKind, VariableKind, WhereClause,
- consteval::unknown_const, db::HirDatabase, fold_generic_args, fold_tys_and_consts,
- to_chalk_trait_id, traits::FnTrait,
+ AliasTy, BoundVar, Canonical, Const, ConstValue, DebruijnIndex, GenericArg, GenericArgData,
+ Goal, GoalData, InEnvironment, InferenceVar, Interner, Lifetime, OpaqueTyId, ParamKind,
+ ProjectionTy, Scalar, Substitution, TraitEnvironment, TraitRef, Ty, TyBuilder, TyExt, TyKind,
+ VariableKind, WhereClause,
+ consteval::unknown_const,
+ db::HirDatabase,
+ fold_generic_args, fold_tys_and_consts,
+ next_solver::infer::InferOk,
+ next_solver::{
+ self, ClauseKind, DbInterner, ParamEnv, Predicate, PredicateKind, SolverDefIds, Term,
+ fulfill::FulfillmentCtxt,
+ infer::{
+ DbInternerInferExt, InferCtxt,
+ snapshot::CombinedSnapshot,
+ traits::{Obligation, ObligationCause},
+ },
+ inspect::{InspectConfig, InspectGoal, ProofTreeVisitor},
+ mapping::{ChalkToNextSolver, NextSolverToChalk},
+ },
+ to_chalk_trait_id,
+ traits::{
+ FnTrait, NextTraitSolveResult, next_trait_solve_canonical_in_ctxt, next_trait_solve_in_ctxt,
+ },
};
-impl InferenceContext<'_> {
- pub(super) fn canonicalize<T>(&mut self, t: T) -> Canonical<T>
+impl<'db> InferenceContext<'db> {
+ pub(super) fn canonicalize<T>(&mut self, t: T) -> rustc_type_ir::Canonical<DbInterner<'db>, T>
where
- T: TypeFoldable<Interner> + HasInterner<Interner = Interner>,
+ 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 = self.table.var_unification_table.inference_var_root(self_ty);
- let pending_obligations = mem::take(&mut self.table.pending_obligations);
- let obligations = pending_obligations
- .iter()
- .filter_map(|obligation| match obligation.value.value.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,
- };
+struct NestedObligationsForSelfTy<'a, 'db> {
+ ctx: &'a InferenceTable<'db>,
+ self_ty: TyVid,
+ root_cause: &'a ObligationCause,
+ obligations_for_self_ty: &'a mut SmallVec<[Obligation<'db, Predicate<'db>>; 4]>,
+}
- let uncanonical =
- chalk_ir::Substitute::apply(&obligation.free_vars, ty, Interner);
- if matches!(
- self.resolve_ty_shallow(&uncanonical).kind(Interner),
- TyKind::InferenceVar(iv, TyVariableKind::General) if *iv == root,
- ) {
- Some(chalk_ir::Substitute::apply(
- &obligation.free_vars,
- clause.clone(),
- Interner,
- ))
- } else {
- None
- }
- }
- _ => None,
- })
- .collect();
- self.table.pending_obligations = pending_obligations;
+impl<'a, 'db> ProofTreeVisitor<'db> for NestedObligationsForSelfTy<'a, 'db> {
+ type Result = ();
- obligations
+ fn config(&self) -> InspectConfig {
+ // Using an intentionally low depth to minimize the chance of future
+ // breaking changes in case we adapt the approach later on. This also
+ // avoids any hangs for exponentially growing proof trees.
+ InspectConfig { max_depth: 5 }
}
-}
-#[derive(Debug, Clone)]
-pub(crate) struct Canonicalized<T>
-where
- T: HasInterner<Interner = Interner>,
-{
- pub(crate) value: Canonical<T>,
- free_vars: Vec<GenericArg>,
-}
+ fn visit_goal(&mut self, inspect_goal: &InspectGoal<'_, 'db>) {
+ // No need to walk into goal subtrees that certainly hold, since they
+ // wouldn't then be stalled on an infer var.
+ if inspect_goal.result() == Ok(Certainty::Yes) {
+ return;
+ }
-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));
- ctx.unify(var.assert_ty_ref(Interner), &ty);
- } else {
- let _ = ctx.try_unify(var, &new_vars.apply(v.clone(), Interner));
- }
+ let db = self.ctx.interner;
+ let goal = inspect_goal.goal();
+ if self.ctx.predicate_has_self_ty(goal.predicate, self.self_ty)
+ // We do not push the instantiated forms of goals as it would cause any
+ // aliases referencing bound vars to go from having escaping bound vars to
+ // being able to be normalized to an inference variable.
+ //
+ // This is mostly just a hack as arbitrary nested goals could still contain
+ // such aliases while having a different `GoalSource`. Closure signature inference
+ // however can't really handle *every* higher ranked `Fn` goal also being present
+ // in the form of `?c: Fn<(<?x as Trait<'!a>>::Assoc)`.
+ //
+ // This also just better matches the behaviour of the old solver where we do not
+ // encounter instantiated forms of goals, only nested goals that referred to bound
+ // vars from instantiated goals.
+ && !matches!(inspect_goal.source(), GoalSource::InstantiateHigherRanked)
+ {
+ self.obligations_for_self_ty.push(Obligation::new(
+ db,
+ self.root_cause.clone(),
+ goal.param_env,
+ goal.predicate,
+ ));
+ }
+
+ // If there's a unique way to prove a given goal, recurse into
+ // that candidate. This means that for `impl<F: FnOnce(u32)> Trait<F> for () {}`
+ // and a `(): Trait<?0>` goal we recurse into the impl and look at
+ // the nested `?0: FnOnce(u32)` goal.
+ if let Some(candidate) = inspect_goal.unique_applicable_candidate() {
+ candidate.visit_nested_no_probe(self)
}
}
}
@@ -153,7 +146,7 @@ pub fn could_unify_deeply(
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.select_obligations_where_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);
@@ -219,37 +212,118 @@ bitflags::bitflags! {
}
}
-type ChalkInferenceTable = chalk_solve::infer::InferenceTable<Interner>;
-
#[derive(Clone)]
-pub(crate) struct InferenceTable<'a> {
- pub(crate) db: &'a dyn HirDatabase,
+pub(crate) struct InferenceTable<'db> {
+ pub(crate) db: &'db dyn HirDatabase,
+ pub(crate) interner: DbInterner<'db>,
pub(crate) trait_env: Arc<TraitEnvironment>,
+ pub(crate) param_env: ParamEnv<'db>,
pub(crate) tait_coercion_table: Option<FxHashMap<OpaqueTyId, Ty>>,
- var_unification_table: ChalkInferenceTable,
- type_variable_table: SmallVec<[TypeVariableFlags; 16]>,
- pending_obligations: Vec<Canonicalized<InEnvironment<Goal>>>,
- /// Double buffer used in [`Self::resolve_obligations_as_possible`] to cut down on
- /// temporary allocations.
- resolve_obligations_buffer: Vec<Canonicalized<InEnvironment<Goal>>>,
+ pub(crate) infer_ctxt: InferCtxt<'db>,
+ diverging_tys: FxHashSet<Ty>,
+ pub(super) fulfillment_cx: FulfillmentCtxt<'db>,
}
-pub(crate) struct InferenceTableSnapshot {
- var_table_snapshot: chalk_solve::infer::InferenceSnapshot<Interner>,
- type_variable_table: SmallVec<[TypeVariableFlags; 16]>,
- pending_obligations: Vec<Canonicalized<InEnvironment<Goal>>>,
+pub(crate) struct InferenceTableSnapshot<'db> {
+ ctxt_snapshot: CombinedSnapshot,
+ obligations: FulfillmentCtxt<'db>,
+ diverging_tys: FxHashSet<Ty>,
}
-impl<'a> InferenceTable<'a> {
- pub(crate) fn new(db: &'a dyn HirDatabase, trait_env: Arc<TraitEnvironment>) -> Self {
+impl<'db> InferenceTable<'db> {
+ pub(crate) fn new(db: &'db dyn HirDatabase, trait_env: Arc<TraitEnvironment>) -> Self {
+ let interner = DbInterner::new_with(db, Some(trait_env.krate), trait_env.block);
+ let infer_ctxt = interner.infer_ctxt().build(rustc_type_ir::TypingMode::Analysis {
+ defining_opaque_types_and_generators: SolverDefIds::new_from_iter(interner, []),
+ });
InferenceTable {
db,
+ interner,
+ param_env: trait_env.env.to_nextsolver(interner),
trait_env,
tait_coercion_table: None,
- var_unification_table: ChalkInferenceTable::new(),
- type_variable_table: SmallVec::new(),
- pending_obligations: Vec::new(),
- resolve_obligations_buffer: Vec::new(),
+ fulfillment_cx: FulfillmentCtxt::new(&infer_ctxt),
+ infer_ctxt,
+ diverging_tys: FxHashSet::default(),
+ }
+ }
+
+ pub(crate) fn type_var_is_sized(&self, self_ty: TyVid) -> bool {
+ let Some(sized_did) = LangItem::Sized.resolve_trait(self.db, self.trait_env.krate) else {
+ return true;
+ };
+ self.obligations_for_self_ty(self_ty).into_iter().any(|obligation| {
+ match obligation.predicate.kind().skip_binder() {
+ crate::next_solver::PredicateKind::Clause(
+ crate::next_solver::ClauseKind::Trait(data),
+ ) => data.def_id().0 == sized_did,
+ _ => false,
+ }
+ })
+ }
+
+ pub(super) fn obligations_for_self_ty(
+ &self,
+ self_ty: TyVid,
+ ) -> SmallVec<[Obligation<'db, Predicate<'db>>; 4]> {
+ let obligations = self.fulfillment_cx.pending_obligations();
+ let mut obligations_for_self_ty = SmallVec::new();
+ for obligation in obligations {
+ let mut visitor = NestedObligationsForSelfTy {
+ ctx: self,
+ self_ty,
+ obligations_for_self_ty: &mut obligations_for_self_ty,
+ root_cause: &obligation.cause,
+ };
+
+ let goal = obligation.as_goal();
+ self.infer_ctxt.visit_proof_tree(goal, &mut visitor);
+ }
+
+ obligations_for_self_ty.retain_mut(|obligation| {
+ obligation.predicate = self.infer_ctxt.resolve_vars_if_possible(obligation.predicate);
+ !obligation.predicate.has_placeholders()
+ });
+ obligations_for_self_ty
+ }
+
+ fn predicate_has_self_ty(&self, predicate: Predicate<'db>, expected_vid: TyVid) -> bool {
+ match predicate.kind().skip_binder() {
+ PredicateKind::Clause(ClauseKind::Trait(data)) => {
+ self.type_matches_expected_vid(expected_vid, data.self_ty())
+ }
+ PredicateKind::Clause(ClauseKind::Projection(data)) => {
+ self.type_matches_expected_vid(expected_vid, data.projection_term.self_ty())
+ }
+ PredicateKind::Clause(ClauseKind::ConstArgHasType(..))
+ | PredicateKind::Subtype(..)
+ | PredicateKind::Coerce(..)
+ | PredicateKind::Clause(ClauseKind::RegionOutlives(..))
+ | PredicateKind::Clause(ClauseKind::TypeOutlives(..))
+ | PredicateKind::Clause(ClauseKind::WellFormed(..))
+ | PredicateKind::DynCompatible(..)
+ | PredicateKind::NormalizesTo(..)
+ | PredicateKind::AliasRelate(..)
+ | PredicateKind::Clause(ClauseKind::ConstEvaluatable(..))
+ | PredicateKind::ConstEquate(..)
+ | PredicateKind::Clause(ClauseKind::HostEffect(..))
+ | PredicateKind::Clause(ClauseKind::UnstableFeature(_))
+ | PredicateKind::Ambiguous => false,
+ }
+ }
+
+ fn type_matches_expected_vid(
+ &self,
+ expected_vid: TyVid,
+ ty: crate::next_solver::Ty<'db>,
+ ) -> bool {
+ let ty = self.shallow_resolve(ty);
+
+ match ty.kind() {
+ crate::next_solver::TyKind::Infer(rustc_type_ir::TyVar(found_vid)) => {
+ self.infer_ctxt.root_var(expected_vid) == self.infer_ctxt.root_var(found_vid)
+ }
+ _ => false,
}
}
@@ -260,29 +334,58 @@ impl<'a> InferenceTable<'a> {
/// marked as diverging if necessary, so that resolving them gives the right
/// result.
pub(super) fn propagate_diverging_flag(&mut self) {
- for i in 0..self.type_variable_table.len() {
- if !self.type_variable_table[i].contains(TypeVariableFlags::DIVERGING) {
- continue;
+ 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));
+ }
+ }
+ },
+ _ => {}
}
- let v = InferenceVar::from(i as u32);
- let root = self.var_unification_table.inference_var_root(v);
- self.modify_type_variable_flag(root, |f| {
- *f |= TypeVariableFlags::DIVERGING;
- });
}
+ self.diverging_tys.extend(new_tys);
}
- pub(super) fn set_diverging(&mut self, iv: InferenceVar, diverging: bool) {
- self.modify_type_variable_flag(iv, |f| {
- f.set(TypeVariableFlags::DIVERGING, diverging);
- });
+ pub(super) fn set_diverging(&mut self, iv: InferenceVar, kind: TyVariableKind) {
+ self.diverging_tys.insert(TyKind::InferenceVar(iv, kind).intern(Interner));
}
fn fallback_value(&self, iv: InferenceVar, kind: TyVariableKind) -> Ty {
- let is_diverging = self
- .type_variable_table
- .get(iv.index() as usize)
- .is_some_and(|data| data.contains(TypeVariableFlags::DIVERGING));
+ let is_diverging =
+ self.diverging_tys.contains(&TyKind::InferenceVar(iv, kind).intern(Interner));
if is_diverging {
return TyKind::Never.intern(Interner);
}
@@ -294,30 +397,14 @@ impl<'a> InferenceTable<'a> {
.intern(Interner)
}
- pub(crate) fn canonicalize_with_free_vars<T>(&mut self, t: T) -> Canonicalized<T>
- where
- T: TypeFoldable<Interner> + HasInterner<Interner = Interner>,
- {
- // try to resolve obligations before canonicalizing, since this might
- // result in new knowledge about variables
- self.resolve_obligations_as_possible();
- let result = self.var_unification_table.canonicalize(Interner, t);
- let free_vars = result
- .free_vars
- .into_iter()
- .map(|free_var| free_var.to_generic_arg(Interner))
- .collect();
- Canonicalized { value: result.quantified, free_vars }
- }
-
- pub(crate) fn canonicalize<T>(&mut self, t: T) -> Canonical<T>
+ pub(crate) fn canonicalize<T>(&mut self, t: T) -> rustc_type_ir::Canonical<DbInterner<'db>, T>
where
- T: TypeFoldable<Interner> + HasInterner<Interner = Interner>,
+ T: rustc_type_ir::TypeFoldable<DbInterner<'db>>,
{
// try to resolve obligations before canonicalizing, since this might
// result in new knowledge about variables
- self.resolve_obligations_as_possible();
- self.var_unification_table.canonicalize(Interner, t).quantified
+ self.select_obligations_where_possible();
+ self.infer_ctxt.canonicalize_response(t)
}
/// Recurses through the given type, normalizing associated types mentioned
@@ -326,42 +413,26 @@ impl<'a> InferenceTable<'a> {
/// 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.
- pub(crate) fn normalize_associated_types_in<T>(&mut self, ty: T) -> T
+ pub(crate) fn normalize_associated_types_in<T, U>(&mut self, ty: T) -> T
where
- T: HasInterner<Interner = Interner> + TypeFoldable<Interner>,
+ T: ChalkToNextSolver<'db, U>,
+ U: NextSolverToChalk<'db, T> + rustc_type_ir::TypeFoldable<DbInterner<'db>>,
{
- fold_tys_and_consts(
- ty,
- |e, _| match e {
- Either::Left(ty) => Either::Left(match ty.kind(Interner) {
- TyKind::Alias(AliasTy::Projection(proj_ty)) => {
- self.normalize_projection_ty(proj_ty.clone())
- }
- _ => 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,
- )
+ self.normalize_associated_types_in_ns(ty.to_nextsolver(self.interner))
+ .to_chalk(self.interner)
+ }
+
+ // FIXME: We should get rid of this method. We cannot deeply normalize during inference, only when finishing.
+ // Inference should use shallow normalization (`try_structurally_resolve_type()`) only, when needed.
+ pub(crate) fn normalize_associated_types_in_ns<T>(&mut self, ty: T) -> T
+ where
+ T: rustc_type_ir::TypeFoldable<DbInterner<'db>> + Clone,
+ {
+ let ty = self.resolve_vars_with_obligations(ty);
+ self.infer_ctxt
+ .at(&ObligationCause::new(), self.param_env)
+ .deeply_normalize(ty.clone())
+ .unwrap_or(ty)
}
/// Works almost same as [`Self::normalize_associated_types_in`], but this also resolves shallow
@@ -423,51 +494,60 @@ impl<'a> InferenceTable<'a> {
}
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
+ let ty = TyKind::Alias(chalk_ir::AliasTy::Projection(proj_ty))
+ .intern(Interner)
+ .to_nextsolver(self.interner);
+ self.normalize_alias_ty(ty).to_chalk(self.interner)
}
- fn modify_type_variable_flag<F>(&mut self, var: InferenceVar, cb: F)
- where
- F: FnOnce(&mut TypeVariableFlags),
- {
- let idx = var.index() as usize;
- if self.type_variable_table.len() <= idx {
- self.extend_type_variable_table(idx);
- }
- if let Some(f) = self.type_variable_table.get_mut(idx) {
- cb(f);
- }
- }
- fn extend_type_variable_table(&mut self, to_index: usize) {
- let count = to_index - self.type_variable_table.len() + 1;
- self.type_variable_table.extend(std::iter::repeat_n(TypeVariableFlags::default(), count));
+ pub(crate) fn normalize_alias_ty(
+ &mut self,
+ alias: crate::next_solver::Ty<'db>,
+ ) -> crate::next_solver::Ty<'db> {
+ let infer_term = self.infer_ctxt.next_ty_var();
+ let obligation = crate::next_solver::Predicate::new(
+ self.interner,
+ crate::next_solver::Binder::dummy(crate::next_solver::PredicateKind::AliasRelate(
+ alias.into(),
+ infer_term.into(),
+ rustc_type_ir::AliasRelationDirection::Equate,
+ )),
+ );
+ self.register_obligation(obligation);
+ self.resolve_vars_with_obligations(infer_term)
}
fn new_var(&mut self, kind: TyVariableKind, diverging: bool) -> Ty {
- let var = self.var_unification_table.new_variable(UniverseIndex::ROOT);
- // Chalk might have created some type variables for its own purposes that we don't know about...
- self.extend_type_variable_table(var.index() as usize);
- assert_eq!(var.index() as usize, self.type_variable_table.len() - 1);
- let flags = self.type_variable_table.get_mut(var.index() as usize).unwrap();
+ 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 {
- *flags |= TypeVariableFlags::DIVERGING;
+ self.diverging_tys.insert(ty.clone());
}
- if matches!(kind, TyVariableKind::Integer) {
- *flags |= TypeVariableFlags::INTEGER;
- } else if matches!(kind, TyVariableKind::Float) {
- *flags |= TypeVariableFlags::FLOAT;
- }
- var.to_ty_with_kind(Interner, kind)
+ ty
}
pub(crate) fn new_type_var(&mut self) -> Ty {
self.new_var(TyVariableKind::General, false)
}
+ pub(crate) fn next_ty_var(&mut self) -> crate::next_solver::Ty<'db> {
+ self.infer_ctxt.next_ty_var()
+ }
+
pub(crate) fn new_integer_var(&mut self) -> Ty {
self.new_var(TyVariableKind::Integer, false)
}
@@ -481,15 +561,21 @@ impl<'a> InferenceTable<'a> {
}
pub(crate) fn new_const_var(&mut self, ty: Ty) -> Const {
- let var = self.var_unification_table.new_variable(UniverseIndex::ROOT);
+ 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.var_unification_table.new_variable(UniverseIndex::ROOT);
+ let var = self.infer_ctxt.next_region_vid();
+ let var = InferenceVar::from(var.as_u32());
var.to_lifetime(Interner)
}
+ pub(crate) fn next_region_var(&mut self) -> crate::next_solver::Region<'db> {
+ self.infer_ctxt.next_region_var()
+ }
+
pub(crate) fn resolve_with_fallback<T>(
&mut self,
t: T,
@@ -498,16 +584,18 @@ impl<'a> InferenceTable<'a> {
where
T: HasInterner<Interner = Interner> + TypeFoldable<Interner>,
{
- self.resolve_with_fallback_inner(&mut Vec::new(), t, &fallback)
+ 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| {
- let param_infer_var =
- kind.map_ref(|&ui| self.var_unification_table.new_variable(ui));
- param_infer_var.to_generic_arg(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),
}),
)
}
@@ -520,25 +608,40 @@ impl<'a> InferenceTable<'a> {
subst.apply(canonical.value, Interner)
}
+ pub(crate) fn instantiate_canonical_ns<T>(
+ &mut self,
+ canonical: rustc_type_ir::Canonical<DbInterner<'db>, T>,
+ ) -> T
+ where
+ T: rustc_type_ir::TypeFoldable<DbInterner<'db>>,
+ {
+ self.infer_ctxt.instantiate_canonical(&canonical).0
+ }
+
fn resolve_with_fallback_inner<T>(
&mut self,
- var_stack: &mut Vec<InferenceVar>,
t: T,
fallback: &dyn Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg,
) -> T
where
T: HasInterner<Interner = Interner> + TypeFoldable<Interner>,
{
+ let 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
+ pub(crate) fn resolve_completely<T, U>(&mut self, t: T) -> T
where
- T: HasInterner<Interner = Interner> + TypeFoldable<Interner>,
+ T: HasInterner<Interner = Interner> + TypeFoldable<Interner> + ChalkToNextSolver<'db, U>,
+ U: NextSolverToChalk<'db, T> + rustc_type_ir::TypeFoldable<DbInterner<'db>>,
{
+ let t = self.resolve_with_fallback(t, &|_, _, d, _| d);
+ let t = self.normalize_associated_types_in(t);
+ // let t = self.resolve_opaque_tys_in(t);
+ // Resolve again, because maybe normalization inserted infer vars.
self.resolve_with_fallback(t, &|_, _, d, _| d)
}
@@ -554,29 +657,26 @@ impl<'a> InferenceTable<'a> {
let int_fallback = TyKind::Scalar(Scalar::Int(IntTy::I32)).intern(Interner);
let float_fallback = TyKind::Scalar(Scalar::Float(FloatTy::F64)).intern(Interner);
- let scalar_vars: Vec<_> = self
- .type_variable_table
- .iter()
- .enumerate()
- .filter_map(|(index, flags)| {
- let kind = if flags.contains(TypeVariableFlags::INTEGER) {
- TyVariableKind::Integer
- } else if flags.contains(TypeVariableFlags::FLOAT) {
- TyVariableKind::Float
- } else {
- return None;
+ 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!(),
};
-
- // FIXME: This is not really the nicest way to get `InferenceVar`s. Can we get them
- // without directly constructing them from `index`?
- let var = InferenceVar::from(index as u32).to_ty(Interner, kind);
- Some(var)
- })
- .collect();
-
- for var in scalar_vars {
+ 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::Float);
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,
@@ -588,258 +688,291 @@ impl<'a> InferenceTable<'a> {
}
/// Unify two relatable values (e.g. `Ty`) and register new trait goals that arise from that.
- #[tracing::instrument(skip_all)]
- pub(crate) fn unify<T: ?Sized + Zip<Interner>>(&mut self, ty1: &T, ty2: &T) -> bool {
+ pub(crate) fn unify<T: ChalkToNextSolver<'db, U>, U: Relate<DbInterner<'db>>>(
+ &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);
+ self.register_obligations(result.goals);
+ true
+ }
+
+ pub(crate) fn unify_ns<T: Relate<DbInterner<'db>>>(&mut self, lhs: T, rhs: T) -> bool {
+ let Ok(infer_ok) = self.try_unify_ns(lhs, rhs) else {
+ return false;
+ };
+ self.register_obligations(infer_ok.goals);
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: ?Sized + Zip<Interner>>(&mut self, ty1: &T, ty2: &T) -> bool {
+ pub(crate) fn unify_deeply<T: ChalkToNextSolver<'db, U>, U: Relate<DbInterner<'db>>>(
+ &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 canonicalized = self.canonicalize_with_free_vars(goal.clone());
- self.try_resolve_obligation(&canonicalized).is_some()
+ result.goals.into_iter().all(|goal| {
+ matches!(next_trait_solve_in_ctxt(&self.infer_ctxt, goal), Ok((_, Certainty::Yes)))
})
}
/// 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: ?Sized + Zip<Interner>>(
+ pub(crate) fn try_unify<T: ChalkToNextSolver<'db, U>, U: Relate<DbInterner<'db>>>(
&mut self,
t1: &T,
t2: &T,
- ) -> InferResult<()> {
- match self.var_unification_table.relate(
- Interner,
- &self.db,
- &self.trait_env.env,
- chalk_ir::Variance::Invariant,
- t1,
- t2,
- ) {
- Ok(result) => Ok(InferOk { goals: result.goals, value: () }),
- Err(chalk_ir::NoSolution) => Err(TypeError),
+ ) -> InferResult<'db, ()> {
+ let lhs = t1.to_nextsolver(self.interner);
+ let rhs = t2.to_nextsolver(self.interner);
+ self.try_unify_ns(lhs, rhs)
+ }
+
+ /// 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_ns<T: Relate<DbInterner<'db>>>(
+ &mut self,
+ lhs: T,
+ rhs: T,
+ ) -> InferResult<'db, ()> {
+ let variance = rustc_type_ir::Variance::Invariant;
+ let span = crate::next_solver::Span::dummy();
+ match self.infer_ctxt.relate(self.param_env, lhs, variance, rhs, span) {
+ Ok(goals) => Ok(crate::infer::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 {
- self.resolve_obligations_as_possible();
- self.var_unification_table.normalize_ty_shallow(Interner, ty).unwrap_or_else(|| ty.clone())
+ self.shallow_resolve(ty.to_nextsolver(self.interner)).to_chalk(self.interner)
+ }
+
+ pub(crate) fn shallow_resolve(
+ &self,
+ ty: crate::next_solver::Ty<'db>,
+ ) -> crate::next_solver::Ty<'db> {
+ self.infer_ctxt.shallow_resolve(ty)
+ }
+
+ pub(crate) fn resolve_vars_with_obligations<T>(&mut self, t: T) -> T
+ where
+ T: rustc_type_ir::TypeFoldable<DbInterner<'db>>,
+ {
+ use rustc_type_ir::TypeVisitableExt;
+
+ if !t.has_non_region_infer() {
+ return t;
+ }
+
+ let t = self.infer_ctxt.resolve_vars_if_possible(t);
+
+ if !t.has_non_region_infer() {
+ return t;
+ }
+
+ self.select_obligations_where_possible();
+ self.infer_ctxt.resolve_vars_if_possible(t)
+ }
+
+ pub(crate) fn structurally_resolve_type(&mut self, ty: &Ty) -> Ty {
+ if let TyKind::Alias(..) = ty.kind(Interner) {
+ self.structurally_normalize_ty(ty)
+ } else {
+ self.resolve_vars_with_obligations(ty.to_nextsolver(self.interner))
+ .to_chalk(self.interner)
+ }
+ }
+
+ fn structurally_normalize_ty(&mut self, ty: &Ty) -> Ty {
+ self.structurally_normalize_term(ty.to_nextsolver(self.interner).into())
+ .expect_ty()
+ .to_chalk(self.interner)
+ }
+
+ fn structurally_normalize_term(&mut self, term: Term<'db>) -> Term<'db> {
+ self.infer_ctxt
+ .at(&ObligationCause::new(), self.param_env)
+ .structurally_normalize_term(term, &mut self.fulfillment_cx)
+ .unwrap_or(term)
}
- pub(crate) fn snapshot(&mut self) -> InferenceTableSnapshot {
- let var_table_snapshot = self.var_unification_table.snapshot();
- let type_variable_table = self.type_variable_table.clone();
- let pending_obligations = self.pending_obligations.clone();
- InferenceTableSnapshot { var_table_snapshot, pending_obligations, type_variable_table }
+ /// Try to resolve `ty` to a structural type, normalizing aliases.
+ ///
+ /// In case there is still ambiguity, the returned type may be an inference
+ /// variable. This is different from `structurally_resolve_type` which errors
+ /// in this case.
+ pub(crate) fn try_structurally_resolve_type(
+ &mut self,
+ ty: crate::next_solver::Ty<'db>,
+ ) -> crate::next_solver::Ty<'db> {
+ if let crate::next_solver::TyKind::Alias(..) = ty.kind() {
+ // We need to use a separate variable here as otherwise the temporary for
+ // `self.fulfillment_cx.borrow_mut()` is alive in the `Err` branch, resulting
+ // in a reentrant borrow, causing an ICE.
+ let result = self
+ .infer_ctxt
+ .at(&ObligationCause::misc(), self.param_env)
+ .structurally_normalize_ty(ty, &mut self.fulfillment_cx);
+ match result {
+ Ok(normalized_ty) => normalized_ty,
+ Err(_errors) => crate::next_solver::Ty::new_error(self.interner, ErrorGuaranteed),
+ }
+ } else {
+ self.resolve_vars_with_obligations(ty)
+ }
+ }
+
+ pub(crate) fn snapshot(&mut self) -> InferenceTableSnapshot<'db> {
+ let ctxt_snapshot = self.infer_ctxt.start_snapshot();
+ let diverging_tys = self.diverging_tys.clone();
+ let obligations = self.fulfillment_cx.clone();
+ InferenceTableSnapshot { ctxt_snapshot, diverging_tys, obligations }
}
#[tracing::instrument(skip_all)]
- pub(crate) fn rollback_to(&mut self, snapshot: InferenceTableSnapshot) {
- self.var_unification_table.rollback_to(snapshot.var_table_snapshot);
- self.type_variable_table = snapshot.type_variable_table;
- self.pending_obligations = snapshot.pending_obligations;
+ pub(crate) fn rollback_to(&mut self, snapshot: InferenceTableSnapshot<'db>) {
+ self.infer_ctxt.rollback_to(snapshot.ctxt_snapshot);
+ self.diverging_tys = snapshot.diverging_tys;
+ self.fulfillment_cx = snapshot.obligations;
}
#[tracing::instrument(skip_all)]
- pub(crate) fn run_in_snapshot<T>(&mut self, f: impl FnOnce(&mut InferenceTable<'_>) -> T) -> T {
+ pub(crate) fn run_in_snapshot<T>(
+ &mut self,
+ f: impl FnOnce(&mut InferenceTable<'db>) -> 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<'db>) -> 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).
- pub(crate) fn try_obligation(&mut self, goal: Goal) -> Option<Solution> {
+ #[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);
+ let canonicalized = self.canonicalize(in_env.to_nextsolver(self.interner));
- self.db.trait_solve(self.trait_env.krate, self.trait_env.block, canonicalized)
+ next_trait_solve_canonical_in_ctxt(&self.infer_ctxt, canonicalized)
}
- 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)
+ #[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 goal = goal.to_nextsolver(self.interner);
+ let result = next_trait_solve_in_ctxt(&self.infer_ctxt, goal);
+ result.map(|m| m.1)
}
- fn register_obligation_in_env(&mut self, goal: InEnvironment<Goal>) {
- let canonicalized = self.canonicalize_with_free_vars(goal);
- let solution = self.try_resolve_obligation(&canonicalized);
- if matches!(solution, Some(Solution::Ambig(_))) {
- self.pending_obligations.push(canonicalized);
- }
- }
-
- 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 register_obligation(&mut self, predicate: Predicate<'db>) {
+ let goal = next_solver::Goal {
+ param_env: self.trait_env.env.to_nextsolver(self.interner),
+ predicate,
+ };
+ 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;
- let mut obligations = mem::take(&mut self.resolve_obligations_buffer);
- while mem::take(&mut changed) {
- mem::swap(&mut self.pending_obligations, &mut obligations);
-
- for canonicalized in obligations.drain(..) {
- if !self.check_changed(&canonicalized) {
- self.pending_obligations.push(canonicalized);
- continue;
- }
- changed = true;
- let uncanonical = chalk_ir::Substitute::apply(
- &canonicalized.free_vars,
- canonicalized.value.value,
- Interner,
+ #[tracing::instrument(level = "debug", skip(self))]
+ fn register_obligation_in_env(
+ &mut self,
+ goal: next_solver::Goal<'db, next_solver::Predicate<'db>>,
+ ) {
+ let result = next_trait_solve_in_ctxt(&self.infer_ctxt, goal);
+ tracing::debug!(?result);
+ match result {
+ Ok((_, Certainty::Yes)) => {}
+ Err(rustc_type_ir::solve::NoSolution) => {}
+ Ok((_, Certainty::Maybe { .. })) => {
+ self.fulfillment_cx.register_predicate_obligation(
+ &self.infer_ctxt,
+ Obligation::new(
+ self.interner,
+ ObligationCause::new(),
+ goal.param_env,
+ goal.predicate,
+ ),
);
- self.register_obligation_in_env(uncanonical);
}
}
- self.resolve_obligations_buffer = obligations;
- self.resolve_obligations_buffer.clear();
}
- 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
- }
+ pub(crate) fn register_infer_ok<T>(&mut self, infer_ok: InferOk<'db, T>) -> T {
+ let InferOk { value, obligations } = infer_ok;
+ self.register_predicates(obligations);
+ value
+ }
- 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()
- }
- }
+ pub(crate) fn register_obligations(
+ &mut self,
+ obligations: Vec<crate::next_solver::Goal<'db, crate::next_solver::Predicate<'db>>>,
+ ) {
+ obligations.into_iter().for_each(|goal| self.register_obligation_in_env(goal));
+ }
- 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()
- }
- }
+ pub(crate) fn select_obligations_where_possible(&mut self) {
+ self.fulfillment_cx.select_where_possible(&self.infer_ctxt);
+ }
- 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)
- }
- }
+ pub(super) fn register_predicate(
+ &mut self,
+ obligation: crate::next_solver::infer::traits::PredicateObligation<'db>,
+ ) {
+ if obligation.has_escaping_bound_vars() {
+ panic!("escaping bound vars in predicate {:?}", obligation);
}
- 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)
- }
-
- /// This checks whether any of the free variables in the `canonicalized`
- /// have changed (either been unified with another variable, or with a
- /// value). If this is not the case, we don't need to try to solve the goal
- /// again -- it'll give the same result as last time.
- fn check_changed(&mut self, canonicalized: &Canonicalized<InEnvironment<Goal>>) -> bool {
- canonicalized.free_vars.iter().any(|var| {
- let iv = match var.data(Interner) {
- GenericArgData::Ty(ty) => ty.inference_var(Interner),
- GenericArgData::Lifetime(lt) => lt.inference_var(Interner),
- GenericArgData::Const(c) => c.inference_var(Interner),
- }
- .expect("free var is not inference var");
- if self.var_unification_table.probe_var(iv).is_some() {
- return true;
- }
- let root = self.var_unification_table.inference_var_root(iv);
- iv != root
- })
+ self.fulfillment_cx.register_predicate_obligation(&self.infer_ctxt, obligation);
}
- fn try_resolve_obligation(
- &mut self,
- canonicalized: &Canonicalized<InEnvironment<Goal>>,
- ) -> Option<chalk_solve::Solution<Interner>> {
- let solution = self.db.trait_solve(
- self.trait_env.krate,
- self.trait_env.block,
- canonicalized.value.clone(),
- );
-
- match &solution {
- Some(Solution::Unique(canonical_subst)) => {
- canonicalized.apply_solution(
- self,
- Canonical {
- binders: canonical_subst.binders.clone(),
- // FIXME: handle constraints
- value: canonical_subst.value.subst.clone(),
- },
- );
- }
- Some(Solution::Ambig(Guidance::Definite(substs))) => {
- canonicalized.apply_solution(self, substs.clone());
- }
- Some(_) => {
- // FIXME use this when trying to resolve everything at the end
- }
- None => {
- // FIXME obligation cannot be fulfilled => diagnostic
- }
- }
- solution
+ pub(super) fn register_predicates<I>(&mut self, obligations: I)
+ where
+ I: IntoIterator<Item = crate::next_solver::infer::traits::PredicateObligation<'db>>,
+ {
+ obligations.into_iter().for_each(|obligation| {
+ self.register_predicate(obligation);
+ });
}
pub(crate) fn callable_sig(
&mut self,
ty: &Ty,
num_args: usize,
- ) -> Option<(Option<FnTrait>, Vec<Ty>, Ty)> {
+ ) -> Option<(Option<FnTrait>, Vec<crate::next_solver::Ty<'db>>, crate::next_solver::Ty<'db>)>
+ {
match ty.callable_sig(self.db) {
- Some(sig) => Some((None, sig.params().to_vec(), sig.ret().clone())),
+ Some(sig) => Some((
+ None,
+ sig.params().iter().map(|param| param.to_nextsolver(self.interner)).collect(),
+ sig.ret().to_nextsolver(self.interner),
+ )),
None => {
let (f, args_ty, return_ty) = self.callable_sig_from_fn_trait(ty, num_args)?;
Some((Some(f), args_ty, return_ty))
@@ -851,7 +984,7 @@ impl<'a> InferenceTable<'a> {
&mut self,
ty: &Ty,
num_args: usize,
- ) -> Option<(FnTrait, Vec<Ty>, Ty)> {
+ ) -> Option<(FnTrait, Vec<crate::next_solver::Ty<'db>>, crate::next_solver::Ty<'db>)> {
for (fn_trait_name, output_assoc_name, subtraits) in [
(FnTrait::FnOnce, sym::Output, &[FnTrait::Fn, FnTrait::FnMut][..]),
(FnTrait::AsyncFnMut, sym::CallRefFuture, &[FnTrait::AsyncFn]),
@@ -871,7 +1004,7 @@ impl<'a> InferenceTable<'a> {
ParamKind::Lifetime => unreachable!("Tuple with lifetime parameter"),
ParamKind::Const(_) => unreachable!("Tuple with const parameter"),
};
- arg_tys.push(arg.clone());
+ arg_tys.push(arg.to_nextsolver(self.interner));
arg.cast(Interner)
})
.build();
@@ -890,30 +1023,16 @@ impl<'a> InferenceTable<'a> {
.fill_with_unknown()
.build();
- let trait_env = self.trait_env.env.clone();
- let obligation = InEnvironment {
- goal: trait_ref.clone().cast(Interner),
- environment: trait_env.clone(),
- };
- let canonical = self.canonicalize(obligation.clone());
- if self.db.trait_solve(krate, self.trait_env.block, canonical.cast(Interner)).is_some()
- {
- self.register_obligation(obligation.goal);
- let return_ty = self.normalize_projection_ty(projection);
+ let goal: Goal = trait_ref.clone().cast(Interner);
+ if !self.try_obligation(goal.clone()).no_solution() {
+ self.register_obligation(goal.to_nextsolver(self.interner));
+ let return_ty =
+ self.normalize_projection_ty(projection).to_nextsolver(self.interner);
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 obligation: chalk_ir::InEnvironment<chalk_ir::Goal<Interner>> =
- InEnvironment {
- goal: trait_ref.clone().cast(Interner),
- environment: trait_env.clone(),
- };
- let canonical = self.canonicalize(obligation.clone());
- if self
- .db
- .trait_solve(krate, self.trait_env.block, canonical.cast(Interner))
- .is_some()
- {
+ let goal = trait_ref.clone().cast(Interner);
+ if !self.try_obligation(goal).no_solution() {
return Some((fn_x, arg_tys, return_ty));
}
}
@@ -947,13 +1066,38 @@ impl<'a> InferenceTable<'a> {
match ty.kind(Interner) {
TyKind::Error => self.new_type_var(),
TyKind::InferenceVar(..) => {
- let ty_resolved = self.resolve_ty_shallow(&ty);
+ let ty_resolved = self.structurally_resolve_type(&ty);
if ty_resolved.is_unknown() { self.new_type_var() } else { ty }
}
_ => ty,
}
}
+ /// Whenever you lower a user-written type, you should call this.
+ pub(crate) fn process_user_written_ty<T, U>(&mut self, ty: T) -> T
+ where
+ T: HasInterner<Interner = Interner> + TypeFoldable<Interner> + ChalkToNextSolver<'db, U>,
+ U: NextSolverToChalk<'db, T> + rustc_type_ir::TypeFoldable<DbInterner<'db>>,
+ {
+ self.process_remote_user_written_ty(ty)
+ // FIXME: Register a well-formed obligation.
+ }
+
+ /// The difference of this method from `process_user_written_ty()` is that this method doesn't register a well-formed obligation,
+ /// while `process_user_written_ty()` should (but doesn't currently).
+ pub(crate) fn process_remote_user_written_ty<T, U>(&mut self, ty: T) -> T
+ where
+ T: HasInterner<Interner = Interner> + TypeFoldable<Interner> + ChalkToNextSolver<'db, U>,
+ U: NextSolverToChalk<'db, T> + rustc_type_ir::TypeFoldable<DbInterner<'db>>,
+ {
+ let ty = self.insert_type_vars(ty);
+ // See https://github.com/rust-lang/rust/blob/cdb45c87e2cd43495379f7e867e3cc15dcee9f93/compiler/rustc_hir_typeck/src/fn_ctxt/mod.rs#L487-L495:
+ // Even though the new solver only lazily normalizes usually, here we eagerly normalize so that not everything needs
+ // to normalize before inspecting the `TyKind`.
+ // FIXME(next-solver): We should not deeply normalize here, only shallowly.
+ self.normalize_associated_types_in(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);
@@ -1032,13 +1176,16 @@ impl<'a> InferenceTable<'a> {
substitution: Substitution::from1(Interner, ty),
});
let goal = GoalData::DomainGoal(chalk_ir::DomainGoal::Holds(sized_pred)).intern(Interner);
- matches!(self.try_obligation(goal), Some(Solution::Unique(_)))
+ self.try_obligation(goal).certain()
}
}
impl fmt::Debug for InferenceTable<'_> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- f.debug_struct("InferenceTable").field("num_vars", &self.type_variable_table.len()).finish()
+ f.debug_struct("InferenceTable")
+ .field("name", &self.infer_ctxt.inner.borrow().type_variable_storage)
+ .field("fulfillment_cx", &self.fulfillment_cx)
+ .finish()
}
}
@@ -1047,11 +1194,19 @@ mod resolve {
use crate::{
ConcreteConst, Const, ConstData, ConstScalar, ConstValue, DebruijnIndex, GenericArg,
InferenceVar, Interner, Lifetime, Ty, TyVariableKind, VariableKind,
+ next_solver::mapping::NextSolverToChalk,
};
use chalk_ir::{
cast::Cast,
fold::{TypeFoldable, TypeFolder},
};
+ use rustc_type_ir::{FloatVid, IntVid, TyVid};
+
+ #[derive(Debug, Copy, Clone, PartialEq, Eq)]
+ pub(super) enum VarKind {
+ Ty(TyVariableKind),
+ Const,
+ }
#[derive(chalk_derive::FallibleTypeFolder)]
#[has_interner(Interner)]
@@ -1061,7 +1216,7 @@ mod resolve {
F: Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg,
> {
pub(super) table: &'a mut InferenceTable<'b>,
- pub(super) var_stack: &'a mut Vec<InferenceVar>,
+ pub(super) var_stack: &'a mut Vec<(InferenceVar, VarKind)>,
pub(super) fallback: F,
}
impl<F> TypeFolder<Interner> for Resolver<'_, '_, F>
@@ -1082,25 +1237,91 @@ mod resolve {
kind: TyVariableKind,
outer_binder: DebruijnIndex,
) -> Ty {
- let var = self.table.var_unification_table.inference_var_root(var);
- if self.var_stack.contains(&var) {
- // 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.var_unification_table.probe_var(var) {
- // known_ty may contain other variables that are known by now
- self.var_stack.push(var);
- let result = known_ty.fold_with(self, outer_binder);
- self.var_stack.pop();
- result.assert_ty_ref(Interner).clone()
- } 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()
+ 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 = known_ty.to_chalk(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 = known_ty.to_chalk(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 = known_ty.to_chalk(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()
+ }
+ }
}
}
@@ -1110,25 +1331,30 @@ mod resolve {
var: InferenceVar,
outer_binder: DebruijnIndex,
) -> Const {
- let var = self.table.var_unification_table.inference_var_root(var);
+ 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) {
+ 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 Some(known_ty) = self.table.var_unification_table.probe_var(var) {
+ if let Ok(known_const) = self.table.infer_ctxt.probe_const_var(vid) {
+ let known_const: Const = known_const.to_chalk(self.table.interner);
// known_ty may contain other variables that are known by now
- self.var_stack.push(var);
- let result = known_ty.fold_with(self, outer_binder);
+ self.var_stack.push((var, VarKind::Const));
+ let result = known_const.fold_with(self, outer_binder);
self.var_stack.pop();
- result.assert_const_ref(Interner).clone()
+ result
} else {
(self.fallback)(var, VariableKind::Const(ty), default, outer_binder)
.assert_const_ref(Interner)