src/librustc/infer/outlives/free_region_map.rs

   1 // Copyright 2012-2014 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 use ty::{self, Lift, TyCtxt, Region};
  12 use rustc_data_structures::transitive_relation::TransitiveRelation;
  13
  14 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
  15 pub struct FreeRegionMap<'tcx> {
  16     // Stores the relation `a < b`, where `a` and `b` are regions.
  17     //
  18     // Invariant: only free regions like `'x` or `'static` are stored
  19     // in this relation, not scopes.
  20     relation: TransitiveRelation<Region<'tcx>>
  21 }
  22
  23 impl<'tcx> FreeRegionMap<'tcx> {
  24     pub fn new() -> Self {
  25         FreeRegionMap { relation: TransitiveRelation::new() }
  26     }
  27
  28     pub fn is_empty(&self) -> bool {
  29         self.relation.is_empty()
  30     }
  31
  32     // Record that `'sup:'sub`. Or, put another way, `'sub <= 'sup`.
  33     // (with the exception that `'static: 'x` is not notable)
  34     pub fn relate_regions(&mut self, sub: Region<'tcx>, sup: Region<'tcx>) {
  35         debug!("relate_regions(sub={:?}, sup={:?})", sub, sup);
  36         if is_free_or_static(sub) && is_free(sup) {
  37             self.relation.add(sub, sup)
  38         }
  39     }
  40
  41     /// Compute the least-upper-bound of two free regions. In some
  42     /// cases, this is more conservative than necessary, in order to
  43     /// avoid making arbitrary choices. See
  44     /// `TransitiveRelation::postdom_upper_bound` for more details.
  45     pub fn lub_free_regions<'a, 'gcx>(&self,
  46                                       tcx: TyCtxt<'a, 'gcx, 'tcx>,
  47                                       r_a: Region<'tcx>,
  48                                       r_b: Region<'tcx>)
  49                                       -> Region<'tcx> {
  50         debug!("lub_free_regions(r_a={:?}, r_b={:?})", r_a, r_b);
  51         assert!(is_free(r_a));
  52         assert!(is_free(r_b));
  53         let result = if r_a == r_b { r_a } else {
  54             match self.relation.postdom_upper_bound(&r_a, &r_b) {
  55                 None => tcx.mk_region(ty::ReStatic),
  56                 Some(r) => *r,
  57             }
  58         };
  59         debug!("lub_free_regions(r_a={:?}, r_b={:?}) = {:?}", r_a, r_b, result);
  60         result
  61     }
  62 }
  63
  64 /// The NLL region handling code represents free region relations in a
  65 /// slightly different way; this trait allows functions to be abstract
  66 /// over which version is in use.
  67 pub trait FreeRegionRelations<'tcx> {
  68     /// Tests whether `r_a <= r_b`. Both must be free regions or
  69     /// `'static`.
  70     fn sub_free_regions(&self, shorter: ty::Region<'tcx>, longer: ty::Region<'tcx>) -> bool;
  71 }
  72
  73 impl<'tcx> FreeRegionRelations<'tcx> for FreeRegionMap<'tcx> {
  74     fn sub_free_regions(&self,
  75                         r_a: Region<'tcx>,
  76                         r_b: Region<'tcx>)
  77                         -> bool {
  78         assert!(is_free_or_static(r_a) && is_free_or_static(r_b));
  79         if let ty::ReStatic = r_b {
  80             true // `'a <= 'static` is just always true, and not stored in the relation explicitly
  81         } else {
  82             r_a == r_b || self.relation.contains(&r_a, &r_b)
  83         }
  84     }
  85 }
  86
  87 fn is_free(r: Region) -> bool {
  88     match *r {
  89         ty::ReEarlyBound(_) | ty::ReFree(_) => true,
  90         _ => false
  91     }
  92 }
  93
  94 fn is_free_or_static(r: Region) -> bool {
  95     match *r {
  96         ty::ReStatic => true,
  97         _ => is_free(r),
  98     }
  99 }
 100
 101 impl_stable_hash_for!(struct FreeRegionMap<'tcx> {
 102     relation
 103 });
 104
 105 impl<'a, 'tcx> Lift<'tcx> for FreeRegionMap<'a> {
 106     type Lifted = FreeRegionMap<'tcx>;
 107     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<FreeRegionMap<'tcx>> {
 108         self.relation.maybe_map(|&fr| fr.lift_to_tcx(tcx))
 109                      .map(|relation| FreeRegionMap { relation })
 110     }
 111 }