Использование статистических характеристик программного кода в задачах дедупликации и оценки качества

Введение

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

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

Количество дубликатов в больших проектах варьируется в пределах от 5% до 50% от общего объёма кода [1, 2]. Существование дубликатов объясняется сложившейся практикой программирования, когда разработчики, чтобы быстро добавить некоторую функциональность, предпочитают скопировать часть кода (copy/paste), а не видоизменить и повторно использовать первоначальный код.

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

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

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

Теоретический анализ

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Текстовое дублирование. Этот вид наиболее простой и легко находимый. Он проявляется, когда в программе есть секции кода, которые идентичны или очень похожи;
2. Функциональное дублирование. Это особый вид текстового дублирования, когда в исходном коде есть различные функции или методы, предназначенные для одного и того же. Его можно часто встретить в проектах, которые разделены между группами разработчиков, недостаточно хорошо взаимодействующих друг с другом;
3. Временное дублирование. Оно более трудное, менее ясное, и не так легко обнаруживаемое. Временное дублирование наблюдается, когда при выполнении программы одна и та же работа делается повторно — в то время, когда так не должно быть. Оно может стать серьезной проблемой при масштабировании системы, существенно снижая производительность.

В дальнейшем будет рассматриваться только текстовое и, отчасти, функциональное дублирование. Для устранения временного дублирования лучше всего подходят системы профилирования кода (profilers).

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

Большинство из существующих подходов для выявления клонов фокусируются главным образом на синтаксической схожести фрагментов кода, поскольку определение семантической схожести очень сложно и малоэффективно в плане производительности. Согласно [3] все методы могут быть разделены на 4 класса:

1. Методы, основанные на строках (string-based, line-based), разбивают программный код по строкам исходного файла. Таким образом, каждый фрагмент кода представляется в виде последовательности строк. Два фрагмента считаются похожими, если составляющие их строки схожи между собой;
2. Методы, основанные на токенах (token-based), трансформируют исходный код в последовательность токенов. Затем эта последовательность анализируется на вхождение дублирующихся подпоследовательностей, что может служить признаком программных клонов. В сравнении с подходами, основанными на строках, методы, базирующиеся на токенах, более устойчивы к таким изменениям кода, как форматирование, добавление пробелов и комментариев;
3. Методы, основанные на деревьях (tree-based), представляют программный код в виде абстрактного синтаксического дерева (АСД). Точные или близкие совпадения поддеревьев могут быть найдены путём их сравнения с АСД. В качестве альтернативного подхода может применяться метод отпечатков (fingerprints) для поддеревьев. Поддеревья с похожими отпечатками являются признаком дублирования кода;
4. Методы, основанные на семантическом анализе (semantics-based), используют граф зависимостей (program dependence graphs) и расщепление (slicing) программы для поиска изоморфных подграфов (т.е. имеющих идентичную форму) с целью идентификации клонов.

Как показано в [4] процесс поиска клонов всегда включает два основных этапа: трансформацию кода и дальнейшее сравнение этого кода.

На этапе трансформации необходимо решить как минимум две проблемы: характер преобразования кода и минимальный размер фрагмента, которым в дальнейшем будет оперировать алгоритм сравнения.

Характер преобразования кода определяет глубину и объём изменений. Минимальное преобразование кода требует удаления всей незначащей информации: комментариев, пустых строк и лишних пробелов.

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

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

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

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

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

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

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

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

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

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

, таких что

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

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

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

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

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

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

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

Методика

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

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

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

, таких что

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

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

Эмпирический подход основывается на многократном повторении процедуры поиска клонов и ручном подборе K_min. Его основные недостатки: субъективность, низкая точность, требует серии испытаний.

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

Для аналитического определения K_min сформулируем несколько предпосылок.

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

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

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

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

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

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

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

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

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

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

Решение:

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

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

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

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

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

где m_min– минимальный размер синтаксической единицы; m_K — средний размер синтаксической единицы по (7); I_C =0,9999 — коэффициент, который позволяет значению K_min, найденному по (11), удовлетворять неравенству (10).

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

Под метрикой объемной структурированности кода будем понимать величину:

где m_max — максимальный размер синтаксической единицы; m_K — средний размер синтаксической единицы по (7).

Из (13) следует, что чем лучше структурирован исходный код, и чем меньше разброс между средним и максимальным размерами синтаксических единиц, тем меньше будет значение метрики:

Экспериментальная часть

Нахождение и выделение синтаксических единиц в программном коде требует реализации синтаксического анализатора (парсера) для каждого поддерживаемого языка программирования. Для решения этой задачи был выбран генератор компиляторов Сосо/R.

Coco/R воспринимает атрибутную LL(1) грамматику языка в расширенной форме Бэкуса-Наура (EBNF) и строит для нее нисходящий рекурсивный синтаксический и лексический анализатор. По функциональности Coco/R покрывает использование пары утилит flex/yacc.

Для определения синтаксических характеристик программного кода и вычисления порогового размера клон-фрагмента написана грамматика, поддерживающая язык программирования C#. Также разработана библиотека классов, использующая сгенерированные лексический и синтаксический анализаторы.

Для апробации разработанной библиотеки были выбраны четыре программных продукта с открытым исходным кодом. В табл. 2 приведены результаты анализа синтаксических характеристик этих продуктов.

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

Результаты

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