Когда property-based testing (QuickCheck) лучше примерного тестирования
- Покрывает большое пространство входов и находит неожиданные крайние случаи, которые трудно перечислить вручную.
- Хорошо проверяет инварианты (семантику), а не конкретные примеры; полезно, когда поведение можно формализовать свойствами.
- Автоматически генерирует комбинации и случайные вариации (фуззинг), легко находит редкие баги и даёт сокращённый воспроизводимый пример (shrinking).
- Менее полезен, если требуются точные примеры требований UI/UX или когда спецификация неформальна; но превосходит example‑тесты для алгоритмов и преобразований данных.
Свойства для функции сжатия строки (обобщённо, для lossless compression; если у вас конкретный формат — адаптировать формулировки)
1) Lossless (обратимость)
$\mathrm{decompress}(\mathrm{compress}(s))=s$ (сжатие + распаковка возвращают исходную строку).
2) Идемпотентность компрессии
$\mathrm{compress}(\mathrm{compress}(s))=\mathrm{compress}(s)$ (повторное сжатие не меняет результат).
3) Сохранение длины при распаковке
$|\mathrm{decompress}(\mathrm{compress}(s))|=|s|$
4) Сохранение мультимножества символов при распаковке
$\forall c:\mathrm{count}(c,\mathrm{decompress}(\mathrm{compress}(s)))=\mathrm{count}(c,s)$
5) Сохранение порядка групп (для RLE‑подобных алгоритмов)
Если мы разбиваем $s$ на последовательность максимальных равных символов (runs), то последовательность символов этих блоков сохраняется:
$runs\_chars(s)=runs\_chars(\mathrm{decompress}(\mathrm{compress}(s)))$
6) Граничные случаи
- пустая строка: $\mathrm{compress}("")$ — корректно определена (обычно $"")$.
- единичный символ: для любого $c$ поведение определено: $\mathrm{decompress}(\mathrm{compress}(c))=c$.
(при наличии дополнительных обещаний — например, что compress уменьшает длину для длинных одинаковых подряд символов — формулировать и тестировать такие свойства отдельно).
Стратегия генерации тестовых данных (QuickCheck‑генераторы и shrinking)
1) Основные типы входов (генерировать смесь):
- пустая строка (вероятность ~$10\%$),
- короткие строки длины $1\dots 10$,
- средние $10\dots 100$,
- редкие длинные до, например, $10^4$ (или меньше, чтобы тесты быстрые).
2) Композиционные генераторы (для RLE/похожих алгоритмов удобно):
- генерировать число блоков (runs) $k$ из распределения, сосредоточенного на малых значениях, но с долгим хвостом (например, геометрическое): $k\sim \mathrm{Geom}(p)$.
- для каждого блока генерировать символ $c$ (из набора: ASCII letters, digits, пробелы, специальные, Unicode) — учитывать разные кодовые точки.
- для каждого блока генерировать длину run $n$ из смеси: чаще маленькие ($1\dots 3$), иногда большие (например, до $10^3$ или $10^4$), можно использовать геометрическое или смешанное распределение.
3) Специфические краевые шаблоны (обязательно включать):
- долгие повторы одного символа (один run длины большая),
- частые смены символов (альтернативы: "ababab..."),
- много разных символов без повторов,
- символы с кодами >$127$ (Unicode), управляющие символы, NUL (\(\0\)),
- строки с цифрами и буквами, если формат сжатия включает цифры (чтобы проверить разбор цифр в коде).
4) Shrinking (стратегия уменьшения при неудаче)
- первое стремление — сократить длину строки к $0$ (empty).
- уменьшать число блоков $k$.
- уменьшать длины блоков (run lengths) по бинарному поиску/делению пополам.
- заменять символы на один фиксированный символ (например, 'a') для упрощения схемы.
- убирать/сокращать Unicode коды к ASCII.
Эти шаги дают минимальный воспроизводимый пример ошибки.
5) Практические советы
- ограничьте максимальную длину, чтобы тесты оставались быстрыми (например, до $10^4$ символов).
- комбинируйте «направленные» генераторы (long runs, alternating) и «случайные» генераторы для лучшего покрытия.
- проверяйте свойства с декомпрессией и с idempotence отдельно — это помогает локализовать баги.
- используйте seed‑параметры и параметр размера QuickCheck (size) для постепенного увеличения сложности.
Короткая проверочная схема (псевдокод QuickCheck):
- для случайной s из генератора: assert $\mathrm{decompress}(\mathrm{compress}(s))=s$;
- assert $\mathrm{compress}(\mathrm{compress}(s))=\mathrm{compress}(s)$;
- assert $|\mathrm{decompress}(\mathrm{compress}(s))|=|s|$;
- дополнительные свойства для специфичного формата (парсинг чисел, корректность границ и т.п.).
Этого набора обычно достаточно, чтобы выявить большинство логических ошибок реализации сжатия.