Re: test for lib.alg.partitions

[Martin Sebor <se...@roguewave.com>]

Anton Pevtsov wrote:
[..]
> The attached file 25.partitions.cpp contains the updated test version. I 
> hardcoded test sequences and eliminated one predicate.

Thanks for changing it. The test looks very good! I committed it here:
http://svn.apache.org/viewcvs.cgi?rev=374225&view=rev but we will need
to revisit and enhance it soon thanks to your astute observation below.

> 
> Martin Sebor wrote:
> 
>> It's certainly possible that there is a bug in the algorithm, but I
>> would be more inclined to suspect the test before the algorithm just
>> because you just made making non-trivial changes to it.
> 
> [...]
> 
>> A simple test case would be helpful.
> 
> 
> The old test version didn't exercise all possible cases. I updated the
> test according to your notes and got the same results. So I still
> suspect the bug in the algorithm.
> The attached file stable_partition_test.cpp illustrates the problem: the 
> algorithm fails when the predicate returns true for any element.
> 
> I debug the algorithm and found the following code in algorithm.cc, line
> 760:
> 
> ...
>    _Dist __fill = 0;
> 
>    const _BidirIter __res =
>        __stable_partition_adaptive (__first, __last, __pred, __dist,
>                                     __pair.first, __pair.second,
>                                     __fill, (_TypeT*)0);
> 
>    for (_TypeT *__ptr = __pair.first + __fill; !(__pair.first ==
> --__ptr); )
>        (*__ptr).~_TypeT ();
> ...
> 
> If the __fill remains equal to 0 after the __stable_partition_adaptive
> call the "for" will never end and will try to call destructors of
> non-existing elements moving from the left bound of the given sequence
> to left.

That definitely looks like a bug.

> Also if __fill is equal to 1 no destructors will be called, but
> one should be, shouldn't it?

It sure seems like it should, otherwise there could be a leak.

> May be, something like this
> 
> ...
>    for (_TypeT *__ptr = __pair.first + __fill; !(__pair.first ==
> __ptr--); )
>        (*__ptr).~_TypeT ();
> ...
> will fix the issue?

I'll have to study the code some more to understand it better. In the
meantime, I suggest you enhance the test to keep track of the number
of objects of type X that exist immediately before the algorithm is
invoked and right after and detect outstanding instances. Look at the
members of class X to see how to do it. That way we'll be sure our
fix doesn't cause any leaks.

I created a new issue with your test case that I modified ever so
slightly to better show where the problem occurs to keep track of
this bug: http://issues.apache.org/jira/browse/STDCXX-131. I also
added you to the Jira group of stdcxx-developers and assigned the
issue to you. Congratulations on your very first bug! :)

> 
> 
> And I have another question: what will happen with the temporary buffer
> in stable_partition if the X copy ctor throws an exception? It looks
> like the buffer will leak.

Excellent question! We need to exercise the exception safety of the
algorithms. Class X allows you to control precisely at which point
it should throw an exception (default ctor, copy ctor, assignment
operator, etc.) We need to set up the test so as to trigger an
exception at every possible step starting from the very first
opportunity and until no exception is thrown. At each iteration of
this loop we need to calculate the number of X objects in existence
and verify than none leaked. I suggest you check out the
23.deque.modifiers.cpp test below to get an idea how to implement
something like this here:

http://svn.apache.org/repos/asf/incubator/stdcxx/trunk/tests/containers/23.deque.modifiers.cpp

Thanks for the great detective work! :)
Martin