src/librustc_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 type schemes. This means that they are
  24 generic types that may have type parameters. TypeSchemes are
  25 represented by an instance of `ty::TypeScheme`.  This combines the
  26 core type along with a list of the bounds for each parameter. Type
  27 parameters themselves are represented as `ty_param()` instances.
  28
  29 The phasing of type conversion is somewhat complicated. There are a
  30 number of possible cycles that can arise.
  31
  32 Converting types can require:
  33
  34 1. `Foo<X>` where `Foo` is a type alias, or trait requires knowing:
  35    - number of region / type parameters
  36    - for type parameters, `T:'a` annotations to control defaults for object lifetimes
  37    - defaults for type parameters (which are themselves types!)
  38 2. `Foo<X>` where `Foo` is a type alias requires knowing what `Foo` expands to
  39 3. Translating `SomeTrait` with no explicit lifetime bound requires knowing
  40    - supertraits of `SomeTrait`
  41 4. Translating `T::X` (vs `<T as Trait>::X`) requires knowing
  42    - bounds on `T`
  43    - supertraits of those bounds
  44
  45 So as you can see, in general translating types requires knowing the
  46 trait hierarchy. But this gets a bit tricky because translating the
  47 trait hierarchy requires converting the types that appear in trait
  48 references. One potential saving grace is that in general knowing the
  49 trait hierarchy is only necessary for shorthands like `T::X` or
  50 handling omitted lifetime bounds on object types. Therefore, if we are
  51 lazy about expanding out the trait hierachy, users can sever cycles if
  52 necessary. Lazy expansion is also needed for type aliases.
  53
  54 This system is not perfect yet. Currently, we "convert" types and
  55 traits in three phases (note that conversion only affects the types of
  56 items / enum variants / methods; it does not e.g. compute the types of
  57 individual expressions):
  58
  59 0. Intrinsics
  60 1. Trait definitions
  61 2. Type definitions
  62
  63 Conversion itself is done by simply walking each of the items in turn
  64 and invoking an appropriate function (e.g., `trait_def_of_item` or
  65 `convert_item`). However, it is possible that while converting an
  66 item, we may need to compute the *type scheme* or *trait definition*
  67 for other items. This is a kind of shallow conversion that is
  68 triggered on demand by calls to `AstConv::get_item_type_scheme` or
  69 `AstConv::lookup_trait_def`. It is possible for cycles to result from
  70 this (e.g., `type A = B; type B = A;`), in which case astconv
  71 (currently) reports the error.
  72
  73 There are some shortcomings in this design:
  74
  75 - Cycles through trait definitions (e.g. supertraits) are not currently
  76   detected by astconv. (#12511)
  77 - Because the type scheme includes defaults, cycles through type
  78   parameter defaults are illegal even if those defaults are never
  79   employed. This is not necessarily a bug.
  80 - The phasing of trait definitions before type definitions does not
  81   seem to be necessary, sufficient, or particularly helpful, given that
  82   processing a trait definition can trigger processing a type def and
  83   vice versa. However, if I remove it, I get ICEs, so some more work is
  84   needed in that area. -nmatsakis
  85
  86 */
  87
  88 use astconv::{self, AstConv, ty_of_arg, ast_ty_to_ty, ast_region_to_region};
  89 use middle::def;
  90 use constrained_type_params::identify_constrained_type_params;
  91 use middle::lang_items::SizedTraitLangItem;
  92 use middle::region;
  93 use middle::resolve_lifetime;
  94 use middle::subst;
  95 use middle::subst::{Substs, SelfSpace, TypeSpace, VecPerParamSpace};
  96 use middle::ty::{AsPredicate, ImplContainer, ImplOrTraitItemContainer, TraitContainer};
  97 use middle::ty::{self, RegionEscape, Ty, TypeScheme};
  98 use middle::ty_fold::{self, TypeFolder, TypeFoldable};
  99 use middle::infer;
 100 use rscope::*;
 101 use util::common::memoized;
 102 use util::nodemap::{FnvHashMap, FnvHashSet};
 103 use util::ppaux;
 104 use util::ppaux::{Repr,UserString};
 105 use write_ty_to_tcx;
 106
 107 use std::collections::HashSet;
 108 use std::rc::Rc;
 109
 110 use syntax::abi;
 111 use syntax::ast;
 112 use syntax::ast_map;
 113 use syntax::ast_util::{local_def, PostExpansionMethod};
 114 use syntax::codemap::Span;
 115 use syntax::parse::token::{special_idents};
 116 use syntax::parse::token;
 117 use syntax::ptr::P;
 118 use syntax::visit;
 119
 120 ///////////////////////////////////////////////////////////////////////////
 121 // Main entry point
 122
 123 pub fn collect_item_types(tcx: &ty::ctxt) {
 124     let ccx = &CollectCtxt { tcx: tcx };
 125
 126     match ccx.tcx.lang_items.ty_desc() {
 127         Some(id) => { collect_intrinsic_type(ccx, id); }
 128         None => {}
 129     }
 130     match ccx.tcx.lang_items.opaque() {
 131         Some(id) => { collect_intrinsic_type(ccx, id); }
 132         None => {}
 133     }
 134
 135     let mut visitor = CollectTraitDefVisitor{ ccx: ccx };
 136     visit::walk_crate(&mut visitor, ccx.tcx.map.krate());
 137
 138     let mut visitor = CollectItemTypesVisitor{ ccx: ccx };
 139     visit::walk_crate(&mut visitor, ccx.tcx.map.krate());
 140 }
 141
 142 ///////////////////////////////////////////////////////////////////////////
 143
 144 struct CollectCtxt<'a,'tcx:'a> {
 145     tcx: &'a ty::ctxt<'tcx>,
 146 }
 147
 148 ///////////////////////////////////////////////////////////////////////////
 149 // Zeroth phase: collect types of intrinsics
 150
 151 fn collect_intrinsic_type(ccx: &CollectCtxt,
 152                           lang_item: ast::DefId) {
 153     let ty::TypeScheme { ty, .. } =
 154         ccx.get_item_type_scheme(lang_item);
 155     ccx.tcx.intrinsic_defs.borrow_mut().insert(lang_item, ty);
 156 }
 157
 158 ///////////////////////////////////////////////////////////////////////////
 159 // First phase: just collect *trait definitions* -- basically, the set
 160 // of type parameters and supertraits. This is information we need to
 161 // know later when parsing field defs.
 162
 163 struct CollectTraitDefVisitor<'a, 'tcx: 'a> {
 164     ccx: &'a CollectCtxt<'a, 'tcx>
 165 }
 166
 167 impl<'a, 'tcx, 'v> visit::Visitor<'v> for CollectTraitDefVisitor<'a, 'tcx> {
 168     fn visit_item(&mut self, i: &ast::Item) {
 169         match i.node {
 170             ast::ItemTrait(..) => {
 171                 // computing the trait def also fills in the table
 172                 let _ = trait_def_of_item(self.ccx, i);
 173             }
 174             _ => { }
 175         }
 176
 177         visit::walk_item(self, i);
 178     }
 179 }
 180
 181 ///////////////////////////////////////////////////////////////////////////
 182 // Second phase: collection proper.
 183
 184 struct CollectItemTypesVisitor<'a, 'tcx: 'a> {
 185     ccx: &'a CollectCtxt<'a, 'tcx>
 186 }
 187
 188 impl<'a, 'tcx, 'v> visit::Visitor<'v> for CollectItemTypesVisitor<'a, 'tcx> {
 189     fn visit_item(&mut self, i: &ast::Item) {
 190         convert_item(self.ccx, i);
 191         visit::walk_item(self, i);
 192     }
 193     fn visit_foreign_item(&mut self, i: &ast::ForeignItem) {
 194         convert_foreign_item(self.ccx, i);
 195         visit::walk_foreign_item(self, i);
 196     }
 197 }
 198
 199 ///////////////////////////////////////////////////////////////////////////
 200 // Utility types and common code for the above passes.
 201
 202 pub trait ToTy<'tcx> {
 203     fn to_ty<RS:RegionScope>(&self, rs: &RS, ast_ty: &ast::Ty) -> Ty<'tcx>;
 204 }
 205
 206 impl<'a,'tcx> ToTy<'tcx> for CollectCtxt<'a,'tcx> {
 207     fn to_ty<RS:RegionScope>(&self, rs: &RS, ast_ty: &ast::Ty) -> Ty<'tcx> {
 208         ast_ty_to_ty(self, rs, ast_ty)
 209     }
 210 }
 211
 212 impl<'a, 'tcx> AstConv<'tcx> for CollectCtxt<'a, 'tcx> {
 213     fn tcx(&self) -> &ty::ctxt<'tcx> { self.tcx }
 214
 215     fn get_item_type_scheme(&self, id: ast::DefId) -> ty::TypeScheme<'tcx> {
 216         if id.krate != ast::LOCAL_CRATE {
 217             return ty::lookup_item_type(self.tcx, id);
 218         }
 219
 220         match self.tcx.map.find(id.node) {
 221             Some(ast_map::NodeItem(item)) => {
 222                 type_scheme_of_item(self, &*item)
 223             }
 224             Some(ast_map::NodeForeignItem(foreign_item)) => {
 225                 let abi = self.tcx.map.get_foreign_abi(id.node);
 226                 type_scheme_of_foreign_item(self, &*foreign_item, abi)
 227             }
 228             x => {
 229                 self.tcx.sess.bug(&format!("unexpected sort of node \
 230                                             in get_item_type_scheme(): {:?}",
 231                                            x));
 232             }
 233         }
 234     }
 235
 236     fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef<'tcx>> {
 237         get_trait_def(self, id)
 238     }
 239
 240     fn ty_infer(&self, span: Span) -> Ty<'tcx> {
 241         span_err!(self.tcx().sess, span, E0121,
 242                   "the type placeholder `_` is not allowed within types on item signatures");
 243         self.tcx().types.err
 244     }
 245
 246     fn projected_ty(&self,
 247                     _span: Span,
 248                     trait_ref: Rc<ty::TraitRef<'tcx>>,
 249                     item_name: ast::Name)
 250                     -> Ty<'tcx>
 251     {
 252         ty::mk_projection(self.tcx(), trait_ref, item_name)
 253     }
 254 }
 255
 256 fn get_enum_variant_types<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 257                                     enum_scheme: ty::TypeScheme<'tcx>,
 258                                     enum_predicates: ty::GenericPredicates<'tcx>,
 259                                     variants: &[P<ast::Variant>]) {
 260     let tcx = ccx.tcx;
 261
 262     // Create a set of parameter types shared among all the variants.
 263     for variant in variants {
 264         let variant_def_id = local_def(variant.node.id);
 265
 266         // Nullary enum constructors get turned into constants; n-ary enum
 267         // constructors get turned into functions.
 268         let result_ty = match variant.node.kind {
 269             ast::TupleVariantKind(ref args) if args.len() > 0 => {
 270                 let rs = ExplicitRscope;
 271                 let input_tys: Vec<_> = args.iter().map(|va| ccx.to_ty(&rs, &*va.ty)).collect();
 272                 ty::mk_ctor_fn(tcx, variant_def_id, &input_tys[..], enum_scheme.ty)
 273             }
 274
 275             ast::TupleVariantKind(_) => {
 276                 enum_scheme.ty
 277             }
 278
 279             ast::StructVariantKind(ref struct_def) => {
 280                 convert_struct(ccx, &**struct_def, enum_scheme.clone(),
 281                                enum_predicates.clone(), variant.node.id);
 282                 enum_scheme.ty
 283             }
 284         };
 285
 286         let variant_scheme = TypeScheme {
 287             generics: enum_scheme.generics.clone(),
 288             ty: result_ty
 289         };
 290
 291         tcx.tcache.borrow_mut().insert(variant_def_id, variant_scheme.clone());
 292         tcx.predicates.borrow_mut().insert(variant_def_id, enum_predicates.clone());
 293         write_ty_to_tcx(tcx, variant.node.id, result_ty);
 294     }
 295 }
 296
 297 fn collect_trait_methods<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 298                                    trait_id: ast::NodeId,
 299                                    trait_def: &ty::TraitDef<'tcx>,
 300                                    trait_predicates: &ty::GenericPredicates<'tcx>) {
 301     let tcx = ccx.tcx;
 302     if let ast_map::NodeItem(item) = tcx.map.get(trait_id) {
 303         if let ast::ItemTrait(_, _, _, ref trait_items) = item.node {
 304             // For each method, construct a suitable ty::Method and
 305             // store it into the `tcx.impl_or_trait_items` table:
 306             for trait_item in trait_items {
 307                 match *trait_item {
 308                     ast::RequiredMethod(_) |
 309                     ast::ProvidedMethod(_) => {
 310                         let ty_method = Rc::new(match *trait_item {
 311                             ast::RequiredMethod(ref m) => {
 312                                 ty_method_of_trait_method(
 313                                     ccx,
 314                                     trait_id,
 315                                     &trait_def.generics,
 316                                     &trait_predicates,
 317                                     &trait_items[..],
 318                                     &m.id,
 319                                     &m.ident.name,
 320                                     &m.explicit_self,
 321                                     m.abi,
 322                                     &m.generics,
 323                                     &m.unsafety,
 324                                     &*m.decl)
 325                             }
 326                             ast::ProvidedMethod(ref m) => {
 327                                 ty_method_of_trait_method(
 328                                     ccx,
 329                                     trait_id,
 330                                     &trait_def.generics,
 331                                     &trait_predicates,
 332                                     &trait_items[..],
 333                                     &m.id,
 334                                     &m.pe_ident().name,
 335                                     m.pe_explicit_self(),
 336                                     m.pe_abi(),
 337                                     m.pe_generics(),
 338                                     &m.pe_unsafety(),
 339                                     &*m.pe_fn_decl())
 340                             }
 341                             ast::TypeTraitItem(ref at) => {
 342                                 tcx.sess.span_bug(at.ty_param.span,
 343                                                   "there shouldn't be a type trait item here")
 344                             }
 345                         });
 346
 347                         debug!("ty_method_of_trait_method yielded {} for method {} of trait {}",
 348                                ty_method.repr(ccx.tcx),
 349                                trait_item.repr(ccx.tcx),
 350                                local_def(trait_id).repr(ccx.tcx));
 351
 352                         make_method_ty(ccx, &*ty_method);
 353
 354                         tcx.impl_or_trait_items
 355                             .borrow_mut()
 356                             .insert(ty_method.def_id, ty::MethodTraitItem(ty_method));
 357                     }
 358                     ast::TypeTraitItem(ref ast_associated_type) => {
 359                         let trait_did = local_def(trait_id);
 360                         let associated_type = ty::AssociatedType {
 361                             name: ast_associated_type.ty_param.ident.name,
 362                             vis: ast::Public,
 363                             def_id: local_def(ast_associated_type.ty_param.id),
 364                             container: TraitContainer(trait_did),
 365                         };
 366
 367                         let trait_item = ty::TypeTraitItem(Rc::new(associated_type));
 368                         tcx.impl_or_trait_items
 369                             .borrow_mut()
 370                             .insert(associated_type.def_id, trait_item);
 371                     }
 372                 }
 373             }
 374
 375             // Add an entry mapping
 376             let trait_item_def_ids =
 377                 Rc::new(trait_items.iter().map(|ti| {
 378                     match *ti {
 379                         ast::RequiredMethod(ref ty_method) => {
 380                             ty::MethodTraitItemId(local_def(ty_method.id))
 381                         }
 382                         ast::ProvidedMethod(ref method) => {
 383                             ty::MethodTraitItemId(local_def(method.id))
 384                         }
 385                         ast::TypeTraitItem(ref typedef) => {
 386                             ty::TypeTraitItemId(local_def(typedef.ty_param.id))
 387                         }
 388                     }
 389                 }).collect());
 390
 391             let trait_def_id = local_def(trait_id);
 392             tcx.trait_item_def_ids.borrow_mut().insert(trait_def_id, trait_item_def_ids);
 393         }
 394     }
 395
 396     fn make_method_ty<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>, m: &ty::Method<'tcx>) {
 397         ccx.tcx.tcache.borrow_mut().insert(
 398             m.def_id,
 399             TypeScheme {
 400                 generics: m.generics.clone(),
 401                 ty: ty::mk_bare_fn(ccx.tcx, Some(m.def_id), ccx.tcx.mk_bare_fn(m.fty.clone()))
 402             });
 403         ccx.tcx.predicates.borrow_mut().insert(
 404             m.def_id,
 405             m.predicates.clone());
 406     }
 407
 408     fn ty_method_of_trait_method<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 409                                            trait_id: ast::NodeId,
 410                                            trait_generics: &ty::Generics<'tcx>,
 411                                            trait_bounds: &ty::GenericPredicates<'tcx>,
 412                                            _trait_items: &[ast::TraitItem],
 413                                            m_id: &ast::NodeId,
 414                                            m_name: &ast::Name,
 415                                            m_explicit_self: &ast::ExplicitSelf,
 416                                            m_abi: abi::Abi,
 417                                            m_generics: &ast::Generics,
 418                                            m_unsafety: &ast::Unsafety,
 419                                            m_decl: &ast::FnDecl)
 420                                            -> ty::Method<'tcx> {
 421         let ty_generics =
 422             ty_generics_for_fn_or_method(ccx,
 423                                          m_generics,
 424                                          trait_generics.clone());
 425
 426         let ty_bounds =
 427             ty_generic_bounds_for_fn_or_method(ccx,
 428                                                m_generics,
 429                                                &ty_generics,
 430                                                trait_bounds.clone());
 431
 432         let (fty, explicit_self_category) = {
 433             let trait_self_ty = ty::mk_self_type(ccx.tcx);
 434             astconv::ty_of_method(ccx,
 435                                   *m_unsafety,
 436                                   trait_self_ty,
 437                                   m_explicit_self,
 438                                   m_decl,
 439                                   m_abi)
 440         };
 441
 442         ty::Method::new(
 443             *m_name,
 444             ty_generics,
 445             ty_bounds,
 446             fty,
 447             explicit_self_category,
 448             // assume public, because this is only invoked on trait methods
 449             ast::Public,
 450             local_def(*m_id),
 451             TraitContainer(local_def(trait_id)),
 452             None
 453         )
 454     }
 455 }
 456
 457 fn convert_field<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 458                                 struct_generics: &ty::Generics<'tcx>,
 459                                 struct_predicates: &ty::GenericPredicates<'tcx>,
 460                                 v: &ast::StructField,
 461                                 origin: ast::DefId) -> ty::field_ty {
 462     let tt = ccx.to_ty(&ExplicitRscope, &*v.node.ty);
 463     write_ty_to_tcx(ccx.tcx, v.node.id, tt);
 464
 465     /* add the field to the tcache */
 466     ccx.tcx.tcache.borrow_mut().insert(local_def(v.node.id),
 467                                        ty::TypeScheme {
 468                                            generics: struct_generics.clone(),
 469                                            ty: tt
 470                                        });
 471     ccx.tcx.predicates.borrow_mut().insert(local_def(v.node.id),
 472                                            struct_predicates.clone());
 473
 474     match v.node.kind {
 475         ast::NamedField(ident, visibility) => {
 476             ty::field_ty {
 477                 name: ident.name,
 478                 id: local_def(v.node.id),
 479                 vis: visibility,
 480                 origin: origin,
 481             }
 482         }
 483         ast::UnnamedField(visibility) => {
 484             ty::field_ty {
 485                 name: special_idents::unnamed_field.name,
 486                 id: local_def(v.node.id),
 487                 vis: visibility,
 488                 origin: origin,
 489             }
 490         }
 491     }
 492 }
 493
 494 fn convert_associated_type<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 495                                      trait_def: &ty::TraitDef<'tcx>,
 496                                      associated_type: &ast::AssociatedType)
 497 {
 498     let associated_type = Rc::new(ty::AssociatedType {
 499         name: associated_type.ty_param.ident.name,
 500         vis: ast::Public,
 501         def_id: local_def(associated_type.ty_param.id),
 502         container: TraitContainer(trait_def.trait_ref.def_id),
 503     });
 504     ccx.tcx
 505        .impl_or_trait_items
 506        .borrow_mut()
 507        .insert(associated_type.def_id,
 508                ty::TypeTraitItem(associated_type));
 509 }
 510
 511 fn convert_methods<'a,'tcx,'i,I>(ccx: &CollectCtxt<'a, 'tcx>,
 512                                  container: ImplOrTraitItemContainer,
 513                                  ms: I,
 514                                  untransformed_rcvr_ty: Ty<'tcx>,
 515                                  rcvr_ty_generics: &ty::Generics<'tcx>,
 516                                  rcvr_ty_predicates: &ty::GenericPredicates<'tcx>,
 517                                  rcvr_visibility: ast::Visibility)
 518                                  where I: Iterator<Item=&'i ast::Method> {
 519     debug!("convert_methods(untransformed_rcvr_ty={}, rcvr_ty_generics={})",
 520            untransformed_rcvr_ty.repr(ccx.tcx),
 521            rcvr_ty_generics.repr(ccx.tcx));
 522
 523     let tcx = ccx.tcx;
 524     let mut seen_methods = FnvHashSet();
 525     for m in ms {
 526         if !seen_methods.insert(m.pe_ident().repr(tcx)) {
 527             span_err!(tcx.sess, m.span, E0201, "duplicate method in trait impl");
 528         }
 529
 530         let m_def_id = local_def(m.id);
 531
 532         let mty = Rc::new(ty_of_method(ccx,
 533                                        container,
 534                                        m,
 535                                        untransformed_rcvr_ty,
 536                                        rcvr_ty_generics,
 537                                        rcvr_ty_predicates,
 538                                        rcvr_visibility));
 539         let fty = ty::mk_bare_fn(tcx, Some(m_def_id), tcx.mk_bare_fn(mty.fty.clone()));
 540         debug!("method {} (id {}) has type {}",
 541                 m.pe_ident().repr(tcx),
 542                 m.id,
 543                 fty.repr(tcx));
 544         tcx.tcache.borrow_mut().insert(
 545             m_def_id,
 546             TypeScheme {
 547                 generics: mty.generics.clone(),
 548                 ty: fty
 549             });
 550         tcx.predicates.borrow_mut().insert(m_def_id, mty.predicates.clone());
 551
 552         write_ty_to_tcx(tcx, m.id, fty);
 553
 554         debug!("writing method type: def_id={:?} mty={}",
 555                mty.def_id, mty.repr(ccx.tcx));
 556
 557         tcx.impl_or_trait_items
 558            .borrow_mut()
 559            .insert(mty.def_id, ty::MethodTraitItem(mty));
 560     }
 561
 562     fn ty_of_method<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 563                               container: ImplOrTraitItemContainer,
 564                               m: &ast::Method,
 565                               untransformed_rcvr_ty: Ty<'tcx>,
 566                               rcvr_ty_generics: &ty::Generics<'tcx>,
 567                               rcvr_ty_predicates: &ty::GenericPredicates<'tcx>,
 568                               rcvr_visibility: ast::Visibility)
 569                               -> ty::Method<'tcx> {
 570         let m_ty_generics =
 571             ty_generics_for_fn_or_method(ccx,
 572                                          m.pe_generics(),
 573                                          rcvr_ty_generics.clone());
 574
 575         let m_ty_bounds =
 576             ty_generic_bounds_for_fn_or_method(ccx,
 577                                                m.pe_generics(),
 578                                                &m_ty_generics,
 579                                                rcvr_ty_predicates.clone());
 580
 581         let (fty, explicit_self_category) = astconv::ty_of_method(ccx,
 582                                                                   m.pe_unsafety(),
 583                                                                   untransformed_rcvr_ty,
 584                                                                   m.pe_explicit_self(),
 585                                                                   &*m.pe_fn_decl(),
 586                                                                   m.pe_abi());
 587
 588         // if the method specifies a visibility, use that, otherwise
 589         // inherit the visibility from the impl (so `foo` in `pub impl
 590         // { fn foo(); }` is public, but private in `priv impl { fn
 591         // foo(); }`).
 592         let method_vis = m.pe_vis().inherit_from(rcvr_visibility);
 593
 594         ty::Method::new(m.pe_ident().name,
 595                         m_ty_generics,
 596                         m_ty_bounds,
 597                         fty,
 598                         explicit_self_category,
 599                         method_vis,
 600                         local_def(m.id),
 601                         container,
 602                         None)
 603     }
 604 }
 605
 606 fn ensure_no_ty_param_bounds(ccx: &CollectCtxt,
 607                                  span: Span,
 608                                  generics: &ast::Generics,
 609                                  thing: &'static str) {
 610     let mut warn = false;
 611
 612     for ty_param in &*generics.ty_params {
 613         for bound in &*ty_param.bounds {
 614             match *bound {
 615                 ast::TraitTyParamBound(..) => {
 616                     warn = true;
 617                 }
 618                 ast::RegionTyParamBound(..) => { }
 619             }
 620         }
 621     }
 622
 623     if warn {
 624         // According to accepted RFC #XXX, we should
 625         // eventually accept these, but it will not be
 626         // part of this PR. Still, convert to warning to
 627         // make bootstrapping easier.
 628         span_warn!(ccx.tcx.sess, span, E0122,
 629                    "trait bounds are not (yet) enforced \
 630                    in {} definitions",
 631                    thing);
 632     }
 633 }
 634
 635 fn convert_item(ccx: &CollectCtxt, it: &ast::Item) {
 636     let tcx = ccx.tcx;
 637     debug!("convert: item {} with id {}", token::get_ident(it.ident), it.id);
 638     match it.node {
 639         // These don't define types.
 640         ast::ItemExternCrate(_) | ast::ItemUse(_) |
 641         ast::ItemForeignMod(_) | ast::ItemMod(_) | ast::ItemMac(_) => {
 642         }
 643         ast::ItemEnum(ref enum_definition, _) => {
 644             let (scheme, predicates) = convert_typed_item(ccx, it);
 645             write_ty_to_tcx(tcx, it.id, scheme.ty);
 646             get_enum_variant_types(ccx,
 647                                    scheme,
 648                                    predicates,
 649                                    &enum_definition.variants);
 650         },
 651         ast::ItemImpl(_, _,
 652                       ref generics,
 653                       ref opt_trait_ref,
 654                       ref selfty,
 655                       ref impl_items) => {
 656             // Create generics from the generics specified in the impl head.
 657
 658             debug!("convert: ast_generics={:?}", generics);
 659             let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
 660             let ty_predicates = ty_generic_bounds_for_type_or_impl(ccx, &ty_generics, generics);
 661
 662             debug!("convert: impl_bounds={:?}", ty_predicates);
 663
 664             let selfty = ccx.to_ty(&ExplicitRscope, &**selfty);
 665             write_ty_to_tcx(tcx, it.id, selfty);
 666
 667             tcx.tcache.borrow_mut().insert(local_def(it.id),
 668                                            TypeScheme { generics: ty_generics.clone(),
 669                                                         ty: selfty });
 670             tcx.predicates.borrow_mut().insert(local_def(it.id),
 671                                                ty_predicates.clone());
 672
 673             // If there is a trait reference, treat the methods as always public.
 674             // This is to work around some incorrect behavior in privacy checking:
 675             // when the method belongs to a trait, it should acquire the privacy
 676             // from the trait, not the impl. Forcing the visibility to be public
 677             // makes things sorta work.
 678             let parent_visibility = if opt_trait_ref.is_some() {
 679                 ast::Public
 680             } else {
 681                 it.vis
 682             };
 683
 684             let mut methods = Vec::new();
 685             for impl_item in impl_items {
 686                 match *impl_item {
 687                     ast::MethodImplItem(ref method) => {
 688                         let body_id = method.pe_body().id;
 689                         check_method_self_type(ccx,
 690                                                &BindingRscope::new(),
 691                                                selfty,
 692                                                method.pe_explicit_self(),
 693                                                body_id);
 694                         methods.push(&**method);
 695                     }
 696                     ast::TypeImplItem(ref typedef) => {
 697                         if opt_trait_ref.is_none() {
 698                             span_err!(tcx.sess, typedef.span, E0202,
 699                                               "associated items are not allowed in inherent impls");
 700                         }
 701
 702                         let typ = ccx.to_ty(&ExplicitRscope, &*typedef.typ);
 703                         tcx.tcache.borrow_mut().insert(local_def(typedef.id),
 704                                                        TypeScheme {
 705                                                            generics: ty::Generics::empty(),
 706                                                            ty: typ,
 707                                                        });
 708                         tcx.predicates.borrow_mut().insert(local_def(typedef.id),
 709                                                            ty::GenericPredicates::empty());
 710                         write_ty_to_tcx(tcx, typedef.id, typ);
 711
 712                         let associated_type = Rc::new(ty::AssociatedType {
 713                             name: typedef.ident.name,
 714                             vis: typedef.vis,
 715                             def_id: local_def(typedef.id),
 716                             container: ty::ImplContainer(local_def(it.id)),
 717                         });
 718                         tcx.impl_or_trait_items
 719                            .borrow_mut()
 720                            .insert(local_def(typedef.id),
 721                                    ty::TypeTraitItem(associated_type));
 722                     }
 723                 }
 724             }
 725
 726             convert_methods(ccx,
 727                             ImplContainer(local_def(it.id)),
 728                             methods.into_iter(),
 729                             selfty,
 730                             &ty_generics,
 731                             &ty_predicates,
 732                             parent_visibility);
 733
 734             if let Some(ref trait_ref) = *opt_trait_ref {
 735                 astconv::instantiate_trait_ref(ccx,
 736                                                &ExplicitRscope,
 737                                                trait_ref,
 738                                                Some(selfty),
 739                                                None);
 740             }
 741
 742             enforce_impl_ty_params_are_constrained(tcx,
 743                                                    generics,
 744                                                    local_def(it.id));
 745         },
 746         ast::ItemTrait(_, _, _, ref trait_methods) => {
 747             let trait_def = trait_def_of_item(ccx, it);
 748             convert_trait_predicates(ccx, it);
 749             let trait_predicates = ty::lookup_predicates(ccx.tcx, local_def(it.id));
 750
 751             debug!("convert: trait_bounds={:?}", trait_predicates);
 752
 753             for trait_method in trait_methods {
 754                 let self_type = ty::mk_self_type(tcx);
 755                 match *trait_method {
 756                     ast::RequiredMethod(ref type_method) => {
 757                         let rscope = BindingRscope::new();
 758                         check_method_self_type(ccx,
 759                                                &rscope,
 760                                                self_type,
 761                                                &type_method.explicit_self,
 762                                                it.id)
 763                     }
 764                     ast::ProvidedMethod(ref method) => {
 765                         check_method_self_type(ccx,
 766                                                &BindingRscope::new(),
 767                                                self_type,
 768                                                method.pe_explicit_self(),
 769                                                it.id)
 770                     }
 771                     ast::TypeTraitItem(ref associated_type) => {
 772                         convert_associated_type(ccx,
 773                                                 &*trait_def,
 774                                                 &**associated_type);
 775                     }
 776                 }
 777             }
 778
 779             // Run convert_methods on the provided methods.
 780             let untransformed_rcvr_ty = ty::mk_self_type(tcx);
 781             convert_methods(ccx,
 782                             TraitContainer(local_def(it.id)),
 783                             trait_methods.iter().filter_map(|m| match *m {
 784                                 ast::RequiredMethod(_) => None,
 785                                 ast::ProvidedMethod(ref m) => Some(&**m),
 786                                 ast::TypeTraitItem(_) => None,
 787                             }),
 788                             untransformed_rcvr_ty,
 789                             &trait_def.generics,
 790                             &trait_predicates,
 791                             it.vis);
 792
 793             // We need to do this *after* converting methods, since
 794             // convert_methods produces a tcache entry that is wrong for
 795             // static trait methods. This is somewhat unfortunate.
 796             collect_trait_methods(ccx, it.id, &*trait_def, &trait_predicates);
 797         },
 798         ast::ItemStruct(ref struct_def, _) => {
 799             // Write the class type.
 800             let (scheme, predicates) = convert_typed_item(ccx, it);
 801             write_ty_to_tcx(tcx, it.id, scheme.ty);
 802             convert_struct(ccx, &**struct_def, scheme, predicates, it.id);
 803         },
 804         ast::ItemTy(_, ref generics) => {
 805             ensure_no_ty_param_bounds(ccx, it.span, generics, "type");
 806             let (scheme, _) = convert_typed_item(ccx, it);
 807             write_ty_to_tcx(tcx, it.id, scheme.ty);
 808         },
 809         _ => {
 810             // This call populates the type cache with the converted type
 811             // of the item in passing. All we have to do here is to write
 812             // it into the node type table.
 813             let (scheme, _) = convert_typed_item(ccx, it);
 814             write_ty_to_tcx(tcx, it.id, scheme.ty);
 815         },
 816     }
 817 }
 818
 819 fn convert_struct<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 820                             struct_def: &ast::StructDef,
 821                             scheme: ty::TypeScheme<'tcx>,
 822                             predicates: ty::GenericPredicates<'tcx>,
 823                             id: ast::NodeId) {
 824     let tcx = ccx.tcx;
 825
 826     // Write the type of each of the members and check for duplicate fields.
 827     let mut seen_fields: FnvHashMap<ast::Name, Span> = FnvHashMap();
 828     let field_tys = struct_def.fields.iter().map(|f| {
 829         let result = convert_field(ccx, &scheme.generics, &predicates, f, local_def(id));
 830
 831         if result.name != special_idents::unnamed_field.name {
 832             let dup = match seen_fields.get(&result.name) {
 833                 Some(prev_span) => {
 834                     span_err!(tcx.sess, f.span, E0124,
 835                               "field `{}` is already declared",
 836                               token::get_name(result.name));
 837                     span_note!(tcx.sess, *prev_span, "previously declared here");
 838                     true
 839                 },
 840                 None => false,
 841             };
 842             // FIXME(#6393) this whole dup thing is just to satisfy
 843             // the borrow checker :-(
 844             if !dup {
 845                 seen_fields.insert(result.name, f.span);
 846             }
 847         }
 848
 849         result
 850     }).collect();
 851
 852     tcx.struct_fields.borrow_mut().insert(local_def(id), Rc::new(field_tys));
 853
 854     let substs = mk_item_substs(ccx, &scheme.generics);
 855     let selfty = ty::mk_struct(tcx, local_def(id), tcx.mk_substs(substs));
 856
 857     // If this struct is enum-like or tuple-like, create the type of its
 858     // constructor.
 859     match struct_def.ctor_id {
 860         None => {}
 861         Some(ctor_id) => {
 862             if struct_def.fields.len() == 0 {
 863                 // Enum-like.
 864                 write_ty_to_tcx(tcx, ctor_id, selfty);
 865
 866                 tcx.tcache.borrow_mut().insert(local_def(ctor_id), scheme);
 867                 tcx.predicates.borrow_mut().insert(local_def(ctor_id), predicates);
 868             } else if struct_def.fields[0].node.kind.is_unnamed() {
 869                 // Tuple-like.
 870                 let inputs: Vec<_> = struct_def.fields.iter().map(
 871                         |field| (*tcx.tcache.borrow())[
 872                             local_def(field.node.id)].ty).collect();
 873                 let ctor_fn_ty = ty::mk_ctor_fn(tcx,
 874                                                 local_def(ctor_id),
 875                                                 &inputs[..],
 876                                                 selfty);
 877                 write_ty_to_tcx(tcx, ctor_id, ctor_fn_ty);
 878                 tcx.tcache.borrow_mut().insert(local_def(ctor_id),
 879                                                TypeScheme {
 880                                                    generics: scheme.generics,
 881                                                    ty: ctor_fn_ty
 882                                                });
 883                 tcx.predicates.borrow_mut().insert(local_def(ctor_id), predicates);
 884             }
 885         }
 886     }
 887 }
 888
 889 fn get_trait_def<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 890                            trait_id: ast::DefId)
 891                            -> Rc<ty::TraitDef<'tcx>> {
 892     let tcx = ccx.tcx;
 893
 894     if trait_id.krate != ast::LOCAL_CRATE {
 895         return ty::lookup_trait_def(tcx, trait_id)
 896     }
 897
 898     match tcx.map.get(trait_id.node) {
 899         ast_map::NodeItem(item) => trait_def_of_item(ccx, &*item),
 900         _ => {
 901             tcx.sess.bug(&format!("get_trait_def({}): not an item",
 902                                   trait_id.node)[])
 903         }
 904     }
 905 }
 906
 907 fn trait_def_of_item<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 908                                it: &ast::Item)
 909                                -> Rc<ty::TraitDef<'tcx>>
 910 {
 911     let def_id = local_def(it.id);
 912     let tcx = ccx.tcx;
 913
 914     if let Some(def) = tcx.trait_defs.borrow().get(&def_id) {
 915         return def.clone();
 916     }
 917
 918     let (unsafety, generics, bounds, items) = match it.node {
 919         ast::ItemTrait(unsafety,
 920                        ref generics,
 921                        ref supertraits,
 922                        ref items) => {
 923             (unsafety, generics, supertraits, items)
 924         }
 925         ref s => {
 926             tcx.sess.span_bug(
 927                 it.span,
 928                 &format!("trait_def_of_item invoked on {:?}", s)[]);
 929         }
 930     };
 931
 932     let paren_sugar = ty::has_attr(tcx, def_id, "rustc_paren_sugar");
 933     if paren_sugar && !ccx.tcx.sess.features.borrow().unboxed_closures {
 934         ccx.tcx.sess.span_err(
 935             it.span,
 936             "the `#[rustc_paren_sugar]` attribute is a temporary means of controlling \
 937              which traits can use parenthetical notation");
 938         span_help!(ccx.tcx.sess, it.span,
 939                    "add `#![feature(unboxed_closures)]` to \
 940                     the crate attributes to use it");
 941     }
 942
 943     let substs = ccx.tcx.mk_substs(mk_trait_substs(ccx, generics));
 944
 945     let ty_generics = ty_generics_for_trait(ccx, it.id, substs, generics);
 946
 947     let self_param_ty = ty::ParamTy::for_self().to_ty(ccx.tcx);
 948
 949     // supertraits:
 950     let bounds = compute_bounds(ccx,
 951                                 self_param_ty,
 952                                 bounds,
 953                                 SizedByDefault::No,
 954                                 it.span);
 955
 956     let associated_type_names: Vec<_> =
 957         items.iter()
 958              .filter_map(|item| {
 959                  match *item {
 960                      ast::RequiredMethod(_) | ast::ProvidedMethod(_) => None,
 961                      ast::TypeTraitItem(ref data) => Some(data.ty_param.ident.name),
 962                  }
 963              })
 964              .collect();
 965
 966     let trait_ref = Rc::new(ty::TraitRef {
 967         def_id: def_id,
 968         substs: substs,
 969     });
 970
 971     let trait_def = Rc::new(ty::TraitDef {
 972         paren_sugar: paren_sugar,
 973         unsafety: unsafety,
 974         generics: ty_generics,
 975         bounds: bounds,
 976         trait_ref: trait_ref,
 977         associated_type_names: associated_type_names,
 978     });
 979
 980     tcx.trait_defs.borrow_mut().insert(def_id, trait_def.clone());
 981
 982     return trait_def;
 983
 984     fn mk_trait_substs<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 985                                  generics: &ast::Generics)
 986                                  -> subst::Substs<'tcx>
 987     {
 988         let tcx = ccx.tcx;
 989
 990         // Creates a no-op substitution for the trait's type parameters.
 991         let regions =
 992             generics.lifetimes
 993                     .iter()
 994                     .enumerate()
 995                     .map(|(i, def)| ty::ReEarlyBound(def.lifetime.id,
 996                                                      subst::TypeSpace,
 997                                                      i as u32,
 998                                                      def.lifetime.name))
 999                     .collect();
1000
1001         // Start with the generics in the type parameters...
1002         let types: Vec<_> =
1003             generics.ty_params
1004                     .iter()
1005                     .enumerate()
1006                     .map(|(i, def)| ty::mk_param(tcx, subst::TypeSpace,
1007                                                  i as u32, def.ident.name))
1008                     .collect();
1009
1010         // ...and also create the `Self` parameter.
1011         let self_ty = ty::mk_self_type(tcx);
1012
1013         subst::Substs::new_trait(types, regions, self_ty)
1014     }
1015 }
1016
1017 fn convert_trait_predicates<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>, it: &ast::Item) {
1018     let tcx = ccx.tcx;
1019     let trait_def = trait_def_of_item(ccx, it);
1020
1021     let def_id = local_def(it.id);
1022
1023     let (generics, items) = match it.node {
1024         ast::ItemTrait(_, ref generics, _, ref items) => (generics, items),
1025         ref s => {
1026             tcx.sess.span_bug(
1027                 it.span,
1028                 &format!("trait_def_of_item invoked on {:?}", s)[]);
1029         }
1030     };
1031
1032     let self_param_ty = ty::ParamTy::for_self().to_ty(ccx.tcx);
1033
1034     let super_predicates = ty::predicates(ccx.tcx, self_param_ty, &trait_def.bounds);
1035
1036     let assoc_predicates = predicates_for_associated_types(ccx, &trait_def.trait_ref, items);
1037
1038     // `ty_generic_bounds` below will consider the bounds on the type
1039     // parameters (including `Self`) and the explicit where-clauses,
1040     // but to get the full set of predicates on a trait we need to add
1041     // in the supertrait bounds and anything declared on the
1042     // associated types.
1043     let mut base_predicates =
1044         ty::GenericPredicates {
1045             predicates: VecPerParamSpace::new(super_predicates, vec![], vec![])
1046         };
1047     base_predicates.predicates.extend(subst::TypeSpace, assoc_predicates.into_iter());
1048
1049     let self_bounds = &trait_def.generics.types.get_self().unwrap().bounds;
1050     base_predicates.predicates.extend(
1051         subst::SelfSpace,
1052         ty::predicates(ccx.tcx, self_param_ty, self_bounds).into_iter());
1053
1054     // add in the explicit where-clauses
1055     let trait_predicates =
1056         ty_generic_bounds(ccx,
1057                           subst::TypeSpace,
1058                           &trait_def.generics,
1059                           base_predicates,
1060                           &generics.where_clause);
1061
1062     let prev_predicates = tcx.predicates.borrow_mut().insert(def_id, trait_predicates);
1063     assert!(prev_predicates.is_none());
1064
1065     return;
1066
1067     fn predicates_for_associated_types<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
1068                                                  self_trait_ref: &Rc<ty::TraitRef<'tcx>>,
1069                                                  trait_items: &[ast::TraitItem])
1070                                                  -> Vec<ty::Predicate<'tcx>>
1071     {
1072         trait_items
1073             .iter()
1074             .flat_map(|trait_item| {
1075                 let assoc_type_def = match *trait_item {
1076                     ast::TypeTraitItem(ref assoc_type) => &assoc_type.ty_param,
1077                     ast::RequiredMethod(..) | ast::ProvidedMethod(..) => {
1078                         return vec!().into_iter();
1079                     }
1080                 };
1081
1082                 let assoc_ty = ty::mk_projection(ccx.tcx,
1083                                                  self_trait_ref.clone(),
1084                                                  assoc_type_def.ident.name);
1085
1086                 let bounds = compute_bounds(ccx,
1087                                             assoc_ty,
1088                                             &*assoc_type_def.bounds,
1089                                             SizedByDefault::Yes,
1090                                             assoc_type_def.span);
1091
1092                 ty::predicates(ccx.tcx, assoc_ty, &bounds).into_iter()
1093             })
1094             .collect()
1095     }
1096 }
1097
1098 fn type_scheme_of_item<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1099                                 it: &ast::Item)
1100                                 -> ty::TypeScheme<'tcx>
1101 {
1102     memoized(&ccx.tcx.tcache,
1103              local_def(it.id),
1104              |_| compute_type_scheme_of_item(ccx, it))
1105 }
1106
1107
1108 fn compute_type_scheme_of_item<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1109                                               it: &ast::Item)
1110                                               -> ty::TypeScheme<'tcx>
1111 {
1112     let tcx = ccx.tcx;
1113     match it.node {
1114         ast::ItemStatic(ref t, _, _) | ast::ItemConst(ref t, _) => {
1115             let ty = ccx.to_ty(&ExplicitRscope, &**t);
1116             ty::TypeScheme { ty: ty, generics: ty::Generics::empty() }
1117         }
1118         ast::ItemFn(ref decl, unsafety, abi, ref generics, _) => {
1119             let ty_generics = ty_generics_for_fn_or_method(ccx,
1120                                                            generics,
1121                                                            ty::Generics::empty());
1122             let tofd = astconv::ty_of_bare_fn(ccx, unsafety, abi, &**decl);
1123             let ty = ty::mk_bare_fn(tcx, Some(local_def(it.id)), tcx.mk_bare_fn(tofd));
1124             ty::TypeScheme { ty: ty, generics: ty_generics }
1125         }
1126         ast::ItemTy(ref t, ref generics) => {
1127             let ty = ccx.to_ty(&ExplicitRscope, &**t);
1128             let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
1129             ty::TypeScheme { ty: ty, generics: ty_generics }
1130         }
1131         ast::ItemEnum(_, ref generics) => {
1132             // Create a new generic polytype.
1133             let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
1134             let substs = mk_item_substs(ccx, &ty_generics);
1135             let t = ty::mk_enum(tcx, local_def(it.id), tcx.mk_substs(substs));
1136             ty::TypeScheme { ty: t, generics: ty_generics }
1137         }
1138         ast::ItemStruct(_, ref generics) => {
1139             let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
1140             let substs = mk_item_substs(ccx, &ty_generics);
1141             let t = ty::mk_struct(tcx, local_def(it.id), tcx.mk_substs(substs));
1142             ty::TypeScheme { ty: t, generics: ty_generics }
1143         }
1144         ast::ItemTrait(..) |
1145         ast::ItemImpl(..) |
1146         ast::ItemMod(..) |
1147         ast::ItemForeignMod(..) |
1148         ast::ItemExternCrate(..) |
1149         ast::ItemUse(..) |
1150         ast::ItemMac(..) => {
1151             tcx.sess.span_bug(
1152                 it.span,
1153                 format!("compute_type_scheme_of_item: unexpected item type: {:?}",
1154                         it.node).as_slice());
1155         }
1156     }
1157 }
1158
1159 fn convert_typed_item<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
1160                                 it: &ast::Item)
1161                                 -> (ty::TypeScheme<'tcx>, ty::GenericPredicates<'tcx>)
1162 {
1163     let tcx = ccx.tcx;
1164
1165     let tag = type_scheme_of_item(ccx, it);
1166     let scheme = TypeScheme { generics: tag.generics, ty: tag.ty };
1167     let predicates = match it.node {
1168         ast::ItemStatic(..) | ast::ItemConst(..) => {
1169             ty::GenericPredicates::empty()
1170         }
1171         ast::ItemFn(_, _, _, ref ast_generics, _) => {
1172             ty_generic_bounds_for_fn_or_method(ccx,
1173                                                ast_generics,
1174                                                &scheme.generics,
1175                                                ty::GenericPredicates::empty())
1176         }
1177         ast::ItemTy(_, ref generics) => {
1178             ty_generic_bounds_for_type_or_impl(ccx, &scheme.generics, generics)
1179         }
1180         ast::ItemEnum(_, ref generics) => {
1181             ty_generic_bounds_for_type_or_impl(ccx, &scheme.generics, generics)
1182         }
1183         ast::ItemStruct(_, ref generics) => {
1184             ty_generic_bounds_for_type_or_impl(ccx, &scheme.generics, generics)
1185         }
1186         ast::ItemTrait(..) |
1187         ast::ItemExternCrate(..) |
1188         ast::ItemUse(..) |
1189         ast::ItemImpl(..) |
1190         ast::ItemMod(..) |
1191         ast::ItemForeignMod(..) |
1192         ast::ItemMac(..) => {
1193             tcx.sess.span_bug(
1194                 it.span,
1195                 format!("compute_type_scheme_of_item: unexpected item type: {:?}",
1196                         it.node).as_slice());
1197         }
1198     };
1199
1200     let prev_predicates = tcx.predicates.borrow_mut().insert(local_def(it.id),
1201                                                              predicates.clone());
1202     assert!(prev_predicates.is_none());
1203
1204     // Debugging aid.
1205     if ty::has_attr(tcx, local_def(it.id), "rustc_object_lifetime_default") {
1206         let object_lifetime_default_reprs: String =
1207             scheme.generics.types.iter()
1208                                  .map(|t| match t.object_lifetime_default {
1209                                      Some(ty::ObjectLifetimeDefault::Specific(r)) =>
1210                                          r.user_string(tcx),
1211                                      d =>
1212                                          d.repr(ccx.tcx()),
1213                                  })
1214                                  .collect::<Vec<String>>()
1215                                  .connect(",");
1216
1217         tcx.sess.span_err(it.span, &object_lifetime_default_reprs);
1218     }
1219
1220     return (scheme, predicates);
1221 }
1222
1223 fn type_scheme_of_foreign_item<'a, 'tcx>(
1224     ccx: &CollectCtxt<'a, 'tcx>,
1225     it: &ast::ForeignItem,
1226     abi: abi::Abi)
1227     -> ty::TypeScheme<'tcx>
1228 {
1229     memoized(&ccx.tcx().tcache,
1230              local_def(it.id),
1231              |_| compute_type_scheme_of_foreign_item(ccx, it, abi))
1232 }
1233
1234 fn compute_type_scheme_of_foreign_item<'a, 'tcx>(
1235     ccx: &CollectCtxt<'a, 'tcx>,
1236     it: &ast::ForeignItem,
1237     abi: abi::Abi)
1238     -> ty::TypeScheme<'tcx>
1239 {
1240     match it.node {
1241         ast::ForeignItemFn(ref fn_decl, ref generics) => {
1242             compute_type_scheme_of_foreign_fn_decl(ccx, fn_decl, generics, abi)
1243         }
1244         ast::ForeignItemStatic(ref t, _) => {
1245             ty::TypeScheme {
1246                 generics: ty::Generics::empty(),
1247                 ty: ast_ty_to_ty(ccx, &ExplicitRscope, t)
1248             }
1249         }
1250     }
1251 }
1252
1253 fn convert_foreign_item<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
1254                                   it: &ast::ForeignItem)
1255 {
1256     // For reasons I cannot fully articulate, I do so hate the AST
1257     // map, and I regard each time that I use it as a personal and
1258     // moral failing, but at the moment it seems like the only
1259     // convenient way to extract the ABI. - ndm
1260     let tcx = ccx.tcx;
1261     let abi = tcx.map.get_foreign_abi(it.id);
1262
1263     let scheme = type_scheme_of_foreign_item(ccx, it, abi);
1264     write_ty_to_tcx(ccx.tcx, it.id, scheme.ty);
1265
1266     let predicates = match it.node {
1267         ast::ForeignItemFn(_, ref generics) => {
1268             ty_generic_bounds_for_fn_or_method(ccx,
1269                                                generics,
1270                                                &scheme.generics,
1271                                                ty::GenericPredicates::empty())
1272         }
1273         ast::ForeignItemStatic(..) => {
1274             ty::GenericPredicates::empty()
1275         }
1276     };
1277
1278     let prev_predicates = tcx.predicates.borrow_mut().insert(local_def(it.id), predicates);
1279     assert!(prev_predicates.is_none());
1280 }
1281
1282 fn ty_generics_for_type_or_impl<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
1283                                           generics: &ast::Generics)
1284                                           -> ty::Generics<'tcx> {
1285     ty_generics(ccx,
1286                 subst::TypeSpace,
1287                 &generics.lifetimes[],
1288                 &generics.ty_params[],
1289                 &generics.where_clause,
1290                 ty::Generics::empty())
1291 }
1292
1293 fn ty_generic_bounds_for_type_or_impl<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1294                                                ty_generics: &ty::Generics<'tcx>,
1295                                                generics: &ast::Generics)
1296                                                -> ty::GenericPredicates<'tcx>
1297 {
1298     ty_generic_bounds(ccx,
1299                       subst::TypeSpace,
1300                       ty_generics,
1301                       ty::GenericPredicates::empty(),
1302                       &generics.where_clause)
1303 }
1304
1305 fn ty_generics_for_trait<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
1306                                    trait_id: ast::NodeId,
1307                                    substs: &'tcx subst::Substs<'tcx>,
1308                                    ast_generics: &ast::Generics)
1309                                    -> ty::Generics<'tcx>
1310 {
1311     debug!("ty_generics_for_trait(trait_id={}, substs={})",
1312            local_def(trait_id).repr(ccx.tcx), substs.repr(ccx.tcx));
1313
1314     let mut generics =
1315         ty_generics(ccx,
1316                     subst::TypeSpace,
1317                     &ast_generics.lifetimes[],
1318                     &ast_generics.ty_params[],
1319                     &ast_generics.where_clause,
1320                     ty::Generics::empty());
1321
1322     // Add in the self type parameter.
1323     //
1324     // Something of a hack: use the node id for the trait, also as
1325     // the node id for the Self type parameter.
1326     let param_id = trait_id;
1327
1328     let self_trait_ref =
1329         Rc::new(ty::TraitRef { def_id: local_def(trait_id),
1330                                substs: substs });
1331
1332     let def = ty::TypeParameterDef {
1333         space: subst::SelfSpace,
1334         index: 0,
1335         name: special_idents::type_self.name,
1336         def_id: local_def(param_id),
1337         bounds: ty::ParamBounds {
1338             region_bounds: vec!(),
1339             builtin_bounds: ty::empty_builtin_bounds(),
1340             trait_bounds: vec!(ty::Binder(self_trait_ref.clone())),
1341             projection_bounds: vec!(),
1342         },
1343         default: None,
1344         object_lifetime_default: None,
1345     };
1346
1347     ccx.tcx.ty_param_defs.borrow_mut().insert(param_id, def.clone());
1348
1349     generics.types.push(subst::SelfSpace, def);
1350
1351     return generics;
1352 }
1353
1354 fn ty_generics_for_fn_or_method<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1355                                          generics: &ast::Generics,
1356                                          base_generics: ty::Generics<'tcx>)
1357                                          -> ty::Generics<'tcx>
1358 {
1359     let early_lifetimes = resolve_lifetime::early_bound_lifetimes(generics);
1360     ty_generics(ccx,
1361                 subst::FnSpace,
1362                 &early_lifetimes[..],
1363                 &generics.ty_params[],
1364                 &generics.where_clause,
1365                 base_generics)
1366 }
1367
1368 fn ty_generic_bounds_for_fn_or_method<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1369                                                generics: &ast::Generics,
1370                                                ty_generics: &ty::Generics<'tcx>,
1371                                                base: ty::GenericPredicates<'tcx>)
1372                                                -> ty::GenericPredicates<'tcx>
1373 {
1374     ty_generic_bounds(ccx,
1375                       subst::FnSpace,
1376                       ty_generics,
1377                       base,
1378                       &generics.where_clause)
1379 }
1380
1381 // Add the Sized bound, unless the type parameter is marked as `?Sized`.
1382 fn add_unsized_bound<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1383                               bounds: &mut ty::BuiltinBounds,
1384                               ast_bounds: &[ast::TyParamBound],
1385                               span: Span)
1386 {
1387     // Try to find an unbound in bounds.
1388     let mut unbound = None;
1389     for ab in ast_bounds {
1390         if let &ast::TraitTyParamBound(ref ptr, ast::TraitBoundModifier::Maybe) = ab  {
1391             if unbound.is_none() {
1392                 assert!(ptr.bound_lifetimes.is_empty());
1393                 unbound = Some(ptr.trait_ref.clone());
1394             } else {
1395                 span_err!(ccx.tcx.sess, span, E0203,
1396                           "type parameter has more than one relaxed default \
1397                                                 bound, only one is supported");
1398             }
1399         }
1400     }
1401
1402     let kind_id = ccx.tcx.lang_items.require(SizedTraitLangItem);
1403     match unbound {
1404         Some(ref tpb) => {
1405             // FIXME(#8559) currently requires the unbound to be built-in.
1406             let trait_def_id = ty::trait_ref_to_def_id(ccx.tcx, tpb);
1407             match kind_id {
1408                 Ok(kind_id) if trait_def_id != kind_id => {
1409                     ccx.tcx.sess.span_warn(span,
1410                                               "default bound relaxed for a type parameter, but \
1411                                                this does nothing because the given bound is not \
1412                                                a default. Only `?Sized` is supported");
1413                     ty::try_add_builtin_trait(ccx.tcx,
1414                                               kind_id,
1415                                               bounds);
1416                 }
1417                 _ => {}
1418             }
1419         }
1420         _ if kind_id.is_ok() => {
1421             ty::try_add_builtin_trait(ccx.tcx, kind_id.unwrap(), bounds);
1422         }
1423         // No lang item for Sized, so we can't add it as a bound.
1424         None => {}
1425     }
1426 }
1427
1428 fn ty_generic_bounds<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1429                               space: subst::ParamSpace,
1430                               generics: &ty::Generics<'tcx>,
1431                               base: ty::GenericPredicates<'tcx>,
1432                               where_clause: &ast::WhereClause)
1433                               -> ty::GenericPredicates<'tcx>
1434 {
1435     let tcx = ccx.tcx;
1436     let mut result = base;
1437
1438     // For now, scrape the bounds out of parameters from Generics. This is not great.
1439     for def in generics.regions.get_slice(space) {
1440         let r_a = def.to_early_bound_region();
1441         for &r_b in &def.bounds {
1442             let outlives = ty::Binder(ty::OutlivesPredicate(r_a, r_b));
1443             result.predicates.push(def.space, ty::Predicate::RegionOutlives(outlives));
1444         }
1445     }
1446     for def in generics.types.get_slice(space) {
1447         let t = ty::mk_param_from_def(ccx.tcx, def);
1448         result.predicates.extend(def.space, ty::predicates(ccx.tcx, t, &def.bounds).into_iter());
1449     }
1450
1451     // Add the bounds not associated with a type parameter
1452     for predicate in &where_clause.predicates {
1453         match predicate {
1454             &ast::WherePredicate::BoundPredicate(ref bound_pred) => {
1455                 let ty = ast_ty_to_ty(ccx, &ExplicitRscope, &*bound_pred.bounded_ty);
1456
1457                 for bound in &*bound_pred.bounds {
1458                     match bound {
1459                         &ast::TyParamBound::TraitTyParamBound(ref poly_trait_ref, _) => {
1460                             let mut projections = Vec::new();
1461
1462                             let trait_ref = astconv::instantiate_poly_trait_ref(
1463                                 ccx,
1464                                 &ExplicitRscope,
1465                                 poly_trait_ref,
1466                                 Some(ty),
1467                                 &mut projections,
1468                             );
1469
1470                             result.predicates.push(space, trait_ref.as_predicate());
1471
1472                             for projection in &projections {
1473                                 result.predicates.push(space, projection.as_predicate());
1474                             }
1475                         }
1476
1477                         &ast::TyParamBound::RegionTyParamBound(ref lifetime) => {
1478                             let region = ast_region_to_region(tcx, lifetime);
1479                             let pred = ty::Binder(ty::OutlivesPredicate(ty, region));
1480                             result.predicates.push(space, ty::Predicate::TypeOutlives(pred))
1481                         }
1482                     }
1483                 }
1484             }
1485
1486             &ast::WherePredicate::RegionPredicate(ref region_pred) => {
1487                 let r1 = ast_region_to_region(tcx, &region_pred.lifetime);
1488                 for bound in &region_pred.bounds {
1489                     let r2 = ast_region_to_region(tcx, bound);
1490                     let pred = ty::Binder(ty::OutlivesPredicate(r1, r2));
1491                     result.predicates.push(space, ty::Predicate::RegionOutlives(pred))
1492                 }
1493             }
1494
1495             &ast::WherePredicate::EqPredicate(ref eq_pred) => {
1496                 // FIXME(#20041)
1497                 tcx.sess.span_bug(eq_pred.span,
1498                                     "Equality constraints are not yet \
1499                                         implemented (#20041)")
1500             }
1501         }
1502     }
1503
1504     return result;
1505 }
1506
1507 fn ty_generics<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1508                         space: subst::ParamSpace,
1509                         lifetime_defs: &[ast::LifetimeDef],
1510                         types: &[ast::TyParam],
1511                         where_clause: &ast::WhereClause,
1512                         base_generics: ty::Generics<'tcx>)
1513                         -> ty::Generics<'tcx>
1514 {
1515     let tcx = ccx.tcx;
1516     let mut result = base_generics;
1517
1518     for (i, l) in lifetime_defs.iter().enumerate() {
1519         let bounds = l.bounds.iter()
1520                              .map(|l| ast_region_to_region(tcx, l))
1521                              .collect();
1522         let def = ty::RegionParameterDef { name: l.lifetime.name,
1523                                            space: space,
1524                                            index: i as u32,
1525                                            def_id: local_def(l.lifetime.id),
1526                                            bounds: bounds };
1527         // debug!("ty_generics: def for region param: {:?}",
1528         //        def.repr(tcx));
1529         result.regions.push(space, def);
1530     }
1531
1532     assert!(result.types.is_empty_in(space));
1533
1534     // Now create the real type parameters.
1535     for (i, param) in types.iter().enumerate() {
1536         let def = get_or_create_type_parameter_def(ccx, space, param, i as u32, where_clause);
1537         debug!("ty_generics: def for type param: {:?}, {:?}", def, space);
1538         result.types.push(space, def);
1539     }
1540
1541     result
1542 }
1543
1544 fn get_or_create_type_parameter_def<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1545                                              space: subst::ParamSpace,
1546                                              param: &ast::TyParam,
1547                                              index: u32,
1548                                              where_clause: &ast::WhereClause)
1549                                              -> ty::TypeParameterDef<'tcx>
1550 {
1551     let tcx = ccx.tcx;
1552     match tcx.ty_param_defs.borrow().get(&param.id) {
1553         Some(d) => { return d.clone(); }
1554         None => { }
1555     }
1556
1557     let param_ty = ty::ParamTy::new(space, index, param.ident.name);
1558     let bounds = compute_bounds(ccx,
1559                                 param_ty.to_ty(ccx.tcx),
1560                                 &param.bounds[],
1561                                 SizedByDefault::Yes,
1562                                 param.span);
1563     let default = match param.default {
1564         None => None,
1565         Some(ref path) => {
1566             let ty = ast_ty_to_ty(ccx, &ExplicitRscope, &**path);
1567             let cur_idx = index;
1568
1569             ty::walk_ty(ty, |t| {
1570                 match t.sty {
1571                     ty::ty_param(p) => if p.idx > cur_idx {
1572                         span_err!(tcx.sess, path.span, E0128,
1573                                   "type parameters with a default cannot use \
1574                                   forward declared identifiers");
1575                         },
1576                         _ => {}
1577                     }
1578             });
1579
1580             Some(ty)
1581         }
1582     };
1583
1584     let object_lifetime_default =
1585         compute_object_lifetime_default(ccx, space, index, &param.bounds, where_clause);
1586
1587     let def = ty::TypeParameterDef {
1588         space: space,
1589         index: index,
1590         name: param.ident.name,
1591         def_id: local_def(param.id),
1592         bounds: bounds,
1593         default: default,
1594         object_lifetime_default: object_lifetime_default,
1595     };
1596
1597     tcx.ty_param_defs.borrow_mut().insert(param.id, def.clone());
1598
1599     def
1600 }
1601
1602 /// Scan the bounds and where-clauses on a parameter to extract bounds
1603 /// of the form `T:'a` so as to determine the `ObjectLifetimeDefault`.
1604 /// This runs as part of computing the minimal type scheme, so we
1605 /// intentionally avoid just asking astconv to convert all the where
1606 /// clauses into a `ty::Predicate`. This is because that could induce
1607 /// artificial cycles.
1608 fn compute_object_lifetime_default<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1609                                             space: subst::ParamSpace,
1610                                             index: u32,
1611                                             param_bounds: &[ast::TyParamBound],
1612                                             where_clause: &ast::WhereClause)
1613                                             -> Option<ty::ObjectLifetimeDefault>
1614 {
1615     let inline_bounds = from_bounds(ccx, param_bounds);
1616     let where_bounds = from_predicates(ccx, space, index, &where_clause.predicates);
1617     let all_bounds: HashSet<_> = inline_bounds.into_iter()
1618                                               .chain(where_bounds.into_iter())
1619                                               .collect();
1620     return if all_bounds.len() > 1 {
1621         Some(ty::ObjectLifetimeDefault::Ambiguous)
1622     } else {
1623         all_bounds.into_iter()
1624                   .next()
1625                   .map(ty::ObjectLifetimeDefault::Specific)
1626     };
1627
1628     fn from_bounds<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1629                             bounds: &[ast::TyParamBound])
1630                             -> Vec<ty::Region>
1631     {
1632         bounds.iter()
1633               .filter_map(|bound| {
1634                   match *bound {
1635                       ast::TraitTyParamBound(..) =>
1636                           None,
1637                       ast::RegionTyParamBound(ref lifetime) =>
1638                           Some(astconv::ast_region_to_region(ccx.tcx(), lifetime)),
1639                   }
1640               })
1641               .collect()
1642     }
1643
1644     fn from_predicates<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1645                                 space: subst::ParamSpace,
1646                                 index: u32,
1647                                 predicates: &[ast::WherePredicate])
1648                                 -> Vec<ty::Region>
1649     {
1650         predicates.iter()
1651                   .flat_map(|predicate| {
1652                       match *predicate {
1653                           ast::WherePredicate::BoundPredicate(ref data) => {
1654                               if data.bound_lifetimes.len() == 0 &&
1655                                   is_param(ccx, &data.bounded_ty, space, index)
1656                               {
1657                                   from_bounds(ccx, &data.bounds).into_iter()
1658                               } else {
1659                                   Vec::new().into_iter()
1660                               }
1661                           }
1662                           ast::WherePredicate::RegionPredicate(..) |
1663                           ast::WherePredicate::EqPredicate(..) => {
1664                               Vec::new().into_iter()
1665                           }
1666                       }
1667                   })
1668                   .collect()
1669     }
1670
1671     fn is_param(ccx: &CollectCtxt,
1672                 ast_ty: &ast::Ty,
1673                 space: subst::ParamSpace,
1674                 index: u32)
1675                 -> bool
1676     {
1677         match ast_ty.node {
1678             ast::TyPath(_, id) => {
1679                 match ccx.tcx.def_map.borrow()[id] {
1680                     def::DefTyParam(s, i, _, _) => {
1681                         space == s && index == i
1682                     }
1683                     _ => {
1684                         false
1685                     }
1686                 }
1687             }
1688             _ => {
1689                 false
1690             }
1691         }
1692     }
1693 }
1694
1695 enum SizedByDefault { Yes, No }
1696
1697 /// Translate the AST's notion of ty param bounds (which are an enum consisting of a newtyped Ty or
1698 /// a region) to ty's notion of ty param bounds, which can either be user-defined traits, or the
1699 /// built-in trait (formerly known as kind): Send.
1700 fn compute_bounds<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1701                            param_ty: ty::Ty<'tcx>,
1702                            ast_bounds: &[ast::TyParamBound],
1703                            sized_by_default: SizedByDefault,
1704                            span: Span)
1705                            -> ty::ParamBounds<'tcx>
1706 {
1707     let mut param_bounds = conv_param_bounds(ccx,
1708                                              span,
1709                                              param_ty,
1710                                              ast_bounds);
1711
1712     if let SizedByDefault::Yes = sized_by_default {
1713         add_unsized_bound(ccx,
1714                           &mut param_bounds.builtin_bounds,
1715                           ast_bounds,
1716                           span);
1717
1718         check_bounds_compatible(ccx,
1719                                 param_ty,
1720                                 &param_bounds,
1721                                 span);
1722     }
1723
1724     param_bounds.trait_bounds.sort_by(|a,b| a.def_id().cmp(&b.def_id()));
1725
1726     param_bounds
1727 }
1728
1729 fn check_bounds_compatible<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1730                                     param_ty: Ty<'tcx>,
1731                                     param_bounds: &ty::ParamBounds<'tcx>,
1732                                     span: Span) {
1733     if !param_bounds.builtin_bounds.contains(&ty::BoundSized) {
1734         ty::each_bound_trait_and_supertraits(
1735             ccx.tcx,
1736             &param_bounds.trait_bounds[],
1737             |trait_ref| {
1738                 let trait_def = ccx.get_trait_def(trait_ref.def_id());
1739                 if trait_def.bounds.builtin_bounds.contains(&ty::BoundSized) {
1740                     span_err!(ccx.tcx.sess, span, E0129,
1741                               "incompatible bounds on `{}`, \
1742                                bound `{}` does not allow unsized type",
1743                               param_ty.user_string(ccx.tcx),
1744                               trait_ref.user_string(ccx.tcx));
1745                 }
1746                 true
1747             });
1748     }
1749 }
1750
1751 fn conv_param_bounds<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
1752                               span: Span,
1753                               param_ty: ty::Ty<'tcx>,
1754                               ast_bounds: &[ast::TyParamBound])
1755                               -> ty::ParamBounds<'tcx>
1756 {
1757     let tcx = ccx.tcx;
1758     let astconv::PartitionedBounds {
1759         builtin_bounds,
1760         trait_bounds,
1761         region_bounds
1762     } = astconv::partition_bounds(tcx, span, ast_bounds.as_slice());
1763
1764     let mut projection_bounds = Vec::new();
1765
1766     let trait_bounds: Vec<ty::PolyTraitRef> =
1767         trait_bounds.into_iter()
1768         .map(|bound| {
1769             astconv::instantiate_poly_trait_ref(ccx,
1770                                                 &ExplicitRscope,
1771                                                 bound,
1772                                                 Some(param_ty),
1773                                                 &mut projection_bounds)
1774         })
1775     .collect();
1776
1777     let region_bounds: Vec<ty::Region> =
1778         region_bounds.into_iter()
1779                      .map(|r| ast_region_to_region(ccx.tcx, r))
1780                      .collect();
1781
1782     ty::ParamBounds {
1783         region_bounds: region_bounds,
1784         builtin_bounds: builtin_bounds,
1785         trait_bounds: trait_bounds,
1786         projection_bounds: projection_bounds,
1787     }
1788 }
1789
1790 fn compute_type_scheme_of_foreign_fn_decl<'a, 'tcx>(
1791     ccx: &CollectCtxt<'a, 'tcx>,
1792     decl: &ast::FnDecl,
1793     ast_generics: &ast::Generics,
1794     abi: abi::Abi)
1795     -> ty::TypeScheme<'tcx>
1796 {
1797     for i in decl.inputs.iter() {
1798         match (*i).pat.node {
1799             ast::PatIdent(_, _, _) => (),
1800             ast::PatWild(ast::PatWildSingle) => (),
1801             _ => {
1802                 span_err!(ccx.tcx.sess, (*i).pat.span, E0130,
1803                           "patterns aren't allowed in foreign function declarations");
1804             }
1805         }
1806     }
1807
1808     let ty_generics = ty_generics_for_fn_or_method(ccx, ast_generics, ty::Generics::empty());
1809
1810     let rb = BindingRscope::new();
1811     let input_tys = decl.inputs
1812                         .iter()
1813                         .map(|a| ty_of_arg(ccx, &rb, a, None))
1814                         .collect();
1815
1816     let output = match decl.output {
1817         ast::Return(ref ty) =>
1818             ty::FnConverging(ast_ty_to_ty(ccx, &rb, &**ty)),
1819         ast::DefaultReturn(..) =>
1820             ty::FnConverging(ty::mk_nil(ccx.tcx)),
1821         ast::NoReturn(..) =>
1822             ty::FnDiverging
1823     };
1824
1825     let t_fn = ty::mk_bare_fn(
1826         ccx.tcx,
1827         None,
1828         ccx.tcx.mk_bare_fn(ty::BareFnTy {
1829             abi: abi,
1830             unsafety: ast::Unsafety::Unsafe,
1831             sig: ty::Binder(ty::FnSig {inputs: input_tys,
1832                                        output: output,
1833                                        variadic: decl.variadic}),
1834         }));
1835
1836     ty::TypeScheme {
1837         generics: ty_generics,
1838         ty: t_fn
1839     }
1840 }
1841
1842 fn mk_item_substs<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
1843                             ty_generics: &ty::Generics<'tcx>)
1844                             -> subst::Substs<'tcx>
1845 {
1846     let types =
1847         ty_generics.types.map(
1848             |def| ty::mk_param_from_def(ccx.tcx, def));
1849
1850     let regions =
1851         ty_generics.regions.map(
1852             |def| def.to_early_bound_region());
1853
1854     subst::Substs::new(types, regions)
1855 }
1856
1857 /// Verifies that the explicit self type of a method matches the impl
1858 /// or trait. This is a bit weird but basically because right now we
1859 /// don't handle the general case, but instead map it to one of
1860 /// several pre-defined options using various heuristics, this method
1861 /// comes back to check after the fact that explicit type the user
1862 /// wrote actually matches what the pre-defined option said.
1863 fn check_method_self_type<'a, 'tcx, RS:RegionScope>(
1864     ccx: &CollectCtxt<'a, 'tcx>,
1865     rs: &RS,
1866     required_type: Ty<'tcx>,
1867     explicit_self: &ast::ExplicitSelf,
1868     body_id: ast::NodeId)
1869 {
1870     let tcx = ccx.tcx;
1871     if let ast::SelfExplicit(ref ast_type, _) = explicit_self.node {
1872         let typ = ccx.to_ty(rs, &**ast_type);
1873         let base_type = match typ.sty {
1874             ty::ty_ptr(tm) | ty::ty_rptr(_, tm) => tm.ty,
1875             ty::ty_uniq(typ) => typ,
1876             _ => typ,
1877         };
1878
1879         let body_scope = region::DestructionScopeData::new(body_id);
1880
1881         // "Required type" comes from the trait definition. It may
1882         // contain late-bound regions from the method, but not the
1883         // trait (since traits only have early-bound region
1884         // parameters).
1885         assert!(!base_type.has_regions_escaping_depth(1));
1886         let required_type_free =
1887             liberate_early_bound_regions(
1888                 tcx, body_scope,
1889                 &ty::liberate_late_bound_regions(
1890                     tcx, body_scope, &ty::Binder(required_type)));
1891
1892         // The "base type" comes from the impl. It too may have late-bound
1893         // regions from the method.
1894         assert!(!base_type.has_regions_escaping_depth(1));
1895         let base_type_free =
1896             liberate_early_bound_regions(
1897                 tcx, body_scope,
1898                 &ty::liberate_late_bound_regions(
1899                     tcx, body_scope, &ty::Binder(base_type)));
1900
1901         debug!("required_type={} required_type_free={} \
1902                 base_type={} base_type_free={}",
1903                required_type.repr(tcx),
1904                required_type_free.repr(tcx),
1905                base_type.repr(tcx),
1906                base_type_free.repr(tcx));
1907
1908         let infcx = infer::new_infer_ctxt(tcx);
1909         drop(::require_same_types(tcx,
1910                                   Some(&infcx),
1911                                   false,
1912                                   explicit_self.span,
1913                                   base_type_free,
1914                                   required_type_free,
1915                                   || {
1916                 format!("mismatched self type: expected `{}`",
1917                         ppaux::ty_to_string(tcx, required_type))
1918         }));
1919         infcx.resolve_regions_and_report_errors(body_id);
1920     }
1921
1922     fn liberate_early_bound_regions<'tcx,T>(
1923         tcx: &ty::ctxt<'tcx>,
1924         scope: region::DestructionScopeData,
1925         value: &T)
1926         -> T
1927         where T : TypeFoldable<'tcx> + Repr<'tcx>
1928     {
1929         /*!
1930          * Convert early-bound regions into free regions; normally this is done by
1931          * applying the `free_substs` from the `ParameterEnvironment`, but this particular
1932          * method-self-type check is kind of hacky and done very early in the process,
1933          * before we really have a `ParameterEnvironment` to check.
1934          */
1935
1936         ty_fold::fold_regions(tcx, value, |region, _| {
1937             match region {
1938                 ty::ReEarlyBound(id, _, _, name) => {
1939                     let def_id = local_def(id);
1940                     ty::ReFree(ty::FreeRegion { scope: scope,
1941                                                 bound_region: ty::BrNamed(def_id, name) })
1942                 }
1943                 _ => region
1944             }
1945         })
1946     }
1947 }
1948
1949 /// Checks that all the type parameters on an impl
1950 fn enforce_impl_ty_params_are_constrained<'tcx>(tcx: &ty::ctxt<'tcx>,
1951                                                 ast_generics: &ast::Generics,
1952                                                 impl_def_id: ast::DefId)
1953 {
1954     let impl_scheme = ty::lookup_item_type(tcx, impl_def_id);
1955     let impl_predicates = ty::lookup_predicates(tcx, impl_def_id);
1956     let impl_trait_ref = ty::impl_trait_ref(tcx, impl_def_id);
1957
1958     // The trait reference is an input, so find all type parameters
1959     // reachable from there, to start (if this is an inherent impl,
1960     // then just examine the self type).
1961     let mut input_parameters: HashSet<_> =
1962         impl_trait_ref.iter()
1963                       .flat_map(|t| t.input_types().iter()) // Types in trait ref, if any
1964                       .chain(Some(impl_scheme.ty).iter())   // Self type, always
1965                       .flat_map(|t| t.walk())
1966                       .filter_map(|t| t.as_opt_param_ty())
1967                       .collect();
1968
1969     identify_constrained_type_params(tcx,
1970                                      impl_predicates.predicates.as_slice(),
1971                                      impl_trait_ref,
1972                                      &mut input_parameters);
1973
1974     for (index, ty_param) in ast_generics.ty_params.iter().enumerate() {
1975         let param_ty = ty::ParamTy { space: TypeSpace,
1976                                      idx: index as u32,
1977                                      name: ty_param.ident.name };
1978         if !input_parameters.contains(&param_ty) {
1979             if ty::has_attr(tcx, impl_def_id, "old_impl_check") {
1980                 tcx.sess.span_warn(
1981                     ty_param.span,
1982                     &format!("the type parameter `{}` is not constrained by the \
1983                               impl trait, self type, or predicates",
1984                              param_ty.user_string(tcx)));
1985             } else {
1986                 span_err!(tcx.sess, ty_param.span, E0207,
1987                     "the type parameter `{}` is not constrained by the \
1988                              impl trait, self type, or predicates",
1989                             param_ty.user_string(tcx));
1990             }
1991         }
1992     }
1993 }