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             if let &Some(ref ast_trait_ref) = opt_trait_ref {
 844                 tcx.impl_trait_refs.borrow_mut().insert(
 845                     local_def(it.id),
 846                     Some(astconv::instantiate_mono_trait_ref(&ccx.icx(&ty_predicates),
 847                                                              &ExplicitRscope,
 848                                                              ast_trait_ref,
 849                                                              Some(selfty)))
 850                         );
 851             } else {
 852                 tcx.impl_trait_refs.borrow_mut().insert(local_def(it.id), None);
 853             }
 854
 855
 856             // If there is a trait reference, treat the methods as always public.
 857             // This is to work around some incorrect behavior in privacy checking:
 858             // when the method belongs to a trait, it should acquire the privacy
 859             // from the trait, not the impl. Forcing the visibility to be public
 860             // makes things sorta work.
 861             let parent_visibility = if opt_trait_ref.is_some() {
 862                 ast::Public
 863             } else {
 864                 it.vis
 865             };
 866
 867             // Convert all the associated consts.
 868             // Also, check if there are any duplicate associated items
 869             let mut seen_type_items = FnvHashSet();
 870             let mut seen_value_items = FnvHashSet();
 871
 872             for impl_item in impl_items {
 873                 let seen_items = match impl_item.node {
 874                     ast::TypeImplItem(_) => &mut seen_type_items,
 875                     _                    => &mut seen_value_items,
 876                 };
 877                 if !seen_items.insert(impl_item.ident.name) {
 878                     let desc = match impl_item.node {
 879                         ast::ConstImplItem(_, _) => "associated constant",
 880                         ast::TypeImplItem(_) => "associated type",
 881                         ast::MethodImplItem(ref sig, _) =>
 882                             match sig.explicit_self.node {
 883                                 ast::SelfStatic => "associated function",
 884                                 _ => "method",
 885                             },
 886                         _ => "associated item",
 887                     };
 888
 889                     span_err!(tcx.sess, impl_item.span, E0201, "duplicate {}", desc);
 890                 }
 891
 892                 if let ast::ConstImplItem(ref ty, ref expr) = impl_item.node {
 893                     let ty = ccx.icx(&ty_predicates)
 894                                 .to_ty(&ExplicitRscope, &*ty);
 895                     tcx.register_item_type(local_def(impl_item.id),
 896                                            TypeScheme {
 897                                                generics: ty_generics.clone(),
 898                                                ty: ty,
 899                                            });
 900                     convert_associated_const(ccx, ImplContainer(local_def(it.id)),
 901                                              impl_item.ident, impl_item.id,
 902                                              impl_item.vis.inherit_from(parent_visibility),
 903                                              ty, Some(&*expr));
 904                 }
 905             }
 906
 907             // Convert all the associated types.
 908             for impl_item in impl_items {
 909                 if let ast::TypeImplItem(ref ty) = impl_item.node {
 910                     if opt_trait_ref.is_none() {
 911                         span_err!(tcx.sess, impl_item.span, E0202,
 912                                   "associated types are not allowed in inherent impls");
 913                     }
 914
 915                     let typ = ccx.icx(&ty_predicates).to_ty(&ExplicitRscope, ty);
 916
 917                     convert_associated_type(ccx, ImplContainer(local_def(it.id)),
 918                                             impl_item.ident, impl_item.id, impl_item.vis,
 919                                             Some(typ));
 920                 }
 921             }
 922
 923             let methods = impl_items.iter().filter_map(|ii| {
 924                 if let ast::MethodImplItem(ref sig, _) = ii.node {
 925                     // if the method specifies a visibility, use that, otherwise
 926                     // inherit the visibility from the impl (so `foo` in `pub impl
 927                     // { fn foo(); }` is public, but private in `impl { fn
 928                     // foo(); }`).
 929                     let method_vis = ii.vis.inherit_from(parent_visibility);
 930                     Some((sig, ii.id, ii.ident, method_vis, ii.span))
 931                 } else {
 932                     None
 933                 }
 934             });
 935             convert_methods(ccx,
 936                             ImplContainer(local_def(it.id)),
 937                             methods,
 938                             selfty,
 939                             &ty_generics,
 940                             &ty_predicates);
 941
 942             for impl_item in impl_items {
 943                 if let ast::MethodImplItem(ref sig, ref body) = impl_item.node {
 944                     let body_id = body.id;
 945                     check_method_self_type(ccx,
 946                                            &BindingRscope::new(),
 947                                            ccx.method_ty(impl_item.id),
 948                                            selfty,
 949                                            &sig.explicit_self,
 950                                            body_id);
 951                 }
 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 parent = ccx.tcx.map.get_parent(param_id);
1651
1652     let def = ty::TypeParameterDef {
1653         space: SelfSpace,
1654         index: 0,
1655         name: special_idents::type_self.name,
1656         def_id: local_def(param_id),
1657         default_def_id: local_def(parent),
1658         default: None,
1659         object_lifetime_default: ty::ObjectLifetimeDefault::BaseDefault,
1660     };
1661
1662     ccx.tcx.ty_param_defs.borrow_mut().insert(param_id, def.clone());
1663
1664     generics.types.push(SelfSpace, def);
1665
1666     return generics;
1667 }
1668
1669 fn ty_generics_for_fn<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1670                                generics: &ast::Generics,
1671                                base_generics: &ty::Generics<'tcx>)
1672                                -> ty::Generics<'tcx>
1673 {
1674     ty_generics(ccx, FnSpace, generics, base_generics)
1675 }
1676
1677 fn ty_generic_predicates_for_fn<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1678                                          generics: &ast::Generics,
1679                                          base_predicates: &ty::GenericPredicates<'tcx>)
1680                                          -> ty::GenericPredicates<'tcx>
1681 {
1682     ty_generic_predicates(ccx, FnSpace, generics, base_predicates)
1683 }
1684
1685 // Add the Sized bound, unless the type parameter is marked as `?Sized`.
1686 fn add_unsized_bound<'tcx>(astconv: &AstConv<'tcx>,
1687                            bounds: &mut ty::BuiltinBounds,
1688                            ast_bounds: &[ast::TyParamBound],
1689                            span: Span)
1690 {
1691     let tcx = astconv.tcx();
1692
1693     // Try to find an unbound in bounds.
1694     let mut unbound = None;
1695     for ab in ast_bounds {
1696         if let &ast::TraitTyParamBound(ref ptr, ast::TraitBoundModifier::Maybe) = ab  {
1697             if unbound.is_none() {
1698                 assert!(ptr.bound_lifetimes.is_empty());
1699                 unbound = Some(ptr.trait_ref.clone());
1700             } else {
1701                 span_err!(tcx.sess, span, E0203,
1702                           "type parameter has more than one relaxed default \
1703                                                 bound, only one is supported");
1704             }
1705         }
1706     }
1707
1708     let kind_id = tcx.lang_items.require(SizedTraitLangItem);
1709     match unbound {
1710         Some(ref tpb) => {
1711             // FIXME(#8559) currently requires the unbound to be built-in.
1712             let trait_def_id = tcx.trait_ref_to_def_id(tpb);
1713             match kind_id {
1714                 Ok(kind_id) if trait_def_id != kind_id => {
1715                     tcx.sess.span_warn(span,
1716                                        "default bound relaxed for a type parameter, but \
1717                                        this does nothing because the given bound is not \
1718                                        a default. Only `?Sized` is supported");
1719                     tcx.try_add_builtin_trait(kind_id, bounds);
1720                 }
1721                 _ => {}
1722             }
1723         }
1724         _ if kind_id.is_ok() => {
1725             tcx.try_add_builtin_trait(kind_id.unwrap(), bounds);
1726         }
1727         // No lang item for Sized, so we can't add it as a bound.
1728         None => {}
1729     }
1730 }
1731
1732 /// Returns the early-bound lifetimes declared in this generics
1733 /// listing.  For anything other than fns/methods, this is just all
1734 /// the lifetimes that are declared. For fns or methods, we have to
1735 /// screen out those that do not appear in any where-clauses etc using
1736 /// `resolve_lifetime::early_bound_lifetimes`.
1737 fn early_bound_lifetimes_from_generics(space: ParamSpace,
1738                                        ast_generics: &ast::Generics)
1739                                        -> Vec<ast::LifetimeDef>
1740 {
1741     match space {
1742         SelfSpace | TypeSpace => ast_generics.lifetimes.to_vec(),
1743         FnSpace => resolve_lifetime::early_bound_lifetimes(ast_generics),
1744     }
1745 }
1746
1747 fn ty_generic_predicates<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1748                                   space: ParamSpace,
1749                                   ast_generics: &ast::Generics,
1750                                   base_predicates: &ty::GenericPredicates<'tcx>)
1751                                   -> ty::GenericPredicates<'tcx>
1752 {
1753     let tcx = ccx.tcx;
1754     let mut result = base_predicates.clone();
1755
1756     // Collect the predicates that were written inline by the user on each
1757     // type parameter (e.g., `<T:Foo>`).
1758     for (index, param) in ast_generics.ty_params.iter().enumerate() {
1759         let index = index as u32;
1760         let param_ty = ty::ParamTy::new(space, index, param.ident.name).to_ty(ccx.tcx);
1761         let bounds = compute_bounds(&ccx.icx(&(base_predicates, ast_generics)),
1762                                     param_ty,
1763                                     &param.bounds,
1764                                     SizedByDefault::Yes,
1765                                     param.span);
1766         let predicates = bounds.predicates(ccx.tcx, param_ty);
1767         result.predicates.extend(space, predicates.into_iter());
1768     }
1769
1770     // Collect the region predicates that were declared inline as
1771     // well. In the case of parameters declared on a fn or method, we
1772     // have to be careful to only iterate over early-bound regions.
1773     let early_lifetimes = early_bound_lifetimes_from_generics(space, ast_generics);
1774     for (index, param) in early_lifetimes.iter().enumerate() {
1775         let index = index as u32;
1776         let region =
1777             ty::ReEarlyBound(ty::EarlyBoundRegion {
1778                 param_id: param.lifetime.id,
1779                 space: space,
1780                 index: index,
1781                 name: param.lifetime.name
1782             });
1783         for bound in &param.bounds {
1784             let bound_region = ast_region_to_region(ccx.tcx, bound);
1785             let outlives = ty::Binder(ty::OutlivesPredicate(region, bound_region));
1786             result.predicates.push(space, outlives.to_predicate());
1787         }
1788     }
1789
1790     // Add in the bounds that appear in the where-clause
1791     let where_clause = &ast_generics.where_clause;
1792     for predicate in &where_clause.predicates {
1793         match predicate {
1794             &ast::WherePredicate::BoundPredicate(ref bound_pred) => {
1795                 let ty = ast_ty_to_ty(&ccx.icx(&(base_predicates, ast_generics)),
1796                                       &ExplicitRscope,
1797                                       &*bound_pred.bounded_ty);
1798
1799                 for bound in bound_pred.bounds.iter() {
1800                     match bound {
1801                         &ast::TyParamBound::TraitTyParamBound(ref poly_trait_ref, _) => {
1802                             let mut projections = Vec::new();
1803
1804                             let trait_ref =
1805                                 conv_poly_trait_ref(&ccx.icx(&(base_predicates, ast_generics)),
1806                                                     ty,
1807                                                     poly_trait_ref,
1808                                                     &mut projections);
1809
1810                             result.predicates.push(space, trait_ref.to_predicate());
1811
1812                             for projection in &projections {
1813                                 result.predicates.push(space, projection.to_predicate());
1814                             }
1815                         }
1816
1817                         &ast::TyParamBound::RegionTyParamBound(ref lifetime) => {
1818                             let region = ast_region_to_region(tcx, lifetime);
1819                             let pred = ty::Binder(ty::OutlivesPredicate(ty, region));
1820                             result.predicates.push(space, ty::Predicate::TypeOutlives(pred))
1821                         }
1822                     }
1823                 }
1824             }
1825
1826             &ast::WherePredicate::RegionPredicate(ref region_pred) => {
1827                 let r1 = ast_region_to_region(tcx, &region_pred.lifetime);
1828                 for bound in &region_pred.bounds {
1829                     let r2 = ast_region_to_region(tcx, bound);
1830                     let pred = ty::Binder(ty::OutlivesPredicate(r1, r2));
1831                     result.predicates.push(space, ty::Predicate::RegionOutlives(pred))
1832                 }
1833             }
1834
1835             &ast::WherePredicate::EqPredicate(ref eq_pred) => {
1836                 // FIXME(#20041)
1837                 tcx.sess.span_bug(eq_pred.span,
1838                                     "Equality constraints are not yet \
1839                                         implemented (#20041)")
1840             }
1841         }
1842     }
1843
1844     return result;
1845 }
1846
1847 fn ty_generics<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1848                         space: ParamSpace,
1849                         ast_generics: &ast::Generics,
1850                         base_generics: &ty::Generics<'tcx>)
1851                         -> ty::Generics<'tcx>
1852 {
1853     let tcx = ccx.tcx;
1854     let mut result = base_generics.clone();
1855
1856     let early_lifetimes = early_bound_lifetimes_from_generics(space, ast_generics);
1857     for (i, l) in early_lifetimes.iter().enumerate() {
1858         let bounds = l.bounds.iter()
1859                              .map(|l| ast_region_to_region(tcx, l))
1860                              .collect();
1861         let def = ty::RegionParameterDef { name: l.lifetime.name,
1862                                            space: space,
1863                                            index: i as u32,
1864                                            def_id: local_def(l.lifetime.id),
1865                                            bounds: bounds };
1866         result.regions.push(space, def);
1867     }
1868
1869     assert!(result.types.is_empty_in(space));
1870
1871     // Now create the real type parameters.
1872     for i in 0..ast_generics.ty_params.len() {
1873         let def = get_or_create_type_parameter_def(ccx, ast_generics, space, i as u32);
1874         debug!("ty_generics: def for type param: {:?}, {:?}", def, space);
1875         result.types.push(space, def);
1876     }
1877
1878     result
1879 }
1880
1881 fn convert_default_type_parameter<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1882                                             path: &P<ast::Ty>,
1883                                             space: ParamSpace,
1884                                             index: u32)
1885                                             -> Ty<'tcx>
1886 {
1887     let ty = ast_ty_to_ty(&ccx.icx(&()), &ExplicitRscope, &path);
1888
1889     for leaf_ty in ty.walk() {
1890         if let ty::TyParam(p) = leaf_ty.sty {
1891             if p.space == space && p.idx >= index {
1892                 span_err!(ccx.tcx.sess, path.span, E0128,
1893                           "type parameters with a default cannot use \
1894                            forward declared identifiers");
1895
1896                 return ccx.tcx.types.err
1897             }
1898         }
1899     }
1900
1901     ty
1902 }
1903
1904 fn get_or_create_type_parameter_def<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1905                                              ast_generics: &ast::Generics,
1906                                              space: ParamSpace,
1907                                              index: u32)
1908                                              -> ty::TypeParameterDef<'tcx>
1909 {
1910     let param = &ast_generics.ty_params[index as usize];
1911
1912     let tcx = ccx.tcx;
1913     match tcx.ty_param_defs.borrow().get(&param.id) {
1914         Some(d) => { return d.clone(); }
1915         None => { }
1916     }
1917
1918     let default = param.default.as_ref().map(
1919         |def| convert_default_type_parameter(ccx, def, space, index)
1920     );
1921
1922     let object_lifetime_default =
1923         compute_object_lifetime_default(ccx, param.id,
1924                                         &param.bounds, &ast_generics.where_clause);
1925
1926     let parent = tcx.map.get_parent(param.id);
1927
1928     let def = ty::TypeParameterDef {
1929         space: space,
1930         index: index,
1931         name: param.ident.name,
1932         def_id: local_def(param.id),
1933         default_def_id: local_def(parent),
1934         default: default,
1935         object_lifetime_default: object_lifetime_default,
1936     };
1937
1938     tcx.ty_param_defs.borrow_mut().insert(param.id, def.clone());
1939
1940     def
1941 }
1942
1943 /// Scan the bounds and where-clauses on a parameter to extract bounds
1944 /// of the form `T:'a` so as to determine the `ObjectLifetimeDefault`.
1945 /// This runs as part of computing the minimal type scheme, so we
1946 /// intentionally avoid just asking astconv to convert all the where
1947 /// clauses into a `ty::Predicate`. This is because that could induce
1948 /// artificial cycles.
1949 fn compute_object_lifetime_default<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1950                                             param_id: ast::NodeId,
1951                                             param_bounds: &[ast::TyParamBound],
1952                                             where_clause: &ast::WhereClause)
1953                                             -> ty::ObjectLifetimeDefault
1954 {
1955     let inline_bounds = from_bounds(ccx, param_bounds);
1956     let where_bounds = from_predicates(ccx, param_id, &where_clause.predicates);
1957     let all_bounds: HashSet<_> = inline_bounds.into_iter()
1958                                               .chain(where_bounds)
1959                                               .collect();
1960     return if all_bounds.len() > 1 {
1961         ty::ObjectLifetimeDefault::Ambiguous
1962     } else if all_bounds.len() == 0 {
1963         ty::ObjectLifetimeDefault::BaseDefault
1964     } else {
1965         ty::ObjectLifetimeDefault::Specific(
1966             all_bounds.into_iter().next().unwrap())
1967     };
1968
1969     fn from_bounds<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1970                             bounds: &[ast::TyParamBound])
1971                             -> Vec<ty::Region>
1972     {
1973         bounds.iter()
1974               .filter_map(|bound| {
1975                   match *bound {
1976                       ast::TraitTyParamBound(..) =>
1977                           None,
1978                       ast::RegionTyParamBound(ref lifetime) =>
1979                           Some(astconv::ast_region_to_region(ccx.tcx, lifetime)),
1980                   }
1981               })
1982               .collect()
1983     }
1984
1985     fn from_predicates<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1986                                 param_id: ast::NodeId,
1987                                 predicates: &[ast::WherePredicate])
1988                                 -> Vec<ty::Region>
1989     {
1990         predicates.iter()
1991                   .flat_map(|predicate| {
1992                       match *predicate {
1993                           ast::WherePredicate::BoundPredicate(ref data) => {
1994                               if data.bound_lifetimes.is_empty() &&
1995                                   is_param(ccx.tcx, &data.bounded_ty, param_id)
1996                               {
1997                                   from_bounds(ccx, &data.bounds).into_iter()
1998                               } else {
1999                                   Vec::new().into_iter()
2000                               }
2001                           }
2002                           ast::WherePredicate::RegionPredicate(..) |
2003                           ast::WherePredicate::EqPredicate(..) => {
2004                               Vec::new().into_iter()
2005                           }
2006                       }
2007                   })
2008                   .collect()
2009     }
2010 }
2011
2012 enum SizedByDefault { Yes, No, }
2013
2014 /// Translate the AST's notion of ty param bounds (which are an enum consisting of a newtyped Ty or
2015 /// a region) to ty's notion of ty param bounds, which can either be user-defined traits, or the
2016 /// built-in trait (formerly known as kind): Send.
2017 fn compute_bounds<'tcx>(astconv: &AstConv<'tcx>,
2018                         param_ty: ty::Ty<'tcx>,
2019                         ast_bounds: &[ast::TyParamBound],
2020                         sized_by_default: SizedByDefault,
2021                         span: Span)
2022                         -> astconv::Bounds<'tcx>
2023 {
2024     let mut bounds =
2025         conv_param_bounds(astconv,
2026                           span,
2027                           param_ty,
2028                           ast_bounds);
2029
2030     if let SizedByDefault::Yes = sized_by_default {
2031         add_unsized_bound(astconv,
2032                           &mut bounds.builtin_bounds,
2033                           ast_bounds,
2034                           span);
2035     }
2036
2037     bounds.trait_bounds.sort_by(|a,b| a.def_id().cmp(&b.def_id()));
2038
2039     bounds
2040 }
2041
2042 /// Converts a specific TyParamBound from the AST into a set of
2043 /// predicates that apply to the self-type. A vector is returned
2044 /// because this can be anywhere from 0 predicates (`T:?Sized` adds no
2045 /// predicates) to 1 (`T:Foo`) to many (`T:Bar<X=i32>` adds `T:Bar`
2046 /// and `<T as Bar>::X == i32`).
2047 fn predicates_from_bound<'tcx>(astconv: &AstConv<'tcx>,
2048                                param_ty: Ty<'tcx>,
2049                                bound: &ast::TyParamBound)
2050                                -> Vec<ty::Predicate<'tcx>>
2051 {
2052     match *bound {
2053         ast::TraitTyParamBound(ref tr, ast::TraitBoundModifier::None) => {
2054             let mut projections = Vec::new();
2055             let pred = conv_poly_trait_ref(astconv, param_ty, tr, &mut projections);
2056             projections.into_iter()
2057                        .map(|p| p.to_predicate())
2058                        .chain(Some(pred.to_predicate()))
2059                        .collect()
2060         }
2061         ast::RegionTyParamBound(ref lifetime) => {
2062             let region = ast_region_to_region(astconv.tcx(), lifetime);
2063             let pred = ty::Binder(ty::OutlivesPredicate(param_ty, region));
2064             vec![ty::Predicate::TypeOutlives(pred)]
2065         }
2066         ast::TraitTyParamBound(_, ast::TraitBoundModifier::Maybe) => {
2067             Vec::new()
2068         }
2069     }
2070 }
2071
2072 fn conv_poly_trait_ref<'tcx>(astconv: &AstConv<'tcx>,
2073                              param_ty: Ty<'tcx>,
2074                              trait_ref: &ast::PolyTraitRef,
2075                              projections: &mut Vec<ty::PolyProjectionPredicate<'tcx>>)
2076                              -> ty::PolyTraitRef<'tcx>
2077 {
2078     astconv::instantiate_poly_trait_ref(astconv,
2079                                         &ExplicitRscope,
2080                                         trait_ref,
2081                                         Some(param_ty),
2082                                         projections)
2083 }
2084
2085 fn conv_param_bounds<'a,'tcx>(astconv: &AstConv<'tcx>,
2086                               span: Span,
2087                               param_ty: ty::Ty<'tcx>,
2088                               ast_bounds: &[ast::TyParamBound])
2089                               -> astconv::Bounds<'tcx>
2090 {
2091     let tcx = astconv.tcx();
2092     let astconv::PartitionedBounds {
2093         builtin_bounds,
2094         trait_bounds,
2095         region_bounds
2096     } = astconv::partition_bounds(tcx, span, &ast_bounds);
2097
2098     let mut projection_bounds = Vec::new();
2099
2100     let trait_bounds: Vec<ty::PolyTraitRef> =
2101         trait_bounds.iter()
2102                     .map(|bound| conv_poly_trait_ref(astconv,
2103                                                      param_ty,
2104                                                      *bound,
2105                                                      &mut projection_bounds))
2106                     .collect();
2107
2108     let region_bounds: Vec<ty::Region> =
2109         region_bounds.into_iter()
2110                      .map(|r| ast_region_to_region(tcx, r))
2111                      .collect();
2112
2113     astconv::Bounds {
2114         region_bounds: region_bounds,
2115         builtin_bounds: builtin_bounds,
2116         trait_bounds: trait_bounds,
2117         projection_bounds: projection_bounds,
2118     }
2119 }
2120
2121 fn compute_type_scheme_of_foreign_fn_decl<'a, 'tcx>(
2122     ccx: &CrateCtxt<'a, 'tcx>,
2123     decl: &ast::FnDecl,
2124     ast_generics: &ast::Generics,
2125     abi: abi::Abi)
2126     -> ty::TypeScheme<'tcx>
2127 {
2128     for i in &decl.inputs {
2129         match (*i).pat.node {
2130             ast::PatIdent(_, _, _) => (),
2131             ast::PatWild(ast::PatWildSingle) => (),
2132             _ => {
2133                 span_err!(ccx.tcx.sess, (*i).pat.span, E0130,
2134                           "patterns aren't allowed in foreign function declarations");
2135             }
2136         }
2137     }
2138
2139     let ty_generics = ty_generics_for_fn(ccx, ast_generics, &ty::Generics::empty());
2140
2141     let rb = BindingRscope::new();
2142     let input_tys = decl.inputs
2143                         .iter()
2144                         .map(|a| ty_of_arg(&ccx.icx(ast_generics), &rb, a, None))
2145                         .collect();
2146
2147     let output = match decl.output {
2148         ast::Return(ref ty) =>
2149             ty::FnConverging(ast_ty_to_ty(&ccx.icx(ast_generics), &rb, &**ty)),
2150         ast::DefaultReturn(..) =>
2151             ty::FnConverging(ccx.tcx.mk_nil()),
2152         ast::NoReturn(..) =>
2153             ty::FnDiverging
2154     };
2155
2156     let t_fn = ccx.tcx.mk_fn(None,
2157         ccx.tcx.mk_bare_fn(ty::BareFnTy {
2158             abi: abi,
2159             unsafety: ast::Unsafety::Unsafe,
2160             sig: ty::Binder(ty::FnSig {inputs: input_tys,
2161                                        output: output,
2162                                        variadic: decl.variadic}),
2163         }));
2164
2165     ty::TypeScheme {
2166         generics: ty_generics,
2167         ty: t_fn
2168     }
2169 }
2170
2171 fn mk_item_substs<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
2172                             ty_generics: &ty::Generics<'tcx>)
2173                             -> Substs<'tcx>
2174 {
2175     let types =
2176         ty_generics.types.map(
2177             |def| ccx.tcx.mk_param_from_def(def));
2178
2179     let regions =
2180         ty_generics.regions.map(
2181             |def| def.to_early_bound_region());
2182
2183     Substs::new(types, regions)
2184 }
2185
2186 /// Verifies that the explicit self type of a method matches the impl
2187 /// or trait. This is a bit weird but basically because right now we
2188 /// don't handle the general case, but instead map it to one of
2189 /// several pre-defined options using various heuristics, this method
2190 /// comes back to check after the fact that explicit type the user
2191 /// wrote actually matches what the pre-defined option said.
2192 fn check_method_self_type<'a, 'tcx, RS:RegionScope>(
2193     ccx: &CrateCtxt<'a, 'tcx>,
2194     rs: &RS,
2195     method_type: Rc<ty::Method<'tcx>>,
2196     required_type: Ty<'tcx>,
2197     explicit_self: &ast::ExplicitSelf,
2198     body_id: ast::NodeId)
2199 {
2200     let tcx = ccx.tcx;
2201     if let ast::SelfExplicit(ref ast_type, _) = explicit_self.node {
2202         let typ = ccx.icx(&method_type.predicates).to_ty(rs, &**ast_type);
2203         let base_type = match typ.sty {
2204             ty::TyRef(_, tm) => tm.ty,
2205             ty::TyBox(typ) => typ,
2206             _ => typ,
2207         };
2208
2209         let body_scope = region::DestructionScopeData::new(body_id);
2210
2211         // "Required type" comes from the trait definition. It may
2212         // contain late-bound regions from the method, but not the
2213         // trait (since traits only have early-bound region
2214         // parameters).
2215         assert!(!base_type.has_regions_escaping_depth(1));
2216         let required_type_free =
2217             liberate_early_bound_regions(
2218                 tcx, body_scope,
2219                 &tcx.liberate_late_bound_regions(body_scope, &ty::Binder(required_type)));
2220
2221         // The "base type" comes from the impl. It too may have late-bound
2222         // regions from the method.
2223         assert!(!base_type.has_regions_escaping_depth(1));
2224         let base_type_free =
2225             liberate_early_bound_regions(
2226                 tcx, body_scope,
2227                 &tcx.liberate_late_bound_regions(body_scope, &ty::Binder(base_type)));
2228
2229         debug!("required_type={:?} required_type_free={:?} \
2230                 base_type={:?} base_type_free={:?}",
2231                required_type,
2232                required_type_free,
2233                base_type,
2234                base_type_free);
2235
2236         let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None, false);
2237         drop(::require_same_types(tcx,
2238                                   Some(&infcx),
2239                                   false,
2240                                   explicit_self.span,
2241                                   base_type_free,
2242                                   required_type_free,
2243                                   || {
2244                 format!("mismatched self type: expected `{}`",
2245                          required_type)
2246         }));
2247
2248         // We could conceviably add more free-region relations here,
2249         // but since this code is just concerned with checking that
2250         // the `&Self` types etc match up, it's not really necessary.
2251         // It would just allow people to be more approximate in some
2252         // cases. In any case, we can do it later as we feel the need;
2253         // I'd like this function to go away eventually.
2254         let free_regions = FreeRegionMap::new();
2255
2256         infcx.resolve_regions_and_report_errors(&free_regions, body_id);
2257     }
2258
2259     fn liberate_early_bound_regions<'tcx,T>(
2260         tcx: &ty::ctxt<'tcx>,
2261         scope: region::DestructionScopeData,
2262         value: &T)
2263         -> T
2264         where T : TypeFoldable<'tcx>
2265     {
2266         /*!
2267          * Convert early-bound regions into free regions; normally this is done by
2268          * applying the `free_substs` from the `ParameterEnvironment`, but this particular
2269          * method-self-type check is kind of hacky and done very early in the process,
2270          * before we really have a `ParameterEnvironment` to check.
2271          */
2272
2273         ty_fold::fold_regions(tcx, value, &mut false, |region, _| {
2274             match region {
2275                 ty::ReEarlyBound(data) => {
2276                     let def_id = local_def(data.param_id);
2277                     ty::ReFree(ty::FreeRegion { scope: scope,
2278                                                 bound_region: ty::BrNamed(def_id, data.name) })
2279                 }
2280                 _ => region
2281             }
2282         })
2283     }
2284 }
2285
2286 /// Checks that all the type parameters on an impl
2287 fn enforce_impl_params_are_constrained<'tcx>(tcx: &ty::ctxt<'tcx>,
2288                                              ast_generics: &ast::Generics,
2289                                              impl_def_id: ast::DefId,
2290                                              impl_items: &[P<ast::ImplItem>])
2291 {
2292     let impl_scheme = tcx.lookup_item_type(impl_def_id);
2293     let impl_predicates = tcx.lookup_predicates(impl_def_id);
2294     let impl_trait_ref = tcx.impl_trait_ref(impl_def_id);
2295
2296     // The trait reference is an input, so find all type parameters
2297     // reachable from there, to start (if this is an inherent impl,
2298     // then just examine the self type).
2299     let mut input_parameters: HashSet<_> =
2300         ctp::parameters_for_type(impl_scheme.ty).into_iter().collect();
2301     if let Some(ref trait_ref) = impl_trait_ref {
2302         input_parameters.extend(ctp::parameters_for_trait_ref(trait_ref));
2303     }
2304
2305     ctp::identify_constrained_type_params(tcx,
2306                                           impl_predicates.predicates.as_slice(),
2307                                           impl_trait_ref,
2308                                           &mut input_parameters);
2309
2310     for (index, ty_param) in ast_generics.ty_params.iter().enumerate() {
2311         let param_ty = ty::ParamTy { space: TypeSpace,
2312                                      idx: index as u32,
2313                                      name: ty_param.ident.name };
2314         if !input_parameters.contains(&ctp::Parameter::Type(param_ty)) {
2315             report_unused_parameter(tcx, ty_param.span, "type", &param_ty.to_string());
2316         }
2317     }
2318
2319     // Every lifetime used in an associated type must be constrained.
2320
2321     let lifetimes_in_associated_types: HashSet<_> =
2322         impl_items.iter()
2323                   .map(|item| tcx.impl_or_trait_item(local_def(item.id)))
2324                   .filter_map(|item| match item {
2325                       ty::TypeTraitItem(ref assoc_ty) => assoc_ty.ty,
2326                       ty::ConstTraitItem(..) | ty::MethodTraitItem(..) => None
2327                   })
2328                   .flat_map(|ty| ctp::parameters_for_type(ty))
2329                   .filter_map(|p| match p {
2330                       ctp::Parameter::Type(_) => None,
2331                       ctp::Parameter::Region(r) => Some(r),
2332                   })
2333                   .collect();
2334
2335     for (index, lifetime_def) in ast_generics.lifetimes.iter().enumerate() {
2336         let region = ty::EarlyBoundRegion { param_id: lifetime_def.lifetime.id,
2337                                             space: TypeSpace,
2338                                             index: index as u32,
2339                                             name: lifetime_def.lifetime.name };
2340         if
2341             lifetimes_in_associated_types.contains(&region) && // (*)
2342             !input_parameters.contains(&ctp::Parameter::Region(region))
2343         {
2344             report_unused_parameter(tcx, lifetime_def.lifetime.span,
2345                                     "lifetime", &region.name.to_string());
2346         }
2347     }
2348
2349     // (*) This is a horrible concession to reality. I think it'd be
2350     // better to just ban unconstrianed lifetimes outright, but in
2351     // practice people do non-hygenic macros like:
2352     //
2353     // ```
2354     // macro_rules! __impl_slice_eq1 {
2355     //     ($Lhs: ty, $Rhs: ty, $Bound: ident) => {
2356     //         impl<'a, 'b, A: $Bound, B> PartialEq<$Rhs> for $Lhs where A: PartialEq<B> {
2357     //            ....
2358     //         }
2359     //     }
2360     // }
2361     // ```
2362     //
2363     // In a concession to backwards compatbility, we continue to
2364     // permit those, so long as the lifetimes aren't used in
2365     // associated types. I believe this is sound, because lifetimes
2366     // used elsewhere are not projected back out.
2367 }
2368
2369 fn report_unused_parameter(tcx: &ty::ctxt,
2370                            span: Span,
2371                            kind: &str,
2372                            name: &str)
2373 {
2374     span_err!(tcx.sess, span, E0207,
2375               "the {} parameter `{}` is not constrained by the \
2376                impl trait, self type, or predicates",
2377               kind, name);
2378 }