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