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