Re: [boost] [range][stride] broken?

Subject: Re: [boost] [range][stride] broken?
From: Michel MORIN (mimomorin_at_[hidden])
Date: 2010-12-26 20:08:55

Hi Neil,

The following message was written before I updated to r67461.
(A bug in increment() is FIXED in r67461.)

Neil Groves wrote:
>> increment() can generate overflowed iterator:
>>     // boost/range/adaptor/strided.hpp
>>     void increment()
>>     {
>>         m_offset += m_stride;
>>         if (m_offset <= m_max_offset)
>>             std::advance(this->base_reference(), m_stride);
>>     }
>> Do you mean "if (m_offset < m_max_offset)"?
>
> No, I really do mean <=. m_max_offset is the maximum valid offset of the
> last (one passed the end) iterator from the first. This works as verified by
> the test cases. It advances the iterator to the last of the half-open range
> at the limit which is fine.

increment() might try to advance past-the-end iterators. This is problematic.
For example, trying to advance past-the-end iterators of std::forward_list
(in GCC 4.4 C++0x mode) results in crashes. See the code in test_increment.cpp.
Also note that, in the code, I defined a new overload of boost::size(rng) for
std::forward_list since we are not allowed to add a new function (i.e.
range_calculate_size(rng)) in namespace std.

> I can't see a bug in the decrement operation.

Then I think a bug is in the strided_range constructor.

> If you can still see a defect, could I please trouble
> you to provide a test case or further explanation?

OK. Consider the following code:

    int ar[3] = {0, 1, 2};
    boost::strided_range<int[3]> rng = ar | boost::adaptors::strided(2);

Then

    *--rng.end() != *boost::next(rng.begin(), boost::distance(rng) - 1)

IMO, this is a bug. For full code, see test_decrement.cpp.

> I would like to thank you for your feedback, it has been most helpful.

Hey, it's me to say thank you :-)
I really appreciate your work and I love range adaptors!

> For now the recent commits fix a Show Stopper defect with
> the minimum code change and all pre-conditions are weaker than the previous
> release. Therefore this allows me to get a change merged into the release
> stream with a very low risk. Subsequent improvements will simply come in
> subsequent commits.

Sounds good.

> strided_iterator implementation needs to be quite different for the Single
> Pass and Forward Ranges and this means working with compiler features that I
> know to vary across compilers hence the risk was quite high that by
> implementing this feature that, for some compilers, there would be
> regressions on the trunk.

Yep, we need partial specialization of class templates.

Regards,
Michel