Test driven development when implementing a flexible length list

According to the commonly used TDD strategy, to implement something, you write a test that fail the code first, write the simplest code, refactor, and then repeat. I am trying to imagine this scenario with implementing a flexible length list (e.g. List<T> in .net.

Let’s say I first test by inserting one item. Probably the simplest way to achieve this is by backing the list with an array with length 1 (which will pass the test). Nothing to refactor here, so I’ll go ahead and write another test that insert 2 items. I’ll simply change the array length to 2, and the test pass again. Then I write test with 3 items, expand the array, and repeat again. I will end up forever doing this until I’m tired.

Is this an exception to the fail-test-first strategy? Or am I missing something in the above strategy?

PS: The actual implementation backs the list with an array which grows twice as large every time the number of elements exceed the array length.

“Write the most simple thing that could possibly work” is one principle, but it is not the only one, and it isn’t always the most important one. “Don’t repeat yourself” is arguably more important, and repeating yourself the way you describe is definitely not justified by “most simple”. As soon as you notice repeating yourself, you should switch to a solution that can handle more than one list length.

Note that this solution may very well still be a fixed-length array if you know that you will not need more than a given number of elements as per the requirements. Alternatively, it might be a dynamic structure that grows with the demands made on it. But in no case is it useful to climb the latter of integers one by one – not least because you can’t possibly reach the top.

Ok, so you are doing what you think is the simplest thing that works, but you haven’t defined your problem adequately.

Turn the problem around and look at what you have. “Implement a List clone” has many nuances to it which need to be expanded and documented. What is the purpose of this List clone? What number of items is it expected to support?

Generally answers to these and other questions come out at the beginning. For example, ask yourself why are you implementing a List replacement? If it’s just a coding exercise, you need to flesh out a scenario a bit. In the real world you might be doing this because the existing List implementation does not exhibit certain characteristics you want. It might be too slow or not sorted or unable to cope with a gazillion items or what ever. That is what you are lacking here.

To restate the problem, how will you know that you are done? What are your acceptance criteria? What does “Working and complete” mean for this problem? TDD may flush out issues like what happens if you try and access an item at position “-3.2”, but it actually doesn’t have to. What it is supposed to do is make sure your code a) does what it is expected to do and b) continues to do what is expected of it when you refactor or replace it.

You can use for in tests. I would create one test which inserts one item. And then another test which inserts a random number of items (where count > reallocation size).

I would however never start with an internal array size of 1. There’s no point, it’s a list, isn’t it?

“I’ll go ahead and write another test that insert 2 items. (…) Then I write test with 3 items, expand the array, and repeat again. I will end up forever doing this until I’m tired.”

The problem here is not that your implementation of List<T> is flawed, but that your unit tests are specifying the wrong kind of implementation.

If you consider these unit tests a specification for your List<T> implementation, then you have just specified something like the following:

Can insert 1 item into the empty list, after which it will contain 1 item.
Can insert 2 items into the empty list, after which it will contain 2 items.
Can insert 3 items into the empty list, after which it will contain 3 items.
etc.

And once your tests pass, your list will be able to fulfill exactly that specification. But is this really what you want?

Or would you perhaps prefer a more general specification, such as the following?:

Can insert 1 item into the empty list, after which it will contain 1 item.
Can insert 1 item into a list with n items, after which it will contain n+1 items.

If so, write different unit tests that encode that specification instead (and you will find that you no longer need infinitely many tests, but that you’re actually done after two).

If flexible length matters, the best way I can think is to write a general test as function with argument the number of entries.
Then the nature of your problem should tell you which numbers are important to test for. Good candidates are numbers 0 and 1.
In general, you want to test what Robert Martin calls “Boundary conditions” in his great book “Clean Code”, described as:

Boundary is what separates the known from the unknown

The other side of the boundary in your case would be a large number entries, say the largest you can expect, to see that your system can cope with it.

TL;DR

Testing is more of an art than a science. How to construct a test is actually less important than knowing what’s useful to test.

Test Behavior

Test behavior, not implementation details. What behavior are you actually trying to test? In all likelihood, your feature needs to do just two things: create a list, and extract data from the list.

From a pragmatic point of view, it doesn’t really matter how your list is implemented. What you really want to know is whether your inputs result in some expected output. For example:

List Creation

Given data elements x, y, and z
When I call the create method with those elements
Then the method returns a list that matches my fixture object.
List Extraction

Given a list containing 50 fixture elements
When I look at the 43rd element
Then I should find my expected value.

In most cases, non-functional requirements can be described in behavioral terms, too.

Test Boundary Conditions

It’s not generally useful to test infinity, or to exhaustively test every possible input or intermediate value in a system. On the other hand, it is often useful to think about boundary conditions like:

A list with no data elements.
A list with a very small number of data elements.
A list with a very large number of data elements.

A test is really a hypothesis that you’re validating, so it’s fine to make documented assumptions. If you’re unlikely to ever have more than 500 elements in your list, then you might define boundaries at elements 499, 500, and 501 that are worth testing; however, there’s almost no value in explicitly testing 13,756 elements in this scenario because it’s already covered by your boundary tests.

I think you are confusing unit tests with property-based testing in your question.

Unit tests look at a class as if it was a unit of processing in a signal processing chain, such as an amplifier circuit or a guitar effects rack. I think Kent Beck used exactly this metaphor in his work “Test Driven Development: By Example”, but right now I don’t have a copy of the book to check.

The point is to explain that it is easier to check that a certain filter always takes out high frequencies, than to check if a specific combination of many filters and distortions make you sound exactly like Jimi Hendrix.

Applied to your case, you may want to test in a unit test that a List class can add elements as needed. Being strict with TDD philosophy, you should arrange for the List to already hold a random number of elements before adding to it — otherwise, a minimal implementation might know the expected total number and just return that.

Property-based testing, on the other hand, checks that a function is mathematically well-defined in the sense that it returns what is expected for the whole domain where it is defined (the definition here is mine, and may be inaccurate). You can get an idea of how this works by reading on QuickCheck and ScalaCheck.

The core concept is that if you pass to the test framework a function that has a typed signature, e.g. sum(one: Int, another: Int), then the framework generates many tests by traversing all possible variations of the type. In the sum example, Int goes from Int.MinValue to Int.MaxValue: the framework picks, say, 100 value pairs and tries to sum them. For more complex classes, you may need to tell the framework how to create an Arbitrary instance of your class.

Applied to your case, you may want to show that the length of your List is always increased by one after an add operation. Define an Arbitrary List as a List that already holds a random number of items, and define that after an add this number is increased by 1.

The main benefit of property-based testing is that you get a lot of tests written automatically for you, and you may even control the generation in order to look for edge cases. The property-based test will generate a 100 lists and check that the invariant holds; the unit test would have to be repeated a 100 times in order to give you such a guarantee. However, property-based testing is not a silver bullet, it is just a complement for unit tests in certain situations.

Filed under: softwareengineering - @ 22:00

Thẻ: list, tdd, unit-testing

Thiết kế website giá rẻ

Danh mục