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