1 files changed, 119 insertions, 0 deletions
diff --git a/compiler/rustc_infer/src/infer/free_regions.rs b/compiler/rustc_infer/src/infer/free_regions.rs
new file mode 100644
index 000000000..d566634a4
--- /dev/null
+++ b/compiler/rustc_infer/src/infer/free_regions.rs
@@ -0,0 +1,119 @@
+//! This module handles the relationships between "free regions", i.e., lifetime parameters.
+//! Ordinarily, free regions are unrelated to one another, but they can be related via implied
+//! or explicit bounds. In that case, we track the bounds using the `TransitiveRelation` type,
+//! and use that to decide when one free region outlives another, and so forth.
+
+use rustc_data_structures::transitive_relation::TransitiveRelation;
+use rustc_middle::ty::{Lift, Region, TyCtxt};
+
+/// Combines a `FreeRegionMap` and a `TyCtxt`.
+///
+/// This stuff is a bit convoluted and should be refactored, but as we
+/// transition to NLL, it'll all go away anyhow.
+pub(crate) struct RegionRelations<'a, 'tcx> {
+    pub tcx: TyCtxt<'tcx>,
+
+    /// Free-region relationships.
+    pub free_regions: &'a FreeRegionMap<'tcx>,
+}
+
+impl<'a, 'tcx> RegionRelations<'a, 'tcx> {
+    pub fn new(tcx: TyCtxt<'tcx>, free_regions: &'a FreeRegionMap<'tcx>) -> Self {
+        Self { tcx, free_regions }
+    }
+
+    pub fn lub_free_regions(&self, r_a: Region<'tcx>, r_b: Region<'tcx>) -> Region<'tcx> {
+        self.free_regions.lub_free_regions(self.tcx, r_a, r_b)
+    }
+}
+
+#[derive(Clone, Debug, Default)]
+pub struct FreeRegionMap<'tcx> {
+    // Stores the relation `a < b`, where `a` and `b` are regions.
+    //
+    // Invariant: only free regions like `'x` or `'static` are stored
+    // in this relation, not scopes.
+    relation: TransitiveRelation<Region<'tcx>>,
+}
+
+impl<'tcx> FreeRegionMap<'tcx> {
+    pub fn elements(&self) -> impl Iterator<Item = Region<'tcx>> + '_ {
+        self.relation.elements().copied()
+    }
+
+    pub fn is_empty(&self) -> bool {
+        self.relation.is_empty()
+    }
+
+    // Record that `'sup:'sub`. Or, put another way, `'sub <= 'sup`.
+    // (with the exception that `'static: 'x` is not notable)
+    pub fn relate_regions(&mut self, sub: Region<'tcx>, sup: Region<'tcx>) {
+        debug!("relate_regions(sub={:?}, sup={:?})", sub, sup);
+        if sub.is_free_or_static() && sup.is_free() {
+            self.relation.add(sub, sup)
+        }
+    }
+
+    /// Tests whether `r_a <= r_b`.
+    ///
+    /// Both regions must meet `is_free_or_static`.
+    ///
+    /// Subtle: one tricky case that this code gets correct is as
+    /// follows. If we know that `r_b: 'static`, then this function
+    /// will return true, even though we don't know anything that
+    /// directly relates `r_a` and `r_b`.
+    pub fn sub_free_regions(
+        &self,
+        tcx: TyCtxt<'tcx>,
+        r_a: Region<'tcx>,
+        r_b: Region<'tcx>,
+    ) -> bool {
+        assert!(r_a.is_free_or_static() && r_b.is_free_or_static());
+        let re_static = tcx.lifetimes.re_static;
+        if self.check_relation(re_static, r_b) {
+            // `'a <= 'static` is always true, and not stored in the
+            // relation explicitly, so check if `'b` is `'static` (or
+            // equivalent to it)
+            true
+        } else {
+            self.check_relation(r_a, r_b)
+        }
+    }
+
+    /// Check whether `r_a <= r_b` is found in the relation.
+    fn check_relation(&self, r_a: Region<'tcx>, r_b: Region<'tcx>) -> bool {
+        r_a == r_b || self.relation.contains(r_a, r_b)
+    }
+
+    /// Computes the least-upper-bound of two free regions. In some
+    /// cases, this is more conservative than necessary, in order to
+    /// avoid making arbitrary choices. See
+    /// `TransitiveRelation::postdom_upper_bound` for more details.
+    pub fn lub_free_regions(
+        &self,
+        tcx: TyCtxt<'tcx>,
+        r_a: Region<'tcx>,
+        r_b: Region<'tcx>,
+    ) -> Region<'tcx> {
+        debug!("lub_free_regions(r_a={:?}, r_b={:?})", r_a, r_b);
+        assert!(r_a.is_free());
+        assert!(r_b.is_free());
+        let result = if r_a == r_b {
+            r_a
+        } else {
+            match self.relation.postdom_upper_bound(r_a, r_b) {
+                None => tcx.lifetimes.re_static,
+                Some(r) => r,
+            }
+        };
+        debug!("lub_free_regions(r_a={:?}, r_b={:?}) = {:?}", r_a, r_b, result);
+        result
+    }
+}
+
+impl<'a, 'tcx> Lift<'tcx> for FreeRegionMap<'a> {
+    type Lifted = FreeRegionMap<'tcx>;
+    fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<FreeRegionMap<'tcx>> {
+        self.relation.maybe_map(|fr| tcx.lift(fr)).map(|relation| FreeRegionMap { relation })
+    }
+}