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

Subject: [boost] [iterator] Silent-but-deadly bug in iterator_facade category
From: Gabriel Redner (gredner_at_[hidden])
Date: 2013-05-06 16:17:58

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