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, VarianceDiagInfo};
5 use std::fmt;
6 use std::ops::Index;
7 
8 use crate::type_check::Locations;
9 
10 crate mod graph;
11 
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<'tcx> {
18     outlives: IndexVec<OutlivesConstraintIndex, OutlivesConstraint<'tcx>>,
19 }
20 
21 impl<'tcx> OutlivesConstraintSet<'tcx> {
push(&mut self, constraint: OutlivesConstraint<'tcx>)22     crate fn push(&mut self, constraint: OutlivesConstraint<'tcx>) {
23         debug!(
24             "OutlivesConstraintSet::push({:?}: {:?} @ {:?}",
25             constraint.sup, constraint.sub, constraint.locations
26         );
27         if constraint.sup == constraint.sub {
28             // 'a: 'a is pretty uninteresting
29             return;
30         }
31         self.outlives.push(constraint);
32     }
33 
34     /// Constructs a "normal" graph from the constraint set; the graph makes it
35     /// easy to find the constraints affecting a particular region.
36     ///
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.
graph(&self, num_region_vars: usize) -> graph::NormalConstraintGraph40     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`.
reverse_graph(&self, num_region_vars: usize) -> graph::ReverseConstraintGraph46     crate fn reverse_graph(&self, num_region_vars: usize) -> graph::ReverseConstraintGraph {
47         graph::ConstraintGraph::new(graph::Reverse, self, num_region_vars)
48     }
49 
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.
compute_sccs( &self, constraint_graph: &graph::NormalConstraintGraph, static_region: RegionVid, ) -> Sccs<RegionVid, ConstraintSccIndex>53     crate fn compute_sccs(
54         &self,
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)
60     }
61 
outlives(&self) -> &IndexVec<OutlivesConstraintIndex, OutlivesConstraint<'tcx>>62     crate fn outlives(&self) -> &IndexVec<OutlivesConstraintIndex, OutlivesConstraint<'tcx>> {
63         &self.outlives
64     }
65 }
66 
67 impl<'tcx> Index<OutlivesConstraintIndex> for OutlivesConstraintSet<'tcx> {
68     type Output = OutlivesConstraint<'tcx>;
69 
index(&self, i: OutlivesConstraintIndex) -> &Self::Output70     fn index(&self, i: OutlivesConstraintIndex) -> &Self::Output {
71         &self.outlives[i]
72     }
73 }
74 
75 #[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
76 pub struct OutlivesConstraint<'tcx> {
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,
89 
90     /// What caused this constraint?
91     pub category: ConstraintCategory,
92 
93     /// Variance diagnostic information
94     pub variance_info: VarianceDiagInfo<'tcx>,
95 }
96 
97 impl<'tcx> fmt::Debug for OutlivesConstraint<'tcx> {
fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result98     fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
99         write!(
100             formatter,
101             "({:?}: {:?}) due to {:?} ({:?})",
102             self.sup, self.sub, self.locations, self.variance_info
103         )
104     }
105 }
106 
107 rustc_index::newtype_index! {
108     pub struct OutlivesConstraintIndex {
109         DEBUG_FORMAT = "OutlivesConstraintIndex({})"
110     }
111 }
112 
113 rustc_index::newtype_index! {
114     pub struct ConstraintSccIndex {
115         DEBUG_FORMAT = "ConstraintSccIndex({})"
116     }
117 }
118