1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220
use std::fmt;
use std::ops::Index;
use rustc_index::{IndexSlice, IndexVec};
use rustc_middle::mir::ConstraintCategory;
use rustc_middle::ty::{RegionVid, TyCtxt, VarianceDiagInfo};
use rustc_span::Span;
use tracing::{debug, instrument};
use crate::region_infer::{ConstraintSccs, RegionDefinition, RegionTracker};
use crate::type_check::Locations;
use crate::universal_regions::UniversalRegions;
pub(crate) mod graph;
/// A set of NLL region constraints. These include "outlives"
/// constraints of the form `R1: R2`. Each constraint is identified by
/// a unique `OutlivesConstraintIndex` and you can index into the set
/// (`constraint_set[i]`) to access the constraint details.
#[derive(Clone, Debug, Default)]
pub(crate) struct OutlivesConstraintSet<'tcx> {
outlives: IndexVec<OutlivesConstraintIndex, OutlivesConstraint<'tcx>>,
}
impl<'tcx> OutlivesConstraintSet<'tcx> {
pub(crate) fn push(&mut self, constraint: OutlivesConstraint<'tcx>) {
debug!("OutlivesConstraintSet::push({:?})", constraint);
if constraint.sup == constraint.sub {
// 'a: 'a is pretty uninteresting
return;
}
self.outlives.push(constraint);
}
/// Constructs a "normal" graph from the constraint set; the graph makes it
/// easy to find the constraints affecting a particular region.
///
/// N.B., this graph contains a "frozen" view of the current
/// constraints. Any new constraints added to the `OutlivesConstraintSet`
/// after the graph is built will not be present in the graph.
pub(crate) fn graph(&self, num_region_vars: usize) -> graph::NormalConstraintGraph {
graph::ConstraintGraph::new(graph::Normal, self, num_region_vars)
}
/// Like `graph`, but constraints a reverse graph where `R1: R2`
/// represents an edge `R2 -> R1`.
pub(crate) fn reverse_graph(&self, num_region_vars: usize) -> graph::ReverseConstraintGraph {
graph::ConstraintGraph::new(graph::Reverse, self, num_region_vars)
}
pub(crate) fn outlives(
&self,
) -> &IndexSlice<OutlivesConstraintIndex, OutlivesConstraint<'tcx>> {
&self.outlives
}
/// Computes cycles (SCCs) in the graph of regions. In particular,
/// find all regions R1, R2 such that R1: R2 and R2: R1 and group
/// them into an SCC, and find the relationships between SCCs.
pub(crate) fn compute_sccs(
&self,
static_region: RegionVid,
definitions: &IndexVec<RegionVid, RegionDefinition<'tcx>>,
) -> ConstraintSccs {
let constraint_graph = self.graph(definitions.len());
let region_graph = &constraint_graph.region_graph(self, static_region);
ConstraintSccs::new_with_annotation(®ion_graph, |r| {
RegionTracker::new(r, &definitions[r])
})
}
/// This method handles Universe errors by rewriting the constraint
/// graph. For each strongly connected component in the constraint
/// graph such that there is a series of constraints
/// A: B: C: ... : X where
/// A's universe is smaller than X's and A is a placeholder,
/// add a constraint that A: 'static. This is a safe upper bound
/// in the face of borrow checker/trait solver limitations that will
/// eventually go away.
///
/// For a more precise definition, see the documentation for
/// [`RegionTracker::has_incompatible_universes()`].
///
/// This edge case used to be handled during constraint propagation
/// by iterating over the strongly connected components in the constraint
/// graph while maintaining a set of bookkeeping mappings similar
/// to what is stored in `RegionTracker` and manually adding 'sttaic as
/// needed.
///
/// It was rewritten as part of the Polonius project with the goal of moving
/// higher-kindedness concerns out of the path of the borrow checker,
/// for two reasons:
///
/// 1. Implementing Polonius is difficult enough without also
/// handling them.
/// 2. The long-term goal is to handle higher-kinded concerns
/// in the trait solver, where they belong. This avoids
/// logic duplication and allows future trait solvers
/// to compute better bounds than for example our
/// "must outlive 'static" here.
///
/// This code is a stop-gap measure in preparation for the future trait solver.
///
/// Every constraint added by this method is an
/// internal `IllegalUniverse` constraint.
#[instrument(skip(self, universal_regions, definitions))]
pub(crate) fn add_outlives_static(
&mut self,
universal_regions: &UniversalRegions<'tcx>,
definitions: &IndexVec<RegionVid, RegionDefinition<'tcx>>,
) -> ConstraintSccs {
let fr_static = universal_regions.fr_static;
let sccs = self.compute_sccs(fr_static, definitions);
// Changed to `true` if we added any constraints to `self` and need to
// recompute SCCs.
let mut added_constraints = false;
for scc in sccs.all_sccs() {
// No point in adding 'static: 'static!
// This micro-optimisation makes somewhat sense
// because static outlives *everything*.
if scc == sccs.scc(fr_static) {
continue;
}
let annotation = sccs.annotation(scc);
// If this SCC participates in a universe violation,
// e.g. if it reaches a region with a universe smaller than
// the largest region reached, add a requirement that it must
// outlive `'static`.
if annotation.has_incompatible_universes() {
// Optimisation opportunity: this will add more constraints than
// needed for correctness, since an SCC upstream of another with
// a universe violation will "infect" its downstream SCCs to also
// outlive static.
added_constraints = true;
let scc_representative_outlives_static = OutlivesConstraint {
sup: annotation.representative,
sub: fr_static,
category: ConstraintCategory::IllegalUniverse,
locations: Locations::All(rustc_span::DUMMY_SP),
span: rustc_span::DUMMY_SP,
variance_info: VarianceDiagInfo::None,
from_closure: false,
};
self.push(scc_representative_outlives_static);
}
}
if added_constraints {
// We changed the constraint set and so must recompute SCCs.
self.compute_sccs(fr_static, definitions)
} else {
// If we didn't add any back-edges; no more work needs doing
sccs
}
}
}
impl<'tcx> Index<OutlivesConstraintIndex> for OutlivesConstraintSet<'tcx> {
type Output = OutlivesConstraint<'tcx>;
fn index(&self, i: OutlivesConstraintIndex) -> &Self::Output {
&self.outlives[i]
}
}
#[derive(Copy, Clone, PartialEq, Eq)]
pub struct OutlivesConstraint<'tcx> {
// NB. The ordering here is not significant for correctness, but
// it is for convenience. Before we dump the constraints in the
// debugging logs, we sort them, and we'd like the "super region"
// to be first, etc. (In particular, span should remain last.)
/// The region SUP must outlive SUB...
pub sup: RegionVid,
/// Region that must be outlived.
pub sub: RegionVid,
/// Where did this constraint arise?
pub locations: Locations,
/// The `Span` associated with the creation of this constraint.
/// This should be used in preference to obtaining the span from
/// `locations`, since the `locations` may give a poor span
/// in some cases (e.g. converting a constraint from a promoted).
pub span: Span,
/// What caused this constraint?
pub category: ConstraintCategory<'tcx>,
/// Variance diagnostic information
pub variance_info: VarianceDiagInfo<TyCtxt<'tcx>>,
/// If this constraint is promoted from closure requirements.
pub from_closure: bool,
}
impl<'tcx> fmt::Debug for OutlivesConstraint<'tcx> {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(
formatter,
"({:?}: {:?}) due to {:?} ({:?}) ({:?})",
self.sup, self.sub, self.locations, self.variance_info, self.category,
)
}
}
rustc_index::newtype_index! {
#[debug_format = "OutlivesConstraintIndex({})"]
pub struct OutlivesConstraintIndex {}
}
rustc_index::newtype_index! {
#[orderable]
#[debug_format = "ConstraintSccIndex({})"]
pub struct ConstraintSccIndex {}
}