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 hir::LangItem;
   9 use rustc_hir as hir;
  10 use rustc_infer::traits::ObligationCause;
  11 use rustc_infer::traits::{Obligation, SelectionError, TraitObligation};
  12 use rustc_middle::ty::{self, Ty, TypeVisitable};
  13 use rustc_target::spec::abi::Abi;
  14
  15 use crate::traits;
  16 use crate::traits::query::evaluate_obligation::InferCtxtExt;
  17 use crate::traits::util;
  18
  19 use super::BuiltinImplConditions;
  20 use super::SelectionCandidate::*;
  21 use super::{SelectionCandidateSet, SelectionContext, TraitObligationStack};
  22
  23 impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
  24     #[instrument(skip(self, stack), level = "debug")]
  25     pub(super) fn assemble_candidates<'o>(
  26         &mut self,
  27         stack: &TraitObligationStack<'o, 'tcx>,
  28     ) -> Result<SelectionCandidateSet<'tcx>, SelectionError<'tcx>> {
  29         let TraitObligationStack { obligation, .. } = *stack;
  30         let obligation = &Obligation {
  31             param_env: obligation.param_env,
  32             cause: obligation.cause.clone(),
  33             recursion_depth: obligation.recursion_depth,
  34             predicate: self.infcx.resolve_vars_if_possible(obligation.predicate),
  35         };
  36
  37         if obligation.predicate.skip_binder().self_ty().is_ty_var() {
  38             debug!(ty = ?obligation.predicate.skip_binder().self_ty(), "ambiguous inference var or opaque type");
  39             // Self is a type variable (e.g., `_: AsRef<str>`).
  40             //
  41             // This is somewhat problematic, as the current scheme can't really
  42             // handle it turning to be a projection. This does end up as truly
  43             // ambiguous in most cases anyway.
  44             //
  45             // Take the fast path out - this also improves
  46             // performance by preventing assemble_candidates_from_impls from
  47             // matching every impl for this trait.
  48             return Ok(SelectionCandidateSet { vec: vec![], ambiguous: true });
  49         }
  50
  51         let mut candidates = SelectionCandidateSet { vec: Vec::new(), ambiguous: false };
  52
  53         // The only way to prove a NotImplemented(T: Foo) predicate is via a negative impl.
  54         // There are no compiler built-in rules for this.
  55         if obligation.polarity() == ty::ImplPolarity::Negative {
  56             self.assemble_candidates_for_trait_alias(obligation, &mut candidates);
  57             self.assemble_candidates_from_impls(obligation, &mut candidates);
  58         } else {
  59             self.assemble_candidates_for_trait_alias(obligation, &mut candidates);
  60
  61             // Other bounds. Consider both in-scope bounds from fn decl
  62             // and applicable impls. There is a certain set of precedence rules here.
  63             let def_id = obligation.predicate.def_id();
  64             let lang_items = self.tcx().lang_items();
  65
  66             if lang_items.copy_trait() == Some(def_id) {
  67                 debug!(obligation_self_ty = ?obligation.predicate.skip_binder().self_ty());
  68
  69                 // User-defined copy impls are permitted, but only for
  70                 // structs and enums.
  71                 self.assemble_candidates_from_impls(obligation, &mut candidates);
  72
  73                 // For other types, we'll use the builtin rules.
  74                 let copy_conditions = self.copy_clone_conditions(obligation);
  75                 self.assemble_builtin_bound_candidates(copy_conditions, &mut candidates);
  76             } else if lang_items.discriminant_kind_trait() == Some(def_id) {
  77                 // `DiscriminantKind` is automatically implemented for every type.
  78                 candidates.vec.push(BuiltinCandidate { has_nested: false });
  79             } else if lang_items.pointee_trait() == Some(def_id) {
  80                 // `Pointee` is automatically implemented for every type.
  81                 candidates.vec.push(BuiltinCandidate { has_nested: false });
  82             } else if lang_items.sized_trait() == Some(def_id) {
  83                 // Sized is never implementable by end-users, it is
  84                 // always automatically computed.
  85                 let sized_conditions = self.sized_conditions(obligation);
  86                 self.assemble_builtin_bound_candidates(sized_conditions, &mut candidates);
  87             } else if lang_items.unsize_trait() == Some(def_id) {
  88                 self.assemble_candidates_for_unsizing(obligation, &mut candidates);
  89             } else if lang_items.destruct_trait() == Some(def_id) {
  90                 self.assemble_const_destruct_candidates(obligation, &mut candidates);
  91             } else if lang_items.transmute_trait() == Some(def_id) {
  92                 // User-defined transmutability impls are permitted.
  93                 self.assemble_candidates_from_impls(obligation, &mut candidates);
  94                 self.assemble_candidates_for_transmutability(obligation, &mut candidates);
  95             } else if lang_items.tuple_trait() == Some(def_id) {
  96                 self.assemble_candidate_for_tuple(obligation, &mut candidates);
  97             } else if lang_items.pointer_sized() == Some(def_id) {
  98                 self.assemble_candidate_for_ptr_sized(obligation, &mut candidates);
  99             } else {
 100                 if lang_items.clone_trait() == Some(def_id) {
 101                     // Same builtin conditions as `Copy`, i.e., every type which has builtin support
 102                     // for `Copy` also has builtin support for `Clone`, and tuples/arrays of `Clone`
 103                     // types have builtin support for `Clone`.
 104                     let clone_conditions = self.copy_clone_conditions(obligation);
 105                     self.assemble_builtin_bound_candidates(clone_conditions, &mut candidates);
 106                 }
 107
 108                 if lang_items.gen_trait() == Some(def_id) {
 109                     self.assemble_generator_candidates(obligation, &mut candidates);
 110                 } else if lang_items.future_trait() == Some(def_id) {
 111                     self.assemble_future_candidates(obligation, &mut candidates);
 112                 }
 113
 114                 self.assemble_closure_candidates(obligation, &mut candidates);
 115                 self.assemble_fn_pointer_candidates(obligation, &mut candidates);
 116                 self.assemble_candidates_from_impls(obligation, &mut candidates);
 117                 self.assemble_candidates_from_object_ty(obligation, &mut candidates);
 118             }
 119
 120             self.assemble_candidates_from_projected_tys(obligation, &mut candidates);
 121             self.assemble_candidates_from_caller_bounds(stack, &mut candidates)?;
 122             // Auto implementations have lower priority, so we only
 123             // consider triggering a default if there is no other impl that can apply.
 124             if candidates.vec.is_empty() {
 125                 self.assemble_candidates_from_auto_impls(obligation, &mut candidates);
 126             }
 127         }
 128         debug!("candidate list size: {}", candidates.vec.len());
 129         Ok(candidates)
 130     }
 131
 132     #[instrument(level = "debug", skip(self, candidates))]
 133     fn assemble_candidates_from_projected_tys(
 134         &mut self,
 135         obligation: &TraitObligation<'tcx>,
 136         candidates: &mut SelectionCandidateSet<'tcx>,
 137     ) {
 138         // Before we go into the whole placeholder thing, just
 139         // quickly check if the self-type is a projection at all.
 140         match obligation.predicate.skip_binder().trait_ref.self_ty().kind() {
 141             ty::Alias(..) => {}
 142             ty::Infer(ty::TyVar(_)) => {
 143                 span_bug!(
 144                     obligation.cause.span,
 145                     "Self=_ should have been handled by assemble_candidates"
 146                 );
 147             }
 148             _ => return,
 149         }
 150
 151         let result = self
 152             .infcx
 153             .probe(|_| self.match_projection_obligation_against_definition_bounds(obligation));
 154
 155         candidates
 156             .vec
 157             .extend(result.into_iter().map(|(idx, constness)| ProjectionCandidate(idx, constness)));
 158     }
 159
 160     /// Given an obligation like `<SomeTrait for T>`, searches the obligations that the caller
 161     /// supplied to find out whether it is listed among them.
 162     ///
 163     /// Never affects the inference environment.
 164     #[instrument(level = "debug", skip(self, stack, candidates))]
 165     fn assemble_candidates_from_caller_bounds<'o>(
 166         &mut self,
 167         stack: &TraitObligationStack<'o, 'tcx>,
 168         candidates: &mut SelectionCandidateSet<'tcx>,
 169     ) -> Result<(), SelectionError<'tcx>> {
 170         debug!(?stack.obligation);
 171
 172         let all_bounds = stack
 173             .obligation
 174             .param_env
 175             .caller_bounds()
 176             .iter()
 177             .filter(|p| !p.references_error())
 178             .filter_map(|p| p.to_opt_poly_trait_pred());
 179
 180         // Micro-optimization: filter out predicates relating to different traits.
 181         let matching_bounds =
 182             all_bounds.filter(|p| p.def_id() == stack.obligation.predicate.def_id());
 183
 184         // Keep only those bounds which may apply, and propagate overflow if it occurs.
 185         for bound in matching_bounds {
 186             // FIXME(oli-obk): it is suspicious that we are dropping the constness and
 187             // polarity here.
 188             let wc = self.where_clause_may_apply(stack, bound.map_bound(|t| t.trait_ref))?;
 189             if wc.may_apply() {
 190                 candidates.vec.push(ParamCandidate(bound));
 191             }
 192         }
 193
 194         Ok(())
 195     }
 196
 197     fn assemble_generator_candidates(
 198         &mut self,
 199         obligation: &TraitObligation<'tcx>,
 200         candidates: &mut SelectionCandidateSet<'tcx>,
 201     ) {
 202         // Okay to skip binder because the substs on generator types never
 203         // touch bound regions, they just capture the in-scope
 204         // type/region parameters.
 205         let self_ty = obligation.self_ty().skip_binder();
 206         match self_ty.kind() {
 207             // async constructs get lowered to a special kind of generator that
 208             // should *not* `impl Generator`.
 209             ty::Generator(did, ..) if !self.tcx().generator_is_async(*did) => {
 210                 debug!(?self_ty, ?obligation, "assemble_generator_candidates",);
 211
 212                 candidates.vec.push(GeneratorCandidate);
 213             }
 214             ty::Infer(ty::TyVar(_)) => {
 215                 debug!("assemble_generator_candidates: ambiguous self-type");
 216                 candidates.ambiguous = true;
 217             }
 218             _ => {}
 219         }
 220     }
 221
 222     fn assemble_future_candidates(
 223         &mut self,
 224         obligation: &TraitObligation<'tcx>,
 225         candidates: &mut SelectionCandidateSet<'tcx>,
 226     ) {
 227         let self_ty = obligation.self_ty().skip_binder();
 228         if let ty::Generator(did, ..) = self_ty.kind() {
 229             // async constructs get lowered to a special kind of generator that
 230             // should directly `impl Future`.
 231             if self.tcx().generator_is_async(*did) {
 232                 debug!(?self_ty, ?obligation, "assemble_future_candidates",);
 233
 234                 candidates.vec.push(FutureCandidate);
 235             }
 236         }
 237     }
 238
 239     /// Checks for the artificial impl that the compiler will create for an obligation like `X :
 240     /// FnMut<..>` where `X` is a closure type.
 241     ///
 242     /// Note: the type parameters on a closure candidate are modeled as *output* type
 243     /// parameters and hence do not affect whether this trait is a match or not. They will be
 244     /// unified during the confirmation step.
 245     fn assemble_closure_candidates(
 246         &mut self,
 247         obligation: &TraitObligation<'tcx>,
 248         candidates: &mut SelectionCandidateSet<'tcx>,
 249     ) {
 250         let Some(kind) = self.tcx().fn_trait_kind_from_def_id(obligation.predicate.def_id()) else {
 251             return;
 252         };
 253
 254         // Okay to skip binder because the substs on closure types never
 255         // touch bound regions, they just capture the in-scope
 256         // type/region parameters
 257         match *obligation.self_ty().skip_binder().kind() {
 258             ty::Closure(def_id, closure_substs) => {
 259                 let is_const = self.tcx().is_const_fn_raw(def_id);
 260                 debug!(?kind, ?obligation, "assemble_unboxed_candidates");
 261                 match self.infcx.closure_kind(closure_substs) {
 262                     Some(closure_kind) => {
 263                         debug!(?closure_kind, "assemble_unboxed_candidates");
 264                         if closure_kind.extends(kind) {
 265                             candidates.vec.push(ClosureCandidate { is_const });
 266                         }
 267                     }
 268                     None => {
 269                         debug!("assemble_unboxed_candidates: closure_kind not yet known");
 270                         candidates.vec.push(ClosureCandidate { is_const });
 271                     }
 272                 }
 273             }
 274             ty::Infer(ty::TyVar(_)) => {
 275                 debug!("assemble_unboxed_closure_candidates: ambiguous self-type");
 276                 candidates.ambiguous = true;
 277             }
 278             _ => {}
 279         }
 280     }
 281
 282     /// Implements one of the `Fn()` family for a fn pointer.
 283     fn assemble_fn_pointer_candidates(
 284         &mut self,
 285         obligation: &TraitObligation<'tcx>,
 286         candidates: &mut SelectionCandidateSet<'tcx>,
 287     ) {
 288         // We provide impl of all fn traits for fn pointers.
 289         if !self.tcx().is_fn_trait(obligation.predicate.def_id()) {
 290             return;
 291         }
 292
 293         // Okay to skip binder because what we are inspecting doesn't involve bound regions.
 294         let self_ty = obligation.self_ty().skip_binder();
 295         match *self_ty.kind() {
 296             ty::Infer(ty::TyVar(_)) => {
 297                 debug!("assemble_fn_pointer_candidates: ambiguous self-type");
 298                 candidates.ambiguous = true; // Could wind up being a fn() type.
 299             }
 300             // Provide an impl, but only for suitable `fn` pointers.
 301             ty::FnPtr(_) => {
 302                 if let ty::FnSig {
 303                     unsafety: hir::Unsafety::Normal,
 304                     abi: Abi::Rust,
 305                     c_variadic: false,
 306                     ..
 307                 } = self_ty.fn_sig(self.tcx()).skip_binder()
 308                 {
 309                     candidates.vec.push(FnPointerCandidate { is_const: false });
 310                 }
 311             }
 312             // Provide an impl for suitable functions, rejecting `#[target_feature]` functions (RFC 2396).
 313             ty::FnDef(def_id, _) => {
 314                 if let ty::FnSig {
 315                     unsafety: hir::Unsafety::Normal,
 316                     abi: Abi::Rust,
 317                     c_variadic: false,
 318                     ..
 319                 } = self_ty.fn_sig(self.tcx()).skip_binder()
 320                 {
 321                     if self.tcx().codegen_fn_attrs(def_id).target_features.is_empty() {
 322                         candidates
 323                             .vec
 324                             .push(FnPointerCandidate { is_const: self.tcx().is_const_fn(def_id) });
 325                     }
 326                 }
 327             }
 328             _ => {}
 329         }
 330     }
 331
 332     /// Searches for impls that might apply to `obligation`.
 333     fn assemble_candidates_from_impls(
 334         &mut self,
 335         obligation: &TraitObligation<'tcx>,
 336         candidates: &mut SelectionCandidateSet<'tcx>,
 337     ) {
 338         debug!(?obligation, "assemble_candidates_from_impls");
 339
 340         // Essentially any user-written impl will match with an error type,
 341         // so creating `ImplCandidates` isn't useful. However, we might
 342         // end up finding a candidate elsewhere (e.g. a `BuiltinCandidate` for `Sized)
 343         // This helps us avoid overflow: see issue #72839
 344         // Since compilation is already guaranteed to fail, this is just
 345         // to try to show the 'nicest' possible errors to the user.
 346         // We don't check for errors in the `ParamEnv` - in practice,
 347         // it seems to cause us to be overly aggressive in deciding
 348         // to give up searching for candidates, leading to spurious errors.
 349         if obligation.predicate.references_error() {
 350             return;
 351         }
 352
 353         self.tcx().for_each_relevant_impl(
 354             obligation.predicate.def_id(),
 355             obligation.predicate.skip_binder().trait_ref.self_ty(),
 356             |impl_def_id| {
 357                 // Before we create the substitutions and everything, first
 358                 // consider a "quick reject". This avoids creating more types
 359                 // and so forth that we need to.
 360                 let impl_trait_ref = self.tcx().impl_trait_ref(impl_def_id).unwrap();
 361                 if self.fast_reject_trait_refs(obligation, &impl_trait_ref.0) {
 362                     return;
 363                 }
 364
 365                 self.infcx.probe(|_| {
 366                     if let Ok(_substs) = self.match_impl(impl_def_id, impl_trait_ref, obligation) {
 367                         candidates.vec.push(ImplCandidate(impl_def_id));
 368                     }
 369                 });
 370             },
 371         );
 372     }
 373
 374     fn assemble_candidates_from_auto_impls(
 375         &mut self,
 376         obligation: &TraitObligation<'tcx>,
 377         candidates: &mut SelectionCandidateSet<'tcx>,
 378     ) {
 379         // Okay to skip binder here because the tests we do below do not involve bound regions.
 380         let self_ty = obligation.self_ty().skip_binder();
 381         debug!(?self_ty, "assemble_candidates_from_auto_impls");
 382
 383         let def_id = obligation.predicate.def_id();
 384
 385         if self.tcx().trait_is_auto(def_id) {
 386             match self_ty.kind() {
 387                 ty::Dynamic(..) => {
 388                     // For object types, we don't know what the closed
 389                     // over types are. This means we conservatively
 390                     // say nothing; a candidate may be added by
 391                     // `assemble_candidates_from_object_ty`.
 392                 }
 393                 ty::Foreign(..) => {
 394                     // Since the contents of foreign types is unknown,
 395                     // we don't add any `..` impl. Default traits could
 396                     // still be provided by a manual implementation for
 397                     // this trait and type.
 398                 }
 399                 ty::Param(..) | ty::Alias(ty::Projection, ..) => {
 400                     // In these cases, we don't know what the actual
 401                     // type is. Therefore, we cannot break it down
 402                     // into its constituent types. So we don't
 403                     // consider the `..` impl but instead just add no
 404                     // candidates: this means that typeck will only
 405                     // succeed if there is another reason to believe
 406                     // that this obligation holds. That could be a
 407                     // where-clause or, in the case of an object type,
 408                     // it could be that the object type lists the
 409                     // trait (e.g., `Foo+Send : Send`). See
 410                     // `ui/typeck/typeck-default-trait-impl-send-param.rs`
 411                     // for an example of a test case that exercises
 412                     // this path.
 413                 }
 414                 ty::Infer(ty::TyVar(_)) => {
 415                     // The auto impl might apply; we don't know.
 416                     candidates.ambiguous = true;
 417                 }
 418                 ty::Generator(_, _, movability)
 419                     if self.tcx().lang_items().unpin_trait() == Some(def_id) =>
 420                 {
 421                     match movability {
 422                         hir::Movability::Static => {
 423                             // Immovable generators are never `Unpin`, so
 424                             // suppress the normal auto-impl candidate for it.
 425                         }
 426                         hir::Movability::Movable => {
 427                             // Movable generators are always `Unpin`, so add an
 428                             // unconditional builtin candidate.
 429                             candidates.vec.push(BuiltinCandidate { has_nested: false });
 430                         }
 431                     }
 432                 }
 433
 434                 _ => candidates.vec.push(AutoImplCandidate),
 435             }
 436         }
 437     }
 438
 439     /// Searches for impls that might apply to `obligation`.
 440     fn assemble_candidates_from_object_ty(
 441         &mut self,
 442         obligation: &TraitObligation<'tcx>,
 443         candidates: &mut SelectionCandidateSet<'tcx>,
 444     ) {
 445         debug!(
 446             self_ty = ?obligation.self_ty().skip_binder(),
 447             "assemble_candidates_from_object_ty",
 448         );
 449
 450         self.infcx.probe(|_snapshot| {
 451             // The code below doesn't care about regions, and the
 452             // self-ty here doesn't escape this probe, so just erase
 453             // any LBR.
 454             let self_ty = self.tcx().erase_late_bound_regions(obligation.self_ty());
 455             let poly_trait_ref = match self_ty.kind() {
 456                 ty::Dynamic(ref data, ..) => {
 457                     if data.auto_traits().any(|did| did == obligation.predicate.def_id()) {
 458                         debug!(
 459                             "assemble_candidates_from_object_ty: matched builtin bound, \
 460                              pushing candidate"
 461                         );
 462                         candidates.vec.push(BuiltinObjectCandidate);
 463                         return;
 464                     }
 465
 466                     if let Some(principal) = data.principal() {
 467                         if !self.infcx.tcx.features().object_safe_for_dispatch {
 468                             principal.with_self_ty(self.tcx(), self_ty)
 469                         } else if self.tcx().check_is_object_safe(principal.def_id()) {
 470                             principal.with_self_ty(self.tcx(), self_ty)
 471                         } else {
 472                             return;
 473                         }
 474                     } else {
 475                         // Only auto trait bounds exist.
 476                         return;
 477                     }
 478                 }
 479                 ty::Infer(ty::TyVar(_)) => {
 480                     debug!("assemble_candidates_from_object_ty: ambiguous");
 481                     candidates.ambiguous = true; // could wind up being an object type
 482                     return;
 483                 }
 484                 _ => return,
 485             };
 486
 487             debug!(?poly_trait_ref, "assemble_candidates_from_object_ty");
 488
 489             let poly_trait_predicate = self.infcx.resolve_vars_if_possible(obligation.predicate);
 490             let placeholder_trait_predicate =
 491                 self.infcx.instantiate_binder_with_placeholders(poly_trait_predicate);
 492
 493             // Count only those upcast versions that match the trait-ref
 494             // we are looking for. Specifically, do not only check for the
 495             // correct trait, but also the correct type parameters.
 496             // For example, we may be trying to upcast `Foo` to `Bar<i32>`,
 497             // but `Foo` is declared as `trait Foo: Bar<u32>`.
 498             let candidate_supertraits = util::supertraits(self.tcx(), poly_trait_ref)
 499                 .enumerate()
 500                 .filter(|&(_, upcast_trait_ref)| {
 501                     self.infcx.probe(|_| {
 502                         self.match_normalize_trait_ref(
 503                             obligation,
 504                             upcast_trait_ref,
 505                             placeholder_trait_predicate.trait_ref,
 506                         )
 507                         .is_ok()
 508                     })
 509                 })
 510                 .map(|(idx, _)| ObjectCandidate(idx));
 511
 512             candidates.vec.extend(candidate_supertraits);
 513         })
 514     }
 515
 516     /// Temporary migration for #89190
 517     fn need_migrate_deref_output_trait_object(
 518         &mut self,
 519         ty: Ty<'tcx>,
 520         param_env: ty::ParamEnv<'tcx>,
 521         cause: &ObligationCause<'tcx>,
 522     ) -> Option<ty::PolyExistentialTraitRef<'tcx>> {
 523         let tcx = self.tcx();
 524         if tcx.features().trait_upcasting {
 525             return None;
 526         }
 527
 528         // <ty as Deref>
 529         let trait_ref = tcx.mk_trait_ref(tcx.lang_items().deref_trait()?, [ty]);
 530
 531         let obligation =
 532             traits::Obligation::new(tcx, cause.clone(), param_env, ty::Binder::dummy(trait_ref));
 533         if !self.infcx.predicate_may_hold(&obligation) {
 534             return None;
 535         }
 536
 537         self.infcx.probe(|_| {
 538             let ty = traits::normalize_projection_type(
 539                 self,
 540                 param_env,
 541                 tcx.mk_alias_ty(tcx.lang_items().deref_target()?, trait_ref.substs),
 542                 cause.clone(),
 543                 0,
 544                 // We're *intentionally* throwing these away,
 545                 // since we don't actually use them.
 546                 &mut vec![],
 547             )
 548             .ty()
 549             .unwrap();
 550
 551             if let ty::Dynamic(data, ..) = ty.kind() { data.principal() } else { None }
 552         })
 553     }
 554
 555     /// Searches for unsizing that might apply to `obligation`.
 556     fn assemble_candidates_for_unsizing(
 557         &mut self,
 558         obligation: &TraitObligation<'tcx>,
 559         candidates: &mut SelectionCandidateSet<'tcx>,
 560     ) {
 561         // We currently never consider higher-ranked obligations e.g.
 562         // `for<'a> &'a T: Unsize<Trait+'a>` to be implemented. This is not
 563         // because they are a priori invalid, and we could potentially add support
 564         // for them later, it's just that there isn't really a strong need for it.
 565         // A `T: Unsize<U>` obligation is always used as part of a `T: CoerceUnsize<U>`
 566         // impl, and those are generally applied to concrete types.
 567         //
 568         // That said, one might try to write a fn with a where clause like
 569         //     for<'a> Foo<'a, T>: Unsize<Foo<'a, Trait>>
 570         // where the `'a` is kind of orthogonal to the relevant part of the `Unsize`.
 571         // Still, you'd be more likely to write that where clause as
 572         //     T: Trait
 573         // so it seems ok if we (conservatively) fail to accept that `Unsize`
 574         // obligation above. Should be possible to extend this in the future.
 575         let Some(source) = obligation.self_ty().no_bound_vars() else {
 576             // Don't add any candidates if there are bound regions.
 577             return;
 578         };
 579         let target = obligation.predicate.skip_binder().trait_ref.substs.type_at(1);
 580
 581         debug!(?source, ?target, "assemble_candidates_for_unsizing");
 582
 583         match (source.kind(), target.kind()) {
 584             // Trait+Kx+'a -> Trait+Ky+'b (upcasts).
 585             (&ty::Dynamic(ref data_a, _, ty::Dyn), &ty::Dynamic(ref data_b, _, ty::Dyn)) => {
 586                 // Upcast coercions permit several things:
 587                 //
 588                 // 1. Dropping auto traits, e.g., `Foo + Send` to `Foo`
 589                 // 2. Tightening the region bound, e.g., `Foo + 'a` to `Foo + 'b` if `'a: 'b`
 590                 // 3. Tightening trait to its super traits, eg. `Foo` to `Bar` if `Foo: Bar`
 591                 //
 592                 // Note that neither of the first two of these changes requires any
 593                 // change at runtime. The third needs to change pointer metadata at runtime.
 594                 //
 595                 // We always perform upcasting coercions when we can because of reason
 596                 // #2 (region bounds).
 597                 let auto_traits_compatible = data_b
 598                     .auto_traits()
 599                     // All of a's auto traits need to be in b's auto traits.
 600                     .all(|b| data_a.auto_traits().any(|a| a == b));
 601                 if auto_traits_compatible {
 602                     let principal_def_id_a = data_a.principal_def_id();
 603                     let principal_def_id_b = data_b.principal_def_id();
 604                     if principal_def_id_a == principal_def_id_b {
 605                         // no cyclic
 606                         candidates.vec.push(BuiltinUnsizeCandidate);
 607                     } else if principal_def_id_a.is_some() && principal_def_id_b.is_some() {
 608                         // not casual unsizing, now check whether this is trait upcasting coercion.
 609                         let principal_a = data_a.principal().unwrap();
 610                         let target_trait_did = principal_def_id_b.unwrap();
 611                         let source_trait_ref = principal_a.with_self_ty(self.tcx(), source);
 612                         if let Some(deref_trait_ref) = self.need_migrate_deref_output_trait_object(
 613                             source,
 614                             obligation.param_env,
 615                             &obligation.cause,
 616                         ) {
 617                             if deref_trait_ref.def_id() == target_trait_did {
 618                                 return;
 619                             }
 620                         }
 621
 622                         for (idx, upcast_trait_ref) in
 623                             util::supertraits(self.tcx(), source_trait_ref).enumerate()
 624                         {
 625                             if upcast_trait_ref.def_id() == target_trait_did {
 626                                 candidates.vec.push(TraitUpcastingUnsizeCandidate(idx));
 627                             }
 628                         }
 629                     }
 630                 }
 631             }
 632
 633             // `T` -> `Trait`
 634             (_, &ty::Dynamic(_, _, ty::Dyn)) => {
 635                 candidates.vec.push(BuiltinUnsizeCandidate);
 636             }
 637
 638             // Ambiguous handling is below `T` -> `Trait`, because inference
 639             // variables can still implement `Unsize<Trait>` and nested
 640             // obligations will have the final say (likely deferred).
 641             (&ty::Infer(ty::TyVar(_)), _) | (_, &ty::Infer(ty::TyVar(_))) => {
 642                 debug!("assemble_candidates_for_unsizing: ambiguous");
 643                 candidates.ambiguous = true;
 644             }
 645
 646             // `[T; n]` -> `[T]`
 647             (&ty::Array(..), &ty::Slice(_)) => {
 648                 candidates.vec.push(BuiltinUnsizeCandidate);
 649             }
 650
 651             // `Struct<T>` -> `Struct<U>`
 652             (&ty::Adt(def_id_a, _), &ty::Adt(def_id_b, _)) if def_id_a.is_struct() => {
 653                 if def_id_a == def_id_b {
 654                     candidates.vec.push(BuiltinUnsizeCandidate);
 655                 }
 656             }
 657
 658             // `(.., T)` -> `(.., U)`
 659             (&ty::Tuple(tys_a), &ty::Tuple(tys_b)) => {
 660                 if tys_a.len() == tys_b.len() {
 661                     candidates.vec.push(BuiltinUnsizeCandidate);
 662                 }
 663             }
 664
 665             _ => {}
 666         };
 667     }
 668
 669     #[instrument(level = "debug", skip(self, obligation, candidates))]
 670     fn assemble_candidates_for_transmutability(
 671         &mut self,
 672         obligation: &TraitObligation<'tcx>,
 673         candidates: &mut SelectionCandidateSet<'tcx>,
 674     ) {
 675         if obligation.has_non_region_param() {
 676             return;
 677         }
 678
 679         if obligation.has_non_region_infer() {
 680             candidates.ambiguous = true;
 681             return;
 682         }
 683
 684         candidates.vec.push(TransmutabilityCandidate);
 685     }
 686
 687     #[instrument(level = "debug", skip(self, obligation, candidates))]
 688     fn assemble_candidates_for_trait_alias(
 689         &mut self,
 690         obligation: &TraitObligation<'tcx>,
 691         candidates: &mut SelectionCandidateSet<'tcx>,
 692     ) {
 693         // Okay to skip binder here because the tests we do below do not involve bound regions.
 694         let self_ty = obligation.self_ty().skip_binder();
 695         debug!(?self_ty);
 696
 697         let def_id = obligation.predicate.def_id();
 698
 699         if self.tcx().is_trait_alias(def_id) {
 700             candidates.vec.push(TraitAliasCandidate);
 701         }
 702     }
 703
 704     /// Assembles the trait which are built-in to the language itself:
 705     /// `Copy`, `Clone` and `Sized`.
 706     #[instrument(level = "debug", skip(self, candidates))]
 707     fn assemble_builtin_bound_candidates(
 708         &mut self,
 709         conditions: BuiltinImplConditions<'tcx>,
 710         candidates: &mut SelectionCandidateSet<'tcx>,
 711     ) {
 712         match conditions {
 713             BuiltinImplConditions::Where(nested) => {
 714                 candidates
 715                     .vec
 716                     .push(BuiltinCandidate { has_nested: !nested.skip_binder().is_empty() });
 717             }
 718             BuiltinImplConditions::None => {}
 719             BuiltinImplConditions::Ambiguous => {
 720                 candidates.ambiguous = true;
 721             }
 722         }
 723     }
 724
 725     fn assemble_const_destruct_candidates(
 726         &mut self,
 727         obligation: &TraitObligation<'tcx>,
 728         candidates: &mut SelectionCandidateSet<'tcx>,
 729     ) {
 730         // If the predicate is `~const Destruct` in a non-const environment, we don't actually need
 731         // to check anything. We'll short-circuit checking any obligations in confirmation, too.
 732         if !obligation.is_const() {
 733             candidates.vec.push(ConstDestructCandidate(None));
 734             return;
 735         }
 736
 737         let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
 738         match self_ty.skip_binder().kind() {
 739             ty::Alias(..)
 740             | ty::Dynamic(..)
 741             | ty::Error(_)
 742             | ty::Bound(..)
 743             | ty::Param(_)
 744             | ty::Placeholder(_) => {
 745                 // We don't know if these are `~const Destruct`, at least
 746                 // not structurally... so don't push a candidate.
 747             }
 748
 749             ty::Bool
 750             | ty::Char
 751             | ty::Int(_)
 752             | ty::Uint(_)
 753             | ty::Float(_)
 754             | ty::Infer(ty::IntVar(_))
 755             | ty::Infer(ty::FloatVar(_))
 756             | ty::Str
 757             | ty::RawPtr(_)
 758             | ty::Ref(..)
 759             | ty::FnDef(..)
 760             | ty::FnPtr(_)
 761             | ty::Never
 762             | ty::Foreign(_)
 763             | ty::Array(..)
 764             | ty::Slice(_)
 765             | ty::Closure(..)
 766             | ty::Generator(..)
 767             | ty::Tuple(_)
 768             | ty::GeneratorWitness(_)
 769             | ty::GeneratorWitnessMIR(..) => {
 770                 // These are built-in, and cannot have a custom `impl const Destruct`.
 771                 candidates.vec.push(ConstDestructCandidate(None));
 772             }
 773
 774             ty::Adt(..) => {
 775                 // Find a custom `impl Drop` impl, if it exists
 776                 let relevant_impl = self.tcx().find_map_relevant_impl(
 777                     self.tcx().require_lang_item(LangItem::Drop, None),
 778                     obligation.predicate.skip_binder().trait_ref.self_ty(),
 779                     Some,
 780                 );
 781
 782                 if let Some(impl_def_id) = relevant_impl {
 783                     // Check that `impl Drop` is actually const, if there is a custom impl
 784                     if self.tcx().constness(impl_def_id) == hir::Constness::Const {
 785                         candidates.vec.push(ConstDestructCandidate(Some(impl_def_id)));
 786                     }
 787                 } else {
 788                     // Otherwise check the ADT like a built-in type (structurally)
 789                     candidates.vec.push(ConstDestructCandidate(None));
 790                 }
 791             }
 792
 793             ty::Infer(_) => {
 794                 candidates.ambiguous = true;
 795             }
 796         }
 797     }
 798
 799     fn assemble_candidate_for_tuple(
 800         &mut self,
 801         obligation: &TraitObligation<'tcx>,
 802         candidates: &mut SelectionCandidateSet<'tcx>,
 803     ) {
 804         let self_ty = self.infcx.shallow_resolve(obligation.self_ty().skip_binder());
 805         match self_ty.kind() {
 806             ty::Tuple(_) => {
 807                 candidates.vec.push(BuiltinCandidate { has_nested: false });
 808             }
 809             ty::Infer(ty::TyVar(_)) => {
 810                 candidates.ambiguous = true;
 811             }
 812             ty::Bool
 813             | ty::Char
 814             | ty::Int(_)
 815             | ty::Uint(_)
 816             | ty::Float(_)
 817             | ty::Adt(_, _)
 818             | ty::Foreign(_)
 819             | ty::Str
 820             | ty::Array(_, _)
 821             | ty::Slice(_)
 822             | ty::RawPtr(_)
 823             | ty::Ref(_, _, _)
 824             | ty::FnDef(_, _)
 825             | ty::FnPtr(_)
 826             | ty::Dynamic(_, _, _)
 827             | ty::Closure(_, _)
 828             | ty::Generator(_, _, _)
 829             | ty::GeneratorWitness(_)
 830             | ty::GeneratorWitnessMIR(..)
 831             | ty::Never
 832             | ty::Alias(..)
 833             | ty::Param(_)
 834             | ty::Bound(_, _)
 835             | ty::Error(_)
 836             | ty::Infer(_)
 837             | ty::Placeholder(_) => {}
 838         }
 839     }
 840
 841     fn assemble_candidate_for_ptr_sized(
 842         &mut self,
 843         obligation: &TraitObligation<'tcx>,
 844         candidates: &mut SelectionCandidateSet<'tcx>,
 845     ) {
 846         // The regions of a type don't affect the size of the type
 847         let self_ty = self
 848             .tcx()
 849             .erase_regions(self.tcx().erase_late_bound_regions(obligation.predicate.self_ty()));
 850
 851         // But if there are inference variables, we have to wait until it's resolved.
 852         if self_ty.has_non_region_infer() {
 853             candidates.ambiguous = true;
 854             return;
 855         }
 856
 857         let usize_layout =
 858             self.tcx().layout_of(ty::ParamEnv::empty().and(self.tcx().types.usize)).unwrap().layout;
 859         if let Ok(layout) = self.tcx().layout_of(obligation.param_env.and(self_ty))
 860             && layout.layout.size() == usize_layout.size()
 861             && layout.layout.align().abi == usize_layout.align().abi
 862         {
 863             candidates.vec.push(BuiltinCandidate { has_nested: false });
 864         }
 865     }
 866 }