1 use rustc_errors::Diagnostic;
3 use smallvec::SmallVec;
5 use rustc_data_structures::fx::FxHashSet;
6 use rustc_hir::def_id::DefId;
7 use rustc_middle::ty::{self, ImplSubject, ToPredicate, Ty, TyCtxt, TypeVisitable};
8 use rustc_middle::ty::{GenericArg, SubstsRef};
10 use super::NormalizeExt;
11 use super::{Obligation, ObligationCause, PredicateObligation, SelectionContext};
12 use rustc_infer::infer::InferOk;
13 pub use rustc_infer::traits::{self, util::*};
15 ///////////////////////////////////////////////////////////////////////////
16 // `TraitAliasExpander` iterator
17 ///////////////////////////////////////////////////////////////////////////
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> {
29 stack: Vec<TraitAliasExpansionInfo<'tcx>>,
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]>,
38 impl<'tcx> TraitAliasExpansionInfo<'tcx> {
39 fn new(trait_ref: ty::PolyTraitRef<'tcx>, span: Span) -> Self {
40 Self { path: smallvec![(trait_ref, span)] }
43 /// Adds diagnostic labels to `diag` for the expansion path of a trait through all intermediate
45 pub fn label_with_exp_info(&self, diag: &mut Diagnostic, top_label: &str, use_desc: &str) {
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));
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
57 format!("trait alias used in trait object type ({})", use_desc),
62 pub fn trait_ref(&self) -> ty::PolyTraitRef<'tcx> {
66 pub fn top(&self) -> &(ty::PolyTraitRef<'tcx>, Span) {
67 self.path.last().unwrap()
70 pub fn bottom(&self) -> &(ty::PolyTraitRef<'tcx>, Span) {
71 self.path.first().unwrap()
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));
82 pub fn expand_trait_aliases<'tcx>(
84 trait_refs: impl Iterator<Item = (ty::PolyTraitRef<'tcx>, Span)>,
85 ) -> TraitAliasExpander<'tcx> {
87 trait_refs.map(|(trait_ref, span)| TraitAliasExpansionInfo::new(trait_ref, span)).collect();
88 TraitAliasExpander { tcx, stack: items }
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
96 /// The return value indicates whether `item` should be yielded to the user.
97 fn expand(&mut self, item: &TraitAliasExpansionInfo<'tcx>) -> bool {
99 let trait_ref = item.trait_ref();
100 let pred = trait_ref.without_const().to_predicate(tcx);
102 debug!("expand_trait_aliases: trait_ref={:?}", trait_ref);
104 // Don't recurse if this bound is not a trait alias.
105 let is_alias = tcx.is_trait_alias(trait_ref.def_id());
110 // Don't recurse if this trait alias is already on the stack for the DFS search.
111 let anon_pred = anonymize_predicate(tcx, pred);
112 if item.path.iter().rev().skip(1).any(|&(tr, _)| {
113 anonymize_predicate(tcx, tr.without_const().to_predicate(tcx)) == anon_pred
118 // Get components of trait alias.
119 let predicates = tcx.super_predicates_of(trait_ref.def_id());
122 let items = predicates.predicates.iter().rev().filter_map(|(pred, span)| {
123 pred.subst_supertrait(tcx, &trait_ref)
124 .to_opt_poly_trait_pred()
125 .map(|trait_ref| item.clone_and_push(trait_ref.map_bound(|t| t.trait_ref), *span))
127 debug!("expand_trait_aliases: items={:?}", items.clone().collect::<Vec<_>>());
129 self.stack.extend(items);
135 impl<'tcx> Iterator for TraitAliasExpander<'tcx> {
136 type Item = TraitAliasExpansionInfo<'tcx>;
138 fn size_hint(&self) -> (usize, Option<usize>) {
139 (self.stack.len(), None)
142 fn next(&mut self) -> Option<TraitAliasExpansionInfo<'tcx>> {
143 while let Some(item) = self.stack.pop() {
144 if self.expand(&item) {
152 ///////////////////////////////////////////////////////////////////////////
153 // Iterator over def-IDs of supertraits
154 ///////////////////////////////////////////////////////////////////////////
156 pub struct SupertraitDefIds<'tcx> {
159 visited: FxHashSet<DefId>,
162 pub fn supertrait_def_ids(tcx: TyCtxt<'_>, trait_def_id: DefId) -> SupertraitDefIds<'_> {
165 stack: vec![trait_def_id],
166 visited: Some(trait_def_id).into_iter().collect(),
170 impl Iterator for SupertraitDefIds<'_> {
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;
181 .filter_map(|(pred, _)| pred.to_opt_poly_trait_pred())
182 .map(|trait_ref| trait_ref.def_id())
183 .filter(|&super_def_id| visited.insert(super_def_id)),
189 ///////////////////////////////////////////////////////////////////////////
191 ///////////////////////////////////////////////////////////////////////////
193 /// Instantiate all bound parameters of the impl subject with the given substs,
194 /// returning the resulting subject and all obligations that arise.
195 /// The obligations are closed under normalization.
196 pub fn impl_subject_and_oblig<'a, 'tcx>(
197 selcx: &mut SelectionContext<'a, 'tcx>,
198 param_env: ty::ParamEnv<'tcx>,
200 impl_substs: SubstsRef<'tcx>,
201 ) -> (ImplSubject<'tcx>, impl Iterator<Item = PredicateObligation<'tcx>>) {
202 let subject = selcx.tcx().bound_impl_subject(impl_def_id);
203 let subject = subject.subst(selcx.tcx(), impl_substs);
204 let InferOk { value: subject, obligations: normalization_obligations1 } =
205 selcx.infcx.at(&ObligationCause::dummy(), param_env).normalize(subject);
207 let predicates = selcx.tcx().predicates_of(impl_def_id);
208 let predicates = predicates.instantiate(selcx.tcx(), impl_substs);
209 let InferOk { value: predicates, obligations: normalization_obligations2 } =
210 selcx.infcx.at(&ObligationCause::dummy(), param_env).normalize(predicates);
211 let impl_obligations =
212 super::predicates_for_generics(|_, _| ObligationCause::dummy(), param_env, predicates);
214 let impl_obligations = impl_obligations
215 .chain(normalization_obligations1.into_iter())
216 .chain(normalization_obligations2.into_iter());
218 (subject, impl_obligations)
221 pub fn predicate_for_trait_ref<'tcx>(
223 cause: ObligationCause<'tcx>,
224 param_env: ty::ParamEnv<'tcx>,
225 trait_ref: ty::TraitRef<'tcx>,
226 recursion_depth: usize,
227 ) -> PredicateObligation<'tcx> {
232 predicate: ty::Binder::dummy(trait_ref).without_const().to_predicate(tcx),
236 pub fn predicate_for_trait_def<'tcx>(
238 param_env: ty::ParamEnv<'tcx>,
239 cause: ObligationCause<'tcx>,
241 recursion_depth: usize,
242 params: impl IntoIterator<Item = impl Into<GenericArg<'tcx>>>,
243 ) -> PredicateObligation<'tcx> {
244 let trait_ref = tcx.mk_trait_ref(trait_def_id, params);
245 predicate_for_trait_ref(tcx, cause, param_env, trait_ref, recursion_depth)
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
251 pub fn upcast_choices<'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.
260 supertraits(tcx, source_trait_ref).filter(|r| r.def_id() == target_trait_def_id).collect()
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`.
266 pub fn get_vtable_index_of_object_method<'tcx, N>(
268 object: &super::ImplSourceObjectData<'tcx, N>,
269 method_def_id: DefId,
271 // Count number of methods preceding the one we are selecting and
272 // add them to the total offset.
273 if let Some(index) = tcx
274 .own_existential_vtable_entries(object.upcast_trait_ref.def_id())
277 .position(|def_id| def_id == method_def_id)
279 Some(object.vtable_base + index)
285 pub fn closure_trait_ref_and_return_type<'tcx>(
287 fn_trait_def_id: DefId,
289 sig: ty::PolyFnSig<'tcx>,
290 tuple_arguments: TupleArgumentsFlag,
291 ) -> ty::Binder<'tcx, (ty::TraitRef<'tcx>, Ty<'tcx>)> {
292 assert!(!self_ty.has_escaping_bound_vars());
293 let arguments_tuple = match tuple_arguments {
294 TupleArgumentsFlag::No => sig.skip_binder().inputs()[0],
295 TupleArgumentsFlag::Yes => tcx.intern_tup(sig.skip_binder().inputs()),
297 let trait_ref = tcx.mk_trait_ref(fn_trait_def_id, [self_ty, arguments_tuple]);
298 sig.map_bound(|sig| (trait_ref, sig.output()))
301 pub fn generator_trait_ref_and_outputs<'tcx>(
303 fn_trait_def_id: DefId,
305 sig: ty::PolyGenSig<'tcx>,
306 ) -> ty::Binder<'tcx, (ty::TraitRef<'tcx>, Ty<'tcx>, Ty<'tcx>)> {
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]);
309 sig.map_bound(|sig| (trait_ref, sig.yield_ty, sig.return_ty))
312 pub fn future_trait_ref_and_outputs<'tcx>(
314 fn_trait_def_id: DefId,
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))
323 pub fn impl_item_is_final(tcx: TyCtxt<'_>, assoc_item: &ty::AssocItem) -> bool {
324 assoc_item.defaultness(tcx).is_final()
325 && tcx.impl_defaultness(assoc_item.container_id(tcx)).is_final()
328 pub enum TupleArgumentsFlag {