src/librustc_infer/infer/free_regions.rs

   1 //! This module handles the relationships between "free regions", i.e., lifetime parameters.
   2 //! Ordinarily, free regions are unrelated to one another, but they can be related via implied
   3 //! or explicit bounds. In that case, we track the bounds using the `TransitiveRelation` type,
   4 //! and use that to decide when one free region outlives another, and so forth.
   5
   6 use rustc_data_structures::transitive_relation::TransitiveRelation;
   7 use rustc_hir::def_id::DefId;
   8 use rustc_middle::ty::{self, Lift, Region, TyCtxt};
   9
  10 /// Combines a `region::ScopeTree` (which governs relationships between
  11 /// scopes) and a `FreeRegionMap` (which governs relationships between
  12 /// free regions) to yield a complete relation between concrete
  13 /// regions.
  14 ///
  15 /// This stuff is a bit convoluted and should be refactored, but as we
  16 /// transition to NLL, it'll all go away anyhow.
  17 pub struct RegionRelations<'a, 'tcx> {
  18     pub tcx: TyCtxt<'tcx>,
  19
  20     /// The context used to fetch the region maps.
  21     pub context: DefId,
  22
  23     /// Free-region relationships.
  24     pub free_regions: &'a FreeRegionMap<'tcx>,
  25 }
  26
  27 impl<'a, 'tcx> RegionRelations<'a, 'tcx> {
  28     pub fn new(tcx: TyCtxt<'tcx>, context: DefId, free_regions: &'a FreeRegionMap<'tcx>) -> Self {
  29         Self { tcx, context, free_regions }
  30     }
  31
  32     pub fn lub_free_regions(&self, r_a: Region<'tcx>, r_b: Region<'tcx>) -> Region<'tcx> {
  33         self.free_regions.lub_free_regions(self.tcx, r_a, r_b)
  34     }
  35 }
  36
  37 #[derive(Clone, RustcEncodable, RustcDecodable, Debug, Default, HashStable)]
  38 pub struct FreeRegionMap<'tcx> {
  39     // Stores the relation `a < b`, where `a` and `b` are regions.
  40     //
  41     // Invariant: only free regions like `'x` or `'static` are stored
  42     // in this relation, not scopes.
  43     relation: TransitiveRelation<Region<'tcx>>,
  44 }
  45
  46 impl<'tcx> FreeRegionMap<'tcx> {
  47     pub fn elements(&self) -> impl Iterator<Item = &Region<'tcx>> {
  48         self.relation.elements()
  49     }
  50
  51     pub fn is_empty(&self) -> bool {
  52         self.relation.is_empty()
  53     }
  54
  55     // Record that `'sup:'sub`. Or, put another way, `'sub <= 'sup`.
  56     // (with the exception that `'static: 'x` is not notable)
  57     pub fn relate_regions(&mut self, sub: Region<'tcx>, sup: Region<'tcx>) {
  58         debug!("relate_regions(sub={:?}, sup={:?})", sub, sup);
  59         if self.is_free_or_static(sub) && self.is_free(sup) {
  60             self.relation.add(sub, sup)
  61         }
  62     }
  63
  64     /// Tests whether `r_a <= r_b`.
  65     ///
  66     /// Both regions must meet `is_free_or_static`.
  67     ///
  68     /// Subtle: one tricky case that this code gets correct is as
  69     /// follows. If we know that `r_b: 'static`, then this function
  70     /// will return true, even though we don't know anything that
  71     /// directly relates `r_a` and `r_b`.
  72     ///
  73     /// Also available through the `FreeRegionRelations` trait below.
  74     pub fn sub_free_regions(
  75         &self,
  76         tcx: TyCtxt<'tcx>,
  77         r_a: Region<'tcx>,
  78         r_b: Region<'tcx>,
  79     ) -> bool {
  80         assert!(self.is_free_or_static(r_a) && self.is_free_or_static(r_b));
  81         let re_static = tcx.lifetimes.re_static;
  82         if self.check_relation(re_static, r_b) {
  83             // `'a <= 'static` is always true, and not stored in the
  84             // relation explicitly, so check if `'b` is `'static` (or
  85             // equivalent to it)
  86             true
  87         } else {
  88             self.check_relation(r_a, r_b)
  89         }
  90     }
  91
  92     /// Check whether `r_a <= r_b` is found in the relation.
  93     fn check_relation(&self, r_a: Region<'tcx>, r_b: Region<'tcx>) -> bool {
  94         r_a == r_b || self.relation.contains(&r_a, &r_b)
  95     }
  96
  97     /// True for free regions other than `'static`.
  98     pub fn is_free(&self, r: Region<'_>) -> bool {
  99         match *r {
 100             ty::ReEarlyBound(_) | ty::ReFree(_) => true,
 101             _ => false,
 102         }
 103     }
 104
 105     /// True if `r` is a free region or static of the sort that this
 106     /// free region map can be used with.
 107     pub fn is_free_or_static(&self, r: Region<'_>) -> bool {
 108         match *r {
 109             ty::ReStatic => true,
 110             _ => self.is_free(r),
 111         }
 112     }
 113
 114     /// Computes the least-upper-bound of two free regions. In some
 115     /// cases, this is more conservative than necessary, in order to
 116     /// avoid making arbitrary choices. See
 117     /// `TransitiveRelation::postdom_upper_bound` for more details.
 118     pub fn lub_free_regions(
 119         &self,
 120         tcx: TyCtxt<'tcx>,
 121         r_a: Region<'tcx>,
 122         r_b: Region<'tcx>,
 123     ) -> Region<'tcx> {
 124         debug!("lub_free_regions(r_a={:?}, r_b={:?})", r_a, r_b);
 125         assert!(self.is_free(r_a));
 126         assert!(self.is_free(r_b));
 127         let result = if r_a == r_b {
 128             r_a
 129         } else {
 130             match self.relation.postdom_upper_bound(&r_a, &r_b) {
 131                 None => tcx.lifetimes.re_static,
 132                 Some(r) => *r,
 133             }
 134         };
 135         debug!("lub_free_regions(r_a={:?}, r_b={:?}) = {:?}", r_a, r_b, result);
 136         result
 137     }
 138 }
 139
 140 /// The NLL region handling code represents free region relations in a
 141 /// slightly different way; this trait allows functions to be abstract
 142 /// over which version is in use.
 143 pub trait FreeRegionRelations<'tcx> {
 144     /// Tests whether `r_a <= r_b`. Both must be free regions or
 145     /// `'static`.
 146     fn sub_free_regions(
 147         &self,
 148         tcx: TyCtxt<'tcx>,
 149         shorter: ty::Region<'tcx>,
 150         longer: ty::Region<'tcx>,
 151     ) -> bool;
 152 }
 153
 154 impl<'tcx> FreeRegionRelations<'tcx> for FreeRegionMap<'tcx> {
 155     fn sub_free_regions(&self, tcx: TyCtxt<'tcx>, r_a: Region<'tcx>, r_b: Region<'tcx>) -> bool {
 156         // invoke the "inherent method"
 157         self.sub_free_regions(tcx, r_a, r_b)
 158     }
 159 }
 160
 161 impl<'a, 'tcx> Lift<'tcx> for FreeRegionMap<'a> {
 162     type Lifted = FreeRegionMap<'tcx>;
 163     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<FreeRegionMap<'tcx>> {
 164         self.relation.maybe_map(|&fr| tcx.lift(&fr)).map(|relation| FreeRegionMap { relation })
 165     }
 166 }