c++ - Reverse iterator returns garbage when optimized

Question

I have a AsIterator template class which takes a numeric-like type, in this example just an int, and converts it into an iterator (++ and -- increment and decrement the number, and operator* just returns a reference to it).

This works fine unless it's wrapped into a std::reverse_iterator and compiled with any optimization (-O is enough). When I optimize the binary, the compiler strips out the dereference call to the reverse_iterator and replaces it with some weird value. It must be noted that it still makes the correct number of iterations. It's just the value obtained by reverse iterator that is garbage.

Consider the following code:

#include <iterator>
#include <cstdio>

template<typename T>
class AsIterator : public std::iterator<std::bidirectional_iterator_tag, T> {
    T v;
public:
    AsIterator(const T & init) : v(init) {}

    T &operator*() { return v; }

    AsIterator &operator++() { ++v; return *this; }
    AsIterator operator++(int) { AsIterator copy(*this); ++(*this); return copy; }
    AsIterator &operator--() { --v; return *this; }
    AsIterator operator--(int) { AsIterator copy(*this); --(*this); return copy; }

    bool operator!=(const AsIterator &other) const {return v != other.v;}
    bool operator==(const AsIterator &other) const {return v == other.v;}
};

typedef std::reverse_iterator<AsIterator<int>> ReverseIt;

int main() {
    int a = 0, b = 0;
    printf("Insert two integers: ");
    scanf("%d %d", &a, &b);
    if (b < a) std::swap(a, b);

    AsIterator<int> real_begin(a);
    AsIterator<int> real_end(b);
    for (ReverseIt rev_it(real_end); rev_it != ReverseIt(real_begin); ++rev_it) {
        printf("%d
", *rev_it);
    }
    return 0;
}

This should supposingly loop down from the highest inserted number to the lowest and print them, such as in this run (compiled with -O0):

Insert two integers: 1 4 
3
2
1

What I get with -O is instead:

Insert two integers: 1 4 
1
0
0

You can try it online here; the numbers may vary but they're always "wrong" when optimizing the binary.

---

What I've tried:

• hardcoding the input integers is enough to produce the same result;
• the issue persists with gcc 5.4.0 and clang 3.8.0, also when using libc++;
• making all the objects const (i.e. returning const int &, and declaring all variables as such) doesn't fix it;
• using the reverse_iterator in the same way on for example some std::vector<int> works fine;
• if I just use AsIterator<int> for a normal forward or backward loop it works fine.
• in my tests, the constant 0 that is printed is actually hardcoded by the compiler, the calls to printf all look like this when compiled with -S -O:

    movl    $.L.str.2, %edi  # .L.str.2 is "%d
"
    xorl    %eax, %eax
    callq   printf

Given the consistency of clang and gcc's behavior here I am pretty sure they're doing it right and I misunderstood, but I really can't see it.

question from:https://stackoverflow.com/questions/41898473/reverse-iterator-returns-garbage-when-optimized

Answer 1

Looking at std::reverse_iterator's libstdc++ implementation reveals something interesting:

  /**
   *  @return  A reference to the value at @c --current
   *
   *  This requires that @c --current is dereferenceable.
   *
   *  @warning This implementation requires that for an iterator of the
   *           underlying iterator type, @c x, a reference obtained by
   *           @c *x remains valid after @c x has been modified or
   *           destroyed. This is a bug: http://gcc.gnu.org/PR51823
  */
  _GLIBCXX17_CONSTEXPR reference
  operator*() const
  {
    _Iterator __tmp = current;
     return *--__tmp;
  }

The @warning section tells us that a requirement of the underlying iterator type is that *x must remain valid even after the underlying iterator is modified/destroyed.

Looking at the mentioned bug link reveals more interesting information:

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 by Jonathan Wakely (2012)

So it looks like a bug... but at the end of the topic:

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.

comment by Jonathan Wakely (2014)

So it seems that using std::reverse_iterator with "stashing iterators" does indeed lead to UB.

---

Looking at the DR 2204: "reverse_iterator should not require a second copy of the base iterator" further clarifies the issue:

This note in 24.5.1.3.4 [reverse.iter.op.star]/2:

[ 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 ]

[my note: I think that the above note would fix your UB issue]

is incorrect because such iterator implementations are ruled out by 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.