compiler/rustc_infer/src/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_middle::ty::{Lift, Region, TyCtxt};
   8
   9 /// Combines a `FreeRegionMap` and a `TyCtxt`.
  10 ///
  11 /// This stuff is a bit convoluted and should be refactored, but as we
  12 /// transition to NLL, it'll all go away anyhow.
  13 pub(crate) struct RegionRelations<'a, 'tcx> {
  14     pub tcx: TyCtxt<'tcx>,
  15
  16     /// Free-region relationships.
  17     pub free_regions: &'a FreeRegionMap<'tcx>,
  18 }
  19
  20 impl<'a, 'tcx> RegionRelations<'a, 'tcx> {
  21     pub fn new(tcx: TyCtxt<'tcx>, free_regions: &'a FreeRegionMap<'tcx>) -> Self {
  22         Self { tcx, free_regions }
  23     }
  24
  25     pub fn lub_free_regions(&self, r_a: Region<'tcx>, r_b: Region<'tcx>) -> Region<'tcx> {
  26         self.free_regions.lub_free_regions(self.tcx, r_a, r_b)
  27     }
  28 }
  29
  30 #[derive(Clone, Debug)]
  31 pub struct FreeRegionMap<'tcx> {
  32     // Stores the relation `a < b`, where `a` and `b` are regions.
  33     //
  34     // Invariant: only free regions like `'x` or `'static` are stored
  35     // in this relation, not scopes.
  36     pub(crate) relation: TransitiveRelation<Region<'tcx>>,
  37 }
  38
  39 impl<'tcx> FreeRegionMap<'tcx> {
  40     pub fn elements(&self) -> impl Iterator<Item = Region<'tcx>> + '_ {
  41         self.relation.elements().copied()
  42     }
  43
  44     pub fn is_empty(&self) -> bool {
  45         self.relation.is_empty()
  46     }
  47
  48     /// Tests whether `r_a <= r_b`.
  49     ///
  50     /// Both regions must meet `is_free_or_static`.
  51     ///
  52     /// Subtle: one tricky case that this code gets correct is as
  53     /// follows. If we know that `r_b: 'static`, then this function
  54     /// will return true, even though we don't know anything that
  55     /// directly relates `r_a` and `r_b`.
  56     pub fn sub_free_regions(
  57         &self,
  58         tcx: TyCtxt<'tcx>,
  59         r_a: Region<'tcx>,
  60         r_b: Region<'tcx>,
  61     ) -> bool {
  62         assert!(r_a.is_free_or_static() && r_b.is_free_or_static());
  63         let re_static = tcx.lifetimes.re_static;
  64         if self.check_relation(re_static, r_b) {
  65             // `'a <= 'static` is always true, and not stored in the
  66             // relation explicitly, so check if `'b` is `'static` (or
  67             // equivalent to it)
  68             true
  69         } else {
  70             self.check_relation(r_a, r_b)
  71         }
  72     }
  73
  74     /// Check whether `r_a <= r_b` is found in the relation.
  75     fn check_relation(&self, r_a: Region<'tcx>, r_b: Region<'tcx>) -> bool {
  76         r_a == r_b || self.relation.contains(r_a, r_b)
  77     }
  78
  79     /// Computes the least-upper-bound of two free regions. In some
  80     /// cases, this is more conservative than necessary, in order to
  81     /// avoid making arbitrary choices. See
  82     /// `TransitiveRelation::postdom_upper_bound` for more details.
  83     pub fn lub_free_regions(
  84         &self,
  85         tcx: TyCtxt<'tcx>,
  86         r_a: Region<'tcx>,
  87         r_b: Region<'tcx>,
  88     ) -> Region<'tcx> {
  89         debug!("lub_free_regions(r_a={:?}, r_b={:?})", r_a, r_b);
  90         assert!(r_a.is_free());
  91         assert!(r_b.is_free());
  92         let result = if r_a == r_b {
  93             r_a
  94         } else {
  95             match self.relation.postdom_upper_bound(r_a, r_b) {
  96                 None => tcx.lifetimes.re_static,
  97                 Some(r) => r,
  98             }
  99         };
 100         debug!("lub_free_regions(r_a={:?}, r_b={:?}) = {:?}", r_a, r_b, result);
 101         result
 102     }
 103 }
 104
 105 impl<'a, 'tcx> Lift<'tcx> for FreeRegionMap<'a> {
 106     type Lifted = FreeRegionMap<'tcx>;
 107     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<FreeRegionMap<'tcx>> {
 108         self.relation.maybe_map(|fr| tcx.lift(fr)).map(|relation| FreeRegionMap { relation })
 109     }
 110 }