1use 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
20pub 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
41struct 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: _, 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 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: _, target_information,
149 runtime_checks,
150 item_names,
151 assoc_item_names,
152 short_names: _, files: _, type_decls,
155 fun_decls,
156 global_decls,
157 trait_decls,
158 trait_impls,
159 ordered_decls: _, } = 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
202generate_index_type!(TargetGroupId, "TargetGroup");
208
209struct TargetGroup {
212 ids: SeqHashMap<TargetTriple, ItemId>,
213}
214
215#[derive(Debug, Copy, Clone, PartialEq, Eq)]
217enum MergeDecision {
218 Skip,
220 Dedup,
222 Facade,
225}
226
227struct 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
274impl 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: _,
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 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 fn canonical_id(&self) -> ItemId {
432 self.ids.values().next().copied().unwrap()
433 }
434
435 fn is_function_group(&self) -> bool {
437 self.canonical_id().is_fun()
438 }
439
440 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 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 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 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 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
525fn 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 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
555struct ItemDeduplicator<'a> {
557 krate: &'a mut TranslatedCrate,
558 groups: IndexVec<TargetGroupId, TargetGroup>,
559}
560
561impl<'a> ItemDeduplicator<'a> {
562 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 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 per_target.clear();
590 } else {
591 per_target.insert(target, item_id);
592 }
593 }
594 }
595 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 per_target.clear();
615 break;
616 } else {
617 per_target.insert(target, item_id);
618 }
619 }
620 }
621 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 fn decide_group_mergings(&self) -> Vec<(TargetGroupId, MergeDecision)> {
636 let mut candidates: Vec<(TargetGroupId, MergeDecision)> = self
638 .groups
639 .indices()
640 .map(|id| (id, MergeDecision::Skip))
641 .collect();
642
643 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 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 facade_decls.push(group.build_facade_decl(facade_id, self.krate));
693 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 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 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 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 for &id in group.ids.values() {
757 if id != canonical {
758 self.krate.remove_item(id);
759 }
760 }
761 }
762}
763
764fn 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
779fn 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 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 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 _ => {
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 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 krate.remove_item(ItemId::Fun(fun_id));
878 }
879 }
880 }
881 if unused_methods.is_empty() {
882 return;
883 }
884
885 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#[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}