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 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, 'tcx>(
 100         &'rg self,
 101         set: &'rg OutlivesConstraintSet<'tcx>,
 102         static_region: RegionVid,
 103     ) -> RegionGraph<'rg, 'tcx, 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, 'tcx>(
 109         &'a self,
 110         region_sup: RegionVid,
 111         constraints: &'a OutlivesConstraintSet<'tcx>,
 112         static_region: RegionVid,
 113     ) -> Edges<'a, 'tcx, 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, 'tcx, D: ConstraintGraphDirecton> {
 133     graph: &'s ConstraintGraph<D>,
 134     constraints: &'s OutlivesConstraintSet<'tcx>,
 135     pointer: Option<OutlivesConstraintIndex>,
 136     next_static_idx: Option<usize>,
 137     static_region: RegionVid,
 138 }
 139
 140 impl<'s, 'tcx, D: ConstraintGraphDirecton> Iterator for Edges<'s, 'tcx, D> {
 141     type Item = OutlivesConstraint<'tcx>;
 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].clone())
 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                 span: DUMMY_SP,
 160                 category: ConstraintCategory::Internal,
 161                 variance_info: VarianceDiagInfo::default(),
 162             })
 163         } else {
 164             None
 165         }
 166     }
 167 }
 168
 169 /// This struct brings together a constraint set and a (normal, not
 170 /// reverse) constraint graph. It implements the graph traits and is
 171 /// usd for doing the SCC computation.
 172 crate struct RegionGraph<'s, 'tcx, D: ConstraintGraphDirecton> {
 173     set: &'s OutlivesConstraintSet<'tcx>,
 174     constraint_graph: &'s ConstraintGraph<D>,
 175     static_region: RegionVid,
 176 }
 177
 178 impl<'s, 'tcx, D: ConstraintGraphDirecton> RegionGraph<'s, 'tcx, D> {
 179     /// Creates a "dependency graph" where each region constraint `R1:
 180     /// R2` is treated as an edge `R1 -> R2`. We use this graph to
 181     /// construct SCCs for region inference but also for error
 182     /// reporting.
 183     crate fn new(
 184         set: &'s OutlivesConstraintSet<'tcx>,
 185         constraint_graph: &'s ConstraintGraph<D>,
 186         static_region: RegionVid,
 187     ) -> Self {
 188         Self { set, constraint_graph, static_region }
 189     }
 190
 191     /// Given a region `R`, iterate over all regions `R1` such that
 192     /// there exists a constraint `R: R1`.
 193     crate fn outgoing_regions(&self, region_sup: RegionVid) -> Successors<'s, 'tcx, D> {
 194         Successors {
 195             edges: self.constraint_graph.outgoing_edges(region_sup, self.set, self.static_region),
 196         }
 197     }
 198 }
 199
 200 crate struct Successors<'s, 'tcx, D: ConstraintGraphDirecton> {
 201     edges: Edges<'s, 'tcx, D>,
 202 }
 203
 204 impl<'s, 'tcx, D: ConstraintGraphDirecton> Iterator for Successors<'s, 'tcx, D> {
 205     type Item = RegionVid;
 206
 207     fn next(&mut self) -> Option<Self::Item> {
 208         self.edges.next().map(|c| D::end_region(&c))
 209     }
 210 }
 211
 212 impl<'s, 'tcx, D: ConstraintGraphDirecton> graph::DirectedGraph for RegionGraph<'s, 'tcx, D> {
 213     type Node = RegionVid;
 214 }
 215
 216 impl<'s, 'tcx, D: ConstraintGraphDirecton> graph::WithNumNodes for RegionGraph<'s, 'tcx, D> {
 217     fn num_nodes(&self) -> usize {
 218         self.constraint_graph.first_constraints.len()
 219     }
 220 }
 221
 222 impl<'s, 'tcx, D: ConstraintGraphDirecton> graph::WithSuccessors for RegionGraph<'s, 'tcx, D> {
 223     fn successors(&self, node: Self::Node) -> <Self as graph::GraphSuccessors<'_>>::Iter {
 224         self.outgoing_regions(node)
 225     }
 226 }
 227
 228 impl<'s, 'tcx, D: ConstraintGraphDirecton> graph::GraphSuccessors<'_> for RegionGraph<'s, 'tcx, D> {
 229     type Item = RegionVid;
 230     type Iter = Successors<'s, 'tcx, D>;
 231 }