fallow_cli/report/
dupes_grouping.rs

1//! Per-group attribution for `fallow dupes --group-by`.
2//!
3//! For each `CloneGroup`, every instance is attributed to a group key (owner,
4//! directory, package, or section) via the same [`OwnershipResolver`] used by
5//! `check` and `health`. The group itself is then attributed to its
6//! **largest owner**: the key with the most instances in that clone group.
7//! Ties are broken alphabetically (lexicographic ascending).
8//!
9//! This mirrors jscpd's majority-owner attribution and avoids the
10//! positional non-determinism that a "first-instance-wins" rule would
11//! introduce, since `DuplicationReport::sort()` already orders instances
12//! deterministically by file path then line.
13
14use std::collections::BTreeMap;
15use std::path::Path;
16
17use fallow_core::duplicates::{
18    CloneFingerprintSet, CloneGroup, CloneInstance, DuplicationReport, DuplicationStats,
19};
20use rustc_hash::FxHashSet;
21use serde::Serialize;
22
23use super::grouping::OwnershipResolver;
24use super::relative_path;
25use crate::baseline::recompute_stats;
26use crate::codeowners::UNOWNED_LABEL;
27use crate::output_dupes::{AttributedCloneGroupFinding, CloneFamilyFinding};
28
29/// Resolve the group key for a single instance file.
30fn key_for_instance(instance: &CloneInstance, root: &Path, resolver: &OwnershipResolver) -> String {
31    resolver.resolve(relative_path(&instance.file, root))
32}
33
34/// Pick the largest owner for a clone group: most instances wins, ties broken
35/// alphabetically (smallest key wins).
36///
37/// Iterates a `BTreeMap` so iteration order is alphabetical. The first key
38/// to reach the running maximum wins, which means equal counts resolve to the
39/// alphabetically-smallest key.
40pub fn largest_owner(group: &CloneGroup, root: &Path, resolver: &OwnershipResolver) -> String {
41    let mut counts: BTreeMap<String, u32> = BTreeMap::new();
42    for instance in &group.instances {
43        let key = key_for_instance(instance, root, resolver);
44        *counts.entry(key).or_insert(0) += 1;
45    }
46    if counts.is_empty() {
47        return UNOWNED_LABEL.to_string();
48    }
49    let mut best_key: Option<String> = None;
50    let mut best_count: u32 = 0;
51    for (key, count) in counts {
52        if best_key.is_none() || count > best_count {
53            best_count = count;
54            best_key = Some(key);
55        }
56    }
57    best_key.unwrap_or_else(|| UNOWNED_LABEL.to_string())
58}
59
60/// A clone instance plus its per-instance owner key (for inline JSON / SARIF
61/// rendering).
62///
63/// Each instance carries its own `owner` field alongside the standard
64/// `CloneInstance` shape (file / start_line / end_line / start_col / end_col /
65/// fragment), so consumers can attribute instances to resolver keys without
66/// re-resolving paths.
67#[derive(Debug, Clone, Serialize)]
68#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
69pub struct AttributedInstance {
70    /// The original clone instance.
71    #[serde(flatten)]
72    pub instance: CloneInstance,
73    /// Resolver key for this specific instance (per-instance, not the
74    /// group-level largest-owner).
75    pub owner: String,
76}
77
78/// A clone group annotated with its largest-owner attribution and per-instance
79/// owner keys.
80#[derive(Debug, Clone, Serialize)]
81#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
82pub struct AttributedCloneGroup {
83    /// Largest-owner attribution: the resolver key with the most instances in
84    /// this clone group. Ties broken alphabetically (smallest key wins).
85    pub primary_owner: String,
86    pub token_count: usize,
87    pub line_count: usize,
88    /// Each instance carries its own `owner` field alongside the standard
89    /// CloneInstance shape.
90    pub instances: Vec<AttributedInstance>,
91}
92
93impl AttributedCloneGroup {
94    fn from_group(group: &CloneGroup, root: &Path, resolver: &OwnershipResolver) -> Self {
95        let primary_owner = largest_owner(group, root, resolver);
96        let instances = group
97            .instances
98            .iter()
99            .map(|instance| AttributedInstance {
100                owner: key_for_instance(instance, root, resolver),
101                instance: instance.clone(),
102            })
103            .collect();
104        Self {
105            primary_owner,
106            token_count: group.token_count,
107            line_count: group.line_count,
108            instances,
109        }
110    }
111
112    fn fingerprint(&self, fingerprints: &CloneFingerprintSet) -> String {
113        let instances: Vec<_> = self
114            .instances
115            .iter()
116            .map(|instance| instance.instance.clone())
117            .collect();
118        fingerprints.fingerprint_for_parts(&instances, self.token_count, self.line_count)
119    }
120}
121
122/// A single grouped duplication bucket. Per-group `stats` are dedup-aware and
123/// computed over the FULL group BEFORE any `--top` truncation.
124#[derive(Debug, Clone, Serialize)]
125#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
126pub struct DuplicationGroup {
127    /// Group label (owner / directory / package / section). `(unowned)` for
128    /// files with no CODEOWNERS rule, `(no section)` for pre-section rules in
129    /// section mode.
130    pub key: String,
131    pub stats: DuplicationStats,
132    /// Clone groups attributed to this owner, each wrapped with the typed
133    /// `actions[]` array. Each group's `primary_owner` is its largest-owner
134    /// key; per-instance `owner` lets consumers see cross-bucket fan-out
135    /// without re-resolving paths.
136    pub clone_groups: Vec<AttributedCloneGroupFinding>,
137    /// Clone families overlapping this bucket, each wrapped with the typed
138    /// `actions[]` array.
139    pub clone_families: Vec<CloneFamilyFinding>,
140}
141
142/// Wrapper carrying the resolver mode label and grouped buckets.
143#[derive(Debug, Clone, Serialize)]
144pub struct DuplicationGrouping {
145    /// Resolver mode label (`"owner"`, `"directory"`, `"package"`, `"section"`).
146    pub mode: &'static str,
147    /// One bucket per resolver key, sorted most clone groups first with
148    /// `(unowned)` pinned last.
149    pub groups: Vec<DuplicationGroup>,
150}
151
152/// Build the grouped duplication payload from a project-level report.
153///
154/// Aggregation is performed BEFORE any `--top` truncation so per-group stats
155/// reflect the full group, not just the rendered top-N.
156pub fn build_duplication_grouping(
157    report: &DuplicationReport,
158    root: &Path,
159    resolver: &OwnershipResolver,
160) -> DuplicationGrouping {
161    let fingerprints = CloneFingerprintSet::from_groups(&report.clone_groups);
162    let mut buckets: BTreeMap<String, Vec<AttributedCloneGroup>> = BTreeMap::new();
163    for group in &report.clone_groups {
164        let attributed = AttributedCloneGroup::from_group(group, root, resolver);
165        buckets
166            .entry(attributed.primary_owner.clone())
167            .or_default()
168            .push(attributed);
169    }
170
171    let mut groups: Vec<DuplicationGroup> = buckets
172        .into_iter()
173        .map(|(key, attributed_groups)| {
174            let original_groups: Vec<CloneGroup> = attributed_groups
175                .iter()
176                .map(|ag| CloneGroup {
177                    instances: ag.instances.iter().map(|i| i.instance.clone()).collect(),
178                    token_count: ag.token_count,
179                    line_count: ag.line_count,
180                })
181                .collect();
182            let mut subset = DuplicationReport {
183                clone_groups: original_groups,
184                clone_families: Vec::new(),
185                mirrored_directories: Vec::new(),
186                stats: DuplicationStats {
187                    total_files: report.stats.total_files,
188                    files_with_clones: 0,
189                    total_lines: report.stats.total_lines,
190                    duplicated_lines: 0,
191                    total_tokens: report.stats.total_tokens,
192                    duplicated_tokens: 0,
193                    clone_groups: 0,
194                    clone_instances: 0,
195                    duplication_percentage: 0.0,
196                    clone_groups_below_min_occurrences: report
197                        .stats
198                        .clone_groups_below_min_occurrences,
199                },
200            };
201            subset.stats = recompute_stats(&subset);
202
203            let bucket_files: FxHashSet<&Path> = attributed_groups
204                .iter()
205                .flat_map(|ag| ag.instances.iter().map(|i| i.instance.file.as_path()))
206                .collect();
207            let clone_families: Vec<CloneFamilyFinding> = report
208                .clone_families
209                .iter()
210                .filter(|f| f.files.iter().any(|fp| bucket_files.contains(fp.as_path())))
211                .map(|family| CloneFamilyFinding::with_fingerprints(family.clone(), &fingerprints))
212                .collect();
213
214            let clone_groups: Vec<AttributedCloneGroupFinding> = attributed_groups
215                .into_iter()
216                .map(|group| {
217                    let fingerprint = group.fingerprint(&fingerprints);
218                    AttributedCloneGroupFinding::with_fingerprint(group, fingerprint)
219                })
220                .collect();
221
222            DuplicationGroup {
223                key,
224                stats: subset.stats,
225                clone_groups,
226                clone_families,
227            }
228        })
229        .collect();
230
231    groups.sort_by(|a, b| {
232        let a_unowned = a.key == UNOWNED_LABEL;
233        let b_unowned = b.key == UNOWNED_LABEL;
234        match (a_unowned, b_unowned) {
235            (true, false) => std::cmp::Ordering::Greater,
236            (false, true) => std::cmp::Ordering::Less,
237            _ => b
238                .clone_groups
239                .len()
240                .cmp(&a.clone_groups.len())
241                .then_with(|| a.key.cmp(&b.key)),
242        }
243    });
244
245    DuplicationGrouping {
246        mode: resolver.mode_label(),
247        groups,
248    }
249}
250
251#[cfg(test)]
252mod tests {
253    use std::path::PathBuf;
254
255    use fallow_core::duplicates::{CloneInstance, DuplicationStats};
256
257    use super::*;
258    use crate::codeowners::CodeOwners;
259
260    fn instance(path: &str, start: usize, end: usize) -> CloneInstance {
261        CloneInstance {
262            file: PathBuf::from(path),
263            start_line: start,
264            end_line: end,
265            start_col: 0,
266            end_col: 0,
267            fragment: String::new(),
268        }
269    }
270
271    fn group(instances: Vec<CloneInstance>) -> CloneGroup {
272        CloneGroup {
273            instances,
274            token_count: 50,
275            line_count: 10,
276        }
277    }
278
279    fn report(groups: Vec<CloneGroup>) -> DuplicationReport {
280        DuplicationReport {
281            clone_groups: groups,
282            clone_families: vec![],
283            mirrored_directories: vec![],
284            stats: DuplicationStats {
285                total_files: 10,
286                total_lines: 1000,
287                ..Default::default()
288            },
289        }
290    }
291
292    #[test]
293    fn largest_owner_majority_wins() {
294        let r = group(vec![
295            instance("/root/src/a.ts", 1, 10),
296            instance("/root/src/b.ts", 1, 10),
297            instance("/root/lib/c.ts", 1, 10),
298        ]);
299        let key = largest_owner(&r, Path::new("/root"), &OwnershipResolver::Directory);
300        assert_eq!(key, "src", "src has 2 instances vs lib's 1");
301    }
302
303    #[test]
304    fn largest_owner_alphabetical_tiebreak() {
305        let r = group(vec![
306            instance("/root/src/a.ts", 1, 10),
307            instance("/root/lib/b.ts", 1, 10),
308        ]);
309        let key = largest_owner(&r, Path::new("/root"), &OwnershipResolver::Directory);
310        assert_eq!(key, "lib");
311    }
312
313    #[test]
314    fn largest_owner_three_way_tie_alphabetical() {
315        let r = group(vec![
316            instance("/root/zeta/a.ts", 1, 10),
317            instance("/root/alpha/b.ts", 1, 10),
318            instance("/root/beta/c.ts", 1, 10),
319        ]);
320        let key = largest_owner(&r, Path::new("/root"), &OwnershipResolver::Directory);
321        assert_eq!(key, "alpha");
322    }
323
324    #[test]
325    fn build_grouping_partitions_clone_groups() {
326        let g1 = group(vec![
327            instance("/root/src/a.ts", 1, 10),
328            instance("/root/src/b.ts", 1, 10),
329        ]);
330        let g2 = group(vec![
331            instance("/root/lib/x.ts", 1, 10),
332            instance("/root/lib/y.ts", 1, 10),
333        ]);
334        let r = report(vec![g1, g2]);
335        let grouping =
336            build_duplication_grouping(&r, Path::new("/root"), &OwnershipResolver::Directory);
337        assert_eq!(grouping.groups.len(), 2);
338        let lib = grouping.groups.iter().find(|g| g.key == "lib").unwrap();
339        let src = grouping.groups.iter().find(|g| g.key == "src").unwrap();
340        assert_eq!(lib.clone_groups.len(), 1);
341        assert_eq!(src.clone_groups.len(), 1);
342    }
343
344    #[test]
345    fn build_grouping_unowned_pinned_last() {
346        let co = CodeOwners::parse("/src/ @frontend\n").unwrap();
347        let resolver = OwnershipResolver::Owner(co);
348        let g_src = group(vec![
349            instance("/root/src/a.ts", 1, 10),
350            instance("/root/src/b.ts", 1, 10),
351        ]);
352        let g_docs = group(vec![
353            instance("/root/docs/a.md", 1, 10),
354            instance("/root/docs/b.md", 1, 10),
355        ]);
356        let r = report(vec![g_src, g_docs]);
357        let grouping = build_duplication_grouping(&r, Path::new("/root"), &resolver);
358        assert_eq!(grouping.groups.len(), 2);
359        assert_eq!(grouping.groups.last().unwrap().key, UNOWNED_LABEL);
360    }
361
362    #[test]
363    fn build_grouping_per_instance_owner_inline() {
364        let g = group(vec![
365            instance("/root/src/a.ts", 1, 10),
366            instance("/root/src/b.ts", 1, 10),
367            instance("/root/lib/c.ts", 1, 10),
368        ]);
369        let r = report(vec![g]);
370        let grouping =
371            build_duplication_grouping(&r, Path::new("/root"), &OwnershipResolver::Directory);
372        assert_eq!(grouping.groups.len(), 1);
373        let bucket = &grouping.groups[0];
374        assert_eq!(bucket.key, "src");
375        assert_eq!(bucket.clone_groups.len(), 1);
376        let finding = &bucket.clone_groups[0];
377        let cg = &finding.group;
378        assert_eq!(cg.primary_owner, "src");
379        assert_eq!(cg.instances.len(), 3);
380        let owners: Vec<&str> = cg.instances.iter().map(|i| i.owner.as_str()).collect();
381        assert!(owners.contains(&"src"));
382        assert!(owners.contains(&"lib"));
383        assert_eq!(finding.actions.len(), 2);
384    }
385
386    #[test]
387    fn empty_report_produces_empty_grouping() {
388        let r = DuplicationReport::default();
389        let grouping =
390            build_duplication_grouping(&r, Path::new("/root"), &OwnershipResolver::Directory);
391        assert!(grouping.groups.is_empty());
392    }
393}
fallow_cli/report/dupes_grouping.rs

fallow_cli/report/
dupes_grouping.rs
