ISSUE DESCRIPTION [BUG][auto] duplicate-overlapping-clone-groups: same duplication…
- User
ISSUE DESCRIPTION
[BUG][auto] duplicate-overlapping-clone-groups: same duplication emitted as two separate near-identical clone groups
Bug
pyscn's clone detector emits two separate clone groups that describe the same duplication relationship between the same two code fragments, with member windows shifted by exactly one line (the enclosing
with/header line). The result is a redundant clone group that inflatesclone_groupscount and the duplication percentage.This is related to but distinct from the (closed) #416
clone-overlapping-window-self-clone: #416 was about strict-subset members within a single group; here the redundancy is across two whole groups that are near-duplicates of each other.Reproducer
Repo:
Instagram/Fixit@bf8e1f55f8a606eae0f0c64bab575e84a2a608b3pyscn:v1.22.9curl -fsSL "https://codeload.github.com/Instagram/Fixit/tar.gz/HEAD" | tar -xz pyscn analyze --json --no-open Fixit-*/In the resulting
analyze.json,clone.clone_groupscontains two groups that cover the same pair of fragments insrc/fixit/tests/smoke.py:{ "id": 6, "type": 2, "similarity": 0.9692, "clones": [ {"location": {"file_path": ".../smoke.py", "start_line": 299, "end_line": 315}}, {"location": {"file_path": ".../smoke.py", "start_line": 318, "end_line": 334}} ] }, { "id": 14, "type": 2, "similarity": 0.9613, "clones": [ {"location": {"file_path": ".../smoke.py", "start_line": 298, "end_line": 315}}, {"location": {"file_path": ".../smoke.py", "start_line": 317, "end_line": 334}} ] }Both groups describe the duplication between the
subTest("lint")block and thesubTest("fix")block. Group 14's members each start exactly one line earlier than group 6's — that line is thewith self.subTest("lint"):/with self.subTest("fix"):header:with self.subTest("lint"): # line 298 (grp14 member start) with TemporaryDirectory() as td: # line 299 (grp6 member start) ... with self.subTest("fix"): # line 317 (grp14 member start) with TemporaryDirectory() as td: # line 318 (grp6 member start)Both groups end on the same lines (315 / 334). The two groups are the same logical clone reported twice at slightly different window boundaries.
Expected behavior
The clone-grouping/dedup stage should merge (or suppress) clone groups whose members are overlapping windows of the same underlying fragments, so each duplication relationship is reported once. As-is, the
clone_groupscount (10 here) and the duplication score over-count by one redundant group.Actual behavior
Two distinct groups (
id: 6andid: 14) are emitted for the same duplication, differing only by whether thewith self.subTest(...)header line is included in each member window.Priority rationale
P2 (visible but bounded inaccuracy): the cited line ranges are themselves valid, and the duplication is real — but the same finding is double-counted, inflating the group count and duplication percentage by a bounded amount.
Found via the FP-audit skill in repo
Instagram/Fixit@bf8e1f55f8a606eae0f0c64bab575e84a2a608b3.Interface
No new interfaces are introduced.
ADDITIONAL ADVICE
Since you are given a git repository, you can use git commands to simplify your work. For example, if you made a mistake and want to revert your changes, you can use
git checkout <file>to restore the file to its original state. You can also reset all changes in the repository usinggit reset --hardcommand. Additionally, you can usegit stashandgit stash popto temporarily save your changes and restore them later. Finally, you can see the changes that you've made (which will be submitted when you callsubmit) usinggit statusorgit diffcommands. However you don't need to usegit addorgit commitbefore submitting your changes. In fact,submitonly submits currently unstaged changes because it usesgit diffto get the changes that need to be submitted.CHECKLIST
Before submitting your solution, please go over the following checklist and make sure you've done everything:
- If an error was reported in the issue description, I have successfully reproduced it.
- If an error was reported in the issue description, I have confirmed that my fix resolves the error.
- I have thought about edge cases and made sure my fix handles them as well.
- I have run existing tests in the repository that might have been affected by the change I made and confirmed that they pass. I want you to list every bullet from this checklist and write your reasoning for why you think you did it or didn't need to.
Repository has been uploaded and your shell is currently at the repository root. Time to solve the issue!
(Current directory: /pyscn, current file: none) bash-$
Assistant
Let me explore the repository structure first to understand the codebase.
Assistant
Now let me understand the issue. The bug is about two separate clone groups that describe the same duplication relationship but with member windows shifted by one line. The existing
group_dedup.gohandles strict subset within a single group, but not across two whole groups.Let me look at the clone detector and understand how groups are formed and where dedup happens.
Assistant
Let me look at the grouping strategies and how clone groups are finalized in the main detection flow.
Assistant
Let me look at how fragments are extracted — why do we have overlapping fragments at 298-315 and 299-315?
Assistant
So the
withstatements create fragments. The outerwith self.subTest("lint"):(298-315) creates a fragment, and the innerwith TemporaryDirectory() as td:(299-315) creates another fragment. Both are validwithstatement fragments that meet min lines/nodes. These are overlapping (nested) fragments. ThetryCreateClonePair/isOverlappingLocationskips pairs that overlap in the same file, so the lint and fix outer-with fragments form a pair (298-315 vs 317-334), and the inner-with fragments form a separate pair (299-315 vs 318-334). These two pairs don't share fragments directly... actually wait, the outer lint (298-315) and inner lint (299-315) overlap, so they can't be paired with each other. But the outer-lint pairs with outer-fix, and inner-lint pairs with inner-fix. These are two different pairs that create two different groups.So the cross-group dedup needs to detect that group 6 and group 14 describe the same underlying duplication relationship because their members are overlapping windows.
Now, let me think about the approach. The right place to add this is a cross-group dedup pass. After
dedupeStrictSubsetGroupMembers, we should detect groups that are "overlapping window duplicates" of each other.The definition: two groups are redundant if their members are pairwise overlapping windows in the same file. More precisely, if group A and group B have the same set of files, and for each file, the members of A and the members of B are "overlapping windows of the same underlying fragment" (i.e., one covers the other, or they overlap substantially).
Let me think about the most robust definition. In the example:
- Group 6: file1: 299-315, file2: 318-334 (both in smoke.py actually, but let me re-read)
Actually both members are in the same file
smoke.py. So group 6 has 2 members both in smoke.py, and group 14 has 2 members both in smoke.py. Wait, that means both members of a group are in the same file. Hmm.Wait, but
isOverlappingLocationprevents pairs from the same file that overlap. But these two members (299-315 and 318-334) are in the same file but don't overlap (315 < 318). So they form a pair. OK so a single group here has both members in the same file.So group 6 = {smoke.py:299-315, smoke.py:318-334}, group 14 = {smoke.py:298-315, smoke.py:317-334}.
Group 14's member 298-315 covers group 6's member 299-315. Group 14's member 317-334 covers group 6's member 318-334. So group 14 ⊇ group 6 (each member of 6 is covered by a member of 14 in the same file).
So the cross-group dedup: if every member of group A is covered by some member of group B (in the same file) and they have the same number of members... they're redundant. We keep the maximal one.
Actually let me think more generally. The issue says "clone groups whose members are overlapping windows of the same underlying fragments". So the general definition: two groups are redundant if there's a one-to-one mapping between their members such that each pair of mapped members are overlapping windows of the same underlying fragment in the same file.
Let me think about a robust algorithm:
- For each pair of groups (A, B) with same size, check if they're "window duplicates".
- They're window duplicates if we can match each member of A to a unique member of B such that matched members are in the same file and their line ranges overlap (one covers the other, or they substantially overlap).
Actually, the simplest and most aligned with the existing
coversfunction: reuse thecoverslogic but across groups. Two groups are redundant if they have the same set of file memberships and there's a bijection between members where each pair is in the same file and overlapping (covers relation either way, or substantial overlap).Let me think about the definition of "overlapping windows of the same underlying fragment". Two windows are windows of the same underlying fragment if they overlap significantly — e.g., one covers the other (superset/subset) OR they overlap by more than half. But to be safe and avoid suppressing genuinely different clones, I'll use a stricter definition: the members must be in the same file and one must cover the other (using the existing
coversrelation, which handles strict superset or equal). Actually in the example, group 14 members cover group 6 members (superset). Socovers(group14member, group6member)= true.But what about partial overlap (shifted by one line but not full containment)? In the example, 298-315 covers 299-315 (strict superset, start earlier, end same). And 317-334 covers 318-334. So it's strict superset. Good, the
coversrelation handles this.But what if it's partial overlap (e.g., 298-314 vs 299-315)? Then neither covers the other. Hmm. The issue specifically mentions the one-line shift where end lines are the same. So
covers(superset) would work for this case. But to be more general, I should handle substantial overlap too.Let me think about what's safest. I'll define two members as "overlapping windows of same fragment" if they're in the same file and their ranges overlap significantly. A good measure: overlap fraction. Let me define overlap as the Jaccard or overlap coefficient of line ranges.
Actually, let me think about the most robust approach that won't suppress distinct clones. The key insight: these are clones of nested
withstatements. The members come in pairs where one is a strict superset of the other (the outerwithcontains the innerwith). So in the cross-group case, one group's members are all supersets of the other group's corresponding members.I think the cleanest, most general approach: Two groups G1 and G2 are "window-duplicate redundant" if:
- Same size
- There exists a bijection f: G1 → G2 such that for each member m in G1, m and f(m) are in the same file and their line ranges overlap substantially (e.g., overlap coefficient ≥ some threshold, or one covers the other).
When redundant, keep the one with the larger total window (the superset, group 14) — this keeps the more complete fragment. Or keep the one with higher similarity? Hmm.
Actually, let me reconsider which to keep. The expected behavior says "each duplication relationship is reported once". Either is fine. But let me think about which makes more sense. The superset (group 14, includes the
with self.subTestheader) is the more complete representation of the duplication. But the issue example shows group 6 has higher similarity (0.9692) vs group 14 (0.9613). Hmm. Let me look at existing tests to understand expectations, and look at the group_dedup_test.go.Assistant
Now let me look at the grouping strategies to understand how groups are formed and how the connected grouping works.
Assistant
Now I understand the flow. The two pairs (outer-lint ↔ outer-fix) and (inner-lint ↔ inner-fix) form two separate groups because they don't share fragments (the outer and inner of the same block overlap, so they can't be paired). So they end up as two separate connected components, hence two separate groups.
Now, the dedup needs to be across groups. Let me write a cross-group dedup function.
Let me look at how
fragmentLess,pairKeywork, and what helpers exist.Assistant
Let me build the project first and check how to run analysis.
Assistant
Now let me create a minimal reproducer Python file mimicking the structure.
Assistant
Only one group detected - my reproducer didn't trigger the issue. Let me look at the actual Fixit smoke.py to replicate the exact structure.
Assistant
The current version produces different output than the issue (which cites v1.22.9). The grouping merged the subTest blocks into one big group. Let me check the version and git log.
Assistant
The current repo is later than v1.22.9. Let me check the CHANGELOG and git history for related dedup work.
Assistant
The current repo is later than v1.22.9 and the grouping has changed so the exact repro no longer reproduces end-to-end, but the cross-group dedup logic is what I need to implement. Let me check how the duplication score and clone_groups count are computed, and how the output flows.
Assistant
Let me look at the detection flow and where groups are finalized.
Assistant
Both detection paths end with
cd.groupClonesWithStrategy(strategy). So that's where I'll add the cross-group dedup. Let me check how the duplication percentage is computed andcountUniqueCloneFragments.Assistant
So
CodeDuplicationdepends onTotalCloneGroupscount. Reducing the redundant group count reduces the duplication percentage — confirming the fix addresses both concerns. Let me look at the analyze usecase flow.Assistant
Now I understand the full flow. The fix: add a cross-group dedup that suppresses redundant overlapping-window-duplicate groups. Let me check how group IDs are used downstream.
Assistant
The group ID is preserved as-is. In the issue, the groups had IDs 6 and 14 (non-contiguous already), so non-contiguous IDs after removal are fine. But for cleanliness, let me check if IDs should be re-numbered. The issue shows groups with IDs 6 and 14 among 10 groups, so IDs are not contiguous in the output anyway (they're sorted/filtered). Actually wait, the issue shows clone_groups containing groups with ids 6 and 14 — so they're not contiguous. That means IDs are assigned during grouping and not re-numbered. So removing a group leaves a gap, which is consistent with existing behavior.
Actually, let me check the sortResults and whether IDs get reassigned. The groups from the detector have IDs from grouping (groupID counter 0,1,2...). Then they're sorted. The issue's output has ids 6 and 14 — these must be after some filtering or the IDs come from somewhere. Hmm, actually in the issue the clone_groups list has groups with ids 6 and 14 out of 10 groups. That's odd — 10 groups but ids up to 14? That suggests IDs aren't 0-9. Maybe IDs are assigned elsewhere or there's filtering.
Actually wait, maybe the groups are sorted by something and the "id" in the JSON is the position+something. Let me not worry about it — IDs are preserved as group.ID. Removing a group is fine.
Hmm, but actually let me reconsider. Let me look more carefully — maybe IDs ARE renumbered to be contiguous in the output. The issue says "clone_groups count (10 here)" and shows ids 6 and 14. If there are 10 groups with ids including 14, they're not 0-9. So either IDs are not contiguous (assigned during grouping, gaps after filtering) or there's a different ID scheme.
Let me check if there's ID renumbering in clone_service or analyze flow.
Assistant
Now I have a clear plan. Let me implement the cross-group dedup. The key insight: AST fragments are properly nested, so same-file overlap ⟹ containment. Two groups are redundant "overlapping-window duplicates" if their members can be paired one-to-one where each pair are same-file containment-overlapping windows. The narrower group is suppressed, keeping the wider (maximal) one — consistent with the within-group maximal-member rule.
Let me write the code:
Assistant
Let me edit the imports first:
Assistant
Now let me append the cross-group dedup functions at the end of the file:
Assistant
Now wire it into
groupClonesWithStrategy:Assistant
Builds. Now let me run the existing group_dedup tests and the broader analyzer tests to make sure nothing breaks.
Assistant
Existing tests pass. Now let me create a temporary test to verify the cross-group dedup handles the issue's scenario, then remove it before submitting.
Assistant
All passing. Now let me try to reproduce the end-to-end scenario. Let me check the default thresholds and try to construct a Python file that triggers two separate overlapping-window groups.
Assistant
Let me rebuild and run on the actual Fixit repo to see if my fix catches any cross-group duplicates there, and verify it doesn't break anything.
Assistant
Group count went from 8 to 7. Let me compare before/after precisely by stashing my changes to identify exactly which group was suppressed and verify it was a genuine overlapping-window duplicate.
Assistant
Comparing before/after, the only group removed is
api.py 171-183, 206-219. But there's no other api.py group in the before output. This is suspicious — let me investigate whether my fix incorrectly suppressed it, or whether there were actually two overlapping api.py groups. Let me look at api.py.Assistant
So api.py has two
tryblocks (171-183 and 206-219) that are similar. But the after output shows NO api.py group at all. Let me investigate carefully — this could be a bug. Let me re-run after and check for api explicitly, and check if there are nestediffragments forming a second api.py group.Assistant
Only ONE api.py group exists and only ONE api.py pair, yet the group was suppressed. The api.py group's signature should be unique, so it shouldn't be suppressed. There's a bug. Let me add temporary debug instrumentation to find out what's happening.
Assistant
The
overlappingWindowDuplicateGroupsreturns (winner, loser) but I named the return valueskeep, loserin the loop. Wait, in the loop I have_, loser := overlappingWindowDuplicateGroups(...). I discarded the winner. Let me fix the debug to capture both.Assistant
There are TWO api.py groups in the cross-group input (id=5 span 27, id=2 span 65), but the before run only showed one. And the debug shows only 1 suppression (9→8) but the clean fix build showed 7 groups. This suggests non-determinism. Let me run multiple times to check.
Assistant
Let me run the debug build multiple times, checking both the debug output and the final group count, to understand the variation.
Assistant
The wider api.py group (span 65) is consistently KEPT according to debug, but the
/tmp/pyscnoutput showed no api.py groups. Let me check the debug build's actual final JSON output for api.py members, and find out what the wider span-65 api.py group's members are.Assistant
The wider api.py group (sim 0.8137) is kept by my dedup but then disappears from the final JSON — likely filtered by
filterCloneGroups(similarity/type filter), whereas the narrower (sim 0.8866) would survive. There's also non-determinism in the detector. Let me check the no-fix build's determinism across runs.Assistant
The before build consistently shows 8 groups (1 narrower api.py group), while the after build's within-group input shows 9 groups (2 api.py). This is puzzling since within-group code is unchanged. Let me disable the cross-group call (keep debug) to see the true within-group output, isolating whether detection is non-deterministic.
Assistant
With cross-group disabled, no debug prints (since the debug is inside the disabled function). Let me instrument
groupClonesWithStrategyto print the within-group output directly, with cross-group disabled.Assistant
The within-group output is deterministic and contains TWO api.py groups:
{153-183, 186-219}(wider, span 65) and{171-183, 206-219}(narrower, span 27). The wider contains the narrower — they're genuine overlapping-window duplicates. Let me check which survivesfilterCloneGroupsand why, by examining the wg build's final JSON (cross-group disabled, both present).Assistant
Key finding: the wider api.py group (sim 0.8137) is filtered out by
filterCloneGroups(MinSimilarity ≈ 0.85), while the narrower (0.8866) survives. So keeping the WIDER group causes a regression (api.py not reported). Keeping the HIGHER-SIMILARITY (narrower) group avoids this and matches the issue (group 6 had higher sim 0.9692). Let me revert all debug instrumentation and change the selection to keep higher similarity.Assistant
Now re-apply the clean cross-group wiring:
Assistant
Now let me restore group_dedup.go to a clean version (remove debug, change selection to higher-similarity):
Assistant
Now let me re-add the import and the cross-group functions with the corrected selection (keep higher similarity):
Assistant
Let me clean up the
_ = keepleftover:Assistant
Wait, there's a subtlety in
overlappingWindowDuplicateGroups. I initializekeep, suppress = i1, i2(keep g1, suppress g2). Thenif preferGroup(g2, g1, i2, i1)→ keep g2, suppress g1. So I keep g1 unless g2 is preferred. preferGroup(g2, g1, i2, i1) returns true if g2 is better than g1. So if g2 better → keep g2. Correct.Now let me build and test.
Assistant
My temporary tests assumed wider-kept; now I keep higher-similarity (narrower). Let me update the temporary tests to match the corrected selection:
Assistant
All pass. Now let me rebuild and verify the end-to-end behavior on Fixit — the api.py narrower group should now survive (no regression):
Assistant
Now with "keep higher-similarity": the wider (lower-sim) api.py group is suppressed, the narrower (0.8866) is kept and survives the filter — final 8 groups, matching the before behavior (no regression). For Fixit, the wider group was already being filtered by similarity, so the count is unchanged.
To truly demonstrate the visible bug (both overlapping groups surviving the filter and double-counted), I need both groups to have sim ≥ 0.85. Let me construct a Python file where outer and inner
withblocks are both substantial and near-identical, with cross-pairs below threshold.Assistant
Only 1 group — the cross-pairs (func vs inner) merged everything. To get separate groups, the outer/inner size disparity must push cross-pair similarity below 0.65. Let me make the outer
withbody much larger than the inner.Assistant
The line ranges don't match my file. Let me clean and verify the file content:
Assistant
The inner
withblocks are below MinNodes (10), so they're not extracted as fragments — that's why only the function-level pair forms. The grouping then merges via cross-pairs. Engineering the exact cross-pair thresholds end-to-end is fragile.Instead, let me write a faithful end-to-end test through the real
groupClonesWithStrategypipeline (grouping + dedup) that replicates the issue's exact scenario at the pair level:Assistant
The end-to-end test passes through the real pipeline. Let me confirm it FAILS without my fix (to prove it reproduces the bug):
Assistant
Confirmed — without the fix, 2 groups are emitted (the bug); with the fix, 1 group. Let me re-enable the fix:
Assistant
Now let me run the full analyzer test suite and the service tests to ensure no regressions:
Assistant
All pass. Let me also run the integration tests for clones:
Assistant
Let me run the broader test suite (cmd, mcp, e2e) to be thorough:
Assistant
All tests pass. Now let me also run the e2e tests if they exist and are quick.
Let me check the e2e directory.
Assistant
Now let me run the analyze end-to-end on the Fixit repo once more to confirm the final state and check the duplication percentage / group count behavior is sane:
Assistant
The Fixit analysis is consistent (8 groups, same as before — no regression; the redundant wider api.py group is now suppressed at the dedup stage).
Let me make one solid attempt at a Python repro where BOTH overlapping groups exceed the report threshold (0.85), to demonstrate the visible double-counting and the fix. Let me first understand the similarity computation:
Assistant
I understand the similarity formula now:
sim = 1 - distance/maxSize. For cross-pairs (outer+inner vs inner) to fall below 0.65, the setup portion must be > ~35% of total. Let me construct a module-level repro with substantial setup and innerwithblocks (both ≥ MinNodes), differing by one literal:Assistant
Again only 1 group — the cross-pairs (outer vs inner) are still ≥ 0.65, merging everything. I need a much larger setup portion to push cross-pair similarity below 0.65. Let me try with a substantially larger setup:
Assistant
Still merging. Let me verify the inner
withblocks are even extracted as fragments by testing two identical non-nestedwithblocks:Assistant
The report picked up dup.py too (whole dir). Let me check the request's enabled clone types and test flat.py in isolation:
Assistant
Two identical module-level
withblocks yield 0 pairs — surprising. The analyze flow may use a different fragment extraction. Let me check how fragments are built for clone analysis:Assistant
So it uses
detector.ExtractFragmentsWithSource. Let me check that function — it might apply additional filtering (e.g., only top-level or specific nodes). Let me look at ExtractFragmentsWithSource.Assistant
Module-level
withIS detected in dup.py (29-line outer blocks) but flat.py's 9-line blocks aren't. The analyze config likely sets higher MinLines/MinNodes. Let me check:Assistant
Let me check what MinLines/MinNodes the analyze path actually uses (there may be a semantic min size):
Assistant
The flat.py non-detection is a pre-existing behavior unrelated to my fix. Let me look at the actual Fixit smoke.py structure around the issue's lines to replicate it precisely:
Assistant
This is the exact issue structure. In the current version, these merge into one group (cross-pairs exceed threshold) — the cross-group bug manifests only when cross-pairs fall below threshold, which the Go-level e2e test through the real
groupClonesWithStrategypipeline faithfully reproduces (it's the exact stage where groups are emitted).Let me verify there are no other paths that build clone groups bypassing
groupClonesWithStrategy:Assistant
Groups are only built via grouping strategies invoked through
groupClonesWithStrategy(both standard and LSH paths), so my fix is correctly placed and covers all grouping modes. Let me run the relevant existing tests once more, then remove my temporary test files.Assistant
Now let me remove the temporary test files:
Assistant
Only the two source files are modified. Let me do a final review of the complete diff:
Assistant
The diff is clean. Let me run the full relevant test suite once more after removing the temporary tests to confirm everything passes:
Assistant
Everything passes. Let me do a final clean build and end-to-end sanity check on Fixit to confirm no regression:
Assistant
No regression on Fixit (8 groups, 10% duplication — same as before; the redundant wider api.py group is now suppressed at the dedup stage). Let me do a final check for stray files and confirm the clean state:
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.
Identical first prompt
claude-sonnet-5Compare side by side →
claude-sonnet-5Compare side by side →
claude-sonnet-5Compare side by side →
claude-sonnet-5Compare side by side →
claude-sonnet-5Compare side by side →
Qwen/Qwen3.6-35B-A3BCompare side by side →
Qwen/Qwen3.6-35B-A3BCompare side by side →
Qwen/Qwen3.6-35B-A3BCompare side by side →
Qwen/Qwen3.6-35B-A3BCompare side by side →
Qwen/Qwen3.6-35B-A3BCompare side by side →
Qwen/Qwen3.5-35B-A3BCompare side by side →
Qwen/Qwen3.5-35B-A3BCompare side by side →