1use rustc_data_structures::frozen::Frozen;
6use rustc_data_structures::fx::FxIndexMap;
7use rustc_data_structures::graph::scc;
8use rustc_data_structures::graph::scc::Sccs;
9use rustc_index::IndexVec;
10use rustc_infer::infer::RegionVariableOrigin;
11use rustc_middle::mir::ConstraintCategory;
12use rustc_middle::ty::{RegionVid, UniverseIndex};
13use tracing::debug;
14
15use crate::constraints::{ConstraintSccIndex, OutlivesConstraintSet};
16use crate::consumers::OutlivesConstraint;
17use crate::diagnostics::UniverseInfo;
18use crate::member_constraints::MemberConstraintSet;
19use crate::region_infer::values::{LivenessValues, PlaceholderIndices};
20use crate::region_infer::{ConstraintSccs, RegionDefinition, Representative, TypeTest};
21use crate::ty::VarianceDiagInfo;
22use crate::type_check::free_region_relations::UniversalRegionRelations;
23use crate::type_check::{Locations, MirTypeckRegionConstraints};
24use crate::universal_regions::UniversalRegions;
25use crate::{BorrowckInferCtxt, NllRegionVariableOrigin};
26
27pub(crate) struct LoweredConstraints<'tcx> {
30 pub(crate) constraint_sccs: Sccs<RegionVid, ConstraintSccIndex>,
31 pub(crate) definitions: Frozen<IndexVec<RegionVid, RegionDefinition<'tcx>>>,
32 pub(crate) scc_annotations: IndexVec<ConstraintSccIndex, RegionTracker>,
33 pub(crate) member_constraints: MemberConstraintSet<'tcx, RegionVid>,
34 pub(crate) outlives_constraints: Frozen<OutlivesConstraintSet<'tcx>>,
35 pub(crate) type_tests: Vec<TypeTest<'tcx>>,
36 pub(crate) liveness_constraints: LivenessValues,
37 pub(crate) universe_causes: FxIndexMap<UniverseIndex, UniverseInfo<'tcx>>,
38 pub(crate) placeholder_indices: PlaceholderIndices,
39}
40
41impl<'d, 'tcx, A: scc::Annotation> SccAnnotations<'d, 'tcx, A> {
42 pub(crate) fn init(definitions: &'d IndexVec<RegionVid, RegionDefinition<'tcx>>) -> Self {
43 Self { scc_to_annotation: IndexVec::new(), definitions }
44 }
45}
46
47pub(crate) struct SccAnnotations<'d, 'tcx, A: scc::Annotation> {
49 pub(crate) scc_to_annotation: IndexVec<ConstraintSccIndex, A>,
50 definitions: &'d IndexVec<RegionVid, RegionDefinition<'tcx>>,
51}
52
53impl scc::Annotations<RegionVid> for SccAnnotations<'_, '_, RegionTracker> {
54 fn new(&self, element: RegionVid) -> RegionTracker {
55 RegionTracker::new(element, &self.definitions[element])
56 }
57
58 fn annotate_scc(&mut self, scc: ConstraintSccIndex, annotation: RegionTracker) {
59 let idx = self.scc_to_annotation.push(annotation);
60 assert!(idx == scc);
61 }
62
63 type Ann = RegionTracker;
64 type SccIdx = ConstraintSccIndex;
65}
66
67#[derive(Copy, Debug, Clone)]
70pub(crate) struct RegionTracker {
71 max_placeholder_universe_reached: UniverseIndex,
74
75 max_nameable_universe: UniverseIndex,
79
80 pub(crate) representative: Representative,
82}
83
84impl RegionTracker {
85 pub(crate) fn new(rvid: RegionVid, definition: &RegionDefinition<'_>) -> Self {
86 let placeholder_universe =
87 if matches!(definition.origin, NllRegionVariableOrigin::Placeholder(_)) {
88 definition.universe
89 } else {
90 UniverseIndex::ROOT
91 };
92
93 Self {
94 max_placeholder_universe_reached: placeholder_universe,
95 max_nameable_universe: definition.universe,
96 representative: Representative::new(rvid, definition),
97 }
98 }
99
100 pub(crate) fn max_nameable_universe(self) -> UniverseIndex {
103 self.max_nameable_universe
104 }
105
106 fn merge_min_max_seen(&mut self, other: &Self) {
107 self.max_placeholder_universe_reached = std::cmp::max(
108 self.max_placeholder_universe_reached,
109 other.max_placeholder_universe_reached,
110 );
111
112 self.max_nameable_universe =
113 std::cmp::min(self.max_nameable_universe, other.max_nameable_universe);
114 }
115
116 pub(crate) fn has_incompatible_universes(&self) -> bool {
120 self.max_nameable_universe().cannot_name(self.max_placeholder_universe_reached)
121 }
122
123 pub(crate) fn universe_compatible_with(&self, other: Self) -> bool {
125 self.max_nameable_universe().can_name(other.max_nameable_universe())
126 || self.max_nameable_universe().can_name(other.max_placeholder_universe_reached)
127 }
128}
129
130impl scc::Annotation for RegionTracker {
131 fn merge_scc(mut self, other: Self) -> Self {
132 self.representative = self.representative.merge_scc(other.representative);
133 self.merge_min_max_seen(&other);
134 self
135 }
136
137 fn merge_reached(mut self, other: Self) -> Self {
138 self.merge_min_max_seen(&other);
140 self
141 }
142}
143
144fn region_definitions<'tcx>(
147 universal_regions: &UniversalRegions<'tcx>,
148 infcx: &BorrowckInferCtxt<'tcx>,
149) -> (Frozen<IndexVec<RegionVid, RegionDefinition<'tcx>>>, bool) {
150 let var_infos = infcx.get_region_var_infos();
151 let mut definitions = IndexVec::with_capacity(var_infos.len());
155 let mut has_placeholders = false;
156
157 for info in var_infos.iter() {
158 let origin = match info.origin {
159 RegionVariableOrigin::Nll(origin) => origin,
160 _ => NllRegionVariableOrigin::Existential { from_forall: false },
161 };
162
163 let definition = RegionDefinition { origin, universe: info.universe, external_name: None };
164
165 has_placeholders |= matches!(origin, NllRegionVariableOrigin::Placeholder(_));
166 definitions.push(definition);
167 }
168
169 for (external_name, variable) in universal_regions.named_universal_regions_iter() {
172 debug!("region {:?} has external name {:?}", variable, external_name);
173 definitions[variable].external_name = Some(external_name);
174 }
175 (Frozen::freeze(definitions), has_placeholders)
176}
177
178pub(crate) fn compute_sccs_applying_placeholder_outlives_constraints<'tcx>(
207 constraints: MirTypeckRegionConstraints<'tcx>,
208 universal_region_relations: &Frozen<UniversalRegionRelations<'tcx>>,
209 infcx: &BorrowckInferCtxt<'tcx>,
210) -> LoweredConstraints<'tcx> {
211 let universal_regions = &universal_region_relations.universal_regions;
212 let (definitions, has_placeholders) = region_definitions(universal_regions, infcx);
213
214 let MirTypeckRegionConstraints {
215 placeholder_indices,
216 placeholder_index_to_region: _,
217 liveness_constraints,
218 mut outlives_constraints,
219 mut member_constraints,
220 universe_causes,
221 type_tests,
222 } = constraints;
223
224 if let Some(guar) = universal_regions.tainted_by_errors() {
225 debug!("Universal regions tainted by errors; removing constraints!");
226 outlives_constraints = Default::default();
229 member_constraints = Default::default();
230
231 infcx.set_tainted_by_errors(guar);
233 }
234
235 let fr_static = universal_regions.fr_static;
236 let compute_sccs =
237 |constraints: &OutlivesConstraintSet<'tcx>,
238 annotations: &mut SccAnnotations<'_, 'tcx, RegionTracker>| {
239 ConstraintSccs::new_with_annotation(
240 &constraints.graph(definitions.len()).region_graph(constraints, fr_static),
241 annotations,
242 )
243 };
244
245 let mut scc_annotations = SccAnnotations::init(&definitions);
246 let constraint_sccs = compute_sccs(&outlives_constraints, &mut scc_annotations);
247
248 if !has_placeholders {
252 debug!("No placeholder regions found; skipping rewriting logic!");
253
254 return LoweredConstraints {
255 type_tests,
256 member_constraints,
257 constraint_sccs,
258 scc_annotations: scc_annotations.scc_to_annotation,
259 definitions,
260 outlives_constraints: Frozen::freeze(outlives_constraints),
261 liveness_constraints,
262 universe_causes,
263 placeholder_indices,
264 };
265 }
266 debug!("Placeholders present; activating placeholder handling logic!");
267
268 let added_constraints = rewrite_placeholder_outlives(
269 &constraint_sccs,
270 &scc_annotations,
271 fr_static,
272 &mut outlives_constraints,
273 );
274
275 let (constraint_sccs, scc_annotations) = if added_constraints {
276 let mut annotations = SccAnnotations::init(&definitions);
277
278 (compute_sccs(&outlives_constraints, &mut annotations), annotations.scc_to_annotation)
283 } else {
284 debug!("No constraints rewritten!");
286 (constraint_sccs, scc_annotations.scc_to_annotation)
287 };
288
289 LoweredConstraints {
290 constraint_sccs,
291 definitions,
292 scc_annotations,
293 member_constraints,
294 outlives_constraints: Frozen::freeze(outlives_constraints),
295 type_tests,
296 liveness_constraints,
297 universe_causes,
298 placeholder_indices,
299 }
300}
301
302fn rewrite_placeholder_outlives<'tcx>(
303 sccs: &Sccs<RegionVid, ConstraintSccIndex>,
304 annotations: &SccAnnotations<'_, '_, RegionTracker>,
305 fr_static: RegionVid,
306 outlives_constraints: &mut OutlivesConstraintSet<'tcx>,
307) -> bool {
308 let mut added_constraints = false;
311
312 let annotations = &annotations.scc_to_annotation;
313
314 for scc in sccs.all_sccs() {
315 if scc == sccs.scc(fr_static) {
319 continue;
320 }
321
322 let annotation = annotations[scc];
323
324 if annotation.has_incompatible_universes() {
329 let scc_representative_outlives_static = OutlivesConstraint {
334 sup: annotation.representative.rvid(),
335 sub: fr_static,
336 category: ConstraintCategory::IllegalUniverse,
337 locations: Locations::All(rustc_span::DUMMY_SP),
338 span: rustc_span::DUMMY_SP,
339 variance_info: VarianceDiagInfo::None,
340 from_closure: false,
341 };
342 outlives_constraints.push(scc_representative_outlives_static);
343 added_constraints = true;
344 debug!("Added {:?}: 'static!", annotation.representative.rvid());
345 }
346 }
347 added_constraints
348}