Покрытие путей

Что такое покрытие путей? #

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

Рассмотрим функцию с двумя последовательными операторами if:

def process_order(amount, is_member):
    discount = 0

    if amount > 100:          # Решение 1
        discount = 10

    if is_member:             # Решение 2
        discount += 5

    return amount - discount

Покрытие операторов требует тестов, выполняющих каждую строку — 2 теста могут быть достаточны.

Покрытие решений требует True и False для каждого решения — 2 теста достаточны.

Покрытие путей требует каждой комбинации путей через все решения:

С 2 последовательными решениями у нас 4 пути. С N последовательными решениями — 2^N путей. Этот экспоненциальный рост — причина, по которой полное покрытие путей часто непрактично.

Проблема взрыва путей #

Добавьте цикл — и пути становятся бесконечными:

def retry_request(url, max_retries=3):
    for attempt in range(max_retries):
        response = send_request(url)
        if response.status == 200:
            return response
    raise TimeoutError("Max retries exceeded")

Цикл может выполниться 0, 1, 2 или 3 раза. Каждая итерация добавляет точку принятия решения. Для цикла до N итераций с M решениями внутри, общее число путей может достигать M^N.

Поэтому практики используют basis path testing вместо исчерпывающего покрытия путей.

Графы потока управления #

Перед подсчётом путей представьте код как граф потока управления (CFG):

• Узлы представляют операторы или блоки последовательных операторов
• Рёбра представляют поток управления между узлами
• Узлы решений имеют два или более исходящих ребра

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

Цикломатическая сложность (предложена Томасом Маккейбом в 1976 году) измеряет число линейно независимых путей через программу. Она даёт минимальное число тест-кейсов для покрытия базисных путей.

Три эквивалентные формулы:

1. V(G) = E - N + 2 (E = рёбра, N = узлы)
2. V(G) = P + 1 (P = число точек принятия решений/предикатов)
3. V(G) = R (R = число регионов в планарном графе, включая внешний)

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

Большинство стандартов рекомендуют держать цикломатическую сложность ниже 10 на функцию.

Метод Basis Path Testing #

Basis path testing Тома Маккейба предоставляет системный способ вывода тест-кейсов:

Шаг 1: Нарисуйте граф потока управления.

Шаг 2: Вычислите цикломатическую сложность V(G).

Шаг 3: Определите базисный набор независимых путей. Начните с простейшего пути, затем меняйте по одному решению за раз.

Шаг 4: Создайте тест-кейсы для каждого базисного пути.

Пример: Валидация логина #

def validate_login(username, password, is_locked):
    if is_locked:                    # D1
        return "ACCOUNT_LOCKED"

    if not username:                 # D2
        return "USERNAME_REQUIRED"

    if len(password) < 8:           # D3
        return "PASSWORD_TOO_SHORT"

    return "VALID"

V(G) = 3 + 1 = 4 (три решения плюс один).

Базисные пути:

1. D1=True → “ACCOUNT_LOCKED”
2. D1=False, D2=True → “USERNAME_REQUIRED”
3. D1=False, D2=False, D3=True → “PASSWORD_TOO_SHORT”
4. D1=False, D2=False, D3=False → “VALID”

Тест-кейсы:

Четыре тест-кейса обеспечивают покрытие базисных путей.

Инструменты для анализа путей #

• SonarQube — отчёты о цикломатической сложности по функциям и файлам
• Lizard — быстрый анализатор сложности, поддерживающий 20+ языков
• radon — анализ сложности для Python
• ESLint (правило complexity) — ограничение цикломатической сложности для JavaScript/TypeScript
• PMD — анализ сложности для Java/Apex

Упражнение: Basis Path Testing #

Задача 1 #

Выведите базисные пути и тест-кейсы для функции:

def calculate_shipping(weight, distance, is_express):
    base_cost = 5.0

    if weight > 10:
        base_cost += weight * 0.5
    else:
        base_cost += weight * 0.3

    if distance > 500:
        base_cost *= 1.5

    if is_express:
        base_cost *= 2

    return round(base_cost, 2)

Задача 2 #

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

def grade_student(score, attendance, has_extra_credit):
    if score >= 90:
        grade = "A"
    elif score >= 80:
        grade = "B"
    elif score >= 70:
        grade = "C"
    else:
        grade = "F"

    if attendance < 75:
        grade = "F"

    if has_extra_credit and grade != "F":
        grade = chr(ord(grade) - 1)

    return grade

Покрытие путей vs. другие критерии #

Покрытие путей — сильнейший критерий, но обычно непрактичен для полного покрытия. Basis path testing — практичный компромисс.

Когда использовать покрытие путей #

Используйте basis path testing когда:

• Тестируете критические алгоритмы (финансовые расчёты, логика безопасности)
• Код имеет умеренную сложность (V(G) < 15)
• Нужно обосновать достаточность тестов перед аудиторами
• Рефакторите сложные функции — пути помогают понять, что делает код

Пропустите полное покрытие путей когда:

• Функции содержат циклы с большим числом итераций
• Цикломатическая сложность превышает 20 (сначала рефакторинг)
• Код достаточно прост, и покрытия решений хватает

Ключевые выводы #

• Покрытие путей тестирует каждый уникальный путь выполнения от входа до выхода
• Полное покрытие путей непрактично из-за экспоненциального роста и бесконечных путей циклов
• Цикломатическая сложность V(G) = P + 1 даёт минимальное число тестов базисных путей
• Basis path testing — практичный подход: тестируйте независимые пути, а не все пути
• Держите цикломатическую сложность ниже 10 на функцию
• Используйте инструменты SonarQube, Lizard или radon для автоматического измерения сложности