src/librustc_typeck/collect.rs

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