Skip to main content

charon_lib/export/
multi_target.rs

1//! Merging multiple [`CrateData`]s from different compilation targets into one.
2use std::cell::RefCell;
3use std::collections::{HashMap, HashSet};
4use std::fmt::Debug;
5use std::mem;
6
7use itertools::Itertools;
8use petgraph::prelude::DiGraphMap;
9use petgraph::visit::{Dfs, Walker};
10
11use crate::errors::ErrorCtx;
12use crate::ids::IndexVec;
13use crate::options::TranslateOptions;
14use crate::transform::TransformCtx;
15use crate::transform::ctx::TransformPass;
16use crate::{ast::*, options::CliOpts};
17
18use super::{CharonVersion, CrateData};
19
20/// Merge per-target [`CrateData`]s into a single [`CrateData`].
21pub fn merge(options: CliOpts, krates: Vec<CrateData>) -> CrateData {
22    let mut error_ctx = ErrorCtx::new();
23    let tr_options = TranslateOptions::new(&mut error_ctx, &options);
24
25    let mut merged = CrateMerger::process(krates);
26
27    ItemDeduplicator::dedup(&mut merged.translated, &mut error_ctx);
28
29    let mut ctx = TransformCtx {
30        options: tr_options,
31        translated: merged.translated,
32        errors: RefCell::new(error_ctx),
33    };
34    cleanup_post_merge(&mut ctx);
35    merged.translated = ctx.translated;
36    merged.translated.preset = options.preset;
37
38    merged
39}
40
41// =============================================================================================
42// Step 1: Merge a set of crates into one, remembering the source target in the names.
43// =============================================================================================
44
45struct CrateMerger {
46    merged: CrateData,
47    file_name_to_id: HashMap<FileName, FileId>,
48}
49
50impl CrateMerger {
51    fn process(krates: Vec<CrateData>) -> CrateData {
52        let translated = TranslatedCrate::default();
53        let mut merger = CrateMerger {
54            merged: CrateData {
55                charon_version: CharonVersion(crate::VERSION.to_owned()),
56                translated,
57                has_errors: false,
58            },
59            file_name_to_id: HashMap::new(),
60        };
61        for krate in krates {
62            merger.add_one(krate);
63        }
64
65        merger.merged
66    }
67
68    fn add_one(&mut self, krate: CrateData) {
69        let CrateData {
70            charon_version: _, // Checked by deserialization already
71            translated: mut krate,
72            has_errors,
73        } = krate;
74        self.merged.has_errors |= has_errors;
75        let target = krate
76            .target_information
77            .keys()
78            .exactly_one()
79            .ok()
80            .unwrap()
81            .clone();
82
83        // Remap all ids inside `krate`.
84        krate.drive_mut(&mut {
85            let file_id_map = krate.files.map_ref(|file| {
86                if let Some(&existing_id) = self.file_name_to_id.get(&file.name) {
87                    existing_id
88                } else {
89                    let new_id = self.merged.translated.files.push_with(|new_id| {
90                        let mut file = file.clone();
91                        file.id = new_id;
92                        file
93                    });
94                    self.file_name_to_id.insert(file.name.clone(), new_id);
95                    new_id
96                }
97            });
98
99            #[derive(Visitor)]
100            struct RemapIdsVisitor {
101                target: TargetTriple,
102                file_id_map: IndexVec<FileId, FileId>,
103                type_offset: usize,
104                fun_offset: usize,
105                global_offset: usize,
106                trait_decl_offset: usize,
107                trait_impl_offset: usize,
108            }
109
110            impl VisitAstMut for RemapIdsVisitor {
111                fn enter_file_id(&mut self, id: &mut FileId) {
112                    *id = self.file_id_map[*id];
113                }
114                fn enter_type_decl_id(&mut self, id: &mut TypeDeclId) {
115                    *id += self.type_offset;
116                }
117                fn enter_fun_decl_id(&mut self, id: &mut FunDeclId) {
118                    *id += self.fun_offset;
119                }
120                fn enter_global_decl_id(&mut self, id: &mut GlobalDeclId) {
121                    *id += self.global_offset;
122                }
123                fn enter_trait_decl_id(&mut self, id: &mut TraitDeclId) {
124                    *id += self.trait_decl_offset;
125                }
126                fn enter_trait_impl_id(&mut self, id: &mut TraitImplId) {
127                    *id += self.trait_impl_offset;
128                }
129                fn enter_name(&mut self, name: &mut Name) {
130                    name.name.push(PathElem::Target(self.target.clone()));
131                }
132            }
133
134            RemapIdsVisitor {
135                target,
136                file_id_map,
137                type_offset: self.merged.translated.type_decls.slot_count(),
138                fun_offset: self.merged.translated.fun_decls.slot_count(),
139                global_offset: self.merged.translated.global_decls.slot_count(),
140                trait_decl_offset: self.merged.translated.trait_decls.slot_count(),
141                trait_impl_offset: self.merged.translated.trait_impls.slot_count(),
142            }
143        });
144
145        let TranslatedCrate {
146            crate_name,
147            preset: _, // The preset is shared by all targets
148            target_information,
149            runtime_checks,
150            item_names,
151            assoc_item_names,
152            short_names: _, // TODO
153            files: _,       // Done above
154            type_decls,
155            fun_decls,
156            global_decls,
157            trait_decls,
158            trait_impls,
159            ordered_decls: _, // Recomputed on the merged crate
160        } = krate;
161        if self.merged.translated.crate_name.is_empty() {
162            self.merged.translated.crate_name = crate_name;
163            self.merged.translated.runtime_checks = runtime_checks;
164        } else {
165            assert_eq!(
166                self.merged.translated.runtime_checks, runtime_checks,
167                "cannot merge crates with different runtime-check settings"
168            );
169        }
170        self.merged
171            .translated
172            .target_information
173            .extend(target_information);
174        self.merged.translated.item_names.extend(item_names);
175        self.merged
176            .translated
177            .assoc_item_names
178            .extend_from_other(assoc_item_names);
179        self.merged
180            .translated
181            .type_decls
182            .extend_from_other(type_decls);
183        self.merged
184            .translated
185            .fun_decls
186            .extend_from_other(fun_decls);
187        self.merged
188            .translated
189            .global_decls
190            .extend_from_other(global_decls);
191        self.merged
192            .translated
193            .trait_decls
194            .extend_from_other(trait_decls);
195        self.merged
196            .translated
197            .trait_impls
198            .extend_from_other(trait_impls);
199    }
200}
201
202// =============================================================================================
203// Step 2: Deduplicates items that don't differ across targets and create façades for
204// target-dependent functions
205// =============================================================================================
206
207generate_index_type!(TargetGroupId, "TargetGroup");
208
209/// A set of items that share the same base name and item kind.
210/// These are candidates for merging into a single cross-target item.
211struct TargetGroup {
212    ids: SeqHashMap<TargetTriple, ItemId>,
213}
214
215/// How a `TargetGroup` should be merged.
216#[derive(Debug, Copy, Clone, PartialEq, Eq)]
217enum MergeDecision {
218    /// Don't merge this group.
219    Skip,
220    /// All the items are the same; merge them into one.
221    Dedup,
222    /// Function signatures match but bodies diffe; create a façade that dispatches to the
223    /// per-target items.
224    Facade,
225}
226
227/// Compares items modulo the target-specific differences we want to ignore.
228struct ItemComparer<'a> {
229    remap: &'a HashMap<ItemId, ItemId>,
230}
231
232impl Visitor for ItemComparer<'_> {
233    type Break = ();
234}
235
236impl<'a, T: AstVisitable> derive_generic_visitor::VisitTwo<'a, T> for ItemComparer<'_> {
237    fn visit(&mut self, left: &'a T, right: &'a T) -> ControlFlow<Self::Break> {
238        ZipAst::visit(self, left, right)
239    }
240}
241
242impl ItemComparer<'_> {
243    fn compare_items(&mut self, left: ItemRef<'_>, right: ItemRef<'_>) -> ControlFlow<()> {
244        left.drive_two(&right, self)
245    }
246
247    fn compare_fun_interface(&mut self, left: &FunDecl, right: &FunDecl) -> ControlFlow<()> {
248        self.visit(&left.item_meta.name, &right.item_meta.name)?;
249        self.visit(&left.generics, &right.generics)?;
250        self.visit(&left.signature, &right.signature)
251    }
252
253    fn compare_ids<Id: Copy + Into<ItemId>>(&self, left: &Id, right: &Id) -> ControlFlow<()> {
254        let remap = |id: &Id| {
255            let id = (*id).into();
256            self.remap.get(&id).copied().unwrap_or(id)
257        };
258        if remap(left) == remap(right) {
259            ControlFlow::Continue(())
260        } else {
261            ControlFlow::Break(())
262        }
263    }
264
265    fn compare_iters<'a, T: AstVisitable + 'a>(
266        &mut self,
267        left: impl Iterator<Item = &'a T>,
268        right: impl Iterator<Item = &'a T>,
269    ) -> ControlFlow<()> {
270        derive_generic_visitor::drive_iter_two(left, right, self)
271    }
272}
273
274// Use lockstep visitation for "equality modulo" comparison.
275impl ZipAst for ItemComparer<'_> {
276    fn visit_type_decl_id(
277        &mut self,
278        left: &TypeDeclId,
279        right: &TypeDeclId,
280    ) -> ControlFlow<Self::Break> {
281        self.compare_ids(left, right)
282    }
283
284    fn visit_fun_decl_id(
285        &mut self,
286        left: &FunDeclId,
287        right: &FunDeclId,
288    ) -> ControlFlow<Self::Break> {
289        self.compare_ids(left, right)
290    }
291
292    fn visit_global_decl_id(
293        &mut self,
294        left: &GlobalDeclId,
295        right: &GlobalDeclId,
296    ) -> ControlFlow<Self::Break> {
297        self.compare_ids(left, right)
298    }
299
300    fn visit_trait_decl_id(
301        &mut self,
302        left: &TraitDeclId,
303        right: &TraitDeclId,
304    ) -> ControlFlow<Self::Break> {
305        self.compare_ids(left, right)
306    }
307
308    fn visit_trait_impl_id(
309        &mut self,
310        left: &TraitImplId,
311        right: &TraitImplId,
312    ) -> ControlFlow<Self::Break> {
313        self.compare_ids(left, right)
314    }
315
316    fn visit_name(&mut self, left: &Name, right: &Name) -> ControlFlow<Self::Break> {
317        let without_target = |elem: &&PathElem| !matches!(elem, PathElem::Target(_));
318        self.compare_iters(
319            left.name.iter().filter(without_target),
320            right.name.iter().filter(without_target),
321        )
322    }
323
324    fn visit_span(&mut self, _left: &Span, _right: &Span) -> ControlFlow<Self::Break> {
325        ControlFlow::Continue(())
326    }
327
328    fn visit_attr_info(&mut self, left: &AttrInfo, right: &AttrInfo) -> ControlFlow<Self::Break> {
329        let AttrInfo {
330            attributes: left_attributes,
331            inline: left_inline,
332            rename: left_rename,
333            public: left_public,
334        } = left;
335        let AttrInfo {
336            attributes: right_attributes,
337            inline: right_inline,
338            rename: right_rename,
339            public: right_public,
340        } = right;
341
342        let is_stable = |attr: &&Attribute| !matches!(attr, Attribute::Unknown(attr) if attr.path.starts_with("rustc_"));
343        self.compare_iters(
344            left_attributes.iter().filter(is_stable),
345            right_attributes.iter().filter(is_stable),
346        )?;
347        self.visit(left_inline, right_inline)?;
348        self.visit(left_rename, right_rename)?;
349        self.visit(left_public, right_public)
350    }
351
352    fn visit_item_meta(&mut self, left: &ItemMeta, right: &ItemMeta) -> ControlFlow<Self::Break> {
353        let ItemMeta {
354            name: left_name,
355            span: left_span,
356            // Source text isn't relevant to cross-target identity.
357            source_text: _,
358            attr_info: left_attr_info,
359            is_local: left_is_local,
360            started_from: left_started_from,
361            is_extern: left_is_extern,
362            opacity: left_opacity,
363            lang_item: left_lang_item,
364            diagnostic_item: left_diagnostic_item,
365            has_errors: left_has_errors,
366        } = left;
367        let ItemMeta {
368            name: right_name,
369            span: right_span,
370            source_text: _,
371            attr_info: right_attr_info,
372            is_local: right_is_local,
373            started_from: right_started_from,
374            is_extern: right_is_extern,
375            opacity: right_opacity,
376            lang_item: right_lang_item,
377            diagnostic_item: right_diagnostic_item,
378            has_errors: right_has_errors,
379        } = right;
380
381        self.visit(left_name, right_name)?;
382        self.visit(left_span, right_span)?;
383        self.visit(left_attr_info, right_attr_info)?;
384        self.visit(left_is_local, right_is_local)?;
385        self.visit(left_started_from, right_started_from)?;
386        self.visit(left_is_extern, right_is_extern)?;
387        self.visit(left_opacity, right_opacity)?;
388        self.visit(left_lang_item, right_lang_item)?;
389        self.visit(left_diagnostic_item, right_diagnostic_item)?;
390        self.visit(left_has_errors, right_has_errors)?;
391        ControlFlow::Continue(())
392    }
393
394    fn visit_type_decl(&mut self, left: &TypeDecl, right: &TypeDecl) -> ControlFlow<Self::Break> {
395        let TypeDecl {
396            def_id: left_def_id,
397            item_meta: left_item_meta,
398            generics: left_generics,
399            src: left_src,
400            kind: left_kind,
401            // Layouts are allowed to differ per target.
402            layout: _,
403            monomorphic_layouts: _,
404            ptr_metadata: left_ptr_metadata,
405            marker_traits: left_marker_traits,
406        } = left;
407        let TypeDecl {
408            def_id: right_def_id,
409            item_meta: right_item_meta,
410            generics: right_generics,
411            src: right_src,
412            kind: right_kind,
413            layout: _,
414            monomorphic_layouts: _,
415            ptr_metadata: right_ptr_metadata,
416            marker_traits: right_marker_traits,
417        } = right;
418
419        self.visit(left_def_id, right_def_id)?;
420        self.visit(left_item_meta, right_item_meta)?;
421        self.visit(left_generics, right_generics)?;
422        self.visit(left_src, right_src)?;
423        self.visit(left_kind, right_kind)?;
424        self.visit(left_ptr_metadata, right_ptr_metadata)?;
425        self.visit(left_marker_traits, right_marker_traits)
426    }
427}
428
429impl TargetGroup {
430    /// Deterministically chosen representative id.
431    fn canonical_id(&self) -> ItemId {
432        self.ids.values().next().copied().unwrap()
433    }
434
435    /// Whether this group is a group of function items.
436    fn is_function_group(&self) -> bool {
437        self.canonical_id().is_fun()
438    }
439
440    /// Compare the items of this group under the provided id mapping.
441    fn decide_merge(
442        &self,
443        krate: &TranslatedCrate,
444        remap: &HashMap<ItemId, ItemId>,
445    ) -> MergeDecision {
446        let items: Vec<Option<ItemRef<'_>>> = self
447            .ids
448            .values()
449            .map(|&id| krate.get_item(id))
450            .collect_vec();
451
452        // Items that don't exist in the crate can't be compared; if they're all missing we can
453        // still merge them tho.
454        if items.iter().all(|i| i.is_none()) {
455            return MergeDecision::Dedup;
456        }
457        let items: Vec<_> = match items.into_iter().collect::<Option<Vec<_>>>() {
458            Some(items) => items,
459            None => return MergeDecision::Skip,
460        };
461
462        let mut comparer = ItemComparer { remap };
463        if items
464            .iter()
465            .tuple_windows()
466            .all(|(&left, &right)| comparer.compare_items(left, right).is_continue())
467        {
468            MergeDecision::Dedup
469        } else if self.is_function_group()
470            && items
471                .iter()
472                .map(|item| item.as_fun().unwrap())
473                .tuple_windows()
474                .all(|(left, right)| comparer.compare_fun_interface(left, right).is_continue())
475        {
476            MergeDecision::Facade
477        } else {
478            MergeDecision::Skip
479        }
480    }
481
482    /// Yields `(non_canonical_id, canonical_id)` pairs for building an ID remap.
483    fn remap_entries<'a>(&'a self) -> impl Iterator<Item = (ItemId, ItemId)> + 'a {
484        let canonical_id = self.canonical_id();
485        self.ids.values().map(move |&id| (id, canonical_id))
486    }
487    fn into_remap_entries(self) -> impl Iterator<Item = (ItemId, ItemId)> {
488        let canonical_id = self.canonical_id();
489        self.ids.into_values().map(move |id| (id, canonical_id))
490    }
491
492    /// Build a façade `FunDecl` for a group of functions with matching signatures but different
493    /// bodies.
494    fn build_facade_decl(&self, def_id: FunDeclId, krate: &TranslatedCrate) -> FunDecl {
495        let canonical_fun_id = *self.canonical_id().as_fun().unwrap();
496        let canonical = krate.fun_decls.get(canonical_fun_id).unwrap();
497
498        let dispatch_map = self
499            .ids
500            .iter()
501            .map(|(target, &id)| {
502                let fun_decl_ref = FunDeclRef {
503                    id: *id.as_fun().unwrap(),
504                    generics: Box::new(canonical.generics.identity_args()),
505                };
506                (target.clone(), fun_decl_ref)
507            })
508            .collect();
509
510        let mut item_meta = canonical.item_meta.clone();
511        // Remove the target suffix (and do a little sanity check).
512        item_meta.name.name.pop().unwrap().as_target().unwrap();
513
514        FunDecl {
515            def_id,
516            item_meta,
517            generics: canonical.generics.clone(),
518            signature: canonical.signature.clone(),
519            src: canonical.src.clone(),
520            body: Body::TargetDispatch(dispatch_map),
521        }
522    }
523}
524
525/// Normalize a name for grouping across targets; returns the target.
526fn normalize_name_for_grouping(
527    name: &Name,
528    krate: &TranslatedCrate,
529) -> Option<(Name, TargetTriple)> {
530    let (mut name, target) = name.strip_target_suffix()?;
531    for elem in &mut name.name {
532        if let PathElem::Impl(ImplElem::Trait(id)) = elem {
533            // Replace impl block references with something that contains the implemented trait
534            // predicate instead. That way, comparing names for equality compares trait predicates
535            // instead.
536            if let Some(timpl) = krate.trait_impls.get(*id) {
537                let mut params = GenericParams::default();
538                params.trait_clauses.push(TraitParam {
539                    clause_id: TraitClauseId::ZERO,
540                    span: None,
541                    origin: PredicateOrigin::WhereClauseOnImpl,
542                    trait_: RegionBinder::empty(timpl.impl_trait.clone()),
543                });
544                *elem = PathElem::Impl(ImplElem::Ty(Box::new(Binder {
545                    params,
546                    skip_binder: Ty::mk_unit(),
547                    kind: BinderKind::Other,
548                })));
549            }
550        }
551    }
552    Some((name, target))
553}
554
555/// Orchestrates deduplication of items across compilation targets.
556struct ItemDeduplicator<'a> {
557    krate: &'a mut TranslatedCrate,
558    groups: IndexVec<TargetGroupId, TargetGroup>,
559}
560
561impl<'a> ItemDeduplicator<'a> {
562    /// Entrypoint: deduplicate items that are the same across targets.
563    pub fn dedup(krate: &'a mut TranslatedCrate, errors: &mut ErrorCtx) {
564        let groups = Self::discover_groups(krate, errors);
565        if groups.is_empty() {
566            return;
567        }
568        let mut this = Self { krate, groups };
569        let decisions = this.decide_group_mergings();
570        this.apply_merge_decisions(decisions);
571    }
572
573    /// Group items by (base_name, item_kind). Each group contains the versions of that item
574    /// across all targets where it exists.
575    fn discover_groups(
576        krate: &TranslatedCrate,
577        _errors: &mut ErrorCtx,
578    ) -> IndexVec<TargetGroupId, TargetGroup> {
579        let mut groups_map: SeqHashMap<
580            (Name, std::mem::Discriminant<ItemId>),
581            SeqHashMap<TargetTriple, ItemId>,
582        > = SeqHashMap::new();
583        for (&item_id, name) in &krate.item_names {
584            if let Some((base_name, target)) = normalize_name_for_grouping(name, krate) {
585                let key = (base_name, std::mem::discriminant(&item_id));
586                let per_target = groups_map.entry(key).or_default();
587                if per_target.contains_key(&target) {
588                    // Name collision within the same target: skip this group entirely.
589                    per_target.clear();
590                } else {
591                    per_target.insert(target, item_id);
592                }
593            }
594        }
595        // We do a fixpoint: merging a group may lead to detecting that some names are actually the
596        // same (because the names refer to impls/types).
597        loop {
598            let prev_len = groups_map.len();
599            let remap: HashMap<ItemId, ItemId> = groups_map
600                .values()
601                .filter(|ids| !ids.is_empty())
602                .cloned()
603                .map(|ids| TargetGroup { ids })
604                .flat_map(|g| g.into_remap_entries())
605                .filter(|(x, y)| x != y)
606                .collect();
607            for ((mut name, kind), ids) in mem::take(&mut groups_map) {
608                name.drive_mut(&mut IdRefMapperVisitor::new(&remap));
609                let key = (name, kind);
610                let per_target = groups_map.entry(key).or_default();
611                for (target, item_id) in ids {
612                    if per_target.contains_key(&target) {
613                        // Name collision within the same target: skip this group entirely.
614                        per_target.clear();
615                        break;
616                    } else {
617                        per_target.insert(target, item_id);
618                    }
619                }
620            }
621            // Remove empty groups (from collisions) and check for convergence.
622            groups_map.retain(|_, v| !v.is_empty());
623            if prev_len == groups_map.len() {
624                break;
625            }
626        }
627        let groups: IndexVec<TargetGroupId, TargetGroup> = groups_map
628            .into_values()
629            .map(|ids| TargetGroup { ids })
630            .collect();
631        groups
632    }
633
634    /// Decide how to merge each group. Skipped groups are not included in the output.
635    fn decide_group_mergings(&self) -> Vec<(TargetGroupId, MergeDecision)> {
636        // Start with all groups as candidates.
637        let mut candidates: Vec<(TargetGroupId, MergeDecision)> = self
638            .groups
639            .indices()
640            .map(|id| (id, MergeDecision::Skip))
641            .collect();
642
643        // Fixpoint: assume that all included groups are mapped to a single item; keep the groups
644        // that can be merged under such a mapping. Iterate until fixpoint.
645        loop {
646            let remap = self.build_remap(candidates.iter().map(|(id, _)| id));
647            let prev_len = candidates.len();
648            candidates.retain_mut(|(idx, decision)| {
649                *decision = self.groups[*idx].decide_merge(self.krate, &remap);
650                *decision != MergeDecision::Skip
651            });
652            if candidates.len() == prev_len {
653                break;
654            }
655        }
656
657        candidates
658    }
659
660    /// Build an id remap: for each candidate group, map non-canonical IDs → canonical ID.
661    fn build_remap<'b>(
662        &self,
663        candidate_indices: impl IntoIterator<Item = &'b TargetGroupId>,
664    ) -> HashMap<ItemId, ItemId> {
665        candidate_indices
666            .into_iter()
667            .flat_map(|&idx| self.groups[idx].remap_entries())
668            .filter(|(x, y)| x != y)
669            .collect()
670    }
671
672    fn apply_merge_decisions(&mut self, decisions: Vec<(TargetGroupId, MergeDecision)>) {
673        if decisions.is_empty() {
674            return;
675        }
676
677        let mut remap = HashMap::new();
678        let mut facade_decls: Vec<FunDecl> = Vec::new();
679        for &(idx, decision) in &decisions {
680            let group = &self.groups[idx];
681            let target_id = match decision {
682                MergeDecision::Skip => unreachable!(),
683                MergeDecision::Dedup => {
684                    let canonical_id = group.canonical_id();
685                    self.dedup_group(idx);
686                    canonical_id
687                }
688                MergeDecision::Facade => {
689                    let facade_id = self.krate.fun_decls.reserve_slot();
690                    // Insert facade decls later because the id remapping would mess up the
691                    // dispatch maps.
692                    facade_decls.push(group.build_facade_decl(facade_id, self.krate));
693                    // Mark per-target functions as target-dependent.
694                    for &id in group.ids.values() {
695                        let fun_id = *id.as_fun().unwrap();
696                        if let Some(fun_decl) = self.krate.fun_decls.get_mut(fun_id) {
697                            fun_decl.src = FunSource::TargetDependent {
698                                dispatcher: FunDeclRef {
699                                    id: facade_id,
700                                    generics: Box::new(fun_decl.generics.identity_args()),
701                                },
702                            };
703                        }
704                    }
705                    ItemId::Fun(facade_id)
706                }
707            };
708            let group = &self.groups[idx];
709            for &id in group.ids.values() {
710                if id != target_id {
711                    remap.insert(id, target_id);
712                }
713            }
714        }
715
716        // Remap all ids.
717        self.krate.drive_mut(&mut IdRefMapperVisitor::new(&remap));
718
719        for decl in facade_decls {
720            self.krate
721                .set_new_item_slot(ItemId::Fun(decl.def_id), ItemByVal::Fun(decl));
722        }
723    }
724
725    fn dedup_group(&mut self, idx: TargetGroupId) {
726        let group = &self.groups[idx];
727        let canonical = group.canonical_id();
728
729        // Remove the target suffix (and do a little sanity check).
730        let mut name = self.krate.item_names.get(&canonical).cloned().unwrap();
731        name.name.pop().unwrap().as_target().unwrap();
732        if let Some(mut canonical_item) = self.krate.get_item_mut(canonical) {
733            canonical_item.item_meta().name = name.clone();
734        }
735        self.krate.item_names.insert(canonical, name);
736
737        // Merge per-target layouts into the canonical type.
738        if let ItemId::Type(canonical_type_id) = canonical {
739            let mut layouts = TargetLayouts::default();
740            let mut mono_layouts: SeqHashMap<GenericArgs, TargetLayouts> = SeqHashMap::new();
741            for &id in group.ids.values() {
742                if let Some(tdecl) = self.krate.type_decls.get_mut(*id.as_type().unwrap()) {
743                    layouts.extend(mem::take(&mut tdecl.layout.0));
744                    for (args, layouts) in mem::take(&mut tdecl.monomorphic_layouts) {
745                        mono_layouts.entry(args).or_default().extend(layouts.0);
746                    }
747                }
748            }
749            if let Some(dest) = self.krate.type_decls.get_mut(canonical_type_id) {
750                dest.layout = layouts;
751                dest.monomorphic_layouts = mono_layouts;
752            }
753        }
754
755        // Remove non-canonical copies.
756        for &id in group.ids.values() {
757            if id != canonical {
758                self.krate.remove_item(id);
759            }
760        }
761    }
762}
763
764// =============================================================================================
765// Step 3: Cleanup the merged crate
766// =============================================================================================
767
768/// Recompute declaration order and run final whole-crate cleanup on the merged crate.
769fn cleanup_post_merge(ctx: &mut TransformCtx) {
770    if !ctx.options.translate_all_methods {
771        remove_unmentioned_methods(&mut ctx.translated);
772    }
773    crate::transform::add_missing_info::reorder_decls::Transform.transform_ctx(ctx);
774    if ctx.options.unbind_item_vars {
775        crate::transform::simplify_output::unbind_item_vars::Check.transform_ctx(ctx);
776    }
777}
778
779/// Emulate the behavior of our lazy method translation scheme by removing default trait methods
780/// that aren't usefully mentioned anywhere.
781fn remove_unmentioned_methods(krate: &mut TranslatedCrate) {
782    type MethodKey = (TraitDeclId, TraitMethodId);
783
784    use ReachabilityNode::*;
785    #[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
786    enum ReachabilityNode {
787        Root,
788        Method(MethodKey),
789        Fun(FunDeclId),
790    }
791
792    #[derive(Visitor)]
793    struct MentionedFunVisitor<F>(F);
794
795    impl<F> VisitAst for MentionedFunVisitor<F>
796    where
797        F: FnMut(ReachabilityNode),
798    {
799        fn enter_fun_decl_id(&mut self, id: &FunDeclId) {
800            (self.0)(Fun(*id));
801        }
802
803        fn enter_fn_ptr(&mut self, fn_ptr: &FnPtr) {
804            if let FnPtrKind::Trait(trait_ref, method_id) = fn_ptr.kind.as_ref() {
805                (self.0)(Method((trait_ref.trait_id(), *method_id)));
806            }
807        }
808    }
809
810    // Build a graph where the items we want to keep are reachable from the root. To start with
811    // that's all the `FunDeclId`s that aren't a method (or a target-dispatch target coming from a
812    // method), as well as all the methods without default. We end up with a graph where methods
813    // with a default may end up not reachable.
814    let graph = {
815        let mut graph: DiGraphMap<ReachabilityNode, ()> = DiGraphMap::new();
816        graph.add_node(Root);
817
818        for (fun_id, fun) in krate.fun_decls.iter_indexed() {
819            let fun_node = Fun(fun_id);
820            graph.add_node(fun_node);
821
822            if let FunSource::TraitDefault {
823                trait_ref, item_id, ..
824            }
825            | FunSource::TraitImpl {
826                trait_ref, item_id, ..
827            } = &fun.src
828            {
829                let method_key = (trait_ref.id, *item_id);
830                // The method node is reachable iff any of the corresponding function nodes is.
831                graph.add_edge(Method(method_key), fun_node, ());
832                graph.add_edge(fun_node, Method(method_key), ());
833            }
834
835            match &fun.src {
836                FunSource::TraitDefault { .. }
837                | FunSource::TraitImpl { .. }
838                | FunSource::TargetDependent { .. } => {}
839                // Functions that aren't any of the above are reachable. target-dependent functions
840                // will be reachable if their dispatcher is.
841                _ => {
842                    graph.add_edge(Root, fun_node, ());
843                }
844            }
845
846            let _ = fun.body.drive(&mut MentionedFunVisitor(|n| {
847                graph.add_edge(fun_node, n, ());
848            }));
849        }
850
851        for trait_decl in krate.trait_decls.iter() {
852            for (method_id, method) in trait_decl.methods.iter_enumerated() {
853                if method.skip_binder.default.is_none() {
854                    graph.add_edge(Root, Method((trait_decl.def_id, method_id)), ());
855                }
856            }
857        }
858
859        graph
860    };
861
862    let reachable_nodes: HashSet<_> = Dfs::new(&graph, Root).iter(&graph).collect();
863
864    let mut unused_methods: HashMap<TraitDeclId, HashSet<TraitMethodId>> = HashMap::new();
865    // Iterate over unreachable nodes.
866    for n in graph.nodes().filter(|n| !reachable_nodes.contains(n)) {
867        match n {
868            Root => {}
869            Method((trait_id, method_id)) => {
870                unused_methods
871                    .entry(trait_id)
872                    .or_default()
873                    .insert(method_id);
874            }
875            Fun(fun_id) => {
876                // Remove unreachable functions.
877                krate.remove_item(ItemId::Fun(fun_id));
878            }
879        }
880    }
881    if unused_methods.is_empty() {
882        return;
883    }
884
885    // Remove unreachable methods from both decls and impls.
886    for trait_impl in krate.trait_impls.iter_mut() {
887        let trait_id = trait_impl.impl_trait.id;
888        if let Some(unused_methods) = unused_methods.get(&trait_id) {
889            trait_impl
890                .methods
891                .retain(|method_id, _| !unused_methods.contains(&method_id));
892        }
893    }
894    for (trait_id, unused_methods) in unused_methods {
895        if let Some(trait_decl) = krate.trait_decls.get_mut(trait_id) {
896            trait_decl
897                .methods
898                .retain(|method_id, _| !unused_methods.contains(&method_id));
899        }
900    }
901}
902
903// =============================================================================================
904// Utilities
905// =============================================================================================
906
907/// Visitor that remaps references to the given items.
908#[derive(Visitor)]
909struct IdRefMapperVisitor<'a> {
910    map: &'a HashMap<ItemId, ItemId>,
911}
912
913impl<'a> IdRefMapperVisitor<'a> {
914    fn new(remap: &'a HashMap<ItemId, ItemId>) -> Self {
915        Self { map: remap }
916    }
917
918    fn map<Id>(&self, id: &mut Id)
919    where
920        Id: Copy,
921        Id: Into<ItemId>,
922        ItemId: TryInto<Id, Error: Debug>,
923    {
924        if let Some(&new) = self.map.get(&(*id).into()) {
925            *id = new.try_into().unwrap();
926        }
927    }
928}
929
930impl VisitAstMut for IdRefMapperVisitor<'_> {
931    fn enter_type_decl_ref(&mut self, x: &mut TypeDeclRef) {
932        self.map(&mut x.id);
933    }
934    fn enter_fun_decl_ref(&mut self, x: &mut FunDeclRef) {
935        self.map(&mut x.id);
936    }
937    fn enter_global_decl_ref(&mut self, x: &mut GlobalDeclRef) {
938        self.map(&mut x.id);
939    }
940    fn enter_trait_decl_ref(&mut self, x: &mut TraitDeclRef) {
941        self.map(&mut x.id);
942    }
943    fn enter_trait_impl_ref(&mut self, x: &mut TraitImplRef) {
944        self.map(&mut x.id);
945    }
946
947    fn enter_fn_ptr(&mut self, x: &mut FnPtr) {
948        if let FnPtrKind::Fun(id) = x.kind.as_mut() {
949            self.map(id)
950        }
951    }
952    fn enter_impl_elem(&mut self, x: &mut ImplElem) {
953        if let ImplElem::Trait(id) = x {
954            self.map(id);
955        }
956    }
957    fn enter_binder<T: AstVisitable>(&mut self, x: &mut Binder<T>) {
958        match &mut x.kind {
959            BinderKind::TraitType(trait_id, _) | BinderKind::TraitMethod(trait_id, _) => {
960                self.map(trait_id);
961            }
962            BinderKind::InherentImplBlock | BinderKind::Dyn | BinderKind::Other => {}
963        }
964    }
965}