Skip to main content

charon_driver/translate/
translate_items.rs

1use super::translate_crate::*;
2use super::translate_ctx::*;
3use charon_lib::ast::ullbc_ast_utils::BodyBuilder;
4use charon_lib::ast::*;
5use charon_lib::formatter::IntoFormatter;
6use charon_lib::pretty::FmtWithCtx;
7use derive_generic_visitor::Visitor;
8use hax::SInto;
9use itertools::Itertools;
10use rustc_span::sym;
11use std::mem;
12use std::ops::ControlFlow;
13
14impl<'tcx, 'ctx> TranslateCtx<'tcx> {
15    pub(crate) fn translate_item(&mut self, item_src: &TransItemSource) {
16        let trans_id = self.register_no_enqueue(&None, item_src);
17        let def_id = item_src.def_id();
18        if let Some(trans_id) = trans_id {
19            if self.translate_stack.contains(&trans_id) {
20                register_error!(
21                    self,
22                    Span::dummy(),
23                    "Cycle detected while translating {def_id:?}! Stack: {:?}",
24                    &self.translate_stack
25                );
26                return;
27            } else {
28                self.translate_stack.push(trans_id);
29            }
30        }
31        self.with_def_id(def_id, trans_id, |mut ctx| {
32            let span = ctx.def_span(def_id);
33            // Catch cycles
34            let res = {
35                // Stopgap measure because there are still many panics in charon and hax.
36                let mut ctx = std::panic::AssertUnwindSafe(&mut ctx);
37                std::panic::catch_unwind(move || ctx.translate_item_aux(item_src, trans_id))
38            };
39            match res {
40                Ok(Ok(())) => return,
41                // Translation error
42                Ok(Err(_)) => {
43                    register_error!(ctx, span, "Item `{def_id:?}` caused errors; ignoring.")
44                }
45                // Panic
46                Err(_) => register_error!(
47                    ctx,
48                    span,
49                    "Thread panicked when extracting item `{def_id:?}`."
50                ),
51            };
52        });
53        // We must be careful not to early-return from this function to not unbalance the stack.
54        self.translate_stack.pop();
55    }
56
57    pub(crate) fn translate_item_aux(
58        &mut self,
59        item_src: &TransItemSource,
60        trans_id: Option<ItemId>,
61    ) -> Result<(), Error> {
62        // Translate the meta information
63        let name = self.translate_name(item_src)?;
64        if let Some(trans_id) = trans_id {
65            self.translated.item_names.insert(trans_id, name.clone());
66        }
67        let opacity = self.opacity_for_name(&name);
68        if opacity.is_invisible() {
69            // Don't even start translating the item. In particular don't call `hax_def` on it.
70            return Ok(());
71        }
72        let def = self.hax_def_for_item(&item_src.item)?;
73        let item_meta = self.translate_item_meta(&def, item_src, name, opacity);
74        if item_meta.opacity.is_invisible() {
75            return Ok(());
76        }
77
78        // For items in the current crate that have bodies, also enqueue items defined in that
79        // body.
80        if !item_meta.opacity.is_opaque()
81            && let Some(def_id) = def.def_id().as_rust_def_id()
82            && let Some(ldid) = def_id.as_local()
83            && let node = self.tcx.hir_node_by_def_id(ldid)
84            && let Some(body_id) = node.body_id()
85        {
86            use rustc_hir::intravisit;
87            #[allow(non_local_definitions)]
88            impl<'tcx> intravisit::Visitor<'tcx> for TranslateCtx<'tcx> {
89                fn visit_nested_item(&mut self, id: rustc_hir::ItemId) {
90                    let def_id = id.owner_id.def_id.to_def_id();
91                    let def_id = def_id.sinto(&self.hax_state);
92                    self.enqueue_module_item(&def_id);
93                }
94            }
95            let body = self.tcx.hir_body(body_id);
96            intravisit::walk_body(self, body);
97        }
98
99        // Initialize the item translation context
100        let mut bt_ctx = ItemTransCtx::new(item_src.clone(), trans_id, self);
101        trace!(
102            "About to translate item `{:?}` as a {:?}; \
103            target_id={trans_id:?}, mono={}",
104            def.def_id(),
105            item_src.kind,
106            bt_ctx.monomorphize()
107        );
108        if !matches!(
109            &item_src.kind,
110            TransItemSourceKind::InherentImpl | TransItemSourceKind::Module,
111        ) {
112            bt_ctx.translate_item_generics(item_meta.span, &def, &item_src.kind)?;
113        }
114        match &item_src.kind {
115            TransItemSourceKind::InherentImpl | TransItemSourceKind::Module => {
116                bt_ctx.register_module(item_meta, &def);
117            }
118            TransItemSourceKind::Type => {
119                let Some(ItemId::Type(id)) = trans_id else {
120                    unreachable!()
121                };
122                let ty = bt_ctx.translate_type_decl(id, item_meta, &def)?;
123                self.translated.type_decls.set_slot(id, ty);
124            }
125            TransItemSourceKind::Fun => {
126                let Some(ItemId::Fun(id)) = trans_id else {
127                    unreachable!()
128                };
129                let fun_decl = bt_ctx.translate_fun_decl(id, item_meta, &def)?;
130                self.translated.fun_decls.set_slot(id, fun_decl);
131            }
132            TransItemSourceKind::Global => {
133                let Some(ItemId::Global(id)) = trans_id else {
134                    unreachable!()
135                };
136                let global_decl = bt_ctx.translate_global(id, item_meta, &def)?;
137                self.translated.global_decls.set_slot(id, global_decl);
138            }
139            TransItemSourceKind::TraitDecl => {
140                let Some(ItemId::TraitDecl(id)) = trans_id else {
141                    unreachable!()
142                };
143                let trait_decl = bt_ctx.translate_trait_decl(id, item_meta, &def)?;
144                self.translated.trait_decls.set_slot(id, trait_decl);
145            }
146            TransItemSourceKind::TraitImpl(kind) => {
147                let Some(ItemId::TraitImpl(id)) = trans_id else {
148                    unreachable!()
149                };
150                let trait_impl = match kind {
151                    TraitImplSource::Normal => bt_ctx.translate_trait_impl(id, item_meta, &def)?,
152                    TraitImplSource::TraitAlias => {
153                        bt_ctx.translate_trait_alias_blanket_impl(id, item_meta, &def)?
154                    }
155                    &TraitImplSource::Closure(kind) => {
156                        bt_ctx.translate_closure_trait_impl(id, item_meta, &def, kind)?
157                    }
158                    TraitImplSource::ImplicitDestruct => {
159                        bt_ctx.translate_implicit_destruct_impl(id, item_meta, &def)?
160                    }
161                };
162                self.translated.trait_impls.set_slot(id, trait_impl);
163            }
164            &TransItemSourceKind::DefaultedMethod(impl_kind, name) => {
165                let Some(ItemId::Fun(id)) = trans_id else {
166                    unreachable!()
167                };
168                let fun_decl =
169                    bt_ctx.translate_defaulted_method(id, item_meta, &def, impl_kind, name)?;
170                self.translated.fun_decls.set_slot(id, fun_decl);
171            }
172            &TransItemSourceKind::ClosureMethod(kind) => {
173                let Some(ItemId::Fun(id)) = trans_id else {
174                    unreachable!()
175                };
176                let fun_decl = bt_ctx.translate_closure_method(id, item_meta, &def, kind)?;
177                self.translated.fun_decls.set_slot(id, fun_decl);
178            }
179            TransItemSourceKind::ClosureAsFnCast => {
180                let Some(ItemId::Fun(id)) = trans_id else {
181                    unreachable!()
182                };
183                let fun_decl = bt_ctx.translate_stateless_closure_as_fn(id, item_meta, &def)?;
184                self.translated.fun_decls.set_slot(id, fun_decl);
185            }
186            &TransItemSourceKind::DropInPlaceMethod(impl_kind) => {
187                let Some(ItemId::Fun(id)) = trans_id else {
188                    unreachable!()
189                };
190                let fun_decl =
191                    bt_ctx.translate_drop_in_place_method(id, item_meta, &def, impl_kind)?;
192                self.translated.fun_decls.set_slot(id, fun_decl);
193            }
194            TransItemSourceKind::VTable => {
195                let Some(ItemId::Type(id)) = trans_id else {
196                    unreachable!()
197                };
198                let ty_decl = bt_ctx.translate_vtable_struct(id, item_meta, &def)?;
199                self.translated.type_decls.set_slot(id, ty_decl);
200            }
201            TransItemSourceKind::VTableInstance(impl_kind) => {
202                let Some(ItemId::Global(id)) = trans_id else {
203                    unreachable!()
204                };
205                let global_decl =
206                    bt_ctx.translate_vtable_instance(id, item_meta, &def, impl_kind)?;
207                self.translated.global_decls.set_slot(id, global_decl);
208            }
209            TransItemSourceKind::VTableInstanceInitializer(impl_kind) => {
210                let Some(ItemId::Fun(id)) = trans_id else {
211                    unreachable!()
212                };
213                let fun_decl =
214                    bt_ctx.translate_vtable_instance_init(id, item_meta, &def, impl_kind)?;
215                self.translated.fun_decls.set_slot(id, fun_decl);
216            }
217            TransItemSourceKind::VTableMethod => {
218                let Some(ItemId::Fun(id)) = trans_id else {
219                    unreachable!()
220                };
221                let fun_decl = bt_ctx.translate_vtable_shim(id, item_meta, &def)?;
222                self.translated.fun_decls.set_slot(id, fun_decl);
223            }
224            TransItemSourceKind::VTableDropShim => {
225                let Some(ItemId::Fun(id)) = trans_id else {
226                    unreachable!()
227                };
228                let fun_decl = bt_ctx.translate_vtable_drop_shim(id, item_meta, &def)?;
229                self.translated.fun_decls.set_slot(id, fun_decl);
230            }
231        }
232        Ok(())
233    }
234
235    /// While translating an item you may need the contents of another. Use this to retreive the
236    /// translated version of this item. Use with care as this could create cycles.
237    pub(crate) fn get_or_translate(&mut self, id: ItemId) -> Result<krate::ItemRef<'_>, Error> {
238        // We have to call `get_item` a few times because we're running into the classic `Polonius`
239        // problem case.
240        if self.translated.get_item(id).is_none() {
241            let item_source = self.reverse_id_map.get(&id).unwrap().clone();
242            self.translate_item(&item_source);
243            if self.translated.get_item(id).is_none() {
244                let span = self.def_span(item_source.def_id());
245                let name = self
246                    .translated
247                    .item_name(id)
248                    .map(|n| n.to_string_with_ctx(&self.into_fmt()))
249                    .unwrap_or_else(|| id.to_string());
250                // Not a real error, its message won't be displayed.
251                return Err(Error {
252                    span,
253                    msg: format!("Failed to translate item {name}."),
254                });
255                // raise_error!(self, span, "Failed to translate item {name}.")
256            }
257            // Add to avoid the double translation of the same item
258            self.processed.insert(item_source.clone());
259        }
260        let item = self.translated.get_item(id);
261        Ok(item.unwrap())
262    }
263
264    /// Add a `const UNIT: () = ();` const, used as metadata for thin pointers/references.
265    pub fn translate_unit_metadata_const(&mut self) {
266        use charon_lib::ullbc_ast::*;
267        let name = Name::from_path(&["UNIT_METADATA"]);
268        let item_meta = ItemMeta {
269            name,
270            span: Span::dummy(),
271            source_text: None,
272            attr_info: AttrInfo::default(),
273            is_local: false,
274            opacity: ItemOpacity::Foreign,
275            lang_item: None,
276        };
277
278        let body = {
279            let mut builder = BodyBuilder::new(Span::dummy(), 0);
280            let _ = builder.new_var(None, Ty::mk_unit());
281            builder.build()
282        };
283
284        let global_id = self.translated.global_decls.reserve_slot();
285        let initializer = self.translated.fun_decls.push_with(|def_id| FunDecl {
286            def_id,
287            item_meta: item_meta.clone(),
288            src: ItemSource::TopLevel,
289            is_global_initializer: Some(global_id),
290            generics: Default::default(),
291            signature: FunSig {
292                is_unsafe: false,
293                inputs: vec![],
294                output: Ty::mk_unit(),
295            },
296            body: Body::Unstructured(body),
297        });
298        self.translated.global_decls.set_slot(
299            global_id,
300            GlobalDecl {
301                def_id: global_id,
302                item_meta,
303                generics: Default::default(),
304                ty: Ty::mk_unit(),
305                src: ItemSource::TopLevel,
306                global_kind: GlobalKind::NamedConst,
307                init: initializer,
308            },
309        );
310        self.translated.unit_metadata = Some(GlobalDeclRef {
311            id: global_id,
312            generics: Box::new(GenericArgs::empty()),
313        });
314    }
315
316    /// Keep only the methods we marked as "used".
317    pub fn remove_unused_methods(&mut self) {
318        let method_is_used = |trait_id, name| {
319            self.method_status.get(trait_id).is_some_and(|map| {
320                map.get(&name)
321                    .is_some_and(|status| matches!(status, MethodStatus::Used))
322            })
323        };
324        for tdecl in self.translated.trait_decls.iter_mut() {
325            tdecl
326                .methods
327                .retain(|m| method_is_used(tdecl.def_id, m.name()));
328        }
329        for timpl in self.translated.trait_impls.iter_mut() {
330            let trait_id = timpl.impl_trait.id;
331            timpl
332                .methods
333                .retain(|(name, _)| method_is_used(trait_id, *name));
334        }
335    }
336}
337
338impl ItemTransCtx<'_, '_> {
339    /// Register the items inside this module or inherent impl.
340    // TODO: we may want to accumulate the set of modules we found, to check that all
341    // the opaque modules given as arguments actually exist
342    #[tracing::instrument(skip(self, item_meta, def))]
343    pub(crate) fn register_module(&mut self, item_meta: ItemMeta, def: &hax::FullDef) {
344        if !item_meta.opacity.is_transparent() {
345            return;
346        }
347        match def.kind() {
348            hax::FullDefKind::InherentImpl { items, .. } => {
349                for assoc in items {
350                    self.t_ctx.enqueue_module_item(&assoc.def_id);
351                }
352            }
353            hax::FullDefKind::Mod { items, .. } => {
354                for (_, def_id) in items {
355                    self.t_ctx.enqueue_module_item(def_id);
356                }
357            }
358            hax::FullDefKind::ForeignMod { items, .. } => {
359                for def_id in items {
360                    self.t_ctx.enqueue_module_item(def_id);
361                }
362            }
363            _ => panic!("Item should be a module but isn't: {def:?}"),
364        }
365    }
366
367    pub(crate) fn get_item_source(
368        &mut self,
369        span: Span,
370        def: &hax::FullDef,
371    ) -> Result<ItemSource, Error> {
372        let assoc = match def.kind() {
373            hax::FullDefKind::AssocTy {
374                associated_item, ..
375            }
376            | hax::FullDefKind::AssocConst {
377                associated_item, ..
378            }
379            | hax::FullDefKind::AssocFn {
380                associated_item, ..
381            } => associated_item,
382            hax::FullDefKind::Closure { args, .. } => {
383                let info = self.translate_closure_info(span, args)?;
384                return Ok(ItemSource::Closure { info });
385            }
386            _ => return Ok(ItemSource::TopLevel),
387        };
388        Ok(match &assoc.container {
389            // E.g.:
390            // ```
391            // impl<T> List<T> {
392            //   fn new() -> Self { ... } <- inherent method
393            // }
394            // ```
395            hax::AssocItemContainer::InherentImplContainer { .. } => ItemSource::TopLevel,
396            // E.g.:
397            // ```
398            // impl Foo for Bar {
399            //   fn baz(...) { ... } // <- implementation of a trait method
400            // }
401            // ```
402            hax::AssocItemContainer::TraitImplContainer {
403                impl_,
404                implemented_trait_ref,
405                overrides_default,
406                ..
407            } => {
408                let impl_ref =
409                    self.translate_trait_impl_ref(span, impl_, TraitImplSource::Normal)?;
410                let trait_ref = self.translate_trait_ref(span, implemented_trait_ref)?;
411                let item_name = self.t_ctx.translate_trait_item_name(def.def_id())?;
412                if matches!(def.kind(), hax::FullDefKind::AssocFn { .. }) {
413                    // If the implementation is getting translated, that means the method is
414                    // getting used.
415                    self.mark_method_as_used(trait_ref.id, item_name);
416                }
417                ItemSource::TraitImpl {
418                    impl_ref,
419                    trait_ref,
420                    item_name,
421                    reuses_default: !overrides_default,
422                }
423            }
424            // This method is the *declaration* of a trait item
425            // E.g.:
426            // ```
427            // trait Foo {
428            //   fn baz(...); // <- declaration of a trait method
429            // }
430            // ```
431            hax::AssocItemContainer::TraitContainer { trait_ref, .. } => {
432                // The trait id should be Some(...): trait markers (that we may eliminate)
433                // don't have associated items.
434                let trait_ref = self.translate_trait_ref(span, trait_ref)?;
435                let item_name = self.t_ctx.translate_trait_item_name(def.def_id())?;
436                ItemSource::TraitDecl {
437                    trait_ref,
438                    item_name,
439                    has_default: assoc.has_value,
440                }
441            }
442        })
443    }
444
445    /// Translate a type definition.
446    ///
447    /// Note that we translate the types one by one: we don't need to take into
448    /// account the fact that some types are mutually recursive at this point
449    /// (we will need to take that into account when generating the code in a file).
450    #[tracing::instrument(skip(self, item_meta, def))]
451    pub fn translate_type_decl(
452        mut self,
453        trans_id: TypeDeclId,
454        item_meta: ItemMeta,
455        def: &hax::FullDef,
456    ) -> Result<TypeDecl, Error> {
457        let span = item_meta.span;
458
459        // Get the kind of the type decl -- is it a closure?
460        let src = self.get_item_source(span, def)?;
461
462        let mut repr: Option<ReprOptions> = None;
463
464        // Translate type body
465        let kind = match &def.kind {
466            _ if item_meta.opacity.is_opaque() => Ok(TypeDeclKind::Opaque),
467            hax::FullDefKind::OpaqueTy | hax::FullDefKind::ForeignTy => Ok(TypeDeclKind::Opaque),
468            hax::FullDefKind::TyAlias { ty, .. } => {
469                // Don't error on missing trait refs.
470                self.error_on_impl_expr_error = false;
471                self.translate_ty(span, ty).map(TypeDeclKind::Alias)
472            }
473            hax::FullDefKind::Adt { repr: hax_repr, .. } => {
474                repr = Some(self.translate_repr_options(hax_repr));
475                self.translate_adt_def(trans_id, span, &item_meta, def)
476            }
477            hax::FullDefKind::Closure { args, .. } => self.translate_closure_adt(span, &args),
478            _ => panic!("Unexpected item when translating types: {def:?}"),
479        };
480
481        let kind = match kind {
482            Ok(kind) => kind,
483            Err(err) => TypeDeclKind::Error(err.msg),
484        };
485        let layout = self.translate_layout(def.this());
486        let ptr_metadata = self.translate_ptr_metadata(span, def.this())?;
487        let type_def = TypeDecl {
488            def_id: trans_id,
489            item_meta,
490            generics: self.into_generics(),
491            kind,
492            src,
493            layout,
494            ptr_metadata,
495            repr,
496        };
497
498        Ok(type_def)
499    }
500
501    /// Translate one function.
502    #[tracing::instrument(skip(self, item_meta, def))]
503    pub fn translate_fun_decl(
504        mut self,
505        def_id: FunDeclId,
506        item_meta: ItemMeta,
507        def: &hax::FullDef,
508    ) -> Result<FunDecl, Error> {
509        let span = item_meta.span;
510
511        let src = self.get_item_source(span, def)?;
512
513        if let hax::FullDefKind::Ctor {
514            fields, output_ty, ..
515        } = def.kind()
516        {
517            let signature = FunSig {
518                inputs: fields
519                    .iter()
520                    .map(|field| self.translate_ty(span, &field.ty))
521                    .try_collect()?,
522                output: self.translate_ty(span, output_ty)?,
523                is_unsafe: false,
524            };
525
526            let body = if item_meta.opacity.with_private_contents().is_opaque() {
527                Body::Opaque
528            } else {
529                self.build_ctor_body(span, def)?
530            };
531            return Ok(FunDecl {
532                def_id,
533                item_meta,
534                generics: self.into_generics(),
535                signature,
536                src,
537                is_global_initializer: None,
538                body,
539            });
540        }
541
542        // Translate the function signature
543        trace!("Translating function signature");
544        let signature = match &def.kind {
545            hax::FullDefKind::Fn { sig, .. } | hax::FullDefKind::AssocFn { sig, .. } => {
546                self.translate_fun_sig(span, &sig.value)?
547            }
548            hax::FullDefKind::Const { ty, .. }
549            | hax::FullDefKind::AssocConst { ty, .. }
550            | hax::FullDefKind::Static { ty, .. } => FunSig {
551                inputs: vec![],
552                output: self.translate_ty(span, ty)?,
553                is_unsafe: false,
554            },
555            _ => panic!("Unexpected definition for function: {def:?}"),
556        };
557
558        // Check whether this function is a method declaration for a trait definition.
559        // If this is the case, it shouldn't contain a body.
560        let is_trait_method_decl_without_default = match &src {
561            ItemSource::TraitDecl { has_default, .. } => !has_default,
562            _ => false,
563        };
564
565        let is_global_initializer = matches!(
566            def.kind(),
567            hax::FullDefKind::Const { .. }
568                | hax::FullDefKind::AssocConst { .. }
569                | hax::FullDefKind::Static { .. }
570        );
571        let is_global_initializer = is_global_initializer
572            .then(|| self.register_item(span, def.this(), TransItemSourceKind::Global));
573
574        let body = if item_meta.opacity.with_private_contents().is_opaque() {
575            Body::Opaque
576        } else if is_trait_method_decl_without_default {
577            Body::TraitMethodWithoutDefault
578        } else {
579            // Translate the MIR body for this definition.
580            self.translate_def_body(item_meta.span, def)
581        };
582        Ok(FunDecl {
583            def_id,
584            item_meta,
585            generics: self.into_generics(),
586            signature,
587            src,
588            is_global_initializer,
589            body,
590        })
591    }
592
593    /// Translate one global.
594    #[tracing::instrument(skip(self, item_meta, def))]
595    pub fn translate_global(
596        mut self,
597        def_id: GlobalDeclId,
598        item_meta: ItemMeta,
599        def: &hax::FullDef,
600    ) -> Result<GlobalDecl, Error> {
601        let span = item_meta.span;
602
603        // Retrieve the kind
604        let item_source = self.get_item_source(span, def)?;
605
606        trace!("Translating global type");
607        let ty = match &def.kind {
608            hax::FullDefKind::Const { ty, .. }
609            | hax::FullDefKind::AssocConst { ty, .. }
610            | hax::FullDefKind::Static { ty, .. } => ty,
611            _ => panic!("Unexpected def for constant: {def:?}"),
612        };
613        let ty = self.translate_ty(span, ty)?;
614
615        let global_kind = match &def.kind {
616            hax::FullDefKind::Static { .. } => GlobalKind::Static,
617            hax::FullDefKind::Const {
618                kind: hax::ConstKind::TopLevel,
619                ..
620            }
621            | hax::FullDefKind::AssocConst { .. } => GlobalKind::NamedConst,
622            hax::FullDefKind::Const { .. } => GlobalKind::AnonConst,
623            _ => panic!("Unexpected def for constant: {def:?}"),
624        };
625
626        let initializer = self.register_item(span, def.this(), TransItemSourceKind::Fun);
627
628        Ok(GlobalDecl {
629            def_id,
630            item_meta,
631            generics: self.into_generics(),
632            ty,
633            src: item_source,
634            global_kind,
635            init: initializer,
636        })
637    }
638
639    #[tracing::instrument(skip(self, item_meta, def))]
640    pub fn translate_trait_decl(
641        mut self,
642        def_id: TraitDeclId,
643        item_meta: ItemMeta,
644        def: &hax::FullDef,
645    ) -> Result<TraitDecl, Error> {
646        let span = item_meta.span;
647
648        let (hax::FullDefKind::Trait {
649            implied_predicates, ..
650        }
651        | hax::FullDefKind::TraitAlias {
652            implied_predicates, ..
653        }) = def.kind()
654        else {
655            raise_error!(self, span, "Unexpected definition: {def:?}");
656        };
657
658        // Register implied predicates.
659        let mut preds =
660            self.translate_predicates(implied_predicates, PredicateOrigin::WhereClauseOnTrait)?;
661        let implied_clauses = mem::take(&mut preds.trait_clauses);
662        // Consider the other predicates as required since the distinction doesn't matter for
663        // non-trait-clauses.
664        self.innermost_generics_mut().take_predicates_from(preds);
665
666        let vtable = self.translate_vtable_struct_ref_no_enqueue(span, def.this())?;
667
668        if let hax::FullDefKind::TraitAlias { .. } = def.kind() {
669            // Trait aliases don't have any items. Everything interesting is in the parent clauses.
670            return Ok(TraitDecl {
671                def_id,
672                item_meta,
673                implied_clauses,
674                generics: self.into_generics(),
675                consts: Default::default(),
676                types: Default::default(),
677                methods: Default::default(),
678                vtable,
679            });
680        }
681
682        let hax::FullDefKind::Trait {
683            items,
684            self_predicate,
685            ..
686        } = &def.kind
687        else {
688            unreachable!()
689        };
690        let self_trait_ref = TraitRef::new(
691            TraitRefKind::SelfId,
692            RegionBinder::empty(self.translate_trait_predicate(span, self_predicate)?),
693        );
694        let items: Vec<(TraitItemName, &hax::AssocItem)> = items
695            .iter()
696            .map(|item| -> Result<_, Error> {
697                let name = self.t_ctx.translate_trait_item_name(&item.def_id)?;
698                Ok((name, item))
699            })
700            .try_collect()?;
701
702        // Translate the associated items
703        let mut consts = Vec::new();
704        let mut types = Vec::new();
705        let mut methods = Vec::new();
706
707        for &(item_name, ref hax_item) in &items {
708            let item_def_id = &hax_item.def_id;
709            let item_span = self.def_span(item_def_id);
710
711            // In --mono mode, we keep only non-polymorphic items; in not-mono mode, we use the
712            // polymorphic item as usual.
713            let trans_kind = match hax_item.kind {
714                hax::AssocKind::Fn { .. } => TransItemSourceKind::Fun,
715                hax::AssocKind::Const { .. } => TransItemSourceKind::Global,
716                hax::AssocKind::Type { .. } => TransItemSourceKind::Type,
717            };
718            let poly_item_def = self.poly_hax_def(item_def_id)?;
719            let (item_src, item_def) = if self.monomorphize() {
720                if poly_item_def.has_own_generics_or_predicates() {
721                    // Skip items that have generics of their own (as rustc defines these). This
722                    // skips GAT and generic methods. This does not skip methods with late-bound
723                    // lifetimes as these aren't considered generic arguments to the method itself
724                    // by rustc.
725                    continue;
726                } else {
727                    let item = def.this().with_def_id(self.hax_state(), item_def_id);
728                    let item_def = self.hax_def(&item)?;
729                    let item_src = TransItemSource::monomorphic(&item, trans_kind);
730                    (item_src, item_def)
731                }
732            } else {
733                let item_src = TransItemSource::polymorphic(item_def_id, trans_kind);
734                (item_src, poly_item_def)
735            };
736            let attr_info = self.translate_attr_info(&item_def);
737
738            match item_def.kind() {
739                hax::FullDefKind::AssocFn { .. } => {
740                    let method_id = self.register_no_enqueue(item_span, &item_src);
741                    // Register this method.
742                    self.register_method_impl(def_id, item_name, method_id);
743                    // By default we only enqueue required methods (those that don't have a default
744                    // impl). If the trait is transparent, we enqueue all its methods.
745                    if self.options.translate_all_methods
746                        || item_meta.opacity.is_transparent()
747                        || !hax_item.has_value
748                    {
749                        self.mark_method_as_used(def_id, item_name);
750                    }
751
752                    let binder_kind = BinderKind::TraitMethod(def_id, item_name);
753                    let mut method = self.translate_binder_for_def(
754                        item_span,
755                        binder_kind,
756                        &item_def,
757                        |bt_ctx| {
758                            assert_eq!(bt_ctx.binding_levels.len(), 2);
759                            let fun_generics = bt_ctx
760                                .outermost_binder()
761                                .params
762                                .identity_args_at_depth(DeBruijnId::one())
763                                .concat(
764                                    &bt_ctx
765                                        .innermost_binder()
766                                        .params
767                                        .identity_args_at_depth(DeBruijnId::zero()),
768                                );
769                            let fn_ref = FunDeclRef {
770                                id: method_id,
771                                generics: Box::new(fun_generics),
772                            };
773                            Ok(TraitMethod {
774                                name: item_name.clone(),
775                                attr_info,
776                                item: fn_ref,
777                            })
778                        },
779                    )?;
780                    // In hax, associated items take an extra explicit `Self: Trait` clause, but we
781                    // don't want that to be part of the method clauses. Hence we remove the first
782                    // bound clause and replace its uses with references to the ambient `Self`
783                    // clause available in trait declarations.
784                    if !self.monomorphize() {
785                        struct ReplaceSelfVisitor;
786                        impl VarsVisitor for ReplaceSelfVisitor {
787                            fn visit_clause_var(&mut self, v: ClauseDbVar) -> Option<TraitRefKind> {
788                                if let DeBruijnVar::Bound(DeBruijnId::ZERO, clause_id) = v {
789                                    // Replace clause 0 and decrement the others.
790                                    Some(if let Some(new_id) = clause_id.index().checked_sub(1) {
791                                        TraitRefKind::Clause(DeBruijnVar::Bound(
792                                            DeBruijnId::ZERO,
793                                            TraitClauseId::new(new_id),
794                                        ))
795                                    } else {
796                                        TraitRefKind::SelfId
797                                    })
798                                } else {
799                                    None
800                                }
801                            }
802                        }
803                        method.params.visit_vars(&mut ReplaceSelfVisitor);
804                        method.skip_binder.visit_vars(&mut ReplaceSelfVisitor);
805                        method
806                            .params
807                            .trait_clauses
808                            .remove_and_shift_ids(TraitClauseId::ZERO);
809                        method.params.trait_clauses.iter_mut().for_each(|clause| {
810                            clause.clause_id -= 1;
811                        });
812                    }
813
814                    // We insert the `Binder<TraitMethod>` unconditionally here; we'll remove the
815                    // ones that correspond to unused methods at the end of translation.
816                    methods.push(method);
817                }
818                hax::FullDefKind::AssocConst { ty, .. } => {
819                    // Check if the constant has a value (i.e., a body).
820                    let default = hax_item.has_value.then(|| {
821                        // The parameters of the constant are the same as those of the item that
822                        // declares them.
823                        let id = self.register_and_enqueue(item_span, item_src);
824                        let mut generics = self.the_only_binder().params.identity_args();
825                        // We add an extra `Self: Trait` clause to default consts.
826                        if !self.monomorphize() {
827                            generics.trait_refs.push(self_trait_ref.clone());
828                        }
829                        GlobalDeclRef {
830                            id,
831                            generics: Box::new(generics),
832                        }
833                    });
834                    let ty = self.translate_ty(item_span, ty)?;
835                    consts.push(TraitAssocConst {
836                        name: item_name.clone(),
837                        attr_info,
838                        ty,
839                        default,
840                    });
841                }
842                // Monomorphic traits need no associated types.
843                hax::FullDefKind::AssocTy { .. } if self.monomorphize() => continue,
844                hax::FullDefKind::AssocTy {
845                    value,
846                    implied_predicates,
847                    ..
848                } => {
849                    let binder_kind = BinderKind::TraitType(def_id, item_name.clone());
850                    let assoc_ty =
851                        self.translate_binder_for_def(item_span, binder_kind, &item_def, |ctx| {
852                            // Also add the implied predicates.
853                            let mut preds = ctx.translate_predicates(
854                                &implied_predicates,
855                                PredicateOrigin::TraitItem(item_name.clone()),
856                            )?;
857                            let implied_clauses = mem::take(&mut preds.trait_clauses);
858                            // Consider the other predicates as required since the distinction doesn't
859                            // matter for non-trait-clauses.
860                            ctx.innermost_generics_mut().take_predicates_from(preds);
861
862                            let default = value
863                                .as_ref()
864                                .map(|ty| ctx.translate_ty(item_span, ty))
865                                .transpose()?;
866                            Ok(TraitAssocTy {
867                                name: item_name.clone(),
868                                attr_info,
869                                default,
870                                implied_clauses,
871                            })
872                        })?;
873                    types.push(assoc_ty);
874                }
875                _ => panic!("Unexpected definition for trait item: {item_def:?}"),
876            }
877        }
878
879        if def.lang_item == Some(sym::destruct) {
880            // Add a `drop_in_place(*mut self)` method that contains the drop glue for this type.
881            let (method_name, method_binder) =
882                self.prepare_drop_in_place_method(def, span, def_id, None);
883            self.mark_method_as_used(def_id, method_name);
884            methods.push(method_binder.map(|fn_ref| TraitMethod {
885                name: method_name,
886                attr_info: AttrInfo::dummy_public(),
887                item: fn_ref,
888            }));
889        }
890
891        // In case of a trait implementation, some values may not have been
892        // provided, in case the declaration provided default values. We
893        // check those, and lookup the relevant values.
894        Ok(TraitDecl {
895            def_id,
896            item_meta,
897            implied_clauses,
898            generics: self.into_generics(),
899            consts,
900            types,
901            methods,
902            vtable,
903        })
904    }
905
906    #[tracing::instrument(skip(self, item_meta, def))]
907    pub fn translate_trait_impl(
908        mut self,
909        def_id: TraitImplId,
910        item_meta: ItemMeta,
911        def: &hax::FullDef,
912    ) -> Result<TraitImpl, Error> {
913        let span = item_meta.span;
914
915        let hax::FullDefKind::TraitImpl {
916            trait_pred,
917            implied_impl_exprs,
918            items: impl_items,
919            ..
920        } = &def.kind
921        else {
922            unreachable!()
923        };
924
925        // Retrieve the information about the implemented trait.
926        let implemented_trait = self.translate_trait_ref(span, &trait_pred.trait_ref)?;
927        let trait_id = implemented_trait.id;
928        // A `TraitRef` that points to this impl with the correct generics.
929        let self_predicate = TraitRef::new(
930            TraitRefKind::TraitImpl(TraitImplRef {
931                id: def_id,
932                generics: Box::new(self.the_only_binder().params.identity_args()),
933            }),
934            RegionBinder::empty(implemented_trait.clone()),
935        );
936
937        let vtable =
938            self.translate_vtable_instance_ref_no_enqueue(span, &trait_pred.trait_ref, def.this())?;
939
940        // The trait refs which implement the parent clauses of the implemented trait decl.
941        let implied_trait_refs = self.translate_trait_impl_exprs(span, &implied_impl_exprs)?;
942
943        {
944            // Debugging
945            let ctx = self.into_fmt();
946            let refs = implied_trait_refs
947                .iter()
948                .map(|c| c.with_ctx(&ctx))
949                .format("\n");
950            trace!(
951                "Trait impl: {:?}\n- implied_trait_refs:\n{}",
952                def.def_id(),
953                refs
954            );
955        }
956
957        // Explore the associated items
958        let mut consts = Vec::new();
959        let mut types = Vec::new();
960        let mut methods = Vec::new();
961
962        for impl_item in impl_items {
963            use hax::ImplAssocItemValue::*;
964            let name = self
965                .t_ctx
966                .translate_trait_item_name(&impl_item.decl_def_id)?;
967            let item_def_id = impl_item.def_id();
968            let item_span = self.def_span(item_def_id);
969            //
970            // In --mono mode, we keep only non-polymorphic items; in not-mono mode, we use the
971            // polymorphic item as usual.
972            let poly_item_def = self.poly_hax_def(item_def_id)?;
973            let trans_kind = match poly_item_def.kind() {
974                hax::FullDefKind::AssocFn { .. } => TransItemSourceKind::Fun,
975                hax::FullDefKind::AssocConst { .. } => TransItemSourceKind::Global,
976                hax::FullDefKind::AssocTy { .. } => TransItemSourceKind::Type,
977                _ => unreachable!(),
978            };
979            let (item_src, item_def) = if self.monomorphize() {
980                if poly_item_def.has_own_generics_or_predicates() {
981                    continue;
982                } else {
983                    let item = match &impl_item.value {
984                        // Real item: we reuse the impl arguments to get a reference to the item.
985                        Provided { def_id, .. } => def.this().with_def_id(self.hax_state(), def_id),
986                        // Defaulted item: we use the implemented trait arguments.
987                        _ => trait_pred
988                            .trait_ref
989                            .with_def_id(self.hax_state(), &impl_item.decl_def_id),
990                    };
991                    let item_src = TransItemSource::monomorphic(&item, trans_kind);
992                    let item_def = self.hax_def_for_item(&item_src.item)?;
993                    (item_src, item_def)
994                }
995            } else {
996                let item_src = TransItemSource::polymorphic(item_def_id, trans_kind);
997                (item_src, poly_item_def)
998            };
999
1000            match item_def.kind() {
1001                hax::FullDefKind::AssocFn { .. } => {
1002                    let method_id: FunDeclId = {
1003                        let method_src = match &impl_item.value {
1004                            Provided { .. } => item_src,
1005                            // This will generate a copy of the default method. Note that the base
1006                            // item for `DefaultedMethod` is the trait impl.
1007                            DefaultedFn { .. } => TransItemSource::from_item(
1008                                def.this(),
1009                                TransItemSourceKind::DefaultedMethod(TraitImplSource::Normal, name),
1010                                self.monomorphize(),
1011                            ),
1012                            _ => unreachable!(),
1013                        };
1014                        self.register_no_enqueue(item_span, &method_src)
1015                    };
1016
1017                    // Register this method.
1018                    self.register_method_impl(trait_id, name, method_id);
1019                    // By default we only enqueue required methods (those that don't have a default
1020                    // impl). If the impl is transparent, we enqueue all the implemented methods.
1021                    if matches!(impl_item.value, Provided { .. })
1022                        && item_meta.opacity.is_transparent()
1023                    {
1024                        self.mark_method_as_used(trait_id, name);
1025                    }
1026
1027                    let binder_kind = BinderKind::TraitMethod(trait_id, name);
1028                    let bound_fn_ref = match &impl_item.value {
1029                        Provided { .. } => self.translate_binder_for_def(
1030                            item_span,
1031                            binder_kind,
1032                            &item_def,
1033                            |ctx| {
1034                                let generics = ctx
1035                                    .outermost_generics()
1036                                    .identity_args_at_depth(DeBruijnId::one())
1037                                    .concat(
1038                                        &ctx.innermost_generics()
1039                                            .identity_args_at_depth(DeBruijnId::zero()),
1040                                    );
1041                                Ok(FunDeclRef {
1042                                    id: method_id,
1043                                    generics: Box::new(generics),
1044                                })
1045                            },
1046                        )?,
1047                        DefaultedFn { .. } => {
1048                            // Retrieve the method generics from the trait decl.
1049                            let decl_methods =
1050                                match self.get_or_translate(implemented_trait.id.into()) {
1051                                    Ok(ItemRef::TraitDecl(tdecl)) => tdecl.methods.as_slice(),
1052                                    _ => &[],
1053                                };
1054                            let Some(bound_method) = decl_methods.iter().find(|m| m.name() == name)
1055                            else {
1056                                continue;
1057                            };
1058                            let method_params = bound_method
1059                                .clone()
1060                                .substitute_with_tref(&self_predicate)
1061                                .params;
1062
1063                            let generics = self
1064                                .outermost_generics()
1065                                .identity_args_at_depth(DeBruijnId::one())
1066                                .concat(&method_params.identity_args_at_depth(DeBruijnId::zero()));
1067                            let fn_ref = FunDeclRef {
1068                                id: method_id,
1069                                generics: Box::new(generics),
1070                            };
1071                            Binder::new(binder_kind, method_params, fn_ref)
1072                        }
1073                        _ => unreachable!(),
1074                    };
1075
1076                    // We insert the `Binder<FunDeclRef>` unconditionally here; we'll remove the
1077                    // ones that correspond to unused methods at the end of translation.
1078                    methods.push((name, bound_fn_ref));
1079                }
1080                hax::FullDefKind::AssocConst { .. } => {
1081                    let id = self.register_and_enqueue(item_span, item_src);
1082                    // The parameters of the constant are the same as those of the item that
1083                    // declares them.
1084                    let generics = match &impl_item.value {
1085                        Provided { .. } => self.the_only_binder().params.identity_args(),
1086                        _ => {
1087                            let mut generics = implemented_trait.generics.as_ref().clone();
1088                            // For default consts, we add an extra `Self` predicate.
1089                            if !self.monomorphize() {
1090                                generics.trait_refs.push(self_predicate.clone());
1091                            }
1092                            generics
1093                        }
1094                    };
1095                    let gref = GlobalDeclRef {
1096                        id,
1097                        generics: Box::new(generics),
1098                    };
1099                    consts.push((name, gref));
1100                }
1101                // Monomorphic traits have no associated types.
1102                hax::FullDefKind::AssocTy { .. } if self.monomorphize() => continue,
1103                hax::FullDefKind::AssocTy { value, .. } => {
1104                    let binder_kind = BinderKind::TraitType(trait_id, name.clone());
1105                    let assoc_ty =
1106                        self.translate_binder_for_def(item_span, binder_kind, &item_def, |ctx| {
1107                            let ty = match &impl_item.value {
1108                                Provided { .. } => {
1109                                    ctx.translate_ty(item_span, value.as_ref().unwrap())?
1110                                }
1111                                DefaultedTy { ty: Some(ty), .. } => {
1112                                    ctx.translate_ty(item_span, ty)?
1113                                }
1114                                DefaultedTy { ty: None, .. } => {
1115                                    // Retrieve the type from the trait decl.
1116                                    let decl_types =
1117                                        match ctx.get_or_translate(implemented_trait.id.into()) {
1118                                            Ok(ItemRef::TraitDecl(tdecl)) => tdecl.types.as_slice(),
1119                                            _ => &[],
1120                                        };
1121                                    if let Some(bound_ty) =
1122                                        decl_types.iter().find(|m| *m.name() == name)
1123                                    {
1124                                        bound_ty
1125                                            .clone()
1126                                            .substitute_with_tref(&self_predicate)
1127                                            .apply(&ctx.innermost_generics().identity_args())
1128                                            .default
1129                                            .unwrap()
1130                                    } else {
1131                                        let e = register_error!(
1132                                            ctx,
1133                                            item_span,
1134                                            "couldn't translate defaulted GAT; \
1135                                            either the corresponding trait decl caused errors \
1136                                            or it was declared opaque."
1137                                        );
1138                                        TyKind::Error(e.msg).into_ty()
1139                                    }
1140                                }
1141                                _ => unreachable!(),
1142                            };
1143                            let implied_trait_refs = ctx.translate_trait_impl_exprs(
1144                                item_span,
1145                                &impl_item.required_impl_exprs,
1146                            )?;
1147                            Ok(TraitAssocTyImpl {
1148                                value: ty,
1149                                implied_trait_refs,
1150                            })
1151                        })?;
1152                    types.push((name.clone(), assoc_ty));
1153                }
1154                _ => panic!("Unexpected definition for trait item: {item_def:?}"),
1155            }
1156        }
1157
1158        let implemented_trait_def = self.poly_hax_def(&trait_pred.trait_ref.def_id)?;
1159        if implemented_trait_def.lang_item == Some(sym::destruct) {
1160            raise_error!(
1161                self,
1162                span,
1163                "found an explicit impl of `core::marker::Destruct`, this should not happen"
1164            );
1165        }
1166
1167        Ok(TraitImpl {
1168            def_id,
1169            item_meta,
1170            impl_trait: implemented_trait,
1171            generics: self.into_generics(),
1172            implied_trait_refs,
1173            consts,
1174            types,
1175            methods,
1176            vtable,
1177        })
1178    }
1179
1180    /// Generate a blanket impl for this trait, as in:
1181    /// ```
1182    ///     trait Alias<U> = Trait<Option<U>, Item = u32> + Clone;
1183    /// ```
1184    /// becomes:
1185    /// ```
1186    ///     trait Alias<U>: Trait<Option<U>, Item = u32> + Clone {}
1187    ///     impl<U, Self: Trait<Option<U>, Item = u32> + Clone> Alias<U> for Self {}
1188    /// ```
1189    #[tracing::instrument(skip(self, item_meta, def))]
1190    pub fn translate_trait_alias_blanket_impl(
1191        mut self,
1192        def_id: TraitImplId,
1193        item_meta: ItemMeta,
1194        def: &hax::FullDef,
1195    ) -> Result<TraitImpl, Error> {
1196        let span = item_meta.span;
1197
1198        let hax::FullDefKind::TraitAlias {
1199            implied_predicates, ..
1200        } = &def.kind
1201        else {
1202            raise_error!(self, span, "Unexpected definition: {def:?}");
1203        };
1204
1205        let trait_id = self.register_item(span, def.this(), TransItemSourceKind::TraitDecl);
1206
1207        // Register the trait implied clauses as required clauses for the impl.
1208        assert!(self.innermost_generics_mut().trait_clauses.is_empty());
1209        self.register_predicates(implied_predicates, PredicateOrigin::WhereClauseOnTrait)?;
1210
1211        let mut generics = self.the_only_binder().params.identity_args();
1212        // Do the inverse operation: the trait considers the clauses as implied.
1213        let implied_trait_refs = mem::take(&mut generics.trait_refs);
1214        let implemented_trait = TraitDeclRef {
1215            id: trait_id,
1216            generics: Box::new(generics),
1217        };
1218
1219        let mut timpl = TraitImpl {
1220            def_id,
1221            item_meta,
1222            impl_trait: implemented_trait,
1223            generics: self.the_only_binder().params.clone(),
1224            implied_trait_refs,
1225            consts: Default::default(),
1226            types: Default::default(),
1227            methods: Default::default(),
1228            // TODO(dyn)
1229            vtable: None,
1230        };
1231        // We got the predicates from a trait decl, so they may refer to the virtual `Self`
1232        // clause, which doesn't exist for impls. We fix that up here.
1233        {
1234            struct FixSelfVisitor {
1235                binder_depth: DeBruijnId,
1236            }
1237            struct UnhandledSelf;
1238            impl Visitor for FixSelfVisitor {
1239                type Break = UnhandledSelf;
1240            }
1241            impl VisitorWithBinderDepth for FixSelfVisitor {
1242                fn binder_depth_mut(&mut self) -> &mut DeBruijnId {
1243                    &mut self.binder_depth
1244                }
1245            }
1246            impl VisitAstMut for FixSelfVisitor {
1247                fn visit<'a, T: AstVisitable>(&'a mut self, x: &mut T) -> ControlFlow<Self::Break> {
1248                    VisitWithBinderDepth::new(self).visit(x)
1249                }
1250                fn visit_trait_ref_kind(
1251                    &mut self,
1252                    kind: &mut TraitRefKind,
1253                ) -> ControlFlow<Self::Break> {
1254                    match kind {
1255                        TraitRefKind::SelfId => return ControlFlow::Break(UnhandledSelf),
1256                        TraitRefKind::ParentClause(sub, clause_id)
1257                            if matches!(sub.kind, TraitRefKind::SelfId) =>
1258                        {
1259                            *kind = TraitRefKind::Clause(DeBruijnVar::bound(
1260                                self.binder_depth,
1261                                *clause_id,
1262                            ))
1263                        }
1264                        _ => (),
1265                    }
1266                    self.visit_inner(kind)
1267                }
1268            }
1269            match timpl.drive_mut(&mut FixSelfVisitor {
1270                binder_depth: DeBruijnId::zero(),
1271            }) {
1272                ControlFlow::Continue(()) => {}
1273                ControlFlow::Break(UnhandledSelf) => {
1274                    register_error!(
1275                        self,
1276                        span,
1277                        "Found `Self` clause we can't handle \
1278                         in a trait alias blanket impl."
1279                    );
1280                }
1281            }
1282        };
1283
1284        Ok(timpl)
1285    }
1286
1287    /// Make a trait impl from a hax `VirtualTraitImpl`. Used for constructing fake trait impls for
1288    /// builtin types like `FnOnce`.
1289    #[tracing::instrument(skip(self, item_meta))]
1290    pub fn translate_virtual_trait_impl(
1291        &mut self,
1292        def_id: TraitImplId,
1293        item_meta: ItemMeta,
1294        vimpl: &hax::VirtualTraitImpl,
1295    ) -> Result<TraitImpl, Error> {
1296        let span = item_meta.span;
1297        let trait_def = self.hax_def(&vimpl.trait_pred.trait_ref)?;
1298        let hax::FullDefKind::Trait {
1299            items: trait_items, ..
1300        } = trait_def.kind()
1301        else {
1302            panic!()
1303        };
1304
1305        let implemented_trait = self.translate_trait_predicate(span, &vimpl.trait_pred)?;
1306        let implied_trait_refs =
1307            self.translate_trait_impl_exprs(span, &vimpl.implied_impl_exprs)?;
1308
1309        let mut types = vec![];
1310        // Monomorphic traits have no associated types.
1311        if !self.monomorphize() {
1312            let type_items = trait_items.iter().filter(|assoc| match assoc.kind {
1313                hax::AssocKind::Type { .. } => true,
1314                _ => false,
1315            });
1316            for ((ty, impl_exprs), assoc) in vimpl.types.iter().zip(type_items) {
1317                let name = self.t_ctx.translate_trait_item_name(&assoc.def_id)?;
1318                let assoc_ty = TraitAssocTyImpl {
1319                    value: self.translate_ty(span, ty)?,
1320                    implied_trait_refs: self.translate_trait_impl_exprs(span, impl_exprs)?,
1321                };
1322                let binder_kind = BinderKind::TraitType(implemented_trait.id, name.clone());
1323                types.push((name, Binder::empty(binder_kind, assoc_ty)));
1324            }
1325        }
1326
1327        let generics = self.the_only_binder().params.clone();
1328        Ok(TraitImpl {
1329            def_id,
1330            item_meta,
1331            impl_trait: implemented_trait,
1332            generics,
1333            implied_trait_refs,
1334            consts: vec![],
1335            types,
1336            methods: vec![],
1337            // TODO(dyn): generate vtable instances for builtin traits
1338            vtable: None,
1339        })
1340    }
1341
1342    /// Record that `method_id` is an implementation of the given method of the trait. If the
1343    /// method is not used anywhere yet we simply record the implementation. If the method is used
1344    /// then we enqueue it for translation.
1345    pub fn register_method_impl(
1346        &mut self,
1347        trait_id: TraitDeclId,
1348        method_name: TraitItemName,
1349        method_id: FunDeclId,
1350    ) {
1351        match self
1352            .method_status
1353            .get_or_extend_and_insert_default(trait_id)
1354            .entry(method_name)
1355            .or_default()
1356        {
1357            MethodStatus::Unused { implementors } => {
1358                implementors.insert(method_id);
1359            }
1360            MethodStatus::Used => {
1361                self.enqueue_id(method_id);
1362            }
1363        }
1364    }
1365
1366    /// Mark the method as "used", which will enqueue for translation all the implementations of
1367    /// that method.
1368    pub fn mark_method_as_used(&mut self, trait_id: TraitDeclId, method_name: TraitItemName) {
1369        let method_status = self
1370            .method_status
1371            .get_or_extend_and_insert_default(trait_id)
1372            .entry(method_name)
1373            .or_default();
1374        match method_status {
1375            MethodStatus::Unused { implementors } => {
1376                let implementors = mem::take(implementors);
1377                *method_status = MethodStatus::Used;
1378                for fun_id in implementors {
1379                    self.enqueue_id(fun_id);
1380                }
1381            }
1382            MethodStatus::Used => {}
1383        }
1384    }
1385
1386    /// In case an impl does not override a trait method, this duplicates the original trait method
1387    /// and adjusts its generics to make the corresponding impl method.
1388    #[tracing::instrument(skip(self, item_meta, def))]
1389    pub fn translate_defaulted_method(
1390        &mut self,
1391        def_id: FunDeclId,
1392        item_meta: ItemMeta,
1393        def: &hax::FullDef,
1394        impl_kind: TraitImplSource,
1395        method_name: TraitItemName,
1396    ) -> Result<FunDecl, Error> {
1397        let span = item_meta.span;
1398
1399        let hax::FullDefKind::TraitImpl { trait_pred, .. } = &def.kind else {
1400            unreachable!()
1401        };
1402
1403        // Retrieve the information about the implemented trait.
1404        let implemented_trait = self.translate_trait_ref(span, &trait_pred.trait_ref)?;
1405        // A `TraitRef` that points to this impl with the correct generics.
1406        let self_impl_ref = self.translate_trait_impl_ref(span, def.this(), impl_kind)?;
1407        let self_predicate_kind = TraitRefKind::TraitImpl(self_impl_ref.clone());
1408
1409        // Build a reference to the original declared method.
1410        let ItemRef::TraitDecl(tdecl) = self.get_or_translate(implemented_trait.id.into())? else {
1411            panic!()
1412        };
1413        let Some(bound_method) = tdecl.methods.iter().find(|m| m.name() == method_name) else {
1414            raise_error!(
1415                self,
1416                span,
1417                "Could not find a method with name \
1418                `{method_name}` in trait `{:?}`",
1419                trait_pred.trait_ref.def_id,
1420            )
1421        };
1422        let bound_fn_ref: Binder<FunDeclRef> = bound_method
1423            .clone()
1424            .substitute_with_self(&implemented_trait.generics, &self_predicate_kind)
1425            .map(|m| m.item);
1426
1427        // Now we need to create the generic params for the new method. These are the concatenation
1428        // of the impl params and the method params. We obtain that by making the two existing
1429        // binders explicit and using `binder.flatten()`.
1430        let bound_fn_ref: Binder<Binder<FunDeclRef>> = Binder {
1431            params: self.outermost_generics().clone(),
1432            skip_binder: bound_fn_ref,
1433            kind: BinderKind::Other,
1434        };
1435        let bound_fn_ref: Binder<FunDeclRef> = bound_fn_ref.flatten();
1436
1437        // Create a copy of the provided method with the new generics.
1438        let original_method_id = bound_fn_ref.skip_binder.id;
1439        let ItemRef::Fun(fun_decl) = self.get_or_translate(original_method_id.into())? else {
1440            panic!()
1441        };
1442        let mut fun_decl = fun_decl
1443            .clone()
1444            .substitute_params(bound_fn_ref.map(|x| *x.generics));
1445
1446        // Update the rest of the data.
1447        fun_decl.def_id = def_id;
1448        // We use the span of the *impl*, not the span of the default method in the
1449        // original trait declaration.
1450        fun_decl.item_meta = ItemMeta {
1451            name: item_meta.name,
1452            opacity: item_meta.opacity,
1453            is_local: item_meta.is_local,
1454            span: item_meta.span,
1455            source_text: fun_decl.item_meta.source_text,
1456            attr_info: fun_decl.item_meta.attr_info,
1457            lang_item: fun_decl.item_meta.lang_item,
1458        };
1459        fun_decl.src = if let ItemSource::TraitDecl {
1460            trait_ref,
1461            item_name,
1462            ..
1463        } = fun_decl.src
1464        {
1465            ItemSource::TraitImpl {
1466                impl_ref: self_impl_ref.clone(),
1467                trait_ref,
1468                item_name,
1469                reuses_default: true,
1470            }
1471        } else {
1472            unreachable!()
1473        };
1474        if !item_meta.opacity.is_transparent() {
1475            fun_decl.body = Body::Opaque;
1476        }
1477
1478        Ok(fun_decl)
1479    }
1480}