Friday, August 14, 2009

Unit testing for C++ "concept"

When you gain the ability to do template generic programming like this:
template<typename T>
class MyClass {
// use T somewhere
};
It falls naturally that you expect T to provide certain functionality. For example, many people write code like this:
template<typename T>
class MyClass {
public:
T Add(T x, T y) { return x + y; };
};
This assumes that T has a well-defined operator+. It might be more precise to write this:
template<class T /* implements Addition */>
class MyClass {
public:
T Add(T x, T y) { return x + y; };
};
where the interface Addition could be specified like this:
template<typename T>
class Addition {
public:
T operator+(T that)();
};
This is to say that the T you use to instantiate MyClass cannot be any type, but only a type that has implemented addition. The concept of addition is not very interesting, so let's use another example.

Let's say you have the concept of a map<K, V> that is an associative map from keys of type K to values of type V. For the sake of testing, you can assume that K is both hashable and comparable (using an integer key will do). Then you are given two implementations of the map<K, V> concept, one implements the binary search tree sorted by K, and one implements hash table hashed by K. Most of the tests you want to do have to do with the concept of map<K, V> itself, e.g. insert, replace, find, and remove; not to do with the particular way the map is implemented. How do you avoid duplication? Use Type-Parameterized Tests.

However, here is a tricky bit. A concept does not describe how a class is constructed or destroyed, only that the class implements certain methods. What if the class does not have a default constructor? For example, the hash table requires an initial size. Most implementations of a hash table supplies a "good enough" default value for the default constructor, but there are cases where this is not applicable.

I figured out that you could parameterize the test using a factory class instead, and the factory would act like a default constructor. This is illustrated here.

However, this is not as straightforward as I would like because when a template class inherit from the base class which is also a template, the derived class does not have access to any of the protected variables! This is illustrated here. This code compiles, but if you replace the self->x_ and self->y_ references with simply x_ and y_, gcc would fail to compile.

Update: apparently gcc is correct, and the workaround is to simply prefix the member access with "this->."

No comments: