1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
use std::fmt;
use std::ops::Index;

use rustc_index::{IndexSlice, IndexVec};
use rustc_middle::mir::ConstraintCategory;
use rustc_middle::ty::{RegionVid, TyCtxt, VarianceDiagInfo};
use rustc_span::Span;
use tracing::{debug, instrument};

use crate::region_infer::{ConstraintSccs, RegionDefinition, RegionTracker};
use crate::type_check::Locations;
use crate::universal_regions::UniversalRegions;

pub(crate) mod graph;

/// A set of NLL region constraints. These include "outlives"
/// constraints of the form `R1: R2`. Each constraint is identified by
/// a unique `OutlivesConstraintIndex` and you can index into the set
/// (`constraint_set[i]`) to access the constraint details.
#[derive(Clone, Debug, Default)]
pub(crate) struct OutlivesConstraintSet<'tcx> {
    outlives: IndexVec<OutlivesConstraintIndex, OutlivesConstraint<'tcx>>,
}

impl<'tcx> OutlivesConstraintSet<'tcx> {
    pub(crate) fn push(&mut self, constraint: OutlivesConstraint<'tcx>) {
        debug!("OutlivesConstraintSet::push({:?})", constraint);
        if constraint.sup == constraint.sub {
            // 'a: 'a is pretty uninteresting
            return;
        }
        self.outlives.push(constraint);
    }

    /// Constructs a "normal" graph from the constraint set; the graph makes it
    /// easy to find the constraints affecting a particular region.
    ///
    /// N.B., this graph contains a "frozen" view of the current
    /// constraints. Any new constraints added to the `OutlivesConstraintSet`
    /// after the graph is built will not be present in the graph.
    pub(crate) fn graph(&self, num_region_vars: usize) -> graph::NormalConstraintGraph {
        graph::ConstraintGraph::new(graph::Normal, self, num_region_vars)
    }

    /// Like `graph`, but constraints a reverse graph where `R1: R2`
    /// represents an edge `R2 -> R1`.
    pub(crate) fn reverse_graph(&self, num_region_vars: usize) -> graph::ReverseConstraintGraph {
        graph::ConstraintGraph::new(graph::Reverse, self, num_region_vars)
    }

    pub(crate) fn outlives(
        &self,
    ) -> &IndexSlice<OutlivesConstraintIndex, OutlivesConstraint<'tcx>> {
        &self.outlives
    }

    /// Computes cycles (SCCs) in the graph of regions. In particular,
    /// find all regions R1, R2 such that R1: R2 and R2: R1 and group
    /// them into an SCC, and find the relationships between SCCs.
    pub(crate) fn compute_sccs(
        &self,
        static_region: RegionVid,
        definitions: &IndexVec<RegionVid, RegionDefinition<'tcx>>,
    ) -> ConstraintSccs {
        let constraint_graph = self.graph(definitions.len());
        let region_graph = &constraint_graph.region_graph(self, static_region);
        ConstraintSccs::new_with_annotation(&region_graph, |r| {
            RegionTracker::new(r, &definitions[r])
        })
    }

    /// This method handles Universe errors by rewriting the constraint
    /// graph. For each strongly connected component in the constraint
    /// graph such that there is a series of constraints
    ///    A: B: C: ... : X  where
    /// A's universe is smaller than X's and A is a placeholder,
    /// add a constraint that A: 'static. This is a safe upper bound
    /// in the face of borrow checker/trait solver limitations that will
    /// eventually go away.
    ///
    /// For a more precise definition, see the documentation for
    /// [`RegionTracker::has_incompatible_universes()`].
    ///
    /// This edge case used to be handled during constraint propagation
    /// by iterating over the strongly connected components in the constraint
    /// graph while maintaining a set of bookkeeping mappings similar
    /// to what is stored in `RegionTracker` and manually adding 'sttaic as
    /// needed.
    ///
    /// It was rewritten as part of the Polonius project with the goal of moving
    /// higher-kindedness concerns out of the path of the borrow checker,
    /// for two reasons:
    ///
    /// 1. Implementing Polonius is difficult enough without also
    ///     handling them.
    /// 2. The long-term goal is to handle higher-kinded concerns
    ///     in the trait solver, where they belong. This avoids
    ///     logic duplication and allows future trait solvers
    ///     to compute better bounds than for example our
    ///     "must outlive 'static" here.
    ///
    /// This code is a stop-gap measure in preparation for the future trait solver.
    ///
    /// Every constraint added by this method is an
    /// internal `IllegalUniverse` constraint.
    #[instrument(skip(self, universal_regions, definitions))]
    pub(crate) fn add_outlives_static(
        &mut self,
        universal_regions: &UniversalRegions<'tcx>,
        definitions: &IndexVec<RegionVid, RegionDefinition<'tcx>>,
    ) -> ConstraintSccs {
        let fr_static = universal_regions.fr_static;
        let sccs = self.compute_sccs(fr_static, definitions);

        // Changed to `true` if we added any constraints to `self` and need to
        // recompute SCCs.
        let mut added_constraints = false;

        for scc in sccs.all_sccs() {
            // No point in adding 'static: 'static!
            // This micro-optimisation makes somewhat sense
            // because static outlives *everything*.
            if scc == sccs.scc(fr_static) {
                continue;
            }

            let annotation = sccs.annotation(scc);

            // If this SCC participates in a universe violation,
            // e.g. if it reaches a region with a universe smaller than
            // the largest region reached, add a requirement that it must
            // outlive `'static`.
            if annotation.has_incompatible_universes() {
                // Optimisation opportunity: this will add more constraints than
                // needed for correctness, since an SCC upstream of another with
                // a universe violation will "infect" its downstream SCCs to also
                // outlive static.
                added_constraints = true;
                let scc_representative_outlives_static = OutlivesConstraint {
                    sup: annotation.representative,
                    sub: fr_static,
                    category: ConstraintCategory::IllegalUniverse,
                    locations: Locations::All(rustc_span::DUMMY_SP),
                    span: rustc_span::DUMMY_SP,
                    variance_info: VarianceDiagInfo::None,
                    from_closure: false,
                };
                self.push(scc_representative_outlives_static);
            }
        }

        if added_constraints {
            // We changed the constraint set and so must recompute SCCs.
            self.compute_sccs(fr_static, definitions)
        } else {
            // If we didn't add any back-edges; no more work needs doing
            sccs
        }
    }
}

impl<'tcx> Index<OutlivesConstraintIndex> for OutlivesConstraintSet<'tcx> {
    type Output = OutlivesConstraint<'tcx>;

    fn index(&self, i: OutlivesConstraintIndex) -> &Self::Output {
        &self.outlives[i]
    }
}

#[derive(Copy, Clone, PartialEq, Eq)]
pub struct OutlivesConstraint<'tcx> {
    // NB. The ordering here is not significant for correctness, but
    // it is for convenience. Before we dump the constraints in the
    // debugging logs, we sort them, and we'd like the "super region"
    // to be first, etc. (In particular, span should remain last.)
    /// The region SUP must outlive SUB...
    pub sup: RegionVid,

    /// Region that must be outlived.
    pub sub: RegionVid,

    /// Where did this constraint arise?
    pub locations: Locations,

    /// The `Span` associated with the creation of this constraint.
    /// This should be used in preference to obtaining the span from
    /// `locations`, since the `locations` may give a poor span
    /// in some cases (e.g. converting a constraint from a promoted).
    pub span: Span,

    /// What caused this constraint?
    pub category: ConstraintCategory<'tcx>,

    /// Variance diagnostic information
    pub variance_info: VarianceDiagInfo<TyCtxt<'tcx>>,

    /// If this constraint is promoted from closure requirements.
    pub from_closure: bool,
}

impl<'tcx> fmt::Debug for OutlivesConstraint<'tcx> {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            formatter,
            "({:?}: {:?}) due to {:?} ({:?}) ({:?})",
            self.sup, self.sub, self.locations, self.variance_info, self.category,
        )
    }
}

rustc_index::newtype_index! {
    #[debug_format = "OutlivesConstraintIndex({})"]
    pub struct OutlivesConstraintIndex {}
}

rustc_index::newtype_index! {
    #[orderable]
    #[debug_format = "ConstraintSccIndex({})"]
    pub struct ConstraintSccIndex {}
}