2 use crate::infer::CombinedSnapshot;
3 use rustc_data_structures::{
5 graph::{scc::Sccs, vec_graph::VecGraph},
8 use rustc_index::vec::Idx;
9 use rustc_middle::ty::error::TypeError;
10 use rustc_middle::ty::relate::RelateResult;
12 impl<'tcx> RegionConstraintCollector<'_, 'tcx> {
13 /// Searches new universes created during `snapshot`, looking for
14 /// placeholders that may "leak" out from the universes they are contained
15 /// in. If any leaking placeholders are found, then an `Err` is returned
16 /// (typically leading to the snapshot being reversed).
18 /// The leak check *used* to be the only way we had to handle higher-ranked
19 /// obligations. Now that we have integrated universes into the region
20 /// solvers, this is no longer the case, but we retain the leak check for
21 /// backwards compatibility purposes. In particular, it lets us make "early"
22 /// decisions about whether a region error will be reported that are used in
23 /// coherence and elsewhere -- see #56105 and #59490 for more details. The
24 /// eventual fate of the leak checker is not yet settled.
26 /// The leak checker works by searching for the following error patterns:
28 /// * P1: P2, where P1 != P2
29 /// * P1: R, where R is in some universe that cannot name P1
31 /// The idea here is that each of these patterns represents something that
32 /// the region solver would eventually report as an error, so we can detect
33 /// the error early. There is a fly in the ointment, though, in that this is
34 /// not entirely true. In particular, in the future, we may extend the
35 /// environment with implied bounds or other info about how placeholders
36 /// relate to regions in outer universes. In that case, `P1: R` for example
37 /// might become solvable.
39 /// # Summary of the implementation
41 /// The leak checks as follows. First, we construct a graph where `R2: R1`
42 /// implies `R2 -> R1`, and we compute the SCCs.
44 /// For each SCC S, we compute:
46 /// * what placeholder P it must be equal to, if any
47 /// * if there are multiple placeholders that must be equal, report an error because `P1: P2`
48 /// * the minimum universe of its constituents
50 /// Then we walk the SCCs in dependency order and compute
52 /// * what placeholder they must outlive transitively
53 /// * if they must also be equal to a placeholder, report an error because `P1: P2`
54 /// * minimum universe U of all SCCs they must outlive
55 /// * if they must also be equal to a placeholder P, and U cannot name P, report an error, as that
56 /// indicates `P: R` and `R` is in an incompatible universe
60 /// Older variants of the leak check used to report errors for these
61 /// patterns, but we no longer do:
63 /// * R: P1, even if R cannot name P1, because R = 'static is a valid sol'n
64 /// * R: P1, R: P2, as above
68 overly_polymorphic: bool,
69 max_universe: ty::UniverseIndex,
70 snapshot: &CombinedSnapshot<'tcx>,
71 ) -> RelateResult<'tcx, ()> {
73 "leak_check(max_universe={:?}, snapshot.universe={:?}, overly_polymorphic={:?})",
74 max_universe, snapshot.universe, overly_polymorphic
77 assert!(UndoLogs::<super::UndoLog<'_>>::in_snapshot(&self.undo_log));
79 let universe_at_start_of_snapshot = snapshot.universe;
80 if universe_at_start_of_snapshot == max_universe {
85 &MiniGraph::new(tcx, self.undo_log.region_constraints(), &self.storage.data.verifys);
87 let mut leak_check = LeakCheck::new(
89 universe_at_start_of_snapshot,
95 leak_check.assign_placeholder_values()?;
96 leak_check.propagate_scc_value()?;
101 struct LeakCheck<'me, 'tcx> {
103 universe_at_start_of_snapshot: ty::UniverseIndex,
104 /// Only used when reporting region errors.
105 overly_polymorphic: bool,
106 mini_graph: &'me MiniGraph<'tcx>,
107 rcc: &'me RegionConstraintCollector<'me, 'tcx>,
109 // Initially, for each SCC S, stores a placeholder `P` such that `S = P`
112 // Later, during the [`LeakCheck::propagate_scc_value`] function, this array
113 // is repurposed to store some placeholder `P` such that the weaker
114 // condition `S: P` must hold. (This is true if `S: S1` transitively and `S1
116 scc_placeholders: IndexVec<LeakCheckScc, Option<ty::PlaceholderRegion>>,
118 // For each SCC S, track the minimum universe that flows into it. Note that
119 // this is both the minimum of the universes for every region that is a
120 // member of the SCC, but also if you have `R1: R2`, then the universe of
121 // `R2` must be less than the universe of `R1` (i.e., `R1` flows `R2`). To
122 // see that, imagine that you have `P1: R` -- in that case, `R` must be
123 // either the placeholder `P1` or the empty region in that same universe.
125 // To detect errors, we look for an SCC S where the values in
126 // `scc_values[S]` (if any) cannot be stored into `scc_universes[S]`.
127 scc_universes: IndexVec<LeakCheckScc, SccUniverse<'tcx>>,
130 impl<'me, 'tcx> LeakCheck<'me, 'tcx> {
133 universe_at_start_of_snapshot: ty::UniverseIndex,
134 max_universe: ty::UniverseIndex,
135 overly_polymorphic: bool,
136 mini_graph: &'me MiniGraph<'tcx>,
137 rcc: &'me RegionConstraintCollector<'me, 'tcx>,
139 let dummy_scc_universe = SccUniverse { universe: max_universe, region: None };
142 universe_at_start_of_snapshot,
146 scc_placeholders: IndexVec::from_elem_n(None, mini_graph.sccs.num_sccs()),
147 scc_universes: IndexVec::from_elem_n(dummy_scc_universe, mini_graph.sccs.num_sccs()),
151 /// Compute what placeholders (if any) each SCC must be equal to.
152 /// Also compute the minimum universe of all the regions in each SCC.
153 fn assign_placeholder_values(&mut self) -> RelateResult<'tcx, ()> {
154 // First walk: find each placeholder that is from a newly created universe.
155 for (region, leak_check_node) in &self.mini_graph.nodes {
156 let scc = self.mini_graph.sccs.scc(*leak_check_node);
158 // Set the universe of each SCC to be the minimum of its constituent universes
159 let universe = self.rcc.universe(*region);
161 "assign_placeholder_values: scc={:?} universe={:?} region={:?}",
162 scc, universe, region
164 self.scc_universes[scc].take_min(universe, *region);
166 // Detect those SCCs that directly contain a placeholder
167 if let ty::RePlaceholder(placeholder) = **region {
168 if self.universe_at_start_of_snapshot.cannot_name(placeholder.universe) {
169 self.assign_scc_value(scc, placeholder)?;
177 // assign_scc_value(S, P): Update `scc_values` to account for the fact that `P: S` must hold.
178 // This may create an error.
182 placeholder: ty::PlaceholderRegion,
183 ) -> RelateResult<'tcx, ()> {
184 match self.scc_placeholders[scc] {
186 assert_ne!(p, placeholder);
187 return Err(self.placeholder_error(p, placeholder));
190 self.scc_placeholders[scc] = Some(placeholder);
197 /// For each SCC S, iterate over each successor S1 where `S: S1`:
200 /// Iterate over each SCC `S` and ensure that, for each `S1` where `S1: S`,
201 /// `universe(S) <= universe(S1)`. This executes after
202 /// `assign_placeholder_values`, so `universe(S)` is already the minimum
203 /// universe of any of its direct constituents.
204 fn propagate_scc_value(&mut self) -> RelateResult<'tcx, ()> {
207 // On start of the loop iteration for `scc1`:
209 // * `scc_universes[scc1]` contains the minimum universe of the
210 // constituents of `scc1`
211 // * `scc_placeholder[scc1]` stores the placeholder that `scc1` must
212 // be equal to (if any)
214 // For each successor `scc2` where `scc1: scc2`:
216 // * `scc_placeholder[scc2]` stores some placeholder `P` where
217 // `scc2: P` (if any)
218 // * `scc_universes[scc2]` contains the minimum universe of the
219 // constituents of `scc2` and any of its successors
220 for scc1 in self.mini_graph.sccs.all_sccs() {
222 "propagate_scc_value: scc={:?} with universe {:?}",
223 scc1, self.scc_universes[scc1]
226 // Walk over each `scc2` such that `scc1: scc2` and compute:
228 // * `scc1_universe`: the minimum universe of `scc2` and the constituents of `scc1`
229 // * `succ_bound`: placeholder `P` that the successors must outlive, if any (if there are multiple,
230 // we pick one arbitrarily)
231 let mut scc1_universe = self.scc_universes[scc1];
232 let mut succ_bound = None;
233 for &scc2 in self.mini_graph.sccs.successors(scc1) {
234 let SccUniverse { universe: scc2_universe, region: scc2_region } =
235 self.scc_universes[scc2];
237 scc1_universe.take_min(scc2_universe, scc2_region.unwrap());
239 if let Some(b) = self.scc_placeholders[scc2] {
240 succ_bound = Some(b);
244 // Update minimum universe of scc1.
245 self.scc_universes[scc1] = scc1_universe;
247 // At this point, `scc_placeholders[scc1]` stores the placeholder that
248 // `scc1` must be equal to, if any.
249 if let Some(scc1_placeholder) = self.scc_placeholders[scc1] {
251 "propagate_scc_value: scc1={:?} placeholder={:?} scc1_universe={:?}",
252 scc1, scc1_placeholder, scc1_universe
255 // Check if `P1: R` for some `R` in a universe that cannot name
256 // P1. That's an error.
257 if scc1_universe.universe.cannot_name(scc1_placeholder.universe) {
258 return Err(self.error(scc1_placeholder, scc1_universe.region.unwrap()));
261 // Check if we have some placeholder where `S: P2`
262 // (transitively). In that case, since `S = P1`, that implies
263 // `P1: P2`, which is an error condition.
264 if let Some(scc2_placeholder) = succ_bound {
265 assert_ne!(scc1_placeholder, scc2_placeholder);
266 return Err(self.placeholder_error(scc1_placeholder, scc2_placeholder));
269 // Otherwise, we can reach a placeholder if some successor can.
270 self.scc_placeholders[scc1] = succ_bound;
273 // At this point, `scc_placeholder[scc1]` stores some placeholder that `scc1` must outlive (if any).
278 fn placeholder_error(
280 placeholder1: ty::PlaceholderRegion,
281 placeholder2: ty::PlaceholderRegion,
282 ) -> TypeError<'tcx> {
283 self.error(placeholder1, self.tcx.mk_region(ty::RePlaceholder(placeholder2)))
288 placeholder: ty::PlaceholderRegion,
289 other_region: ty::Region<'tcx>,
290 ) -> TypeError<'tcx> {
291 debug!("error: placeholder={:?}, other_region={:?}", placeholder, other_region);
292 if self.overly_polymorphic {
293 TypeError::RegionsOverlyPolymorphic(placeholder.name, other_region)
295 TypeError::RegionsInsufficientlyPolymorphic(placeholder.name, other_region)
300 // States we need to distinguish:
302 // * must be equal to a placeholder (i.e., a placeholder is in the SCC)
303 // * it could conflict with some other regions in the SCC in different universes
304 // * or a different placeholder
305 // * `P1: S` and `S` must be equal to a placeholder
306 // * `P1: S` and `S` is in an incompatible universe
310 // (a) compute which placeholder (if any) each SCC must be equal to
311 // (b) compute its minimum universe
312 // (c) compute *some* placeholder where `S: P1` (any one will do)
314 // then we get an error if:
316 // - it must be equal to a placeholder `P1` and minimum universe cannot name `P1`
317 // - `S: P1` and minimum universe cannot name `P1`
318 // - `S: P1` and we must be equal to `P2`
320 // So we want to track:
322 // * Equal placeholder (if any)
323 // * Some bounding placeholder (if any)
324 // * Minimum universe
326 // * We compute equal placeholder + minimum universe of constituents in first pass
327 // * Then we walk in order and compute from our dependencies `S1` where `S: S1` (`S -> S1`)
328 // * bounding placeholder (if any)
329 // * minimum universe
330 // * And if we must be equal to a placeholder then we check it against
331 // * minimum universe
332 // * no bounding placeholder
334 /// Tracks the "minimum universe" for each SCC, along with some region that
335 /// caused it to change.
336 #[derive(Copy, Clone, Debug)]
337 struct SccUniverse<'tcx> {
338 /// For some SCC S, the minimum universe of:
340 /// * each region R in S
341 /// * each SCC S1 such that S: S1
342 universe: ty::UniverseIndex,
344 /// Some region that caused `universe` to be what it is.
345 region: Option<ty::Region<'tcx>>,
348 impl<'tcx> SccUniverse<'tcx> {
349 /// If `universe` is less than our current universe, then update
350 /// `self.universe` and `self.region`.
351 fn take_min(&mut self, universe: ty::UniverseIndex, region: ty::Region<'tcx>) {
352 if universe < self.universe || self.region.is_none() {
353 self.universe = universe;
354 self.region = Some(region);
359 rustc_index::newtype_index! {
360 #[debug_format = "LeakCheckNode({})"]
361 struct LeakCheckNode {}
364 rustc_index::newtype_index! {
365 #[debug_format = "LeakCheckScc({})"]
366 struct 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: FxIndexMap<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 = FxIndexMap::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 FxIndexMap<ty::Region<'tcx>, LeakCheckNode>,
444 *nodes.entry(r).or_insert(LeakCheckNode::new(l))