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 /*
  12
  13 # Collect phase
  14
  15 The collect phase of type check has the job of visiting all items,
  16 determining their type, and writing that type into the `tcx.types`
  17 table.  Despite its name, this table does not really operate as a
  18 *cache*, at least not for the types of items defined within the
  19 current crate: we assume that after the collect phase, the types of
  20 all local items will be present in the table.
  21
  22 Unlike most of the types that are present in Rust, the types computed
  23 for each item are in fact type schemes. This means that they are
  24 generic types that may have type parameters. TypeSchemes are
  25 represented by a pair of `Generics` and `Ty`.  Type
  26 parameters themselves are represented as `ty_param()` instances.
  27
  28 The phasing of type conversion is somewhat complicated. There is no
  29 clear set of phases we can enforce (e.g., converting traits first,
  30 then types, or something like that) because the user can introduce
  31 arbitrary interdependencies. So instead we generally convert things
  32 lazilly and on demand, and include logic that checks for cycles.
  33 Demand is driven by calls to `AstConv::get_item_type_scheme` or
  34 `AstConv::trait_def`.
  35
  36 Currently, we "convert" types and traits in two phases (note that
  37 conversion only affects the types of items / enum variants / methods;
  38 it does not e.g. compute the types of individual expressions):
  39
  40 0. Intrinsics
  41 1. Trait/Type definitions
  42
  43 Conversion itself is done by simply walking each of the items in turn
  44 and invoking an appropriate function (e.g., `trait_def_of_item` or
  45 `convert_item`). However, it is possible that while converting an
  46 item, we may need to compute the *type scheme* or *trait definition*
  47 for other items.
  48
  49 There are some shortcomings in this design:
  50 - Because the item generics include defaults, cycles through type
  51   parameter defaults are illegal even if those defaults are never
  52   employed. This is not necessarily a bug.
  53
  54 */
  55
  56 use astconv::{AstConv, Bounds};
  57 use lint;
  58 use constrained_type_params as ctp;
  59 use middle::lang_items::SizedTraitLangItem;
  60 use middle::const_val::ConstVal;
  61 use middle::resolve_lifetime as rl;
  62 use rustc::ty::subst::Substs;
  63 use rustc::ty::{ToPredicate, ReprOptions};
  64 use rustc::ty::{self, AdtKind, ToPolyTraitRef, Ty, TyCtxt};
  65 use rustc::ty::maps::Providers;
  66 use rustc::ty::util::IntTypeExt;
  67 use util::nodemap::FxHashMap;
  68
  69 use rustc_const_math::ConstInt;
  70
  71 use std::collections::BTreeMap;
  72
  73 use syntax::{abi, ast};
  74 use syntax::codemap::Spanned;
  75 use syntax::symbol::{Symbol, keywords};
  76 use syntax_pos::{Span, DUMMY_SP};
  77
  78 use rustc::hir::{self, map as hir_map};
  79 use rustc::hir::intravisit::{self, Visitor, NestedVisitorMap};
  80 use rustc::hir::def::{Def, CtorKind};
  81 use rustc::hir::def_id::DefId;
  82
  83 ///////////////////////////////////////////////////////////////////////////
  84 // Main entry point
  85
  86 pub fn collect_item_types<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) {
  87     let mut visitor = CollectItemTypesVisitor { tcx: tcx };
  88     tcx.hir.krate().visit_all_item_likes(&mut visitor.as_deep_visitor());
  89 }
  90
  91 pub fn provide(providers: &mut Providers) {
  92     *providers = Providers {
  93         type_of,
  94         generics_of,
  95         predicates_of,
  96         super_predicates_of,
  97         type_param_predicates,
  98         trait_def,
  99         adt_def,
 100         impl_trait_ref,
 101         impl_polarity,
 102         is_foreign_item,
 103         ..*providers
 104     };
 105 }
 106
 107 ///////////////////////////////////////////////////////////////////////////
 108
 109 /// Context specific to some particular item. This is what implements
 110 /// AstConv. It has information about the predicates that are defined
 111 /// on the trait. Unfortunately, this predicate information is
 112 /// available in various different forms at various points in the
 113 /// process. So we can't just store a pointer to e.g. the AST or the
 114 /// parsed ty form, we have to be more flexible. To this end, the
 115 /// `ItemCtxt` is parameterized by a `DefId` that it uses to satisfy
 116 /// `get_type_parameter_bounds` requests, drawing the information from
 117 /// the AST (`hir::Generics`), recursively.
 118 pub struct ItemCtxt<'a,'tcx:'a> {
 119     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 120     item_def_id: DefId,
 121 }
 122
 123 ///////////////////////////////////////////////////////////////////////////
 124
 125 struct CollectItemTypesVisitor<'a, 'tcx: 'a> {
 126     tcx: TyCtxt<'a, 'tcx, 'tcx>
 127 }
 128
 129 impl<'a, 'tcx> Visitor<'tcx> for CollectItemTypesVisitor<'a, 'tcx> {
 130     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
 131         NestedVisitorMap::OnlyBodies(&self.tcx.hir)
 132     }
 133
 134     fn visit_item(&mut self, item: &'tcx hir::Item) {
 135         convert_item(self.tcx, item.id);
 136         intravisit::walk_item(self, item);
 137     }
 138
 139     fn visit_generics(&mut self, generics: &'tcx hir::Generics) {
 140         for param in &generics.ty_params {
 141             if param.default.is_some() {
 142                 let def_id = self.tcx.hir.local_def_id(param.id);
 143                 self.tcx.type_of(def_id);
 144             }
 145         }
 146         intravisit::walk_generics(self, generics);
 147     }
 148
 149     fn visit_expr(&mut self, expr: &'tcx hir::Expr) {
 150         if let hir::ExprClosure(..) = expr.node {
 151             let def_id = self.tcx.hir.local_def_id(expr.id);
 152             self.tcx.generics_of(def_id);
 153             self.tcx.type_of(def_id);
 154         }
 155         intravisit::walk_expr(self, expr);
 156     }
 157
 158     fn visit_ty(&mut self, ty: &'tcx hir::Ty) {
 159         if let hir::TyImplTrait(..) = ty.node {
 160             let def_id = self.tcx.hir.local_def_id(ty.id);
 161             self.tcx.generics_of(def_id);
 162             self.tcx.predicates_of(def_id);
 163         }
 164         intravisit::walk_ty(self, ty);
 165     }
 166
 167     fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem) {
 168         convert_trait_item(self.tcx, trait_item.id);
 169         intravisit::walk_trait_item(self, trait_item);
 170     }
 171
 172     fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem) {
 173         convert_impl_item(self.tcx, impl_item.id);
 174         intravisit::walk_impl_item(self, impl_item);
 175     }
 176 }
 177
 178 ///////////////////////////////////////////////////////////////////////////
 179 // Utility types and common code for the above passes.
 180
 181 impl<'a, 'tcx> ItemCtxt<'a, 'tcx> {
 182     pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>, item_def_id: DefId)
 183            -> ItemCtxt<'a,'tcx> {
 184         ItemCtxt {
 185             tcx: tcx,
 186             item_def_id: item_def_id,
 187         }
 188     }
 189 }
 190
 191 impl<'a,'tcx> ItemCtxt<'a,'tcx> {
 192     pub fn to_ty(&self, ast_ty: &hir::Ty) -> Ty<'tcx> {
 193         AstConv::ast_ty_to_ty(self, ast_ty)
 194     }
 195 }
 196
 197 impl<'a, 'tcx> AstConv<'tcx, 'tcx> for ItemCtxt<'a, 'tcx> {
 198     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'tcx, 'tcx> { self.tcx }
 199
 200     fn get_type_parameter_bounds(&self,
 201                                  span: Span,
 202                                  def_id: DefId)
 203                                  -> ty::GenericPredicates<'tcx>
 204     {
 205         self.tcx.at(span).type_param_predicates((self.item_def_id, def_id))
 206     }
 207
 208     fn re_infer(&self, _span: Span, _def: Option<&ty::RegionParameterDef>)
 209                 -> Option<ty::Region<'tcx>> {
 210         None
 211     }
 212
 213     fn ty_infer(&self, span: Span) -> Ty<'tcx> {
 214         struct_span_err!(
 215             self.tcx().sess,
 216             span,
 217             E0121,
 218             "the type placeholder `_` is not allowed within types on item signatures"
 219         ).span_label(span, "not allowed in type signatures")
 220         .emit();
 221         self.tcx().types.err
 222     }
 223
 224     fn projected_ty_from_poly_trait_ref(&self,
 225                                         span: Span,
 226                                         poly_trait_ref: ty::PolyTraitRef<'tcx>,
 227                                         item_name: ast::Name)
 228                                         -> Ty<'tcx>
 229     {
 230         if let Some(trait_ref) = self.tcx().no_late_bound_regions(&poly_trait_ref) {
 231             self.tcx().mk_projection(trait_ref, item_name)
 232         } else {
 233             // no late-bound regions, we can just ignore the binder
 234             span_err!(self.tcx().sess, span, E0212,
 235                 "cannot extract an associated type from a higher-ranked trait bound \
 236                  in this context");
 237             self.tcx().types.err
 238         }
 239     }
 240
 241     fn normalize_ty(&self, _span: Span, ty: Ty<'tcx>) -> Ty<'tcx> {
 242         // types in item signatures are not normalized, to avoid undue
 243         // dependencies.
 244         ty
 245     }
 246
 247     fn set_tainted_by_errors(&self) {
 248         // no obvious place to track this, just let it go
 249     }
 250 }
 251
 252 fn type_param_predicates<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 253                                    (item_def_id, def_id): (DefId, DefId))
 254                                    -> ty::GenericPredicates<'tcx> {
 255     use rustc::hir::map::*;
 256     use rustc::hir::*;
 257
 258     // In the AST, bounds can derive from two places. Either
 259     // written inline like `<T:Foo>` or in a where clause like
 260     // `where T:Foo`.
 261
 262     let param_id = tcx.hir.as_local_node_id(def_id).unwrap();
 263     let param_owner = tcx.hir.ty_param_owner(param_id);
 264     let param_owner_def_id = tcx.hir.local_def_id(param_owner);
 265     let generics = tcx.generics_of(param_owner_def_id);
 266     let index = generics.type_param_to_index[&def_id.index];
 267     let ty = tcx.mk_param(index, tcx.hir.ty_param_name(param_id));
 268
 269     // Don't look for bounds where the type parameter isn't in scope.
 270     let parent = if item_def_id == param_owner_def_id {
 271         None
 272     } else {
 273         tcx.generics_of(item_def_id).parent
 274     };
 275
 276     let mut result = parent.map_or(ty::GenericPredicates {
 277         parent: None,
 278         predicates: vec![]
 279     }, |parent| {
 280         let icx = ItemCtxt::new(tcx, parent);
 281         icx.get_type_parameter_bounds(DUMMY_SP, def_id)
 282     });
 283
 284     let item_node_id = tcx.hir.as_local_node_id(item_def_id).unwrap();
 285     let ast_generics = match tcx.hir.get(item_node_id) {
 286         NodeTraitItem(item) => {
 287             match item.node {
 288                 TraitItemKind::Method(ref sig, _) => &sig.generics,
 289                 _ => return result
 290             }
 291         }
 292
 293         NodeImplItem(item) => {
 294             match item.node {
 295                 ImplItemKind::Method(ref sig, _) => &sig.generics,
 296                 _ => return result
 297             }
 298         }
 299
 300         NodeItem(item) => {
 301             match item.node {
 302                 ItemFn(.., ref generics, _) |
 303                 ItemImpl(_, _, _, ref generics, ..) |
 304                 ItemTy(_, ref generics) |
 305                 ItemEnum(_, ref generics) |
 306                 ItemStruct(_, ref generics) |
 307                 ItemUnion(_, ref generics) => generics,
 308                 ItemTrait(_, ref generics, ..) => {
 309                     // Implied `Self: Trait` and supertrait bounds.
 310                     if param_id == item_node_id {
 311                         result.predicates.push(ty::TraitRef {
 312                             def_id: item_def_id,
 313                             substs: Substs::identity_for_item(tcx, item_def_id)
 314                         }.to_predicate());
 315                     }
 316                     generics
 317                 }
 318                 _ => return result
 319             }
 320         }
 321
 322         NodeForeignItem(item) => {
 323             match item.node {
 324                 ForeignItemFn(_, _, ref generics) => generics,
 325                 _ => return result
 326             }
 327         }
 328
 329         _ => return result
 330     };
 331
 332     let icx = ItemCtxt::new(tcx, item_def_id);
 333     result.predicates.extend(
 334         icx.type_parameter_bounds_in_generics(ast_generics, param_id, ty));
 335     result
 336 }
 337
 338 impl<'a, 'tcx> ItemCtxt<'a, 'tcx> {
 339     /// Find bounds from hir::Generics. This requires scanning through the
 340     /// AST. We do this to avoid having to convert *all* the bounds, which
 341     /// would create artificial cycles. Instead we can only convert the
 342     /// bounds for a type parameter `X` if `X::Foo` is used.
 343     fn type_parameter_bounds_in_generics(&self,
 344                                          ast_generics: &hir::Generics,
 345                                          param_id: ast::NodeId,
 346                                          ty: Ty<'tcx>)
 347                                          -> Vec<ty::Predicate<'tcx>>
 348     {
 349         let from_ty_params =
 350             ast_generics.ty_params
 351                 .iter()
 352                 .filter(|p| p.id == param_id)
 353                 .flat_map(|p| p.bounds.iter())
 354                 .flat_map(|b| predicates_from_bound(self, ty, b));
 355
 356         let from_where_clauses =
 357             ast_generics.where_clause
 358                 .predicates
 359                 .iter()
 360                 .filter_map(|wp| match *wp {
 361                     hir::WherePredicate::BoundPredicate(ref bp) => Some(bp),
 362                     _ => None
 363                 })
 364                 .filter(|bp| is_param(self.tcx, &bp.bounded_ty, param_id))
 365                 .flat_map(|bp| bp.bounds.iter())
 366                 .flat_map(|b| predicates_from_bound(self, ty, b));
 367
 368         from_ty_params.chain(from_where_clauses).collect()
 369     }
 370 }
 371
 372 /// Tests whether this is the AST for a reference to the type
 373 /// parameter with id `param_id`. We use this so as to avoid running
 374 /// `ast_ty_to_ty`, because we want to avoid triggering an all-out
 375 /// conversion of the type to avoid inducing unnecessary cycles.
 376 fn is_param<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 377                       ast_ty: &hir::Ty,
 378                       param_id: ast::NodeId)
 379                       -> bool
 380 {
 381     if let hir::TyPath(hir::QPath::Resolved(None, ref path)) = ast_ty.node {
 382         match path.def {
 383             Def::SelfTy(Some(def_id), None) |
 384             Def::TyParam(def_id) => {
 385                 def_id == tcx.hir.local_def_id(param_id)
 386             }
 387             _ => false
 388         }
 389     } else {
 390         false
 391     }
 392 }
 393
 394 fn ensure_no_ty_param_bounds(tcx: TyCtxt,
 395                              span: Span,
 396                              generics: &hir::Generics,
 397                              thing: &'static str) {
 398     let mut warn = false;
 399
 400     for ty_param in generics.ty_params.iter() {
 401         for bound in ty_param.bounds.iter() {
 402             match *bound {
 403                 hir::TraitTyParamBound(..) => {
 404                     warn = true;
 405                 }
 406                 hir::RegionTyParamBound(..) => { }
 407             }
 408         }
 409     }
 410
 411     for predicate in generics.where_clause.predicates.iter() {
 412         match *predicate {
 413             hir::WherePredicate::BoundPredicate(..) => {
 414                 warn = true;
 415             }
 416             hir::WherePredicate::RegionPredicate(..) => { }
 417             hir::WherePredicate::EqPredicate(..) => { }
 418         }
 419     }
 420
 421     if warn {
 422         // According to accepted RFC #XXX, we should
 423         // eventually accept these, but it will not be
 424         // part of this PR. Still, convert to warning to
 425         // make bootstrapping easier.
 426         span_warn!(tcx.sess, span, E0122,
 427                    "trait bounds are not (yet) enforced \
 428                    in {} definitions",
 429                    thing);
 430     }
 431 }
 432
 433 fn convert_item<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, item_id: ast::NodeId) {
 434     let it = tcx.hir.expect_item(item_id);
 435     debug!("convert: item {} with id {}", it.name, it.id);
 436     let def_id = tcx.hir.local_def_id(item_id);
 437     match it.node {
 438         // These don't define types.
 439         hir::ItemExternCrate(_) |
 440         hir::ItemUse(..) |
 441         hir::ItemMod(_) |
 442         hir::ItemGlobalAsm(_) => {}
 443         hir::ItemForeignMod(ref foreign_mod) => {
 444             for item in &foreign_mod.items {
 445                 let def_id = tcx.hir.local_def_id(item.id);
 446                 tcx.generics_of(def_id);
 447                 tcx.type_of(def_id);
 448                 tcx.predicates_of(def_id);
 449             }
 450         }
 451         hir::ItemEnum(ref enum_definition, _) => {
 452             tcx.generics_of(def_id);
 453             tcx.type_of(def_id);
 454             tcx.predicates_of(def_id);
 455             convert_enum_variant_types(tcx, def_id, &enum_definition.variants);
 456         },
 457         hir::ItemDefaultImpl(..) => {
 458             tcx.impl_trait_ref(def_id);
 459         }
 460         hir::ItemImpl(..) => {
 461             tcx.generics_of(def_id);
 462             tcx.type_of(def_id);
 463             tcx.impl_trait_ref(def_id);
 464             tcx.predicates_of(def_id);
 465         },
 466         hir::ItemTrait(..) => {
 467             tcx.generics_of(def_id);
 468             tcx.trait_def(def_id);
 469             tcx.at(it.span).super_predicates_of(def_id);
 470             tcx.predicates_of(def_id);
 471         },
 472         hir::ItemStruct(ref struct_def, _) |
 473         hir::ItemUnion(ref struct_def, _) => {
 474             tcx.generics_of(def_id);
 475             tcx.type_of(def_id);
 476             tcx.predicates_of(def_id);
 477
 478             for f in struct_def.fields() {
 479                 let def_id = tcx.hir.local_def_id(f.id);
 480                 tcx.generics_of(def_id);
 481                 tcx.type_of(def_id);
 482                 tcx.predicates_of(def_id);
 483             }
 484
 485             if !struct_def.is_struct() {
 486                 convert_variant_ctor(tcx, struct_def.id());
 487             }
 488         },
 489         hir::ItemTy(_, ref generics) => {
 490             ensure_no_ty_param_bounds(tcx, it.span, generics, "type");
 491             tcx.generics_of(def_id);
 492             tcx.type_of(def_id);
 493             tcx.predicates_of(def_id);
 494         }
 495         hir::ItemStatic(..) | hir::ItemConst(..) | hir::ItemFn(..) => {
 496             tcx.generics_of(def_id);
 497             tcx.type_of(def_id);
 498             tcx.predicates_of(def_id);
 499         }
 500     }
 501 }
 502
 503 fn convert_trait_item<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, trait_item_id: ast::NodeId) {
 504     let trait_item = tcx.hir.expect_trait_item(trait_item_id);
 505     let def_id = tcx.hir.local_def_id(trait_item.id);
 506     tcx.generics_of(def_id);
 507
 508     match trait_item.node {
 509         hir::TraitItemKind::Const(..) |
 510         hir::TraitItemKind::Type(_, Some(_)) |
 511         hir::TraitItemKind::Method(..) => {
 512             tcx.type_of(def_id);
 513         }
 514
 515         hir::TraitItemKind::Type(_, None) => {}
 516     };
 517
 518     tcx.predicates_of(def_id);
 519 }
 520
 521 fn convert_impl_item<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, impl_item_id: ast::NodeId) {
 522     let def_id = tcx.hir.local_def_id(impl_item_id);
 523     tcx.generics_of(def_id);
 524     tcx.type_of(def_id);
 525     tcx.predicates_of(def_id);
 526 }
 527
 528 fn convert_variant_ctor<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 529                                   ctor_id: ast::NodeId) {
 530     let def_id = tcx.hir.local_def_id(ctor_id);
 531     tcx.generics_of(def_id);
 532     tcx.type_of(def_id);
 533     tcx.predicates_of(def_id);
 534 }
 535
 536 fn convert_enum_variant_types<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 537                                         def_id: DefId,
 538                                         variants: &[hir::Variant]) {
 539     let def = tcx.adt_def(def_id);
 540     let repr_type = def.repr.discr_type();
 541     let initial = repr_type.initial_discriminant(tcx);
 542     let mut prev_discr = None::<ConstInt>;
 543
 544     // fill the discriminant values and field types
 545     for variant in variants {
 546         let wrapped_discr = prev_discr.map_or(initial, |d| d.wrap_incr());
 547         prev_discr = Some(if let Some(e) = variant.node.disr_expr {
 548             let expr_did = tcx.hir.local_def_id(e.node_id);
 549             let substs = Substs::empty();
 550             let result = tcx.at(variant.span).const_eval((expr_did, substs));
 551
 552             // enum variant evaluation happens before the global constant check
 553             // so we need to report the real error
 554             if let Err(ref err) = result {
 555                 err.report(tcx, variant.span, "enum discriminant");
 556             }
 557
 558             match result {
 559                 Ok(ConstVal::Integral(x)) => Some(x),
 560                 _ => None
 561             }
 562         } else if let Some(discr) = repr_type.disr_incr(tcx, prev_discr) {
 563             Some(discr)
 564         } else {
 565             struct_span_err!(tcx.sess, variant.span, E0370,
 566                              "enum discriminant overflowed")
 567                 .span_label(variant.span, format!("overflowed on value after {}",
 568                                                    prev_discr.unwrap()))
 569                 .note(&format!("explicitly set `{} = {}` if that is desired outcome",
 570                                variant.node.name, wrapped_discr))
 571                 .emit();
 572             None
 573         }.unwrap_or(wrapped_discr));
 574
 575         for f in variant.node.data.fields() {
 576             let def_id = tcx.hir.local_def_id(f.id);
 577             tcx.generics_of(def_id);
 578             tcx.type_of(def_id);
 579             tcx.predicates_of(def_id);
 580         }
 581
 582         // Convert the ctor, if any. This also registers the variant as
 583         // an item.
 584         convert_variant_ctor(tcx, variant.node.data.id());
 585     }
 586 }
 587
 588 fn convert_struct_variant<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 589                                     did: DefId,
 590                                     name: ast::Name,
 591                                     discr: ty::VariantDiscr,
 592                                     def: &hir::VariantData)
 593                                     -> ty::VariantDef {
 594     let mut seen_fields: FxHashMap<ast::Name, Span> = FxHashMap();
 595     let node_id = tcx.hir.as_local_node_id(did).unwrap();
 596     let fields = def.fields().iter().map(|f| {
 597         let fid = tcx.hir.local_def_id(f.id);
 598         let dup_span = seen_fields.get(&f.name).cloned();
 599         if let Some(prev_span) = dup_span {
 600             struct_span_err!(tcx.sess, f.span, E0124,
 601                              "field `{}` is already declared",
 602                              f.name)
 603                 .span_label(f.span, "field already declared")
 604                 .span_label(prev_span, format!("`{}` first declared here", f.name))
 605                 .emit();
 606         } else {
 607             seen_fields.insert(f.name, f.span);
 608         }
 609
 610         ty::FieldDef {
 611             did: fid,
 612             name: f.name,
 613             vis: ty::Visibility::from_hir(&f.vis, node_id, tcx)
 614         }
 615     }).collect();
 616     ty::VariantDef {
 617         did: did,
 618         name: name,
 619         discr: discr,
 620         fields: fields,
 621         ctor_kind: CtorKind::from_hir(def),
 622     }
 623 }
 624
 625 fn adt_def<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 626                      def_id: DefId)
 627                      -> &'tcx ty::AdtDef {
 628     use rustc::hir::map::*;
 629     use rustc::hir::*;
 630
 631     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
 632     let item = match tcx.hir.get(node_id) {
 633         NodeItem(item) => item,
 634         _ => bug!()
 635     };
 636
 637     let repr = ReprOptions::new(tcx, def_id);
 638     let (kind, variants) = match item.node {
 639         ItemEnum(ref def, _) => {
 640             let mut distance_from_explicit = 0;
 641             (AdtKind::Enum, def.variants.iter().map(|v| {
 642                 let did = tcx.hir.local_def_id(v.node.data.id());
 643                 let discr = if let Some(e) = v.node.disr_expr {
 644                     distance_from_explicit = 0;
 645                     ty::VariantDiscr::Explicit(tcx.hir.local_def_id(e.node_id))
 646                 } else {
 647                     ty::VariantDiscr::Relative(distance_from_explicit)
 648                 };
 649                 distance_from_explicit += 1;
 650
 651                 convert_struct_variant(tcx, did, v.node.name, discr, &v.node.data)
 652             }).collect())
 653         }
 654         ItemStruct(ref def, _) => {
 655             // Use separate constructor id for unit/tuple structs and reuse did for braced structs.
 656             let ctor_id = if !def.is_struct() {
 657                 Some(tcx.hir.local_def_id(def.id()))
 658             } else {
 659                 None
 660             };
 661             (AdtKind::Struct, vec![
 662                 convert_struct_variant(tcx, ctor_id.unwrap_or(def_id), item.name,
 663                                        ty::VariantDiscr::Relative(0), def)
 664             ])
 665         }
 666         ItemUnion(ref def, _) => {
 667             (AdtKind::Union, vec![
 668                 convert_struct_variant(tcx, def_id, item.name,
 669                                        ty::VariantDiscr::Relative(0), def)
 670             ])
 671         }
 672         _ => bug!()
 673     };
 674     tcx.alloc_adt_def(def_id, kind, variants, repr)
 675 }
 676
 677 /// Ensures that the super-predicates of the trait with def-id
 678 /// trait_def_id are converted and stored. This also ensures that
 679 /// the transitive super-predicates are converted;
 680 fn super_predicates_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 681                                  trait_def_id: DefId)
 682                                  -> ty::GenericPredicates<'tcx> {
 683     debug!("super_predicates(trait_def_id={:?})", trait_def_id);
 684     let trait_node_id = tcx.hir.as_local_node_id(trait_def_id).unwrap();
 685
 686     let item = match tcx.hir.get(trait_node_id) {
 687         hir_map::NodeItem(item) => item,
 688         _ => bug!("trait_node_id {} is not an item", trait_node_id)
 689     };
 690
 691     let (generics, bounds) = match item.node {
 692         hir::ItemTrait(_, ref generics, ref supertraits, _) => (generics, supertraits),
 693         _ => span_bug!(item.span,
 694                        "super_predicates invoked on non-trait"),
 695     };
 696
 697     let icx = ItemCtxt::new(tcx, trait_def_id);
 698
 699     // Convert the bounds that follow the colon, e.g. `Bar+Zed` in `trait Foo : Bar+Zed`.
 700     let self_param_ty = tcx.mk_self_type();
 701     let superbounds1 = compute_bounds(&icx,
 702                                       self_param_ty,
 703                                       bounds,
 704                                       SizedByDefault::No,
 705                                       item.span);
 706
 707     let superbounds1 = superbounds1.predicates(tcx, self_param_ty);
 708
 709     // Convert any explicit superbounds in the where clause,
 710     // e.g. `trait Foo where Self : Bar`:
 711     let superbounds2 = icx.type_parameter_bounds_in_generics(generics, item.id, self_param_ty);
 712
 713     // Combine the two lists to form the complete set of superbounds:
 714     let superbounds: Vec<_> = superbounds1.into_iter().chain(superbounds2).collect();
 715
 716     // Now require that immediate supertraits are converted,
 717     // which will, in turn, reach indirect supertraits.
 718     for bound in superbounds.iter().filter_map(|p| p.to_opt_poly_trait_ref()) {
 719         tcx.at(item.span).super_predicates_of(bound.def_id());
 720     }
 721
 722     ty::GenericPredicates {
 723         parent: None,
 724         predicates: superbounds
 725     }
 726 }
 727
 728 fn trait_def<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 729                        def_id: DefId)
 730                        -> &'tcx ty::TraitDef {
 731     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
 732     let item = tcx.hir.expect_item(node_id);
 733
 734     let unsafety = match item.node {
 735         hir::ItemTrait(unsafety, ..) => unsafety,
 736         _ => span_bug!(item.span, "trait_def_of_item invoked on non-trait"),
 737     };
 738
 739     let paren_sugar = tcx.has_attr(def_id, "rustc_paren_sugar");
 740     if paren_sugar && !tcx.sess.features.borrow().unboxed_closures {
 741         let mut err = tcx.sess.struct_span_err(
 742             item.span,
 743             "the `#[rustc_paren_sugar]` attribute is a temporary means of controlling \
 744              which traits can use parenthetical notation");
 745         help!(&mut err,
 746             "add `#![feature(unboxed_closures)]` to \
 747              the crate attributes to use it");
 748         err.emit();
 749     }
 750
 751     let def_path_hash = tcx.def_path_hash(def_id);
 752     let has_default_impl = tcx.hir.trait_is_auto(def_id);
 753     let def = ty::TraitDef::new(def_id,
 754                                 unsafety,
 755                                 paren_sugar,
 756                                 has_default_impl,
 757                                 def_path_hash);
 758     tcx.alloc_trait_def(def)
 759 }
 760
 761 fn generics_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 762                          def_id: DefId)
 763                          -> &'tcx ty::Generics {
 764     use rustc::hir::map::*;
 765     use rustc::hir::*;
 766
 767     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
 768
 769     let node = tcx.hir.get(node_id);
 770     let parent_def_id = match node {
 771         NodeImplItem(_) |
 772         NodeTraitItem(_) |
 773         NodeVariant(_) |
 774         NodeStructCtor(_) |
 775         NodeField(_) => {
 776             let parent_id = tcx.hir.get_parent(node_id);
 777             Some(tcx.hir.local_def_id(parent_id))
 778         }
 779         NodeExpr(&hir::Expr { node: hir::ExprClosure(..), .. }) => {
 780             Some(tcx.closure_base_def_id(def_id))
 781         }
 782         NodeTy(&hir::Ty { node: hir::TyImplTrait(..), .. }) => {
 783             let mut parent_id = node_id;
 784             loop {
 785                 match tcx.hir.get(parent_id) {
 786                     NodeItem(_) | NodeImplItem(_) | NodeTraitItem(_) => break,
 787                     _ => {
 788                         parent_id = tcx.hir.get_parent_node(parent_id);
 789                     }
 790                 }
 791             }
 792             Some(tcx.hir.local_def_id(parent_id))
 793         }
 794         _ => None
 795     };
 796
 797     let mut opt_self = None;
 798     let mut allow_defaults = false;
 799
 800     let no_generics = hir::Generics::empty();
 801     let ast_generics = match node {
 802         NodeTraitItem(item) => {
 803             match item.node {
 804                 TraitItemKind::Method(ref sig, _) => &sig.generics,
 805                 _ => &no_generics
 806             }
 807         }
 808
 809         NodeImplItem(item) => {
 810             match item.node {
 811                 ImplItemKind::Method(ref sig, _) => &sig.generics,
 812                 _ => &no_generics
 813             }
 814         }
 815
 816         NodeItem(item) => {
 817             match item.node {
 818                 ItemFn(.., ref generics, _) |
 819                 ItemImpl(_, _, _, ref generics, ..) => generics,
 820
 821                 ItemTy(_, ref generics) |
 822                 ItemEnum(_, ref generics) |
 823                 ItemStruct(_, ref generics) |
 824                 ItemUnion(_, ref generics) => {
 825                     allow_defaults = true;
 826                     generics
 827                 }
 828
 829                 ItemTrait(_, ref generics, ..) => {
 830                     // Add in the self type parameter.
 831                     //
 832                     // Something of a hack: use the node id for the trait, also as
 833                     // the node id for the Self type parameter.
 834                     let param_id = item.id;
 835
 836                     opt_self = Some(ty::TypeParameterDef {
 837                         index: 0,
 838                         name: keywords::SelfType.name(),
 839                         def_id: tcx.hir.local_def_id(param_id),
 840                         has_default: false,
 841                         object_lifetime_default: rl::Set1::Empty,
 842                         pure_wrt_drop: false,
 843                     });
 844
 845                     allow_defaults = true;
 846                     generics
 847                 }
 848
 849                 _ => &no_generics
 850             }
 851         }
 852
 853         NodeForeignItem(item) => {
 854             match item.node {
 855                 ForeignItemStatic(..) => &no_generics,
 856                 ForeignItemFn(_, _, ref generics) => generics
 857             }
 858         }
 859
 860         _ => &no_generics
 861     };
 862
 863     let has_self = opt_self.is_some();
 864     let mut parent_has_self = false;
 865     let mut own_start = has_self as u32;
 866     let (parent_regions, parent_types) = parent_def_id.map_or((0, 0), |def_id| {
 867         let generics = tcx.generics_of(def_id);
 868         assert_eq!(has_self, false);
 869         parent_has_self = generics.has_self;
 870         own_start = generics.count() as u32;
 871         (generics.parent_regions + generics.regions.len() as u32,
 872             generics.parent_types + generics.types.len() as u32)
 873     });
 874
 875     let early_lifetimes = early_bound_lifetimes_from_generics(tcx, ast_generics);
 876     let regions = early_lifetimes.enumerate().map(|(i, l)| {
 877         let issue_32330 = tcx.named_region_map.issue_32330.get(&l.lifetime.id).cloned();
 878         ty::RegionParameterDef {
 879             name: l.lifetime.name,
 880             index: own_start + i as u32,
 881             def_id: tcx.hir.local_def_id(l.lifetime.id),
 882             pure_wrt_drop: l.pure_wrt_drop,
 883             issue_32330: issue_32330,
 884         }
 885     }).collect::<Vec<_>>();
 886
 887     let object_lifetime_defaults =
 888         tcx.named_region_map.object_lifetime_defaults.get(&node_id);
 889
 890     // Now create the real type parameters.
 891     let type_start = own_start + regions.len() as u32;
 892     let types = ast_generics.ty_params.iter().enumerate().map(|(i, p)| {
 893         if p.name == keywords::SelfType.name() {
 894             span_bug!(p.span, "`Self` should not be the name of a regular parameter");
 895         }
 896
 897         if !allow_defaults && p.default.is_some() {
 898             if !tcx.sess.features.borrow().default_type_parameter_fallback {
 899                 tcx.sess.add_lint(
 900                     lint::builtin::INVALID_TYPE_PARAM_DEFAULT,
 901                     p.id,
 902                     p.span,
 903                     format!("defaults for type parameters are only allowed in `struct`, \
 904                              `enum`, `type`, or `trait` definitions."));
 905             }
 906         }
 907
 908         ty::TypeParameterDef {
 909             index: type_start + i as u32,
 910             name: p.name,
 911             def_id: tcx.hir.local_def_id(p.id),
 912             has_default: p.default.is_some(),
 913             object_lifetime_default:
 914                 object_lifetime_defaults.map_or(rl::Set1::Empty, |o| o[i]),
 915             pure_wrt_drop: p.pure_wrt_drop,
 916         }
 917     });
 918     let mut types: Vec<_> = opt_self.into_iter().chain(types).collect();
 919
 920     // provide junk type parameter defs - the only place that
 921     // cares about anything but the length is instantiation,
 922     // and we don't do that for closures.
 923     if let NodeExpr(&hir::Expr { node: hir::ExprClosure(..), .. }) = node {
 924         tcx.with_freevars(node_id, |fv| {
 925             types.extend(fv.iter().enumerate().map(|(i, _)| ty::TypeParameterDef {
 926                 index: type_start + i as u32,
 927                 name: Symbol::intern("<upvar>"),
 928                 def_id: def_id,
 929                 has_default: false,
 930                 object_lifetime_default: rl::Set1::Empty,
 931                 pure_wrt_drop: false,
 932             }));
 933         });
 934     }
 935
 936     let mut type_param_to_index = BTreeMap::new();
 937     for param in &types {
 938         type_param_to_index.insert(param.def_id.index, param.index);
 939     }
 940
 941     tcx.alloc_generics(ty::Generics {
 942         parent: parent_def_id,
 943         parent_regions: parent_regions,
 944         parent_types: parent_types,
 945         regions: regions,
 946         types: types,
 947         type_param_to_index: type_param_to_index,
 948         has_self: has_self || parent_has_self
 949     })
 950 }
 951
 952 fn type_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 953                      def_id: DefId)
 954                      -> Ty<'tcx> {
 955     use rustc::hir::map::*;
 956     use rustc::hir::*;
 957
 958     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
 959
 960     let icx = ItemCtxt::new(tcx, def_id);
 961
 962     match tcx.hir.get(node_id) {
 963         NodeTraitItem(item) => {
 964             match item.node {
 965                 TraitItemKind::Method(ref sig, _) => {
 966                     let fty = AstConv::ty_of_fn(&icx, sig.unsafety, sig.abi, &sig.decl);
 967                     let substs = Substs::identity_for_item(tcx, def_id);
 968                     tcx.mk_fn_def(def_id, substs, fty)
 969                 }
 970                 TraitItemKind::Const(ref ty, _) |
 971                 TraitItemKind::Type(_, Some(ref ty)) => icx.to_ty(ty),
 972                 TraitItemKind::Type(_, None) => {
 973                     span_bug!(item.span, "associated type missing default");
 974                 }
 975             }
 976         }
 977
 978         NodeImplItem(item) => {
 979             match item.node {
 980                 ImplItemKind::Method(ref sig, _) => {
 981                     let fty = AstConv::ty_of_fn(&icx, sig.unsafety, sig.abi, &sig.decl);
 982                     let substs = Substs::identity_for_item(tcx, def_id);
 983                     tcx.mk_fn_def(def_id, substs, fty)
 984                 }
 985                 ImplItemKind::Const(ref ty, _) => icx.to_ty(ty),
 986                 ImplItemKind::Type(ref ty) => {
 987                     if tcx.impl_trait_ref(tcx.hir.get_parent_did(node_id)).is_none() {
 988                         span_err!(tcx.sess, item.span, E0202,
 989                                   "associated types are not allowed in inherent impls");
 990                     }
 991
 992                     icx.to_ty(ty)
 993                 }
 994             }
 995         }
 996
 997         NodeItem(item) => {
 998             match item.node {
 999                 ItemStatic(ref t, ..) | ItemConst(ref t, _) |
1000                 ItemTy(ref t, _) | ItemImpl(.., ref t, _) => {
1001                     icx.to_ty(t)
1002                 }
1003                 ItemFn(ref decl, unsafety, _, abi, _, _) => {
1004                     let tofd = AstConv::ty_of_fn(&icx, unsafety, abi, &decl);
1005                     let substs = Substs::identity_for_item(tcx, def_id);
1006                     tcx.mk_fn_def(def_id, substs, tofd)
1007                 }
1008                 ItemEnum(..) |
1009                 ItemStruct(..) |
1010                 ItemUnion(..) => {
1011                     let def = tcx.adt_def(def_id);
1012                     let substs = Substs::identity_for_item(tcx, def_id);
1013                     tcx.mk_adt(def, substs)
1014                 }
1015                 ItemDefaultImpl(..) |
1016                 ItemTrait(..) |
1017                 ItemMod(..) |
1018                 ItemForeignMod(..) |
1019                 ItemGlobalAsm(..) |
1020                 ItemExternCrate(..) |
1021                 ItemUse(..) => {
1022                     span_bug!(
1023                         item.span,
1024                         "compute_type_of_item: unexpected item type: {:?}",
1025                         item.node);
1026                 }
1027             }
1028         }
1029
1030         NodeForeignItem(foreign_item) => {
1031             let abi = tcx.hir.get_foreign_abi(node_id);
1032
1033             match foreign_item.node {
1034                 ForeignItemFn(ref fn_decl, _, _) => {
1035                     compute_type_of_foreign_fn_decl(tcx, def_id, fn_decl, abi)
1036                 }
1037                 ForeignItemStatic(ref t, _) => icx.to_ty(t)
1038             }
1039         }
1040
1041         NodeStructCtor(&ref def) |
1042         NodeVariant(&Spanned { node: hir::Variant_ { data: ref def, .. }, .. }) => {
1043             let ty = tcx.type_of(tcx.hir.get_parent_did(node_id));
1044             match *def {
1045                 VariantData::Unit(..) | VariantData::Struct(..) => ty,
1046                 VariantData::Tuple(ref fields, _) => {
1047                     let inputs = fields.iter().map(|f| {
1048                         tcx.type_of(tcx.hir.local_def_id(f.id))
1049                     });
1050                     let substs = Substs::identity_for_item(tcx, def_id);
1051                     tcx.mk_fn_def(def_id, substs, ty::Binder(tcx.mk_fn_sig(
1052                         inputs,
1053                         ty,
1054                         false,
1055                         hir::Unsafety::Normal,
1056                         abi::Abi::Rust
1057                     )))
1058                 }
1059             }
1060         }
1061
1062         NodeField(field) => icx.to_ty(&field.ty),
1063
1064         NodeExpr(&hir::Expr { node: hir::ExprClosure(..), .. }) => {
1065             tcx.mk_closure(def_id, Substs::for_item(
1066                 tcx, def_id,
1067                 |def, _| {
1068                     let region = def.to_early_bound_region_data();
1069                     tcx.mk_region(ty::ReEarlyBound(region))
1070                 },
1071                 |def, _| tcx.mk_param_from_def(def)
1072             ))
1073         }
1074
1075         NodeExpr(_) => match tcx.hir.get(tcx.hir.get_parent_node(node_id)) {
1076             NodeTy(&hir::Ty { node: TyArray(_, body), .. }) |
1077             NodeTy(&hir::Ty { node: TyTypeof(body), .. }) |
1078             NodeExpr(&hir::Expr { node: ExprRepeat(_, body), .. })
1079                 if body.node_id == node_id => tcx.types.usize,
1080
1081             NodeVariant(&Spanned { node: Variant_ { disr_expr: Some(e), .. }, .. })
1082                 if e.node_id == node_id => {
1083                     tcx.adt_def(tcx.hir.get_parent_did(node_id))
1084                         .repr.discr_type().to_ty(tcx)
1085                 }
1086
1087             x => {
1088                 bug!("unexpected expr parent in type_of_def_id(): {:?}", x);
1089             }
1090         },
1091
1092         NodeTyParam(&hir::TyParam { default: Some(ref ty), .. }) => {
1093             icx.to_ty(ty)
1094         }
1095
1096         NodeTy(&hir::Ty { node: TyImplTrait(..), .. }) => {
1097             let owner = tcx.hir.get_parent_did(node_id);
1098             tcx.typeck_tables_of(owner).node_id_to_type(node_id)
1099         }
1100
1101         x => {
1102             bug!("unexpected sort of node in type_of_def_id(): {:?}", x);
1103         }
1104     }
1105 }
1106
1107 fn impl_trait_ref<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
1108                             def_id: DefId)
1109                             -> Option<ty::TraitRef<'tcx>> {
1110     let icx = ItemCtxt::new(tcx, def_id);
1111
1112     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
1113     match tcx.hir.expect_item(node_id).node {
1114         hir::ItemDefaultImpl(_, ref ast_trait_ref) => {
1115             Some(AstConv::instantiate_mono_trait_ref(&icx,
1116                                                      ast_trait_ref,
1117                                                      tcx.mk_self_type()))
1118         }
1119         hir::ItemImpl(.., ref opt_trait_ref, _, _) => {
1120             opt_trait_ref.as_ref().map(|ast_trait_ref| {
1121                 let selfty = tcx.type_of(def_id);
1122                 AstConv::instantiate_mono_trait_ref(&icx, ast_trait_ref, selfty)
1123             })
1124         }
1125         _ => bug!()
1126     }
1127 }
1128
1129 fn impl_polarity<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
1130                            def_id: DefId)
1131                            -> hir::ImplPolarity {
1132     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
1133     match tcx.hir.expect_item(node_id).node {
1134         hir::ItemImpl(_, polarity, ..) => polarity,
1135         ref item => bug!("impl_polarity: {:?} not an impl", item)
1136     }
1137 }
1138
1139 // Is it marked with ?Sized
1140 fn is_unsized<'gcx: 'tcx, 'tcx>(astconv: &AstConv<'gcx, 'tcx>,
1141                                 ast_bounds: &[hir::TyParamBound],
1142                                 span: Span) -> bool
1143 {
1144     let tcx = astconv.tcx();
1145
1146     // Try to find an unbound in bounds.
1147     let mut unbound = None;
1148     for ab in ast_bounds {
1149         if let &hir::TraitTyParamBound(ref ptr, hir::TraitBoundModifier::Maybe) = ab  {
1150             if unbound.is_none() {
1151                 unbound = Some(ptr.trait_ref.clone());
1152             } else {
1153                 span_err!(tcx.sess, span, E0203,
1154                           "type parameter has more than one relaxed default \
1155                                                 bound, only one is supported");
1156             }
1157         }
1158     }
1159
1160     let kind_id = tcx.lang_items.require(SizedTraitLangItem);
1161     match unbound {
1162         Some(ref tpb) => {
1163             // FIXME(#8559) currently requires the unbound to be built-in.
1164             if let Ok(kind_id) = kind_id {
1165                 if tpb.path.def != Def::Trait(kind_id) {
1166                     tcx.sess.span_warn(span,
1167                                        "default bound relaxed for a type parameter, but \
1168                                        this does nothing because the given bound is not \
1169                                        a default. Only `?Sized` is supported");
1170                 }
1171             }
1172         }
1173         _ if kind_id.is_ok() => {
1174             return false;
1175         }
1176         // No lang item for Sized, so we can't add it as a bound.
1177         None => {}
1178     }
1179
1180     true
1181 }
1182
1183 /// Returns the early-bound lifetimes declared in this generics
1184 /// listing.  For anything other than fns/methods, this is just all
1185 /// the lifetimes that are declared. For fns or methods, we have to
1186 /// screen out those that do not appear in any where-clauses etc using
1187 /// `resolve_lifetime::early_bound_lifetimes`.
1188 fn early_bound_lifetimes_from_generics<'a, 'tcx>(
1189     tcx: TyCtxt<'a, 'tcx, 'tcx>,
1190     ast_generics: &'a hir::Generics)
1191     -> impl Iterator<Item=&'a hir::LifetimeDef>
1192 {
1193     ast_generics
1194         .lifetimes
1195         .iter()
1196         .filter(move |l| !tcx.named_region_map.late_bound.contains(&l.lifetime.id))
1197 }
1198
1199 fn predicates_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
1200                            def_id: DefId)
1201                            -> ty::GenericPredicates<'tcx> {
1202     use rustc::hir::map::*;
1203     use rustc::hir::*;
1204
1205     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
1206     let node = tcx.hir.get(node_id);
1207
1208     let mut is_trait = None;
1209
1210     let icx = ItemCtxt::new(tcx, def_id);
1211     let no_generics = hir::Generics::empty();
1212     let ast_generics = match node {
1213         NodeTraitItem(item) => {
1214             match item.node {
1215                 TraitItemKind::Method(ref sig, _) => &sig.generics,
1216                 _ => &no_generics
1217             }
1218         }
1219
1220         NodeImplItem(item) => {
1221             match item.node {
1222                 ImplItemKind::Method(ref sig, _) => &sig.generics,
1223                 _ => &no_generics
1224             }
1225         }
1226
1227         NodeItem(item) => {
1228             match item.node {
1229                 ItemFn(.., ref generics, _) |
1230                 ItemImpl(_, _, _, ref generics, ..) |
1231                 ItemTy(_, ref generics) |
1232                 ItemEnum(_, ref generics) |
1233                 ItemStruct(_, ref generics) |
1234                 ItemUnion(_, ref generics) => {
1235                     generics
1236                 }
1237
1238                 ItemTrait(_, ref generics, .., ref items) => {
1239                     is_trait = Some((ty::TraitRef {
1240                         def_id: def_id,
1241                         substs: Substs::identity_for_item(tcx, def_id)
1242                     }, items));
1243                     generics
1244                 }
1245
1246                 _ => &no_generics
1247             }
1248         }
1249
1250         NodeForeignItem(item) => {
1251             match item.node {
1252                 ForeignItemStatic(..) => &no_generics,
1253                 ForeignItemFn(_, _, ref generics) => generics
1254             }
1255         }
1256
1257         NodeTy(&Ty { node: TyImplTrait(ref bounds), span, .. }) => {
1258             let substs = Substs::identity_for_item(tcx, def_id);
1259             let anon_ty = tcx.mk_anon(def_id, substs);
1260
1261             // Collect the bounds, i.e. the `A+B+'c` in `impl A+B+'c`.
1262             let bounds = compute_bounds(&icx, anon_ty, bounds,
1263                                         SizedByDefault::Yes,
1264                                         span);
1265             return ty::GenericPredicates {
1266                 parent: None,
1267                 predicates: bounds.predicates(tcx, anon_ty)
1268             };
1269         }
1270
1271         _ => &no_generics
1272     };
1273
1274     let generics = tcx.generics_of(def_id);
1275     let parent_count = generics.parent_count() as u32;
1276     let has_own_self = generics.has_self && parent_count == 0;
1277
1278     let mut predicates = vec![];
1279
1280     // Below we'll consider the bounds on the type parameters (including `Self`)
1281     // and the explicit where-clauses, but to get the full set of predicates
1282     // on a trait we need to add in the supertrait bounds and bounds found on
1283     // associated types.
1284     if let Some((trait_ref, _)) = is_trait {
1285         predicates = tcx.super_predicates_of(def_id).predicates;
1286
1287         // Add in a predicate that `Self:Trait` (where `Trait` is the
1288         // current trait).  This is needed for builtin bounds.
1289         predicates.push(trait_ref.to_poly_trait_ref().to_predicate());
1290     }
1291
1292     // Collect the region predicates that were declared inline as
1293     // well. In the case of parameters declared on a fn or method, we
1294     // have to be careful to only iterate over early-bound regions.
1295     let mut index = parent_count + has_own_self as u32;
1296     for param in early_bound_lifetimes_from_generics(tcx, ast_generics) {
1297         let region = tcx.mk_region(ty::ReEarlyBound(ty::EarlyBoundRegion {
1298             def_id: tcx.hir.local_def_id(param.lifetime.id),
1299             index: index,
1300             name: param.lifetime.name
1301         }));
1302         index += 1;
1303
1304         for bound in &param.bounds {
1305             let bound_region = AstConv::ast_region_to_region(&icx, bound, None);
1306             let outlives = ty::Binder(ty::OutlivesPredicate(region, bound_region));
1307             predicates.push(outlives.to_predicate());
1308         }
1309     }
1310
1311     // Collect the predicates that were written inline by the user on each
1312     // type parameter (e.g., `<T:Foo>`).
1313     for param in &ast_generics.ty_params {
1314         let param_ty = ty::ParamTy::new(index, param.name).to_ty(tcx);
1315         index += 1;
1316
1317         let bounds = compute_bounds(&icx,
1318                                     param_ty,
1319                                     &param.bounds,
1320                                     SizedByDefault::Yes,
1321                                     param.span);
1322         predicates.extend(bounds.predicates(tcx, param_ty));
1323     }
1324
1325     // Add in the bounds that appear in the where-clause
1326     let where_clause = &ast_generics.where_clause;
1327     for predicate in &where_clause.predicates {
1328         match predicate {
1329             &hir::WherePredicate::BoundPredicate(ref bound_pred) => {
1330                 let ty = icx.to_ty(&bound_pred.bounded_ty);
1331
1332                 for bound in bound_pred.bounds.iter() {
1333                     match bound {
1334                         &hir::TyParamBound::TraitTyParamBound(ref poly_trait_ref, _) => {
1335                             let mut projections = Vec::new();
1336
1337                             let trait_ref =
1338                                 AstConv::instantiate_poly_trait_ref(&icx,
1339                                                                     poly_trait_ref,
1340                                                                     ty,
1341                                                                     &mut projections);
1342
1343                             predicates.push(trait_ref.to_predicate());
1344
1345                             for projection in &projections {
1346                                 predicates.push(projection.to_predicate());
1347                             }
1348                         }
1349
1350                         &hir::TyParamBound::RegionTyParamBound(ref lifetime) => {
1351                             let region = AstConv::ast_region_to_region(&icx,
1352                                                                        lifetime,
1353                                                                        None);
1354                             let pred = ty::Binder(ty::OutlivesPredicate(ty, region));
1355                             predicates.push(ty::Predicate::TypeOutlives(pred))
1356                         }
1357                     }
1358                 }
1359             }
1360
1361             &hir::WherePredicate::RegionPredicate(ref region_pred) => {
1362                 let r1 = AstConv::ast_region_to_region(&icx, &region_pred.lifetime, None);
1363                 for bound in &region_pred.bounds {
1364                     let r2 = AstConv::ast_region_to_region(&icx, bound, None);
1365                     let pred = ty::Binder(ty::OutlivesPredicate(r1, r2));
1366                     predicates.push(ty::Predicate::RegionOutlives(pred))
1367                 }
1368             }
1369
1370             &hir::WherePredicate::EqPredicate(..) => {
1371                 // FIXME(#20041)
1372             }
1373         }
1374     }
1375
1376     // Add predicates from associated type bounds.
1377     if let Some((self_trait_ref, trait_items)) = is_trait {
1378         predicates.extend(trait_items.iter().flat_map(|trait_item_ref| {
1379             let trait_item = tcx.hir.trait_item(trait_item_ref.id);
1380             let bounds = match trait_item.node {
1381                 hir::TraitItemKind::Type(ref bounds, _) => bounds,
1382                 _ => {
1383                     return vec![].into_iter();
1384                 }
1385             };
1386
1387             let assoc_ty = tcx.mk_projection(self_trait_ref, trait_item.name);
1388
1389             let bounds = compute_bounds(&ItemCtxt::new(tcx, def_id),
1390                                         assoc_ty,
1391                                         bounds,
1392                                         SizedByDefault::Yes,
1393                                         trait_item.span);
1394
1395             bounds.predicates(tcx, assoc_ty).into_iter()
1396         }))
1397     }
1398
1399     // Subtle: before we store the predicates into the tcx, we
1400     // sort them so that predicates like `T: Foo<Item=U>` come
1401     // before uses of `U`.  This avoids false ambiguity errors
1402     // in trait checking. See `setup_constraining_predicates`
1403     // for details.
1404     if let NodeItem(&Item { node: ItemImpl(..), .. }) = node {
1405         let self_ty = tcx.type_of(def_id);
1406         let trait_ref = tcx.impl_trait_ref(def_id);
1407         ctp::setup_constraining_predicates(&mut predicates,
1408                                            trait_ref,
1409                                            &mut ctp::parameters_for_impl(self_ty, trait_ref));
1410     }
1411
1412     ty::GenericPredicates {
1413         parent: generics.parent,
1414         predicates: predicates
1415     }
1416 }
1417
1418 pub enum SizedByDefault { Yes, No, }
1419
1420 /// Translate the AST's notion of ty param bounds (which are an enum consisting of a newtyped Ty or
1421 /// a region) to ty's notion of ty param bounds, which can either be user-defined traits, or the
1422 /// built-in trait (formerly known as kind): Send.
1423 pub fn compute_bounds<'gcx: 'tcx, 'tcx>(astconv: &AstConv<'gcx, 'tcx>,
1424                                         param_ty: ty::Ty<'tcx>,
1425                                         ast_bounds: &[hir::TyParamBound],
1426                                         sized_by_default: SizedByDefault,
1427                                         span: Span)
1428                                         -> Bounds<'tcx>
1429 {
1430     let mut region_bounds = vec![];
1431     let mut trait_bounds = vec![];
1432     for ast_bound in ast_bounds {
1433         match *ast_bound {
1434             hir::TraitTyParamBound(ref b, hir::TraitBoundModifier::None) => {
1435                 trait_bounds.push(b);
1436             }
1437             hir::TraitTyParamBound(_, hir::TraitBoundModifier::Maybe) => {}
1438             hir::RegionTyParamBound(ref l) => {
1439                 region_bounds.push(l);
1440             }
1441         }
1442     }
1443
1444     let mut projection_bounds = vec![];
1445
1446     let mut trait_bounds: Vec<_> = trait_bounds.iter().map(|&bound| {
1447         astconv.instantiate_poly_trait_ref(bound,
1448                                            param_ty,
1449                                            &mut projection_bounds)
1450     }).collect();
1451
1452     let region_bounds = region_bounds.into_iter().map(|r| {
1453         astconv.ast_region_to_region(r, None)
1454     }).collect();
1455
1456     trait_bounds.sort_by(|a,b| a.def_id().cmp(&b.def_id()));
1457
1458     let implicitly_sized = if let SizedByDefault::Yes = sized_by_default {
1459         !is_unsized(astconv, ast_bounds, span)
1460     } else {
1461         false
1462     };
1463
1464     Bounds {
1465         region_bounds: region_bounds,
1466         implicitly_sized: implicitly_sized,
1467         trait_bounds: trait_bounds,
1468         projection_bounds: projection_bounds,
1469     }
1470 }
1471
1472 /// Converts a specific TyParamBound from the AST into a set of
1473 /// predicates that apply to the self-type. A vector is returned
1474 /// because this can be anywhere from 0 predicates (`T:?Sized` adds no
1475 /// predicates) to 1 (`T:Foo`) to many (`T:Bar<X=i32>` adds `T:Bar`
1476 /// and `<T as Bar>::X == i32`).
1477 fn predicates_from_bound<'tcx>(astconv: &AstConv<'tcx, 'tcx>,
1478                                param_ty: Ty<'tcx>,
1479                                bound: &hir::TyParamBound)
1480                                -> Vec<ty::Predicate<'tcx>>
1481 {
1482     match *bound {
1483         hir::TraitTyParamBound(ref tr, hir::TraitBoundModifier::None) => {
1484             let mut projections = Vec::new();
1485             let pred = astconv.instantiate_poly_trait_ref(tr,
1486                                                           param_ty,
1487                                                           &mut projections);
1488             projections.into_iter()
1489                        .map(|p| p.to_predicate())
1490                        .chain(Some(pred.to_predicate()))
1491                        .collect()
1492         }
1493         hir::RegionTyParamBound(ref lifetime) => {
1494             let region = astconv.ast_region_to_region(lifetime, None);
1495             let pred = ty::Binder(ty::OutlivesPredicate(param_ty, region));
1496             vec![ty::Predicate::TypeOutlives(pred)]
1497         }
1498         hir::TraitTyParamBound(_, hir::TraitBoundModifier::Maybe) => {
1499             Vec::new()
1500         }
1501     }
1502 }
1503
1504 fn compute_type_of_foreign_fn_decl<'a, 'tcx>(
1505     tcx: TyCtxt<'a, 'tcx, 'tcx>,
1506     def_id: DefId,
1507     decl: &hir::FnDecl,
1508     abi: abi::Abi)
1509     -> Ty<'tcx>
1510 {
1511     let fty = AstConv::ty_of_fn(&ItemCtxt::new(tcx, def_id), hir::Unsafety::Unsafe, abi, decl);
1512
1513     // feature gate SIMD types in FFI, since I (huonw) am not sure the
1514     // ABIs are handled at all correctly.
1515     if abi != abi::Abi::RustIntrinsic && abi != abi::Abi::PlatformIntrinsic
1516             && !tcx.sess.features.borrow().simd_ffi {
1517         let check = |ast_ty: &hir::Ty, ty: ty::Ty| {
1518             if ty.is_simd() {
1519                 tcx.sess.struct_span_err(ast_ty.span,
1520                               &format!("use of SIMD type `{}` in FFI is highly experimental and \
1521                                         may result in invalid code",
1522                                        tcx.hir.node_to_pretty_string(ast_ty.id)))
1523                     .help("add #![feature(simd_ffi)] to the crate attributes to enable")
1524                     .emit();
1525             }
1526         };
1527         for (input, ty) in decl.inputs.iter().zip(*fty.inputs().skip_binder()) {
1528             check(&input, ty)
1529         }
1530         if let hir::Return(ref ty) = decl.output {
1531             check(&ty, *fty.output().skip_binder())
1532         }
1533     }
1534
1535     let substs = Substs::identity_for_item(tcx, def_id);
1536     tcx.mk_fn_def(def_id, substs, fty)
1537 }
1538
1539 fn is_foreign_item<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
1540                              def_id: DefId)
1541                              -> bool {
1542     match tcx.hir.get_if_local(def_id) {
1543         Some(hir_map::NodeForeignItem(..)) => true,
1544         Some(_) => false,
1545         _ => bug!("is_foreign_item applied to non-local def-id {:?}", def_id)
1546     }
1547 }