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