]>
Commit | Line | Data |
---|---|---|
5e7ed085 | 1 | use rustc_errors::Diagnostic; |
ba9703b0 XL |
2 | use rustc_span::Span; |
3 | use smallvec::smallvec; | |
4 | use smallvec::SmallVec; | |
5 | ||
6 | use rustc_data_structures::fx::FxHashSet; | |
7 | use rustc_hir::def_id::DefId; | |
8 | use rustc_middle::ty::subst::{GenericArg, Subst, SubstsRef}; | |
04454e1e | 9 | use rustc_middle::ty::{self, EarlyBinder, ImplSubject, ToPredicate, Ty, TyCtxt, TypeFoldable}; |
ba9703b0 XL |
10 | |
11 | use super::{Normalized, Obligation, ObligationCause, PredicateObligation, SelectionContext}; | |
3c0e092e XL |
12 | pub use rustc_infer::traits::{self, util::*}; |
13 | ||
14 | use std::iter; | |
ba9703b0 XL |
15 | |
16 | /////////////////////////////////////////////////////////////////////////// | |
17 | // `TraitAliasExpander` iterator | |
18 | /////////////////////////////////////////////////////////////////////////// | |
19 | ||
20 | /// "Trait alias expansion" is the process of expanding a sequence of trait | |
21 | /// references into another sequence by transitively following all trait | |
22 | /// aliases. e.g. If you have bounds like `Foo + Send`, a trait alias | |
23 | /// `trait Foo = Bar + Sync;`, and another trait alias | |
24 | /// `trait Bar = Read + Write`, then the bounds would expand to | |
25 | /// `Read + Write + Sync + Send`. | |
26 | /// Expansion is done via a DFS (depth-first search), and the `visited` field | |
27 | /// is used to avoid cycles. | |
28 | pub struct TraitAliasExpander<'tcx> { | |
29 | tcx: TyCtxt<'tcx>, | |
30 | stack: Vec<TraitAliasExpansionInfo<'tcx>>, | |
31 | } | |
32 | ||
33 | /// Stores information about the expansion of a trait via a path of zero or more trait aliases. | |
34 | #[derive(Debug, Clone)] | |
35 | pub struct TraitAliasExpansionInfo<'tcx> { | |
36 | pub path: SmallVec<[(ty::PolyTraitRef<'tcx>, Span); 4]>, | |
37 | } | |
38 | ||
39 | impl<'tcx> TraitAliasExpansionInfo<'tcx> { | |
40 | fn new(trait_ref: ty::PolyTraitRef<'tcx>, span: Span) -> Self { | |
41 | Self { path: smallvec![(trait_ref, span)] } | |
42 | } | |
43 | ||
44 | /// Adds diagnostic labels to `diag` for the expansion path of a trait through all intermediate | |
45 | /// trait aliases. | |
5e7ed085 | 46 | pub fn label_with_exp_info(&self, diag: &mut Diagnostic, top_label: &str, use_desc: &str) { |
ba9703b0 XL |
47 | diag.span_label(self.top().1, top_label); |
48 | if self.path.len() > 1 { | |
49 | for (_, sp) in self.path.iter().rev().skip(1).take(self.path.len() - 2) { | |
50 | diag.span_label(*sp, format!("referenced here ({})", use_desc)); | |
51 | } | |
52 | } | |
3dfed10e XL |
53 | if self.top().1 != self.bottom().1 { |
54 | // When the trait object is in a return type these two spans match, we don't want | |
55 | // redundant labels. | |
56 | diag.span_label( | |
57 | self.bottom().1, | |
58 | format!("trait alias used in trait object type ({})", use_desc), | |
59 | ); | |
60 | } | |
ba9703b0 XL |
61 | } |
62 | ||
3dfed10e XL |
63 | pub fn trait_ref(&self) -> ty::PolyTraitRef<'tcx> { |
64 | self.top().0 | |
ba9703b0 XL |
65 | } |
66 | ||
67 | pub fn top(&self) -> &(ty::PolyTraitRef<'tcx>, Span) { | |
68 | self.path.last().unwrap() | |
69 | } | |
70 | ||
71 | pub fn bottom(&self) -> &(ty::PolyTraitRef<'tcx>, Span) { | |
72 | self.path.first().unwrap() | |
73 | } | |
74 | ||
75 | fn clone_and_push(&self, trait_ref: ty::PolyTraitRef<'tcx>, span: Span) -> Self { | |
76 | let mut path = self.path.clone(); | |
77 | path.push((trait_ref, span)); | |
78 | ||
79 | Self { path } | |
80 | } | |
81 | } | |
82 | ||
83 | pub fn expand_trait_aliases<'tcx>( | |
84 | tcx: TyCtxt<'tcx>, | |
85 | trait_refs: impl Iterator<Item = (ty::PolyTraitRef<'tcx>, Span)>, | |
86 | ) -> TraitAliasExpander<'tcx> { | |
87 | let items: Vec<_> = | |
88 | trait_refs.map(|(trait_ref, span)| TraitAliasExpansionInfo::new(trait_ref, span)).collect(); | |
89 | TraitAliasExpander { tcx, stack: items } | |
90 | } | |
91 | ||
92 | impl<'tcx> TraitAliasExpander<'tcx> { | |
93 | /// If `item` is a trait alias and its predicate has not yet been visited, then expands `item` | |
94 | /// to the definition, pushes the resulting expansion onto `self.stack`, and returns `false`. | |
95 | /// Otherwise, immediately returns `true` if `item` is a regular trait, or `false` if it is a | |
96 | /// trait alias. | |
97 | /// The return value indicates whether `item` should be yielded to the user. | |
98 | fn expand(&mut self, item: &TraitAliasExpansionInfo<'tcx>) -> bool { | |
99 | let tcx = self.tcx; | |
100 | let trait_ref = item.trait_ref(); | |
f9f354fc | 101 | let pred = trait_ref.without_const().to_predicate(tcx); |
ba9703b0 XL |
102 | |
103 | debug!("expand_trait_aliases: trait_ref={:?}", trait_ref); | |
104 | ||
105 | // Don't recurse if this bound is not a trait alias. | |
106 | let is_alias = tcx.is_trait_alias(trait_ref.def_id()); | |
107 | if !is_alias { | |
108 | return true; | |
109 | } | |
110 | ||
111 | // Don't recurse if this trait alias is already on the stack for the DFS search. | |
f9f354fc | 112 | let anon_pred = anonymize_predicate(tcx, pred); |
3dfed10e | 113 | if item.path.iter().rev().skip(1).any(|&(tr, _)| { |
f9f354fc | 114 | anonymize_predicate(tcx, tr.without_const().to_predicate(tcx)) == anon_pred |
ba9703b0 XL |
115 | }) { |
116 | return false; | |
117 | } | |
118 | ||
119 | // Get components of trait alias. | |
120 | let predicates = tcx.super_predicates_of(trait_ref.def_id()); | |
04454e1e | 121 | debug!(?predicates); |
ba9703b0 XL |
122 | |
123 | let items = predicates.predicates.iter().rev().filter_map(|(pred, span)| { | |
124 | pred.subst_supertrait(tcx, &trait_ref) | |
a2a8927a XL |
125 | .to_opt_poly_trait_pred() |
126 | .map(|trait_ref| item.clone_and_push(trait_ref.map_bound(|t| t.trait_ref), *span)) | |
ba9703b0 | 127 | }); |
04454e1e | 128 | debug!("expand_trait_aliases: items={:?}", items.clone().collect::<Vec<_>>()); |
ba9703b0 XL |
129 | |
130 | self.stack.extend(items); | |
131 | ||
132 | false | |
133 | } | |
134 | } | |
135 | ||
136 | impl<'tcx> Iterator for TraitAliasExpander<'tcx> { | |
137 | type Item = TraitAliasExpansionInfo<'tcx>; | |
138 | ||
139 | fn size_hint(&self) -> (usize, Option<usize>) { | |
140 | (self.stack.len(), None) | |
141 | } | |
142 | ||
143 | fn next(&mut self) -> Option<TraitAliasExpansionInfo<'tcx>> { | |
144 | while let Some(item) = self.stack.pop() { | |
145 | if self.expand(&item) { | |
146 | return Some(item); | |
147 | } | |
148 | } | |
149 | None | |
150 | } | |
151 | } | |
152 | ||
153 | /////////////////////////////////////////////////////////////////////////// | |
154 | // Iterator over def-IDs of supertraits | |
155 | /////////////////////////////////////////////////////////////////////////// | |
156 | ||
157 | pub struct SupertraitDefIds<'tcx> { | |
158 | tcx: TyCtxt<'tcx>, | |
159 | stack: Vec<DefId>, | |
160 | visited: FxHashSet<DefId>, | |
161 | } | |
162 | ||
163 | pub fn supertrait_def_ids(tcx: TyCtxt<'_>, trait_def_id: DefId) -> SupertraitDefIds<'_> { | |
164 | SupertraitDefIds { | |
165 | tcx, | |
166 | stack: vec![trait_def_id], | |
167 | visited: Some(trait_def_id).into_iter().collect(), | |
168 | } | |
169 | } | |
170 | ||
a2a8927a | 171 | impl Iterator for SupertraitDefIds<'_> { |
ba9703b0 XL |
172 | type Item = DefId; |
173 | ||
174 | fn next(&mut self) -> Option<DefId> { | |
175 | let def_id = self.stack.pop()?; | |
176 | let predicates = self.tcx.super_predicates_of(def_id); | |
177 | let visited = &mut self.visited; | |
178 | self.stack.extend( | |
179 | predicates | |
180 | .predicates | |
181 | .iter() | |
a2a8927a XL |
182 | .filter_map(|(pred, _)| pred.to_opt_poly_trait_pred()) |
183 | .map(|trait_ref| trait_ref.def_id()) | |
ba9703b0 XL |
184 | .filter(|&super_def_id| visited.insert(super_def_id)), |
185 | ); | |
186 | Some(def_id) | |
187 | } | |
188 | } | |
189 | ||
190 | /////////////////////////////////////////////////////////////////////////// | |
191 | // Other | |
192 | /////////////////////////////////////////////////////////////////////////// | |
193 | ||
5e7ed085 FG |
194 | /// Instantiate all bound parameters of the impl subject with the given substs, |
195 | /// returning the resulting subject and all obligations that arise. | |
ba9703b0 | 196 | /// The obligations are closed under normalization. |
5e7ed085 | 197 | pub fn impl_subject_and_oblig<'a, 'tcx>( |
ba9703b0 XL |
198 | selcx: &mut SelectionContext<'a, 'tcx>, |
199 | param_env: ty::ParamEnv<'tcx>, | |
200 | impl_def_id: DefId, | |
201 | impl_substs: SubstsRef<'tcx>, | |
5e7ed085 FG |
202 | ) -> (ImplSubject<'tcx>, impl Iterator<Item = PredicateObligation<'tcx>>) { |
203 | let subject = selcx.tcx().impl_subject(impl_def_id); | |
04454e1e | 204 | let subject = EarlyBinder(subject).subst(selcx.tcx(), impl_substs); |
5e7ed085 FG |
205 | let Normalized { value: subject, obligations: normalization_obligations1 } = |
206 | super::normalize(selcx, param_env, ObligationCause::dummy(), subject); | |
ba9703b0 XL |
207 | |
208 | let predicates = selcx.tcx().predicates_of(impl_def_id); | |
209 | let predicates = predicates.instantiate(selcx.tcx(), impl_substs); | |
210 | let Normalized { value: predicates, obligations: normalization_obligations2 } = | |
fc512014 | 211 | super::normalize(selcx, param_env, ObligationCause::dummy(), predicates); |
ba9703b0 XL |
212 | let impl_obligations = |
213 | predicates_for_generics(ObligationCause::dummy(), 0, param_env, predicates); | |
214 | ||
215 | let impl_obligations = impl_obligations | |
216 | .chain(normalization_obligations1.into_iter()) | |
217 | .chain(normalization_obligations2.into_iter()); | |
218 | ||
5e7ed085 | 219 | (subject, impl_obligations) |
ba9703b0 XL |
220 | } |
221 | ||
ba9703b0 XL |
222 | pub fn predicates_for_generics<'tcx>( |
223 | cause: ObligationCause<'tcx>, | |
224 | recursion_depth: usize, | |
225 | param_env: ty::ParamEnv<'tcx>, | |
226 | generic_bounds: ty::InstantiatedPredicates<'tcx>, | |
227 | ) -> impl Iterator<Item = PredicateObligation<'tcx>> { | |
228 | debug!("predicates_for_generics(generic_bounds={:?})", generic_bounds); | |
229 | ||
3c0e092e | 230 | iter::zip(generic_bounds.predicates, generic_bounds.spans).map(move |(predicate, span)| { |
a2a8927a | 231 | let cause = match *cause.code() { |
3c0e092e XL |
232 | traits::ItemObligation(def_id) if !span.is_dummy() => traits::ObligationCause::new( |
233 | cause.span, | |
234 | cause.body_id, | |
235 | traits::BindingObligation(def_id, span), | |
236 | ), | |
237 | _ => cause.clone(), | |
238 | }; | |
239 | Obligation { cause, recursion_depth, param_env, predicate } | |
ba9703b0 XL |
240 | }) |
241 | } | |
242 | ||
243 | pub fn predicate_for_trait_ref<'tcx>( | |
f9f354fc | 244 | tcx: TyCtxt<'tcx>, |
ba9703b0 XL |
245 | cause: ObligationCause<'tcx>, |
246 | param_env: ty::ParamEnv<'tcx>, | |
247 | trait_ref: ty::TraitRef<'tcx>, | |
248 | recursion_depth: usize, | |
249 | ) -> PredicateObligation<'tcx> { | |
250 | Obligation { | |
251 | cause, | |
252 | param_env, | |
253 | recursion_depth, | |
c295e0f8 | 254 | predicate: ty::Binder::dummy(trait_ref).without_const().to_predicate(tcx), |
ba9703b0 XL |
255 | } |
256 | } | |
257 | ||
a2a8927a | 258 | pub fn predicate_for_trait_def<'tcx>( |
ba9703b0 XL |
259 | tcx: TyCtxt<'tcx>, |
260 | param_env: ty::ParamEnv<'tcx>, | |
261 | cause: ObligationCause<'tcx>, | |
262 | trait_def_id: DefId, | |
263 | recursion_depth: usize, | |
264 | self_ty: Ty<'tcx>, | |
265 | params: &[GenericArg<'tcx>], | |
266 | ) -> PredicateObligation<'tcx> { | |
267 | let trait_ref = | |
268 | ty::TraitRef { def_id: trait_def_id, substs: tcx.mk_substs_trait(self_ty, params) }; | |
f9f354fc | 269 | predicate_for_trait_ref(tcx, cause, param_env, trait_ref, recursion_depth) |
ba9703b0 XL |
270 | } |
271 | ||
272 | /// Casts a trait reference into a reference to one of its super | |
273 | /// traits; returns `None` if `target_trait_def_id` is not a | |
274 | /// supertrait. | |
a2a8927a | 275 | pub fn upcast_choices<'tcx>( |
ba9703b0 XL |
276 | tcx: TyCtxt<'tcx>, |
277 | source_trait_ref: ty::PolyTraitRef<'tcx>, | |
278 | target_trait_def_id: DefId, | |
279 | ) -> Vec<ty::PolyTraitRef<'tcx>> { | |
280 | if source_trait_ref.def_id() == target_trait_def_id { | |
281 | return vec![source_trait_ref]; // Shortcut the most common case. | |
282 | } | |
283 | ||
284 | supertraits(tcx, source_trait_ref).filter(|r| r.def_id() == target_trait_def_id).collect() | |
285 | } | |
286 | ||
287 | /// Given a trait `trait_ref`, returns the number of vtable entries | |
288 | /// that come from `trait_ref`, excluding its supertraits. Used in | |
289 | /// computing the vtable base for an upcast trait of a trait object. | |
a2a8927a XL |
290 | pub fn count_own_vtable_entries<'tcx>( |
291 | tcx: TyCtxt<'tcx>, | |
292 | trait_ref: ty::PolyTraitRef<'tcx>, | |
293 | ) -> usize { | |
c295e0f8 XL |
294 | let existential_trait_ref = |
295 | trait_ref.map_bound(|trait_ref| ty::ExistentialTraitRef::erase_self_ty(tcx, trait_ref)); | |
296 | let existential_trait_ref = tcx.erase_regions(existential_trait_ref); | |
297 | tcx.own_existential_vtable_entries(existential_trait_ref).len() | |
ba9703b0 XL |
298 | } |
299 | ||
300 | /// Given an upcast trait object described by `object`, returns the | |
301 | /// index of the method `method_def_id` (which should be part of | |
302 | /// `object.upcast_trait_ref`) within the vtable for `object`. | |
a2a8927a | 303 | pub fn get_vtable_index_of_object_method<'tcx, N>( |
ba9703b0 | 304 | tcx: TyCtxt<'tcx>, |
f035d41b | 305 | object: &super::ImplSourceObjectData<'tcx, N>, |
ba9703b0 | 306 | method_def_id: DefId, |
923072b8 | 307 | ) -> Option<usize> { |
c295e0f8 XL |
308 | let existential_trait_ref = object |
309 | .upcast_trait_ref | |
310 | .map_bound(|trait_ref| ty::ExistentialTraitRef::erase_self_ty(tcx, trait_ref)); | |
311 | let existential_trait_ref = tcx.erase_regions(existential_trait_ref); | |
923072b8 | 312 | |
ba9703b0 XL |
313 | // Count number of methods preceding the one we are selecting and |
314 | // add them to the total offset. | |
923072b8 | 315 | if let Some(index) = tcx |
c295e0f8 XL |
316 | .own_existential_vtable_entries(existential_trait_ref) |
317 | .iter() | |
318 | .copied() | |
319 | .position(|def_id| def_id == method_def_id) | |
923072b8 FG |
320 | { |
321 | Some(object.vtable_base + index) | |
322 | } else { | |
323 | None | |
324 | } | |
ba9703b0 XL |
325 | } |
326 | ||
a2a8927a | 327 | pub fn closure_trait_ref_and_return_type<'tcx>( |
ba9703b0 XL |
328 | tcx: TyCtxt<'tcx>, |
329 | fn_trait_def_id: DefId, | |
330 | self_ty: Ty<'tcx>, | |
331 | sig: ty::PolyFnSig<'tcx>, | |
332 | tuple_arguments: TupleArgumentsFlag, | |
cdc7bbd5 | 333 | ) -> ty::Binder<'tcx, (ty::TraitRef<'tcx>, Ty<'tcx>)> { |
ba9703b0 XL |
334 | let arguments_tuple = match tuple_arguments { |
335 | TupleArgumentsFlag::No => sig.skip_binder().inputs()[0], | |
336 | TupleArgumentsFlag::Yes => tcx.intern_tup(sig.skip_binder().inputs()), | |
337 | }; | |
fc512014 | 338 | debug_assert!(!self_ty.has_escaping_bound_vars()); |
ba9703b0 XL |
339 | let trait_ref = ty::TraitRef { |
340 | def_id: fn_trait_def_id, | |
341 | substs: tcx.mk_substs_trait(self_ty, &[arguments_tuple.into()]), | |
342 | }; | |
fc512014 | 343 | sig.map_bound(|sig| (trait_ref, sig.output())) |
ba9703b0 XL |
344 | } |
345 | ||
a2a8927a | 346 | pub fn generator_trait_ref_and_outputs<'tcx>( |
ba9703b0 XL |
347 | tcx: TyCtxt<'tcx>, |
348 | fn_trait_def_id: DefId, | |
349 | self_ty: Ty<'tcx>, | |
350 | sig: ty::PolyGenSig<'tcx>, | |
cdc7bbd5 | 351 | ) -> ty::Binder<'tcx, (ty::TraitRef<'tcx>, Ty<'tcx>, Ty<'tcx>)> { |
fc512014 | 352 | debug_assert!(!self_ty.has_escaping_bound_vars()); |
ba9703b0 XL |
353 | let trait_ref = ty::TraitRef { |
354 | def_id: fn_trait_def_id, | |
355 | substs: tcx.mk_substs_trait(self_ty, &[sig.skip_binder().resume_ty.into()]), | |
356 | }; | |
fc512014 | 357 | sig.map_bound(|sig| (trait_ref, sig.yield_ty, sig.return_ty)) |
ba9703b0 XL |
358 | } |
359 | ||
360 | pub fn impl_item_is_final(tcx: TyCtxt<'_>, assoc_item: &ty::AssocItem) -> bool { | |
361 | assoc_item.defaultness.is_final() && tcx.impl_defaultness(assoc_item.container.id()).is_final() | |
362 | } | |
363 | ||
364 | pub enum TupleArgumentsFlag { | |
365 | Yes, | |
366 | No, | |
367 | } |