src/librustc_typeck/collect.rs

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