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