1 use rustc::mir::ConstraintCategory;
2 use rustc::ty::RegionVid;
3 use rustc_data_structures::graph;
4 use rustc_index::vec::IndexVec;
5 use rustc_span::DUMMY_SP;
7 use crate::borrow_check::{
8 constraints::OutlivesConstraintIndex,
9 constraints::{OutlivesConstraint, OutlivesConstraintSet},
10 type_check::Locations,
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> {
18 first_constraints: IndexVec<RegionVid, Option<OutlivesConstraintIndex>>,
19 next_constraints: IndexVec<OutlivesConstraintIndex, Option<OutlivesConstraintIndex>>,
22 crate type NormalConstraintGraph = ConstraintGraph<Normal>;
24 crate type ReverseConstraintGraph = ConstraintGraph<Reverse>;
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;
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)]
41 impl ConstraintGraphDirecton for Normal {
42 fn start_region(c: &OutlivesConstraint) -> RegionVid {
46 fn end_region(c: &OutlivesConstraint) -> RegionVid {
50 fn is_normal() -> bool {
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)]
62 impl ConstraintGraphDirecton for Reverse {
63 fn start_region(c: &OutlivesConstraint) -> RegionVid {
67 fn end_region(c: &OutlivesConstraint) -> RegionVid {
71 fn is_normal() -> bool {
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
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);
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());
93 Self { _direction: direction, first_constraints, next_constraints }
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>(
101 set: &'rg OutlivesConstraintSet,
102 static_region: RegionVid,
103 ) -> RegionGraph<'rg, D> {
104 RegionGraph::new(set, self, static_region)
107 /// Given a region `R`, iterate over all constraints `R: R1`.
108 crate fn outgoing_edges<'a>(
110 region_sup: RegionVid,
111 constraints: &'a OutlivesConstraintSet,
112 static_region: RegionVid,
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() {
121 next_static_idx: Some(0),
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 }
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,
140 impl<'s, D: ConstraintGraphDirecton> Iterator for Edges<'s, D> {
141 type Item = OutlivesConstraint;
143 fn next(&mut self) -> Option<Self::Item> {
144 if let Some(p) = self.pointer {
145 self.pointer = self.graph.next_constraints[p];
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) {
152 Some(next_static_idx + 1)
155 Some(OutlivesConstraint {
156 sup: self.static_region,
157 sub: next_static_idx.into(),
158 locations: Locations::All(DUMMY_SP),
159 category: ConstraintCategory::Internal,
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,
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
182 set: &'s OutlivesConstraintSet,
183 constraint_graph: &'s ConstraintGraph<D>,
184 static_region: RegionVid,
186 Self { set, constraint_graph, static_region }
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> {
193 edges: self.constraint_graph.outgoing_edges(region_sup, self.set, self.static_region),
198 crate struct Successors<'s, D: ConstraintGraphDirecton> {
202 impl<'s, D: ConstraintGraphDirecton> Iterator for Successors<'s, D> {
203 type Item = RegionVid;
205 fn next(&mut self) -> Option<Self::Item> {
206 self.edges.next().map(|c| D::end_region(&c))
210 impl<'s, D: ConstraintGraphDirecton> graph::DirectedGraph for RegionGraph<'s, D> {
211 type Node = RegionVid;
214 impl<'s, D: ConstraintGraphDirecton> graph::WithNumNodes for RegionGraph<'s, D> {
215 fn num_nodes(&self) -> usize {
216 self.constraint_graph.first_constraints.len()
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)
226 impl<'s, 'graph, D: ConstraintGraphDirecton> graph::GraphSuccessors<'graph> for RegionGraph<'s, D> {
227 type Item = RegionVid;
228 type Iter = Successors<'graph, D>;