hax_frontend_exporter/
traits.rs

1use crate::prelude::*;
2
3#[cfg(feature = "rustc")]
4mod resolution;
5#[cfg(feature = "rustc")]
6mod utils;
7#[cfg(feature = "rustc")]
8pub use utils::{
9    erase_and_norm, implied_predicates, predicates_defined_on, required_predicates, self_predicate,
10    ToPolyTraitRef,
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#[derive(AdtInto)]
21#[args(<'tcx, S: UnderOwnerState<'tcx> >, from: resolution::PathChunk<'tcx>, state: S as s)]
22#[derive_group(Serializers)]
23#[derive(Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord, JsonSchema)]
24pub enum ImplExprPathChunk {
25    AssocItem {
26        item: AssocItem,
27        /// The arguments provided to the item (for GATs).
28        generic_args: Vec<GenericArg>,
29        /// The impl exprs that must be satisfied to apply the given arguments to the item. E.g.
30        /// `T: Clone` in the following example:
31        /// ```ignore
32        /// trait Foo {
33        ///     type Type<T: Clone>: Debug;
34        /// }
35        /// ```
36        impl_exprs: Vec<ImplExpr>,
37        /// The implemented predicate.
38        predicate: Binder<TraitPredicate>,
39        #[value(<_ as SInto<_, Clause>>::sinto(predicate, s).id)]
40        predicate_id: PredicateId,
41        /// The index of this predicate in the list returned by `implied_predicates`.
42        index: usize,
43    },
44    Parent {
45        /// The implemented predicate.
46        predicate: Binder<TraitPredicate>,
47        #[value(<_ as SInto<_, Clause>>::sinto(predicate, s).id)]
48        predicate_id: PredicateId,
49        /// The index of this predicate in the list returned by `implied_predicates`.
50        index: usize,
51    },
52}
53
54/// The source of a particular trait implementation. Most often this is either `Concrete` for a
55/// concrete `impl Trait for Type {}` item, or `LocalBound` for a context-bound `where T: Trait`.
56#[derive(AdtInto)]
57#[args(<'tcx, S: UnderOwnerState<'tcx> >, from: resolution::ImplExprAtom<'tcx>, state: S as s)]
58#[derive_group(Serializers)]
59#[derive(Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord, JsonSchema)]
60pub enum ImplExprAtom {
61    /// A concrete `impl Trait for Type {}` item.
62    Concrete {
63        #[from(def_id)]
64        id: GlobalIdent,
65        generics: Vec<GenericArg>,
66        /// The impl exprs that prove the clauses on the impl.
67        impl_exprs: Vec<ImplExpr>,
68    },
69    /// A context-bound clause like `where T: Trait`.
70    LocalBound {
71        #[not_in_source]
72        #[value({
73            let Self::LocalBound { predicate, .. } = self else { unreachable!() };
74            predicate.sinto(s).id
75        })]
76        predicate_id: PredicateId,
77        /// The nth (non-self) predicate found for this item. We use predicates from
78        /// `required_predicates` starting from the parentmost item.
79        index: usize,
80        r#trait: Binder<TraitRef>,
81        path: Vec<ImplExprPathChunk>,
82    },
83    /// The implicit `Self: Trait` clause present inside a `trait Trait {}` item.
84    // TODO: should we also get that clause for trait impls?
85    SelfImpl {
86        r#trait: Binder<TraitRef>,
87        path: Vec<ImplExprPathChunk>,
88    },
89    /// `dyn Trait` is a wrapped value with a virtual table for trait
90    /// `Trait`.  In other words, a value `dyn Trait` is a dependent
91    /// triple that gathers a type τ, a value of type τ and an
92    /// instance of type `Trait`.
93    /// `dyn Trait` implements `Trait` using a built-in implementation; this refers to that
94    /// built-in implementation.
95    Dyn,
96    /// A built-in trait whose implementation is computed by the compiler, such as `FnMut`. This
97    /// morally points to an invisible `impl` block; as such it contains the information we may
98    /// need from one.
99    Builtin {
100        r#trait: Binder<TraitRef>,
101        /// The `ImplExpr`s required to satisfy the implied predicates on the trait declaration.
102        /// E.g. since `FnMut: FnOnce`, a built-in `T: FnMut` impl would have an `ImplExpr` for `T:
103        /// FnOnce`.
104        impl_exprs: Vec<ImplExpr>,
105        /// The values of the associated types for this trait.
106        types: Vec<(DefId, Ty)>,
107    },
108    /// An error happened while resolving traits.
109    Error(String),
110}
111
112/// An `ImplExpr` describes the full data of a trait implementation. Because of generics, this may
113/// need to combine several concrete trait implementation items. For example, `((1u8, 2u8),
114/// "hello").clone()` combines the generic implementation of `Clone` for `(A, B)` with the
115/// concrete implementations for `u8` and `&str`, represented as a tree.
116#[derive_group(Serializers)]
117#[derive(Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord, JsonSchema, AdtInto)]
118#[args(<'tcx, S: UnderOwnerState<'tcx> >, from: resolution::ImplExpr<'tcx>, state: S as s)]
119pub struct ImplExpr {
120    /// The trait this is an impl for.
121    pub r#trait: Binder<TraitRef>,
122    /// The kind of implemention of the root of the tree.
123    pub r#impl: ImplExprAtom,
124}
125
126/// Given a clause `clause` in the context of some impl block `impl_did`, susbts correctly `Self`
127/// from `clause` and (1) derive a `Clause` and (2) resolve an `ImplExpr`.
128#[cfg(feature = "rustc")]
129pub fn super_clause_to_clause_and_impl_expr<'tcx, S: UnderOwnerState<'tcx>>(
130    s: &S,
131    impl_did: rustc_span::def_id::DefId,
132    clause: rustc_middle::ty::Clause<'tcx>,
133    span: rustc_span::Span,
134) -> Option<(Clause, ImplExpr, Span)> {
135    let tcx = s.base().tcx;
136    let impl_trait_ref = tcx
137        .impl_trait_ref(impl_did)
138        .map(|binder| rustc_middle::ty::Binder::dummy(binder.instantiate_identity()))?;
139    let original_predicate_id = {
140        // We don't want the id of the substituted clause id, but the
141        // original clause id (with, i.e., `Self`)
142        let s = &with_owner_id(s.base(), (), (), impl_trait_ref.def_id());
143        clause.sinto(s).id
144    };
145    let new_clause = clause.instantiate_supertrait(tcx, impl_trait_ref);
146    let impl_expr = solve_trait(
147        s,
148        new_clause
149            .as_predicate()
150            .as_trait_clause()?
151            .to_poly_trait_ref(),
152    );
153    let mut new_clause_no_binder = new_clause.sinto(s);
154    new_clause_no_binder.id = original_predicate_id;
155    Some((new_clause_no_binder, impl_expr, span.sinto(s)))
156}
157
158/// This is the entrypoint of the solving.
159#[cfg(feature = "rustc")]
160#[tracing::instrument(level = "trace", skip(s))]
161pub fn solve_trait<'tcx, S: BaseState<'tcx> + HasOwnerId>(
162    s: &S,
163    trait_ref: rustc_middle::ty::PolyTraitRef<'tcx>,
164) -> ImplExpr {
165    let warn = |msg: &str| {
166        if !s.base().ty_alias_mode {
167            crate::warning!(s, "{}", msg)
168        }
169    };
170    if let Some(impl_expr) = s.with_cache(|cache| cache.impl_exprs.get(&trait_ref).cloned()) {
171        return impl_expr;
172    }
173    let resolved = s.with_cache(|cache| {
174        cache
175            .predicate_searcher
176            .get_or_insert_with(|| PredicateSearcher::new_for_owner(s.base().tcx, s.owner_id()))
177            .resolve(&trait_ref, &warn)
178    });
179    let impl_expr = match resolved {
180        Ok(x) => x.sinto(s),
181        Err(e) => crate::fatal!(s, "{}", e),
182    };
183    s.with_cache(|cache| cache.impl_exprs.insert(trait_ref, impl_expr.clone()));
184    impl_expr
185}
186
187/// Solve the trait obligations for a specific item use (for example, a method call, an ADT, etc.)
188/// in the current context. Just like generic args include generics of parent items, this includes
189/// impl exprs for parent items.
190#[cfg(feature = "rustc")]
191#[tracing::instrument(level = "trace", skip(s), ret)]
192pub fn solve_item_required_traits<'tcx, S: UnderOwnerState<'tcx>>(
193    s: &S,
194    def_id: RDefId,
195    generics: ty::GenericArgsRef<'tcx>,
196) -> Vec<ImplExpr> {
197    fn accumulate<'tcx, S: UnderOwnerState<'tcx>>(
198        s: &S,
199        def_id: RDefId,
200        generics: ty::GenericArgsRef<'tcx>,
201        impl_exprs: &mut Vec<ImplExpr>,
202    ) {
203        let tcx = s.base().tcx;
204        use rustc_hir::def::DefKind::*;
205        match tcx.def_kind(def_id) {
206            AssocTy | AssocFn | AssocConst | Closure | Ctor(..) | Variant => {
207                let parent = tcx.parent(def_id);
208                accumulate(s, parent, generics, impl_exprs);
209            }
210            _ => {}
211        }
212        let predicates = required_predicates(tcx, def_id);
213        impl_exprs.extend(solve_item_traits_inner(s, generics, predicates));
214    }
215    let mut impl_exprs = vec![];
216    accumulate(s, def_id, generics, &mut impl_exprs);
217    impl_exprs
218}
219
220/// Solve the trait obligations for implementing a trait (or for trait associated type bounds) in
221/// the current context.
222#[cfg(feature = "rustc")]
223#[tracing::instrument(level = "trace", skip(s), ret)]
224pub fn solve_item_implied_traits<'tcx, S: UnderOwnerState<'tcx>>(
225    s: &S,
226    def_id: RDefId,
227    generics: ty::GenericArgsRef<'tcx>,
228) -> Vec<ImplExpr> {
229    let predicates = implied_predicates(s.base().tcx, def_id);
230    solve_item_traits_inner(s, generics, predicates)
231}
232
233/// Apply the given generics to the provided clauses and resolve the trait references in the
234/// current context.
235#[cfg(feature = "rustc")]
236fn solve_item_traits_inner<'tcx, S: UnderOwnerState<'tcx>>(
237    s: &S,
238    generics: ty::GenericArgsRef<'tcx>,
239    predicates: ty::GenericPredicates<'tcx>,
240) -> Vec<ImplExpr> {
241    let tcx = s.base().tcx;
242    let typing_env = s.typing_env();
243    predicates
244        .predicates
245        .iter()
246        .map(|(clause, _span)| *clause)
247        .filter_map(|clause| clause.as_trait_clause())
248        .map(|clause| clause.to_poly_trait_ref())
249        // Substitute the item generics
250        .map(|trait_ref| ty::EarlyBinder::bind(trait_ref).instantiate(tcx, generics))
251        // We unfortunately don't have a way to normalize without erasing regions.
252        .map(|trait_ref| {
253            tcx.try_normalize_erasing_regions(typing_env, trait_ref)
254                .unwrap_or(trait_ref)
255        })
256        // Resolve
257        .map(|trait_ref| solve_trait(s, trait_ref))
258        .collect()
259}
260
261/// Retrieve the `Self: Trait` clause for a trait associated item.
262#[cfg(feature = "rustc")]
263pub fn self_clause_for_item<'tcx, S: UnderOwnerState<'tcx>>(
264    s: &S,
265    def_id: RDefId,
266    generics: rustc_middle::ty::GenericArgsRef<'tcx>,
267) -> Option<ImplExpr> {
268    use rustc_middle::ty::EarlyBinder;
269    let tcx = s.base().tcx;
270
271    let tr_def_id = tcx.trait_of_item(def_id)?;
272    // The "self" predicate in the context of the trait.
273    let self_pred = self_predicate(tcx, tr_def_id);
274    // Substitute to be in the context of the current item.
275    let generics = generics.truncate_to(tcx, tcx.generics_of(tr_def_id));
276    let self_pred = EarlyBinder::bind(self_pred).instantiate(tcx, generics);
277
278    // Resolve
279    Some(solve_trait(s, self_pred))
280}
hax_frontend_exporter/traits.rs

hax_frontend_exporter/
traits.rs
