charon_driver/translate/
translate_trait_objects.rs

1use charon_lib::ast::ullbc_ast_utils::BodyBuilder;
2use hax::TraitPredicate;
3use itertools::Itertools;
4use std::mem;
5
6use super::{
7    translate_crate::TransItemSourceKind, translate_ctx::*, translate_generics::BindingLevel,
8};
9use charon_lib::formatter::IntoFormatter;
10use charon_lib::ids::{IndexMap, IndexVec};
11use charon_lib::pretty::FmtWithCtx;
12use charon_lib::ullbc_ast::*;
13
14fn usize_ty() -> Ty {
15    Ty::new(TyKind::Literal(LiteralTy::UInt(UIntTy::Usize)))
16}
17
18/// Takes a `T` valid in the context of a trait ref and transforms it into a `T` valid in the
19/// context of its vtable definition, i.e. no longer mentions the `Self` type or `Self` clause. If
20/// `new_self` is `Some`, we replace any mention of the `Self` type with it; otherwise we panic if
21/// `Self` is mentioned.
22/// If `for_method` is true, we're handling a value coming from a `AssocFn`, which takes the `Self`
23/// clause as its first clause parameter. Otherwise we're in trait scope, where the `Self` clause
24/// is represented with `TraitRefKind::SelfId`.
25fn dynify<T: TyVisitable>(mut x: T, new_self: Option<Ty>, for_method: bool) -> T {
26    struct ReplaceSelfVisitor {
27        new_self: Option<Ty>,
28        for_method: bool,
29    }
30    impl VarsVisitor for ReplaceSelfVisitor {
31        fn visit_type_var(&mut self, v: TypeDbVar) -> Option<Ty> {
32            if let DeBruijnVar::Bound(DeBruijnId::ZERO, type_id) = v {
33                // Replace type 0 and decrement the others.
34                Some(if let Some(new_id) = type_id.index().checked_sub(1) {
35                    TyKind::TypeVar(DeBruijnVar::Bound(DeBruijnId::ZERO, TypeVarId::new(new_id)))
36                        .into_ty()
37                } else {
38                    self.new_self.clone().expect(
39                        "Found unexpected `Self`
40                        type when constructing vtable",
41                    )
42                })
43            } else {
44                None
45            }
46        }
47
48        fn visit_clause_var(&mut self, v: ClauseDbVar) -> Option<TraitRefKind> {
49            if let DeBruijnVar::Bound(DeBruijnId::ZERO, clause_id) = v {
50                if self.for_method && clause_id == TraitClauseId::ZERO {
51                    // That's the `Self` clause.
52                    Some(TraitRefKind::Dyn)
53                } else {
54                    panic!("Found unexpected clause var when constructing vtable: {v}")
55                }
56            } else {
57                None
58            }
59        }
60
61        fn visit_self_clause(&mut self) -> Option<TraitRefKind> {
62            Some(TraitRefKind::Dyn)
63        }
64    }
65    x.visit_vars(&mut ReplaceSelfVisitor {
66        new_self,
67        for_method,
68    });
69    x
70}
71
72//// Translate the `dyn Trait` type.
73impl ItemTransCtx<'_, '_> {
74    pub fn check_at_most_one_pred_has_methods(
75        &mut self,
76        span: Span,
77        preds: &hax::GenericPredicates,
78    ) -> Result<(), Error> {
79        // Only the first clause is allowed to have methods.
80        for (clause, _) in preds.predicates.iter().skip(1) {
81            if let hax::ClauseKind::Trait(trait_predicate) = clause.kind.hax_skip_binder_ref() {
82                let trait_def_id = &trait_predicate.trait_ref.def_id;
83                let trait_def = self.poly_hax_def(trait_def_id)?;
84                let has_methods = match trait_def.kind() {
85                    hax::FullDefKind::Trait { items, .. } => items
86                        .iter()
87                        .any(|assoc| matches!(assoc.kind, hax::AssocKind::Fn { .. })),
88                    hax::FullDefKind::TraitAlias { .. } => false,
89                    _ => unreachable!(),
90                };
91                if has_methods {
92                    raise_error!(
93                        self,
94                        span,
95                        "`dyn Trait` with multiple method-bearing predicates is not supported"
96                    );
97                }
98            }
99        }
100        Ok(())
101    }
102
103    pub fn translate_dyn_binder<T, U>(
104        &mut self,
105        span: Span,
106        binder: &hax::DynBinder<T>,
107        f: impl FnOnce(&mut Self, Ty, &T) -> Result<U, Error>,
108    ) -> Result<Binder<U>, Error> {
109        // This is a robustness check: the current version of Rustc
110        // accepts at most one method-bearing predicate in a trait object.
111        // But things may change in the future.
112        self.check_at_most_one_pred_has_methods(span, &binder.predicates)?;
113
114        // Add a binder that contains the existentially quantified type.
115        self.binding_levels.push(BindingLevel::new(true));
116
117        // Add the existentially quantified type.
118        let ty_id = self.innermost_binder_mut().push_type_var(
119            binder.existential_ty.index,
120            binder.existential_ty.name.clone(),
121        );
122        let ty = TyKind::TypeVar(DeBruijnVar::new_at_zero(ty_id)).into_ty();
123        let val = f(self, ty, &binder.val)?;
124
125        self.register_predicates(&binder.predicates, PredicateOrigin::Dyn)?;
126
127        let params = self.binding_levels.pop().unwrap().params;
128        Ok(Binder {
129            params: params,
130            skip_binder: val,
131            kind: BinderKind::Dyn,
132        })
133    }
134}
135
136/// Vtable field info used for translation (same deal as `charon_lib::VTableField` but with
137/// different data).
138pub enum TrVTableField {
139    Size,
140    Align,
141    Drop,
142    Method(TraitItemName, hax::Binder<hax::TyFnSig>),
143    SuperTrait(TraitClauseId, hax::Clause),
144}
145
146pub struct VTableData {
147    pub fields: IndexVec<FieldId, TrVTableField>,
148    pub supertrait_map: IndexMap<TraitClauseId, Option<FieldId>>,
149}
150
151//// Generate the vtable struct.
152impl ItemTransCtx<'_, '_> {
153    /// Query whether a trait is dyn compatible.
154    /// TODO(dyn): for now we return `false` if the trait has any associated types, as we don't
155    /// handle associated types in vtables.
156    pub fn trait_is_dyn_compatible(&mut self, def_id: &hax::DefId) -> Result<bool, Error> {
157        let def = self.poly_hax_def(def_id)?;
158        Ok(match def.kind() {
159            hax::FullDefKind::Trait { dyn_self, .. }
160            | hax::FullDefKind::TraitAlias { dyn_self, .. } => dyn_self.is_some(),
161            _ => false,
162        })
163    }
164
165    /// Check whether this trait ref is of the form `Self: Trait<...>`.
166    fn pred_is_for_self(&self, tref: &hax::TraitRef) -> bool {
167        let first_ty = tref
168            .generic_args
169            .iter()
170            .filter_map(|arg| match arg {
171                hax::GenericArg::Type(ty) => Some(ty),
172                _ => None,
173            })
174            .next();
175        match first_ty {
176            None => false,
177            Some(first_ty) => match first_ty.kind() {
178                hax::TyKind::Param(param_ty) if param_ty.index == 0 => {
179                    assert_eq!(param_ty.name, "Self");
180                    true
181                }
182                _ => false,
183            },
184        }
185    }
186
187    pub fn translate_vtable_struct_ref(
188        &mut self,
189        span: Span,
190        tref: &hax::TraitRef,
191    ) -> Result<Option<TypeDeclRef>, Error> {
192        self.translate_vtable_struct_ref_maybe_enqueue(true, span, tref)
193    }
194
195    pub fn translate_vtable_struct_ref_no_enqueue(
196        &mut self,
197        span: Span,
198        tref: &hax::TraitRef,
199    ) -> Result<Option<TypeDeclRef>, Error> {
200        self.translate_vtable_struct_ref_maybe_enqueue(false, span, tref)
201    }
202
203    /// Given a trait ref, return a reference to its vtable struct, if it is dyn compatible.
204    pub fn translate_vtable_struct_ref_maybe_enqueue(
205        &mut self,
206        enqueue: bool,
207        span: Span,
208        tref: &hax::TraitRef,
209    ) -> Result<Option<TypeDeclRef>, Error> {
210        if !self.trait_is_dyn_compatible(&tref.def_id)? {
211            return Ok(None);
212        }
213        // Don't enqueue the vtable for translation by default. It will be enqueued if used in a
214        // `dyn Trait`.
215        let mut vtable_ref: TypeDeclRef =
216            self.translate_item_maybe_enqueue(span, enqueue, tref, TransItemSourceKind::VTable)?;
217        // Remove the `Self` type variable from the generic parameters.
218        vtable_ref
219            .generics
220            .types
221            .remove_and_shift_ids(TypeVarId::ZERO);
222
223        // The vtable type also takes associated types as parameters.
224        let assoc_tys: Vec<_> = tref
225            .trait_associated_types(self.hax_state_with_id())
226            .iter()
227            .map(|ty| self.translate_ty(span, ty))
228            .try_collect()?;
229        vtable_ref.generics.types.extend(assoc_tys);
230
231        Ok(Some(vtable_ref))
232    }
233
234    fn prepare_vtable_fields(
235        &mut self,
236        trait_def: &hax::FullDef,
237        implied_predicates: &hax::GenericPredicates,
238    ) -> Result<VTableData, Error> {
239        let mut supertrait_map: IndexMap<TraitClauseId, _> =
240            (0..implied_predicates.predicates.len())
241                .map(|_| None)
242                .collect();
243        let mut fields = IndexVec::new();
244
245        // Basic fields.
246        fields.push(TrVTableField::Size);
247        fields.push(TrVTableField::Align);
248        fields.push(TrVTableField::Drop);
249
250        // Method fields.
251        if let hax::FullDefKind::Trait { items, .. } = trait_def.kind() {
252            for item in items {
253                let item_def_id = &item.def_id;
254                // This is ok because dyn-compatible methods don't have generics.
255                let item_def =
256                    self.hax_def(&trait_def.this().with_def_id(self.hax_state(), item_def_id))?;
257                if let hax::FullDefKind::AssocFn {
258                    sig,
259                    vtable_sig: Some(_),
260                    ..
261                } = item_def.kind()
262                {
263                    let name = self.translate_trait_item_name(&item_def_id)?;
264                    fields.push(TrVTableField::Method(name, sig.clone()));
265                }
266            }
267        }
268
269        // Supertrait fields.
270        for (i, (clause, _span)) in implied_predicates.predicates.iter().enumerate() {
271            // If a clause looks like `Self: OtherTrait<...>`, we consider it a supertrait.
272            if let hax::ClauseKind::Trait(pred) = clause.kind.hax_skip_binder_ref()
273                && self.pred_is_for_self(&pred.trait_ref)
274            {
275                let trait_clause_id = TraitClauseId::from_raw(i);
276                supertrait_map[trait_clause_id] = Some(fields.next_idx());
277                fields.push(TrVTableField::SuperTrait(trait_clause_id, clause.clone()));
278            }
279        }
280
281        Ok(VTableData {
282            fields,
283            supertrait_map,
284        })
285    }
286
287    fn gen_vtable_struct_fields(
288        &mut self,
289        span: Span,
290        vtable_data: &VTableData,
291    ) -> Result<IndexVec<FieldId, Field>, Error> {
292        let mut fields = IndexVec::new();
293        let mut supertrait_counter = (0..).into_iter();
294        for field in &vtable_data.fields {
295            let (name, ty) = match field {
296                TrVTableField::Size => ("size".into(), usize_ty()),
297                TrVTableField::Align => ("align".into(), usize_ty()),
298                TrVTableField::Drop => {
299                    let self_ty =
300                        TyKind::TypeVar(DeBruijnVar::new_at_zero(TypeVarId::ZERO)).into_ty();
301                    let self_ptr = TyKind::RawPtr(self_ty, RefKind::Mut).into_ty();
302                    let drop_ty = Ty::new(TyKind::FnPtr(RegionBinder::empty(FunSig {
303                        is_unsafe: true,
304                        inputs: [self_ptr].into(),
305                        output: Ty::mk_unit(),
306                    })));
307                    ("drop".into(), drop_ty)
308                }
309                TrVTableField::Method(item_name, sig) => {
310                    // It's ok to translate the method signature in the context of the trait because
311                    // `vtable_sig: Some(_)` ensures the method has no generics of its own.
312                    let sig = self.translate_poly_fun_sig(span, &sig)?;
313                    let ty = TyKind::FnPtr(sig).into_ty();
314                    let field_name = format!("method_{}", item_name.0);
315                    (field_name, ty)
316                }
317                TrVTableField::SuperTrait(_, clause) => {
318                    let vtbl_struct = self
319                        .translate_region_binder(span, &clause.kind, |ctx, kind| {
320                            let hax::ClauseKind::Trait(pred) = kind else {
321                                unreachable!()
322                            };
323                            ctx.translate_vtable_struct_ref(span, &pred.trait_ref)
324                        })?
325                        .erase()
326                        .expect("parent trait should be dyn compatible");
327                    let ty = Ty::new(TyKind::Ref(
328                        Region::Static,
329                        Ty::new(TyKind::Adt(vtbl_struct)),
330                        RefKind::Shared,
331                    ));
332                    let name = format!("super_trait_{}", supertrait_counter.next().unwrap());
333                    (name, ty)
334                }
335            };
336            fields.push(Field {
337                span,
338                attr_info: AttrInfo::dummy_public(),
339                name: Some(name),
340                ty,
341            });
342        }
343        Ok(fields)
344    }
345
346    /// This is a temporary check until we support `dyn Trait` with `--monomorphize`.
347    pub(crate) fn check_no_monomorphize(&self, span: Span) -> Result<(), Error> {
348        if self.monomorphize() {
349            raise_error!(
350                self,
351                span,
352                "`dyn Trait` is not yet supported with `--monomorphize`"
353            )
354        }
355        Ok(())
356    }
357
358    /// Construct the type of the vtable for this trait.
359    ///
360    /// It's a struct that has for generics the generics of the trait + one parameter for each
361    /// associated type of the trait and its parents.
362    ///
363    /// struct TraitVTable<TraitArgs.., AssocTys..> {
364    ///   size: usize,
365    ///   align: usize,
366    ///   drop: fn(*mut dyn Trait<...>),
367    ///   method_name: fn(&dyn Trait<...>, Args..) -> Output,
368    ///   ... other methods
369    ///   super_trait_0: &'static SuperTrait0VTable
370    ///   ... other supertraits
371    /// }
372    pub(crate) fn translate_vtable_struct(
373        mut self,
374        type_id: TypeDeclId,
375        item_meta: ItemMeta,
376        trait_def: &hax::FullDef,
377    ) -> Result<TypeDecl, Error> {
378        let span = item_meta.span;
379        if !self.trait_is_dyn_compatible(trait_def.def_id())? {
380            raise_error!(
381                self,
382                span,
383                "Trying to compute the vtable type \
384                for a non-dyn-compatible trait"
385            );
386        }
387        self.check_no_monomorphize(span)?;
388
389        let (hax::FullDefKind::Trait {
390            dyn_self,
391            implied_predicates,
392            ..
393        }
394        | hax::FullDefKind::TraitAlias {
395            dyn_self,
396            implied_predicates,
397            ..
398        }) = trait_def.kind()
399        else {
400            panic!()
401        };
402        let Some(dyn_self) = dyn_self else {
403            panic!("Trying to generate a vtable for a non-dyn-compatible trait")
404        };
405
406        // The `dyn Trait<Args..>` type for this trait.
407        let mut dyn_self = {
408            let dyn_self = self.translate_ty(span, dyn_self)?;
409            let TyKind::DynTrait(mut dyn_pred) = dyn_self.kind().clone() else {
410                panic!("incorrect `dyn_self`")
411            };
412
413            // Add one generic parameter for each associated type of this trait and its parents. We
414            // then use that in `dyn_self`
415            for (i, ty_constraint) in dyn_pred
416                .binder
417                .params
418                .trait_type_constraints
419                .iter_mut()
420                .enumerate()
421            {
422                let name = format!("Ty{i}");
423                let new_ty = self
424                    .the_only_binder_mut()
425                    .params
426                    .types
427                    .push_with(|index| TypeParam { index, name });
428                // Moving that type under two levels of binders: the `DynPredicate` binder and the
429                // type constraint binder.
430                let new_ty =
431                    TyKind::TypeVar(DeBruijnVar::bound(DeBruijnId::new(2), new_ty)).into_ty();
432                ty_constraint.skip_binder.ty = new_ty;
433            }
434            TyKind::DynTrait(dyn_pred).into_ty()
435        };
436
437        let mut field_map = IndexVec::new();
438        let mut supertrait_map: IndexMap<TraitClauseId, _> =
439            (0..implied_predicates.predicates.len())
440                .map(|_| None)
441                .collect();
442        let (mut kind, layout) = if item_meta.opacity.with_private_contents().is_opaque() {
443            (TypeDeclKind::Opaque, None)
444        } else {
445            // First construct fields that use the real method signatures (which may use the `Self`
446            // type). We fixup the types and generics below.
447            let vtable_data = self.prepare_vtable_fields(trait_def, implied_predicates)?;
448            let fields = self.gen_vtable_struct_fields(span, &vtable_data)?;
449            let kind = TypeDeclKind::Struct(fields);
450            let layout = self.generate_naive_layout(span, &kind)?;
451            supertrait_map = vtable_data.supertrait_map;
452            field_map = vtable_data.fields.map_ref(|tr_field| match *tr_field {
453                TrVTableField::Size => VTableField::Size,
454                TrVTableField::Align => VTableField::Align,
455                TrVTableField::Drop => VTableField::Drop,
456                TrVTableField::Method(name, ..) => VTableField::Method(name),
457                TrVTableField::SuperTrait(clause_id, ..) => VTableField::SuperTrait(clause_id),
458            });
459            (kind, Some(layout))
460        };
461
462        // Replace any use of `Self` with `dyn Trait<...>`, and remove the `Self` type variable
463        // from the generic parameters.
464        let mut generics = self.into_generics();
465        {
466            dyn_self = dynify(dyn_self, None, false);
467            generics = dynify(generics, Some(dyn_self.clone()), false);
468            kind = dynify(kind, Some(dyn_self.clone()), true);
469            generics.types.remove_and_shift_ids(TypeVarId::ZERO);
470            generics.types.iter_mut().for_each(|ty| {
471                ty.index -= 1;
472            });
473        }
474
475        let dyn_predicate = dyn_self
476            .kind()
477            .as_dyn_trait()
478            .expect("incorrect `dyn_self`");
479        Ok(TypeDecl {
480            def_id: type_id,
481            item_meta: item_meta,
482            generics: generics,
483            src: ItemSource::VTableTy {
484                dyn_predicate: dyn_predicate.clone(),
485                field_map,
486                supertrait_map,
487            },
488            kind,
489            layout,
490            // A vtable struct is always sized
491            ptr_metadata: PtrMetadata::None,
492            repr: None,
493        })
494    }
495}
496
497//// Generate a vtable value.
498impl ItemTransCtx<'_, '_> {
499    pub fn translate_vtable_instance_ref(
500        &mut self,
501        span: Span,
502        trait_ref: &hax::TraitRef,
503        impl_ref: &hax::ItemRef,
504    ) -> Result<Option<GlobalDeclRef>, Error> {
505        self.translate_vtable_instance_ref_maybe_enqueue(true, span, trait_ref, impl_ref)
506    }
507
508    pub fn translate_vtable_instance_ref_no_enqueue(
509        &mut self,
510        span: Span,
511        trait_ref: &hax::TraitRef,
512        impl_ref: &hax::ItemRef,
513    ) -> Result<Option<GlobalDeclRef>, Error> {
514        self.translate_vtable_instance_ref_maybe_enqueue(false, span, trait_ref, impl_ref)
515    }
516
517    pub fn translate_vtable_instance_ref_maybe_enqueue(
518        &mut self,
519        enqueue: bool,
520        span: Span,
521        trait_ref: &hax::TraitRef,
522        impl_ref: &hax::ItemRef,
523    ) -> Result<Option<GlobalDeclRef>, Error> {
524        if !self.trait_is_dyn_compatible(&trait_ref.def_id)? {
525            return Ok(None);
526        }
527        // Don't enqueue the vtable for translation by default. It will be enqueued if used in a
528        // `dyn Trait` coercion.
529        // TODO(dyn): To do this properly we'd need to know for each clause whether it ultimately
530        // ends up used in a vtable cast.
531        let vtable_ref: GlobalDeclRef = self.translate_item_maybe_enqueue(
532            span,
533            enqueue,
534            impl_ref,
535            TransItemSourceKind::VTableInstance(TraitImplSource::Normal),
536        )?;
537        Ok(Some(vtable_ref))
538    }
539
540    /// Local helper function to get the vtable struct reference and trait declaration reference
541    fn get_vtable_instance_info<'a>(
542        &mut self,
543        span: Span,
544        impl_def: &'a hax::FullDef,
545        impl_kind: &TraitImplSource,
546    ) -> Result<(TraitImplRef, TypeDeclRef), Error> {
547        let implemented_trait = match impl_def.kind() {
548            hax::FullDefKind::TraitImpl { trait_pred, .. } => &trait_pred.trait_ref,
549            _ => unreachable!(),
550        };
551        let vtable_struct_ref = self
552            .translate_vtable_struct_ref(span, implemented_trait)?
553            .expect("trait should be dyn-compatible");
554        let impl_ref = self.translate_item(
555            span,
556            impl_def.this(),
557            TransItemSourceKind::TraitImpl(*impl_kind),
558        )?;
559        Ok((impl_ref, vtable_struct_ref))
560    }
561
562    /// E.g.,
563    /// ```
564    /// global {impl Trait for Foo}::vtable<Args..>: Trait::{vtable}<TraitArgs.., AssocTys..> {
565    ///     size: size_of(Foo),
566    ///     align: align_of(Foo),
567    ///     drop: <Foo as Destruct>::drop_in_place,
568    ///     method_0: <Foo as Trait>::method_0::{shim},
569    ///     method_1: <Foo as Trait>::method_1::{shim},
570    ///     ...
571    ///     super_trait_0: SuperImpl0<..>::{vtable_instance}::<..>,
572    ///     super_trait_1: SuperImpl1<..>::{vtable_instance}::<..>,
573    ///     ...
574    /// }
575    /// ```
576    pub(crate) fn translate_vtable_instance(
577        mut self,
578        global_id: GlobalDeclId,
579        item_meta: ItemMeta,
580        impl_def: &hax::FullDef,
581        impl_kind: &TraitImplSource,
582    ) -> Result<GlobalDecl, Error> {
583        let span = item_meta.span;
584        self.check_no_monomorphize(span)?;
585
586        let (impl_ref, vtable_struct_ref) =
587            self.get_vtable_instance_info(span, impl_def, impl_kind)?;
588        // Initializer function for this global.
589        let init = self.register_item(
590            span,
591            impl_def.this(),
592            TransItemSourceKind::VTableInstanceInitializer(*impl_kind),
593        );
594
595        Ok(GlobalDecl {
596            def_id: global_id,
597            item_meta,
598            generics: self.into_generics(),
599            src: ItemSource::VTableInstance { impl_ref },
600            // it should be static to have its own address
601            global_kind: GlobalKind::Static,
602            ty: Ty::new(TyKind::Adt(vtable_struct_ref)),
603            init,
604        })
605    }
606
607    fn add_method_to_vtable_value(
608        &mut self,
609        span: Span,
610        impl_def: &hax::FullDef,
611        item: &hax::ImplAssocItem,
612        mut mk_field: impl FnMut(ConstantExprKind),
613    ) -> Result<(), Error> {
614        // Exit if the item isn't a vtable safe method.
615        match self.poly_hax_def(&item.decl_def_id)?.kind() {
616            hax::FullDefKind::AssocFn {
617                vtable_sig: Some(_),
618                ..
619            } => {}
620            _ => return Ok(()),
621        }
622
623        let const_kind = match &item.value {
624            hax::ImplAssocItemValue::Provided {
625                def_id: item_def_id,
626                ..
627            } => {
628                // The method is vtable safe so it has no generics, hence we can reuse the impl
629                // generics -- the lifetime binder will be added as `Erased` in `translate_fn_ptr`.
630                let item_ref = impl_def.this().with_def_id(self.hax_state(), item_def_id);
631                let shim_ref = self
632                    .translate_fn_ptr(span, &item_ref, TransItemSourceKind::VTableMethod)?
633                    .erase();
634                ConstantExprKind::FnDef(shim_ref)
635            }
636            hax::ImplAssocItemValue::DefaultedFn { .. } => ConstantExprKind::Opaque(
637                "shim for default methods \
638                    aren't yet supported"
639                    .to_string(),
640            ),
641            _ => return Ok(()),
642        };
643
644        mk_field(const_kind);
645
646        Ok(())
647    }
648
649    fn add_supertraits_to_vtable_value(
650        &mut self,
651        span: Span,
652        trait_def: &hax::FullDef,
653        impl_def: &hax::FullDef,
654        mut mk_field: impl FnMut(ConstantExprKind),
655    ) -> Result<(), Error> {
656        let hax::FullDefKind::TraitImpl {
657            implied_impl_exprs, ..
658        } = impl_def.kind()
659        else {
660            unreachable!()
661        };
662        let hax::FullDefKind::Trait {
663            implied_predicates, ..
664        } = trait_def.kind()
665        else {
666            unreachable!()
667        };
668        for ((clause, _), impl_expr) in implied_predicates.predicates.iter().zip(implied_impl_exprs)
669        {
670            let hax::ClauseKind::Trait(pred) = clause.kind.hax_skip_binder_ref() else {
671                continue;
672            };
673            // If a clause looks like `Self: OtherTrait<...>`, we consider it a supertrait.
674            if !self.pred_is_for_self(&pred.trait_ref) {
675                continue;
676            }
677
678            let vtable_def_ref = self
679                .translate_region_binder(span, &impl_expr.r#trait, |ctx, tref| {
680                    ctx.translate_vtable_struct_ref(span, tref)
681                })?
682                .erase()
683                .expect("parent trait should be dyn compatible");
684            let fn_ptr_ty = TyKind::Adt(vtable_def_ref).into_ty();
685            let kind = match &impl_expr.r#impl {
686                hax::ImplExprAtom::Concrete(impl_item) => {
687                    let vtable_instance_ref = self
688                        .translate_region_binder(span, &impl_expr.r#trait, |ctx, tref| {
689                            ctx.translate_vtable_instance_ref(span, tref, impl_item)
690                        })?
691                        .erase()
692                        .expect("parent trait should be dyn compatible");
693                    let global = Box::new(ConstantExpr {
694                        kind: ConstantExprKind::Global(vtable_instance_ref),
695                        ty: fn_ptr_ty,
696                    });
697                    ConstantExprKind::Ref(global)
698                }
699                // TODO(dyn): builtin impls
700                _ => ConstantExprKind::Opaque("missing supertrait vtable".into()),
701            };
702            mk_field(kind);
703        }
704        Ok(())
705    }
706
707    /// Generate the body of the vtable instance function.
708    /// This is for `impl Trait for T` implementation, it does NOT handle builtin impls.
709    /// ```ignore
710    /// let ret@0 : VTable;
711    /// ret@0 = VTable { ... };
712    /// return;
713    /// ```
714    fn gen_vtable_instance_init_body(
715        &mut self,
716        span: Span,
717        impl_def: &hax::FullDef,
718        vtable_struct_ref: TypeDeclRef,
719    ) -> Result<Body, Error> {
720        let hax::FullDefKind::TraitImpl {
721            trait_pred, items, ..
722        } = impl_def.kind()
723        else {
724            unreachable!()
725        };
726        let trait_def = self.hax_def(&trait_pred.trait_ref)?;
727        let implemented_trait = self.translate_trait_decl_ref(span, &trait_pred.trait_ref)?;
728        // The type this impl is for.
729        let self_ty = &implemented_trait.generics.types[0];
730
731        let mut builder = BodyBuilder::new(span, 0);
732        let ret_ty = Ty::new(TyKind::Adt(vtable_struct_ref.clone()));
733        let ret_place = builder.new_var(Some("ret".into()), ret_ty.clone());
734
735        // Retreive the expected field types from the struct definition. This avoids complicated
736        // substitutions.
737        let field_tys = {
738            let vtable_decl_id = vtable_struct_ref.id.as_adt().unwrap().clone();
739            let ItemRef::Type(vtable_def) = self.t_ctx.get_or_translate(vtable_decl_id.into())?
740            else {
741                unreachable!()
742            };
743            let TypeDeclKind::Struct(fields) = &vtable_def.kind else {
744                unreachable!()
745            };
746            fields
747                .iter()
748                .map(|f| &f.ty)
749                .cloned()
750                .map(|ty| ty.substitute(&vtable_struct_ref.generics))
751                .collect_vec()
752        };
753
754        let mut aggregate_fields = vec![];
755        // For each vtable field, assign the desired value to a new local.
756        let mut field_ty_iter = field_tys.into_iter();
757
758        let size_ty = field_ty_iter.next().unwrap();
759        let size_local = builder.new_var(Some("size".to_string()), size_ty);
760        builder.push_statement(StatementKind::Assign(
761            size_local.clone(),
762            Rvalue::NullaryOp(NullOp::SizeOf, self_ty.clone()),
763        ));
764        aggregate_fields.push(Operand::Move(size_local));
765
766        let align_ty = field_ty_iter.next().unwrap();
767        let align_local = builder.new_var(Some("align".to_string()), align_ty);
768        builder.push_statement(StatementKind::Assign(
769            align_local.clone(),
770            Rvalue::NullaryOp(NullOp::AlignOf, self_ty.clone()),
771        ));
772        aggregate_fields.push(Operand::Move(align_local));
773
774        // Helper to fill in the remaining fields with constant values.
775        let mut mk_field = |kind| {
776            let ty = field_ty_iter.next().unwrap();
777            aggregate_fields.push(Operand::Const(Box::new(ConstantExpr { kind, ty })));
778        };
779
780        let drop_shim =
781            self.translate_item(span, impl_def.this(), TransItemSourceKind::VTableDropShim)?;
782
783        mk_field(ConstantExprKind::FnDef(drop_shim));
784
785        for item in items {
786            self.add_method_to_vtable_value(span, impl_def, item, &mut mk_field)?;
787        }
788
789        self.add_supertraits_to_vtable_value(span, &trait_def, impl_def, &mut mk_field)?;
790
791        if field_ty_iter.next().is_some() {
792            raise_error!(
793                self,
794                span,
795                "Missed some fields in vtable value construction"
796            )
797        }
798
799        // Construct the final struct.
800        builder.push_statement(StatementKind::Assign(
801            ret_place,
802            Rvalue::Aggregate(
803                AggregateKind::Adt(vtable_struct_ref.clone(), None, None),
804                aggregate_fields,
805            ),
806        ));
807
808        Ok(Body::Unstructured(builder.build()))
809    }
810
811    pub(crate) fn translate_vtable_instance_init(
812        mut self,
813        init_func_id: FunDeclId,
814        item_meta: ItemMeta,
815        impl_def: &hax::FullDef,
816        impl_kind: &TraitImplSource,
817    ) -> Result<FunDecl, Error> {
818        let span = item_meta.span;
819        self.check_no_monomorphize(span)?;
820
821        let (impl_ref, vtable_struct_ref) =
822            self.get_vtable_instance_info(span, impl_def, impl_kind)?;
823        let init_for = self.register_item(
824            span,
825            impl_def.this(),
826            TransItemSourceKind::VTableInstance(*impl_kind),
827        );
828
829        // Signature: `() -> VTable`.
830        let sig = FunSig {
831            is_unsafe: false,
832            inputs: vec![],
833            output: Ty::new(TyKind::Adt(vtable_struct_ref.clone())),
834        };
835
836        let body = match impl_kind {
837            _ if item_meta.opacity.with_private_contents().is_opaque() => Body::Opaque,
838            TraitImplSource::Normal => {
839                self.gen_vtable_instance_init_body(span, impl_def, vtable_struct_ref)?
840            }
841            _ => {
842                raise_error!(
843                    self,
844                    span,
845                    "Don't know how to generate a vtable for a virtual impl {impl_kind:?}"
846                );
847            }
848        };
849
850        Ok(FunDecl {
851            def_id: init_func_id,
852            item_meta: item_meta,
853            generics: self.into_generics(),
854            signature: sig,
855            src: ItemSource::VTableInstance { impl_ref },
856            is_global_initializer: Some(init_for),
857            body,
858        })
859    }
860
861    /// The target vtable shim body looks like:
862    /// ```ignore
863    /// local ret@0 : ReturnTy;
864    /// // the shim receiver of this shim function
865    /// local shim_self@1 : ShimReceiverTy;
866    /// // the arguments of the impl function
867    /// local arg1@2 : Arg1Ty;
868    /// ...
869    /// local argN@N : ArgNTy;
870    /// // the target receiver of the impl function
871    /// local target_self@(N+1) : TargetReceiverTy;
872    /// // perform some conversion to cast / re-box the shim receiver to the target receiver
873    /// ...
874    /// target_self@(N+1) := concretize_cast<ShimReceiverTy, TargetReceiverTy>(shim_self@1);
875    /// // call the impl function and assign the result to ret@0
876    /// ret@0 := impl_func(target_self@(N+1), arg1@2, ..., argN@N);
877    /// ```
878    fn translate_vtable_shim_body(
879        &mut self,
880        span: Span,
881        target_receiver: &Ty,
882        shim_signature: &FunSig,
883        impl_func_def: &hax::FullDef,
884    ) -> Result<Body, Error> {
885        let mut builder = BodyBuilder::new(span, shim_signature.inputs.len());
886
887        let ret_place = builder.new_var(None, shim_signature.output.clone());
888        let mut method_args = shim_signature
889            .inputs
890            .iter()
891            .map(|ty| builder.new_var(None, ty.clone()))
892            .collect_vec();
893        let target_self = builder.new_var(None, target_receiver.clone());
894
895        // Replace the `dyn Trait` receiver with the concrete one.
896        let shim_self = mem::replace(&mut method_args[0], target_self.clone());
897
898        // Perform the core concretization cast.
899        // FIXME: need to unpack & re-pack the structure for cases like `Rc`, `Arc`, `Pin` and
900        // (when --raw-boxes is on) `Box`
901        let rval = Rvalue::UnaryOp(
902            UnOp::Cast(CastKind::Concretize(
903                shim_self.ty().clone(),
904                target_self.ty().clone(),
905            )),
906            Operand::Move(shim_self.clone()),
907        );
908        builder.push_statement(StatementKind::Assign(target_self.clone(), rval));
909
910        let fun_id = self.register_item(span, &impl_func_def.this(), TransItemSourceKind::Fun);
911        let generics = self.outermost_binder().params.identity_args();
912        builder.call(Call {
913            func: FnOperand::Regular(FnPtr::new(FnPtrKind::Fun(fun_id), generics)),
914            args: method_args
915                .into_iter()
916                .map(|arg| Operand::Move(arg))
917                .collect(),
918            dest: ret_place,
919        });
920
921        Ok(Body::Unstructured(builder.build()))
922    }
923
924    /// The target vtable drop_shim body looks like:
925    /// ```ignore
926    /// local ret@0 : ();
927    /// // the shim receiver of this drop_shim function
928    /// local shim_self@1 : ShimReceiverTy;
929    /// // the target receiver of the drop_shim
930    /// local target_self@2 : TargetReceiverTy;
931    /// // perform some conversion to cast / re-box the drop_shim receiver to the target receiver
932    /// target_self@2 := concretize_cast<ShimReceiverTy, TargetReceiverTy>(shim_self@1);
933    /// Drop(*target_self@2);
934    /// ```
935    fn translate_vtable_drop_shim_body(
936        &mut self,
937        span: Span,
938        shim_receiver: &Ty,
939        target_receiver: &Ty,
940        trait_pred: &TraitPredicate,
941    ) -> Result<Body, Error> {
942        let mut builder = BodyBuilder::new(span, 1);
943
944        builder.new_var(Some("ret".into()), Ty::mk_unit());
945        let dyn_self = builder.new_var(Some("dyn_self".into()), shim_receiver.clone());
946        let target_self = builder.new_var(Some("target_self".into()), target_receiver.clone());
947
948        // Perform the core concretization cast.
949        let rval = Rvalue::UnaryOp(
950            UnOp::Cast(CastKind::Concretize(
951                dyn_self.ty().clone(),
952                target_self.ty().clone(),
953            )),
954            Operand::Move(dyn_self.clone()),
955        );
956        builder.push_statement(StatementKind::Assign(target_self.clone(), rval));
957
958        // Build a reference to `impl Destruct for T`. Given the
959        // target_receiver type `T`, use Hax to solve `T: Destruct`
960        // and translate the resolved result to `TraitRef` of the
961        // `drop_in_place`
962        let destruct_trait = self.tcx.lang_items().destruct_trait().unwrap();
963        let impl_expr: hax::ImplExpr = {
964            let s = self.hax_state_with_id();
965            let rustc_trait_args = trait_pred.trait_ref.rustc_args(s);
966            let generics = self.tcx.mk_args(&rustc_trait_args[..1]); // keep only the `Self` type
967            let tref =
968                rustc_middle::ty::TraitRef::new_from_args(self.tcx, destruct_trait, generics);
969            hax::solve_trait(s, rustc_middle::ty::Binder::dummy(tref))
970        };
971        let tref = self.translate_trait_impl_expr(span, &impl_expr)?;
972
973        // Drop(*target_self)
974        let drop_arg = target_self.clone().deref();
975        builder.insert_drop(drop_arg, tref);
976
977        Ok(Body::Unstructured(builder.build()))
978    }
979
980    pub(crate) fn translate_vtable_drop_shim(
981        mut self,
982        fun_id: FunDeclId,
983        item_meta: ItemMeta,
984        impl_def: &hax::FullDef,
985    ) -> Result<FunDecl, Error> {
986        let span = item_meta.span;
987
988        let hax::FullDefKind::TraitImpl {
989            dyn_self: Some(dyn_self),
990            trait_pred,
991            ..
992        } = impl_def.kind()
993        else {
994            raise_error!(
995                self,
996                span,
997                "Trying to generate a vtable drop shim for a non-trait impl"
998            );
999        };
1000
1001        // `*mut dyn Trait`
1002        let ref_dyn_self =
1003            TyKind::RawPtr(self.translate_ty(span, dyn_self)?, RefKind::Mut).into_ty();
1004        // `*mut T` for `impl Trait for T`
1005        let ref_target_self = {
1006            let impl_trait = self.translate_trait_ref(span, &trait_pred.trait_ref)?;
1007            TyKind::RawPtr(impl_trait.generics.types[0].clone(), RefKind::Mut).into_ty()
1008        };
1009
1010        // `*mut dyn Trait -> ()`
1011        let signature = FunSig {
1012            is_unsafe: true,
1013            inputs: vec![ref_dyn_self.clone()],
1014            output: Ty::mk_unit(),
1015        };
1016
1017        let body: Body = self.translate_vtable_drop_shim_body(
1018            span,
1019            &ref_dyn_self,
1020            &ref_target_self,
1021            trait_pred,
1022        )?;
1023
1024        Ok(FunDecl {
1025            def_id: fun_id,
1026            item_meta,
1027            generics: self.into_generics(),
1028            signature,
1029            src: ItemSource::VTableMethodShim,
1030            is_global_initializer: None,
1031            body,
1032        })
1033    }
1034
1035    pub(crate) fn translate_vtable_shim(
1036        mut self,
1037        fun_id: FunDeclId,
1038        item_meta: ItemMeta,
1039        impl_func_def: &hax::FullDef,
1040    ) -> Result<FunDecl, Error> {
1041        let span = item_meta.span;
1042        self.check_no_monomorphize(span)?;
1043
1044        let hax::FullDefKind::AssocFn {
1045            vtable_sig: Some(vtable_sig),
1046            sig: target_signature,
1047            ..
1048        } = impl_func_def.kind()
1049        else {
1050            raise_error!(
1051                self,
1052                span,
1053                "Trying to generate a vtable shim for a non-vtable-safe method"
1054            );
1055        };
1056
1057        // The signature of the shim function.
1058        let signature = self.translate_fun_sig(span, &vtable_sig.value)?;
1059        // The concrete receiver we will cast to.
1060        let target_receiver = self.translate_ty(span, &target_signature.value.inputs[0])?;
1061
1062        trace!(
1063            "[VtableShim] Obtained dyn signature with receiver type: {}",
1064            signature.inputs[0].with_ctx(&self.into_fmt())
1065        );
1066
1067        let body = if item_meta.opacity.with_private_contents().is_opaque() {
1068            Body::Opaque
1069        } else {
1070            self.translate_vtable_shim_body(span, &target_receiver, &signature, impl_func_def)?
1071        };
1072
1073        Ok(FunDecl {
1074            def_id: fun_id,
1075            item_meta,
1076            generics: self.into_generics(),
1077            signature,
1078            src: ItemSource::VTableMethodShim,
1079            is_global_initializer: None,
1080            body,
1081        })
1082    }
1083}
charon_driver/translate/translate_trait_objects.rs

charon_driver/translate/
translate_trait_objects.rs
