Skip to main content

fallow_types/
duplicates.rs

1//! Shared duplicate-code output contracts.
2
3use std::cmp::{Ordering, Reverse};
4use std::collections::hash_map::Entry;
5use std::path::{Component, Path, PathBuf};
6
7use rustc_hash::FxHashMap;
8use serde::{Deserialize, Serialize};
9
10use crate::serde_path;
11
12/// A single instance of duplicated code at a specific location.
13#[derive(Debug, Clone, Serialize, Deserialize)]
14#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
15pub struct CloneInstance {
16    /// Path to the file containing this clone instance.
17    #[serde(serialize_with = "serde_path::serialize")]
18    pub file: PathBuf,
19    /// 1-based start line of the clone.
20    pub start_line: usize,
21    /// 1-based end line of the clone.
22    pub end_line: usize,
23    /// 0-based byte column offset of the start.
24    pub start_col: usize,
25    /// 0-based byte column offset of the end.
26    pub end_col: usize,
27    /// The actual source code fragment.
28    ///
29    /// Omitted from JSON when the caller asked for a location-only payload
30    /// (`fallow dupes --no-fragments`, and the MCP `find_dupes` default). The
31    /// five location fields above address the same text, so a consumer that
32    /// wants the source reads it from the file.
33    #[serde(default, skip_serializing_if = "String::is_empty")]
34    pub fragment: String,
35    /// Whether the file path is a symlink, or lies under a symlinked
36    /// directory, inside the project root. Omitted when `false`.
37    ///
38    /// A clone with a symlinked instance can be the same file under two
39    /// paths, not copied code. `duplicates.ignoreSymlinks` (or
40    /// `fallow dupes --ignore-symlinks`) removes these instances.
41    #[serde(default, skip_serializing_if = "std::ops::Not::not")]
42    pub is_symlink: bool,
43}
44
45/// A group of code clones -- the same (or normalized-equivalent) code appearing
46/// in multiple places.
47#[derive(Debug, Clone, Serialize, Deserialize)]
48#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
49pub struct CloneGroup {
50    /// All instances where this duplicated code appears.
51    pub instances: Vec<CloneInstance>,
52    /// Number of tokens in the duplicated block.
53    pub token_count: usize,
54    /// Number of lines in the duplicated block.
55    pub line_count: usize,
56    /// Lowest all-pairs similarity for a near-miss clone group. Exact clone
57    /// groups omit this field.
58    #[serde(default, skip_serializing_if = "Option::is_none")]
59    #[cfg_attr(feature = "schema", schemars(with = "f64"))]
60    pub similarity: Option<f64>,
61}
62
63/// Whether a clone group is exact or a near-miss match.
64///
65/// This is derived from the serialized clone-group fields and does not add a
66/// separate discriminator to the output contract.
67#[derive(Debug, Clone, Copy, PartialEq)]
68#[non_exhaustive]
69pub enum CloneGroupKind {
70    /// An exact or normalization-equivalent clone group.
71    Exact,
72    /// A near-miss group and its lowest all-pairs similarity.
73    Near {
74        /// Lowest all-pairs similarity for the group.
75        similarity: f64,
76    },
77}
78
79impl CloneGroup {
80    /// Return the semantic kind represented by this clone group.
81    #[must_use]
82    pub fn kind(&self) -> CloneGroupKind {
83        self.similarity
84            .map_or(CloneGroupKind::Exact, |similarity| CloneGroupKind::Near {
85                similarity,
86            })
87    }
88
89    /// Maximum directory-tree or same-file line distance between instances.
90    #[must_use]
91    pub fn spread(&self) -> usize {
92        clone_group_spread(&self.instances)
93    }
94
95    /// Drop the verbatim source text from every instance in this group.
96    pub fn strip_fragments(&mut self) {
97        for instance in &mut self.instances {
98            instance.fragment.clear();
99        }
100    }
101}
102
103const SAME_FILE_SPREAD_STEP: usize = 250;
104const MAX_RANKED_SPREAD: usize = 8;
105const SPREAD_RANK_WEIGHTS: [u64; MAX_RANKED_SPREAD + 1] = [
106    1_000_000_000,
107    1_047_319_732,
108    1_075_000_000,
109    1_094_639_463,
110    1_109_873_014,
111    1_122_319_732,
112    1_132_843_281,
113    1_141_959_195,
114    1_150_000_000,
115];
116
117/// Compute the maximum distance between clone instances.
118///
119/// Instances in different files use lexical parent-directory distance.
120/// Instances in the same file use the non-overlapping line gap, rounded up in
121/// 250-line steps. The returned value is not capped; only ranking caps spread.
122#[must_use]
123pub fn clone_group_spread(instances: &[CloneInstance]) -> usize {
124    clone_location_spread(instances.iter().map(|instance| {
125        (
126            instance.file.as_path(),
127            instance.start_line,
128            instance.end_line,
129        )
130    }))
131}
132
133/// Compute clone spread from borrowed file and line locations.
134///
135/// This is equivalent to [`clone_group_spread`] without requiring callers
136/// that wrap clone instances to clone their source fragments.
137#[must_use]
138pub fn clone_location_spread<'a>(
139    locations: impl IntoIterator<Item = (&'a Path, usize, usize)>,
140) -> usize {
141    let mut locations = locations.into_iter();
142    let mut small = SmallFileSet::default();
143    let mut location_count = 0;
144    while let Some((file, start_line, end_line)) = locations.next() {
145        location_count += 1;
146        if small.include(file, start_line, end_line) {
147            continue;
148        }
149        let new_file = FileLines::new(file, start_line, end_line);
150        if !small.push(new_file) {
151            return large_location_spread(&small, new_file, locations);
152        }
153    }
154
155    if location_count < 2 {
156        return 0;
157    }
158    small.spread()
159}
160
161/// The number of files that [`clone_location_spread`] keeps on the stack.
162/// Most clone groups span two or three files.
163const SMALL_FILE_SET_LIMIT: usize = 8;
164
165/// The line range of the locations in one file.
166#[derive(Clone, Copy)]
167struct FileLines<'a> {
168    file: &'a Path,
169    min_end: usize,
170    max_start: usize,
171    occurrences: usize,
172}
173
174impl<'a> FileLines<'a> {
175    const fn new(file: &'a Path, start_line: usize, end_line: usize) -> Self {
176        Self {
177            file,
178            min_end: end_line,
179            max_start: start_line,
180            occurrences: 1,
181        }
182    }
183
184    fn include(&mut self, start_line: usize, end_line: usize) {
185        self.min_end = self.min_end.min(end_line);
186        self.max_start = self.max_start.max(start_line);
187        self.occurrences += 1;
188    }
189
190    fn same_file_spread(&self) -> usize {
191        self.max_start
192            .saturating_sub(self.min_end)
193            .saturating_sub(1)
194            .div_ceil(SAME_FILE_SPREAD_STEP)
195    }
196}
197
198/// The files of a small clone group, without a heap allocation.
199#[derive(Default)]
200struct SmallFileSet<'a> {
201    files: [Option<FileLines<'a>>; SMALL_FILE_SET_LIMIT],
202    len: usize,
203}
204
205impl<'a> SmallFileSet<'a> {
206    fn iter(&self) -> impl Iterator<Item = &FileLines<'a>> {
207        self.files[..self.len].iter().flatten()
208    }
209
210    /// Add a location to its file. Returns `false` when the file is new.
211    fn include(&mut self, file: &Path, start_line: usize, end_line: usize) -> bool {
212        let Some(lines) = self.files[..self.len]
213            .iter_mut()
214            .flatten()
215            .find(|lines| lines.file == file)
216        else {
217            return false;
218        };
219        lines.include(start_line, end_line);
220        true
221    }
222
223    /// Add a new file. Returns `false` when the set is full.
224    fn push(&mut self, lines: FileLines<'a>) -> bool {
225        let Some(slot) = self.files.get_mut(self.len) else {
226            return false;
227        };
228        *slot = Some(lines);
229        self.len += 1;
230        true
231    }
232
233    /// The spread of the set: the largest same-file spread or the largest
234    /// directory distance between two files. With few files, the pairwise
235    /// maximum is the tree diameter.
236    fn spread(&self) -> usize {
237        let same_file_max = self
238            .iter()
239            .filter(|lines| lines.occurrences >= 2)
240            .map(FileLines::same_file_spread)
241            .max()
242            .unwrap_or(0);
243        let mut diameter = 0;
244        for (index, left) in self.iter().enumerate() {
245            for right in self.iter().skip(index + 1) {
246                diameter = diameter.max(parent_distance(left.file, right.file));
247            }
248        }
249        same_file_max.max(diameter)
250    }
251}
252
253/// The number of parent-directory steps between two files, read in one pass
254/// over each path.
255fn parent_distance(left: &Path, right: &Path) -> usize {
256    let mut left = left.parent().unwrap_or_else(|| Path::new("")).components();
257    let mut right = right.parent().unwrap_or_else(|| Path::new("")).components();
258    loop {
259        match (left.next(), right.next()) {
260            (Some(left_part), Some(right_part)) if left_part == right_part => {}
261            (Some(_), Some(_)) => return 2 + left.count() + right.count(),
262            (Some(_), None) => return 1 + left.count(),
263            (None, Some(_)) => return 1 + right.count(),
264            (None, None) => return 0,
265        }
266    }
267}
268
269/// The spread of a clone group with more files than [`SmallFileSet`] holds.
270fn large_location_spread<'a>(
271    small: &SmallFileSet<'a>,
272    pending: FileLines<'a>,
273    rest: impl Iterator<Item = (&'a Path, usize, usize)>,
274) -> usize {
275    let mut file_indices: FxHashMap<&'a Path, usize> = FxHashMap::default();
276    let mut by_file: Vec<FileSpread<'a>> = Vec::new();
277    for lines in small.iter().copied().chain(std::iter::once(pending)) {
278        file_indices.insert(lines.file, by_file.len());
279        by_file.push(FileSpread::from_lines(lines));
280    }
281
282    for (file, start_line, end_line) in rest {
283        let next_index = by_file.len();
284        match file_indices.entry(file) {
285            Entry::Occupied(entry) => by_file[*entry.get()].include(start_line, end_line),
286            Entry::Vacant(entry) => {
287                entry.insert(next_index);
288                by_file.push(FileSpread::new(file, start_line, end_line));
289            }
290        }
291    }
292
293    let same_file_max = by_file
294        .iter()
295        .filter(|file| file.occurrences >= 2)
296        .map(FileSpread::same_file_spread)
297        .max()
298        .unwrap_or(0);
299
300    same_file_max.max(directory_tree_diameter(&by_file))
301}
302
303struct FileSpread<'a> {
304    parent_components: Vec<Component<'a>>,
305    min_end: usize,
306    max_start: usize,
307    occurrences: usize,
308}
309
310impl<'a> FileSpread<'a> {
311    fn from_lines(lines: FileLines<'a>) -> Self {
312        Self {
313            parent_components: path_parent_components(lines.file),
314            min_end: lines.min_end,
315            max_start: lines.max_start,
316            occurrences: lines.occurrences,
317        }
318    }
319
320    fn new(file: &'a Path, start_line: usize, end_line: usize) -> Self {
321        Self {
322            parent_components: path_parent_components(file),
323            min_end: end_line,
324            max_start: start_line,
325            occurrences: 1,
326        }
327    }
328
329    fn include(&mut self, start_line: usize, end_line: usize) {
330        self.min_end = self.min_end.min(end_line);
331        self.max_start = self.max_start.max(start_line);
332        self.occurrences += 1;
333    }
334
335    fn same_file_spread(&self) -> usize {
336        self.max_start
337            .saturating_sub(self.min_end)
338            .saturating_sub(1)
339            .div_ceil(SAME_FILE_SPREAD_STEP)
340    }
341}
342
343/// Compare clone groups in shared spread-aware priority order.
344#[must_use]
345pub fn compare_clone_groups(left: &CloneGroup, right: &CloneGroup) -> Ordering {
346    clone_group_rank_key(left).cmp(&clone_group_rank_key(right))
347}
348
349#[cfg(test)]
350fn instance_pair_spread(left: &CloneInstance, right: &CloneInstance) -> usize {
351    if left.file == right.file {
352        return same_file_spread(left, right);
353    }
354    directory_distance(&left.file, &right.file)
355}
356
357#[cfg(test)]
358fn same_file_spread(left: &CloneInstance, right: &CloneInstance) -> usize {
359    let gap = if left.end_line < right.start_line {
360        right
361            .start_line
362            .saturating_sub(left.end_line)
363            .saturating_sub(1)
364    } else if right.end_line < left.start_line {
365        left.start_line
366            .saturating_sub(right.end_line)
367            .saturating_sub(1)
368    } else {
369        0
370    };
371    gap.div_ceil(SAME_FILE_SPREAD_STEP)
372}
373
374fn path_parent_components(path: &Path) -> Vec<Component<'_>> {
375    path.parent()
376        .unwrap_or_else(|| Path::new(""))
377        .components()
378        .collect()
379}
380
381fn directory_tree_diameter(paths: &[FileSpread<'_>]) -> usize {
382    if paths.len() < 2 {
383        return 0;
384    }
385
386    let endpoint = farthest_path(paths, 0).0;
387    farthest_path(paths, endpoint).1
388}
389
390fn farthest_path(paths: &[FileSpread<'_>], origin: usize) -> (usize, usize) {
391    paths
392        .iter()
393        .enumerate()
394        .map(|(index, path)| {
395            (
396                index,
397                component_distance(&paths[origin].parent_components, &path.parent_components),
398            )
399        })
400        .max_by_key(|&(index, distance)| (distance, index))
401        .unwrap_or((origin, 0))
402}
403
404fn component_distance(left: &[Component<'_>], right: &[Component<'_>]) -> usize {
405    let shared = left
406        .iter()
407        .zip(right)
408        .take_while(|(left, right)| left == right)
409        .count();
410    left.len()
411        .saturating_sub(shared)
412        .saturating_add(right.len().saturating_sub(shared))
413}
414
415#[cfg(test)]
416fn directory_distance(left: &Path, right: &Path) -> usize {
417    component_distance(
418        &path_parent_components(left),
419        &path_parent_components(right),
420    )
421}
422
423type CloneGroupRankKey = (
424    Reverse<u128>,
425    Reverse<usize>,
426    Reverse<usize>,
427    Reverse<usize>,
428    Reverse<usize>,
429    bool,
430    PathBuf,
431    usize,
432);
433
434fn clone_group_rank_key(group: &CloneGroup) -> CloneGroupRankKey {
435    let spread = group.spread();
436    let weight = SPREAD_RANK_WEIGHTS[spread.min(MAX_RANKED_SPREAD)];
437    let token_count = u128::try_from(group.token_count).unwrap_or(u128::MAX);
438    let instance_count = u128::try_from(group.instances.len()).unwrap_or(u128::MAX);
439    let score = token_count
440        .saturating_mul(instance_count)
441        .saturating_mul(u128::from(weight));
442    let first = group.instances.iter().min_by(|left, right| {
443        left.file
444            .cmp(&right.file)
445            .then(left.start_line.cmp(&right.start_line))
446    });
447    (
448        Reverse(score),
449        Reverse(spread),
450        Reverse(group.token_count),
451        Reverse(group.instances.len()),
452        Reverse(group.line_count),
453        first.is_none(),
454        first.map_or_else(PathBuf::new, |instance| instance.file.clone()),
455        first.map_or(0, |instance| instance.start_line),
456    )
457}
458
459fn sort_clone_groups(groups: &mut [CloneGroup]) {
460    groups.sort_by_cached_key(clone_group_rank_key);
461}
462
463/// Sort clone groups into the order of [`DuplicationReport::sort`]: instances
464/// by file path and line, groups by spread-aware priority.
465///
466/// A clone family builds its suggestions from its groups, so it sorts them
467/// with this function first. Then the suggestions follow the group order on
468/// every surface.
469pub fn sort_clone_groups_in_report_order(groups: &mut [CloneGroup]) {
470    for group in groups.iter_mut() {
471        group
472            .instances
473            .sort_by(|a, b| a.file.cmp(&b.file).then(a.start_line.cmp(&b.start_line)));
474    }
475    sort_clone_groups(groups);
476}
477
478/// The kind of refactoring suggested for a clone family.
479#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
480#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
481pub enum RefactoringKind {
482    /// Extract a shared function/utility.
483    ExtractFunction,
484    /// Extract a shared module.
485    ExtractModule,
486}
487
488/// A refactoring suggestion for a clone family.
489#[derive(Debug, Clone, Serialize, Deserialize)]
490#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
491pub struct RefactoringSuggestion {
492    /// What kind of refactoring is suggested.
493    pub kind: RefactoringKind,
494    /// Human-readable description of the suggestion.
495    pub description: String,
496    /// Estimated lines that could be eliminated.
497    pub estimated_savings: usize,
498}
499
500/// A clone family: a set of clone groups that share the same file set.
501///
502/// When multiple clone groups are all duplicated between the same set of files,
503/// they form a family, indicating a deeper structural relationship that should
504/// be refactored together rather than group-by-group.
505#[derive(Debug, Clone, Serialize, Deserialize)]
506#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
507pub struct CloneFamily {
508    /// The files involved in this family (sorted for stable output).
509    #[serde(serialize_with = "serde_path::serialize_vec")]
510    pub files: Vec<PathBuf>,
511    /// Clone groups belonging to this family.
512    pub groups: Vec<CloneGroup>,
513    /// Total number of duplicated lines across all groups.
514    pub total_duplicated_lines: usize,
515    /// Total number of duplicated tokens across all groups.
516    pub total_duplicated_tokens: usize,
517    /// Refactoring suggestions for this family.
518    pub suggestions: Vec<RefactoringSuggestion>,
519}
520
521/// A detected mirrored directory pattern: two directory prefixes that contain
522/// identical files (e.g., `src/` and `deno/lib/`).
523#[derive(Debug, Clone, Serialize, Deserialize)]
524#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
525pub struct MirroredDirectory {
526    /// First directory path (lexically smaller).
527    pub dir_a: String,
528    /// Second directory path.
529    pub dir_b: String,
530    /// Filenames shared between the two directories.
531    pub shared_files: Vec<String>,
532    /// Total duplicated lines across all shared files.
533    pub total_lines: usize,
534}
535
536/// Number of files skipped by one built-in duplicates ignore pattern.
537#[derive(Debug, Clone, Default)]
538pub struct DefaultIgnoreSkipCount {
539    /// Glob pattern that matched skipped files.
540    pub pattern: &'static str,
541    /// Number of files skipped by this pattern.
542    pub count: usize,
543}
544
545/// Human-format-only skipped-file stats for built-in duplicates ignores.
546#[derive(Debug, Clone, Default)]
547pub struct DefaultIgnoreSkips {
548    /// Total number of files skipped by built-in duplicates ignores.
549    pub total: usize,
550    /// Per-pattern skip counts, in default pattern order.
551    pub by_pattern: Vec<DefaultIgnoreSkipCount>,
552}
553
554/// Overall duplication analysis report.
555#[derive(Debug, Clone, Default, Serialize, Deserialize)]
556#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
557pub struct DuplicationReport {
558    /// All detected clone groups. Each group contains 2+ instances of identical
559    /// or near-identical code.
560    pub clone_groups: Vec<CloneGroup>,
561    /// Clone families: groups of clone groups sharing the same file set,
562    /// indicating systematic duplication patterns.
563    pub clone_families: Vec<CloneFamily>,
564    /// Detected mirrored directory trees (directories with many identical files).
565    #[serde(default, skip_serializing_if = "Vec::is_empty")]
566    pub mirrored_directories: Vec<MirroredDirectory>,
567    /// `fallow-ignore-start` and `fallow-ignore-end` markers with a problem.
568    /// A marker with a problem has no effect on clone detection.
569    #[serde(default, skip_serializing_if = "Vec::is_empty")]
570    pub range_marker_problems: Vec<RangeMarkerFinding>,
571    /// Aggregate statistics.
572    pub stats: DuplicationStats,
573}
574
575/// A `fallow-ignore-start` or `fallow-ignore-end` marker with a problem, in
576/// one file.
577#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
578#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
579pub struct RangeMarkerFinding {
580    /// Path to the file that holds the marker.
581    #[serde(serialize_with = "serde_path::serialize")]
582    pub path: PathBuf,
583    /// The line and the problem of the marker.
584    #[serde(flatten)]
585    pub problem: crate::suppress::RangeMarkerProblem,
586}
587
588impl DuplicationReport {
589    /// Sort all result arrays for deterministic output ordering.
590    ///
591    /// Clone groups use spread-aware priority order, instances use file path and
592    /// line order, and clone families use their file set.
593    pub fn sort(&mut self) {
594        sort_clone_groups_in_report_order(&mut self.clone_groups);
595        for family in &mut self.clone_families {
596            sort_clone_groups_in_report_order(&mut family.groups);
597        }
598        self.clone_families.sort_by(|a, b| a.files.cmp(&b.files));
599    }
600
601    /// Number of clone groups actually carried in `clone_groups[]`.
602    #[must_use]
603    pub fn clone_groups_shown(&self) -> usize {
604        self.clone_groups.len()
605    }
606
607    /// Number of scoped-corpus clone groups withheld from `clone_groups[]`.
608    ///
609    /// Non-zero only when a presentation cap such as `--top` truncated the
610    /// array; scope filters (diff, workspace, baseline) recompute `stats`, so
611    /// they leave nothing omitted.
612    #[must_use]
613    pub fn clone_groups_omitted(&self) -> usize {
614        self.stats
615            .clone_groups
616            .saturating_sub(self.clone_groups.len())
617    }
618
619    /// Number of clone groups the measured corpus holds, shown plus omitted.
620    ///
621    /// Reads `stats.clone_groups` except on a report whose stats were never
622    /// populated, where it falls back to the array length so a caller never
623    /// renders a total smaller than the rows beneath it.
624    #[must_use]
625    pub fn clone_groups_total(&self) -> usize {
626        self.clone_groups_shown() + self.clone_groups_omitted()
627    }
628
629    /// Number of clone families actually carried in `clone_families[]`.
630    #[must_use]
631    pub fn clone_families_shown(&self) -> usize {
632        self.clone_families.len()
633    }
634
635    /// Number of scoped-corpus clone families withheld from
636    /// `clone_families[]`.
637    ///
638    /// `--top` truncates `clone_groups[]` and rebuilds the families from what
639    /// survives, so the family array narrows with the group array. Scope
640    /// filters (diff, workspace, baseline) rebuild the families and then
641    /// recompute `stats`, so they leave nothing omitted.
642    #[must_use]
643    pub fn clone_families_omitted(&self) -> usize {
644        self.stats
645            .clone_families
646            .saturating_sub(self.clone_families.len())
647    }
648
649    /// Number of clone families the measured corpus holds, shown plus omitted.
650    #[must_use]
651    pub fn clone_families_total(&self) -> usize {
652        self.clone_families_shown() + self.clone_families_omitted()
653    }
654
655    /// Drop the verbatim source text from every clone instance, including the
656    /// copies nested in `clone_families[].groups[]`.
657    ///
658    /// Fingerprints, suggested names, refactoring suggestions and actions are
659    /// all derived before serialization, so removing the text only shrinks the
660    /// payload.
661    pub fn strip_fragments(&mut self) {
662        for group in &mut self.clone_groups {
663            group.strip_fragments();
664        }
665        for family in &mut self.clone_families {
666            for group in &mut family.groups {
667                group.strip_fragments();
668            }
669        }
670    }
671}
672
673/// Aggregate duplication statistics.
674#[derive(Debug, Clone, Default, Serialize, Deserialize)]
675#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
676pub struct DuplicationStats {
677    /// Total files analyzed.
678    pub total_files: usize,
679    /// Files containing at least one clone instance.
680    pub files_with_clones: usize,
681    /// Total lines across all analyzed files.
682    pub total_lines: usize,
683    /// Lines that are part of at least one clone.
684    pub duplicated_lines: usize,
685    /// Total tokens across all analyzed files.
686    pub total_tokens: usize,
687    /// Tokens in redundant clone copies, excluding one retained copy per group.
688    pub duplicated_tokens: usize,
689    /// Number of clone groups the scoped corpus contains after filtering.
690    /// `--top` does not change it; compare it with `clone_groups_shown` on the
691    /// envelope to see how much of the corpus the array carries.
692    pub clone_groups: usize,
693    /// Number of clone families the scoped corpus contains after filtering.
694    /// `--top` truncates `clone_families[]` along with `clone_groups[]` but
695    /// does not change this counter; compare it with `clone_families_shown` on
696    /// the envelope to see how much of the corpus the array carries.
697    pub clone_families: usize,
698    /// Total clone instances across the scoped corpus after filtering.
699    /// `--top` does not change it.
700    pub clone_instances: usize,
701    /// Percentage of duplicated lines (0.0 to 100.0). `--top` does not change
702    /// this scoped corpus metric.
703    pub duplication_percentage: f64,
704    /// Number of clone groups hidden by `duplicates.minOccurrences`. Absent (or
705    /// `0`) when the filter is at its default of `2` and nothing was hidden.
706    /// This counter covers only the minimum-occurrence filter.
707    #[serde(default, skip_serializing_if = "is_zero_usize")]
708    pub clone_groups_below_min_occurrences: usize,
709    /// Number of clone groups hidden by `duplicates.ignoredClones`.
710    #[serde(default, skip_serializing_if = "is_zero_usize")]
711    pub clone_groups_ignored: usize,
712    /// Near-miss candidate comparisons skipped by bounded-work limits.
713    #[serde(default, skip_serializing_if = "is_zero_usize")]
714    pub near_candidates_skipped: usize,
715}
716
717#[expect(
718    clippy::trivially_copy_pass_by_ref,
719    reason = "serde skip_serializing_if requires &T signature"
720)]
721const fn is_zero_usize(value: &usize) -> bool {
722    *value == 0
723}
724
725#[cfg(test)]
726mod tests {
727    use super::*;
728    use proptest::prelude::*;
729
730    fn pairwise_clone_group_spread(instances: &[CloneInstance]) -> usize {
731        let mut spread = 0;
732        for (index, left) in instances.iter().enumerate() {
733            for right in &instances[index + 1..] {
734                spread = spread.max(instance_pair_spread(left, right));
735            }
736        }
737        spread
738    }
739
740    fn instance(file: impl Into<PathBuf>, start_line: usize, end_line: usize) -> CloneInstance {
741        CloneInstance {
742            is_symlink: false,
743            file: file.into(),
744            start_line,
745            end_line,
746            start_col: 0,
747            end_col: 0,
748            fragment: String::new(),
749        }
750    }
751
752    fn group(instances: Vec<CloneInstance>, token_count: usize, line_count: usize) -> CloneGroup {
753        CloneGroup {
754            instances,
755            token_count,
756            line_count,
757            similarity: None,
758        }
759    }
760
761    #[test]
762    fn spread_counts_non_shared_parent_components() {
763        let clone = group(
764            vec![
765                instance("/repo/packages/a/src/a.ts", 1, 10),
766                instance("/repo/packages/b/src/b.ts", 1, 10),
767            ],
768            100,
769            10,
770        );
771        assert_eq!(clone.spread(), 4);
772    }
773
774    #[test]
775    fn spread_is_zero_for_different_files_in_the_same_directory() {
776        let clone = group(
777            vec![
778                instance("/repo/src/a.ts", 1, 10),
779                instance("/repo/src/b.ts", 1, 10),
780            ],
781            100,
782            10,
783        );
784        assert_eq!(clone.spread(), 0);
785    }
786
787    #[test]
788    fn adjacent_same_file_instances_have_zero_spread() {
789        let clone = group(
790            vec![
791                instance("/repo/src/a.ts", 1, 10),
792                instance("/repo/src/a.ts", 11, 20),
793            ],
794            100,
795            10,
796        );
797        assert_eq!(clone.spread(), 0);
798    }
799
800    #[test]
801    fn same_file_spread_uses_ceiling_rounded_intervening_lines() {
802        let clone = group(
803            vec![
804                instance("/repo/src/a.ts", 1, 10),
805                instance("/repo/src/a.ts", 260, 269),
806                instance("/repo/src/a.ts", 261, 270),
807                instance("/repo/src/a.ts", 262, 271),
808            ],
809            100,
810            10,
811        );
812        assert_eq!(clone_group_spread(&clone.instances[..2]), 1);
813        assert_eq!(clone_group_spread(&clone.instances[..3]), 1);
814        assert_eq!(clone.spread(), 2);
815    }
816
817    #[test]
818    fn overlapping_same_file_instances_have_zero_spread() {
819        let clone = group(
820            vec![
821                instance("/repo/src/a.ts", 1, 20),
822                instance("/repo/src/a.ts", 10, 30),
823            ],
824            100,
825            20,
826        );
827        assert_eq!(clone.spread(), 0);
828    }
829
830    #[test]
831    fn directory_diameter_handles_ties_and_mixed_roots() {
832        let instances = vec![
833            instance("src/a.ts", 1, 10),
834            instance("packages/a/b.ts", 1, 10),
835            instance("packages/c/d.ts", 1, 10),
836            instance("/repo/src/e.ts", 1, 10),
837        ];
838
839        assert_eq!(
840            clone_group_spread(&instances),
841            pairwise_clone_group_spread(&instances)
842        );
843    }
844
845    #[test]
846    fn spread_matches_reference_for_repeated_mixed_and_nested_files() {
847        let instances = vec![
848            instance("src/a.ts", 900, 920),
849            instance("packages/a/src/nested/b.ts", 40, 60),
850            instance("src/a.ts", 1, 20),
851            instance("/repo/apps/web/c.ts", 300, 325),
852            instance("packages/b/test/d.ts", 70, 90),
853            instance("/repo/apps/web/c.ts", 1, 25),
854        ];
855
856        assert_eq!(
857            clone_group_spread(&instances),
858            pairwise_clone_group_spread(&instances)
859        );
860    }
861
862    #[cfg(unix)]
863    #[test]
864    fn spread_matches_reference_for_non_utf8_paths() {
865        use std::ffi::OsString;
866        use std::os::unix::ffi::OsStringExt;
867
868        let first = PathBuf::from(OsString::from_vec(b"/repo/packages/\x80/src/a.ts".to_vec()));
869        let second = PathBuf::from(OsString::from_vec(b"/repo/packages/\x81/src/b.ts".to_vec()));
870        let instances = vec![
871            instance(first.clone(), 1, 20),
872            instance(second, 100, 120),
873            instance(first, 800, 820),
874        ];
875
876        assert_eq!(
877            clone_group_spread(&instances),
878            pairwise_clone_group_spread(&instances)
879        );
880    }
881
882    #[cfg(windows)]
883    #[test]
884    fn directory_diameter_handles_windows_prefixes() {
885        let instances = vec![
886            instance(r"C:\repo\src\a.ts", 1, 10),
887            instance(r"C:\repo\packages\b.ts", 1, 10),
888            instance(r"D:\other\c.ts", 1, 10),
889        ];
890
891        assert_eq!(
892            clone_group_spread(&instances),
893            pairwise_clone_group_spread(&instances)
894        );
895    }
896
897    #[test]
898    fn clone_group_kind_does_not_change_serialized_contract() {
899        let mut clone = group(vec![instance("src/a.ts", 1, 10)], 20, 10);
900        assert_eq!(clone.kind(), CloneGroupKind::Exact);
901        assert!(serde_json::to_value(&clone).unwrap()["similarity"].is_null());
902
903        clone.similarity = Some(0.85);
904        assert_eq!(clone.kind(), CloneGroupKind::Near { similarity: 0.85 });
905        assert_eq!(serde_json::to_value(&clone).unwrap()["similarity"], 0.85);
906    }
907
908    mod proptests {
909        use super::*;
910
911        proptest! {
912            #[test]
913            fn optimized_spread_matches_pairwise_reference(
914                entries in prop::collection::vec((0_u8..16, 1_usize..4_000, 1_usize..500), 0..80)
915            ) {
916                // More paths than the small file set holds, so a group can
917                // move to the large path. Two spellings name an earlier path.
918                let paths = [
919                    "src/a.ts",
920                    "src/b.ts",
921                    "packages/a/src/c.ts",
922                    "packages/b/src/d.ts",
923                    "packages/b/test/e.ts",
924                    "/repo/apps/web/f.ts",
925                    "/repo/crates/core/g.ts",
926                    "h.ts",
927                    "src//a.ts",
928                    "./src/b.ts",
929                    "packages/c/src/i.ts",
930                    "packages/c/src/deep/j.ts",
931                    "apps/web/k.ts",
932                    "apps/api/src/l.ts",
933                    "tools/m.ts",
934                    "n.ts",
935                ];
936                let instances = entries
937                    .into_iter()
938                    .map(|(path, start, len)| instance(paths[usize::from(path)], start, start + len))
939                    .collect::<Vec<_>>();
940
941                prop_assert_eq!(
942                    clone_group_spread(&instances),
943                    pairwise_clone_group_spread(&instances)
944                );
945            }
946        }
947    }
948
949    #[test]
950    fn ranking_uses_spread_without_overriding_a_larger_base_score() {
951        let distant = group(
952            vec![
953                instance("/repo/a/b/c/d/e/a.ts", 1, 10),
954                instance("/repo/f/g/h/i/j/b.ts", 1, 10),
955            ],
956            100,
957            10,
958        );
959        let slightly_larger_local = group(
960            vec![
961                instance("/repo/src/a.ts", 1, 10),
962                instance("/repo/src/b.ts", 1, 10),
963            ],
964            116,
965            10,
966        );
967        assert_eq!(distant.spread(), 10);
968        assert_eq!(
969            compare_clone_groups(&distant, &slightly_larger_local),
970            Ordering::Greater
971        );
972
973        let slightly_smaller_local = group(
974            vec![
975                instance("/repo/src/c.ts", 1, 10),
976                instance("/repo/src/d.ts", 1, 10),
977            ],
978            114,
979            10,
980        );
981        assert_eq!(
982            compare_clone_groups(&distant, &slightly_smaller_local),
983            Ordering::Less
984        );
985    }
986
987    #[test]
988    fn report_sort_uses_canonical_location_as_final_tiebreaker() {
989        let later = group(
990            vec![
991                instance("/repo/src/z.ts", 1, 10),
992                instance("/repo/src/y.ts", 1, 10),
993            ],
994            100,
995            10,
996        );
997        let earlier = group(
998            vec![
999                instance("/repo/src/a.ts", 20, 29),
1000                instance("/repo/src/b.ts", 20, 29),
1001            ],
1002            100,
1003            10,
1004        );
1005        let mut report = DuplicationReport {
1006            clone_groups: vec![later, earlier],
1007            ..DuplicationReport::default()
1008        };
1009        report.sort();
1010        assert_eq!(
1011            report.clone_groups[0].instances[0].file,
1012            Path::new("/repo/src/a.ts")
1013        );
1014    }
1015
1016    #[test]
1017    fn exact_clone_similarity_is_omitted() {
1018        let clone = group(Vec::new(), 100, 10);
1019        let value = serde_json::to_value(clone).unwrap();
1020        assert!(value.get("similarity").is_none());
1021    }
1022
1023    #[test]
1024    fn near_clone_similarity_is_serialized() {
1025        let mut clone = group(Vec::new(), 100, 10);
1026        clone.similarity = Some(0.85);
1027        let value = serde_json::to_value(clone).unwrap();
1028        assert_eq!(value["similarity"], 0.85);
1029    }
1030
1031    #[test]
1032    fn optional_duplication_stats_are_omitted_at_zero() {
1033        let empty = serde_json::to_value(DuplicationStats::default()).unwrap();
1034        assert!(empty.get("clone_groups_ignored").is_none());
1035        assert!(empty.get("near_candidates_skipped").is_none());
1036
1037        let populated = serde_json::to_value(DuplicationStats {
1038            clone_groups_ignored: 2,
1039            near_candidates_skipped: 3,
1040            ..DuplicationStats::default()
1041        })
1042        .unwrap();
1043        assert_eq!(populated["clone_groups_ignored"], 2);
1044        assert_eq!(populated["near_candidates_skipped"], 3);
1045    }
1046}