Property-тест упал, и в отчёте — список из 847 случайных чисел, половина отрицательные, и где-то среди них одно проблемное. Отлаживать по такому невозможно, непонятно, что ломает функцию, а что просто шум. Но Hypothesis показывает не его, а крошечный пример — скажем, [0, 0] или строку “0”. Между падением на грязном входе и этим аккуратным минимумом работает shrinking, и устроен он очень интересно.

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

Зачем вообще ужимать

В случайном контрпримере полно лишнего. В списке из 847 элементов баг могут вызывать два, а остальные 845 — балласт, который только мешает читать. Ужать контрпример — значит найти простейший вход, на котором свойство всё ещё падает: выкинуть лишнее, прижать числа к нулю, строки к пустым, оставить ровно то, без чего падение пропадает.

По хорошему минимуму обычно сразу видно, в чём дело: [0, 0] для функции, спотыкающейся на дубликатах, или пустая строка для забытого края.

Наивный способ и где он буксует

Классический QuickCheck ужимает значения по типу. Для каждого типа пишется функция shrink, которая возвращает упрощённые версии: для целого — числа поближе к нулю, для списка — варианты с выкинутыми и укороченными элементами. Фреймворк подставляет этих кандидатов, пока находит падающих.

Буксует это на композиции. Генератор почти никогда не отдаёт сырой тип напрямую, его преобразуют: целое превращают в дату, список пар собирают в объект, строку фильтруют по формату. А shrink написан для исходного типа и про преобразование ничего не знает. Стоит наложить map, и связь между значением и его shrinker рвётся: либо минимизация производного значения теряется, либо под каждое преобразование приходится писать новый shrinker руками. Отсюда и вечная возня с ручными shrink-функциями, и то, что они ломаются при рефакторинге генераторов.

Идея интегрированного shrinking: ужимать источник случайности

Hypothesis может зайти с другой стороны. Любое сгенерированное значение — это функция от внутреннего потока байтов, который тянет генератор: и целое, и список, и объект строятся, читая «примитивы» из этого буфера. Раз так, ужимать можно не значение, а сам буфер: сделать его проще — короче и с меньшими байтами, потом заново прогнать генератор и проверить, падает ли свойство всё ещё.

Главное следствие: минимизация композируется сама собой. Какие бы map, filter и builds ни стояли поверх генератора, значение остаётся функцией того же буфера, поэтому упрощение буфера упрощает и производное значение. Ручных shrinker нет вовсе, есть один алгоритм, работающий на уровне источника случайности.

Маленькая реализация

Соберём интегрированную минимизацию целиком. Источник случайности — буфер байтов, из которого генератор тянет примитивы; генератор строит список целых, читая «байт-продолжатель» и значения.

class Source:
    """Источник случайности: генератор тянет байты отсюда."""
    def __init__(self, buf):
        self.buf, self.i = list(buf), 0
    def draw(self):
        b = self.buf[self.i] if self.i < len(self.buf) else 0
        self.i += 1
        return b

def gen_list(src):
    """Список целых: пока байт-продолжатель нечётный — рисуем ещё элемент."""
    xs = []
    while src.draw() % 2 == 1:
        xs.append(src.draw())
    return xs

Свойство, которое мы нечаянно нарушим: в списке не должно быть элемента не меньше пяти.

def fails(xs):
    return any(x >= 5 for x in xs)        # баг: значение >= 5 встречаться не должно

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

def candidates(buf):
    for i in range(len(buf)):                       # удалить байт
        yield buf[:i] + buf[i + 1:]
    for i in range(len(buf)):                       # уменьшить байт на единицу
        if buf[i] > 0:
            yield buf[:i] + [buf[i] - 1] + buf[i + 1:]
    for i in range(len(buf)):                       # обнулить байт
        if buf[i] > 0:
            yield buf[:i] + [0] + buf[i + 1:]

def simpler(a, b):                                  # порядок shortlex
    return (len(a), a) < (len(b), b)

def still_fails(buf):
    return fails(gen_list(Source(buf)))

def shrink(buf):
    progress = True
    while progress:                                 # жадный спуск до фикспоинта
        progress = False
        for cand in candidates(buf):
            if simpler(cand, buf) and still_fails(cand):
                buf, progress = cand, True
                break                               # начинаем проходы заново от более простого буфера
    return buf

Запустим на грязном случайном буфере:

import random
random.seed(0)
start = [random.randint(0, 9) for _ in range(40)]

print(gen_list(Source(start)))                      # длинный список со случайными значениями
minimal = shrink(start)
print(gen_list(Source(minimal)))                    # [5] — минимальный список, всё ещё нарушающий свойство

Спуск удаляет лишние байты, и список укорачивается до одного элемента; уменьшает байт значения, пока остаётся не меньше пяти — на четвёрке падение пропадает, и шаг откатывается. На выходе [5]. Мы ни разу не написали shrinker для списка: ужали байты, регенерируя значение, и минимальное значение получилось само. Накинь поверх gen_list любое преобразование — минимизация продолжит работать, потому что упрощается источник, а не результат.

Полезно увидеть спуск по шагам. Если логировать принятые упрощения, выходит примерно так:

исходный буфер длины 40   ->  список из 11 элементов, среди них есть 8
удаление байтов           ->  [8]      (буфер сжался до пары байт)
понижение значения 8 -> 7 ->  [7]
понижение 7 -> 6          ->  [6]
понижение 6 -> 5          ->  [5]
понижение 5 -> 4          ->  свойство НЕ нарушается — шаг откатывается

Сначала удаляются целые куски буфера, и список схлопывается до одного элемента, потом единственное значение жадно понижается, пока остаётся не меньше пяти. Откат на четвёрке фиксирует границу: [5] — локальный минимум, из которого ни одно простое упрощение не ведёт к более простому падающему входу.

В реальном Hypothesis проходов больше, чем три в нашем мелком примере, но идея та же — структурные правки буфера, применяемые жадно до фикспоинта. Удаление участков выкидывает элементы списков и опциональные части, обнуление гонит числа к нулю, а строки к пустоте, понижение уменьшает отдельные числовые блоки, есть сортировка и дедупликация блоков, замена участка на меньший, удаление крупными кусками с откатом, если перестало падать. Каждый проход — это «поправить буфер, перегенерировать значение, принять, если всё ещё падает и стало проще, иначе откатить». В сумме получается спуск по буферам к локальному минимуму в порядке shortlex.

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

Фазы движка: повтор, генерация, минимизация, объяснение

Минимизация в Hypothesis — лишь одна из фаз, и их порядок объясняет, почему падения стабильны, а минимум приходит не сразу. Сначала фаза повтора проигрывает контрпримеры из локальной базы и заданные через @example, так что уже найденный баг ловится мгновенно, не дожидаясь удачи генератора. Потом фаза генерации перебирает новые случайные входы. Нашли падение — включается минимизация, тот самый спуск по буферу.

Если задан target, отдельная фаза двигает генерацию к экстремальным значениям метрики. Наконец, фаза объяснения пытается показать, какая часть входа отвечает за падение, помечая участки буфера, варьирование которых падение сохраняет.

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

Если совсем коротко

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

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

Больше о тестировании читайте в статьях:

Автоматический поиск ошибок полезен не только в property-based testing: похожие идеи работают в фаззинге, тестировании API и других подходах, где входные данные становятся способом находить редкие и трудноуловимые баги. На бесплатных открытых уроках можно посмотреть эти инструменты в деле, познакомиться с преподавателями-практиками и задать вопросы по своим кейсам.

  • 2 июля, 20:00. «REST Assured & JSON Schema Validator: автоматизация тестирования API на практике». Записаться
    Разберём, как автоматизировать проверки API и валидировать ответы сервисов с помощью JSON Schema.

  • 23 июля, 20:00. «Фаззинг и реверс: как понять, что делает программа, найти в ней ошибки». Записаться
    Поговорим о поиске уязвимостей и скрытых дефектов через фаззинг и анализ поведения программ.

Больше бесплатных уроков июня смотрите в дайджесте.