unittesting generic functions

[H. S. Teoh via Digitalmars-d]

On Thu, Aug 14, 2014 at 05:49:39PM -0700, Andrei Alexandrescu via Digitalmars-d wrote:
> On 8/14/14, 3:34 PM, H. S. Teoh via Digitalmars-d wrote:
> >How does this relate to writing generic unittests? Since the incoming
> >types are generic, you can't assume anything about them beyond what
> >the function itself already assumes, so how would the unittest test
> >anything beyond what the function already does?
> 
> Check the workings of the function via an alternate algorithm for
> example.  There's plenty of examples, including unittests inside a
> parameterized struct/class test methods within that class.

Can you give a concrete example?


> >For example, if the function performs x+y on two generic arguments x
> >and y, how would a generic unittest check whether the result is
> >correct, since you can't assume anything about the concrete values of
> >x and y?  The only way the unittest can check the result is to see if
> >it equals x+y, which defeats the purpose because it's tautological
> >with what the function already does, and therefore proves nothing at
> >all.
> 
> We could ask the same question about x+y for int in particular: it's a
> primitive so there's not much to test.

That's not the point. I used x+y just as an example. You can substitute
that with an arbitrarily complex computation, and the question stands:
how would the unittest determine what's the correct result, without
basically reimplementing the entire function?


> This does bring up the interesting point that we need a way to
> generate random values of generic types.
> http://www.haskell.org/haskellwiki/Introduction_to_QuickCheck1 comes
> to mind.
[...]

I agree that's a cool thing to have, but that still doesn't address the
core issue, that is, given a generic type T, of which you have no
further information about how its concrete values might behave, 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?

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?  Even if the answers match, all you've
proven is that the two algorithms are equivalent -- they could *both* be
wrong in the same places (e.g., they could both return an empty path),
but you'd never know that.

(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.

(c) Maybe the unittest's implementation of shortest path is wrong but
shortestPath is actually correct. How do you tell the difference? Keep
in mind that g is a *random*, *arbitrary* instance of G, and when the
unittest runs we know *nothing* about it other than the fact that it's
some random instance of G.

Basically, I can't think of any sane way to write a generic test that
would give meaningful results for *arbitrary* instances of G, about
which the unittest code has no further information other than it's some
random instance of G.

Due to this, I contend that you need to use *concrete* inputs and check
for *concrete* outputs in order for the unittest to be of any value at
all.  Examples to the contrary are more than welcome -- if you can come
up with one.


T

-- 
Frank disagreement binds closer than feigned agreement.