Что такое цикломатическая сложность?

• Суть
• Формула
• Пример и схема
• Важность этого числа в тестировании
• Подробно о цикломатической сложности (осторожно матан!)
  • Графы путей
  • Как вычислить цикломатическую сложность
  • Пример кода и его граф
• Характеристики цикломатической сложности
• Применение в QA: «ограничение сверху и снизу»
• Этапы вычисления ЦС
• Каких значений может достичь ЦС (таблица)
• Инструменты вычисления ЦС
• Приложение: альтернативный взгляд на показатели сложности кода

Определение

Цикломатическая сложность — показатель сложности исходного кода программы, который связан (коррелирует) с вероятностью возникновения ошибок (багов) в программе. Показатель цикломатической сложности вычисляется через граф потока управления (Control flow graph, CFG), который отображает количество линейно-независимых путей выполнения (как это?) в программе.

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

Формула

Цикломатическая сложность описывается следующей формулой:

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

CC = E - N + 2*P,

где

E = количество рёбер в графе

N = количество узлов в графе

P = количество компонентов связности (узлов, имеющих точки выхода)

Быстрый пример

Код программы (модуля):

IF A = 10 THEN 
 IF B > C THEN 
   A = B
 ELSE
   A = C
 ENDIF
ENDIF
Print A
Print B
Print C

Граф путей выполнения:

В данном случае цикломатическая сложность программы, состоящей из 7 узлов (черных фигур на рисунке) и 8 рёбер (соединяющих линий на рисунке), составляет: 8-7+2=3.

Важность в QA

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

Цикломатическая сложность имеет следующие свойства (в контексте тестирования), так как дает:

— оценку сверху количества тестов, обеспечивающих покрытие условий (точек ветвления);

— оценку снизу количества «маршрутов» через граф потока управления и, таким образом, количества тестов для полного покрытия путей.

Подробнее

Подробнее о цикломатической сложности

Концепция ЦС впервые описана в 1970х Томасом Маккейбом (поэтому называется еще «сложностью программы по Маккейбу») в книге о структурном тестировании и создании правильных тест-кейсов. 

Линейно-независимый путь выполнения определяется Маккейбом как путь, имеющий хотя бы одно ребро, которое не было пройдено перед тем любыми другими путями выполнения.

В графе узлы (или ноды, nodes), обозначают задачи (processing tasks), а рёбра обозначают пути выполнения (control flow).

Графы путей

На графах демонстрируется в наглядном виде выполнение программы (обычно выполнение ее отдельного модуля, поскольку граф всей программы выглядел бы слишком большим и запутанным). Ниже графы выполнения операторов if-else, while, if-then-else, until.

Как вычислить цикломатическую сложность

С математической точки зрения цикломатическая сложность — это набор (совокупность) независимых путей выполнения. Формула цикломатической сложности программы (тестируемого модуля):

CC = E - N + 2*P

Где E — количество рёбер, N — количество узлов, P — количество предикативных узлов (то есть узлов, содержащих условие).

Пример кода и его граф

Код программы:

i = 0;
n=4; //N-Number of nodes present in the graph

while (i<n-1) do
j = i + 1;

while (j<n) do

if A[i]<A[j] then
swap(A[i], A[j]);

end do;
j=j+1;

end do;

Граф этого кода:

Вычисление цикломатической сложности этого кода:

CC=9-7+2=4

CC=3+1=4 (мы видим, что предикативные узлы у нас: 1, 2 и 3)

Базовый набор таких путей выполнения:

• 1,7
• 1, 2, 6, 1, 7
• 1, 2, 3, 4, 5, 2, 6, 1, 7
• 1, 2, 3, 5, 2, 6, 1, 7

Итого 4.

Характеристики цикломатической сложности

• Это максимальное количество независимых путей выполнения в графе
• Оно может быть равно или больше единицы (обычно намного больше)
• Оно равно единице, если путей всего один
• Всегда нужно стремиться «держать в рамках» цикломатическую сложность при написании программ. Хорошей практикой является цикломатическая сложность меньше 10.

Применение при тестировании

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

• Количество тест-кейсов может быть равно цикломатической сложности, если стремятся достичь 100% покрытия ветвлений («ограничение сверху»)
• Количество тест-кейсов может быть равно количеству путей по графу («ограничение снизу»)

Еще один пример

If (Condition 1)
Statement 1

Else
Statement 2

If (Condition 2)
Statement 3

Else
Statement 4

Цикломатическая сложность получается 8-7+2=3. Поскольку СС равна 3, понадобится три тест-кейса, чтобы достичь полного покрытия путей в данном модуле.

Этапы вычисления ЦС

Этапы вычисления цикломатической сложности для подсчета количества будущих тест-кейсов:

1. Создание графа с узлами и ребрами
2. Определение независимых путей
3. Вычисление цикломатической сложности
4. Все, пишем тест-кейсы

Каких значений достигает цикломатическая сложность

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

Инструменты вычисления ЦС

Автоматический подсчет цикломатической сложности (в программе-анализаторе кода, то есть линтере) основывается на оценке количества точек принятия решений в программе (модуле), типа: if, for, for-each, while, do, catch, case и т.п. Примеры инструментов с автоматическим вычислением ЦС:

• OCLint — статический анализатор кода для Си-подобных языков
• Reflector — для .NET
• GMetrix — для Java

Полезности показателя цикломатической сложности в разработке и QA

• Наглядно показывает разработчику (и тестировщику) количество независимых путей выполнения
• Поэтому разработчик/тестировщик обеспечит, чтобы все пути были проверены хотя бы по разу
• Тем самым давая больше времени на проверку непокрытых/неочевидных/негативных путей
• Все это повышает тестовое покрытие
• И этим снижает риски сбоя/отказа
• Таким образом, повышается общее качество кода.

Альтернативные подходы

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

Цикломатическая сложность по Маккейбу является развитием изложенной выше концепции, но с упором на точки принятия решений и графы (так называемая graph driven model). Маккейб предложил разбивать программу на блоки (каждый блок = точка принятия решений) и соединять их рёбрами по определенному принципу, и к стандартной схеме добавил граф:

Считается, что цикломатическая сложность в идеале не должна превышать 10. В гайдах по качеству кода, например Microsoft, особо подчеркивается, что высокая ЦС чревата ошибками (то есть багами). Анализаторы кода в IDE-редакторе отправляют разработчику (автоматическое) уведомление, если ЦС превысила пороговое значение (по дефолту 25, но можно настроить и ниже/выше).

В 2017 предложен совсем альтернативный подход к оценке сложности программного кода — с точки зрения его читаемости, то есть легкости восприятия человеком (что разумеется имеет значение и для QA тоже). В какой-то мере читаемость зависит от самого языка, например, код на HTML или SQL явно лучше читается человеком, чем на C++ или Java. При этом отличают необходимую сложность кода (которую никак нельзя устранить, из-за специфики языка, или специфики самой программы) и непреднамеренную, которая может и должна быть успешно устранена/существенно снижена создателем кода, или код-ревьюером. 

Непреднамеренная сложность — это и есть цикломатическая сложность. Однако, эта метрика слишком тесно привязана к структуре кода, и хотя ЦС полезная метрика и широко применяется в разработке (и QA!), именно сложность кода, как таковую, она показывает не очень точно. Например, два сниппета ниже; как видим, подсчитана цикломатическая сложность каждого сниппета = 4, но код слева, сугубо визуально — он явно сложнее для восприятия, чем код справа. 

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

Эта метрика основана на следующем:

• Игнорирование структур ЯП, «искусственно» сокращающих объем кода (особенно касается ЯП с часто обновляемым синтаксисом)
• Показатель когнитивной сложности увеличивается на 1 с каждым оператором, прерывающим поток выполнения (циклы, условия, тернарные операторы)
• Показатель увеличивается на 1 с каждой вложенной конструкцией (nested)

Если смотреть по показателю когнитивной сложности, то у Си-подобных языков получается средняя сложность кода около 25, в то время как все остальные ЯП — в среднем 15.

***

Источники: 1,2,3,4