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