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