rustc_borrowck/constraints/
mod.rs

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