Unnamed repository; edit this file 'description' to name the repository.
Diffstat (limited to 'crates/hir-ty/src/traits.rs')
| -rw-r--r-- | crates/hir-ty/src/traits.rs | 301 |
1 files changed, 212 insertions, 89 deletions
diff --git a/crates/hir-ty/src/traits.rs b/crates/hir-ty/src/traits.rs index 08b9d242e7..8095d702be 100644 --- a/crates/hir-ty/src/traits.rs +++ b/crates/hir-ty/src/traits.rs @@ -1,43 +1,38 @@ //! Trait solving using Chalk. use core::fmt; -use std::env::var; +use std::hash::Hash; use chalk_ir::{DebruijnIndex, GoalData, fold::TypeFoldable}; -use chalk_recursive::Cache; -use chalk_solve::{Solver, logging_db::LoggingRustIrDatabase, rust_ir}; use base_db::Crate; use hir_def::{BlockId, TraitId, lang_item::LangItem}; use hir_expand::name::Name; use intern::sym; +use rustc_next_trait_solver::solve::{HasChanged, SolverDelegateEvalExt}; +use rustc_type_ir::{ + InferCtxtLike, TypingMode, + inherent::{SliceLike, Span as _}, + solve::Certainty, +}; use span::Edition; -use stdx::{never, panic_context}; +use stdx::never; use triomphe::Arc; use crate::{ - AliasEq, AliasTy, Canonical, DomainGoal, Goal, Guidance, InEnvironment, Interner, ProjectionTy, - ProjectionTyExt, Solution, TraitRefExt, Ty, TyKind, TypeFlags, WhereClause, db::HirDatabase, - infer::unify::InferenceTable, utils::UnevaluatedConstEvaluatorFolder, + AliasEq, AliasTy, Canonical, DomainGoal, Goal, InEnvironment, Interner, ProjectionTy, + ProjectionTyExt, TraitRefExt, Ty, TyKind, TypeFlags, WhereClause, + db::HirDatabase, + infer::unify::InferenceTable, + next_solver::{ + DbInterner, GenericArg, Predicate, SolverContext, Span, + infer::{DbInternerInferExt, InferCtxt}, + mapping::{ChalkToNextSolver, convert_canonical_args_for_result}, + util::mini_canonicalize, + }, + utils::UnevaluatedConstEvaluatorFolder, }; -/// This controls how much 'time' we give the Chalk solver before giving up. -const CHALK_SOLVER_FUEL: i32 = 1000; - -#[derive(Debug, Copy, Clone)] -pub(crate) struct ChalkContext<'a> { - pub(crate) db: &'a dyn HirDatabase, - pub(crate) krate: Crate, - pub(crate) block: Option<BlockId>, -} - -fn create_chalk_solver() -> chalk_recursive::RecursiveSolver<Interner> { - let overflow_depth = - var("CHALK_OVERFLOW_DEPTH").ok().and_then(|s| s.parse().ok()).unwrap_or(500); - let max_size = var("CHALK_SOLVER_MAX_SIZE").ok().and_then(|s| s.parse().ok()).unwrap_or(150); - chalk_recursive::RecursiveSolver::new(overflow_depth, max_size, Some(Cache::new())) -} - /// A set of clauses that we assume to be true. E.g. if we are inside this function: /// ```rust /// fn foo<T: Default>(t: T) {} @@ -103,13 +98,43 @@ pub(crate) fn normalize_projection_query( table.resolve_completely(ty) } +fn identity_subst( + binders: chalk_ir::CanonicalVarKinds<Interner>, +) -> chalk_ir::Canonical<chalk_ir::Substitution<Interner>> { + let identity_subst = chalk_ir::Substitution::from_iter( + Interner, + binders.iter(Interner).enumerate().map(|(index, c)| { + let index_db = chalk_ir::BoundVar::new(DebruijnIndex::INNERMOST, index); + match &c.kind { + chalk_ir::VariableKind::Ty(_) => { + chalk_ir::GenericArgData::Ty(TyKind::BoundVar(index_db).intern(Interner)) + .intern(Interner) + } + chalk_ir::VariableKind::Lifetime => chalk_ir::GenericArgData::Lifetime( + chalk_ir::LifetimeData::BoundVar(index_db).intern(Interner), + ) + .intern(Interner), + chalk_ir::VariableKind::Const(ty) => chalk_ir::GenericArgData::Const( + chalk_ir::ConstData { + ty: ty.clone(), + value: chalk_ir::ConstValue::BoundVar(index_db), + } + .intern(Interner), + ) + .intern(Interner), + } + }), + ); + chalk_ir::Canonical { binders, value: identity_subst } +} + /// Solve a trait goal using Chalk. pub(crate) fn trait_solve_query( db: &dyn HirDatabase, krate: Crate, block: Option<BlockId>, goal: Canonical<InEnvironment<Goal>>, -) -> Option<Solution> { +) -> NextTraitSolveResult { let _p = tracing::info_span!("trait_solve_query", detail = ?match &goal.value.goal.data(Interner) { GoalData::DomainGoal(DomainGoal::Holds(WhereClause::Implemented(it))) => db .trait_signature(it.hir_trait_id()) @@ -128,7 +153,7 @@ pub(crate) fn trait_solve_query( && let TyKind::BoundVar(_) = projection_ty.self_type_parameter(db).kind(Interner) { // Hack: don't ask Chalk to normalize with an unknown self type, it'll say that's impossible - return Some(Solution::Ambig(Guidance::Unknown)); + return NextTraitSolveResult::Uncertain(identity_subst(goal.binders.clone())); } // Chalk see `UnevaluatedConst` as a unique concrete value, but we see it as an alias for another const. So @@ -139,71 +164,183 @@ pub(crate) fn trait_solve_query( // We currently don't deal with universes (I think / hope they're not yet // relevant for our use cases?) - let u_canonical = chalk_ir::UCanonical { canonical: goal, universes: 1 }; - solve(db, krate, block, &u_canonical) + next_trait_solve(db, krate, block, goal) } -fn solve( - db: &dyn HirDatabase, +fn solve_nextsolver<'db>( + db: &'db dyn HirDatabase, krate: Crate, block: Option<BlockId>, goal: &chalk_ir::UCanonical<chalk_ir::InEnvironment<chalk_ir::Goal<Interner>>>, -) -> Option<chalk_solve::Solution<Interner>> { - let _p = tracing::info_span!("solve", ?krate, ?block).entered(); - let context = ChalkContext { db, krate, block }; - tracing::debug!("solve goal: {:?}", goal); - let mut solver = create_chalk_solver(); - - let fuel = std::cell::Cell::new(CHALK_SOLVER_FUEL); - - let should_continue = || { - db.unwind_if_revision_cancelled(); - let remaining = fuel.get(); - fuel.set(remaining - 1); - if remaining == 0 { - tracing::debug!("fuel exhausted"); +) -> Result< + (HasChanged, Certainty, rustc_type_ir::Canonical<DbInterner<'db>, Vec<GenericArg<'db>>>), + rustc_type_ir::solve::NoSolution, +> { + // FIXME: should use analysis_in_body, but that needs GenericDefId::Block + let context = SolverContext( + DbInterner::new_with(db, Some(krate), block) + .infer_ctxt() + .build(TypingMode::non_body_analysis()), + ); + + match goal.canonical.value.goal.data(Interner) { + // FIXME: args here should be...what? not empty + GoalData::All(goals) if goals.is_empty(Interner) => { + return Ok((HasChanged::No, Certainty::Yes, mini_canonicalize(context, vec![]))); } - remaining > 0 - }; + _ => {} + } - let mut solve = || { - let _ctx = if is_chalk_debug() || is_chalk_print() { - Some(panic_context::enter(format!("solving {goal:?}"))) - } else { - None - }; - let solution = if is_chalk_print() { - let logging_db = - LoggingRustIrDatabaseLoggingOnDrop(LoggingRustIrDatabase::new(context)); - solver.solve_limited(&logging_db.0, goal, &should_continue) - } else { - solver.solve_limited(&context, goal, &should_continue) - }; - - tracing::debug!("solve({:?}) => {:?}", goal, solution); - - solution - }; + let goal = goal.canonical.to_nextsolver(context.cx()); + tracing::info!(?goal); + + let (goal, var_values) = context.instantiate_canonical(&goal); + tracing::info!(?var_values); + + let res = context.evaluate_root_goal(goal, Span::dummy(), None); + + let vars = + var_values.var_values.iter().map(|g| context.0.resolve_vars_if_possible(g)).collect(); + let canonical_var_values = mini_canonicalize(context, vars); + + let res = res.map(|r| (r.has_changed, r.certainty, canonical_var_values)); + + tracing::debug!("solve_nextsolver({:?}) => {:?}", goal, res); + + res +} - // don't set the TLS for Chalk unless Chalk debugging is active, to make - // extra sure we only use it for debugging - if is_chalk_debug() { crate::tls::set_current_program(db, solve) } else { solve() } +#[derive(Clone, Debug, PartialEq)] +pub enum NextTraitSolveResult { + Certain(chalk_ir::Canonical<chalk_ir::ConstrainedSubst<Interner>>), + Uncertain(chalk_ir::Canonical<chalk_ir::Substitution<Interner>>), + NoSolution, } -struct LoggingRustIrDatabaseLoggingOnDrop<'a>(LoggingRustIrDatabase<Interner, ChalkContext<'a>>); +impl NextTraitSolveResult { + pub fn no_solution(&self) -> bool { + matches!(self, NextTraitSolveResult::NoSolution) + } -impl Drop for LoggingRustIrDatabaseLoggingOnDrop<'_> { - fn drop(&mut self) { - tracing::info!("chalk program:\n{}", self.0); + pub fn certain(&self) -> bool { + matches!(self, NextTraitSolveResult::Certain(..)) + } + + pub fn uncertain(&self) -> bool { + matches!(self, NextTraitSolveResult::Uncertain(..)) } } -fn is_chalk_debug() -> bool { - std::env::var("CHALK_DEBUG").is_ok() +pub fn next_trait_solve( + db: &dyn HirDatabase, + krate: Crate, + block: Option<BlockId>, + goal: Canonical<InEnvironment<Goal>>, +) -> NextTraitSolveResult { + let detail = match &goal.value.goal.data(Interner) { + GoalData::DomainGoal(DomainGoal::Holds(WhereClause::Implemented(it))) => { + db.trait_signature(it.hir_trait_id()).name.display(db, Edition::LATEST).to_string() + } + GoalData::DomainGoal(DomainGoal::Holds(WhereClause::AliasEq(_))) => "alias_eq".to_owned(), + _ => "??".to_owned(), + }; + let _p = tracing::info_span!("next_trait_solve", ?detail).entered(); + tracing::info!("next_trait_solve({:?})", goal.value.goal); + + if let GoalData::DomainGoal(DomainGoal::Holds(WhereClause::AliasEq(AliasEq { + alias: AliasTy::Projection(projection_ty), + .. + }))) = &goal.value.goal.data(Interner) + && let TyKind::BoundVar(_) = projection_ty.self_type_parameter(db).kind(Interner) + { + // Hack: don't ask Chalk to normalize with an unknown self type, it'll say that's impossible + // FIXME + return NextTraitSolveResult::Uncertain(identity_subst(goal.binders.clone())); + } + + // Chalk see `UnevaluatedConst` as a unique concrete value, but we see it as an alias for another const. So + // we should get rid of it when talking to chalk. + let goal = goal + .try_fold_with(&mut UnevaluatedConstEvaluatorFolder { db }, DebruijnIndex::INNERMOST) + .unwrap(); + + // We currently don't deal with universes (I think / hope they're not yet + // relevant for our use cases?) + let u_canonical = chalk_ir::UCanonical { canonical: goal, universes: 1 }; + tracing::info!(?u_canonical); + + let next_solver_res = solve_nextsolver(db, krate, block, &u_canonical); + + match next_solver_res { + Err(_) => NextTraitSolveResult::NoSolution, + Ok((_, Certainty::Yes, args)) => NextTraitSolveResult::Certain( + convert_canonical_args_for_result(DbInterner::new_with(db, Some(krate), block), args), + ), + Ok((_, Certainty::Maybe { .. }, args)) => { + let subst = convert_canonical_args_for_result( + DbInterner::new_with(db, Some(krate), block), + args, + ); + NextTraitSolveResult::Uncertain(chalk_ir::Canonical { + binders: subst.binders, + value: subst.value.subst, + }) + } + } } -fn is_chalk_print() -> bool { - std::env::var("CHALK_PRINT").is_ok() +pub fn next_trait_solve_canonical_in_ctxt<'db>( + infer_ctxt: &InferCtxt<'db>, + goal: crate::next_solver::Canonical<'db, crate::next_solver::Goal<'db, Predicate<'db>>>, +) -> NextTraitSolveResult { + let context = SolverContext(infer_ctxt.clone()); + + tracing::info!(?goal); + + let (goal, var_values) = context.instantiate_canonical(&goal); + tracing::info!(?var_values); + + let res = context.evaluate_root_goal(goal, Span::dummy(), None); + + let vars = + var_values.var_values.iter().map(|g| context.0.resolve_vars_if_possible(g)).collect(); + let canonical_var_values = mini_canonicalize(context, vars); + + let res = res.map(|r| (r.has_changed, r.certainty, canonical_var_values)); + + tracing::debug!("solve_nextsolver({:?}) => {:?}", goal, res); + + match res { + Err(_) => NextTraitSolveResult::NoSolution, + Ok((_, Certainty::Yes, args)) => NextTraitSolveResult::Certain( + convert_canonical_args_for_result(infer_ctxt.interner, args), + ), + Ok((_, Certainty::Maybe { .. }, args)) => { + let subst = convert_canonical_args_for_result(infer_ctxt.interner, args); + NextTraitSolveResult::Uncertain(chalk_ir::Canonical { + binders: subst.binders, + value: subst.value.subst, + }) + } + } +} + +/// Solve a trait goal using Chalk. +pub fn next_trait_solve_in_ctxt<'db, 'a>( + infer_ctxt: &'a InferCtxt<'db>, + goal: crate::next_solver::Goal<'db, crate::next_solver::Predicate<'db>>, +) -> Result<(HasChanged, Certainty), rustc_type_ir::solve::NoSolution> { + tracing::info!(?goal); + + let context = <&SolverContext<'db>>::from(infer_ctxt); + + let res = context.evaluate_root_goal(goal, Span::dummy(), None); + + let res = res.map(|r| (r.has_changed, r.certainty)); + + tracing::debug!("solve_nextsolver({:?}) => {:?}", goal, res); + + res } #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)] @@ -267,15 +404,6 @@ impl FnTrait { } } - pub const fn to_chalk_ir(self) -> rust_ir::ClosureKind { - // Chalk doesn't support async fn traits. - match self { - FnTrait::AsyncFnOnce | FnTrait::FnOnce => rust_ir::ClosureKind::FnOnce, - FnTrait::AsyncFnMut | FnTrait::FnMut => rust_ir::ClosureKind::FnMut, - FnTrait::AsyncFn | FnTrait::Fn => rust_ir::ClosureKind::Fn, - } - } - pub fn method_name(self) -> Name { match self { FnTrait::FnOnce => Name::new_symbol_root(sym::call_once), @@ -290,9 +418,4 @@ impl FnTrait { pub fn get_id(self, db: &dyn HirDatabase, krate: Crate) -> Option<TraitId> { self.lang_item().resolve_trait(db, krate) } - - #[inline] - pub(crate) fn is_async(self) -> bool { - matches!(self, FnTrait::AsyncFn | FnTrait::AsyncFnMut | FnTrait::AsyncFnOnce) - } } |