rustc_trait_selection/traits/
util.rs

1use std::collections::{BTreeMap, VecDeque};
2
3use rustc_data_structures::fx::{FxHashSet, FxIndexMap};
4use rustc_hir::LangItem;
5use rustc_hir::def_id::DefId;
6use rustc_infer::infer::InferCtxt;
7pub use rustc_infer::traits::util::*;
8use rustc_middle::bug;
9use rustc_middle::ty::{
10    self, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable, TypeVisitableExt,
11};
12use rustc_span::Span;
13use smallvec::{SmallVec, smallvec};
14use tracing::debug;
15
16/// Return the trait and projection predicates that come from eagerly expanding the
17/// trait aliases in the list of clauses. For each trait predicate, record a stack
18/// of spans that trace from the user-written trait alias bound. For projection predicates,
19/// just record the span of the projection itself.
20///
21/// For trait aliases, we don't deduplicte the predicates, since we currently do not
22/// consider duplicated traits as a single trait for the purposes of our "one trait principal"
23/// restriction; however, for projections we do deduplicate them.
24///
25/// ```rust,ignore (fails)
26/// trait Bar {}
27/// trait Foo = Bar + Bar;
28///
29/// let dyn_incompatible: dyn Foo; // bad, two `Bar` principals.
30/// ```
31pub fn expand_trait_aliases<'tcx>(
32    tcx: TyCtxt<'tcx>,
33    clauses: impl IntoIterator<Item = (ty::Clause<'tcx>, Span)>,
34) -> (
35    Vec<(ty::PolyTraitPredicate<'tcx>, SmallVec<[Span; 1]>)>,
36    Vec<(ty::PolyProjectionPredicate<'tcx>, Span)>,
37) {
38    let mut trait_preds = vec![];
39    let mut projection_preds = vec![];
40    let mut seen_projection_preds = FxHashSet::default();
41
42    let mut queue: VecDeque<_> = clauses.into_iter().map(|(p, s)| (p, smallvec![s])).collect();
43
44    while let Some((clause, spans)) = queue.pop_front() {
45        match clause.kind().skip_binder() {
46            ty::ClauseKind::Trait(trait_pred) => {
47                if tcx.is_trait_alias(trait_pred.def_id()) {
48                    queue.extend(
49                        tcx.explicit_super_predicates_of(trait_pred.def_id())
50                            .iter_identity_copied()
51                            .map(|(super_clause, span)| {
52                                let mut spans = spans.clone();
53                                spans.push(span);
54                                (
55                                    super_clause.instantiate_supertrait(
56                                        tcx,
57                                        clause.kind().rebind(trait_pred.trait_ref),
58                                    ),
59                                    spans,
60                                )
61                            }),
62                    );
63                } else {
64                    trait_preds.push((clause.kind().rebind(trait_pred), spans));
65                }
66            }
67            ty::ClauseKind::Projection(projection_pred) => {
68                let projection_pred = clause.kind().rebind(projection_pred);
69                if !seen_projection_preds.insert(tcx.anonymize_bound_vars(projection_pred)) {
70                    continue;
71                }
72                projection_preds.push((projection_pred, *spans.last().unwrap()));
73            }
74            ty::ClauseKind::RegionOutlives(..)
75            | ty::ClauseKind::TypeOutlives(..)
76            | ty::ClauseKind::ConstArgHasType(_, _)
77            | ty::ClauseKind::WellFormed(_)
78            | ty::ClauseKind::ConstEvaluatable(_)
79            | ty::ClauseKind::HostEffect(..) => {}
80        }
81    }
82
83    (trait_preds, projection_preds)
84}
85
86///////////////////////////////////////////////////////////////////////////
87// Other
88///////////////////////////////////////////////////////////////////////////
89
90/// Casts a trait reference into a reference to one of its super
91/// traits; returns `None` if `target_trait_def_id` is not a
92/// supertrait.
93pub fn upcast_choices<'tcx>(
94    tcx: TyCtxt<'tcx>,
95    source_trait_ref: ty::PolyTraitRef<'tcx>,
96    target_trait_def_id: DefId,
97) -> Vec<ty::PolyTraitRef<'tcx>> {
98    if source_trait_ref.def_id() == target_trait_def_id {
99        return vec![source_trait_ref]; // Shortcut the most common case.
100    }
101
102    supertraits(tcx, source_trait_ref).filter(|r| r.def_id() == target_trait_def_id).collect()
103}
104
105pub(crate) fn closure_trait_ref_and_return_type<'tcx>(
106    tcx: TyCtxt<'tcx>,
107    fn_trait_def_id: DefId,
108    self_ty: Ty<'tcx>,
109    sig: ty::PolyFnSig<'tcx>,
110    tuple_arguments: TupleArgumentsFlag,
111) -> ty::Binder<'tcx, (ty::TraitRef<'tcx>, Ty<'tcx>)> {
112    assert!(!self_ty.has_escaping_bound_vars());
113    let arguments_tuple = match tuple_arguments {
114        TupleArgumentsFlag::No => sig.skip_binder().inputs()[0],
115        TupleArgumentsFlag::Yes => Ty::new_tup(tcx, sig.skip_binder().inputs()),
116    };
117    let trait_ref = ty::TraitRef::new(tcx, fn_trait_def_id, [self_ty, arguments_tuple]);
118    sig.map_bound(|sig| (trait_ref, sig.output()))
119}
120
121pub(crate) fn coroutine_trait_ref_and_outputs<'tcx>(
122    tcx: TyCtxt<'tcx>,
123    fn_trait_def_id: DefId,
124    self_ty: Ty<'tcx>,
125    sig: ty::GenSig<TyCtxt<'tcx>>,
126) -> (ty::TraitRef<'tcx>, Ty<'tcx>, Ty<'tcx>) {
127    assert!(!self_ty.has_escaping_bound_vars());
128    let trait_ref = ty::TraitRef::new(tcx, fn_trait_def_id, [self_ty, sig.resume_ty]);
129    (trait_ref, sig.yield_ty, sig.return_ty)
130}
131
132pub(crate) fn future_trait_ref_and_outputs<'tcx>(
133    tcx: TyCtxt<'tcx>,
134    fn_trait_def_id: DefId,
135    self_ty: Ty<'tcx>,
136    sig: ty::GenSig<TyCtxt<'tcx>>,
137) -> (ty::TraitRef<'tcx>, Ty<'tcx>) {
138    assert!(!self_ty.has_escaping_bound_vars());
139    let trait_ref = ty::TraitRef::new(tcx, fn_trait_def_id, [self_ty]);
140    (trait_ref, sig.return_ty)
141}
142
143pub(crate) fn iterator_trait_ref_and_outputs<'tcx>(
144    tcx: TyCtxt<'tcx>,
145    iterator_def_id: DefId,
146    self_ty: Ty<'tcx>,
147    sig: ty::GenSig<TyCtxt<'tcx>>,
148) -> (ty::TraitRef<'tcx>, Ty<'tcx>) {
149    assert!(!self_ty.has_escaping_bound_vars());
150    let trait_ref = ty::TraitRef::new(tcx, iterator_def_id, [self_ty]);
151    (trait_ref, sig.yield_ty)
152}
153
154pub(crate) fn async_iterator_trait_ref_and_outputs<'tcx>(
155    tcx: TyCtxt<'tcx>,
156    async_iterator_def_id: DefId,
157    self_ty: Ty<'tcx>,
158    sig: ty::GenSig<TyCtxt<'tcx>>,
159) -> (ty::TraitRef<'tcx>, Ty<'tcx>) {
160    assert!(!self_ty.has_escaping_bound_vars());
161    let trait_ref = ty::TraitRef::new(tcx, async_iterator_def_id, [self_ty]);
162    (trait_ref, sig.yield_ty)
163}
164
165pub fn impl_item_is_final(tcx: TyCtxt<'_>, assoc_item: &ty::AssocItem) -> bool {
166    assoc_item.defaultness(tcx).is_final()
167        && tcx.defaultness(assoc_item.container_id(tcx)).is_final()
168}
169
170pub(crate) enum TupleArgumentsFlag {
171    Yes,
172    No,
173}
174
175/// Executes `f` on `value` after replacing all escaping bound variables with placeholders
176/// and then replaces these placeholders with the original bound variables in the result.
177///
178/// In most places, bound variables should be replaced right when entering a binder, making
179/// this function unnecessary. However, normalization currently does not do that, so we have
180/// to do this lazily.
181///
182/// You should not add any additional uses of this function, at least not without first
183/// discussing it with t-types.
184///
185/// FIXME(@lcnr): We may even consider experimenting with eagerly replacing bound vars during
186/// normalization as well, at which point this function will be unnecessary and can be removed.
187pub fn with_replaced_escaping_bound_vars<
188    'a,
189    'tcx,
190    T: TypeFoldable<TyCtxt<'tcx>>,
191    R: TypeFoldable<TyCtxt<'tcx>>,
192>(
193    infcx: &'a InferCtxt<'tcx>,
194    universe_indices: &'a mut Vec<Option<ty::UniverseIndex>>,
195    value: T,
196    f: impl FnOnce(T) -> R,
197) -> R {
198    if value.has_escaping_bound_vars() {
199        let (value, mapped_regions, mapped_types, mapped_consts) =
200            BoundVarReplacer::replace_bound_vars(infcx, universe_indices, value);
201        let result = f(value);
202        PlaceholderReplacer::replace_placeholders(
203            infcx,
204            mapped_regions,
205            mapped_types,
206            mapped_consts,
207            universe_indices,
208            result,
209        )
210    } else {
211        f(value)
212    }
213}
214
215pub struct BoundVarReplacer<'a, 'tcx> {
216    infcx: &'a InferCtxt<'tcx>,
217    // These three maps track the bound variable that were replaced by placeholders. It might be
218    // nice to remove these since we already have the `kind` in the placeholder; we really just need
219    // the `var` (but we *could* bring that into scope if we were to track them as we pass them).
220    mapped_regions: FxIndexMap<ty::PlaceholderRegion, ty::BoundRegion>,
221    mapped_types: FxIndexMap<ty::PlaceholderType, ty::BoundTy>,
222    mapped_consts: BTreeMap<ty::PlaceholderConst, ty::BoundVar>,
223    // The current depth relative to *this* folding, *not* the entire normalization. In other words,
224    // the depth of binders we've passed here.
225    current_index: ty::DebruijnIndex,
226    // The `UniverseIndex` of the binding levels above us. These are optional, since we are lazy:
227    // we don't actually create a universe until we see a bound var we have to replace.
228    universe_indices: &'a mut Vec<Option<ty::UniverseIndex>>,
229}
230
231impl<'a, 'tcx> BoundVarReplacer<'a, 'tcx> {
232    /// Returns `Some` if we *were* able to replace bound vars. If there are any bound vars that
233    /// use a binding level above `universe_indices.len()`, we fail.
234    pub fn replace_bound_vars<T: TypeFoldable<TyCtxt<'tcx>>>(
235        infcx: &'a InferCtxt<'tcx>,
236        universe_indices: &'a mut Vec<Option<ty::UniverseIndex>>,
237        value: T,
238    ) -> (
239        T,
240        FxIndexMap<ty::PlaceholderRegion, ty::BoundRegion>,
241        FxIndexMap<ty::PlaceholderType, ty::BoundTy>,
242        BTreeMap<ty::PlaceholderConst, ty::BoundVar>,
243    ) {
244        let mapped_regions: FxIndexMap<ty::PlaceholderRegion, ty::BoundRegion> =
245            FxIndexMap::default();
246        let mapped_types: FxIndexMap<ty::PlaceholderType, ty::BoundTy> = FxIndexMap::default();
247        let mapped_consts: BTreeMap<ty::PlaceholderConst, ty::BoundVar> = BTreeMap::new();
248
249        let mut replacer = BoundVarReplacer {
250            infcx,
251            mapped_regions,
252            mapped_types,
253            mapped_consts,
254            current_index: ty::INNERMOST,
255            universe_indices,
256        };
257
258        let value = value.fold_with(&mut replacer);
259
260        (value, replacer.mapped_regions, replacer.mapped_types, replacer.mapped_consts)
261    }
262
263    fn universe_for(&mut self, debruijn: ty::DebruijnIndex) -> ty::UniverseIndex {
264        let infcx = self.infcx;
265        let index =
266            self.universe_indices.len() + self.current_index.as_usize() - debruijn.as_usize() - 1;
267        let universe = self.universe_indices[index].unwrap_or_else(|| {
268            for i in self.universe_indices.iter_mut().take(index + 1) {
269                *i = i.or_else(|| Some(infcx.create_next_universe()))
270            }
271            self.universe_indices[index].unwrap()
272        });
273        universe
274    }
275}
276
277impl<'tcx> TypeFolder<TyCtxt<'tcx>> for BoundVarReplacer<'_, 'tcx> {
278    fn cx(&self) -> TyCtxt<'tcx> {
279        self.infcx.tcx
280    }
281
282    fn fold_binder<T: TypeFoldable<TyCtxt<'tcx>>>(
283        &mut self,
284        t: ty::Binder<'tcx, T>,
285    ) -> ty::Binder<'tcx, T> {
286        self.current_index.shift_in(1);
287        let t = t.super_fold_with(self);
288        self.current_index.shift_out(1);
289        t
290    }
291
292    fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
293        match r.kind() {
294            ty::ReBound(debruijn, _)
295                if debruijn.as_usize()
296                    >= self.current_index.as_usize() + self.universe_indices.len() =>
297            {
298                bug!(
299                    "Bound vars {r:#?} outside of `self.universe_indices`: {:#?}",
300                    self.universe_indices
301                );
302            }
303            ty::ReBound(debruijn, br) if debruijn >= self.current_index => {
304                let universe = self.universe_for(debruijn);
305                let p = ty::PlaceholderRegion { universe, bound: br };
306                self.mapped_regions.insert(p, br);
307                ty::Region::new_placeholder(self.infcx.tcx, p)
308            }
309            _ => r,
310        }
311    }
312
313    fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
314        match *t.kind() {
315            ty::Bound(debruijn, _)
316                if debruijn.as_usize() + 1
317                    > self.current_index.as_usize() + self.universe_indices.len() =>
318            {
319                bug!(
320                    "Bound vars {t:#?} outside of `self.universe_indices`: {:#?}",
321                    self.universe_indices
322                );
323            }
324            ty::Bound(debruijn, bound_ty) if debruijn >= self.current_index => {
325                let universe = self.universe_for(debruijn);
326                let p = ty::PlaceholderType { universe, bound: bound_ty };
327                self.mapped_types.insert(p, bound_ty);
328                Ty::new_placeholder(self.infcx.tcx, p)
329            }
330            _ if t.has_vars_bound_at_or_above(self.current_index) => t.super_fold_with(self),
331            _ => t,
332        }
333    }
334
335    fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
336        match ct.kind() {
337            ty::ConstKind::Bound(debruijn, _)
338                if debruijn.as_usize() + 1
339                    > self.current_index.as_usize() + self.universe_indices.len() =>
340            {
341                bug!(
342                    "Bound vars {ct:#?} outside of `self.universe_indices`: {:#?}",
343                    self.universe_indices
344                );
345            }
346            ty::ConstKind::Bound(debruijn, bound_const) if debruijn >= self.current_index => {
347                let universe = self.universe_for(debruijn);
348                let p = ty::PlaceholderConst { universe, bound: bound_const };
349                self.mapped_consts.insert(p, bound_const);
350                ty::Const::new_placeholder(self.infcx.tcx, p)
351            }
352            _ => ct.super_fold_with(self),
353        }
354    }
355
356    fn fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> {
357        if p.has_vars_bound_at_or_above(self.current_index) { p.super_fold_with(self) } else { p }
358    }
359}
360
361/// The inverse of [`BoundVarReplacer`]: replaces placeholders with the bound vars from which they came.
362pub struct PlaceholderReplacer<'a, 'tcx> {
363    infcx: &'a InferCtxt<'tcx>,
364    mapped_regions: FxIndexMap<ty::PlaceholderRegion, ty::BoundRegion>,
365    mapped_types: FxIndexMap<ty::PlaceholderType, ty::BoundTy>,
366    mapped_consts: BTreeMap<ty::PlaceholderConst, ty::BoundVar>,
367    universe_indices: &'a [Option<ty::UniverseIndex>],
368    current_index: ty::DebruijnIndex,
369}
370
371impl<'a, 'tcx> PlaceholderReplacer<'a, 'tcx> {
372    pub fn replace_placeholders<T: TypeFoldable<TyCtxt<'tcx>>>(
373        infcx: &'a InferCtxt<'tcx>,
374        mapped_regions: FxIndexMap<ty::PlaceholderRegion, ty::BoundRegion>,
375        mapped_types: FxIndexMap<ty::PlaceholderType, ty::BoundTy>,
376        mapped_consts: BTreeMap<ty::PlaceholderConst, ty::BoundVar>,
377        universe_indices: &'a [Option<ty::UniverseIndex>],
378        value: T,
379    ) -> T {
380        let mut replacer = PlaceholderReplacer {
381            infcx,
382            mapped_regions,
383            mapped_types,
384            mapped_consts,
385            universe_indices,
386            current_index: ty::INNERMOST,
387        };
388        value.fold_with(&mut replacer)
389    }
390}
391
392impl<'tcx> TypeFolder<TyCtxt<'tcx>> for PlaceholderReplacer<'_, 'tcx> {
393    fn cx(&self) -> TyCtxt<'tcx> {
394        self.infcx.tcx
395    }
396
397    fn fold_binder<T: TypeFoldable<TyCtxt<'tcx>>>(
398        &mut self,
399        t: ty::Binder<'tcx, T>,
400    ) -> ty::Binder<'tcx, T> {
401        if !t.has_placeholders() && !t.has_infer() {
402            return t;
403        }
404        self.current_index.shift_in(1);
405        let t = t.super_fold_with(self);
406        self.current_index.shift_out(1);
407        t
408    }
409
410    fn fold_region(&mut self, r0: ty::Region<'tcx>) -> ty::Region<'tcx> {
411        let r1 = match r0.kind() {
412            ty::ReVar(vid) => self
413                .infcx
414                .inner
415                .borrow_mut()
416                .unwrap_region_constraints()
417                .opportunistic_resolve_var(self.infcx.tcx, vid),
418            _ => r0,
419        };
420
421        let r2 = match r1.kind() {
422            ty::RePlaceholder(p) => {
423                let replace_var = self.mapped_regions.get(&p);
424                match replace_var {
425                    Some(replace_var) => {
426                        let index = self
427                            .universe_indices
428                            .iter()
429                            .position(|u| matches!(u, Some(pu) if *pu == p.universe))
430                            .unwrap_or_else(|| bug!("Unexpected placeholder universe."));
431                        let db = ty::DebruijnIndex::from_usize(
432                            self.universe_indices.len() - index + self.current_index.as_usize() - 1,
433                        );
434                        ty::Region::new_bound(self.cx(), db, *replace_var)
435                    }
436                    None => r1,
437                }
438            }
439            _ => r1,
440        };
441
442        debug!(?r0, ?r1, ?r2, "fold_region");
443
444        r2
445    }
446
447    fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
448        let ty = self.infcx.shallow_resolve(ty);
449        match *ty.kind() {
450            ty::Placeholder(p) => {
451                let replace_var = self.mapped_types.get(&p);
452                match replace_var {
453                    Some(replace_var) => {
454                        let index = self
455                            .universe_indices
456                            .iter()
457                            .position(|u| matches!(u, Some(pu) if *pu == p.universe))
458                            .unwrap_or_else(|| bug!("Unexpected placeholder universe."));
459                        let db = ty::DebruijnIndex::from_usize(
460                            self.universe_indices.len() - index + self.current_index.as_usize() - 1,
461                        );
462                        Ty::new_bound(self.infcx.tcx, db, *replace_var)
463                    }
464                    None => {
465                        if ty.has_infer() {
466                            ty.super_fold_with(self)
467                        } else {
468                            ty
469                        }
470                    }
471                }
472            }
473
474            _ if ty.has_placeholders() || ty.has_infer() => ty.super_fold_with(self),
475            _ => ty,
476        }
477    }
478
479    fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
480        let ct = self.infcx.shallow_resolve_const(ct);
481        if let ty::ConstKind::Placeholder(p) = ct.kind() {
482            let replace_var = self.mapped_consts.get(&p);
483            match replace_var {
484                Some(replace_var) => {
485                    let index = self
486                        .universe_indices
487                        .iter()
488                        .position(|u| matches!(u, Some(pu) if *pu == p.universe))
489                        .unwrap_or_else(|| bug!("Unexpected placeholder universe."));
490                    let db = ty::DebruijnIndex::from_usize(
491                        self.universe_indices.len() - index + self.current_index.as_usize() - 1,
492                    );
493                    ty::Const::new_bound(self.infcx.tcx, db, *replace_var)
494                }
495                None => {
496                    if ct.has_infer() {
497                        ct.super_fold_with(self)
498                    } else {
499                        ct
500                    }
501                }
502            }
503        } else {
504            ct.super_fold_with(self)
505        }
506    }
507}
508
509pub fn sizedness_fast_path<'tcx>(tcx: TyCtxt<'tcx>, predicate: ty::Predicate<'tcx>) -> bool {
510    // Proving `Sized` very often on "obviously sized" types like `&T`, accounts for about 60%
511    // percentage of the predicates we have to prove. No need to canonicalize and all that for
512    // such cases.
513    if let ty::PredicateKind::Clause(ty::ClauseKind::Trait(trait_ref)) =
514        predicate.kind().skip_binder()
515    {
516        if tcx.is_lang_item(trait_ref.def_id(), LangItem::Sized)
517            && trait_ref.self_ty().is_trivially_sized(tcx)
518        {
519            debug!("fast path -- trivial sizedness");
520            return true;
521        }
522    }
523
524    false
525}
rustc_trait_selection/traits/util.rs

rustc_trait_selection/traits/
util.rs
