src/librustc_typeck/collect.rs

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