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 generics_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 776                          def_id: DefId)
 777                          -> &'tcx ty::Generics {
 778     use rustc::hir::map::*;
 779     use rustc::hir::*;
 780
 781     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
 782
 783     let node = tcx.hir.get(node_id);
 784     let parent_def_id = match node {
 785         NodeImplItem(_) |
 786         NodeTraitItem(_) |
 787         NodeVariant(_) |
 788         NodeStructCtor(_) |
 789         NodeField(_) => {
 790             let parent_id = tcx.hir.get_parent(node_id);
 791             Some(tcx.hir.local_def_id(parent_id))
 792         }
 793         NodeExpr(&hir::Expr { node: hir::ExprClosure(..), .. }) => {
 794             Some(tcx.closure_base_def_id(def_id))
 795         }
 796         NodeTy(&hir::Ty { node: hir::TyImplTrait(..), .. }) => {
 797             let mut parent_id = node_id;
 798             loop {
 799                 match tcx.hir.get(parent_id) {
 800                     NodeItem(_) | NodeImplItem(_) | NodeTraitItem(_) => break,
 801                     _ => {
 802                         parent_id = tcx.hir.get_parent_node(parent_id);
 803                     }
 804                 }
 805             }
 806             Some(tcx.hir.local_def_id(parent_id))
 807         }
 808         _ => None
 809     };
 810
 811     let mut opt_self = None;
 812     let mut allow_defaults = false;
 813
 814     let no_generics = hir::Generics::empty();
 815     let ast_generics = match node {
 816         NodeTraitItem(item) => {
 817             match item.node {
 818                 TraitItemKind::Method(ref sig, _) => &sig.generics,
 819                 _ => &no_generics
 820             }
 821         }
 822
 823         NodeImplItem(item) => {
 824             match item.node {
 825                 ImplItemKind::Method(ref sig, _) => &sig.generics,
 826                 _ => &no_generics
 827             }
 828         }
 829
 830         NodeItem(item) => {
 831             match item.node {
 832                 ItemFn(.., ref generics, _) |
 833                 ItemImpl(_, _, _, ref generics, ..) => generics,
 834
 835                 ItemTy(_, ref generics) |
 836                 ItemEnum(_, ref generics) |
 837                 ItemStruct(_, ref generics) |
 838                 ItemUnion(_, ref generics) => {
 839                     allow_defaults = true;
 840                     generics
 841                 }
 842
 843                 ItemTrait(_, ref generics, ..) => {
 844                     // Add in the self type parameter.
 845                     //
 846                     // Something of a hack: use the node id for the trait, also as
 847                     // the node id for the Self type parameter.
 848                     let param_id = item.id;
 849
 850                     opt_self = Some(ty::TypeParameterDef {
 851                         index: 0,
 852                         name: keywords::SelfType.name(),
 853                         def_id: tcx.hir.local_def_id(param_id),
 854                         has_default: false,
 855                         object_lifetime_default: rl::Set1::Empty,
 856                         pure_wrt_drop: false,
 857                     });
 858
 859                     allow_defaults = true;
 860                     generics
 861                 }
 862
 863                 _ => &no_generics
 864             }
 865         }
 866
 867         NodeForeignItem(item) => {
 868             match item.node {
 869                 ForeignItemStatic(..) => &no_generics,
 870                 ForeignItemFn(_, _, ref generics) => generics
 871             }
 872         }
 873
 874         _ => &no_generics
 875     };
 876
 877     let has_self = opt_self.is_some();
 878     let mut parent_has_self = false;
 879     let mut own_start = has_self as u32;
 880     let (parent_regions, parent_types) = parent_def_id.map_or((0, 0), |def_id| {
 881         let generics = tcx.generics_of(def_id);
 882         assert_eq!(has_self, false);
 883         parent_has_self = generics.has_self;
 884         own_start = generics.count() as u32;
 885         (generics.parent_regions + generics.regions.len() as u32,
 886             generics.parent_types + generics.types.len() as u32)
 887     });
 888
 889     let early_lifetimes = early_bound_lifetimes_from_generics(tcx, ast_generics);
 890     let regions = early_lifetimes.enumerate().map(|(i, l)| {
 891         let issue_32330 = tcx.named_region_map.issue_32330.get(&l.lifetime.id).cloned();
 892         ty::RegionParameterDef {
 893             name: l.lifetime.name,
 894             index: own_start + i as u32,
 895             def_id: tcx.hir.local_def_id(l.lifetime.id),
 896             pure_wrt_drop: l.pure_wrt_drop,
 897             issue_32330: issue_32330,
 898         }
 899     }).collect::<Vec<_>>();
 900
 901     let object_lifetime_defaults =
 902         tcx.named_region_map.object_lifetime_defaults.get(&node_id);
 903
 904     // Now create the real type parameters.
 905     let type_start = own_start + regions.len() as u32;
 906     let types = ast_generics.ty_params.iter().enumerate().map(|(i, p)| {
 907         if p.name == keywords::SelfType.name() {
 908             span_bug!(p.span, "`Self` should not be the name of a regular parameter");
 909         }
 910
 911         if !allow_defaults && p.default.is_some() {
 912             if !tcx.sess.features.borrow().default_type_parameter_fallback {
 913                 tcx.sess.add_lint(
 914                     lint::builtin::INVALID_TYPE_PARAM_DEFAULT,
 915                     p.id,
 916                     p.span,
 917                     format!("defaults for type parameters are only allowed in `struct`, \
 918                              `enum`, `type`, or `trait` definitions."));
 919             }
 920         }
 921
 922         ty::TypeParameterDef {
 923             index: type_start + i as u32,
 924             name: p.name,
 925             def_id: tcx.hir.local_def_id(p.id),
 926             has_default: p.default.is_some(),
 927             object_lifetime_default:
 928                 object_lifetime_defaults.map_or(rl::Set1::Empty, |o| o[i]),
 929             pure_wrt_drop: p.pure_wrt_drop,
 930         }
 931     });
 932     let mut types: Vec<_> = opt_self.into_iter().chain(types).collect();
 933
 934     // provide junk type parameter defs - the only place that
 935     // cares about anything but the length is instantiation,
 936     // and we don't do that for closures.
 937     if let NodeExpr(&hir::Expr { node: hir::ExprClosure(..), .. }) = node {
 938         tcx.with_freevars(node_id, |fv| {
 939             types.extend(fv.iter().enumerate().map(|(i, _)| ty::TypeParameterDef {
 940                 index: type_start + i as u32,
 941                 name: Symbol::intern("<upvar>"),
 942                 def_id: def_id,
 943                 has_default: false,
 944                 object_lifetime_default: rl::Set1::Empty,
 945                 pure_wrt_drop: false,
 946             }));
 947         });
 948     }
 949
 950     let mut type_param_to_index = BTreeMap::new();
 951     for param in &types {
 952         type_param_to_index.insert(param.def_id.index, param.index);
 953     }
 954
 955     tcx.alloc_generics(ty::Generics {
 956         parent: parent_def_id,
 957         parent_regions: parent_regions,
 958         parent_types: parent_types,
 959         regions: regions,
 960         types: types,
 961         type_param_to_index: type_param_to_index,
 962         has_self: has_self || parent_has_self
 963     })
 964 }
 965
 966 fn type_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 967                      def_id: DefId)
 968                      -> Ty<'tcx> {
 969     use rustc::hir::map::*;
 970     use rustc::hir::*;
 971
 972     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
 973
 974     let icx = ItemCtxt::new(tcx, def_id);
 975
 976     match tcx.hir.get(node_id) {
 977         NodeTraitItem(item) => {
 978             match item.node {
 979                 TraitItemKind::Method(..) => {
 980                     let substs = Substs::identity_for_item(tcx, def_id);
 981                     tcx.mk_fn_def(def_id, substs)
 982                 }
 983                 TraitItemKind::Const(ref ty, _) |
 984                 TraitItemKind::Type(_, Some(ref ty)) => icx.to_ty(ty),
 985                 TraitItemKind::Type(_, None) => {
 986                     span_bug!(item.span, "associated type missing default");
 987                 }
 988             }
 989         }
 990
 991         NodeImplItem(item) => {
 992             match item.node {
 993                 ImplItemKind::Method(..) => {
 994                     let substs = Substs::identity_for_item(tcx, def_id);
 995                     tcx.mk_fn_def(def_id, substs)
 996                 }
 997                 ImplItemKind::Const(ref ty, _) => icx.to_ty(ty),
 998                 ImplItemKind::Type(ref ty) => {
 999                     if tcx.impl_trait_ref(tcx.hir.get_parent_did(node_id)).is_none() {
1000                         span_err!(tcx.sess, item.span, E0202,
1001                                   "associated types are not allowed in inherent impls");
1002                     }
1003
1004                     icx.to_ty(ty)
1005                 }
1006             }
1007         }
1008
1009         NodeItem(item) => {
1010             match item.node {
1011                 ItemStatic(ref t, ..) | ItemConst(ref t, _) |
1012                 ItemTy(ref t, _) | ItemImpl(.., ref t, _) => {
1013                     icx.to_ty(t)
1014                 }
1015                 ItemFn(..) => {
1016                     let substs = Substs::identity_for_item(tcx, def_id);
1017                     tcx.mk_fn_def(def_id, substs)
1018                 }
1019                 ItemEnum(..) |
1020                 ItemStruct(..) |
1021                 ItemUnion(..) => {
1022                     let def = tcx.adt_def(def_id);
1023                     let substs = Substs::identity_for_item(tcx, def_id);
1024                     tcx.mk_adt(def, substs)
1025                 }
1026                 ItemDefaultImpl(..) |
1027                 ItemTrait(..) |
1028                 ItemMod(..) |
1029                 ItemForeignMod(..) |
1030                 ItemGlobalAsm(..) |
1031                 ItemExternCrate(..) |
1032                 ItemUse(..) => {
1033                     span_bug!(
1034                         item.span,
1035                         "compute_type_of_item: unexpected item type: {:?}",
1036                         item.node);
1037                 }
1038             }
1039         }
1040
1041         NodeForeignItem(foreign_item) => {
1042             match foreign_item.node {
1043                 ForeignItemFn(..) => {
1044                     let substs = Substs::identity_for_item(tcx, def_id);
1045                     tcx.mk_fn_def(def_id, substs)
1046                 }
1047                 ForeignItemStatic(ref t, _) => icx.to_ty(t)
1048             }
1049         }
1050
1051         NodeStructCtor(&ref def) |
1052         NodeVariant(&Spanned { node: hir::Variant_ { data: ref def, .. }, .. }) => {
1053             match *def {
1054                 VariantData::Unit(..) | VariantData::Struct(..) => {
1055                     tcx.type_of(tcx.hir.get_parent_did(node_id))
1056                 }
1057                 VariantData::Tuple(..) => {
1058                     let substs = Substs::identity_for_item(tcx, def_id);
1059                     tcx.mk_fn_def(def_id, substs)
1060                 }
1061             }
1062         }
1063
1064         NodeField(field) => icx.to_ty(&field.ty),
1065
1066         NodeExpr(&hir::Expr { node: hir::ExprClosure(..), .. }) => {
1067             tcx.mk_closure(def_id, Substs::for_item(
1068                 tcx, def_id,
1069                 |def, _| {
1070                     let region = def.to_early_bound_region_data();
1071                     tcx.mk_region(ty::ReEarlyBound(region))
1072                 },
1073                 |def, _| tcx.mk_param_from_def(def)
1074             ))
1075         }
1076
1077         NodeExpr(_) => match tcx.hir.get(tcx.hir.get_parent_node(node_id)) {
1078             NodeTy(&hir::Ty { node: TyArray(_, body), .. }) |
1079             NodeTy(&hir::Ty { node: TyTypeof(body), .. }) |
1080             NodeExpr(&hir::Expr { node: ExprRepeat(_, body), .. })
1081                 if body.node_id == node_id => tcx.types.usize,
1082
1083             NodeVariant(&Spanned { node: Variant_ { disr_expr: Some(e), .. }, .. })
1084                 if e.node_id == node_id => {
1085                     tcx.adt_def(tcx.hir.get_parent_did(node_id))
1086                         .repr.discr_type().to_ty(tcx)
1087                 }
1088
1089             x => {
1090                 bug!("unexpected expr parent in type_of_def_id(): {:?}", x);
1091             }
1092         },
1093
1094         NodeTyParam(&hir::TyParam { default: Some(ref ty), .. }) => {
1095             icx.to_ty(ty)
1096         }
1097
1098         NodeTy(&hir::Ty { node: TyImplTrait(..), .. }) => {
1099             let owner = tcx.hir.get_parent_did(node_id);
1100             tcx.typeck_tables_of(owner).node_id_to_type(node_id)
1101         }
1102
1103         x => {
1104             bug!("unexpected sort of node in type_of_def_id(): {:?}", x);
1105         }
1106     }
1107 }
1108
1109 fn fn_sig<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
1110                     def_id: DefId)
1111                     -> ty::PolyFnSig<'tcx> {
1112     use rustc::hir::map::*;
1113     use rustc::hir::*;
1114
1115     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
1116
1117     let icx = ItemCtxt::new(tcx, def_id);
1118
1119     match tcx.hir.get(node_id) {
1120         NodeTraitItem(&hir::TraitItem { node: TraitItemKind::Method(ref sig, _), .. }) |
1121         NodeImplItem(&hir::ImplItem { node: ImplItemKind::Method(ref sig, _), .. }) => {
1122             AstConv::ty_of_fn(&icx, sig.unsafety, sig.abi, &sig.decl)
1123         }
1124
1125         NodeItem(&hir::Item { node: ItemFn(ref decl, unsafety, _, abi, _, _), .. }) => {
1126             AstConv::ty_of_fn(&icx, unsafety, abi, decl)
1127         }
1128
1129         NodeForeignItem(&hir::ForeignItem { node: ForeignItemFn(ref fn_decl, _, _), .. }) => {
1130             let abi = tcx.hir.get_foreign_abi(node_id);
1131             compute_sig_of_foreign_fn_decl(tcx, def_id, fn_decl, abi)
1132         }
1133
1134         NodeStructCtor(&VariantData::Tuple(ref fields, _)) |
1135         NodeVariant(&Spanned { node: hir::Variant_ {
1136             data: VariantData::Tuple(ref fields, _), ..
1137         }, .. }) => {
1138             let ty = tcx.type_of(tcx.hir.get_parent_did(node_id));
1139             let inputs = fields.iter().map(|f| {
1140                 tcx.type_of(tcx.hir.local_def_id(f.id))
1141             });
1142             ty::Binder(tcx.mk_fn_sig(
1143                 inputs,
1144                 ty,
1145                 false,
1146                 hir::Unsafety::Normal,
1147                 abi::Abi::Rust
1148             ))
1149         }
1150
1151         NodeExpr(&hir::Expr { node: hir::ExprClosure(..), .. }) => {
1152             tcx.typeck_tables_of(def_id).closure_tys[&node_id]
1153         }
1154
1155         x => {
1156             bug!("unexpected sort of node in fn_sig(): {:?}", x);
1157         }
1158     }
1159 }
1160
1161 fn impl_trait_ref<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
1162                             def_id: DefId)
1163                             -> Option<ty::TraitRef<'tcx>> {
1164     let icx = ItemCtxt::new(tcx, def_id);
1165
1166     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
1167     match tcx.hir.expect_item(node_id).node {
1168         hir::ItemDefaultImpl(_, ref ast_trait_ref) => {
1169             Some(AstConv::instantiate_mono_trait_ref(&icx,
1170                                                      ast_trait_ref,
1171                                                      tcx.mk_self_type()))
1172         }
1173         hir::ItemImpl(.., ref opt_trait_ref, _, _) => {
1174             opt_trait_ref.as_ref().map(|ast_trait_ref| {
1175                 let selfty = tcx.type_of(def_id);
1176                 AstConv::instantiate_mono_trait_ref(&icx, ast_trait_ref, selfty)
1177             })
1178         }
1179         _ => bug!()
1180     }
1181 }
1182
1183 fn impl_polarity<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
1184                            def_id: DefId)
1185                            -> hir::ImplPolarity {
1186     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
1187     match tcx.hir.expect_item(node_id).node {
1188         hir::ItemImpl(_, polarity, ..) => polarity,
1189         ref item => bug!("impl_polarity: {:?} not an impl", item)
1190     }
1191 }
1192
1193 // Is it marked with ?Sized
1194 fn is_unsized<'gcx: 'tcx, 'tcx>(astconv: &AstConv<'gcx, 'tcx>,
1195                                 ast_bounds: &[hir::TyParamBound],
1196                                 span: Span) -> bool
1197 {
1198     let tcx = astconv.tcx();
1199
1200     // Try to find an unbound in bounds.
1201     let mut unbound = None;
1202     for ab in ast_bounds {
1203         if let &hir::TraitTyParamBound(ref ptr, hir::TraitBoundModifier::Maybe) = ab  {
1204             if unbound.is_none() {
1205                 unbound = Some(ptr.trait_ref.clone());
1206             } else {
1207                 span_err!(tcx.sess, span, E0203,
1208                           "type parameter has more than one relaxed default \
1209                                                 bound, only one is supported");
1210             }
1211         }
1212     }
1213
1214     let kind_id = tcx.lang_items.require(SizedTraitLangItem);
1215     match unbound {
1216         Some(ref tpb) => {
1217             // FIXME(#8559) currently requires the unbound to be built-in.
1218             if let Ok(kind_id) = kind_id {
1219                 if tpb.path.def != Def::Trait(kind_id) {
1220                     tcx.sess.span_warn(span,
1221                                        "default bound relaxed for a type parameter, but \
1222                                        this does nothing because the given bound is not \
1223                                        a default. Only `?Sized` is supported");
1224                 }
1225             }
1226         }
1227         _ if kind_id.is_ok() => {
1228             return false;
1229         }
1230         // No lang item for Sized, so we can't add it as a bound.
1231         None => {}
1232     }
1233
1234     true
1235 }
1236
1237 /// Returns the early-bound lifetimes declared in this generics
1238 /// listing.  For anything other than fns/methods, this is just all
1239 /// the lifetimes that are declared. For fns or methods, we have to
1240 /// screen out those that do not appear in any where-clauses etc using
1241 /// `resolve_lifetime::early_bound_lifetimes`.
1242 fn early_bound_lifetimes_from_generics<'a, 'tcx>(
1243     tcx: TyCtxt<'a, 'tcx, 'tcx>,
1244     ast_generics: &'a hir::Generics)
1245     -> impl Iterator<Item=&'a hir::LifetimeDef>
1246 {
1247     ast_generics
1248         .lifetimes
1249         .iter()
1250         .filter(move |l| !tcx.named_region_map.late_bound.contains(&l.lifetime.id))
1251 }
1252
1253 fn predicates_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
1254                            def_id: DefId)
1255                            -> ty::GenericPredicates<'tcx> {
1256     use rustc::hir::map::*;
1257     use rustc::hir::*;
1258
1259     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
1260     let node = tcx.hir.get(node_id);
1261
1262     let mut is_trait = None;
1263
1264     let icx = ItemCtxt::new(tcx, def_id);
1265     let no_generics = hir::Generics::empty();
1266     let ast_generics = match node {
1267         NodeTraitItem(item) => {
1268             match item.node {
1269                 TraitItemKind::Method(ref sig, _) => &sig.generics,
1270                 _ => &no_generics
1271             }
1272         }
1273
1274         NodeImplItem(item) => {
1275             match item.node {
1276                 ImplItemKind::Method(ref sig, _) => &sig.generics,
1277                 _ => &no_generics
1278             }
1279         }
1280
1281         NodeItem(item) => {
1282             match item.node {
1283                 ItemFn(.., ref generics, _) |
1284                 ItemImpl(_, _, _, ref generics, ..) |
1285                 ItemTy(_, ref generics) |
1286                 ItemEnum(_, ref generics) |
1287                 ItemStruct(_, ref generics) |
1288                 ItemUnion(_, ref generics) => {
1289                     generics
1290                 }
1291
1292                 ItemTrait(_, ref generics, .., ref items) => {
1293                     is_trait = Some((ty::TraitRef {
1294                         def_id: def_id,
1295                         substs: Substs::identity_for_item(tcx, def_id)
1296                     }, items));
1297                     generics
1298                 }
1299
1300                 _ => &no_generics
1301             }
1302         }
1303
1304         NodeForeignItem(item) => {
1305             match item.node {
1306                 ForeignItemStatic(..) => &no_generics,
1307                 ForeignItemFn(_, _, ref generics) => generics
1308             }
1309         }
1310
1311         NodeTy(&Ty { node: TyImplTrait(ref bounds), span, .. }) => {
1312             let substs = Substs::identity_for_item(tcx, def_id);
1313             let anon_ty = tcx.mk_anon(def_id, substs);
1314
1315             // Collect the bounds, i.e. the `A+B+'c` in `impl A+B+'c`.
1316             let bounds = compute_bounds(&icx, anon_ty, bounds,
1317                                         SizedByDefault::Yes,
1318                                         span);
1319             return ty::GenericPredicates {
1320                 parent: None,
1321                 predicates: bounds.predicates(tcx, anon_ty)
1322             };
1323         }
1324
1325         _ => &no_generics
1326     };
1327
1328     let generics = tcx.generics_of(def_id);
1329     let parent_count = generics.parent_count() as u32;
1330     let has_own_self = generics.has_self && parent_count == 0;
1331
1332     let mut predicates = vec![];
1333
1334     // Below we'll consider the bounds on the type parameters (including `Self`)
1335     // and the explicit where-clauses, but to get the full set of predicates
1336     // on a trait we need to add in the supertrait bounds and bounds found on
1337     // associated types.
1338     if let Some((trait_ref, _)) = is_trait {
1339         predicates = tcx.super_predicates_of(def_id).predicates;
1340
1341         // Add in a predicate that `Self:Trait` (where `Trait` is the
1342         // current trait).  This is needed for builtin bounds.
1343         predicates.push(trait_ref.to_poly_trait_ref().to_predicate());
1344     }
1345
1346     // Collect the region predicates that were declared inline as
1347     // well. In the case of parameters declared on a fn or method, we
1348     // have to be careful to only iterate over early-bound regions.
1349     let mut index = parent_count + has_own_self as u32;
1350     for param in early_bound_lifetimes_from_generics(tcx, ast_generics) {
1351         let region = tcx.mk_region(ty::ReEarlyBound(ty::EarlyBoundRegion {
1352             def_id: tcx.hir.local_def_id(param.lifetime.id),
1353             index: index,
1354             name: param.lifetime.name
1355         }));
1356         index += 1;
1357
1358         for bound in &param.bounds {
1359             let bound_region = AstConv::ast_region_to_region(&icx, bound, None);
1360             let outlives = ty::Binder(ty::OutlivesPredicate(region, bound_region));
1361             predicates.push(outlives.to_predicate());
1362         }
1363     }
1364
1365     // Collect the predicates that were written inline by the user on each
1366     // type parameter (e.g., `<T:Foo>`).
1367     for param in &ast_generics.ty_params {
1368         let param_ty = ty::ParamTy::new(index, param.name).to_ty(tcx);
1369         index += 1;
1370
1371         let bounds = compute_bounds(&icx,
1372                                     param_ty,
1373                                     &param.bounds,
1374                                     SizedByDefault::Yes,
1375                                     param.span);
1376         predicates.extend(bounds.predicates(tcx, param_ty));
1377     }
1378
1379     // Add in the bounds that appear in the where-clause
1380     let where_clause = &ast_generics.where_clause;
1381     for predicate in &where_clause.predicates {
1382         match predicate {
1383             &hir::WherePredicate::BoundPredicate(ref bound_pred) => {
1384                 let ty = icx.to_ty(&bound_pred.bounded_ty);
1385
1386                 for bound in bound_pred.bounds.iter() {
1387                     match bound {
1388                         &hir::TyParamBound::TraitTyParamBound(ref poly_trait_ref, _) => {
1389                             let mut projections = Vec::new();
1390
1391                             let trait_ref =
1392                                 AstConv::instantiate_poly_trait_ref(&icx,
1393                                                                     poly_trait_ref,
1394                                                                     ty,
1395                                                                     &mut projections);
1396
1397                             predicates.push(trait_ref.to_predicate());
1398
1399                             for projection in &projections {
1400                                 predicates.push(projection.to_predicate());
1401                             }
1402                         }
1403
1404                         &hir::TyParamBound::RegionTyParamBound(ref lifetime) => {
1405                             let region = AstConv::ast_region_to_region(&icx,
1406                                                                        lifetime,
1407                                                                        None);
1408                             let pred = ty::Binder(ty::OutlivesPredicate(ty, region));
1409                             predicates.push(ty::Predicate::TypeOutlives(pred))
1410                         }
1411                     }
1412                 }
1413             }
1414
1415             &hir::WherePredicate::RegionPredicate(ref region_pred) => {
1416                 let r1 = AstConv::ast_region_to_region(&icx, &region_pred.lifetime, None);
1417                 for bound in &region_pred.bounds {
1418                     let r2 = AstConv::ast_region_to_region(&icx, bound, None);
1419                     let pred = ty::Binder(ty::OutlivesPredicate(r1, r2));
1420                     predicates.push(ty::Predicate::RegionOutlives(pred))
1421                 }
1422             }
1423
1424             &hir::WherePredicate::EqPredicate(..) => {
1425                 // FIXME(#20041)
1426             }
1427         }
1428     }
1429
1430     // Add predicates from associated type bounds.
1431     if let Some((self_trait_ref, trait_items)) = is_trait {
1432         predicates.extend(trait_items.iter().flat_map(|trait_item_ref| {
1433             let trait_item = tcx.hir.trait_item(trait_item_ref.id);
1434             let bounds = match trait_item.node {
1435                 hir::TraitItemKind::Type(ref bounds, _) => bounds,
1436                 _ => {
1437                     return vec![].into_iter();
1438                 }
1439             };
1440
1441             let assoc_ty = tcx.mk_projection(
1442                 tcx.hir.local_def_id(trait_item.id),
1443                 self_trait_ref.substs,
1444             );
1445
1446             let bounds = compute_bounds(&ItemCtxt::new(tcx, def_id),
1447                                         assoc_ty,
1448                                         bounds,
1449                                         SizedByDefault::Yes,
1450                                         trait_item.span);
1451
1452             bounds.predicates(tcx, assoc_ty).into_iter()
1453         }))
1454     }
1455
1456     // Subtle: before we store the predicates into the tcx, we
1457     // sort them so that predicates like `T: Foo<Item=U>` come
1458     // before uses of `U`.  This avoids false ambiguity errors
1459     // in trait checking. See `setup_constraining_predicates`
1460     // for details.
1461     if let NodeItem(&Item { node: ItemImpl(..), .. }) = node {
1462         let self_ty = tcx.type_of(def_id);
1463         let trait_ref = tcx.impl_trait_ref(def_id);
1464         ctp::setup_constraining_predicates(tcx,
1465                                            &mut predicates,
1466                                            trait_ref,
1467                                            &mut ctp::parameters_for_impl(self_ty, trait_ref));
1468     }
1469
1470     ty::GenericPredicates {
1471         parent: generics.parent,
1472         predicates: predicates
1473     }
1474 }
1475
1476 pub enum SizedByDefault { Yes, No, }
1477
1478 /// Translate the AST's notion of ty param bounds (which are an enum consisting of a newtyped Ty or
1479 /// a region) to ty's notion of ty param bounds, which can either be user-defined traits, or the
1480 /// built-in trait (formerly known as kind): Send.
1481 pub fn compute_bounds<'gcx: 'tcx, 'tcx>(astconv: &AstConv<'gcx, 'tcx>,
1482                                         param_ty: ty::Ty<'tcx>,
1483                                         ast_bounds: &[hir::TyParamBound],
1484                                         sized_by_default: SizedByDefault,
1485                                         span: Span)
1486                                         -> Bounds<'tcx>
1487 {
1488     let mut region_bounds = vec![];
1489     let mut trait_bounds = vec![];
1490     for ast_bound in ast_bounds {
1491         match *ast_bound {
1492             hir::TraitTyParamBound(ref b, hir::TraitBoundModifier::None) => {
1493                 trait_bounds.push(b);
1494             }
1495             hir::TraitTyParamBound(_, hir::TraitBoundModifier::Maybe) => {}
1496             hir::RegionTyParamBound(ref l) => {
1497                 region_bounds.push(l);
1498             }
1499         }
1500     }
1501
1502     let mut projection_bounds = vec![];
1503
1504     let mut trait_bounds: Vec<_> = trait_bounds.iter().map(|&bound| {
1505         astconv.instantiate_poly_trait_ref(bound,
1506                                            param_ty,
1507                                            &mut projection_bounds)
1508     }).collect();
1509
1510     let region_bounds = region_bounds.into_iter().map(|r| {
1511         astconv.ast_region_to_region(r, None)
1512     }).collect();
1513
1514     trait_bounds.sort_by(|a,b| a.def_id().cmp(&b.def_id()));
1515
1516     let implicitly_sized = if let SizedByDefault::Yes = sized_by_default {
1517         !is_unsized(astconv, ast_bounds, span)
1518     } else {
1519         false
1520     };
1521
1522     Bounds {
1523         region_bounds: region_bounds,
1524         implicitly_sized: implicitly_sized,
1525         trait_bounds: trait_bounds,
1526         projection_bounds: projection_bounds,
1527     }
1528 }
1529
1530 /// Converts a specific TyParamBound from the AST into a set of
1531 /// predicates that apply to the self-type. A vector is returned
1532 /// because this can be anywhere from 0 predicates (`T:?Sized` adds no
1533 /// predicates) to 1 (`T:Foo`) to many (`T:Bar<X=i32>` adds `T:Bar`
1534 /// and `<T as Bar>::X == i32`).
1535 fn predicates_from_bound<'tcx>(astconv: &AstConv<'tcx, 'tcx>,
1536                                param_ty: Ty<'tcx>,
1537                                bound: &hir::TyParamBound)
1538                                -> Vec<ty::Predicate<'tcx>>
1539 {
1540     match *bound {
1541         hir::TraitTyParamBound(ref tr, hir::TraitBoundModifier::None) => {
1542             let mut projections = Vec::new();
1543             let pred = astconv.instantiate_poly_trait_ref(tr,
1544                                                           param_ty,
1545                                                           &mut projections);
1546             projections.into_iter()
1547                        .map(|p| p.to_predicate())
1548                        .chain(Some(pred.to_predicate()))
1549                        .collect()
1550         }
1551         hir::RegionTyParamBound(ref lifetime) => {
1552             let region = astconv.ast_region_to_region(lifetime, None);
1553             let pred = ty::Binder(ty::OutlivesPredicate(param_ty, region));
1554             vec![ty::Predicate::TypeOutlives(pred)]
1555         }
1556         hir::TraitTyParamBound(_, hir::TraitBoundModifier::Maybe) => {
1557             Vec::new()
1558         }
1559     }
1560 }
1561
1562 fn compute_sig_of_foreign_fn_decl<'a, 'tcx>(
1563     tcx: TyCtxt<'a, 'tcx, 'tcx>,
1564     def_id: DefId,
1565     decl: &hir::FnDecl,
1566     abi: abi::Abi)
1567     -> ty::PolyFnSig<'tcx>
1568 {
1569     let fty = AstConv::ty_of_fn(&ItemCtxt::new(tcx, def_id), hir::Unsafety::Unsafe, abi, decl);
1570
1571     // feature gate SIMD types in FFI, since I (huonw) am not sure the
1572     // ABIs are handled at all correctly.
1573     if abi != abi::Abi::RustIntrinsic && abi != abi::Abi::PlatformIntrinsic
1574             && !tcx.sess.features.borrow().simd_ffi {
1575         let check = |ast_ty: &hir::Ty, ty: ty::Ty| {
1576             if ty.is_simd() {
1577                 tcx.sess.struct_span_err(ast_ty.span,
1578                               &format!("use of SIMD type `{}` in FFI is highly experimental and \
1579                                         may result in invalid code",
1580                                        tcx.hir.node_to_pretty_string(ast_ty.id)))
1581                     .help("add #![feature(simd_ffi)] to the crate attributes to enable")
1582                     .emit();
1583             }
1584         };
1585         for (input, ty) in decl.inputs.iter().zip(*fty.inputs().skip_binder()) {
1586             check(&input, ty)
1587         }
1588         if let hir::Return(ref ty) = decl.output {
1589             check(&ty, *fty.output().skip_binder())
1590         }
1591     }
1592
1593     fty
1594 }
1595
1596 fn is_foreign_item<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
1597                              def_id: DefId)
1598                              -> bool {
1599     match tcx.hir.get_if_local(def_id) {
1600         Some(hir_map::NodeForeignItem(..)) => true,
1601         Some(_) => false,
1602         _ => bug!("is_foreign_item applied to non-local def-id {:?}", def_id)
1603     }
1604 }
1605
1606 fn is_default_impl<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
1607                              def_id: DefId)
1608                              -> bool {
1609     match tcx.hir.get_if_local(def_id) {
1610         Some(hir_map::NodeItem(&hir::Item { node: hir::ItemDefaultImpl(..), .. }))
1611              => true,
1612         Some(_) => false,
1613         _ => bug!("is_default_impl applied to non-local def-id {:?}", def_id)
1614     }
1615 }