src/librustc_trait_selection/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, 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         diag.span_label(
  57             self.bottom().1,
  58             format!("trait alias used in trait object type ({})", use_desc),
  59         );
  60     }
  61
  62     pub fn trait_ref(&self) -> &ty::PolyTraitRef<'tcx> {
  63         &self.top().0
  64     }
  65
  66     pub fn top(&self) -> &(ty::PolyTraitRef<'tcx>, Span) {
  67         self.path.last().unwrap()
  68     }
  69
  70     pub fn bottom(&self) -> &(ty::PolyTraitRef<'tcx>, Span) {
  71         self.path.first().unwrap()
  72     }
  73
  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));
  77
  78         Self { path }
  79     }
  80 }
  81
  82 pub fn expand_trait_aliases<'tcx>(
  83     tcx: TyCtxt<'tcx>,
  84     trait_refs: impl Iterator<Item = (ty::PolyTraitRef<'tcx>, Span)>,
  85 ) -> TraitAliasExpander<'tcx> {
  86     let items: Vec<_> =
  87         trait_refs.map(|(trait_ref, span)| TraitAliasExpansionInfo::new(trait_ref, span)).collect();
  88     TraitAliasExpander { tcx, stack: items }
  89 }
  90
  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
  95     /// trait alias.
  96     /// The return value indicates whether `item` should be yielded to the user.
  97     fn expand(&mut self, item: &TraitAliasExpansionInfo<'tcx>) -> bool {
  98         let tcx = self.tcx;
  99         let trait_ref = item.trait_ref();
 100         let pred = trait_ref.without_const().to_predicate();
 101
 102         debug!("expand_trait_aliases: trait_ref={:?}", trait_ref);
 103
 104         // Don't recurse if this bound is not a trait alias.
 105         let is_alias = tcx.is_trait_alias(trait_ref.def_id());
 106         if !is_alias {
 107             return true;
 108         }
 109
 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()) == anon_pred
 114         }) {
 115             return false;
 116         }
 117
 118         // Get components of trait alias.
 119         let predicates = tcx.super_predicates_of(trait_ref.def_id());
 120
 121         let items = predicates.predicates.iter().rev().filter_map(|(pred, span)| {
 122             pred.subst_supertrait(tcx, &trait_ref)
 123                 .to_opt_poly_trait_ref()
 124                 .map(|trait_ref| item.clone_and_push(trait_ref, *span))
 125         });
 126         debug!("expand_trait_aliases: items={:?}", items.clone());
 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<'tcx> {
 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_ref())
 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 with the given substs,
 193 /// returning the resulting trait ref and all obligations that arise.
 194 /// The obligations are closed under normalization.
 195 pub fn impl_trait_ref_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 ) -> (ty::TraitRef<'tcx>, impl Iterator<Item = PredicateObligation<'tcx>>) {
 201     let impl_trait_ref = selcx.tcx().impl_trait_ref(impl_def_id).unwrap();
 202     let impl_trait_ref = impl_trait_ref.subst(selcx.tcx(), impl_substs);
 203     let Normalized { value: impl_trait_ref, obligations: normalization_obligations1 } =
 204         super::normalize(selcx, param_env, ObligationCause::dummy(), &impl_trait_ref);
 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         predicates_for_generics(ObligationCause::dummy(), 0, param_env, predicates);
 212
 213     let impl_obligations = impl_obligations
 214         .chain(normalization_obligations1.into_iter())
 215         .chain(normalization_obligations2.into_iter());
 216
 217     (impl_trait_ref, impl_obligations)
 218 }
 219
 220 /// See [`super::obligations_for_generics`].
 221 pub fn predicates_for_generics<'tcx>(
 222     cause: ObligationCause<'tcx>,
 223     recursion_depth: usize,
 224     param_env: ty::ParamEnv<'tcx>,
 225     generic_bounds: ty::InstantiatedPredicates<'tcx>,
 226 ) -> impl Iterator<Item = PredicateObligation<'tcx>> {
 227     debug!("predicates_for_generics(generic_bounds={:?})", generic_bounds);
 228
 229     generic_bounds.predicates.into_iter().map(move |predicate| Obligation {
 230         cause: cause.clone(),
 231         recursion_depth,
 232         param_env,
 233         predicate,
 234     })
 235 }
 236
 237 pub fn predicate_for_trait_ref<'tcx>(
 238     cause: ObligationCause<'tcx>,
 239     param_env: ty::ParamEnv<'tcx>,
 240     trait_ref: ty::TraitRef<'tcx>,
 241     recursion_depth: usize,
 242 ) -> PredicateObligation<'tcx> {
 243     Obligation {
 244         cause,
 245         param_env,
 246         recursion_depth,
 247         predicate: trait_ref.without_const().to_predicate(),
 248     }
 249 }
 250
 251 pub fn predicate_for_trait_def(
 252     tcx: TyCtxt<'tcx>,
 253     param_env: ty::ParamEnv<'tcx>,
 254     cause: ObligationCause<'tcx>,
 255     trait_def_id: DefId,
 256     recursion_depth: usize,
 257     self_ty: Ty<'tcx>,
 258     params: &[GenericArg<'tcx>],
 259 ) -> PredicateObligation<'tcx> {
 260     let trait_ref =
 261         ty::TraitRef { def_id: trait_def_id, substs: tcx.mk_substs_trait(self_ty, params) };
 262     predicate_for_trait_ref(cause, param_env, trait_ref, recursion_depth)
 263 }
 264
 265 /// Casts a trait reference into a reference to one of its super
 266 /// traits; returns `None` if `target_trait_def_id` is not a
 267 /// supertrait.
 268 pub fn upcast_choices(
 269     tcx: TyCtxt<'tcx>,
 270     source_trait_ref: ty::PolyTraitRef<'tcx>,
 271     target_trait_def_id: DefId,
 272 ) -> Vec<ty::PolyTraitRef<'tcx>> {
 273     if source_trait_ref.def_id() == target_trait_def_id {
 274         return vec![source_trait_ref]; // Shortcut the most common case.
 275     }
 276
 277     supertraits(tcx, source_trait_ref).filter(|r| r.def_id() == target_trait_def_id).collect()
 278 }
 279
 280 /// Given a trait `trait_ref`, returns the number of vtable entries
 281 /// that come from `trait_ref`, excluding its supertraits. Used in
 282 /// computing the vtable base for an upcast trait of a trait object.
 283 pub fn count_own_vtable_entries(tcx: TyCtxt<'tcx>, trait_ref: ty::PolyTraitRef<'tcx>) -> usize {
 284     let mut entries = 0;
 285     // Count number of methods and add them to the total offset.
 286     // Skip over associated types and constants.
 287     for trait_item in tcx.associated_items(trait_ref.def_id()).in_definition_order() {
 288         if trait_item.kind == ty::AssocKind::Fn {
 289             entries += 1;
 290         }
 291     }
 292     entries
 293 }
 294
 295 /// Given an upcast trait object described by `object`, returns the
 296 /// index of the method `method_def_id` (which should be part of
 297 /// `object.upcast_trait_ref`) within the vtable for `object`.
 298 pub fn get_vtable_index_of_object_method<N>(
 299     tcx: TyCtxt<'tcx>,
 300     object: &super::VtableObjectData<'tcx, N>,
 301     method_def_id: DefId,
 302 ) -> usize {
 303     // Count number of methods preceding the one we are selecting and
 304     // add them to the total offset.
 305     // Skip over associated types and constants.
 306     let mut entries = object.vtable_base;
 307     for trait_item in tcx.associated_items(object.upcast_trait_ref.def_id()).in_definition_order() {
 308         if trait_item.def_id == method_def_id {
 309             // The item with the ID we were given really ought to be a method.
 310             assert_eq!(trait_item.kind, ty::AssocKind::Fn);
 311             return entries;
 312         }
 313         if trait_item.kind == ty::AssocKind::Fn {
 314             entries += 1;
 315         }
 316     }
 317
 318     bug!("get_vtable_index_of_object_method: {:?} was not found", method_def_id);
 319 }
 320
 321 pub fn closure_trait_ref_and_return_type(
 322     tcx: TyCtxt<'tcx>,
 323     fn_trait_def_id: DefId,
 324     self_ty: Ty<'tcx>,
 325     sig: ty::PolyFnSig<'tcx>,
 326     tuple_arguments: TupleArgumentsFlag,
 327 ) -> ty::Binder<(ty::TraitRef<'tcx>, Ty<'tcx>)> {
 328     let arguments_tuple = match tuple_arguments {
 329         TupleArgumentsFlag::No => sig.skip_binder().inputs()[0],
 330         TupleArgumentsFlag::Yes => tcx.intern_tup(sig.skip_binder().inputs()),
 331     };
 332     let trait_ref = ty::TraitRef {
 333         def_id: fn_trait_def_id,
 334         substs: tcx.mk_substs_trait(self_ty, &[arguments_tuple.into()]),
 335     };
 336     ty::Binder::bind((trait_ref, sig.skip_binder().output()))
 337 }
 338
 339 pub fn generator_trait_ref_and_outputs(
 340     tcx: TyCtxt<'tcx>,
 341     fn_trait_def_id: DefId,
 342     self_ty: Ty<'tcx>,
 343     sig: ty::PolyGenSig<'tcx>,
 344 ) -> ty::Binder<(ty::TraitRef<'tcx>, Ty<'tcx>, Ty<'tcx>)> {
 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     ty::Binder::bind((trait_ref, sig.skip_binder().yield_ty, sig.skip_binder().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 }