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

[Stephen M. Webb]

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);
>
> Prior to the pop_back() call, the list is [2 1 3]  and the iterators i
> and k, along with reverse_iterator j, point to the 1. However, the
> actual iterator that j stores (in j.current) points to the 3, which is
> invalidated by the pop_back() call, and therefore should not be
> dereferenced at the line marked INVALID. The same problem occurs again
> in the next block (j.current is still singular).
>
> Note that the problem does not show up as a failure in normal test
> runs, presumably because the old node is still accessible in memory due
> to the pooling allocator.

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 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 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.  I believe the library is allowed to take advantage of 
knowledge of its own internals in order to implement its functionality:  if a 
library user were to rely on this behaviour it would be an error.

Note that j.base() will be invalidated by the pop_back() call, since it is an 
iterator to the erased element.  It will not return an iterator that will 
return true when compared for equality with the end() of the list.  An 
invalidated iterator is not singular.  

At the line marked INVALID above, j.current is not dereferenced at any point.

-- 
Stephen M. Webb