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