3

How does one even approach testing an abstract data type?

I mean, besides the normal (supposed) way of doing unit tests, where you mock the collaborators, feed them in the class to test, together with sample data, and call the public methods, verifying that the output is the expected one, how do you ensure that the internals are what you want?

Let's take an example : let's say I want to implement my own PriorityQueue, but I want to use a Heap as internal representation and even further, an array for the Heap part.

The normal way to test would be to check the public methods in different scenarios, the methods being : push, pop, peek.

This does not give any guarantees on the performance of the algorithm used internally. I could and should bother make some "scenarios" to check the performance, but these are useful after I have implemented my thing and they are mostly for collecting metrics.

So, how do I test the internal parts? Or better said, how do I ensure that the internal representation uses the algorithm I want.

I know that I will have several levels on internals if I go with the "heap" implementation (these are everywhere on the Internet for implementations of PriorityQueues) :

1. calculating the left-child, right-child, parent for a node ; I could extract these in a separate class and test that. Or I could just make them protected and test them in the PriorityQueue class, but this break encapsulation because the tests look into the state of the class to test

2. shiftUp and shiftDown ; same issues as for the one in point 1., except now I can make them receive the object that represents the internal state, or use the private field direct, in case of an Object-oriented language. So, protected or in another entity?

3. the internal representation is a array, so I could have a toArray() method that is public and test that. Testing the output of this can even "save" me from testing the previous two points, but again, the internal state is exposed to the outside world. Do I really want to do that?

The questions here are :

  • do you separate the code into more pieces? when do you stop with the granularity?
  • how much do I sacrifice from KISS in order to have some unit tests? I want the things simple and could have most of the things in the same class and even methods to use the internal fields directly (in case of OO)
  • are there other "suggestions", other ways to ensure both the functionality of the data structure and the algorithm used ?
Belun
  • 1,314
  • 8
  • 15
  • If you're working in Java, you can invoke (and test) private methods in your unit tests using Powermock. – FrustratedWithFormsDesigner Jan 11 '17 at 15:39
  • i take it that by "data structure" you mean a tree like document object model with various methods which modify the document? – Ewan Jan 11 '17 at 15:39
  • use protected method (final if you really want them to not be overrided) and make a child test class ? Otherwise you can without any framework invoke change the visibility of methods and invoke them using reflection. – Walfrat Jan 11 '17 at 15:41
  • 1
    I took the freedom and changed the title to make it match your actual question. However, I am pretty sure I can find a duplicate one (not the one mentioned by svidgen, that is IMHO not a dupe). – Doc Brown Jan 11 '17 at 15:41
  • 4
    @Walfrat: I don't think so, the core point here is the OP wants to test something with very complex internals, having only a few public methods, but he really dislikes to expose the internals and break encapsulation. So it is more a question of the type "how do I test private methods", which have been asked in different variations here on SE very often. – Doc Brown Jan 11 '17 at 15:48
  • 2
    Possible duplicate of [Do unit tests sometimes break encapsulation?](http://softwareengineering.stackexchange.com/questions/170740/do-unit-tests-sometimes-break-encapsulation) – Doc Brown Jan 11 '17 at 15:50
  • 2
    Create a public method that checks your invariants, then have your unit tests call that between each atomic operation. That can check functionality, though not performance. – DylanSp Jan 11 '17 at 16:00
  • @DylanSp This might be a good answer if you expand a bit. – Frank Hileman Jan 12 '17 at 17:04
  • @DylanSp there are already public methods, but those do not reveal anything about the implementation of the ADS. there could be a toArray() but can potentially reveal some internal. should i create an ArrayCompleteHeap and then have the excuse to check the internal array? :) – Belun Jan 12 '17 at 17:09

2 Answers2

4

Tests are just plain bad at enforcing that a class is implemented in exactly the way you want it. What tests are good at is verifying that the visible behavior of a class (or other unit) matches the expectations, but a good test doesn't care how the class achieves that.

If you want to ensure that your PriorityQueue class gets implemented using a Heap which itself is based on an array, then the most effective way of ensuring that is to perform consistent code reviews for all changes that are being made.
The reason for this is that design changes that don't affect the outcome of the algorithm are very hard to detect with test cases, but they can be spotted very easily by a human reader.

Bart van Ingen Schenau
  • 71,712
  • 20
  • 110
  • 179
2

If some logging can add to the software under test, then internal attributes (e.g. time, space, structure, etc) could be published that the test code could inspect after putting the object through its paces. With common logging frameworks, the data can by passed through a dedicated logger that would not be apparent if the software under test was published, and filtered to have a low-impact on running performance.

However, this brings up the question of how much testing should be tied to the particulars of an implementation rather than the behaviour at the published interface. The maintenance of test code can take a significant cost. By focusing testing on the behaviour of the PriorityQueue, its implementer may later optimise the code without any change to the test code. Therefore, if testing the implementation is required, I suggest separating the implementation tests from the behavioural tests so that the former can be skipped to help manage the testing effort.

Steve Palmer
  • 21
  • 1