]>
Commit | Line | Data |
---|---|---|
8faf50e0 | 1 | use rustc_data_structures::graph::scc::Sccs; |
dfeec247 | 2 | use rustc_index::vec::IndexVec; |
ba9703b0 | 3 | use rustc_middle::mir::ConstraintCategory; |
17df50a5 | 4 | use rustc_middle::ty::{RegionVid, VarianceDiagInfo}; |
8faf50e0 | 5 | use std::fmt; |
dc9dc135 | 6 | use std::ops::Index; |
8faf50e0 | 7 | |
60c5eb7d XL |
8 | use crate::borrow_check::type_check::Locations; |
9 | ||
8faf50e0 XL |
10 | crate mod graph; |
11 | ||
dc9dc135 XL |
12 | /// A set of NLL region constraints. These include "outlives" |
13 | /// constraints of the form `R1: R2`. Each constraint is identified by | |
14 | /// a unique `OutlivesConstraintIndex` and you can index into the set | |
15 | /// (`constraint_set[i]`) to access the constraint details. | |
8faf50e0 | 16 | #[derive(Clone, Default)] |
17df50a5 XL |
17 | crate struct OutlivesConstraintSet<'tcx> { |
18 | outlives: IndexVec<OutlivesConstraintIndex, OutlivesConstraint<'tcx>>, | |
8faf50e0 XL |
19 | } |
20 | ||
17df50a5 XL |
21 | impl<'tcx> OutlivesConstraintSet<'tcx> { |
22 | crate fn push(&mut self, constraint: OutlivesConstraint<'tcx>) { | |
8faf50e0 | 23 | debug!( |
dc9dc135 | 24 | "OutlivesConstraintSet::push({:?}: {:?} @ {:?}", |
8faf50e0 XL |
25 | constraint.sup, constraint.sub, constraint.locations |
26 | ); | |
27 | if constraint.sup == constraint.sub { | |
28 | // 'a: 'a is pretty uninteresting | |
29 | return; | |
30 | } | |
dc9dc135 | 31 | self.outlives.push(constraint); |
8faf50e0 XL |
32 | } |
33 | ||
b7449926 XL |
34 | /// Constructs a "normal" graph from the constraint set; the graph makes it |
35 | /// easy to find the constraints affecting a particular region. | |
36 | /// | |
0731742a | 37 | /// N.B., this graph contains a "frozen" view of the current |
dc9dc135 | 38 | /// constraints. Any new constraints added to the `OutlivesConstraintSet` |
b7449926 XL |
39 | /// after the graph is built will not be present in the graph. |
40 | crate fn graph(&self, num_region_vars: usize) -> graph::NormalConstraintGraph { | |
41 | graph::ConstraintGraph::new(graph::Normal, self, num_region_vars) | |
42 | } | |
43 | ||
44 | /// Like `graph`, but constraints a reverse graph where `R1: R2` | |
45 | /// represents an edge `R2 -> R1`. | |
46 | crate fn reverse_graph(&self, num_region_vars: usize) -> graph::ReverseConstraintGraph { | |
47 | graph::ConstraintGraph::new(graph::Reverse, self, num_region_vars) | |
8faf50e0 XL |
48 | } |
49 | ||
9fa01778 | 50 | /// Computes cycles (SCCs) in the graph of regions. In particular, |
8faf50e0 XL |
51 | /// find all regions R1, R2 such that R1: R2 and R2: R1 and group |
52 | /// them into an SCC, and find the relationships between SCCs. | |
53 | crate fn compute_sccs( | |
54 | &self, | |
b7449926 XL |
55 | constraint_graph: &graph::NormalConstraintGraph, |
56 | static_region: RegionVid, | |
8faf50e0 | 57 | ) -> Sccs<RegionVid, ConstraintSccIndex> { |
b7449926 | 58 | let region_graph = &constraint_graph.region_graph(self, static_region); |
8faf50e0 XL |
59 | Sccs::new(region_graph) |
60 | } | |
dc9dc135 | 61 | |
17df50a5 | 62 | crate fn outlives(&self) -> &IndexVec<OutlivesConstraintIndex, OutlivesConstraint<'tcx>> { |
dc9dc135 XL |
63 | &self.outlives |
64 | } | |
8faf50e0 XL |
65 | } |
66 | ||
17df50a5 XL |
67 | impl<'tcx> Index<OutlivesConstraintIndex> for OutlivesConstraintSet<'tcx> { |
68 | type Output = OutlivesConstraint<'tcx>; | |
8faf50e0 | 69 | |
dc9dc135 XL |
70 | fn index(&self, i: OutlivesConstraintIndex) -> &Self::Output { |
71 | &self.outlives[i] | |
8faf50e0 XL |
72 | } |
73 | } | |
74 | ||
17df50a5 XL |
75 | #[derive(Clone, PartialEq, Eq, PartialOrd, Ord)] |
76 | pub struct OutlivesConstraint<'tcx> { | |
8faf50e0 XL |
77 | // NB. The ordering here is not significant for correctness, but |
78 | // it is for convenience. Before we dump the constraints in the | |
79 | // debugging logs, we sort them, and we'd like the "super region" | |
80 | // to be first, etc. (In particular, span should remain last.) | |
81 | /// The region SUP must outlive SUB... | |
82 | pub sup: RegionVid, | |
83 | ||
84 | /// Region that must be outlived. | |
85 | pub sub: RegionVid, | |
86 | ||
87 | /// Where did this constraint arise? | |
88 | pub locations: Locations, | |
0bf4aa26 XL |
89 | |
90 | /// What caused this constraint? | |
91 | pub category: ConstraintCategory, | |
17df50a5 XL |
92 | |
93 | /// Variance diagnostic information | |
94 | pub variance_info: VarianceDiagInfo<'tcx>, | |
8faf50e0 XL |
95 | } |
96 | ||
17df50a5 | 97 | impl<'tcx> fmt::Debug for OutlivesConstraint<'tcx> { |
9fa01778 | 98 | fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result { |
17df50a5 XL |
99 | write!( |
100 | formatter, | |
101 | "({:?}: {:?}) due to {:?} ({:?})", | |
102 | self.sup, self.sub, self.locations, self.variance_info | |
103 | ) | |
8faf50e0 XL |
104 | } |
105 | } | |
106 | ||
e74abb32 | 107 | rustc_index::newtype_index! { |
dc9dc135 XL |
108 | pub struct OutlivesConstraintIndex { |
109 | DEBUG_FORMAT = "OutlivesConstraintIndex({})" | |
b7449926 XL |
110 | } |
111 | } | |
8faf50e0 | 112 | |
e74abb32 | 113 | rustc_index::newtype_index! { |
b7449926 XL |
114 | pub struct ConstraintSccIndex { |
115 | DEBUG_FORMAT = "ConstraintSccIndex({})" | |
116 | } | |
117 | } |