compiler/rustc_mir/src/borrow_check/constraints/graph.rs

   1 use rustc_data_structures::graph;
   2 use rustc_index::vec::IndexVec;
   3 use rustc_middle::mir::ConstraintCategory;
   4 use rustc_middle::ty::RegionVid;
   5 use rustc_span::DUMMY_SP;
   6
   7 use crate::borrow_check::{
   8     constraints::OutlivesConstraintIndex,
   9     constraints::{OutlivesConstraint, OutlivesConstraintSet},
  10     type_check::Locations,
  11 };
  12
  13 /// The construct graph organizes the constraints by their end-points.
  14 /// It can be used to view a `R1: R2` constraint as either an edge `R1
  15 /// -> R2` or `R2 -> R1` depending on the direction type `D`.
  16 crate struct ConstraintGraph<D: ConstraintGraphDirecton> {
  17     _direction: D,
  18     first_constraints: IndexVec<RegionVid, Option<OutlivesConstraintIndex>>,
  19     next_constraints: IndexVec<OutlivesConstraintIndex, Option<OutlivesConstraintIndex>>,
  20 }
  21
  22 crate type NormalConstraintGraph = ConstraintGraph<Normal>;
  23
  24 crate type ReverseConstraintGraph = ConstraintGraph<Reverse>;
  25
  26 /// Marker trait that controls whether a `R1: R2` constraint
  27 /// represents an edge `R1 -> R2` or `R2 -> R1`.
  28 crate trait ConstraintGraphDirecton: Copy + 'static {
  29     fn start_region(c: &OutlivesConstraint) -> RegionVid;
  30     fn end_region(c: &OutlivesConstraint) -> RegionVid;
  31     fn is_normal() -> bool;
  32 }
  33
  34 /// In normal mode, a `R1: R2` constraint results in an edge `R1 ->
  35 /// R2`. This is what we use when constructing the SCCs for
  36 /// inference. This is because we compute the value of R1 by union'ing
  37 /// all the things that it relies on.
  38 #[derive(Copy, Clone, Debug)]
  39 crate struct Normal;
  40
  41 impl ConstraintGraphDirecton for Normal {
  42     fn start_region(c: &OutlivesConstraint) -> RegionVid {
  43         c.sup
  44     }
  45
  46     fn end_region(c: &OutlivesConstraint) -> RegionVid {
  47         c.sub
  48     }
  49
  50     fn is_normal() -> bool {
  51         true
  52     }
  53 }
  54
  55 /// In reverse mode, a `R1: R2` constraint results in an edge `R2 ->
  56 /// R1`. We use this for optimizing liveness computation, because then
  57 /// we wish to iterate from a region (e.g., R2) to all the regions
  58 /// that will outlive it (e.g., R1).
  59 #[derive(Copy, Clone, Debug)]
  60 crate struct Reverse;
  61
  62 impl ConstraintGraphDirecton for Reverse {
  63     fn start_region(c: &OutlivesConstraint) -> RegionVid {
  64         c.sub
  65     }
  66
  67     fn end_region(c: &OutlivesConstraint) -> RegionVid {
  68         c.sup
  69     }
  70
  71     fn is_normal() -> bool {
  72         false
  73     }
  74 }
  75
  76 impl<D: ConstraintGraphDirecton> ConstraintGraph<D> {
  77     /// Creates a "dependency graph" where each region constraint `R1:
  78     /// R2` is treated as an edge `R1 -> R2`. We use this graph to
  79     /// construct SCCs for region inference but also for error
  80     /// reporting.
  81     crate fn new(direction: D, set: &OutlivesConstraintSet, num_region_vars: usize) -> Self {
  82         let mut first_constraints = IndexVec::from_elem_n(None, num_region_vars);
  83         let mut next_constraints = IndexVec::from_elem(None, &set.outlives);
  84
  85         for (idx, constraint) in set.outlives.iter_enumerated().rev() {
  86             let head = &mut first_constraints[D::start_region(constraint)];
  87             let next = &mut next_constraints[idx];
  88             debug_assert!(next.is_none());
  89             *next = *head;
  90             *head = Some(idx);
  91         }
  92
  93         Self { _direction: direction, first_constraints, next_constraints }
  94     }
  95
  96     /// Given the constraint set from which this graph was built
  97     /// creates a region graph so that you can iterate over *regions*
  98     /// and not constraints.
  99     crate fn region_graph<'rg>(
 100         &'rg self,
 101         set: &'rg OutlivesConstraintSet,
 102         static_region: RegionVid,
 103     ) -> RegionGraph<'rg, D> {
 104         RegionGraph::new(set, self, static_region)
 105     }
 106
 107     /// Given a region `R`, iterate over all constraints `R: R1`.
 108     crate fn outgoing_edges<'a>(
 109         &'a self,
 110         region_sup: RegionVid,
 111         constraints: &'a OutlivesConstraintSet,
 112         static_region: RegionVid,
 113     ) -> Edges<'a, D> {
 114         //if this is the `'static` region and the graph's direction is normal,
 115         //then setup the Edges iterator to return all regions #53178
 116         if region_sup == static_region && D::is_normal() {
 117             Edges {
 118                 graph: self,
 119                 constraints,
 120                 pointer: None,
 121                 next_static_idx: Some(0),
 122                 static_region,
 123             }
 124         } else {
 125             //otherwise, just setup the iterator as normal
 126             let first = self.first_constraints[region_sup];
 127             Edges { graph: self, constraints, pointer: first, next_static_idx: None, static_region }
 128         }
 129     }
 130 }
 131
 132 crate struct Edges<'s, D: ConstraintGraphDirecton> {
 133     graph: &'s ConstraintGraph<D>,
 134     constraints: &'s OutlivesConstraintSet,
 135     pointer: Option<OutlivesConstraintIndex>,
 136     next_static_idx: Option<usize>,
 137     static_region: RegionVid,
 138 }
 139
 140 impl<'s, D: ConstraintGraphDirecton> Iterator for Edges<'s, D> {
 141     type Item = OutlivesConstraint;
 142
 143     fn next(&mut self) -> Option<Self::Item> {
 144         if let Some(p) = self.pointer {
 145             self.pointer = self.graph.next_constraints[p];
 146
 147             Some(self.constraints[p])
 148         } else if let Some(next_static_idx) = self.next_static_idx {
 149             self.next_static_idx = if next_static_idx == (self.graph.first_constraints.len() - 1) {
 150                 None
 151             } else {
 152                 Some(next_static_idx + 1)
 153             };
 154
 155             Some(OutlivesConstraint {
 156                 sup: self.static_region,
 157                 sub: next_static_idx.into(),
 158                 locations: Locations::All(DUMMY_SP),
 159                 category: ConstraintCategory::Internal,
 160             })
 161         } else {
 162             None
 163         }
 164     }
 165 }
 166
 167 /// This struct brings together a constraint set and a (normal, not
 168 /// reverse) constraint graph. It implements the graph traits and is
 169 /// usd for doing the SCC computation.
 170 crate struct RegionGraph<'s, D: ConstraintGraphDirecton> {
 171     set: &'s OutlivesConstraintSet,
 172     constraint_graph: &'s ConstraintGraph<D>,
 173     static_region: RegionVid,
 174 }
 175
 176 impl<'s, D: ConstraintGraphDirecton> RegionGraph<'s, D> {
 177     /// Creates a "dependency graph" where each region constraint `R1:
 178     /// R2` is treated as an edge `R1 -> R2`. We use this graph to
 179     /// construct SCCs for region inference but also for error
 180     /// reporting.
 181     crate fn new(
 182         set: &'s OutlivesConstraintSet,
 183         constraint_graph: &'s ConstraintGraph<D>,
 184         static_region: RegionVid,
 185     ) -> Self {
 186         Self { set, constraint_graph, static_region }
 187     }
 188
 189     /// Given a region `R`, iterate over all regions `R1` such that
 190     /// there exists a constraint `R: R1`.
 191     crate fn outgoing_regions(&self, region_sup: RegionVid) -> Successors<'_, D> {
 192         Successors {
 193             edges: self.constraint_graph.outgoing_edges(region_sup, self.set, self.static_region),
 194         }
 195     }
 196 }
 197
 198 crate struct Successors<'s, D: ConstraintGraphDirecton> {
 199     edges: Edges<'s, D>,
 200 }
 201
 202 impl<'s, D: ConstraintGraphDirecton> Iterator for Successors<'s, D> {
 203     type Item = RegionVid;
 204
 205     fn next(&mut self) -> Option<Self::Item> {
 206         self.edges.next().map(|c| D::end_region(&c))
 207     }
 208 }
 209
 210 impl<'s, D: ConstraintGraphDirecton> graph::DirectedGraph for RegionGraph<'s, D> {
 211     type Node = RegionVid;
 212 }
 213
 214 impl<'s, D: ConstraintGraphDirecton> graph::WithNumNodes for RegionGraph<'s, D> {
 215     fn num_nodes(&self) -> usize {
 216         self.constraint_graph.first_constraints.len()
 217     }
 218 }
 219
 220 impl<'s, D: ConstraintGraphDirecton> graph::WithSuccessors for RegionGraph<'s, D> {
 221     fn successors(&self, node: Self::Node) -> <Self as graph::GraphSuccessors<'_>>::Iter {
 222         self.outgoing_regions(node)
 223     }
 224 }
 225
 226 impl<'s, 'graph, D: ConstraintGraphDirecton> graph::GraphSuccessors<'graph> for RegionGraph<'s, D> {
 227     type Item = RegionVid;
 228     type Iter = Successors<'graph, D>;
 229 }