Test Principles - Part II

a designer knows he has achieved perfection not when there is nothing left to add, but when there is nothing left to take away.

Antoine de Saint Exupéry

Part I of my blog series Test Principles suggested the usage of Design by Contract to reduce and detect bugs, introduced by test code.

In addition of detecting bugs, tests serve as documentation of how to use an API and what a user can expect in a specific scenario. But this documentation is almost useless if the effort required to understand the test code is comparable to reading the code implementing the API. If it is difficult to understand how a test works and what it is intended to do than it is less likely to find a logical bug.

Tests should be focused and easy to understand

To improve the readability of tests I make sure that they do have the following properties:

• all statements of my tests are defined at the same level of abstraction
• all code that is only technically required to setup a test scenario is hidden behind test helper methods or test builders to keep the test focused
• all tests are self contained by defining all test values inside the test not fields or constants
• all test values are obtained from test methods named in a way emphasizing the important properties of the returned values

These are the hard and fast rules, but of course test design like all software design has to do trade-offs. For example when to much redundancy is introduced.

Mixing statements of different levels of abstraction inside one block of code is a bad practice, even for test code. But sometimes developers consider test code to be less valuable than production code and tend to care not much about its quality. I value test code as much as production code because:

• continuous improvement of production code relies heavily on a huge test base. If not written properly and free of duplication, maintenance will become a nightmare.
• tests are the foundation of safe refactorings and economic changes of business contracts. If a contract gets violated or changed, it is the test detecting it first and providing the most valuable feedback.
• developers in need of looking up the contract or usage of an API under development can do that easily by using the tests as an index. If not structured properly or not documenting every scenario of importance, reading code is the last resort of exact documentation.

This list isn't even close to be complete, but should be motivation enough to care about the quality of tests. To make things clear I will start with an example. Let's consider the class Mail from Part I once again.

This time I write the test tagging a mail with a label, the mail is yet not tagged with, straight forward. This implementation is very common and can be improved in many ways:

The way I do setup a set of labels is very low level compared to tagging the mail with a label. But tagging the mail is the main purpose why we write the test, making its level of abstraction the level the whole test has to be formulated at. Let me improve the test:

I moved the code creating the set of labels to a test helper method and gave it a name reflecting what I expect.

In case you wonder why the test helper method is populated with all the Java assert statements, this is my approach to use Design by Contract for test helper methods as explained in Part I of my Test Principles series.

All the statements are now at a similar level of abstraction. The test code still lacks to be focused on what to test and does not express which properties of the test values are significant and which are not. Tests written this way are both, difficult to maintain and understand.

A focused test contains only:

• non technical statements
• test values significant to define the scenario
• statements using the API under test
• statements verifying the expectations

When I create the test value mail I do not care about the values for the sender, recipient, subject and message. To avoid burdening the reader with all the information he has not to care about, I move the creation of the mail out of the test.

Now the test itself is focused on the aspect of tagging the mail with a label, while lacking to be self contained. The test alone reveals nothing about the test value mail, which, if already tagged with LABEL_3, would make the test pass, even for an empty implementation of the method Mail.tag(String label).

This approach of organizing tests is very common but I would not suggest it. But it is a good start to discuss further improvements.

When I inspect a test, I prefer to have all the informations relevant for understanding the test introduced by the test itself, instead of looking up test values in fields of the test instance.

Let's inspect the last refactored test code again. To verify the test does something useful, we have to lookup the initialization of the test value mail. Jumping from one code block to another, collecting all the relevant information required to get a complete picture of the test, increases the complexity and reduces the readability of the test. To increase the readability, I add the statement constructing the test value mail back to the test method, narrowed to the input parameters significant to make the test plausible.

Now everything that is important to understand how I try to test the aspect of mail tagging gets defined by the test method itself. Browsing through the code is not necessary anymore, which in my opinion does increase the readability. But there is still one major improvement left: the references to the three label constants.

The definition of literal values in a test method or class has one major drawback: the criteria of how the values were chosen is not explicit, but has to be guess by inspecting their values.

Let's deal with the three label constants left in the test. LABEL_1, LABEL_2 and LABEL_3 are defined outside the test method. This forces the reader to browse away from the test which reduces the readability. Further, when inspecting their values the reader has to guess why they were chosen. They have:

• different values
• the same prefix label
• a numeric suffix
• the numbers are positive and greater 0
• the numbers are natural
• ...

The question arising is: which of those properties are of importance for the test and which are not? It would be easier to understand the test if the criterion of how the test values were chosen would be explicit. Here is another improvement:

I replaced the method createMail(Set<String>) with anyMailTaggedWith(Set<String>) emphasizing which property of the test value is of importance: an arbitrary mail tagged with a specific set of labels.

The specific set of labels used is the result of the factory method anyLabels() which does create an arbitrary non empty set of labels. Why is a non empty set of importance to me, you may ask? I prefer to test boundary values explicit in a separate test instead of relying to get one by chance. The last method introduced, anyLabelDifferentFrom(Set<String>), has to return any label not contained in the set of labels passed in. Now the test makes its choices of proper test values explicit.

For those of you interested in how to implement the test value factory methods used in the test, I added some example implementations below (which do not return randomly generated values).

Tests written the way I have explained let you jump right into any test. You do not have to remember test class constants or test instance fields to get an understanding of the test method you are about to inspect due to its self containment. Further the test is focused on the aspect it's intended to test, leaving technical details about setting up the test scenario to test helper methods. Those are named emphasizing the properties of importance to the test which does help to keep all the statements defining the test on the same level of abstraction, improving the readability of the test.

In an upcoming blog I will explain the rules I follow for naming test value factory methods, prefixing them with any, to improve the readability and why I use randomly generated values in preference to literal values.

TO BE CONTINUED ...

Test Principles - Part I

the fool who invents everything imaginable, motivated by pride and greed only while lacking humility, is a brother in mind with Icarus, doomed to annihilate human kind.

Harmlezz

One goal of writing tests is to detect bugs in production code. To reduce duplication of code and improve readability tests often delegate tasks, which are complex or formulated on a lower abstraction level than the test, to test helper methods. These helper methods have a good chance to be reused by other tests.

Structuring tests in such a way introduces new risks. Different tests may call the same helper method without satisfying the expected pre-condition, which is seldom checked explicitly. Or the helper method is buggy itself, not producing a correct result or state change as expected by the caller.

The question is, how to deal with this problem.

We won't write tests, testing our tests

I would like to explain my implementation approach using Design by Contract for test helper methods. It has the following positive effects:

• early detection of bugs in test code
• and hence less bugs in test code
• improved documentation of what must be provided before using a test helper method
• and what can be expected as a result

One aspect of Design by Contract is to check the pre-conditions of a method before executing its body. In addition a method does check its post-conditions before returning to the caller. Some of the conditions to check can be moved from the method code to unit tests. This shift can be attractive if:

• the readability of the method code would suffer from code, checking conditions
• the complexity of the code, checking conditions, is high
• the code, checking conditions, has a significant impact on the method performance

Post-conditions depending only on input parameters, a returned result or an object state, observable by querying its interface, are good candidates to be moved from the method code to unit tests.

Consider a class Mail capable of being tagged with many labels. The mail class exposes a method tag(String label) which adds a tag with given label to the mail.

One test scenario is to tag a mail with a label, the mail is not already tagged with:

At the first line the test creates a randomly generated mail already tagged with a set of randomly generated labels, returned by the method anyLabels(). The method anyLabels() guarantees that the returned set of labels is never empty. If the scenario for a mail not yet tagged with a label is of importance, a separate test enforcing this condition should be written instead of waiting that the method anyLabels() does return an empty set of labels by chance.

So, the first test helper method that has to guarantee a post-condition, to never return an empty set of labels, has shown up. The code below shows how i do start to implement it:

The aspects of importance to me are the following:

• define the variable, to be returned as result, as soon as possible
• omit the code necessary to provide the promised result
• define the post-conditions and return the yet incomplete result
• omit those post-conditions which would introduce a high complexity bearing the risk of being buggy itself or would obfuscate the code instead of improving its readability.
• use Java assert instead of JUnit Assert to distinguish test code bugs from bugs in the code under test

I always try to run the test using the incomplete helper method before implementing its functionality, just to verify that my post-condition is significant. I skip providing the code for the anyLabels() method required to pass the post-condition, because it does not add anything important to explain my approach.

There is one last thing i like to notice about defining post-conditions that may make a difference in finding test code bugs. Let's consider the test helper method anyLabelNotContainedIn(Set<String> labels) that guarantees to return a label different from any label contained in the set of labels given as input parameter.

The definition of the pre-condition is straight forward while checking the input parameter labels to not contain null is technically optional. It does not prevent the method from generating a proper label but could detect a flaw in the test code.

The important fact is the post-condition is defined in terms of the result variable and the given input parameter only. Whenever possible i suggest to prevent using values held by local variables, because they may have the expected values but their relationship to the returned result is observable only when inspecting the method code which may be buggy. This would compromise the purpose of the post-condition, checking that the result has the promised properties regardless of the way it was calculated.

You should benefit from this approach due to:

• a reduction of undetected bugs in your test code
• a better documentation what you can expect from test helper methods
• an early response when using a test helper method in a way it was not intended for
• improved readability of your tests because drilling down can be reduced to inspecting the first helper method and its pre- and post-conditions
• distinctness of the cause for failing tests due to the usage of Java asserts for test code and JUnit Asserts for code under test

Continue reading Part II of my blog series Test Principles, dealing with how to improve the readability of tests.

Project Euler: Mission 4

unawareness is a blessing for both, the curious and the ignoramus. or else the former would suffer from tedium while the later from the cruelty of truth.

Harmlezz

The Infection

Some days ago a friend of mine pointed me to the Project Euler site. It offers a lot of mathematical puzzles which can be solved either by mathematics or by writing a short computer program. And because I am not educated in mathematics well enough to solve the problems by pure mathematics the challenge for me is to find an elegant and efficient software solution.

When I started to solve my first problem I became immediately infected. The more familiar I got with the problem the more optimizations I did discover. And even so the web is yet full of information and discussions about published solutions (so far I resisted to read any solution up front because I fear to loss my interest in solving them) I still like to write about my way how I solved some of the problems and which kind of improvements I found.

Currently I do a lot of programming in Java and that's the reason why I will present my solutions in that language. Perhaps, if I find enough time to speed up learning Scala, I will present some of my solutions in Scala as well.

First Contact

The problem we start with is Problem No. 4:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

 

Find the largest palindrome made from the product of two 3-digit numbers.

We will focus on finding an algorithm that reduces the number of required picks of products when searching the largest palindrome. We also strive to use not too much memory or processor time, calculating a product on the fly when making the decision to pick it.

Starting Very Simple (alpha)

The simplest way (I can imagine) to find the largest palindrome is to calculate the product of each possible pair (x, y) of two 3-digit numbers. We start with the largest x number (the upper bound) and pair it with each y number, beginning with the largest , and decrementing it after each pick, till we reach the smallest y number (the lower bound) . Than we decrement the x value and start over with the largest y value as before . For each pair we calculate the product and check if it is larger than the currently stored palindrome. If that is the case and the product is a palindrome as well , we store the new palindrome.

Palindrome palindrome = Palindrome.createNullObject();
for (int x = upperBound(); x >= lowerBound(); x--) {
   for (int y = upperBound(); y >= lowerBound(); y--) {
      long product = 1L * x * y;
      if (palindrome.isLesser(product) && isPalindrome(product)) {
         palindrome.setTo(product);
      }
   }
}

The type Palindrome does hold the current palindrome, in case we have found one, or the value 0 to indicate that we have not found one. The methods upperBound() and lowerBound() return the largest and smallest possible number for a given n-digit (3-digit in our case).The Palindrome.isLesser() method compares the value stored against the input parameter product. To calculate if a product is a palindrome is the responsibility of the method isPalindrome(). Finally when we find a greater palindrome than the one we do currently hold, we store it using the method Palindrome.setTo().

This algorithm requires 810.000 picks to find the largest 3-digit palindrome. We can do better!

Ignore Permutations (beta)

Approximately half of the pairs picked are permutations of the same x and y numbers. This pairs do have the same product and therefore do not help in finding a larger palindrome. This improvement can be achieved by choosing the x number as starting value for y whenever decrementing x .

Palindrome palindrome = Palindrome.createNullObject();
for (int x = upperBound(); x >= lowerBound(); x--) {
   for (int y = x; y >= lowerBound(); y--) {
      long product = 1L * x * y;
      if (palindrome.isLesser(product) && isPalindrome(product)) {
         palindrome.setTo(product);
      }
   }
}

We have reduced the required picks to find the largest 3-digit palindrome from 810.000 to 405.450. We still can do better!

Palindromes And Lesser Products (gamma)

While iterating down the y-axis each product we calculate is lesser than any product of the same column calculated before. So when we find our first palindrome we know that every pick on the same column can't be larger than the palindrome just found. For the succeeding columns we can stop picking further pairs when the first product calculated is lesser than or equal to the palindrome .

Palindrome palindrome = Palindrome.createNullObject();
for (int x = upperBound(); x >= lowerBound(); x--) {
   for (int y = x; y >= lowerBound(); y--) {
      long product = 1L * x * y;
      if (palindrome.isGreaterEqual(product)) {
         break;
      } else if (isPalindrome(product)) {
         palindrome.setTo(product);
         break;
      }
   }
}

We have added the method Palindrome.isGreaterEqual() to compare if the current palindrome is greater or equal than the input parameter product.

This is another huge improvement, reducing the required picks for finding the largest 3-digit palindrome from 405.450 to 7018. But we can do even better!

Think Diagonal (omega)

We discovered that large products do help in reducing the number of required picks. By iterating down the y-axis we decrease the product in each step by x. And because we start the algorithm with the largest x we decrease the product very fast. This can be improved by changing the iteration order from horizontal to diagonal. We just choose the two largest x and y numbers and increment x while decrement y till x is equal to the largest possible number (the upper bound) or y is equal to the smallest possible number (the lower bound). Than we decrement y if it is equal to x , otherwise we decrement x . This way the product decreases much slower.

Palindrome palindrome = Palindrome.createNullObject();
int startX = upperBound();
int startY = upperBound();
while (insideBoundaries(startX, startY)) {
   for (int x = startX; int y = startY; insideBoundaries(x, y); x++, y--) {
      long product = 1L * x * y;
      if (palindrome.isGreaterEqual(product)) {
         if (isDiagonalStart(x, y)) return;
         else break;
      } else if (isPalindrome(product)) {
         palindrome = product;
         break;
      }
   }
   if (startX > startY) startX--;
   else startY--;
}

The method insideBoundaries() returns true if both input parameter are neither less than the lowerBound() nor greater than the upperBound(), otherwise false. The method isDiagonalStart() returns true if the input parameter x is equal to startX and the input parameter y is equal to startY, otherwise false.

This change in the iteration order reduces the required picks for finding the largest 3-digit palindrome further from 7018 to 2251. But inspecting the Java program we notice that it starts to become more complex and harder to understand.

Some Analysis

Finally we can get an idea of how good the four different algorithms would scale relative to the total number of unique products for a given n-digit.

Finding the largest palindrome in the maximal matrix for a given n-digit is not only a matter of the used algorithm but also where the largest palindrome is found. To make the measurement more realistic we may try to calculate the average number of picks for a given n-digit as follows:

We execute one algorithm 9 times, reducing the upper bound of the matrix (the largest x and y values) by the lower bound after each execution. In each of this matrices we search for the largest palindrome. The sum of picks required in each run we divide by the number of total runs (9 in our case). This average number of required picks we divide by the number of available unique products for the given n-digit as a hint of the relative number of picks required to find the largest palindrome in an arbitrary matrix (we did not recalculated the available number of unique products for each reduced matrix because we are only interested in the growth and not exact graph).

As we can see algorithm gamma gave us the best improvement without making the algorithm to complex to understand or maintain. Algorithm omega still does much better compared to gamma but not compared to the total number of unique products. The average picks, given a 4-digit matrix, is 28626 for algorithm gamma and 5769 for algorithm omega. But the complexity of the program has grown as well.

That's it for now. For my next blog I am working on solving Problem No. 275