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