On 8/14/14, 6:20 PM, Idan Arye wrote:
> At any rate, random is bad for unit testing. Unit tests need to be
> deterministic, because when a unit test fails you want to debug it to
> see what's wrong.

Just publish the seed upon failure. It's a classic technique. -- Andrei

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.

On 8/14/14, 7:46 PM, H. S. Teoh via Digitalmars-d wrote:
> 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 all integrals converting some value to a string and back should yield the same value.

Accelerated searches in any sorted ranges should provide the same result as linear searches.

Sorting should provide sorted results.

...


Andrei

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.

On 15/08/14 04:46, H. S. Teoh via Digitalmars-d wrote:

> 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? */);
> 	}

I don't know if this is how Andrei is thinking but it might be useful:

1. Instantiate "shortestPath" with random values of random types and assert that the instantiation succeeds

2. Then call "shortestPath" with known values of various types to validate that the algorithm is correct

-- 
/Jacob Carlborg

On 14/08/2014 17:14, Nick Treleaven wrote:
> I think it's not possible to have a documented unittest for a method
> that isn't part of the parent template. This is necessary to prevent
> template instantiation recursion sometimes.

Oops, my example wasn't recursive, I meant where the unittest has some local aggregate type defined:

struct S(T)
{
    void foo(){}

    ///
    unittest
    {
        class C {}
        S!C s;	// recursive template expansion
        s.foo();
    }
}

unittest
{
    S!int s;
}