rustc_trait_selection/traits/
util.rs

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

rustc_trait_selection/traits/
util.rs
