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