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