ЯдроКодаподготовка к экзаменам
Подготавливаем текст, источники и редакционные примечания без изменения разметки страницы.
Автор: Казачкин Даниил Михайлович · Обновлено
Идея QuickCheck на собственном примере Python: свойства сортировки, контрпримеры, генераторы и границы случайного тестирования.
Обычный тест выбирает вход и записывает ожидаемый выход. Для нескольких примеров это просто. Но функция сортировки принимает списки разной длины, с повторами, отрицательными числами и уже упорядоченными участками. Автор тестов способен пропустить целый класс входов, даже если хорошо понимает алгоритм. Возникает задача: сформулировать требования один раз и автоматически искать данные, которые их нарушают.
Проверка свойств, или property-based testing, переносит внимание с отдельных ответов на общие отношения. При этом правильное свойство не появляется автоматически. Разработчик по-прежнему должен определить область входов и смысл корректности. Генератор расширяет поиск ошибок, а не освобождает от проектирования контракта.
Подход получил известность благодаря семейству QuickCheck, первоначально для Haskell. Первичная работа MacIver, Hatfield-Dodds и других участников, JOSS 2019, описывает библиотеку Hypothesis и применение проверки свойств к Python, включая научное программное обеспечение. Важная идея — описывать свойства и область входов, после чего искать нарушающие их примеры. Это исследовательский инструмент, а не обещание доказать любую программу конечным числом запусков. Статья Hypothesis.
Современная библиотека Hypothesis применяет этот подход к Python, предоставляя стратегии данных и поиск контрпримеров. Ниже используется собственный полный перебор маленькой области, чтобы результат был прозрачен и не зависел от случайного seed. Пример демонстрирует проектирование свойств, а не воспроизводит внутренний алгоритм QuickCheck или Hypothesis.
Пусть разработчик решил сначала убрать повторы, а затем отсортировать оставшиеся числа. Для списка из разных элементов результат выглядит правильным. Проверка «соседние числа не убывают» тоже проходит. Но задача сортировки требует сохранить не только порядок, а все исходные элементы вместе с количеством повторений.
from collections import Counter
from itertools import product
def broken_sort(values):
return sorted(set(values))
def ordered(values):
return all(a <= b for a, b in zip(values, values[1:]))
counterexample = None
for length in range(4):
for values in product([-1, 0, 1], repeat=length):
result = broken_sort(values)
assert ordered(result)
if Counter(result) != Counter(values):
counterexample = values
break
if counterexample is not None:
break
assert counterexample == (-1, -1)
print(counterexample)Мы нашли короткий контрпример: два одинаковых числа превращаются в одно. Порядок результата правильный, а мультимножество элементов изменилось. Следовательно, одно правдоподобное свойство было недостаточным. Для целых чисел сочетание упорядоченности и сохранения мультимножества уже гораздо точнее описывает ожидаемую сортировку.
Контрпример здесь минимален по длине в выбранном переборе, но не является результатом общего алгоритма уменьшения произвольных входов. В реальной библиотеке уменьшение, или shrinking, помогает превращать большой падающий случай в маленький. Это особенно полезно, когда ошибка зависит от длинной последовательности действий и её трудно объяснить по начальному сообщению теста.
Предположим, проверяем пару encode/decode: декодирование закодированного значения должно возвращать исходное. Это хорошее отношение, но две функции могут согласованно ошибаться относительно внешнего формата. Поэтому дополнительно нужны известные примеры протокола и проверка совместимости с независимой реализацией. Иначе тест подтверждает лишь согласованность двух собственных ошибок.
Похожая ситуация возникает в TypeScript. Статический тип описывает допустимую форму значения для компилятора, но входящий JSON существует до этой гарантии. Свойство для валидатора может говорить: все принятые значения удовлетворяют независимому предикату домена. Для сериализатора — что повторное чтение сохраняет существенные поля. Не следует превращать тест в копию той же проверки, написанную другими именами.
Генератор тоже является частью эксперимента. Если он всегда создаёт непустые уникальные списки, пример выше никогда не обнаружит потерю дублей. Если даты генерируются только в середине месяца, границы месяцев останутся невидимыми. Начните с перечня классов входов: пустота, повторы, минимальные размеры, предельные значения, неверный внешний формат. Затем проверьте, какие из них действительно посещаются.
Введение Hypothesis показывает стратегии и интеграцию свойств с обычными тестами. Для проекта разумно сохранять найденный контрпример как отдельную регрессию с понятным названием. Тогда важная ошибка останется проверяемой даже после изменения генератора или настроек библиотеки.
Если контракт расширяется с целых чисел на вещественные, отдельно определите поведение для бесконечностей и специальных значений. Прежнее свойство упорядоченности может перестать описывать ожидаемый порядок. Исключение неудобных случаев из генератора допустимо только тогда, когда их действительно исключает контракт функции, а не когда они мешают тесту пройти.
Случайная проверка не доказывает отсутствие ошибки на бесконечной области. Полный перебор конечной области доказывает утверждение только для этой области и при корректности самого проверяющего кода. В нашем эксперименте это списки длины до трёх из трёх целых значений; вывод нельзя переносить на произвольные объекты с нестандартным сравнением.
Подход особенно полезен для преобразований данных, парсеров, денежных округлений, коллекций и последовательностей команд. Начните с одной функции, для которой можно назвать независимый инвариант. Хороший итог работы — не большое число запусков, а ясный контракт, разнообразная область поиска и маленький воспроизводимый случай, объясняющий реальную ошибку.
Самостоятельный русскоязычный разбор ЯдроКода. Описания первоисточников отделены от авторских учебных примеров и инженерных выводов. Материал не является переводом или перепечаткой.
Учебные данные, расчёты, таблицы и программные примеры созданы для этой публикации. Иллюстрации и программный код из первоисточников не воспроизводятся.