src/librustc_typeck/collect.rs

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