src/librustc/middle/implicator.rs

   1 // Copyright 2012 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 // #![warn(deprecated_mode)]
  12
  13 use middle::infer::{InferCtxt, GenericKind};
  14 use middle::subst::Substs;
  15 use middle::traits;
  16 use middle::ty::{self, RegionEscape, ToPolyTraitRef, ToPredicate, Ty};
  17 use middle::ty_fold::{TypeFoldable, TypeFolder};
  18
  19 use syntax::ast;
  20 use syntax::codemap::Span;
  21
  22 use util::common::ErrorReported;
  23 use util::nodemap::FnvHashSet;
  24
  25 // Helper functions related to manipulating region types.
  26
  27 #[derive(Debug)]
  28 pub enum Implication<'tcx> {
  29     RegionSubRegion(Option<Ty<'tcx>>, ty::Region, ty::Region),
  30     RegionSubGeneric(Option<Ty<'tcx>>, ty::Region, GenericKind<'tcx>),
  31     Predicate(ast::DefId, ty::Predicate<'tcx>),
  32 }
  33
  34 struct Implicator<'a, 'tcx: 'a> {
  35     infcx: &'a InferCtxt<'a,'tcx>,
  36     body_id: ast::NodeId,
  37     stack: Vec<(ty::Region, Option<Ty<'tcx>>)>,
  38     span: Span,
  39     out: Vec<Implication<'tcx>>,
  40     visited: FnvHashSet<Ty<'tcx>>,
  41 }
  42
  43 /// This routine computes the well-formedness constraints that must hold for the type `ty` to
  44 /// appear in a context with lifetime `outer_region`
  45 pub fn implications<'a,'tcx>(
  46     infcx: &'a InferCtxt<'a,'tcx>,
  47     body_id: ast::NodeId,
  48     ty: Ty<'tcx>,
  49     outer_region: ty::Region,
  50     span: Span)
  51     -> Vec<Implication<'tcx>>
  52 {
  53     debug!("implications(body_id={}, ty={:?}, outer_region={:?})",
  54            body_id,
  55            ty,
  56            outer_region);
  57
  58     let mut stack = Vec::new();
  59     stack.push((outer_region, None));
  60     let mut wf = Implicator { infcx: infcx,
  61                               body_id: body_id,
  62                               span: span,
  63                               stack: stack,
  64                               out: Vec::new(),
  65                               visited: FnvHashSet() };
  66     wf.accumulate_from_ty(ty);
  67     debug!("implications: out={:?}", wf.out);
  68     wf.out
  69 }
  70
  71 impl<'a, 'tcx> Implicator<'a, 'tcx> {
  72     fn tcx(&self) -> &'a ty::ctxt<'tcx> {
  73         self.infcx.tcx
  74     }
  75
  76     fn accumulate_from_ty(&mut self, ty: Ty<'tcx>) {
  77         debug!("accumulate_from_ty(ty={:?})",
  78                ty);
  79
  80         // When expanding out associated types, we can visit a cyclic
  81         // set of types. Issue #23003.
  82         if !self.visited.insert(ty) {
  83             return;
  84         }
  85
  86         match ty.sty {
  87             ty::TyBool |
  88             ty::TyChar |
  89             ty::TyInt(..) |
  90             ty::TyUint(..) |
  91             ty::TyFloat(..) |
  92             ty::TyBareFn(..) |
  93             ty::TyError |
  94             ty::TyStr => {
  95                 // No borrowed content reachable here.
  96             }
  97
  98             ty::TyClosure(_, ref substs) => {
  99                 // FIXME(#27086). We do not accumulate from substs, since they
 100                 // don't represent reachable data. This means that, in
 101                 // practice, some of the lifetime parameters might not
 102                 // be in scope when the body runs, so long as there is
 103                 // no reachable data with that lifetime. For better or
 104                 // worse, this is consistent with fn types, however,
 105                 // which can also encapsulate data in this fashion
 106                 // (though it's somewhat harder, and typically
 107                 // requires virtual dispatch).
 108                 //
 109                 // Note that changing this (in a naive way, at least)
 110                 // causes regressions for what appears to be perfectly
 111                 // reasonable code like this:
 112                 //
 113                 // ```
 114                 // fn foo<'a>(p: &Data<'a>) {
 115                 //    bar(|q: &mut Parser| q.read_addr())
 116                 // }
 117                 // fn bar(p: Box<FnMut(&mut Parser)+'static>) {
 118                 // }
 119                 // ```
 120                 //
 121                 // Note that `p` (and `'a`) are not used in the
 122                 // closure at all, but to meet the requirement that
 123                 // the closure type `C: 'static` (so it can be coerced
 124                 // to the object type), we get the requirement that
 125                 // `'a: 'static` since `'a` appears in the closure
 126                 // type `C`.
 127                 //
 128                 // A smarter fix might "prune" unused `func_substs` --
 129                 // this would avoid breaking simple examples like
 130                 // this, but would still break others (which might
 131                 // indeed be invalid, depending on your POV). Pruning
 132                 // would be a subtle process, since we have to see
 133                 // what func/type parameters are used and unused,
 134                 // taking into consideration UFCS and so forth.
 135
 136                 for &upvar_ty in &substs.upvar_tys {
 137                     self.accumulate_from_ty(upvar_ty);
 138                 }
 139             }
 140
 141             ty::TyTrait(ref t) => {
 142                 let required_region_bounds =
 143                     object_region_bounds(self.tcx(), &t.principal, t.bounds.builtin_bounds);
 144                 self.accumulate_from_object_ty(ty, t.bounds.region_bound, required_region_bounds)
 145             }
 146
 147             ty::TyEnum(def, substs) |
 148             ty::TyStruct(def, substs) => {
 149                 let item_scheme = def.type_scheme(self.tcx());
 150                 self.accumulate_from_adt(ty, def.did, &item_scheme.generics, substs)
 151             }
 152
 153             ty::TyArray(t, _) |
 154             ty::TySlice(t) |
 155             ty::TyRawPtr(ty::TypeAndMut { ty: t, .. }) |
 156             ty::TyBox(t) => {
 157                 self.accumulate_from_ty(t)
 158             }
 159
 160             ty::TyRef(r_b, mt) => {
 161                 self.accumulate_from_rptr(ty, *r_b, mt.ty);
 162             }
 163
 164             ty::TyParam(p) => {
 165                 self.push_param_constraint_from_top(p);
 166             }
 167
 168             ty::TyProjection(ref data) => {
 169                 // `<T as TraitRef<..>>::Name`
 170
 171                 self.push_projection_constraint_from_top(data);
 172             }
 173
 174             ty::TyTuple(ref tuptys) => {
 175                 for &tupty in tuptys {
 176                     self.accumulate_from_ty(tupty);
 177                 }
 178             }
 179
 180             ty::TyInfer(_) => {
 181                 // This should not happen, BUT:
 182                 //
 183                 //   Currently we uncover region relationships on
 184                 //   entering the fn check. We should do this after
 185                 //   the fn check, then we can call this case a bug().
 186             }
 187         }
 188     }
 189
 190     fn accumulate_from_rptr(&mut self,
 191                             ty: Ty<'tcx>,
 192                             r_b: ty::Region,
 193                             ty_b: Ty<'tcx>) {
 194         // We are walking down a type like this, and current
 195         // position is indicated by caret:
 196         //
 197         //     &'a &'b ty_b
 198         //         ^
 199         //
 200         // At this point, top of stack will be `'a`. We must
 201         // require that `'a <= 'b`.
 202
 203         self.push_region_constraint_from_top(r_b);
 204
 205         // Now we push `'b` onto the stack, because it must
 206         // constrain any borrowed content we find within `T`.
 207
 208         self.stack.push((r_b, Some(ty)));
 209         self.accumulate_from_ty(ty_b);
 210         self.stack.pop().unwrap();
 211     }
 212
 213     /// Pushes a constraint that `r_b` must outlive the top region on the stack.
 214     fn push_region_constraint_from_top(&mut self,
 215                                        r_b: ty::Region) {
 216
 217         // Indicates that we have found borrowed content with a lifetime
 218         // of at least `r_b`. This adds a constraint that `r_b` must
 219         // outlive the region `r_a` on top of the stack.
 220         //
 221         // As an example, imagine walking a type like:
 222         //
 223         //     &'a &'b T
 224         //         ^
 225         //
 226         // when we hit the inner pointer (indicated by caret), `'a` will
 227         // be on top of stack and `'b` will be the lifetime of the content
 228         // we just found. So we add constraint that `'a <= 'b`.
 229
 230         let &(r_a, opt_ty) = self.stack.last().unwrap();
 231         self.push_sub_region_constraint(opt_ty, r_a, r_b);
 232     }
 233
 234     /// Pushes a constraint that `r_a <= r_b`, due to `opt_ty`
 235     fn push_sub_region_constraint(&mut self,
 236                                   opt_ty: Option<Ty<'tcx>>,
 237                                   r_a: ty::Region,
 238                                   r_b: ty::Region) {
 239         self.out.push(Implication::RegionSubRegion(opt_ty, r_a, r_b));
 240     }
 241
 242     /// Pushes a constraint that `param_ty` must outlive the top region on the stack.
 243     fn push_param_constraint_from_top(&mut self,
 244                                       param_ty: ty::ParamTy) {
 245         let &(region, opt_ty) = self.stack.last().unwrap();
 246         self.push_param_constraint(region, opt_ty, param_ty);
 247     }
 248
 249     /// Pushes a constraint that `projection_ty` must outlive the top region on the stack.
 250     fn push_projection_constraint_from_top(&mut self,
 251                                            projection_ty: &ty::ProjectionTy<'tcx>) {
 252         let &(region, opt_ty) = self.stack.last().unwrap();
 253         self.out.push(Implication::RegionSubGeneric(
 254             opt_ty, region, GenericKind::Projection(projection_ty.clone())));
 255     }
 256
 257     /// Pushes a constraint that `region <= param_ty`, due to `opt_ty`
 258     fn push_param_constraint(&mut self,
 259                              region: ty::Region,
 260                              opt_ty: Option<Ty<'tcx>>,
 261                              param_ty: ty::ParamTy) {
 262         self.out.push(Implication::RegionSubGeneric(
 263             opt_ty, region, GenericKind::Param(param_ty)));
 264     }
 265
 266     fn accumulate_from_adt(&mut self,
 267                            ty: Ty<'tcx>,
 268                            def_id: ast::DefId,
 269                            _generics: &ty::Generics<'tcx>,
 270                            substs: &Substs<'tcx>)
 271     {
 272         let predicates =
 273             self.tcx().lookup_predicates(def_id).instantiate(self.tcx(), substs);
 274         let predicates = match self.fully_normalize(&predicates) {
 275             Ok(predicates) => predicates,
 276             Err(ErrorReported) => { return; }
 277         };
 278
 279         for predicate in predicates.predicates.as_slice() {
 280             match *predicate {
 281                 ty::Predicate::Trait(ref data) => {
 282                     self.accumulate_from_assoc_types_transitive(data);
 283                 }
 284                 ty::Predicate::Equate(..) => { }
 285                 ty::Predicate::Projection(..) => { }
 286                 ty::Predicate::RegionOutlives(ref data) => {
 287                     match self.tcx().no_late_bound_regions(data) {
 288                         None => { }
 289                         Some(ty::OutlivesPredicate(r_a, r_b)) => {
 290                             self.push_sub_region_constraint(Some(ty), r_b, r_a);
 291                         }
 292                     }
 293                 }
 294                 ty::Predicate::TypeOutlives(ref data) => {
 295                     match self.tcx().no_late_bound_regions(data) {
 296                         None => { }
 297                         Some(ty::OutlivesPredicate(ty_a, r_b)) => {
 298                             self.stack.push((r_b, Some(ty)));
 299                             self.accumulate_from_ty(ty_a);
 300                             self.stack.pop().unwrap();
 301                         }
 302                     }
 303                 }
 304             }
 305         }
 306
 307         let obligations = predicates.predicates
 308                                     .into_iter()
 309                                     .map(|pred| Implication::Predicate(def_id, pred));
 310         self.out.extend(obligations);
 311
 312         let variances = self.tcx().item_variances(def_id);
 313         self.accumulate_from_substs(substs, Some(&variances));
 314     }
 315
 316     fn accumulate_from_substs(&mut self,
 317                               substs: &Substs<'tcx>,
 318                               variances: Option<&ty::ItemVariances>)
 319     {
 320         let mut tmp_variances = None;
 321         let variances = variances.unwrap_or_else(|| {
 322             tmp_variances = Some(ty::ItemVariances {
 323                 types: substs.types.map(|_| ty::Variance::Invariant),
 324                 regions: substs.regions().map(|_| ty::Variance::Invariant),
 325             });
 326             tmp_variances.as_ref().unwrap()
 327         });
 328
 329         for (&region, &variance) in substs.regions().iter().zip(&variances.regions) {
 330             match variance {
 331                 ty::Contravariant | ty::Invariant => {
 332                     // If any data with this lifetime is reachable
 333                     // within, it must be at least contravariant.
 334                     self.push_region_constraint_from_top(region)
 335                 }
 336                 ty::Covariant | ty::Bivariant => { }
 337             }
 338         }
 339
 340         for (&ty, &variance) in substs.types.iter().zip(&variances.types) {
 341             match variance {
 342                 ty::Covariant | ty::Invariant => {
 343                     // If any data of this type is reachable within,
 344                     // it must be at least covariant.
 345                     self.accumulate_from_ty(ty);
 346                 }
 347                 ty::Contravariant | ty::Bivariant => { }
 348             }
 349         }
 350     }
 351
 352     /// Given that there is a requirement that `Foo<X> : 'a`, where
 353     /// `Foo` is declared like `struct Foo<T> where T : SomeTrait`,
 354     /// this code finds all the associated types defined in
 355     /// `SomeTrait` (and supertraits) and adds a requirement that `<X
 356     /// as SomeTrait>::N : 'a` (where `N` is some associated type
 357     /// defined in `SomeTrait`). This rule only applies to
 358     /// trait-bounds that are not higher-ranked, because we cannot
 359     /// project out of a HRTB. This rule helps code using associated
 360     /// types to compile, see Issue #22246 for an example.
 361     fn accumulate_from_assoc_types_transitive(&mut self,
 362                                               data: &ty::PolyTraitPredicate<'tcx>)
 363     {
 364         debug!("accumulate_from_assoc_types_transitive({:?})",
 365                data);
 366
 367         for poly_trait_ref in traits::supertraits(self.tcx(), data.to_poly_trait_ref()) {
 368             match self.tcx().no_late_bound_regions(&poly_trait_ref) {
 369                 Some(trait_ref) => { self.accumulate_from_assoc_types(trait_ref); }
 370                 None => { }
 371             }
 372         }
 373     }
 374
 375     fn accumulate_from_assoc_types(&mut self,
 376                                    trait_ref: ty::TraitRef<'tcx>)
 377     {
 378         debug!("accumulate_from_assoc_types({:?})",
 379                trait_ref);
 380
 381         let trait_def_id = trait_ref.def_id;
 382         let trait_def = self.tcx().lookup_trait_def(trait_def_id);
 383         let assoc_type_projections: Vec<_> =
 384             trait_def.associated_type_names
 385                      .iter()
 386                      .map(|&name| self.tcx().mk_projection(trait_ref.clone(), name))
 387                      .collect();
 388         debug!("accumulate_from_assoc_types: assoc_type_projections={:?}",
 389                assoc_type_projections);
 390         let tys = match self.fully_normalize(&assoc_type_projections) {
 391             Ok(tys) => { tys }
 392             Err(ErrorReported) => { return; }
 393         };
 394         for ty in tys {
 395             self.accumulate_from_ty(ty);
 396         }
 397     }
 398
 399     fn accumulate_from_object_ty(&mut self,
 400                                  ty: Ty<'tcx>,
 401                                  region_bound: ty::Region,
 402                                  required_region_bounds: Vec<ty::Region>)
 403     {
 404         // Imagine a type like this:
 405         //
 406         //     trait Foo { }
 407         //     trait Bar<'c> : 'c { }
 408         //
 409         //     &'b (Foo+'c+Bar<'d>)
 410         //         ^
 411         //
 412         // In this case, the following relationships must hold:
 413         //
 414         //     'b <= 'c
 415         //     'd <= 'c
 416         //
 417         // The first conditions is due to the normal region pointer
 418         // rules, which say that a reference cannot outlive its
 419         // referent.
 420         //
 421         // The final condition may be a bit surprising. In particular,
 422         // you may expect that it would have been `'c <= 'd`, since
 423         // usually lifetimes of outer things are conservative
 424         // approximations for inner things. However, it works somewhat
 425         // differently with trait objects: here the idea is that if the
 426         // user specifies a region bound (`'c`, in this case) it is the
 427         // "master bound" that *implies* that bounds from other traits are
 428         // all met. (Remember that *all bounds* in a type like
 429         // `Foo+Bar+Zed` must be met, not just one, hence if we write
 430         // `Foo<'x>+Bar<'y>`, we know that the type outlives *both* 'x and
 431         // 'y.)
 432         //
 433         // Note: in fact we only permit builtin traits, not `Bar<'d>`, I
 434         // am looking forward to the future here.
 435
 436         // The content of this object type must outlive
 437         // `bounds.region_bound`:
 438         let r_c = region_bound;
 439         self.push_region_constraint_from_top(r_c);
 440
 441         // And then, in turn, to be well-formed, the
 442         // `region_bound` that user specified must imply the
 443         // region bounds required from all of the trait types:
 444         for &r_d in &required_region_bounds {
 445             // Each of these is an instance of the `'c <= 'b`
 446             // constraint above
 447             self.out.push(Implication::RegionSubRegion(Some(ty), r_d, r_c));
 448         }
 449     }
 450
 451     fn fully_normalize<T>(&self, value: &T) -> Result<T,ErrorReported>
 452         where T : TypeFoldable<'tcx> + ty::HasTypeFlags
 453     {
 454         let value =
 455             traits::fully_normalize(self.infcx,
 456                                     traits::ObligationCause::misc(self.span, self.body_id),
 457                                     value);
 458         match value {
 459             Ok(value) => Ok(value),
 460             Err(errors) => {
 461                 // I don't like reporting these errors here, but I
 462                 // don't know where else to report them just now. And
 463                 // I don't really expect errors to arise here
 464                 // frequently. I guess the best option would be to
 465                 // propagate them out.
 466                 traits::report_fulfillment_errors(self.infcx, &errors);
 467                 Err(ErrorReported)
 468             }
 469         }
 470     }
 471 }
 472
 473 /// Given an object type like `SomeTrait+Send`, computes the lifetime
 474 /// bounds that must hold on the elided self type. These are derived
 475 /// from the declarations of `SomeTrait`, `Send`, and friends -- if
 476 /// they declare `trait SomeTrait : 'static`, for example, then
 477 /// `'static` would appear in the list. The hard work is done by
 478 /// `ty::required_region_bounds`, see that for more information.
 479 pub fn object_region_bounds<'tcx>(
 480     tcx: &ty::ctxt<'tcx>,
 481     principal: &ty::PolyTraitRef<'tcx>,
 482     others: ty::BuiltinBounds)
 483     -> Vec<ty::Region>
 484 {
 485     // Since we don't actually *know* the self type for an object,
 486     // this "open(err)" serves as a kind of dummy standin -- basically
 487     // a skolemized type.
 488     let open_ty = tcx.mk_infer(ty::FreshTy(0));
 489
 490     // Note that we preserve the overall binding levels here.
 491     assert!(!open_ty.has_escaping_regions());
 492     let substs = tcx.mk_substs(principal.0.substs.with_self_ty(open_ty));
 493     let trait_refs = vec!(ty::Binder(ty::TraitRef::new(principal.0.def_id, substs)));
 494
 495     let mut predicates = others.to_predicates(tcx, open_ty);
 496     predicates.extend(trait_refs.iter().map(|t| t.to_predicate()));
 497
 498     tcx.required_region_bounds(open_ty, predicates)
 499 }