src/librustc/middle/typeck/collect.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 /*
  12
  13 # Collect phase
  14
  15 The collect phase of type check has the job of visiting all items,
  16 determining their type, and writing that type into the `tcx.tcache`
  17 table.  Despite its name, this table does not really operate as a
  18 *cache*, at least not for the types of items defined within the
  19 current crate: we assume that after the collect phase, the types of
  20 all local items will be present in the table.
  21
  22 Unlike most of the types that are present in Rust, the types computed
  23 for each item are in fact polytypes.  In "layman's terms", this means
  24 that they are generic types that may have type parameters (more
  25 mathematically phrased, they are universally quantified over a set of
  26 type parameters).  Polytypes are represented by an instance of
  27 `ty::Polytype`.  This combines the core type along with a list of the
  28 bounds for each parameter.  Type parameters themselves are represented
  29 as `ty_param()` instances.
  30
  31 */
  32
  33
  34 use metadata::csearch;
  35 use middle::def;
  36 use middle::lang_items::SizedTraitLangItem;
  37 use middle::resolve_lifetime;
  38 use middle::subst;
  39 use middle::subst::{Substs};
  40 use middle::ty::{ImplContainer, MethodContainer, TraitContainer};
  41 use middle::ty::{Polytype};
  42 use middle::ty;
  43 use middle::typeck::astconv::{AstConv, ty_of_arg};
  44 use middle::typeck::astconv::{ast_ty_to_ty};
  45 use middle::typeck::astconv;
  46 use middle::typeck::rscope::*;
  47 use middle::typeck::{CrateCtxt, lookup_def_tcx, no_params, write_ty_to_tcx};
  48 use util::ppaux;
  49 use util::ppaux::Repr;
  50
  51 use std::collections::{HashMap, HashSet};
  52 use std::rc::Rc;
  53 use std::gc::Gc;
  54
  55 use syntax::abi;
  56 use syntax::ast::{StaticRegionTyParamBound, OtherRegionTyParamBound};
  57 use syntax::ast::{TraitTyParamBound, UnboxedFnTyParamBound};
  58 use syntax::ast;
  59 use syntax::ast_map;
  60 use syntax::ast_util::{local_def, split_trait_methods};
  61 use syntax::codemap::Span;
  62 use syntax::codemap;
  63 use syntax::owned_slice::OwnedSlice;
  64 use syntax::parse::token::special_idents;
  65 use syntax::parse::token;
  66 use syntax::print::pprust::{path_to_str};
  67 use syntax::visit;
  68
  69 struct CollectItemTypesVisitor<'a> {
  70     ccx: &'a CrateCtxt<'a>
  71 }
  72
  73 impl<'a> visit::Visitor<()> for CollectItemTypesVisitor<'a> {
  74     fn visit_item(&mut self, i: &ast::Item, _: ()) {
  75         convert(self.ccx, i);
  76         visit::walk_item(self, i, ());
  77     }
  78     fn visit_foreign_item(&mut self, i: &ast::ForeignItem, _: ()) {
  79         convert_foreign(self.ccx, i);
  80         visit::walk_foreign_item(self, i, ());
  81     }
  82 }
  83
  84 pub fn collect_item_types(ccx: &CrateCtxt, krate: &ast::Crate) {
  85     fn collect_intrinsic_type(ccx: &CrateCtxt,
  86                               lang_item: ast::DefId) {
  87         let ty::Polytype { ty: ty, .. } =
  88             ccx.get_item_ty(lang_item);
  89         ccx.tcx.intrinsic_defs.borrow_mut().insert(lang_item, ty);
  90     }
  91
  92     match ccx.tcx.lang_items.ty_desc() {
  93         Some(id) => { collect_intrinsic_type(ccx, id); } None => {}
  94     }
  95     match ccx.tcx.lang_items.opaque() {
  96         Some(id) => { collect_intrinsic_type(ccx, id); } None => {}
  97     }
  98
  99     let mut visitor = CollectItemTypesVisitor{ ccx: ccx };
 100     visit::walk_crate(&mut visitor, krate, ());
 101 }
 102
 103 pub trait ToTy {
 104     fn to_ty<RS:RegionScope>(&self, rs: &RS, ast_ty: &ast::Ty) -> ty::t;
 105 }
 106
 107 impl<'a> ToTy for CrateCtxt<'a> {
 108     fn to_ty<RS:RegionScope>(&self, rs: &RS, ast_ty: &ast::Ty) -> ty::t {
 109         ast_ty_to_ty(self, rs, ast_ty)
 110     }
 111 }
 112
 113 impl<'a> AstConv for CrateCtxt<'a> {
 114     fn tcx<'a>(&'a self) -> &'a ty::ctxt { self.tcx }
 115
 116     fn get_item_ty(&self, id: ast::DefId) -> ty::Polytype {
 117         if id.krate != ast::LOCAL_CRATE {
 118             return csearch::get_type(self.tcx, id)
 119         }
 120
 121         match self.tcx.map.find(id.node) {
 122             Some(ast_map::NodeItem(item)) => ty_of_item(self, &*item),
 123             Some(ast_map::NodeForeignItem(foreign_item)) => {
 124                 let abi = self.tcx.map.get_foreign_abi(id.node);
 125                 ty_of_foreign_item(self, &*foreign_item, abi)
 126             }
 127             x => {
 128                 self.tcx.sess.bug(format!("unexpected sort of node \
 129                                            in get_item_ty(): {:?}",
 130                                           x).as_slice());
 131             }
 132         }
 133     }
 134
 135     fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef> {
 136         get_trait_def(self, id)
 137     }
 138
 139     fn ty_infer(&self, span: Span) -> ty::t {
 140         self.tcx.sess.span_err(span, "the type placeholder `_` is not \
 141                                       allowed within types on item \
 142                                       signatures.");
 143         ty::mk_err()
 144     }
 145 }
 146
 147 pub fn get_enum_variant_types(ccx: &CrateCtxt,
 148                               enum_ty: ty::t,
 149                               variants: &[ast::P<ast::Variant>],
 150                               generics: &ast::Generics) {
 151     let tcx = ccx.tcx;
 152
 153     // Create a set of parameter types shared among all the variants.
 154     for variant in variants.iter() {
 155         // Nullary enum constructors get turned into constants; n-ary enum
 156         // constructors get turned into functions.
 157         let scope = variant.node.id;
 158         let result_ty = match variant.node.kind {
 159             ast::TupleVariantKind(ref args) if args.len() > 0 => {
 160                 let rs = ExplicitRscope;
 161                 let input_tys: Vec<_> = args.iter().map(|va| ccx.to_ty(&rs, &*va.ty)).collect();
 162                 ty::mk_ctor_fn(tcx, scope, input_tys.as_slice(), enum_ty)
 163             }
 164
 165             ast::TupleVariantKind(_) => {
 166                 enum_ty
 167             }
 168
 169             ast::StructVariantKind(struct_def) => {
 170                 let pty = Polytype {
 171                     generics: ty_generics_for_type(ccx, generics),
 172                     ty: enum_ty
 173                 };
 174
 175                 convert_struct(ccx, &*struct_def, pty, variant.node.id);
 176
 177                 let input_tys: Vec<_> = struct_def.fields.iter().map(
 178                     |f| ty::node_id_to_type(ccx.tcx, f.node.id)).collect();
 179                 ty::mk_ctor_fn(tcx, scope, input_tys.as_slice(), enum_ty)
 180             }
 181         };
 182
 183         let pty = Polytype {
 184             generics: ty_generics_for_type(ccx, generics),
 185             ty: result_ty
 186         };
 187
 188         tcx.tcache.borrow_mut().insert(local_def(variant.node.id), pty);
 189
 190         write_ty_to_tcx(tcx, variant.node.id, result_ty);
 191     }
 192 }
 193
 194 pub fn ensure_trait_methods(ccx: &CrateCtxt,
 195                             trait_id: ast::NodeId,
 196                             trait_def: &ty::TraitDef) {
 197     let tcx = ccx.tcx;
 198     match tcx.map.get(trait_id) {
 199         ast_map::NodeItem(item) => {
 200             match item.node {
 201                 ast::ItemTrait(_, _, _, ref ms) => {
 202                     // For each method, construct a suitable ty::Method and
 203                     // store it into the `tcx.methods` table:
 204                     for m in ms.iter() {
 205                         let ty_method = Rc::new(match m {
 206                             &ast::Required(ref m) => {
 207                                 ty_method_of_trait_method(
 208                                     ccx, trait_id, &trait_def.generics,
 209                                     &m.id, &m.ident, &m.explicit_self,
 210                                     &m.generics, &m.fn_style, &*m.decl)
 211                             }
 212
 213                             &ast::Provided(ref m) => {
 214                                 ty_method_of_trait_method(
 215                                     ccx, trait_id, &trait_def.generics,
 216                                     &m.id, &m.ident, &m.explicit_self,
 217                                     &m.generics, &m.fn_style, &*m.decl)
 218                             }
 219                         });
 220
 221                         if ty_method.explicit_self == ast::SelfStatic {
 222                             make_static_method_ty(ccx, &*ty_method);
 223                         }
 224
 225                         tcx.methods.borrow_mut().insert(ty_method.def_id,
 226                                                         ty_method);
 227                     }
 228
 229                     // Add an entry mapping
 230                     let method_def_ids = Rc::new(ms.iter().map(|m| {
 231                         match m {
 232                             &ast::Required(ref ty_method) => {
 233                                 local_def(ty_method.id)
 234                             }
 235                             &ast::Provided(ref method) => {
 236                                 local_def(method.id)
 237                             }
 238                         }
 239                     }).collect());
 240
 241                     let trait_def_id = local_def(trait_id);
 242                     tcx.trait_method_def_ids.borrow_mut()
 243                         .insert(trait_def_id, method_def_ids);
 244                 }
 245                 _ => {} // Ignore things that aren't traits.
 246             }
 247         }
 248         _ => { /* Ignore things that aren't traits */ }
 249     }
 250
 251     fn make_static_method_ty(ccx: &CrateCtxt, m: &ty::Method) {
 252         ccx.tcx.tcache.borrow_mut().insert(
 253             m.def_id,
 254             Polytype {
 255                 generics: m.generics.clone(),
 256                 ty: ty::mk_bare_fn(ccx.tcx, m.fty.clone()) });
 257     }
 258
 259     fn ty_method_of_trait_method(this: &CrateCtxt,
 260                                  trait_id: ast::NodeId,
 261                                  trait_generics: &ty::Generics,
 262                                  m_id: &ast::NodeId,
 263                                  m_ident: &ast::Ident,
 264                                  m_explicit_self: &ast::ExplicitSelf,
 265                                  m_generics: &ast::Generics,
 266                                  m_fn_style: &ast::FnStyle,
 267                                  m_decl: &ast::FnDecl) -> ty::Method
 268     {
 269         let trait_self_ty = ty::mk_self_type(this.tcx, local_def(trait_id));
 270         let fty = astconv::ty_of_method(this, *m_id, *m_fn_style, trait_self_ty,
 271                                         *m_explicit_self, m_decl);
 272         let ty_generics =
 273             ty_generics_for_fn_or_method(this,
 274                                          m_generics,
 275                                          (*trait_generics).clone());
 276         ty::Method::new(
 277             *m_ident,
 278             ty_generics,
 279             fty,
 280             m_explicit_self.node,
 281             // assume public, because this is only invoked on trait methods
 282             ast::Public,
 283             local_def(*m_id),
 284             TraitContainer(local_def(trait_id)),
 285             None
 286         )
 287     }
 288 }
 289
 290 pub fn convert_field(ccx: &CrateCtxt,
 291                      struct_generics: &ty::Generics,
 292                      v: &ast::StructField,
 293                      origin: ast::DefId) -> ty::field_ty {
 294     let tt = ccx.to_ty(&ExplicitRscope, &*v.node.ty);
 295     write_ty_to_tcx(ccx.tcx, v.node.id, tt);
 296     /* add the field to the tcache */
 297     ccx.tcx.tcache.borrow_mut().insert(local_def(v.node.id),
 298                                        ty::Polytype {
 299                                            generics: struct_generics.clone(),
 300                                            ty: tt
 301                                        });
 302
 303     match v.node.kind {
 304         ast::NamedField(ident, visibility) => {
 305             ty::field_ty {
 306                 name: ident.name,
 307                 id: local_def(v.node.id),
 308                 vis: visibility,
 309                 origin: origin,
 310             }
 311         }
 312         ast::UnnamedField(visibility) => {
 313             ty::field_ty {
 314                 name: special_idents::unnamed_field.name,
 315                 id: local_def(v.node.id),
 316                 vis: visibility,
 317                 origin: origin,
 318             }
 319         }
 320     }
 321 }
 322
 323 fn convert_methods(ccx: &CrateCtxt,
 324                    container: MethodContainer,
 325                    ms: &[Gc<ast::Method>],
 326                    untransformed_rcvr_ty: ty::t,
 327                    rcvr_ty_generics: &ty::Generics,
 328                    rcvr_visibility: ast::Visibility)
 329 {
 330     let tcx = ccx.tcx;
 331     let mut seen_methods = HashSet::new();
 332     for m in ms.iter() {
 333         if !seen_methods.insert(m.ident.repr(ccx.tcx)) {
 334             tcx.sess.span_err(m.span, "duplicate method in trait impl");
 335         }
 336
 337         let mty = Rc::new(ty_of_method(ccx,
 338                                        container,
 339                                        &**m,
 340                                        untransformed_rcvr_ty,
 341                                        rcvr_ty_generics,
 342                                        rcvr_visibility));
 343         let fty = ty::mk_bare_fn(tcx, mty.fty.clone());
 344         debug!("method {} (id {}) has type {}",
 345                 m.ident.repr(ccx.tcx),
 346                 m.id,
 347                 fty.repr(ccx.tcx));
 348         tcx.tcache.borrow_mut().insert(
 349             local_def(m.id),
 350             Polytype {
 351                 generics: mty.generics.clone(),
 352                 ty: fty
 353             });
 354
 355         write_ty_to_tcx(tcx, m.id, fty);
 356
 357         tcx.methods.borrow_mut().insert(mty.def_id, mty);
 358     }
 359
 360     fn ty_of_method(ccx: &CrateCtxt,
 361                     container: MethodContainer,
 362                     m: &ast::Method,
 363                     untransformed_rcvr_ty: ty::t,
 364                     rcvr_ty_generics: &ty::Generics,
 365                     rcvr_visibility: ast::Visibility)
 366                     -> ty::Method
 367     {
 368         let fty = astconv::ty_of_method(ccx, m.id, m.fn_style,
 369                                         untransformed_rcvr_ty,
 370                                         m.explicit_self, &*m.decl);
 371
 372         // if the method specifies a visibility, use that, otherwise
 373         // inherit the visibility from the impl (so `foo` in `pub impl
 374         // { fn foo(); }` is public, but private in `priv impl { fn
 375         // foo(); }`).
 376         let method_vis = m.vis.inherit_from(rcvr_visibility);
 377
 378         let m_ty_generics =
 379             ty_generics_for_fn_or_method(ccx, &m.generics,
 380                                          (*rcvr_ty_generics).clone());
 381         ty::Method::new(m.ident,
 382                         m_ty_generics,
 383                         fty,
 384                         m.explicit_self.node,
 385                         method_vis,
 386                         local_def(m.id),
 387                         container,
 388                         None)
 389     }
 390 }
 391
 392 pub fn ensure_no_ty_param_bounds(ccx: &CrateCtxt,
 393                                  span: Span,
 394                                  generics: &ast::Generics,
 395                                  thing: &'static str) {
 396     for ty_param in generics.ty_params.iter() {
 397         if ty_param.bounds.len() > 0 {
 398             ccx.tcx.sess.span_err(
 399                 span,
 400                 format!("trait bounds are not allowed in {} definitions",
 401                         thing).as_slice());
 402         }
 403     }
 404 }
 405
 406 fn ensure_generics_abi(ccx: &CrateCtxt,
 407                        span: Span,
 408                        abi: abi::Abi,
 409                        generics: &ast::Generics) {
 410     if generics.ty_params.len() > 0 &&
 411        !(abi == abi::Rust || abi == abi::RustIntrinsic) {
 412         ccx.tcx.sess.span_err(span,
 413                               "foreign functions may not use type parameters");
 414     }
 415 }
 416
 417 pub fn convert(ccx: &CrateCtxt, it: &ast::Item) {
 418     let tcx = ccx.tcx;
 419     debug!("convert: item {} with id {}", token::get_ident(it.ident), it.id);
 420     match it.node {
 421         // These don't define types.
 422         ast::ItemForeignMod(_) | ast::ItemMod(_) | ast::ItemMac(_) => {}
 423         ast::ItemEnum(ref enum_definition, ref generics) => {
 424             ensure_no_ty_param_bounds(ccx, it.span, generics, "enumeration");
 425             let pty = ty_of_item(ccx, it);
 426             write_ty_to_tcx(tcx, it.id, pty.ty);
 427             get_enum_variant_types(ccx,
 428                                    pty.ty,
 429                                    enum_definition.variants.as_slice(),
 430                                    generics);
 431         },
 432         ast::ItemImpl(ref generics, ref opt_trait_ref, selfty, ref ms) => {
 433             let ty_generics = ty_generics_for_type(ccx, generics);
 434             let selfty = ccx.to_ty(&ExplicitRscope, &*selfty);
 435             write_ty_to_tcx(tcx, it.id, selfty);
 436
 437             tcx.tcache.borrow_mut().insert(local_def(it.id),
 438                                 Polytype {
 439                                     generics: ty_generics.clone(),
 440                                     ty: selfty});
 441
 442             // If there is a trait reference, treat the methods as always public.
 443             // This is to work around some incorrect behavior in privacy checking:
 444             // when the method belongs to a trait, it should acquire the privacy
 445             // from the trait, not the impl. Forcing the visibility to be public
 446             // makes things sorta work.
 447             let parent_visibility = if opt_trait_ref.is_some() {
 448                 ast::Public
 449             } else {
 450                 it.vis
 451             };
 452
 453             convert_methods(ccx,
 454                             ImplContainer(local_def(it.id)),
 455                             ms.as_slice(),
 456                             selfty,
 457                             &ty_generics,
 458                             parent_visibility);
 459
 460             for trait_ref in opt_trait_ref.iter() {
 461                 instantiate_trait_ref(ccx, trait_ref, selfty);
 462             }
 463         },
 464         ast::ItemTrait(_, _, _, ref trait_methods) => {
 465             let trait_def = trait_def_of_item(ccx, it);
 466
 467             // Run convert_methods on the provided methods.
 468             let (_, provided_methods) =
 469                 split_trait_methods(trait_methods.as_slice());
 470             let untransformed_rcvr_ty = ty::mk_self_type(tcx, local_def(it.id));
 471             convert_methods(ccx,
 472                             TraitContainer(local_def(it.id)),
 473                             provided_methods.as_slice(),
 474                             untransformed_rcvr_ty,
 475                             &trait_def.generics,
 476                             it.vis);
 477
 478             // We need to do this *after* converting methods, since
 479             // convert_methods produces a tcache entry that is wrong for
 480             // static trait methods. This is somewhat unfortunate.
 481             ensure_trait_methods(ccx, it.id, &*trait_def);
 482         },
 483         ast::ItemStruct(struct_def, ref generics) => {
 484             ensure_no_ty_param_bounds(ccx, it.span, generics, "structure");
 485
 486             // Write the class type.
 487             let pty = ty_of_item(ccx, it);
 488             write_ty_to_tcx(tcx, it.id, pty.ty);
 489
 490             tcx.tcache.borrow_mut().insert(local_def(it.id), pty.clone());
 491
 492             // Write the super-struct type, if it exists.
 493             match struct_def.super_struct {
 494                 Some(ty) => {
 495                     let supserty = ccx.to_ty(&ExplicitRscope, &*ty);
 496                     write_ty_to_tcx(tcx, it.id, supserty);
 497                 },
 498                 _ => {},
 499             }
 500
 501             convert_struct(ccx, &*struct_def, pty, it.id);
 502         },
 503         ast::ItemTy(_, ref generics) => {
 504             ensure_no_ty_param_bounds(ccx, it.span, generics, "type");
 505             let pty = ty_of_item(ccx, it);
 506             write_ty_to_tcx(tcx, it.id, pty.ty);
 507         },
 508         ast::ItemFn(_, _, abi, ref generics, _) => {
 509             ensure_generics_abi(ccx, it.span, abi, generics);
 510             let pty = ty_of_item(ccx, it);
 511             write_ty_to_tcx(tcx, it.id, pty.ty);
 512         },
 513         _ => {
 514             // This call populates the type cache with the converted type
 515             // of the item in passing. All we have to do here is to write
 516             // it into the node type table.
 517             let pty = ty_of_item(ccx, it);
 518             write_ty_to_tcx(tcx, it.id, pty.ty);
 519         },
 520     }
 521 }
 522
 523 pub fn convert_struct(ccx: &CrateCtxt,
 524                       struct_def: &ast::StructDef,
 525                       pty: ty::Polytype,
 526                       id: ast::NodeId) {
 527     let tcx = ccx.tcx;
 528
 529     // Write the type of each of the members and check for duplicate fields.
 530     let mut seen_fields: HashMap<ast::Name, Span> = HashMap::new();
 531     let field_tys = struct_def.fields.iter().map(|f| {
 532         let result = convert_field(ccx, &pty.generics, f, local_def(id));
 533
 534         if result.name != special_idents::unnamed_field.name {
 535             let dup = match seen_fields.find(&result.name) {
 536                 Some(prev_span) => {
 537                     tcx.sess.span_err(
 538                         f.span,
 539                         format!("field `{}` is already declared",
 540                                 token::get_name(result.name)).as_slice());
 541                     tcx.sess.span_note(*prev_span,
 542                                        "previously declared here");
 543                     true
 544                 },
 545                 None => false,
 546             };
 547             // FIXME(#6393) this whole dup thing is just to satisfy
 548             // the borrow checker :-(
 549             if !dup {
 550                 seen_fields.insert(result.name, f.span);
 551             }
 552         }
 553
 554         result
 555     }).collect();
 556
 557     tcx.struct_fields.borrow_mut().insert(local_def(id), Rc::new(field_tys));
 558
 559     let super_struct = match struct_def.super_struct {
 560         Some(t) => match t.node {
 561             ast::TyPath(_, _, path_id) => {
 562                 let def_map = tcx.def_map.borrow();
 563                 match def_map.find(&path_id) {
 564                     Some(&def::DefStruct(def_id)) => {
 565                         // FIXME(#12511) Check for cycles in the inheritance hierarchy.
 566                         // Check super-struct is virtual.
 567                         match tcx.map.find(def_id.node) {
 568                             Some(ast_map::NodeItem(i)) => match i.node {
 569                                 ast::ItemStruct(struct_def, _) => {
 570                                     if !struct_def.is_virtual {
 571                                         tcx.sess.span_err(t.span,
 572                                             "struct inheritance is only \
 573                                              allowed from virtual structs");
 574                                     }
 575                                 },
 576                                 _ => {},
 577                             },
 578                             _ => {},
 579                         }
 580
 581                         Some(def_id)
 582                     },
 583                     _ => None,
 584                 }
 585             }
 586             _ => None,
 587         },
 588         None => None,
 589     };
 590     tcx.superstructs.borrow_mut().insert(local_def(id), super_struct);
 591
 592     let substs = mk_item_substs(ccx, &pty.generics);
 593     let selfty = ty::mk_struct(tcx, local_def(id), substs);
 594
 595     // If this struct is enum-like or tuple-like, create the type of its
 596     // constructor.
 597     match struct_def.ctor_id {
 598         None => {}
 599         Some(ctor_id) => {
 600             if struct_def.fields.len() == 0 {
 601                 // Enum-like.
 602                 write_ty_to_tcx(tcx, ctor_id, selfty);
 603
 604                 tcx.tcache.borrow_mut().insert(local_def(ctor_id), pty);
 605             } else if struct_def.fields.get(0).node.kind.is_unnamed() {
 606                 // Tuple-like.
 607                 let inputs: Vec<_> = struct_def.fields.iter().map(
 608                         |field| tcx.tcache.borrow().get(
 609                             &local_def(field.node.id)).ty).collect();
 610                 let ctor_fn_ty = ty::mk_ctor_fn(tcx,
 611                                                 ctor_id,
 612                                                 inputs.as_slice(),
 613                                                 selfty);
 614                 write_ty_to_tcx(tcx, ctor_id, ctor_fn_ty);
 615                 tcx.tcache.borrow_mut().insert(local_def(ctor_id),
 616                                   Polytype {
 617                     generics: pty.generics,
 618                     ty: ctor_fn_ty
 619                 });
 620             }
 621         }
 622     }
 623 }
 624
 625 pub fn convert_foreign(ccx: &CrateCtxt, i: &ast::ForeignItem) {
 626     // As above, this call populates the type table with the converted
 627     // type of the foreign item. We simply write it into the node type
 628     // table.
 629
 630     // For reasons I cannot fully articulate, I do so hate the AST
 631     // map, and I regard each time that I use it as a personal and
 632     // moral failing, but at the moment it seems like the only
 633     // convenient way to extract the ABI. - ndm
 634     let abi = ccx.tcx.map.get_foreign_abi(i.id);
 635
 636     let pty = ty_of_foreign_item(ccx, i, abi);
 637     write_ty_to_tcx(ccx.tcx, i.id, pty.ty);
 638
 639     ccx.tcx.tcache.borrow_mut().insert(local_def(i.id), pty);
 640 }
 641
 642 pub fn instantiate_trait_ref(ccx: &CrateCtxt,
 643                              ast_trait_ref: &ast::TraitRef,
 644                              self_ty: ty::t) -> Rc<ty::TraitRef> {
 645     /*!
 646      * Instantiates the path for the given trait reference, assuming that
 647      * it's bound to a valid trait type. Returns the def_id for the defining
 648      * trait. Fails if the type is a type other than a trait type.
 649      */
 650
 651     // FIXME(#5121) -- distinguish early vs late lifetime params
 652     let rscope = ExplicitRscope;
 653
 654     match lookup_def_tcx(ccx.tcx, ast_trait_ref.path.span, ast_trait_ref.ref_id) {
 655         def::DefTrait(trait_did) => {
 656             let trait_ref =
 657                 astconv::ast_path_to_trait_ref(
 658                     ccx, &rscope, trait_did, Some(self_ty), &ast_trait_ref.path);
 659
 660             ccx.tcx.trait_refs.borrow_mut().insert(ast_trait_ref.ref_id,
 661                                                    trait_ref.clone());
 662             trait_ref
 663         }
 664         _ => {
 665             ccx.tcx.sess.span_fatal(
 666                 ast_trait_ref.path.span,
 667                 format!("`{}` is not a trait",
 668                         path_to_str(&ast_trait_ref.path)).as_slice());
 669         }
 670     }
 671 }
 672
 673 fn get_trait_def(ccx: &CrateCtxt, trait_id: ast::DefId) -> Rc<ty::TraitDef> {
 674     if trait_id.krate != ast::LOCAL_CRATE {
 675         return ty::lookup_trait_def(ccx.tcx, trait_id)
 676     }
 677
 678     match ccx.tcx.map.get(trait_id.node) {
 679         ast_map::NodeItem(item) => trait_def_of_item(ccx, &*item),
 680         _ => {
 681             ccx.tcx.sess.bug(format!("get_trait_def({}): not an item",
 682                                      trait_id.node).as_slice())
 683         }
 684     }
 685 }
 686
 687 pub fn trait_def_of_item(ccx: &CrateCtxt, it: &ast::Item) -> Rc<ty::TraitDef> {
 688     let def_id = local_def(it.id);
 689     let tcx = ccx.tcx;
 690     match tcx.trait_defs.borrow().find(&def_id) {
 691         Some(def) => return def.clone(),
 692         _ => {}
 693     }
 694
 695     let (generics, sized, supertraits) = match it.node {
 696         ast::ItemTrait(ref generics, sized, ref supertraits, _) => {
 697             (generics, sized, supertraits)
 698         }
 699         ref s => {
 700             tcx.sess.span_bug(
 701                 it.span,
 702                 format!("trait_def_of_item invoked on {:?}", s).as_slice());
 703         }
 704     };
 705
 706     let substs = mk_trait_substs(ccx, it.id, generics);
 707
 708     let ty_generics = ty_generics_for_trait(ccx,
 709                                             it.id,
 710                                             &substs,
 711                                             generics);
 712
 713     let builtin_bounds =
 714         ensure_supertraits(ccx, it.id, it.span, supertraits, sized);
 715
 716     let substs = mk_item_substs(ccx, &ty_generics);
 717     let trait_def = Rc::new(ty::TraitDef {
 718         generics: ty_generics,
 719         bounds: builtin_bounds,
 720         trait_ref: Rc::new(ty::TraitRef {
 721             def_id: def_id,
 722             substs: substs
 723         })
 724     });
 725     tcx.trait_defs.borrow_mut().insert(def_id, trait_def.clone());
 726
 727     return trait_def;
 728
 729     fn mk_trait_substs(ccx: &CrateCtxt,
 730                        trait_id: ast::NodeId,
 731                        generics: &ast::Generics)
 732                         -> subst::Substs
 733     {
 734         // Creates a no-op substitution for the trait's type parameters.
 735         let regions =
 736             generics.lifetimes
 737                     .iter()
 738                     .enumerate()
 739                     .map(|(i, def)| ty::ReEarlyBound(def.id,
 740                                                      subst::TypeSpace,
 741                                                      i, def.name))
 742                     .collect();
 743
 744         let types =
 745             generics.ty_params
 746                     .iter()
 747                     .enumerate()
 748                     .map(|(i, def)| ty::mk_param(ccx.tcx, subst::TypeSpace,
 749                                                  i, local_def(def.id)))
 750                     .collect();
 751
 752         let self_ty =
 753             ty::mk_param(ccx.tcx, subst::SelfSpace, 0, local_def(trait_id));
 754
 755         subst::Substs::new_trait(types, regions, self_ty)
 756     }
 757
 758     fn ensure_supertraits(ccx: &CrateCtxt,
 759                           id: ast::NodeId,
 760                           sp: codemap::Span,
 761                           ast_trait_refs: &Vec<ast::TraitRef>,
 762                           sized: ast::Sized)
 763                           -> ty::BuiltinBounds
 764     {
 765         let tcx = ccx.tcx;
 766
 767         // Called only the first time trait_def_of_item is called.
 768         // Supertraits are ensured at the same time.
 769         assert!(!tcx.supertraits.borrow().contains_key(&local_def(id)));
 770
 771         let self_ty = ty::mk_self_type(ccx.tcx, local_def(id));
 772         let mut ty_trait_refs: Vec<Rc<ty::TraitRef>> = Vec::new();
 773         let mut bounds = ty::empty_builtin_bounds();
 774         for ast_trait_ref in ast_trait_refs.iter() {
 775             let trait_def_id = ty::trait_ref_to_def_id(ccx.tcx, ast_trait_ref);
 776
 777             // FIXME(#8559): Need to instantiate the trait_ref whether
 778             // or not it's a builtin trait, so that the trait's node
 779             // id appears in the tcx trait_ref map. This is only
 780             // needed for metadata; see the similar fixme in
 781             // encoder.rs.
 782
 783             let trait_ref = instantiate_trait_ref(ccx, ast_trait_ref, self_ty);
 784             if !ty::try_add_builtin_trait(ccx.tcx, trait_def_id, &mut bounds) {
 785
 786                 // FIXME(#5527) Could have same trait multiple times
 787                 if ty_trait_refs.iter().any(
 788                     |other_trait| other_trait.def_id == trait_ref.def_id)
 789                 {
 790                     // This means a trait inherited from the same
 791                     // supertrait more than once.
 792                     tcx.sess.span_err(sp, "duplicate supertrait in \
 793                                            trait declaration");
 794                     break;
 795                 } else {
 796                     ty_trait_refs.push(trait_ref);
 797                 }
 798             }
 799         }
 800
 801         if sized == ast::StaticSize {
 802             match tcx.lang_items.require(SizedTraitLangItem) {
 803                 Ok(def_id) => {
 804                     ty::try_add_builtin_trait(tcx, def_id, &mut bounds);
 805                 }
 806                 Err(s) => tcx.sess.err(s.as_slice()),
 807             };
 808         }
 809
 810         tcx.supertraits.borrow_mut().insert(local_def(id),
 811                                             Rc::new(ty_trait_refs));
 812         bounds
 813     }
 814 }
 815
 816 pub fn ty_of_item(ccx: &CrateCtxt, it: &ast::Item)
 817                   -> ty::Polytype {
 818     let def_id = local_def(it.id);
 819     let tcx = ccx.tcx;
 820     match tcx.tcache.borrow().find(&def_id) {
 821         Some(pty) => return pty.clone(),
 822         _ => {}
 823     }
 824     match it.node {
 825         ast::ItemStatic(t, _, _) => {
 826             let typ = ccx.to_ty(&ExplicitRscope, &*t);
 827             let pty = no_params(typ);
 828
 829             tcx.tcache.borrow_mut().insert(local_def(it.id), pty.clone());
 830             return pty;
 831         }
 832         ast::ItemFn(decl, fn_style, abi, ref generics, _) => {
 833             let ty_generics = ty_generics_for_fn_or_method(ccx, generics,
 834                                                            ty::Generics::empty());
 835             let tofd = astconv::ty_of_bare_fn(ccx,
 836                                               it.id,
 837                                               fn_style,
 838                                               abi,
 839                                               &*decl);
 840             let pty = Polytype {
 841                 generics: ty_generics,
 842                 ty: ty::mk_bare_fn(ccx.tcx, tofd)
 843             };
 844             debug!("type of {} (id {}) is {}",
 845                     token::get_ident(it.ident),
 846                     it.id,
 847                     ppaux::ty_to_str(tcx, pty.ty));
 848
 849             ccx.tcx.tcache.borrow_mut().insert(local_def(it.id), pty.clone());
 850             return pty;
 851         }
 852         ast::ItemTy(t, ref generics) => {
 853             match tcx.tcache.borrow_mut().find(&local_def(it.id)) {
 854                 Some(pty) => return pty.clone(),
 855                 None => { }
 856             }
 857
 858             let pty = {
 859                 let ty = ccx.to_ty(&ExplicitRscope, &*t);
 860                 Polytype {
 861                     generics: ty_generics_for_type(ccx, generics),
 862                     ty: ty
 863                 }
 864             };
 865
 866             tcx.tcache.borrow_mut().insert(local_def(it.id), pty.clone());
 867             return pty;
 868         }
 869         ast::ItemEnum(_, ref generics) => {
 870             // Create a new generic polytype.
 871             let ty_generics = ty_generics_for_type(ccx, generics);
 872             let substs = mk_item_substs(ccx, &ty_generics);
 873             let t = ty::mk_enum(tcx, local_def(it.id), substs);
 874             let pty = Polytype {
 875                 generics: ty_generics,
 876                 ty: t
 877             };
 878
 879             tcx.tcache.borrow_mut().insert(local_def(it.id), pty.clone());
 880             return pty;
 881         }
 882         ast::ItemTrait(..) => {
 883             tcx.sess.span_bug(it.span, "invoked ty_of_item on trait");
 884         }
 885         ast::ItemStruct(_, ref generics) => {
 886             let ty_generics = ty_generics_for_type(ccx, generics);
 887             let substs = mk_item_substs(ccx, &ty_generics);
 888             let t = ty::mk_struct(tcx, local_def(it.id), substs);
 889             let pty = Polytype {
 890                 generics: ty_generics,
 891                 ty: t
 892             };
 893
 894             tcx.tcache.borrow_mut().insert(local_def(it.id), pty.clone());
 895             return pty;
 896         }
 897         ast::ItemImpl(..) | ast::ItemMod(_) |
 898         ast::ItemForeignMod(_) | ast::ItemMac(_) => fail!(),
 899     }
 900 }
 901
 902 pub fn ty_of_foreign_item(ccx: &CrateCtxt,
 903                           it: &ast::ForeignItem,
 904                           abi: abi::Abi) -> ty::Polytype
 905 {
 906     match it.node {
 907         ast::ForeignItemFn(fn_decl, ref generics) => {
 908             ty_of_foreign_fn_decl(ccx,
 909                                   &*fn_decl,
 910                                   local_def(it.id),
 911                                   generics,
 912                                   abi)
 913         }
 914         ast::ForeignItemStatic(t, _) => {
 915             ty::Polytype {
 916                 generics: ty::Generics::empty(),
 917                 ty: ast_ty_to_ty(ccx, &ExplicitRscope, &*t)
 918             }
 919         }
 920     }
 921 }
 922
 923 fn ty_generics_for_type(ccx: &CrateCtxt,
 924                         generics: &ast::Generics)
 925                         -> ty::Generics
 926 {
 927     ty_generics(ccx, subst::TypeSpace, &generics.lifetimes,
 928                 &generics.ty_params, ty::Generics::empty())
 929 }
 930
 931 fn ty_generics_for_trait(ccx: &CrateCtxt,
 932                          trait_id: ast::NodeId,
 933                          substs: &subst::Substs,
 934                          generics: &ast::Generics)
 935                          -> ty::Generics
 936 {
 937     let mut generics = ty_generics(ccx, subst::TypeSpace, &generics.lifetimes,
 938                                    &generics.ty_params, ty::Generics::empty());
 939
 940     // Something of a hack: use the node id for the trait, also as
 941     // the node id for the Self type parameter.
 942     let param_id = trait_id;
 943
 944     let self_trait_ref =
 945         Rc::new(ty::TraitRef { def_id: local_def(trait_id),
 946                                substs: (*substs).clone() });
 947
 948     let def = ty::TypeParameterDef {
 949         space: subst::SelfSpace,
 950         index: 0,
 951         ident: special_idents::type_self,
 952         def_id: local_def(param_id),
 953         bounds: Rc::new(ty::ParamBounds {
 954             builtin_bounds: ty::empty_builtin_bounds(),
 955             trait_bounds: vec!(self_trait_ref),
 956         }),
 957         default: None
 958     };
 959
 960     ccx.tcx.ty_param_defs.borrow_mut().insert(param_id, def.clone());
 961
 962     generics.types.push(subst::SelfSpace, def);
 963
 964     generics
 965 }
 966
 967 fn ty_generics_for_fn_or_method(ccx: &CrateCtxt,
 968                                 generics: &ast::Generics,
 969                                 base_generics: ty::Generics)
 970                                 -> ty::Generics
 971 {
 972     let early_lifetimes = resolve_lifetime::early_bound_lifetimes(generics);
 973     ty_generics(ccx, subst::FnSpace, &early_lifetimes,
 974                 &generics.ty_params, base_generics)
 975 }
 976
 977 fn ty_generics(ccx: &CrateCtxt,
 978                space: subst::ParamSpace,
 979                lifetimes: &Vec<ast::Lifetime>,
 980                types: &OwnedSlice<ast::TyParam>,
 981                base_generics: ty::Generics)
 982                -> ty::Generics
 983 {
 984     let mut result = base_generics;
 985
 986     for (i, l) in lifetimes.iter().enumerate() {
 987         result.regions.push(space,
 988                             ty::RegionParameterDef { name: l.name,
 989                                                      space: space,
 990                                                      index: i,
 991                                                      def_id: local_def(l.id) });
 992     }
 993
 994     for (i, param) in types.iter().enumerate() {
 995         let def = get_or_create_type_parameter_def(ccx, space, param, i);
 996         debug!("def for param: {}", def.repr(ccx.tcx));
 997         result.types.push(space, def);
 998     }
 999
1000     return result;
1001
1002     fn get_or_create_type_parameter_def(ccx: &CrateCtxt,
1003                                         space: subst::ParamSpace,
1004                                         param: &ast::TyParam,
1005                                         index: uint)
1006                                         -> ty::TypeParameterDef
1007     {
1008         match ccx.tcx.ty_param_defs.borrow().find(&param.id) {
1009             Some(d) => { return (*d).clone(); }
1010             None => { }
1011         }
1012
1013         let param_ty = ty::ParamTy {space: space,
1014                                     idx: index,
1015                                     def_id: local_def(param.id)};
1016         let bounds = Rc::new(compute_bounds(ccx,
1017                                             param_ty,
1018                                             &param.bounds,
1019                                             param.sized,
1020                                             param.ident,
1021                                             param.span));
1022         let default = param.default.map(|path| {
1023             let ty = ast_ty_to_ty(ccx, &ExplicitRscope, &*path);
1024             let cur_idx = param_ty.idx;
1025
1026             ty::walk_ty(ty, |t| {
1027                 match ty::get(t).sty {
1028                     ty::ty_param(p) => if p.idx > cur_idx {
1029                         ccx.tcx.sess.span_err(
1030                             path.span,
1031                             "type parameters with a default cannot use \
1032                              forward declared identifiers")
1033                     },
1034                     _ => {}
1035                 }
1036             });
1037
1038             ty
1039         });
1040
1041         let def = ty::TypeParameterDef {
1042             space: space,
1043             index: index,
1044             ident: param.ident,
1045             def_id: local_def(param.id),
1046             bounds: bounds,
1047             default: default
1048         };
1049
1050         ccx.tcx.ty_param_defs.borrow_mut().insert(param.id, def.clone());
1051
1052         def
1053     }
1054
1055     fn compute_bounds(
1056         ccx: &CrateCtxt,
1057         param_ty: ty::ParamTy,
1058         ast_bounds: &OwnedSlice<ast::TyParamBound>,
1059         sized: ast::Sized,
1060         ident: ast::Ident,
1061         span: Span) -> ty::ParamBounds
1062     {
1063         /*!
1064          * Translate the AST's notion of ty param bounds (which are an
1065          * enum consisting of a newtyped Ty or a region) to ty's
1066          * notion of ty param bounds, which can either be user-defined
1067          * traits, or the built-in trait (formerly known as kind): Send.
1068          */
1069
1070         let mut param_bounds = ty::ParamBounds {
1071             builtin_bounds: ty::empty_builtin_bounds(),
1072             trait_bounds: Vec::new()
1073         };
1074         for ast_bound in ast_bounds.iter() {
1075             match *ast_bound {
1076                 TraitTyParamBound(ref b) => {
1077                     let ty = ty::mk_param(ccx.tcx, param_ty.space,
1078                                           param_ty.idx, param_ty.def_id);
1079                     let trait_ref = instantiate_trait_ref(ccx, b, ty);
1080                     if !ty::try_add_builtin_trait(
1081                             ccx.tcx, trait_ref.def_id,
1082                             &mut param_bounds.builtin_bounds) {
1083                         // Must be a user-defined trait
1084                         param_bounds.trait_bounds.push(trait_ref);
1085                     }
1086                 }
1087
1088                 StaticRegionTyParamBound => {
1089                     param_bounds.builtin_bounds.add(ty::BoundStatic);
1090                 }
1091
1092                 UnboxedFnTyParamBound(ref unboxed_function) => {
1093                     let rscope = ExplicitRscope;
1094                     let self_ty = ty::mk_param(ccx.tcx,
1095                                                param_ty.space,
1096                                                param_ty.idx,
1097                                                param_ty.def_id);
1098                     let trait_ref =
1099                         astconv::trait_ref_for_unboxed_function(ccx,
1100                                                                 &rscope,
1101                                                                 unboxed_function,
1102                                                                 Some(self_ty));
1103                     param_bounds.trait_bounds.push(Rc::new(trait_ref));
1104                 }
1105
1106                 OtherRegionTyParamBound(span) => {
1107                     if !ccx.tcx.sess.features.issue_5723_bootstrap.get() {
1108                         ccx.tcx.sess.span_err(
1109                             span,
1110                             "only the 'static lifetime is accepted here.");
1111                     }
1112                 }
1113             }
1114         }
1115
1116         if sized == ast::StaticSize {
1117             match ccx.tcx.lang_items.require(SizedTraitLangItem) {
1118                 Ok(def_id) => { ty::try_add_builtin_trait(ccx.tcx,
1119                                                           def_id,
1120                                                           &mut param_bounds.builtin_bounds); },
1121                 // Fixme(13367) after `type` makes it into the snapshot, we can check this properly
1122                 Err(_s) => {}, //ccx.tcx.sess.err(s),
1123             }
1124         }
1125
1126         check_bounds_compatible(ccx.tcx, &param_bounds, ident, span);
1127
1128         param_bounds
1129     }
1130
1131     fn check_bounds_compatible(tcx: &ty::ctxt,
1132                                param_bounds: &ty::ParamBounds,
1133                                ident: ast::Ident,
1134                                span: Span) {
1135         // Currently the only bound which is incompatible with other bounds is
1136         // Sized/Unsized.
1137         if !param_bounds.builtin_bounds.contains_elem(ty::BoundSized) {
1138             ty::each_bound_trait_and_supertraits(tcx,
1139                                                  param_bounds.trait_bounds.as_slice(),
1140                                                  |trait_ref| {
1141                 let trait_def = ty::lookup_trait_def(tcx, trait_ref.def_id);
1142                 if trait_def.bounds.contains_elem(ty::BoundSized) {
1143                     tcx.sess.span_err(span,
1144                         format!("incompatible bounds on type parameter {}, \
1145                                  bound {} does not allow unsized type",
1146                         token::get_ident(ident),
1147                         ppaux::trait_ref_to_str(tcx,
1148                                                 &*trait_ref)).as_slice());
1149                 }
1150                 true
1151             });
1152         }
1153     }
1154 }
1155
1156 pub fn ty_of_foreign_fn_decl(ccx: &CrateCtxt,
1157                              decl: &ast::FnDecl,
1158                              def_id: ast::DefId,
1159                              ast_generics: &ast::Generics,
1160                              abi: abi::Abi)
1161                           -> ty::Polytype {
1162
1163     for i in decl.inputs.iter() {
1164         match (*i).pat.node {
1165             ast::PatIdent(_, _, _) => (),
1166             ast::PatWild => (),
1167             _ => ccx.tcx.sess.span_err((*i).pat.span,
1168                     "patterns aren't allowed in foreign function declarations")
1169         }
1170     }
1171
1172     let ty_generics_for_fn_or_method =
1173         ty_generics_for_fn_or_method(ccx, ast_generics,
1174                                      ty::Generics::empty());
1175     let rb = BindingRscope::new(def_id.node);
1176     let input_tys = decl.inputs
1177                         .iter()
1178                         .map(|a| ty_of_arg(ccx, &rb, a, None))
1179                         .collect();
1180
1181     let output_ty = ast_ty_to_ty(ccx, &rb, &*decl.output);
1182
1183     let t_fn = ty::mk_bare_fn(
1184         ccx.tcx,
1185         ty::BareFnTy {
1186             abi: abi,
1187             fn_style: ast::UnsafeFn,
1188             sig: ty::FnSig {binder_id: def_id.node,
1189                             inputs: input_tys,
1190                             output: output_ty,
1191                             variadic: decl.variadic}
1192         });
1193     let pty = Polytype {
1194         generics: ty_generics_for_fn_or_method,
1195         ty: t_fn
1196     };
1197
1198     ccx.tcx.tcache.borrow_mut().insert(def_id, pty.clone());
1199     return pty;
1200 }
1201
1202 pub fn mk_item_substs(ccx: &CrateCtxt,
1203                       ty_generics: &ty::Generics)
1204                       -> subst::Substs
1205 {
1206     let types =
1207         ty_generics.types.map(
1208             |def| ty::mk_param_from_def(ccx.tcx, def));
1209
1210     let regions =
1211         ty_generics.regions.map(
1212             |def| ty::ReEarlyBound(def.def_id.node, def.space,
1213                                    def.index, def.name));
1214
1215     subst::Substs::new(types, regions)
1216 }