src/librustc_typeck/check/regionmanip.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 pub use self::WfConstraint::*;
  14
  15 use middle::subst::{ParamSpace, Subst, Substs};
  16 use middle::ty::{self, Ty};
  17 use middle::ty_fold::{TypeFolder};
  18
  19 use syntax::ast;
  20
  21 use util::ppaux::Repr;
  22
  23 // Helper functions related to manipulating region types.
  24
  25 pub enum WfConstraint<'tcx> {
  26     RegionSubRegionConstraint(Option<Ty<'tcx>>, ty::Region, ty::Region),
  27     RegionSubParamConstraint(Option<Ty<'tcx>>, ty::Region, ty::ParamTy),
  28 }
  29
  30 struct Wf<'a, 'tcx: 'a> {
  31     tcx: &'a ty::ctxt<'tcx>,
  32     stack: Vec<(ty::Region, Option<Ty<'tcx>>)>,
  33     out: Vec<WfConstraint<'tcx>>,
  34 }
  35
  36 /// This routine computes the well-formedness constraints that must hold for the type `ty` to
  37 /// appear in a context with lifetime `outer_region`
  38 pub fn region_wf_constraints<'tcx>(
  39     tcx: &ty::ctxt<'tcx>,
  40     ty: Ty<'tcx>,
  41     outer_region: ty::Region)
  42     -> Vec<WfConstraint<'tcx>>
  43 {
  44     let mut stack = Vec::new();
  45     stack.push((outer_region, None));
  46     let mut wf = Wf { tcx: tcx,
  47                       stack: stack,
  48                       out: Vec::new() };
  49     wf.accumulate_from_ty(ty);
  50     wf.out
  51 }
  52
  53 impl<'a, 'tcx> Wf<'a, 'tcx> {
  54     fn accumulate_from_ty(&mut self, ty: Ty<'tcx>) {
  55         debug!("Wf::accumulate_from_ty(ty={})",
  56                ty.repr(self.tcx));
  57
  58         match ty.sty {
  59             ty::ty_bool |
  60             ty::ty_char |
  61             ty::ty_int(..) |
  62             ty::ty_uint(..) |
  63             ty::ty_float(..) |
  64             ty::ty_bare_fn(..) |
  65             ty::ty_err |
  66             ty::ty_str => {
  67                 // No borrowed content reachable here.
  68             }
  69
  70             ty::ty_closure(box ref c) => {
  71                 self.accumulate_from_closure_ty(ty, c);
  72             }
  73
  74             ty::ty_unboxed_closure(_, region, _) => {
  75                 // An "unboxed closure type" is basically
  76                 // modeled here as equivalent to a struct like
  77                 //
  78                 //     struct TheClosure<'b> {
  79                 //         ...
  80                 //     }
  81                 //
  82                 // where the `'b` is the lifetime bound of the
  83                 // contents (i.e., all contents must outlive 'b).
  84                 //
  85                 // Even though unboxed closures are glorified structs
  86                 // of upvars, we do not need to consider them as they
  87                 // can't generate any new constraints.  The
  88                 // substitutions on the closure are equal to the free
  89                 // substitutions of the enclosing parameter
  90                 // environment.  An upvar captured by value has the
  91                 // same type as the original local variable which is
  92                 // already checked for consistency.  If the upvar is
  93                 // captured by reference it must also outlive the
  94                 // region bound on the closure, but this is explicitly
  95                 // handled by logic in regionck.
  96                 self.push_region_constraint_from_top(*region);
  97             }
  98
  99             ty::ty_trait(ref t) => {
 100                 let required_region_bounds =
 101                     ty::object_region_bounds(self.tcx, Some(&t.principal), t.bounds.builtin_bounds);
 102                 self.accumulate_from_object_ty(ty, t.bounds.region_bound, required_region_bounds)
 103             }
 104
 105             ty::ty_enum(def_id, substs) |
 106             ty::ty_struct(def_id, substs) => {
 107                 let item_scheme = ty::lookup_item_type(self.tcx, def_id);
 108                 self.accumulate_from_adt(ty, def_id, &item_scheme.generics, substs)
 109             }
 110
 111             ty::ty_vec(t, _) |
 112             ty::ty_ptr(ty::mt { ty: t, .. }) |
 113             ty::ty_uniq(t) => {
 114                 self.accumulate_from_ty(t)
 115             }
 116
 117             ty::ty_rptr(r_b, mt) => {
 118                 self.accumulate_from_rptr(ty, *r_b, mt.ty);
 119             }
 120
 121             ty::ty_param(p) => {
 122                 self.push_param_constraint_from_top(p);
 123             }
 124
 125             ty::ty_projection(ref data) => {
 126                 // `<T as TraitRef<..>>::Name`
 127
 128                 // FIXME(#20303) -- gain ability to require that ty_projection : in-scope region,
 129                 // like a type parameter
 130
 131                 // this seems like a minimal requirement:
 132                 let trait_def = ty::lookup_trait_def(self.tcx, data.trait_ref.def_id);
 133                 self.accumulate_from_adt(ty, data.trait_ref.def_id,
 134                                          &trait_def.generics, data.trait_ref.substs)
 135             }
 136
 137             ty::ty_tup(ref tuptys) => {
 138                 for &tupty in tuptys.iter() {
 139                     self.accumulate_from_ty(tupty);
 140                 }
 141             }
 142
 143             ty::ty_infer(_) => {
 144                 // This should not happen, BUT:
 145                 //
 146                 //   Currently we uncover region relationships on
 147                 //   entering the fn check. We should do this after
 148                 //   the fn check, then we can call this case a bug().
 149             }
 150
 151             ty::ty_open(_) => {
 152                 self.tcx.sess.bug(
 153                     format!("Unexpected type encountered while doing wf check: {}",
 154                             ty.repr(self.tcx))[]);
 155             }
 156         }
 157     }
 158
 159     fn accumulate_from_rptr(&mut self,
 160                             ty: Ty<'tcx>,
 161                             r_b: ty::Region,
 162                             ty_b: Ty<'tcx>) {
 163         // We are walking down a type like this, and current
 164         // position is indicated by caret:
 165         //
 166         //     &'a &'b ty_b
 167         //         ^
 168         //
 169         // At this point, top of stack will be `'a`. We must
 170         // require that `'a <= 'b`.
 171
 172         self.push_region_constraint_from_top(r_b);
 173
 174         // Now we push `'b` onto the stack, because it must
 175         // constrain any borrowed content we find within `T`.
 176
 177         self.stack.push((r_b, Some(ty)));
 178         self.accumulate_from_ty(ty_b);
 179         self.stack.pop().unwrap();
 180     }
 181
 182     /// Pushes a constraint that `r_b` must outlive the top region on the stack.
 183     fn push_region_constraint_from_top(&mut self,
 184                                        r_b: ty::Region) {
 185
 186         // Indicates that we have found borrowed content with a lifetime
 187         // of at least `r_b`. This adds a constraint that `r_b` must
 188         // outlive the region `r_a` on top of the stack.
 189         //
 190         // As an example, imagine walking a type like:
 191         //
 192         //     &'a &'b T
 193         //         ^
 194         //
 195         // when we hit the inner pointer (indicated by caret), `'a` will
 196         // be on top of stack and `'b` will be the lifetime of the content
 197         // we just found. So we add constraint that `'a <= 'b`.
 198
 199         let &(r_a, opt_ty) = self.stack.last().unwrap();
 200         self.push_sub_region_constraint(opt_ty, r_a, r_b);
 201     }
 202
 203     /// Pushes a constraint that `r_a <= r_b`, due to `opt_ty`
 204     fn push_sub_region_constraint(&mut self,
 205                                   opt_ty: Option<Ty<'tcx>>,
 206                                   r_a: ty::Region,
 207                                   r_b: ty::Region) {
 208         self.out.push(RegionSubRegionConstraint(opt_ty, r_a, r_b));
 209     }
 210
 211     /// Pushes a constraint that `param_ty` must outlive the top region on the stack.
 212     fn push_param_constraint_from_top(&mut self,
 213                                       param_ty: ty::ParamTy) {
 214         let &(region, opt_ty) = self.stack.last().unwrap();
 215         self.push_param_constraint(region, opt_ty, param_ty);
 216     }
 217
 218     /// Pushes a constraint that `region <= param_ty`, due to `opt_ty`
 219     fn push_param_constraint(&mut self,
 220                              region: ty::Region,
 221                              opt_ty: Option<Ty<'tcx>>,
 222                              param_ty: ty::ParamTy) {
 223         self.out.push(RegionSubParamConstraint(opt_ty, region, param_ty));
 224     }
 225
 226     fn accumulate_from_adt(&mut self,
 227                            ty: Ty<'tcx>,
 228                            def_id: ast::DefId,
 229                            generics: &ty::Generics<'tcx>,
 230                            substs: &Substs<'tcx>)
 231     {
 232         // The generic declarations from the type, appropriately
 233         // substituted for the actual substitutions.
 234         let generics = generics.subst(self.tcx, substs);
 235
 236         // Variance of each type/region parameter.
 237         let variances = ty::item_variances(self.tcx, def_id);
 238
 239         for &space in ParamSpace::all().iter() {
 240             let region_params = substs.regions().get_slice(space);
 241             let region_variances = variances.regions.get_slice(space);
 242             let region_param_defs = generics.regions.get_slice(space);
 243             assert_eq!(region_params.len(), region_variances.len());
 244             for (&region_param, (&region_variance, region_param_def)) in
 245                 region_params.iter().zip(
 246                     region_variances.iter().zip(
 247                         region_param_defs.iter()))
 248             {
 249                 match region_variance {
 250                     ty::Covariant | ty::Bivariant => {
 251                         // Ignore covariant or bivariant region
 252                         // parameters.  To understand why, consider a
 253                         // struct `Foo<'a>`. If `Foo` contains any
 254                         // references with lifetime `'a`, then `'a` must
 255                         // be at least contravariant (and possibly
 256                         // invariant). The only way to have a covariant
 257                         // result is if `Foo` contains only a field with a
 258                         // type like `fn() -> &'a T`; i.e., a bare
 259                         // function that can produce a reference of
 260                         // lifetime `'a`. In this case, there is no
 261                         // *actual data* with lifetime `'a` that is
 262                         // reachable. (Presumably this bare function is
 263                         // really returning static data.)
 264                     }
 265
 266                     ty::Contravariant | ty::Invariant => {
 267                         // If the parameter is contravariant or
 268                         // invariant, there may indeed be reachable
 269                         // data with this lifetime. See other case for
 270                         // more details.
 271                         self.push_region_constraint_from_top(region_param);
 272                     }
 273                 }
 274
 275                 for &region_bound in region_param_def.bounds.iter() {
 276                     // The type declared a constraint like
 277                     //
 278                     //     'b : 'a
 279                     //
 280                     // which means that `'a <= 'b` (after
 281                     // substitution).  So take the region we
 282                     // substituted for `'a` (`region_bound`) and make
 283                     // it a subregion of the region we substituted
 284                     // `'b` (`region_param`).
 285                     self.push_sub_region_constraint(
 286                         Some(ty), region_bound, region_param);
 287                 }
 288             }
 289
 290             let types = substs.types.get_slice(space);
 291             let type_variances = variances.types.get_slice(space);
 292             let type_param_defs = generics.types.get_slice(space);
 293             assert_eq!(types.len(), type_variances.len());
 294             for (&type_param_ty, (&variance, type_param_def)) in
 295                 types.iter().zip(
 296                     type_variances.iter().zip(
 297                         type_param_defs.iter()))
 298             {
 299                 debug!("type_param_ty={} variance={}",
 300                        type_param_ty.repr(self.tcx),
 301                        variance.repr(self.tcx));
 302
 303                 match variance {
 304                     ty::Contravariant | ty::Bivariant => {
 305                         // As above, except that in this it is a
 306                         // *contravariant* reference that indices that no
 307                         // actual data of type T is reachable.
 308                     }
 309
 310                     ty::Covariant | ty::Invariant => {
 311                         self.accumulate_from_ty(type_param_ty);
 312                     }
 313                 }
 314
 315                 // Inspect bounds on this type parameter for any
 316                 // region bounds.
 317                 for &r in type_param_def.bounds.region_bounds.iter() {
 318                     self.stack.push((r, Some(ty)));
 319                     self.accumulate_from_ty(type_param_ty);
 320                     self.stack.pop().unwrap();
 321                 }
 322             }
 323         }
 324     }
 325
 326     fn accumulate_from_closure_ty(&mut self,
 327                                   ty: Ty<'tcx>,
 328                                   c: &ty::ClosureTy<'tcx>)
 329     {
 330         match c.store {
 331             ty::RegionTraitStore(r_b, _) => {
 332                 self.push_region_constraint_from_top(r_b);
 333             }
 334             ty::UniqTraitStore => { }
 335         }
 336
 337         let required_region_bounds =
 338             ty::object_region_bounds(self.tcx, None, c.bounds.builtin_bounds);
 339         self.accumulate_from_object_ty(ty, c.bounds.region_bound, required_region_bounds);
 340     }
 341
 342     fn accumulate_from_object_ty(&mut self,
 343                                  ty: Ty<'tcx>,
 344                                  region_bound: ty::Region,
 345                                  required_region_bounds: Vec<ty::Region>)
 346     {
 347         // Imagine a type like this:
 348         //
 349         //     trait Foo { }
 350         //     trait Bar<'c> : 'c { }
 351         //
 352         //     &'b (Foo+'c+Bar<'d>)
 353         //         ^
 354         //
 355         // In this case, the following relationships must hold:
 356         //
 357         //     'b <= 'c
 358         //     'd <= 'c
 359         //
 360         // The first conditions is due to the normal region pointer
 361         // rules, which say that a reference cannot outlive its
 362         // referent.
 363         //
 364         // The final condition may be a bit surprising. In particular,
 365         // you may expect that it would have been `'c <= 'd`, since
 366         // usually lifetimes of outer things are conservative
 367         // approximations for inner things. However, it works somewhat
 368         // differently with trait objects: here the idea is that if the
 369         // user specifies a region bound (`'c`, in this case) it is the
 370         // "master bound" that *implies* that bounds from other traits are
 371         // all met. (Remember that *all bounds* in a type like
 372         // `Foo+Bar+Zed` must be met, not just one, hence if we write
 373         // `Foo<'x>+Bar<'y>`, we know that the type outlives *both* 'x and
 374         // 'y.)
 375         //
 376         // Note: in fact we only permit builtin traits, not `Bar<'d>`, I
 377         // am looking forward to the future here.
 378
 379         // The content of this object type must outlive
 380         // `bounds.region_bound`:
 381         let r_c = region_bound;
 382         self.push_region_constraint_from_top(r_c);
 383
 384         // And then, in turn, to be well-formed, the
 385         // `region_bound` that user specified must imply the
 386         // region bounds required from all of the trait types:
 387         for &r_d in required_region_bounds.iter() {
 388             // Each of these is an instance of the `'c <= 'b`
 389             // constraint above
 390             self.out.push(RegionSubRegionConstraint(Some(ty), r_d, r_c));
 391         }
 392     }
 393 }
 394
 395 impl<'tcx> Repr<'tcx> for WfConstraint<'tcx> {
 396     fn repr(&self, tcx: &ty::ctxt) -> String {
 397         match *self {
 398             RegionSubRegionConstraint(_, r_a, r_b) => {
 399                 format!("RegionSubRegionConstraint({}, {})",
 400                         r_a.repr(tcx),
 401                         r_b.repr(tcx))
 402             }
 403
 404             RegionSubParamConstraint(_, r, p) => {
 405                 format!("RegionSubParamConstraint({}, {})",
 406                         r.repr(tcx),
 407                         p.repr(tcx))
 408             }
 409         }
 410     }
 411 }