Detecting Duplicate Python Code Is Harder Than Comparing Text
The hard part isn't finding repeated lines. It's deciding what "the same code" actually means.
Duplicate-code detection sounds easy.
You have some source files. Find sequences of lines that occur more than once.
How hard could it be?
I asked essentially that question when I started building Arid, a duplicate-code checker for Python.
The answer, as it often is in software, was: it depends on what you mean.
What exactly is a duplicate?
Consider these two functions:
def save_customer(value):
# Persist the customer
result = serialize(value)
database.save(result)
def save_account(value):
# Store the account
result = serialize(value)
database.save(result)
As text, they're different.
As executable logic, they're the same.
If I change the comment again, is it suddenly different code?
What about the function name?
What about a docstring?
Imports?
Blank lines?
Decorators?
Formatting?
At some point duplicate-code detection stops being a string-comparison problem and becomes a language problem.
That was one of the first lessons I learned building Arid.
First, Define "Duplicate"
There are a lot of ways two pieces of code can be similar.
These are obviously identical:
value = calculate()
save(value)
value = calculate()
save(value)
Now change the variable name:
value = calculate()
save(value)
result = calculate()
save(result)
Are those duplicates?
A human can look at them and reasonably say yes.
Arid says no.
That's deliberate.
Arid 1.1.0 detects exact duplicate source after configured normalization. It is not trying to determine whether two pieces of code are semantically equivalent, structurally similar, or suspiciously alike.
Changing value to result changes the code being compared.
Changing a literal from 10 to 20 changes it.
Changing an expression changes it.
That's an important boundary because "find code that means roughly the same thing" is a very different problem from "find source that has actually been duplicated."
The first problem starts taking you toward AST similarity, clone classification, semantic analysis, and eventually a fairly interesting discussion about what "equivalent" even means.
I wasn't trying to solve that problem.
I wanted a fast replacement for the duplicate-code functionality I was using in Pylint.
Pylint's similarity checker already has useful concepts for this. By default, it can exclude comments, docstrings, imports, and function signatures from similarity calculation. Those options are part of Pylint's similarity checker.
Arid keeps that general idea.
The interesting part is figuring out how to do it correctly.
A # Is Not Necessarily a Comment
Let's start with comments.
This looks easy:
value = 42 # this is a comment
Remove everything after #.
Done.
Until this shows up:
value = "# this is not a comment"
Now our sophisticated duplicate-code checker has helpfully converted valid Python source into:
value = "
Excellent.
You can keep adding increasingly clever text-processing rules, or you can ask Python what the thing actually is.
Arid takes the second approach.
Its Python frontend tokenizes the source and identifies tokens whose kind is actually Comment. The comment's source range can then be removed from the representation used for duplicate matching.
So:
value = "# this is not a comment"
other = 42 # actual comment
normalizes to:
value = "# this is not a comment"
other = 42
when comments are ignored.
The distinction seems obvious when you see the example.
But that's the point.
The distinction is obvious because you understand Python syntax.
A text processor doesn't.
A String Is Not Necessarily a Docstring
Docstrings get more interesting.
Consider:
def calculate():
"""Calculate the current value."""
value = 42
return value
If docstrings are configured to be ignored, we don't want that string to participate in duplicate identity.
Now consider:
def calculate():
value = 42
"""This is an ordinary string expression."""
return value
Should that string disappear too?
No.
They're both string literals.
Only one is a docstring.
The difference isn't the quotes. The difference is where that expression exists in the Python program.
Arid identifies structural docstrings as string-expression statements in the docstring position of a module, class, or function body.
So this:
"""module documentation"""
class Customer:
"""class documentation"""
def save(self):
"""method documentation"""
persist()
can have all three docstrings excluded from matching.
But this:
def save():
persist()
"""ordinary string expression"""
finish()
keeps the string expression.
You can't make that distinction reliably by looking for triple quotes.
You have to understand the syntax tree.
And now our simple "compare some lines" project has a parser.
That escalated quickly.
Function Signatures Are Worse Than They Look
Ignoring function signatures sounds simple too.
Remove the def line:
def calculate(value):
Except Python doesn't require a function declaration to fit on one line.
It can look like this:
def calculate(
value: dict[str, tuple[int, int]],
multiplier: int = 2,
) -> list[int]:
return transform(value, multiplier)
Or:
async def calculate(
value: dict[str, tuple[int, int]],
) -> list[int]:
return await transform(value)
There can be nested brackets, type annotations, default values, and plenty of colons inside those expressions before you reach the colon that actually terminates the function signature.
So "remove everything through the first colon" isn't going to last very long.
Arid walks the parser tokens beginning at def or async, tracks bracket nesting, and finds the colon that terminates the declaration at nesting level zero.
Then it masks that source range.
The body remains.
There's another detail I like here.
Decorators remain significant.
Given:
@transactional
def save(value):
persist(value)
and:
@cached
def save(value):
persist(value)
ignoring function signatures doesn't silently erase the decorators.
Arid removes the function declaration.
It doesn't remove everything vaguely associated with the function.
That distinction is easier to maintain when syntax tells you where the boundaries actually are.
Then There Are Imports
Imports have their own collection of small traps.
This:
import os
is easy.
This:
from package import (
first,
second,
third,
)
takes several physical lines.
Imports can also occur inside control flow or functions:
if enabled:
import optional_backend
run()
If imports are ignored, Arid removes the import statement while retaining:
if enabled:
run()
Then somebody writes:
import os; run()
If you remove only the AST range belonging to import os, you're left with:
; run()
Wonderful.
Or:
run(); import os
becomes:
run();
So Arid's frontend deliberately consumes the appropriate adjacent semicolon when an ignored statement shares a logical line with retained code.
The result in both cases is:
run()
It's a tiny implementation detail.
It's also exactly the kind of tiny implementation detail that separates "works on my example" from "works on Python source."
Normalization Is Not Parsing
At this point it would be easy to let the parser take over the entire design.
I didn't want that either.
Arid uses Python syntax to answer questions that require knowledge of Python:
- Is this actually a comment?
- Is this string expression actually a docstring?
- What source range belongs to this import?
- Where does this function signature end?
- Is this code associated with a module, class, or function?
Then that knowledge crosses a boundary.
The Python frontend converts parser-specific information into ordinary source ranges and structural regions owned by Arid.
The normalization layer doesn't operate on AST nodes.
The duplicate detector certainly doesn't.
The basic relationship is:
Python source
↓
parser + tokenizer
↓
source masks + structural regions
↓
normalized lines
↓
duplicate detector
I think that distinction matters.
Python syntax determines what participates in comparison. It does not perform the comparison.
The parser is there because text alone can't reliably tell me which text should be ignored.
Once that question has been answered, the rest of Arid doesn't need to know which parser answered it.
The Source You Compare Is Not the Source You Report
Normalization creates another problem.
Suppose the original code is:
def calculate(
first: int,
second: int,
) -> int:
# Add the values
result = first + second
return result
With comments and signatures ignored, the meaningful normalized representation might effectively be:
result = first + second
return result
That's useful for matching.
It's terrible for reporting if you lose the relationship to the original file.
A developer doesn't want a diagnostic that says:
Duplicate found at normalized line 2.
Normalized line 2 does not exist in the file they're editing.
Arid therefore keeps the original physical source-line location on every normalized line.
The detector works with the normalized representation.
The report maps the result back to the original Python source.
That means ignored comments, docstrings, signatures, imports, and blank lines can disappear from duplicate identity without making the diagnostic point somewhere imaginary.
This sounds like bookkeeping.
It is bookkeeping.
Bookkeeping is architecture when getting it wrong makes the product useless.
Four Lines Isn't Always Four Lines
There's another deceptively small question:
What does --min-lines 4 mean?
Four physical lines?
Four normalized lines?
Four lines containing actual code?
Consider:
values = [
first,
second,
]
The closing bracket is a normalized physical line.
But should ] count as one of the four meaningful lines required to declare a duplicate?
Arid distinguishes a normalized line from an effective line.
A line is effective when it contains at least one alphanumeric character or underscore.
So punctuation-only lines can remain part of a repeated source sequence without artificially helping that sequence satisfy the configured minimum duplicate size.
Blank lines don't count either.
That means a reported four-line duplicate means four effective normalized lines satisfied the threshold, even if the corresponding physical source range spans more lines.
Again, this isn't difficult because the algorithm is exotic.
It's difficult because apparently simple words like line turn out to require definitions.
Python-Aware Does Not Mean Semantic
This is probably the most important boundary in Arid's normalization model.
Using a Python parser does not mean Arid performs semantic duplicate detection.
These two blocks:
value = calculate()
save(value)
result = calculate()
save(result)
are not duplicates to Arid.
Nor are:
if ready:
execute()
and:
if is_ready:
execute()
They may represent the same pattern.
They may deserve refactoring.
They may even have been created by copy and paste followed by renaming a variable.
Arid still says they're different.
Why?
Because the parser is being used to interpret Python syntax accurately, not to erase meaningful Python source until everything vaguely similar starts matching everything else.
There's a line somewhere between useful normalization and inventing equivalence.
As of Arid 1.1.0, that line sits in a fairly conservative place.
Comments, structural docstrings, imports, and function signatures can be configured out.
What remains must match exactly.
Could Arid eventually detect renamed-variable clones, structural clones, or fuzzy AST similarity?
Sure.
It could also become an IDE, package manager, database, and small accounting system.
The question isn't whether those things can be built.
The question is whether they're the problem Arid is supposed to solve.
For now, they're not.
Description Is Not Identity
Arid does use the Python structure for one other purpose: describing what it found.
A duplicate can be reported as declarative or executable and associated with module, class, or function scope.
For example, repeated class-level assignments might be described differently from repeated executable logic inside functions.
But that metadata doesn't change duplicate identity.
Two blocks don't become equal because they're both executable.
They don't stop being equal because one occurs in a different structural context.
First Arid answers:
Is this source duplicated?
Then it can help answer:
What kind of source did I find?
I deliberately keep those questions separate.
The moment classification starts deciding whether something "really counts" as duplication, the tool starts making domain judgments it doesn't have enough information to make.
Repeated declarative code might be framework boilerplate.
It might be accidental duplication.
It might be exactly what the project wants.
Arid doesn't know.
Neither does the AST.
The Algorithm Wasn't the First Hard Part
Arid ultimately uses a generalized suffix array and longest-common-prefix analysis to find repeated normalized sequences.
That's the algorithmically interesting part of the project, and I'll get into it separately.
But something surprised me while building the tool.
Before you can efficiently find repeated sequences, you have to decide what the sequence is.
That decision contains a surprising amount of the product's behavior.
Do comments matter?
Which strings are docstrings?
Do imports matter?
What is a function signature?
What happens to decorators?
What does a line mean?
How do normalized lines map back to physical source?
Does structural context affect equality?
How much difference is allowed before code stops being "the same"?
Those aren't suffix-array questions.
They're product-definition questions.
And they're language questions.
The duplicate detector can only be as correct as the representation you give it.
Feed it bad normalization quickly and all you've built is a very fast way to produce bad answers.
The Parser Isn't the Point
I started Arid because Pylint's duplicate-code checker was too slow for my workflow.
I expected performance to be the interesting problem.
And performance certainly mattered.
But building the tool reinforced something I keep running into in software architecture:
Before optimizing the solution, define the problem precisely.
"Find duplicate code" isn't precise enough.
"Find exact repeated Python source after removing a configurable set of syntactically understood constructs" is considerably closer.
Once that definition existed, a lot of architectural decisions became easier.
Use Python syntax where Python syntax matters.
Turn that knowledge into a small internal representation.
Keep parser details out of the detector.
Preserve the mapping back to the source developers actually edit.
And don't quietly turn exact duplicate detection into semantic similarity because the parser happens to make that possible.
It turns out duplicate-code detection is harder than comparing text.
Not because comparing text is hard.
Because deciding which text means what is.
Arid is an open-source Python duplicate-code checker written in Rust. This article describes the normalization model in Arid 1.1.0. The implementation is available in normalize.rs, and the Python syntax frontend is in python.rs.
About the Author
Bob Taylor is a software engineer and architect who builds developer tools and AI systems. He is currently developing Arid and Polaris.
