rustc_borrowck/
handle_placeholders.rs

1//! Logic for lowering higher-kinded outlives constraints
2//! (with placeholders and universes) and turn them into regular
3//! outlives constraints.
4
5use 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
27/// A set of outlives constraints after rewriting to remove
28/// higher-kinded constraints.
29pub(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
47/// A Visitor for SCC annotation construction.
48pub(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/// An annotation for region graph SCCs that tracks
68/// the values of its elements. This annotates a single SCC.
69#[derive(Copy, Debug, Clone)]
70pub(crate) struct RegionTracker {
71    /// The largest universe of a placeholder reached from this SCC.
72    /// This includes placeholders within this SCC.
73    max_placeholder_universe_reached: UniverseIndex,
74
75    /// The largest universe nameable from this SCC.
76    /// It is the smallest nameable universes of all
77    /// existential regions reachable from it.
78    max_nameable_universe: UniverseIndex,
79
80    /// The representative Region Variable Id for this SCC.
81    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    /// The largest universe this SCC can name. It's the smallest
101    /// largest nameable uninverse of any reachable region.
102    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    /// Returns `true` if during the annotated SCC reaches a placeholder
117    /// with a universe larger than the smallest nameable universe of any
118    /// reachable existential region.
119    pub(crate) fn has_incompatible_universes(&self) -> bool {
120        self.max_nameable_universe().cannot_name(self.max_placeholder_universe_reached)
121    }
122
123    /// Determine if the tracked universes of the two SCCs are compatible.
124    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        // No update to in-component values, only add seen values.
139        self.merge_min_max_seen(&other);
140        self
141    }
142}
143
144/// Determines if the region variable definitions contain
145/// placeholders, and compute them for later use.
146fn 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    // Create a RegionDefinition for each inference variable. This happens here because
152    // it allows us to sneak in a cheap check for placeholders. Otherwise, its proper home
153    // is in `RegionInferenceContext::new()`, probably.
154    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    // Add external names from universal regions in fun function definitions.
170    // FIXME: this two-step method is annoying, but I don't know how to avoid it.
171    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
178/// This method handles placeholders by rewriting the constraint
179/// graph. For each strongly connected component in the constraint
180/// graph such that there is a series of constraints
181///    A: B: C: ... : X  where
182/// A contains a placeholder whose universe cannot be named by X,
183/// add a constraint that A: 'static. This is a safe upper bound
184/// in the face of borrow checker/trait solver limitations that will
185/// eventually go away.
186///
187/// For a more precise definition, see the documentation for
188/// [`RegionTracker`] and its methods!
189///
190/// This edge case used to be handled during constraint propagation.
191/// It was rewritten as part of the Polonius project with the goal of moving
192/// higher-kindedness concerns out of the path of the borrow checker,
193/// for two reasons:
194///
195/// 1. Implementing Polonius is difficult enough without also
196///     handling them.
197/// 2. The long-term goal is to handle higher-kinded concerns
198///     in the trait solver, where they belong. This avoids
199///     logic duplication and allows future trait solvers
200///     to compute better bounds than for example our
201///     "must outlive 'static" here.
202///
203/// This code is a stop-gap measure in preparation for the future trait solver.
204///
205/// Every constraint added by this method is an internal `IllegalUniverse` constraint.
206pub(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        // Suppress unhelpful extra errors in `infer_opaque_types` by clearing out all
227        // outlives bounds that we may end up checking.
228        outlives_constraints = Default::default();
229        member_constraints = Default::default();
230
231        // Also taint the entire scope.
232        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    // This code structure is a bit convoluted because it allows for a planned
249    // future change where the early return here has a different type of annotation
250    // that does much less work.
251    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        // We changed the constraint set and so must recompute SCCs.
279        // Optimisation opportunity: if we can add them incrementally (and that's
280        // possible because edges to 'static always only merge SCCs into 'static),
281        // we would potentially save a lot of work here.
282        (compute_sccs(&outlives_constraints, &mut annotations), annotations.scc_to_annotation)
283    } else {
284        // If we didn't add any back-edges; no more work needs doing
285        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    // Changed to `true` if we added any constraints and need to
309    // recompute SCCs.
310    let mut added_constraints = false;
311
312    let annotations = &annotations.scc_to_annotation;
313
314    for scc in sccs.all_sccs() {
315        // No point in adding 'static: 'static!
316        // This micro-optimisation makes somewhat sense
317        // because static outlives *everything*.
318        if scc == sccs.scc(fr_static) {
319            continue;
320        }
321
322        let annotation = annotations[scc];
323
324        // If this SCC participates in a universe violation,
325        // e.g. if it reaches a region with a universe smaller than
326        // the largest region reached, add a requirement that it must
327        // outlive `'static`.
328        if annotation.has_incompatible_universes() {
329            // Optimisation opportunity: this will add more constraints than
330            // needed for correctness, since an SCC upstream of another with
331            // a universe violation will "infect" its downstream SCCs to also
332            // outlive static.
333            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}