Старая псина учит новые трюки: Code Kata с использованием QuickCheck18.10.2014 19:48

Когда я агитирую коллег-программистов создавать больше различных автотестов на их код, они часто жалуются, что это сложная и унылая работа. И в чём-то они правы. При использовании классических юнит-тестов, действительно, нередко приходится писать уйму кода, чтобы проверить каждый отдельный случай поведения. Да и к качеству тестирования порой возникают вопросы, особенно в сложных системах, когда тривиальные сценарии использования проходят на ура, но на каких-то более сложных сценариях, на которые никто не подумал писать тесты, возникают неприятные проблемы.Я уже давно слышал про способ тестирования, который используется в QuickCheck, но всё никак не хватало финального толчка, чтобы им заняться вплотную. Этим толчком стала эта презентация от Джона Хьюза, автора этой замечательной библиотеки.

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

Вот только с какого бока подойти к этому чуду простому быдлопрограммисту человеку, который пишет не на Haskell и не на Erlang, а на более мэйнстримовых языках? Вот я, к примеру, более комфортно чувствую себя при программировании на Java. Не беда! Гугл практически сразу подсказывает, что для JUnit есть соответствующий плагин под названием JUnit-QuickCheck.

Лучший вариант попробовать новый способ подход в программировании — написать что-то уже известное. Поэтому я взял классическую Prime Factors Kata от Роберта Мартина. Рекомендую по-быстрому ознакомиться с ней, прежде чем углубляться в мою статью, потому что иначе могут быть непонятны какие-то моменты.

Для начала создадим пустой проект. Чтобы не утомлять читателя простынёй XML-файлов, я буду использовать для этого Gradle. С ним всё описание проекта уместится в несколько строчек: apply plugin: 'java'

repositories { mavenCentral () }

dependencies { testCompile ( «junit: junit:4.11», «org.hamcrest: hamcrest-all:1.3», «org.junit.contrib: junit-theories:4.11», «com.pholser: junit-quickcheck-core:0.4-beta-1», «com.pholser: junit-quickcheck-generators:0.4-beta-1» ) } Каждая зависимость находится здесь не случайно. Зачем здесь нужен сам JUnit, объяснять не приходится, а про остальные зависимости скажу по паре слов.

Hamcrest мы будем использовать, чтобы писать красивые и легко читаемые assert-ы. JUnit-Theories также необходим, потому что наш плагин работает только с ним (потому что во встроенной в JUnit версии теорий до сих пор не исправлен один неприятный баг) Проекты junit-quickcheck-core и junit-quickcheck-generators содержат классы, которые мы будем использовать непосредственно для генерации тестовых значений. Следуя принципам TDD, начинаем с самой простой теории, что позволяет максимально быстро удостовериться, что цикл обратной связи функционирует.

import static org.hamcrest.CoreMatchers.is; import static org.hamcrest.MatcherAssert.assertThat; import com.pholser.junit.quickcheck.ForAll; import org.junit.contrib.theories.Theories; import org.junit.contrib.theories.Theory; import org.junit.runner.RunWith;

@RunWith (Theories.class) public class PrimeFactorsTest { @Theory public void allOk (@ForAll Integer number) { assertThat (true, is (true)); } } Этот простенький трюк может сэкономить Вам уйму времени. Я не раз видел, как люди, применяя TDD, тратят много времени на создание сложного теста, а когда его наконец запускают, обнаруживают, что он не может работать из-за какой-то совершенно посторонней проблемы (не скачались или не прописались зависимости, не установлен JDK, неправильно настроился проект, код неправильно написан и уйма других нелепых ошибок). Это всегда очень сильно расстраивает и сбивает с рабочего ритма. Особенно сложно справиться с этим новичкам, которые только ещё пробуют TDD на вкус.

Поэтому я и сам всегда начинаю с самого простого, тривиального, дебильного теста, и вам советую делать так же. Нужно лишь запустить его и проверить, что я вижу, когда он проходит, и вижу, когда он падает. Это значит, что моя система готова к бою работе, и ничто не будет отвлекать от цикла Red-Green-Refactor.

Чтобы не заморачиваться вопросом, как выявлять простые числа (это ведь должен делать мой код!), я просто забиваю уже известные числа в массив. Очевидно, из-за ограниченности нашего списка мы также вынуждены ограничивать диапазон чисел для тестирования. Исправим это позже, когда придёт время. Чтобы не отвлекаться от главного, я больше не буду писать в коде импорты, ограничусь лишь самим кодом. @Theory public void primeNumberIsItsOwnFactor (@ForAll @InRange (minInt = 1, maxInt = 50) Integer number) { List firstPrimeNumbers = Arrays.asList (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47); assumeThat (number, isIn (firstPrimeNumbers));

List factors = PrimeFactors.extract (number); assertThat (factors, hasItem (number)); } Мы используем аннотации @ForAll и @InRange из проекта JUnit-QuickCheck, чтобы автоматически генерировать случайные числа в указанном промежутке. Затем дополнительно фильтруем их с помощью функции assumeThat, чтобы последующий код работал только с числами, которые я указал в массиве. Различие между assumeThat от assertThat в том, что первая функция всего лишь останавливает тест (и переходит к следующему примеру), если очередное число не проходит проверку, а вторая будет сигнализировать об ошибке (и остановит выполнение теста для всех последующих примеров). Использовать assume в тестах идиоматичнее, чем фильтровать значения с помощью условных выражений.

Этот тест сначала будет падать (потому что у нас нет никакой реализации метода extract), но это несложно поправить. Решение, которое проходит все тесты, получается тривиальным.

public class PrimeFactors { public static List extract (Integer number) { return Arrays.asList (number); } } Не стоит удивляться или негодовать раньше времени. Этот код работает полностью в соответствии со спецификацией, раскладывая на простые множители любое простое число не больше 50. Чтобы научить код работать с другими числами, просто напишем новую теорию.

Какими свойствами обладает набор множителей числа? Очевидно, их произведение должно быть равно самому числу. @Theory public void productOfFactorsShouldBeEqualToNumber (@ForAll @InRange (minInt = 2, maxInt = 50) Integer number) { List factors = PrimeFactors.extract (number); Integer product = 1; for (Integer factor: factors) product = product * factor; assertThat (product, is (number)); } Эта теория… не падает! И ведь действительно, если наш код возвращает само число, то так и будет всегда. Чёрт.

Ладно, ещё одна теория, на этот раз более удачная.

@Theory public void everyFactorShouldBeSimple (@ForAll @InRange (minInt = 2, maxInt = 50) Integer number) { List factors = PrimeFactors.extract (number); assertThat (factors, everyItem (isIn (firstPrimeNumbers))); } Каждый множитель должен быть простым (ну, попадать в наш список простых), поэтому теория начинает падать стабильно и регулярно. А это именно то, что нам нужно. Пускай, к примеру, выпала такая ошибка:

org.junit.contrib.theories.internal.ParameterizedAssertionError: everyFactorShouldBeSimple (»10» ) at org.junit.contrib.theories.Theories$TheoryAnchor.reportParameterizedError (Theories.java:215) at org.junit.contrib.theories.Theories$TheoryAnchor$1$1.evaluate (Theories.java:169) at org.junit.contrib.theories.Theories$TheoryAnchor.runWithCompleteAssignment (Theories.java:153) at org.junit.contrib.theories.Theories$TheoryAnchor.runWithAssignment (Theories.java:142) … Напишем максимально простой код, который позволяет найти делители для этого числа:

public class PrimeFactors { public static List extract (Integer number) { if (number % 2 == 0) return Arrays.asList (2, number / 2); return Arrays.asList (number); } } Запускаем тесты снова. Они автоматически падают на новом найденном значении:

org.junit.contrib.theories.internal.ParameterizedAssertionError: everyFactorShouldBeSimple (»15» ) at org.junit.contrib.theories.Theories$TheoryAnchor.reportParameterizedError (Theories.java:215) at org.junit.contrib.theories.Theories$TheoryAnchor$1$1.evaluate (Theories.java:169) at org.junit.contrib.theories.Theories$TheoryAnchor.runWithCompleteAssignment (Theories.java:153) … Сделаем хак и для него!

public class PrimeFactors { public static List extract (Integer number) { if (number % 2 == 0) return Arrays.asList (2, number / 2); if (number % 3 == 0) return Arrays.asList (3, number / 3); return Arrays.asList (number); } } Запускаем тесты снова и снова, и каждый раз они находят новое значение, на котором реализация падает. При этом мы не можем просто возвращать какое-нибудь простое число, чтобы тест проходил. Если мы так сделаем, то начнёт ломаться предыдущая теория (которая проверяет произведение чисел). Поэтому мы вынуждены шаг за шагом реализовывать правильный алгоритм.

Постепенно (а на самом деле, довольно быстро) эта череда хаков приводит нас к первому корректному решению.

public class PrimeFactors { public static List extract (Integer number) { List factors = new ArrayList<>(); for (int divisor = 2; divisor <=7; divisor++) { while ((number > divisor) && (number % divisor == 0)) { factors.add (divisor); number = number / divisor; } } factors.add (number); return factors;

} } Разумеется, под словом «корректное решение» подразумевается лишь то, что оно стабильно проходит все тесты на данном этапе. Хотя, очевидно, и не годится для общего случая.

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

Пока что кажется, что всё очень круто. Мы написали всего пару теорий, и они в полу-автоматическом режиме выпестовали наш алгоритм. Разве это не красота? Однако посмотрим, что будет дальше.

Эйфория постепенно проходит, и глаз начинает обращать внимание на острые углы, которые мы старательно огибали на первых этапах. Наш код, конечно, работает по спецификации, но эта спецификация определена только для чисел от 2 до 50. Небогато! На этом интервале и без программы можно обойтись, просто посчитать всё в уме.Давайте двигаться дальше. Поднимем верхнюю границу в 10 раз во всех теориях!

@Theory public void primeNumberIsItsOwnFactor (@ForAll @InRange (minInt = 2, maxInt = 500) Integer number) { … } @Theory public void productOfFactorsShouldBeEqualToNumber (@ForAll @InRange (minInt = 2, maxInt = 500) Integer number) { … } @Theory public void everyFactorShouldBeSimple (@ForAll @InRange (minInt = 2, maxInt = 500) Integer number) { … } Внезапно возникает новая проблема: наши теории не в курсе, что существуют простые числа, больше 47 (упс, никто не знакомил её с Эвклидом). Надо придумывать новый способ определения простых чисел.

Немного сжульничаем (или всё тут честно?) и воспользуемся готовой реализацией проверки на простоту), которая есть в стандартной библиотеке Java. Чтобы не нарушать красоту и единообразие кода, сделаем её в виде соответствующего матчера.

@Theory public void primeNumberIsItsOwnFactor (@ForAll @InRange (minInt = 2, maxInt = 500) Integer number) { assumeThat (number, isProbablySimple ());

List factors = PrimeFactors.extract (number); assertThat (factors, hasItem (number)); }

@Theory public void productOfFactorsShouldBeEqualToNumber (@ForAll @InRange (minInt = 2, maxInt = 500) Integer number) { … }

@Theory public void everyFactorShouldBeSimple (@ForAll @InRange (minInt = 2, maxInt = 500) Integer number) { List factors = PrimeFactors.extract (number); assertThat (factors, everyItem (isProbablySimple ())); }

private Matcher isProbablySimple () { return new BaseMatcher() { @Override public boolean matches (Object item) { return (item instanceof Integer) && (BigInteger.valueOf ((Integer) item).isProbablePrime (5)); }

@Override public void describeTo (Description description) { description.appendText («prime number»); } }; } Теперь наш код падает на разложении больших чисел. Самое время исправить его!

public class PrimeFactors { public static List extract (Integer number) { List factors = new ArrayList<>(); for (int divisor = 2; divisor <= number; divisor++) { ... Исправляем старую границу цикла (7) на number, и, кажется, всё снова работает.

Осталась лишь малость: раздвинуть границы тестов ещё шире и наслаждаться результатом. И тут нас ждёт внезапный сюрприз…

Реальность выглядит так: @Theory public void primeNumberIsItsOwnFactor (@ForAll @InRange (minInt = 2, maxInt = Integer.MAX_VALUE) Integer number) { … } @Theory public void productOfFactorsShouldBeEqualToNumber (@ForAll @InRange (minInt = 2, maxInt = Integer.MAX_VALUE) Integer number) { … } @Theory public void everyFactorShouldBeSimple (@ForAll @InRange (minInt = 2, maxInt = Integer.MAX_VALUE) Integer number) { … } Стоило нам увеличить верхнюю границу тестов с 500 до Integer.MAX_VALUE (2^31 — 1), как тесты стали работать нереально долго. По минуте на каждый тест. В чём же дело? Что не так?

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

Что мы делаем, когда нам нужно найти затык в коде? Варианта два: либо берём в руки профайлер и начинаем снимать показания, либо ищем ошибку методом пристального разглядывания.

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

Накатим же фикс. Снова изменим верхнюю границу цикла, но на этот раз до Math.sqrt (number).

public class PrimeFactors { public static List extract (Integer number) { List factors = new ArrayList<>(); for (int divisor = 2; divisor <= Math.sqrt(number) + 1; divisor++) { ... Как это повлияло на результат работы? Тесты снова стали работать быстро, причём разница поистине впечатляет.

Вот теперь-то уже всё совсем хорошо! Все тесты проходят, код выглядит опрятно, получен интересный опыт — не пора ли написать статью на хабр? И тут мне в голову закрадывается ещё мысль…

Стоп, дружок, говорю я себе, а верно ли ты записал граничное условие цикла? Точно ли надо добавлять единицу к корню числа, или она лишняя? Вроде бы, плёвый вопрос. У нас же есть тесты, которые запускаются на сотне тестовых значений! Они и покажут, кто здесь неправ.

Отнимаем »+1» у верхней границы цикла (divisor <= Math.sqrt(number);) и запускаем тесты.

Отлично, они проходят!

Отнимаем ещё единицу, просто так, на всякий случай (divisor < Math.sqrt(number);).

Тесты снова проходят!

Чтооо?

И вот тут пришлось снова задуматься. Усугубим ситуацию ещё сильнее.

public class PrimeFactors { public static List extract (Integer number) { List factors = new ArrayList<>(); for (int divisor = 2; divisor < Math.sqrt(number) - 2; divisor++) { ... Я написал заведомо неправильный код (он не найдёт множителей даже у числа 9), но тесты говорят, что всё хорошо. Я запускаю их ещё раз — они снова говорят, что всё хорошо. Я запускаю их снова — раз за разом они успешно проходят. Падения происходят совсем редко, и контрпримеры к моему ошибочному алгоритму, которые тесты изредка находят, не сохраняются для следующих запусков.

В чём причина такого поведения тестов?

Увеличив границы тестов до Integer.MAX_VALUE, мы смогли найти и исправить проблемы с производительностью, но попали в новую ловушку. Фокус в том, что с такими настройками диапазона в тестах используются преимущественно большие числа (потому что для генерации используется равномерное распределение). А внедрённый в код дефект проявляет себя только на квадратах простых чисел (я надеюсь, не требует разъяснения), которых среди больших чисел очень мало.

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

@Theory public void everyFactorShouldBeSimple (@ForAll @InRange (minInt = 2, maxInt = Integer.MAX_VALUE) Integer number) { List factors = PrimeFactors.extract (number); assertThat (factors, everyItem (isProbablySimple ())); }

@Theory public void everyFactorShouldBeSimpleEspeciallyForSmallNumbers (@ForAll @InRange (minInt = 2, maxInt = 200) Integer number) { everyFactorShouldBeSimple (number); } Выглядит это коряво, но хотя бы позволяет найти точную верхнюю границу, до которой нужно гонять цикл (divisor <= Math.sqrt(number)).

Пора подвести итоги и собрать вместе все открытия, которые попались нам в этом (казалось бы) простом примере.

Даже один эксперимент в малознакомой области может принести немало открытий. Попробую собрать все особенности QuickCheck-подхода в один пучок и оценить их.Лаконичная спецификация Действительно, есть такое. Мне пришлось написать всего три теории, каждая из которых проверяла одну особенность алгоритма. Это заметно меньше, чем десяток обычных юнит-тестов, который возникает в классическом варианте каты. Запишем эту особенность в однозначный плюс данной техники.

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

В приведённом примере удалось воспользоваться методом isProbablePrime, который использует быстрый эвристический алгоритм для неточной проверки числа на простоту. Однако, если бы такого алгоритма не существовало, то какие у нас остались бы возможности проверки? Ведь, по определению, простое число — это такое число, у которых нет делителей. И, чтобы проверить простоту числа, нужно постараться разложить его на делители.

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

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

Я думаю, Вы уже догадались, что использовать QuickCheck для end-to-end тестирования может оказаться не самой лучшей идеей именно по этой причине. Хотя, если очень уж хочется, то можно и попробовать.

Нечувствительность к граничным условиям Возможно, это особенность конкретно библиотеки JUnit-QuickCheck, а в других языках с этим делом ситуация обстоит лучше. Или это особенность конкретного примера, который мы выбрали для пробы. Тем не менее, это показывает, что не стоит всегда легкомысленно полагаться на случайные значения, которые услужливо подбирает для нас библиотека. Всё равно приходится тяжко думать мозгом и перепроверять корректность написанного кода.

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

Не исключено, что при тестировании кода будет хорошо работать комбинация классических тестов-примеров и параметризованных теорий в стиле QuickCheck. Я обязательно постараюсь продолжить свои исследования в этой области и поделюсь интересными находками.

© Habrahabr.ru