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#[derive(Debug, Copy, Clone)]
39enum CurrentGoalKind {
40 Misc,
41 CoinductiveTrait,
46 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 delegate: &'a D,
93
94 variables: I::CanonicalVarKinds,
97
98 current_goal_kind: CurrentGoalKind,
101 pub(super) var_values: CanonicalVarValues<I>,
102
103 pub(super) max_input_universe: ty::UniverseIndex,
113 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 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 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 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 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 pub(super) fn step_kind_for_source(&self, source: GoalSource) -> PathKind {
256 match source {
257 GoalSource::Misc => PathKind::Unknown,
265 GoalSource::NormalizeGoal(path_kind) => path_kind,
266 GoalSource::ImplWhereBound => match self.current_goal_kind {
267 CurrentGoalKind::CoinductiveTrait => PathKind::Coinductive,
270 CurrentGoalKind::NormalizesTo => PathKind::Inductive,
278 CurrentGoalKind::Misc => PathKind::Unknown,
282 },
283 GoalSource::TypeRelating => PathKind::Inductive,
287 GoalSource::InstantiateHigherRanked => PathKind::Inductive,
290 GoalSource::AliasBoundConstCondition | GoalSource::AliasWellFormed => PathKind::Unknown,
294 }
295 }
296
297 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 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 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 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 delegate.reset_opaque_types();
396
397 result
398 }
399
400 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 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 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 let stalled_on = match certainty {
482 Certainty::Yes => None,
483 Certainty::Maybe(stalled_cause) => match has_changed {
484 HasChanged::Yes => None,
489 HasChanged::No => {
490 let mut stalled_vars = orig_values;
491
492 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 ty::GenericArgKind::Lifetime(_) => false,
500 });
501
502 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 #[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 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 fn evaluate_added_goals_step(&mut self) -> Result<Option<Certainty>, NoSolution> {
624 let cx = self.cx();
625 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 if let Some(pred) = goal.predicate.as_normalizes_to() {
650 let pred = pred.no_bound_vars().unwrap();
652 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 trace!(?nested_goals);
669 self.nested_goals.extend(nested_goals.into_iter().map(|(s, g)| (s, g, None)));
670
671 self.eq_structurally_relating_aliases(
686 goal.param_env,
687 pred.term,
688 unconstrained_rhs,
689 )?;
690
691 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 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 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 #[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 #[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 if term.is_infer() {
933 let cx = self.cx();
934 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 #[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 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 #[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 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 self.delegate.sub_regions(b, a, self.origin_span);
1073 }
1074
1075 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 pub(super) fn probe_existing_opaque_ty(
1133 &mut self,
1134 key: ty::OpaqueTypeKey<I>,
1135 ) -> Option<(ty::OpaqueTypeKey<I>, I::Ty)> {
1136 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 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
1182struct 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}