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