src/librustc_typeck/collect.rs

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