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.rs273
1 files changed, 0 insertions, 273 deletions
diff --git a/crates/ra_hir_ty/src/traits.rs b/crates/ra_hir_ty/src/traits.rs
deleted file mode 100644
index 3f6d2cf35..000000000
--- a/crates/ra_hir_ty/src/traits.rs
+++ /dev/null
@@ -1,273 +0,0 @@
1//! Trait solving using Chalk.
2use std::sync::Arc;
3
4use chalk_ir::cast::Cast;
5use chalk_solve::Solver;
6use hir_def::{lang_item::LangItemTarget, TraitId};
7use ra_db::CrateId;
8use ra_prof::profile;
9
10use crate::{db::HirDatabase, DebruijnIndex, Substs};
11
12use super::{Canonical, GenericPredicate, HirDisplay, ProjectionTy, TraitRef, Ty, TypeWalk};
13
14use self::chalk::{from_chalk, Interner, ToChalk};
15
16pub(crate) mod chalk;
17
18// This controls the maximum size of types Chalk considers. If we set this too
19// high, we can run into slow edge cases; if we set it too low, Chalk won't
20// find some solutions.
21// FIXME this is currently hardcoded in the recursive solver
22// const CHALK_SOLVER_MAX_SIZE: usize = 10;
23
24/// This controls how much 'time' we give the Chalk solver before giving up.
25const CHALK_SOLVER_FUEL: i32 = 100;
26
27#[derive(Debug, Copy, Clone)]
28struct ChalkContext<'a> {
29 db: &'a dyn HirDatabase,
30 krate: CrateId,
31}
32
33fn create_chalk_solver() -> chalk_recursive::RecursiveSolver<Interner> {
34 let overflow_depth = 100;
35 let caching_enabled = true;
36 chalk_recursive::RecursiveSolver::new(overflow_depth, caching_enabled)
37}
38
39/// A set of clauses that we assume to be true. E.g. if we are inside this function:
40/// ```rust
41/// fn foo<T: Default>(t: T) {}
42/// ```
43/// we assume that `T: Default`.
44#[derive(Clone, Debug, PartialEq, Eq, Hash)]
45pub struct TraitEnvironment {
46 pub predicates: Vec<GenericPredicate>,
47}
48
49impl TraitEnvironment {
50 /// Returns trait refs with the given self type which are supposed to hold
51 /// in this trait env. E.g. if we are in `foo<T: SomeTrait>()`, this will
52 /// find that `T: SomeTrait` if we call it for `T`.
53 pub(crate) fn trait_predicates_for_self_ty<'a>(
54 &'a self,
55 ty: &'a Ty,
56 ) -> impl Iterator<Item = &'a TraitRef> + 'a {
57 self.predicates.iter().filter_map(move |pred| match pred {
58 GenericPredicate::Implemented(tr) if tr.self_ty() == ty => Some(tr),
59 _ => None,
60 })
61 }
62}
63
64/// Something (usually a goal), along with an environment.
65#[derive(Clone, Debug, PartialEq, Eq, Hash)]
66pub struct InEnvironment<T> {
67 pub environment: Arc<TraitEnvironment>,
68 pub value: T,
69}
70
71impl<T> InEnvironment<T> {
72 pub fn new(environment: Arc<TraitEnvironment>, value: T) -> InEnvironment<T> {
73 InEnvironment { environment, value }
74 }
75}
76
77/// Something that needs to be proven (by Chalk) during type checking, e.g. that
78/// a certain type implements a certain trait. Proving the Obligation might
79/// result in additional information about inference variables.
80#[derive(Clone, Debug, PartialEq, Eq, Hash)]
81pub enum Obligation {
82 /// Prove that a certain type implements a trait (the type is the `Self` type
83 /// parameter to the `TraitRef`).
84 Trait(TraitRef),
85 Projection(ProjectionPredicate),
86}
87
88impl Obligation {
89 pub fn from_predicate(predicate: GenericPredicate) -> Option<Obligation> {
90 match predicate {
91 GenericPredicate::Implemented(trait_ref) => Some(Obligation::Trait(trait_ref)),
92 GenericPredicate::Projection(projection_pred) => {
93 Some(Obligation::Projection(projection_pred))
94 }
95 GenericPredicate::Error => None,
96 }
97 }
98}
99
100#[derive(Clone, Debug, PartialEq, Eq, Hash)]
101pub struct ProjectionPredicate {
102 pub projection_ty: ProjectionTy,
103 pub ty: Ty,
104}
105
106impl TypeWalk for ProjectionPredicate {
107 fn walk(&self, f: &mut impl FnMut(&Ty)) {
108 self.projection_ty.walk(f);
109 self.ty.walk(f);
110 }
111
112 fn walk_mut_binders(
113 &mut self,
114 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
115 binders: DebruijnIndex,
116 ) {
117 self.projection_ty.walk_mut_binders(f, binders);
118 self.ty.walk_mut_binders(f, binders);
119 }
120}
121
122/// Solve a trait goal using Chalk.
123pub(crate) fn trait_solve_query(
124 db: &dyn HirDatabase,
125 krate: CrateId,
126 goal: Canonical<InEnvironment<Obligation>>,
127) -> Option<Solution> {
128 let _p = profile("trait_solve_query").detail(|| match &goal.value.value {
129 Obligation::Trait(it) => db.trait_data(it.trait_).name.to_string(),
130 Obligation::Projection(_) => "projection".to_string(),
131 });
132 log::info!("trait_solve_query({})", goal.value.value.display(db));
133
134 if let Obligation::Projection(pred) = &goal.value.value {
135 if let Ty::Bound(_) = &pred.projection_ty.parameters[0] {
136 // Hack: don't ask Chalk to normalize with an unknown self type, it'll say that's impossible
137 return Some(Solution::Ambig(Guidance::Unknown));
138 }
139 }
140
141 let canonical = goal.to_chalk(db).cast(&Interner);
142
143 // We currently don't deal with universes (I think / hope they're not yet
144 // relevant for our use cases?)
145 let u_canonical = chalk_ir::UCanonical { canonical, universes: 1 };
146 let solution = solve(db, krate, &u_canonical);
147 solution.map(|solution| solution_from_chalk(db, solution))
148}
149
150fn solve(
151 db: &dyn HirDatabase,
152 krate: CrateId,
153 goal: &chalk_ir::UCanonical<chalk_ir::InEnvironment<chalk_ir::Goal<Interner>>>,
154) -> Option<chalk_solve::Solution<Interner>> {
155 let context = ChalkContext { db, krate };
156 log::debug!("solve goal: {:?}", goal);
157 let mut solver = create_chalk_solver();
158
159 let fuel = std::cell::Cell::new(CHALK_SOLVER_FUEL);
160
161 let should_continue = || {
162 context.db.check_canceled();
163 let remaining = fuel.get();
164 fuel.set(remaining - 1);
165 if remaining == 0 {
166 log::debug!("fuel exhausted");
167 }
168 remaining > 0
169 };
170 let mut solve = || {
171 let solution = solver.solve_limited(&context, goal, should_continue);
172 log::debug!("solve({:?}) => {:?}", goal, solution);
173 solution
174 };
175 // don't set the TLS for Chalk unless Chalk debugging is active, to make
176 // extra sure we only use it for debugging
177 let solution =
178 if is_chalk_debug() { chalk::tls::set_current_program(db, solve) } else { solve() };
179
180 solution
181}
182
183fn is_chalk_debug() -> bool {
184 std::env::var("CHALK_DEBUG").is_ok()
185}
186
187fn solution_from_chalk(
188 db: &dyn HirDatabase,
189 solution: chalk_solve::Solution<Interner>,
190) -> Solution {
191 let convert_subst = |subst: chalk_ir::Canonical<chalk_ir::Substitution<Interner>>| {
192 let result = from_chalk(db, subst);
193 SolutionVariables(result)
194 };
195 match solution {
196 chalk_solve::Solution::Unique(constr_subst) => {
197 let subst = chalk_ir::Canonical {
198 value: constr_subst.value.subst,
199 binders: constr_subst.binders,
200 };
201 Solution::Unique(convert_subst(subst))
202 }
203 chalk_solve::Solution::Ambig(chalk_solve::Guidance::Definite(subst)) => {
204 Solution::Ambig(Guidance::Definite(convert_subst(subst)))
205 }
206 chalk_solve::Solution::Ambig(chalk_solve::Guidance::Suggested(subst)) => {
207 Solution::Ambig(Guidance::Suggested(convert_subst(subst)))
208 }
209 chalk_solve::Solution::Ambig(chalk_solve::Guidance::Unknown) => {
210 Solution::Ambig(Guidance::Unknown)
211 }
212 }
213}
214
215#[derive(Clone, Debug, PartialEq, Eq)]
216pub struct SolutionVariables(pub Canonical<Substs>);
217
218#[derive(Clone, Debug, PartialEq, Eq)]
219/// A (possible) solution for a proposed goal.
220pub enum Solution {
221 /// The goal indeed holds, and there is a unique value for all existential
222 /// variables.
223 Unique(SolutionVariables),
224
225 /// The goal may be provable in multiple ways, but regardless we may have some guidance
226 /// for type inference. In this case, we don't return any lifetime
227 /// constraints, since we have not "committed" to any particular solution
228 /// yet.
229 Ambig(Guidance),
230}
231
232#[derive(Clone, Debug, PartialEq, Eq)]
233/// When a goal holds ambiguously (e.g., because there are multiple possible
234/// solutions), we issue a set of *guidance* back to type inference.
235pub enum Guidance {
236 /// The existential variables *must* have the given values if the goal is
237 /// ever to hold, but that alone isn't enough to guarantee the goal will
238 /// actually hold.
239 Definite(SolutionVariables),
240
241 /// There are multiple plausible values for the existentials, but the ones
242 /// here are suggested as the preferred choice heuristically. These should
243 /// be used for inference fallback only.
244 Suggested(SolutionVariables),
245
246 /// There's no useful information to feed back to type inference
247 Unknown,
248}
249
250#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
251pub enum FnTrait {
252 FnOnce,
253 FnMut,
254 Fn,
255}
256
257impl FnTrait {
258 fn lang_item_name(self) -> &'static str {
259 match self {
260 FnTrait::FnOnce => "fn_once",
261 FnTrait::FnMut => "fn_mut",
262 FnTrait::Fn => "fn",
263 }
264 }
265
266 pub fn get_id(&self, db: &dyn HirDatabase, krate: CrateId) -> Option<TraitId> {
267 let target = db.lang_item(krate, self.lang_item_name().into())?;
268 match target {
269 LangItemTarget::TraitId(t) => Some(t),
270 _ => None,
271 }
272 }
273}
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-19 11:29:54 +0100