Цикломатическая сложность

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Цикломати́ческая сло́жность програ́ммы (англ. Cyclomatic complexity of a program) — структурная (или топологическая) мера сложности программ, используемая для измерения качества программного обеспечения, основанная на методах статического анализа кода. ЦСП равна увеличенному на единицу цикломатическому числу графа программы.

Она была разработана Томасом Дж. Маккейбом в 1976 году; он использовал эти показатели сложности для программ. Он производил непосредственные численные измерения для линейно независимых путей в исходных кодах программ. Концепция, но не метод, отчасти похож на измерение сложности с помощью теста удобочитаемости Флеша-Кинкейда[en] для общего текста.

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

Эта стратегия тестирования называется основным маршрутом тестирования Мак-Кейба, который первым предложил его. Это тестирование каждого линейного независимого маршрута через программу; в этом случае, число тестов должно быть равно цикломатической сложности программы.[1]

Описание[править | править вики-текст]

Граф управления потоком простой программы. Программа начинает выполняться с красного узла, затем идут циклы (после красного узла идут две группы по три узла). Выход из цикла осуществляется через условный оператор (нижняя группа узлов) и конечный выход из программы в синем узле. Для этого графа E = 9, N = 8 и P = 1, цикломатическая сложность программы равна 9-8+(2*1)=3 (рассчитано по первому варианту).

Цикломатическая сложность части программного кода — количество линейно независимых маршрутов через программный код. Например, если исходный код не содержит никаких точек ветвления или циклов, то сложность равна единице, поскольку, есть только единственный маршрут через код. Если код имеет единственный оператор IF, содержащий простое условие, то существует два пути через код: один если условие оператора IF имеет значение TRUE и один — если FALSE.

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

M = EN + 2P,

где:

M = цикломатическая сложность,
E = количество рёбер в графе,
N = количество узлов в графе,
P = количество компонент связности.
Сильносвязанный граф управления потоком той же функции. Для этого графа E = 10, N = 8 и P = 1, следовательно, цикломатическая сложность программы, рассчитанная по второму варианту, также равна 10-8+1=3.

В другой формулировке используется граф, в котором каждая точка выхода соединена с точкой входа. В этом случае граф является сильносвязным и цикломатическая сложность программы равна цикломатическому числу этого графа (также известному как first Betti number (англ.)), которое определяется как:[3]

M = EN + P

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

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

Может быть показано, что цикломатическая сложность любой структурированной программы с только одной точкой входа и одной точкой выхода эквивалентна числу точек ветвления (то есть, операторов if или условных циклов), содержащихся в этой программе, плюс один.[3][4]

Цикломатическая сложность может быть распространена на программу с многочисленными точками выхода; в этом случае она равна:[4][5]

π − s + 2

где:

π — число точек ветвления в программе,
s — число точек выхода.

Формальное определение[править | править вики-текст]

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

M := b_1(G,t) := \operatorname{rank}\,H_1(G,t)

Это читается, как «первый однородный граф G, относительно терминального узла t». Этот технический путь произносится, как «число линейно независимых маршрутов через граф от входа к выходу», где:

  • «линейно независимый» соответствует однородности и означает, что один не возвращается в исходное состояние двойного счета;
  • «маршрут» соответствует нальной однородности: маршруту соответствует одномерный объект;
  • «относительно» означает, что путь должен начаться и закончится в точке входа или выхода, соответственно.

Это соответствие интуитивно понятно как цикломатическая вложенность, и может быть вычислено как указанно выше.

Кроме того, его можно вычислить через абсолютное число Бетти (абсолютно однородное — не относительное) определяющее все терминальные узлы данного компонента (или равно, получение маршрутов соединяющих входы с выходами), в этом случае (вызов нового, расширенного графа \tilde G, которым он является) получаем:

M = b_1(\tilde G) = \operatorname{rank}\,H_1(\tilde G)

Это соответствие характеризуется цикломатической сложностью как «количество циклов плюс количество компонентов».

Применение[править | править вики-текст]

Ограничение сложности при разработке[править | править вики-текст]

Одно из первоначально предложенных Маккейбом применений состоит в том, что необходимо ограничивать сложность программ во время их разработки. Он рекомендует, чтобы программистов обязывали вычислять сложность разрабатываемых ими модулей и разделять модули на более мелкие всякий раз, когда цикломатическая сложность этих модулей превысит десять.[3] Эта практика была включена НИСТ-ом в методику структурного тестирования с замечанием, что со времени исходной публикации Маккейба, выбор значения 10 получил весомые подтверждения, однако в некоторых случаях может быть целесообразно ослабить ограничение и разрешить модули со сложностью до 15. В данной методике признаётся, что иногда могут существовать причины для выхода за рамки согласованного лимита. Это сформулировано как рекомендация: "Для каждого модуля следует либо ограничивать цикломатическую сложность до согласованных пределов, либо предоставить письменное объяснение того, почему лимит был превышен".

Применение при тестировании программного обеспечения[править | править вики-текст]

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

Он полезен, поскольку цикломатическая сложность M имеет два свойства, для конкретного модуля:

  • M — верхняя граница для числа произведённых тестов, которые необходимо достичь для полного покрытия ветки;
  • M — пониженная граница для числа маршрутов через контролируемый поток графа (КПГ).

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

Но некоторые пути могут быть невозможными, так что, число путей через КПГ — это, несомненно, верхняя граница числа тестов, для обеспечения покрытия пути (возможного пути), чей номер идёт последним, которое иногда может быть меньше чем M.

Все три вышеуказанные числа могут быть равны: покрытие ветки \leq cyclomatic complexity \leq количества путей.

Для примера рассмотрим нижеприведённую программу, состоящую из последовательного применения двух операторов if-then-else.

if( c1() )
   f1();
else
   f2();
 
if( c2() )
   f3();
else
   f4();
В вышеуказанном графе управления потоком исходного кода красный кружок обозначает точку входа в функцию, синий кружок — точку выхода. Выход соединён со входом, что делает граф сильносвязанным.

Связность[править | править вики-текст]

Корреляция числа дефектов[править | править вики-текст]

  • Сложность больше 50 означает очень высокий риск и практически не тестируемый код.[6]

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. A J Sobey. Основной маршрут тестирования. Архивировано из первоисточника 26 апреля 2012.
  2. Here «structured» means in particular «with a single exit (return statement) per function».
  3. 1 2 3 4 McCabe (December 1976). «A Complexity Measure» ((недоступная ссылка)). IEEE Transactions on Software Engineering: 308–320.
  4. 1 2 Belzer, Kent, Holzman and Williams Encyclopedia of Computer Science and Technology. — CRC Press, 1992. — P. 367–368.
  5. Harrison (October 1984). «Applying Mccabe's complexity measure to multiple-exit programs». Software: Practice and Experience (J Wiley & Sons).
  6. Цикломатическая сложность