hax_frontend_exporter/
traits.rs

1use crate::prelude::*;
2
3#[cfg(feature = "rustc")]
4pub mod resolution;
5#[cfg(feature = "rustc")]
6mod utils;
7#[cfg(feature = "rustc")]
8pub use utils::{
9    Predicates, ToPolyTraitRef, erase_and_norm, erase_free_regions, implied_predicates, normalize,
10    predicates_defined_on, required_predicates, self_predicate,
11};
12
13#[cfg(feature = "rustc")]
14pub use resolution::PredicateSearcher;
15#[cfg(feature = "rustc")]
16use rustc_middle::ty;
17#[cfg(feature = "rustc")]
18use rustc_span::def_id::DefId as RDefId;
19
20#[cfg(feature = "rustc")]
21pub use utils::is_sized_related_trait;
22
23#[derive_group(Serializers)]
24#[derive(Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord, JsonSchema)]
25pub enum ImplExprPathChunk {
26    AssocItem {
27        /// Reference to the item, with generics (for GATs), e.g. the `T` and `T: Clone` `ImplExpr`
28        /// in the following example:
29        /// ```ignore
30        /// trait Foo {
31        ///     type Type<T: Clone>: Debug;
32        /// }
33        /// ```
34        item: ItemRef,
35        assoc_item: AssocItem,
36        /// The implemented predicate.
37        predicate: Binder<TraitPredicate>,
38        predicate_id: PredicateId,
39        /// The index of this predicate in the list returned by `implied_predicates`.
40        index: usize,
41    },
42    Parent {
43        /// The implemented predicate.
44        predicate: Binder<TraitPredicate>,
45        predicate_id: PredicateId,
46        /// The index of this predicate in the list returned by `implied_predicates`.
47        index: usize,
48    },
49}
50
51#[cfg(feature = "rustc")]
52impl<'tcx, S: UnderOwnerState<'tcx>> SInto<S, ImplExprPathChunk> for resolution::PathChunk<'tcx> {
53    fn sinto(&self, s: &S) -> ImplExprPathChunk {
54        match self {
55            resolution::PathChunk::AssocItem {
56                item,
57                generic_args,
58                predicate,
59                index,
60                ..
61            } => ImplExprPathChunk::AssocItem {
62                item: translate_item_ref(s, item.def_id, generic_args),
63                assoc_item: AssocItem::sfrom(s, item),
64                predicate: predicate.sinto(s),
65                predicate_id: <_ as SInto<_, Clause>>::sinto(predicate, s).id,
66                index: index.sinto(s),
67            },
68            resolution::PathChunk::Parent {
69                predicate, index, ..
70            } => ImplExprPathChunk::Parent {
71                predicate: predicate.sinto(s),
72                predicate_id: <_ as SInto<_, Clause>>::sinto(predicate, s).id,
73                index: index.sinto(s),
74            },
75        }
76    }
77}
78
79/// The source of a particular trait implementation. Most often this is either `Concrete` for a
80/// concrete `impl Trait for Type {}` item, or `LocalBound` for a context-bound `where T: Trait`.
81#[derive(AdtInto)]
82#[args(<'tcx, S: UnderOwnerState<'tcx> >, from: resolution::ImplExprAtom<'tcx>, state: S as s)]
83#[derive_group(Serializers)]
84#[derive(Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord, JsonSchema)]
85pub enum ImplExprAtom {
86    /// A concrete `impl Trait for Type {}` item.
87    #[custom_arm(FROM_TYPE::Concrete { def_id, generics } => TO_TYPE::Concrete(
88        translate_item_ref(s, *def_id, generics),
89    ),)]
90    Concrete(ItemRef),
91    /// A context-bound clause like `where T: Trait`.
92    LocalBound {
93        #[not_in_source]
94        #[value({
95            let Self::LocalBound { predicate, .. } = self else { unreachable!() };
96            predicate.sinto(s).id
97        })]
98        predicate_id: PredicateId,
99        /// The nth (non-self) predicate found for this item. We use predicates from
100        /// `required_predicates` starting from the parentmost item.
101        index: usize,
102        r#trait: Binder<TraitRef>,
103        path: Vec<ImplExprPathChunk>,
104    },
105    /// The implicit `Self: Trait` clause present inside a `trait Trait {}` item.
106    // TODO: should we also get that clause for trait impls?
107    SelfImpl {
108        r#trait: Binder<TraitRef>,
109        path: Vec<ImplExprPathChunk>,
110    },
111    /// `dyn Trait` is a wrapped value with a virtual table for trait
112    /// `Trait`.  In other words, a value `dyn Trait` is a dependent
113    /// triple that gathers a type τ, a value of type τ and an
114    /// instance of type `Trait`.
115    /// `dyn Trait` implements `Trait` using a built-in implementation; this refers to that
116    /// built-in implementation.
117    Dyn,
118    /// A built-in trait whose implementation is computed by the compiler, such as `FnMut`. This
119    /// morally points to an invisible `impl` block; as such it contains the information we may
120    /// need from one.
121    Builtin {
122        /// Extra data for the given trait.
123        trait_data: BuiltinTraitData,
124        /// The `ImplExpr`s required to satisfy the implied predicates on the trait declaration.
125        /// E.g. since `FnMut: FnOnce`, a built-in `T: FnMut` impl would have an `ImplExpr` for `T:
126        /// FnOnce`.
127        impl_exprs: Vec<ImplExpr>,
128        /// The values of the associated types for this trait.
129        types: Vec<(DefId, Ty, Vec<ImplExpr>)>,
130    },
131    /// An error happened while resolving traits.
132    Error(String),
133}
134
135#[derive(AdtInto)]
136#[args(<'tcx, S: UnderOwnerState<'tcx> >, from: resolution::BuiltinTraitData<'tcx>, state: S as s)]
137#[derive_group(Serializers)]
138#[derive(Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord, JsonSchema)]
139pub enum BuiltinTraitData {
140    /// A virtual `Destruct` implementation.
141    /// `Destruct` is implemented automatically for all types. For our purposes, we chose to attach
142    /// the information about `drop_in_place` to that trait. This data tells us what kind of
143    /// `drop_in_place` the target type has.
144    Destruct(DestructData),
145    /// Some other builtin trait.
146    Other,
147}
148
149#[derive(AdtInto)]
150#[args(<'tcx, S: UnderOwnerState<'tcx> >, from: resolution::DestructData<'tcx>, state: S as s)]
151#[derive_group(Serializers)]
152#[derive(Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord, JsonSchema)]
153pub enum DestructData {
154    /// A drop that does nothing, e.g. for scalars and pointers.
155    Noop,
156    /// An implicit `Destruct` local clause, if the `resolve_destruct_bounds` option is `false`. If
157    /// that option is `true`, we'll add `Destruct` bounds to every type param, and use that to
158    /// resolve `Destruct` impls of generics. If it's `false`, we use this variant to indicate that
159    /// the clause comes from a generic or associated type.
160    Implicit,
161    /// The `drop_in_place` is known and non-trivial.
162    Glue {
163        /// The type we're generating glue for.
164        ty: Ty,
165    },
166}
167
168/// An `ImplExpr` describes the full data of a trait implementation. Because of generics, this may
169/// need to combine several concrete trait implementation items. For example, `((1u8, 2u8),
170/// "hello").clone()` combines the generic implementation of `Clone` for `(A, B)` with the
171/// concrete implementations for `u8` and `&str`, represented as a tree.
172#[derive_group(Serializers)]
173#[derive(Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord, JsonSchema, AdtInto)]
174#[args(<'tcx, S: UnderOwnerState<'tcx> >, from: resolution::ImplExpr<'tcx>, state: S as s)]
175pub struct ImplExpr {
176    /// The trait this is an impl for.
177    pub r#trait: Binder<TraitRef>,
178    /// The kind of implemention of the root of the tree.
179    pub r#impl: ImplExprAtom,
180}
181
182/// Given a clause `clause` declared on `item_did`'s counterpart in the trait that `impl_did`
183/// implements, substitutes the impl's arguments into it and (1) derives a `Clause` and (2)
184/// resolves an `ImplExpr`. `item_did` is `impl_did` itself for a clause of the trait, or one of
185/// the impl's associated items for a clause of that item; the latter appends a generic associated
186/// type's own parameters, which is the arity the declared clause expects.
187#[cfg(feature = "rustc")]
188pub fn super_clause_to_clause_and_impl_expr<'tcx, S: UnderOwnerState<'tcx>>(
189    s: &S,
190    impl_did: rustc_span::def_id::DefId,
191    item_did: rustc_span::def_id::DefId,
192    clause: rustc_middle::ty::Clause<'tcx>,
193    span: rustc_span::Span,
194) -> Option<(Clause, ImplExpr, Span)> {
195    let tcx = s.base().tcx;
196    if !matches!(
197        tcx.def_kind(impl_did),
198        rustc_hir::def::DefKind::Impl { of_trait: true }
199    ) {
200        return None;
201    }
202    let impl_trait_ref = tcx.impl_trait_ref(impl_did).instantiate_identity();
203    let original_predicate_id = {
204        // We don't want the id of the substituted clause id, but the
205        // original clause id (with, i.e., `Self`)
206        let s = &s.with_owner_id(impl_trait_ref.def_id);
207        clause.sinto(s).id
208    };
209    let args = ty::GenericArgs::identity_for_item(tcx, item_did).rebase_onto(
210        tcx,
211        impl_did,
212        impl_trait_ref.args,
213    );
214    let new_clause = ty::EarlyBinder::bind(clause).instantiate(tcx, args);
215    let impl_expr = solve_trait(
216        s,
217        new_clause
218            .as_predicate()
219            .as_trait_clause()?
220            .to_poly_trait_ref(),
221    );
222    let mut new_clause_no_binder = new_clause.sinto(s);
223    new_clause_no_binder.id = original_predicate_id;
224    Some((new_clause_no_binder, impl_expr, span.sinto(s)))
225}
226
227/// This is the entrypoint of the solving.
228#[cfg(feature = "rustc")]
229#[tracing::instrument(level = "trace", skip(s))]
230pub fn solve_trait<'tcx, S: UnderOwnerState<'tcx>>(
231    s: &S,
232    trait_ref: rustc_middle::ty::PolyTraitRef<'tcx>,
233) -> ImplExpr {
234    let warn = |msg: &str| {
235        if !s.base().silence_resolution_errors {
236            crate::warning!(s, "{}", msg)
237        }
238    };
239    if let Some(impl_expr) = s.with_cache(|cache| cache.impl_exprs.get(&trait_ref).cloned()) {
240        return impl_expr;
241    }
242    let resolved =
243        s.with_predicate_searcher(|pred_searcher| pred_searcher.resolve(&trait_ref, &warn));
244    let impl_expr = match resolved {
245        Ok(x) => x.sinto(s),
246        Err(e) => crate::fatal!(s, "{}", e),
247    };
248    s.with_cache(|cache| cache.impl_exprs.insert(trait_ref, impl_expr.clone()));
249    impl_expr
250}
251
252/// Translate a reference to an item, resolving the appropriate trait clauses as needed.
253#[cfg(feature = "rustc")]
254#[tracing::instrument(level = "trace", skip(s), ret)]
255pub fn translate_item_ref<'tcx, S: UnderOwnerState<'tcx>>(
256    s: &S,
257    def_id: RDefId,
258    generics: ty::GenericArgsRef<'tcx>,
259) -> ItemRef {
260    ItemRef::translate(s, def_id, generics)
261}
262
263/// Solve the trait obligations for a specific item use (for example, a method call, an ADT, etc.)
264/// in the current context. Just like generic args include generics of parent items, this includes
265/// impl exprs for parent items.
266#[cfg(feature = "rustc")]
267#[tracing::instrument(level = "trace", skip(s), ret)]
268pub fn solve_item_required_traits<'tcx, S: UnderOwnerState<'tcx>>(
269    s: &S,
270    def_id: RDefId,
271    generics: ty::GenericArgsRef<'tcx>,
272) -> Vec<ImplExpr> {
273    fn accumulate<'tcx, S: UnderOwnerState<'tcx>>(
274        s: &S,
275        def_id: RDefId,
276        generics: ty::GenericArgsRef<'tcx>,
277        impl_exprs: &mut Vec<ImplExpr>,
278    ) {
279        let tcx = s.base().tcx;
280        use rustc_hir::def::DefKind::*;
281        match tcx.def_kind(def_id) {
282            AssocTy | AssocFn | AssocConst | Closure | Ctor(..) | Variant => {
283                let parent = tcx.parent(def_id);
284                accumulate(s, parent, generics, impl_exprs);
285            }
286            _ => {}
287        }
288        let predicates = required_predicates(tcx, def_id, s.base().options.bounds_options);
289        impl_exprs.extend(solve_item_traits_inner(s, generics, predicates));
290    }
291    let mut impl_exprs = vec![];
292    accumulate(s, def_id, generics, &mut impl_exprs);
293    impl_exprs
294}
295
296/// Solve the trait obligations for implementing a trait (or for trait associated type bounds) in
297/// the current context.
298#[cfg(feature = "rustc")]
299#[tracing::instrument(level = "trace", skip(s), ret)]
300pub fn solve_item_implied_traits<'tcx, S: UnderOwnerState<'tcx>>(
301    s: &S,
302    def_id: RDefId,
303    generics: ty::GenericArgsRef<'tcx>,
304) -> Vec<ImplExpr> {
305    let predicates = implied_predicates(s.base().tcx, def_id, s.base().options.bounds_options);
306    solve_item_traits_inner(s, generics, predicates)
307}
308
309/// Apply the given generics to the provided clauses and resolve the trait references in the
310/// current context.
311#[cfg(feature = "rustc")]
312fn solve_item_traits_inner<'tcx, S: UnderOwnerState<'tcx>>(
313    s: &S,
314    generics: ty::GenericArgsRef<'tcx>,
315    predicates: utils::Predicates<'tcx>,
316) -> Vec<ImplExpr> {
317    let tcx = s.base().tcx;
318    let typing_env = s.typing_env();
319    predicates
320        .iter()
321        .map(|(clause, _span)| *clause)
322        .filter_map(|clause| clause.as_trait_clause())
323        .map(|clause| clause.to_poly_trait_ref())
324        // Substitute the item generics
325        .map(|trait_ref| ty::EarlyBinder::bind(trait_ref).instantiate(tcx, generics))
326        // We unfortunately don't have a way to normalize without erasing regions.
327        .map(|trait_ref| {
328            tcx.try_normalize_erasing_regions(typing_env, trait_ref)
329                .unwrap_or(trait_ref)
330        })
331        // Resolve
332        .map(|trait_ref| solve_trait(s, trait_ref))
333        .collect()
334}
335
336/// Retrieve the `Self: Trait` clause for a trait associated item.
337#[cfg(feature = "rustc")]
338pub fn self_clause_for_item<'tcx, S: UnderOwnerState<'tcx>>(
339    s: &S,
340    def_id: RDefId,
341    generics: rustc_middle::ty::GenericArgsRef<'tcx>,
342) -> Option<ImplExpr> {
343    let tcx = s.base().tcx;
344
345    let tr_def_id = tcx.trait_of_assoc(def_id)?;
346    // The "self" predicate in the context of the trait.
347    let self_pred = self_predicate(tcx, tr_def_id);
348    // Substitute to be in the context of the current item.
349    let generics = generics.truncate_to(tcx, tcx.generics_of(tr_def_id));
350    let self_pred = ty::EarlyBinder::bind(self_pred).instantiate(tcx, generics);
351
352    // Resolve
353    Some(solve_trait(s, self_pred))
354}
355
356/// Solve the `T: Sized` predicate.
357#[cfg(feature = "rustc")]
358pub fn solve_sized<'tcx, S: UnderOwnerState<'tcx>>(s: &S, ty: ty::Ty<'tcx>) -> ImplExpr {
359    let tcx = s.base().tcx;
360    let sized_trait = tcx.lang_items().sized_trait().unwrap();
361    let ty = erase_free_regions(tcx, ty);
362    let tref = ty::Binder::dummy(ty::TraitRef::new(tcx, sized_trait, [ty]));
363    solve_trait(s, tref)
364}
hax_frontend_exporter/traits.rs

hax_frontend_exporter/
traits.rs
