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