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