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::{Obligation, ObligationCause, PredicateObligation, SelectionContext};
  12 use crate::infer::InferCtxtExt;
  13 use rustc_infer::infer::InferOk;
  14 pub use rustc_infer::traits::{self, util::*};
  15
  16 ///////////////////////////////////////////////////////////////////////////
  17 // `TraitAliasExpander` iterator
  18 ///////////////////////////////////////////////////////////////////////////
  19
  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> {
  29     tcx: TyCtxt<'tcx>,
  30     stack: Vec<TraitAliasExpansionInfo<'tcx>>,
  31 }
  32
  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]>,
  37 }
  38
  39 impl<'tcx> TraitAliasExpansionInfo<'tcx> {
  40     fn new(trait_ref: ty::PolyTraitRef<'tcx>, span: Span) -> Self {
  41         Self { path: smallvec![(trait_ref, span)] }
  42     }
  43
  44     /// Adds diagnostic labels to `diag` for the expansion path of a trait through all intermediate
  45     /// trait aliases.
  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));
  51             }
  52         }
  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
  55             // redundant labels.
  56             diag.span_label(
  57                 self.bottom().1,
  58                 format!("trait alias used in trait object type ({})", use_desc),
  59             );
  60         }
  61     }
  62
  63     pub fn trait_ref(&self) -> ty::PolyTraitRef<'tcx> {
  64         self.top().0
  65     }
  66
  67     pub fn top(&self) -> &(ty::PolyTraitRef<'tcx>, Span) {
  68         self.path.last().unwrap()
  69     }
  70
  71     pub fn bottom(&self) -> &(ty::PolyTraitRef<'tcx>, Span) {
  72         self.path.first().unwrap()
  73     }
  74
  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));
  78
  79         Self { path }
  80     }
  81 }
  82
  83 pub fn expand_trait_aliases<'tcx>(
  84     tcx: TyCtxt<'tcx>,
  85     trait_refs: impl Iterator<Item = (ty::PolyTraitRef<'tcx>, Span)>,
  86 ) -> TraitAliasExpander<'tcx> {
  87     let items: Vec<_> =
  88         trait_refs.map(|(trait_ref, span)| TraitAliasExpansionInfo::new(trait_ref, span)).collect();
  89     TraitAliasExpander { tcx, stack: items }
  90 }
  91
  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
  96     /// trait alias.
  97     /// The return value indicates whether `item` should be yielded to the user.
  98     fn expand(&mut self, item: &TraitAliasExpansionInfo<'tcx>) -> bool {
  99         let tcx = self.tcx;
 100         let trait_ref = item.trait_ref();
 101         let pred = trait_ref.without_const().to_predicate(tcx);
 102
 103         debug!("expand_trait_aliases: trait_ref={:?}", trait_ref);
 104
 105         // Don't recurse if this bound is not a trait alias.
 106         let is_alias = tcx.is_trait_alias(trait_ref.def_id());
 107         if !is_alias {
 108             return true;
 109         }
 110
 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
 115         }) {
 116             return false;
 117         }
 118
 119         // Get components of trait alias.
 120         let predicates = tcx.super_predicates_of(trait_ref.def_id());
 121         debug!(?predicates);
 122
 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))
 127         });
 128         debug!("expand_trait_aliases: items={:?}", items.clone().collect::<Vec<_>>());
 129
 130         self.stack.extend(items);
 131
 132         false
 133     }
 134 }
 135
 136 impl<'tcx> Iterator for TraitAliasExpander<'tcx> {
 137     type Item = TraitAliasExpansionInfo<'tcx>;
 138
 139     fn size_hint(&self) -> (usize, Option<usize>) {
 140         (self.stack.len(), None)
 141     }
 142
 143     fn next(&mut self) -> Option<TraitAliasExpansionInfo<'tcx>> {
 144         while let Some(item) = self.stack.pop() {
 145             if self.expand(&item) {
 146                 return Some(item);
 147             }
 148         }
 149         None
 150     }
 151 }
 152
 153 ///////////////////////////////////////////////////////////////////////////
 154 // Iterator over def-IDs of supertraits
 155 ///////////////////////////////////////////////////////////////////////////
 156
 157 pub struct SupertraitDefIds<'tcx> {
 158     tcx: TyCtxt<'tcx>,
 159     stack: Vec<DefId>,
 160     visited: FxHashSet<DefId>,
 161 }
 162
 163 pub fn supertrait_def_ids(tcx: TyCtxt<'_>, trait_def_id: DefId) -> SupertraitDefIds<'_> {
 164     SupertraitDefIds {
 165         tcx,
 166         stack: vec![trait_def_id],
 167         visited: Some(trait_def_id).into_iter().collect(),
 168     }
 169 }
 170
 171 impl Iterator for SupertraitDefIds<'_> {
 172     type Item = DefId;
 173
 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;
 178         self.stack.extend(
 179             predicates
 180                 .predicates
 181                 .iter()
 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)),
 185         );
 186         Some(def_id)
 187     }
 188 }
 189
 190 ///////////////////////////////////////////////////////////////////////////
 191 // Other
 192 ///////////////////////////////////////////////////////////////////////////
 193
 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>,
 200     impl_def_id: DefId,
 201     impl_substs: SubstsRef<'tcx>,
 202 ) -> (ImplSubject<'tcx>, impl Iterator<Item = PredicateObligation<'tcx>>) {
 203     let subject = selcx.tcx().bound_impl_subject(impl_def_id);
 204     let subject = subject.subst(selcx.tcx(), impl_substs);
 205     let InferOk { value: subject, obligations: normalization_obligations1 } = selcx
 206         .infcx
 207         .partially_normalize_associated_types_in(ObligationCause::dummy(), param_env, subject);
 208
 209     let predicates = selcx.tcx().predicates_of(impl_def_id);
 210     let predicates = predicates.instantiate(selcx.tcx(), impl_substs);
 211     let InferOk { value: predicates, obligations: normalization_obligations2 } = selcx
 212         .infcx
 213         .partially_normalize_associated_types_in(ObligationCause::dummy(), param_env, predicates);
 214     let impl_obligations =
 215         super::predicates_for_generics(|_, _| ObligationCause::dummy(), param_env, predicates);
 216
 217     let impl_obligations = impl_obligations
 218         .chain(normalization_obligations1.into_iter())
 219         .chain(normalization_obligations2.into_iter());
 220
 221     (subject, impl_obligations)
 222 }
 223
 224 pub fn predicate_for_trait_ref<'tcx>(
 225     tcx: TyCtxt<'tcx>,
 226     cause: ObligationCause<'tcx>,
 227     param_env: ty::ParamEnv<'tcx>,
 228     trait_ref: ty::TraitRef<'tcx>,
 229     recursion_depth: usize,
 230 ) -> PredicateObligation<'tcx> {
 231     Obligation {
 232         cause,
 233         param_env,
 234         recursion_depth,
 235         predicate: ty::Binder::dummy(trait_ref).without_const().to_predicate(tcx),
 236     }
 237 }
 238
 239 pub fn predicate_for_trait_def<'tcx>(
 240     tcx: TyCtxt<'tcx>,
 241     param_env: ty::ParamEnv<'tcx>,
 242     cause: ObligationCause<'tcx>,
 243     trait_def_id: DefId,
 244     recursion_depth: usize,
 245     params: impl IntoIterator<Item = impl Into<GenericArg<'tcx>>>,
 246 ) -> PredicateObligation<'tcx> {
 247     let trait_ref = tcx.mk_trait_ref(trait_def_id, params);
 248     predicate_for_trait_ref(tcx, cause, param_env, trait_ref, recursion_depth)
 249 }
 250
 251 /// Casts a trait reference into a reference to one of its super
 252 /// traits; returns `None` if `target_trait_def_id` is not a
 253 /// supertrait.
 254 pub fn upcast_choices<'tcx>(
 255     tcx: TyCtxt<'tcx>,
 256     source_trait_ref: ty::PolyTraitRef<'tcx>,
 257     target_trait_def_id: DefId,
 258 ) -> Vec<ty::PolyTraitRef<'tcx>> {
 259     if source_trait_ref.def_id() == target_trait_def_id {
 260         return vec![source_trait_ref]; // Shortcut the most common case.
 261     }
 262
 263     supertraits(tcx, source_trait_ref).filter(|r| r.def_id() == target_trait_def_id).collect()
 264 }
 265
 266 /// Given a trait `trait_ref`, returns the number of vtable entries
 267 /// that come from `trait_ref`, excluding its supertraits. Used in
 268 /// computing the vtable base for an upcast trait of a trait object.
 269 pub fn count_own_vtable_entries<'tcx>(
 270     tcx: TyCtxt<'tcx>,
 271     trait_ref: ty::PolyTraitRef<'tcx>,
 272 ) -> usize {
 273     tcx.own_existential_vtable_entries(trait_ref.def_id()).len()
 274 }
 275
 276 /// Given an upcast trait object described by `object`, returns the
 277 /// index of the method `method_def_id` (which should be part of
 278 /// `object.upcast_trait_ref`) within the vtable for `object`.
 279 pub fn get_vtable_index_of_object_method<'tcx, N>(
 280     tcx: TyCtxt<'tcx>,
 281     object: &super::ImplSourceObjectData<'tcx, N>,
 282     method_def_id: DefId,
 283 ) -> Option<usize> {
 284     // Count number of methods preceding the one we are selecting and
 285     // add them to the total offset.
 286     if let Some(index) = tcx
 287         .own_existential_vtable_entries(object.upcast_trait_ref.def_id())
 288         .iter()
 289         .copied()
 290         .position(|def_id| def_id == method_def_id)
 291     {
 292         Some(object.vtable_base + index)
 293     } else {
 294         None
 295     }
 296 }
 297
 298 pub fn closure_trait_ref_and_return_type<'tcx>(
 299     tcx: TyCtxt<'tcx>,
 300     fn_trait_def_id: DefId,
 301     self_ty: Ty<'tcx>,
 302     sig: ty::PolyFnSig<'tcx>,
 303     tuple_arguments: TupleArgumentsFlag,
 304 ) -> ty::Binder<'tcx, (ty::TraitRef<'tcx>, Ty<'tcx>)> {
 305     assert!(!self_ty.has_escaping_bound_vars());
 306     let arguments_tuple = match tuple_arguments {
 307         TupleArgumentsFlag::No => sig.skip_binder().inputs()[0],
 308         TupleArgumentsFlag::Yes => tcx.intern_tup(sig.skip_binder().inputs()),
 309     };
 310     let trait_ref = tcx.mk_trait_ref(fn_trait_def_id, [self_ty, arguments_tuple]);
 311     sig.map_bound(|sig| (trait_ref, sig.output()))
 312 }
 313
 314 pub fn generator_trait_ref_and_outputs<'tcx>(
 315     tcx: TyCtxt<'tcx>,
 316     fn_trait_def_id: DefId,
 317     self_ty: Ty<'tcx>,
 318     sig: ty::PolyGenSig<'tcx>,
 319 ) -> ty::Binder<'tcx, (ty::TraitRef<'tcx>, Ty<'tcx>, Ty<'tcx>)> {
 320     assert!(!self_ty.has_escaping_bound_vars());
 321     let trait_ref = tcx.mk_trait_ref(fn_trait_def_id, [self_ty, sig.skip_binder().resume_ty]);
 322     sig.map_bound(|sig| (trait_ref, sig.yield_ty, sig.return_ty))
 323 }
 324
 325 pub fn future_trait_ref_and_outputs<'tcx>(
 326     tcx: TyCtxt<'tcx>,
 327     fn_trait_def_id: DefId,
 328     self_ty: Ty<'tcx>,
 329     sig: ty::PolyGenSig<'tcx>,
 330 ) -> ty::Binder<'tcx, (ty::TraitRef<'tcx>, Ty<'tcx>)> {
 331     assert!(!self_ty.has_escaping_bound_vars());
 332     let trait_ref = tcx.mk_trait_ref(fn_trait_def_id, [self_ty]);
 333     sig.map_bound(|sig| (trait_ref, sig.return_ty))
 334 }
 335
 336 pub fn impl_item_is_final(tcx: TyCtxt<'_>, assoc_item: &ty::AssocItem) -> bool {
 337     assoc_item.defaultness(tcx).is_final()
 338         && tcx.impl_defaultness(assoc_item.container_id(tcx)).is_final()
 339 }
 340
 341 pub enum TupleArgumentsFlag {
 342     Yes,
 343     No,
 344 }