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::ty_param_bounds_and_ty`.  This combines the core type along with
  28 a list of the bounds for each parameter.  Type parameters themselves
  29 are represented as `ty_param()` instances.
  30
  31 */
  32
  33
  34 use metadata::csearch;
  35 use middle::resolve_lifetime;
  36 use middle::ty::{ImplContainer, MethodContainer, TraitContainer, substs};
  37 use middle::ty::{ty_param_bounds_and_ty};
  38 use middle::ty;
  39 use middle::subst::Subst;
  40 use middle::typeck::astconv::{AstConv, ty_of_arg};
  41 use middle::typeck::astconv::{ast_ty_to_ty};
  42 use middle::typeck::astconv;
  43 use middle::typeck::rscope::*;
  44 use middle::typeck::{CrateCtxt, lookup_def_tcx, no_params, write_ty_to_tcx};
  45 use util::ppaux;
  46 use util::ppaux::Repr;
  47
  48 use std::rc::Rc;
  49 use std::vec;
  50 use collections::HashSet;
  51
  52 use syntax::abi::AbiSet;
  53 use syntax::ast::{RegionTyParamBound, TraitTyParamBound};
  54 use syntax::ast;
  55 use syntax::ast_map;
  56 use syntax::ast_util::{local_def, split_trait_methods};
  57 use syntax::codemap::Span;
  58 use syntax::codemap;
  59 use syntax::parse::token::special_idents;
  60 use syntax::parse::token;
  61 use syntax::print::pprust::{path_to_str};
  62 use syntax::visit;
  63 use syntax::owned_slice::OwnedSlice;
  64
  65 struct CollectItemTypesVisitor<'a> {
  66     ccx: &'a CrateCtxt<'a>
  67 }
  68
  69 impl<'a> visit::Visitor<()> for CollectItemTypesVisitor<'a> {
  70     fn visit_item(&mut self, i: &ast::Item, _: ()) {
  71         convert(self.ccx, i);
  72         visit::walk_item(self, i, ());
  73     }
  74     fn visit_foreign_item(&mut self, i: &ast::ForeignItem, _: ()) {
  75         convert_foreign(self.ccx, i);
  76         visit::walk_foreign_item(self, i, ());
  77     }
  78 }
  79
  80 pub fn collect_item_types(ccx: &CrateCtxt, krate: &ast::Crate) {
  81     fn collect_intrinsic_type(ccx: &CrateCtxt,
  82                               lang_item: ast::DefId) {
  83         let ty::ty_param_bounds_and_ty { ty: ty, .. } =
  84             ccx.get_item_ty(lang_item);
  85         ccx.tcx.intrinsic_defs.borrow_mut().insert(lang_item, ty);
  86     }
  87
  88     match ccx.tcx.lang_items.ty_desc() {
  89         Some(id) => { collect_intrinsic_type(ccx, id); } None => {}
  90     }
  91     match ccx.tcx.lang_items.opaque() {
  92         Some(id) => { collect_intrinsic_type(ccx, id); } None => {}
  93     }
  94
  95     let mut visitor = CollectItemTypesVisitor{ ccx: ccx };
  96     visit::walk_crate(&mut visitor, krate, ());
  97 }
  98
  99 pub trait ToTy {
 100     fn to_ty<RS:RegionScope>(&self, rs: &RS, ast_ty: &ast::Ty) -> ty::t;
 101 }
 102
 103 impl<'a> ToTy for CrateCtxt<'a> {
 104     fn to_ty<RS:RegionScope>(&self, rs: &RS, ast_ty: &ast::Ty) -> ty::t {
 105         ast_ty_to_ty(self, rs, ast_ty)
 106     }
 107 }
 108
 109 impl<'a> AstConv for CrateCtxt<'a> {
 110     fn tcx<'a>(&'a self) -> &'a ty::ctxt { self.tcx }
 111
 112     fn get_item_ty(&self, id: ast::DefId) -> ty::ty_param_bounds_and_ty {
 113         if id.krate != ast::LOCAL_CRATE {
 114             return csearch::get_type(self.tcx, id)
 115         }
 116
 117         match self.tcx.map.find(id.node) {
 118             Some(ast_map::NodeItem(item)) => ty_of_item(self, item),
 119             Some(ast_map::NodeForeignItem(foreign_item)) => {
 120                 let abis = self.tcx.map.get_foreign_abis(id.node);
 121                 ty_of_foreign_item(self, foreign_item, abis)
 122             }
 123             x => {
 124                 self.tcx.sess.bug(format!("unexpected sort of node \
 125                                            in get_item_ty(): {:?}", x));
 126             }
 127         }
 128     }
 129
 130     fn get_trait_def(&self, id: ast::DefId) -> @ty::TraitDef {
 131         get_trait_def(self, id)
 132     }
 133
 134     fn ty_infer(&self, span: Span) -> ty::t {
 135         self.tcx.sess.span_err(span, "the type placeholder `_` is not \
 136                                       allowed within types on item signatures.");
 137         ty::mk_err()
 138     }
 139 }
 140
 141 pub fn get_enum_variant_types(ccx: &CrateCtxt,
 142                               enum_ty: ty::t,
 143                               variants: &[ast::P<ast::Variant>],
 144                               generics: &ast::Generics) {
 145     let tcx = ccx.tcx;
 146
 147     // Create a set of parameter types shared among all the variants.
 148     for variant in variants.iter() {
 149         // Nullary enum constructors get turned into constants; n-ary enum
 150         // constructors get turned into functions.
 151         let scope = variant.node.id;
 152         let result_ty = match variant.node.kind {
 153             ast::TupleVariantKind(ref args) if args.len() > 0 => {
 154                 let rs = ExplicitRscope;
 155                 let input_tys = args.map(|va| ccx.to_ty(&rs, va.ty));
 156                 ty::mk_ctor_fn(tcx, scope, input_tys.as_slice(), enum_ty)
 157             }
 158
 159             ast::TupleVariantKind(_) => {
 160                 enum_ty
 161             }
 162
 163             ast::StructVariantKind(struct_def) => {
 164                 let tpt = ty_param_bounds_and_ty {
 165                     generics: ty_generics_for_type(ccx, generics),
 166                     ty: enum_ty
 167                 };
 168
 169                 convert_struct(ccx, struct_def, tpt, variant.node.id);
 170
 171                 let input_tys = struct_def.fields.map(
 172                     |f| ty::node_id_to_type(ccx.tcx, f.node.id));
 173                 ty::mk_ctor_fn(tcx, scope, input_tys.as_slice(), enum_ty)
 174             }
 175         };
 176
 177         let tpt = ty_param_bounds_and_ty {
 178             generics: ty_generics_for_type(ccx, generics),
 179             ty: result_ty
 180         };
 181
 182         tcx.tcache.borrow_mut().insert(local_def(variant.node.id), tpt);
 183
 184         write_ty_to_tcx(tcx, variant.node.id, result_ty);
 185     }
 186 }
 187
 188 pub fn ensure_trait_methods(ccx: &CrateCtxt, trait_id: ast::NodeId) {
 189     let tcx = ccx.tcx;
 190     match tcx.map.get(trait_id) {
 191         ast_map::NodeItem(item) => {
 192             match item.node {
 193                 ast::ItemTrait(ref generics, _, ref ms) => {
 194                     let trait_ty_generics = ty_generics_for_type(ccx, generics);
 195
 196                     // For each method, construct a suitable ty::Method and
 197                     // store it into the `tcx.methods` table:
 198                     for m in ms.iter() {
 199                         let ty_method = @match m {
 200                             &ast::Required(ref m) => {
 201                                 ty_method_of_trait_method(
 202                                     ccx, trait_id, &trait_ty_generics,
 203                                     &m.id, &m.ident, &m.explicit_self,
 204                                     &m.generics, &m.purity, m.decl)
 205                             }
 206
 207                             &ast::Provided(ref m) => {
 208                                 ty_method_of_trait_method(
 209                                     ccx, trait_id, &trait_ty_generics,
 210                                     &m.id, &m.ident, &m.explicit_self,
 211                                     &m.generics, &m.purity, m.decl)
 212                             }
 213                         };
 214
 215                         if ty_method.explicit_self == ast::SelfStatic {
 216                             make_static_method_ty(ccx, trait_id, ty_method,
 217                                                   &trait_ty_generics);
 218                         }
 219
 220                         tcx.methods.borrow_mut().insert(ty_method.def_id,
 221                                                         ty_method);
 222                     }
 223
 224                     // Add an entry mapping
 225                     let method_def_ids = @ms.map(|m| {
 226                         match m {
 227                             &ast::Required(ref ty_method) => {
 228                                 local_def(ty_method.id)
 229                             }
 230                             &ast::Provided(ref method) => {
 231                                 local_def(method.id)
 232                             }
 233                         }
 234                     });
 235
 236                     let trait_def_id = local_def(trait_id);
 237                     tcx.trait_method_def_ids.borrow_mut()
 238                         .insert(trait_def_id, @method_def_ids.iter()
 239                                                              .map(|x| *x)
 240                                                              .collect());
 241                 }
 242                 _ => {} // Ignore things that aren't traits.
 243             }
 244         }
 245         _ => { /* Ignore things that aren't traits */ }
 246     }
 247
 248     fn make_static_method_ty(ccx: &CrateCtxt,
 249                              trait_id: ast::NodeId,
 250                              m: &ty::Method,
 251                              trait_ty_generics: &ty::Generics) {
 252         // If declaration is
 253         //
 254         //     trait Trait<'a,'b,'c,a,b,c> {
 255         //        fn foo<'d,'e,'f,d,e,f>(...) -> Self;
 256         //     }
 257         //
 258         // and we will create a function like
 259         //
 260         //     fn foo<'a,'b,'c,   // First the lifetime params from trait
 261         //            'd,'e,'f,   // Then lifetime params from `foo()`
 262         //            a,b,c,      // Then type params from trait
 263         //            D:Trait<'a,'b,'c,a,b,c>, // Then this sucker
 264         //            E,F,G       // Then type params from `foo()`, offset by 1
 265         //           >(...) -> D' {}
 266         //
 267         // Note that `Self` is replaced with an explicit type
 268         // parameter D that is sandwiched in between the trait params
 269         // and the method params, and thus the indices of the method
 270         // type parameters are offset by 1 (that is, the method
 271         // parameters are mapped from d, e, f to E, F, and G).  The
 272         // choice of this ordering is somewhat arbitrary.
 273         //
 274         // Note also that the bound for `D` is `Trait<'a,'b,'c,a,b,c>`.
 275         // This implies that the lifetime parameters that were inherited
 276         // from the trait (i.e., `'a`, `'b`, and `'c`) all must be early
 277         // bound, since they appear in a trait bound.
 278         //
 279         // Also, this system is rather a hack that should be replaced
 280         // with a more uniform treatment of Self (which is partly
 281         // underway).
 282
 283         // build up a subst that shifts all of the parameters over
 284         // by one and substitute in a new type param for self
 285
 286         let tcx = ccx.tcx;
 287
 288         let dummy_defid = ast::DefId {krate: 0, node: 0};
 289
 290         // Represents [A',B',C']
 291         let num_trait_bounds = trait_ty_generics.type_param_defs().len();
 292         let non_shifted_trait_tps = Vec::from_fn(num_trait_bounds, |i| {
 293             ty::mk_param(tcx, i, trait_ty_generics.type_param_defs()[i].def_id)
 294         });
 295
 296         // Represents [D']
 297         let self_param = ty::mk_param(tcx, num_trait_bounds,
 298                                       dummy_defid);
 299
 300         // Represents [E',F',G']
 301         let num_method_bounds = m.generics.type_param_defs().len();
 302         let shifted_method_tps = Vec::from_fn(num_method_bounds, |i| {
 303             ty::mk_param(tcx, i + num_trait_bounds + 1,
 304                          m.generics.type_param_defs()[i].def_id)
 305         });
 306
 307         // Convert the regions 'a, 'b, 'c defined on the trait into
 308         // bound regions on the fn. Note that because these appear in the
 309         // bound for `Self` they must be early bound.
 310         let new_early_region_param_defs = trait_ty_generics.region_param_defs.clone();
 311         let rps_from_trait =
 312             trait_ty_generics.region_param_defs().iter().
 313             enumerate().
 314             map(|(index,d)| ty::ReEarlyBound(d.def_id.node, index, d.name)).
 315             collect();
 316
 317         // build up the substitution from
 318         //     'a,'b,'c => 'a,'b,'c
 319         //     A,B,C => A',B',C'
 320         //     Self => D'
 321         //     D,E,F => E',F',G'
 322         let substs = substs {
 323             regions: ty::NonerasedRegions(rps_from_trait),
 324             self_ty: Some(self_param),
 325             tps: vec::append(non_shifted_trait_tps,
 326                                 shifted_method_tps.as_slice())
 327         };
 328
 329         // create the type of `foo`, applying the substitution above
 330         let ty = ty::subst(tcx,
 331                            &substs,
 332                            ty::mk_bare_fn(tcx, m.fty.clone()));
 333
 334         // create the type parameter definitions for `foo`, applying
 335         // the substitution to any traits that appear in their bounds.
 336
 337         // add in the type parameters from the trait
 338         let mut new_type_param_defs = Vec::new();
 339         let substd_type_param_defs =
 340             trait_ty_generics.type_param_defs.subst(tcx, &substs);
 341         new_type_param_defs.push_all(substd_type_param_defs.as_slice());
 342
 343         // add in the "self" type parameter
 344         let self_trait_def = get_trait_def(ccx, local_def(trait_id));
 345         let self_trait_ref = self_trait_def.trait_ref.subst(tcx, &substs);
 346         new_type_param_defs.push(ty::TypeParameterDef {
 347             ident: special_idents::self_,
 348             def_id: dummy_defid,
 349             bounds: @ty::ParamBounds {
 350                 builtin_bounds: ty::EmptyBuiltinBounds(),
 351                 trait_bounds: vec!(self_trait_ref)
 352             },
 353             default: None
 354         });
 355
 356         // add in the type parameters from the method
 357         let substd_type_param_defs = m.generics.type_param_defs.subst(tcx, &substs);
 358         new_type_param_defs.push_all(substd_type_param_defs.as_slice());
 359
 360         debug!("static method {} type_param_defs={} ty={}, substs={}",
 361                m.def_id.repr(tcx),
 362                new_type_param_defs.repr(tcx),
 363                ty.repr(tcx),
 364                substs.repr(tcx));
 365
 366         tcx.tcache.borrow_mut().insert(m.def_id,
 367                           ty_param_bounds_and_ty {
 368                               generics: ty::Generics {
 369                                   type_param_defs: Rc::new(new_type_param_defs),
 370                                   region_param_defs: new_early_region_param_defs
 371                               },
 372                               ty: ty
 373                           });
 374     }
 375
 376     fn ty_method_of_trait_method(this: &CrateCtxt,
 377                                  trait_id: ast::NodeId,
 378                                  trait_generics: &ty::Generics,
 379                                  m_id: &ast::NodeId,
 380                                  m_ident: &ast::Ident,
 381                                  m_explicit_self: &ast::ExplicitSelf,
 382                                  m_generics: &ast::Generics,
 383                                  m_purity: &ast::Purity,
 384                                  m_decl: &ast::FnDecl) -> ty::Method
 385     {
 386         let trait_self_ty = ty::mk_self(this.tcx, local_def(trait_id));
 387         let fty = astconv::ty_of_method(this, *m_id, *m_purity, trait_self_ty,
 388                                         *m_explicit_self, m_decl);
 389         let num_trait_type_params = trait_generics.type_param_defs().len();
 390         let ty_generics = ty_generics_for_fn_or_method(this, m_generics,
 391                                                        num_trait_type_params);
 392         ty::Method::new(
 393             *m_ident,
 394             ty_generics,
 395             fty,
 396             m_explicit_self.node,
 397             // assume public, because this is only invoked on trait methods
 398             ast::Public,
 399             local_def(*m_id),
 400             TraitContainer(local_def(trait_id)),
 401             None
 402         )
 403     }
 404 }
 405
 406 pub fn ensure_supertraits(ccx: &CrateCtxt,
 407                           id: ast::NodeId,
 408                           sp: codemap::Span,
 409                           ast_trait_refs: &[ast::TraitRef])
 410                           -> ty::BuiltinBounds
 411 {
 412     let tcx = ccx.tcx;
 413
 414     // Called only the first time trait_def_of_item is called.
 415     // Supertraits are ensured at the same time.
 416     assert!(!tcx.supertraits.borrow().contains_key(&local_def(id)));
 417
 418     let self_ty = ty::mk_self(ccx.tcx, local_def(id));
 419     let mut ty_trait_refs: Vec<@ty::TraitRef> = Vec::new();
 420     let mut bounds = ty::EmptyBuiltinBounds();
 421     for ast_trait_ref in ast_trait_refs.iter() {
 422         let trait_def_id = ty::trait_ref_to_def_id(ccx.tcx, ast_trait_ref);
 423         // FIXME(#8559): Need to instantiate the trait_ref whether or not it's a
 424         // builtin trait, so that the trait's node id appears in the tcx trait_ref
 425         // map. This is only needed for metadata; see the similar fixme in encoder.rs.
 426         let trait_ref = instantiate_trait_ref(ccx, ast_trait_ref, self_ty);
 427         if !ty::try_add_builtin_trait(ccx.tcx, trait_def_id, &mut bounds) {
 428
 429             // FIXME(#5527) Could have same trait multiple times
 430             if ty_trait_refs.iter().any(|other_trait| other_trait.def_id == trait_ref.def_id) {
 431                 // This means a trait inherited from the same supertrait more
 432                 // than once.
 433                 tcx.sess.span_err(sp, "duplicate supertrait in trait declaration");
 434                 break;
 435             } else {
 436                 ty_trait_refs.push(trait_ref);
 437             }
 438         }
 439     }
 440
 441     tcx.supertraits.borrow_mut().insert(local_def(id), @ty_trait_refs);
 442     bounds
 443 }
 444
 445 pub fn convert_field(ccx: &CrateCtxt,
 446                      struct_generics: &ty::Generics,
 447                      v: &ast::StructField) {
 448     let tt = ccx.to_ty(&ExplicitRscope, v.node.ty);
 449     write_ty_to_tcx(ccx.tcx, v.node.id, tt);
 450     /* add the field to the tcache */
 451     ccx.tcx.tcache.borrow_mut().insert(local_def(v.node.id),
 452                           ty::ty_param_bounds_and_ty {
 453                               generics: struct_generics.clone(),
 454                               ty: tt
 455                           });
 456 }
 457
 458 fn convert_methods(ccx: &CrateCtxt,
 459                    container: MethodContainer,
 460                    ms: &[@ast::Method],
 461                    untransformed_rcvr_ty: ty::t,
 462                    rcvr_ty_generics: &ty::Generics,
 463                    rcvr_ast_generics: &ast::Generics,
 464                    rcvr_visibility: ast::Visibility)
 465 {
 466     let tcx = ccx.tcx;
 467     let mut seen_methods = HashSet::new();
 468     for m in ms.iter() {
 469         if !seen_methods.insert(m.ident.repr(ccx.tcx)) {
 470             tcx.sess.span_err(m.span, "duplicate method in trait impl");
 471         }
 472
 473         let num_rcvr_ty_params = rcvr_ty_generics.type_param_defs().len();
 474         let m_ty_generics = ty_generics_for_fn_or_method(ccx, &m.generics,
 475                                                          num_rcvr_ty_params);
 476         let mty = @ty_of_method(ccx,
 477                                 container,
 478                                 *m,
 479                                 untransformed_rcvr_ty,
 480                                 rcvr_ast_generics,
 481                                 rcvr_visibility);
 482         let fty = ty::mk_bare_fn(tcx, mty.fty.clone());
 483         debug!("method {} (id {}) has type {}",
 484                 m.ident.repr(ccx.tcx),
 485                 m.id,
 486                 fty.repr(ccx.tcx));
 487         tcx.tcache.borrow_mut().insert(
 488             local_def(m.id),
 489
 490             // n.b.: the type of a method is parameterized by both
 491             // the parameters on the receiver and those on the method
 492             // itself
 493             ty_param_bounds_and_ty {
 494                 generics: ty::Generics {
 495                     type_param_defs: Rc::new(vec::append(
 496                         Vec::from_slice(
 497                             rcvr_ty_generics.type_param_defs()),
 498                         m_ty_generics.type_param_defs())),
 499                     region_param_defs: Rc::new(vec::append(
 500                             Vec::from_slice(rcvr_ty_generics.region_param_defs()),
 501                             m_ty_generics.region_param_defs())),
 502                 },
 503                 ty: fty
 504             });
 505
 506         write_ty_to_tcx(tcx, m.id, fty);
 507
 508         tcx.methods.borrow_mut().insert(mty.def_id, mty);
 509     }
 510
 511     fn ty_of_method(ccx: &CrateCtxt,
 512                     container: MethodContainer,
 513                     m: &ast::Method,
 514                     untransformed_rcvr_ty: ty::t,
 515                     rcvr_generics: &ast::Generics,
 516                     rcvr_visibility: ast::Visibility) -> ty::Method
 517     {
 518         let fty = astconv::ty_of_method(ccx, m.id, m.purity,
 519                                         untransformed_rcvr_ty,
 520                                         m.explicit_self, m.decl);
 521
 522         // if the method specifies a visibility, use that, otherwise
 523         // inherit the visibility from the impl (so `foo` in `pub impl
 524         // { fn foo(); }` is public, but private in `priv impl { fn
 525         // foo(); }`).
 526         let method_vis = m.vis.inherit_from(rcvr_visibility);
 527
 528         let num_rcvr_type_params = rcvr_generics.ty_params.len();
 529         let m_ty_generics =
 530             ty_generics_for_fn_or_method(ccx, &m.generics, num_rcvr_type_params);
 531         ty::Method::new(
 532             m.ident,
 533             m_ty_generics,
 534             fty,
 535             m.explicit_self.node,
 536             method_vis,
 537             local_def(m.id),
 538             container,
 539             None
 540         )
 541     }
 542 }
 543
 544 pub fn ensure_no_ty_param_bounds(ccx: &CrateCtxt,
 545                                  span: Span,
 546                                  generics: &ast::Generics,
 547                                  thing: &'static str) {
 548     for ty_param in generics.ty_params.iter() {
 549         if ty_param.bounds.len() > 0 {
 550             ccx.tcx.sess.span_err(
 551                 span,
 552                 format!("trait bounds are not allowed in {} definitions",
 553                      thing));
 554         }
 555     }
 556 }
 557
 558 fn ensure_generics_abi(ccx: &CrateCtxt,
 559                        span: Span,
 560                        abis: AbiSet,
 561                        generics: &ast::Generics) {
 562     if generics.ty_params.len() > 0 &&
 563        !(abis.is_rust() || abis.is_intrinsic()) {
 564         ccx.tcx.sess.span_err(span,
 565                               "foreign functions may not use type parameters");
 566     }
 567 }
 568
 569 pub fn convert(ccx: &CrateCtxt, it: &ast::Item) {
 570     let tcx = ccx.tcx;
 571     debug!("convert: item {} with id {}", token::get_ident(it.ident), it.id);
 572     match it.node {
 573         // These don't define types.
 574         ast::ItemForeignMod(_) | ast::ItemMod(_) | ast::ItemMac(_) => {}
 575         ast::ItemEnum(ref enum_definition, ref generics) => {
 576             ensure_no_ty_param_bounds(ccx, it.span, generics, "enumeration");
 577             let tpt = ty_of_item(ccx, it);
 578             write_ty_to_tcx(tcx, it.id, tpt.ty);
 579             get_enum_variant_types(ccx,
 580                                    tpt.ty,
 581                                    enum_definition.variants.as_slice(),
 582                                    generics);
 583         },
 584         ast::ItemImpl(ref generics, ref opt_trait_ref, selfty, ref ms) => {
 585             let ty_generics = ty_generics_for_type(ccx, generics);
 586             let selfty = ccx.to_ty(&ExplicitRscope, selfty);
 587             write_ty_to_tcx(tcx, it.id, selfty);
 588
 589             tcx.tcache.borrow_mut().insert(local_def(it.id),
 590                                 ty_param_bounds_and_ty {
 591                                     generics: ty_generics.clone(),
 592                                     ty: selfty});
 593
 594             // If there is a trait reference, treat the methods as always public.
 595             // This is to work around some incorrect behavior in privacy checking:
 596             // when the method belongs to a trait, it should acquire the privacy
 597             // from the trait, not the impl. Forcing the visibility to be public
 598             // makes things sorta work.
 599             let parent_visibility = if opt_trait_ref.is_some() {
 600                 ast::Public
 601             } else {
 602                 it.vis
 603             };
 604
 605             convert_methods(ccx,
 606                             ImplContainer(local_def(it.id)),
 607                             ms.as_slice(),
 608                             selfty,
 609                             &ty_generics,
 610                             generics,
 611                             parent_visibility);
 612
 613             for trait_ref in opt_trait_ref.iter() {
 614                 let trait_ref = instantiate_trait_ref(ccx, trait_ref, selfty);
 615
 616                 // Prevent the builtin kind traits from being manually implemented.
 617                 if tcx.lang_items.to_builtin_kind(trait_ref.def_id).is_some() {
 618                     tcx.sess.span_err(it.span,
 619                         "cannot provide an explicit implementation \
 620                          for a builtin kind");
 621                 }
 622             }
 623         },
 624         ast::ItemTrait(ref generics, _, ref trait_methods) => {
 625             let trait_def = trait_def_of_item(ccx, it);
 626
 627             // Run convert_methods on the provided methods.
 628             let (_, provided_methods) =
 629                 split_trait_methods(trait_methods.as_slice());
 630             let untransformed_rcvr_ty = ty::mk_self(tcx, local_def(it.id));
 631             convert_methods(ccx,
 632                             TraitContainer(local_def(it.id)),
 633                             provided_methods.as_slice(),
 634                             untransformed_rcvr_ty,
 635                             &trait_def.generics,
 636                             generics,
 637                             it.vis);
 638
 639             // We need to do this *after* converting methods, since
 640             // convert_methods produces a tcache entry that is wrong for
 641             // static trait methods. This is somewhat unfortunate.
 642             ensure_trait_methods(ccx, it.id);
 643         },
 644         ast::ItemStruct(struct_def, ref generics) => {
 645             ensure_no_ty_param_bounds(ccx, it.span, generics, "structure");
 646
 647             // Write the class type
 648             let tpt = ty_of_item(ccx, it);
 649             write_ty_to_tcx(tcx, it.id, tpt.ty);
 650
 651             tcx.tcache.borrow_mut().insert(local_def(it.id), tpt.clone());
 652
 653             convert_struct(ccx, struct_def, tpt, it.id);
 654         },
 655         ast::ItemTy(_, ref generics) => {
 656             ensure_no_ty_param_bounds(ccx, it.span, generics, "type");
 657             let tpt = ty_of_item(ccx, it);
 658             write_ty_to_tcx(tcx, it.id, tpt.ty);
 659         },
 660         ast::ItemFn(_, _, abi, ref generics, _) => {
 661             ensure_generics_abi(ccx, it.span, abi, generics);
 662             let tpt = ty_of_item(ccx, it);
 663             write_ty_to_tcx(tcx, it.id, tpt.ty);
 664         },
 665         _ => {
 666             // This call populates the type cache with the converted type
 667             // of the item in passing. All we have to do here is to write
 668             // it into the node type table.
 669             let tpt = ty_of_item(ccx, it);
 670             write_ty_to_tcx(tcx, it.id, tpt.ty);
 671         },
 672     }
 673 }
 674
 675 pub fn convert_struct(ccx: &CrateCtxt,
 676                       struct_def: &ast::StructDef,
 677                       tpt: ty::ty_param_bounds_and_ty,
 678                       id: ast::NodeId) {
 679     let tcx = ccx.tcx;
 680
 681     // Write the type of each of the members
 682     for f in struct_def.fields.iter() {
 683        convert_field(ccx, &tpt.generics, f);
 684     }
 685     let substs = mk_item_substs(ccx, &tpt.generics, None);
 686     let selfty = ty::mk_struct(tcx, local_def(id), substs);
 687
 688     // If this struct is enum-like or tuple-like, create the type of its
 689     // constructor.
 690     match struct_def.ctor_id {
 691         None => {}
 692         Some(ctor_id) => {
 693             if struct_def.fields.len() == 0 {
 694                 // Enum-like.
 695                 write_ty_to_tcx(tcx, ctor_id, selfty);
 696
 697                 tcx.tcache.borrow_mut().insert(local_def(ctor_id), tpt);
 698             } else if struct_def.fields.get(0).node.kind ==
 699                     ast::UnnamedField {
 700                 // Tuple-like.
 701                 let inputs = struct_def.fields.map(
 702                         |field| tcx.tcache.borrow().get(
 703                             &local_def(field.node.id)).ty);
 704                 let ctor_fn_ty = ty::mk_ctor_fn(tcx,
 705                                                 ctor_id,
 706                                                 inputs.as_slice(),
 707                                                 selfty);
 708                 write_ty_to_tcx(tcx, ctor_id, ctor_fn_ty);
 709                 tcx.tcache.borrow_mut().insert(local_def(ctor_id),
 710                                   ty_param_bounds_and_ty {
 711                     generics: tpt.generics,
 712                     ty: ctor_fn_ty
 713                 });
 714             }
 715         }
 716     }
 717 }
 718
 719 pub fn convert_foreign(ccx: &CrateCtxt, i: &ast::ForeignItem) {
 720     // As above, this call populates the type table with the converted
 721     // type of the foreign item. We simply write it into the node type
 722     // table.
 723
 724     // For reasons I cannot fully articulate, I do so hate the AST
 725     // map, and I regard each time that I use it as a personal and
 726     // moral failing, but at the moment it seems like the only
 727     // convenient way to extract the ABI. - ndm
 728     let abis = ccx.tcx.map.get_foreign_abis(i.id);
 729
 730     let tpt = ty_of_foreign_item(ccx, i, abis);
 731     write_ty_to_tcx(ccx.tcx, i.id, tpt.ty);
 732
 733     ccx.tcx.tcache.borrow_mut().insert(local_def(i.id), tpt);
 734 }
 735
 736 pub fn instantiate_trait_ref(ccx: &CrateCtxt,
 737                              ast_trait_ref: &ast::TraitRef,
 738                              self_ty: ty::t) -> @ty::TraitRef
 739 {
 740     /*!
 741      * Instantiates the path for the given trait reference, assuming that
 742      * it's bound to a valid trait type. Returns the def_id for the defining
 743      * trait. Fails if the type is a type other than a trait type.
 744      */
 745
 746     // FIXME(#5121) -- distinguish early vs late lifetime params
 747     let rscope = ExplicitRscope;
 748
 749     match lookup_def_tcx(ccx.tcx, ast_trait_ref.path.span, ast_trait_ref.ref_id) {
 750         ast::DefTrait(trait_did) => {
 751             let trait_ref =
 752                 astconv::ast_path_to_trait_ref(
 753                     ccx, &rscope, trait_did, Some(self_ty), &ast_trait_ref.path);
 754
 755             ccx.tcx.trait_refs.borrow_mut().insert(ast_trait_ref.ref_id,
 756                                                    trait_ref);
 757             return trait_ref;
 758         }
 759         _ => {
 760             ccx.tcx.sess.span_fatal(
 761                 ast_trait_ref.path.span,
 762                 format!("`{}` is not a trait",
 763                     path_to_str(&ast_trait_ref.path)));
 764         }
 765     }
 766 }
 767
 768 fn get_trait_def(ccx: &CrateCtxt, trait_id: ast::DefId) -> @ty::TraitDef {
 769     if trait_id.krate != ast::LOCAL_CRATE {
 770         return ty::lookup_trait_def(ccx.tcx, trait_id)
 771     }
 772
 773     match ccx.tcx.map.get(trait_id.node) {
 774         ast_map::NodeItem(item) => trait_def_of_item(ccx, item),
 775         _ => ccx.tcx.sess.bug(format!("get_trait_def({}): not an item",
 776                                    trait_id.node))
 777     }
 778 }
 779
 780 pub fn trait_def_of_item(ccx: &CrateCtxt, it: &ast::Item) -> @ty::TraitDef {
 781     let def_id = local_def(it.id);
 782     let tcx = ccx.tcx;
 783     match tcx.trait_defs.borrow().find(&def_id) {
 784         Some(&def) => return def,
 785         _ => {}
 786     }
 787
 788     match it.node {
 789         ast::ItemTrait(ref generics, ref supertraits, _) => {
 790             let self_ty = ty::mk_self(tcx, def_id);
 791             let ty_generics = ty_generics_for_type(ccx, generics);
 792             let substs = mk_item_substs(ccx, &ty_generics, Some(self_ty));
 793             let bounds = ensure_supertraits(ccx,
 794                                             it.id,
 795                                             it.span,
 796                                             supertraits.as_slice());
 797             let trait_ref = @ty::TraitRef {def_id: def_id,
 798                                            substs: substs};
 799             let trait_def = @ty::TraitDef {generics: ty_generics,
 800                                            bounds: bounds,
 801                                            trait_ref: trait_ref};
 802             tcx.trait_defs.borrow_mut().insert(def_id, trait_def);
 803             return trait_def;
 804         }
 805         ref s => {
 806             tcx.sess.span_bug(
 807                 it.span,
 808                 format!("trait_def_of_item invoked on {:?}", s));
 809         }
 810     }
 811 }
 812
 813 pub fn ty_of_item(ccx: &CrateCtxt, it: &ast::Item)
 814                   -> ty::ty_param_bounds_and_ty {
 815     let def_id = local_def(it.id);
 816     let tcx = ccx.tcx;
 817     match tcx.tcache.borrow().find(&def_id) {
 818         Some(tpt) => return tpt.clone(),
 819         _ => {}
 820     }
 821     match it.node {
 822         ast::ItemStatic(t, _, _) => {
 823             let typ = ccx.to_ty(&ExplicitRscope, t);
 824             let tpt = no_params(typ);
 825
 826             tcx.tcache.borrow_mut().insert(local_def(it.id), tpt.clone());
 827             return tpt;
 828         }
 829         ast::ItemFn(decl, purity, abi, ref generics, _) => {
 830             let ty_generics = ty_generics_for_fn_or_method(ccx, generics, 0);
 831             let tofd = astconv::ty_of_bare_fn(ccx,
 832                                               it.id,
 833                                               purity,
 834                                               abi,
 835                                               decl);
 836             let tpt = ty_param_bounds_and_ty {
 837                 generics: ty_generics,
 838                 ty: ty::mk_bare_fn(ccx.tcx, tofd)
 839             };
 840             debug!("type of {} (id {}) is {}",
 841                     token::get_ident(it.ident),
 842                     it.id,
 843                     ppaux::ty_to_str(tcx, tpt.ty));
 844
 845             ccx.tcx.tcache.borrow_mut().insert(local_def(it.id), tpt.clone());
 846             return tpt;
 847         }
 848         ast::ItemTy(t, ref generics) => {
 849             match tcx.tcache.borrow_mut().find(&local_def(it.id)) {
 850                 Some(tpt) => return tpt.clone(),
 851                 None => { }
 852             }
 853
 854             let tpt = {
 855                 let ty = ccx.to_ty(&ExplicitRscope, t);
 856                 ty_param_bounds_and_ty {
 857                     generics: ty_generics_for_type(ccx, generics),
 858                     ty: ty
 859                 }
 860             };
 861
 862             tcx.tcache.borrow_mut().insert(local_def(it.id), tpt.clone());
 863             return tpt;
 864         }
 865         ast::ItemEnum(_, ref generics) => {
 866             // Create a new generic polytype.
 867             let ty_generics = ty_generics_for_type(ccx, generics);
 868             let substs = mk_item_substs(ccx, &ty_generics, None);
 869             let t = ty::mk_enum(tcx, local_def(it.id), substs);
 870             let tpt = ty_param_bounds_and_ty {
 871                 generics: ty_generics,
 872                 ty: t
 873             };
 874
 875             tcx.tcache.borrow_mut().insert(local_def(it.id), tpt.clone());
 876             return tpt;
 877         }
 878         ast::ItemTrait(..) => {
 879             tcx.sess.span_bug(
 880                 it.span,
 881                 format!("invoked ty_of_item on trait"));
 882         }
 883         ast::ItemStruct(_, ref generics) => {
 884             let ty_generics = ty_generics_for_type(ccx, generics);
 885             let substs = mk_item_substs(ccx, &ty_generics, None);
 886             let t = ty::mk_struct(tcx, local_def(it.id), substs);
 887             let tpt = ty_param_bounds_and_ty {
 888                 generics: ty_generics,
 889                 ty: t
 890             };
 891
 892             tcx.tcache.borrow_mut().insert(local_def(it.id), tpt.clone());
 893             return tpt;
 894         }
 895         ast::ItemImpl(..) | ast::ItemMod(_) |
 896         ast::ItemForeignMod(_) | ast::ItemMac(_) => fail!(),
 897     }
 898 }
 899
 900 pub fn ty_of_foreign_item(ccx: &CrateCtxt,
 901                           it: &ast::ForeignItem,
 902                           abis: AbiSet) -> ty::ty_param_bounds_and_ty
 903 {
 904     match it.node {
 905         ast::ForeignItemFn(fn_decl, ref generics) => {
 906             ty_of_foreign_fn_decl(ccx,
 907                                   fn_decl,
 908                                   local_def(it.id),
 909                                   generics,
 910                                   abis)
 911         }
 912         ast::ForeignItemStatic(t, _) => {
 913             ty::ty_param_bounds_and_ty {
 914                 generics: ty::Generics {
 915                     type_param_defs: Rc::new(Vec::new()),
 916                     region_param_defs: Rc::new(Vec::new()),
 917                 },
 918                 ty: ast_ty_to_ty(ccx, &ExplicitRscope, t)
 919             }
 920         }
 921     }
 922 }
 923
 924 pub fn ty_generics_for_type(ccx: &CrateCtxt,
 925                             generics: &ast::Generics)
 926                             -> ty::Generics {
 927     ty_generics(ccx, &generics.lifetimes, &generics.ty_params, 0)
 928 }
 929
 930 pub fn ty_generics_for_fn_or_method(ccx: &CrateCtxt,
 931                                     generics: &ast::Generics,
 932                                     base_index: uint)
 933                                     -> ty::Generics {
 934     let early_lifetimes = resolve_lifetime::early_bound_lifetimes(generics);
 935     ty_generics(ccx, &early_lifetimes, &generics.ty_params, base_index)
 936 }
 937
 938 pub fn ty_generics(ccx: &CrateCtxt,
 939                    lifetimes: &Vec<ast::Lifetime>,
 940                    ty_params: &OwnedSlice<ast::TyParam>,
 941                    base_index: uint) -> ty::Generics {
 942     return ty::Generics {
 943         region_param_defs: Rc::new(lifetimes.iter().map(|l| {
 944                 ty::RegionParameterDef { name: l.name,
 945                                          def_id: local_def(l.id) }
 946             }).collect()),
 947         type_param_defs: Rc::new(ty_params.iter().enumerate().map(|(offset, param)| {
 948             let existing_def_opt = {
 949                 let ty_param_defs = ccx.tcx.ty_param_defs.borrow();
 950                 ty_param_defs.find(&param.id).map(|&def| def)
 951             };
 952             existing_def_opt.unwrap_or_else(|| {
 953                 let param_ty = ty::param_ty {idx: base_index + offset,
 954                                              def_id: local_def(param.id)};
 955                 let bounds = @compute_bounds(ccx, param_ty, &param.bounds);
 956                 let default = param.default.map(|x| ast_ty_to_ty(ccx, &ExplicitRscope, x));
 957                 let def = ty::TypeParameterDef {
 958                     ident: param.ident,
 959                     def_id: local_def(param.id),
 960                     bounds: bounds,
 961                     default: default
 962                 };
 963                 debug!("def for param: {}", def.repr(ccx.tcx));
 964                 ccx.tcx.ty_param_defs.borrow_mut().insert(param.id, def);
 965                 def
 966             })
 967         }).collect()),
 968     };
 969
 970     fn compute_bounds(
 971         ccx: &CrateCtxt,
 972         param_ty: ty::param_ty,
 973         ast_bounds: &OwnedSlice<ast::TyParamBound>) -> ty::ParamBounds
 974     {
 975         /*!
 976          * Translate the AST's notion of ty param bounds (which are an
 977          * enum consisting of a newtyped Ty or a region) to ty's
 978          * notion of ty param bounds, which can either be user-defined
 979          * traits, or the built-in trait (formerly known as kind): Send.
 980          */
 981
 982         let mut param_bounds = ty::ParamBounds {
 983             builtin_bounds: ty::EmptyBuiltinBounds(),
 984             trait_bounds: Vec::new()
 985         };
 986         for ast_bound in ast_bounds.iter() {
 987             match *ast_bound {
 988                 TraitTyParamBound(ref b) => {
 989                     let ty = ty::mk_param(ccx.tcx, param_ty.idx, param_ty.def_id);
 990                     let trait_ref = instantiate_trait_ref(ccx, b, ty);
 991                     if !ty::try_add_builtin_trait(
 992                         ccx.tcx, trait_ref.def_id,
 993                         &mut param_bounds.builtin_bounds)
 994                     {
 995                         // Must be a user-defined trait
 996                         param_bounds.trait_bounds.push(trait_ref);
 997                     }
 998                 }
 999
1000                 RegionTyParamBound => {
1001                     param_bounds.builtin_bounds.add(ty::BoundStatic);
1002                 }
1003             }
1004         }
1005
1006         param_bounds
1007     }
1008 }
1009
1010 pub fn ty_of_foreign_fn_decl(ccx: &CrateCtxt,
1011                              decl: &ast::FnDecl,
1012                              def_id: ast::DefId,
1013                              ast_generics: &ast::Generics,
1014                              abis: AbiSet)
1015                           -> ty::ty_param_bounds_and_ty {
1016
1017     for i in decl.inputs.iter() {
1018         match (*i).pat.node {
1019             ast::PatIdent(_, _, _) => (),
1020             ast::PatWild => (),
1021             _ => ccx.tcx.sess.span_err((*i).pat.span,
1022                     "patterns aren't allowed in foreign function declarations")
1023         }
1024     }
1025
1026     let ty_generics_for_fn_or_method =
1027         ty_generics_for_fn_or_method(ccx, ast_generics, 0);
1028     let rb = BindingRscope::new(def_id.node);
1029     let input_tys = decl.inputs
1030                         .iter()
1031                         .map(|a| ty_of_arg(ccx, &rb, a, None))
1032                         .collect();
1033
1034     let output_ty = ast_ty_to_ty(ccx, &rb, decl.output);
1035
1036     let t_fn = ty::mk_bare_fn(
1037         ccx.tcx,
1038         ty::BareFnTy {
1039             abis: abis,
1040             purity: ast::UnsafeFn,
1041             sig: ty::FnSig {binder_id: def_id.node,
1042                             inputs: input_tys,
1043                             output: output_ty,
1044                             variadic: decl.variadic}
1045         });
1046     let tpt = ty_param_bounds_and_ty {
1047         generics: ty_generics_for_fn_or_method,
1048         ty: t_fn
1049     };
1050
1051     ccx.tcx.tcache.borrow_mut().insert(def_id, tpt.clone());
1052     return tpt;
1053 }
1054
1055 pub fn mk_item_substs(ccx: &CrateCtxt,
1056                       ty_generics: &ty::Generics,
1057                       self_ty: Option<ty::t>) -> ty::substs
1058 {
1059     let params: Vec<ty::t> =
1060         ty_generics.type_param_defs().iter().enumerate().map(
1061             |(i, t)| ty::mk_param(ccx.tcx, i, t.def_id)).collect();
1062
1063     let regions: OwnedSlice<ty::Region> =
1064         ty_generics.region_param_defs().iter().enumerate().map(
1065             |(i, l)| ty::ReEarlyBound(l.def_id.node, i, l.name)).collect();
1066
1067     substs {regions: ty::NonerasedRegions(regions),
1068             self_ty: self_ty,
1069             tps: params}
1070 }