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