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