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};
  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     if let Some(ctor_id) = ctor_id {
1011         // Make adt definition available through constructor id as well.
1012         ccx.tcx.adt_defs.borrow_mut().insert(ctor_id, adt);
1013     }
1014
1015     ccx.tcx.adt_defs.borrow_mut().insert(did, adt);
1016     adt
1017 }
1018
1019 fn convert_union_def<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1020                                 it: &hir::Item,
1021                                 def: &hir::VariantData)
1022                                 -> &'tcx ty::AdtDef
1023 {
1024     let did = ccx.tcx.hir.local_def_id(it.id);
1025     let variants = vec![convert_struct_variant(ccx, did, it.name, ConstInt::Infer(0), def)];
1026
1027     let adt = ccx.tcx.alloc_adt_def(did, AdtKind::Union, variants);
1028     ccx.tcx.adt_defs.borrow_mut().insert(did, adt);
1029     adt
1030 }
1031
1032     fn evaluate_disr_expr(ccx: &CrateCtxt, repr_ty: attr::IntType, body: hir::BodyId)
1033                           -> Option<ty::Disr> {
1034         let e = &ccx.tcx.hir.body(body).value;
1035         debug!("disr expr, checking {}", ccx.tcx.hir.node_to_pretty_string(e.id));
1036
1037         let ty_hint = repr_ty.to_ty(ccx.tcx);
1038         let print_err = |cv: ConstVal| {
1039             struct_span_err!(ccx.tcx.sess, e.span, E0079, "mismatched types")
1040                 .note_expected_found(&"type", &ty_hint, &format!("{}", cv.description()))
1041                 .span_label(e.span, &format!("expected '{}' type", ty_hint))
1042                 .emit();
1043         };
1044
1045         let hint = UncheckedExprHint(ty_hint);
1046         match ConstContext::new(ccx.tcx, body).eval(e, hint) {
1047             Ok(ConstVal::Integral(i)) => {
1048                 // FIXME: eval should return an error if the hint is wrong
1049                 match (repr_ty, i) {
1050                     (attr::SignedInt(ast::IntTy::I8), ConstInt::I8(_)) |
1051                     (attr::SignedInt(ast::IntTy::I16), ConstInt::I16(_)) |
1052                     (attr::SignedInt(ast::IntTy::I32), ConstInt::I32(_)) |
1053                     (attr::SignedInt(ast::IntTy::I64), ConstInt::I64(_)) |
1054                     (attr::SignedInt(ast::IntTy::I128), ConstInt::I128(_)) |
1055                     (attr::SignedInt(ast::IntTy::Is), ConstInt::Isize(_)) |
1056                     (attr::UnsignedInt(ast::UintTy::U8), ConstInt::U8(_)) |
1057                     (attr::UnsignedInt(ast::UintTy::U16), ConstInt::U16(_)) |
1058                     (attr::UnsignedInt(ast::UintTy::U32), ConstInt::U32(_)) |
1059                     (attr::UnsignedInt(ast::UintTy::U64), ConstInt::U64(_)) |
1060                     (attr::UnsignedInt(ast::UintTy::U128), ConstInt::U128(_)) |
1061                     (attr::UnsignedInt(ast::UintTy::Us), ConstInt::Usize(_)) => Some(i),
1062                     (_, i) => {
1063                         print_err(ConstVal::Integral(i));
1064                         None
1065                     },
1066                 }
1067             },
1068             Ok(cv) => {
1069                 print_err(cv);
1070                 None
1071             },
1072             // enum variant evaluation happens before the global constant check
1073             // so we need to report the real error
1074             Err(err) => {
1075                 let mut diag = report_const_eval_err(
1076                     ccx.tcx, &err, e.span, "enum discriminant");
1077                 diag.emit();
1078                 None
1079             }
1080         }
1081     }
1082
1083 fn convert_enum_def<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1084                               it: &hir::Item,
1085                               def: &hir::EnumDef)
1086                               -> &'tcx ty::AdtDef
1087 {
1088     let tcx = ccx.tcx;
1089     let did = tcx.hir.local_def_id(it.id);
1090     let repr_hints = tcx.lookup_repr_hints(did);
1091     let repr_type = tcx.enum_repr_type(repr_hints.get(0));
1092     let initial = repr_type.initial_discriminant(tcx);
1093     let mut prev_disr = None::<ty::Disr>;
1094     let variants = def.variants.iter().map(|v| {
1095         let wrapped_disr = prev_disr.map_or(initial, |d| d.wrap_incr());
1096         let disr = if let Some(e) = v.node.disr_expr {
1097             evaluate_disr_expr(ccx, repr_type, e)
1098         } else if let Some(disr) = repr_type.disr_incr(tcx, prev_disr) {
1099             Some(disr)
1100         } else {
1101             struct_span_err!(tcx.sess, v.span, E0370,
1102                              "enum discriminant overflowed")
1103                 .span_label(v.span, &format!("overflowed on value after {}", prev_disr.unwrap()))
1104                 .note(&format!("explicitly set `{} = {}` if that is desired outcome",
1105                                v.node.name, wrapped_disr))
1106                 .emit();
1107             None
1108         }.unwrap_or(wrapped_disr);
1109         prev_disr = Some(disr);
1110
1111         let did = tcx.hir.local_def_id(v.node.data.id());
1112         convert_struct_variant(ccx, did, v.node.name, disr, &v.node.data)
1113     }).collect();
1114
1115     let adt = tcx.alloc_adt_def(did, AdtKind::Enum, variants);
1116     tcx.adt_defs.borrow_mut().insert(did, adt);
1117     adt
1118 }
1119
1120 /// Ensures that the super-predicates of the trait with def-id
1121 /// trait_def_id are converted and stored. This does NOT ensure that
1122 /// the transitive super-predicates are converted; that is the job of
1123 /// the `ensure_super_predicates()` method in the `AstConv` impl
1124 /// above. Returns a list of trait def-ids that must be ensured as
1125 /// well to guarantee that the transitive superpredicates are
1126 /// converted.
1127 fn ensure_super_predicates_step(ccx: &CrateCtxt,
1128                                 trait_def_id: DefId)
1129                                 -> Vec<DefId>
1130 {
1131     let tcx = ccx.tcx;
1132
1133     debug!("ensure_super_predicates_step(trait_def_id={:?})", trait_def_id);
1134
1135     let trait_node_id = if let Some(n) = tcx.hir.as_local_node_id(trait_def_id) {
1136         n
1137     } else {
1138         // If this trait comes from an external crate, then all of the
1139         // supertraits it may depend on also must come from external
1140         // crates, and hence all of them already have their
1141         // super-predicates "converted" (and available from crate
1142         // meta-data), so there is no need to transitively test them.
1143         return Vec::new();
1144     };
1145
1146     let superpredicates = tcx.super_predicates.borrow().get(&trait_def_id).cloned();
1147     let superpredicates = superpredicates.unwrap_or_else(|| {
1148         let item = match ccx.tcx.hir.get(trait_node_id) {
1149             hir_map::NodeItem(item) => item,
1150             _ => bug!("trait_node_id {} is not an item", trait_node_id)
1151         };
1152
1153         let (generics, bounds) = match item.node {
1154             hir::ItemTrait(_, ref generics, ref supertraits, _) => (generics, supertraits),
1155             _ => span_bug!(item.span,
1156                            "ensure_super_predicates_step invoked on non-trait"),
1157         };
1158
1159         // In-scope when converting the superbounds for `Trait` are
1160         // that `Self:Trait` as well as any bounds that appear on the
1161         // generic types:
1162         generics_of_def_id(ccx, trait_def_id);
1163         trait_def_of_item(ccx, item);
1164         let trait_ref = ty::TraitRef {
1165             def_id: trait_def_id,
1166             substs: Substs::identity_for_item(tcx, trait_def_id)
1167         };
1168         let self_predicate = ty::GenericPredicates {
1169             parent: None,
1170             predicates: vec![trait_ref.to_predicate()]
1171         };
1172         let scope = &(generics, &self_predicate);
1173
1174         // Convert the bounds that follow the colon, e.g. `Bar+Zed` in `trait Foo : Bar+Zed`.
1175         let self_param_ty = tcx.mk_self_type();
1176         let superbounds1 = compute_bounds(&ccx.icx(scope),
1177                                           self_param_ty,
1178                                           bounds,
1179                                           SizedByDefault::No,
1180                                           item.span);
1181
1182         let superbounds1 = superbounds1.predicates(tcx, self_param_ty);
1183
1184         // Convert any explicit superbounds in the where clause,
1185         // e.g. `trait Foo where Self : Bar`:
1186         let superbounds2 = generics.get_type_parameter_bounds(&ccx.icx(scope), item.span, item.id);
1187
1188         // Combine the two lists to form the complete set of superbounds:
1189         let superbounds = superbounds1.into_iter().chain(superbounds2).collect();
1190         let superpredicates = ty::GenericPredicates {
1191             parent: None,
1192             predicates: superbounds
1193         };
1194         debug!("superpredicates for trait {:?} = {:?}",
1195                tcx.hir.local_def_id(item.id),
1196                superpredicates);
1197
1198         tcx.super_predicates.borrow_mut().insert(trait_def_id, superpredicates.clone());
1199
1200         superpredicates
1201     });
1202
1203     let def_ids: Vec<_> = superpredicates.predicates
1204                                          .iter()
1205                                          .filter_map(|p| p.to_opt_poly_trait_ref())
1206                                          .map(|tr| tr.def_id())
1207                                          .collect();
1208
1209     debug!("ensure_super_predicates_step: def_ids={:?}", def_ids);
1210
1211     def_ids
1212 }
1213
1214 fn trait_def_of_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, it: &hir::Item) -> &'tcx ty::TraitDef {
1215     let def_id = ccx.tcx.hir.local_def_id(it.id);
1216     let tcx = ccx.tcx;
1217
1218     tcx.trait_defs.memoize(def_id, || {
1219         let unsafety = match it.node {
1220             hir::ItemTrait(unsafety, ..) => unsafety,
1221             _ => span_bug!(it.span, "trait_def_of_item invoked on non-trait"),
1222         };
1223
1224         let paren_sugar = tcx.has_attr(def_id, "rustc_paren_sugar");
1225         if paren_sugar && !ccx.tcx.sess.features.borrow().unboxed_closures {
1226             let mut err = ccx.tcx.sess.struct_span_err(
1227                 it.span,
1228                 "the `#[rustc_paren_sugar]` attribute is a temporary means of controlling \
1229                 which traits can use parenthetical notation");
1230             help!(&mut err,
1231                 "add `#![feature(unboxed_closures)]` to \
1232                 the crate attributes to use it");
1233             err.emit();
1234         }
1235
1236         let def_path_hash = tcx.def_path(def_id).deterministic_hash(tcx);
1237         tcx.alloc_trait_def(ty::TraitDef::new(def_id, unsafety, paren_sugar, def_path_hash))
1238     })
1239 }
1240
1241 fn convert_trait_predicates<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, it: &hir::Item) {
1242     let tcx = ccx.tcx;
1243
1244     let def_id = ccx.tcx.hir.local_def_id(it.id);
1245
1246     generics_of_def_id(ccx, def_id);
1247     trait_def_of_item(ccx, it);
1248
1249     let (generics, items) = match it.node {
1250         hir::ItemTrait(_, ref generics, _, ref items) => (generics, items),
1251         ref s => {
1252             span_bug!(
1253                 it.span,
1254                 "trait_def_of_item invoked on {:?}",
1255                 s);
1256         }
1257     };
1258
1259     let super_predicates = ccx.tcx.item_super_predicates(def_id);
1260
1261     // `ty_generic_predicates` below will consider the bounds on the type
1262     // parameters (including `Self`) and the explicit where-clauses,
1263     // but to get the full set of predicates on a trait we need to add
1264     // in the supertrait bounds and anything declared on the
1265     // associated types.
1266     let mut base_predicates = super_predicates.predicates;
1267
1268     // Add in a predicate that `Self:Trait` (where `Trait` is the
1269     // current trait).  This is needed for builtin bounds.
1270     let trait_ref = ty::TraitRef {
1271         def_id: def_id,
1272         substs: Substs::identity_for_item(tcx, def_id)
1273     };
1274     let self_predicate = trait_ref.to_poly_trait_ref().to_predicate();
1275     base_predicates.push(self_predicate);
1276
1277     // add in the explicit where-clauses
1278     let mut trait_predicates =
1279         ty_generic_predicates(ccx, generics, None, base_predicates, true);
1280
1281     let assoc_predicates = predicates_for_associated_types(ccx,
1282                                                            generics,
1283                                                            &trait_predicates,
1284                                                            trait_ref,
1285                                                            items);
1286     trait_predicates.predicates.extend(assoc_predicates);
1287
1288     tcx.predicates.borrow_mut().insert(def_id, trait_predicates);
1289     return;
1290
1291     fn predicates_for_associated_types<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1292                                                  ast_generics: &hir::Generics,
1293                                                  trait_predicates: &ty::GenericPredicates<'tcx>,
1294                                                  self_trait_ref: ty::TraitRef<'tcx>,
1295                                                  trait_item_refs: &[hir::TraitItemRef])
1296                                                  -> Vec<ty::Predicate<'tcx>>
1297     {
1298         trait_item_refs.iter().flat_map(|trait_item_ref| {
1299             let trait_item = ccx.tcx.hir.trait_item(trait_item_ref.id);
1300             let bounds = match trait_item.node {
1301                 hir::TraitItemKind::Type(ref bounds, _) => bounds,
1302                 _ => {
1303                     return vec![].into_iter();
1304                 }
1305             };
1306
1307             let assoc_ty = ccx.tcx.mk_projection(self_trait_ref,
1308                                                  trait_item.name);
1309
1310             let bounds = compute_bounds(&ccx.icx(&(ast_generics, trait_predicates)),
1311                                         assoc_ty,
1312                                         bounds,
1313                                         SizedByDefault::Yes,
1314                                         trait_item.span);
1315
1316             bounds.predicates(ccx.tcx, assoc_ty).into_iter()
1317         }).collect()
1318     }
1319 }
1320
1321 fn generics_of_def_id<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1322                                 def_id: DefId)
1323                                 -> &'tcx ty::Generics<'tcx> {
1324     let tcx = ccx.tcx;
1325     let node_id = if let Some(id) = tcx.hir.as_local_node_id(def_id) {
1326         id
1327     } else {
1328         return tcx.item_generics(def_id);
1329     };
1330     tcx.generics.memoize(def_id, || {
1331         use rustc::hir::map::*;
1332         use rustc::hir::*;
1333
1334         let node = tcx.hir.get(node_id);
1335         let parent_def_id = match node {
1336             NodeImplItem(_) |
1337             NodeTraitItem(_) |
1338             NodeVariant(_) |
1339             NodeStructCtor(_) => {
1340                 let parent_id = tcx.hir.get_parent(node_id);
1341                 Some(tcx.hir.local_def_id(parent_id))
1342             }
1343             NodeExpr(&hir::Expr { node: hir::ExprClosure(..), .. }) => {
1344                 Some(tcx.closure_base_def_id(def_id))
1345             }
1346             NodeTy(&hir::Ty { node: hir::TyImplTrait(..), .. }) => {
1347                 let mut parent_id = node_id;
1348                 loop {
1349                     match tcx.hir.get(parent_id) {
1350                         NodeItem(_) | NodeImplItem(_) | NodeTraitItem(_) => break,
1351                         _ => {
1352                             parent_id = tcx.hir.get_parent_node(parent_id);
1353                         }
1354                     }
1355                 }
1356                 Some(tcx.hir.local_def_id(parent_id))
1357             }
1358             _ => None
1359         };
1360
1361         let mut opt_self = None;
1362         let mut allow_defaults = false;
1363
1364         let no_generics = hir::Generics::empty();
1365         let ast_generics = match node {
1366             NodeTraitItem(item) => {
1367                 match item.node {
1368                     TraitItemKind::Method(ref sig, _) => &sig.generics,
1369                     _ => &no_generics
1370                 }
1371             }
1372
1373             NodeImplItem(item) => {
1374                 match item.node {
1375                     ImplItemKind::Method(ref sig, _) => &sig.generics,
1376                     _ => &no_generics
1377                 }
1378             }
1379
1380             NodeItem(item) => {
1381                 match item.node {
1382                     ItemFn(.., ref generics, _) |
1383                     ItemImpl(_, _, ref generics, ..) => generics,
1384
1385                     ItemTy(_, ref generics) |
1386                     ItemEnum(_, ref generics) |
1387                     ItemStruct(_, ref generics) |
1388                     ItemUnion(_, ref generics) => {
1389                         allow_defaults = true;
1390                         generics
1391                     }
1392
1393                     ItemTrait(_, ref generics, ..) => {
1394                         // Add in the self type parameter.
1395                         //
1396                         // Something of a hack: use the node id for the trait, also as
1397                         // the node id for the Self type parameter.
1398                         let param_id = item.id;
1399
1400                         let parent = ccx.tcx.hir.get_parent(param_id);
1401
1402                         let def = ty::TypeParameterDef {
1403                             index: 0,
1404                             name: keywords::SelfType.name(),
1405                             def_id: tcx.hir.local_def_id(param_id),
1406                             default_def_id: tcx.hir.local_def_id(parent),
1407                             default: None,
1408                             pure_wrt_drop: false,
1409                         };
1410                         tcx.ty_param_defs.borrow_mut().insert(param_id, def.clone());
1411                         opt_self = Some(def);
1412
1413                         allow_defaults = true;
1414                         generics
1415                     }
1416
1417                     _ => &no_generics
1418                 }
1419             }
1420
1421             NodeForeignItem(item) => {
1422                 match item.node {
1423                     ForeignItemStatic(..) => &no_generics,
1424                     ForeignItemFn(_, _, ref generics) => generics
1425                 }
1426             }
1427
1428             _ => &no_generics
1429         };
1430
1431         let has_self = opt_self.is_some();
1432         let mut parent_has_self = false;
1433         let mut own_start = has_self as u32;
1434         let (parent_regions, parent_types) = parent_def_id.map_or((0, 0), |def_id| {
1435             let generics = generics_of_def_id(ccx, def_id);
1436             assert_eq!(has_self, false);
1437             parent_has_self = generics.has_self;
1438             own_start = generics.count() as u32;
1439             (generics.parent_regions + generics.regions.len() as u32,
1440              generics.parent_types + generics.types.len() as u32)
1441         });
1442
1443         let early_lifetimes = early_bound_lifetimes_from_generics(ccx, ast_generics);
1444         let regions = early_lifetimes.iter().enumerate().map(|(i, l)| {
1445             ty::RegionParameterDef {
1446                 name: l.lifetime.name,
1447                 index: own_start + i as u32,
1448                 def_id: tcx.hir.local_def_id(l.lifetime.id),
1449                 pure_wrt_drop: l.pure_wrt_drop,
1450             }
1451         }).collect::<Vec<_>>();
1452
1453         // Now create the real type parameters.
1454         let type_start = own_start + regions.len() as u32;
1455         let types = ast_generics.ty_params.iter().enumerate().map(|(i, p)| {
1456             let i = type_start + i as u32;
1457             get_or_create_type_parameter_def(ccx, i, p, allow_defaults)
1458         });
1459         let mut types: Vec<_> = opt_self.into_iter().chain(types).collect();
1460
1461         // provide junk type parameter defs - the only place that
1462         // cares about anything but the length is instantiation,
1463         // and we don't do that for closures.
1464         if let NodeExpr(&hir::Expr { node: hir::ExprClosure(..), .. }) = node {
1465             tcx.with_freevars(node_id, |fv| {
1466                 types.extend(fv.iter().enumerate().map(|(i, _)| ty::TypeParameterDef {
1467                     index: type_start + i as u32,
1468                     name: Symbol::intern("<upvar>"),
1469                     def_id: def_id,
1470                     default_def_id: parent_def_id.unwrap(),
1471                     default: None,
1472                     pure_wrt_drop: false,
1473                }));
1474             });
1475         }
1476
1477         tcx.alloc_generics(ty::Generics {
1478             parent: parent_def_id,
1479             parent_regions: parent_regions,
1480             parent_types: parent_types,
1481             regions: regions,
1482             types: types,
1483             has_self: has_self || parent_has_self
1484         })
1485     })
1486 }
1487
1488 fn type_of_def_id<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1489                             def_id: DefId)
1490                             -> Ty<'tcx> {
1491     let node_id = if let Some(id) = ccx.tcx.hir.as_local_node_id(def_id) {
1492         id
1493     } else {
1494         return ccx.tcx.item_type(def_id);
1495     };
1496     ccx.tcx.item_types.memoize(def_id, || {
1497         use rustc::hir::map::*;
1498         use rustc::hir::*;
1499
1500         // Alway bring in generics, as computing the type needs them.
1501         generics_of_def_id(ccx, def_id);
1502
1503         let ty = match ccx.tcx.hir.get(node_id) {
1504             NodeItem(item) => {
1505                 match item.node {
1506                     ItemStatic(ref t, ..) | ItemConst(ref t, _) => {
1507                         ccx.icx(&()).to_ty(&t)
1508                     }
1509                     ItemFn(ref decl, unsafety, _, abi, ref generics, _) => {
1510                         let tofd = AstConv::ty_of_fn(&ccx.icx(generics), unsafety, abi, &decl);
1511                         let substs = mk_item_substs(&ccx.icx(generics), item.span, def_id);
1512                         ccx.tcx.mk_fn_def(def_id, substs, tofd)
1513                     }
1514                     ItemTy(ref t, ref generics) => {
1515                         ccx.icx(generics).to_ty(&t)
1516                     }
1517                     ItemEnum(ref ei, ref generics) => {
1518                         let def = convert_enum_def(ccx, item, ei);
1519                         let substs = mk_item_substs(&ccx.icx(generics), item.span, def_id);
1520                         ccx.tcx.mk_adt(def, substs)
1521                     }
1522                     ItemStruct(ref si, ref generics) => {
1523                         let def = convert_struct_def(ccx, item, si);
1524                         let substs = mk_item_substs(&ccx.icx(generics), item.span, def_id);
1525                         ccx.tcx.mk_adt(def, substs)
1526                     }
1527                     ItemUnion(ref un, ref generics) => {
1528                         let def = convert_union_def(ccx, item, un);
1529                         let substs = mk_item_substs(&ccx.icx(generics), item.span, def_id);
1530                         ccx.tcx.mk_adt(def, substs)
1531                     }
1532                     ItemDefaultImpl(..) |
1533                     ItemTrait(..) |
1534                     ItemImpl(..) |
1535                     ItemMod(..) |
1536                     ItemForeignMod(..) |
1537                     ItemExternCrate(..) |
1538                     ItemUse(..) => {
1539                         span_bug!(
1540                             item.span,
1541                             "compute_type_of_item: unexpected item type: {:?}",
1542                             item.node);
1543                     }
1544                 }
1545             }
1546             NodeForeignItem(foreign_item) => {
1547                 let abi = ccx.tcx.hir.get_foreign_abi(node_id);
1548
1549                 match foreign_item.node {
1550                     ForeignItemFn(ref fn_decl, _, ref generics) => {
1551                         compute_type_of_foreign_fn_decl(
1552                             ccx, ccx.tcx.hir.local_def_id(foreign_item.id),
1553                             fn_decl, generics, abi)
1554                     }
1555                     ForeignItemStatic(ref t, _) => {
1556                         ccx.icx(&()).to_ty(t)
1557                     }
1558                 }
1559             }
1560             NodeExpr(&hir::Expr { node: hir::ExprClosure(..), .. }) => {
1561                 ccx.tcx.mk_closure(def_id, Substs::for_item(
1562                     ccx.tcx, def_id,
1563                     |def, _| {
1564                         let region = def.to_early_bound_region_data();
1565                         ccx.tcx.mk_region(ty::ReEarlyBound(region))
1566                     },
1567                     |def, _| ccx.tcx.mk_param_from_def(def)
1568                 ))
1569             }
1570             x => {
1571                 bug!("unexpected sort of node in type_of_def_id(): {:?}", x);
1572             }
1573         };
1574
1575         ty
1576     })
1577 }
1578
1579 fn predicates_of_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1580                                 it: &hir::Item)
1581                                 -> ty::GenericPredicates<'tcx> {
1582     let def_id = ccx.tcx.hir.local_def_id(it.id);
1583
1584     let no_generics = hir::Generics::empty();
1585     let generics = match it.node {
1586         hir::ItemFn(.., ref generics, _) |
1587         hir::ItemTy(_, ref generics) |
1588         hir::ItemEnum(_, ref generics) |
1589         hir::ItemStruct(_, ref generics) |
1590         hir::ItemUnion(_, ref generics) => generics,
1591         _ => &no_generics
1592     };
1593
1594     let predicates = ty_generic_predicates(ccx, generics, None, vec![], false);
1595     ccx.tcx.predicates.borrow_mut().insert(def_id, predicates.clone());
1596
1597     predicates
1598 }
1599
1600 fn convert_foreign_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1601                                   it: &hir::ForeignItem)
1602 {
1603     // For reasons I cannot fully articulate, I do so hate the AST
1604     // map, and I regard each time that I use it as a personal and
1605     // moral failing, but at the moment it seems like the only
1606     // convenient way to extract the ABI. - ndm
1607     let def_id = ccx.tcx.hir.local_def_id(it.id);
1608     type_of_def_id(ccx, def_id);
1609     generics_of_def_id(ccx, def_id);
1610
1611     let no_generics = hir::Generics::empty();
1612     let generics = match it.node {
1613         hir::ForeignItemFn(_, _, ref generics) => generics,
1614         hir::ForeignItemStatic(..) => &no_generics
1615     };
1616
1617     let predicates = ty_generic_predicates(ccx, generics, None, vec![], false);
1618     ccx.tcx.predicates.borrow_mut().insert(def_id, predicates);
1619 }
1620
1621 // Is it marked with ?Sized
1622 fn is_unsized<'gcx: 'tcx, 'tcx>(astconv: &AstConv<'gcx, 'tcx>,
1623                                 ast_bounds: &[hir::TyParamBound],
1624                                 span: Span) -> bool
1625 {
1626     let tcx = astconv.tcx();
1627
1628     // Try to find an unbound in bounds.
1629     let mut unbound = None;
1630     for ab in ast_bounds {
1631         if let &hir::TraitTyParamBound(ref ptr, hir::TraitBoundModifier::Maybe) = ab  {
1632             if unbound.is_none() {
1633                 unbound = Some(ptr.trait_ref.clone());
1634             } else {
1635                 span_err!(tcx.sess, span, E0203,
1636                           "type parameter has more than one relaxed default \
1637                                                 bound, only one is supported");
1638             }
1639         }
1640     }
1641
1642     let kind_id = tcx.lang_items.require(SizedTraitLangItem);
1643     match unbound {
1644         Some(ref tpb) => {
1645             // FIXME(#8559) currently requires the unbound to be built-in.
1646             if let Ok(kind_id) = kind_id {
1647                 if tpb.path.def != Def::Trait(kind_id) {
1648                     tcx.sess.span_warn(span,
1649                                        "default bound relaxed for a type parameter, but \
1650                                        this does nothing because the given bound is not \
1651                                        a default. Only `?Sized` is supported");
1652                 }
1653             }
1654         }
1655         _ if kind_id.is_ok() => {
1656             return false;
1657         }
1658         // No lang item for Sized, so we can't add it as a bound.
1659         None => {}
1660     }
1661
1662     true
1663 }
1664
1665 /// Returns the early-bound lifetimes declared in this generics
1666 /// listing.  For anything other than fns/methods, this is just all
1667 /// the lifetimes that are declared. For fns or methods, we have to
1668 /// screen out those that do not appear in any where-clauses etc using
1669 /// `resolve_lifetime::early_bound_lifetimes`.
1670 fn early_bound_lifetimes_from_generics<'a, 'tcx, 'hir>(
1671     ccx: &CrateCtxt<'a, 'tcx>,
1672     ast_generics: &'hir hir::Generics)
1673     -> Vec<&'hir hir::LifetimeDef>
1674 {
1675     ast_generics
1676         .lifetimes
1677         .iter()
1678         .filter(|l| !ccx.tcx.named_region_map.late_bound.contains_key(&l.lifetime.id))
1679         .collect()
1680 }
1681
1682 fn ty_generic_predicates<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1683                                   ast_generics: &hir::Generics,
1684                                   parent: Option<DefId>,
1685                                   super_predicates: Vec<ty::Predicate<'tcx>>,
1686                                   has_self: bool)
1687                                   -> ty::GenericPredicates<'tcx>
1688 {
1689     let tcx = ccx.tcx;
1690     let parent_count = parent.map_or(0, |def_id| {
1691         let generics = generics_of_def_id(ccx, def_id);
1692         assert_eq!(generics.parent, None);
1693         assert_eq!(generics.parent_regions, 0);
1694         assert_eq!(generics.parent_types, 0);
1695         generics.count() as u32
1696     });
1697     let ref base_predicates = match parent {
1698         Some(def_id) => {
1699             assert_eq!(super_predicates, vec![]);
1700             tcx.item_predicates(def_id)
1701         }
1702         None => {
1703             ty::GenericPredicates {
1704                 parent: None,
1705                 predicates: super_predicates.clone()
1706             }
1707         }
1708     };
1709     let mut predicates = super_predicates;
1710
1711     // Collect the region predicates that were declared inline as
1712     // well. In the case of parameters declared on a fn or method, we
1713     // have to be careful to only iterate over early-bound regions.
1714     let own_start = parent_count + has_self as u32;
1715     let early_lifetimes = early_bound_lifetimes_from_generics(ccx, ast_generics);
1716     for (index, param) in early_lifetimes.iter().enumerate() {
1717         let index = own_start + index as u32;
1718         let region = ccx.tcx.mk_region(ty::ReEarlyBound(ty::EarlyBoundRegion {
1719             index: index,
1720             name: param.lifetime.name
1721         }));
1722         for bound in &param.bounds {
1723             let bound_region = AstConv::ast_region_to_region(&ccx.icx(&()), bound, None);
1724             let outlives = ty::Binder(ty::OutlivesPredicate(region, bound_region));
1725             predicates.push(outlives.to_predicate());
1726         }
1727     }
1728
1729     // Collect the predicates that were written inline by the user on each
1730     // type parameter (e.g., `<T:Foo>`).
1731     let type_start = own_start + early_lifetimes.len() as u32;
1732     for (index, param) in ast_generics.ty_params.iter().enumerate() {
1733         let index = type_start + index as u32;
1734         let param_ty = ty::ParamTy::new(index, param.name).to_ty(ccx.tcx);
1735         let bounds = compute_bounds(&ccx.icx(&(base_predicates, ast_generics)),
1736                                     param_ty,
1737                                     &param.bounds,
1738                                     SizedByDefault::Yes,
1739                                     param.span);
1740         predicates.extend(bounds.predicates(ccx.tcx, param_ty));
1741     }
1742
1743     // Add in the bounds that appear in the where-clause
1744     let where_clause = &ast_generics.where_clause;
1745     for predicate in &where_clause.predicates {
1746         match predicate {
1747             &hir::WherePredicate::BoundPredicate(ref bound_pred) => {
1748                 let ty = AstConv::ast_ty_to_ty(&ccx.icx(&(base_predicates, ast_generics)),
1749                                                &bound_pred.bounded_ty);
1750
1751                 for bound in bound_pred.bounds.iter() {
1752                     match bound {
1753                         &hir::TyParamBound::TraitTyParamBound(ref poly_trait_ref, _) => {
1754                             let mut projections = Vec::new();
1755
1756                             let trait_ref =
1757                                 AstConv::instantiate_poly_trait_ref(&ccx.icx(&(base_predicates,
1758                                                                                ast_generics)),
1759                                                                     poly_trait_ref,
1760                                                                     ty,
1761                                                                     &mut projections);
1762
1763                             predicates.push(trait_ref.to_predicate());
1764
1765                             for projection in &projections {
1766                                 predicates.push(projection.to_predicate());
1767                             }
1768                         }
1769
1770                         &hir::TyParamBound::RegionTyParamBound(ref lifetime) => {
1771                             let region = AstConv::ast_region_to_region(&ccx.icx(&()),
1772                                                                        lifetime,
1773                                                                        None);
1774                             let pred = ty::Binder(ty::OutlivesPredicate(ty, region));
1775                             predicates.push(ty::Predicate::TypeOutlives(pred))
1776                         }
1777                     }
1778                 }
1779             }
1780
1781             &hir::WherePredicate::RegionPredicate(ref region_pred) => {
1782                 let r1 = AstConv::ast_region_to_region(&ccx.icx(&()), &region_pred.lifetime, None);
1783                 for bound in &region_pred.bounds {
1784                     let r2 = AstConv::ast_region_to_region(&ccx.icx(&()), bound, None);
1785                     let pred = ty::Binder(ty::OutlivesPredicate(r1, r2));
1786                     predicates.push(ty::Predicate::RegionOutlives(pred))
1787                 }
1788             }
1789
1790             &hir::WherePredicate::EqPredicate(..) => {
1791                 // FIXME(#20041)
1792             }
1793         }
1794     }
1795
1796     ty::GenericPredicates {
1797         parent: parent,
1798         predicates: predicates
1799     }
1800 }
1801
1802 fn get_or_create_type_parameter_def<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1803                                              index: u32,
1804                                              param: &hir::TyParam,
1805                                              allow_defaults: bool)
1806                                              -> ty::TypeParameterDef<'tcx>
1807 {
1808     let tcx = ccx.tcx;
1809     match tcx.ty_param_defs.borrow().get(&param.id) {
1810         Some(d) => { return d.clone(); }
1811         None => { }
1812     }
1813
1814     let default =
1815         param.default.as_ref().map(|def| ccx.icx(&()).to_ty(def));
1816
1817     let parent = tcx.hir.get_parent(param.id);
1818
1819     if !allow_defaults && default.is_some() {
1820         if !tcx.sess.features.borrow().default_type_parameter_fallback {
1821             tcx.sess.add_lint(
1822                 lint::builtin::INVALID_TYPE_PARAM_DEFAULT,
1823                 param.id,
1824                 param.span,
1825                 format!("defaults for type parameters are only allowed in `struct`, \
1826                          `enum`, `type`, or `trait` definitions."));
1827         }
1828     }
1829
1830     let def = ty::TypeParameterDef {
1831         index: index,
1832         name: param.name,
1833         def_id: ccx.tcx.hir.local_def_id(param.id),
1834         default_def_id: ccx.tcx.hir.local_def_id(parent),
1835         default: default,
1836         pure_wrt_drop: param.pure_wrt_drop,
1837     };
1838
1839     if def.name == keywords::SelfType.name() {
1840         span_bug!(param.span, "`Self` should not be the name of a regular parameter");
1841     }
1842
1843     tcx.ty_param_defs.borrow_mut().insert(param.id, def.clone());
1844
1845     debug!("get_or_create_type_parameter_def: def for type param: {:?}", def);
1846
1847     def
1848 }
1849
1850 pub enum SizedByDefault { Yes, No, }
1851
1852 /// Translate the AST's notion of ty param bounds (which are an enum consisting of a newtyped Ty or
1853 /// a region) to ty's notion of ty param bounds, which can either be user-defined traits, or the
1854 /// built-in trait (formerly known as kind): Send.
1855 pub fn compute_bounds<'gcx: 'tcx, 'tcx>(astconv: &AstConv<'gcx, 'tcx>,
1856                                         param_ty: ty::Ty<'tcx>,
1857                                         ast_bounds: &[hir::TyParamBound],
1858                                         sized_by_default: SizedByDefault,
1859                                         span: Span)
1860                                         -> Bounds<'tcx>
1861 {
1862     let mut region_bounds = vec![];
1863     let mut trait_bounds = vec![];
1864     for ast_bound in ast_bounds {
1865         match *ast_bound {
1866             hir::TraitTyParamBound(ref b, hir::TraitBoundModifier::None) => {
1867                 trait_bounds.push(b);
1868             }
1869             hir::TraitTyParamBound(_, hir::TraitBoundModifier::Maybe) => {}
1870             hir::RegionTyParamBound(ref l) => {
1871                 region_bounds.push(l);
1872             }
1873         }
1874     }
1875
1876     let mut projection_bounds = vec![];
1877
1878     let mut trait_bounds: Vec<_> = trait_bounds.iter().map(|&bound| {
1879         astconv.instantiate_poly_trait_ref(bound,
1880                                            param_ty,
1881                                            &mut projection_bounds)
1882     }).collect();
1883
1884     let region_bounds = region_bounds.into_iter().map(|r| {
1885         astconv.ast_region_to_region(r, None)
1886     }).collect();
1887
1888     trait_bounds.sort_by(|a,b| a.def_id().cmp(&b.def_id()));
1889
1890     let implicitly_sized = if let SizedByDefault::Yes = sized_by_default {
1891         !is_unsized(astconv, ast_bounds, span)
1892     } else {
1893         false
1894     };
1895
1896     Bounds {
1897         region_bounds: region_bounds,
1898         implicitly_sized: implicitly_sized,
1899         trait_bounds: trait_bounds,
1900         projection_bounds: projection_bounds,
1901     }
1902 }
1903
1904 /// Converts a specific TyParamBound from the AST into a set of
1905 /// predicates that apply to the self-type. A vector is returned
1906 /// because this can be anywhere from 0 predicates (`T:?Sized` adds no
1907 /// predicates) to 1 (`T:Foo`) to many (`T:Bar<X=i32>` adds `T:Bar`
1908 /// and `<T as Bar>::X == i32`).
1909 fn predicates_from_bound<'tcx>(astconv: &AstConv<'tcx, 'tcx>,
1910                                param_ty: Ty<'tcx>,
1911                                bound: &hir::TyParamBound)
1912                                -> Vec<ty::Predicate<'tcx>>
1913 {
1914     match *bound {
1915         hir::TraitTyParamBound(ref tr, hir::TraitBoundModifier::None) => {
1916             let mut projections = Vec::new();
1917             let pred = astconv.instantiate_poly_trait_ref(tr,
1918                                                           param_ty,
1919                                                           &mut projections);
1920             projections.into_iter()
1921                        .map(|p| p.to_predicate())
1922                        .chain(Some(pred.to_predicate()))
1923                        .collect()
1924         }
1925         hir::RegionTyParamBound(ref lifetime) => {
1926             let region = astconv.ast_region_to_region(lifetime, None);
1927             let pred = ty::Binder(ty::OutlivesPredicate(param_ty, region));
1928             vec![ty::Predicate::TypeOutlives(pred)]
1929         }
1930         hir::TraitTyParamBound(_, hir::TraitBoundModifier::Maybe) => {
1931             Vec::new()
1932         }
1933     }
1934 }
1935
1936 fn compute_type_of_foreign_fn_decl<'a, 'tcx>(
1937     ccx: &CrateCtxt<'a, 'tcx>,
1938     def_id: DefId,
1939     decl: &hir::FnDecl,
1940     ast_generics: &hir::Generics,
1941     abi: abi::Abi)
1942     -> Ty<'tcx>
1943 {
1944     let fty = AstConv::ty_of_fn(&ccx.icx(ast_generics), hir::Unsafety::Unsafe, abi, decl);
1945
1946     // feature gate SIMD types in FFI, since I (huonw) am not sure the
1947     // ABIs are handled at all correctly.
1948     if abi != abi::Abi::RustIntrinsic && abi != abi::Abi::PlatformIntrinsic
1949             && !ccx.tcx.sess.features.borrow().simd_ffi {
1950         let check = |ast_ty: &hir::Ty, ty: ty::Ty| {
1951             if ty.is_simd() {
1952                 ccx.tcx.sess.struct_span_err(ast_ty.span,
1953                               &format!("use of SIMD type `{}` in FFI is highly experimental and \
1954                                         may result in invalid code",
1955                                        ccx.tcx.hir.node_to_pretty_string(ast_ty.id)))
1956                     .help("add #![feature(simd_ffi)] to the crate attributes to enable")
1957                     .emit();
1958             }
1959         };
1960         for (input, ty) in decl.inputs.iter().zip(*fty.sig.inputs().skip_binder()) {
1961             check(&input, ty)
1962         }
1963         if let hir::Return(ref ty) = decl.output {
1964             check(&ty, *fty.sig.output().skip_binder())
1965         }
1966     }
1967
1968     let id = ccx.tcx.hir.as_local_node_id(def_id).unwrap();
1969     let substs = mk_item_substs(&ccx.icx(ast_generics), ccx.tcx.hir.span(id), def_id);
1970     ccx.tcx.mk_fn_def(def_id, substs, fty)
1971 }
1972
1973 fn mk_item_substs<'tcx>(astconv: &AstConv<'tcx, 'tcx>,
1974                         span: Span,
1975                         def_id: DefId)
1976                         -> &'tcx Substs<'tcx> {
1977     let tcx = astconv.tcx();
1978     // FIXME(eddyb) Do this request from Substs::for_item in librustc.
1979     if let Err(ErrorReported) = astconv.get_generics(span, def_id) {
1980         // No convenient way to recover from a cycle here. Just bail. Sorry!
1981         tcx.sess.abort_if_errors();
1982         bug!("ErrorReported returned, but no errors reports?")
1983     }
1984
1985     Substs::identity_for_item(tcx, def_id)
1986 }