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