compiler/rustc_trait_selection/src/traits/util.rs

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