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