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