compiler/rustc_borrowck/src/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, VarianceDiagInfo};
   5 use rustc_span::DUMMY_SP;
   6
   7 use crate::{
   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 pub(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 pub(crate) type NormalConstraintGraph = ConstraintGraph<Normal>;
  23
  24 pub(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 pub(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 pub(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 pub(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     pub(crate) fn new(
  82         direction: D,
  83         set: &OutlivesConstraintSet<'_>,
  84         num_region_vars: usize,
  85     ) -> Self {
  86         let mut first_constraints = IndexVec::from_elem_n(None, num_region_vars);
  87         let mut next_constraints = IndexVec::from_elem(None, &set.outlives);
  88
  89         for (idx, constraint) in set.outlives.iter_enumerated().rev() {
  90             let head = &mut first_constraints[D::start_region(constraint)];
  91             let next = &mut next_constraints[idx];
  92             debug_assert!(next.is_none());
  93             *next = *head;
  94             *head = Some(idx);
  95         }
  96
  97         Self { _direction: direction, first_constraints, next_constraints }
  98     }
  99
 100     /// Given the constraint set from which this graph was built
 101     /// creates a region graph so that you can iterate over *regions*
 102     /// and not constraints.
 103     pub(crate) fn region_graph<'rg, 'tcx>(
 104         &'rg self,
 105         set: &'rg OutlivesConstraintSet<'tcx>,
 106         static_region: RegionVid,
 107     ) -> RegionGraph<'rg, 'tcx, D> {
 108         RegionGraph::new(set, self, static_region)
 109     }
 110
 111     /// Given a region `R`, iterate over all constraints `R: R1`.
 112     pub(crate) fn outgoing_edges<'a, 'tcx>(
 113         &'a self,
 114         region_sup: RegionVid,
 115         constraints: &'a OutlivesConstraintSet<'tcx>,
 116         static_region: RegionVid,
 117     ) -> Edges<'a, 'tcx, D> {
 118         //if this is the `'static` region and the graph's direction is normal,
 119         //then setup the Edges iterator to return all regions #53178
 120         if region_sup == static_region && D::is_normal() {
 121             Edges {
 122                 graph: self,
 123                 constraints,
 124                 pointer: None,
 125                 next_static_idx: Some(0),
 126                 static_region,
 127             }
 128         } else {
 129             //otherwise, just setup the iterator as normal
 130             let first = self.first_constraints[region_sup];
 131             Edges { graph: self, constraints, pointer: first, next_static_idx: None, static_region }
 132         }
 133     }
 134 }
 135
 136 pub(crate) struct Edges<'s, 'tcx, D: ConstraintGraphDirecton> {
 137     graph: &'s ConstraintGraph<D>,
 138     constraints: &'s OutlivesConstraintSet<'tcx>,
 139     pointer: Option<OutlivesConstraintIndex>,
 140     next_static_idx: Option<usize>,
 141     static_region: RegionVid,
 142 }
 143
 144 impl<'s, 'tcx, D: ConstraintGraphDirecton> Iterator for Edges<'s, 'tcx, D> {
 145     type Item = OutlivesConstraint<'tcx>;
 146
 147     fn next(&mut self) -> Option<Self::Item> {
 148         if let Some(p) = self.pointer {
 149             self.pointer = self.graph.next_constraints[p];
 150
 151             Some(self.constraints[p].clone())
 152         } else if let Some(next_static_idx) = self.next_static_idx {
 153             self.next_static_idx = if next_static_idx == (self.graph.first_constraints.len() - 1) {
 154                 None
 155             } else {
 156                 Some(next_static_idx + 1)
 157             };
 158
 159             Some(OutlivesConstraint {
 160                 sup: self.static_region,
 161                 sub: next_static_idx.into(),
 162                 locations: Locations::All(DUMMY_SP),
 163                 span: DUMMY_SP,
 164                 category: ConstraintCategory::Internal,
 165                 variance_info: VarianceDiagInfo::default(),
 166             })
 167         } else {
 168             None
 169         }
 170     }
 171 }
 172
 173 /// This struct brings together a constraint set and a (normal, not
 174 /// reverse) constraint graph. It implements the graph traits and is
 175 /// usd for doing the SCC computation.
 176 pub(crate) struct RegionGraph<'s, 'tcx, D: ConstraintGraphDirecton> {
 177     set: &'s OutlivesConstraintSet<'tcx>,
 178     constraint_graph: &'s ConstraintGraph<D>,
 179     static_region: RegionVid,
 180 }
 181
 182 impl<'s, 'tcx, D: ConstraintGraphDirecton> RegionGraph<'s, 'tcx, D> {
 183     /// Creates a "dependency graph" where each region constraint `R1:
 184     /// R2` is treated as an edge `R1 -> R2`. We use this graph to
 185     /// construct SCCs for region inference but also for error
 186     /// reporting.
 187     pub(crate) fn new(
 188         set: &'s OutlivesConstraintSet<'tcx>,
 189         constraint_graph: &'s ConstraintGraph<D>,
 190         static_region: RegionVid,
 191     ) -> Self {
 192         Self { set, constraint_graph, static_region }
 193     }
 194
 195     /// Given a region `R`, iterate over all regions `R1` such that
 196     /// there exists a constraint `R: R1`.
 197     pub(crate) fn outgoing_regions(&self, region_sup: RegionVid) -> Successors<'s, 'tcx, D> {
 198         Successors {
 199             edges: self.constraint_graph.outgoing_edges(region_sup, self.set, self.static_region),
 200         }
 201     }
 202 }
 203
 204 pub(crate) struct Successors<'s, 'tcx, D: ConstraintGraphDirecton> {
 205     edges: Edges<'s, 'tcx, D>,
 206 }
 207
 208 impl<'s, 'tcx, D: ConstraintGraphDirecton> Iterator for Successors<'s, 'tcx, D> {
 209     type Item = RegionVid;
 210
 211     fn next(&mut self) -> Option<Self::Item> {
 212         self.edges.next().map(|c| D::end_region(&c))
 213     }
 214 }
 215
 216 impl<'s, 'tcx, D: ConstraintGraphDirecton> graph::DirectedGraph for RegionGraph<'s, 'tcx, D> {
 217     type Node = RegionVid;
 218 }
 219
 220 impl<'s, 'tcx, D: ConstraintGraphDirecton> graph::WithNumNodes for RegionGraph<'s, 'tcx, D> {
 221     fn num_nodes(&self) -> usize {
 222         self.constraint_graph.first_constraints.len()
 223     }
 224 }
 225
 226 impl<'s, 'tcx, D: ConstraintGraphDirecton> graph::WithSuccessors for RegionGraph<'s, 'tcx, D> {
 227     fn successors(&self, node: Self::Node) -> <Self as graph::GraphSuccessors<'_>>::Iter {
 228         self.outgoing_regions(node)
 229     }
 230 }
 231
 232 impl<'s, 'tcx, D: ConstraintGraphDirecton> graph::GraphSuccessors<'_> for RegionGraph<'s, 'tcx, D> {
 233     type Item = RegionVid;
 234     type Iter = Successors<'s, 'tcx, D>;
 235 }