src/librustc_typeck/collect.rs

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