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;
7 use crate::borrow_check::{
9 constraints::OutlivesConstraintIndex,
10 constraints::{OutlivesConstraintSet, OutlivesConstraint},
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
83 set: &OutlivesConstraintSet,
84 num_region_vars: usize,
86 let mut first_constraints = IndexVec::from_elem_n(None, num_region_vars);
87 let mut next_constraints = IndexVec::from_elem(None, &set.outlives);
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());
98 _direction: direction,
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>(
109 set: &'rg OutlivesConstraintSet,
110 static_region: RegionVid,
111 ) -> RegionGraph<'rg, D> {
112 RegionGraph::new(set, self, static_region)
115 /// Given a region `R`, iterate over all constraints `R: R1`.
116 crate fn outgoing_edges<'a>(
118 region_sup: RegionVid,
119 constraints: &'a OutlivesConstraintSet,
120 static_region: RegionVid,
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() {
129 next_static_idx: Some(0),
133 //otherwise, just setup the iterator as normal
134 let first = self.first_constraints[region_sup];
139 next_static_idx: None,
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,
154 impl<'s, D: ConstraintGraphDirecton> Iterator for Edges<'s, D> {
155 type Item = OutlivesConstraint;
157 fn next(&mut self) -> Option<Self::Item> {
158 if let Some(p) = self.pointer {
159 self.pointer = self.graph.next_constraints[p];
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) {
167 Some(next_static_idx + 1)
170 Some(OutlivesConstraint {
171 sup: self.static_region,
172 sub: next_static_idx.into(),
173 locations: Locations::All(DUMMY_SP),
174 category: ConstraintCategory::Internal,
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,
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
197 set: &'s OutlivesConstraintSet,
198 constraint_graph: &'s ConstraintGraph<D>,
199 static_region: RegionVid,
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> {
212 edges: self.constraint_graph.outgoing_edges(region_sup, self.set, self.static_region),
217 crate struct Successors<'s, D: ConstraintGraphDirecton> {
221 impl<'s, D: ConstraintGraphDirecton> Iterator for Successors<'s, D> {
222 type Item = RegionVid;
224 fn next(&mut self) -> Option<Self::Item> {
225 self.edges.next().map(|c| D::end_region(&c))
229 impl<'s, D: ConstraintGraphDirecton> graph::DirectedGraph for RegionGraph<'s, D> {
230 type Node = RegionVid;
233 impl<'s, D: ConstraintGraphDirecton> graph::WithNumNodes for RegionGraph<'s, D> {
234 fn num_nodes(&self) -> usize {
235 self.constraint_graph.first_constraints.len()
239 impl<'s, D: ConstraintGraphDirecton> graph::WithSuccessors for RegionGraph<'s, D> {
243 ) -> <Self as graph::GraphSuccessors<'_>>::Iter {
244 self.outgoing_regions(node)
248 impl<'s, 'graph, D: ConstraintGraphDirecton> graph::GraphSuccessors<'graph> for RegionGraph<'s, D> {
249 type Item = RegionVid;
250 type Iter = Successors<'graph, D>;