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::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::SelfTy(Some(def_id), None) => {
 516                 path_res.depth == 0 && def_id == tcx.map.local_def_id(param_id)
 517             }
 518             Def::TyParam(_, _, 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         kind: VariantKind::from_variant_data(def),
1011     }
1012 }
1013
1014 fn convert_struct_def<'tcx>(tcx: &ty::ctxt<'tcx>,
1015                             it: &hir::Item,
1016                             def: &hir::VariantData)
1017                             -> ty::AdtDefMaster<'tcx>
1018 {
1019
1020     let did = tcx.map.local_def_id(it.id);
1021     let ctor_id = if !def.is_struct() {
1022         tcx.map.local_def_id(def.id())
1023     } else {
1024         did
1025     };
1026     tcx.intern_adt_def(
1027         did,
1028         ty::AdtKind::Struct,
1029         vec![convert_struct_variant(tcx, ctor_id, it.name, 0, def)]
1030     )
1031 }
1032
1033 fn convert_enum_def<'tcx>(tcx: &ty::ctxt<'tcx>,
1034                           it: &hir::Item,
1035                           def: &hir::EnumDef)
1036                           -> ty::AdtDefMaster<'tcx>
1037 {
1038     fn evaluate_disr_expr<'tcx>(tcx: &ty::ctxt<'tcx>,
1039                                 repr_ty: Ty<'tcx>,
1040                                 e: &hir::Expr) -> Option<ty::Disr> {
1041         debug!("disr expr, checking {}", pprust::expr_to_string(e));
1042
1043         let hint = UncheckedExprHint(repr_ty);
1044         match const_eval::eval_const_expr_partial(tcx, e, hint, None) {
1045             Ok(ConstVal::Int(val)) => Some(val as ty::Disr),
1046             Ok(ConstVal::Uint(val)) => Some(val as ty::Disr),
1047             Ok(_) => {
1048                 let sign_desc = if repr_ty.is_signed() {
1049                     "signed"
1050                 } else {
1051                     "unsigned"
1052                 };
1053                 span_err!(tcx.sess, e.span, E0079,
1054                           "expected {} integer constant",
1055                           sign_desc);
1056                 None
1057             },
1058             Err(err) => {
1059                 let mut diag = struct_span_err!(tcx.sess, err.span, E0080,
1060                                                 "constant evaluation error: {}",
1061                                                 err.description());
1062                 if !e.span.contains(err.span) {
1063                     diag.span_note(e.span, "for enum discriminant here");
1064                 }
1065                 diag.emit();
1066                 None
1067             }
1068         }
1069     }
1070
1071     fn report_discrim_overflow(tcx: &ty::ctxt,
1072                                variant_span: Span,
1073                                variant_name: &str,
1074                                repr_type: attr::IntType,
1075                                prev_val: ty::Disr) {
1076         let computed_value = repr_type.disr_wrap_incr(Some(prev_val));
1077         let computed_value = repr_type.disr_string(computed_value);
1078         let prev_val = repr_type.disr_string(prev_val);
1079         let repr_type = repr_type.to_ty(tcx);
1080         span_err!(tcx.sess, variant_span, E0370,
1081                   "enum discriminant overflowed on value after {}: {}; \
1082                    set explicitly via {} = {} if that is desired outcome",
1083                   prev_val, repr_type, variant_name, computed_value);
1084     }
1085
1086     fn next_disr(tcx: &ty::ctxt,
1087                  v: &hir::Variant,
1088                  repr_type: attr::IntType,
1089                  prev_disr_val: Option<ty::Disr>) -> Option<ty::Disr> {
1090         if let Some(prev_disr_val) = prev_disr_val {
1091             let result = repr_type.disr_incr(prev_disr_val);
1092             if let None = result {
1093                 report_discrim_overflow(tcx, v.span, &v.node.name.as_str(),
1094                                              repr_type, prev_disr_val);
1095             }
1096             result
1097         } else {
1098             Some(ty::INITIAL_DISCRIMINANT_VALUE)
1099         }
1100     }
1101     fn convert_enum_variant<'tcx>(tcx: &ty::ctxt<'tcx>,
1102                                   v: &hir::Variant,
1103                                   disr: ty::Disr)
1104                                   -> ty::VariantDefData<'tcx, 'tcx>
1105     {
1106         let did = tcx.map.local_def_id(v.node.data.id());
1107         let name = v.node.name;
1108         convert_struct_variant(tcx, did, name, disr, &v.node.data)
1109     }
1110     let did = tcx.map.local_def_id(it.id);
1111     let repr_hints = tcx.lookup_repr_hints(did);
1112     let (repr_type, repr_type_ty) = tcx.enum_repr_type(repr_hints.get(0));
1113     let mut prev_disr = None;
1114     let variants = def.variants.iter().map(|v| {
1115         let disr = match v.node.disr_expr {
1116             Some(ref e) => evaluate_disr_expr(tcx, repr_type_ty, e),
1117             None => next_disr(tcx, v, repr_type, prev_disr)
1118         }.unwrap_or(repr_type.disr_wrap_incr(prev_disr));
1119
1120         let v = convert_enum_variant(tcx, v, disr);
1121         prev_disr = Some(disr);
1122         v
1123     }).collect();
1124     tcx.intern_adt_def(tcx.map.local_def_id(it.id), ty::AdtKind::Enum, variants)
1125 }
1126
1127 /// Ensures that the super-predicates of the trait with def-id
1128 /// trait_def_id are converted and stored. This does NOT ensure that
1129 /// the transitive super-predicates are converted; that is the job of
1130 /// the `ensure_super_predicates()` method in the `AstConv` impl
1131 /// above. Returns a list of trait def-ids that must be ensured as
1132 /// well to guarantee that the transitive superpredicates are
1133 /// converted.
1134 fn ensure_super_predicates_step(ccx: &CrateCtxt,
1135                                 trait_def_id: DefId)
1136                                 -> Vec<DefId>
1137 {
1138     let tcx = ccx.tcx;
1139
1140     debug!("ensure_super_predicates_step(trait_def_id={:?})", trait_def_id);
1141
1142     let trait_node_id = if let Some(n) = tcx.map.as_local_node_id(trait_def_id) {
1143         n
1144     } else {
1145         // If this trait comes from an external crate, then all of the
1146         // supertraits it may depend on also must come from external
1147         // crates, and hence all of them already have their
1148         // super-predicates "converted" (and available from crate
1149         // meta-data), so there is no need to transitively test them.
1150         return Vec::new();
1151     };
1152
1153     let superpredicates = tcx.super_predicates.borrow().get(&trait_def_id).cloned();
1154     let superpredicates = superpredicates.unwrap_or_else(|| {
1155         let item = match ccx.tcx.map.get(trait_node_id) {
1156             hir_map::NodeItem(item) => item,
1157             _ => ccx.tcx.sess.bug(&format!("trait_node_id {} is not an item", trait_node_id))
1158         };
1159
1160         let (generics, bounds) = match item.node {
1161             hir::ItemTrait(_, ref generics, ref supertraits, _) => (generics, supertraits),
1162             _ => tcx.sess.span_bug(item.span,
1163                                    "ensure_super_predicates_step invoked on non-trait"),
1164         };
1165
1166         // In-scope when converting the superbounds for `Trait` are
1167         // that `Self:Trait` as well as any bounds that appear on the
1168         // generic types:
1169         let trait_def = trait_def_of_item(ccx, item);
1170         let self_predicate = ty::GenericPredicates {
1171             predicates: VecPerParamSpace::new(vec![],
1172                                               vec![trait_def.trait_ref.to_predicate()],
1173                                               vec![])
1174         };
1175         let scope = &(generics, &self_predicate);
1176
1177         // Convert the bounds that follow the colon, e.g. `Bar+Zed` in `trait Foo : Bar+Zed`.
1178         let self_param_ty = tcx.mk_self_type();
1179         let superbounds1 = compute_bounds(&ccx.icx(scope),
1180                                     self_param_ty,
1181                                     bounds,
1182                                     SizedByDefault::No,
1183                                     item.span);
1184
1185         let superbounds1 = superbounds1.predicates(tcx, self_param_ty);
1186
1187         // Convert any explicit superbounds in the where clause,
1188         // e.g. `trait Foo where Self : Bar`:
1189         let superbounds2 = generics.get_type_parameter_bounds(&ccx.icx(scope), item.span, item.id);
1190
1191         // Combine the two lists to form the complete set of superbounds:
1192         let superbounds = superbounds1.into_iter().chain(superbounds2).collect();
1193         let superpredicates = ty::GenericPredicates {
1194             predicates: VecPerParamSpace::new(superbounds, vec![], vec![])
1195         };
1196         debug!("superpredicates for trait {:?} = {:?}",
1197                tcx.map.local_def_id(item.id),
1198                superpredicates);
1199
1200         tcx.super_predicates.borrow_mut().insert(trait_def_id, superpredicates.clone());
1201
1202         superpredicates
1203     });
1204
1205     let def_ids: Vec<_> = superpredicates.predicates
1206                                          .iter()
1207                                          .filter_map(|p| p.to_opt_poly_trait_ref())
1208                                          .map(|tr| tr.def_id())
1209                                          .collect();
1210
1211     debug!("ensure_super_predicates_step: def_ids={:?}", def_ids);
1212
1213     def_ids
1214 }
1215
1216 fn trait_def_of_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1217                                it: &hir::Item)
1218                                -> &'tcx ty::TraitDef<'tcx>
1219 {
1220     let def_id = ccx.tcx.map.local_def_id(it.id);
1221     let tcx = ccx.tcx;
1222
1223     if let Some(def) = tcx.trait_defs.borrow().get(&def_id) {
1224         return def.clone();
1225     }
1226
1227     let (unsafety, generics, items) = match it.node {
1228         hir::ItemTrait(unsafety, ref generics, _, ref items) => (unsafety, generics, items),
1229         _ => tcx.sess.span_bug(it.span, "trait_def_of_item invoked on non-trait"),
1230     };
1231
1232     let paren_sugar = tcx.has_attr(def_id, "rustc_paren_sugar");
1233     if paren_sugar && !ccx.tcx.sess.features.borrow().unboxed_closures {
1234         let mut err = ccx.tcx.sess.struct_span_err(
1235             it.span,
1236             "the `#[rustc_paren_sugar]` attribute is a temporary means of controlling \
1237              which traits can use parenthetical notation");
1238         fileline_help!(&mut err, it.span,
1239                    "add `#![feature(unboxed_closures)]` to \
1240                     the crate attributes to use it");
1241         err.emit();
1242     }
1243
1244     let substs = ccx.tcx.mk_substs(mk_trait_substs(ccx, generics));
1245
1246     let ty_generics = ty_generics_for_trait(ccx, it.id, substs, generics);
1247
1248     let associated_type_names: Vec<_> = items.iter().filter_map(|trait_item| {
1249         match trait_item.node {
1250             hir::TypeTraitItem(..) => Some(trait_item.name),
1251             _ => None,
1252         }
1253     }).collect();
1254
1255     let trait_ref = ty::TraitRef {
1256         def_id: def_id,
1257         substs: substs,
1258     };
1259
1260     let trait_def = ty::TraitDef::new(unsafety,
1261                                       paren_sugar,
1262                                       ty_generics,
1263                                       trait_ref,
1264                                       associated_type_names);
1265
1266     return tcx.intern_trait_def(trait_def);
1267
1268     fn mk_trait_substs<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1269                                  generics: &hir::Generics)
1270                                  -> Substs<'tcx>
1271     {
1272         let tcx = ccx.tcx;
1273
1274         // Creates a no-op substitution for the trait's type parameters.
1275         let regions =
1276             generics.lifetimes
1277                     .iter()
1278                     .enumerate()
1279                     .map(|(i, def)| ty::ReEarlyBound(ty::EarlyBoundRegion {
1280                         space: TypeSpace,
1281                         index: i as u32,
1282                         name: def.lifetime.name
1283                     }))
1284                     .collect();
1285
1286         // Start with the generics in the type parameters...
1287         let types: Vec<_> =
1288             generics.ty_params
1289                     .iter()
1290                     .enumerate()
1291                     .map(|(i, def)| tcx.mk_param(TypeSpace,
1292                                                  i as u32, def.name))
1293                     .collect();
1294
1295         // ...and also create the `Self` parameter.
1296         let self_ty = tcx.mk_self_type();
1297
1298         Substs::new_trait(types, regions, self_ty)
1299     }
1300 }
1301
1302 fn trait_defines_associated_type_named(ccx: &CrateCtxt,
1303                                        trait_node_id: ast::NodeId,
1304                                        assoc_name: ast::Name)
1305                                        -> bool
1306 {
1307     let item = match ccx.tcx.map.get(trait_node_id) {
1308         hir_map::NodeItem(item) => item,
1309         _ => ccx.tcx.sess.bug(&format!("trait_node_id {} is not an item", trait_node_id))
1310     };
1311
1312     let trait_items = match item.node {
1313         hir::ItemTrait(_, _, _, ref trait_items) => trait_items,
1314         _ => ccx.tcx.sess.bug(&format!("trait_node_id {} is not a trait", trait_node_id))
1315     };
1316
1317     trait_items.iter().any(|trait_item| {
1318         match trait_item.node {
1319             hir::TypeTraitItem(..) => trait_item.name == assoc_name,
1320             _ => false,
1321         }
1322     })
1323 }
1324
1325 fn convert_trait_predicates<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, it: &hir::Item) {
1326     let tcx = ccx.tcx;
1327     let trait_def = trait_def_of_item(ccx, it);
1328
1329     let def_id = ccx.tcx.map.local_def_id(it.id);
1330
1331     let (generics, items) = match it.node {
1332         hir::ItemTrait(_, ref generics, _, ref items) => (generics, items),
1333         ref s => {
1334             tcx.sess.span_bug(
1335                 it.span,
1336                 &format!("trait_def_of_item invoked on {:?}", s));
1337         }
1338     };
1339
1340     let super_predicates = ccx.tcx.lookup_super_predicates(def_id);
1341
1342     // `ty_generic_predicates` below will consider the bounds on the type
1343     // parameters (including `Self`) and the explicit where-clauses,
1344     // but to get the full set of predicates on a trait we need to add
1345     // in the supertrait bounds and anything declared on the
1346     // associated types.
1347     let mut base_predicates = super_predicates;
1348
1349     // Add in a predicate that `Self:Trait` (where `Trait` is the
1350     // current trait).  This is needed for builtin bounds.
1351     let self_predicate = trait_def.trait_ref.to_poly_trait_ref().to_predicate();
1352     base_predicates.predicates.push(SelfSpace, self_predicate);
1353
1354     // add in the explicit where-clauses
1355     let mut trait_predicates =
1356         ty_generic_predicates(ccx, TypeSpace, generics, &base_predicates);
1357
1358     let assoc_predicates = predicates_for_associated_types(ccx,
1359                                                            generics,
1360                                                            &trait_predicates,
1361                                                            trait_def.trait_ref,
1362                                                            items);
1363     trait_predicates.predicates.extend(TypeSpace, assoc_predicates.into_iter());
1364
1365     let prev_predicates = tcx.predicates.borrow_mut().insert(def_id, trait_predicates);
1366     assert!(prev_predicates.is_none());
1367
1368     return;
1369
1370     fn predicates_for_associated_types<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1371                                                  ast_generics: &hir::Generics,
1372                                                  trait_predicates: &ty::GenericPredicates<'tcx>,
1373                                                  self_trait_ref: ty::TraitRef<'tcx>,
1374                                                  trait_items: &[hir::TraitItem])
1375                                                  -> Vec<ty::Predicate<'tcx>>
1376     {
1377         trait_items.iter().flat_map(|trait_item| {
1378             let bounds = match trait_item.node {
1379                 hir::TypeTraitItem(ref bounds, _) => bounds,
1380                 _ => {
1381                     return vec!().into_iter();
1382                 }
1383             };
1384
1385             let assoc_ty = ccx.tcx.mk_projection(self_trait_ref,
1386                                                  trait_item.name);
1387
1388             let bounds = compute_bounds(&ccx.icx(&(ast_generics, trait_predicates)),
1389                                         assoc_ty,
1390                                         bounds,
1391                                         SizedByDefault::Yes,
1392                                         trait_item.span);
1393
1394             bounds.predicates(ccx.tcx, assoc_ty).into_iter()
1395         }).collect()
1396     }
1397 }
1398
1399 fn type_scheme_of_def_id<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1400                                   def_id: DefId)
1401                                   -> ty::TypeScheme<'tcx>
1402 {
1403     if let Some(node_id) = ccx.tcx.map.as_local_node_id(def_id) {
1404         match ccx.tcx.map.find(node_id) {
1405             Some(hir_map::NodeItem(item)) => {
1406                 type_scheme_of_item(ccx, &*item)
1407             }
1408             Some(hir_map::NodeForeignItem(foreign_item)) => {
1409                 let abi = ccx.tcx.map.get_foreign_abi(node_id);
1410                 type_scheme_of_foreign_item(ccx, &*foreign_item, abi)
1411             }
1412             x => {
1413                 ccx.tcx.sess.bug(&format!("unexpected sort of node \
1414                                            in get_item_type_scheme(): {:?}",
1415                                           x));
1416             }
1417         }
1418     } else {
1419         ccx.tcx.lookup_item_type(def_id)
1420     }
1421 }
1422
1423 fn type_scheme_of_item<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1424                                 item: &hir::Item)
1425                                 -> ty::TypeScheme<'tcx>
1426 {
1427     let item_def_id = ccx.tcx.map.local_def_id(item.id);
1428     ccx.tcx.tcache.memoize(item_def_id, || {
1429         // NB. Since the `memoized` function enters a new task, and we
1430         // are giving this task access to the item `item`, we must
1431         // register a read.
1432         ccx.tcx.dep_graph.read(DepNode::Hir(item_def_id));
1433         compute_type_scheme_of_item(ccx, item)
1434     })
1435 }
1436
1437 fn compute_type_scheme_of_item<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1438                                         it: &hir::Item)
1439                                         -> ty::TypeScheme<'tcx>
1440 {
1441     let tcx = ccx.tcx;
1442     match it.node {
1443         hir::ItemStatic(ref t, _, _) | hir::ItemConst(ref t, _) => {
1444             let ty = ccx.icx(&()).to_ty(&ExplicitRscope, &**t);
1445             ty::TypeScheme { ty: ty, generics: ty::Generics::empty() }
1446         }
1447         hir::ItemFn(ref decl, unsafety, _, abi, ref generics, _) => {
1448             let ty_generics = ty_generics_for_fn(ccx, generics, &ty::Generics::empty());
1449             let tofd = astconv::ty_of_bare_fn(&ccx.icx(generics), unsafety, abi, &**decl);
1450             let ty = tcx.mk_fn(Some(ccx.tcx.map.local_def_id(it.id)), tcx.mk_bare_fn(tofd));
1451             ty::TypeScheme { ty: ty, generics: ty_generics }
1452         }
1453         hir::ItemTy(ref t, ref generics) => {
1454             let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
1455             let ty = ccx.icx(generics).to_ty(&ExplicitRscope, &**t);
1456             ty::TypeScheme { ty: ty, generics: ty_generics }
1457         }
1458         hir::ItemEnum(ref ei, ref generics) => {
1459             let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
1460             let substs = mk_item_substs(ccx, &ty_generics);
1461             let def = convert_enum_def(tcx, it, ei);
1462             let t = tcx.mk_enum(def, tcx.mk_substs(substs));
1463             ty::TypeScheme { ty: t, generics: ty_generics }
1464         }
1465         hir::ItemStruct(ref si, ref generics) => {
1466             let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
1467             let substs = mk_item_substs(ccx, &ty_generics);
1468             let def = convert_struct_def(tcx, it, si);
1469             let t = tcx.mk_struct(def, tcx.mk_substs(substs));
1470             ty::TypeScheme { ty: t, generics: ty_generics }
1471         }
1472         hir::ItemDefaultImpl(..) |
1473         hir::ItemTrait(..) |
1474         hir::ItemImpl(..) |
1475         hir::ItemMod(..) |
1476         hir::ItemForeignMod(..) |
1477         hir::ItemExternCrate(..) |
1478         hir::ItemUse(..) => {
1479             tcx.sess.span_bug(
1480                 it.span,
1481                 &format!("compute_type_scheme_of_item: unexpected item type: {:?}",
1482                          it.node));
1483         }
1484     }
1485 }
1486
1487 fn convert_typed_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1488                                 it: &hir::Item)
1489                                 -> (ty::TypeScheme<'tcx>, ty::GenericPredicates<'tcx>)
1490 {
1491     let tcx = ccx.tcx;
1492
1493     let tag = type_scheme_of_item(ccx, it);
1494     let scheme = TypeScheme { generics: tag.generics, ty: tag.ty };
1495     let predicates = match it.node {
1496         hir::ItemStatic(..) | hir::ItemConst(..) => {
1497             ty::GenericPredicates::empty()
1498         }
1499         hir::ItemFn(_, _, _, _, ref ast_generics, _) => {
1500             ty_generic_predicates_for_fn(ccx, ast_generics, &ty::GenericPredicates::empty())
1501         }
1502         hir::ItemTy(_, ref generics) => {
1503             ty_generic_predicates_for_type_or_impl(ccx, generics)
1504         }
1505         hir::ItemEnum(_, ref generics) => {
1506             ty_generic_predicates_for_type_or_impl(ccx, generics)
1507         }
1508         hir::ItemStruct(_, ref generics) => {
1509             ty_generic_predicates_for_type_or_impl(ccx, generics)
1510         }
1511         hir::ItemDefaultImpl(..) |
1512         hir::ItemTrait(..) |
1513         hir::ItemExternCrate(..) |
1514         hir::ItemUse(..) |
1515         hir::ItemImpl(..) |
1516         hir::ItemMod(..) |
1517         hir::ItemForeignMod(..) => {
1518             tcx.sess.span_bug(
1519                 it.span,
1520                 &format!("compute_type_scheme_of_item: unexpected item type: {:?}",
1521                          it.node));
1522         }
1523     };
1524
1525     let prev_predicates = tcx.predicates.borrow_mut().insert(ccx.tcx.map.local_def_id(it.id),
1526                                                              predicates.clone());
1527     assert!(prev_predicates.is_none());
1528
1529     // Debugging aid.
1530     if tcx.has_attr(ccx.tcx.map.local_def_id(it.id), "rustc_object_lifetime_default") {
1531         let object_lifetime_default_reprs: String =
1532             scheme.generics.types.iter()
1533                                  .map(|t| match t.object_lifetime_default {
1534                                      ty::ObjectLifetimeDefault::Specific(r) => r.to_string(),
1535                                      d => format!("{:?}", d),
1536                                  })
1537                                  .collect::<Vec<String>>()
1538                                  .join(",");
1539
1540         tcx.sess.span_err(it.span, &object_lifetime_default_reprs);
1541     }
1542
1543     return (scheme, predicates);
1544 }
1545
1546 fn type_scheme_of_foreign_item<'a, 'tcx>(
1547     ccx: &CrateCtxt<'a, 'tcx>,
1548     item: &hir::ForeignItem,
1549     abi: abi::Abi)
1550     -> ty::TypeScheme<'tcx>
1551 {
1552     let item_def_id = ccx.tcx.map.local_def_id(item.id);
1553     ccx.tcx.tcache.memoize(item_def_id, || {
1554         // NB. Since the `memoized` function enters a new task, and we
1555         // are giving this task access to the item `item`, we must
1556         // register a read.
1557         ccx.tcx.dep_graph.read(DepNode::Hir(item_def_id));
1558         compute_type_scheme_of_foreign_item(ccx, item, abi)
1559     })
1560 }
1561
1562 fn compute_type_scheme_of_foreign_item<'a, 'tcx>(
1563     ccx: &CrateCtxt<'a, 'tcx>,
1564     it: &hir::ForeignItem,
1565     abi: abi::Abi)
1566     -> ty::TypeScheme<'tcx>
1567 {
1568     match it.node {
1569         hir::ForeignItemFn(ref fn_decl, ref generics) => {
1570             compute_type_scheme_of_foreign_fn_decl(ccx, fn_decl, generics, abi)
1571         }
1572         hir::ForeignItemStatic(ref t, _) => {
1573             ty::TypeScheme {
1574                 generics: ty::Generics::empty(),
1575                 ty: ast_ty_to_ty(&ccx.icx(&()), &ExplicitRscope, t)
1576             }
1577         }
1578     }
1579 }
1580
1581 fn convert_foreign_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1582                                   it: &hir::ForeignItem)
1583 {
1584     // For reasons I cannot fully articulate, I do so hate the AST
1585     // map, and I regard each time that I use it as a personal and
1586     // moral failing, but at the moment it seems like the only
1587     // convenient way to extract the ABI. - ndm
1588     let tcx = ccx.tcx;
1589     let abi = tcx.map.get_foreign_abi(it.id);
1590
1591     let scheme = type_scheme_of_foreign_item(ccx, it, abi);
1592     write_ty_to_tcx(ccx.tcx, it.id, scheme.ty);
1593
1594     let predicates = match it.node {
1595         hir::ForeignItemFn(_, ref generics) => {
1596             ty_generic_predicates_for_fn(ccx, generics, &ty::GenericPredicates::empty())
1597         }
1598         hir::ForeignItemStatic(..) => {
1599             ty::GenericPredicates::empty()
1600         }
1601     };
1602
1603     let prev_predicates = tcx.predicates.borrow_mut().insert(ccx.tcx.map.local_def_id(it.id),
1604                                                              predicates);
1605     assert!(prev_predicates.is_none());
1606 }
1607
1608 fn ty_generics_for_type_or_impl<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1609                                           generics: &hir::Generics)
1610                                           -> ty::Generics<'tcx> {
1611     ty_generics(ccx, TypeSpace, generics, &ty::Generics::empty())
1612 }
1613
1614 fn ty_generic_predicates_for_type_or_impl<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1615                                                    generics: &hir::Generics)
1616                                                    -> ty::GenericPredicates<'tcx>
1617 {
1618     ty_generic_predicates(ccx, TypeSpace, generics, &ty::GenericPredicates::empty())
1619 }
1620
1621 fn ty_generics_for_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1622                                    trait_id: ast::NodeId,
1623                                    substs: &'tcx Substs<'tcx>,
1624                                    ast_generics: &hir::Generics)
1625                                    -> ty::Generics<'tcx>
1626 {
1627     debug!("ty_generics_for_trait(trait_id={:?}, substs={:?})",
1628            ccx.tcx.map.local_def_id(trait_id), substs);
1629
1630     let mut generics = ty_generics_for_type_or_impl(ccx, ast_generics);
1631
1632     // Add in the self type parameter.
1633     //
1634     // Something of a hack: use the node id for the trait, also as
1635     // the node id for the Self type parameter.
1636     let param_id = trait_id;
1637
1638     let parent = ccx.tcx.map.get_parent(param_id);
1639
1640     let def = ty::TypeParameterDef {
1641         space: SelfSpace,
1642         index: 0,
1643         name: special_idents::type_self.name,
1644         def_id: ccx.tcx.map.local_def_id(param_id),
1645         default_def_id: ccx.tcx.map.local_def_id(parent),
1646         default: None,
1647         object_lifetime_default: ty::ObjectLifetimeDefault::BaseDefault,
1648     };
1649
1650     ccx.tcx.ty_param_defs.borrow_mut().insert(param_id, def.clone());
1651
1652     generics.types.push(SelfSpace, def);
1653
1654     return generics;
1655 }
1656
1657 fn ty_generics_for_fn<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1658                                generics: &hir::Generics,
1659                                base_generics: &ty::Generics<'tcx>)
1660                                -> ty::Generics<'tcx>
1661 {
1662     ty_generics(ccx, FnSpace, generics, base_generics)
1663 }
1664
1665 fn ty_generic_predicates_for_fn<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1666                                          generics: &hir::Generics,
1667                                          base_predicates: &ty::GenericPredicates<'tcx>)
1668                                          -> ty::GenericPredicates<'tcx>
1669 {
1670     ty_generic_predicates(ccx, FnSpace, generics, base_predicates)
1671 }
1672
1673 // Add the Sized bound, unless the type parameter is marked as `?Sized`.
1674 fn add_unsized_bound<'tcx>(astconv: &AstConv<'tcx>,
1675                            bounds: &mut ty::BuiltinBounds,
1676                            ast_bounds: &[hir::TyParamBound],
1677                            span: Span)
1678 {
1679     let tcx = astconv.tcx();
1680
1681     // Try to find an unbound in bounds.
1682     let mut unbound = None;
1683     for ab in ast_bounds {
1684         if let &hir::TraitTyParamBound(ref ptr, hir::TraitBoundModifier::Maybe) = ab  {
1685             if unbound.is_none() {
1686                 assert!(ptr.bound_lifetimes.is_empty());
1687                 unbound = Some(ptr.trait_ref.clone());
1688             } else {
1689                 span_err!(tcx.sess, span, E0203,
1690                           "type parameter has more than one relaxed default \
1691                                                 bound, only one is supported");
1692             }
1693         }
1694     }
1695
1696     let kind_id = tcx.lang_items.require(SizedTraitLangItem);
1697     match unbound {
1698         Some(ref tpb) => {
1699             // FIXME(#8559) currently requires the unbound to be built-in.
1700             let trait_def_id = tcx.trait_ref_to_def_id(tpb);
1701             match kind_id {
1702                 Ok(kind_id) if trait_def_id != kind_id => {
1703                     tcx.sess.span_warn(span,
1704                                        "default bound relaxed for a type parameter, but \
1705                                        this does nothing because the given bound is not \
1706                                        a default. Only `?Sized` is supported");
1707                     tcx.try_add_builtin_trait(kind_id, bounds);
1708                 }
1709                 _ => {}
1710             }
1711         }
1712         _ if kind_id.is_ok() => {
1713             tcx.try_add_builtin_trait(kind_id.unwrap(), bounds);
1714         }
1715         // No lang item for Sized, so we can't add it as a bound.
1716         None => {}
1717     }
1718 }
1719
1720 /// Returns the early-bound lifetimes declared in this generics
1721 /// listing.  For anything other than fns/methods, this is just all
1722 /// the lifetimes that are declared. For fns or methods, we have to
1723 /// screen out those that do not appear in any where-clauses etc using
1724 /// `resolve_lifetime::early_bound_lifetimes`.
1725 fn early_bound_lifetimes_from_generics(space: ParamSpace,
1726                                        ast_generics: &hir::Generics)
1727                                        -> Vec<hir::LifetimeDef>
1728 {
1729     match space {
1730         SelfSpace | TypeSpace => ast_generics.lifetimes.to_vec(),
1731         FnSpace => resolve_lifetime::early_bound_lifetimes(ast_generics),
1732     }
1733 }
1734
1735 fn ty_generic_predicates<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1736                                   space: ParamSpace,
1737                                   ast_generics: &hir::Generics,
1738                                   base_predicates: &ty::GenericPredicates<'tcx>)
1739                                   -> ty::GenericPredicates<'tcx>
1740 {
1741     let tcx = ccx.tcx;
1742     let mut result = base_predicates.clone();
1743
1744     // Collect the predicates that were written inline by the user on each
1745     // type parameter (e.g., `<T:Foo>`).
1746     for (index, param) in ast_generics.ty_params.iter().enumerate() {
1747         let index = index as u32;
1748         let param_ty = ty::ParamTy::new(space, index, param.name).to_ty(ccx.tcx);
1749         let bounds = compute_bounds(&ccx.icx(&(base_predicates, ast_generics)),
1750                                     param_ty,
1751                                     &param.bounds,
1752                                     SizedByDefault::Yes,
1753                                     param.span);
1754         let predicates = bounds.predicates(ccx.tcx, param_ty);
1755         result.predicates.extend(space, predicates.into_iter());
1756     }
1757
1758     // Collect the region predicates that were declared inline as
1759     // well. In the case of parameters declared on a fn or method, we
1760     // have to be careful to only iterate over early-bound regions.
1761     let early_lifetimes = early_bound_lifetimes_from_generics(space, ast_generics);
1762     for (index, param) in early_lifetimes.iter().enumerate() {
1763         let index = index as u32;
1764         let region =
1765             ty::ReEarlyBound(ty::EarlyBoundRegion {
1766                 space: space,
1767                 index: index,
1768                 name: param.lifetime.name
1769             });
1770         for bound in &param.bounds {
1771             let bound_region = ast_region_to_region(ccx.tcx, bound);
1772             let outlives = ty::Binder(ty::OutlivesPredicate(region, bound_region));
1773             result.predicates.push(space, outlives.to_predicate());
1774         }
1775     }
1776
1777     // Add in the bounds that appear in the where-clause
1778     let where_clause = &ast_generics.where_clause;
1779     for predicate in &where_clause.predicates {
1780         match predicate {
1781             &hir::WherePredicate::BoundPredicate(ref bound_pred) => {
1782                 let ty = ast_ty_to_ty(&ccx.icx(&(base_predicates, ast_generics)),
1783                                       &ExplicitRscope,
1784                                       &*bound_pred.bounded_ty);
1785
1786                 for bound in bound_pred.bounds.iter() {
1787                     match bound {
1788                         &hir::TyParamBound::TraitTyParamBound(ref poly_trait_ref, _) => {
1789                             let mut projections = Vec::new();
1790
1791                             let trait_ref =
1792                                 conv_poly_trait_ref(&ccx.icx(&(base_predicates, ast_generics)),
1793                                                     ty,
1794                                                     poly_trait_ref,
1795                                                     &mut projections);
1796
1797                             result.predicates.push(space, trait_ref.to_predicate());
1798
1799                             for projection in &projections {
1800                                 result.predicates.push(space, projection.to_predicate());
1801                             }
1802                         }
1803
1804                         &hir::TyParamBound::RegionTyParamBound(ref lifetime) => {
1805                             let region = ast_region_to_region(tcx, lifetime);
1806                             let pred = ty::Binder(ty::OutlivesPredicate(ty, region));
1807                             result.predicates.push(space, ty::Predicate::TypeOutlives(pred))
1808                         }
1809                     }
1810                 }
1811             }
1812
1813             &hir::WherePredicate::RegionPredicate(ref region_pred) => {
1814                 let r1 = ast_region_to_region(tcx, &region_pred.lifetime);
1815                 for bound in &region_pred.bounds {
1816                     let r2 = ast_region_to_region(tcx, bound);
1817                     let pred = ty::Binder(ty::OutlivesPredicate(r1, r2));
1818                     result.predicates.push(space, ty::Predicate::RegionOutlives(pred))
1819                 }
1820             }
1821
1822             &hir::WherePredicate::EqPredicate(ref eq_pred) => {
1823                 // FIXME(#20041)
1824                 tcx.sess.span_bug(eq_pred.span,
1825                                     "Equality constraints are not yet \
1826                                         implemented (#20041)")
1827             }
1828         }
1829     }
1830
1831     return result;
1832 }
1833
1834 fn ty_generics<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1835                         space: ParamSpace,
1836                         ast_generics: &hir::Generics,
1837                         base_generics: &ty::Generics<'tcx>)
1838                         -> ty::Generics<'tcx>
1839 {
1840     let tcx = ccx.tcx;
1841     let mut result = base_generics.clone();
1842
1843     let early_lifetimes = early_bound_lifetimes_from_generics(space, ast_generics);
1844     for (i, l) in early_lifetimes.iter().enumerate() {
1845         let bounds = l.bounds.iter()
1846                              .map(|l| ast_region_to_region(tcx, l))
1847                              .collect();
1848         let def = ty::RegionParameterDef { name: l.lifetime.name,
1849                                            space: space,
1850                                            index: i as u32,
1851                                            def_id: ccx.tcx.map.local_def_id(l.lifetime.id),
1852                                            bounds: bounds };
1853         result.regions.push(space, def);
1854     }
1855
1856     assert!(result.types.is_empty_in(space));
1857
1858     // Now create the real type parameters.
1859     for i in 0..ast_generics.ty_params.len() {
1860         let def = get_or_create_type_parameter_def(ccx, ast_generics, space, i as u32);
1861         debug!("ty_generics: def for type param: {:?}, {:?}", def, space);
1862         result.types.push(space, def);
1863     }
1864
1865     result
1866 }
1867
1868 fn convert_default_type_parameter<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1869                                             path: &P<hir::Ty>,
1870                                             space: ParamSpace,
1871                                             index: u32)
1872                                             -> Ty<'tcx>
1873 {
1874     let ty = ast_ty_to_ty(&ccx.icx(&()), &ExplicitRscope, &path);
1875
1876     for leaf_ty in ty.walk() {
1877         if let ty::TyParam(p) = leaf_ty.sty {
1878             if p.space == space && p.idx >= index {
1879                 span_err!(ccx.tcx.sess, path.span, E0128,
1880                           "type parameters with a default cannot use \
1881                            forward declared identifiers");
1882
1883                 return ccx.tcx.types.err
1884             }
1885         }
1886     }
1887
1888     ty
1889 }
1890
1891 fn get_or_create_type_parameter_def<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1892                                              ast_generics: &hir::Generics,
1893                                              space: ParamSpace,
1894                                              index: u32)
1895                                              -> ty::TypeParameterDef<'tcx>
1896 {
1897     let param = &ast_generics.ty_params[index as usize];
1898
1899     let tcx = ccx.tcx;
1900     match tcx.ty_param_defs.borrow().get(&param.id) {
1901         Some(d) => { return d.clone(); }
1902         None => { }
1903     }
1904
1905     let default = param.default.as_ref().map(
1906         |def| convert_default_type_parameter(ccx, def, space, index)
1907     );
1908
1909     let object_lifetime_default =
1910         compute_object_lifetime_default(ccx, param.id,
1911                                         &param.bounds, &ast_generics.where_clause);
1912
1913     let parent = tcx.map.get_parent(param.id);
1914
1915     if space != TypeSpace && default.is_some() {
1916         if !tcx.sess.features.borrow().default_type_parameter_fallback {
1917             tcx.sess.add_lint(
1918                 lint::builtin::INVALID_TYPE_PARAM_DEFAULT,
1919                 param.id,
1920                 param.span,
1921                 format!("defaults for type parameters are only allowed on type definitions, \
1922                          like `struct` or `enum`"));
1923         }
1924     }
1925
1926     let def = ty::TypeParameterDef {
1927         space: space,
1928         index: index,
1929         name: param.name,
1930         def_id: ccx.tcx.map.local_def_id(param.id),
1931         default_def_id: ccx.tcx.map.local_def_id(parent),
1932         default: default,
1933         object_lifetime_default: object_lifetime_default,
1934     };
1935
1936     tcx.ty_param_defs.borrow_mut().insert(param.id, def.clone());
1937
1938     def
1939 }
1940
1941 /// Scan the bounds and where-clauses on a parameter to extract bounds
1942 /// of the form `T:'a` so as to determine the `ObjectLifetimeDefault`.
1943 /// This runs as part of computing the minimal type scheme, so we
1944 /// intentionally avoid just asking astconv to convert all the where
1945 /// clauses into a `ty::Predicate`. This is because that could induce
1946 /// artificial cycles.
1947 fn compute_object_lifetime_default<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1948                                             param_id: ast::NodeId,
1949                                             param_bounds: &[hir::TyParamBound],
1950                                             where_clause: &hir::WhereClause)
1951                                             -> ty::ObjectLifetimeDefault
1952 {
1953     let inline_bounds = from_bounds(ccx, param_bounds);
1954     let where_bounds = from_predicates(ccx, param_id, &where_clause.predicates);
1955     let all_bounds: HashSet<_> = inline_bounds.into_iter()
1956                                               .chain(where_bounds)
1957                                               .collect();
1958     return if all_bounds.len() > 1 {
1959         ty::ObjectLifetimeDefault::Ambiguous
1960     } else if all_bounds.len() == 0 {
1961         ty::ObjectLifetimeDefault::BaseDefault
1962     } else {
1963         ty::ObjectLifetimeDefault::Specific(
1964             all_bounds.into_iter().next().unwrap())
1965     };
1966
1967     fn from_bounds<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1968                             bounds: &[hir::TyParamBound])
1969                             -> Vec<ty::Region>
1970     {
1971         bounds.iter()
1972               .filter_map(|bound| {
1973                   match *bound {
1974                       hir::TraitTyParamBound(..) =>
1975                           None,
1976                       hir::RegionTyParamBound(ref lifetime) =>
1977                           Some(astconv::ast_region_to_region(ccx.tcx, lifetime)),
1978                   }
1979               })
1980               .collect()
1981     }
1982
1983     fn from_predicates<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1984                                 param_id: ast::NodeId,
1985                                 predicates: &[hir::WherePredicate])
1986                                 -> Vec<ty::Region>
1987     {
1988         predicates.iter()
1989                   .flat_map(|predicate| {
1990                       match *predicate {
1991                           hir::WherePredicate::BoundPredicate(ref data) => {
1992                               if data.bound_lifetimes.is_empty() &&
1993                                   is_param(ccx.tcx, &data.bounded_ty, param_id)
1994                               {
1995                                   from_bounds(ccx, &data.bounds).into_iter()
1996                               } else {
1997                                   Vec::new().into_iter()
1998                               }
1999                           }
2000                           hir::WherePredicate::RegionPredicate(..) |
2001                           hir::WherePredicate::EqPredicate(..) => {
2002                               Vec::new().into_iter()
2003                           }
2004                       }
2005                   })
2006                   .collect()
2007     }
2008 }
2009
2010 enum SizedByDefault { Yes, No, }
2011
2012 /// Translate the AST's notion of ty param bounds (which are an enum consisting of a newtyped Ty or
2013 /// a region) to ty's notion of ty param bounds, which can either be user-defined traits, or the
2014 /// built-in trait (formerly known as kind): Send.
2015 fn compute_bounds<'tcx>(astconv: &AstConv<'tcx>,
2016                         param_ty: ty::Ty<'tcx>,
2017                         ast_bounds: &[hir::TyParamBound],
2018                         sized_by_default: SizedByDefault,
2019                         span: Span)
2020                         -> astconv::Bounds<'tcx>
2021 {
2022     let mut bounds =
2023         conv_param_bounds(astconv,
2024                           span,
2025                           param_ty,
2026                           ast_bounds);
2027
2028     if let SizedByDefault::Yes = sized_by_default {
2029         add_unsized_bound(astconv,
2030                           &mut bounds.builtin_bounds,
2031                           ast_bounds,
2032                           span);
2033     }
2034
2035     bounds.trait_bounds.sort_by(|a,b| a.def_id().cmp(&b.def_id()));
2036
2037     bounds
2038 }
2039
2040 /// Converts a specific TyParamBound from the AST into a set of
2041 /// predicates that apply to the self-type. A vector is returned
2042 /// because this can be anywhere from 0 predicates (`T:?Sized` adds no
2043 /// predicates) to 1 (`T:Foo`) to many (`T:Bar<X=i32>` adds `T:Bar`
2044 /// and `<T as Bar>::X == i32`).
2045 fn predicates_from_bound<'tcx>(astconv: &AstConv<'tcx>,
2046                                param_ty: Ty<'tcx>,
2047                                bound: &hir::TyParamBound)
2048                                -> Vec<ty::Predicate<'tcx>>
2049 {
2050     match *bound {
2051         hir::TraitTyParamBound(ref tr, hir::TraitBoundModifier::None) => {
2052             let mut projections = Vec::new();
2053             let pred = conv_poly_trait_ref(astconv, param_ty, tr, &mut projections);
2054             projections.into_iter()
2055                        .map(|p| p.to_predicate())
2056                        .chain(Some(pred.to_predicate()))
2057                        .collect()
2058         }
2059         hir::RegionTyParamBound(ref lifetime) => {
2060             let region = ast_region_to_region(astconv.tcx(), lifetime);
2061             let pred = ty::Binder(ty::OutlivesPredicate(param_ty, region));
2062             vec![ty::Predicate::TypeOutlives(pred)]
2063         }
2064         hir::TraitTyParamBound(_, hir::TraitBoundModifier::Maybe) => {
2065             Vec::new()
2066         }
2067     }
2068 }
2069
2070 fn conv_poly_trait_ref<'tcx>(astconv: &AstConv<'tcx>,
2071                              param_ty: Ty<'tcx>,
2072                              trait_ref: &hir::PolyTraitRef,
2073                              projections: &mut Vec<ty::PolyProjectionPredicate<'tcx>>)
2074                              -> ty::PolyTraitRef<'tcx>
2075 {
2076     astconv::instantiate_poly_trait_ref(astconv,
2077                                         &ExplicitRscope,
2078                                         trait_ref,
2079                                         Some(param_ty),
2080                                         projections)
2081 }
2082
2083 fn conv_param_bounds<'a,'tcx>(astconv: &AstConv<'tcx>,
2084                               span: Span,
2085                               param_ty: ty::Ty<'tcx>,
2086                               ast_bounds: &[hir::TyParamBound])
2087                               -> astconv::Bounds<'tcx>
2088 {
2089     let tcx = astconv.tcx();
2090     let astconv::PartitionedBounds {
2091         builtin_bounds,
2092         trait_bounds,
2093         region_bounds
2094     } = astconv::partition_bounds(tcx, span, &ast_bounds);
2095
2096     let mut projection_bounds = Vec::new();
2097
2098     let trait_bounds: Vec<ty::PolyTraitRef> =
2099         trait_bounds.iter()
2100                     .map(|bound| conv_poly_trait_ref(astconv,
2101                                                      param_ty,
2102                                                      *bound,
2103                                                      &mut projection_bounds))
2104                     .collect();
2105
2106     let region_bounds: Vec<ty::Region> =
2107         region_bounds.into_iter()
2108                      .map(|r| ast_region_to_region(tcx, r))
2109                      .collect();
2110
2111     astconv::Bounds {
2112         region_bounds: region_bounds,
2113         builtin_bounds: builtin_bounds,
2114         trait_bounds: trait_bounds,
2115         projection_bounds: projection_bounds,
2116     }
2117 }
2118
2119 fn compute_type_scheme_of_foreign_fn_decl<'a, 'tcx>(
2120     ccx: &CrateCtxt<'a, 'tcx>,
2121     decl: &hir::FnDecl,
2122     ast_generics: &hir::Generics,
2123     abi: abi::Abi)
2124     -> ty::TypeScheme<'tcx>
2125 {
2126     for i in &decl.inputs {
2127         match (*i).pat.node {
2128             hir::PatIdent(_, _, _) => (),
2129             hir::PatWild => (),
2130             _ => {
2131                 span_err!(ccx.tcx.sess, (*i).pat.span, E0130,
2132                           "patterns aren't allowed in foreign function declarations");
2133             }
2134         }
2135     }
2136
2137     let ty_generics = ty_generics_for_fn(ccx, ast_generics, &ty::Generics::empty());
2138
2139     let rb = BindingRscope::new();
2140     let input_tys = decl.inputs
2141                         .iter()
2142                         .map(|a| ty_of_arg(&ccx.icx(ast_generics), &rb, a, None))
2143                         .collect();
2144
2145     let output = match decl.output {
2146         hir::Return(ref ty) =>
2147             ty::FnConverging(ast_ty_to_ty(&ccx.icx(ast_generics), &rb, &**ty)),
2148         hir::DefaultReturn(..) =>
2149             ty::FnConverging(ccx.tcx.mk_nil()),
2150         hir::NoReturn(..) =>
2151             ty::FnDiverging
2152     };
2153
2154     let t_fn = ccx.tcx.mk_fn(None,
2155         ccx.tcx.mk_bare_fn(ty::BareFnTy {
2156             abi: abi,
2157             unsafety: hir::Unsafety::Unsafe,
2158             sig: ty::Binder(ty::FnSig {inputs: input_tys,
2159                                        output: output,
2160                                        variadic: decl.variadic}),
2161         }));
2162
2163     ty::TypeScheme {
2164         generics: ty_generics,
2165         ty: t_fn
2166     }
2167 }
2168
2169 fn mk_item_substs<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
2170                             ty_generics: &ty::Generics<'tcx>)
2171                             -> Substs<'tcx>
2172 {
2173     let types =
2174         ty_generics.types.map(
2175             |def| ccx.tcx.mk_param_from_def(def));
2176
2177     let regions =
2178         ty_generics.regions.map(
2179             |def| def.to_early_bound_region());
2180
2181     Substs::new(types, regions)
2182 }
2183
2184 /// Checks that all the type parameters on an impl
2185 fn enforce_impl_params_are_constrained<'tcx>(tcx: &ty::ctxt<'tcx>,
2186                                              ast_generics: &hir::Generics,
2187                                              impl_predicates: &mut ty::GenericPredicates<'tcx>,
2188                                              impl_def_id: DefId)
2189 {
2190     let impl_scheme = tcx.lookup_item_type(impl_def_id);
2191     let impl_trait_ref = tcx.impl_trait_ref(impl_def_id);
2192
2193     assert!(impl_predicates.predicates.is_empty_in(FnSpace));
2194     assert!(impl_predicates.predicates.is_empty_in(SelfSpace));
2195
2196     // The trait reference is an input, so find all type parameters
2197     // reachable from there, to start (if this is an inherent impl,
2198     // then just examine the self type).
2199     let mut input_parameters: HashSet<_> =
2200         ctp::parameters_for_type(impl_scheme.ty, false).into_iter().collect();
2201     if let Some(ref trait_ref) = impl_trait_ref {
2202         input_parameters.extend(ctp::parameters_for_trait_ref(trait_ref, false));
2203     }
2204
2205     ctp::setup_constraining_predicates(tcx,
2206                                        impl_predicates.predicates.get_mut_slice(TypeSpace),
2207                                        impl_trait_ref,
2208                                        &mut input_parameters);
2209
2210     for (index, ty_param) in ast_generics.ty_params.iter().enumerate() {
2211         let param_ty = ty::ParamTy { space: TypeSpace,
2212                                      idx: index as u32,
2213                                      name: ty_param.name };
2214         if !input_parameters.contains(&ctp::Parameter::Type(param_ty)) {
2215             report_unused_parameter(tcx, ty_param.span, "type", &param_ty.to_string());
2216         }
2217     }
2218 }
2219
2220 fn enforce_impl_lifetimes_are_constrained<'tcx>(tcx: &ty::ctxt<'tcx>,
2221                                                 ast_generics: &hir::Generics,
2222                                                 impl_def_id: DefId,
2223                                                 impl_items: &[hir::ImplItem])
2224 {
2225     // Every lifetime used in an associated type must be constrained.
2226     let impl_scheme = tcx.lookup_item_type(impl_def_id);
2227     let impl_predicates = tcx.lookup_predicates(impl_def_id);
2228     let impl_trait_ref = tcx.impl_trait_ref(impl_def_id);
2229
2230     let mut input_parameters: HashSet<_> =
2231         ctp::parameters_for_type(impl_scheme.ty, false).into_iter().collect();
2232     if let Some(ref trait_ref) = impl_trait_ref {
2233         input_parameters.extend(ctp::parameters_for_trait_ref(trait_ref, false));
2234     }
2235     ctp::identify_constrained_type_params(tcx,
2236         &impl_predicates.predicates.as_slice(), impl_trait_ref, &mut input_parameters);
2237
2238     let lifetimes_in_associated_types: HashSet<_> =
2239         impl_items.iter()
2240                   .map(|item| tcx.impl_or_trait_item(tcx.map.local_def_id(item.id)))
2241                   .filter_map(|item| match item {
2242                       ty::TypeTraitItem(ref assoc_ty) => assoc_ty.ty,
2243                       ty::ConstTraitItem(..) | ty::MethodTraitItem(..) => None
2244                   })
2245                   .flat_map(|ty| ctp::parameters_for_type(ty, true))
2246                   .filter_map(|p| match p {
2247                       ctp::Parameter::Type(_) => None,
2248                       ctp::Parameter::Region(r) => Some(r),
2249                   })
2250                   .collect();
2251
2252     for (index, lifetime_def) in ast_generics.lifetimes.iter().enumerate() {
2253         let region = ty::EarlyBoundRegion { space: TypeSpace,
2254                                             index: index as u32,
2255                                             name: lifetime_def.lifetime.name };
2256         if
2257             lifetimes_in_associated_types.contains(&region) && // (*)
2258             !input_parameters.contains(&ctp::Parameter::Region(region))
2259         {
2260             report_unused_parameter(tcx, lifetime_def.lifetime.span,
2261                                     "lifetime", &region.name.to_string());
2262         }
2263     }
2264
2265     // (*) This is a horrible concession to reality. I think it'd be
2266     // better to just ban unconstrianed lifetimes outright, but in
2267     // practice people do non-hygenic macros like:
2268     //
2269     // ```
2270     // macro_rules! __impl_slice_eq1 {
2271     //     ($Lhs: ty, $Rhs: ty, $Bound: ident) => {
2272     //         impl<'a, 'b, A: $Bound, B> PartialEq<$Rhs> for $Lhs where A: PartialEq<B> {
2273     //            ....
2274     //         }
2275     //     }
2276     // }
2277     // ```
2278     //
2279     // In a concession to backwards compatbility, we continue to
2280     // permit those, so long as the lifetimes aren't used in
2281     // associated types. I believe this is sound, because lifetimes
2282     // used elsewhere are not projected back out.
2283 }
2284
2285 fn report_unused_parameter(tcx: &ty::ctxt,
2286                            span: Span,
2287                            kind: &str,
2288                            name: &str)
2289 {
2290     span_err!(tcx.sess, span, E0207,
2291               "the {} parameter `{}` is not constrained by the \
2292                impl trait, self type, or predicates",
2293               kind, name);
2294 }