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