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