Re: [boost] [gil] Is bit_aligned_pixel_iterator a standard conformant random access iterator?

Subject: Re: [boost] [gil] Is bit_aligned_pixel_iterator a standard conformant random access iterator?
From: David Abrahams (dave_at_[hidden])
Date: 2010-06-01 11:20:12

At Mon, 31 May 2010 23:25:44 +0000 (UTC),
Adam Merz wrote:
> 
> To be clear, it's not that MSVC10 doesn't understand that
> bit_aligned_pixel_iterator is a random access iterator, it's that
> bit_aligned_pixel_iterator *isn't* a random access iterator. I.e.,
> std::iterator_traits< bit_aligned_pixel_iterator >::iterator_category is
> std::input_iterator_tag on every compiler/platform. 

The proxy reference alone is enough to make it
not-a-random-access-iterator.

> It's just that MSVC10 refuses to instantiate std::copy given a
> destination iterator categorized as an input iterator (which is a
> good thing). If GIL had a regression test with a static assertion
> that boost::is_same< std::iterator_traits<
> bit_aligned_pixel_iterator<...> >::iterator_category,
> std::random_access_iterator_tag >::value == true, this would have
> been caught long ago. (hint, hint)

Well, this iterator could also legitimately be classified as an
output_iterator.  The author of the iterator could multiply-inherit
the iterator's tag from std::output_iterator_tag

> One perspective is that the bug here is that bit_aligned_pixel_iterator is
> trying to pass itself off as a random access iterator in the first place,
> despite the fact that it returns a proxy object rather than an actual
> reference, violating the standard's requirements for forward iterators.
> However, since it appears to work properly on all tested toolsets, that could
> be deemed an acceptable flaw, in which case the proper fix is to pass
> iterator_facade a category of std::random_access_iterator_tag rather than
> boost::random_access_traversal_tag. Easy enough. :-]

That would be the “proper” way to do it (if we ignore the fact that
you're lying to the standard library).

> Another perspective is that the bug here is caused by iterator_facade silently
> decaying 

It's not “silently decaying” into anything.  It's following the rules.

> into an input iterator despite being told to function as a random
> access iterator. 

The iterator has been told to allow random access traversal, not to
pass itself off as something it isn't.   If you want to tell it the
latter, just force it to use random_access_iterator_tag

> This is documented behavior, so it's not a bug in and of
> itself, but the fact that it does so *silently* 

What alternative would you suggest?

> is a questionable design issue given that it's negatively affected
> at least two released libraries so far. I'm not sure what mechanism
> could be used to make the decay 'noisy' rather than silent, but this
> is clearly a gotcha for users of iterator_facade. 

If there's a gotcha there, it should be handled with documentation.

> Also, the fact that it decays into an input iterator rather than an
> input/output iterator seems arbitrary and less than ideal. Why
> doesn't it decay into boost::detail::input_output_iterator_tag? At
> least then it could be used as a destination for std::copy.

There's no decay.  You simply haven't done anything to tell 
iterator_facade that the iterator is writable.  Derive a tag from all the
appropriate parts and it will do “what you want.”

> Keep in mind that the issue surrounding bit_aligned_pixel_iterator applies in
> an identical manner to boost::detail::multi_array::array_iterator, as brought
> up by Thomas Klimpel multiple times now, most recently here:
> http://lists.boost.org/Archives/boost/2010/05/167125.php So whatever solution
> is deemed acceptable for bit_aligned_pixel_iterator should be applied to
> array_iterator as well, if possible.

FWIW, I advocate lying to the standard library here.  The “new
iterator categories” were somewhat mis-designed and will probably be
deprecated sometime in the future anyway.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com