2 files changed, 359 insertions, 0 deletions
diff --git a/compiler/rustc_borrowck/src/constraints/graph.rs b/compiler/rustc_borrowck/src/constraints/graph.rs
new file mode 100644
index 000000000..609fbc2bc
--- /dev/null
+++ b/compiler/rustc_borrowck/src/constraints/graph.rs
@@ -0,0 +1,235 @@
+use rustc_data_structures::graph;
+use rustc_index::vec::IndexVec;
+use rustc_middle::mir::ConstraintCategory;
+use rustc_middle::ty::{RegionVid, VarianceDiagInfo};
+use rustc_span::DUMMY_SP;
+
+use crate::{
+    constraints::OutlivesConstraintIndex,
+    constraints::{OutlivesConstraint, OutlivesConstraintSet},
+    type_check::Locations,
+};
+
+/// The construct graph organizes the constraints by their end-points.
+/// It can be used to view a `R1: R2` constraint as either an edge `R1
+/// -> R2` or `R2 -> R1` depending on the direction type `D`.
+pub(crate) struct ConstraintGraph<D: ConstraintGraphDirecton> {
+    _direction: D,
+    first_constraints: IndexVec<RegionVid, Option<OutlivesConstraintIndex>>,
+    next_constraints: IndexVec<OutlivesConstraintIndex, Option<OutlivesConstraintIndex>>,
+}
+
+pub(crate) type NormalConstraintGraph = ConstraintGraph<Normal>;
+
+pub(crate) type ReverseConstraintGraph = ConstraintGraph<Reverse>;
+
+/// Marker trait that controls whether a `R1: R2` constraint
+/// represents an edge `R1 -> R2` or `R2 -> R1`.
+pub(crate) trait ConstraintGraphDirecton: Copy + 'static {
+    fn start_region(c: &OutlivesConstraint<'_>) -> RegionVid;
+    fn end_region(c: &OutlivesConstraint<'_>) -> RegionVid;
+    fn is_normal() -> bool;
+}
+
+/// In normal mode, a `R1: R2` constraint results in an edge `R1 ->
+/// R2`. This is what we use when constructing the SCCs for
+/// inference. This is because we compute the value of R1 by union'ing
+/// all the things that it relies on.
+#[derive(Copy, Clone, Debug)]
+pub(crate) struct Normal;
+
+impl ConstraintGraphDirecton for Normal {
+    fn start_region(c: &OutlivesConstraint<'_>) -> RegionVid {
+        c.sup
+    }
+
+    fn end_region(c: &OutlivesConstraint<'_>) -> RegionVid {
+        c.sub
+    }
+
+    fn is_normal() -> bool {
+        true
+    }
+}
+
+/// In reverse mode, a `R1: R2` constraint results in an edge `R2 ->
+/// R1`. We use this for optimizing liveness computation, because then
+/// we wish to iterate from a region (e.g., R2) to all the regions
+/// that will outlive it (e.g., R1).
+#[derive(Copy, Clone, Debug)]
+pub(crate) struct Reverse;
+
+impl ConstraintGraphDirecton for Reverse {
+    fn start_region(c: &OutlivesConstraint<'_>) -> RegionVid {
+        c.sub
+    }
+
+    fn end_region(c: &OutlivesConstraint<'_>) -> RegionVid {
+        c.sup
+    }
+
+    fn is_normal() -> bool {
+        false
+    }
+}
+
+impl<D: ConstraintGraphDirecton> ConstraintGraph<D> {
+    /// Creates a "dependency graph" where each region constraint `R1:
+    /// R2` is treated as an edge `R1 -> R2`. We use this graph to
+    /// construct SCCs for region inference but also for error
+    /// reporting.
+    pub(crate) fn new(
+        direction: D,
+        set: &OutlivesConstraintSet<'_>,
+        num_region_vars: usize,
+    ) -> Self {
+        let mut first_constraints = IndexVec::from_elem_n(None, num_region_vars);
+        let mut next_constraints = IndexVec::from_elem(None, &set.outlives);
+
+        for (idx, constraint) in set.outlives.iter_enumerated().rev() {
+            let head = &mut first_constraints[D::start_region(constraint)];
+            let next = &mut next_constraints[idx];
+            debug_assert!(next.is_none());
+            *next = *head;
+            *head = Some(idx);
+        }
+
+        Self { _direction: direction, first_constraints, next_constraints }
+    }
+
+    /// Given the constraint set from which this graph was built
+    /// creates a region graph so that you can iterate over *regions*
+    /// and not constraints.
+    pub(crate) fn region_graph<'rg, 'tcx>(
+        &'rg self,
+        set: &'rg OutlivesConstraintSet<'tcx>,
+        static_region: RegionVid,
+    ) -> RegionGraph<'rg, 'tcx, D> {
+        RegionGraph::new(set, self, static_region)
+    }
+
+    /// Given a region `R`, iterate over all constraints `R: R1`.
+    pub(crate) fn outgoing_edges<'a, 'tcx>(
+        &'a self,
+        region_sup: RegionVid,
+        constraints: &'a OutlivesConstraintSet<'tcx>,
+        static_region: RegionVid,
+    ) -> Edges<'a, 'tcx, D> {
+        //if this is the `'static` region and the graph's direction is normal,
+        //then setup the Edges iterator to return all regions #53178
+        if region_sup == static_region && D::is_normal() {
+            Edges {
+                graph: self,
+                constraints,
+                pointer: None,
+                next_static_idx: Some(0),
+                static_region,
+            }
+        } else {
+            //otherwise, just setup the iterator as normal
+            let first = self.first_constraints[region_sup];
+            Edges { graph: self, constraints, pointer: first, next_static_idx: None, static_region }
+        }
+    }
+}
+
+pub(crate) struct Edges<'s, 'tcx, D: ConstraintGraphDirecton> {
+    graph: &'s ConstraintGraph<D>,
+    constraints: &'s OutlivesConstraintSet<'tcx>,
+    pointer: Option<OutlivesConstraintIndex>,
+    next_static_idx: Option<usize>,
+    static_region: RegionVid,
+}
+
+impl<'s, 'tcx, D: ConstraintGraphDirecton> Iterator for Edges<'s, 'tcx, D> {
+    type Item = OutlivesConstraint<'tcx>;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        if let Some(p) = self.pointer {
+            self.pointer = self.graph.next_constraints[p];
+
+            Some(self.constraints[p].clone())
+        } else if let Some(next_static_idx) = self.next_static_idx {
+            self.next_static_idx = if next_static_idx == (self.graph.first_constraints.len() - 1) {
+                None
+            } else {
+                Some(next_static_idx + 1)
+            };
+
+            Some(OutlivesConstraint {
+                sup: self.static_region,
+                sub: next_static_idx.into(),
+                locations: Locations::All(DUMMY_SP),
+                span: DUMMY_SP,
+                category: ConstraintCategory::Internal,
+                variance_info: VarianceDiagInfo::default(),
+            })
+        } else {
+            None
+        }
+    }
+}
+
+/// This struct brings together a constraint set and a (normal, not
+/// reverse) constraint graph. It implements the graph traits and is
+/// usd for doing the SCC computation.
+pub(crate) struct RegionGraph<'s, 'tcx, D: ConstraintGraphDirecton> {
+    set: &'s OutlivesConstraintSet<'tcx>,
+    constraint_graph: &'s ConstraintGraph<D>,
+    static_region: RegionVid,
+}
+
+impl<'s, 'tcx, D: ConstraintGraphDirecton> RegionGraph<'s, 'tcx, D> {
+    /// Creates a "dependency graph" where each region constraint `R1:
+    /// R2` is treated as an edge `R1 -> R2`. We use this graph to
+    /// construct SCCs for region inference but also for error
+    /// reporting.
+    pub(crate) fn new(
+        set: &'s OutlivesConstraintSet<'tcx>,
+        constraint_graph: &'s ConstraintGraph<D>,
+        static_region: RegionVid,
+    ) -> Self {
+        Self { set, constraint_graph, static_region }
+    }
+
+    /// Given a region `R`, iterate over all regions `R1` such that
+    /// there exists a constraint `R: R1`.
+    pub(crate) fn outgoing_regions(&self, region_sup: RegionVid) -> Successors<'s, 'tcx, D> {
+        Successors {
+            edges: self.constraint_graph.outgoing_edges(region_sup, self.set, self.static_region),
+        }
+    }
+}
+
+pub(crate) struct Successors<'s, 'tcx, D: ConstraintGraphDirecton> {
+    edges: Edges<'s, 'tcx, D>,
+}
+
+impl<'s, 'tcx, D: ConstraintGraphDirecton> Iterator for Successors<'s, 'tcx, D> {
+    type Item = RegionVid;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.edges.next().map(|c| D::end_region(&c))
+    }
+}
+
+impl<'s, 'tcx, D: ConstraintGraphDirecton> graph::DirectedGraph for RegionGraph<'s, 'tcx, D> {
+    type Node = RegionVid;
+}
+
+impl<'s, 'tcx, D: ConstraintGraphDirecton> graph::WithNumNodes for RegionGraph<'s, 'tcx, D> {
+    fn num_nodes(&self) -> usize {
+        self.constraint_graph.first_constraints.len()
+    }
+}
+
+impl<'s, 'tcx, D: ConstraintGraphDirecton> graph::WithSuccessors for RegionGraph<'s, 'tcx, D> {
+    fn successors(&self, node: Self::Node) -> <Self as graph::GraphSuccessors<'_>>::Iter {
+        self.outgoing_regions(node)
+    }
+}
+
+impl<'s, 'tcx, D: ConstraintGraphDirecton> graph::GraphSuccessors<'_> for RegionGraph<'s, 'tcx, D> {
+    type Item = RegionVid;
+    type Iter = Successors<'s, 'tcx, D>;
+}
diff --git a/compiler/rustc_borrowck/src/constraints/mod.rs b/compiler/rustc_borrowck/src/constraints/mod.rs
new file mode 100644
index 000000000..a504d0c91
--- /dev/null
+++ b/compiler/rustc_borrowck/src/constraints/mod.rs
@@ -0,0 +1,124 @@
+use rustc_data_structures::graph::scc::Sccs;
+use rustc_index::vec::IndexVec;
+use rustc_middle::mir::ConstraintCategory;
+use rustc_middle::ty::{RegionVid, VarianceDiagInfo};
+use rustc_span::Span;
+use std::fmt;
+use std::ops::Index;
+
+use crate::type_check::Locations;
+
+pub(crate) mod graph;
+
+/// A set of NLL region constraints. These include "outlives"
+/// constraints of the form `R1: R2`. Each constraint is identified by
+/// a unique `OutlivesConstraintIndex` and you can index into the set
+/// (`constraint_set[i]`) to access the constraint details.
+#[derive(Clone, Default)]
+pub(crate) struct OutlivesConstraintSet<'tcx> {
+    outlives: IndexVec<OutlivesConstraintIndex, OutlivesConstraint<'tcx>>,
+}
+
+impl<'tcx> OutlivesConstraintSet<'tcx> {
+    pub(crate) fn push(&mut self, constraint: OutlivesConstraint<'tcx>) {
+        debug!(
+            "OutlivesConstraintSet::push({:?}: {:?} @ {:?}",
+            constraint.sup, constraint.sub, constraint.locations
+        );
+        if constraint.sup == constraint.sub {
+            // 'a: 'a is pretty uninteresting
+            return;
+        }
+        self.outlives.push(constraint);
+    }
+
+    /// Constructs a "normal" graph from the constraint set; the graph makes it
+    /// easy to find the constraints affecting a particular region.
+    ///
+    /// N.B., this graph contains a "frozen" view of the current
+    /// constraints. Any new constraints added to the `OutlivesConstraintSet`
+    /// after the graph is built will not be present in the graph.
+    pub(crate) fn graph(&self, num_region_vars: usize) -> graph::NormalConstraintGraph {
+        graph::ConstraintGraph::new(graph::Normal, self, num_region_vars)
+    }
+
+    /// Like `graph`, but constraints a reverse graph where `R1: R2`
+    /// represents an edge `R2 -> R1`.
+    pub(crate) fn reverse_graph(&self, num_region_vars: usize) -> graph::ReverseConstraintGraph {
+        graph::ConstraintGraph::new(graph::Reverse, self, num_region_vars)
+    }
+
+    /// Computes cycles (SCCs) in the graph of regions. In particular,
+    /// find all regions R1, R2 such that R1: R2 and R2: R1 and group
+    /// them into an SCC, and find the relationships between SCCs.
+    pub(crate) fn compute_sccs(
+        &self,
+        constraint_graph: &graph::NormalConstraintGraph,
+        static_region: RegionVid,
+    ) -> Sccs<RegionVid, ConstraintSccIndex> {
+        let region_graph = &constraint_graph.region_graph(self, static_region);
+        Sccs::new(region_graph)
+    }
+
+    pub(crate) fn outlives(&self) -> &IndexVec<OutlivesConstraintIndex, OutlivesConstraint<'tcx>> {
+        &self.outlives
+    }
+}
+
+impl<'tcx> Index<OutlivesConstraintIndex> for OutlivesConstraintSet<'tcx> {
+    type Output = OutlivesConstraint<'tcx>;
+
+    fn index(&self, i: OutlivesConstraintIndex) -> &Self::Output {
+        &self.outlives[i]
+    }
+}
+
+#[derive(Clone, PartialEq, Eq)]
+pub struct OutlivesConstraint<'tcx> {
+    // NB. The ordering here is not significant for correctness, but
+    // it is for convenience. Before we dump the constraints in the
+    // debugging logs, we sort them, and we'd like the "super region"
+    // to be first, etc. (In particular, span should remain last.)
+    /// The region SUP must outlive SUB...
+    pub sup: RegionVid,
+
+    /// Region that must be outlived.
+    pub sub: RegionVid,
+
+    /// Where did this constraint arise?
+    pub locations: Locations,
+
+    /// The `Span` associated with the creation of this constraint.
+    /// This should be used in preference to obtaining the span from
+    /// `locations`, since the `locations` may give a poor span
+    /// in some cases (e.g. converting a constraint from a promoted).
+    pub span: Span,
+
+    /// What caused this constraint?
+    pub category: ConstraintCategory<'tcx>,
+
+    /// Variance diagnostic information
+    pub variance_info: VarianceDiagInfo<'tcx>,
+}
+
+impl<'tcx> fmt::Debug for OutlivesConstraint<'tcx> {
+    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(
+            formatter,
+            "({:?}: {:?}) due to {:?} ({:?})",
+            self.sup, self.sub, self.locations, self.variance_info
+        )
+    }
+}
+
+rustc_index::newtype_index! {
+    pub struct OutlivesConstraintIndex {
+        DEBUG_FORMAT = "OutlivesConstraintIndex({})"
+    }
+}
+
+rustc_index::newtype_index! {
+    pub struct ConstraintSccIndex {
+        DEBUG_FORMAT = "ConstraintSccIndex({})"
+    }
+}