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