]>
Commit | Line | Data |
---|---|---|
74b04a01 | 1 | use smallvec::smallvec; |
dc9dc135 | 2 | |
c295e0f8 | 3 | use crate::infer::outlives::components::{push_outlives_components, Component}; |
353b0b11 | 4 | use crate::traits::{self, Obligation, PredicateObligation}; |
6a06907d | 5 | use rustc_data_structures::fx::{FxHashSet, FxIndexSet}; |
a2a8927a | 6 | use rustc_middle::ty::{self, ToPredicate, TyCtxt}; |
6a06907d | 7 | use rustc_span::symbol::Ident; |
3c0e092e | 8 | use rustc_span::Span; |
1a4d82fc | 9 | |
ba9703b0 XL |
10 | pub fn anonymize_predicate<'tcx>( |
11 | tcx: TyCtxt<'tcx>, | |
f9f354fc | 12 | pred: ty::Predicate<'tcx>, |
ba9703b0 | 13 | ) -> ty::Predicate<'tcx> { |
064997fb | 14 | let new = tcx.anonymize_bound_vars(pred.kind()); |
5869c6ff | 15 | tcx.reuse_or_mk_predicate(pred, new) |
a7813a04 XL |
16 | } |
17 | ||
94222f64 | 18 | pub struct PredicateSet<'tcx> { |
dc9dc135 | 19 | tcx: TyCtxt<'tcx>, |
476ff2be | 20 | set: FxHashSet<ty::Predicate<'tcx>>, |
85aaf69f SL |
21 | } |
22 | ||
a2a8927a | 23 | impl<'tcx> PredicateSet<'tcx> { |
94222f64 | 24 | pub fn new(tcx: TyCtxt<'tcx>) -> Self { |
74b04a01 | 25 | Self { tcx, set: Default::default() } |
85aaf69f SL |
26 | } |
27 | ||
94222f64 | 28 | pub fn insert(&mut self, pred: ty::Predicate<'tcx>) -> bool { |
85aaf69f SL |
29 | // We have to be careful here because we want |
30 | // | |
f035d41b | 31 | // for<'a> Foo<&'a i32> |
85aaf69f SL |
32 | // |
33 | // and | |
34 | // | |
f035d41b | 35 | // for<'b> Foo<&'b i32> |
85aaf69f SL |
36 | // |
37 | // to be considered equivalent. So normalize all late-bound | |
38 | // regions before we throw things into the underlying set. | |
a7813a04 | 39 | self.set.insert(anonymize_predicate(self.tcx, pred)) |
85aaf69f SL |
40 | } |
41 | } | |
42 | ||
a2a8927a | 43 | impl<'tcx> Extend<ty::Predicate<'tcx>> for PredicateSet<'tcx> { |
f9f354fc | 44 | fn extend<I: IntoIterator<Item = ty::Predicate<'tcx>>>(&mut self, iter: I) { |
dc9dc135 | 45 | for pred in iter { |
f9f354fc | 46 | self.insert(pred); |
dc9dc135 XL |
47 | } |
48 | } | |
f9f354fc XL |
49 | |
50 | fn extend_one(&mut self, pred: ty::Predicate<'tcx>) { | |
51 | self.insert(pred); | |
52 | } | |
53 | ||
54 | fn extend_reserve(&mut self, additional: usize) { | |
55 | Extend::<ty::Predicate<'tcx>>::extend_reserve(&mut self.set, additional); | |
56 | } | |
dc9dc135 XL |
57 | } |
58 | ||
1a4d82fc JJ |
59 | /////////////////////////////////////////////////////////////////////////// |
60 | // `Elaboration` iterator | |
61 | /////////////////////////////////////////////////////////////////////////// | |
62 | ||
63 | /// "Elaboration" is the process of identifying all the predicates that | |
60c5eb7d | 64 | /// are implied by a source predicate. Currently, this basically means |
dc9dc135 XL |
65 | /// walking the "supertraits" and other similar assumptions. For example, |
66 | /// if we know that `T: Ord`, the elaborator would deduce that `T: PartialOrd` | |
67 | /// holds as well. Similarly, if we have `trait Foo: 'static`, and we know that | |
68 | /// `T: Foo`, then we know that `T: 'static`. | |
353b0b11 FG |
69 | pub struct Elaborator<'tcx, O> { |
70 | stack: Vec<O>, | |
dc9dc135 | 71 | visited: PredicateSet<'tcx>, |
353b0b11 | 72 | only_self: bool, |
1a4d82fc JJ |
73 | } |
74 | ||
353b0b11 FG |
75 | /// Describes how to elaborate an obligation into a sub-obligation. |
76 | /// | |
77 | /// For [`Obligation`], a sub-obligation is combined with the current obligation's | |
78 | /// param-env and cause code. For [`ty::Predicate`], none of this is needed, since | |
79 | /// there is no param-env or cause code to copy over. | |
80 | pub trait Elaboratable<'tcx> { | |
81 | fn predicate(&self) -> ty::Predicate<'tcx>; | |
82 | ||
83 | // Makes a new `Self` but with a different predicate. | |
84 | fn child(&self, predicate: ty::Predicate<'tcx>) -> Self; | |
85 | ||
86 | // Makes a new `Self` but with a different predicate and a different cause | |
87 | // code (if `Self` has one). | |
88 | fn child_with_derived_cause( | |
89 | &self, | |
90 | predicate: ty::Predicate<'tcx>, | |
91 | span: Span, | |
92 | parent_trait_pred: ty::PolyTraitPredicate<'tcx>, | |
93 | index: usize, | |
94 | ) -> Self; | |
1a4d82fc JJ |
95 | } |
96 | ||
353b0b11 FG |
97 | impl<'tcx> Elaboratable<'tcx> for PredicateObligation<'tcx> { |
98 | fn predicate(&self) -> ty::Predicate<'tcx> { | |
99 | self.predicate | |
100 | } | |
101 | ||
102 | fn child(&self, predicate: ty::Predicate<'tcx>) -> Self { | |
103 | Obligation { | |
104 | cause: self.cause.clone(), | |
105 | param_env: self.param_env, | |
106 | recursion_depth: 0, | |
107 | predicate, | |
108 | } | |
109 | } | |
110 | ||
111 | fn child_with_derived_cause( | |
112 | &self, | |
113 | predicate: ty::Predicate<'tcx>, | |
114 | span: Span, | |
115 | parent_trait_pred: ty::PolyTraitPredicate<'tcx>, | |
116 | index: usize, | |
117 | ) -> Self { | |
118 | let cause = self.cause.clone().derived_cause(parent_trait_pred, |derived| { | |
119 | traits::ImplDerivedObligation(Box::new(traits::ImplDerivedObligationCause { | |
120 | derived, | |
121 | impl_or_alias_def_id: parent_trait_pred.def_id(), | |
122 | impl_def_predicate_index: Some(index), | |
123 | span, | |
124 | })) | |
125 | }); | |
126 | Obligation { cause, param_env: self.param_env, recursion_depth: 0, predicate } | |
127 | } | |
1a4d82fc JJ |
128 | } |
129 | ||
353b0b11 FG |
130 | impl<'tcx> Elaboratable<'tcx> for ty::Predicate<'tcx> { |
131 | fn predicate(&self) -> ty::Predicate<'tcx> { | |
132 | *self | |
133 | } | |
134 | ||
135 | fn child(&self, predicate: ty::Predicate<'tcx>) -> Self { | |
136 | predicate | |
137 | } | |
138 | ||
139 | fn child_with_derived_cause( | |
140 | &self, | |
141 | predicate: ty::Predicate<'tcx>, | |
142 | _span: Span, | |
143 | _parent_trait_pred: ty::PolyTraitPredicate<'tcx>, | |
144 | _index: usize, | |
145 | ) -> Self { | |
146 | predicate | |
147 | } | |
3c0e092e XL |
148 | } |
149 | ||
353b0b11 FG |
150 | impl<'tcx> Elaboratable<'tcx> for (ty::Predicate<'tcx>, Span) { |
151 | fn predicate(&self) -> ty::Predicate<'tcx> { | |
152 | self.0 | |
153 | } | |
154 | ||
155 | fn child(&self, predicate: ty::Predicate<'tcx>) -> Self { | |
156 | (predicate, self.1) | |
157 | } | |
158 | ||
159 | fn child_with_derived_cause( | |
160 | &self, | |
161 | predicate: ty::Predicate<'tcx>, | |
162 | _span: Span, | |
163 | _parent_trait_pred: ty::PolyTraitPredicate<'tcx>, | |
164 | _index: usize, | |
165 | ) -> Self { | |
166 | (predicate, self.1) | |
167 | } | |
ba9703b0 XL |
168 | } |
169 | ||
353b0b11 | 170 | pub fn elaborate<'tcx, O: Elaboratable<'tcx>>( |
ba9703b0 | 171 | tcx: TyCtxt<'tcx>, |
353b0b11 FG |
172 | obligations: impl IntoIterator<Item = O>, |
173 | ) -> Elaborator<'tcx, O> { | |
174 | let mut elaborator = | |
175 | Elaborator { stack: Vec::new(), visited: PredicateSet::new(tcx), only_self: false }; | |
9ffffee4 FG |
176 | elaborator.extend_deduped(obligations); |
177 | elaborator | |
ba9703b0 XL |
178 | } |
179 | ||
353b0b11 FG |
180 | impl<'tcx, O: Elaboratable<'tcx>> Elaborator<'tcx, O> { |
181 | fn extend_deduped(&mut self, obligations: impl IntoIterator<Item = O>) { | |
9ffffee4 FG |
182 | // Only keep those bounds that we haven't already seen. |
183 | // This is necessary to prevent infinite recursion in some | |
184 | // cases. One common case is when people define | |
185 | // `trait Sized: Sized { }` rather than `trait Sized { }`. | |
186 | // let visited = &mut self.visited; | |
353b0b11 | 187 | self.stack.extend(obligations.into_iter().filter(|o| self.visited.insert(o.predicate()))); |
9ffffee4 FG |
188 | } |
189 | ||
353b0b11 FG |
190 | /// Filter to only the supertraits of trait predicates, i.e. only the predicates |
191 | /// that have `Self` as their self type, instead of all implied predicates. | |
192 | pub fn filter_only_self(mut self) -> Self { | |
193 | self.only_self = true; | |
194 | self | |
1a4d82fc JJ |
195 | } |
196 | ||
353b0b11 | 197 | fn elaborate(&mut self, elaboratable: &O) { |
a7813a04 | 198 | let tcx = self.visited.tcx; |
3dfed10e | 199 | |
353b0b11 | 200 | let bound_predicate = elaboratable.predicate().kind(); |
29967ef6 | 201 | match bound_predicate.skip_binder() { |
487cf647 | 202 | ty::PredicateKind::Clause(ty::Clause::Trait(data)) => { |
49aad941 FG |
203 | // Negative trait bounds do not imply any supertrait bounds |
204 | if data.polarity == ty::ImplPolarity::Negative { | |
205 | return; | |
206 | } | |
353b0b11 FG |
207 | // Get predicates implied by the trait, or only super predicates if we only care about self predicates. |
208 | let predicates = if self.only_self { | |
209 | tcx.super_predicates_of(data.def_id()) | |
210 | } else { | |
211 | tcx.implied_predicates_of(data.def_id()) | |
212 | }; | |
c34b1796 | 213 | |
9ffffee4 FG |
214 | let obligations = |
215 | predicates.predicates.iter().enumerate().map(|(index, &(mut pred, span))| { | |
216 | // when parent predicate is non-const, elaborate it to non-const predicates. | |
217 | if data.constness == ty::BoundConstness::NotConst { | |
218 | pred = pred.without_const(tcx); | |
219 | } | |
353b0b11 | 220 | elaboratable.child_with_derived_cause( |
9ffffee4 | 221 | pred.subst_supertrait(tcx, &bound_predicate.rebind(data.trait_ref)), |
353b0b11 FG |
222 | span, |
223 | bound_predicate.rebind(data), | |
224 | index, | |
9ffffee4 FG |
225 | ) |
226 | }); | |
5099ac24 | 227 | debug!(?data, ?obligations, "super_predicates"); |
9ffffee4 | 228 | self.extend_deduped(obligations); |
1a4d82fc | 229 | } |
5869c6ff | 230 | ty::PredicateKind::WellFormed(..) => { |
e9174d1e SL |
231 | // Currently, we do not elaborate WF predicates, |
232 | // although we easily could. | |
233 | } | |
5869c6ff | 234 | ty::PredicateKind::ObjectSafe(..) => { |
e9174d1e SL |
235 | // Currently, we do not elaborate object-safe |
236 | // predicates. | |
237 | } | |
5869c6ff | 238 | ty::PredicateKind::Subtype(..) => { |
dc9dc135 XL |
239 | // Currently, we do not "elaborate" predicates like `X <: Y`, |
240 | // though conceivably we might. | |
cc61c64b | 241 | } |
94222f64 XL |
242 | ty::PredicateKind::Coerce(..) => { |
243 | // Currently, we do not "elaborate" predicates like `X -> Y`, | |
244 | // though conceivably we might. | |
245 | } | |
487cf647 | 246 | ty::PredicateKind::Clause(ty::Clause::Projection(..)) => { |
1a4d82fc JJ |
247 | // Nothing to elaborate in a projection predicate. |
248 | } | |
5869c6ff | 249 | ty::PredicateKind::ClosureKind(..) => { |
a7813a04 XL |
250 | // Nothing to elaborate when waiting for a closure's kind to be inferred. |
251 | } | |
5869c6ff | 252 | ty::PredicateKind::ConstEvaluatable(..) => { |
ea8adc8c XL |
253 | // Currently, we do not elaborate const-evaluatable |
254 | // predicates. | |
255 | } | |
5869c6ff | 256 | ty::PredicateKind::ConstEquate(..) => { |
f9f354fc XL |
257 | // Currently, we do not elaborate const-equate |
258 | // predicates. | |
259 | } | |
487cf647 | 260 | ty::PredicateKind::Clause(ty::Clause::RegionOutlives(..)) => { |
c30ab7b3 SL |
261 | // Nothing to elaborate from `'a: 'b`. |
262 | } | |
487cf647 FG |
263 | ty::PredicateKind::Clause(ty::Clause::TypeOutlives(ty::OutlivesPredicate( |
264 | ty_max, | |
265 | r_min, | |
266 | ))) => { | |
c30ab7b3 SL |
267 | // We know that `T: 'a` for some type `T`. We can |
268 | // often elaborate this. For example, if we know that | |
269 | // `[U]: 'a`, that implies that `U: 'a`. Similarly, if | |
270 | // we know `&'a U: 'b`, then we know that `'a: 'b` and | |
271 | // `U: 'b`. | |
1a4d82fc | 272 | // |
c30ab7b3 SL |
273 | // We can basically ignore bound regions here. So for |
274 | // example `for<'c> Foo<'a,'c>: 'b` can be elaborated to | |
275 | // `'a: 'b`. | |
276 | ||
277 | // Ignore `for<'a> T: 'a` -- we might in the future | |
278 | // consider this as evidence that `T: 'static`, but | |
279 | // I'm a bit wary of such constructions and so for now | |
280 | // I want to be conservative. --nmatsakis | |
7cac9316 | 281 | if r_min.is_late_bound() { |
c30ab7b3 SL |
282 | return; |
283 | } | |
284 | ||
a1dfa0c6 | 285 | let mut components = smallvec![]; |
c295e0f8 | 286 | push_outlives_components(tcx, ty_max, &mut components); |
9ffffee4 | 287 | self.extend_deduped( |
a1dfa0c6 | 288 | components |
dc9dc135 XL |
289 | .into_iter() |
290 | .filter_map(|component| match component { | |
dfeec247 XL |
291 | Component::Region(r) => { |
292 | if r.is_late_bound() { | |
293 | None | |
294 | } else { | |
487cf647 FG |
295 | Some(ty::PredicateKind::Clause(ty::Clause::RegionOutlives( |
296 | ty::OutlivesPredicate(r, r_min), | |
dfeec247 XL |
297 | ))) |
298 | } | |
dc9dc135 XL |
299 | } |
300 | ||
301 | Component::Param(p) => { | |
302 | let ty = tcx.mk_ty_param(p.index, p.name); | |
487cf647 FG |
303 | Some(ty::PredicateKind::Clause(ty::Clause::TypeOutlives( |
304 | ty::OutlivesPredicate(ty, r_min), | |
dfeec247 | 305 | ))) |
dc9dc135 XL |
306 | } |
307 | ||
dfeec247 | 308 | Component::UnresolvedInferenceVariable(_) => None, |
dc9dc135 | 309 | |
9c376795 | 310 | Component::Alias(alias_ty) => { |
5099ac24 FG |
311 | // We might end up here if we have `Foo<<Bar as Baz>::Assoc>: 'a`. |
312 | // With this, we can deduce that `<Bar as Baz>::Assoc: 'a`. | |
487cf647 | 313 | Some(ty::PredicateKind::Clause(ty::Clause::TypeOutlives( |
9c376795 | 314 | ty::OutlivesPredicate(alias_ty.to_ty(tcx), r_min), |
5099ac24 FG |
315 | ))) |
316 | } | |
317 | ||
9c376795 | 318 | Component::EscapingAlias(_) => { |
5099ac24 FG |
319 | // We might be able to do more here, but we don't |
320 | // want to deal with escaping vars right now. | |
dc9dc135 XL |
321 | None |
322 | } | |
323 | }) | |
2b03887a FG |
324 | .map(|predicate_kind| { |
325 | bound_predicate.rebind(predicate_kind).to_predicate(tcx) | |
326 | }) | |
353b0b11 | 327 | .map(|predicate| elaboratable.child(predicate)), |
dc9dc135 | 328 | ); |
1a4d82fc | 329 | } |
5869c6ff | 330 | ty::PredicateKind::TypeWellFormedFromEnv(..) => { |
1b1a35ee XL |
331 | // Nothing to elaborate |
332 | } | |
487cf647 | 333 | ty::PredicateKind::Ambiguous => {} |
353b0b11 | 334 | ty::PredicateKind::AliasRelate(..) => { |
9ffffee4 FG |
335 | // No |
336 | } | |
337 | ty::PredicateKind::Clause(ty::Clause::ConstArgHasType(..)) => { | |
338 | // Nothing to elaborate | |
339 | } | |
1a4d82fc JJ |
340 | } |
341 | } | |
342 | } | |
343 | ||
353b0b11 FG |
344 | impl<'tcx, O: Elaboratable<'tcx>> Iterator for Elaborator<'tcx, O> { |
345 | type Item = O; | |
1a4d82fc | 346 | |
b7449926 XL |
347 | fn size_hint(&self) -> (usize, Option<usize>) { |
348 | (self.stack.len(), None) | |
349 | } | |
350 | ||
ba9703b0 | 351 | fn next(&mut self) -> Option<Self::Item> { |
c34b1796 | 352 | // Extract next item from top-most stack frame, if any. |
ba9703b0 XL |
353 | if let Some(obligation) = self.stack.pop() { |
354 | self.elaborate(&obligation); | |
355 | Some(obligation) | |
dc9dc135 XL |
356 | } else { |
357 | None | |
358 | } | |
1a4d82fc JJ |
359 | } |
360 | } | |
361 | ||
362 | /////////////////////////////////////////////////////////////////////////// | |
363 | // Supertrait iterator | |
364 | /////////////////////////////////////////////////////////////////////////// | |
365 | ||
dc9dc135 XL |
366 | pub fn supertraits<'tcx>( |
367 | tcx: TyCtxt<'tcx>, | |
368 | trait_ref: ty::PolyTraitRef<'tcx>, | |
353b0b11 FG |
369 | ) -> impl Iterator<Item = ty::PolyTraitRef<'tcx>> { |
370 | elaborate(tcx, [trait_ref.to_predicate(tcx)]).filter_only_self().filter_to_traits() | |
1a4d82fc JJ |
371 | } |
372 | ||
dc9dc135 XL |
373 | pub fn transitive_bounds<'tcx>( |
374 | tcx: TyCtxt<'tcx>, | |
353b0b11 FG |
375 | trait_refs: impl Iterator<Item = ty::PolyTraitRef<'tcx>>, |
376 | ) -> impl Iterator<Item = ty::PolyTraitRef<'tcx>> { | |
377 | elaborate(tcx, trait_refs.map(|trait_ref| trait_ref.to_predicate(tcx))) | |
378 | .filter_only_self() | |
379 | .filter_to_traits() | |
1a4d82fc JJ |
380 | } |
381 | ||
353b0b11 | 382 | /// A specialized variant of `elaborate` that only elaborates trait references that may |
49aad941 FG |
383 | /// define the given associated item with the name `assoc_name`. It uses the |
384 | /// `super_predicates_that_define_assoc_item` query to avoid enumerating super-predicates that | |
9c376795 | 385 | /// aren't related to `assoc_item`. This is used when resolving types like `Self::Item` or |
6a06907d | 386 | /// `T::Item` and helps to avoid cycle errors (see e.g. #35237). |
49aad941 | 387 | pub fn transitive_bounds_that_define_assoc_item<'tcx>( |
6a06907d XL |
388 | tcx: TyCtxt<'tcx>, |
389 | bounds: impl Iterator<Item = ty::PolyTraitRef<'tcx>>, | |
390 | assoc_name: Ident, | |
391 | ) -> impl Iterator<Item = ty::PolyTraitRef<'tcx>> { | |
392 | let mut stack: Vec<_> = bounds.collect(); | |
393 | let mut visited = FxIndexSet::default(); | |
394 | ||
395 | std::iter::from_fn(move || { | |
396 | while let Some(trait_ref) = stack.pop() { | |
064997fb | 397 | let anon_trait_ref = tcx.anonymize_bound_vars(trait_ref); |
6a06907d | 398 | if visited.insert(anon_trait_ref) { |
353b0b11 | 399 | let super_predicates = |
49aad941 | 400 | tcx.super_predicates_that_define_assoc_item((trait_ref.def_id(), assoc_name)); |
6a06907d | 401 | for (super_predicate, _) in super_predicates.predicates { |
cdc7bbd5 | 402 | let subst_predicate = super_predicate.subst_supertrait(tcx, &trait_ref); |
a2a8927a XL |
403 | if let Some(binder) = subst_predicate.to_opt_poly_trait_pred() { |
404 | stack.push(binder.map_bound(|t| t.trait_ref)); | |
6a06907d XL |
405 | } |
406 | } | |
407 | ||
408 | return Some(trait_ref); | |
409 | } | |
410 | } | |
411 | ||
412 | return None; | |
413 | }) | |
414 | } | |
415 | ||
c34b1796 AL |
416 | /////////////////////////////////////////////////////////////////////////// |
417 | // Other | |
418 | /////////////////////////////////////////////////////////////////////////// | |
419 | ||
353b0b11 FG |
420 | impl<'tcx> Elaborator<'tcx, ty::Predicate<'tcx>> { |
421 | fn filter_to_traits(self) -> FilterToTraits<Self> { | |
422 | FilterToTraits { base_iterator: self } | |
423 | } | |
424 | } | |
425 | ||
c34b1796 AL |
426 | /// A filter around an iterator of predicates that makes it yield up |
427 | /// just trait references. | |
428 | pub struct FilterToTraits<I> { | |
dfeec247 | 429 | base_iterator: I, |
c34b1796 AL |
430 | } |
431 | ||
353b0b11 | 432 | impl<'tcx, I: Iterator<Item = ty::Predicate<'tcx>>> Iterator for FilterToTraits<I> { |
1a4d82fc JJ |
433 | type Item = ty::PolyTraitRef<'tcx>; |
434 | ||
435 | fn next(&mut self) -> Option<ty::PolyTraitRef<'tcx>> { | |
353b0b11 FG |
436 | while let Some(pred) = self.base_iterator.next() { |
437 | if let Some(data) = pred.to_opt_poly_trait_pred() { | |
a2a8927a | 438 | return Some(data.map_bound(|t| t.trait_ref)); |
1a4d82fc JJ |
439 | } |
440 | } | |
dc9dc135 | 441 | None |
1a4d82fc | 442 | } |
0531ce1d XL |
443 | |
444 | fn size_hint(&self) -> (usize, Option<usize>) { | |
445 | let (_, upper) = self.base_iterator.size_hint(); | |
446 | (0, upper) | |
447 | } | |
1a4d82fc | 448 | } |