When I agitate fellow programmers to create more different autotests for their code, they often complain that this is a difficult and dismal work. And in some ways they are right. When using classic unit tests, in fact, often have to write a lot of code to check each individual case of behavior. Yes, and the quality of testing sometimes raises questions, especially in complex systems, when trivial usage scenarios go bang, but in some more complex scenarios that no one thought of writing tests, unpleasant problems arise.

I heard about the testing method used in QuickCheck a long time ago, but I still didn’t have enough of the final push to get to the close. This impetus was this presentation from John Hughes, the author of this wonderful library.

What is the QuickCheck approach

It’s quite simple to describe the essence of the approach: we don’t create sample tests, but instead set up rules that define the behavior of the system on arbitrary input data. The library itself generates a large amount of random input data and checks whether the behavior of the code conforms to established rules. If this is not the case, then it shows us in what example the test falls.
')
It sounds promising? Full


But from what side should a simple bydlopprogrammer person approach this miracle who writes not in Haskell and not in Erlang, but in more mainstream languages? Here I, for example, feel more comfortable when programming in Java. No problem! Google almost immediately suggests that for JUnit there is a corresponding plugin called JUnit-QuickCheck .

The best option to try a new approach to programming is to write something already known. So I took the classic Prime Factors Kata from Robert Martin . I recommend to get acquainted with it quickly before going deep into my article, because some moments might not be clear.

Go

First, create an empty project. In order not to bore the reader with a sheet of XML files, I will use Gradle for this. With him all the description of the project will fit in several lines:

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" ) } 

Every dependency is not here by chance. Why JUnit is needed here, it is not necessary to explain, but I’ll say a couple of words about other dependencies.

• We will use Hamcrest to write beautiful and easy-to-read assertions.
• JUnit-Theories is also necessary, because our plugin only works with it (because in the embedded version of the theories in JUnit one unpleasant bug has not yet been fixed)
• The junit-quickcheck-core and junit-quickcheck-generators projects contain classes that we will use directly to generate test values.

Following the principles of TDD, we start with the simplest theory, which allows us to quickly verify that the feedback loop is functioning.

 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)); } } 

This simple trick can save you a lot of time. I have repeatedly seen how people, using TDD, spend a lot of time creating a complex test, and when it is finally launched, they discover that it cannot work due to some completely extraneous problem (dependencies did not download or do not register, do not JDK is installed, the project is incorrectly configured, the code is incorrectly written and a lot of other ridiculous errors). It is always very frustrating and confusing to the work rhythm. It is especially difficult to cope with this for beginners who are just trying to taste TDD.

Therefore, I myself always start with the simplest, trivial, moronic test, and I advise you to do the same. You just need to run it and check what I see when it passes, and see when it falls. This means that my system is ready for combat , and nothing will distract from the Red-Green-Refactor cycle.

First working theory

In order not to bother with the question of how to identify prime numbers (this is what my code should do!), I simply block already known numbers into an array . Obviously, due to the limitations of our list, we also have to limit the range of numbers to be tested. Correct this later when the time comes. In order not to be distracted from the main thing, I will no longer write in the import code, I will confine myself to the code itself.

 @Theory public void primeNumberIsItsOwnFactor(@ForAll @InRange(minInt = 1, maxInt = 50) Integer number) { List<Integer> firstPrimeNumbers = Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47); assumeThat(number, isIn(firstPrimeNumbers)); List<Integer> factors = PrimeFactors.extract(number); assertThat(factors, hasItem(number)); } 

We use the @ForAll and @InRange from the JUnit-QuickCheck project to automatically generate random numbers in the specified range. Then we additionally filter them using the assumeThat function, so that the following code works only with the numbers I specified in the array. The difference between assumeThat from assertThat is that the first function only stops the test (and proceeds to the next example) if the next number fails the test, and the second will signal an error (and stop the test for all subsequent examples). Using assume in tests is more idiomatic than filtering values ​​using conditional expressions.

This test will fall first (because we have no implementation of the extract method), but this is easy to fix. The solution that passes all the tests turns out to be trivial.

 public class PrimeFactors { public static List<Integer> extract(Integer number) { return Arrays.asList(number); } } 

Do not be surprised or indignant ahead of time. This code works completely in accordance with the specification , decomposing any prime number not more than 50 into simple factors. To teach the code to work with other numbers, just write a new theory.

Ramping meat on the skeleton

What properties does a set of factors of a number have? Obviously, their product should be equal to the number itself.

 @Theory public void productOfFactorsShouldBeEqualToNumber(@ForAll @InRange(minInt = 2, maxInt = 50) Integer number) { List<Integer> factors = PrimeFactors.extract(number); Integer product = 1; for (Integer factor: factors) product = product * factor; assertThat(product, is(number)); } 

This theory ... does not fall! And indeed, if our code returns the number itself, then it will always be. Heck.

Well, another theory, this time more successful.

 @Theory public void everyFactorShouldBeSimple(@ForAll @InRange(minInt = 2, maxInt = 50) Integer number) { List<Integer> factors = PrimeFactors.extract(number); assertThat(factors, everyItem(isIn(firstPrimeNumbers))); } 

Each factor should be simple (well, get on our list of simple), so the theory begins to fall steadily and regularly. And this is exactly what we need. Let, for example, the following error occurred:

 org.junit.contrib.theories.internal.ParameterizedAssertionError: everyFactorShouldBeSimple("10" <from 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) ... 

Let's write the most simple code that allows you to find dividers for this number:

 public class PrimeFactors { public static List<Integer> extract(Integer number) { if (number % 2 == 0) return Arrays.asList(2, number / 2); return Arrays.asList(number); } } 

Run the tests again. They automatically fall on the new found value:

 org.junit.contrib.theories.internal.ParameterizedAssertionError: everyFactorShouldBeSimple("15" <from 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) ... 

Let's make a hack for him too!

 public class PrimeFactors { public static List<Integer> 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); } } 

We run tests again and again, and each time they find a new value on which the implementation falls. At the same time, we cannot simply return any prime number for the test to pass. If we do this, the previous theory (which checks the product of numbers) will begin to break. Therefore, we are forced, step by step, to implement the correct algorithm.

Gradually (and in fact, rather quickly), this series of hacks leads us to the first correct solution .

 public class PrimeFactors { public static List<Integer> extract(Integer number) { List<Integer> 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; } } 

Of course, the word “correct solution” means only that it consistently passes all tests at this stage . Although, obviously, not suitable for the general case.

It is necessary to take a break and reflex a little. The theory, which itself selects a counterexample for the current code, turns out to be a very convenient thing. The process of working on the code turns into ping-pong with a robot, which deals quick, accurate and tricky strikes. No need to spend time thinking about new examples breaking the code, because they are born themselves. Instead, you can fully concentrate on the thoughts about the algorithm itself, and polish it in the flow mode. This is partly why there is such a big leap in commits. It’s just that the code was born too fast for intermediate steps to harden and form into full-fledged commits.

So far it seems that everything is very cool. We wrote just a couple of theories, and they semi-automatically fed out our algorithm. Isn't it a beauty? However, let's see what happens next.

It's time to grow out of short pants

The euphoria gradually passes, and the eye begins to pay attention to the sharp corners, which we diligently skirted in the first stages. Our code, of course, works according to the specification, but this specification is defined only for numbers from 2 to 50. It's not rich! At this interval, and without a program, you can do without, just count everything in your mind.

Let's move on. We raise the upper limit 10 times in all theories!

 @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) { ... } 

Suddenly , a new problem arises: our theories are not aware that there are simple numbers, more than 47 (oops, no one introduced her to Euclid ). We must come up with a new way to determine the prime numbers.

Let's cheat a little (or is everything honest here?) And use the ready-made implementation of the test for simplicity , which is in the standard Java library. In order not to violate the beauty and uniformity of the code, we will do it in the form of an appropriate matcher.

 @Theory public void primeNumberIsItsOwnFactor(@ForAll @InRange(minInt = 2, maxInt = 500) Integer number) { assumeThat(number, isProbablySimple()); List<Integer> 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<Integer> factors = PrimeFactors.extract(number); assertThat(factors, everyItem(isProbablySimple())); } private Matcher<Integer> isProbablySimple() { return new BaseMatcher<Integer>() { @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"); } }; } 

Now our code falls on the decomposition of large numbers. It's time to fix it!

 public class PrimeFactors { public static List<Integer> extract(Integer number) { List<Integer> factors = new ArrayList<>(); for (int divisor = 2; divisor <= number; divisor++) { ... 

We fix the old cycle boundary (7) on the number , and it seems that everything is working again.

Only a little remains: push the boundaries of the tests even wider and enjoy the result. And here we are in for a sudden surprise ...

Facing harsh reality

The reality is :

 @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) { ... } 

As soon as we increased the upper bound of the tests from 500 to Integer.MAX_VALUE (2 ^ 31 - 1), the tests began to work unrealistically for a long time. For a minute for each test. What's the matter? What's wrong?

An unexpected side-effect of QuickCheck-style tests is their sensitivity to the speed of the code under test . Although, if you think about it, this is quite logical: if our code is not optimized and works slowly, then a hundred calls to it will make this non-optimality a hundred times more visible. In the "classic" unit tests, this slowdown will not be so noticeable, but here it manifests itself in all its glory.

What do we do when we need to find a plug in the code? There are two options: either we take a profiler in our hands and begin to take readings, or we are looking for an error by means of close scrutiny .

However, in our code there is nothing special to look at, everything is already in sight. The problem is that we run idle for too long in a cycle, burning electricity in vain. Anyone familiar with the factorization algorithm remembers that it is enough for us to check factors that do not exceed the square root of a given number. And who does not remember, he can go to Uncle Bob .

Let's fix the same fix . Again we change the upper bound of the loop, but this time to Math.sqrt(number) .

 public class PrimeFactors { public static List<Integer> extract(Integer number) { List<Integer> factors = new ArrayList<>(); for (int divisor = 2; divisor <= Math.sqrt(number) + 1; divisor++) { ... 

How did this affect the result of the work? Tests began to work again quickly, and the difference is truly impressive.

Now everything is all right! All tests pass, the code looks neat, an interesting experience is gained - isn't it time to write an article for Habr? And then another thought creeps into my head ...

Test your tests

Stop, my friend, I tell myself, have you written down the boundary condition of the cycle correctly? Is it necessary to add one to the root of a number, or is it superfluous?

It seems to be a trifling question. We also have tests that run on hundreds of test values! They will show who is wrong here.

Subtract "+1" at the top of the loop ( divisor <= Math.sqrt(number); ) and run the tests.

Great, they pass!

We subtract one more, just like that, just in case ( divisor < Math.sqrt(number); ).

Tests pass again!

What?

And here I had to think again. We will aggravate the situation even more .

 public class PrimeFactors { public static List<Integer> extract(Integer number) { List<Integer> factors = new ArrayList<>(); for (int divisor = 2; divisor < Math.sqrt(number) - 2; divisor++) { ... 

I wrote a deliberately wrong code (it will not find multipliers even for the number 9), but the tests say that everything is fine . I run them again - again they say that everything is fine. I run them again - time after time they pass successfully. Falls occur very rarely, and counterexamples to my erroneous algorithm, which the tests occasionally find, are not saved for the next launches.

What is the reason for this behavior tests?

By Integer.MAX_VALUE test boundaries to Integer.MAX_VALUE , we were able to find and fix performance problems, but fell into a new trap. The trick is that with such range settings in tests, mostly large numbers are used (because a uniform distribution is used for generation). And the defect introduced into the code manifests itself only on the squares of prime numbers (I hope, does not require clarification), which are very few among large numbers.

Unfortunately, I was not able to come up with solutions that were more successful than cheating again and making a copy of the existing specification, but only again with narrow boundaries.

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

It looks clumsy, but at least allows you to find the exact upper limit to which you need to drive a cycle ( divisor <= Math.sqrt(number) ).

It's time to take stock and bring together all the discoveries that have come across to us in this (seemingly) simple example.

What we got in the end

Even one experiment in an unfamiliar area can bring a lot of discoveries. I will try to collect all the features of the QuickCheck-approach in one bundle and evaluate them.

Laconic specification

Indeed, there is such. I had to write only three theories, each of which tested one feature of the algorithm. This is noticeably less than a dozen regular unit tests, which occurs in the classic version of the kata. We write this feature in a unique plus of this technique.

The need to carefully formulate verifiable properties

In order for the theories to work well, it is necessary to invent qualitative properties for testing that are invariant with respect to the input parameters. Sometimes it can be really difficult. It may seem as if you need to fully implement the testing algorithm inside the test code.

In the above example, we managed to use the isProbablePrime method, which uses a fast heuristic algorithm to inaccurately check the number for simplicity. However, if such an algorithm did not exist, then what would be the possibility of verification? Indeed, by definition, a prime number is such a number that do not have divisors. And, to check the simplicity of the number, you need to try to decompose it into dividers .

Perhaps this is the most difficult moment in QuickCheck testing. I will need further research to understand how hard it is to create good invariants for use in theories.

Slow code sensitivity

On the one hand, this is good, because it can immediately indicate that our code is not optimal. On the other hand, if the code in principle cannot be greatly accelerated, then you will either have to accept the slow work of the tests, or reduce the number of random values ​​that are used as test parameters. And if we reduce the number of random values, then our confidence that the tests will find possible defects in the code also falls to an appropriate degree.

I think you already guessed that using QuickCheck for end-to-end testing might not be the best idea for this very reason. Although, if you really want, you can try .

Insensitivity to boundary conditions

Perhaps this is a feature of the specific library JUnit-QuickCheck, and in other languages ​​with this matter the situation is better. Or is it a feature of a specific example that we have chosen for the sample. Nevertheless, it shows that you should not always lightly rely on random values, which the library helpfully selects for us. Anyway, you have to think hard with your brain and re-check the correctness of the written code.

QuickCheck can also be used for TDD!

It seems to be quite real, although the sensations are different. Due to the fact that there are fewer theories (and each of them is testing more cases), it is easier to build a chain of test methods that will lead us to the working code. On the other hand, it can turn into troubles if it is necessary to take too big a step in order to force the code to pass the newly added theory. However, people encounter such problems in classic TDD (and either find ways to solve them, or begin to be afraid of TDD in principle).

It is possible that when testing code, a combination of classic test examples and parameterized theories in the QuickCheck style will work well. I will definitely try to continue my research in this area and share interesting findings.