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.types`
  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 a pair of `Generics` and `Ty`.  Type
  26 parameters themselves are represented as `ty_param()` instances.
  27
  28 The phasing of type conversion is somewhat complicated. There is no
  29 clear set of phases we can enforce (e.g., converting traits first,
  30 then types, or something like that) because the user can introduce
  31 arbitrary interdependencies. So instead we generally convert things
  32 lazilly and on demand, and include logic that checks for cycles.
  33 Demand is driven by calls to `AstConv::get_item_type_scheme` or
  34 `AstConv::lookup_trait_def`.
  35
  36 Currently, we "convert" types and traits in two phases (note that
  37 conversion only affects the types of items / enum variants / methods;
  38 it does not e.g. compute the types of individual expressions):
  39
  40 0. Intrinsics
  41 1. Trait/Type definitions
  42
  43 Conversion itself is done by simply walking each of the items in turn
  44 and invoking an appropriate function (e.g., `trait_def_of_item` or
  45 `convert_item`). However, it is possible that while converting an
  46 item, we may need to compute the *type scheme* or *trait definition*
  47 for other items.
  48
  49 There are some shortcomings in this design:
  50
  51 - Before walking the set of supertraits for a given trait, you must
  52   call `ensure_super_predicates` on that trait def-id. Otherwise,
  53   `item_super_predicates` will result in ICEs.
  54 - Because the item generics include defaults, cycles through type
  55   parameter defaults are illegal even if those defaults are never
  56   employed. This is not necessarily a bug.
  57
  58 */
  59
  60 use astconv::{AstConv, ast_region_to_region, Bounds, PartitionedBounds, partition_bounds};
  61 use lint;
  62 use constrained_type_params as ctp;
  63 use middle::lang_items::SizedTraitLangItem;
  64 use middle::const_val::ConstVal;
  65 use rustc_const_eval::EvalHint::UncheckedExprHint;
  66 use rustc_const_eval::{eval_const_expr_partial, report_const_eval_err};
  67 use rustc::ty::subst::Substs;
  68 use rustc::ty::{ToPredicate, ImplContainer, AssociatedItemContainer, TraitContainer};
  69 use rustc::ty::{self, AdtKind, ToPolyTraitRef, Ty, TyCtxt};
  70 use rustc::ty::util::IntTypeExt;
  71 use rscope::*;
  72 use rustc::dep_graph::DepNode;
  73 use util::common::{ErrorReported, MemoizationMap};
  74 use util::nodemap::{NodeMap, FxHashMap, FxHashSet};
  75 use CrateCtxt;
  76
  77 use rustc_const_math::ConstInt;
  78
  79 use std::cell::RefCell;
  80
  81 use syntax::{abi, ast, attr};
  82 use syntax::symbol::{Symbol, keywords};
  83 use syntax_pos::Span;
  84
  85 use rustc::hir::{self, map as hir_map, print as pprust};
  86 use rustc::hir::intravisit::{self, Visitor};
  87 use rustc::hir::def::{Def, CtorKind};
  88 use rustc::hir::def_id::DefId;
  89
  90 ///////////////////////////////////////////////////////////////////////////
  91 // Main entry point
  92
  93 pub fn collect_item_types(ccx: &CrateCtxt) {
  94     let mut visitor = CollectItemTypesVisitor { ccx: ccx };
  95     ccx.tcx.visit_all_item_likes_in_krate(DepNode::CollectItem, &mut visitor.as_deep_visitor());
  96 }
  97
  98 ///////////////////////////////////////////////////////////////////////////
  99
 100 /// Context specific to some particular item. This is what implements
 101 /// AstConv. It has information about the predicates that are defined
 102 /// on the trait. Unfortunately, this predicate information is
 103 /// available in various different forms at various points in the
 104 /// process. So we can't just store a pointer to e.g. the AST or the
 105 /// parsed ty form, we have to be more flexible. To this end, the
 106 /// `ItemCtxt` is parameterized by a `GetTypeParameterBounds` object
 107 /// that it uses to satisfy `get_type_parameter_bounds` requests.
 108 /// This object might draw the information from the AST
 109 /// (`hir::Generics`) or it might draw from a `ty::GenericPredicates`
 110 /// or both (a tuple).
 111 struct ItemCtxt<'a,'tcx:'a> {
 112     ccx: &'a CrateCtxt<'a,'tcx>,
 113     param_bounds: &'a (GetTypeParameterBounds<'tcx>+'a),
 114 }
 115
 116 #[derive(Copy, Clone, PartialEq, Eq)]
 117 pub enum AstConvRequest {
 118     GetGenerics(DefId),
 119     GetItemTypeScheme(DefId),
 120     GetTraitDef(DefId),
 121     EnsureSuperPredicates(DefId),
 122     GetTypeParameterBounds(ast::NodeId),
 123 }
 124
 125 ///////////////////////////////////////////////////////////////////////////
 126
 127 struct CollectItemTypesVisitor<'a, 'tcx: 'a> {
 128     ccx: &'a CrateCtxt<'a, 'tcx>
 129 }
 130
 131 impl<'a, 'tcx, 'v> Visitor<'v> for CollectItemTypesVisitor<'a, 'tcx> {
 132     fn visit_item(&mut self, item: &hir::Item) {
 133         convert_item(self.ccx, item);
 134         intravisit::walk_item(self, item);
 135     }
 136
 137     fn visit_expr(&mut self, expr: &hir::Expr) {
 138         if let hir::ExprClosure(..) = expr.node {
 139             convert_closure(self.ccx, expr.id);
 140         }
 141         intravisit::walk_expr(self, expr);
 142     }
 143
 144     fn visit_ty(&mut self, ty: &hir::Ty) {
 145         if let hir::TyImplTrait(..) = ty.node {
 146             let def_id = self.ccx.tcx.map.local_def_id(ty.id);
 147             generics_of_def_id(self.ccx, def_id);
 148         }
 149         intravisit::walk_ty(self, ty);
 150     }
 151
 152     fn visit_impl_item(&mut self, impl_item: &hir::ImplItem) {
 153         convert_impl_item(self.ccx, impl_item);
 154         intravisit::walk_impl_item(self, impl_item);
 155     }
 156 }
 157
 158 ///////////////////////////////////////////////////////////////////////////
 159 // Utility types and common code for the above passes.
 160
 161 impl<'a,'tcx> CrateCtxt<'a,'tcx> {
 162     fn icx(&'a self, param_bounds: &'a GetTypeParameterBounds<'tcx>) -> ItemCtxt<'a,'tcx> {
 163         ItemCtxt {
 164             ccx: self,
 165             param_bounds: param_bounds,
 166         }
 167     }
 168
 169     fn cycle_check<F,R>(&self,
 170                         span: Span,
 171                         request: AstConvRequest,
 172                         code: F)
 173                         -> Result<R,ErrorReported>
 174         where F: FnOnce() -> Result<R,ErrorReported>
 175     {
 176         {
 177             let mut stack = self.stack.borrow_mut();
 178             if let Some((i, _)) = stack.iter().enumerate().rev().find(|&(_, r)| *r == request) {
 179                 let cycle = &stack[i..];
 180                 self.report_cycle(span, cycle);
 181                 return Err(ErrorReported);
 182             }
 183             stack.push(request);
 184         }
 185
 186         let result = code();
 187
 188         self.stack.borrow_mut().pop();
 189         result
 190     }
 191
 192     fn report_cycle(&self,
 193                     span: Span,
 194                     cycle: &[AstConvRequest])
 195     {
 196         assert!(!cycle.is_empty());
 197         let tcx = self.tcx;
 198
 199         let mut err = struct_span_err!(tcx.sess, span, E0391,
 200             "unsupported cyclic reference between types/traits detected");
 201         err.span_label(span, &format!("cyclic reference"));
 202
 203         match cycle[0] {
 204             AstConvRequest::GetGenerics(def_id) |
 205             AstConvRequest::GetItemTypeScheme(def_id) |
 206             AstConvRequest::GetTraitDef(def_id) => {
 207                 err.note(
 208                     &format!("the cycle begins when processing `{}`...",
 209                              tcx.item_path_str(def_id)));
 210             }
 211             AstConvRequest::EnsureSuperPredicates(def_id) => {
 212                 err.note(
 213                     &format!("the cycle begins when computing the supertraits of `{}`...",
 214                              tcx.item_path_str(def_id)));
 215             }
 216             AstConvRequest::GetTypeParameterBounds(id) => {
 217                 let def = tcx.type_parameter_def(id);
 218                 err.note(
 219                     &format!("the cycle begins when computing the bounds \
 220                               for type parameter `{}`...",
 221                              def.name));
 222             }
 223         }
 224
 225         for request in &cycle[1..] {
 226             match *request {
 227                 AstConvRequest::GetGenerics(def_id) |
 228                 AstConvRequest::GetItemTypeScheme(def_id) |
 229                 AstConvRequest::GetTraitDef(def_id) => {
 230                     err.note(
 231                         &format!("...which then requires processing `{}`...",
 232                                  tcx.item_path_str(def_id)));
 233                 }
 234                 AstConvRequest::EnsureSuperPredicates(def_id) => {
 235                     err.note(
 236                         &format!("...which then requires computing the supertraits of `{}`...",
 237                                  tcx.item_path_str(def_id)));
 238                 }
 239                 AstConvRequest::GetTypeParameterBounds(id) => {
 240                     let def = tcx.type_parameter_def(id);
 241                     err.note(
 242                         &format!("...which then requires computing the bounds \
 243                                   for type parameter `{}`...",
 244                                  def.name));
 245                 }
 246             }
 247         }
 248
 249         match cycle[0] {
 250             AstConvRequest::GetGenerics(def_id) |
 251             AstConvRequest::GetItemTypeScheme(def_id) |
 252             AstConvRequest::GetTraitDef(def_id) => {
 253                 err.note(
 254                     &format!("...which then again requires processing `{}`, completing the cycle.",
 255                              tcx.item_path_str(def_id)));
 256             }
 257             AstConvRequest::EnsureSuperPredicates(def_id) => {
 258                 err.note(
 259                     &format!("...which then again requires computing the supertraits of `{}`, \
 260                               completing the cycle.",
 261                              tcx.item_path_str(def_id)));
 262             }
 263             AstConvRequest::GetTypeParameterBounds(id) => {
 264                 let def = tcx.type_parameter_def(id);
 265                 err.note(
 266                     &format!("...which then again requires computing the bounds \
 267                               for type parameter `{}`, completing the cycle.",
 268                              def.name));
 269             }
 270         }
 271         err.emit();
 272     }
 273
 274     /// Loads the trait def for a given trait, returning ErrorReported if a cycle arises.
 275     fn get_trait_def(&self, trait_id: DefId)
 276                      -> &'tcx ty::TraitDef<'tcx>
 277     {
 278         let tcx = self.tcx;
 279
 280         if let Some(trait_id) = tcx.map.as_local_node_id(trait_id) {
 281             let item = match tcx.map.get(trait_id) {
 282                 hir_map::NodeItem(item) => item,
 283                 _ => bug!("get_trait_def({:?}): not an item", trait_id)
 284             };
 285
 286             trait_def_of_item(self, &item)
 287         } else {
 288             tcx.lookup_trait_def(trait_id)
 289         }
 290     }
 291
 292     /// Ensure that the (transitive) super predicates for
 293     /// `trait_def_id` are available. This will report a cycle error
 294     /// if a trait `X` (transitively) extends itself in some form.
 295     fn ensure_super_predicates(&self, span: Span, trait_def_id: DefId)
 296                                -> Result<(), ErrorReported>
 297     {
 298         self.cycle_check(span, AstConvRequest::EnsureSuperPredicates(trait_def_id), || {
 299             let def_ids = ensure_super_predicates_step(self, trait_def_id);
 300
 301             for def_id in def_ids {
 302                 self.ensure_super_predicates(span, def_id)?;
 303             }
 304
 305             Ok(())
 306         })
 307     }
 308 }
 309
 310 impl<'a,'tcx> ItemCtxt<'a,'tcx> {
 311     fn to_ty<RS:RegionScope>(&self, rs: &RS, ast_ty: &hir::Ty) -> Ty<'tcx> {
 312         AstConv::ast_ty_to_ty(self, rs, ast_ty)
 313     }
 314 }
 315
 316 impl<'a, 'tcx> AstConv<'tcx, 'tcx> for ItemCtxt<'a, 'tcx> {
 317     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'tcx, 'tcx> { self.ccx.tcx }
 318
 319     fn ast_ty_to_ty_cache(&self) -> &RefCell<NodeMap<Ty<'tcx>>> {
 320         &self.ccx.ast_ty_to_ty_cache
 321     }
 322
 323     fn get_generics(&self, span: Span, id: DefId)
 324                     -> Result<&'tcx ty::Generics<'tcx>, ErrorReported>
 325     {
 326         self.ccx.cycle_check(span, AstConvRequest::GetGenerics(id), || {
 327             Ok(generics_of_def_id(self.ccx, id))
 328         })
 329     }
 330
 331     fn get_item_type(&self, span: Span, id: DefId) -> Result<Ty<'tcx>, ErrorReported> {
 332         self.ccx.cycle_check(span, AstConvRequest::GetItemTypeScheme(id), || {
 333             Ok(type_of_def_id(self.ccx, id))
 334         })
 335     }
 336
 337     fn get_trait_def(&self, span: Span, id: DefId)
 338                      -> Result<&'tcx ty::TraitDef<'tcx>, ErrorReported>
 339     {
 340         self.ccx.cycle_check(span, AstConvRequest::GetTraitDef(id), || {
 341             Ok(self.ccx.get_trait_def(id))
 342         })
 343     }
 344
 345     fn ensure_super_predicates(&self,
 346                                span: Span,
 347                                trait_def_id: DefId)
 348                                -> Result<(), ErrorReported>
 349     {
 350         debug!("ensure_super_predicates(trait_def_id={:?})",
 351                trait_def_id);
 352
 353         self.ccx.ensure_super_predicates(span, trait_def_id)
 354     }
 355
 356
 357     fn get_type_parameter_bounds(&self,
 358                                  span: Span,
 359                                  node_id: ast::NodeId)
 360                                  -> Result<Vec<ty::PolyTraitRef<'tcx>>, ErrorReported>
 361     {
 362         self.ccx.cycle_check(span, AstConvRequest::GetTypeParameterBounds(node_id), || {
 363             let v = self.param_bounds.get_type_parameter_bounds(self, span, node_id)
 364                                      .into_iter()
 365                                      .filter_map(|p| p.to_opt_poly_trait_ref())
 366                                      .collect();
 367             Ok(v)
 368         })
 369     }
 370
 371     fn get_free_substs(&self) -> Option<&Substs<'tcx>> {
 372         None
 373     }
 374
 375     fn ty_infer(&self, span: Span) -> Ty<'tcx> {
 376         struct_span_err!(
 377             self.tcx().sess,
 378             span,
 379             E0121,
 380             "the type placeholder `_` is not allowed within types on item signatures"
 381         ).span_label(span, &format!("not allowed in type signatures"))
 382         .emit();
 383         self.tcx().types.err
 384     }
 385
 386     fn projected_ty_from_poly_trait_ref(&self,
 387                                         span: Span,
 388                                         poly_trait_ref: ty::PolyTraitRef<'tcx>,
 389                                         item_name: ast::Name)
 390                                         -> Ty<'tcx>
 391     {
 392         if let Some(trait_ref) = self.tcx().no_late_bound_regions(&poly_trait_ref) {
 393             self.projected_ty(span, trait_ref, item_name)
 394         } else {
 395             // no late-bound regions, we can just ignore the binder
 396             span_err!(self.tcx().sess, span, E0212,
 397                 "cannot extract an associated type from a higher-ranked trait bound \
 398                  in this context");
 399             self.tcx().types.err
 400         }
 401     }
 402
 403     fn projected_ty(&self,
 404                     _span: Span,
 405                     trait_ref: ty::TraitRef<'tcx>,
 406                     item_name: ast::Name)
 407                     -> Ty<'tcx>
 408     {
 409         self.tcx().mk_projection(trait_ref, item_name)
 410     }
 411
 412     fn set_tainted_by_errors(&self) {
 413         // no obvious place to track this, just let it go
 414     }
 415 }
 416
 417 /// Interface used to find the bounds on a type parameter from within
 418 /// an `ItemCtxt`. This allows us to use multiple kinds of sources.
 419 trait GetTypeParameterBounds<'tcx> {
 420     fn get_type_parameter_bounds(&self,
 421                                  astconv: &AstConv<'tcx, 'tcx>,
 422                                  span: Span,
 423                                  node_id: ast::NodeId)
 424                                  -> Vec<ty::Predicate<'tcx>>;
 425 }
 426
 427 /// Find bounds from both elements of the tuple.
 428 impl<'a,'b,'tcx,A,B> GetTypeParameterBounds<'tcx> for (&'a A,&'b B)
 429     where A : GetTypeParameterBounds<'tcx>, B : GetTypeParameterBounds<'tcx>
 430 {
 431     fn get_type_parameter_bounds(&self,
 432                                  astconv: &AstConv<'tcx, 'tcx>,
 433                                  span: Span,
 434                                  node_id: ast::NodeId)
 435                                  -> Vec<ty::Predicate<'tcx>>
 436     {
 437         let mut v = self.0.get_type_parameter_bounds(astconv, span, node_id);
 438         v.extend(self.1.get_type_parameter_bounds(astconv, span, node_id));
 439         v
 440     }
 441 }
 442
 443 /// Empty set of bounds.
 444 impl<'tcx> GetTypeParameterBounds<'tcx> for () {
 445     fn get_type_parameter_bounds(&self,
 446                                  _astconv: &AstConv<'tcx, 'tcx>,
 447                                  _span: Span,
 448                                  _node_id: ast::NodeId)
 449                                  -> Vec<ty::Predicate<'tcx>>
 450     {
 451         Vec::new()
 452     }
 453 }
 454
 455 /// Find bounds from the parsed and converted predicates.  This is
 456 /// used when converting methods, because by that time the predicates
 457 /// from the trait/impl have been fully converted.
 458 impl<'tcx> GetTypeParameterBounds<'tcx> for ty::GenericPredicates<'tcx> {
 459     fn get_type_parameter_bounds(&self,
 460                                  astconv: &AstConv<'tcx, 'tcx>,
 461                                  span: Span,
 462                                  node_id: ast::NodeId)
 463                                  -> Vec<ty::Predicate<'tcx>>
 464     {
 465         let def = astconv.tcx().type_parameter_def(node_id);
 466
 467         let mut results = self.parent.map_or(vec![], |def_id| {
 468             let parent = astconv.tcx().item_predicates(def_id);
 469             parent.get_type_parameter_bounds(astconv, span, node_id)
 470         });
 471
 472         results.extend(self.predicates.iter().filter(|predicate| {
 473             match **predicate {
 474                 ty::Predicate::Trait(ref data) => {
 475                     data.skip_binder().self_ty().is_param(def.index)
 476                 }
 477                 ty::Predicate::TypeOutlives(ref data) => {
 478                     data.skip_binder().0.is_param(def.index)
 479                 }
 480                 ty::Predicate::Equate(..) |
 481                 ty::Predicate::RegionOutlives(..) |
 482                 ty::Predicate::WellFormed(..) |
 483                 ty::Predicate::ObjectSafe(..) |
 484                 ty::Predicate::ClosureKind(..) |
 485                 ty::Predicate::Projection(..) => {
 486                     false
 487                 }
 488             }
 489         }).cloned());
 490
 491         results
 492     }
 493 }
 494
 495 /// Find bounds from hir::Generics. This requires scanning through the
 496 /// AST. We do this to avoid having to convert *all* the bounds, which
 497 /// would create artificial cycles. Instead we can only convert the
 498 /// bounds for a type parameter `X` if `X::Foo` is used.
 499 impl<'tcx> GetTypeParameterBounds<'tcx> for hir::Generics {
 500     fn get_type_parameter_bounds(&self,
 501                                  astconv: &AstConv<'tcx, 'tcx>,
 502                                  _: Span,
 503                                  node_id: ast::NodeId)
 504                                  -> Vec<ty::Predicate<'tcx>>
 505     {
 506         // In the AST, bounds can derive from two places. Either
 507         // written inline like `<T:Foo>` or in a where clause like
 508         // `where T:Foo`.
 509
 510         let def = astconv.tcx().type_parameter_def(node_id);
 511         let ty = astconv.tcx().mk_param_from_def(&def);
 512
 513         let from_ty_params =
 514             self.ty_params
 515                 .iter()
 516                 .filter(|p| p.id == node_id)
 517                 .flat_map(|p| p.bounds.iter())
 518                 .flat_map(|b| predicates_from_bound(astconv, ty, b));
 519
 520         let from_where_clauses =
 521             self.where_clause
 522                 .predicates
 523                 .iter()
 524                 .filter_map(|wp| match *wp {
 525                     hir::WherePredicate::BoundPredicate(ref bp) => Some(bp),
 526                     _ => None
 527                 })
 528                 .filter(|bp| is_param(astconv.tcx(), &bp.bounded_ty, node_id))
 529                 .flat_map(|bp| bp.bounds.iter())
 530                 .flat_map(|b| predicates_from_bound(astconv, ty, b));
 531
 532         from_ty_params.chain(from_where_clauses).collect()
 533     }
 534 }
 535
 536 /// Tests whether this is the AST for a reference to the type
 537 /// parameter with id `param_id`. We use this so as to avoid running
 538 /// `ast_ty_to_ty`, because we want to avoid triggering an all-out
 539 /// conversion of the type to avoid inducing unnecessary cycles.
 540 fn is_param<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 541                       ast_ty: &hir::Ty,
 542                       param_id: ast::NodeId)
 543                       -> bool
 544 {
 545     if let hir::TyPath(hir::QPath::Resolved(None, _)) = ast_ty.node {
 546         let path_res = tcx.expect_resolution(ast_ty.id);
 547         match path_res.base_def {
 548             Def::SelfTy(Some(def_id), None) |
 549             Def::TyParam(def_id) if path_res.depth == 0 => {
 550                 def_id == tcx.map.local_def_id(param_id)
 551             }
 552             _ => false
 553         }
 554     } else {
 555         false
 556     }
 557 }
 558
 559 fn convert_field<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 560                            struct_generics: &'tcx ty::Generics<'tcx>,
 561                            struct_predicates: &ty::GenericPredicates<'tcx>,
 562                            field: &hir::StructField,
 563                            ty_f: ty::FieldDefMaster<'tcx>)
 564 {
 565     let tt = ccx.icx(struct_predicates).to_ty(&ExplicitRscope, &field.ty);
 566     ty_f.fulfill_ty(tt);
 567
 568     let def_id = ccx.tcx.map.local_def_id(field.id);
 569     ccx.tcx.item_types.borrow_mut().insert(def_id, tt);
 570     ccx.tcx.generics.borrow_mut().insert(def_id, struct_generics);
 571     ccx.tcx.predicates.borrow_mut().insert(def_id, struct_predicates.clone());
 572 }
 573
 574 fn convert_closure<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 575                              node_id: ast::NodeId)
 576 {
 577     let tcx = ccx.tcx;
 578     let def_id = tcx.map.local_def_id(node_id);
 579     let base_def_id = tcx.closure_base_def_id(def_id);
 580     let base_generics = generics_of_def_id(ccx, base_def_id);
 581
 582     // provide junk type parameter defs - the only place that
 583     // cares about anything but the length is instantiation,
 584     // and we don't do that for closures.
 585     let upvar_decls : Vec<_> = tcx.with_freevars(node_id, |fv| {
 586         fv.iter().enumerate().map(|(i, _)| ty::TypeParameterDef {
 587             index: (base_generics.count() as u32) + (i as u32),
 588             name: Symbol::intern("<upvar>"),
 589             def_id: def_id,
 590             default_def_id: base_def_id,
 591             default: None,
 592             object_lifetime_default: ty::ObjectLifetimeDefault::BaseDefault,
 593             pure_wrt_drop: false,
 594         }).collect()
 595     });
 596     tcx.generics.borrow_mut().insert(def_id, tcx.alloc_generics(ty::Generics {
 597         parent: Some(base_def_id),
 598         parent_regions: base_generics.parent_regions + (base_generics.regions.len() as u32),
 599         parent_types: base_generics.parent_types + (base_generics.types.len() as u32),
 600         regions: vec![],
 601         types: upvar_decls,
 602         has_self: base_generics.has_self,
 603     }));
 604
 605     type_of_def_id(ccx, def_id);
 606 }
 607
 608 fn convert_method<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 609                             container: AssociatedItemContainer,
 610                             id: ast::NodeId,
 611                             sig: &hir::MethodSig,
 612                             untransformed_rcvr_ty: Ty<'tcx>,
 613                             rcvr_ty_predicates: &ty::GenericPredicates<'tcx>) {
 614     let def_id = ccx.tcx.map.local_def_id(id);
 615     let ty_generics = generics_of_def_id(ccx, def_id);
 616
 617     let ty_generic_predicates =
 618         ty_generic_predicates(ccx, &sig.generics, ty_generics.parent, vec![], false);
 619
 620     let anon_scope = match container {
 621         ImplContainer(_) => Some(AnonTypeScope::new(def_id)),
 622         TraitContainer(_) => None
 623     };
 624     let fty = AstConv::ty_of_method(&ccx.icx(&(rcvr_ty_predicates, &sig.generics)),
 625                                     sig, untransformed_rcvr_ty, anon_scope);
 626
 627     let substs = mk_item_substs(&ccx.icx(&(rcvr_ty_predicates, &sig.generics)),
 628                                 ccx.tcx.map.span(id), def_id);
 629     let fty = ccx.tcx.mk_fn_def(def_id, substs, fty);
 630     ccx.tcx.item_types.borrow_mut().insert(def_id, fty);
 631     ccx.tcx.predicates.borrow_mut().insert(def_id, ty_generic_predicates);
 632 }
 633
 634 fn convert_associated_const<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 635                                       container: AssociatedItemContainer,
 636                                       id: ast::NodeId,
 637                                       ty: ty::Ty<'tcx>)
 638 {
 639     let predicates = ty::GenericPredicates {
 640         parent: Some(container.id()),
 641         predicates: vec![]
 642     };
 643     let def_id = ccx.tcx.map.local_def_id(id);
 644     ccx.tcx.predicates.borrow_mut().insert(def_id, predicates);
 645     ccx.tcx.item_types.borrow_mut().insert(def_id, ty);
 646 }
 647
 648 fn convert_associated_type<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 649                                      container: AssociatedItemContainer,
 650                                      id: ast::NodeId,
 651                                      ty: Option<Ty<'tcx>>)
 652 {
 653     let predicates = ty::GenericPredicates {
 654         parent: Some(container.id()),
 655         predicates: vec![]
 656     };
 657     let def_id = ccx.tcx.map.local_def_id(id);
 658     ccx.tcx.predicates.borrow_mut().insert(def_id, predicates);
 659
 660     if let Some(ty) = ty {
 661         ccx.tcx.item_types.borrow_mut().insert(def_id, ty);
 662     }
 663 }
 664
 665 fn ensure_no_ty_param_bounds(ccx: &CrateCtxt,
 666                                  span: Span,
 667                                  generics: &hir::Generics,
 668                                  thing: &'static str) {
 669     let mut warn = false;
 670
 671     for ty_param in generics.ty_params.iter() {
 672         for bound in ty_param.bounds.iter() {
 673             match *bound {
 674                 hir::TraitTyParamBound(..) => {
 675                     warn = true;
 676                 }
 677                 hir::RegionTyParamBound(..) => { }
 678             }
 679         }
 680     }
 681
 682     if warn {
 683         // According to accepted RFC #XXX, we should
 684         // eventually accept these, but it will not be
 685         // part of this PR. Still, convert to warning to
 686         // make bootstrapping easier.
 687         span_warn!(ccx.tcx.sess, span, E0122,
 688                    "trait bounds are not (yet) enforced \
 689                    in {} definitions",
 690                    thing);
 691     }
 692 }
 693
 694 fn convert_item(ccx: &CrateCtxt, it: &hir::Item) {
 695     let tcx = ccx.tcx;
 696     debug!("convert: item {} with id {}", it.name, it.id);
 697     match it.node {
 698         // These don't define types.
 699         hir::ItemExternCrate(_) | hir::ItemUse(..) | hir::ItemMod(_) => {
 700         }
 701         hir::ItemForeignMod(ref foreign_mod) => {
 702             for item in &foreign_mod.items {
 703                 convert_foreign_item(ccx, item);
 704             }
 705         }
 706         hir::ItemEnum(ref enum_definition, _) => {
 707             let def_id = ccx.tcx.map.local_def_id(it.id);
 708             let ty = type_of_def_id(ccx, def_id);
 709             let generics = generics_of_def_id(ccx, def_id);
 710             let predicates = predicates_of_item(ccx, it);
 711             convert_enum_variant_types(ccx,
 712                                        tcx.lookup_adt_def_master(ccx.tcx.map.local_def_id(it.id)),
 713                                        ty,
 714                                        generics,
 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                                                     tcx.mk_self_type());
 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                       _) => {
 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             generics_of_def_id(ccx, def_id);
 739             let mut ty_predicates =
 740                 ty_generic_predicates(ccx, generics, None, vec![], false);
 741
 742             debug!("convert: impl_bounds={:?}", ty_predicates);
 743
 744             let selfty = ccx.icx(&ty_predicates).to_ty(&ExplicitRscope, &selfty);
 745             tcx.item_types.borrow_mut().insert(def_id, selfty);
 746
 747             let trait_ref = opt_trait_ref.as_ref().map(|ast_trait_ref| {
 748                 AstConv::instantiate_mono_trait_ref(&ccx.icx(&ty_predicates),
 749                                                     &ExplicitRscope,
 750                                                     ast_trait_ref,
 751                                                     selfty)
 752             });
 753             tcx.impl_trait_refs.borrow_mut().insert(def_id, trait_ref);
 754
 755             // Subtle: before we store the predicates into the tcx, we
 756             // sort them so that predicates like `T: Foo<Item=U>` come
 757             // before uses of `U`.  This avoids false ambiguity errors
 758             // in trait checking. See `setup_constraining_predicates`
 759             // for details.
 760             ctp::setup_constraining_predicates(&mut ty_predicates.predicates,
 761                                                trait_ref,
 762                                                &mut ctp::parameters_for_impl(selfty, trait_ref));
 763
 764             tcx.predicates.borrow_mut().insert(def_id, ty_predicates.clone());
 765         },
 766         hir::ItemTrait(.., ref trait_items) => {
 767             let trait_def = trait_def_of_item(ccx, it);
 768             let def_id = trait_def.trait_ref.def_id;
 769             let _: Result<(), ErrorReported> = // any error is already reported, can ignore
 770                 ccx.ensure_super_predicates(it.span, def_id);
 771             convert_trait_predicates(ccx, it);
 772             let trait_predicates = tcx.item_predicates(def_id);
 773
 774             debug!("convert: trait_bounds={:?}", trait_predicates);
 775
 776             // FIXME: is the ordering here important? I think it is.
 777             let container = TraitContainer(def_id);
 778
 779             // Convert all the associated constants.
 780             for trait_item in trait_items {
 781                 if let hir::ConstTraitItem(ref ty, _) = trait_item.node {
 782                     let const_def_id = ccx.tcx.map.local_def_id(trait_item.id);
 783                     generics_of_def_id(ccx, const_def_id);
 784                     let ty = ccx.icx(&trait_predicates)
 785                         .to_ty(&ExplicitRscope, ty);
 786                     tcx.item_types.borrow_mut().insert(const_def_id, ty);
 787                     convert_associated_const(ccx, container, trait_item.id, ty)
 788                 }
 789             }
 790
 791             // Convert all the associated types.
 792             for trait_item in trait_items {
 793                 if let hir::TypeTraitItem(_, ref opt_ty) = trait_item.node {
 794                     let type_def_id = ccx.tcx.map.local_def_id(trait_item.id);
 795                     generics_of_def_id(ccx, type_def_id);
 796
 797                     let typ = opt_ty.as_ref().map({
 798                         |ty| ccx.icx(&trait_predicates).to_ty(&ExplicitRscope, &ty)
 799                     });
 800
 801                     convert_associated_type(ccx, container, trait_item.id, typ);
 802                 }
 803             }
 804
 805             // Convert all the methods
 806             for trait_item in trait_items {
 807                 if let hir::MethodTraitItem(ref sig, _) = trait_item.node {
 808                     convert_method(ccx,
 809                                    container,
 810                                    trait_item.id,
 811                                    sig,
 812                                    tcx.mk_self_type(),
 813                                    &trait_predicates);
 814                 }
 815             }
 816         },
 817         hir::ItemStruct(ref struct_def, _) |
 818         hir::ItemUnion(ref struct_def, _) => {
 819             let def_id = ccx.tcx.map.local_def_id(it.id);
 820             let ty = type_of_def_id(ccx, def_id);
 821             let generics = generics_of_def_id(ccx, def_id);
 822             let predicates = predicates_of_item(ccx, it);
 823
 824             let variant = tcx.lookup_adt_def_master(def_id).struct_variant();
 825
 826             for (f, ty_f) in struct_def.fields().iter().zip(variant.fields.iter()) {
 827                 convert_field(ccx, generics, &predicates, f, ty_f)
 828             }
 829
 830             if !struct_def.is_struct() {
 831                 convert_variant_ctor(ccx, struct_def.id(), variant, ty, predicates);
 832             }
 833         },
 834         hir::ItemTy(_, ref generics) => {
 835             ensure_no_ty_param_bounds(ccx, it.span, generics, "type");
 836             let def_id = ccx.tcx.map.local_def_id(it.id);
 837             type_of_def_id(ccx, def_id);
 838             generics_of_def_id(ccx, def_id);
 839             predicates_of_item(ccx, it);
 840         },
 841         _ => {
 842             let def_id = ccx.tcx.map.local_def_id(it.id);
 843             type_of_def_id(ccx, def_id);
 844             generics_of_def_id(ccx, def_id);
 845             predicates_of_item(ccx, it);
 846         },
 847     }
 848 }
 849
 850 fn convert_impl_item(ccx: &CrateCtxt, impl_item: &hir::ImplItem) {
 851     let tcx = ccx.tcx;
 852
 853     // we can lookup details about the impl because items are visited
 854     // before impl-items
 855     let impl_def_id = tcx.map.get_parent_did(impl_item.id);
 856     let impl_predicates = tcx.item_predicates(impl_def_id);
 857     let impl_trait_ref = tcx.impl_trait_ref(impl_def_id);
 858     let impl_self_ty = tcx.item_type(impl_def_id);
 859
 860     match impl_item.node {
 861         hir::ImplItemKind::Const(ref ty, _) => {
 862             let const_def_id = ccx.tcx.map.local_def_id(impl_item.id);
 863             generics_of_def_id(ccx, const_def_id);
 864             let ty = ccx.icx(&impl_predicates)
 865                         .to_ty(&ExplicitRscope, &ty);
 866             tcx.item_types.borrow_mut().insert(const_def_id, ty);
 867             convert_associated_const(ccx, ImplContainer(impl_def_id),
 868                                      impl_item.id, ty);
 869         }
 870
 871         hir::ImplItemKind::Type(ref ty) => {
 872             let type_def_id = ccx.tcx.map.local_def_id(impl_item.id);
 873             generics_of_def_id(ccx, type_def_id);
 874
 875             if impl_trait_ref.is_none() {
 876                 span_err!(tcx.sess, impl_item.span, E0202,
 877                           "associated types are not allowed in inherent impls");
 878             }
 879
 880             let typ = ccx.icx(&impl_predicates).to_ty(&ExplicitRscope, ty);
 881
 882             convert_associated_type(ccx, ImplContainer(impl_def_id), impl_item.id, Some(typ));
 883         }
 884
 885         hir::ImplItemKind::Method(ref sig, _) => {
 886             convert_method(ccx, ImplContainer(impl_def_id),
 887                            impl_item.id, sig, impl_self_ty,
 888                            &impl_predicates);
 889         }
 890     }
 891 }
 892
 893 fn convert_variant_ctor<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 894                                   ctor_id: ast::NodeId,
 895                                   variant: ty::VariantDef<'tcx>,
 896                                   ty: Ty<'tcx>,
 897                                   predicates: ty::GenericPredicates<'tcx>) {
 898     let tcx = ccx.tcx;
 899     let def_id = tcx.map.local_def_id(ctor_id);
 900     generics_of_def_id(ccx, def_id);
 901     let ctor_ty = match variant.ctor_kind {
 902         CtorKind::Fictive | CtorKind::Const => ty,
 903         CtorKind::Fn => {
 904             let inputs: Vec<_> =
 905                 variant.fields
 906                 .iter()
 907                 .map(|field| field.unsubst_ty())
 908                 .collect();
 909             let substs = mk_item_substs(&ccx.icx(&predicates),
 910                                         ccx.tcx.map.span(ctor_id), def_id);
 911             tcx.mk_fn_def(def_id, substs, tcx.mk_bare_fn(ty::BareFnTy {
 912                 unsafety: hir::Unsafety::Normal,
 913                 abi: abi::Abi::Rust,
 914                 sig: ty::Binder(ty::FnSig {
 915                     inputs: inputs,
 916                     output: ty,
 917                     variadic: false
 918                 })
 919             }))
 920         }
 921     };
 922     tcx.item_types.borrow_mut().insert(def_id, ctor_ty);
 923     tcx.predicates.borrow_mut().insert(tcx.map.local_def_id(ctor_id), predicates);
 924 }
 925
 926 fn convert_enum_variant_types<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 927                                         def: ty::AdtDefMaster<'tcx>,
 928                                         ty: Ty<'tcx>,
 929                                         generics: &'tcx ty::Generics<'tcx>,
 930                                         predicates: ty::GenericPredicates<'tcx>,
 931                                         variants: &[hir::Variant]) {
 932     // fill the field types
 933     for (variant, ty_variant) in variants.iter().zip(def.variants.iter()) {
 934         for (f, ty_f) in variant.node.data.fields().iter().zip(ty_variant.fields.iter()) {
 935             convert_field(ccx, generics, &predicates, f, ty_f)
 936         }
 937
 938         // Convert the ctor, if any. This also registers the variant as
 939         // an item.
 940         convert_variant_ctor(
 941             ccx,
 942             variant.node.data.id(),
 943             ty_variant,
 944             ty,
 945             predicates.clone()
 946         );
 947     }
 948 }
 949
 950 fn convert_struct_variant<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 951                                     did: DefId,
 952                                     name: ast::Name,
 953                                     disr_val: ty::Disr,
 954                                     def: &hir::VariantData)
 955                                     -> ty::VariantDefData<'tcx, 'tcx> {
 956     let mut seen_fields: FxHashMap<ast::Name, Span> = FxHashMap();
 957     let node_id = ccx.tcx.map.as_local_node_id(did).unwrap();
 958     let fields = def.fields().iter().map(|f| {
 959         let fid = ccx.tcx.map.local_def_id(f.id);
 960         let dup_span = seen_fields.get(&f.name).cloned();
 961         if let Some(prev_span) = dup_span {
 962             struct_span_err!(ccx.tcx.sess, f.span, E0124,
 963                              "field `{}` is already declared",
 964                              f.name)
 965                 .span_label(f.span, &"field already declared")
 966                 .span_label(prev_span, &format!("`{}` first declared here", f.name))
 967                 .emit();
 968         } else {
 969             seen_fields.insert(f.name, f.span);
 970         }
 971
 972         ty::FieldDefData::new(fid, f.name,
 973             ty::Visibility::from_hir(&f.vis, node_id, ccx.tcx))
 974     }).collect();
 975     ty::VariantDefData {
 976         did: did,
 977         name: name,
 978         disr_val: disr_val,
 979         fields: fields,
 980         ctor_kind: CtorKind::from_hir(def),
 981     }
 982 }
 983
 984 fn convert_struct_def<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 985                                 it: &hir::Item,
 986                                 def: &hir::VariantData)
 987                                 -> ty::AdtDefMaster<'tcx>
 988 {
 989     let did = ccx.tcx.map.local_def_id(it.id);
 990     // Use separate constructor id for unit/tuple structs and reuse did for braced structs.
 991     let ctor_id = if !def.is_struct() { Some(ccx.tcx.map.local_def_id(def.id())) } else { None };
 992     let variants = vec![convert_struct_variant(ccx, ctor_id.unwrap_or(did), it.name,
 993                                                ConstInt::Infer(0), def)];
 994     let adt = ccx.tcx.intern_adt_def(did, AdtKind::Struct, variants);
 995     if let Some(ctor_id) = ctor_id {
 996         // Make adt definition available through constructor id as well.
 997         ccx.tcx.insert_adt_def(ctor_id, adt);
 998     }
 999     adt
1000 }
1001
1002 fn convert_union_def<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1003                                 it: &hir::Item,
1004                                 def: &hir::VariantData)
1005                                 -> ty::AdtDefMaster<'tcx>
1006 {
1007     let did = ccx.tcx.map.local_def_id(it.id);
1008     let variants = vec![convert_struct_variant(ccx, did, it.name, ConstInt::Infer(0), def)];
1009     ccx.tcx.intern_adt_def(did, AdtKind::Union, variants)
1010 }
1011
1012     fn evaluate_disr_expr(ccx: &CrateCtxt, repr_ty: attr::IntType, e: &hir::Expr)
1013                           -> Option<ty::Disr> {
1014         debug!("disr expr, checking {}", pprust::expr_to_string(e));
1015
1016         let ty_hint = repr_ty.to_ty(ccx.tcx);
1017         let print_err = |cv: ConstVal| {
1018             struct_span_err!(ccx.tcx.sess, e.span, E0079, "mismatched types")
1019                 .note_expected_found(&"type", &ty_hint, &format!("{}", cv.description()))
1020                 .span_label(e.span, &format!("expected '{}' type", ty_hint))
1021                 .emit();
1022         };
1023
1024         let hint = UncheckedExprHint(ty_hint);
1025         match eval_const_expr_partial(ccx.tcx, e, hint, None) {
1026             Ok(ConstVal::Integral(i)) => {
1027                 // FIXME: eval_const_expr_partial should return an error if the hint is wrong
1028                 match (repr_ty, i) {
1029                     (attr::SignedInt(ast::IntTy::I8), ConstInt::I8(_)) |
1030                     (attr::SignedInt(ast::IntTy::I16), ConstInt::I16(_)) |
1031                     (attr::SignedInt(ast::IntTy::I32), ConstInt::I32(_)) |
1032                     (attr::SignedInt(ast::IntTy::I64), ConstInt::I64(_)) |
1033                     (attr::SignedInt(ast::IntTy::Is), ConstInt::Isize(_)) |
1034                     (attr::UnsignedInt(ast::UintTy::U8), ConstInt::U8(_)) |
1035                     (attr::UnsignedInt(ast::UintTy::U16), ConstInt::U16(_)) |
1036                     (attr::UnsignedInt(ast::UintTy::U32), ConstInt::U32(_)) |
1037                     (attr::UnsignedInt(ast::UintTy::U64), ConstInt::U64(_)) |
1038                     (attr::UnsignedInt(ast::UintTy::Us), ConstInt::Usize(_)) => Some(i),
1039                     (_, i) => {
1040                         print_err(ConstVal::Integral(i));
1041                         None
1042                     },
1043                 }
1044             },
1045             Ok(cv) => {
1046                 print_err(cv);
1047                 None
1048             },
1049             // enum variant evaluation happens before the global constant check
1050             // so we need to report the real error
1051             Err(err) => {
1052                 let mut diag = report_const_eval_err(
1053                     ccx.tcx, &err, e.span, "enum discriminant");
1054                 diag.emit();
1055                 None
1056             }
1057         }
1058     }
1059
1060 fn convert_enum_def<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1061                               it: &hir::Item,
1062                               def: &hir::EnumDef)
1063                               -> ty::AdtDefMaster<'tcx>
1064 {
1065     let tcx = ccx.tcx;
1066     let did = tcx.map.local_def_id(it.id);
1067     let repr_hints = tcx.lookup_repr_hints(did);
1068     let repr_type = tcx.enum_repr_type(repr_hints.get(0));
1069     let initial = repr_type.initial_discriminant(tcx);
1070     let mut prev_disr = None::<ty::Disr>;
1071     let variants = def.variants.iter().map(|v| {
1072         let wrapped_disr = prev_disr.map_or(initial, |d| d.wrap_incr());
1073         let disr = if let Some(ref e) = v.node.disr_expr {
1074             evaluate_disr_expr(ccx, repr_type, e)
1075         } else if let Some(disr) = repr_type.disr_incr(tcx, prev_disr) {
1076             Some(disr)
1077         } else {
1078             struct_span_err!(tcx.sess, v.span, E0370,
1079                              "enum discriminant overflowed")
1080                 .span_label(v.span, &format!("overflowed on value after {}", prev_disr.unwrap()))
1081                 .note(&format!("explicitly set `{} = {}` if that is desired outcome",
1082                                v.node.name, wrapped_disr))
1083                 .emit();
1084             None
1085         }.unwrap_or(wrapped_disr);
1086         prev_disr = Some(disr);
1087
1088         let did = tcx.map.local_def_id(v.node.data.id());
1089         convert_struct_variant(ccx, did, v.node.name, disr, &v.node.data)
1090     }).collect();
1091     tcx.intern_adt_def(tcx.map.local_def_id(it.id), AdtKind::Enum, variants)
1092 }
1093
1094 /// Ensures that the super-predicates of the trait with def-id
1095 /// trait_def_id are converted and stored. This does NOT ensure that
1096 /// the transitive super-predicates are converted; that is the job of
1097 /// the `ensure_super_predicates()` method in the `AstConv` impl
1098 /// above. Returns a list of trait def-ids that must be ensured as
1099 /// well to guarantee that the transitive superpredicates are
1100 /// converted.
1101 fn ensure_super_predicates_step(ccx: &CrateCtxt,
1102                                 trait_def_id: DefId)
1103                                 -> Vec<DefId>
1104 {
1105     let tcx = ccx.tcx;
1106
1107     debug!("ensure_super_predicates_step(trait_def_id={:?})", trait_def_id);
1108
1109     let trait_node_id = if let Some(n) = tcx.map.as_local_node_id(trait_def_id) {
1110         n
1111     } else {
1112         // If this trait comes from an external crate, then all of the
1113         // supertraits it may depend on also must come from external
1114         // crates, and hence all of them already have their
1115         // super-predicates "converted" (and available from crate
1116         // meta-data), so there is no need to transitively test them.
1117         return Vec::new();
1118     };
1119
1120     let superpredicates = tcx.super_predicates.borrow().get(&trait_def_id).cloned();
1121     let superpredicates = superpredicates.unwrap_or_else(|| {
1122         let item = match ccx.tcx.map.get(trait_node_id) {
1123             hir_map::NodeItem(item) => item,
1124             _ => bug!("trait_node_id {} is not an item", trait_node_id)
1125         };
1126
1127         let (generics, bounds) = match item.node {
1128             hir::ItemTrait(_, ref generics, ref supertraits, _) => (generics, supertraits),
1129             _ => span_bug!(item.span,
1130                            "ensure_super_predicates_step invoked on non-trait"),
1131         };
1132
1133         // In-scope when converting the superbounds for `Trait` are
1134         // that `Self:Trait` as well as any bounds that appear on the
1135         // generic types:
1136         let trait_def = trait_def_of_item(ccx, item);
1137         let self_predicate = ty::GenericPredicates {
1138             parent: None,
1139             predicates: vec![trait_def.trait_ref.to_predicate()]
1140         };
1141         let scope = &(generics, &self_predicate);
1142
1143         // Convert the bounds that follow the colon, e.g. `Bar+Zed` in `trait Foo : Bar+Zed`.
1144         let self_param_ty = tcx.mk_self_type();
1145         let superbounds1 = compute_bounds(&ccx.icx(scope),
1146                                           self_param_ty,
1147                                           bounds,
1148                                           SizedByDefault::No,
1149                                           None,
1150                                           item.span);
1151
1152         let superbounds1 = superbounds1.predicates(tcx, self_param_ty);
1153
1154         // Convert any explicit superbounds in the where clause,
1155         // e.g. `trait Foo where Self : Bar`:
1156         let superbounds2 = generics.get_type_parameter_bounds(&ccx.icx(scope), item.span, item.id);
1157
1158         // Combine the two lists to form the complete set of superbounds:
1159         let superbounds = superbounds1.into_iter().chain(superbounds2).collect();
1160         let superpredicates = ty::GenericPredicates {
1161             parent: None,
1162             predicates: superbounds
1163         };
1164         debug!("superpredicates for trait {:?} = {:?}",
1165                tcx.map.local_def_id(item.id),
1166                superpredicates);
1167
1168         tcx.super_predicates.borrow_mut().insert(trait_def_id, superpredicates.clone());
1169
1170         superpredicates
1171     });
1172
1173     let def_ids: Vec<_> = superpredicates.predicates
1174                                          .iter()
1175                                          .filter_map(|p| p.to_opt_poly_trait_ref())
1176                                          .map(|tr| tr.def_id())
1177                                          .collect();
1178
1179     debug!("ensure_super_predicates_step: def_ids={:?}", def_ids);
1180
1181     def_ids
1182 }
1183
1184 fn trait_def_of_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1185                                it: &hir::Item)
1186                                -> &'tcx ty::TraitDef<'tcx>
1187 {
1188     let def_id = ccx.tcx.map.local_def_id(it.id);
1189     let tcx = ccx.tcx;
1190
1191     if let Some(def) = tcx.trait_defs.borrow().get(&def_id) {
1192         return def.clone();
1193     }
1194
1195     let (unsafety, generics) = match it.node {
1196         hir::ItemTrait(unsafety, ref generics, _, _) => {
1197             (unsafety, generics)
1198         }
1199         _ => span_bug!(it.span, "trait_def_of_item invoked on non-trait"),
1200     };
1201
1202     let paren_sugar = tcx.has_attr(def_id, "rustc_paren_sugar");
1203     if paren_sugar && !ccx.tcx.sess.features.borrow().unboxed_closures {
1204         let mut err = ccx.tcx.sess.struct_span_err(
1205             it.span,
1206             "the `#[rustc_paren_sugar]` attribute is a temporary means of controlling \
1207              which traits can use parenthetical notation");
1208         help!(&mut err,
1209             "add `#![feature(unboxed_closures)]` to \
1210              the crate attributes to use it");
1211         err.emit();
1212     }
1213
1214     let ty_generics = generics_of_def_id(ccx, def_id);
1215     let substs = mk_item_substs(&ccx.icx(generics), it.span, def_id);
1216
1217     let def_path_hash = tcx.def_path(def_id).deterministic_hash(tcx);
1218
1219     let trait_ref = ty::TraitRef::new(def_id, substs);
1220     let trait_def = ty::TraitDef::new(unsafety, paren_sugar, ty_generics, trait_ref,
1221                                       def_path_hash);
1222
1223     tcx.intern_trait_def(trait_def)
1224 }
1225
1226 fn convert_trait_predicates<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, it: &hir::Item) {
1227     let tcx = ccx.tcx;
1228     let trait_def = trait_def_of_item(ccx, it);
1229
1230     let def_id = ccx.tcx.map.local_def_id(it.id);
1231
1232     let (generics, items) = match it.node {
1233         hir::ItemTrait(_, ref generics, _, ref items) => (generics, items),
1234         ref s => {
1235             span_bug!(
1236                 it.span,
1237                 "trait_def_of_item invoked on {:?}",
1238                 s);
1239         }
1240     };
1241
1242     let super_predicates = ccx.tcx.item_super_predicates(def_id);
1243
1244     // `ty_generic_predicates` below will consider the bounds on the type
1245     // parameters (including `Self`) and the explicit where-clauses,
1246     // but to get the full set of predicates on a trait we need to add
1247     // in the supertrait bounds and anything declared on the
1248     // associated types.
1249     let mut base_predicates = super_predicates.predicates;
1250
1251     // Add in a predicate that `Self:Trait` (where `Trait` is the
1252     // current trait).  This is needed for builtin bounds.
1253     let self_predicate = trait_def.trait_ref.to_poly_trait_ref().to_predicate();
1254     base_predicates.push(self_predicate);
1255
1256     // add in the explicit where-clauses
1257     let mut trait_predicates =
1258         ty_generic_predicates(ccx, generics, None, base_predicates, true);
1259
1260     let assoc_predicates = predicates_for_associated_types(ccx,
1261                                                            generics,
1262                                                            &trait_predicates,
1263                                                            trait_def.trait_ref,
1264                                                            items);
1265     trait_predicates.predicates.extend(assoc_predicates);
1266
1267     let prev_predicates = tcx.predicates.borrow_mut().insert(def_id, trait_predicates);
1268     assert!(prev_predicates.is_none());
1269
1270     return;
1271
1272     fn predicates_for_associated_types<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1273                                                  ast_generics: &hir::Generics,
1274                                                  trait_predicates: &ty::GenericPredicates<'tcx>,
1275                                                  self_trait_ref: ty::TraitRef<'tcx>,
1276                                                  trait_items: &[hir::TraitItem])
1277                                                  -> Vec<ty::Predicate<'tcx>>
1278     {
1279         trait_items.iter().flat_map(|trait_item| {
1280             let bounds = match trait_item.node {
1281                 hir::TypeTraitItem(ref bounds, _) => bounds,
1282                 _ => {
1283                     return vec![].into_iter();
1284                 }
1285             };
1286
1287             let assoc_ty = ccx.tcx.mk_projection(self_trait_ref,
1288                                                  trait_item.name);
1289
1290             let bounds = compute_bounds(&ccx.icx(&(ast_generics, trait_predicates)),
1291                                         assoc_ty,
1292                                         bounds,
1293                                         SizedByDefault::Yes,
1294                                         None,
1295                                         trait_item.span);
1296
1297             bounds.predicates(ccx.tcx, assoc_ty).into_iter()
1298         }).collect()
1299     }
1300 }
1301
1302 fn generics_of_def_id<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1303                                 def_id: DefId)
1304                                 -> &'tcx ty::Generics<'tcx> {
1305     let tcx = ccx.tcx;
1306     let node_id = if let Some(id) = tcx.map.as_local_node_id(def_id) {
1307         id
1308     } else {
1309         return tcx.item_generics(def_id);
1310     };
1311     tcx.generics.memoize(def_id, || {
1312         use rustc::hir::map::*;
1313         use rustc::hir::*;
1314
1315         let node = tcx.map.get(node_id);
1316         let parent_def_id = match node {
1317             NodeImplItem(_) |
1318             NodeTraitItem(_) |
1319             NodeVariant(_) |
1320             NodeStructCtor(_) => {
1321                 let parent_id = tcx.map.get_parent(node_id);
1322                 Some(tcx.map.local_def_id(parent_id))
1323             }
1324             NodeTy(&hir::Ty { node: hir::TyImplTrait(..), .. }) => {
1325                 let mut parent_id = node_id;
1326                 loop {
1327                     match tcx.map.get(parent_id) {
1328                         NodeItem(_) | NodeImplItem(_) | NodeTraitItem(_) => break,
1329                         _ => {
1330                             parent_id = tcx.map.get_parent_node(parent_id);
1331                         }
1332                     }
1333                 }
1334                 Some(tcx.map.local_def_id(parent_id))
1335             }
1336             _ => None
1337         };
1338
1339         let mut opt_self = None;
1340         let mut allow_defaults = false;
1341
1342         let no_generics = hir::Generics::empty();
1343         let ast_generics = match node {
1344             NodeTraitItem(item) => {
1345                 match item.node {
1346                     MethodTraitItem(ref sig, _) => &sig.generics,
1347                     _ => &no_generics
1348                 }
1349             }
1350
1351             NodeImplItem(item) => {
1352                 match item.node {
1353                     ImplItemKind::Method(ref sig, _) => &sig.generics,
1354                     _ => &no_generics
1355                 }
1356             }
1357
1358             NodeItem(item) => {
1359                 match item.node {
1360                     ItemFn(.., ref generics, _) |
1361                     ItemImpl(_, _, ref generics, ..) => generics,
1362
1363                     ItemTy(_, ref generics) |
1364                     ItemEnum(_, ref generics) |
1365                     ItemStruct(_, ref generics) |
1366                     ItemUnion(_, ref generics) => {
1367                         allow_defaults = true;
1368                         generics
1369                     }
1370
1371                     ItemTrait(_, ref generics, ..) => {
1372                         // Add in the self type parameter.
1373                         //
1374                         // Something of a hack: use the node id for the trait, also as
1375                         // the node id for the Self type parameter.
1376                         let param_id = item.id;
1377
1378                         let parent = ccx.tcx.map.get_parent(param_id);
1379
1380                         let def = ty::TypeParameterDef {
1381                             index: 0,
1382                             name: keywords::SelfType.name(),
1383                             def_id: tcx.map.local_def_id(param_id),
1384                             default_def_id: tcx.map.local_def_id(parent),
1385                             default: None,
1386                             object_lifetime_default: ty::ObjectLifetimeDefault::BaseDefault,
1387                             pure_wrt_drop: false,
1388                         };
1389                         tcx.ty_param_defs.borrow_mut().insert(param_id, def.clone());
1390                         opt_self = Some(def);
1391
1392                         allow_defaults = true;
1393                         generics
1394                     }
1395
1396                     _ => &no_generics
1397                 }
1398             }
1399
1400             NodeForeignItem(item) => {
1401                 match item.node {
1402                     ForeignItemStatic(..) => &no_generics,
1403                     ForeignItemFn(_, ref generics) => generics
1404                 }
1405             }
1406
1407             _ => &no_generics
1408         };
1409
1410         let has_self = opt_self.is_some();
1411         let mut parent_has_self = false;
1412         let mut own_start = has_self as u32;
1413         let (parent_regions, parent_types) = parent_def_id.map_or((0, 0), |def_id| {
1414             let generics = generics_of_def_id(ccx, def_id);
1415             assert_eq!(has_self, false);
1416             parent_has_self = generics.has_self;
1417             own_start = generics.count() as u32;
1418             (generics.parent_regions + generics.regions.len() as u32,
1419              generics.parent_types + generics.types.len() as u32)
1420         });
1421
1422         let early_lifetimes = early_bound_lifetimes_from_generics(ccx, ast_generics);
1423         let regions = early_lifetimes.iter().enumerate().map(|(i, l)| {
1424             ty::RegionParameterDef {
1425                 name: l.lifetime.name,
1426                 index: own_start + i as u32,
1427                 def_id: tcx.map.local_def_id(l.lifetime.id),
1428                 bounds: l.bounds.iter().map(|l| {
1429                     ast_region_to_region(tcx, l)
1430                 }).collect(),
1431                 pure_wrt_drop: l.pure_wrt_drop,
1432             }
1433         }).collect::<Vec<_>>();
1434
1435         // Now create the real type parameters.
1436         let type_start = own_start + regions.len() as u32;
1437         let types = ast_generics.ty_params.iter().enumerate().map(|(i, p)| {
1438             let i = type_start + i as u32;
1439             get_or_create_type_parameter_def(ccx, ast_generics, i, p, allow_defaults)
1440         });
1441         let types: Vec<_> = opt_self.into_iter().chain(types).collect();
1442
1443         // Debugging aid.
1444         if tcx.has_attr(def_id, "rustc_object_lifetime_default") {
1445             let object_lifetime_default_reprs: String =
1446                 types.iter().map(|t| {
1447                     match t.object_lifetime_default {
1448                         ty::ObjectLifetimeDefault::Specific(r) => r.to_string(),
1449                         d => format!("{:?}", d),
1450                     }
1451                 }).collect::<Vec<String>>().join(",");
1452             tcx.sess.span_err(tcx.map.span(node_id), &object_lifetime_default_reprs);
1453         }
1454
1455         tcx.alloc_generics(ty::Generics {
1456             parent: parent_def_id,
1457             parent_regions: parent_regions,
1458             parent_types: parent_types,
1459             regions: regions,
1460             types: types,
1461             has_self: has_self || parent_has_self
1462         })
1463     })
1464 }
1465
1466 fn type_of_def_id<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1467                             def_id: DefId)
1468                             -> Ty<'tcx> {
1469     let node_id = if let Some(id) = ccx.tcx.map.as_local_node_id(def_id) {
1470         id
1471     } else {
1472         return ccx.tcx.item_type(def_id);
1473     };
1474     ccx.tcx.item_types.memoize(def_id, || {
1475         use rustc::hir::map::*;
1476         use rustc::hir::*;
1477
1478         // Alway bring in generics, as computing the type needs them.
1479         generics_of_def_id(ccx, def_id);
1480
1481         let ty = match ccx.tcx.map.get(node_id) {
1482             NodeItem(item) => {
1483                 match item.node {
1484                     ItemStatic(ref t, ..) | ItemConst(ref t, _) => {
1485                         ccx.icx(&()).to_ty(&StaticRscope::new(&ccx.tcx), &t)
1486                     }
1487                     ItemFn(ref decl, unsafety, _, abi, ref generics, _) => {
1488                         let tofd = AstConv::ty_of_bare_fn(&ccx.icx(generics), unsafety, abi, &decl,
1489                                                           Some(AnonTypeScope::new(def_id)));
1490                         let substs = mk_item_substs(&ccx.icx(generics), item.span, def_id);
1491                         ccx.tcx.mk_fn_def(def_id, substs, tofd)
1492                     }
1493                     ItemTy(ref t, ref generics) => {
1494                         ccx.icx(generics).to_ty(&ExplicitRscope, &t)
1495                     }
1496                     ItemEnum(ref ei, ref generics) => {
1497                         let def = convert_enum_def(ccx, item, ei);
1498                         let substs = mk_item_substs(&ccx.icx(generics), item.span, def_id);
1499                         ccx.tcx.mk_adt(def, substs)
1500                     }
1501                     ItemStruct(ref si, ref generics) => {
1502                         let def = convert_struct_def(ccx, item, si);
1503                         let substs = mk_item_substs(&ccx.icx(generics), item.span, def_id);
1504                         ccx.tcx.mk_adt(def, substs)
1505                     }
1506                     ItemUnion(ref un, ref generics) => {
1507                         let def = convert_union_def(ccx, item, un);
1508                         let substs = mk_item_substs(&ccx.icx(generics), item.span, def_id);
1509                         ccx.tcx.mk_adt(def, substs)
1510                     }
1511                     ItemDefaultImpl(..) |
1512                     ItemTrait(..) |
1513                     ItemImpl(..) |
1514                     ItemMod(..) |
1515                     ItemForeignMod(..) |
1516                     ItemExternCrate(..) |
1517                     ItemUse(..) => {
1518                         span_bug!(
1519                             item.span,
1520                             "compute_type_of_item: unexpected item type: {:?}",
1521                             item.node);
1522                     }
1523                 }
1524             }
1525             NodeForeignItem(foreign_item) => {
1526                 let abi = ccx.tcx.map.get_foreign_abi(node_id);
1527
1528                 match foreign_item.node {
1529                     ForeignItemFn(ref fn_decl, ref generics) => {
1530                         compute_type_of_foreign_fn_decl(
1531                             ccx, ccx.tcx.map.local_def_id(foreign_item.id),
1532                             fn_decl, generics, abi)
1533                     }
1534                     ForeignItemStatic(ref t, _) => {
1535                         ccx.icx(&()).to_ty(&ExplicitRscope, t)
1536                     }
1537                 }
1538             }
1539             NodeExpr(&hir::Expr { node: hir::ExprClosure(..), .. }) => {
1540                 ccx.tcx.mk_closure(def_id, Substs::for_item(
1541                     ccx.tcx, def_id,
1542                     |def, _| ccx.tcx.mk_region(def.to_early_bound_region()),
1543                     |def, _| ccx.tcx.mk_param_from_def(def)
1544                 ))
1545             }
1546             x => {
1547                 bug!("unexpected sort of node in type_of_def_id(): {:?}", x);
1548             }
1549         };
1550
1551         ty
1552     })
1553 }
1554
1555 fn predicates_of_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1556                                 it: &hir::Item)
1557                                 -> ty::GenericPredicates<'tcx> {
1558     let def_id = ccx.tcx.map.local_def_id(it.id);
1559
1560     let no_generics = hir::Generics::empty();
1561     let generics = match it.node {
1562         hir::ItemFn(.., ref generics, _) |
1563         hir::ItemTy(_, ref generics) |
1564         hir::ItemEnum(_, ref generics) |
1565         hir::ItemStruct(_, ref generics) |
1566         hir::ItemUnion(_, ref generics) => generics,
1567         _ => &no_generics
1568     };
1569
1570     let predicates = ty_generic_predicates(ccx, generics, None, vec![], false);
1571     let prev_predicates = ccx.tcx.predicates.borrow_mut().insert(def_id,
1572                                                                  predicates.clone());
1573     assert!(prev_predicates.is_none());
1574
1575     predicates
1576 }
1577
1578 fn convert_foreign_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1579                                   it: &hir::ForeignItem)
1580 {
1581     // For reasons I cannot fully articulate, I do so hate the AST
1582     // map, and I regard each time that I use it as a personal and
1583     // moral failing, but at the moment it seems like the only
1584     // convenient way to extract the ABI. - ndm
1585     let def_id = ccx.tcx.map.local_def_id(it.id);
1586     type_of_def_id(ccx, def_id);
1587     generics_of_def_id(ccx, def_id);
1588
1589     let no_generics = hir::Generics::empty();
1590     let generics = match it.node {
1591         hir::ForeignItemFn(_, ref generics) => generics,
1592         hir::ForeignItemStatic(..) => &no_generics
1593     };
1594
1595     let predicates = ty_generic_predicates(ccx, generics, None, vec![], false);
1596     let prev_predicates = ccx.tcx.predicates.borrow_mut().insert(def_id, predicates);
1597     assert!(prev_predicates.is_none());
1598 }
1599
1600 // Add the Sized bound, unless the type parameter is marked as `?Sized`.
1601 fn add_unsized_bound<'gcx: 'tcx, 'tcx>(astconv: &AstConv<'gcx, 'tcx>,
1602                                        bounds: &mut ty::BuiltinBounds,
1603                                        ast_bounds: &[hir::TyParamBound],
1604                                        span: Span)
1605 {
1606     let tcx = astconv.tcx();
1607
1608     // Try to find an unbound in bounds.
1609     let mut unbound = None;
1610     for ab in ast_bounds {
1611         if let &hir::TraitTyParamBound(ref ptr, hir::TraitBoundModifier::Maybe) = ab  {
1612             if unbound.is_none() {
1613                 assert!(ptr.bound_lifetimes.is_empty());
1614                 unbound = Some(ptr.trait_ref.clone());
1615             } else {
1616                 span_err!(tcx.sess, span, E0203,
1617                           "type parameter has more than one relaxed default \
1618                                                 bound, only one is supported");
1619             }
1620         }
1621     }
1622
1623     let kind_id = tcx.lang_items.require(SizedTraitLangItem);
1624     match unbound {
1625         Some(ref tpb) => {
1626             // FIXME(#8559) currently requires the unbound to be built-in.
1627             if let Ok(kind_id) = kind_id {
1628                 let trait_def = tcx.expect_def(tpb.ref_id);
1629                 if trait_def != Def::Trait(kind_id) {
1630                     tcx.sess.span_warn(span,
1631                                        "default bound relaxed for a type parameter, but \
1632                                        this does nothing because the given bound is not \
1633                                        a default. Only `?Sized` is supported");
1634                     tcx.try_add_builtin_trait(kind_id, bounds);
1635                 }
1636             }
1637         }
1638         _ if kind_id.is_ok() => {
1639             tcx.try_add_builtin_trait(kind_id.unwrap(), bounds);
1640         }
1641         // No lang item for Sized, so we can't add it as a bound.
1642         None => {}
1643     }
1644 }
1645
1646 /// Returns the early-bound lifetimes declared in this generics
1647 /// listing.  For anything other than fns/methods, this is just all
1648 /// the lifetimes that are declared. For fns or methods, we have to
1649 /// screen out those that do not appear in any where-clauses etc using
1650 /// `resolve_lifetime::early_bound_lifetimes`.
1651 fn early_bound_lifetimes_from_generics<'a, 'tcx, 'hir>(
1652     ccx: &CrateCtxt<'a, 'tcx>,
1653     ast_generics: &'hir hir::Generics)
1654     -> Vec<&'hir hir::LifetimeDef>
1655 {
1656     ast_generics
1657         .lifetimes
1658         .iter()
1659         .filter(|l| !ccx.tcx.named_region_map.late_bound.contains_key(&l.lifetime.id))
1660         .collect()
1661 }
1662
1663 fn ty_generic_predicates<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1664                                   ast_generics: &hir::Generics,
1665                                   parent: Option<DefId>,
1666                                   super_predicates: Vec<ty::Predicate<'tcx>>,
1667                                   has_self: bool)
1668                                   -> ty::GenericPredicates<'tcx>
1669 {
1670     let tcx = ccx.tcx;
1671     let parent_count = parent.map_or(0, |def_id| {
1672         let generics = generics_of_def_id(ccx, def_id);
1673         assert_eq!(generics.parent, None);
1674         assert_eq!(generics.parent_regions, 0);
1675         assert_eq!(generics.parent_types, 0);
1676         generics.count() as u32
1677     });
1678     let ref base_predicates = match parent {
1679         Some(def_id) => {
1680             assert_eq!(super_predicates, vec![]);
1681             tcx.item_predicates(def_id)
1682         }
1683         None => {
1684             ty::GenericPredicates {
1685                 parent: None,
1686                 predicates: super_predicates.clone()
1687             }
1688         }
1689     };
1690     let mut predicates = super_predicates;
1691
1692     // Collect the region predicates that were declared inline as
1693     // well. In the case of parameters declared on a fn or method, we
1694     // have to be careful to only iterate over early-bound regions.
1695     let own_start = parent_count + has_self as u32;
1696     let early_lifetimes = early_bound_lifetimes_from_generics(ccx, ast_generics);
1697     for (index, param) in early_lifetimes.iter().enumerate() {
1698         let index = own_start + index as u32;
1699         let region = ccx.tcx.mk_region(ty::ReEarlyBound(ty::EarlyBoundRegion {
1700             index: index,
1701             name: param.lifetime.name
1702         }));
1703         for bound in &param.bounds {
1704             let bound_region = ast_region_to_region(ccx.tcx, bound);
1705             let outlives = ty::Binder(ty::OutlivesPredicate(region, bound_region));
1706             predicates.push(outlives.to_predicate());
1707         }
1708     }
1709
1710     // Collect the predicates that were written inline by the user on each
1711     // type parameter (e.g., `<T:Foo>`).
1712     let type_start = own_start + early_lifetimes.len() as u32;
1713     for (index, param) in ast_generics.ty_params.iter().enumerate() {
1714         let index = type_start + index as u32;
1715         let param_ty = ty::ParamTy::new(index, param.name).to_ty(ccx.tcx);
1716         let bounds = compute_bounds(&ccx.icx(&(base_predicates, ast_generics)),
1717                                     param_ty,
1718                                     &param.bounds,
1719                                     SizedByDefault::Yes,
1720                                     None,
1721                                     param.span);
1722         predicates.extend(bounds.predicates(ccx.tcx, param_ty));
1723     }
1724
1725     // Add in the bounds that appear in the where-clause
1726     let where_clause = &ast_generics.where_clause;
1727     for predicate in &where_clause.predicates {
1728         match predicate {
1729             &hir::WherePredicate::BoundPredicate(ref bound_pred) => {
1730                 let ty = AstConv::ast_ty_to_ty(&ccx.icx(&(base_predicates, ast_generics)),
1731                                                &ExplicitRscope,
1732                                                &bound_pred.bounded_ty);
1733
1734                 for bound in bound_pred.bounds.iter() {
1735                     match bound {
1736                         &hir::TyParamBound::TraitTyParamBound(ref poly_trait_ref, _) => {
1737                             let mut projections = Vec::new();
1738
1739                             let trait_ref =
1740                                 AstConv::instantiate_poly_trait_ref(&ccx.icx(&(base_predicates,
1741                                                                                ast_generics)),
1742                                                                     &ExplicitRscope,
1743                                                                     poly_trait_ref,
1744                                                                     ty,
1745                                                                     &mut projections);
1746
1747                             predicates.push(trait_ref.to_predicate());
1748
1749                             for projection in &projections {
1750                                 predicates.push(projection.to_predicate());
1751                             }
1752                         }
1753
1754                         &hir::TyParamBound::RegionTyParamBound(ref lifetime) => {
1755                             let region = ast_region_to_region(tcx, lifetime);
1756                             let pred = ty::Binder(ty::OutlivesPredicate(ty, region));
1757                             predicates.push(ty::Predicate::TypeOutlives(pred))
1758                         }
1759                     }
1760                 }
1761             }
1762
1763             &hir::WherePredicate::RegionPredicate(ref region_pred) => {
1764                 let r1 = ast_region_to_region(tcx, &region_pred.lifetime);
1765                 for bound in &region_pred.bounds {
1766                     let r2 = ast_region_to_region(tcx, bound);
1767                     let pred = ty::Binder(ty::OutlivesPredicate(r1, r2));
1768                     predicates.push(ty::Predicate::RegionOutlives(pred))
1769                 }
1770             }
1771
1772             &hir::WherePredicate::EqPredicate(ref eq_pred) => {
1773                 // FIXME(#20041)
1774                 span_bug!(eq_pred.span,
1775                          "Equality constraints are not yet \
1776                           implemented (#20041)")
1777             }
1778         }
1779     }
1780
1781     ty::GenericPredicates {
1782         parent: parent,
1783         predicates: predicates
1784     }
1785 }
1786
1787 fn get_or_create_type_parameter_def<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1788                                              ast_generics: &hir::Generics,
1789                                              index: u32,
1790                                              param: &hir::TyParam,
1791                                              allow_defaults: bool)
1792                                              -> ty::TypeParameterDef<'tcx>
1793 {
1794     let tcx = ccx.tcx;
1795     match tcx.ty_param_defs.borrow().get(&param.id) {
1796         Some(d) => { return d.clone(); }
1797         None => { }
1798     }
1799
1800     let default =
1801         param.default.as_ref().map(|def| ccx.icx(&()).to_ty(&ExplicitRscope, def));
1802
1803     let object_lifetime_default =
1804         compute_object_lifetime_default(ccx, param.id,
1805                                         &param.bounds, &ast_generics.where_clause);
1806
1807     let parent = tcx.map.get_parent(param.id);
1808
1809     if !allow_defaults && default.is_some() {
1810         if !tcx.sess.features.borrow().default_type_parameter_fallback {
1811             tcx.sess.add_lint(
1812                 lint::builtin::INVALID_TYPE_PARAM_DEFAULT,
1813                 param.id,
1814                 param.span,
1815                 format!("defaults for type parameters are only allowed in `struct`, \
1816                          `enum`, `type`, or `trait` definitions."));
1817         }
1818     }
1819
1820     let def = ty::TypeParameterDef {
1821         index: index,
1822         name: param.name,
1823         def_id: ccx.tcx.map.local_def_id(param.id),
1824         default_def_id: ccx.tcx.map.local_def_id(parent),
1825         default: default,
1826         object_lifetime_default: object_lifetime_default,
1827         pure_wrt_drop: param.pure_wrt_drop,
1828     };
1829
1830     if def.name == keywords::SelfType.name() {
1831         span_bug!(param.span, "`Self` should not be the name of a regular parameter");
1832     }
1833
1834     tcx.ty_param_defs.borrow_mut().insert(param.id, def.clone());
1835
1836     debug!("get_or_create_type_parameter_def: def for type param: {:?}", def);
1837
1838     def
1839 }
1840
1841 /// Scan the bounds and where-clauses on a parameter to extract bounds
1842 /// of the form `T:'a` so as to determine the `ObjectLifetimeDefault`.
1843 /// This runs as part of computing the minimal type scheme, so we
1844 /// intentionally avoid just asking astconv to convert all the where
1845 /// clauses into a `ty::Predicate`. This is because that could induce
1846 /// artificial cycles.
1847 fn compute_object_lifetime_default<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1848                                             param_id: ast::NodeId,
1849                                             param_bounds: &[hir::TyParamBound],
1850                                             where_clause: &hir::WhereClause)
1851                                             -> ty::ObjectLifetimeDefault<'tcx>
1852 {
1853     let inline_bounds = from_bounds(ccx, param_bounds);
1854     let where_bounds = from_predicates(ccx, param_id, &where_clause.predicates);
1855     let all_bounds: FxHashSet<_> = inline_bounds.into_iter()
1856                                                 .chain(where_bounds)
1857                                                 .collect();
1858     return if all_bounds.len() > 1 {
1859         ty::ObjectLifetimeDefault::Ambiguous
1860     } else if all_bounds.len() == 0 {
1861         ty::ObjectLifetimeDefault::BaseDefault
1862     } else {
1863         ty::ObjectLifetimeDefault::Specific(
1864             all_bounds.into_iter().next().unwrap())
1865     };
1866
1867     fn from_bounds<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1868                             bounds: &[hir::TyParamBound])
1869                             -> Vec<&'tcx ty::Region>
1870     {
1871         bounds.iter()
1872               .filter_map(|bound| {
1873                   match *bound {
1874                       hir::TraitTyParamBound(..) =>
1875                           None,
1876                       hir::RegionTyParamBound(ref lifetime) =>
1877                           Some(ast_region_to_region(ccx.tcx, lifetime)),
1878                   }
1879               })
1880               .collect()
1881     }
1882
1883     fn from_predicates<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1884                                 param_id: ast::NodeId,
1885                                 predicates: &[hir::WherePredicate])
1886                                 -> Vec<&'tcx ty::Region>
1887     {
1888         predicates.iter()
1889                   .flat_map(|predicate| {
1890                       match *predicate {
1891                           hir::WherePredicate::BoundPredicate(ref data) => {
1892                               if data.bound_lifetimes.is_empty() &&
1893                                   is_param(ccx.tcx, &data.bounded_ty, param_id)
1894                               {
1895                                   from_bounds(ccx, &data.bounds).into_iter()
1896                               } else {
1897                                   Vec::new().into_iter()
1898                               }
1899                           }
1900                           hir::WherePredicate::RegionPredicate(..) |
1901                           hir::WherePredicate::EqPredicate(..) => {
1902                               Vec::new().into_iter()
1903                           }
1904                       }
1905                   })
1906                   .collect()
1907     }
1908 }
1909
1910 pub enum SizedByDefault { Yes, No, }
1911
1912 /// Translate the AST's notion of ty param bounds (which are an enum consisting of a newtyped Ty or
1913 /// a region) to ty's notion of ty param bounds, which can either be user-defined traits, or the
1914 /// built-in trait (formerly known as kind): Send.
1915 pub fn compute_bounds<'gcx: 'tcx, 'tcx>(astconv: &AstConv<'gcx, 'tcx>,
1916                                         param_ty: ty::Ty<'tcx>,
1917                                         ast_bounds: &[hir::TyParamBound],
1918                                         sized_by_default: SizedByDefault,
1919                                         anon_scope: Option<AnonTypeScope>,
1920                                         span: Span)
1921                                         -> Bounds<'tcx>
1922 {
1923     let tcx = astconv.tcx();
1924     let PartitionedBounds {
1925         mut builtin_bounds,
1926         trait_bounds,
1927         region_bounds
1928     } = partition_bounds(tcx, span, &ast_bounds);
1929
1930     if let SizedByDefault::Yes = sized_by_default {
1931         add_unsized_bound(astconv, &mut builtin_bounds, ast_bounds, span);
1932     }
1933
1934     let mut projection_bounds = vec![];
1935
1936     let rscope = MaybeWithAnonTypes::new(ExplicitRscope, anon_scope);
1937     let mut trait_bounds: Vec<_> = trait_bounds.iter().map(|&bound| {
1938         astconv.instantiate_poly_trait_ref(&rscope,
1939                                            bound,
1940                                            param_ty,
1941                                            &mut projection_bounds)
1942     }).collect();
1943
1944     let region_bounds = region_bounds.into_iter().map(|r| {
1945         ast_region_to_region(tcx, r)
1946     }).collect();
1947
1948     trait_bounds.sort_by(|a,b| a.def_id().cmp(&b.def_id()));
1949
1950     Bounds {
1951         region_bounds: region_bounds,
1952         builtin_bounds: builtin_bounds,
1953         trait_bounds: trait_bounds,
1954         projection_bounds: projection_bounds,
1955     }
1956 }
1957
1958 /// Converts a specific TyParamBound from the AST into a set of
1959 /// predicates that apply to the self-type. A vector is returned
1960 /// because this can be anywhere from 0 predicates (`T:?Sized` adds no
1961 /// predicates) to 1 (`T:Foo`) to many (`T:Bar<X=i32>` adds `T:Bar`
1962 /// and `<T as Bar>::X == i32`).
1963 fn predicates_from_bound<'tcx>(astconv: &AstConv<'tcx, 'tcx>,
1964                                param_ty: Ty<'tcx>,
1965                                bound: &hir::TyParamBound)
1966                                -> Vec<ty::Predicate<'tcx>>
1967 {
1968     match *bound {
1969         hir::TraitTyParamBound(ref tr, hir::TraitBoundModifier::None) => {
1970             let mut projections = Vec::new();
1971             let pred = astconv.instantiate_poly_trait_ref(&ExplicitRscope,
1972                                                           tr,
1973                                                           param_ty,
1974                                                           &mut projections);
1975             projections.into_iter()
1976                        .map(|p| p.to_predicate())
1977                        .chain(Some(pred.to_predicate()))
1978                        .collect()
1979         }
1980         hir::RegionTyParamBound(ref lifetime) => {
1981             let region = ast_region_to_region(astconv.tcx(), lifetime);
1982             let pred = ty::Binder(ty::OutlivesPredicate(param_ty, region));
1983             vec![ty::Predicate::TypeOutlives(pred)]
1984         }
1985         hir::TraitTyParamBound(_, hir::TraitBoundModifier::Maybe) => {
1986             Vec::new()
1987         }
1988     }
1989 }
1990
1991 fn compute_type_of_foreign_fn_decl<'a, 'tcx>(
1992     ccx: &CrateCtxt<'a, 'tcx>,
1993     def_id: DefId,
1994     decl: &hir::FnDecl,
1995     ast_generics: &hir::Generics,
1996     abi: abi::Abi)
1997     -> Ty<'tcx>
1998 {
1999     let rb = BindingRscope::new();
2000     let input_tys = decl.inputs
2001                         .iter()
2002                         .map(|a| AstConv::ty_of_arg(&ccx.icx(ast_generics), &rb, a, None))
2003                         .collect::<Vec<_>>();
2004
2005     let output = match decl.output {
2006         hir::Return(ref ty) =>
2007             AstConv::ast_ty_to_ty(&ccx.icx(ast_generics), &rb, &ty),
2008         hir::DefaultReturn(..) =>
2009             ccx.tcx.mk_nil(),
2010     };
2011
2012     // feature gate SIMD types in FFI, since I (huonw) am not sure the
2013     // ABIs are handled at all correctly.
2014     if abi != abi::Abi::RustIntrinsic && abi != abi::Abi::PlatformIntrinsic
2015             && !ccx.tcx.sess.features.borrow().simd_ffi {
2016         let check = |ast_ty: &hir::Ty, ty: ty::Ty| {
2017             if ty.is_simd() {
2018                 ccx.tcx.sess.struct_span_err(ast_ty.span,
2019                               &format!("use of SIMD type `{}` in FFI is highly experimental and \
2020                                         may result in invalid code",
2021                                        pprust::ty_to_string(ast_ty)))
2022                     .help("add #![feature(simd_ffi)] to the crate attributes to enable")
2023                     .emit();
2024             }
2025         };
2026         for (input, ty) in decl.inputs.iter().zip(&input_tys) {
2027             check(&input.ty, ty)
2028         }
2029         if let hir::Return(ref ty) = decl.output {
2030             check(&ty, output)
2031         }
2032     }
2033
2034     let id = ccx.tcx.map.as_local_node_id(def_id).unwrap();
2035     let substs = mk_item_substs(&ccx.icx(ast_generics), ccx.tcx.map.span(id), def_id);
2036     ccx.tcx.mk_fn_def(def_id, substs, ccx.tcx.mk_bare_fn(ty::BareFnTy {
2037         abi: abi,
2038         unsafety: hir::Unsafety::Unsafe,
2039         sig: ty::Binder(ty::FnSig {inputs: input_tys,
2040                                     output: output,
2041                                     variadic: decl.variadic}),
2042     }))
2043 }
2044
2045 pub fn mk_item_substs<'gcx: 'tcx, 'tcx>(astconv: &AstConv<'gcx, 'tcx>,
2046                                         span: Span,
2047                                         def_id: DefId)
2048                                         -> &'tcx Substs<'tcx> {
2049     let tcx = astconv.tcx();
2050     // FIXME(eddyb) Do this request from Substs::for_item in librustc.
2051     if let Err(ErrorReported) = astconv.get_generics(span, def_id) {
2052         // No convenient way to recover from a cycle here. Just bail. Sorry!
2053         tcx.sess.abort_if_errors();
2054         bug!("ErrorReported returned, but no errors reports?")
2055     }
2056
2057     Substs::for_item(tcx, def_id,
2058                      |def, _| tcx.mk_region(def.to_early_bound_region()),
2059                      |def, _| tcx.mk_param_from_def(def))
2060 }