src/librustc_typeck/collect.rs

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