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