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