1 //! Trait solving using Chalk.
3 use std::{env::var, sync::Arc};
5 use chalk_ir::GoalData;
6 use chalk_recursive::Cache;
7 use chalk_solve::{logging_db::LoggingRustIrDatabase, Solver};
10 use hir_def::{lang_item::LangItemTarget, TraitId};
11 use stdx::panic_context;
15 db::HirDatabase, infer::unify::InferenceTable, AliasEq, AliasTy, Canonical, DomainGoal, Goal,
16 Guidance, InEnvironment, Interner, ProjectionTy, Solution, TraitRefExt, Ty, TyKind,
20 /// This controls how much 'time' we give the Chalk solver before giving up.
21 const CHALK_SOLVER_FUEL: i32 = 100;
23 #[derive(Debug, Copy, Clone)]
24 pub(crate) struct ChalkContext<'a> {
25 pub(crate) db: &'a dyn HirDatabase,
26 pub(crate) krate: CrateId,
29 fn create_chalk_solver() -> chalk_recursive::RecursiveSolver<Interner> {
31 var("CHALK_OVERFLOW_DEPTH").ok().and_then(|s| s.parse().ok()).unwrap_or(500);
32 let max_size = var("CHALK_SOLVER_MAX_SIZE").ok().and_then(|s| s.parse().ok()).unwrap_or(150);
33 chalk_recursive::RecursiveSolver::new(overflow_depth, max_size, Some(Cache::new()))
36 /// A set of clauses that we assume to be true. E.g. if we are inside this function:
38 /// fn foo<T: Default>(t: T) {}
40 /// we assume that `T: Default`.
41 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
42 pub struct TraitEnvironment {
44 // FIXME make this a BTreeMap
45 pub(crate) traits_from_clauses: Vec<(Ty, TraitId)>,
46 pub env: chalk_ir::Environment<Interner>,
49 impl TraitEnvironment {
50 pub fn empty(krate: CrateId) -> Self {
53 traits_from_clauses: Vec::new(),
54 env: chalk_ir::Environment::new(Interner),
58 pub fn traits_in_scope_from_clauses<'a>(
61 ) -> impl Iterator<Item = TraitId> + 'a {
62 self.traits_from_clauses
64 .filter_map(move |(self_ty, trait_id)| (*self_ty == ty).then(|| *trait_id))
68 pub(crate) fn normalize_projection_query(
70 projection: ProjectionTy,
71 env: Arc<TraitEnvironment>,
73 let mut table = InferenceTable::new(db, env.clone());
74 let ty = table.normalize_projection_ty(projection);
75 Some(table.resolve_completely(ty))
78 /// Solve a trait goal using Chalk.
79 pub(crate) fn trait_solve_query(
82 goal: Canonical<InEnvironment<Goal>>,
83 ) -> Option<Solution> {
84 let _p = profile::span("trait_solve_query").detail(|| match &goal.value.goal.data(Interner) {
85 GoalData::DomainGoal(DomainGoal::Holds(WhereClause::Implemented(it))) => {
86 db.trait_data(it.hir_trait_id()).name.to_string()
88 GoalData::DomainGoal(DomainGoal::Holds(WhereClause::AliasEq(_))) => "alias_eq".to_string(),
89 _ => "??".to_string(),
91 tracing::info!("trait_solve_query({:?})", goal.value.goal);
93 if let GoalData::DomainGoal(DomainGoal::Holds(WhereClause::AliasEq(AliasEq {
94 alias: AliasTy::Projection(projection_ty),
96 }))) = &goal.value.goal.data(Interner)
98 if let TyKind::BoundVar(_) = projection_ty.self_type_parameter(Interner).kind(Interner) {
99 // Hack: don't ask Chalk to normalize with an unknown self type, it'll say that's impossible
100 return Some(Solution::Ambig(Guidance::Unknown));
104 // We currently don't deal with universes (I think / hope they're not yet
105 // relevant for our use cases?)
106 let u_canonical = chalk_ir::UCanonical { canonical: goal, universes: 1 };
107 solve(db, krate, &u_canonical)
111 db: &dyn HirDatabase,
113 goal: &chalk_ir::UCanonical<chalk_ir::InEnvironment<chalk_ir::Goal<Interner>>>,
114 ) -> Option<chalk_solve::Solution<Interner>> {
115 let context = ChalkContext { db, krate };
116 tracing::debug!("solve goal: {:?}", goal);
117 let mut solver = create_chalk_solver();
119 let fuel = std::cell::Cell::new(CHALK_SOLVER_FUEL);
121 let should_continue = || {
122 db.unwind_if_cancelled();
123 let remaining = fuel.get();
124 fuel.set(remaining - 1);
126 tracing::debug!("fuel exhausted");
132 let _ctx = if is_chalk_debug() || is_chalk_print() {
133 Some(panic_context::enter(format!("solving {:?}", goal)))
137 let solution = if is_chalk_print() {
139 LoggingRustIrDatabaseLoggingOnDrop(LoggingRustIrDatabase::new(context));
140 solver.solve_limited(&logging_db.0, goal, &should_continue)
142 solver.solve_limited(&context, goal, &should_continue)
145 tracing::debug!("solve({:?}) => {:?}", goal, solution);
150 // don't set the TLS for Chalk unless Chalk debugging is active, to make
151 // extra sure we only use it for debugging
152 if is_chalk_debug() {
153 crate::tls::set_current_program(db, solve)
159 struct LoggingRustIrDatabaseLoggingOnDrop<'a>(LoggingRustIrDatabase<Interner, ChalkContext<'a>>);
161 impl<'a> Drop for LoggingRustIrDatabaseLoggingOnDrop<'a> {
163 eprintln!("chalk program:\n{}", self.0);
167 fn is_chalk_debug() -> bool {
168 std::env::var("CHALK_DEBUG").is_ok()
171 fn is_chalk_print() -> bool {
172 std::env::var("CHALK_PRINT").is_ok()
175 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
183 const fn lang_item_name(self) -> &'static str {
185 FnTrait::FnOnce => "fn_once",
186 FnTrait::FnMut => "fn_mut",
191 pub fn get_id(&self, db: &dyn HirDatabase, krate: CrateId) -> Option<TraitId> {
192 let target = db.lang_item(krate, SmolStr::new_inline(self.lang_item_name()))?;
194 LangItemTarget::TraitId(t) => Some(t),