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;
4use std::fmt::Debug;
5use std::mem;
6
7use itertools::Itertools;
8
9use crate::errors::ErrorCtx;
10use crate::ids::IndexVec;
11use crate::options::TranslateOptions;
12use crate::transform::TransformCtx;
13use crate::transform::ctx::TransformPass;
14use crate::{ast::*, options::CliOpts};
15
16use super::{CharonVersion, CrateData};
17
18/// Merge per-target [`CrateData`]s into a single [`CrateData`].
19pub fn merge(options: CliOpts, krates: Vec<CrateData>) -> CrateData {
20    let mut error_ctx = ErrorCtx::new();
21    let tr_options = TranslateOptions::new(&mut error_ctx, &options);
22
23    let mut merged = CrateMerger::process(options, krates);
24
25    ItemDeduplicator::dedup(&mut merged.translated, &mut error_ctx);
26
27    // Recompute declaration order on the merged crate.
28    let mut ctx = TransformCtx {
29        options: tr_options,
30        translated: merged.translated,
31        errors: RefCell::new(error_ctx),
32    };
33    crate::transform::add_missing_info::reorder_decls::Transform.transform_ctx(&mut ctx);
34    merged.translated = ctx.translated;
35
36    merged
37}
38
39// =============================================================================================
40// Step 1: Merge a set of crates into one, remembering the source target in the names.
41// =============================================================================================
42
43struct CrateMerger {
44    merged: CrateData,
45    file_name_to_id: HashMap<FileName, FileId>,
46}
47
48impl CrateMerger {
49    fn process(options: CliOpts, krates: Vec<CrateData>) -> CrateData {
50        let mut translated = TranslatedCrate::default();
51        translated.options = options;
52        let mut merger = CrateMerger {
53            merged: CrateData {
54                charon_version: CharonVersion(crate::VERSION.to_owned()),
55                translated,
56                has_errors: false,
57            },
58            file_name_to_id: HashMap::new(),
59        };
60        for krate in krates {
61            merger.add_one(krate);
62        }
63
64        merger.merged
65    }
66
67    fn add_one(&mut self, krate: CrateData) {
68        let CrateData {
69            charon_version: _, // Checked by deserialization already
70            translated: mut krate,
71            has_errors,
72        } = krate;
73        self.merged.has_errors |= has_errors;
74        let target = krate
75            .target_information
76            .keys()
77            .exactly_one()
78            .ok()
79            .unwrap()
80            .clone();
81
82        // Remap all ids inside `krate`.
83        krate.drive_mut(&mut {
84            let file_id_map = krate.files.map_ref(|file| {
85                if let Some(&existing_id) = self.file_name_to_id.get(&file.name) {
86                    existing_id
87                } else {
88                    let new_id = self.merged.translated.files.push(file.clone());
89                    self.file_name_to_id.insert(file.name.clone(), new_id);
90                    new_id
91                }
92            });
93
94            #[derive(Visitor)]
95            struct RemapIdsVisitor {
96                target: TargetTriple,
97                file_id_map: IndexVec<FileId, FileId>,
98                type_offset: usize,
99                fun_offset: usize,
100                global_offset: usize,
101                trait_decl_offset: usize,
102                trait_impl_offset: usize,
103            }
104
105            impl VisitAstMut for RemapIdsVisitor {
106                fn enter_file_id(&mut self, id: &mut FileId) {
107                    *id = self.file_id_map[*id];
108                }
109                fn enter_type_decl_id(&mut self, id: &mut TypeDeclId) {
110                    *id += self.type_offset;
111                }
112                fn enter_fun_decl_id(&mut self, id: &mut FunDeclId) {
113                    *id += self.fun_offset;
114                }
115                fn enter_global_decl_id(&mut self, id: &mut GlobalDeclId) {
116                    *id += self.global_offset;
117                }
118                fn enter_trait_decl_id(&mut self, id: &mut TraitDeclId) {
119                    *id += self.trait_decl_offset;
120                }
121                fn enter_trait_impl_id(&mut self, id: &mut TraitImplId) {
122                    *id += self.trait_impl_offset;
123                }
124                fn enter_name(&mut self, name: &mut Name) {
125                    name.name.push(PathElem::Target(self.target.clone()));
126                }
127            }
128
129            RemapIdsVisitor {
130                target,
131                file_id_map,
132                type_offset: self.merged.translated.type_decls.slot_count(),
133                fun_offset: self.merged.translated.fun_decls.slot_count(),
134                global_offset: self.merged.translated.global_decls.slot_count(),
135                trait_decl_offset: self.merged.translated.trait_decls.slot_count(),
136                trait_impl_offset: self.merged.translated.trait_impls.slot_count(),
137            }
138        });
139
140        let TranslatedCrate {
141            crate_name,
142            options: _, // We discard the per-target options we made
143            target_information,
144            item_names,
145            short_names: _, // TODO
146            files: _,       // Done above
147            type_decls,
148            fun_decls,
149            global_decls,
150            trait_decls,
151            trait_impls,
152            unit_metadata,
153            ordered_decls: _, // Recomputed on the merged crate
154        } = krate;
155        if self.merged.translated.crate_name.is_empty() {
156            self.merged.translated.crate_name = crate_name;
157        }
158        self.merged
159            .translated
160            .target_information
161            .extend(target_information);
162        self.merged.translated.item_names.extend(item_names);
163        self.merged
164            .translated
165            .type_decls
166            .extend_from_other(type_decls);
167        self.merged
168            .translated
169            .fun_decls
170            .extend_from_other(fun_decls);
171        self.merged
172            .translated
173            .global_decls
174            .extend_from_other(global_decls);
175        self.merged
176            .translated
177            .trait_decls
178            .extend_from_other(trait_decls);
179        self.merged
180            .translated
181            .trait_impls
182            .extend_from_other(trait_impls);
183        if self.merged.translated.unit_metadata.is_none() {
184            self.merged.translated.unit_metadata = unit_metadata;
185        }
186    }
187}
188
189// =============================================================================================
190// Step 2: Deduplicates items that don't differ across targets and create façades for
191// target-dependent functions
192// =============================================================================================
193
194generate_index_type!(TargetGroupId, "TargetGroup");
195
196/// A set of items that share the same base name and item kind.
197/// These are candidates for merging into a single cross-target item.
198struct TargetGroup {
199    ids: SeqHashMap<TargetTriple, ItemId>,
200}
201
202/// How a `TargetGroup` should be merged.
203#[derive(Debug, Clone, Copy, PartialEq, Eq)]
204enum MergeDecision {
205    /// Don't merge this group.
206    Skip,
207    /// All the items are the same; merge them into one.
208    Dedup,
209    /// Function signatures match but bodies diffe; create a façade that dispatches to the
210    /// per-target items.
211    Facade,
212}
213
214impl TargetGroup {
215    /// Deterministically chosen representative id.
216    fn canonical_id(&self) -> ItemId {
217        self.ids.values().next().copied().unwrap()
218    }
219
220    /// Whether this group is a group of function items.
221    fn is_function_group(&self) -> bool {
222        self.canonical_id().is_fun()
223    }
224
225    /// Compare the items of this group under the provided id mapping.
226    fn decide_merge(
227        &self,
228        krate: &TranslatedCrate,
229        remap: &HashMap<ItemId, ItemId>,
230    ) -> MergeDecision {
231        let canonical_id = self.canonical_id();
232        let items: Vec<Option<ItemByVal>> = self
233            .ids
234            .values()
235            .map(|&id| {
236                krate
237                    .get_item(id)
238                    .map(|item| normalize_item(item.to_owned(), canonical_id, remap))
239            })
240            .collect_vec();
241
242        // Items that don't exist in the crate can't be compared; if they're all missing we can
243        // still merge them tho.
244        if items.iter().all(|i| i.is_none()) {
245            return MergeDecision::Dedup;
246        }
247        let items: Vec<_> = match items.into_iter().collect::<Option<Vec<_>>>() {
248            Some(items) => items,
249            None => return MergeDecision::Skip,
250        };
251
252        if items.iter().all_equal() {
253            MergeDecision::Dedup
254        } else if self.is_function_group()
255            && items
256                .iter()
257                .map(|item| item.as_fun().unwrap())
258                .map(|d| (&d.generics, &d.signature))
259                .all_equal()
260        {
261            MergeDecision::Facade
262        } else {
263            MergeDecision::Skip
264        }
265    }
266
267    /// Yields `(non_canonical_id, canonical_id)` pairs for building an ID remap.
268    fn remap_entries<'a>(&'a self) -> impl Iterator<Item = (ItemId, ItemId)> + 'a {
269        self.ids.values().map(|&id| (id, self.canonical_id()))
270    }
271    fn into_remap_entries(self) -> impl Iterator<Item = (ItemId, ItemId)> {
272        let canonical_id = self.canonical_id();
273        self.ids.into_values().map(move |id| (id, canonical_id))
274    }
275
276    /// Build a façade `FunDecl` for a group of functions with matching signatures but different
277    /// bodies. The `def_id` is set to a placeholder and must be fixed up on insertion.
278    fn build_facade_decl(&self, def_id: FunDeclId, krate: &TranslatedCrate) -> FunDecl {
279        let canonical_fun_id = *self.canonical_id().as_fun().unwrap();
280        let canonical = krate.fun_decls.get(canonical_fun_id).unwrap();
281
282        let dispatch_map = self
283            .ids
284            .iter()
285            .map(|(target, &id)| {
286                let fun_decl_ref = FunDeclRef {
287                    id: *id.as_fun().unwrap(),
288                    generics: Box::new(canonical.generics.identity_args()),
289                };
290                (target.clone(), fun_decl_ref)
291            })
292            .collect();
293
294        let mut item_meta = canonical.item_meta.clone();
295        // Remove the target suffix (and do a little sanity check).
296        item_meta.name.name.pop().unwrap().as_target().unwrap();
297
298        FunDecl {
299            def_id,
300            item_meta,
301            generics: canonical.generics.clone(),
302            signature: canonical.signature.clone(),
303            src: canonical.src.clone(),
304            is_global_initializer: canonical.is_global_initializer,
305            body: Body::TargetDispatch(dispatch_map),
306        }
307    }
308}
309
310/// Normalize a name for grouping across targets; returns the target.
311fn normalize_name_for_grouping(
312    name: &Name,
313    krate: &TranslatedCrate,
314) -> Option<(Name, TargetTriple)> {
315    let (mut name, target) = name.strip_target_suffix()?;
316    for elem in &mut name.name {
317        if let PathElem::Impl(ImplElem::Trait(id)) = elem {
318            // Replace ipl block references with something that contains the implemented trait
319            // predicate instead. That way, comparing names for equality compares trait predicates
320            // instead.
321            if let Some(timpl) = krate.trait_impls.get(*id) {
322                let mut params = GenericParams::default();
323                params.trait_clauses.push(TraitParam {
324                    clause_id: TraitClauseId::ZERO,
325                    span: None,
326                    origin: PredicateOrigin::WhereClauseOnImpl,
327                    trait_: RegionBinder::empty(timpl.impl_trait.clone()),
328                });
329                *elem = PathElem::Impl(ImplElem::Ty(Box::new(Binder {
330                    params,
331                    skip_binder: Ty::mk_unit(),
332                    kind: BinderKind::Other,
333                })));
334            }
335        }
336    }
337    Some((name, target))
338}
339
340/// Orchestrates deduplication of items across compilation targets.
341struct ItemDeduplicator<'a> {
342    krate: &'a mut TranslatedCrate,
343    groups: IndexVec<TargetGroupId, TargetGroup>,
344}
345
346impl<'a> ItemDeduplicator<'a> {
347    /// Entrypoint: deduplicate items that are the same across targets.
348    pub fn dedup(krate: &'a mut TranslatedCrate, errors: &mut ErrorCtx) {
349        let groups = Self::discover_groups(krate, errors);
350        if groups.is_empty() {
351            return;
352        }
353        let mut this = Self { krate, groups };
354        let decisions = this.decide_group_mergings();
355        this.apply_merge_decisions(decisions);
356    }
357
358    /// Group items by (base_name, item_kind), keeping only groups that have items in all targets.
359    fn discover_groups(
360        krate: &TranslatedCrate,
361        _errors: &mut ErrorCtx,
362    ) -> IndexVec<TargetGroupId, TargetGroup> {
363        let num_targets = krate.target_information.len();
364        let mut groups_map: SeqHashMap<
365            (Name, std::mem::Discriminant<ItemId>),
366            SeqHashMap<TargetTriple, ItemId>,
367        > = SeqHashMap::new();
368        for (&item_id, name) in &krate.item_names {
369            if let Some((base_name, target)) = normalize_name_for_grouping(name, krate) {
370                let key = (base_name, std::mem::discriminant(&item_id));
371                let per_target = groups_map.entry(key).or_default();
372                if per_target.contains_key(&target) {
373                    // Name collision within the same target: skip this group entirely.
374                    per_target.clear();
375                } else {
376                    per_target.insert(target, item_id);
377                }
378            }
379        }
380        // We do a fixpoint: merging a group may lead to detecting that some names are actually the
381        // same (because the names refer to impls/types).
382        loop {
383            let prev_len = groups_map.len();
384            let remap: HashMap<ItemId, ItemId> = groups_map
385                .values()
386                .cloned()
387                .map(|ids| TargetGroup { ids })
388                .flat_map(|g| g.into_remap_entries())
389                .filter(|(x, y)| x != y)
390                .collect();
391            for ((mut name, kind), ids) in mem::take(&mut groups_map) {
392                name.drive_mut(&mut IdRefMapperVisitor::new(&remap));
393                let key = (name, kind);
394                let per_target = groups_map.entry(key).or_default();
395                for (target, item_id) in ids {
396                    if per_target.contains_key(&target) {
397                        // Name collision within the same target: skip this group entirely.
398                        per_target.clear();
399                        break;
400                    } else {
401                        per_target.insert(target, item_id);
402                    }
403                }
404            }
405            groups_map.retain(|_, v| v.len() == num_targets);
406            if prev_len == groups_map.len() {
407                break;
408            }
409        }
410        let groups: IndexVec<TargetGroupId, TargetGroup> = groups_map
411            .values()
412            .filter(|&per_target| per_target.len() == num_targets)
413            .cloned()
414            .map(|ids| TargetGroup { ids })
415            .collect();
416        groups
417    }
418
419    /// Decide how to merge each group. Skipped groups are not included in the output.
420    fn decide_group_mergings(&self) -> Vec<(TargetGroupId, MergeDecision)> {
421        // Start with all groups as candidates.
422        let mut candidates: Vec<(TargetGroupId, MergeDecision)> = self
423            .groups
424            .indices()
425            .map(|id| (id, MergeDecision::Skip))
426            .collect();
427
428        // Fixpoint: assume that all included groups are mapped to a single item; keep the groups
429        // that can be merged under such a mapping. Iterate until fixpoint.
430        loop {
431            let remap = self.build_remap(candidates.iter().map(|(id, _)| id));
432            let prev_len = candidates.len();
433            candidates.retain_mut(|(idx, decision)| {
434                *decision = self.groups[*idx].decide_merge(self.krate, &remap);
435                *decision != MergeDecision::Skip
436            });
437            if candidates.len() == prev_len {
438                break;
439            }
440        }
441
442        candidates
443    }
444
445    /// Build an id remap: for each candidate group, map non-canonical IDs → canonical ID.
446    fn build_remap<'b>(
447        &self,
448        candidate_indices: impl IntoIterator<Item = &'b TargetGroupId>,
449    ) -> HashMap<ItemId, ItemId> {
450        candidate_indices
451            .into_iter()
452            .flat_map(|&idx| self.groups[idx].remap_entries())
453            .filter(|(x, y)| x != y)
454            .collect()
455    }
456
457    fn apply_merge_decisions(&mut self, decisions: Vec<(TargetGroupId, MergeDecision)>) {
458        if decisions.is_empty() {
459            return;
460        }
461
462        let mut remap = HashMap::new();
463        let mut facade_decls: Vec<FunDecl> = Vec::new();
464        for &(idx, decision) in &decisions {
465            let mut group = &self.groups[idx];
466            let target_id = match decision {
467                MergeDecision::Skip => unreachable!(),
468                MergeDecision::Dedup => {
469                    self.dedup_group(idx); // takes mutable borrow; invalidates `group`
470                    group = &self.groups[idx];
471                    group.canonical_id()
472                }
473                MergeDecision::Facade => {
474                    let facade_id = self.krate.fun_decls.reserve_slot();
475                    // Insert facade decls later because the id remapping would mess up the
476                    // dispatch maps.
477                    facade_decls.push(group.build_facade_decl(facade_id, self.krate));
478                    ItemId::Fun(facade_id)
479                }
480            };
481            for &id in group.ids.values() {
482                if id != target_id {
483                    remap.insert(id, target_id);
484                }
485            }
486        }
487
488        // Remap all ids.
489        self.krate.drive_mut(&mut IdRefMapperVisitor::new(&remap));
490
491        for decl in facade_decls {
492            self.krate
493                .set_new_item_slot(ItemId::Fun(decl.def_id), ItemByVal::Fun(decl));
494        }
495    }
496
497    fn dedup_group(&mut self, idx: TargetGroupId) {
498        let group = &self.groups[idx];
499        let canonical = group.canonical_id();
500
501        // Remove the target suffix (and do a little sanity check).
502        let mut name = self.krate.item_names.get(&canonical).cloned().unwrap();
503        name.name.pop().unwrap().as_target().unwrap();
504        if let Some(mut canonical_item) = self.krate.get_item_mut(canonical) {
505            canonical_item.item_meta().name = name.clone();
506        }
507        self.krate.item_names.insert(canonical, name);
508
509        // Merge per-target layouts into the canonical type.
510        if let ItemId::Type(canonical_type_id) = canonical {
511            let layouts = group
512                .ids
513                .values()
514                .map(|&id| *id.as_type().unwrap())
515                .flat_map(|id| {
516                    self.krate
517                        .type_decls
518                        .get_mut(id)
519                        .map(|tdecl| mem::take(&mut tdecl.layout))
520                        .into_iter()
521                        .flatten()
522                })
523                .collect();
524            if let Some(dest) = self.krate.type_decls.get_mut(canonical_type_id) {
525                dest.layout = layouts;
526            }
527        }
528
529        // Remove non-canonical copies.
530        for &id in group.ids.values() {
531            if id != canonical {
532                self.krate.remove_item(id);
533            }
534        }
535    }
536}
537
538// =============================================================================================
539// Utilities
540// =============================================================================================
541
542/// Normalize an item for cross-target comparison.
543fn normalize_item(
544    mut item: ItemByVal,
545    canonical_id: ItemId,
546    remap: &HashMap<ItemId, ItemId>,
547) -> ItemByVal {
548    item.as_mut().drive_mut(&mut IdRefMapperVisitor::new(remap));
549    item.as_mut().set_id(canonical_id);
550    item.as_mut()
551        .item_meta()
552        .name
553        .name
554        .retain(|elem| !matches!(elem, PathElem::Target(_)));
555    if let ItemByVal::Type(ty_decl) = &mut item {
556        // Layouts are allowed to differ per-target.
557        ty_decl.layout.clear();
558    }
559    item
560}
561
562/// Visitor that remaps references to the given items.
563#[derive(Visitor)]
564struct IdRefMapperVisitor<'a> {
565    map: &'a HashMap<ItemId, ItemId>,
566}
567
568impl<'a> IdRefMapperVisitor<'a> {
569    fn new(remap: &'a HashMap<ItemId, ItemId>) -> Self {
570        Self { map: remap }
571    }
572
573    fn map<Id>(&self, id: &mut Id)
574    where
575        Id: Copy,
576        Id: Into<ItemId>,
577        ItemId: TryInto<Id, Error: Debug>,
578    {
579        if let Some(&new) = self.map.get(&(*id).into()) {
580            *id = new.try_into().unwrap();
581        }
582    }
583}
584
585impl VisitAstMut for IdRefMapperVisitor<'_> {
586    fn enter_type_decl_ref(&mut self, x: &mut TypeDeclRef) {
587        if let TypeId::Adt(id) = &mut x.id {
588            self.map(id);
589        }
590    }
591    fn enter_fun_decl_ref(&mut self, x: &mut FunDeclRef) {
592        self.map(&mut x.id);
593    }
594    fn enter_global_decl_ref(&mut self, x: &mut GlobalDeclRef) {
595        self.map(&mut x.id);
596    }
597    fn enter_trait_decl_ref(&mut self, x: &mut TraitDeclRef) {
598        self.map(&mut x.id);
599    }
600    fn enter_trait_impl_ref(&mut self, x: &mut TraitImplRef) {
601        self.map(&mut x.id);
602    }
603
604    fn enter_projection_elem(&mut self, x: &mut ProjectionElem) {
605        if let ProjectionElem::Field(proj, _) = x
606            && let FieldProjKind::Adt(id, _) = proj
607        {
608            self.map(id);
609        }
610    }
611    fn enter_fn_ptr(&mut self, x: &mut FnPtr) {
612        match &mut *x.kind {
613            FnPtrKind::Fun(FunId::Regular(id)) => self.map(id),
614            FnPtrKind::Trait(_, _, id) => self.map(id),
615            _ => {}
616        }
617    }
618    fn enter_trait_method_ref(&mut self, x: &mut TraitMethodRef) {
619        self.map(&mut x.method_decl_id);
620    }
621    fn enter_item_source(&mut self, x: &mut ItemSource) {
622        if let ItemSource::VTableMethodPreShim(id, _, _) = x {
623            self.map(id);
624        }
625    }
626    fn enter_global_decl(&mut self, x: &mut GlobalDecl) {
627        self.map(&mut x.init);
628    }
629    fn enter_fun_decl(&mut self, x: &mut FunDecl) {
630        if let Some(id) = &mut x.is_global_initializer {
631            self.map(id);
632        }
633    }
634    fn enter_impl_elem(&mut self, x: &mut ImplElem) {
635        if let ImplElem::Trait(id) = x {
636            self.map(id);
637        }
638    }
639}
charon_lib/export/multi_target.rs

charon_lib/export/
multi_target.rs
