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<'tcx>) {
 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<'tcx>) {
 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<'tcx>) {
 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 always when we get lazy normalization.
 913         Node::AnonConst(_) => {
 914             // HACK(eddyb) this provides the correct generics when
 915             // `feature(const_generics)` is enabled, so that const expressions
 916             // used with const generics, e.g. `Foo<{N+1}>`, can work at all.
 917             if tcx.features().const_generics {
 918                 let parent_id = tcx.hir().get_parent_item(hir_id);
 919                 Some(tcx.hir().local_def_id(parent_id))
 920             } else {
 921                 None
 922             }
 923         }
 924         Node::Expr(&hir::Expr {
 925             kind: hir::ExprKind::Closure(..),
 926             ..
 927         }) => Some(tcx.closure_base_def_id(def_id)),
 928         Node::Item(item) => match item.kind {
 929             ItemKind::OpaqueTy(hir::OpaqueTy { impl_trait_fn, .. }) => impl_trait_fn,
 930             _ => None,
 931         },
 932         _ => None,
 933     };
 934
 935     let mut opt_self = None;
 936     let mut allow_defaults = false;
 937
 938     let no_generics = hir::Generics::empty();
 939     let ast_generics = match node {
 940         Node::TraitItem(item) => &item.generics,
 941
 942         Node::ImplItem(item) => &item.generics,
 943
 944         Node::Item(item) => {
 945             match item.kind {
 946                 ItemKind::Fn(.., ref generics, _) | ItemKind::Impl(_, _, _, ref generics, ..) => {
 947                     generics
 948                 }
 949
 950                 ItemKind::TyAlias(_, ref generics)
 951                 | ItemKind::Enum(_, ref generics)
 952                 | ItemKind::Struct(_, ref generics)
 953                 | ItemKind::OpaqueTy(hir::OpaqueTy { ref generics, .. })
 954                 | ItemKind::Union(_, ref generics) => {
 955                     allow_defaults = true;
 956                     generics
 957                 }
 958
 959                 ItemKind::Trait(_, _, ref generics, ..)
 960                 | ItemKind::TraitAlias(ref generics, ..) => {
 961                     // Add in the self type parameter.
 962                     //
 963                     // Something of a hack: use the node id for the trait, also as
 964                     // the node id for the Self type parameter.
 965                     let param_id = item.hir_id;
 966
 967                     opt_self = Some(ty::GenericParamDef {
 968                         index: 0,
 969                         name: kw::SelfUpper,
 970                         def_id: tcx.hir().local_def_id(param_id),
 971                         pure_wrt_drop: false,
 972                         kind: ty::GenericParamDefKind::Type {
 973                             has_default: false,
 974                             object_lifetime_default: rl::Set1::Empty,
 975                             synthetic: None,
 976                         },
 977                     });
 978
 979                     allow_defaults = true;
 980                     generics
 981                 }
 982
 983                 _ => &no_generics,
 984             }
 985         }
 986
 987         Node::ForeignItem(item) => match item.kind {
 988             ForeignItemKind::Static(..) => &no_generics,
 989             ForeignItemKind::Fn(_, _, ref generics) => generics,
 990             ForeignItemKind::Type => &no_generics,
 991         },
 992
 993         _ => &no_generics,
 994     };
 995
 996     let has_self = opt_self.is_some();
 997     let mut parent_has_self = false;
 998     let mut own_start = has_self as u32;
 999     let parent_count = parent_def_id.map_or(0, |def_id| {
1000         let generics = tcx.generics_of(def_id);
1001         assert_eq!(has_self, false);
1002         parent_has_self = generics.has_self;
1003         own_start = generics.count() as u32;
1004         generics.parent_count + generics.params.len()
1005     });
1006
1007     let mut params: Vec<_> = opt_self.into_iter().collect();
1008
1009     let early_lifetimes = early_bound_lifetimes_from_generics(tcx, ast_generics);
1010     params.extend(
1011         early_lifetimes
1012             .enumerate()
1013             .map(|(i, param)| ty::GenericParamDef {
1014                 name: param.name.ident().name,
1015                 index: own_start + i as u32,
1016                 def_id: tcx.hir().local_def_id(param.hir_id),
1017                 pure_wrt_drop: param.pure_wrt_drop,
1018                 kind: ty::GenericParamDefKind::Lifetime,
1019             }),
1020     );
1021
1022     let object_lifetime_defaults = tcx.object_lifetime_defaults(hir_id);
1023
1024     // Now create the real type parameters.
1025     let type_start = own_start - has_self as u32 + params.len() as u32;
1026     let mut i = 0;
1027     params.extend(
1028         ast_generics
1029             .params
1030             .iter()
1031             .filter_map(|param| {
1032                 let kind = match param.kind {
1033                     GenericParamKind::Type {
1034                         ref default,
1035                         synthetic,
1036                         ..
1037                     } => {
1038                         if !allow_defaults && default.is_some() {
1039                             if !tcx.features().default_type_parameter_fallback {
1040                                 tcx.lint_hir(
1041                                     lint::builtin::INVALID_TYPE_PARAM_DEFAULT,
1042                                     param.hir_id,
1043                                     param.span,
1044                                     &format!(
1045                                         "defaults for type parameters are only allowed in \
1046                                         `struct`, `enum`, `type`, or `trait` definitions."
1047                                     ),
1048                                 );
1049                             }
1050                         }
1051
1052                         ty::GenericParamDefKind::Type {
1053                             has_default: default.is_some(),
1054                             object_lifetime_default: object_lifetime_defaults
1055                                 .as_ref()
1056                                 .map_or(rl::Set1::Empty, |o| o[i]),
1057                             synthetic,
1058                         }
1059                     }
1060                     GenericParamKind::Const { .. } => {
1061                         ty::GenericParamDefKind::Const
1062                     }
1063                     _ => return None,
1064                 };
1065
1066                 let param_def = ty::GenericParamDef {
1067                     index: type_start + i as u32,
1068                     name: param.name.ident().name,
1069                     def_id: tcx.hir().local_def_id(param.hir_id),
1070                     pure_wrt_drop: param.pure_wrt_drop,
1071                     kind,
1072                 };
1073                 i += 1;
1074                 Some(param_def)
1075             })
1076     );
1077
1078     // provide junk type parameter defs - the only place that
1079     // cares about anything but the length is instantiation,
1080     // and we don't do that for closures.
1081     if let Node::Expr(&hir::Expr {
1082         kind: hir::ExprKind::Closure(.., gen),
1083         ..
1084     }) = node
1085     {
1086         let dummy_args = if gen.is_some() {
1087             &["<yield_ty>", "<return_ty>", "<witness>"][..]
1088         } else {
1089             &["<closure_kind>", "<closure_signature>"][..]
1090         };
1091
1092         params.extend(
1093             dummy_args
1094                 .iter()
1095                 .enumerate()
1096                 .map(|(i, &arg)| ty::GenericParamDef {
1097                     index: type_start + i as u32,
1098                     name: Symbol::intern(arg),
1099                     def_id,
1100                     pure_wrt_drop: false,
1101                     kind: ty::GenericParamDefKind::Type {
1102                         has_default: false,
1103                         object_lifetime_default: rl::Set1::Empty,
1104                         synthetic: None,
1105                     },
1106                 }),
1107         );
1108
1109         if let Some(upvars) = tcx.upvars(def_id) {
1110             params.extend(upvars.iter().zip((dummy_args.len() as u32)..).map(|(_, i)| {
1111                 ty::GenericParamDef {
1112                     index: type_start + i,
1113                     name: Symbol::intern("<upvar>"),
1114                     def_id,
1115                     pure_wrt_drop: false,
1116                     kind: ty::GenericParamDefKind::Type {
1117                         has_default: false,
1118                         object_lifetime_default: rl::Set1::Empty,
1119                         synthetic: None,
1120                     },
1121                 }
1122             }));
1123         }
1124     }
1125
1126     let param_def_id_to_index = params
1127         .iter()
1128         .map(|param| (param.def_id, param.index))
1129         .collect();
1130
1131     tcx.arena.alloc(ty::Generics {
1132         parent: parent_def_id,
1133         parent_count,
1134         params,
1135         param_def_id_to_index,
1136         has_self: has_self || parent_has_self,
1137         has_late_bound_regions: has_late_bound_regions(tcx, node),
1138     })
1139 }
1140
1141 fn report_assoc_ty_on_inherent_impl(tcx: TyCtxt<'_>, span: Span) {
1142     span_err!(
1143         tcx.sess,
1144         span,
1145         E0202,
1146         "associated types are not yet supported in inherent impls (see #8995)"
1147     );
1148 }
1149
1150 fn infer_placeholder_type(
1151     tcx: TyCtxt<'_>,
1152     def_id: DefId,
1153     body_id: hir::BodyId,
1154     span: Span,
1155     item_ident: Ident,
1156 ) -> Ty<'_> {
1157     let ty = tcx.typeck_tables_of(def_id).node_type(body_id.hir_id);
1158
1159     // If this came from a free `const` or `static mut?` item,
1160     // then the user may have written e.g. `const A = 42;`.
1161     // In this case, the parser has stashed a diagnostic for
1162     // us to improve in typeck so we do that now.
1163     match tcx.sess.diagnostic().steal_diagnostic(span, StashKey::ItemNoType) {
1164         Some(mut err) => {
1165             // The parser provided a sub-optimal `HasPlaceholders` suggestion for the type.
1166             // We are typeck and have the real type, so remove that and suggest the actual type.
1167             err.suggestions.clear();
1168             err.span_suggestion(
1169                 span,
1170                 "provide a type for the item",
1171                 format!("{}: {}", item_ident, ty),
1172                 Applicability::MachineApplicable,
1173             )
1174             .emit();
1175         }
1176         None => {
1177             let mut diag = bad_placeholder_type(tcx, span);
1178             if ty != tcx.types.err {
1179                 diag.span_suggestion(
1180                     span,
1181                     "replace `_` with the correct type",
1182                     ty.to_string(),
1183                     Applicability::MaybeIncorrect,
1184                 );
1185             }
1186             diag.emit();
1187         }
1188     }
1189
1190     ty
1191 }
1192
1193 fn type_of(tcx: TyCtxt<'_>, def_id: DefId) -> Ty<'_> {
1194     use rustc::hir::*;
1195
1196     let hir_id = tcx.hir().as_local_hir_id(def_id).unwrap();
1197
1198     let icx = ItemCtxt::new(tcx, def_id);
1199
1200     match tcx.hir().get(hir_id) {
1201         Node::TraitItem(item) => match item.kind {
1202             TraitItemKind::Method(..) => {
1203                 let substs = InternalSubsts::identity_for_item(tcx, def_id);
1204                 tcx.mk_fn_def(def_id, substs)
1205             }
1206             TraitItemKind::Const(ref ty, body_id)  => {
1207                 body_id.and_then(|body_id| {
1208                     if let hir::TyKind::Infer = ty.kind {
1209                         Some(infer_placeholder_type(tcx, def_id, body_id, ty.span, item.ident))
1210                     } else {
1211                         None
1212                     }
1213                 }).unwrap_or_else(|| icx.to_ty(ty))
1214             },
1215             TraitItemKind::Type(_, Some(ref ty)) => icx.to_ty(ty),
1216             TraitItemKind::Type(_, None) => {
1217                 span_bug!(item.span, "associated type missing default");
1218             }
1219         },
1220
1221         Node::ImplItem(item) => match item.kind {
1222             ImplItemKind::Method(..) => {
1223                 let substs = InternalSubsts::identity_for_item(tcx, def_id);
1224                 tcx.mk_fn_def(def_id, substs)
1225             }
1226             ImplItemKind::Const(ref ty, body_id) => {
1227                 if let hir::TyKind::Infer = ty.kind {
1228                     infer_placeholder_type(tcx, def_id, body_id, ty.span, item.ident)
1229                 } else {
1230                     icx.to_ty(ty)
1231                 }
1232             },
1233             ImplItemKind::OpaqueTy(_) => {
1234                 if tcx
1235                     .impl_trait_ref(tcx.hir().get_parent_did(hir_id))
1236                     .is_none()
1237                 {
1238                     report_assoc_ty_on_inherent_impl(tcx, item.span);
1239                 }
1240
1241                 find_opaque_ty_constraints(tcx, def_id)
1242             }
1243             ImplItemKind::TyAlias(ref ty) => {
1244                 if tcx
1245                     .impl_trait_ref(tcx.hir().get_parent_did(hir_id))
1246                     .is_none()
1247                 {
1248                     report_assoc_ty_on_inherent_impl(tcx, item.span);
1249                 }
1250
1251                 icx.to_ty(ty)
1252             }
1253         },
1254
1255         Node::Item(item) => {
1256             match item.kind {
1257                 ItemKind::Static(ref ty, .., body_id)
1258                 | ItemKind::Const(ref ty, body_id) => {
1259                     if let hir::TyKind::Infer = ty.kind {
1260                         infer_placeholder_type(tcx, def_id, body_id, ty.span, item.ident)
1261                     } else {
1262                         icx.to_ty(ty)
1263                     }
1264                 },
1265                 ItemKind::TyAlias(ref ty, _)
1266                 | ItemKind::Impl(.., ref ty, _) => icx.to_ty(ty),
1267                 ItemKind::Fn(..) => {
1268                     let substs = InternalSubsts::identity_for_item(tcx, def_id);
1269                     tcx.mk_fn_def(def_id, substs)
1270                 }
1271                 ItemKind::Enum(..) | ItemKind::Struct(..) | ItemKind::Union(..) => {
1272                     let def = tcx.adt_def(def_id);
1273                     let substs = InternalSubsts::identity_for_item(tcx, def_id);
1274                     tcx.mk_adt(def, substs)
1275                 }
1276                 ItemKind::OpaqueTy(hir::OpaqueTy {
1277                     impl_trait_fn: None,
1278                     ..
1279                 }) => find_opaque_ty_constraints(tcx, def_id),
1280                 // Opaque types desugared from `impl Trait`.
1281                 ItemKind::OpaqueTy(hir::OpaqueTy {
1282                     impl_trait_fn: Some(owner),
1283                     ..
1284                 }) => {
1285                     tcx.typeck_tables_of(owner)
1286                         .concrete_opaque_types
1287                         .get(&def_id)
1288                         .map(|opaque| opaque.concrete_type)
1289                         .unwrap_or_else(|| {
1290                             // This can occur if some error in the
1291                             // owner fn prevented us from populating
1292                             // the `concrete_opaque_types` table.
1293                             tcx.sess.delay_span_bug(
1294                                 DUMMY_SP,
1295                                 &format!(
1296                                     "owner {:?} has no opaque type for {:?} in its tables",
1297                                     owner, def_id,
1298                                 ),
1299                             );
1300                             tcx.types.err
1301                         })
1302                 }
1303                 ItemKind::Trait(..)
1304                 | ItemKind::TraitAlias(..)
1305                 | ItemKind::Mod(..)
1306                 | ItemKind::ForeignMod(..)
1307                 | ItemKind::GlobalAsm(..)
1308                 | ItemKind::ExternCrate(..)
1309                 | ItemKind::Use(..) => {
1310                     span_bug!(
1311                         item.span,
1312                         "compute_type_of_item: unexpected item type: {:?}",
1313                         item.kind
1314                     );
1315                 }
1316             }
1317         }
1318
1319         Node::ForeignItem(foreign_item) => match foreign_item.kind {
1320             ForeignItemKind::Fn(..) => {
1321                 let substs = InternalSubsts::identity_for_item(tcx, def_id);
1322                 tcx.mk_fn_def(def_id, substs)
1323             }
1324             ForeignItemKind::Static(ref t, _) => icx.to_ty(t),
1325             ForeignItemKind::Type => tcx.mk_foreign(def_id),
1326         },
1327
1328         Node::Ctor(&ref def) | Node::Variant(
1329             hir::Variant { data: ref def, .. }
1330         ) => match *def {
1331             VariantData::Unit(..) | VariantData::Struct(..) => {
1332                 tcx.type_of(tcx.hir().get_parent_did(hir_id))
1333             }
1334             VariantData::Tuple(..) => {
1335                 let substs = InternalSubsts::identity_for_item(tcx, def_id);
1336                 tcx.mk_fn_def(def_id, substs)
1337             }
1338         },
1339
1340         Node::Field(field) => icx.to_ty(&field.ty),
1341
1342         Node::Expr(&hir::Expr {
1343             kind: hir::ExprKind::Closure(.., gen),
1344             ..
1345         }) => {
1346             if gen.is_some() {
1347                 return tcx.typeck_tables_of(def_id).node_type(hir_id);
1348             }
1349
1350             let substs = InternalSubsts::identity_for_item(tcx, def_id);
1351             tcx.mk_closure(def_id, substs)
1352         }
1353
1354         Node::AnonConst(_) => {
1355             let parent_node = tcx.hir().get(tcx.hir().get_parent_node(hir_id));
1356             match parent_node {
1357                 Node::Ty(&hir::Ty {
1358                     kind: hir::TyKind::Array(_, ref constant),
1359                     ..
1360                 })
1361                 | Node::Ty(&hir::Ty {
1362                     kind: hir::TyKind::Typeof(ref constant),
1363                     ..
1364                 })
1365                 | Node::Expr(&hir::Expr {
1366                     kind: ExprKind::Repeat(_, ref constant),
1367                     ..
1368                 }) if constant.hir_id == hir_id =>
1369                 {
1370                     tcx.types.usize
1371                 }
1372
1373                 Node::Variant(Variant {
1374                     disr_expr: Some(ref e),
1375                     ..
1376                 }) if e.hir_id == hir_id =>
1377                 {
1378                     tcx.adt_def(tcx.hir().get_parent_did(hir_id))
1379                         .repr
1380                         .discr_type()
1381                         .to_ty(tcx)
1382                 }
1383
1384                 Node::Ty(&hir::Ty { kind: hir::TyKind::Path(_), .. }) |
1385                 Node::Expr(&hir::Expr { kind: ExprKind::Struct(..), .. }) |
1386                 Node::Expr(&hir::Expr { kind: ExprKind::Path(_), .. }) |
1387                 Node::TraitRef(..) => {
1388                     let path = match parent_node {
1389                         Node::Ty(&hir::Ty {
1390                             kind: hir::TyKind::Path(QPath::Resolved(_, ref path)),
1391                             ..
1392                         })
1393                         | Node::Expr(&hir::Expr {
1394                             kind: ExprKind::Path(QPath::Resolved(_, ref path)),
1395                             ..
1396                         }) => {
1397                             Some(&**path)
1398                         }
1399                         Node::Expr(&hir::Expr { kind: ExprKind::Struct(ref path, ..), .. }) => {
1400                             if let QPath::Resolved(_, ref path) = **path {
1401                                 Some(&**path)
1402                             } else {
1403                                 None
1404                             }
1405                         }
1406                         Node::TraitRef(&hir::TraitRef { ref path, .. }) => Some(&**path),
1407                         _ => None,
1408                     };
1409
1410                     if let Some(path) = path {
1411                         let arg_index = path.segments.iter()
1412                             .filter_map(|seg| seg.args.as_ref())
1413                             .map(|generic_args| generic_args.args.as_ref())
1414                             .find_map(|args| {
1415                                 args.iter()
1416                                     .filter(|arg| arg.is_const())
1417                                     .enumerate()
1418                                     .filter(|(_, arg)| arg.id() == hir_id)
1419                                     .map(|(index, _)| index)
1420                                     .next()
1421                             })
1422                             .unwrap_or_else(|| {
1423                                 bug!("no arg matching AnonConst in path");
1424                             });
1425
1426                         // We've encountered an `AnonConst` in some path, so we need to
1427                         // figure out which generic parameter it corresponds to and return
1428                         // the relevant type.
1429                         let generics = match path.res {
1430                             Res::Def(DefKind::Ctor(..), def_id) => {
1431                                 tcx.generics_of(tcx.parent(def_id).unwrap())
1432                             }
1433                             Res::Def(_, def_id) => tcx.generics_of(def_id),
1434                             Res::Err => return tcx.types.err,
1435                             res => {
1436                                 tcx.sess.delay_span_bug(
1437                                     DUMMY_SP,
1438                                     &format!(
1439                                         "unexpected const parent path def {:?}",
1440                                         res,
1441                                     ),
1442                                 );
1443                                 return tcx.types.err;
1444                             }
1445                         };
1446
1447                         generics.params.iter()
1448                             .filter(|param| {
1449                                 if let ty::GenericParamDefKind::Const = param.kind {
1450                                     true
1451                                 } else {
1452                                     false
1453                                 }
1454                             })
1455                             .nth(arg_index)
1456                             .map(|param| tcx.type_of(param.def_id))
1457                             // This is no generic parameter associated with the arg. This is
1458                             // probably from an extra arg where one is not needed.
1459                             .unwrap_or(tcx.types.err)
1460                     } else {
1461                         tcx.sess.delay_span_bug(
1462                             DUMMY_SP,
1463                             &format!(
1464                                 "unexpected const parent path {:?}",
1465                                 parent_node,
1466                             ),
1467                         );
1468                         return tcx.types.err;
1469                     }
1470                 }
1471
1472                 x => {
1473                     tcx.sess.delay_span_bug(
1474                         DUMMY_SP,
1475                         &format!(
1476                             "unexpected const parent in type_of_def_id(): {:?}", x
1477                         ),
1478                     );
1479                     tcx.types.err
1480                 }
1481             }
1482         }
1483
1484         Node::GenericParam(param) => match &param.kind {
1485             hir::GenericParamKind::Type { default: Some(ref ty), .. } => icx.to_ty(ty),
1486             hir::GenericParamKind::Const { ty: ref hir_ty, .. } => {
1487                 let ty = icx.to_ty(hir_ty);
1488                 if !tcx.features().const_compare_raw_pointers {
1489                     let err = match ty.peel_refs().kind {
1490                         ty::FnPtr(_) => Some("function pointers"),
1491                         ty::RawPtr(_) => Some("raw pointers"),
1492                         _ => None,
1493                     };
1494                     if let Some(unsupported_type) = err {
1495                         feature_gate::feature_err(
1496                             &tcx.sess.parse_sess,
1497                             sym::const_compare_raw_pointers,
1498                             hir_ty.span,
1499                             &format!(
1500                                 "using {} as const generic parameters is unstable",
1501                                 unsupported_type
1502                             ),
1503                         )
1504                         .emit();
1505                     };
1506                 }
1507                 if ty::search_for_structural_match_violation(
1508                     param.hir_id, param.span, tcx, ty).is_some()
1509                 {
1510                     struct_span_err!(
1511                         tcx.sess,
1512                         hir_ty.span,
1513                         E0741,
1514                         "the types of const generic parameters must derive `PartialEq` and `Eq`",
1515                     ).span_label(
1516                         hir_ty.span,
1517                         format!("`{}` doesn't derive both `PartialEq` and `Eq`", ty),
1518                     ).emit();
1519                 }
1520                 ty
1521             }
1522             x => bug!("unexpected non-type Node::GenericParam: {:?}", x),
1523         },
1524
1525         x => {
1526             bug!("unexpected sort of node in type_of_def_id(): {:?}", x);
1527         }
1528     }
1529 }
1530
1531 fn find_opaque_ty_constraints(tcx: TyCtxt<'_>, def_id: DefId) -> Ty<'_> {
1532     use rustc::hir::{ImplItem, Item, TraitItem};
1533
1534     debug!("find_opaque_ty_constraints({:?})", def_id);
1535
1536     struct ConstraintLocator<'tcx> {
1537         tcx: TyCtxt<'tcx>,
1538         def_id: DefId,
1539         // (first found type span, actual type, mapping from the opaque type's generic
1540         // parameters to the concrete type's generic parameters)
1541         //
1542         // The mapping is an index for each use site of a generic parameter in the concrete type
1543         //
1544         // The indices index into the generic parameters on the opaque type.
1545         found: Option<(Span, Ty<'tcx>, Vec<usize>)>,
1546     }
1547
1548     impl ConstraintLocator<'tcx> {
1549         fn check(&mut self, def_id: DefId) {
1550             // Don't try to check items that cannot possibly constrain the type.
1551             if !self.tcx.has_typeck_tables(def_id) {
1552                 debug!(
1553                     "find_opaque_ty_constraints: no constraint for `{:?}` at `{:?}`: no tables",
1554                     self.def_id,
1555                     def_id,
1556                 );
1557                 return;
1558             }
1559             let ty = self
1560                 .tcx
1561                 .typeck_tables_of(def_id)
1562                 .concrete_opaque_types
1563                 .get(&self.def_id);
1564             if let Some(ty::ResolvedOpaqueTy { concrete_type, substs }) = ty {
1565                 debug!(
1566                     "find_opaque_ty_constraints: found constraint for `{:?}` at `{:?}`: {:?}",
1567                     self.def_id,
1568                     def_id,
1569                     ty,
1570                 );
1571
1572                 // FIXME(oli-obk): trace the actual span from inference to improve errors.
1573                 let span = self.tcx.def_span(def_id);
1574                 // used to quickly look up the position of a generic parameter
1575                 let mut index_map: FxHashMap<ty::ParamTy, usize> = FxHashMap::default();
1576                 // Skipping binder is ok, since we only use this to find generic parameters and
1577                 // their positions.
1578                 for (idx, subst) in substs.iter().enumerate() {
1579                     if let GenericArgKind::Type(ty) = subst.unpack() {
1580                         if let ty::Param(p) = ty.kind {
1581                             if index_map.insert(p, idx).is_some() {
1582                                 // There was already an entry for `p`, meaning a generic parameter
1583                                 // was used twice.
1584                                 self.tcx.sess.span_err(
1585                                     span,
1586                                     &format!(
1587                                         "defining opaque type use restricts opaque \
1588                                          type by using the generic parameter `{}` twice",
1589                                         p,
1590                                     ),
1591                                 );
1592                                 return;
1593                             }
1594                         } else {
1595                             self.tcx.sess.delay_span_bug(
1596                                 span,
1597                                 &format!(
1598                                     "non-defining opaque ty use in defining scope: {:?}, {:?}",
1599                                     concrete_type, substs,
1600                                 ),
1601                             );
1602                         }
1603                     }
1604                 }
1605                 // Compute the index within the opaque type for each generic parameter used in
1606                 // the concrete type.
1607                 let indices = concrete_type
1608                     .subst(self.tcx, substs)
1609                     .walk()
1610                     .filter_map(|t| match &t.kind {
1611                         ty::Param(p) => Some(*index_map.get(p).unwrap()),
1612                         _ => None,
1613                     }).collect();
1614                 let is_param = |ty: Ty<'_>| match ty.kind {
1615                     ty::Param(_) => true,
1616                     _ => false,
1617                 };
1618                 let bad_substs: Vec<_> = substs.types().enumerate()
1619                     .filter(|(_, ty)| !is_param(ty)).collect();
1620                 if !bad_substs.is_empty() {
1621                     let identity_substs = InternalSubsts::identity_for_item(self.tcx, self.def_id);
1622                     for (i, bad_subst) in bad_substs {
1623                         self.tcx.sess.span_err(
1624                             span,
1625                             &format!("defining opaque type use does not fully define opaque type: \
1626                             generic parameter `{}` is specified as concrete type `{}`",
1627                             identity_substs.type_at(i), bad_subst)
1628                         );
1629                     }
1630                 } else if let Some((prev_span, prev_ty, ref prev_indices)) = self.found {
1631                     let mut ty = concrete_type.walk().fuse();
1632                     let mut p_ty = prev_ty.walk().fuse();
1633                     let iter_eq = (&mut ty).zip(&mut p_ty).all(|(t, p)| match (&t.kind, &p.kind) {
1634                         // Type parameters are equal to any other type parameter for the purpose of
1635                         // concrete type equality, as it is possible to obtain the same type just
1636                         // by passing matching parameters to a function.
1637                         (ty::Param(_), ty::Param(_)) => true,
1638                         _ => t == p,
1639                     });
1640                     if !iter_eq || ty.next().is_some() || p_ty.next().is_some() {
1641                         debug!("find_opaque_ty_constraints: span={:?}", span);
1642                         // Found different concrete types for the opaque type.
1643                         let mut err = self.tcx.sess.struct_span_err(
1644                             span,
1645                             "concrete type differs from previous defining opaque type use",
1646                         );
1647                         err.span_label(
1648                             span,
1649                             format!("expected `{}`, got `{}`", prev_ty, concrete_type),
1650                         );
1651                         err.span_note(prev_span, "previous use here");
1652                         err.emit();
1653                     } else if indices != *prev_indices {
1654                         // Found "same" concrete types, but the generic parameter order differs.
1655                         let mut err = self.tcx.sess.struct_span_err(
1656                             span,
1657                             "concrete type's generic parameters differ from previous defining use",
1658                         );
1659                         use std::fmt::Write;
1660                         let mut s = String::new();
1661                         write!(s, "expected [").unwrap();
1662                         let list = |s: &mut String, indices: &Vec<usize>| {
1663                             let mut indices = indices.iter().cloned();
1664                             if let Some(first) = indices.next() {
1665                                 write!(s, "`{}`", substs[first]).unwrap();
1666                                 for i in indices {
1667                                     write!(s, ", `{}`", substs[i]).unwrap();
1668                                 }
1669                             }
1670                         };
1671                         list(&mut s, prev_indices);
1672                         write!(s, "], got [").unwrap();
1673                         list(&mut s, &indices);
1674                         write!(s, "]").unwrap();
1675                         err.span_label(span, s);
1676                         err.span_note(prev_span, "previous use here");
1677                         err.emit();
1678                     }
1679                 } else {
1680                     self.found = Some((span, concrete_type, indices));
1681                 }
1682             } else {
1683                 debug!(
1684                     "find_opaque_ty_constraints: no constraint for `{:?}` at `{:?}`",
1685                     self.def_id,
1686                     def_id,
1687                 );
1688             }
1689         }
1690     }
1691
1692     impl<'tcx> intravisit::Visitor<'tcx> for ConstraintLocator<'tcx> {
1693         fn nested_visit_map<'this>(&'this mut self) -> intravisit::NestedVisitorMap<'this, 'tcx> {
1694             intravisit::NestedVisitorMap::All(&self.tcx.hir())
1695         }
1696         fn visit_item(&mut self, it: &'tcx Item<'tcx>) {
1697             debug!("find_existential_constraints: visiting {:?}", it);
1698             let def_id = self.tcx.hir().local_def_id(it.hir_id);
1699             // The opaque type itself or its children are not within its reveal scope.
1700             if def_id != self.def_id {
1701                 self.check(def_id);
1702                 intravisit::walk_item(self, it);
1703             }
1704         }
1705         fn visit_impl_item(&mut self, it: &'tcx ImplItem<'tcx>) {
1706             debug!("find_existential_constraints: visiting {:?}", it);
1707             let def_id = self.tcx.hir().local_def_id(it.hir_id);
1708             // The opaque type itself or its children are not within its reveal scope.
1709             if def_id != self.def_id {
1710                 self.check(def_id);
1711                 intravisit::walk_impl_item(self, it);
1712             }
1713         }
1714         fn visit_trait_item(&mut self, it: &'tcx TraitItem<'tcx>) {
1715             debug!("find_existential_constraints: visiting {:?}", it);
1716             let def_id = self.tcx.hir().local_def_id(it.hir_id);
1717             self.check(def_id);
1718             intravisit::walk_trait_item(self, it);
1719         }
1720     }
1721
1722     let hir_id = tcx.hir().as_local_hir_id(def_id).unwrap();
1723     let scope = tcx.hir().get_defining_scope(hir_id);
1724     let mut locator = ConstraintLocator {
1725         def_id,
1726         tcx,
1727         found: None,
1728     };
1729
1730     debug!("find_opaque_ty_constraints: scope={:?}", scope);
1731
1732     if scope == hir::CRATE_HIR_ID {
1733         intravisit::walk_crate(&mut locator, tcx.hir().krate());
1734     } else {
1735         debug!("find_opaque_ty_constraints: scope={:?}", tcx.hir().get(scope));
1736         match tcx.hir().get(scope) {
1737             // We explicitly call `visit_*` methods, instead of using `intravisit::walk_*` methods
1738             // This allows our visitor to process the defining item itself, causing
1739             // it to pick up any 'sibling' defining uses.
1740             //
1741             // For example, this code:
1742             // ```
1743             // fn foo() {
1744             //     type Blah = impl Debug;
1745             //     let my_closure = || -> Blah { true };
1746             // }
1747             // ```
1748             //
1749             // requires us to explicitly process `foo()` in order
1750             // to notice the defining usage of `Blah`.
1751             Node::Item(ref it) => locator.visit_item(it),
1752             Node::ImplItem(ref it) => locator.visit_impl_item(it),
1753             Node::TraitItem(ref it) => locator.visit_trait_item(it),
1754             other => bug!(
1755                 "{:?} is not a valid scope for an opaque type item",
1756                 other
1757             ),
1758         }
1759     }
1760
1761     match locator.found {
1762         Some((_, ty, _)) => ty,
1763         None => {
1764             let span = tcx.def_span(def_id);
1765             tcx.sess.span_err(span, "could not find defining uses");
1766             tcx.types.err
1767         }
1768     }
1769 }
1770
1771 pub fn get_infer_ret_ty(output: &'_ hir::FunctionRetTy) -> Option<&hir::Ty> {
1772     if let hir::FunctionRetTy::Return(ref ty) = output {
1773         if let hir::TyKind::Infer = ty.kind {
1774             return Some(&**ty)
1775         }
1776     }
1777     None
1778 }
1779
1780 fn fn_sig(tcx: TyCtxt<'_>, def_id: DefId) -> ty::PolyFnSig<'_> {
1781     use rustc::hir::*;
1782     use rustc::hir::Node::*;
1783
1784     let hir_id = tcx.hir().as_local_hir_id(def_id).unwrap();
1785
1786     let icx = ItemCtxt::new(tcx, def_id);
1787
1788     match tcx.hir().get(hir_id) {
1789         TraitItem(hir::TraitItem {
1790             kind: TraitItemKind::Method(sig, TraitMethod::Provided(_)),
1791             ..
1792         })
1793         | ImplItem(hir::ImplItem {
1794             kind: ImplItemKind::Method(sig, _),
1795             ..
1796         })
1797         | Item(hir::Item {
1798             kind: ItemKind::Fn(sig, _, _),
1799             ..
1800         }) => match get_infer_ret_ty(&sig.decl.output) {
1801             Some(ty) => {
1802                 let fn_sig = tcx.typeck_tables_of(def_id).liberated_fn_sigs()[hir_id];
1803                 let mut diag = bad_placeholder_type(tcx, ty.span);
1804                 let ret_ty = fn_sig.output();
1805                 if ret_ty != tcx.types.err  {
1806                     diag.span_suggestion(
1807                         ty.span,
1808                         "replace `_` with the correct return type",
1809                         ret_ty.to_string(),
1810                         Applicability::MaybeIncorrect,
1811                     );
1812                 }
1813                 diag.emit();
1814                 ty::Binder::bind(fn_sig)
1815             },
1816             None => AstConv::ty_of_fn(&icx, sig.header.unsafety, sig.header.abi, &sig.decl)
1817         },
1818
1819         TraitItem(hir::TraitItem {
1820             kind: TraitItemKind::Method(FnSig { header, decl }, _),
1821             ..
1822         }) => {
1823             AstConv::ty_of_fn(&icx, header.unsafety, header.abi, decl)
1824         },
1825
1826         ForeignItem(&hir::ForeignItem {
1827             kind: ForeignItemKind::Fn(ref fn_decl, _, _),
1828             ..
1829         }) => {
1830             let abi = tcx.hir().get_foreign_abi(hir_id);
1831             compute_sig_of_foreign_fn_decl(tcx, def_id, fn_decl, abi)
1832         }
1833
1834         Ctor(data) | Variant(
1835             hir::Variant { data, ..  }
1836         ) if data.ctor_hir_id().is_some() => {
1837             let ty = tcx.type_of(tcx.hir().get_parent_did(hir_id));
1838             let inputs = data.fields()
1839                 .iter()
1840                 .map(|f| tcx.type_of(tcx.hir().local_def_id(f.hir_id)));
1841             ty::Binder::bind(tcx.mk_fn_sig(
1842                 inputs,
1843                 ty,
1844                 false,
1845                 hir::Unsafety::Normal,
1846                 abi::Abi::Rust,
1847             ))
1848         }
1849
1850         Expr(&hir::Expr {
1851             kind: hir::ExprKind::Closure(..),
1852             ..
1853         }) => {
1854             // Closure signatures are not like other function
1855             // signatures and cannot be accessed through `fn_sig`. For
1856             // example, a closure signature excludes the `self`
1857             // argument. In any case they are embedded within the
1858             // closure type as part of the `ClosureSubsts`.
1859             //
1860             // To get
1861             // the signature of a closure, you should use the
1862             // `closure_sig` method on the `ClosureSubsts`:
1863             //
1864             //    closure_substs.sig(def_id, tcx)
1865             //
1866             // or, inside of an inference context, you can use
1867             //
1868             //    infcx.closure_sig(def_id, closure_substs)
1869             bug!("to get the signature of a closure, use `closure_sig()` not `fn_sig()`");
1870         }
1871
1872         x => {
1873             bug!("unexpected sort of node in fn_sig(): {:?}", x);
1874         }
1875     }
1876 }
1877
1878 fn impl_trait_ref(tcx: TyCtxt<'_>, def_id: DefId) -> Option<ty::TraitRef<'_>> {
1879     let icx = ItemCtxt::new(tcx, def_id);
1880
1881     let hir_id = tcx.hir().as_local_hir_id(def_id).unwrap();
1882     match tcx.hir().expect_item(hir_id).kind {
1883         hir::ItemKind::Impl(.., ref opt_trait_ref, _, _) => {
1884             opt_trait_ref.as_ref().map(|ast_trait_ref| {
1885                 let selfty = tcx.type_of(def_id);
1886                 AstConv::instantiate_mono_trait_ref(&icx, ast_trait_ref, selfty)
1887             })
1888         }
1889         _ => bug!(),
1890     }
1891 }
1892
1893 fn impl_polarity(tcx: TyCtxt<'_>, def_id: DefId) -> ty::ImplPolarity {
1894     let hir_id = tcx.hir().as_local_hir_id(def_id).unwrap();
1895     let is_rustc_reservation = tcx.has_attr(def_id, sym::rustc_reservation_impl);
1896     let item = tcx.hir().expect_item(hir_id);
1897     match &item.kind {
1898         hir::ItemKind::Impl(_, hir::ImplPolarity::Negative, ..) => {
1899             if is_rustc_reservation {
1900                 tcx.sess.span_err(item.span, "reservation impls can't be negative");
1901             }
1902             ty::ImplPolarity::Negative
1903         }
1904         hir::ItemKind::Impl(_, hir::ImplPolarity::Positive, _, _, None, _, _) => {
1905             if is_rustc_reservation {
1906                 tcx.sess.span_err(item.span, "reservation impls can't be inherent");
1907             }
1908             ty::ImplPolarity::Positive
1909         }
1910         hir::ItemKind::Impl(_, hir::ImplPolarity::Positive, _, _, Some(_tr), _, _) => {
1911             if is_rustc_reservation {
1912                 ty::ImplPolarity::Reservation
1913             } else {
1914                 ty::ImplPolarity::Positive
1915             }
1916         }
1917         ref item => bug!("impl_polarity: {:?} not an impl", item),
1918     }
1919 }
1920
1921 /// Returns the early-bound lifetimes declared in this generics
1922 /// listing. For anything other than fns/methods, this is just all
1923 /// the lifetimes that are declared. For fns or methods, we have to
1924 /// screen out those that do not appear in any where-clauses etc using
1925 /// `resolve_lifetime::early_bound_lifetimes`.
1926 fn early_bound_lifetimes_from_generics<'a, 'tcx: 'a>(
1927     tcx: TyCtxt<'tcx>,
1928     generics: &'a hir::Generics,
1929 ) -> impl Iterator<Item = &'a hir::GenericParam> + Captures<'tcx> {
1930     generics
1931         .params
1932         .iter()
1933         .filter(move |param| match param.kind {
1934             GenericParamKind::Lifetime { .. } => {
1935                 !tcx.is_late_bound(param.hir_id)
1936             }
1937             _ => false,
1938         })
1939 }
1940
1941 /// Returns a list of type predicates for the definition with ID `def_id`, including inferred
1942 /// lifetime constraints. This includes all predicates returned by `explicit_predicates_of`, plus
1943 /// inferred constraints concerning which regions outlive other regions.
1944 fn predicates_defined_on(
1945     tcx: TyCtxt<'_>,
1946     def_id: DefId,
1947 ) -> ty::GenericPredicates<'_> {
1948     debug!("predicates_defined_on({:?})", def_id);
1949     let mut result = tcx.explicit_predicates_of(def_id);
1950     debug!(
1951         "predicates_defined_on: explicit_predicates_of({:?}) = {:?}",
1952         def_id,
1953         result,
1954     );
1955     let inferred_outlives = tcx.inferred_outlives_of(def_id);
1956     if !inferred_outlives.is_empty() {
1957         debug!(
1958             "predicates_defined_on: inferred_outlives_of({:?}) = {:?}",
1959             def_id,
1960             inferred_outlives,
1961         );
1962         if result.predicates.is_empty() {
1963             result.predicates = inferred_outlives;
1964         } else {
1965             result.predicates = tcx.arena.alloc_from_iter(
1966                 result.predicates.iter().chain(inferred_outlives).copied(),
1967             );
1968         }
1969     }
1970     debug!("predicates_defined_on({:?}) = {:?}", def_id, result);
1971     result
1972 }
1973
1974 /// Returns a list of all type predicates (explicit and implicit) for the definition with
1975 /// ID `def_id`. This includes all predicates returned by `predicates_defined_on`, plus
1976 /// `Self: Trait` predicates for traits.
1977 fn predicates_of(tcx: TyCtxt<'_>, def_id: DefId) -> ty::GenericPredicates<'_> {
1978     let mut result = tcx.predicates_defined_on(def_id);
1979
1980     if tcx.is_trait(def_id) {
1981         // For traits, add `Self: Trait` predicate. This is
1982         // not part of the predicates that a user writes, but it
1983         // is something that one must prove in order to invoke a
1984         // method or project an associated type.
1985         //
1986         // In the chalk setup, this predicate is not part of the
1987         // "predicates" for a trait item. But it is useful in
1988         // rustc because if you directly (e.g.) invoke a trait
1989         // method like `Trait::method(...)`, you must naturally
1990         // prove that the trait applies to the types that were
1991         // used, and adding the predicate into this list ensures
1992         // that this is done.
1993         let span = tcx.def_span(def_id);
1994         result.predicates = tcx.arena.alloc_from_iter(
1995             result.predicates.iter().copied().chain(
1996                 std::iter::once((ty::TraitRef::identity(tcx, def_id).to_predicate(), span))
1997             ),
1998         );
1999     }
2000     debug!("predicates_of(def_id={:?}) = {:?}", def_id, result);
2001     result
2002 }
2003
2004 /// Returns a list of user-specified type predicates for the definition with ID `def_id`.
2005 /// N.B., this does not include any implied/inferred constraints.
2006 fn explicit_predicates_of(
2007     tcx: TyCtxt<'_>,
2008     def_id: DefId,
2009 ) -> ty::GenericPredicates<'_> {
2010     use rustc::hir::*;
2011     use rustc_data_structures::fx::FxHashSet;
2012
2013     debug!("explicit_predicates_of(def_id={:?})", def_id);
2014
2015     /// A data structure with unique elements, which preserves order of insertion.
2016     /// Preserving the order of insertion is important here so as not to break
2017     /// compile-fail UI tests.
2018     // FIXME(eddyb) just use `IndexSet` from `indexmap`.
2019     struct UniquePredicates<'tcx> {
2020         predicates: Vec<(ty::Predicate<'tcx>, Span)>,
2021         uniques: FxHashSet<(ty::Predicate<'tcx>, Span)>,
2022     }
2023
2024     impl<'tcx> UniquePredicates<'tcx> {
2025         fn new() -> Self {
2026             UniquePredicates {
2027                 predicates: vec![],
2028                 uniques: FxHashSet::default(),
2029             }
2030         }
2031
2032         fn push(&mut self, value: (ty::Predicate<'tcx>, Span)) {
2033             if self.uniques.insert(value) {
2034                 self.predicates.push(value);
2035             }
2036         }
2037
2038         fn extend<I: IntoIterator<Item = (ty::Predicate<'tcx>, Span)>>(&mut self, iter: I) {
2039             for value in iter {
2040                 self.push(value);
2041             }
2042         }
2043     }
2044
2045     let hir_id = tcx.hir().as_local_hir_id(def_id).unwrap();
2046     let node = tcx.hir().get(hir_id);
2047
2048     let mut is_trait = None;
2049     let mut is_default_impl_trait = None;
2050
2051     let icx = ItemCtxt::new(tcx, def_id);
2052
2053     const NO_GENERICS: &hir::Generics = &hir::Generics::empty();
2054
2055     let mut predicates = UniquePredicates::new();
2056
2057     let ast_generics = match node {
2058         Node::TraitItem(item) => &item.generics,
2059
2060         Node::ImplItem(item) => match item.kind {
2061             ImplItemKind::OpaqueTy(ref bounds) => {
2062                 ty::print::with_no_queries(|| {
2063                     let substs = InternalSubsts::identity_for_item(tcx, def_id);
2064                     let opaque_ty = tcx.mk_opaque(def_id, substs);
2065                     debug!("explicit_predicates_of({:?}): created opaque type {:?}",
2066                         def_id, opaque_ty);
2067
2068
2069                     // Collect the bounds, i.e., the `A + B + 'c` in `impl A + B + 'c`.
2070                     let bounds = AstConv::compute_bounds(
2071                         &icx,
2072                         opaque_ty,
2073                         bounds,
2074                         SizedByDefault::Yes,
2075                         tcx.def_span(def_id),
2076                     );
2077
2078                     predicates.extend(bounds.predicates(tcx, opaque_ty));
2079                     &item.generics
2080                 })
2081             }
2082             _ => &item.generics,
2083         },
2084
2085         Node::Item(item) => {
2086             match item.kind {
2087                 ItemKind::Impl(_, _, defaultness, ref generics, ..) => {
2088                     if defaultness.is_default() {
2089                         is_default_impl_trait = tcx.impl_trait_ref(def_id);
2090                     }
2091                     generics
2092                 }
2093                 ItemKind::Fn(.., ref generics, _)
2094                 | ItemKind::TyAlias(_, ref generics)
2095                 | ItemKind::Enum(_, ref generics)
2096                 | ItemKind::Struct(_, ref generics)
2097                 | ItemKind::Union(_, ref generics) => generics,
2098
2099                 ItemKind::Trait(_, _, ref generics, .., items) => {
2100                     is_trait = Some((ty::TraitRef::identity(tcx, def_id), items));
2101                     generics
2102                 }
2103                 ItemKind::TraitAlias(ref generics, _) => {
2104                     is_trait = Some((ty::TraitRef::identity(tcx, def_id), &[]));
2105                     generics
2106                 }
2107                 ItemKind::OpaqueTy(OpaqueTy {
2108                     ref bounds,
2109                     impl_trait_fn,
2110                     ref generics,
2111                     origin: _,
2112                 }) => {
2113                     let bounds_predicates = ty::print::with_no_queries(|| {
2114                         let substs = InternalSubsts::identity_for_item(tcx, def_id);
2115                         let opaque_ty = tcx.mk_opaque(def_id, substs);
2116
2117                         // Collect the bounds, i.e., the `A + B + 'c` in `impl A + B + 'c`.
2118                         let bounds = AstConv::compute_bounds(
2119                             &icx,
2120                             opaque_ty,
2121                             bounds,
2122                             SizedByDefault::Yes,
2123                             tcx.def_span(def_id),
2124                         );
2125
2126                         bounds.predicates(tcx, opaque_ty)
2127                     });
2128                     if impl_trait_fn.is_some() {
2129                         // opaque types
2130                         return ty::GenericPredicates {
2131                             parent: None,
2132                             predicates: tcx.arena.alloc_from_iter(bounds_predicates),
2133                         };
2134                     } else {
2135                         // named opaque types
2136                         predicates.extend(bounds_predicates);
2137                         generics
2138                     }
2139                 }
2140
2141                 _ => NO_GENERICS,
2142             }
2143         }
2144
2145         Node::ForeignItem(item) => match item.kind {
2146             ForeignItemKind::Static(..) => NO_GENERICS,
2147             ForeignItemKind::Fn(_, _, ref generics) => generics,
2148             ForeignItemKind::Type => NO_GENERICS,
2149         },
2150
2151         _ => NO_GENERICS,
2152     };
2153
2154     let generics = tcx.generics_of(def_id);
2155     let parent_count = generics.parent_count as u32;
2156     let has_own_self = generics.has_self && parent_count == 0;
2157
2158     // Below we'll consider the bounds on the type parameters (including `Self`)
2159     // and the explicit where-clauses, but to get the full set of predicates
2160     // on a trait we need to add in the supertrait bounds and bounds found on
2161     // associated types.
2162     if let Some((_trait_ref, _)) = is_trait {
2163         predicates.extend(tcx.super_predicates_of(def_id).predicates.iter().cloned());
2164     }
2165
2166     // In default impls, we can assume that the self type implements
2167     // the trait. So in:
2168     //
2169     //     default impl Foo for Bar { .. }
2170     //
2171     // we add a default where clause `Foo: Bar`. We do a similar thing for traits
2172     // (see below). Recall that a default impl is not itself an impl, but rather a
2173     // set of defaults that can be incorporated into another impl.
2174     if let Some(trait_ref) = is_default_impl_trait {
2175         predicates.push((trait_ref.to_poly_trait_ref().to_predicate(), tcx.def_span(def_id)));
2176     }
2177
2178     // Collect the region predicates that were declared inline as
2179     // well. In the case of parameters declared on a fn or method, we
2180     // have to be careful to only iterate over early-bound regions.
2181     let mut index = parent_count + has_own_self as u32;
2182     for param in early_bound_lifetimes_from_generics(tcx, ast_generics) {
2183         let region = tcx.mk_region(ty::ReEarlyBound(ty::EarlyBoundRegion {
2184             def_id: tcx.hir().local_def_id(param.hir_id),
2185             index,
2186             name: param.name.ident().name,
2187         }));
2188         index += 1;
2189
2190         match param.kind {
2191             GenericParamKind::Lifetime { .. } => {
2192                 param.bounds.iter().for_each(|bound| match bound {
2193                     hir::GenericBound::Outlives(lt) => {
2194                         let bound = AstConv::ast_region_to_region(&icx, &lt, None);
2195                         let outlives = ty::Binder::bind(ty::OutlivesPredicate(region, bound));
2196                         predicates.push((outlives.to_predicate(), lt.span));
2197                     }
2198                     _ => bug!(),
2199                 });
2200             }
2201             _ => bug!(),
2202         }
2203     }
2204
2205     // Collect the predicates that were written inline by the user on each
2206     // type parameter (e.g., `<T: Foo>`).
2207     for param in &ast_generics.params {
2208         if let GenericParamKind::Type { .. } = param.kind {
2209             let name = param.name.ident().name;
2210             let param_ty = ty::ParamTy::new(index, name).to_ty(tcx);
2211             index += 1;
2212
2213             let sized = SizedByDefault::Yes;
2214             let bounds = AstConv::compute_bounds(&icx, param_ty, &param.bounds, sized, param.span);
2215             predicates.extend(bounds.predicates(tcx, param_ty));
2216         }
2217     }
2218
2219     // Add in the bounds that appear in the where-clause.
2220     let where_clause = &ast_generics.where_clause;
2221     for predicate in &where_clause.predicates {
2222         match predicate {
2223             &hir::WherePredicate::BoundPredicate(ref bound_pred) => {
2224                 let ty = icx.to_ty(&bound_pred.bounded_ty);
2225
2226                 // Keep the type around in a dummy predicate, in case of no bounds.
2227                 // That way, `where Ty:` is not a complete noop (see #53696) and `Ty`
2228                 // is still checked for WF.
2229                 if bound_pred.bounds.is_empty() {
2230                     if let ty::Param(_) = ty.kind {
2231                         // This is a `where T:`, which can be in the HIR from the
2232                         // transformation that moves `?Sized` to `T`'s declaration.
2233                         // We can skip the predicate because type parameters are
2234                         // trivially WF, but also we *should*, to avoid exposing
2235                         // users who never wrote `where Type:,` themselves, to
2236                         // compiler/tooling bugs from not handling WF predicates.
2237                     } else {
2238                         let span = bound_pred.bounded_ty.span;
2239                         let predicate = ty::OutlivesPredicate(ty, tcx.mk_region(ty::ReEmpty));
2240                         predicates.push(
2241                             (ty::Predicate::TypeOutlives(ty::Binder::dummy(predicate)), span)
2242                         );
2243                     }
2244                 }
2245
2246                 for bound in bound_pred.bounds.iter() {
2247                     match bound {
2248                         &hir::GenericBound::Trait(ref poly_trait_ref, _) => {
2249                             let mut bounds = Bounds::default();
2250                             let _ = AstConv::instantiate_poly_trait_ref(
2251                                 &icx,
2252                                 poly_trait_ref,
2253                                 ty,
2254                                 &mut bounds,
2255                             );
2256                             predicates.extend(bounds.predicates(tcx, ty));
2257                         }
2258
2259                         &hir::GenericBound::Outlives(ref lifetime) => {
2260                             let region = AstConv::ast_region_to_region(&icx, lifetime, None);
2261                             let pred = ty::Binder::bind(ty::OutlivesPredicate(ty, region));
2262                             predicates.push((ty::Predicate::TypeOutlives(pred), lifetime.span))
2263                         }
2264                     }
2265                 }
2266             }
2267
2268             &hir::WherePredicate::RegionPredicate(ref region_pred) => {
2269                 let r1 = AstConv::ast_region_to_region(&icx, &region_pred.lifetime, None);
2270                 predicates.extend(region_pred.bounds.iter().map(|bound| {
2271                     let (r2, span) = match bound {
2272                         hir::GenericBound::Outlives(lt) => {
2273                             (AstConv::ast_region_to_region(&icx, lt, None), lt.span)
2274                         }
2275                         _ => bug!(),
2276                     };
2277                     let pred = ty::Binder::bind(ty::OutlivesPredicate(r1, r2));
2278
2279                     (ty::Predicate::RegionOutlives(pred), span)
2280                 }))
2281             }
2282
2283             &hir::WherePredicate::EqPredicate(..) => {
2284                 // FIXME(#20041)
2285             }
2286         }
2287     }
2288
2289     // Add predicates from associated type bounds.
2290     if let Some((self_trait_ref, trait_items)) = is_trait {
2291         predicates.extend(trait_items.iter().flat_map(|trait_item_ref| {
2292             let trait_item = tcx.hir().trait_item(trait_item_ref.id);
2293             let bounds = match trait_item.kind {
2294                 hir::TraitItemKind::Type(ref bounds, _) => bounds,
2295                 _ => return Vec::new().into_iter()
2296             };
2297
2298             let assoc_ty =
2299                 tcx.mk_projection(tcx.hir().local_def_id(trait_item.hir_id),
2300                     self_trait_ref.substs);
2301
2302             let bounds = AstConv::compute_bounds(
2303                 &ItemCtxt::new(tcx, def_id),
2304                 assoc_ty,
2305                 bounds,
2306                 SizedByDefault::Yes,
2307                 trait_item.span,
2308             );
2309
2310             bounds.predicates(tcx, assoc_ty).into_iter()
2311         }))
2312     }
2313
2314     let mut predicates = predicates.predicates;
2315
2316     // Subtle: before we store the predicates into the tcx, we
2317     // sort them so that predicates like `T: Foo<Item=U>` come
2318     // before uses of `U`.  This avoids false ambiguity errors
2319     // in trait checking. See `setup_constraining_predicates`
2320     // for details.
2321     if let Node::Item(&Item {
2322         kind: ItemKind::Impl(..),
2323         ..
2324     }) = node
2325     {
2326         let self_ty = tcx.type_of(def_id);
2327         let trait_ref = tcx.impl_trait_ref(def_id);
2328         cgp::setup_constraining_predicates(
2329             tcx,
2330             &mut predicates,
2331             trait_ref,
2332             &mut cgp::parameters_for_impl(self_ty, trait_ref),
2333         );
2334     }
2335
2336     let result = ty::GenericPredicates {
2337         parent: generics.parent,
2338         predicates: tcx.arena.alloc_from_iter(predicates),
2339     };
2340     debug!("explicit_predicates_of(def_id={:?}) = {:?}", def_id, result);
2341     result
2342 }
2343
2344 /// Converts a specific `GenericBound` from the AST into a set of
2345 /// predicates that apply to the self type. A vector is returned
2346 /// because this can be anywhere from zero predicates (`T: ?Sized` adds no
2347 /// predicates) to one (`T: Foo`) to many (`T: Bar<X = i32>` adds `T: Bar`
2348 /// and `<T as Bar>::X == i32`).
2349 fn predicates_from_bound<'tcx>(
2350     astconv: &dyn AstConv<'tcx>,
2351     param_ty: Ty<'tcx>,
2352     bound: &'tcx hir::GenericBound,
2353 ) -> Vec<(ty::Predicate<'tcx>, Span)> {
2354     match *bound {
2355         hir::GenericBound::Trait(ref tr, hir::TraitBoundModifier::None) => {
2356             let mut bounds = Bounds::default();
2357             let _ = astconv.instantiate_poly_trait_ref(
2358                 tr,
2359                 param_ty,
2360                 &mut bounds,
2361             );
2362             bounds.predicates(astconv.tcx(), param_ty)
2363         }
2364         hir::GenericBound::Outlives(ref lifetime) => {
2365             let region = astconv.ast_region_to_region(lifetime, None);
2366             let pred = ty::Binder::bind(ty::OutlivesPredicate(param_ty, region));
2367             vec![(ty::Predicate::TypeOutlives(pred), lifetime.span)]
2368         }
2369         hir::GenericBound::Trait(_, hir::TraitBoundModifier::Maybe) => vec![],
2370     }
2371 }
2372
2373 fn compute_sig_of_foreign_fn_decl<'tcx>(
2374     tcx: TyCtxt<'tcx>,
2375     def_id: DefId,
2376     decl: &'tcx hir::FnDecl,
2377     abi: abi::Abi,
2378 ) -> ty::PolyFnSig<'tcx> {
2379     let unsafety = if abi == abi::Abi::RustIntrinsic {
2380         intrinsic_operation_unsafety(&tcx.item_name(def_id).as_str())
2381     } else {
2382         hir::Unsafety::Unsafe
2383     };
2384     let fty = AstConv::ty_of_fn(&ItemCtxt::new(tcx, def_id), unsafety, abi, decl);
2385
2386     // Feature gate SIMD types in FFI, since I am not sure that the
2387     // ABIs are handled at all correctly. -huonw
2388     if abi != abi::Abi::RustIntrinsic
2389         && abi != abi::Abi::PlatformIntrinsic
2390         && !tcx.features().simd_ffi
2391     {
2392         let check = |ast_ty: &hir::Ty, ty: Ty<'_>| {
2393             if ty.is_simd() {
2394                 tcx.sess
2395                    .struct_span_err(
2396                        ast_ty.span,
2397                        &format!(
2398                            "use of SIMD type `{}` in FFI is highly experimental and \
2399                             may result in invalid code",
2400                            tcx.hir().hir_to_pretty_string(ast_ty.hir_id)
2401                        ),
2402                    )
2403                    .help("add `#![feature(simd_ffi)]` to the crate attributes to enable")
2404                    .emit();
2405             }
2406         };
2407         for (input, ty) in decl.inputs.iter().zip(*fty.inputs().skip_binder()) {
2408             check(&input, ty)
2409         }
2410         if let hir::Return(ref ty) = decl.output {
2411             check(&ty, *fty.output().skip_binder())
2412         }
2413     }
2414
2415     fty
2416 }
2417
2418 fn is_foreign_item(tcx: TyCtxt<'_>, def_id: DefId) -> bool {
2419     match tcx.hir().get_if_local(def_id) {
2420         Some(Node::ForeignItem(..)) => true,
2421         Some(_) => false,
2422         _ => bug!("is_foreign_item applied to non-local def-id {:?}", def_id),
2423     }
2424 }
2425
2426 fn static_mutability(tcx: TyCtxt<'_>, def_id: DefId) -> Option<hir::Mutability> {
2427     match tcx.hir().get_if_local(def_id) {
2428         Some(Node::Item(&hir::Item {
2429             kind: hir::ItemKind::Static(_, mutbl, _), ..
2430         })) |
2431         Some(Node::ForeignItem( &hir::ForeignItem {
2432             kind: hir::ForeignItemKind::Static(_, mutbl), ..
2433         })) => Some(mutbl),
2434         Some(_) => None,
2435         _ => bug!("static_mutability applied to non-local def-id {:?}", def_id),
2436     }
2437 }
2438
2439 fn from_target_feature(
2440     tcx: TyCtxt<'_>,
2441     id: DefId,
2442     attr: &ast::Attribute,
2443     whitelist: &FxHashMap<String, Option<Symbol>>,
2444     target_features: &mut Vec<Symbol>,
2445 ) {
2446     let list = match attr.meta_item_list() {
2447         Some(list) => list,
2448         None => return,
2449     };
2450     let bad_item = |span| {
2451         let msg = "malformed `target_feature` attribute input";
2452         let code = "enable = \"..\"".to_owned();
2453         tcx.sess.struct_span_err(span, &msg)
2454             .span_suggestion(span, "must be of the form", code, Applicability::HasPlaceholders)
2455             .emit();
2456     };
2457     let rust_features = tcx.features();
2458     for item in list {
2459         // Only `enable = ...` is accepted in the meta-item list.
2460         if !item.check_name(sym::enable) {
2461             bad_item(item.span());
2462             continue;
2463         }
2464
2465         // Must be of the form `enable = "..."` (a string).
2466         let value = match item.value_str() {
2467             Some(value) => value,
2468             None => {
2469                 bad_item(item.span());
2470                 continue;
2471             }
2472         };
2473
2474         // We allow comma separation to enable multiple features.
2475         target_features.extend(value.as_str().split(',').filter_map(|feature| {
2476             // Only allow whitelisted features per platform.
2477             let feature_gate = match whitelist.get(feature) {
2478                 Some(g) => g,
2479                 None => {
2480                     let msg = format!(
2481                         "the feature named `{}` is not valid for this target",
2482                         feature
2483                     );
2484                     let mut err = tcx.sess.struct_span_err(item.span(), &msg);
2485                     err.span_label(
2486                         item.span(),
2487                         format!("`{}` is not valid for this target", feature),
2488                     );
2489                     if feature.starts_with("+") {
2490                         let valid = whitelist.contains_key(&feature[1..]);
2491                         if valid {
2492                             err.help("consider removing the leading `+` in the feature name");
2493                         }
2494                     }
2495                     err.emit();
2496                     return None;
2497                 }
2498             };
2499
2500             // Only allow features whose feature gates have been enabled.
2501             let allowed = match feature_gate.as_ref().map(|s| *s) {
2502                 Some(sym::arm_target_feature) => rust_features.arm_target_feature,
2503                 Some(sym::aarch64_target_feature) => rust_features.aarch64_target_feature,
2504                 Some(sym::hexagon_target_feature) => rust_features.hexagon_target_feature,
2505                 Some(sym::powerpc_target_feature) => rust_features.powerpc_target_feature,
2506                 Some(sym::mips_target_feature) => rust_features.mips_target_feature,
2507                 Some(sym::avx512_target_feature) => rust_features.avx512_target_feature,
2508                 Some(sym::mmx_target_feature) => rust_features.mmx_target_feature,
2509                 Some(sym::sse4a_target_feature) => rust_features.sse4a_target_feature,
2510                 Some(sym::tbm_target_feature) => rust_features.tbm_target_feature,
2511                 Some(sym::wasm_target_feature) => rust_features.wasm_target_feature,
2512                 Some(sym::cmpxchg16b_target_feature) => rust_features.cmpxchg16b_target_feature,
2513                 Some(sym::adx_target_feature) => rust_features.adx_target_feature,
2514                 Some(sym::movbe_target_feature) => rust_features.movbe_target_feature,
2515                 Some(sym::rtm_target_feature) => rust_features.rtm_target_feature,
2516                 Some(sym::f16c_target_feature) => rust_features.f16c_target_feature,
2517                 Some(name) => bug!("unknown target feature gate {}", name),
2518                 None => true,
2519             };
2520             if !allowed && id.is_local() {
2521                 feature_gate::feature_err(
2522                     &tcx.sess.parse_sess,
2523                     feature_gate.unwrap(),
2524                     item.span(),
2525                     &format!("the target feature `{}` is currently unstable", feature),
2526                 )
2527                 .emit();
2528             }
2529             Some(Symbol::intern(feature))
2530         }));
2531     }
2532 }
2533
2534 fn linkage_by_name(tcx: TyCtxt<'_>, def_id: DefId, name: &str) -> Linkage {
2535     use rustc::mir::mono::Linkage::*;
2536
2537     // Use the names from src/llvm/docs/LangRef.rst here. Most types are only
2538     // applicable to variable declarations and may not really make sense for
2539     // Rust code in the first place but whitelist them anyway and trust that
2540     // the user knows what s/he's doing. Who knows, unanticipated use cases
2541     // may pop up in the future.
2542     //
2543     // ghost, dllimport, dllexport and linkonce_odr_autohide are not supported
2544     // and don't have to be, LLVM treats them as no-ops.
2545     match name {
2546         "appending" => Appending,
2547         "available_externally" => AvailableExternally,
2548         "common" => Common,
2549         "extern_weak" => ExternalWeak,
2550         "external" => External,
2551         "internal" => Internal,
2552         "linkonce" => LinkOnceAny,
2553         "linkonce_odr" => LinkOnceODR,
2554         "private" => Private,
2555         "weak" => WeakAny,
2556         "weak_odr" => WeakODR,
2557         _ => {
2558             let span = tcx.hir().span_if_local(def_id);
2559             if let Some(span) = span {
2560                 tcx.sess.span_fatal(span, "invalid linkage specified")
2561             } else {
2562                 tcx.sess
2563                    .fatal(&format!("invalid linkage specified: {}", name))
2564             }
2565         }
2566     }
2567 }
2568
2569 fn codegen_fn_attrs(tcx: TyCtxt<'_>, id: DefId) -> CodegenFnAttrs {
2570     let attrs = tcx.get_attrs(id);
2571
2572     let mut codegen_fn_attrs = CodegenFnAttrs::new();
2573
2574     let whitelist = tcx.target_features_whitelist(LOCAL_CRATE);
2575
2576     let mut inline_span = None;
2577     let mut link_ordinal_span = None;
2578     for attr in attrs.iter() {
2579         if attr.check_name(sym::cold) {
2580             codegen_fn_attrs.flags |= CodegenFnAttrFlags::COLD;
2581         } else if attr.check_name(sym::rustc_allocator) {
2582             codegen_fn_attrs.flags |= CodegenFnAttrFlags::ALLOCATOR;
2583         } else if attr.check_name(sym::unwind) {
2584             codegen_fn_attrs.flags |= CodegenFnAttrFlags::UNWIND;
2585         } else if attr.check_name(sym::ffi_returns_twice) {
2586             if tcx.is_foreign_item(id) {
2587                 codegen_fn_attrs.flags |= CodegenFnAttrFlags::FFI_RETURNS_TWICE;
2588             } else {
2589                 // `#[ffi_returns_twice]` is only allowed `extern fn`s.
2590                 struct_span_err!(
2591                     tcx.sess,
2592                     attr.span,
2593                     E0724,
2594                     "`#[ffi_returns_twice]` may only be used on foreign functions"
2595                 ).emit();
2596             }
2597         } else if attr.check_name(sym::rustc_allocator_nounwind) {
2598             codegen_fn_attrs.flags |= CodegenFnAttrFlags::RUSTC_ALLOCATOR_NOUNWIND;
2599         } else if attr.check_name(sym::naked) {
2600             codegen_fn_attrs.flags |= CodegenFnAttrFlags::NAKED;
2601         } else if attr.check_name(sym::no_mangle) {
2602             codegen_fn_attrs.flags |= CodegenFnAttrFlags::NO_MANGLE;
2603         } else if attr.check_name(sym::rustc_std_internal_symbol) {
2604             codegen_fn_attrs.flags |= CodegenFnAttrFlags::RUSTC_STD_INTERNAL_SYMBOL;
2605         } else if attr.check_name(sym::no_debug) {
2606             codegen_fn_attrs.flags |= CodegenFnAttrFlags::NO_DEBUG;
2607         } else if attr.check_name(sym::used) {
2608             codegen_fn_attrs.flags |= CodegenFnAttrFlags::USED;
2609         } else if attr.check_name(sym::thread_local) {
2610             codegen_fn_attrs.flags |= CodegenFnAttrFlags::THREAD_LOCAL;
2611         } else if attr.check_name(sym::track_caller) {
2612             if tcx.fn_sig(id).abi() != abi::Abi::Rust {
2613                 struct_span_err!(
2614                     tcx.sess,
2615                     attr.span,
2616                     E0737,
2617                     "`#[track_caller]` requires Rust ABI"
2618                 ).emit();
2619             }
2620             codegen_fn_attrs.flags |= CodegenFnAttrFlags::TRACK_CALLER;
2621         } else if attr.check_name(sym::export_name) {
2622             if let Some(s) = attr.value_str() {
2623                 if s.as_str().contains("\0") {
2624                     // `#[export_name = ...]` will be converted to a null-terminated string,
2625                     // so it may not contain any null characters.
2626                     struct_span_err!(
2627                         tcx.sess,
2628                         attr.span,
2629                         E0648,
2630                         "`export_name` may not contain null characters"
2631                     ).emit();
2632                 }
2633                 codegen_fn_attrs.export_name = Some(s);
2634             }
2635         } else if attr.check_name(sym::target_feature) {
2636             if tcx.fn_sig(id).unsafety() == Unsafety::Normal {
2637                 let msg = "`#[target_feature(..)]` can only be applied to `unsafe` functions";
2638                 tcx.sess.struct_span_err(attr.span, msg)
2639                     .span_label(attr.span, "can only be applied to `unsafe` functions")
2640                     .span_label(tcx.def_span(id), "not an `unsafe` function")
2641                     .emit();
2642             }
2643             from_target_feature(
2644                 tcx,
2645                 id,
2646                 attr,
2647                 &whitelist,
2648                 &mut codegen_fn_attrs.target_features,
2649             );
2650         } else if attr.check_name(sym::linkage) {
2651             if let Some(val) = attr.value_str() {
2652                 codegen_fn_attrs.linkage = Some(linkage_by_name(tcx, id, &val.as_str()));
2653             }
2654         } else if attr.check_name(sym::link_section) {
2655             if let Some(val) = attr.value_str() {
2656                 if val.as_str().bytes().any(|b| b == 0) {
2657                     let msg = format!(
2658                         "illegal null byte in link_section \
2659                          value: `{}`",
2660                         &val
2661                     );
2662                     tcx.sess.span_err(attr.span, &msg);
2663                 } else {
2664                     codegen_fn_attrs.link_section = Some(val);
2665                 }
2666             }
2667         } else if attr.check_name(sym::link_name) {
2668             codegen_fn_attrs.link_name = attr.value_str();
2669         } else if attr.check_name(sym::link_ordinal) {
2670             link_ordinal_span = Some(attr.span);
2671             if let ordinal @ Some(_) = check_link_ordinal(tcx, attr) {
2672                 codegen_fn_attrs.link_ordinal = ordinal;
2673             }
2674         }
2675     }
2676
2677     codegen_fn_attrs.inline = attrs.iter().fold(InlineAttr::None, |ia, attr| {
2678         if !attr.has_name(sym::inline) {
2679             return ia;
2680         }
2681         match attr.meta().map(|i| i.kind) {
2682             Some(MetaItemKind::Word) => {
2683                 mark_used(attr);
2684                 InlineAttr::Hint
2685             }
2686             Some(MetaItemKind::List(ref items)) => {
2687                 mark_used(attr);
2688                 inline_span = Some(attr.span);
2689                 if items.len() != 1 {
2690                     span_err!(
2691                         tcx.sess.diagnostic(),
2692                         attr.span,
2693                         E0534,
2694                         "expected one argument"
2695                     );
2696                     InlineAttr::None
2697                 } else if list_contains_name(&items[..], sym::always) {
2698                     InlineAttr::Always
2699                 } else if list_contains_name(&items[..], sym::never) {
2700                     InlineAttr::Never
2701                 } else {
2702                     span_err!(
2703                         tcx.sess.diagnostic(),
2704                         items[0].span(),
2705                         E0535,
2706                         "invalid argument"
2707                     );
2708
2709                     InlineAttr::None
2710                 }
2711             }
2712             Some(MetaItemKind::NameValue(_)) => ia,
2713             None => ia,
2714         }
2715     });
2716
2717     codegen_fn_attrs.optimize = attrs.iter().fold(OptimizeAttr::None, |ia, attr| {
2718         if !attr.has_name(sym::optimize) {
2719             return ia;
2720         }
2721         let err = |sp, s| span_err!(tcx.sess.diagnostic(), sp, E0722, "{}", s);
2722         match attr.meta().map(|i| i.kind) {
2723             Some(MetaItemKind::Word) => {
2724                 err(attr.span, "expected one argument");
2725                 ia
2726             }
2727             Some(MetaItemKind::List(ref items)) => {
2728                 mark_used(attr);
2729                 inline_span = Some(attr.span);
2730                 if items.len() != 1 {
2731                     err(attr.span, "expected one argument");
2732                     OptimizeAttr::None
2733                 } else if list_contains_name(&items[..], sym::size) {
2734                     OptimizeAttr::Size
2735                 } else if list_contains_name(&items[..], sym::speed) {
2736                     OptimizeAttr::Speed
2737                 } else {
2738                     err(items[0].span(), "invalid argument");
2739                     OptimizeAttr::None
2740                 }
2741             }
2742             Some(MetaItemKind::NameValue(_)) => ia,
2743             None => ia,
2744         }
2745     });
2746
2747     // If a function uses #[target_feature] it can't be inlined into general
2748     // purpose functions as they wouldn't have the right target features
2749     // enabled. For that reason we also forbid #[inline(always)] as it can't be
2750     // respected.
2751
2752     if codegen_fn_attrs.target_features.len() > 0 {
2753         if codegen_fn_attrs.inline == InlineAttr::Always {
2754             if let Some(span) = inline_span {
2755                 tcx.sess.span_err(
2756                     span,
2757                     "cannot use `#[inline(always)]` with \
2758                      `#[target_feature]`",
2759                 );
2760             }
2761         }
2762     }
2763
2764     // Weak lang items have the same semantics as "std internal" symbols in the
2765     // sense that they're preserved through all our LTO passes and only
2766     // strippable by the linker.
2767     //
2768     // Additionally weak lang items have predetermined symbol names.
2769     if tcx.is_weak_lang_item(id) {
2770         codegen_fn_attrs.flags |= CodegenFnAttrFlags::RUSTC_STD_INTERNAL_SYMBOL;
2771     }
2772     if let Some(name) = weak_lang_items::link_name(&attrs) {
2773         codegen_fn_attrs.export_name = Some(name);
2774         codegen_fn_attrs.link_name = Some(name);
2775     }
2776     check_link_name_xor_ordinal(tcx, &codegen_fn_attrs, link_ordinal_span);
2777
2778     // Internal symbols to the standard library all have no_mangle semantics in
2779     // that they have defined symbol names present in the function name. This
2780     // also applies to weak symbols where they all have known symbol names.
2781     if codegen_fn_attrs.flags.contains(CodegenFnAttrFlags::RUSTC_STD_INTERNAL_SYMBOL) {
2782         codegen_fn_attrs.flags |= CodegenFnAttrFlags::NO_MANGLE;
2783     }
2784
2785     codegen_fn_attrs
2786 }
2787
2788 fn check_link_ordinal(tcx: TyCtxt<'_>, attr: &ast::Attribute) -> Option<usize> {
2789     use syntax::ast::{Lit, LitIntType, LitKind};
2790     let meta_item_list = attr.meta_item_list();
2791     let meta_item_list: Option<&[ast::NestedMetaItem]> = meta_item_list.as_ref().map(Vec::as_ref);
2792     let sole_meta_list = match meta_item_list {
2793         Some([item]) => item.literal(),
2794         _ => None,
2795     };
2796     if let Some(Lit { kind: LitKind::Int(ordinal, LitIntType::Unsuffixed), .. }) = sole_meta_list {
2797         if *ordinal <= std::usize::MAX as u128 {
2798             Some(*ordinal as usize)
2799         } else {
2800             let msg = format!(
2801                 "ordinal value in `link_ordinal` is too large: `{}`",
2802                 &ordinal
2803             );
2804             tcx.sess.struct_span_err(attr.span, &msg)
2805                 .note("the value may not exceed `std::usize::MAX`")
2806                 .emit();
2807             None
2808         }
2809     } else {
2810         tcx.sess.struct_span_err(attr.span, "illegal ordinal format in `link_ordinal`")
2811             .note("an unsuffixed integer value, e.g., `1`, is expected")
2812             .emit();
2813         None
2814     }
2815 }
2816
2817 fn check_link_name_xor_ordinal(
2818     tcx: TyCtxt<'_>,
2819     codegen_fn_attrs: &CodegenFnAttrs,
2820     inline_span: Option<Span>,
2821 ) {
2822     if codegen_fn_attrs.link_name.is_none() || codegen_fn_attrs.link_ordinal.is_none() {
2823         return;
2824     }
2825     let msg = "cannot use `#[link_name]` with `#[link_ordinal]`";
2826     if let Some(span) = inline_span {
2827         tcx.sess.span_err(span, msg);
2828     } else {
2829         tcx.sess.err(msg);
2830     }
2831 }