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             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                         if opt_trait_ref.is_none() {
 611                             tcx.sess.span_err(typedef.span,
 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                 ccx.tcx.sess.span_err(span, "type parameter has more than one relaxed default \
1164                                                 bound, only one is supported");
1165             }
1166         }
1167     }
1168
1169     let kind_id = ccx.tcx.lang_items.require(SizedTraitLangItem);
1170     match unbound {
1171         Some(ref tpb) => {
1172             // FIXME(#8559) currently requires the unbound to be built-in.
1173             let trait_def_id = ty::trait_ref_to_def_id(ccx.tcx, tpb);
1174             match kind_id {
1175                 Ok(kind_id) if trait_def_id != kind_id => {
1176                     ccx.tcx.sess.span_warn(span,
1177                                               "default bound relaxed for a type parameter, but \
1178                                                this does nothing because the given bound is not \
1179                                                a default. Only `?Sized` is supported");
1180                     ty::try_add_builtin_trait(ccx.tcx,
1181                                               kind_id,
1182                                               bounds);
1183                 }
1184                 _ => {}
1185             }
1186         }
1187         _ if kind_id.is_ok() => {
1188             ty::try_add_builtin_trait(ccx.tcx, kind_id.unwrap(), bounds);
1189         }
1190         // No lang item for Sized, so we can't add it as a bound.
1191         None => {}
1192     }
1193 }
1194
1195 fn ty_generics<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1196                         space: subst::ParamSpace,
1197                         lifetime_defs: &[ast::LifetimeDef],
1198                         types: &[ast::TyParam],
1199                         base_generics: ty::Generics<'tcx>,
1200                         where_clause: &ast::WhereClause)
1201                         -> ty::Generics<'tcx>
1202 {
1203     let mut result = base_generics;
1204
1205     for (i, l) in lifetime_defs.iter().enumerate() {
1206         let bounds = l.bounds.iter()
1207                              .map(|l| ast_region_to_region(ccx.tcx, l))
1208                              .collect();
1209         let def = ty::RegionParameterDef { name: l.lifetime.name,
1210                                            space: space,
1211                                            index: i as u32,
1212                                            def_id: local_def(l.lifetime.id),
1213                                            bounds: bounds };
1214         debug!("ty_generics: def for region param: {:?}", def);
1215         result.regions.push(space, def);
1216     }
1217
1218     assert!(result.types.is_empty_in(space));
1219
1220     // Now create the real type parameters.
1221     for (i, param) in types.iter().enumerate() {
1222         let def = get_or_create_type_parameter_def(ccx,
1223                                                    space,
1224                                                    param,
1225                                                    i as u32);
1226         debug!("ty_generics: def for type param: {}, {:?}",
1227                def.repr(ccx.tcx),
1228                space);
1229         result.types.push(space, def);
1230     }
1231
1232     // Just for fun, also push the bounds from the type parameters
1233     // into the predicates list. This is currently kind of non-DRY.
1234     create_predicates(ccx.tcx, &mut result, space);
1235
1236     // Add the bounds not associated with a type parameter
1237     for predicate in where_clause.predicates.iter() {
1238         match predicate {
1239             &ast::WherePredicate::BoundPredicate(ref bound_pred) => {
1240                 let ty = ast_ty_to_ty(ccx, &ExplicitRscope, &*bound_pred.bounded_ty);
1241
1242                 for bound in bound_pred.bounds.iter() {
1243                     match bound {
1244                         &ast::TyParamBound::TraitTyParamBound(ref poly_trait_ref, _) => {
1245                             let mut projections = Vec::new();
1246
1247                             let trait_ref = astconv::instantiate_poly_trait_ref(
1248                                 ccx,
1249                                 &ExplicitRscope,
1250                                 poly_trait_ref,
1251                                 Some(ty),
1252                                 &mut projections,
1253                             );
1254
1255                             result.predicates.push(space, trait_ref.as_predicate());
1256
1257                             for projection in projections.iter() {
1258                                 result.predicates.push(space, projection.as_predicate());
1259                             }
1260                         }
1261
1262                         &ast::TyParamBound::RegionTyParamBound(ref lifetime) => {
1263                             let region = ast_region_to_region(ccx.tcx, lifetime);
1264                             let pred = ty::Binder(ty::OutlivesPredicate(ty, region));
1265                             result.predicates.push(space, ty::Predicate::TypeOutlives(pred))
1266                         }
1267                     }
1268                 }
1269             }
1270
1271             &ast::WherePredicate::RegionPredicate(ref region_pred) => {
1272                 let r1 = ast_region_to_region(ccx.tcx, &region_pred.lifetime);
1273                 for bound in region_pred.bounds.iter() {
1274                     let r2 = ast_region_to_region(ccx.tcx, bound);
1275                     let pred = ty::Binder(ty::OutlivesPredicate(r1, r2));
1276                     result.predicates.push(space, ty::Predicate::RegionOutlives(pred))
1277                 }
1278             }
1279
1280             &ast::WherePredicate::EqPredicate(ref eq_pred) => {
1281                 // FIXME(#20041)
1282                 ccx.tcx.sess.span_bug(eq_pred.span,
1283                                          "Equality constraints are not yet \
1284                                             implemented (#20041)")
1285             }
1286         }
1287     }
1288
1289     return result;
1290
1291     fn create_predicates<'tcx>(
1292         tcx: &ty::ctxt<'tcx>,
1293         result: &mut ty::Generics<'tcx>,
1294         space: subst::ParamSpace)
1295     {
1296         for type_param_def in result.types.get_slice(space).iter() {
1297             let param_ty = ty::mk_param_from_def(tcx, type_param_def);
1298             for predicate in ty::predicates(tcx, param_ty, &type_param_def.bounds).into_iter() {
1299                 result.predicates.push(space, predicate);
1300             }
1301         }
1302
1303         for region_param_def in result.regions.get_slice(space).iter() {
1304             let region = region_param_def.to_early_bound_region();
1305             for &bound_region in region_param_def.bounds.iter() {
1306                 // account for new binder introduced in the predicate below; no need
1307                 // to shift `region` because it is never a late-bound region
1308                 let bound_region = ty_fold::shift_region(bound_region, 1);
1309                 result.predicates.push(
1310                     space,
1311                     ty::Binder(ty::OutlivesPredicate(region, bound_region)).as_predicate());
1312             }
1313         }
1314     }
1315 }
1316
1317 fn get_or_create_type_parameter_def<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1318                                              space: subst::ParamSpace,
1319                                              param: &ast::TyParam,
1320                                              index: u32)
1321                                              -> ty::TypeParameterDef<'tcx>
1322 {
1323     match ccx.tcx.ty_param_defs.borrow().get(&param.id) {
1324         Some(d) => { return (*d).clone(); }
1325         None => { }
1326     }
1327
1328     let param_ty = ty::ParamTy::new(space, index, param.ident.name);
1329     let bounds = compute_bounds(ccx,
1330                                 param_ty.to_ty(ccx.tcx),
1331                                 &param.bounds[],
1332                                 SizedByDefault::Yes,
1333                                 param.span);
1334     let default = match param.default {
1335         None => None,
1336         Some(ref path) => {
1337             let ty = ast_ty_to_ty(ccx, &ExplicitRscope, &**path);
1338             let cur_idx = index;
1339
1340             ty::walk_ty(ty, |t| {
1341                 match t.sty {
1342                     ty::ty_param(p) => if p.idx > cur_idx {
1343                         span_err!(ccx.tcx.sess, path.span, E0128,
1344                                   "type parameters with a default cannot use \
1345                                    forward declared identifiers");
1346                         },
1347                         _ => {}
1348                     }
1349             });
1350
1351             Some(ty)
1352         }
1353     };
1354
1355     let def = ty::TypeParameterDef {
1356         space: space,
1357         index: index,
1358         name: param.ident.name,
1359         def_id: local_def(param.id),
1360         bounds: bounds,
1361         default: default
1362     };
1363
1364     ccx.tcx.ty_param_defs.borrow_mut().insert(param.id, def.clone());
1365
1366     def
1367 }
1368
1369 enum SizedByDefault { Yes, No }
1370
1371 /// Translate the AST's notion of ty param bounds (which are an enum consisting of a newtyped Ty or
1372 /// a region) to ty's notion of ty param bounds, which can either be user-defined traits, or the
1373 /// built-in trait (formerly known as kind): Send.
1374 fn compute_bounds<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1375                            param_ty: ty::Ty<'tcx>,
1376                            ast_bounds: &[ast::TyParamBound],
1377                            sized_by_default: SizedByDefault,
1378                            span: Span)
1379                            -> ty::ParamBounds<'tcx>
1380 {
1381     let mut param_bounds = conv_param_bounds(ccx,
1382                                              span,
1383                                              param_ty,
1384                                              ast_bounds);
1385
1386     if let SizedByDefault::Yes = sized_by_default {
1387         add_unsized_bound(ccx,
1388                           &mut param_bounds.builtin_bounds,
1389                           ast_bounds,
1390                           span);
1391
1392         check_bounds_compatible(ccx.tcx,
1393                                 param_ty,
1394                                 &param_bounds,
1395                                 span);
1396     }
1397
1398     param_bounds.trait_bounds.sort_by(|a,b| a.def_id().cmp(&b.def_id()));
1399
1400     param_bounds
1401 }
1402
1403 fn check_bounds_compatible<'tcx>(tcx: &ty::ctxt<'tcx>,
1404                                  param_ty: Ty<'tcx>,
1405                                  param_bounds: &ty::ParamBounds<'tcx>,
1406                                  span: Span) {
1407     // Currently the only bound which is incompatible with other bounds is
1408     // Sized/Unsized.
1409     if !param_bounds.builtin_bounds.contains(&ty::BoundSized) {
1410         ty::each_bound_trait_and_supertraits(
1411             tcx,
1412             &param_bounds.trait_bounds[],
1413             |trait_ref| {
1414                 let trait_def = ty::lookup_trait_def(tcx, trait_ref.def_id());
1415                 if trait_def.bounds.builtin_bounds.contains(&ty::BoundSized) {
1416                     span_err!(tcx.sess, span, E0129,
1417                               "incompatible bounds on `{}`, \
1418                                bound `{}` does not allow unsized type",
1419                               param_ty.user_string(tcx),
1420                               trait_ref.user_string(tcx));
1421                 }
1422                 true
1423             });
1424     }
1425 }
1426
1427 fn conv_param_bounds<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1428                               span: Span,
1429                               param_ty: ty::Ty<'tcx>,
1430                               ast_bounds: &[ast::TyParamBound])
1431                               -> ty::ParamBounds<'tcx>
1432 {
1433     let astconv::PartitionedBounds { builtin_bounds,
1434                                      trait_bounds,
1435                                      region_bounds } =
1436         astconv::partition_bounds(ccx.tcx, span, ast_bounds.as_slice());
1437
1438     let mut projection_bounds = Vec::new();
1439
1440     let trait_bounds: Vec<ty::PolyTraitRef> =
1441         trait_bounds.into_iter()
1442         .map(|bound| {
1443             astconv::instantiate_poly_trait_ref(ccx,
1444                                                 &ExplicitRscope,
1445                                                 bound,
1446                                                 Some(param_ty),
1447                                                 &mut projection_bounds)
1448         })
1449         .collect();
1450     let region_bounds: Vec<ty::Region> =
1451         region_bounds.into_iter()
1452         .map(|r| ast_region_to_region(ccx.tcx, r))
1453         .collect();
1454     ty::ParamBounds {
1455         region_bounds: region_bounds,
1456         builtin_bounds: builtin_bounds,
1457         trait_bounds: trait_bounds,
1458         projection_bounds: projection_bounds,
1459     }
1460 }
1461
1462 fn ty_of_foreign_fn_decl<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
1463                                        decl: &ast::FnDecl,
1464                                        def_id: ast::DefId,
1465                                        ast_generics: &ast::Generics,
1466                                        abi: abi::Abi)
1467                                        -> ty::TypeScheme<'tcx> {
1468     for i in decl.inputs.iter() {
1469         match (*i).pat.node {
1470             ast::PatIdent(_, _, _) => (),
1471             ast::PatWild(ast::PatWildSingle) => (),
1472             _ => {
1473                 span_err!(ccx.tcx.sess, (*i).pat.span, E0130,
1474                           "patterns aren't allowed in foreign function declarations");
1475             }
1476         }
1477     }
1478
1479     let ty_generics_for_fn_or_method = ty_generics_for_fn_or_method(ccx,
1480                                                                     ast_generics,
1481                                                                     ty::Generics::empty());
1482     let rb = BindingRscope::new();
1483     let input_tys = decl.inputs
1484                         .iter()
1485                         .map(|a| ty_of_arg(ccx, &rb, a, None))
1486                         .collect();
1487
1488     let output = match decl.output {
1489         ast::Return(ref ty) =>
1490             ty::FnConverging(ast_ty_to_ty(ccx, &rb, &**ty)),
1491         ast::DefaultReturn(..) =>
1492             ty::FnConverging(ty::mk_nil(ccx.tcx)),
1493         ast::NoReturn(..) =>
1494             ty::FnDiverging
1495     };
1496
1497     let t_fn = ty::mk_bare_fn(
1498         ccx.tcx,
1499         None,
1500         ccx.tcx.mk_bare_fn(ty::BareFnTy {
1501             abi: abi,
1502             unsafety: ast::Unsafety::Unsafe,
1503             sig: ty::Binder(ty::FnSig {inputs: input_tys,
1504                                        output: output,
1505                                        variadic: decl.variadic}),
1506         }));
1507     let scheme = TypeScheme {
1508         generics: ty_generics_for_fn_or_method,
1509         ty: t_fn
1510     };
1511
1512     ccx.tcx.tcache.borrow_mut().insert(def_id, scheme.clone());
1513     return scheme;
1514 }
1515
1516 fn mk_item_substs<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
1517                             ty_generics: &ty::Generics<'tcx>)
1518                             -> subst::Substs<'tcx>
1519 {
1520     let types =
1521         ty_generics.types.map(
1522             |def| ty::mk_param_from_def(ccx.tcx, def));
1523
1524     let regions =
1525         ty_generics.regions.map(
1526             |def| def.to_early_bound_region());
1527
1528     subst::Substs::new(types, regions)
1529 }
1530
1531 /// Verifies that the explicit self type of a method matches the impl
1532 /// or trait. This is a bit weird but basically because right now we
1533 /// don't handle the general case, but instead map it to one of
1534 /// several pre-defined options using various heuristics, this method
1535 /// comes back to check after the fact that explicit type the user
1536 /// wrote actually matches what the pre-defined option said.
1537 fn check_method_self_type<'a, 'tcx, RS:RegionScope>(
1538     ccx: &CollectCtxt<'a, 'tcx>,
1539     rs: &RS,
1540     required_type: Ty<'tcx>,
1541     explicit_self: &ast::ExplicitSelf,
1542     body_id: ast::NodeId)
1543 {
1544     if let ast::SelfExplicit(ref ast_type, _) = explicit_self.node {
1545         let typ = ccx.to_ty(rs, &**ast_type);
1546         let base_type = match typ.sty {
1547             ty::ty_ptr(tm) | ty::ty_rptr(_, tm) => tm.ty,
1548             ty::ty_uniq(typ) => typ,
1549             _ => typ,
1550         };
1551
1552         let body_scope = region::CodeExtent::from_node_id(body_id);
1553
1554         // "Required type" comes from the trait definition. It may
1555         // contain late-bound regions from the method, but not the
1556         // trait (since traits only have early-bound region
1557         // parameters).
1558         assert!(!base_type.has_regions_escaping_depth(1));
1559         let required_type_free =
1560             liberate_early_bound_regions(
1561                 ccx.tcx, body_scope,
1562                 &ty::liberate_late_bound_regions(
1563                     ccx.tcx, body_scope, &ty::Binder(required_type)));
1564
1565         // The "base type" comes from the impl. It too may have late-bound
1566         // regions from the method.
1567         assert!(!base_type.has_regions_escaping_depth(1));
1568         let base_type_free =
1569             liberate_early_bound_regions(
1570                 ccx.tcx, body_scope,
1571                 &ty::liberate_late_bound_regions(
1572                     ccx.tcx, body_scope, &ty::Binder(base_type)));
1573
1574         debug!("required_type={} required_type_free={} \
1575                 base_type={} base_type_free={}",
1576                required_type.repr(ccx.tcx),
1577                required_type_free.repr(ccx.tcx),
1578                base_type.repr(ccx.tcx),
1579                base_type_free.repr(ccx.tcx));
1580         let infcx = infer::new_infer_ctxt(ccx.tcx);
1581         drop(::require_same_types(ccx.tcx,
1582                                   Some(&infcx),
1583                                   false,
1584                                   explicit_self.span,
1585                                   base_type_free,
1586                                   required_type_free,
1587                                   || {
1588                 format!("mismatched self type: expected `{}`",
1589                         ppaux::ty_to_string(ccx.tcx, required_type))
1590         }));
1591         infcx.resolve_regions_and_report_errors(body_id);
1592     }
1593
1594     fn liberate_early_bound_regions<'tcx,T>(
1595         tcx: &ty::ctxt<'tcx>,
1596         scope: region::CodeExtent,
1597         value: &T)
1598         -> T
1599         where T : TypeFoldable<'tcx> + Repr<'tcx>
1600     {
1601         /*!
1602          * Convert early-bound regions into free regions; normally this is done by
1603          * applying the `free_substs` from the `ParameterEnvironment`, but this particular
1604          * method-self-type check is kind of hacky and done very early in the process,
1605          * before we really have a `ParameterEnvironment` to check.
1606          */
1607
1608         ty_fold::fold_regions(tcx, value, |region, _| {
1609             match region {
1610                 ty::ReEarlyBound(id, _, _, name) => {
1611                     let def_id = local_def(id);
1612                     ty::ReFree(ty::FreeRegion { scope: scope,
1613                                                 bound_region: ty::BrNamed(def_id, name) })
1614                 }
1615                 _ => region
1616             }
1617         })
1618     }
1619 }
1620
1621 /// Checks that all the type parameters on an impl
1622 fn enforce_impl_ty_params_are_constrained<'tcx>(tcx: &ty::ctxt<'tcx>,
1623                                                 ast_generics: &ast::Generics,
1624                                                 impl_def_id: ast::DefId)
1625 {
1626     let impl_scheme = ty::lookup_item_type(tcx, impl_def_id);
1627     let impl_trait_ref = ty::impl_trait_ref(tcx, impl_def_id);
1628
1629     // The trait reference is an input, so find all type parameters
1630     // reachable from there, to start (if this is an inherent impl,
1631     // then just examine the self type).
1632     let mut input_parameters: HashSet<_> =
1633         impl_trait_ref.iter()
1634                       .flat_map(|t| t.input_types().iter()) // Types in trait ref, if any
1635                       .chain(Some(impl_scheme.ty).iter())  // Self type, always
1636                       .flat_map(|t| t.walk())
1637                       .filter_map(to_opt_param_ty)
1638                       .collect();
1639
1640     loop {
1641         let num_inputs = input_parameters.len();
1642
1643         let mut projection_predicates =
1644             impl_scheme.generics.predicates
1645             .iter()
1646             .filter_map(|predicate| {
1647                 match *predicate {
1648                     // Ignore higher-ranked binders. For the purposes
1649                     // of this check, they don't matter because they
1650                     // only affect named regions, and we're just
1651                     // concerned about type parameters here.
1652                     ty::Predicate::Projection(ref data) => Some(data.0.clone()),
1653                     _ => None,
1654                 }
1655             });
1656
1657         for projection in projection_predicates {
1658             // Special case: watch out for some kind of sneaky attempt
1659             // to project out an associated type defined by this very trait.
1660             if Some(projection.projection_ty.trait_ref.clone()) == impl_trait_ref {
1661                 continue;
1662             }
1663
1664             let relies_only_on_inputs =
1665                 projection.projection_ty.trait_ref.input_types().iter()
1666                 .flat_map(|t| t.walk())
1667                 .filter_map(to_opt_param_ty)
1668                 .all(|t| input_parameters.contains(&t));
1669
1670             if relies_only_on_inputs {
1671                 input_parameters.extend(
1672                     projection.ty.walk().filter_map(to_opt_param_ty));
1673             }
1674         }
1675
1676         if input_parameters.len() == num_inputs {
1677             break;
1678         }
1679     }
1680
1681     for (index, ty_param) in ast_generics.ty_params.iter().enumerate() {
1682         let param_ty = ty::ParamTy { space: TypeSpace,
1683                                      idx: index as u32,
1684                                      name: ty_param.ident.name };
1685         if !input_parameters.contains(&param_ty) {
1686             if ty::has_attr(tcx, impl_def_id, "old_impl_check") {
1687                 tcx.sess.span_warn(
1688                     ty_param.span,
1689                     format!("the type parameter `{}` is not constrained by the \
1690                              impl trait, self type, or predicates",
1691                             param_ty.user_string(tcx)).as_slice());
1692             } else {
1693                 tcx.sess.span_err(
1694                     ty_param.span,
1695                     format!("the type parameter `{}` is not constrained by the \
1696                              impl trait, self type, or predicates",
1697                             param_ty.user_string(tcx)).as_slice());
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 }