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::LangItem;
31use rustc_hir::def::DefKind;
32use rustc_middle::ty::*;
33use rustc_span::def_id::DefId;
34use rustc_span::{DUMMY_SP, Span};
35use std::borrow::Cow;
36
37pub type Predicates<'tcx> = Cow<'tcx, [(Clause<'tcx>, Span)]>;
38
39/// Returns a list of type predicates for the definition with ID `def_id`, including inferred
40/// lifetime constraints. This is the basic list of predicates we use for essentially all items.
41pub fn predicates_defined_on(tcx: TyCtxt<'_>, def_id: DefId) -> Predicates<'_> {
42    let mut result = Cow::Borrowed(tcx.explicit_predicates_of(def_id).predicates);
43    let inferred_outlives = tcx.inferred_outlives_of(def_id);
44    if !inferred_outlives.is_empty() {
45        result.to_mut().extend(
46            inferred_outlives
47                .iter()
48                .map(|(clause, span)| ((*clause).upcast(tcx), *span)),
49        );
50    }
51    result
52}
53
54/// Add `T: Destruct` bounds for every generic parameter of the given item.
55fn add_destruct_bounds<'tcx>(
56    tcx: TyCtxt<'tcx>,
57    def_id: DefId,
58    predicates: &mut Vec<(Clause<'tcx>, Span)>,
59) {
60    let def_kind = tcx.def_kind(def_id);
61    if matches!(def_kind, DefKind::Closure) {
62        // Closures have fictitious weird type parameters in their `own_args` that we don't want to
63        // add `Destruct` bounds for.
64        return;
65    }
66    // Add a `T: Destruct` bound for every generic.
67    let destruct_trait = tcx.lang_items().destruct_trait().unwrap();
68    let extra_bounds = tcx
69        .generics_of(def_id)
70        .own_params
71        .iter()
72        .filter(|param| matches!(param.kind, GenericParamDefKind::Type { .. }))
73        .map(|param| tcx.mk_param_from_def(param))
74        .map(|ty| Binder::dummy(TraitRef::new(tcx, destruct_trait, [ty])))
75        .map(|tref| tref.upcast(tcx))
76        .map(|clause| (clause, DUMMY_SP));
77    predicates.extend(extra_bounds);
78}
79
80/// The predicates that must hold to mention this item. E.g.
81///
82/// ```ignore
83/// // `U: OtherTrait` is required, `Self: Sized` is implied.
84/// trait Trait<U: OtherTrait>: Sized {
85///     // `T: Clone` is required, `Self::Type<T>: Debug` is implied.
86///     type Type<T: Clone>: Debug;
87/// }
88/// ```
89///
90/// If `add_drop` is true, we add a `T: Drop` bound for every type generic.
91pub fn required_predicates<'tcx>(
92    tcx: TyCtxt<'tcx>,
93    def_id: DefId,
94    options: BoundsOptions,
95) -> Predicates<'tcx> {
96    use DefKind::*;
97    let def_kind = tcx.def_kind(def_id);
98    let mut predicates = match def_kind {
99        AssocConst
100        | AssocFn
101        | AssocTy
102        | Const
103        | Enum
104        | Fn
105        | ForeignTy
106        | Impl { .. }
107        | OpaqueTy
108        | Static { .. }
109        | Struct
110        | TyAlias
111        | Union => predicates_defined_on(tcx, def_id),
112        // We consider all predicates on traits to be outputs
113        Trait | TraitAlias => Default::default(),
114        // `predicates_defined_on` ICEs on other def kinds.
115        _ => Default::default(),
116    };
117    // For methods and assoc consts in trait definitions, we add an explicit `Self: Trait` clause.
118    // Associated types get to use the implicit `Self: Trait` clause instead.
119    if !matches!(def_kind, AssocTy)
120        && let Some(trait_def_id) = tcx.trait_of_assoc(def_id)
121    {
122        let self_clause = self_predicate(tcx, trait_def_id).upcast(tcx);
123        predicates.to_mut().insert(0, (self_clause, DUMMY_SP));
124    }
125    if options.resolve_destruct && !matches!(def_kind, Trait | TraitAlias) {
126        // Add a `T: Destruct` bound for every generic. For traits we consider these predicates
127        // implied instead of required.
128        add_destruct_bounds(tcx, def_id, predicates.to_mut());
129    }
130    if options.prune_sized {
131        prune_sized_predicates(tcx, &mut predicates);
132    }
133    predicates
134}
135
136/// The special "self" predicate on a trait.
137pub fn self_predicate<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId) -> PolyTraitRef<'tcx> {
138    // Copied from the code of `tcx.predicates_of()`.
139    Binder::dummy(TraitRef::identity(tcx, def_id))
140}
141
142/// The predicates that can be deduced from the presence of this item in a signature. We only
143/// consider predicates implied by traits here, not implied bounds such as `&'a T` implying `T:
144/// 'a`. E.g.
145///
146/// ```ignore
147/// // `U: OtherTrait` is required, `Self: Sized` is implied.
148/// trait Trait<U: OtherTrait>: Sized {
149///     // `T: Clone` is required, `Self::Type<T>: Debug` is implied.
150///     type Type<T: Clone>: Debug;
151/// }
152/// ```
153///
154/// If `add_drop` is true, we add a `T: Drop` bound for every type generic and associated type.
155pub fn implied_predicates<'tcx>(
156    tcx: TyCtxt<'tcx>,
157    def_id: DefId,
158    options: BoundsOptions,
159) -> Predicates<'tcx> {
160    use DefKind::*;
161    let parent = tcx.opt_parent(def_id);
162    let mut predicates = match tcx.def_kind(def_id) {
163        // We consider all predicates on traits to be outputs
164        Trait | TraitAlias => {
165            let mut predicates = predicates_defined_on(tcx, def_id);
166            if options.resolve_destruct {
167                // Add a `T: Drop` bound for every generic, unless the current trait is `Drop` itself, or a
168                // built-in marker trait that we know doesn't need the bound.
169                if !matches!(
170                    tcx.as_lang_item(def_id),
171                    Some(
172                        LangItem::Destruct
173                            | LangItem::Sized
174                            | LangItem::MetaSized
175                            | LangItem::PointeeSized
176                            | LangItem::DiscriminantKind
177                            | LangItem::PointeeTrait
178                            | LangItem::Tuple
179                    )
180                ) {
181                    add_destruct_bounds(tcx, def_id, predicates.to_mut());
182                }
183            }
184            predicates
185        }
186        AssocTy if matches!(tcx.def_kind(parent.unwrap()), Trait) => {
187            // `skip_binder` is for the GAT `EarlyBinder`
188            let mut predicates = Cow::Borrowed(tcx.explicit_item_bounds(def_id).skip_binder());
189            if options.resolve_destruct {
190                // Add a `Drop` bound to the assoc item.
191                let destruct_trait = tcx.lang_items().destruct_trait().unwrap();
192                let ty =
193                    Ty::new_projection(tcx, def_id, GenericArgs::identity_for_item(tcx, def_id));
194                let tref = Binder::dummy(TraitRef::new(tcx, destruct_trait, [ty]));
195                predicates.to_mut().push((tref.upcast(tcx), DUMMY_SP));
196            }
197            predicates
198        }
199        _ => Predicates::default(),
200    };
201    if options.prune_sized {
202        prune_sized_predicates(tcx, &mut predicates);
203    }
204    predicates
205}
206
207/// Normalize a value.
208pub fn normalize<'tcx, T>(tcx: TyCtxt<'tcx>, typing_env: TypingEnv<'tcx>, value: T) -> T
209where
210    T: TypeFoldable<TyCtxt<'tcx>> + Clone,
211{
212    use rustc_infer::infer::TyCtxtInferExt;
213    use rustc_middle::traits::ObligationCause;
214    use rustc_trait_selection::traits::query::normalize::QueryNormalizeExt;
215    let (infcx, param_env) = tcx.infer_ctxt().build_with_typing_env(typing_env);
216    infcx
217        .at(&ObligationCause::dummy(), param_env)
218        .query_normalize(value.clone())
219        // We ignore the generated outlives relations. Unsure what we should do with them.
220        .map(|x| x.value)
221        .unwrap_or(value)
222}
223
224/// Erase free regions from the given value. Largely copied from `tcx.erase_and_anonymize_regions`, but also
225/// erases bound regions that are bound outside `value`, so we can call this function inside a
226/// `Binder`.
227pub fn erase_free_regions<'tcx, T>(tcx: TyCtxt<'tcx>, value: T) -> T
228where
229    T: TypeFoldable<TyCtxt<'tcx>>,
230{
231    use rustc_middle::ty;
232    struct RegionEraserVisitor<'tcx> {
233        tcx: TyCtxt<'tcx>,
234        depth: u32,
235    }
236
237    impl<'tcx> TypeFolder<TyCtxt<'tcx>> for RegionEraserVisitor<'tcx> {
238        fn cx(&self) -> TyCtxt<'tcx> {
239            self.tcx
240        }
241
242        fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
243            ty.super_fold_with(self)
244        }
245
246        fn fold_binder<T>(&mut self, t: ty::Binder<'tcx, T>) -> ty::Binder<'tcx, T>
247        where
248            T: TypeFoldable<TyCtxt<'tcx>>,
249        {
250            let t = self.tcx.anonymize_bound_vars(t);
251            self.depth += 1;
252            let t = t.super_fold_with(self);
253            self.depth -= 1;
254            t
255        }
256
257        fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
258            // We don't erase bound regions that are bound inside the expression we started with,
259            // but we do erase those that point "outside of it".
260            match r.kind() {
261                ty::ReBound(BoundVarIndexKind::Bound(dbid), _) if dbid.as_u32() < self.depth => r,
262                _ => self.tcx.lifetimes.re_erased,
263            }
264        }
265    }
266    value.fold_with(&mut RegionEraserVisitor { tcx, depth: 0 })
267}
268
269// Normalize and erase lifetimes, erasing more lifetimes than normal because we might be already
270// inside a binder and rustc doesn't like that.
271pub fn erase_and_norm<'tcx, T>(tcx: TyCtxt<'tcx>, typing_env: TypingEnv<'tcx>, x: T) -> T
272where
273    T: TypeFoldable<TyCtxt<'tcx>> + Copy,
274{
275    erase_free_regions(
276        tcx,
277        tcx.try_normalize_erasing_regions(typing_env, x)
278            .unwrap_or(x),
279    )
280}
281
282/// Given our currently hacky handling of binders, in order for trait resolution to work we must
283/// empty out the binders of trait refs. Specifically it's so that we can reconnect associated type
284/// constraints with the trait ref they come from, given that the projection in question doesn't
285/// track the right binder currently.
286pub fn normalize_bound_val<'tcx, T>(
287    tcx: TyCtxt<'tcx>,
288    typing_env: TypingEnv<'tcx>,
289    x: Binder<'tcx, T>,
290) -> Binder<'tcx, T>
291where
292    T: TypeFoldable<TyCtxt<'tcx>> + Copy,
293{
294    Binder::dummy(erase_and_norm(tcx, typing_env, x.skip_binder()))
295}
296
297/// Returns true whenever `def_id` is `MetaSized`, `Sized` or `PointeeSized`.
298pub fn is_sized_related_trait<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId) -> bool {
299    use rustc_hir::lang_items::LangItem;
300    let lang_item = tcx.as_lang_item(def_id);
301    matches!(
302        lang_item,
303        Some(LangItem::PointeeSized | LangItem::MetaSized | LangItem::Sized)
304    )
305}
306
307/// Given a `GenericPredicates`, prune every occurence of a sized-related clause.
308/// Prunes bounds of the shape `T: MetaSized`, `T: Sized` or `T: PointeeSized`.
309fn prune_sized_predicates<'tcx>(tcx: TyCtxt<'tcx>, generic_predicates: &mut Predicates<'tcx>) {
310    let predicates: Vec<(Clause<'tcx>, rustc_span::Span)> = generic_predicates
311        .iter()
312        .filter(|(clause, _)| {
313            clause.as_trait_clause().is_some_and(|trait_predicate| {
314                !is_sized_related_trait(tcx, trait_predicate.skip_binder().def_id())
315            })
316        })
317        .copied()
318        .collect();
319    if predicates.len() != generic_predicates.len() {
320        *generic_predicates.to_mut() = predicates;
321    }
322}
323
324pub trait ToPolyTraitRef<'tcx> {
325    fn to_poly_trait_ref(&self) -> PolyTraitRef<'tcx>;
326}
327
328impl<'tcx> ToPolyTraitRef<'tcx> for PolyTraitPredicate<'tcx> {
329    fn to_poly_trait_ref(&self) -> PolyTraitRef<'tcx> {
330        self.map_bound_ref(|trait_pred| trait_pred.trait_ref)
331    }
332}
hax_frontend_exporter/traits/utils.rs

hax_frontend_exporter/traits/
utils.rs
