fallow_engine/duplication_detector/
deepdive.rs

1//! Deep-dive helpers for the `fallow dupes --trace` inspector: a stable
2//! content fingerprint that addresses a clone group across runs, a group-level
3//! refactoring suggestion, and a best-effort "dominant identifier" name for the
4//! extracted function.
5//!
6//! These are pure functions over [`CloneInstance`] / [`CloneGroup`] so every
7//! surface (human listing, `--trace dup:<fp>` lookup, the typed JSON wrappers,
8//! and `trace_clone`) computes the same values without storing a field on the
9//! core [`CloneGroup`] struct.
10
11use std::path::Path;
12
13use fallow_config::DetectionMode;
14use rustc_hash::{FxHashMap, FxHashSet};
15use xxhash_rust::xxh3::{Xxh3, xxh3_64};
16
17use super::tokenize::{
18    FragmentTokenizationKind, FragmentTokenizationStrategy, fragment_tokenization_kind,
19};
20use super::types::{CloneGroup, CloneInstance, RefactoringKind, RefactoringSuggestion};
21
22/// Prefix marking a clone-group fingerprint addressable via `--trace`.
23pub const FINGERPRINT_PREFIX: &str = "dup:";
24
25/// Canonical identity for a clone group when assigning report-scoped handles.
26///
27/// Compact digests of canonically sorted fragments and locations make report
28/// entries addressable and provide a report-order-independent collision-suffix
29/// order without retaining a second copy of every source fragment and path.
30/// The separately hashed, sorted, deduplicated normalized instance sequences
31/// provide the public content identity.
32#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
33pub struct CloneFingerprintKey {
34    fragments_digest: u128,
35    locations_digest: u128,
36    token_count: usize,
37    line_count: usize,
38    instance_count: usize,
39}
40
41const _: () = assert!(std::mem::size_of::<CloneFingerprintKey>() <= 64);
42
43impl CloneFingerprintKey {
44    /// Build a fingerprint key from clone-group parts.
45    #[must_use]
46    fn from_parts(instances: &[CloneInstance], token_count: usize, line_count: usize) -> Self {
47        Self {
48            fragments_digest: hash_distinct_fragments(instances),
49            locations_digest: hash_sorted_locations(instances),
50            token_count,
51            line_count,
52            instance_count: instances.len(),
53        }
54    }
55
56    fn from_group(group: &CloneGroup) -> Self {
57        Self::from_parts(&group.instances, group.token_count, group.line_count)
58    }
59}
60
61/// Report-scoped clone fingerprint assignment.
62///
63/// Most reports retain the short `dup:<8hex>` handle. If two report entries
64/// collide on those low 32 bits, only the colliding entries widen to
65/// `dup:<16hex>`. If a full 64-bit collision ever occurs inside one report,
66/// every entry in that collision bucket receives a deterministic numeric suffix.
67#[derive(Debug, Clone)]
68pub struct CloneFingerprintSet {
69    by_key: FxHashMap<CloneFingerprintKey, String>,
70    key_by_fingerprint: FxHashMap<String, CloneFingerprintKey>,
71}
72
73impl CloneFingerprintSet {
74    /// Assign collision-free fingerprints for the report's clone groups.
75    #[must_use]
76    pub fn from_groups(groups: &[CloneGroup]) -> Self {
77        let entries: Vec<_> = groups
78            .iter()
79            .map(|group| {
80                let key = CloneFingerprintKey::from_group(group);
81                let hash = hash_instances(&group.instances);
82                (key, hash)
83            })
84            .collect();
85        Self::from_hashed_entries(&entries)
86    }
87
88    /// Return the assigned fingerprint for a clone group.
89    #[must_use]
90    pub fn fingerprint_for_group(&self, group: &CloneGroup) -> String {
91        self.by_key
92            .get(&CloneFingerprintKey::from_group(group))
93            .cloned()
94            .unwrap_or_else(|| clone_fingerprint(&group.instances))
95    }
96
97    /// Return the config key used by `duplicates.ignoredClones` for a group.
98    #[must_use]
99    pub fn ignored_clone_key_for_group(&self, group: &CloneGroup) -> String {
100        format!(
101            "{}:{}",
102            self.fingerprint_for_group(group),
103            group.instances.len()
104        )
105    }
106
107    /// Return the assigned fingerprint for clone-group parts.
108    #[must_use]
109    pub fn fingerprint_for_parts(
110        &self,
111        instances: &[CloneInstance],
112        token_count: usize,
113        line_count: usize,
114    ) -> String {
115        let key = CloneFingerprintKey::from_parts(instances, token_count, line_count);
116        self.by_key
117            .get(&key)
118            .cloned()
119            .unwrap_or_else(|| clone_fingerprint(instances))
120    }
121
122    /// Find the group addressed by an assigned fingerprint.
123    ///
124    /// Ambiguous short handles created by low-32 collisions are intentionally
125    /// absent from the lookup table, so callers get `None` instead of the first
126    /// matching group.
127    #[must_use]
128    pub fn find_group<'a>(
129        &self,
130        groups: &'a [CloneGroup],
131        fingerprint: &str,
132    ) -> Option<&'a CloneGroup> {
133        let key = self.key_by_fingerprint.get(fingerprint)?;
134        groups
135            .iter()
136            .find(|group| CloneFingerprintKey::from_group(group) == *key)
137    }
138
139    fn from_hashed_entries(entries: &[(CloneFingerprintKey, u64)]) -> Self {
140        let mut short_counts: FxHashMap<u32, usize> = FxHashMap::default();
141        let mut full_counts: FxHashMap<u64, usize> = FxHashMap::default();
142        for (_, hash) in entries {
143            *short_counts.entry(*hash as u32).or_insert(0) += 1;
144            *full_counts.entry(*hash).or_insert(0) += 1;
145        }
146
147        let mut sorted_entries = entries.to_vec();
148        sorted_entries.sort_unstable_by(|(left_key, left_hash), (right_key, right_hash)| {
149            left_key
150                .cmp(right_key)
151                .then_with(|| left_hash.cmp(right_hash))
152        });
153
154        let mut full_ordinals: FxHashMap<u64, usize> = FxHashMap::default();
155        let mut ambiguous_short_handles: FxHashSet<String> = FxHashSet::default();
156        let mut by_key = FxHashMap::default();
157        let mut key_by_fingerprint = FxHashMap::default();
158
159        for (key, hash) in &sorted_entries {
160            let short = *hash as u32;
161            let short_handle = format!("{FINGERPRINT_PREFIX}{short:08x}");
162            let fingerprint = if short_counts.get(&short).copied().unwrap_or(0) == 1 {
163                short_handle
164            } else {
165                ambiguous_short_handles.insert(short_handle);
166                let full_handle = format!("{FINGERPRINT_PREFIX}{hash:016x}");
167                if full_counts.get(hash).copied().unwrap_or(0) == 1 {
168                    full_handle
169                } else {
170                    let ordinal = full_ordinals.entry(*hash).or_insert(0);
171                    *ordinal += 1;
172                    format!("{full_handle}-{ordinal}")
173                }
174            };
175
176            key_by_fingerprint.insert(fingerprint.clone(), key.clone());
177            by_key.insert(key.clone(), fingerprint);
178        }
179
180        for handle in ambiguous_short_handles {
181            key_by_fingerprint.remove(&handle);
182        }
183
184        Self {
185            by_key,
186            key_by_fingerprint,
187        }
188    }
189}
190
191/// Compute a mode-independent normalized short content fingerprint for a clone
192/// group from all distinct instance token sequences.
193///
194/// Whitespace, comments, and line endings are absent from the normalized token
195/// hashes. Sorting and deduplicating sequences makes the fingerprint independent
196/// of instance order while ensuring a token edit in any distinct instance
197/// changes the group identity. Instance count is deliberately excluded and is
198/// appended separately by [`CloneFingerprintSet::ignored_clone_key_for_group`].
199///
200/// Use [`CloneFingerprintSet`] for user-facing report output, since it widens
201/// only the rare colliding handles while preserving this short form for the
202/// common case.
203///
204/// Hashes the empty string for an empty group (never produced by the detector,
205/// which guarantees `>= 2` instances), so the result is still a well-formed
206/// `dup:<8hex>` handle.
207#[must_use]
208pub fn clone_fingerprint(instances: &[CloneInstance]) -> String {
209    fingerprint_for_hash(hash_instances(instances))
210}
211
212/// Compute the fingerprint directly from a representative source fragment.
213///
214/// Use when the instances are wrapped (e.g. `--group-by` attributed instances)
215/// but the representative fragment is the same as the bare clone group's, so the
216/// fingerprint matches the top-level `clone_groups[].fingerprint` for the clone.
217#[must_use]
218pub fn fingerprint_for_fragment(fragment: &str) -> String {
219    let sequence = normalized_fragment_sequence(Path::new("fragment.ts"), fragment);
220    fingerprint_for_hash(hash_normalized_sequences(&[sequence]))
221}
222
223fn hash_distinct_fragments(instances: &[CloneInstance]) -> u128 {
224    let mut fragments = instances
225        .iter()
226        .map(|instance| instance.fragment.as_str())
227        .collect::<Vec<_>>();
228    fragments.sort_unstable();
229    fragments.dedup();
230
231    let mut hasher = Xxh3::new();
232    for fragment in fragments {
233        update_hash_bytes(&mut hasher, fragment.as_bytes());
234    }
235    hasher.digest128()
236}
237
238fn hash_sorted_locations(instances: &[CloneInstance]) -> u128 {
239    let mut locations = instances
240        .iter()
241        .map(|instance| {
242            (
243                instance.file.as_path(),
244                instance.start_line,
245                instance.end_line,
246            )
247        })
248        .collect::<Vec<_>>();
249    locations.sort_unstable();
250
251    let mut hasher = Xxh3::new();
252    for (path, start_line, end_line) in locations {
253        update_hash_bytes(&mut hasher, path.as_os_str().as_encoded_bytes());
254        hasher.update(&start_line.to_le_bytes());
255        hasher.update(&end_line.to_le_bytes());
256    }
257    hasher.digest128()
258}
259
260fn update_hash_bytes(hasher: &mut Xxh3, bytes: &[u8]) {
261    hasher.update(&bytes.len().to_le_bytes());
262    hasher.update(bytes);
263}
264
265fn hash_instances(instances: &[CloneInstance]) -> u64 {
266    let mut sequences = distinct_fragment_inputs(instances)
267        .into_iter()
268        .map(|(kind, fragment)| normalized_fragment_sequence(kind.path(), fragment))
269        .collect::<Vec<_>>();
270    sequences.sort_unstable();
271    sequences.dedup();
272    hash_normalized_sequences(&sequences)
273}
274
275fn distinct_fragment_inputs(instances: &[CloneInstance]) -> Vec<(FragmentTokenizationKind, &str)> {
276    let mut fragments = instances
277        .iter()
278        .map(|instance| {
279            (
280                fragment_tokenization_kind(
281                    &instance.file,
282                    FragmentTokenizationStrategy::Fingerprint,
283                ),
284                instance.fragment.as_str(),
285            )
286        })
287        .collect::<Vec<_>>();
288    fragments.sort_unstable();
289    fragments.dedup();
290    fragments
291}
292
293fn normalized_fragment_sequence(path: &Path, fragment: &str) -> Vec<u64> {
294    let tokens = super::tokenize::tokenize_file(path, fragment, false);
295    super::normalize::normalize_and_hash(&tokens.tokens, DetectionMode::Strict)
296        .into_iter()
297        .map(|token| token.hash)
298        .collect()
299}
300
301fn hash_normalized_sequences(sequences: &[Vec<u64>]) -> u64 {
302    let byte_len = sequences
303        .iter()
304        .map(|sequence| sequence.len().saturating_add(1))
305        .sum::<usize>()
306        .saturating_mul(std::mem::size_of::<u64>());
307    let mut bytes = Vec::with_capacity(byte_len);
308    for sequence in sequences {
309        bytes.extend_from_slice(&(sequence.len() as u64).to_le_bytes());
310        for hash in sequence {
311            bytes.extend_from_slice(&hash.to_le_bytes());
312        }
313    }
314    xxh3_64(&bytes)
315}
316
317fn fingerprint_for_hash(hash: u64) -> String {
318    format!("{FINGERPRINT_PREFIX}{:08x}", hash as u32)
319}
320
321/// Build a per-group `ExtractFunction` refactoring suggestion.
322///
323/// Mirrors the per-group branch of the families suggestion generator:
324/// the savings is `(instances - 1)` copies of the group's line count, since one
325/// copy survives as the extracted function and the rest collapse to call sites.
326#[must_use]
327pub fn group_refactoring_suggestion(group: &CloneGroup) -> RefactoringSuggestion {
328    let estimated_savings = group.line_count * group.instances.len().saturating_sub(1);
329    RefactoringSuggestion {
330        kind: RefactoringKind::ExtractFunction,
331        description: format!(
332            "Extract the shared {}-line block into one function and call it from {} sites",
333            group.line_count,
334            group.instances.len(),
335        ),
336        estimated_savings,
337    }
338}
339
340/// Best-effort name for the extracted function, derived from the most frequent
341/// non-generic identifier in the representative fragment.
342///
343/// Returns `None` when the dominant identifier is generic (`data`, `result`,
344/// loop counters), appears only once, or ties with another, so absence is the
345/// low-confidence signal for both human and agent consumers. This is a
346/// lexical heuristic over the raw fragment, not an AST analysis; it is advisory
347/// and consumers should verify before applying.
348#[must_use]
349pub fn dominant_identifier(group: &CloneGroup) -> Option<String> {
350    let fragment = group.instances.first().map(|inst| inst.fragment.as_str())?;
351    let mut counts: FxHashMap<&str, usize> = FxHashMap::default();
352    for word in identifier_words(fragment) {
353        if is_generic_identifier(word) {
354            continue;
355        }
356        *counts.entry(word).or_insert(0) += 1;
357    }
358
359    let mut candidates: Vec<_> = counts
360        .into_iter()
361        .map(|(word, count)| IdentifierCandidate {
362            word,
363            count,
364            score: identifier_score(word, count),
365        })
366        .collect();
367    candidates.sort_by(|a, b| {
368        b.score
369            .cmp(&a.score)
370            .then_with(|| b.count.cmp(&a.count))
371            .then_with(|| a.word.cmp(b.word))
372    });
373
374    let best = candidates.first()?;
375    if best.count < 2 {
376        return None;
377    }
378
379    let runner_up = candidates.get(1);
380    if runner_up.is_some_and(|next| best.score.saturating_sub(next.score) < 2) {
381        return None;
382    }
383
384    if is_plain_single_token(best.word) {
385        let next_count = runner_up.map_or(0, |candidate| candidate.count);
386        if best.count < 3 || best.count < next_count + 2 {
387            return None;
388        }
389    }
390
391    Some(best.word.to_string())
392}
393
394#[derive(Debug)]
395struct IdentifierCandidate<'a> {
396    word: &'a str,
397    count: usize,
398    score: usize,
399}
400
401fn identifier_score(word: &str, count: usize) -> usize {
402    let quality_bonus = if has_identifier_separator_or_case_transition(word) {
403        5
404    } else if word.chars().count() >= 8 {
405        2
406    } else {
407        0
408    };
409    count * 5 + quality_bonus
410}
411
412fn is_plain_single_token(word: &str) -> bool {
413    !has_identifier_separator_or_case_transition(word) && word.chars().count() < 8
414}
415
416fn has_identifier_separator_or_case_transition(word: &str) -> bool {
417    if word.contains('_') || word.contains('$') {
418        return true;
419    }
420
421    let mut previous = None;
422    for ch in word.chars() {
423        if previous.is_some_and(|prev: char| prev.is_ascii_lowercase() && ch.is_ascii_uppercase()) {
424            return true;
425        }
426        previous = Some(ch);
427    }
428    false
429}
430
431/// Yield identifier-like words (`[A-Za-z_$][A-Za-z0-9_$]*`) from raw source.
432fn identifier_words(source: &str) -> impl Iterator<Item = &str> {
433    source
434        .split(|c: char| !(c.is_ascii_alphanumeric() || c == '_' || c == '$'))
435        .filter(|word| {
436            !word.is_empty()
437                && word
438                    .chars()
439                    .next()
440                    .is_some_and(|c| c.is_ascii_alphabetic() || c == '_' || c == '$')
441        })
442}
443
444/// Identifiers too generic to make a useful extracted-function name, plus the
445/// reserved words that show up as bare tokens in a fragment.
446const GENERIC_IDENTIFIERS: &[&str] = &[
447    "data",
448    "result",
449    "results",
450    "item",
451    "items",
452    "value",
453    "values",
454    "val",
455    "obj",
456    "object",
457    "arr",
458    "array",
459    "list",
460    "map",
461    "set",
462    "key",
463    "keys",
464    "tmp",
465    "temp",
466    "acc",
467    "cur",
468    "curr",
469    "prev",
470    "next",
471    "node",
472    "el",
473    "elem",
474    "element",
475    "args",
476    "arg",
477    "opts",
478    "options",
479    "params",
480    "param",
481    "props",
482    "ctx",
483    "context",
484    "res",
485    "req",
486    "err",
487    "error",
488    "fn",
489    "cb",
490    "callback",
491    "out",
492    "input",
493    "output",
494    "name",
495    "id",
496    "index",
497    "idx",
498    "x",
499    "y",
500    "z",
501    "i",
502    "j",
503    "k",
504    "n",
505    "m",
506    "a",
507    "b",
508    "c",
509    "e",
510    "_",
511    "const",
512    "let",
513    "var",
514    "function",
515    "return",
516    "if",
517    "else",
518    "for",
519    "while",
520    "do",
521    "switch",
522    "case",
523    "break",
524    "continue",
525    "new",
526    "this",
527    "true",
528    "false",
529    "null",
530    "undefined",
531    "void",
532    "typeof",
533    "instanceof",
534    "in",
535    "of",
536    "class",
537    "extends",
538    "super",
539    "import",
540    "export",
541    "from",
542    "default",
543    "async",
544    "await",
545    "yield",
546    "type",
547    "interface",
548    "enum",
549    "as",
550    "is",
551    "keyof",
552    "readonly",
553    "public",
554    "private",
555    "protected",
556    "static",
557    "get",
558    "delete",
559    "throw",
560    "try",
561    "catch",
562    "finally",
563    "string",
564    "number",
565    "boolean",
566    "any",
567    "unknown",
568    "never",
569    "bigint",
570    "symbol",
571    "Math",
572    "JSON",
573    "Object",
574    "Array",
575    "Promise",
576    "BigInt",
577    "Number",
578    "String",
579    "Boolean",
580    "Symbol",
581    "RegExp",
582    "Date",
583];
584
585fn is_generic_identifier(word: &str) -> bool {
586    word.chars().count() == 1 || GENERIC_IDENTIFIERS.contains(&word)
587}
588
589#[cfg(test)]
590mod tests {
591    use std::path::PathBuf;
592
593    use super::*;
594
595    fn instance(fragment: &str) -> CloneInstance {
596        CloneInstance {
597            file: PathBuf::from("a.ts"),
598            start_line: 1,
599            end_line: 5,
600            start_col: 0,
601            end_col: 0,
602            fragment: fragment.to_string(),
603        }
604    }
605
606    fn group(fragments: &[&str], line_count: usize) -> CloneGroup {
607        CloneGroup {
608            instances: fragments.iter().map(|f| instance(f)).collect(),
609            token_count: 40,
610            line_count,
611            similarity: None,
612        }
613    }
614
615    #[test]
616    fn fingerprint_is_stable_and_prefixed() {
617        let g = group(&["foo(bar)", "foo(baz)"], 3);
618        let fp1 = clone_fingerprint(&g.instances);
619        let fp2 = clone_fingerprint(&g.instances);
620        assert_eq!(fp1, fp2);
621        assert!(fp1.starts_with("dup:"));
622        assert_eq!(fp1.len(), "dup:".len() + 8);
623    }
624
625    #[test]
626    fn compact_fingerprint_key_is_independent_of_instance_order() {
627        let mut original = group(&["alpha()", "beta()"], 3);
628        original.instances[0].file = PathBuf::from("src/a.ts");
629        original.instances[0].start_line = 2;
630        original.instances[1].file = PathBuf::from("src/b.ts");
631        original.instances[1].start_line = 8;
632        let mut reordered = original.clone();
633        reordered.instances.reverse();
634
635        assert_eq!(
636            CloneFingerprintKey::from_group(&original),
637            CloneFingerprintKey::from_group(&reordered)
638        );
639    }
640
641    #[test]
642    fn duplicate_fragments_are_deduplicated_before_tokenization() {
643        let mut clones = group(&["alpha()", "alpha()", "alpha()"], 2);
644        clones.instances[0].file = PathBuf::from("src/a.ts");
645        clones.instances[1].file = PathBuf::from("src/b.ts");
646        clones.instances[2].file = PathBuf::from("src/c.ts");
647        assert_eq!(distinct_fragment_inputs(&clones.instances).len(), 1);
648
649        clones.instances[2].file = PathBuf::from("src/c.css");
650        assert_eq!(
651            distinct_fragment_inputs(&clones.instances).len(),
652            2,
653            "equal source still needs separate tokenization when syntax differs"
654        );
655    }
656
657    #[test]
658    fn fingerprint_is_sibling_stable() {
659        let group_a = group(&["computeInvoiceTotal(order)", "computeInvoiceTotal(o)"], 4);
660        let before = clone_fingerprint(&group_a.instances);
661        let _group_b_edited = group(&["totallyDifferentBody()"], 2);
662        let after = clone_fingerprint(&group_a.instances);
663        assert_eq!(before, after);
664    }
665
666    #[test]
667    fn fingerprint_differs_for_different_content() {
668        let a = group(&["alpha()"], 2);
669        let b = group(&["beta()"], 2);
670        assert_ne!(
671            clone_fingerprint(&a.instances),
672            clone_fingerprint(&b.instances)
673        );
674    }
675
676    #[test]
677    fn fingerprint_ignores_formatting_comments_and_line_endings() {
678        let compact = group(
679            &["const total = left + right;", "const total = left + right;"],
680            2,
681        );
682        let formatted = group(
683            &[
684                "const  total=left + right; // reviewed\r\n",
685                "/* reviewed */\nconst total = left + right;",
686            ],
687            3,
688        );
689
690        assert_eq!(
691            clone_fingerprint(&compact.instances),
692            clone_fingerprint(&formatted.instances)
693        );
694    }
695
696    #[test]
697    fn fingerprint_changes_when_any_distinct_instance_changes_tokens() {
698        let reviewed = group(&["alpha()", "alpha()"], 2);
699        let edited = group(&["alpha()", "beta()"], 2);
700
701        assert_ne!(
702            clone_fingerprint(&reviewed.instances),
703            clone_fingerprint(&edited.instances)
704        );
705    }
706
707    #[test]
708    fn fingerprint_is_independent_of_instance_order_and_count() {
709        let two = group(&["alpha()", "beta()"], 2);
710        let three_reordered = group(&["beta()", "alpha()", "alpha()"], 2);
711
712        assert_eq!(
713            clone_fingerprint(&two.instances),
714            clone_fingerprint(&three_reordered.instances)
715        );
716
717        let two_set = CloneFingerprintSet::from_groups(std::slice::from_ref(&two));
718        let three_set = CloneFingerprintSet::from_groups(std::slice::from_ref(&three_reordered));
719        assert_ne!(
720            two_set.ignored_clone_key_for_group(&two),
721            three_set.ignored_clone_key_for_group(&three_reordered)
722        );
723    }
724
725    #[test]
726    fn fingerprint_set_widens_only_colliding_short_handles() {
727        let a = group(&["alpha()"], 2);
728        let b = group(&["beta()"], 2);
729        let c = group(&["gamma()"], 2);
730        let entries = vec![
731            (
732                CloneFingerprintKey::from_group(&a),
733                0x0000_0001_1234_5678_u64,
734            ),
735            (
736                CloneFingerprintKey::from_group(&b),
737                0x0000_0002_1234_5678_u64,
738            ),
739            (
740                CloneFingerprintKey::from_group(&c),
741                0x0000_0003_8765_4321_u64,
742            ),
743        ];
744
745        let fingerprints = CloneFingerprintSet::from_hashed_entries(&entries);
746
747        assert_eq!(
748            fingerprints.fingerprint_for_group(&a),
749            "dup:0000000112345678"
750        );
751        assert_eq!(
752            fingerprints.fingerprint_for_group(&b),
753            "dup:0000000212345678"
754        );
755        assert_eq!(fingerprints.fingerprint_for_group(&c), "dup:87654321");
756        assert!(
757            fingerprints
758                .find_group(&[a.clone(), b.clone(), c.clone()], "dup:12345678")
759                .is_none()
760        );
761        assert_eq!(
762            fingerprints
763                .find_group(&[a, b, c], "dup:0000000212345678")
764                .and_then(|group| group.instances.first())
765                .map(|inst| inst.fragment.as_str()),
766            Some("beta()")
767        );
768    }
769
770    #[test]
771    fn fingerprint_set_suffixes_full_hash_collisions() {
772        let a = group(&["alpha()"], 2);
773        let b = group(&["beta()"], 2);
774        let mut entries = vec![
775            (
776                CloneFingerprintKey::from_group(&a),
777                0x0000_0001_1234_5678_u64,
778            ),
779            (
780                CloneFingerprintKey::from_group(&b),
781                0x0000_0001_1234_5678_u64,
782            ),
783        ];
784
785        let fingerprints = CloneFingerprintSet::from_hashed_entries(&entries);
786        entries.reverse();
787        let reversed_fingerprints = CloneFingerprintSet::from_hashed_entries(&entries);
788
789        let a_fingerprint = fingerprints.fingerprint_for_group(&a);
790        let b_fingerprint = fingerprints.fingerprint_for_group(&b);
791        assert_eq!(
792            a_fingerprint,
793            reversed_fingerprints.fingerprint_for_group(&a)
794        );
795        assert_eq!(
796            b_fingerprint,
797            reversed_fingerprints.fingerprint_for_group(&b)
798        );
799        let mut assigned = vec![a_fingerprint, b_fingerprint];
800        assigned.sort_unstable();
801        assert_eq!(
802            assigned,
803            ["dup:0000000112345678-1", "dup:0000000112345678-2"]
804        );
805        assert!(
806            fingerprints
807                .find_group(&[a.clone(), b.clone()], "dup:12345678")
808                .is_none()
809        );
810        assert!(
811            fingerprints
812                .find_group(&[a, b], "dup:0000000112345678")
813                .is_none()
814        );
815    }
816
817    #[test]
818    fn group_suggestion_savings_is_lines_times_extra_copies() {
819        let g = group(&["x", "x", "x"], 10); // 3 instances, 10 lines
820        let suggestion = group_refactoring_suggestion(&g);
821        assert_eq!(suggestion.kind, RefactoringKind::ExtractFunction);
822        assert_eq!(suggestion.estimated_savings, 20); // 10 * (3 - 1)
823    }
824
825    #[test]
826    fn dominant_identifier_picks_repeated_domain_name() {
827        let g = group(
828            &["function buildInvoice(invoice) { return invoice.total + invoice.tax; }"],
829            3,
830        );
831        assert_eq!(dominant_identifier(&g).as_deref(), Some("invoice"));
832    }
833
834    #[test]
835    fn dominant_identifier_none_on_generic() {
836        let g = group(&["const data = result.map((item) => item.value);"], 3);
837        assert_eq!(dominant_identifier(&g), None);
838    }
839
840    #[test]
841    fn dominant_identifier_skips_ts_primitive_keywords_and_globals() {
842        let g = group(
843            &["const parseUser = z.string(); parseUser(z.number()); parseUser.or(z.string());"],
844            4,
845        );
846        assert_eq!(dominant_identifier(&g).as_deref(), Some("parseUser"));
847        let only_keywords = group(&["const x: string = y as string; return x as any;"], 3);
848        assert_eq!(dominant_identifier(&only_keywords), None);
849        let g_global = group(&["Math.max(Math.floor(Math.abs(v)), 0)"], 3);
850        assert_eq!(dominant_identifier(&g_global), None);
851    }
852
853    #[test]
854    fn dominant_identifier_none_on_single_letter_type_param() {
855        let g = group(
856            &["function id<T>(x: T): T { const a: T = x; return a as T; }"],
857            3,
858        );
859        assert_eq!(dominant_identifier(&g), None);
860    }
861
862    #[test]
863    fn dominant_identifier_none_on_tie() {
864        let g = group(&["alpha(); beta();"], 2); // each appears once, no count >= 2
865        assert_eq!(dominant_identifier(&g), None);
866    }
867
868    #[test]
869    fn dominant_identifier_prefers_structured_names() {
870        let g = group(
871            &["parseSchema(input); parseSchema(cache); helper(); helper();"],
872            3,
873        );
874        assert_eq!(dominant_identifier(&g).as_deref(), Some("parseSchema"));
875    }
876
877    #[test]
878    fn dominant_identifier_requires_plain_token_margin() {
879        let low_signal = group(&["schema(); schema(); parseUser();"], 3);
880        assert_eq!(dominant_identifier(&low_signal), None);
881
882        let strong = group(&["schema(); schema(); schema(); schema(); parseUser();"], 3);
883        assert_eq!(dominant_identifier(&strong).as_deref(), Some("schema"));
884    }
885
886    #[test]
887    fn dominant_identifier_is_stable_across_word_order() {
888        let first = group(
889            &["helper(); parseSchema(input); helper(); parseSchema(cache);"],
890            3,
891        );
892        let second = group(
893            &["parseSchema(input); helper(); parseSchema(cache); helper();"],
894            3,
895        );
896
897        assert_eq!(dominant_identifier(&first), dominant_identifier(&second));
898        assert_eq!(dominant_identifier(&first).as_deref(), Some("parseSchema"));
899    }
900}
fallow_engine/duplication_detector/deepdive.rs

fallow_engine/duplication_detector/
deepdive.rs
