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])
 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                 from_closure: false,
 167             })
 168         } else {
 169             None
 170         }
 171     }
 172 }
 173
 174 /// This struct brings together a constraint set and a (normal, not
 175 /// reverse) constraint graph. It implements the graph traits and is
 176 /// usd for doing the SCC computation.
 177 pub(crate) struct RegionGraph<'s, 'tcx, D: ConstraintGraphDirecton> {
 178     set: &'s OutlivesConstraintSet<'tcx>,
 179     constraint_graph: &'s ConstraintGraph<D>,
 180     static_region: RegionVid,
 181 }
 182
 183 impl<'s, 'tcx, D: ConstraintGraphDirecton> RegionGraph<'s, 'tcx, D> {
 184     /// Creates a "dependency graph" where each region constraint `R1:
 185     /// R2` is treated as an edge `R1 -> R2`. We use this graph to
 186     /// construct SCCs for region inference but also for error
 187     /// reporting.
 188     pub(crate) fn new(
 189         set: &'s OutlivesConstraintSet<'tcx>,
 190         constraint_graph: &'s ConstraintGraph<D>,
 191         static_region: RegionVid,
 192     ) -> Self {
 193         Self { set, constraint_graph, static_region }
 194     }
 195
 196     /// Given a region `R`, iterate over all regions `R1` such that
 197     /// there exists a constraint `R: R1`.
 198     pub(crate) fn outgoing_regions(&self, region_sup: RegionVid) -> Successors<'s, 'tcx, D> {
 199         Successors {
 200             edges: self.constraint_graph.outgoing_edges(region_sup, self.set, self.static_region),
 201         }
 202     }
 203 }
 204
 205 pub(crate) struct Successors<'s, 'tcx, D: ConstraintGraphDirecton> {
 206     edges: Edges<'s, 'tcx, D>,
 207 }
 208
 209 impl<'s, 'tcx, D: ConstraintGraphDirecton> Iterator for Successors<'s, 'tcx, D> {
 210     type Item = RegionVid;
 211
 212     fn next(&mut self) -> Option<Self::Item> {
 213         self.edges.next().map(|c| D::end_region(&c))
 214     }
 215 }
 216
 217 impl<'s, 'tcx, D: ConstraintGraphDirecton> graph::DirectedGraph for RegionGraph<'s, 'tcx, D> {
 218     type Node = RegionVid;
 219 }
 220
 221 impl<'s, 'tcx, D: ConstraintGraphDirecton> graph::WithNumNodes for RegionGraph<'s, 'tcx, D> {
 222     fn num_nodes(&self) -> usize {
 223         self.constraint_graph.first_constraints.len()
 224     }
 225 }
 226
 227 impl<'s, 'tcx, D: ConstraintGraphDirecton> graph::WithSuccessors for RegionGraph<'s, 'tcx, D> {
 228     fn successors(&self, node: Self::Node) -> <Self as graph::GraphSuccessors<'_>>::Iter {
 229         self.outgoing_regions(node)
 230     }
 231 }
 232
 233 impl<'s, 'tcx, D: ConstraintGraphDirecton> graph::GraphSuccessors<'_> for RegionGraph<'s, 'tcx, D> {
 234     type Item = RegionVid;
 235     type Iter = Successors<'s, 'tcx, D>;
 236 }