On Thu, Mar 14, 2013 at 06:09:26PM +0100, Andrej Mitrovic wrote:
> On 3/14/13, bearophile <bearophileHUGS@lycos.com> wrote:
> > This is an invalid argument. You can say the same thing for many (most?) tests done by the compiler. Unit tests can't be sure to verify all code paths inside a function or template.
> 
> No, it must do exactly that. If you have so many paths that you can't reasonably test all paths then your template or function is too complicated to begin with. The benefit here of D over C++ is that unit testing is cheap and doesn't require external libraries.
[...]

I think you're missing the point. The point is that concepts allow the compiler to deduce template correctness *without* instantiating it with every possible combination of types.

Right now, we *don't* have concepts, and therefore the only way to ensure template correctness is to iterate over the exponential number of combinations of template arguments. But if we *had* concepts, then the compiler could reason about code correctness without needing to explicitly check every instantiation -- thus effectively covering all possible combinations, but without actually doing it. It's the difference between proving a boolean statement is tautologous by reducing it to true using known logic identities, vs. looping over every combination of variable assignments and checking that they all evaluate to true.


T

-- 
Кто везде - тот нигде.

14-Mar-2013 22:13, H. S. Teoh пишет:
> On Thu, Mar 14, 2013 at 06:09:26PM +0100, Andrej Mitrovic wrote:
>> On 3/14/13, bearophile <bearophileHUGS@lycos.com> wrote:
>>> This is an invalid argument. You can say the same thing for many
>>> (most?) tests done by the compiler. Unit tests can't be sure to
>>> verify all code paths inside a function or template.
>>
>> No, it must do exactly that. If you have so many paths that you can't
>> reasonably test all paths then your template or function is too
>> complicated to begin with. The benefit here of D over C++ is that unit
>> testing is cheap and doesn't require external libraries.
> [...]
>
> I think you're missing the point. The point is that concepts allow the
> compiler to deduce template correctness *without* instantiating it with
> every possible combination of types.
>
> Right now, we *don't* have concepts, and therefore the only way to
> ensure template correctness is to iterate over the exponential number of
> combinations of template arguments.

And if you create a library tool to try out all sensible combinations would that work for this use case of concepts?

In essence you transform concept to some specification and feed it into a CTFE-able generatopr function. Then take the code out and apply mixin it put into a unittest.

Sounds easy (if only DMD doesn't run out of memory in the process).



-- 
Dmitry Olshansky

On Thu, Mar 14, 2013 at 07:00:47PM +0100, Dicebot wrote:
> On Thursday, 14 March 2013 at 17:26:18 UTC, Andrei Alexandrescu wrote:
> >Walter has measured coverage of Phobos unittests a couple of times, it's very high. But I agree it would be nice to have it as a target.
> >
> >Andrei

Beware the fallacy that 100% line coverage of a template == 100% coverage of correctness in *every possible instantiation*.

Just because template X has 100% line coverage for !(int,int) does not
necessarily mean it will work for !(int,string), for example. Or
!(int,const(int)). Or !(const(int),int). Or any number of subtle but
sometimes important combinations.


> Sarcasm aside, this brought me to an idea for utilities for template fuzzy testing  to check some instantiation combinations. Which is much more useful than plain line coverage check in case of templates. I have submitted pull request only a few weeks ago that fixed std.traits bug where template has failed to instantiate for function types (but not other types) despite 100% line coverage by unit test. It could have been checked automagically.
> 
> Not sure what usage interface may be though.

I've written code like this before, though it definitely can use some refinement:

	struct MySet(ElemType) { ... }
	unittest {
		void test(T)(T sampleArgs) {
			auto set = MySet!T(sampleArgs);
			assert( ... /* test for MySet behaviour here */);
		}
		void testNumArray(T, U...)() {
			T[] data = [1,2,3,4,5];
			test(data);
			testNumArray!(U);
		}
		void testCharArray(T, U...)() {
			T[] data = "abc";
			test(data);
			testCharArray!(U);
		}

		testNumArray!(byte, ubyte, int, uint, long, ulong)();
		testCharArray!(char, wchar, dchar, const(char),
			const(wchar), const(dchar), immutable(char),
			immutable(wchar), immutable(dchar))();

		// Coverage is still not really complete; we'd need to
		// add struct and class, and nested arrays, etc..
	}

The fact that D actually lets you do this, is quite awesome.


T

-- 
He who laughs last thinks slowest.

On 3/14/13 1:58 PM, Nick Sabalausky wrote:
> On Thu, 14 Mar 2013 12:48:28 -0400
> Andrei Alexandrescu<SeeWebsiteForEmail@erdani.org>  wrote:
>> On 3/14/13 11:50 AM, deadalnix wrote:
>>> This is usualy much better to have the compiler smash your mistake
>>> right into your face than discovering with a unittest much latter.
>>
>> I don't think so.
>
>
> On Thu, 14 Mar 2013 12:49:01 -0400
> Andrei Alexandrescu<SeeWebsiteForEmail@erdani.org>  wrote:
>> On 3/14/13 12:32 PM, bearophile wrote:
>>>
>>> This is an invalid argument. You can say the same thing for many
>>> (most?) tests done by the compiler.
>>
>> No, this is different.
>>
>
> Man:    An argument is a connected series of statements intended to
> establish a proposition.
> Andrei: No it isn't.
> Man:    Yes it is! It's not just contradiction.
> Andrei: Look, if I argue with you, I must take up a contrary position.
> Man:    Yes, but that's not just saying 'No it isn't.'
> Andrei: Yes it is!
> Man:    No it isn't!
> Andrei: Yes it is!
> Man:    Argument is an intellectual process. Contradiction is just the
> automatic gainsaying of any statement the other person makes.
> (short pause)
> Andrei: No it isn't.
>
>

No.

Andrei

On 3/14/13 2:07 PM, Dicebot wrote:
> On Thursday, 14 March 2013 at 17:51:23 UTC, Andrei Alexandrescu wrote:
>> If you found a few, that would be great. I don't think you'll have an
>> easy time.
>>
>> Andrei
>
> In other comment I have mentioned a case I have fixed just 15 days ago:
> https://github.com/D-Programming-Language/phobos/pull/1182
> 100% line coverage, compile-time error for certain type parameter
> subset. Could have been found by compiler / clever-enough framework.
>
> That was easy.

1 < a few

Andrei

On Thu, Mar 14, 2013 at 10:20:04PM +0400, Dmitry Olshansky wrote:
> 14-Mar-2013 22:13, H. S. Teoh пишет:
> >On Thu, Mar 14, 2013 at 06:09:26PM +0100, Andrej Mitrovic wrote:
> >>On 3/14/13, bearophile <bearophileHUGS@lycos.com> wrote:
> >>>This is an invalid argument. You can say the same thing for many (most?) tests done by the compiler. Unit tests can't be sure to verify all code paths inside a function or template.
> >>
> >>No, it must do exactly that. If you have so many paths that you can't reasonably test all paths then your template or function is too complicated to begin with. The benefit here of D over C++ is that unit testing is cheap and doesn't require external libraries.
> >[...]
> >
> >I think you're missing the point. The point is that concepts allow the compiler to deduce template correctness *without* instantiating it with every possible combination of types.
> >
> >Right now, we *don't* have concepts, and therefore the only way to ensure template correctness is to iterate over the exponential number of combinations of template arguments.
> 
> And if you create a library tool to try out all sensible combinations would that work for this use case of concepts?
> 
> In essence you transform concept to some specification and feed it into a CTFE-able generatopr function. Then take the code out and apply mixin it put into a unittest.
> 
> Sounds easy (if only DMD doesn't run out of memory in the process).
[...]

It's certainly possible, I think. Is it worth pursuing? Maybe. Here's a first crack at it:

We'd need some way of listing (or generating a list of) all representative template arguments, say for example, a listing that includes input range, forward range, bidirectional range, etc.. Then we need a way to generically generate non-trivial instances of these ranges (otherwise the unittest could only cover trivial instances, like empty input range, empty forward range, etc., so the template being tested will not be verified for non-empty ranges!). The result then will be used to instantiate the template and run it through a battery of tests.

Of course, the ranges themselves have arguments, so you'd need some kind of listing of representative types: char, int, float, string, etc., and have a way of generating non-trivial instances of each of these types, then use them to instantiate the range with. Maybe for each type also test it for const(T), immutable(T), etc..

Then you'd have to cover nested ranges, so you'd need a way to specify how deep you want to go (e.g., a recent forward range bug of using = instead of .save will only manifest itself if you had a nested range of forward ranges -- you couldn't catch that just by running through non-nested ranges).

As you can see, this quickly explodes in exponential number of combinations. So ultimately, maybe we still have to resort to hand-picked "representative" types.

But we can do better than the current ad-hoc scheme of writing unittests for whatever combination just occurred to the code writer (which usually misses a lot of corner cases). We should have a std.unittest module that contains lists of all numeric types (byte, int, long, float, double, real, etc.) with their respective non-trivial instances, as well as representative range types: {arrays, struct ranges, class ranges} x {input, forward, bidirection, ...}, along with non-trivial instances of them. Then provide some generic testing functions that iterate over each of these lists, that user-written unittests can call to instantiate and test their templates with.

There can also be a way of adding custom types to the lists, that the generic functions can pick up and include in their combinations to test.

But the important thing is to collect these type lists in a single place, so that we can, for example, test std.algorithm functions that expect input ranges with *all* ranges in the input range list, and be reasonably certain that if it all passes, the chances for any more bugs are very slim. (Otherwise, std.algorithm.joiner may have good coverage but std.algorithm.cartesianProduct may have poor coverage, and there's lots of missed reuse opportunities for the test ranges used by the unittests.)


T

-- 
Trying to define yourself is like trying to bite your own teeth. -- Alan Watts

On Thu, Mar 14, 2013 at 02:54:17PM -0400, Andrei Alexandrescu wrote:
> On 3/14/13 2:07 PM, Dicebot wrote:
> >On Thursday, 14 March 2013 at 17:51:23 UTC, Andrei Alexandrescu wrote:
> >>If you found a few, that would be great. I don't think you'll have an easy time.
> >>
> >>Andrei
> >
> >In other comment I have mentioned a case I have fixed just 15 days ago: https://github.com/D-Programming-Language/phobos/pull/1182 100% line coverage, compile-time error for certain type parameter subset. Could have been found by compiler / clever-enough framework.
> >
> >That was easy.
> 
> 1 < a few
[...]

I found (and fixed!) a number of missed combinations in std.algorithm:
transient ranges, joiner() not using .save on forward ranges, same bug
in transposed(), transposed crashing on jagged range of ranges, etc..

Given that some of this code is rather old before I touched them, I'm forced to believe that many more such bugs lurk in Phobos that nobody has found yet. Or they found it but just evaded it by rewriting some user code -- I've found myself doing that on several occasions, because I was trying to get my own code done and didn't want to spend another 4 hours' digression to find where the bug in Phobos is. Sometimes I don't even file bugs because it takes time to reduce the test case and it's distracting from the task at hand.

So no, it's not just 1. They are there, and there are more than 1 of them, if you'd only look. I don't think denying this is helpful to improving Phobos' quality.


T

-- 
Without geometry, life would be pointless. -- VS

On 3/14/13 3:04 PM, H. S. Teoh wrote:
> I found (and fixed!) a number of missed combinations in std.algorithm:
> transient ranges, joiner() not using .save on forward ranges, same bug
> in transposed(), transposed crashing on jagged range of ranges, etc..

I think you're right but only in part; there may be a bit of a confusion. There's pure semantic checking such as forgetting to use .save that can't be detected statically. Then there's code that e.g. should work for forward ranges but has only been tested with arrays.

My question was referring to code that has sheer typos that are mechanically detected, which are present in code that has never ever been instantiated. I do recall we found a few, but I think that illustrates a problem with the process, not the language.


Andrei

Andrei Alexandrescu:

> A concept system would have helped me there if my intent was to ship Kahan summation without ever testing it. That's not an intent we want to cater for!

I think Issue 9715 isn't about Concepts.

- - - - -

Regarding the more general topic of Concepts (and their almost equivalent Typeclasses (http://dotat.at/tmp/p37-bernardy.pdf ) of the Rust language, or more powerful in Haskell), the argument you are proposing is exactly the same used by dynamic language proponents against static typing.

A difference is that adding a static type system to Ruby causes much larger changes compared to adding typeclasses to Rust (Rust didn't have typeclasses since recently. Rust used to have templates similar to C++, with some restrictions).

Haskell programmers have typeclasses, yet unit testing is done in Haskell, they have even invented a testing idea that was widely copied (QuickCheck).

Types (like ones of Typeclasses and Concepts) help avoid catch some bugs and shape your style of coding, the unittests avoid the other bugs and shape your coding, and contract programming catches other bugs and they too shape the way you code, for the better.

In the last Haskell version they have introduced a static type system at level of kinds, and it helps avoid some other bugs, or to catch them earlier.

For a Haskell programmer the great and numerous advantages of Concepts/Typeclasses are not in discussion. I think Rust programmers are now learning to appreciate them.

Bye,
bearophile

14-Mar-2013 22:55, H. S. Teoh пишет:
> On Thu, Mar 14, 2013 at 10:20:04PM +0400, Dmitry Olshansky wrote:
>> 14-Mar-2013 22:13, H. S. Teoh пишет:
>>> On Thu, Mar 14, 2013 at 06:09:26PM +0100, Andrej Mitrovic wrote:
>>>> On 3/14/13, bearophile <bearophileHUGS@lycos.com> wrote:
>>>>> This is an invalid argument. You can say the same thing for many
>>>>> (most?) tests done by the compiler. Unit tests can't be sure to
>>>>> verify all code paths inside a function or template.
>>>>
>>>> No, it must do exactly that. If you have so many paths that you
>>>> can't reasonably test all paths then your template or function is
>>>> too complicated to begin with. The benefit here of D over C++ is
>>>> that unit testing is cheap and doesn't require external libraries.
>>> [...]
>>>
>>> I think you're missing the point. The point is that concepts allow
>>> the compiler to deduce template correctness *without* instantiating
>>> it with every possible combination of types.
>>>
>>> Right now, we *don't* have concepts, and therefore the only way to
>>> ensure template correctness is to iterate over the exponential number
>>> of combinations of template arguments.
>>
>> And if you create a library tool to try out all sensible
>> combinations would that work for this use case of concepts?
>>
>> In essence you transform concept to some specification and feed it
>> into a CTFE-able generatopr function. Then take the code out and
>> apply mixin it put into a unittest.
>>
>> Sounds easy (if only DMD doesn't run out of memory in the process).
> [...]
>
> It's certainly possible, I think. Is it worth pursuing? Maybe.

It is as this won't require arguing with Walter, Andrei et al. and the other wopuld either use it or not but you both ways you'd have hard data.

> Here's a
> first crack at it:
>
> We'd need some way of listing (or generating a list of) all
> representative template arguments, say for example, a listing that
> includes input range, forward range, bidirectional range, etc.. Then we
> need a way to generically generate non-trivial instances of these ranges
> (otherwise the unittest could only cover trivial instances, like empty
> input range, empty forward range, etc., so the template being tested
> will not be verified for non-empty ranges!). The result then will be
> used to instantiate the template and run it through a battery of tests.
>
> Of course, the ranges themselves have arguments, so you'd need some kind
> of listing of representative types: char, int, float, string, etc., and
> have a way of generating non-trivial instances of each of these types,
> then use them to instantiate the range with. Maybe for each type also
> test it for const(T), immutable(T), etc..
>
> Then you'd have to cover nested ranges, so you'd need a way to specify
> how deep you want to go (e.g., a recent forward range bug of using =
> instead of .save will only manifest itself if you had a nested range of
> forward ranges -- you couldn't catch that just by running through
> non-nested ranges).
>
> As you can see, this quickly explodes in exponential number of
> combinations. So ultimately, maybe we still have to resort to
> hand-picked "representative" types.

No - just use some language (DSL!) for the specification instead of generating type-strings. Basically exactly the same thing you'd put into a concept if it was langauge feature.

You'd have a spec written in this language per each concept: input range of type X, an infinite range of type Y, an output range for E, etc. Spec states unit tests (and not only) for any type satisfying a concept. The concept (spec) itself is parametrize on types and/or other concepts.

Then your tests are kind of monte carlo - pick random (large number) X of full spectrum (infinite on types, but finite on meta-types) of type combinations that this template supports and run the generated unit tests for these.

That pick (following the spec) should cover all of the rules in the concept. The types themselves should include dummies generated based on the spec and some real world stuff (predefined).

>
> But we can do better than the current ad-hoc scheme of writing unittests
> for whatever combination just occurred to the code writer (which usually
> misses a lot of corner cases). We should have a std.unittest module that
> contains lists of all numeric types (byte, int, long, float, double,
> real, etc.) with their respective non-trivial instances, as well as
> representative range types: {arrays, struct ranges, class ranges} x
> {input, forward, bidirection, ...}, along with non-trivial instances of
> them. Then provide some generic testing functions that iterate over each
> of these lists, that user-written unittests can call to instantiate and
> test their templates with.
>

Exactly. But I'd call for more high-callibre module as in std.testing.spec.

> There can also be a way of adding custom types to the lists, that the
> generic functions can pick up and include in their combinations to test.

> But the important thing is to collect these type lists in a single
> place, so that we can, for example, test std.algorithm functions that
> expect input ranges with *all* ranges in the input range list, and be
> reasonably certain that if it all passes, the chances for any more bugs
> are very slim. (Otherwise, std.algorithm.joiner may have good coverage
> but std.algorithm.cartesianProduct may have poor coverage, and there's
> lots of missed reuse opportunities for the test ranges used by the
> unittests.)
>

That would be a huge step forward but it's like collecting sets of strings and use their concatenation to define a required set of strings. Instead you could use a formal grammar and define much broader kinds of sets with less "lines"/"rules" (like even regular grammar does).


-- 
Dmitry Olshansky