compiler/rustc_trait_selection/src/traits/select/mod.rs

   1 //! Candidate selection. See the [rustc dev guide] for more information on how this works.
   2 //!
   3 //! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/resolution.html#selection
   4
   5 use self::EvaluationResult::*;
   6 use self::SelectionCandidate::*;
   7
   8 use super::coherence::{self, Conflict};
   9 use super::const_evaluatable;
  10 use super::project;
  11 use super::project::normalize_with_depth_to;
  12 use super::project::ProjectionTyObligation;
  13 use super::util;
  14 use super::util::{closure_trait_ref_and_return_type, predicate_for_trait_def};
  15 use super::wf;
  16 use super::{
  17     ErrorReporting, ImplDerivedObligation, ImplDerivedObligationCause, Normalized, Obligation,
  18     ObligationCause, ObligationCauseCode, Overflow, PredicateObligation, Selection, SelectionError,
  19     SelectionResult, TraitObligation, TraitQueryMode,
  20 };
  21
  22 use crate::infer::{InferCtxt, InferOk, TypeFreshener};
  23 use crate::traits::error_reporting::TypeErrCtxtExt;
  24 use crate::traits::project::ProjectAndUnifyResult;
  25 use crate::traits::project::ProjectionCacheKeyExt;
  26 use crate::traits::ProjectionCacheKey;
  27 use rustc_data_structures::fx::{FxHashMap, FxHashSet, FxIndexSet};
  28 use rustc_data_structures::stack::ensure_sufficient_stack;
  29 use rustc_errors::{Diagnostic, ErrorGuaranteed};
  30 use rustc_hir as hir;
  31 use rustc_hir::def_id::DefId;
  32 use rustc_infer::infer::LateBoundRegionConversionTime;
  33 use rustc_middle::dep_graph::{DepKind, DepNodeIndex};
  34 use rustc_middle::mir::interpret::ErrorHandled;
  35 use rustc_middle::ty::abstract_const::NotConstEvaluatable;
  36 use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams};
  37 use rustc_middle::ty::fold::BottomUpFolder;
  38 use rustc_middle::ty::relate::TypeRelation;
  39 use rustc_middle::ty::SubstsRef;
  40 use rustc_middle::ty::{self, EarlyBinder, PolyProjectionPredicate, ToPolyTraitRef, ToPredicate};
  41 use rustc_middle::ty::{Ty, TyCtxt, TypeFoldable, TypeVisitable};
  42 use rustc_span::symbol::sym;
  43
  44 use std::cell::{Cell, RefCell};
  45 use std::cmp;
  46 use std::fmt::{self, Display};
  47 use std::iter;
  48
  49 pub use rustc_middle::traits::select::*;
  50
  51 mod candidate_assembly;
  52 mod confirmation;
  53
  54 #[derive(Clone, Debug, Eq, PartialEq, Hash)]
  55 pub enum IntercrateAmbiguityCause {
  56     DownstreamCrate { trait_desc: String, self_desc: Option<String> },
  57     UpstreamCrateUpdate { trait_desc: String, self_desc: Option<String> },
  58     ReservationImpl { message: String },
  59 }
  60
  61 impl IntercrateAmbiguityCause {
  62     /// Emits notes when the overlap is caused by complex intercrate ambiguities.
  63     /// See #23980 for details.
  64     pub fn add_intercrate_ambiguity_hint(&self, err: &mut Diagnostic) {
  65         err.note(&self.intercrate_ambiguity_hint());
  66     }
  67
  68     pub fn intercrate_ambiguity_hint(&self) -> String {
  69         match self {
  70             IntercrateAmbiguityCause::DownstreamCrate { trait_desc, self_desc } => {
  71                 let self_desc = if let Some(ty) = self_desc {
  72                     format!(" for type `{}`", ty)
  73                 } else {
  74                     String::new()
  75                 };
  76                 format!("downstream crates may implement trait `{}`{}", trait_desc, self_desc)
  77             }
  78             IntercrateAmbiguityCause::UpstreamCrateUpdate { trait_desc, self_desc } => {
  79                 let self_desc = if let Some(ty) = self_desc {
  80                     format!(" for type `{}`", ty)
  81                 } else {
  82                     String::new()
  83                 };
  84                 format!(
  85                     "upstream crates may add a new impl of trait `{}`{} \
  86                      in future versions",
  87                     trait_desc, self_desc
  88                 )
  89             }
  90             IntercrateAmbiguityCause::ReservationImpl { message } => message.clone(),
  91         }
  92     }
  93 }
  94
  95 pub struct SelectionContext<'cx, 'tcx> {
  96     infcx: &'cx InferCtxt<'tcx>,
  97
  98     /// Freshener used specifically for entries on the obligation
  99     /// stack. This ensures that all entries on the stack at one time
 100     /// will have the same set of placeholder entries, which is
 101     /// important for checking for trait bounds that recursively
 102     /// require themselves.
 103     freshener: TypeFreshener<'cx, 'tcx>,
 104
 105     /// During coherence we have to assume that other crates may add
 106     /// additional impls which we currently don't know about.
 107     ///
 108     /// To deal with this evaluation should be conservative
 109     /// and consider the possibility of impls from outside this crate.
 110     /// This comes up primarily when resolving ambiguity. Imagine
 111     /// there is some trait reference `$0: Bar` where `$0` is an
 112     /// inference variable. If `intercrate` is true, then we can never
 113     /// say for sure that this reference is not implemented, even if
 114     /// there are *no impls at all for `Bar`*, because `$0` could be
 115     /// bound to some type that in a downstream crate that implements
 116     /// `Bar`.
 117     ///
 118     /// Outside of coherence we set this to false because we are only
 119     /// interested in types that the user could actually have written.
 120     /// In other words, we consider `$0: Bar` to be unimplemented if
 121     /// there is no type that the user could *actually name* that
 122     /// would satisfy it. This avoids crippling inference, basically.
 123     intercrate: bool,
 124     /// If `intercrate` is set, we remember predicates which were
 125     /// considered ambiguous because of impls potentially added in other crates.
 126     /// This is used in coherence to give improved diagnostics.
 127     /// We don't do his until we detect a coherence error because it can
 128     /// lead to false overflow results (#47139) and because always
 129     /// computing it may negatively impact performance.
 130     intercrate_ambiguity_causes: Option<FxIndexSet<IntercrateAmbiguityCause>>,
 131
 132     /// The mode that trait queries run in, which informs our error handling
 133     /// policy. In essence, canonicalized queries need their errors propagated
 134     /// rather than immediately reported because we do not have accurate spans.
 135     query_mode: TraitQueryMode,
 136 }
 137
 138 // A stack that walks back up the stack frame.
 139 struct TraitObligationStack<'prev, 'tcx> {
 140     obligation: &'prev TraitObligation<'tcx>,
 141
 142     /// The trait predicate from `obligation` but "freshened" with the
 143     /// selection-context's freshener. Used to check for recursion.
 144     fresh_trait_pred: ty::PolyTraitPredicate<'tcx>,
 145
 146     /// Starts out equal to `depth` -- if, during evaluation, we
 147     /// encounter a cycle, then we will set this flag to the minimum
 148     /// depth of that cycle for all participants in the cycle. These
 149     /// participants will then forego caching their results. This is
 150     /// not the most efficient solution, but it addresses #60010. The
 151     /// problem we are trying to prevent:
 152     ///
 153     /// - If you have `A: AutoTrait` requires `B: AutoTrait` and `C: NonAutoTrait`
 154     /// - `B: AutoTrait` requires `A: AutoTrait` (coinductive cycle, ok)
 155     /// - `C: NonAutoTrait` requires `A: AutoTrait` (non-coinductive cycle, not ok)
 156     ///
 157     /// you don't want to cache that `B: AutoTrait` or `A: AutoTrait`
 158     /// is `EvaluatedToOk`; this is because they were only considered
 159     /// ok on the premise that if `A: AutoTrait` held, but we indeed
 160     /// encountered a problem (later on) with `A: AutoTrait. So we
 161     /// currently set a flag on the stack node for `B: AutoTrait` (as
 162     /// well as the second instance of `A: AutoTrait`) to suppress
 163     /// caching.
 164     ///
 165     /// This is a simple, targeted fix. A more-performant fix requires
 166     /// deeper changes, but would permit more caching: we could
 167     /// basically defer caching until we have fully evaluated the
 168     /// tree, and then cache the entire tree at once. In any case, the
 169     /// performance impact here shouldn't be so horrible: every time
 170     /// this is hit, we do cache at least one trait, so we only
 171     /// evaluate each member of a cycle up to N times, where N is the
 172     /// length of the cycle. This means the performance impact is
 173     /// bounded and we shouldn't have any terrible worst-cases.
 174     reached_depth: Cell<usize>,
 175
 176     previous: TraitObligationStackList<'prev, 'tcx>,
 177
 178     /// The number of parent frames plus one (thus, the topmost frame has depth 1).
 179     depth: usize,
 180
 181     /// The depth-first number of this node in the search graph -- a
 182     /// pre-order index. Basically, a freshly incremented counter.
 183     dfn: usize,
 184 }
 185
 186 struct SelectionCandidateSet<'tcx> {
 187     // A list of candidates that definitely apply to the current
 188     // obligation (meaning: types unify).
 189     vec: Vec<SelectionCandidate<'tcx>>,
 190
 191     // If `true`, then there were candidates that might or might
 192     // not have applied, but we couldn't tell. This occurs when some
 193     // of the input types are type variables, in which case there are
 194     // various "builtin" rules that might or might not trigger.
 195     ambiguous: bool,
 196 }
 197
 198 #[derive(PartialEq, Eq, Debug, Clone)]
 199 struct EvaluatedCandidate<'tcx> {
 200     candidate: SelectionCandidate<'tcx>,
 201     evaluation: EvaluationResult,
 202 }
 203
 204 /// When does the builtin impl for `T: Trait` apply?
 205 #[derive(Debug)]
 206 enum BuiltinImplConditions<'tcx> {
 207     /// The impl is conditional on `T1, T2, ...: Trait`.
 208     Where(ty::Binder<'tcx, Vec<Ty<'tcx>>>),
 209     /// There is no built-in impl. There may be some other
 210     /// candidate (a where-clause or user-defined impl).
 211     None,
 212     /// It is unknown whether there is an impl.
 213     Ambiguous,
 214 }
 215
 216 impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 217     pub fn new(infcx: &'cx InferCtxt<'tcx>) -> SelectionContext<'cx, 'tcx> {
 218         SelectionContext {
 219             infcx,
 220             freshener: infcx.freshener_keep_static(),
 221             intercrate: false,
 222             intercrate_ambiguity_causes: None,
 223             query_mode: TraitQueryMode::Standard,
 224         }
 225     }
 226
 227     pub fn intercrate(infcx: &'cx InferCtxt<'tcx>) -> SelectionContext<'cx, 'tcx> {
 228         SelectionContext { intercrate: true, ..SelectionContext::new(infcx) }
 229     }
 230
 231     pub fn with_query_mode(
 232         infcx: &'cx InferCtxt<'tcx>,
 233         query_mode: TraitQueryMode,
 234     ) -> SelectionContext<'cx, 'tcx> {
 235         debug!(?query_mode, "with_query_mode");
 236         SelectionContext { query_mode, ..SelectionContext::new(infcx) }
 237     }
 238
 239     /// Enables tracking of intercrate ambiguity causes. See
 240     /// the documentation of [`Self::intercrate_ambiguity_causes`] for more.
 241     pub fn enable_tracking_intercrate_ambiguity_causes(&mut self) {
 242         assert!(self.intercrate);
 243         assert!(self.intercrate_ambiguity_causes.is_none());
 244         self.intercrate_ambiguity_causes = Some(FxIndexSet::default());
 245         debug!("selcx: enable_tracking_intercrate_ambiguity_causes");
 246     }
 247
 248     /// Gets the intercrate ambiguity causes collected since tracking
 249     /// was enabled and disables tracking at the same time. If
 250     /// tracking is not enabled, just returns an empty vector.
 251     pub fn take_intercrate_ambiguity_causes(&mut self) -> FxIndexSet<IntercrateAmbiguityCause> {
 252         assert!(self.intercrate);
 253         self.intercrate_ambiguity_causes.take().unwrap_or_default()
 254     }
 255
 256     pub fn infcx(&self) -> &'cx InferCtxt<'tcx> {
 257         self.infcx
 258     }
 259
 260     pub fn tcx(&self) -> TyCtxt<'tcx> {
 261         self.infcx.tcx
 262     }
 263
 264     pub fn is_intercrate(&self) -> bool {
 265         self.intercrate
 266     }
 267
 268     ///////////////////////////////////////////////////////////////////////////
 269     // Selection
 270     //
 271     // The selection phase tries to identify *how* an obligation will
 272     // be resolved. For example, it will identify which impl or
 273     // parameter bound is to be used. The process can be inconclusive
 274     // if the self type in the obligation is not fully inferred. Selection
 275     // can result in an error in one of two ways:
 276     //
 277     // 1. If no applicable impl or parameter bound can be found.
 278     // 2. If the output type parameters in the obligation do not match
 279     //    those specified by the impl/bound. For example, if the obligation
 280     //    is `Vec<Foo>: Iterable<Bar>`, but the impl specifies
 281     //    `impl<T> Iterable<T> for Vec<T>`, than an error would result.
 282
 283     /// Attempts to satisfy the obligation. If successful, this will affect the surrounding
 284     /// type environment by performing unification.
 285     #[instrument(level = "debug", skip(self), ret)]
 286     pub fn select(
 287         &mut self,
 288         obligation: &TraitObligation<'tcx>,
 289     ) -> SelectionResult<'tcx, Selection<'tcx>> {
 290         let candidate = match self.select_from_obligation(obligation) {
 291             Err(SelectionError::Overflow(OverflowError::Canonical)) => {
 292                 // In standard mode, overflow must have been caught and reported
 293                 // earlier.
 294                 assert!(self.query_mode == TraitQueryMode::Canonical);
 295                 return Err(SelectionError::Overflow(OverflowError::Canonical));
 296             }
 297             Err(SelectionError::Ambiguous(_)) => {
 298                 return Ok(None);
 299             }
 300             Err(e) => {
 301                 return Err(e);
 302             }
 303             Ok(None) => {
 304                 return Ok(None);
 305             }
 306             Ok(Some(candidate)) => candidate,
 307         };
 308
 309         match self.confirm_candidate(obligation, candidate) {
 310             Err(SelectionError::Overflow(OverflowError::Canonical)) => {
 311                 assert!(self.query_mode == TraitQueryMode::Canonical);
 312                 Err(SelectionError::Overflow(OverflowError::Canonical))
 313             }
 314             Err(e) => Err(e),
 315             Ok(candidate) => Ok(Some(candidate)),
 316         }
 317     }
 318
 319     pub(crate) fn select_from_obligation(
 320         &mut self,
 321         obligation: &TraitObligation<'tcx>,
 322     ) -> SelectionResult<'tcx, SelectionCandidate<'tcx>> {
 323         debug_assert!(!obligation.predicate.has_escaping_bound_vars());
 324
 325         let pec = &ProvisionalEvaluationCache::default();
 326         let stack = self.push_stack(TraitObligationStackList::empty(pec), obligation);
 327
 328         self.candidate_from_obligation(&stack)
 329     }
 330
 331     ///////////////////////////////////////////////////////////////////////////
 332     // EVALUATION
 333     //
 334     // Tests whether an obligation can be selected or whether an impl
 335     // can be applied to particular types. It skips the "confirmation"
 336     // step and hence completely ignores output type parameters.
 337     //
 338     // The result is "true" if the obligation *may* hold and "false" if
 339     // we can be sure it does not.
 340
 341     /// Evaluates whether the obligation `obligation` can be satisfied (by any means).
 342     pub fn predicate_may_hold_fatal(&mut self, obligation: &PredicateObligation<'tcx>) -> bool {
 343         debug!(?obligation, "predicate_may_hold_fatal");
 344
 345         // This fatal query is a stopgap that should only be used in standard mode,
 346         // where we do not expect overflow to be propagated.
 347         assert!(self.query_mode == TraitQueryMode::Standard);
 348
 349         self.evaluate_root_obligation(obligation)
 350             .expect("Overflow should be caught earlier in standard query mode")
 351             .may_apply()
 352     }
 353
 354     /// Evaluates whether the obligation `obligation` can be satisfied
 355     /// and returns an `EvaluationResult`. This is meant for the
 356     /// *initial* call.
 357     pub fn evaluate_root_obligation(
 358         &mut self,
 359         obligation: &PredicateObligation<'tcx>,
 360     ) -> Result<EvaluationResult, OverflowError> {
 361         self.evaluation_probe(|this| {
 362             this.evaluate_predicate_recursively(
 363                 TraitObligationStackList::empty(&ProvisionalEvaluationCache::default()),
 364                 obligation.clone(),
 365             )
 366         })
 367     }
 368
 369     fn evaluation_probe(
 370         &mut self,
 371         op: impl FnOnce(&mut Self) -> Result<EvaluationResult, OverflowError>,
 372     ) -> Result<EvaluationResult, OverflowError> {
 373         self.infcx.probe(|snapshot| -> Result<EvaluationResult, OverflowError> {
 374             let result = op(self)?;
 375
 376             match self.infcx.leak_check(true, snapshot) {
 377                 Ok(()) => {}
 378                 Err(_) => return Ok(EvaluatedToErr),
 379             }
 380
 381             if self.infcx.opaque_types_added_in_snapshot(snapshot) {
 382                 return Ok(result.max(EvaluatedToOkModuloOpaqueTypes));
 383             }
 384
 385             match self.infcx.region_constraints_added_in_snapshot(snapshot) {
 386                 None => Ok(result),
 387                 Some(_) => Ok(result.max(EvaluatedToOkModuloRegions)),
 388             }
 389         })
 390     }
 391
 392     /// Evaluates the predicates in `predicates` recursively. Note that
 393     /// this applies projections in the predicates, and therefore
 394     /// is run within an inference probe.
 395     #[instrument(skip(self, stack), level = "debug")]
 396     fn evaluate_predicates_recursively<'o, I>(
 397         &mut self,
 398         stack: TraitObligationStackList<'o, 'tcx>,
 399         predicates: I,
 400     ) -> Result<EvaluationResult, OverflowError>
 401     where
 402         I: IntoIterator<Item = PredicateObligation<'tcx>> + std::fmt::Debug,
 403     {
 404         let mut result = EvaluatedToOk;
 405         for obligation in predicates {
 406             let eval = self.evaluate_predicate_recursively(stack, obligation.clone())?;
 407             if let EvaluatedToErr = eval {
 408                 // fast-path - EvaluatedToErr is the top of the lattice,
 409                 // so we don't need to look on the other predicates.
 410                 return Ok(EvaluatedToErr);
 411             } else {
 412                 result = cmp::max(result, eval);
 413             }
 414         }
 415         Ok(result)
 416     }
 417
 418     #[instrument(
 419         level = "debug",
 420         skip(self, previous_stack),
 421         fields(previous_stack = ?previous_stack.head())
 422         ret,
 423     )]
 424     fn evaluate_predicate_recursively<'o>(
 425         &mut self,
 426         previous_stack: TraitObligationStackList<'o, 'tcx>,
 427         obligation: PredicateObligation<'tcx>,
 428     ) -> Result<EvaluationResult, OverflowError> {
 429         // `previous_stack` stores a `TraitObligation`, while `obligation` is
 430         // a `PredicateObligation`. These are distinct types, so we can't
 431         // use any `Option` combinator method that would force them to be
 432         // the same.
 433         match previous_stack.head() {
 434             Some(h) => self.check_recursion_limit(&obligation, h.obligation)?,
 435             None => self.check_recursion_limit(&obligation, &obligation)?,
 436         }
 437
 438         ensure_sufficient_stack(|| {
 439             let bound_predicate = obligation.predicate.kind();
 440             match bound_predicate.skip_binder() {
 441                 ty::PredicateKind::Trait(t) => {
 442                     let t = bound_predicate.rebind(t);
 443                     debug_assert!(!t.has_escaping_bound_vars());
 444                     let obligation = obligation.with(t);
 445                     self.evaluate_trait_predicate_recursively(previous_stack, obligation)
 446                 }
 447
 448                 ty::PredicateKind::Subtype(p) => {
 449                     let p = bound_predicate.rebind(p);
 450                     // Does this code ever run?
 451                     match self.infcx.subtype_predicate(&obligation.cause, obligation.param_env, p) {
 452                         Ok(Ok(InferOk { mut obligations, .. })) => {
 453                             self.add_depth(obligations.iter_mut(), obligation.recursion_depth);
 454                             self.evaluate_predicates_recursively(
 455                                 previous_stack,
 456                                 obligations.into_iter(),
 457                             )
 458                         }
 459                         Ok(Err(_)) => Ok(EvaluatedToErr),
 460                         Err(..) => Ok(EvaluatedToAmbig),
 461                     }
 462                 }
 463
 464                 ty::PredicateKind::Coerce(p) => {
 465                     let p = bound_predicate.rebind(p);
 466                     // Does this code ever run?
 467                     match self.infcx.coerce_predicate(&obligation.cause, obligation.param_env, p) {
 468                         Ok(Ok(InferOk { mut obligations, .. })) => {
 469                             self.add_depth(obligations.iter_mut(), obligation.recursion_depth);
 470                             self.evaluate_predicates_recursively(
 471                                 previous_stack,
 472                                 obligations.into_iter(),
 473                             )
 474                         }
 475                         Ok(Err(_)) => Ok(EvaluatedToErr),
 476                         Err(..) => Ok(EvaluatedToAmbig),
 477                     }
 478                 }
 479
 480                 ty::PredicateKind::WellFormed(arg) => {
 481                     // So, there is a bit going on here. First, `WellFormed` predicates
 482                     // are coinductive, like trait predicates with auto traits.
 483                     // This means that we need to detect if we have recursively
 484                     // evaluated `WellFormed(X)`. Otherwise, we would run into
 485                     // a "natural" overflow error.
 486                     //
 487                     // Now, the next question is whether we need to do anything
 488                     // special with caching. Considering the following tree:
 489                     // - `WF(Foo<T>)`
 490                     //   - `Bar<T>: Send`
 491                     //     - `WF(Foo<T>)`
 492                     //   - `Foo<T>: Trait`
 493                     // In this case, the innermost `WF(Foo<T>)` should return
 494                     // `EvaluatedToOk`, since it's coinductive. Then if
 495                     // `Bar<T>: Send` is resolved to `EvaluatedToOk`, it can be
 496                     // inserted into a cache (because without thinking about `WF`
 497                     // goals, it isn't in a cycle). If `Foo<T>: Trait` later doesn't
 498                     // hold, then `Bar<T>: Send` shouldn't hold. Therefore, we
 499                     // *do* need to keep track of coinductive cycles.
 500
 501                     let cache = previous_stack.cache;
 502                     let dfn = cache.next_dfn();
 503
 504                     for stack_arg in previous_stack.cache.wf_args.borrow().iter().rev() {
 505                         if stack_arg.0 != arg {
 506                             continue;
 507                         }
 508                         debug!("WellFormed({:?}) on stack", arg);
 509                         if let Some(stack) = previous_stack.head {
 510                             // Okay, let's imagine we have two different stacks:
 511                             //   `T: NonAutoTrait -> WF(T) -> T: NonAutoTrait`
 512                             //   `WF(T) -> T: NonAutoTrait -> WF(T)`
 513                             // Because of this, we need to check that all
 514                             // predicates between the WF goals are coinductive.
 515                             // Otherwise, we can say that `T: NonAutoTrait` is
 516                             // true.
 517                             // Let's imagine we have a predicate stack like
 518                             //         `Foo: Bar -> WF(T) -> T: NonAutoTrait -> T: Auto
 519                             // depth   ^1                    ^2                 ^3
 520                             // and the current predicate is `WF(T)`. `wf_args`
 521                             // would contain `(T, 1)`. We want to check all
 522                             // trait predicates greater than `1`. The previous
 523                             // stack would be `T: Auto`.
 524                             let cycle = stack.iter().take_while(|s| s.depth > stack_arg.1);
 525                             let tcx = self.tcx();
 526                             let cycle =
 527                                 cycle.map(|stack| stack.obligation.predicate.to_predicate(tcx));
 528                             if self.coinductive_match(cycle) {
 529                                 stack.update_reached_depth(stack_arg.1);
 530                                 return Ok(EvaluatedToOk);
 531                             } else {
 532                                 return Ok(EvaluatedToRecur);
 533                             }
 534                         }
 535                         return Ok(EvaluatedToOk);
 536                     }
 537
 538                     match wf::obligations(
 539                         self.infcx,
 540                         obligation.param_env,
 541                         obligation.cause.body_id,
 542                         obligation.recursion_depth + 1,
 543                         arg,
 544                         obligation.cause.span,
 545                     ) {
 546                         Some(mut obligations) => {
 547                             self.add_depth(obligations.iter_mut(), obligation.recursion_depth);
 548
 549                             cache.wf_args.borrow_mut().push((arg, previous_stack.depth()));
 550                             let result =
 551                                 self.evaluate_predicates_recursively(previous_stack, obligations);
 552                             cache.wf_args.borrow_mut().pop();
 553
 554                             let result = result?;
 555
 556                             if !result.must_apply_modulo_regions() {
 557                                 cache.on_failure(dfn);
 558                             }
 559
 560                             cache.on_completion(dfn);
 561
 562                             Ok(result)
 563                         }
 564                         None => Ok(EvaluatedToAmbig),
 565                     }
 566                 }
 567
 568                 ty::PredicateKind::TypeOutlives(pred) => {
 569                     // A global type with no late-bound regions can only
 570                     // contain the "'static" lifetime (any other lifetime
 571                     // would either be late-bound or local), so it is guaranteed
 572                     // to outlive any other lifetime
 573                     if pred.0.is_global() && !pred.0.has_late_bound_regions() {
 574                         Ok(EvaluatedToOk)
 575                     } else {
 576                         Ok(EvaluatedToOkModuloRegions)
 577                     }
 578                 }
 579
 580                 ty::PredicateKind::RegionOutlives(..) => {
 581                     // We do not consider region relationships when evaluating trait matches.
 582                     Ok(EvaluatedToOkModuloRegions)
 583                 }
 584
 585                 ty::PredicateKind::ObjectSafe(trait_def_id) => {
 586                     if self.tcx().is_object_safe(trait_def_id) {
 587                         Ok(EvaluatedToOk)
 588                     } else {
 589                         Ok(EvaluatedToErr)
 590                     }
 591                 }
 592
 593                 ty::PredicateKind::Projection(data) => {
 594                     let data = bound_predicate.rebind(data);
 595                     let project_obligation = obligation.with(data);
 596                     match project::poly_project_and_unify_type(self, &project_obligation) {
 597                         ProjectAndUnifyResult::Holds(mut subobligations) => {
 598                             'compute_res: {
 599                                 // If we've previously marked this projection as 'complete', then
 600                                 // use the final cached result (either `EvaluatedToOk` or
 601                                 // `EvaluatedToOkModuloRegions`), and skip re-evaluating the
 602                                 // sub-obligations.
 603                                 if let Some(key) =
 604                                     ProjectionCacheKey::from_poly_projection_predicate(self, data)
 605                                 {
 606                                     if let Some(cached_res) = self
 607                                         .infcx
 608                                         .inner
 609                                         .borrow_mut()
 610                                         .projection_cache()
 611                                         .is_complete(key)
 612                                     {
 613                                         break 'compute_res Ok(cached_res);
 614                                     }
 615                                 }
 616
 617                                 self.add_depth(
 618                                     subobligations.iter_mut(),
 619                                     obligation.recursion_depth,
 620                                 );
 621                                 let res = self.evaluate_predicates_recursively(
 622                                     previous_stack,
 623                                     subobligations,
 624                                 );
 625                                 if let Ok(eval_rslt) = res
 626                                     && (eval_rslt == EvaluatedToOk || eval_rslt == EvaluatedToOkModuloRegions)
 627                                     && let Some(key) =
 628                                         ProjectionCacheKey::from_poly_projection_predicate(
 629                                             self, data,
 630                                         )
 631                                 {
 632                                     // If the result is something that we can cache, then mark this
 633                                     // entry as 'complete'. This will allow us to skip evaluating the
 634                                     // subobligations at all the next time we evaluate the projection
 635                                     // predicate.
 636                                     self.infcx
 637                                         .inner
 638                                         .borrow_mut()
 639                                         .projection_cache()
 640                                         .complete(key, eval_rslt);
 641                                 }
 642                                 res
 643                             }
 644                         }
 645                         ProjectAndUnifyResult::FailedNormalization => Ok(EvaluatedToAmbig),
 646                         ProjectAndUnifyResult::Recursive => Ok(EvaluatedToRecur),
 647                         ProjectAndUnifyResult::MismatchedProjectionTypes(_) => Ok(EvaluatedToErr),
 648                     }
 649                 }
 650
 651                 ty::PredicateKind::ClosureKind(_, closure_substs, kind) => {
 652                     match self.infcx.closure_kind(closure_substs) {
 653                         Some(closure_kind) => {
 654                             if closure_kind.extends(kind) {
 655                                 Ok(EvaluatedToOk)
 656                             } else {
 657                                 Ok(EvaluatedToErr)
 658                             }
 659                         }
 660                         None => Ok(EvaluatedToAmbig),
 661                     }
 662                 }
 663
 664                 ty::PredicateKind::ConstEvaluatable(uv) => {
 665                     match const_evaluatable::is_const_evaluatable(
 666                         self.infcx,
 667                         uv,
 668                         obligation.param_env,
 669                         obligation.cause.span,
 670                     ) {
 671                         Ok(()) => Ok(EvaluatedToOk),
 672                         Err(NotConstEvaluatable::MentionsInfer) => Ok(EvaluatedToAmbig),
 673                         Err(NotConstEvaluatable::MentionsParam) => Ok(EvaluatedToErr),
 674                         Err(_) => Ok(EvaluatedToErr),
 675                     }
 676                 }
 677
 678                 ty::PredicateKind::ConstEquate(c1, c2) => {
 679                     assert!(
 680                         self.tcx().features().generic_const_exprs,
 681                         "`ConstEquate` without a feature gate: {c1:?} {c2:?}",
 682                     );
 683                     debug!(?c1, ?c2, "evaluate_predicate_recursively: equating consts");
 684
 685                     // FIXME: we probably should only try to unify abstract constants
 686                     // if the constants depend on generic parameters.
 687                     //
 688                     // Let's just see where this breaks :shrug:
 689                     if let (ty::ConstKind::Unevaluated(a), ty::ConstKind::Unevaluated(b)) =
 690                         (c1.kind(), c2.kind())
 691                     {
 692                         if self.infcx.try_unify_abstract_consts(a, b, obligation.param_env) {
 693                             return Ok(EvaluatedToOk);
 694                         }
 695                     }
 696
 697                     let evaluate = |c: ty::Const<'tcx>| {
 698                         if let ty::ConstKind::Unevaluated(unevaluated) = c.kind() {
 699                             match self.infcx.try_const_eval_resolve(
 700                                 obligation.param_env,
 701                                 unevaluated,
 702                                 c.ty(),
 703                                 Some(obligation.cause.span),
 704                             ) {
 705                                 Ok(val) => Ok(val),
 706                                 Err(e) => Err(e),
 707                             }
 708                         } else {
 709                             Ok(c)
 710                         }
 711                     };
 712
 713                     match (evaluate(c1), evaluate(c2)) {
 714                         (Ok(c1), Ok(c2)) => {
 715                             match self
 716                                 .infcx()
 717                                 .at(&obligation.cause, obligation.param_env)
 718                                 .eq(c1, c2)
 719                             {
 720                                 Ok(_) => Ok(EvaluatedToOk),
 721                                 Err(_) => Ok(EvaluatedToErr),
 722                             }
 723                         }
 724                         (Err(ErrorHandled::Reported(_)), _)
 725                         | (_, Err(ErrorHandled::Reported(_))) => Ok(EvaluatedToErr),
 726                         (Err(ErrorHandled::Linted), _) | (_, Err(ErrorHandled::Linted)) => {
 727                             span_bug!(
 728                                 obligation.cause.span(),
 729                                 "ConstEquate: const_eval_resolve returned an unexpected error"
 730                             )
 731                         }
 732                         (Err(ErrorHandled::TooGeneric), _) | (_, Err(ErrorHandled::TooGeneric)) => {
 733                             if c1.has_non_region_infer() || c2.has_non_region_infer() {
 734                                 Ok(EvaluatedToAmbig)
 735                             } else {
 736                                 // Two different constants using generic parameters ~> error.
 737                                 Ok(EvaluatedToErr)
 738                             }
 739                         }
 740                     }
 741                 }
 742                 ty::PredicateKind::TypeWellFormedFromEnv(..) => {
 743                     bug!("TypeWellFormedFromEnv is only used for chalk")
 744                 }
 745             }
 746         })
 747     }
 748
 749     #[instrument(skip(self, previous_stack), level = "debug", ret)]
 750     fn evaluate_trait_predicate_recursively<'o>(
 751         &mut self,
 752         previous_stack: TraitObligationStackList<'o, 'tcx>,
 753         mut obligation: TraitObligation<'tcx>,
 754     ) -> Result<EvaluationResult, OverflowError> {
 755         if !self.intercrate
 756             && obligation.is_global()
 757             && obligation.param_env.caller_bounds().iter().all(|bound| bound.needs_subst())
 758         {
 759             // If a param env has no global bounds, global obligations do not
 760             // depend on its particular value in order to work, so we can clear
 761             // out the param env and get better caching.
 762             debug!("in global");
 763             obligation.param_env = obligation.param_env.without_caller_bounds();
 764         }
 765
 766         let stack = self.push_stack(previous_stack, &obligation);
 767         let mut fresh_trait_pred = stack.fresh_trait_pred;
 768         let mut param_env = obligation.param_env;
 769
 770         fresh_trait_pred = fresh_trait_pred.map_bound(|mut pred| {
 771             pred.remap_constness(&mut param_env);
 772             pred
 773         });
 774
 775         debug!(?fresh_trait_pred);
 776
 777         // If a trait predicate is in the (local or global) evaluation cache,
 778         // then we know it holds without cycles.
 779         if let Some(result) = self.check_evaluation_cache(param_env, fresh_trait_pred) {
 780             debug!("CACHE HIT");
 781             return Ok(result);
 782         }
 783
 784         if let Some(result) = stack.cache().get_provisional(fresh_trait_pred) {
 785             debug!("PROVISIONAL CACHE HIT");
 786             stack.update_reached_depth(result.reached_depth);
 787             return Ok(result.result);
 788         }
 789
 790         // Check if this is a match for something already on the
 791         // stack. If so, we don't want to insert the result into the
 792         // main cache (it is cycle dependent) nor the provisional
 793         // cache (which is meant for things that have completed but
 794         // for a "backedge" -- this result *is* the backedge).
 795         if let Some(cycle_result) = self.check_evaluation_cycle(&stack) {
 796             return Ok(cycle_result);
 797         }
 798
 799         let (result, dep_node) = self.in_task(|this| this.evaluate_stack(&stack));
 800         let result = result?;
 801
 802         if !result.must_apply_modulo_regions() {
 803             stack.cache().on_failure(stack.dfn);
 804         }
 805
 806         let reached_depth = stack.reached_depth.get();
 807         if reached_depth >= stack.depth {
 808             debug!("CACHE MISS");
 809             self.insert_evaluation_cache(param_env, fresh_trait_pred, dep_node, result);
 810             stack.cache().on_completion(stack.dfn);
 811         } else {
 812             debug!("PROVISIONAL");
 813             debug!(
 814                 "caching provisionally because {:?} \
 815                  is a cycle participant (at depth {}, reached depth {})",
 816                 fresh_trait_pred, stack.depth, reached_depth,
 817             );
 818
 819             stack.cache().insert_provisional(stack.dfn, reached_depth, fresh_trait_pred, result);
 820         }
 821
 822         Ok(result)
 823     }
 824
 825     /// If there is any previous entry on the stack that precisely
 826     /// matches this obligation, then we can assume that the
 827     /// obligation is satisfied for now (still all other conditions
 828     /// must be met of course). One obvious case this comes up is
 829     /// marker traits like `Send`. Think of a linked list:
 830     ///
 831     ///     struct List<T> { data: T, next: Option<Box<List<T>>> }
 832     ///
 833     /// `Box<List<T>>` will be `Send` if `T` is `Send` and
 834     /// `Option<Box<List<T>>>` is `Send`, and in turn
 835     /// `Option<Box<List<T>>>` is `Send` if `Box<List<T>>` is
 836     /// `Send`.
 837     ///
 838     /// Note that we do this comparison using the `fresh_trait_ref`
 839     /// fields. Because these have all been freshened using
 840     /// `self.freshener`, we can be sure that (a) this will not
 841     /// affect the inferencer state and (b) that if we see two
 842     /// fresh regions with the same index, they refer to the same
 843     /// unbound type variable.
 844     fn check_evaluation_cycle(
 845         &mut self,
 846         stack: &TraitObligationStack<'_, 'tcx>,
 847     ) -> Option<EvaluationResult> {
 848         if let Some(cycle_depth) = stack
 849             .iter()
 850             .skip(1) // Skip top-most frame.
 851             .find(|prev| {
 852                 stack.obligation.param_env == prev.obligation.param_env
 853                     && stack.fresh_trait_pred == prev.fresh_trait_pred
 854             })
 855             .map(|stack| stack.depth)
 856         {
 857             debug!("evaluate_stack --> recursive at depth {}", cycle_depth);
 858
 859             // If we have a stack like `A B C D E A`, where the top of
 860             // the stack is the final `A`, then this will iterate over
 861             // `A, E, D, C, B` -- i.e., all the participants apart
 862             // from the cycle head. We mark them as participating in a
 863             // cycle. This suppresses caching for those nodes. See
 864             // `in_cycle` field for more details.
 865             stack.update_reached_depth(cycle_depth);
 866
 867             // Subtle: when checking for a coinductive cycle, we do
 868             // not compare using the "freshened trait refs" (which
 869             // have erased regions) but rather the fully explicit
 870             // trait refs. This is important because it's only a cycle
 871             // if the regions match exactly.
 872             let cycle = stack.iter().skip(1).take_while(|s| s.depth >= cycle_depth);
 873             let tcx = self.tcx();
 874             let cycle = cycle.map(|stack| stack.obligation.predicate.to_predicate(tcx));
 875             if self.coinductive_match(cycle) {
 876                 debug!("evaluate_stack --> recursive, coinductive");
 877                 Some(EvaluatedToOk)
 878             } else {
 879                 debug!("evaluate_stack --> recursive, inductive");
 880                 Some(EvaluatedToRecur)
 881             }
 882         } else {
 883             None
 884         }
 885     }
 886
 887     fn evaluate_stack<'o>(
 888         &mut self,
 889         stack: &TraitObligationStack<'o, 'tcx>,
 890     ) -> Result<EvaluationResult, OverflowError> {
 891         // In intercrate mode, whenever any of the generics are unbound,
 892         // there can always be an impl. Even if there are no impls in
 893         // this crate, perhaps the type would be unified with
 894         // something from another crate that does provide an impl.
 895         //
 896         // In intra mode, we must still be conservative. The reason is
 897         // that we want to avoid cycles. Imagine an impl like:
 898         //
 899         //     impl<T:Eq> Eq for Vec<T>
 900         //
 901         // and a trait reference like `$0 : Eq` where `$0` is an
 902         // unbound variable. When we evaluate this trait-reference, we
 903         // will unify `$0` with `Vec<$1>` (for some fresh variable
 904         // `$1`), on the condition that `$1 : Eq`. We will then wind
 905         // up with many candidates (since that are other `Eq` impls
 906         // that apply) and try to winnow things down. This results in
 907         // a recursive evaluation that `$1 : Eq` -- as you can
 908         // imagine, this is just where we started. To avoid that, we
 909         // check for unbound variables and return an ambiguous (hence possible)
 910         // match if we've seen this trait before.
 911         //
 912         // This suffices to allow chains like `FnMut` implemented in
 913         // terms of `Fn` etc, but we could probably make this more
 914         // precise still.
 915         let unbound_input_types =
 916             stack.fresh_trait_pred.skip_binder().trait_ref.substs.types().any(|ty| ty.is_fresh());
 917
 918         if unbound_input_types
 919             && stack.iter().skip(1).any(|prev| {
 920                 stack.obligation.param_env == prev.obligation.param_env
 921                     && self.match_fresh_trait_refs(
 922                         stack.fresh_trait_pred,
 923                         prev.fresh_trait_pred,
 924                         prev.obligation.param_env,
 925                     )
 926             })
 927         {
 928             debug!("evaluate_stack --> unbound argument, recursive --> giving up",);
 929             return Ok(EvaluatedToUnknown);
 930         }
 931
 932         match self.candidate_from_obligation(stack) {
 933             Ok(Some(c)) => self.evaluate_candidate(stack, &c),
 934             Err(SelectionError::Ambiguous(_)) => Ok(EvaluatedToAmbig),
 935             Ok(None) => Ok(EvaluatedToAmbig),
 936             Err(Overflow(OverflowError::Canonical)) => Err(OverflowError::Canonical),
 937             Err(ErrorReporting) => Err(OverflowError::ErrorReporting),
 938             Err(..) => Ok(EvaluatedToErr),
 939         }
 940     }
 941
 942     /// For defaulted traits, we use a co-inductive strategy to solve, so
 943     /// that recursion is ok. This routine returns `true` if the top of the
 944     /// stack (`cycle[0]`):
 945     ///
 946     /// - is a defaulted trait,
 947     /// - it also appears in the backtrace at some position `X`,
 948     /// - all the predicates at positions `X..` between `X` and the top are
 949     ///   also defaulted traits.
 950     pub(crate) fn coinductive_match<I>(&mut self, mut cycle: I) -> bool
 951     where
 952         I: Iterator<Item = ty::Predicate<'tcx>>,
 953     {
 954         cycle.all(|predicate| self.coinductive_predicate(predicate))
 955     }
 956
 957     fn coinductive_predicate(&self, predicate: ty::Predicate<'tcx>) -> bool {
 958         let result = match predicate.kind().skip_binder() {
 959             ty::PredicateKind::Trait(ref data) => self.tcx().trait_is_auto(data.def_id()),
 960             ty::PredicateKind::WellFormed(_) => true,
 961             _ => false,
 962         };
 963         debug!(?predicate, ?result, "coinductive_predicate");
 964         result
 965     }
 966
 967     /// Further evaluates `candidate` to decide whether all type parameters match and whether nested
 968     /// obligations are met. Returns whether `candidate` remains viable after this further
 969     /// scrutiny.
 970     #[instrument(
 971         level = "debug",
 972         skip(self, stack),
 973         fields(depth = stack.obligation.recursion_depth),
 974         ret
 975     )]
 976     fn evaluate_candidate<'o>(
 977         &mut self,
 978         stack: &TraitObligationStack<'o, 'tcx>,
 979         candidate: &SelectionCandidate<'tcx>,
 980     ) -> Result<EvaluationResult, OverflowError> {
 981         let mut result = self.evaluation_probe(|this| {
 982             let candidate = (*candidate).clone();
 983             match this.confirm_candidate(stack.obligation, candidate) {
 984                 Ok(selection) => {
 985                     debug!(?selection);
 986                     this.evaluate_predicates_recursively(
 987                         stack.list(),
 988                         selection.nested_obligations().into_iter(),
 989                     )
 990                 }
 991                 Err(..) => Ok(EvaluatedToErr),
 992             }
 993         })?;
 994
 995         // If we erased any lifetimes, then we want to use
 996         // `EvaluatedToOkModuloRegions` instead of `EvaluatedToOk`
 997         // as your final result. The result will be cached using
 998         // the freshened trait predicate as a key, so we need
 999         // our result to be correct by *any* choice of original lifetimes,
1000         // not just the lifetime choice for this particular (non-erased)
1001         // predicate.
1002         // See issue #80691
1003         if stack.fresh_trait_pred.has_erased_regions() {
1004             result = result.max(EvaluatedToOkModuloRegions);
1005         }
1006
1007         Ok(result)
1008     }
1009
1010     fn check_evaluation_cache(
1011         &self,
1012         param_env: ty::ParamEnv<'tcx>,
1013         trait_pred: ty::PolyTraitPredicate<'tcx>,
1014     ) -> Option<EvaluationResult> {
1015         // Neither the global nor local cache is aware of intercrate
1016         // mode, so don't do any caching. In particular, we might
1017         // re-use the same `InferCtxt` with both an intercrate
1018         // and non-intercrate `SelectionContext`
1019         if self.intercrate {
1020             return None;
1021         }
1022
1023         let tcx = self.tcx();
1024         if self.can_use_global_caches(param_env) {
1025             if let Some(res) = tcx.evaluation_cache.get(&(param_env, trait_pred), tcx) {
1026                 return Some(res);
1027             }
1028         }
1029         self.infcx.evaluation_cache.get(&(param_env, trait_pred), tcx)
1030     }
1031
1032     fn insert_evaluation_cache(
1033         &mut self,
1034         param_env: ty::ParamEnv<'tcx>,
1035         trait_pred: ty::PolyTraitPredicate<'tcx>,
1036         dep_node: DepNodeIndex,
1037         result: EvaluationResult,
1038     ) {
1039         // Avoid caching results that depend on more than just the trait-ref
1040         // - the stack can create recursion.
1041         if result.is_stack_dependent() {
1042             return;
1043         }
1044
1045         // Neither the global nor local cache is aware of intercrate
1046         // mode, so don't do any caching. In particular, we might
1047         // re-use the same `InferCtxt` with both an intercrate
1048         // and non-intercrate `SelectionContext`
1049         if self.intercrate {
1050             return;
1051         }
1052
1053         if self.can_use_global_caches(param_env) {
1054             if !trait_pred.needs_infer() {
1055                 debug!(?trait_pred, ?result, "insert_evaluation_cache global");
1056                 // This may overwrite the cache with the same value
1057                 // FIXME: Due to #50507 this overwrites the different values
1058                 // This should be changed to use HashMapExt::insert_same
1059                 // when that is fixed
1060                 self.tcx().evaluation_cache.insert((param_env, trait_pred), dep_node, result);
1061                 return;
1062             }
1063         }
1064
1065         debug!(?trait_pred, ?result, "insert_evaluation_cache");
1066         self.infcx.evaluation_cache.insert((param_env, trait_pred), dep_node, result);
1067     }
1068
1069     /// For various reasons, it's possible for a subobligation
1070     /// to have a *lower* recursion_depth than the obligation used to create it.
1071     /// Projection sub-obligations may be returned from the projection cache,
1072     /// which results in obligations with an 'old' `recursion_depth`.
1073     /// Additionally, methods like `InferCtxt.subtype_predicate` produce
1074     /// subobligations without taking in a 'parent' depth, causing the
1075     /// generated subobligations to have a `recursion_depth` of `0`.
1076     ///
1077     /// To ensure that obligation_depth never decreases, we force all subobligations
1078     /// to have at least the depth of the original obligation.
1079     fn add_depth<T: 'cx, I: Iterator<Item = &'cx mut Obligation<'tcx, T>>>(
1080         &self,
1081         it: I,
1082         min_depth: usize,
1083     ) {
1084         it.for_each(|o| o.recursion_depth = cmp::max(min_depth, o.recursion_depth) + 1);
1085     }
1086
1087     fn check_recursion_depth<T: Display + TypeFoldable<'tcx>>(
1088         &self,
1089         depth: usize,
1090         error_obligation: &Obligation<'tcx, T>,
1091     ) -> Result<(), OverflowError> {
1092         if !self.infcx.tcx.recursion_limit().value_within_limit(depth) {
1093             match self.query_mode {
1094                 TraitQueryMode::Standard => {
1095                     if self.infcx.is_tainted_by_errors() {
1096                         return Err(OverflowError::Error(
1097                             ErrorGuaranteed::unchecked_claim_error_was_emitted(),
1098                         ));
1099                     }
1100                     self.infcx.err_ctxt().report_overflow_error(error_obligation, true);
1101                 }
1102                 TraitQueryMode::Canonical => {
1103                     return Err(OverflowError::Canonical);
1104                 }
1105             }
1106         }
1107         Ok(())
1108     }
1109
1110     /// Checks that the recursion limit has not been exceeded.
1111     ///
1112     /// The weird return type of this function allows it to be used with the `try` (`?`)
1113     /// operator within certain functions.
1114     #[inline(always)]
1115     fn check_recursion_limit<T: Display + TypeFoldable<'tcx>, V: Display + TypeFoldable<'tcx>>(
1116         &self,
1117         obligation: &Obligation<'tcx, T>,
1118         error_obligation: &Obligation<'tcx, V>,
1119     ) -> Result<(), OverflowError> {
1120         self.check_recursion_depth(obligation.recursion_depth, error_obligation)
1121     }
1122
1123     fn in_task<OP, R>(&mut self, op: OP) -> (R, DepNodeIndex)
1124     where
1125         OP: FnOnce(&mut Self) -> R,
1126     {
1127         let (result, dep_node) =
1128             self.tcx().dep_graph.with_anon_task(self.tcx(), DepKind::TraitSelect, || op(self));
1129         self.tcx().dep_graph.read_index(dep_node);
1130         (result, dep_node)
1131     }
1132
1133     /// filter_impls filters constant trait obligations and candidates that have a positive impl
1134     /// for a negative goal and a negative impl for a positive goal
1135     #[instrument(level = "debug", skip(self, candidates))]
1136     fn filter_impls(
1137         &mut self,
1138         candidates: Vec<SelectionCandidate<'tcx>>,
1139         obligation: &TraitObligation<'tcx>,
1140     ) -> Vec<SelectionCandidate<'tcx>> {
1141         trace!("{candidates:#?}");
1142         let tcx = self.tcx();
1143         let mut result = Vec::with_capacity(candidates.len());
1144
1145         for candidate in candidates {
1146             // Respect const trait obligations
1147             if obligation.is_const() {
1148                 match candidate {
1149                     // const impl
1150                     ImplCandidate(def_id) if tcx.constness(def_id) == hir::Constness::Const => {}
1151                     // const param
1152                     ParamCandidate(trait_pred) if trait_pred.is_const_if_const() => {}
1153                     // const projection
1154                     ProjectionCandidate(_, ty::BoundConstness::ConstIfConst) => {}
1155                     // auto trait impl
1156                     AutoImplCandidate => {}
1157                     // generator, this will raise error in other places
1158                     // or ignore error with const_async_blocks feature
1159                     GeneratorCandidate => {}
1160                     // FnDef where the function is const
1161                     FnPointerCandidate { is_const: true } => {}
1162                     ConstDestructCandidate(_) => {}
1163                     _ => {
1164                         // reject all other types of candidates
1165                         continue;
1166                     }
1167                 }
1168             }
1169
1170             if let ImplCandidate(def_id) = candidate {
1171                 if ty::ImplPolarity::Reservation == tcx.impl_polarity(def_id)
1172                     || obligation.polarity() == tcx.impl_polarity(def_id)
1173                 {
1174                     result.push(candidate);
1175                 }
1176             } else {
1177                 result.push(candidate);
1178             }
1179         }
1180
1181         trace!("{result:#?}");
1182         result
1183     }
1184
1185     /// filter_reservation_impls filter reservation impl for any goal as ambiguous
1186     #[instrument(level = "debug", skip(self))]
1187     fn filter_reservation_impls(
1188         &mut self,
1189         candidate: SelectionCandidate<'tcx>,
1190         obligation: &TraitObligation<'tcx>,
1191     ) -> SelectionResult<'tcx, SelectionCandidate<'tcx>> {
1192         let tcx = self.tcx();
1193         // Treat reservation impls as ambiguity.
1194         if let ImplCandidate(def_id) = candidate {
1195             if let ty::ImplPolarity::Reservation = tcx.impl_polarity(def_id) {
1196                 if let Some(intercrate_ambiguity_clauses) = &mut self.intercrate_ambiguity_causes {
1197                     let value = tcx
1198                         .get_attr(def_id, sym::rustc_reservation_impl)
1199                         .and_then(|a| a.value_str());
1200                     if let Some(value) = value {
1201                         debug!(
1202                             "filter_reservation_impls: \
1203                                  reservation impl ambiguity on {:?}",
1204                             def_id
1205                         );
1206                         intercrate_ambiguity_clauses.insert(
1207                             IntercrateAmbiguityCause::ReservationImpl {
1208                                 message: value.to_string(),
1209                             },
1210                         );
1211                     }
1212                 }
1213                 return Ok(None);
1214             }
1215         }
1216         Ok(Some(candidate))
1217     }
1218
1219     fn is_knowable<'o>(&mut self, stack: &TraitObligationStack<'o, 'tcx>) -> Result<(), Conflict> {
1220         debug!("is_knowable(intercrate={:?})", self.intercrate);
1221
1222         if !self.intercrate || stack.obligation.polarity() == ty::ImplPolarity::Negative {
1223             return Ok(());
1224         }
1225
1226         let obligation = &stack.obligation;
1227         let predicate = self.infcx().resolve_vars_if_possible(obligation.predicate);
1228
1229         // Okay to skip binder because of the nature of the
1230         // trait-ref-is-knowable check, which does not care about
1231         // bound regions.
1232         let trait_ref = predicate.skip_binder().trait_ref;
1233
1234         coherence::trait_ref_is_knowable(self.tcx(), trait_ref)
1235     }
1236
1237     /// Returns `true` if the global caches can be used.
1238     fn can_use_global_caches(&self, param_env: ty::ParamEnv<'tcx>) -> bool {
1239         // If there are any inference variables in the `ParamEnv`, then we
1240         // always use a cache local to this particular scope. Otherwise, we
1241         // switch to a global cache.
1242         if param_env.needs_infer() {
1243             return false;
1244         }
1245
1246         // Avoid using the master cache during coherence and just rely
1247         // on the local cache. This effectively disables caching
1248         // during coherence. It is really just a simplification to
1249         // avoid us having to fear that coherence results "pollute"
1250         // the master cache. Since coherence executes pretty quickly,
1251         // it's not worth going to more trouble to increase the
1252         // hit-rate, I don't think.
1253         if self.intercrate {
1254             return false;
1255         }
1256
1257         // Otherwise, we can use the global cache.
1258         true
1259     }
1260
1261     fn check_candidate_cache(
1262         &mut self,
1263         mut param_env: ty::ParamEnv<'tcx>,
1264         cache_fresh_trait_pred: ty::PolyTraitPredicate<'tcx>,
1265     ) -> Option<SelectionResult<'tcx, SelectionCandidate<'tcx>>> {
1266         // Neither the global nor local cache is aware of intercrate
1267         // mode, so don't do any caching. In particular, we might
1268         // re-use the same `InferCtxt` with both an intercrate
1269         // and non-intercrate `SelectionContext`
1270         if self.intercrate {
1271             return None;
1272         }
1273         let tcx = self.tcx();
1274         let mut pred = cache_fresh_trait_pred.skip_binder();
1275         pred.remap_constness(&mut param_env);
1276
1277         if self.can_use_global_caches(param_env) {
1278             if let Some(res) = tcx.selection_cache.get(&(param_env, pred), tcx) {
1279                 return Some(res);
1280             }
1281         }
1282         self.infcx.selection_cache.get(&(param_env, pred), tcx)
1283     }
1284
1285     /// Determines whether can we safely cache the result
1286     /// of selecting an obligation. This is almost always `true`,
1287     /// except when dealing with certain `ParamCandidate`s.
1288     ///
1289     /// Ordinarily, a `ParamCandidate` will contain no inference variables,
1290     /// since it was usually produced directly from a `DefId`. However,
1291     /// certain cases (currently only librustdoc's blanket impl finder),
1292     /// a `ParamEnv` may be explicitly constructed with inference types.
1293     /// When this is the case, we do *not* want to cache the resulting selection
1294     /// candidate. This is due to the fact that it might not always be possible
1295     /// to equate the obligation's trait ref and the candidate's trait ref,
1296     /// if more constraints end up getting added to an inference variable.
1297     ///
1298     /// Because of this, we always want to re-run the full selection
1299     /// process for our obligation the next time we see it, since
1300     /// we might end up picking a different `SelectionCandidate` (or none at all).
1301     fn can_cache_candidate(
1302         &self,
1303         result: &SelectionResult<'tcx, SelectionCandidate<'tcx>>,
1304     ) -> bool {
1305         // Neither the global nor local cache is aware of intercrate
1306         // mode, so don't do any caching. In particular, we might
1307         // re-use the same `InferCtxt` with both an intercrate
1308         // and non-intercrate `SelectionContext`
1309         if self.intercrate {
1310             return false;
1311         }
1312         match result {
1313             Ok(Some(SelectionCandidate::ParamCandidate(trait_ref))) => !trait_ref.needs_infer(),
1314             _ => true,
1315         }
1316     }
1317
1318     #[instrument(skip(self, param_env, cache_fresh_trait_pred, dep_node), level = "debug")]
1319     fn insert_candidate_cache(
1320         &mut self,
1321         mut param_env: ty::ParamEnv<'tcx>,
1322         cache_fresh_trait_pred: ty::PolyTraitPredicate<'tcx>,
1323         dep_node: DepNodeIndex,
1324         candidate: SelectionResult<'tcx, SelectionCandidate<'tcx>>,
1325     ) {
1326         let tcx = self.tcx();
1327         let mut pred = cache_fresh_trait_pred.skip_binder();
1328
1329         pred.remap_constness(&mut param_env);
1330
1331         if !self.can_cache_candidate(&candidate) {
1332             debug!(?pred, ?candidate, "insert_candidate_cache - candidate is not cacheable");
1333             return;
1334         }
1335
1336         if self.can_use_global_caches(param_env) {
1337             if let Err(Overflow(OverflowError::Canonical)) = candidate {
1338                 // Don't cache overflow globally; we only produce this in certain modes.
1339             } else if !pred.needs_infer() {
1340                 if !candidate.needs_infer() {
1341                     debug!(?pred, ?candidate, "insert_candidate_cache global");
1342                     // This may overwrite the cache with the same value.
1343                     tcx.selection_cache.insert((param_env, pred), dep_node, candidate);
1344                     return;
1345                 }
1346             }
1347         }
1348
1349         debug!(?pred, ?candidate, "insert_candidate_cache local");
1350         self.infcx.selection_cache.insert((param_env, pred), dep_node, candidate);
1351     }
1352
1353     /// Matches a predicate against the bounds of its self type.
1354     ///
1355     /// Given an obligation like `<T as Foo>::Bar: Baz` where the self type is
1356     /// a projection, look at the bounds of `T::Bar`, see if we can find a
1357     /// `Baz` bound. We return indexes into the list returned by
1358     /// `tcx.item_bounds` for any applicable bounds.
1359     #[instrument(level = "debug", skip(self), ret)]
1360     fn match_projection_obligation_against_definition_bounds(
1361         &mut self,
1362         obligation: &TraitObligation<'tcx>,
1363     ) -> smallvec::SmallVec<[(usize, ty::BoundConstness); 2]> {
1364         let poly_trait_predicate = self.infcx().resolve_vars_if_possible(obligation.predicate);
1365         let placeholder_trait_predicate =
1366             self.infcx().replace_bound_vars_with_placeholders(poly_trait_predicate);
1367         debug!(?placeholder_trait_predicate);
1368
1369         let tcx = self.infcx.tcx;
1370         let (def_id, substs) = match *placeholder_trait_predicate.trait_ref.self_ty().kind() {
1371             ty::Projection(ref data) => (data.item_def_id, data.substs),
1372             ty::Opaque(def_id, substs) => (def_id, substs),
1373             _ => {
1374                 span_bug!(
1375                     obligation.cause.span,
1376                     "match_projection_obligation_against_definition_bounds() called \
1377                      but self-ty is not a projection: {:?}",
1378                     placeholder_trait_predicate.trait_ref.self_ty()
1379                 );
1380             }
1381         };
1382         let bounds = tcx.bound_item_bounds(def_id).subst(tcx, substs);
1383
1384         // The bounds returned by `item_bounds` may contain duplicates after
1385         // normalization, so try to deduplicate when possible to avoid
1386         // unnecessary ambiguity.
1387         let mut distinct_normalized_bounds = FxHashSet::default();
1388
1389         bounds
1390             .iter()
1391             .enumerate()
1392             .filter_map(|(idx, bound)| {
1393                 let bound_predicate = bound.kind();
1394                 if let ty::PredicateKind::Trait(pred) = bound_predicate.skip_binder() {
1395                     let bound = bound_predicate.rebind(pred.trait_ref);
1396                     if self.infcx.probe(|_| {
1397                         match self.match_normalize_trait_ref(
1398                             obligation,
1399                             bound,
1400                             placeholder_trait_predicate.trait_ref,
1401                         ) {
1402                             Ok(None) => true,
1403                             Ok(Some(normalized_trait))
1404                                 if distinct_normalized_bounds.insert(normalized_trait) =>
1405                             {
1406                                 true
1407                             }
1408                             _ => false,
1409                         }
1410                     }) {
1411                         return Some((idx, pred.constness));
1412                     }
1413                 }
1414                 None
1415             })
1416             .collect()
1417     }
1418
1419     /// Equates the trait in `obligation` with trait bound. If the two traits
1420     /// can be equated and the normalized trait bound doesn't contain inference
1421     /// variables or placeholders, the normalized bound is returned.
1422     fn match_normalize_trait_ref(
1423         &mut self,
1424         obligation: &TraitObligation<'tcx>,
1425         trait_bound: ty::PolyTraitRef<'tcx>,
1426         placeholder_trait_ref: ty::TraitRef<'tcx>,
1427     ) -> Result<Option<ty::PolyTraitRef<'tcx>>, ()> {
1428         debug_assert!(!placeholder_trait_ref.has_escaping_bound_vars());
1429         if placeholder_trait_ref.def_id != trait_bound.def_id() {
1430             // Avoid unnecessary normalization
1431             return Err(());
1432         }
1433
1434         let Normalized { value: trait_bound, obligations: _ } = ensure_sufficient_stack(|| {
1435             project::normalize_with_depth(
1436                 self,
1437                 obligation.param_env,
1438                 obligation.cause.clone(),
1439                 obligation.recursion_depth + 1,
1440                 trait_bound,
1441             )
1442         });
1443         self.infcx
1444             .at(&obligation.cause, obligation.param_env)
1445             .define_opaque_types(false)
1446             .sup(ty::Binder::dummy(placeholder_trait_ref), trait_bound)
1447             .map(|InferOk { obligations: _, value: () }| {
1448                 // This method is called within a probe, so we can't have
1449                 // inference variables and placeholders escape.
1450                 if !trait_bound.needs_infer() && !trait_bound.has_placeholders() {
1451                     Some(trait_bound)
1452                 } else {
1453                     None
1454                 }
1455             })
1456             .map_err(|_| ())
1457     }
1458
1459     fn where_clause_may_apply<'o>(
1460         &mut self,
1461         stack: &TraitObligationStack<'o, 'tcx>,
1462         where_clause_trait_ref: ty::PolyTraitRef<'tcx>,
1463     ) -> Result<EvaluationResult, OverflowError> {
1464         self.evaluation_probe(|this| {
1465             match this.match_where_clause_trait_ref(stack.obligation, where_clause_trait_ref) {
1466                 Ok(obligations) => this.evaluate_predicates_recursively(stack.list(), obligations),
1467                 Err(()) => Ok(EvaluatedToErr),
1468             }
1469         })
1470     }
1471
1472     /// Return `Yes` if the obligation's predicate type applies to the env_predicate, and
1473     /// `No` if it does not. Return `Ambiguous` in the case that the projection type is a GAT,
1474     /// and applying this env_predicate constrains any of the obligation's GAT substitutions.
1475     ///
1476     /// This behavior is a somewhat of a hack to prevent over-constraining inference variables
1477     /// in cases like #91762.
1478     pub(super) fn match_projection_projections(
1479         &mut self,
1480         obligation: &ProjectionTyObligation<'tcx>,
1481         env_predicate: PolyProjectionPredicate<'tcx>,
1482         potentially_unnormalized_candidates: bool,
1483     ) -> ProjectionMatchesProjection {
1484         let mut nested_obligations = Vec::new();
1485         let infer_predicate = self.infcx.replace_bound_vars_with_fresh_vars(
1486             obligation.cause.span,
1487             LateBoundRegionConversionTime::HigherRankedType,
1488             env_predicate,
1489         );
1490         let infer_projection = if potentially_unnormalized_candidates {
1491             ensure_sufficient_stack(|| {
1492                 project::normalize_with_depth_to(
1493                     self,
1494                     obligation.param_env,
1495                     obligation.cause.clone(),
1496                     obligation.recursion_depth + 1,
1497                     infer_predicate.projection_ty,
1498                     &mut nested_obligations,
1499                 )
1500             })
1501         } else {
1502             infer_predicate.projection_ty
1503         };
1504
1505         let is_match = self
1506             .infcx
1507             .at(&obligation.cause, obligation.param_env)
1508             .define_opaque_types(false)
1509             .sup(obligation.predicate, infer_projection)
1510             .map_or(false, |InferOk { obligations, value: () }| {
1511                 self.evaluate_predicates_recursively(
1512                     TraitObligationStackList::empty(&ProvisionalEvaluationCache::default()),
1513                     nested_obligations.into_iter().chain(obligations),
1514                 )
1515                 .map_or(false, |res| res.may_apply())
1516             });
1517
1518         if is_match {
1519             let generics = self.tcx().generics_of(obligation.predicate.item_def_id);
1520             // FIXME(generic-associated-types): Addresses aggressive inference in #92917.
1521             // If this type is a GAT, and of the GAT substs resolve to something new,
1522             // that means that we must have newly inferred something about the GAT.
1523             // We should give up in that case.
1524             if !generics.params.is_empty()
1525                 && obligation.predicate.substs[generics.parent_count..]
1526                     .iter()
1527                     .any(|&p| p.has_non_region_infer() && self.infcx.shallow_resolve(p) != p)
1528             {
1529                 ProjectionMatchesProjection::Ambiguous
1530             } else {
1531                 ProjectionMatchesProjection::Yes
1532             }
1533         } else {
1534             ProjectionMatchesProjection::No
1535         }
1536     }
1537
1538     ///////////////////////////////////////////////////////////////////////////
1539     // WINNOW
1540     //
1541     // Winnowing is the process of attempting to resolve ambiguity by
1542     // probing further. During the winnowing process, we unify all
1543     // type variables and then we also attempt to evaluate recursive
1544     // bounds to see if they are satisfied.
1545
1546     /// Returns `true` if `victim` should be dropped in favor of
1547     /// `other`. Generally speaking we will drop duplicate
1548     /// candidates and prefer where-clause candidates.
1549     ///
1550     /// See the comment for "SelectionCandidate" for more details.
1551     fn candidate_should_be_dropped_in_favor_of(
1552         &mut self,
1553         victim: &EvaluatedCandidate<'tcx>,
1554         other: &EvaluatedCandidate<'tcx>,
1555         needs_infer: bool,
1556     ) -> bool {
1557         if victim.candidate == other.candidate {
1558             return true;
1559         }
1560
1561         // Check if a bound would previously have been removed when normalizing
1562         // the param_env so that it can be given the lowest priority. See
1563         // #50825 for the motivation for this.
1564         let is_global = |cand: &ty::PolyTraitPredicate<'tcx>| {
1565             cand.is_global() && !cand.has_late_bound_regions()
1566         };
1567
1568         // (*) Prefer `BuiltinCandidate { has_nested: false }`, `PointeeCandidate`,
1569         // `DiscriminantKindCandidate`, `ConstDestructCandidate`
1570         // to anything else.
1571         //
1572         // This is a fix for #53123 and prevents winnowing from accidentally extending the
1573         // lifetime of a variable.
1574         match (&other.candidate, &victim.candidate) {
1575             (_, AutoImplCandidate) | (AutoImplCandidate, _) => {
1576                 bug!(
1577                     "default implementations shouldn't be recorded \
1578                     when there are other valid candidates"
1579                 );
1580             }
1581
1582             // FIXME(@jswrenn): this should probably be more sophisticated
1583             (TransmutabilityCandidate, _) | (_, TransmutabilityCandidate) => false,
1584
1585             // (*)
1586             (
1587                 BuiltinCandidate { has_nested: false }
1588                 | DiscriminantKindCandidate
1589                 | PointeeCandidate
1590                 | ConstDestructCandidate(_),
1591                 _,
1592             ) => true,
1593             (
1594                 _,
1595                 BuiltinCandidate { has_nested: false }
1596                 | DiscriminantKindCandidate
1597                 | PointeeCandidate
1598                 | ConstDestructCandidate(_),
1599             ) => false,
1600
1601             (ParamCandidate(other), ParamCandidate(victim)) => {
1602                 let same_except_bound_vars = other.skip_binder().trait_ref
1603                     == victim.skip_binder().trait_ref
1604                     && other.skip_binder().constness == victim.skip_binder().constness
1605                     && other.skip_binder().polarity == victim.skip_binder().polarity
1606                     && !other.skip_binder().trait_ref.has_escaping_bound_vars();
1607                 if same_except_bound_vars {
1608                     // See issue #84398. In short, we can generate multiple ParamCandidates which are
1609                     // the same except for unused bound vars. Just pick the one with the fewest bound vars
1610                     // or the current one if tied (they should both evaluate to the same answer). This is
1611                     // probably best characterized as a "hack", since we might prefer to just do our
1612                     // best to *not* create essentially duplicate candidates in the first place.
1613                     other.bound_vars().len() <= victim.bound_vars().len()
1614                 } else if other.skip_binder().trait_ref == victim.skip_binder().trait_ref
1615                     && victim.skip_binder().constness == ty::BoundConstness::NotConst
1616                     && other.skip_binder().polarity == victim.skip_binder().polarity
1617                 {
1618                     // Drop otherwise equivalent non-const candidates in favor of const candidates.
1619                     true
1620                 } else {
1621                     false
1622                 }
1623             }
1624
1625             // Drop otherwise equivalent non-const fn pointer candidates
1626             (FnPointerCandidate { .. }, FnPointerCandidate { is_const: false }) => true,
1627
1628             // Global bounds from the where clause should be ignored
1629             // here (see issue #50825). Otherwise, we have a where
1630             // clause so don't go around looking for impls.
1631             // Arbitrarily give param candidates priority
1632             // over projection and object candidates.
1633             (
1634                 ParamCandidate(ref cand),
1635                 ImplCandidate(..)
1636                 | ClosureCandidate
1637                 | GeneratorCandidate
1638                 | FnPointerCandidate { .. }
1639                 | BuiltinObjectCandidate
1640                 | BuiltinUnsizeCandidate
1641                 | TraitUpcastingUnsizeCandidate(_)
1642                 | BuiltinCandidate { .. }
1643                 | TraitAliasCandidate
1644                 | ObjectCandidate(_)
1645                 | ProjectionCandidate(..),
1646             ) => !is_global(cand),
1647             (ObjectCandidate(_) | ProjectionCandidate(..), ParamCandidate(ref cand)) => {
1648                 // Prefer these to a global where-clause bound
1649                 // (see issue #50825).
1650                 is_global(cand)
1651             }
1652             (
1653                 ImplCandidate(_)
1654                 | ClosureCandidate
1655                 | GeneratorCandidate
1656                 | FnPointerCandidate { .. }
1657                 | BuiltinObjectCandidate
1658                 | BuiltinUnsizeCandidate
1659                 | TraitUpcastingUnsizeCandidate(_)
1660                 | BuiltinCandidate { has_nested: true }
1661                 | TraitAliasCandidate,
1662                 ParamCandidate(ref cand),
1663             ) => {
1664                 // Prefer these to a global where-clause bound
1665                 // (see issue #50825).
1666                 is_global(cand) && other.evaluation.must_apply_modulo_regions()
1667             }
1668
1669             (ProjectionCandidate(i, _), ProjectionCandidate(j, _))
1670             | (ObjectCandidate(i), ObjectCandidate(j)) => {
1671                 // Arbitrarily pick the lower numbered candidate for backwards
1672                 // compatibility reasons. Don't let this affect inference.
1673                 i < j && !needs_infer
1674             }
1675             (ObjectCandidate(_), ProjectionCandidate(..))
1676             | (ProjectionCandidate(..), ObjectCandidate(_)) => {
1677                 bug!("Have both object and projection candidate")
1678             }
1679
1680             // Arbitrarily give projection and object candidates priority.
1681             (
1682                 ObjectCandidate(_) | ProjectionCandidate(..),
1683                 ImplCandidate(..)
1684                 | ClosureCandidate
1685                 | GeneratorCandidate
1686                 | FnPointerCandidate { .. }
1687                 | BuiltinObjectCandidate
1688                 | BuiltinUnsizeCandidate
1689                 | TraitUpcastingUnsizeCandidate(_)
1690                 | BuiltinCandidate { .. }
1691                 | TraitAliasCandidate,
1692             ) => true,
1693
1694             (
1695                 ImplCandidate(..)
1696                 | ClosureCandidate
1697                 | GeneratorCandidate
1698                 | FnPointerCandidate { .. }
1699                 | BuiltinObjectCandidate
1700                 | BuiltinUnsizeCandidate
1701                 | TraitUpcastingUnsizeCandidate(_)
1702                 | BuiltinCandidate { .. }
1703                 | TraitAliasCandidate,
1704                 ObjectCandidate(_) | ProjectionCandidate(..),
1705             ) => false,
1706
1707             (&ImplCandidate(other_def), &ImplCandidate(victim_def)) => {
1708                 // See if we can toss out `victim` based on specialization.
1709                 // While this requires us to know *for sure* that the `other` impl applies
1710                 // we still use modulo regions here.
1711                 //
1712                 // This is fine as specialization currently assumes that specializing
1713                 // impls have to be always applicable, meaning that the only allowed
1714                 // region constraints may be constraints also present on the default impl.
1715                 let tcx = self.tcx();
1716                 if other.evaluation.must_apply_modulo_regions() {
1717                     if tcx.specializes((other_def, victim_def)) {
1718                         return true;
1719                     }
1720                 }
1721
1722                 if other.evaluation.must_apply_considering_regions() {
1723                     match tcx.impls_are_allowed_to_overlap(other_def, victim_def) {
1724                         Some(ty::ImplOverlapKind::Permitted { marker: true }) => {
1725                             // Subtle: If the predicate we are evaluating has inference
1726                             // variables, do *not* allow discarding candidates due to
1727                             // marker trait impls.
1728                             //
1729                             // Without this restriction, we could end up accidentally
1730                             // constraining inference variables based on an arbitrarily
1731                             // chosen trait impl.
1732                             //
1733                             // Imagine we have the following code:
1734                             //
1735                             // ```rust
1736                             // #[marker] trait MyTrait {}
1737                             // impl MyTrait for u8 {}
1738                             // impl MyTrait for bool {}
1739                             // ```
1740                             //
1741                             // And we are evaluating the predicate `<_#0t as MyTrait>`.
1742                             //
1743                             // During selection, we will end up with one candidate for each
1744                             // impl of `MyTrait`. If we were to discard one impl in favor
1745                             // of the other, we would be left with one candidate, causing
1746                             // us to "successfully" select the predicate, unifying
1747                             // _#0t with (for example) `u8`.
1748                             //
1749                             // However, we have no reason to believe that this unification
1750                             // is correct - we've essentially just picked an arbitrary
1751                             // *possibility* for _#0t, and required that this be the *only*
1752                             // possibility.
1753                             //
1754                             // Eventually, we will either:
1755                             // 1) Unify all inference variables in the predicate through
1756                             // some other means (e.g. type-checking of a function). We will
1757                             // then be in a position to drop marker trait candidates
1758                             // without constraining inference variables (since there are
1759                             // none left to constrain)
1760                             // 2) Be left with some unconstrained inference variables. We
1761                             // will then correctly report an inference error, since the
1762                             // existence of multiple marker trait impls tells us nothing
1763                             // about which one should actually apply.
1764                             !needs_infer
1765                         }
1766                         Some(_) => true,
1767                         None => false,
1768                     }
1769                 } else {
1770                     false
1771                 }
1772             }
1773
1774             // Everything else is ambiguous
1775             (
1776                 ImplCandidate(_)
1777                 | ClosureCandidate
1778                 | GeneratorCandidate
1779                 | FnPointerCandidate { .. }
1780                 | BuiltinObjectCandidate
1781                 | BuiltinUnsizeCandidate
1782                 | TraitUpcastingUnsizeCandidate(_)
1783                 | BuiltinCandidate { has_nested: true }
1784                 | TraitAliasCandidate,
1785                 ImplCandidate(_)
1786                 | ClosureCandidate
1787                 | GeneratorCandidate
1788                 | FnPointerCandidate { .. }
1789                 | BuiltinObjectCandidate
1790                 | BuiltinUnsizeCandidate
1791                 | TraitUpcastingUnsizeCandidate(_)
1792                 | BuiltinCandidate { has_nested: true }
1793                 | TraitAliasCandidate,
1794             ) => false,
1795         }
1796     }
1797
1798     fn sized_conditions(
1799         &mut self,
1800         obligation: &TraitObligation<'tcx>,
1801     ) -> BuiltinImplConditions<'tcx> {
1802         use self::BuiltinImplConditions::{Ambiguous, None, Where};
1803
1804         // NOTE: binder moved to (*)
1805         let self_ty = self.infcx.shallow_resolve(obligation.predicate.skip_binder().self_ty());
1806
1807         match self_ty.kind() {
1808             ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
1809             | ty::Uint(_)
1810             | ty::Int(_)
1811             | ty::Bool
1812             | ty::Float(_)
1813             | ty::FnDef(..)
1814             | ty::FnPtr(_)
1815             | ty::RawPtr(..)
1816             | ty::Char
1817             | ty::Ref(..)
1818             | ty::Generator(..)
1819             | ty::GeneratorWitness(..)
1820             | ty::Array(..)
1821             | ty::Closure(..)
1822             | ty::Never
1823             | ty::Dynamic(_, _, ty::DynStar)
1824             | ty::Error(_) => {
1825                 // safe for everything
1826                 Where(ty::Binder::dummy(Vec::new()))
1827             }
1828
1829             ty::Str | ty::Slice(_) | ty::Dynamic(..) | ty::Foreign(..) => None,
1830
1831             ty::Tuple(tys) => Where(
1832                 obligation.predicate.rebind(tys.last().map_or_else(Vec::new, |&last| vec![last])),
1833             ),
1834
1835             ty::Adt(def, substs) => {
1836                 let sized_crit = def.sized_constraint(self.tcx());
1837                 // (*) binder moved here
1838                 Where(obligation.predicate.rebind({
1839                     sized_crit
1840                         .0
1841                         .iter()
1842                         .map(|ty| sized_crit.rebind(*ty).subst(self.tcx(), substs))
1843                         .collect()
1844                 }))
1845             }
1846
1847             ty::Projection(_) | ty::Param(_) | ty::Opaque(..) => None,
1848             ty::Infer(ty::TyVar(_)) => Ambiguous,
1849
1850             ty::Placeholder(..)
1851             | ty::Bound(..)
1852             | ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
1853                 bug!("asked to assemble builtin bounds of unexpected type: {:?}", self_ty);
1854             }
1855         }
1856     }
1857
1858     fn copy_clone_conditions(
1859         &mut self,
1860         obligation: &TraitObligation<'tcx>,
1861     ) -> BuiltinImplConditions<'tcx> {
1862         // NOTE: binder moved to (*)
1863         let self_ty = self.infcx.shallow_resolve(obligation.predicate.skip_binder().self_ty());
1864
1865         use self::BuiltinImplConditions::{Ambiguous, None, Where};
1866
1867         match *self_ty.kind() {
1868             ty::Infer(ty::IntVar(_))
1869             | ty::Infer(ty::FloatVar(_))
1870             | ty::FnDef(..)
1871             | ty::FnPtr(_)
1872             | ty::Error(_) => Where(ty::Binder::dummy(Vec::new())),
1873
1874             ty::Uint(_)
1875             | ty::Int(_)
1876             | ty::Bool
1877             | ty::Float(_)
1878             | ty::Char
1879             | ty::RawPtr(..)
1880             | ty::Never
1881             | ty::Ref(_, _, hir::Mutability::Not)
1882             | ty::Array(..) => {
1883                 // Implementations provided in libcore
1884                 None
1885             }
1886
1887             ty::Dynamic(..)
1888             | ty::Str
1889             | ty::Slice(..)
1890             | ty::Generator(_, _, hir::Movability::Static)
1891             | ty::Foreign(..)
1892             | ty::Ref(_, _, hir::Mutability::Mut) => None,
1893
1894             ty::Tuple(tys) => {
1895                 // (*) binder moved here
1896                 Where(obligation.predicate.rebind(tys.iter().collect()))
1897             }
1898
1899             ty::Generator(_, substs, hir::Movability::Movable) => {
1900                 if self.tcx().features().generator_clone {
1901                     let resolved_upvars =
1902                         self.infcx.shallow_resolve(substs.as_generator().tupled_upvars_ty());
1903                     let resolved_witness =
1904                         self.infcx.shallow_resolve(substs.as_generator().witness());
1905                     if resolved_upvars.is_ty_var() || resolved_witness.is_ty_var() {
1906                         // Not yet resolved.
1907                         Ambiguous
1908                     } else {
1909                         let all = substs
1910                             .as_generator()
1911                             .upvar_tys()
1912                             .chain(iter::once(substs.as_generator().witness()))
1913                             .collect::<Vec<_>>();
1914                         Where(obligation.predicate.rebind(all))
1915                     }
1916                 } else {
1917                     None
1918                 }
1919             }
1920
1921             ty::GeneratorWitness(binder) => {
1922                 let witness_tys = binder.skip_binder();
1923                 for witness_ty in witness_tys.iter() {
1924                     let resolved = self.infcx.shallow_resolve(witness_ty);
1925                     if resolved.is_ty_var() {
1926                         return Ambiguous;
1927                     }
1928                 }
1929                 // (*) binder moved here
1930                 let all_vars = self.tcx().mk_bound_variable_kinds(
1931                     obligation.predicate.bound_vars().iter().chain(binder.bound_vars().iter()),
1932                 );
1933                 Where(ty::Binder::bind_with_vars(witness_tys.to_vec(), all_vars))
1934             }
1935
1936             ty::Closure(_, substs) => {
1937                 // (*) binder moved here
1938                 let ty = self.infcx.shallow_resolve(substs.as_closure().tupled_upvars_ty());
1939                 if let ty::Infer(ty::TyVar(_)) = ty.kind() {
1940                     // Not yet resolved.
1941                     Ambiguous
1942                 } else {
1943                     Where(obligation.predicate.rebind(substs.as_closure().upvar_tys().collect()))
1944                 }
1945             }
1946
1947             ty::Adt(..) | ty::Projection(..) | ty::Param(..) | ty::Opaque(..) => {
1948                 // Fallback to whatever user-defined impls exist in this case.
1949                 None
1950             }
1951
1952             ty::Infer(ty::TyVar(_)) => {
1953                 // Unbound type variable. Might or might not have
1954                 // applicable impls and so forth, depending on what
1955                 // those type variables wind up being bound to.
1956                 Ambiguous
1957             }
1958
1959             ty::Placeholder(..)
1960             | ty::Bound(..)
1961             | ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
1962                 bug!("asked to assemble builtin bounds of unexpected type: {:?}", self_ty);
1963             }
1964         }
1965     }
1966
1967     /// For default impls, we need to break apart a type into its
1968     /// "constituent types" -- meaning, the types that it contains.
1969     ///
1970     /// Here are some (simple) examples:
1971     ///
1972     /// ```ignore (illustrative)
1973     /// (i32, u32) -> [i32, u32]
1974     /// Foo where struct Foo { x: i32, y: u32 } -> [i32, u32]
1975     /// Bar<i32> where struct Bar<T> { x: T, y: u32 } -> [i32, u32]
1976     /// Zed<i32> where enum Zed { A(T), B(u32) } -> [i32, u32]
1977     /// ```
1978     fn constituent_types_for_ty(
1979         &self,
1980         t: ty::Binder<'tcx, Ty<'tcx>>,
1981     ) -> ty::Binder<'tcx, Vec<Ty<'tcx>>> {
1982         match *t.skip_binder().kind() {
1983             ty::Uint(_)
1984             | ty::Int(_)
1985             | ty::Bool
1986             | ty::Float(_)
1987             | ty::FnDef(..)
1988             | ty::FnPtr(_)
1989             | ty::Str
1990             | ty::Error(_)
1991             | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
1992             | ty::Never
1993             | ty::Char => ty::Binder::dummy(Vec::new()),
1994
1995             ty::Placeholder(..)
1996             | ty::Dynamic(..)
1997             | ty::Param(..)
1998             | ty::Foreign(..)
1999             | ty::Projection(..)
2000             | ty::Bound(..)
2001             | ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
2002                 bug!("asked to assemble constituent types of unexpected type: {:?}", t);
2003             }
2004
2005             ty::RawPtr(ty::TypeAndMut { ty: element_ty, .. }) | ty::Ref(_, element_ty, _) => {
2006                 t.rebind(vec![element_ty])
2007             }
2008
2009             ty::Array(element_ty, _) | ty::Slice(element_ty) => t.rebind(vec![element_ty]),
2010
2011             ty::Tuple(ref tys) => {
2012                 // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet
2013                 t.rebind(tys.iter().collect())
2014             }
2015
2016             ty::Closure(_, ref substs) => {
2017                 let ty = self.infcx.shallow_resolve(substs.as_closure().tupled_upvars_ty());
2018                 t.rebind(vec![ty])
2019             }
2020
2021             ty::Generator(_, ref substs, _) => {
2022                 let ty = self.infcx.shallow_resolve(substs.as_generator().tupled_upvars_ty());
2023                 let witness = substs.as_generator().witness();
2024                 t.rebind([ty].into_iter().chain(iter::once(witness)).collect())
2025             }
2026
2027             ty::GeneratorWitness(types) => {
2028                 debug_assert!(!types.has_escaping_bound_vars());
2029                 types.map_bound(|types| types.to_vec())
2030             }
2031
2032             // For `PhantomData<T>`, we pass `T`.
2033             ty::Adt(def, substs) if def.is_phantom_data() => t.rebind(substs.types().collect()),
2034
2035             ty::Adt(def, substs) => {
2036                 t.rebind(def.all_fields().map(|f| f.ty(self.tcx(), substs)).collect())
2037             }
2038
2039             ty::Opaque(def_id, substs) => {
2040                 // We can resolve the `impl Trait` to its concrete type,
2041                 // which enforces a DAG between the functions requiring
2042                 // the auto trait bounds in question.
2043                 t.rebind(vec![self.tcx().bound_type_of(def_id).subst(self.tcx(), substs)])
2044             }
2045         }
2046     }
2047
2048     fn collect_predicates_for_types(
2049         &mut self,
2050         param_env: ty::ParamEnv<'tcx>,
2051         cause: ObligationCause<'tcx>,
2052         recursion_depth: usize,
2053         trait_def_id: DefId,
2054         types: ty::Binder<'tcx, Vec<Ty<'tcx>>>,
2055     ) -> Vec<PredicateObligation<'tcx>> {
2056         // Because the types were potentially derived from
2057         // higher-ranked obligations they may reference late-bound
2058         // regions. For example, `for<'a> Foo<&'a i32> : Copy` would
2059         // yield a type like `for<'a> &'a i32`. In general, we
2060         // maintain the invariant that we never manipulate bound
2061         // regions, so we have to process these bound regions somehow.
2062         //
2063         // The strategy is to:
2064         //
2065         // 1. Instantiate those regions to placeholder regions (e.g.,
2066         //    `for<'a> &'a i32` becomes `&0 i32`.
2067         // 2. Produce something like `&'0 i32 : Copy`
2068         // 3. Re-bind the regions back to `for<'a> &'a i32 : Copy`
2069
2070         types
2071             .as_ref()
2072             .skip_binder() // binder moved -\
2073             .iter()
2074             .flat_map(|ty| {
2075                 let ty: ty::Binder<'tcx, Ty<'tcx>> = types.rebind(*ty); // <----/
2076
2077                 let placeholder_ty = self.infcx.replace_bound_vars_with_placeholders(ty);
2078                 let Normalized { value: normalized_ty, mut obligations } =
2079                     ensure_sufficient_stack(|| {
2080                         project::normalize_with_depth(
2081                             self,
2082                             param_env,
2083                             cause.clone(),
2084                             recursion_depth,
2085                             placeholder_ty,
2086                         )
2087                     });
2088                 let placeholder_obligation = predicate_for_trait_def(
2089                     self.tcx(),
2090                     param_env,
2091                     cause.clone(),
2092                     trait_def_id,
2093                     recursion_depth,
2094                     normalized_ty,
2095                     &[],
2096                 );
2097                 obligations.push(placeholder_obligation);
2098                 obligations
2099             })
2100             .collect()
2101     }
2102
2103     ///////////////////////////////////////////////////////////////////////////
2104     // Matching
2105     //
2106     // Matching is a common path used for both evaluation and
2107     // confirmation.  It basically unifies types that appear in impls
2108     // and traits. This does affect the surrounding environment;
2109     // therefore, when used during evaluation, match routines must be
2110     // run inside of a `probe()` so that their side-effects are
2111     // contained.
2112
2113     fn rematch_impl(
2114         &mut self,
2115         impl_def_id: DefId,
2116         obligation: &TraitObligation<'tcx>,
2117     ) -> Normalized<'tcx, SubstsRef<'tcx>> {
2118         let impl_trait_ref = self.tcx().bound_impl_trait_ref(impl_def_id).unwrap();
2119         match self.match_impl(impl_def_id, impl_trait_ref, obligation) {
2120             Ok(substs) => substs,
2121             Err(()) => {
2122                 self.infcx.tcx.sess.delay_span_bug(
2123                     obligation.cause.span,
2124                     &format!(
2125                         "Impl {:?} was matchable against {:?} but now is not",
2126                         impl_def_id, obligation
2127                     ),
2128                 );
2129                 let value = self.infcx.fresh_substs_for_item(obligation.cause.span, impl_def_id);
2130                 let err = self.tcx().ty_error();
2131                 let value = value.fold_with(&mut BottomUpFolder {
2132                     tcx: self.tcx(),
2133                     ty_op: |_| err,
2134                     lt_op: |l| l,
2135                     ct_op: |c| c,
2136                 });
2137                 Normalized { value, obligations: vec![] }
2138             }
2139         }
2140     }
2141
2142     #[instrument(level = "debug", skip(self), ret)]
2143     fn match_impl(
2144         &mut self,
2145         impl_def_id: DefId,
2146         impl_trait_ref: EarlyBinder<ty::TraitRef<'tcx>>,
2147         obligation: &TraitObligation<'tcx>,
2148     ) -> Result<Normalized<'tcx, SubstsRef<'tcx>>, ()> {
2149         let placeholder_obligation =
2150             self.infcx().replace_bound_vars_with_placeholders(obligation.predicate);
2151         let placeholder_obligation_trait_ref = placeholder_obligation.trait_ref;
2152
2153         let impl_substs = self.infcx.fresh_substs_for_item(obligation.cause.span, impl_def_id);
2154
2155         let impl_trait_ref = impl_trait_ref.subst(self.tcx(), impl_substs);
2156
2157         debug!(?impl_trait_ref);
2158
2159         let Normalized { value: impl_trait_ref, obligations: mut nested_obligations } =
2160             ensure_sufficient_stack(|| {
2161                 project::normalize_with_depth(
2162                     self,
2163                     obligation.param_env,
2164                     obligation.cause.clone(),
2165                     obligation.recursion_depth + 1,
2166                     impl_trait_ref,
2167                 )
2168             });
2169
2170         debug!(?impl_trait_ref, ?placeholder_obligation_trait_ref);
2171
2172         let cause = ObligationCause::new(
2173             obligation.cause.span,
2174             obligation.cause.body_id,
2175             ObligationCauseCode::MatchImpl(obligation.cause.clone(), impl_def_id),
2176         );
2177
2178         let InferOk { obligations, .. } = self
2179             .infcx
2180             .at(&cause, obligation.param_env)
2181             .define_opaque_types(false)
2182             .eq(placeholder_obligation_trait_ref, impl_trait_ref)
2183             .map_err(|e| debug!("match_impl: failed eq_trait_refs due to `{e}`"))?;
2184         nested_obligations.extend(obligations);
2185
2186         if !self.intercrate
2187             && self.tcx().impl_polarity(impl_def_id) == ty::ImplPolarity::Reservation
2188         {
2189             debug!("reservation impls only apply in intercrate mode");
2190             return Err(());
2191         }
2192
2193         Ok(Normalized { value: impl_substs, obligations: nested_obligations })
2194     }
2195
2196     fn fast_reject_trait_refs(
2197         &mut self,
2198         obligation: &TraitObligation<'tcx>,
2199         impl_trait_ref: &ty::TraitRef<'tcx>,
2200     ) -> bool {
2201         // We can avoid creating type variables and doing the full
2202         // substitution if we find that any of the input types, when
2203         // simplified, do not match.
2204         let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::AsPlaceholder };
2205         iter::zip(obligation.predicate.skip_binder().trait_ref.substs, impl_trait_ref.substs)
2206             .any(|(obl, imp)| !drcx.generic_args_may_unify(obl, imp))
2207     }
2208
2209     /// Normalize `where_clause_trait_ref` and try to match it against
2210     /// `obligation`. If successful, return any predicates that
2211     /// result from the normalization.
2212     fn match_where_clause_trait_ref(
2213         &mut self,
2214         obligation: &TraitObligation<'tcx>,
2215         where_clause_trait_ref: ty::PolyTraitRef<'tcx>,
2216     ) -> Result<Vec<PredicateObligation<'tcx>>, ()> {
2217         self.match_poly_trait_ref(obligation, where_clause_trait_ref)
2218     }
2219
2220     /// Returns `Ok` if `poly_trait_ref` being true implies that the
2221     /// obligation is satisfied.
2222     #[instrument(skip(self), level = "debug")]
2223     fn match_poly_trait_ref(
2224         &mut self,
2225         obligation: &TraitObligation<'tcx>,
2226         poly_trait_ref: ty::PolyTraitRef<'tcx>,
2227     ) -> Result<Vec<PredicateObligation<'tcx>>, ()> {
2228         self.infcx
2229             .at(&obligation.cause, obligation.param_env)
2230             // We don't want predicates for opaque types to just match all other types,
2231             // if there is an obligation on the opaque type, then that obligation must be met
2232             // opaquely. Otherwise we'd match any obligation to the opaque type and then error
2233             // out later.
2234             .define_opaque_types(false)
2235             .sup(obligation.predicate.to_poly_trait_ref(), poly_trait_ref)
2236             .map(|InferOk { obligations, .. }| obligations)
2237             .map_err(|_| ())
2238     }
2239
2240     ///////////////////////////////////////////////////////////////////////////
2241     // Miscellany
2242
2243     fn match_fresh_trait_refs(
2244         &self,
2245         previous: ty::PolyTraitPredicate<'tcx>,
2246         current: ty::PolyTraitPredicate<'tcx>,
2247         param_env: ty::ParamEnv<'tcx>,
2248     ) -> bool {
2249         let mut matcher = ty::_match::Match::new(self.tcx(), param_env);
2250         matcher.relate(previous, current).is_ok()
2251     }
2252
2253     fn push_stack<'o>(
2254         &mut self,
2255         previous_stack: TraitObligationStackList<'o, 'tcx>,
2256         obligation: &'o TraitObligation<'tcx>,
2257     ) -> TraitObligationStack<'o, 'tcx> {
2258         let fresh_trait_pred = obligation.predicate.fold_with(&mut self.freshener);
2259
2260         let dfn = previous_stack.cache.next_dfn();
2261         let depth = previous_stack.depth() + 1;
2262         TraitObligationStack {
2263             obligation,
2264             fresh_trait_pred,
2265             reached_depth: Cell::new(depth),
2266             previous: previous_stack,
2267             dfn,
2268             depth,
2269         }
2270     }
2271
2272     #[instrument(skip(self), level = "debug")]
2273     fn closure_trait_ref_unnormalized(
2274         &mut self,
2275         obligation: &TraitObligation<'tcx>,
2276         substs: SubstsRef<'tcx>,
2277     ) -> ty::PolyTraitRef<'tcx> {
2278         let closure_sig = substs.as_closure().sig();
2279
2280         debug!(?closure_sig);
2281
2282         // (1) Feels icky to skip the binder here, but OTOH we know
2283         // that the self-type is an unboxed closure type and hence is
2284         // in fact unparameterized (or at least does not reference any
2285         // regions bound in the obligation). Still probably some
2286         // refactoring could make this nicer.
2287         closure_trait_ref_and_return_type(
2288             self.tcx(),
2289             obligation.predicate.def_id(),
2290             obligation.predicate.skip_binder().self_ty(), // (1)
2291             closure_sig,
2292             util::TupleArgumentsFlag::No,
2293         )
2294         .map_bound(|(trait_ref, _)| trait_ref)
2295     }
2296
2297     fn generator_trait_ref_unnormalized(
2298         &mut self,
2299         obligation: &TraitObligation<'tcx>,
2300         substs: SubstsRef<'tcx>,
2301     ) -> ty::PolyTraitRef<'tcx> {
2302         let gen_sig = substs.as_generator().poly_sig();
2303
2304         // (1) Feels icky to skip the binder here, but OTOH we know
2305         // that the self-type is an generator type and hence is
2306         // in fact unparameterized (or at least does not reference any
2307         // regions bound in the obligation). Still probably some
2308         // refactoring could make this nicer.
2309
2310         super::util::generator_trait_ref_and_outputs(
2311             self.tcx(),
2312             obligation.predicate.def_id(),
2313             obligation.predicate.skip_binder().self_ty(), // (1)
2314             gen_sig,
2315         )
2316         .map_bound(|(trait_ref, ..)| trait_ref)
2317     }
2318
2319     /// Returns the obligations that are implied by instantiating an
2320     /// impl or trait. The obligations are substituted and fully
2321     /// normalized. This is used when confirming an impl or default
2322     /// impl.
2323     #[instrument(level = "debug", skip(self, cause, param_env))]
2324     fn impl_or_trait_obligations(
2325         &mut self,
2326         cause: &ObligationCause<'tcx>,
2327         recursion_depth: usize,
2328         param_env: ty::ParamEnv<'tcx>,
2329         def_id: DefId,           // of impl or trait
2330         substs: SubstsRef<'tcx>, // for impl or trait
2331         parent_trait_pred: ty::Binder<'tcx, ty::TraitPredicate<'tcx>>,
2332     ) -> Vec<PredicateObligation<'tcx>> {
2333         let tcx = self.tcx();
2334
2335         // To allow for one-pass evaluation of the nested obligation,
2336         // each predicate must be preceded by the obligations required
2337         // to normalize it.
2338         // for example, if we have:
2339         //    impl<U: Iterator<Item: Copy>, V: Iterator<Item = U>> Foo for V
2340         // the impl will have the following predicates:
2341         //    <V as Iterator>::Item = U,
2342         //    U: Iterator, U: Sized,
2343         //    V: Iterator, V: Sized,
2344         //    <U as Iterator>::Item: Copy
2345         // When we substitute, say, `V => IntoIter<u32>, U => $0`, the last
2346         // obligation will normalize to `<$0 as Iterator>::Item = $1` and
2347         // `$1: Copy`, so we must ensure the obligations are emitted in
2348         // that order.
2349         let predicates = tcx.bound_predicates_of(def_id);
2350         debug!(?predicates);
2351         assert_eq!(predicates.0.parent, None);
2352         let mut obligations = Vec::with_capacity(predicates.0.predicates.len());
2353         for (predicate, span) in predicates.0.predicates {
2354             let span = *span;
2355             let cause = cause.clone().derived_cause(parent_trait_pred, |derived| {
2356                 ImplDerivedObligation(Box::new(ImplDerivedObligationCause {
2357                     derived,
2358                     impl_def_id: def_id,
2359                     span,
2360                 }))
2361             });
2362             let predicate = normalize_with_depth_to(
2363                 self,
2364                 param_env,
2365                 cause.clone(),
2366                 recursion_depth,
2367                 predicates.rebind(*predicate).subst(tcx, substs),
2368                 &mut obligations,
2369             );
2370             obligations.push(Obligation { cause, recursion_depth, param_env, predicate });
2371         }
2372
2373         obligations
2374     }
2375 }
2376
2377 impl<'o, 'tcx> TraitObligationStack<'o, 'tcx> {
2378     fn list(&'o self) -> TraitObligationStackList<'o, 'tcx> {
2379         TraitObligationStackList::with(self)
2380     }
2381
2382     fn cache(&self) -> &'o ProvisionalEvaluationCache<'tcx> {
2383         self.previous.cache
2384     }
2385
2386     fn iter(&'o self) -> TraitObligationStackList<'o, 'tcx> {
2387         self.list()
2388     }
2389
2390     /// Indicates that attempting to evaluate this stack entry
2391     /// required accessing something from the stack at depth `reached_depth`.
2392     fn update_reached_depth(&self, reached_depth: usize) {
2393         assert!(
2394             self.depth >= reached_depth,
2395             "invoked `update_reached_depth` with something under this stack: \
2396              self.depth={} reached_depth={}",
2397             self.depth,
2398             reached_depth,
2399         );
2400         debug!(reached_depth, "update_reached_depth");
2401         let mut p = self;
2402         while reached_depth < p.depth {
2403             debug!(?p.fresh_trait_pred, "update_reached_depth: marking as cycle participant");
2404             p.reached_depth.set(p.reached_depth.get().min(reached_depth));
2405             p = p.previous.head.unwrap();
2406         }
2407     }
2408 }
2409
2410 /// The "provisional evaluation cache" is used to store intermediate cache results
2411 /// when solving auto traits. Auto traits are unusual in that they can support
2412 /// cycles. So, for example, a "proof tree" like this would be ok:
2413 ///
2414 /// - `Foo<T>: Send` :-
2415 ///   - `Bar<T>: Send` :-
2416 ///     - `Foo<T>: Send` -- cycle, but ok
2417 ///   - `Baz<T>: Send`
2418 ///
2419 /// Here, to prove `Foo<T>: Send`, we have to prove `Bar<T>: Send` and
2420 /// `Baz<T>: Send`. Proving `Bar<T>: Send` in turn required `Foo<T>: Send`.
2421 /// For non-auto traits, this cycle would be an error, but for auto traits (because
2422 /// they are coinductive) it is considered ok.
2423 ///
2424 /// However, there is a complication: at the point where we have
2425 /// "proven" `Bar<T>: Send`, we have in fact only proven it
2426 /// *provisionally*. In particular, we proved that `Bar<T>: Send`
2427 /// *under the assumption* that `Foo<T>: Send`. But what if we later
2428 /// find out this assumption is wrong?  Specifically, we could
2429 /// encounter some kind of error proving `Baz<T>: Send`. In that case,
2430 /// `Bar<T>: Send` didn't turn out to be true.
2431 ///
2432 /// In Issue #60010, we found a bug in rustc where it would cache
2433 /// these intermediate results. This was fixed in #60444 by disabling
2434 /// *all* caching for things involved in a cycle -- in our example,
2435 /// that would mean we don't cache that `Bar<T>: Send`.  But this led
2436 /// to large slowdowns.
2437 ///
2438 /// Specifically, imagine this scenario, where proving `Baz<T>: Send`
2439 /// first requires proving `Bar<T>: Send` (which is true:
2440 ///
2441 /// - `Foo<T>: Send` :-
2442 ///   - `Bar<T>: Send` :-
2443 ///     - `Foo<T>: Send` -- cycle, but ok
2444 ///   - `Baz<T>: Send`
2445 ///     - `Bar<T>: Send` -- would be nice for this to be a cache hit!
2446 ///     - `*const T: Send` -- but what if we later encounter an error?
2447 ///
2448 /// The *provisional evaluation cache* resolves this issue. It stores
2449 /// cache results that we've proven but which were involved in a cycle
2450 /// in some way. We track the minimal stack depth (i.e., the
2451 /// farthest from the top of the stack) that we are dependent on.
2452 /// The idea is that the cache results within are all valid -- so long as
2453 /// none of the nodes in between the current node and the node at that minimum
2454 /// depth result in an error (in which case the cached results are just thrown away).
2455 ///
2456 /// During evaluation, we consult this provisional cache and rely on
2457 /// it. Accessing a cached value is considered equivalent to accessing
2458 /// a result at `reached_depth`, so it marks the *current* solution as
2459 /// provisional as well. If an error is encountered, we toss out any
2460 /// provisional results added from the subtree that encountered the
2461 /// error.  When we pop the node at `reached_depth` from the stack, we
2462 /// can commit all the things that remain in the provisional cache.
2463 struct ProvisionalEvaluationCache<'tcx> {
2464     /// next "depth first number" to issue -- just a counter
2465     dfn: Cell<usize>,
2466
2467     /// Map from cache key to the provisionally evaluated thing.
2468     /// The cache entries contain the result but also the DFN in which they
2469     /// were added. The DFN is used to clear out values on failure.
2470     ///
2471     /// Imagine we have a stack like:
2472     ///
2473     /// - `A B C` and we add a cache for the result of C (DFN 2)
2474     /// - Then we have a stack `A B D` where `D` has DFN 3
2475     /// - We try to solve D by evaluating E: `A B D E` (DFN 4)
2476     /// - `E` generates various cache entries which have cyclic dependencies on `B`
2477     ///   - `A B D E F` and so forth
2478     ///   - the DFN of `F` for example would be 5
2479     /// - then we determine that `E` is in error -- we will then clear
2480     ///   all cache values whose DFN is >= 4 -- in this case, that
2481     ///   means the cached value for `F`.
2482     map: RefCell<FxHashMap<ty::PolyTraitPredicate<'tcx>, ProvisionalEvaluation>>,
2483
2484     /// The stack of args that we assume to be true because a `WF(arg)` predicate
2485     /// is on the stack above (and because of wellformedness is coinductive).
2486     /// In an "ideal" world, this would share a stack with trait predicates in
2487     /// `TraitObligationStack`. However, trait predicates are *much* hotter than
2488     /// `WellFormed` predicates, and it's very likely that the additional matches
2489     /// will have a perf effect. The value here is the well-formed `GenericArg`
2490     /// and the depth of the trait predicate *above* that well-formed predicate.
2491     wf_args: RefCell<Vec<(ty::GenericArg<'tcx>, usize)>>,
2492 }
2493
2494 /// A cache value for the provisional cache: contains the depth-first
2495 /// number (DFN) and result.
2496 #[derive(Copy, Clone, Debug)]
2497 struct ProvisionalEvaluation {
2498     from_dfn: usize,
2499     reached_depth: usize,
2500     result: EvaluationResult,
2501 }
2502
2503 impl<'tcx> Default for ProvisionalEvaluationCache<'tcx> {
2504     fn default() -> Self {
2505         Self { dfn: Cell::new(0), map: Default::default(), wf_args: Default::default() }
2506     }
2507 }
2508
2509 impl<'tcx> ProvisionalEvaluationCache<'tcx> {
2510     /// Get the next DFN in sequence (basically a counter).
2511     fn next_dfn(&self) -> usize {
2512         let result = self.dfn.get();
2513         self.dfn.set(result + 1);
2514         result
2515     }
2516
2517     /// Check the provisional cache for any result for
2518     /// `fresh_trait_ref`. If there is a hit, then you must consider
2519     /// it an access to the stack slots at depth
2520     /// `reached_depth` (from the returned value).
2521     fn get_provisional(
2522         &self,
2523         fresh_trait_pred: ty::PolyTraitPredicate<'tcx>,
2524     ) -> Option<ProvisionalEvaluation> {
2525         debug!(
2526             ?fresh_trait_pred,
2527             "get_provisional = {:#?}",
2528             self.map.borrow().get(&fresh_trait_pred),
2529         );
2530         Some(*self.map.borrow().get(&fresh_trait_pred)?)
2531     }
2532
2533     /// Insert a provisional result into the cache. The result came
2534     /// from the node with the given DFN. It accessed a minimum depth
2535     /// of `reached_depth` to compute. It evaluated `fresh_trait_pred`
2536     /// and resulted in `result`.
2537     fn insert_provisional(
2538         &self,
2539         from_dfn: usize,
2540         reached_depth: usize,
2541         fresh_trait_pred: ty::PolyTraitPredicate<'tcx>,
2542         result: EvaluationResult,
2543     ) {
2544         debug!(?from_dfn, ?fresh_trait_pred, ?result, "insert_provisional");
2545
2546         let mut map = self.map.borrow_mut();
2547
2548         // Subtle: when we complete working on the DFN `from_dfn`, anything
2549         // that remains in the provisional cache must be dependent on some older
2550         // stack entry than `from_dfn`. We have to update their depth with our transitive
2551         // depth in that case or else it would be referring to some popped note.
2552         //
2553         // Example:
2554         // A (reached depth 0)
2555         //   ...
2556         //      B // depth 1 -- reached depth = 0
2557         //          C // depth 2 -- reached depth = 1 (should be 0)
2558         //              B
2559         //          A // depth 0
2560         //   D (reached depth 1)
2561         //      C (cache -- reached depth = 2)
2562         for (_k, v) in &mut *map {
2563             if v.from_dfn >= from_dfn {
2564                 v.reached_depth = reached_depth.min(v.reached_depth);
2565             }
2566         }
2567
2568         map.insert(fresh_trait_pred, ProvisionalEvaluation { from_dfn, reached_depth, result });
2569     }
2570
2571     /// Invoked when the node with dfn `dfn` does not get a successful
2572     /// result.  This will clear out any provisional cache entries
2573     /// that were added since `dfn` was created. This is because the
2574     /// provisional entries are things which must assume that the
2575     /// things on the stack at the time of their creation succeeded --
2576     /// since the failing node is presently at the top of the stack,
2577     /// these provisional entries must either depend on it or some
2578     /// ancestor of it.
2579     fn on_failure(&self, dfn: usize) {
2580         debug!(?dfn, "on_failure");
2581         self.map.borrow_mut().retain(|key, eval| {
2582             if !eval.from_dfn >= dfn {
2583                 debug!("on_failure: removing {:?}", key);
2584                 false
2585             } else {
2586                 true
2587             }
2588         });
2589     }
2590
2591     /// Invoked when the node at depth `depth` completed without
2592     /// depending on anything higher in the stack (if that completion
2593     /// was a failure, then `on_failure` should have been invoked
2594     /// already).
2595     ///
2596     /// Note that we may still have provisional cache items remaining
2597     /// in the cache when this is done. For example, if there is a
2598     /// cycle:
2599     ///
2600     /// * A depends on...
2601     ///     * B depends on A
2602     ///     * C depends on...
2603     ///         * D depends on C
2604     ///     * ...
2605     ///
2606     /// Then as we complete the C node we will have a provisional cache
2607     /// with results for A, B, C, and D. This method would clear out
2608     /// the C and D results, but leave A and B provisional.
2609     ///
2610     /// This is determined based on the DFN: we remove any provisional
2611     /// results created since `dfn` started (e.g., in our example, dfn
2612     /// would be 2, representing the C node, and hence we would
2613     /// remove the result for D, which has DFN 3, but not the results for
2614     /// A and B, which have DFNs 0 and 1 respectively).
2615     ///
2616     /// Note that we *do not* attempt to cache these cycle participants
2617     /// in the evaluation cache. Doing so would require carefully computing
2618     /// the correct `DepNode` to store in the cache entry:
2619     /// cycle participants may implicitly depend on query results
2620     /// related to other participants in the cycle, due to our logic
2621     /// which examines the evaluation stack.
2622     ///
2623     /// We used to try to perform this caching,
2624     /// but it lead to multiple incremental compilation ICEs
2625     /// (see #92987 and #96319), and was very hard to understand.
2626     /// Fortunately, removing the caching didn't seem to
2627     /// have a performance impact in practice.
2628     fn on_completion(&self, dfn: usize) {
2629         debug!(?dfn, "on_completion");
2630
2631         for (fresh_trait_pred, eval) in
2632             self.map.borrow_mut().drain_filter(|_k, eval| eval.from_dfn >= dfn)
2633         {
2634             debug!(?fresh_trait_pred, ?eval, "on_completion");
2635         }
2636     }
2637 }
2638
2639 #[derive(Copy, Clone)]
2640 struct TraitObligationStackList<'o, 'tcx> {
2641     cache: &'o ProvisionalEvaluationCache<'tcx>,
2642     head: Option<&'o TraitObligationStack<'o, 'tcx>>,
2643 }
2644
2645 impl<'o, 'tcx> TraitObligationStackList<'o, 'tcx> {
2646     fn empty(cache: &'o ProvisionalEvaluationCache<'tcx>) -> TraitObligationStackList<'o, 'tcx> {
2647         TraitObligationStackList { cache, head: None }
2648     }
2649
2650     fn with(r: &'o TraitObligationStack<'o, 'tcx>) -> TraitObligationStackList<'o, 'tcx> {
2651         TraitObligationStackList { cache: r.cache(), head: Some(r) }
2652     }
2653
2654     fn head(&self) -> Option<&'o TraitObligationStack<'o, 'tcx>> {
2655         self.head
2656     }
2657
2658     fn depth(&self) -> usize {
2659         if let Some(head) = self.head { head.depth } else { 0 }
2660     }
2661 }
2662
2663 impl<'o, 'tcx> Iterator for TraitObligationStackList<'o, 'tcx> {
2664     type Item = &'o TraitObligationStack<'o, 'tcx>;
2665
2666     fn next(&mut self) -> Option<&'o TraitObligationStack<'o, 'tcx>> {
2667         let o = self.head?;
2668         *self = o.previous;
2669         Some(o)
2670     }
2671 }
2672
2673 impl<'o, 'tcx> fmt::Debug for TraitObligationStack<'o, 'tcx> {
2674     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2675         write!(f, "TraitObligationStack({:?})", self.obligation)
2676     }
2677 }
2678
2679 pub enum ProjectionMatchesProjection {
2680     Yes,
2681     Ambiguous,
2682     No,
2683 }