Suppose you create a range: struct MyRange{...}

Now you have to unittest it. And there's a lot of ways a range implementation can go wrong. There's a fair amount of things to test. And they all, ideally, need to be done for *every* range type created.

But, ranges are all supposed to conform to a standard interface with standardized semantics. So can't most of this testing be generalized into a generic InputRangeTester, RandomAccessRageTester, etc? All you'd do is feed it an array of elements to test with, and, in theory, it should be able to unittest the range's semantics for conformance.

Obviously it couldn't guarantee 100% conformance, because no unittest can do that, but it seems reasonable that it could be just as good as a well-designed set of hand-written tests.

I think this would be an enormously useful thing to have in Phobos. Can any Phobos/range gurus say fur sure how feasible this is? Does Phobos perhaps already do something similar internally that could just be generalized?

(This message has been brought to you by three random access ranges I
just created but really, really don't feel like unittesting ;) )

On Thursday, March 21, 2013 13:08:58 Nick Sabalausky wrote:
> Suppose you create a range: struct MyRange{...}
> 
> Now you have to unittest it. And there's a lot of ways a range implementation can go wrong. There's a fair amount of things to test. And they all, ideally, need to be done for *every* range type created.
> 
> But, ranges are all supposed to conform to a standard interface with standardized semantics. So can't most of this testing be generalized into a generic InputRangeTester, RandomAccessRageTester, etc? All you'd do is feed it an array of elements to test with, and, in theory, it should be able to unittest the range's semantics for conformance.
> 
> Obviously it couldn't guarantee 100% conformance, because no unittest can do that, but it seems reasonable that it could be just as good as a well-designed set of hand-written tests.
> 
> I think this would be an enormously useful thing to have in Phobos. Can any Phobos/range gurus say fur sure how feasible this is? Does Phobos perhaps already do something similar internally that could just be generalized?
> 
> (This message has been brought to you by three random access ranges I
> just created but really, really don't feel like unittesting ;) )

Hmmm. I've been working on stuff which makes creating ranges to test range- based functions easier, but I've never thought about creating something to test conformance. If I need something like that I just use static asserts to test isInputRange, isForwardRange, etc. and make sure that each of the ones that are supposed to pass for that range do and that those that aren't supposed to pass don't. All that that's going to test though is the API, not behavior. But I don't know how you'd automate testing behavior when the exact behavior of the range is very much dependent on the range itself. In most cases though, you end up with a new range type, because it's being returned from a range-based function, in which case, simply unit testing the function with a variety of range types generally takes care of it, and those aren't particularly automatable, because what the tests need to test depends entirely on what the function is supposed to do.

- Jonathan M Davis

On Thu, 21 Mar 2013 13:29:35 -0400
"Jonathan M Davis" <jmdavisProg@gmx.com> wrote:
> 
> But I don't
> know how you'd automate testing behavior when the exact behavior of
> the range is very much dependent on the range itself.

I don't think that's true at all. Granted, you can't automate testing of the range's internal state, but there's a lot about the external behavior which is very strictly defined:

Examples:
- Multiple calls to front return the same element.
- Calling popFront and then front returns the next element.
- If range has length, then 'empty' returns true IFF popFront has been
  called at least 'myRange.length' times.
- Calling popFront doesn't throw unless range is empty.
- Calling popFront on an empty range throws a RangeError.
- Upon instantiating a new random access range, 'r.front == r[0]', and
  then after 'r.popFront()', 'r.front == r[1]', etc.
- 'r.save.front == r.front'. And then call popFront on both ranges, and
  'r1.front == r2.front' is still true.
- Iterating via back/popBack yields the same elements as
  front/popFront, but in reverse order.

And I'm sure there's a whole bunch more.

If you give a hypothetical generic range-testing tool both an instantiated range to be tested and an array of all the elements you expect to be in the range, in the same order, then I'd think all of the above and more should be testable.

On Thu, 21 Mar 2013 13:48:54 -0400
Nick Sabalausky <SeeWebsiteToContactMe@semitwist.com> wrote:
> - Calling popFront doesn't throw unless range is empty.
> - Calling popFront on an empty range throws a RangeError.

Actually, I'm not certain about those two, but I know they're true if you just s/popFront/front/

21-Mar-2013 21:48, Nick Sabalausky пишет:
> On Thu, 21 Mar 2013 13:29:35 -0400
> "Jonathan M Davis" <jmdavisProg@gmx.com> wrote:
>>
>> But I don't
>> know how you'd automate testing behavior when the exact behavior of
>> the range is very much dependent on the range itself.
>
> I don't think that's true at all. Granted, you can't automate testing
> of the range's internal state, but there's a lot about the external
> behavior which is very strictly defined:
>
> Examples:
> - Multiple calls to front return the same element.
> - Calling popFront and then front returns the next element.
> - If range has length, then 'empty' returns true IFF popFront has been
>    called at least 'myRange.length' times.
> - Calling popFront doesn't throw unless range is empty.
> - Calling popFront on an empty range throws a RangeError.
> - Upon instantiating a new random access range, 'r.front == r[0]', and
>    then after 'r.popFront()', 'r.front == r[1]', etc.
> - 'r.save.front == r.front'. And then call popFront on both ranges, and
>    'r1.front == r2.front' is still true.
> - Iterating via back/popBack yields the same elements as
>    front/popFront, but in reverse order.
>
> And I'm sure there's a whole bunch more.
>
> If you give a hypothetical generic range-testing tool both an
> instantiated range to be tested and an array of all the elements you
> expect to be in the range, in the same order, then I'd think all of the
> above and more should be testable.
>

Indeed there is a host of invariants that must hold for any range of certain kind. I'd say this along with other stuff should go into std.test or std.testing (or package within) etc.

-- 
Dmitry Olshansky

On Thu, Mar 21, 2013 at 01:48:54PM -0400, Nick Sabalausky wrote:
> On Thu, 21 Mar 2013 13:29:35 -0400
> "Jonathan M Davis" <jmdavisProg@gmx.com> wrote:
> > 
> > But I don't know how you'd automate testing behavior when the exact behavior of the range is very much dependent on the range itself.
> 
> I don't think that's true at all. Granted, you can't automate testing of the range's internal state, but there's a lot about the external behavior which is very strictly defined:
> 
> Examples:
> - Multiple calls to front return the same element.

This is easy to test.


> - Calling popFront and then front returns the next element.

How do you know if something is the "next element"? What if the range is
repeat(1)?


> - If range has length, then 'empty' returns true IFF popFront has been
>   called at least 'myRange.length' times.

This should also be easy to test. But it requires the ability to instantiate the range with some given number of elements. So you still need a range-specific function to create the range in the first place.


> - Calling popFront doesn't throw unless range is empty.

Should be easy to check.


> - Calling popFront on an empty range throws a RangeError.

Is this part of the official requirement on ranges? I've been guilty of writing ranges whose popFront are no-ops when the range is empty (simply because for some ranges, it's a pain to explicitly check for this and throw, when the popFront computation doesn't actually assume anything about emptiness).


> - Upon instantiating a new random access range, 'r.front == r[0]', and
>   then after 'r.popFront()', 'r.front == r[1]', etc.

This should be relatively easy to check.


> - 'r.save.front == r.front'. And then call popFront on both ranges, and
>   'r1.front == r2.front' is still true.

Should be easy to check too.

I was gonna say that you'd have to watch out for RNGs, as popFront on an RNG that bases its output on, say, random environmental factors, will break this rule; but on second thought, in this case .save is invalid on such ranges (they can only be input ranges) so this check *should* fail.


> - Iterating via back/popBack yields the same elements as
>   front/popFront, but in reverse order.

Doesn't work on infinite ranges. :) (You *can* have infinite ranges with two ends. There's no good reason to do that, of course, because they are effectively just two infinite forward ranges stuck together at their infinite ends, which is kinda pointless, but in theory, this *can* happen.)


> And I'm sure there's a whole bunch more.
>
> If you give a hypothetical generic range-testing tool both an instantiated range to be tested and an array of all the elements you expect to be in the range, in the same order, then I'd think all of the above and more should be testable.

This wouldn't work on infinite ranges. :) But you could at least test some initial segment of an infinite range, I suppose, so this shouldn't be too big of an issue.


T

-- 
Amateurs built the Ark; professionals built the Titanic.

On Thursday, March 21, 2013 13:52:12 Nick Sabalausky wrote:
> On Thu, 21 Mar 2013 13:48:54 -0400
> 
> Nick Sabalausky <SeeWebsiteToContactMe@semitwist.com> wrote:
> > - Calling popFront doesn't throw unless range is empty.
> > - Calling popFront on an empty range throws a RangeError.
> 
> Actually, I'm not certain about those two, but I know they're true if you just s/popFront/front/

There are no such requirements on ranges. popFront most definitely _can_ throw even if the range is non-empty (e.g. UTFException due to invalid UTF), and I'm not aware of any range in Phobos which currently throws a RangeError when trying to call popFront on an empty range. Normally, an assertion is used, and the range's behavior when popping an element from an empty range in release mode is undefined. But I could definitely see an argument for adopting the policy of having popFront throw RangeError when the range is empty.

- Jonathan M Davis

On Thursday, March 21, 2013 13:48:54 Nick Sabalausky wrote:
> On Thu, 21 Mar 2013 13:29:35 -0400
> 
> "Jonathan M Davis" <jmdavisProg@gmx.com> wrote:
> > But I don't
> > know how you'd automate testing behavior when the exact behavior of
> > the range is very much dependent on the range itself.
> 
> I don't think that's true at all. Granted, you can't automate testing of the range's internal state, but there's a lot about the external behavior which is very strictly defined:
> 
> Examples:
> - Multiple calls to front return the same element.
> - Calling popFront and then front returns the next element.
> - If range has length, then 'empty' returns true IFF popFront has been
> called at least 'myRange.length' times.
> - Calling popFront doesn't throw unless range is empty.
> - Calling popFront on an empty range throws a RangeError.
> - Upon instantiating a new random access range, 'r.front == r[0]', and
> then after 'r.popFront()', 'r.front == r[1]', etc.
> - 'r.save.front == r.front'. And then call popFront on both ranges, and
> 'r1.front == r2.front' is still true.
> - Iterating via back/popBack yields the same elements as
> front/popFront, but in reverse order.
> 
> And I'm sure there's a whole bunch more.
> 
> If you give a hypothetical generic range-testing tool both an instantiated range to be tested and an array of all the elements you expect to be in the range, in the same order, then I'd think all of the above and more should be testable.

I confess that it pretty much never occurs to me to test most of this stuff. It's always the exact state of the range that I care about, because that has to do with whether the function returns the correct result. But the sort of testing that you're listing here could probably be automated.

- Jonathan M Davis

On Thu, 21 Mar 2013 11:04:31 -0700
"H. S. Teoh" <hsteoh@quickfur.ath.cx> wrote:
>
> > - Calling popFront and then front returns the next element.
> 
> How do you know if something is the "next element"? What if the range
> is repeat(1)?
> 
> 
> > - If range has length, then 'empty' returns true IFF popFront has been called at least 'myRange.length' times.
> 
> This should also be easy to test. But it requires the ability to instantiate the range with some given number of elements. So you still need a range-specific function to create the range in the first place.
> 

What I had in mind was something like:

void testForwardRange(R, E)(R range, E[] content)
{
    // Deliberately not contraints, because this *is* a test, after all.
    // *Or* maybe it just auto-detects range type and leaves it
    // up to the user to check for "isForwardRange!R" or whatever.
    static assert(isForwardRange!R);
    static assert(is(ElementTypeOf!R == E));

    static if(hasLength!R)
        assert(range.length == content.length);

    foreach(i; 0...content.length)
    {
        assert(range.front == content[i]);
        range.popFront();
    }

    // More tests
}

unittest{
    testForwardRange(createMyRangeSomehow(), [...expected elements...]);
}


> 
> > - Calling popFront on an empty range throws a RangeError.
> 
> Is this part of the official requirement on ranges? I've been guilty of writing ranges whose popFront are no-ops when the range is empty (simply because for some ranges, it's a pain to explicitly check for this and throw, when the popFront computation doesn't actually assume anything about emptiness).
> 

Actually, I'm not sure on that one. I would think that calling
front on an empty range should throw. Or at least in a typical
well-behaved range it should, even if it's not specifically stated as
being technically mandatory. But in any case, it was only an example.

> 
> > - Iterating via back/popBack yields the same elements as
> >   front/popFront, but in reverse order.
> 
> Doesn't work on infinite ranges. :) (You *can* have infinite ranges with two ends. There's no good reason to do that, of course, because they are effectively just two infinite forward ranges stuck together at their infinite ends, which is kinda pointless, but in theory, this *can* happen.)
> 

Naturally, the testing would be different on different types of ranges. The tester could auto-detect things like "isInfiniteRage" and "hasLength", and act accordingly.

And of course, if you want to guarantee your range is indeed, for example, a "hasLength", then you can also just add "static assert(hasLength!MyRange);" alongside your call to the tester.

On Thursday, 21 March 2013 at 18:19:00 UTC, Jonathan M Davis wrote:
> I could definitely see an argument for adopting the
> policy of having popFront throw RangeError when the range is empty.
>
> - Jonathan M Davis

In release mode, assert expressions are removed. This would not be possible for throwing a RangeError, preventing a useful optimisation in well tested code.