[Bug libstdc++/51823] New: reverse iterator instantiated with POD type returns uninitialized values + work around

[Bug libstdc++/51823] New: reverse iterator instantiated with POD type returns uninitialized values + work around

[jakobsybren at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51823

             Bug #: 51823
           Summary: reverse iterator instantiated with POD type returns
                    uninitialized values + work around
    Classification: Unclassified
           Product: gcc
           Version: 4.6.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: jakobsybren@gmail.com


Created attachment 26299
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=26299
*.i* output of minimal example that reproduces the bug

System info:
$ uname -a 
Linux ****** 3.0.0-14-generic #23-Ubuntu SMP Mon Nov 21 20:28:43 UTC 2011
x86_64 x86_64 x86_64 GNU/Linux

$ g++ -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.6.1/lto-wrapper
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu/Linaro
4.6.1-9ubuntu3' --with-bugurl=file:///usr/share/doc/gcc-4.6/README.Bugs
--enable-languages=c,c++,fortran,objc,obj-c++,go --prefix=/usr
--program-suffix=-4.6 --enable-shared --enable-linker-build-id
--with-system-zlib --libexecdir=/usr/lib --without-included-gettext
--enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.6
--libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu
--enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-plugin
--enable-objc-gc --disable-werror --with-arch-32=i686 --with-tune=generic
--enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu
--target=x86_64-linux-gnu
Thread model: posix
gcc version 4.6.1 (Ubuntu/Linaro 4.6.1-9ubuntu3)


Attachment:
 * ostream_iterator_reverse_iterator.ii: output of:
 g++ -save-temps -o ostream_iterator_reverse_iterator -Wall
ostream_iterator_reverse_iterator.cc
 where ostream_iterator_reverse_iterator.cc is a minimal example that
reproduces the bug.

Headerfiles involved:
 <iterator>

Compile command: g++ -o ostream_iterator_reverse_iterator -Wall
ostream_iterator_reverse_iterator.cc

Description:
Consider an iterator class that implements the requirements of a
forward_iterator. We underlying datatype is always POD and the operator*()
member of the iterator returns the results by value, since it is POD anyway.

Upon creating a reverse_iterator from this class a simple for-loop produces the
expected results:
 Returning 9 9
 Returning 8 8
 Returning 7 7
 Returning 6 6
 Returning 5 5
 Returning 4 4
 Returning 3 3
 Returning 2 2
 Returning 1 1
 Returning 0 0

but using the reverse_iterator in std::copy() with std::ostream_iterator
produces:
 Returning 9 32767
 Returning 8 32767
 Returning 7 32767
 Returning 6 32767
 Returning 5 32767
 Returning 4 32767
 Returning 3 32767
 Returning 2 32767
 Returning 1 32767
 Returning 0 32767

It seems that the internal value does not get copied. When using -O3 both the
for-loop and the copy() construct produce 0 (zero) for each call to operator*()
in the reverse_iterator, but not in the normal iterator. 

The 'work-around' forces the use of forwarding. I put it as comment in the
minimum example. If I should have attached a separate source file with just the
operator*()-line replaced, I wish to express my apologies in advance.

The source file with the work-around instead of the original version of
operator*() needs an additional compiler option though: -std=c++0x
However, even with this version, the result with -O3 is still all zeros; not
what I expected, but since that is the same as before, I guess that is more
likely to be me misunderstanding what is supposed to happen with -O3 switched
on.

[Bug libstdc++/51823] reverse iterator instantiated with POD type returns uninitialized values + work around

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51823

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-01-11 13:16:16 UTC ---
(In reply to comment #0)
> Consider an iterator class that implements the requirements of a
> forward_iterator. We underlying datatype is always POD and the operator*()
> member of the iterator returns the results by value, since it is POD anyway.

The iterator requirements [iterator.iterators] say operator* must return
iterator_traits<some_iterator>::reference

[Bug libstdc++/51823] reverse iterator instantiated with POD type returns uninitialized values + work around

[jakobsybren at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51823

Jakob van Bethlehem <jakobsybren at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #26299|0                           |1
        is obsolete|                            |

--- Comment #2 from Jakob van Bethlehem <jakobsybren at gmail dot com> 2012-01-11 13:40:18 UTC ---
Created attachment 26300
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=26300
Minimal example that reproduces bug, but with proper call-signature for
operator*() (ie: returning reference)

Minimal example was changed with proper call-signature for operator*(),
returning reference. 

The resulting behavior remains the same as explained in the original message
though.

[Bug libstdc++/51823] reverse iterator instantiated with POD type returns uninitialized values + work around

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51823

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-01-11 13:55:49 UTC ---
(In reply to comment #0)
> Headerfiles involved:
>  <iterator>

And <iostream>

> Consider an iterator class that implements the requirements of a
> forward_iterator.

Do you mean bidirectional iterator?  You can't reverse a forward iterator, and 
std::reverse_iterator requires that its template parameter meets the
requirements of a Bidirectional Iterator.
Your class doesn't implement those requirements, it doesn't have a
post-increment operator.

And as I said in my previous comment, the iterator requirements say operator*
returns the iterator's 'reference' type.  reverse_iterator::operator* then
returns the same thing because the 'reference' type is, in effect, defined as
"the type returned by operator*"

(Also, the name __traits is forbidden, names beginning with double-underscore
are reserved for the implementation)

> The 'work-around' forces the use of forwarding. I put it as comment in the
> minimum example. If I should have attached a separate source file with just the
> operator*()-line replaced, I wish to express my apologies in advance.

The preprocessor strips comments out, so the workaround isn't in the attached
file.


The first problem is that your class lies, saying its 'reference' type is a
reference, but then returning something different from operator*.  That causes
a reference to be bound to a temporary, as you'll see if you compile with
-Wsystem-headers to enable warnings for code in the standard library headers.

The second problem is how reverse_iterator::operator* is defined:

      reference
      operator*() const
      {
    _Iterator __tmp = current;
    return *--__tmp;
      }

This creates a temporary iterator, then returns a reference to its d_val
member. By the time that's written to std::cout the temporary has been
destroyed.

For a bidirectional iterator the expression *r-- is required to be valid, so
your type fails that requirement.

What you've written is not an iterator, it's a generator.  It doesn't meet the
iterator requirements, so can't be used with std::reverse_iterator and
std::copy and other templates that require iterators.

[Bug libstdc++/51823] reverse iterator instantiated with POD type returns uninitialized values + work around

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51823

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|                            |INVALID

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-01-11 14:06:36 UTC ---
(In reply to comment #3)
> The preprocessor strips comments out, so the workaround isn't in the attached
> file.

Fixed by the new attachment 

> For a bidirectional iterator the expression *r-- is required to be valid, so
> your type fails that requirement.

Not fixed, this invalid.

[Bug libstdc++/51823] reverse iterator instantiated with POD type returns uninitialized values + work around

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51823

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |NEW
   Last reconfirmed|                            |2012-01-11
         Resolution|INVALID                     |
     Ever Confirmed|0                           |1

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-01-11 14:17:34 UTC ---
actually, my bad, even if your type did meet the requirements it wouldn't work,
and that *is* a libstdc++ bug

at some point between C++03 and C++11 the definition of
reverse_iterator::operator* was changed to clarify this, making libstdc++'s
implementation wrong.  The standard now says:

[ Note: This operation must use an auxiliary member variable rather than a
temporary variable to avoid returning a reference that persists beyond the
lifetime of its associated iterator. (See 24.2.) —end note ]

[Bug libstdc++/51823] reverse iterator instantiated with POD type returns uninitialized values + work around

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51823

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-01-11 14:37:27 UTC ---
That change was present as early as the Feb 2004 draft, n1577

Also related: http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#1052

[Bug libstdc++/51823] reverse iterator instantiated with POD type returns uninitialized values + work around

[marc.glisse at normalesup dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51823

--- Comment #7 from Marc Glisse <marc.glisse at normalesup dot org> 2012-01-11 15:16:58 UTC ---
Paolo started a discussion on this:
http://gcc.gnu.org/ml/libstdc++/2003-11/msg00089.html
but apparently the code wasn't changed. It is really sad that in most cases the
size of reverse_iterator is needlessly doubled just so some rare fancy
iterators can use it. And other fancy uses prevent from using a global instead
(even a tls).

For the special case of a Iota_iterator, when the C++ iterator concept is
eventually fixed (or for people who decide to ignore the requirement that
reference be a reference), reference should be int, not int const&, so
operator* would return by value.

[Bug libstdc++/51823] [DR 198] reverse iterator returns uninitialized values

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51823

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|reverse iterator            |[DR 198] reverse iterator
                   |instantiated with POD type  |returns uninitialized
                   |returns uninitialized       |values
                   |values + work around        |

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-01-11 15:25:42 UTC ---
Thanks, Marc, I'd failed to find the relevant DR number
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#198

We could specialize reverse_iterator on a trait that says the extra member
isn't needed, and then make that trait true for all iterator types defined in
the library.  The size would still change for
reverse_iterator<user_defined_iterator> but I don't see how else to meet the
requirement.

[Bug libstdc++/51823] [DR 198] reverse iterator returns uninitialized values

[marc.glisse at normalesup dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51823

--- Comment #9 from Marc Glisse <marc.glisse at normalesup dot org> 2012-01-11 15:46:44 UTC ---
(In reply to comment #8)
> We could specialize reverse_iterator on a trait that says the extra member
> isn't needed, and then make that trait true for all iterator types defined in
> the library.

I was just writing myself a note to try and get such a trait added to the
standard ;-)
I don't know if it is worth doing that optimization now (I was complaining on
the principle, I don't think I ever used reverse_iterator), depends on your
motivation...

[Bug libstdc++/51823] [DR 198] reverse iterator returns uninitialized values

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51823

--- Comment #10 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-01-11 15:59:43 UTC ---
I can work on it for GCC 4.8

[Bug libstdc++/51823] [DR 198] reverse iterator returns uninitialized values

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51823

--- Comment #11 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-01-14 15:43:52 UTC ---
Created attachment 26323
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=26323
implement DR 198

it's ugly, but it works

[Bug libstdc++/51823] [DR 198] reverse iterator returns uninitialized values

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51823

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |ABI

--- Comment #12 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-08-22 19:19:15 UTC ---
setting ABI keyword as this can't be properly fixed without an incompatible
change

[Bug libstdc++/51823] [DR 198] reverse iterator returns uninitialized values

[dave at boostpro dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51823

Dave Abrahams <dave at boostpro dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dave at boostpro dot com

--- Comment #13 from Dave Abrahams <dave at boostpro dot com> 2012-10-30 23:48:36 UTC ---
I think this bug is invalid, because the iterator being wrapped doesn't model
ForwardIterator due to I found 24.2.5 [forward.iterators]/6, where it says:

  If a and b are both dereferenceable, then a == b if and only if *a and
  *b are bound to the same object.

[Bug libstdc++/51823] [DR 198] reverse iterator returns uninitialized values

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51823

--- Comment #14 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-10-31 00:36:48 UTC ---
Thanks, Dave.  So IIUC that means a counting iterator or other iterator that
stores a value internally can only be an input iterator, and so can't be used
with reverse_iterator.

[Bug libstdc++/51823] [DR 198] [DR 2204] reverse iterator returns uninitialized values

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51823

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |SUSPENDED
            Summary|[DR 198] reverse iterator   |[DR 198] [DR 2204] reverse
                   |returns uninitialized       |iterator returns
                   |values                      |uninitialized values

--- Comment #15 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-12-13 12:23:46 UTC ---
Suspending pending resolution of Dave's issue:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3473.html#2204

[Bug libstdc++/51823] [DR 198] [DR 2204] reverse iterator returns uninitialized values

[dave at boostpro dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51823

--- Comment #16 from Dave Abrahams <dave at boostpro dot com> 2012-12-14 16:34:31 UTC ---
Normative text vs. non-normative note == no contest, IMO.  But I guess it
doesn't hurt to have the bug open if it doesn't mean any changes to the
library.

[Bug libstdc++/51823] [DR 198] [DR 2204] reverse iterator returns uninitialized values

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51823

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|SUSPENDED                   |RESOLVED
         Resolution|---                         |INVALID

--- Comment #17 from Jonathan Wakely <redi at gcc dot gnu.org> ---
The definition of reverse_iterator has been reverted to the C++03 version,
which does not use an extra member, so "stashing iterators" can not be used
with reverse_iterator.