Множество инженерных задач, таких как: рефакторинг, оценка качества кода, поиск и исправление ошибок, требуют выделения синтаксически или семантически схожих фрагментов исходного кода, обычно называемых клонами (software clones). Клоны — это фрагменты кода, которые точно или приближенно совпадают с другими фрагментами.
Многочисленные исследования показывают, что в больших программных продуктах значительная часть кода (от 5% до 50%) дублируется. Существование дубликатов объясняется сложившейся практикой программирования, когда разработчики, чтобы быстро добавить некоторую функциональность, предпочитают скопировать часть кода (copy/paste), а не видоизменить и повторно использовать первоначальный код.
Присутствие дубликатов в коде приводит к необоснованному увеличению его объёма, что в свою очередь вынуждает программистов контролировать и отлаживать больше кода, чем нужно. Кроме того, возрастает время на компиляцию проекта. Следствием этого становятся увеличивающиеся затраты на поддержку и развитие программного продукта, и в целом, как правило, суммарное снижение его качества.В связи с этим возникает задача своевременного обнаружения дублирующегося кода (detecting duplicated code) и его последующего удаления.
Большинство из предложенных в литературе подходов для выявления клонов фокусируются главным образом на синтаксической схожести фрагментов кода, поскольку определение семантической схожести очень сложно. Согласно [1] эти методы могут быть разделены на 4 класса:
1. Методы, основанные на строках (string-based, line-based).
Они разбивают программный код на строки (обычно деление осуществляется по строкам исходного файла). Таким образом, каждый фрагмент кода представляется в виде последовательности строк. Два фрагмента считаются похожими, если составляющие их строки схожи между собой. Одна из основных работ, описывающих этот метод, это работа [2] Бренды Бейкер (Brenda Baker). В [2] описывается программа «Dup», которая позволяет находить дублирующийся или связанный код в больших программных продуктах. При этом можно либо искать полностью идентичные фрагменты, либо производить поиск секций кода, которые совпадают между собой за исключением некоторых параметров, таких как: имена переменных и константы. Кроме того, «Dup» может построить график структурной сложности системы, отражающий необычно сложные файлы, а также фрагменты кода, которые следует подвергнуть рефакторингу.
2. Методы, основанные на токенах (token-based).
Исходный код разбивается на лексемы (выражения, операторы), образуя так называемую последовательность токенов. Затем эта последовательность анализируется на вхождение дублирующихся подпоследовательностей, что может служить признаком программных клонов. В сравнении с подходами, основанными на строках, методы, базирующиеся на токенах, более устойчивы к таким изменениям кода, как форматирование, добавление пробелов и комментариев. CCFinder и CP-Miner, вероятно, наиболее известные реализации подобного метода поиска дубликатов в коде.
3. Методы, основанные на деревьях (tree-based).
Данные методы представляют программный код в виде абстрактного синтаксического дерева (АСД). Точные или близкие совпадения поддеревьев могут быть найдены путём их сравнения с АСД. В качестве альтернативного подхода может применяться метод отпечатков (fingerprints) для поддеревьев. Поддеревья с похожими отпечатками являются признаком дублирования кода.
4. Методы, основанные на семантическом анализе (semantics-based).
Помимо вышеперечисленных также были разработаны методы, учитывающие семантическую составляющую программного кода. Комондор (Komondoor) и Хорвиц (Horwitz) предложили использовать граф зависимостей (programdependencegraphs) и расщепление (slicing) программы для поиска изоморфных подграфов (т.е. имеющих идентичную форму) с целью идентификации клонов. Также они представили метод, позволяющий группировать обнаруженные дубликаты до тех пор, пока сохраняется семантическая составляющая первоначального кода. Такой подход может применяться для автоматической процедуры извлечения функций при рефакторинге кода. Однако его масштабирование для использования в больших программных продуктах весьма затруднительно.
Каждый из рассмотренных выше подходов для выявления дублирующегося кода имеет как ряд преимуществ, так и ряд недостатков. Сравнительный анализ их практической эффективности на реальном исходном коде станет следующим этапом работы и позволит выбрать наиболее перспективный метод для дальнейших исследований.