rustc_next_trait_solver/solve/eval_ctxt/
canonical.rs1use std::iter;
13
14use rustc_index::IndexVec;
15use rustc_type_ir::inherent::*;
16use rustc_type_ir::relate::solver_relating::RelateExt;
17use rustc_type_ir::{
18 self as ty, Canonical, CanonicalVarValues, InferCtxtLike, Interner, TypeFoldable,
19};
20use tracing::{debug, instrument, trace};
21
22use crate::canonicalizer::Canonicalizer;
23use crate::delegate::SolverDelegate;
24use crate::resolve::EagerResolver;
25use crate::solve::eval_ctxt::{CurrentGoalKind, NestedGoals};
26use crate::solve::{
27 CanonicalInput, CanonicalResponse, Certainty, EvalCtxt, ExternalConstraintsData, Goal,
28 MaybeCause, NestedNormalizationGoals, NoSolution, PredefinedOpaquesData, QueryInput,
29 QueryResult, Response, inspect, response_no_constraints_raw,
30};
31
32trait ResponseT<I: Interner> {
33 fn var_values(&self) -> CanonicalVarValues<I>;
34}
35
36impl<I: Interner> ResponseT<I> for Response<I> {
37 fn var_values(&self) -> CanonicalVarValues<I> {
38 self.var_values
39 }
40}
41
42impl<I: Interner, T> ResponseT<I> for inspect::State<I, T> {
43 fn var_values(&self) -> CanonicalVarValues<I> {
44 self.var_values
45 }
46}
47
48impl<D, I> EvalCtxt<'_, D>
49where
50 D: SolverDelegate<Interner = I>,
51 I: Interner,
52{
53 pub(super) fn canonicalize_goal<T: TypeFoldable<I>>(
56 &self,
57 goal: Goal<I, T>,
58 ) -> (Vec<I::GenericArg>, CanonicalInput<I, T>) {
59 let opaque_types = self.delegate.clone_opaque_types_for_query_response();
60 let (goal, opaque_types) =
61 (goal, opaque_types).fold_with(&mut EagerResolver::new(self.delegate));
62
63 let mut orig_values = Default::default();
64 let canonical = Canonicalizer::canonicalize_input(
65 self.delegate,
66 &mut orig_values,
67 QueryInput {
68 goal,
69 predefined_opaques_in_body: self
70 .cx()
71 .mk_predefined_opaques_in_body(PredefinedOpaquesData { opaque_types }),
72 },
73 );
74 let query_input = ty::CanonicalQueryInput { canonical, typing_mode: self.typing_mode() };
75 (orig_values, query_input)
76 }
77
78 #[instrument(level = "trace", skip(self), ret)]
85 pub(in crate::solve) fn evaluate_added_goals_and_make_canonical_response(
86 &mut self,
87 certainty: Certainty,
88 ) -> QueryResult<I> {
89 self.inspect.make_canonical_response(certainty);
90
91 let goals_certainty = self.try_evaluate_added_goals()?;
92 assert_eq!(
93 self.tainted,
94 Ok(()),
95 "EvalCtxt is tainted -- nested goals may have been dropped in a \
96 previous call to `try_evaluate_added_goals!`"
97 );
98
99 self.delegate.leak_check(self.max_input_universe).map_err(|NoSolution| {
102 trace!("failed the leak check");
103 NoSolution
104 })?;
105
106 let (certainty, normalization_nested_goals) = match self.current_goal_kind {
114 CurrentGoalKind::NormalizesTo => {
115 let NestedGoals { normalizes_to_goals, goals } =
116 std::mem::take(&mut self.nested_goals);
117 if cfg!(debug_assertions) {
118 assert!(normalizes_to_goals.is_empty());
119 if goals.is_empty() {
120 assert!(matches!(goals_certainty, Certainty::Yes));
121 }
122 }
123 (certainty, NestedNormalizationGoals(goals))
124 }
125 CurrentGoalKind::Misc | CurrentGoalKind::CoinductiveTrait => {
126 let certainty = certainty.unify_with(goals_certainty);
127 (certainty, NestedNormalizationGoals::empty())
128 }
129 };
130
131 if let Certainty::Maybe(cause @ MaybeCause::Overflow { .. }) = certainty {
132 return Ok(self.make_ambiguous_response_no_constraints(cause));
144 }
145
146 let external_constraints =
147 self.compute_external_query_constraints(certainty, normalization_nested_goals);
148 let (var_values, mut external_constraints) = (self.var_values, external_constraints)
149 .fold_with(&mut EagerResolver::new(self.delegate));
150 external_constraints
152 .region_constraints
153 .retain(|outlives| outlives.0.as_region().is_none_or(|re| re != outlives.1));
154
155 let canonical = Canonicalizer::canonicalize_response(
156 self.delegate,
157 self.max_input_universe,
158 &mut Default::default(),
159 Response {
160 var_values,
161 certainty,
162 external_constraints: self.cx().mk_external_constraints(external_constraints),
163 },
164 );
165
166 match self.current_goal_kind {
172 CurrentGoalKind::NormalizesTo => {}
177 CurrentGoalKind::Misc | CurrentGoalKind::CoinductiveTrait => {
178 let num_non_region_vars = canonical
179 .variables
180 .iter()
181 .filter(|c| !c.is_region() && c.is_existential())
182 .count();
183 if num_non_region_vars > self.cx().recursion_limit() {
184 debug!(?num_non_region_vars, "too many inference variables -> overflow");
185 return Ok(self.make_ambiguous_response_no_constraints(MaybeCause::Overflow {
186 suggest_increasing_limit: true,
187 }));
188 }
189 }
190 }
191
192 Ok(canonical)
193 }
194
195 pub(in crate::solve) fn make_ambiguous_response_no_constraints(
200 &self,
201 maybe_cause: MaybeCause,
202 ) -> CanonicalResponse<I> {
203 response_no_constraints_raw(
204 self.cx(),
205 self.max_input_universe,
206 self.variables,
207 Certainty::Maybe(maybe_cause),
208 )
209 }
210
211 #[instrument(level = "trace", skip(self), ret)]
219 fn compute_external_query_constraints(
220 &self,
221 certainty: Certainty,
222 normalization_nested_goals: NestedNormalizationGoals<I>,
223 ) -> ExternalConstraintsData<I> {
224 let region_constraints = if certainty == Certainty::Yes {
233 self.delegate.make_deduplicated_outlives_constraints()
234 } else {
235 Default::default()
236 };
237
238 ExternalConstraintsData {
239 region_constraints,
240 opaque_types: self
241 .delegate
242 .clone_opaque_types_for_query_response()
243 .into_iter()
244 .filter(|(a, _)| {
246 self.predefined_opaques_in_body.opaque_types.iter().all(|(pa, _)| pa != a)
247 })
248 .collect(),
249 normalization_nested_goals,
250 }
251 }
252
253 pub(super) fn instantiate_and_apply_query_response(
262 &mut self,
263 param_env: I::ParamEnv,
264 original_values: Vec<I::GenericArg>,
265 response: CanonicalResponse<I>,
266 ) -> (NestedNormalizationGoals<I>, Certainty) {
267 let instantiation = Self::compute_query_response_instantiation_values(
268 self.delegate,
269 &original_values,
270 &response,
271 self.origin_span,
272 );
273
274 let Response { var_values, external_constraints, certainty } =
275 self.delegate.instantiate_canonical(response, instantiation);
276
277 Self::unify_query_var_values(
278 self.delegate,
279 param_env,
280 &original_values,
281 var_values,
282 self.origin_span,
283 );
284
285 let ExternalConstraintsData {
286 region_constraints,
287 opaque_types,
288 normalization_nested_goals,
289 } = &*external_constraints;
290
291 self.register_region_constraints(region_constraints);
292 self.register_new_opaque_types(opaque_types);
293
294 (normalization_nested_goals.clone(), certainty)
295 }
296
297 fn compute_query_response_instantiation_values<T: ResponseT<I>>(
301 delegate: &D,
302 original_values: &[I::GenericArg],
303 response: &Canonical<I, T>,
304 span: I::Span,
305 ) -> CanonicalVarValues<I> {
306 let prev_universe = delegate.universe();
310 let universes_created_in_query = response.max_universe.index();
311 for _ in 0..universes_created_in_query {
312 delegate.create_next_universe();
313 }
314
315 let var_values = response.value.var_values();
316 assert_eq!(original_values.len(), var_values.len());
317
318 let mut opt_values = IndexVec::from_elem_n(None, response.variables.len());
326 for (original_value, result_value) in
327 iter::zip(original_values, var_values.var_values.iter())
328 {
329 match result_value.kind() {
330 ty::GenericArgKind::Type(t) => {
331 if let ty::Bound(debruijn, b) = t.kind() {
332 assert_eq!(debruijn, ty::INNERMOST);
333 opt_values[b.var()] = Some(*original_value);
334 }
335 }
336 ty::GenericArgKind::Lifetime(r) => {
337 if let ty::ReBound(debruijn, br) = r.kind() {
338 assert_eq!(debruijn, ty::INNERMOST);
339 opt_values[br.var()] = Some(*original_value);
340 }
341 }
342 ty::GenericArgKind::Const(c) => {
343 if let ty::ConstKind::Bound(debruijn, bv) = c.kind() {
344 assert_eq!(debruijn, ty::INNERMOST);
345 opt_values[bv.var()] = Some(*original_value);
346 }
347 }
348 }
349 }
350
351 let var_values = delegate.cx().mk_args_from_iter(
352 response.variables.iter().enumerate().map(|(index, info)| {
353 if info.universe() != ty::UniverseIndex::ROOT {
354 delegate.instantiate_canonical_var_with_infer(info, span, |idx| {
358 ty::UniverseIndex::from(prev_universe.index() + idx.index())
359 })
360 } else if info.is_existential() {
361 if let Some(v) = opt_values[ty::BoundVar::from_usize(index)] {
369 v
370 } else {
371 delegate.instantiate_canonical_var_with_infer(info, span, |_| prev_universe)
372 }
373 } else {
374 original_values[info.expect_placeholder_index()]
377 }
378 }),
379 );
380
381 CanonicalVarValues { var_values }
382 }
383
384 #[instrument(level = "trace", skip(delegate))]
397 fn unify_query_var_values(
398 delegate: &D,
399 param_env: I::ParamEnv,
400 original_values: &[I::GenericArg],
401 var_values: CanonicalVarValues<I>,
402 span: I::Span,
403 ) {
404 assert_eq!(original_values.len(), var_values.len());
405
406 for (&orig, response) in iter::zip(original_values, var_values.var_values.iter()) {
407 let goals =
408 delegate.eq_structurally_relating_aliases(param_env, orig, response, span).unwrap();
409 assert!(goals.is_empty());
410 }
411 }
412
413 fn register_region_constraints(
414 &mut self,
415 outlives: &[ty::OutlivesPredicate<I, I::GenericArg>],
416 ) {
417 for &ty::OutlivesPredicate(lhs, rhs) in outlives {
418 match lhs.kind() {
419 ty::GenericArgKind::Lifetime(lhs) => self.register_region_outlives(lhs, rhs),
420 ty::GenericArgKind::Type(lhs) => self.register_ty_outlives(lhs, rhs),
421 ty::GenericArgKind::Const(_) => panic!("const outlives: {lhs:?}: {rhs:?}"),
422 }
423 }
424 }
425
426 fn register_new_opaque_types(&mut self, opaque_types: &[(ty::OpaqueTypeKey<I>, I::Ty)]) {
427 for &(key, ty) in opaque_types {
428 self.delegate.inject_new_hidden_type_unchecked(key, ty, self.origin_span);
429 }
430 }
431}
432
433pub(in crate::solve) fn make_canonical_state<D, T, I>(
438 delegate: &D,
439 var_values: &[I::GenericArg],
440 max_input_universe: ty::UniverseIndex,
441 data: T,
442) -> inspect::CanonicalState<I, T>
443where
444 D: SolverDelegate<Interner = I>,
445 I: Interner,
446 T: TypeFoldable<I>,
447{
448 let var_values = CanonicalVarValues { var_values: delegate.cx().mk_args(var_values) };
449 let state = inspect::State { var_values, data };
450 let state = state.fold_with(&mut EagerResolver::new(delegate));
451 Canonicalizer::canonicalize_response(delegate, max_input_universe, &mut vec![], state)
452}
453
454pub fn instantiate_canonical_state<D, I, T: TypeFoldable<I>>(
457 delegate: &D,
458 span: I::Span,
459 param_env: I::ParamEnv,
460 orig_values: &mut Vec<I::GenericArg>,
461 state: inspect::CanonicalState<I, T>,
462) -> T
463where
464 D: SolverDelegate<Interner = I>,
465 I: Interner,
466{
467 orig_values.extend(
470 state.value.var_values.var_values.as_slice()[orig_values.len()..]
471 .iter()
472 .map(|&arg| delegate.fresh_var_for_kind_with_span(arg, span)),
473 );
474
475 let instantiation =
476 EvalCtxt::compute_query_response_instantiation_values(delegate, orig_values, &state, span);
477
478 let inspect::State { var_values, data } = delegate.instantiate_canonical(state, instantiation);
479
480 EvalCtxt::unify_query_var_values(delegate, param_env, orig_values, var_values, span);
481 data
482}