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 polytypes.  In "layman's terms", this means
  24 that they are generic types that may have type parameters (more
  25 mathematically phrased, they are universally quantified over a set of
  26 type parameters).  TypeSchemes are represented by an instance of
  27 `ty::TypeScheme`.  This combines the core type along with a list of the
  28 bounds for each parameter.  Type parameters themselves are represented
  29 as `ty_param()` instances.
  30
  31 */
  32 use astconv::{self, AstConv, ty_of_arg, ast_ty_to_ty, ast_region_to_region};
  33 use metadata::csearch;
  34 use middle::lang_items::SizedTraitLangItem;
  35 use middle::region;
  36 use middle::resolve_lifetime;
  37 use middle::subst;
  38 use middle::subst::{Substs, TypeSpace};
  39 use middle::ty::{AsPredicate, ImplContainer, ImplOrTraitItemContainer, TraitContainer};
  40 use middle::ty::{self, RegionEscape, Ty, TypeScheme};
  41 use middle::ty_fold::{self, TypeFolder, TypeFoldable};
  42 use middle::infer;
  43 use no_params;
  44 use rscope::*;
  45 use util::nodemap::{FnvHashMap, FnvHashSet};
  46 use util::ppaux;
  47 use util::ppaux::{Repr,UserString};
  48 use write_ty_to_tcx;
  49
  50 use std::collections::HashSet;
  51 use std::rc::Rc;
  52
  53 use syntax::abi;
  54 use syntax::ast;
  55 use syntax::ast_map;
  56 use syntax::ast_util::{local_def, PostExpansionMethod};
  57 use syntax::codemap::Span;
  58 use syntax::parse::token::{special_idents};
  59 use syntax::parse::token;
  60 use syntax::ptr::P;
  61 use syntax::visit;
  62
  63 ///////////////////////////////////////////////////////////////////////////
  64 // Main entry point
  65
  66 pub fn collect_item_types(tcx: &ty::ctxt) {
  67     let ccx = &CollectCtxt { tcx: tcx };
  68
  69     match ccx.tcx.lang_items.ty_desc() {
  70         Some(id) => { collect_intrinsic_type(ccx, id); }
  71         None => {}
  72     }
  73     match ccx.tcx.lang_items.opaque() {
  74         Some(id) => { collect_intrinsic_type(ccx, id); }
  75         None => {}
  76     }
  77
  78     let mut visitor = CollectTraitDefVisitor{ ccx: ccx };
  79     visit::walk_crate(&mut visitor, ccx.tcx.map.krate());
  80
  81     let mut visitor = CollectItemTypesVisitor{ ccx: ccx };
  82     visit::walk_crate(&mut visitor, ccx.tcx.map.krate());
  83 }
  84
  85 ///////////////////////////////////////////////////////////////////////////
  86
  87 struct CollectCtxt<'a,'tcx:'a> {
  88     tcx: &'a ty::ctxt<'tcx>,
  89 }
  90
  91 ///////////////////////////////////////////////////////////////////////////
  92 // Zeroth phase: collect types of intrinsics
  93
  94 fn collect_intrinsic_type(ccx: &CollectCtxt,
  95                           lang_item: ast::DefId) {
  96     let ty::TypeScheme { ty, .. } =
  97         ccx.get_item_type_scheme(lang_item);
  98     ccx.tcx.intrinsic_defs.borrow_mut().insert(lang_item, ty);
  99 }
 100
 101 ///////////////////////////////////////////////////////////////////////////
 102 // First phase: just collect *trait definitions* -- basically, the set
 103 // of type parameters and supertraits. This is information we need to
 104 // know later when parsing field defs.
 105
 106 struct CollectTraitDefVisitor<'a, 'tcx: 'a> {
 107     ccx: &'a CollectCtxt<'a, 'tcx>
 108 }
 109
 110 impl<'a, 'tcx, 'v> visit::Visitor<'v> for CollectTraitDefVisitor<'a, 'tcx> {
 111     fn visit_item(&mut self, i: &ast::Item) {
 112         match i.node {
 113             ast::ItemTrait(..) => {
 114                 // computing the trait def also fills in the table
 115                 let _ = trait_def_of_item(self.ccx, i);
 116             }
 117             _ => { }
 118         }
 119
 120         visit::walk_item(self, i);
 121     }
 122 }
 123
 124 ///////////////////////////////////////////////////////////////////////////
 125 // Second phase: collection proper.
 126
 127 struct CollectItemTypesVisitor<'a, 'tcx: 'a> {
 128     ccx: &'a CollectCtxt<'a, 'tcx>
 129 }
 130
 131 impl<'a, 'tcx, 'v> visit::Visitor<'v> for CollectItemTypesVisitor<'a, 'tcx> {
 132     fn visit_item(&mut self, i: &ast::Item) {
 133         convert(self.ccx, i);
 134         visit::walk_item(self, i);
 135     }
 136     fn visit_foreign_item(&mut self, i: &ast::ForeignItem) {
 137         convert_foreign(self.ccx, i);
 138         visit::walk_foreign_item(self, i);
 139     }
 140 }
 141
 142 ///////////////////////////////////////////////////////////////////////////
 143 // Utility types and common code for the above passes.
 144
 145 pub trait ToTy<'tcx> {
 146     fn to_ty<RS:RegionScope>(&self, rs: &RS, ast_ty: &ast::Ty) -> Ty<'tcx>;
 147 }
 148
 149 impl<'a,'tcx> ToTy<'tcx> for CollectCtxt<'a,'tcx> {
 150     fn to_ty<RS:RegionScope>(&self, rs: &RS, ast_ty: &ast::Ty) -> Ty<'tcx> {
 151         ast_ty_to_ty(self, rs, ast_ty)
 152     }
 153 }
 154
 155 impl<'a, 'tcx> AstConv<'tcx> for CollectCtxt<'a, 'tcx> {
 156     fn tcx(&self) -> &ty::ctxt<'tcx> { self.tcx }
 157
 158     fn get_item_type_scheme(&self, id: ast::DefId) -> ty::TypeScheme<'tcx> {
 159         if id.krate != ast::LOCAL_CRATE {
 160             return csearch::get_type(self.tcx, id)
 161         }
 162
 163         match self.tcx.map.find(id.node) {
 164             Some(ast_map::NodeItem(item)) => {
 165                 ty_of_item(self, &*item)
 166             }
 167             Some(ast_map::NodeForeignItem(foreign_item)) => {
 168                 let abi = self.tcx.map.get_foreign_abi(id.node);
 169                 ty_of_foreign_item(self, &*foreign_item, abi)
 170             }
 171             x => {
 172                 self.tcx.sess.bug(format!("unexpected sort of node \
 173                                            in get_item_type_scheme(): {:?}",
 174                                           x).as_slice());
 175             }
 176         }
 177     }
 178
 179     fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef<'tcx>> {
 180         get_trait_def(self, id)
 181     }
 182
 183     fn ty_infer(&self, span: Span) -> Ty<'tcx> {
 184         span_err!(self.tcx.sess, span, E0121,
 185                   "the type placeholder `_` is not allowed within types on item signatures");
 186         self.tcx().types.err
 187     }
 188
 189     fn projected_ty(&self,
 190                     _span: Span,
 191                     trait_ref: Rc<ty::TraitRef<'tcx>>,
 192                     item_name: ast::Name)
 193                     -> Ty<'tcx>
 194     {
 195         ty::mk_projection(self.tcx, trait_ref, item_name)
 196     }
 197 }
 198
 199 fn get_enum_variant_types<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 200                                         enum_ty: Ty<'tcx>,
 201                                         variants: &[P<ast::Variant>],
 202                                         generics: &ast::Generics) {
 203     let tcx = ccx.tcx;
 204
 205     // Create a set of parameter types shared among all the variants.
 206     for variant in variants {
 207         let variant_def_id = local_def(variant.node.id);
 208
 209         // Nullary enum constructors get turned into constants; n-ary enum
 210         // constructors get turned into functions.
 211         let result_ty = match variant.node.kind {
 212             ast::TupleVariantKind(ref args) if args.len() > 0 => {
 213                 let rs = ExplicitRscope;
 214                 let input_tys: Vec<_> = args.iter().map(|va| ccx.to_ty(&rs, &*va.ty)).collect();
 215                 ty::mk_ctor_fn(tcx, variant_def_id, &input_tys[], enum_ty)
 216             }
 217
 218             ast::TupleVariantKind(_) => {
 219                 enum_ty
 220             }
 221
 222             ast::StructVariantKind(ref struct_def) => {
 223                 let scheme = TypeScheme {
 224                     generics: ty_generics_for_type_or_impl(ccx, generics),
 225                     ty: enum_ty
 226                 };
 227
 228                 convert_struct(ccx, &**struct_def, scheme, variant.node.id);
 229                 enum_ty
 230             }
 231         };
 232
 233         let scheme = TypeScheme {
 234             generics: ty_generics_for_type_or_impl(ccx, generics),
 235             ty: result_ty
 236         };
 237
 238         tcx.tcache.borrow_mut().insert(variant_def_id, scheme);
 239
 240         write_ty_to_tcx(tcx, variant.node.id, result_ty);
 241     }
 242 }
 243
 244 fn collect_trait_methods<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 245                                    trait_id: ast::NodeId,
 246                                    trait_def: &ty::TraitDef<'tcx>) {
 247     let tcx = ccx.tcx;
 248     if let ast_map::NodeItem(item) = tcx.map.get(trait_id) {
 249         if let ast::ItemTrait(_, _, _, ref trait_items) = item.node {
 250             // For each method, construct a suitable ty::Method and
 251             // store it into the `tcx.impl_or_trait_items` table:
 252             for trait_item in trait_items {
 253                 match *trait_item {
 254                     ast::RequiredMethod(_) |
 255                     ast::ProvidedMethod(_) => {
 256                         let ty_method = Rc::new(match *trait_item {
 257                             ast::RequiredMethod(ref m) => {
 258                                 ty_method_of_trait_method(
 259                                     ccx,
 260                                     trait_id,
 261                                     &trait_def.generics,
 262                                     &trait_items[],
 263                                     &m.id,
 264                                     &m.ident.name,
 265                                     &m.explicit_self,
 266                                     m.abi,
 267                                     &m.generics,
 268                                     &m.unsafety,
 269                                     &*m.decl)
 270                             }
 271                             ast::ProvidedMethod(ref m) => {
 272                                 ty_method_of_trait_method(
 273                                     ccx,
 274                                     trait_id,
 275                                     &trait_def.generics,
 276                                     &trait_items[],
 277                                     &m.id,
 278                                     &m.pe_ident().name,
 279                                     m.pe_explicit_self(),
 280                                     m.pe_abi(),
 281                                     m.pe_generics(),
 282                                     &m.pe_unsafety(),
 283                                     &*m.pe_fn_decl())
 284                             }
 285                             ast::TypeTraitItem(ref at) => {
 286                                 tcx.sess.span_bug(at.ty_param.span,
 287                                                   "there shouldn't be a type trait item here")
 288                             }
 289                         });
 290
 291                         debug!("ty_method_of_trait_method yielded {} for method {} of trait {}",
 292                                ty_method.repr(ccx.tcx),
 293                                trait_item.repr(ccx.tcx),
 294                                local_def(trait_id).repr(ccx.tcx));
 295
 296                         make_method_ty(ccx, &*ty_method);
 297
 298                         tcx.impl_or_trait_items
 299                             .borrow_mut()
 300                             .insert(ty_method.def_id, ty::MethodTraitItem(ty_method));
 301                     }
 302                     ast::TypeTraitItem(ref ast_associated_type) => {
 303                         let trait_did = local_def(trait_id);
 304                         let associated_type = ty::AssociatedType {
 305                             name: ast_associated_type.ty_param.ident.name,
 306                             vis: ast::Public,
 307                             def_id: local_def(ast_associated_type.ty_param.id),
 308                             container: TraitContainer(trait_did),
 309                         };
 310
 311                         let trait_item = ty::TypeTraitItem(Rc::new(associated_type));
 312                         tcx.impl_or_trait_items
 313                             .borrow_mut()
 314                             .insert(associated_type.def_id, trait_item);
 315                     }
 316                 }
 317             }
 318
 319             // Add an entry mapping
 320             let trait_item_def_ids =
 321                 Rc::new(trait_items.iter().map(|ti| {
 322                     match *ti {
 323                         ast::RequiredMethod(ref ty_method) => {
 324                             ty::MethodTraitItemId(local_def(ty_method.id))
 325                         }
 326                         ast::ProvidedMethod(ref method) => {
 327                             ty::MethodTraitItemId(local_def(method.id))
 328                         }
 329                         ast::TypeTraitItem(ref typedef) => {
 330                             ty::TypeTraitItemId(local_def(typedef.ty_param.id))
 331                         }
 332                     }
 333                 }).collect());
 334
 335             let trait_def_id = local_def(trait_id);
 336             tcx.trait_item_def_ids.borrow_mut().insert(trait_def_id, trait_item_def_ids);
 337         }
 338     }
 339
 340     fn make_method_ty<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>, m: &ty::Method<'tcx>) {
 341         ccx.tcx.tcache.borrow_mut().insert(
 342             m.def_id,
 343             TypeScheme {
 344                 generics: m.generics.clone(),
 345                 ty: ty::mk_bare_fn(ccx.tcx, Some(m.def_id), ccx.tcx.mk_bare_fn(m.fty.clone())) });
 346     }
 347
 348     fn ty_method_of_trait_method<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 349                                            trait_id: ast::NodeId,
 350                                            trait_generics: &ty::Generics<'tcx>,
 351                                            _trait_items: &[ast::TraitItem],
 352                                            m_id: &ast::NodeId,
 353                                            m_name: &ast::Name,
 354                                            m_explicit_self: &ast::ExplicitSelf,
 355                                            m_abi: abi::Abi,
 356                                            m_generics: &ast::Generics,
 357                                            m_unsafety: &ast::Unsafety,
 358                                            m_decl: &ast::FnDecl)
 359                                            -> ty::Method<'tcx> {
 360         let ty_generics =
 361             ty_generics_for_fn_or_method(
 362                 ccx,
 363                 m_generics,
 364                 (*trait_generics).clone());
 365
 366         let (fty, explicit_self_category) = {
 367             let trait_self_ty = ty::mk_self_type(ccx.tcx);
 368             astconv::ty_of_method(ccx,
 369                                   *m_unsafety,
 370                                   trait_self_ty,
 371                                   m_explicit_self,
 372                                   m_decl,
 373                                   m_abi)
 374         };
 375
 376         ty::Method::new(
 377             *m_name,
 378             ty_generics,
 379             fty,
 380             explicit_self_category,
 381             // assume public, because this is only invoked on trait methods
 382             ast::Public,
 383             local_def(*m_id),
 384             TraitContainer(local_def(trait_id)),
 385             None
 386         )
 387     }
 388 }
 389
 390 fn convert_field<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 391                                 struct_generics: &ty::Generics<'tcx>,
 392                                 v: &ast::StructField,
 393                                 origin: ast::DefId) -> ty::field_ty {
 394     let tt = ccx.to_ty(&ExplicitRscope, &*v.node.ty);
 395     write_ty_to_tcx(ccx.tcx, v.node.id, tt);
 396     /* add the field to the tcache */
 397     ccx.tcx.tcache.borrow_mut().insert(local_def(v.node.id),
 398                                        ty::TypeScheme {
 399                                            generics: struct_generics.clone(),
 400                                            ty: tt
 401                                        });
 402
 403     match v.node.kind {
 404         ast::NamedField(ident, visibility) => {
 405             ty::field_ty {
 406                 name: ident.name,
 407                 id: local_def(v.node.id),
 408                 vis: visibility,
 409                 origin: origin,
 410             }
 411         }
 412         ast::UnnamedField(visibility) => {
 413             ty::field_ty {
 414                 name: special_idents::unnamed_field.name,
 415                 id: local_def(v.node.id),
 416                 vis: visibility,
 417                 origin: origin,
 418             }
 419         }
 420     }
 421 }
 422
 423 fn convert_associated_type<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 424                                      trait_def: &ty::TraitDef<'tcx>,
 425                                      associated_type: &ast::AssociatedType)
 426 {
 427     let associated_type = Rc::new(ty::AssociatedType {
 428         name: associated_type.ty_param.ident.name,
 429         vis: ast::Public,
 430         def_id: local_def(associated_type.ty_param.id),
 431         container: TraitContainer(trait_def.trait_ref.def_id),
 432     });
 433     ccx.tcx
 434        .impl_or_trait_items
 435        .borrow_mut()
 436        .insert(associated_type.def_id,
 437                ty::TypeTraitItem(associated_type));
 438 }
 439
 440 fn convert_methods<'a,'tcx,'i,I>(ccx: &CollectCtxt<'a, 'tcx>,
 441                                  container: ImplOrTraitItemContainer,
 442                                  mut ms: I,
 443                                  untransformed_rcvr_ty: Ty<'tcx>,
 444                                  rcvr_ty_generics: &ty::Generics<'tcx>,
 445                                  rcvr_visibility: ast::Visibility)
 446                                  where I: Iterator<Item=&'i ast::Method> {
 447     debug!("convert_methods(untransformed_rcvr_ty={}, rcvr_ty_generics={})",
 448            untransformed_rcvr_ty.repr(ccx.tcx),
 449            rcvr_ty_generics.repr(ccx.tcx));
 450
 451     let tcx = ccx.tcx;
 452     let mut seen_methods = FnvHashSet();
 453     for m in ms {
 454         if !seen_methods.insert(m.pe_ident().repr(tcx)) {
 455             span_err!(tcx.sess, m.span, E0201, "duplicate method in trait impl");
 456         }
 457
 458         let m_def_id = local_def(m.id);
 459         let mty = Rc::new(ty_of_method(ccx,
 460                                        container,
 461                                        m,
 462                                        untransformed_rcvr_ty,
 463                                        rcvr_ty_generics,
 464                                        rcvr_visibility));
 465         let fty = ty::mk_bare_fn(tcx, Some(m_def_id), tcx.mk_bare_fn(mty.fty.clone()));
 466         debug!("method {} (id {}) has type {}",
 467                 m.pe_ident().repr(tcx),
 468                 m.id,
 469                 fty.repr(tcx));
 470         tcx.tcache.borrow_mut().insert(
 471             m_def_id,
 472             TypeScheme {
 473                 generics: mty.generics.clone(),
 474                 ty: fty
 475             });
 476
 477         write_ty_to_tcx(tcx, m.id, fty);
 478
 479         debug!("writing method type: def_id={:?} mty={}",
 480                mty.def_id, mty.repr(ccx.tcx));
 481
 482         tcx.impl_or_trait_items
 483            .borrow_mut()
 484            .insert(mty.def_id, ty::MethodTraitItem(mty));
 485     }
 486
 487     fn ty_of_method<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 488                               container: ImplOrTraitItemContainer,
 489                               m: &ast::Method,
 490                               untransformed_rcvr_ty: Ty<'tcx>,
 491                               rcvr_ty_generics: &ty::Generics<'tcx>,
 492                               rcvr_visibility: ast::Visibility)
 493                               -> ty::Method<'tcx> {
 494         let m_ty_generics =
 495             ty_generics_for_fn_or_method(
 496                 ccx,
 497                 m.pe_generics(),
 498                 (*rcvr_ty_generics).clone());
 499
 500         let (fty, explicit_self_category) = astconv::ty_of_method(ccx,
 501                                                                   m.pe_unsafety(),
 502                                                                   untransformed_rcvr_ty,
 503                                                                   m.pe_explicit_self(),
 504                                                                   &*m.pe_fn_decl(),
 505                                                                   m.pe_abi());
 506
 507         // if the method specifies a visibility, use that, otherwise
 508         // inherit the visibility from the impl (so `foo` in `pub impl
 509         // { fn foo(); }` is public, but private in `priv impl { fn
 510         // foo(); }`).
 511         let method_vis = m.pe_vis().inherit_from(rcvr_visibility);
 512
 513         ty::Method::new(m.pe_ident().name,
 514                         m_ty_generics,
 515                         fty,
 516                         explicit_self_category,
 517                         method_vis,
 518                         local_def(m.id),
 519                         container,
 520                         None)
 521     }
 522 }
 523
 524 fn ensure_no_ty_param_bounds(ccx: &CollectCtxt,
 525                                  span: Span,
 526                                  generics: &ast::Generics,
 527                                  thing: &'static str) {
 528     let mut warn = false;
 529
 530     for ty_param in &*generics.ty_params {
 531         for bound in &*ty_param.bounds {
 532             match *bound {
 533                 ast::TraitTyParamBound(..) => {
 534                     warn = true;
 535                 }
 536                 ast::RegionTyParamBound(..) => { }
 537             }
 538         }
 539     }
 540
 541     if warn {
 542         // According to accepted RFC #XXX, we should
 543         // eventually accept these, but it will not be
 544         // part of this PR. Still, convert to warning to
 545         // make bootstrapping easier.
 546         span_warn!(ccx.tcx.sess, span, E0122,
 547                    "trait bounds are not (yet) enforced \
 548                    in {} definitions",
 549                    thing);
 550     }
 551 }
 552
 553 fn convert(ccx: &CollectCtxt, it: &ast::Item) {
 554     let tcx = ccx.tcx;
 555     debug!("convert: item {} with id {}", token::get_ident(it.ident), it.id);
 556     match it.node {
 557         // These don't define types.
 558         ast::ItemExternCrate(_) | ast::ItemUse(_) |
 559         ast::ItemForeignMod(_) | ast::ItemMod(_) | ast::ItemMac(_) => {}
 560         ast::ItemEnum(ref enum_definition, ref generics) => {
 561             let scheme = ty_of_item(ccx, it);
 562             write_ty_to_tcx(tcx, it.id, scheme.ty);
 563             get_enum_variant_types(ccx,
 564                                    scheme.ty,
 565                                    enum_definition.variants.as_slice(),
 566                                    generics);
 567         },
 568         ast::ItemImpl(_, _,
 569                       ref generics,
 570                       ref opt_trait_ref,
 571                       ref selfty,
 572                       ref impl_items) => {
 573             // Create generics from the generics specified in the impl head.
 574             let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
 575
 576             let selfty = ccx.to_ty(&ExplicitRscope, &**selfty);
 577             write_ty_to_tcx(tcx, it.id, selfty);
 578
 579             tcx.tcache
 580                .borrow_mut()
 581                .insert(local_def(it.id),
 582                        TypeScheme {
 583                         generics: ty_generics.clone(),
 584                         ty: selfty,
 585                        });
 586
 587             // If there is a trait reference, treat the methods as always public.
 588             // This is to work around some incorrect behavior in privacy checking:
 589             // when the method belongs to a trait, it should acquire the privacy
 590             // from the trait, not the impl. Forcing the visibility to be public
 591             // makes things sorta work.
 592             let parent_visibility = if opt_trait_ref.is_some() {
 593                 ast::Public
 594             } else {
 595                 it.vis
 596             };
 597
 598             let mut methods = Vec::new();
 599             for impl_item in impl_items {
 600                 match *impl_item {
 601                     ast::MethodImplItem(ref method) => {
 602                         let body_id = method.pe_body().id;
 603                         check_method_self_type(ccx,
 604                                                &BindingRscope::new(),
 605                                                selfty,
 606                                                method.pe_explicit_self(),
 607                                                body_id);
 608                         methods.push(&**method);
 609                     }
 610                     ast::TypeImplItem(ref typedef) => {
 611                         if opt_trait_ref.is_none() {
 612                             span_err!(tcx.sess, typedef.span, E0202,
 613                                               "associated items are not allowed in inherent impls");
 614                         }
 615
 616                         let typ = ccx.to_ty(&ExplicitRscope, &*typedef.typ);
 617                         tcx.tcache
 618                            .borrow_mut()
 619                            .insert(local_def(typedef.id),
 620                                    TypeScheme {
 621                                     generics: ty::Generics::empty(),
 622                                     ty: typ,
 623                                    });
 624                         write_ty_to_tcx(ccx.tcx, typedef.id, typ);
 625
 626                         let associated_type = Rc::new(ty::AssociatedType {
 627                             name: typedef.ident.name,
 628                             vis: typedef.vis,
 629                             def_id: local_def(typedef.id),
 630                             container: ty::ImplContainer(local_def(it.id)),
 631                         });
 632                         tcx.impl_or_trait_items
 633                            .borrow_mut()
 634                            .insert(local_def(typedef.id),
 635                                    ty::TypeTraitItem(associated_type));
 636                     }
 637                 }
 638             }
 639
 640             convert_methods(ccx,
 641                             ImplContainer(local_def(it.id)),
 642                             methods.into_iter(),
 643                             selfty,
 644                             &ty_generics,
 645                             parent_visibility);
 646
 647             if let Some(ref trait_ref) = *opt_trait_ref {
 648                 astconv::instantiate_trait_ref(ccx,
 649                                                &ExplicitRscope,
 650                                                trait_ref,
 651                                                Some(selfty),
 652                                                None);
 653             }
 654
 655             enforce_impl_ty_params_are_constrained(ccx.tcx,
 656                                                    generics,
 657                                                    local_def(it.id));
 658         },
 659         ast::ItemTrait(_, _, _, ref trait_methods) => {
 660             let trait_def = trait_def_of_item(ccx, it);
 661
 662             debug!("trait_def: ident={} trait_def={}",
 663                    it.ident.repr(ccx.tcx),
 664                    trait_def.repr(ccx.tcx));
 665
 666             for trait_method in trait_methods {
 667                 let self_type = ty::mk_self_type(tcx);
 668                 match *trait_method {
 669                     ast::RequiredMethod(ref type_method) => {
 670                         let rscope = BindingRscope::new();
 671                         check_method_self_type(ccx,
 672                                                &rscope,
 673                                                self_type,
 674                                                &type_method.explicit_self,
 675                                                it.id)
 676                     }
 677                     ast::ProvidedMethod(ref method) => {
 678                         check_method_self_type(ccx,
 679                                                &BindingRscope::new(),
 680                                                self_type,
 681                                                method.pe_explicit_self(),
 682                                                it.id)
 683                     }
 684                     ast::TypeTraitItem(ref associated_type) => {
 685                         convert_associated_type(ccx,
 686                                                 &*trait_def,
 687                                                 &**associated_type);
 688                     }
 689                 }
 690             }
 691
 692             // Run convert_methods on the provided methods.
 693             let untransformed_rcvr_ty = ty::mk_self_type(tcx);
 694             convert_methods(ccx,
 695                             TraitContainer(local_def(it.id)),
 696                             trait_methods.iter().filter_map(|m| match *m {
 697                                 ast::RequiredMethod(_) => None,
 698                                 ast::ProvidedMethod(ref m) => Some(&**m),
 699                                 ast::TypeTraitItem(_) => None,
 700                             }),
 701                             untransformed_rcvr_ty,
 702                             &trait_def.generics,
 703                             it.vis);
 704
 705             // We need to do this *after* converting methods, since
 706             // convert_methods produces a tcache entry that is wrong for
 707             // static trait methods. This is somewhat unfortunate.
 708             collect_trait_methods(ccx, it.id, &*trait_def);
 709         },
 710         ast::ItemStruct(ref struct_def, _) => {
 711             // Write the class type.
 712             let scheme = ty_of_item(ccx, it);
 713             write_ty_to_tcx(tcx, it.id, scheme.ty);
 714
 715             tcx.tcache.borrow_mut().insert(local_def(it.id), scheme.clone());
 716
 717             convert_struct(ccx, &**struct_def, scheme, it.id);
 718         },
 719         ast::ItemTy(_, ref generics) => {
 720             ensure_no_ty_param_bounds(ccx, it.span, generics, "type");
 721             let tpt = ty_of_item(ccx, it);
 722             write_ty_to_tcx(tcx, it.id, tpt.ty);
 723         },
 724         _ => {
 725             // This call populates the type cache with the converted type
 726             // of the item in passing. All we have to do here is to write
 727             // it into the node type table.
 728             let scheme = ty_of_item(ccx, it);
 729             write_ty_to_tcx(tcx, it.id, scheme.ty);
 730         },
 731     }
 732 }
 733
 734 fn convert_struct<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 735                                 struct_def: &ast::StructDef,
 736                                 scheme: ty::TypeScheme<'tcx>,
 737                                 id: ast::NodeId) {
 738     let tcx = ccx.tcx;
 739
 740     // Write the type of each of the members and check for duplicate fields.
 741     let mut seen_fields: FnvHashMap<ast::Name, Span> = FnvHashMap();
 742     let field_tys = struct_def.fields.iter().map(|f| {
 743         let result = convert_field(ccx, &scheme.generics, f, local_def(id));
 744
 745         if result.name != special_idents::unnamed_field.name {
 746             let dup = match seen_fields.get(&result.name) {
 747                 Some(prev_span) => {
 748                     span_err!(tcx.sess, f.span, E0124,
 749                               "field `{}` is already declared",
 750                               token::get_name(result.name));
 751                     span_note!(tcx.sess, *prev_span, "previously declared here");
 752                     true
 753                 },
 754                 None => false,
 755             };
 756             // FIXME(#6393) this whole dup thing is just to satisfy
 757             // the borrow checker :-(
 758             if !dup {
 759                 seen_fields.insert(result.name, f.span);
 760             }
 761         }
 762
 763         result
 764     }).collect();
 765
 766     tcx.struct_fields.borrow_mut().insert(local_def(id), Rc::new(field_tys));
 767
 768     let substs = mk_item_substs(ccx, &scheme.generics);
 769     let selfty = ty::mk_struct(tcx, local_def(id), tcx.mk_substs(substs));
 770
 771     // If this struct is enum-like or tuple-like, create the type of its
 772     // constructor.
 773     match struct_def.ctor_id {
 774         None => {}
 775         Some(ctor_id) => {
 776             if struct_def.fields.len() == 0 {
 777                 // Enum-like.
 778                 write_ty_to_tcx(tcx, ctor_id, selfty);
 779
 780                 tcx.tcache.borrow_mut().insert(local_def(ctor_id), scheme);
 781             } else if struct_def.fields[0].node.kind.is_unnamed() {
 782                 // Tuple-like.
 783                 let inputs: Vec<_> = struct_def.fields.iter().map(
 784                         |field| (*tcx.tcache.borrow())[
 785                             local_def(field.node.id)].ty).collect();
 786                 let ctor_fn_ty = ty::mk_ctor_fn(tcx,
 787                                                 local_def(ctor_id),
 788                                                 &inputs[],
 789                                                 selfty);
 790                 write_ty_to_tcx(tcx, ctor_id, ctor_fn_ty);
 791                 tcx.tcache.borrow_mut().insert(local_def(ctor_id),
 792                                   TypeScheme {
 793                     generics: scheme.generics,
 794                     ty: ctor_fn_ty
 795                 });
 796             }
 797         }
 798     }
 799 }
 800
 801 fn convert_foreign(ccx: &CollectCtxt, i: &ast::ForeignItem) {
 802     // As above, this call populates the type table with the converted
 803     // type of the foreign item. We simply write it into the node type
 804     // table.
 805
 806     // For reasons I cannot fully articulate, I do so hate the AST
 807     // map, and I regard each time that I use it as a personal and
 808     // moral failing, but at the moment it seems like the only
 809     // convenient way to extract the ABI. - ndm
 810     let abi = ccx.tcx.map.get_foreign_abi(i.id);
 811
 812     let scheme = ty_of_foreign_item(ccx, i, abi);
 813     write_ty_to_tcx(ccx.tcx, i.id, scheme.ty);
 814
 815     ccx.tcx.tcache.borrow_mut().insert(local_def(i.id), scheme);
 816 }
 817
 818 fn get_trait_def<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 819                            trait_id: ast::DefId)
 820                            -> Rc<ty::TraitDef<'tcx>> {
 821     if trait_id.krate != ast::LOCAL_CRATE {
 822         return ty::lookup_trait_def(ccx.tcx, trait_id)
 823     }
 824
 825     match ccx.tcx.map.get(trait_id.node) {
 826         ast_map::NodeItem(item) => trait_def_of_item(ccx, &*item),
 827         _ => {
 828             ccx.tcx.sess.bug(&format!("get_trait_def({}): not an item",
 829                                      trait_id.node)[])
 830         }
 831     }
 832 }
 833
 834 fn trait_def_of_item<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 835                                it: &ast::Item)
 836                                -> Rc<ty::TraitDef<'tcx>>
 837 {
 838     let def_id = local_def(it.id);
 839     let tcx = ccx.tcx;
 840     if let Some(def) = tcx.trait_defs.borrow().get(&def_id) {
 841         return def.clone();
 842     }
 843
 844     let (unsafety, generics, bounds, items) = match it.node {
 845         ast::ItemTrait(unsafety,
 846                        ref generics,
 847                        ref supertraits,
 848                        ref items) => {
 849             (unsafety, generics, supertraits, items.as_slice())
 850         }
 851         ref s => {
 852             tcx.sess.span_bug(
 853                 it.span,
 854                 &format!("trait_def_of_item invoked on {:?}", s)[]);
 855         }
 856     };
 857
 858     let paren_sugar = ty::has_attr(tcx, def_id, "rustc_paren_sugar");
 859     if paren_sugar && !ccx.tcx.sess.features.borrow().unboxed_closures {
 860         ccx.tcx.sess.span_err(
 861             it.span,
 862             "the `#[rustc_paren_sugar]` attribute is a temporary means of controlling \
 863              which traits can use parenthetical notation");
 864         span_help!(ccx.tcx.sess, it.span,
 865                    "add `#![feature(unboxed_closures)]` to \
 866                     the crate attributes to use it");
 867     }
 868
 869     let substs = ccx.tcx.mk_substs(mk_trait_substs(ccx, generics));
 870
 871     let ty_generics = ty_generics_for_trait(ccx,
 872                                             it.id,
 873                                             substs,
 874                                             generics,
 875                                             items);
 876
 877     let self_param_ty = ty::ParamTy::for_self();
 878
 879     let bounds = compute_bounds(ccx,
 880                                 self_param_ty.to_ty(ccx.tcx),
 881                                 bounds.as_slice(),
 882                                 SizedByDefault::No,
 883                                 it.span);
 884
 885     let associated_type_names: Vec<_> =
 886         items.iter()
 887              .filter_map(|item| {
 888                  match *item {
 889                      ast::RequiredMethod(_) | ast::ProvidedMethod(_) => None,
 890                      ast::TypeTraitItem(ref data) => Some(data.ty_param.ident.name),
 891                  }
 892              })
 893             .collect();
 894
 895     let trait_ref = Rc::new(ty::TraitRef {
 896         def_id: def_id,
 897         substs: substs
 898     });
 899
 900     let trait_def = Rc::new(ty::TraitDef {
 901         paren_sugar: paren_sugar,
 902         unsafety: unsafety,
 903         generics: ty_generics,
 904         bounds: bounds,
 905         trait_ref: trait_ref,
 906         associated_type_names: associated_type_names,
 907     });
 908     tcx.trait_defs.borrow_mut().insert(def_id, trait_def.clone());
 909
 910     return trait_def;
 911
 912     fn mk_trait_substs<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 913                                  generics: &ast::Generics)
 914                                  -> subst::Substs<'tcx>
 915     {
 916         // Creates a no-op substitution for the trait's type parameters.
 917         let regions =
 918             generics.lifetimes
 919                     .iter()
 920                     .enumerate()
 921                     .map(|(i, def)| ty::ReEarlyBound(def.lifetime.id,
 922                                                      subst::TypeSpace,
 923                                                      i as u32,
 924                                                      def.lifetime.name))
 925                     .collect();
 926
 927         // Start with the generics in the type parameters...
 928         let types: Vec<_> =
 929             generics.ty_params
 930                     .iter()
 931                     .enumerate()
 932                     .map(|(i, def)| ty::mk_param(ccx.tcx, subst::TypeSpace,
 933                                                  i as u32, def.ident.name))
 934                     .collect();
 935
 936         // ...and also create the `Self` parameter.
 937         let self_ty = ty::mk_self_type(ccx.tcx);
 938
 939         subst::Substs::new_trait(types, regions, self_ty)
 940     }
 941 }
 942
 943 fn ty_of_item<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>, it: &ast::Item)
 944                             -> ty::TypeScheme<'tcx> {
 945     let def_id = local_def(it.id);
 946     let tcx = ccx.tcx;
 947     if let Some(scheme) = tcx.tcache.borrow().get(&def_id) {
 948         return scheme.clone();
 949     }
 950     match it.node {
 951         ast::ItemStatic(ref t, _, _) | ast::ItemConst(ref t, _) => {
 952             let typ = ccx.to_ty(&ExplicitRscope, &**t);
 953             let scheme = no_params(typ);
 954
 955             tcx.tcache.borrow_mut().insert(local_def(it.id), scheme.clone());
 956             return scheme;
 957         }
 958         ast::ItemFn(ref decl, unsafety, abi, ref generics, _) => {
 959             let ty_generics = ty_generics_for_fn_or_method(ccx,
 960                                                            generics,
 961                                                            ty::Generics::empty());
 962             let tofd = astconv::ty_of_bare_fn(ccx, unsafety, abi, &**decl);
 963             let scheme = TypeScheme {
 964                 generics: ty_generics,
 965                 ty: ty::mk_bare_fn(ccx.tcx, Some(local_def(it.id)), ccx.tcx.mk_bare_fn(tofd))
 966             };
 967             debug!("type of {} (id {}) is {}",
 968                     token::get_ident(it.ident),
 969                     it.id,
 970                     scheme.repr(tcx));
 971
 972             ccx.tcx.tcache.borrow_mut().insert(local_def(it.id), scheme.clone());
 973             return scheme;
 974         }
 975         ast::ItemTy(ref t, ref generics) => {
 976             match tcx.tcache.borrow_mut().get(&local_def(it.id)) {
 977                 Some(scheme) => return scheme.clone(),
 978                 None => { }
 979             }
 980
 981             let scheme = {
 982                 let ty = ccx.to_ty(&ExplicitRscope, &**t);
 983                 TypeScheme {
 984                     generics: ty_generics_for_type_or_impl(ccx, generics),
 985                     ty: ty
 986                 }
 987             };
 988
 989             tcx.tcache.borrow_mut().insert(local_def(it.id), scheme.clone());
 990             return scheme;
 991         }
 992         ast::ItemEnum(_, ref generics) => {
 993             // Create a new generic polytype.
 994             let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
 995             let substs = mk_item_substs(ccx, &ty_generics);
 996             let t = ty::mk_enum(tcx, local_def(it.id), tcx.mk_substs(substs));
 997             let scheme = TypeScheme {
 998                 generics: ty_generics,
 999                 ty: t
1000             };
1001
1002             tcx.tcache.borrow_mut().insert(local_def(it.id), scheme.clone());
1003             return scheme;
1004         }
1005         ast::ItemTrait(..) => {
1006             tcx.sess.span_bug(it.span, "invoked ty_of_item on trait");
1007         }
1008         ast::ItemStruct(_, ref generics) => {
1009             let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
1010             let substs = mk_item_substs(ccx, &ty_generics);
1011             let t = ty::mk_struct(tcx, local_def(it.id), tcx.mk_substs(substs));
1012             let scheme = TypeScheme {
1013                 generics: ty_generics,
1014                 ty: t
1015             };
1016
1017             tcx.tcache.borrow_mut().insert(local_def(it.id), scheme.clone());
1018             return scheme;
1019         }
1020         ast::ItemExternCrate(_) | ast::ItemUse(_) |
1021         ast::ItemImpl(..) | ast::ItemMod(_) |
1022         ast::ItemForeignMod(_) | ast::ItemMac(_) => panic!(),
1023     }
1024 }
1025
1026 fn ty_of_foreign_item<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
1027                                     it: &ast::ForeignItem,
1028                                     abi: abi::Abi) -> ty::TypeScheme<'tcx>
1029 {
1030     match it.node {
1031         ast::ForeignItemFn(ref fn_decl, ref generics) => {
1032             ty_of_foreign_fn_decl(ccx,
1033                                   &**fn_decl,
1034                                   local_def(it.id),
1035                                   generics,
1036                                   abi)
1037         }
1038         ast::ForeignItemStatic(ref t, _) => {
1039             ty::TypeScheme {
1040                 generics: ty::Generics::empty(),
1041                 ty: ast_ty_to_ty(ccx, &ExplicitRscope, &**t)
1042             }
1043         }
1044     }
1045 }
1046
1047 fn ty_generics_for_type_or_impl<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
1048                                           generics: &ast::Generics)
1049                                           -> ty::Generics<'tcx> {
1050     ty_generics(ccx,
1051                 subst::TypeSpace,
1052                 &generics.lifetimes[],
1053                 &generics.ty_params[],
1054                 ty::Generics::empty(),
1055                 &generics.where_clause)
1056 }
1057
1058 fn ty_generics_for_trait<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
1059                                    trait_id: ast::NodeId,
1060                                    substs: &'tcx subst::Substs<'tcx>,
1061                                    ast_generics: &ast::Generics,
1062                                    trait_items: &[ast::TraitItem])
1063                                    -> ty::Generics<'tcx>
1064 {
1065     debug!("ty_generics_for_trait(trait_id={}, substs={})",
1066            local_def(trait_id).repr(ccx.tcx), substs.repr(ccx.tcx));
1067
1068     let mut generics =
1069         ty_generics(ccx,
1070                     subst::TypeSpace,
1071                     &ast_generics.lifetimes[],
1072                     &ast_generics.ty_params[],
1073                     ty::Generics::empty(),
1074                     &ast_generics.where_clause);
1075
1076     // Add in the self type parameter.
1077     //
1078     // Something of a hack: use the node id for the trait, also as
1079     // the node id for the Self type parameter.
1080     let param_id = trait_id;
1081
1082     let self_trait_ref =
1083         Rc::new(ty::TraitRef { def_id: local_def(trait_id),
1084                                substs: substs });
1085
1086     let def = ty::TypeParameterDef {
1087         space: subst::SelfSpace,
1088         index: 0,
1089         name: special_idents::type_self.name,
1090         def_id: local_def(param_id),
1091         bounds: ty::ParamBounds {
1092             region_bounds: vec!(),
1093             builtin_bounds: ty::empty_builtin_bounds(),
1094             trait_bounds: vec!(ty::Binder(self_trait_ref.clone())),
1095             projection_bounds: vec!(),
1096         },
1097         default: None
1098     };
1099
1100     ccx.tcx.ty_param_defs.borrow_mut().insert(param_id, def.clone());
1101
1102     generics.types.push(subst::SelfSpace, def);
1103
1104     generics.predicates.push(subst::SelfSpace, self_trait_ref.as_predicate());
1105
1106     let assoc_predicates = predicates_for_associated_types(ccx,
1107                                                            &self_trait_ref,
1108                                                            trait_items);
1109
1110     debug!("ty_generics_for_trait: assoc_predicates={}", assoc_predicates.repr(ccx.tcx));
1111
1112     for assoc_predicate in assoc_predicates {
1113         generics.predicates.push(subst::TypeSpace, assoc_predicate);
1114     }
1115
1116     return generics;
1117
1118     fn predicates_for_associated_types<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
1119                                                  self_trait_ref: &Rc<ty::TraitRef<'tcx>>,
1120                                                  trait_items: &[ast::TraitItem])
1121                                                  -> Vec<ty::Predicate<'tcx>>
1122     {
1123         trait_items
1124             .iter()
1125             .flat_map(|trait_item| {
1126                 let assoc_type_def = match *trait_item {
1127                     ast::TypeTraitItem(ref assoc_type) => &assoc_type.ty_param,
1128                     ast::RequiredMethod(..) | ast::ProvidedMethod(..) => {
1129                         return vec!().into_iter();
1130                     }
1131                 };
1132
1133                 let assoc_ty = ty::mk_projection(ccx.tcx,
1134                                                  self_trait_ref.clone(),
1135                                                  assoc_type_def.ident.name);
1136
1137                 let bounds = compute_bounds(ccx,
1138                                             assoc_ty,
1139                                             assoc_type_def.bounds.as_slice(),
1140                                             SizedByDefault::Yes,
1141                                             assoc_type_def.span);
1142
1143                 ty::predicates(ccx.tcx, assoc_ty, &bounds).into_iter()
1144             })
1145             .collect()
1146     }
1147 }
1148
1149 fn ty_generics_for_fn_or_method<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1150                                          generics: &ast::Generics,
1151                                          base_generics: ty::Generics<'tcx>)
1152                                          -> ty::Generics<'tcx>
1153 {
1154     let early_lifetimes = resolve_lifetime::early_bound_lifetimes(generics);
1155     ty_generics(ccx,
1156                 subst::FnSpace,
1157                 &early_lifetimes[],
1158                 &generics.ty_params[],
1159                 base_generics,
1160                 &generics.where_clause)
1161 }
1162
1163 // Add the Sized bound, unless the type parameter is marked as `?Sized`.
1164 fn add_unsized_bound<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1165                               bounds: &mut ty::BuiltinBounds,
1166                               ast_bounds: &[ast::TyParamBound],
1167                               span: Span)
1168 {
1169     // Try to find an unbound in bounds.
1170     let mut unbound = None;
1171     for ab in ast_bounds {
1172         if let &ast::TraitTyParamBound(ref ptr, ast::TraitBoundModifier::Maybe) = ab  {
1173             if unbound.is_none() {
1174                 assert!(ptr.bound_lifetimes.is_empty());
1175                 unbound = Some(ptr.trait_ref.clone());
1176             } else {
1177                 span_err!(ccx.tcx.sess, span, E0203,
1178                           "type parameter has more than one relaxed default \
1179                                                 bound, only one is supported");
1180             }
1181         }
1182     }
1183
1184     let kind_id = ccx.tcx.lang_items.require(SizedTraitLangItem);
1185     match unbound {
1186         Some(ref tpb) => {
1187             // FIXME(#8559) currently requires the unbound to be built-in.
1188             let trait_def_id = ty::trait_ref_to_def_id(ccx.tcx, tpb);
1189             match kind_id {
1190                 Ok(kind_id) if trait_def_id != kind_id => {
1191                     ccx.tcx.sess.span_warn(span,
1192                                               "default bound relaxed for a type parameter, but \
1193                                                this does nothing because the given bound is not \
1194                                                a default. Only `?Sized` is supported");
1195                     ty::try_add_builtin_trait(ccx.tcx,
1196                                               kind_id,
1197                                               bounds);
1198                 }
1199                 _ => {}
1200             }
1201         }
1202         _ if kind_id.is_ok() => {
1203             ty::try_add_builtin_trait(ccx.tcx, kind_id.unwrap(), bounds);
1204         }
1205         // No lang item for Sized, so we can't add it as a bound.
1206         None => {}
1207     }
1208 }
1209
1210 fn ty_generics<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1211                         space: subst::ParamSpace,
1212                         lifetime_defs: &[ast::LifetimeDef],
1213                         types: &[ast::TyParam],
1214                         base_generics: ty::Generics<'tcx>,
1215                         where_clause: &ast::WhereClause)
1216                         -> ty::Generics<'tcx>
1217 {
1218     let mut result = base_generics;
1219
1220     for (i, l) in lifetime_defs.iter().enumerate() {
1221         let bounds = l.bounds.iter()
1222                              .map(|l| ast_region_to_region(ccx.tcx, l))
1223                              .collect();
1224         let def = ty::RegionParameterDef { name: l.lifetime.name,
1225                                            space: space,
1226                                            index: i as u32,
1227                                            def_id: local_def(l.lifetime.id),
1228                                            bounds: bounds };
1229         debug!("ty_generics: def for region param: {:?}", def);
1230         result.regions.push(space, def);
1231     }
1232
1233     assert!(result.types.is_empty_in(space));
1234
1235     // Now create the real type parameters.
1236     for (i, param) in types.iter().enumerate() {
1237         let def = get_or_create_type_parameter_def(ccx,
1238                                                    space,
1239                                                    param,
1240                                                    i as u32);
1241         debug!("ty_generics: def for type param: {}, {:?}",
1242                def.repr(ccx.tcx),
1243                space);
1244         result.types.push(space, def);
1245     }
1246
1247     // Just for fun, also push the bounds from the type parameters
1248     // into the predicates list. This is currently kind of non-DRY.
1249     create_predicates(ccx.tcx, &mut result, space);
1250
1251     // Add the bounds not associated with a type parameter
1252     for predicate in &where_clause.predicates {
1253         match predicate {
1254             &ast::WherePredicate::BoundPredicate(ref bound_pred) => {
1255                 let ty = ast_ty_to_ty(ccx, &ExplicitRscope, &*bound_pred.bounded_ty);
1256
1257                 for bound in &*bound_pred.bounds {
1258                     match bound {
1259                         &ast::TyParamBound::TraitTyParamBound(ref poly_trait_ref, _) => {
1260                             let mut projections = Vec::new();
1261
1262                             let trait_ref = astconv::instantiate_poly_trait_ref(
1263                                 ccx,
1264                                 &ExplicitRscope,
1265                                 poly_trait_ref,
1266                                 Some(ty),
1267                                 &mut projections,
1268                             );
1269
1270                             result.predicates.push(space, trait_ref.as_predicate());
1271
1272                             for projection in &projections {
1273                                 result.predicates.push(space, projection.as_predicate());
1274                             }
1275                         }
1276
1277                         &ast::TyParamBound::RegionTyParamBound(ref lifetime) => {
1278                             let region = ast_region_to_region(ccx.tcx, lifetime);
1279                             let pred = ty::Binder(ty::OutlivesPredicate(ty, region));
1280                             result.predicates.push(space, ty::Predicate::TypeOutlives(pred))
1281                         }
1282                     }
1283                 }
1284             }
1285
1286             &ast::WherePredicate::RegionPredicate(ref region_pred) => {
1287                 let r1 = ast_region_to_region(ccx.tcx, &region_pred.lifetime);
1288                 for bound in &region_pred.bounds {
1289                     let r2 = ast_region_to_region(ccx.tcx, bound);
1290                     let pred = ty::Binder(ty::OutlivesPredicate(r1, r2));
1291                     result.predicates.push(space, ty::Predicate::RegionOutlives(pred))
1292                 }
1293             }
1294
1295             &ast::WherePredicate::EqPredicate(ref eq_pred) => {
1296                 // FIXME(#20041)
1297                 ccx.tcx.sess.span_bug(eq_pred.span,
1298                                          "Equality constraints are not yet \
1299                                             implemented (#20041)")
1300             }
1301         }
1302     }
1303
1304     return result;
1305
1306     fn create_predicates<'tcx>(
1307         tcx: &ty::ctxt<'tcx>,
1308         result: &mut ty::Generics<'tcx>,
1309         space: subst::ParamSpace)
1310     {
1311         for type_param_def in result.types.get_slice(space) {
1312             let param_ty = ty::mk_param_from_def(tcx, type_param_def);
1313             for predicate in ty::predicates(tcx, param_ty, &type_param_def.bounds) {
1314                 result.predicates.push(space, predicate);
1315             }
1316         }
1317
1318         for region_param_def in result.regions.get_slice(space) {
1319             let region = region_param_def.to_early_bound_region();
1320             for &bound_region in &region_param_def.bounds {
1321                 // account for new binder introduced in the predicate below; no need
1322                 // to shift `region` because it is never a late-bound region
1323                 let bound_region = ty_fold::shift_region(bound_region, 1);
1324                 result.predicates.push(
1325                     space,
1326                     ty::Binder(ty::OutlivesPredicate(region, bound_region)).as_predicate());
1327             }
1328         }
1329     }
1330 }
1331
1332 fn get_or_create_type_parameter_def<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1333                                              space: subst::ParamSpace,
1334                                              param: &ast::TyParam,
1335                                              index: u32)
1336                                              -> ty::TypeParameterDef<'tcx>
1337 {
1338     match ccx.tcx.ty_param_defs.borrow().get(&param.id) {
1339         Some(d) => { return (*d).clone(); }
1340         None => { }
1341     }
1342
1343     let param_ty = ty::ParamTy::new(space, index, param.ident.name);
1344     let bounds = compute_bounds(ccx,
1345                                 param_ty.to_ty(ccx.tcx),
1346                                 &param.bounds[],
1347                                 SizedByDefault::Yes,
1348                                 param.span);
1349     let default = match param.default {
1350         None => None,
1351         Some(ref path) => {
1352             let ty = ast_ty_to_ty(ccx, &ExplicitRscope, &**path);
1353             let cur_idx = index;
1354
1355             ty::walk_ty(ty, |t| {
1356                 match t.sty {
1357                     ty::ty_param(p) => if p.idx > cur_idx {
1358                         span_err!(ccx.tcx.sess, path.span, E0128,
1359                                   "type parameters with a default cannot use \
1360                                    forward declared identifiers");
1361                         },
1362                         _ => {}
1363                     }
1364             });
1365
1366             Some(ty)
1367         }
1368     };
1369
1370     let def = ty::TypeParameterDef {
1371         space: space,
1372         index: index,
1373         name: param.ident.name,
1374         def_id: local_def(param.id),
1375         bounds: bounds,
1376         default: default
1377     };
1378
1379     ccx.tcx.ty_param_defs.borrow_mut().insert(param.id, def.clone());
1380
1381     def
1382 }
1383
1384 enum SizedByDefault { Yes, No }
1385
1386 /// Translate the AST's notion of ty param bounds (which are an enum consisting of a newtyped Ty or
1387 /// a region) to ty's notion of ty param bounds, which can either be user-defined traits, or the
1388 /// built-in trait (formerly known as kind): Send.
1389 fn compute_bounds<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1390                            param_ty: ty::Ty<'tcx>,
1391                            ast_bounds: &[ast::TyParamBound],
1392                            sized_by_default: SizedByDefault,
1393                            span: Span)
1394                            -> ty::ParamBounds<'tcx>
1395 {
1396     let mut param_bounds = conv_param_bounds(ccx,
1397                                              span,
1398                                              param_ty,
1399                                              ast_bounds);
1400
1401     if let SizedByDefault::Yes = sized_by_default {
1402         add_unsized_bound(ccx,
1403                           &mut param_bounds.builtin_bounds,
1404                           ast_bounds,
1405                           span);
1406
1407         check_bounds_compatible(ccx.tcx,
1408                                 param_ty,
1409                                 &param_bounds,
1410                                 span);
1411     }
1412
1413     param_bounds.trait_bounds.sort_by(|a,b| a.def_id().cmp(&b.def_id()));
1414
1415     param_bounds
1416 }
1417
1418 fn check_bounds_compatible<'tcx>(tcx: &ty::ctxt<'tcx>,
1419                                  param_ty: Ty<'tcx>,
1420                                  param_bounds: &ty::ParamBounds<'tcx>,
1421                                  span: Span) {
1422     // Currently the only bound which is incompatible with other bounds is
1423     // Sized/Unsized.
1424     if !param_bounds.builtin_bounds.contains(&ty::BoundSized) {
1425         ty::each_bound_trait_and_supertraits(
1426             tcx,
1427             &param_bounds.trait_bounds[],
1428             |trait_ref| {
1429                 let trait_def = ty::lookup_trait_def(tcx, trait_ref.def_id());
1430                 if trait_def.bounds.builtin_bounds.contains(&ty::BoundSized) {
1431                     span_err!(tcx.sess, span, E0129,
1432                               "incompatible bounds on `{}`, \
1433                                bound `{}` does not allow unsized type",
1434                               param_ty.user_string(tcx),
1435                               trait_ref.user_string(tcx));
1436                 }
1437                 true
1438             });
1439     }
1440 }
1441
1442 fn conv_param_bounds<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1443                               span: Span,
1444                               param_ty: ty::Ty<'tcx>,
1445                               ast_bounds: &[ast::TyParamBound])
1446                               -> ty::ParamBounds<'tcx>
1447 {
1448     let astconv::PartitionedBounds { builtin_bounds,
1449                                      trait_bounds,
1450                                      region_bounds } =
1451         astconv::partition_bounds(ccx.tcx, span, ast_bounds.as_slice());
1452
1453     let mut projection_bounds = Vec::new();
1454
1455     let trait_bounds: Vec<ty::PolyTraitRef> =
1456         trait_bounds.into_iter()
1457         .map(|bound| {
1458             astconv::instantiate_poly_trait_ref(ccx,
1459                                                 &ExplicitRscope,
1460                                                 bound,
1461                                                 Some(param_ty),
1462                                                 &mut projection_bounds)
1463         })
1464         .collect();
1465     let region_bounds: Vec<ty::Region> =
1466         region_bounds.into_iter()
1467         .map(|r| ast_region_to_region(ccx.tcx, r))
1468         .collect();
1469     ty::ParamBounds {
1470         region_bounds: region_bounds,
1471         builtin_bounds: builtin_bounds,
1472         trait_bounds: trait_bounds,
1473         projection_bounds: projection_bounds,
1474     }
1475 }
1476
1477 fn ty_of_foreign_fn_decl<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
1478                                        decl: &ast::FnDecl,
1479                                        def_id: ast::DefId,
1480                                        ast_generics: &ast::Generics,
1481                                        abi: abi::Abi)
1482                                        -> ty::TypeScheme<'tcx> {
1483     for i in &decl.inputs {
1484         match (*i).pat.node {
1485             ast::PatIdent(_, _, _) => (),
1486             ast::PatWild(ast::PatWildSingle) => (),
1487             _ => {
1488                 span_err!(ccx.tcx.sess, (*i).pat.span, E0130,
1489                           "patterns aren't allowed in foreign function declarations");
1490             }
1491         }
1492     }
1493
1494     let ty_generics_for_fn_or_method = ty_generics_for_fn_or_method(ccx,
1495                                                                     ast_generics,
1496                                                                     ty::Generics::empty());
1497     let rb = BindingRscope::new();
1498     let input_tys = decl.inputs
1499                         .iter()
1500                         .map(|a| ty_of_arg(ccx, &rb, a, None))
1501                         .collect();
1502
1503     let output = match decl.output {
1504         ast::Return(ref ty) =>
1505             ty::FnConverging(ast_ty_to_ty(ccx, &rb, &**ty)),
1506         ast::DefaultReturn(..) =>
1507             ty::FnConverging(ty::mk_nil(ccx.tcx)),
1508         ast::NoReturn(..) =>
1509             ty::FnDiverging
1510     };
1511
1512     let t_fn = ty::mk_bare_fn(
1513         ccx.tcx,
1514         None,
1515         ccx.tcx.mk_bare_fn(ty::BareFnTy {
1516             abi: abi,
1517             unsafety: ast::Unsafety::Unsafe,
1518             sig: ty::Binder(ty::FnSig {inputs: input_tys,
1519                                        output: output,
1520                                        variadic: decl.variadic}),
1521         }));
1522     let scheme = TypeScheme {
1523         generics: ty_generics_for_fn_or_method,
1524         ty: t_fn
1525     };
1526
1527     ccx.tcx.tcache.borrow_mut().insert(def_id, scheme.clone());
1528     return scheme;
1529 }
1530
1531 fn mk_item_substs<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
1532                             ty_generics: &ty::Generics<'tcx>)
1533                             -> subst::Substs<'tcx>
1534 {
1535     let types =
1536         ty_generics.types.map(
1537             |def| ty::mk_param_from_def(ccx.tcx, def));
1538
1539     let regions =
1540         ty_generics.regions.map(
1541             |def| def.to_early_bound_region());
1542
1543     subst::Substs::new(types, regions)
1544 }
1545
1546 /// Verifies that the explicit self type of a method matches the impl
1547 /// or trait. This is a bit weird but basically because right now we
1548 /// don't handle the general case, but instead map it to one of
1549 /// several pre-defined options using various heuristics, this method
1550 /// comes back to check after the fact that explicit type the user
1551 /// wrote actually matches what the pre-defined option said.
1552 fn check_method_self_type<'a, 'tcx, RS:RegionScope>(
1553     ccx: &CollectCtxt<'a, 'tcx>,
1554     rs: &RS,
1555     required_type: Ty<'tcx>,
1556     explicit_self: &ast::ExplicitSelf,
1557     body_id: ast::NodeId)
1558 {
1559     if let ast::SelfExplicit(ref ast_type, _) = explicit_self.node {
1560         let typ = ccx.to_ty(rs, &**ast_type);
1561         let base_type = match typ.sty {
1562             ty::ty_ptr(tm) | ty::ty_rptr(_, tm) => tm.ty,
1563             ty::ty_uniq(typ) => typ,
1564             _ => typ,
1565         };
1566
1567         let body_scope = region::CodeExtent::from_node_id(body_id);
1568
1569         // "Required type" comes from the trait definition. It may
1570         // contain late-bound regions from the method, but not the
1571         // trait (since traits only have early-bound region
1572         // parameters).
1573         assert!(!base_type.has_regions_escaping_depth(1));
1574         let required_type_free =
1575             liberate_early_bound_regions(
1576                 ccx.tcx, body_scope,
1577                 &ty::liberate_late_bound_regions(
1578                     ccx.tcx, body_scope, &ty::Binder(required_type)));
1579
1580         // The "base type" comes from the impl. It too may have late-bound
1581         // regions from the method.
1582         assert!(!base_type.has_regions_escaping_depth(1));
1583         let base_type_free =
1584             liberate_early_bound_regions(
1585                 ccx.tcx, body_scope,
1586                 &ty::liberate_late_bound_regions(
1587                     ccx.tcx, body_scope, &ty::Binder(base_type)));
1588
1589         debug!("required_type={} required_type_free={} \
1590                 base_type={} base_type_free={}",
1591                required_type.repr(ccx.tcx),
1592                required_type_free.repr(ccx.tcx),
1593                base_type.repr(ccx.tcx),
1594                base_type_free.repr(ccx.tcx));
1595         let infcx = infer::new_infer_ctxt(ccx.tcx);
1596         drop(::require_same_types(ccx.tcx,
1597                                   Some(&infcx),
1598                                   false,
1599                                   explicit_self.span,
1600                                   base_type_free,
1601                                   required_type_free,
1602                                   || {
1603                 format!("mismatched self type: expected `{}`",
1604                         ppaux::ty_to_string(ccx.tcx, required_type))
1605         }));
1606         infcx.resolve_regions_and_report_errors(body_id);
1607     }
1608
1609     fn liberate_early_bound_regions<'tcx,T>(
1610         tcx: &ty::ctxt<'tcx>,
1611         scope: region::CodeExtent,
1612         value: &T)
1613         -> T
1614         where T : TypeFoldable<'tcx> + Repr<'tcx>
1615     {
1616         /*!
1617          * Convert early-bound regions into free regions; normally this is done by
1618          * applying the `free_substs` from the `ParameterEnvironment`, but this particular
1619          * method-self-type check is kind of hacky and done very early in the process,
1620          * before we really have a `ParameterEnvironment` to check.
1621          */
1622
1623         ty_fold::fold_regions(tcx, value, |region, _| {
1624             match region {
1625                 ty::ReEarlyBound(id, _, _, name) => {
1626                     let def_id = local_def(id);
1627                     ty::ReFree(ty::FreeRegion { scope: scope,
1628                                                 bound_region: ty::BrNamed(def_id, name) })
1629                 }
1630                 _ => region
1631             }
1632         })
1633     }
1634 }
1635
1636 /// Checks that all the type parameters on an impl
1637 fn enforce_impl_ty_params_are_constrained<'tcx>(tcx: &ty::ctxt<'tcx>,
1638                                                 ast_generics: &ast::Generics,
1639                                                 impl_def_id: ast::DefId)
1640 {
1641     let impl_scheme = ty::lookup_item_type(tcx, impl_def_id);
1642     let impl_trait_ref = ty::impl_trait_ref(tcx, impl_def_id);
1643
1644     // The trait reference is an input, so find all type parameters
1645     // reachable from there, to start (if this is an inherent impl,
1646     // then just examine the self type).
1647     let mut input_parameters: HashSet<_> =
1648         impl_trait_ref.iter()
1649                       .flat_map(|t| t.input_types().iter()) // Types in trait ref, if any
1650                       .chain(Some(impl_scheme.ty).iter())  // Self type, always
1651                       .flat_map(|t| t.walk())
1652                       .filter_map(to_opt_param_ty)
1653                       .collect();
1654
1655     loop {
1656         let num_inputs = input_parameters.len();
1657
1658         let mut projection_predicates =
1659             impl_scheme.generics.predicates
1660             .iter()
1661             .filter_map(|predicate| {
1662                 match *predicate {
1663                     // Ignore higher-ranked binders. For the purposes
1664                     // of this check, they don't matter because they
1665                     // only affect named regions, and we're just
1666                     // concerned about type parameters here.
1667                     ty::Predicate::Projection(ref data) => Some(data.0.clone()),
1668                     _ => None,
1669                 }
1670             });
1671
1672         for projection in projection_predicates {
1673             // Special case: watch out for some kind of sneaky attempt
1674             // to project out an associated type defined by this very trait.
1675             if Some(projection.projection_ty.trait_ref.clone()) == impl_trait_ref {
1676                 continue;
1677             }
1678
1679             let relies_only_on_inputs =
1680                 projection.projection_ty.trait_ref.input_types().iter()
1681                 .flat_map(|t| t.walk())
1682                 .filter_map(to_opt_param_ty)
1683                 .all(|t| input_parameters.contains(&t));
1684
1685             if relies_only_on_inputs {
1686                 input_parameters.extend(
1687                     projection.ty.walk().filter_map(to_opt_param_ty));
1688             }
1689         }
1690
1691         if input_parameters.len() == num_inputs {
1692             break;
1693         }
1694     }
1695
1696     for (index, ty_param) in ast_generics.ty_params.iter().enumerate() {
1697         let param_ty = ty::ParamTy { space: TypeSpace,
1698                                      idx: index as u32,
1699                                      name: ty_param.ident.name };
1700         if !input_parameters.contains(&param_ty) {
1701             if ty::has_attr(tcx, impl_def_id, "old_impl_check") {
1702                 tcx.sess.span_warn(
1703                     ty_param.span,
1704                     format!("the type parameter `{}` is not constrained by the \
1705                              impl trait, self type, or predicates",
1706                             param_ty.user_string(tcx)).as_slice());
1707             } else {
1708                 span_err!(tcx.sess, ty_param.span, E0207,
1709                     "the type parameter `{}` is not constrained by the \
1710                              impl trait, self type, or predicates",
1711                             param_ty.user_string(tcx));
1712                 tcx.sess.span_help(
1713                     ty_param.span,
1714                     format!("you can temporarily opt out of this rule by placing \
1715                              the `#[old_impl_check]` attribute on the impl").as_slice());
1716             }
1717         }
1718     }
1719
1720     fn to_opt_param_ty<'tcx>(ty: Ty<'tcx>) -> Option<ty::ParamTy> {
1721         match ty.sty {
1722             ty::ty_param(ref d) => Some(d.clone()),
1723             _ => None,
1724         }
1725     }
1726 }