Partitions can help us divide up our input space for testing purposes, but what drives the partitions we use, and how do we choose suitable examples for TDD?
We’ll look at several concerns:
- Problem-Oriented Partitions
- Solution-Oriented Partitions
- Partitions Arising from Partial Functions
- Driving Tests for Partitions Based on Ranges
- Driving Tests for Partitions Not Based on Ranges
- Extra Concerns for Floating Point Values
Partitions don’t drive every kind of test we might write, but they often give us a way to refine our problem and solution to make progress.
Problem-Oriented Partitions
When we’re deciding what the partitions will be, the first place to look is the problem definition or specification. Many times these lay out different behavior for different values.
For example, suppose a credit card company says:
- No penalty if payment is made within 5 days of the due date
- $25 penalty if payment is made between 6 and 13 days after the due date
- $50 penalty if payment is made more than 14 days late
Right away, we can see that there are three “natural” partitions, corresponding to the three clauses. It might be that we can devise a solution that can solve this with one block of code, thus folding it back into one partition, but the natural partitions give us a starting point.
Solution-Oriented Partitions
Partitions need to take both specifications and solutions into account.
For example, in the SortTables(™) data viewer I’ve been working on, data loaded from the database goes through a cache. From the client side, the cache is invisible – you ask for a row, you get it. From the problem point of view, we only need two partitions: for empty and non-empty result sets.
From the solution side, however, there’s a big difference between asking for a row that was recently accessed (and is in the cache), and asking for a row that wasn’t recently accessed (and must be fetched from the database).
With the cache, we need to break non-empty set results into at least three categories:
- result found in cache – return it without hitting the database
- result not found when cache has room – result is fetched, stored in the cache, and returned
- result not found when cache is full – something is removed from cache, and the desired result is fetched, stored, and returned,
The client interface isn’t rich enough to reveal the complexity through the API, although it does show up in performance tests.
Partitions Arising from Partial Functions
A total function defines an output for any input; a partial function defines the output onlyfor certain inputs.
There are pretty much three ways we handle partial functions:
- Ignore it and assume nobody would call with bad values
- Document it
- Enforce it (e.g., throw an exception for inputs with no defined output)
Can you explain what values you will handle? If not, how will callers know whether to use your code?
Can you detect when you’re given values that won’t work? How will you handle them? Will you reject them (e.g., with an exception)?
Can you detect legal values cheaply enough? For example, if your function is defined for prime numbers, it might be too expensive to check them each time.
At any rate, a partition of a partial function is usually a refinement of this:
| values we reject | values we handle |
Example: Absolute value for integers
Mathematically,
{ -i, i < 0
abs(i) = { 0, i == 0
{ i, i > 0
For old time’s sake, let’s implement this with 16-bit integers. Is abs() a partial or total function? Partial, because, a 16-bit int can’t store the absolute value of -32768.
Our initial partitioning looks like this:
| -32768 (reject) | everything else (handle) |
Intermediate Calculations
Identifying the scope of our code is tricky – we need to consider both places where the function isn’t defined for the inputs, and the values that cause problems in computation.
For example, suppose you’re working with 32-bit integers and doing intermediate calculations that square the number. If the number to square will exceed 46,340 (the last integer whose square is smaller than INT32_MAX), our calculation will overflow. Determining the true limits is tricky for anything beyond simple math formulas.
One of my favorite examples of this issue is that binary search in Java had an overflow issue for nine years, based on an algorithm “proven” correct by Jon Bentley in 1986. (See below, “Extra, Extra…”.) The issue was that calculating an average index (L+R)/2 would overflow for very large arrays.
(I take this as a warning about both testing and proofs.)
Driving Tests for Partitions Based on Ranges
Partitioning by ranges is very common.
Ranges can be closed (<= or >=), open (< or >), or half-open or half-closed (closed on one end, open on the other). We can write intervals with “[” or “]” for closed, “(” or “)” for open. Thus, [3,7] is the set {x: 3 <= x <= 7}, and [1,2) is the set {x: 1 <= x < 2}.
When we partition by ranges, we expect to use one piece of code to handle the whole range. If we need different code, we’d split our partition.
What values should we use to test our partition?
One approach would be to grab a typical value out of the middle. But it turns out that come values in a partition are more likely to reveal errors than others.
Some values in a partition are more likely to reveal errors than others.
We’re far more likely to make a mistake at the ends, where it would be easy to do things like use > instead of >=. Taking advantage of this is known as boundary testing, which has been around since at least the 1970s. “Boundaries” are the B in James Grenning’s ZOMBIES acronym, though he includes other types of boundaries in that as well.
To write code that uses the partition [3, 7) – with integers, we’d want to test 2, 3, 6, and 7. With floats, something like 2.999, 3, 6.999, and 7.
Check on and just next to critical boundaries.
You still might test with a typical value, just to be comfortable that the middle of the range is covered, but this is likely to be a confirming test, expected to run green.
Some Classic Ranges
The most basic thing to consider is what kind of numbers you’re talking about. Mathematically, we divide integers into:
Natural Numbers: 1, 2, 3, …
Whole Numbers: 0, 1, 2, 3, …, which contain:
Integers: … -3, -2, -1, 0, 1, 2, 3, …, which contain:
This is the root of the Positive-Zero-Negative (PZN) partition.
Another classic partition is Zero-One-Many (ZOM) – a breakdown of the whole numbers.
Moving into computer arithmetic, with two’s complement numbers, we have a bounded, asymmetric range of numbers. If we’re going to go all the way to the ends, this partition is very common: {-INT_MAX-1}, {-INT_MAX…-1}, {0}, {1…INT_MAX}.
Example Continued – Absolute Value of Integers:
Recall where we left off:
| -32768 (reject) | everything else (handle) |
How do we want to partition the rest? Well, the specification clearly implies a Positive-Zero-Negative breakdown:
| A | B | C | D |
| -32768 | -32767…-1 | 0 | 1…32767 |
Our test cases will cover the boundaries:
- -32768 – only value in partition A – ensure it’s rejected
- -32767 – left boundary of partition B
- -1 – right boundary of partition B
- 0 – only value in partition C
- 1 – left boundary of partition D
- 32767 – right boundary of partition D
You could try these in any order. My natural inclination is Zero, Positive (either), Negative (either), Error, and Confirming (on the remaining values). You could definitely make a case for trying a Negative first, since that’s the interesting case that’s driving the creation of the function.
You might feel comfortable with fewer selections from each partition, with such a simple function.
Driving Tests for Partitions Not Based on Ranges
Not all partitions are ranges.
Suppose we had a function that did one thing for even numbers, another for odd. It would make sense to divide the partitions that way – like interlocking combs:
We can go further, having even more interlocking partitions (though it’s harder to visualize beyond two).
Example: Leap Years
The rules for leap years are:
- years divisible by 4 are leap years,
- except not if they’re years divisible by 100,
- except they are if they’re divisible by 400
Our input is an integer year.
Is it a total or partial function? Clearly, it’s partial, since there was no year 0. As with all things calendar-related, it’s complicated. (See “Change from Julian to Gregorian Calendar” in the references.) The earliest countries switched calendars in 1582, the most recent in 1927.
The high end is a little tricky too – there are proposals that Y4000 NOT be a leap year.
In the end, we negotiate that our function will work for [1582, 4000) so we avoid that problem.
| < 1582 (excluded) | 1582…3999 (included) | >= 4000 (excluded) |
Of the included values, what partitions should we use? Once again, the structure of the specification can guide us:
- Numbers not divisible by 4
- Numbers divisible by 4 but not 100
- Numbers divisible by 100 but not 400
- Numbers divisible by 400
Take a moment to convince yourself that every number falls into one of these buckets.
What values could we use to test?
- 1581 and 4000 – check that exclusions work
- 1582 and 3999 – check that boundaries work – smallest and largest supported values
- 2023, 2025, 2026 – not a leap year; any of these might convince you that case is right
- 2024 – the next leap year (as of 2021)
- 1900 and 2100 – divisible by 100, not a leap year
- 2000, 2400, 3600 – divisible by 400, is a leap year; any of these might be enough
Summary: Choosing data for non-range partitions
- We need to be extra careful that it’s a true partition. (It would be an easy mistake to include 100 in every partition but the first.)
- Even if ranges aren’t used, the smallest and largest values in a partition are a good candidate for a test example.
- Neighboring values between two partitions are also good candidates (such as 2023-2026 in the example above).
- Things outside the math may drive you to certain choices: I picked 2023-2026 as they were likely to show up soonish in the real world.
Extra Concerns for Floating Point Values
Floating point values are similar to integers in some ways: you may have partitions using ranges or not, boundary testing is helpful, and you have to be concerned about intermediate calculations. But it brings in a few other issues worth highlighting.
Floating point numbers (in computers) act just enough like real numbers (in math) to work well only most of the time.
Floating point numbers (computers) are not the same as real numbers (math).
Inexact: A float or double can only represent a small fraction of the values of real numbers. It’s easy to be surprised by this: 10 * 0.1 != 1.0.
One way this comes out is that you need some “fuzz” on equality tests. Two numbers calculated differently are only approximately equal. The xUnit libraries I’m aware of have an extra “accuracy” parameter so the comparison is something like abs(d1 – d2) <= accuracy.
Special Values: IEEE floating point (used by most computers – see article below) specifies some special values:
- NaN – not a number (see the NaN article referenced below)
- Positive Infinity
- Negative Infinity
These values come about when you do things like take the square root of a negative number or divide by zero.
They have special behavior when combined with other numbers, and compare in unexpected ways.
In general, they may tell you that an intermediate calculation failed.
Non-Associative: One of the ways floating points differ from real numbers is that + and * are not associative.
Associativity says for example that (a+b)+c = a+(b+c).
This problem is most noticeable when you mix very large with very small numbers.
Let’s do an example in decimal arithmetic. Suppose you get two decimal digits of precision.
(0.04 + 0.04) + 1.0 = 0.08 + 1.0 = 1.1
but
0.04 + (0.04 + 1.0) = 0.04 + 1.0 = 1.0
Very Large and Very Small Numbers: With integers, we worry about very positive or very negative numbers, but neighboring numbers are always separate by 1. With floating point, we still have to worry about very large numbers, but we also have to worry about very small numbers.
In computers, the differences between neighboring floating point numbers vary with the size of the number. Numbers close to 0 are tightly packed, but big numbers are further apart.
As hinted at by the non-associativity example, mixing different magnitudes can lead to unexpected results.
Loss of Precision: Every time you use an operator, you potentially lose precision. Do enough operations and you totally lose control. Numerical methods suggest you may be able to do things like interval arithmetic as a sort of check. (Interval arithmetic computes with values on either side of the true value, to act as a sort of robustness check.)
All of this is not to scare you away from floating point numbers when they’re suitable, but to reinforce that they’re much more complicated than they seem, so you will have to partition more carefully, and use more test values to validate them.
Conclusion
Good partitions take into account both the structure of the problem and the solution. Each partition represents somewhere we think different code will be required, and both problem and solution affect that.
Some partitions are range-based, and we have a good tool for working with them: boundary testing. Values at and around the boundary tend to be the trickiest to get right. Boundaries aren’t the only challenge though – we also have to be careful about how values in the middle might fail (e.g., too-large intermediate calculations).
Some partitions aren’t based on ranges – and you’ll especially see that as you address types other than numbers. With non-range partitions, be careful that you’ve defined a good partition, not putting any value in separate partitions. Ensure you’ve chosen test examples from each partition.
Floating-point numbers add a few twists, mostly because they’re only an approximation of real numbers. Our instincts from real numbers don’t serve us at the edge cases. We have to worry about approximation, non-number values, precision, and more.
I hope this discussion gives you some insights into how you might create good TDD test examples when confronted with values involving integers and floating point numbers.
References
The Art of Software Testing, by Glenford J. Myers. 1979.
“Change from Julian to Gregorian Calendar”, by Konstantin Bikos and Apama Kher. Retrieved 2021-01-17.
“Extra, Extra – Read All About It: Nearly All Binary Searches and Mergesorts are Broken”, by Joshua Bloch. Retrieved 2021-01-19.
“IEEE 754-1985”. Retrieved 2021-01-19.
“NaN”. Retrieved 2021-01-19.
“TDD Guided by ZOMBIES”, by James Grenning. Retrieved 2021-01-17.
“TDD is an Alchemy Trick: Points and Partitions”, by Bill Wake. Retrieved 2021-01-19.