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.iter() {
 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.iter() {
 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.iter() {
 531         for bound in ty_param.bounds.iter() {
 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::ItemForeignMod(_) | ast::ItemMod(_) | ast::ItemMac(_) => {}
 559         ast::ItemEnum(ref enum_definition, ref generics) => {
 560             let scheme = ty_of_item(ccx, it);
 561             write_ty_to_tcx(tcx, it.id, scheme.ty);
 562             get_enum_variant_types(ccx,
 563                                    scheme.ty,
 564                                    enum_definition.variants.as_slice(),
 565                                    generics);
 566         },
 567         ast::ItemImpl(_, _,
 568                       ref generics,
 569                       ref opt_trait_ref,
 570                       ref selfty,
 571                       ref impl_items) => {
 572             // Create generics from the generics specified in the impl head.
 573             let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
 574
 575             let selfty = ccx.to_ty(&ExplicitRscope, &**selfty);
 576             write_ty_to_tcx(tcx, it.id, selfty);
 577
 578             tcx.tcache
 579                .borrow_mut()
 580                .insert(local_def(it.id),
 581                        TypeScheme {
 582                         generics: ty_generics.clone(),
 583                         ty: selfty,
 584                        });
 585
 586             // If there is a trait reference, treat the methods as always public.
 587             // This is to work around some incorrect behavior in privacy checking:
 588             // when the method belongs to a trait, it should acquire the privacy
 589             // from the trait, not the impl. Forcing the visibility to be public
 590             // makes things sorta work.
 591             let parent_visibility = if opt_trait_ref.is_some() {
 592                 ast::Public
 593             } else {
 594                 it.vis
 595             };
 596
 597             let mut methods = Vec::new();
 598             for impl_item in impl_items.iter() {
 599                 match *impl_item {
 600                     ast::MethodImplItem(ref method) => {
 601                         let body_id = method.pe_body().id;
 602                         check_method_self_type(ccx,
 603                                                &BindingRscope::new(),
 604                                                selfty,
 605                                                method.pe_explicit_self(),
 606                                                body_id);
 607                         methods.push(&**method);
 608                     }
 609                     ast::TypeImplItem(ref typedef) => {
 610                         if opt_trait_ref.is_none() {
 611                             span_err!(tcx.sess, typedef.span, E0202,
 612                                               "associated items are not allowed in inherent impls");
 613                         }
 614
 615                         let typ = ccx.to_ty(&ExplicitRscope, &*typedef.typ);
 616                         tcx.tcache
 617                            .borrow_mut()
 618                            .insert(local_def(typedef.id),
 619                                    TypeScheme {
 620                                     generics: ty::Generics::empty(),
 621                                     ty: typ,
 622                                    });
 623                         write_ty_to_tcx(ccx.tcx, typedef.id, typ);
 624
 625                         let associated_type = Rc::new(ty::AssociatedType {
 626                             name: typedef.ident.name,
 627                             vis: typedef.vis,
 628                             def_id: local_def(typedef.id),
 629                             container: ty::ImplContainer(local_def(it.id)),
 630                         });
 631                         tcx.impl_or_trait_items
 632                            .borrow_mut()
 633                            .insert(local_def(typedef.id),
 634                                    ty::TypeTraitItem(associated_type));
 635                     }
 636                 }
 637             }
 638
 639             convert_methods(ccx,
 640                             ImplContainer(local_def(it.id)),
 641                             methods.into_iter(),
 642                             selfty,
 643                             &ty_generics,
 644                             parent_visibility);
 645
 646             for trait_ref in opt_trait_ref.iter() {
 647                 astconv::instantiate_trait_ref(ccx,
 648                                                &ExplicitRscope,
 649                                                trait_ref,
 650                                                Some(selfty),
 651                                                None);
 652             }
 653
 654             enforce_impl_ty_params_are_constrained(ccx.tcx,
 655                                                    generics,
 656                                                    local_def(it.id));
 657         },
 658         ast::ItemTrait(_, _, _, ref trait_methods) => {
 659             let trait_def = trait_def_of_item(ccx, it);
 660
 661             debug!("trait_def: ident={} trait_def={}",
 662                    it.ident.repr(ccx.tcx),
 663                    trait_def.repr(ccx.tcx));
 664
 665             for trait_method in trait_methods.iter() {
 666                 let self_type = ty::mk_self_type(tcx);
 667                 match *trait_method {
 668                     ast::RequiredMethod(ref type_method) => {
 669                         let rscope = BindingRscope::new();
 670                         check_method_self_type(ccx,
 671                                                &rscope,
 672                                                self_type,
 673                                                &type_method.explicit_self,
 674                                                it.id)
 675                     }
 676                     ast::ProvidedMethod(ref method) => {
 677                         check_method_self_type(ccx,
 678                                                &BindingRscope::new(),
 679                                                self_type,
 680                                                method.pe_explicit_self(),
 681                                                it.id)
 682                     }
 683                     ast::TypeTraitItem(ref associated_type) => {
 684                         convert_associated_type(ccx,
 685                                                 &*trait_def,
 686                                                 &**associated_type);
 687                     }
 688                 }
 689             }
 690
 691             // Run convert_methods on the provided methods.
 692             let untransformed_rcvr_ty = ty::mk_self_type(tcx);
 693             convert_methods(ccx,
 694                             TraitContainer(local_def(it.id)),
 695                             trait_methods.iter().filter_map(|m| match *m {
 696                                 ast::RequiredMethod(_) => None,
 697                                 ast::ProvidedMethod(ref m) => Some(&**m),
 698                                 ast::TypeTraitItem(_) => None,
 699                             }),
 700                             untransformed_rcvr_ty,
 701                             &trait_def.generics,
 702                             it.vis);
 703
 704             // We need to do this *after* converting methods, since
 705             // convert_methods produces a tcache entry that is wrong for
 706             // static trait methods. This is somewhat unfortunate.
 707             collect_trait_methods(ccx, it.id, &*trait_def);
 708         },
 709         ast::ItemStruct(ref struct_def, _) => {
 710             // Write the class type.
 711             let scheme = ty_of_item(ccx, it);
 712             write_ty_to_tcx(tcx, it.id, scheme.ty);
 713
 714             tcx.tcache.borrow_mut().insert(local_def(it.id), scheme.clone());
 715
 716             convert_struct(ccx, &**struct_def, scheme, it.id);
 717         },
 718         ast::ItemTy(_, ref generics) => {
 719             ensure_no_ty_param_bounds(ccx, it.span, generics, "type");
 720             let tpt = ty_of_item(ccx, it);
 721             write_ty_to_tcx(tcx, it.id, tpt.ty);
 722         },
 723         _ => {
 724             // This call populates the type cache with the converted type
 725             // of the item in passing. All we have to do here is to write
 726             // it into the node type table.
 727             let scheme = ty_of_item(ccx, it);
 728             write_ty_to_tcx(tcx, it.id, scheme.ty);
 729         },
 730     }
 731 }
 732
 733 fn convert_struct<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 734                                 struct_def: &ast::StructDef,
 735                                 scheme: ty::TypeScheme<'tcx>,
 736                                 id: ast::NodeId) {
 737     let tcx = ccx.tcx;
 738
 739     // Write the type of each of the members and check for duplicate fields.
 740     let mut seen_fields: FnvHashMap<ast::Name, Span> = FnvHashMap();
 741     let field_tys = struct_def.fields.iter().map(|f| {
 742         let result = convert_field(ccx, &scheme.generics, f, local_def(id));
 743
 744         if result.name != special_idents::unnamed_field.name {
 745             let dup = match seen_fields.get(&result.name) {
 746                 Some(prev_span) => {
 747                     span_err!(tcx.sess, f.span, E0124,
 748                               "field `{}` is already declared",
 749                               token::get_name(result.name));
 750                     span_note!(tcx.sess, *prev_span, "previously declared here");
 751                     true
 752                 },
 753                 None => false,
 754             };
 755             // FIXME(#6393) this whole dup thing is just to satisfy
 756             // the borrow checker :-(
 757             if !dup {
 758                 seen_fields.insert(result.name, f.span);
 759             }
 760         }
 761
 762         result
 763     }).collect();
 764
 765     tcx.struct_fields.borrow_mut().insert(local_def(id), Rc::new(field_tys));
 766
 767     let substs = mk_item_substs(ccx, &scheme.generics);
 768     let selfty = ty::mk_struct(tcx, local_def(id), tcx.mk_substs(substs));
 769
 770     // If this struct is enum-like or tuple-like, create the type of its
 771     // constructor.
 772     match struct_def.ctor_id {
 773         None => {}
 774         Some(ctor_id) => {
 775             if struct_def.fields.len() == 0 {
 776                 // Enum-like.
 777                 write_ty_to_tcx(tcx, ctor_id, selfty);
 778
 779                 tcx.tcache.borrow_mut().insert(local_def(ctor_id), scheme);
 780             } else if struct_def.fields[0].node.kind.is_unnamed() {
 781                 // Tuple-like.
 782                 let inputs: Vec<_> = struct_def.fields.iter().map(
 783                         |field| (*tcx.tcache.borrow())[
 784                             local_def(field.node.id)].ty).collect();
 785                 let ctor_fn_ty = ty::mk_ctor_fn(tcx,
 786                                                 local_def(ctor_id),
 787                                                 &inputs[],
 788                                                 selfty);
 789                 write_ty_to_tcx(tcx, ctor_id, ctor_fn_ty);
 790                 tcx.tcache.borrow_mut().insert(local_def(ctor_id),
 791                                   TypeScheme {
 792                     generics: scheme.generics,
 793                     ty: ctor_fn_ty
 794                 });
 795             }
 796         }
 797     }
 798 }
 799
 800 fn convert_foreign(ccx: &CollectCtxt, i: &ast::ForeignItem) {
 801     // As above, this call populates the type table with the converted
 802     // type of the foreign item. We simply write it into the node type
 803     // table.
 804
 805     // For reasons I cannot fully articulate, I do so hate the AST
 806     // map, and I regard each time that I use it as a personal and
 807     // moral failing, but at the moment it seems like the only
 808     // convenient way to extract the ABI. - ndm
 809     let abi = ccx.tcx.map.get_foreign_abi(i.id);
 810
 811     let scheme = ty_of_foreign_item(ccx, i, abi);
 812     write_ty_to_tcx(ccx.tcx, i.id, scheme.ty);
 813
 814     ccx.tcx.tcache.borrow_mut().insert(local_def(i.id), scheme);
 815 }
 816
 817 fn get_trait_def<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 818                            trait_id: ast::DefId)
 819                            -> Rc<ty::TraitDef<'tcx>> {
 820     if trait_id.krate != ast::LOCAL_CRATE {
 821         return ty::lookup_trait_def(ccx.tcx, trait_id)
 822     }
 823
 824     match ccx.tcx.map.get(trait_id.node) {
 825         ast_map::NodeItem(item) => trait_def_of_item(ccx, &*item),
 826         _ => {
 827             ccx.tcx.sess.bug(&format!("get_trait_def({}): not an item",
 828                                      trait_id.node)[])
 829         }
 830     }
 831 }
 832
 833 fn trait_def_of_item<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 834                                it: &ast::Item)
 835                                -> Rc<ty::TraitDef<'tcx>>
 836 {
 837     let def_id = local_def(it.id);
 838     let tcx = ccx.tcx;
 839     if let Some(def) = tcx.trait_defs.borrow().get(&def_id) {
 840         return def.clone();
 841     }
 842
 843     let (unsafety, generics, bounds, items) = match it.node {
 844         ast::ItemTrait(unsafety,
 845                        ref generics,
 846                        ref supertraits,
 847                        ref items) => {
 848             (unsafety, generics, supertraits, items.as_slice())
 849         }
 850         ref s => {
 851             tcx.sess.span_bug(
 852                 it.span,
 853                 &format!("trait_def_of_item invoked on {:?}", s)[]);
 854         }
 855     };
 856
 857     let substs = ccx.tcx.mk_substs(mk_trait_substs(ccx, generics));
 858
 859     let ty_generics = ty_generics_for_trait(ccx,
 860                                             it.id,
 861                                             substs,
 862                                             generics,
 863                                             items);
 864
 865     let self_param_ty = ty::ParamTy::for_self();
 866
 867     let bounds = compute_bounds(ccx,
 868                                 self_param_ty.to_ty(ccx.tcx),
 869                                 bounds.as_slice(),
 870                                 SizedByDefault::No,
 871                                 it.span);
 872
 873     let associated_type_names: Vec<_> =
 874         items.iter()
 875              .filter_map(|item| {
 876                  match *item {
 877                      ast::RequiredMethod(_) | ast::ProvidedMethod(_) => None,
 878                      ast::TypeTraitItem(ref data) => Some(data.ty_param.ident.name),
 879                  }
 880              })
 881             .collect();
 882
 883     let trait_ref = Rc::new(ty::TraitRef {
 884         def_id: def_id,
 885         substs: substs
 886     });
 887
 888     let trait_def = Rc::new(ty::TraitDef {
 889         unsafety: unsafety,
 890         generics: ty_generics,
 891         bounds: bounds,
 892         trait_ref: trait_ref,
 893         associated_type_names: associated_type_names,
 894     });
 895     tcx.trait_defs.borrow_mut().insert(def_id, trait_def.clone());
 896
 897     return trait_def;
 898
 899     fn mk_trait_substs<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 900                                  generics: &ast::Generics)
 901                                  -> subst::Substs<'tcx>
 902     {
 903         // Creates a no-op substitution for the trait's type parameters.
 904         let regions =
 905             generics.lifetimes
 906                     .iter()
 907                     .enumerate()
 908                     .map(|(i, def)| ty::ReEarlyBound(def.lifetime.id,
 909                                                      subst::TypeSpace,
 910                                                      i as u32,
 911                                                      def.lifetime.name))
 912                     .collect();
 913
 914         // Start with the generics in the type parameters...
 915         let types: Vec<_> =
 916             generics.ty_params
 917                     .iter()
 918                     .enumerate()
 919                     .map(|(i, def)| ty::mk_param(ccx.tcx, subst::TypeSpace,
 920                                                  i as u32, def.ident.name))
 921                     .collect();
 922
 923         // ...and also create the `Self` parameter.
 924         let self_ty = ty::mk_self_type(ccx.tcx);
 925
 926         subst::Substs::new_trait(types, regions, self_ty)
 927     }
 928 }
 929
 930 fn ty_of_item<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>, it: &ast::Item)
 931                             -> ty::TypeScheme<'tcx> {
 932     let def_id = local_def(it.id);
 933     let tcx = ccx.tcx;
 934     if let Some(scheme) = tcx.tcache.borrow().get(&def_id) {
 935         return scheme.clone();
 936     }
 937     match it.node {
 938         ast::ItemStatic(ref t, _, _) | ast::ItemConst(ref t, _) => {
 939             let typ = ccx.to_ty(&ExplicitRscope, &**t);
 940             let scheme = no_params(typ);
 941
 942             tcx.tcache.borrow_mut().insert(local_def(it.id), scheme.clone());
 943             return scheme;
 944         }
 945         ast::ItemFn(ref decl, unsafety, abi, ref generics, _) => {
 946             let ty_generics = ty_generics_for_fn_or_method(ccx,
 947                                                            generics,
 948                                                            ty::Generics::empty());
 949             let tofd = astconv::ty_of_bare_fn(ccx, unsafety, abi, &**decl);
 950             let scheme = TypeScheme {
 951                 generics: ty_generics,
 952                 ty: ty::mk_bare_fn(ccx.tcx, Some(local_def(it.id)), ccx.tcx.mk_bare_fn(tofd))
 953             };
 954             debug!("type of {} (id {}) is {}",
 955                     token::get_ident(it.ident),
 956                     it.id,
 957                     scheme.repr(tcx));
 958
 959             ccx.tcx.tcache.borrow_mut().insert(local_def(it.id), scheme.clone());
 960             return scheme;
 961         }
 962         ast::ItemTy(ref t, ref generics) => {
 963             match tcx.tcache.borrow_mut().get(&local_def(it.id)) {
 964                 Some(scheme) => return scheme.clone(),
 965                 None => { }
 966             }
 967
 968             let scheme = {
 969                 let ty = ccx.to_ty(&ExplicitRscope, &**t);
 970                 TypeScheme {
 971                     generics: ty_generics_for_type_or_impl(ccx, generics),
 972                     ty: ty
 973                 }
 974             };
 975
 976             tcx.tcache.borrow_mut().insert(local_def(it.id), scheme.clone());
 977             return scheme;
 978         }
 979         ast::ItemEnum(_, ref generics) => {
 980             // Create a new generic polytype.
 981             let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
 982             let substs = mk_item_substs(ccx, &ty_generics);
 983             let t = ty::mk_enum(tcx, local_def(it.id), tcx.mk_substs(substs));
 984             let scheme = TypeScheme {
 985                 generics: ty_generics,
 986                 ty: t
 987             };
 988
 989             tcx.tcache.borrow_mut().insert(local_def(it.id), scheme.clone());
 990             return scheme;
 991         }
 992         ast::ItemTrait(..) => {
 993             tcx.sess.span_bug(it.span, "invoked ty_of_item on trait");
 994         }
 995         ast::ItemStruct(_, ref generics) => {
 996             let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
 997             let substs = mk_item_substs(ccx, &ty_generics);
 998             let t = ty::mk_struct(tcx, local_def(it.id), tcx.mk_substs(substs));
 999             let scheme = TypeScheme {
1000                 generics: ty_generics,
1001                 ty: t
1002             };
1003
1004             tcx.tcache.borrow_mut().insert(local_def(it.id), scheme.clone());
1005             return scheme;
1006         }
1007         ast::ItemImpl(..) | ast::ItemMod(_) |
1008         ast::ItemForeignMod(_) | ast::ItemMac(_) => panic!(),
1009     }
1010 }
1011
1012 fn ty_of_foreign_item<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
1013                                     it: &ast::ForeignItem,
1014                                     abi: abi::Abi) -> ty::TypeScheme<'tcx>
1015 {
1016     match it.node {
1017         ast::ForeignItemFn(ref fn_decl, ref generics) => {
1018             ty_of_foreign_fn_decl(ccx,
1019                                   &**fn_decl,
1020                                   local_def(it.id),
1021                                   generics,
1022                                   abi)
1023         }
1024         ast::ForeignItemStatic(ref t, _) => {
1025             ty::TypeScheme {
1026                 generics: ty::Generics::empty(),
1027                 ty: ast_ty_to_ty(ccx, &ExplicitRscope, &**t)
1028             }
1029         }
1030     }
1031 }
1032
1033 fn ty_generics_for_type_or_impl<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
1034                                           generics: &ast::Generics)
1035                                           -> ty::Generics<'tcx> {
1036     ty_generics(ccx,
1037                 subst::TypeSpace,
1038                 &generics.lifetimes[],
1039                 &generics.ty_params[],
1040                 ty::Generics::empty(),
1041                 &generics.where_clause)
1042 }
1043
1044 fn ty_generics_for_trait<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
1045                                    trait_id: ast::NodeId,
1046                                    substs: &'tcx subst::Substs<'tcx>,
1047                                    ast_generics: &ast::Generics,
1048                                    trait_items: &[ast::TraitItem])
1049                                    -> ty::Generics<'tcx>
1050 {
1051     debug!("ty_generics_for_trait(trait_id={}, substs={})",
1052            local_def(trait_id).repr(ccx.tcx), substs.repr(ccx.tcx));
1053
1054     let mut generics =
1055         ty_generics(ccx,
1056                     subst::TypeSpace,
1057                     &ast_generics.lifetimes[],
1058                     &ast_generics.ty_params[],
1059                     ty::Generics::empty(),
1060                     &ast_generics.where_clause);
1061
1062     // Add in the self type parameter.
1063     //
1064     // Something of a hack: use the node id for the trait, also as
1065     // the node id for the Self type parameter.
1066     let param_id = trait_id;
1067
1068     let self_trait_ref =
1069         Rc::new(ty::TraitRef { def_id: local_def(trait_id),
1070                                substs: substs });
1071
1072     let def = ty::TypeParameterDef {
1073         space: subst::SelfSpace,
1074         index: 0,
1075         name: special_idents::type_self.name,
1076         def_id: local_def(param_id),
1077         bounds: ty::ParamBounds {
1078             region_bounds: vec!(),
1079             builtin_bounds: ty::empty_builtin_bounds(),
1080             trait_bounds: vec!(ty::Binder(self_trait_ref.clone())),
1081             projection_bounds: vec!(),
1082         },
1083         default: None
1084     };
1085
1086     ccx.tcx.ty_param_defs.borrow_mut().insert(param_id, def.clone());
1087
1088     generics.types.push(subst::SelfSpace, def);
1089
1090     generics.predicates.push(subst::SelfSpace, self_trait_ref.as_predicate());
1091
1092     let assoc_predicates = predicates_for_associated_types(ccx,
1093                                                            &self_trait_ref,
1094                                                            trait_items);
1095
1096     debug!("ty_generics_for_trait: assoc_predicates={}", assoc_predicates.repr(ccx.tcx));
1097
1098     for assoc_predicate in assoc_predicates.into_iter() {
1099         generics.predicates.push(subst::TypeSpace, assoc_predicate);
1100     }
1101
1102     return generics;
1103
1104     fn predicates_for_associated_types<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
1105                                                  self_trait_ref: &Rc<ty::TraitRef<'tcx>>,
1106                                                  trait_items: &[ast::TraitItem])
1107                                                  -> Vec<ty::Predicate<'tcx>>
1108     {
1109         trait_items
1110             .iter()
1111             .flat_map(|trait_item| {
1112                 let assoc_type_def = match *trait_item {
1113                     ast::TypeTraitItem(ref assoc_type) => &assoc_type.ty_param,
1114                     ast::RequiredMethod(..) | ast::ProvidedMethod(..) => {
1115                         return vec!().into_iter();
1116                     }
1117                 };
1118
1119                 let assoc_ty = ty::mk_projection(ccx.tcx,
1120                                                  self_trait_ref.clone(),
1121                                                  assoc_type_def.ident.name);
1122
1123                 let bounds = compute_bounds(ccx,
1124                                             assoc_ty,
1125                                             assoc_type_def.bounds.as_slice(),
1126                                             SizedByDefault::Yes,
1127                                             assoc_type_def.span);
1128
1129                 ty::predicates(ccx.tcx, assoc_ty, &bounds).into_iter()
1130             })
1131             .collect()
1132     }
1133 }
1134
1135 fn ty_generics_for_fn_or_method<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1136                                          generics: &ast::Generics,
1137                                          base_generics: ty::Generics<'tcx>)
1138                                          -> ty::Generics<'tcx>
1139 {
1140     let early_lifetimes = resolve_lifetime::early_bound_lifetimes(generics);
1141     ty_generics(ccx,
1142                 subst::FnSpace,
1143                 &early_lifetimes[],
1144                 &generics.ty_params[],
1145                 base_generics,
1146                 &generics.where_clause)
1147 }
1148
1149 // Add the Sized bound, unless the type parameter is marked as `?Sized`.
1150 fn add_unsized_bound<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1151                               bounds: &mut ty::BuiltinBounds,
1152                               ast_bounds: &[ast::TyParamBound],
1153                               span: Span)
1154 {
1155     // Try to find an unbound in bounds.
1156     let mut unbound = None;
1157     for ab in ast_bounds.iter() {
1158         if let &ast::TraitTyParamBound(ref ptr, ast::TraitBoundModifier::Maybe) = ab  {
1159             if unbound.is_none() {
1160                 assert!(ptr.bound_lifetimes.is_empty());
1161                 unbound = Some(ptr.trait_ref.clone());
1162             } else {
1163                 span_err!(ccx.tcx.sess, span, E0203,
1164                           "type parameter has more than one relaxed default \
1165                                                 bound, only one is supported");
1166             }
1167         }
1168     }
1169
1170     let kind_id = ccx.tcx.lang_items.require(SizedTraitLangItem);
1171     match unbound {
1172         Some(ref tpb) => {
1173             // FIXME(#8559) currently requires the unbound to be built-in.
1174             let trait_def_id = ty::trait_ref_to_def_id(ccx.tcx, tpb);
1175             match kind_id {
1176                 Ok(kind_id) if trait_def_id != kind_id => {
1177                     ccx.tcx.sess.span_warn(span,
1178                                               "default bound relaxed for a type parameter, but \
1179                                                this does nothing because the given bound is not \
1180                                                a default. Only `?Sized` is supported");
1181                     ty::try_add_builtin_trait(ccx.tcx,
1182                                               kind_id,
1183                                               bounds);
1184                 }
1185                 _ => {}
1186             }
1187         }
1188         _ if kind_id.is_ok() => {
1189             ty::try_add_builtin_trait(ccx.tcx, kind_id.unwrap(), bounds);
1190         }
1191         // No lang item for Sized, so we can't add it as a bound.
1192         None => {}
1193     }
1194 }
1195
1196 fn ty_generics<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1197                         space: subst::ParamSpace,
1198                         lifetime_defs: &[ast::LifetimeDef],
1199                         types: &[ast::TyParam],
1200                         base_generics: ty::Generics<'tcx>,
1201                         where_clause: &ast::WhereClause)
1202                         -> ty::Generics<'tcx>
1203 {
1204     let mut result = base_generics;
1205
1206     for (i, l) in lifetime_defs.iter().enumerate() {
1207         let bounds = l.bounds.iter()
1208                              .map(|l| ast_region_to_region(ccx.tcx, l))
1209                              .collect();
1210         let def = ty::RegionParameterDef { name: l.lifetime.name,
1211                                            space: space,
1212                                            index: i as u32,
1213                                            def_id: local_def(l.lifetime.id),
1214                                            bounds: bounds };
1215         debug!("ty_generics: def for region param: {:?}", def);
1216         result.regions.push(space, def);
1217     }
1218
1219     assert!(result.types.is_empty_in(space));
1220
1221     // Now create the real type parameters.
1222     for (i, param) in types.iter().enumerate() {
1223         let def = get_or_create_type_parameter_def(ccx,
1224                                                    space,
1225                                                    param,
1226                                                    i as u32);
1227         debug!("ty_generics: def for type param: {}, {:?}",
1228                def.repr(ccx.tcx),
1229                space);
1230         result.types.push(space, def);
1231     }
1232
1233     // Just for fun, also push the bounds from the type parameters
1234     // into the predicates list. This is currently kind of non-DRY.
1235     create_predicates(ccx.tcx, &mut result, space);
1236
1237     // Add the bounds not associated with a type parameter
1238     for predicate in where_clause.predicates.iter() {
1239         match predicate {
1240             &ast::WherePredicate::BoundPredicate(ref bound_pred) => {
1241                 let ty = ast_ty_to_ty(ccx, &ExplicitRscope, &*bound_pred.bounded_ty);
1242
1243                 for bound in bound_pred.bounds.iter() {
1244                     match bound {
1245                         &ast::TyParamBound::TraitTyParamBound(ref poly_trait_ref, _) => {
1246                             let mut projections = Vec::new();
1247
1248                             let trait_ref = astconv::instantiate_poly_trait_ref(
1249                                 ccx,
1250                                 &ExplicitRscope,
1251                                 poly_trait_ref,
1252                                 Some(ty),
1253                                 &mut projections,
1254                             );
1255
1256                             result.predicates.push(space, trait_ref.as_predicate());
1257
1258                             for projection in projections.iter() {
1259                                 result.predicates.push(space, projection.as_predicate());
1260                             }
1261                         }
1262
1263                         &ast::TyParamBound::RegionTyParamBound(ref lifetime) => {
1264                             let region = ast_region_to_region(ccx.tcx, lifetime);
1265                             let pred = ty::Binder(ty::OutlivesPredicate(ty, region));
1266                             result.predicates.push(space, ty::Predicate::TypeOutlives(pred))
1267                         }
1268                     }
1269                 }
1270             }
1271
1272             &ast::WherePredicate::RegionPredicate(ref region_pred) => {
1273                 let r1 = ast_region_to_region(ccx.tcx, &region_pred.lifetime);
1274                 for bound in region_pred.bounds.iter() {
1275                     let r2 = ast_region_to_region(ccx.tcx, bound);
1276                     let pred = ty::Binder(ty::OutlivesPredicate(r1, r2));
1277                     result.predicates.push(space, ty::Predicate::RegionOutlives(pred))
1278                 }
1279             }
1280
1281             &ast::WherePredicate::EqPredicate(ref eq_pred) => {
1282                 // FIXME(#20041)
1283                 ccx.tcx.sess.span_bug(eq_pred.span,
1284                                          "Equality constraints are not yet \
1285                                             implemented (#20041)")
1286             }
1287         }
1288     }
1289
1290     return result;
1291
1292     fn create_predicates<'tcx>(
1293         tcx: &ty::ctxt<'tcx>,
1294         result: &mut ty::Generics<'tcx>,
1295         space: subst::ParamSpace)
1296     {
1297         for type_param_def in result.types.get_slice(space).iter() {
1298             let param_ty = ty::mk_param_from_def(tcx, type_param_def);
1299             for predicate in ty::predicates(tcx, param_ty, &type_param_def.bounds).into_iter() {
1300                 result.predicates.push(space, predicate);
1301             }
1302         }
1303
1304         for region_param_def in result.regions.get_slice(space).iter() {
1305             let region = region_param_def.to_early_bound_region();
1306             for &bound_region in region_param_def.bounds.iter() {
1307                 // account for new binder introduced in the predicate below; no need
1308                 // to shift `region` because it is never a late-bound region
1309                 let bound_region = ty_fold::shift_region(bound_region, 1);
1310                 result.predicates.push(
1311                     space,
1312                     ty::Binder(ty::OutlivesPredicate(region, bound_region)).as_predicate());
1313             }
1314         }
1315     }
1316 }
1317
1318 fn get_or_create_type_parameter_def<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1319                                              space: subst::ParamSpace,
1320                                              param: &ast::TyParam,
1321                                              index: u32)
1322                                              -> ty::TypeParameterDef<'tcx>
1323 {
1324     match ccx.tcx.ty_param_defs.borrow().get(&param.id) {
1325         Some(d) => { return (*d).clone(); }
1326         None => { }
1327     }
1328
1329     let param_ty = ty::ParamTy::new(space, index, param.ident.name);
1330     let bounds = compute_bounds(ccx,
1331                                 param_ty.to_ty(ccx.tcx),
1332                                 &param.bounds[],
1333                                 SizedByDefault::Yes,
1334                                 param.span);
1335     let default = match param.default {
1336         None => None,
1337         Some(ref path) => {
1338             let ty = ast_ty_to_ty(ccx, &ExplicitRscope, &**path);
1339             let cur_idx = index;
1340
1341             ty::walk_ty(ty, |t| {
1342                 match t.sty {
1343                     ty::ty_param(p) => if p.idx > cur_idx {
1344                         span_err!(ccx.tcx.sess, path.span, E0128,
1345                                   "type parameters with a default cannot use \
1346                                    forward declared identifiers");
1347                         },
1348                         _ => {}
1349                     }
1350             });
1351
1352             Some(ty)
1353         }
1354     };
1355
1356     let def = ty::TypeParameterDef {
1357         space: space,
1358         index: index,
1359         name: param.ident.name,
1360         def_id: local_def(param.id),
1361         bounds: bounds,
1362         default: default
1363     };
1364
1365     ccx.tcx.ty_param_defs.borrow_mut().insert(param.id, def.clone());
1366
1367     def
1368 }
1369
1370 enum SizedByDefault { Yes, No }
1371
1372 /// Translate the AST's notion of ty param bounds (which are an enum consisting of a newtyped Ty or
1373 /// a region) to ty's notion of ty param bounds, which can either be user-defined traits, or the
1374 /// built-in trait (formerly known as kind): Send.
1375 fn compute_bounds<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1376                            param_ty: ty::Ty<'tcx>,
1377                            ast_bounds: &[ast::TyParamBound],
1378                            sized_by_default: SizedByDefault,
1379                            span: Span)
1380                            -> ty::ParamBounds<'tcx>
1381 {
1382     let mut param_bounds = conv_param_bounds(ccx,
1383                                              span,
1384                                              param_ty,
1385                                              ast_bounds);
1386
1387     if let SizedByDefault::Yes = sized_by_default {
1388         add_unsized_bound(ccx,
1389                           &mut param_bounds.builtin_bounds,
1390                           ast_bounds,
1391                           span);
1392
1393         check_bounds_compatible(ccx.tcx,
1394                                 param_ty,
1395                                 &param_bounds,
1396                                 span);
1397     }
1398
1399     param_bounds.trait_bounds.sort_by(|a,b| a.def_id().cmp(&b.def_id()));
1400
1401     param_bounds
1402 }
1403
1404 fn check_bounds_compatible<'tcx>(tcx: &ty::ctxt<'tcx>,
1405                                  param_ty: Ty<'tcx>,
1406                                  param_bounds: &ty::ParamBounds<'tcx>,
1407                                  span: Span) {
1408     // Currently the only bound which is incompatible with other bounds is
1409     // Sized/Unsized.
1410     if !param_bounds.builtin_bounds.contains(&ty::BoundSized) {
1411         ty::each_bound_trait_and_supertraits(
1412             tcx,
1413             &param_bounds.trait_bounds[],
1414             |trait_ref| {
1415                 let trait_def = ty::lookup_trait_def(tcx, trait_ref.def_id());
1416                 if trait_def.bounds.builtin_bounds.contains(&ty::BoundSized) {
1417                     span_err!(tcx.sess, span, E0129,
1418                               "incompatible bounds on `{}`, \
1419                                bound `{}` does not allow unsized type",
1420                               param_ty.user_string(tcx),
1421                               trait_ref.user_string(tcx));
1422                 }
1423                 true
1424             });
1425     }
1426 }
1427
1428 fn conv_param_bounds<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1429                               span: Span,
1430                               param_ty: ty::Ty<'tcx>,
1431                               ast_bounds: &[ast::TyParamBound])
1432                               -> ty::ParamBounds<'tcx>
1433 {
1434     let astconv::PartitionedBounds { builtin_bounds,
1435                                      trait_bounds,
1436                                      region_bounds } =
1437         astconv::partition_bounds(ccx.tcx, span, ast_bounds.as_slice());
1438
1439     let mut projection_bounds = Vec::new();
1440
1441     let trait_bounds: Vec<ty::PolyTraitRef> =
1442         trait_bounds.into_iter()
1443         .map(|bound| {
1444             astconv::instantiate_poly_trait_ref(ccx,
1445                                                 &ExplicitRscope,
1446                                                 bound,
1447                                                 Some(param_ty),
1448                                                 &mut projection_bounds)
1449         })
1450         .collect();
1451     let region_bounds: Vec<ty::Region> =
1452         region_bounds.into_iter()
1453         .map(|r| ast_region_to_region(ccx.tcx, r))
1454         .collect();
1455     ty::ParamBounds {
1456         region_bounds: region_bounds,
1457         builtin_bounds: builtin_bounds,
1458         trait_bounds: trait_bounds,
1459         projection_bounds: projection_bounds,
1460     }
1461 }
1462
1463 fn ty_of_foreign_fn_decl<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
1464                                        decl: &ast::FnDecl,
1465                                        def_id: ast::DefId,
1466                                        ast_generics: &ast::Generics,
1467                                        abi: abi::Abi)
1468                                        -> ty::TypeScheme<'tcx> {
1469     for i in decl.inputs.iter() {
1470         match (*i).pat.node {
1471             ast::PatIdent(_, _, _) => (),
1472             ast::PatWild(ast::PatWildSingle) => (),
1473             _ => {
1474                 span_err!(ccx.tcx.sess, (*i).pat.span, E0130,
1475                           "patterns aren't allowed in foreign function declarations");
1476             }
1477         }
1478     }
1479
1480     let ty_generics_for_fn_or_method = ty_generics_for_fn_or_method(ccx,
1481                                                                     ast_generics,
1482                                                                     ty::Generics::empty());
1483     let rb = BindingRscope::new();
1484     let input_tys = decl.inputs
1485                         .iter()
1486                         .map(|a| ty_of_arg(ccx, &rb, a, None))
1487                         .collect();
1488
1489     let output = match decl.output {
1490         ast::Return(ref ty) =>
1491             ty::FnConverging(ast_ty_to_ty(ccx, &rb, &**ty)),
1492         ast::DefaultReturn(..) =>
1493             ty::FnConverging(ty::mk_nil(ccx.tcx)),
1494         ast::NoReturn(..) =>
1495             ty::FnDiverging
1496     };
1497
1498     let t_fn = ty::mk_bare_fn(
1499         ccx.tcx,
1500         None,
1501         ccx.tcx.mk_bare_fn(ty::BareFnTy {
1502             abi: abi,
1503             unsafety: ast::Unsafety::Unsafe,
1504             sig: ty::Binder(ty::FnSig {inputs: input_tys,
1505                                        output: output,
1506                                        variadic: decl.variadic}),
1507         }));
1508     let scheme = TypeScheme {
1509         generics: ty_generics_for_fn_or_method,
1510         ty: t_fn
1511     };
1512
1513     ccx.tcx.tcache.borrow_mut().insert(def_id, scheme.clone());
1514     return scheme;
1515 }
1516
1517 fn mk_item_substs<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
1518                             ty_generics: &ty::Generics<'tcx>)
1519                             -> subst::Substs<'tcx>
1520 {
1521     let types =
1522         ty_generics.types.map(
1523             |def| ty::mk_param_from_def(ccx.tcx, def));
1524
1525     let regions =
1526         ty_generics.regions.map(
1527             |def| def.to_early_bound_region());
1528
1529     subst::Substs::new(types, regions)
1530 }
1531
1532 /// Verifies that the explicit self type of a method matches the impl
1533 /// or trait. This is a bit weird but basically because right now we
1534 /// don't handle the general case, but instead map it to one of
1535 /// several pre-defined options using various heuristics, this method
1536 /// comes back to check after the fact that explicit type the user
1537 /// wrote actually matches what the pre-defined option said.
1538 fn check_method_self_type<'a, 'tcx, RS:RegionScope>(
1539     ccx: &CollectCtxt<'a, 'tcx>,
1540     rs: &RS,
1541     required_type: Ty<'tcx>,
1542     explicit_self: &ast::ExplicitSelf,
1543     body_id: ast::NodeId)
1544 {
1545     if let ast::SelfExplicit(ref ast_type, _) = explicit_self.node {
1546         let typ = ccx.to_ty(rs, &**ast_type);
1547         let base_type = match typ.sty {
1548             ty::ty_ptr(tm) | ty::ty_rptr(_, tm) => tm.ty,
1549             ty::ty_uniq(typ) => typ,
1550             _ => typ,
1551         };
1552
1553         let body_scope = region::CodeExtent::from_node_id(body_id);
1554
1555         // "Required type" comes from the trait definition. It may
1556         // contain late-bound regions from the method, but not the
1557         // trait (since traits only have early-bound region
1558         // parameters).
1559         assert!(!base_type.has_regions_escaping_depth(1));
1560         let required_type_free =
1561             liberate_early_bound_regions(
1562                 ccx.tcx, body_scope,
1563                 &ty::liberate_late_bound_regions(
1564                     ccx.tcx, body_scope, &ty::Binder(required_type)));
1565
1566         // The "base type" comes from the impl. It too may have late-bound
1567         // regions from the method.
1568         assert!(!base_type.has_regions_escaping_depth(1));
1569         let base_type_free =
1570             liberate_early_bound_regions(
1571                 ccx.tcx, body_scope,
1572                 &ty::liberate_late_bound_regions(
1573                     ccx.tcx, body_scope, &ty::Binder(base_type)));
1574
1575         debug!("required_type={} required_type_free={} \
1576                 base_type={} base_type_free={}",
1577                required_type.repr(ccx.tcx),
1578                required_type_free.repr(ccx.tcx),
1579                base_type.repr(ccx.tcx),
1580                base_type_free.repr(ccx.tcx));
1581         let infcx = infer::new_infer_ctxt(ccx.tcx);
1582         drop(::require_same_types(ccx.tcx,
1583                                   Some(&infcx),
1584                                   false,
1585                                   explicit_self.span,
1586                                   base_type_free,
1587                                   required_type_free,
1588                                   || {
1589                 format!("mismatched self type: expected `{}`",
1590                         ppaux::ty_to_string(ccx.tcx, required_type))
1591         }));
1592         infcx.resolve_regions_and_report_errors(body_id);
1593     }
1594
1595     fn liberate_early_bound_regions<'tcx,T>(
1596         tcx: &ty::ctxt<'tcx>,
1597         scope: region::CodeExtent,
1598         value: &T)
1599         -> T
1600         where T : TypeFoldable<'tcx> + Repr<'tcx>
1601     {
1602         /*!
1603          * Convert early-bound regions into free regions; normally this is done by
1604          * applying the `free_substs` from the `ParameterEnvironment`, but this particular
1605          * method-self-type check is kind of hacky and done very early in the process,
1606          * before we really have a `ParameterEnvironment` to check.
1607          */
1608
1609         ty_fold::fold_regions(tcx, value, |region, _| {
1610             match region {
1611                 ty::ReEarlyBound(id, _, _, name) => {
1612                     let def_id = local_def(id);
1613                     ty::ReFree(ty::FreeRegion { scope: scope,
1614                                                 bound_region: ty::BrNamed(def_id, name) })
1615                 }
1616                 _ => region
1617             }
1618         })
1619     }
1620 }
1621
1622 /// Checks that all the type parameters on an impl
1623 fn enforce_impl_ty_params_are_constrained<'tcx>(tcx: &ty::ctxt<'tcx>,
1624                                                 ast_generics: &ast::Generics,
1625                                                 impl_def_id: ast::DefId)
1626 {
1627     let impl_scheme = ty::lookup_item_type(tcx, impl_def_id);
1628     let impl_trait_ref = ty::impl_trait_ref(tcx, impl_def_id);
1629
1630     // The trait reference is an input, so find all type parameters
1631     // reachable from there, to start (if this is an inherent impl,
1632     // then just examine the self type).
1633     let mut input_parameters: HashSet<_> =
1634         impl_trait_ref.iter()
1635                       .flat_map(|t| t.input_types().iter()) // Types in trait ref, if any
1636                       .chain(Some(impl_scheme.ty).iter())  // Self type, always
1637                       .flat_map(|t| t.walk())
1638                       .filter_map(to_opt_param_ty)
1639                       .collect();
1640
1641     loop {
1642         let num_inputs = input_parameters.len();
1643
1644         let mut projection_predicates =
1645             impl_scheme.generics.predicates
1646             .iter()
1647             .filter_map(|predicate| {
1648                 match *predicate {
1649                     // Ignore higher-ranked binders. For the purposes
1650                     // of this check, they don't matter because they
1651                     // only affect named regions, and we're just
1652                     // concerned about type parameters here.
1653                     ty::Predicate::Projection(ref data) => Some(data.0.clone()),
1654                     _ => None,
1655                 }
1656             });
1657
1658         for projection in projection_predicates {
1659             // Special case: watch out for some kind of sneaky attempt
1660             // to project out an associated type defined by this very trait.
1661             if Some(projection.projection_ty.trait_ref.clone()) == impl_trait_ref {
1662                 continue;
1663             }
1664
1665             let relies_only_on_inputs =
1666                 projection.projection_ty.trait_ref.input_types().iter()
1667                 .flat_map(|t| t.walk())
1668                 .filter_map(to_opt_param_ty)
1669                 .all(|t| input_parameters.contains(&t));
1670
1671             if relies_only_on_inputs {
1672                 input_parameters.extend(
1673                     projection.ty.walk().filter_map(to_opt_param_ty));
1674             }
1675         }
1676
1677         if input_parameters.len() == num_inputs {
1678             break;
1679         }
1680     }
1681
1682     for (index, ty_param) in ast_generics.ty_params.iter().enumerate() {
1683         let param_ty = ty::ParamTy { space: TypeSpace,
1684                                      idx: index as u32,
1685                                      name: ty_param.ident.name };
1686         if !input_parameters.contains(&param_ty) {
1687             if ty::has_attr(tcx, impl_def_id, "old_impl_check") {
1688                 tcx.sess.span_warn(
1689                     ty_param.span,
1690                     format!("the type parameter `{}` is not constrained by the \
1691                              impl trait, self type, or predicates",
1692                             param_ty.user_string(tcx)).as_slice());
1693             } else {
1694                 span_err!(tcx.sess, ty_param.span, E0207,
1695                     "the type parameter `{}` is not constrained by the \
1696                              impl trait, self type, or predicates",
1697                             param_ty.user_string(tcx));
1698                 tcx.sess.span_help(
1699                     ty_param.span,
1700                     format!("you can temporarily opt out of this rule by placing \
1701                              the `#[old_impl_check]` attribute on the impl").as_slice());
1702             }
1703         }
1704     }
1705
1706     fn to_opt_param_ty<'tcx>(ty: Ty<'tcx>) -> Option<ty::ParamTy> {
1707         match ty.sty {
1708             ty::ty_param(ref d) => Some(d.clone()),
1709             _ => None,
1710         }
1711     }
1712 }