rustc_type_ir/
elaborate.rs

1use std::marker::PhantomData;
2
3use smallvec::smallvec;
4
5use crate::data_structures::HashSet;
6use crate::inherent::*;
7use crate::outlives::{Component, push_outlives_components};
8use crate::{self as ty, Interner, Upcast as _};
9
10/// "Elaboration" is the process of identifying all the predicates that
11/// are implied by a source predicate. Currently, this basically means
12/// walking the "supertraits" and other similar assumptions. For example,
13/// if we know that `T: Ord`, the elaborator would deduce that `T: PartialOrd`
14/// holds as well. Similarly, if we have `trait Foo: 'static`, and we know that
15/// `T: Foo`, then we know that `T: 'static`.
16pub struct Elaborator<I: Interner, O> {
17    cx: I,
18    stack: Vec<O>,
19    visited: HashSet<ty::Binder<I, ty::PredicateKind<I>>>,
20    mode: Filter,
21}
22
23enum Filter {
24    All,
25    OnlySelf,
26}
27
28/// Describes how to elaborate an obligation into a sub-obligation.
29pub trait Elaboratable<I: Interner> {
30    fn predicate(&self) -> I::Predicate;
31
32    // Makes a new `Self` but with a different clause that comes from elaboration.
33    fn child(&self, clause: I::Clause) -> Self;
34
35    // Makes a new `Self` but with a different clause and a different cause
36    // code (if `Self` has one, such as [`PredicateObligation`]).
37    fn child_with_derived_cause(
38        &self,
39        clause: I::Clause,
40        span: I::Span,
41        parent_trait_pred: ty::Binder<I, ty::TraitPredicate<I>>,
42        index: usize,
43    ) -> Self;
44}
45
46pub struct ClauseWithSupertraitSpan<I: Interner> {
47    pub clause: I::Clause,
48    // Span of the supertrait predicatae that lead to this clause.
49    pub supertrait_span: I::Span,
50}
51impl<I: Interner> ClauseWithSupertraitSpan<I> {
52    pub fn new(clause: I::Clause, span: I::Span) -> Self {
53        ClauseWithSupertraitSpan { clause, supertrait_span: span }
54    }
55}
56impl<I: Interner> Elaboratable<I> for ClauseWithSupertraitSpan<I> {
57    fn predicate(&self) -> <I as Interner>::Predicate {
58        self.clause.as_predicate()
59    }
60
61    fn child(&self, clause: <I as Interner>::Clause) -> Self {
62        ClauseWithSupertraitSpan { clause, supertrait_span: self.supertrait_span }
63    }
64
65    fn child_with_derived_cause(
66        &self,
67        clause: <I as Interner>::Clause,
68        supertrait_span: <I as Interner>::Span,
69        _parent_trait_pred: crate::Binder<I, crate::TraitPredicate<I>>,
70        _index: usize,
71    ) -> Self {
72        ClauseWithSupertraitSpan { clause, supertrait_span }
73    }
74}
75
76pub fn elaborate<I: Interner, O: Elaboratable<I>>(
77    cx: I,
78    obligations: impl IntoIterator<Item = O>,
79) -> Elaborator<I, O> {
80    let mut elaborator =
81        Elaborator { cx, stack: Vec::new(), visited: HashSet::default(), mode: Filter::All };
82    elaborator.extend_deduped(obligations);
83    elaborator
84}
85
86impl<I: Interner, O: Elaboratable<I>> Elaborator<I, O> {
87    fn extend_deduped(&mut self, obligations: impl IntoIterator<Item = O>) {
88        // Only keep those bounds that we haven't already seen.
89        // This is necessary to prevent infinite recursion in some
90        // cases. One common case is when people define
91        // `trait Sized: Sized { }` rather than `trait Sized { }`.
92        self.stack.extend(
93            obligations.into_iter().filter(|o| {
94                self.visited.insert(self.cx.anonymize_bound_vars(o.predicate().kind()))
95            }),
96        );
97    }
98
99    /// Filter to only the supertraits of trait predicates, i.e. only the predicates
100    /// that have `Self` as their self type, instead of all implied predicates.
101    pub fn filter_only_self(mut self) -> Self {
102        self.mode = Filter::OnlySelf;
103        self
104    }
105
106    fn elaborate(&mut self, elaboratable: &O) {
107        let cx = self.cx;
108
109        // We only elaborate clauses.
110        let Some(clause) = elaboratable.predicate().as_clause() else {
111            return;
112        };
113
114        let bound_clause = clause.kind();
115        match bound_clause.skip_binder() {
116            ty::ClauseKind::Trait(data) => {
117                // Negative trait bounds do not imply any supertrait bounds
118                if data.polarity != ty::PredicatePolarity::Positive {
119                    return;
120                }
121
122                let map_to_child_clause =
123                    |(index, (clause, span)): (usize, (I::Clause, I::Span))| {
124                        elaboratable.child_with_derived_cause(
125                            clause.instantiate_supertrait(cx, bound_clause.rebind(data.trait_ref)),
126                            span,
127                            bound_clause.rebind(data),
128                            index,
129                        )
130                    };
131
132                // Get predicates implied by the trait, or only super predicates if we only care about self predicates.
133                match self.mode {
134                    Filter::All => self.extend_deduped(
135                        cx.explicit_implied_predicates_of(data.def_id())
136                            .iter_identity()
137                            .enumerate()
138                            .map(map_to_child_clause),
139                    ),
140                    Filter::OnlySelf => self.extend_deduped(
141                        cx.explicit_super_predicates_of(data.def_id())
142                            .iter_identity()
143                            .enumerate()
144                            .map(map_to_child_clause),
145                    ),
146                };
147            }
148            // `T: ~const Trait` implies `T: ~const Supertrait`.
149            ty::ClauseKind::HostEffect(data) => self.extend_deduped(
150                cx.explicit_implied_const_bounds(data.def_id()).iter_identity().map(|trait_ref| {
151                    elaboratable.child(
152                        trait_ref
153                            .to_host_effect_clause(cx, data.constness)
154                            .instantiate_supertrait(cx, bound_clause.rebind(data.trait_ref)),
155                    )
156                }),
157            ),
158            ty::ClauseKind::TypeOutlives(ty::OutlivesPredicate(ty_max, r_min)) => {
159                // We know that `T: 'a` for some type `T`. We can
160                // often elaborate this. For example, if we know that
161                // `[U]: 'a`, that implies that `U: 'a`. Similarly, if
162                // we know `&'a U: 'b`, then we know that `'a: 'b` and
163                // `U: 'b`.
164                //
165                // We can basically ignore bound regions here. So for
166                // example `for<'c> Foo<'a,'c>: 'b` can be elaborated to
167                // `'a: 'b`.
168
169                // Ignore `for<'a> T: 'a` -- we might in the future
170                // consider this as evidence that `T: 'static`, but
171                // I'm a bit wary of such constructions and so for now
172                // I want to be conservative. --nmatsakis
173                if r_min.is_bound() {
174                    return;
175                }
176
177                let mut components = smallvec![];
178                push_outlives_components(cx, ty_max, &mut components);
179                self.extend_deduped(
180                    components
181                        .into_iter()
182                        .filter_map(|component| elaborate_component_to_clause(cx, component, r_min))
183                        .map(|clause| elaboratable.child(bound_clause.rebind(clause).upcast(cx))),
184                );
185            }
186            ty::ClauseKind::RegionOutlives(..) => {
187                // Nothing to elaborate from `'a: 'b`.
188            }
189            ty::ClauseKind::WellFormed(..) => {
190                // Currently, we do not elaborate WF predicates,
191                // although we easily could.
192            }
193            ty::ClauseKind::Projection(..) => {
194                // Nothing to elaborate in a projection predicate.
195            }
196            ty::ClauseKind::ConstEvaluatable(..) => {
197                // Currently, we do not elaborate const-evaluatable
198                // predicates.
199            }
200            ty::ClauseKind::ConstArgHasType(..) => {
201                // Nothing to elaborate
202            }
203        }
204    }
205}
206
207fn elaborate_component_to_clause<I: Interner>(
208    cx: I,
209    component: Component<I>,
210    outlives_region: I::Region,
211) -> Option<ty::ClauseKind<I>> {
212    match component {
213        Component::Region(r) => {
214            if r.is_bound() {
215                None
216            } else {
217                Some(ty::ClauseKind::RegionOutlives(ty::OutlivesPredicate(r, outlives_region)))
218            }
219        }
220
221        Component::Param(p) => {
222            let ty = Ty::new_param(cx, p);
223            Some(ty::ClauseKind::TypeOutlives(ty::OutlivesPredicate(ty, outlives_region)))
224        }
225
226        Component::Placeholder(p) => {
227            let ty = Ty::new_placeholder(cx, p);
228            Some(ty::ClauseKind::TypeOutlives(ty::OutlivesPredicate(ty, outlives_region)))
229        }
230
231        Component::UnresolvedInferenceVariable(_) => None,
232
233        Component::Alias(alias_ty) => {
234            // We might end up here if we have `Foo<<Bar as Baz>::Assoc>: 'a`.
235            // With this, we can deduce that `<Bar as Baz>::Assoc: 'a`.
236            Some(ty::ClauseKind::TypeOutlives(ty::OutlivesPredicate(
237                alias_ty.to_ty(cx),
238                outlives_region,
239            )))
240        }
241
242        Component::EscapingAlias(_) => {
243            // We might be able to do more here, but we don't
244            // want to deal with escaping vars right now.
245            None
246        }
247    }
248}
249
250impl<I: Interner, O: Elaboratable<I>> Iterator for Elaborator<I, O> {
251    type Item = O;
252
253    fn size_hint(&self) -> (usize, Option<usize>) {
254        (self.stack.len(), None)
255    }
256
257    fn next(&mut self) -> Option<Self::Item> {
258        // Extract next item from top-most stack frame, if any.
259        if let Some(obligation) = self.stack.pop() {
260            self.elaborate(&obligation);
261            Some(obligation)
262        } else {
263            None
264        }
265    }
266}
267
268///////////////////////////////////////////////////////////////////////////
269// Supertrait iterator
270///////////////////////////////////////////////////////////////////////////
271
272/// Computes the def-ids of the transitive supertraits of `trait_def_id`. This (intentionally)
273/// does not compute the full elaborated super-predicates but just the set of def-ids. It is used
274/// to identify which traits may define a given associated type to help avoid cycle errors,
275/// and to make size estimates for vtable layout computation.
276pub fn supertrait_def_ids<I: Interner>(
277    cx: I,
278    trait_def_id: I::DefId,
279) -> impl Iterator<Item = I::DefId> {
280    let mut set = HashSet::default();
281    let mut stack = vec![trait_def_id];
282
283    set.insert(trait_def_id);
284
285    std::iter::from_fn(move || {
286        let trait_def_id = stack.pop()?;
287
288        for (predicate, _) in cx.explicit_super_predicates_of(trait_def_id).iter_identity() {
289            if let ty::ClauseKind::Trait(data) = predicate.kind().skip_binder() {
290                if set.insert(data.def_id()) {
291                    stack.push(data.def_id());
292                }
293            }
294        }
295
296        Some(trait_def_id)
297    })
298}
299
300pub fn supertraits<I: Interner>(
301    cx: I,
302    trait_ref: ty::Binder<I, ty::TraitRef<I>>,
303) -> FilterToTraits<I, Elaborator<I, I::Clause>> {
304    elaborate(cx, [trait_ref.upcast(cx)]).filter_only_self().filter_to_traits()
305}
306
307impl<I: Interner> Elaborator<I, I::Clause> {
308    fn filter_to_traits(self) -> FilterToTraits<I, Self> {
309        FilterToTraits { _cx: PhantomData, base_iterator: self }
310    }
311}
312
313/// A filter around an iterator of predicates that makes it yield up
314/// just trait references.
315pub struct FilterToTraits<I: Interner, It: Iterator<Item = I::Clause>> {
316    _cx: PhantomData<I>,
317    base_iterator: It,
318}
319
320impl<I: Interner, It: Iterator<Item = I::Clause>> Iterator for FilterToTraits<I, It> {
321    type Item = ty::Binder<I, ty::TraitRef<I>>;
322
323    fn next(&mut self) -> Option<ty::Binder<I, ty::TraitRef<I>>> {
324        while let Some(pred) = self.base_iterator.next() {
325            if let Some(data) = pred.as_trait_clause() {
326                return Some(data.map_bound(|t| t.trait_ref));
327            }
328        }
329        None
330    }
331
332    fn size_hint(&self) -> (usize, Option<usize>) {
333        let (_, upper) = self.base_iterator.size_hint();
334        (0, upper)
335    }
336}