rustc_next_trait_solver/solve/
mod.rs1mod alias_relate;
15mod assembly;
16mod effect_goals;
17mod eval_ctxt;
18pub mod inspect;
19mod normalizes_to;
20mod project_goals;
21mod search_graph;
22mod trait_goals;
23
24use rustc_type_ir::inherent::*;
25pub use rustc_type_ir::solve::*;
26use rustc_type_ir::{self as ty, Interner, TypingMode};
27use tracing::instrument;
28
29pub use self::eval_ctxt::{EvalCtxt, GenerateProofTree, SolverDelegateEvalExt};
30use crate::delegate::SolverDelegate;
31
32const FIXPOINT_STEP_LIMIT: usize = 8;
42
43#[derive(Debug, Copy, Clone, PartialEq, Eq)]
44enum GoalEvaluationKind {
45 Root,
46 Nested,
47}
48
49#[derive(PartialEq, Eq, Debug, Hash, Clone, Copy)]
52pub enum HasChanged {
53 Yes,
54 No,
55}
56
57fn has_no_inference_or_external_constraints<I: Interner>(
60 response: ty::Canonical<I, Response<I>>,
61) -> bool {
62 let ExternalConstraintsData {
63 ref region_constraints,
64 ref opaque_types,
65 ref normalization_nested_goals,
66 } = *response.value.external_constraints;
67 response.value.var_values.is_identity()
68 && region_constraints.is_empty()
69 && opaque_types.is_empty()
70 && normalization_nested_goals.is_empty()
71}
72
73impl<'a, D, I> EvalCtxt<'a, D>
74where
75 D: SolverDelegate<Interner = I>,
76 I: Interner,
77{
78 #[instrument(level = "trace", skip(self))]
79 fn compute_type_outlives_goal(
80 &mut self,
81 goal: Goal<I, ty::OutlivesPredicate<I, I::Ty>>,
82 ) -> QueryResult<I> {
83 let ty::OutlivesPredicate(ty, lt) = goal.predicate;
84 self.register_ty_outlives(ty, lt);
85 self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
86 }
87
88 #[instrument(level = "trace", skip(self))]
89 fn compute_region_outlives_goal(
90 &mut self,
91 goal: Goal<I, ty::OutlivesPredicate<I, I::Region>>,
92 ) -> QueryResult<I> {
93 let ty::OutlivesPredicate(a, b) = goal.predicate;
94 self.register_region_outlives(a, b);
95 self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
96 }
97
98 #[instrument(level = "trace", skip(self))]
99 fn compute_coerce_goal(&mut self, goal: Goal<I, ty::CoercePredicate<I>>) -> QueryResult<I> {
100 self.compute_subtype_goal(Goal {
101 param_env: goal.param_env,
102 predicate: ty::SubtypePredicate {
103 a_is_expected: false,
104 a: goal.predicate.a,
105 b: goal.predicate.b,
106 },
107 })
108 }
109
110 #[instrument(level = "trace", skip(self))]
111 fn compute_subtype_goal(&mut self, goal: Goal<I, ty::SubtypePredicate<I>>) -> QueryResult<I> {
112 if goal.predicate.a.is_ty_var() && goal.predicate.b.is_ty_var() {
113 self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
114 } else {
115 self.sub(goal.param_env, goal.predicate.a, goal.predicate.b)?;
116 self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
117 }
118 }
119
120 fn compute_dyn_compatible_goal(&mut self, trait_def_id: I::DefId) -> QueryResult<I> {
121 if self.cx().trait_is_dyn_compatible(trait_def_id) {
122 self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
123 } else {
124 Err(NoSolution)
125 }
126 }
127
128 #[instrument(level = "trace", skip(self))]
129 fn compute_well_formed_goal(&mut self, goal: Goal<I, I::GenericArg>) -> QueryResult<I> {
130 match self.well_formed_goals(goal.param_env, goal.predicate) {
131 Some(goals) => {
132 self.add_goals(GoalSource::Misc, goals);
133 self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
134 }
135 None => self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS),
136 }
137 }
138
139 #[instrument(level = "trace", skip(self))]
140 fn compute_const_evaluatable_goal(
141 &mut self,
142 Goal { param_env, predicate: ct }: Goal<I, I::Const>,
143 ) -> QueryResult<I> {
144 match ct.kind() {
145 ty::ConstKind::Unevaluated(uv) => {
146 if let Some(_normalized) = self.evaluate_const(param_env, uv) {
155 self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
156 } else {
157 self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
158 }
159 }
160 ty::ConstKind::Infer(_) => {
161 self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
162 }
163 ty::ConstKind::Placeholder(_) | ty::ConstKind::Value(_) | ty::ConstKind::Error(_) => {
164 self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
165 }
166 ty::ConstKind::Param(_) | ty::ConstKind::Bound(_, _) | ty::ConstKind::Expr(_) => {
171 panic!("unexpected const kind: {:?}", ct)
172 }
173 }
174 }
175
176 #[instrument(level = "trace", skip(self), ret)]
177 fn compute_const_arg_has_type_goal(
178 &mut self,
179 goal: Goal<I, (I::Const, I::Ty)>,
180 ) -> QueryResult<I> {
181 let (ct, ty) = goal.predicate;
182
183 let ct_ty = match ct.kind() {
184 ty::ConstKind::Infer(_) => {
185 return self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS);
186 }
187 ty::ConstKind::Error(_) => {
188 return self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes);
189 }
190 ty::ConstKind::Unevaluated(uv) => {
191 self.cx().type_of(uv.def).instantiate(self.cx(), uv.args)
192 }
193 ty::ConstKind::Expr(_) => unimplemented!(
194 "`feature(generic_const_exprs)` is not supported in the new trait solver"
195 ),
196 ty::ConstKind::Param(_) => {
197 unreachable!("`ConstKind::Param` should have been canonicalized to `Placeholder`")
198 }
199 ty::ConstKind::Bound(_, _) => panic!("escaping bound vars in {:?}", ct),
200 ty::ConstKind::Value(cv) => cv.ty(),
201 ty::ConstKind::Placeholder(placeholder) => {
202 self.cx().find_const_ty_from_env(goal.param_env, placeholder)
203 }
204 };
205
206 self.eq(goal.param_env, ct_ty, ty)?;
207 self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
208 }
209}
210
211impl<D, I> EvalCtxt<'_, D>
212where
213 D: SolverDelegate<Interner = I>,
214 I: Interner,
215{
216 #[instrument(level = "trace", skip(self), ret)]
220 fn try_merge_responses(
221 &mut self,
222 responses: &[CanonicalResponse<I>],
223 ) -> Option<CanonicalResponse<I>> {
224 if responses.is_empty() {
225 return None;
226 }
227
228 let one = responses[0];
231 if responses[1..].iter().all(|&resp| resp == one) {
232 return Some(one);
233 }
234
235 responses
236 .iter()
237 .find(|response| {
238 response.value.certainty == Certainty::Yes
239 && has_no_inference_or_external_constraints(**response)
240 })
241 .copied()
242 }
243
244 fn bail_with_ambiguity(&mut self, responses: &[CanonicalResponse<I>]) -> CanonicalResponse<I> {
245 debug_assert!(!responses.is_empty());
246 if let Certainty::Maybe(maybe_cause) =
247 responses.iter().fold(Certainty::AMBIGUOUS, |certainty, response| {
248 certainty.unify_with(response.value.certainty)
249 })
250 {
251 self.make_ambiguous_response_no_constraints(maybe_cause)
252 } else {
253 panic!("expected flounder response to be ambiguous")
254 }
255 }
256
257 #[instrument(level = "trace", skip(self), ret)]
259 fn flounder(&mut self, responses: &[CanonicalResponse<I>]) -> QueryResult<I> {
260 if responses.is_empty() {
261 return Err(NoSolution);
262 } else {
263 Ok(self.bail_with_ambiguity(responses))
264 }
265 }
266
267 #[instrument(level = "trace", skip(self, param_env), ret)]
273 fn structurally_normalize_ty(
274 &mut self,
275 param_env: I::ParamEnv,
276 ty: I::Ty,
277 ) -> Result<I::Ty, NoSolution> {
278 self.structurally_normalize_term(param_env, ty.into()).map(|term| term.expect_ty())
279 }
280
281 #[instrument(level = "trace", skip(self, param_env), ret)]
288 fn structurally_normalize_const(
289 &mut self,
290 param_env: I::ParamEnv,
291 ct: I::Const,
292 ) -> Result<I::Const, NoSolution> {
293 self.structurally_normalize_term(param_env, ct.into()).map(|term| term.expect_const())
294 }
295
296 fn structurally_normalize_term(
301 &mut self,
302 param_env: I::ParamEnv,
303 term: I::Term,
304 ) -> Result<I::Term, NoSolution> {
305 if let Some(_) = term.to_alias_term() {
306 let normalized_term = self.next_term_infer_of_kind(term);
307 let alias_relate_goal = Goal::new(
308 self.cx(),
309 param_env,
310 ty::PredicateKind::AliasRelate(
311 term,
312 normalized_term,
313 ty::AliasRelationDirection::Equate,
314 ),
315 );
316 self.add_goal(GoalSource::TypeRelating, alias_relate_goal);
319 self.try_evaluate_added_goals()?;
320 Ok(self.resolve_vars_if_possible(normalized_term))
321 } else {
322 Ok(term)
323 }
324 }
325
326 fn opaque_type_is_rigid(&self, def_id: I::DefId) -> bool {
327 match self.typing_mode() {
328 TypingMode::Coherence | TypingMode::PostAnalysis => false,
330 TypingMode::Analysis { defining_opaque_types: non_rigid_opaques }
333 | TypingMode::PostBorrowckAnalysis { defined_opaque_types: non_rigid_opaques } => {
334 !def_id.as_local().is_some_and(|def_id| non_rigid_opaques.contains(&def_id))
335 }
336 }
337 }
338}
339
340fn response_no_constraints_raw<I: Interner>(
341 cx: I,
342 max_universe: ty::UniverseIndex,
343 variables: I::CanonicalVars,
344 certainty: Certainty,
345) -> CanonicalResponse<I> {
346 ty::Canonical {
347 max_universe,
348 variables,
349 value: Response {
350 var_values: ty::CanonicalVarValues::make_identity(cx, variables),
351 external_constraints: cx.mk_external_constraints(ExternalConstraintsData::default()),
354 certainty,
355 },
356 }
357}