src/librustc/ty/free_region_map.rs

   1 use crate::ty::{self, Lift, Region, TyCtxt};
   2 use rustc_data_structures::transitive_relation::TransitiveRelation;
   3
   4 #[derive(Clone, RustcEncodable, RustcDecodable, Debug, Default, HashStable)]
   5 pub struct FreeRegionMap<'tcx> {
   6     // Stores the relation `a < b`, where `a` and `b` are regions.
   7     //
   8     // Invariant: only free regions like `'x` or `'static` are stored
   9     // in this relation, not scopes.
  10     relation: TransitiveRelation<Region<'tcx>>,
  11 }
  12
  13 impl<'tcx> FreeRegionMap<'tcx> {
  14     pub fn elements(&self) -> impl Iterator<Item = &Region<'tcx>> {
  15         self.relation.elements()
  16     }
  17
  18     pub fn is_empty(&self) -> bool {
  19         self.relation.is_empty()
  20     }
  21
  22     // Record that `'sup:'sub`. Or, put another way, `'sub <= 'sup`.
  23     // (with the exception that `'static: 'x` is not notable)
  24     pub fn relate_regions(&mut self, sub: Region<'tcx>, sup: Region<'tcx>) {
  25         debug!("relate_regions(sub={:?}, sup={:?})", sub, sup);
  26         if self.is_free_or_static(sub) && self.is_free(sup) {
  27             self.relation.add(sub, sup)
  28         }
  29     }
  30
  31     /// Tests whether `r_a <= r_b`.
  32     ///
  33     /// Both regions must meet `is_free_or_static`.
  34     ///
  35     /// Subtle: one tricky case that this code gets correct is as
  36     /// follows. If we know that `r_b: 'static`, then this function
  37     /// will return true, even though we don't know anything that
  38     /// directly relates `r_a` and `r_b`.
  39     ///
  40     /// Also available through the `FreeRegionRelations` trait below.
  41     pub fn sub_free_regions(
  42         &self,
  43         tcx: TyCtxt<'tcx>,
  44         r_a: Region<'tcx>,
  45         r_b: Region<'tcx>,
  46     ) -> bool {
  47         assert!(self.is_free_or_static(r_a) && self.is_free_or_static(r_b));
  48         let re_static = tcx.lifetimes.re_static;
  49         if self.check_relation(re_static, r_b) {
  50             // `'a <= 'static` is always true, and not stored in the
  51             // relation explicitly, so check if `'b` is `'static` (or
  52             // equivalent to it)
  53             true
  54         } else {
  55             self.check_relation(r_a, r_b)
  56         }
  57     }
  58
  59     /// Check whether `r_a <= r_b` is found in the relation.
  60     fn check_relation(&self, r_a: Region<'tcx>, r_b: Region<'tcx>) -> bool {
  61         r_a == r_b || self.relation.contains(&r_a, &r_b)
  62     }
  63
  64     /// True for free regions other than `'static`.
  65     pub fn is_free(&self, r: Region<'_>) -> bool {
  66         match *r {
  67             ty::ReEarlyBound(_) | ty::ReFree(_) => true,
  68             _ => false,
  69         }
  70     }
  71
  72     /// True if `r` is a free region or static of the sort that this
  73     /// free region map can be used with.
  74     pub fn is_free_or_static(&self, r: Region<'_>) -> bool {
  75         match *r {
  76             ty::ReStatic => true,
  77             _ => self.is_free(r),
  78         }
  79     }
  80
  81     /// Computes the least-upper-bound of two free regions. In some
  82     /// cases, this is more conservative than necessary, in order to
  83     /// avoid making arbitrary choices. See
  84     /// `TransitiveRelation::postdom_upper_bound` for more details.
  85     pub fn lub_free_regions(
  86         &self,
  87         tcx: TyCtxt<'tcx>,
  88         r_a: Region<'tcx>,
  89         r_b: Region<'tcx>,
  90     ) -> Region<'tcx> {
  91         debug!("lub_free_regions(r_a={:?}, r_b={:?})", r_a, r_b);
  92         assert!(self.is_free(r_a));
  93         assert!(self.is_free(r_b));
  94         let result = if r_a == r_b {
  95             r_a
  96         } else {
  97             match self.relation.postdom_upper_bound(&r_a, &r_b) {
  98                 None => tcx.lifetimes.re_static,
  99                 Some(r) => *r,
 100             }
 101         };
 102         debug!("lub_free_regions(r_a={:?}, r_b={:?}) = {:?}", r_a, r_b, result);
 103         result
 104     }
 105 }
 106
 107 /// The NLL region handling code represents free region relations in a
 108 /// slightly different way; this trait allows functions to be abstract
 109 /// over which version is in use.
 110 pub trait FreeRegionRelations<'tcx> {
 111     /// Tests whether `r_a <= r_b`. Both must be free regions or
 112     /// `'static`.
 113     fn sub_free_regions(
 114         &self,
 115         tcx: TyCtxt<'tcx>,
 116         shorter: ty::Region<'tcx>,
 117         longer: ty::Region<'tcx>,
 118     ) -> bool;
 119 }
 120
 121 impl<'tcx> FreeRegionRelations<'tcx> for FreeRegionMap<'tcx> {
 122     fn sub_free_regions(&self, tcx: TyCtxt<'tcx>, r_a: Region<'tcx>, r_b: Region<'tcx>) -> bool {
 123         // invoke the "inherent method"
 124         self.sub_free_regions(tcx, r_a, r_b)
 125     }
 126 }
 127
 128 impl<'a, 'tcx> Lift<'tcx> for FreeRegionMap<'a> {
 129     type Lifted = FreeRegionMap<'tcx>;
 130     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<FreeRegionMap<'tcx>> {
 131         self.relation.maybe_map(|&fr| tcx.lift(&fr)).map(|relation| FreeRegionMap { relation })
 132     }
 133 }