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

Размещено на http://www.allbest.ru/

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

Технические науки

Вахрушев Иван Николаевич, аспирант Вологодский государственный университет

Введение

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

Рис.1 - Проблемы при разработке крупных программных продуктов

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

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

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

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

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

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

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

Рис.2 - Пример программных клонов в АБС RS-Bank\Pervasive

Рис.3 - Пример программных клонов в ядре Linux

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

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

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

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

(1)

где - i-ая единица кода.

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

(2)

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

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

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

(3)

где E1 и E2 - единицы кода.

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

1. , тогда и только тогда, когда , то есть когда единицы кода полностью идентичны;

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

3. , если (единицы кода частично совпадают).

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

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

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

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

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

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

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

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

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

, (5)

где F1 и F2 - фрагменты кода.

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

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

Рис.4 - Клон-фрагменты с добавлением\удалением единиц кода

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

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

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

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

Рис.5 - Виды фрагментов кода

Рис.6 - Пример иррелевантных клон-фрагментов

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

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

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

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

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

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

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

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

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

программный код дублирующийся формализация

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

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

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

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

Пусть исходный код содержит N синтаксических единиц SUi, где . - размер i-той синтаксической единицы (в единицах кода). Размер синтаксической единицы является дискретной случайной величиной. Тогда среднее значение (математическое ожидание) [4] размера синтаксической единицы равно:

. (7)

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

. (8)

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

. (9)

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

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

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

. (10)

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

, (11)

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

, (12)

где

mmin - размер минимального фрагмента кода;

mk - средний размер фрагмента кода по (7);

Ic = 0,9999

Список литературы

1. Вахрушев, И. Н. Проблема дублирования исходного кода в программных продуктах / И. Н. Вахрушев // Вузовская наука - региону: Материалы восьмой всероссийской научно-технической конференции. - Вологда: ВоГТУ, 2010

2. Вахрушев, И. Н. Применение методов поиска дублирующегося кода в процессе разработки программного обеспечения / И. Н. Вахрушев // Автоматизация и энергосбережение машиностроительного и металлургического производств, технология и надёжность машин, приборов и оборудования: Материалы шестой международной научно-технической конференции. Т. 1. - Вологда: ВоГТУ, 2010. - с. 73-76

3. Гасфилд, Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология / Д. Гасфилд. - СПб.: Невский Диалект; БХВ-Петербург, 2003. - 654 с.: ил.

4. Пугачев B.C. Теория вероятностей и математическая статистика / В.С. Пугачев. - М.: ФИЗМАТЛИТ, 2002. - 496 с.

5. Kamiya, T. CCFinder: A Multilinguistic Token-Based Code Clone Detection System for Large Scale Source Code / Toshihiro Kamiya, Shinji Kusumoto, Katsuro Inoue // IEEE Transactions on Software Engineering. - 2002. - №28. - p. 654-670

6. Baxter, I. Clone detection using abstract syntax trees / I. Baxter, A. Yahin, L. Moura. // In ICSM'98: Proceedings of the International Conference on Software Maintenance. - USA, Bethesda, Maryland. - 1998. - p. 368-377

7. Baker, B. A program for identifying duplicated code / B. Baker // Computing Science and Statistics. - 1992. - №24. - p. 49-57

Размещено на Allbest.ru