stdcxx-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Anton Pevtsov <ant...@moscow.vdiweb.com>
Subject Re: Re: test for lib.alg.partitions
Date Fri, 27 Jan 2006 16:01:52 GMT
Martin Sebor wrote:
> I think we should rewrite the test and hardcode the initial and
> partitioned sequences. I don't think we can sufficiently exercise the
> interesting/corner cases by generating the sequence. Also, I think we
> should be able to eliminate one of the two predicates. It's sufficient
> to exercise the algorithm with just one so long as we exhaustively
> verify all the requirements. Let me know if this makes sense to you
> and/or if you have any questions.

The attached file 25.partitions.cpp contains the updated test version. 
I hardcoded test sequences and eliminated one predicate.

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. Also if __fill is equal to 1 no destructors will be called, but
one should be, shouldn't it?
May be, something like this

...
    for (_TypeT *__ptr = __pair.first + __fill; !(__pair.first ==
__ptr--); )
        (*__ptr).~_TypeT ();
...
will fix the issue?


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.


With best wishes,
Anton Pevtsov


-----Original Message-----
From: Martin Sebor [mailto:sebor@roguewave.com] 
Sent: Friday, January 27, 2006 03:43
To: stdcxx-dev@incubator.apache.org
Subject: Re: test for lib.alg.partitions


Anton Pevtsov wrote:

>> The attached file contains my attempt to update lib.alg.partiton and 
>> lib.alg.stable_partiton tests and port them to new test driver.
>  
>

I think we should rewrite the test and hardcode the initial and
partitioned sequences. I don't think we can sufficiently exercise the
interesting/corner cases by generating the sequence. Also, I think we
should be able to eliminate one of the two predicates. It's sufficient
to exercise the algorithm with just one so long as we exhaustively
verify all the requirements. Let me know if this makes sense to you
and/or if you have any questions.


>> 
>> I suspect a bug in the stable_partiton algorithm implementation. 
>> Suppose that for all elements of an array the predicate is true. The 
>> stable_partition should return "last" in this case. But call of the 
>> stable_partiton on this array fails with the following
>> assertion:
>>    stdlib\tests\src\alg_test.cpp:135: __thiscall X::~X(void): 
>> Assertion 'id_ && id_ <= id_gen_' failed. In the debugger you can see

>> that the id_ of the deleting X object is equal to 0 (I suppose that 
>> this X is invalid), but the "this" looks good.
>  
>

Yes, the id_ member is reset in the dtor to indicate that the object has
already been destroyed (no valid id_ is ever 0).


>> What do you think about this issue?
>  
>

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.


>> 
>> I plan investigate this more deeply.
>  
>

A simple test case would be helpful.


>> Current test version includes the tests on which stable_partiton fails
>  
>

>> and these tests are marked using comments.
>> 
>> Also, there is another intresting thing with the stable_partition 
>> algorithm. Suppose that an array contains only one element. According 
>> to the standard the complexity in this case should be equal to 0 
>> swaps. Actually there are 0 swaps, but there is 1 assignment. I guess 
>> this is not a bug (the standard talks nothing about the assignments), 
>> but may be there are unnecessary assignment operations in the 
>> stable_partitions implementation.
>> What do you think about it?
>  
>

There is no reason to do anything if there's only one element in the
range, but if the standard allows it we don't need to go to heroic
measures eliminating it. That said, if it's an easy change we should
definitely do it.

A few more comments below...


>> 
>> With best wishes,
>> Anton Pevtsov
>> 
>> 
>> ----------------------------------------------------------------------
>> --
>  
>
[...]

>> template <class T>
>> struct LessThanPredicate : ComparePredicateBase
>> {
>>     LessThanPredicate (const int value) : ComparePredicateBase (value)
>  
>

>> {}
>> 
>>     // return a type other than bool but one that is implicitly
>>     // convertible to bool to detect incorrect assumptions
>>     ConvertibleToBool operator() (const T &arg) {
>  
>

Let's replace the type with the canned conv_to_bool type defined in
alg_test.h.

[...]

>> // exercises std::partition() and std::stable_partition() template 
>> <class T, class Iterator, class Predicate> void test_partitions (const
>  
>

>> std::size_t line, const std::size_t N,
>  
>

line should be int to match the type of the __LINE__ macro.


>>                       const Iterator& it, const Predicate& pr, 
>>                       const T* , int val, bool stable)
>> {
>>     _RWSTD_UNUSED(pr);
>> 
>>     const char* const itname = type_name (it, (T*)0);
>>     const char* const fname = 
>>         stable ? "stable_partition" : "partition";
>>     const char* const funname = Predicate::name();
>> 
>>     rw_info (0, 0, 0,
>>              "%s %s (%1$s, %1$s, %s)",
>>              itname, fname, funname);
>> 
>>     // create an array of T 
>>     T::gen_ = gen_seq;
>>     T *buf = new T[N];
>> 
>>     for (std::size_t i = 0; i < N; ++i) {
>> 
>>         const Iterator first = make_iter (buf, buf, buf + i + 1, it);
>  
>

The end pointer above should be (buf + i), not (buf + i + 1). (This is
true in general for all these tests. I corrected this in the others but
forgot to mention it.)

Martin


Mime
View raw message