[boost] [iterator] Silent-but-deadly bug in iterator_facade category

[Gabriel Redner]

Hi folks,

I've stumbled across a nasty problem with iterator_facade in which
code which appears correct and compiles fine can cause runtime
problems. Consider an iterator_facade which just wraps a random
access iterator and applies a transformation to it:

char transform(int i) { return 'a'; }

struct my_iterator
: public boost::iterator_facade<my_iterator,
char, // value_type
std::random_access_iterator_tag, // ***
char> // reference
{
my_iterator(const std::vector<int>::iterator& it) : _it(it) {}

char dereference() const { return transform(*_it); }
bool equal(const my_iterator& other) const { return _it == other._it; }
void increment() { ++_it; }
void decrement() { --_it; }
void advance(int n) { std::advance(_it, n); }
int distance_to(const my_iterator& other) const { return other._it - _it; }

private:
std::vector<int>::iterator _it;
};

Now if I have an STL-style function which is overloaded on the
iterator category, clearly the random-access version will be selected.

template <typename TIterator>
void funcImpl(TIterator it, std::input_iterator_tag)
{ std::cerr << "Running func treating 'it' as input iterator\n"; }

template <typename TIterator>
void funcImpl(TIterator it, std::random_access_iterator_tag)
{ std::cerr << "Running func treating 'it' as random access iterator\n"; }

template <typename TIterator>
void func(TIterator it)
{ funcImpl(it, typename
std::iterator_traits<TIterator>::iterator_category()); }

In the line marked ***, the docs suggest I should use
boost::random_access_traversal_tag instead of
std::random_access_iterator_tag - but when I do, the program no longer
selects the random access version of 'func', choosing the forward-only
version instead! The iterator_category of my_iterator ends up as:

boost::detail::iterator_category_with_traversal<std::input_iterator_tag,
boost::random_access_traversal_tag>

The reason I called this a 'deadly' bug is that std::advance is
suddenly a deathtrap:

std::advance(it, -1);

This is fine and legal for random access iterators, but if the
forward-only version gets called instead, the behavior is undefined
(on my system, it loops endlessly). The compiler doesn't complain
either way - the problem surfaces only at runtime.

Does the problem lie with iterator_category_with_traversal? It looks
like it's intended in this case to be convertible to either
std::input_iterator_tag or std::random_access_iterator_tag, but
clearly something is wrong with the latter conversion. Any ideas?

Thanks,
-Gabe

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[paul Fultz]

>

> Does the problem lie with iterator_category_with_traversal?  It looks
> like it's intended in this case to be convertible to either
> std::input_iterator_tag or std::random_access_iterator_tag, but
> clearly something is wrong with the latter conversion.  Any ideas?
>

The problem lies in the fact that your iterator when it calls `dereference()`,
returns something that is not a reference(ie char). For it to be a
`std::random_access_iterator_tag` it must a reference. That is,
`iterator_traits<X>::reference` must be an actual reference. So therefore your
iterator is given the `std::input_iterator_tag`, since it is the only iterator
category that doesn't require `dereference()` to return a reference. So then
when you call:

> std::advance(it, -1);

With an input iterator, it will, depending on the implementation and the build
type, either fail with a runtime assertion, or go into an infinite loop.

Thanks,
Paul

[Gabriel Redner]

Hi Paul,

Thanks for your reply.

> For it to be a
> `std::random_access_iterator_tag` it must a reference. That is,
> `iterator_traits<X>::reference` must be an actual reference.

Can you point me at a reference (pun not intended) for this
requirement? The sites I've looked at don't mention this [1-3]. Is
it a requirement for, say, bidirectional iterators too? Your message
makes it sound like this is specific to random access iterators.

If the iterator's reference must be a real reference type, then why
does iterator_facade not check this at compile time?

And in any case, isn't this a flaw? my_iterator can be advanced etc.
in constant time - why should the STL be forced to use a
possibly-suboptimal overload of some algorithm on account of the
reference type?

Confused,
-Gabe

[1] http://www.cplusplus.com/reference/iterator/RandomAccessIterator/
[2] http://en.cppreference.com/w/cpp/concept/RandomAccessIterator
[3] http://www.sgi.com/tech/stl/RandomAccessIterator.html

[Stephan T. Lavavej]

[Gabriel Redner]

> Can you point me at a reference (pun not intended) for this
> requirement? The sites I've looked at don't mention this [1-3]. Is
> it a requirement for, say, bidirectional iterators too?

> [1] http://www.cplusplus.com/reference/iterator/RandomAccessIterator/
> [2] http://en.cppreference.com/w/cpp/concept/RandomAccessIterator
> [3] http://www.sgi.com/tech/stl/RandomAccessIterator.html

Only Standards - and Working Papers that will become Standards when they grow up - are authoritative.

The latest Working Paper is N3485, http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3485.pdf

24.2.7 [random.access.iterators]/1: "A class or pointer type X satisfies the requirements of a random access iterator if, in addition to satisfying the requirements for bidirectional iterators, [...]"

24.2.6 [bidirectional.iterators]/1: "A class or pointer type X satisfies the requirements of a bidirectional iterator if, in addition to satisfying the
requirements for forward iterators, [...]"

24.2.5 [forward.iterators]/1: "A class or pointer type X satisfies the requirements of a forward iterator if
[...]
- if X is a mutable iterator, reference is a reference to T; if X is a const iterator, reference is a reference to const T,
[...]"

Stephan T. Lavavej
Visual C++ Libraries Developer

[paul Fultz]

>
> And in any case, isn't this a flaw?  my_iterator can be advanced etc.
> in constant time - why should the STL be forced to use a
> possibly-suboptimal overload of some algorithm on account of the
> reference type?
>

This exactly the problem that Boost.Iterator is trying to address. It
separates access and traversal. So, whereas the random access iterator
category requires an lvalue access with random access traversal, in
Boost.Iterator you can specify them separately. Unfortunately, the proposal to
accept this into C++ was never accepted. There was talk of relaxing the
requirements for C++11, but that never happened. And I dont think theres any
talk of it for C++14 that I know of.


Thanks,
Paul

[Nathan Ridge]

> > For it to be a
> > `std::random_access_iterator_tag` it must a reference. That is,
> > `iterator_traits<X>::reference` must be an actual reference.
>
> Can you point me at a reference (pun not intended) for this
> requirement? The sites I've looked at don't mention this [1-3]. Is
> it a requirement for, say, bidirectional iterators too? Your message
> makes it sound like this is specific to random access iterators.

It is a requirement for forward iterators and higher. The
authoritative source for the requirement is the C++ standard.

In the 2003 standard, section 24.1.3 has a table listing requirements
for forward iterators. One of them is that if 'a' if a forward
iterator, '*a' is a valid expression and has type 'T&', where T is
the iterator's value type.

In the 2011 standard, it's even more clear: section 24.2.5 states
that one of the requirements for X to be a forward iterator is that

"if 'X' is a mutable iterator, 'reference' is a reference to 'T';

if 'X' is a const iterator, 'reference' is a reference to 'const T'".

Regarding the sites you linked to, the completeness and accuracy
of their information is to be taken with a grain of salt, but I do
see [1] list as a requirement for forward, bidirectional, and
random access iterators that they "can be deferenced as an lvalue",
which effectively requires that 'reference' be a reference type.

> And in any case, isn't this a flaw? my_iterator can be advanced etc.
> in constant time - why should the STL be forced to use a
> possibly-suboptimal overload of some algorithm on account of the
> reference type?

Yes, it's a flaw. The STL unnecessarily conflates iterator traversal
and iterator value access in its iterator categories. This is why
Boost has developed, and uses, its own iterator concepts. See [2].

You can take advantage of Boost's iterator concepts by modifying
'func' from your original post to dispatch on
boost::iterator_traversal<TITerator>::type() instead of
std::iterator_traits<TIterator>::iterator_category(), since traversal
is the relevant aspect in that case.

> If the iterator's reference must be a real reference type, then why
> does iterator_facade not check this at compile time?

It "must" be a real reference type only from the point of view of
the STL's broken iterator concepts. Boost.Iterator is perfectly
happy to let you write an iterator whose traversal is random-access
but whose 'reference' is not a reference type, which will then be
considered an 'input iterator' by the STL.

Hope that helps.

Regards,
Nate

[1] http://www.cplusplus.com/reference/iterator/ForwardIterator/
    http://www.cplusplus.com/reference/iterator/BidirectionalIterator/
    http://www.cplusplus.com/reference/iterator/RandomAccessIterator/

[2] http://www.boost.org/doc/libs/1_53_0/libs/iterator/doc/new-iter-concepts.html

[Marc Glisse]

On Tue, 7 May 2013, Nathan Ridge wrote:

> Yes, it's a flaw. The STL unnecessarily conflates iterator traversal
> and iterator value access in its iterator categories. This is why
> Boost has developed, and uses, its own iterator concepts. See [2].

And those concepts are "incompatible" with algorithms written for the
standard concepts, so we are left with 2 choices:
- don't use the STL directly, use the boost implementations instead
- don't use boost iterators (well, a few classes are usable, but not
transform_iterator for instance)

In my experience, the easiest way to handle this painful reference
requirement is to ignore it and pretend that the standard categories are
only about traversal. I've never had anything break because of this.

--
Marc Glisse

[Nathan Ridge]

> In my experience, the easiest way to handle this painful reference
> requirement is to ignore it and pretend that the standard categories are
> only about traversal. I've never had anything break because of this.

Is the OP's problem not an example of pretending that the standard
iterator categories are only about traversal and having something
break as a result?

Regards,
Nate

[Marc Glisse]

On Tue, 7 May 2013, Nathan Ridge wrote:

>> In my experience, the easiest way to handle this painful reference
>> requirement is to ignore it and pretend that the standard categories are
>> only about traversal. I've never had anything break because of this.
>
> Is the OP's problem not an example of pretending that the standard
> iterator categories are only about traversal and having something
> break as a result?

As far as I can tell, the OP's problem only appeared when he started using
boost traversal iterator categories, and things were working fine when he
had random_access_iterator_tag (violating the reference requirement).

Did I misunderstand his post?

--
Marc Glisse

[Nathan Ridge]

> >> In my experience, the easiest way to handle this painful reference
> >> requirement is to ignore it and pretend that the standard categories are
> >> only about traversal. I've never had anything break because of this.
> >
> > Is the OP's problem not an example of pretending that the standard
> > iterator categories are only about traversal and having something
> > break as a result?
>
> As far as I can tell, the OP's problem only appeared when he started using
> boost traversal iterator categories, and things were working fine when he
> had random_access_iterator_tag (violating the reference requirement).

Well, you didn't say anything about using standard iterator categories
in lieu of Boost ones when using Boost classes like iterator_facade.

If you're saying that doing that together with ignoring the reference
requirement has kept you out of trouble, I take your word for it :)

Regards,
Nate

[Gabriel Redner]

Hi folks,

Stephan T. Lavavej:

> if X is a mutable iterator, reference is a reference to T;

> if X is a const iterator, reference is a reference to const T,

If I'm reading this right, then an iterator whose 'reference' is not a
reference is not an std iterator at all.

If so, then my question (not necessarily to you, but to everyone)
becomes: why does the Iterator library tag such an iterator with
std::input_iterator_tag? Isn't this strictly wrong?

Nathan Ridge:

> You can take advantage of Boost's iterator concepts by modifying
> 'func' from your original post to dispatch on
> boost::iterator_traversal<TITerator>::type() instead of
> std::iterator_traits<TIterator>::iterator_category(), since traversal
> is the relevant aspect in that case.

'func' exists just to illustrate the issue that these iterators
interact badly with the STL. I realize that I could dispatch on the
boost traversal concepts, but my concern was interoperability with STL
algorithms.

Marc Glisse:

> In my experience, the easiest way to handle this painful reference
> requirement is to ignore it and pretend that the standard categories
> are only about traversal. I've never had anything break because of this.

+
Nathan Ridge:

> Is the OP's problem not an example of pretending that the standard
> iterator categories are only about traversal and having something
> break as a result?

I would say that my problem was misunderstanding what iterator_facade
is trying to do. It's not clearly explained how the
CategoryOrTraversal argument is translated into the
interator_category, and in what cases the result is different from
what one would intuitively expect. The docs state over and over again
how one of the goals of the library is easy interoperability of boost
iterators with STL algorithms, but the gotchas seem to be hidden or
not mentioned at all.

Thanks everyone for the information.

-Gabe

[Jeffrey Lee Hellrung, Jr.]

On Tue, May 7, 2013 at 7:58 AM, Gabriel Redner <gre...@gmail.com> wrote:

> Hi folks,
>
> Stephan T. Lavavej:
> > if X is a mutable iterator, reference is a reference to T;
> > if X is a const iterator, reference is a reference to const T,
>
> If I'm reading this right, then an iterator whose 'reference' is not a
> reference is not an std iterator at all.
>
> If so, then my question (not necessarily to you, but to everyone)
> becomes: why does the Iterator library tag such an iterator with
> std::input_iterator_tag? Isn't this strictly wrong?
>

You snipped the relevant context: The above applies to ForwardIterators,
not to InputIterators or OutputIterators.

[...]

- Jeff

[Gabriel Redner]

> You snipped the relevant context: The above applies to ForwardIterators,
> not to InputIterators or OutputIterators.

Ah ok, I see. I don't see why it should be that way, but I see that it is.

The more I learn about iterators, the less I understand :-\

Thanks,
-Gabe

[Jeffrey Lee Hellrung, Jr.]

On Tue, May 7, 2013 at 8:26 AM, Gabriel Redner <gre...@gmail.com> wrote:

> > You snipped the relevant context: The above applies to ForwardIterators,
> > not to InputIterators or OutputIterators.
>
> Ah ok, I see. I don't see why it should be that way, but I see that it is.
>

Welcome to the club :/

- Jeff

[Dave Abrahams]

on Tue May 07 2013, Gabriel Redner <gredner-AT-gmail.com> wrote:

> Hi folks,
>
> Stephan T. Lavavej:
>> if X is a mutable iterator, reference is a reference to T;
>> if X is a const iterator, reference is a reference to const T,
>
> If I'm reading this right, then an iterator whose 'reference' is not a
> reference is not an std iterator at all.

It might be an input iterator or an output iterator, but it's not a
forward iterator.

> If so, then my question (not necessarily to you, but to everyone)
> becomes: why does the Iterator library tag such an iterator with
> std::input_iterator_tag? Isn't this strictly wrong?

No, it's strictly correct.


--
Dave Abrahams