aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir_ty/src/traits.rs
diff options
context:
space:
mode:
Diffstat (limited to 'crates/ra_hir_ty/src/traits.rs')
-rw-r--r--crates/ra_hir_ty/src/traits.rs328
1 files changed, 328 insertions, 0 deletions
diff --git a/crates/ra_hir_ty/src/traits.rs b/crates/ra_hir_ty/src/traits.rs
new file mode 100644
index 000000000..76189a60b
--- /dev/null
+++ b/crates/ra_hir_ty/src/traits.rs
@@ -0,0 +1,328 @@
1//! Trait solving using Chalk.
2use std::sync::{Arc, Mutex};
3
4use chalk_ir::{cast::Cast, family::ChalkIr};
5use hir_def::{expr::ExprId, DefWithBodyId, ImplId, TraitId, TypeAliasId};
6use log::debug;
7use ra_db::{impl_intern_key, salsa, CrateId};
8use ra_prof::profile;
9use rustc_hash::FxHashSet;
10
11use crate::db::HirDatabase;
12
13use super::{Canonical, GenericPredicate, HirDisplay, ProjectionTy, TraitRef, Ty, TypeWalk};
14
15use self::chalk::{from_chalk, ToChalk};
16
17pub(crate) mod chalk;
18
19#[derive(Debug, Clone)]
20pub struct TraitSolver {
21 krate: CrateId,
22 inner: Arc<Mutex<chalk_solve::Solver<ChalkIr>>>,
23}
24
25/// We need eq for salsa
26impl PartialEq for TraitSolver {
27 fn eq(&self, other: &TraitSolver) -> bool {
28 Arc::ptr_eq(&self.inner, &other.inner)
29 }
30}
31
32impl Eq for TraitSolver {}
33
34impl TraitSolver {
35 fn solve(
36 &self,
37 db: &impl HirDatabase,
38 goal: &chalk_ir::UCanonical<chalk_ir::InEnvironment<chalk_ir::Goal<ChalkIr>>>,
39 ) -> Option<chalk_solve::Solution<ChalkIr>> {
40 let context = ChalkContext { db, krate: self.krate };
41 debug!("solve goal: {:?}", goal);
42 let mut solver = match self.inner.lock() {
43 Ok(it) => it,
44 // Our cancellation works via unwinding, but, as chalk is not
45 // panic-safe, we need to make sure to propagate the cancellation.
46 // Ideally, we should also make chalk panic-safe.
47 Err(_) => ra_db::Canceled::throw(),
48 };
49 let solution = solver.solve(&context, goal);
50 debug!("solve({:?}) => {:?}", goal, solution);
51 solution
52 }
53}
54
55/// This controls the maximum size of types Chalk considers. If we set this too
56/// high, we can run into slow edge cases; if we set it too low, Chalk won't
57/// find some solutions.
58const CHALK_SOLVER_MAX_SIZE: usize = 4;
59
60#[derive(Debug, Copy, Clone)]
61struct ChalkContext<'a, DB> {
62 db: &'a DB,
63 krate: CrateId,
64}
65
66pub(crate) fn trait_solver_query(
67 db: &(impl HirDatabase + salsa::Database),
68 krate: CrateId,
69) -> TraitSolver {
70 db.salsa_runtime().report_untracked_read();
71 // krate parameter is just so we cache a unique solver per crate
72 let solver_choice = chalk_solve::SolverChoice::SLG { max_size: CHALK_SOLVER_MAX_SIZE };
73 debug!("Creating new solver for crate {:?}", krate);
74 TraitSolver { krate, inner: Arc::new(Mutex::new(solver_choice.into_solver())) }
75}
76
77/// Collects impls for the given trait in the whole dependency tree of `krate`.
78pub(crate) fn impls_for_trait_query(
79 db: &impl HirDatabase,
80 krate: CrateId,
81 trait_: TraitId,
82) -> Arc<[ImplId]> {
83 let mut impls = FxHashSet::default();
84 // We call the query recursively here. On the one hand, this means we can
85 // reuse results from queries for different crates; on the other hand, this
86 // will only ever get called for a few crates near the root of the tree (the
87 // ones the user is editing), so this may actually be a waste of memory. I'm
88 // doing it like this mainly for simplicity for now.
89 for dep in db.crate_graph().dependencies(krate) {
90 impls.extend(db.impls_for_trait(dep.crate_id, trait_).iter());
91 }
92 let crate_impl_blocks = db.impls_in_crate(krate);
93 impls.extend(crate_impl_blocks.lookup_impl_blocks_for_trait(trait_));
94 impls.into_iter().collect()
95}
96
97/// A set of clauses that we assume to be true. E.g. if we are inside this function:
98/// ```rust
99/// fn foo<T: Default>(t: T) {}
100/// ```
101/// we assume that `T: Default`.
102#[derive(Clone, Debug, PartialEq, Eq, Hash)]
103pub struct TraitEnvironment {
104 pub predicates: Vec<GenericPredicate>,
105}
106
107impl TraitEnvironment {
108 /// Returns trait refs with the given self type which are supposed to hold
109 /// in this trait env. E.g. if we are in `foo<T: SomeTrait>()`, this will
110 /// find that `T: SomeTrait` if we call it for `T`.
111 pub(crate) fn trait_predicates_for_self_ty<'a>(
112 &'a self,
113 ty: &'a Ty,
114 ) -> impl Iterator<Item = &'a TraitRef> + 'a {
115 self.predicates.iter().filter_map(move |pred| match pred {
116 GenericPredicate::Implemented(tr) if tr.self_ty() == ty => Some(tr),
117 _ => None,
118 })
119 }
120}
121
122/// Something (usually a goal), along with an environment.
123#[derive(Clone, Debug, PartialEq, Eq, Hash)]
124pub struct InEnvironment<T> {
125 pub environment: Arc<TraitEnvironment>,
126 pub value: T,
127}
128
129impl<T> InEnvironment<T> {
130 pub fn new(environment: Arc<TraitEnvironment>, value: T) -> InEnvironment<T> {
131 InEnvironment { environment, value }
132 }
133}
134
135/// Something that needs to be proven (by Chalk) during type checking, e.g. that
136/// a certain type implements a certain trait. Proving the Obligation might
137/// result in additional information about inference variables.
138#[derive(Clone, Debug, PartialEq, Eq, Hash)]
139pub enum Obligation {
140 /// Prove that a certain type implements a trait (the type is the `Self` type
141 /// parameter to the `TraitRef`).
142 Trait(TraitRef),
143 Projection(ProjectionPredicate),
144}
145
146impl Obligation {
147 pub fn from_predicate(predicate: GenericPredicate) -> Option<Obligation> {
148 match predicate {
149 GenericPredicate::Implemented(trait_ref) => Some(Obligation::Trait(trait_ref)),
150 GenericPredicate::Projection(projection_pred) => {
151 Some(Obligation::Projection(projection_pred))
152 }
153 GenericPredicate::Error => None,
154 }
155 }
156}
157
158#[derive(Clone, Debug, PartialEq, Eq, Hash)]
159pub struct ProjectionPredicate {
160 pub projection_ty: ProjectionTy,
161 pub ty: Ty,
162}
163
164impl TypeWalk for ProjectionPredicate {
165 fn walk(&self, f: &mut impl FnMut(&Ty)) {
166 self.projection_ty.walk(f);
167 self.ty.walk(f);
168 }
169
170 fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
171 self.projection_ty.walk_mut_binders(f, binders);
172 self.ty.walk_mut_binders(f, binders);
173 }
174}
175
176/// Solve a trait goal using Chalk.
177pub(crate) fn trait_solve_query(
178 db: &impl HirDatabase,
179 krate: CrateId,
180 goal: Canonical<InEnvironment<Obligation>>,
181) -> Option<Solution> {
182 let _p = profile("trait_solve_query");
183 debug!("trait_solve_query({})", goal.value.value.display(db));
184
185 if let Obligation::Projection(pred) = &goal.value.value {
186 if let Ty::Bound(_) = &pred.projection_ty.parameters[0] {
187 // Hack: don't ask Chalk to normalize with an unknown self type, it'll say that's impossible
188 return Some(Solution::Ambig(Guidance::Unknown));
189 }
190 }
191
192 let canonical = goal.to_chalk(db).cast();
193
194 // We currently don't deal with universes (I think / hope they're not yet
195 // relevant for our use cases?)
196 let u_canonical = chalk_ir::UCanonical { canonical, universes: 1 };
197 let solution = db.trait_solver(krate).solve(db, &u_canonical);
198 solution.map(|solution| solution_from_chalk(db, solution))
199}
200
201fn solution_from_chalk(
202 db: &impl HirDatabase,
203 solution: chalk_solve::Solution<ChalkIr>,
204) -> Solution {
205 let convert_subst = |subst: chalk_ir::Canonical<chalk_ir::Substitution<ChalkIr>>| {
206 let value = subst
207 .value
208 .parameters
209 .into_iter()
210 .map(|p| {
211 let ty = match p {
212 chalk_ir::Parameter(chalk_ir::ParameterKind::Ty(ty)) => from_chalk(db, ty),
213 chalk_ir::Parameter(chalk_ir::ParameterKind::Lifetime(_)) => unimplemented!(),
214 };
215 ty
216 })
217 .collect();
218 let result = Canonical { value, num_vars: subst.binders.len() };
219 SolutionVariables(result)
220 };
221 match solution {
222 chalk_solve::Solution::Unique(constr_subst) => {
223 let subst = chalk_ir::Canonical {
224 value: constr_subst.value.subst,
225 binders: constr_subst.binders,
226 };
227 Solution::Unique(convert_subst(subst))
228 }
229 chalk_solve::Solution::Ambig(chalk_solve::Guidance::Definite(subst)) => {
230 Solution::Ambig(Guidance::Definite(convert_subst(subst)))
231 }
232 chalk_solve::Solution::Ambig(chalk_solve::Guidance::Suggested(subst)) => {
233 Solution::Ambig(Guidance::Suggested(convert_subst(subst)))
234 }
235 chalk_solve::Solution::Ambig(chalk_solve::Guidance::Unknown) => {
236 Solution::Ambig(Guidance::Unknown)
237 }
238 }
239}
240
241#[derive(Clone, Debug, PartialEq, Eq)]
242pub struct SolutionVariables(pub Canonical<Vec<Ty>>);
243
244#[derive(Clone, Debug, PartialEq, Eq)]
245/// A (possible) solution for a proposed goal.
246pub enum Solution {
247 /// The goal indeed holds, and there is a unique value for all existential
248 /// variables.
249 Unique(SolutionVariables),
250
251 /// The goal may be provable in multiple ways, but regardless we may have some guidance
252 /// for type inference. In this case, we don't return any lifetime
253 /// constraints, since we have not "committed" to any particular solution
254 /// yet.
255 Ambig(Guidance),
256}
257
258#[derive(Clone, Debug, PartialEq, Eq)]
259/// When a goal holds ambiguously (e.g., because there are multiple possible
260/// solutions), we issue a set of *guidance* back to type inference.
261pub enum Guidance {
262 /// The existential variables *must* have the given values if the goal is
263 /// ever to hold, but that alone isn't enough to guarantee the goal will
264 /// actually hold.
265 Definite(SolutionVariables),
266
267 /// There are multiple plausible values for the existentials, but the ones
268 /// here are suggested as the preferred choice heuristically. These should
269 /// be used for inference fallback only.
270 Suggested(SolutionVariables),
271
272 /// There's no useful information to feed back to type inference
273 Unknown,
274}
275
276#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
277pub enum FnTrait {
278 FnOnce,
279 FnMut,
280 Fn,
281}
282
283impl FnTrait {
284 fn lang_item_name(self) -> &'static str {
285 match self {
286 FnTrait::FnOnce => "fn_once",
287 FnTrait::FnMut => "fn_mut",
288 FnTrait::Fn => "fn",
289 }
290 }
291}
292
293#[derive(Debug, Clone, PartialEq, Eq, Hash)]
294pub struct ClosureFnTraitImplData {
295 def: DefWithBodyId,
296 expr: ExprId,
297 fn_trait: FnTrait,
298}
299
300/// An impl. Usually this comes from an impl block, but some built-in types get
301/// synthetic impls.
302#[derive(Debug, Clone, PartialEq, Eq, Hash)]
303pub enum Impl {
304 /// A normal impl from an impl block.
305 ImplBlock(ImplId),
306 /// Closure types implement the Fn traits synthetically.
307 ClosureFnTraitImpl(ClosureFnTraitImplData),
308}
309/// This exists just for Chalk, because our ImplIds are only unique per module.
310#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
311pub struct GlobalImplId(salsa::InternId);
312impl_intern_key!(GlobalImplId);
313
314/// An associated type value. Usually this comes from a `type` declaration
315/// inside an impl block, but for built-in impls we have to synthesize it.
316/// (We only need this because Chalk wants a unique ID for each of these.)
317#[derive(Debug, Clone, PartialEq, Eq, Hash)]
318pub enum AssocTyValue {
319 /// A normal assoc type value from an impl block.
320 TypeAlias(TypeAliasId),
321 /// The output type of the Fn trait implementation.
322 ClosureFnTraitImplOutput(ClosureFnTraitImplData),
323}
324/// This exists just for Chalk, because it needs a unique ID for each associated
325/// type value in an impl (even synthetic ones).
326#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
327pub struct AssocTyValueId(salsa::InternId);
328impl_intern_key!(AssocTyValueId);