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