Формализация процесса поиска дублирующегося кода в крупных программных продуктах

Введение

При разработке крупных программных продуктов (ПП) на одно из первых мест выходят поддержка приемлемого уровня качества продукта, снижение затрат на внедрение и сопровождение, повышение точности планирования и прогнозирования работ с целью оперативного внесения изменений в соответствие с требованиями заказчика или законодательства (рис. 1).

Всё это значительно усложняется, если в проекте присутствует дублирующийся код, и чем его больше, тем сильнее усугубляются указанные выше проблемы.

Присутствие дубликатов в коде приводит к необоснованному увеличению его объёма, что в свою очередь вынуждает программистов контролировать и отлаживать больше кода, чем нужно. Кроме того, возрастает время на накладные расходы (компиляция проекта, работа с репозиторием и т.п.). Также повышается вероятность внесения несогласованных изменений, когда обнаруженная ошибка исправляется только в части продублированных фрагментов, а не везде. Следствием этого становятся увеличивающиеся затраты на поддержку и развитие программного продукта, и в целом, как правило, снижение качества продукта.

Количество дубликатов в больших проектах варьируется в пределах от 5% до 50% от общего объёма кода [1, 2]. В связи с этим возникает задача своевременного обнаружения дублирующегося кода и его последующего удаления.

Основной целью дедупликации исходного кода является повышение его качества и, как следствие, повышение качества программного продукта в целом за счёт снижения трудозатрат на внесение изменений, снижения риска возникновения связанных ошибок, повышения сопровождаемости.

В данной статье будут представлены основные понятия, используемые в процессе поиска дублирующегося кода, описана и формализована математическая модель.

Термины и определения

Дубликаты (clones, клоны, клон-фрагменты) — это фрагменты кода, которые полностью идентичны (match) другим фрагментам кода или в определенной степени похожи на них, то есть совпадают за исключением некоторых формальных параметров, например, имён функций, методов или переменных (рис. 2, рис. 3).

Фрагменты кода состоят из единиц кода.

Единица кода E представляет собой минимальный блок кода, который можно рассматривать, как единое целое, и к которому применима операция сравнения.

В качестве подобного блока целесообразно рассматривать отдельную строку кода в исходном файле. Это объясняется с одной стороны тем, что все основные операции во время кодирования, включая копирование и вставку, выполняются над одной или несколькими строками, а с другой стороны позволяет упростить предварительную обработку кода. Также в качестве единицы кода допустимо использование токенов (операторы, переменные и т.п.).

Введение единиц кода позволяет абстрагироваться от конкретных особенностей работы с исходным кодом (на уровне строк или на уровне токенов). Все рассматриваемые далее алгоритмы оперируют именно единицами кода.

Фрагмент кода F можно представить в виде последовательности (набора) единиц кода:

F={E₁,E₂,…,E_K} (1)

где E_i(i=1,…,K) — i-ая единица кода.

Размер фрагмента кода есть количество единиц кода, составляющих этот фрагмент:

|F| = |{E₁,E₂,…,E_K}| = K (2)

Синтаксическая единица SU — это логически завершенный фрагмент кода — класс, метод или функция (то есть, по сути, базовая конструкция языка программирования).

Схожесть единиц кода

Для определения схожести единиц кода введём функцию S_E, множество допустимых значений которой лежит на отрезке [0, 1], т.е.

(3)

где E₁ и E₂ — единицы кода.

Функция SE обладает следующими свойствами:

1. , тогда и только тогда, когда , то есть когда единицы кода полностью идентичны;
2. , если (единицы кода абсолютно не совпадают);
3. , если (единицы кода частично совпадают).

Конкретная реализация функции S_E может основываться, например, на редакционном расстоянии или локальном выравнивании [3].

В зависимости от выбранного объекта для представления в виде единиц кода — строки или токены — возможны некоторые частные случаи. Так для токенов становится неактуальным свойство 3, поскольку их частичное совпадение исключено. Однако для модели, использующей непосредственно строки, это свойство чрезвычайно важно.

В общем случае для поддержки независимости от конкретного языка программирования алгоритм сравнения двух единиц кода должен использовать анализ строк (string matching) и возвращать логическое значение «истина», если единицы кода совпадают, или «ложь» в противном случае.

Под алгоритмом сравнения мы будем понимать некоторую функцию A_E такую, что для любой пары схожих единиц кода E₁ и E₂. Используя (3), расширим определение функции A_E, введя пороговое значение схожести единиц кода σ:

таких что, . (4)

Очевидно, что допустимые значения σ также лежат на отрезке [0, 1]. Изменяя значение σ, можно управлять количеством обнаруживаемых схожих единиц кода, и тем самым влиять на количество получаемых клон-фрагментов.

Для удобства восприятия значение σ может задаваться в процентах.

Схожесть фрагментов кода

Фрагменты кода, также как и единицы кода, обладают схожестью. Для определения схожести фрагментов кода по аналогии с (3) введём функцию S_F:

, (5)

где F₁ и F₂ — фрагменты кода.

Функция S_F обладает всеми свойствами рассмотренной ранее функции S_E.

Фрагменты кода представляют собой строки над алфавитом единиц кода (см. (1) и определение фрагмента кода). Таким образом, для вычисления схожести фрагментов допустимо применять алгоритмы, описанные в [3].

Наиболее подходящим видится использование метода локального выравнивания для нахождения подстрок высокого сходства. Такой подход позволит определять клон-фрагменты, в которых производилось добавление или удаление единиц кода, либо изменялся порядок следования единиц кода (рис. 4).

Релевантность фрагментов кода

Под релевантностью фрагмента дублирующегося кода понимается его практическая значимость для процедуры извлечения клонов.

Основным, на данный момент, критерием релевантности является размер фрагмента кода. Извлечение слишком маленьких фрагментов не представляет смысла, так как потребует существенных трудозатрат и вряд ли положительно отразится на читаемости и наглядности кода. Такие фрагменты считаются иррелевантными (рис. 5, рис. 6).

Другие критерии релевантности основываются на семантической составляющей фрагментов кода, например, пригодность фрагмента к рефакторингу (извлечению в виде новой синтаксической единицы). Однако семантический анализ достаточно сложен и в дальнейшем рассматриваться не будет.

Задача:

Для заданного фрагмента дублирующегося кода F размера определить его релевантность.

Решение:

Введём функцию R(F), которая возвращает логическое значение «истина», если фрагмент кода является релевантным, и значение «ложь» в противном случае.

Математическим отображением критерия релевантности служит пороговое значение размера фрагмента кода K_min такое, что все фрагменты F, размер которых , считаются иррелевантными.

, таких что . (6)

Таким образом, определение K_min является ключевой задачей, для выявления релевантности фрагментов дублирующегося кода.

В общем случае значение K_min является индивидуальным для каждого программного продукта и может быть определено с использованием двух различных подходов:

1. Эмпирический. Основывается на многократном повторении процедуры поиска клонов и ручном подборе K_min. Недостатки: субъективность, сложность, значительные трудозатраты;
2. Аналитический. Основывается на использовании предварительной обработки исходного кода и аппарата математической статистики. Недостатки: возможно менее точный результат, недостаточная гибкость.

Аналитическое определение порогового значения размера фрагмента кода

Предпосылка 1: целью поиска дублирующихся фрагментов кода является их дальнейшее устранение путём рефакторинга кода.

Предпосылка 2: рефакторинг осуществляется с использованием паттернов (шаблонов) и заключается, в общем случае, в выделении дублирующейся функциональности в виде новых синтаксических единиц (функций или методов классов).

Следовательно, при определении K_min следует ориентироваться на размер уже имеющихся в исходном коде синтаксических единиц (функций или методов классов). Таким образом, для вычисления K_min потребуется анализ исходного кода.

Для этого рассмотрим подробнее статистические характеристики исходного кода.

Пусть исходный код содержит N синтаксических единиц SU_i, где i=1,…,N.

— размер i-той синтаксической единицы (в единицах кода).

Размер синтаксической единицы является дискретной случайной величиной. Тогда среднее значение (математическое ожидание) [4] размера синтаксической единицы равно:

. (7)

Дисперсию можно определить как

. (8)

А среднее квадратическое (стандартное) отклонение будет равно

. (9)

Задача:

для заданного исходного кода определить пороговое значение размера фрагмента кода K_min.

Решение:

Значение K_min должно быть меньше или равно среднему размеру фрагмента кода m_K. Такое ограничение позволяет отбросить значительную часть иррелевантных фрагментов с очень маленьким размером.

Значение K_min должно быть строго меньше среднего размера фрагмента кода m_k. Дело в том, что дублироваться могут не отдельные синтаксические единицы, а их части, и согласно исследованиям [5, 6, 7] количество таких дубликатов велико.

Для ответа на вопрос, насколько меньше, целесообразно учитывать среднее квадратическое отклонение, вычисляемое по (9).

. (10)

Тогда значение K_min можно найти как:

, (11)

где — пороговый коэффициент, зависящий от характеристик кода.

, (12)

где m_min — размер минимального фрагмента кода; m_k — средний размер фрагмента кода по (7); I_c = 0,9999