User account creation filtered due to spam.

Bug 51823 - [DR 198] [DR 2204] reverse iterator returns uninitialized values
Summary: [DR 198] [DR 2204] reverse iterator returns uninitialized values
Status: RESOLVED INVALID
Alias: None
Product: gcc
Classification: Unclassified
Component: libstdc++ (show other bugs)
Version: 4.6.1
: P3 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords: ABI
Depends on:
Blocks:
 
Reported: 2012-01-11 12:58 UTC by Jakob van Bethlehem
Modified: 2014-02-19 21:02 UTC (History)
4 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2012-01-11 00:00:00


Attachments
*.i* output of minimal example that reproduces the bug (61.25 KB, application/octet-stream)
2012-01-11 12:58 UTC, Jakob van Bethlehem
Details
Minimal example that reproduces bug, but with proper call-signature for operator*() (ie: returning reference) (61.25 KB, application/octet-stream)
2012-01-11 13:40 UTC, Jakob van Bethlehem
Details
implement DR 198 (2.94 KB, patch)
2012-01-14 15:43 UTC, Jonathan Wakely
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Jakob van Bethlehem 2012-01-11 12:58:25 UTC
Created attachment 26299 [details]
*.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.
Comment 1 Jonathan Wakely 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
Comment 2 Jakob van Bethlehem 2012-01-11 13:40:18 UTC
Created attachment 26300 [details]
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.
Comment 3 Jonathan Wakely 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.
Comment 4 Jonathan Wakely 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.
Comment 5 Jonathan Wakely 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 ]
Comment 6 Jonathan Wakely 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
Comment 7 Marc Glisse 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.
Comment 8 Jonathan Wakely 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.
Comment 9 Marc Glisse 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...
Comment 10 Jonathan Wakely 2012-01-11 15:59:43 UTC
I can work on it for GCC 4.8
Comment 11 Jonathan Wakely 2012-01-14 15:43:52 UTC
Created attachment 26323 [details]
implement DR 198

it's ugly, but it works
Comment 12 Jonathan Wakely 2012-08-22 19:19:15 UTC
setting ABI keyword as this can't be properly fixed without an incompatible change
Comment 13 Dave Abrahams 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.
Comment 14 Jonathan Wakely 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.
Comment 15 Jonathan Wakely 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
Comment 16 Dave Abrahams 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.
Comment 17 Jonathan Wakely 2014-02-19 21:02:27 UTC
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.