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