1 use rustc_errors
::Diagnostic
;
3 use smallvec
::smallvec
;
4 use smallvec
::SmallVec
;
6 use rustc_data_structures
::fx
::FxHashSet
;
7 use rustc_hir
::def_id
::DefId
;
8 use rustc_middle
::ty
::subst
::{GenericArg, Subst, SubstsRef}
;
9 use rustc_middle
::ty
::{self, EarlyBinder, ImplSubject, ToPredicate, Ty, TyCtxt, TypeFoldable}
;
11 use super::{Normalized, Obligation, ObligationCause, PredicateObligation, SelectionContext}
;
12 pub use rustc_infer
::traits
::{self, util::*}
;
16 ///////////////////////////////////////////////////////////////////////////
17 // `TraitAliasExpander` iterator
18 ///////////////////////////////////////////////////////////////////////////
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
> {
30 stack
: Vec
<TraitAliasExpansionInfo
<'tcx
>>,
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]>,
39 impl<'tcx
> TraitAliasExpansionInfo
<'tcx
> {
40 fn new(trait_ref
: ty
::PolyTraitRef
<'tcx
>, span
: Span
) -> Self {
41 Self { path: smallvec![(trait_ref, span)] }
44 /// Adds diagnostic labels to `diag` for the expansion path of a trait through all intermediate
46 pub fn label_with_exp_info(&self, diag
: &mut Diagnostic
, top_label
: &str, use_desc
: &str) {
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
));
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
58 format
!("trait alias used in trait object type ({})", use_desc
),
63 pub fn trait_ref(&self) -> ty
::PolyTraitRef
<'tcx
> {
67 pub fn top(&self) -> &(ty
::PolyTraitRef
<'tcx
>, Span
) {
68 self.path
.last().unwrap()
71 pub fn bottom(&self) -> &(ty
::PolyTraitRef
<'tcx
>, Span
) {
72 self.path
.first().unwrap()
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
));
83 pub fn expand_trait_aliases
<'tcx
>(
85 trait_refs
: impl Iterator
<Item
= (ty
::PolyTraitRef
<'tcx
>, Span
)>,
86 ) -> TraitAliasExpander
<'tcx
> {
88 trait_refs
.map(|(trait_ref
, span
)| TraitAliasExpansionInfo
::new(trait_ref
, span
)).collect();
89 TraitAliasExpander { tcx, stack: items }
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
97 /// The return value indicates whether `item` should be yielded to the user.
98 fn expand(&mut self, item
: &TraitAliasExpansionInfo
<'tcx
>) -> bool
{
100 let trait_ref
= item
.trait_ref();
101 let pred
= trait_ref
.without_const().to_predicate(tcx
);
103 debug
!("expand_trait_aliases: trait_ref={:?}", trait_ref
);
105 // Don't recurse if this bound is not a trait alias.
106 let is_alias
= tcx
.is_trait_alias(trait_ref
.def_id());
111 // Don't recurse if this trait alias is already on the stack for the DFS search.
112 let anon_pred
= anonymize_predicate(tcx
, pred
);
113 if item
.path
.iter().rev().skip(1).any(|&(tr
, _
)| {
114 anonymize_predicate(tcx
, tr
.without_const().to_predicate(tcx
)) == anon_pred
119 // Get components of trait alias.
120 let predicates
= tcx
.super_predicates_of(trait_ref
.def_id());
123 let items
= predicates
.predicates
.iter().rev().filter_map(|(pred
, span
)| {
124 pred
.subst_supertrait(tcx
, &trait_ref
)
125 .to_opt_poly_trait_pred()
126 .map(|trait_ref
| item
.clone_and_push(trait_ref
.map_bound(|t
| t
.trait_ref
), *span
))
128 debug
!("expand_trait_aliases: items={:?}", items
.clone().collect
::<Vec
<_
>>());
130 self.stack
.extend(items
);
136 impl<'tcx
> Iterator
for TraitAliasExpander
<'tcx
> {
137 type Item
= TraitAliasExpansionInfo
<'tcx
>;
139 fn size_hint(&self) -> (usize, Option
<usize>) {
140 (self.stack
.len(), None
)
143 fn next(&mut self) -> Option
<TraitAliasExpansionInfo
<'tcx
>> {
144 while let Some(item
) = self.stack
.pop() {
145 if self.expand(&item
) {
153 ///////////////////////////////////////////////////////////////////////////
154 // Iterator over def-IDs of supertraits
155 ///////////////////////////////////////////////////////////////////////////
157 pub struct SupertraitDefIds
<'tcx
> {
160 visited
: FxHashSet
<DefId
>,
163 pub fn supertrait_def_ids(tcx
: TyCtxt
<'_
>, trait_def_id
: DefId
) -> SupertraitDefIds
<'_
> {
166 stack
: vec
![trait_def_id
],
167 visited
: Some(trait_def_id
).into_iter().collect(),
171 impl Iterator
for SupertraitDefIds
<'_
> {
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
;
182 .filter_map(|(pred
, _
)| pred
.to_opt_poly_trait_pred())
183 .map(|trait_ref
| trait_ref
.def_id())
184 .filter(|&super_def_id
| visited
.insert(super_def_id
)),
190 ///////////////////////////////////////////////////////////////////////////
192 ///////////////////////////////////////////////////////////////////////////
194 /// Instantiate all bound parameters of the impl subject with the given substs,
195 /// returning the resulting subject and all obligations that arise.
196 /// The obligations are closed under normalization.
197 pub fn impl_subject_and_oblig
<'a
, 'tcx
>(
198 selcx
: &mut SelectionContext
<'a
, 'tcx
>,
199 param_env
: ty
::ParamEnv
<'tcx
>,
201 impl_substs
: SubstsRef
<'tcx
>,
202 ) -> (ImplSubject
<'tcx
>, impl Iterator
<Item
= PredicateObligation
<'tcx
>>) {
203 let subject
= selcx
.tcx().impl_subject(impl_def_id
);
204 let subject
= EarlyBinder(subject
).subst(selcx
.tcx(), impl_substs
);
205 let Normalized { value: subject, obligations: normalization_obligations1 }
=
206 super::normalize(selcx
, param_env
, ObligationCause
::dummy(), subject
);
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 }
=
211 super::normalize(selcx
, param_env
, ObligationCause
::dummy(), predicates
);
212 let impl_obligations
=
213 predicates_for_generics(ObligationCause
::dummy(), 0, param_env
, predicates
);
215 let impl_obligations
= impl_obligations
216 .chain(normalization_obligations1
.into_iter())
217 .chain(normalization_obligations2
.into_iter());
219 (subject
, impl_obligations
)
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
);
230 iter
::zip(generic_bounds
.predicates
, generic_bounds
.spans
).map(move |(predicate
, span
)| {
231 let cause
= match *cause
.code() {
232 traits
::ItemObligation(def_id
) if !span
.is_dummy() => traits
::ObligationCause
::new(
235 traits
::BindingObligation(def_id
, span
),
239 Obligation { cause, recursion_depth, param_env, predicate }
243 pub fn predicate_for_trait_ref
<'tcx
>(
245 cause
: ObligationCause
<'tcx
>,
246 param_env
: ty
::ParamEnv
<'tcx
>,
247 trait_ref
: ty
::TraitRef
<'tcx
>,
248 recursion_depth
: usize,
249 ) -> PredicateObligation
<'tcx
> {
254 predicate
: ty
::Binder
::dummy(trait_ref
).without_const().to_predicate(tcx
),
258 pub fn predicate_for_trait_def
<'tcx
>(
260 param_env
: ty
::ParamEnv
<'tcx
>,
261 cause
: ObligationCause
<'tcx
>,
263 recursion_depth
: usize,
265 params
: &[GenericArg
<'tcx
>],
266 ) -> PredicateObligation
<'tcx
> {
268 ty
::TraitRef { def_id: trait_def_id, substs: tcx.mk_substs_trait(self_ty, params) }
;
269 predicate_for_trait_ref(tcx
, cause
, param_env
, trait_ref
, recursion_depth
)
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
275 pub fn upcast_choices
<'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.
284 supertraits(tcx
, source_trait_ref
).filter(|r
| r
.def_id() == target_trait_def_id
).collect()
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.
290 pub fn count_own_vtable_entries
<'tcx
>(
292 trait_ref
: ty
::PolyTraitRef
<'tcx
>,
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()
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`.
303 pub fn get_vtable_index_of_object_method
<'tcx
, N
>(
305 object
: &super::ImplSourceObjectData
<'tcx
, N
>,
306 method_def_id
: DefId
,
308 let existential_trait_ref
= object
310 .map_bound(|trait_ref
| ty
::ExistentialTraitRef
::erase_self_ty(tcx
, trait_ref
));
311 let existential_trait_ref
= tcx
.erase_regions(existential_trait_ref
);
313 // Count number of methods preceding the one we are selecting and
314 // add them to the total offset.
315 if let Some(index
) = tcx
316 .own_existential_vtable_entries(existential_trait_ref
)
319 .position(|def_id
| def_id
== method_def_id
)
321 Some(object
.vtable_base
+ index
)
327 pub fn closure_trait_ref_and_return_type
<'tcx
>(
329 fn_trait_def_id
: DefId
,
331 sig
: ty
::PolyFnSig
<'tcx
>,
332 tuple_arguments
: TupleArgumentsFlag
,
333 ) -> ty
::Binder
<'tcx
, (ty
::TraitRef
<'tcx
>, Ty
<'tcx
>)> {
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()),
338 debug_assert
!(!self_ty
.has_escaping_bound_vars());
339 let trait_ref
= ty
::TraitRef
{
340 def_id
: fn_trait_def_id
,
341 substs
: tcx
.mk_substs_trait(self_ty
, &[arguments_tuple
.into()]),
343 sig
.map_bound(|sig
| (trait_ref
, sig
.output()))
346 pub fn generator_trait_ref_and_outputs
<'tcx
>(
348 fn_trait_def_id
: DefId
,
350 sig
: ty
::PolyGenSig
<'tcx
>,
351 ) -> ty
::Binder
<'tcx
, (ty
::TraitRef
<'tcx
>, Ty
<'tcx
>, Ty
<'tcx
>)> {
352 debug_assert
!(!self_ty
.has_escaping_bound_vars());
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()]),
357 sig
.map_bound(|sig
| (trait_ref
, sig
.yield_ty
, sig
.return_ty
))
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()
364 pub enum TupleArgumentsFlag
{