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