Цикломатическая сложность: как считать по Маккейбу

Цикломатическая сложность - структурная метрика кода, предложенная Томасом Маккейбом в 1976 году в статье «A Complexity Measure» (IEEE Transactions on Software Engineering). Идея простая: чем больше в функции ветвлений и циклов, тем больше в её графе потока управления независимых путей, по которым может пойти исполнение. Это число и называют цикломатической сложностью $V(G)$. Оно не привязано к длине функции в строках и не зависит от языка: одну и ту же по структуре функцию на Python, Java и C метрика оценит одинаково.

Формула через граф потока

Под графом потока управления (control flow graph, CFG) понимают ориентированный граф, в котором узлы - это базовые блоки (последовательности инструкций без ветвлений), а рёбра - возможные переходы между блоками. Любой if порождает развилку (один узел - два исходящих ребра), любой цикл - обратное ребро.

Маккейб взял из теории графов формулу для цикломатического числа связного графа и адаптировал её к CFG:

$V(G) = E - N + 2P$

где $E$ - число рёбер, $N$ - число узлов, $P$ - число связных компонент графа. Для одной функции $P = 1$, поэтому формула обычно сокращается до $V(G) = E - N + 2$. Множитель $2P$ нужен, когда метрику считают сразу для нескольких процедур одного модуля: тогда $P$ растёт.

Геометрический смысл: $V(G)$ равно числу линейно независимых путей от входа до выхода функции - то есть базису пространства всех возможных маршрутов исполнения. Любой реальный путь можно получить как линейную комбинацию базисных.

Подсчёт на пальцах

Строить CFG руками лень. Маккейб показал, что для структурированного кода без goto достаточно сосчитать решающие точки и прибавить единицу:

$V(G) = 1 + \sum_i d_i$

Решающей точкой считается любая конструкция, добавляющая ребро в CFG:

• if, else if - каждое условие даёт +1;
• case / when в switch - каждая ветка +1 (default обычно не считают);
• while, for, do-while, foreach - каждый цикл +1;
• логические операторы с короткой схемой && и || - каждое появление +1;
• тернарный ?: - +1;
• catch (или except) в обработке исключений - +1.

Сама точка входа в функцию даёт базовую единицу - отсюда «+1» в формуле.

Конкретный пример

Возьмём функцию на псевдокоде:

function classify(x):
    if x < 0:                      # решающая точка 1
        return "neg"
    else if x == 0:                # решающая точка 2
        return "zero"
    else:
        total = 0
        while x > 0:               # решающая точка 3
            total = total + x % 10
            x = x / 10
        return "pos"

Через решающие точки. Их три (if, else if, while), плюс базовая единица - итого $V(G) = 4$.

Через CFG. Базовых блоков - 7: вход, проверка x < 0, возврат «neg», проверка x == 0, возврат «zero», тело цикла, выход. Рёбра:

вход → if1
if1 → return_neg     (x < 0)
if1 → if2            (иначе)
if2 → return_zero    (x == 0)
if2 → while          (иначе)
while → body         (x > 0)
while → return_pos   (x ≤ 0)
body → while         (обратное ребро)
return_neg → exit
return_zero → exit
return_pos → exit

Узлов $N = 7$ (плюс отдельный exit, итого 8, как удобнее), рёбер $E = 11$, $P = 1$. Подставляем: $V(G) = 11 - 8 + 2 \cdot 1 = 5$. Если объединить три return в один exit-узел (классический приём), получится $V(G) = 9 - 6 + 2 = 5$. Расхождение с быстрым подсчётом на 1 - типичная ловушка: else сам по себе не решающая точка, но если внутри else есть отдельный путь без return, граф добавляет лишнее ребро. Поэтому канонический способ - всё-таки CFG, а «решающие точки + 1» - оценка снизу, удобная для эвристики.

Что значат значения

Сам Маккейб рекомендовал держать $V(G) \le 10$ на функцию. Software Engineering Institute (SEI) и стандарт качества ISO/IEC 9126 (сейчас 25010) кодифицировали типичную шкалу:

• 1–10 - простая функция, легко читается и тестируется;
• 11–20 - умеренная сложность, нужна осторожность, желательно покрытие тестами;
• 21–50 - сложная, высокий риск ошибок, кандидат на декомпозицию;
• больше 50 - практически неподдерживаемая; почти всегда означает «гигантский switch» или «парсер на регулярках».

Для классов и модулей суммируют $V(G)$ по всем методам - это даёт weighted methods per class (WMC) из набора метрик Чидамбера–Кемерера.

Связь с количеством тестов

Маккейб показал, что $V(G)$ равно минимальному числу тест-кейсов, необходимых для покрытия всех линейно независимых путей в функции - так называемое basis path coverage. Это сильнее, чем покрытие веток (branch coverage), но слабее, чем покрытие всех маршрутов (которое в общем случае бесконечно из-за циклов).

Практически: если $V(G) = 7$, придётся написать минимум 7 разных тест-кейсов, чтобы дойти до каждой ветки и каждой итерации цикла хотя бы один раз. Поэтому статический анализ часто связывает цикломатическую сложность с требованиями по test coverage в CI.

Критика и ограничения

Метрика проста и популярна, но не лишена недостатков:

1. Не учитывает вложенность. Функция с десятью последовательными if и функция с десятью вложенными друг в друга if получают одинаковую $V(G)$, хотя читаются совершенно по-разному. Для вложенности придумали отдельную метрику - cognitive complexity Сонара.
2. Сильно коррелирует с длиной. Знаменитое исследование Shepperd (1988, «A critique of cyclomatic complexity as a software metric») показало, что $V(G)$ почти линейно зависит от LOC (lines of code). То есть метрика часто измеряет «длину», а не «структурную трудность».
3. Игнорирует семантику. Регулярное выражение с десятью альтернативами и парсер с десятью case имеют одну и ту же сложность, но первый понятнее.
4. Прячет работу за вызовами. Функция, вся логика которой вынесена в десять подметодов, формально получит $V(G) = 1$.

Поэтому в современных кодовых базах $V(G)$ используется не как единственный критерий, а в связке: cognitive complexity, дублирование, покрытие тестами.

Где используется

Цикломатическая сложность встроена практически во все статические анализаторы:

• SonarQube / SonarCloud - порог по умолчанию 15 для функции, 200 для файла; считает и cognitive complexity рядом.
• radon (Python) - radon cc -s -a path/ показывает ранг A–F по таблице, близкой к ISO 9126.
• ESLint - правило complexity с настраиваемым порогом, по умолчанию 20.
• IntelliJ IDEA / WebStorm - инспекция «Method is too complex».
• PMD для Java, lizard - мультиязычный (C, C++, Java, JS, Python, Swift).

В Continuous Integration метрику обычно вешают как warning при превышении 10–15 и как блокер при 30+.

Частые ошибки

• Считают else как решающую точку. Нет, добавляет ребро только if/elif. else - просто продолжение.
• Забывают про && и ||. Условие if (a && b && c) даёт +3, а не +1, потому что short-circuit порождает три ветки.
• Считают default в switch. Он не добавляет независимого пути - это «всё остальное».
• Применяют к коду с goto без анализа CFG. Формула «+1» работает только для структурированного кода; при произвольных переходах нужен честный граф.
• Путают $V(G)$ с числом строк или с числом тестов для 100% покрытия. Это нижняя граница тестов на basis path, не на all-paths.

FAQ

Чем цикломатическая сложность отличается от когнитивной? $V(G)$ считает все решающие точки одинаково и не учитывает вложенность. Cognitive complexity (Sonar) штрафует вложенные конструкции дополнительно: if внутри if стоит дороже, чем два последовательных. Поэтому cognitive complexity лучше коррелирует с субъективной «трудностью чтения», а McCabe - с числом независимых путей.

Какое значение считается «нормальным» в проде? Большинство команд держат функции в диапазоне 1–10. Превышение 15 - повод для код-ревью, 20 - для рефакторинга. Для legacy-кода типичны значения 30–60 на одну функцию, и это сигнал, что её пора разбивать.

Можно ли уменьшить $V(G)$, не меняя логику? Да. Помогают: ранний возврат (guard clauses вместо вложенных if), вынос условий в отдельные предикаты, замена длинного switch на таблицу диспетчеризации (dict функций в Python, Map в JS), polymorphism вместо instanceof-цепочек.

Коротко

Цикломатическая сложность по Маккейбу - это число линейно независимых путей в графе потока управления функции, считаемое по формуле $V(G) = E - N + 2P$ или эквивалентно как «число решающих точек + 1». Значения до 10 считаются нормой, выше 20 - поводом для рефакторинга. Метрика равна минимальному числу тест-кейсов для покрытия базисных путей и встроена в SonarQube, radon, ESLint и большинство IDE. Главное ограничение - она не учитывает вложенность и сильно коррелирует с длиной кода, поэтому работает в связке с cognitive complexity, а не в одиночку.