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
  14 use middle::ty;
  15
  16 use middle::typeck::isr_alist;
  17 use util::common::indenter;
  18 use util::ppaux::region_to_str;
  19 use util::ppaux;
  20
  21 use extra::list::Cons;
  22
  23 // Helper functions related to manipulating region types.
  24
  25 pub fn replace_bound_regions_in_fn_sig(
  26     tcx: ty::ctxt,
  27     isr: isr_alist,
  28     opt_self_ty: Option<ty::t>,
  29     fn_sig: &ty::FnSig,
  30     mapf: &fn(ty::bound_region) -> ty::Region)
  31     -> (isr_alist, Option<ty::t>, ty::FnSig)
  32 {
  33     let mut all_tys = ty::tys_in_fn_sig(fn_sig);
  34
  35     for &self_ty in opt_self_ty.iter() {
  36         all_tys.push(self_ty);
  37     }
  38
  39     for &t in opt_self_ty.iter() { all_tys.push(t) }
  40
  41     debug!("replace_bound_regions_in_fn_sig(self_ty=%?, fn_sig=%s, \
  42             all_tys=%?)",
  43            opt_self_ty.map(|t| ppaux::ty_to_str(tcx, *t)),
  44            ppaux::fn_sig_to_str(tcx, fn_sig),
  45            all_tys.map(|t| ppaux::ty_to_str(tcx, *t)));
  46     let _i = indenter();
  47
  48     let isr = do create_bound_region_mapping(tcx, isr, all_tys) |br| {
  49         debug!("br=%?", br);
  50         mapf(br)
  51     };
  52     let new_fn_sig = ty::fold_sig(fn_sig, |t| {
  53         replace_bound_regions(tcx, isr, t)
  54     });
  55     let new_self_ty = opt_self_ty.map(|t| replace_bound_regions(tcx, isr, *t));
  56
  57     debug!("result of replace_bound_regions_in_fn_sig: \
  58             new_self_ty=%?, \
  59             fn_sig=%s",
  60            new_self_ty.map(|t| ppaux::ty_to_str(tcx, *t)),
  61            ppaux::fn_sig_to_str(tcx, &new_fn_sig));
  62
  63     return (isr, new_self_ty, new_fn_sig);
  64
  65     // Takes `isr`, a (possibly empty) mapping from in-scope region
  66     // names ("isr"s) to their corresponding regions; `tys`, a list of
  67     // types, and `to_r`, a closure that takes a bound_region and
  68     // returns a region.  Returns an updated version of `isr`,
  69     // extended with the in-scope region names from all of the bound
  70     // regions appearing in the types in the `tys` list (if they're
  71     // not in `isr` already), with each of those in-scope region names
  72     // mapped to a region that's the result of applying `to_r` to
  73     // itself.
  74     fn create_bound_region_mapping(
  75         tcx: ty::ctxt,
  76         isr: isr_alist,
  77         tys: ~[ty::t],
  78         to_r: &fn(ty::bound_region) -> ty::Region) -> isr_alist {
  79
  80         // Takes `isr` (described above), `to_r` (described above),
  81         // and `r`, a region.  If `r` is anything other than a bound
  82         // region, or if it's a bound region that already appears in
  83         // `isr`, then we return `isr` unchanged.  If `r` is a bound
  84         // region that doesn't already appear in `isr`, we return an
  85         // updated isr_alist that now contains a mapping from `r` to
  86         // the result of calling `to_r` on it.
  87         fn append_isr(isr: isr_alist,
  88                       to_r: &fn(ty::bound_region) -> ty::Region,
  89                       r: ty::Region) -> isr_alist {
  90             match r {
  91               ty::re_empty | ty::re_free(*) | ty::re_static | ty::re_scope(_) |
  92               ty::re_infer(_) => {
  93                 isr
  94               }
  95               ty::re_bound(br) => {
  96                 match isr.find(br) {
  97                   Some(_) => isr,
  98                   None => @Cons((br, to_r(br)), isr)
  99                 }
 100               }
 101             }
 102         }
 103
 104         // For each type `ty` in `tys`...
 105         do tys.iter().fold(isr) |isr, ty| {
 106             let mut isr = isr;
 107
 108             // Using fold_regions is inefficient, because it
 109             // constructs new types, but it avoids code duplication in
 110             // terms of locating all the regions within the various
 111             // kinds of types.  This had already caused me several
 112             // bugs so I decided to switch over.
 113             do ty::fold_regions(tcx, *ty) |r, in_fn| {
 114                 if !in_fn { isr = append_isr(isr, |br| to_r(br), r); }
 115                 r
 116             };
 117
 118             isr
 119         }
 120     }
 121
 122     // Takes `isr`, a mapping from in-scope region names ("isr"s) to
 123     // their corresponding regions; and `ty`, a type.  Returns an
 124     // updated version of `ty`, in which bound regions in `ty` have
 125     // been replaced with the corresponding bindings in `isr`.
 126     fn replace_bound_regions(
 127         tcx: ty::ctxt,
 128         isr: isr_alist,
 129         ty: ty::t) -> ty::t {
 130
 131         do ty::fold_regions(tcx, ty) |r, in_fn| {
 132             let r1 = match r {
 133               // As long as we are not within a fn() type, `&T` is
 134               // mapped to the free region anon_r.  But within a fn
 135               // type, it remains bound.
 136               ty::re_bound(ty::br_anon(_)) if in_fn => r,
 137
 138               ty::re_bound(br) => {
 139                 match isr.find(br) {
 140                   // In most cases, all named, bound regions will be
 141                   // mapped to some free region.
 142                   Some(fr) => fr,
 143
 144                   // But in the case of a fn() type, there may be
 145                   // named regions within that remain bound:
 146                   None if in_fn => r,
 147                   None => {
 148                     tcx.sess.bug(
 149                         fmt!("Bound region not found in \
 150                               in_scope_regions list: %s",
 151                              region_to_str(tcx, "", false, r)));
 152                   }
 153                 }
 154               }
 155
 156               // Free regions like these just stay the same:
 157               ty::re_empty |
 158               ty::re_static |
 159               ty::re_scope(_) |
 160               ty::re_free(*) |
 161               ty::re_infer(_) => r
 162             };
 163             r1
 164         }
 165     }
 166 }
 167
 168 pub fn relate_nested_regions(
 169     tcx: ty::ctxt,
 170     opt_region: Option<ty::Region>,
 171     ty: ty::t,
 172     relate_op: &fn(ty::Region, ty::Region))
 173 {
 174     /*!
 175      *
 176      * This rather specialized function walks each region `r` that appear
 177      * in `ty` and invokes `relate_op(r_encl, r)` for each one.  `r_encl`
 178      * here is the region of any enclosing `&'r T` pointer.  If there is
 179      * no enclosing pointer, and `opt_region` is Some, then `opt_region.get()`
 180      * is used instead.  Otherwise, no callback occurs at all).
 181      *
 182      * Here are some examples to give you an intution:
 183      *
 184      * - `relate_nested_regions(Some('r1), &'r2 uint)` invokes
 185      *   - `relate_op('r1, 'r2)`
 186      * - `relate_nested_regions(Some('r1), &'r2 &'r3 uint)` invokes
 187      *   - `relate_op('r1, 'r2)`
 188      *   - `relate_op('r2, 'r3)`
 189      * - `relate_nested_regions(None, &'r2 &'r3 uint)` invokes
 190      *   - `relate_op('r2, 'r3)`
 191      * - `relate_nested_regions(None, &'r2 &'r3 &'r4 uint)` invokes
 192      *   - `relate_op('r2, 'r3)`
 193      *   - `relate_op('r2, 'r4)`
 194      *   - `relate_op('r3, 'r4)`
 195      *
 196      * This function is used in various pieces of code because we enforce the
 197      * constraint that a region pointer cannot outlive the things it points at.
 198      * Hence, in the second example above, `'r2` must be a subregion of `'r3`.
 199      */
 200
 201     let mut the_stack = ~[];
 202     for &r in opt_region.iter() { the_stack.push(r); }
 203     walk_ty(tcx, &mut the_stack, ty, relate_op);
 204
 205     fn walk_ty(tcx: ty::ctxt,
 206                the_stack: &mut ~[ty::Region],
 207                ty: ty::t,
 208                relate_op: &fn(ty::Region, ty::Region))
 209     {
 210         match ty::get(ty).sty {
 211             ty::ty_rptr(r, ref mt) |
 212             ty::ty_evec(ref mt, ty::vstore_slice(r)) => {
 213                 relate(*the_stack, r, |x,y| relate_op(x,y));
 214                 the_stack.push(r);
 215                 walk_ty(tcx, the_stack, mt.ty, |x,y| relate_op(x,y));
 216                 the_stack.pop();
 217             }
 218             _ => {
 219                 ty::fold_regions_and_ty(
 220                     tcx,
 221                     ty,
 222                     |r| { relate(     *the_stack, r, |x,y| relate_op(x,y)); r },
 223                     |t| { walk_ty(tcx, the_stack, t, |x,y| relate_op(x,y)); t },
 224                     |t| { walk_ty(tcx, the_stack, t, |x,y| relate_op(x,y)); t });
 225             }
 226         }
 227     }
 228
 229     fn relate(the_stack: &[ty::Region],
 230               r_sub: ty::Region,
 231               relate_op: &fn(ty::Region, ty::Region))
 232     {
 233         for &r in the_stack.iter() {
 234             if !r.is_bound() && !r_sub.is_bound() {
 235                 relate_op(r, r_sub);
 236             }
 237         }
 238     }
 239 }
 240
 241 pub fn relate_free_regions(
 242     tcx: ty::ctxt,
 243     self_ty: Option<ty::t>,
 244     fn_sig: &ty::FnSig)
 245 {
 246     /*!
 247      * This function populates the region map's `free_region_map`.
 248      * It walks over the transformed self type and argument types
 249      * for each function just before we check the body of that
 250      * function, looking for types where you have a borrowed
 251      * pointer to other borrowed data (e.g., `&'a &'b [uint]`.
 252      * We do not allow borrowed pointers to outlive the things they
 253      * point at, so we can assume that `'a <= 'b`.
 254      *
 255      * Tests: `src/test/compile-fail/regions-free-region-ordering-*.rs`
 256      */
 257
 258     debug!("relate_free_regions >>");
 259
 260     let mut all_tys = ~[];
 261     for arg in fn_sig.inputs.iter() {
 262         all_tys.push(*arg);
 263     }
 264     for &t in self_ty.iter() {
 265         all_tys.push(t);
 266     }
 267
 268     for &t in all_tys.iter() {
 269         debug!("relate_free_regions(t=%s)", ppaux::ty_to_str(tcx, t));
 270         relate_nested_regions(tcx, None, t, |a, b| {
 271             match (&a, &b) {
 272                 (&ty::re_free(free_a), &ty::re_free(free_b)) => {
 273                     tcx.region_maps.relate_free_regions(free_a, free_b);
 274                 }
 275                 _ => {}
 276             }
 277         })
 278     }
 279
 280     debug!("<< relate_free_regions");
 281 }