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

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

Вологодский государственный университет

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

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

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

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

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

S(F₁,F₂) ? [0,1], ? F₁,F₂

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

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

S(F₁,F₂) == 1, если F₁ == F₂ (фрагменты полностью идентичны);

S(F₁,F₂) == 0, если F₁? F₂ , если (фрагменты полностью различны);

S(F₁,F₂) ? (0,1), если F₁? F₂ , если (фрагменты частично совпадают).

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

В общем случае алгоритм сравнения двух фрагментов кода должен использовать анализ строк (string matching) и возвращать логическое значение «истина», если фрагменты совпадают, или «ложь» в противном случае. Под алгоритмом сравнения мы будем понимать некоторую функцию A такую, что для любой пары одинаковых фрагментов кода F₁и F₂. Используя (1),расширим определение функции A, введя некоторое пороговое значение схожести фрагментов кода у:

A(F₁,F₂,у) ? true, ? F₁,F₂ , таких что, S(F₁,F₂) ? у

Изменяя значение у, можно управлять количеством обнаруживаемых клонов.

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

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

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

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

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

Характер преобразования кода определяет глубину и объём изменений. Для того чтобы обеспечить независимость от конкретного языка программирования, все операции на данном этапе должны быть сведены к манипуляциям над символьными строками. В качестве инструментария чаще всего используются абстрактные синтаксические деревья [2] или параметризированные строки [3], которые требуют как минимум реализации лексического анализатора для каждого поддерживаемого языка программирования.

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

Рис. 1. Пример трансформации кода

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

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

Нативный алгоритм сравнения имеет временную и пространственную сложность O(n²), где n - количество единиц кода. Квадратичная сложность делает его неприемлемым для использования на реальных программных продуктах, в которых количество строк кода может достигать нескольких миллионов.

Одним из возможных способов оптимизации данного алгоритма является использование ещё одного этапа предварительной обработки кода, требующего O(n) времени, на котором всё входное множество единиц кода разбивается на блоки с помощью хэширования [2]. Одинаковые строки имеют одинаковые хэш-значения, и будут помещены в один и тот же хэш-блок. Затем алгоритм сравнения будет оперировать этими хэш-блоками, число которых B в большинстве случаев будет меньше числа строк n на входе, однако временная сложность по-прежнему остаётся квадратичной от B.

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

она не должна зависеть от реализации конкретного алгоритма;

должна обеспечивать лёгкую и быструю смену используемых алгоритмов;

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

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

программный кодирование клон

1. Ducasse, S. A language independent approach for detecting duplicate code / S. Ducasse, M. Reiger, S. Demeyer. // In ICSM'99: Proceedings of the International Conference on Software Maintenance. - UK, Oxford, England. - 1999. - p. 109-118.

2. 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.

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

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