Dancing backwards with Go: why TDD is weird
Colourised image from Swing Time (1936) by morganmonroe81
Fred Astaire? Sure, he was great, but don’t forget Ginger Rogers did everything he did… backwards, and in high heels.
—Bob Thaves
Have you ever tried programming backwards? If not, you’re in for a treat! You won’t even need to wear high heels. (If you want to, though, go for it—you’ll look fabulous!)
The function that never was
Suppose we want to write a Go function that checks whether a given slice is sorted (that is, its elements are in order).
For example, if the input is {1, 2, 3}, the answer
should be true, because the slice is sorted. On the other
hand, if the input is {3, 1, 2}, we should get
false, because the slice is not sorted.
Most people would probably start writing some function
IsSorted. That’s fine for Fred Astaire. Just for fun,
though, shall we try tackling this problem backwards, like Ginger
Rogers?
We’ll start by imagining that we already have the
IsSorted function, and we’ll try to write a test for it.
Once we have the test, we’ll go on to write the function.
In my book The Power of Go: Tests, I use this “magic function” technique a lot to help me develop Go code. If it feels weird to you to write the test before the function itself, don’t worry: I think it takes everyone that way at first. In the book I’ll show you how to apply the trick in all sorts of different situations, from fixing bugs to designing user-friendly APIs.
Let’s see how it works in this scenario; we’ll start by creating a
new Go project called sorted:
mkdir sorted
cd sorted
go mod init github.com/bitfield/sorted
go: creating new go.mod: module github.com/bitfield/sortedNext, we’ll create a source file, and name it
sorted_test.go.
We’ll start by declaring:
package sorted_test
import "testing"Now we can write the test function for IsSorted, but
what should we name it? A great way to name your tests is as a sentence describing the behaviour you
want to test. What would that be here?
Well, one thing we know about IsSorted is that it should
return true for sorted slices. That’s not the only
behaviour we care about, but it’s a good place to start, so let’s make
that sentence our test name:
func TestIsSorted_IsTrueForSortedSlice(t *testing.T) {
}Sounds believable, so let’s fill in the body of the test:
func TestIsSorted_IsTrueForSortedSlice(t *testing.T) {
t.Parallel()
input := []int{1, 2, 3}
if !sorted.IsSorted(input) {
t.Errorf("got false for %v", input)
}
}In other words, given the input 1, 2,
3, if the result of calling IsSorted on this
input is false, the test fails. Straightforward enough, and
IsSorted will definitely need to pass at least
this test if it’s to be any use.
The fastest route to failure
We know IsSorted doesn’t exist yet, but before we
implement it, we first need to know if this test will actually detect
bugs in IsSorted. That’s what tests are for, after all.
Let’s write as little code as we possibly can to get this test
compiling and failing. The first error we have is “undefined:
sorted”. Fair enough: we haven’t defined it!
To fix this, we need to create the sorted package, so
let’s create another new file sorted.go. We’ll start by
declaring:
package sortedNow we can add a suitable import declaration to
sorted_test.go:
import (
"testing"
"github.com/bitfield/sorted"
)That fixes the compile error we had, but now there’s a new one:
undefined: sorted.IsSortedGo is saying “Okay, now I know how to find the sorted
package, but you also referenced an IsSorted function
within it, and I can’t find that.” No worries, we’ll fix that now by
adding the following to the sorted.go file:
func IsSorted(input []int) bool {
}We didn’t write anything in the function body yet, but that’s okay. Remember, all we need is enough code to make the test compile. We don’t expect it to pass yet, and indeed we want to see it fail before we do anything else.
But we’re not there yet. The undefined error goes away,
because we defined the function, but now there’s an error in the
function:
missing returnNot unreasonable, is it? After all, the function signature says that
it returns bool, but we didn’t return anything at all. That
must be wrong, so let’s continue to do as little as possible at each
stage and see how far we can get:
func IsSorted(input []int) bool {
return
}I mean, right? You wanted a return statement, Go, and
now you have one. Are you not entertained?
not enough return values
have ()
want (bool)Apparently return by itself wasn’t enough. We actually
need to supply some value here to return:
func IsSorted(input []int) bool {
return false
}Now everything compiles. “But this won’t work!” I hear you
wail. “It always returns false no matter what the
input!”
Your wailing is on point, dear reader, but remember, we
wanted a non-working implementation to validate the test, and
now we have one. This is the perfect time to check if our test will
actually detect a bug in IsSorted—for instance, that it
always returns false!
Let’s run the test. We assume it will fail, but you never know—that’s why we check:
go test
--- FAIL: TestIsSorted_IsTrueForSortedSlice (0.00s)
sorted_test.go:13: got false for [1 2 3]So that’s a success. Sounds backwards, I know, but that’s how we do. A failing test, when we know the function doesn’t work, proves that the test works. And if we hadn’t proved that, what use would the test be when we want to check if the function does work?
Cranking up the difficulty
Now let’s fix the problem. We could trivially change
IsSorted to return true instead of
false to make this pass, but that doesn’t really get us
anywhere. IsSorted needs to be able to distinguish
between sorted and unsorted slices, not just return a fixed value.
We need two tests, then, for two different behaviours: that
IsSorted is true for sorted inputs, and that
it’s false for unsorted ones. It turns out both are
required for IsSorted to work the way we want.
func TestIsSorted_IsTrueForSortedSlice(t *testing.T) {
t.Parallel()
input := []int{1, 2, 3}
if !sorted.IsSorted(input) {
t.Errorf("got false for %v", input)
}
}
func TestIsSorted_IsFalseForUnsortedSlice(t *testing.T) {
t.Parallel()
input := []int{1, 3, 2}
if sorted.IsSorted(input) {
t.Errorf("got true for %v", input)
}
}A fixed-value implementation could pass one test or the other, but not both. Let’s prove it:
go test
--- FAIL: TestIsSorted_IsTrueForSortedSlice (0.00s)
sorted_test.go:13: got false for [1 2 3]How little work do you think we can do to get both tests passing, then? Because as little work as possible is exactly how much work I plan to do. This approach is key to test-driven development, and it’s called Shameless Green.
The point is that we treat the test as the source of truth for how the program should behave. And if we take that idea seriously, it means that as soon as the test is passing, we don’t need to write any more code. (We may need to write more tests, of course, but that’s nearly always true.)
Baby’s first steps
If any elements are not in order, then at some point we’ll encounter a number that’s smaller than the previous one. The simplest, dumbest way I can think of to detect that is:
func IsSorted(input []int) bool {
prev := 0
for _, v := range input {
if v < prev {
return false
}
}
return true
}It seems reasonable, but I could stare at this code all day and not be sure whether it’s correct or not. Let’s check:
--- FAIL: TestIsSorted_IsFalseForUnsortedSlice (0.00s)
sorted_test.go:21: got true for [1 3 2]Oops. I forgot to update prev with each new number (not
enough coffee today). Let’s add a prev = v to the loop:
func IsSorted(input []int) bool {
prev := 0
for _, v := range input {
if v < prev {
return false
}
prev = v
}
return true
}This passes both tests now, but is it really correct? Again, we could have a staring contest with this code looking for bugs, and we might find some, or we might not.
The backwards programmer’s approach, though, is to stare at the
tests instead. Can we think of some more test cases that might
trip up a buggy implementation of IsSorted?
What about a slice that contains repeated numbers, for example?
func TestIsSorted_IsTrueForSortedSliceWithRepeat(t *testing.T) {
t.Parallel()
input := []int{1, 2, 2}
if !sorted.IsSorted(input) {
t.Errorf("got false for %v", input)
}
}This passes too, which is encouraging. But I notice that the test logic is the same for all our “sorted” tests, so let’s combine them into a single table test.
Cases on the table
Here we are:
func TestIsSorted_IsTrueForSortedSlicesWith(t *testing.T) {
t.Parallel()
inputs := map[string][]int{
"all elements different": {1, 2, 3},
"repeated elements": {1, 2, 2},
}
for name, input := range inputs {
t.Run(name, func(t *testing.T) {
if !sorted.IsSorted(input) {
t.Errorf("got false for %v", input)
}
})
}
}A few things to note about this:
This test runs in parallel with others, because we call
t.Parallel(). That’s more efficient, and there’s usually no reason all our tests can’t be parallel.The test cases are organised as a map, keyed by name. We don’t have to give names to our cases, but it helps understand what this specific case is testing when it fails for some reason.
Using
t.Runturns each case into a named subtest, and all our subtests can share the same function body, which makes things more concise.We don’t need to specify
wantevery time, because it’s alwaystruein this test. It’s best not to mix “should betrue” with “should befalse” cases in a single test, because it makes the logic more complicated. Here, it’s very simple: fail onfalse!
This replaces the two old IsTrue tests, so now let’s add
another table test for IsFalse:
func TestIsSorted_IsFalseForUnsortedSlicesWith(t *testing.T) {
t.Parallel()
inputs := map[string][]int{
"all elements different": {1, 3, 2},
"repeated elements": {3, 2, 2},
}
for name, input := range inputs {
t.Run(name, func(t *testing.T) {
if sorted.IsSorted(input) {
t.Errorf("got true for %v", input)
}
})
}
}Looking good. Time for a well-earned break, I think. Would you care for some tea and cake?
Don’t be so negative!
While I was nibbling at a moist, fudgy chocolate brownie just now, I
thought: prev starts at zero, but what if the first element
is negative? Then we’d wrongly return false for a sorted
slice, because v < prev. Yikes!
Your conventional programmer—Fred Astaire, if you like—would jump
straight into fixing IsSorted. But we’re backwards
programmers, so we’ll use the Ginger Rogers technique: first write a
failing test, then make it pass.
func TestIsSorted_IsTrueForSortedSlicesWith(t *testing.T) {
t.Parallel()
inputs := map[string][]int{
"all elements different": {1, 2, 3},
"repeated elements": {1, 2, 2},
"negative first element": {-1, 2, 3},
}
...This fails as expected:
sorted_test.go:19: got false for [-1 2 3]Now we can fix it. Let’s initialise prev to the first
element of input and then loop over the remaining
elements:
func IsSorted(input []int) bool {
prev := input[0]
for _, v := range input[1:] {
if v < prev {
return false
}
prev = v
}
return true
}Let’s face the music and test:
PASSOh glory be, oh happy day! We can ship the package to production and go out for our team pizza night (extra pepperoni on mine, please).
Later that same week…
Well, everything was fine for a few days, but then a bug report came
in from a customer: IsSorted panicked when they called it
with an empty slice (oh dear).
Well, we can fix this—backwards! Let’s add the customer’s “no elements” test case to our table:
func TestIsSorted_IsTrueForSortedSlicesWith(t *testing.T) {
t.Parallel()
inputs := map[string][]int{
"all elements different": {1, 2, 3},
"repeated elements": {1, 2, 2},
"negative first element": {-1, 2, 3},
"no elements": {},
}
...This should reproduce the bug report:
--- FAIL: TestIsSorted_IsTrueForSortedSlicesWith/no_elements (0.00s)
panic: runtime error: index out of range [0] with length 0Next, we’ll locate the panic using the stack trace:
sorted.IsSorted(...)
/yumyum/cake/yesplease/sorted/sorted.go:4Here’s the offending line 4 in sorted.go:
prev := input[0]Hmm. That tracks: an empty slice has no elements, so we
definitely can’t retrieve its first element, which is what
input[0] tries to do.
But an empty slice is sorted, in the sense that it doesn’t
contain any out-of-order elements. So we can treat this as a special
case, and modify the function to return true straight away
for empty slices.
if len(input) == 0 {
return true
}And while we’re thinking about special cases, it’s clear that we can also handle a one-element slice the same way, and for the same reason. Here’s another test case for that:
func TestIsSorted_IsTrueForSortedSlicesWith(t *testing.T) {
t.Parallel()
inputs := map[string][]int{
"all elements different": {1, 2, 3},
"repeated elements": {1, 2, 2},
"negative first element": {-1, 2, 3},
"no elements": {},
"one element": {1},
}
...A small tweak to the function is all we need:
if len(input) < 2 {
return true
}Tests are passing, and customers are happy. Another win for backwards programming!
Cutting out the calories
A little while later, a new member of the team, Alyssa, is looking at
our current version of IsSorted:
func IsSorted(input []int) bool {
if len(input) < 2 {
return true
}
prev := input[0]
for _, v := range input[1:] {
if v < prev {
return false
}
prev = v
}
return true
}“You know,” she says, “there’s a function for this in the standard
library. If we imported the slices package…”
import "slices"“…I think we could replace all this code with a single function call.”
return slices.IsSorted(input)Huge if true! Well, we know exactly how to find out: run the tests.
Just for fun, let’s use the gotestdox
tool, which both runs the tests and prints their names as
English sentences. “Tests as docs”, if you like.
go run github.com/bitfield/gotestdox/cmd/gotestdox@latest
sorted:
✔ IsSorted is false for unsorted slices with all elements different (0.00s)
✔ IsSorted is false for unsorted slices with repeated elements (0.00s)
✔ IsSorted is true for sorted slices with all elements different (0.00s)
✔ IsSorted is true for sorted slices with negative first element (0.00s)
✔ IsSorted is true for sorted slices with no elements (0.00s)
✔ IsSorted is true for sorted slices with one element (0.00s)
✔ IsSorted is true for sorted slices with repeated elements (0.00s)Wonderful! This is exactly the kind of radical refactoring idea we hoped you’d bring to the team, Alyssa P. Hacker. And backwards programming helped make it safe: by writing our tests first, we made sure that any new code is always covered by tests.
The way forward?
So that’s backwards programming. Once you’ve tried it, it doesn’t really seem so backwards after all, does it?
Next time you have a feature to add or a bug to fix, then, why not try doing the backwards quickstep yourself? It’s as easy as “red, green, refactor”:
- Add a failing test (“red”)
- Make it pass (“green”)
- Tidy up, optimise, and check that all tests still pass (“refactor”)
Just remember to always look where you’re going, and try not to trip over your own feet. (And if you’d like to learn more about backwards programming, you’re welcome to sign up for my dancing lessons.)
