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
// The outlines relation `T: 'a` or `'a: 'b`. This code frequently
// refers to rules defined in RFC 1214 (`OutlivesFooBar`), so see that
// RFC for reference.

use rustc_data_structures::sso::SsoHashSet;
use rustc_middle::ty::subst::{GenericArg, GenericArgKind};
use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitable};
use smallvec::{smallvec, SmallVec};

#[derive(Debug)]
pub enum Component<'tcx> {
    Region(ty::Region<'tcx>),
    Param(ty::ParamTy),
    UnresolvedInferenceVariable(ty::InferTy),

    // Projections like `T::Foo` are tricky because a constraint like
    // `T::Foo: 'a` can be satisfied in so many ways. There may be a
    // where-clause that says `T::Foo: 'a`, or the defining trait may
    // include a bound like `type Foo: 'static`, or -- in the most
    // conservative way -- we can prove that `T: 'a` (more generally,
    // that all components in the projection outlive `'a`). This code
    // is not in a position to judge which is the best technique, so
    // we just product the projection as a component and leave it to
    // the consumer to decide (but see `EscapingProjection` below).
    Projection(ty::ProjectionTy<'tcx>),

    // In the case where a projection has escaping regions -- meaning
    // regions bound within the type itself -- we always use
    // the most conservative rule, which requires that all components
    // outlive the bound. So for example if we had a type like this:
    //
    //     for<'a> Trait1<  <T as Trait2<'a,'b>>::Foo  >
    //                      ~~~~~~~~~~~~~~~~~~~~~~~~~
    //
    // then the inner projection (underlined) has an escaping region
    // `'a`. We consider that outer trait `'c` to meet a bound if `'b`
    // outlives `'b: 'c`, and we don't consider whether the trait
    // declares that `Foo: 'static` etc. Therefore, we just return the
    // free components of such a projection (in this case, `'b`).
    //
    // However, in the future, we may want to get smarter, and
    // actually return a "higher-ranked projection" here. Therefore,
    // we mark that these components are part of an escaping
    // projection, so that implied bounds code can avoid relying on
    // them. This gives us room to improve the regionck reasoning in
    // the future without breaking backwards compat.
    EscapingProjection(Vec<Component<'tcx>>),
}

/// Push onto `out` all the things that must outlive `'a` for the condition
/// `ty0: 'a` to hold. Note that `ty0` must be a **fully resolved type**.
pub fn push_outlives_components<'tcx>(
    tcx: TyCtxt<'tcx>,
    ty0: Ty<'tcx>,
    out: &mut SmallVec<[Component<'tcx>; 4]>,
) {
    let mut visited = SsoHashSet::new();
    compute_components(tcx, ty0, out, &mut visited);
    debug!("components({:?}) = {:?}", ty0, out);
}

fn compute_components<'tcx>(
    tcx: TyCtxt<'tcx>,
    ty: Ty<'tcx>,
    out: &mut SmallVec<[Component<'tcx>; 4]>,
    visited: &mut SsoHashSet<GenericArg<'tcx>>,
) {
    // Descend through the types, looking for the various "base"
    // components and collecting them into `out`. This is not written
    // with `collect()` because of the need to sometimes skip subtrees
    // in the `subtys` iterator (e.g., when encountering a
    // projection).
    match *ty.kind() {
            ty::FnDef(_, substs) => {
                // HACK(eddyb) ignore lifetimes found shallowly in `substs`.
                // This is inconsistent with `ty::Adt` (including all substs)
                // and with `ty::Closure` (ignoring all substs other than
                // upvars, of which a `ty::FnDef` doesn't have any), but
                // consistent with previous (accidental) behavior.
                // See https://github.com/rust-lang/rust/issues/70917
                // for further background and discussion.
                for child in substs {
                    match child.unpack() {
                        GenericArgKind::Type(ty) => {
                            compute_components(tcx, ty, out, visited);
                        }
                        GenericArgKind::Lifetime(_) => {}
                        GenericArgKind::Const(_) => {
                            compute_components_recursive(tcx, child, out, visited);
                        }
                    }
                }
            }

            ty::Array(element, _) => {
                // Don't look into the len const as it doesn't affect regions
                compute_components(tcx, element, out, visited);
            }

            ty::Closure(_, ref substs) => {
                let tupled_ty = substs.as_closure().tupled_upvars_ty();
                compute_components(tcx, tupled_ty, out, visited);
            }

            ty::Generator(_, ref substs, _) => {
                // Same as the closure case
                let tupled_ty = substs.as_generator().tupled_upvars_ty();
                compute_components(tcx, tupled_ty, out, visited);

                // We ignore regions in the generator interior as we don't
                // want these to affect region inference
            }

            // All regions are bound inside a witness
            ty::GeneratorWitness(..) => (),

            // OutlivesTypeParameterEnv -- the actual checking that `X:'a`
            // is implied by the environment is done in regionck.
            ty::Param(p) => {
                out.push(Component::Param(p));
            }

            // For projections, we prefer to generate an obligation like
            // `<P0 as Trait<P1...Pn>>::Foo: 'a`, because this gives the
            // regionck more ways to prove that it holds. However,
            // regionck is not (at least currently) prepared to deal with
            // higher-ranked regions that may appear in the
            // trait-ref. Therefore, if we see any higher-ranked regions,
            // we simply fallback to the most restrictive rule, which
            // requires that `Pi: 'a` for all `i`.
            ty::Projection(ref data) => {
                if !data.has_escaping_bound_vars() {
                    // best case: no escaping regions, so push the
                    // projection and skip the subtree (thus generating no
                    // constraints for Pi). This defers the choice between
                    // the rules OutlivesProjectionEnv,
                    // OutlivesProjectionTraitDef, and
                    // OutlivesProjectionComponents to regionck.
                    out.push(Component::Projection(*data));
                } else {
                    // fallback case: hard code
                    // OutlivesProjectionComponents.  Continue walking
                    // through and constrain Pi.
                    let mut subcomponents = smallvec![];
                    let mut subvisited = SsoHashSet::new();
                    compute_components_recursive(tcx, ty.into(), &mut subcomponents, &mut subvisited);
                    out.push(Component::EscapingProjection(subcomponents.into_iter().collect()));
                }
            }

            // We assume that inference variables are fully resolved.
            // So, if we encounter an inference variable, just record
            // the unresolved variable as a component.
            ty::Infer(infer_ty) => {
                out.push(Component::UnresolvedInferenceVariable(infer_ty));
            }

            // Most types do not introduce any region binders, nor
            // involve any other subtle cases, and so the WF relation
            // simply constraints any regions referenced directly by
            // the type and then visits the types that are lexically
            // contained within. (The comments refer to relevant rules
            // from RFC1214.)
            ty::Bool |            // OutlivesScalar
            ty::Char |            // OutlivesScalar
            ty::Int(..) |         // OutlivesScalar
            ty::Uint(..) |        // OutlivesScalar
            ty::Float(..) |       // OutlivesScalar
            ty::Never |           // ...
            ty::Adt(..) |         // OutlivesNominalType
            ty::Opaque(..) |      // OutlivesNominalType (ish)
            ty::Foreign(..) |     // OutlivesNominalType
            ty::Str |             // OutlivesScalar (ish)
            ty::Slice(..) |       // ...
            ty::RawPtr(..) |      // ...
            ty::Ref(..) |         // OutlivesReference
            ty::Tuple(..) |       // ...
            ty::FnPtr(_) |        // OutlivesFunction (*)
            ty::Dynamic(..) |     // OutlivesObject, OutlivesFragment (*)
            ty::Placeholder(..) |
            ty::Bound(..) |
            ty::Error(_) => {
                // (*) Function pointers and trait objects are both binders.
                // In the RFC, this means we would add the bound regions to
                // the "bound regions list".  In our representation, no such
                // list is maintained explicitly, because bound regions
                // themselves can be readily identified.
                compute_components_recursive(tcx, ty.into(), out, visited);
            }
        }
}

/// Collect [Component]s for *all* the substs of `parent`.
///
/// This should not be used to get the components of `parent` itself.
/// Use [push_outlives_components] instead.
pub(super) fn compute_components_recursive<'tcx>(
    tcx: TyCtxt<'tcx>,
    parent: GenericArg<'tcx>,
    out: &mut SmallVec<[Component<'tcx>; 4]>,
    visited: &mut SsoHashSet<GenericArg<'tcx>>,
) {
    for child in parent.walk_shallow(visited) {
        match child.unpack() {
            GenericArgKind::Type(ty) => {
                compute_components(tcx, ty, out, visited);
            }
            GenericArgKind::Lifetime(lt) => {
                // Ignore late-bound regions.
                if !lt.is_late_bound() {
                    out.push(Component::Region(lt));
                }
            }
            GenericArgKind::Const(_) => {
                compute_components_recursive(tcx, child, out, visited);
            }
        }
    }
}