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