compiler/rustc_middle/src/ty/instance.rs

   1 use crate::middle::codegen_fn_attrs::CodegenFnAttrFlags;
   2 use crate::ty::print::{FmtPrinter, Printer};
   3 use crate::ty::{self, Ty, TyCtxt, TypeFoldable, TypeSuperFoldable, TypeVisitable};
   4 use crate::ty::{EarlyBinder, InternalSubsts, SubstsRef};
   5 use rustc_errors::ErrorGuaranteed;
   6 use rustc_hir::def::Namespace;
   7 use rustc_hir::def_id::{CrateNum, DefId};
   8 use rustc_hir::lang_items::LangItem;
   9 use rustc_index::bit_set::FiniteBitSet;
  10 use rustc_macros::HashStable;
  11 use rustc_middle::ty::normalize_erasing_regions::NormalizationError;
  12 use rustc_span::Symbol;
  13
  14 use std::fmt;
  15
  16 /// A monomorphized `InstanceDef`.
  17 ///
  18 /// Monomorphization happens on-the-fly and no monomorphized MIR is ever created. Instead, this type
  19 /// simply couples a potentially generic `InstanceDef` with some substs, and codegen and const eval
  20 /// will do all required substitution as they run.
  21 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, TyEncodable, TyDecodable)]
  22 #[derive(HashStable, Lift, TypeFoldable, TypeVisitable)]
  23 pub struct Instance<'tcx> {
  24     pub def: InstanceDef<'tcx>,
  25     pub substs: SubstsRef<'tcx>,
  26 }
  27
  28 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
  29 #[derive(TyEncodable, TyDecodable, HashStable, TypeFoldable, TypeVisitable, Lift)]
  30 pub enum InstanceDef<'tcx> {
  31     /// A user-defined callable item.
  32     ///
  33     /// This includes:
  34     /// - `fn` items
  35     /// - closures
  36     /// - generators
  37     Item(ty::WithOptConstParam<DefId>),
  38
  39     /// An intrinsic `fn` item (with `"rust-intrinsic"` or `"platform-intrinsic"` ABI).
  40     ///
  41     /// Alongside `Virtual`, this is the only `InstanceDef` that does not have its own callable MIR.
  42     /// Instead, codegen and const eval "magically" evaluate calls to intrinsics purely in the
  43     /// caller.
  44     Intrinsic(DefId),
  45
  46     /// `<T as Trait>::method` where `method` receives unsizeable `self: Self` (part of the
  47     /// `unsized_locals` feature).
  48     ///
  49     /// The generated shim will take `Self` via `*mut Self` - conceptually this is `&owned Self` -
  50     /// and dereference the argument to call the original function.
  51     VTableShim(DefId),
  52
  53     /// `fn()` pointer where the function itself cannot be turned into a pointer.
  54     ///
  55     /// One example is `<dyn Trait as Trait>::fn`, where the shim contains
  56     /// a virtual call, which codegen supports only via a direct call to the
  57     /// `<dyn Trait as Trait>::fn` instance (an `InstanceDef::Virtual`).
  58     ///
  59     /// Another example is functions annotated with `#[track_caller]`, which
  60     /// must have their implicit caller location argument populated for a call.
  61     /// Because this is a required part of the function's ABI but can't be tracked
  62     /// as a property of the function pointer, we use a single "caller location"
  63     /// (the definition of the function itself).
  64     ReifyShim(DefId),
  65
  66     /// `<fn() as FnTrait>::call_*` (generated `FnTrait` implementation for `fn()` pointers).
  67     ///
  68     /// `DefId` is `FnTrait::call_*`.
  69     FnPtrShim(DefId, Ty<'tcx>),
  70
  71     /// Dynamic dispatch to `<dyn Trait as Trait>::fn`.
  72     ///
  73     /// This `InstanceDef` does not have callable MIR. Calls to `Virtual` instances must be
  74     /// codegen'd as virtual calls through the vtable.
  75     ///
  76     /// If this is reified to a `fn` pointer, a `ReifyShim` is used (see `ReifyShim` above for more
  77     /// details on that).
  78     Virtual(DefId, usize),
  79
  80     /// `<[FnMut closure] as FnOnce>::call_once`.
  81     ///
  82     /// The `DefId` is the ID of the `call_once` method in `FnOnce`.
  83     ClosureOnceShim { call_once: DefId, track_caller: bool },
  84
  85     /// `core::ptr::drop_in_place::<T>`.
  86     ///
  87     /// The `DefId` is for `core::ptr::drop_in_place`.
  88     /// The `Option<Ty<'tcx>>` is either `Some(T)`, or `None` for empty drop
  89     /// glue.
  90     DropGlue(DefId, Option<Ty<'tcx>>),
  91
  92     /// Compiler-generated `<T as Clone>::clone` implementation.
  93     ///
  94     /// For all types that automatically implement `Copy`, a trivial `Clone` impl is provided too.
  95     /// Additionally, arrays, tuples, and closures get a `Clone` shim even if they aren't `Copy`.
  96     ///
  97     /// The `DefId` is for `Clone::clone`, the `Ty` is the type `T` with the builtin `Clone` impl.
  98     CloneShim(DefId, Ty<'tcx>),
  99 }
 100
 101 impl<'tcx> Instance<'tcx> {
 102     /// Returns the `Ty` corresponding to this `Instance`, with generic substitutions applied and
 103     /// lifetimes erased, allowing a `ParamEnv` to be specified for use during normalization.
 104     pub fn ty(&self, tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>) -> Ty<'tcx> {
 105         let ty = tcx.type_of(self.def.def_id());
 106         tcx.subst_and_normalize_erasing_regions(self.substs, param_env, ty)
 107     }
 108
 109     /// Finds a crate that contains a monomorphization of this instance that
 110     /// can be linked to from the local crate. A return value of `None` means
 111     /// no upstream crate provides such an exported monomorphization.
 112     ///
 113     /// This method already takes into account the global `-Zshare-generics`
 114     /// setting, always returning `None` if `share-generics` is off.
 115     pub fn upstream_monomorphization(&self, tcx: TyCtxt<'tcx>) -> Option<CrateNum> {
 116         // If we are not in share generics mode, we don't link to upstream
 117         // monomorphizations but always instantiate our own internal versions
 118         // instead.
 119         if !tcx.sess.opts.share_generics() {
 120             return None;
 121         }
 122
 123         // If this is an item that is defined in the local crate, no upstream
 124         // crate can know about it/provide a monomorphization.
 125         if self.def_id().is_local() {
 126             return None;
 127         }
 128
 129         // If this a non-generic instance, it cannot be a shared monomorphization.
 130         self.substs.non_erasable_generics().next()?;
 131
 132         match self.def {
 133             InstanceDef::Item(def) => tcx
 134                 .upstream_monomorphizations_for(def.did)
 135                 .and_then(|monos| monos.get(&self.substs).cloned()),
 136             InstanceDef::DropGlue(_, Some(_)) => tcx.upstream_drop_glue_for(self.substs),
 137             _ => None,
 138         }
 139     }
 140 }
 141
 142 impl<'tcx> InstanceDef<'tcx> {
 143     #[inline]
 144     pub fn def_id(self) -> DefId {
 145         match self {
 146             InstanceDef::Item(def) => def.did,
 147             InstanceDef::VTableShim(def_id)
 148             | InstanceDef::ReifyShim(def_id)
 149             | InstanceDef::FnPtrShim(def_id, _)
 150             | InstanceDef::Virtual(def_id, _)
 151             | InstanceDef::Intrinsic(def_id)
 152             | InstanceDef::ClosureOnceShim { call_once: def_id, track_caller: _ }
 153             | InstanceDef::DropGlue(def_id, _)
 154             | InstanceDef::CloneShim(def_id, _) => def_id,
 155         }
 156     }
 157
 158     /// Returns the `DefId` of instances which might not require codegen locally.
 159     pub fn def_id_if_not_guaranteed_local_codegen(self) -> Option<DefId> {
 160         match self {
 161             ty::InstanceDef::Item(def) => Some(def.did),
 162             ty::InstanceDef::DropGlue(def_id, Some(_)) => Some(def_id),
 163             InstanceDef::VTableShim(..)
 164             | InstanceDef::ReifyShim(..)
 165             | InstanceDef::FnPtrShim(..)
 166             | InstanceDef::Virtual(..)
 167             | InstanceDef::Intrinsic(..)
 168             | InstanceDef::ClosureOnceShim { .. }
 169             | InstanceDef::DropGlue(..)
 170             | InstanceDef::CloneShim(..) => None,
 171         }
 172     }
 173
 174     #[inline]
 175     pub fn with_opt_param(self) -> ty::WithOptConstParam<DefId> {
 176         match self {
 177             InstanceDef::Item(def) => def,
 178             InstanceDef::VTableShim(def_id)
 179             | InstanceDef::ReifyShim(def_id)
 180             | InstanceDef::FnPtrShim(def_id, _)
 181             | InstanceDef::Virtual(def_id, _)
 182             | InstanceDef::Intrinsic(def_id)
 183             | InstanceDef::ClosureOnceShim { call_once: def_id, track_caller: _ }
 184             | InstanceDef::DropGlue(def_id, _)
 185             | InstanceDef::CloneShim(def_id, _) => ty::WithOptConstParam::unknown(def_id),
 186         }
 187     }
 188
 189     #[inline]
 190     pub fn get_attrs(&self, tcx: TyCtxt<'tcx>, attr: Symbol) -> ty::Attributes<'tcx> {
 191         tcx.get_attrs(self.def_id(), attr)
 192     }
 193
 194     /// Returns `true` if the LLVM version of this instance is unconditionally
 195     /// marked with `inline`. This implies that a copy of this instance is
 196     /// generated in every codegen unit.
 197     /// Note that this is only a hint. See the documentation for
 198     /// `generates_cgu_internal_copy` for more information.
 199     pub fn requires_inline(&self, tcx: TyCtxt<'tcx>) -> bool {
 200         use rustc_hir::definitions::DefPathData;
 201         let def_id = match *self {
 202             ty::InstanceDef::Item(def) => def.did,
 203             ty::InstanceDef::DropGlue(_, Some(_)) => return false,
 204             _ => return true,
 205         };
 206         matches!(
 207             tcx.def_key(def_id).disambiguated_data.data,
 208             DefPathData::Ctor | DefPathData::ClosureExpr
 209         )
 210     }
 211
 212     /// Returns `true` if the machine code for this instance is instantiated in
 213     /// each codegen unit that references it.
 214     /// Note that this is only a hint! The compiler can globally decide to *not*
 215     /// do this in order to speed up compilation. CGU-internal copies are
 216     /// only exist to enable inlining. If inlining is not performed (e.g. at
 217     /// `-Copt-level=0`) then the time for generating them is wasted and it's
 218     /// better to create a single copy with external linkage.
 219     pub fn generates_cgu_internal_copy(&self, tcx: TyCtxt<'tcx>) -> bool {
 220         if self.requires_inline(tcx) {
 221             return true;
 222         }
 223         if let ty::InstanceDef::DropGlue(.., Some(ty)) = *self {
 224             // Drop glue generally wants to be instantiated at every codegen
 225             // unit, but without an #[inline] hint. We should make this
 226             // available to normal end-users.
 227             if tcx.sess.opts.incremental.is_none() {
 228                 return true;
 229             }
 230             // When compiling with incremental, we can generate a *lot* of
 231             // codegen units. Including drop glue into all of them has a
 232             // considerable compile time cost.
 233             //
 234             // We include enums without destructors to allow, say, optimizing
 235             // drops of `Option::None` before LTO. We also respect the intent of
 236             // `#[inline]` on `Drop::drop` implementations.
 237             return ty.ty_adt_def().map_or(true, |adt_def| {
 238                 adt_def.destructor(tcx).map_or_else(
 239                     || adt_def.is_enum(),
 240                     |dtor| tcx.codegen_fn_attrs(dtor.did).requests_inline(),
 241                 )
 242             });
 243         }
 244         tcx.codegen_fn_attrs(self.def_id()).requests_inline()
 245     }
 246
 247     pub fn requires_caller_location(&self, tcx: TyCtxt<'_>) -> bool {
 248         match *self {
 249             InstanceDef::Item(ty::WithOptConstParam { did: def_id, .. })
 250             | InstanceDef::Virtual(def_id, _) => {
 251                 tcx.body_codegen_attrs(def_id).flags.contains(CodegenFnAttrFlags::TRACK_CALLER)
 252             }
 253             InstanceDef::ClosureOnceShim { call_once: _, track_caller } => track_caller,
 254             _ => false,
 255         }
 256     }
 257
 258     /// Returns `true` when the MIR body associated with this instance should be monomorphized
 259     /// by its users (e.g. codegen or miri) by substituting the `substs` from `Instance` (see
 260     /// `Instance::substs_for_mir_body`).
 261     ///
 262     /// Otherwise, returns `false` only for some kinds of shims where the construction of the MIR
 263     /// body should perform necessary substitutions.
 264     pub fn has_polymorphic_mir_body(&self) -> bool {
 265         match *self {
 266             InstanceDef::CloneShim(..)
 267             | InstanceDef::FnPtrShim(..)
 268             | InstanceDef::DropGlue(_, Some(_)) => false,
 269             InstanceDef::ClosureOnceShim { .. }
 270             | InstanceDef::DropGlue(..)
 271             | InstanceDef::Item(_)
 272             | InstanceDef::Intrinsic(..)
 273             | InstanceDef::ReifyShim(..)
 274             | InstanceDef::Virtual(..)
 275             | InstanceDef::VTableShim(..) => true,
 276         }
 277     }
 278 }
 279
 280 fn fmt_instance(
 281     f: &mut fmt::Formatter<'_>,
 282     instance: &Instance<'_>,
 283     type_length: rustc_session::Limit,
 284 ) -> fmt::Result {
 285     ty::tls::with(|tcx| {
 286         let substs = tcx.lift(instance.substs).expect("could not lift for printing");
 287
 288         let s = FmtPrinter::new_with_limit(tcx, Namespace::ValueNS, type_length)
 289             .print_def_path(instance.def_id(), substs)?
 290             .into_buffer();
 291         f.write_str(&s)
 292     })?;
 293
 294     match instance.def {
 295         InstanceDef::Item(_) => Ok(()),
 296         InstanceDef::VTableShim(_) => write!(f, " - shim(vtable)"),
 297         InstanceDef::ReifyShim(_) => write!(f, " - shim(reify)"),
 298         InstanceDef::Intrinsic(_) => write!(f, " - intrinsic"),
 299         InstanceDef::Virtual(_, num) => write!(f, " - virtual#{}", num),
 300         InstanceDef::FnPtrShim(_, ty) => write!(f, " - shim({})", ty),
 301         InstanceDef::ClosureOnceShim { .. } => write!(f, " - shim"),
 302         InstanceDef::DropGlue(_, None) => write!(f, " - shim(None)"),
 303         InstanceDef::DropGlue(_, Some(ty)) => write!(f, " - shim(Some({}))", ty),
 304         InstanceDef::CloneShim(_, ty) => write!(f, " - shim({})", ty),
 305     }
 306 }
 307
 308 pub struct ShortInstance<'a, 'tcx>(pub &'a Instance<'tcx>, pub usize);
 309
 310 impl<'a, 'tcx> fmt::Display for ShortInstance<'a, 'tcx> {
 311     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 312         fmt_instance(f, self.0, rustc_session::Limit(self.1))
 313     }
 314 }
 315
 316 impl<'tcx> fmt::Display for Instance<'tcx> {
 317     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 318         ty::tls::with(|tcx| fmt_instance(f, self, tcx.type_length_limit()))
 319     }
 320 }
 321
 322 impl<'tcx> Instance<'tcx> {
 323     pub fn new(def_id: DefId, substs: SubstsRef<'tcx>) -> Instance<'tcx> {
 324         assert!(
 325             !substs.has_escaping_bound_vars(),
 326             "substs of instance {:?} not normalized for codegen: {:?}",
 327             def_id,
 328             substs
 329         );
 330         Instance { def: InstanceDef::Item(ty::WithOptConstParam::unknown(def_id)), substs }
 331     }
 332
 333     pub fn mono(tcx: TyCtxt<'tcx>, def_id: DefId) -> Instance<'tcx> {
 334         let substs = InternalSubsts::for_item(tcx, def_id, |param, _| match param.kind {
 335             ty::GenericParamDefKind::Lifetime => tcx.lifetimes.re_erased.into(),
 336             ty::GenericParamDefKind::Type { .. } => {
 337                 bug!("Instance::mono: {:?} has type parameters", def_id)
 338             }
 339             ty::GenericParamDefKind::Const { .. } => {
 340                 bug!("Instance::mono: {:?} has const parameters", def_id)
 341             }
 342         });
 343
 344         Instance::new(def_id, substs)
 345     }
 346
 347     #[inline]
 348     pub fn def_id(&self) -> DefId {
 349         self.def.def_id()
 350     }
 351
 352     /// Resolves a `(def_id, substs)` pair to an (optional) instance -- most commonly,
 353     /// this is used to find the precise code that will run for a trait method invocation,
 354     /// if known.
 355     ///
 356     /// Returns `Ok(None)` if we cannot resolve `Instance` to a specific instance.
 357     /// For example, in a context like this,
 358     ///
 359     /// ```ignore (illustrative)
 360     /// fn foo<T: Debug>(t: T) { ... }
 361     /// ```
 362     ///
 363     /// trying to resolve `Debug::fmt` applied to `T` will yield `Ok(None)`, because we do not
 364     /// know what code ought to run. (Note that this setting is also affected by the
 365     /// `RevealMode` in the parameter environment.)
 366     ///
 367     /// Presuming that coherence and type-check have succeeded, if this method is invoked
 368     /// in a monomorphic context (i.e., like during codegen), then it is guaranteed to return
 369     /// `Ok(Some(instance))`.
 370     ///
 371     /// Returns `Err(ErrorGuaranteed)` when the `Instance` resolution process
 372     /// couldn't complete due to errors elsewhere - this is distinct
 373     /// from `Ok(None)` to avoid misleading diagnostics when an error
 374     /// has already been/will be emitted, for the original cause
 375     pub fn resolve(
 376         tcx: TyCtxt<'tcx>,
 377         param_env: ty::ParamEnv<'tcx>,
 378         def_id: DefId,
 379         substs: SubstsRef<'tcx>,
 380     ) -> Result<Option<Instance<'tcx>>, ErrorGuaranteed> {
 381         Instance::resolve_opt_const_arg(
 382             tcx,
 383             param_env,
 384             ty::WithOptConstParam::unknown(def_id),
 385             substs,
 386         )
 387     }
 388
 389     pub fn expect_resolve(
 390         tcx: TyCtxt<'tcx>,
 391         param_env: ty::ParamEnv<'tcx>,
 392         def_id: DefId,
 393         substs: SubstsRef<'tcx>,
 394     ) -> Instance<'tcx> {
 395         match ty::Instance::resolve(tcx, param_env, def_id, substs) {
 396             Ok(Some(instance)) => instance,
 397             _ => bug!(
 398                 "failed to resolve instance for {}",
 399                 tcx.def_path_str_with_substs(def_id, substs)
 400             ),
 401         }
 402     }
 403
 404     // This should be kept up to date with `resolve`.
 405     pub fn resolve_opt_const_arg(
 406         tcx: TyCtxt<'tcx>,
 407         param_env: ty::ParamEnv<'tcx>,
 408         def: ty::WithOptConstParam<DefId>,
 409         substs: SubstsRef<'tcx>,
 410     ) -> Result<Option<Instance<'tcx>>, ErrorGuaranteed> {
 411         // All regions in the result of this query are erased, so it's
 412         // fine to erase all of the input regions.
 413
 414         // HACK(eddyb) erase regions in `substs` first, so that `param_env.and(...)`
 415         // below is more likely to ignore the bounds in scope (e.g. if the only
 416         // generic parameters mentioned by `substs` were lifetime ones).
 417         let substs = tcx.erase_regions(substs);
 418
 419         // FIXME(eddyb) should this always use `param_env.with_reveal_all()`?
 420         if let Some((did, param_did)) = def.as_const_arg() {
 421             tcx.resolve_instance_of_const_arg(
 422                 tcx.erase_regions(param_env.and((did, param_did, substs))),
 423             )
 424         } else {
 425             tcx.resolve_instance(tcx.erase_regions(param_env.and((def.did, substs))))
 426         }
 427     }
 428
 429     pub fn resolve_for_fn_ptr(
 430         tcx: TyCtxt<'tcx>,
 431         param_env: ty::ParamEnv<'tcx>,
 432         def_id: DefId,
 433         substs: SubstsRef<'tcx>,
 434     ) -> Option<Instance<'tcx>> {
 435         debug!("resolve(def_id={:?}, substs={:?})", def_id, substs);
 436         // Use either `resolve_closure` or `resolve_for_vtable`
 437         assert!(!tcx.is_closure(def_id), "Called `resolve_for_fn_ptr` on closure: {:?}", def_id);
 438         Instance::resolve(tcx, param_env, def_id, substs).ok().flatten().map(|mut resolved| {
 439             match resolved.def {
 440                 InstanceDef::Item(def) if resolved.def.requires_caller_location(tcx) => {
 441                     debug!(" => fn pointer created for function with #[track_caller]");
 442                     resolved.def = InstanceDef::ReifyShim(def.did);
 443                 }
 444                 InstanceDef::Virtual(def_id, _) => {
 445                     debug!(" => fn pointer created for virtual call");
 446                     resolved.def = InstanceDef::ReifyShim(def_id);
 447                 }
 448                 _ => {}
 449             }
 450
 451             resolved
 452         })
 453     }
 454
 455     pub fn resolve_for_vtable(
 456         tcx: TyCtxt<'tcx>,
 457         param_env: ty::ParamEnv<'tcx>,
 458         def_id: DefId,
 459         substs: SubstsRef<'tcx>,
 460     ) -> Option<Instance<'tcx>> {
 461         debug!("resolve_for_vtable(def_id={:?}, substs={:?})", def_id, substs);
 462         let fn_sig = tcx.fn_sig(def_id).subst_identity();
 463         let is_vtable_shim = !fn_sig.inputs().skip_binder().is_empty()
 464             && fn_sig.input(0).skip_binder().is_param(0)
 465             && tcx.generics_of(def_id).has_self;
 466         if is_vtable_shim {
 467             debug!(" => associated item with unsizeable self: Self");
 468             Some(Instance { def: InstanceDef::VTableShim(def_id), substs })
 469         } else {
 470             Instance::resolve(tcx, param_env, def_id, substs).ok().flatten().map(|mut resolved| {
 471                 match resolved.def {
 472                     InstanceDef::Item(def) => {
 473                         // We need to generate a shim when we cannot guarantee that
 474                         // the caller of a trait object method will be aware of
 475                         // `#[track_caller]` - this ensures that the caller
 476                         // and callee ABI will always match.
 477                         //
 478                         // The shim is generated when all of these conditions are met:
 479                         //
 480                         // 1) The underlying method expects a caller location parameter
 481                         // in the ABI
 482                         if resolved.def.requires_caller_location(tcx)
 483                             // 2) The caller location parameter comes from having `#[track_caller]`
 484                             // on the implementation, and *not* on the trait method.
 485                             && !tcx.should_inherit_track_caller(def.did)
 486                             // If the method implementation comes from the trait definition itself
 487                             // (e.g. `trait Foo { #[track_caller] my_fn() { /* impl */ } }`),
 488                             // then we don't need to generate a shim. This check is needed because
 489                             // `should_inherit_track_caller` returns `false` if our method
 490                             // implementation comes from the trait block, and not an impl block
 491                             && !matches!(
 492                                 tcx.opt_associated_item(def.did),
 493                                 Some(ty::AssocItem {
 494                                     container: ty::AssocItemContainer::TraitContainer,
 495                                     ..
 496                                 })
 497                             )
 498                         {
 499                             if tcx.is_closure(def.did) {
 500                                 debug!(" => vtable fn pointer created for closure with #[track_caller]: {:?} for method {:?} {:?}",
 501                                        def.did, def_id, substs);
 502
 503                                 // Create a shim for the `FnOnce/FnMut/Fn` method we are calling
 504                                 // - unlike functions, invoking a closure always goes through a
 505                                 // trait.
 506                                 resolved = Instance { def: InstanceDef::ReifyShim(def_id), substs };
 507                             } else {
 508                                 debug!(
 509                                     " => vtable fn pointer created for function with #[track_caller]: {:?}", def.did
 510                                 );
 511                                 resolved.def = InstanceDef::ReifyShim(def.did);
 512                             }
 513                         }
 514                     }
 515                     InstanceDef::Virtual(def_id, _) => {
 516                         debug!(" => vtable fn pointer created for virtual call");
 517                         resolved.def = InstanceDef::ReifyShim(def_id);
 518                     }
 519                     _ => {}
 520                 }
 521
 522                 resolved
 523             })
 524         }
 525     }
 526
 527     pub fn resolve_closure(
 528         tcx: TyCtxt<'tcx>,
 529         def_id: DefId,
 530         substs: ty::SubstsRef<'tcx>,
 531         requested_kind: ty::ClosureKind,
 532     ) -> Option<Instance<'tcx>> {
 533         let actual_kind = substs.as_closure().kind();
 534
 535         match needs_fn_once_adapter_shim(actual_kind, requested_kind) {
 536             Ok(true) => Instance::fn_once_adapter_instance(tcx, def_id, substs),
 537             _ => Some(Instance::new(def_id, substs)),
 538         }
 539     }
 540
 541     pub fn resolve_drop_in_place(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> ty::Instance<'tcx> {
 542         let def_id = tcx.require_lang_item(LangItem::DropInPlace, None);
 543         let substs = tcx.intern_substs(&[ty.into()]);
 544         Instance::expect_resolve(tcx, ty::ParamEnv::reveal_all(), def_id, substs)
 545     }
 546
 547     #[instrument(level = "debug", skip(tcx), ret)]
 548     pub fn fn_once_adapter_instance(
 549         tcx: TyCtxt<'tcx>,
 550         closure_did: DefId,
 551         substs: ty::SubstsRef<'tcx>,
 552     ) -> Option<Instance<'tcx>> {
 553         let fn_once = tcx.require_lang_item(LangItem::FnOnce, None);
 554         let call_once = tcx
 555             .associated_items(fn_once)
 556             .in_definition_order()
 557             .find(|it| it.kind == ty::AssocKind::Fn)
 558             .unwrap()
 559             .def_id;
 560         let track_caller =
 561             tcx.codegen_fn_attrs(closure_did).flags.contains(CodegenFnAttrFlags::TRACK_CALLER);
 562         let def = ty::InstanceDef::ClosureOnceShim { call_once, track_caller };
 563
 564         let self_ty = tcx.mk_closure(closure_did, substs);
 565
 566         let sig = substs.as_closure().sig();
 567         let sig =
 568             tcx.try_normalize_erasing_late_bound_regions(ty::ParamEnv::reveal_all(), sig).ok()?;
 569         assert_eq!(sig.inputs().len(), 1);
 570         let substs = tcx.mk_substs_trait(self_ty, [sig.inputs()[0].into()]);
 571
 572         debug!(?self_ty, ?sig);
 573         Some(Instance { def, substs })
 574     }
 575
 576     /// Depending on the kind of `InstanceDef`, the MIR body associated with an
 577     /// instance is expressed in terms of the generic parameters of `self.def_id()`, and in other
 578     /// cases the MIR body is expressed in terms of the types found in the substitution array.
 579     /// In the former case, we want to substitute those generic types and replace them with the
 580     /// values from the substs when monomorphizing the function body. But in the latter case, we
 581     /// don't want to do that substitution, since it has already been done effectively.
 582     ///
 583     /// This function returns `Some(substs)` in the former case and `None` otherwise -- i.e., if
 584     /// this function returns `None`, then the MIR body does not require substitution during
 585     /// codegen.
 586     fn substs_for_mir_body(&self) -> Option<SubstsRef<'tcx>> {
 587         if self.def.has_polymorphic_mir_body() { Some(self.substs) } else { None }
 588     }
 589
 590     pub fn subst_mir<T>(&self, tcx: TyCtxt<'tcx>, v: &T) -> T
 591     where
 592         T: TypeFoldable<'tcx> + Copy,
 593     {
 594         if let Some(substs) = self.substs_for_mir_body() {
 595             EarlyBinder(*v).subst(tcx, substs)
 596         } else {
 597             *v
 598         }
 599     }
 600
 601     #[inline(always)]
 602     pub fn subst_mir_and_normalize_erasing_regions<T>(
 603         &self,
 604         tcx: TyCtxt<'tcx>,
 605         param_env: ty::ParamEnv<'tcx>,
 606         v: T,
 607     ) -> T
 608     where
 609         T: TypeFoldable<'tcx> + Clone,
 610     {
 611         if let Some(substs) = self.substs_for_mir_body() {
 612             tcx.subst_and_normalize_erasing_regions(substs, param_env, v)
 613         } else {
 614             tcx.normalize_erasing_regions(param_env, v)
 615         }
 616     }
 617
 618     #[inline(always)]
 619     pub fn try_subst_mir_and_normalize_erasing_regions<T>(
 620         &self,
 621         tcx: TyCtxt<'tcx>,
 622         param_env: ty::ParamEnv<'tcx>,
 623         v: T,
 624     ) -> Result<T, NormalizationError<'tcx>>
 625     where
 626         T: TypeFoldable<'tcx> + Clone,
 627     {
 628         if let Some(substs) = self.substs_for_mir_body() {
 629             tcx.try_subst_and_normalize_erasing_regions(substs, param_env, v)
 630         } else {
 631             tcx.try_normalize_erasing_regions(param_env, v)
 632         }
 633     }
 634
 635     /// Returns a new `Instance` where generic parameters in `instance.substs` are replaced by
 636     /// identity parameters if they are determined to be unused in `instance.def`.
 637     pub fn polymorphize(self, tcx: TyCtxt<'tcx>) -> Self {
 638         debug!("polymorphize: running polymorphization analysis");
 639         if !tcx.sess.opts.unstable_opts.polymorphize {
 640             return self;
 641         }
 642
 643         let polymorphized_substs = polymorphize(tcx, self.def, self.substs);
 644         debug!("polymorphize: self={:?} polymorphized_substs={:?}", self, polymorphized_substs);
 645         Self { def: self.def, substs: polymorphized_substs }
 646     }
 647 }
 648
 649 fn polymorphize<'tcx>(
 650     tcx: TyCtxt<'tcx>,
 651     instance: ty::InstanceDef<'tcx>,
 652     substs: SubstsRef<'tcx>,
 653 ) -> SubstsRef<'tcx> {
 654     debug!("polymorphize({:?}, {:?})", instance, substs);
 655     let unused = tcx.unused_generic_params(instance);
 656     debug!("polymorphize: unused={:?}", unused);
 657
 658     // If this is a closure or generator then we need to handle the case where another closure
 659     // from the function is captured as an upvar and hasn't been polymorphized. In this case,
 660     // the unpolymorphized upvar closure would result in a polymorphized closure producing
 661     // multiple mono items (and eventually symbol clashes).
 662     let def_id = instance.def_id();
 663     let upvars_ty = if tcx.is_closure(def_id) {
 664         Some(substs.as_closure().tupled_upvars_ty())
 665     } else if tcx.type_of(def_id).is_generator() {
 666         Some(substs.as_generator().tupled_upvars_ty())
 667     } else {
 668         None
 669     };
 670     let has_upvars = upvars_ty.map_or(false, |ty| !ty.tuple_fields().is_empty());
 671     debug!("polymorphize: upvars_ty={:?} has_upvars={:?}", upvars_ty, has_upvars);
 672
 673     struct PolymorphizationFolder<'tcx> {
 674         tcx: TyCtxt<'tcx>,
 675     }
 676
 677     impl<'tcx> ty::TypeFolder<'tcx> for PolymorphizationFolder<'tcx> {
 678         fn tcx<'a>(&'a self) -> TyCtxt<'tcx> {
 679             self.tcx
 680         }
 681
 682         fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 683             debug!("fold_ty: ty={:?}", ty);
 684             match *ty.kind() {
 685                 ty::Closure(def_id, substs) => {
 686                     let polymorphized_substs = polymorphize(
 687                         self.tcx,
 688                         ty::InstanceDef::Item(ty::WithOptConstParam::unknown(def_id)),
 689                         substs,
 690                     );
 691                     if substs == polymorphized_substs {
 692                         ty
 693                     } else {
 694                         self.tcx.mk_closure(def_id, polymorphized_substs)
 695                     }
 696                 }
 697                 ty::Generator(def_id, substs, movability) => {
 698                     let polymorphized_substs = polymorphize(
 699                         self.tcx,
 700                         ty::InstanceDef::Item(ty::WithOptConstParam::unknown(def_id)),
 701                         substs,
 702                     );
 703                     if substs == polymorphized_substs {
 704                         ty
 705                     } else {
 706                         self.tcx.mk_generator(def_id, polymorphized_substs, movability)
 707                     }
 708                 }
 709                 _ => ty.super_fold_with(self),
 710             }
 711         }
 712     }
 713
 714     InternalSubsts::for_item(tcx, def_id, |param, _| {
 715         let is_unused = unused.is_unused(param.index);
 716         debug!("polymorphize: param={:?} is_unused={:?}", param, is_unused);
 717         match param.kind {
 718             // Upvar case: If parameter is a type parameter..
 719             ty::GenericParamDefKind::Type { .. } if
 720                 // ..and has upvars..
 721                 has_upvars &&
 722                 // ..and this param has the same type as the tupled upvars..
 723                 upvars_ty == Some(substs[param.index as usize].expect_ty()) => {
 724                     // ..then double-check that polymorphization marked it used..
 725                     debug_assert!(!is_unused);
 726                     // ..and polymorphize any closures/generators captured as upvars.
 727                     let upvars_ty = upvars_ty.unwrap();
 728                     let polymorphized_upvars_ty = upvars_ty.fold_with(
 729                         &mut PolymorphizationFolder { tcx });
 730                     debug!("polymorphize: polymorphized_upvars_ty={:?}", polymorphized_upvars_ty);
 731                     ty::GenericArg::from(polymorphized_upvars_ty)
 732                 },
 733
 734             // Simple case: If parameter is a const or type parameter..
 735             ty::GenericParamDefKind::Const { .. } | ty::GenericParamDefKind::Type { .. } if
 736                 // ..and is within range and unused..
 737                 unused.is_unused(param.index) =>
 738                     // ..then use the identity for this parameter.
 739                     tcx.mk_param_from_def(param),
 740
 741             // Otherwise, use the parameter as before.
 742             _ => substs[param.index as usize],
 743         }
 744     })
 745 }
 746
 747 fn needs_fn_once_adapter_shim(
 748     actual_closure_kind: ty::ClosureKind,
 749     trait_closure_kind: ty::ClosureKind,
 750 ) -> Result<bool, ()> {
 751     match (actual_closure_kind, trait_closure_kind) {
 752         (ty::ClosureKind::Fn, ty::ClosureKind::Fn)
 753         | (ty::ClosureKind::FnMut, ty::ClosureKind::FnMut)
 754         | (ty::ClosureKind::FnOnce, ty::ClosureKind::FnOnce) => {
 755             // No adapter needed.
 756             Ok(false)
 757         }
 758         (ty::ClosureKind::Fn, ty::ClosureKind::FnMut) => {
 759             // The closure fn `llfn` is a `fn(&self, ...)`. We want a
 760             // `fn(&mut self, ...)`. In fact, at codegen time, these are
 761             // basically the same thing, so we can just return llfn.
 762             Ok(false)
 763         }
 764         (ty::ClosureKind::Fn | ty::ClosureKind::FnMut, ty::ClosureKind::FnOnce) => {
 765             // The closure fn `llfn` is a `fn(&self, ...)` or `fn(&mut
 766             // self, ...)`. We want a `fn(self, ...)`. We can produce
 767             // this by doing something like:
 768             //
 769             //     fn call_once(self, ...) { call_mut(&self, ...) }
 770             //     fn call_once(mut self, ...) { call_mut(&mut self, ...) }
 771             //
 772             // These are both the same at codegen time.
 773             Ok(true)
 774         }
 775         (ty::ClosureKind::FnMut | ty::ClosureKind::FnOnce, _) => Err(()),
 776     }
 777 }
 778
 779 // Set bits represent unused generic parameters.
 780 // An empty set indicates that all parameters are used.
 781 #[derive(Debug, Copy, Clone, Eq, PartialEq, Decodable, Encodable, HashStable)]
 782 pub struct UnusedGenericParams(FiniteBitSet<u32>);
 783
 784 impl UnusedGenericParams {
 785     pub fn new_all_unused(amount: u32) -> Self {
 786         let mut bitset = FiniteBitSet::new_empty();
 787         bitset.set_range(0..amount);
 788         Self(bitset)
 789     }
 790
 791     pub fn new_all_used() -> Self {
 792         Self(FiniteBitSet::new_empty())
 793     }
 794
 795     pub fn mark_used(&mut self, idx: u32) {
 796         self.0.clear(idx);
 797     }
 798
 799     pub fn is_unused(&self, idx: u32) -> bool {
 800         self.0.contains(idx).unwrap_or(false)
 801     }
 802
 803     pub fn is_used(&self, idx: u32) -> bool {
 804         !self.is_unused(idx)
 805     }
 806
 807     pub fn all_used(&self) -> bool {
 808         self.0.is_empty()
 809     }
 810 }