2

For example, let's say I write a container class, which supports 2 kinds of operations:

  • insert(x): inserts an element
  • get_all(): retrieves all previously inserted elements

Maybe it has some kind of hash set under the hood, or maybe an SQL database, doesn't matter.

It works, it's unit tested, everything's fine, but then I decide I want to retrieve the elements in a specific order, so that subsequent calls (with no new inserts in between) to get_all() produce the same output.

This is a required functionality, in the usual sense of the word.

But it's also an accidental functionality, in the sense that there's a good chance any 'reasonable' unit test would already pass, without any changes to the code, 'accidentally', because of implementation details.

It's clear how to implement this functionality. If I used a hash set, I should switch to an ordered data structure instead. If I used an SQL database, I should add an order column and an ORDER BY clause. The problem is, even if I don't do any of this, the unit test might pass, and when it does it does so consistently. A simple SELECT * FROM SomeTable will reliably return the elements in the order of insertion in most databases (I think), even though that is not a required behavior. A hash set will most likely return its elements in the same order every time until a rehash happens. That same order might as well be the order of insertion, depending on the implementation. These behaviors can be consistent enough that it's hard to break the unit test, even if I actively try to, but not nearly consistent enough to just say 'meh, I guess this data structure is sorted enough' and call it a day.

My question is twofold:

  • How to write code which is more easily testable in spite of accidental functionality?
  • How to test code written without the above in mind in spite of accidental functionality?

For the first question, an approach that might work is to create a 3rd build type (additionally to the common DEBUG and RELEASE builds) which intentionally breaks every not-officially-supported behavior. Something like this is used for Facebook's F14 datastructures:

To make sure code doesn’t take implicit dependencies on F14’s iteration order, we randomize it for debug builds.

But I'm also interested in other solutions, of course.

The second question is a tougher one, I believe. Depending on the exact task it might be possible to break the accidental functionality for a wide range of possible implementations at once, that's one way to go then. Or, specifically to SQL ordering, you can create a view like CREATE VIEW SomeView AS SELECT * FROM SomeTable ORDER BY RANDOM() and run all queries against it, instead of the original table.

But I'm not aware of a general solution.

Runnable example

Consider the following code:

#include <unordered_set>
#include <sstream>

int main()
{
    std::unordered_set<int> s;
    s.insert(3);
    s.insert(1);
    s.insert(2);

    std::stringstream res;
    for (auto e : s) res << e;

    if (res.str() == "312") return 0;  // Test passed.
    else return -1;  // Test failed.
}

Using MSVC++ 2017, this test passes every single time. The problem is, this, of course, does not mean I can rely on unordered_set secretly being ordered, because that functionality is not standard mandated, but completely accidental, and might or might not break with the next inserted value.

  • 4
    There's no such thing as accidental functionality. Unit tests don't fail just because you've added a new requirement. Quite the opposite in fact: the only reason an existing unit test would fail is if you've changed an existing requirement. – Robert Harvey Apr 29 at 20:27
  • 3
    @szmate1618: I think there are some really good questions hidden in your post - but in the current form, I have to agree to Robert Harvey, the question is IMHO too broad. It seems you are mixing at least two different problems here: testing a component which fulfills already some previously undefined requirement using TDD style, which means you want to write a breaking test first. And second: testing that code does not rely on some undocumented feature of another component. I guess you should not mix up these questions, better ask them separately. – Doc Brown Apr 30 at 7:52
  • 4
    ...What I mean that the order of insertion is preserved. Inserting 3, 1, 2 and retrieving 3, 1, 2 is just as problematic. I cannot rely on this behavior, because a unordered_set does not even give this much guarantee, but I also cannot catch this in a unit test, because this non-guaranteed behavior happens every time. -- It would seem that you misunderstand the purpose of unit tests. You can't conclusively prove that non-trivial code works under every possible operating condition. Unit tests provide confidence that your code works, but not proof. – Robert Harvey Apr 30 at 14:16
  • 3
    Going back to your database example, you already stated that most databases return records in insertion order, but do not guarantee that order so you can't rely on it. Do you know what that means? It means that you can't rely on the return order of records from a database unless you include an ORDER BY clause. If a software developer or user is relying on that order in spite of the fact that the specifications already tell them they cannot, that is not "accidental functionality," it is pilot error. – Robert Harvey Apr 30 at 14:30
  • 2
    How do you catch developers relying on an undocumented feature by writing unit tests? It's not possible. The number of such undocumented features is potentially unlimited, and you can't test for them if you don't know about them (that's what "undocumented" means). – Robert Harvey Apr 30 at 14:39
3

Part 1: Handling "accidental functionality" when writing tests

To answer your question, let's start at the beginning: with a failing test. I'm going to take as read the idea that you already understand the principles of TDD and use it. So I can use a completely contrived and pointless example to focus on the issues you are asking about, rather than "selling" TDD itself.

I have a requirement: write a function that can take two numbers between 0 and 10 and return the sum of those numbers. I'm going to use C# here as it's what I'm most used to writing, but the ideas apply to all languages. I write my first test:

[Test]
For0And0_ResultIsZero()
{
    var result = MyAddFunction(0, 0);
    Assert.AreEqual(0, result);
}

uint MyAddFunction() => throw new NotImplementedException(); 

The test fails. I threw an exception rather than returning 0. I fix the function:

uint MyAddFunction(uint a, uint b) => 0; 

and my test passes. Great. Now for another test:

[Test]
For1And0_ResultIs1()
{
    var result = MyAddFunction(1, 0);
    Assert.AreEqual(1, result);
}

The test fails, so I modify the function to make both tests pass:

uint MyAddFunction(uint a, uint b) => a == 0 ? 0 : 1; 

And both tests pass. But the code is less than ideal. I want to refactor it to:

uint MyAddFunction(uint a, uint b) => a + b; 

But I have a problem if I do. My tests will still pass, but so will a test that I subsequently add that tests any of the other combinations. We have an example of that "accidental functionality" that you were talking about. How do I write a failing test after performing the refactor?

There are two approaches we can take here. One is really useful during initial development when you arrive at this position. The other is more useful for when you are maintaining or enhancing an existing piece of code.

The first approach uses a technique called recycling TDD. The idea being a simple one. To test those 121 combinations, you do not have to write 121 tests as there is nothing sacrosanct about a test. You are free to change an existing test to cover new functionality. In doing so, it must still fail once more though. In other words, there's no need to write a new failing test; make an existing one fail if that's more useful. So let's change that first test to:

[Test]
ForAllValuesOfXAnd0_ResultIsX([Range(0, 10)]uint x)
{
    var result = MyAddFunction(x, 0);
    Assert.AreEqual(x, result);
}

And it should fail for x of 2-10. Then we make it pass:

uint MyAddFunction(uint a, uint b) => a;  

And finally, change the test once more to what we really want it to be:

[Test]
ForAllValuesOfXAndY_ResultIsXPlusY([Range(0, 10)]uint x, [Range(0, 10)]uint y)
{
    var result = MyAddFunction(x, y);
    Assert.AreEqual(x + y, result);
}

Again the test fails for all values of y save 0. And we can write than function to make it pass:

uint MyAddFunction(uint a, uint b) => a + b;

So we've avoided that accidental functionality, without going insane through writing ever more tests and ever more convoluted code that only passes those tests and nothing else.

For the other approach, let's say our requirements change and we now need to handle 0-11. I'm fairly sure that my existing code will handle that. So I write a test to check:

[Test]
ForAllValuesOfXAnd11_ResultIsXPlus11([Range(0, 10)]uint x)
{
    var result = MyAddFunction(x, 10);
    Assert.AreEqual(x + 10, result);
}

Yes, the test passes. 11 is supported. But hand on, I've not actually tested 11; I tested 10. My test passed, but I didn't test what I meant to test. I broke the red/green rule by not writing a failing test first. But how can I write a failing test when it already supports adding 11? By writing the test to specifically fail on those new values:

[Test]
ForAllValuesOfXAndY_ResultIsXPlusY([Range(0, 11)]uint x, [Range(0, 11)]uint y)
{
    var result = MyAddFunction(x, y);
    Assert.IsTrue(result <= 20);
}

Now I have a test that passes all previous 0-10 tests, but fails for 10+11, 11+10 and 11+11. I've forced a failure for my new cases. And now I can change it to the proper test:

[Test]
ForAllValuesOfXAndY_ResultIsXPlusY([Range(0, 11)]uint x, [Range(0, 11)]uint y)
{
    var result = MyAddFunction(x, y);
    Assert.AreEqual(x + y, result);
}

Part 2: Handling "accidental functionality" in implementation details

In your example, you cite the case of having a hash set under the hood. You may have access to the source for that hash set and you look at it and confirm to yourself that it will indeed always return the elements in the order they were added. The author may even have stated that in the documentation. With that knowledge, you could just accept that your code works as is and all is well.

But what if it's not documented that way and the author changes the algorithm in the next release or a bug is introduced and it doesn't work as documented in the next release? Since you are adding it as a requirement to your code, maybe you should add a test for it?

There's no right answer here. Adding the test is arguably over-engineering and testing 3rd party code rather than your own (which unit tests should avoid). But if it isn't documented other than in the implementation code, a newer version could indeed change things so a unit test could be a useful early warning signal.

If you do decide to test it, don't forget to write a deliberately failing test first though. Think about your test data as you want to avoid repeating values for example and you want to minimise the impact that that accidental functionality has on your testing. So maybe test that get_all().reverse() doesn't return a matching set to get that failing test. Then remove the .reverse() to have the test pass to give you confidence in your new test.

Part 3: Handling apparent accidental functionality due to "happy path testing"

You also cite the example of having a SQL database under the hood. In this case, you might write an integration test that creates a database, writes some data and then reads it back without an ORDER BY and the test passes: we got the results back in the same order. So there's no need to add ordering to your get_all(); it does it already. Or does it?

Let's say you are using a SQL database implementation that I wrote (in my imagination only). Now the way I've implemented things is that I make all rows the same size in the file I store the table in. When a row is deleted, I set a deleted flag on that row. When you do another add, I look for a deleted row and re-use it if possible.

So one day, you add delete to your container class. And folk start complaining that your get-all() doesn't work properly after a delete. Your test for some insert()'s and then a get_all() took the happy path through my SQL implementation and so only appeared to work without that ORDER BY. When the system under the hood is sufficiently complex, you take a big risk by writing a simple unit test and coding around those results. If the SQL docs say that the order isn't guaranteed, play safe and add that ORDER BY.

5

If I understand correctly, your issue is with an implementation that most of the time "accidentally" fulfills the requirement. This is something that is very hard to test. Successful tests only prove that the implementation does the right thing in the specific test case, they cannot prove that it will always behave correctly.

You normally don't reach this situation by deliberately changing the requirements such that a behavior that was formerly an unintended side effect of the implementation becomes a requirement.

In my experience, it is more common that the implementation is slightly buggy, does the right thing most of the time, so tests don't detect the bugs. Such bugs typically appear in production, and after debugging you know what the bug is. Ideally, you have also learned how to provoke the bug in the initial implementation, and you use that knowledge to write a regression test.

Of course you can do the same thing when you elevate an incidental behavior to the status of a requirement. It might be harder to construct a test case that would break the initial implementation if you have no actual incident in which the bug is provoked, but if you know the implementation details you might be able to find a way, for example by forcing a rehash.

But even if you can construct such a regression test, you should be aware that absence of proof of a bug is not proof of absence of bugs.

1

To continue off of what @Hans said, you can't reasonably tests every situation for this ordering issue and it might be buggy on certain situations.

But there is something you can do, you could put an assert in main code to make sure it is "in order", if it is not too expensive. There are certain situations where this is acceptable, e.g. if the list is not "in order" you wanted and that disorder is not an acceptable state for your program to keep running, so throwing an exception would be a good way to find out in prod what list insertion orders don't work, and then you can remedy this. It depends on your requirements and if this is acceptable behavior

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.