rustc_infer/traits/
util.rs

1use rustc_data_structures::fx::FxHashSet;
2pub use rustc_middle::ty::elaborate::*;
3use rustc_middle::ty::{self, TyCtxt, Unnormalized};
4use rustc_span::{Ident, Span};
5
6use crate::traits::{self, Obligation, ObligationCauseCode, PredicateObligation};
7
8pub fn anonymize_predicate<'tcx>(
9    tcx: TyCtxt<'tcx>,
10    pred: ty::Predicate<'tcx>,
11) -> ty::Predicate<'tcx> {
12    let new = tcx.anonymize_bound_vars(pred.kind());
13    tcx.reuse_or_mk_predicate(pred, new)
14}
15
16pub struct PredicateSet<'tcx> {
17    tcx: TyCtxt<'tcx>,
18    set: FxHashSet<ty::Predicate<'tcx>>,
19}
20
21impl<'tcx> PredicateSet<'tcx> {
22    pub fn new(tcx: TyCtxt<'tcx>) -> Self {
23        Self { tcx, set: Default::default() }
24    }
25
26    /// Adds a predicate to the set.
27    ///
28    /// Returns whether the predicate was newly inserted. That is:
29    /// - If the set did not previously contain this predicate, `true` is returned.
30    /// - If the set already contained this predicate, `false` is returned,
31    ///   and the set is not modified: original predicate is not replaced,
32    ///   and the predicate passed as argument is dropped.
33    pub fn insert(&mut self, pred: ty::Predicate<'tcx>) -> bool {
34        // We have to be careful here because we want
35        //
36        //    for<'a> Foo<&'a i32>
37        //
38        // and
39        //
40        //    for<'b> Foo<&'b i32>
41        //
42        // to be considered equivalent. So normalize all late-bound
43        // regions before we throw things into the underlying set.
44        self.set.insert(anonymize_predicate(self.tcx, pred))
45    }
46}
47
48impl<'tcx> Extend<ty::Predicate<'tcx>> for PredicateSet<'tcx> {
49    fn extend<I: IntoIterator<Item = ty::Predicate<'tcx>>>(&mut self, iter: I) {
50        let iter = iter.into_iter();
51        self.set.reserve(iter.size_hint().0);
52        for pred in iter {
53            self.insert(pred);
54        }
55    }
56
57    fn extend_one(&mut self, pred: ty::Predicate<'tcx>) {
58        self.insert(pred);
59    }
60
61    fn extend_reserve(&mut self, additional: usize) {
62        Extend::<ty::Predicate<'tcx>>::extend_reserve(&mut self.set, additional);
63    }
64}
65
66/// For [`Obligation`], a sub-obligation is combined with the current obligation's
67/// param-env and cause code.
68impl<'tcx> Elaboratable<TyCtxt<'tcx>> for PredicateObligation<'tcx> {
69    fn predicate(&self) -> ty::Predicate<'tcx> {
70        self.predicate
71    }
72
73    fn child(&self, clause: ty::Clause<'tcx>) -> Self {
74        Obligation {
75            cause: self.cause.clone(),
76            param_env: self.param_env,
77            recursion_depth: 0,
78            predicate: clause.as_predicate(),
79        }
80    }
81
82    fn child_with_derived_cause(
83        &self,
84        clause: ty::Clause<'tcx>,
85        span: Span,
86        parent_trait_pred: ty::PolyTraitClause<'tcx>,
87        index: usize,
88    ) -> Self {
89        let cause = self.cause.clone().derived_cause(parent_trait_pred, |derived| {
90            ObligationCauseCode::ImplDerived(Box::new(traits::ImplDerivedCause {
91                derived,
92                impl_or_alias_def_id: parent_trait_pred.def_id(),
93                impl_def_clause_index: Some(index),
94                span,
95            }))
96        });
97        Obligation {
98            cause,
99            param_env: self.param_env,
100            recursion_depth: 0,
101            predicate: clause.as_predicate(),
102        }
103    }
104}
105
106/// A specialized variant of `elaborate` that only elaborates trait references that may
107/// define the given associated item with the name `assoc_name`. It uses the
108/// `explicit_supertraits_containing_assoc_item` query to avoid enumerating super-predicates that
109/// aren't related to `assoc_item`. This is used when resolving types like `Self::Item` or
110/// `T::Item` and helps to avoid cycle errors (see e.g. #35237).
111pub fn transitive_bounds_that_define_assoc_item<'tcx>(
112    tcx: TyCtxt<'tcx>,
113    trait_refs: impl Iterator<Item = ty::PolyTraitRef<'tcx>>,
114    assoc_name: Ident,
115) -> impl Iterator<Item = ty::PolyTraitRef<'tcx>> {
116    let mut seen = FxHashSet::default();
117    let mut stack: Vec<_> = trait_refs.collect();
118
119    std::iter::from_fn(move || {
120        while let Some(trait_ref) = stack.pop() {
121            if !seen.insert(tcx.anonymize_bound_vars(trait_ref)) {
122                continue;
123            }
124
125            stack.extend(
126                tcx.explicit_supertraits_containing_assoc_item((trait_ref.def_id(), assoc_name))
127                    .iter_identity_copied()
128                    .map(Unnormalized::skip_norm_wip)
129                    .map(|(clause, _)| clause.instantiate_supertrait(tcx, trait_ref))
130                    .filter_map(|clause| clause.as_trait_clause())
131                    .filter(|clause| clause.polarity() == ty::ClausePolarity::Positive)
132                    .map(|clause| clause.map_bound(|clause| clause.trait_ref)),
133            );
134
135            return Some(trait_ref);
136        }
137
138        None
139    })
140}
rustc_infer/traits/util.rs

rustc_infer/traits/
util.rs
