2 use crate::infer::CombinedSnapshot;
3 use rustc_data_structures::{
4 graph::{scc::Sccs, vec_graph::VecGraph},
7 use rustc_index::vec::Idx;
8 use rustc_middle::ty::error::TypeError;
9 use rustc_middle::ty::relate::RelateResult;
11 impl<'tcx> RegionConstraintCollector<'_, 'tcx> {
12 /// Searches new universes created during `snapshot`, looking for
13 /// placeholders that may "leak" out from the universes they are contained
14 /// in. If any leaking placeholders are found, then an `Err` is returned
15 /// (typically leading to the snapshot being reversed).
17 /// The leak check *used* to be the only way we had to handle higher-ranked
18 /// obligations. Now that we have integrated universes into the region
19 /// solvers, this is no longer the case, but we retain the leak check for
20 /// backwards compatibility purposes. In particular, it lets us make "early"
21 /// decisions about whether a region error will be reported that are used in
22 /// coherence and elsewhere -- see #56105 and #59490 for more details. The
23 /// eventual fate of the leak checker is not yet settled.
25 /// The leak checker works by searching for the following error patterns:
27 /// * P1: P2, where P1 != P2
28 /// * P1: R, where R is in some universe that cannot name P1
30 /// The idea here is that each of these patterns represents something that
31 /// the region solver would eventually report as an error, so we can detect
32 /// the error early. There is a fly in the ointment, though, in that this is
33 /// not entirely true. In particular, in the future, we may extend the
34 /// environment with implied bounds or other info about how placeholders
35 /// relate to regions in outer universes. In that case, `P1: R` for example
36 /// might become solveable.
38 /// # Summary of the implementation
40 /// The leak checks as follows. First, we construct a graph where `R2: R1`
41 /// implies `R2 -> R1`, and we compute the SCCs.
43 /// For each SCC S, we compute:
45 /// * what placeholder P it must be equal to, if any
46 /// * if there are multiple placeholders that must be equal, report an error because `P1: P2`
47 /// * the minimum universe of its constituents
49 /// Then we walk the SCCs in dependency order and compute
51 /// * what placeholder they must outlive transitively
52 /// * if they must also be equal to a placeholder, report an error because `P1: P2`
53 /// * minimum universe U of all SCCs they must outlive
54 /// * if they must also be equal to a placeholder P, and U cannot name P, report an error, as that
55 /// indicates `P: R` and `R` is in an incompatible universe
59 /// Older variants of the leak check used to report errors for these
60 /// patterns, but we no longer do:
62 /// * R: P1, even if R cannot name P1, because R = 'static is a valid sol'n
63 /// * R: P1, R: P2, as above
67 overly_polymorphic: bool,
68 max_universe: ty::UniverseIndex,
69 snapshot: &CombinedSnapshot<'_, 'tcx>,
70 ) -> RelateResult<'tcx, ()> {
72 "leak_check(max_universe={:?}, snapshot.universe={:?}, overly_polymorphic={:?})",
73 max_universe, snapshot.universe, overly_polymorphic
76 assert!(UndoLogs::<super::UndoLog<'_>>::in_snapshot(&self.undo_log));
78 let universe_at_start_of_snapshot = snapshot.universe;
79 if universe_at_start_of_snapshot == max_universe {
84 &MiniGraph::new(tcx, self.undo_log.region_constraints(), &self.storage.data.verifys);
86 let mut leak_check = LeakCheck::new(
88 universe_at_start_of_snapshot,
94 leak_check.assign_placeholder_values()?;
95 leak_check.propagate_scc_value()?;
100 struct LeakCheck<'me, 'tcx> {
102 universe_at_start_of_snapshot: ty::UniverseIndex,
103 overly_polymorphic: bool,
104 mini_graph: &'me MiniGraph<'tcx>,
105 rcc: &'me RegionConstraintCollector<'me, 'tcx>,
107 // Initially, for each SCC S, stores a placeholder `P` such that `S = P`
110 // Later, during the [`LeakCheck::propagate_scc_value`] function, this array
111 // is repurposed to store some placeholder `P` such that the weaker
112 // condition `S: P` must hold. (This is true if `S: S1` transitively and `S1
114 scc_placeholders: IndexVec<LeakCheckScc, Option<ty::PlaceholderRegion>>,
116 // For each SCC S, track the minimum universe that flows into it. Note that
117 // this is both the minimum of the universes for every region that is a
118 // member of the SCC, but also if you have `R1: R2`, then the universe of
119 // `R2` must be less than the universe of `R1` (i.e., `R1` flows `R2`). To
120 // see that, imagine that you have `P1: R` -- in that case, `R` must be
121 // either the placeholder `P1` or the empty region in that same universe.
123 // To detect errors, we look for an SCC S where the values in
124 // `scc_values[S]` (if any) cannot be stored into `scc_universes[S]`.
125 scc_universes: IndexVec<LeakCheckScc, SccUniverse<'tcx>>,
128 impl<'me, 'tcx> LeakCheck<'me, 'tcx> {
131 universe_at_start_of_snapshot: ty::UniverseIndex,
132 max_universe: ty::UniverseIndex,
133 overly_polymorphic: bool,
134 mini_graph: &'me MiniGraph<'tcx>,
135 rcc: &'me RegionConstraintCollector<'me, 'tcx>,
137 let dummy_scc_universe = SccUniverse { universe: max_universe, region: None };
140 universe_at_start_of_snapshot,
144 scc_placeholders: IndexVec::from_elem_n(None, mini_graph.sccs.num_sccs()),
145 scc_universes: IndexVec::from_elem_n(dummy_scc_universe, mini_graph.sccs.num_sccs()),
149 /// Compute what placeholders (if any) each SCC must be equal to.
150 /// Also compute the minimum universe of all the regions in each SCC.
151 fn assign_placeholder_values(&mut self) -> RelateResult<'tcx, ()> {
152 // First walk: find each placeholder that is from a newly created universe.
153 for (region, leak_check_node) in &self.mini_graph.nodes {
154 let scc = self.mini_graph.sccs.scc(*leak_check_node);
156 // Set the universe of each SCC to be the minimum of its constituent universes
157 let universe = self.rcc.universe(region);
159 "assign_placeholder_values: scc={:?} universe={:?} region={:?}",
160 scc, universe, region
162 self.scc_universes[scc].take_min(universe, region);
164 // Detect those SCCs that directly contain a placeholder
165 if let ty::RePlaceholder(placeholder) = region {
166 if self.universe_at_start_of_snapshot.cannot_name(placeholder.universe) {
167 self.assign_scc_value(scc, *placeholder)?;
175 // assign_scc_value(S, P): Update `scc_values` to account for the fact that `P: S` must hold.
176 // This may create an error.
180 placeholder: ty::PlaceholderRegion,
181 ) -> RelateResult<'tcx, ()> {
182 match self.scc_placeholders[scc] {
184 assert_ne!(p, placeholder);
185 return Err(self.placeholder_error(p, placeholder));
188 self.scc_placeholders[scc] = Some(placeholder);
195 /// For each SCC S, iterate over each successor S1 where `S: S1`:
198 /// Iterate over each SCC `S` and ensure that, for each `S1` where `S1: S`,
199 /// `universe(S) <= universe(S1)`. This executes after
200 /// `assign_placeholder_values`, so `universe(S)` is already the minimum
201 /// universe of any of its direct constituents.
202 fn propagate_scc_value(&mut self) -> RelateResult<'tcx, ()> {
205 // On start of the loop iteration for `scc1`:
207 // * `scc_universes[scc1]` contains the minimum universe of the
208 // constituents of `scc1`
209 // * `scc_placeholder[scc1]` stores the placeholder that `scc1` must
210 // be equal to (if any)
212 // For each succssor `scc2` where `scc1: scc2`:
214 // * `scc_placeholder[scc2]` stores some placeholder `P` where
215 // `scc2: P` (if any)
216 // * `scc_universes[scc2]` contains the minimum universe of the
217 // constituents of `scc2` and any of its successors
218 for scc1 in self.mini_graph.sccs.all_sccs() {
220 "propagate_scc_value: scc={:?} with universe {:?}",
221 scc1, self.scc_universes[scc1]
224 // Walk over each `scc2` such that `scc1: scc2` and compute:
226 // * `scc1_universe`: the minimum universe of `scc2` and the constituents of `scc1`
227 // * `succ_bound`: placeholder `P` that the successors must outlive, if any (if there are multiple,
228 // we pick one arbitrarily)
229 let mut scc1_universe = self.scc_universes[scc1];
230 let mut succ_bound = None;
231 for &scc2 in self.mini_graph.sccs.successors(scc1) {
232 let SccUniverse { universe: scc2_universe, region: scc2_region } =
233 self.scc_universes[scc2];
235 scc1_universe.take_min(scc2_universe, scc2_region.unwrap());
237 if let Some(b) = self.scc_placeholders[scc2] {
238 succ_bound = Some(b);
242 // Update minimum universe of scc1.
243 self.scc_universes[scc1] = scc1_universe;
245 // At this point, `scc_placholder[scc1]` stores the placeholder that
246 // `scc1` must be equal to, if any.
247 if let Some(scc1_placeholder) = self.scc_placeholders[scc1] {
249 "propagate_scc_value: scc1={:?} placeholder={:?} scc1_universe={:?}",
250 scc1, scc1_placeholder, scc1_universe
253 // Check if `P1: R` for some `R` in a universe that cannot name
254 // P1. That's an error.
255 if scc1_universe.universe.cannot_name(scc1_placeholder.universe) {
256 return Err(self.error(scc1_placeholder, scc1_universe.region.unwrap()));
259 // Check if we have some placeholder where `S: P2`
260 // (transitively). In that case, since `S = P1`, that implies
261 // `P1: P2`, which is an error condition.
262 if let Some(scc2_placeholder) = succ_bound {
263 assert_ne!(scc1_placeholder, scc2_placeholder);
264 return Err(self.placeholder_error(scc1_placeholder, scc2_placeholder));
267 // Otherwise, we can reach a placeholder if some successor can.
268 self.scc_placeholders[scc1] = succ_bound;
271 // At this point, `scc_placeholder[scc1]` stores some placeholder that `scc1` must outlive (if any).
276 fn placeholder_error(
278 placeholder1: ty::PlaceholderRegion,
279 placeholder2: ty::PlaceholderRegion,
280 ) -> TypeError<'tcx> {
281 self.error(placeholder1, self.tcx.mk_region(ty::RePlaceholder(placeholder2)))
286 placeholder: ty::PlaceholderRegion,
287 other_region: ty::Region<'tcx>,
288 ) -> TypeError<'tcx> {
289 debug!("error: placeholder={:?}, other_region={:?}", placeholder, other_region);
290 if self.overly_polymorphic {
291 TypeError::RegionsOverlyPolymorphic(placeholder.name, other_region)
293 TypeError::RegionsInsufficientlyPolymorphic(placeholder.name, other_region)
298 // States we need to distinguish:
300 // * must be equal to a placeholder (i.e., a placeholder is in the SCC)
301 // * it could conflict with some other regions in the SCC in different universes
302 // * or a different placeholder
303 // * `P1: S` and `S` must be equal to a placeholder
304 // * `P1: S` and `S` is in an incompatible universe
308 // (a) compute which placeholder (if any) each SCC must be equal to
309 // (b) compute its minimum universe
310 // (c) compute *some* placeholder where `S: P1` (any one will do)
312 // then we get an error if:
314 // - it must be equal to a placeholder `P1` and minimum universe cannot name `P1`
315 // - `S: P1` and minimum universe cannot name `P1`
316 // - `S: P1` and we must be equal to `P2`
318 // So we want to track:
320 // * Equal placeholder (if any)
321 // * Some bounding placeholder (if any)
322 // * Minimum universe
324 // * We compute equal placeholder + minimum universe of constituents in first pass
325 // * Then we walk in order and compute from our dependencies `S1` where `S: S1` (`S -> S1`)
326 // * bounding placeholder (if any)
327 // * minimum universe
328 // * And if we must be equal to a placeholder then we check it against
329 // * minimum universe
330 // * no bounding placeholder
332 /// Tracks the "minimum universe" for each SCC, along with some region that
333 /// caused it to change.
334 #[derive(Copy, Clone, Debug)]
335 struct SccUniverse<'tcx> {
336 /// For some SCC S, the minimum universe of:
338 /// * each region R in S
339 /// * each SCC S1 such that S: S1
340 universe: ty::UniverseIndex,
342 /// Some region that caused `universe` to be what it is.
343 region: Option<ty::Region<'tcx>>,
346 impl<'tcx> SccUniverse<'tcx> {
347 /// If `universe` is less than our current universe, then update
348 /// `self.universe` and `self.region`.
349 fn take_min(&mut self, universe: ty::UniverseIndex, region: ty::Region<'tcx>) {
350 if universe < self.universe || self.region.is_none() {
351 self.universe = universe;
352 self.region = Some(region);
357 rustc_index::newtype_index! {
358 struct LeakCheckNode {
359 DEBUG_FORMAT = "LeakCheckNode({})"
363 rustc_index::newtype_index! {
364 struct LeakCheckScc {
365 DEBUG_FORMAT = "LeakCheckScc({})"
369 /// Represents the graph of constraints. For each `R1: R2` constraint we create
370 /// an edge `R1 -> R2` in the graph.
371 struct MiniGraph<'tcx> {
372 /// Map from a region to the index of the node in the graph.
373 nodes: FxHashMap<ty::Region<'tcx>, LeakCheckNode>,
375 /// Map from node index to SCC, and stores the successors of each SCC. All
376 /// the regions in the same SCC are equal to one another, and if `S1 -> S2`,
378 sccs: Sccs<LeakCheckNode, LeakCheckScc>,
381 impl<'tcx> MiniGraph<'tcx> {
384 undo_log: impl Iterator<Item = &'a UndoLog<'tcx>>,
385 verifys: &[Verify<'tcx>],
390 let mut nodes = FxHashMap::default();
391 let mut edges = Vec::new();
393 // Note that if `R2: R1`, we get a callback `r1, r2`, so `target` is first parameter.
394 Self::iterate_undo_log(tcx, undo_log, verifys, |target, source| {
395 let source_node = Self::add_node(&mut nodes, source);
396 let target_node = Self::add_node(&mut nodes, target);
397 edges.push((source_node, target_node));
399 let graph = VecGraph::new(nodes.len(), edges);
400 let sccs = Sccs::new(&graph);
404 /// Invokes `each_edge(R1, R2)` for each edge where `R2: R1`
405 fn iterate_undo_log<'a>(
407 undo_log: impl Iterator<Item = &'a UndoLog<'tcx>>,
408 verifys: &[Verify<'tcx>],
409 mut each_edge: impl FnMut(ty::Region<'tcx>, ty::Region<'tcx>),
413 for undo_entry in undo_log {
415 &AddConstraint(Constraint::VarSubVar(a, b)) => {
416 each_edge(tcx.mk_region(ReVar(a)), tcx.mk_region(ReVar(b)));
418 &AddConstraint(Constraint::RegSubVar(a, b)) => {
419 each_edge(a, tcx.mk_region(ReVar(b)));
421 &AddConstraint(Constraint::VarSubReg(a, b)) => {
422 each_edge(tcx.mk_region(ReVar(a)), b);
424 &AddConstraint(Constraint::RegSubReg(a, b)) => {
428 each_edge(a, tcx.mk_region(ReVar(b)));
430 &AddVerify(i) => span_bug!(
431 verifys[i].origin.span(),
432 "we never add verifications while doing higher-ranked things",
434 &AddCombination(..) | &AddVar(..) => {}
440 nodes: &mut FxHashMap<ty::Region<'tcx>, LeakCheckNode>,
444 *nodes.entry(r).or_insert(LeakCheckNode::new(l))