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

hax_frontend_exporter/
traits.rs
