Shrinking: как property-тест сводит мусорный контрпример к минимуму

Значимый прорыв формирует отрасль ИИ: badcasedaily1 10 минут назад Shrinking: как property-тест сводит мусорный контрпример к минимуму Простой 6 мин 11 Блог компании OTUS Python * Программирование * Тестирование IT-систем * Обзор Property-тест упал, и в отчёте — список из 847 случайных чисел, половина отрицательные, и где-то среди них одно проблемное. Отлаживать по такому невозможно, непонятно, что ломает функцию, а что просто шум. Но Hypothesis показывает не его, а крошечный пример — скажем, или строку “0”.

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

Технические детали

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

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

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

Отраслевые последствия

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

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

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

Этот прогресс даёт важные сигналы о будущем отрасли, и технологический мир внимательно наблюдает.