rustc_next_trait_solver/solve/eval_ctxt/
mod.rs

1use std::mem;
2use std::ops::ControlFlow;
3
4#[cfg(feature = "nightly")]
5use rustc_macros::HashStable_NoContext;
6use rustc_type_ir::data_structures::{HashMap, HashSet};
7use rustc_type_ir::fast_reject::DeepRejectCtxt;
8use rustc_type_ir::inherent::*;
9use rustc_type_ir::relate::Relate;
10use rustc_type_ir::relate::solver_relating::RelateExt;
11use rustc_type_ir::search_graph::PathKind;
12use rustc_type_ir::{
13    self as ty, CanonicalVarValues, InferCtxtLike, Interner, TypeFoldable, TypeFolder,
14    TypeSuperFoldable, TypeSuperVisitable, TypeVisitable, TypeVisitableExt, TypeVisitor,
15    TypingMode,
16};
17use tracing::{debug, instrument, trace};
18
19use super::has_only_region_constraints;
20use crate::coherence;
21use crate::delegate::SolverDelegate;
22use crate::placeholder::BoundVarReplacer;
23use crate::solve::inspect::{self, ProofTreeBuilder};
24use crate::solve::search_graph::SearchGraph;
25use crate::solve::{
26    CanonicalInput, Certainty, FIXPOINT_STEP_LIMIT, Goal, GoalEvaluation, GoalEvaluationKind,
27    GoalSource, GoalStalledOn, HasChanged, NestedNormalizationGoals, NoSolution, QueryInput,
28    QueryResult,
29};
30
31pub(super) mod canonical;
32mod probe;
33
34/// The kind of goal we're currently proving.
35///
36/// This has effects on cycle handling handling and on how we compute
37/// query responses, see the variant descriptions for more info.
38#[derive(Debug, Copy, Clone)]
39enum CurrentGoalKind {
40    Misc,
41    /// We're proving an trait goal for a coinductive trait, either an auto trait or `Sized`.
42    ///
43    /// These are currently the only goals whose impl where-clauses are considered to be
44    /// productive steps.
45    CoinductiveTrait,
46    /// Unlike other goals, `NormalizesTo` goals act like functions with the expected term
47    /// always being fully unconstrained. This would weaken inference however, as the nested
48    /// goals never get the inference constraints from the actual normalized-to type.
49    ///
50    /// Because of this we return any ambiguous nested goals from `NormalizesTo` to the
51    /// caller when then adds these to its own context. The caller is always an `AliasRelate`
52    /// goal so this never leaks out of the solver.
53    NormalizesTo,
54}
55
56impl CurrentGoalKind {
57    fn from_query_input<I: Interner>(cx: I, input: QueryInput<I, I::Predicate>) -> CurrentGoalKind {
58        match input.goal.predicate.kind().skip_binder() {
59            ty::PredicateKind::Clause(ty::ClauseKind::Trait(pred)) => {
60                if cx.trait_is_coinductive(pred.trait_ref.def_id) {
61                    CurrentGoalKind::CoinductiveTrait
62                } else {
63                    CurrentGoalKind::Misc
64                }
65            }
66            ty::PredicateKind::NormalizesTo(_) => CurrentGoalKind::NormalizesTo,
67            _ => CurrentGoalKind::Misc,
68        }
69    }
70}
71
72pub struct EvalCtxt<'a, D, I = <D as SolverDelegate>::Interner>
73where
74    D: SolverDelegate<Interner = I>,
75    I: Interner,
76{
77    /// The inference context that backs (mostly) inference and placeholder terms
78    /// instantiated while solving goals.
79    ///
80    /// NOTE: The `InferCtxt` that backs the `EvalCtxt` is intentionally private,
81    /// because the `InferCtxt` is much more general than `EvalCtxt`. Methods such
82    /// as  `take_registered_region_obligations` can mess up query responses,
83    /// using `At::normalize` is totally wrong, calling `evaluate_root_goal` can
84    /// cause coinductive unsoundness, etc.
85    ///
86    /// Methods that are generally of use for trait solving are *intentionally*
87    /// re-declared through the `EvalCtxt` below, often with cleaner signatures
88    /// since we don't care about things like `ObligationCause`s and `Span`s here.
89    /// If some `InferCtxt` method is missing, please first think defensively about
90    /// the method's compatibility with this solver, or if an existing one does
91    /// the job already.
92    delegate: &'a D,
93
94    /// The variable info for the `var_values`, only used to make an ambiguous response
95    /// with no constraints.
96    variables: I::CanonicalVarKinds,
97
98    /// What kind of goal we're currently computing, see the enum definition
99    /// for more info.
100    current_goal_kind: CurrentGoalKind,
101    pub(super) var_values: CanonicalVarValues<I>,
102
103    /// The highest universe index nameable by the caller.
104    ///
105    /// When we enter a new binder inside of the query we create new universes
106    /// which the caller cannot name. We have to be careful with variables from
107    /// these new universes when creating the query response.
108    ///
109    /// Both because these new universes can prevent us from reaching a fixpoint
110    /// if we have a coinductive cycle and because that's the only way we can return
111    /// new placeholders to the caller.
112    pub(super) max_input_universe: ty::UniverseIndex,
113    /// The opaque types from the canonical input. We only need to return opaque types
114    /// which have been added to the storage while evaluating this goal.
115    pub(super) initial_opaque_types_storage_num_entries:
116        <D::Infcx as InferCtxtLike>::OpaqueTypeStorageEntries,
117
118    pub(super) search_graph: &'a mut SearchGraph<D>,
119
120    nested_goals: Vec<(GoalSource, Goal<I, I::Predicate>, Option<GoalStalledOn<I>>)>,
121
122    pub(super) origin_span: I::Span,
123
124    // Has this `EvalCtxt` errored out with `NoSolution` in `try_evaluate_added_goals`?
125    //
126    // If so, then it can no longer be used to make a canonical query response,
127    // since subsequent calls to `try_evaluate_added_goals` have possibly dropped
128    // ambiguous goals. Instead, a probe needs to be introduced somewhere in the
129    // evaluation code.
130    tainted: Result<(), NoSolution>,
131
132    pub(super) inspect: ProofTreeBuilder<D>,
133}
134
135#[derive(PartialEq, Eq, Debug, Hash, Clone, Copy)]
136#[cfg_attr(feature = "nightly", derive(HashStable_NoContext))]
137pub enum GenerateProofTree {
138    Yes,
139    No,
140}
141
142pub trait SolverDelegateEvalExt: SolverDelegate {
143    /// Evaluates a goal from **outside** of the trait solver.
144    ///
145    /// Using this while inside of the solver is wrong as it uses a new
146    /// search graph which would break cycle detection.
147    fn evaluate_root_goal(
148        &self,
149        goal: Goal<Self::Interner, <Self::Interner as Interner>::Predicate>,
150        span: <Self::Interner as Interner>::Span,
151        stalled_on: Option<GoalStalledOn<Self::Interner>>,
152    ) -> Result<GoalEvaluation<Self::Interner>, NoSolution>;
153
154    /// Check whether evaluating `goal` with a depth of `root_depth` may
155    /// succeed. This only returns `false` if the goal is guaranteed to
156    /// not hold. In case evaluation overflows and fails with ambiguity this
157    /// returns `true`.
158    ///
159    /// This is only intended to be used as a performance optimization
160    /// in coherence checking.
161    fn root_goal_may_hold_with_depth(
162        &self,
163        root_depth: usize,
164        goal: Goal<Self::Interner, <Self::Interner as Interner>::Predicate>,
165    ) -> bool;
166
167    // FIXME: This is only exposed because we need to use it in `analyse.rs`
168    // which is not yet uplifted. Once that's done, we should remove this.
169    fn evaluate_root_goal_for_proof_tree(
170        &self,
171        goal: Goal<Self::Interner, <Self::Interner as Interner>::Predicate>,
172        span: <Self::Interner as Interner>::Span,
173    ) -> (
174        Result<
175            (NestedNormalizationGoals<Self::Interner>, GoalEvaluation<Self::Interner>),
176            NoSolution,
177        >,
178        inspect::GoalEvaluation<Self::Interner>,
179    );
180}
181
182impl<D, I> SolverDelegateEvalExt for D
183where
184    D: SolverDelegate<Interner = I>,
185    I: Interner,
186{
187    #[instrument(level = "debug", skip(self))]
188    fn evaluate_root_goal(
189        &self,
190        goal: Goal<I, I::Predicate>,
191        span: I::Span,
192        stalled_on: Option<GoalStalledOn<I>>,
193    ) -> Result<GoalEvaluation<I>, NoSolution> {
194        EvalCtxt::enter_root(
195            self,
196            self.cx().recursion_limit(),
197            GenerateProofTree::No,
198            span,
199            |ecx| ecx.evaluate_goal(GoalEvaluationKind::Root, GoalSource::Misc, goal, stalled_on),
200        )
201        .0
202    }
203
204    fn root_goal_may_hold_with_depth(
205        &self,
206        root_depth: usize,
207        goal: Goal<Self::Interner, <Self::Interner as Interner>::Predicate>,
208    ) -> bool {
209        self.probe(|| {
210            EvalCtxt::enter_root(self, root_depth, GenerateProofTree::No, I::Span::dummy(), |ecx| {
211                ecx.evaluate_goal(GoalEvaluationKind::Root, GoalSource::Misc, goal, None)
212            })
213            .0
214        })
215        .is_ok()
216    }
217
218    #[instrument(level = "debug", skip(self))]
219    fn evaluate_root_goal_for_proof_tree(
220        &self,
221        goal: Goal<I, I::Predicate>,
222        span: I::Span,
223    ) -> (
224        Result<(NestedNormalizationGoals<I>, GoalEvaluation<I>), NoSolution>,
225        inspect::GoalEvaluation<I>,
226    ) {
227        let (result, proof_tree) = EvalCtxt::enter_root(
228            self,
229            self.cx().recursion_limit(),
230            GenerateProofTree::Yes,
231            span,
232            |ecx| ecx.evaluate_goal_raw(GoalEvaluationKind::Root, GoalSource::Misc, goal, None),
233        );
234        (result, proof_tree.unwrap())
235    }
236}
237
238impl<'a, D, I> EvalCtxt<'a, D>
239where
240    D: SolverDelegate<Interner = I>,
241    I: Interner,
242{
243    pub(super) fn typing_mode(&self) -> TypingMode<I> {
244        self.delegate.typing_mode()
245    }
246
247    /// Computes the `PathKind` for the step from the current goal to the
248    /// nested goal required due to `source`.
249    ///
250    /// See #136824 for a more detailed reasoning for this behavior. We
251    /// consider cycles to be coinductive if they 'step into' a where-clause
252    /// of a coinductive trait. We will likely extend this function in the future
253    /// and will need to clearly document it in the rustc-dev-guide before
254    /// stabilization.
255    pub(super) fn step_kind_for_source(&self, source: GoalSource) -> PathKind {
256        match source {
257            // We treat these goals as unknown for now. It is likely that most miscellaneous
258            // nested goals will be converted to an inductive variant in the future.
259            //
260            // Having unknown cycles is always the safer option, as changing that to either
261            // succeed or hard error is backwards compatible. If we incorrectly treat a cycle
262            // as inductive even though it should not be, it may be unsound during coherence and
263            // fixing it may cause inference breakage or introduce ambiguity.
264            GoalSource::Misc => PathKind::Unknown,
265            GoalSource::NormalizeGoal(path_kind) => path_kind,
266            GoalSource::ImplWhereBound => match self.current_goal_kind {
267                // We currently only consider a cycle coinductive if it steps
268                // into a where-clause of a coinductive trait.
269                CurrentGoalKind::CoinductiveTrait => PathKind::Coinductive,
270                // While normalizing via an impl does step into a where-clause of
271                // an impl, accessing the associated item immediately steps out of
272                // it again. This means cycles/recursive calls are not guarded
273                // by impls used for normalization.
274                //
275                // See tests/ui/traits/next-solver/cycles/normalizes-to-is-not-productive.rs
276                // for how this can go wrong.
277                CurrentGoalKind::NormalizesTo => PathKind::Inductive,
278                // We probably want to make all traits coinductive in the future,
279                // so we treat cycles involving where-clauses of not-yet coinductive
280                // traits as ambiguous for now.
281                CurrentGoalKind::Misc => PathKind::Unknown,
282            },
283            // Relating types is always unproductive. If we were to map proof trees to
284            // corecursive functions as explained in #136824, relating types never
285            // introduces a constructor which could cause the recursion to be guarded.
286            GoalSource::TypeRelating => PathKind::Inductive,
287            // Instantiating a higher ranked goal can never cause the recursion to be
288            // guarded and is therefore unproductive.
289            GoalSource::InstantiateHigherRanked => PathKind::Inductive,
290            // These goal sources are likely unproductive and can be changed to
291            // `PathKind::Inductive`. Keeping them as unknown until we're confident
292            // about this and have an example where it is necessary.
293            GoalSource::AliasBoundConstCondition | GoalSource::AliasWellFormed => PathKind::Unknown,
294        }
295    }
296
297    /// Creates a root evaluation context and search graph. This should only be
298    /// used from outside of any evaluation, and other methods should be preferred
299    /// over using this manually (such as [`SolverDelegateEvalExt::evaluate_root_goal`]).
300    pub(super) fn enter_root<R>(
301        delegate: &D,
302        root_depth: usize,
303        generate_proof_tree: GenerateProofTree,
304        origin_span: I::Span,
305        f: impl FnOnce(&mut EvalCtxt<'_, D>) -> R,
306    ) -> (R, Option<inspect::GoalEvaluation<I>>) {
307        let mut search_graph = SearchGraph::new(root_depth);
308
309        let mut ecx = EvalCtxt {
310            delegate,
311            search_graph: &mut search_graph,
312            nested_goals: Default::default(),
313            inspect: ProofTreeBuilder::new_maybe_root(generate_proof_tree),
314
315            // Only relevant when canonicalizing the response,
316            // which we don't do within this evaluation context.
317            max_input_universe: ty::UniverseIndex::ROOT,
318            initial_opaque_types_storage_num_entries: Default::default(),
319            variables: Default::default(),
320            var_values: CanonicalVarValues::dummy(),
321            current_goal_kind: CurrentGoalKind::Misc,
322            origin_span,
323            tainted: Ok(()),
324        };
325        let result = f(&mut ecx);
326
327        let proof_tree = ecx.inspect.finalize();
328        assert!(
329            ecx.nested_goals.is_empty(),
330            "root `EvalCtxt` should not have any goals added to it"
331        );
332
333        assert!(search_graph.is_empty());
334        (result, proof_tree)
335    }
336
337    /// Creates a nested evaluation context that shares the same search graph as the
338    /// one passed in. This is suitable for evaluation, granted that the search graph
339    /// has had the nested goal recorded on its stack. This method only be used by
340    /// `search_graph::Delegate::compute_goal`.
341    ///
342    /// This function takes care of setting up the inference context, setting the anchor,
343    /// and registering opaques from the canonicalized input.
344    pub(super) fn enter_canonical<R>(
345        cx: I,
346        search_graph: &'a mut SearchGraph<D>,
347        canonical_input: CanonicalInput<I>,
348        canonical_goal_evaluation: &mut ProofTreeBuilder<D>,
349        f: impl FnOnce(&mut EvalCtxt<'_, D>, Goal<I, I::Predicate>) -> R,
350    ) -> R {
351        let (ref delegate, input, var_values) = D::build_with_canonical(cx, &canonical_input);
352
353        for &(key, ty) in &input.predefined_opaques_in_body.opaque_types {
354            let prev = delegate.register_hidden_type_in_storage(key, ty, I::Span::dummy());
355            // It may be possible that two entries in the opaque type storage end up
356            // with the same key after resolving contained inference variables.
357            //
358            // We could put them in the duplicate list but don't have to. The opaques we
359            // encounter here are already tracked in the caller, so there's no need to
360            // also store them here. We'd take them out when computing the query response
361            // and then discard them, as they're already present in the input.
362            //
363            // Ideally we'd drop duplicate opaque type definitions when computing
364            // the canonical input. This is more annoying to implement and may cause a
365            // perf regression, so we do it inside of the query for now.
366            if let Some(prev) = prev {
367                debug!(?key, ?ty, ?prev, "ignore duplicate in `opaque_types_storage`");
368            }
369        }
370
371        let initial_opaque_types_storage_num_entries = delegate.opaque_types_storage_num_entries();
372        let mut ecx = EvalCtxt {
373            delegate,
374            variables: canonical_input.canonical.variables,
375            var_values,
376            current_goal_kind: CurrentGoalKind::from_query_input(cx, input),
377            max_input_universe: canonical_input.canonical.max_universe,
378            initial_opaque_types_storage_num_entries,
379            search_graph,
380            nested_goals: Default::default(),
381            origin_span: I::Span::dummy(),
382            tainted: Ok(()),
383            inspect: canonical_goal_evaluation.new_goal_evaluation_step(var_values),
384        };
385
386        let result = f(&mut ecx, input.goal);
387        ecx.inspect.probe_final_state(ecx.delegate, ecx.max_input_universe);
388        canonical_goal_evaluation.goal_evaluation_step(ecx.inspect);
389
390        // When creating a query response we clone the opaque type constraints
391        // instead of taking them. This would cause an ICE here, since we have
392        // assertions against dropping an `InferCtxt` without taking opaques.
393        // FIXME: Once we remove support for the old impl we can remove this.
394        // FIXME: Could we make `build_with_canonical` into `enter_with_canonical` and call this at the end?
395        delegate.reset_opaque_types();
396
397        result
398    }
399
400    /// Recursively evaluates `goal`, returning whether any inference vars have
401    /// been constrained and the certainty of the result.
402    fn evaluate_goal(
403        &mut self,
404        goal_evaluation_kind: GoalEvaluationKind,
405        source: GoalSource,
406        goal: Goal<I, I::Predicate>,
407        stalled_on: Option<GoalStalledOn<I>>,
408    ) -> Result<GoalEvaluation<I>, NoSolution> {
409        let (normalization_nested_goals, goal_evaluation) =
410            self.evaluate_goal_raw(goal_evaluation_kind, source, goal, stalled_on)?;
411        assert!(normalization_nested_goals.is_empty());
412        Ok(goal_evaluation)
413    }
414
415    /// Recursively evaluates `goal`, returning the nested goals in case
416    /// the nested goal is a `NormalizesTo` goal.
417    ///
418    /// As all other goal kinds do not return any nested goals and
419    /// `NormalizesTo` is only used by `AliasRelate`, all other callsites
420    /// should use [`EvalCtxt::evaluate_goal`] which discards that empty
421    /// storage.
422    pub(super) fn evaluate_goal_raw(
423        &mut self,
424        goal_evaluation_kind: GoalEvaluationKind,
425        source: GoalSource,
426        goal: Goal<I, I::Predicate>,
427        stalled_on: Option<GoalStalledOn<I>>,
428    ) -> Result<(NestedNormalizationGoals<I>, GoalEvaluation<I>), NoSolution> {
429        // If we have run this goal before, and it was stalled, check that any of the goal's
430        // args have changed. Otherwise, we don't need to re-run the goal because it'll remain
431        // stalled, since it'll canonicalize the same way and evaluation is pure.
432        if let Some(stalled_on) = stalled_on
433            && !stalled_on.stalled_vars.iter().any(|value| self.delegate.is_changed_arg(*value))
434            && !self
435                .delegate
436                .opaque_types_storage_num_entries()
437                .needs_reevaluation(stalled_on.num_opaques)
438        {
439            return Ok((
440                NestedNormalizationGoals::empty(),
441                GoalEvaluation {
442                    certainty: Certainty::Maybe(stalled_on.stalled_cause),
443                    has_changed: HasChanged::No,
444                    stalled_on: Some(stalled_on),
445                },
446            ));
447        }
448
449        let (orig_values, canonical_goal) = self.canonicalize_goal(goal);
450        let mut goal_evaluation =
451            self.inspect.new_goal_evaluation(goal, &orig_values, goal_evaluation_kind);
452        let canonical_result = self.search_graph.evaluate_goal(
453            self.cx(),
454            canonical_goal,
455            self.step_kind_for_source(source),
456            &mut goal_evaluation,
457        );
458        goal_evaluation.query_result(canonical_result);
459        self.inspect.goal_evaluation(goal_evaluation);
460        let response = match canonical_result {
461            Err(e) => return Err(e),
462            Ok(response) => response,
463        };
464
465        let has_changed =
466            if !has_only_region_constraints(response) { HasChanged::Yes } else { HasChanged::No };
467
468        let (normalization_nested_goals, certainty) =
469            self.instantiate_and_apply_query_response(goal.param_env, &orig_values, response);
470
471        // FIXME: We previously had an assert here that checked that recomputing
472        // a goal after applying its constraints did not change its response.
473        //
474        // This assert was removed as it did not hold for goals constraining
475        // an inference variable to a recursive alias, e.g. in
476        // tests/ui/traits/next-solver/overflow/recursive-self-normalization.rs.
477        //
478        // Once we have decided on how to handle trait-system-refactor-initiative#75,
479        // we should re-add an assert here.
480
481        let stalled_on = match certainty {
482            Certainty::Yes => None,
483            Certainty::Maybe(stalled_cause) => match has_changed {
484                // FIXME: We could recompute a *new* set of stalled variables by walking
485                // through the orig values, resolving, and computing the root vars of anything
486                // that is not resolved. Only when *these* have changed is it meaningful
487                // to recompute this goal.
488                HasChanged::Yes => None,
489                HasChanged::No => {
490                    let mut stalled_vars = orig_values;
491
492                    // Remove the canonicalized universal vars, since we only care about stalled existentials.
493                    stalled_vars.retain(|arg| match arg.kind() {
494                        ty::GenericArgKind::Type(ty) => matches!(ty.kind(), ty::Infer(_)),
495                        ty::GenericArgKind::Const(ct) => {
496                            matches!(ct.kind(), ty::ConstKind::Infer(_))
497                        }
498                        // Lifetimes can never stall goals.
499                        ty::GenericArgKind::Lifetime(_) => false,
500                    });
501
502                    // Remove the unconstrained RHS arg, which is expected to have changed.
503                    if let Some(normalizes_to) = goal.predicate.as_normalizes_to() {
504                        let normalizes_to = normalizes_to.skip_binder();
505                        let rhs_arg: I::GenericArg = normalizes_to.term.into();
506                        let idx = stalled_vars
507                            .iter()
508                            .rposition(|arg| *arg == rhs_arg)
509                            .expect("expected unconstrained arg");
510                        stalled_vars.swap_remove(idx);
511                    }
512
513                    Some(GoalStalledOn {
514                        num_opaques: canonical_goal
515                            .canonical
516                            .value
517                            .predefined_opaques_in_body
518                            .opaque_types
519                            .len(),
520                        stalled_vars,
521                        stalled_cause,
522                    })
523                }
524            },
525        };
526
527        Ok((normalization_nested_goals, GoalEvaluation { certainty, has_changed, stalled_on }))
528    }
529
530    pub(super) fn compute_goal(&mut self, goal: Goal<I, I::Predicate>) -> QueryResult<I> {
531        let Goal { param_env, predicate } = goal;
532        let kind = predicate.kind();
533        if let Some(kind) = kind.no_bound_vars() {
534            match kind {
535                ty::PredicateKind::Clause(ty::ClauseKind::Trait(predicate)) => {
536                    self.compute_trait_goal(Goal { param_env, predicate }).map(|(r, _via)| r)
537                }
538                ty::PredicateKind::Clause(ty::ClauseKind::HostEffect(predicate)) => {
539                    self.compute_host_effect_goal(Goal { param_env, predicate })
540                }
541                ty::PredicateKind::Clause(ty::ClauseKind::Projection(predicate)) => {
542                    self.compute_projection_goal(Goal { param_env, predicate })
543                }
544                ty::PredicateKind::Clause(ty::ClauseKind::TypeOutlives(predicate)) => {
545                    self.compute_type_outlives_goal(Goal { param_env, predicate })
546                }
547                ty::PredicateKind::Clause(ty::ClauseKind::RegionOutlives(predicate)) => {
548                    self.compute_region_outlives_goal(Goal { param_env, predicate })
549                }
550                ty::PredicateKind::Clause(ty::ClauseKind::ConstArgHasType(ct, ty)) => {
551                    self.compute_const_arg_has_type_goal(Goal { param_env, predicate: (ct, ty) })
552                }
553                ty::PredicateKind::Subtype(predicate) => {
554                    self.compute_subtype_goal(Goal { param_env, predicate })
555                }
556                ty::PredicateKind::Coerce(predicate) => {
557                    self.compute_coerce_goal(Goal { param_env, predicate })
558                }
559                ty::PredicateKind::DynCompatible(trait_def_id) => {
560                    self.compute_dyn_compatible_goal(trait_def_id)
561                }
562                ty::PredicateKind::Clause(ty::ClauseKind::WellFormed(term)) => {
563                    self.compute_well_formed_goal(Goal { param_env, predicate: term })
564                }
565                ty::PredicateKind::Clause(ty::ClauseKind::ConstEvaluatable(ct)) => {
566                    self.compute_const_evaluatable_goal(Goal { param_env, predicate: ct })
567                }
568                ty::PredicateKind::ConstEquate(_, _) => {
569                    panic!("ConstEquate should not be emitted when `-Znext-solver` is active")
570                }
571                ty::PredicateKind::NormalizesTo(predicate) => {
572                    self.compute_normalizes_to_goal(Goal { param_env, predicate })
573                }
574                ty::PredicateKind::AliasRelate(lhs, rhs, direction) => self
575                    .compute_alias_relate_goal(Goal {
576                        param_env,
577                        predicate: (lhs, rhs, direction),
578                    }),
579                ty::PredicateKind::Ambiguous => {
580                    self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
581                }
582            }
583        } else {
584            self.enter_forall(kind, |ecx, kind| {
585                let goal = goal.with(ecx.cx(), ty::Binder::dummy(kind));
586                ecx.add_goal(GoalSource::InstantiateHigherRanked, goal);
587                ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
588            })
589        }
590    }
591
592    // Recursively evaluates all the goals added to this `EvalCtxt` to completion, returning
593    // the certainty of all the goals.
594    #[instrument(level = "trace", skip(self))]
595    pub(super) fn try_evaluate_added_goals(&mut self) -> Result<Certainty, NoSolution> {
596        let mut response = Ok(Certainty::overflow(false));
597        for _ in 0..FIXPOINT_STEP_LIMIT {
598            // FIXME: This match is a bit ugly, it might be nice to change the inspect
599            // stuff to use a closure instead. which should hopefully simplify this a bit.
600            match self.evaluate_added_goals_step() {
601                Ok(Some(cert)) => {
602                    response = Ok(cert);
603                    break;
604                }
605                Ok(None) => {}
606                Err(NoSolution) => {
607                    response = Err(NoSolution);
608                    break;
609                }
610            }
611        }
612
613        if response.is_err() {
614            self.tainted = Err(NoSolution);
615        }
616
617        response
618    }
619
620    /// Iterate over all added goals: returning `Ok(Some(_))` in case we can stop rerunning.
621    ///
622    /// Goals for the next step get directly added to the nested goals of the `EvalCtxt`.
623    fn evaluate_added_goals_step(&mut self) -> Result<Option<Certainty>, NoSolution> {
624        let cx = self.cx();
625        // If this loop did not result in any progress, what's our final certainty.
626        let mut unchanged_certainty = Some(Certainty::Yes);
627        for (source, goal, stalled_on) in mem::take(&mut self.nested_goals) {
628            if let Some(certainty) = self.delegate.compute_goal_fast_path(goal, self.origin_span) {
629                match certainty {
630                    Certainty::Yes => {}
631                    Certainty::Maybe(_) => {
632                        self.nested_goals.push((source, goal, None));
633                        unchanged_certainty = unchanged_certainty.map(|c| c.and(certainty));
634                    }
635                }
636                continue;
637            }
638
639            // We treat normalizes-to goals specially here. In each iteration we take the
640            // RHS of the projection, replace it with a fresh inference variable, and only
641            // after evaluating that goal do we equate the fresh inference variable with the
642            // actual RHS of the predicate.
643            //
644            // This is both to improve caching, and to avoid using the RHS of the
645            // projection predicate to influence the normalizes-to candidate we select.
646            //
647            // Forgetting to replace the RHS with a fresh inference variable when we evaluate
648            // this goal results in an ICE.
649            if let Some(pred) = goal.predicate.as_normalizes_to() {
650                // We should never encounter higher-ranked normalizes-to goals.
651                let pred = pred.no_bound_vars().unwrap();
652                // Replace the goal with an unconstrained infer var, so the
653                // RHS does not affect projection candidate assembly.
654                let unconstrained_rhs = self.next_term_infer_of_kind(pred.term);
655                let unconstrained_goal =
656                    goal.with(cx, ty::NormalizesTo { alias: pred.alias, term: unconstrained_rhs });
657
658                let (
659                    NestedNormalizationGoals(nested_goals),
660                    GoalEvaluation { certainty, stalled_on, has_changed: _ },
661                ) = self.evaluate_goal_raw(
662                    GoalEvaluationKind::Nested,
663                    source,
664                    unconstrained_goal,
665                    stalled_on,
666                )?;
667                // Add the nested goals from normalization to our own nested goals.
668                trace!(?nested_goals);
669                self.nested_goals.extend(nested_goals.into_iter().map(|(s, g)| (s, g, None)));
670
671                // Finally, equate the goal's RHS with the unconstrained var.
672                //
673                // SUBTLE:
674                // We structurally relate aliases here. This is necessary
675                // as we otherwise emit a nested `AliasRelate` goal in case the
676                // returned term is a rigid alias, resulting in overflow.
677                //
678                // It is correct as both `goal.predicate.term` and `unconstrained_rhs`
679                // start out as an unconstrained inference variable so any aliases get
680                // fully normalized when instantiating it.
681                //
682                // FIXME: Strictly speaking this may be incomplete if the normalized-to
683                // type contains an ambiguous alias referencing bound regions. We should
684                // consider changing this to only use "shallow structural equality".
685                self.eq_structurally_relating_aliases(
686                    goal.param_env,
687                    pred.term,
688                    unconstrained_rhs,
689                )?;
690
691                // We only look at the `projection_ty` part here rather than
692                // looking at the "has changed" return from evaluate_goal,
693                // because we expect the `unconstrained_rhs` part of the predicate
694                // to have changed -- that means we actually normalized successfully!
695                // FIXME: Do we need to eagerly resolve here? Or should we check
696                // if the cache key has any changed vars?
697                let with_resolved_vars = self.resolve_vars_if_possible(goal);
698                if pred.alias != goal.predicate.as_normalizes_to().unwrap().skip_binder().alias {
699                    unchanged_certainty = None;
700                }
701
702                match certainty {
703                    Certainty::Yes => {}
704                    Certainty::Maybe(_) => {
705                        self.nested_goals.push((source, with_resolved_vars, stalled_on));
706                        unchanged_certainty = unchanged_certainty.map(|c| c.and(certainty));
707                    }
708                }
709            } else {
710                let GoalEvaluation { certainty, has_changed, stalled_on } =
711                    self.evaluate_goal(GoalEvaluationKind::Nested, source, goal, stalled_on)?;
712                if has_changed == HasChanged::Yes {
713                    unchanged_certainty = None;
714                }
715
716                match certainty {
717                    Certainty::Yes => {}
718                    Certainty::Maybe(_) => {
719                        self.nested_goals.push((source, goal, stalled_on));
720                        unchanged_certainty = unchanged_certainty.map(|c| c.and(certainty));
721                    }
722                }
723            }
724        }
725
726        Ok(unchanged_certainty)
727    }
728
729    /// Record impl args in the proof tree for later access by `InspectCandidate`.
730    pub(crate) fn record_impl_args(&mut self, impl_args: I::GenericArgs) {
731        self.inspect.record_impl_args(self.delegate, self.max_input_universe, impl_args)
732    }
733
734    pub(super) fn cx(&self) -> I {
735        self.delegate.cx()
736    }
737
738    #[instrument(level = "debug", skip(self))]
739    pub(super) fn add_goal(&mut self, source: GoalSource, mut goal: Goal<I, I::Predicate>) {
740        goal.predicate =
741            goal.predicate.fold_with(&mut ReplaceAliasWithInfer::new(self, source, goal.param_env));
742        self.inspect.add_goal(self.delegate, self.max_input_universe, source, goal);
743        self.nested_goals.push((source, goal, None));
744    }
745
746    #[instrument(level = "trace", skip(self, goals))]
747    pub(super) fn add_goals(
748        &mut self,
749        source: GoalSource,
750        goals: impl IntoIterator<Item = Goal<I, I::Predicate>>,
751    ) {
752        for goal in goals {
753            self.add_goal(source, goal);
754        }
755    }
756
757    pub(super) fn next_region_var(&mut self) -> I::Region {
758        let region = self.delegate.next_region_infer();
759        self.inspect.add_var_value(region);
760        region
761    }
762
763    pub(super) fn next_ty_infer(&mut self) -> I::Ty {
764        let ty = self.delegate.next_ty_infer();
765        self.inspect.add_var_value(ty);
766        ty
767    }
768
769    pub(super) fn next_const_infer(&mut self) -> I::Const {
770        let ct = self.delegate.next_const_infer();
771        self.inspect.add_var_value(ct);
772        ct
773    }
774
775    /// Returns a ty infer or a const infer depending on whether `kind` is a `Ty` or `Const`.
776    /// If `kind` is an integer inference variable this will still return a ty infer var.
777    pub(super) fn next_term_infer_of_kind(&mut self, term: I::Term) -> I::Term {
778        match term.kind() {
779            ty::TermKind::Ty(_) => self.next_ty_infer().into(),
780            ty::TermKind::Const(_) => self.next_const_infer().into(),
781        }
782    }
783
784    /// Is the projection predicate is of the form `exists<T> <Ty as Trait>::Assoc = T`.
785    ///
786    /// This is the case if the `term` does not occur in any other part of the predicate
787    /// and is able to name all other placeholder and inference variables.
788    #[instrument(level = "trace", skip(self), ret)]
789    pub(super) fn term_is_fully_unconstrained(&self, goal: Goal<I, ty::NormalizesTo<I>>) -> bool {
790        let universe_of_term = match goal.predicate.term.kind() {
791            ty::TermKind::Ty(ty) => {
792                if let ty::Infer(ty::TyVar(vid)) = ty.kind() {
793                    self.delegate.universe_of_ty(vid).unwrap()
794                } else {
795                    return false;
796                }
797            }
798            ty::TermKind::Const(ct) => {
799                if let ty::ConstKind::Infer(ty::InferConst::Var(vid)) = ct.kind() {
800                    self.delegate.universe_of_ct(vid).unwrap()
801                } else {
802                    return false;
803                }
804            }
805        };
806
807        struct ContainsTermOrNotNameable<'a, D: SolverDelegate<Interner = I>, I: Interner> {
808            term: I::Term,
809            universe_of_term: ty::UniverseIndex,
810            delegate: &'a D,
811            cache: HashSet<I::Ty>,
812        }
813
814        impl<D: SolverDelegate<Interner = I>, I: Interner> ContainsTermOrNotNameable<'_, D, I> {
815            fn check_nameable(&self, universe: ty::UniverseIndex) -> ControlFlow<()> {
816                if self.universe_of_term.can_name(universe) {
817                    ControlFlow::Continue(())
818                } else {
819                    ControlFlow::Break(())
820                }
821            }
822        }
823
824        impl<D: SolverDelegate<Interner = I>, I: Interner> TypeVisitor<I>
825            for ContainsTermOrNotNameable<'_, D, I>
826        {
827            type Result = ControlFlow<()>;
828            fn visit_ty(&mut self, t: I::Ty) -> Self::Result {
829                if self.cache.contains(&t) {
830                    return ControlFlow::Continue(());
831                }
832
833                match t.kind() {
834                    ty::Infer(ty::TyVar(vid)) => {
835                        if let ty::TermKind::Ty(term) = self.term.kind()
836                            && let ty::Infer(ty::TyVar(term_vid)) = term.kind()
837                            && self.delegate.root_ty_var(vid) == self.delegate.root_ty_var(term_vid)
838                        {
839                            return ControlFlow::Break(());
840                        }
841
842                        self.check_nameable(self.delegate.universe_of_ty(vid).unwrap())?;
843                    }
844                    ty::Placeholder(p) => self.check_nameable(p.universe())?,
845                    _ => {
846                        if t.has_non_region_infer() || t.has_placeholders() {
847                            t.super_visit_with(self)?
848                        }
849                    }
850                }
851
852                assert!(self.cache.insert(t));
853                ControlFlow::Continue(())
854            }
855
856            fn visit_const(&mut self, c: I::Const) -> Self::Result {
857                match c.kind() {
858                    ty::ConstKind::Infer(ty::InferConst::Var(vid)) => {
859                        if let ty::TermKind::Const(term) = self.term.kind()
860                            && let ty::ConstKind::Infer(ty::InferConst::Var(term_vid)) = term.kind()
861                            && self.delegate.root_const_var(vid)
862                                == self.delegate.root_const_var(term_vid)
863                        {
864                            return ControlFlow::Break(());
865                        }
866
867                        self.check_nameable(self.delegate.universe_of_ct(vid).unwrap())
868                    }
869                    ty::ConstKind::Placeholder(p) => self.check_nameable(p.universe()),
870                    _ => {
871                        if c.has_non_region_infer() || c.has_placeholders() {
872                            c.super_visit_with(self)
873                        } else {
874                            ControlFlow::Continue(())
875                        }
876                    }
877                }
878            }
879
880            fn visit_predicate(&mut self, p: I::Predicate) -> Self::Result {
881                if p.has_non_region_infer() || p.has_placeholders() {
882                    p.super_visit_with(self)
883                } else {
884                    ControlFlow::Continue(())
885                }
886            }
887
888            fn visit_clauses(&mut self, c: I::Clauses) -> Self::Result {
889                if c.has_non_region_infer() || c.has_placeholders() {
890                    c.super_visit_with(self)
891                } else {
892                    ControlFlow::Continue(())
893                }
894            }
895        }
896
897        let mut visitor = ContainsTermOrNotNameable {
898            delegate: self.delegate,
899            universe_of_term,
900            term: goal.predicate.term,
901            cache: Default::default(),
902        };
903        goal.predicate.alias.visit_with(&mut visitor).is_continue()
904            && goal.param_env.visit_with(&mut visitor).is_continue()
905    }
906
907    #[instrument(level = "trace", skip(self, param_env), ret)]
908    pub(super) fn eq<T: Relate<I>>(
909        &mut self,
910        param_env: I::ParamEnv,
911        lhs: T,
912        rhs: T,
913    ) -> Result<(), NoSolution> {
914        self.relate(param_env, lhs, ty::Variance::Invariant, rhs)
915    }
916
917    /// This should be used when relating a rigid alias with another type.
918    ///
919    /// Normally we emit a nested `AliasRelate` when equating an inference
920    /// variable and an alias. This causes us to instead constrain the inference
921    /// variable to the alias without emitting a nested alias relate goals.
922    #[instrument(level = "trace", skip(self, param_env), ret)]
923    pub(super) fn relate_rigid_alias_non_alias(
924        &mut self,
925        param_env: I::ParamEnv,
926        alias: ty::AliasTerm<I>,
927        variance: ty::Variance,
928        term: I::Term,
929    ) -> Result<(), NoSolution> {
930        // NOTE: this check is purely an optimization, the structural eq would
931        // always fail if the term is not an inference variable.
932        if term.is_infer() {
933            let cx = self.cx();
934            // We need to relate `alias` to `term` treating only the outermost
935            // constructor as rigid, relating any contained generic arguments as
936            // normal. We do this by first structurally equating the `term`
937            // with the alias constructor instantiated with unconstrained infer vars,
938            // and then relate this with the whole `alias`.
939            //
940            // Alternatively we could modify `Equate` for this case by adding another
941            // variant to `StructurallyRelateAliases`.
942            let identity_args = self.fresh_args_for_item(alias.def_id);
943            let rigid_ctor = ty::AliasTerm::new_from_args(cx, alias.def_id, identity_args);
944            let ctor_term = rigid_ctor.to_term(cx);
945            let obligations = self.delegate.eq_structurally_relating_aliases(
946                param_env,
947                term,
948                ctor_term,
949                self.origin_span,
950            )?;
951            debug_assert!(obligations.is_empty());
952            self.relate(param_env, alias, variance, rigid_ctor)
953        } else {
954            Err(NoSolution)
955        }
956    }
957
958    /// This sohuld only be used when we're either instantiating a previously
959    /// unconstrained "return value" or when we're sure that all aliases in
960    /// the types are rigid.
961    #[instrument(level = "trace", skip(self, param_env), ret)]
962    pub(super) fn eq_structurally_relating_aliases<T: Relate<I>>(
963        &mut self,
964        param_env: I::ParamEnv,
965        lhs: T,
966        rhs: T,
967    ) -> Result<(), NoSolution> {
968        let result = self.delegate.eq_structurally_relating_aliases(
969            param_env,
970            lhs,
971            rhs,
972            self.origin_span,
973        )?;
974        assert_eq!(result, vec![]);
975        Ok(())
976    }
977
978    #[instrument(level = "trace", skip(self, param_env), ret)]
979    pub(super) fn sub<T: Relate<I>>(
980        &mut self,
981        param_env: I::ParamEnv,
982        sub: T,
983        sup: T,
984    ) -> Result<(), NoSolution> {
985        self.relate(param_env, sub, ty::Variance::Covariant, sup)
986    }
987
988    #[instrument(level = "trace", skip(self, param_env), ret)]
989    pub(super) fn relate<T: Relate<I>>(
990        &mut self,
991        param_env: I::ParamEnv,
992        lhs: T,
993        variance: ty::Variance,
994        rhs: T,
995    ) -> Result<(), NoSolution> {
996        let goals = self.delegate.relate(param_env, lhs, variance, rhs, self.origin_span)?;
997        for &goal in goals.iter() {
998            let source = match goal.predicate.kind().skip_binder() {
999                ty::PredicateKind::Subtype { .. } | ty::PredicateKind::AliasRelate(..) => {
1000                    GoalSource::TypeRelating
1001                }
1002                // FIXME(-Znext-solver=coinductive): should these WF goals also be unproductive?
1003                ty::PredicateKind::Clause(ty::ClauseKind::WellFormed(_)) => GoalSource::Misc,
1004                p => unreachable!("unexpected nested goal in `relate`: {p:?}"),
1005            };
1006            self.add_goal(source, goal);
1007        }
1008        Ok(())
1009    }
1010
1011    /// Equates two values returning the nested goals without adding them
1012    /// to the nested goals of the `EvalCtxt`.
1013    ///
1014    /// If possible, try using `eq` instead which automatically handles nested
1015    /// goals correctly.
1016    #[instrument(level = "trace", skip(self, param_env), ret)]
1017    pub(super) fn eq_and_get_goals<T: Relate<I>>(
1018        &self,
1019        param_env: I::ParamEnv,
1020        lhs: T,
1021        rhs: T,
1022    ) -> Result<Vec<Goal<I, I::Predicate>>, NoSolution> {
1023        Ok(self.delegate.relate(param_env, lhs, ty::Variance::Invariant, rhs, self.origin_span)?)
1024    }
1025
1026    pub(super) fn instantiate_binder_with_infer<T: TypeFoldable<I> + Copy>(
1027        &self,
1028        value: ty::Binder<I, T>,
1029    ) -> T {
1030        self.delegate.instantiate_binder_with_infer(value)
1031    }
1032
1033    /// `enter_forall`, but takes `&mut self` and passes it back through the
1034    /// callback since it can't be aliased during the call.
1035    pub(super) fn enter_forall<T: TypeFoldable<I>, U>(
1036        &mut self,
1037        value: ty::Binder<I, T>,
1038        f: impl FnOnce(&mut Self, T) -> U,
1039    ) -> U {
1040        self.delegate.enter_forall(value, |value| f(self, value))
1041    }
1042
1043    pub(super) fn resolve_vars_if_possible<T>(&self, value: T) -> T
1044    where
1045        T: TypeFoldable<I>,
1046    {
1047        self.delegate.resolve_vars_if_possible(value)
1048    }
1049
1050    pub(super) fn eager_resolve_region(&self, r: I::Region) -> I::Region {
1051        if let ty::ReVar(vid) = r.kind() {
1052            self.delegate.opportunistic_resolve_lt_var(vid)
1053        } else {
1054            r
1055        }
1056    }
1057
1058    pub(super) fn fresh_args_for_item(&mut self, def_id: I::DefId) -> I::GenericArgs {
1059        let args = self.delegate.fresh_args_for_item(def_id);
1060        for arg in args.iter() {
1061            self.inspect.add_var_value(arg);
1062        }
1063        args
1064    }
1065
1066    pub(super) fn register_ty_outlives(&self, ty: I::Ty, lt: I::Region) {
1067        self.delegate.register_ty_outlives(ty, lt, self.origin_span);
1068    }
1069
1070    pub(super) fn register_region_outlives(&self, a: I::Region, b: I::Region) {
1071        // `'a: 'b` ==> `'b <= 'a`
1072        self.delegate.sub_regions(b, a, self.origin_span);
1073    }
1074
1075    /// Computes the list of goals required for `arg` to be well-formed
1076    pub(super) fn well_formed_goals(
1077        &self,
1078        param_env: I::ParamEnv,
1079        term: I::Term,
1080    ) -> Option<Vec<Goal<I, I::Predicate>>> {
1081        self.delegate.well_formed_goals(param_env, term)
1082    }
1083
1084    pub(super) fn trait_ref_is_knowable(
1085        &mut self,
1086        param_env: I::ParamEnv,
1087        trait_ref: ty::TraitRef<I>,
1088    ) -> Result<bool, NoSolution> {
1089        let delegate = self.delegate;
1090        let lazily_normalize_ty = |ty| self.structurally_normalize_ty(param_env, ty);
1091        coherence::trait_ref_is_knowable(&**delegate, trait_ref, lazily_normalize_ty)
1092            .map(|is_knowable| is_knowable.is_ok())
1093    }
1094
1095    pub(super) fn fetch_eligible_assoc_item(
1096        &self,
1097        goal_trait_ref: ty::TraitRef<I>,
1098        trait_assoc_def_id: I::DefId,
1099        impl_def_id: I::DefId,
1100    ) -> Result<Option<I::DefId>, I::ErrorGuaranteed> {
1101        self.delegate.fetch_eligible_assoc_item(goal_trait_ref, trait_assoc_def_id, impl_def_id)
1102    }
1103
1104    pub(super) fn register_hidden_type_in_storage(
1105        &mut self,
1106        opaque_type_key: ty::OpaqueTypeKey<I>,
1107        hidden_ty: I::Ty,
1108    ) -> Option<I::Ty> {
1109        self.delegate.register_hidden_type_in_storage(opaque_type_key, hidden_ty, self.origin_span)
1110    }
1111
1112    pub(super) fn add_item_bounds_for_hidden_type(
1113        &mut self,
1114        opaque_def_id: I::DefId,
1115        opaque_args: I::GenericArgs,
1116        param_env: I::ParamEnv,
1117        hidden_ty: I::Ty,
1118    ) {
1119        let mut goals = Vec::new();
1120        self.delegate.add_item_bounds_for_hidden_type(
1121            opaque_def_id,
1122            opaque_args,
1123            param_env,
1124            hidden_ty,
1125            &mut goals,
1126        );
1127        self.add_goals(GoalSource::AliasWellFormed, goals);
1128    }
1129
1130    // Do something for each opaque/hidden pair defined with `def_id` in the
1131    // current inference context.
1132    pub(super) fn probe_existing_opaque_ty(
1133        &mut self,
1134        key: ty::OpaqueTypeKey<I>,
1135    ) -> Option<(ty::OpaqueTypeKey<I>, I::Ty)> {
1136        // We shouldn't have any duplicate entries when using
1137        // this function during `TypingMode::Analysis`.
1138        let duplicate_entries = self.delegate.clone_duplicate_opaque_types();
1139        assert!(duplicate_entries.is_empty(), "unexpected duplicates: {duplicate_entries:?}");
1140        let mut matching = self.delegate.clone_opaque_types_lookup_table().into_iter().filter(
1141            |(candidate_key, _)| {
1142                candidate_key.def_id == key.def_id
1143                    && DeepRejectCtxt::relate_rigid_rigid(self.cx())
1144                        .args_may_unify(candidate_key.args, key.args)
1145            },
1146        );
1147        let first = matching.next();
1148        let second = matching.next();
1149        assert_eq!(second, None);
1150        first
1151    }
1152
1153    // Try to evaluate a const, or return `None` if the const is too generic.
1154    // This doesn't mean the const isn't evaluatable, though, and should be treated
1155    // as an ambiguity rather than no-solution.
1156    pub(super) fn evaluate_const(
1157        &self,
1158        param_env: I::ParamEnv,
1159        uv: ty::UnevaluatedConst<I>,
1160    ) -> Option<I::Const> {
1161        self.delegate.evaluate_const(param_env, uv)
1162    }
1163
1164    pub(super) fn is_transmutable(
1165        &mut self,
1166        dst: I::Ty,
1167        src: I::Ty,
1168        assume: I::Const,
1169    ) -> Result<Certainty, NoSolution> {
1170        self.delegate.is_transmutable(dst, src, assume)
1171    }
1172
1173    pub(super) fn replace_bound_vars<T: TypeFoldable<I>>(
1174        &self,
1175        t: T,
1176        universes: &mut Vec<Option<ty::UniverseIndex>>,
1177    ) -> T {
1178        BoundVarReplacer::replace_bound_vars(&**self.delegate, universes, t).0
1179    }
1180}
1181
1182/// Eagerly replace aliases with inference variables, emitting `AliasRelate`
1183/// goals, used when adding goals to the `EvalCtxt`. We compute the
1184/// `AliasRelate` goals before evaluating the actual goal to get all the
1185/// constraints we can.
1186///
1187/// This is a performance optimization to more eagerly detect cycles during trait
1188/// solving. See tests/ui/traits/next-solver/cycles/cycle-modulo-ambig-aliases.rs.
1189///
1190/// The emitted goals get evaluated in the context of the parent goal; by
1191/// replacing aliases in nested goals we essentially pull the normalization out of
1192/// the nested goal. We want to treat the goal as if the normalization still happens
1193/// inside of the nested goal by inheriting the `step_kind` of the nested goal and
1194/// storing it in the `GoalSource` of the emitted `AliasRelate` goals.
1195/// This is necessary for tests/ui/sized/coinductive-1.rs to compile.
1196struct ReplaceAliasWithInfer<'me, 'a, D, I>
1197where
1198    D: SolverDelegate<Interner = I>,
1199    I: Interner,
1200{
1201    ecx: &'me mut EvalCtxt<'a, D>,
1202    param_env: I::ParamEnv,
1203    normalization_goal_source: GoalSource,
1204    cache: HashMap<I::Ty, I::Ty>,
1205}
1206
1207impl<'me, 'a, D, I> ReplaceAliasWithInfer<'me, 'a, D, I>
1208where
1209    D: SolverDelegate<Interner = I>,
1210    I: Interner,
1211{
1212    fn new(
1213        ecx: &'me mut EvalCtxt<'a, D>,
1214        for_goal_source: GoalSource,
1215        param_env: I::ParamEnv,
1216    ) -> Self {
1217        let step_kind = ecx.step_kind_for_source(for_goal_source);
1218        ReplaceAliasWithInfer {
1219            ecx,
1220            param_env,
1221            normalization_goal_source: GoalSource::NormalizeGoal(step_kind),
1222            cache: Default::default(),
1223        }
1224    }
1225}
1226
1227impl<D, I> TypeFolder<I> for ReplaceAliasWithInfer<'_, '_, D, I>
1228where
1229    D: SolverDelegate<Interner = I>,
1230    I: Interner,
1231{
1232    fn cx(&self) -> I {
1233        self.ecx.cx()
1234    }
1235
1236    fn fold_ty(&mut self, ty: I::Ty) -> I::Ty {
1237        match ty.kind() {
1238            ty::Alias(..) if !ty.has_escaping_bound_vars() => {
1239                let infer_ty = self.ecx.next_ty_infer();
1240                let normalizes_to = ty::PredicateKind::AliasRelate(
1241                    ty.into(),
1242                    infer_ty.into(),
1243                    ty::AliasRelationDirection::Equate,
1244                );
1245                self.ecx.add_goal(
1246                    self.normalization_goal_source,
1247                    Goal::new(self.cx(), self.param_env, normalizes_to),
1248                );
1249                infer_ty
1250            }
1251            _ => {
1252                if !ty.has_aliases() {
1253                    ty
1254                } else if let Some(&entry) = self.cache.get(&ty) {
1255                    return entry;
1256                } else {
1257                    let res = ty.super_fold_with(self);
1258                    assert!(self.cache.insert(ty, res).is_none());
1259                    res
1260                }
1261            }
1262        }
1263    }
1264
1265    fn fold_const(&mut self, ct: I::Const) -> I::Const {
1266        match ct.kind() {
1267            ty::ConstKind::Unevaluated(..) if !ct.has_escaping_bound_vars() => {
1268                let infer_ct = self.ecx.next_const_infer();
1269                let normalizes_to = ty::PredicateKind::AliasRelate(
1270                    ct.into(),
1271                    infer_ct.into(),
1272                    ty::AliasRelationDirection::Equate,
1273                );
1274                self.ecx.add_goal(
1275                    self.normalization_goal_source,
1276                    Goal::new(self.cx(), self.param_env, normalizes_to),
1277                );
1278                infer_ct
1279            }
1280            _ => ct.super_fold_with(self),
1281        }
1282    }
1283
1284    fn fold_predicate(&mut self, predicate: I::Predicate) -> I::Predicate {
1285        if predicate.allow_normalization() { predicate.super_fold_with(self) } else { predicate }
1286    }
1287}