Как перестать беспокоиться и начать писать тесты на основе свойств

В последнее время все чаще встречаются упоминания о некоем волшебном средстве — тестировании на основе свойств (property based testing, если надо погуглить англоязычную литературу). Большинство статей на эту тему рассказывают о том, какой это классный подход, затем на элементарном примере показывают как написать такой тест используя какой-то конкретный фреймворк, в лучшем случае подсказывают несколько часто встречающихся свойств, и… на этом все заканчивается. Дальше изумленный и воодушевленный читатель пытается применить все это на практике, и упирается в то, что свойства как-то не придумываются. И к большому сожалению часто на этом сдается. В этой статье я постараюсь расставить приоритеты немного по другому. Начну все-таки с более-менее конкретного примера, чтобы объяснить что это за зверь такой. Но пример, надеюсь, не совсем типичный для подобного рода статей. Затем попробую разобрать некоторые проблемы, связанные с этим подходом, и как их можно решить. А вот дальше — свойства, свойства и только свойства, с примерами куда их можно приткнуть. Интересно?

Тестируем хранилище ключ-значение в три коротких теста

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

• записать значение по ключу
• проверить, существует ли запись с нужным ключом
• прочитать значение по ключу
• получить список записанных элементов
• получить копию хранилища

При классическом подходе на основе примеров типичный тест выглядел бы как-то так:

storage = Storage()
storage['a'] = 42
assert len(storage) == 1
assert 'a' in storage
assert storage['a'] == 42

Или так:

storage = Storage()
storage['a'] = 42
storage['b'] = 73
assert len(storage) == 2
assert 'a' in storage
assert 'b' in storage
assert storage['a'] == 42
assert storage['b'] == 73

И в общем-то подобных тестов можно и нужно будет написать немного больше, чем дофига. Причем чем сложнее внутренняя реализация, тем больше шансов все равно что-то упустить. Короче, долгая, нудная и часто неблагодарная работа. Как хорошо было бы ее на кого-то спихнуть! Например, заставить компьютер генерировать тест-кейсы за нас. Для начала попробуем сделать что-то такое:

storage = Storage()
key = arbitrary_key()
value = arbitrary_value()
storage[key] = value
assert len(storage) == 1
assert key in storage
assert storage[key] == value 

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

storage = arbitrary_storage()
storage_copy = storage.copy()
assert len(storage) == len(storage_copy)
assert all(storage_copy[key] == storage[key] for key in storage)
assert all(storage[key] == storage_copy[key] for key in storage_copy)

Здесь вместо того, чтобы взять пустое хранилище мы генерируем произвольное с некими данными, и проверяем, что его копия идентична оригиналу. Да, генератор надо еще написать, используя потенциально глючное публичное API, но как правило это не такая сложная задача. Заодно если в реализации есть какие-то серьезные баги, то высоки шансы, что начнутся падения в процессе генерации, так что это можно считать еще и своеобразным бонусным smoke-тестом. Зато теперь мы можем быть уверены — все, что смог нагенерить генератор может быть корректно скопировано. А благодаря первому тесту мы точно знаем, что генератор может создать хранилище хотя бы с одним элементом. Время для следующего теста! Заодно повторно используем генератор:

storage = arbitrary_storage()
backup = storage.copy()
key = arbitrary_key()
value = arbitrary_value()
if key in storage:
	return
storage[key] = value
assert len(storage) == len(backup) + 1
assert key in storage
assert storage[key] == value
assert all(storage[key] == backup[key] for key in backup)

Берем произвольное хранилище, и проверяем, что можем туда добавить еще один элемент. А значит генератор может создать хранилище с двумя элементами. И в него тоже можно добавить элемент. И так далее (сразу вспоминается такая штука, как математическая индукция). В результате написанные три теста и генератор позволяют достаточно надежно проверить, что в хранилище можно добавить произвольное число разных элементов. Всего три коротких теста! Вот в общем-то и вся идея тестов на основе свойств:

• находим свойства
• проверяем свойства на куче разных данных
• профит!

Кстати, этот подход никак не противоречит принципам TDD — тесты точно так же можно писать до кода (по крайней мере лично я обычно так и делаю). Другое дело, что заставить такой тест стать зеленым может оказаться сильно сложнее, чем традиционный, но зато когда он наконец успешно пройдет мы будем уверены, что код действительно соблюдает определенную часть контракта.

Это все конечно хорошо, но...

При всей привлекательности подхода тестирования на основе свойств есть целый ворох проблем. В этой части я постараюсь разобрать наиболее часто встречающиеся. И если не считать проблемы с собственно сложностью поиска полезных свойств (к которой я вернусь в следующем разделе), то на мой взгляд самая большая беда начинающих — это часто ложная уверенность в хорошем покрытии. Действительно, мы написали несколько тестов, которые генерируют сотни тест-кейсов — что может пойти не так? Если посмотреть на пример из предыдущей части, то на самом деле много чего. Для начала, написанные тесты не дают никакой гарантии, что storage.copy() действительно сделает «глубокую» копию, а не просто скопирует указатель. Другая дыра — нет нормальной проверки, что key in storage вернет False если искомого ключа нет в хранилище. И список можно еще продолжать. Ну и один из моих любимых примеров — допустим, мы пишем сортировку, и по какой-то причине считаем, что одного теста, проверяющего порядок элементов достаточно:

input = arbitrary_list()
output = sort(input)
assert all(a <= b for a, b in zip(output, output[1:]))

И вот такая реализация его отлично пройдет

def sort(input):
	return [1, 2, 3]

Надеюсь, мораль тут ясна.

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

Теперь к вопросу о фреймворках, что от них ждать и зачем они вообще нужны — ведь никто не запрещает руками в цикле гонять тест, вызывая внутри рандом и радуясь жизни. На самом деле, радость будет до первого падения теста, и хорошо если локально, а не в каком-нибудь CI. Во-первых, поскольку тесты на основе свойств рандомизированы, то обязательно нужен способ надежно воспроизвести упавший кейс, и любой уважающий себя фреймворк позволяет это делать. Наиболее популярные подходы — выводить в консоль некий seed, который можно вручную подсунуть в test runner и надежно воспроизвести упавший кейс (удобно для отладки), либо создавать на диске кэш с «плохими» сидами, которые будут при запуске теста автоматически проверяться в первую очередь (помогает с повторяемостью в CI). Другой важный аспект — это минификация данных (shrinking в зарубежных источниках). Поскольку данные генерируются рандомно, то есть совершенно неиллюзорный шанс попасть на падающий тест-кейс с контейнером из 1000 элементов, который отлажить то еще «удовольствие». Поэтому хорошие фреймворки после того как нашли фейлящийся кейс применяют ряд эвристик, чтобы попытаться найти более компактный набор входных данных, которые тем не менее будут продолжать валить тест. Ну и наконец — часто половина функционала теста — это генератор входных данных, поэтому наличие встроенных генераторов и примитивов, позволяющих быстро собирать из простых генераторов более сложные также сильно помогают.

Также периодически встречается критика, что тестах на основе свойств слишком много логики. Однако обычно это сопровождается примерами в стиле

data = totally_arbitrary_data()
perform_actions(sut, data)
if is_category_a(data):
	assert property_a_holds(sut)
else if is is_category_b(data):
	assert property_b_holds(sut)

На самом деле это довольно часто встречающийся (у новичков) антипаттерн, не надо так делать! Гораздо лучше разбить такой тест на два разных, и либо пропускать неподходящие входные данные (во многих фреймворках для этого есть даже специальные средства) если шанс на них попасть маленький, либо использовать более специализированные генераторы, которые сразу будут выдавать только подходящие данные. В результате должно получиться что-то вроде

data = totally_arbitrary_data()
assume(is_category_a(data))
perform_actions(sut, data)
assert property_a_holds(sut)

и

data = data_from_category_b()
perform_actions(sut, data)
assert property_b_holds(sut)

Полезные свойства, и места их обитания

Окей, чем полезно тестирование на основе свойств вроде понятно, основные подводные камни разобраны… хотя нет, главное пока как раз непонятно — откуда брать эти самые свойства? Попробуем поискать.

Хотя бы не падай

Самый простой вариант — пихаем произвольные данные в тестируемую систему и проверяем, что она не падает. На самом деле это целое отдельное направление с модным названием фаззинг (fuzzing), для которого существуют специализированные инструменты (например AFL aka American Fuzzy Lop), но с некоторой натяжкой это можно считать частным случаем тестирования на основе свойств, и если вообще никаких идей в голову не лезет, то можно начать с него. Тем не менее, как правило в явном виде такие тесты редко имеют смысл, поскольку потенциальные падения обычно очень неплохо вылазят и при проверке других свойств. Основные причины, почему упоминаю это «свойство» — навести читателя на фаззеры и в частности AFL (англоязычных статей на эту тему полно), ну и для полноты картины.

Тестовый оракул

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

input = arbitrary_list()
assert quick_sort(input) == bubble_sort(input)

Однако этим применимость данного свойства не ограничивается. Например, очень часто оказывается, что функционал реализуемый системой которую мы хотим протестировать является надмножеством чего-то уже реализованного, часто даже в стандартной библиотеке языка. В частности, обычно бОльшую часть функционала какого-нибудь key-value хранилища (в памяти или на диске, на основе деревьев, хэш-таблиц или каких-то более экзотических структур данных типа merkle patricia tree) можно протестировать обычным стандартным словарем. Тестирование всяких CRUDов — туда же.

Еще интересный вариант применения, который использовал лично — иногда при реализации численной модели какой-то системы некоторые частные случаи можно посчитать аналитически, и сравнивать с ними результаты моделирования. При этом как правило если попытаться пихать на вход совсем произвольные данные, то даже при корректной реализации тесты все равно начнут падать в силу ограниченной точности (и соответственно применимости) численных решений, зато в процессе починки с помощью наложения ограничений на генерируемые входные данные эти самые ограничения становятся известны.

Требования и инварианты

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

Небольшой список примеров из самых разных областей, удобных для проверки свойств:

• поле класса должно иметь ранее присвоенное значение (геттеры-сеттеры)
• в хранилище должна быть возможность прочитать ранее записанный элемент
• добавление ранее несуществующего элемента в хранилище не затрагивает ранее добавленные элементы
• во многих словарях не могут храниться несколько разных элементов с одинаковым ключом
• высота сбалансированного дерева должна быть не больше , где — число записанных элементов
• результатом сортировки является список упорядоченных элементов
• результат кодирования в base64 должен содержать только символы из алфавита base64
• алгоритм построения маршрута должен возвращать последовательность допустимых перемещений, которая приведет из точки A в точку B
• для всех точек построенных изолиний должно выполняться
• алгоритм проверки электронной подписи должен возвращать True, если подпись настоящая и False в противном случае
• в результате ортонормирования все вектора в базисе должны иметь единичную длину и нулевые взаимные скалярные произведения
• операции переноса и вращения вектора не должны менять его длину

В принципе тут можно было бы сказать что все, статья закончена, используйте тестовые оракулы или ищите свойства в требованиях, но есть еще несколько интересных «частных случаев», которые хотелось бы отметить отдельно.

Индукция и тестирование состояния (stateful testing)

Иногда требуется потестировать нечто имеющее состояния. В этом случае самый простой способ:

• написать тест, проверяющий корректность начального состояния (например — что только что созданный контейнер пустой)
• написать генератор, который используя набор случайных операций приведет систему в некое произвольное состояние
• написать тесты на все операции используя в качестве начального состояния результат работы генератора

Очень похоже на математическую индукцию:

• доказать утверждение 1
• доказать утверждение N+1, считая что утверждение N верно

Другой метод (иногда дающий чуть больше информации о том где сломалось) — генерировать допустимую последовательность событий, применять ее к тестируемой системе и проверять свойства после каждого шага.

Туда-сюда-обратно

Если внезапно появилась необходимость протестировать пару функций для прямого и обратного преобразования каких-то данных, то считайте, что вам крупно повезло:

input = arbitrary_data()
assert decode(encode(input)) == input

Отлично подходит для тестирования:

• сериализации-десериализации
• шифрования-дешифрования
• кодирования-декодирвания
• преобразования базисной матрицы в кватернион и обратно
• прямое и обратное преобразование координат
• прямое и обратное преобразование Фурье

Частный, но интересный случай — инверсия:

input = arbitrary_data()
assert invert(invert(input)) == input

Яркий пример — обращение или транспонирование матрицы.

Идемпотентность

Некоторые операции не меняют результат при повторном применении. Типичные примеры:

• сортировка
• всякие нормировки векторов и базисов
• повторное добавение существующего элемента в множество или словарь
• повторная запись одинаковых данных в какое-то свойство объекта
• приведение данных к канонической форме (пробелы в JSON привести к единому стилю например)

Также идемпотентность можно использовать для тестирования сериализации-десериализации если обычный способ decode(encode(input)) == input не подходит из-за разных возможных представлений для эквивалентных входных данных (опять же — пробелы лишние в каком-нибудь JSONе):

def normalize(input):
	return decode(encode(input))

input = arbitrary_data()
assert normalize(normalize(input)) == normalize(input)

Разные пути, один результат

Здесь идея сводится к тому, чтобы эксплуатировать тот факт, что иногда есть несколько способов сделать одно и то же. Может показаться, что это частный случай тестового оракула, но на самом деле это не совсем так. Самый простой пример — использование коммутативности некоторых операций:

a = arbitrary_value()
b = arbitrary_value()
assert a + b == b + a

Может показаться тривиальным, но это отличный способ потестировать:

• сложение и умножение чисел в нестандартном представлении (bigint, rational, вот это все)
• «сложение» точек на эллиптических кривых в конечных полях (привет, криптография!)
• объединение множеств (которые внутри могут иметь совсем нетривиальные структуры данных)

Кроме того, этим же свойством обладает и добавление элементов в словарь:

A = dict()
A[key_a] = value_a
A[key_b] = value_b
B = dict()
B[key_b] = value_b
B[key_a] = value_a
assert A == B

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

• сложение и умножение всяких странных чисел, векторов, матриц, кватернионов ()
• линейные операторы, в частности всякие интегралы, дифференциалы, свертки, цифровые фильтры, преобразования Фурье и т.п ()
• операции над одинаковыми объектами в разных представлениях, например
  
  
  • , где и — это единичные кватернионы, а — операция преобразования кватерниона в эквивалентную базисную матрицу
  • , где и — это сигналы, — свертка, — умножение, а — преобразование Фурье
  
  

Пример чуть более «обыденной» задачи — потестировать какой-нибудь хитрый алгоритм слияния словарей можно как-то так:

a = arbitrary_list_of_kv_pairs()
b = arbitrary_list_of_kv_pairs()
result = as_dict(a)
result.merge(as_dict(b))
assert result == as_dict(a + b)

Вместо заключения

Вот в общем-то и все, что я хотел рассказать в этой статье. Надеюсь было интересно, и чуть больше людей начнут применять все это на практике. Чтобы еще немного облегчить задачу приведу список фреймворков разной степени годности для разных языков:

• Python: Hypothesis
• Rust: Proptest
• Scala: Scalacheck
• C++: Rapidcheck
• JavaScript: FastCheck
• Go: Gopter

И, конечно, отдельное спасибо людям когда-то написавшим замечательные статьи, благодаря которым пару лет назад я узнал про этот подход, перестал беспокоиться и начал писать тесты на основе свойств:

• alexwlchan.net/talks/hypothesis-intro
• fsharpforfunandprofit.com/posts/property-based-testing-2