rustc_borrowck/constraints/
graph.rs

Help
1use rustc_data_structures::graph;
2use rustc_index::IndexVec;
3use rustc_middle::ty::RegionVid;
4
5use crate::constraints::{OutlivesConstraint, OutlivesConstraintIndex, OutlivesConstraintSet};
6
7/// The construct graph organizes the constraints by their end-points.
8/// It can be used to view a `R1: R2` constraint as either an edge `R1
9/// -> R2` or `R2 -> R1` depending on the direction type `D`.
10pub(crate) struct ConstraintGraph<D: ConstraintGraphDirection> {
11    _direction: D,
12    first_constraints: IndexVec<RegionVid, Option<OutlivesConstraintIndex>>,
13    next_constraints: IndexVec<OutlivesConstraintIndex, Option<OutlivesConstraintIndex>>,
14}
15
16pub(crate) type NormalConstraintGraph = ConstraintGraph<Normal>;
17
18pub(crate) type ReverseConstraintGraph = ConstraintGraph<Reverse>;
19
20/// Marker trait that controls whether a `R1: R2` constraint
21/// represents an edge `R1 -> R2` or `R2 -> R1`.
22pub(crate) trait ConstraintGraphDirection: Copy + 'static {
23    fn start_region(sup: RegionVid, sub: RegionVid) -> RegionVid;
24    fn end_region(sup: RegionVid, sub: RegionVid) -> RegionVid;
25    fn is_normal() -> bool;
26}
27
28/// In normal mode, a `R1: R2` constraint results in an edge `R1 ->
29/// R2`. This is what we use when constructing the SCCs for
30/// inference. This is because we compute the value of R1 by union'ing
31/// all the things that it relies on.
32#[derive(Copy, Clone, Debug)]
33pub(crate) struct Normal;
34
35impl ConstraintGraphDirection for Normal {
36    fn start_region(sup: RegionVid, _sub: RegionVid) -> RegionVid {
37        sup
38    }
39
40    fn end_region(_sup: RegionVid, sub: RegionVid) -> RegionVid {
41        sub
42    }
43
44    fn is_normal() -> bool {
45        true
46    }
47}
48
49/// In reverse mode, a `R1: R2` constraint results in an edge `R2 ->
50/// R1`. We use this for optimizing liveness computation, because then
51/// we wish to iterate from a region (e.g., R2) to all the regions
52/// that will outlive it (e.g., R1).
53#[derive(Copy, Clone, Debug)]
54pub(crate) struct Reverse;
55
56impl ConstraintGraphDirection for Reverse {
57    fn start_region(_sup: RegionVid, sub: RegionVid) -> RegionVid {
58        sub
59    }
60
61    fn end_region(sup: RegionVid, _sub: RegionVid) -> RegionVid {
62        sup
63    }
64
65    fn is_normal() -> bool {
66        false
67    }
68}
69
70impl<D: ConstraintGraphDirection> ConstraintGraph<D> {
71    /// Creates a "dependency graph" where each region constraint `R1:
72    /// R2` is treated as an edge `R1 -> R2`. We use this graph to
73    /// construct SCCs for region inference but also for error
74    /// reporting.
75    pub(crate) fn new(
76        direction: D,
77        set: &OutlivesConstraintSet<'_>,
78        num_region_vars: usize,
79    ) -> Self {
80        let mut first_constraints = IndexVec::from_elem_n(None, num_region_vars);
81        let mut next_constraints = IndexVec::from_elem(None, &set.outlives);
82
83        for (idx, constraint) in set.outlives.iter_enumerated().rev() {
84            let head = &mut first_constraints[D::start_region(constraint.sup, constraint.sub)];
85            let next = &mut next_constraints[idx];
86            debug_assert!(next.is_none());
87            *next = *head;
88            *head = Some(idx);
89        }
90
91        Self { _direction: direction, first_constraints, next_constraints }
92    }
93
94    /// Given the constraint set from which this graph was built
95    /// creates a region graph so that you can iterate over *regions*
96    /// and not constraints.
97    pub(crate) fn region_graph<'a, 'tcx>(
98        &'a self,
99        set: &'a OutlivesConstraintSet<'tcx>,
100        static_region: RegionVid,
101    ) -> RegionGraph<'a, 'tcx, D> {
102        RegionGraph::new(set, self, static_region)
103    }
104
105    pub(crate) fn is_normal(&self) -> bool {
106        D::is_normal()
107    }
108
109    /// Given a region `R`, iterate over all constraints `R: R1`.
110    pub(crate) fn outgoing_edges_from_graph<'a, 'tcx>(
111        &'a self,
112        region_sup: RegionVid,
113        constraints: &'a OutlivesConstraintSet<'tcx>,
114    ) -> EdgesFromGraph<'a, 'tcx, D> {
115        EdgesFromGraph { graph: self, constraints, pointer: self.first_constraints[region_sup] }
116    }
117
118    /// Returns all regions (#53178).
119    pub(crate) fn outgoing_edges_from_static(&self) -> EdgesFromStatic {
120        EdgesFromStatic { next_static_idx: 0, end_static_idx: self.first_constraints.len() }
121    }
122}
123
124pub(crate) struct EdgesFromGraph<'a, 'tcx, D: ConstraintGraphDirection> {
125    graph: &'a ConstraintGraph<D>,
126    constraints: &'a OutlivesConstraintSet<'tcx>,
127    pointer: Option<OutlivesConstraintIndex>,
128}
129
130impl<'a, 'tcx, D: ConstraintGraphDirection> Iterator for EdgesFromGraph<'a, 'tcx, D> {
131    type Item = &'a OutlivesConstraint<'tcx>;
132
133    fn next(&mut self) -> Option<Self::Item> {
134        if let Some(p) = self.pointer {
135            self.pointer = self.graph.next_constraints[p];
136            Some(&self.constraints[p])
137        } else {
138            None
139        }
140    }
141}
142
143pub(crate) struct EdgesFromStatic {
144    next_static_idx: usize,
145    end_static_idx: usize,
146}
147
148impl Iterator for EdgesFromStatic {
149    type Item = RegionVid;
150
151    fn next(&mut self) -> Option<Self::Item> {
152        if self.next_static_idx < self.end_static_idx {
153            let ret = RegionVid::from_usize(self.next_static_idx);
154            self.next_static_idx += 1;
155            Some(ret)
156        } else {
157            None
158        }
159    }
160}
161
162/// This struct brings together a constraint set and a (normal, not
163/// reverse) constraint graph. It implements the graph traits and is
164/// usd for doing the SCC computation.
165pub(crate) struct RegionGraph<'a, 'tcx, D: ConstraintGraphDirection> {
166    set: &'a OutlivesConstraintSet<'tcx>,
167    constraint_graph: &'a ConstraintGraph<D>,
168    static_region: RegionVid,
169}
170
171impl<'a, 'tcx, D: ConstraintGraphDirection> RegionGraph<'a, 'tcx, D> {
172    /// Creates a "dependency graph" where each region constraint `R1:
173    /// R2` is treated as an edge `R1 -> R2`. We use this graph to
174    /// construct SCCs for region inference but also for error
175    /// reporting.
176    pub(crate) fn new(
177        set: &'a OutlivesConstraintSet<'tcx>,
178        constraint_graph: &'a ConstraintGraph<D>,
179        static_region: RegionVid,
180    ) -> Self {
181        Self { set, constraint_graph, static_region }
182    }
183
184    /// Given a region `R`, iterate over all regions `R1` such that
185    /// there exists a constraint `R: R1`.
186    pub(crate) fn outgoing_regions(&self, region_sup: RegionVid) -> Successors<'a, 'tcx, D> {
187        // If this is the `'static` region and the graph's direction is normal,
188        // then setup the Edges iterator to return all regions (#53178).
189        if region_sup == self.static_region && D::is_normal() {
190            Successors::FromStatic(self.constraint_graph.outgoing_edges_from_static())
191        } else {
192            // Otherwise, just setup the iterator as normal.
193            Successors::FromGraph(
194                self.constraint_graph.outgoing_edges_from_graph(region_sup, self.set),
195            )
196        }
197    }
198}
199
200pub(crate) enum Successors<'a, 'tcx, D: ConstraintGraphDirection> {
201    FromStatic(EdgesFromStatic),
202    FromGraph(EdgesFromGraph<'a, 'tcx, D>),
203}
204
205impl<'a, 'tcx, D: ConstraintGraphDirection> Iterator for Successors<'a, 'tcx, D> {
206    type Item = RegionVid;
207
208    fn next(&mut self) -> Option<Self::Item> {
209        match self {
210            Successors::FromStatic(edges) => {
211                // No `D::end_region` call needed here: static successors are only possible when
212                // the direction is `Normal`, so we can directly use what would be the `sub` value.
213                edges.next()
214            }
215            Successors::FromGraph(edges) => {
216                edges.next().map(|constraint| D::end_region(constraint.sup, constraint.sub))
217            }
218        }
219    }
220}
221
222impl<'a, 'tcx, D: ConstraintGraphDirection> graph::DirectedGraph for RegionGraph<'a, 'tcx, D> {
223    type Node = RegionVid;
224
225    fn num_nodes(&self) -> usize {
226        self.constraint_graph.first_constraints.len()
227    }
228}
229
230impl<'a, 'tcx, D: ConstraintGraphDirection> graph::Successors for RegionGraph<'a, 'tcx, D> {
231    fn successors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> {
232        self.outgoing_regions(node)
233    }
234}
rustc_borrowck/constraints/graph.rs

rustc_borrowck/constraints/
graph.rs
