Mailing-List: contact stdcxx-dev-help@incubator.apache.org; run by ezmlm
Precedence: bulk
Reply-To: stdcxx-dev@incubator.apache.org
Received-SPF: pass (asf.osuosl.org: domain of AntonP@moscow.vdiweb.com
 designates 195.210.189.132 as permitted sender)
Message-ID: <43DA43F0.9020601@moscow.vdiweb.com>
Date: Fri, 27 Jan 2006 19:01:52 +0300
From: Anton Pevtsov <antonp@moscow.vdiweb.com>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US;
 rv:1.7) Gecko/20040514
MIME-Version: 1.0
To: stdcxx-dev@incubator.apache.org
Subject: Re: Re: test for lib.alg.partitions
Content-Type: multipart/mixed;
 boundary="------------090406080200050800070207"

--------------090406080200050800070207
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit

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


--------------090406080200050800070207
Content-Type: text/plain;
 name="stable_partition_test.cpp"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="stable_partition_test.cpp"

#include <algorithm>
#include <stdio.h>

static int ids;

struct TestX
{
    TestX () {
        id_ = ++ids;
        val_ = id_;

        printf ("ctor created TestX with id == %d, this == %p\n", 
                id_, (void*) this);
    }

    TestX (const TestX& y) {
        id_ = ++ids;
        this->val_ = y.val_;
        printf ("copy ctor created TestX with id == %d, this == %p\n", 
                id_, (void*) this);
    }

    ~TestX () {
        printf ("deleting TestX with id == %d, this == %p\n", 
                id_, (void*) this);
        id_ = 0;
    }

    int val_;

private:
    int id_;
};

bool true_predicate (TestX& ) {
    return true;
}

int main()
{
    TestX* px = new TestX[3];

    printf ("begin stable_partition\n");
    std::stable_partition (px, px + 2, true_predicate);
    printf ("end stable_partition\n");

    delete[] px;
    return 0;
}

--------------090406080200050800070207
Content-Type: text/plain;
 name="25.partitions.cpp"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="25.partitions.cpp"

/***************************************************************************
 *
 * partitions.cpp - test exercising 25.2.12 [lib.alg.partitions]
 *
 * $Id: //stdlib/dev/tests/stdlib/algorithm/partitions.cpp#18 $
 *
 ***************************************************************************
 *
 * Copyright (c) 1994-2005 Quovadx,  Inc., acting through its  Rogue Wave
 * Software division. Licensed under the Apache License, Version 2.0 (the
 * "License");  you may  not use this file except  in compliance with the
 * License.    You    may   obtain   a   copy   of    the   License    at
 * http://www.apache.org/licenses/LICENSE-2.0.    Unless   required    by
 * applicable law  or agreed to  in writing,  software  distributed under
 * the License is distributed on an "AS IS" BASIS,  WITHOUT WARRANTIES OR
 * CONDITIONS OF  ANY KIND, either  express or implied.  See  the License
 * for the specific language governing permissions  and limitations under
 * the License.
 * 
 **************************************************************************/

#include <algorithm>    // for partition, stable_partition
#include <cstring>      // for strlen, size_t

#include <alg_test.h>
#include <driver.h>     // for rw_test()

/**************************************************************************/

_RWSTD_NAMESPACE (std) { 

// disable explicit instantiation for compilers (like MSVC)
// that can't handle it
#ifndef _RWSTD_NO_EXPLICIT_INSTANTIATION

template
BidirIter<assign<base<cpy_ctor> > >
partition (BidirIter<assign<base<cpy_ctor> > >,
           BidirIter<assign<base<cpy_ctor> > >,
           predicate<assign<base<cpy_ctor> > >);

template
BidirIter<assign<base<cpy_ctor> > >
stable_partition (BidirIter<assign<base<cpy_ctor> > >,
                  BidirIter<assign<base<cpy_ctor> > >,
                  predicate<assign<base<cpy_ctor> > >);

#endif // _RWSTD_NO_EXPLICIT_INSTANTIATION

}   // namespace std

/**************************************************************************/

template <class T>
struct GreaterThanPredicate 
{
    static std::size_t funcalls_;

    GreaterThanPredicate (const int value) : value_(value) {
        funcalls_ = 0;
    }

    // return a type other than bool but one that is implicitly
    // convertible to bool to detect incorrect assumptions
    conv_to_bool operator() (const T &arg) {
        ++funcalls_;
        return conv_to_bool::make (arg.val_ > value_);
    }

    static const char* name () { return "GreaterThanPredicate"; }

private:
    const int value_;
    void operator= (GreaterThanPredicate&);
};

template<class T> std::size_t GreaterThanPredicate<T>::funcalls_;

/**************************************************************************/

// exercises std::partition() and std::stable_partition()
template <class T, class Iterator, class Predicate>
void test_partitions (int                   line, 
                      const char           *src,
                      const char           *dst,
                      const int             value,
                      const std::size_t     offset,
                      const Iterator       &it, 
                      const Predicate      *ppred, 
                      const T* , 
                      bool                  stable)
{
    _RWSTD_UNUSED(ppred);

    const char* const itname = type_name (it, (T*)0);
    const char* const fname = 
        stable ? "stable_partition" : "partition";
    const char* const funname = Predicate::name();

    const std::size_t nsrc = std::strlen (src);
    const std::size_t ndst = std::strlen (dst);

    T* const xsrc = T::from_char (src, nsrc);
    T* const xdst = T::from_char (dst, ndst);

    T* const xsrc_end = xsrc + nsrc;

    const Iterator first = make_iter (xsrc, xsrc, xsrc_end, it);
    const Iterator last  = make_iter (xsrc_end, xsrc, xsrc_end, it);

    const std::size_t last_n_op_assign = T::n_total_op_assign_;

    const Predicate pred(value);

    const Iterator res = 
            stable ? std::stable_partition (first, last, pred) 
                   : std::partition (first, last, pred);

    // check that the returned iterator points to the expected element
    bool success = res.cur_ == first.cur_ + offset;
    rw_assert (success, 0, line,
               "line %d: std::%s <%s, %s>(\"%s\", ...) ==> \"%{X=*.*}\", "
               "returned iterator it = first + %td, expected first + %zu",
               __LINE__, fname, itname, funname, src, int (nsrc), 
               -1, xsrc, res.cur_ - first.cur_, offset);

    // check 25.2.12, p2 & p5
    // "left" part of the array there the predicate should be true
    std::size_t i = 0;
    for ( ; i < offset; i++) {
        success = xsrc[i].val_ > value;
        if (!success)
            break;
    }

    rw_assert (success, 0, line,
               "line %d: std::%s <%s, %s>(\"%s\", ...) "
               "==> \"%{X=*.*}\", at %zu got: %#c !> %#c",
               __LINE__, fname, itname, funname, src, int (nsrc), 
               -1, xsrc, i + 1, xsrc[i].val_, value);


    // "right" part of the array there the predicate should be false
    for ( ; i < nsrc; i++) {
        success = xsrc[i].val_ <= value;
        if (!success)
            break;
    }

    rw_assert (success, 0, line,
               "line %d: std::%s <%s, %s>(\"%s\", ...) "
               "==> \"%{X=*.*}\", at %zu got: %#c !<= %#c",
               __LINE__, fname, itname, funname, src, int (nsrc), 
               -1, xsrc, i + 1, xsrc[i].val_, value);


    // check the complexity, 25.2.12 p3 & p6
    // first check number of swaps, 2 assignments per swap

    // add 1 in case of stable_partition to avoid the assertion failing
    // when i == 0 (only one element presents in the sequence)
    // is this one extra assignment an algorithm bug??
    // the standard talks about swaps only, not about assignments
    // and there are 0 swaps (1 swap equals 2 assignments) in this case...
    std::size_t exp_assigns =  stable ? 2 * nsrc * ::ilog2 (nsrc) + 1 : nsrc;
    std::size_t op_assigns  = T::n_total_op_assign_ - last_n_op_assign;

    success = op_assigns <= exp_assigns;
    rw_assert (success, 0, line,
               "line %d: std::%s <%s, %s>(\"%s\", ...): complexity: "
               "got %zu assignments, expected no more than %zu",
                __LINE__, fname, itname, funname, src,
                op_assigns, exp_assigns);

    // second check the number of the predicate calls
    success = Predicate::funcalls_ == nsrc;
    rw_assert (success, 0, line,
               "line %d: std::%s <%s, %s>(\"%s\", ...): complexity: "
               "got %zu applications of the predicate, "
               "expected no more than %zu",
                __LINE__, fname, itname, funname, src,
                Predicate::funcalls_, nsrc);

    if (!stable) {
        delete[] xsrc;
        delete[] xdst;
        return;
    }

    // check the stable_partition is really stable 25.2.12, p5
    for (i = 0; i < nsrc; i++) {
        success = xsrc[i].val_ == xdst[i].val_;
        if (!success)
            break;
    }

    rw_assert (success, 0, line,
               "line %d: std::%s <%s, %s>(\"%s\", ...) ==> \"%{X=*.*}\", "
               "expected \"%{X=*.*}\", realtive order broken at %zu, "
               "%#c != %#c",
               __LINE__, fname, itname, funname, src, 
               int (nsrc), int (i), xsrc, int (ndst), int (i), xdst,
               i, xsrc[i].val_, xdst[i].val_);

    delete[] xsrc;
    delete[] xdst;
}


template <class T, class Iterator>
void test_partitions (const Iterator &it, 
                      const T* , 
                      bool            stable)
{
    const char* const itname = type_name (it, (T*)0);
    const char* const fname = 
        stable ? "stable_partition" : "partition";
    const char* const funname = GreaterThanPredicate<T>::name();

    rw_info (0, 0, 0,
             "%s %s (%1$s, %1$s, %s)",
             itname, fname, funname);

#define TEST(src, dest, mid, offet)                                \
    test_partitions (__LINE__, src, dest, mid, offet, it,          \
                     (GreaterThanPredicate<T>*)0, (T*)0, stable)

    // stable_partition fails this test
    TEST ("abcdefghij", "abcdefghij",  0,  10); 

    TEST ("abcdefghij", "bcdefghija", 'a',  9);
    TEST ("abcdefghij", "cdefghijab", 'b',  8);
    TEST ("abcdefghij", "defghijabc", 'c',  7);
    TEST ("abcdefghij", "efghijabcd", 'd',  6);
    TEST ("abcdefghij", "fghijabcde", 'e',  5);
    TEST ("abcdefghij", "ghijabcdef", 'f',  4);
    TEST ("abcdefghij", "hijabcdefg", 'g',  3);
    TEST ("abcdefghij", "ijabcdefgh", 'h',  2);
    TEST ("abcdefghij", "jabcdefghi", 'i',  1);
    TEST ("abcdefghij", "abcdefghij", 'j',  0);

    // stable_partition fails this test
    TEST ("jihgfedcba", "jihgfedcba",  0,  10);

    TEST ("jihgfedcba", "jihgfedcba", 'a',  9);
    TEST ("jihgfedcba", "jihgfedcba", 'b',  8);
    TEST ("jihgfedcba", "jihgfedcba", 'c',  7);
    TEST ("jihgfedcba", "jihgfedcba", 'd',  6);
    TEST ("jihgfedcba", "jihgfedcba", 'e',  5);
    TEST ("jihgfedcba", "jihgfedcba", 'f',  4);
    TEST ("jihgfedcba", "jihgfedcba", 'g',  3);
    TEST ("jihgfedcba", "jihgfedcba", 'h',  2);
    TEST ("jihgfedcba", "jihgfedcba", 'i',  1);
    TEST ("jihgfedcba", "jihgfedcba", 'j',  0);

    // stable_partition fails this test
    TEST ("a", "a", 0, 1);  

    TEST ("a", "a", 'a', 0);
}

/**************************************************************************/

/* extern */ int rw_opt_no_partition;           // --no-partition
/* extern */ int rw_opt_no_stable_partition;    // --no-stable_partition
/* extern */ int rw_opt_no_bidir_iter;          // --no-BidirectionalIterator
/* extern */ int rw_opt_no_rnd_iter;            // --no-RandomAccessIterator


template <class T>
void test_partitions (const T* , 
                      bool          stable)
{
    rw_info (0, 0, 0, 
             "template <class %s, class %s> %1$s %s (%1$s, %1$s, %2$s)",
             "BidirectionalIterator", "Predicate", 
             stable ? "stable_partition" : "partition");

    if (rw_opt_no_bidir_iter) {
        rw_note (0, __FILE__, __LINE__, "BidirectionalIterator test disabled");
    }
    else {
        test_partitions (BidirIter<T>(), (T*)0, stable); 
    }

    if (rw_opt_no_rnd_iter) {
        rw_note (0, __FILE__, __LINE__, "RandomAccessIterator test disabled");
    }
    else {
        test_partitions (RandomAccessIter<T>(), (T*)0, stable);  
    }
}

static int run_test (int, char*[])
{
    if (rw_opt_no_partition) {
        rw_note (0, __FILE__, __LINE__, "std::partition test disabled");
    }
    else {
        test_partitions ((X*)0, false);
    }

    if (rw_opt_no_stable_partition) {
        rw_note (0, __FILE__, __LINE__, 
                 "std::stable_partition test disabled");
    }
    else {
        test_partitions ((X*)0, true);
    }

    return 0;
}

/**************************************************************************/

int main (int argc, char *argv[])
{
    return rw_test (argc, argv, __FILE__,
                    "lib.alg.partitions",
                    0 /* no comment */, run_test,
                    "|-no-partition# "
                    "|-no-stable_partition# "
                    "|-no-BidirectionalIterator# "
                    "|-no-RandomAccessIterator", 
                    &rw_opt_no_partition,
                    &rw_opt_no_stable_partition,
                    &rw_opt_no_bidir_iter,
                    &rw_opt_no_rnd_iter);
}

--------------090406080200050800070207--