1 //! Trait solving using Chalk.
2
3 use std::env::var;
4
5 use chalk_ir::{fold::TypeFoldable, DebruijnIndex, GoalData};
6 use chalk_recursive::Cache;
7 use chalk_solve::{logging_db::LoggingRustIrDatabase, rust_ir, Solver};
8
9 use base_db::CrateId;
10 use hir_def::{
11 lang_item::{LangItem, LangItemTarget},
12 BlockId, TraitId,
13 };
14 use hir_expand::name::{name, Name};
15 use stdx::panic_context;
16 use triomphe::Arc;
17
18 use crate::{
19 db::HirDatabase, infer::unify::InferenceTable, utils::UnevaluatedConstEvaluatorFolder, AliasEq,
20 AliasTy, Canonical, DomainGoal, Goal, Guidance, InEnvironment, Interner, ProjectionTy,
21 ProjectionTyExt, Solution, TraitRefExt, Ty, TyKind, WhereClause,
22 };
23
24 /// This controls how much 'time' we give the Chalk solver before giving up.
25 const CHALK_SOLVER_FUEL: i32 = 1000;
26
27 #[derive(Debug, Copy, Clone)]
28 pub(crate) struct ChalkContext<'a> {
29 pub(crate) db: &'a dyn HirDatabase,
30 pub(crate) krate: CrateId,
31 pub(crate) block: Option<BlockId>,
32 }
33
create_chalk_solver() -> chalk_recursive::RecursiveSolver<Interner>34 fn create_chalk_solver() -> chalk_recursive::RecursiveSolver<Interner> {
35 let overflow_depth =
36 var("CHALK_OVERFLOW_DEPTH").ok().and_then(|s| s.parse().ok()).unwrap_or(500);
37 let max_size = var("CHALK_SOLVER_MAX_SIZE").ok().and_then(|s| s.parse().ok()).unwrap_or(150);
38 chalk_recursive::RecursiveSolver::new(overflow_depth, max_size, Some(Cache::new()))
39 }
40
41 /// A set of clauses that we assume to be true. E.g. if we are inside this function:
42 /// ```rust
43 /// fn foo<T: Default>(t: T) {}
44 /// ```
45 /// we assume that `T: Default`.
46 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
47 pub struct TraitEnvironment {
48 pub krate: CrateId,
49 pub block: Option<BlockId>,
50 // FIXME make this a BTreeMap
51 pub(crate) traits_from_clauses: Vec<(Ty, TraitId)>,
52 pub env: chalk_ir::Environment<Interner>,
53 }
54
55 impl TraitEnvironment {
empty(krate: CrateId) -> Self56 pub fn empty(krate: CrateId) -> Self {
57 TraitEnvironment {
58 krate,
59 block: None,
60 traits_from_clauses: Vec::new(),
61 env: chalk_ir::Environment::new(Interner),
62 }
63 }
64
traits_in_scope_from_clauses(&self, ty: Ty) -> impl Iterator<Item = TraitId> + '_65 pub fn traits_in_scope_from_clauses(&self, ty: Ty) -> impl Iterator<Item = TraitId> + '_ {
66 self.traits_from_clauses
67 .iter()
68 .filter_map(move |(self_ty, trait_id)| (*self_ty == ty).then_some(*trait_id))
69 }
70 }
71
normalize_projection_query( db: &dyn HirDatabase, projection: ProjectionTy, env: Arc<TraitEnvironment>, ) -> Ty72 pub(crate) fn normalize_projection_query(
73 db: &dyn HirDatabase,
74 projection: ProjectionTy,
75 env: Arc<TraitEnvironment>,
76 ) -> Ty {
77 let mut table = InferenceTable::new(db, env);
78 let ty = table.normalize_projection_ty(projection);
79 table.resolve_completely(ty)
80 }
81
82 /// Solve a trait goal using Chalk.
trait_solve_query( db: &dyn HirDatabase, krate: CrateId, block: Option<BlockId>, goal: Canonical<InEnvironment<Goal>>, ) -> Option<Solution>83 pub(crate) fn trait_solve_query(
84 db: &dyn HirDatabase,
85 krate: CrateId,
86 block: Option<BlockId>,
87 goal: Canonical<InEnvironment<Goal>>,
88 ) -> Option<Solution> {
89 let _p = profile::span("trait_solve_query").detail(|| match &goal.value.goal.data(Interner) {
90 GoalData::DomainGoal(DomainGoal::Holds(WhereClause::Implemented(it))) => {
91 db.trait_data(it.hir_trait_id()).name.display(db.upcast()).to_string()
92 }
93 GoalData::DomainGoal(DomainGoal::Holds(WhereClause::AliasEq(_))) => "alias_eq".to_string(),
94 _ => "??".to_string(),
95 });
96 tracing::info!("trait_solve_query({:?})", goal.value.goal);
97
98 if let GoalData::DomainGoal(DomainGoal::Holds(WhereClause::AliasEq(AliasEq {
99 alias: AliasTy::Projection(projection_ty),
100 ..
101 }))) = &goal.value.goal.data(Interner)
102 {
103 if let TyKind::BoundVar(_) = projection_ty.self_type_parameter(db).kind(Interner) {
104 // Hack: don't ask Chalk to normalize with an unknown self type, it'll say that's impossible
105 return Some(Solution::Ambig(Guidance::Unknown));
106 }
107 }
108
109 // Chalk see `UnevaluatedConst` as a unique concrete value, but we see it as an alias for another const. So
110 // we should get rid of it when talking to chalk.
111 let goal = goal
112 .try_fold_with(&mut UnevaluatedConstEvaluatorFolder { db }, DebruijnIndex::INNERMOST)
113 .unwrap();
114
115 // We currently don't deal with universes (I think / hope they're not yet
116 // relevant for our use cases?)
117 let u_canonical = chalk_ir::UCanonical { canonical: goal, universes: 1 };
118 solve(db, krate, block, &u_canonical)
119 }
120
solve( db: &dyn HirDatabase, krate: CrateId, block: Option<BlockId>, goal: &chalk_ir::UCanonical<chalk_ir::InEnvironment<chalk_ir::Goal<Interner>>>, ) -> Option<chalk_solve::Solution<Interner>>121 fn solve(
122 db: &dyn HirDatabase,
123 krate: CrateId,
124 block: Option<BlockId>,
125 goal: &chalk_ir::UCanonical<chalk_ir::InEnvironment<chalk_ir::Goal<Interner>>>,
126 ) -> Option<chalk_solve::Solution<Interner>> {
127 let context = ChalkContext { db, krate, block };
128 tracing::debug!("solve goal: {:?}", goal);
129 let mut solver = create_chalk_solver();
130
131 let fuel = std::cell::Cell::new(CHALK_SOLVER_FUEL);
132
133 let should_continue = || {
134 db.unwind_if_cancelled();
135 let remaining = fuel.get();
136 fuel.set(remaining - 1);
137 if remaining == 0 {
138 tracing::debug!("fuel exhausted");
139 }
140 remaining > 0
141 };
142
143 let mut solve = || {
144 let _ctx = if is_chalk_debug() || is_chalk_print() {
145 Some(panic_context::enter(format!("solving {goal:?}")))
146 } else {
147 None
148 };
149 let solution = if is_chalk_print() {
150 let logging_db =
151 LoggingRustIrDatabaseLoggingOnDrop(LoggingRustIrDatabase::new(context));
152 solver.solve_limited(&logging_db.0, goal, &should_continue)
153 } else {
154 solver.solve_limited(&context, goal, &should_continue)
155 };
156
157 tracing::debug!("solve({:?}) => {:?}", goal, solution);
158
159 solution
160 };
161
162 // don't set the TLS for Chalk unless Chalk debugging is active, to make
163 // extra sure we only use it for debugging
164 if is_chalk_debug() {
165 crate::tls::set_current_program(db, solve)
166 } else {
167 solve()
168 }
169 }
170
171 struct LoggingRustIrDatabaseLoggingOnDrop<'a>(LoggingRustIrDatabase<Interner, ChalkContext<'a>>);
172
173 impl<'a> Drop for LoggingRustIrDatabaseLoggingOnDrop<'a> {
drop(&mut self)174 fn drop(&mut self) {
175 eprintln!("chalk program:\n{}", self.0);
176 }
177 }
178
is_chalk_debug() -> bool179 fn is_chalk_debug() -> bool {
180 std::env::var("CHALK_DEBUG").is_ok()
181 }
182
is_chalk_print() -> bool183 fn is_chalk_print() -> bool {
184 std::env::var("CHALK_PRINT").is_ok()
185 }
186
187 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
188 pub enum FnTrait {
189 // Warning: Order is important. If something implements `x` it should also implement
190 // `y` if `y <= x`.
191 FnOnce,
192 FnMut,
193 Fn,
194 }
195
196 impl FnTrait {
lang_item(self) -> LangItem197 const fn lang_item(self) -> LangItem {
198 match self {
199 FnTrait::FnOnce => LangItem::FnOnce,
200 FnTrait::FnMut => LangItem::FnMut,
201 FnTrait::Fn => LangItem::Fn,
202 }
203 }
204
to_chalk_ir(self) -> rust_ir::ClosureKind205 pub const fn to_chalk_ir(self) -> rust_ir::ClosureKind {
206 match self {
207 FnTrait::FnOnce => rust_ir::ClosureKind::FnOnce,
208 FnTrait::FnMut => rust_ir::ClosureKind::FnMut,
209 FnTrait::Fn => rust_ir::ClosureKind::Fn,
210 }
211 }
212
method_name(self) -> Name213 pub fn method_name(self) -> Name {
214 match self {
215 FnTrait::FnOnce => name!(call_once),
216 FnTrait::FnMut => name!(call_mut),
217 FnTrait::Fn => name!(call),
218 }
219 }
220
get_id(self, db: &dyn HirDatabase, krate: CrateId) -> Option<TraitId>221 pub fn get_id(self, db: &dyn HirDatabase, krate: CrateId) -> Option<TraitId> {
222 let target = db.lang_item(krate, self.lang_item())?;
223 match target {
224 LangItemTarget::Trait(t) => Some(t),
225 _ => None,
226 }
227 }
228 }
229