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

Цикломатическая сложность (англ. cyclomatic complexity) — это метрика программного обеспечения, используемая для количественной оценки сложности программы. Она измеряет количество линейно независимых путей выполнения через исходный код программы. Предложена Томасом Маккейбом в 1976 году как способ выявления модулей с высокой сложностью, которые требуют более тщательного тестирования и подвержены большему количеству ошибок.

История

Метрика была впервые описана Томасом Дж. Маккейбом-младшим в статье «A Complexity Measure» (IEEE Transactions on Software Engineering, декабрь 1976 года). Маккейб работал в компании Hughes Aircraft Company, где занимался вопросами качества и тестирования программного обеспечения. Он предложил использовать теорию графов для анализа управляющего потока программы, заменив субъективные оценки сложности на объективное числовое значение.

Изначально метрика предназначалась для оценки сложности модулей на языке Фортран, но быстро распространилась на другие языки программирования. В 1980-х годах цикломатическая сложность стала одной из ключевых метрик в методологии структурного тестирования и анализа качества кода. В 1990-х годах она вошла в стандарты разработки программного обеспечения, такие как IEEE Std 982.1-1988, где рекомендовалось поддерживать сложность отдельных модулей не выше 10.

Определение и математическая основа

Цикломатическая сложность вычисляется на основе графа управляющего потока (Control Flow Graph, CFG) программы. Граф представляет собой ориентированный граф, где вершины соответствуют блокам последовательного кода (без ветвлений), а рёбра — возможным переходам между блоками.

Формула

Цикломатическая сложность \( M \) для графа с одним входом и одним выходом вычисляется по формуле:

\[ M = E - N + 2P \]

где:

• \( E \) — количество рёбер в графе;
• \( N \) — количество вершин в графе;
• \( P \) — количество компонент связности графа (обычно \( P = 1 \) для одной программы или функции).

Для графа с одним входом и одним выходом формула упрощается до:

\[ M = E - N + 2 \]

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

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

Пример вычисления

Рассмотрим простую функцию на псевдокоде:

`` function example(x, y): if (x > 0) then print("положительное") else print("неположительное") end if if (y > 0) then print("y положительное") end if end function ``

Граф управляющего потока будет иметь:

• 5 вершин (начало, два условных блока, два блока вывода, конец);
• 7 рёбер (переходы между вершинами).

Цикломатическая сложность: \( M = 7 - 5 + 2 = 4 \).

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

Классификация значений

На практике значения цикломатической сложности интерпретируются следующим образом:

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

Применение

Тестирование

Цикломатическая сложность напрямую связана с количеством тестовых случаев, необходимых для достижения 100% покрытия ветвей (branch coverage). Минимальное количество тестов равно \( M \). Это делает метрику полезной для планирования тестирования и оценки его полноты.

Оценка рисков

Модули с высокой цикломатической сложностью статистически чаще содержат ошибки. Исследования показывают корреляцию между \( M > 10 \) и повышенной плотностью дефектов. Метрика используется для выявления «горячих точек» кода, требующих рефакторинга или дополнительного тестирования.

Рефакторинг

Снижение цикломатической сложности является одной из целей рефакторинга. Типичные приёмы:

• Разбиение длинных функций на несколько более коротких;
• Замена вложенных условных операторов на ранний возврат (early return);
• Использование полиморфизма вместо длинных цепочек if-else;
• Извлечение сложных условий в отдельные функции.

Стандарты качества

Многие инструменты статического анализа кода (например, SonarQube, ESLint, PMD) включают проверку цикломатической сложности. Превышение порогового значения (обычно 10–15) считается нарушением стиля кодирования.

Критика

Несмотря на широкое распространение, цикломатическая сложность имеет ряд ограничений:

1. Не учитывает сложность данных. Метрика оценивает только управляющий поток, игнорируя сложность структур данных, алгоритмов и взаимодействия между модулями.
2. Не различает типы ветвлений. Оператор switch с 10 case даёт ту же сложность, что и 10 последовательных if, хотя первый может быть более читаемым.
3. Зависит от стиля кодирования. Один и тот же алгоритм может быть реализован с разной цикломатической сложностью в зависимости от стиля (например, использование рекурсии вместо циклов).
4. Не учитывает вложенность. Два вложенных if дают ту же сложность, что и последовательные, хотя вложенность значительно усложняет понимание кода.
5. Неприменима к некоторым парадигмам. В функциональных языках программирования (Haskell, Clojure) условные операторы используются редко, и метрика может давать заниженные значения, не отражающие реальной сложности.

Альтернативные метрики

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

• Сложность Холстеда (Halstead complexity) — учитывает количество операторов и операндов.
• Глубина вложенности (Nesting depth) — измеряет максимальную глубину вложенных структур.
• Когнитивная сложность (Cognitive complexity) — разработана компанией SonarSource для оценки сложности понимания кода человеком.
• Сцепление (Coupling) и связность (Cohesion) — метрики, оценивающие взаимосвязи между модулями.

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

Цикломатическая сложность вычисляется большинством современных инструментов статического анализа:

• SonarQube — поддерживает множество языков (Java, C#, Python, JavaScript и др.);
• ESLint — для JavaScript/TypeScript (правило complexity);
• PMD — для Java, Apex, PL/SQL;
• Radon — для Python;
• GCC — компилятор GNU C/C++ имеет опцию -fcyc-complexity;
• Visual Studio — встроенный анализатор кода для C# и C++.

Интересные факты

• В оригинальной статье Маккейба 1976 года метрика называлась «цикломатическое число» (cyclomatic number) по аналогии с цикломатическим числом графа в теории графов.
• Маккейб предложил использовать метрику не только для оценки сложности, но и для определения минимального количества тестовых случаев, необходимых для покрытия всех путей.
• В некоторых компаниях (например, в Microsoft) цикломатическая сложность используется как один из критериев для code review: модули с \( M > 15 \) требуют обязательного обсуждения командой.
• Метрика критикуется за то, что её легко «обмануть»: разбив одну сложную функцию на несколько простых, можно снизить значение \( M \) для каждой из них, но общая сложность системы не уменьшится.

Источники

• McCabe, T. J. (1976). «A Complexity Measure». IEEE Transactions on Software Engineering, SE-2(4), 308–320.
• IEEE Std 982.1-1988 — Standard Dictionary of Measures to Produce Reliable Software.
• Watson, A. H., & McCabe, T. J. (1996). «Structured Testing: A Testing Methodology Using the Cyclomatic Complexity Metric». NIST Special Publication 500-235.
• Pressman, R. S. (2014). «Software Engineering: A Practitioner's Approach» (8th ed.). McGraw-Hill.
• SonarSource. (2023). «Cognitive Complexity — A New Way to Measure Understandability».