unittesting generic functions

[xenon325 via Digitalmars-d]

On Friday, 15 August 2014 at 02:48:18 UTC, H. S. Teoh via 
Digitalmars-d wrote:
> how do
> you write a unittest that checks whether some generic 
> computation
> involving T produces the correct result? Even if I hand you 
> some random
> instance of T, let's call it x, and you're trying to unittest a 
> function
> f, how does the unittest know what the *correct* value of f(x) 
> ought to
> be?

You can check some properties like `f(x) < f(x+1)`.

> Let's use a concrete example. Suppose I'm implementing a 
> shortestPath
> algorithm that takes an arbitrary graph type G:
>
> 	path!G shortestPath(G)(G graph)
> 		if (isGraph!G)
> 	{
> 		... // fancy algorithm here
> 		return path(result);
> 	}
>
> Now let's write a generic unittest:
>
> 	unittest
> 	{
> 		// Let's test shortestPath on some random instance of G:
> 		auto g = G.random; // suppose this exists
> 		auto p = shortestPath(g);
>
> 		// OK, now what? How do we know p is the shortest
> 		// path of the random graph instance g?
> 		assert(p == ... /* what goes here? */);
> 	}
>
> The only possibilities I can think of, that work, is to either 
> (1) check
> if p == shortestPath(g), which is useless because it proves 
> nothing; or
> (2) implement a different shortest path algorithm and check the 
> answer
> against that, which suffers from numerous problems:
>
> (a) How do we know this second shortest path algorithm, used by 
> the
> unittest, is correct? Why, by unittesting it, of course, with a 
> generic
> unittest, and checking the result against ... um... the original
> shortestPath implementation?

you can resort to inefficient but trivial algorithms in unit 
tests, e.g. brute force.

> (b) There might be multiple shortest paths in g, and the second
> algorithm might return a different (but still correct) shortest 
> path.
> So just because the answers don't match, doesn't prove that the 
> original
> algorithm is wrong.

still it could be possible to verify some invariants:
assert(fast_path.length == simple_path.length);


So, one can use generic unittests to verify the most, umm... 
generic properties of algorithms and complement them with tests 
for concrete types.