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

   1 //! Candidate assembly.
   2 //!
   3 //! The selection process begins by examining all in-scope impls,
   4 //! caller obligations, and so forth and assembling a list of
   5 //! candidates. See the [rustc dev guide] for more details.
   6 //!
   7 //! [rustc dev guide]:https://rustc-dev-guide.rust-lang.org/traits/resolution.html#candidate-assembly
   8 use rustc_hir as hir;
   9 use rustc_hir::def_id::DefId;
  10 use rustc_infer::traits::TraitEngine;
  11 use rustc_infer::traits::{Obligation, SelectionError, TraitObligation};
  12 use rustc_lint_defs::builtin::DEREF_INTO_DYN_SUPERTRAIT;
  13 use rustc_middle::ty::print::with_no_trimmed_paths;
  14 use rustc_middle::ty::{self, ToPredicate, Ty, TypeFoldable, WithConstness};
  15 use rustc_target::spec::abi::Abi;
  16
  17 use crate::traits;
  18 use crate::traits::coherence::Conflict;
  19 use crate::traits::query::evaluate_obligation::InferCtxtExt;
  20 use crate::traits::{util, SelectionResult};
  21 use crate::traits::{Ambiguous, ErrorReporting, Overflow, Unimplemented};
  22
  23 use super::BuiltinImplConditions;
  24 use super::IntercrateAmbiguityCause;
  25 use super::OverflowError;
  26 use super::SelectionCandidate::{self, *};
  27 use super::{EvaluatedCandidate, SelectionCandidateSet, SelectionContext, TraitObligationStack};
  28
  29 impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
  30     #[instrument(level = "debug", skip(self))]
  31     pub(super) fn candidate_from_obligation<'o>(
  32         &mut self,
  33         stack: &TraitObligationStack<'o, 'tcx>,
  34     ) -> SelectionResult<'tcx, SelectionCandidate<'tcx>> {
  35         // Watch out for overflow. This intentionally bypasses (and does
  36         // not update) the cache.
  37         self.check_recursion_limit(&stack.obligation, &stack.obligation)?;
  38
  39         // Check the cache. Note that we freshen the trait-ref
  40         // separately rather than using `stack.fresh_trait_ref` --
  41         // this is because we want the unbound variables to be
  42         // replaced with fresh types starting from index 0.
  43         let cache_fresh_trait_pred = self.infcx.freshen(stack.obligation.predicate);
  44         debug!(?cache_fresh_trait_pred);
  45         debug_assert!(!stack.obligation.predicate.has_escaping_bound_vars());
  46
  47         if let Some(c) =
  48             self.check_candidate_cache(stack.obligation.param_env, cache_fresh_trait_pred)
  49         {
  50             debug!(candidate = ?c, "CACHE HIT");
  51             return c;
  52         }
  53
  54         // If no match, compute result and insert into cache.
  55         //
  56         // FIXME(nikomatsakis) -- this cache is not taking into
  57         // account cycles that may have occurred in forming the
  58         // candidate. I don't know of any specific problems that
  59         // result but it seems awfully suspicious.
  60         let (candidate, dep_node) =
  61             self.in_task(|this| this.candidate_from_obligation_no_cache(stack));
  62
  63         debug!(?candidate, "CACHE MISS");
  64         self.insert_candidate_cache(
  65             stack.obligation.param_env,
  66             cache_fresh_trait_pred,
  67             dep_node,
  68             candidate.clone(),
  69         );
  70         candidate
  71     }
  72
  73     fn candidate_from_obligation_no_cache<'o>(
  74         &mut self,
  75         stack: &TraitObligationStack<'o, 'tcx>,
  76     ) -> SelectionResult<'tcx, SelectionCandidate<'tcx>> {
  77         if let Some(conflict) = self.is_knowable(stack) {
  78             debug!("coherence stage: not knowable");
  79             if self.intercrate_ambiguity_causes.is_some() {
  80                 debug!("evaluate_stack: intercrate_ambiguity_causes is some");
  81                 // Heuristics: show the diagnostics when there are no candidates in crate.
  82                 if let Ok(candidate_set) = self.assemble_candidates(stack) {
  83                     let mut no_candidates_apply = true;
  84
  85                     for c in candidate_set.vec.iter() {
  86                         if self.evaluate_candidate(stack, &c)?.may_apply() {
  87                             no_candidates_apply = false;
  88                             break;
  89                         }
  90                     }
  91
  92                     if !candidate_set.ambiguous && no_candidates_apply {
  93                         let trait_ref = stack.obligation.predicate.skip_binder().trait_ref;
  94                         let self_ty = trait_ref.self_ty();
  95                         let (trait_desc, self_desc) = with_no_trimmed_paths(|| {
  96                             let trait_desc = trait_ref.print_only_trait_path().to_string();
  97                             let self_desc = if self_ty.has_concrete_skeleton() {
  98                                 Some(self_ty.to_string())
  99                             } else {
 100                                 None
 101                             };
 102                             (trait_desc, self_desc)
 103                         });
 104                         let cause = if let Conflict::Upstream = conflict {
 105                             IntercrateAmbiguityCause::UpstreamCrateUpdate { trait_desc, self_desc }
 106                         } else {
 107                             IntercrateAmbiguityCause::DownstreamCrate { trait_desc, self_desc }
 108                         };
 109                         debug!(?cause, "evaluate_stack: pushing cause");
 110                         self.intercrate_ambiguity_causes.as_mut().unwrap().push(cause);
 111                     }
 112                 }
 113             }
 114             return Ok(None);
 115         }
 116
 117         let candidate_set = self.assemble_candidates(stack)?;
 118
 119         if candidate_set.ambiguous {
 120             debug!("candidate set contains ambig");
 121             return Ok(None);
 122         }
 123
 124         let candidates = candidate_set.vec;
 125
 126         debug!(?stack, ?candidates, "assembled {} candidates", candidates.len());
 127
 128         // At this point, we know that each of the entries in the
 129         // candidate set is *individually* applicable. Now we have to
 130         // figure out if they contain mutual incompatibilities. This
 131         // frequently arises if we have an unconstrained input type --
 132         // for example, we are looking for `$0: Eq` where `$0` is some
 133         // unconstrained type variable. In that case, we'll get a
 134         // candidate which assumes $0 == int, one that assumes `$0 ==
 135         // usize`, etc. This spells an ambiguity.
 136
 137         let mut candidates = self.filter_impls(candidates, stack.obligation);
 138
 139         // If there is more than one candidate, first winnow them down
 140         // by considering extra conditions (nested obligations and so
 141         // forth). We don't winnow if there is exactly one
 142         // candidate. This is a relatively minor distinction but it
 143         // can lead to better inference and error-reporting. An
 144         // example would be if there was an impl:
 145         //
 146         //     impl<T:Clone> Vec<T> { fn push_clone(...) { ... } }
 147         //
 148         // and we were to see some code `foo.push_clone()` where `boo`
 149         // is a `Vec<Bar>` and `Bar` does not implement `Clone`.  If
 150         // we were to winnow, we'd wind up with zero candidates.
 151         // Instead, we select the right impl now but report "`Bar` does
 152         // not implement `Clone`".
 153         if candidates.len() == 1 {
 154             return self.filter_reservation_impls(candidates.pop().unwrap(), stack.obligation);
 155         }
 156
 157         // Winnow, but record the exact outcome of evaluation, which
 158         // is needed for specialization. Propagate overflow if it occurs.
 159         let mut candidates = candidates
 160             .into_iter()
 161             .map(|c| match self.evaluate_candidate(stack, &c) {
 162                 Ok(eval) if eval.may_apply() => {
 163                     Ok(Some(EvaluatedCandidate { candidate: c, evaluation: eval }))
 164                 }
 165                 Ok(_) => Ok(None),
 166                 Err(OverflowError::Canonical) => Err(Overflow),
 167                 Err(OverflowError::ErrorReporting) => Err(ErrorReporting),
 168             })
 169             .flat_map(Result::transpose)
 170             .collect::<Result<Vec<_>, _>>()?;
 171
 172         debug!(?stack, ?candidates, "winnowed to {} candidates", candidates.len());
 173
 174         let needs_infer = stack.obligation.predicate.has_infer_types_or_consts();
 175
 176         // If there are STILL multiple candidates, we can further
 177         // reduce the list by dropping duplicates -- including
 178         // resolving specializations.
 179         if candidates.len() > 1 {
 180             let mut i = 0;
 181             while i < candidates.len() {
 182                 let is_dup = (0..candidates.len()).filter(|&j| i != j).any(|j| {
 183                     self.candidate_should_be_dropped_in_favor_of(
 184                         &candidates[i],
 185                         &candidates[j],
 186                         needs_infer,
 187                     )
 188                 });
 189                 if is_dup {
 190                     debug!(candidate = ?candidates[i], "Dropping candidate #{}/{}", i, candidates.len());
 191                     candidates.swap_remove(i);
 192                 } else {
 193                     debug!(candidate = ?candidates[i], "Retaining candidate #{}/{}", i, candidates.len());
 194                     i += 1;
 195
 196                     // If there are *STILL* multiple candidates, give up
 197                     // and report ambiguity.
 198                     if i > 1 {
 199                         debug!("multiple matches, ambig");
 200                         return Err(Ambiguous(
 201                             candidates
 202                                 .into_iter()
 203                                 .filter_map(|c| match c.candidate {
 204                                     SelectionCandidate::ImplCandidate(def_id) => Some(def_id),
 205                                     _ => None,
 206                                 })
 207                                 .collect(),
 208                         ));
 209                     }
 210                 }
 211             }
 212         }
 213
 214         // If there are *NO* candidates, then there are no impls --
 215         // that we know of, anyway. Note that in the case where there
 216         // are unbound type variables within the obligation, it might
 217         // be the case that you could still satisfy the obligation
 218         // from another crate by instantiating the type variables with
 219         // a type from another crate that does have an impl. This case
 220         // is checked for in `evaluate_stack` (and hence users
 221         // who might care about this case, like coherence, should use
 222         // that function).
 223         if candidates.is_empty() {
 224             // If there's an error type, 'downgrade' our result from
 225             // `Err(Unimplemented)` to `Ok(None)`. This helps us avoid
 226             // emitting additional spurious errors, since we're guaranteed
 227             // to have emitted at least one.
 228             if stack.obligation.references_error() {
 229                 debug!("no results for error type, treating as ambiguous");
 230                 return Ok(None);
 231             }
 232             return Err(Unimplemented);
 233         }
 234
 235         // Just one candidate left.
 236         self.filter_reservation_impls(candidates.pop().unwrap().candidate, stack.obligation)
 237     }
 238
 239     #[instrument(skip(self, stack), level = "debug")]
 240     pub(super) fn assemble_candidates<'o>(
 241         &mut self,
 242         stack: &TraitObligationStack<'o, 'tcx>,
 243     ) -> Result<SelectionCandidateSet<'tcx>, SelectionError<'tcx>> {
 244         let TraitObligationStack { obligation, .. } = *stack;
 245         let obligation = &Obligation {
 246             param_env: obligation.param_env,
 247             cause: obligation.cause.clone(),
 248             recursion_depth: obligation.recursion_depth,
 249             predicate: self.infcx().resolve_vars_if_possible(obligation.predicate),
 250         };
 251
 252         if obligation.predicate.skip_binder().self_ty().is_ty_var() {
 253             // Self is a type variable (e.g., `_: AsRef<str>`).
 254             //
 255             // This is somewhat problematic, as the current scheme can't really
 256             // handle it turning to be a projection. This does end up as truly
 257             // ambiguous in most cases anyway.
 258             //
 259             // Take the fast path out - this also improves
 260             // performance by preventing assemble_candidates_from_impls from
 261             // matching every impl for this trait.
 262             return Ok(SelectionCandidateSet { vec: vec![], ambiguous: true });
 263         }
 264
 265         let mut candidates = SelectionCandidateSet { vec: Vec::new(), ambiguous: false };
 266
 267         // The only way to prove a NotImplemented(T: Foo) predicate is via a negative impl.
 268         // There are no compiler built-in rules for this.
 269         if obligation.polarity() == ty::ImplPolarity::Negative {
 270             self.assemble_candidates_for_trait_alias(obligation, &mut candidates);
 271             self.assemble_candidates_from_impls(obligation, &mut candidates);
 272         } else {
 273             self.assemble_candidates_for_trait_alias(obligation, &mut candidates);
 274
 275             // Other bounds. Consider both in-scope bounds from fn decl
 276             // and applicable impls. There is a certain set of precedence rules here.
 277             let def_id = obligation.predicate.def_id();
 278             let lang_items = self.tcx().lang_items();
 279
 280             if lang_items.copy_trait() == Some(def_id) {
 281                 debug!(obligation_self_ty = ?obligation.predicate.skip_binder().self_ty());
 282
 283                 // User-defined copy impls are permitted, but only for
 284                 // structs and enums.
 285                 self.assemble_candidates_from_impls(obligation, &mut candidates);
 286
 287                 // For other types, we'll use the builtin rules.
 288                 let copy_conditions = self.copy_clone_conditions(obligation);
 289                 self.assemble_builtin_bound_candidates(copy_conditions, &mut candidates);
 290             } else if lang_items.discriminant_kind_trait() == Some(def_id) {
 291                 // `DiscriminantKind` is automatically implemented for every type.
 292                 candidates.vec.push(DiscriminantKindCandidate);
 293             } else if lang_items.pointee_trait() == Some(def_id) {
 294                 // `Pointee` is automatically implemented for every type.
 295                 candidates.vec.push(PointeeCandidate);
 296             } else if lang_items.sized_trait() == Some(def_id) {
 297                 // Sized is never implementable by end-users, it is
 298                 // always automatically computed.
 299                 let sized_conditions = self.sized_conditions(obligation);
 300                 self.assemble_builtin_bound_candidates(sized_conditions, &mut candidates);
 301             } else if lang_items.unsize_trait() == Some(def_id) {
 302                 self.assemble_candidates_for_unsizing(obligation, &mut candidates);
 303             } else if lang_items.drop_trait() == Some(def_id)
 304                 && obligation.predicate.skip_binder().constness == ty::BoundConstness::ConstIfConst
 305             {
 306                 if self.is_in_const_context {
 307                     self.assemble_const_drop_candidates(obligation, &mut candidates)?;
 308                 } else {
 309                     debug!("passing ~const Drop bound; in non-const context");
 310                     // `~const Drop` when we are not in a const context has no effect.
 311                     candidates.vec.push(ConstDropCandidate)
 312                 }
 313             } else {
 314                 if lang_items.clone_trait() == Some(def_id) {
 315                     // Same builtin conditions as `Copy`, i.e., every type which has builtin support
 316                     // for `Copy` also has builtin support for `Clone`, and tuples/arrays of `Clone`
 317                     // types have builtin support for `Clone`.
 318                     let clone_conditions = self.copy_clone_conditions(obligation);
 319                     self.assemble_builtin_bound_candidates(clone_conditions, &mut candidates);
 320                 }
 321
 322                 self.assemble_generator_candidates(obligation, &mut candidates);
 323                 self.assemble_closure_candidates(obligation, &mut candidates);
 324                 self.assemble_fn_pointer_candidates(obligation, &mut candidates);
 325                 self.assemble_candidates_from_impls(obligation, &mut candidates);
 326                 self.assemble_candidates_from_object_ty(obligation, &mut candidates);
 327             }
 328
 329             self.assemble_candidates_from_projected_tys(obligation, &mut candidates);
 330             self.assemble_candidates_from_caller_bounds(stack, &mut candidates)?;
 331             // Auto implementations have lower priority, so we only
 332             // consider triggering a default if there is no other impl that can apply.
 333             if candidates.vec.is_empty() {
 334                 self.assemble_candidates_from_auto_impls(obligation, &mut candidates);
 335             }
 336         }
 337         debug!("candidate list size: {}", candidates.vec.len());
 338         Ok(candidates)
 339     }
 340
 341     fn assemble_candidates_from_projected_tys(
 342         &mut self,
 343         obligation: &TraitObligation<'tcx>,
 344         candidates: &mut SelectionCandidateSet<'tcx>,
 345     ) {
 346         debug!(?obligation, "assemble_candidates_from_projected_tys");
 347
 348         // Before we go into the whole placeholder thing, just
 349         // quickly check if the self-type is a projection at all.
 350         match obligation.predicate.skip_binder().trait_ref.self_ty().kind() {
 351             ty::Projection(_) | ty::Opaque(..) => {}
 352             ty::Infer(ty::TyVar(_)) => {
 353                 span_bug!(
 354                     obligation.cause.span,
 355                     "Self=_ should have been handled by assemble_candidates"
 356                 );
 357             }
 358             _ => return,
 359         }
 360
 361         let result = self
 362             .infcx
 363             .probe(|_| self.match_projection_obligation_against_definition_bounds(obligation));
 364
 365         for predicate_index in result {
 366             candidates.vec.push(ProjectionCandidate(predicate_index));
 367         }
 368     }
 369
 370     /// Given an obligation like `<SomeTrait for T>`, searches the obligations that the caller
 371     /// supplied to find out whether it is listed among them.
 372     ///
 373     /// Never affects the inference environment.
 374     fn assemble_candidates_from_caller_bounds<'o>(
 375         &mut self,
 376         stack: &TraitObligationStack<'o, 'tcx>,
 377         candidates: &mut SelectionCandidateSet<'tcx>,
 378     ) -> Result<(), SelectionError<'tcx>> {
 379         debug!(?stack.obligation, "assemble_candidates_from_caller_bounds");
 380
 381         let all_bounds = stack
 382             .obligation
 383             .param_env
 384             .caller_bounds()
 385             .iter()
 386             .filter_map(|o| o.to_opt_poly_trait_ref());
 387
 388         // Micro-optimization: filter out predicates relating to different traits.
 389         let matching_bounds =
 390             all_bounds.filter(|p| p.value.def_id() == stack.obligation.predicate.def_id());
 391
 392         // Keep only those bounds which may apply, and propagate overflow if it occurs.
 393         for bound in matching_bounds {
 394             let wc = self.evaluate_where_clause(stack, bound.value)?;
 395             if wc.may_apply() {
 396                 candidates.vec.push(ParamCandidate((bound, stack.obligation.polarity())));
 397             }
 398         }
 399
 400         Ok(())
 401     }
 402
 403     fn assemble_generator_candidates(
 404         &mut self,
 405         obligation: &TraitObligation<'tcx>,
 406         candidates: &mut SelectionCandidateSet<'tcx>,
 407     ) {
 408         if self.tcx().lang_items().gen_trait() != Some(obligation.predicate.def_id()) {
 409             return;
 410         }
 411
 412         // Okay to skip binder because the substs on generator types never
 413         // touch bound regions, they just capture the in-scope
 414         // type/region parameters.
 415         let self_ty = obligation.self_ty().skip_binder();
 416         match self_ty.kind() {
 417             ty::Generator(..) => {
 418                 debug!(?self_ty, ?obligation, "assemble_generator_candidates",);
 419
 420                 candidates.vec.push(GeneratorCandidate);
 421             }
 422             ty::Infer(ty::TyVar(_)) => {
 423                 debug!("assemble_generator_candidates: ambiguous self-type");
 424                 candidates.ambiguous = true;
 425             }
 426             _ => {}
 427         }
 428     }
 429
 430     /// Checks for the artificial impl that the compiler will create for an obligation like `X :
 431     /// FnMut<..>` where `X` is a closure type.
 432     ///
 433     /// Note: the type parameters on a closure candidate are modeled as *output* type
 434     /// parameters and hence do not affect whether this trait is a match or not. They will be
 435     /// unified during the confirmation step.
 436     fn assemble_closure_candidates(
 437         &mut self,
 438         obligation: &TraitObligation<'tcx>,
 439         candidates: &mut SelectionCandidateSet<'tcx>,
 440     ) {
 441         let kind = match self.tcx().fn_trait_kind_from_lang_item(obligation.predicate.def_id()) {
 442             Some(k) => k,
 443             None => {
 444                 return;
 445             }
 446         };
 447
 448         // Okay to skip binder because the substs on closure types never
 449         // touch bound regions, they just capture the in-scope
 450         // type/region parameters
 451         match *obligation.self_ty().skip_binder().kind() {
 452             ty::Closure(_, closure_substs) => {
 453                 debug!(?kind, ?obligation, "assemble_unboxed_candidates");
 454                 match self.infcx.closure_kind(closure_substs) {
 455                     Some(closure_kind) => {
 456                         debug!(?closure_kind, "assemble_unboxed_candidates");
 457                         if closure_kind.extends(kind) {
 458                             candidates.vec.push(ClosureCandidate);
 459                         }
 460                     }
 461                     None => {
 462                         debug!("assemble_unboxed_candidates: closure_kind not yet known");
 463                         candidates.vec.push(ClosureCandidate);
 464                     }
 465                 }
 466             }
 467             ty::Infer(ty::TyVar(_)) => {
 468                 debug!("assemble_unboxed_closure_candidates: ambiguous self-type");
 469                 candidates.ambiguous = true;
 470             }
 471             _ => {}
 472         }
 473     }
 474
 475     /// Implements one of the `Fn()` family for a fn pointer.
 476     fn assemble_fn_pointer_candidates(
 477         &mut self,
 478         obligation: &TraitObligation<'tcx>,
 479         candidates: &mut SelectionCandidateSet<'tcx>,
 480     ) {
 481         // We provide impl of all fn traits for fn pointers.
 482         if self.tcx().fn_trait_kind_from_lang_item(obligation.predicate.def_id()).is_none() {
 483             return;
 484         }
 485
 486         // Okay to skip binder because what we are inspecting doesn't involve bound regions.
 487         let self_ty = obligation.self_ty().skip_binder();
 488         match *self_ty.kind() {
 489             ty::Infer(ty::TyVar(_)) => {
 490                 debug!("assemble_fn_pointer_candidates: ambiguous self-type");
 491                 candidates.ambiguous = true; // Could wind up being a fn() type.
 492             }
 493             // Provide an impl, but only for suitable `fn` pointers.
 494             ty::FnPtr(_) => {
 495                 if let ty::FnSig {
 496                     unsafety: hir::Unsafety::Normal,
 497                     abi: Abi::Rust,
 498                     c_variadic: false,
 499                     ..
 500                 } = self_ty.fn_sig(self.tcx()).skip_binder()
 501                 {
 502                     candidates.vec.push(FnPointerCandidate { is_const: false });
 503                 }
 504             }
 505             // Provide an impl for suitable functions, rejecting `#[target_feature]` functions (RFC 2396).
 506             ty::FnDef(def_id, _) => {
 507                 if let ty::FnSig {
 508                     unsafety: hir::Unsafety::Normal,
 509                     abi: Abi::Rust,
 510                     c_variadic: false,
 511                     ..
 512                 } = self_ty.fn_sig(self.tcx()).skip_binder()
 513                 {
 514                     if self.tcx().codegen_fn_attrs(def_id).target_features.is_empty() {
 515                         candidates
 516                             .vec
 517                             .push(FnPointerCandidate { is_const: self.tcx().is_const_fn(def_id) });
 518                     }
 519                 }
 520             }
 521             _ => {}
 522         }
 523     }
 524
 525     /// Searches for impls that might apply to `obligation`.
 526     fn assemble_candidates_from_impls(
 527         &mut self,
 528         obligation: &TraitObligation<'tcx>,
 529         candidates: &mut SelectionCandidateSet<'tcx>,
 530     ) {
 531         debug!(?obligation, "assemble_candidates_from_impls");
 532
 533         // Essentially any user-written impl will match with an error type,
 534         // so creating `ImplCandidates` isn't useful. However, we might
 535         // end up finding a candidate elsewhere (e.g. a `BuiltinCandidate` for `Sized)
 536         // This helps us avoid overflow: see issue #72839
 537         // Since compilation is already guaranteed to fail, this is just
 538         // to try to show the 'nicest' possible errors to the user.
 539         if obligation.references_error() {
 540             return;
 541         }
 542
 543         self.tcx().for_each_relevant_impl(
 544             obligation.predicate.def_id(),
 545             obligation.predicate.skip_binder().trait_ref.self_ty(),
 546             |impl_def_id| {
 547                 self.infcx.probe(|_| {
 548                     if let Ok(_substs) = self.match_impl(impl_def_id, obligation) {
 549                         candidates.vec.push(ImplCandidate(impl_def_id));
 550                     }
 551                 });
 552             },
 553         );
 554     }
 555
 556     fn assemble_candidates_from_auto_impls(
 557         &mut self,
 558         obligation: &TraitObligation<'tcx>,
 559         candidates: &mut SelectionCandidateSet<'tcx>,
 560     ) {
 561         // Okay to skip binder here because the tests we do below do not involve bound regions.
 562         let self_ty = obligation.self_ty().skip_binder();
 563         debug!(?self_ty, "assemble_candidates_from_auto_impls");
 564
 565         let def_id = obligation.predicate.def_id();
 566
 567         if self.tcx().trait_is_auto(def_id) {
 568             match self_ty.kind() {
 569                 ty::Dynamic(..) => {
 570                     // For object types, we don't know what the closed
 571                     // over types are. This means we conservatively
 572                     // say nothing; a candidate may be added by
 573                     // `assemble_candidates_from_object_ty`.
 574                 }
 575                 ty::Foreign(..) => {
 576                     // Since the contents of foreign types is unknown,
 577                     // we don't add any `..` impl. Default traits could
 578                     // still be provided by a manual implementation for
 579                     // this trait and type.
 580                 }
 581                 ty::Param(..) | ty::Projection(..) => {
 582                     // In these cases, we don't know what the actual
 583                     // type is.  Therefore, we cannot break it down
 584                     // into its constituent types. So we don't
 585                     // consider the `..` impl but instead just add no
 586                     // candidates: this means that typeck will only
 587                     // succeed if there is another reason to believe
 588                     // that this obligation holds. That could be a
 589                     // where-clause or, in the case of an object type,
 590                     // it could be that the object type lists the
 591                     // trait (e.g., `Foo+Send : Send`). See
 592                     // `ui/typeck/typeck-default-trait-impl-send-param.rs`
 593                     // for an example of a test case that exercises
 594                     // this path.
 595                 }
 596                 ty::Infer(ty::TyVar(_)) => {
 597                     // The auto impl might apply; we don't know.
 598                     candidates.ambiguous = true;
 599                 }
 600                 ty::Generator(_, _, movability)
 601                     if self.tcx().lang_items().unpin_trait() == Some(def_id) =>
 602                 {
 603                     match movability {
 604                         hir::Movability::Static => {
 605                             // Immovable generators are never `Unpin`, so
 606                             // suppress the normal auto-impl candidate for it.
 607                         }
 608                         hir::Movability::Movable => {
 609                             // Movable generators are always `Unpin`, so add an
 610                             // unconditional builtin candidate.
 611                             candidates.vec.push(BuiltinCandidate { has_nested: false });
 612                         }
 613                     }
 614                 }
 615
 616                 _ => candidates.vec.push(AutoImplCandidate(def_id)),
 617             }
 618         }
 619     }
 620
 621     /// Searches for impls that might apply to `obligation`.
 622     fn assemble_candidates_from_object_ty(
 623         &mut self,
 624         obligation: &TraitObligation<'tcx>,
 625         candidates: &mut SelectionCandidateSet<'tcx>,
 626     ) {
 627         debug!(
 628             self_ty = ?obligation.self_ty().skip_binder(),
 629             "assemble_candidates_from_object_ty",
 630         );
 631
 632         self.infcx.probe(|_snapshot| {
 633             // The code below doesn't care about regions, and the
 634             // self-ty here doesn't escape this probe, so just erase
 635             // any LBR.
 636             let self_ty = self.tcx().erase_late_bound_regions(obligation.self_ty());
 637             let poly_trait_ref = match self_ty.kind() {
 638                 ty::Dynamic(ref data, ..) => {
 639                     if data.auto_traits().any(|did| did == obligation.predicate.def_id()) {
 640                         debug!(
 641                             "assemble_candidates_from_object_ty: matched builtin bound, \
 642                              pushing candidate"
 643                         );
 644                         candidates.vec.push(BuiltinObjectCandidate);
 645                         return;
 646                     }
 647
 648                     if let Some(principal) = data.principal() {
 649                         if !self.infcx.tcx.features().object_safe_for_dispatch {
 650                             principal.with_self_ty(self.tcx(), self_ty)
 651                         } else if self.tcx().is_object_safe(principal.def_id()) {
 652                             principal.with_self_ty(self.tcx(), self_ty)
 653                         } else {
 654                             return;
 655                         }
 656                     } else {
 657                         // Only auto trait bounds exist.
 658                         return;
 659                     }
 660                 }
 661                 ty::Infer(ty::TyVar(_)) => {
 662                     debug!("assemble_candidates_from_object_ty: ambiguous");
 663                     candidates.ambiguous = true; // could wind up being an object type
 664                     return;
 665                 }
 666                 _ => return,
 667             };
 668
 669             debug!(?poly_trait_ref, "assemble_candidates_from_object_ty");
 670
 671             let poly_trait_predicate = self.infcx().resolve_vars_if_possible(obligation.predicate);
 672             let placeholder_trait_predicate =
 673                 self.infcx().replace_bound_vars_with_placeholders(poly_trait_predicate);
 674
 675             // Count only those upcast versions that match the trait-ref
 676             // we are looking for. Specifically, do not only check for the
 677             // correct trait, but also the correct type parameters.
 678             // For example, we may be trying to upcast `Foo` to `Bar<i32>`,
 679             // but `Foo` is declared as `trait Foo: Bar<u32>`.
 680             let candidate_supertraits = util::supertraits(self.tcx(), poly_trait_ref)
 681                 .enumerate()
 682                 .filter(|&(_, upcast_trait_ref)| {
 683                     self.infcx.probe(|_| {
 684                         self.match_normalize_trait_ref(
 685                             obligation,
 686                             upcast_trait_ref,
 687                             placeholder_trait_predicate.trait_ref,
 688                         )
 689                         .is_ok()
 690                     })
 691                 })
 692                 .map(|(idx, _)| ObjectCandidate(idx));
 693
 694             candidates.vec.extend(candidate_supertraits);
 695         })
 696     }
 697
 698     /// Temporary migration for #89190
 699     fn need_migrate_deref_output_trait_object(
 700         &mut self,
 701         ty: Ty<'tcx>,
 702         cause: &traits::ObligationCause<'tcx>,
 703         param_env: ty::ParamEnv<'tcx>,
 704     ) -> Option<(Ty<'tcx>, DefId)> {
 705         let tcx = self.tcx();
 706         if tcx.features().trait_upcasting {
 707             return None;
 708         }
 709
 710         // <ty as Deref>
 711         let trait_ref = ty::TraitRef {
 712             def_id: tcx.lang_items().deref_trait()?,
 713             substs: tcx.mk_substs_trait(ty, &[]),
 714         };
 715
 716         let obligation = traits::Obligation::new(
 717             cause.clone(),
 718             param_env,
 719             ty::Binder::dummy(trait_ref).without_const().to_predicate(tcx),
 720         );
 721         if !self.infcx.predicate_may_hold(&obligation) {
 722             return None;
 723         }
 724
 725         let mut fulfillcx = traits::FulfillmentContext::new_in_snapshot();
 726         let normalized_ty = fulfillcx.normalize_projection_type(
 727             &self.infcx,
 728             param_env,
 729             ty::ProjectionTy {
 730                 item_def_id: tcx.lang_items().deref_target()?,
 731                 substs: trait_ref.substs,
 732             },
 733             cause.clone(),
 734         );
 735
 736         let ty::Dynamic(data, ..) = normalized_ty.kind() else {
 737             return None;
 738         };
 739
 740         let def_id = data.principal_def_id()?;
 741
 742         return Some((normalized_ty, def_id));
 743     }
 744
 745     /// Searches for unsizing that might apply to `obligation`.
 746     fn assemble_candidates_for_unsizing(
 747         &mut self,
 748         obligation: &TraitObligation<'tcx>,
 749         candidates: &mut SelectionCandidateSet<'tcx>,
 750     ) {
 751         // We currently never consider higher-ranked obligations e.g.
 752         // `for<'a> &'a T: Unsize<Trait+'a>` to be implemented. This is not
 753         // because they are a priori invalid, and we could potentially add support
 754         // for them later, it's just that there isn't really a strong need for it.
 755         // A `T: Unsize<U>` obligation is always used as part of a `T: CoerceUnsize<U>`
 756         // impl, and those are generally applied to concrete types.
 757         //
 758         // That said, one might try to write a fn with a where clause like
 759         //     for<'a> Foo<'a, T>: Unsize<Foo<'a, Trait>>
 760         // where the `'a` is kind of orthogonal to the relevant part of the `Unsize`.
 761         // Still, you'd be more likely to write that where clause as
 762         //     T: Trait
 763         // so it seems ok if we (conservatively) fail to accept that `Unsize`
 764         // obligation above. Should be possible to extend this in the future.
 765         let source = match obligation.self_ty().no_bound_vars() {
 766             Some(t) => t,
 767             None => {
 768                 // Don't add any candidates if there are bound regions.
 769                 return;
 770             }
 771         };
 772         let target = obligation.predicate.skip_binder().trait_ref.substs.type_at(1);
 773
 774         debug!(?source, ?target, "assemble_candidates_for_unsizing");
 775
 776         match (source.kind(), target.kind()) {
 777             // Trait+Kx+'a -> Trait+Ky+'b (upcasts).
 778             (&ty::Dynamic(ref data_a, ..), &ty::Dynamic(ref data_b, ..)) => {
 779                 // Upcast coercions permit several things:
 780                 //
 781                 // 1. Dropping auto traits, e.g., `Foo + Send` to `Foo`
 782                 // 2. Tightening the region bound, e.g., `Foo + 'a` to `Foo + 'b` if `'a: 'b`
 783                 // 3. Tightening trait to its super traits, eg. `Foo` to `Bar` if `Foo: Bar`
 784                 //
 785                 // Note that neither of the first two of these changes requires any
 786                 // change at runtime. The third needs to change pointer metadata at runtime.
 787                 //
 788                 // We always perform upcasting coercions when we can because of reason
 789                 // #2 (region bounds).
 790                 let auto_traits_compatible = data_b
 791                     .auto_traits()
 792                     // All of a's auto traits need to be in b's auto traits.
 793                     .all(|b| data_a.auto_traits().any(|a| a == b));
 794                 if auto_traits_compatible {
 795                     let principal_def_id_a = data_a.principal_def_id();
 796                     let principal_def_id_b = data_b.principal_def_id();
 797                     if principal_def_id_a == principal_def_id_b {
 798                         // no cyclic
 799                         candidates.vec.push(BuiltinUnsizeCandidate);
 800                     } else if principal_def_id_a.is_some() && principal_def_id_b.is_some() {
 801                         // not casual unsizing, now check whether this is trait upcasting coercion.
 802                         let principal_a = data_a.principal().unwrap();
 803                         let target_trait_did = principal_def_id_b.unwrap();
 804                         let source_trait_ref = principal_a.with_self_ty(self.tcx(), source);
 805                         if let Some((deref_output_ty, deref_output_trait_did)) = self
 806                             .need_migrate_deref_output_trait_object(
 807                                 source,
 808                                 &obligation.cause,
 809                                 obligation.param_env,
 810                             )
 811                         {
 812                             if deref_output_trait_did == target_trait_did {
 813                                 self.tcx().struct_span_lint_hir(
 814                                     DEREF_INTO_DYN_SUPERTRAIT,
 815                                     obligation.cause.body_id,
 816                                     obligation.cause.span,
 817                                     |lint| {
 818                                         lint.build(&format!(
 819                                             "`{}` implements `Deref` with supertrait `{}` as output",
 820                                             source,
 821                                             deref_output_ty
 822                                         )).emit();
 823                                     },
 824                                 );
 825                                 return;
 826                             }
 827                         }
 828
 829                         for (idx, upcast_trait_ref) in
 830                             util::supertraits(self.tcx(), source_trait_ref).enumerate()
 831                         {
 832                             if upcast_trait_ref.def_id() == target_trait_did {
 833                                 candidates.vec.push(TraitUpcastingUnsizeCandidate(idx));
 834                             }
 835                         }
 836                     }
 837                 }
 838             }
 839
 840             // `T` -> `Trait`
 841             (_, &ty::Dynamic(..)) => {
 842                 candidates.vec.push(BuiltinUnsizeCandidate);
 843             }
 844
 845             // Ambiguous handling is below `T` -> `Trait`, because inference
 846             // variables can still implement `Unsize<Trait>` and nested
 847             // obligations will have the final say (likely deferred).
 848             (&ty::Infer(ty::TyVar(_)), _) | (_, &ty::Infer(ty::TyVar(_))) => {
 849                 debug!("assemble_candidates_for_unsizing: ambiguous");
 850                 candidates.ambiguous = true;
 851             }
 852
 853             // `[T; n]` -> `[T]`
 854             (&ty::Array(..), &ty::Slice(_)) => {
 855                 candidates.vec.push(BuiltinUnsizeCandidate);
 856             }
 857
 858             // `Struct<T>` -> `Struct<U>`
 859             (&ty::Adt(def_id_a, _), &ty::Adt(def_id_b, _)) if def_id_a.is_struct() => {
 860                 if def_id_a == def_id_b {
 861                     candidates.vec.push(BuiltinUnsizeCandidate);
 862                 }
 863             }
 864
 865             // `(.., T)` -> `(.., U)`
 866             (&ty::Tuple(tys_a), &ty::Tuple(tys_b)) => {
 867                 if tys_a.len() == tys_b.len() {
 868                     candidates.vec.push(BuiltinUnsizeCandidate);
 869                 }
 870             }
 871
 872             _ => {}
 873         };
 874     }
 875
 876     fn assemble_candidates_for_trait_alias(
 877         &mut self,
 878         obligation: &TraitObligation<'tcx>,
 879         candidates: &mut SelectionCandidateSet<'tcx>,
 880     ) {
 881         // Okay to skip binder here because the tests we do below do not involve bound regions.
 882         let self_ty = obligation.self_ty().skip_binder();
 883         debug!(?self_ty, "assemble_candidates_for_trait_alias");
 884
 885         let def_id = obligation.predicate.def_id();
 886
 887         if self.tcx().is_trait_alias(def_id) {
 888             candidates.vec.push(TraitAliasCandidate(def_id));
 889         }
 890     }
 891
 892     /// Assembles the trait which are built-in to the language itself:
 893     /// `Copy`, `Clone` and `Sized`.
 894     fn assemble_builtin_bound_candidates(
 895         &mut self,
 896         conditions: BuiltinImplConditions<'tcx>,
 897         candidates: &mut SelectionCandidateSet<'tcx>,
 898     ) {
 899         match conditions {
 900             BuiltinImplConditions::Where(nested) => {
 901                 debug!(?nested, "builtin_bound");
 902                 candidates
 903                     .vec
 904                     .push(BuiltinCandidate { has_nested: !nested.skip_binder().is_empty() });
 905             }
 906             BuiltinImplConditions::None => {}
 907             BuiltinImplConditions::Ambiguous => {
 908                 debug!("assemble_builtin_bound_candidates: ambiguous builtin");
 909                 candidates.ambiguous = true;
 910             }
 911         }
 912     }
 913
 914     fn assemble_const_drop_candidates(
 915         &mut self,
 916         obligation: &TraitObligation<'tcx>,
 917         candidates: &mut SelectionCandidateSet<'tcx>,
 918     ) -> Result<(), SelectionError<'tcx>> {
 919         let mut stack: Vec<(Ty<'tcx>, usize)> = vec![(obligation.self_ty().skip_binder(), 0)];
 920
 921         while let Some((ty, depth)) = stack.pop() {
 922             let mut noreturn = false;
 923
 924             self.check_recursion_depth(depth, obligation)?;
 925             let mut copy_candidates = SelectionCandidateSet { vec: Vec::new(), ambiguous: false };
 926             let mut copy_obligation =
 927                 obligation.with(obligation.predicate.rebind(ty::TraitPredicate {
 928                     trait_ref: ty::TraitRef {
 929                         def_id: self.tcx().require_lang_item(hir::LangItem::Copy, None),
 930                         substs: self.tcx().mk_substs_trait(ty, &[]),
 931                     },
 932                     constness: ty::BoundConstness::NotConst,
 933                     polarity: ty::ImplPolarity::Positive,
 934                 }));
 935             copy_obligation.recursion_depth = depth + 1;
 936             self.assemble_candidates_from_impls(&copy_obligation, &mut copy_candidates);
 937             let copy_conditions = self.copy_clone_conditions(&copy_obligation);
 938             self.assemble_builtin_bound_candidates(copy_conditions, &mut copy_candidates);
 939             if !copy_candidates.vec.is_empty() {
 940                 noreturn = true;
 941             }
 942             debug!(?copy_candidates.vec, "assemble_const_drop_candidates - copy");
 943
 944             match ty.kind() {
 945                 ty::Int(_)
 946                 | ty::Uint(_)
 947                 | ty::Float(_)
 948                 | ty::Infer(ty::IntVar(_))
 949                 | ty::Infer(ty::FloatVar(_))
 950                 | ty::FnPtr(_)
 951                 | ty::Never
 952                 | ty::Ref(..)
 953                 | ty::FnDef(..)
 954                 | ty::RawPtr(_)
 955                 | ty::Bool
 956                 | ty::Char
 957                 | ty::Str
 958                 | ty::Foreign(_) => {} // Do nothing. These types satisfy `const Drop`.
 959
 960                 ty::Adt(def, subst) => {
 961                     let mut set = SelectionCandidateSet { vec: Vec::new(), ambiguous: false };
 962                     self.assemble_candidates_from_impls(
 963                         &obligation.with(obligation.predicate.map_bound(|mut pred| {
 964                             pred.trait_ref.substs = self.tcx().mk_substs_trait(ty, &[]);
 965                             pred
 966                         })),
 967                         &mut set,
 968                     );
 969                     stack.extend(def.all_fields().map(|f| (f.ty(self.tcx(), subst), depth + 1)));
 970
 971                     debug!(?set.vec, "assemble_const_drop_candidates - ty::Adt");
 972                     if set.vec.into_iter().any(|candidate| {
 973                         if let SelectionCandidate::ImplCandidate(did) = candidate {
 974                             matches!(self.tcx().impl_constness(did), hir::Constness::NotConst)
 975                         } else {
 976                             false
 977                         }
 978                     }) {
 979                         if !noreturn {
 980                             // has non-const Drop
 981                             return Ok(());
 982                         }
 983                         debug!("not returning");
 984                     }
 985                 }
 986
 987                 ty::Array(ty, _) => stack.push((ty, depth + 1)),
 988
 989                 ty::Tuple(_) => stack.extend(ty.tuple_fields().map(|t| (t, depth + 1))),
 990
 991                 ty::Closure(_, substs) => {
 992                     let substs = substs.as_closure();
 993                     let ty = self.infcx.shallow_resolve(substs.tupled_upvars_ty());
 994                     stack.push((ty, depth + 1));
 995                 }
 996
 997                 ty::Generator(_, substs, _) => {
 998                     let substs = substs.as_generator();
 999                     let ty = self.infcx.shallow_resolve(substs.tupled_upvars_ty());
1000
1001                     stack.push((ty, depth + 1));
1002                     stack.push((substs.witness(), depth + 1));
1003                 }
1004
1005                 ty::GeneratorWitness(tys) => stack.extend(
1006                     self.tcx().erase_late_bound_regions(*tys).iter().map(|t| (t, depth + 1)),
1007                 ),
1008
1009                 ty::Slice(ty) => stack.push((ty, depth + 1)),
1010
1011                 ty::Opaque(..)
1012                 | ty::Dynamic(..)
1013                 | ty::Error(_)
1014                 | ty::Bound(..)
1015                 | ty::Infer(_)
1016                 | ty::Placeholder(_)
1017                 | ty::Projection(..)
1018                 | ty::Param(..) => {
1019                     if !noreturn {
1020                         return Ok(());
1021                     }
1022                     debug!("not returning");
1023                 }
1024             }
1025             debug!(?stack, "assemble_const_drop_candidates - in loop");
1026         }
1027         // all types have passed.
1028         candidates.vec.push(ConstDropCandidate);
1029
1030         Ok(())
1031     }
1032 }