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.tcache`
  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 an instance of `ty::TypeScheme`.  This combines the
  26 core type along with a list of the bounds for each parameter. Type
  27 parameters themselves are represented as `ty_param()` instances.
  28
  29 The phasing of type conversion is somewhat complicated. There is no
  30 clear set of phases we can enforce (e.g., converting traits first,
  31 then types, or something like that) because the user can introduce
  32 arbitrary interdependencies. So instead we generally convert things
  33 lazilly and on demand, and include logic that checks for cycles.
  34 Demand is driven by calls to `AstConv::get_item_type_scheme` or
  35 `AstConv::lookup_trait_def`.
  36
  37 Currently, we "convert" types and traits in three phases (note that
  38 conversion only affects the types of items / enum variants / methods;
  39 it does not e.g. compute the types of individual expressions):
  40
  41 0. Intrinsics
  42 1. Trait definitions
  43 2. Type definitions
  44
  45 Conversion itself is done by simply walking each of the items in turn
  46 and invoking an appropriate function (e.g., `trait_def_of_item` or
  47 `convert_item`). However, it is possible that while converting an
  48 item, we may need to compute the *type scheme* or *trait definition*
  49 for other items.
  50
  51 There are some shortcomings in this design:
  52
  53 - Before walking the set of supertraits for a given trait, you must
  54   call `ensure_super_predicates` on that trait def-id. Otherwise,
  55   `lookup_super_predicates` will result in ICEs.
  56 - Because the type scheme includes defaults, cycles through type
  57   parameter defaults are illegal even if those defaults are never
  58   employed. This is not necessarily a bug.
  59 - The phasing of trait definitions before type definitions does not
  60   seem to be necessary, sufficient, or particularly helpful, given that
  61   processing a trait definition can trigger processing a type def and
  62   vice versa. However, if I remove it, I get ICEs, so some more work is
  63   needed in that area. -nmatsakis
  64
  65 */
  66
  67 use astconv::{self, AstConv, ty_of_arg, ast_ty_to_ty, ast_region_to_region};
  68 use metadata::cstore::LOCAL_CRATE;
  69 use middle::def;
  70 use middle::def_id::DefId;
  71 use constrained_type_params as ctp;
  72 use middle::lang_items::SizedTraitLangItem;
  73 use middle::free_region::FreeRegionMap;
  74 use middle::region;
  75 use middle::resolve_lifetime;
  76 use middle::const_eval::{self, ConstVal};
  77 use middle::const_eval::EvalHint::UncheckedExprHint;
  78 use middle::subst::{Substs, FnSpace, ParamSpace, SelfSpace, TypeSpace, VecPerParamSpace};
  79 use middle::ty::{ToPredicate, ImplContainer, ImplOrTraitItemContainer, TraitContainer};
  80 use middle::ty::{self, RegionEscape, ToPolyTraitRef, Ty, TypeScheme};
  81 use middle::ty::{VariantKind};
  82 use middle::ty::fold::{TypeFolder, TypeFoldable};
  83 use middle::ty::util::IntTypeExt;
  84 use middle::infer;
  85 use rscope::*;
  86 use rustc::front::map as hir_map;
  87 use util::common::{ErrorReported, memoized};
  88 use util::nodemap::{FnvHashMap, FnvHashSet};
  89 use write_ty_to_tcx;
  90
  91 use std::cell::{Cell, RefCell};
  92 use std::collections::HashSet;
  93 use std::rc::Rc;
  94
  95 use syntax::abi;
  96 use syntax::ast;
  97 use syntax::attr;
  98 use syntax::codemap::Span;
  99 use syntax::parse::token::special_idents;
 100 use syntax::ptr::P;
 101 use rustc_front::hir;
 102 use rustc_front::visit;
 103 use rustc_front::print::pprust;
 104
 105 ///////////////////////////////////////////////////////////////////////////
 106 // Main entry point
 107
 108 pub fn collect_item_types(tcx: &ty::ctxt) {
 109     let ccx = &CrateCtxt { tcx: tcx, stack: RefCell::new(Vec::new()) };
 110
 111     let mut visitor = CollectTraitDefVisitor{ ccx: ccx };
 112     visit::walk_crate(&mut visitor, ccx.tcx.map.krate());
 113
 114     let mut visitor = CollectItemTypesVisitor{ ccx: ccx };
 115     visit::walk_crate(&mut visitor, ccx.tcx.map.krate());
 116 }
 117
 118 ///////////////////////////////////////////////////////////////////////////
 119
 120 struct CrateCtxt<'a,'tcx:'a> {
 121     tcx: &'a ty::ctxt<'tcx>,
 122
 123     // This stack is used to identify cycles in the user's source.
 124     // Note that these cycles can cross multiple items.
 125     stack: RefCell<Vec<AstConvRequest>>,
 126 }
 127
 128 /// Context specific to some particular item. This is what implements
 129 /// AstConv. It has information about the predicates that are defined
 130 /// on the trait. Unfortunately, this predicate information is
 131 /// available in various different forms at various points in the
 132 /// process. So we can't just store a pointer to e.g. the AST or the
 133 /// parsed ty form, we have to be more flexible. To this end, the
 134 /// `ItemCtxt` is parameterized by a `GetTypeParameterBounds` object
 135 /// that it uses to satisfy `get_type_parameter_bounds` requests.
 136 /// This object might draw the information from the AST
 137 /// (`hir::Generics`) or it might draw from a `ty::GenericPredicates`
 138 /// or both (a tuple).
 139 struct ItemCtxt<'a,'tcx:'a> {
 140     ccx: &'a CrateCtxt<'a,'tcx>,
 141     param_bounds: &'a (GetTypeParameterBounds<'tcx>+'a),
 142 }
 143
 144 #[derive(Copy, Clone, PartialEq, Eq)]
 145 enum AstConvRequest {
 146     GetItemTypeScheme(DefId),
 147     GetTraitDef(DefId),
 148     EnsureSuperPredicates(DefId),
 149     GetTypeParameterBounds(ast::NodeId),
 150 }
 151
 152 ///////////////////////////////////////////////////////////////////////////
 153 // First phase: just collect *trait definitions* -- basically, the set
 154 // of type parameters and supertraits. This is information we need to
 155 // know later when parsing field defs.
 156
 157 struct CollectTraitDefVisitor<'a, 'tcx: 'a> {
 158     ccx: &'a CrateCtxt<'a, 'tcx>
 159 }
 160
 161 impl<'a, 'tcx, 'v> visit::Visitor<'v> for CollectTraitDefVisitor<'a, 'tcx> {
 162     fn visit_item(&mut self, i: &hir::Item) {
 163         match i.node {
 164             hir::ItemTrait(..) => {
 165                 // computing the trait def also fills in the table
 166                 let _ = trait_def_of_item(self.ccx, i);
 167             }
 168             _ => { }
 169         }
 170
 171         visit::walk_item(self, i);
 172     }
 173 }
 174
 175 ///////////////////////////////////////////////////////////////////////////
 176 // Second phase: collection proper.
 177
 178 struct CollectItemTypesVisitor<'a, 'tcx: 'a> {
 179     ccx: &'a CrateCtxt<'a, 'tcx>
 180 }
 181
 182 impl<'a, 'tcx, 'v> visit::Visitor<'v> for CollectItemTypesVisitor<'a, 'tcx> {
 183     fn visit_item(&mut self, i: &hir::Item) {
 184         convert_item(self.ccx, i);
 185         visit::walk_item(self, i);
 186     }
 187     fn visit_foreign_item(&mut self, i: &hir::ForeignItem) {
 188         convert_foreign_item(self.ccx, i);
 189         visit::walk_foreign_item(self, i);
 190     }
 191 }
 192
 193 ///////////////////////////////////////////////////////////////////////////
 194 // Utility types and common code for the above passes.
 195
 196 impl<'a,'tcx> CrateCtxt<'a,'tcx> {
 197     fn icx(&'a self, param_bounds: &'a GetTypeParameterBounds<'tcx>) -> ItemCtxt<'a,'tcx> {
 198         ItemCtxt { ccx: self, param_bounds: param_bounds }
 199     }
 200
 201     fn method_ty(&self, method_id: ast::NodeId) -> Rc<ty::Method<'tcx>> {
 202         let def_id = DefId::local(method_id);
 203         match *self.tcx.impl_or_trait_items.borrow().get(&def_id).unwrap() {
 204             ty::MethodTraitItem(ref mty) => mty.clone(),
 205             _ => {
 206                 self.tcx.sess.bug(&format!("method with id {} has the wrong type", method_id));
 207             }
 208         }
 209     }
 210
 211     fn cycle_check<F,R>(&self,
 212                         span: Span,
 213                         request: AstConvRequest,
 214                         code: F)
 215                         -> Result<R,ErrorReported>
 216         where F: FnOnce() -> Result<R,ErrorReported>
 217     {
 218         {
 219             let mut stack = self.stack.borrow_mut();
 220             match stack.iter().enumerate().rev().find(|&(_, r)| *r == request) {
 221                 None => { }
 222                 Some((i, _)) => {
 223                     let cycle = &stack[i..];
 224                     self.report_cycle(span, cycle);
 225                     return Err(ErrorReported);
 226                 }
 227             }
 228             stack.push(request);
 229         }
 230
 231         let result = code();
 232
 233         self.stack.borrow_mut().pop();
 234         result
 235     }
 236
 237     fn report_cycle(&self,
 238                     span: Span,
 239                     cycle: &[AstConvRequest])
 240     {
 241         assert!(!cycle.is_empty());
 242         let tcx = self.tcx;
 243
 244         span_err!(tcx.sess, span, E0391,
 245             "unsupported cyclic reference between types/traits detected");
 246
 247         match cycle[0] {
 248             AstConvRequest::GetItemTypeScheme(def_id) |
 249             AstConvRequest::GetTraitDef(def_id) => {
 250                 tcx.sess.note(
 251                     &format!("the cycle begins when processing `{}`...",
 252                              tcx.item_path_str(def_id)));
 253             }
 254             AstConvRequest::EnsureSuperPredicates(def_id) => {
 255                 tcx.sess.note(
 256                     &format!("the cycle begins when computing the supertraits of `{}`...",
 257                              tcx.item_path_str(def_id)));
 258             }
 259             AstConvRequest::GetTypeParameterBounds(id) => {
 260                 let def = tcx.type_parameter_def(id);
 261                 tcx.sess.note(
 262                     &format!("the cycle begins when computing the bounds \
 263                               for type parameter `{}`...",
 264                              def.name));
 265             }
 266         }
 267
 268         for request in &cycle[1..] {
 269             match *request {
 270                 AstConvRequest::GetItemTypeScheme(def_id) |
 271                 AstConvRequest::GetTraitDef(def_id) => {
 272                     tcx.sess.note(
 273                         &format!("...which then requires processing `{}`...",
 274                                  tcx.item_path_str(def_id)));
 275                 }
 276                 AstConvRequest::EnsureSuperPredicates(def_id) => {
 277                     tcx.sess.note(
 278                         &format!("...which then requires computing the supertraits of `{}`...",
 279                                  tcx.item_path_str(def_id)));
 280                 }
 281                 AstConvRequest::GetTypeParameterBounds(id) => {
 282                     let def = tcx.type_parameter_def(id);
 283                     tcx.sess.note(
 284                         &format!("...which then requires computing the bounds \
 285                                   for type parameter `{}`...",
 286                                  def.name));
 287                 }
 288             }
 289         }
 290
 291         match cycle[0] {
 292             AstConvRequest::GetItemTypeScheme(def_id) |
 293             AstConvRequest::GetTraitDef(def_id) => {
 294                 tcx.sess.note(
 295                     &format!("...which then again requires processing `{}`, completing the cycle.",
 296                              tcx.item_path_str(def_id)));
 297             }
 298             AstConvRequest::EnsureSuperPredicates(def_id) => {
 299                 tcx.sess.note(
 300                     &format!("...which then again requires computing the supertraits of `{}`, \
 301                               completing the cycle.",
 302                              tcx.item_path_str(def_id)));
 303             }
 304             AstConvRequest::GetTypeParameterBounds(id) => {
 305                 let def = tcx.type_parameter_def(id);
 306                 tcx.sess.note(
 307                     &format!("...which then again requires computing the bounds \
 308                               for type parameter `{}`, completing the cycle.",
 309                              def.name));
 310             }
 311         }
 312     }
 313
 314     /// Loads the trait def for a given trait, returning ErrorReported if a cycle arises.
 315     fn get_trait_def(&self, trait_id: DefId)
 316                      -> &'tcx ty::TraitDef<'tcx>
 317     {
 318         let tcx = self.tcx;
 319
 320         if trait_id.krate != LOCAL_CRATE {
 321             return tcx.lookup_trait_def(trait_id)
 322         }
 323
 324         let item = match tcx.map.get(trait_id.node) {
 325             hir_map::NodeItem(item) => item,
 326             _ => tcx.sess.bug(&format!("get_trait_def({:?}): not an item", trait_id))
 327         };
 328
 329         trait_def_of_item(self, &*item)
 330     }
 331
 332     /// Ensure that the (transitive) super predicates for
 333     /// `trait_def_id` are available. This will report a cycle error
 334     /// if a trait `X` (transitively) extends itself in some form.
 335     fn ensure_super_predicates(&self, span: Span, trait_def_id: DefId)
 336                                -> Result<(), ErrorReported>
 337     {
 338         self.cycle_check(span, AstConvRequest::EnsureSuperPredicates(trait_def_id), || {
 339             let def_ids = ensure_super_predicates_step(self, trait_def_id);
 340
 341             for def_id in def_ids {
 342                 try!(self.ensure_super_predicates(span, def_id));
 343             }
 344
 345             Ok(())
 346         })
 347     }
 348 }
 349
 350 impl<'a,'tcx> ItemCtxt<'a,'tcx> {
 351     fn to_ty<RS:RegionScope>(&self, rs: &RS, ast_ty: &hir::Ty) -> Ty<'tcx> {
 352         ast_ty_to_ty(self, rs, ast_ty)
 353     }
 354 }
 355
 356 impl<'a, 'tcx> AstConv<'tcx> for ItemCtxt<'a, 'tcx> {
 357     fn tcx(&self) -> &ty::ctxt<'tcx> { self.ccx.tcx }
 358
 359     fn get_item_type_scheme(&self, span: Span, id: DefId)
 360                             -> Result<ty::TypeScheme<'tcx>, ErrorReported>
 361     {
 362         self.ccx.cycle_check(span, AstConvRequest::GetItemTypeScheme(id), || {
 363             Ok(type_scheme_of_def_id(self.ccx, id))
 364         })
 365     }
 366
 367     fn get_trait_def(&self, span: Span, id: DefId)
 368                      -> Result<&'tcx ty::TraitDef<'tcx>, ErrorReported>
 369     {
 370         self.ccx.cycle_check(span, AstConvRequest::GetTraitDef(id), || {
 371             Ok(self.ccx.get_trait_def(id))
 372         })
 373     }
 374
 375     fn ensure_super_predicates(&self,
 376                                span: Span,
 377                                trait_def_id: DefId)
 378                                -> Result<(), ErrorReported>
 379     {
 380         debug!("ensure_super_predicates(trait_def_id={:?})",
 381                trait_def_id);
 382
 383         self.ccx.ensure_super_predicates(span, trait_def_id)
 384     }
 385
 386
 387     fn get_type_parameter_bounds(&self,
 388                                  span: Span,
 389                                  node_id: ast::NodeId)
 390                                  -> Result<Vec<ty::PolyTraitRef<'tcx>>, ErrorReported>
 391     {
 392         self.ccx.cycle_check(span, AstConvRequest::GetTypeParameterBounds(node_id), || {
 393             let v = self.param_bounds.get_type_parameter_bounds(self, span, node_id)
 394                                      .into_iter()
 395                                      .filter_map(|p| p.to_opt_poly_trait_ref())
 396                                      .collect();
 397             Ok(v)
 398         })
 399     }
 400
 401     fn trait_defines_associated_type_named(&self,
 402                                            trait_def_id: DefId,
 403                                            assoc_name: ast::Name)
 404                                            -> bool
 405     {
 406         if trait_def_id.is_local() {
 407             trait_defines_associated_type_named(self.ccx, trait_def_id.node, assoc_name)
 408         } else {
 409             let trait_def = self.tcx().lookup_trait_def(trait_def_id);
 410             trait_def.associated_type_names.contains(&assoc_name)
 411         }
 412     }
 413
 414         fn ty_infer(&self,
 415                     _ty_param_def: Option<ty::TypeParameterDef<'tcx>>,
 416                     _substs: Option<&mut Substs<'tcx>>,
 417                     _space: Option<ParamSpace>,
 418                     span: Span) -> Ty<'tcx> {
 419         span_err!(self.tcx().sess, span, E0121,
 420                   "the type placeholder `_` is not allowed within types on item signatures");
 421         self.tcx().types.err
 422     }
 423
 424     fn projected_ty(&self,
 425                     _span: Span,
 426                     trait_ref: ty::TraitRef<'tcx>,
 427                     item_name: ast::Name)
 428                     -> Ty<'tcx>
 429     {
 430         self.tcx().mk_projection(trait_ref, item_name)
 431     }
 432 }
 433
 434 /// Interface used to find the bounds on a type parameter from within
 435 /// an `ItemCtxt`. This allows us to use multiple kinds of sources.
 436 trait GetTypeParameterBounds<'tcx> {
 437     fn get_type_parameter_bounds(&self,
 438                                  astconv: &AstConv<'tcx>,
 439                                  span: Span,
 440                                  node_id: ast::NodeId)
 441                                  -> Vec<ty::Predicate<'tcx>>;
 442 }
 443
 444 /// Find bounds from both elements of the tuple.
 445 impl<'a,'b,'tcx,A,B> GetTypeParameterBounds<'tcx> for (&'a A,&'b B)
 446     where A : GetTypeParameterBounds<'tcx>, B : GetTypeParameterBounds<'tcx>
 447 {
 448     fn get_type_parameter_bounds(&self,
 449                                  astconv: &AstConv<'tcx>,
 450                                  span: Span,
 451                                  node_id: ast::NodeId)
 452                                  -> Vec<ty::Predicate<'tcx>>
 453     {
 454         let mut v = self.0.get_type_parameter_bounds(astconv, span, node_id);
 455         v.extend(self.1.get_type_parameter_bounds(astconv, span, node_id));
 456         v
 457     }
 458 }
 459
 460 /// Empty set of bounds.
 461 impl<'tcx> GetTypeParameterBounds<'tcx> for () {
 462     fn get_type_parameter_bounds(&self,
 463                                  _astconv: &AstConv<'tcx>,
 464                                  _span: Span,
 465                                  _node_id: ast::NodeId)
 466                                  -> Vec<ty::Predicate<'tcx>>
 467     {
 468         Vec::new()
 469     }
 470 }
 471
 472 /// Find bounds from the parsed and converted predicates.  This is
 473 /// used when converting methods, because by that time the predicates
 474 /// from the trait/impl have been fully converted.
 475 impl<'tcx> GetTypeParameterBounds<'tcx> for ty::GenericPredicates<'tcx> {
 476     fn get_type_parameter_bounds(&self,
 477                                  astconv: &AstConv<'tcx>,
 478                                  _span: Span,
 479                                  node_id: ast::NodeId)
 480                                  -> Vec<ty::Predicate<'tcx>>
 481     {
 482         let def = astconv.tcx().type_parameter_def(node_id);
 483
 484         self.predicates
 485             .iter()
 486             .filter(|predicate| {
 487                 match **predicate {
 488                     ty::Predicate::Trait(ref data) => {
 489                         data.skip_binder().self_ty().is_param(def.space, def.index)
 490                     }
 491                     ty::Predicate::TypeOutlives(ref data) => {
 492                         data.skip_binder().0.is_param(def.space, def.index)
 493                     }
 494                     ty::Predicate::Equate(..) |
 495                     ty::Predicate::RegionOutlives(..) |
 496                     ty::Predicate::WellFormed(..) |
 497                     ty::Predicate::ObjectSafe(..) |
 498                     ty::Predicate::Projection(..) => {
 499                         false
 500                     }
 501                 }
 502             })
 503             .cloned()
 504             .collect()
 505     }
 506 }
 507
 508 /// Find bounds from hir::Generics. This requires scanning through the
 509 /// AST. We do this to avoid having to convert *all* the bounds, which
 510 /// would create artificial cycles. Instead we can only convert the
 511 /// bounds for those a type parameter `X` if `X::Foo` is used.
 512 impl<'tcx> GetTypeParameterBounds<'tcx> for hir::Generics {
 513     fn get_type_parameter_bounds(&self,
 514                                  astconv: &AstConv<'tcx>,
 515                                  _: Span,
 516                                  node_id: ast::NodeId)
 517                                  -> Vec<ty::Predicate<'tcx>>
 518     {
 519         // In the AST, bounds can derive from two places. Either
 520         // written inline like `<T:Foo>` or in a where clause like
 521         // `where T:Foo`.
 522
 523         let def = astconv.tcx().type_parameter_def(node_id);
 524         let ty = astconv.tcx().mk_param_from_def(&def);
 525
 526         let from_ty_params =
 527             self.ty_params
 528                 .iter()
 529                 .filter(|p| p.id == node_id)
 530                 .flat_map(|p| p.bounds.iter())
 531                 .flat_map(|b| predicates_from_bound(astconv, ty, b));
 532
 533         let from_where_clauses =
 534             self.where_clause
 535                 .predicates
 536                 .iter()
 537                 .filter_map(|wp| match *wp {
 538                     hir::WherePredicate::BoundPredicate(ref bp) => Some(bp),
 539                     _ => None
 540                 })
 541                 .filter(|bp| is_param(astconv.tcx(), &bp.bounded_ty, node_id))
 542                 .flat_map(|bp| bp.bounds.iter())
 543                 .flat_map(|b| predicates_from_bound(astconv, ty, b));
 544
 545         from_ty_params.chain(from_where_clauses).collect()
 546     }
 547 }
 548
 549 /// Tests whether this is the AST for a reference to the type
 550 /// parameter with id `param_id`. We use this so as to avoid running
 551 /// `ast_ty_to_ty`, because we want to avoid triggering an all-out
 552 /// conversion of the type to avoid inducing unnecessary cycles.
 553 fn is_param<'tcx>(tcx: &ty::ctxt<'tcx>,
 554                   ast_ty: &hir::Ty,
 555                   param_id: ast::NodeId)
 556                   -> bool
 557 {
 558     if let hir::TyPath(None, _) = ast_ty.node {
 559         let path_res = *tcx.def_map.borrow().get(&ast_ty.id).unwrap();
 560         match path_res.base_def {
 561             def::DefSelfTy(Some(def_id), None) => {
 562                 path_res.depth == 0 && def_id.node == param_id
 563             }
 564             def::DefTyParam(_, _, def_id, _) => {
 565                 path_res.depth == 0 && def_id == DefId::local(param_id)
 566             }
 567             _ => {
 568                 false
 569             }
 570         }
 571     } else {
 572         false
 573     }
 574 }
 575
 576
 577 fn convert_method<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 578                             container: ImplOrTraitItemContainer,
 579                             sig: &hir::MethodSig,
 580                             id: ast::NodeId,
 581                             name: ast::Name,
 582                             vis: hir::Visibility,
 583                             untransformed_rcvr_ty: Ty<'tcx>,
 584                             rcvr_ty_generics: &ty::Generics<'tcx>,
 585                             rcvr_ty_predicates: &ty::GenericPredicates<'tcx>) {
 586     let ty_generics = ty_generics_for_fn(ccx, &sig.generics, rcvr_ty_generics);
 587
 588     let ty_generic_predicates =
 589         ty_generic_predicates_for_fn(ccx, &sig.generics, rcvr_ty_predicates);
 590
 591     let (fty, explicit_self_category) =
 592         astconv::ty_of_method(&ccx.icx(&(rcvr_ty_predicates, &sig.generics)),
 593                               sig, untransformed_rcvr_ty);
 594
 595     let def_id = DefId::local(id);
 596     let ty_method = ty::Method::new(name,
 597                                     ty_generics,
 598                                     ty_generic_predicates,
 599                                     fty,
 600                                     explicit_self_category,
 601                                     vis,
 602                                     def_id,
 603                                     container);
 604
 605     let fty = ccx.tcx.mk_fn(Some(def_id),
 606                             ccx.tcx.mk_bare_fn(ty_method.fty.clone()));
 607     debug!("method {} (id {}) has type {:?}",
 608             name, id, fty);
 609     ccx.tcx.register_item_type(def_id, TypeScheme {
 610         generics: ty_method.generics.clone(),
 611         ty: fty
 612     });
 613     ccx.tcx.predicates.borrow_mut().insert(def_id, ty_method.predicates.clone());
 614
 615     write_ty_to_tcx(ccx.tcx, id, fty);
 616
 617     debug!("writing method type: def_id={:?} mty={:?}",
 618             def_id, ty_method);
 619
 620     ccx.tcx.impl_or_trait_items.borrow_mut().insert(def_id,
 621         ty::MethodTraitItem(Rc::new(ty_method)));
 622 }
 623
 624 fn convert_field<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 625                            struct_generics: &ty::Generics<'tcx>,
 626                            struct_predicates: &ty::GenericPredicates<'tcx>,
 627                            v: &hir::StructField,
 628                            ty_f: ty::FieldDefMaster<'tcx>)
 629 {
 630     let tt = ccx.icx(struct_predicates).to_ty(&ExplicitRscope, &*v.node.ty);
 631     ty_f.fulfill_ty(tt);
 632     write_ty_to_tcx(ccx.tcx, v.node.id, tt);
 633
 634     /* add the field to the tcache */
 635     ccx.tcx.register_item_type(DefId::local(v.node.id),
 636                                ty::TypeScheme {
 637                                    generics: struct_generics.clone(),
 638                                    ty: tt
 639                                });
 640     ccx.tcx.predicates.borrow_mut().insert(DefId::local(v.node.id),
 641                                            struct_predicates.clone());
 642 }
 643
 644 fn convert_associated_const<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 645                                       container: ImplOrTraitItemContainer,
 646                                       name: ast::Name,
 647                                       id: ast::NodeId,
 648                                       vis: hir::Visibility,
 649                                       ty: ty::Ty<'tcx>,
 650                                       has_value: bool)
 651 {
 652     ccx.tcx.predicates.borrow_mut().insert(DefId::local(id),
 653                                            ty::GenericPredicates::empty());
 654
 655     write_ty_to_tcx(ccx.tcx, id, ty);
 656
 657     let associated_const = Rc::new(ty::AssociatedConst {
 658         name: name,
 659         vis: vis,
 660         def_id: DefId::local(id),
 661         container: container,
 662         ty: ty,
 663         has_value: has_value
 664     });
 665     ccx.tcx.impl_or_trait_items.borrow_mut()
 666        .insert(DefId::local(id), ty::ConstTraitItem(associated_const));
 667 }
 668
 669 fn convert_associated_type<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 670                                      container: ImplOrTraitItemContainer,
 671                                      name: ast::Name,
 672                                      id: ast::NodeId,
 673                                      vis: hir::Visibility,
 674                                      ty: Option<Ty<'tcx>>)
 675 {
 676     let associated_type = Rc::new(ty::AssociatedType {
 677         name: name,
 678         vis: vis,
 679         ty: ty,
 680         def_id: DefId::local(id),
 681         container: container
 682     });
 683     ccx.tcx.impl_or_trait_items.borrow_mut()
 684        .insert(DefId::local(id), ty::TypeTraitItem(associated_type));
 685 }
 686
 687 fn convert_methods<'a,'tcx,'i,I>(ccx: &CrateCtxt<'a, 'tcx>,
 688                                  container: ImplOrTraitItemContainer,
 689                                  methods: I,
 690                                  untransformed_rcvr_ty: Ty<'tcx>,
 691                                  rcvr_ty_generics: &ty::Generics<'tcx>,
 692                                  rcvr_ty_predicates: &ty::GenericPredicates<'tcx>)
 693     where I: Iterator<Item=(&'i hir::MethodSig, ast::NodeId, ast::Name, hir::Visibility, Span)>
 694 {
 695     debug!("convert_methods(untransformed_rcvr_ty={:?}, rcvr_ty_generics={:?}, \
 696                             rcvr_ty_predicates={:?})",
 697            untransformed_rcvr_ty,
 698            rcvr_ty_generics,
 699            rcvr_ty_predicates);
 700
 701     for (sig, id, name, vis, _span) in methods {
 702         convert_method(ccx,
 703                        container,
 704                        sig,
 705                        id,
 706                        name,
 707                        vis,
 708                        untransformed_rcvr_ty,
 709                        rcvr_ty_generics,
 710                        rcvr_ty_predicates);
 711     }
 712 }
 713
 714 fn ensure_no_ty_param_bounds(ccx: &CrateCtxt,
 715                                  span: Span,
 716                                  generics: &hir::Generics,
 717                                  thing: &'static str) {
 718     let mut warn = false;
 719
 720     for ty_param in generics.ty_params.iter() {
 721         for bound in ty_param.bounds.iter() {
 722             match *bound {
 723                 hir::TraitTyParamBound(..) => {
 724                     warn = true;
 725                 }
 726                 hir::RegionTyParamBound(..) => { }
 727             }
 728         }
 729     }
 730
 731     if warn {
 732         // According to accepted RFC #XXX, we should
 733         // eventually accept these, but it will not be
 734         // part of this PR. Still, convert to warning to
 735         // make bootstrapping easier.
 736         span_warn!(ccx.tcx.sess, span, E0122,
 737                    "trait bounds are not (yet) enforced \
 738                    in {} definitions",
 739                    thing);
 740     }
 741 }
 742
 743 fn convert_item(ccx: &CrateCtxt, it: &hir::Item) {
 744     let tcx = ccx.tcx;
 745     debug!("convert: item {} with id {}", it.name, it.id);
 746     match it.node {
 747         // These don't define types.
 748         hir::ItemExternCrate(_) | hir::ItemUse(_) |
 749         hir::ItemForeignMod(_) | hir::ItemMod(_) => {
 750         }
 751         hir::ItemEnum(ref enum_definition, _) => {
 752             let (scheme, predicates) = convert_typed_item(ccx, it);
 753             write_ty_to_tcx(tcx, it.id, scheme.ty);
 754             convert_enum_variant_types(ccx,
 755                                        tcx.lookup_adt_def_master(DefId::local(it.id)),
 756                                        scheme,
 757                                        predicates,
 758                                        &enum_definition.variants);
 759         },
 760         hir::ItemDefaultImpl(_, ref ast_trait_ref) => {
 761             let trait_ref =
 762                 astconv::instantiate_mono_trait_ref(&ccx.icx(&()),
 763                                                     &ExplicitRscope,
 764                                                     ast_trait_ref,
 765                                                     None);
 766
 767             tcx.record_trait_has_default_impl(trait_ref.def_id);
 768
 769             tcx.impl_trait_refs.borrow_mut().insert(DefId::local(it.id), Some(trait_ref));
 770         }
 771         hir::ItemImpl(_, _,
 772                       ref generics,
 773                       ref opt_trait_ref,
 774                       ref selfty,
 775                       ref impl_items) => {
 776             // Create generics from the generics specified in the impl head.
 777             debug!("convert: ast_generics={:?}", generics);
 778             let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
 779             let ty_predicates = ty_generic_predicates_for_type_or_impl(ccx, generics);
 780
 781             debug!("convert: impl_bounds={:?}", ty_predicates);
 782
 783             let selfty = ccx.icx(&ty_predicates).to_ty(&ExplicitRscope, &**selfty);
 784             write_ty_to_tcx(tcx, it.id, selfty);
 785
 786             tcx.register_item_type(DefId::local(it.id),
 787                                    TypeScheme { generics: ty_generics.clone(),
 788                                                 ty: selfty });
 789             tcx.predicates.borrow_mut().insert(DefId::local(it.id),
 790                                                ty_predicates.clone());
 791             if let &Some(ref ast_trait_ref) = opt_trait_ref {
 792                 tcx.impl_trait_refs.borrow_mut().insert(
 793                     DefId::local(it.id),
 794                     Some(astconv::instantiate_mono_trait_ref(&ccx.icx(&ty_predicates),
 795                                                              &ExplicitRscope,
 796                                                              ast_trait_ref,
 797                                                              Some(selfty)))
 798                         );
 799             } else {
 800                 tcx.impl_trait_refs.borrow_mut().insert(DefId::local(it.id), None);
 801             }
 802
 803
 804             // If there is a trait reference, treat the methods as always public.
 805             // This is to work around some incorrect behavior in privacy checking:
 806             // when the method belongs to a trait, it should acquire the privacy
 807             // from the trait, not the impl. Forcing the visibility to be public
 808             // makes things sorta work.
 809             let parent_visibility = if opt_trait_ref.is_some() {
 810                 hir::Public
 811             } else {
 812                 it.vis
 813             };
 814
 815             // Convert all the associated consts.
 816             // Also, check if there are any duplicate associated items
 817             let mut seen_type_items = FnvHashSet();
 818             let mut seen_value_items = FnvHashSet();
 819
 820             for impl_item in impl_items {
 821                 let seen_items = match impl_item.node {
 822                     hir::TypeImplItem(_) => &mut seen_type_items,
 823                     _                    => &mut seen_value_items,
 824                 };
 825                 if !seen_items.insert(impl_item.name) {
 826                     let desc = match impl_item.node {
 827                         hir::ConstImplItem(_, _) => "associated constant",
 828                         hir::TypeImplItem(_) => "associated type",
 829                         hir::MethodImplItem(ref sig, _) =>
 830                             match sig.explicit_self.node {
 831                                 hir::SelfStatic => "associated function",
 832                                 _ => "method",
 833                             },
 834                     };
 835
 836                     span_err!(tcx.sess, impl_item.span, E0201, "duplicate {}", desc);
 837                 }
 838
 839                 if let hir::ConstImplItem(ref ty, _) = impl_item.node {
 840                     let ty = ccx.icx(&ty_predicates)
 841                                 .to_ty(&ExplicitRscope, &*ty);
 842                     tcx.register_item_type(DefId::local(impl_item.id),
 843                                            TypeScheme {
 844                                                generics: ty_generics.clone(),
 845                                                ty: ty,
 846                                            });
 847                     convert_associated_const(ccx, ImplContainer(DefId::local(it.id)),
 848                                              impl_item.name, impl_item.id,
 849                                              impl_item.vis.inherit_from(parent_visibility),
 850                                              ty, true /* has_value */);
 851                 }
 852             }
 853
 854             // Convert all the associated types.
 855             for impl_item in impl_items {
 856                 if let hir::TypeImplItem(ref ty) = impl_item.node {
 857                     if opt_trait_ref.is_none() {
 858                         span_err!(tcx.sess, impl_item.span, E0202,
 859                                   "associated types are not allowed in inherent impls");
 860                     }
 861
 862                     let typ = ccx.icx(&ty_predicates).to_ty(&ExplicitRscope, ty);
 863
 864                     convert_associated_type(ccx, ImplContainer(DefId::local(it.id)),
 865                                             impl_item.name, impl_item.id, impl_item.vis,
 866                                             Some(typ));
 867                 }
 868             }
 869
 870             let methods = impl_items.iter().filter_map(|ii| {
 871                 if let hir::MethodImplItem(ref sig, _) = ii.node {
 872                     // if the method specifies a visibility, use that, otherwise
 873                     // inherit the visibility from the impl (so `foo` in `pub impl
 874                     // { fn foo(); }` is public, but private in `impl { fn
 875                     // foo(); }`).
 876                     let method_vis = ii.vis.inherit_from(parent_visibility);
 877                     Some((sig, ii.id, ii.name, method_vis, ii.span))
 878                 } else {
 879                     None
 880                 }
 881             });
 882             convert_methods(ccx,
 883                             ImplContainer(DefId::local(it.id)),
 884                             methods,
 885                             selfty,
 886                             &ty_generics,
 887                             &ty_predicates);
 888
 889             for impl_item in impl_items {
 890                 if let hir::MethodImplItem(ref sig, ref body) = impl_item.node {
 891                     let body_id = body.id;
 892                     check_method_self_type(ccx,
 893                                            &BindingRscope::new(),
 894                                            ccx.method_ty(impl_item.id),
 895                                            selfty,
 896                                            &sig.explicit_self,
 897                                            body_id);
 898                 }
 899             }
 900
 901             enforce_impl_params_are_constrained(tcx,
 902                                                 generics,
 903                                                 DefId::local(it.id),
 904                                                 impl_items);
 905         },
 906         hir::ItemTrait(_, _, _, ref trait_items) => {
 907             let trait_def = trait_def_of_item(ccx, it);
 908             let _: Result<(), ErrorReported> = // any error is already reported, can ignore
 909                 ccx.ensure_super_predicates(it.span, DefId::local(it.id));
 910             convert_trait_predicates(ccx, it);
 911             let trait_predicates = tcx.lookup_predicates(DefId::local(it.id));
 912
 913             debug!("convert: trait_bounds={:?}", trait_predicates);
 914
 915             // Convert all the associated types.
 916             for trait_item in trait_items {
 917                 match trait_item.node {
 918                     hir::ConstTraitItem(ref ty, ref default) => {
 919                         let ty = ccx.icx(&trait_predicates)
 920                                     .to_ty(&ExplicitRscope, ty);
 921                         tcx.register_item_type(DefId::local(trait_item.id),
 922                                                TypeScheme {
 923                                                    generics: trait_def.generics.clone(),
 924                                                    ty: ty,
 925                                                });
 926                         convert_associated_const(ccx, TraitContainer(DefId::local(it.id)),
 927                                                  trait_item.name, trait_item.id,
 928                                                  hir::Public, ty, default.is_some());
 929                     }
 930                     _ => {}
 931                 }
 932             };
 933
 934             // Convert all the associated types.
 935             for trait_item in trait_items {
 936                 match trait_item.node {
 937                     hir::TypeTraitItem(_, ref opt_ty) => {
 938                         let typ = opt_ty.as_ref().map({
 939                             |ty| ccx.icx(&trait_predicates).to_ty(&ExplicitRscope, &ty)
 940                         });
 941
 942                         convert_associated_type(ccx, TraitContainer(DefId::local(it.id)),
 943                                                 trait_item.name, trait_item.id, hir::Public,
 944                                                 typ);
 945                     }
 946                     _ => {}
 947                 }
 948             };
 949
 950             let methods = trait_items.iter().filter_map(|ti| {
 951                 let sig = match ti.node {
 952                     hir::MethodTraitItem(ref sig, _) => sig,
 953                     _ => return None,
 954                 };
 955                 Some((sig, ti.id, ti.name, hir::Inherited, ti.span))
 956             });
 957
 958             // Run convert_methods on the trait methods.
 959             convert_methods(ccx,
 960                             TraitContainer(DefId::local(it.id)),
 961                             methods,
 962                             tcx.mk_self_type(),
 963                             &trait_def.generics,
 964                             &trait_predicates);
 965
 966             // Add an entry mapping
 967             let trait_item_def_ids = Rc::new(trait_items.iter().map(|trait_item| {
 968                 let def_id = DefId::local(trait_item.id);
 969                 match trait_item.node {
 970                     hir::ConstTraitItem(..) => {
 971                         ty::ConstTraitItemId(def_id)
 972                     }
 973                     hir::MethodTraitItem(..) => {
 974                         ty::MethodTraitItemId(def_id)
 975                     }
 976                     hir::TypeTraitItem(..) => {
 977                         ty::TypeTraitItemId(def_id)
 978                     }
 979                 }
 980             }).collect());
 981             tcx.trait_item_def_ids.borrow_mut().insert(DefId::local(it.id), trait_item_def_ids);
 982
 983             // This must be done after `collect_trait_methods` so that
 984             // we have a method type stored for every method.
 985             for trait_item in trait_items {
 986                 let sig = match trait_item.node {
 987                     hir::MethodTraitItem(ref sig, _) => sig,
 988                     _ => continue
 989                 };
 990                 check_method_self_type(ccx,
 991                                        &BindingRscope::new(),
 992                                        ccx.method_ty(trait_item.id),
 993                                        tcx.mk_self_type(),
 994                                        &sig.explicit_self,
 995                                        it.id)
 996             }
 997         },
 998         hir::ItemStruct(ref struct_def, _) => {
 999             let (scheme, predicates) = convert_typed_item(ccx, it);
1000             write_ty_to_tcx(tcx, it.id, scheme.ty);
1001
1002             let variant = tcx.lookup_adt_def_master(DefId::local(it.id)).struct_variant();
1003
1004             for (f, ty_f) in struct_def.fields.iter().zip(variant.fields.iter()) {
1005                 convert_field(ccx, &scheme.generics, &predicates, f, ty_f)
1006             }
1007
1008             if let Some(ctor_id) = struct_def.ctor_id {
1009                 convert_variant_ctor(tcx, ctor_id, variant, scheme, predicates);
1010             }
1011         },
1012         hir::ItemTy(_, ref generics) => {
1013             ensure_no_ty_param_bounds(ccx, it.span, generics, "type");
1014             let (scheme, _) = convert_typed_item(ccx, it);
1015             write_ty_to_tcx(tcx, it.id, scheme.ty);
1016         },
1017         _ => {
1018             // This call populates the type cache with the converted type
1019             // of the item in passing. All we have to do here is to write
1020             // it into the node type table.
1021             let (scheme, _) = convert_typed_item(ccx, it);
1022             write_ty_to_tcx(tcx, it.id, scheme.ty);
1023         },
1024     }
1025 }
1026
1027 fn convert_variant_ctor<'a, 'tcx>(tcx: &ty::ctxt<'tcx>,
1028                                   ctor_id: ast::NodeId,
1029                                   variant: ty::VariantDef<'tcx>,
1030                                   scheme: ty::TypeScheme<'tcx>,
1031                                   predicates: ty::GenericPredicates<'tcx>) {
1032     let ctor_ty = match variant.kind() {
1033         VariantKind::Unit | VariantKind::Dict => scheme.ty,
1034         VariantKind::Tuple => {
1035             let inputs: Vec<_> =
1036                 variant.fields
1037                 .iter()
1038                 .map(|field| field.unsubst_ty())
1039                 .collect();
1040             tcx.mk_ctor_fn(DefId::local(ctor_id),
1041                            &inputs[..],
1042                            scheme.ty)
1043         }
1044     };
1045     write_ty_to_tcx(tcx, ctor_id, ctor_ty);
1046     tcx.predicates.borrow_mut().insert(DefId::local(ctor_id), predicates);
1047     tcx.register_item_type(DefId::local(ctor_id),
1048                            TypeScheme {
1049                                generics: scheme.generics,
1050                                ty: ctor_ty
1051                            });
1052 }
1053
1054 fn convert_enum_variant_types<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1055                                         def: ty::AdtDefMaster<'tcx>,
1056                                         scheme: ty::TypeScheme<'tcx>,
1057                                         predicates: ty::GenericPredicates<'tcx>,
1058                                         variants: &[P<hir::Variant>]) {
1059     let tcx = ccx.tcx;
1060     let icx = ccx.icx(&predicates);
1061
1062     // fill the field types
1063     for (variant, ty_variant) in variants.iter().zip(def.variants.iter()) {
1064         match variant.node.kind {
1065             hir::TupleVariantKind(ref args) => {
1066                 let rs = ExplicitRscope;
1067                 let input_tys: Vec<_> = args.iter().map(|va| icx.to_ty(&rs, &*va.ty)).collect();
1068                 for (field, &ty) in ty_variant.fields.iter().zip(input_tys.iter()) {
1069                     field.fulfill_ty(ty);
1070                 }
1071             }
1072
1073             hir::StructVariantKind(ref struct_def) => {
1074                 for (f, ty_f) in struct_def.fields.iter().zip(ty_variant.fields.iter()) {
1075                     convert_field(ccx, &scheme.generics, &predicates, f, ty_f)
1076                 }
1077             }
1078         };
1079
1080         // Convert the ctor, if any. This also registers the variant as
1081         // an item.
1082         convert_variant_ctor(
1083             tcx,
1084             variant.node.id,
1085             ty_variant,
1086             scheme.clone(),
1087             predicates.clone()
1088         );
1089     }
1090 }
1091
1092 fn convert_struct_variant<'tcx>(tcx: &ty::ctxt<'tcx>,
1093                                 did: DefId,
1094                                 name: ast::Name,
1095                                 disr_val: ty::Disr,
1096                                 def: &hir::StructDef) -> ty::VariantDefData<'tcx, 'tcx> {
1097     let mut seen_fields: FnvHashMap<ast::Name, Span> = FnvHashMap();
1098     let fields = def.fields.iter().map(|f| {
1099         let fid = DefId::local(f.node.id);
1100         match f.node.kind {
1101             hir::NamedField(name, vis) => {
1102                 let dup_span = seen_fields.get(&name).cloned();
1103                 if let Some(prev_span) = dup_span {
1104                     span_err!(tcx.sess, f.span, E0124,
1105                               "field `{}` is already declared",
1106                               name);
1107                     span_note!(tcx.sess, prev_span, "previously declared here");
1108                 } else {
1109                     seen_fields.insert(name, f.span);
1110                 }
1111
1112                 ty::FieldDefData::new(fid, name, vis)
1113             },
1114             hir::UnnamedField(vis) => {
1115                 ty::FieldDefData::new(fid, special_idents::unnamed_field.name, vis)
1116             }
1117         }
1118     }).collect();
1119     ty::VariantDefData {
1120         did: did,
1121         name: name,
1122         disr_val: disr_val,
1123         fields: fields
1124     }
1125 }
1126
1127 fn convert_struct_def<'tcx>(tcx: &ty::ctxt<'tcx>,
1128                             it: &hir::Item,
1129                             def: &hir::StructDef)
1130                             -> ty::AdtDefMaster<'tcx>
1131 {
1132
1133     let did = DefId::local(it.id);
1134     tcx.intern_adt_def(
1135         did,
1136         ty::AdtKind::Struct,
1137         vec![convert_struct_variant(tcx, did, it.name, 0, def)]
1138     )
1139 }
1140
1141 fn convert_enum_def<'tcx>(tcx: &ty::ctxt<'tcx>,
1142                           it: &hir::Item,
1143                           def: &hir::EnumDef)
1144                           -> ty::AdtDefMaster<'tcx>
1145 {
1146     fn evaluate_disr_expr<'tcx>(tcx: &ty::ctxt<'tcx>,
1147                                 repr_ty: Ty<'tcx>,
1148                                 e: &hir::Expr) -> Option<ty::Disr> {
1149         debug!("disr expr, checking {}", pprust::expr_to_string(e));
1150
1151         let hint = UncheckedExprHint(repr_ty);
1152         match const_eval::eval_const_expr_partial(tcx, e, hint) {
1153             Ok(ConstVal::Int(val)) => Some(val as ty::Disr),
1154             Ok(ConstVal::Uint(val)) => Some(val as ty::Disr),
1155             Ok(_) => {
1156                 let sign_desc = if repr_ty.is_signed() {
1157                     "signed"
1158                 } else {
1159                     "unsigned"
1160                 };
1161                 span_err!(tcx.sess, e.span, E0079,
1162                           "expected {} integer constant",
1163                           sign_desc);
1164                 None
1165             },
1166             Err(err) => {
1167               span_err!(tcx.sess, err.span, E0080,
1168                         "constant evaluation error: {}",
1169                         err.description());
1170                 None
1171             }
1172         }
1173     }
1174
1175     fn report_discrim_overflow(tcx: &ty::ctxt,
1176                                variant_span: Span,
1177                                variant_name: &str,
1178                                repr_type: attr::IntType,
1179                                prev_val: ty::Disr) {
1180         let computed_value = repr_type.disr_wrap_incr(Some(prev_val));
1181         let computed_value = repr_type.disr_string(computed_value);
1182         let prev_val = repr_type.disr_string(prev_val);
1183         let repr_type = repr_type.to_ty(tcx);
1184         span_err!(tcx.sess, variant_span, E0370,
1185                   "enum discriminant overflowed on value after {}: {}; \
1186                    set explicitly via {} = {} if that is desired outcome",
1187                   prev_val, repr_type, variant_name, computed_value);
1188     }
1189
1190     fn next_disr(tcx: &ty::ctxt,
1191                  v: &hir::Variant,
1192                  repr_type: attr::IntType,
1193                  prev_disr_val: Option<ty::Disr>) -> Option<ty::Disr> {
1194         if let Some(prev_disr_val) = prev_disr_val {
1195             let result = repr_type.disr_incr(prev_disr_val);
1196             if let None = result {
1197                 report_discrim_overflow(tcx, v.span, &v.node.name.as_str(),
1198                                              repr_type, prev_disr_val);
1199             }
1200             result
1201         } else {
1202             Some(ty::INITIAL_DISCRIMINANT_VALUE)
1203         }
1204     }
1205     fn convert_enum_variant<'tcx>(tcx: &ty::ctxt<'tcx>,
1206                                   v: &hir::Variant,
1207                                   disr: ty::Disr)
1208                                   -> ty::VariantDefData<'tcx, 'tcx>
1209     {
1210         let did = DefId::local(v.node.id);
1211         let name = v.node.name;
1212         match v.node.kind {
1213             hir::TupleVariantKind(ref va) => {
1214                 ty::VariantDefData {
1215                     did: did,
1216                     name: name,
1217                     disr_val: disr,
1218                     fields: va.iter().map(|&hir::VariantArg { id, .. }| {
1219                         ty::FieldDefData::new(
1220                             DefId::local(id),
1221                             special_idents::unnamed_field.name,
1222                             hir::Visibility::Public
1223                         )
1224                     }).collect()
1225                 }
1226             }
1227             hir::StructVariantKind(ref def) => {
1228                 convert_struct_variant(tcx, did, name, disr, &def)
1229             }
1230         }
1231     }
1232     let did = DefId::local(it.id);
1233     let repr_hints = tcx.lookup_repr_hints(did);
1234     let (repr_type, repr_type_ty) = tcx.enum_repr_type(repr_hints.get(0));
1235     let mut prev_disr = None;
1236     let variants = def.variants.iter().map(|v| {
1237         let disr = match v.node.disr_expr {
1238             Some(ref e) => evaluate_disr_expr(tcx, repr_type_ty, e),
1239             None => next_disr(tcx, v, repr_type, prev_disr)
1240         }.unwrap_or(repr_type.disr_wrap_incr(prev_disr));
1241
1242         let v = convert_enum_variant(tcx, v, disr);
1243         prev_disr = Some(disr);
1244         v
1245     }).collect();
1246     tcx.intern_adt_def(DefId::local(it.id), ty::AdtKind::Enum, variants)
1247 }
1248
1249 /// Ensures that the super-predicates of the trait with def-id
1250 /// trait_def_id are converted and stored. This does NOT ensure that
1251 /// the transitive super-predicates are converted; that is the job of
1252 /// the `ensure_super_predicates()` method in the `AstConv` impl
1253 /// above. Returns a list of trait def-ids that must be ensured as
1254 /// well to guarantee that the transitive superpredicates are
1255 /// converted.
1256 fn ensure_super_predicates_step(ccx: &CrateCtxt,
1257                                 trait_def_id: DefId)
1258                                 -> Vec<DefId>
1259 {
1260     let tcx = ccx.tcx;
1261
1262     debug!("ensure_super_predicates_step(trait_def_id={:?})", trait_def_id);
1263
1264     if trait_def_id.krate != LOCAL_CRATE {
1265         // If this trait comes from an external crate, then all of the
1266         // supertraits it may depend on also must come from external
1267         // crates, and hence all of them already have their
1268         // super-predicates "converted" (and available from crate
1269         // meta-data), so there is no need to transitively test them.
1270         return Vec::new();
1271     }
1272
1273     let superpredicates = tcx.super_predicates.borrow().get(&trait_def_id).cloned();
1274     let superpredicates = superpredicates.unwrap_or_else(|| {
1275         let trait_node_id = trait_def_id.node;
1276
1277         let item = match ccx.tcx.map.get(trait_node_id) {
1278             hir_map::NodeItem(item) => item,
1279             _ => ccx.tcx.sess.bug(&format!("trait_node_id {} is not an item", trait_node_id))
1280         };
1281
1282         let (generics, bounds) = match item.node {
1283             hir::ItemTrait(_, ref generics, ref supertraits, _) => (generics, supertraits),
1284             _ => tcx.sess.span_bug(item.span,
1285                                    "ensure_super_predicates_step invoked on non-trait"),
1286         };
1287
1288         // In-scope when converting the superbounds for `Trait` are
1289         // that `Self:Trait` as well as any bounds that appear on the
1290         // generic types:
1291         let trait_def = trait_def_of_item(ccx, item);
1292         let self_predicate = ty::GenericPredicates {
1293             predicates: VecPerParamSpace::new(vec![],
1294                                               vec![trait_def.trait_ref.to_predicate()],
1295                                               vec![])
1296         };
1297         let scope = &(generics, &self_predicate);
1298
1299         // Convert the bounds that follow the colon, e.g. `Bar+Zed` in `trait Foo : Bar+Zed`.
1300         let self_param_ty = tcx.mk_self_type();
1301         let superbounds1 = compute_bounds(&ccx.icx(scope),
1302                                     self_param_ty,
1303                                     bounds,
1304                                     SizedByDefault::No,
1305                                     item.span);
1306
1307         let superbounds1 = superbounds1.predicates(tcx, self_param_ty);
1308
1309         // Convert any explicit superbounds in the where clause,
1310         // e.g. `trait Foo where Self : Bar`:
1311         let superbounds2 = generics.get_type_parameter_bounds(&ccx.icx(scope), item.span, item.id);
1312
1313         // Combine the two lists to form the complete set of superbounds:
1314         let superbounds = superbounds1.into_iter().chain(superbounds2).collect();
1315         let superpredicates = ty::GenericPredicates {
1316             predicates: VecPerParamSpace::new(superbounds, vec![], vec![])
1317         };
1318         debug!("superpredicates for trait {:?} = {:?}",
1319                DefId::local(item.id),
1320                superpredicates);
1321
1322         tcx.super_predicates.borrow_mut().insert(trait_def_id, superpredicates.clone());
1323
1324         superpredicates
1325     });
1326
1327     let def_ids: Vec<_> = superpredicates.predicates
1328                                          .iter()
1329                                          .filter_map(|p| p.to_opt_poly_trait_ref())
1330                                          .map(|tr| tr.def_id())
1331                                          .collect();
1332
1333     debug!("ensure_super_predicates_step: def_ids={:?}", def_ids);
1334
1335     def_ids
1336 }
1337
1338 fn trait_def_of_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1339                                it: &hir::Item)
1340                                -> &'tcx ty::TraitDef<'tcx>
1341 {
1342     let def_id = DefId::local(it.id);
1343     let tcx = ccx.tcx;
1344
1345     if let Some(def) = tcx.trait_defs.borrow().get(&def_id) {
1346         return def.clone();
1347     }
1348
1349     let (unsafety, generics, items) = match it.node {
1350         hir::ItemTrait(unsafety, ref generics, _, ref items) => (unsafety, generics, items),
1351         _ => tcx.sess.span_bug(it.span, "trait_def_of_item invoked on non-trait"),
1352     };
1353
1354     let paren_sugar = tcx.has_attr(def_id, "rustc_paren_sugar");
1355     if paren_sugar && !ccx.tcx.sess.features.borrow().unboxed_closures {
1356         ccx.tcx.sess.span_err(
1357             it.span,
1358             "the `#[rustc_paren_sugar]` attribute is a temporary means of controlling \
1359              which traits can use parenthetical notation");
1360         fileline_help!(ccx.tcx.sess, it.span,
1361                    "add `#![feature(unboxed_closures)]` to \
1362                     the crate attributes to use it");
1363     }
1364
1365     let substs = ccx.tcx.mk_substs(mk_trait_substs(ccx, generics));
1366
1367     let ty_generics = ty_generics_for_trait(ccx, it.id, substs, generics);
1368
1369     let associated_type_names: Vec<_> = items.iter().filter_map(|trait_item| {
1370         match trait_item.node {
1371             hir::TypeTraitItem(..) => Some(trait_item.name),
1372             _ => None,
1373         }
1374     }).collect();
1375
1376     let trait_ref = ty::TraitRef {
1377         def_id: def_id,
1378         substs: substs,
1379     };
1380
1381     let trait_def = ty::TraitDef {
1382         paren_sugar: paren_sugar,
1383         unsafety: unsafety,
1384         generics: ty_generics,
1385         trait_ref: trait_ref,
1386         associated_type_names: associated_type_names,
1387         nonblanket_impls: RefCell::new(FnvHashMap()),
1388         blanket_impls: RefCell::new(vec![]),
1389         flags: Cell::new(ty::TraitFlags::NO_TRAIT_FLAGS)
1390     };
1391
1392     return tcx.intern_trait_def(trait_def);
1393
1394     fn mk_trait_substs<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1395                                  generics: &hir::Generics)
1396                                  -> Substs<'tcx>
1397     {
1398         let tcx = ccx.tcx;
1399
1400         // Creates a no-op substitution for the trait's type parameters.
1401         let regions =
1402             generics.lifetimes
1403                     .iter()
1404                     .enumerate()
1405                     .map(|(i, def)| ty::ReEarlyBound(ty::EarlyBoundRegion {
1406                         param_id: def.lifetime.id,
1407                         space: TypeSpace,
1408                         index: i as u32,
1409                         name: def.lifetime.name
1410                     }))
1411                     .collect();
1412
1413         // Start with the generics in the type parameters...
1414         let types: Vec<_> =
1415             generics.ty_params
1416                     .iter()
1417                     .enumerate()
1418                     .map(|(i, def)| tcx.mk_param(TypeSpace,
1419                                                  i as u32, def.name))
1420                     .collect();
1421
1422         // ...and also create the `Self` parameter.
1423         let self_ty = tcx.mk_self_type();
1424
1425         Substs::new_trait(types, regions, self_ty)
1426     }
1427 }
1428
1429 fn trait_defines_associated_type_named(ccx: &CrateCtxt,
1430                                        trait_node_id: ast::NodeId,
1431                                        assoc_name: ast::Name)
1432                                        -> bool
1433 {
1434     let item = match ccx.tcx.map.get(trait_node_id) {
1435         hir_map::NodeItem(item) => item,
1436         _ => ccx.tcx.sess.bug(&format!("trait_node_id {} is not an item", trait_node_id))
1437     };
1438
1439     let trait_items = match item.node {
1440         hir::ItemTrait(_, _, _, ref trait_items) => trait_items,
1441         _ => ccx.tcx.sess.bug(&format!("trait_node_id {} is not a trait", trait_node_id))
1442     };
1443
1444     trait_items.iter().any(|trait_item| {
1445         match trait_item.node {
1446             hir::TypeTraitItem(..) => trait_item.name == assoc_name,
1447             _ => false,
1448         }
1449     })
1450 }
1451
1452 fn convert_trait_predicates<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, it: &hir::Item) {
1453     let tcx = ccx.tcx;
1454     let trait_def = trait_def_of_item(ccx, it);
1455
1456     let def_id = DefId::local(it.id);
1457
1458     let (generics, items) = match it.node {
1459         hir::ItemTrait(_, ref generics, _, ref items) => (generics, items),
1460         ref s => {
1461             tcx.sess.span_bug(
1462                 it.span,
1463                 &format!("trait_def_of_item invoked on {:?}", s));
1464         }
1465     };
1466
1467     let super_predicates = ccx.tcx.lookup_super_predicates(def_id);
1468
1469     // `ty_generic_predicates` below will consider the bounds on the type
1470     // parameters (including `Self`) and the explicit where-clauses,
1471     // but to get the full set of predicates on a trait we need to add
1472     // in the supertrait bounds and anything declared on the
1473     // associated types.
1474     let mut base_predicates = super_predicates;
1475
1476     // Add in a predicate that `Self:Trait` (where `Trait` is the
1477     // current trait).  This is needed for builtin bounds.
1478     let self_predicate = trait_def.trait_ref.to_poly_trait_ref().to_predicate();
1479     base_predicates.predicates.push(SelfSpace, self_predicate);
1480
1481     // add in the explicit where-clauses
1482     let mut trait_predicates =
1483         ty_generic_predicates(ccx, TypeSpace, generics, &base_predicates);
1484
1485     let assoc_predicates = predicates_for_associated_types(ccx,
1486                                                            generics,
1487                                                            &trait_predicates,
1488                                                            trait_def.trait_ref,
1489                                                            items);
1490     trait_predicates.predicates.extend(TypeSpace, assoc_predicates.into_iter());
1491
1492     let prev_predicates = tcx.predicates.borrow_mut().insert(def_id, trait_predicates);
1493     assert!(prev_predicates.is_none());
1494
1495     return;
1496
1497     fn predicates_for_associated_types<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1498                                                  ast_generics: &hir::Generics,
1499                                                  trait_predicates: &ty::GenericPredicates<'tcx>,
1500                                                  self_trait_ref: ty::TraitRef<'tcx>,
1501                                                  trait_items: &[P<hir::TraitItem>])
1502                                                  -> Vec<ty::Predicate<'tcx>>
1503     {
1504         trait_items.iter().flat_map(|trait_item| {
1505             let bounds = match trait_item.node {
1506                 hir::TypeTraitItem(ref bounds, _) => bounds,
1507                 _ => {
1508                     return vec!().into_iter();
1509                 }
1510             };
1511
1512             let assoc_ty = ccx.tcx.mk_projection(self_trait_ref,
1513                                                  trait_item.name);
1514
1515             let bounds = compute_bounds(&ccx.icx(&(ast_generics, trait_predicates)),
1516                                         assoc_ty,
1517                                         bounds,
1518                                         SizedByDefault::Yes,
1519                                         trait_item.span);
1520
1521             bounds.predicates(ccx.tcx, assoc_ty).into_iter()
1522         }).collect()
1523     }
1524 }
1525
1526 fn type_scheme_of_def_id<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1527                                   def_id: DefId)
1528                                   -> ty::TypeScheme<'tcx>
1529 {
1530     if def_id.krate != LOCAL_CRATE {
1531         return ccx.tcx.lookup_item_type(def_id);
1532     }
1533
1534     match ccx.tcx.map.find(def_id.node) {
1535         Some(hir_map::NodeItem(item)) => {
1536             type_scheme_of_item(ccx, &*item)
1537         }
1538         Some(hir_map::NodeForeignItem(foreign_item)) => {
1539             let abi = ccx.tcx.map.get_foreign_abi(def_id.node);
1540             type_scheme_of_foreign_item(ccx, &*foreign_item, abi)
1541         }
1542         x => {
1543             ccx.tcx.sess.bug(&format!("unexpected sort of node \
1544                                             in get_item_type_scheme(): {:?}",
1545                                        x));
1546         }
1547     }
1548 }
1549
1550 fn type_scheme_of_item<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1551                                 it: &hir::Item)
1552                                 -> ty::TypeScheme<'tcx>
1553 {
1554     memoized(&ccx.tcx.tcache,
1555              DefId::local(it.id),
1556              |_| compute_type_scheme_of_item(ccx, it))
1557 }
1558
1559 fn compute_type_scheme_of_item<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1560                                         it: &hir::Item)
1561                                         -> ty::TypeScheme<'tcx>
1562 {
1563     let tcx = ccx.tcx;
1564     match it.node {
1565         hir::ItemStatic(ref t, _, _) | hir::ItemConst(ref t, _) => {
1566             let ty = ccx.icx(&()).to_ty(&ExplicitRscope, &**t);
1567             ty::TypeScheme { ty: ty, generics: ty::Generics::empty() }
1568         }
1569         hir::ItemFn(ref decl, unsafety, _, abi, ref generics, _) => {
1570             let ty_generics = ty_generics_for_fn(ccx, generics, &ty::Generics::empty());
1571             let tofd = astconv::ty_of_bare_fn(&ccx.icx(generics), unsafety, abi, &**decl);
1572             let ty = tcx.mk_fn(Some(DefId::local(it.id)), tcx.mk_bare_fn(tofd));
1573             ty::TypeScheme { ty: ty, generics: ty_generics }
1574         }
1575         hir::ItemTy(ref t, ref generics) => {
1576             let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
1577             let ty = ccx.icx(generics).to_ty(&ExplicitRscope, &**t);
1578             ty::TypeScheme { ty: ty, generics: ty_generics }
1579         }
1580         hir::ItemEnum(ref ei, ref generics) => {
1581             let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
1582             let substs = mk_item_substs(ccx, &ty_generics);
1583             let def = convert_enum_def(tcx, it, ei);
1584             let t = tcx.mk_enum(def, tcx.mk_substs(substs));
1585             ty::TypeScheme { ty: t, generics: ty_generics }
1586         }
1587         hir::ItemStruct(ref si, ref generics) => {
1588             let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
1589             let substs = mk_item_substs(ccx, &ty_generics);
1590             let def = convert_struct_def(tcx, it, si);
1591             let t = tcx.mk_struct(def, tcx.mk_substs(substs));
1592             ty::TypeScheme { ty: t, generics: ty_generics }
1593         }
1594         hir::ItemDefaultImpl(..) |
1595         hir::ItemTrait(..) |
1596         hir::ItemImpl(..) |
1597         hir::ItemMod(..) |
1598         hir::ItemForeignMod(..) |
1599         hir::ItemExternCrate(..) |
1600         hir::ItemUse(..) => {
1601             tcx.sess.span_bug(
1602                 it.span,
1603                 &format!("compute_type_scheme_of_item: unexpected item type: {:?}",
1604                          it.node));
1605         }
1606     }
1607 }
1608
1609 fn convert_typed_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1610                                 it: &hir::Item)
1611                                 -> (ty::TypeScheme<'tcx>, ty::GenericPredicates<'tcx>)
1612 {
1613     let tcx = ccx.tcx;
1614
1615     let tag = type_scheme_of_item(ccx, it);
1616     let scheme = TypeScheme { generics: tag.generics, ty: tag.ty };
1617     let predicates = match it.node {
1618         hir::ItemStatic(..) | hir::ItemConst(..) => {
1619             ty::GenericPredicates::empty()
1620         }
1621         hir::ItemFn(_, _, _, _, ref ast_generics, _) => {
1622             ty_generic_predicates_for_fn(ccx, ast_generics, &ty::GenericPredicates::empty())
1623         }
1624         hir::ItemTy(_, ref generics) => {
1625             ty_generic_predicates_for_type_or_impl(ccx, generics)
1626         }
1627         hir::ItemEnum(_, ref generics) => {
1628             ty_generic_predicates_for_type_or_impl(ccx, generics)
1629         }
1630         hir::ItemStruct(_, ref generics) => {
1631             ty_generic_predicates_for_type_or_impl(ccx, generics)
1632         }
1633         hir::ItemDefaultImpl(..) |
1634         hir::ItemTrait(..) |
1635         hir::ItemExternCrate(..) |
1636         hir::ItemUse(..) |
1637         hir::ItemImpl(..) |
1638         hir::ItemMod(..) |
1639         hir::ItemForeignMod(..) => {
1640             tcx.sess.span_bug(
1641                 it.span,
1642                 &format!("compute_type_scheme_of_item: unexpected item type: {:?}",
1643                          it.node));
1644         }
1645     };
1646
1647     let prev_predicates = tcx.predicates.borrow_mut().insert(DefId::local(it.id),
1648                                                              predicates.clone());
1649     assert!(prev_predicates.is_none());
1650
1651     // Debugging aid.
1652     if tcx.has_attr(DefId::local(it.id), "rustc_object_lifetime_default") {
1653         let object_lifetime_default_reprs: String =
1654             scheme.generics.types.iter()
1655                                  .map(|t| match t.object_lifetime_default {
1656                                      ty::ObjectLifetimeDefault::Specific(r) => r.to_string(),
1657                                      d => format!("{:?}", d),
1658                                  })
1659                                  .collect::<Vec<String>>()
1660                                  .join(",");
1661
1662         tcx.sess.span_err(it.span, &object_lifetime_default_reprs);
1663     }
1664
1665     return (scheme, predicates);
1666 }
1667
1668 fn type_scheme_of_foreign_item<'a, 'tcx>(
1669     ccx: &CrateCtxt<'a, 'tcx>,
1670     it: &hir::ForeignItem,
1671     abi: abi::Abi)
1672     -> ty::TypeScheme<'tcx>
1673 {
1674     memoized(&ccx.tcx.tcache,
1675              DefId::local(it.id),
1676              |_| compute_type_scheme_of_foreign_item(ccx, it, abi))
1677 }
1678
1679 fn compute_type_scheme_of_foreign_item<'a, 'tcx>(
1680     ccx: &CrateCtxt<'a, 'tcx>,
1681     it: &hir::ForeignItem,
1682     abi: abi::Abi)
1683     -> ty::TypeScheme<'tcx>
1684 {
1685     match it.node {
1686         hir::ForeignItemFn(ref fn_decl, ref generics) => {
1687             compute_type_scheme_of_foreign_fn_decl(ccx, fn_decl, generics, abi)
1688         }
1689         hir::ForeignItemStatic(ref t, _) => {
1690             ty::TypeScheme {
1691                 generics: ty::Generics::empty(),
1692                 ty: ast_ty_to_ty(&ccx.icx(&()), &ExplicitRscope, t)
1693             }
1694         }
1695     }
1696 }
1697
1698 fn convert_foreign_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1699                                   it: &hir::ForeignItem)
1700 {
1701     // For reasons I cannot fully articulate, I do so hate the AST
1702     // map, and I regard each time that I use it as a personal and
1703     // moral failing, but at the moment it seems like the only
1704     // convenient way to extract the ABI. - ndm
1705     let tcx = ccx.tcx;
1706     let abi = tcx.map.get_foreign_abi(it.id);
1707
1708     let scheme = type_scheme_of_foreign_item(ccx, it, abi);
1709     write_ty_to_tcx(ccx.tcx, it.id, scheme.ty);
1710
1711     let predicates = match it.node {
1712         hir::ForeignItemFn(_, ref generics) => {
1713             ty_generic_predicates_for_fn(ccx, generics, &ty::GenericPredicates::empty())
1714         }
1715         hir::ForeignItemStatic(..) => {
1716             ty::GenericPredicates::empty()
1717         }
1718     };
1719
1720     let prev_predicates = tcx.predicates.borrow_mut().insert(DefId::local(it.id), predicates);
1721     assert!(prev_predicates.is_none());
1722 }
1723
1724 fn ty_generics_for_type_or_impl<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1725                                           generics: &hir::Generics)
1726                                           -> ty::Generics<'tcx> {
1727     ty_generics(ccx, TypeSpace, generics, &ty::Generics::empty())
1728 }
1729
1730 fn ty_generic_predicates_for_type_or_impl<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1731                                                    generics: &hir::Generics)
1732                                                    -> ty::GenericPredicates<'tcx>
1733 {
1734     ty_generic_predicates(ccx, TypeSpace, generics, &ty::GenericPredicates::empty())
1735 }
1736
1737 fn ty_generics_for_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1738                                    trait_id: ast::NodeId,
1739                                    substs: &'tcx Substs<'tcx>,
1740                                    ast_generics: &hir::Generics)
1741                                    -> ty::Generics<'tcx>
1742 {
1743     debug!("ty_generics_for_trait(trait_id={:?}, substs={:?})",
1744            DefId::local(trait_id), substs);
1745
1746     let mut generics = ty_generics_for_type_or_impl(ccx, ast_generics);
1747
1748     // Add in the self type parameter.
1749     //
1750     // Something of a hack: use the node id for the trait, also as
1751     // the node id for the Self type parameter.
1752     let param_id = trait_id;
1753
1754     let parent = ccx.tcx.map.get_parent(param_id);
1755
1756     let def = ty::TypeParameterDef {
1757         space: SelfSpace,
1758         index: 0,
1759         name: special_idents::type_self.name,
1760         def_id: DefId::local(param_id),
1761         default_def_id: DefId::local(parent),
1762         default: None,
1763         object_lifetime_default: ty::ObjectLifetimeDefault::BaseDefault,
1764     };
1765
1766     ccx.tcx.ty_param_defs.borrow_mut().insert(param_id, def.clone());
1767
1768     generics.types.push(SelfSpace, def);
1769
1770     return generics;
1771 }
1772
1773 fn ty_generics_for_fn<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1774                                generics: &hir::Generics,
1775                                base_generics: &ty::Generics<'tcx>)
1776                                -> ty::Generics<'tcx>
1777 {
1778     ty_generics(ccx, FnSpace, generics, base_generics)
1779 }
1780
1781 fn ty_generic_predicates_for_fn<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1782                                          generics: &hir::Generics,
1783                                          base_predicates: &ty::GenericPredicates<'tcx>)
1784                                          -> ty::GenericPredicates<'tcx>
1785 {
1786     ty_generic_predicates(ccx, FnSpace, generics, base_predicates)
1787 }
1788
1789 // Add the Sized bound, unless the type parameter is marked as `?Sized`.
1790 fn add_unsized_bound<'tcx>(astconv: &AstConv<'tcx>,
1791                            bounds: &mut ty::BuiltinBounds,
1792                            ast_bounds: &[hir::TyParamBound],
1793                            span: Span)
1794 {
1795     let tcx = astconv.tcx();
1796
1797     // Try to find an unbound in bounds.
1798     let mut unbound = None;
1799     for ab in ast_bounds {
1800         if let &hir::TraitTyParamBound(ref ptr, hir::TraitBoundModifier::Maybe) = ab  {
1801             if unbound.is_none() {
1802                 assert!(ptr.bound_lifetimes.is_empty());
1803                 unbound = Some(ptr.trait_ref.clone());
1804             } else {
1805                 span_err!(tcx.sess, span, E0203,
1806                           "type parameter has more than one relaxed default \
1807                                                 bound, only one is supported");
1808             }
1809         }
1810     }
1811
1812     let kind_id = tcx.lang_items.require(SizedTraitLangItem);
1813     match unbound {
1814         Some(ref tpb) => {
1815             // FIXME(#8559) currently requires the unbound to be built-in.
1816             let trait_def_id = tcx.trait_ref_to_def_id(tpb);
1817             match kind_id {
1818                 Ok(kind_id) if trait_def_id != kind_id => {
1819                     tcx.sess.span_warn(span,
1820                                        "default bound relaxed for a type parameter, but \
1821                                        this does nothing because the given bound is not \
1822                                        a default. Only `?Sized` is supported");
1823                     tcx.try_add_builtin_trait(kind_id, bounds);
1824                 }
1825                 _ => {}
1826             }
1827         }
1828         _ if kind_id.is_ok() => {
1829             tcx.try_add_builtin_trait(kind_id.unwrap(), bounds);
1830         }
1831         // No lang item for Sized, so we can't add it as a bound.
1832         None => {}
1833     }
1834 }
1835
1836 /// Returns the early-bound lifetimes declared in this generics
1837 /// listing.  For anything other than fns/methods, this is just all
1838 /// the lifetimes that are declared. For fns or methods, we have to
1839 /// screen out those that do not appear in any where-clauses etc using
1840 /// `resolve_lifetime::early_bound_lifetimes`.
1841 fn early_bound_lifetimes_from_generics(space: ParamSpace,
1842                                        ast_generics: &hir::Generics)
1843                                        -> Vec<hir::LifetimeDef>
1844 {
1845     match space {
1846         SelfSpace | TypeSpace => ast_generics.lifetimes.to_vec(),
1847         FnSpace => resolve_lifetime::early_bound_lifetimes(ast_generics),
1848     }
1849 }
1850
1851 fn ty_generic_predicates<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1852                                   space: ParamSpace,
1853                                   ast_generics: &hir::Generics,
1854                                   base_predicates: &ty::GenericPredicates<'tcx>)
1855                                   -> ty::GenericPredicates<'tcx>
1856 {
1857     let tcx = ccx.tcx;
1858     let mut result = base_predicates.clone();
1859
1860     // Collect the predicates that were written inline by the user on each
1861     // type parameter (e.g., `<T:Foo>`).
1862     for (index, param) in ast_generics.ty_params.iter().enumerate() {
1863         let index = index as u32;
1864         let param_ty = ty::ParamTy::new(space, index, param.name).to_ty(ccx.tcx);
1865         let bounds = compute_bounds(&ccx.icx(&(base_predicates, ast_generics)),
1866                                     param_ty,
1867                                     &param.bounds,
1868                                     SizedByDefault::Yes,
1869                                     param.span);
1870         let predicates = bounds.predicates(ccx.tcx, param_ty);
1871         result.predicates.extend(space, predicates.into_iter());
1872     }
1873
1874     // Collect the region predicates that were declared inline as
1875     // well. In the case of parameters declared on a fn or method, we
1876     // have to be careful to only iterate over early-bound regions.
1877     let early_lifetimes = early_bound_lifetimes_from_generics(space, ast_generics);
1878     for (index, param) in early_lifetimes.iter().enumerate() {
1879         let index = index as u32;
1880         let region =
1881             ty::ReEarlyBound(ty::EarlyBoundRegion {
1882                 param_id: param.lifetime.id,
1883                 space: space,
1884                 index: index,
1885                 name: param.lifetime.name
1886             });
1887         for bound in &param.bounds {
1888             let bound_region = ast_region_to_region(ccx.tcx, bound);
1889             let outlives = ty::Binder(ty::OutlivesPredicate(region, bound_region));
1890             result.predicates.push(space, outlives.to_predicate());
1891         }
1892     }
1893
1894     // Add in the bounds that appear in the where-clause
1895     let where_clause = &ast_generics.where_clause;
1896     for predicate in &where_clause.predicates {
1897         match predicate {
1898             &hir::WherePredicate::BoundPredicate(ref bound_pred) => {
1899                 let ty = ast_ty_to_ty(&ccx.icx(&(base_predicates, ast_generics)),
1900                                       &ExplicitRscope,
1901                                       &*bound_pred.bounded_ty);
1902
1903                 for bound in bound_pred.bounds.iter() {
1904                     match bound {
1905                         &hir::TyParamBound::TraitTyParamBound(ref poly_trait_ref, _) => {
1906                             let mut projections = Vec::new();
1907
1908                             let trait_ref =
1909                                 conv_poly_trait_ref(&ccx.icx(&(base_predicates, ast_generics)),
1910                                                     ty,
1911                                                     poly_trait_ref,
1912                                                     &mut projections);
1913
1914                             result.predicates.push(space, trait_ref.to_predicate());
1915
1916                             for projection in &projections {
1917                                 result.predicates.push(space, projection.to_predicate());
1918                             }
1919                         }
1920
1921                         &hir::TyParamBound::RegionTyParamBound(ref lifetime) => {
1922                             let region = ast_region_to_region(tcx, lifetime);
1923                             let pred = ty::Binder(ty::OutlivesPredicate(ty, region));
1924                             result.predicates.push(space, ty::Predicate::TypeOutlives(pred))
1925                         }
1926                     }
1927                 }
1928             }
1929
1930             &hir::WherePredicate::RegionPredicate(ref region_pred) => {
1931                 let r1 = ast_region_to_region(tcx, &region_pred.lifetime);
1932                 for bound in &region_pred.bounds {
1933                     let r2 = ast_region_to_region(tcx, bound);
1934                     let pred = ty::Binder(ty::OutlivesPredicate(r1, r2));
1935                     result.predicates.push(space, ty::Predicate::RegionOutlives(pred))
1936                 }
1937             }
1938
1939             &hir::WherePredicate::EqPredicate(ref eq_pred) => {
1940                 // FIXME(#20041)
1941                 tcx.sess.span_bug(eq_pred.span,
1942                                     "Equality constraints are not yet \
1943                                         implemented (#20041)")
1944             }
1945         }
1946     }
1947
1948     return result;
1949 }
1950
1951 fn ty_generics<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1952                         space: ParamSpace,
1953                         ast_generics: &hir::Generics,
1954                         base_generics: &ty::Generics<'tcx>)
1955                         -> ty::Generics<'tcx>
1956 {
1957     let tcx = ccx.tcx;
1958     let mut result = base_generics.clone();
1959
1960     let early_lifetimes = early_bound_lifetimes_from_generics(space, ast_generics);
1961     for (i, l) in early_lifetimes.iter().enumerate() {
1962         let bounds = l.bounds.iter()
1963                              .map(|l| ast_region_to_region(tcx, l))
1964                              .collect();
1965         let def = ty::RegionParameterDef { name: l.lifetime.name,
1966                                            space: space,
1967                                            index: i as u32,
1968                                            def_id: DefId::local(l.lifetime.id),
1969                                            bounds: bounds };
1970         result.regions.push(space, def);
1971     }
1972
1973     assert!(result.types.is_empty_in(space));
1974
1975     // Now create the real type parameters.
1976     for i in 0..ast_generics.ty_params.len() {
1977         let def = get_or_create_type_parameter_def(ccx, ast_generics, space, i as u32);
1978         debug!("ty_generics: def for type param: {:?}, {:?}", def, space);
1979         result.types.push(space, def);
1980     }
1981
1982     result
1983 }
1984
1985 fn convert_default_type_parameter<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1986                                             path: &P<hir::Ty>,
1987                                             space: ParamSpace,
1988                                             index: u32)
1989                                             -> Ty<'tcx>
1990 {
1991     let ty = ast_ty_to_ty(&ccx.icx(&()), &ExplicitRscope, &path);
1992
1993     for leaf_ty in ty.walk() {
1994         if let ty::TyParam(p) = leaf_ty.sty {
1995             if p.space == space && p.idx >= index {
1996                 span_err!(ccx.tcx.sess, path.span, E0128,
1997                           "type parameters with a default cannot use \
1998                            forward declared identifiers");
1999
2000                 return ccx.tcx.types.err
2001             }
2002         }
2003     }
2004
2005     ty
2006 }
2007
2008 fn get_or_create_type_parameter_def<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
2009                                              ast_generics: &hir::Generics,
2010                                              space: ParamSpace,
2011                                              index: u32)
2012                                              -> ty::TypeParameterDef<'tcx>
2013 {
2014     let param = &ast_generics.ty_params[index as usize];
2015
2016     let tcx = ccx.tcx;
2017     match tcx.ty_param_defs.borrow().get(&param.id) {
2018         Some(d) => { return d.clone(); }
2019         None => { }
2020     }
2021
2022     let default = param.default.as_ref().map(
2023         |def| convert_default_type_parameter(ccx, def, space, index)
2024     );
2025
2026     let object_lifetime_default =
2027         compute_object_lifetime_default(ccx, param.id,
2028                                         &param.bounds, &ast_generics.where_clause);
2029
2030     let parent = tcx.map.get_parent(param.id);
2031
2032     let def = ty::TypeParameterDef {
2033         space: space,
2034         index: index,
2035         name: param.name,
2036         def_id: DefId::local(param.id),
2037         default_def_id: DefId::local(parent),
2038         default: default,
2039         object_lifetime_default: object_lifetime_default,
2040     };
2041
2042     tcx.ty_param_defs.borrow_mut().insert(param.id, def.clone());
2043
2044     def
2045 }
2046
2047 /// Scan the bounds and where-clauses on a parameter to extract bounds
2048 /// of the form `T:'a` so as to determine the `ObjectLifetimeDefault`.
2049 /// This runs as part of computing the minimal type scheme, so we
2050 /// intentionally avoid just asking astconv to convert all the where
2051 /// clauses into a `ty::Predicate`. This is because that could induce
2052 /// artificial cycles.
2053 fn compute_object_lifetime_default<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
2054                                             param_id: ast::NodeId,
2055                                             param_bounds: &[hir::TyParamBound],
2056                                             where_clause: &hir::WhereClause)
2057                                             -> ty::ObjectLifetimeDefault
2058 {
2059     let inline_bounds = from_bounds(ccx, param_bounds);
2060     let where_bounds = from_predicates(ccx, param_id, &where_clause.predicates);
2061     let all_bounds: HashSet<_> = inline_bounds.into_iter()
2062                                               .chain(where_bounds)
2063                                               .collect();
2064     return if all_bounds.len() > 1 {
2065         ty::ObjectLifetimeDefault::Ambiguous
2066     } else if all_bounds.len() == 0 {
2067         ty::ObjectLifetimeDefault::BaseDefault
2068     } else {
2069         ty::ObjectLifetimeDefault::Specific(
2070             all_bounds.into_iter().next().unwrap())
2071     };
2072
2073     fn from_bounds<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
2074                             bounds: &[hir::TyParamBound])
2075                             -> Vec<ty::Region>
2076     {
2077         bounds.iter()
2078               .filter_map(|bound| {
2079                   match *bound {
2080                       hir::TraitTyParamBound(..) =>
2081                           None,
2082                       hir::RegionTyParamBound(ref lifetime) =>
2083                           Some(astconv::ast_region_to_region(ccx.tcx, lifetime)),
2084                   }
2085               })
2086               .collect()
2087     }
2088
2089     fn from_predicates<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
2090                                 param_id: ast::NodeId,
2091                                 predicates: &[hir::WherePredicate])
2092                                 -> Vec<ty::Region>
2093     {
2094         predicates.iter()
2095                   .flat_map(|predicate| {
2096                       match *predicate {
2097                           hir::WherePredicate::BoundPredicate(ref data) => {
2098                               if data.bound_lifetimes.is_empty() &&
2099                                   is_param(ccx.tcx, &data.bounded_ty, param_id)
2100                               {
2101                                   from_bounds(ccx, &data.bounds).into_iter()
2102                               } else {
2103                                   Vec::new().into_iter()
2104                               }
2105                           }
2106                           hir::WherePredicate::RegionPredicate(..) |
2107                           hir::WherePredicate::EqPredicate(..) => {
2108                               Vec::new().into_iter()
2109                           }
2110                       }
2111                   })
2112                   .collect()
2113     }
2114 }
2115
2116 enum SizedByDefault { Yes, No, }
2117
2118 /// Translate the AST's notion of ty param bounds (which are an enum consisting of a newtyped Ty or
2119 /// a region) to ty's notion of ty param bounds, which can either be user-defined traits, or the
2120 /// built-in trait (formerly known as kind): Send.
2121 fn compute_bounds<'tcx>(astconv: &AstConv<'tcx>,
2122                         param_ty: ty::Ty<'tcx>,
2123                         ast_bounds: &[hir::TyParamBound],
2124                         sized_by_default: SizedByDefault,
2125                         span: Span)
2126                         -> astconv::Bounds<'tcx>
2127 {
2128     let mut bounds =
2129         conv_param_bounds(astconv,
2130                           span,
2131                           param_ty,
2132                           ast_bounds);
2133
2134     if let SizedByDefault::Yes = sized_by_default {
2135         add_unsized_bound(astconv,
2136                           &mut bounds.builtin_bounds,
2137                           ast_bounds,
2138                           span);
2139     }
2140
2141     bounds.trait_bounds.sort_by(|a,b| a.def_id().cmp(&b.def_id()));
2142
2143     bounds
2144 }
2145
2146 /// Converts a specific TyParamBound from the AST into a set of
2147 /// predicates that apply to the self-type. A vector is returned
2148 /// because this can be anywhere from 0 predicates (`T:?Sized` adds no
2149 /// predicates) to 1 (`T:Foo`) to many (`T:Bar<X=i32>` adds `T:Bar`
2150 /// and `<T as Bar>::X == i32`).
2151 fn predicates_from_bound<'tcx>(astconv: &AstConv<'tcx>,
2152                                param_ty: Ty<'tcx>,
2153                                bound: &hir::TyParamBound)
2154                                -> Vec<ty::Predicate<'tcx>>
2155 {
2156     match *bound {
2157         hir::TraitTyParamBound(ref tr, hir::TraitBoundModifier::None) => {
2158             let mut projections = Vec::new();
2159             let pred = conv_poly_trait_ref(astconv, param_ty, tr, &mut projections);
2160             projections.into_iter()
2161                        .map(|p| p.to_predicate())
2162                        .chain(Some(pred.to_predicate()))
2163                        .collect()
2164         }
2165         hir::RegionTyParamBound(ref lifetime) => {
2166             let region = ast_region_to_region(astconv.tcx(), lifetime);
2167             let pred = ty::Binder(ty::OutlivesPredicate(param_ty, region));
2168             vec![ty::Predicate::TypeOutlives(pred)]
2169         }
2170         hir::TraitTyParamBound(_, hir::TraitBoundModifier::Maybe) => {
2171             Vec::new()
2172         }
2173     }
2174 }
2175
2176 fn conv_poly_trait_ref<'tcx>(astconv: &AstConv<'tcx>,
2177                              param_ty: Ty<'tcx>,
2178                              trait_ref: &hir::PolyTraitRef,
2179                              projections: &mut Vec<ty::PolyProjectionPredicate<'tcx>>)
2180                              -> ty::PolyTraitRef<'tcx>
2181 {
2182     astconv::instantiate_poly_trait_ref(astconv,
2183                                         &ExplicitRscope,
2184                                         trait_ref,
2185                                         Some(param_ty),
2186                                         projections)
2187 }
2188
2189 fn conv_param_bounds<'a,'tcx>(astconv: &AstConv<'tcx>,
2190                               span: Span,
2191                               param_ty: ty::Ty<'tcx>,
2192                               ast_bounds: &[hir::TyParamBound])
2193                               -> astconv::Bounds<'tcx>
2194 {
2195     let tcx = astconv.tcx();
2196     let astconv::PartitionedBounds {
2197         builtin_bounds,
2198         trait_bounds,
2199         region_bounds
2200     } = astconv::partition_bounds(tcx, span, &ast_bounds);
2201
2202     let mut projection_bounds = Vec::new();
2203
2204     let trait_bounds: Vec<ty::PolyTraitRef> =
2205         trait_bounds.iter()
2206                     .map(|bound| conv_poly_trait_ref(astconv,
2207                                                      param_ty,
2208                                                      *bound,
2209                                                      &mut projection_bounds))
2210                     .collect();
2211
2212     let region_bounds: Vec<ty::Region> =
2213         region_bounds.into_iter()
2214                      .map(|r| ast_region_to_region(tcx, r))
2215                      .collect();
2216
2217     astconv::Bounds {
2218         region_bounds: region_bounds,
2219         builtin_bounds: builtin_bounds,
2220         trait_bounds: trait_bounds,
2221         projection_bounds: projection_bounds,
2222     }
2223 }
2224
2225 fn compute_type_scheme_of_foreign_fn_decl<'a, 'tcx>(
2226     ccx: &CrateCtxt<'a, 'tcx>,
2227     decl: &hir::FnDecl,
2228     ast_generics: &hir::Generics,
2229     abi: abi::Abi)
2230     -> ty::TypeScheme<'tcx>
2231 {
2232     for i in &decl.inputs {
2233         match (*i).pat.node {
2234             hir::PatIdent(_, _, _) => (),
2235             hir::PatWild(hir::PatWildSingle) => (),
2236             _ => {
2237                 span_err!(ccx.tcx.sess, (*i).pat.span, E0130,
2238                           "patterns aren't allowed in foreign function declarations");
2239             }
2240         }
2241     }
2242
2243     let ty_generics = ty_generics_for_fn(ccx, ast_generics, &ty::Generics::empty());
2244
2245     let rb = BindingRscope::new();
2246     let input_tys = decl.inputs
2247                         .iter()
2248                         .map(|a| ty_of_arg(&ccx.icx(ast_generics), &rb, a, None))
2249                         .collect();
2250
2251     let output = match decl.output {
2252         hir::Return(ref ty) =>
2253             ty::FnConverging(ast_ty_to_ty(&ccx.icx(ast_generics), &rb, &**ty)),
2254         hir::DefaultReturn(..) =>
2255             ty::FnConverging(ccx.tcx.mk_nil()),
2256         hir::NoReturn(..) =>
2257             ty::FnDiverging
2258     };
2259
2260     let t_fn = ccx.tcx.mk_fn(None,
2261         ccx.tcx.mk_bare_fn(ty::BareFnTy {
2262             abi: abi,
2263             unsafety: hir::Unsafety::Unsafe,
2264             sig: ty::Binder(ty::FnSig {inputs: input_tys,
2265                                        output: output,
2266                                        variadic: decl.variadic}),
2267         }));
2268
2269     ty::TypeScheme {
2270         generics: ty_generics,
2271         ty: t_fn
2272     }
2273 }
2274
2275 fn mk_item_substs<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
2276                             ty_generics: &ty::Generics<'tcx>)
2277                             -> Substs<'tcx>
2278 {
2279     let types =
2280         ty_generics.types.map(
2281             |def| ccx.tcx.mk_param_from_def(def));
2282
2283     let regions =
2284         ty_generics.regions.map(
2285             |def| def.to_early_bound_region());
2286
2287     Substs::new(types, regions)
2288 }
2289
2290 /// Verifies that the explicit self type of a method matches the impl
2291 /// or trait. This is a bit weird but basically because right now we
2292 /// don't handle the general case, but instead map it to one of
2293 /// several pre-defined options using various heuristics, this method
2294 /// comes back to check after the fact that explicit type the user
2295 /// wrote actually matches what the pre-defined option said.
2296 fn check_method_self_type<'a, 'tcx, RS:RegionScope>(
2297     ccx: &CrateCtxt<'a, 'tcx>,
2298     rs: &RS,
2299     method_type: Rc<ty::Method<'tcx>>,
2300     required_type: Ty<'tcx>,
2301     explicit_self: &hir::ExplicitSelf,
2302     body_id: ast::NodeId)
2303 {
2304     let tcx = ccx.tcx;
2305     if let hir::SelfExplicit(ref ast_type, _) = explicit_self.node {
2306         let typ = ccx.icx(&method_type.predicates).to_ty(rs, &**ast_type);
2307         let base_type = match typ.sty {
2308             ty::TyRef(_, tm) => tm.ty,
2309             ty::TyBox(typ) => typ,
2310             _ => typ,
2311         };
2312
2313         let body_scope = tcx.region_maps.item_extent(body_id);
2314
2315         // "Required type" comes from the trait definition. It may
2316         // contain late-bound regions from the method, but not the
2317         // trait (since traits only have early-bound region
2318         // parameters).
2319         assert!(!base_type.has_regions_escaping_depth(1));
2320         let required_type_free =
2321             liberate_early_bound_regions(
2322                 tcx, body_scope,
2323                 &tcx.liberate_late_bound_regions(body_scope, &ty::Binder(required_type)));
2324
2325         // The "base type" comes from the impl. It too may have late-bound
2326         // regions from the method.
2327         assert!(!base_type.has_regions_escaping_depth(1));
2328         let base_type_free =
2329             liberate_early_bound_regions(
2330                 tcx, body_scope,
2331                 &tcx.liberate_late_bound_regions(body_scope, &ty::Binder(base_type)));
2332
2333         debug!("required_type={:?} required_type_free={:?} \
2334                 base_type={:?} base_type_free={:?}",
2335                required_type,
2336                required_type_free,
2337                base_type,
2338                base_type_free);
2339
2340         let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None, false);
2341         drop(::require_same_types(tcx,
2342                                   Some(&infcx),
2343                                   false,
2344                                   explicit_self.span,
2345                                   base_type_free,
2346                                   required_type_free,
2347                                   || {
2348                 format!("mismatched self type: expected `{}`",
2349                          required_type)
2350         }));
2351
2352         // We could conceviably add more free-region relations here,
2353         // but since this code is just concerned with checking that
2354         // the `&Self` types etc match up, it's not really necessary.
2355         // It would just allow people to be more approximate in some
2356         // cases. In any case, we can do it later as we feel the need;
2357         // I'd like this function to go away eventually.
2358         let free_regions = FreeRegionMap::new();
2359
2360         infcx.resolve_regions_and_report_errors(&free_regions, body_id);
2361     }
2362
2363     fn liberate_early_bound_regions<'tcx,T>(
2364         tcx: &ty::ctxt<'tcx>,
2365         scope: region::CodeExtent,
2366         value: &T)
2367         -> T
2368         where T : TypeFoldable<'tcx>
2369     {
2370         /*!
2371          * Convert early-bound regions into free regions; normally this is done by
2372          * applying the `free_substs` from the `ParameterEnvironment`, but this particular
2373          * method-self-type check is kind of hacky and done very early in the process,
2374          * before we really have a `ParameterEnvironment` to check.
2375          */
2376
2377         tcx.fold_regions(value, &mut false, |region, _| {
2378             match region {
2379                 ty::ReEarlyBound(data) => {
2380                     let def_id = DefId::local(data.param_id);
2381                     ty::ReFree(ty::FreeRegion { scope: scope,
2382                                                 bound_region: ty::BrNamed(def_id, data.name) })
2383                 }
2384                 _ => region
2385             }
2386         })
2387     }
2388 }
2389
2390 /// Checks that all the type parameters on an impl
2391 fn enforce_impl_params_are_constrained<'tcx>(tcx: &ty::ctxt<'tcx>,
2392                                              ast_generics: &hir::Generics,
2393                                              impl_def_id: DefId,
2394                                              impl_items: &[P<hir::ImplItem>])
2395 {
2396     let impl_scheme = tcx.lookup_item_type(impl_def_id);
2397     let impl_predicates = tcx.lookup_predicates(impl_def_id);
2398     let impl_trait_ref = tcx.impl_trait_ref(impl_def_id);
2399
2400     // The trait reference is an input, so find all type parameters
2401     // reachable from there, to start (if this is an inherent impl,
2402     // then just examine the self type).
2403     let mut input_parameters: HashSet<_> =
2404         ctp::parameters_for_type(impl_scheme.ty).into_iter().collect();
2405     if let Some(ref trait_ref) = impl_trait_ref {
2406         input_parameters.extend(ctp::parameters_for_trait_ref(trait_ref));
2407     }
2408
2409     ctp::identify_constrained_type_params(tcx,
2410                                           impl_predicates.predicates.as_slice(),
2411                                           impl_trait_ref,
2412                                           &mut input_parameters);
2413
2414     for (index, ty_param) in ast_generics.ty_params.iter().enumerate() {
2415         let param_ty = ty::ParamTy { space: TypeSpace,
2416                                      idx: index as u32,
2417                                      name: ty_param.name };
2418         if !input_parameters.contains(&ctp::Parameter::Type(param_ty)) {
2419             report_unused_parameter(tcx, ty_param.span, "type", &param_ty.to_string());
2420         }
2421     }
2422
2423     // Every lifetime used in an associated type must be constrained.
2424
2425     let lifetimes_in_associated_types: HashSet<_> =
2426         impl_items.iter()
2427                   .map(|item| tcx.impl_or_trait_item(DefId::local(item.id)))
2428                   .filter_map(|item| match item {
2429                       ty::TypeTraitItem(ref assoc_ty) => assoc_ty.ty,
2430                       ty::ConstTraitItem(..) | ty::MethodTraitItem(..) => None
2431                   })
2432                   .flat_map(|ty| ctp::parameters_for_type(ty))
2433                   .filter_map(|p| match p {
2434                       ctp::Parameter::Type(_) => None,
2435                       ctp::Parameter::Region(r) => Some(r),
2436                   })
2437                   .collect();
2438
2439     for (index, lifetime_def) in ast_generics.lifetimes.iter().enumerate() {
2440         let region = ty::EarlyBoundRegion { param_id: lifetime_def.lifetime.id,
2441                                             space: TypeSpace,
2442                                             index: index as u32,
2443                                             name: lifetime_def.lifetime.name };
2444         if
2445             lifetimes_in_associated_types.contains(&region) && // (*)
2446             !input_parameters.contains(&ctp::Parameter::Region(region))
2447         {
2448             report_unused_parameter(tcx, lifetime_def.lifetime.span,
2449                                     "lifetime", &region.name.to_string());
2450         }
2451     }
2452
2453     // (*) This is a horrible concession to reality. I think it'd be
2454     // better to just ban unconstrianed lifetimes outright, but in
2455     // practice people do non-hygenic macros like:
2456     //
2457     // ```
2458     // macro_rules! __impl_slice_eq1 {
2459     //     ($Lhs: ty, $Rhs: ty, $Bound: ident) => {
2460     //         impl<'a, 'b, A: $Bound, B> PartialEq<$Rhs> for $Lhs where A: PartialEq<B> {
2461     //            ....
2462     //         }
2463     //     }
2464     // }
2465     // ```
2466     //
2467     // In a concession to backwards compatbility, we continue to
2468     // permit those, so long as the lifetimes aren't used in
2469     // associated types. I believe this is sound, because lifetimes
2470     // used elsewhere are not projected back out.
2471 }
2472
2473 fn report_unused_parameter(tcx: &ty::ctxt,
2474                            span: Span,
2475                            kind: &str,
2476                            name: &str)
2477 {
2478     span_err!(tcx.sess, span, E0207,
2479               "the {} parameter `{}` is not constrained by the \
2480                impl trait, self type, or predicates",
2481               kind, name);
2482 }