Unit testing not a good fit for exhaustiveness

So I implemented a layered memory allocator from scratch, somewhat in the fashion of Hoard (mine has a different abstraction). My allocator heavily uses C++ Mixin and Curiously Recurring Template Pattern (CRTP). Mixin is an overloaded term, but the concept I'm citing here is a class whose superclass is a template parameter. This allows a limited form of aspect-oriented programming where the Mixin is an added aspect of an existing class. CRPT is a recursive use of Mixin, which coerces the inheritance hierarchy of the user and the Mixin to form one class. The result allows static dispatch of methods which would otherwise have to be declared virtual, and subsequently dispatched dynamically using a virtual table.

Anyway, long story short. After creating many composable layers of memory allocator, I also created corresponding unit test for each layer. However, the unit tests only covered the best case scenario, that Alloc() never returns NULL. It worked well. But I also wanted to test the case where some allocation returns NULL, in order to tell if the layer handled NULL pointer propagation correctly. This unit test scenario turns out to be much of a nuisance.

To briefly explain why, no allocator always deterministically returns a valid pointer, nor does it always deterministically returns NULL, and it's the handling of the non-determinism that matters. Constructing a mock allocator that always returns NULL would still bypass some code paths. To make sure we traverse all code paths, we would have to construct an allocator that returns NULL after n successes for an arbitrary n, and run the unit tests for n = 1, 2, ... and so on. It may never exhaust all possibilities for a complex allocator layer such as the free list allocator. But then, what about a code path that is not reached unless the allocator succeeds every 2 attempts, or one that succeeds every 3 attempts, and so on?

NULL pointer is a special form of the 'a option datatype in ML. The concept is really simple. The 'a option datatype has two constructors, SOME which carries an item of type 'a, and NONE which doesn't carry an item. When a pointer is not NULL, it is assumed that it refers to a valid object, hence corresponds to SOME; when a pointer is NULL, it is assumed that no such object exists (typically due to an exception), hence corresponds to NONE. When you pattern match against the constructors of a datatype, ML also performs exhaustive analysis. Forgetting to check for NULL is a kind of non-exhaustive pattern matching. Since exhaustiveness is a local property, using unit test (which tests for a property that is much wider in scope) is overkill and ineffective. It is very hard to create a unit test that will run all possible execution paths, especially for the error handling code, because simulating all possible combinations of error condition is impractical.

Although a lot of times it's easier to write unit test for operations that are in-spec (e.g. to make sure a sorting algorithm permutes the sequence in order), it is best to leave exhaustive analysis to a compiler, like ATS, which effectively deals with out-of-spec situations.