src/librustc_typeck/collect.rs

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