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