src/librustc_typeck/collect.rs

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