Posts Tagged ‘test driven development’
Does it really work? The Transformation Priority Premise
Given a simple problem of sorting numbers in an array, how come that one TDD session leads to Bubble sort while the other produces QuickSort?
Robert C. Martin proposed the question in his talk titled The Transformation Priority Premise at the Norwegian Developers Conference in 2011, which was brought to my attention by DeVill. The topic is also discussed in a blogpost. In short, when more and more tests are created during a TDD session, the test code gets more and more specific, which forces the production code to get more and more generic. While the third step of TDD is refactoring (i.e. changing the code without changing its external behavior, which is verified by the tests written so far), the second, the pass step utilizes transformations, in other words: changing the code to make its behavior more generic. Uncle Bob has a small list of such transformations, from which he recommends choosing the highest one that can make the failing test pass and avoiding the items near the bottom of the list if possible. Doing so is believed to yield better code.
({} -> nil) no code at all -> code that employs nil
(nil -> constant)
(constant -> constant+) a simple constant to a more complex constant
(constant -> scalar) replacing a constant with a variable or an arg
(statement -> statements) adding more unconditional statements
(statement -> if) splitting the execution path
(scalar -> array)
(array -> container)
(statement -> recursion)
(if -> while)
(expression -> function) replacing an expression with a func or algorithm
(stateless -> assignment) replacing the value of a variable.
Using only those transformations during the pass step of TDD will really force you to take baby-steps! 
According to Uncle Bob, the difference between the QuickSort and Bubble sort TDD sessions basically originates from one single decision at an early stage of development. For example, assume the following stage of the TDD iteration, in Python:
class SorterTest(unittest.TestCase):
def test_sorting(self):
sorter = Sorter()
self.assertEquals([], sorter.sort([]))
self.assertEquals([ 1 ], sorter.sort([ 1 ]))
self.assertEquals([ 1, 2 ], sorter.sort([ 1, 2 ]))
self.assertEquals([ 1, 2 ], sorter.sort([ 2, 1 ]))
class Sorter(object):
def sort(self, elements):
return elements
At this point, the test using [2,1] is failing and we are to modify the production code to make it pass. One possibility is to swap the elements of the input array if they are in the wrong order:
class Sorter(object):
def sort(self, elements):
if len(elements) > 1:
if elements[0] > elements[1]:
elements[0], elements[1] = elements[1], elements[0]
return elements
Swapping the elements of the input array will change the outside world as well since in Python, lists are passed by reference. This is obviously the last element from the list: (stateless->assignment). I tried it, and it trivially lead to a bubble sort. Here’s the screencast:
What surprised me is how easily it turned into quicksort when instead of swapping elements, I satisfied the failing testcase by appending elements to a new array:
class Sorter(object):
def sort(self, elements):
if len(elements) < 2:
return list(elements)
sorted = []
if elements[0] < elements[1]:
sorted.append(elements[0])
sorted.append(elements[1])
else:
sorted.append(elements[1])
sorted.append(elements[0])
return sorted
There’s a screencast for that as well:
Doing these experiments made me think. Does the same trick work for other well known algorithms? Take searching in a sorted list for example. I could not imagine how those baby-steps could lead to binary search, the fastest algorithm I know for this problem. My first experiment ended up with an implementation of linear search, kinda like what I expected:
However, I realized I’d broken the rules of TDD. TDD says that you must implement the simplest code that can make the currently failing test pass, but what I did for one of the tests near the beginning was not the simplest solution. At this early stage, everything was fine:
class SearchTest(unittest.TestCase):
def test_when_value_is_found_in_sorted_list_then_its_key_is_returned(self):
search = Search()
self.assertEqual(0, search.search([ 1 ], 1))
self.assertEqual(0, search.search([ 1, 2 ], 1))
def test_when_value_is_not_in_sorted_list_then_exception_is_raised(self):
search = Search()
self.assertRaises(NotFound, search.search, [], 1)
class Search(object):
def search(self, sorted_array, value):
if len(sorted_array) > 0:
if sorted_array[0] == value:
return 0
raise NotFound
Then I added a new test, which was still okay:
self.assertEqual(1, search.search([ 1, 2 ], 2))
But then I added two more if statements to the production code:
class Search(object):
def search(self, sorted_array, value):
if len(sorted_array) > 0:
if sorted_array[0] == value:
return 0
if len(sorted_array) > 1:
if sorted_array[1] == value:
return 1
raise NotFound
This is not the simplest code that can make the test pass. There is at least one that is more simple:
class Search(object):
def search(self, sorted_array, value):
if len(sorted_array) > 0:
if sorted_array[0] == value:
return 0
if sorted_array[1] == value:
return 1
raise NotFound
And when the constant 0 is turned into a variable named lower and the 1 is replaced with the last index of the array named upper, then the algorithm magically starts to resemble a binary search! Though implementing binary search this way is not a brainlessly trivial exercise (see the update at the end of the post for a detailed explanation), the algorithm almost fell out from my hands as I added more and more tests.
If I was surprised when quicksort appeared on my screen, I don’t know what I was when a shitload of if statements turned into binary search right before my very eyes.
P.S: yes, in the binary search demo, middle would have been a better name for the variable than i.
Update: seems that this binary search screencast is not very self-explanatory. Let’s start from here:
class SearchTest(unittest.TestCase):
def test_when_value_is_found_in_sorted_list_then_its_key_is_returned(self):
search = Search()
self.assertEqual(0, search.search([ 1 ], 1))
self.assertEqual(0, search.search([ 1, 2 ], 1))
self.assertEqual(1, search.search([ 1, 2 ], 2))
def test_when_value_is_not_in_sorted_list_then_exception_is_raised(self):
search = Search()
self.assertRaises(NotFound, search.search, [], 1)
class Search(object):
def search(self, sorted_array, value):
if len(sorted_array) > 0:
if sorted_array[0] == value:
return 0
if sorted_array[1] == value:
return 1
raise NotFound
At this point, all the tests pass. I cannot seem to find a useful refactoring here, however, I don’t like those two if statements. I add a test that allows me to make one of them more generic:
self.assertEqual(2, search.search([ 1, 2, 3 ], 3))
This could be solved by inserting one more if statement, but there are transformations higher on the priority list that can also make the test pass: replacing the constant 1 with the last index in the array:
class Search(object):
def search(self, sorted_array, value):
if len(sorted_array) > 0:
if sorted_array[0] == value:
return 0
if sorted_array[len(sorted_array) - 1] == value:
return len(sorted_array) - 1
raise NotFound
Now let’s refactor: len(sorted_array) appears three times in the code. By changing the greater-than comparison to an equivalent greater-than-or-equal comparison in the condition, all three occurrences can be refactored to the exact same format. To get rid of this redundancy, this expression can be given a name by introducing a variable, however, the value of that variable never changes during an individual execution of the search() method, so what we have done so far can be viewed as a constant->constant+ transformation. Certainly higher on the list than statement->if.
class Search(object):
def search(self, sorted_array, value):
upper = len(sorted_array) - 1
if upper >= 0:
if sorted_array[0] == value:
return 0
if sorted_array[upper] == value:
return upper
raise NotFound
Still wearing the Refactoring hat, we can introduce a name for the other constant as well: it’s the lower boundary of the array.
class Search(object):
def search(self, sorted_array, value):
lower, upper = 0, len(sorted_array) - 1
if upper >= lower:
if sorted_array[lower] == value:
return lower
if sorted_array[upper] == value:
return upper
raise NotFound
Notice that at this point, we have the terminating condition for the loop of a binary search algorithm.
The similarity between the two inner if statements still bugs me, but I don’t know how to eliminate at least one of them, so I keep going by adding a new test:
self.assertEqual(1, search.search([ 1, 2, 3 ], 2))
This introduces the concept of an element in the middle of the array. Sadly enough, the highest item on the list I can come up with is another damn if statement:
class Search(object):
def search(self, sorted_array, value):
lower, upper = 0, len(sorted_array) - 1
if upper >= lower:
if sorted_array[lower] == value:
return lower
if sorted_array[1] == value:
return 1
if sorted_array[upper] == value:
return upper
raise NotFound
Carefully inserted into the middle. There it does not seem to hurt much, and at the same time, it’s still easy to enforce moving it from there by introducing a test that expects a NotFound exception to be raised when searching in an array of length 1. However, this does not solve the bigger problem with this new if statement. The last test was intended to make the code look at the middle element in the array but what this statement does is looking at the second element, no matter what. In other words, it’s not quite generic enough. I could pretend not to realize this and add a new test that expects the middle element to be found in a 5 long array, but TDD allows you to take bigger steps when you feel confident, so I replaced the constant 1 with the real index of the middle element which happens to be (lower+upper)/2:
class Search(object):
def search(self, sorted_array, value):
lower, upper = 0, len(sorted_array) - 1
if upper >= lower:
if sorted_array[lower] == value:
return lower
if sorted_array[(lower + upper) / 2] == value:
return (lower + upper) / 2
if sorted_array[upper] == value:
return upper
raise NotFound
However, since nor upper nor lower are changed in this function, this expression is still a fancy way of saying 1, at least in the case of the last test written sor far. Also, changing that explicit 1 to this more flexible formula allows the if statement in question to be moved higher inside the outer conditional, simply because it will never attempt to acces an array index out of bounds.
Next thing I did in the screencast was to give this expression a name, though, not the best name as I mentioned earlier. Here I’m using the better name, middle instead of the i used in the screencast.
class Search(object):
def search(self, sorted_array, value):
lower, upper = 0, len(sorted_array) - 1
if upper >= lower:
middle = (lower + upper) / 2
if sorted_array[middle] == value:
return middle
if sorted_array[lower] == value:
return lower
if sorted_array[upper] == value:
return upper
raise NotFound
The next testcase was a tricky one:
self.assertEqual(2, search.search([ 1, 2, 3, 4 ], 3))
None of the inner if statements finds that 3 right now, however, after the first one fails to find it, we can force the second one to do it anyways. When the element in the middle is too small, we can simply set lower to 2, which will trigger the second if statement and bang, our test is green again! Of course we could write lower=2 but we know that this code wouldn’t live for a long time, so let’s use middle+1 instead, which seems to be more future-proof. Remember what TDD says about being confident. Also note that at this point, all our variables and expressions are just fancy ways of saying 0 or len(sorted_array), but for a given input, all of them behave like constants. It does not really matter at this point if you say 2, 1 + 1 or middle+1.
class Search(object):
def search(self, sorted_array, value):
lower, upper = 0, len(sorted_array) - 1
if upper >= lower:
middle = (lower + upper) / 2
if sorted_array[middle] == value:
return middle
if sorted_array[middle] < value:
lower = middle + 1
if sorted_array[lower] == value:
return lower
if sorted_array[upper] == value:
return upper
raise NotFound
The same idea leads to the fifth inner if statement after a new test:
class Search(object):
def search(self, sorted_array, value):
lower, upper = 0, len(sorted_array) - 1
if upper >= lower:
middle = (lower + upper) / 2
if sorted_array[middle] == value:
return middle
if sorted_array[middle] < value:
lower = middle + 1
if sorted_array[middle] > value:
upper = middle - 1
if sorted_array[lower] == value:
return lower
if sorted_array[upper] == value:
return upper
raise NotFound
Note that everything we did so far was either renaming some constants and parameters or choosing one element from the list of transformations!
But what to do now? First, let’s understand the code we did so far. This bunch of if statements can be divided into two parts. The first three inner if statements check one element near the middle of the array. This part of the code immediately returns the index when it finds the value it was looking for or changes either the lower or the upper boundary. What it means is that the array gets split into two parts: one that surely does not contain the value and the other that may do. This is true since the array is sorted. Then the second part, the last two inner if statements check the first and the last element of that latter subarray. What if we copy&paste-ed all those conditionals? There would be ten of them and they would either find the value or split the array again. Everytime we executed those five conditionals one after the other, the subarray that might contain the value we are looking for would become smaller and smaller, thus lower and upper would get closer and closer to each other. Actually, for iteratively splitting the array, repeating the first three if statements are just enough. Thinking through this finally makes it possible to eliminate the last two conditionals and safely change the outer if to while. Oh, how long I was waiting for being able to delete those if statements!
And voila, there is the binary search algorithm:
class Search(object):
def search(self, sorted_array, value):
lower, upper = 0, len(sorted_array) - 1
while upper >= lower:
middle = (lower + upper) / 2
if sorted_array[middle] == value:
return middle
if sorted_array[middle] < value:
lower = middle + 1
if sorted_array[middle] > value:
upper = middle - 1
raise NotFound
Game of life – never getting boring
Do you think it’s funny to implement Conway’s Game of Life for the 20th time? According to my experiences, the answer is hell yeah!
Since the Global Day of CodeRetreat event (organized by Marton Meszaros in Hungary), I’m a big fan of the CodeRetreat format of coding dojos. I’ve been attending all the events of the CodeRetreat Budapest Community, and at the last one, I even helped coaching during some of the sessions. Nucc and me decided to introduce this event to our fellow developers at BalaBit as well and fortunately the management was kind enough to support us by dedicating some working hours to learn about TDD and other modern software development methodologies.
At a CodeRetreat event, you always implement the four rules of Game of Life (without UI and such fancy stuff). Doing the same task again and again makes the problem well-known and understood so you can focus on the style and design of your tests and code, which is the goal of a CodeRetreat. You don’t have to finish the implementation, though, it’s not about Getting Things Done or competing which pair is the first to finish. More like Not Getting Things Done. Often it’s impossible as well to finish for you have only 45 minutes to work. After that, well, code is deleted, a short retrospective meeting is held then a new session begins. Pair programming is mandatory, and by changing the pairs after every session you’re guaranteed to learn a lot from others. To make sure that you won’t be able to train yourself during the day to finish new constraints are introduced in every session, like infinite grid, immutability of states, 3 line methods with at most 2 parameters, no-mouse (did you notice you go faster when you use only keyboard shortcuts in your IDE?), etc..
During the first few sessions, there are no constraints. The goal is getting the problem understood. In the implementation, you just do whatever you want. That seems to be the hardest constraint though, since people tend to not finish during the first sessions. Instead they do Big Design Up Front and forget to care about the software to be implemented. These are the sessions where nice UML diagrams about Cells and Neighborhood relations and Worlds and Games and Rules and such nicely designed stuff are drawn, then people realize after 45 minutes that they spent almost an hour working on getters and setters but not a single rule of the game got implemented. Yep, there’s a reason for the Four Rules of Simple Design having been invented. 
Turns out if you’d started the very first testcase with the first rule (“Any live cell with fewer than two live neighbours dies, as if caused by under-population”), you might have had a working implementation of all four of them after 15-20 minutes or so. And nothing more than that since you wouldn’t have written code that is never used except for making those UMLs feel more complete. YAGNI!
Of course there’s a chance that such a quick and dirty implementation will be, well, dirty. It may contain at least one thing you consider ugly. But you have more than half of the session left and the safety net of a bunch of tests to refactor the hell out of it!
You spoiled the public interface of your Game with methods that should belong to a class named Board or World or Map instead? Are you feeling the need to test a method that is declared private? After extracting such methods into a separate class, you might end up with a Game class that has no state at all and contains only one public method that just creates new generations of cells based on a previous one.
On the other hand, after realizing how over-engineering slows them down, many people try to continue with sloppy design, skipping the refactorings for example to get rid of language primitives in the most abstract levels of the business logic or to conform to the SOLID principles, etc. They can be forced to do so by introducing requirement change surprises. For example, to handle hexagon maps along with square grids, a Topology or similar interface has to be extracted from the class representing the board, which can encapsulate the details of coordinate systems and neighborhood relations between coordinates. (Did you notice that the rules of the game do not depend on the placement and shape of the neighbors nor the neighbors themselves, but only their count is what matters?) To handle colored cells which know how old they are, cells have to be represented by a separate class instead of bare coordinate-tuples or boolean flags.
Such refactorings can be a pain in the ass when tests contain copy&paste, duplication, redundancy and duplication, so they must be cleaned up as well: by extracting common fixtures, creating abstract assertions based on the repeating patterns of similar assertions, etc. (Abstract assertions even help you to conform to such rigorous principles like “1 assertion per test.”)
Imagine your day to day software development work boiling down to such simple business requirements implemented by a couple of short but well named methods in a few simple and minimalistic classes, all of them thoroughly unit tested (by unit testing I mean unit testing), all of those tests proven to be useful (since you’ve seen them fail and turning into green a couple of seconds later) and providing 100% coverage of assertions. Wouldn’t it be easier than digging yourself through stack traces in mindblowingly complex codes full of nested infinite-but-conditionally-breaking-somewhere-in-the-middle-do-while loops depending on side effects of getter functions and badly named global variables coming from a dozen layers away? If you know this feeling I’m talking about, I’d recommend you to visit the next CodeRetreat near your location (look around in Twitter or Facebook) – to try something new!
Test-driving a regular expression
“When you have a problem to solve, use regular expressions! Now you have two problems!”
Regular expressions are very useful tools in the inventory of a programmer: they can be used to validate a string according to a given format, or to find and extract parts of a string, or even to change substrings matching a given pattern. But when you write some hellish tricky regular expression, do you stop for a moment to think about the spaghetty of while loops and switch-case statements that your regexp will translate to? I mean just a few characters of regexp may specify a state machine that would take tens or maybe hundreds of lines of loops and conditionals to implement. All that amount of code gets executed whenever you use your regexp, so you would need a big amount of testcases to cover that state machine if you happen to practise Test-driven development (TDD). In this experiment I’m going to blindly apply the three well-known steps of TDD to create a regular expression for a given task, and see how far I can get and how much time it takes.
These three steps of the TDD cycle are:
- Write a failing unit test (compilation errors are considered a failure).
- Write just enough production code and not a single line more to pass the failing test.
- Cleanup the mess created during the first two steps.
Or in short:
- Red
- Green
- Refactor
My kata
My kata for this experiment will be validating a simple time specification, that contains two digits of hour and minute parts separated by a colon and either AM or PM in case of 12 hour notation. The rules are going to be:
- Valid time specifications should always contain a two digit number (with a leading zero if necessary) describing the hour of the day followed by a colon followed by a two digit number (with a leading zero as well) to describe the minute of the hour.
- The HH:MM part may be followed by a single space followed by two alphabetic characters, either AM or PM. In this case the time specification is considered to be in 12 hour format, thus the hour part should not be more than 12.
- When there is no AM or PM at the end of the string, the time specification is considered to be 24 hour format, in which case the hour part should be between 00-23 (inclusive).
- In any case, the minute part must be between 00-59 (inclusive).
The job is to decide if a string matches all the above rules or not.
There are a million possible implementations, but for now, let’s evolve this one by applying the TDD development cycle to meet the requirements. The language is going to be PHP, the testing framework will be PHPUnit, and the implementation will rely on PHP’s preg_match() function. First, let’s start from very small, trivial steps. Going forward, we may speed things up, just like in Kent Beck’s wonderful book.
The first testcase
In TDD, tests come first, so let’s create a simple testcase:
<?php
require_once 'TimeValidator.php';
class TimeValidatorTest extends PHPUnit_Framework_TestCase
{
public function testTimeValidatorCanBeCreated()
{
new TimeValidator();
}
}
?>This will fail badly, obviously, but let’s run it, just to be sure!
PHPUnit 3.5.15 by Sebastian Bergmann.
PHP Fatal error: Class 'TimeValidator' not found in /home/athos/projects/TimeValidator/TimeValidatorTest.php on line 7
PHP Stack trace:
PHP 1. {main}() /usr/bin/phpunit:0
PHP 2. PHPUnit_TextUI_Command::main() /usr/bin/phpunit:49
PHP 3. PHPUnit_TextUI_Command->run() /usr/share/php/PHPUnit/TextUI/Command.php:129
PHP 4. PHPUnit_TextUI_TestRunner->doRun() /usr/share/php/PHPUnit/TextUI/Command.php:188
PHP 5. PHPUnit_Framework_TestSuite->run() /usr/share/php/PHPUnit/TextUI/TestRunner.php:305
PHP 6. PHPUnit_Framework_TestSuite->runTest() /usr/share/php/PHPUnit/Framework/TestSuite.php:733
PHP 7. PHPUnit_Framework_TestCase->run() /usr/share/php/PHPUnit/Framework/TestSuite.php:757
PHP 8. PHPUnit_Framework_TestResult->run() /usr/share/php/PHPUnit/Framework/TestCase.php:576
PHP 9. PHPUnit_Framework_TestCase->runBare() /usr/share/php/PHPUnit/Framework/TestResult.php:666
PHP 10. PHPUnit_Framework_TestCase->runTest() /usr/share/php/PHPUnit/Framework/TestCase.php:628
PHP 11. ReflectionMethod->invokeArgs() /usr/share/php/PHPUnit/Framework/TestCase.php:738
PHP 12. TimeValidatorTest->testTimeValidatorCanBeCreated() /home/athos/projects/TimeValidator/TimeValidatorTest.php:0Yeah, we are in Red! Now we can write a tiny bit of production code in the hope we will get into the Green phase:
<?php
class TimeValidator
{
}
?>And now the test passes, we’re in Green.
Is there anything to refactor here? We have 0 ELoC, so let’s move on. I’m going to ignore Tell, don’t ask! for this kata, so I’m going to call the one and only public method of my TimeValidator class isValid(). Maybe later I’ll come up with a cleaner name for both the class and the method, but it will do for now. But before we could write any more lines of production code, we need a failing testcase first. So let’s do some actual work in the testcase:
public function testTimeValidatorCanBeCreated()
{
$validator = new TimeValidator();
$this->assertTrue($validator->isValid('10:42'));
}There’s no such method, so this will fail. Let’s implement the method with an empty body in TimeValidator.php:
public function isValid($time_specification)
{
}Again, the test fails because NULL does not equal to true. We’re still in Red, so we can write some more production code, because the lines we have written so far are not enough to get us into Green. What is the simplest algorithm that will make our failing testcase pass if implemented in the production code? Yes, it’s a big facepalm:
public function isValid($time_specification)
{
return true;
}And now we’re in Green. Let’s do some refactoring!
The name of our testcase lies: it says it checks the construction of our newly defined class, but actually the return value of a function is being checked. So let’s rename the testcase as a refactoring:
public function test24HourFormatIsAccepted()
{
$validator = new TimeValidator();
$this->assertTrue($validator->isValid('10:42'));
}I decided to consider 10:42 to be in 24 hour format, because that is the simplier one.
Is there any more opportunity to refactor? Though our validator is very useless at the moment, we don’t have any tests to enforce us to implement some real functionality in that method, so we’re not allowed to change that code to something more complex. We were required to write just enough production code to pass the failing test, and we’ve done exactly that and not a single line more.
Now what about creating a failing testcase to let us move forward?
A negative test
After a few seconds of thinking, I decided to test if our method does care about colons. Any kinds of time specifications mentioned in the requirements must contain a colon character, so it gives us a fairly simple testcase:
public function testTimeSpecificationMustContainOneColon()
{
$validator = new TimeValidator();
$this->assertFalse($validator->isValid('1042'));
}Sadly Hooray, a failure! We’re back in Red, let’s write some more production code! Sadly a fairly simple change to our isValid() can make this test pass:
public function isValid($time_specification)
{
return $time_specification != '1042';
}Back in Green, but far from any meaningful code. At least we can refactor, luckily we have some code duplications:
- There’s a repeating pattern in our tests: instantiation of the class under test (CUT).
- The string constant ’1042′ appears in both the test and the code!
In the Refactoring phase, we’re allowed to remove code duplication while keeping the tests pass and the functionality of the code unchanged. Let’s deal with the first problem, PHPUnit offers the setUp() method for that:
class TimeValidatorTest extends PHPUnit_Framework_TestCase
{
public function setUp()
{
$this->validator = new TimeValidator();
}
public function test24HourFormatIsAccepted()
{
$this->assertTrue($this->validator->isValid('10:42'));
}
public function testTimeSpecificationMustContainOneColon()
{
$this->assertFalse($this->validator->isValid('1042'));
}
private $validator;
}That was piece of cake, now let’s clean the production code! The simplest PHP line that came to my mind to make both testcases pass without the dirty hack of repeating constants in the production code used by the tests to check the behavior of the code, was an strpos() call. But knowing that in the end I want to see a regular expression doing the work, I used an equivalent regexp matching instead:
class TimeValidator
{
public function isValid($time_specification)
{
return preg_match('/:/', $time_specification) == 1;
}
}The tests still pass, so it’s time to look for more difficult cases. (And speed things up a little bit.)
Only one colon
The next test that came to my mind was to see if the regexp can deal with two colons:
public function testTimeSpecificationMustContainOneColon()
{
$this->assertFalse($this->validator->isValid('1042'));
$this->assertFalse($this->validator->isValid('10::42'));
}Red phase again, but it’s not very difficult to get into Green:
public function isValid($time_specification)
{
return preg_match('/^[^:]*:[^:]*$/', $time_specification) == 1;
}Now we look for exactly one colon from the beginning of the string to the very end. And we’re in Green! Anything to refactor here? Yes, duplicated non-trivial code appears in the regular expression! Let’s get rid of it:
public function isValid($time_specification)
{
$not_colon = '[^:]*';
return preg_match(
"/^$not_colon:$not_colon\$/",
$time_specification
) == 1;
}The tests still pass. Now there is still repeated code in the regular expression and to make things worse, it got longer, but this will move us forward, so knowing what to come, it’s a good idea to extract that little piece. Besides, the variable explains pretty well what the expression does. Anything else to refactor? Maybe a dataProvider would help eliminating the two almost identical lines from the tests, but I’m lazy now. I promise the next time I’m gonna write a similar assertion, I’ll do clean up the tests.
Hours must be numeric
The next simpliest test that came to my mind was:
public function testHoursMustBeNumeric()
{
$this->assertFalse($this->validator->isValid('ab:42'));
}Now we’re in Red, but it seems the next Refactoring phase will be a nice opportunity to get back to that promise.
How to fix that? I know I want to validate hours, so I’m going to create a new variable to be substituted into the regular expression:
public function isValid($time_specification)
{
$hours = '[0-9]*';
$not_colon = '[^:]*';
return preg_match(
"/^$hours:$not_colon\$/",
$time_specification
) == 1;
}The new variable is called hours and it matches any sequence of numbers. Yeah, Green again! That was just a matter of seconds. So anything to refactor here? Yes, remember what I promised a few minutes ago:
/**
* @dataProvider provideInvalidTimeSpecifications
*/
public function testInvalidTimeSpecificationsAreNotAccepted($time_specification)
{
$this->assertFalse($this->validator->isValid($time_specification));
}
public function provideInvalidTimeSpecifications()
{
return array(
'Time specification must contain at least one colon' => array('1042'),
'Time specification must contain at most one colon' => array('10::42'),
'Hours must be numeric' => array('ab:42'),
);
}Hours must be less than 24
Regardless of 12 hour time format, the hours part must be less than 24. This assertion is simple enough to create a new testcase from it:
public function provideInvalidTimeSpecifications()
{
return array(
'Time specification must contain at least one colon' => array('1042'),
'Time specification must contain at most one colon' => array('10::42'),
'Hours must be numeric' => array('ab:42'),
'Hours must be less than 24' => array('24:42'),
);
}And the code that passes all the tests so far is not a big deal either:
public function isValid($time_specification)
{
$hours = '([0-1]?[0-9]|2[0-3])';
$not_colon = '[^:]*';
return preg_match(
"/^$hours:$not_colon\$/",
$time_specification
) == 1;
}Anything to refactor? Nope I guess.
Minutes must be numeric
One more simple testcase, just to see how well minutes are validated:
public function provideInvalidTimeSpecifications()
{
return array(
'Time specification must contain at least one colon' => array('1042'),
'Time specification must contain at most one colon' => array('10::42'),
'Hours must be numeric' => array('ab:42'),
'Hours must be less than 24' => array('24:42'),
'Minutes must be numeric' => array('10:ab'),
);
}Getting from Red to Green is children’s play as well, I did the same as in the case of the hours. Minutes are validated to be numeric, then a new testcase to make sure they are less than 60:
public function provideInvalidTimeSpecifications()
{
return array(
'Time specification must contain at least one colon' => array('1042'),
'Time specification must contain at most one colon' => array('10::42'),
'Hours must be numeric' => array('ab:42'),
'Hours must be less than 24' => array('24:42'),
'Minutes must be numeric' => array('10:ab'),
'Minutes must be less than 60' => array('10:60'),
);
}And the code:
public function isValid($time_specification)
{
$hours = '([0-1]?[0-9]|2[0-3])';
$minutes = '([0-5]?[0-9])';
return preg_match(
"/^$hours:$minutes\$/",
$time_specification
) == 1;
}Anything to refactor? Not a single bit! Notice how nicely that ugly $not_colon variable disappeard? The regular expression is quite self-explanatory, it doesn’t even need a comment to be understandable.
Two digits
Both hours and minutes should be expected to be two digits:
public function provideInvalidTimeSpecifications()
{
return array(
'Time specification must contain at least one colon' => array('1042'),
'Time specification must contain at most one colon' => array('10::42'),
'Hours must be numeric' => array('ab:42'),
'Hours must be less than 24' => array('24:42'),
'Minutes must be numeric' => array('10:ab'),
'Minutes must be less than 60' => array('10:60'),
'Hours must be two-digit' => array('1:42'),
'Minutes must be two-digit' => array('10:4'),
);
}Okay, those are two tests at the same time, but TDD allows you to go in your own tempo as long as you can clearly see the small, trivial steps you join together to take a bigger leap. In this case, the two tests are nearly identical, and the fix for them is similar as well: we only have to remove two question marks (why the hell did I write them in the first place?):
public function isValid($time_specification)
{
$hours = '([0-1][0-9]|2[0-3])';
$minutes = '([0-5][0-9])';
return preg_match(
"/^$hours:$minutes\$/",
$time_specification
) == 1;
}There’s no doubt that the trivial steps joined together here are visible for everyone, so let’s move on. What to refactor now? I can’t see anything. 
The good news is that we are now validating 24 hour format time specifications and our code is still readable, even the reqular expression.
The half of 24 is 12
But the work to validate it is going to be at least the double. Let’s start with some positive tests:
public function test12HourFormatIsAccepted()
{
$this->assertTrue($this->validator->isValid('10:42 AM'));
}That’s very similar to test24HourFormatIsAccepted(), but we’re not in Red, so we have to write even more code to get into Green!
What is the simplest regular expression that can make our new testcase pass? Yes, it’s only two characters, but a nice facepalm:
public function isValid($time_specification)
{
$hours = '([0-1][0-9]|2[0-3])';
$minutes = '([0-5][0-9])';
return preg_match(
"/^$hours:$minutes.*\$/",
$time_specification
) == 1;
}Now we accept any bullshit following a 24 hour format time specification. But we can refactor now:
/**
* @dataProvider provideValidTimeSpecifications
*/
public function testValidTimeSpecificationsAreAccepted($time_specification)
{
$this->assertTrue($this->validator->isValid($time_specification));
}
public function provideValidTimeSpecifications()
{
return array(
'Simple 24 hour time specification' => array('10:42'),
'Simple 12 hour time specification' => array('10:42 AM'),
);
}Now we’re green, but we’ve just invalidated our assertion about the exactly one colon.
Exactly one colon is allowed
public function provideInvalidTimeSpecifications()
{
return array(
'Time specification must contain at least one colon' => array('1042'),
'Time specification must contain at most one colon' => array('10::42'),
'Time specification must not contain colon after minutes' => array('10:42:'),
'Hours must be numeric' => array('ab:42'),
'Hours must be less than 24' => array('24:42'),
'Minutes must be numeric' => array('10:ab'),
'Minutes must be less than 60' => array('10:60'),
'Hours must be two-digit' => array('1:42'),
'Minutes must be two-digit' => array('10:4'),
);
}The not so beautiful solution can be something like this:
public function isValid($time_specification)
{
$hours = '([0-1][0-9]|2[0-3])';
$minutes = '([0-5][0-9])';
return preg_match(
"/^$hours:{$minutes}[^:]*\$/",
$time_specification
) == 1;
}PHP thought I wanted to refer to $minutes as an array, so I put curly braces around the variable.
Now we’re in Green again, so we can refactor the code. First the tests:
public function provideValidTimeSpecifications()
{
return array(
'24 hour time specification' => array('10:42'),
'12 hour time specification in the morning' => array('10:42 AM'),
'12 hour time specification in the afternoon' => array('10:42 PM'),
);
}Okay, I’m cheating. I added another testcase that I know will be helpful later on, but it still passes with our current production code, so it won’t hurt. Apropo, the production code: a minor refactoring might be to reintroduce the variable we’ve deleted a few minutes ago.
public function isValid($time_specification)
{
$hours = '([0-1][0-9]|2[0-3])';
$minutes = '([0-5][0-9])';
$not_colon = '[^:]*';
return preg_match(
"/^$hours:$minutes$not_colon\$/",
$time_specification
) == 1;
}At least it’s readable. Let’s move on, that $not_colon will not haunt us too long.
Bad idea
I want to get rid of $not_colon as soon as possible, so let’s force the evolution of the regexp into a direction that does not involve $not_colon existing any longer. I want a space after the minutes part of the time specification:
public function provideInvalidTimeSpecifications()
{
return array(
'Time specification must contain at least one colon' => array('1042'),
'Time specification must contain at most one colon' => array('10::42'),
'Time specification must not contain colon after minutes' => array('10:42:'),
'Hours must be numeric' => array('ab:42'),
'Hours must be less than 24' => array('24:42'),
'Minutes must be numeric' => array('10:ab'),
'Minutes must be less than 60' => array('10:60'),
'Hours must be two-digit' => array('1:42'),
'Minutes must be two-digit' => array('10:4'),
'12 hour time specification must contain a space after minutes' => array('10:42AM'),
);
}The first idea that came to my mind to make that pass was to insert a space before $not_colon in the regexp:
"/^$hours:$minutes $not_colon\$/"That makes the 24 hour format tests fail, so I deleted both the space and the new testcase. Though the new testcase was a teeny-tiny little step, it’d have required bigger changes in the regular expression, namely to separate the two kinds of hour format. Instead I introduced a more strict testcase in provideInvalidTimeSpecifications() that is comparable to the size of the changes to make it pass while not breaking all the other tests:
'12 hour format must end with AM or PM' => array('10:42 XY'),The production code to pass that test:
public function isValid($time_specification)
{
$hours = '([0-1][0-9]|2[0-3])';
$minutes = '([0-5][0-9])';
$ampm = '( [AP]M)';
return preg_match(
"/^$hours:$minutes$ampm?\$/",
$time_specification
) == 1;
}Reviewing that now I can see I could have made the original testcase pass by applying the same changes I did for this case, but the test I deleted was not suggesting it. It seems to me that TDD is not about coding skills but about testing skills. Writing good code is one thing, but writing good tests that enforce building up good code step-by-step can be at least as much important.
Differentiating 12 hour and 24 hour formats
Time for a bigger change. A new testcase for the negative tests:
'24 hour format must be exactly 5 characters long' => array('14:42 PM'),To make that pass, the regular expression must recognize the difference between the two kinds of time formats. It requires matching numbers less than 13, but most of the code needed already exists.
public function isValid($time_specification)
{
$minutes = '([0-5][0-9])';
$hours_less_than_24 = '([0-1][0-9]|2[0-3])';
$time_spec_24 = "$hours_less_than_24:$minutes";
$hours_less_than13 = '(0[0-9]|1[012])';
$ampm = '( [AP]M)';
$time_spec_12 = "$hours_less_than13:$minutes$ampm";
return preg_match(
"/^($time_spec_24|$time_spec_12)\$/",
$time_specification
) == 1;
}It seems to be a big change, but actually it’s quite simple: the question mark has been substituted with the two alternatives it specified: one is hour specification without $ampm, the other is the same, but with $ampm. Of course the second alternative should not match hours greater than 12, so it required a second type of hour matching regular expression. When everything worked, some extractions and variable renames were done.
Attempt to write more failing tests
Are we ready? The code in isValid() seems to contain all the information appearing in the requirements, so there must be only a few small steps remaining. Let’s try adding some new tests. These should not be considered valid:
'Hour part of 12 hour format must be less than 13' => array('13:00 PM'),
'12 hour format must be exactly 8 characters long' => array('12:45 AM'),They pass without touching the code, we couldn’t manage to get into Red. This means there’s some room for further refactoring. All the dirty details of building our regular expressions can go to a private method buried at the bottom of the class:
class TimeValidator
{
public function isValid($time_specification)
{
return preg_match($this->buildRegExp(), $time_specification) == 1;
}
private function buildRegExp()
{
$minutes = '([0-5][0-9])';
$hours_less_than_24 = '([0-1][0-9]|2[0-3])';
$time_spec_24 = "$hours_less_than_24:$minutes";
$hours_less_than13 = '(0[0-9]|1[012])';
$ampm = '( [AP]M)';
$time_spec_12 = "$hours_less_than13:$minutes$ampm";
return "/^($time_spec_24|$time_spec_12)\$/";
}
}Maybe isValid() is easier to read like this:
public function isValid($time_specification)
{
return 1 == preg_match($this->buildRegExp(), $time_specification);
}So is there anything to test? Well, I’m sure PHP has a gotcha for us:
'Multiline strings are not accepted' => array("10:42\n"),Bang, it fails! The fix is very simple:
return "/^($time_spec_24|$time_spec_12)\$/D";Sometimes it’s worth reading around PCRE modifiers in PHP documentation, just to make time pass faster.
Leading zeros
One more thing I miss: though the code cares about leading zeros, there’s no testcase mentioning them. So these should be valid:
'12 hour time specification with leading zero' => array('00:42 PM'),
'24 hour time specification with leading zero' => array('00:42'),Doesn’t that 00:42 PM look weird? I’m not used to 12 hour time format, so I had to think about it for a few seconds: in 12 hour notation there’s no such thing as 00:00. Hours can be between 01 and 12, which means that our two new passing tests should look like:
'12 hour time specification with leading zero' => array('01:42 PM'),
'24 hour time specification with leading zero' => array('00:42'),(Yes, they pass as expected. Note that I forgot this speciality of 12 hour notation when writing the requirements!)
And the bug can be easily triggered by this negative test:
'12 hour time specification does not allow hours to be zero' => array('00:42 PM'And the code fixing it:
$hours_less_than13 = '(0[1-9]|1[012])';The whole code
After adding some corner cases to the list of positive tests, the final results are:
TimeValidator.php
class TimeValidator
{
public function isValid($time_specification)
{
return 1 == preg_match($this->buildRegExp(), $time_specification);
}
private function buildRegExp()
{
$minutes = '([0-5][0-9])';
$hours_less_than_24 = '([0-1][0-9]|2[0-3])';
$time_spec_24 = "$hours_less_than_24:$minutes";
$hours_less_than13 = '(0[1-9]|1[012])';
$ampm = '( [AP]M)';
$time_spec_12 = "$hours_less_than13:$minutes$ampm";
return "/^($time_spec_24|$time_spec_12)\$/D";
}
}TimeValidatorTest.php
class TimeValidatorTest extends PHPUnit_Framework_TestCase
{
public function setUp()
{
$this->validator = new TimeValidator();
}
/**
* @dataProvider provideValidTimeSpecifications
*/
public function testValidTimeSpecificationsAreAccepted($time_specification)
{
$this->assertTrue($this->validator->isValid($time_specification));
}
public function provideValidTimeSpecifications()
{
return array(
'24 hour time specification' => array('10:42'),
'12 hour time specification in the morning' => array('10:42 AM'),
'12 hour time specification in the afternoon' => array('10:42 PM'),
'12 hour time specification with leading zero' => array('01:42 PM'),
'24 hour time specification with leading zero' => array('00:42'),
'First minute of a 24 hour specification' => array('00:00'),
'First minute of a 12 hour specification' => array('01:00 AM'),
'Last 12 hour time specification in the morning' => array('12:59 AM'),
'Last 12 hour time specification in the afternoon' => array('12:59 PM'),
'Last 24 hour time specification' => array('23:59'),
);
}
/**
* @dataProvider provideInvalidTimeSpecifications
*/
public function testInvalidTimeSpecificationsAreNotAccepted($time_specification)
{
$this->assertFalse($this->validator->isValid($time_specification));
}
public function provideInvalidTimeSpecifications()
{
return array(
'Time specification must contain at least one colon' => array('1042'),
'Time specification must contain at most one colon' => array('10::42'),
'Time specification must not contain colon after minutes' => array('10:42:'),
'Hours must be numeric' => array('ab:42'),
'Hours must be less than 24' => array('24:42'),
'Minutes must be numeric' => array('10:ab'),
'Minutes must be less than 60' => array('10:60'),
'Hours must be two-digit' => array('1:42'),
'Minutes must be two-digit' => array('10:4'),
'12 hour format must end with AM or PM' => array('10:42 XY'),
'24 hour format must be exactly 5 characters long' => array('14:42 PM'),
'Hour part of 12 hour format must be less than 13' => array('13:00 PM'),
'12 hour format must be exactly 8 characters long' => array('12:45 AM'),
'Multiline strings are not accepted' => array("10:42\n"),
'12 hour time specification does not allow hours to be zero' => array('00:42 PM'),
);
}
private $validator;
}You can check them out at GitHub.
Conclusion
The whole code copied above took about 45-60 minutes to write (including taking notes for this blog post), during which I’ve learnt a lot of things about practising TDD. I’m sure that if I tried to reproduce this experiment from scratch, it would take several steps less while still moving with teeny-tiny steps forward.
Just as any part of code, regular expressions also worth writing a bunch of unit tests that make sure that the code can be changed anytime later, either to fix bugs or to extend functionality. The big advantage of unit tests (besides architectural flexibility, documentation, etc.) is not that they can expose any possible bug that can be imagined but they allow the code to be changed without worrying much about breaking existing, well-tested functionality.
But there are some gotchas in the field as well:
- There’s no tool to measure coverage for regular expressions that I’m aware of at the moment. The most useful hit I found with Google doesn’t help much either.
- It’s very easy to overlook bugs and miss testcases during test-driving regular expressions. (When the regexp engine that comes bundled with your language has some gotchas to offer, well, that doesn’t make the situation much better.)
- One character change in the regular expression may require a bunch of new testcases to be written.
RECENT POST
As you might have already noticed, I'm a great fan ... [Read More]
Last week I was at Linuxwochen in ... [Read More]
Twitter
LinkedIn
