]>
Commit | Line | Data |
---|---|---|
dc9dc135 XL |
1 | use errors::DiagnosticBuilder; |
2 | use smallvec::SmallVec; | |
3 | use syntax_pos::Span; | |
4 | ||
9fa01778 XL |
5 | use crate::hir; |
6 | use crate::hir::def_id::DefId; | |
9fa01778 XL |
7 | use crate::ty::{self, Ty, TyCtxt, ToPredicate, ToPolyTraitRef}; |
8 | use crate::ty::outlives::Component; | |
e74abb32 | 9 | use crate::ty::subst::{GenericArg, Subst, SubstsRef}; |
9fa01778 | 10 | use crate::util::nodemap::FxHashSet; |
1a4d82fc | 11 | |
54a0048b | 12 | use super::{Obligation, ObligationCause, PredicateObligation, SelectionContext, Normalized}; |
1a4d82fc | 13 | |
dc9dc135 | 14 | fn anonymize_predicate<'tcx>(tcx: TyCtxt<'tcx>, pred: &ty::Predicate<'tcx>) -> ty::Predicate<'tcx> { |
a7813a04 XL |
15 | match *pred { |
16 | ty::Predicate::Trait(ref data) => | |
17 | ty::Predicate::Trait(tcx.anonymize_late_bound_regions(data)), | |
18 | ||
a7813a04 XL |
19 | ty::Predicate::RegionOutlives(ref data) => |
20 | ty::Predicate::RegionOutlives(tcx.anonymize_late_bound_regions(data)), | |
21 | ||
22 | ty::Predicate::TypeOutlives(ref data) => | |
23 | ty::Predicate::TypeOutlives(tcx.anonymize_late_bound_regions(data)), | |
24 | ||
25 | ty::Predicate::Projection(ref data) => | |
26 | ty::Predicate::Projection(tcx.anonymize_late_bound_regions(data)), | |
27 | ||
28 | ty::Predicate::WellFormed(data) => | |
29 | ty::Predicate::WellFormed(data), | |
30 | ||
31 | ty::Predicate::ObjectSafe(data) => | |
32 | ty::Predicate::ObjectSafe(data), | |
33 | ||
ff7c6d11 XL |
34 | ty::Predicate::ClosureKind(closure_def_id, closure_substs, kind) => |
35 | ty::Predicate::ClosureKind(closure_def_id, closure_substs, kind), | |
cc61c64b XL |
36 | |
37 | ty::Predicate::Subtype(ref data) => | |
38 | ty::Predicate::Subtype(tcx.anonymize_late_bound_regions(data)), | |
ea8adc8c XL |
39 | |
40 | ty::Predicate::ConstEvaluatable(def_id, substs) => | |
41 | ty::Predicate::ConstEvaluatable(def_id, substs), | |
a7813a04 XL |
42 | } |
43 | } | |
44 | ||
dc9dc135 XL |
45 | struct PredicateSet<'tcx> { |
46 | tcx: TyCtxt<'tcx>, | |
476ff2be | 47 | set: FxHashSet<ty::Predicate<'tcx>>, |
85aaf69f SL |
48 | } |
49 | ||
dc9dc135 XL |
50 | impl PredicateSet<'tcx> { |
51 | fn new(tcx: TyCtxt<'tcx>) -> Self { | |
52 | Self { tcx: tcx, set: Default::default() } | |
85aaf69f SL |
53 | } |
54 | ||
55 | fn insert(&mut self, pred: &ty::Predicate<'tcx>) -> bool { | |
56 | // We have to be careful here because we want | |
57 | // | |
58 | // for<'a> Foo<&'a int> | |
59 | // | |
60 | // and | |
61 | // | |
62 | // for<'b> Foo<&'b int> | |
63 | // | |
64 | // to be considered equivalent. So normalize all late-bound | |
65 | // regions before we throw things into the underlying set. | |
a7813a04 | 66 | self.set.insert(anonymize_predicate(self.tcx, pred)) |
85aaf69f SL |
67 | } |
68 | } | |
69 | ||
dc9dc135 XL |
70 | impl<T: AsRef<ty::Predicate<'tcx>>> Extend<T> for PredicateSet<'tcx> { |
71 | fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { | |
72 | for pred in iter { | |
73 | self.insert(pred.as_ref()); | |
74 | } | |
75 | } | |
76 | } | |
77 | ||
1a4d82fc JJ |
78 | /////////////////////////////////////////////////////////////////////////// |
79 | // `Elaboration` iterator | |
80 | /////////////////////////////////////////////////////////////////////////// | |
81 | ||
82 | /// "Elaboration" is the process of identifying all the predicates that | |
60c5eb7d | 83 | /// are implied by a source predicate. Currently, this basically means |
dc9dc135 XL |
84 | /// walking the "supertraits" and other similar assumptions. For example, |
85 | /// if we know that `T: Ord`, the elaborator would deduce that `T: PartialOrd` | |
86 | /// holds as well. Similarly, if we have `trait Foo: 'static`, and we know that | |
87 | /// `T: Foo`, then we know that `T: 'static`. | |
88 | pub struct Elaborator<'tcx> { | |
c34b1796 | 89 | stack: Vec<ty::Predicate<'tcx>>, |
dc9dc135 | 90 | visited: PredicateSet<'tcx>, |
1a4d82fc JJ |
91 | } |
92 | ||
dc9dc135 XL |
93 | pub fn elaborate_trait_ref<'tcx>( |
94 | tcx: TyCtxt<'tcx>, | |
95 | trait_ref: ty::PolyTraitRef<'tcx>, | |
96 | ) -> Elaborator<'tcx> { | |
c1a9b12d | 97 | elaborate_predicates(tcx, vec![trait_ref.to_predicate()]) |
1a4d82fc JJ |
98 | } |
99 | ||
dc9dc135 XL |
100 | pub fn elaborate_trait_refs<'tcx>( |
101 | tcx: TyCtxt<'tcx>, | |
102 | trait_refs: impl Iterator<Item = ty::PolyTraitRef<'tcx>>, | |
103 | ) -> Elaborator<'tcx> { | |
104 | let predicates = trait_refs.map(|trait_ref| trait_ref.to_predicate()).collect(); | |
1a4d82fc JJ |
105 | elaborate_predicates(tcx, predicates) |
106 | } | |
107 | ||
dc9dc135 XL |
108 | pub fn elaborate_predicates<'tcx>( |
109 | tcx: TyCtxt<'tcx>, | |
110 | mut predicates: Vec<ty::Predicate<'tcx>>, | |
111 | ) -> Elaborator<'tcx> { | |
85aaf69f SL |
112 | let mut visited = PredicateSet::new(tcx); |
113 | predicates.retain(|pred| visited.insert(pred)); | |
dc9dc135 | 114 | Elaborator { stack: predicates, visited } |
1a4d82fc JJ |
115 | } |
116 | ||
dc9dc135 | 117 | impl Elaborator<'tcx> { |
a7813a04 | 118 | pub fn filter_to_traits(self) -> FilterToTraits<Self> { |
c34b1796 | 119 | FilterToTraits::new(self) |
1a4d82fc JJ |
120 | } |
121 | ||
dc9dc135 | 122 | fn elaborate(&mut self, predicate: &ty::Predicate<'tcx>) { |
a7813a04 | 123 | let tcx = self.visited.tcx; |
1a4d82fc JJ |
124 | match *predicate { |
125 | ty::Predicate::Trait(ref data) => { | |
dc9dc135 | 126 | // Get predicates declared on the trait. |
7cac9316 | 127 | let predicates = tcx.super_predicates_of(data.def_id()); |
c34b1796 | 128 | |
dc9dc135 XL |
129 | let predicates = predicates.predicates |
130 | .iter() | |
131 | .map(|(pred, _)| pred.subst_supertrait(tcx, &data.to_poly_trait_ref())); | |
62682a34 | 132 | debug!("super_predicates: data={:?} predicates={:?}", |
dc9dc135 | 133 | data, predicates.clone()); |
1a4d82fc | 134 | |
dc9dc135 XL |
135 | // Only keep those bounds that we haven't already seen. |
136 | // This is necessary to prevent infinite recursion in some | |
137 | // cases. One common case is when people define | |
138 | // `trait Sized: Sized { }` rather than `trait Sized { }`. | |
139 | let visited = &mut self.visited; | |
140 | let predicates = predicates.filter(|pred| visited.insert(pred)); | |
1a4d82fc | 141 | |
62682a34 | 142 | self.stack.extend(predicates); |
1a4d82fc | 143 | } |
e9174d1e SL |
144 | ty::Predicate::WellFormed(..) => { |
145 | // Currently, we do not elaborate WF predicates, | |
146 | // although we easily could. | |
147 | } | |
148 | ty::Predicate::ObjectSafe(..) => { | |
149 | // Currently, we do not elaborate object-safe | |
150 | // predicates. | |
151 | } | |
cc61c64b | 152 | ty::Predicate::Subtype(..) => { |
dc9dc135 XL |
153 | // Currently, we do not "elaborate" predicates like `X <: Y`, |
154 | // though conceivably we might. | |
cc61c64b | 155 | } |
1a4d82fc JJ |
156 | ty::Predicate::Projection(..) => { |
157 | // Nothing to elaborate in a projection predicate. | |
158 | } | |
a7813a04 XL |
159 | ty::Predicate::ClosureKind(..) => { |
160 | // Nothing to elaborate when waiting for a closure's kind to be inferred. | |
161 | } | |
ea8adc8c XL |
162 | ty::Predicate::ConstEvaluatable(..) => { |
163 | // Currently, we do not elaborate const-evaluatable | |
164 | // predicates. | |
165 | } | |
c30ab7b3 SL |
166 | ty::Predicate::RegionOutlives(..) => { |
167 | // Nothing to elaborate from `'a: 'b`. | |
168 | } | |
c30ab7b3 SL |
169 | ty::Predicate::TypeOutlives(ref data) => { |
170 | // We know that `T: 'a` for some type `T`. We can | |
171 | // often elaborate this. For example, if we know that | |
172 | // `[U]: 'a`, that implies that `U: 'a`. Similarly, if | |
173 | // we know `&'a U: 'b`, then we know that `'a: 'b` and | |
174 | // `U: 'b`. | |
1a4d82fc | 175 | // |
c30ab7b3 SL |
176 | // We can basically ignore bound regions here. So for |
177 | // example `for<'c> Foo<'a,'c>: 'b` can be elaborated to | |
178 | // `'a: 'b`. | |
179 | ||
180 | // Ignore `for<'a> T: 'a` -- we might in the future | |
181 | // consider this as evidence that `T: 'static`, but | |
182 | // I'm a bit wary of such constructions and so for now | |
183 | // I want to be conservative. --nmatsakis | |
184 | let ty_max = data.skip_binder().0; | |
185 | let r_min = data.skip_binder().1; | |
7cac9316 | 186 | if r_min.is_late_bound() { |
c30ab7b3 SL |
187 | return; |
188 | } | |
189 | ||
190 | let visited = &mut self.visited; | |
a1dfa0c6 XL |
191 | let mut components = smallvec![]; |
192 | tcx.push_outlives_components(ty_max, &mut components); | |
c30ab7b3 | 193 | self.stack.extend( |
a1dfa0c6 | 194 | components |
dc9dc135 XL |
195 | .into_iter() |
196 | .filter_map(|component| match component { | |
197 | Component::Region(r) => if r.is_late_bound() { | |
198 | None | |
199 | } else { | |
200 | Some(ty::Predicate::RegionOutlives( | |
201 | ty::Binder::dummy(ty::OutlivesPredicate(r, r_min)))) | |
202 | } | |
203 | ||
204 | Component::Param(p) => { | |
205 | let ty = tcx.mk_ty_param(p.index, p.name); | |
206 | Some(ty::Predicate::TypeOutlives( | |
207 | ty::Binder::dummy(ty::OutlivesPredicate(ty, r_min)))) | |
208 | } | |
209 | ||
210 | Component::UnresolvedInferenceVariable(_) => { | |
211 | None | |
212 | } | |
213 | ||
214 | Component::Projection(_) | | |
215 | Component::EscapingProjection(_) => { | |
216 | // We can probably do more here. This | |
217 | // corresponds to a case like `<T as | |
218 | // Foo<'a>>::U: 'b`. | |
219 | None | |
220 | } | |
221 | }) | |
222 | .filter(|p| visited.insert(p)) | |
223 | ); | |
1a4d82fc JJ |
224 | } |
225 | } | |
226 | } | |
227 | } | |
228 | ||
dc9dc135 | 229 | impl Iterator for Elaborator<'tcx> { |
1a4d82fc JJ |
230 | type Item = ty::Predicate<'tcx>; |
231 | ||
b7449926 XL |
232 | fn size_hint(&self) -> (usize, Option<usize>) { |
233 | (self.stack.len(), None) | |
234 | } | |
235 | ||
1a4d82fc | 236 | fn next(&mut self) -> Option<ty::Predicate<'tcx>> { |
c34b1796 | 237 | // Extract next item from top-most stack frame, if any. |
dc9dc135 XL |
238 | if let Some(pred) = self.stack.pop() { |
239 | self.elaborate(&pred); | |
240 | Some(pred) | |
241 | } else { | |
242 | None | |
243 | } | |
1a4d82fc JJ |
244 | } |
245 | } | |
246 | ||
247 | /////////////////////////////////////////////////////////////////////////// | |
248 | // Supertrait iterator | |
249 | /////////////////////////////////////////////////////////////////////////// | |
250 | ||
dc9dc135 | 251 | pub type Supertraits<'tcx> = FilterToTraits<Elaborator<'tcx>>; |
1a4d82fc | 252 | |
dc9dc135 XL |
253 | pub fn supertraits<'tcx>( |
254 | tcx: TyCtxt<'tcx>, | |
255 | trait_ref: ty::PolyTraitRef<'tcx>, | |
256 | ) -> Supertraits<'tcx> { | |
1a4d82fc JJ |
257 | elaborate_trait_ref(tcx, trait_ref).filter_to_traits() |
258 | } | |
259 | ||
dc9dc135 XL |
260 | pub fn transitive_bounds<'tcx>( |
261 | tcx: TyCtxt<'tcx>, | |
262 | bounds: impl Iterator<Item = ty::PolyTraitRef<'tcx>>, | |
263 | ) -> Supertraits<'tcx> { | |
1a4d82fc JJ |
264 | elaborate_trait_refs(tcx, bounds).filter_to_traits() |
265 | } | |
266 | ||
c34b1796 | 267 | /////////////////////////////////////////////////////////////////////////// |
dc9dc135 XL |
268 | // `TraitAliasExpander` iterator |
269 | /////////////////////////////////////////////////////////////////////////// | |
270 | ||
271 | /// "Trait alias expansion" is the process of expanding a sequence of trait | |
272 | /// references into another sequence by transitively following all trait | |
273 | /// aliases. e.g. If you have bounds like `Foo + Send`, a trait alias | |
274 | /// `trait Foo = Bar + Sync;`, and another trait alias | |
275 | /// `trait Bar = Read + Write`, then the bounds would expand to | |
276 | /// `Read + Write + Sync + Send`. | |
277 | /// Expansion is done via a DFS (depth-first search), and the `visited` field | |
278 | /// is used to avoid cycles. | |
279 | pub struct TraitAliasExpander<'tcx> { | |
280 | tcx: TyCtxt<'tcx>, | |
281 | stack: Vec<TraitAliasExpansionInfo<'tcx>>, | |
282 | } | |
283 | ||
284 | /// Stores information about the expansion of a trait via a path of zero or more trait aliases. | |
285 | #[derive(Debug, Clone)] | |
286 | pub struct TraitAliasExpansionInfo<'tcx> { | |
287 | pub path: SmallVec<[(ty::PolyTraitRef<'tcx>, Span); 4]>, | |
288 | } | |
289 | ||
290 | impl<'tcx> TraitAliasExpansionInfo<'tcx> { | |
291 | fn new(trait_ref: ty::PolyTraitRef<'tcx>, span: Span) -> Self { | |
292 | Self { | |
293 | path: smallvec![(trait_ref, span)] | |
294 | } | |
295 | } | |
296 | ||
297 | /// Adds diagnostic labels to `diag` for the expansion path of a trait through all intermediate | |
298 | /// trait aliases. | |
299 | pub fn label_with_exp_info(&self, | |
300 | diag: &mut DiagnosticBuilder<'_>, | |
301 | top_label: &str, | |
302 | use_desc: &str | |
303 | ) { | |
304 | diag.span_label(self.top().1, top_label); | |
305 | if self.path.len() > 1 { | |
306 | for (_, sp) in self.path.iter().rev().skip(1).take(self.path.len() - 2) { | |
307 | diag.span_label(*sp, format!("referenced here ({})", use_desc)); | |
308 | } | |
309 | } | |
310 | diag.span_label(self.bottom().1, | |
311 | format!("trait alias used in trait object type ({})", use_desc)); | |
312 | } | |
313 | ||
314 | pub fn trait_ref(&self) -> &ty::PolyTraitRef<'tcx> { | |
315 | &self.top().0 | |
316 | } | |
317 | ||
318 | pub fn top(&self) -> &(ty::PolyTraitRef<'tcx>, Span) { | |
319 | self.path.last().unwrap() | |
320 | } | |
321 | ||
322 | pub fn bottom(&self) -> &(ty::PolyTraitRef<'tcx>, Span) { | |
323 | self.path.first().unwrap() | |
324 | } | |
c34b1796 | 325 | |
dc9dc135 XL |
326 | fn clone_and_push(&self, trait_ref: ty::PolyTraitRef<'tcx>, span: Span) -> Self { |
327 | let mut path = self.path.clone(); | |
328 | path.push((trait_ref, span)); | |
329 | ||
330 | Self { | |
331 | path | |
332 | } | |
333 | } | |
334 | } | |
335 | ||
336 | pub fn expand_trait_aliases<'tcx>( | |
337 | tcx: TyCtxt<'tcx>, | |
338 | trait_refs: impl IntoIterator<Item = (ty::PolyTraitRef<'tcx>, Span)>, | |
339 | ) -> TraitAliasExpander<'tcx> { | |
340 | let items: Vec<_> = trait_refs | |
341 | .into_iter() | |
342 | .map(|(trait_ref, span)| TraitAliasExpansionInfo::new(trait_ref, span)) | |
343 | .collect(); | |
344 | TraitAliasExpander { tcx, stack: items } | |
345 | } | |
346 | ||
347 | impl<'tcx> TraitAliasExpander<'tcx> { | |
348 | /// If `item` is a trait alias and its predicate has not yet been visited, then expands `item` | |
349 | /// to the definition, pushes the resulting expansion onto `self.stack`, and returns `false`. | |
350 | /// Otherwise, immediately returns `true` if `item` is a regular trait, or `false` if it is a | |
351 | /// trait alias. | |
352 | /// The return value indicates whether `item` should be yielded to the user. | |
353 | fn expand(&mut self, item: &TraitAliasExpansionInfo<'tcx>) -> bool { | |
354 | let tcx = self.tcx; | |
355 | let trait_ref = item.trait_ref(); | |
356 | let pred = trait_ref.to_predicate(); | |
357 | ||
358 | debug!("expand_trait_aliases: trait_ref={:?}", trait_ref); | |
359 | ||
360 | // Don't recurse if this bound is not a trait alias. | |
361 | let is_alias = tcx.is_trait_alias(trait_ref.def_id()); | |
362 | if !is_alias { | |
363 | return true; | |
364 | } | |
365 | ||
366 | // Don't recurse if this trait alias is already on the stack for the DFS search. | |
367 | let anon_pred = anonymize_predicate(tcx, &pred); | |
368 | if item.path.iter().rev().skip(1) | |
369 | .any(|(tr, _)| anonymize_predicate(tcx, &tr.to_predicate()) == anon_pred) { | |
370 | return false; | |
371 | } | |
372 | ||
373 | // Get components of trait alias. | |
374 | let predicates = tcx.super_predicates_of(trait_ref.def_id()); | |
375 | ||
376 | let items = predicates.predicates | |
377 | .iter() | |
378 | .rev() | |
379 | .filter_map(|(pred, span)| { | |
380 | pred.subst_supertrait(tcx, &trait_ref) | |
381 | .to_opt_poly_trait_ref() | |
382 | .map(|trait_ref| item.clone_and_push(trait_ref, *span)) | |
383 | }); | |
384 | debug!("expand_trait_aliases: items={:?}", items.clone()); | |
385 | ||
386 | self.stack.extend(items); | |
387 | ||
388 | false | |
389 | } | |
390 | } | |
391 | ||
392 | impl<'tcx> Iterator for TraitAliasExpander<'tcx> { | |
393 | type Item = TraitAliasExpansionInfo<'tcx>; | |
394 | ||
395 | fn size_hint(&self) -> (usize, Option<usize>) { | |
396 | (self.stack.len(), None) | |
397 | } | |
398 | ||
399 | fn next(&mut self) -> Option<TraitAliasExpansionInfo<'tcx>> { | |
400 | while let Some(item) = self.stack.pop() { | |
401 | if self.expand(&item) { | |
402 | return Some(item); | |
403 | } | |
404 | } | |
405 | None | |
406 | } | |
407 | } | |
408 | ||
409 | /////////////////////////////////////////////////////////////////////////// | |
410 | // Iterator over def-IDs of supertraits | |
411 | /////////////////////////////////////////////////////////////////////////// | |
412 | ||
413 | pub struct SupertraitDefIds<'tcx> { | |
414 | tcx: TyCtxt<'tcx>, | |
e9174d1e | 415 | stack: Vec<DefId>, |
476ff2be | 416 | visited: FxHashSet<DefId>, |
c34b1796 AL |
417 | } |
418 | ||
416331ca | 419 | pub fn supertrait_def_ids(tcx: TyCtxt<'_>, trait_def_id: DefId) -> SupertraitDefIds<'_> { |
c34b1796 | 420 | SupertraitDefIds { |
041b39d2 | 421 | tcx, |
c34b1796 AL |
422 | stack: vec![trait_def_id], |
423 | visited: Some(trait_def_id).into_iter().collect(), | |
424 | } | |
425 | } | |
426 | ||
dc9dc135 | 427 | impl Iterator for SupertraitDefIds<'tcx> { |
e9174d1e | 428 | type Item = DefId; |
c34b1796 | 429 | |
e9174d1e | 430 | fn next(&mut self) -> Option<DefId> { |
532ac7d7 | 431 | let def_id = self.stack.pop()?; |
7cac9316 | 432 | let predicates = self.tcx.super_predicates_of(def_id); |
c34b1796 AL |
433 | let visited = &mut self.visited; |
434 | self.stack.extend( | |
435 | predicates.predicates | |
436 | .iter() | |
dc9dc135 XL |
437 | .filter_map(|(pred, _)| pred.to_opt_poly_trait_ref()) |
438 | .map(|trait_ref| trait_ref.def_id()) | |
c34b1796 AL |
439 | .filter(|&super_def_id| visited.insert(super_def_id))); |
440 | Some(def_id) | |
441 | } | |
442 | } | |
443 | ||
444 | /////////////////////////////////////////////////////////////////////////// | |
445 | // Other | |
446 | /////////////////////////////////////////////////////////////////////////// | |
447 | ||
448 | /// A filter around an iterator of predicates that makes it yield up | |
449 | /// just trait references. | |
450 | pub struct FilterToTraits<I> { | |
451 | base_iterator: I | |
452 | } | |
453 | ||
454 | impl<I> FilterToTraits<I> { | |
455 | fn new(base: I) -> FilterToTraits<I> { | |
456 | FilterToTraits { base_iterator: base } | |
457 | } | |
458 | } | |
459 | ||
a1dfa0c6 | 460 | impl<'tcx, I: Iterator<Item = ty::Predicate<'tcx>>> Iterator for FilterToTraits<I> { |
1a4d82fc JJ |
461 | type Item = ty::PolyTraitRef<'tcx>; |
462 | ||
463 | fn next(&mut self) -> Option<ty::PolyTraitRef<'tcx>> { | |
dc9dc135 XL |
464 | while let Some(pred) = self.base_iterator.next() { |
465 | if let ty::Predicate::Trait(data) = pred { | |
466 | return Some(data.to_poly_trait_ref()); | |
1a4d82fc JJ |
467 | } |
468 | } | |
dc9dc135 | 469 | None |
1a4d82fc | 470 | } |
0531ce1d XL |
471 | |
472 | fn size_hint(&self) -> (usize, Option<usize>) { | |
473 | let (_, upper) = self.base_iterator.size_hint(); | |
474 | (0, upper) | |
475 | } | |
1a4d82fc JJ |
476 | } |
477 | ||
478 | /////////////////////////////////////////////////////////////////////////// | |
479 | // Other | |
480 | /////////////////////////////////////////////////////////////////////////// | |
481 | ||
54a0048b SL |
482 | /// Instantiate all bound parameters of the impl with the given substs, |
483 | /// returning the resulting trait ref and all obligations that arise. | |
484 | /// The obligations are closed under normalization. | |
dc9dc135 XL |
485 | pub fn impl_trait_ref_and_oblig<'a, 'tcx>( |
486 | selcx: &mut SelectionContext<'a, 'tcx>, | |
487 | param_env: ty::ParamEnv<'tcx>, | |
488 | impl_def_id: DefId, | |
489 | impl_substs: SubstsRef<'tcx>, | |
490 | ) -> (ty::TraitRef<'tcx>, Vec<PredicateObligation<'tcx>>) { | |
54a0048b SL |
491 | let impl_trait_ref = |
492 | selcx.tcx().impl_trait_ref(impl_def_id).unwrap(); | |
493 | let impl_trait_ref = | |
494 | impl_trait_ref.subst(selcx.tcx(), impl_substs); | |
495 | let Normalized { value: impl_trait_ref, obligations: normalization_obligations1 } = | |
7cac9316 | 496 | super::normalize(selcx, param_env, ObligationCause::dummy(), &impl_trait_ref); |
54a0048b | 497 | |
7cac9316 | 498 | let predicates = selcx.tcx().predicates_of(impl_def_id); |
54a0048b SL |
499 | let predicates = predicates.instantiate(selcx.tcx(), impl_substs); |
500 | let Normalized { value: predicates, obligations: normalization_obligations2 } = | |
7cac9316 | 501 | super::normalize(selcx, param_env, ObligationCause::dummy(), &predicates); |
54a0048b | 502 | let impl_obligations = |
7cac9316 | 503 | predicates_for_generics(ObligationCause::dummy(), 0, param_env, &predicates); |
54a0048b SL |
504 | |
505 | let impl_obligations: Vec<_> = | |
506 | impl_obligations.into_iter() | |
507 | .chain(normalization_obligations1) | |
508 | .chain(normalization_obligations2) | |
509 | .collect(); | |
510 | ||
511 | (impl_trait_ref, impl_obligations) | |
512 | } | |
513 | ||
e1599b0c XL |
514 | /// See [`super::obligations_for_generics`]. |
515 | pub fn predicates_for_generics<'tcx>( | |
516 | cause: ObligationCause<'tcx>, | |
517 | recursion_depth: usize, | |
518 | param_env: ty::ParamEnv<'tcx>, | |
519 | generic_bounds: &ty::InstantiatedPredicates<'tcx>, | |
520 | ) -> Vec<PredicateObligation<'tcx>> { | |
521 | debug!("predicates_for_generics(generic_bounds={:?})", generic_bounds); | |
522 | ||
523 | generic_bounds.predicates.iter().map(|predicate| Obligation { | |
524 | cause: cause.clone(), | |
525 | recursion_depth, | |
526 | param_env, | |
527 | predicate: predicate.clone(), | |
62682a34 | 528 | }).collect() |
1a4d82fc JJ |
529 | } |
530 | ||
c34b1796 | 531 | pub fn predicate_for_trait_ref<'tcx>( |
1a4d82fc | 532 | cause: ObligationCause<'tcx>, |
7cac9316 | 533 | param_env: ty::ParamEnv<'tcx>, |
d9579d0f | 534 | trait_ref: ty::TraitRef<'tcx>, |
c34b1796 | 535 | recursion_depth: usize) |
d9579d0f | 536 | -> PredicateObligation<'tcx> |
1a4d82fc | 537 | { |
d9579d0f | 538 | Obligation { |
041b39d2 XL |
539 | cause, |
540 | param_env, | |
541 | recursion_depth, | |
c1a9b12d | 542 | predicate: trait_ref.to_predicate(), |
d9579d0f | 543 | } |
1a4d82fc JJ |
544 | } |
545 | ||
dc9dc135 | 546 | impl<'tcx> TyCtxt<'tcx> { |
a7813a04 | 547 | pub fn predicate_for_trait_def(self, |
7cac9316 XL |
548 | param_env: ty::ParamEnv<'tcx>, |
549 | cause: ObligationCause<'tcx>, | |
550 | trait_def_id: DefId, | |
551 | recursion_depth: usize, | |
94b46f34 | 552 | self_ty: Ty<'tcx>, |
e74abb32 | 553 | params: &[GenericArg<'tcx>]) |
a7813a04 XL |
554 | -> PredicateObligation<'tcx> |
555 | { | |
556 | let trait_ref = ty::TraitRef { | |
557 | def_id: trait_def_id, | |
94b46f34 | 558 | substs: self.mk_substs_trait(self_ty, params) |
a7813a04 | 559 | }; |
7cac9316 | 560 | predicate_for_trait_ref(cause, param_env, trait_ref, recursion_depth) |
1a4d82fc JJ |
561 | } |
562 | ||
e1599b0c | 563 | /// Casts a trait reference into a reference to one of its super |
a7813a04 XL |
564 | /// traits; returns `None` if `target_trait_def_id` is not a |
565 | /// supertrait. | |
566 | pub fn upcast_choices(self, | |
567 | source_trait_ref: ty::PolyTraitRef<'tcx>, | |
568 | target_trait_def_id: DefId) | |
569 | -> Vec<ty::PolyTraitRef<'tcx>> | |
570 | { | |
571 | if source_trait_ref.def_id() == target_trait_def_id { | |
e1599b0c | 572 | return vec![source_trait_ref]; // Shortcut the most common case. |
1a4d82fc | 573 | } |
a7813a04 XL |
574 | |
575 | supertraits(self, source_trait_ref) | |
576 | .filter(|r| r.def_id() == target_trait_def_id) | |
577 | .collect() | |
85aaf69f SL |
578 | } |
579 | ||
a7813a04 XL |
580 | /// Given a trait `trait_ref`, returns the number of vtable entries |
581 | /// that come from `trait_ref`, excluding its supertraits. Used in | |
582 | /// computing the vtable base for an upcast trait of a trait object. | |
583 | pub fn count_own_vtable_entries(self, trait_ref: ty::PolyTraitRef<'tcx>) -> usize { | |
584 | let mut entries = 0; | |
585 | // Count number of methods and add them to the total offset. | |
586 | // Skip over associated types and constants. | |
476ff2be | 587 | for trait_item in self.associated_items(trait_ref.def_id()) { |
dc9dc135 | 588 | if trait_item.kind == ty::AssocKind::Method { |
a7813a04 XL |
589 | entries += 1; |
590 | } | |
c1a9b12d | 591 | } |
a7813a04 XL |
592 | entries |
593 | } | |
594 | ||
595 | /// Given an upcast trait object described by `object`, returns the | |
596 | /// index of the method `method_def_id` (which should be part of | |
597 | /// `object.upcast_trait_ref`) within the vtable for `object`. | |
598 | pub fn get_vtable_index_of_object_method<N>(self, | |
599 | object: &super::VtableObjectData<'tcx, N>, | |
600 | method_def_id: DefId) -> usize { | |
601 | // Count number of methods preceding the one we are selecting and | |
602 | // add them to the total offset. | |
603 | // Skip over associated types and constants. | |
604 | let mut entries = object.vtable_base; | |
476ff2be SL |
605 | for trait_item in self.associated_items(object.upcast_trait_ref.def_id()) { |
606 | if trait_item.def_id == method_def_id { | |
a7813a04 | 607 | // The item with the ID we were given really ought to be a method. |
dc9dc135 | 608 | assert_eq!(trait_item.kind, ty::AssocKind::Method); |
a7813a04 XL |
609 | return entries; |
610 | } | |
dc9dc135 | 611 | if trait_item.kind == ty::AssocKind::Method { |
a7813a04 XL |
612 | entries += 1; |
613 | } | |
85aaf69f | 614 | } |
a7813a04 XL |
615 | |
616 | bug!("get_vtable_index_of_object_method: {:?} was not found", | |
617 | method_def_id); | |
85aaf69f SL |
618 | } |
619 | ||
a7813a04 XL |
620 | pub fn closure_trait_ref_and_return_type(self, |
621 | fn_trait_def_id: DefId, | |
622 | self_ty: Ty<'tcx>, | |
8bb4bdeb | 623 | sig: ty::PolyFnSig<'tcx>, |
a7813a04 XL |
624 | tuple_arguments: TupleArgumentsFlag) |
625 | -> ty::Binder<(ty::TraitRef<'tcx>, Ty<'tcx>)> | |
626 | { | |
627 | let arguments_tuple = match tuple_arguments { | |
476ff2be SL |
628 | TupleArgumentsFlag::No => sig.skip_binder().inputs()[0], |
629 | TupleArgumentsFlag::Yes => | |
0531ce1d | 630 | self.intern_tup(sig.skip_binder().inputs()), |
a7813a04 | 631 | }; |
a7813a04 XL |
632 | let trait_ref = ty::TraitRef { |
633 | def_id: fn_trait_def_id, | |
94b46f34 | 634 | substs: self.mk_substs_trait(self_ty, &[arguments_tuple.into()]), |
a7813a04 | 635 | }; |
83c7162d | 636 | ty::Binder::bind((trait_ref, sig.skip_binder().output())) |
a7813a04 | 637 | } |
7cac9316 | 638 | |
ea8adc8c XL |
639 | pub fn generator_trait_ref_and_outputs(self, |
640 | fn_trait_def_id: DefId, | |
641 | self_ty: Ty<'tcx>, | |
642 | sig: ty::PolyGenSig<'tcx>) | |
643 | -> ty::Binder<(ty::TraitRef<'tcx>, Ty<'tcx>, Ty<'tcx>)> | |
644 | { | |
645 | let trait_ref = ty::TraitRef { | |
646 | def_id: fn_trait_def_id, | |
647 | substs: self.mk_substs_trait(self_ty, &[]), | |
648 | }; | |
83c7162d | 649 | ty::Binder::bind((trait_ref, sig.skip_binder().yield_ty, sig.skip_binder().return_ty)) |
ea8adc8c XL |
650 | } |
651 | ||
7cac9316 | 652 | pub fn impl_is_default(self, node_item_def_id: DefId) -> bool { |
9fa01778 XL |
653 | match self.hir().as_local_hir_id(node_item_def_id) { |
654 | Some(hir_id) => { | |
dc9dc135 | 655 | let item = self.hir().expect_item(hir_id); |
e74abb32 | 656 | if let hir::ItemKind::Impl(_, _, defaultness, ..) = item.kind { |
7cac9316 XL |
657 | defaultness.is_default() |
658 | } else { | |
659 | false | |
660 | } | |
661 | } | |
662 | None => { | |
e74abb32 | 663 | self.impl_defaultness(node_item_def_id) |
7cac9316 XL |
664 | .is_default() |
665 | } | |
666 | } | |
667 | } | |
668 | ||
e74abb32 XL |
669 | pub fn impl_item_is_final(self, assoc_item: &ty::AssocItem) -> bool { |
670 | assoc_item.defaultness.is_final() && !self.impl_is_default(assoc_item.container.id()) | |
7cac9316 | 671 | } |
85aaf69f SL |
672 | } |
673 | ||
674 | pub enum TupleArgumentsFlag { Yes, No } |