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