hax_frontend_exporter/traits/
utils.rs

1//! Each item can involve three kinds of predicates:
2//! - input aka required predicates: the predicates required to mention the item. These are usually `where`
3//!   clauses (or equivalent) on the item:
4//! ```ignore
5//! struct Foo<T: Clone> { ... }
6//! trait Foo<T> where T: Clone { ... }
7//! fn function<I>() where I: Iterator, I::Item: Clone { ... }
8//! ```
9//! - output aka implied predicates: the predicates that are implied by the presence of this item in a
10//!   signature. This is mostly trait parent predicates:
11//! ```ignore
12//! trait Foo: Clone { ... }
13//! fn bar<T: Foo>() {
14//!   // from `T: Foo` we can deduce `T: Clone`
15//! }
16//! ```
17//!   This could also include implied predicates such as `&'a T` implying `T: 'a` but we don't
18//!   consider these.
19//! - "self" predicate: that's the special `Self: Trait` predicate in scope within a trait
20//!   declaration or implementation for trait `Trait`.
21//!
22//! Note that within a given item the polarity is reversed: input predicates are the ones that can
23//! be assumed to hold and output predicates must be proven to hold. The "self" predicate is both
24//! assumed and proven within an impl block, and just assumed within a trait declaration block.
25//!
26//! The current implementation considers all predicates on traits to be outputs, which has the
27//! benefit of reducing the size of signatures. Moreover, the rules on which bounds are required vs
28//! implied are subtle. We may change this if this proves to be a problem.
29use hax_frontend_exporter_options::BoundsOptions;
30use rustc_hir::def::DefKind;
31use rustc_middle::ty::*;
32use rustc_span::DUMMY_SP;
33use rustc_span::def_id::DefId;
34
35/// Returns a list of type predicates for the definition with ID `def_id`, including inferred
36/// lifetime constraints. This is the basic list of predicates we use for essentially all items.
37pub fn predicates_defined_on(tcx: TyCtxt<'_>, def_id: DefId) -> GenericPredicates<'_> {
38    let mut result = tcx.explicit_predicates_of(def_id);
39    let inferred_outlives = tcx.inferred_outlives_of(def_id);
40    if !inferred_outlives.is_empty() {
41        let inferred_outlives_iter = inferred_outlives
42            .iter()
43            .map(|(clause, span)| ((*clause).upcast(tcx), *span));
44        result.predicates = tcx.arena.alloc_from_iter(
45            result
46                .predicates
47                .into_iter()
48                .copied()
49                .chain(inferred_outlives_iter),
50        );
51    }
52    result
53}
54
55/// The predicates that must hold to mention this item. E.g.
56///
57/// ```ignore
58/// // `U: OtherTrait` is required, `Self: Sized` is implied.
59/// trait Trait<U: OtherTrait>: Sized {
60///     // `T: Clone` is required, `Self::Type<T>: Debug` is implied.
61///     type Type<T: Clone>: Debug;
62/// }
63/// ```
64///
65/// If `add_drop` is true, we add a `T: Drop` bound for every type generic.
66pub fn required_predicates<'tcx>(
67    tcx: TyCtxt<'tcx>,
68    def_id: DefId,
69    options: BoundsOptions,
70) -> GenericPredicates<'tcx> {
71    use DefKind::*;
72    let def_kind = tcx.def_kind(def_id);
73    let mut predicates = match def_kind {
74        AssocConst
75        | AssocFn
76        | AssocTy
77        | Const
78        | Enum
79        | Fn
80        | ForeignTy
81        | Impl { .. }
82        | OpaqueTy
83        | Static { .. }
84        | Struct
85        | TyAlias
86        | Union => predicates_defined_on(tcx, def_id),
87        // We consider all predicates on traits to be outputs
88        Trait | TraitAlias => Default::default(),
89        // `predicates_defined_on` ICEs on other def kinds.
90        _ => Default::default(),
91    };
92    if options.resolve_drop {
93        // Add a `T: Drop` bound for every generic, unless the current trait is `Drop` itself, or
94        // `Sized`.
95        let drop_trait = tcx.lang_items().drop_trait().unwrap();
96        let sized_trait = tcx.lang_items().sized_trait().unwrap();
97        if def_id != drop_trait && def_id != sized_trait {
98            let extra_bounds = tcx
99                .generics_of(def_id)
100                .own_params
101                .iter()
102                .filter(|param| matches!(param.kind, GenericParamDefKind::Type { .. }))
103                .map(|param| tcx.mk_param_from_def(param))
104                .map(|ty| Binder::dummy(TraitRef::new(tcx, drop_trait, [ty])))
105                .map(|tref| tref.upcast(tcx))
106                .map(|clause| (clause, DUMMY_SP));
107            predicates.predicates = tcx
108                .arena
109                .alloc_from_iter(predicates.predicates.iter().copied().chain(extra_bounds));
110        }
111    }
112    if options.prune_sized {
113        prune_sized_predicates(tcx, &mut predicates);
114    }
115    predicates
116}
117
118/// The special "self" predicate on a trait.
119pub fn self_predicate<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId) -> PolyTraitRef<'tcx> {
120    // Copied from the code of `tcx.predicates_of()`.
121    Binder::dummy(TraitRef::identity(tcx, def_id))
122}
123
124/// The predicates that can be deduced from the presence of this item in a signature. We only
125/// consider predicates implied by traits here, not implied bounds such as `&'a T` implying `T:
126/// 'a`. E.g.
127///
128/// ```ignore
129/// // `U: OtherTrait` is required, `Self: Sized` is implied.
130/// trait Trait<U: OtherTrait>: Sized {
131///     // `T: Clone` is required, `Self::Type<T>: Debug` is implied.
132///     type Type<T: Clone>: Debug;
133/// }
134/// ```
135///
136/// If `add_drop` is true, we add a `T: Drop` bound for every type generic and associated type.
137pub fn implied_predicates<'tcx>(
138    tcx: TyCtxt<'tcx>,
139    def_id: DefId,
140    options: BoundsOptions,
141) -> GenericPredicates<'tcx> {
142    use DefKind::*;
143    let parent = tcx.opt_parent(def_id);
144    let mut predicates = match tcx.def_kind(def_id) {
145        // We consider all predicates on traits to be outputs
146        Trait | TraitAlias => predicates_defined_on(tcx, def_id),
147        AssocTy if matches!(tcx.def_kind(parent.unwrap()), Trait) => {
148            let mut predicates = GenericPredicates {
149                parent,
150                // `skip_binder` is for the GAT `EarlyBinder`
151                predicates: tcx.explicit_item_bounds(def_id).skip_binder(),
152                ..GenericPredicates::default()
153            };
154            if options.resolve_drop {
155                // Add a `Drop` bound to the assoc item.
156                let drop_trait = tcx.lang_items().drop_trait().unwrap();
157                let ty =
158                    Ty::new_projection(tcx, def_id, GenericArgs::identity_for_item(tcx, def_id));
159                let tref = Binder::dummy(TraitRef::new(tcx, drop_trait, [ty]));
160                predicates.predicates = tcx.arena.alloc_from_iter(
161                    predicates
162                        .predicates
163                        .iter()
164                        .copied()
165                        .chain([(tref.upcast(tcx), DUMMY_SP)]),
166                );
167            }
168            predicates
169        }
170        _ => GenericPredicates::default(),
171    };
172    if options.prune_sized {
173        prune_sized_predicates(tcx, &mut predicates);
174    }
175    predicates
176}
177
178/// Erase free regions from the given value. Largely copied from `tcx.erase_regions`, but also
179/// erases bound regions that are bound outside `value`, so we can call this function inside a
180/// `Binder`.
181fn erase_free_regions<'tcx, T>(tcx: TyCtxt<'tcx>, value: T) -> T
182where
183    T: TypeFoldable<TyCtxt<'tcx>>,
184{
185    use rustc_middle::ty;
186    struct RegionEraserVisitor<'tcx> {
187        tcx: TyCtxt<'tcx>,
188        depth: u32,
189    }
190
191    impl<'tcx> TypeFolder<TyCtxt<'tcx>> for RegionEraserVisitor<'tcx> {
192        fn cx(&self) -> TyCtxt<'tcx> {
193            self.tcx
194        }
195
196        fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
197            ty.super_fold_with(self)
198        }
199
200        fn fold_binder<T>(&mut self, t: ty::Binder<'tcx, T>) -> ty::Binder<'tcx, T>
201        where
202            T: TypeFoldable<TyCtxt<'tcx>>,
203        {
204            let t = self.tcx.anonymize_bound_vars(t);
205            self.depth += 1;
206            let t = t.super_fold_with(self);
207            self.depth -= 1;
208            t
209        }
210
211        fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
212            // We don't erase bound regions that are bound inside the expression we started with,
213            // but we do erase those that point "outside of it".
214            match r.kind() {
215                ty::ReBound(dbid, _) if dbid.as_u32() < self.depth => r,
216                _ => self.tcx.lifetimes.re_erased,
217            }
218        }
219    }
220    value.fold_with(&mut RegionEraserVisitor { tcx, depth: 0 })
221}
222
223// Normalize and erase lifetimes, erasing more lifetimes than normal because we might be already
224// inside a binder and rustc doesn't like that.
225pub fn erase_and_norm<'tcx, T>(tcx: TyCtxt<'tcx>, typing_env: TypingEnv<'tcx>, x: T) -> T
226where
227    T: TypeFoldable<TyCtxt<'tcx>> + Copy,
228{
229    erase_free_regions(
230        tcx,
231        tcx.try_normalize_erasing_regions(typing_env, x)
232            .unwrap_or(x),
233    )
234}
235
236/// Given our currently hacky handling of binders, in order for trait resolution to work we must
237/// empty out the binders of trait refs. Specifically it's so that we can reconnect associated type
238/// constraints with the trait ref they come from, given that the projection in question doesn't
239/// track the right binder currently.
240pub fn normalize_bound_val<'tcx, T>(
241    tcx: TyCtxt<'tcx>,
242    typing_env: TypingEnv<'tcx>,
243    x: Binder<'tcx, T>,
244) -> Binder<'tcx, T>
245where
246    T: TypeFoldable<TyCtxt<'tcx>> + Copy,
247{
248    Binder::dummy(erase_and_norm(tcx, typing_env, x.skip_binder()))
249}
250
251/// Returns true whenever `def_id` is `MetaSized`, `Sized` or `PointeeSized`.
252pub fn is_sized_related_trait<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId) -> bool {
253    use rustc_hir::lang_items::LangItem;
254    let lang_item = tcx.as_lang_item(def_id);
255    matches!(
256        lang_item,
257        Some(LangItem::PointeeSized | LangItem::MetaSized | LangItem::Sized)
258    )
259}
260
261/// Given a `GenericPredicates`, prune every occurence of a sized-related clause.
262/// Prunes bounds of the shape `T: MetaSized`, `T: Sized` or `T: PointeeSized`.
263fn prune_sized_predicates<'tcx>(
264    tcx: TyCtxt<'tcx>,
265    generic_predicates: &mut GenericPredicates<'tcx>,
266) {
267    let predicates: Vec<(Clause<'tcx>, rustc_span::Span)> = generic_predicates
268        .predicates
269        .iter()
270        .filter(|(clause, _)| {
271            clause.as_trait_clause().is_some_and(|trait_predicate| {
272                !is_sized_related_trait(tcx, trait_predicate.skip_binder().def_id())
273            })
274        })
275        .copied()
276        .collect();
277    if predicates.len() != generic_predicates.predicates.len() {
278        generic_predicates.predicates = tcx.arena.alloc_slice(&predicates);
279    }
280}
281
282pub trait ToPolyTraitRef<'tcx> {
283    fn to_poly_trait_ref(&self) -> PolyTraitRef<'tcx>;
284}
285
286impl<'tcx> ToPolyTraitRef<'tcx> for PolyTraitPredicate<'tcx> {
287    fn to_poly_trait_ref(&self) -> PolyTraitRef<'tcx> {
288        self.map_bound_ref(|trait_pred| trait_pred.trait_ref)
289    }
290}
hax_frontend_exporter/traits/utils.rs

hax_frontend_exporter/traits/
utils.rs
