FROM THE ARCHIVES OF PRAGPUB MAGAZINE, JUNE 2017 🧟♀️🧟♂️
TDD Guided by ZOMBIES: Zombies to the Rescue
by James Grenning
📚 Connect with us. Want to hear what’s new at The Pragmatic Bookshelf? Sign up for our newsletter. You’ll be the first to know about author speaking engagements, books in beta, new books in print, and promo codes that give you discounts of up to 40 percent.
James has been using and teaching Test-Driven Development for years, with a little help from ZOMBIES.
Have you had a hard time figuring out where to start with Test-Driven Development? What if ZOMBIES could help you build code that does exactly what it is supposed to do? What if ZOMBIES helped you to build a test harness that could keep your code clean and behaving properly for a long and useful life?
I’m not talking about those zombies! ZOMBIES is an acronym.
ZOMBIES to the Rescue
One of the seemingly odd things I saw back in 1999 when Kent Beck, Ron Jeffries, and others demonstrated Test-Driven Development, was how they always started with the simplest cases, working their way deliberately to the more involved cases. I mean really simple. For example, they’d first ask, how would the object respond right after it is initialized?
They would add one behavior at a time. Initially, each behavior specified in a test scenario was an opportunity to try interface ideas. The early tests usually had hard-coded return results. Each implementation was so simple, ZOMBIES could do it.
People new to TDD often struggle with what test to write. It’s hard to know where to start or what test to write next. It’s hard to know when you are done, and it’s scary to think you will leave some incomplete code behind. Scary! How can ZOMBIES help with scary?!
I’ve come to rely on ZOMBIES to help explain how I figure out the next test, and what I am considering as I am writing the test. I find that ZOMBIES help me when I am stuck on a programming problem. ZOMBIES help find a logical next step. ZOMBIES help me keep on the firm footing of continually establishing cause and effect. ZOMBIES help me hone my procrastination skills, by suggesting what to do now and what to put off until later.
Procrastination skills!? Yes! Procrastination is a set of skills to develop and master. But only use your procrastination skills for good!
Let me spell out ZOMBIES and explain the algorithm:
Z — Zero
O — One
M — Many (or More complex)
B — Boundary Behaviors
I — Interface definition
E — Exercise Exceptional behavior
S — Simple Scenarios, Simple Solutions
When test-driving guided by ZOMBIES, the first-test Scenarios are for Simple post-conditions of a just created object. These are the Zero cases. While defining the Zero cases, take care to design the Interface and capture the Boundary Behaviors in your test Scenarios. Keep it Simple, both Solutions and Scenarios. You’ll find that keeping it simple is hard. But once progress is made on the Zero cases, move to the next special Boundary case, testing the Behavior desired when transitioning from Zero to One. To do so, there are likely other Interfaces to define and use in new test Scenarios. Once the Boundary Behaviors between Zero and One (and possibly back to Zero from One) have been captured in tests, move on to start to generalize your design now dealing with More complex Scenarios and Many items being managed. Often there are new Boundary conditions to be concerned with. Finally, review your work and make sure you consider and Exercise the Exceptional things that might happen.
(I was hoping to work ‘P’ for procrastination into the acronym. ZOMBIE aPocalypse?)
ZOMBIES is not your usual sequential acronym. It is only partially sequential. It has two dimensions.
One Axis is ZOM and the orthogonal axis is BIE, with simple test scenarios (several reasons for the S) bringing them together.
Zombies are chaotic but ZOMBIES are orderly and purposeful. Initial test Scenarios follow the ZOM pattern from simple to complex, while the things we consider come from BIE, all the time aiming for Simplicity in test Scenarios and production code Solutions.
Are you ready for some code? Nothing like an example to understand ZOMBIES.
Working with ZOMBIES
The rest of the article explains the role of ZOMBIES in test-driving a simple C module that implements a CircularBuffer or First-In-First-Out (FIFO) data structure.
This CircularBuffer will hold a series of integers. We can Put() a new integer in and Get() the oldest out. If it IsFull(), it will reject all new attempts to Put(). If it IsEmpty(), a Get() returns a default value that you can specify during Create().
There are quite a few usage scenarios that have to be tested, especially around the boundaries and exceptional things that can happen. Just to refresh your memory, here is a diagram to illustrate a CircularBuffer implementation.
Before starting, make a list of Scenarios to test, in no particular order:
- Wrap around
- Overflow
- Underflow
- Empty
- Full
- Happy path — FIFO
I use this example in my TDD for Embedded C or C++ training courses.
Engineers are drawn to the more challenging parts of the implementation, like wrap around, overflow, and underflow. They were taught to go after the tough problems first. In TDD guided by my ZOMBIES, we start with the easy stuff and build a foundation of simple behaviors first, procrastinating skillfully. Then we work out the more involved scenarios and behaviors one at a time.
For CircularBuffer, the zero scenario focuses on the test cases for the newly created container: it is empty; it is not full. Testing that the new CircularBuffer is empty and not full leads to defining interfaces for the production code. The test cases record critical boundary behaviors. Let’s see what these tests look like in CppUTest, an open source test harness (designed for embedded C and C++ programmers in mind).
NOTE: In all the examples, the tests are written one at a time, and the code to pass each test is written incrementally. I’m just showing them in batches. I’ll also take advantage of calloc()’s behavior of initializing allocated memory to zero. So while using calloc() I won’t explicitly initialize member variables to zero.
The thing that really bothers people new to TDD, is that to pass these tests, this is all the code that is needed:
With that code, there are often gasps and shaking heads from the people new to TDD. The fear of past programming mistakes shows on their faces. “You are not using or storing the Create parameters.” “IsEmpty and IsFull are nowhere close to right!” “What if you forget to come back and change those hard-coded results!?”
With ZOMBIES helping, it may seem scary, but the next action is Simple: attack one of the hardcoded return statements right now, and add the other to your test list if it’s not already there.
If you look at the effort to get the code and tests to this point, most of the effort is spent to keep the compiler and linker happy. Due to the Simple Scenarios coming first, and the incomplete but Simple Solution that passes all the tests, we can be confident that tests pass for the intended Behavior and fail for unintended Behavior.
If the next test Put() a value into the CircularBuffer, it would not be empty. Hard coding IsFull() would not work for both Scenarios. So write this Boundary Behavior test that defines the Put() Interface that stores One item.
TEST(CircularBuffer, is_not_empty_after_put)
{
CircularBuffer_Put(buffer, 42);
CHECK_FALSE(CircularBuffer_IsEmpty(buffer));
}Expanding the Interface further and defining another Boundary Behavior Scenario, this tests transitions the CircularBuffer back to empty. Next, make sure Get() returns what was Put() for this One item in the FIFO Boundary Behavior.
TEST(CircularBuffer, is_empty_after_put_then_get)
{
CircularBuffer_Put(buffer, 42);
CircularBuffer_Get(buffer);
CHECK_TRUE(CircularBuffer_IsEmpty(buffer));
}
TEST(CircularBuffer, get_equals_put_for_one_item)
{
CircularBuffer_Put(buffer, 42);
LONGS_EQUAL(42, CircularBuffer_Get(buffer));
}When we do the Simplest thing that moves the code toward the solution we have in mind, very little production code is needed to pass these tests.
Whenever we can get by with an incomplete solution in the production code, it means one or more tests are needed to fully exercise the code.
More gasps and groans, as another hard-coded value is introduced. The horror of not even saving the value that is Put()! It can be pretty scary to program with ZOMBIES, until you get to know them.
I’ve seen thousands of programmers solve this problem (in my training classes). Many cannot resist putting in an implementation for IsFull() right now. I’ve seen virtually no programmers get it right on the first try, especially if they use the index and outdex to implement IsFull(). To the TDD learner, it is scary to procrastinate, but you can always add anything you think you might forget to the test list. I think it is scarier to leave behind untested code for such an important case.
What have we accomplished so far with help from ZOMBIES? To the novice, “you are testing nothing!” Sure enough, but I think I’ve accomplished several important things:
- The interface is nearly complete and we can see where it is going. If it was inconvenient to use, we’d know already!
- The code is proving to be testable.
- A lot of compiler syntax has been tamed for our needs.
- Several important boundary conditions have been captured in tests we are confident in.
- I can devote less of my brain to those boundary cases as I define the rest of the behaviors for the
CircularBuffer. The tests will tell me if my code stops following the behaviors defined in the test scenarios. - We have explored a specific mechanism that the
CircularBuffercan use to report that it is empty or not empty. Saving the value has nothing to do with determiningIsEmpty().
Now that the Zero/One Boundary Behavior Scenarios have been cataloged and the Interface has evolved, let’s finally make this a FIFO as we define the first scenario for Many contained items.
TEST(CircularBuffer, put_get_is_fifo)
{
CircularBuffer_Put(buffer, 41);
CircularBuffer_Put(buffer, 42);
CircularBuffer_Put(buffer, 43);
LONGS_EQUAL(41, CircularBuffer_Get(buffer));
LONGS_EQUAL(42, CircularBuffer_Get(buffer));
LONGS_EQUAL(43, CircularBuffer_Get(buffer));
}There are a couple things to consider at this step. How should we dynamically size the array to hold the values? We could do two allocations or one. If we are using the heap, we better make sure we put the allocated memory back when the CircularBuffer is destroyed. Then we also have to save and retrieve the value in a First-In First-Out manner.
Keeping it Simple, let’s make those changes one at a time. First FIFO, then dynamic allocation. For now, we can hard code the size of the values array. It will be a little easier to keep the code working with a single change. Repeat after me: It’s easier to keep code working than to fix it after you break it.
I’d like to add Boundary tests for IsFull(), but up to this point there is no notion of capacity. So let’s introduce capacity to the tests and code. It will be handy for callers to access the CircularBuffer’s capacity. Also we’ll have to add a capacity parameter to Create() function. These tests drive the initial Interface, and the adding of capacity to Create().
TEST(CircularBuffer, report_capacity)
{
LONGS_EQUAL(CAPACITY, CircularBuffer_Capacity(buffer));
}
TEST(CircularBuffer, capacity_is_adjustable)
{
CircularBuffer * buffer = CircularBuffer_Create(CAPACITY+2);
LONGS_EQUAL(CAPACITY+2, CircularBuffer_Capacity(buffer));
CircularBuffer_Destroy(buffer);
}The capacity_is_adjustable test established cause and effect of tying Create() to Capacity(). Here’s the implementation of Capacity() and the associated changes. We did not actually use the capacity yet.
Now the code is ready to add dynamic allocation. Given that: One, we already have a fixed-size array working, and two, capacity has been introduced. There is not a really good way for the test to force the array allocation with malloc() or calloc(), so we treat it as a refactoring, changing the structure without changing the external behavior.
This step usually does not go too smoothly for people in my training. There are a lot of details to get right.
I chose the single allocation implementation, where int values[] has to be the last member of the struct, the malloc() size must take into account the size of the struct, and the space needed for capacity number of ints, not to mention that we can’t allow a memory leak. Thankfully, CppUTest has leak detection. You can see that changing from calloc() to malloc() has to be accompanied with explicit member variable initializations. With capacity and dynamic sizing complete, it is finally possible to completely fill the buffer.
fillItUp() is a helper function. It started life as an in-line for loop in the test case, primitively filling the buffer. I generally don’t like loops in unit tests. I’d rather read a test top to bottom as a scenario specification. Extracting fillItUp() from the test cleans up the test; fillItUp() could be handy for other tests too. Here is a wrong IsFull() that works as long as we have not yet wrapped.
This implementation passes the test, but we know it won’t survive wrapping. This simple and wrong implementation makes me think of another Boundary Behavior that should be tested. Like we did with IsEmpty(), let’s transition away from being full.
TEST(CircularBuffer, is_not_full_after_get_from_full_buffer)
{
fillItUp(CircularBuffer_Capacity(buffer));
CircularBuffer_Get(buffer);
CHECK_FALSE(CircularBuffer_IsFull(buffer));
}Here is another wrong implementation, but this will all change with wrapping so we take the passing Boundary test as progress.
Now, finally, we get to one of the final Boundary cases. The Scenario that many engineers think of first: wrapping!
TEST(CircularBuffer, force_a_buffer_wraparound)
{
CircularBuffer * buffer = CircularBuffer_Create(2);
CircularBuffer_Put(buffer, 1);
CircularBuffer_Put(buffer, 2);
CircularBuffer_Get(buffer);
CircularBuffer_Put(buffer, 3);
LONGS_EQUAL(2, CircularBuffer_Get(buffer));
LONGS_EQUAL(3, CircularBuffer_Get(buffer));
CHECK_TRUE(CircularBuffer_IsEmpty(buffer));
CircularBuffer_Destroy(buffer);
}CppUTest reports after writing this test that memory was corrupted. Because wrapping is not yet implemented, the int after the end of the allocated memory was overwritten. CppUTest overrides memory allocation and adds a guard value at the end of the allocated memory. If the guard is changed, CppUTest lets you know. The existing tests help keep the code working during this change. It is a small change to Put() and Get().
That implementation broke IsFull() Boundary Behavior just as suspected.
compiling CircularBuffer.c
Building archive lib/libCircularBuffer.a
r -objs/CircularBuffer.o
Linking CircularBuffer_tests
Running CircularBuffer_tests
..
CircularBufferTest.cpp:95: error:
Failure in TEST(CircularBuffer, fill_to_capacity)
CHECK_TRUE(CircularBuffer_IsFull(buffer)) failed
.........
Errors (1 failures, 12 tests, 12 ran, 15 checks, 0 ignored,
0 filtered out, 2 ms)That failure may have been surprising.
It’s time to look at the sketch of a wrapped full buffer, and what it means to our current implementation.
After wrapping, self->index and self->outdex are the same! Full and empty can’t be the same! That’s not logical. During my training exercise, many programmers get stuck here trying to get IsFull() working using only self->index, self->outdex, and self->capacity. I usually suggest they look for a Simple Solution that will work.
In training, I’ll sometimes provide this nudge: “How many items are in an empty buffer?” “How many are in a full buffer?” A simple counter will do. (There are other solutions.)
Here is the code just after introducing self->count for IsEmpty() and IsFull(). I also extracted the duplicate wrapping logic out of Put() and Get(). Notice I also extracted duplicate code into nextIndex(), a local helper function.
Just to be sure, let’s add a test to make sure IsFull() works after wrapping. I don’t expect a problem.
TEST(CircularBuffer, full_after_wrapping)
{
CircularBuffer * buffer = CircularBuffer_Create(2);
CircularBuffer_Put(buffer, 1); CircularBuffer_Put(buffer, 2);
CircularBuffer_Get(buffer); CircularBuffer_Put(buffer, 3);
CHECK_TRUE(CircularBuffer_IsFull(buffer));
CircularBuffer_Destroy(buffer);
}Are We There Yet?
Expectation met! Are we done? No! What about the “E” in ZOMBIES? Now that we have all the happy paths, what can go wrong? Most engineers are quick to think of these abuse cases when we’re first composing a test list.
TEST(CircularBuffer, put_to_full_fails)
{
CircularBuffer * buffer = CircularBuffer_Create(1);
CHECK_TRUE(CircularBuffer_Put(buffer, 1));
CHECK_FALSE(CircularBuffer_Put(buffer, 2));
CircularBuffer_Destroy(buffer);
}
TEST(CircularBuffer, get_from_empty_returns_default_value)
{
LONGS_EQUAL(DEFAULT_VALUE, CircularBuffer_Get(buffer));
}Here are the completed Put(), Get() implementations:
Hmmm, while we are exploring things that can go wrong, let’s make sure putting to full and getting from empty does not harm the buffer’s integrity. These are belt and suspender tests: I don’t really expect them to fail.
TEST(CircularBuffer, put_to_full_does_not_damage_contents)
{
CircularBuffer * buffer = CircularBuffer_Create(1, DEFAULT_VALUE);
CircularBuffer_Put(buffer, 1);
CHECK_FALSE(CircularBuffer_Put(buffer, 2));
LONGS_EQUAL(1, CircularBuffer_Get(buffer));
CHECK_TRUE(CircularBuffer_IsEmpty(buffer));
CircularBuffer_Destroy(buffer);
} TEST(CircularBuffer, get_from_empty_does_no_harm)
{
CircularBuffer * buffer = CircularBuffer_Create(1, DEFAULT_VALUE);
CircularBuffer_Get(buffer);
CHECK_TRUE(CircularBuffer_IsEmpty(buffer));
CHECK_FALSE(CircularBuffer_IsFull(buffer));
CircularBuffer_Put(buffer, 1);
CHECK_TRUE(CircularBuffer_IsFull(buffer));
CHECK_FALSE(CircularBuffer_IsEmpty(buffer));
LONGS_EQUAL(1, CircularBuffer_Get(buffer));
CHECK_TRUE(CircularBuffer_IsEmpty(buffer));
CircularBuffer_Destroy(buffer);
}
Notice how this test is not as simple as the earlier tests. We try to make all the tests Simple, though some thwart that goal. This test could be split into several tests, but I don’t think in this case it helps much.
What else can go wrong? Are there other Exceptional or abusive scenarios? Could wrong parameters be passed to the CircularBuffer functions? A quick review suggests tests may be warranted for these abuse Scenarios:
- Create with a zero or negative length
- Passing in a
NULLpointer where a buffer is expected - Running out of heap
How to react to these is outside the scope of this article. You’d have to consider these for your application.
The First Bug Fix!
Let’s toss a curveball at the CircularBuffer. What if we discovered that this CircularBuffer had to be populated from an interrupt routine and read by an application task?
You may think nothing of it, but then again you might. You might encounter some very mysterious behavior using the CircularBuffer in that concurrent environment. Put() and Get() have a shared variable (self->count)! There is a race condition! This code will eventually experience a catastrophic failure because Put() and Get() are not atomic operations. self->count will eventually be corrupted.
Doing some research we come across this wikipedia article on circular buffers. There is a solution that instead of a shared counter, Get() is the only function to change self->index and Put() is the only function to change self->outdex. The algorithm requires that there be an extra cell in values[], while Put() will consider the buffer full when self->index gets within one cell of self->outdex.
This sounds like a significant change to the algorithm, but we have tests to notify us of any test scenarios that break during this Exceptional refactoring. Here’s the production code after the refactoring:
Only four changes were needed:
- Add one to capacity in
Create()andnextIndex() - Changes to
IsEmpty()andIsFull()
That went really smoothly. Even though we decided to implement some of the key decisions in CircularBuffer, in the end we could take them in stride. Early behaviors were easy to get right and keep right as the actual final solution took form.
Final Thoughts
TDD guided by ZOMBIES helps me make progress in growing the behavior of code I am working on. Long ago, it changed how I program. Instead of writing out whole files and functions and then figuring out what is wrong, I define one behavior at a time and implement it as simply as possible, moving the code closer to the end goal as I envision it, keeping the code working the whole time I am changing it. Hand in hand with that is refactoring when I see a way to make the code better; again, keeping the code working because it is easier to keep a system working than to fix it after you break it.
When I wrote Test-Driven Development for Embedded C, I described a behavioral pattern of Test-Driven Developers that I called 0,1,M. My friend Tim Ottinger said, oh yeah, ZOM. There are only three numbers important in computing: Zero, One, and Many. Zero and One are special cases. Many is the first generalization. ZOM has been helping me for years as I practiced and taught TDD. Thanks, Tim! Then there’s DTSTTCPW. Kent Beck showed this handy unpronounceable acronym to me back in 1999: DTSTTCPW. Spelling it out: Do The Simplest Thing That Could Possibly Work. Thanks, Kent!
About the Author
James Grenning trains, coaches, and consults worldwide. James’s mission is to bring modern technical and management practices to product development teams, especially embedded systems development. He is the author of Test-Driven Development for Embedded C. He is a co-author of CppUTest, a popular unit test harness for embedded C and C++. He invented Planning Poker, an estimating technique used around the world, and participated in the creation of the Manifesto for Agile Software Development. This article first appeared on his blog, and if you have any comments, he’d love to continue the discussion there.
