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    // Recover the bounds a type alias's body needs but doesn't declare (see
118    // `type_alias_implied_predicates`).
119    if matches!(def_kind, TyAlias) {
120        let predicates = predicates.to_mut();
121        for (clause, span) in type_alias_implied_predicates(tcx, def_id) {
122            if !predicates.iter().any(|(c, _)| *c == clause) {
123                predicates.push((clause, span));
124            }
125        }
126    }
127    // For methods and assoc consts in trait definitions, we add an explicit `Self: Trait` clause.
128    // Associated types get to use the implicit `Self: Trait` clause instead.
129    if !matches!(def_kind, AssocTy)
130        && let Some(trait_def_id) = tcx.trait_of_assoc(def_id)
131    {
132        let self_clause = self_predicate(tcx, trait_def_id).upcast(tcx);
133        predicates.to_mut().insert(0, (self_clause, DUMMY_SP));
134    }
135    if options.resolve_destruct && !matches!(def_kind, Trait | TraitAlias) {
136        // Add a `T: Destruct` bound for every generic. For traits we consider these predicates
137        // implied instead of required.
138        add_destruct_bounds(tcx, def_id, predicates.to_mut());
139    }
140    if options.prune_sized {
141        prune_sized_predicates(tcx, &mut predicates);
142    }
143    predicates
144}
145
146/// Bounds that a free type alias's body needs but that Rust doesn't record on the alias. E.g. for
147/// `type F<G> = <G as T>::A`, translating the body requires `G: T`, yet that bound isn't part of the
148/// alias's predicates. We recover such bounds from the well-formedness obligations of the body.
149pub fn type_alias_implied_predicates<'tcx>(
150    tcx: TyCtxt<'tcx>,
151    def_id: DefId,
152) -> Vec<(Clause<'tcx>, Span)> {
153    use super::resolution::shallow_resolve_trait_ref;
154    use rustc_infer::infer::TyCtxtInferExt;
155    use rustc_middle::ty::TypeVisitableExt;
156    use rustc_trait_selection::traits::wf;
157    if !matches!(tcx.def_kind(def_id), DefKind::TyAlias) {
158        return vec![];
159    }
160    let Some(local_def_id) = def_id.as_local() else {
161        return vec![];
162    };
163    let ty = tcx.type_of(def_id).instantiate_identity();
164    let span = tcx.def_span(def_id);
165    let param_env = tcx.param_env(def_id);
166    let typing_env = TypingEnv {
167        param_env,
168        typing_mode: TypingMode::PostAnalysis,
169    };
170    let (infcx, wf_param_env) = tcx.infer_ctxt().build_with_typing_env(typing_env);
171    let Some(obligations) = wf::obligations(&infcx, wf_param_env, local_def_id, 0, ty.into(), span)
172    else {
173        return vec![];
174    };
175    obligations
176        .into_iter()
177        .filter_map(|obligation| obligation.predicate.as_clause())
178        .filter_map(|clause| Some((clause, clause.as_trait_clause()?.to_poly_trait_ref())))
179        // Inference variables can't be turned into bounds (and would make selection panic below).
180        .filter(|(_, trait_ref)| !trait_ref.has_infer())
181        // Keep only the bounds that don't already hold: e.g. `Global: Allocator` resolves on its
182        // own, while `G: T` is the one we need to assume.
183        .filter(|(_, trait_ref)| shallow_resolve_trait_ref(tcx, param_env, *trait_ref).is_err())
184        .map(|(clause, _)| (clause, span))
185        .collect()
186}
187
188/// The special "self" predicate on a trait.
189pub fn self_predicate<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId) -> PolyTraitRef<'tcx> {
190    // Copied from the code of `tcx.predicates_of()`.
191    Binder::dummy(TraitRef::identity(tcx, def_id))
192}
193
194/// The predicates that can be deduced from the presence of this item in a signature. We only
195/// consider predicates implied by traits here, not implied bounds such as `&'a T` implying `T:
196/// 'a`. E.g.
197///
198/// ```ignore
199/// // `U: OtherTrait` is required, `Self: Sized` is implied.
200/// trait Trait<U: OtherTrait>: Sized {
201///     // `T: Clone` is required, `Self::Type<T>: Debug` is implied.
202///     type Type<T: Clone>: Debug;
203/// }
204/// ```
205///
206/// If `add_drop` is true, we add a `T: Drop` bound for every type generic and associated type.
207pub fn implied_predicates<'tcx>(
208    tcx: TyCtxt<'tcx>,
209    def_id: DefId,
210    options: BoundsOptions,
211) -> Predicates<'tcx> {
212    use DefKind::*;
213    let parent = tcx.opt_parent(def_id);
214    let mut predicates = match tcx.def_kind(def_id) {
215        // We consider all predicates on traits to be outputs
216        Trait | TraitAlias => {
217            let mut predicates = predicates_defined_on(tcx, def_id);
218            if options.resolve_destruct {
219                // Add a `T: Drop` bound for every generic, unless the current trait is `Drop` itself, or a
220                // built-in marker trait that we know doesn't need the bound.
221                if !matches!(
222                    tcx.as_lang_item(def_id),
223                    Some(
224                        LangItem::Destruct
225                            | LangItem::Sized
226                            | LangItem::MetaSized
227                            | LangItem::PointeeSized
228                            | LangItem::DiscriminantKind
229                            | LangItem::PointeeTrait
230                            | LangItem::Tuple
231                    )
232                ) {
233                    add_destruct_bounds(tcx, def_id, predicates.to_mut());
234                }
235            }
236            predicates
237        }
238        AssocTy if matches!(tcx.def_kind(parent.unwrap()), Trait) => {
239            // `skip_binder` is for the GAT `EarlyBinder`
240            let mut predicates = Cow::Borrowed(tcx.explicit_item_bounds(def_id).skip_binder());
241            if options.resolve_destruct {
242                // Add a `Drop` bound to the assoc item.
243                let destruct_trait = tcx.lang_items().destruct_trait().unwrap();
244                let ty =
245                    Ty::new_projection(tcx, def_id, GenericArgs::identity_for_item(tcx, def_id));
246                let tref = Binder::dummy(TraitRef::new(tcx, destruct_trait, [ty]));
247                predicates.to_mut().push((tref.upcast(tcx), DUMMY_SP));
248            }
249            predicates
250        }
251        _ => Predicates::default(),
252    };
253    if options.prune_sized {
254        prune_sized_predicates(tcx, &mut predicates);
255    }
256    predicates
257}
258
259/// Normalize a value.
260pub fn normalize<'tcx, T>(tcx: TyCtxt<'tcx>, typing_env: TypingEnv<'tcx>, value: T) -> T
261where
262    T: TypeFoldable<TyCtxt<'tcx>> + Clone,
263{
264    use rustc_infer::infer::TyCtxtInferExt;
265    use rustc_middle::traits::ObligationCause;
266    use rustc_trait_selection::traits::query::normalize::QueryNormalizeExt;
267    let (infcx, param_env) = tcx.infer_ctxt().build_with_typing_env(typing_env);
268    infcx
269        .at(&ObligationCause::dummy(), param_env)
270        .query_normalize(value.clone())
271        // We ignore the generated outlives relations. Unsure what we should do with them.
272        .map(|x| x.value)
273        .unwrap_or(value)
274}
275
276/// Erase free regions from the given value. Largely copied from `tcx.erase_and_anonymize_regions`, but also
277/// erases bound regions that are bound outside `value`, so we can call this function inside a
278/// `Binder`.
279pub fn erase_free_regions<'tcx, T>(tcx: TyCtxt<'tcx>, value: T) -> T
280where
281    T: TypeFoldable<TyCtxt<'tcx>>,
282{
283    use rustc_middle::ty;
284    struct RegionEraserVisitor<'tcx> {
285        tcx: TyCtxt<'tcx>,
286        depth: u32,
287    }
288
289    impl<'tcx> TypeFolder<TyCtxt<'tcx>> for RegionEraserVisitor<'tcx> {
290        fn cx(&self) -> TyCtxt<'tcx> {
291            self.tcx
292        }
293
294        fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
295            ty.super_fold_with(self)
296        }
297
298        fn fold_binder<T>(&mut self, t: ty::Binder<'tcx, T>) -> ty::Binder<'tcx, T>
299        where
300            T: TypeFoldable<TyCtxt<'tcx>>,
301        {
302            let t = self.tcx.anonymize_bound_vars(t);
303            self.depth += 1;
304            let t = t.super_fold_with(self);
305            self.depth -= 1;
306            t
307        }
308
309        fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
310            // We don't erase bound regions that are bound inside the expression we started with,
311            // but we do erase those that point "outside of it".
312            match r.kind() {
313                ty::ReBound(BoundVarIndexKind::Bound(dbid), _) if dbid.as_u32() < self.depth => r,
314                _ => self.tcx.lifetimes.re_erased,
315            }
316        }
317    }
318    value.fold_with(&mut RegionEraserVisitor { tcx, depth: 0 })
319}
320
321// Normalize and erase lifetimes, erasing more lifetimes than normal because we might be already
322// inside a binder and rustc doesn't like that.
323pub fn erase_and_norm<'tcx, T>(tcx: TyCtxt<'tcx>, typing_env: TypingEnv<'tcx>, x: T) -> T
324where
325    T: TypeFoldable<TyCtxt<'tcx>> + Copy,
326{
327    erase_free_regions(
328        tcx,
329        tcx.try_normalize_erasing_regions(typing_env, x)
330            .unwrap_or(x),
331    )
332}
333
334/// Given our currently hacky handling of binders, in order for trait resolution to work we must
335/// empty out the binders of trait refs. Specifically it's so that we can reconnect associated type
336/// constraints with the trait ref they come from, given that the projection in question doesn't
337/// track the right binder currently.
338pub fn normalize_bound_val<'tcx, T>(
339    tcx: TyCtxt<'tcx>,
340    typing_env: TypingEnv<'tcx>,
341    x: Binder<'tcx, T>,
342) -> Binder<'tcx, T>
343where
344    T: TypeFoldable<TyCtxt<'tcx>> + Copy,
345{
346    Binder::dummy(erase_and_norm(tcx, typing_env, x.skip_binder()))
347}
348
349/// Returns true whenever `def_id` is `MetaSized`, `Sized` or `PointeeSized`.
350pub fn is_sized_related_trait<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId) -> bool {
351    use rustc_hir::lang_items::LangItem;
352    let lang_item = tcx.as_lang_item(def_id);
353    matches!(
354        lang_item,
355        Some(LangItem::PointeeSized | LangItem::MetaSized | LangItem::Sized)
356    )
357}
358
359/// Given a `GenericPredicates`, prune every occurence of a sized-related clause.
360/// Prunes bounds of the shape `T: MetaSized`, `T: Sized` or `T: PointeeSized`.
361fn prune_sized_predicates<'tcx>(tcx: TyCtxt<'tcx>, generic_predicates: &mut Predicates<'tcx>) {
362    let predicates: Vec<(Clause<'tcx>, rustc_span::Span)> = generic_predicates
363        .iter()
364        .filter(|(clause, _)| {
365            clause.as_trait_clause().is_none_or(|trait_predicate| {
366                !is_sized_related_trait(tcx, trait_predicate.skip_binder().def_id())
367            })
368        })
369        .copied()
370        .collect();
371    if predicates.len() != generic_predicates.len() {
372        *generic_predicates.to_mut() = predicates;
373    }
374}
375
376pub trait ToPolyTraitRef<'tcx> {
377    fn to_poly_trait_ref(&self) -> PolyTraitRef<'tcx>;
378}
379
380impl<'tcx> ToPolyTraitRef<'tcx> for PolyTraitPredicate<'tcx> {
381    fn to_poly_trait_ref(&self) -> PolyTraitRef<'tcx> {
382        self.map_bound_ref(|trait_pred| trait_pred.trait_ref)
383    }
384}
hax_frontend_exporter/traits/utils.rs

hax_frontend_exporter/traits/
utils.rs
