src/librustc_typeck/collect.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! "Collection" is the process of determining the type and other external
  12 //! details of each item in Rust. Collection is specifically concerned
  13 //! with *interprocedural* things -- for example, for a function
  14 //! definition, collection will figure out the type and signature of the
  15 //! function, but it will not visit the *body* of the function in any way,
  16 //! nor examine type annotations on local variables (that's the job of
  17 //! type *checking*).
  18 //!
  19 //! Collecting is ultimately defined by a bundle of queries that
  20 //! inquire after various facts about the items in the crate (e.g.,
  21 //! `type_of`, `generics_of`, `predicates_of`, etc). See the `provide` function
  22 //! for the full set.
  23 //!
  24 //! At present, however, we do run collection across all items in the
  25 //! crate as a kind of pass. This should eventually be factored away.
  26
  27 use astconv::{AstConv, Bounds};
  28 use lint;
  29 use constrained_type_params as ctp;
  30 use middle::lang_items::SizedTraitLangItem;
  31 use middle::resolve_lifetime as rl;
  32 use rustc::mir::mono::Linkage;
  33 use rustc::ty::subst::Substs;
  34 use rustc::ty::{ToPredicate, ReprOptions};
  35 use rustc::ty::{self, AdtKind, ToPolyTraitRef, Ty, TyCtxt};
  36 use rustc::ty::query::Providers;
  37 use rustc::ty::util::IntTypeExt;
  38 use rustc::ty::util::Discr;
  39 use rustc::util::captures::Captures;
  40 use rustc::util::nodemap::FxHashMap;
  41 use rustc_target::spec::abi;
  42
  43 use syntax::ast;
  44 use syntax::ast::MetaItemKind;
  45 use syntax::attr::{InlineAttr, list_contains_name, mark_used};
  46 use syntax::codemap::Spanned;
  47 use syntax::symbol::{Symbol, keywords};
  48 use syntax::feature_gate;
  49 use syntax_pos::{Span, DUMMY_SP};
  50
  51 use rustc::hir::{self, map as hir_map, CodegenFnAttrs, CodegenFnAttrFlags, Unsafety};
  52 use rustc::hir::GenericParamKind;
  53 use rustc::hir::intravisit::{self, Visitor, NestedVisitorMap};
  54 use rustc::hir::def::{Def, CtorKind};
  55 use rustc::hir::def_id::{DefId, LOCAL_CRATE};
  56
  57 ///////////////////////////////////////////////////////////////////////////
  58 // Main entry point
  59
  60 pub fn collect_item_types<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) {
  61     let mut visitor = CollectItemTypesVisitor { tcx: tcx };
  62     tcx.hir.krate().visit_all_item_likes(&mut visitor.as_deep_visitor());
  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         codegen_fn_attrs,
  81         ..*providers
  82     };
  83 }
  84
  85 ///////////////////////////////////////////////////////////////////////////
  86
  87 /// Context specific to some particular item. This is what implements
  88 /// AstConv. It has information about the predicates that are defined
  89 /// on the trait. Unfortunately, this predicate information is
  90 /// available in various different forms at various points in the
  91 /// process. So we can't just store a pointer to e.g. the AST or the
  92 /// parsed ty form, we have to be more flexible. To this end, the
  93 /// `ItemCtxt` is parameterized by a `DefId` that it uses to satisfy
  94 /// `get_type_parameter_bounds` requests, drawing the information from
  95 /// the AST (`hir::Generics`), recursively.
  96 pub struct ItemCtxt<'a,'tcx:'a> {
  97     tcx: TyCtxt<'a, 'tcx, 'tcx>,
  98     item_def_id: DefId,
  99 }
 100
 101 ///////////////////////////////////////////////////////////////////////////
 102
 103 struct CollectItemTypesVisitor<'a, 'tcx: 'a> {
 104     tcx: TyCtxt<'a, 'tcx, 'tcx>
 105 }
 106
 107 impl<'a, 'tcx> Visitor<'tcx> for CollectItemTypesVisitor<'a, 'tcx> {
 108     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
 109         NestedVisitorMap::OnlyBodies(&self.tcx.hir)
 110     }
 111
 112     fn visit_item(&mut self, item: &'tcx hir::Item) {
 113         convert_item(self.tcx, item.id);
 114         intravisit::walk_item(self, item);
 115     }
 116
 117     fn visit_generics(&mut self, generics: &'tcx hir::Generics) {
 118         for param in &generics.params {
 119             match param.kind {
 120                 hir::GenericParamKind::Lifetime { .. } => {}
 121                 hir::GenericParamKind::Type { default: Some(_), .. } => {
 122                     let def_id = self.tcx.hir.local_def_id(param.id);
 123                     self.tcx.type_of(def_id);
 124                 }
 125                 hir::GenericParamKind::Type { .. } => {}
 126             }
 127         }
 128         intravisit::walk_generics(self, generics);
 129     }
 130
 131     fn visit_expr(&mut self, expr: &'tcx hir::Expr) {
 132         if let hir::ExprKind::Closure(..) = expr.node {
 133             let def_id = self.tcx.hir.local_def_id(expr.id);
 134             self.tcx.generics_of(def_id);
 135             self.tcx.type_of(def_id);
 136         }
 137         intravisit::walk_expr(self, expr);
 138     }
 139
 140     fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem) {
 141         convert_trait_item(self.tcx, trait_item.id);
 142         intravisit::walk_trait_item(self, trait_item);
 143     }
 144
 145     fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem) {
 146         convert_impl_item(self.tcx, impl_item.id);
 147         intravisit::walk_impl_item(self, impl_item);
 148     }
 149 }
 150
 151 ///////////////////////////////////////////////////////////////////////////
 152 // Utility types and common code for the above passes.
 153
 154 impl<'a, 'tcx> ItemCtxt<'a, 'tcx> {
 155     pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>, item_def_id: DefId)
 156            -> ItemCtxt<'a,'tcx> {
 157         ItemCtxt {
 158             tcx,
 159             item_def_id,
 160         }
 161     }
 162 }
 163
 164 impl<'a,'tcx> ItemCtxt<'a,'tcx> {
 165     pub fn to_ty(&self, ast_ty: &hir::Ty) -> Ty<'tcx> {
 166         AstConv::ast_ty_to_ty(self, ast_ty)
 167     }
 168 }
 169
 170 impl<'a, 'tcx> AstConv<'tcx, 'tcx> for ItemCtxt<'a, 'tcx> {
 171     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'tcx, 'tcx> { self.tcx }
 172
 173     fn get_type_parameter_bounds(&self,
 174                                  span: Span,
 175                                  def_id: DefId)
 176                                  -> ty::GenericPredicates<'tcx>
 177     {
 178         self.tcx.at(span).type_param_predicates((self.item_def_id, def_id))
 179     }
 180
 181     fn re_infer(&self, _span: Span, _def: Option<&ty::GenericParamDef>)
 182                 -> Option<ty::Region<'tcx>> {
 183         None
 184     }
 185
 186     fn ty_infer(&self, span: Span) -> Ty<'tcx> {
 187         struct_span_err!(
 188             self.tcx().sess,
 189             span,
 190             E0121,
 191             "the type placeholder `_` is not allowed within types on item signatures"
 192         ).span_label(span, "not allowed in type signatures")
 193         .emit();
 194         self.tcx().types.err
 195     }
 196
 197     fn projected_ty_from_poly_trait_ref(&self,
 198                                         span: Span,
 199                                         item_def_id: DefId,
 200                                         poly_trait_ref: ty::PolyTraitRef<'tcx>)
 201                                         -> Ty<'tcx>
 202     {
 203         if let Some(trait_ref) = poly_trait_ref.no_late_bound_regions() {
 204             self.tcx().mk_projection(item_def_id, trait_ref.substs)
 205         } else {
 206             // no late-bound regions, we can just ignore the binder
 207             span_err!(self.tcx().sess, span, E0212,
 208                 "cannot extract an associated type from a higher-ranked trait bound \
 209                  in this context");
 210             self.tcx().types.err
 211         }
 212     }
 213
 214     fn normalize_ty(&self, _span: Span, ty: Ty<'tcx>) -> Ty<'tcx> {
 215         // types in item signatures are not normalized, to avoid undue
 216         // dependencies.
 217         ty
 218     }
 219
 220     fn set_tainted_by_errors(&self) {
 221         // no obvious place to track this, just let it go
 222     }
 223
 224     fn record_ty(&self, _hir_id: hir::HirId, _ty: Ty<'tcx>, _span: Span) {
 225         // no place to record types from signatures?
 226     }
 227 }
 228
 229 fn type_param_predicates<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 230                                    (item_def_id, def_id): (DefId, DefId))
 231                                    -> ty::GenericPredicates<'tcx> {
 232     use rustc::hir::map::*;
 233     use rustc::hir::*;
 234
 235     // In the AST, bounds can derive from two places. Either
 236     // written inline like `<T:Foo>` or in a where clause like
 237     // `where T:Foo`.
 238
 239     let param_id = tcx.hir.as_local_node_id(def_id).unwrap();
 240     let param_owner = tcx.hir.ty_param_owner(param_id);
 241     let param_owner_def_id = tcx.hir.local_def_id(param_owner);
 242     let generics = tcx.generics_of(param_owner_def_id);
 243     let index = generics.param_def_id_to_index[&def_id];
 244     let ty = tcx.mk_ty_param(index, tcx.hir.ty_param_name(param_id).as_interned_str());
 245
 246     // Don't look for bounds where the type parameter isn't in scope.
 247     let parent = if item_def_id == param_owner_def_id {
 248         None
 249     } else {
 250         tcx.generics_of(item_def_id).parent
 251     };
 252
 253     let mut result = parent.map_or(ty::GenericPredicates {
 254         parent: None,
 255         predicates: vec![]
 256     }, |parent| {
 257         let icx = ItemCtxt::new(tcx, parent);
 258         icx.get_type_parameter_bounds(DUMMY_SP, def_id)
 259     });
 260
 261     let item_node_id = tcx.hir.as_local_node_id(item_def_id).unwrap();
 262     let ast_generics = match tcx.hir.get(item_node_id) {
 263         NodeTraitItem(item) => &item.generics,
 264
 265         NodeImplItem(item) => &item.generics,
 266
 267         NodeItem(item) => {
 268             match item.node {
 269                 ItemKind::Fn(.., ref generics, _) |
 270                 ItemKind::Impl(_, _, _, ref generics, ..) |
 271                 ItemKind::Ty(_, ref generics) |
 272                 ItemKind::Existential(ExistTy { ref generics, impl_trait_fn: None, ..}) |
 273                 ItemKind::Enum(_, ref generics) |
 274                 ItemKind::Struct(_, ref generics) |
 275                 ItemKind::Union(_, ref generics) => generics,
 276                 ItemKind::Trait(_, _, ref generics, ..) => {
 277                     // Implied `Self: Trait` and supertrait bounds.
 278                     if param_id == item_node_id {
 279                         result.predicates.push(
 280                             ty::TraitRef::identity(tcx, item_def_id).to_predicate()
 281                         );
 282                     }
 283                     generics
 284                 }
 285                 _ => return result
 286             }
 287         }
 288
 289         NodeForeignItem(item) => {
 290             match item.node {
 291                 ForeignItemKind::Fn(_, _, ref generics) => generics,
 292                 _ => return result
 293             }
 294         }
 295
 296         _ => return result
 297     };
 298
 299     let icx = ItemCtxt::new(tcx, item_def_id);
 300     result.predicates.extend(
 301         icx.type_parameter_bounds_in_generics(ast_generics, param_id, ty));
 302     result
 303 }
 304
 305 impl<'a, 'tcx> ItemCtxt<'a, 'tcx> {
 306     /// Find bounds from hir::Generics. This requires scanning through the
 307     /// AST. We do this to avoid having to convert *all* the bounds, which
 308     /// would create artificial cycles. Instead we can only convert the
 309     /// bounds for a type parameter `X` if `X::Foo` is used.
 310     fn type_parameter_bounds_in_generics(&self,
 311                                          ast_generics: &hir::Generics,
 312                                          param_id: ast::NodeId,
 313                                          ty: Ty<'tcx>)
 314                                          -> Vec<ty::Predicate<'tcx>>
 315     {
 316         let from_ty_params =
 317             ast_generics.params.iter()
 318                 .filter_map(|param| match param.kind {
 319                     GenericParamKind::Type { .. } if param.id == param_id => Some(&param.bounds),
 320                     _ => None
 321                 })
 322                 .flat_map(|bounds| bounds.iter())
 323                 .flat_map(|b| predicates_from_bound(self, ty, b));
 324
 325         let from_where_clauses =
 326             ast_generics.where_clause
 327                 .predicates
 328                 .iter()
 329                 .filter_map(|wp| match *wp {
 330                     hir::WherePredicate::BoundPredicate(ref bp) => Some(bp),
 331                     _ => None
 332                 })
 333                 .filter(|bp| is_param(self.tcx, &bp.bounded_ty, param_id))
 334                 .flat_map(|bp| bp.bounds.iter())
 335                 .flat_map(|b| predicates_from_bound(self, ty, b));
 336
 337         from_ty_params.chain(from_where_clauses).collect()
 338     }
 339 }
 340
 341 /// Tests whether this is the AST for a reference to the type
 342 /// parameter with id `param_id`. We use this so as to avoid running
 343 /// `ast_ty_to_ty`, because we want to avoid triggering an all-out
 344 /// conversion of the type to avoid inducing unnecessary cycles.
 345 fn is_param<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 346                       ast_ty: &hir::Ty,
 347                       param_id: ast::NodeId)
 348                       -> bool
 349 {
 350     if let hir::TyKind::Path(hir::QPath::Resolved(None, ref path)) = ast_ty.node {
 351         match path.def {
 352             Def::SelfTy(Some(def_id), None) |
 353             Def::TyParam(def_id) => {
 354                 def_id == tcx.hir.local_def_id(param_id)
 355             }
 356             _ => false
 357         }
 358     } else {
 359         false
 360     }
 361 }
 362
 363 fn convert_item<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, item_id: ast::NodeId) {
 364     let it = tcx.hir.expect_item(item_id);
 365     debug!("convert: item {} with id {}", it.name, it.id);
 366     let def_id = tcx.hir.local_def_id(item_id);
 367     match it.node {
 368         // These don't define types.
 369         hir::ItemKind::ExternCrate(_) |
 370         hir::ItemKind::Use(..) |
 371         hir::ItemKind::Mod(_) |
 372         hir::ItemKind::GlobalAsm(_) => {}
 373         hir::ItemKind::ForeignMod(ref foreign_mod) => {
 374             for item in &foreign_mod.items {
 375                 let def_id = tcx.hir.local_def_id(item.id);
 376                 tcx.generics_of(def_id);
 377                 tcx.type_of(def_id);
 378                 tcx.predicates_of(def_id);
 379                 if let hir::ForeignItemKind::Fn(..) = item.node {
 380                     tcx.fn_sig(def_id);
 381                 }
 382             }
 383         }
 384         hir::ItemKind::Enum(ref enum_definition, _) => {
 385             tcx.generics_of(def_id);
 386             tcx.type_of(def_id);
 387             tcx.predicates_of(def_id);
 388             convert_enum_variant_types(tcx, def_id, &enum_definition.variants);
 389         },
 390         hir::ItemKind::Impl(..) => {
 391             tcx.generics_of(def_id);
 392             tcx.type_of(def_id);
 393             tcx.impl_trait_ref(def_id);
 394             tcx.predicates_of(def_id);
 395         },
 396         hir::ItemKind::Trait(..) => {
 397             tcx.generics_of(def_id);
 398             tcx.trait_def(def_id);
 399             tcx.at(it.span).super_predicates_of(def_id);
 400             tcx.predicates_of(def_id);
 401         },
 402         hir::ItemKind::TraitAlias(..) => {
 403             span_err!(tcx.sess, it.span, E0645,
 404                       "trait aliases are not yet implemented (see issue #41517)");
 405         },
 406         hir::ItemKind::Struct(ref struct_def, _) |
 407         hir::ItemKind::Union(ref struct_def, _) => {
 408             tcx.generics_of(def_id);
 409             tcx.type_of(def_id);
 410             tcx.predicates_of(def_id);
 411
 412             for f in struct_def.fields() {
 413                 let def_id = tcx.hir.local_def_id(f.id);
 414                 tcx.generics_of(def_id);
 415                 tcx.type_of(def_id);
 416                 tcx.predicates_of(def_id);
 417             }
 418
 419             if !struct_def.is_struct() {
 420                 convert_variant_ctor(tcx, struct_def.id());
 421             }
 422         },
 423
 424         // Desugared from `impl Trait` -> visited by the function's return type
 425         hir::ItemKind::Existential(hir::ExistTy { impl_trait_fn: Some(_), .. }) => {}
 426
 427         hir::ItemKind::Existential(..) |
 428         hir::ItemKind::Ty(..) |
 429         hir::ItemKind::Static(..) |
 430         hir::ItemKind::Const(..) |
 431         hir::ItemKind::Fn(..) => {
 432             tcx.generics_of(def_id);
 433             tcx.type_of(def_id);
 434             tcx.predicates_of(def_id);
 435             if let hir::ItemKind::Fn(..) = it.node {
 436                 tcx.fn_sig(def_id);
 437             }
 438         }
 439     }
 440 }
 441
 442 fn convert_trait_item<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, trait_item_id: ast::NodeId) {
 443     let trait_item = tcx.hir.expect_trait_item(trait_item_id);
 444     let def_id = tcx.hir.local_def_id(trait_item.id);
 445     tcx.generics_of(def_id);
 446
 447     match trait_item.node {
 448         hir::TraitItemKind::Const(..) |
 449         hir::TraitItemKind::Type(_, Some(_)) |
 450         hir::TraitItemKind::Method(..) => {
 451             tcx.type_of(def_id);
 452             if let hir::TraitItemKind::Method(..) = trait_item.node {
 453                 tcx.fn_sig(def_id);
 454             }
 455         }
 456
 457         hir::TraitItemKind::Type(_, None) => {}
 458     };
 459
 460     tcx.predicates_of(def_id);
 461 }
 462
 463 fn convert_impl_item<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, impl_item_id: ast::NodeId) {
 464     let def_id = tcx.hir.local_def_id(impl_item_id);
 465     tcx.generics_of(def_id);
 466     tcx.type_of(def_id);
 467     tcx.predicates_of(def_id);
 468     if let hir::ImplItemKind::Method(..) = tcx.hir.expect_impl_item(impl_item_id).node {
 469         tcx.fn_sig(def_id);
 470     }
 471 }
 472
 473 fn convert_variant_ctor<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 474                                   ctor_id: ast::NodeId) {
 475     let def_id = tcx.hir.local_def_id(ctor_id);
 476     tcx.generics_of(def_id);
 477     tcx.type_of(def_id);
 478     tcx.predicates_of(def_id);
 479 }
 480
 481 fn convert_enum_variant_types<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 482                                         def_id: DefId,
 483                                         variants: &[hir::Variant]) {
 484     let def = tcx.adt_def(def_id);
 485     let repr_type = def.repr.discr_type();
 486     let initial = repr_type.initial_discriminant(tcx);
 487     let mut prev_discr = None::<Discr<'tcx>>;
 488
 489     // fill the discriminant values and field types
 490     for variant in variants {
 491         let wrapped_discr = prev_discr.map_or(initial, |d| d.wrap_incr(tcx));
 492         prev_discr = Some(if let Some(ref e) = variant.node.disr_expr {
 493             let expr_did = tcx.hir.local_def_id(e.id);
 494             def.eval_explicit_discr(tcx, expr_did)
 495         } else if let Some(discr) = repr_type.disr_incr(tcx, prev_discr) {
 496             Some(discr)
 497         } else {
 498             struct_span_err!(tcx.sess, variant.span, E0370,
 499                              "enum discriminant overflowed")
 500                 .span_label(variant.span, format!("overflowed on value after {}",
 501                                                    prev_discr.unwrap()))
 502                 .note(&format!("explicitly set `{} = {}` if that is desired outcome",
 503                                variant.node.name, wrapped_discr))
 504                 .emit();
 505             None
 506         }.unwrap_or(wrapped_discr));
 507
 508         for f in variant.node.data.fields() {
 509             let def_id = tcx.hir.local_def_id(f.id);
 510             tcx.generics_of(def_id);
 511             tcx.type_of(def_id);
 512             tcx.predicates_of(def_id);
 513         }
 514
 515         // Convert the ctor, if any. This also registers the variant as
 516         // an item.
 517         convert_variant_ctor(tcx, variant.node.data.id());
 518     }
 519 }
 520
 521 fn convert_struct_variant<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 522                                     did: DefId,
 523                                     name: ast::Name,
 524                                     discr: ty::VariantDiscr,
 525                                     def: &hir::VariantData)
 526                                     -> ty::VariantDef {
 527     let mut seen_fields: FxHashMap<ast::Ident, Span> = FxHashMap();
 528     let node_id = tcx.hir.as_local_node_id(did).unwrap();
 529     let fields = def.fields().iter().map(|f| {
 530         let fid = tcx.hir.local_def_id(f.id);
 531         let dup_span = seen_fields.get(&f.ident.modern()).cloned();
 532         if let Some(prev_span) = dup_span {
 533             struct_span_err!(tcx.sess, f.span, E0124,
 534                              "field `{}` is already declared",
 535                              f.ident)
 536                 .span_label(f.span, "field already declared")
 537                 .span_label(prev_span, format!("`{}` first declared here", f.ident))
 538                 .emit();
 539         } else {
 540             seen_fields.insert(f.ident.modern(), f.span);
 541         }
 542
 543         ty::FieldDef {
 544             did: fid,
 545             ident: f.ident,
 546             vis: ty::Visibility::from_hir(&f.vis, node_id, tcx)
 547         }
 548     }).collect();
 549     ty::VariantDef {
 550         did,
 551         name,
 552         discr,
 553         fields,
 554         ctor_kind: CtorKind::from_hir(def),
 555     }
 556 }
 557
 558 fn adt_def<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 559                      def_id: DefId)
 560                      -> &'tcx ty::AdtDef {
 561     use rustc::hir::map::*;
 562     use rustc::hir::*;
 563
 564     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
 565     let item = match tcx.hir.get(node_id) {
 566         NodeItem(item) => item,
 567         _ => bug!()
 568     };
 569
 570     let repr = ReprOptions::new(tcx, def_id);
 571     let (kind, variants) = match item.node {
 572         ItemKind::Enum(ref def, _) => {
 573             let mut distance_from_explicit = 0;
 574             (AdtKind::Enum, def.variants.iter().map(|v| {
 575                 let did = tcx.hir.local_def_id(v.node.data.id());
 576                 let discr = if let Some(ref e) = v.node.disr_expr {
 577                     distance_from_explicit = 0;
 578                     ty::VariantDiscr::Explicit(tcx.hir.local_def_id(e.id))
 579                 } else {
 580                     ty::VariantDiscr::Relative(distance_from_explicit)
 581                 };
 582                 distance_from_explicit += 1;
 583
 584                 convert_struct_variant(tcx, did, v.node.name, discr, &v.node.data)
 585             }).collect())
 586         }
 587         ItemKind::Struct(ref def, _) => {
 588             // Use separate constructor id for unit/tuple structs and reuse did for braced structs.
 589             let ctor_id = if !def.is_struct() {
 590                 Some(tcx.hir.local_def_id(def.id()))
 591             } else {
 592                 None
 593             };
 594             (AdtKind::Struct, vec![
 595                 convert_struct_variant(tcx, ctor_id.unwrap_or(def_id), item.name,
 596                                        ty::VariantDiscr::Relative(0), def)
 597             ])
 598         }
 599         ItemKind::Union(ref def, _) => {
 600             (AdtKind::Union, vec![
 601                 convert_struct_variant(tcx, def_id, item.name,
 602                                        ty::VariantDiscr::Relative(0), def)
 603             ])
 604         }
 605         _ => bug!()
 606     };
 607     tcx.alloc_adt_def(def_id, kind, variants, repr)
 608 }
 609
 610 /// Ensures that the super-predicates of the trait with def-id
 611 /// trait_def_id are converted and stored. This also ensures that
 612 /// the transitive super-predicates are converted;
 613 fn super_predicates_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 614                                  trait_def_id: DefId)
 615                                  -> ty::GenericPredicates<'tcx> {
 616     debug!("super_predicates(trait_def_id={:?})", trait_def_id);
 617     let trait_node_id = tcx.hir.as_local_node_id(trait_def_id).unwrap();
 618
 619     let item = match tcx.hir.get(trait_node_id) {
 620         hir_map::NodeItem(item) => item,
 621         _ => bug!("trait_node_id {} is not an item", trait_node_id)
 622     };
 623
 624     let (generics, bounds) = match item.node {
 625         hir::ItemKind::Trait(.., ref generics, ref supertraits, _) => (generics, supertraits),
 626         hir::ItemKind::TraitAlias(ref generics, ref supertraits) => (generics, supertraits),
 627         _ => span_bug!(item.span,
 628                        "super_predicates invoked on non-trait"),
 629     };
 630
 631     let icx = ItemCtxt::new(tcx, trait_def_id);
 632
 633     // Convert the bounds that follow the colon, e.g. `Bar+Zed` in `trait Foo : Bar+Zed`.
 634     let self_param_ty = tcx.mk_self_type();
 635     let superbounds1 = compute_bounds(&icx,
 636                                       self_param_ty,
 637                                       bounds,
 638                                       SizedByDefault::No,
 639                                       item.span);
 640
 641     let superbounds1 = superbounds1.predicates(tcx, self_param_ty);
 642
 643     // Convert any explicit superbounds in the where clause,
 644     // e.g. `trait Foo where Self : Bar`:
 645     let superbounds2 = icx.type_parameter_bounds_in_generics(generics, item.id, self_param_ty);
 646
 647     // Combine the two lists to form the complete set of superbounds:
 648     let superbounds: Vec<_> = superbounds1.into_iter().chain(superbounds2).collect();
 649
 650     // Now require that immediate supertraits are converted,
 651     // which will, in turn, reach indirect supertraits.
 652     for bound in superbounds.iter().filter_map(|p| p.to_opt_poly_trait_ref()) {
 653         tcx.at(item.span).super_predicates_of(bound.def_id());
 654     }
 655
 656     ty::GenericPredicates {
 657         parent: None,
 658         predicates: superbounds
 659     }
 660 }
 661
 662 fn trait_def<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 663                        def_id: DefId)
 664                        -> &'tcx ty::TraitDef {
 665     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
 666     let item = tcx.hir.expect_item(node_id);
 667
 668     let (is_auto, unsafety) = match item.node {
 669         hir::ItemKind::Trait(is_auto, unsafety, ..) => (is_auto == hir::IsAuto::Yes, unsafety),
 670         hir::ItemKind::TraitAlias(..) => (false, hir::Unsafety::Normal),
 671         _ => span_bug!(item.span, "trait_def_of_item invoked on non-trait"),
 672     };
 673
 674     let paren_sugar = tcx.has_attr(def_id, "rustc_paren_sugar");
 675     if paren_sugar && !tcx.features().unboxed_closures {
 676         let mut err = tcx.sess.struct_span_err(
 677             item.span,
 678             "the `#[rustc_paren_sugar]` attribute is a temporary means of controlling \
 679              which traits can use parenthetical notation");
 680         help!(&mut err,
 681             "add `#![feature(unboxed_closures)]` to \
 682              the crate attributes to use it");
 683         err.emit();
 684     }
 685
 686     let def_path_hash = tcx.def_path_hash(def_id);
 687     let def = ty::TraitDef::new(def_id,
 688                                 unsafety,
 689                                 paren_sugar,
 690                                 is_auto,
 691                                 def_path_hash);
 692     tcx.alloc_trait_def(def)
 693 }
 694
 695 fn has_late_bound_regions<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 696                                     node: hir_map::Node<'tcx>)
 697                                     -> Option<Span> {
 698     struct LateBoundRegionsDetector<'a, 'tcx: 'a> {
 699         tcx: TyCtxt<'a, 'tcx, 'tcx>,
 700         outer_index: ty::DebruijnIndex,
 701         has_late_bound_regions: Option<Span>,
 702     }
 703
 704     impl<'a, 'tcx> Visitor<'tcx> for LateBoundRegionsDetector<'a, 'tcx> {
 705         fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
 706             NestedVisitorMap::None
 707         }
 708
 709         fn visit_ty(&mut self, ty: &'tcx hir::Ty) {
 710             if self.has_late_bound_regions.is_some() { return }
 711             match ty.node {
 712                 hir::TyKind::BareFn(..) => {
 713                     self.outer_index.shift_in(1);
 714                     intravisit::walk_ty(self, ty);
 715                     self.outer_index.shift_out(1);
 716                 }
 717                 _ => intravisit::walk_ty(self, ty)
 718             }
 719         }
 720
 721         fn visit_poly_trait_ref(&mut self,
 722                                 tr: &'tcx hir::PolyTraitRef,
 723                                 m: hir::TraitBoundModifier) {
 724             if self.has_late_bound_regions.is_some() { return }
 725             self.outer_index.shift_in(1);
 726             intravisit::walk_poly_trait_ref(self, tr, m);
 727             self.outer_index.shift_out(1);
 728         }
 729
 730         fn visit_lifetime(&mut self, lt: &'tcx hir::Lifetime) {
 731             if self.has_late_bound_regions.is_some() { return }
 732
 733             let hir_id = self.tcx.hir.node_to_hir_id(lt.id);
 734             match self.tcx.named_region(hir_id) {
 735                 Some(rl::Region::Static) | Some(rl::Region::EarlyBound(..)) => {}
 736                 Some(rl::Region::LateBound(debruijn, _, _)) |
 737                 Some(rl::Region::LateBoundAnon(debruijn, _))
 738                     if debruijn < self.outer_index => {}
 739                 Some(rl::Region::LateBound(..)) |
 740                 Some(rl::Region::LateBoundAnon(..)) |
 741                 Some(rl::Region::Free(..)) |
 742                 None => {
 743                     self.has_late_bound_regions = Some(lt.span);
 744                 }
 745             }
 746         }
 747     }
 748
 749     fn has_late_bound_regions<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 750                                         generics: &'tcx hir::Generics,
 751                                         decl: &'tcx hir::FnDecl)
 752                                         -> Option<Span> {
 753         let mut visitor = LateBoundRegionsDetector {
 754             tcx,
 755             outer_index: ty::INNERMOST,
 756             has_late_bound_regions: None,
 757         };
 758         for param in &generics.params {
 759             match param.kind {
 760                 GenericParamKind::Lifetime { .. } => {
 761                     let hir_id = tcx.hir.node_to_hir_id(param.id);
 762                     if tcx.is_late_bound(hir_id) {
 763                         return Some(param.span);
 764                     }
 765                 }
 766                 _ => {},
 767             }
 768         }
 769         visitor.visit_fn_decl(decl);
 770         visitor.has_late_bound_regions
 771     }
 772
 773     match node {
 774         hir_map::NodeTraitItem(item) => match item.node {
 775             hir::TraitItemKind::Method(ref sig, _) =>
 776                 has_late_bound_regions(tcx, &item.generics, &sig.decl),
 777             _ => None,
 778         },
 779         hir_map::NodeImplItem(item) => match item.node {
 780             hir::ImplItemKind::Method(ref sig, _) =>
 781                 has_late_bound_regions(tcx, &item.generics, &sig.decl),
 782             _ => None,
 783         },
 784         hir_map::NodeForeignItem(item) => match item.node {
 785             hir::ForeignItemKind::Fn(ref fn_decl, _, ref generics) =>
 786                 has_late_bound_regions(tcx, generics, fn_decl),
 787             _ => None,
 788         },
 789         hir_map::NodeItem(item) => match item.node {
 790             hir::ItemKind::Fn(ref fn_decl, .., ref generics, _) =>
 791                 has_late_bound_regions(tcx, generics, fn_decl),
 792             _ => None,
 793         },
 794         _ => None
 795     }
 796 }
 797
 798 fn generics_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 799                          def_id: DefId)
 800                          -> &'tcx ty::Generics {
 801     use rustc::hir::map::*;
 802     use rustc::hir::*;
 803
 804     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
 805
 806     let node = tcx.hir.get(node_id);
 807     let parent_def_id = match node {
 808         NodeImplItem(_) |
 809         NodeTraitItem(_) |
 810         NodeVariant(_) |
 811         NodeStructCtor(_) |
 812         NodeField(_) => {
 813             let parent_id = tcx.hir.get_parent(node_id);
 814             Some(tcx.hir.local_def_id(parent_id))
 815         }
 816         NodeExpr(&hir::Expr { node: hir::ExprKind::Closure(..), .. }) => {
 817             Some(tcx.closure_base_def_id(def_id))
 818         }
 819         NodeItem(item) => {
 820             match item.node {
 821                 ItemKind::Existential(hir::ExistTy { impl_trait_fn, .. }) => impl_trait_fn,
 822                 _ => None,
 823             }
 824         },
 825         _ => None
 826     };
 827
 828     let mut opt_self = None;
 829     let mut allow_defaults = false;
 830
 831     let no_generics = hir::Generics::empty();
 832     let ast_generics = match node {
 833         NodeTraitItem(item) => &item.generics,
 834
 835         NodeImplItem(item) => &item.generics,
 836
 837         NodeItem(item) => {
 838             match item.node {
 839                 ItemKind::Fn(.., ref generics, _) |
 840                 ItemKind::Impl(_, _, _, ref generics, ..) => generics,
 841
 842                 ItemKind::Ty(_, ref generics) |
 843                 ItemKind::Enum(_, ref generics) |
 844                 ItemKind::Struct(_, ref generics) |
 845                 ItemKind::Existential(hir::ExistTy { ref generics, .. }) |
 846                 ItemKind::Union(_, ref generics) => {
 847                     allow_defaults = true;
 848                     generics
 849                 }
 850
 851                 ItemKind::Trait(_, _, ref generics, ..) |
 852                 ItemKind::TraitAlias(ref generics, ..) => {
 853                     // Add in the self type parameter.
 854                     //
 855                     // Something of a hack: use the node id for the trait, also as
 856                     // the node id for the Self type parameter.
 857                     let param_id = item.id;
 858
 859                     opt_self = Some(ty::GenericParamDef {
 860                         index: 0,
 861                         name: keywords::SelfType.name().as_interned_str(),
 862                         def_id: tcx.hir.local_def_id(param_id),
 863                         pure_wrt_drop: false,
 864                         kind: ty::GenericParamDefKind::Type {
 865                             has_default: false,
 866                             object_lifetime_default: rl::Set1::Empty,
 867                             synthetic: None,
 868                         },
 869                     });
 870
 871                     allow_defaults = true;
 872                     generics
 873                 }
 874
 875                 _ => &no_generics,
 876             }
 877         }
 878
 879         NodeForeignItem(item) => {
 880             match item.node {
 881                 ForeignItemKind::Static(..) => &no_generics,
 882                 ForeignItemKind::Fn(_, _, ref generics) => generics,
 883                 ForeignItemKind::Type => &no_generics,
 884             }
 885         }
 886
 887         _ => &no_generics,
 888     };
 889
 890     let has_self = opt_self.is_some();
 891     let mut parent_has_self = false;
 892     let mut own_start = has_self as u32;
 893     let parent_count = parent_def_id.map_or(0, |def_id| {
 894         let generics = tcx.generics_of(def_id);
 895         assert_eq!(has_self, false);
 896         parent_has_self = generics.has_self;
 897         own_start = generics.count() as u32;
 898         generics.parent_count + generics.params.len()
 899     });
 900
 901     let mut params: Vec<_> = opt_self.into_iter().collect();
 902
 903     let early_lifetimes = early_bound_lifetimes_from_generics(tcx, ast_generics);
 904     params.extend(early_lifetimes.enumerate().map(|(i, param)| {
 905         ty::GenericParamDef {
 906             name: param.name.ident().as_interned_str(),
 907             index: own_start + i as u32,
 908             def_id: tcx.hir.local_def_id(param.id),
 909             pure_wrt_drop: param.pure_wrt_drop,
 910             kind: ty::GenericParamDefKind::Lifetime,
 911         }
 912     }));
 913
 914     let hir_id = tcx.hir.node_to_hir_id(node_id);
 915     let object_lifetime_defaults = tcx.object_lifetime_defaults(hir_id);
 916
 917     // Now create the real type parameters.
 918     let type_start = own_start - has_self as u32 + params.len() as u32;
 919     let mut i = 0;
 920     params.extend(ast_generics.params.iter().filter_map(|param| match param.kind {
 921         GenericParamKind::Type { ref default, synthetic, .. } => {
 922             if param.name.ident().name == keywords::SelfType.name() {
 923                 span_bug!(param.span,  "`Self` should not be the name of a regular parameter");
 924             }
 925
 926             if !allow_defaults && default.is_some() {
 927                 if !tcx.features().default_type_parameter_fallback {
 928                     tcx.lint_node(
 929                         lint::builtin::INVALID_TYPE_PARAM_DEFAULT,
 930                         param.id,
 931                         param.span,
 932                         &format!("defaults for type parameters are only allowed in \
 933                                     `struct`, `enum`, `type`, or `trait` definitions."));
 934                 }
 935             }
 936
 937             let ty_param = ty::GenericParamDef {
 938                 index: type_start + i as u32,
 939                 name: param.name.ident().as_interned_str(),
 940                 def_id: tcx.hir.local_def_id(param.id),
 941                 pure_wrt_drop: param.pure_wrt_drop,
 942                 kind: ty::GenericParamDefKind::Type {
 943                     has_default: default.is_some(),
 944                     object_lifetime_default:
 945                         object_lifetime_defaults.as_ref().map_or(rl::Set1::Empty, |o| o[i]),
 946                     synthetic,
 947                 },
 948             };
 949             i += 1;
 950             Some(ty_param)
 951         }
 952         _ => None,
 953     }));
 954
 955     // provide junk type parameter defs - the only place that
 956     // cares about anything but the length is instantiation,
 957     // and we don't do that for closures.
 958     if let NodeExpr(&hir::Expr { node: hir::ExprKind::Closure(.., gen), .. }) = node {
 959         let dummy_args = if gen.is_some() {
 960             &["<yield_ty>", "<return_ty>", "<witness>"][..]
 961         } else {
 962             &["<closure_kind>", "<closure_signature>"][..]
 963         };
 964
 965         for (i, &arg) in dummy_args.iter().enumerate() {
 966             params.push(ty::GenericParamDef {
 967                 index: type_start + i as u32,
 968                 name: Symbol::intern(arg).as_interned_str(),
 969                 def_id,
 970                 pure_wrt_drop: false,
 971                 kind: ty::GenericParamDefKind::Type {
 972                     has_default: false,
 973                     object_lifetime_default: rl::Set1::Empty,
 974                     synthetic: None,
 975                 },
 976             });
 977         }
 978
 979         tcx.with_freevars(node_id, |fv| {
 980             params.extend(fv.iter().zip((dummy_args.len() as u32)..).map(|(_, i)| {
 981                 ty::GenericParamDef {
 982                     index: type_start + i,
 983                     name: Symbol::intern("<upvar>").as_interned_str(),
 984                     def_id,
 985                     pure_wrt_drop: false,
 986                     kind: ty::GenericParamDefKind::Type {
 987                         has_default: false,
 988                         object_lifetime_default: rl::Set1::Empty,
 989                         synthetic: None,
 990                     },
 991                 }
 992             }));
 993         });
 994     }
 995
 996     let param_def_id_to_index = params.iter()
 997                                       .map(|param| (param.def_id, param.index))
 998                                       .collect();
 999
1000     tcx.alloc_generics(ty::Generics {
1001         parent: parent_def_id,
1002         parent_count,
1003         params,
1004         param_def_id_to_index,
1005         has_self: has_self || parent_has_self,
1006         has_late_bound_regions: has_late_bound_regions(tcx, node),
1007     })
1008 }
1009
1010 fn report_assoc_ty_on_inherent_impl<'a, 'tcx>(
1011     tcx: TyCtxt<'a, 'tcx, 'tcx>,
1012     span: Span,
1013 ) {
1014     span_err!(tcx.sess, span, E0202, "associated types are not allowed in inherent impls");
1015 }
1016
1017 fn type_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
1018                      def_id: DefId)
1019                      -> Ty<'tcx> {
1020     use rustc::hir::map::*;
1021     use rustc::hir::*;
1022
1023     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
1024
1025     let icx = ItemCtxt::new(tcx, def_id);
1026
1027     match tcx.hir.get(node_id) {
1028         NodeTraitItem(item) => {
1029             match item.node {
1030                 TraitItemKind::Method(..) => {
1031                     let substs = Substs::identity_for_item(tcx, def_id);
1032                     tcx.mk_fn_def(def_id, substs)
1033                 }
1034                 TraitItemKind::Const(ref ty, _) |
1035                 TraitItemKind::Type(_, Some(ref ty)) => icx.to_ty(ty),
1036                 TraitItemKind::Type(_, None) => {
1037                     span_bug!(item.span, "associated type missing default");
1038                 }
1039             }
1040         }
1041
1042         NodeImplItem(item) => {
1043             match item.node {
1044                 ImplItemKind::Method(..) => {
1045                     let substs = Substs::identity_for_item(tcx, def_id);
1046                     tcx.mk_fn_def(def_id, substs)
1047                 }
1048                 ImplItemKind::Const(ref ty, _) => icx.to_ty(ty),
1049                 ImplItemKind::Existential(ref _bounds) => {
1050                     if tcx.impl_trait_ref(tcx.hir.get_parent_did(node_id)).is_none() {
1051                         report_assoc_ty_on_inherent_impl(tcx, item.span);
1052                     }
1053                     // FIXME(oli-obk) implement existential types in trait impls
1054                     unimplemented!()
1055                 }
1056                 ImplItemKind::Type(ref ty) => {
1057                     if tcx.impl_trait_ref(tcx.hir.get_parent_did(node_id)).is_none() {
1058                         report_assoc_ty_on_inherent_impl(tcx, item.span);
1059                     }
1060
1061                     icx.to_ty(ty)
1062                 }
1063             }
1064         }
1065
1066         NodeItem(item) => {
1067             match item.node {
1068                 ItemKind::Static(ref t, ..) | ItemKind::Const(ref t, _) |
1069                 ItemKind::Ty(ref t, _) | ItemKind::Impl(.., ref t, _) => {
1070                     icx.to_ty(t)
1071                 }
1072                 ItemKind::Fn(..) => {
1073                     let substs = Substs::identity_for_item(tcx, def_id);
1074                     tcx.mk_fn_def(def_id, substs)
1075                 }
1076                 ItemKind::Enum(..) |
1077                 ItemKind::Struct(..) |
1078                 ItemKind::Union(..) => {
1079                     let def = tcx.adt_def(def_id);
1080                     let substs = Substs::identity_for_item(tcx, def_id);
1081                     tcx.mk_adt(def, substs)
1082                 }
1083                 ItemKind::Existential(hir::ExistTy { impl_trait_fn: None, .. }) => {
1084                     find_existential_constraints(tcx, def_id)
1085                 },
1086                 // existential types desugared from impl Trait
1087                 ItemKind::Existential(hir::ExistTy { impl_trait_fn: Some(owner), .. }) => {
1088                     tcx.typeck_tables_of(owner).concrete_existential_types[&def_id]
1089                 },
1090                 ItemKind::Trait(..) | ItemKind::TraitAlias(..) |
1091                 ItemKind::Mod(..) |
1092                 ItemKind::ForeignMod(..) |
1093                 ItemKind::GlobalAsm(..) |
1094                 ItemKind::ExternCrate(..) |
1095                 ItemKind::Use(..) => {
1096                     span_bug!(
1097                         item.span,
1098                         "compute_type_of_item: unexpected item type: {:?}",
1099                         item.node);
1100                 }
1101             }
1102         }
1103
1104         NodeForeignItem(foreign_item) => {
1105             match foreign_item.node {
1106                 ForeignItemKind::Fn(..) => {
1107                     let substs = Substs::identity_for_item(tcx, def_id);
1108                     tcx.mk_fn_def(def_id, substs)
1109                 }
1110                 ForeignItemKind::Static(ref t, _) => icx.to_ty(t),
1111                 ForeignItemKind::Type => tcx.mk_foreign(def_id),
1112             }
1113         }
1114
1115         NodeStructCtor(&ref def) |
1116         NodeVariant(&Spanned { node: hir::VariantKind { data: ref def, .. }, .. }) => {
1117             match *def {
1118                 VariantData::Unit(..) | VariantData::Struct(..) => {
1119                     tcx.type_of(tcx.hir.get_parent_did(node_id))
1120                 }
1121                 VariantData::Tuple(..) => {
1122                     let substs = Substs::identity_for_item(tcx, def_id);
1123                     tcx.mk_fn_def(def_id, substs)
1124                 }
1125             }
1126         }
1127
1128         NodeField(field) => icx.to_ty(&field.ty),
1129
1130         NodeExpr(&hir::Expr { node: hir::ExprKind::Closure(.., gen), .. }) => {
1131             if gen.is_some() {
1132                 let hir_id = tcx.hir.node_to_hir_id(node_id);
1133                 return tcx.typeck_tables_of(def_id).node_id_to_type(hir_id);
1134             }
1135
1136             let substs = ty::ClosureSubsts {
1137                 substs: Substs::identity_for_item(tcx, def_id),
1138             };
1139
1140             tcx.mk_closure(def_id, substs)
1141         }
1142
1143         NodeAnonConst(_) => match tcx.hir.get(tcx.hir.get_parent_node(node_id)) {
1144             NodeTy(&hir::Ty { node: hir::TyKind::Array(_, ref constant), .. }) |
1145             NodeTy(&hir::Ty { node: hir::TyKind::Typeof(ref constant), .. }) |
1146             NodeExpr(&hir::Expr { node: ExprKind::Repeat(_, ref constant), .. })
1147                 if constant.id == node_id => tcx.types.usize,
1148
1149             NodeVariant(&Spanned { node: VariantKind { disr_expr: Some(ref e), .. }, .. })
1150                 if e.id == node_id => {
1151                     tcx.adt_def(tcx.hir.get_parent_did(node_id))
1152                         .repr.discr_type().to_ty(tcx)
1153                 }
1154
1155             x => {
1156                 bug!("unexpected const parent in type_of_def_id(): {:?}", x);
1157             }
1158         },
1159
1160         NodeGenericParam(param) => {
1161             match param.kind {
1162                 hir::GenericParamKind::Type { default: Some(ref ty), .. } => {
1163                     icx.to_ty(ty)
1164                 }
1165                 _ => bug!("unexpected non-type NodeGenericParam"),
1166             }
1167         }
1168
1169         x => {
1170             bug!("unexpected sort of node in type_of_def_id(): {:?}", x);
1171         }
1172     }
1173 }
1174
1175 fn find_existential_constraints<'a, 'tcx>(
1176     tcx: TyCtxt<'a, 'tcx, 'tcx>,
1177     def_id: DefId,
1178 ) -> ty::Ty<'tcx> {
1179     use rustc::hir::map::*;
1180     use rustc::hir::*;
1181
1182     struct ConstraintLocator<'a, 'tcx: 'a> {
1183         tcx: TyCtxt<'a, 'tcx, 'tcx>,
1184         def_id: DefId,
1185         found: Option<(Span, ty::Ty<'tcx>)>,
1186     }
1187     impl<'a, 'tcx> ConstraintLocator<'a, 'tcx> {
1188         fn check(&mut self, node_id: ast::NodeId) {
1189             let def_id = self.tcx.hir.local_def_id(node_id);
1190             // don't try to check items that cannot possibly constrain the type
1191             if !self.tcx.has_typeck_tables(def_id) {
1192                 return;
1193             }
1194             let ty = self
1195                 .tcx
1196                 .typeck_tables_of(def_id)
1197                 .concrete_existential_types
1198                 .get(&self.def_id)
1199                 .cloned();
1200             if let Some(ty) = ty {
1201                 // FIXME(oli-obk): trace the actual span from inference to improve errors
1202                 let span = self.tcx.def_span(def_id);
1203                 if let Some((prev_span, prev_ty)) = self.found {
1204                     if ty != prev_ty {
1205                         // found different concrete types for the existential type
1206                         let mut err = self.tcx.sess.struct_span_err(
1207                             span,
1208                             "defining existential type use differs from previous",
1209                         );
1210                         err.span_note(prev_span, "previous use here");
1211                         err.emit();
1212                     }
1213                 } else {
1214                     self.found = Some((span, ty));
1215                 }
1216             }
1217         }
1218     }
1219     impl<'a, 'tcx> intravisit::Visitor<'tcx> for ConstraintLocator<'a, 'tcx> {
1220         fn nested_visit_map<'this>(&'this mut self) -> intravisit::NestedVisitorMap<'this, 'tcx> {
1221             intravisit::NestedVisitorMap::All(&self.tcx.hir)
1222         }
1223         fn visit_item(&mut self, it: &'tcx Item) {
1224             // the existential type itself or its children are not within its reveal scope
1225             if self.tcx.hir.local_def_id(it.id) != self.def_id {
1226                 self.check(it.id);
1227                 intravisit::walk_item(self, it);
1228             }
1229         }
1230         fn visit_impl_item(&mut self, it: &'tcx ImplItem) {
1231             // the existential type itself or its children are not within its reveal scope
1232             if self.tcx.hir.local_def_id(it.id) != self.def_id {
1233                 self.check(it.id);
1234                 intravisit::walk_impl_item(self, it);
1235             }
1236         }
1237         fn visit_trait_item(&mut self, it: &'tcx TraitItem) {
1238             self.check(it.id);
1239             intravisit::walk_trait_item(self, it);
1240         }
1241     }
1242     let mut locator = ConstraintLocator { def_id, tcx, found: None };
1243     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
1244     let parent = tcx.hir.get_parent(node_id);
1245     if parent == ast::CRATE_NODE_ID {
1246         intravisit::walk_crate(&mut locator, tcx.hir.krate());
1247     } else {
1248         match tcx.hir.get(parent) {
1249             NodeItem(ref it) => intravisit::walk_item(&mut locator, it),
1250             NodeImplItem(ref it) => intravisit::walk_impl_item(&mut locator, it),
1251             other => bug!("{:?} is not a valid parent of an existential type item", other),
1252         }
1253     }
1254     match locator.found {
1255         Some((_, ty)) => ty,
1256         None => {
1257             let span = tcx.def_span(def_id);
1258             tcx.sess.span_err(span, "could not find defining uses");
1259             tcx.types.err
1260         }
1261     }
1262 }
1263
1264 fn fn_sig<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
1265                     def_id: DefId)
1266                     -> ty::PolyFnSig<'tcx> {
1267     use rustc::hir::map::*;
1268     use rustc::hir::*;
1269
1270     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
1271
1272     let icx = ItemCtxt::new(tcx, def_id);
1273
1274     match tcx.hir.get(node_id) {
1275         NodeTraitItem(hir::TraitItem { node: TraitItemKind::Method(sig, _), .. }) |
1276         NodeImplItem(hir::ImplItem { node: ImplItemKind::Method(sig, _), .. }) => {
1277             AstConv::ty_of_fn(&icx, sig.header.unsafety, sig.header.abi, &sig.decl)
1278         }
1279
1280         NodeItem(hir::Item { node: ItemKind::Fn(decl, header, _, _), .. }) => {
1281             AstConv::ty_of_fn(&icx, header.unsafety, header.abi, decl)
1282         }
1283
1284         NodeForeignItem(&hir::ForeignItem { node: ForeignItemKind::Fn(ref fn_decl, _, _), .. }) => {
1285             let abi = tcx.hir.get_foreign_abi(node_id);
1286             compute_sig_of_foreign_fn_decl(tcx, def_id, fn_decl, abi)
1287         }
1288
1289         NodeStructCtor(&VariantData::Tuple(ref fields, _)) |
1290         NodeVariant(&Spanned { node: hir::VariantKind {
1291             data: VariantData::Tuple(ref fields, _), ..
1292         }, .. }) => {
1293             let ty = tcx.type_of(tcx.hir.get_parent_did(node_id));
1294             let inputs = fields.iter().map(|f| {
1295                 tcx.type_of(tcx.hir.local_def_id(f.id))
1296             });
1297             ty::Binder::bind(tcx.mk_fn_sig(
1298                 inputs,
1299                 ty,
1300                 false,
1301                 hir::Unsafety::Normal,
1302                 abi::Abi::Rust
1303             ))
1304         }
1305
1306         NodeExpr(&hir::Expr { node: hir::ExprKind::Closure(..), .. }) => {
1307             // Closure signatures are not like other function
1308             // signatures and cannot be accessed through `fn_sig`. For
1309             // example, a closure signature excludes the `self`
1310             // argument. In any case they are embedded within the
1311             // closure type as part of the `ClosureSubsts`.
1312             //
1313             // To get
1314             // the signature of a closure, you should use the
1315             // `closure_sig` method on the `ClosureSubsts`:
1316             //
1317             //    closure_substs.closure_sig(def_id, tcx)
1318             //
1319             // or, inside of an inference context, you can use
1320             //
1321             //    infcx.closure_sig(def_id, closure_substs)
1322             bug!("to get the signature of a closure, use `closure_sig()` not `fn_sig()`");
1323         }
1324
1325         x => {
1326             bug!("unexpected sort of node in fn_sig(): {:?}", x);
1327         }
1328     }
1329 }
1330
1331 fn impl_trait_ref<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
1332                             def_id: DefId)
1333                             -> Option<ty::TraitRef<'tcx>> {
1334     let icx = ItemCtxt::new(tcx, def_id);
1335
1336     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
1337     match tcx.hir.expect_item(node_id).node {
1338         hir::ItemKind::Impl(.., ref opt_trait_ref, _, _) => {
1339             opt_trait_ref.as_ref().map(|ast_trait_ref| {
1340                 let selfty = tcx.type_of(def_id);
1341                 AstConv::instantiate_mono_trait_ref(&icx, ast_trait_ref, selfty)
1342             })
1343         }
1344         _ => bug!()
1345     }
1346 }
1347
1348 fn impl_polarity<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
1349                            def_id: DefId)
1350                            -> hir::ImplPolarity {
1351     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
1352     match tcx.hir.expect_item(node_id).node {
1353         hir::ItemKind::Impl(_, polarity, ..) => polarity,
1354         ref item => bug!("impl_polarity: {:?} not an impl", item)
1355     }
1356 }
1357
1358 // Is it marked with ?Sized
1359 fn is_unsized<'gcx: 'tcx, 'tcx>(astconv: &dyn AstConv<'gcx, 'tcx>,
1360                                 ast_bounds: &[hir::GenericBound],
1361                                 span: Span) -> bool
1362 {
1363     let tcx = astconv.tcx();
1364
1365     // Try to find an unbound in bounds.
1366     let mut unbound = None;
1367     for ab in ast_bounds {
1368         if let &hir::GenericBound::Trait(ref ptr, hir::TraitBoundModifier::Maybe) = ab  {
1369             if unbound.is_none() {
1370                 unbound = Some(ptr.trait_ref.clone());
1371             } else {
1372                 span_err!(tcx.sess, span, E0203,
1373                           "type parameter has more than one relaxed default \
1374                                                 bound, only one is supported");
1375             }
1376         }
1377     }
1378
1379     let kind_id = tcx.lang_items().require(SizedTraitLangItem);
1380     match unbound {
1381         Some(ref tpb) => {
1382             // FIXME(#8559) currently requires the unbound to be built-in.
1383             if let Ok(kind_id) = kind_id {
1384                 if tpb.path.def != Def::Trait(kind_id) {
1385                     tcx.sess.span_warn(span,
1386                                        "default bound relaxed for a type parameter, but \
1387                                        this does nothing because the given bound is not \
1388                                        a default. Only `?Sized` is supported");
1389                 }
1390             }
1391         }
1392         _ if kind_id.is_ok() => {
1393             return false;
1394         }
1395         // No lang item for Sized, so we can't add it as a bound.
1396         None => {}
1397     }
1398
1399     true
1400 }
1401
1402 /// Returns the early-bound lifetimes declared in this generics
1403 /// listing.  For anything other than fns/methods, this is just all
1404 /// the lifetimes that are declared. For fns or methods, we have to
1405 /// screen out those that do not appear in any where-clauses etc using
1406 /// `resolve_lifetime::early_bound_lifetimes`.
1407 fn early_bound_lifetimes_from_generics<'a, 'tcx>(
1408     tcx: TyCtxt<'a, 'tcx, 'tcx>,
1409     generics: &'a hir::Generics)
1410     -> impl Iterator<Item=&'a hir::GenericParam> + Captures<'tcx>
1411 {
1412     generics.params.iter().filter(move |param| match param.kind {
1413         GenericParamKind::Lifetime { .. } => {
1414             let hir_id = tcx.hir.node_to_hir_id(param.id);
1415             !tcx.is_late_bound(hir_id)
1416         }
1417         _ => false,
1418     })
1419 }
1420
1421 fn predicates_defined_on<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
1422                                    def_id: DefId)
1423                                    -> ty::GenericPredicates<'tcx> {
1424     let explicit = tcx.explicit_predicates_of(def_id);
1425     let predicates = if tcx.sess.features_untracked().infer_outlives_requirements {
1426         [&explicit.predicates[..], &tcx.inferred_outlives_of(def_id)[..]].concat()
1427     } else { explicit.predicates };
1428
1429     ty::GenericPredicates {
1430         parent: explicit.parent,
1431         predicates: predicates,
1432     }
1433 }
1434
1435 fn predicates_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
1436                            def_id: DefId)
1437                            -> ty::GenericPredicates<'tcx> {
1438     let ty::GenericPredicates { parent, mut predicates } =
1439         tcx.predicates_defined_on(def_id);
1440
1441     if tcx.is_trait(def_id) {
1442         // For traits, add `Self: Trait` predicate. This is
1443         // not part of the predicates that a user writes, but it
1444         // is something that one must prove in order to invoke a
1445         // method or project an associated type.
1446         //
1447         // In the chalk setup, this predicate is not part of the
1448         // "predicates" for a trait item. But it is useful in
1449         // rustc because if you directly (e.g.) invoke a trait
1450         // method like `Trait::method(...)`, you must naturally
1451         // prove that the trait applies to the types that were
1452         // used, and adding the predicate into this list ensures
1453         // that this is done.
1454         predicates.push(ty::TraitRef::identity(tcx, def_id).to_predicate());
1455     }
1456
1457     ty::GenericPredicates { parent, predicates }
1458 }
1459
1460 fn explicit_predicates_of<'a, 'tcx>(
1461     tcx: TyCtxt<'a, 'tcx, 'tcx>,
1462     def_id: DefId,
1463 ) -> ty::GenericPredicates<'tcx> {
1464     use rustc::hir::map::*;
1465     use rustc::hir::*;
1466
1467     debug!("explicit_predicates_of(def_id={:?})", def_id);
1468
1469     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
1470     let node = tcx.hir.get(node_id);
1471
1472     let mut is_trait = None;
1473     let mut is_default_impl_trait = None;
1474
1475     let icx = ItemCtxt::new(tcx, def_id);
1476     let no_generics = hir::Generics::empty();
1477
1478     let mut predicates = vec![];
1479
1480     let ast_generics = match node {
1481         NodeTraitItem(item) => {
1482             &item.generics
1483         }
1484
1485         NodeImplItem(item) => &item.generics,
1486
1487         NodeItem(item) => {
1488             match item.node {
1489                 ItemKind::Impl(_, _, defaultness, ref generics, ..) => {
1490                     if defaultness.is_default() {
1491                         is_default_impl_trait = tcx.impl_trait_ref(def_id);
1492                     }
1493                     generics
1494                 }
1495                 ItemKind::Fn(.., ref generics, _) |
1496                 ItemKind::Ty(_, ref generics) |
1497                 ItemKind::Enum(_, ref generics) |
1498                 ItemKind::Struct(_, ref generics) |
1499                 ItemKind::Union(_, ref generics) => generics,
1500
1501                 ItemKind::Trait(_, _, ref generics, .., ref items) => {
1502                     is_trait = Some((ty::TraitRef::identity(tcx, def_id), items));
1503                     generics
1504                 }
1505                 ItemKind::Existential(ExistTy { ref bounds, impl_trait_fn, ref generics }) => {
1506                     let substs = Substs::identity_for_item(tcx, def_id);
1507                     let anon_ty = tcx.mk_anon(def_id, substs);
1508
1509                     // Collect the bounds, i.e. the `A+B+'c` in `impl A+B+'c`.
1510                     let bounds = compute_bounds(&icx,
1511                                                 anon_ty,
1512                                                 bounds,
1513                                                 SizedByDefault::Yes,
1514                                                 tcx.def_span(def_id));
1515
1516                     if impl_trait_fn.is_some() {
1517                         // impl Trait
1518                         return ty::GenericPredicates {
1519                             parent: None,
1520                             predicates: bounds.predicates(tcx, anon_ty),
1521                         };
1522                     } else {
1523                         // named existential types
1524                         predicates.extend(bounds.predicates(tcx, anon_ty));
1525                         generics
1526                     }
1527                 }
1528
1529                 _ => &no_generics,
1530             }
1531         }
1532
1533         NodeForeignItem(item) => {
1534             match item.node {
1535                 ForeignItemKind::Static(..) => &no_generics,
1536                 ForeignItemKind::Fn(_, _, ref generics) => generics,
1537                 ForeignItemKind::Type => &no_generics,
1538             }
1539         }
1540
1541         _ => &no_generics,
1542     };
1543
1544     let generics = tcx.generics_of(def_id);
1545     let parent_count = generics.parent_count as u32;
1546     let has_own_self = generics.has_self && parent_count == 0;
1547
1548     // Below we'll consider the bounds on the type parameters (including `Self`)
1549     // and the explicit where-clauses, but to get the full set of predicates
1550     // on a trait we need to add in the supertrait bounds and bounds found on
1551     // associated types.
1552     if let Some((_trait_ref, _)) = is_trait {
1553         predicates = tcx.super_predicates_of(def_id).predicates;
1554     }
1555
1556     // In default impls, we can assume that the self type implements
1557     // the trait. So in:
1558     //
1559     //     default impl Foo for Bar { .. }
1560     //
1561     // we add a default where clause `Foo: Bar`. We do a similar thing for traits
1562     // (see below). Recall that a default impl is not itself an impl, but rather a
1563     // set of defaults that can be incorporated into another impl.
1564     if let Some(trait_ref) = is_default_impl_trait {
1565         predicates.push(trait_ref.to_poly_trait_ref().to_predicate());
1566     }
1567
1568     // Collect the region predicates that were declared inline as
1569     // well. In the case of parameters declared on a fn or method, we
1570     // have to be careful to only iterate over early-bound regions.
1571     let mut index = parent_count + has_own_self as u32;
1572     for param in early_bound_lifetimes_from_generics(tcx, ast_generics) {
1573         let region = tcx.mk_region(ty::ReEarlyBound(ty::EarlyBoundRegion {
1574             def_id: tcx.hir.local_def_id(param.id),
1575             index,
1576             name: param.name.ident().as_interned_str(),
1577         }));
1578         index += 1;
1579
1580         match param.kind {
1581             GenericParamKind::Lifetime { .. } => {
1582                 param.bounds.iter().for_each(|bound| match bound {
1583                     hir::GenericBound::Outlives(lt) => {
1584                         let bound = AstConv::ast_region_to_region(&icx, &lt, None);
1585                         let outlives = ty::Binder::bind(ty::OutlivesPredicate(region, bound));
1586                         predicates.push(outlives.to_predicate());
1587                     }
1588                     _ => bug!(),
1589                 });
1590             },
1591             _ => bug!(),
1592         }
1593     }
1594
1595     // Collect the predicates that were written inline by the user on each
1596     // type parameter (e.g., `<T:Foo>`).
1597     for param in &ast_generics.params {
1598         match param.kind {
1599             GenericParamKind::Type { .. } => {
1600                 let name = param.name.ident().as_interned_str();
1601                 let param_ty = ty::ParamTy::new(index, name).to_ty(tcx);
1602                 index += 1;
1603
1604                 let sized = SizedByDefault::Yes;
1605                 let bounds = compute_bounds(&icx, param_ty, &param.bounds, sized, param.span);
1606                 predicates.extend(bounds.predicates(tcx, param_ty));
1607             }
1608             _ => {}
1609         }
1610     }
1611
1612     // Add in the bounds that appear in the where-clause
1613     let where_clause = &ast_generics.where_clause;
1614     for predicate in &where_clause.predicates {
1615         match predicate {
1616             &hir::WherePredicate::BoundPredicate(ref bound_pred) => {
1617                 let ty = icx.to_ty(&bound_pred.bounded_ty);
1618
1619                 for bound in bound_pred.bounds.iter() {
1620                     match bound {
1621                         &hir::GenericBound::Trait(ref poly_trait_ref, _) => {
1622                             let mut projections = Vec::new();
1623
1624                             let trait_ref =
1625                                 AstConv::instantiate_poly_trait_ref(&icx,
1626                                                                     poly_trait_ref,
1627                                                                     ty,
1628                                                                     &mut projections);
1629
1630                             predicates.push(trait_ref.to_predicate());
1631
1632                             for projection in &projections {
1633                                 predicates.push(projection.to_predicate());
1634                             }
1635                         }
1636
1637                         &hir::GenericBound::Outlives(ref lifetime) => {
1638                             let region = AstConv::ast_region_to_region(&icx,
1639                                                                        lifetime,
1640                                                                        None);
1641                             let pred = ty::Binder::bind(ty::OutlivesPredicate(ty, region));
1642                             predicates.push(ty::Predicate::TypeOutlives(pred))
1643                         }
1644                     }
1645                 }
1646             }
1647
1648             &hir::WherePredicate::RegionPredicate(ref region_pred) => {
1649                 let r1 = AstConv::ast_region_to_region(&icx, &region_pred.lifetime, None);
1650                 for bound in &region_pred.bounds {
1651                     let r2 = match bound {
1652                         hir::GenericBound::Outlives(lt) => {
1653                             AstConv::ast_region_to_region(&icx, lt, None)
1654                         }
1655                         _ => bug!(),
1656                     };
1657                     let pred = ty::Binder::bind(ty::OutlivesPredicate(r1, r2));
1658                     predicates.push(ty::Predicate::RegionOutlives(pred))
1659                 }
1660             }
1661
1662             &hir::WherePredicate::EqPredicate(..) => {
1663                 // FIXME(#20041)
1664             }
1665         }
1666     }
1667
1668     // Add predicates from associated type bounds.
1669     if let Some((self_trait_ref, trait_items)) = is_trait {
1670         predicates.extend(trait_items.iter().flat_map(|trait_item_ref| {
1671             let trait_item = tcx.hir.trait_item(trait_item_ref.id);
1672             let bounds = match trait_item.node {
1673                 hir::TraitItemKind::Type(ref bounds, _) => bounds,
1674                 _ => {
1675                     return vec![].into_iter();
1676                 }
1677             };
1678
1679             let assoc_ty = tcx.mk_projection(
1680                 tcx.hir.local_def_id(trait_item.id),
1681                 self_trait_ref.substs,
1682             );
1683
1684             let bounds = compute_bounds(&ItemCtxt::new(tcx, def_id),
1685                                         assoc_ty,
1686                                         bounds,
1687                                         SizedByDefault::Yes,
1688                                         trait_item.span);
1689
1690             bounds.predicates(tcx, assoc_ty).into_iter()
1691         }))
1692     }
1693
1694     // Subtle: before we store the predicates into the tcx, we
1695     // sort them so that predicates like `T: Foo<Item=U>` come
1696     // before uses of `U`.  This avoids false ambiguity errors
1697     // in trait checking. See `setup_constraining_predicates`
1698     // for details.
1699     if let NodeItem(&Item { node: ItemKind::Impl(..), .. }) = node {
1700         let self_ty = tcx.type_of(def_id);
1701         let trait_ref = tcx.impl_trait_ref(def_id);
1702         ctp::setup_constraining_predicates(tcx,
1703                                            &mut predicates,
1704                                            trait_ref,
1705                                            &mut ctp::parameters_for_impl(self_ty, trait_ref));
1706     }
1707
1708     ty::GenericPredicates {
1709         parent: generics.parent,
1710         predicates,
1711     }
1712 }
1713
1714 pub enum SizedByDefault { Yes, No, }
1715
1716 /// Translate the AST's notion of ty param bounds (which are an enum consisting of a newtyped Ty or
1717 /// a region) to ty's notion of ty param bounds, which can either be user-defined traits, or the
1718 /// built-in trait (formerly known as kind): Send.
1719 pub fn compute_bounds<'gcx: 'tcx, 'tcx>(astconv: &dyn AstConv<'gcx, 'tcx>,
1720                                         param_ty: Ty<'tcx>,
1721                                         ast_bounds: &[hir::GenericBound],
1722                                         sized_by_default: SizedByDefault,
1723                                         span: Span)
1724                                         -> Bounds<'tcx>
1725 {
1726     let mut region_bounds = vec![];
1727     let mut trait_bounds = vec![];
1728     for ast_bound in ast_bounds {
1729         match *ast_bound {
1730             hir::GenericBound::Trait(ref b, hir::TraitBoundModifier::None) => trait_bounds.push(b),
1731             hir::GenericBound::Trait(_, hir::TraitBoundModifier::Maybe) => {}
1732             hir::GenericBound::Outlives(ref l) => region_bounds.push(l),
1733         }
1734     }
1735
1736     let mut projection_bounds = vec![];
1737
1738     let mut trait_bounds: Vec<_> = trait_bounds.iter().map(|&bound| {
1739         astconv.instantiate_poly_trait_ref(bound, param_ty, &mut projection_bounds)
1740     }).collect();
1741
1742     let region_bounds = region_bounds.into_iter().map(|r| {
1743         astconv.ast_region_to_region(r, None)
1744     }).collect();
1745
1746     trait_bounds.sort_by(|a,b| a.def_id().cmp(&b.def_id()));
1747
1748     let implicitly_sized = if let SizedByDefault::Yes = sized_by_default {
1749         !is_unsized(astconv, ast_bounds, span)
1750     } else {
1751         false
1752     };
1753
1754     Bounds {
1755         region_bounds,
1756         implicitly_sized,
1757         trait_bounds,
1758         projection_bounds,
1759     }
1760 }
1761
1762 /// Converts a specific GenericBound from the AST into a set of
1763 /// predicates that apply to the self-type. A vector is returned
1764 /// because this can be anywhere from 0 predicates (`T:?Sized` adds no
1765 /// predicates) to 1 (`T:Foo`) to many (`T:Bar<X=i32>` adds `T:Bar`
1766 /// and `<T as Bar>::X == i32`).
1767 fn predicates_from_bound<'tcx>(astconv: &dyn AstConv<'tcx, 'tcx>,
1768                                param_ty: Ty<'tcx>,
1769                                bound: &hir::GenericBound)
1770                                -> Vec<ty::Predicate<'tcx>>
1771 {
1772     match *bound {
1773         hir::GenericBound::Trait(ref tr, hir::TraitBoundModifier::None) => {
1774             let mut projections = Vec::new();
1775             let pred = astconv.instantiate_poly_trait_ref(tr,
1776                                                           param_ty,
1777                                                           &mut projections);
1778             projections.into_iter()
1779                        .map(|p| p.to_predicate())
1780                        .chain(Some(pred.to_predicate()))
1781                        .collect()
1782         }
1783         hir::GenericBound::Outlives(ref lifetime) => {
1784             let region = astconv.ast_region_to_region(lifetime, None);
1785             let pred = ty::Binder::bind(ty::OutlivesPredicate(param_ty, region));
1786             vec![ty::Predicate::TypeOutlives(pred)]
1787         }
1788         hir::GenericBound::Trait(_, hir::TraitBoundModifier::Maybe) => vec![],
1789     }
1790 }
1791
1792 fn compute_sig_of_foreign_fn_decl<'a, 'tcx>(
1793     tcx: TyCtxt<'a, 'tcx, 'tcx>,
1794     def_id: DefId,
1795     decl: &hir::FnDecl,
1796     abi: abi::Abi)
1797     -> ty::PolyFnSig<'tcx>
1798 {
1799     let fty = AstConv::ty_of_fn(&ItemCtxt::new(tcx, def_id), hir::Unsafety::Unsafe, abi, decl);
1800
1801     // feature gate SIMD types in FFI, since I (huonw) am not sure the
1802     // ABIs are handled at all correctly.
1803     if abi != abi::Abi::RustIntrinsic && abi != abi::Abi::PlatformIntrinsic
1804             && !tcx.features().simd_ffi {
1805         let check = |ast_ty: &hir::Ty, ty: Ty| {
1806             if ty.is_simd() {
1807                 tcx.sess.struct_span_err(ast_ty.span,
1808                               &format!("use of SIMD type `{}` in FFI is highly experimental and \
1809                                         may result in invalid code",
1810                                        tcx.hir.node_to_pretty_string(ast_ty.id)))
1811                     .help("add #![feature(simd_ffi)] to the crate attributes to enable")
1812                     .emit();
1813             }
1814         };
1815         for (input, ty) in decl.inputs.iter().zip(*fty.inputs().skip_binder()) {
1816             check(&input, ty)
1817         }
1818         if let hir::Return(ref ty) = decl.output {
1819             check(&ty, *fty.output().skip_binder())
1820         }
1821     }
1822
1823     fty
1824 }
1825
1826 fn is_foreign_item<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
1827                              def_id: DefId)
1828                              -> bool {
1829     match tcx.hir.get_if_local(def_id) {
1830         Some(hir_map::NodeForeignItem(..)) => true,
1831         Some(_) => false,
1832         _ => bug!("is_foreign_item applied to non-local def-id {:?}", def_id)
1833     }
1834 }
1835
1836 fn from_target_feature(
1837     tcx: TyCtxt,
1838     id: DefId,
1839     attr: &ast::Attribute,
1840     whitelist: &FxHashMap<String, Option<String>>,
1841     target_features: &mut Vec<Symbol>,
1842 ) {
1843     let list = match attr.meta_item_list() {
1844         Some(list) => list,
1845         None => {
1846             let msg = "#[target_feature] attribute must be of the form \
1847                        #[target_feature(..)]";
1848             tcx.sess.span_err(attr.span, &msg);
1849             return
1850         }
1851     };
1852     let rust_features = tcx.features();
1853     for item in list {
1854         // Only `enable = ...` is accepted in the meta item list
1855         if !item.check_name("enable") {
1856             let msg = "#[target_feature(..)] only accepts sub-keys of `enable` \
1857                        currently";
1858             tcx.sess.span_err(item.span, &msg);
1859             continue
1860         }
1861
1862         // Must be of the form `enable = "..."` ( a string)
1863         let value = match item.value_str() {
1864             Some(value) => value,
1865             None => {
1866                 let msg = "#[target_feature] attribute must be of the form \
1867                            #[target_feature(enable = \"..\")]";
1868                 tcx.sess.span_err(item.span, &msg);
1869                 continue
1870             }
1871         };
1872
1873         // We allow comma separation to enable multiple features
1874         for feature in value.as_str().split(',') {
1875
1876             // Only allow whitelisted features per platform
1877             let feature_gate = match whitelist.get(feature) {
1878                 Some(g) => g,
1879                 None => {
1880                     let msg = format!("the feature named `{}` is not valid for \
1881                                        this target", feature);
1882                     let mut err = tcx.sess.struct_span_err(item.span, &msg);
1883
1884                     if feature.starts_with("+") {
1885                         let valid = whitelist.contains_key(&feature[1..]);
1886                         if valid {
1887                             err.help("consider removing the leading `+` in the feature name");
1888                         }
1889                     }
1890                     err.emit();
1891                     continue
1892                 }
1893             };
1894
1895             // Only allow features whose feature gates have been enabled
1896             let allowed = match feature_gate.as_ref().map(|s| &**s) {
1897                 Some("arm_target_feature") => rust_features.arm_target_feature,
1898                 Some("aarch64_target_feature") => rust_features.aarch64_target_feature,
1899                 Some("hexagon_target_feature") => rust_features.hexagon_target_feature,
1900                 Some("powerpc_target_feature") => rust_features.powerpc_target_feature,
1901                 Some("mips_target_feature") => rust_features.mips_target_feature,
1902                 Some("avx512_target_feature") => rust_features.avx512_target_feature,
1903                 Some("mmx_target_feature") => rust_features.mmx_target_feature,
1904                 Some("sse4a_target_feature") => rust_features.sse4a_target_feature,
1905                 Some("tbm_target_feature") => rust_features.tbm_target_feature,
1906                 Some(name) => bug!("unknown target feature gate {}", name),
1907                 None => true,
1908             };
1909             if !allowed && id.is_local() {
1910                 feature_gate::emit_feature_err(
1911                     &tcx.sess.parse_sess,
1912                     feature_gate.as_ref().unwrap(),
1913                     item.span,
1914                     feature_gate::GateIssue::Language,
1915                     &format!("the target feature `{}` is currently unstable",
1916                              feature),
1917                 );
1918                 continue
1919             }
1920             target_features.push(Symbol::intern(feature));
1921         }
1922     }
1923 }
1924
1925 fn linkage_by_name<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId, name: &str) -> Linkage {
1926     use rustc::mir::mono::Linkage::*;
1927
1928     // Use the names from src/llvm/docs/LangRef.rst here. Most types are only
1929     // applicable to variable declarations and may not really make sense for
1930     // Rust code in the first place but whitelist them anyway and trust that
1931     // the user knows what s/he's doing. Who knows, unanticipated use cases
1932     // may pop up in the future.
1933     //
1934     // ghost, dllimport, dllexport and linkonce_odr_autohide are not supported
1935     // and don't have to be, LLVM treats them as no-ops.
1936     match name {
1937         "appending" => Appending,
1938         "available_externally" => AvailableExternally,
1939         "common" => Common,
1940         "extern_weak" => ExternalWeak,
1941         "external" => External,
1942         "internal" => Internal,
1943         "linkonce" => LinkOnceAny,
1944         "linkonce_odr" => LinkOnceODR,
1945         "private" => Private,
1946         "weak" => WeakAny,
1947         "weak_odr" => WeakODR,
1948         _ => {
1949             let span = tcx.hir.span_if_local(def_id);
1950             if let Some(span) = span {
1951                 tcx.sess.span_fatal(span, "invalid linkage specified")
1952             } else {
1953                 tcx.sess.fatal(&format!("invalid linkage specified: {}", name))
1954             }
1955         }
1956     }
1957 }
1958
1959 fn codegen_fn_attrs<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, id: DefId) -> CodegenFnAttrs {
1960     let attrs = tcx.get_attrs(id);
1961
1962     let mut codegen_fn_attrs = CodegenFnAttrs::new();
1963
1964     let whitelist = tcx.target_features_whitelist(LOCAL_CRATE);
1965
1966     let mut inline_span = None;
1967     for attr in attrs.iter() {
1968         if attr.check_name("cold") {
1969             codegen_fn_attrs.flags |= CodegenFnAttrFlags::COLD;
1970         } else if attr.check_name("allocator") {
1971             codegen_fn_attrs.flags |= CodegenFnAttrFlags::ALLOCATOR;
1972         } else if attr.check_name("unwind") {
1973             codegen_fn_attrs.flags |= CodegenFnAttrFlags::UNWIND;
1974         } else if attr.check_name("rustc_allocator_nounwind") {
1975             codegen_fn_attrs.flags |= CodegenFnAttrFlags::RUSTC_ALLOCATOR_NOUNWIND;
1976         } else if attr.check_name("naked") {
1977             codegen_fn_attrs.flags |= CodegenFnAttrFlags::NAKED;
1978         } else if attr.check_name("no_mangle") {
1979             codegen_fn_attrs.flags |= CodegenFnAttrFlags::NO_MANGLE;
1980         } else if attr.check_name("rustc_std_internal_symbol") {
1981             codegen_fn_attrs.flags |= CodegenFnAttrFlags::RUSTC_STD_INTERNAL_SYMBOL;
1982         } else if attr.check_name("no_debug") {
1983             codegen_fn_attrs.flags |= CodegenFnAttrFlags::NO_DEBUG;
1984         } else if attr.check_name("inline") {
1985             codegen_fn_attrs.inline = attrs.iter().fold(InlineAttr::None, |ia, attr| {
1986                 if attr.path != "inline" {
1987                     return ia;
1988                 }
1989                 let meta = match attr.meta() {
1990                     Some(meta) => meta.node,
1991                     None => return ia,
1992                 };
1993                 match meta {
1994                     MetaItemKind::Word => {
1995                         mark_used(attr);
1996                         InlineAttr::Hint
1997                     }
1998                     MetaItemKind::List(ref items) => {
1999                         mark_used(attr);
2000                         inline_span = Some(attr.span);
2001                         if items.len() != 1 {
2002                             span_err!(tcx.sess.diagnostic(), attr.span, E0534,
2003                                         "expected one argument");
2004                             InlineAttr::None
2005                         } else if list_contains_name(&items[..], "always") {
2006                             InlineAttr::Always
2007                         } else if list_contains_name(&items[..], "never") {
2008                             InlineAttr::Never
2009                         } else {
2010                             span_err!(tcx.sess.diagnostic(), items[0].span, E0535,
2011                                         "invalid argument");
2012
2013                             InlineAttr::None
2014                         }
2015                     }
2016                     _ => ia,
2017                 }
2018             });
2019         } else if attr.check_name("export_name") {
2020             if let Some(s) = attr.value_str() {
2021                 if s.as_str().contains("\0") {
2022                     // `#[export_name = ...]` will be converted to a null-terminated string,
2023                     // so it may not contain any null characters.
2024                     struct_span_err!(tcx.sess, attr.span, E0648,
2025                                      "`export_name` may not contain null characters")
2026                         .emit();
2027                 }
2028                 codegen_fn_attrs.export_name = Some(s);
2029             } else {
2030                 struct_span_err!(tcx.sess, attr.span, E0558,
2031                                  "`export_name` attribute has invalid format")
2032                     .span_label(attr.span, "did you mean #[export_name=\"*\"]?")
2033                     .emit();
2034             }
2035         } else if attr.check_name("target_feature") {
2036             if tcx.fn_sig(id).unsafety() == Unsafety::Normal {
2037                 let msg = "#[target_feature(..)] can only be applied to \
2038                            `unsafe` function";
2039                 tcx.sess.span_err(attr.span, msg);
2040             }
2041             from_target_feature(tcx, id, attr, &whitelist, &mut codegen_fn_attrs.target_features);
2042         } else if attr.check_name("linkage") {
2043             if let Some(val) = attr.value_str() {
2044                 codegen_fn_attrs.linkage = Some(linkage_by_name(tcx, id, &val.as_str()));
2045             }
2046         } else if attr.check_name("wasm_custom_section") {
2047             match attr.value_str() {
2048                 Some(name) => codegen_fn_attrs.wasm_custom_section = Some(name),
2049                 None => {
2050                     tcx.sess.span_err(attr.span, "must be of the form \
2051                         #[wasm_custom_section = \"foo\"]");
2052                 }
2053             }
2054         }
2055     }
2056
2057     // If a function uses #[target_feature] it can't be inlined into general
2058     // purpose functions as they wouldn't have the right target features
2059     // enabled. For that reason we also forbid #[inline(always)] as it can't be
2060     // respected.
2061     if codegen_fn_attrs.target_features.len() > 0 {
2062         if codegen_fn_attrs.inline == InlineAttr::Always {
2063             if let Some(span) = inline_span {
2064                 tcx.sess.span_err(span, "cannot use #[inline(always)] with \
2065                                          #[target_feature]");
2066             }
2067         }
2068     }
2069
2070     codegen_fn_attrs
2071 }