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