Skip to main content

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, Region, Unnormalized, 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::TraitClause<I>>,
42        index: usize,
43    ) -> Self;
44}
45
46pub struct ClauseWithSupertraitSpan<I: Interner> {
47    pub clause: I::Clause,
48    // Span of the supertrait predicate that lead to this clause.
49    pub supertrait_span: I::Span,
50}
51
52impl<I: Interner> ClauseWithSupertraitSpan<I> {
53    pub fn new(clause: I::Clause, span: I::Span) -> Self {
54        ClauseWithSupertraitSpan { clause, supertrait_span: span }
55    }
56}
57
58impl<I: Interner> Elaboratable<I> for ClauseWithSupertraitSpan<I> {
59    fn predicate(&self) -> <I as Interner>::Predicate {
60        self.clause.as_predicate()
61    }
62
63    fn child(&self, clause: <I as Interner>::Clause) -> Self {
64        ClauseWithSupertraitSpan { clause, supertrait_span: self.supertrait_span }
65    }
66
67    fn child_with_derived_cause(
68        &self,
69        clause: <I as Interner>::Clause,
70        supertrait_span: <I as Interner>::Span,
71        _parent_trait_pred: crate::Binder<I, crate::TraitClause<I>>,
72        _index: usize,
73    ) -> Self {
74        ClauseWithSupertraitSpan { clause, supertrait_span }
75    }
76}
77
78pub fn elaborate<I: Interner, O: Elaboratable<I>>(
79    cx: I,
80    obligations: impl IntoIterator<Item = O>,
81) -> Elaborator<I, O> {
82    let mut elaborator =
83        Elaborator { cx, stack: Vec::new(), visited: HashSet::default(), mode: Filter::All };
84    elaborator.extend_deduped(obligations);
85    elaborator
86}
87
88impl<I: Interner, O: Elaboratable<I>> Elaborator<I, O> {
89    /// Adds `obligations` to the stack.
90    fn extend_deduped(&mut self, obligations: impl IntoIterator<Item = O>) {
91        // Only keep those bounds that we haven't already seen.
92        // This is necessary to prevent infinite recursion in some
93        // cases. One common case is when people define
94        // `trait Sized: Sized { }` rather than `trait Sized { }`.
95        self.stack.extend(
96            obligations.into_iter().filter(|o| {
97                self.visited.insert(self.cx.anonymize_bound_vars(o.predicate().kind()))
98            }),
99        );
100    }
101
102    /// Filter to only the supertraits of trait predicates, i.e. only the predicates
103    /// that have `Self` as their self type, instead of all implied predicates.
104    pub fn filter_only_self(mut self) -> Self {
105        self.mode = Filter::OnlySelf;
106        self
107    }
108
109    fn elaborate(&mut self, elaboratable: &O) {
110        let cx = self.cx;
111
112        // We only elaborate clauses.
113        let Some(clause) = elaboratable.predicate().as_clause() else {
114            return;
115        };
116
117        let bound_clause = clause.kind();
118        match bound_clause.skip_binder() {
119            ty::ClauseKind::Trait(data) => {
120                // Negative trait bounds do not imply any supertrait bounds
121                if data.polarity != ty::ClausePolarity::Positive {
122                    return;
123                }
124
125                let map_to_child_clause =
126                    |(index, (clause, span)): (usize, (I::Clause, I::Span))| {
127                        elaboratable.child_with_derived_cause(
128                            clause.instantiate_supertrait(cx, bound_clause.rebind(data.trait_ref)),
129                            span,
130                            bound_clause.rebind(data),
131                            index,
132                        )
133                    };
134
135                // Get clauses implied by the trait, or only super clauses if we only care
136                // about self clauses.
137                match self.mode {
138                    Filter::All => self.extend_deduped(
139                        cx.explicit_implied_clauses_of(data.def_id().into())
140                            .iter_identity()
141                            .map(Unnormalized::skip_norm_wip)
142                            .enumerate()
143                            .map(map_to_child_clause),
144                    ),
145                    Filter::OnlySelf => self.extend_deduped(
146                        cx.explicit_super_clauses_of(data.def_id())
147                            .iter_identity()
148                            .map(Unnormalized::skip_norm_wip)
149                            .enumerate()
150                            .map(map_to_child_clause),
151                    ),
152                };
153            }
154            // `T: [const] Trait` implies `T: [const] Supertrait`.
155            ty::ClauseKind::HostEffect(data) => self.extend_deduped(
156                cx.explicit_implied_const_bounds(data.def_id().into()).iter_identity().map(
157                    |trait_ref| {
158                        elaboratable.child(
159                            trait_ref
160                                .to_host_effect_clause(cx, data.constness)
161                                .skip_norm_wip()
162                                .instantiate_supertrait(cx, bound_clause.rebind(data.trait_ref)),
163                        )
164                    },
165                ),
166            ),
167            ty::ClauseKind::TypeOutlives(ty::OutlivesClause(ty_max, r_min)) => {
168                // We know that `T: 'a` for some type `T`. We can
169                // often elaborate this. For example, if we know that
170                // `[U]: 'a`, that implies that `U: 'a`. Similarly, if
171                // we know `&'a U: 'b`, then we know that `'a: 'b` and
172                // `U: 'b`.
173                //
174                // We can basically ignore bound regions here. So for
175                // example `for<'c> Foo<'a,'c>: 'b` can be elaborated to
176                // `'a: 'b`.
177
178                // Ignore `for<'a> T: 'a` -- we might in the future
179                // consider this as evidence that `T: 'static`, but
180                // I'm a bit wary of such constructions and so for now
181                // I want to be conservative. --nmatsakis
182                if r_min.is_bound() {
183                    return;
184                }
185
186                let mut components = ::smallvec::SmallVec::new()smallvec![];
187                push_outlives_components(cx, ty_max, &mut components);
188                self.extend_deduped(
189                    components
190                        .into_iter()
191                        .filter_map(|component| elaborate_component_to_clause(cx, component, r_min))
192                        .map(|clause| elaboratable.child(bound_clause.rebind(clause).upcast(cx))),
193                );
194            }
195            ty::ClauseKind::RegionOutlives(..) => {
196                // Nothing to elaborate from `'a: 'b`.
197            }
198            ty::ClauseKind::WellFormed(..) => {
199                // Currently, we do not elaborate WF predicates,
200                // although we easily could.
201            }
202            ty::ClauseKind::Projection(..) => {
203                // Nothing to elaborate in a projection predicate.
204            }
205            ty::ClauseKind::ConstEvaluatable(..) => {
206                // Currently, we do not elaborate const-evaluatable
207                // predicates.
208            }
209            ty::ClauseKind::ConstArgHasType(..) => {
210                // Nothing to elaborate
211            }
212            ty::ClauseKind::UnstableFeature(_) => {
213                // Nothing to elaborate
214            }
215            ty::ClauseKind::CompressedTrait(_) => ::core::panicking::unreachable_default_msg()unreachable!(),
216        }
217    }
218}
219
220fn elaborate_component_to_clause<I: Interner>(
221    cx: I,
222    component: Component<I>,
223    outlives_region: Region<I>,
224) -> Option<ty::ClauseKind<I>> {
225    match component {
226        Component::Region(r) => {
227            if r.is_bound() {
228                None
229            } else {
230                Some(ty::ClauseKind::RegionOutlives(ty::OutlivesClause(r, outlives_region)))
231            }
232        }
233
234        Component::Param(p) => {
235            let ty = Ty::new_param(cx, p);
236            Some(ty::ClauseKind::TypeOutlives(ty::OutlivesClause(ty, outlives_region)))
237        }
238
239        Component::Placeholder(p) => {
240            let ty = Ty::new_placeholder(cx, p);
241            Some(ty::ClauseKind::TypeOutlives(ty::OutlivesClause(ty, outlives_region)))
242        }
243
244        Component::UnresolvedInferenceVariable(_) => None,
245
246        Component::Alias(is_rigid, alias_ty) => {
247            // We might end up here if we have `Foo<<Bar as Baz>::Assoc>: 'a`.
248            // With this, we can deduce that `<Bar as Baz>::Assoc: 'a`.
249            Some(ty::ClauseKind::TypeOutlives(ty::OutlivesClause(
250                alias_ty.to_ty(cx, is_rigid),
251                outlives_region,
252            )))
253        }
254
255        Component::EscapingAlias(_) => {
256            // We might be able to do more here, but we don't
257            // want to deal with escaping vars right now.
258            None
259        }
260    }
261}
262
263impl<I: Interner, O: Elaboratable<I>> Iterator for Elaborator<I, O> {
264    type Item = O;
265
266    fn size_hint(&self) -> (usize, Option<usize>) {
267        (self.stack.len(), None)
268    }
269
270    fn next(&mut self) -> Option<Self::Item> {
271        // Extract next item from top-most stack frame, if any.
272        if let Some(obligation) = self.stack.pop() {
273            self.elaborate(&obligation);
274            Some(obligation)
275        } else {
276            None
277        }
278    }
279}
280
281///////////////////////////////////////////////////////////////////////////
282// Supertrait iterator
283///////////////////////////////////////////////////////////////////////////
284
285/// Computes the def-ids of the transitive supertraits of `trait_def_id`. This (intentionally)
286/// does not compute the full elaborated super-predicates but just the set of def-ids. It is used
287/// to identify which traits may define a given associated type to help avoid cycle errors,
288/// and to make size estimates for vtable layout computation.
289///
290/// rust-analyzer has a query for this, so don't use this function there.
291#[cfg(feature = "nightly")]
292pub fn supertrait_def_ids<I: Interner>(
293    cx: I,
294    trait_def_id: I::TraitId,
295) -> impl Iterator<Item = I::TraitId> {
296    let mut set = HashSet::default();
297    let mut stack = ::alloc::boxed::box_assume_init_into_vec_unsafe(::alloc::intrinsics::write_box_via_move(::alloc::boxed::Box::new_uninit(),
        [trait_def_id]))vec![trait_def_id];
298
299    set.insert(trait_def_id);
300
301    std::iter::from_fn(move || {
302        let trait_def_id = stack.pop()?;
303
304        for (clause, _) in cx
305            .explicit_super_clauses_of(trait_def_id)
306            .iter_identity()
307            .map(Unnormalized::skip_norm_wip)
308        {
309            if let ty::ClauseKind::Trait(data) = clause.kind().skip_binder()
310                && set.insert(data.def_id())
311            {
312                stack.push(data.def_id());
313            }
314        }
315
316        Some(trait_def_id)
317    })
318}
319
320pub fn supertraits<I: Interner>(
321    cx: I,
322    trait_ref: ty::Binder<I, ty::TraitRef<I>>,
323) -> FilterToTraits<I, Elaborator<I, I::Clause>> {
324    elaborate(cx, [trait_ref.upcast(cx)]).filter_only_self().filter_to_traits()
325}
326
327impl<I: Interner> Elaborator<I, I::Clause> {
328    fn filter_to_traits(self) -> FilterToTraits<I, Self> {
329        FilterToTraits { _cx: PhantomData, base_iterator: self }
330    }
331}
332
333/// A filter around an iterator of predicates that makes it yield up
334/// just trait references.
335pub struct FilterToTraits<I: Interner, It: Iterator<Item = I::Clause>> {
336    _cx: PhantomData<I>,
337    base_iterator: It,
338}
339
340impl<I: Interner, It: Iterator<Item = I::Clause>> Iterator for FilterToTraits<I, It> {
341    type Item = ty::Binder<I, ty::TraitRef<I>>;
342
343    fn next(&mut self) -> Option<ty::Binder<I, ty::TraitRef<I>>> {
344        while let Some(pred) = self.base_iterator.next() {
345            if let Some(data) = pred.as_trait_clause() {
346                return Some(data.map_bound(|t| t.trait_ref));
347            }
348        }
349        None
350    }
351
352    fn size_hint(&self) -> (usize, Option<usize>) {
353        let (_, upper) = self.base_iterator.size_hint();
354        (0, upper)
355    }
356}
357
358pub fn elaborate_outlives_assumptions<I: Interner>(
359    cx: I,
360    assumptions: impl IntoIterator<Item = ty::OutlivesClause<I, I::GenericArg>>,
361) -> HashSet<ty::OutlivesClause<I, I::GenericArg>> {
362    let mut collected = HashSet::default();
363
364    for ty::OutlivesClause(arg1, r2) in assumptions {
365        collected.insert(ty::OutlivesClause(arg1, r2));
366        match arg1.kind() {
367            // Elaborate the components of an type, since we may have substituted a
368            // generic coroutine with a more specific type.
369            ty::GenericArgKind::Type(ty1) => {
370                let mut components = ::smallvec::SmallVec::new()smallvec![];
371                push_outlives_components(cx, ty1, &mut components);
372                for c in components {
373                    match c {
374                        Component::Region(r1) => {
375                            if !r1.is_bound() {
376                                collected.insert(ty::OutlivesClause(r1.into(), r2));
377                            }
378                        }
379
380                        Component::Param(p) => {
381                            let ty = Ty::new_param(cx, p);
382                            collected.insert(ty::OutlivesClause(ty.into(), r2));
383                        }
384
385                        Component::Placeholder(p) => {
386                            let ty = Ty::new_placeholder(cx, p);
387                            collected.insert(ty::OutlivesClause(ty.into(), r2));
388                        }
389
390                        Component::Alias(is_rigid, alias_ty) => {
391                            collected.insert(ty::OutlivesClause(
392                                alias_ty.to_ty(cx, is_rigid).into(),
393                                r2,
394                            ));
395                        }
396
397                        Component::UnresolvedInferenceVariable(_) | Component::EscapingAlias(_) => {
398                        }
399                    }
400                }
401            }
402            // Nothing to elaborate for a region.
403            ty::GenericArgKind::Lifetime(_) => {}
404            // Consts don't really participate in outlives.
405            ty::GenericArgKind::Const(_) => {}
406        }
407    }
408
409    collected
410}