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
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::TraitClause<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}
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 fn extend_deduped(&mut self, obligations: impl IntoIterator<Item = O>) {
91 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 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 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 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 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 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 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 }
198 ty::ClauseKind::WellFormed(..) => {
199 }
202 ty::ClauseKind::Projection(..) => {
203 }
205 ty::ClauseKind::ConstEvaluatable(..) => {
206 }
209 ty::ClauseKind::ConstArgHasType(..) => {
210 }
212 ty::ClauseKind::UnstableFeature(_) => {
213 }
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 Some(ty::ClauseKind::TypeOutlives(ty::OutlivesClause(
250 alias_ty.to_ty(cx, is_rigid),
251 outlives_region,
252 )))
253 }
254
255 Component::EscapingAlias(_) => {
256 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 if let Some(obligation) = self.stack.pop() {
273 self.elaborate(&obligation);
274 Some(obligation)
275 } else {
276 None
277 }
278 }
279}
280
281#[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
333pub 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 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 ty::GenericArgKind::Lifetime(_) => {}
404 ty::GenericArgKind::Const(_) => {}
406 }
407 }
408
409 collected
410}