codehelion_core/structural/
analysis.rs

1use super::{
2    BTreeMap, BTreeSet, BuildVariant, FileFeatures, GroupDetail, GroupingUnit, ResolvedTypes,
3    SimilarityEdge, StructuralConfig, StructuralNearMiss, StructuralRegion, StructuralReport,
4    StructuralStats, StructuralUnit, SyntaxIrFile, Unit, UnitEvidence, VerifyConfig, candidate,
5    confirm_regions, control_flow, drop_subsumed, features, flatten_units, group_detail, grouping,
6    grow_runs, lift_to_unit_pairs, maximal, near_match, sweep_siblings, token_count_meets_minimum,
7    unit_evidence, unit_meets_minimum, unrepresented_pairs, verify, view,
8};
9
10/// Run the structural pipeline over parsed IR files.
11///
12/// The result is a pure, deterministic function of the inputs and the build
13/// variant.
14#[must_use]
15pub fn analyze(
16    files: &[SyntaxIrFile],
17    variant: &BuildVariant,
18    config: &StructuralConfig,
19) -> StructuralReport {
20    analyze_resolved(files, variant, config, &ResolvedTypes::default())
21}
22
23/// [`analyze`] with what a compiler resolved about the same files.
24///
25/// The stages are the same ones; what changes is that the type dimension of
26/// every comparison is measured instead of absent. Passing nothing resolved is
27/// exactly [`analyze`], which is the modes that run no compiler.
28#[must_use]
29#[allow(
30    clippy::too_many_lines,
31    reason = "the structural pipeline deliberately keeps its ordered stages together"
32)]
33pub fn analyze_resolved(
34    files: &[SyntaxIrFile],
35    variant: &BuildVariant,
36    config: &StructuralConfig,
37    resolved: &ResolvedTypes,
38) -> StructuralReport {
39    let feature_files: Vec<FileFeatures> = files.iter().map(features::extract).collect();
40
41    let (units, offsets) = flatten_units(files, variant, config.literals, resolved);
42    let evidence = unit_evidence(&units, resolved);
43
44    // Stage: candidate extraction (exact seeds, near matches and shared
45    // control-flow skeletons), lifted to distinct unit pairs.
46    let candidate = candidate::generate(&feature_files, &config.candidate);
47    let near = near_match::generate(&feature_files, &config.near_match);
48    let skeleton = control_flow::generate(&feature_files, &config.control_flow);
49    let near_misses = near
50        .near_misses
51        .iter()
52        .map(|near_miss| StructuralNearMiss {
53            a: offsets[near_miss.a.file] + near_miss.a.unit,
54            b: offsets[near_miss.b.file] + near_miss.b.unit,
55            estimated_jaccard: near_miss.estimated_jaccard,
56        })
57        .collect();
58    let lifted = lift_to_unit_pairs(
59        &candidate,
60        &near,
61        &skeleton,
62        &units,
63        &offsets,
64        &feature_files,
65        config.max_shape_divergence,
66    );
67    let mut pairs = lifted.pairs;
68    let candidate_pairs = pairs.len();
69    pairs.retain(|&(left, right)| {
70        unit_meets_minimum(&units[left], config.min_clone_tokens)
71            && unit_meets_minimum(&units[right], config.min_clone_tokens)
72    });
73    let below_min_clone_token_pairs = candidate_pairs.saturating_sub(pairs.len());
74
75    // Stage: fold the window seeds into the maximal shared runs they describe,
76    // then confirm each candidate run against the tokens it actually covers.
77    let candidate_regions = maximal::consolidate(&candidate.pairs, &config.maximal);
78    let (mut confirmed, mut dropped) = confirm_regions(
79        &candidate_regions.shared,
80        files,
81        &offsets,
82        variant,
83        config.literals,
84    );
85    let merged = grow_runs(
86        &mut confirmed,
87        &mut dropped,
88        files,
89        &offsets,
90        variant,
91        config.literals,
92    );
93    let mut regions: Vec<StructuralRegion> =
94        confirmed.into_iter().map(|entry| entry.region).collect();
95    let subsumed = drop_subsumed(&mut regions);
96    let confirmed_regions = regions.len();
97    regions.retain(|region| {
98        region.occurrences.iter().all(|occurrence| {
99            token_count_meets_minimum(
100                occurrence.token_end.saturating_sub(occurrence.token_start),
101                config.min_clone_tokens,
102            )
103        })
104    });
105    let below_min_clone_token_regions = confirmed_regions.saturating_sub(regions.len());
106
107    // Stage: precise verification of each distinct unit pair.
108    let verification = verify_pairs(
109        &pairs,
110        &units,
111        files,
112        &feature_files,
113        &evidence,
114        &config.verify,
115        config.verification_budget,
116    );
117    // The precise verifier has consumed the lifted candidates. Keeping this
118    // potentially large set alive through grouping and reporting needlessly
119    // raises the scan's peak memory.
120    drop(pairs);
121    let edges = verification.edges;
122
123    // Stage: medoid grouping over the verified pairs.
124    let grouping_units: Vec<GroupingUnit> = units
125        .iter()
126        .map(|unit| GroupingUnit {
127            // The component ceiling must not cut a content-equivalence class
128            // into several groups: structural group identity uses normalized
129            // content for non-Type-1 findings, and raw keys would therefore
130            // mint duplicate fingerprints after a cut.
131            key: *unit.normalized_content.as_bytes(),
132        })
133        .collect();
134    let groups = grouping::group(&grouping_units, &edges, &config.grouping);
135
136    // Per-group reporting detail: the stable clone id and the medoid-to-member
137    // similarity breakdowns (re-run against the chosen medoid, deterministic).
138    let details: Vec<GroupDetail> = groups
139        .groups
140        .iter()
141        .map(|group| {
142            group_detail(
143                group,
144                &units,
145                files,
146                &feature_files,
147                &evidence,
148                variant,
149                config,
150            )
151        })
152        .collect();
153
154    let (unrepresented, described_pairs, severed_pairs) =
155        unrepresented_pairs(&edges, &groups, &units, files, variant);
156    // This is intentionally after primary grouping and unrepresented-pair
157    // carry-out. It only inspects ungrouped units and cannot add an edge or a
158    // member to `groups`.
159    let (siblings, sibling_stats) =
160        sweep_siblings(&groups, &units, files, &feature_files, &evidence, config);
161
162    let stats = StructuralStats {
163        files: files.len(),
164        units: units.len(),
165        candidate: candidate.stats,
166        near_match: near.stats,
167        control_flow: skeleton.stats,
168        maximal: candidate_regions.stats,
169        regions: regions.len(),
170        region_singletons: dropped.singletons,
171        region_overlapping: dropped.overlapping,
172        region_adjoining: dropped.adjoining,
173        region_subsumed: subsumed,
174        region_merged: merged,
175        below_min_clone_token_regions,
176        nested_pairs: lifted.nested,
177        alternative_pairs: lifted.alternatives,
178        divergent_shape_pairs: lifted.divergent,
179        below_min_clone_token_pairs,
180        unit_pairs: candidate_pairs.saturating_sub(below_min_clone_token_pairs),
181        verification_budget_dropped: verification.dropped,
182        verified_pairs: edges.len(),
183        unrepresented_pairs: unrepresented.len(),
184        described_pairs,
185        severed_pairs,
186        grouping: groups.stats.clone(),
187        siblings: sibling_stats,
188    };
189
190    StructuralReport {
191        units: reported(&units),
192        groups,
193        regions,
194        details,
195        unrepresented,
196        siblings,
197        near_misses,
198        stats,
199    }
200}
201
202/// The analysed units as the report carries them: what a reader can point at,
203/// without the working state the pipeline needed to get there.
204fn reported(units: &[Unit]) -> Vec<StructuralUnit> {
205    units
206        .iter()
207        .map(|unit| StructuralUnit {
208            file: unit.file,
209            kind: unit.kind,
210            range: unit.range,
211            start_line: unit.lines.0,
212            end_line: unit.lines.1,
213            token_start: unit.tokens.0,
214            token_end: unit.tokens.1,
215            name: unit.name.clone(),
216            boilerplate: unit.boilerplate,
217            test_code: unit.test_code,
218            test_code_evidence: unit.test_code_evidence,
219            fingerprint: unit.fingerprint,
220            content: unit.content,
221            normalized_content: unit.normalized_content,
222        })
223        .collect()
224}
225
226/// Verify every candidate unit pair, keeping the ones a verdict accepts.
227///
228/// A pair the verifier leaves unclassified is not an edge: grouping works over
229/// accepted pairs only.
230struct VerificationSet {
231    /// Candidate pairs the verifier accepted.
232    edges: Vec<SimilarityEdge>,
233    /// Candidate pairs the resource ceiling intentionally left unexamined.
234    dropped: usize,
235}
236
237fn verify_pairs(
238    pairs: &BTreeSet<(usize, usize)>,
239    units: &[Unit],
240    files: &[SyntaxIrFile],
241    feature_files: &[FileFeatures],
242    evidence: &UnitEvidence,
243    config: &VerifyConfig,
244    budget: usize,
245) -> VerificationSet {
246    let mut edges: Vec<SimilarityEdge> = Vec::new();
247    let (selected, dropped) = verification_components(pairs, budget);
248    for (a, b) in selected {
249        let view_a = view(a, units, files, feature_files, evidence);
250        let view_b = view(b, units, files, feature_files, evidence);
251        let verdict = verify::verify(&view_a, &view_b, config);
252        if let (Some(class), Some(confidence)) = (verdict.class, verdict.confidence) {
253            edges.push(SimilarityEdge {
254                a,
255                b,
256                similarity: verdict.breakdown.composite,
257                breakdown: Some(verdict.breakdown),
258                class,
259                confidence,
260            });
261        }
262    }
263    VerificationSet { edges, dropped }
264}
265
266/// Select complete candidate components for verification under `budget`.
267fn verification_components(
268    pairs: &BTreeSet<(usize, usize)>,
269    budget: usize,
270) -> (Vec<(usize, usize)>, usize) {
271    let mut adjacent = BTreeMap::<usize, Vec<usize>>::new();
272    for &(a, b) in pairs {
273        adjacent.entry(a).or_default().push(b);
274        adjacent.entry(b).or_default().push(a);
275    }
276    let mut visited = BTreeSet::new();
277    let mut remaining = budget;
278    let mut dropped = 0;
279    let mut selected = Vec::new();
280    for &root in adjacent.keys() {
281        if !visited.insert(root) {
282            continue;
283        }
284        let mut stack = vec![root];
285        let mut members = BTreeSet::from([root]);
286        while let Some(member) = stack.pop() {
287            for &next in &adjacent[&member] {
288                if visited.insert(next) {
289                    members.insert(next);
290                    stack.push(next);
291                }
292            }
293        }
294        let component: Vec<(usize, usize)> = pairs
295            .iter()
296            .copied()
297            .filter(|(a, b)| members.contains(a) && members.contains(b))
298            .collect();
299        if component.len() > remaining {
300            dropped += component.len();
301            continue;
302        }
303        remaining -= component.len();
304        selected.extend(component);
305    }
306    (selected, dropped)
307}
308
309#[cfg(test)]
310mod tests {
311    use super::*;
312
313    #[test]
314    fn verification_budget_never_cuts_through_a_connected_candidate_family() {
315        let pairs = BTreeSet::from([(0, 1), (1, 2), (3, 4)]);
316        let (selected, dropped) = verification_components(&pairs, 1);
317
318        assert_eq!(selected, vec![(3, 4)]);
319        assert_eq!(dropped, 2);
320    }
321}
codehelion_core/structural/analysis.rs

codehelion_core/structural/
analysis.rs
