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 Mon, 06 Feb 2006 16:41:19 GMT
Martin, here is the updated test version - I added checks for X objects
leaks (or unexpected dtor calls).
I plan to implement the exception-safity test for this algorithm (and I
think we need to implement such tests for each algorithm, don't we?).

With best wishes,
Anton Pevtsov.

-----Original Message-----
From: Martin Sebor [mailto:sebor@roguewave.com] 
Sent: Thursday, February 02, 2006 05:54
To: stdcxx-dev@incubator.apache.org
Subject: Re: test for lib.alg.partitions


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


Mime
View raw message