src/librustc/middle/typeck/collect.rs

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