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