compiler/rustc_trait_selection/src/traits/util.rs

   1 use rustc_errors::Diagnostic;
   2 use rustc_span::Span;
   3 use smallvec::SmallVec;
   4
   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};
   9
  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::*};
  14
  15 ///////////////////////////////////////////////////////////////////////////
  16 // `TraitAliasExpander` iterator
  17 ///////////////////////////////////////////////////////////////////////////
  18
  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> {
  28     tcx: TyCtxt<'tcx>,
  29     stack: Vec<TraitAliasExpansionInfo<'tcx>>,
  30 }
  31
  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]>,
  36 }
  37
  38 impl<'tcx> TraitAliasExpansionInfo<'tcx> {
  39     fn new(trait_ref: ty::PolyTraitRef<'tcx>, span: Span) -> Self {
  40         Self { path: smallvec![(trait_ref, span)] }
  41     }
  42
  43     /// Adds diagnostic labels to `diag` for the expansion path of a trait through all intermediate
  44     /// trait aliases.
  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));
  50             }
  51         }
  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
  54             // redundant labels.
  55             diag.span_label(
  56                 self.bottom().1,
  57                 format!("trait alias used in trait object type ({})", use_desc),
  58             );
  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(tcx);
 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(tcx)) == 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         debug!(?predicates);
 121
 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))
 126         });
 127         debug!("expand_trait_aliases: items={:?}", items.clone().collect::<Vec<_>>());
 128
 129         self.stack.extend(items);
 130
 131         false
 132     }
 133 }
 134
 135 impl<'tcx> Iterator for TraitAliasExpander<'tcx> {
 136     type Item = TraitAliasExpansionInfo<'tcx>;
 137
 138     fn size_hint(&self) -> (usize, Option<usize>) {
 139         (self.stack.len(), None)
 140     }
 141
 142     fn next(&mut self) -> Option<TraitAliasExpansionInfo<'tcx>> {
 143         while let Some(item) = self.stack.pop() {
 144             if self.expand(&item) {
 145                 return Some(item);
 146             }
 147         }
 148         None
 149     }
 150 }
 151
 152 ///////////////////////////////////////////////////////////////////////////
 153 // Iterator over def-IDs of supertraits
 154 ///////////////////////////////////////////////////////////////////////////
 155
 156 pub struct SupertraitDefIds<'tcx> {
 157     tcx: TyCtxt<'tcx>,
 158     stack: Vec<DefId>,
 159     visited: FxHashSet<DefId>,
 160 }
 161
 162 pub fn supertrait_def_ids(tcx: TyCtxt<'_>, trait_def_id: DefId) -> SupertraitDefIds<'_> {
 163     SupertraitDefIds {
 164         tcx,
 165         stack: vec![trait_def_id],
 166         visited: Some(trait_def_id).into_iter().collect(),
 167     }
 168 }
 169
 170 impl Iterator for SupertraitDefIds<'_> {
 171     type Item = DefId;
 172
 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;
 177         self.stack.extend(
 178             predicates
 179                 .predicates
 180                 .iter()
 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)),
 184         );
 185         Some(def_id)
 186     }
 187 }
 188
 189 ///////////////////////////////////////////////////////////////////////////
 190 // Other
 191 ///////////////////////////////////////////////////////////////////////////
 192
 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>,
 199     impl_def_id: DefId,
 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);
 206
 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);
 213
 214     let impl_obligations = impl_obligations
 215         .chain(normalization_obligations1.into_iter())
 216         .chain(normalization_obligations2.into_iter());
 217
 218     (subject, impl_obligations)
 219 }
 220
 221 pub fn predicate_for_trait_ref<'tcx>(
 222     tcx: TyCtxt<'tcx>,
 223     cause: ObligationCause<'tcx>,
 224     param_env: ty::ParamEnv<'tcx>,
 225     trait_ref: ty::TraitRef<'tcx>,
 226     recursion_depth: usize,
 227 ) -> PredicateObligation<'tcx> {
 228     Obligation {
 229         cause,
 230         param_env,
 231         recursion_depth,
 232         predicate: ty::Binder::dummy(trait_ref).without_const().to_predicate(tcx),
 233     }
 234 }
 235
 236 pub fn predicate_for_trait_def<'tcx>(
 237     tcx: TyCtxt<'tcx>,
 238     param_env: ty::ParamEnv<'tcx>,
 239     cause: ObligationCause<'tcx>,
 240     trait_def_id: DefId,
 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)
 246 }
 247
 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
 250 /// supertrait.
 251 pub fn upcast_choices<'tcx>(
 252     tcx: TyCtxt<'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.
 258     }
 259
 260     supertraits(tcx, source_trait_ref).filter(|r| r.def_id() == target_trait_def_id).collect()
 261 }
 262
 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>(
 267     tcx: TyCtxt<'tcx>,
 268     object: &super::ImplSourceObjectData<'tcx, N>,
 269     method_def_id: DefId,
 270 ) -> Option<usize> {
 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())
 275         .iter()
 276         .copied()
 277         .position(|def_id| def_id == method_def_id)
 278     {
 279         Some(object.vtable_base + index)
 280     } else {
 281         None
 282     }
 283 }
 284
 285 pub fn closure_trait_ref_and_return_type<'tcx>(
 286     tcx: TyCtxt<'tcx>,
 287     fn_trait_def_id: DefId,
 288     self_ty: Ty<'tcx>,
 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()),
 296     };
 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()))
 299 }
 300
 301 pub fn generator_trait_ref_and_outputs<'tcx>(
 302     tcx: TyCtxt<'tcx>,
 303     fn_trait_def_id: DefId,
 304     self_ty: Ty<'tcx>,
 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))
 310 }
 311
 312 pub fn future_trait_ref_and_outputs<'tcx>(
 313     tcx: TyCtxt<'tcx>,
 314     fn_trait_def_id: DefId,
 315     self_ty: Ty<'tcx>,
 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))
 321 }
 322
 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()
 326 }
 327
 328 pub enum TupleArgumentsFlag {
 329     Yes,
 330     No,
 331 }