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.as_slice(), 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.as_slice(), 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()
 239                                         .insert(trait_def_id,
 240                                                 @method_def_ids.iter()
 241                                                                .map(|x| *x)
 242                                                                .collect());
 243                 }
 244                 _ => {} // Ignore things that aren't traits.
 245             }
 246         }
 247         _ => { /* Ignore things that aren't traits */ }
 248     }
 249
 250     fn make_static_method_ty(ccx: &CrateCtxt,
 251                              trait_id: ast::NodeId,
 252                              m: &ty::Method,
 253                              trait_ty_generics: &ty::Generics) {
 254         // If declaration is
 255         //
 256         //     trait Trait<'a,'b,'c,a,b,c> {
 257         //        fn foo<'d,'e,'f,d,e,f>(...) -> Self;
 258         //     }
 259         //
 260         // and we will create a function like
 261         //
 262         //     fn foo<'a,'b,'c,   // First the lifetime params from trait
 263         //            'd,'e,'f,   // Then lifetime params from `foo()`
 264         //            a,b,c,      // Then type params from trait
 265         //            D:Trait<'a,'b,'c,a,b,c>, // Then this sucker
 266         //            E,F,G       // Then type params from `foo()`, offset by 1
 267         //           >(...) -> D' {}
 268         //
 269         // Note that `Self` is replaced with an explicit type
 270         // parameter D that is sandwiched in between the trait params
 271         // and the method params, and thus the indices of the method
 272         // type parameters are offset by 1 (that is, the method
 273         // parameters are mapped from d, e, f to E, F, and G).  The
 274         // choice of this ordering is somewhat arbitrary.
 275         //
 276         // Note also that the bound for `D` is `Trait<'a,'b,'c,a,b,c>`.
 277         // This implies that the lifetime parameters that were inherited
 278         // from the trait (i.e., `'a`, `'b`, and `'c`) all must be early
 279         // bound, since they appear in a trait bound.
 280         //
 281         // Also, this system is rather a hack that should be replaced
 282         // with a more uniform treatment of Self (which is partly
 283         // underway).
 284
 285         // build up a subst that shifts all of the parameters over
 286         // by one and substitute in a new type param for self
 287
 288         let tcx = ccx.tcx;
 289
 290         let dummy_defid = ast::DefId {krate: 0, node: 0};
 291
 292         // Represents [A',B',C']
 293         let num_trait_bounds = trait_ty_generics.type_param_defs().len();
 294         let non_shifted_trait_tps = vec::from_fn(num_trait_bounds, |i| {
 295             ty::mk_param(tcx, i, trait_ty_generics.type_param_defs()[i].def_id)
 296         });
 297
 298         // Represents [D']
 299         let self_param = ty::mk_param(tcx, num_trait_bounds,
 300                                       dummy_defid);
 301
 302         // Represents [E',F',G']
 303         let num_method_bounds = m.generics.type_param_defs().len();
 304         let shifted_method_tps = vec::from_fn(num_method_bounds, |i| {
 305             ty::mk_param(tcx, i + num_trait_bounds + 1,
 306                          m.generics.type_param_defs()[i].def_id)
 307         });
 308
 309         // Convert the regions 'a, 'b, 'c defined on the trait into
 310         // bound regions on the fn. Note that because these appear in the
 311         // bound for `Self` they must be early bound.
 312         let new_early_region_param_defs = trait_ty_generics.region_param_defs.clone();
 313         let rps_from_trait =
 314             trait_ty_generics.region_param_defs().iter().
 315             enumerate().
 316             map(|(index,d)| ty::ReEarlyBound(d.def_id.node, index, d.ident)).
 317             collect();
 318
 319         // build up the substitution from
 320         //     'a,'b,'c => 'a,'b,'c
 321         //     A,B,C => A',B',C'
 322         //     Self => D'
 323         //     D,E,F => E',F',G'
 324         let substs = substs {
 325             regions: ty::NonerasedRegions(rps_from_trait),
 326             self_ty: Some(self_param),
 327             tps: non_shifted_trait_tps + shifted_method_tps
 328         };
 329
 330         // create the type of `foo`, applying the substitution above
 331         let ty = ty::subst(tcx,
 332                            &substs,
 333                            ty::mk_bare_fn(tcx, m.fty.clone()));
 334
 335         // create the type parameter definitions for `foo`, applying
 336         // the substitution to any traits that appear in their bounds.
 337
 338         // add in the type parameters from the trait
 339         let mut new_type_param_defs = Vec::new();
 340         let substd_type_param_defs =
 341             trait_ty_generics.type_param_defs.subst(tcx, &substs);
 342         new_type_param_defs.push_all(*substd_type_param_defs.borrow());
 343
 344         // add in the "self" type parameter
 345         let self_trait_def = get_trait_def(ccx, local_def(trait_id));
 346         let self_trait_ref = self_trait_def.trait_ref.subst(tcx, &substs);
 347         new_type_param_defs.push(ty::TypeParameterDef {
 348             ident: special_idents::self_,
 349             def_id: dummy_defid,
 350             bounds: @ty::ParamBounds {
 351                 builtin_bounds: ty::EmptyBuiltinBounds(),
 352                 trait_bounds: vec!(self_trait_ref)
 353             },
 354             default: None
 355         });
 356
 357         // add in the type parameters from the method
 358         let substd_type_param_defs = m.generics.type_param_defs.subst(tcx, &substs);
 359         new_type_param_defs.push_all(*substd_type_param_defs.borrow());
 360
 361         debug!("static method {} type_param_defs={} ty={}, substs={}",
 362                m.def_id.repr(tcx),
 363                new_type_param_defs.repr(tcx),
 364                ty.repr(tcx),
 365                substs.repr(tcx));
 366
 367         let mut tcache = tcx.tcache.borrow_mut();
 368         tcache.get().insert(m.def_id,
 369                           ty_param_bounds_and_ty {
 370                               generics: ty::Generics {
 371                                   type_param_defs: Rc::new(new_type_param_defs),
 372                                   region_param_defs: new_early_region_param_defs
 373                               },
 374                               ty: ty
 375                           });
 376     }
 377
 378     fn ty_method_of_trait_method(this: &CrateCtxt,
 379                                  trait_id: ast::NodeId,
 380                                  trait_generics: &ty::Generics,
 381                                  m_id: &ast::NodeId,
 382                                  m_ident: &ast::Ident,
 383                                  m_explicit_self: &ast::ExplicitSelf,
 384                                  m_generics: &ast::Generics,
 385                                  m_purity: &ast::Purity,
 386                                  m_decl: &ast::FnDecl) -> ty::Method
 387     {
 388         let trait_self_ty = ty::mk_self(this.tcx, local_def(trait_id));
 389         let fty = astconv::ty_of_method(this, *m_id, *m_purity, trait_self_ty,
 390                                         *m_explicit_self, m_decl);
 391         let num_trait_type_params = trait_generics.type_param_defs().len();
 392         ty::Method::new(
 393             *m_ident,
 394             // FIXME(#5121) -- distinguish early vs late lifetime params
 395             ty_generics(this, m_generics, num_trait_type_params),
 396             fty,
 397             m_explicit_self.node,
 398             // assume public, because this is only invoked on trait methods
 399             ast::Public,
 400             local_def(*m_id),
 401             TraitContainer(local_def(trait_id)),
 402             None
 403         )
 404     }
 405 }
 406
 407 pub fn ensure_supertraits(ccx: &CrateCtxt,
 408                           id: ast::NodeId,
 409                           sp: codemap::Span,
 410                           ast_trait_refs: &[ast::TraitRef])
 411                           -> ty::BuiltinBounds
 412 {
 413     let tcx = ccx.tcx;
 414
 415     // Called only the first time trait_def_of_item is called.
 416     // Supertraits are ensured at the same time.
 417     {
 418         let supertraits = tcx.supertraits.borrow();
 419         assert!(!supertraits.get().contains_key(&local_def(id)));
 420     }
 421
 422     let self_ty = ty::mk_self(ccx.tcx, local_def(id));
 423     let mut ty_trait_refs: Vec<@ty::TraitRef> = Vec::new();
 424     let mut bounds = ty::EmptyBuiltinBounds();
 425     for ast_trait_ref in ast_trait_refs.iter() {
 426         let trait_def_id = ty::trait_ref_to_def_id(ccx.tcx, ast_trait_ref);
 427         // FIXME(#8559): Need to instantiate the trait_ref whether or not it's a
 428         // builtin trait, so that the trait's node id appears in the tcx trait_ref
 429         // map. This is only needed for metadata; see the similar fixme in encoder.rs.
 430         let trait_ref = instantiate_trait_ref(ccx, ast_trait_ref, self_ty);
 431         if !ty::try_add_builtin_trait(ccx.tcx, trait_def_id, &mut bounds) {
 432
 433             // FIXME(#5527) Could have same trait multiple times
 434             if ty_trait_refs.iter().any(|other_trait| other_trait.def_id == trait_ref.def_id) {
 435                 // This means a trait inherited from the same supertrait more
 436                 // than once.
 437                 tcx.sess.span_err(sp, "duplicate supertrait in trait declaration");
 438                 break;
 439             } else {
 440                 ty_trait_refs.push(trait_ref);
 441             }
 442         }
 443     }
 444
 445     let mut supertraits = tcx.supertraits.borrow_mut();
 446     supertraits.get().insert(local_def(id), @ty_trait_refs);
 447     bounds
 448 }
 449
 450 pub fn convert_field(ccx: &CrateCtxt,
 451                      struct_generics: &ty::Generics,
 452                      v: &ast::StructField) {
 453     let tt = ccx.to_ty(&ExplicitRscope, v.node.ty);
 454     write_ty_to_tcx(ccx.tcx, v.node.id, tt);
 455     /* add the field to the tcache */
 456     let mut tcache = ccx.tcx.tcache.borrow_mut();
 457     tcache.get().insert(local_def(v.node.id),
 458                           ty::ty_param_bounds_and_ty {
 459                               generics: struct_generics.clone(),
 460                               ty: tt
 461                           });
 462 }
 463
 464 fn convert_methods(ccx: &CrateCtxt,
 465                    container: MethodContainer,
 466                    ms: &[@ast::Method],
 467                    untransformed_rcvr_ty: ty::t,
 468                    rcvr_ty_generics: &ty::Generics,
 469                    rcvr_ast_generics: &ast::Generics,
 470                    rcvr_visibility: ast::Visibility)
 471 {
 472     let tcx = ccx.tcx;
 473     for m in ms.iter() {
 474         let num_rcvr_ty_params = rcvr_ty_generics.type_param_defs().len();
 475         let m_ty_generics = ty_generics(ccx, &m.generics, 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         {
 488             let mut tcache = tcx.tcache.borrow_mut();
 489             tcache.get().insert(
 490                 local_def(m.id),
 491
 492                 // n.b.: the type of a method is parameterized by both
 493                 // the parameters on the receiver and those on the method
 494                 // itself
 495                 ty_param_bounds_and_ty {
 496                     generics: ty::Generics {
 497                         type_param_defs: Rc::new(vec_ng::append(
 498                             rcvr_ty_generics.type_param_defs().to_owned(),
 499                             m_ty_generics.type_param_defs())),
 500                         region_param_defs: rcvr_ty_generics.region_param_defs.clone(),
 501                     },
 502                     ty: fty
 503                 });
 504         }
 505
 506         write_ty_to_tcx(tcx, m.id, fty);
 507
 508         let mut methods = tcx.methods.borrow_mut();
 509         methods.get().insert(mty.def_id, mty);
 510     }
 511
 512     fn ty_of_method(ccx: &CrateCtxt,
 513                     container: MethodContainer,
 514                     m: &ast::Method,
 515                     untransformed_rcvr_ty: ty::t,
 516                     rcvr_generics: &ast::Generics,
 517                     rcvr_visibility: ast::Visibility) -> ty::Method
 518     {
 519         let fty = astconv::ty_of_method(ccx, m.id, m.purity,
 520                                         untransformed_rcvr_ty,
 521                                         m.explicit_self, m.decl);
 522
 523         // if the method specifies a visibility, use that, otherwise
 524         // inherit the visibility from the impl (so `foo` in `pub impl
 525         // { fn foo(); }` is public, but private in `priv impl { fn
 526         // foo(); }`).
 527         let method_vis = m.vis.inherit_from(rcvr_visibility);
 528
 529         let num_rcvr_type_params = rcvr_generics.ty_params.len();
 530         ty::Method::new(
 531             m.ident,
 532             // FIXME(#5121) -- distinguish early vs late lifetime params
 533             ty_generics(ccx, &m.generics, num_rcvr_type_params),
 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 i_ty_generics = ty_generics(ccx, generics, 0);
 586             let selfty = ccx.to_ty(&ExplicitRscope, selfty);
 587             write_ty_to_tcx(tcx, it.id, selfty);
 588
 589             {
 590                 let mut tcache = tcx.tcache.borrow_mut();
 591                 tcache.get().insert(local_def(it.id),
 592                                     ty_param_bounds_and_ty {
 593                                         generics: i_ty_generics.clone(),
 594                                         ty: selfty});
 595             }
 596
 597             // If there is a trait reference, treat the methods as always public.
 598             // This is to work around some incorrect behavior in privacy checking:
 599             // when the method belongs to a trait, it should acquire the privacy
 600             // from the trait, not the impl. Forcing the visibility to be public
 601             // makes things sorta work.
 602             let parent_visibility = if opt_trait_ref.is_some() {
 603                 ast::Public
 604             } else {
 605                 it.vis
 606             };
 607
 608             convert_methods(ccx,
 609                             ImplContainer(local_def(it.id)),
 610                             ms.as_slice(),
 611                             selfty,
 612                             &i_ty_generics,
 613                             generics,
 614                             parent_visibility);
 615
 616             for trait_ref in opt_trait_ref.iter() {
 617                 let trait_ref = instantiate_trait_ref(ccx, trait_ref, selfty);
 618
 619                 // Prevent the builtin kind traits from being manually implemented.
 620                 if tcx.lang_items.to_builtin_kind(trait_ref.def_id).is_some() {
 621                     tcx.sess.span_err(it.span,
 622                         "cannot provide an explicit implementation \
 623                          for a builtin kind");
 624                 }
 625             }
 626         },
 627         ast::ItemTrait(ref generics, _, ref trait_methods) => {
 628             let trait_def = trait_def_of_item(ccx, it);
 629
 630             // Run convert_methods on the provided methods.
 631             let (_, provided_methods) =
 632                 split_trait_methods(trait_methods.as_slice());
 633             let untransformed_rcvr_ty = ty::mk_self(tcx, local_def(it.id));
 634             convert_methods(ccx,
 635                             TraitContainer(local_def(it.id)),
 636                             provided_methods.as_slice(),
 637                             untransformed_rcvr_ty,
 638                             &trait_def.generics,
 639                             generics,
 640                             it.vis);
 641
 642             // We need to do this *after* converting methods, since
 643             // convert_methods produces a tcache entry that is wrong for
 644             // static trait methods. This is somewhat unfortunate.
 645             ensure_trait_methods(ccx, it.id);
 646         },
 647         ast::ItemStruct(struct_def, ref generics) => {
 648             ensure_no_ty_param_bounds(ccx, it.span, generics, "structure");
 649
 650             // Write the class type
 651             let tpt = ty_of_item(ccx, it);
 652             write_ty_to_tcx(tcx, it.id, tpt.ty);
 653
 654             {
 655                 let mut tcache = tcx.tcache.borrow_mut();
 656                 tcache.get().insert(local_def(it.id), tpt.clone());
 657             }
 658
 659             convert_struct(ccx, struct_def, tpt, it.id);
 660         },
 661         ast::ItemTy(_, ref generics) => {
 662             ensure_no_ty_param_bounds(ccx, it.span, generics, "type");
 663             let tpt = ty_of_item(ccx, it);
 664             write_ty_to_tcx(tcx, it.id, tpt.ty);
 665         },
 666         ast::ItemFn(_, _, abi, ref generics, _) => {
 667             ensure_generics_abi(ccx, it.span, abi, generics);
 668             let tpt = ty_of_item(ccx, it);
 669             write_ty_to_tcx(tcx, it.id, tpt.ty);
 670         },
 671         _ => {
 672             // This call populates the type cache with the converted type
 673             // of the item in passing. All we have to do here is to write
 674             // it into the node type table.
 675             let tpt = ty_of_item(ccx, it);
 676             write_ty_to_tcx(tcx, it.id, tpt.ty);
 677         },
 678     }
 679 }
 680
 681 pub fn convert_struct(ccx: &CrateCtxt,
 682                       struct_def: &ast::StructDef,
 683                       tpt: ty::ty_param_bounds_and_ty,
 684                       id: ast::NodeId) {
 685     let tcx = ccx.tcx;
 686
 687     // Write the type of each of the members
 688     for f in struct_def.fields.iter() {
 689        convert_field(ccx, &tpt.generics, f);
 690     }
 691     let substs = mk_item_substs(ccx, &tpt.generics, None);
 692     let selfty = ty::mk_struct(tcx, local_def(id), substs);
 693
 694     // If this struct is enum-like or tuple-like, create the type of its
 695     // constructor.
 696     match struct_def.ctor_id {
 697         None => {}
 698         Some(ctor_id) => {
 699             if struct_def.fields.len() == 0 {
 700                 // Enum-like.
 701                 write_ty_to_tcx(tcx, ctor_id, selfty);
 702
 703                 {
 704                     let mut tcache = tcx.tcache.borrow_mut();
 705                     tcache.get().insert(local_def(ctor_id), tpt);
 706                 }
 707             } else if struct_def.fields.get(0).node.kind ==
 708                     ast::UnnamedField {
 709                 // Tuple-like.
 710                 let inputs = {
 711                     let tcache = tcx.tcache.borrow();
 712                     struct_def.fields.map(
 713                         |field| tcache.get().get(
 714                             &local_def(field.node.id)).ty)
 715                 };
 716                 let ctor_fn_ty = ty::mk_ctor_fn(tcx,
 717                                                 ctor_id,
 718                                                 inputs.as_slice(),
 719                                                 selfty);
 720                 write_ty_to_tcx(tcx, ctor_id, ctor_fn_ty);
 721                 {
 722                     let mut tcache = tcx.tcache.borrow_mut();
 723                     tcache.get().insert(local_def(ctor_id),
 724                                       ty_param_bounds_and_ty {
 725                         generics: tpt.generics,
 726                         ty: ctor_fn_ty
 727                     });
 728                 }
 729             }
 730         }
 731     }
 732 }
 733
 734 pub fn convert_foreign(ccx: &CrateCtxt, i: &ast::ForeignItem) {
 735     // As above, this call populates the type table with the converted
 736     // type of the foreign item. We simply write it into the node type
 737     // table.
 738
 739     // For reasons I cannot fully articulate, I do so hate the AST
 740     // map, and I regard each time that I use it as a personal and
 741     // moral failing, but at the moment it seems like the only
 742     // convenient way to extract the ABI. - ndm
 743     let abis = ccx.tcx.map.get_foreign_abis(i.id);
 744
 745     let tpt = ty_of_foreign_item(ccx, i, abis);
 746     write_ty_to_tcx(ccx.tcx, i.id, tpt.ty);
 747
 748     let mut tcache = ccx.tcx.tcache.borrow_mut();
 749     tcache.get().insert(local_def(i.id), tpt);
 750 }
 751
 752 pub fn instantiate_trait_ref(ccx: &CrateCtxt,
 753                              ast_trait_ref: &ast::TraitRef,
 754                              self_ty: ty::t) -> @ty::TraitRef
 755 {
 756     /*!
 757      * Instantiates the path for the given trait reference, assuming that
 758      * it's bound to a valid trait type. Returns the def_id for the defining
 759      * trait. Fails if the type is a type other than a trait type.
 760      */
 761
 762     // FIXME(#5121) -- distinguish early vs late lifetime params
 763     let rscope = ExplicitRscope;
 764
 765     match lookup_def_tcx(ccx.tcx, ast_trait_ref.path.span, ast_trait_ref.ref_id) {
 766         ast::DefTrait(trait_did) => {
 767             let trait_ref =
 768                 astconv::ast_path_to_trait_ref(
 769                     ccx, &rscope, trait_did, Some(self_ty), &ast_trait_ref.path);
 770
 771             let mut trait_refs = ccx.tcx.trait_refs.borrow_mut();
 772             trait_refs.get().insert(ast_trait_ref.ref_id, trait_ref);
 773             return trait_ref;
 774         }
 775         _ => {
 776             ccx.tcx.sess.span_fatal(
 777                 ast_trait_ref.path.span,
 778                 format!("`{}` is not a trait",
 779                     path_to_str(&ast_trait_ref.path)));
 780         }
 781     }
 782 }
 783
 784 fn get_trait_def(ccx: &CrateCtxt, trait_id: ast::DefId) -> @ty::TraitDef {
 785     if trait_id.krate != ast::LOCAL_CRATE {
 786         return ty::lookup_trait_def(ccx.tcx, trait_id)
 787     }
 788
 789     match ccx.tcx.map.get(trait_id.node) {
 790         ast_map::NodeItem(item) => trait_def_of_item(ccx, item),
 791         _ => ccx.tcx.sess.bug(format!("get_trait_def({}): not an item",
 792                                    trait_id.node))
 793     }
 794 }
 795
 796 pub fn trait_def_of_item(ccx: &CrateCtxt, it: &ast::Item) -> @ty::TraitDef {
 797     let def_id = local_def(it.id);
 798     let tcx = ccx.tcx;
 799     {
 800         let trait_defs = tcx.trait_defs.borrow();
 801         match trait_defs.get().find(&def_id) {
 802           Some(&def) => return def,
 803           _ => {}
 804         }
 805     }
 806
 807     match it.node {
 808         ast::ItemTrait(ref generics, ref supertraits, _) => {
 809             let self_ty = ty::mk_self(tcx, def_id);
 810             let ty_generics = ty_generics(ccx, generics, 0);
 811             let substs = mk_item_substs(ccx, &ty_generics, Some(self_ty));
 812             let bounds = ensure_supertraits(ccx,
 813                                             it.id,
 814                                             it.span,
 815                                             supertraits.as_slice());
 816             let trait_ref = @ty::TraitRef {def_id: def_id,
 817                                            substs: substs};
 818             let trait_def = @ty::TraitDef {generics: ty_generics,
 819                                            bounds: bounds,
 820                                            trait_ref: trait_ref};
 821             let mut trait_defs = tcx.trait_defs.borrow_mut();
 822             trait_defs.get().insert(def_id, trait_def);
 823             return trait_def;
 824         }
 825         ref s => {
 826             tcx.sess.span_bug(
 827                 it.span,
 828                 format!("trait_def_of_item invoked on {:?}", s));
 829         }
 830     }
 831 }
 832
 833 pub fn ty_of_item(ccx: &CrateCtxt, it: &ast::Item)
 834                   -> ty::ty_param_bounds_and_ty {
 835     let def_id = local_def(it.id);
 836     let tcx = ccx.tcx;
 837     {
 838         let tcache = tcx.tcache.borrow();
 839         match tcache.get().find(&def_id) {
 840             Some(tpt) => return tpt.clone(),
 841             _ => {}
 842         }
 843     }
 844     match it.node {
 845         ast::ItemStatic(t, _, _) => {
 846             let typ = ccx.to_ty(&ExplicitRscope, t);
 847             let tpt = no_params(typ);
 848
 849             let mut tcache = tcx.tcache.borrow_mut();
 850             tcache.get().insert(local_def(it.id), tpt.clone());
 851             return tpt;
 852         }
 853         ast::ItemFn(decl, purity, abi, ref generics, _) => {
 854             let ty_generics = ty_generics(ccx, generics, 0);
 855             let tofd = astconv::ty_of_bare_fn(ccx,
 856                                               it.id,
 857                                               purity,
 858                                               abi,
 859                                               decl);
 860             let tpt = ty_param_bounds_and_ty {
 861                 generics: ty::Generics {
 862                     type_param_defs: ty_generics.type_param_defs.clone(),
 863                     region_param_defs: Rc::new(Vec::new()),
 864                 },
 865                 ty: ty::mk_bare_fn(ccx.tcx, tofd)
 866             };
 867             debug!("type of {} (id {}) is {}",
 868                     token::get_ident(it.ident),
 869                     it.id,
 870                     ppaux::ty_to_str(tcx, tpt.ty));
 871
 872             let mut tcache = ccx.tcx.tcache.borrow_mut();
 873             tcache.get().insert(local_def(it.id), tpt.clone());
 874             return tpt;
 875         }
 876         ast::ItemTy(t, ref generics) => {
 877             {
 878                 let mut tcache = tcx.tcache.borrow_mut();
 879                 match tcache.get().find(&local_def(it.id)) {
 880                     Some(tpt) => return tpt.clone(),
 881                     None => { }
 882                 }
 883             }
 884
 885             let tpt = {
 886                 let ty = ccx.to_ty(&ExplicitRscope, t);
 887                 ty_param_bounds_and_ty {
 888                     generics: ty_generics(ccx, generics, 0),
 889                     ty: ty
 890                 }
 891             };
 892
 893             let mut tcache = tcx.tcache.borrow_mut();
 894             tcache.get().insert(local_def(it.id), tpt.clone());
 895             return tpt;
 896         }
 897         ast::ItemEnum(_, ref generics) => {
 898             // Create a new generic polytype.
 899             let ty_generics = ty_generics(ccx, generics, 0);
 900             let substs = mk_item_substs(ccx, &ty_generics, None);
 901             let t = ty::mk_enum(tcx, local_def(it.id), substs);
 902             let tpt = ty_param_bounds_and_ty {
 903                 generics: ty_generics,
 904                 ty: t
 905             };
 906
 907             let mut tcache = tcx.tcache.borrow_mut();
 908             tcache.get().insert(local_def(it.id), tpt.clone());
 909             return tpt;
 910         }
 911         ast::ItemTrait(..) => {
 912             tcx.sess.span_bug(
 913                 it.span,
 914                 format!("invoked ty_of_item on trait"));
 915         }
 916         ast::ItemStruct(_, ref generics) => {
 917             let ty_generics = ty_generics(ccx, generics, 0);
 918             let substs = mk_item_substs(ccx, &ty_generics, None);
 919             let t = ty::mk_struct(tcx, local_def(it.id), substs);
 920             let tpt = ty_param_bounds_and_ty {
 921                 generics: ty_generics,
 922                 ty: t
 923             };
 924
 925             let mut tcache = tcx.tcache.borrow_mut();
 926             tcache.get().insert(local_def(it.id), tpt.clone());
 927             return tpt;
 928         }
 929         ast::ItemImpl(..) | ast::ItemMod(_) |
 930         ast::ItemForeignMod(_) | ast::ItemMac(_) => fail!(),
 931     }
 932 }
 933
 934 pub fn ty_of_foreign_item(ccx: &CrateCtxt,
 935                           it: &ast::ForeignItem,
 936                           abis: AbiSet) -> ty::ty_param_bounds_and_ty
 937 {
 938     match it.node {
 939         ast::ForeignItemFn(fn_decl, ref generics) => {
 940             ty_of_foreign_fn_decl(ccx,
 941                                   fn_decl,
 942                                   local_def(it.id),
 943                                   generics,
 944                                   abis)
 945         }
 946         ast::ForeignItemStatic(t, _) => {
 947             ty::ty_param_bounds_and_ty {
 948                 generics: ty::Generics {
 949                     type_param_defs: Rc::new(Vec::new()),
 950                     region_param_defs: Rc::new(Vec::new()),
 951                 },
 952                 ty: ast_ty_to_ty(ccx, &ExplicitRscope, t)
 953             }
 954         }
 955     }
 956 }
 957
 958 pub fn ty_generics(ccx: &CrateCtxt,
 959                    generics: &ast::Generics,
 960                    base_index: uint) -> ty::Generics {
 961     return ty::Generics {
 962         region_param_defs: Rc::new(generics.lifetimes.iter().map(|l| {
 963                 ty::RegionParameterDef { ident: l.ident,
 964                                          def_id: local_def(l.id) }
 965             }).collect()),
 966         type_param_defs: Rc::new(generics.ty_params.mapi_to_vec(|offset, param| {
 967             let existing_def_opt = {
 968                 let ty_param_defs = ccx.tcx.ty_param_defs.borrow();
 969                 ty_param_defs.get().find(&param.id).map(|def| *def)
 970             };
 971             match existing_def_opt {
 972                 Some(def) => def,
 973                 None => {
 974                     let param_ty = ty::param_ty {idx: base_index + offset,
 975                                                  def_id: local_def(param.id)};
 976                     let bounds = @compute_bounds(ccx, param_ty, &param.bounds);
 977                     let default = param.default.map(|x| ast_ty_to_ty(ccx, &ExplicitRscope, x));
 978                     let def = ty::TypeParameterDef {
 979                         ident: param.ident,
 980                         def_id: local_def(param.id),
 981                         bounds: bounds,
 982                         default: default
 983                     };
 984                     debug!("def for param: {}", def.repr(ccx.tcx));
 985
 986                     let mut ty_param_defs = ccx.tcx
 987                                                .ty_param_defs
 988                                                .borrow_mut();
 989                     ty_param_defs.get().insert(param.id, def);
 990                     def
 991                 }
 992             }
 993         }).move_iter().collect())
 994     };
 995
 996     fn compute_bounds(
 997         ccx: &CrateCtxt,
 998         param_ty: ty::param_ty,
 999         ast_bounds: &OptVec<ast::TyParamBound>) -> ty::ParamBounds
1000     {
1001         /*!
1002          * Translate the AST's notion of ty param bounds (which are an
1003          * enum consisting of a newtyped Ty or a region) to ty's
1004          * notion of ty param bounds, which can either be user-defined
1005          * traits, or one of the two built-in traits (formerly known
1006          * as kinds): Freeze and Send.
1007          */
1008
1009         let mut param_bounds = ty::ParamBounds {
1010             builtin_bounds: ty::EmptyBuiltinBounds(),
1011             trait_bounds: Vec::new()
1012         };
1013         for ast_bound in ast_bounds.iter() {
1014             match *ast_bound {
1015                 TraitTyParamBound(ref b) => {
1016                     let ty = ty::mk_param(ccx.tcx, param_ty.idx, param_ty.def_id);
1017                     let trait_ref = instantiate_trait_ref(ccx, b, ty);
1018                     if !ty::try_add_builtin_trait(
1019                         ccx.tcx, trait_ref.def_id,
1020                         &mut param_bounds.builtin_bounds)
1021                     {
1022                         // Must be a user-defined trait
1023                         param_bounds.trait_bounds.push(trait_ref);
1024                     }
1025                 }
1026
1027                 RegionTyParamBound => {
1028                     param_bounds.builtin_bounds.add(ty::BoundStatic);
1029                 }
1030             }
1031         }
1032
1033         param_bounds
1034     }
1035 }
1036
1037 pub fn ty_of_foreign_fn_decl(ccx: &CrateCtxt,
1038                              decl: &ast::FnDecl,
1039                              def_id: ast::DefId,
1040                              ast_generics: &ast::Generics,
1041                              abis: AbiSet)
1042                           -> ty::ty_param_bounds_and_ty {
1043
1044     for i in decl.inputs.iter() {
1045         match (*i).pat.node {
1046             ast::PatIdent(_, _, _) => (),
1047             ast::PatWild => (),
1048             _ => ccx.tcx.sess.span_err((*i).pat.span,
1049                     "patterns aren't allowed in foreign function declarations")
1050         }
1051     }
1052
1053     let ty_generics = ty_generics(ccx, ast_generics, 0);
1054     let rb = BindingRscope::new(def_id.node);
1055     let input_tys = decl.inputs
1056                         .iter()
1057                         .map(|a| ty_of_arg(ccx, &rb, a, None))
1058                         .collect();
1059
1060     let output_ty = ast_ty_to_ty(ccx, &rb, decl.output);
1061
1062     let t_fn = ty::mk_bare_fn(
1063         ccx.tcx,
1064         ty::BareFnTy {
1065             abis: abis,
1066             purity: ast::UnsafeFn,
1067             sig: ty::FnSig {binder_id: def_id.node,
1068                             inputs: input_tys,
1069                             output: output_ty,
1070                             variadic: decl.variadic}
1071         });
1072     let tpt = ty_param_bounds_and_ty {
1073         generics: ty_generics,
1074         ty: t_fn
1075     };
1076
1077     let mut tcache = ccx.tcx.tcache.borrow_mut();
1078     tcache.get().insert(def_id, tpt.clone());
1079     return tpt;
1080 }
1081
1082 pub fn mk_item_substs(ccx: &CrateCtxt,
1083                       ty_generics: &ty::Generics,
1084                       self_ty: Option<ty::t>) -> ty::substs
1085 {
1086     let params: Vec<ty::t> =
1087         ty_generics.type_param_defs().iter().enumerate().map(
1088             |(i, t)| ty::mk_param(ccx.tcx, i, t.def_id)).collect();
1089
1090     let regions: OptVec<ty::Region> =
1091         ty_generics.region_param_defs().iter().enumerate().map(
1092             |(i, l)| ty::ReEarlyBound(l.def_id.node, i, l.ident)).collect();
1093
1094     substs {regions: ty::NonerasedRegions(regions),
1095             self_ty: self_ty,
1096             tps: params}
1097 }