wowlab_tidy/languages/rust/rules/api/
similar_fns.rs

1#[cfg(test)]
2use googletest::prelude::*;
3use wowlab_types::sim::FastMap;
4
5use crate::{
6    Example, Violation,
7    languages::workspace::{FunctionRecord, WorkspaceCtx},
8    matches_ignore, violation,
9};
10
11const MIN_SHARED_SHINGLES: usize = 5;
12const PERCENT_DENOMINATOR: usize = 100;
13const CANDIDATE_PERCENT: usize = 10;
14
15#[rustfmt::skip]
16const EXAMPLES: &[Example] = &[
17    Example {
18        label: "exact function bodies",
19        code: "fn one(a: i32) -> i32 { let b = a + 1; let c = b + 2; let d = c + 3; let e = d + 4; let f = e + 5; let g = f + 6; let h = g + 7; let i = h + 8; let j = i + 9; let k = j + 10; k }\nfn two(a: i32) -> i32 { let b = a + 1; let c = b + 2; let d = c + 3; let e = d + 4; let f = e + 5; let g = f + 6; let h = g + 7; let i = h + 8; let j = i + 9; let k = j + 10; k }",
20        pass: false,
21    },
22    Example {
23        label: "near function bodies",
24        code: "fn one(a: i32) -> i32 { let b = a + 1; let c = b + 2; let d = c + 3; let e = d + 4; let f = e + 5; let g = f + 6; let h = g + 7; let i = h + 8; let j = i + 9; let k = j + 10; k }\nfn two(a: i32) -> i32 { let b = a + 1; let c = b + 2; let d = c + 3; let e = d + 4; let f = e + 5; let g = f + 6; let h = g + 8; let i = h + 8; let j = i + 9; let k = j + 10; k }",
25        pass: false,
26    },
27    Example {
28        label: "short bodies are exempt",
29        code: "fn one() -> i32 { 1 }\nfn two() -> i32 { 1 }",
30        pass: true,
31    },
32];
33
34crate::workspace_rule!(
35    similar_fns,
36    "Find exact and near duplicate function bodies; full-workspace runs are authoritative.",
37    "Clone detection identifies behavior that should usually be shared behind one implementation.",
38    Low,
39    params {
40        min_tokens: i64 = 40,
41        jaccard_percent: i64 = 85
42    },
43);
44
45#[derive(Clone, Copy)]
46struct Located<'a> {
47    rel: &'a str,
48    record: &'a FunctionRecord,
49}
50
51fn check_similar_fns(ctx: &WorkspaceCtx<'_>) -> Vec<Violation> {
52    let min_tokens = ctx.config.get_usize("rust_similar_fns", &PARAMS[0]);
53    let jaccard_percent = ctx.config.get_usize("rust_similar_fns", &PARAMS[1]);
54    let records: Vec<Located<'_>> = ctx
55        .files
56        .iter()
57        .filter(|file| !matches_ignore(&file.rel, ctx.config.ignore_patterns("rust_similar_fns")))
58        .flat_map(|file| {
59            file.functions
60                .iter()
61                .filter(|function| function.body_token_count >= min_tokens)
62                .map(|record| Located {
63                    rel: &file.rel,
64                    record,
65                })
66        })
67        .collect();
68    let mut index = FastMap::<_, Vec<usize>>::default();
69
70    for (record_index, located) in records.iter().enumerate() {
71        for fingerprint in &located.record.body_shingles {
72            index.entry(*fingerprint).or_default().push(record_index);
73        }
74    }
75
76    let mut shared = FastMap::<(usize, usize), usize>::default();
77
78    for members in index.values() {
79        for (position, left) in members.iter().enumerate() {
80            for right in members.iter().skip(position + 1) {
81                *shared.entry((*left, *right)).or_default() += 1;
82            }
83        }
84    }
85
86    shared
87        .into_iter()
88        .filter_map(|((left_index, right_index), shared_count)| {
89            let left = *records.get(left_index)?;
90            let right = *records.get(right_index)?;
91            let left_shingles = &left.record.body_shingles;
92            let right_shingles = &right.record.body_shingles;
93            let smaller = left_shingles.len().min(right_shingles.len());
94            let threshold = MIN_SHARED_SHINGLES.max(
95                smaller
96                    .saturating_mul(CANDIDATE_PERCENT)
97                    .div_ceil(PERCENT_DENOMINATOR),
98            );
99
100            if shared_count < threshold {
101                return None;
102            }
103
104            let exact = left.record.body_checksum == right.record.body_checksum;
105            let union = left_shingles
106                .len()
107                .saturating_add(right_shingles.len())
108                .saturating_sub(shared_count);
109            let near = shared_count.saturating_mul(PERCENT_DENOMINATOR)
110                >= union.saturating_mul(jaccard_percent);
111
112            if !exact && !near {
113                return None;
114            }
115
116            let (anchor, counterpart) =
117                if (left.rel, left.record.line) > (right.rel, right.record.line) {
118                    (left, right)
119                } else {
120                    (right, left)
121                };
122
123            Some(violation(
124                anchor.rel,
125                anchor.record.line,
126                format!(
127                    "{} function clone ({} shared shingles); similar to {}:{} ({})",
128                    if exact { "exact" } else { "near" },
129                    shared_count,
130                    counterpart.rel,
131                    counterpart.record.line,
132                    counterpart.record.name
133                ),
134            ))
135        })
136        .collect()
137}
138
139crate::tidy_workspace_test!(check_similar_fns, {
140    crate::example_tests!(EXAMPLES, check_similar_fns);
141
142    #[gtest]
143    fn configured_test_paths_are_exempt() -> Result<()> {
144        let source = EXAMPLES[0].code;
145        let violations = crate::test_support::check_workspace_sources_with_ignore(
146            &[("crates/example/src/tests.rs", source)],
147            "rust_similar_fns",
148            &["**/tests.rs"],
149            check_similar_fns,
150        );
151
152        verify_true!(violations.is_empty())?;
153
154        Ok(())
155    }
156});
wowlab_tidy/languages/rust/rules/api/similar_fns.rs

wowlab_tidy/languages/rust/rules/api/
similar_fns.rs
