1 use rustc_errors::DiagnosticBuilder;
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, 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(
48 diag: &mut DiagnosticBuilder<'_>,
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));
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
63 format!("trait alias used in trait object type ({})", use_desc),
68 pub fn trait_ref(&self) -> ty::PolyTraitRef<'tcx> {
72 pub fn top(&self) -> &(ty::PolyTraitRef<'tcx>, Span) {
73 self.path.last().unwrap()
76 pub fn bottom(&self) -> &(ty::PolyTraitRef<'tcx>, Span) {
77 self.path.first().unwrap()
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));
88 pub fn expand_trait_aliases<'tcx>(
90 trait_refs: impl Iterator<Item = (ty::PolyTraitRef<'tcx>, Span)>,
91 ) -> TraitAliasExpander<'tcx> {
93 trait_refs.map(|(trait_ref, span)| TraitAliasExpansionInfo::new(trait_ref, span)).collect();
94 TraitAliasExpander { tcx, stack: items }
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
102 /// The return value indicates whether `item` should be yielded to the user.
103 fn expand(&mut self, item: &TraitAliasExpansionInfo<'tcx>) -> bool {
105 let trait_ref = item.trait_ref();
106 let pred = trait_ref.without_const().to_predicate(tcx);
108 debug!("expand_trait_aliases: trait_ref={:?}", trait_ref);
110 // Don't recurse if this bound is not a trait alias.
111 let is_alias = tcx.is_trait_alias(trait_ref.def_id());
116 // Don't recurse if this trait alias is already on the stack for the DFS search.
117 let anon_pred = anonymize_predicate(tcx, pred);
118 if item.path.iter().rev().skip(1).any(|&(tr, _)| {
119 anonymize_predicate(tcx, tr.without_const().to_predicate(tcx)) == anon_pred
124 // Get components of trait alias.
125 let predicates = tcx.super_predicates_of(trait_ref.def_id());
127 let items = predicates.predicates.iter().rev().filter_map(|(pred, span)| {
128 pred.subst_supertrait(tcx, &trait_ref)
129 .to_opt_poly_trait_pred()
130 .map(|trait_ref| item.clone_and_push(trait_ref.map_bound(|t| t.trait_ref), *span))
132 debug!("expand_trait_aliases: items={:?}", items.clone());
134 self.stack.extend(items);
140 impl<'tcx> Iterator for TraitAliasExpander<'tcx> {
141 type Item = TraitAliasExpansionInfo<'tcx>;
143 fn size_hint(&self) -> (usize, Option<usize>) {
144 (self.stack.len(), None)
147 fn next(&mut self) -> Option<TraitAliasExpansionInfo<'tcx>> {
148 while let Some(item) = self.stack.pop() {
149 if self.expand(&item) {
157 ///////////////////////////////////////////////////////////////////////////
158 // Iterator over def-IDs of supertraits
159 ///////////////////////////////////////////////////////////////////////////
161 pub struct SupertraitDefIds<'tcx> {
164 visited: FxHashSet<DefId>,
167 pub fn supertrait_def_ids(tcx: TyCtxt<'_>, trait_def_id: DefId) -> SupertraitDefIds<'_> {
170 stack: vec![trait_def_id],
171 visited: Some(trait_def_id).into_iter().collect(),
175 impl Iterator for SupertraitDefIds<'_> {
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;
186 .filter_map(|(pred, _)| pred.to_opt_poly_trait_pred())
187 .map(|trait_ref| trait_ref.def_id())
188 .filter(|&super_def_id| visited.insert(super_def_id)),
194 ///////////////////////////////////////////////////////////////////////////
196 ///////////////////////////////////////////////////////////////////////////
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>,
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 } =
210 super::normalize(selcx, param_env, ObligationCause::dummy(), impl_trait_ref);
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 } =
215 super::normalize(selcx, param_env, ObligationCause::dummy(), predicates);
216 let impl_obligations =
217 predicates_for_generics(ObligationCause::dummy(), 0, param_env, predicates);
219 let impl_obligations = impl_obligations
220 .chain(normalization_obligations1.into_iter())
221 .chain(normalization_obligations2.into_iter());
223 (impl_trait_ref, impl_obligations)
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);
234 iter::zip(generic_bounds.predicates, generic_bounds.spans).map(move |(predicate, span)| {
235 let cause = match cause.code {
236 traits::ItemObligation(def_id) if !span.is_dummy() => traits::ObligationCause::new(
239 traits::BindingObligation(def_id, span),
243 Obligation { cause, recursion_depth, param_env, predicate }
247 pub fn predicate_for_trait_ref<'tcx>(
249 cause: ObligationCause<'tcx>,
250 param_env: ty::ParamEnv<'tcx>,
251 trait_ref: ty::TraitRef<'tcx>,
252 recursion_depth: usize,
253 ) -> PredicateObligation<'tcx> {
258 predicate: ty::Binder::dummy(trait_ref).without_const().to_predicate(tcx),
262 pub fn predicate_for_trait_def<'tcx>(
264 param_env: ty::ParamEnv<'tcx>,
265 cause: ObligationCause<'tcx>,
267 recursion_depth: usize,
269 params: &[GenericArg<'tcx>],
270 ) -> PredicateObligation<'tcx> {
272 ty::TraitRef { def_id: trait_def_id, substs: tcx.mk_substs_trait(self_ty, params) };
273 predicate_for_trait_ref(tcx, cause, param_env, trait_ref, recursion_depth)
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
279 pub fn upcast_choices<'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.
288 supertraits(tcx, source_trait_ref).filter(|r| r.def_id() == target_trait_def_id).collect()
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.
294 pub fn count_own_vtable_entries<'tcx>(
296 trait_ref: ty::PolyTraitRef<'tcx>,
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()
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`.
307 pub fn get_vtable_index_of_object_method<'tcx, N>(
309 object: &super::ImplSourceObjectData<'tcx, N>,
310 method_def_id: DefId,
312 let existential_trait_ref = object
314 .map_bound(|trait_ref| ty::ExistentialTraitRef::erase_self_ty(tcx, trait_ref));
315 let existential_trait_ref = tcx.erase_regions(existential_trait_ref);
316 // Count number of methods preceding the one we are selecting and
317 // add them to the total offset.
319 .own_existential_vtable_entries(existential_trait_ref)
322 .position(|def_id| def_id == method_def_id)
324 bug!("get_vtable_index_of_object_method: {:?} was not found", method_def_id);
326 object.vtable_base + index
329 pub fn closure_trait_ref_and_return_type<'tcx>(
331 fn_trait_def_id: DefId,
333 sig: ty::PolyFnSig<'tcx>,
334 tuple_arguments: TupleArgumentsFlag,
335 ) -> ty::Binder<'tcx, (ty::TraitRef<'tcx>, Ty<'tcx>)> {
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()),
340 debug_assert!(!self_ty.has_escaping_bound_vars());
341 let trait_ref = ty::TraitRef {
342 def_id: fn_trait_def_id,
343 substs: tcx.mk_substs_trait(self_ty, &[arguments_tuple.into()]),
345 sig.map_bound(|sig| (trait_ref, sig.output()))
348 pub fn generator_trait_ref_and_outputs<'tcx>(
350 fn_trait_def_id: DefId,
352 sig: ty::PolyGenSig<'tcx>,
353 ) -> ty::Binder<'tcx, (ty::TraitRef<'tcx>, Ty<'tcx>, Ty<'tcx>)> {
354 debug_assert!(!self_ty.has_escaping_bound_vars());
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()]),
359 sig.map_bound(|sig| (trait_ref, sig.yield_ty, sig.return_ty))
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()
366 pub enum TupleArgumentsFlag {