src/librustc_mir/borrow_check/constraints/graph.rs

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