Docs chevron_right Research Background — Code-clone detection algorithms

Research Background

Deslop combines established clone-detection techniques: normalized syntax trees, Merkle fingerprints, sibling windows, MinHash LSH, and optional embedding search. The implementation pointers below identify where each shipped technique lives.

Why AI changes the clone problem

Code clones were already a maintenance risk before AI coding assistants. The established concern is not that every duplicate is automatically wrong; it is that copied logic must be kept consistent across fixes, security patches, and feature changes. AI-assisted development changes the economics: the cost of generating another similar implementation drops, so repeated logic can enter the repository during ordinary feature work rather than only through deliberate copy-and-paste.

Recent research supports that risk model:

Clone taxonomy

Type I describes exact copies apart from layout and comments; Type II allows renaming and changed literals; Type III includes edited statements; Type IV describes equivalent behaviour implemented differently. Deslop's current labels and stricter text-identity rule are explained in How It Works. Shape-only findings are outside this taxonomy and do not count as duplication.

Implementation

  • Tree-sitter parsing and normalization identify structural candidates: crates/deslop-core/src/lang/.
  • Subtree and sibling-run fingerprints locate repeated code: fingerprint.rs and sibling.rs.
  • MinHash and LSH retrieve near-miss candidates: lsh.rs, lsh/banding.rs and tokens.rs.
  • Optional embeddings add semantic candidates: embedding/.
  • Pair admission checks content as well as structure: pair/content_gate.rs. Explicit comparisons expose pair evidence; clusters do not inherit one pair's confidence.
  • Reports rank surviving clones by duplicated mass: report_weight.rs. Percentage calculations live in report_metrics.rs.

These are detection techniques, not proofs of safe refactoring. The accuracy documentation explains the independent checks.

References

  • Baxter, Yahin, Moura, Sant'Anna, and Bier, Clone Detection Using Abstract Syntax Trees, 1998. PDF
  • Chilowicz, Duris, and Roussel, Syntax Tree Fingerprinting for Source Code Similarity Detection, 2009. PDF
  • Sajnani, Saini, Svajlenko, Roy, and Lopes, SourcererCC: Scaling Code Clone Detection to Big Code, 2016. arXiv
  • Roy and Cordy, NICAD: Accurate Detection of Near-Miss Intentional Clones Using Flexible Pretty-Printing and Code Normalization, 2008. ResearchGate entry
  • Shrivastava and Li, Densifying One Permutation Hashing via Rotation for Fast Near Neighbor Search, 2014. PDF
  • Roy, Alam, Al-omari, Roy, Roy, and Schneider, Unveiling the potential of large language models in generating semantic and cross-language clones, 2023. arXiv
  • Roy et al., GPTCloneBench: A comprehensive benchmark of semantic clones and cross-language clones using GPT-3 model and SemanticCloneBench, 2023. arXiv
  • Eagal, Stolee, and Ore, Analyzing the dependability of Large Language Models for code clone generation, 2025. Journal of Systems and Software
  • Liu et al., Code Copycat Conundrum: Demystifying Repetition in LLM-based Code Generation, 2025. arXiv
  • Alam et al., Are Classical Clone Detectors Good Enough For the AI Era?, 2025. arXiv
  • Wu et al., An Empirical Study of Code Clones from Commercial AI Code Generators, 2025. FSE 2025 entry
  • Liu, Widyasari, Zhao, Irsan, and Lo, Debt Behind the AI Boom: A Large-Scale Empirical Study of AI-Generated Code in the Wild, 2026. arXiv