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