src/librustc_typeck/collect.rs

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