src/librustc_typeck/check/wf.rs

   1 // Copyright 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 use astconv::AstConv;
  12 use check::{FnCtxt, Inherited, blank_fn_ctxt, regionck};
  13 use constrained_type_params::{identify_constrained_type_params, Parameter};
  14 use CrateCtxt;
  15 use middle::region;
  16 use middle::subst::{self, TypeSpace, FnSpace, ParamSpace, SelfSpace};
  17 use middle::traits;
  18 use middle::ty::{self, Ty};
  19 use middle::ty_fold::{TypeFolder, TypeFoldable, super_fold_ty};
  20
  21 use std::cell::RefCell;
  22 use std::collections::HashSet;
  23 use syntax::ast;
  24 use syntax::ast_util::local_def;
  25 use syntax::codemap::{DUMMY_SP, Span};
  26 use syntax::parse::token::special_idents;
  27 use syntax::visit;
  28 use syntax::visit::Visitor;
  29
  30 pub struct CheckTypeWellFormedVisitor<'ccx, 'tcx:'ccx> {
  31     ccx: &'ccx CrateCtxt<'ccx, 'tcx>,
  32     cache: HashSet<Ty<'tcx>>
  33 }
  34
  35 impl<'ccx, 'tcx> CheckTypeWellFormedVisitor<'ccx, 'tcx> {
  36     pub fn new(ccx: &'ccx CrateCtxt<'ccx, 'tcx>) -> CheckTypeWellFormedVisitor<'ccx, 'tcx> {
  37         CheckTypeWellFormedVisitor { ccx: ccx, cache: HashSet::new() }
  38     }
  39
  40     fn tcx(&self) -> &ty::ctxt<'tcx> {
  41         self.ccx.tcx
  42     }
  43
  44     /// Checks that the field types (in a struct def'n) or argument types (in an enum def'n) are
  45     /// well-formed, meaning that they do not require any constraints not declared in the struct
  46     /// definition itself. For example, this definition would be illegal:
  47     ///
  48     ///     struct Ref<'a, T> { x: &'a T }
  49     ///
  50     /// because the type did not declare that `T:'a`.
  51     ///
  52     /// We do this check as a pre-pass before checking fn bodies because if these constraints are
  53     /// not included it frequently leads to confusing errors in fn bodies. So it's better to check
  54     /// the types first.
  55     fn check_item_well_formed(&mut self, item: &ast::Item) {
  56         let ccx = self.ccx;
  57         debug!("check_item_well_formed(it.id={}, it.ident={})",
  58                item.id,
  59                ccx.tcx.item_path_str(local_def(item.id)));
  60
  61         match item.node {
  62             /// Right now we check that every default trait implementation
  63             /// has an implementation of itself. Basically, a case like:
  64             ///
  65             /// `impl Trait for T {}`
  66             ///
  67             /// has a requirement of `T: Trait` which was required for default
  68             /// method implementations. Although this could be improved now that
  69             /// there's a better infrastructure in place for this, it's being left
  70             /// for a follow-up work.
  71             ///
  72             /// Since there's such a requirement, we need to check *just* positive
  73             /// implementations, otherwise things like:
  74             ///
  75             /// impl !Send for T {}
  76             ///
  77             /// won't be allowed unless there's an *explicit* implementation of `Send`
  78             /// for `T`
  79             ast::ItemImpl(_, ast::ImplPolarity::Positive, _, _, _, _) => {
  80                 self.check_impl(item);
  81             }
  82             ast::ItemImpl(_, ast::ImplPolarity::Negative, _, Some(_), _, _) => {
  83                 let trait_ref = ccx.tcx.impl_trait_ref(local_def(item.id)).unwrap();
  84                 ccx.tcx.populate_implementations_for_trait_if_necessary(trait_ref.def_id);
  85                 match ccx.tcx.lang_items.to_builtin_kind(trait_ref.def_id) {
  86                     Some(ty::BoundSend) | Some(ty::BoundSync) => {}
  87                     Some(_) | None => {
  88                         if !ccx.tcx.trait_has_default_impl(trait_ref.def_id) {
  89                             span_err!(ccx.tcx.sess, item.span, E0192,
  90                                       "negative impls are only allowed for traits with \
  91                                        default impls (e.g., `Send` and `Sync`)")
  92                         }
  93                     }
  94                 }
  95             }
  96             ast::ItemFn(..) => {
  97                 self.check_item_type(item);
  98             }
  99             ast::ItemStatic(..) => {
 100                 self.check_item_type(item);
 101             }
 102             ast::ItemConst(..) => {
 103                 self.check_item_type(item);
 104             }
 105             ast::ItemStruct(ref struct_def, ref ast_generics) => {
 106                 self.check_type_defn(item, |fcx| {
 107                     vec![struct_variant(fcx, &**struct_def)]
 108                 });
 109
 110                 self.check_variances_for_type_defn(item, ast_generics);
 111             }
 112             ast::ItemEnum(ref enum_def, ref ast_generics) => {
 113                 self.check_type_defn(item, |fcx| {
 114                     enum_variants(fcx, enum_def)
 115                 });
 116
 117                 self.check_variances_for_type_defn(item, ast_generics);
 118             }
 119             ast::ItemTrait(_, _, _, ref items) => {
 120                 let trait_predicates =
 121                     ccx.tcx.lookup_predicates(local_def(item.id));
 122                 reject_non_type_param_bounds(ccx.tcx, item.span, &trait_predicates);
 123                 if ccx.tcx.trait_has_default_impl(local_def(item.id)) {
 124                     if !items.is_empty() {
 125                         span_err!(ccx.tcx.sess, item.span, E0380,
 126                                   "traits with default impls (`e.g. unsafe impl \
 127                                   Trait for ..`) must have no methods or associated items")
 128                     }
 129                 }
 130             }
 131             _ => {}
 132         }
 133     }
 134
 135     fn with_fcx<F>(&mut self, item: &ast::Item, mut f: F) where
 136         F: for<'fcx> FnMut(&mut CheckTypeWellFormedVisitor<'ccx, 'tcx>, &FnCtxt<'fcx, 'tcx>),
 137     {
 138         let ccx = self.ccx;
 139         let item_def_id = local_def(item.id);
 140         let type_scheme = ccx.tcx.lookup_item_type(item_def_id);
 141         let type_predicates = ccx.tcx.lookup_predicates(item_def_id);
 142         reject_non_type_param_bounds(ccx.tcx, item.span, &type_predicates);
 143         let param_env = ccx.tcx.construct_parameter_environment(item.span,
 144                                                                 &type_scheme.generics,
 145                                                                 &type_predicates,
 146                                                                 item.id);
 147         let tables = RefCell::new(ty::Tables::empty());
 148         let inh = Inherited::new(ccx.tcx, &tables, param_env);
 149         let fcx = blank_fn_ctxt(ccx, &inh, ty::FnConverging(type_scheme.ty), item.id);
 150         f(self, &fcx);
 151         fcx.select_all_obligations_or_error();
 152         regionck::regionck_item(&fcx, item);
 153     }
 154
 155     /// In a type definition, we check that to ensure that the types of the fields are well-formed.
 156     fn check_type_defn<F>(&mut self, item: &ast::Item, mut lookup_fields: F) where
 157         F: for<'fcx> FnMut(&FnCtxt<'fcx, 'tcx>) -> Vec<AdtVariant<'tcx>>,
 158     {
 159         self.with_fcx(item, |this, fcx| {
 160             let variants = lookup_fields(fcx);
 161             let mut bounds_checker = BoundsChecker::new(fcx,
 162                                                         item.id,
 163                                                         Some(&mut this.cache));
 164             debug!("check_type_defn at bounds_checker.scope: {:?}", bounds_checker.scope);
 165
 166             for variant in &variants {
 167                 for field in &variant.fields {
 168                     // Regions are checked below.
 169                     bounds_checker.check_traits_in_ty(field.ty, field.span);
 170                 }
 171
 172                 // For DST, all intermediate types must be sized.
 173                 if let Some((_, fields)) = variant.fields.split_last() {
 174                     for field in fields {
 175                         fcx.register_builtin_bound(
 176                             field.ty,
 177                             ty::BoundSized,
 178                             traits::ObligationCause::new(field.span,
 179                                                          fcx.body_id,
 180                                                          traits::FieldSized));
 181                     }
 182                 }
 183             }
 184
 185             let field_tys: Vec<Ty> =
 186                 variants.iter().flat_map(|v| v.fields.iter().map(|f| f.ty)).collect();
 187
 188             regionck::regionck_ensure_component_tys_wf(
 189                 fcx, item.span, &field_tys);
 190         });
 191     }
 192
 193     fn check_item_type(&mut self,
 194                        item: &ast::Item)
 195     {
 196         self.with_fcx(item, |this, fcx| {
 197             let mut bounds_checker = BoundsChecker::new(fcx,
 198                                                         item.id,
 199                                                         Some(&mut this.cache));
 200             debug!("check_item_type at bounds_checker.scope: {:?}", bounds_checker.scope);
 201
 202             let type_scheme = fcx.tcx().lookup_item_type(local_def(item.id));
 203             let item_ty = fcx.instantiate_type_scheme(item.span,
 204                                                       &fcx.inh
 205                                                           .infcx
 206                                                           .parameter_environment
 207                                                           .free_substs,
 208                                                       &type_scheme.ty);
 209
 210             bounds_checker.check_traits_in_ty(item_ty, item.span);
 211         });
 212     }
 213
 214     fn check_impl(&mut self,
 215                   item: &ast::Item)
 216     {
 217         self.with_fcx(item, |this, fcx| {
 218             let mut bounds_checker = BoundsChecker::new(fcx,
 219                                                         item.id,
 220                                                         Some(&mut this.cache));
 221             debug!("check_impl at bounds_checker.scope: {:?}", bounds_checker.scope);
 222
 223             // Find the impl self type as seen from the "inside" --
 224             // that is, with all type parameters converted from bound
 225             // to free.
 226             let self_ty = fcx.tcx().node_id_to_type(item.id);
 227             let self_ty = fcx.instantiate_type_scheme(item.span,
 228                                                       &fcx.inh
 229                                                           .infcx
 230                                                           .parameter_environment
 231                                                           .free_substs,
 232                                                       &self_ty);
 233
 234             bounds_checker.check_traits_in_ty(self_ty, item.span);
 235
 236             // Similarly, obtain an "inside" reference to the trait
 237             // that the impl implements.
 238             let trait_ref = match fcx.tcx().impl_trait_ref(local_def(item.id)) {
 239                 None => { return; }
 240                 Some(t) => { t }
 241             };
 242
 243             let trait_ref = fcx.instantiate_type_scheme(item.span,
 244                                                         &fcx.inh
 245                                                             .infcx
 246                                                             .parameter_environment
 247                                                             .free_substs,
 248                                                         &trait_ref);
 249
 250             // We are stricter on the trait-ref in an impl than the
 251             // self-type.  In particular, we enforce region
 252             // relationships. The reason for this is that (at least
 253             // presently) "applying" an impl does not require that the
 254             // application site check the well-formedness constraints on the
 255             // trait reference. Instead, this is done at the impl site.
 256             // Arguably this is wrong and we should treat the trait-reference
 257             // the same way as we treat the self-type.
 258             bounds_checker.check_trait_ref(&trait_ref, item.span);
 259
 260             let cause =
 261                 traits::ObligationCause::new(
 262                     item.span,
 263                     fcx.body_id,
 264                     traits::ItemObligation(trait_ref.def_id));
 265
 266             // Find the supertrait bounds. This will add `int:Bar`.
 267             let poly_trait_ref = ty::Binder(trait_ref);
 268             let predicates = fcx.tcx().lookup_super_predicates(poly_trait_ref.def_id());
 269             let predicates = predicates.instantiate_supertrait(fcx.tcx(), &poly_trait_ref);
 270             let predicates = {
 271                 let selcx = &mut traits::SelectionContext::new(fcx.infcx());
 272                 traits::normalize(selcx, cause.clone(), &predicates)
 273             };
 274             for predicate in predicates.value.predicates {
 275                 fcx.register_predicate(traits::Obligation::new(cause.clone(), predicate));
 276             }
 277             for obligation in predicates.obligations {
 278                 fcx.register_predicate(obligation);
 279             }
 280         });
 281     }
 282
 283     fn check_variances_for_type_defn(&self,
 284                                      item: &ast::Item,
 285                                      ast_generics: &ast::Generics)
 286     {
 287         let item_def_id = local_def(item.id);
 288         let ty_predicates = self.tcx().lookup_predicates(item_def_id);
 289         let variances = self.tcx().item_variances(item_def_id);
 290
 291         let mut constrained_parameters: HashSet<_> =
 292             variances.types
 293                      .iter_enumerated()
 294                      .filter(|&(_, _, &variance)| variance != ty::Bivariant)
 295                      .map(|(space, index, _)| self.param_ty(ast_generics, space, index))
 296                      .map(|p| Parameter::Type(p))
 297                      .collect();
 298
 299         identify_constrained_type_params(self.tcx(),
 300                                          ty_predicates.predicates.as_slice(),
 301                                          None,
 302                                          &mut constrained_parameters);
 303
 304         for (space, index, _) in variances.types.iter_enumerated() {
 305             let param_ty = self.param_ty(ast_generics, space, index);
 306             if constrained_parameters.contains(&Parameter::Type(param_ty)) {
 307                 continue;
 308             }
 309             let span = self.ty_param_span(ast_generics, item, space, index);
 310             self.report_bivariance(span, param_ty.name);
 311         }
 312
 313         for (space, index, &variance) in variances.regions.iter_enumerated() {
 314             if variance != ty::Bivariant {
 315                 continue;
 316             }
 317
 318             assert_eq!(space, TypeSpace);
 319             let span = ast_generics.lifetimes[index].lifetime.span;
 320             let name = ast_generics.lifetimes[index].lifetime.name;
 321             self.report_bivariance(span, name);
 322         }
 323     }
 324
 325     fn param_ty(&self,
 326                 ast_generics: &ast::Generics,
 327                 space: ParamSpace,
 328                 index: usize)
 329                 -> ty::ParamTy
 330     {
 331         let name = match space {
 332             TypeSpace => ast_generics.ty_params[index].ident.name,
 333             SelfSpace => special_idents::type_self.name,
 334             FnSpace => self.tcx().sess.bug("Fn space occupied?"),
 335         };
 336
 337         ty::ParamTy { space: space, idx: index as u32, name: name }
 338     }
 339
 340     fn ty_param_span(&self,
 341                      ast_generics: &ast::Generics,
 342                      item: &ast::Item,
 343                      space: ParamSpace,
 344                      index: usize)
 345                      -> Span
 346     {
 347         match space {
 348             TypeSpace => ast_generics.ty_params[index].span,
 349             SelfSpace => item.span,
 350             FnSpace => self.tcx().sess.span_bug(item.span, "Fn space occupied?"),
 351         }
 352     }
 353
 354     fn report_bivariance(&self,
 355                          span: Span,
 356                          param_name: ast::Name)
 357     {
 358         span_err!(self.tcx().sess, span, E0392,
 359             "parameter `{}` is never used", param_name);
 360
 361         let suggested_marker_id = self.tcx().lang_items.phantom_data();
 362         match suggested_marker_id {
 363             Some(def_id) => {
 364                 self.tcx().sess.fileline_help(
 365                     span,
 366                     &format!("consider removing `{}` or using a marker such as `{}`",
 367                              param_name,
 368                              self.tcx().item_path_str(def_id)));
 369             }
 370             None => {
 371                 // no lang items, no help!
 372             }
 373         }
 374     }
 375 }
 376
 377 // Reject any predicates that do not involve a type parameter.
 378 fn reject_non_type_param_bounds<'tcx>(tcx: &ty::ctxt<'tcx>,
 379                                       span: Span,
 380                                       predicates: &ty::GenericPredicates<'tcx>) {
 381     for predicate in &predicates.predicates {
 382         match predicate {
 383             &ty::Predicate::Trait(ty::Binder(ref tr)) => {
 384                 let found_param = tr.input_types().iter()
 385                                     .flat_map(|ty| ty.walk())
 386                                     .any(is_ty_param);
 387                 if !found_param { report_bound_error(tcx, span, tr.self_ty() )}
 388             }
 389             &ty::Predicate::TypeOutlives(ty::Binder(ty::OutlivesPredicate(ty, _))) => {
 390                 let found_param = ty.walk().any(|t| is_ty_param(t));
 391                 if !found_param { report_bound_error(tcx, span, ty) }
 392             }
 393             _ => {}
 394         };
 395     }
 396
 397     fn report_bound_error<'t>(tcx: &ty::ctxt<'t>,
 398                           span: Span,
 399                           bounded_ty: ty::Ty<'t>) {
 400         span_err!(tcx.sess, span, E0193,
 401             "cannot bound type `{}`, where clause \
 402                 bounds may only be attached to types involving \
 403                 type parameters",
 404                 bounded_ty)
 405     }
 406
 407     fn is_ty_param(ty: ty::Ty) -> bool {
 408         match &ty.sty {
 409             &ty::TyParam(_) => true,
 410             _ => false
 411         }
 412     }
 413 }
 414
 415 fn reject_shadowing_type_parameters<'tcx>(tcx: &ty::ctxt<'tcx>,
 416                                           span: Span,
 417                                           generics: &ty::Generics<'tcx>) {
 418     let impl_params = generics.types.get_slice(subst::TypeSpace).iter()
 419         .map(|tp| tp.name).collect::<HashSet<_>>();
 420
 421     for method_param in generics.types.get_slice(subst::FnSpace) {
 422         if impl_params.contains(&method_param.name) {
 423             span_err!(tcx.sess, span, E0194,
 424                 "type parameter `{}` shadows another type parameter of the same name",
 425                           method_param.name);
 426         }
 427     }
 428 }
 429
 430 impl<'ccx, 'tcx, 'v> Visitor<'v> for CheckTypeWellFormedVisitor<'ccx, 'tcx> {
 431     fn visit_item(&mut self, i: &ast::Item) {
 432         self.check_item_well_formed(i);
 433         visit::walk_item(self, i);
 434     }
 435
 436     fn visit_fn(&mut self,
 437                 fk: visit::FnKind<'v>, fd: &'v ast::FnDecl,
 438                 b: &'v ast::Block, span: Span, id: ast::NodeId) {
 439         match fk {
 440             visit::FkFnBlock | visit::FkItemFn(..) => {}
 441             visit::FkMethod(..) => {
 442                 match self.tcx().impl_or_trait_item(local_def(id)) {
 443                     ty::ImplOrTraitItem::MethodTraitItem(ty_method) => {
 444                         reject_shadowing_type_parameters(self.tcx(), span, &ty_method.generics)
 445                     }
 446                     _ => {}
 447                 }
 448             }
 449         }
 450         visit::walk_fn(self, fk, fd, b, span)
 451     }
 452
 453     fn visit_trait_item(&mut self, trait_item: &'v ast::TraitItem) {
 454         if let ast::MethodTraitItem(_, None) = trait_item.node {
 455             match self.tcx().impl_or_trait_item(local_def(trait_item.id)) {
 456                 ty::ImplOrTraitItem::MethodTraitItem(ty_method) => {
 457                     reject_non_type_param_bounds(
 458                         self.tcx(),
 459                         trait_item.span,
 460                         &ty_method.predicates);
 461                     reject_shadowing_type_parameters(
 462                         self.tcx(),
 463                         trait_item.span,
 464                         &ty_method.generics);
 465                 }
 466                 _ => {}
 467             }
 468         }
 469
 470         visit::walk_trait_item(self, trait_item)
 471     }
 472 }
 473
 474 pub struct BoundsChecker<'cx,'tcx:'cx> {
 475     fcx: &'cx FnCtxt<'cx,'tcx>,
 476     span: Span,
 477
 478     // This field is often attached to item impls; it is not clear
 479     // that `CodeExtent` is well-defined for such nodes, so pnkfelix
 480     // has left it as a NodeId rather than porting to CodeExtent.
 481     scope: ast::NodeId,
 482
 483     binding_count: usize,
 484     cache: Option<&'cx mut HashSet<Ty<'tcx>>>,
 485 }
 486
 487 impl<'cx,'tcx> BoundsChecker<'cx,'tcx> {
 488     pub fn new(fcx: &'cx FnCtxt<'cx,'tcx>,
 489                scope: ast::NodeId,
 490                cache: Option<&'cx mut HashSet<Ty<'tcx>>>)
 491                -> BoundsChecker<'cx,'tcx> {
 492         BoundsChecker { fcx: fcx, span: DUMMY_SP, scope: scope,
 493                         cache: cache, binding_count: 0 }
 494     }
 495
 496     /// Given a trait ref like `A : Trait<B>`, where `Trait` is defined as (say):
 497     ///
 498     ///     trait Trait<B:OtherTrait> : Copy { ... }
 499     ///
 500     /// This routine will check that `B : OtherTrait` and `A : Trait<B>`. It will also recursively
 501     /// check that the types `A` and `B` are well-formed.
 502     ///
 503     /// Note that it does not (currently, at least) check that `A : Copy` (that check is delegated
 504     /// to the point where impl `A : Trait<B>` is implemented).
 505     pub fn check_trait_ref(&mut self, trait_ref: &ty::TraitRef<'tcx>, span: Span) {
 506         let trait_predicates = self.fcx.tcx().lookup_predicates(trait_ref.def_id);
 507
 508         let bounds = self.fcx.instantiate_bounds(span,
 509                                                  trait_ref.substs,
 510                                                  &trait_predicates);
 511
 512         self.fcx.add_obligations_for_parameters(
 513             traits::ObligationCause::new(
 514                 span,
 515                 self.fcx.body_id,
 516                 traits::ItemObligation(trait_ref.def_id)),
 517             &bounds);
 518
 519         for &ty in &trait_ref.substs.types {
 520             self.check_traits_in_ty(ty, span);
 521         }
 522     }
 523
 524     pub fn check_ty(&mut self, ty: Ty<'tcx>, span: Span) {
 525         self.span = span;
 526         ty.fold_with(self);
 527     }
 528
 529     fn check_traits_in_ty(&mut self, ty: Ty<'tcx>, span: Span) {
 530         self.span = span;
 531         // When checking types outside of a type def'n, we ignore
 532         // region obligations. See discussion below in fold_ty().
 533         self.binding_count += 1;
 534         ty.fold_with(self);
 535         self.binding_count -= 1;
 536     }
 537 }
 538
 539 impl<'cx,'tcx> TypeFolder<'tcx> for BoundsChecker<'cx,'tcx> {
 540     fn tcx(&self) -> &ty::ctxt<'tcx> {
 541         self.fcx.tcx()
 542     }
 543
 544     fn fold_binder<T>(&mut self, binder: &ty::Binder<T>) -> ty::Binder<T>
 545         where T : TypeFoldable<'tcx>
 546     {
 547         self.binding_count += 1;
 548         let value = self.fcx.tcx().liberate_late_bound_regions(
 549             region::DestructionScopeData::new(self.scope),
 550             binder);
 551         debug!("BoundsChecker::fold_binder: late-bound regions replaced: {:?} at scope: {:?}",
 552                value, self.scope);
 553         let value = value.fold_with(self);
 554         self.binding_count -= 1;
 555         ty::Binder(value)
 556     }
 557
 558     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 559         debug!("BoundsChecker t={:?}",
 560                t);
 561
 562         match self.cache {
 563             Some(ref mut cache) => {
 564                 if !cache.insert(t) {
 565                     // Already checked this type! Don't check again.
 566                     debug!("cached");
 567                     return t;
 568                 }
 569             }
 570             None => { }
 571         }
 572
 573         match t.sty{
 574             ty::TyStruct(def, substs) |
 575             ty::TyEnum(def, substs) => {
 576                 let type_predicates = def.predicates(self.fcx.tcx());
 577                 let bounds = self.fcx.instantiate_bounds(self.span, substs,
 578                                                          &type_predicates);
 579
 580                 if self.binding_count == 0 {
 581                     self.fcx.add_obligations_for_parameters(
 582                         traits::ObligationCause::new(self.span,
 583                                                      self.fcx.body_id,
 584                                                      traits::ItemObligation(def.did)),
 585                         &bounds);
 586                 } else {
 587                     // There are two circumstances in which we ignore
 588                     // region obligations.
 589                     //
 590                     // The first is when we are inside of a closure
 591                     // type. This is because in that case the region
 592                     // obligations for the parameter types are things
 593                     // that the closure body gets to assume and the
 594                     // caller must prove at the time of call. In other
 595                     // words, if there is a type like `<'a, 'b> | &'a
 596                     // &'b int |`, it is well-formed, and caller will
 597                     // have to show that `'b : 'a` at the time of
 598                     // call.
 599                     //
 600                     // The second is when we are checking for
 601                     // well-formedness outside of a type def'n or fn
 602                     // body. This is for a similar reason: in general,
 603                     // we only do WF checking for regions in the
 604                     // result of expressions and type definitions, so
 605                     // to as allow for implicit where clauses.
 606                     //
 607                     // (I believe we should do the same for traits, but
 608                     // that will require an RFC. -nmatsakis)
 609                     let bounds = filter_to_trait_obligations(bounds);
 610                     self.fcx.add_obligations_for_parameters(
 611                         traits::ObligationCause::new(self.span,
 612                                                      self.fcx.body_id,
 613                                                      traits::ItemObligation(def.did)),
 614                         &bounds);
 615                 }
 616
 617                 self.fold_substs(substs);
 618             }
 619             _ => {
 620                 super_fold_ty(self, t);
 621             }
 622         }
 623
 624         t // we're not folding to produce a new type, so just return `t` here
 625     }
 626 }
 627
 628 ///////////////////////////////////////////////////////////////////////////
 629 // ADT
 630
 631 struct AdtVariant<'tcx> {
 632     fields: Vec<AdtField<'tcx>>,
 633 }
 634
 635 struct AdtField<'tcx> {
 636     ty: Ty<'tcx>,
 637     span: Span,
 638 }
 639
 640 fn struct_variant<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 641                             struct_def: &ast::StructDef)
 642                             -> AdtVariant<'tcx> {
 643     let fields =
 644         struct_def.fields
 645         .iter()
 646         .map(|field| {
 647             let field_ty = fcx.tcx().node_id_to_type(field.node.id);
 648             let field_ty = fcx.instantiate_type_scheme(field.span,
 649                                                        &fcx.inh
 650                                                            .infcx
 651                                                            .parameter_environment
 652                                                            .free_substs,
 653                                                        &field_ty);
 654             AdtField { ty: field_ty, span: field.span }
 655         })
 656         .collect();
 657     AdtVariant { fields: fields }
 658 }
 659
 660 fn enum_variants<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 661                            enum_def: &ast::EnumDef)
 662                            -> Vec<AdtVariant<'tcx>> {
 663     enum_def.variants.iter()
 664         .map(|variant| {
 665             match variant.node.kind {
 666                 ast::TupleVariantKind(ref args) if !args.is_empty() => {
 667                     let ctor_ty = fcx.tcx().node_id_to_type(variant.node.id);
 668
 669                     // the regions in the argument types come from the
 670                     // enum def'n, and hence will all be early bound
 671                     let arg_tys = fcx.tcx().no_late_bound_regions(&ctor_ty.fn_args()).unwrap();
 672                     AdtVariant {
 673                         fields: args.iter().enumerate().map(|(index, arg)| {
 674                             let arg_ty = arg_tys[index];
 675                             let arg_ty =
 676                                 fcx.instantiate_type_scheme(variant.span,
 677                                                             &fcx.inh
 678                                                                 .infcx
 679                                                                 .parameter_environment
 680                                                                 .free_substs,
 681                                                             &arg_ty);
 682                             AdtField {
 683                                 ty: arg_ty,
 684                                 span: arg.ty.span
 685                             }
 686                         }).collect()
 687                     }
 688                 }
 689                 ast::TupleVariantKind(_) => {
 690                     AdtVariant {
 691                         fields: Vec::new()
 692                     }
 693                 }
 694                 ast::StructVariantKind(ref struct_def) => {
 695                     struct_variant(fcx, &**struct_def)
 696                 }
 697             }
 698         })
 699         .collect()
 700 }
 701
 702 fn filter_to_trait_obligations<'tcx>(bounds: ty::InstantiatedPredicates<'tcx>)
 703                                      -> ty::InstantiatedPredicates<'tcx>
 704 {
 705     let mut result = ty::InstantiatedPredicates::empty();
 706     for (space, _, predicate) in bounds.predicates.iter_enumerated() {
 707         match *predicate {
 708             ty::Predicate::Trait(..) |
 709             ty::Predicate::Projection(..) => {
 710                 result.predicates.push(space, predicate.clone())
 711             }
 712             ty::Predicate::Equate(..) |
 713             ty::Predicate::TypeOutlives(..) |
 714             ty::Predicate::RegionOutlives(..) => {
 715             }
 716         }
 717     }
 718     result
 719 }