hir_ty/next_solver/
predicate.rs

1//! Things related to predicates.
2
3use std::cmp::Ordering;
4
5use intern::Interned;
6use rustc_ast_ir::try_visit;
7use rustc_type_ir::{
8    self as ty, CollectAndApply, DebruijnIndex, EarlyBinder, FlagComputation, Flags,
9    PredicatePolarity, TypeFlags, TypeFoldable, TypeSuperFoldable, TypeSuperVisitable,
10    TypeVisitable, Upcast, UpcastFrom, VisitorResult, WithCachedTypeInfo,
11    elaborate::Elaboratable,
12    error::{ExpectedFound, TypeError},
13    inherent::{IntoKind, SliceLike},
14    relate::Relate,
15};
16use smallvec::{SmallVec, smallvec};
17
18use super::{Binder, BoundVarKinds, DbInterner, Region, Ty, interned_vec_db};
19
20pub type BoundExistentialPredicate<'db> = Binder<'db, ExistentialPredicate<'db>>;
21
22pub type TraitRef<'db> = ty::TraitRef<DbInterner<'db>>;
23pub type AliasTerm<'db> = ty::AliasTerm<DbInterner<'db>>;
24pub type ProjectionPredicate<'db> = ty::ProjectionPredicate<DbInterner<'db>>;
25pub type ExistentialPredicate<'db> = ty::ExistentialPredicate<DbInterner<'db>>;
26pub type ExistentialTraitRef<'db> = ty::ExistentialTraitRef<DbInterner<'db>>;
27pub type ExistentialProjection<'db> = ty::ExistentialProjection<DbInterner<'db>>;
28pub type TraitPredicate<'db> = ty::TraitPredicate<DbInterner<'db>>;
29pub type ClauseKind<'db> = ty::ClauseKind<DbInterner<'db>>;
30pub type PredicateKind<'db> = ty::PredicateKind<DbInterner<'db>>;
31pub type NormalizesTo<'db> = ty::NormalizesTo<DbInterner<'db>>;
32pub type CoercePredicate<'db> = ty::CoercePredicate<DbInterner<'db>>;
33pub type SubtypePredicate<'db> = ty::SubtypePredicate<DbInterner<'db>>;
34pub type OutlivesPredicate<'db, T> = ty::OutlivesPredicate<DbInterner<'db>, T>;
35pub type RegionOutlivesPredicate<'db> = OutlivesPredicate<'db, Region<'db>>;
36pub type TypeOutlivesPredicate<'db> = OutlivesPredicate<'db, Ty<'db>>;
37pub type PolyTraitPredicate<'db> = Binder<'db, TraitPredicate<'db>>;
38pub type PolyRegionOutlivesPredicate<'db> = Binder<'db, RegionOutlivesPredicate<'db>>;
39pub type PolyTypeOutlivesPredicate<'db> = Binder<'db, TypeOutlivesPredicate<'db>>;
40pub type PolySubtypePredicate<'db> = Binder<'db, SubtypePredicate<'db>>;
41pub type PolyCoercePredicate<'db> = Binder<'db, CoercePredicate<'db>>;
42pub type PolyProjectionPredicate<'db> = Binder<'db, ProjectionPredicate<'db>>;
43pub type PolyTraitRef<'db> = Binder<'db, TraitRef<'db>>;
44pub type PolyExistentialTraitRef<'db> = Binder<'db, ExistentialTraitRef<'db>>;
45pub type PolyExistentialProjection<'db> = Binder<'db, ExistentialProjection<'db>>;
46
47/// Compares via an ordering that will not change if modules are reordered or other changes are
48/// made to the tree. In particular, this ordering is preserved across incremental compilations.
49fn stable_cmp_existential_predicate<'db>(
50    a: &ExistentialPredicate<'db>,
51    b: &ExistentialPredicate<'db>,
52) -> Ordering {
53    // FIXME: this is actual unstable - see impl in predicate.rs in `rustc_middle`
54    match (a, b) {
55        (ExistentialPredicate::Trait(_), ExistentialPredicate::Trait(_)) => Ordering::Equal,
56        (ExistentialPredicate::Projection(a), ExistentialPredicate::Projection(b)) => {
57            // Should sort by def path hash
58            Ordering::Equal
59        }
60        (ExistentialPredicate::AutoTrait(a), ExistentialPredicate::AutoTrait(b)) => {
61            // Should sort by def path hash
62            Ordering::Equal
63        }
64        (ExistentialPredicate::Trait(_), _) => Ordering::Less,
65        (ExistentialPredicate::Projection(_), ExistentialPredicate::Trait(_)) => Ordering::Greater,
66        (ExistentialPredicate::Projection(_), _) => Ordering::Less,
67        (ExistentialPredicate::AutoTrait(_), _) => Ordering::Greater,
68    }
69}
70interned_vec_db!(BoundExistentialPredicates, BoundExistentialPredicate);
71
72impl<'db> rustc_type_ir::inherent::BoundExistentialPredicates<DbInterner<'db>>
73    for BoundExistentialPredicates<'db>
74{
75    fn principal_def_id(self) -> Option<<DbInterner<'db> as rustc_type_ir::Interner>::DefId> {
76        self.principal().map(|trait_ref| trait_ref.skip_binder().def_id)
77    }
78
79    fn principal(
80        self,
81    ) -> Option<
82        rustc_type_ir::Binder<DbInterner<'db>, rustc_type_ir::ExistentialTraitRef<DbInterner<'db>>>,
83    > {
84        self.inner()[0]
85            .map_bound(|this| match this {
86                ExistentialPredicate::Trait(tr) => Some(tr),
87                _ => None,
88            })
89            .transpose()
90    }
91
92    fn auto_traits(
93        self,
94    ) -> impl IntoIterator<Item = <DbInterner<'db> as rustc_type_ir::Interner>::DefId> {
95        self.iter().filter_map(|predicate| match predicate.skip_binder() {
96            ExistentialPredicate::AutoTrait(did) => Some(did),
97            _ => None,
98        })
99    }
100
101    fn projection_bounds(
102        self,
103    ) -> impl IntoIterator<
104        Item = rustc_type_ir::Binder<
105            DbInterner<'db>,
106            rustc_type_ir::ExistentialProjection<DbInterner<'db>>,
107        >,
108    > {
109        self.iter().filter_map(|predicate| {
110            predicate
111                .map_bound(|pred| match pred {
112                    ExistentialPredicate::Projection(projection) => Some(projection),
113                    _ => None,
114                })
115                .transpose()
116        })
117    }
118}
119
120impl<'db> rustc_type_ir::relate::Relate<DbInterner<'db>> for BoundExistentialPredicates<'db> {
121    fn relate<R: rustc_type_ir::relate::TypeRelation<DbInterner<'db>>>(
122        relation: &mut R,
123        a: Self,
124        b: Self,
125    ) -> rustc_type_ir::relate::RelateResult<DbInterner<'db>, Self> {
126        let interner = relation.cx();
127
128        // We need to perform this deduplication as we sometimes generate duplicate projections in `a`.
129        let mut a_v: Vec<_> = a.into_iter().collect();
130        let mut b_v: Vec<_> = b.into_iter().collect();
131        // `skip_binder` here is okay because `stable_cmp` doesn't look at binders
132        a_v.sort_by(|a, b| {
133            stable_cmp_existential_predicate(a.as_ref().skip_binder(), b.as_ref().skip_binder())
134        });
135        a_v.dedup();
136        b_v.sort_by(|a, b| {
137            stable_cmp_existential_predicate(a.as_ref().skip_binder(), b.as_ref().skip_binder())
138        });
139        b_v.dedup();
140        if a_v.len() != b_v.len() {
141            return Err(TypeError::ExistentialMismatch(ExpectedFound::new(a, b)));
142        }
143
144        let v = std::iter::zip(a_v, b_v).map(
145            |(ep_a, ep_b): (
146                Binder<'_, ty::ExistentialPredicate<_>>,
147                Binder<'_, ty::ExistentialPredicate<_>>,
148            )| {
149                match (ep_a.skip_binder(), ep_b.skip_binder()) {
150                    (ty::ExistentialPredicate::Trait(a), ty::ExistentialPredicate::Trait(b)) => {
151                        Ok(ep_a.rebind(ty::ExistentialPredicate::Trait(
152                            relation.relate(ep_a.rebind(a), ep_b.rebind(b))?.skip_binder(),
153                        )))
154                    }
155                    (
156                        ty::ExistentialPredicate::Projection(a),
157                        ty::ExistentialPredicate::Projection(b),
158                    ) => Ok(ep_a.rebind(ty::ExistentialPredicate::Projection(
159                        relation.relate(ep_a.rebind(a), ep_b.rebind(b))?.skip_binder(),
160                    ))),
161                    (
162                        ty::ExistentialPredicate::AutoTrait(a),
163                        ty::ExistentialPredicate::AutoTrait(b),
164                    ) if a == b => Ok(ep_a.rebind(ty::ExistentialPredicate::AutoTrait(a))),
165                    _ => Err(TypeError::ExistentialMismatch(ExpectedFound::new(a, b))),
166                }
167            },
168        );
169
170        CollectAndApply::collect_and_apply(v, |g| {
171            BoundExistentialPredicates::new_from_iter(interner, g.iter().cloned())
172        })
173    }
174}
175
176#[derive(PartialEq, Eq, Hash, PartialOrd, Ord, Clone)]
177pub struct InternedWrapperNoDebug<T>(pub(crate) T);
178
179#[salsa::interned(constructor = new_)]
180pub struct Predicate<'db> {
181    #[returns(ref)]
182    kind_: InternedWrapperNoDebug<WithCachedTypeInfo<Binder<'db, PredicateKind<'db>>>>,
183}
184
185impl<'db> std::fmt::Debug for Predicate<'db> {
186    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
187        self.inner().internee.fmt(f)
188    }
189}
190
191impl<'db> std::fmt::Debug
192    for InternedWrapperNoDebug<WithCachedTypeInfo<Binder<'db, PredicateKind<'db>>>>
193{
194    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
195        write!(f, "Binder<")?;
196        match self.0.internee.skip_binder() {
197            rustc_type_ir::PredicateKind::Clause(clause_kind) => {
198                write!(f, "{clause_kind:?}")
199            }
200            rustc_type_ir::PredicateKind::DynCompatible(trait_def_id) => {
201                write!(f, "the trait `{trait_def_id:?}` is dyn-compatible")
202            }
203            rustc_type_ir::PredicateKind::Subtype(subtype_predicate) => {
204                write!(f, "{subtype_predicate:?}")
205            }
206            rustc_type_ir::PredicateKind::Coerce(coerce_predicate) => {
207                write!(f, "{coerce_predicate:?}")
208            }
209            rustc_type_ir::PredicateKind::ConstEquate(c1, c2) => {
210                write!(f, "the constant `{c1:?}` equals `{c2:?}`")
211            }
212            rustc_type_ir::PredicateKind::Ambiguous => write!(f, "ambiguous"),
213            rustc_type_ir::PredicateKind::NormalizesTo(data) => write!(f, "{data:?}"),
214            rustc_type_ir::PredicateKind::AliasRelate(t1, t2, dir) => {
215                write!(f, "{t1:?} {dir:?} {t2:?}")
216            }
217        }?;
218        write!(f, ", [{:?}]>", self.0.internee.bound_vars())?;
219        Ok(())
220    }
221}
222
223impl<'db> Predicate<'db> {
224    pub fn new(interner: DbInterner<'db>, kind: Binder<'db, PredicateKind<'db>>) -> Self {
225        let flags = FlagComputation::for_predicate(kind);
226        let cached = WithCachedTypeInfo {
227            internee: kind,
228            flags: flags.flags,
229            outer_exclusive_binder: flags.outer_exclusive_binder,
230        };
231        Predicate::new_(interner.db(), InternedWrapperNoDebug(cached))
232    }
233
234    pub fn inner(&self) -> &WithCachedTypeInfo<Binder<'db, PredicateKind<'db>>> {
235        salsa::with_attached_database(|db| {
236            let inner = &self.kind_(db).0;
237            // SAFETY: The caller already has access to a `Predicate<'db>`, so borrowchecking will
238            // make sure that our returned value is valid for the lifetime `'db`.
239            unsafe { std::mem::transmute(inner) }
240        })
241        .unwrap()
242    }
243
244    /// Flips the polarity of a Predicate.
245    ///
246    /// Given `T: Trait` predicate it returns `T: !Trait` and given `T: !Trait` returns `T: Trait`.
247    pub fn flip_polarity(self) -> Option<Predicate<'db>> {
248        let kind = self
249            .kind()
250            .map_bound(|kind| match kind {
251                PredicateKind::Clause(ClauseKind::Trait(TraitPredicate {
252                    trait_ref,
253                    polarity,
254                })) => Some(PredicateKind::Clause(ClauseKind::Trait(TraitPredicate {
255                    trait_ref,
256                    polarity: polarity.flip(),
257                }))),
258
259                _ => None,
260            })
261            .transpose()?;
262
263        Some(Predicate::new(DbInterner::conjure(), kind))
264    }
265
266    pub fn as_trait_clause(self) -> Option<PolyTraitPredicate<'db>> {
267        let predicate = self.kind();
268        match predicate.skip_binder() {
269            PredicateKind::Clause(ClauseKind::Trait(t)) => Some(predicate.rebind(t)),
270            PredicateKind::Clause(ClauseKind::Projection(..))
271            | PredicateKind::Clause(ClauseKind::HostEffect(..))
272            | PredicateKind::Clause(ClauseKind::ConstArgHasType(..))
273            | PredicateKind::Clause(ClauseKind::UnstableFeature(_))
274            | PredicateKind::NormalizesTo(..)
275            | PredicateKind::AliasRelate(..)
276            | PredicateKind::Subtype(..)
277            | PredicateKind::Coerce(..)
278            | PredicateKind::Clause(ClauseKind::RegionOutlives(..))
279            | PredicateKind::Clause(ClauseKind::WellFormed(..))
280            | PredicateKind::DynCompatible(..)
281            | PredicateKind::Clause(ClauseKind::TypeOutlives(..))
282            | PredicateKind::Clause(ClauseKind::ConstEvaluatable(..))
283            | PredicateKind::ConstEquate(..)
284            | PredicateKind::Ambiguous => None,
285        }
286    }
287}
288
289// FIXME: should make a "header" in interned_vec
290
291#[derive(Debug, Clone)]
292pub struct InternedClausesWrapper<'db>(SmallVec<[Clause<'db>; 2]>, TypeFlags, DebruijnIndex);
293
294impl<'db> PartialEq for InternedClausesWrapper<'db> {
295    fn eq(&self, other: &Self) -> bool {
296        self.0.eq(&other.0)
297    }
298}
299
300impl<'db> Eq for InternedClausesWrapper<'db> {}
301
302impl<'db> std::hash::Hash for InternedClausesWrapper<'db> {
303    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
304        self.0.hash(state)
305    }
306}
307
308type InternedClauses<'db> = Interned<InternedClausesWrapper<'db>>;
309
310#[salsa::interned(constructor = new_)]
311pub struct Clauses<'db> {
312    #[returns(ref)]
313    inner_: InternedClausesWrapper<'db>,
314}
315
316impl<'db> Clauses<'db> {
317    pub fn new_from_iter(
318        interner: DbInterner<'db>,
319        data: impl IntoIterator<Item = Clause<'db>>,
320    ) -> Self {
321        let clauses: SmallVec<_> = data.into_iter().collect();
322        let flags = FlagComputation::<DbInterner<'db>>::for_clauses(&clauses);
323        let wrapper = InternedClausesWrapper(clauses, flags.flags, flags.outer_exclusive_binder);
324        Clauses::new_(interner.db(), wrapper)
325    }
326
327    pub fn inner(&self) -> &InternedClausesWrapper<'db> {
328        salsa::with_attached_database(|db| {
329            let inner = self.inner_(db);
330            // SAFETY: The caller already has access to a `Clauses<'db>`, so borrowchecking will
331            // make sure that our returned value is valid for the lifetime `'db`.
332            unsafe { std::mem::transmute(inner) }
333        })
334        .unwrap()
335    }
336}
337
338impl<'db> std::fmt::Debug for Clauses<'db> {
339    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
340        self.inner().0.fmt(f)
341    }
342}
343
344impl<'db> rustc_type_ir::inherent::Clauses<DbInterner<'db>> for Clauses<'db> {}
345
346impl<'db> rustc_type_ir::inherent::SliceLike for Clauses<'db> {
347    type Item = Clause<'db>;
348
349    type IntoIter = <smallvec::SmallVec<[Clause<'db>; 2]> as IntoIterator>::IntoIter;
350
351    fn iter(self) -> Self::IntoIter {
352        self.inner().0.clone().into_iter()
353    }
354
355    fn as_slice(&self) -> &[Self::Item] {
356        self.inner().0.as_slice()
357    }
358}
359
360impl<'db> IntoIterator for Clauses<'db> {
361    type Item = Clause<'db>;
362    type IntoIter = <Self as rustc_type_ir::inherent::SliceLike>::IntoIter;
363
364    fn into_iter(self) -> Self::IntoIter {
365        rustc_type_ir::inherent::SliceLike::iter(self)
366    }
367}
368
369impl<'db> Default for Clauses<'db> {
370    fn default() -> Self {
371        Clauses::new_from_iter(DbInterner::conjure(), [])
372    }
373}
374
375impl<'db> rustc_type_ir::TypeSuperFoldable<DbInterner<'db>> for Clauses<'db> {
376    fn try_super_fold_with<F: rustc_type_ir::FallibleTypeFolder<DbInterner<'db>>>(
377        self,
378        folder: &mut F,
379    ) -> Result<Self, F::Error> {
380        let mut clauses: SmallVec<[_; 2]> = SmallVec::with_capacity(self.inner().0.len());
381        for c in self {
382            clauses.push(c.try_fold_with(folder)?);
383        }
384        Ok(Clauses::new_from_iter(folder.cx(), clauses))
385    }
386
387    fn super_fold_with<F: rustc_type_ir::TypeFolder<DbInterner<'db>>>(
388        self,
389        folder: &mut F,
390    ) -> Self {
391        let mut clauses: SmallVec<[_; 2]> = SmallVec::with_capacity(self.inner().0.len());
392        for c in self {
393            clauses.push(c.fold_with(folder));
394        }
395        Clauses::new_from_iter(folder.cx(), clauses)
396    }
397}
398
399impl<'db> rustc_type_ir::TypeFoldable<DbInterner<'db>> for Clauses<'db> {
400    fn try_fold_with<F: rustc_type_ir::FallibleTypeFolder<DbInterner<'db>>>(
401        self,
402        folder: &mut F,
403    ) -> Result<Self, F::Error> {
404        use rustc_type_ir::inherent::SliceLike as _;
405        let inner: smallvec::SmallVec<[_; 2]> =
406            self.iter().map(|v| v.try_fold_with(folder)).collect::<Result<_, _>>()?;
407        Ok(Clauses::new_from_iter(folder.cx(), inner))
408    }
409    fn fold_with<F: rustc_type_ir::TypeFolder<DbInterner<'db>>>(self, folder: &mut F) -> Self {
410        use rustc_type_ir::inherent::SliceLike as _;
411        let inner: smallvec::SmallVec<[_; 2]> = self.iter().map(|v| v.fold_with(folder)).collect();
412        Clauses::new_from_iter(folder.cx(), inner)
413    }
414}
415
416impl<'db> rustc_type_ir::TypeVisitable<DbInterner<'db>> for Clauses<'db> {
417    fn visit_with<V: rustc_type_ir::TypeVisitor<DbInterner<'db>>>(
418        &self,
419        visitor: &mut V,
420    ) -> V::Result {
421        use rustc_ast_ir::visit::VisitorResult;
422        use rustc_type_ir::inherent::SliceLike as _;
423        rustc_ast_ir::walk_visitable_list!(visitor, self.as_slice().iter());
424        V::Result::output()
425    }
426}
427
428impl<'db> rustc_type_ir::Flags for Clauses<'db> {
429    fn flags(&self) -> rustc_type_ir::TypeFlags {
430        self.inner().1
431    }
432
433    fn outer_exclusive_binder(&self) -> rustc_type_ir::DebruijnIndex {
434        self.inner().2
435    }
436}
437
438impl<'db> rustc_type_ir::TypeSuperVisitable<DbInterner<'db>> for Clauses<'db> {
439    fn super_visit_with<V: rustc_type_ir::TypeVisitor<DbInterner<'db>>>(
440        &self,
441        visitor: &mut V,
442    ) -> V::Result {
443        self.as_slice().visit_with(visitor)
444    }
445}
446
447#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)] // TODO implement Debug by hand
448pub struct Clause<'db>(pub(crate) Predicate<'db>);
449
450// We could cram the reveal into the clauses like rustc does, probably
451#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
452pub struct ParamEnv<'db> {
453    pub(crate) clauses: Clauses<'db>,
454}
455
456impl<'db> ParamEnv<'db> {
457    pub fn empty() -> Self {
458        ParamEnv { clauses: Clauses::new_from_iter(DbInterner::conjure(), []) }
459    }
460}
461
462impl<'db> TypeVisitable<DbInterner<'db>> for ParamEnv<'db> {
463    fn visit_with<V: rustc_type_ir::TypeVisitor<DbInterner<'db>>>(
464        &self,
465        visitor: &mut V,
466    ) -> V::Result {
467        try_visit!(self.clauses.visit_with(visitor));
468        V::Result::output()
469    }
470}
471
472impl<'db> TypeFoldable<DbInterner<'db>> for ParamEnv<'db> {
473    fn try_fold_with<F: rustc_type_ir::FallibleTypeFolder<DbInterner<'db>>>(
474        self,
475        folder: &mut F,
476    ) -> Result<Self, F::Error> {
477        Ok(ParamEnv { clauses: self.clauses.try_fold_with(folder)? })
478    }
479    fn fold_with<F: rustc_type_ir::TypeFolder<DbInterner<'db>>>(self, folder: &mut F) -> Self {
480        ParamEnv { clauses: self.clauses.fold_with(folder) }
481    }
482}
483
484impl<'db> rustc_type_ir::inherent::ParamEnv<DbInterner<'db>> for ParamEnv<'db> {
485    fn caller_bounds(self) -> impl rustc_type_ir::inherent::SliceLike<Item = Clause<'db>> {
486        self.clauses
487    }
488}
489
490#[derive(Clone, Debug, PartialEq, Eq, Hash)]
491pub struct ParamEnvAnd<'db, T> {
492    pub param_env: ParamEnv<'db>,
493    pub value: T,
494}
495
496impl<'db, T> ParamEnvAnd<'db, T> {
497    pub fn into_parts(self) -> (ParamEnv<'db>, T) {
498        (self.param_env, self.value)
499    }
500}
501
502impl<'db> TypeVisitable<DbInterner<'db>> for Predicate<'db> {
503    fn visit_with<V: rustc_type_ir::TypeVisitor<DbInterner<'db>>>(
504        &self,
505        visitor: &mut V,
506    ) -> V::Result {
507        visitor.visit_predicate(*self)
508    }
509}
510
511impl<'db> TypeSuperVisitable<DbInterner<'db>> for Predicate<'db> {
512    fn super_visit_with<V: rustc_type_ir::TypeVisitor<DbInterner<'db>>>(
513        &self,
514        visitor: &mut V,
515    ) -> V::Result {
516        (*self).kind().visit_with(visitor)
517    }
518}
519
520impl<'db> TypeFoldable<DbInterner<'db>> for Predicate<'db> {
521    fn try_fold_with<F: rustc_type_ir::FallibleTypeFolder<DbInterner<'db>>>(
522        self,
523        folder: &mut F,
524    ) -> Result<Self, F::Error> {
525        folder.try_fold_predicate(self)
526    }
527    fn fold_with<F: rustc_type_ir::TypeFolder<DbInterner<'db>>>(self, folder: &mut F) -> Self {
528        folder.fold_predicate(self)
529    }
530}
531
532impl<'db> TypeSuperFoldable<DbInterner<'db>> for Predicate<'db> {
533    fn try_super_fold_with<F: rustc_type_ir::FallibleTypeFolder<DbInterner<'db>>>(
534        self,
535        folder: &mut F,
536    ) -> Result<Self, F::Error> {
537        let new = self.kind().try_fold_with(folder)?;
538        Ok(Predicate::new(folder.cx(), new))
539    }
540    fn super_fold_with<F: rustc_type_ir::TypeFolder<DbInterner<'db>>>(
541        self,
542        folder: &mut F,
543    ) -> Self {
544        let new = self.kind().fold_with(folder);
545        Predicate::new(folder.cx(), new)
546    }
547}
548
549impl<'db> Elaboratable<DbInterner<'db>> for Predicate<'db> {
550    fn predicate(&self) -> <DbInterner<'db> as rustc_type_ir::Interner>::Predicate {
551        *self
552    }
553
554    fn child(&self, clause: <DbInterner<'db> as rustc_type_ir::Interner>::Clause) -> Self {
555        clause.as_predicate()
556    }
557
558    fn child_with_derived_cause(
559        &self,
560        clause: <DbInterner<'db> as rustc_type_ir::Interner>::Clause,
561        _span: <DbInterner<'db> as rustc_type_ir::Interner>::Span,
562        _parent_trait_pred: rustc_type_ir::Binder<
563            DbInterner<'db>,
564            rustc_type_ir::TraitPredicate<DbInterner<'db>>,
565        >,
566        _index: usize,
567    ) -> Self {
568        clause.as_predicate()
569    }
570}
571
572impl<'db> Flags for Predicate<'db> {
573    fn flags(&self) -> rustc_type_ir::TypeFlags {
574        self.inner().flags
575    }
576
577    fn outer_exclusive_binder(&self) -> rustc_type_ir::DebruijnIndex {
578        self.inner().outer_exclusive_binder
579    }
580}
581
582impl<'db> IntoKind for Predicate<'db> {
583    type Kind = Binder<'db, PredicateKind<'db>>;
584
585    fn kind(self) -> Self::Kind {
586        self.inner().internee
587    }
588}
589
590impl<'db> UpcastFrom<DbInterner<'db>, ty::PredicateKind<DbInterner<'db>>> for Predicate<'db> {
591    fn upcast_from(from: ty::PredicateKind<DbInterner<'db>>, interner: DbInterner<'db>) -> Self {
592        Binder::dummy(from).upcast(interner)
593    }
594}
595impl<'db>
596    UpcastFrom<DbInterner<'db>, ty::Binder<DbInterner<'db>, ty::PredicateKind<DbInterner<'db>>>>
597    for Predicate<'db>
598{
599    fn upcast_from(
600        from: ty::Binder<DbInterner<'db>, ty::PredicateKind<DbInterner<'db>>>,
601        interner: DbInterner<'db>,
602    ) -> Self {
603        Predicate::new(interner, from)
604    }
605}
606impl<'db> UpcastFrom<DbInterner<'db>, ty::ClauseKind<DbInterner<'db>>> for Predicate<'db> {
607    fn upcast_from(from: ty::ClauseKind<DbInterner<'db>>, interner: DbInterner<'db>) -> Self {
608        Binder::dummy(PredicateKind::Clause(from)).upcast(interner)
609    }
610}
611impl<'db> UpcastFrom<DbInterner<'db>, ty::Binder<DbInterner<'db>, ty::ClauseKind<DbInterner<'db>>>>
612    for Predicate<'db>
613{
614    fn upcast_from(
615        from: ty::Binder<DbInterner<'db>, ty::ClauseKind<DbInterner<'db>>>,
616        interner: DbInterner<'db>,
617    ) -> Self {
618        from.map_bound(PredicateKind::Clause).upcast(interner)
619    }
620}
621impl<'db> UpcastFrom<DbInterner<'db>, Clause<'db>> for Predicate<'db> {
622    fn upcast_from(from: Clause<'db>, _interner: DbInterner<'db>) -> Self {
623        from.0
624    }
625}
626impl<'db> UpcastFrom<DbInterner<'db>, ty::NormalizesTo<DbInterner<'db>>> for Predicate<'db> {
627    fn upcast_from(from: ty::NormalizesTo<DbInterner<'db>>, interner: DbInterner<'db>) -> Self {
628        PredicateKind::NormalizesTo(from).upcast(interner)
629    }
630}
631impl<'db> UpcastFrom<DbInterner<'db>, ty::TraitRef<DbInterner<'db>>> for Predicate<'db> {
632    fn upcast_from(from: ty::TraitRef<DbInterner<'db>>, interner: DbInterner<'db>) -> Self {
633        Binder::dummy(from).upcast(interner)
634    }
635}
636impl<'db> UpcastFrom<DbInterner<'db>, ty::Binder<DbInterner<'db>, ty::TraitRef<DbInterner<'db>>>>
637    for Predicate<'db>
638{
639    fn upcast_from(
640        from: ty::Binder<DbInterner<'db>, ty::TraitRef<DbInterner<'db>>>,
641        interner: DbInterner<'db>,
642    ) -> Self {
643        from.map_bound(|trait_ref| TraitPredicate {
644            trait_ref,
645            polarity: PredicatePolarity::Positive,
646        })
647        .upcast(interner)
648    }
649}
650impl<'db> UpcastFrom<DbInterner<'db>, Binder<'db, ty::TraitPredicate<DbInterner<'db>>>>
651    for Predicate<'db>
652{
653    fn upcast_from(
654        from: Binder<'db, ty::TraitPredicate<DbInterner<'db>>>,
655        interner: DbInterner<'db>,
656    ) -> Self {
657        from.map_bound(|it| PredicateKind::Clause(ClauseKind::Trait(it))).upcast(interner)
658    }
659}
660impl<'db> UpcastFrom<DbInterner<'db>, Binder<'db, ProjectionPredicate<'db>>> for Predicate<'db> {
661    fn upcast_from(from: Binder<'db, ProjectionPredicate<'db>>, interner: DbInterner<'db>) -> Self {
662        from.map_bound(|it| PredicateKind::Clause(ClauseKind::Projection(it))).upcast(interner)
663    }
664}
665impl<'db> UpcastFrom<DbInterner<'db>, ProjectionPredicate<'db>> for Predicate<'db> {
666    fn upcast_from(from: ProjectionPredicate<'db>, interner: DbInterner<'db>) -> Self {
667        PredicateKind::Clause(ClauseKind::Projection(from)).upcast(interner)
668    }
669}
670impl<'db> UpcastFrom<DbInterner<'db>, ty::TraitPredicate<DbInterner<'db>>> for Predicate<'db> {
671    fn upcast_from(from: ty::TraitPredicate<DbInterner<'db>>, interner: DbInterner<'db>) -> Self {
672        PredicateKind::Clause(ClauseKind::Trait(from)).upcast(interner)
673    }
674}
675impl<'db> UpcastFrom<DbInterner<'db>, ty::OutlivesPredicate<DbInterner<'db>, Ty<'db>>>
676    for Predicate<'db>
677{
678    fn upcast_from(
679        from: ty::OutlivesPredicate<DbInterner<'db>, Ty<'db>>,
680        interner: DbInterner<'db>,
681    ) -> Self {
682        PredicateKind::Clause(ClauseKind::TypeOutlives(from)).upcast(interner)
683    }
684}
685impl<'db> UpcastFrom<DbInterner<'db>, ty::OutlivesPredicate<DbInterner<'db>, Region<'db>>>
686    for Predicate<'db>
687{
688    fn upcast_from(
689        from: ty::OutlivesPredicate<DbInterner<'db>, Region<'db>>,
690        interner: DbInterner<'db>,
691    ) -> Self {
692        PredicateKind::Clause(ClauseKind::RegionOutlives(from)).upcast(interner)
693    }
694}
695
696impl<'db> rustc_type_ir::inherent::Predicate<DbInterner<'db>> for Predicate<'db> {
697    fn as_clause(self) -> Option<<DbInterner<'db> as rustc_type_ir::Interner>::Clause> {
698        match self.kind().skip_binder() {
699            PredicateKind::Clause(..) => Some(self.expect_clause()),
700            _ => None,
701        }
702    }
703
704    /// Whether this projection can be soundly normalized.
705    ///
706    /// Wf predicates must not be normalized, as normalization
707    /// can remove required bounds which would cause us to
708    /// unsoundly accept some programs. See #91068.
709    fn allow_normalization(self) -> bool {
710        // TODO: this should probably live in rustc_type_ir
711        match self.inner().as_ref().skip_binder() {
712            PredicateKind::Clause(ClauseKind::WellFormed(_))
713            | PredicateKind::AliasRelate(..)
714            | PredicateKind::NormalizesTo(..) => false,
715            PredicateKind::Clause(ClauseKind::Trait(_))
716            | PredicateKind::Clause(ClauseKind::RegionOutlives(_))
717            | PredicateKind::Clause(ClauseKind::TypeOutlives(_))
718            | PredicateKind::Clause(ClauseKind::Projection(_))
719            | PredicateKind::Clause(ClauseKind::ConstArgHasType(..))
720            | PredicateKind::Clause(ClauseKind::HostEffect(..))
721            | PredicateKind::Clause(ClauseKind::UnstableFeature(_))
722            | PredicateKind::DynCompatible(_)
723            | PredicateKind::Subtype(_)
724            | PredicateKind::Coerce(_)
725            | PredicateKind::Clause(ClauseKind::ConstEvaluatable(_))
726            | PredicateKind::ConstEquate(_, _)
727            | PredicateKind::Ambiguous => true,
728        }
729    }
730}
731
732impl<'db> Predicate<'db> {
733    /// Assert that the predicate is a clause.
734    pub fn expect_clause(self) -> Clause<'db> {
735        match self.kind().skip_binder() {
736            PredicateKind::Clause(..) => Clause(self),
737            _ => panic!("{self:?} is not a clause"),
738        }
739    }
740}
741
742impl<'db> TypeVisitable<DbInterner<'db>> for Clause<'db> {
743    fn visit_with<V: rustc_type_ir::TypeVisitor<DbInterner<'db>>>(
744        &self,
745        visitor: &mut V,
746    ) -> V::Result {
747        visitor.visit_predicate((*self).as_predicate())
748    }
749}
750
751impl<'db> TypeFoldable<DbInterner<'db>> for Clause<'db> {
752    fn try_fold_with<F: rustc_type_ir::FallibleTypeFolder<DbInterner<'db>>>(
753        self,
754        folder: &mut F,
755    ) -> Result<Self, F::Error> {
756        Ok(folder.try_fold_predicate(self.as_predicate())?.expect_clause())
757    }
758    fn fold_with<F: rustc_type_ir::TypeFolder<DbInterner<'db>>>(self, folder: &mut F) -> Self {
759        folder.fold_predicate(self.as_predicate()).expect_clause()
760    }
761}
762
763impl<'db> IntoKind for Clause<'db> {
764    type Kind = Binder<'db, ClauseKind<'db>>;
765
766    fn kind(self) -> Self::Kind {
767        self.0.kind().map_bound(|pk| match pk {
768            PredicateKind::Clause(kind) => kind,
769            _ => unreachable!(),
770        })
771    }
772}
773
774impl<'db> Clause<'db> {
775    pub fn as_predicate(self) -> Predicate<'db> {
776        self.0
777    }
778}
779
780impl<'db> Elaboratable<DbInterner<'db>> for Clause<'db> {
781    fn predicate(&self) -> <DbInterner<'db> as rustc_type_ir::Interner>::Predicate {
782        self.0
783    }
784
785    fn child(&self, clause: <DbInterner<'db> as rustc_type_ir::Interner>::Clause) -> Self {
786        clause
787    }
788
789    fn child_with_derived_cause(
790        &self,
791        clause: <DbInterner<'db> as rustc_type_ir::Interner>::Clause,
792        _span: <DbInterner<'db> as rustc_type_ir::Interner>::Span,
793        _parent_trait_pred: rustc_type_ir::Binder<
794            DbInterner<'db>,
795            rustc_type_ir::TraitPredicate<DbInterner<'db>>,
796        >,
797        _index: usize,
798    ) -> Self {
799        clause
800    }
801}
802
803impl<'db> UpcastFrom<DbInterner<'db>, ty::Binder<DbInterner<'db>, ty::ClauseKind<DbInterner<'db>>>>
804    for Clause<'db>
805{
806    fn upcast_from(
807        from: ty::Binder<DbInterner<'db>, ty::ClauseKind<DbInterner<'db>>>,
808        interner: DbInterner<'db>,
809    ) -> Self {
810        Clause(from.map_bound(PredicateKind::Clause).upcast(interner))
811    }
812}
813impl<'db> UpcastFrom<DbInterner<'db>, ty::TraitRef<DbInterner<'db>>> for Clause<'db> {
814    fn upcast_from(from: ty::TraitRef<DbInterner<'db>>, interner: DbInterner<'db>) -> Self {
815        Clause(from.upcast(interner))
816    }
817}
818impl<'db> UpcastFrom<DbInterner<'db>, ty::Binder<DbInterner<'db>, ty::TraitRef<DbInterner<'db>>>>
819    for Clause<'db>
820{
821    fn upcast_from(
822        from: ty::Binder<DbInterner<'db>, ty::TraitRef<DbInterner<'db>>>,
823        interner: DbInterner<'db>,
824    ) -> Self {
825        Clause(from.upcast(interner))
826    }
827}
828impl<'db> UpcastFrom<DbInterner<'db>, ty::TraitPredicate<DbInterner<'db>>> for Clause<'db> {
829    fn upcast_from(from: ty::TraitPredicate<DbInterner<'db>>, interner: DbInterner<'db>) -> Self {
830        Clause(from.upcast(interner))
831    }
832}
833impl<'db>
834    UpcastFrom<DbInterner<'db>, ty::Binder<DbInterner<'db>, ty::TraitPredicate<DbInterner<'db>>>>
835    for Clause<'db>
836{
837    fn upcast_from(
838        from: ty::Binder<DbInterner<'db>, ty::TraitPredicate<DbInterner<'db>>>,
839        interner: DbInterner<'db>,
840    ) -> Self {
841        Clause(from.upcast(interner))
842    }
843}
844impl<'db> UpcastFrom<DbInterner<'db>, ty::ProjectionPredicate<DbInterner<'db>>> for Clause<'db> {
845    fn upcast_from(
846        from: ty::ProjectionPredicate<DbInterner<'db>>,
847        interner: DbInterner<'db>,
848    ) -> Self {
849        Clause(from.upcast(interner))
850    }
851}
852impl<'db>
853    UpcastFrom<
854        DbInterner<'db>,
855        ty::Binder<DbInterner<'db>, ty::ProjectionPredicate<DbInterner<'db>>>,
856    > for Clause<'db>
857{
858    fn upcast_from(
859        from: ty::Binder<DbInterner<'db>, ty::ProjectionPredicate<DbInterner<'db>>>,
860        interner: DbInterner<'db>,
861    ) -> Self {
862        Clause(from.upcast(interner))
863    }
864}
865
866impl<'db> rustc_type_ir::inherent::Clause<DbInterner<'db>> for Clause<'db> {
867    fn as_predicate(self) -> <DbInterner<'db> as rustc_type_ir::Interner>::Predicate {
868        self.0
869    }
870
871    fn instantiate_supertrait(
872        self,
873        cx: DbInterner<'db>,
874        trait_ref: rustc_type_ir::Binder<DbInterner<'db>, rustc_type_ir::TraitRef<DbInterner<'db>>>,
875    ) -> Self {
876        tracing::debug!(?self, ?trait_ref);
877        // See the rustc impl for a long comment
878        let bound_pred = self.kind();
879        let pred_bound_vars = bound_pred.bound_vars();
880        let trait_bound_vars = trait_ref.bound_vars();
881        // 1) Self: Bar1<'a, '^0.0> -> Self: Bar1<'a, '^0.1>
882        let shifted_pred =
883            cx.shift_bound_var_indices(trait_bound_vars.len(), bound_pred.skip_binder());
884        // 2) Self: Bar1<'a, '^0.1> -> T: Bar1<'^0.0, '^0.1>
885        let new = EarlyBinder::bind(shifted_pred).instantiate(cx, trait_ref.skip_binder().args);
886        // 3) ['x] + ['b] -> ['x, 'b]
887        let bound_vars =
888            BoundVarKinds::new_from_iter(cx, trait_bound_vars.iter().chain(pred_bound_vars.iter()));
889
890        let predicate: Predicate<'db> =
891            ty::Binder::bind_with_vars(PredicateKind::Clause(new), bound_vars).upcast(cx);
892        predicate.expect_clause()
893    }
894}
hir_ty/next_solver/predicate.rs

hir_ty/next_solver/
predicate.rs
