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

Subject: Re: [boost] [range][stride] broken?
From: Neil Groves (neil_at_[hidden])
Date: 2010-12-26 06:18:21

On Sun, Dec 26, 2010 at 4:45 AM, Michel MORIN <mimomorin_at_[hidden]> wrote:

> Hi Neil,
> I'd like to make some comments on the updated strided_range.
>
> [Comments on implementation]
> 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.

> There might be a bug in decrement(). Let rng be a strided_range. Then,
> "boost::prior(rng.end())" and "boost::next(rng.begin(),
> boost::distance(rng)-1)"
> do not point to the same element.
>
>
I can't see a bug in the decrement operation. The underlying iterator is not
decremented beyond the beginning, and m_offset is altered appropriately. The
m_offset % stride_size is always 0, and equality is determined by the use of
the offset directly. If you can still see a defect, could I please trouble
you to provide a test case or further explanation?

> Neil Groves wrote:
> > I have committed a new
> > fix to the trunk and added your test cases
> The test case is credited to Maxim!
>
> I'll change this!

[Comments on design]
> Probably, you have introduced new concepts something like "Sizeable" range.
> The updated implementation of strided_range requires that an input range
> should be "Sizeable". But, IMHO, this is an over-requirement.
>  - For Single Pass and Forward Ranges, input ranges don't need to be
> "Sizeable".
>   strided_range can be implemented without requiring "Sizeable" ranges.
>
>  - For Bidirectional Range, there is a trade-off:
>   requiring "Sizeable" ranges allows us to implement decrement() that can
>   be safely applied to end(). But it seems more convenient for users that
>   "Non-Sizeable" ranges can be used for strided_range. Do you have
>   any rationale for adopting the design that requires "Sizeable" ranges?
>
>
Indeed it would be more convenient to have an implementation for Single Pass
and Forward Ranges that does not require constant-time sizeable. I intend to
add this later. 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. This is generally how I work, but in this case, the
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. Additionally because I know compatibility is
varied in this respect, I usually build and test on a larger number of
compilers and platforms which obviously takes additional time.

Regards,
> Michel
>

I would like to thank you for your feedback, it has been most helpful. I
hope to have the merge to trunk done fairly soon, and then a refined Single
Pass and Forward Pass implementation shortly afterwards.

Thanks,
Neil Groves