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