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
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
//! The outlives relation `T: 'a` or `'a: 'b`. This code frequently
//! refers to rules defined in RFC 1214 (`OutlivesFooBar`), so see that
//! RFC for reference.
use derive_where::derive_where;
use smallvec::{SmallVec, smallvec};
use crate::data_structures::SsoHashSet;
use crate::inherent::*;
use crate::visit::{TypeSuperVisitable, TypeVisitable, TypeVisitableExt as _, TypeVisitor};
use crate::{self as ty, Interner};
#[derive_where(Debug; I: Interner)]
pub enum Component<I: Interner> {
Region(I::Region),
Param(I::ParamTy),
Placeholder(ty::PlaceholderType<I>),
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).
Alias(ty::AliasTy<I>),
// 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.
EscapingAlias(Vec<Component<I>>),
}
/// 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<I: Interner>(
cx: I,
ty: I::Ty,
out: &mut SmallVec<[Component<I>; 4]>,
) {
ty.visit_with(&mut OutlivesCollector { cx, out, visited: Default::default() });
}
struct OutlivesCollector<'a, I: Interner> {
cx: I,
out: &'a mut SmallVec<[Component<I>; 4]>,
visited: SsoHashSet<I::Ty>,
}
impl<I: Interner> TypeVisitor<I> for OutlivesCollector<'_, I> {
#[cfg(not(feature = "nightly"))]
type Result = ();
fn visit_ty(&mut self, ty: I::Ty) -> Self::Result {
if !self.visited.insert(ty) {
return;
}
// 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(_, args) => {
// HACK(eddyb) ignore lifetimes found shallowly in `args`.
// This is inconsistent with `ty::Adt` (including all args)
// and with `ty::Closure` (ignoring all args 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 args.iter() {
match child.kind() {
ty::GenericArgKind::Lifetime(_) => {}
ty::GenericArgKind::Type(_) | ty::GenericArgKind::Const(_) => {
child.visit_with(self);
}
}
}
}
ty::Closure(_, args) => {
args.as_closure().tupled_upvars_ty().visit_with(self);
}
ty::CoroutineClosure(_, args) => {
args.as_coroutine_closure().tupled_upvars_ty().visit_with(self);
}
ty::Coroutine(_, args) => {
args.as_coroutine().tupled_upvars_ty().visit_with(self);
// Coroutines may not outlive a region unless the resume
// ty outlives a region. This is because the resume ty may
// store data that lives shorter than this outlives region
// across yield points, which may subsequently be accessed
// after the coroutine is resumed again.
//
// Conceptually, you may think of the resume arg as an upvar
// of `&mut Option<ResumeArgTy>`, since it is kinda like
// storage shared between the callee of the coroutine and the
// coroutine body.
args.as_coroutine().resume_ty().visit_with(self);
// We ignore regions in the coroutine interior as we don't
// want these to affect region inference
}
// All regions are bound inside a witness, and we don't emit
// higher-ranked outlives components currently.
ty::CoroutineWitness(..) => {}
// OutlivesTypeParameterEnv -- the actual checking that `X:'a`
// is implied by the environment is done in regionck.
ty::Param(p) => {
self.out.push(Component::Param(p));
}
ty::Placeholder(p) => {
self.out.push(Component::Placeholder(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::Alias(alias_ty) => {
if !alias_ty.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.
self.out.push(Component::Alias(alias_ty));
} else {
// fallback case: hard code
// OutlivesProjectionComponents. Continue walking
// through and constrain Pi.
let mut subcomponents = smallvec![];
compute_alias_components_recursive(self.cx, alias_ty, &mut subcomponents);
self.out.push(Component::EscapingAlias(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) => {
self.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.
ty::Bool
| ty::Char
| ty::Int(_)
| ty::Uint(_)
| ty::Float(_)
| ty::Str
| ty::Never
| ty::Error(_) => {
// Trivial
}
ty::Bound(_, _) => {
// FIXME: Bound vars matter here!
}
ty::Adt(_, _)
| ty::Foreign(_)
| ty::Array(_, _)
| ty::Pat(_, _)
| ty::Slice(_)
| ty::RawPtr(_, _)
| ty::Ref(_, _, _)
| ty::FnPtr(..)
| ty::UnsafeBinder(_)
| ty::Dynamic(_, _)
| ty::Tuple(_) => {
ty.super_visit_with(self);
}
}
}
fn visit_region(&mut self, lt: I::Region) -> Self::Result {
if !lt.is_bound() {
self.out.push(Component::Region(lt));
}
}
}
/// Collect [Component]s for *all* the args of `alias_ty`.
///
/// This should not be used to get the components of `alias_ty` itself.
/// Use [push_outlives_components] instead.
pub fn compute_alias_components_recursive<I: Interner>(
cx: I,
alias_ty: ty::AliasTy<I>,
out: &mut SmallVec<[Component<I>; 4]>,
) {
let opt_variances = cx.opt_alias_variances(alias_ty.kind);
let mut visitor = OutlivesCollector { cx, out, visited: Default::default() };
for (index, child) in alias_ty.args.iter().enumerate() {
if opt_variances.and_then(|variances| variances.get(index)) == Some(ty::Bivariant) {
continue;
}
child.visit_with(&mut visitor);
}
}