]>
git.proxmox.com Git - rustc.git/blob - src/librustc_mir/borrow_check/constraints/mod.rs
1 use rustc_data_structures
::graph
::scc
::Sccs
;
2 use rustc_index
::vec
::IndexVec
;
3 use rustc_middle
::mir
::ConstraintCategory
;
4 use rustc_middle
::ty
::RegionVid
;
8 use crate::borrow_check
::type_check
::Locations
;
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.
16 #[derive(Clone, Default)]
17 crate struct OutlivesConstraintSet
{
18 outlives
: IndexVec
<OutlivesConstraintIndex
, OutlivesConstraint
>,
21 impl OutlivesConstraintSet
{
22 crate fn push(&mut self, constraint
: OutlivesConstraint
) {
24 "OutlivesConstraintSet::push({:?}: {:?} @ {:?}",
25 constraint
.sup
, constraint
.sub
, constraint
.locations
27 if constraint
.sup
== constraint
.sub
{
28 // 'a: 'a is pretty uninteresting
31 self.outlives
.push(constraint
);
34 /// Constructs a "normal" graph from the constraint set; the graph makes it
35 /// easy to find the constraints affecting a particular region.
37 /// N.B., this graph contains a "frozen" view of the current
38 /// constraints. Any new constraints added to the `OutlivesConstraintSet`
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
)
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
)
50 /// Computes cycles (SCCs) in the graph of regions. In particular,
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(
55 constraint_graph
: &graph
::NormalConstraintGraph
,
56 static_region
: RegionVid
,
57 ) -> Sccs
<RegionVid
, ConstraintSccIndex
> {
58 let region_graph
= &constraint_graph
.region_graph(self, static_region
);
59 Sccs
::new(region_graph
)
62 crate fn outlives(&self) -> &IndexVec
<OutlivesConstraintIndex
, OutlivesConstraint
> {
67 impl Index
<OutlivesConstraintIndex
> for OutlivesConstraintSet
{
68 type Output
= OutlivesConstraint
;
70 fn index(&self, i
: OutlivesConstraintIndex
) -> &Self::Output
{
75 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
76 pub struct OutlivesConstraint
{
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...
84 /// Region that must be outlived.
87 /// Where did this constraint arise?
88 pub locations
: Locations
,
90 /// What caused this constraint?
91 pub category
: ConstraintCategory
,
94 impl fmt
::Debug
for OutlivesConstraint
{
95 fn fmt(&self, formatter
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
96 write
!(formatter
, "({:?}: {:?}) due to {:?}", self.sup
, self.sub
, self.locations
)
100 rustc_index
::newtype_index
! {
101 pub struct OutlivesConstraintIndex
{
102 DEBUG_FORMAT
= "OutlivesConstraintIndex({})"
106 rustc_index
::newtype_index
! {
107 pub struct ConstraintSccIndex
{
108 DEBUG_FORMAT
= "ConstraintSccIndex({})"