This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

deque fails to meet 23.2.1.3.4-5 causing invalid iterators and extra assignments


I recently found that deque iterators were being invalidated under some
circumstances when they shouldn't be.

Specifically when elements are removed from the front of the deque using
my_deque.erase(my_deque.begin(), my_deque.begin() + n)

iterators at position (begin() + n) and beyond created before the erase
should still be valid after the erase as stated in the standard
at 23.2.1.3.4

When looking into this bug I found that there was another bug when erasing
elements from the middle of the deque.

The standard states that operator=() will be called at most, the minimum
of (the number of elements before the range) and (the number of elements
following the range) see 23.2.1.3.5

There are circumstances in the current implementation where the number of
calls to operator=() is the minimum + 1. This may seem unimportant, but
this bug is the cause of the iterator invalidation bug mentioned above.

I have a patch below that I believe fixes both problems:
Also included are test files that show the existing bugs.

This patch was created against 3.4.4
======================================================================================
*** deque.tcc   Mon Jan 22 14:30:34 2007
--- deque.tcc.fixed     Mon Jan 22 14:31:00 2007
***************
*** 138,148 ****
        }
        else
        {
          const difference_type __n = __last - __first;
          const difference_type __elems_before = __first - this->_M_impl._M_start;
!         if (static_cast<size_type>(__elems_before) < (size() - __n) / 2)
            {
              std::copy_backward(this->_M_impl._M_start, __first, __last);
              iterator __new_start = this->_M_impl._M_start + __n;
              std::_Destroy(this->_M_impl._M_start, __new_start);
              _M_destroy_nodes(this->_M_impl._M_start._M_node, __new_start._M_node);
--- 138,148 ----
        }
        else
        {
          const difference_type __n = __last - __first;
          const difference_type __elems_before = __first - this->_M_impl._M_start;
!         if (static_cast<size_type>(__elems_before) < (size() - __n) - __elems_before)
            {
              std::copy_backward(this->_M_impl._M_start, __first, __last);
              iterator __new_start = this->_M_impl._M_start + __n;
              std::_Destroy(this->_M_impl._M_start, __new_start);
              _M_destroy_nodes(this->_M_impl._M_start._M_node, __new_start._M_node);

======================================================================================

file: stl_deque_bug.cpp
======================================================================================
/////////////////////////////////////////////////////////////////////////////
//
// Steve LoBasso <slobasso@yahoo.com>
//
// This code shows a bug in the deque implementation where iterators,
// not participating in an erase relative to the front, are invalidated.
//
// Sample code to show bug in deque iterator invalidation during erase
// Compile: g++ -Wall -pedantic stl_deque_bug.cpp -o stl_deque_bug
//
// All of the following produce the bug:
// g++ (GCC) 4.1.0 20060304 (Red Hat 4.1.0-3)
// g++ (GCC) 3.2.3 20030502 (Red Hat Linux 3.2.3-34)
// g++ (GCC) 3.4.4 20050721 (Red Hat 3.4.4-2)
//
// Sun Workshop using RougeWave stl works correctly
// CC: Sun WorkShop 6 update 2 C++ 5.3 Patch 111685-07 2002/04/10
//
// Run: ./stl_deque_bug
// This will create invalid iterators in a few cases.
//
// Try: ./stl_deque_bug -w
// This will run code that works around the problem.
// This should create good output to compare against.
//
// To run against larger datasets, use the test-max option:
// Try: ./stl_deque_bug 15
// or
// Try: ./stl_deque_bug -w 15
//
/////////////////////////////////////////////////////////////////////////////

#include <deque>

#define STDCC std::
typedef STDCC deque<long> deque_type;

#include <iostream>
#include <vector>
#include <assert.h>

bool work_around_deque_bug = false;

long get_id()
{
    static long id = 0;
    return ++id;
}

unsigned long where_to_put(long i)
{
    if ((i % 7) == 0) {
        return 0;
    }
    else if ((i % 3) == 0) {
        return static_cast<unsigned long>(-1);
    }
    return ((i % 37) + 1);
}

void dump(deque_type &x)
{
    STDCC cout << "############ Begin Dump ###################################" << STDCC endl;
    STDCC cout << "size = " << x.size() << STDCC endl;

    STDCC cout << STDCC endl;
    STDCC cout << "iterating..." << STDCC endl;
    for (deque_type::iterator it = x.begin(); it != x.end(); ++it) {
        STDCC cout << *it << STDCC endl;
    }

    STDCC cout << STDCC endl;
    STDCC cout << "iterating back..." << STDCC endl;
    if (x.begin() != x.end()) {
        deque_type::iterator it = x.end();
        do {
            --it;
            STDCC cout << *it << STDCC endl;
        } while (it != x.begin());
    }

    STDCC cout << STDCC endl;
    STDCC cout << "indexing..." << STDCC endl;
    for (deque_type::size_type it = 0; it != x.size(); ++it) {
        STDCC cout << x[it] << STDCC endl;
    }

    STDCC cout << STDCC endl;
    STDCC cout << "indexing back..." << STDCC endl;
    if (x.begin() != x.end()) {
        deque_type::size_type it = 0;
        do {
            ++it;
            STDCC cout << x.end()[-it] << STDCC endl;
        } while (it != x.size());
    }
    STDCC cout << "############ End Dump #####################################" << STDCC endl;
}

void fill(deque_type &x, size_t n)
{
    STDCC cout << "inserting..." << STDCC endl;
    long z = get_id();
    for (size_t h = z; h != n + z; ++h) {
        long i = get_id();

        unsigned long where = where_to_put(i);
        
        if (where == 0) {
            STDCC cout << "push_front(" << i << ")" << STDCC endl;
            x.push_front(i);
        }
        else if (where == static_cast<unsigned long>(-1)) {
            STDCC cout << "push_back(" << i << ")" << STDCC endl;
            x.push_back(i);
        }
        else {
            --where;
            if (where > x.size()) {
                where = x.size();
            }
            
            STDCC cout << "insert(" << where << ", " << i << ")" << STDCC endl;
            x.insert(x.begin() + where, i);
        }
    }
}

void test1(size_t elm_cnt, size_t bck_del, size_t frn_del, size_t beg_del, size_t end_del)
{
    deque_type x;
    typedef STDCC vector<deque_type::iterator> iter_container;

    fill(x, elm_cnt);
    assert(x.size() == elm_cnt);
    dump(x);

    {
        assert(x.size() >= bck_del);
        STDCC cout << "saving iterators..." << STDCC endl;
        iter_container valid_iters;
        for (deque_type::iterator si = x.begin(); si != x.end() - bck_del; ++si) {
            valid_iters.push_back(si);
            
            STDCC cout << *si << STDCC endl;
        }
        STDCC cout << "count = " << valid_iters.size() << STDCC endl;
        
        STDCC cout << "deleting from back... " << bck_del << STDCC endl;
        deque_type::iterator it = x.erase(x.end() - bck_del, x.end());
        STDCC cout << "result = " << (it - x.begin()) << STDCC endl;
        dump(x);

        for (iter_container::iterator sii = valid_iters.begin(); sii != valid_iters.end(); ++sii) {
            STDCC cout << *(*sii) << STDCC endl;
        }
        STDCC cout << STDCC endl;

        dump(x);
    }

    {
        assert(x.size() >= frn_del);
        STDCC cout << "saving iterators..." << STDCC endl;
        iter_container valid_iters;
        if (x.size() != frn_del) {
            deque_type::iterator si = x.end();
            do {
                --si;
                valid_iters.push_back(si);
                
                STDCC cout << *si << STDCC endl;
            } while (si != x.begin() + frn_del);
        }
        STDCC cout << "count = " << valid_iters.size() << STDCC endl;
        
        STDCC cout << "deleting from front... " << frn_del << STDCC endl;

        if (!work_around_deque_bug) {
            // C++ Standard 23.2.1.3.4
            // std::deque bug in GNU implementation
            // this seems to invalidate some of the iterators in valid_iters, which it shouldn't
            deque_type::iterator it = x.erase(x.begin(), x.begin() + frn_del);
            STDCC cout << "result = " << (it - x.begin()) << STDCC endl;
        }
        else {
            for (size_t f = 0; f != frn_del; ++f) {
                x.pop_front();
            }
            STDCC cout << "result = " << 0 << STDCC endl;
        }

        dump(x);
        
        for (iter_container::iterator sii = valid_iters.begin(); sii != valid_iters.end(); ++sii) {
            STDCC cout << *(*sii) << STDCC endl;
        }
        STDCC cout << STDCC endl;

        dump(x);
    }

    {
        assert(x.size() >= beg_del && x.size() >= end_del && beg_del <= end_del);
        STDCC cout << "deleting from middle... " << beg_del << " - " << end_del << STDCC endl;
        deque_type::iterator it = x.erase(x.begin() + beg_del, x.begin() + end_del);
        STDCC cout << "result = " << (it - x.begin()) << STDCC endl;
        dump(x);
    }
    
    STDCC cout << "clearing..." << STDCC endl;
    x.clear();
    dump(x);
}

int main(int argc, char **argv)
{
    unsigned long max_cnt = 7; // 7 is usually enough to show a few instances of this bug, otherwise try 30

    for (int i = 1; i < argc; ++i) {
        if (strcmp(argv[i], "-w") == 0) {
            work_around_deque_bug = true;
        }
        else if (sscanf(argv[i], "%lu", &max_cnt) == 1) {
        }
        else {
            STDCC cerr << "usage: " << argv[0] << " [-w] [test-max]" << STDCC endl;
            STDCC cerr << "   -w     work around deque bug." << STDCC endl;
            exit(1);
        }
    }

    for (size_t cnt = 0; cnt <= max_cnt; ++cnt) {
        STDCC cerr << "test1 with container size: " << cnt << STDCC endl;
        STDCC cout << "test1 with container size: " << cnt << STDCC endl;
        STDCC cout << "======================================" << STDCC endl;
        for (size_t bck_del = 0; bck_del <= cnt; ++bck_del) {
            for (size_t frn_del = 0; frn_del <= cnt - bck_del; ++frn_del) {
                for (size_t mid_st = 0; mid_st <= cnt - bck_del - frn_del; ++mid_st) {
                    for (size_t mid_del = 0; mid_del <= cnt - bck_del - frn_del - mid_st; ++mid_del) {
//                        STDCC cerr << cnt << ", " << bck_del << ", "  << frn_del << ", "  << mid_st << ", "  << (mid_st + mid_del) << STDCC endl << STDCC endl;
                        STDCC cout << cnt << ", " << bck_del << ", "  << frn_del << ", "  << mid_st << ", "  << (mid_st + mid_del) << STDCC endl << STDCC endl;
                        test1(cnt, bck_del, frn_del, mid_st, mid_st + mid_del);
                    }
                }
            }
        }
    }
    return 0;
}
======================================================================================

file: stl_deque_bug2.cpp
======================================================================================
/////////////////////////////////////////////////////////////////////////////
//
// Steve LoBasso <slobasso@yahoo.com>
//
// This code shows a bug in the gnu stl deque implementation
// where erase moves elements incorrectly
//
/////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <utility>
#include <deque>

struct foo {
    static size_t assign_cnt;

    foo &operator=(foo const &) {
        ++assign_cnt;
        return *this;
    }
};

size_t foo::assign_cnt = 0;

size_t bad_cpys = 0;

void erase(size_t num_elm, size_t elm_strt, size_t elm_end)
{
    std::deque<foo> x(num_elm);
    
    foo::assign_cnt = 0;
    
    x.erase(x.begin() + elm_strt, x.begin() + elm_end);
    
    size_t min_num_cpy = std::min(elm_strt, num_elm - elm_end);
    size_t num_cpy = foo::assign_cnt;
    if (num_cpy != min_num_cpy) {
        // C++ Standard 23.2.1.3.5 states that the number of assignments should be
        // the minimum of (the number of elements before the range) and (the number of
        // elements following the range)
        ++bad_cpys;
        std::cout << "num_cpy != min_num_cpy: " << num_cpy << " != " << min_num_cpy << std::endl;
        std::cout << "size() = " << num_elm << ", first = " << elm_strt << ", last = " << elm_end << std::endl;
        std::cout << std::endl;
    }
}

int main()
{
    for (size_t num_elm = 0; num_elm <= 10; ++num_elm) {
        for (size_t elm_strt = 0; elm_strt <= num_elm; ++elm_strt) {
            for (size_t elm_end = elm_strt; elm_end <= num_elm; ++elm_end) {
                erase(num_elm, elm_strt, elm_end);
            }
        }
    }

    std::cout << "bad_cpys: " << bad_cpys << std::endl;
    return 0;
}
======================================================================================




 
____________________________________________________________________________________
Yahoo! Music Unlimited
Access over 1 million songs.
http://music.yahoo.com/unlimited


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]