Property-based тестирование — метод, при котором тест-фреймворк (Hypothesis, QuickCheck) генерирует множество случайных входов и проверяет указанные свойства (инварианты) функции; при неудаче тесты автоматически «сжимаются» до минимального контрпримера. Это позволяет находить неожиданные граничные случаи и нарушения инвариантов, которые трудно перечислить обычными юнит-тестами.
Какие свойства проверять для функции сортировки (если $b=\mathrm{sort}(a)$):
- Отсортированность:
- $\forall i<j:b_i\le b_j$. Проверяет, что выход действительно упорядочен по выбранному сравнению.
- Перестановочность / сохранение мультимножества:
- $\mathrm{multiset}(b)=\mathrm{multiset}(a)$. Гарантирует, что элементы не теряются и не добавляются (включая кратности).
- Сохранение длины:
- $|b|=|a|$.
- Идемпотентность:
- $\mathrm{sort}(\mathrm{sort}(a))=\mathrm{sort}(a)$. Проверяет, что повторная сортировка не меняет результат.
- Стабильность (если ожидается стабильная сортировка):
- Если $\text{key}(a_i)=\text{key}(a_j)$ и $i<j$, то в выходе позиция элемента $a_i$ раньше позиции $a_j$. Формально: для позиций $p(\cdot )$ в $b$ $\text{key}(a_i)=\text{key}(a_j)\wedge i<j\Rightarrow p(i)<p(j)$.
- Корректность при нестандартных значениях:
- Правильная обработка пустого и одноэлементного массива, дубликатов, уже отсортированных и обратно отсортированных входов, особых значений (например, NaN для float).
- Свойства компаратора (если сортировка с пользовательским компаратором):
- Компаратор должен задавать строгую слабую упорядоченность: транзитивность и согласованность (например, $\forall x,y,z:(x\le y\wedge y\le z)\Rightarrow x\le z$); иначе корректность сортировки может быть не определена.
Примеры сценариев генерации данных:
- Различные длины (включая пустой), много дубликатов, повторяющиеся шаблоны, уже отсортированные и реверсивные списки, случайные и краевые значения (очень большие/малые, NaN), произвольные ключи и компараторы.
Как property-based тесты дополняют обычные юнит-тесты:
- Находят неожиданные и редкие граничные случаи автоматическим перебором входного пространства и последующим сжатием до минимального контрпримера.
- Проверяют общие инварианты (высокоуровневые свойства), тогда как юнит-тесты обычно проверяют конкретные примеры и контрактные случаи (API-ограничения, ожидаемые исключения, производительность, побочные эффекты).
- Не заменяют юнит-тесты: конкретные примеры, регрессионные тесты и тесты на поведение в документации остаются важными для понятности и требований к функции.
Итого: в property-based тестах для сортировки прописывают инварианты (отсортированность, сохранение мультимножества, идемпотентность, стабильность и т.п.), фреймворк генерирует входы и находит минимальные контрпримеры — это расширяет охват тестирования по сравнению с наборами ручных юнит-тестов.