compiler/rustc_trait_selection/src/traits/util.rs

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