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