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 is no
  30 clear set of phases we can enforce (e.g., converting traits first,
  31 then types, or something like that) because the user can introduce
  32 arbitrary interdependencies. So instead we generally convert things
  33 lazilly and on demand, and include logic that checks for cycles.
  34 Demand is driven by calls to `AstConv::get_item_type_scheme` or
  35 `AstConv::lookup_trait_def`.
  36
  37 Currently, we "convert" types and traits in three phases (note that
  38 conversion only affects the types of items / enum variants / methods;
  39 it does not e.g. compute the types of individual expressions):
  40
  41 0. Intrinsics
  42 1. Trait definitions
  43 2. Type definitions
  44
  45 Conversion itself is done by simply walking each of the items in turn
  46 and invoking an appropriate function (e.g., `trait_def_of_item` or
  47 `convert_item`). However, it is possible that while converting an
  48 item, we may need to compute the *type scheme* or *trait definition*
  49 for other items.
  50
  51 There are some shortcomings in this design:
  52
  53 - Before walking the set of supertraits for a given trait, you must
  54   call `ensure_super_predicates` on that trait def-id. Otherwise,
  55   `lookup_super_predicates` will result in ICEs.
  56 - Because the type scheme includes defaults, cycles through type
  57   parameter defaults are illegal even if those defaults are never
  58   employed. This is not necessarily a bug.
  59 - The phasing of trait definitions before type definitions does not
  60   seem to be necessary, sufficient, or particularly helpful, given that
  61   processing a trait definition can trigger processing a type def and
  62   vice versa. However, if I remove it, I get ICEs, so some more work is
  63   needed in that area. -nmatsakis
  64
  65 */
  66
  67 use astconv::{self, AstConv, ty_of_arg, ast_ty_to_ty, ast_region_to_region};
  68 use middle::def;
  69 use constrained_type_params as ctp;
  70 use middle::lang_items::SizedTraitLangItem;
  71 use middle::free_region::FreeRegionMap;
  72 use middle::region;
  73 use middle::resolve_lifetime;
  74 use middle::subst::{Substs, FnSpace, ParamSpace, SelfSpace, TypeSpace, VecPerParamSpace};
  75 use middle::ty::{ToPredicate, ImplContainer, ImplOrTraitItemContainer, TraitContainer};
  76 use middle::ty::{self, RegionEscape, ToPolyTraitRef, Ty, TypeScheme};
  77 use middle::ty_fold::{self, TypeFolder, TypeFoldable};
  78 use middle::infer;
  79 use rscope::*;
  80 use rustc::ast_map;
  81 use util::common::{ErrorReported, memoized};
  82 use util::nodemap::{FnvHashMap, FnvHashSet};
  83 use write_ty_to_tcx;
  84
  85 use std::cell::{Cell, RefCell};
  86 use std::collections::HashSet;
  87 use std::rc::Rc;
  88
  89 use syntax::abi;
  90 use syntax::ast;
  91 use syntax::ast_util::local_def;
  92 use syntax::codemap::Span;
  93 use syntax::parse::token::special_idents;
  94 use syntax::parse::token;
  95 use syntax::ptr::P;
  96 use syntax::visit;
  97
  98 ///////////////////////////////////////////////////////////////////////////
  99 // Main entry point
 100
 101 pub fn collect_item_types(tcx: &ty::ctxt) {
 102     let ccx = &CrateCtxt { tcx: tcx, stack: RefCell::new(Vec::new()) };
 103
 104     let mut visitor = CollectTraitDefVisitor{ ccx: ccx };
 105     visit::walk_crate(&mut visitor, ccx.tcx.map.krate());
 106
 107     let mut visitor = CollectItemTypesVisitor{ ccx: ccx };
 108     visit::walk_crate(&mut visitor, ccx.tcx.map.krate());
 109 }
 110
 111 ///////////////////////////////////////////////////////////////////////////
 112
 113 struct CrateCtxt<'a,'tcx:'a> {
 114     tcx: &'a ty::ctxt<'tcx>,
 115
 116     // This stack is used to identify cycles in the user's source.
 117     // Note that these cycles can cross multiple items.
 118     stack: RefCell<Vec<AstConvRequest>>,
 119 }
 120
 121 /// Context specific to some particular item. This is what implements
 122 /// AstConv. It has information about the predicates that are defined
 123 /// on the trait. Unfortunately, this predicate information is
 124 /// available in various different forms at various points in the
 125 /// process. So we can't just store a pointer to e.g. the AST or the
 126 /// parsed ty form, we have to be more flexible. To this end, the
 127 /// `ItemCtxt` is parameterized by a `GetTypeParameterBounds` object
 128 /// that it uses to satisfy `get_type_parameter_bounds` requests.
 129 /// This object might draw the information from the AST
 130 /// (`ast::Generics`) or it might draw from a `ty::GenericPredicates`
 131 /// or both (a tuple).
 132 struct ItemCtxt<'a,'tcx:'a> {
 133     ccx: &'a CrateCtxt<'a,'tcx>,
 134     param_bounds: &'a (GetTypeParameterBounds<'tcx>+'a),
 135 }
 136
 137 #[derive(Copy, Clone, PartialEq, Eq)]
 138 enum AstConvRequest {
 139     GetItemTypeScheme(ast::DefId),
 140     GetTraitDef(ast::DefId),
 141     EnsureSuperPredicates(ast::DefId),
 142     GetTypeParameterBounds(ast::NodeId),
 143 }
 144
 145 ///////////////////////////////////////////////////////////////////////////
 146 // First phase: just collect *trait definitions* -- basically, the set
 147 // of type parameters and supertraits. This is information we need to
 148 // know later when parsing field defs.
 149
 150 struct CollectTraitDefVisitor<'a, 'tcx: 'a> {
 151     ccx: &'a CrateCtxt<'a, 'tcx>
 152 }
 153
 154 impl<'a, 'tcx, 'v> visit::Visitor<'v> for CollectTraitDefVisitor<'a, 'tcx> {
 155     fn visit_item(&mut self, i: &ast::Item) {
 156         match i.node {
 157             ast::ItemTrait(..) => {
 158                 // computing the trait def also fills in the table
 159                 let _ = trait_def_of_item(self.ccx, i);
 160             }
 161             _ => { }
 162         }
 163
 164         visit::walk_item(self, i);
 165     }
 166 }
 167
 168 ///////////////////////////////////////////////////////////////////////////
 169 // Second phase: collection proper.
 170
 171 struct CollectItemTypesVisitor<'a, 'tcx: 'a> {
 172     ccx: &'a CrateCtxt<'a, 'tcx>
 173 }
 174
 175 impl<'a, 'tcx, 'v> visit::Visitor<'v> for CollectItemTypesVisitor<'a, 'tcx> {
 176     fn visit_item(&mut self, i: &ast::Item) {
 177         convert_item(self.ccx, i);
 178         visit::walk_item(self, i);
 179     }
 180     fn visit_foreign_item(&mut self, i: &ast::ForeignItem) {
 181         convert_foreign_item(self.ccx, i);
 182         visit::walk_foreign_item(self, i);
 183     }
 184 }
 185
 186 ///////////////////////////////////////////////////////////////////////////
 187 // Utility types and common code for the above passes.
 188
 189 impl<'a,'tcx> CrateCtxt<'a,'tcx> {
 190     fn icx(&'a self, param_bounds: &'a GetTypeParameterBounds<'tcx>) -> ItemCtxt<'a,'tcx> {
 191         ItemCtxt { ccx: self, param_bounds: param_bounds }
 192     }
 193
 194     fn method_ty(&self, method_id: ast::NodeId) -> Rc<ty::Method<'tcx>> {
 195         let def_id = local_def(method_id);
 196         match *self.tcx.impl_or_trait_items.borrow().get(&def_id).unwrap() {
 197             ty::MethodTraitItem(ref mty) => mty.clone(),
 198             _ => {
 199                 self.tcx.sess.bug(&format!("method with id {} has the wrong type", method_id));
 200             }
 201         }
 202     }
 203
 204     fn cycle_check<F,R>(&self,
 205                         span: Span,
 206                         request: AstConvRequest,
 207                         code: F)
 208                         -> Result<R,ErrorReported>
 209         where F: FnOnce() -> Result<R,ErrorReported>
 210     {
 211         {
 212             let mut stack = self.stack.borrow_mut();
 213             match stack.iter().enumerate().rev().find(|&(_, r)| *r == request) {
 214                 None => { }
 215                 Some((i, _)) => {
 216                     let cycle = &stack[i..];
 217                     self.report_cycle(span, cycle);
 218                     return Err(ErrorReported);
 219                 }
 220             }
 221             stack.push(request);
 222         }
 223
 224         let result = code();
 225
 226         self.stack.borrow_mut().pop();
 227         result
 228     }
 229
 230     fn report_cycle(&self,
 231                     span: Span,
 232                     cycle: &[AstConvRequest])
 233     {
 234         assert!(!cycle.is_empty());
 235         let tcx = self.tcx;
 236
 237         span_err!(tcx.sess, span, E0391,
 238             "unsupported cyclic reference between types/traits detected");
 239
 240         match cycle[0] {
 241             AstConvRequest::GetItemTypeScheme(def_id) |
 242             AstConvRequest::GetTraitDef(def_id) => {
 243                 tcx.sess.note(
 244                     &format!("the cycle begins when processing `{}`...",
 245                              tcx.item_path_str(def_id)));
 246             }
 247             AstConvRequest::EnsureSuperPredicates(def_id) => {
 248                 tcx.sess.note(
 249                     &format!("the cycle begins when computing the supertraits of `{}`...",
 250                              tcx.item_path_str(def_id)));
 251             }
 252             AstConvRequest::GetTypeParameterBounds(id) => {
 253                 let def = tcx.type_parameter_def(id);
 254                 tcx.sess.note(
 255                     &format!("the cycle begins when computing the bounds \
 256                               for type parameter `{}`...",
 257                              def.name));
 258             }
 259         }
 260
 261         for request in &cycle[1..] {
 262             match *request {
 263                 AstConvRequest::GetItemTypeScheme(def_id) |
 264                 AstConvRequest::GetTraitDef(def_id) => {
 265                     tcx.sess.note(
 266                         &format!("...which then requires processing `{}`...",
 267                                  tcx.item_path_str(def_id)));
 268                 }
 269                 AstConvRequest::EnsureSuperPredicates(def_id) => {
 270                     tcx.sess.note(
 271                         &format!("...which then requires computing the supertraits of `{}`...",
 272                                  tcx.item_path_str(def_id)));
 273                 }
 274                 AstConvRequest::GetTypeParameterBounds(id) => {
 275                     let def = tcx.type_parameter_def(id);
 276                     tcx.sess.note(
 277                         &format!("...which then requires computing the bounds \
 278                                   for type parameter `{}`...",
 279                                  def.name));
 280                 }
 281             }
 282         }
 283
 284         match cycle[0] {
 285             AstConvRequest::GetItemTypeScheme(def_id) |
 286             AstConvRequest::GetTraitDef(def_id) => {
 287                 tcx.sess.note(
 288                     &format!("...which then again requires processing `{}`, completing the cycle.",
 289                              tcx.item_path_str(def_id)));
 290             }
 291             AstConvRequest::EnsureSuperPredicates(def_id) => {
 292                 tcx.sess.note(
 293                     &format!("...which then again requires computing the supertraits of `{}`, \
 294                               completing the cycle.",
 295                              tcx.item_path_str(def_id)));
 296             }
 297             AstConvRequest::GetTypeParameterBounds(id) => {
 298                 let def = tcx.type_parameter_def(id);
 299                 tcx.sess.note(
 300                     &format!("...which then again requires computing the bounds \
 301                               for type parameter `{}`, completing the cycle.",
 302                              def.name));
 303             }
 304         }
 305     }
 306
 307     /// Loads the trait def for a given trait, returning ErrorReported if a cycle arises.
 308     fn get_trait_def(&self, trait_id: ast::DefId)
 309                      -> &'tcx ty::TraitDef<'tcx>
 310     {
 311         let tcx = self.tcx;
 312
 313         if trait_id.krate != ast::LOCAL_CRATE {
 314             return tcx.lookup_trait_def(trait_id)
 315         }
 316
 317         let item = match tcx.map.get(trait_id.node) {
 318             ast_map::NodeItem(item) => item,
 319             _ => tcx.sess.bug(&format!("get_trait_def({:?}): not an item", trait_id))
 320         };
 321
 322         trait_def_of_item(self, &*item)
 323     }
 324
 325     /// Ensure that the (transitive) super predicates for
 326     /// `trait_def_id` are available. This will report a cycle error
 327     /// if a trait `X` (transitively) extends itself in some form.
 328     fn ensure_super_predicates(&self, span: Span, trait_def_id: ast::DefId)
 329                                -> Result<(), ErrorReported>
 330     {
 331         self.cycle_check(span, AstConvRequest::EnsureSuperPredicates(trait_def_id), || {
 332             let def_ids = ensure_super_predicates_step(self, trait_def_id);
 333
 334             for def_id in def_ids {
 335                 try!(self.ensure_super_predicates(span, def_id));
 336             }
 337
 338             Ok(())
 339         })
 340     }
 341 }
 342
 343 impl<'a,'tcx> ItemCtxt<'a,'tcx> {
 344     fn to_ty<RS:RegionScope>(&self, rs: &RS, ast_ty: &ast::Ty) -> Ty<'tcx> {
 345         ast_ty_to_ty(self, rs, ast_ty)
 346     }
 347 }
 348
 349 impl<'a, 'tcx> AstConv<'tcx> for ItemCtxt<'a, 'tcx> {
 350     fn tcx(&self) -> &ty::ctxt<'tcx> { self.ccx.tcx }
 351
 352     fn get_item_type_scheme(&self, span: Span, id: ast::DefId)
 353                             -> Result<ty::TypeScheme<'tcx>, ErrorReported>
 354     {
 355         self.ccx.cycle_check(span, AstConvRequest::GetItemTypeScheme(id), || {
 356             Ok(type_scheme_of_def_id(self.ccx, id))
 357         })
 358     }
 359
 360     fn get_trait_def(&self, span: Span, id: ast::DefId)
 361                      -> Result<&'tcx ty::TraitDef<'tcx>, ErrorReported>
 362     {
 363         self.ccx.cycle_check(span, AstConvRequest::GetTraitDef(id), || {
 364             Ok(self.ccx.get_trait_def(id))
 365         })
 366     }
 367
 368     fn ensure_super_predicates(&self,
 369                                span: Span,
 370                                trait_def_id: ast::DefId)
 371                                -> Result<(), ErrorReported>
 372     {
 373         debug!("ensure_super_predicates(trait_def_id={:?})",
 374                trait_def_id);
 375
 376         self.ccx.ensure_super_predicates(span, trait_def_id)
 377     }
 378
 379
 380     fn get_type_parameter_bounds(&self,
 381                                  span: Span,
 382                                  node_id: ast::NodeId)
 383                                  -> Result<Vec<ty::PolyTraitRef<'tcx>>, ErrorReported>
 384     {
 385         self.ccx.cycle_check(span, AstConvRequest::GetTypeParameterBounds(node_id), || {
 386             let v = self.param_bounds.get_type_parameter_bounds(self, span, node_id)
 387                                      .into_iter()
 388                                      .filter_map(|p| p.to_opt_poly_trait_ref())
 389                                      .collect();
 390             Ok(v)
 391         })
 392     }
 393
 394     fn trait_defines_associated_type_named(&self,
 395                                            trait_def_id: ast::DefId,
 396                                            assoc_name: ast::Name)
 397                                            -> bool
 398     {
 399         if trait_def_id.krate == ast::LOCAL_CRATE {
 400             trait_defines_associated_type_named(self.ccx, trait_def_id.node, assoc_name)
 401         } else {
 402             let trait_def = self.tcx().lookup_trait_def(trait_def_id);
 403             trait_def.associated_type_names.contains(&assoc_name)
 404         }
 405     }
 406
 407     fn ty_infer(&self, span: Span) -> Ty<'tcx> {
 408         span_err!(self.tcx().sess, span, E0121,
 409                   "the type placeholder `_` is not allowed within types on item signatures");
 410         self.tcx().types.err
 411     }
 412
 413     fn projected_ty(&self,
 414                     _span: Span,
 415                     trait_ref: ty::TraitRef<'tcx>,
 416                     item_name: ast::Name)
 417                     -> Ty<'tcx>
 418     {
 419         self.tcx().mk_projection(trait_ref, item_name)
 420     }
 421 }
 422
 423 /// Interface used to find the bounds on a type parameter from within
 424 /// an `ItemCtxt`. This allows us to use multiple kinds of sources.
 425 trait GetTypeParameterBounds<'tcx> {
 426     fn get_type_parameter_bounds(&self,
 427                                  astconv: &AstConv<'tcx>,
 428                                  span: Span,
 429                                  node_id: ast::NodeId)
 430                                  -> Vec<ty::Predicate<'tcx>>;
 431 }
 432
 433 /// Find bounds from both elements of the tuple.
 434 impl<'a,'b,'tcx,A,B> GetTypeParameterBounds<'tcx> for (&'a A,&'b B)
 435     where A : GetTypeParameterBounds<'tcx>, B : GetTypeParameterBounds<'tcx>
 436 {
 437     fn get_type_parameter_bounds(&self,
 438                                  astconv: &AstConv<'tcx>,
 439                                  span: Span,
 440                                  node_id: ast::NodeId)
 441                                  -> Vec<ty::Predicate<'tcx>>
 442     {
 443         let mut v = self.0.get_type_parameter_bounds(astconv, span, node_id);
 444         v.extend(self.1.get_type_parameter_bounds(astconv, span, node_id));
 445         v
 446     }
 447 }
 448
 449 /// Empty set of bounds.
 450 impl<'tcx> GetTypeParameterBounds<'tcx> for () {
 451     fn get_type_parameter_bounds(&self,
 452                                  _astconv: &AstConv<'tcx>,
 453                                  _span: Span,
 454                                  _node_id: ast::NodeId)
 455                                  -> Vec<ty::Predicate<'tcx>>
 456     {
 457         Vec::new()
 458     }
 459 }
 460
 461 /// Find bounds from the parsed and converted predicates.  This is
 462 /// used when converting methods, because by that time the predicates
 463 /// from the trait/impl have been fully converted.
 464 impl<'tcx> GetTypeParameterBounds<'tcx> for ty::GenericPredicates<'tcx> {
 465     fn get_type_parameter_bounds(&self,
 466                                  astconv: &AstConv<'tcx>,
 467                                  _span: Span,
 468                                  node_id: ast::NodeId)
 469                                  -> Vec<ty::Predicate<'tcx>>
 470     {
 471         let def = astconv.tcx().type_parameter_def(node_id);
 472
 473         self.predicates
 474             .iter()
 475             .filter(|predicate| {
 476                 match **predicate {
 477                     ty::Predicate::Trait(ref data) => {
 478                         data.skip_binder().self_ty().is_param(def.space, def.index)
 479                     }
 480                     ty::Predicate::TypeOutlives(ref data) => {
 481                         data.skip_binder().0.is_param(def.space, def.index)
 482                     }
 483                     ty::Predicate::Equate(..) |
 484                     ty::Predicate::RegionOutlives(..) |
 485                     ty::Predicate::Projection(..) => {
 486                         false
 487                     }
 488                 }
 489             })
 490             .cloned()
 491             .collect()
 492     }
 493 }
 494
 495 /// Find bounds from ast::Generics. This requires scanning through the
 496 /// AST. We do this to avoid having to convert *all* the bounds, which
 497 /// would create artificial cycles. Instead we can only convert the
 498 /// bounds for those a type parameter `X` if `X::Foo` is used.
 499 impl<'tcx> GetTypeParameterBounds<'tcx> for ast::Generics {
 500     fn get_type_parameter_bounds(&self,
 501                                  astconv: &AstConv<'tcx>,
 502                                  _: Span,
 503                                  node_id: ast::NodeId)
 504                                  -> Vec<ty::Predicate<'tcx>>
 505     {
 506         // In the AST, bounds can derive from two places. Either
 507         // written inline like `<T:Foo>` or in a where clause like
 508         // `where T:Foo`.
 509
 510         let def = astconv.tcx().type_parameter_def(node_id);
 511         let ty = astconv.tcx().mk_param_from_def(&def);
 512
 513         let from_ty_params =
 514             self.ty_params
 515                 .iter()
 516                 .filter(|p| p.id == node_id)
 517                 .flat_map(|p| p.bounds.iter())
 518                 .flat_map(|b| predicates_from_bound(astconv, ty, b));
 519
 520         let from_where_clauses =
 521             self.where_clause
 522                 .predicates
 523                 .iter()
 524                 .filter_map(|wp| match *wp {
 525                     ast::WherePredicate::BoundPredicate(ref bp) => Some(bp),
 526                     _ => None
 527                 })
 528                 .filter(|bp| is_param(astconv.tcx(), &bp.bounded_ty, node_id))
 529                 .flat_map(|bp| bp.bounds.iter())
 530                 .flat_map(|b| predicates_from_bound(astconv, ty, b));
 531
 532         from_ty_params.chain(from_where_clauses).collect()
 533     }
 534 }
 535
 536 /// Tests whether this is the AST for a reference to the type
 537 /// parameter with id `param_id`. We use this so as to avoid running
 538 /// `ast_ty_to_ty`, because we want to avoid triggering an all-out
 539 /// conversion of the type to avoid inducing unnecessary cycles.
 540 fn is_param<'tcx>(tcx: &ty::ctxt<'tcx>,
 541                   ast_ty: &ast::Ty,
 542                   param_id: ast::NodeId)
 543                   -> bool
 544 {
 545     if let ast::TyPath(None, _) = ast_ty.node {
 546         let path_res = *tcx.def_map.borrow().get(&ast_ty.id).unwrap();
 547         match path_res.base_def {
 548             def::DefSelfTy(Some(def_id), None) => {
 549                 path_res.depth == 0 && def_id.node == param_id
 550             }
 551             def::DefTyParam(_, _, def_id, _) => {
 552                 path_res.depth == 0 && def_id == local_def(param_id)
 553             }
 554             _ => {
 555                 false
 556             }
 557         }
 558     } else {
 559         false
 560     }
 561 }
 562
 563 fn get_enum_variant_types<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 564                                     enum_scheme: ty::TypeScheme<'tcx>,
 565                                     enum_predicates: ty::GenericPredicates<'tcx>,
 566                                     variants: &[P<ast::Variant>]) {
 567     let tcx = ccx.tcx;
 568     let icx = ccx.icx(&enum_predicates);
 569
 570     // Create a set of parameter types shared among all the variants.
 571     for variant in variants {
 572         let variant_def_id = local_def(variant.node.id);
 573
 574         // Nullary enum constructors get turned into constants; n-ary enum
 575         // constructors get turned into functions.
 576         let result_ty = match variant.node.kind {
 577             ast::TupleVariantKind(ref args) if !args.is_empty() => {
 578                 let rs = ExplicitRscope;
 579                 let input_tys: Vec<_> = args.iter().map(|va| icx.to_ty(&rs, &*va.ty)).collect();
 580                 tcx.mk_ctor_fn(variant_def_id, &input_tys, enum_scheme.ty)
 581             }
 582
 583             ast::TupleVariantKind(_) => {
 584                 enum_scheme.ty
 585             }
 586
 587             ast::StructVariantKind(ref struct_def) => {
 588                 convert_struct(ccx, &**struct_def, enum_scheme.clone(),
 589                                enum_predicates.clone(), variant.node.id);
 590                 enum_scheme.ty
 591             }
 592         };
 593
 594         let variant_scheme = TypeScheme {
 595             generics: enum_scheme.generics.clone(),
 596             ty: result_ty
 597         };
 598
 599         tcx.register_item_type(variant_def_id, variant_scheme.clone());
 600         tcx.predicates.borrow_mut().insert(variant_def_id, enum_predicates.clone());
 601         write_ty_to_tcx(tcx, variant.node.id, result_ty);
 602     }
 603 }
 604
 605 fn convert_method<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 606                             container: ImplOrTraitItemContainer,
 607                             sig: &ast::MethodSig,
 608                             id: ast::NodeId,
 609                             ident: ast::Ident,
 610                             vis: ast::Visibility,
 611                             untransformed_rcvr_ty: Ty<'tcx>,
 612                             rcvr_ty_generics: &ty::Generics<'tcx>,
 613                             rcvr_ty_predicates: &ty::GenericPredicates<'tcx>) {
 614     let ty_generics = ty_generics_for_fn(ccx, &sig.generics, rcvr_ty_generics);
 615
 616     let ty_generic_predicates =
 617         ty_generic_predicates_for_fn(ccx, &sig.generics, rcvr_ty_predicates);
 618
 619     let (fty, explicit_self_category) =
 620         astconv::ty_of_method(&ccx.icx(&(rcvr_ty_predicates, &sig.generics)),
 621                               sig, untransformed_rcvr_ty);
 622
 623     let def_id = local_def(id);
 624     let ty_method = ty::Method::new(ident.name,
 625                                     ty_generics,
 626                                     ty_generic_predicates,
 627                                     fty,
 628                                     explicit_self_category,
 629                                     vis,
 630                                     def_id,
 631                                     container,
 632                                     None);
 633
 634     let fty = ccx.tcx.mk_fn(Some(def_id),
 635                             ccx.tcx.mk_bare_fn(ty_method.fty.clone()));
 636     debug!("method {} (id {}) has type {:?}",
 637             ident, id, fty);
 638     ccx.tcx.register_item_type(def_id, TypeScheme {
 639         generics: ty_method.generics.clone(),
 640         ty: fty
 641     });
 642     ccx.tcx.predicates.borrow_mut().insert(def_id, ty_method.predicates.clone());
 643
 644     write_ty_to_tcx(ccx.tcx, id, fty);
 645
 646     debug!("writing method type: def_id={:?} mty={:?}",
 647             def_id, ty_method);
 648
 649     ccx.tcx.impl_or_trait_items.borrow_mut().insert(def_id,
 650         ty::MethodTraitItem(Rc::new(ty_method)));
 651 }
 652
 653 fn convert_field<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 654                            struct_generics: &ty::Generics<'tcx>,
 655                            struct_predicates: &ty::GenericPredicates<'tcx>,
 656                            v: &ast::StructField,
 657                            origin: ast::DefId)
 658                            -> ty::FieldTy
 659 {
 660     let tt = ccx.icx(struct_predicates).to_ty(&ExplicitRscope, &*v.node.ty);
 661     write_ty_to_tcx(ccx.tcx, v.node.id, tt);
 662
 663     /* add the field to the tcache */
 664     ccx.tcx.register_item_type(local_def(v.node.id),
 665                                ty::TypeScheme {
 666                                    generics: struct_generics.clone(),
 667                                    ty: tt
 668                                });
 669     ccx.tcx.predicates.borrow_mut().insert(local_def(v.node.id),
 670                                            struct_predicates.clone());
 671
 672     match v.node.kind {
 673         ast::NamedField(ident, visibility) => {
 674             ty::FieldTy {
 675                 name: ident.name,
 676                 id: local_def(v.node.id),
 677                 vis: visibility,
 678                 origin: origin,
 679             }
 680         }
 681         ast::UnnamedField(visibility) => {
 682             ty::FieldTy {
 683                 name: special_idents::unnamed_field.name,
 684                 id: local_def(v.node.id),
 685                 vis: visibility,
 686                 origin: origin,
 687             }
 688         }
 689     }
 690 }
 691
 692 fn convert_associated_const<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 693                                       container: ImplOrTraitItemContainer,
 694                                       ident: ast::Ident,
 695                                       id: ast::NodeId,
 696                                       vis: ast::Visibility,
 697                                       ty: ty::Ty<'tcx>,
 698                                       default: Option<&ast::Expr>)
 699 {
 700     ccx.tcx.predicates.borrow_mut().insert(local_def(id),
 701                                            ty::GenericPredicates::empty());
 702
 703     write_ty_to_tcx(ccx.tcx, id, ty);
 704     let default_id = default.map(|expr| local_def(expr.id));
 705
 706     let associated_const = Rc::new(ty::AssociatedConst {
 707         name: ident.name,
 708         vis: vis,
 709         def_id: local_def(id),
 710         container: container,
 711         ty: ty,
 712         default: default_id,
 713     });
 714     ccx.tcx.impl_or_trait_items.borrow_mut()
 715        .insert(local_def(id), ty::ConstTraitItem(associated_const));
 716 }
 717
 718 fn convert_associated_type<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 719                                      container: ImplOrTraitItemContainer,
 720                                      ident: ast::Ident,
 721                                      id: ast::NodeId,
 722                                      vis: ast::Visibility,
 723                                      ty: Option<Ty<'tcx>>)
 724 {
 725     let associated_type = Rc::new(ty::AssociatedType {
 726         name: ident.name,
 727         vis: vis,
 728         ty: ty,
 729         def_id: local_def(id),
 730         container: container
 731     });
 732     ccx.tcx.impl_or_trait_items.borrow_mut()
 733        .insert(local_def(id), ty::TypeTraitItem(associated_type));
 734 }
 735
 736 fn convert_methods<'a,'tcx,'i,I>(ccx: &CrateCtxt<'a, 'tcx>,
 737                                  container: ImplOrTraitItemContainer,
 738                                  methods: I,
 739                                  untransformed_rcvr_ty: Ty<'tcx>,
 740                                  rcvr_ty_generics: &ty::Generics<'tcx>,
 741                                  rcvr_ty_predicates: &ty::GenericPredicates<'tcx>)
 742     where I: Iterator<Item=(&'i ast::MethodSig, ast::NodeId, ast::Ident, ast::Visibility, Span)>
 743 {
 744     debug!("convert_methods(untransformed_rcvr_ty={:?}, rcvr_ty_generics={:?}, \
 745                             rcvr_ty_predicates={:?})",
 746            untransformed_rcvr_ty,
 747            rcvr_ty_generics,
 748            rcvr_ty_predicates);
 749
 750     let tcx = ccx.tcx;
 751     let mut seen_methods = FnvHashSet();
 752     for (sig, id, ident, vis, span) in methods {
 753         if !seen_methods.insert(ident.name) {
 754             let fn_desc = match sig.explicit_self.node {
 755                 ast::SelfStatic => "associated function",
 756                 _               => "method",
 757             };
 758             span_err!(tcx.sess, span, E0201, "duplicate {}", fn_desc);
 759         }
 760
 761         convert_method(ccx,
 762                        container,
 763                        sig,
 764                        id,
 765                        ident,
 766                        vis,
 767                        untransformed_rcvr_ty,
 768                        rcvr_ty_generics,
 769                        rcvr_ty_predicates);
 770     }
 771 }
 772
 773 fn ensure_no_ty_param_bounds(ccx: &CrateCtxt,
 774                                  span: Span,
 775                                  generics: &ast::Generics,
 776                                  thing: &'static str) {
 777     let mut warn = false;
 778
 779     for ty_param in generics.ty_params.iter() {
 780         for bound in ty_param.bounds.iter() {
 781             match *bound {
 782                 ast::TraitTyParamBound(..) => {
 783                     warn = true;
 784                 }
 785                 ast::RegionTyParamBound(..) => { }
 786             }
 787         }
 788     }
 789
 790     if warn {
 791         // According to accepted RFC #XXX, we should
 792         // eventually accept these, but it will not be
 793         // part of this PR. Still, convert to warning to
 794         // make bootstrapping easier.
 795         span_warn!(ccx.tcx.sess, span, E0122,
 796                    "trait bounds are not (yet) enforced \
 797                    in {} definitions",
 798                    thing);
 799     }
 800 }
 801
 802 fn convert_item(ccx: &CrateCtxt, it: &ast::Item) {
 803     let tcx = ccx.tcx;
 804     debug!("convert: item {} with id {}", token::get_ident(it.ident), it.id);
 805     match it.node {
 806         // These don't define types.
 807         ast::ItemExternCrate(_) | ast::ItemUse(_) |
 808         ast::ItemForeignMod(_) | ast::ItemMod(_) | ast::ItemMac(_) => {
 809         }
 810         ast::ItemEnum(ref enum_definition, _) => {
 811             let (scheme, predicates) = convert_typed_item(ccx, it);
 812             write_ty_to_tcx(tcx, it.id, scheme.ty);
 813             get_enum_variant_types(ccx,
 814                                    scheme,
 815                                    predicates,
 816                                    &enum_definition.variants);
 817         },
 818         ast::ItemDefaultImpl(_, ref ast_trait_ref) => {
 819             let trait_ref =
 820                 astconv::instantiate_mono_trait_ref(&ccx.icx(&()),
 821                                                     &ExplicitRscope,
 822                                                     ast_trait_ref,
 823                                                     None);
 824
 825             tcx.record_trait_has_default_impl(trait_ref.def_id);
 826
 827             tcx.impl_trait_refs.borrow_mut().insert(local_def(it.id), Some(trait_ref));
 828         }
 829         ast::ItemImpl(_, _,
 830                       ref generics,
 831                       ref opt_trait_ref,
 832                       ref selfty,
 833                       ref impl_items) => {
 834             // Create generics from the generics specified in the impl head.
 835             debug!("convert: ast_generics={:?}", generics);
 836             let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
 837             let ty_predicates = ty_generic_predicates_for_type_or_impl(ccx, generics);
 838
 839             debug!("convert: impl_bounds={:?}", ty_predicates);
 840
 841             let selfty = ccx.icx(&ty_predicates).to_ty(&ExplicitRscope, &**selfty);
 842             write_ty_to_tcx(tcx, it.id, selfty);
 843
 844             tcx.register_item_type(local_def(it.id),
 845                                    TypeScheme { generics: ty_generics.clone(),
 846                                                 ty: selfty });
 847             tcx.predicates.borrow_mut().insert(local_def(it.id),
 848                                                ty_predicates.clone());
 849
 850             // If there is a trait reference, treat the methods as always public.
 851             // This is to work around some incorrect behavior in privacy checking:
 852             // when the method belongs to a trait, it should acquire the privacy
 853             // from the trait, not the impl. Forcing the visibility to be public
 854             // makes things sorta work.
 855             let parent_visibility = if opt_trait_ref.is_some() {
 856                 ast::Public
 857             } else {
 858                 it.vis
 859             };
 860
 861             // Convert all the associated consts.
 862             for impl_item in impl_items {
 863                 if let ast::ConstImplItem(ref ty, ref expr) = impl_item.node {
 864                     let ty = ccx.icx(&ty_predicates)
 865                                 .to_ty(&ExplicitRscope, &*ty);
 866                     tcx.register_item_type(local_def(impl_item.id),
 867                                            TypeScheme {
 868                                                generics: ty_generics.clone(),
 869                                                ty: ty,
 870                                            });
 871                     convert_associated_const(ccx, ImplContainer(local_def(it.id)),
 872                                              impl_item.ident, impl_item.id,
 873                                              impl_item.vis.inherit_from(parent_visibility),
 874                                              ty, Some(&*expr));
 875                 }
 876             }
 877
 878             // Convert all the associated types.
 879             for impl_item in impl_items {
 880                 if let ast::TypeImplItem(ref ty) = impl_item.node {
 881                     if opt_trait_ref.is_none() {
 882                         span_err!(tcx.sess, impl_item.span, E0202,
 883                                   "associated types are not allowed in inherent impls");
 884                     }
 885
 886                     let typ = ccx.icx(&ty_predicates).to_ty(&ExplicitRscope, ty);
 887
 888                     convert_associated_type(ccx, ImplContainer(local_def(it.id)),
 889                                             impl_item.ident, impl_item.id, impl_item.vis,
 890                                             Some(typ));
 891                 }
 892             }
 893
 894             let methods = impl_items.iter().filter_map(|ii| {
 895                 if let ast::MethodImplItem(ref sig, _) = ii.node {
 896                     // if the method specifies a visibility, use that, otherwise
 897                     // inherit the visibility from the impl (so `foo` in `pub impl
 898                     // { fn foo(); }` is public, but private in `impl { fn
 899                     // foo(); }`).
 900                     let method_vis = ii.vis.inherit_from(parent_visibility);
 901                     Some((sig, ii.id, ii.ident, method_vis, ii.span))
 902                 } else {
 903                     None
 904                 }
 905             });
 906             convert_methods(ccx,
 907                             ImplContainer(local_def(it.id)),
 908                             methods,
 909                             selfty,
 910                             &ty_generics,
 911                             &ty_predicates);
 912
 913             for impl_item in impl_items {
 914                 if let ast::MethodImplItem(ref sig, ref body) = impl_item.node {
 915                     let body_id = body.id;
 916                     check_method_self_type(ccx,
 917                                            &BindingRscope::new(),
 918                                            ccx.method_ty(impl_item.id),
 919                                            selfty,
 920                                            &sig.explicit_self,
 921                                            body_id);
 922                 }
 923             }
 924
 925             if let &Some(ref ast_trait_ref) = opt_trait_ref {
 926                 tcx.impl_trait_refs.borrow_mut().insert(
 927                     local_def(it.id),
 928                     Some(astconv::instantiate_mono_trait_ref(&ccx.icx(&ty_predicates),
 929                                                              &ExplicitRscope,
 930                                                              ast_trait_ref,
 931                                                              Some(selfty)))
 932                         );
 933             } else {
 934                 tcx.impl_trait_refs.borrow_mut().insert(local_def(it.id), None);
 935             }
 936
 937             enforce_impl_params_are_constrained(tcx,
 938                                                 generics,
 939                                                 local_def(it.id),
 940                                                 impl_items);
 941         },
 942         ast::ItemTrait(_, _, _, ref trait_items) => {
 943             let trait_def = trait_def_of_item(ccx, it);
 944             let _: Result<(), ErrorReported> = // any error is already reported, can ignore
 945                 ccx.ensure_super_predicates(it.span, local_def(it.id));
 946             convert_trait_predicates(ccx, it);
 947             let trait_predicates = tcx.lookup_predicates(local_def(it.id));
 948
 949             debug!("convert: trait_bounds={:?}", trait_predicates);
 950
 951             // Convert all the associated types.
 952             for trait_item in trait_items {
 953                 match trait_item.node {
 954                     ast::ConstTraitItem(ref ty, ref default) => {
 955                         let ty = ccx.icx(&trait_predicates)
 956                                     .to_ty(&ExplicitRscope, ty);
 957                         tcx.register_item_type(local_def(trait_item.id),
 958                                                TypeScheme {
 959                                                    generics: trait_def.generics.clone(),
 960                                                    ty: ty,
 961                                                });
 962                         convert_associated_const(ccx, TraitContainer(local_def(it.id)),
 963                                                  trait_item.ident, trait_item.id,
 964                                                  ast::Public, ty, default.as_ref().map(|d| &**d));
 965                     }
 966                     _ => {}
 967                 }
 968             };
 969
 970             // Convert all the associated types.
 971             for trait_item in trait_items {
 972                 match trait_item.node {
 973                     ast::TypeTraitItem(_, ref opt_ty) => {
 974                         let typ = opt_ty.as_ref().map({
 975                             |ty| ccx.icx(&trait_predicates).to_ty(&ExplicitRscope, &ty)
 976                         });
 977
 978                         convert_associated_type(ccx, TraitContainer(local_def(it.id)),
 979                                                 trait_item.ident, trait_item.id, ast::Public,
 980                                                 typ);
 981                     }
 982                     _ => {}
 983                 }
 984             };
 985
 986             let methods = trait_items.iter().filter_map(|ti| {
 987                 let sig = match ti.node {
 988                     ast::MethodTraitItem(ref sig, _) => sig,
 989                     _ => return None,
 990                 };
 991                 Some((sig, ti.id, ti.ident, ast::Inherited, ti.span))
 992             });
 993
 994             // Run convert_methods on the trait methods.
 995             convert_methods(ccx,
 996                             TraitContainer(local_def(it.id)),
 997                             methods,
 998                             tcx.mk_self_type(),
 999                             &trait_def.generics,
1000                             &trait_predicates);
1001
1002             // Add an entry mapping
1003             let trait_item_def_ids = Rc::new(trait_items.iter().map(|trait_item| {
1004                 let def_id = local_def(trait_item.id);
1005                 match trait_item.node {
1006                     ast::ConstTraitItem(..) => {
1007                         ty::ConstTraitItemId(def_id)
1008                     }
1009                     ast::MethodTraitItem(..) => {
1010                         ty::MethodTraitItemId(def_id)
1011                     }
1012                     ast::TypeTraitItem(..) => {
1013                         ty::TypeTraitItemId(def_id)
1014                     }
1015                 }
1016             }).collect());
1017             tcx.trait_item_def_ids.borrow_mut().insert(local_def(it.id), trait_item_def_ids);
1018
1019             // This must be done after `collect_trait_methods` so that
1020             // we have a method type stored for every method.
1021             for trait_item in trait_items {
1022                 let sig = match trait_item.node {
1023                     ast::MethodTraitItem(ref sig, _) => sig,
1024                     _ => continue
1025                 };
1026                 check_method_self_type(ccx,
1027                                        &BindingRscope::new(),
1028                                        ccx.method_ty(trait_item.id),
1029                                        tcx.mk_self_type(),
1030                                        &sig.explicit_self,
1031                                        it.id)
1032             }
1033         },
1034         ast::ItemStruct(ref struct_def, _) => {
1035             // Write the class type.
1036             let (scheme, predicates) = convert_typed_item(ccx, it);
1037             write_ty_to_tcx(tcx, it.id, scheme.ty);
1038             convert_struct(ccx, &**struct_def, scheme, predicates, it.id);
1039         },
1040         ast::ItemTy(_, ref generics) => {
1041             ensure_no_ty_param_bounds(ccx, it.span, generics, "type");
1042             let (scheme, _) = convert_typed_item(ccx, it);
1043             write_ty_to_tcx(tcx, it.id, scheme.ty);
1044         },
1045         _ => {
1046             // This call populates the type cache with the converted type
1047             // of the item in passing. All we have to do here is to write
1048             // it into the node type table.
1049             let (scheme, _) = convert_typed_item(ccx, it);
1050             write_ty_to_tcx(tcx, it.id, scheme.ty);
1051         },
1052     }
1053 }
1054
1055 fn convert_struct<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1056                             struct_def: &ast::StructDef,
1057                             scheme: ty::TypeScheme<'tcx>,
1058                             predicates: ty::GenericPredicates<'tcx>,
1059                             id: ast::NodeId) {
1060     let tcx = ccx.tcx;
1061
1062     // Write the type of each of the members and check for duplicate fields.
1063     let mut seen_fields: FnvHashMap<ast::Name, Span> = FnvHashMap();
1064     let field_tys = struct_def.fields.iter().map(|f| {
1065         let result = convert_field(ccx, &scheme.generics, &predicates, f, local_def(id));
1066
1067         if result.name != special_idents::unnamed_field.name {
1068             let dup = match seen_fields.get(&result.name) {
1069                 Some(prev_span) => {
1070                     span_err!(tcx.sess, f.span, E0124,
1071                               "field `{}` is already declared",
1072                               token::get_name(result.name));
1073                     span_note!(tcx.sess, *prev_span, "previously declared here");
1074                     true
1075                 },
1076                 None => false,
1077             };
1078             // FIXME(#6393) this whole dup thing is just to satisfy
1079             // the borrow checker :-(
1080             if !dup {
1081                 seen_fields.insert(result.name, f.span);
1082             }
1083         }
1084
1085         result
1086     }).collect();
1087
1088     tcx.struct_fields.borrow_mut().insert(local_def(id), Rc::new(field_tys));
1089
1090     let substs = mk_item_substs(ccx, &scheme.generics);
1091     let selfty = tcx.mk_struct(local_def(id), tcx.mk_substs(substs));
1092
1093     // If this struct is enum-like or tuple-like, create the type of its
1094     // constructor.
1095     match struct_def.ctor_id {
1096         None => {}
1097         Some(ctor_id) => {
1098             if struct_def.fields.is_empty() {
1099                 // Enum-like.
1100                 write_ty_to_tcx(tcx, ctor_id, selfty);
1101
1102                 tcx.register_item_type(local_def(ctor_id), scheme);
1103                 tcx.predicates.borrow_mut().insert(local_def(ctor_id), predicates);
1104             } else if struct_def.fields[0].node.kind.is_unnamed() {
1105                 // Tuple-like.
1106                 let inputs: Vec<_> =
1107                     struct_def.fields
1108                               .iter()
1109                               .map(|field| tcx.lookup_item_type(
1110                                   local_def(field.node.id)).ty)
1111                               .collect();
1112                 let ctor_fn_ty = tcx.mk_ctor_fn(local_def(ctor_id),
1113                                                 &inputs[..],
1114                                                 selfty);
1115                 write_ty_to_tcx(tcx, ctor_id, ctor_fn_ty);
1116                 tcx.register_item_type(local_def(ctor_id),
1117                                        TypeScheme {
1118                                            generics: scheme.generics,
1119                                            ty: ctor_fn_ty
1120                                        });
1121                 tcx.predicates.borrow_mut().insert(local_def(ctor_id), predicates);
1122             }
1123         }
1124     }
1125 }
1126
1127 /// Ensures that the super-predicates of the trait with def-id
1128 /// trait_def_id are converted and stored. This does NOT ensure that
1129 /// the transitive super-predicates are converted; that is the job of
1130 /// the `ensure_super_predicates()` method in the `AstConv` impl
1131 /// above. Returns a list of trait def-ids that must be ensured as
1132 /// well to guarantee that the transitive superpredicates are
1133 /// converted.
1134 fn ensure_super_predicates_step(ccx: &CrateCtxt,
1135                                 trait_def_id: ast::DefId)
1136                                 -> Vec<ast::DefId>
1137 {
1138     let tcx = ccx.tcx;
1139
1140     debug!("ensure_super_predicates_step(trait_def_id={:?})", trait_def_id);
1141
1142     if trait_def_id.krate != ast::LOCAL_CRATE {
1143         // If this trait comes from an external crate, then all of the
1144         // supertraits it may depend on also must come from external
1145         // crates, and hence all of them already have their
1146         // super-predicates "converted" (and available from crate
1147         // meta-data), so there is no need to transitively test them.
1148         return Vec::new();
1149     }
1150
1151     let superpredicates = tcx.super_predicates.borrow().get(&trait_def_id).cloned();
1152     let superpredicates = superpredicates.unwrap_or_else(|| {
1153         let trait_node_id = trait_def_id.node;
1154
1155         let item = match ccx.tcx.map.get(trait_node_id) {
1156             ast_map::NodeItem(item) => item,
1157             _ => ccx.tcx.sess.bug(&format!("trait_node_id {} is not an item", trait_node_id))
1158         };
1159
1160         let (generics, bounds) = match item.node {
1161             ast::ItemTrait(_, ref generics, ref supertraits, _) => (generics, supertraits),
1162             _ => tcx.sess.span_bug(item.span,
1163                                    "ensure_super_predicates_step invoked on non-trait"),
1164         };
1165
1166         // In-scope when converting the superbounds for `Trait` are
1167         // that `Self:Trait` as well as any bounds that appear on the
1168         // generic types:
1169         let trait_def = trait_def_of_item(ccx, item);
1170         let self_predicate = ty::GenericPredicates {
1171             predicates: VecPerParamSpace::new(vec![],
1172                                               vec![trait_def.trait_ref.to_predicate()],
1173                                               vec![])
1174         };
1175         let scope = &(generics, &self_predicate);
1176
1177         // Convert the bounds that follow the colon, e.g. `Bar+Zed` in `trait Foo : Bar+Zed`.
1178         let self_param_ty = tcx.mk_self_type();
1179         let superbounds1 = compute_bounds(&ccx.icx(scope),
1180                                     self_param_ty,
1181                                     bounds,
1182                                     SizedByDefault::No,
1183                                     item.span);
1184
1185         let superbounds1 = superbounds1.predicates(tcx, self_param_ty);
1186
1187         // Convert any explicit superbounds in the where clause,
1188         // e.g. `trait Foo where Self : Bar`:
1189         let superbounds2 = generics.get_type_parameter_bounds(&ccx.icx(scope), item.span, item.id);
1190
1191         // Combine the two lists to form the complete set of superbounds:
1192         let superbounds = superbounds1.into_iter().chain(superbounds2).collect();
1193         let superpredicates = ty::GenericPredicates {
1194             predicates: VecPerParamSpace::new(superbounds, vec![], vec![])
1195         };
1196         debug!("superpredicates for trait {:?} = {:?}",
1197                local_def(item.id),
1198                superpredicates);
1199
1200         tcx.super_predicates.borrow_mut().insert(trait_def_id, superpredicates.clone());
1201
1202         superpredicates
1203     });
1204
1205     let def_ids: Vec<_> = superpredicates.predicates
1206                                          .iter()
1207                                          .filter_map(|p| p.to_opt_poly_trait_ref())
1208                                          .map(|tr| tr.def_id())
1209                                          .collect();
1210
1211     debug!("ensure_super_predicates_step: def_ids={:?}", def_ids);
1212
1213     def_ids
1214 }
1215
1216 fn trait_def_of_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1217                                it: &ast::Item)
1218                                -> &'tcx ty::TraitDef<'tcx>
1219 {
1220     let def_id = local_def(it.id);
1221     let tcx = ccx.tcx;
1222
1223     if let Some(def) = tcx.trait_defs.borrow().get(&def_id) {
1224         return def.clone();
1225     }
1226
1227     let (unsafety, generics, items) = match it.node {
1228         ast::ItemTrait(unsafety, ref generics, _, ref items) => (unsafety, generics, items),
1229         _ => tcx.sess.span_bug(it.span, "trait_def_of_item invoked on non-trait"),
1230     };
1231
1232     let paren_sugar = tcx.has_attr(def_id, "rustc_paren_sugar");
1233     if paren_sugar && !ccx.tcx.sess.features.borrow().unboxed_closures {
1234         ccx.tcx.sess.span_err(
1235             it.span,
1236             "the `#[rustc_paren_sugar]` attribute is a temporary means of controlling \
1237              which traits can use parenthetical notation");
1238         fileline_help!(ccx.tcx.sess, it.span,
1239                    "add `#![feature(unboxed_closures)]` to \
1240                     the crate attributes to use it");
1241     }
1242
1243     let substs = ccx.tcx.mk_substs(mk_trait_substs(ccx, generics));
1244
1245     let ty_generics = ty_generics_for_trait(ccx, it.id, substs, generics);
1246
1247     let associated_type_names: Vec<_> = items.iter().filter_map(|trait_item| {
1248         match trait_item.node {
1249             ast::TypeTraitItem(..) => Some(trait_item.ident.name),
1250             _ => None,
1251         }
1252     }).collect();
1253
1254     let trait_ref = ty::TraitRef {
1255         def_id: def_id,
1256         substs: substs,
1257     };
1258
1259     let trait_def = ty::TraitDef {
1260         paren_sugar: paren_sugar,
1261         unsafety: unsafety,
1262         generics: ty_generics,
1263         trait_ref: trait_ref,
1264         associated_type_names: associated_type_names,
1265         nonblanket_impls: RefCell::new(FnvHashMap()),
1266         blanket_impls: RefCell::new(vec![]),
1267         flags: Cell::new(ty::TraitFlags::NO_TRAIT_FLAGS)
1268     };
1269
1270     return tcx.intern_trait_def(trait_def);
1271
1272     fn mk_trait_substs<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1273                                  generics: &ast::Generics)
1274                                  -> Substs<'tcx>
1275     {
1276         let tcx = ccx.tcx;
1277
1278         // Creates a no-op substitution for the trait's type parameters.
1279         let regions =
1280             generics.lifetimes
1281                     .iter()
1282                     .enumerate()
1283                     .map(|(i, def)| ty::ReEarlyBound(ty::EarlyBoundRegion {
1284                         param_id: def.lifetime.id,
1285                         space: TypeSpace,
1286                         index: i as u32,
1287                         name: def.lifetime.name
1288                     }))
1289                     .collect();
1290
1291         // Start with the generics in the type parameters...
1292         let types: Vec<_> =
1293             generics.ty_params
1294                     .iter()
1295                     .enumerate()
1296                     .map(|(i, def)| tcx.mk_param(TypeSpace,
1297                                                  i as u32, def.ident.name))
1298                     .collect();
1299
1300         // ...and also create the `Self` parameter.
1301         let self_ty = tcx.mk_self_type();
1302
1303         Substs::new_trait(types, regions, self_ty)
1304     }
1305 }
1306
1307 fn trait_defines_associated_type_named(ccx: &CrateCtxt,
1308                                        trait_node_id: ast::NodeId,
1309                                        assoc_name: ast::Name)
1310                                        -> bool
1311 {
1312     let item = match ccx.tcx.map.get(trait_node_id) {
1313         ast_map::NodeItem(item) => item,
1314         _ => ccx.tcx.sess.bug(&format!("trait_node_id {} is not an item", trait_node_id))
1315     };
1316
1317     let trait_items = match item.node {
1318         ast::ItemTrait(_, _, _, ref trait_items) => trait_items,
1319         _ => ccx.tcx.sess.bug(&format!("trait_node_id {} is not a trait", trait_node_id))
1320     };
1321
1322     trait_items.iter().any(|trait_item| {
1323         match trait_item.node {
1324             ast::TypeTraitItem(..) => trait_item.ident.name == assoc_name,
1325             _ => false,
1326         }
1327     })
1328 }
1329
1330 fn convert_trait_predicates<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, it: &ast::Item) {
1331     let tcx = ccx.tcx;
1332     let trait_def = trait_def_of_item(ccx, it);
1333
1334     let def_id = local_def(it.id);
1335
1336     let (generics, items) = match it.node {
1337         ast::ItemTrait(_, ref generics, _, ref items) => (generics, items),
1338         ref s => {
1339             tcx.sess.span_bug(
1340                 it.span,
1341                 &format!("trait_def_of_item invoked on {:?}", s));
1342         }
1343     };
1344
1345     let super_predicates = ccx.tcx.lookup_super_predicates(def_id);
1346
1347     // `ty_generic_predicates` below will consider the bounds on the type
1348     // parameters (including `Self`) and the explicit where-clauses,
1349     // but to get the full set of predicates on a trait we need to add
1350     // in the supertrait bounds and anything declared on the
1351     // associated types.
1352     let mut base_predicates = super_predicates;
1353
1354     // Add in a predicate that `Self:Trait` (where `Trait` is the
1355     // current trait).  This is needed for builtin bounds.
1356     let self_predicate = trait_def.trait_ref.to_poly_trait_ref().to_predicate();
1357     base_predicates.predicates.push(SelfSpace, self_predicate);
1358
1359     // add in the explicit where-clauses
1360     let mut trait_predicates =
1361         ty_generic_predicates(ccx, TypeSpace, generics, &base_predicates);
1362
1363     let assoc_predicates = predicates_for_associated_types(ccx,
1364                                                            generics,
1365                                                            &trait_predicates,
1366                                                            trait_def.trait_ref,
1367                                                            items);
1368     trait_predicates.predicates.extend(TypeSpace, assoc_predicates.into_iter());
1369
1370     let prev_predicates = tcx.predicates.borrow_mut().insert(def_id, trait_predicates);
1371     assert!(prev_predicates.is_none());
1372
1373     return;
1374
1375     fn predicates_for_associated_types<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1376                                                  ast_generics: &ast::Generics,
1377                                                  trait_predicates: &ty::GenericPredicates<'tcx>,
1378                                                  self_trait_ref: ty::TraitRef<'tcx>,
1379                                                  trait_items: &[P<ast::TraitItem>])
1380                                                  -> Vec<ty::Predicate<'tcx>>
1381     {
1382         trait_items.iter().flat_map(|trait_item| {
1383             let bounds = match trait_item.node {
1384                 ast::TypeTraitItem(ref bounds, _) => bounds,
1385                 _ => {
1386                     return vec!().into_iter();
1387                 }
1388             };
1389
1390             let assoc_ty = ccx.tcx.mk_projection(self_trait_ref,
1391                                                  trait_item.ident.name);
1392
1393             let bounds = compute_bounds(&ccx.icx(&(ast_generics, trait_predicates)),
1394                                         assoc_ty,
1395                                         bounds,
1396                                         SizedByDefault::Yes,
1397                                         trait_item.span);
1398
1399             bounds.predicates(ccx.tcx, assoc_ty).into_iter()
1400         }).collect()
1401     }
1402 }
1403
1404 fn type_scheme_of_def_id<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1405                                   def_id: ast::DefId)
1406                                   -> ty::TypeScheme<'tcx>
1407 {
1408     if def_id.krate != ast::LOCAL_CRATE {
1409         return ccx.tcx.lookup_item_type(def_id);
1410     }
1411
1412     match ccx.tcx.map.find(def_id.node) {
1413         Some(ast_map::NodeItem(item)) => {
1414             type_scheme_of_item(ccx, &*item)
1415         }
1416         Some(ast_map::NodeForeignItem(foreign_item)) => {
1417             let abi = ccx.tcx.map.get_foreign_abi(def_id.node);
1418             type_scheme_of_foreign_item(ccx, &*foreign_item, abi)
1419         }
1420         x => {
1421             ccx.tcx.sess.bug(&format!("unexpected sort of node \
1422                                             in get_item_type_scheme(): {:?}",
1423                                        x));
1424         }
1425     }
1426 }
1427
1428 fn type_scheme_of_item<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1429                                 it: &ast::Item)
1430                                 -> ty::TypeScheme<'tcx>
1431 {
1432     memoized(&ccx.tcx.tcache,
1433              local_def(it.id),
1434              |_| compute_type_scheme_of_item(ccx, it))
1435 }
1436
1437 fn compute_type_scheme_of_item<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1438                                         it: &ast::Item)
1439                                         -> ty::TypeScheme<'tcx>
1440 {
1441     let tcx = ccx.tcx;
1442     match it.node {
1443         ast::ItemStatic(ref t, _, _) | ast::ItemConst(ref t, _) => {
1444             let ty = ccx.icx(&()).to_ty(&ExplicitRscope, &**t);
1445             ty::TypeScheme { ty: ty, generics: ty::Generics::empty() }
1446         }
1447         ast::ItemFn(ref decl, unsafety, _, abi, ref generics, _) => {
1448             let ty_generics = ty_generics_for_fn(ccx, generics, &ty::Generics::empty());
1449             let tofd = astconv::ty_of_bare_fn(&ccx.icx(generics), unsafety, abi, &**decl);
1450             let ty = tcx.mk_fn(Some(local_def(it.id)), tcx.mk_bare_fn(tofd));
1451             ty::TypeScheme { ty: ty, generics: ty_generics }
1452         }
1453         ast::ItemTy(ref t, ref generics) => {
1454             let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
1455             let ty = ccx.icx(generics).to_ty(&ExplicitRscope, &**t);
1456             ty::TypeScheme { ty: ty, generics: ty_generics }
1457         }
1458         ast::ItemEnum(_, ref generics) => {
1459             // Create a new generic polytype.
1460             let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
1461             let substs = mk_item_substs(ccx, &ty_generics);
1462             let t = tcx.mk_enum(local_def(it.id), tcx.mk_substs(substs));
1463             ty::TypeScheme { ty: t, generics: ty_generics }
1464         }
1465         ast::ItemStruct(_, ref generics) => {
1466             let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
1467             let substs = mk_item_substs(ccx, &ty_generics);
1468             let t = tcx.mk_struct(local_def(it.id), tcx.mk_substs(substs));
1469             ty::TypeScheme { ty: t, generics: ty_generics }
1470         }
1471         ast::ItemDefaultImpl(..) |
1472         ast::ItemTrait(..) |
1473         ast::ItemImpl(..) |
1474         ast::ItemMod(..) |
1475         ast::ItemForeignMod(..) |
1476         ast::ItemExternCrate(..) |
1477         ast::ItemUse(..) |
1478         ast::ItemMac(..) => {
1479             tcx.sess.span_bug(
1480                 it.span,
1481                 &format!("compute_type_scheme_of_item: unexpected item type: {:?}",
1482                          it.node));
1483         }
1484     }
1485 }
1486
1487 fn convert_typed_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1488                                 it: &ast::Item)
1489                                 -> (ty::TypeScheme<'tcx>, ty::GenericPredicates<'tcx>)
1490 {
1491     let tcx = ccx.tcx;
1492
1493     let tag = type_scheme_of_item(ccx, it);
1494     let scheme = TypeScheme { generics: tag.generics, ty: tag.ty };
1495     let predicates = match it.node {
1496         ast::ItemStatic(..) | ast::ItemConst(..) => {
1497             ty::GenericPredicates::empty()
1498         }
1499         ast::ItemFn(_, _, _, _, ref ast_generics, _) => {
1500             ty_generic_predicates_for_fn(ccx, ast_generics, &ty::GenericPredicates::empty())
1501         }
1502         ast::ItemTy(_, ref generics) => {
1503             ty_generic_predicates_for_type_or_impl(ccx, generics)
1504         }
1505         ast::ItemEnum(_, ref generics) => {
1506             ty_generic_predicates_for_type_or_impl(ccx, generics)
1507         }
1508         ast::ItemStruct(_, ref generics) => {
1509             ty_generic_predicates_for_type_or_impl(ccx, generics)
1510         }
1511         ast::ItemDefaultImpl(..) |
1512         ast::ItemTrait(..) |
1513         ast::ItemExternCrate(..) |
1514         ast::ItemUse(..) |
1515         ast::ItemImpl(..) |
1516         ast::ItemMod(..) |
1517         ast::ItemForeignMod(..) |
1518         ast::ItemMac(..) => {
1519             tcx.sess.span_bug(
1520                 it.span,
1521                 &format!("compute_type_scheme_of_item: unexpected item type: {:?}",
1522                          it.node));
1523         }
1524     };
1525
1526     let prev_predicates = tcx.predicates.borrow_mut().insert(local_def(it.id),
1527                                                              predicates.clone());
1528     assert!(prev_predicates.is_none());
1529
1530     // Debugging aid.
1531     if tcx.has_attr(local_def(it.id), "rustc_object_lifetime_default") {
1532         let object_lifetime_default_reprs: String =
1533             scheme.generics.types.iter()
1534                                  .map(|t| match t.object_lifetime_default {
1535                                      ty::ObjectLifetimeDefault::Specific(r) => r.to_string(),
1536                                      d => format!("{:?}", d),
1537                                  })
1538                                  .collect::<Vec<String>>()
1539                                  .join(",");
1540
1541         tcx.sess.span_err(it.span, &object_lifetime_default_reprs);
1542     }
1543
1544     return (scheme, predicates);
1545 }
1546
1547 fn type_scheme_of_foreign_item<'a, 'tcx>(
1548     ccx: &CrateCtxt<'a, 'tcx>,
1549     it: &ast::ForeignItem,
1550     abi: abi::Abi)
1551     -> ty::TypeScheme<'tcx>
1552 {
1553     memoized(&ccx.tcx.tcache,
1554              local_def(it.id),
1555              |_| compute_type_scheme_of_foreign_item(ccx, it, abi))
1556 }
1557
1558 fn compute_type_scheme_of_foreign_item<'a, 'tcx>(
1559     ccx: &CrateCtxt<'a, 'tcx>,
1560     it: &ast::ForeignItem,
1561     abi: abi::Abi)
1562     -> ty::TypeScheme<'tcx>
1563 {
1564     match it.node {
1565         ast::ForeignItemFn(ref fn_decl, ref generics) => {
1566             compute_type_scheme_of_foreign_fn_decl(ccx, fn_decl, generics, abi)
1567         }
1568         ast::ForeignItemStatic(ref t, _) => {
1569             ty::TypeScheme {
1570                 generics: ty::Generics::empty(),
1571                 ty: ast_ty_to_ty(&ccx.icx(&()), &ExplicitRscope, t)
1572             }
1573         }
1574     }
1575 }
1576
1577 fn convert_foreign_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1578                                   it: &ast::ForeignItem)
1579 {
1580     // For reasons I cannot fully articulate, I do so hate the AST
1581     // map, and I regard each time that I use it as a personal and
1582     // moral failing, but at the moment it seems like the only
1583     // convenient way to extract the ABI. - ndm
1584     let tcx = ccx.tcx;
1585     let abi = tcx.map.get_foreign_abi(it.id);
1586
1587     let scheme = type_scheme_of_foreign_item(ccx, it, abi);
1588     write_ty_to_tcx(ccx.tcx, it.id, scheme.ty);
1589
1590     let predicates = match it.node {
1591         ast::ForeignItemFn(_, ref generics) => {
1592             ty_generic_predicates_for_fn(ccx, generics, &ty::GenericPredicates::empty())
1593         }
1594         ast::ForeignItemStatic(..) => {
1595             ty::GenericPredicates::empty()
1596         }
1597     };
1598
1599     let prev_predicates = tcx.predicates.borrow_mut().insert(local_def(it.id), predicates);
1600     assert!(prev_predicates.is_none());
1601 }
1602
1603 fn ty_generics_for_type_or_impl<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1604                                           generics: &ast::Generics)
1605                                           -> ty::Generics<'tcx> {
1606     ty_generics(ccx, TypeSpace, generics, &ty::Generics::empty())
1607 }
1608
1609 fn ty_generic_predicates_for_type_or_impl<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1610                                                    generics: &ast::Generics)
1611                                                    -> ty::GenericPredicates<'tcx>
1612 {
1613     ty_generic_predicates(ccx, TypeSpace, generics, &ty::GenericPredicates::empty())
1614 }
1615
1616 fn ty_generics_for_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1617                                    trait_id: ast::NodeId,
1618                                    substs: &'tcx Substs<'tcx>,
1619                                    ast_generics: &ast::Generics)
1620                                    -> ty::Generics<'tcx>
1621 {
1622     debug!("ty_generics_for_trait(trait_id={:?}, substs={:?})",
1623            local_def(trait_id), substs);
1624
1625     let mut generics = ty_generics_for_type_or_impl(ccx, ast_generics);
1626
1627     // Add in the self type parameter.
1628     //
1629     // Something of a hack: use the node id for the trait, also as
1630     // the node id for the Self type parameter.
1631     let param_id = trait_id;
1632
1633     let def = ty::TypeParameterDef {
1634         space: SelfSpace,
1635         index: 0,
1636         name: special_idents::type_self.name,
1637         def_id: local_def(param_id),
1638         default: None,
1639         object_lifetime_default: ty::ObjectLifetimeDefault::BaseDefault,
1640     };
1641
1642     ccx.tcx.ty_param_defs.borrow_mut().insert(param_id, def.clone());
1643
1644     generics.types.push(SelfSpace, def);
1645
1646     return generics;
1647 }
1648
1649 fn ty_generics_for_fn<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1650                                generics: &ast::Generics,
1651                                base_generics: &ty::Generics<'tcx>)
1652                                -> ty::Generics<'tcx>
1653 {
1654     ty_generics(ccx, FnSpace, generics, base_generics)
1655 }
1656
1657 fn ty_generic_predicates_for_fn<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1658                                          generics: &ast::Generics,
1659                                          base_predicates: &ty::GenericPredicates<'tcx>)
1660                                          -> ty::GenericPredicates<'tcx>
1661 {
1662     ty_generic_predicates(ccx, FnSpace, generics, base_predicates)
1663 }
1664
1665 // Add the Sized bound, unless the type parameter is marked as `?Sized`.
1666 fn add_unsized_bound<'tcx>(astconv: &AstConv<'tcx>,
1667                            bounds: &mut ty::BuiltinBounds,
1668                            ast_bounds: &[ast::TyParamBound],
1669                            span: Span)
1670 {
1671     let tcx = astconv.tcx();
1672
1673     // Try to find an unbound in bounds.
1674     let mut unbound = None;
1675     for ab in ast_bounds {
1676         if let &ast::TraitTyParamBound(ref ptr, ast::TraitBoundModifier::Maybe) = ab  {
1677             if unbound.is_none() {
1678                 assert!(ptr.bound_lifetimes.is_empty());
1679                 unbound = Some(ptr.trait_ref.clone());
1680             } else {
1681                 span_err!(tcx.sess, span, E0203,
1682                           "type parameter has more than one relaxed default \
1683                                                 bound, only one is supported");
1684             }
1685         }
1686     }
1687
1688     let kind_id = tcx.lang_items.require(SizedTraitLangItem);
1689     match unbound {
1690         Some(ref tpb) => {
1691             // FIXME(#8559) currently requires the unbound to be built-in.
1692             let trait_def_id = tcx.trait_ref_to_def_id(tpb);
1693             match kind_id {
1694                 Ok(kind_id) if trait_def_id != kind_id => {
1695                     tcx.sess.span_warn(span,
1696                                        "default bound relaxed for a type parameter, but \
1697                                        this does nothing because the given bound is not \
1698                                        a default. Only `?Sized` is supported");
1699                     tcx.try_add_builtin_trait(kind_id, bounds);
1700                 }
1701                 _ => {}
1702             }
1703         }
1704         _ if kind_id.is_ok() => {
1705             tcx.try_add_builtin_trait(kind_id.unwrap(), bounds);
1706         }
1707         // No lang item for Sized, so we can't add it as a bound.
1708         None => {}
1709     }
1710 }
1711
1712 /// Returns the early-bound lifetimes declared in this generics
1713 /// listing.  For anything other than fns/methods, this is just all
1714 /// the lifetimes that are declared. For fns or methods, we have to
1715 /// screen out those that do not appear in any where-clauses etc using
1716 /// `resolve_lifetime::early_bound_lifetimes`.
1717 fn early_bound_lifetimes_from_generics(space: ParamSpace,
1718                                        ast_generics: &ast::Generics)
1719                                        -> Vec<ast::LifetimeDef>
1720 {
1721     match space {
1722         SelfSpace | TypeSpace => ast_generics.lifetimes.to_vec(),
1723         FnSpace => resolve_lifetime::early_bound_lifetimes(ast_generics),
1724     }
1725 }
1726
1727 fn ty_generic_predicates<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1728                                   space: ParamSpace,
1729                                   ast_generics: &ast::Generics,
1730                                   base_predicates: &ty::GenericPredicates<'tcx>)
1731                                   -> ty::GenericPredicates<'tcx>
1732 {
1733     let tcx = ccx.tcx;
1734     let mut result = base_predicates.clone();
1735
1736     // Collect the predicates that were written inline by the user on each
1737     // type parameter (e.g., `<T:Foo>`).
1738     for (index, param) in ast_generics.ty_params.iter().enumerate() {
1739         let index = index as u32;
1740         let param_ty = ty::ParamTy::new(space, index, param.ident.name).to_ty(ccx.tcx);
1741         let bounds = compute_bounds(&ccx.icx(&(base_predicates, ast_generics)),
1742                                     param_ty,
1743                                     &param.bounds,
1744                                     SizedByDefault::Yes,
1745                                     param.span);
1746         let predicates = bounds.predicates(ccx.tcx, param_ty);
1747         result.predicates.extend(space, predicates.into_iter());
1748     }
1749
1750     // Collect the region predicates that were declared inline as
1751     // well. In the case of parameters declared on a fn or method, we
1752     // have to be careful to only iterate over early-bound regions.
1753     let early_lifetimes = early_bound_lifetimes_from_generics(space, ast_generics);
1754     for (index, param) in early_lifetimes.iter().enumerate() {
1755         let index = index as u32;
1756         let region =
1757             ty::ReEarlyBound(ty::EarlyBoundRegion {
1758                 param_id: param.lifetime.id,
1759                 space: space,
1760                 index: index,
1761                 name: param.lifetime.name
1762             });
1763         for bound in &param.bounds {
1764             let bound_region = ast_region_to_region(ccx.tcx, bound);
1765             let outlives = ty::Binder(ty::OutlivesPredicate(region, bound_region));
1766             result.predicates.push(space, outlives.to_predicate());
1767         }
1768     }
1769
1770     // Add in the bounds that appear in the where-clause
1771     let where_clause = &ast_generics.where_clause;
1772     for predicate in &where_clause.predicates {
1773         match predicate {
1774             &ast::WherePredicate::BoundPredicate(ref bound_pred) => {
1775                 let ty = ast_ty_to_ty(&ccx.icx(&(base_predicates, ast_generics)),
1776                                       &ExplicitRscope,
1777                                       &*bound_pred.bounded_ty);
1778
1779                 for bound in bound_pred.bounds.iter() {
1780                     match bound {
1781                         &ast::TyParamBound::TraitTyParamBound(ref poly_trait_ref, _) => {
1782                             let mut projections = Vec::new();
1783
1784                             let trait_ref =
1785                                 conv_poly_trait_ref(&ccx.icx(&(base_predicates, ast_generics)),
1786                                                     ty,
1787                                                     poly_trait_ref,
1788                                                     &mut projections);
1789
1790                             result.predicates.push(space, trait_ref.to_predicate());
1791
1792                             for projection in &projections {
1793                                 result.predicates.push(space, projection.to_predicate());
1794                             }
1795                         }
1796
1797                         &ast::TyParamBound::RegionTyParamBound(ref lifetime) => {
1798                             let region = ast_region_to_region(tcx, lifetime);
1799                             let pred = ty::Binder(ty::OutlivesPredicate(ty, region));
1800                             result.predicates.push(space, ty::Predicate::TypeOutlives(pred))
1801                         }
1802                     }
1803                 }
1804             }
1805
1806             &ast::WherePredicate::RegionPredicate(ref region_pred) => {
1807                 let r1 = ast_region_to_region(tcx, &region_pred.lifetime);
1808                 for bound in &region_pred.bounds {
1809                     let r2 = ast_region_to_region(tcx, bound);
1810                     let pred = ty::Binder(ty::OutlivesPredicate(r1, r2));
1811                     result.predicates.push(space, ty::Predicate::RegionOutlives(pred))
1812                 }
1813             }
1814
1815             &ast::WherePredicate::EqPredicate(ref eq_pred) => {
1816                 // FIXME(#20041)
1817                 tcx.sess.span_bug(eq_pred.span,
1818                                     "Equality constraints are not yet \
1819                                         implemented (#20041)")
1820             }
1821         }
1822     }
1823
1824     return result;
1825 }
1826
1827 fn ty_generics<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1828                         space: ParamSpace,
1829                         ast_generics: &ast::Generics,
1830                         base_generics: &ty::Generics<'tcx>)
1831                         -> ty::Generics<'tcx>
1832 {
1833     let tcx = ccx.tcx;
1834     let mut result = base_generics.clone();
1835
1836     let early_lifetimes = early_bound_lifetimes_from_generics(space, ast_generics);
1837     for (i, l) in early_lifetimes.iter().enumerate() {
1838         let bounds = l.bounds.iter()
1839                              .map(|l| ast_region_to_region(tcx, l))
1840                              .collect();
1841         let def = ty::RegionParameterDef { name: l.lifetime.name,
1842                                            space: space,
1843                                            index: i as u32,
1844                                            def_id: local_def(l.lifetime.id),
1845                                            bounds: bounds };
1846         result.regions.push(space, def);
1847     }
1848
1849     assert!(result.types.is_empty_in(space));
1850
1851     // Now create the real type parameters.
1852     for i in 0..ast_generics.ty_params.len() {
1853         let def = get_or_create_type_parameter_def(ccx, ast_generics, space, i as u32);
1854         debug!("ty_generics: def for type param: {:?}, {:?}", def, space);
1855         result.types.push(space, def);
1856     }
1857
1858     result
1859 }
1860
1861 fn convert_default_type_parameter<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1862                                             path: &P<ast::Ty>,
1863                                             space: ParamSpace,
1864                                             index: u32)
1865                                             -> Ty<'tcx>
1866 {
1867     let ty = ast_ty_to_ty(&ccx.icx(&()), &ExplicitRscope, &path);
1868
1869     for leaf_ty in ty.walk() {
1870         if let ty::TyParam(p) = leaf_ty.sty {
1871             if p.space == space && p.idx >= index {
1872                 span_err!(ccx.tcx.sess, path.span, E0128,
1873                           "type parameters with a default cannot use \
1874                            forward declared identifiers");
1875
1876                 return ccx.tcx.types.err
1877             }
1878         }
1879     }
1880
1881     ty
1882 }
1883
1884 fn get_or_create_type_parameter_def<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1885                                              ast_generics: &ast::Generics,
1886                                              space: ParamSpace,
1887                                              index: u32)
1888                                              -> ty::TypeParameterDef<'tcx>
1889 {
1890     let param = &ast_generics.ty_params[index as usize];
1891
1892     let tcx = ccx.tcx;
1893     match tcx.ty_param_defs.borrow().get(&param.id) {
1894         Some(d) => { return d.clone(); }
1895         None => { }
1896     }
1897
1898     let default = param.default.as_ref().map(
1899         |def| convert_default_type_parameter(ccx, def, space, index)
1900     );
1901
1902     let object_lifetime_default =
1903         compute_object_lifetime_default(ccx, param.id,
1904                                         &param.bounds, &ast_generics.where_clause);
1905
1906     let def = ty::TypeParameterDef {
1907         space: space,
1908         index: index,
1909         name: param.ident.name,
1910         def_id: local_def(param.id),
1911         default: default,
1912         object_lifetime_default: object_lifetime_default,
1913     };
1914
1915     tcx.ty_param_defs.borrow_mut().insert(param.id, def.clone());
1916
1917     def
1918 }
1919
1920 /// Scan the bounds and where-clauses on a parameter to extract bounds
1921 /// of the form `T:'a` so as to determine the `ObjectLifetimeDefault`.
1922 /// This runs as part of computing the minimal type scheme, so we
1923 /// intentionally avoid just asking astconv to convert all the where
1924 /// clauses into a `ty::Predicate`. This is because that could induce
1925 /// artificial cycles.
1926 fn compute_object_lifetime_default<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1927                                             param_id: ast::NodeId,
1928                                             param_bounds: &[ast::TyParamBound],
1929                                             where_clause: &ast::WhereClause)
1930                                             -> ty::ObjectLifetimeDefault
1931 {
1932     let inline_bounds = from_bounds(ccx, param_bounds);
1933     let where_bounds = from_predicates(ccx, param_id, &where_clause.predicates);
1934     let all_bounds: HashSet<_> = inline_bounds.into_iter()
1935                                               .chain(where_bounds)
1936                                               .collect();
1937     return if all_bounds.len() > 1 {
1938         ty::ObjectLifetimeDefault::Ambiguous
1939     } else if all_bounds.len() == 0 {
1940         ty::ObjectLifetimeDefault::BaseDefault
1941     } else {
1942         ty::ObjectLifetimeDefault::Specific(
1943             all_bounds.into_iter().next().unwrap())
1944     };
1945
1946     fn from_bounds<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1947                             bounds: &[ast::TyParamBound])
1948                             -> Vec<ty::Region>
1949     {
1950         bounds.iter()
1951               .filter_map(|bound| {
1952                   match *bound {
1953                       ast::TraitTyParamBound(..) =>
1954                           None,
1955                       ast::RegionTyParamBound(ref lifetime) =>
1956                           Some(astconv::ast_region_to_region(ccx.tcx, lifetime)),
1957                   }
1958               })
1959               .collect()
1960     }
1961
1962     fn from_predicates<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1963                                 param_id: ast::NodeId,
1964                                 predicates: &[ast::WherePredicate])
1965                                 -> Vec<ty::Region>
1966     {
1967         predicates.iter()
1968                   .flat_map(|predicate| {
1969                       match *predicate {
1970                           ast::WherePredicate::BoundPredicate(ref data) => {
1971                               if data.bound_lifetimes.is_empty() &&
1972                                   is_param(ccx.tcx, &data.bounded_ty, param_id)
1973                               {
1974                                   from_bounds(ccx, &data.bounds).into_iter()
1975                               } else {
1976                                   Vec::new().into_iter()
1977                               }
1978                           }
1979                           ast::WherePredicate::RegionPredicate(..) |
1980                           ast::WherePredicate::EqPredicate(..) => {
1981                               Vec::new().into_iter()
1982                           }
1983                       }
1984                   })
1985                   .collect()
1986     }
1987 }
1988
1989 enum SizedByDefault { Yes, No, }
1990
1991 /// Translate the AST's notion of ty param bounds (which are an enum consisting of a newtyped Ty or
1992 /// a region) to ty's notion of ty param bounds, which can either be user-defined traits, or the
1993 /// built-in trait (formerly known as kind): Send.
1994 fn compute_bounds<'tcx>(astconv: &AstConv<'tcx>,
1995                         param_ty: ty::Ty<'tcx>,
1996                         ast_bounds: &[ast::TyParamBound],
1997                         sized_by_default: SizedByDefault,
1998                         span: Span)
1999                         -> astconv::Bounds<'tcx>
2000 {
2001     let mut bounds =
2002         conv_param_bounds(astconv,
2003                           span,
2004                           param_ty,
2005                           ast_bounds);
2006
2007     if let SizedByDefault::Yes = sized_by_default {
2008         add_unsized_bound(astconv,
2009                           &mut bounds.builtin_bounds,
2010                           ast_bounds,
2011                           span);
2012     }
2013
2014     bounds.trait_bounds.sort_by(|a,b| a.def_id().cmp(&b.def_id()));
2015
2016     bounds
2017 }
2018
2019 /// Converts a specific TyParamBound from the AST into a set of
2020 /// predicates that apply to the self-type. A vector is returned
2021 /// because this can be anywhere from 0 predicates (`T:?Sized` adds no
2022 /// predicates) to 1 (`T:Foo`) to many (`T:Bar<X=i32>` adds `T:Bar`
2023 /// and `<T as Bar>::X == i32`).
2024 fn predicates_from_bound<'tcx>(astconv: &AstConv<'tcx>,
2025                                param_ty: Ty<'tcx>,
2026                                bound: &ast::TyParamBound)
2027                                -> Vec<ty::Predicate<'tcx>>
2028 {
2029     match *bound {
2030         ast::TraitTyParamBound(ref tr, ast::TraitBoundModifier::None) => {
2031             let mut projections = Vec::new();
2032             let pred = conv_poly_trait_ref(astconv, param_ty, tr, &mut projections);
2033             projections.into_iter()
2034                        .map(|p| p.to_predicate())
2035                        .chain(Some(pred.to_predicate()))
2036                        .collect()
2037         }
2038         ast::RegionTyParamBound(ref lifetime) => {
2039             let region = ast_region_to_region(astconv.tcx(), lifetime);
2040             let pred = ty::Binder(ty::OutlivesPredicate(param_ty, region));
2041             vec![ty::Predicate::TypeOutlives(pred)]
2042         }
2043         ast::TraitTyParamBound(_, ast::TraitBoundModifier::Maybe) => {
2044             Vec::new()
2045         }
2046     }
2047 }
2048
2049 fn conv_poly_trait_ref<'tcx>(astconv: &AstConv<'tcx>,
2050                              param_ty: Ty<'tcx>,
2051                              trait_ref: &ast::PolyTraitRef,
2052                              projections: &mut Vec<ty::PolyProjectionPredicate<'tcx>>)
2053                              -> ty::PolyTraitRef<'tcx>
2054 {
2055     astconv::instantiate_poly_trait_ref(astconv,
2056                                         &ExplicitRscope,
2057                                         trait_ref,
2058                                         Some(param_ty),
2059                                         projections)
2060 }
2061
2062 fn conv_param_bounds<'a,'tcx>(astconv: &AstConv<'tcx>,
2063                               span: Span,
2064                               param_ty: ty::Ty<'tcx>,
2065                               ast_bounds: &[ast::TyParamBound])
2066                               -> astconv::Bounds<'tcx>
2067 {
2068     let tcx = astconv.tcx();
2069     let astconv::PartitionedBounds {
2070         builtin_bounds,
2071         trait_bounds,
2072         region_bounds
2073     } = astconv::partition_bounds(tcx, span, &ast_bounds);
2074
2075     let mut projection_bounds = Vec::new();
2076
2077     let trait_bounds: Vec<ty::PolyTraitRef> =
2078         trait_bounds.iter()
2079                     .map(|bound| conv_poly_trait_ref(astconv,
2080                                                      param_ty,
2081                                                      *bound,
2082                                                      &mut projection_bounds))
2083                     .collect();
2084
2085     let region_bounds: Vec<ty::Region> =
2086         region_bounds.into_iter()
2087                      .map(|r| ast_region_to_region(tcx, r))
2088                      .collect();
2089
2090     astconv::Bounds {
2091         region_bounds: region_bounds,
2092         builtin_bounds: builtin_bounds,
2093         trait_bounds: trait_bounds,
2094         projection_bounds: projection_bounds,
2095     }
2096 }
2097
2098 fn compute_type_scheme_of_foreign_fn_decl<'a, 'tcx>(
2099     ccx: &CrateCtxt<'a, 'tcx>,
2100     decl: &ast::FnDecl,
2101     ast_generics: &ast::Generics,
2102     abi: abi::Abi)
2103     -> ty::TypeScheme<'tcx>
2104 {
2105     for i in &decl.inputs {
2106         match (*i).pat.node {
2107             ast::PatIdent(_, _, _) => (),
2108             ast::PatWild(ast::PatWildSingle) => (),
2109             _ => {
2110                 span_err!(ccx.tcx.sess, (*i).pat.span, E0130,
2111                           "patterns aren't allowed in foreign function declarations");
2112             }
2113         }
2114     }
2115
2116     let ty_generics = ty_generics_for_fn(ccx, ast_generics, &ty::Generics::empty());
2117
2118     let rb = BindingRscope::new();
2119     let input_tys = decl.inputs
2120                         .iter()
2121                         .map(|a| ty_of_arg(&ccx.icx(ast_generics), &rb, a, None))
2122                         .collect();
2123
2124     let output = match decl.output {
2125         ast::Return(ref ty) =>
2126             ty::FnConverging(ast_ty_to_ty(&ccx.icx(ast_generics), &rb, &**ty)),
2127         ast::DefaultReturn(..) =>
2128             ty::FnConverging(ccx.tcx.mk_nil()),
2129         ast::NoReturn(..) =>
2130             ty::FnDiverging
2131     };
2132
2133     let t_fn = ccx.tcx.mk_fn(None,
2134         ccx.tcx.mk_bare_fn(ty::BareFnTy {
2135             abi: abi,
2136             unsafety: ast::Unsafety::Unsafe,
2137             sig: ty::Binder(ty::FnSig {inputs: input_tys,
2138                                        output: output,
2139                                        variadic: decl.variadic}),
2140         }));
2141
2142     ty::TypeScheme {
2143         generics: ty_generics,
2144         ty: t_fn
2145     }
2146 }
2147
2148 fn mk_item_substs<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
2149                             ty_generics: &ty::Generics<'tcx>)
2150                             -> Substs<'tcx>
2151 {
2152     let types =
2153         ty_generics.types.map(
2154             |def| ccx.tcx.mk_param_from_def(def));
2155
2156     let regions =
2157         ty_generics.regions.map(
2158             |def| def.to_early_bound_region());
2159
2160     Substs::new(types, regions)
2161 }
2162
2163 /// Verifies that the explicit self type of a method matches the impl
2164 /// or trait. This is a bit weird but basically because right now we
2165 /// don't handle the general case, but instead map it to one of
2166 /// several pre-defined options using various heuristics, this method
2167 /// comes back to check after the fact that explicit type the user
2168 /// wrote actually matches what the pre-defined option said.
2169 fn check_method_self_type<'a, 'tcx, RS:RegionScope>(
2170     ccx: &CrateCtxt<'a, 'tcx>,
2171     rs: &RS,
2172     method_type: Rc<ty::Method<'tcx>>,
2173     required_type: Ty<'tcx>,
2174     explicit_self: &ast::ExplicitSelf,
2175     body_id: ast::NodeId)
2176 {
2177     let tcx = ccx.tcx;
2178     if let ast::SelfExplicit(ref ast_type, _) = explicit_self.node {
2179         let typ = ccx.icx(&method_type.predicates).to_ty(rs, &**ast_type);
2180         let base_type = match typ.sty {
2181             ty::TyRef(_, tm) => tm.ty,
2182             ty::TyBox(typ) => typ,
2183             _ => typ,
2184         };
2185
2186         let body_scope = region::DestructionScopeData::new(body_id);
2187
2188         // "Required type" comes from the trait definition. It may
2189         // contain late-bound regions from the method, but not the
2190         // trait (since traits only have early-bound region
2191         // parameters).
2192         assert!(!base_type.has_regions_escaping_depth(1));
2193         let required_type_free =
2194             liberate_early_bound_regions(
2195                 tcx, body_scope,
2196                 &tcx.liberate_late_bound_regions(body_scope, &ty::Binder(required_type)));
2197
2198         // The "base type" comes from the impl. It too may have late-bound
2199         // regions from the method.
2200         assert!(!base_type.has_regions_escaping_depth(1));
2201         let base_type_free =
2202             liberate_early_bound_regions(
2203                 tcx, body_scope,
2204                 &tcx.liberate_late_bound_regions(body_scope, &ty::Binder(base_type)));
2205
2206         debug!("required_type={:?} required_type_free={:?} \
2207                 base_type={:?} base_type_free={:?}",
2208                required_type,
2209                required_type_free,
2210                base_type,
2211                base_type_free);
2212
2213         let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None, false);
2214         drop(::require_same_types(tcx,
2215                                   Some(&infcx),
2216                                   false,
2217                                   explicit_self.span,
2218                                   base_type_free,
2219                                   required_type_free,
2220                                   || {
2221                 format!("mismatched self type: expected `{}`",
2222                          required_type)
2223         }));
2224
2225         // We could conceviably add more free-region relations here,
2226         // but since this code is just concerned with checking that
2227         // the `&Self` types etc match up, it's not really necessary.
2228         // It would just allow people to be more approximate in some
2229         // cases. In any case, we can do it later as we feel the need;
2230         // I'd like this function to go away eventually.
2231         let free_regions = FreeRegionMap::new();
2232
2233         infcx.resolve_regions_and_report_errors(&free_regions, body_id);
2234     }
2235
2236     fn liberate_early_bound_regions<'tcx,T>(
2237         tcx: &ty::ctxt<'tcx>,
2238         scope: region::DestructionScopeData,
2239         value: &T)
2240         -> T
2241         where T : TypeFoldable<'tcx>
2242     {
2243         /*!
2244          * Convert early-bound regions into free regions; normally this is done by
2245          * applying the `free_substs` from the `ParameterEnvironment`, but this particular
2246          * method-self-type check is kind of hacky and done very early in the process,
2247          * before we really have a `ParameterEnvironment` to check.
2248          */
2249
2250         ty_fold::fold_regions(tcx, value, &mut false, |region, _| {
2251             match region {
2252                 ty::ReEarlyBound(data) => {
2253                     let def_id = local_def(data.param_id);
2254                     ty::ReFree(ty::FreeRegion { scope: scope,
2255                                                 bound_region: ty::BrNamed(def_id, data.name) })
2256                 }
2257                 _ => region
2258             }
2259         })
2260     }
2261 }
2262
2263 /// Checks that all the type parameters on an impl
2264 fn enforce_impl_params_are_constrained<'tcx>(tcx: &ty::ctxt<'tcx>,
2265                                              ast_generics: &ast::Generics,
2266                                              impl_def_id: ast::DefId,
2267                                              impl_items: &[P<ast::ImplItem>])
2268 {
2269     let impl_scheme = tcx.lookup_item_type(impl_def_id);
2270     let impl_predicates = tcx.lookup_predicates(impl_def_id);
2271     let impl_trait_ref = tcx.impl_trait_ref(impl_def_id);
2272
2273     // The trait reference is an input, so find all type parameters
2274     // reachable from there, to start (if this is an inherent impl,
2275     // then just examine the self type).
2276     let mut input_parameters: HashSet<_> =
2277         ctp::parameters_for_type(impl_scheme.ty).into_iter().collect();
2278     if let Some(ref trait_ref) = impl_trait_ref {
2279         input_parameters.extend(ctp::parameters_for_trait_ref(trait_ref));
2280     }
2281
2282     ctp::identify_constrained_type_params(tcx,
2283                                           impl_predicates.predicates.as_slice(),
2284                                           impl_trait_ref,
2285                                           &mut input_parameters);
2286
2287     for (index, ty_param) in ast_generics.ty_params.iter().enumerate() {
2288         let param_ty = ty::ParamTy { space: TypeSpace,
2289                                      idx: index as u32,
2290                                      name: ty_param.ident.name };
2291         if !input_parameters.contains(&ctp::Parameter::Type(param_ty)) {
2292             report_unused_parameter(tcx, ty_param.span, "type", &param_ty.to_string());
2293         }
2294     }
2295
2296     // Every lifetime used in an associated type must be constrained.
2297
2298     let lifetimes_in_associated_types: HashSet<_> =
2299         impl_items.iter()
2300                   .map(|item| tcx.impl_or_trait_item(local_def(item.id)))
2301                   .filter_map(|item| match item {
2302                       ty::TypeTraitItem(ref assoc_ty) => assoc_ty.ty,
2303                       ty::ConstTraitItem(..) | ty::MethodTraitItem(..) => None
2304                   })
2305                   .flat_map(|ty| ctp::parameters_for_type(ty))
2306                   .filter_map(|p| match p {
2307                       ctp::Parameter::Type(_) => None,
2308                       ctp::Parameter::Region(r) => Some(r),
2309                   })
2310                   .collect();
2311
2312     for (index, lifetime_def) in ast_generics.lifetimes.iter().enumerate() {
2313         let region = ty::EarlyBoundRegion { param_id: lifetime_def.lifetime.id,
2314                                             space: TypeSpace,
2315                                             index: index as u32,
2316                                             name: lifetime_def.lifetime.name };
2317         if
2318             lifetimes_in_associated_types.contains(&region) && // (*)
2319             !input_parameters.contains(&ctp::Parameter::Region(region))
2320         {
2321             report_unused_parameter(tcx, lifetime_def.lifetime.span,
2322                                     "lifetime", &region.name.to_string());
2323         }
2324     }
2325
2326     // (*) This is a horrible concession to reality. I think it'd be
2327     // better to just ban unconstrianed lifetimes outright, but in
2328     // practice people do non-hygenic macros like:
2329     //
2330     // ```
2331     // macro_rules! __impl_slice_eq1 {
2332     //     ($Lhs: ty, $Rhs: ty, $Bound: ident) => {
2333     //         impl<'a, 'b, A: $Bound, B> PartialEq<$Rhs> for $Lhs where A: PartialEq<B> {
2334     //            ....
2335     //         }
2336     //     }
2337     // }
2338     // ```
2339     //
2340     // In a concession to backwards compatbility, we continue to
2341     // permit those, so long as the lifetimes aren't used in
2342     // associated types. I believe this is sound, because lifetimes
2343     // used elsewhere are not projected back out.
2344 }
2345
2346 fn report_unused_parameter(tcx: &ty::ctxt,
2347                            span: Span,
2348                            kind: &str,
2349                            name: &str)
2350 {
2351     span_err!(tcx.sess, span, E0207,
2352               "the {} parameter `{}` is not constrained by the \
2353                impl trait, self type, or predicates",
2354               kind, name);
2355 }