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};
9 use crate::type_check::Locations;
13 /// A set of NLL region constraints. These include "outlives"
14 /// constraints of the form `R1: R2`. Each constraint is identified by
15 /// a unique `OutlivesConstraintIndex` and you can index into the set
16 /// (`constraint_set[i]`) to access the constraint details.
17 #[derive(Clone, Default)]
18 pub(crate) struct OutlivesConstraintSet<'tcx> {
19 outlives: IndexVec<OutlivesConstraintIndex, OutlivesConstraint<'tcx>>,
22 impl<'tcx> OutlivesConstraintSet<'tcx> {
23 pub(crate) fn push(&mut self, constraint: OutlivesConstraint<'tcx>) {
24 debug!("OutlivesConstraintSet::push({:?})", constraint);
25 if constraint.sup == constraint.sub {
26 // 'a: 'a is pretty uninteresting
29 self.outlives.push(constraint);
32 /// Constructs a "normal" graph from the constraint set; the graph makes it
33 /// easy to find the constraints affecting a particular region.
35 /// N.B., this graph contains a "frozen" view of the current
36 /// constraints. Any new constraints added to the `OutlivesConstraintSet`
37 /// after the graph is built will not be present in the graph.
38 pub(crate) fn graph(&self, num_region_vars: usize) -> graph::NormalConstraintGraph {
39 graph::ConstraintGraph::new(graph::Normal, self, num_region_vars)
42 /// Like `graph`, but constraints a reverse graph where `R1: R2`
43 /// represents an edge `R2 -> R1`.
44 pub(crate) fn reverse_graph(&self, num_region_vars: usize) -> graph::ReverseConstraintGraph {
45 graph::ConstraintGraph::new(graph::Reverse, self, num_region_vars)
48 /// Computes cycles (SCCs) in the graph of regions. In particular,
49 /// find all regions R1, R2 such that R1: R2 and R2: R1 and group
50 /// them into an SCC, and find the relationships between SCCs.
51 pub(crate) fn compute_sccs(
53 constraint_graph: &graph::NormalConstraintGraph,
54 static_region: RegionVid,
55 ) -> Sccs<RegionVid, ConstraintSccIndex> {
56 let region_graph = &constraint_graph.region_graph(self, static_region);
57 Sccs::new(region_graph)
60 pub(crate) fn outlives(&self) -> &IndexVec<OutlivesConstraintIndex, OutlivesConstraint<'tcx>> {
65 impl<'tcx> Index<OutlivesConstraintIndex> for OutlivesConstraintSet<'tcx> {
66 type Output = OutlivesConstraint<'tcx>;
68 fn index(&self, i: OutlivesConstraintIndex) -> &Self::Output {
73 #[derive(Copy, Clone, PartialEq, Eq)]
74 pub struct OutlivesConstraint<'tcx> {
75 // NB. The ordering here is not significant for correctness, but
76 // it is for convenience. Before we dump the constraints in the
77 // debugging logs, we sort them, and we'd like the "super region"
78 // to be first, etc. (In particular, span should remain last.)
79 /// The region SUP must outlive SUB...
82 /// Region that must be outlived.
85 /// Where did this constraint arise?
86 pub locations: Locations,
88 /// The `Span` associated with the creation of this constraint.
89 /// This should be used in preference to obtaining the span from
90 /// `locations`, since the `locations` may give a poor span
91 /// in some cases (e.g. converting a constraint from a promoted).
94 /// What caused this constraint?
95 pub category: ConstraintCategory<'tcx>,
97 /// Variance diagnostic information
98 pub variance_info: VarianceDiagInfo<'tcx>,
100 /// If this constraint is promoted from closure requirements.
101 pub from_closure: bool,
104 impl<'tcx> fmt::Debug for OutlivesConstraint<'tcx> {
105 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
108 "({:?}: {:?}) due to {:?} ({:?}) ({:?})",
109 self.sup, self.sub, self.locations, self.variance_info, self.category,
114 rustc_index::newtype_index! {
115 pub struct OutlivesConstraintIndex {
116 DEBUG_FORMAT = "OutlivesConstraintIndex({})"
120 rustc_index::newtype_index! {
121 pub struct ConstraintSccIndex {
122 DEBUG_FORMAT = "ConstraintSccIndex({})"