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
10pub 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
28pub trait Elaboratable<I: Interner> {
30 fn predicate(&self) -> I::Predicate;
31
32 fn child(&self, clause: I::Clause) -> Self;
34
35 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 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 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 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 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 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 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 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 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 }
189 ty::ClauseKind::WellFormed(..) => {
190 }
193 ty::ClauseKind::Projection(..) => {
194 }
196 ty::ClauseKind::ConstEvaluatable(..) => {
197 }
200 ty::ClauseKind::ConstArgHasType(..) => {
201 }
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 Some(ty::ClauseKind::TypeOutlives(ty::OutlivesPredicate(
237 alias_ty.to_ty(cx),
238 outlives_region,
239 )))
240 }
241
242 Component::EscapingAlias(_) => {
243 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 if let Some(obligation) = self.stack.pop() {
260 self.elaborate(&obligation);
261 Some(obligation)
262 } else {
263 None
264 }
265 }
266}
267
268pub 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
313pub 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}