src/librustc/middle/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).  Polytypes are represented by an instance of
  27 `ty::Polytype`.  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 self::ConvertMethodContext::*;
  33 use self::CreateTypeParametersForAssociatedTypesFlag::*;
  34
  35 use metadata::csearch;
  36 use middle::def;
  37 use middle::lang_items::SizedTraitLangItem;
  38 use middle::region;
  39 use middle::resolve_lifetime;
  40 use middle::subst;
  41 use middle::subst::{Substs};
  42 use middle::ty::{ImplContainer, ImplOrTraitItemContainer, TraitContainer};
  43 use middle::ty::{Polytype};
  44 use middle::ty::{mod, Ty};
  45 use middle::ty_fold::TypeFolder;
  46 use middle::typeck::astconv::{AstConv, ty_of_arg};
  47 use middle::typeck::astconv::{ast_ty_to_ty, ast_region_to_region};
  48 use middle::typeck::astconv;
  49 use middle::typeck::infer;
  50 use middle::typeck::rscope::*;
  51 use middle::typeck::{CrateCtxt, lookup_def_tcx, no_params, write_ty_to_tcx};
  52 use middle::typeck;
  53 use util::nodemap::{FnvHashMap, FnvHashSet};
  54 use util::ppaux;
  55 use util::ppaux::{Repr,UserString};
  56
  57 use std::rc::Rc;
  58
  59 use syntax::abi;
  60 use syntax::ast;
  61 use syntax::ast_map;
  62 use syntax::ast_util::{local_def, PostExpansionMethod};
  63 use syntax::codemap::Span;
  64 use syntax::parse::token::{special_idents};
  65 use syntax::parse::token;
  66 use syntax::ptr::P;
  67 use syntax::visit;
  68
  69 ///////////////////////////////////////////////////////////////////////////
  70 // Main entry point
  71
  72 pub fn collect_item_types(ccx: &CrateCtxt) {
  73     fn collect_intrinsic_type(ccx: &CrateCtxt,
  74                               lang_item: ast::DefId) {
  75         let ty::Polytype { ty, .. } =
  76             ccx.get_item_ty(lang_item);
  77         ccx.tcx.intrinsic_defs.borrow_mut().insert(lang_item, ty);
  78     }
  79
  80     match ccx.tcx.lang_items.ty_desc() {
  81         Some(id) => { collect_intrinsic_type(ccx, id); }
  82         None => {}
  83     }
  84     match ccx.tcx.lang_items.opaque() {
  85         Some(id) => { collect_intrinsic_type(ccx, id); }
  86         None => {}
  87     }
  88
  89     let mut visitor = CollectTraitDefVisitor{ ccx: ccx };
  90     visit::walk_crate(&mut visitor, ccx.tcx.map.krate());
  91
  92     let mut visitor = CollectItemTypesVisitor{ ccx: ccx };
  93     visit::walk_crate(&mut visitor, ccx.tcx.map.krate());
  94 }
  95
  96 ///////////////////////////////////////////////////////////////////////////
  97 // First phase: just collect *trait definitions* -- basically, the set
  98 // of type parameters and supertraits. This is information we need to
  99 // know later when parsing field defs.
 100
 101 struct CollectTraitDefVisitor<'a, 'tcx: 'a> {
 102     ccx: &'a CrateCtxt<'a, 'tcx>
 103 }
 104
 105 impl<'a, 'tcx, 'v> visit::Visitor<'v> for CollectTraitDefVisitor<'a, 'tcx> {
 106     fn visit_item(&mut self, i: &ast::Item) {
 107         match i.node {
 108             ast::ItemTrait(..) => {
 109                 // computing the trait def also fills in the table
 110                 let _ = trait_def_of_item(self.ccx, i);
 111             }
 112             _ => { }
 113         }
 114
 115         visit::walk_item(self, i);
 116     }
 117 }
 118
 119 ///////////////////////////////////////////////////////////////////////////
 120 // Second phase: collection proper.
 121
 122 struct CollectItemTypesVisitor<'a, 'tcx: 'a> {
 123     ccx: &'a CrateCtxt<'a, 'tcx>
 124 }
 125
 126 impl<'a, 'tcx, 'v> visit::Visitor<'v> for CollectItemTypesVisitor<'a, 'tcx> {
 127     fn visit_item(&mut self, i: &ast::Item) {
 128         convert(self.ccx, i);
 129         visit::walk_item(self, i);
 130     }
 131     fn visit_foreign_item(&mut self, i: &ast::ForeignItem) {
 132         convert_foreign(self.ccx, i);
 133         visit::walk_foreign_item(self, i);
 134     }
 135 }
 136
 137 ///////////////////////////////////////////////////////////////////////////
 138 // Utility types and common code for the above passes.
 139
 140 pub trait ToTy<'tcx> {
 141     fn to_ty<RS:RegionScope>(&self, rs: &RS, ast_ty: &ast::Ty) -> Ty<'tcx>;
 142 }
 143
 144 impl<'a,'tcx> ToTy<'tcx> for ImplCtxt<'a,'tcx> {
 145     fn to_ty<RS:RegionScope>(&self, rs: &RS, ast_ty: &ast::Ty) -> Ty<'tcx> {
 146         ast_ty_to_ty(self, rs, ast_ty)
 147     }
 148 }
 149
 150 impl<'a,'tcx> ToTy<'tcx> for CrateCtxt<'a,'tcx> {
 151     fn to_ty<RS:RegionScope>(&self, rs: &RS, ast_ty: &ast::Ty) -> Ty<'tcx> {
 152         ast_ty_to_ty(self, rs, ast_ty)
 153     }
 154 }
 155
 156 impl<'a, 'tcx> AstConv<'tcx> for CrateCtxt<'a, 'tcx> {
 157     fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> { self.tcx }
 158
 159     fn get_item_ty(&self, id: ast::DefId) -> ty::Polytype<'tcx> {
 160         if id.krate != ast::LOCAL_CRATE {
 161             return csearch::get_type(self.tcx, id)
 162         }
 163
 164         match self.tcx.map.find(id.node) {
 165             Some(ast_map::NodeItem(item)) => ty_of_item(self, &*item),
 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             Some(ast_map::NodeTraitItem(trait_item)) => {
 171                 ty_of_trait_item(self, &*trait_item)
 172             }
 173             x => {
 174                 self.tcx.sess.bug(format!("unexpected sort of node \
 175                                            in get_item_ty(): {}",
 176                                           x).as_slice());
 177             }
 178         }
 179     }
 180
 181     fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef<'tcx>> {
 182         get_trait_def(self, id)
 183     }
 184
 185     fn ty_infer(&self, span: Span) -> Ty<'tcx> {
 186         span_err!(self.tcx.sess, span, E0121,
 187                   "the type placeholder `_` is not allowed within types on item signatures.");
 188         ty::mk_err()
 189     }
 190
 191     fn associated_types_of_trait_are_valid(&self, _: Ty<'tcx>, _: ast::DefId)
 192                                            -> bool {
 193         false
 194     }
 195
 196     fn associated_type_binding(&self,
 197                                span: Span,
 198                                _: Option<Ty<'tcx>>,
 199                                _: ast::DefId,
 200                                _: ast::DefId)
 201                                -> Ty<'tcx> {
 202         self.tcx().sess.span_err(span, "associated types may not be \
 203                                         referenced here");
 204         ty::mk_err()
 205     }
 206 }
 207
 208 pub fn get_enum_variant_types<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 209                                         enum_ty: Ty<'tcx>,
 210                                         variants: &[P<ast::Variant>],
 211                                         generics: &ast::Generics) {
 212     let tcx = ccx.tcx;
 213
 214     // Create a set of parameter types shared among all the variants.
 215     for variant in variants.iter() {
 216         // Nullary enum constructors get turned into constants; n-ary enum
 217         // constructors get turned into functions.
 218         let result_ty = match variant.node.kind {
 219             ast::TupleVariantKind(ref args) if args.len() > 0 => {
 220                 let rs = ExplicitRscope;
 221                 let input_tys: Vec<_> = args.iter().map(|va| ccx.to_ty(&rs, &*va.ty)).collect();
 222                 ty::mk_ctor_fn(tcx, input_tys.as_slice(), enum_ty)
 223             }
 224
 225             ast::TupleVariantKind(_) => {
 226                 enum_ty
 227             }
 228
 229             ast::StructVariantKind(ref struct_def) => {
 230                 let pty = Polytype {
 231                     generics: ty_generics_for_type(
 232                         ccx,
 233                         generics,
 234                         DontCreateTypeParametersForAssociatedTypes),
 235                     ty: enum_ty
 236                 };
 237
 238                 convert_struct(ccx, &**struct_def, pty, variant.node.id);
 239                 enum_ty
 240             }
 241         };
 242
 243         let pty = Polytype {
 244             generics: ty_generics_for_type(
 245                           ccx,
 246                           generics,
 247                           DontCreateTypeParametersForAssociatedTypes),
 248             ty: result_ty
 249         };
 250
 251         tcx.tcache.borrow_mut().insert(local_def(variant.node.id), pty);
 252
 253         write_ty_to_tcx(tcx, variant.node.id, result_ty);
 254     }
 255 }
 256
 257 fn collect_trait_methods<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 258                                    trait_id: ast::NodeId,
 259                                    trait_def: &ty::TraitDef<'tcx>) {
 260     let tcx = ccx.tcx;
 261     match tcx.map.get(trait_id) {
 262         ast_map::NodeItem(item) => {
 263             match item.node {
 264                 ast::ItemTrait(_, _, _, ref trait_items) => {
 265                     // For each method, construct a suitable ty::Method and
 266                     // store it into the `tcx.impl_or_trait_items` table:
 267                     for trait_item in trait_items.iter() {
 268                         match *trait_item {
 269                             ast::RequiredMethod(_) |
 270                             ast::ProvidedMethod(_) => {
 271                                 let ty_method = Rc::new(match *trait_item {
 272                                     ast::RequiredMethod(ref m) => {
 273                                         ty_method_of_trait_method(
 274                                             ccx,
 275                                             trait_id,
 276                                             &trait_def.generics,
 277                                             trait_items.as_slice(),
 278                                             &m.id,
 279                                             &m.ident.name,
 280                                             &m.explicit_self,
 281                                             m.abi,
 282                                             &m.generics,
 283                                             &m.fn_style,
 284                                             &*m.decl)
 285                                     }
 286                                     ast::ProvidedMethod(ref m) => {
 287                                         ty_method_of_trait_method(
 288                                             ccx,
 289                                             trait_id,
 290                                             &trait_def.generics,
 291                                             trait_items.as_slice(),
 292                                             &m.id,
 293                                             &m.pe_ident().name,
 294                                             m.pe_explicit_self(),
 295                                             m.pe_abi(),
 296                                             m.pe_generics(),
 297                                             &m.pe_fn_style(),
 298                                             &*m.pe_fn_decl())
 299                                     }
 300                                     ast::TypeTraitItem(ref at) => {
 301                                         tcx.sess.span_bug(at.ty_param.span,
 302                                                           "there shouldn't \
 303                                                            be a type trait \
 304                                                            item here")
 305                                     }
 306                                 });
 307
 308                                 debug!("ty_method_of_trait_method yielded {} \
 309                                         for method {} of trait {}",
 310                                        ty_method.repr(ccx.tcx),
 311                                        trait_item.repr(ccx.tcx),
 312                                        local_def(trait_id).repr(ccx.tcx));
 313
 314                                 make_method_ty(ccx, &*ty_method);
 315
 316                                 tcx.impl_or_trait_items
 317                                    .borrow_mut()
 318                                    .insert(ty_method.def_id,
 319                                            ty::MethodTraitItem(ty_method));
 320                             }
 321                             ast::TypeTraitItem(ref ast_associated_type) => {
 322                                 let trait_did = local_def(trait_id);
 323                                 let associated_type = ty::AssociatedType {
 324                                     name: ast_associated_type.ty_param.ident.name,
 325                                     vis: ast::Public,
 326                                     def_id: local_def(ast_associated_type.ty_param.id),
 327                                     container: TraitContainer(trait_did),
 328                                 };
 329
 330                                 let trait_item = ty::TypeTraitItem(Rc::new(
 331                                         associated_type));
 332                                 tcx.impl_or_trait_items
 333                                    .borrow_mut()
 334                                    .insert(associated_type.def_id,
 335                                            trait_item);
 336                             }
 337                         }
 338                     }
 339
 340                     // Add an entry mapping
 341                     let trait_item_def_ids =
 342                         Rc::new(trait_items.iter()
 343                                            .map(|ti| {
 344                             match *ti {
 345                                 ast::RequiredMethod(ref ty_method) => {
 346                                     ty::MethodTraitItemId(local_def(
 347                                             ty_method.id))
 348                                 }
 349                                 ast::ProvidedMethod(ref method) => {
 350                                     ty::MethodTraitItemId(local_def(
 351                                             method.id))
 352                                 }
 353                                 ast::TypeTraitItem(ref typedef) => {
 354                                     ty::TypeTraitItemId(local_def(typedef.ty_param.id))
 355                                 }
 356                             }
 357                         }).collect());
 358
 359                     let trait_def_id = local_def(trait_id);
 360                     tcx.trait_item_def_ids.borrow_mut()
 361                         .insert(trait_def_id, trait_item_def_ids);
 362                 }
 363                 _ => {} // Ignore things that aren't traits.
 364             }
 365         }
 366         _ => { /* Ignore things that aren't traits */ }
 367     }
 368
 369     fn make_method_ty<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, m: &ty::Method<'tcx>) {
 370         ccx.tcx.tcache.borrow_mut().insert(
 371             m.def_id,
 372             Polytype {
 373                 generics: m.generics.clone(),
 374                 ty: ty::mk_bare_fn(ccx.tcx, m.fty.clone()) });
 375     }
 376
 377     fn ty_method_of_trait_method<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 378                                            trait_id: ast::NodeId,
 379                                            trait_generics: &ty::Generics<'tcx>,
 380                                            trait_items: &[ast::TraitItem],
 381                                            m_id: &ast::NodeId,
 382                                            m_name: &ast::Name,
 383                                            m_explicit_self: &ast::ExplicitSelf,
 384                                            m_abi: abi::Abi,
 385                                            m_generics: &ast::Generics,
 386                                            m_fn_style: &ast::FnStyle,
 387                                            m_decl: &ast::FnDecl)
 388                                            -> ty::Method<'tcx> {
 389         let ty_generics =
 390             ty_generics_for_fn_or_method(
 391                 ccx,
 392                 m_generics,
 393                 (*trait_generics).clone(),
 394                 DontCreateTypeParametersForAssociatedTypes);
 395
 396         let (fty, explicit_self_category) = {
 397             let tmcx = TraitMethodCtxt {
 398                 ccx: ccx,
 399                 trait_id: local_def(trait_id),
 400                 trait_items: trait_items.as_slice(),
 401                 method_generics: &ty_generics,
 402             };
 403             let trait_self_ty = ty::mk_self_type(tmcx.tcx(),
 404                                                  local_def(trait_id));
 405             astconv::ty_of_method(&tmcx,
 406                                   *m_fn_style,
 407                                   trait_self_ty,
 408                                   m_explicit_self,
 409                                   m_decl,
 410                                   m_abi)
 411         };
 412
 413         ty::Method::new(
 414             *m_name,
 415             ty_generics,
 416             fty,
 417             explicit_self_category,
 418             // assume public, because this is only invoked on trait methods
 419             ast::Public,
 420             local_def(*m_id),
 421             TraitContainer(local_def(trait_id)),
 422             None
 423         )
 424     }
 425 }
 426
 427 pub fn convert_field<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 428                                 struct_generics: &ty::Generics<'tcx>,
 429                                 v: &ast::StructField,
 430                                 origin: ast::DefId) -> ty::field_ty {
 431     let tt = ccx.to_ty(&ExplicitRscope, &*v.node.ty);
 432     write_ty_to_tcx(ccx.tcx, v.node.id, tt);
 433     /* add the field to the tcache */
 434     ccx.tcx.tcache.borrow_mut().insert(local_def(v.node.id),
 435                                        ty::Polytype {
 436                                            generics: struct_generics.clone(),
 437                                            ty: tt
 438                                        });
 439
 440     match v.node.kind {
 441         ast::NamedField(ident, visibility) => {
 442             ty::field_ty {
 443                 name: ident.name,
 444                 id: local_def(v.node.id),
 445                 vis: visibility,
 446                 origin: origin,
 447             }
 448         }
 449         ast::UnnamedField(visibility) => {
 450             ty::field_ty {
 451                 name: special_idents::unnamed_field.name,
 452                 id: local_def(v.node.id),
 453                 vis: visibility,
 454                 origin: origin,
 455             }
 456         }
 457     }
 458 }
 459
 460 fn convert_associated_type<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 461                                      trait_def: &ty::TraitDef<'tcx>,
 462                                      associated_type: &ast::AssociatedType)
 463                                      -> ty::Polytype<'tcx> {
 464     // Find the type parameter ID corresponding to this
 465     // associated type.
 466     let type_parameter_def = trait_def.generics
 467                                       .types
 468                                       .get_slice(subst::AssocSpace)
 469                                       .iter()
 470                                       .find(|def| {
 471         def.def_id == local_def(associated_type.ty_param.id)
 472     });
 473     let type_parameter_def = match type_parameter_def {
 474         Some(type_parameter_def) => type_parameter_def,
 475         None => {
 476             ccx.tcx().sess.span_bug(associated_type.ty_param.span,
 477                                     "`convert_associated_type()` didn't find \
 478                                      a type parameter ID corresponding to \
 479                                      this type")
 480         }
 481     };
 482     let param_type = ty::mk_param(ccx.tcx,
 483                                   type_parameter_def.space,
 484                                   type_parameter_def.index,
 485                                   local_def(associated_type.ty_param.id));
 486     ccx.tcx.tcache.borrow_mut().insert(local_def(associated_type.ty_param.id),
 487                                        Polytype {
 488                                         generics: ty::Generics::empty(),
 489                                         ty: param_type,
 490                                        });
 491     write_ty_to_tcx(ccx.tcx, associated_type.ty_param.id, param_type);
 492
 493     let associated_type = Rc::new(ty::AssociatedType {
 494         name: associated_type.ty_param.ident.name,
 495         vis: ast::Public,
 496         def_id: local_def(associated_type.ty_param.id),
 497         container: TraitContainer(trait_def.trait_ref.def_id),
 498     });
 499     ccx.tcx
 500        .impl_or_trait_items
 501        .borrow_mut()
 502        .insert(associated_type.def_id,
 503                ty::TypeTraitItem(associated_type));
 504
 505     Polytype {
 506         generics: ty::Generics::empty(),
 507         ty: param_type,
 508     }
 509 }
 510
 511 enum ConvertMethodContext<'a> {
 512     /// Used when converting implementation methods.
 513     ImplConvertMethodContext,
 514     /// Used when converting method signatures. The def ID is the def ID of
 515     /// the trait we're translating.
 516     TraitConvertMethodContext(ast::DefId, &'a [ast::TraitItem]),
 517 }
 518
 519 fn convert_methods<'a,'tcx,'i,I>(ccx: &CrateCtxt<'a, 'tcx>,
 520                                  convert_method_context: ConvertMethodContext,
 521                                  container: ImplOrTraitItemContainer,
 522                                  mut ms: I,
 523                                  untransformed_rcvr_ty: Ty<'tcx>,
 524                                  rcvr_ty_generics: &ty::Generics<'tcx>,
 525                                  rcvr_visibility: ast::Visibility)
 526                                  where I: Iterator<&'i ast::Method> {
 527     debug!("convert_methods(untransformed_rcvr_ty={}, \
 528             rcvr_ty_generics={})",
 529            untransformed_rcvr_ty.repr(ccx.tcx),
 530            rcvr_ty_generics.repr(ccx.tcx));
 531
 532     let tcx = ccx.tcx;
 533     let mut seen_methods = FnvHashSet::new();
 534     for m in ms {
 535         if !seen_methods.insert(m.pe_ident().repr(tcx)) {
 536             tcx.sess.span_err(m.span, "duplicate method in trait impl");
 537         }
 538
 539         let mty = Rc::new(ty_of_method(ccx,
 540                                        convert_method_context,
 541                                        container,
 542                                        m,
 543                                        untransformed_rcvr_ty,
 544                                        rcvr_ty_generics,
 545                                        rcvr_visibility));
 546         let fty = ty::mk_bare_fn(tcx, mty.fty.clone());
 547         debug!("method {} (id {}) has type {}",
 548                 m.pe_ident().repr(tcx),
 549                 m.id,
 550                 fty.repr(tcx));
 551         tcx.tcache.borrow_mut().insert(
 552             local_def(m.id),
 553             Polytype {
 554                 generics: mty.generics.clone(),
 555                 ty: fty
 556             });
 557
 558         write_ty_to_tcx(tcx, m.id, fty);
 559
 560         debug!("writing method type: def_id={} mty={}",
 561                mty.def_id, mty.repr(ccx.tcx));
 562
 563         tcx.impl_or_trait_items
 564            .borrow_mut()
 565            .insert(mty.def_id, ty::MethodTraitItem(mty));
 566     }
 567
 568     fn ty_of_method<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 569                     convert_method_context: ConvertMethodContext,
 570                               container: ImplOrTraitItemContainer,
 571                               m: &ast::Method,
 572                               untransformed_rcvr_ty: Ty<'tcx>,
 573                               rcvr_ty_generics: &ty::Generics<'tcx>,
 574                               rcvr_visibility: ast::Visibility)
 575                               -> ty::Method<'tcx> {
 576         let m_ty_generics =
 577             ty_generics_for_fn_or_method(
 578                 ccx,
 579                 m.pe_generics(),
 580                 (*rcvr_ty_generics).clone(),
 581                 CreateTypeParametersForAssociatedTypes);
 582
 583         let (fty, explicit_self_category) = match convert_method_context {
 584             ImplConvertMethodContext => {
 585                 let imcx = ImplMethodCtxt {
 586                     ccx: ccx,
 587                     method_generics: &m_ty_generics,
 588                 };
 589                 astconv::ty_of_method(&imcx,
 590                                       m.pe_fn_style(),
 591                                       untransformed_rcvr_ty,
 592                                       m.pe_explicit_self(),
 593                                       &*m.pe_fn_decl(),
 594                                       m.pe_abi())
 595             }
 596             TraitConvertMethodContext(trait_id, trait_items) => {
 597                 let tmcx = TraitMethodCtxt {
 598                     ccx: ccx,
 599                     trait_id: trait_id,
 600                     trait_items: trait_items,
 601                     method_generics: &m_ty_generics,
 602                 };
 603                 astconv::ty_of_method(&tmcx,
 604                                       m.pe_fn_style(),
 605                                       untransformed_rcvr_ty,
 606                                       m.pe_explicit_self(),
 607                                       &*m.pe_fn_decl(),
 608                                       m.pe_abi())
 609             }
 610         };
 611
 612         // if the method specifies a visibility, use that, otherwise
 613         // inherit the visibility from the impl (so `foo` in `pub impl
 614         // { fn foo(); }` is public, but private in `priv impl { fn
 615         // foo(); }`).
 616         let method_vis = m.pe_vis().inherit_from(rcvr_visibility);
 617
 618         ty::Method::new(m.pe_ident().name,
 619                         m_ty_generics,
 620                         fty,
 621                         explicit_self_category,
 622                         method_vis,
 623                         local_def(m.id),
 624                         container,
 625                         None)
 626     }
 627 }
 628
 629 pub fn ensure_no_ty_param_bounds(ccx: &CrateCtxt,
 630                                  span: Span,
 631                                  generics: &ast::Generics,
 632                                  thing: &'static str) {
 633     let mut warn = false;
 634
 635     for ty_param in generics.ty_params.iter() {
 636         for bound in ty_param.bounds.iter() {
 637             match *bound {
 638                 ast::TraitTyParamBound(..) => {
 639                     warn = true;
 640                 }
 641                 ast::RegionTyParamBound(..) => { }
 642             }
 643         }
 644
 645         match ty_param.unbound {
 646             Some(_) => { warn = true; }
 647             None => { }
 648         }
 649     }
 650
 651     if warn {
 652         // According to accepted RFC #XXX, we should
 653         // eventually accept these, but it will not be
 654         // part of this PR. Still, convert to warning to
 655         // make bootstrapping easier.
 656         span_warn!(ccx.tcx.sess, span, E0122,
 657                    "trait bounds are not (yet) enforced \
 658                    in {} definitions",
 659                    thing);
 660     }
 661 }
 662
 663 fn is_associated_type_valid_for_param(ty: Ty,
 664                                       trait_id: ast::DefId,
 665                                       generics: &ty::Generics)
 666                                       -> bool {
 667     match ty.sty {
 668         ty::ty_param(param_ty) => {
 669             let type_parameter = generics.types.get(param_ty.space,
 670                                                     param_ty.idx);
 671             for trait_bound in type_parameter.bounds.trait_bounds.iter() {
 672                 if trait_bound.def_id == trait_id {
 673                     return true
 674                 }
 675             }
 676         }
 677         _ => {}
 678     }
 679
 680     false
 681 }
 682
 683 fn find_associated_type_in_generics<'tcx>(tcx: &ty::ctxt<'tcx>,
 684                                           span: Span,
 685                                           ty: Option<Ty<'tcx>>,
 686                                           associated_type_id: ast::DefId,
 687                                           generics: &ty::Generics<'tcx>)
 688                                           -> Ty<'tcx>
 689 {
 690     debug!("find_associated_type_in_generics(ty={}, associated_type_id={}, generics={}",
 691            ty.repr(tcx), associated_type_id.repr(tcx), generics.repr(tcx));
 692
 693     let ty = match ty {
 694         None => {
 695             tcx.sess.span_bug(span,
 696                               "find_associated_type_in_generics(): no self \
 697                                type")
 698         }
 699         Some(ty) => ty,
 700     };
 701
 702     match ty.sty {
 703         ty::ty_param(ref param_ty) => {
 704             /*let type_parameter = generics.types.get(param_ty.space,
 705                                                     param_ty.idx);
 706             let param_id = type_parameter.def_id;*/
 707             let param_id = param_ty.def_id;
 708             for type_parameter in generics.types.iter() {
 709                 if type_parameter.def_id == associated_type_id
 710                     && type_parameter.associated_with == Some(param_id) {
 711                     return ty::mk_param_from_def(tcx, type_parameter);
 712                 }
 713             }
 714
 715             tcx.sess.span_err(
 716                 span,
 717                 format!("no suitable bound on `{}`",
 718                         ty.user_string(tcx))[]);
 719             ty::mk_err()
 720         }
 721         _ => {
 722             tcx.sess.span_err(
 723                 span,
 724                 "it is currently unsupported to access associated types except \
 725                  through a type parameter; this restriction will be lifted in time");
 726             ty::mk_err()
 727         }
 728     }
 729 }
 730
 731 fn type_is_self(ty: Ty) -> bool {
 732     match ty.sty {
 733         ty::ty_param(ref param_ty) if param_ty.is_self() => true,
 734         _ => false,
 735     }
 736 }
 737
 738 struct ImplCtxt<'a,'tcx:'a> {
 739     ccx: &'a CrateCtxt<'a,'tcx>,
 740     opt_trait_ref_id: Option<ast::DefId>,
 741     impl_items: &'a [ast::ImplItem],
 742     impl_generics: &'a ty::Generics<'tcx>,
 743 }
 744
 745 impl<'a,'tcx> AstConv<'tcx> for ImplCtxt<'a,'tcx> {
 746     fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
 747         self.ccx.tcx
 748     }
 749
 750     fn get_item_ty(&self, id: ast::DefId) -> ty::Polytype<'tcx> {
 751         self.ccx.get_item_ty(id)
 752     }
 753
 754     fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef<'tcx>> {
 755         self.ccx.get_trait_def(id)
 756     }
 757
 758     fn ty_infer(&self, span: Span) -> Ty<'tcx> {
 759         self.ccx.ty_infer(span)
 760     }
 761
 762     fn associated_types_of_trait_are_valid(&self,
 763                                            ty: Ty<'tcx>,
 764                                            trait_id: ast::DefId)
 765                                            -> bool {
 766         // OK if the trait with the associated type is the trait we're
 767         // implementing.
 768         match self.opt_trait_ref_id {
 769             Some(trait_ref_id) if trait_ref_id == trait_id => {
 770                 if type_is_self(ty) {
 771                     return true
 772                 }
 773             }
 774             Some(_) | None => {}
 775         }
 776
 777         // OK if the trait with the associated type is one of the traits in
 778         // our bounds.
 779         is_associated_type_valid_for_param(ty, trait_id, self.impl_generics)
 780     }
 781
 782     fn associated_type_binding(&self,
 783                                span: Span,
 784                                ty: Option<Ty<'tcx>>,
 785                                trait_id: ast::DefId,
 786                                associated_type_id: ast::DefId)
 787                                -> Ty<'tcx>
 788     {
 789         let trait_def = ty::lookup_trait_def(self.tcx(), trait_id);
 790         match self.opt_trait_ref_id {
 791             Some(trait_ref_id) if trait_ref_id == trait_id => {
 792                 // It's an associated type on the trait that we're
 793                 // implementing.
 794                 assert!(trait_def.generics.types
 795                         .get_slice(subst::AssocSpace)
 796                         .iter()
 797                         .any(|type_param_def| type_param_def.def_id == associated_type_id));
 798                 let associated_type = ty::impl_or_trait_item(self.ccx.tcx, associated_type_id);
 799                 for impl_item in self.impl_items.iter() {
 800                     match *impl_item {
 801                         ast::MethodImplItem(_) => {}
 802                         ast::TypeImplItem(ref typedef) => {
 803                             if associated_type.name() == typedef.ident.name {
 804                                 return self.ccx.to_ty(&ExplicitRscope, &*typedef.typ)
 805                             }
 806                         }
 807                     }
 808                 }
 809                 self.ccx
 810                     .tcx
 811                     .sess
 812                     .span_bug(span,
 813                               "ImplCtxt::associated_type_binding(): didn't \
 814                                find associated type")
 815             }
 816             Some(_) | None => {}
 817         }
 818
 819         // OK then, it should be an associated type on one of the traits in
 820         // our bounds.
 821         find_associated_type_in_generics(self.ccx.tcx,
 822                                          span,
 823                                          ty,
 824                                          associated_type_id,
 825                                          self.impl_generics)
 826     }
 827 }
 828
 829 struct FnCtxt<'a,'tcx:'a> {
 830     ccx: &'a CrateCtxt<'a,'tcx>,
 831     generics: &'a ty::Generics<'tcx>,
 832 }
 833
 834 impl<'a,'tcx> AstConv<'tcx> for FnCtxt<'a,'tcx> {
 835     fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
 836         self.ccx.tcx
 837     }
 838
 839     fn get_item_ty(&self, id: ast::DefId) -> ty::Polytype<'tcx> {
 840         self.ccx.get_item_ty(id)
 841     }
 842
 843     fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef<'tcx>> {
 844         self.ccx.get_trait_def(id)
 845     }
 846
 847     fn ty_infer(&self, span: Span) -> Ty<'tcx> {
 848         self.ccx.ty_infer(span)
 849     }
 850
 851     fn associated_types_of_trait_are_valid(&self,
 852                                            ty: Ty<'tcx>,
 853                                            trait_id: ast::DefId)
 854                                            -> bool {
 855         // OK if the trait with the associated type is one of the traits in
 856         // our bounds.
 857         is_associated_type_valid_for_param(ty, trait_id, self.generics)
 858     }
 859
 860     fn associated_type_binding(&self,
 861                                span: Span,
 862                                ty: Option<Ty<'tcx>>,
 863                                _: ast::DefId,
 864                                associated_type_id: ast::DefId)
 865                                -> Ty<'tcx> {
 866         debug!("collect::FnCtxt::associated_type_binding()");
 867
 868         // The ID should map to an associated type on one of the traits in
 869         // our bounds.
 870         find_associated_type_in_generics(self.ccx.tcx,
 871                                          span,
 872                                          ty,
 873                                          associated_type_id,
 874                                          self.generics)
 875     }
 876 }
 877
 878 struct ImplMethodCtxt<'a,'tcx:'a> {
 879     ccx: &'a CrateCtxt<'a,'tcx>,
 880     method_generics: &'a ty::Generics<'tcx>,
 881 }
 882
 883 impl<'a,'tcx> AstConv<'tcx> for ImplMethodCtxt<'a,'tcx> {
 884     fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
 885         self.ccx.tcx
 886     }
 887
 888     fn get_item_ty(&self, id: ast::DefId) -> ty::Polytype<'tcx> {
 889         self.ccx.get_item_ty(id)
 890     }
 891
 892     fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef<'tcx>> {
 893         self.ccx.get_trait_def(id)
 894     }
 895
 896     fn ty_infer(&self, span: Span) -> Ty<'tcx> {
 897         self.ccx.ty_infer(span)
 898     }
 899
 900     fn associated_types_of_trait_are_valid(&self,
 901                                            ty: Ty<'tcx>,
 902                                            trait_id: ast::DefId)
 903                                            -> bool {
 904         is_associated_type_valid_for_param(ty, trait_id, self.method_generics)
 905     }
 906
 907     fn associated_type_binding(&self,
 908                                span: Span,
 909                                ty: Option<Ty<'tcx>>,
 910                                _: ast::DefId,
 911                                associated_type_id: ast::DefId)
 912                                -> Ty<'tcx> {
 913         debug!("collect::ImplMethodCtxt::associated_type_binding()");
 914
 915         // The ID should map to an associated type on one of the traits in
 916         // our bounds.
 917         find_associated_type_in_generics(self.ccx.tcx,
 918                                          span,
 919                                          ty,
 920                                          associated_type_id,
 921                                          self.method_generics)
 922     }
 923 }
 924
 925 struct TraitMethodCtxt<'a,'tcx:'a> {
 926     ccx: &'a CrateCtxt<'a,'tcx>,
 927     trait_id: ast::DefId,
 928     trait_items: &'a [ast::TraitItem],
 929     method_generics: &'a ty::Generics<'tcx>,
 930 }
 931
 932 impl<'a,'tcx> AstConv<'tcx> for TraitMethodCtxt<'a,'tcx> {
 933     fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
 934         self.ccx.tcx
 935     }
 936
 937     fn get_item_ty(&self, id: ast::DefId) -> ty::Polytype<'tcx> {
 938         self.ccx.get_item_ty(id)
 939     }
 940
 941     fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef<'tcx>> {
 942         self.ccx.get_trait_def(id)
 943     }
 944
 945     fn ty_infer(&self, span: Span) -> Ty<'tcx> {
 946         self.ccx.ty_infer(span)
 947     }
 948
 949     fn associated_types_of_trait_are_valid(&self,
 950                                            ty: Ty<'tcx>,
 951                                            trait_id: ast::DefId)
 952                                            -> bool {
 953         // OK if the trait with the associated type is this trait.
 954         if self.trait_id == trait_id && type_is_self(ty) {
 955             return true
 956         }
 957
 958         // OK if the trait with the associated type is one of the traits in
 959         // our bounds.
 960         is_associated_type_valid_for_param(ty, trait_id, self.method_generics)
 961     }
 962
 963     fn associated_type_binding(&self,
 964                                span: Span,
 965                                ty: Option<Ty<'tcx>>,
 966                                trait_id: ast::DefId,
 967                                associated_type_id: ast::DefId)
 968                                -> Ty<'tcx> {
 969         debug!("collect::TraitMethodCtxt::associated_type_binding()");
 970
 971         // If this is one of our own associated types, return it.
 972         if trait_id == self.trait_id {
 973             let mut index = 0;
 974             for item in self.trait_items.iter() {
 975                 match *item {
 976                     ast::RequiredMethod(_) | ast::ProvidedMethod(_) => {}
 977                     ast::TypeTraitItem(ref item) => {
 978                         if local_def(item.ty_param.id) == associated_type_id {
 979                             return ty::mk_param(self.tcx(),
 980                                                 subst::AssocSpace,
 981                                                 index,
 982                                                 associated_type_id)
 983                         }
 984                         index += 1;
 985                     }
 986                 }
 987             }
 988             self.ccx
 989                 .tcx
 990                 .sess
 991                 .span_bug(span,
 992                           "TraitMethodCtxt::associated_type_binding(): \
 993                            didn't find associated type anywhere in the item \
 994                            list")
 995         }
 996
 997         // The ID should map to an associated type on one of the traits in
 998         // our bounds.
 999         find_associated_type_in_generics(self.ccx.tcx,
1000                                          span,
1001                                          ty,
1002                                          associated_type_id,
1003                                          self.method_generics)
1004     }
1005 }
1006
1007 struct GenericsCtxt<'a,'tcx:'a,AC:'a> {
1008     chain: &'a AC,
1009     associated_types_generics: &'a ty::Generics<'tcx>,
1010 }
1011
1012 impl<'a,'tcx,AC:AstConv<'tcx>> AstConv<'tcx> for GenericsCtxt<'a,'tcx,AC> {
1013     fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
1014         self.chain.tcx()
1015     }
1016
1017     fn get_item_ty(&self, id: ast::DefId) -> ty::Polytype<'tcx> {
1018         self.chain.get_item_ty(id)
1019     }
1020
1021     fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef<'tcx>> {
1022         self.chain.get_trait_def(id)
1023     }
1024
1025     fn ty_infer(&self, span: Span) -> Ty<'tcx> {
1026         self.chain.ty_infer(span)
1027     }
1028
1029     fn associated_types_of_trait_are_valid(&self,
1030                                            ty: Ty<'tcx>,
1031                                            trait_id: ast::DefId)
1032                                            -> bool {
1033         // OK if the trait with the associated type is one of the traits in
1034         // our bounds.
1035         is_associated_type_valid_for_param(ty,
1036                                            trait_id,
1037                                            self.associated_types_generics)
1038     }
1039
1040     fn associated_type_binding(&self,
1041                                span: Span,
1042                                ty: Option<Ty<'tcx>>,
1043                                _: ast::DefId,
1044                                associated_type_id: ast::DefId)
1045                                -> Ty<'tcx> {
1046         debug!("collect::GenericsCtxt::associated_type_binding()");
1047
1048         // The ID should map to an associated type on one of the traits in
1049         // our bounds.
1050         find_associated_type_in_generics(self.chain.tcx(),
1051                                          span,
1052                                          ty,
1053                                          associated_type_id,
1054                                          self.associated_types_generics)
1055     }
1056 }
1057
1058 pub fn convert(ccx: &CrateCtxt, it: &ast::Item) {
1059     let tcx = ccx.tcx;
1060     debug!("convert: item {} with id {}", token::get_ident(it.ident), it.id);
1061     match it.node {
1062         // These don't define types.
1063         ast::ItemForeignMod(_) | ast::ItemMod(_) | ast::ItemMac(_) => {}
1064         ast::ItemEnum(ref enum_definition, ref generics) => {
1065             let pty = ty_of_item(ccx, it);
1066             write_ty_to_tcx(tcx, it.id, pty.ty);
1067             get_enum_variant_types(ccx,
1068                                    pty.ty,
1069                                    enum_definition.variants.as_slice(),
1070                                    generics);
1071         },
1072         ast::ItemImpl(ref generics,
1073                       ref opt_trait_ref,
1074                       ref selfty,
1075                       ref impl_items) => {
1076             // Create generics from the generics specified in the impl head.
1077             let ty_generics = ty_generics_for_type(
1078                     ccx,
1079                     generics,
1080                     CreateTypeParametersForAssociatedTypes);
1081
1082             let selfty = ccx.to_ty(&ExplicitRscope, &**selfty);
1083             write_ty_to_tcx(tcx, it.id, selfty);
1084
1085             tcx.tcache
1086                .borrow_mut()
1087                .insert(local_def(it.id),
1088                        Polytype {
1089                         generics: ty_generics.clone(),
1090                         ty: selfty,
1091                        });
1092
1093             // If there is a trait reference, treat the methods as always public.
1094             // This is to work around some incorrect behavior in privacy checking:
1095             // when the method belongs to a trait, it should acquire the privacy
1096             // from the trait, not the impl. Forcing the visibility to be public
1097             // makes things sorta work.
1098             let parent_visibility = if opt_trait_ref.is_some() {
1099                 ast::Public
1100             } else {
1101                 it.vis
1102             };
1103
1104             let icx = ImplCtxt {
1105                 ccx: ccx,
1106                 opt_trait_ref_id: match *opt_trait_ref {
1107                     None => None,
1108                     Some(ref ast_trait_ref) => {
1109                         Some(lookup_def_tcx(tcx,
1110                                             ast_trait_ref.path.span,
1111                                             ast_trait_ref.ref_id).def_id())
1112                     }
1113                 },
1114                 impl_items: impl_items.as_slice(),
1115                 impl_generics: &ty_generics,
1116             };
1117
1118             let mut methods = Vec::new();
1119             for impl_item in impl_items.iter() {
1120                 match *impl_item {
1121                     ast::MethodImplItem(ref method) => {
1122                         let body_id = method.pe_body().id;
1123                         check_method_self_type(ccx,
1124                                                &BindingRscope::new(),
1125                                                selfty,
1126                                                method.pe_explicit_self(),
1127                                                body_id);
1128                         methods.push(&**method);
1129                     }
1130                     ast::TypeImplItem(ref typedef) => {
1131                         let typ = icx.to_ty(&ExplicitRscope, &*typedef.typ);
1132                         tcx.tcache
1133                            .borrow_mut()
1134                            .insert(local_def(typedef.id),
1135                                    Polytype {
1136                                     generics: ty::Generics::empty(),
1137                                     ty: typ,
1138                                    });
1139                         write_ty_to_tcx(ccx.tcx, typedef.id, typ);
1140
1141                         let associated_type = Rc::new(ty::AssociatedType {
1142                             name: typedef.ident.name,
1143                             vis: typedef.vis,
1144                             def_id: local_def(typedef.id),
1145                             container: ty::ImplContainer(local_def(it.id)),
1146                         });
1147                         tcx.impl_or_trait_items
1148                            .borrow_mut()
1149                            .insert(local_def(typedef.id),
1150                                    ty::TypeTraitItem(associated_type));
1151                     }
1152                 }
1153             }
1154
1155             convert_methods(ccx,
1156                             ImplConvertMethodContext,
1157                             ImplContainer(local_def(it.id)),
1158                             methods.into_iter(),
1159                             selfty,
1160                             &ty_generics,
1161                             parent_visibility);
1162
1163             for trait_ref in opt_trait_ref.iter() {
1164                 astconv::instantiate_trait_ref(&icx, &ExplicitRscope, trait_ref,
1165                                                Some(selfty));
1166             }
1167         },
1168         ast::ItemTrait(_, _, _, ref trait_methods) => {
1169             let trait_def = trait_def_of_item(ccx, it);
1170
1171             debug!("trait_def: ident={} trait_def={}",
1172                    it.ident.repr(ccx.tcx),
1173                    trait_def.repr(ccx.tcx()));
1174
1175             for trait_method in trait_methods.iter() {
1176                 let self_type = ty::mk_param(ccx.tcx,
1177                                              subst::SelfSpace,
1178                                              0,
1179                                              local_def(it.id));
1180                 match *trait_method {
1181                     ast::RequiredMethod(ref type_method) => {
1182                         let rscope = BindingRscope::new();
1183                         check_method_self_type(ccx,
1184                                                &rscope,
1185                                                self_type,
1186                                                &type_method.explicit_self,
1187                                                it.id)
1188                     }
1189                     ast::ProvidedMethod(ref method) => {
1190                         check_method_self_type(ccx,
1191                                                &BindingRscope::new(),
1192                                                self_type,
1193                                                method.pe_explicit_self(),
1194                                                it.id)
1195                     }
1196                     ast::TypeTraitItem(ref associated_type) => {
1197                         convert_associated_type(ccx,
1198                                                 &*trait_def,
1199                                                 &**associated_type);
1200                     }
1201                 }
1202             }
1203
1204             // Run convert_methods on the provided methods.
1205             let untransformed_rcvr_ty = ty::mk_self_type(tcx,
1206                                                          local_def(it.id));
1207             let convert_method_context =
1208                 TraitConvertMethodContext(local_def(it.id),
1209                                           trait_methods.as_slice());
1210             convert_methods(ccx,
1211                             convert_method_context,
1212                             TraitContainer(local_def(it.id)),
1213                             trait_methods.iter().filter_map(|m| match *m {
1214                                 ast::RequiredMethod(_) => None,
1215                                 ast::ProvidedMethod(ref m) => Some(&**m),
1216                                 ast::TypeTraitItem(_) => None,
1217                             }),
1218                             untransformed_rcvr_ty,
1219                             &trait_def.generics,
1220                             it.vis);
1221
1222             // We need to do this *after* converting methods, since
1223             // convert_methods produces a tcache entry that is wrong for
1224             // static trait methods. This is somewhat unfortunate.
1225             collect_trait_methods(ccx, it.id, &*trait_def);
1226         },
1227         ast::ItemStruct(ref struct_def, _) => {
1228             // Write the class type.
1229             let pty = ty_of_item(ccx, it);
1230             write_ty_to_tcx(tcx, it.id, pty.ty);
1231
1232             tcx.tcache.borrow_mut().insert(local_def(it.id), pty.clone());
1233
1234             convert_struct(ccx, &**struct_def, pty, it.id);
1235         },
1236         ast::ItemTy(_, ref generics) => {
1237             ensure_no_ty_param_bounds(ccx, it.span, generics, "type");
1238             let tpt = ty_of_item(ccx, it);
1239             write_ty_to_tcx(tcx, it.id, tpt.ty);
1240         },
1241         _ => {
1242             // This call populates the type cache with the converted type
1243             // of the item in passing. All we have to do here is to write
1244             // it into the node type table.
1245             let pty = ty_of_item(ccx, it);
1246             write_ty_to_tcx(tcx, it.id, pty.ty);
1247         },
1248     }
1249 }
1250
1251 pub fn convert_struct<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1252                                 struct_def: &ast::StructDef,
1253                                 pty: ty::Polytype<'tcx>,
1254                                 id: ast::NodeId) {
1255     let tcx = ccx.tcx;
1256
1257     // Write the type of each of the members and check for duplicate fields.
1258     let mut seen_fields: FnvHashMap<ast::Name, Span> = FnvHashMap::new();
1259     let field_tys = struct_def.fields.iter().map(|f| {
1260         let result = convert_field(ccx, &pty.generics, f, local_def(id));
1261
1262         if result.name != special_idents::unnamed_field.name {
1263             let dup = match seen_fields.get(&result.name) {
1264                 Some(prev_span) => {
1265                     span_err!(tcx.sess, f.span, E0124,
1266                               "field `{}` is already declared",
1267                               token::get_name(result.name));
1268                     span_note!(tcx.sess, *prev_span, "previously declared here");
1269                     true
1270                 },
1271                 None => false,
1272             };
1273             // FIXME(#6393) this whole dup thing is just to satisfy
1274             // the borrow checker :-(
1275             if !dup {
1276                 seen_fields.insert(result.name, f.span);
1277             }
1278         }
1279
1280         result
1281     }).collect();
1282
1283     tcx.struct_fields.borrow_mut().insert(local_def(id), Rc::new(field_tys));
1284
1285     let substs = mk_item_substs(ccx, &pty.generics);
1286     let selfty = ty::mk_struct(tcx, local_def(id), substs);
1287
1288     // If this struct is enum-like or tuple-like, create the type of its
1289     // constructor.
1290     match struct_def.ctor_id {
1291         None => {}
1292         Some(ctor_id) => {
1293             if struct_def.fields.len() == 0 {
1294                 // Enum-like.
1295                 write_ty_to_tcx(tcx, ctor_id, selfty);
1296
1297                 tcx.tcache.borrow_mut().insert(local_def(ctor_id), pty);
1298             } else if struct_def.fields[0].node.kind.is_unnamed() {
1299                 // Tuple-like.
1300                 let inputs: Vec<_> = struct_def.fields.iter().map(
1301                         |field| (*tcx.tcache.borrow())[
1302                             local_def(field.node.id)].ty).collect();
1303                 let ctor_fn_ty = ty::mk_ctor_fn(tcx,
1304                                                 inputs.as_slice(),
1305                                                 selfty);
1306                 write_ty_to_tcx(tcx, ctor_id, ctor_fn_ty);
1307                 tcx.tcache.borrow_mut().insert(local_def(ctor_id),
1308                                   Polytype {
1309                     generics: pty.generics,
1310                     ty: ctor_fn_ty
1311                 });
1312             }
1313         }
1314     }
1315 }
1316
1317 pub fn convert_foreign(ccx: &CrateCtxt, i: &ast::ForeignItem) {
1318     // As above, this call populates the type table with the converted
1319     // type of the foreign item. We simply write it into the node type
1320     // table.
1321
1322     // For reasons I cannot fully articulate, I do so hate the AST
1323     // map, and I regard each time that I use it as a personal and
1324     // moral failing, but at the moment it seems like the only
1325     // convenient way to extract the ABI. - ndm
1326     let abi = ccx.tcx.map.get_foreign_abi(i.id);
1327
1328     let pty = ty_of_foreign_item(ccx, i, abi);
1329     write_ty_to_tcx(ccx.tcx, i.id, pty.ty);
1330
1331     ccx.tcx.tcache.borrow_mut().insert(local_def(i.id), pty);
1332 }
1333
1334 fn get_trait_def<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1335                            trait_id: ast::DefId)
1336                            -> Rc<ty::TraitDef<'tcx>> {
1337     if trait_id.krate != ast::LOCAL_CRATE {
1338         return ty::lookup_trait_def(ccx.tcx, trait_id)
1339     }
1340
1341     match ccx.tcx.map.get(trait_id.node) {
1342         ast_map::NodeItem(item) => trait_def_of_item(ccx, &*item),
1343         _ => {
1344             ccx.tcx.sess.bug(format!("get_trait_def({}): not an item",
1345                                      trait_id.node).as_slice())
1346         }
1347     }
1348 }
1349
1350 pub fn trait_def_of_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1351                                    it: &ast::Item)
1352                                    -> Rc<ty::TraitDef<'tcx>> {
1353     let def_id = local_def(it.id);
1354     let tcx = ccx.tcx;
1355     match tcx.trait_defs.borrow().get(&def_id) {
1356         Some(def) => return def.clone(),
1357         _ => {}
1358     }
1359
1360     let (generics, unbound, bounds, items) = match it.node {
1361         ast::ItemTrait(ref generics,
1362                        ref unbound,
1363                        ref supertraits,
1364                        ref items) => {
1365             (generics, unbound, supertraits, items.as_slice())
1366         }
1367         ref s => {
1368             tcx.sess.span_bug(
1369                 it.span,
1370                 format!("trait_def_of_item invoked on {}", s).as_slice());
1371         }
1372     };
1373
1374     let substs = mk_trait_substs(ccx, it.id, generics, items);
1375
1376     let ty_generics = ty_generics_for_trait(ccx,
1377                                             it.id,
1378                                             &substs,
1379                                             generics,
1380                                             items);
1381
1382     let self_param_ty = ty::ParamTy::for_self(def_id);
1383
1384     let bounds = compute_bounds(ccx, token::SELF_KEYWORD_NAME, self_param_ty,
1385                                 bounds.as_slice(), unbound, it.span,
1386                                 &generics.where_clause);
1387
1388     let substs = mk_item_substs(ccx, &ty_generics);
1389     let trait_def = Rc::new(ty::TraitDef {
1390         generics: ty_generics,
1391         bounds: bounds,
1392         trait_ref: Rc::new(ty::TraitRef {
1393             def_id: def_id,
1394             substs: substs
1395         })
1396     });
1397     tcx.trait_defs.borrow_mut().insert(def_id, trait_def.clone());
1398
1399     return trait_def;
1400
1401     fn mk_trait_substs<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1402                                  trait_id: ast::NodeId,
1403                                  generics: &ast::Generics,
1404                                  items: &[ast::TraitItem])
1405                                  -> subst::Substs<'tcx>
1406     {
1407         // Creates a no-op substitution for the trait's type parameters.
1408         let regions =
1409             generics.lifetimes
1410                     .iter()
1411                     .enumerate()
1412                     .map(|(i, def)| ty::ReEarlyBound(def.lifetime.id,
1413                                                      subst::TypeSpace,
1414                                                      i,
1415                                                      def.lifetime.name))
1416                     .collect();
1417
1418         // Start with the generics in the type parameters...
1419         let types: Vec<_> =
1420             generics.ty_params
1421                     .iter()
1422                     .enumerate()
1423                     .map(|(i, def)| ty::mk_param(ccx.tcx, subst::TypeSpace,
1424                                                  i, local_def(def.id)))
1425                     .collect();
1426
1427         // ...and also create generics synthesized from the associated types.
1428         let assoc_types: Vec<_> =
1429             items.iter()
1430             .flat_map(|item| match *item {
1431                 ast::TypeTraitItem(ref trait_item) => {
1432                     let index = types.len();
1433                     Some(ty::mk_param(ccx.tcx,
1434                                       subst::AssocSpace,
1435                                       index,
1436                                       local_def(trait_item.ty_param.id))).into_iter()
1437                 }
1438                 ast::RequiredMethod(_) | ast::ProvidedMethod(_) => {
1439                     None.into_iter()
1440                 }
1441             })
1442             .collect();
1443
1444         let self_ty =
1445             ty::mk_param(ccx.tcx, subst::SelfSpace, 0, local_def(trait_id));
1446
1447         subst::Substs::new_trait(types, regions, assoc_types, self_ty)
1448     }
1449 }
1450
1451 pub fn ty_of_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, it: &ast::Item)
1452                             -> ty::Polytype<'tcx> {
1453     let def_id = local_def(it.id);
1454     let tcx = ccx.tcx;
1455     match tcx.tcache.borrow().get(&def_id) {
1456         Some(pty) => return pty.clone(),
1457         _ => {}
1458     }
1459     match it.node {
1460         ast::ItemStatic(ref t, _, _) | ast::ItemConst(ref t, _) => {
1461             let typ = ccx.to_ty(&ExplicitRscope, &**t);
1462             let pty = no_params(typ);
1463
1464             tcx.tcache.borrow_mut().insert(local_def(it.id), pty.clone());
1465             return pty;
1466         }
1467         ast::ItemFn(ref decl, fn_style, abi, ref generics, _) => {
1468             let ty_generics = ty_generics_for_fn_or_method(
1469                 ccx,
1470                 generics,
1471                 ty::Generics::empty(),
1472                 CreateTypeParametersForAssociatedTypes);
1473             let tofd = {
1474                 let fcx = FnCtxt {
1475                     ccx: ccx,
1476                     generics: &ty_generics,
1477                 };
1478                 astconv::ty_of_bare_fn(&fcx, fn_style, abi, &**decl)
1479             };
1480             let pty = Polytype {
1481                 generics: ty_generics,
1482                 ty: ty::mk_bare_fn(ccx.tcx, tofd)
1483             };
1484             debug!("type of {} (id {}) is {}",
1485                     token::get_ident(it.ident),
1486                     it.id,
1487                     pty.repr(tcx));
1488
1489             ccx.tcx.tcache.borrow_mut().insert(local_def(it.id), pty.clone());
1490             return pty;
1491         }
1492         ast::ItemTy(ref t, ref generics) => {
1493             match tcx.tcache.borrow_mut().get(&local_def(it.id)) {
1494                 Some(pty) => return pty.clone(),
1495                 None => { }
1496             }
1497
1498             let pty = {
1499                 let ty = ccx.to_ty(&ExplicitRscope, &**t);
1500                 Polytype {
1501                     generics: ty_generics_for_type(
1502                                   ccx,
1503                                   generics,
1504                                   DontCreateTypeParametersForAssociatedTypes),
1505                     ty: ty
1506                 }
1507             };
1508
1509             tcx.tcache.borrow_mut().insert(local_def(it.id), pty.clone());
1510             return pty;
1511         }
1512         ast::ItemEnum(_, ref generics) => {
1513             // Create a new generic polytype.
1514             let ty_generics = ty_generics_for_type(
1515                 ccx,
1516                 generics,
1517                 DontCreateTypeParametersForAssociatedTypes);
1518             let substs = mk_item_substs(ccx, &ty_generics);
1519             let t = ty::mk_enum(tcx, local_def(it.id), substs);
1520             let pty = Polytype {
1521                 generics: ty_generics,
1522                 ty: t
1523             };
1524
1525             tcx.tcache.borrow_mut().insert(local_def(it.id), pty.clone());
1526             return pty;
1527         }
1528         ast::ItemTrait(..) => {
1529             tcx.sess.span_bug(it.span, "invoked ty_of_item on trait");
1530         }
1531         ast::ItemStruct(_, ref generics) => {
1532             let ty_generics = ty_generics_for_type(
1533                 ccx,
1534                 generics,
1535                 DontCreateTypeParametersForAssociatedTypes);
1536             let substs = mk_item_substs(ccx, &ty_generics);
1537             let t = ty::mk_struct(tcx, local_def(it.id), substs);
1538             let pty = Polytype {
1539                 generics: ty_generics,
1540                 ty: t
1541             };
1542
1543             tcx.tcache.borrow_mut().insert(local_def(it.id), pty.clone());
1544             return pty;
1545         }
1546         ast::ItemImpl(..) | ast::ItemMod(_) |
1547         ast::ItemForeignMod(_) | ast::ItemMac(_) => panic!(),
1548     }
1549 }
1550
1551 pub fn ty_of_foreign_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1552                                     it: &ast::ForeignItem,
1553                                     abi: abi::Abi) -> ty::Polytype<'tcx>
1554 {
1555     match it.node {
1556         ast::ForeignItemFn(ref fn_decl, ref generics) => {
1557             ty_of_foreign_fn_decl(ccx,
1558                                   &**fn_decl,
1559                                   local_def(it.id),
1560                                   generics,
1561                                   abi)
1562         }
1563         ast::ForeignItemStatic(ref t, _) => {
1564             ty::Polytype {
1565                 generics: ty::Generics::empty(),
1566                 ty: ast_ty_to_ty(ccx, &ExplicitRscope, &**t)
1567             }
1568         }
1569     }
1570 }
1571
1572 fn ty_of_trait_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1573                               trait_item: &ast::TraitItem)
1574                               -> ty::Polytype<'tcx> {
1575     match *trait_item {
1576         ast::RequiredMethod(ref m) => {
1577             ccx.tcx.sess.span_bug(m.span,
1578                                   "ty_of_trait_item() on required method")
1579         }
1580         ast::ProvidedMethod(ref m) => {
1581             ccx.tcx.sess.span_bug(m.span,
1582                                   "ty_of_trait_item() on provided method")
1583         }
1584         ast::TypeTraitItem(ref associated_type) => {
1585             let parent = ccx.tcx.map.get_parent(associated_type.ty_param.id);
1586             let trait_def = match ccx.tcx.map.get(parent) {
1587                 ast_map::NodeItem(item) => trait_def_of_item(ccx, &*item),
1588                 _ => {
1589                     ccx.tcx.sess.span_bug(associated_type.ty_param.span,
1590                                           "associated type's parent wasn't \
1591                                            an item?!")
1592                 }
1593             };
1594             convert_associated_type(ccx, &*trait_def, &**associated_type)
1595         }
1596     }
1597 }
1598
1599 fn ty_generics_for_type<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1600                                   generics: &ast::Generics,
1601                                   create_type_parameters_for_associated_types:
1602                                       CreateTypeParametersForAssociatedTypesFlag)
1603                                   -> ty::Generics<'tcx> {
1604     ty_generics(ccx,
1605                 subst::TypeSpace,
1606                 generics.lifetimes.as_slice(),
1607                 generics.ty_params.as_slice(),
1608                 ty::Generics::empty(),
1609                 &generics.where_clause,
1610                 create_type_parameters_for_associated_types)
1611 }
1612
1613 fn ty_generics_for_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1614                                    trait_id: ast::NodeId,
1615                                    substs: &subst::Substs<'tcx>,
1616                                    ast_generics: &ast::Generics,
1617                                    items: &[ast::TraitItem])
1618                                    -> ty::Generics<'tcx> {
1619     let mut generics =
1620         ty_generics(ccx,
1621                     subst::TypeSpace,
1622                     ast_generics.lifetimes.as_slice(),
1623                     ast_generics.ty_params.as_slice(),
1624                     ty::Generics::empty(),
1625                     &ast_generics.where_clause,
1626                     DontCreateTypeParametersForAssociatedTypes);
1627
1628     // Add in type parameters for any associated types.
1629     for item in items.iter() {
1630         match *item {
1631             ast::TypeTraitItem(ref associated_type) => {
1632                 let def =
1633                     get_or_create_type_parameter_def(
1634                         ccx,
1635                         subst::AssocSpace,
1636                         &associated_type.ty_param,
1637                         generics.types.len(subst::AssocSpace),
1638                         &ast_generics.where_clause,
1639                         Some(local_def(trait_id)));
1640                 ccx.tcx.ty_param_defs.borrow_mut().insert(associated_type.ty_param.id,
1641                                                           def.clone());
1642                 generics.types.push(subst::AssocSpace, def);
1643             }
1644             ast::ProvidedMethod(_) | ast::RequiredMethod(_) => {}
1645         }
1646     }
1647
1648     // Add in the self type parameter.
1649     //
1650     // Something of a hack: use the node id for the trait, also as
1651     // the node id for the Self type parameter.
1652     let param_id = trait_id;
1653
1654     let self_trait_ref =
1655         Rc::new(ty::TraitRef { def_id: local_def(trait_id),
1656                                substs: (*substs).clone() });
1657
1658     let def = ty::TypeParameterDef {
1659         space: subst::SelfSpace,
1660         index: 0,
1661         name: special_idents::type_self.name,
1662         def_id: local_def(param_id),
1663         bounds: ty::ParamBounds {
1664             region_bounds: vec!(),
1665             builtin_bounds: ty::empty_builtin_bounds(),
1666             trait_bounds: vec!(self_trait_ref),
1667         },
1668         associated_with: None,
1669         default: None
1670     };
1671
1672     ccx.tcx.ty_param_defs.borrow_mut().insert(param_id, def.clone());
1673
1674     generics.types.push(subst::SelfSpace, def);
1675
1676     generics
1677 }
1678
1679 fn ty_generics_for_fn_or_method<'tcx,AC>(
1680         this: &AC,
1681         generics: &ast::Generics,
1682         base_generics: ty::Generics<'tcx>,
1683         create_type_parameters_for_associated_types:
1684         CreateTypeParametersForAssociatedTypesFlag)
1685         -> ty::Generics<'tcx>
1686         where AC: AstConv<'tcx> {
1687     let early_lifetimes = resolve_lifetime::early_bound_lifetimes(generics);
1688     ty_generics(this,
1689                 subst::FnSpace,
1690                 early_lifetimes.as_slice(),
1691                 generics.ty_params.as_slice(),
1692                 base_generics,
1693                 &generics.where_clause,
1694                 create_type_parameters_for_associated_types)
1695 }
1696
1697 // Add the Sized bound, unless the type parameter is marked as `Sized?`.
1698 fn add_unsized_bound<'tcx,AC>(this: &AC,
1699                               unbound: &Option<ast::TraitRef>,
1700                               bounds: &mut ty::BuiltinBounds,
1701                               desc: &str,
1702                               span: Span)
1703                               where AC: AstConv<'tcx> {
1704     let kind_id = this.tcx().lang_items.require(SizedTraitLangItem);
1705     match unbound {
1706         &Some(ref tpb) => {
1707             // FIXME(#8559) currently requires the unbound to be built-in.
1708             let trait_def_id = ty::trait_ref_to_def_id(this.tcx(), tpb);
1709             match kind_id {
1710                 Ok(kind_id) if trait_def_id != kind_id => {
1711                     this.tcx().sess.span_warn(span,
1712                                               format!("default bound relaxed \
1713                                                        for a {}, but this \
1714                                                        does nothing because \
1715                                                        the given bound is not \
1716                                                        a default. \
1717                                                        Only `Sized?` is \
1718                                                        supported.",
1719                                                       desc).as_slice());
1720                     ty::try_add_builtin_trait(this.tcx(),
1721                                               kind_id,
1722                                               bounds);
1723                 }
1724                 _ => {}
1725             }
1726         }
1727         _ if kind_id.is_ok() => {
1728             ty::try_add_builtin_trait(this.tcx(), kind_id.unwrap(), bounds);
1729         }
1730         // No lang item for Sized, so we can't add it as a bound.
1731         &None => {}
1732     }
1733 }
1734
1735 #[deriving(Clone, PartialEq, Eq)]
1736 enum CreateTypeParametersForAssociatedTypesFlag {
1737     DontCreateTypeParametersForAssociatedTypes,
1738     CreateTypeParametersForAssociatedTypes,
1739 }
1740
1741 fn ty_generics<'tcx,AC>(this: &AC,
1742                         space: subst::ParamSpace,
1743                         lifetime_defs: &[ast::LifetimeDef],
1744                         types: &[ast::TyParam],
1745                         base_generics: ty::Generics<'tcx>,
1746                         where_clause: &ast::WhereClause,
1747                         create_type_parameters_for_associated_types_flag:
1748                         CreateTypeParametersForAssociatedTypesFlag)
1749                         -> ty::Generics<'tcx>
1750                         where AC: AstConv<'tcx>
1751 {
1752     let mut result = base_generics;
1753
1754     for (i, l) in lifetime_defs.iter().enumerate() {
1755         let bounds = l.bounds.iter()
1756                              .map(|l| ast_region_to_region(this.tcx(), l))
1757                              .collect();
1758         let def = ty::RegionParameterDef { name: l.lifetime.name,
1759                                            space: space,
1760                                            index: i,
1761                                            def_id: local_def(l.lifetime.id),
1762                                            bounds: bounds };
1763         debug!("ty_generics: def for region param: {}", def);
1764         result.regions.push(space, def);
1765     }
1766
1767     assert!(result.types.is_empty_in(space));
1768
1769     // First, create the virtual type parameters for associated types if
1770     // necessary.
1771     let mut associated_types_generics = ty::Generics::empty();
1772     match create_type_parameters_for_associated_types_flag {
1773         DontCreateTypeParametersForAssociatedTypes => {}
1774         CreateTypeParametersForAssociatedTypes => {
1775             create_type_parameters_for_associated_types(this, space, types,
1776                                                         &mut associated_types_generics);
1777         }
1778     }
1779
1780     // Now create the real type parameters.
1781     let gcx = GenericsCtxt {
1782         chain: this,
1783         associated_types_generics: &associated_types_generics,
1784     };
1785     for (i, param) in types.iter().enumerate() {
1786         let def = get_or_create_type_parameter_def(&gcx,
1787                                                    space,
1788                                                    param,
1789                                                    i,
1790                                                    where_clause,
1791                                                    None);
1792         debug!("ty_generics: def for type param: {}, {}",
1793                def.repr(this.tcx()),
1794                space);
1795         result.types.push(space, def);
1796     }
1797
1798     // Append the associated types to the result.
1799     for associated_type_param in associated_types_generics.types
1800                                                           .get_slice(space)
1801                                                           .iter() {
1802         assert!(result.types.get_slice(space).len() ==
1803                 associated_type_param.index);
1804         debug!("ty_generics: def for associated type: {}, {}",
1805                associated_type_param.repr(this.tcx()),
1806                space);
1807         result.types.push(space, (*associated_type_param).clone());
1808     }
1809
1810     return result;
1811
1812     fn create_type_parameters_for_associated_types<'tcx,AC>(
1813         this: &AC,
1814         space: subst::ParamSpace,
1815         types: &[ast::TyParam],
1816         associated_types_generics: &mut ty::Generics<'tcx>)
1817         where AC: AstConv<'tcx>
1818     {
1819         // The idea here is roughly as follows. We start with
1820         // an item that is paramerized by various type parameters
1821         // with bounds:
1822         //
1823         //    fn foo<T:Iterator>(t: T) { ... }
1824         //
1825         // The traits in those bounds declare associated types:
1826         //
1827         //    trait Iterator { type Elem; ... }
1828         //
1829         // And we rewrite the original function so that every associated
1830         // type is bound to some fresh type parameter:
1831         //
1832         //    fn foo<A,T:Iterator<Elem=A>>(t: T) { ... }
1833
1834         // Number of synthetic type parameters created thus far
1835         let mut index = 0;
1836
1837         // Iterate over the each type parameter `T` (from the example)
1838         for param in types.iter() {
1839             // Iterate over the bound `Iterator`
1840             for bound in param.bounds.iter() {
1841                 // In the above example, `ast_trait_ref` is `Iterator`.
1842                 let ast_trait_ref = match *bound {
1843                     ast::TraitTyParamBound(ref r) => r,
1844                     ast::RegionTyParamBound(..) => { continue; }
1845                 };
1846
1847                 let trait_def_id =
1848                     match lookup_def_tcx(this.tcx(),
1849                                          ast_trait_ref.trait_ref.path.span,
1850                                          ast_trait_ref.trait_ref.ref_id) {
1851                         def::DefTrait(trait_def_id) => trait_def_id,
1852                         _ => {
1853                             this.tcx().sess.span_bug(ast_trait_ref.trait_ref.path.span,
1854                                                      "not a trait?!")
1855                         }
1856                     };
1857
1858                 // trait_def_id is def-id of `Iterator`
1859                 let trait_def = ty::lookup_trait_def(this.tcx(), trait_def_id);
1860                 let associated_type_defs = trait_def.generics.types.get_slice(subst::AssocSpace);
1861
1862                 // Iterate over each associated type `Elem`
1863                 for associated_type_def in associated_type_defs.iter() {
1864                     // Create the fresh type parameter `A`
1865                     let def = ty::TypeParameterDef {
1866                         name: associated_type_def.name,
1867                         def_id: associated_type_def.def_id,
1868                         space: space,
1869                         index: types.len() + index,
1870                         bounds: ty::ParamBounds {
1871                             builtin_bounds: associated_type_def.bounds.builtin_bounds,
1872
1873                             // FIXME(#18178) -- we should add the other bounds, but
1874                             // that requires subst and more logic
1875                             trait_bounds: Vec::new(),
1876                             region_bounds: Vec::new(),
1877                         },
1878                         associated_with: Some(local_def(param.id)),
1879                         default: None,
1880                     };
1881                     associated_types_generics.types.push(space, def);
1882                     index += 1;
1883                 }
1884             }
1885         }
1886     }
1887 }
1888
1889 fn get_or_create_type_parameter_def<'tcx,AC>(this: &AC,
1890                                              space: subst::ParamSpace,
1891                                              param: &ast::TyParam,
1892                                              index: uint,
1893                                              where_clause: &ast::WhereClause,
1894                                              associated_with: Option<ast::DefId>)
1895                                              -> ty::TypeParameterDef<'tcx>
1896     where AC: AstConv<'tcx>
1897 {
1898     match this.tcx().ty_param_defs.borrow().get(&param.id) {
1899         Some(d) => { return (*d).clone(); }
1900         None => { }
1901     }
1902
1903     let param_ty = ty::ParamTy::new(space, index, local_def(param.id));
1904     let bounds = compute_bounds(this,
1905                                 param.ident.name,
1906                                 param_ty,
1907                                 param.bounds.as_slice(),
1908                                 &param.unbound,
1909                                 param.span,
1910                                 where_clause);
1911     let default = match param.default {
1912         None => None,
1913         Some(ref path) => {
1914             let ty = ast_ty_to_ty(this, &ExplicitRscope, &**path);
1915             let cur_idx = index;
1916
1917             ty::walk_ty(ty, |t| {
1918                 match t.sty {
1919                     ty::ty_param(p) => if p.idx > cur_idx {
1920                         span_err!(this.tcx().sess, path.span, E0128,
1921                                   "type parameters with a default cannot use \
1922                                    forward declared identifiers");
1923                         },
1924                         _ => {}
1925                     }
1926             });
1927
1928             Some(ty)
1929         }
1930     };
1931
1932     let def = ty::TypeParameterDef {
1933         space: space,
1934         index: index,
1935         name: param.ident.name,
1936         def_id: local_def(param.id),
1937         associated_with: associated_with,
1938         bounds: bounds,
1939         default: default
1940     };
1941
1942     this.tcx().ty_param_defs.borrow_mut().insert(param.id, def.clone());
1943
1944     def
1945 }
1946
1947 /// Translate the AST's notion of ty param bounds (which are an enum consisting of a newtyped Ty or
1948 /// a region) to ty's notion of ty param bounds, which can either be user-defined traits, or the
1949 /// built-in trait (formerly known as kind): Send.
1950 fn compute_bounds<'tcx,AC>(this: &AC,
1951                            name_of_bounded_thing: ast::Name,
1952                            param_ty: ty::ParamTy,
1953                            ast_bounds: &[ast::TyParamBound],
1954                            unbound: &Option<ast::TraitRef>,
1955                            span: Span,
1956                            where_clause: &ast::WhereClause)
1957                            -> ty::ParamBounds<'tcx>
1958                            where AC: AstConv<'tcx> {
1959     let mut param_bounds = conv_param_bounds(this,
1960                                              span,
1961                                              param_ty,
1962                                              ast_bounds,
1963                                              where_clause);
1964
1965
1966     add_unsized_bound(this,
1967                       unbound,
1968                       &mut param_bounds.builtin_bounds,
1969                       "type parameter",
1970                       span);
1971
1972     check_bounds_compatible(this.tcx(),
1973                             name_of_bounded_thing,
1974                             &param_bounds,
1975                             span);
1976
1977     param_bounds.trait_bounds.sort_by(|a,b| a.def_id.cmp(&b.def_id));
1978
1979     param_bounds
1980 }
1981
1982 fn check_bounds_compatible<'tcx>(tcx: &ty::ctxt<'tcx>,
1983                                  name_of_bounded_thing: ast::Name,
1984                                  param_bounds: &ty::ParamBounds<'tcx>,
1985                                  span: Span) {
1986     // Currently the only bound which is incompatible with other bounds is
1987     // Sized/Unsized.
1988     if !param_bounds.builtin_bounds.contains(&ty::BoundSized) {
1989         ty::each_bound_trait_and_supertraits(
1990             tcx,
1991             param_bounds.trait_bounds.as_slice(),
1992             |trait_ref| {
1993                 let trait_def = ty::lookup_trait_def(tcx, trait_ref.def_id);
1994                 if trait_def.bounds.builtin_bounds.contains(&ty::BoundSized) {
1995                     span_err!(tcx.sess, span, E0129,
1996                               "incompatible bounds on type parameter `{}`, \
1997                                bound `{}` does not allow unsized type",
1998                               name_of_bounded_thing.user_string(tcx),
1999                               ppaux::trait_ref_to_string(tcx, &*trait_ref));
2000                 }
2001                 true
2002             });
2003     }
2004 }
2005
2006 fn conv_param_bounds<'tcx,AC>(this: &AC,
2007                               span: Span,
2008                               param_ty: ty::ParamTy,
2009                               ast_bounds: &[ast::TyParamBound],
2010                               where_clause: &ast::WhereClause)
2011                               -> ty::ParamBounds<'tcx>
2012                               where AC: AstConv<'tcx> {
2013     let all_bounds =
2014         merge_param_bounds(this.tcx(), param_ty, ast_bounds, where_clause);
2015     let astconv::PartitionedBounds { builtin_bounds,
2016                                      trait_bounds,
2017                                      region_bounds } =
2018         astconv::partition_bounds(this.tcx(), span, all_bounds.as_slice());
2019     let trait_bounds: Vec<Rc<ty::TraitRef>> =
2020         trait_bounds.into_iter()
2021         .map(|bound| {
2022             astconv::instantiate_poly_trait_ref(this,
2023                                                 &ExplicitRscope,
2024                                                 bound,
2025                                                 Some(param_ty.to_ty(this.tcx())))
2026         })
2027         .collect();
2028     let region_bounds: Vec<ty::Region> =
2029         region_bounds.into_iter()
2030         .map(|r| ast_region_to_region(this.tcx(), r))
2031         .collect();
2032     ty::ParamBounds {
2033         region_bounds: region_bounds,
2034         builtin_bounds: builtin_bounds,
2035         trait_bounds: trait_bounds,
2036     }
2037 }
2038
2039 /// Merges the bounds declared on a type parameter with those found from where clauses into a
2040 /// single list.
2041 fn merge_param_bounds<'a>(tcx: &ty::ctxt,
2042                           param_ty: ty::ParamTy,
2043                           ast_bounds: &'a [ast::TyParamBound],
2044                           where_clause: &'a ast::WhereClause)
2045                           -> Vec<&'a ast::TyParamBound> {
2046     let mut result = Vec::new();
2047
2048     for ast_bound in ast_bounds.iter() {
2049         result.push(ast_bound);
2050     }
2051
2052     for predicate in where_clause.predicates.iter() {
2053         let predicate_param_id =
2054             tcx.def_map
2055                .borrow()
2056                .get(&predicate.id)
2057                .expect("compute_bounds(): resolve didn't resolve the type \
2058                         parameter identifier in a `where` clause")
2059                .def_id();
2060         if param_ty.def_id != predicate_param_id {
2061             continue
2062         }
2063         for bound in predicate.bounds.iter() {
2064             result.push(bound);
2065         }
2066     }
2067
2068     result
2069 }
2070
2071 pub fn ty_of_foreign_fn_decl<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
2072                                        decl: &ast::FnDecl,
2073                                        def_id: ast::DefId,
2074                                        ast_generics: &ast::Generics,
2075                                        abi: abi::Abi)
2076                                        -> ty::Polytype<'tcx> {
2077     for i in decl.inputs.iter() {
2078         match (*i).pat.node {
2079             ast::PatIdent(_, _, _) => (),
2080             ast::PatWild(ast::PatWildSingle) => (),
2081             _ => {
2082                 span_err!(ccx.tcx.sess, (*i).pat.span, E0130,
2083                           "patterns aren't allowed in foreign function declarations");
2084             }
2085         }
2086     }
2087
2088     let ty_generics_for_fn_or_method = ty_generics_for_fn_or_method(
2089             ccx,
2090             ast_generics,
2091             ty::Generics::empty(),
2092             DontCreateTypeParametersForAssociatedTypes);
2093     let rb = BindingRscope::new();
2094     let input_tys = decl.inputs
2095                         .iter()
2096                         .map(|a| ty_of_arg(ccx, &rb, a, None))
2097                         .collect();
2098
2099     let output = match decl.output {
2100         ast::Return(ref ty) =>
2101             ty::FnConverging(ast_ty_to_ty(ccx, &rb, &**ty)),
2102         ast::NoReturn(_) =>
2103             ty::FnDiverging
2104     };
2105
2106     let t_fn = ty::mk_bare_fn(
2107         ccx.tcx,
2108         ty::BareFnTy {
2109             abi: abi,
2110             fn_style: ast::UnsafeFn,
2111             sig: ty::FnSig {inputs: input_tys,
2112                             output: output,
2113                             variadic: decl.variadic}
2114         });
2115     let pty = Polytype {
2116         generics: ty_generics_for_fn_or_method,
2117         ty: t_fn
2118     };
2119
2120     ccx.tcx.tcache.borrow_mut().insert(def_id, pty.clone());
2121     return pty;
2122 }
2123
2124 pub fn mk_item_substs<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
2125                                 ty_generics: &ty::Generics<'tcx>)
2126                                 -> subst::Substs<'tcx>
2127 {
2128     let types =
2129         ty_generics.types.map(
2130             |def| ty::mk_param_from_def(ccx.tcx, def));
2131
2132     let regions =
2133         ty_generics.regions.map(
2134             |def| ty::ReEarlyBound(def.def_id.node, def.space,
2135                                    def.index, def.name));
2136
2137     subst::Substs::new(types, regions)
2138 }
2139
2140 /// Verifies that the explicit self type of a method matches the impl or
2141 /// trait.
2142 fn check_method_self_type<'a, 'tcx, RS:RegionScope>(
2143     crate_context: &CrateCtxt<'a, 'tcx>,
2144     rs: &RS,
2145     required_type: Ty<'tcx>,
2146     explicit_self: &ast::ExplicitSelf,
2147     body_id: ast::NodeId)
2148 {
2149     match explicit_self.node {
2150         ast::SelfExplicit(ref ast_type, _) => {
2151             let typ = crate_context.to_ty(rs, &**ast_type);
2152             let base_type = match typ.sty {
2153                 ty::ty_ptr(tm) | ty::ty_rptr(_, tm) => tm.ty,
2154                 ty::ty_uniq(typ) => typ,
2155                 _ => typ,
2156             };
2157
2158             let body_scope = region::CodeExtent::from_node_id(body_id);
2159
2160             // "Required type" comes from the trait definition. It may
2161             // contain late-bound regions from the method, but not the
2162             // trait (since traits only have early-bound region
2163             // parameters).
2164             assert!(!ty::type_escapes_depth(required_type, 1));
2165             let required_type_free =
2166                 ty::liberate_late_bound_regions(
2167                     crate_context.tcx, body_scope, &ty::bind(required_type)).value;
2168
2169             // The "base type" comes from the impl. It may have late-bound
2170             // regions from the impl or the method.
2171             let base_type_free = // liberate impl regions:
2172                 ty::liberate_late_bound_regions(
2173                     crate_context.tcx, body_scope, &ty::bind(ty::bind(base_type))).value.value;
2174             let base_type_free = // liberate method regions:
2175                 ty::liberate_late_bound_regions(
2176                     crate_context.tcx, body_scope, &ty::bind(base_type_free)).value;
2177
2178             debug!("required_type={} required_type_free={} \
2179                     base_type={} base_type_free={}",
2180                    required_type.repr(crate_context.tcx),
2181                    required_type_free.repr(crate_context.tcx),
2182                    base_type.repr(crate_context.tcx),
2183                    base_type_free.repr(crate_context.tcx));
2184             let infcx = infer::new_infer_ctxt(crate_context.tcx);
2185             drop(typeck::require_same_types(crate_context.tcx,
2186                                             Some(&infcx),
2187                                             false,
2188                                             explicit_self.span,
2189                                             base_type_free,
2190                                             required_type_free,
2191                                             || {
2192                 format!("mismatched self type: expected `{}`",
2193                         ppaux::ty_to_string(crate_context.tcx, required_type))
2194             }));
2195             infcx.resolve_regions_and_report_errors();
2196         }
2197         _ => {}
2198     }
2199 }