Re: [PATCH] fix singular iterator dereference in libstdc++ testcase 23_containers/list_modifiers.cc

[Doug Gregor <dgregor at apple dot com>]

On Tuesday, June 10, 2003, at 08:15 AM, Stephen M. Webb wrote:

> On June 9, 2003 06:21 pm, Doug Gregor wrote:
> > In the testcase 23_containers/list_modifiers.cc, the function test01()
> > contains this block of code:
> >
> >    list0101.pop_back();          // list should be [2 1]
> >    VERIFY(list0101.size() == 2);
> >    VERIFY(T::dtorCount() == 1);
> >    VERIFY(i->id() == 1);
> >    VERIFY(j->id() == 1); // INVALID
> >    VERIFY(k->id() == 1);
> The standard pretty explicitly states (in [23.2.2.3 (3)]) that 
> pop_back()
> invalidates only iterators and references to the erased elements, and 
> j is an
> iterator into list0101 that is not an iterator to the erased element. 
> It
> should not be invalidated, and I would expect it to continue to work
> correctly in a conforming implementation, since there's nothing in the
> standard that leads me to believe otherwise.

The comments that pertain to iterator invalidation by container 
operations only consider the "iterator" and "const_iterator" types for 
a container, and not the "reverse_iterator" or "const_reverse_iterator" 
types. Under this interpretation, the testcase is wrong, because it 
fails when the latter two types are std::reverse_iterator<iterator> and 
std::reverse_iterator<const_iterator>, respectively. As you say below:

> Note that j.base() will be invalidated by the pop_back() call, since 
> it is an
> iterator to the erased element.

j.base(), which is the same as j.current, is invalidated by the 
pop_back() call. Then when we are using std::reverse_iterator (as noted 
in 23.1.1/9, Table 66), the dereference operator invokes --j.current, 
which has undefined behavior.

> The test case does not pass by coincidence and does not rely on the
> persistence of a deallocated node.  The "current" member of the
> reverse_iterator in the case of a list is merely a collection of 
> pointers,

The "current" member is of type _List_iterator<T, T&, T*>, and its only 
data comes from its base class, _List_iterator_base, which contains 
(only):

  _List_node_base* _M_node;

And here's how we decrement a _List_iterator (includes dereferencing 
the pointer):

    void
    _M_decr()
    { _M_node = _M_node->_M_prev; }

> the important one of which points back to the actual node referenced 
> by the
> reverse_iterator.  Regardless of the fact that the "current" member is
> theoretically an invalid iterator, "--current" will continue to be a 
> valid
> reference into the list, and j will continue to be valid and 
> dereferenceable,
> and it just works.

--current will dereference _M_node, and that is an error. To convince 
yourself of this, clear out the _M_next/_M_prev fields just before 
_M_put node deallocates the node, so it looks like this:

    void
    _M_put_node(_List_node<_Tp>* __p)
    {
      std::cerr << "Deallocate node at " << __p << '\n';
      __p->_M_next = 0;
      __p->_M_prev = 0;
      _Alloc_type::deallocate(__p, 1);
    }

Here's what I get, with a little extra debugging information added in. 
It includes all deference/deallocate/decrement operations on list 
iterators, starting from the push_back:

Decrement node at 0x321ae0
Deallocate node at 0x321b10     // #1
Dereference node at 0x321af0
Decrement node at 0x321b10  // #2
Dereference node at 0 // #3

At #1 is a deallocation, and then we try to decrement that same node at 
#2, that dereferences a pointer already passed to the allocator's 
deallocate() method. And at #3 I get a bus error, because of the 
pointer-zeroing code.

The testcase is incorrect, and with more tracking information we can 
see that the behavior under libstdc++ is also undefined.

	Doug