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