src/librustc_typeck/collect.rs

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