rustc_infer/traits/
util.rs

Help
1use rustc_data_structures::fx::FxHashSet;
2use rustc_middle::ty::{self, TyCtxt};
3use rustc_span::{Ident, Span};
4pub use rustc_type_ir::elaborate::*;
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        for pred in iter {
51            self.insert(pred);
52        }
53    }
54
55    fn extend_one(&mut self, pred: ty::Predicate<'tcx>) {
56        self.insert(pred);
57    }
58
59    fn extend_reserve(&mut self, additional: usize) {
60        Extend::<ty::Predicate<'tcx>>::extend_reserve(&mut self.set, additional);
61    }
62}
63
64/// For [`Obligation`], a sub-obligation is combined with the current obligation's
65/// param-env and cause code.
66impl<'tcx> Elaboratable<TyCtxt<'tcx>> for PredicateObligation<'tcx> {
67    fn predicate(&self) -> ty::Predicate<'tcx> {
68        self.predicate
69    }
70
71    fn child(&self, clause: ty::Clause<'tcx>) -> Self {
72        Obligation {
73            cause: self.cause.clone(),
74            param_env: self.param_env,
75            recursion_depth: 0,
76            predicate: clause.as_predicate(),
77        }
78    }
79
80    fn child_with_derived_cause(
81        &self,
82        clause: ty::Clause<'tcx>,
83        span: Span,
84        parent_trait_pred: ty::PolyTraitPredicate<'tcx>,
85        index: usize,
86    ) -> Self {
87        let cause = self.cause.clone().derived_cause(parent_trait_pred, |derived| {
88            ObligationCauseCode::ImplDerived(Box::new(traits::ImplDerivedCause {
89                derived,
90                impl_or_alias_def_id: parent_trait_pred.def_id(),
91                impl_def_predicate_index: Some(index),
92                span,
93            }))
94        });
95        Obligation {
96            cause,
97            param_env: self.param_env,
98            recursion_depth: 0,
99            predicate: clause.as_predicate(),
100        }
101    }
102}
103
104/// A specialized variant of `elaborate` that only elaborates trait references that may
105/// define the given associated item with the name `assoc_name`. It uses the
106/// `explicit_supertraits_containing_assoc_item` query to avoid enumerating super-predicates that
107/// aren't related to `assoc_item`. This is used when resolving types like `Self::Item` or
108/// `T::Item` and helps to avoid cycle errors (see e.g. #35237).
109pub fn transitive_bounds_that_define_assoc_item<'tcx>(
110    tcx: TyCtxt<'tcx>,
111    trait_refs: impl Iterator<Item = ty::PolyTraitRef<'tcx>>,
112    assoc_name: Ident,
113) -> impl Iterator<Item = ty::PolyTraitRef<'tcx>> {
114    let mut seen = FxHashSet::default();
115    let mut stack: Vec<_> = trait_refs.collect();
116
117    std::iter::from_fn(move || {
118        while let Some(trait_ref) = stack.pop() {
119            if !seen.insert(tcx.anonymize_bound_vars(trait_ref)) {
120                continue;
121            }
122
123            stack.extend(
124                tcx.explicit_supertraits_containing_assoc_item((trait_ref.def_id(), assoc_name))
125                    .iter_identity_copied()
126                    .map(|(clause, _)| clause.instantiate_supertrait(tcx, trait_ref))
127                    .filter_map(|clause| clause.as_trait_clause())
128                    .filter(|clause| clause.polarity() == ty::PredicatePolarity::Positive)
129                    .map(|clause| clause.map_bound(|clause| clause.trait_ref)),
130            );
131
132            return Some(trait_ref);
133        }
134
135        None
136    })
137}
rustc_infer/traits/util.rs

rustc_infer/traits/
util.rs
