src/librustc_typeck/collect.rs

   1 //! "Collection" is the process of determining the type and other external
   2 //! details of each item in Rust. Collection is specifically concerned
   3 //! with *inter-procedural* things -- for example, for a function
   4 //! definition, collection will figure out the type and signature of the
   5 //! function, but it will not visit the *body* of the function in any way,
   6 //! nor examine type annotations on local variables (that's the job of
   7 //! type *checking*).
   8 //!
   9 //! Collecting is ultimately defined by a bundle of queries that
  10 //! inquire after various facts about the items in the crate (e.g.,
  11 //! `type_of`, `generics_of`, `predicates_of`, etc). See the `provide` function
  12 //! for the full set.
  13 //!
  14 //! At present, however, we do run collection across all items in the
  15 //! crate as a kind of pass. This should eventually be factored away.
  16
  17 use crate::astconv::{AstConv, Bounds, SizedByDefault};
  18 use crate::check::intrinsic::intrinsic_operation_unsafety;
  19 use crate::constrained_generic_params as cgp;
  20 use crate::middle::resolve_lifetime as rl;
  21 use rustc_ast::ast;
  22 use rustc_ast::ast::{Ident, MetaItemKind};
  23 use rustc_attr::{list_contains_name, mark_used, InlineAttr, OptimizeAttr};
  24 use rustc_data_structures::captures::Captures;
  25 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
  26 use rustc_errors::{struct_span_err, Applicability};
  27 use rustc_hir as hir;
  28 use rustc_hir::def::{CtorKind, DefKind, Res};
  29 use rustc_hir::def_id::{DefId, LocalDefId, LOCAL_CRATE};
  30 use rustc_hir::intravisit::{self, NestedVisitorMap, Visitor};
  31 use rustc_hir::weak_lang_items;
  32 use rustc_hir::{GenericParamKind, Node};
  33 use rustc_middle::hir::map::blocks::FnLikeNode;
  34 use rustc_middle::hir::map::Map;
  35 use rustc_middle::middle::codegen_fn_attrs::{CodegenFnAttrFlags, CodegenFnAttrs};
  36 use rustc_middle::mir::mono::Linkage;
  37 use rustc_middle::ty::query::Providers;
  38 use rustc_middle::ty::subst::{InternalSubsts, Subst};
  39 use rustc_middle::ty::util::Discr;
  40 use rustc_middle::ty::util::IntTypeExt;
  41 use rustc_middle::ty::{self, AdtKind, Const, ToPolyTraitRef, Ty, TyCtxt};
  42 use rustc_middle::ty::{ReprOptions, ToPredicate, WithConstness};
  43 use rustc_session::lint;
  44 use rustc_session::parse::feature_err;
  45 use rustc_span::symbol::{kw, sym, Symbol};
  46 use rustc_span::{Span, DUMMY_SP};
  47 use rustc_target::spec::abi;
  48 use rustc_trait_selection::traits::error_reporting::suggestions::NextTypeParamName;
  49
  50 mod type_of;
  51
  52 struct OnlySelfBounds(bool);
  53
  54 ///////////////////////////////////////////////////////////////////////////
  55 // Main entry point
  56
  57 fn collect_mod_item_types(tcx: TyCtxt<'_>, module_def_id: DefId) {
  58     tcx.hir().visit_item_likes_in_module(
  59         module_def_id,
  60         &mut CollectItemTypesVisitor { tcx }.as_deep_visitor(),
  61     );
  62 }
  63
  64 pub fn provide(providers: &mut Providers<'_>) {
  65     *providers = Providers {
  66         type_of: type_of::type_of,
  67         generics_of,
  68         predicates_of,
  69         predicates_defined_on,
  70         explicit_predicates_of,
  71         super_predicates_of,
  72         type_param_predicates,
  73         trait_def,
  74         adt_def,
  75         fn_sig,
  76         impl_trait_ref,
  77         impl_polarity,
  78         is_foreign_item,
  79         static_mutability,
  80         generator_kind,
  81         codegen_fn_attrs,
  82         collect_mod_item_types,
  83         ..*providers
  84     };
  85 }
  86
  87 ///////////////////////////////////////////////////////////////////////////
  88
  89 /// Context specific to some particular item. This is what implements
  90 /// `AstConv`. It has information about the predicates that are defined
  91 /// on the trait. Unfortunately, this predicate information is
  92 /// available in various different forms at various points in the
  93 /// process. So we can't just store a pointer to e.g., the AST or the
  94 /// parsed ty form, we have to be more flexible. To this end, the
  95 /// `ItemCtxt` is parameterized by a `DefId` that it uses to satisfy
  96 /// `get_type_parameter_bounds` requests, drawing the information from
  97 /// the AST (`hir::Generics`), recursively.
  98 pub struct ItemCtxt<'tcx> {
  99     tcx: TyCtxt<'tcx>,
 100     item_def_id: DefId,
 101 }
 102
 103 ///////////////////////////////////////////////////////////////////////////
 104
 105 #[derive(Default)]
 106 crate struct PlaceholderHirTyCollector(crate Vec<Span>);
 107
 108 impl<'v> Visitor<'v> for PlaceholderHirTyCollector {
 109     type Map = intravisit::ErasedMap<'v>;
 110
 111     fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
 112         NestedVisitorMap::None
 113     }
 114     fn visit_ty(&mut self, t: &'v hir::Ty<'v>) {
 115         if let hir::TyKind::Infer = t.kind {
 116             self.0.push(t.span);
 117         }
 118         intravisit::walk_ty(self, t)
 119     }
 120 }
 121
 122 struct CollectItemTypesVisitor<'tcx> {
 123     tcx: TyCtxt<'tcx>,
 124 }
 125
 126 /// If there are any placeholder types (`_`), emit an error explaining that this is not allowed
 127 /// and suggest adding type parameters in the appropriate place, taking into consideration any and
 128 /// all already existing generic type parameters to avoid suggesting a name that is already in use.
 129 crate fn placeholder_type_error(
 130     tcx: TyCtxt<'tcx>,
 131     span: Span,
 132     generics: &[hir::GenericParam<'_>],
 133     placeholder_types: Vec<Span>,
 134     suggest: bool,
 135 ) {
 136     if placeholder_types.is_empty() {
 137         return;
 138     }
 139     let type_name = generics.next_type_param_name(None);
 140
 141     let mut sugg: Vec<_> =
 142         placeholder_types.iter().map(|sp| (*sp, (*type_name).to_string())).collect();
 143     if generics.is_empty() {
 144         sugg.push((span, format!("<{}>", type_name)));
 145     } else if let Some(arg) = generics.iter().find(|arg| match arg.name {
 146         hir::ParamName::Plain(Ident { name: kw::Underscore, .. }) => true,
 147         _ => false,
 148     }) {
 149         // Account for `_` already present in cases like `struct S<_>(_);` and suggest
 150         // `struct S<T>(T);` instead of `struct S<_, T>(T);`.
 151         sugg.push((arg.span, (*type_name).to_string()));
 152     } else {
 153         let last = generics.iter().last().unwrap();
 154         sugg.push((
 155             // Account for bounds, we want `fn foo<T: E, K>(_: K)` not `fn foo<T, K: E>(_: K)`.
 156             last.bounds_span().unwrap_or(last.span).shrink_to_hi(),
 157             format!(", {}", type_name),
 158         ));
 159     }
 160     let mut err = bad_placeholder_type(tcx, placeholder_types);
 161     if suggest {
 162         err.multipart_suggestion(
 163             "use type parameters instead",
 164             sugg,
 165             Applicability::HasPlaceholders,
 166         );
 167     }
 168     err.emit();
 169 }
 170
 171 fn reject_placeholder_type_signatures_in_item(tcx: TyCtxt<'tcx>, item: &'tcx hir::Item<'tcx>) {
 172     let (generics, suggest) = match &item.kind {
 173         hir::ItemKind::Union(_, generics)
 174         | hir::ItemKind::Enum(_, generics)
 175         | hir::ItemKind::TraitAlias(generics, _)
 176         | hir::ItemKind::Trait(_, _, generics, ..)
 177         | hir::ItemKind::Impl { generics, .. }
 178         | hir::ItemKind::Struct(_, generics) => (generics, true),
 179         hir::ItemKind::OpaqueTy(hir::OpaqueTy { generics, .. })
 180         | hir::ItemKind::TyAlias(_, generics) => (generics, false),
 181         // `static`, `fn` and `const` are handled elsewhere to suggest appropriate type.
 182         _ => return,
 183     };
 184
 185     let mut visitor = PlaceholderHirTyCollector::default();
 186     visitor.visit_item(item);
 187
 188     placeholder_type_error(tcx, generics.span, &generics.params[..], visitor.0, suggest);
 189 }
 190
 191 impl Visitor<'tcx> for CollectItemTypesVisitor<'tcx> {
 192     type Map = Map<'tcx>;
 193
 194     fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
 195         NestedVisitorMap::OnlyBodies(self.tcx.hir())
 196     }
 197
 198     fn visit_item(&mut self, item: &'tcx hir::Item<'tcx>) {
 199         convert_item(self.tcx, item.hir_id);
 200         reject_placeholder_type_signatures_in_item(self.tcx, item);
 201         intravisit::walk_item(self, item);
 202     }
 203
 204     fn visit_generics(&mut self, generics: &'tcx hir::Generics<'tcx>) {
 205         for param in generics.params {
 206             match param.kind {
 207                 hir::GenericParamKind::Lifetime { .. } => {}
 208                 hir::GenericParamKind::Type { default: Some(_), .. } => {
 209                     let def_id = self.tcx.hir().local_def_id(param.hir_id);
 210                     self.tcx.ensure().type_of(def_id);
 211                 }
 212                 hir::GenericParamKind::Type { .. } => {}
 213                 hir::GenericParamKind::Const { .. } => {
 214                     let def_id = self.tcx.hir().local_def_id(param.hir_id);
 215                     self.tcx.ensure().type_of(def_id);
 216                 }
 217             }
 218         }
 219         intravisit::walk_generics(self, generics);
 220     }
 221
 222     fn visit_expr(&mut self, expr: &'tcx hir::Expr<'tcx>) {
 223         if let hir::ExprKind::Closure(..) = expr.kind {
 224             let def_id = self.tcx.hir().local_def_id(expr.hir_id);
 225             self.tcx.ensure().generics_of(def_id);
 226             self.tcx.ensure().type_of(def_id);
 227         }
 228         intravisit::walk_expr(self, expr);
 229     }
 230
 231     fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem<'tcx>) {
 232         convert_trait_item(self.tcx, trait_item.hir_id);
 233         intravisit::walk_trait_item(self, trait_item);
 234     }
 235
 236     fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem<'tcx>) {
 237         convert_impl_item(self.tcx, impl_item.hir_id);
 238         intravisit::walk_impl_item(self, impl_item);
 239     }
 240 }
 241
 242 ///////////////////////////////////////////////////////////////////////////
 243 // Utility types and common code for the above passes.
 244
 245 fn bad_placeholder_type(
 246     tcx: TyCtxt<'tcx>,
 247     mut spans: Vec<Span>,
 248 ) -> rustc_errors::DiagnosticBuilder<'tcx> {
 249     spans.sort();
 250     let mut err = struct_span_err!(
 251         tcx.sess,
 252         spans.clone(),
 253         E0121,
 254         "the type placeholder `_` is not allowed within types on item signatures",
 255     );
 256     for span in spans {
 257         err.span_label(span, "not allowed in type signatures");
 258     }
 259     err
 260 }
 261
 262 impl ItemCtxt<'tcx> {
 263     pub fn new(tcx: TyCtxt<'tcx>, item_def_id: DefId) -> ItemCtxt<'tcx> {
 264         ItemCtxt { tcx, item_def_id }
 265     }
 266
 267     pub fn to_ty(&self, ast_ty: &'tcx hir::Ty<'tcx>) -> Ty<'tcx> {
 268         AstConv::ast_ty_to_ty(self, ast_ty)
 269     }
 270
 271     pub fn hir_id(&self) -> hir::HirId {
 272         self.tcx.hir().as_local_hir_id(self.item_def_id.expect_local())
 273     }
 274
 275     pub fn node(&self) -> hir::Node<'tcx> {
 276         self.tcx.hir().get(self.hir_id())
 277     }
 278 }
 279
 280 impl AstConv<'tcx> for ItemCtxt<'tcx> {
 281     fn tcx(&self) -> TyCtxt<'tcx> {
 282         self.tcx
 283     }
 284
 285     fn item_def_id(&self) -> Option<DefId> {
 286         Some(self.item_def_id)
 287     }
 288
 289     fn default_constness_for_trait_bounds(&self) -> hir::Constness {
 290         if let Some(fn_like) = FnLikeNode::from_node(self.node()) {
 291             fn_like.constness()
 292         } else {
 293             hir::Constness::NotConst
 294         }
 295     }
 296
 297     fn get_type_parameter_bounds(&self, span: Span, def_id: DefId) -> ty::GenericPredicates<'tcx> {
 298         self.tcx.at(span).type_param_predicates((self.item_def_id, def_id.expect_local()))
 299     }
 300
 301     fn re_infer(&self, _: Option<&ty::GenericParamDef>, _: Span) -> Option<ty::Region<'tcx>> {
 302         None
 303     }
 304
 305     fn allow_ty_infer(&self) -> bool {
 306         false
 307     }
 308
 309     fn ty_infer(&self, _: Option<&ty::GenericParamDef>, span: Span) -> Ty<'tcx> {
 310         self.tcx().sess.delay_span_bug(span, "bad placeholder type");
 311         self.tcx().types.err
 312     }
 313
 314     fn ct_infer(
 315         &self,
 316         ty: Ty<'tcx>,
 317         _: Option<&ty::GenericParamDef>,
 318         span: Span,
 319     ) -> &'tcx Const<'tcx> {
 320         bad_placeholder_type(self.tcx(), vec![span]).emit();
 321
 322         self.tcx().mk_const(ty::Const { val: ty::ConstKind::Error, ty })
 323     }
 324
 325     fn projected_ty_from_poly_trait_ref(
 326         &self,
 327         span: Span,
 328         item_def_id: DefId,
 329         item_segment: &hir::PathSegment<'_>,
 330         poly_trait_ref: ty::PolyTraitRef<'tcx>,
 331     ) -> Ty<'tcx> {
 332         if let Some(trait_ref) = poly_trait_ref.no_bound_vars() {
 333             let item_substs = <dyn AstConv<'tcx>>::create_substs_for_associated_item(
 334                 self,
 335                 self.tcx,
 336                 span,
 337                 item_def_id,
 338                 item_segment,
 339                 trait_ref.substs,
 340             );
 341             self.tcx().mk_projection(item_def_id, item_substs)
 342         } else {
 343             // There are no late-bound regions; we can just ignore the binder.
 344             let mut err = struct_span_err!(
 345                 self.tcx().sess,
 346                 span,
 347                 E0212,
 348                 "cannot extract an associated type from a higher-ranked trait bound \
 349                  in this context"
 350             );
 351
 352             match self.node() {
 353                 hir::Node::Field(_) | hir::Node::Ctor(_) | hir::Node::Variant(_) => {
 354                     let item =
 355                         self.tcx.hir().expect_item(self.tcx.hir().get_parent_item(self.hir_id()));
 356                     match &item.kind {
 357                         hir::ItemKind::Enum(_, generics)
 358                         | hir::ItemKind::Struct(_, generics)
 359                         | hir::ItemKind::Union(_, generics) => {
 360                             let lt_name = get_new_lifetime_name(self.tcx, poly_trait_ref, generics);
 361                             let (lt_sp, sugg) = match &generics.params[..] {
 362                                 [] => (generics.span, format!("<{}>", lt_name)),
 363                                 [bound, ..] => {
 364                                     (bound.span.shrink_to_lo(), format!("{}, ", lt_name))
 365                                 }
 366                             };
 367                             let suggestions = vec![
 368                                 (lt_sp, sugg),
 369                                 (
 370                                     span,
 371                                     format!(
 372                                         "{}::{}",
 373                                         // Replace the existing lifetimes with a new named lifetime.
 374                                         self.tcx
 375                                             .replace_late_bound_regions(&poly_trait_ref, |_| {
 376                                                 self.tcx.mk_region(ty::ReEarlyBound(
 377                                                     ty::EarlyBoundRegion {
 378                                                         def_id: item_def_id,
 379                                                         index: 0,
 380                                                         name: Symbol::intern(&lt_name),
 381                                                     },
 382                                                 ))
 383                                             })
 384                                             .0,
 385                                         item_segment.ident
 386                                     ),
 387                                 ),
 388                             ];
 389                             err.multipart_suggestion(
 390                                 "use a fully qualified path with explicit lifetimes",
 391                                 suggestions,
 392                                 Applicability::MaybeIncorrect,
 393                             );
 394                         }
 395                         _ => {}
 396                     }
 397                 }
 398                 hir::Node::Item(hir::Item {
 399                     kind:
 400                         hir::ItemKind::Struct(..) | hir::ItemKind::Enum(..) | hir::ItemKind::Union(..),
 401                     ..
 402                 }) => {}
 403                 hir::Node::Item(_)
 404                 | hir::Node::ForeignItem(_)
 405                 | hir::Node::TraitItem(_)
 406                 | hir::Node::ImplItem(_) => {
 407                     err.span_suggestion(
 408                         span,
 409                         "use a fully qualified path with inferred lifetimes",
 410                         format!(
 411                             "{}::{}",
 412                             // Erase named lt, we want `<A as B<'_>::C`, not `<A as B<'a>::C`.
 413                             self.tcx.anonymize_late_bound_regions(&poly_trait_ref).skip_binder(),
 414                             item_segment.ident
 415                         ),
 416                         Applicability::MaybeIncorrect,
 417                     );
 418                 }
 419                 _ => {}
 420             }
 421             err.emit();
 422             self.tcx().types.err
 423         }
 424     }
 425
 426     fn normalize_ty(&self, _span: Span, ty: Ty<'tcx>) -> Ty<'tcx> {
 427         // Types in item signatures are not normalized to avoid undue dependencies.
 428         ty
 429     }
 430
 431     fn set_tainted_by_errors(&self) {
 432         // There's no obvious place to track this, so just let it go.
 433     }
 434
 435     fn record_ty(&self, _hir_id: hir::HirId, _ty: Ty<'tcx>, _span: Span) {
 436         // There's no place to record types from signatures?
 437     }
 438 }
 439
 440 /// Synthesize a new lifetime name that doesn't clash with any of the lifetimes already present.
 441 fn get_new_lifetime_name<'tcx>(
 442     tcx: TyCtxt<'tcx>,
 443     poly_trait_ref: ty::PolyTraitRef<'tcx>,
 444     generics: &hir::Generics<'tcx>,
 445 ) -> String {
 446     let existing_lifetimes = tcx
 447         .collect_referenced_late_bound_regions(&poly_trait_ref)
 448         .into_iter()
 449         .filter_map(|lt| {
 450             if let ty::BoundRegion::BrNamed(_, name) = lt {
 451                 Some(name.as_str().to_string())
 452             } else {
 453                 None
 454             }
 455         })
 456         .chain(generics.params.iter().filter_map(|param| {
 457             if let hir::GenericParamKind::Lifetime { .. } = &param.kind {
 458                 Some(param.name.ident().as_str().to_string())
 459             } else {
 460                 None
 461             }
 462         }))
 463         .collect::<FxHashSet<String>>();
 464
 465     let a_to_z_repeat_n = |n| {
 466         (b'a'..=b'z').map(move |c| {
 467             let mut s = '\''.to_string();
 468             s.extend(std::iter::repeat(char::from(c)).take(n));
 469             s
 470         })
 471     };
 472
 473     // If all single char lifetime names are present, we wrap around and double the chars.
 474     (1..).flat_map(a_to_z_repeat_n).find(|lt| !existing_lifetimes.contains(lt.as_str())).unwrap()
 475 }
 476
 477 /// Returns the predicates defined on `item_def_id` of the form
 478 /// `X: Foo` where `X` is the type parameter `def_id`.
 479 fn type_param_predicates(
 480     tcx: TyCtxt<'_>,
 481     (item_def_id, def_id): (DefId, LocalDefId),
 482 ) -> ty::GenericPredicates<'_> {
 483     use rustc_hir::*;
 484
 485     // In the AST, bounds can derive from two places. Either
 486     // written inline like `<T: Foo>` or in a where-clause like
 487     // `where T: Foo`.
 488
 489     let param_id = tcx.hir().as_local_hir_id(def_id);
 490     let param_owner = tcx.hir().ty_param_owner(param_id);
 491     let param_owner_def_id = tcx.hir().local_def_id(param_owner);
 492     let generics = tcx.generics_of(param_owner_def_id);
 493     let index = generics.param_def_id_to_index[&def_id.to_def_id()];
 494     let ty = tcx.mk_ty_param(index, tcx.hir().ty_param_name(param_id));
 495
 496     // Don't look for bounds where the type parameter isn't in scope.
 497     let parent = if item_def_id == param_owner_def_id.to_def_id() {
 498         None
 499     } else {
 500         tcx.generics_of(item_def_id).parent
 501     };
 502
 503     let mut result = parent
 504         .map(|parent| {
 505             let icx = ItemCtxt::new(tcx, parent);
 506             icx.get_type_parameter_bounds(DUMMY_SP, def_id.to_def_id())
 507         })
 508         .unwrap_or_default();
 509     let mut extend = None;
 510
 511     let item_hir_id = tcx.hir().as_local_hir_id(item_def_id.expect_local());
 512     let ast_generics = match tcx.hir().get(item_hir_id) {
 513         Node::TraitItem(item) => &item.generics,
 514
 515         Node::ImplItem(item) => &item.generics,
 516
 517         Node::Item(item) => {
 518             match item.kind {
 519                 ItemKind::Fn(.., ref generics, _)
 520                 | ItemKind::Impl { ref generics, .. }
 521                 | ItemKind::TyAlias(_, ref generics)
 522                 | ItemKind::OpaqueTy(OpaqueTy { ref generics, impl_trait_fn: None, .. })
 523                 | ItemKind::Enum(_, ref generics)
 524                 | ItemKind::Struct(_, ref generics)
 525                 | ItemKind::Union(_, ref generics) => generics,
 526                 ItemKind::Trait(_, _, ref generics, ..) => {
 527                     // Implied `Self: Trait` and supertrait bounds.
 528                     if param_id == item_hir_id {
 529                         let identity_trait_ref = ty::TraitRef::identity(tcx, item_def_id);
 530                         extend =
 531                             Some((identity_trait_ref.without_const().to_predicate(), item.span));
 532                     }
 533                     generics
 534                 }
 535                 _ => return result,
 536             }
 537         }
 538
 539         Node::ForeignItem(item) => match item.kind {
 540             ForeignItemKind::Fn(_, _, ref generics) => generics,
 541             _ => return result,
 542         },
 543
 544         _ => return result,
 545     };
 546
 547     let icx = ItemCtxt::new(tcx, item_def_id);
 548     let extra_predicates = extend.into_iter().chain(
 549         icx.type_parameter_bounds_in_generics(ast_generics, param_id, ty, OnlySelfBounds(true))
 550             .into_iter()
 551             .filter(|(predicate, _)| match predicate {
 552                 ty::Predicate::Trait(ref data, _) => data.skip_binder().self_ty().is_param(index),
 553                 _ => false,
 554             }),
 555     );
 556     result.predicates =
 557         tcx.arena.alloc_from_iter(result.predicates.iter().copied().chain(extra_predicates));
 558     result
 559 }
 560
 561 impl ItemCtxt<'tcx> {
 562     /// Finds bounds from `hir::Generics`. This requires scanning through the
 563     /// AST. We do this to avoid having to convert *all* the bounds, which
 564     /// would create artificial cycles. Instead, we can only convert the
 565     /// bounds for a type parameter `X` if `X::Foo` is used.
 566     fn type_parameter_bounds_in_generics(
 567         &self,
 568         ast_generics: &'tcx hir::Generics<'tcx>,
 569         param_id: hir::HirId,
 570         ty: Ty<'tcx>,
 571         only_self_bounds: OnlySelfBounds,
 572     ) -> Vec<(ty::Predicate<'tcx>, Span)> {
 573         let constness = self.default_constness_for_trait_bounds();
 574         let from_ty_params = ast_generics
 575             .params
 576             .iter()
 577             .filter_map(|param| match param.kind {
 578                 GenericParamKind::Type { .. } if param.hir_id == param_id => Some(&param.bounds),
 579                 _ => None,
 580             })
 581             .flat_map(|bounds| bounds.iter())
 582             .flat_map(|b| predicates_from_bound(self, ty, b, constness));
 583
 584         let from_where_clauses = ast_generics
 585             .where_clause
 586             .predicates
 587             .iter()
 588             .filter_map(|wp| match *wp {
 589                 hir::WherePredicate::BoundPredicate(ref bp) => Some(bp),
 590                 _ => None,
 591             })
 592             .flat_map(|bp| {
 593                 let bt = if is_param(self.tcx, &bp.bounded_ty, param_id) {
 594                     Some(ty)
 595                 } else if !only_self_bounds.0 {
 596                     Some(self.to_ty(&bp.bounded_ty))
 597                 } else {
 598                     None
 599                 };
 600                 bp.bounds.iter().filter_map(move |b| bt.map(|bt| (bt, b)))
 601             })
 602             .flat_map(|(bt, b)| predicates_from_bound(self, bt, b, constness));
 603
 604         from_ty_params.chain(from_where_clauses).collect()
 605     }
 606 }
 607
 608 /// Tests whether this is the AST for a reference to the type
 609 /// parameter with ID `param_id`. We use this so as to avoid running
 610 /// `ast_ty_to_ty`, because we want to avoid triggering an all-out
 611 /// conversion of the type to avoid inducing unnecessary cycles.
 612 fn is_param(tcx: TyCtxt<'_>, ast_ty: &hir::Ty<'_>, param_id: hir::HirId) -> bool {
 613     if let hir::TyKind::Path(hir::QPath::Resolved(None, ref path)) = ast_ty.kind {
 614         match path.res {
 615             Res::SelfTy(Some(def_id), None) | Res::Def(DefKind::TyParam, def_id) => {
 616                 def_id == tcx.hir().local_def_id(param_id).to_def_id()
 617             }
 618             _ => false,
 619         }
 620     } else {
 621         false
 622     }
 623 }
 624
 625 fn convert_item(tcx: TyCtxt<'_>, item_id: hir::HirId) {
 626     let it = tcx.hir().expect_item(item_id);
 627     debug!("convert: item {} with id {}", it.ident, it.hir_id);
 628     let def_id = tcx.hir().local_def_id(item_id);
 629     match it.kind {
 630         // These don't define types.
 631         hir::ItemKind::ExternCrate(_)
 632         | hir::ItemKind::Use(..)
 633         | hir::ItemKind::Mod(_)
 634         | hir::ItemKind::GlobalAsm(_) => {}
 635         hir::ItemKind::ForeignMod(ref foreign_mod) => {
 636             for item in foreign_mod.items {
 637                 let def_id = tcx.hir().local_def_id(item.hir_id);
 638                 tcx.ensure().generics_of(def_id);
 639                 tcx.ensure().type_of(def_id);
 640                 tcx.ensure().predicates_of(def_id);
 641                 if let hir::ForeignItemKind::Fn(..) = item.kind {
 642                     tcx.ensure().fn_sig(def_id);
 643                 }
 644             }
 645         }
 646         hir::ItemKind::Enum(ref enum_definition, _) => {
 647             tcx.ensure().generics_of(def_id);
 648             tcx.ensure().type_of(def_id);
 649             tcx.ensure().predicates_of(def_id);
 650             convert_enum_variant_types(tcx, def_id.to_def_id(), &enum_definition.variants);
 651         }
 652         hir::ItemKind::Impl { .. } => {
 653             tcx.ensure().generics_of(def_id);
 654             tcx.ensure().type_of(def_id);
 655             tcx.ensure().impl_trait_ref(def_id);
 656             tcx.ensure().predicates_of(def_id);
 657         }
 658         hir::ItemKind::Trait(..) => {
 659             tcx.ensure().generics_of(def_id);
 660             tcx.ensure().trait_def(def_id);
 661             tcx.at(it.span).super_predicates_of(def_id);
 662             tcx.ensure().predicates_of(def_id);
 663         }
 664         hir::ItemKind::TraitAlias(..) => {
 665             tcx.ensure().generics_of(def_id);
 666             tcx.at(it.span).super_predicates_of(def_id);
 667             tcx.ensure().predicates_of(def_id);
 668         }
 669         hir::ItemKind::Struct(ref struct_def, _) | hir::ItemKind::Union(ref struct_def, _) => {
 670             tcx.ensure().generics_of(def_id);
 671             tcx.ensure().type_of(def_id);
 672             tcx.ensure().predicates_of(def_id);
 673
 674             for f in struct_def.fields() {
 675                 let def_id = tcx.hir().local_def_id(f.hir_id);
 676                 tcx.ensure().generics_of(def_id);
 677                 tcx.ensure().type_of(def_id);
 678                 tcx.ensure().predicates_of(def_id);
 679             }
 680
 681             if let Some(ctor_hir_id) = struct_def.ctor_hir_id() {
 682                 convert_variant_ctor(tcx, ctor_hir_id);
 683             }
 684         }
 685
 686         // Desugared from `impl Trait`, so visited by the function's return type.
 687         hir::ItemKind::OpaqueTy(hir::OpaqueTy { impl_trait_fn: Some(_), .. }) => {}
 688
 689         hir::ItemKind::OpaqueTy(..)
 690         | hir::ItemKind::TyAlias(..)
 691         | hir::ItemKind::Static(..)
 692         | hir::ItemKind::Const(..)
 693         | hir::ItemKind::Fn(..) => {
 694             tcx.ensure().generics_of(def_id);
 695             tcx.ensure().type_of(def_id);
 696             tcx.ensure().predicates_of(def_id);
 697             if let hir::ItemKind::Fn(..) = it.kind {
 698                 tcx.ensure().fn_sig(def_id);
 699             }
 700         }
 701     }
 702 }
 703
 704 fn convert_trait_item(tcx: TyCtxt<'_>, trait_item_id: hir::HirId) {
 705     let trait_item = tcx.hir().expect_trait_item(trait_item_id);
 706     let def_id = tcx.hir().local_def_id(trait_item.hir_id);
 707     tcx.ensure().generics_of(def_id);
 708
 709     match trait_item.kind {
 710         hir::TraitItemKind::Fn(..) => {
 711             tcx.ensure().type_of(def_id);
 712             tcx.ensure().fn_sig(def_id);
 713         }
 714
 715         hir::TraitItemKind::Const(.., Some(_)) => {
 716             tcx.ensure().type_of(def_id);
 717         }
 718
 719         hir::TraitItemKind::Const(..) | hir::TraitItemKind::Type(_, Some(_)) => {
 720             tcx.ensure().type_of(def_id);
 721             // Account for `const C: _;` and `type T = _;`.
 722             let mut visitor = PlaceholderHirTyCollector::default();
 723             visitor.visit_trait_item(trait_item);
 724             placeholder_type_error(tcx, DUMMY_SP, &[], visitor.0, false);
 725         }
 726
 727         hir::TraitItemKind::Type(_, None) => {}
 728     };
 729
 730     tcx.ensure().predicates_of(def_id);
 731 }
 732
 733 fn convert_impl_item(tcx: TyCtxt<'_>, impl_item_id: hir::HirId) {
 734     let def_id = tcx.hir().local_def_id(impl_item_id);
 735     tcx.ensure().generics_of(def_id);
 736     tcx.ensure().type_of(def_id);
 737     tcx.ensure().predicates_of(def_id);
 738     let impl_item = tcx.hir().expect_impl_item(impl_item_id);
 739     match impl_item.kind {
 740         hir::ImplItemKind::Fn(..) => {
 741             tcx.ensure().fn_sig(def_id);
 742         }
 743         hir::ImplItemKind::TyAlias(_) | hir::ImplItemKind::OpaqueTy(_) => {
 744             // Account for `type T = _;`
 745             let mut visitor = PlaceholderHirTyCollector::default();
 746             visitor.visit_impl_item(impl_item);
 747             placeholder_type_error(tcx, DUMMY_SP, &[], visitor.0, false);
 748         }
 749         hir::ImplItemKind::Const(..) => {}
 750     }
 751 }
 752
 753 fn convert_variant_ctor(tcx: TyCtxt<'_>, ctor_id: hir::HirId) {
 754     let def_id = tcx.hir().local_def_id(ctor_id);
 755     tcx.ensure().generics_of(def_id);
 756     tcx.ensure().type_of(def_id);
 757     tcx.ensure().predicates_of(def_id);
 758 }
 759
 760 fn convert_enum_variant_types(tcx: TyCtxt<'_>, def_id: DefId, variants: &[hir::Variant<'_>]) {
 761     let def = tcx.adt_def(def_id);
 762     let repr_type = def.repr.discr_type();
 763     let initial = repr_type.initial_discriminant(tcx);
 764     let mut prev_discr = None::<Discr<'_>>;
 765
 766     // fill the discriminant values and field types
 767     for variant in variants {
 768         let wrapped_discr = prev_discr.map_or(initial, |d| d.wrap_incr(tcx));
 769         prev_discr = Some(
 770             if let Some(ref e) = variant.disr_expr {
 771                 let expr_did = tcx.hir().local_def_id(e.hir_id);
 772                 def.eval_explicit_discr(tcx, expr_did.to_def_id())
 773             } else if let Some(discr) = repr_type.disr_incr(tcx, prev_discr) {
 774                 Some(discr)
 775             } else {
 776                 struct_span_err!(tcx.sess, variant.span, E0370, "enum discriminant overflowed")
 777                     .span_label(
 778                         variant.span,
 779                         format!("overflowed on value after {}", prev_discr.unwrap()),
 780                     )
 781                     .note(&format!(
 782                         "explicitly set `{} = {}` if that is desired outcome",
 783                         variant.ident, wrapped_discr
 784                     ))
 785                     .emit();
 786                 None
 787             }
 788             .unwrap_or(wrapped_discr),
 789         );
 790
 791         for f in variant.data.fields() {
 792             let def_id = tcx.hir().local_def_id(f.hir_id);
 793             tcx.ensure().generics_of(def_id);
 794             tcx.ensure().type_of(def_id);
 795             tcx.ensure().predicates_of(def_id);
 796         }
 797
 798         // Convert the ctor, if any. This also registers the variant as
 799         // an item.
 800         if let Some(ctor_hir_id) = variant.data.ctor_hir_id() {
 801             convert_variant_ctor(tcx, ctor_hir_id);
 802         }
 803     }
 804 }
 805
 806 fn convert_variant(
 807     tcx: TyCtxt<'_>,
 808     variant_did: Option<LocalDefId>,
 809     ctor_did: Option<LocalDefId>,
 810     ident: Ident,
 811     discr: ty::VariantDiscr,
 812     def: &hir::VariantData<'_>,
 813     adt_kind: ty::AdtKind,
 814     parent_did: LocalDefId,
 815 ) -> ty::VariantDef {
 816     let mut seen_fields: FxHashMap<ast::Ident, Span> = Default::default();
 817     let hir_id = tcx.hir().as_local_hir_id(variant_did.unwrap_or(parent_did));
 818     let fields = def
 819         .fields()
 820         .iter()
 821         .map(|f| {
 822             let fid = tcx.hir().local_def_id(f.hir_id);
 823             let dup_span = seen_fields.get(&f.ident.normalize_to_macros_2_0()).cloned();
 824             if let Some(prev_span) = dup_span {
 825                 struct_span_err!(
 826                     tcx.sess,
 827                     f.span,
 828                     E0124,
 829                     "field `{}` is already declared",
 830                     f.ident
 831                 )
 832                 .span_label(f.span, "field already declared")
 833                 .span_label(prev_span, format!("`{}` first declared here", f.ident))
 834                 .emit();
 835             } else {
 836                 seen_fields.insert(f.ident.normalize_to_macros_2_0(), f.span);
 837             }
 838
 839             ty::FieldDef {
 840                 did: fid.to_def_id(),
 841                 ident: f.ident,
 842                 vis: ty::Visibility::from_hir(&f.vis, hir_id, tcx),
 843             }
 844         })
 845         .collect();
 846     let recovered = match def {
 847         hir::VariantData::Struct(_, r) => *r,
 848         _ => false,
 849     };
 850     ty::VariantDef::new(
 851         tcx,
 852         ident,
 853         variant_did.map(LocalDefId::to_def_id),
 854         ctor_did.map(LocalDefId::to_def_id),
 855         discr,
 856         fields,
 857         CtorKind::from_hir(def),
 858         adt_kind,
 859         parent_did.to_def_id(),
 860         recovered,
 861     )
 862 }
 863
 864 fn adt_def(tcx: TyCtxt<'_>, def_id: DefId) -> &ty::AdtDef {
 865     use rustc_hir::*;
 866
 867     let def_id = def_id.expect_local();
 868     let hir_id = tcx.hir().as_local_hir_id(def_id);
 869     let item = match tcx.hir().get(hir_id) {
 870         Node::Item(item) => item,
 871         _ => bug!(),
 872     };
 873
 874     let repr = ReprOptions::new(tcx, def_id.to_def_id());
 875     let (kind, variants) = match item.kind {
 876         ItemKind::Enum(ref def, _) => {
 877             let mut distance_from_explicit = 0;
 878             let variants = def
 879                 .variants
 880                 .iter()
 881                 .map(|v| {
 882                     let variant_did = Some(tcx.hir().local_def_id(v.id));
 883                     let ctor_did =
 884                         v.data.ctor_hir_id().map(|hir_id| tcx.hir().local_def_id(hir_id));
 885
 886                     let discr = if let Some(ref e) = v.disr_expr {
 887                         distance_from_explicit = 0;
 888                         ty::VariantDiscr::Explicit(tcx.hir().local_def_id(e.hir_id).to_def_id())
 889                     } else {
 890                         ty::VariantDiscr::Relative(distance_from_explicit)
 891                     };
 892                     distance_from_explicit += 1;
 893
 894                     convert_variant(
 895                         tcx,
 896                         variant_did,
 897                         ctor_did,
 898                         v.ident,
 899                         discr,
 900                         &v.data,
 901                         AdtKind::Enum,
 902                         def_id,
 903                     )
 904                 })
 905                 .collect();
 906
 907             (AdtKind::Enum, variants)
 908         }
 909         ItemKind::Struct(ref def, _) => {
 910             let variant_did = None::<LocalDefId>;
 911             let ctor_did = def.ctor_hir_id().map(|hir_id| tcx.hir().local_def_id(hir_id));
 912
 913             let variants = std::iter::once(convert_variant(
 914                 tcx,
 915                 variant_did,
 916                 ctor_did,
 917                 item.ident,
 918                 ty::VariantDiscr::Relative(0),
 919                 def,
 920                 AdtKind::Struct,
 921                 def_id,
 922             ))
 923             .collect();
 924
 925             (AdtKind::Struct, variants)
 926         }
 927         ItemKind::Union(ref def, _) => {
 928             let variant_did = None;
 929             let ctor_did = def.ctor_hir_id().map(|hir_id| tcx.hir().local_def_id(hir_id));
 930
 931             let variants = std::iter::once(convert_variant(
 932                 tcx,
 933                 variant_did,
 934                 ctor_did,
 935                 item.ident,
 936                 ty::VariantDiscr::Relative(0),
 937                 def,
 938                 AdtKind::Union,
 939                 def_id,
 940             ))
 941             .collect();
 942
 943             (AdtKind::Union, variants)
 944         }
 945         _ => bug!(),
 946     };
 947     tcx.alloc_adt_def(def_id.to_def_id(), kind, variants, repr)
 948 }
 949
 950 /// Ensures that the super-predicates of the trait with a `DefId`
 951 /// of `trait_def_id` are converted and stored. This also ensures that
 952 /// the transitive super-predicates are converted.
 953 fn super_predicates_of(tcx: TyCtxt<'_>, trait_def_id: DefId) -> ty::GenericPredicates<'_> {
 954     debug!("super_predicates(trait_def_id={:?})", trait_def_id);
 955     let trait_hir_id = tcx.hir().as_local_hir_id(trait_def_id.expect_local());
 956
 957     let item = match tcx.hir().get(trait_hir_id) {
 958         Node::Item(item) => item,
 959         _ => bug!("trait_node_id {} is not an item", trait_hir_id),
 960     };
 961
 962     let (generics, bounds) = match item.kind {
 963         hir::ItemKind::Trait(.., ref generics, ref supertraits, _) => (generics, supertraits),
 964         hir::ItemKind::TraitAlias(ref generics, ref supertraits) => (generics, supertraits),
 965         _ => span_bug!(item.span, "super_predicates invoked on non-trait"),
 966     };
 967
 968     let icx = ItemCtxt::new(tcx, trait_def_id);
 969
 970     // Convert the bounds that follow the colon, e.g., `Bar + Zed` in `trait Foo: Bar + Zed`.
 971     let self_param_ty = tcx.types.self_param;
 972     let superbounds1 =
 973         AstConv::compute_bounds(&icx, self_param_ty, bounds, SizedByDefault::No, item.span);
 974
 975     let superbounds1 = superbounds1.predicates(tcx, self_param_ty);
 976
 977     // Convert any explicit superbounds in the where-clause,
 978     // e.g., `trait Foo where Self: Bar`.
 979     // In the case of trait aliases, however, we include all bounds in the where-clause,
 980     // so e.g., `trait Foo = where u32: PartialEq<Self>` would include `u32: PartialEq<Self>`
 981     // as one of its "superpredicates".
 982     let is_trait_alias = tcx.is_trait_alias(trait_def_id);
 983     let superbounds2 = icx.type_parameter_bounds_in_generics(
 984         generics,
 985         item.hir_id,
 986         self_param_ty,
 987         OnlySelfBounds(!is_trait_alias),
 988     );
 989
 990     // Combine the two lists to form the complete set of superbounds:
 991     let superbounds = &*tcx.arena.alloc_from_iter(superbounds1.into_iter().chain(superbounds2));
 992
 993     // Now require that immediate supertraits are converted,
 994     // which will, in turn, reach indirect supertraits.
 995     for &(pred, span) in superbounds {
 996         debug!("superbound: {:?}", pred);
 997         if let ty::Predicate::Trait(bound, _) = pred {
 998             tcx.at(span).super_predicates_of(bound.def_id());
 999         }
1000     }
1001
1002     ty::GenericPredicates { parent: None, predicates: superbounds }
1003 }
1004
1005 fn trait_def(tcx: TyCtxt<'_>, def_id: DefId) -> ty::TraitDef {
1006     let hir_id = tcx.hir().as_local_hir_id(def_id.expect_local());
1007     let item = tcx.hir().expect_item(hir_id);
1008
1009     let (is_auto, unsafety) = match item.kind {
1010         hir::ItemKind::Trait(is_auto, unsafety, ..) => (is_auto == hir::IsAuto::Yes, unsafety),
1011         hir::ItemKind::TraitAlias(..) => (false, hir::Unsafety::Normal),
1012         _ => span_bug!(item.span, "trait_def_of_item invoked on non-trait"),
1013     };
1014
1015     let paren_sugar = tcx.has_attr(def_id, sym::rustc_paren_sugar);
1016     if paren_sugar && !tcx.features().unboxed_closures {
1017         tcx.sess
1018             .struct_span_err(
1019                 item.span,
1020                 "the `#[rustc_paren_sugar]` attribute is a temporary means of controlling \
1021                  which traits can use parenthetical notation",
1022             )
1023             .help("add `#![feature(unboxed_closures)]` to the crate attributes to use it")
1024             .emit();
1025     }
1026
1027     let is_marker = tcx.has_attr(def_id, sym::marker);
1028     let spec_kind = if tcx.has_attr(def_id, sym::rustc_unsafe_specialization_marker) {
1029         ty::trait_def::TraitSpecializationKind::Marker
1030     } else if tcx.has_attr(def_id, sym::rustc_specialization_trait) {
1031         ty::trait_def::TraitSpecializationKind::AlwaysApplicable
1032     } else {
1033         ty::trait_def::TraitSpecializationKind::None
1034     };
1035     let def_path_hash = tcx.def_path_hash(def_id);
1036     ty::TraitDef::new(def_id, unsafety, paren_sugar, is_auto, is_marker, spec_kind, def_path_hash)
1037 }
1038
1039 fn has_late_bound_regions<'tcx>(tcx: TyCtxt<'tcx>, node: Node<'tcx>) -> Option<Span> {
1040     struct LateBoundRegionsDetector<'tcx> {
1041         tcx: TyCtxt<'tcx>,
1042         outer_index: ty::DebruijnIndex,
1043         has_late_bound_regions: Option<Span>,
1044     }
1045
1046     impl Visitor<'tcx> for LateBoundRegionsDetector<'tcx> {
1047         type Map = intravisit::ErasedMap<'tcx>;
1048
1049         fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
1050             NestedVisitorMap::None
1051         }
1052
1053         fn visit_ty(&mut self, ty: &'tcx hir::Ty<'tcx>) {
1054             if self.has_late_bound_regions.is_some() {
1055                 return;
1056             }
1057             match ty.kind {
1058                 hir::TyKind::BareFn(..) => {
1059                     self.outer_index.shift_in(1);
1060                     intravisit::walk_ty(self, ty);
1061                     self.outer_index.shift_out(1);
1062                 }
1063                 _ => intravisit::walk_ty(self, ty),
1064             }
1065         }
1066
1067         fn visit_poly_trait_ref(
1068             &mut self,
1069             tr: &'tcx hir::PolyTraitRef<'tcx>,
1070             m: hir::TraitBoundModifier,
1071         ) {
1072             if self.has_late_bound_regions.is_some() {
1073                 return;
1074             }
1075             self.outer_index.shift_in(1);
1076             intravisit::walk_poly_trait_ref(self, tr, m);
1077             self.outer_index.shift_out(1);
1078         }
1079
1080         fn visit_lifetime(&mut self, lt: &'tcx hir::Lifetime) {
1081             if self.has_late_bound_regions.is_some() {
1082                 return;
1083             }
1084
1085             match self.tcx.named_region(lt.hir_id) {
1086                 Some(rl::Region::Static | rl::Region::EarlyBound(..)) => {}
1087                 Some(
1088                     rl::Region::LateBound(debruijn, _, _) | rl::Region::LateBoundAnon(debruijn, _),
1089                 ) if debruijn < self.outer_index => {}
1090                 Some(
1091                     rl::Region::LateBound(..)
1092                     | rl::Region::LateBoundAnon(..)
1093                     | rl::Region::Free(..),
1094                 )
1095                 | None => {
1096                     self.has_late_bound_regions = Some(lt.span);
1097                 }
1098             }
1099         }
1100     }
1101
1102     fn has_late_bound_regions<'tcx>(
1103         tcx: TyCtxt<'tcx>,
1104         generics: &'tcx hir::Generics<'tcx>,
1105         decl: &'tcx hir::FnDecl<'tcx>,
1106     ) -> Option<Span> {
1107         let mut visitor = LateBoundRegionsDetector {
1108             tcx,
1109             outer_index: ty::INNERMOST,
1110             has_late_bound_regions: None,
1111         };
1112         for param in generics.params {
1113             if let GenericParamKind::Lifetime { .. } = param.kind {
1114                 if tcx.is_late_bound(param.hir_id) {
1115                     return Some(param.span);
1116                 }
1117             }
1118         }
1119         visitor.visit_fn_decl(decl);
1120         visitor.has_late_bound_regions
1121     }
1122
1123     match node {
1124         Node::TraitItem(item) => match item.kind {
1125             hir::TraitItemKind::Fn(ref sig, _) => {
1126                 has_late_bound_regions(tcx, &item.generics, &sig.decl)
1127             }
1128             _ => None,
1129         },
1130         Node::ImplItem(item) => match item.kind {
1131             hir::ImplItemKind::Fn(ref sig, _) => {
1132                 has_late_bound_regions(tcx, &item.generics, &sig.decl)
1133             }
1134             _ => None,
1135         },
1136         Node::ForeignItem(item) => match item.kind {
1137             hir::ForeignItemKind::Fn(ref fn_decl, _, ref generics) => {
1138                 has_late_bound_regions(tcx, generics, fn_decl)
1139             }
1140             _ => None,
1141         },
1142         Node::Item(item) => match item.kind {
1143             hir::ItemKind::Fn(ref sig, .., ref generics, _) => {
1144                 has_late_bound_regions(tcx, generics, &sig.decl)
1145             }
1146             _ => None,
1147         },
1148         _ => None,
1149     }
1150 }
1151
1152 fn generics_of(tcx: TyCtxt<'_>, def_id: DefId) -> ty::Generics {
1153     use rustc_hir::*;
1154
1155     let hir_id = tcx.hir().as_local_hir_id(def_id.expect_local());
1156
1157     let node = tcx.hir().get(hir_id);
1158     let parent_def_id = match node {
1159         Node::ImplItem(_)
1160         | Node::TraitItem(_)
1161         | Node::Variant(_)
1162         | Node::Ctor(..)
1163         | Node::Field(_) => {
1164             let parent_id = tcx.hir().get_parent_item(hir_id);
1165             Some(tcx.hir().local_def_id(parent_id).to_def_id())
1166         }
1167         // FIXME(#43408) enable this always when we get lazy normalization.
1168         Node::AnonConst(_) => {
1169             let parent_id = tcx.hir().get_parent_item(hir_id);
1170             let parent_def_id = tcx.hir().local_def_id(parent_id);
1171
1172             // HACK(eddyb) this provides the correct generics when
1173             // `feature(const_generics)` is enabled, so that const expressions
1174             // used with const generics, e.g. `Foo<{N+1}>`, can work at all.
1175             if tcx.features().const_generics {
1176                 Some(parent_def_id.to_def_id())
1177             } else {
1178                 let parent_node = tcx.hir().get(tcx.hir().get_parent_node(hir_id));
1179                 match parent_node {
1180                     // HACK(eddyb) this provides the correct generics for repeat
1181                     // expressions' count (i.e. `N` in `[x; N]`), as they shouldn't
1182                     // be able to cause query cycle errors.
1183                     Node::Expr(&Expr { kind: ExprKind::Repeat(_, ref constant), .. })
1184                         if constant.hir_id == hir_id =>
1185                     {
1186                         Some(parent_def_id.to_def_id())
1187                     }
1188
1189                     _ => None,
1190                 }
1191             }
1192         }
1193         Node::Expr(&hir::Expr { kind: hir::ExprKind::Closure(..), .. }) => {
1194             Some(tcx.closure_base_def_id(def_id))
1195         }
1196         Node::Item(item) => match item.kind {
1197             ItemKind::OpaqueTy(hir::OpaqueTy { impl_trait_fn, .. }) => {
1198                 impl_trait_fn.or_else(|| {
1199                     let parent_id = tcx.hir().get_parent_item(hir_id);
1200                     if parent_id != hir_id && parent_id != CRATE_HIR_ID {
1201                         debug!("generics_of: parent of opaque ty {:?} is {:?}", def_id, parent_id);
1202                         // If this 'impl Trait' is nested inside another 'impl Trait'
1203                         // (e.g. `impl Foo<MyType = impl Bar<A>>`), we need to use the 'parent'
1204                         // 'impl Trait' for its generic parameters, since we can reference them
1205                         // from the 'child' 'impl Trait'
1206                         if let Node::Item(hir::Item { kind: ItemKind::OpaqueTy(..), .. }) =
1207                             tcx.hir().get(parent_id)
1208                         {
1209                             Some(tcx.hir().local_def_id(parent_id).to_def_id())
1210                         } else {
1211                             None
1212                         }
1213                     } else {
1214                         None
1215                     }
1216                 })
1217             }
1218             _ => None,
1219         },
1220         _ => None,
1221     };
1222
1223     let mut opt_self = None;
1224     let mut allow_defaults = false;
1225
1226     let no_generics = hir::Generics::empty();
1227     let ast_generics = match node {
1228         Node::TraitItem(item) => &item.generics,
1229
1230         Node::ImplItem(item) => &item.generics,
1231
1232         Node::Item(item) => {
1233             match item.kind {
1234                 ItemKind::Fn(.., ref generics, _) | ItemKind::Impl { ref generics, .. } => generics,
1235
1236                 ItemKind::TyAlias(_, ref generics)
1237                 | ItemKind::Enum(_, ref generics)
1238                 | ItemKind::Struct(_, ref generics)
1239                 | ItemKind::OpaqueTy(hir::OpaqueTy { ref generics, .. })
1240                 | ItemKind::Union(_, ref generics) => {
1241                     allow_defaults = true;
1242                     generics
1243                 }
1244
1245                 ItemKind::Trait(_, _, ref generics, ..)
1246                 | ItemKind::TraitAlias(ref generics, ..) => {
1247                     // Add in the self type parameter.
1248                     //
1249                     // Something of a hack: use the node id for the trait, also as
1250                     // the node id for the Self type parameter.
1251                     let param_id = item.hir_id;
1252
1253                     opt_self = Some(ty::GenericParamDef {
1254                         index: 0,
1255                         name: kw::SelfUpper,
1256                         def_id: tcx.hir().local_def_id(param_id).to_def_id(),
1257                         pure_wrt_drop: false,
1258                         kind: ty::GenericParamDefKind::Type {
1259                             has_default: false,
1260                             object_lifetime_default: rl::Set1::Empty,
1261                             synthetic: None,
1262                         },
1263                     });
1264
1265                     allow_defaults = true;
1266                     generics
1267                 }
1268
1269                 _ => &no_generics,
1270             }
1271         }
1272
1273         Node::ForeignItem(item) => match item.kind {
1274             ForeignItemKind::Static(..) => &no_generics,
1275             ForeignItemKind::Fn(_, _, ref generics) => generics,
1276             ForeignItemKind::Type => &no_generics,
1277         },
1278
1279         _ => &no_generics,
1280     };
1281
1282     let has_self = opt_self.is_some();
1283     let mut parent_has_self = false;
1284     let mut own_start = has_self as u32;
1285     let parent_count = parent_def_id.map_or(0, |def_id| {
1286         let generics = tcx.generics_of(def_id);
1287         assert_eq!(has_self, false);
1288         parent_has_self = generics.has_self;
1289         own_start = generics.count() as u32;
1290         generics.parent_count + generics.params.len()
1291     });
1292
1293     let mut params: Vec<_> = opt_self.into_iter().collect();
1294
1295     let early_lifetimes = early_bound_lifetimes_from_generics(tcx, ast_generics);
1296     params.extend(early_lifetimes.enumerate().map(|(i, param)| ty::GenericParamDef {
1297         name: param.name.ident().name,
1298         index: own_start + i as u32,
1299         def_id: tcx.hir().local_def_id(param.hir_id).to_def_id(),
1300         pure_wrt_drop: param.pure_wrt_drop,
1301         kind: ty::GenericParamDefKind::Lifetime,
1302     }));
1303
1304     let object_lifetime_defaults = tcx.object_lifetime_defaults(hir_id);
1305
1306     // Now create the real type and const parameters.
1307     let type_start = own_start - has_self as u32 + params.len() as u32;
1308     let mut i = 0;
1309
1310     // FIXME(const_generics): a few places in the compiler expect generic params
1311     // to be in the order lifetimes, then type params, then const params.
1312     //
1313     // To prevent internal errors in case const parameters are supplied before
1314     // type parameters we first add all type params, then all const params.
1315     params.extend(ast_generics.params.iter().filter_map(|param| {
1316         if let GenericParamKind::Type { ref default, synthetic, .. } = param.kind {
1317             if !allow_defaults && default.is_some() {
1318                 if !tcx.features().default_type_parameter_fallback {
1319                     tcx.struct_span_lint_hir(
1320                         lint::builtin::INVALID_TYPE_PARAM_DEFAULT,
1321                         param.hir_id,
1322                         param.span,
1323                         |lint| {
1324                             lint.build(
1325                                 "defaults for type parameters are only allowed in \
1326                                         `struct`, `enum`, `type`, or `trait` definitions.",
1327                             )
1328                             .emit();
1329                         },
1330                     );
1331                 }
1332             }
1333
1334             let kind = ty::GenericParamDefKind::Type {
1335                 has_default: default.is_some(),
1336                 object_lifetime_default: object_lifetime_defaults
1337                     .as_ref()
1338                     .map_or(rl::Set1::Empty, |o| o[i]),
1339                 synthetic,
1340             };
1341
1342             let param_def = ty::GenericParamDef {
1343                 index: type_start + i as u32,
1344                 name: param.name.ident().name,
1345                 def_id: tcx.hir().local_def_id(param.hir_id).to_def_id(),
1346                 pure_wrt_drop: param.pure_wrt_drop,
1347                 kind,
1348             };
1349             i += 1;
1350             Some(param_def)
1351         } else {
1352             None
1353         }
1354     }));
1355
1356     params.extend(ast_generics.params.iter().filter_map(|param| {
1357         if let GenericParamKind::Const { .. } = param.kind {
1358             let param_def = ty::GenericParamDef {
1359                 index: type_start + i as u32,
1360                 name: param.name.ident().name,
1361                 def_id: tcx.hir().local_def_id(param.hir_id).to_def_id(),
1362                 pure_wrt_drop: param.pure_wrt_drop,
1363                 kind: ty::GenericParamDefKind::Const,
1364             };
1365             i += 1;
1366             Some(param_def)
1367         } else {
1368             None
1369         }
1370     }));
1371
1372     // provide junk type parameter defs - the only place that
1373     // cares about anything but the length is instantiation,
1374     // and we don't do that for closures.
1375     if let Node::Expr(&hir::Expr { kind: hir::ExprKind::Closure(.., gen), .. }) = node {
1376         let dummy_args = if gen.is_some() {
1377             &["<resume_ty>", "<yield_ty>", "<return_ty>", "<witness>", "<upvars>"][..]
1378         } else {
1379             &["<closure_kind>", "<closure_signature>", "<upvars>"][..]
1380         };
1381
1382         params.extend(dummy_args.iter().enumerate().map(|(i, &arg)| ty::GenericParamDef {
1383             index: type_start + i as u32,
1384             name: Symbol::intern(arg),
1385             def_id,
1386             pure_wrt_drop: false,
1387             kind: ty::GenericParamDefKind::Type {
1388                 has_default: false,
1389                 object_lifetime_default: rl::Set1::Empty,
1390                 synthetic: None,
1391             },
1392         }));
1393     }
1394
1395     let param_def_id_to_index = params.iter().map(|param| (param.def_id, param.index)).collect();
1396
1397     ty::Generics {
1398         parent: parent_def_id,
1399         parent_count,
1400         params,
1401         param_def_id_to_index,
1402         has_self: has_self || parent_has_self,
1403         has_late_bound_regions: has_late_bound_regions(tcx, node),
1404     }
1405 }
1406
1407 fn are_suggestable_generic_args(generic_args: &[hir::GenericArg<'_>]) -> bool {
1408     generic_args
1409         .iter()
1410         .filter_map(|arg| match arg {
1411             hir::GenericArg::Type(ty) => Some(ty),
1412             _ => None,
1413         })
1414         .any(is_suggestable_infer_ty)
1415 }
1416
1417 /// Whether `ty` is a type with `_` placeholders that can be inferred. Used in diagnostics only to
1418 /// use inference to provide suggestions for the appropriate type if possible.
1419 fn is_suggestable_infer_ty(ty: &hir::Ty<'_>) -> bool {
1420     use hir::TyKind::*;
1421     match &ty.kind {
1422         Infer => true,
1423         Slice(ty) | Array(ty, _) => is_suggestable_infer_ty(ty),
1424         Tup(tys) => tys.iter().any(is_suggestable_infer_ty),
1425         Ptr(mut_ty) | Rptr(_, mut_ty) => is_suggestable_infer_ty(mut_ty.ty),
1426         Def(_, generic_args) => are_suggestable_generic_args(generic_args),
1427         Path(hir::QPath::TypeRelative(ty, segment)) => {
1428             is_suggestable_infer_ty(ty) || are_suggestable_generic_args(segment.generic_args().args)
1429         }
1430         Path(hir::QPath::Resolved(ty_opt, hir::Path { segments, .. })) => {
1431             ty_opt.map_or(false, is_suggestable_infer_ty)
1432                 || segments
1433                     .iter()
1434                     .any(|segment| are_suggestable_generic_args(segment.generic_args().args))
1435         }
1436         _ => false,
1437     }
1438 }
1439
1440 pub fn get_infer_ret_ty(output: &'hir hir::FnRetTy<'hir>) -> Option<&'hir hir::Ty<'hir>> {
1441     if let hir::FnRetTy::Return(ref ty) = output {
1442         if is_suggestable_infer_ty(ty) {
1443             return Some(&**ty);
1444         }
1445     }
1446     None
1447 }
1448
1449 fn fn_sig(tcx: TyCtxt<'_>, def_id: DefId) -> ty::PolyFnSig<'_> {
1450     use rustc_hir::Node::*;
1451     use rustc_hir::*;
1452
1453     let def_id = def_id.expect_local();
1454     let hir_id = tcx.hir().as_local_hir_id(def_id);
1455
1456     let icx = ItemCtxt::new(tcx, def_id.to_def_id());
1457
1458     match tcx.hir().get(hir_id) {
1459         TraitItem(hir::TraitItem {
1460             kind: TraitItemKind::Fn(sig, TraitFn::Provided(_)),
1461             ident,
1462             generics,
1463             ..
1464         })
1465         | ImplItem(hir::ImplItem { kind: ImplItemKind::Fn(sig, _), ident, generics, .. })
1466         | Item(hir::Item { kind: ItemKind::Fn(sig, generics, _), ident, .. }) => {
1467             match get_infer_ret_ty(&sig.decl.output) {
1468                 Some(ty) => {
1469                     let fn_sig = tcx.typeck_tables_of(def_id).liberated_fn_sigs()[hir_id];
1470                     let mut visitor = PlaceholderHirTyCollector::default();
1471                     visitor.visit_ty(ty);
1472                     let mut diag = bad_placeholder_type(tcx, visitor.0);
1473                     let ret_ty = fn_sig.output();
1474                     if ret_ty != tcx.types.err {
1475                         diag.span_suggestion(
1476                             ty.span,
1477                             "replace with the correct return type",
1478                             ret_ty.to_string(),
1479                             Applicability::MaybeIncorrect,
1480                         );
1481                     }
1482                     diag.emit();
1483                     ty::Binder::bind(fn_sig)
1484                 }
1485                 None => AstConv::ty_of_fn(
1486                     &icx,
1487                     sig.header.unsafety,
1488                     sig.header.abi,
1489                     &sig.decl,
1490                     &generics,
1491                     Some(ident.span),
1492                 ),
1493             }
1494         }
1495
1496         TraitItem(hir::TraitItem {
1497             kind: TraitItemKind::Fn(FnSig { header, decl }, _),
1498             ident,
1499             generics,
1500             ..
1501         }) => {
1502             AstConv::ty_of_fn(&icx, header.unsafety, header.abi, decl, &generics, Some(ident.span))
1503         }
1504
1505         ForeignItem(&hir::ForeignItem {
1506             kind: ForeignItemKind::Fn(ref fn_decl, _, _),
1507             ident,
1508             ..
1509         }) => {
1510             let abi = tcx.hir().get_foreign_abi(hir_id);
1511             compute_sig_of_foreign_fn_decl(tcx, def_id.to_def_id(), fn_decl, abi, ident)
1512         }
1513
1514         Ctor(data) | Variant(hir::Variant { data, .. }) if data.ctor_hir_id().is_some() => {
1515             let ty = tcx.type_of(tcx.hir().get_parent_did(hir_id).to_def_id());
1516             let inputs =
1517                 data.fields().iter().map(|f| tcx.type_of(tcx.hir().local_def_id(f.hir_id)));
1518             ty::Binder::bind(tcx.mk_fn_sig(
1519                 inputs,
1520                 ty,
1521                 false,
1522                 hir::Unsafety::Normal,
1523                 abi::Abi::Rust,
1524             ))
1525         }
1526
1527         Expr(&hir::Expr { kind: hir::ExprKind::Closure(..), .. }) => {
1528             // Closure signatures are not like other function
1529             // signatures and cannot be accessed through `fn_sig`. For
1530             // example, a closure signature excludes the `self`
1531             // argument. In any case they are embedded within the
1532             // closure type as part of the `ClosureSubsts`.
1533             //
1534             // To get the signature of a closure, you should use the
1535             // `sig` method on the `ClosureSubsts`:
1536             //
1537             //    substs.as_closure().sig(def_id, tcx)
1538             bug!(
1539                 "to get the signature of a closure, use `substs.as_closure().sig()` not `fn_sig()`",
1540             );
1541         }
1542
1543         x => {
1544             bug!("unexpected sort of node in fn_sig(): {:?}", x);
1545         }
1546     }
1547 }
1548
1549 fn impl_trait_ref(tcx: TyCtxt<'_>, def_id: DefId) -> Option<ty::TraitRef<'_>> {
1550     let icx = ItemCtxt::new(tcx, def_id);
1551
1552     let hir_id = tcx.hir().as_local_hir_id(def_id.expect_local());
1553     match tcx.hir().expect_item(hir_id).kind {
1554         hir::ItemKind::Impl { ref of_trait, .. } => of_trait.as_ref().map(|ast_trait_ref| {
1555             let selfty = tcx.type_of(def_id);
1556             AstConv::instantiate_mono_trait_ref(&icx, ast_trait_ref, selfty)
1557         }),
1558         _ => bug!(),
1559     }
1560 }
1561
1562 fn impl_polarity(tcx: TyCtxt<'_>, def_id: DefId) -> ty::ImplPolarity {
1563     let hir_id = tcx.hir().as_local_hir_id(def_id.expect_local());
1564     let is_rustc_reservation = tcx.has_attr(def_id, sym::rustc_reservation_impl);
1565     let item = tcx.hir().expect_item(hir_id);
1566     match &item.kind {
1567         hir::ItemKind::Impl { polarity: hir::ImplPolarity::Negative(span), of_trait, .. } => {
1568             if is_rustc_reservation {
1569                 let span = span.to(of_trait.as_ref().map(|t| t.path.span).unwrap_or(*span));
1570                 tcx.sess.span_err(span, "reservation impls can't be negative");
1571             }
1572             ty::ImplPolarity::Negative
1573         }
1574         hir::ItemKind::Impl { polarity: hir::ImplPolarity::Positive, of_trait: None, .. } => {
1575             if is_rustc_reservation {
1576                 tcx.sess.span_err(item.span, "reservation impls can't be inherent");
1577             }
1578             ty::ImplPolarity::Positive
1579         }
1580         hir::ItemKind::Impl {
1581             polarity: hir::ImplPolarity::Positive, of_trait: Some(_), ..
1582         } => {
1583             if is_rustc_reservation {
1584                 ty::ImplPolarity::Reservation
1585             } else {
1586                 ty::ImplPolarity::Positive
1587             }
1588         }
1589         ref item => bug!("impl_polarity: {:?} not an impl", item),
1590     }
1591 }
1592
1593 /// Returns the early-bound lifetimes declared in this generics
1594 /// listing. For anything other than fns/methods, this is just all
1595 /// the lifetimes that are declared. For fns or methods, we have to
1596 /// screen out those that do not appear in any where-clauses etc using
1597 /// `resolve_lifetime::early_bound_lifetimes`.
1598 fn early_bound_lifetimes_from_generics<'a, 'tcx: 'a>(
1599     tcx: TyCtxt<'tcx>,
1600     generics: &'a hir::Generics<'a>,
1601 ) -> impl Iterator<Item = &'a hir::GenericParam<'a>> + Captures<'tcx> {
1602     generics.params.iter().filter(move |param| match param.kind {
1603         GenericParamKind::Lifetime { .. } => !tcx.is_late_bound(param.hir_id),
1604         _ => false,
1605     })
1606 }
1607
1608 /// Returns a list of type predicates for the definition with ID `def_id`, including inferred
1609 /// lifetime constraints. This includes all predicates returned by `explicit_predicates_of`, plus
1610 /// inferred constraints concerning which regions outlive other regions.
1611 fn predicates_defined_on(tcx: TyCtxt<'_>, def_id: DefId) -> ty::GenericPredicates<'_> {
1612     debug!("predicates_defined_on({:?})", def_id);
1613     let mut result = tcx.explicit_predicates_of(def_id);
1614     debug!("predicates_defined_on: explicit_predicates_of({:?}) = {:?}", def_id, result,);
1615     let inferred_outlives = tcx.inferred_outlives_of(def_id);
1616     if !inferred_outlives.is_empty() {
1617         debug!(
1618             "predicates_defined_on: inferred_outlives_of({:?}) = {:?}",
1619             def_id, inferred_outlives,
1620         );
1621         if result.predicates.is_empty() {
1622             result.predicates = inferred_outlives;
1623         } else {
1624             result.predicates = tcx
1625                 .arena
1626                 .alloc_from_iter(result.predicates.iter().chain(inferred_outlives).copied());
1627         }
1628     }
1629     debug!("predicates_defined_on({:?}) = {:?}", def_id, result);
1630     result
1631 }
1632
1633 /// Returns a list of all type predicates (explicit and implicit) for the definition with
1634 /// ID `def_id`. This includes all predicates returned by `predicates_defined_on`, plus
1635 /// `Self: Trait` predicates for traits.
1636 fn predicates_of(tcx: TyCtxt<'_>, def_id: DefId) -> ty::GenericPredicates<'_> {
1637     let mut result = tcx.predicates_defined_on(def_id);
1638
1639     if tcx.is_trait(def_id) {
1640         // For traits, add `Self: Trait` predicate. This is
1641         // not part of the predicates that a user writes, but it
1642         // is something that one must prove in order to invoke a
1643         // method or project an associated type.
1644         //
1645         // In the chalk setup, this predicate is not part of the
1646         // "predicates" for a trait item. But it is useful in
1647         // rustc because if you directly (e.g.) invoke a trait
1648         // method like `Trait::method(...)`, you must naturally
1649         // prove that the trait applies to the types that were
1650         // used, and adding the predicate into this list ensures
1651         // that this is done.
1652         let span = tcx.sess.source_map().guess_head_span(tcx.def_span(def_id));
1653         result.predicates =
1654             tcx.arena.alloc_from_iter(result.predicates.iter().copied().chain(std::iter::once((
1655                 ty::TraitRef::identity(tcx, def_id).without_const().to_predicate(),
1656                 span,
1657             ))));
1658     }
1659     debug!("predicates_of(def_id={:?}) = {:?}", def_id, result);
1660     result
1661 }
1662
1663 /// Returns a list of user-specified type predicates for the definition with ID `def_id`.
1664 /// N.B., this does not include any implied/inferred constraints.
1665 fn explicit_predicates_of(tcx: TyCtxt<'_>, def_id: DefId) -> ty::GenericPredicates<'_> {
1666     use rustc_hir::*;
1667
1668     debug!("explicit_predicates_of(def_id={:?})", def_id);
1669
1670     /// A data structure with unique elements, which preserves order of insertion.
1671     /// Preserving the order of insertion is important here so as not to break
1672     /// compile-fail UI tests.
1673     // FIXME(eddyb) just use `IndexSet` from `indexmap`.
1674     struct UniquePredicates<'tcx> {
1675         predicates: Vec<(ty::Predicate<'tcx>, Span)>,
1676         uniques: FxHashSet<(ty::Predicate<'tcx>, Span)>,
1677     }
1678
1679     impl<'tcx> UniquePredicates<'tcx> {
1680         fn new() -> Self {
1681             UniquePredicates { predicates: vec![], uniques: FxHashSet::default() }
1682         }
1683
1684         fn push(&mut self, value: (ty::Predicate<'tcx>, Span)) {
1685             if self.uniques.insert(value) {
1686                 self.predicates.push(value);
1687             }
1688         }
1689
1690         fn extend<I: IntoIterator<Item = (ty::Predicate<'tcx>, Span)>>(&mut self, iter: I) {
1691             for value in iter {
1692                 self.push(value);
1693             }
1694         }
1695     }
1696
1697     let hir_id = tcx.hir().as_local_hir_id(def_id.expect_local());
1698     let node = tcx.hir().get(hir_id);
1699
1700     let mut is_trait = None;
1701     let mut is_default_impl_trait = None;
1702
1703     let icx = ItemCtxt::new(tcx, def_id);
1704     let constness = icx.default_constness_for_trait_bounds();
1705
1706     const NO_GENERICS: &hir::Generics<'_> = &hir::Generics::empty();
1707
1708     let mut predicates = UniquePredicates::new();
1709
1710     let ast_generics = match node {
1711         Node::TraitItem(item) => &item.generics,
1712
1713         Node::ImplItem(item) => match item.kind {
1714             ImplItemKind::OpaqueTy(ref bounds) => {
1715                 ty::print::with_no_queries(|| {
1716                     let substs = InternalSubsts::identity_for_item(tcx, def_id);
1717                     let opaque_ty = tcx.mk_opaque(def_id, substs);
1718                     debug!(
1719                         "explicit_predicates_of({:?}): created opaque type {:?}",
1720                         def_id, opaque_ty
1721                     );
1722
1723                     // Collect the bounds, i.e., the `A + B + 'c` in `impl A + B + 'c`.
1724                     let bounds = AstConv::compute_bounds(
1725                         &icx,
1726                         opaque_ty,
1727                         bounds,
1728                         SizedByDefault::Yes,
1729                         tcx.def_span(def_id),
1730                     );
1731
1732                     predicates.extend(bounds.predicates(tcx, opaque_ty));
1733                     &item.generics
1734                 })
1735             }
1736             _ => &item.generics,
1737         },
1738
1739         Node::Item(item) => {
1740             match item.kind {
1741                 ItemKind::Impl { defaultness, ref generics, .. } => {
1742                     if defaultness.is_default() {
1743                         is_default_impl_trait = tcx.impl_trait_ref(def_id);
1744                     }
1745                     generics
1746                 }
1747                 ItemKind::Fn(.., ref generics, _)
1748                 | ItemKind::TyAlias(_, ref generics)
1749                 | ItemKind::Enum(_, ref generics)
1750                 | ItemKind::Struct(_, ref generics)
1751                 | ItemKind::Union(_, ref generics) => generics,
1752
1753                 ItemKind::Trait(_, _, ref generics, .., items) => {
1754                     is_trait = Some((ty::TraitRef::identity(tcx, def_id), items));
1755                     generics
1756                 }
1757                 ItemKind::TraitAlias(ref generics, _) => {
1758                     is_trait = Some((ty::TraitRef::identity(tcx, def_id), &[]));
1759                     generics
1760                 }
1761                 ItemKind::OpaqueTy(OpaqueTy {
1762                     ref bounds,
1763                     impl_trait_fn,
1764                     ref generics,
1765                     origin: _,
1766                 }) => {
1767                     let bounds_predicates = ty::print::with_no_queries(|| {
1768                         let substs = InternalSubsts::identity_for_item(tcx, def_id);
1769                         let opaque_ty = tcx.mk_opaque(def_id, substs);
1770
1771                         // Collect the bounds, i.e., the `A + B + 'c` in `impl A + B + 'c`.
1772                         let bounds = AstConv::compute_bounds(
1773                             &icx,
1774                             opaque_ty,
1775                             bounds,
1776                             SizedByDefault::Yes,
1777                             tcx.def_span(def_id),
1778                         );
1779
1780                         bounds.predicates(tcx, opaque_ty)
1781                     });
1782                     if impl_trait_fn.is_some() {
1783                         // opaque types
1784                         return ty::GenericPredicates {
1785                             parent: None,
1786                             predicates: tcx.arena.alloc_from_iter(bounds_predicates),
1787                         };
1788                     } else {
1789                         // named opaque types
1790                         predicates.extend(bounds_predicates);
1791                         generics
1792                     }
1793                 }
1794
1795                 _ => NO_GENERICS,
1796             }
1797         }
1798
1799         Node::ForeignItem(item) => match item.kind {
1800             ForeignItemKind::Static(..) => NO_GENERICS,
1801             ForeignItemKind::Fn(_, _, ref generics) => generics,
1802             ForeignItemKind::Type => NO_GENERICS,
1803         },
1804
1805         _ => NO_GENERICS,
1806     };
1807
1808     let generics = tcx.generics_of(def_id);
1809     let parent_count = generics.parent_count as u32;
1810     let has_own_self = generics.has_self && parent_count == 0;
1811
1812     // Below we'll consider the bounds on the type parameters (including `Self`)
1813     // and the explicit where-clauses, but to get the full set of predicates
1814     // on a trait we need to add in the supertrait bounds and bounds found on
1815     // associated types.
1816     if let Some((_trait_ref, _)) = is_trait {
1817         predicates.extend(tcx.super_predicates_of(def_id).predicates.iter().cloned());
1818     }
1819
1820     // In default impls, we can assume that the self type implements
1821     // the trait. So in:
1822     //
1823     //     default impl Foo for Bar { .. }
1824     //
1825     // we add a default where clause `Foo: Bar`. We do a similar thing for traits
1826     // (see below). Recall that a default impl is not itself an impl, but rather a
1827     // set of defaults that can be incorporated into another impl.
1828     if let Some(trait_ref) = is_default_impl_trait {
1829         predicates.push((
1830             trait_ref.to_poly_trait_ref().without_const().to_predicate(),
1831             tcx.def_span(def_id),
1832         ));
1833     }
1834
1835     // Collect the region predicates that were declared inline as
1836     // well. In the case of parameters declared on a fn or method, we
1837     // have to be careful to only iterate over early-bound regions.
1838     let mut index = parent_count + has_own_self as u32;
1839     for param in early_bound_lifetimes_from_generics(tcx, ast_generics) {
1840         let region = tcx.mk_region(ty::ReEarlyBound(ty::EarlyBoundRegion {
1841             def_id: tcx.hir().local_def_id(param.hir_id).to_def_id(),
1842             index,
1843             name: param.name.ident().name,
1844         }));
1845         index += 1;
1846
1847         match param.kind {
1848             GenericParamKind::Lifetime { .. } => {
1849                 param.bounds.iter().for_each(|bound| match bound {
1850                     hir::GenericBound::Outlives(lt) => {
1851                         let bound = AstConv::ast_region_to_region(&icx, &lt, None);
1852                         let outlives = ty::Binder::bind(ty::OutlivesPredicate(region, bound));
1853                         predicates.push((outlives.to_predicate(), lt.span));
1854                     }
1855                     _ => bug!(),
1856                 });
1857             }
1858             _ => bug!(),
1859         }
1860     }
1861
1862     // Collect the predicates that were written inline by the user on each
1863     // type parameter (e.g., `<T: Foo>`).
1864     for param in ast_generics.params {
1865         if let GenericParamKind::Type { .. } = param.kind {
1866             let name = param.name.ident().name;
1867             let param_ty = ty::ParamTy::new(index, name).to_ty(tcx);
1868             index += 1;
1869
1870             let sized = SizedByDefault::Yes;
1871             let bounds = AstConv::compute_bounds(&icx, param_ty, &param.bounds, sized, param.span);
1872             predicates.extend(bounds.predicates(tcx, param_ty));
1873         }
1874     }
1875
1876     // Add in the bounds that appear in the where-clause.
1877     let where_clause = &ast_generics.where_clause;
1878     for predicate in where_clause.predicates {
1879         match predicate {
1880             &hir::WherePredicate::BoundPredicate(ref bound_pred) => {
1881                 let ty = icx.to_ty(&bound_pred.bounded_ty);
1882
1883                 // Keep the type around in a dummy predicate, in case of no bounds.
1884                 // That way, `where Ty:` is not a complete noop (see #53696) and `Ty`
1885                 // is still checked for WF.
1886                 if bound_pred.bounds.is_empty() {
1887                     if let ty::Param(_) = ty.kind {
1888                         // This is a `where T:`, which can be in the HIR from the
1889                         // transformation that moves `?Sized` to `T`'s declaration.
1890                         // We can skip the predicate because type parameters are
1891                         // trivially WF, but also we *should*, to avoid exposing
1892                         // users who never wrote `where Type:,` themselves, to
1893                         // compiler/tooling bugs from not handling WF predicates.
1894                     } else {
1895                         let span = bound_pred.bounded_ty.span;
1896                         let re_root_empty = tcx.lifetimes.re_root_empty;
1897                         let predicate = ty::OutlivesPredicate(ty, re_root_empty);
1898                         predicates.push((
1899                             ty::Predicate::TypeOutlives(ty::Binder::dummy(predicate)),
1900                             span,
1901                         ));
1902                     }
1903                 }
1904
1905                 for bound in bound_pred.bounds.iter() {
1906                     match bound {
1907                         &hir::GenericBound::Trait(ref poly_trait_ref, modifier) => {
1908                             let constness = match modifier {
1909                                 hir::TraitBoundModifier::MaybeConst => hir::Constness::NotConst,
1910                                 hir::TraitBoundModifier::None => constness,
1911                                 hir::TraitBoundModifier::Maybe => bug!("this wasn't handled"),
1912                             };
1913
1914                             let mut bounds = Bounds::default();
1915                             let _ = AstConv::instantiate_poly_trait_ref(
1916                                 &icx,
1917                                 poly_trait_ref,
1918                                 constness,
1919                                 ty,
1920                                 &mut bounds,
1921                             );
1922                             predicates.extend(bounds.predicates(tcx, ty));
1923                         }
1924
1925                         &hir::GenericBound::Outlives(ref lifetime) => {
1926                             let region = AstConv::ast_region_to_region(&icx, lifetime, None);
1927                             let pred = ty::Binder::bind(ty::OutlivesPredicate(ty, region));
1928                             predicates.push((ty::Predicate::TypeOutlives(pred), lifetime.span))
1929                         }
1930                     }
1931                 }
1932             }
1933
1934             &hir::WherePredicate::RegionPredicate(ref region_pred) => {
1935                 let r1 = AstConv::ast_region_to_region(&icx, &region_pred.lifetime, None);
1936                 predicates.extend(region_pred.bounds.iter().map(|bound| {
1937                     let (r2, span) = match bound {
1938                         hir::GenericBound::Outlives(lt) => {
1939                             (AstConv::ast_region_to_region(&icx, lt, None), lt.span)
1940                         }
1941                         _ => bug!(),
1942                     };
1943                     let pred = ty::Binder::bind(ty::OutlivesPredicate(r1, r2));
1944
1945                     (ty::Predicate::RegionOutlives(pred), span)
1946                 }))
1947             }
1948
1949             &hir::WherePredicate::EqPredicate(..) => {
1950                 // FIXME(#20041)
1951             }
1952         }
1953     }
1954
1955     // Add predicates from associated type bounds.
1956     if let Some((self_trait_ref, trait_items)) = is_trait {
1957         predicates.extend(trait_items.iter().flat_map(|trait_item_ref| {
1958             associated_item_predicates(tcx, def_id, self_trait_ref, trait_item_ref)
1959         }))
1960     }
1961
1962     let mut predicates = predicates.predicates;
1963
1964     // Subtle: before we store the predicates into the tcx, we
1965     // sort them so that predicates like `T: Foo<Item=U>` come
1966     // before uses of `U`.  This avoids false ambiguity errors
1967     // in trait checking. See `setup_constraining_predicates`
1968     // for details.
1969     if let Node::Item(&Item { kind: ItemKind::Impl { .. }, .. }) = node {
1970         let self_ty = tcx.type_of(def_id);
1971         let trait_ref = tcx.impl_trait_ref(def_id);
1972         cgp::setup_constraining_predicates(
1973             tcx,
1974             &mut predicates,
1975             trait_ref,
1976             &mut cgp::parameters_for_impl(self_ty, trait_ref),
1977         );
1978     }
1979
1980     let result = ty::GenericPredicates {
1981         parent: generics.parent,
1982         predicates: tcx.arena.alloc_from_iter(predicates),
1983     };
1984     debug!("explicit_predicates_of(def_id={:?}) = {:?}", def_id, result);
1985     result
1986 }
1987
1988 fn associated_item_predicates(
1989     tcx: TyCtxt<'tcx>,
1990     def_id: DefId,
1991     self_trait_ref: ty::TraitRef<'tcx>,
1992     trait_item_ref: &hir::TraitItemRef,
1993 ) -> Vec<(ty::Predicate<'tcx>, Span)> {
1994     let trait_item = tcx.hir().trait_item(trait_item_ref.id);
1995     let item_def_id = tcx.hir().local_def_id(trait_item_ref.id.hir_id);
1996     let bounds = match trait_item.kind {
1997         hir::TraitItemKind::Type(ref bounds, _) => bounds,
1998         _ => return Vec::new(),
1999     };
2000
2001     let is_gat = !tcx.generics_of(item_def_id).params.is_empty();
2002
2003     let mut had_error = false;
2004
2005     let mut unimplemented_error = |arg_kind: &str| {
2006         if !had_error {
2007             tcx.sess
2008                 .struct_span_err(
2009                     trait_item.span,
2010                     &format!("{}-generic associated types are not yet implemented", arg_kind),
2011                 )
2012                 .note(
2013                     "for more information, see issue #44265 \
2014                      <https://github.com/rust-lang/rust/issues/44265> for more information",
2015                 )
2016                 .emit();
2017             had_error = true;
2018         }
2019     };
2020
2021     let mk_bound_param = |param: &ty::GenericParamDef, _: &_| {
2022         match param.kind {
2023             ty::GenericParamDefKind::Lifetime => tcx
2024                 .mk_region(ty::RegionKind::ReLateBound(
2025                     ty::INNERMOST,
2026                     ty::BoundRegion::BrNamed(param.def_id, param.name),
2027                 ))
2028                 .into(),
2029             // FIXME(generic_associated_types): Use bound types and constants
2030             // once they are handled by the trait system.
2031             ty::GenericParamDefKind::Type { .. } => {
2032                 unimplemented_error("type");
2033                 tcx.types.err.into()
2034             }
2035             ty::GenericParamDefKind::Const => {
2036                 unimplemented_error("const");
2037                 tcx.mk_const(ty::Const { val: ty::ConstKind::Error, ty: tcx.type_of(param.def_id) })
2038                     .into()
2039             }
2040         }
2041     };
2042
2043     let bound_substs = if is_gat {
2044         // Given:
2045         //
2046         // trait X<'a, B, const C: usize> {
2047         //     type T<'d, E, const F: usize>: Default;
2048         // }
2049         //
2050         // We need to create predicates on the trait:
2051         //
2052         // for<'d, E, const F: usize>
2053         // <Self as X<'a, B, const C: usize>>::T<'d, E, const F: usize>: Sized + Default
2054         //
2055         // We substitute escaping bound parameters for the generic
2056         // arguments to the associated type which are then bound by
2057         // the `Binder` around the the predicate.
2058         //
2059         // FIXME(generic_associated_types): Currently only lifetimes are handled.
2060         self_trait_ref.substs.extend_to(tcx, item_def_id.to_def_id(), mk_bound_param)
2061     } else {
2062         self_trait_ref.substs
2063     };
2064
2065     let assoc_ty =
2066         tcx.mk_projection(tcx.hir().local_def_id(trait_item.hir_id).to_def_id(), bound_substs);
2067
2068     let bounds = AstConv::compute_bounds(
2069         &ItemCtxt::new(tcx, def_id),
2070         assoc_ty,
2071         bounds,
2072         SizedByDefault::Yes,
2073         trait_item.span,
2074     );
2075
2076     let predicates = bounds.predicates(tcx, assoc_ty);
2077
2078     if is_gat {
2079         // We use shifts to get the regions that we're substituting to
2080         // be bound by the binders in the `Predicate`s rather that
2081         // escaping.
2082         let shifted_in = ty::fold::shift_vars(tcx, &predicates, 1);
2083         let substituted = shifted_in.subst(tcx, bound_substs);
2084         ty::fold::shift_out_vars(tcx, &substituted, 1)
2085     } else {
2086         predicates
2087     }
2088 }
2089
2090 /// Converts a specific `GenericBound` from the AST into a set of
2091 /// predicates that apply to the self type. A vector is returned
2092 /// because this can be anywhere from zero predicates (`T: ?Sized` adds no
2093 /// predicates) to one (`T: Foo`) to many (`T: Bar<X = i32>` adds `T: Bar`
2094 /// and `<T as Bar>::X == i32`).
2095 fn predicates_from_bound<'tcx>(
2096     astconv: &dyn AstConv<'tcx>,
2097     param_ty: Ty<'tcx>,
2098     bound: &'tcx hir::GenericBound<'tcx>,
2099     constness: hir::Constness,
2100 ) -> Vec<(ty::Predicate<'tcx>, Span)> {
2101     match *bound {
2102         hir::GenericBound::Trait(ref tr, modifier) => {
2103             let constness = match modifier {
2104                 hir::TraitBoundModifier::Maybe => return vec![],
2105                 hir::TraitBoundModifier::MaybeConst => hir::Constness::NotConst,
2106                 hir::TraitBoundModifier::None => constness,
2107             };
2108
2109             let mut bounds = Bounds::default();
2110             let _ = astconv.instantiate_poly_trait_ref(tr, constness, param_ty, &mut bounds);
2111             bounds.predicates(astconv.tcx(), param_ty)
2112         }
2113         hir::GenericBound::Outlives(ref lifetime) => {
2114             let region = astconv.ast_region_to_region(lifetime, None);
2115             let pred = ty::Binder::bind(ty::OutlivesPredicate(param_ty, region));
2116             vec![(ty::Predicate::TypeOutlives(pred), lifetime.span)]
2117         }
2118     }
2119 }
2120
2121 fn compute_sig_of_foreign_fn_decl<'tcx>(
2122     tcx: TyCtxt<'tcx>,
2123     def_id: DefId,
2124     decl: &'tcx hir::FnDecl<'tcx>,
2125     abi: abi::Abi,
2126     ident: Ident,
2127 ) -> ty::PolyFnSig<'tcx> {
2128     let unsafety = if abi == abi::Abi::RustIntrinsic {
2129         intrinsic_operation_unsafety(&tcx.item_name(def_id).as_str())
2130     } else {
2131         hir::Unsafety::Unsafe
2132     };
2133     let fty = AstConv::ty_of_fn(
2134         &ItemCtxt::new(tcx, def_id),
2135         unsafety,
2136         abi,
2137         decl,
2138         &hir::Generics::empty(),
2139         Some(ident.span),
2140     );
2141
2142     // Feature gate SIMD types in FFI, since I am not sure that the
2143     // ABIs are handled at all correctly. -huonw
2144     if abi != abi::Abi::RustIntrinsic
2145         && abi != abi::Abi::PlatformIntrinsic
2146         && !tcx.features().simd_ffi
2147     {
2148         let check = |ast_ty: &hir::Ty<'_>, ty: Ty<'_>| {
2149             if ty.is_simd() {
2150                 let snip = tcx
2151                     .sess
2152                     .source_map()
2153                     .span_to_snippet(ast_ty.span)
2154                     .map_or(String::new(), |s| format!(" `{}`", s));
2155                 tcx.sess
2156                     .struct_span_err(
2157                         ast_ty.span,
2158                         &format!(
2159                             "use of SIMD type{} in FFI is highly experimental and \
2160                              may result in invalid code",
2161                             snip
2162                         ),
2163                     )
2164                     .help("add `#![feature(simd_ffi)]` to the crate attributes to enable")
2165                     .emit();
2166             }
2167         };
2168         for (input, ty) in decl.inputs.iter().zip(*fty.inputs().skip_binder()) {
2169             check(&input, ty)
2170         }
2171         if let hir::FnRetTy::Return(ref ty) = decl.output {
2172             check(&ty, *fty.output().skip_binder())
2173         }
2174     }
2175
2176     fty
2177 }
2178
2179 fn is_foreign_item(tcx: TyCtxt<'_>, def_id: DefId) -> bool {
2180     match tcx.hir().get_if_local(def_id) {
2181         Some(Node::ForeignItem(..)) => true,
2182         Some(_) => false,
2183         _ => bug!("is_foreign_item applied to non-local def-id {:?}", def_id),
2184     }
2185 }
2186
2187 fn static_mutability(tcx: TyCtxt<'_>, def_id: DefId) -> Option<hir::Mutability> {
2188     match tcx.hir().get_if_local(def_id) {
2189         Some(
2190             Node::Item(&hir::Item { kind: hir::ItemKind::Static(_, mutbl, _), .. })
2191             | Node::ForeignItem(&hir::ForeignItem {
2192                 kind: hir::ForeignItemKind::Static(_, mutbl),
2193                 ..
2194             }),
2195         ) => Some(mutbl),
2196         Some(_) => None,
2197         _ => bug!("static_mutability applied to non-local def-id {:?}", def_id),
2198     }
2199 }
2200
2201 fn generator_kind(tcx: TyCtxt<'_>, def_id: DefId) -> Option<hir::GeneratorKind> {
2202     match tcx.hir().get_if_local(def_id) {
2203         Some(Node::Expr(&rustc_hir::Expr {
2204             kind: rustc_hir::ExprKind::Closure(_, _, body_id, _, _),
2205             ..
2206         })) => tcx.hir().body(body_id).generator_kind(),
2207         Some(_) => None,
2208         _ => bug!("generator_kind applied to non-local def-id {:?}", def_id),
2209     }
2210 }
2211
2212 fn from_target_feature(
2213     tcx: TyCtxt<'_>,
2214     id: DefId,
2215     attr: &ast::Attribute,
2216     whitelist: &FxHashMap<String, Option<Symbol>>,
2217     target_features: &mut Vec<Symbol>,
2218 ) {
2219     let list = match attr.meta_item_list() {
2220         Some(list) => list,
2221         None => return,
2222     };
2223     let bad_item = |span| {
2224         let msg = "malformed `target_feature` attribute input";
2225         let code = "enable = \"..\"".to_owned();
2226         tcx.sess
2227             .struct_span_err(span, &msg)
2228             .span_suggestion(span, "must be of the form", code, Applicability::HasPlaceholders)
2229             .emit();
2230     };
2231     let rust_features = tcx.features();
2232     for item in list {
2233         // Only `enable = ...` is accepted in the meta-item list.
2234         if !item.check_name(sym::enable) {
2235             bad_item(item.span());
2236             continue;
2237         }
2238
2239         // Must be of the form `enable = "..."` (a string).
2240         let value = match item.value_str() {
2241             Some(value) => value,
2242             None => {
2243                 bad_item(item.span());
2244                 continue;
2245             }
2246         };
2247
2248         // We allow comma separation to enable multiple features.
2249         target_features.extend(value.as_str().split(',').filter_map(|feature| {
2250             // Only allow whitelisted features per platform.
2251             let feature_gate = match whitelist.get(feature) {
2252                 Some(g) => g,
2253                 None => {
2254                     let msg =
2255                         format!("the feature named `{}` is not valid for this target", feature);
2256                     let mut err = tcx.sess.struct_span_err(item.span(), &msg);
2257                     err.span_label(
2258                         item.span(),
2259                         format!("`{}` is not valid for this target", feature),
2260                     );
2261                     if feature.starts_with('+') {
2262                         let valid = whitelist.contains_key(&feature[1..]);
2263                         if valid {
2264                             err.help("consider removing the leading `+` in the feature name");
2265                         }
2266                     }
2267                     err.emit();
2268                     return None;
2269                 }
2270             };
2271
2272             // Only allow features whose feature gates have been enabled.
2273             let allowed = match feature_gate.as_ref().copied() {
2274                 Some(sym::arm_target_feature) => rust_features.arm_target_feature,
2275                 Some(sym::aarch64_target_feature) => rust_features.aarch64_target_feature,
2276                 Some(sym::hexagon_target_feature) => rust_features.hexagon_target_feature,
2277                 Some(sym::powerpc_target_feature) => rust_features.powerpc_target_feature,
2278                 Some(sym::mips_target_feature) => rust_features.mips_target_feature,
2279                 Some(sym::avx512_target_feature) => rust_features.avx512_target_feature,
2280                 Some(sym::mmx_target_feature) => rust_features.mmx_target_feature,
2281                 Some(sym::sse4a_target_feature) => rust_features.sse4a_target_feature,
2282                 Some(sym::tbm_target_feature) => rust_features.tbm_target_feature,
2283                 Some(sym::wasm_target_feature) => rust_features.wasm_target_feature,
2284                 Some(sym::cmpxchg16b_target_feature) => rust_features.cmpxchg16b_target_feature,
2285                 Some(sym::adx_target_feature) => rust_features.adx_target_feature,
2286                 Some(sym::movbe_target_feature) => rust_features.movbe_target_feature,
2287                 Some(sym::rtm_target_feature) => rust_features.rtm_target_feature,
2288                 Some(sym::f16c_target_feature) => rust_features.f16c_target_feature,
2289                 Some(name) => bug!("unknown target feature gate {}", name),
2290                 None => true,
2291             };
2292             if !allowed && id.is_local() {
2293                 feature_err(
2294                     &tcx.sess.parse_sess,
2295                     feature_gate.unwrap(),
2296                     item.span(),
2297                     &format!("the target feature `{}` is currently unstable", feature),
2298                 )
2299                 .emit();
2300             }
2301             Some(Symbol::intern(feature))
2302         }));
2303     }
2304 }
2305
2306 fn linkage_by_name(tcx: TyCtxt<'_>, def_id: DefId, name: &str) -> Linkage {
2307     use rustc_middle::mir::mono::Linkage::*;
2308
2309     // Use the names from src/llvm/docs/LangRef.rst here. Most types are only
2310     // applicable to variable declarations and may not really make sense for
2311     // Rust code in the first place but whitelist them anyway and trust that
2312     // the user knows what s/he's doing. Who knows, unanticipated use cases
2313     // may pop up in the future.
2314     //
2315     // ghost, dllimport, dllexport and linkonce_odr_autohide are not supported
2316     // and don't have to be, LLVM treats them as no-ops.
2317     match name {
2318         "appending" => Appending,
2319         "available_externally" => AvailableExternally,
2320         "common" => Common,
2321         "extern_weak" => ExternalWeak,
2322         "external" => External,
2323         "internal" => Internal,
2324         "linkonce" => LinkOnceAny,
2325         "linkonce_odr" => LinkOnceODR,
2326         "private" => Private,
2327         "weak" => WeakAny,
2328         "weak_odr" => WeakODR,
2329         _ => {
2330             let span = tcx.hir().span_if_local(def_id);
2331             if let Some(span) = span {
2332                 tcx.sess.span_fatal(span, "invalid linkage specified")
2333             } else {
2334                 tcx.sess.fatal(&format!("invalid linkage specified: {}", name))
2335             }
2336         }
2337     }
2338 }
2339
2340 fn codegen_fn_attrs(tcx: TyCtxt<'_>, id: DefId) -> CodegenFnAttrs {
2341     let attrs = tcx.get_attrs(id);
2342
2343     let mut codegen_fn_attrs = CodegenFnAttrs::new();
2344     if should_inherit_track_caller(tcx, id) {
2345         codegen_fn_attrs.flags |= CodegenFnAttrFlags::TRACK_CALLER;
2346     }
2347
2348     let whitelist = tcx.target_features_whitelist(LOCAL_CRATE);
2349
2350     let mut inline_span = None;
2351     let mut link_ordinal_span = None;
2352     let mut no_sanitize_span = None;
2353     for attr in attrs.iter() {
2354         if attr.check_name(sym::cold) {
2355             codegen_fn_attrs.flags |= CodegenFnAttrFlags::COLD;
2356         } else if attr.check_name(sym::rustc_allocator) {
2357             codegen_fn_attrs.flags |= CodegenFnAttrFlags::ALLOCATOR;
2358         } else if attr.check_name(sym::unwind) {
2359             codegen_fn_attrs.flags |= CodegenFnAttrFlags::UNWIND;
2360         } else if attr.check_name(sym::ffi_returns_twice) {
2361             if tcx.is_foreign_item(id) {
2362                 codegen_fn_attrs.flags |= CodegenFnAttrFlags::FFI_RETURNS_TWICE;
2363             } else {
2364                 // `#[ffi_returns_twice]` is only allowed `extern fn`s.
2365                 struct_span_err!(
2366                     tcx.sess,
2367                     attr.span,
2368                     E0724,
2369                     "`#[ffi_returns_twice]` may only be used on foreign functions"
2370                 )
2371                 .emit();
2372             }
2373         } else if attr.check_name(sym::rustc_allocator_nounwind) {
2374             codegen_fn_attrs.flags |= CodegenFnAttrFlags::RUSTC_ALLOCATOR_NOUNWIND;
2375         } else if attr.check_name(sym::naked) {
2376             codegen_fn_attrs.flags |= CodegenFnAttrFlags::NAKED;
2377         } else if attr.check_name(sym::no_mangle) {
2378             codegen_fn_attrs.flags |= CodegenFnAttrFlags::NO_MANGLE;
2379         } else if attr.check_name(sym::rustc_std_internal_symbol) {
2380             codegen_fn_attrs.flags |= CodegenFnAttrFlags::RUSTC_STD_INTERNAL_SYMBOL;
2381         } else if attr.check_name(sym::used) {
2382             codegen_fn_attrs.flags |= CodegenFnAttrFlags::USED;
2383         } else if attr.check_name(sym::thread_local) {
2384             codegen_fn_attrs.flags |= CodegenFnAttrFlags::THREAD_LOCAL;
2385         } else if attr.check_name(sym::track_caller) {
2386             if tcx.is_closure(id) || tcx.fn_sig(id).abi() != abi::Abi::Rust {
2387                 struct_span_err!(tcx.sess, attr.span, E0737, "`#[track_caller]` requires Rust ABI")
2388                     .emit();
2389             }
2390             codegen_fn_attrs.flags |= CodegenFnAttrFlags::TRACK_CALLER;
2391         } else if attr.check_name(sym::export_name) {
2392             if let Some(s) = attr.value_str() {
2393                 if s.as_str().contains('\0') {
2394                     // `#[export_name = ...]` will be converted to a null-terminated string,
2395                     // so it may not contain any null characters.
2396                     struct_span_err!(
2397                         tcx.sess,
2398                         attr.span,
2399                         E0648,
2400                         "`export_name` may not contain null characters"
2401                     )
2402                     .emit();
2403                 }
2404                 codegen_fn_attrs.export_name = Some(s);
2405             }
2406         } else if attr.check_name(sym::target_feature) {
2407             if !tcx.features().target_feature_11 {
2408                 check_target_feature_safe_fn(tcx, id, attr.span);
2409             } else if let Some(local_id) = id.as_local() {
2410                 if tcx.fn_sig(id).unsafety() == hir::Unsafety::Normal {
2411                     check_target_feature_trait_unsafe(tcx, local_id, attr.span);
2412                 }
2413             }
2414             from_target_feature(tcx, id, attr, &whitelist, &mut codegen_fn_attrs.target_features);
2415         } else if attr.check_name(sym::linkage) {
2416             if let Some(val) = attr.value_str() {
2417                 codegen_fn_attrs.linkage = Some(linkage_by_name(tcx, id, &val.as_str()));
2418             }
2419         } else if attr.check_name(sym::link_section) {
2420             if let Some(val) = attr.value_str() {
2421                 if val.as_str().bytes().any(|b| b == 0) {
2422                     let msg = format!(
2423                         "illegal null byte in link_section \
2424                          value: `{}`",
2425                         &val
2426                     );
2427                     tcx.sess.span_err(attr.span, &msg);
2428                 } else {
2429                     codegen_fn_attrs.link_section = Some(val);
2430                 }
2431             }
2432         } else if attr.check_name(sym::link_name) {
2433             codegen_fn_attrs.link_name = attr.value_str();
2434         } else if attr.check_name(sym::link_ordinal) {
2435             link_ordinal_span = Some(attr.span);
2436             if let ordinal @ Some(_) = check_link_ordinal(tcx, attr) {
2437                 codegen_fn_attrs.link_ordinal = ordinal;
2438             }
2439         } else if attr.check_name(sym::no_sanitize) {
2440             no_sanitize_span = Some(attr.span);
2441             if let Some(list) = attr.meta_item_list() {
2442                 for item in list.iter() {
2443                     if item.check_name(sym::address) {
2444                         codegen_fn_attrs.flags |= CodegenFnAttrFlags::NO_SANITIZE_ADDRESS;
2445                     } else if item.check_name(sym::memory) {
2446                         codegen_fn_attrs.flags |= CodegenFnAttrFlags::NO_SANITIZE_MEMORY;
2447                     } else if item.check_name(sym::thread) {
2448                         codegen_fn_attrs.flags |= CodegenFnAttrFlags::NO_SANITIZE_THREAD;
2449                     } else {
2450                         tcx.sess
2451                             .struct_span_err(item.span(), "invalid argument for `no_sanitize`")
2452                             .note("expected one of: `address`, `memory` or `thread`")
2453                             .emit();
2454                     }
2455                 }
2456             }
2457         }
2458     }
2459
2460     codegen_fn_attrs.inline = attrs.iter().fold(InlineAttr::None, |ia, attr| {
2461         if !attr.has_name(sym::inline) {
2462             return ia;
2463         }
2464         match attr.meta().map(|i| i.kind) {
2465             Some(MetaItemKind::Word) => {
2466                 mark_used(attr);
2467                 InlineAttr::Hint
2468             }
2469             Some(MetaItemKind::List(ref items)) => {
2470                 mark_used(attr);
2471                 inline_span = Some(attr.span);
2472                 if items.len() != 1 {
2473                     struct_span_err!(
2474                         tcx.sess.diagnostic(),
2475                         attr.span,
2476                         E0534,
2477                         "expected one argument"
2478                     )
2479                     .emit();
2480                     InlineAttr::None
2481                 } else if list_contains_name(&items[..], sym::always) {
2482                     InlineAttr::Always
2483                 } else if list_contains_name(&items[..], sym::never) {
2484                     InlineAttr::Never
2485                 } else {
2486                     struct_span_err!(
2487                         tcx.sess.diagnostic(),
2488                         items[0].span(),
2489                         E0535,
2490                         "invalid argument"
2491                     )
2492                     .emit();
2493
2494                     InlineAttr::None
2495                 }
2496             }
2497             Some(MetaItemKind::NameValue(_)) => ia,
2498             None => ia,
2499         }
2500     });
2501
2502     codegen_fn_attrs.optimize = attrs.iter().fold(OptimizeAttr::None, |ia, attr| {
2503         if !attr.has_name(sym::optimize) {
2504             return ia;
2505         }
2506         let err = |sp, s| struct_span_err!(tcx.sess.diagnostic(), sp, E0722, "{}", s).emit();
2507         match attr.meta().map(|i| i.kind) {
2508             Some(MetaItemKind::Word) => {
2509                 err(attr.span, "expected one argument");
2510                 ia
2511             }
2512             Some(MetaItemKind::List(ref items)) => {
2513                 mark_used(attr);
2514                 inline_span = Some(attr.span);
2515                 if items.len() != 1 {
2516                     err(attr.span, "expected one argument");
2517                     OptimizeAttr::None
2518                 } else if list_contains_name(&items[..], sym::size) {
2519                     OptimizeAttr::Size
2520                 } else if list_contains_name(&items[..], sym::speed) {
2521                     OptimizeAttr::Speed
2522                 } else {
2523                     err(items[0].span(), "invalid argument");
2524                     OptimizeAttr::None
2525                 }
2526             }
2527             Some(MetaItemKind::NameValue(_)) => ia,
2528             None => ia,
2529         }
2530     });
2531
2532     // If a function uses #[target_feature] it can't be inlined into general
2533     // purpose functions as they wouldn't have the right target features
2534     // enabled. For that reason we also forbid #[inline(always)] as it can't be
2535     // respected.
2536     if !codegen_fn_attrs.target_features.is_empty() {
2537         if codegen_fn_attrs.inline == InlineAttr::Always {
2538             if let Some(span) = inline_span {
2539                 tcx.sess.span_err(
2540                     span,
2541                     "cannot use `#[inline(always)]` with \
2542                      `#[target_feature]`",
2543                 );
2544             }
2545         }
2546     }
2547
2548     if codegen_fn_attrs.flags.intersects(CodegenFnAttrFlags::NO_SANITIZE_ANY) {
2549         if codegen_fn_attrs.inline == InlineAttr::Always {
2550             if let (Some(no_sanitize_span), Some(inline_span)) = (no_sanitize_span, inline_span) {
2551                 let hir_id = tcx.hir().as_local_hir_id(id.expect_local());
2552                 tcx.struct_span_lint_hir(
2553                     lint::builtin::INLINE_NO_SANITIZE,
2554                     hir_id,
2555                     no_sanitize_span,
2556                     |lint| {
2557                         lint.build("`no_sanitize` will have no effect after inlining")
2558                             .span_note(inline_span, "inlining requested here")
2559                             .emit();
2560                     },
2561                 )
2562             }
2563         }
2564     }
2565
2566     // Weak lang items have the same semantics as "std internal" symbols in the
2567     // sense that they're preserved through all our LTO passes and only
2568     // strippable by the linker.
2569     //
2570     // Additionally weak lang items have predetermined symbol names.
2571     if tcx.is_weak_lang_item(id) {
2572         codegen_fn_attrs.flags |= CodegenFnAttrFlags::RUSTC_STD_INTERNAL_SYMBOL;
2573     }
2574     if let Some(name) = weak_lang_items::link_name(&attrs) {
2575         codegen_fn_attrs.export_name = Some(name);
2576         codegen_fn_attrs.link_name = Some(name);
2577     }
2578     check_link_name_xor_ordinal(tcx, &codegen_fn_attrs, link_ordinal_span);
2579
2580     // Internal symbols to the standard library all have no_mangle semantics in
2581     // that they have defined symbol names present in the function name. This
2582     // also applies to weak symbols where they all have known symbol names.
2583     if codegen_fn_attrs.flags.contains(CodegenFnAttrFlags::RUSTC_STD_INTERNAL_SYMBOL) {
2584         codegen_fn_attrs.flags |= CodegenFnAttrFlags::NO_MANGLE;
2585     }
2586
2587     codegen_fn_attrs
2588 }
2589
2590 /// Checks if the provided DefId is a method in a trait impl for a trait which has track_caller
2591 /// applied to the method prototype.
2592 fn should_inherit_track_caller(tcx: TyCtxt<'_>, def_id: DefId) -> bool {
2593     if let Some(impl_item) = tcx.opt_associated_item(def_id) {
2594         if let ty::AssocItemContainer::ImplContainer(impl_def_id) = impl_item.container {
2595             if let Some(trait_def_id) = tcx.trait_id_of_impl(impl_def_id) {
2596                 if let Some(trait_item) = tcx
2597                     .associated_items(trait_def_id)
2598                     .filter_by_name_unhygienic(impl_item.ident.name)
2599                     .find(move |trait_item| {
2600                         trait_item.kind == ty::AssocKind::Fn
2601                             && tcx.hygienic_eq(impl_item.ident, trait_item.ident, trait_def_id)
2602                     })
2603                 {
2604                     return tcx
2605                         .codegen_fn_attrs(trait_item.def_id)
2606                         .flags
2607                         .intersects(CodegenFnAttrFlags::TRACK_CALLER);
2608                 }
2609             }
2610         }
2611     }
2612
2613     false
2614 }
2615
2616 fn check_link_ordinal(tcx: TyCtxt<'_>, attr: &ast::Attribute) -> Option<usize> {
2617     use rustc_ast::ast::{Lit, LitIntType, LitKind};
2618     let meta_item_list = attr.meta_item_list();
2619     let meta_item_list: Option<&[ast::NestedMetaItem]> = meta_item_list.as_ref().map(Vec::as_ref);
2620     let sole_meta_list = match meta_item_list {
2621         Some([item]) => item.literal(),
2622         _ => None,
2623     };
2624     if let Some(Lit { kind: LitKind::Int(ordinal, LitIntType::Unsuffixed), .. }) = sole_meta_list {
2625         if *ordinal <= usize::MAX as u128 {
2626             Some(*ordinal as usize)
2627         } else {
2628             let msg = format!("ordinal value in `link_ordinal` is too large: `{}`", &ordinal);
2629             tcx.sess
2630                 .struct_span_err(attr.span, &msg)
2631                 .note("the value may not exceed `usize::MAX`")
2632                 .emit();
2633             None
2634         }
2635     } else {
2636         tcx.sess
2637             .struct_span_err(attr.span, "illegal ordinal format in `link_ordinal`")
2638             .note("an unsuffixed integer value, e.g., `1`, is expected")
2639             .emit();
2640         None
2641     }
2642 }
2643
2644 fn check_link_name_xor_ordinal(
2645     tcx: TyCtxt<'_>,
2646     codegen_fn_attrs: &CodegenFnAttrs,
2647     inline_span: Option<Span>,
2648 ) {
2649     if codegen_fn_attrs.link_name.is_none() || codegen_fn_attrs.link_ordinal.is_none() {
2650         return;
2651     }
2652     let msg = "cannot use `#[link_name]` with `#[link_ordinal]`";
2653     if let Some(span) = inline_span {
2654         tcx.sess.span_err(span, msg);
2655     } else {
2656         tcx.sess.err(msg);
2657     }
2658 }
2659
2660 /// Checks the function annotated with `#[target_feature]` is unsafe,
2661 /// reporting an error if it isn't.
2662 fn check_target_feature_safe_fn(tcx: TyCtxt<'_>, id: DefId, attr_span: Span) {
2663     if tcx.is_closure(id) || tcx.fn_sig(id).unsafety() == hir::Unsafety::Normal {
2664         let mut err = feature_err(
2665             &tcx.sess.parse_sess,
2666             sym::target_feature_11,
2667             attr_span,
2668             "`#[target_feature(..)]` can only be applied to `unsafe` functions",
2669         );
2670         err.span_label(tcx.def_span(id), "not an `unsafe` function");
2671         err.emit();
2672     }
2673 }
2674
2675 /// Checks the function annotated with `#[target_feature]` is not a safe
2676 /// trait method implementation, reporting an error if it is.
2677 fn check_target_feature_trait_unsafe(tcx: TyCtxt<'_>, id: LocalDefId, attr_span: Span) {
2678     let hir_id = tcx.hir().as_local_hir_id(id);
2679     let node = tcx.hir().get(hir_id);
2680     if let Node::ImplItem(hir::ImplItem { kind: hir::ImplItemKind::Fn(..), .. }) = node {
2681         let parent_id = tcx.hir().get_parent_item(hir_id);
2682         let parent_item = tcx.hir().expect_item(parent_id);
2683         if let hir::ItemKind::Impl { of_trait: Some(_), .. } = parent_item.kind {
2684             tcx.sess
2685                 .struct_span_err(
2686                     attr_span,
2687                     "`#[target_feature(..)]` cannot be applied to safe trait method",
2688                 )
2689                 .span_label(attr_span, "cannot be applied to safe trait method")
2690                 .span_label(tcx.def_span(id), "not an `unsafe` function")
2691                 .emit();
2692         }
2693     }
2694 }