[range][stride] broken?
Consider the following test: std::vector<int> v; boost::push_back( v, boost::irange(0, 30) ); boost::copy( v, std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl << std::endl; for ( int i = 1; i <= 30; i++ ) { std::cout << std::setw(2) << i << ": "; boost::copy( v | boost::adaptors::strided(i), std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl; //std::cout << std::setw(2) << "" << ": "; //BOOST_FOREACH( int x, v | boost::adaptors::strided(i) ) // std::cout << x << ' '; //std::cout << std::endl; } Here is the output: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 1: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 2: 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 3: 0 3 6 9 12 15 18 21 24 27 4: 0 4 8 12 16 20 24 ///< where is 28? 5: 0 5 10 15 20 25 6: 0 6 12 18 24 7: 0 7 14 21 ///< where is 28? 8: 0 8 16 ///< where is 24? 9: 0 9 18 ///< where is 27? 10: 0 10 20 11: 0 11 ///< where is 22? ... 16: 0 ///< where is 16? etc If you uncomment the BOOST_FOREACH code, it crashes at stride=4 (prints 28 and then crashes): 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 1: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 2: 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 : 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 3: 0 3 6 9 12 15 18 21 24 27 : 0 3 6 9 12 15 18 21 24 27 4: 0 4 8 12 16 20 24 /usr/include/stlport-5.2.1/stlport/stl/debug/_iterator.h(170): STL assertion failure : _Incrementable(*this, __n, _Iterator_category()) : 0 4 8 12 16 20 24 28 unknown location:0: fatal error in "test": signal: SIGABRT (application abort requested) Nothing changes if I replace "v | boost::adaptors::strided(i)" with "boost::adaptors::stride(v,i)". It's Boost 1.45.0 on STLPort 5.2.1, gcc 4.4. IF I switch from std::vector to boost::array, BOOST_FOREACH just doesn't stop and keeps printing memory until crash, so I don't think it's an STLPort problem. Am I doing anything wrong, or range::stride is broken? Thanks, Maxim
Hi Maxim, Maxim Yanchenko wrote:
Am I doing anything wrong, or range::stride is broken?
I think it's a bug of strided_range. Could you please create a ticket for this at https://svn.boost.org/trac/boost? (It would be better to provide a minimal test case.) Quick hack to fix this is changing the strided_range's constructor // boost/range/adaptor/strided.hpp Line 89 public: template< typename Difference > strided_range(Difference stride, Rng& rng) : super_t(make_strided_iterator(boost::begin(rng), stride), make_strided_iterator(boost::end(rng), stride)) { } to public: template< typename Difference > strided_range(Difference stride, Rng& rng) : super_t( make_strided_iterator(boost::begin(rng), stride) , make_strided_iterator(boost::begin(rng) + (boost::size(rng) + stride - 1) / stride * stride, stride) ) { } Regards, Michel
Michel MORIN <mimomorin <at> gmail.com> writes:
Maxim Yanchenko wrote:
Am I doing anything wrong, or range::stride is broken?
I think it's a bug of strided_range. Could you please create a ticket for this at https://svn.boost.org/trac/boost? (It would be better to provide a minimal test case.)
Thanks for confirmation, created a ticket: https://svn.boost.org/trac/boost/ticket/5014
On Wed, Dec 22, 2010 at 11:20 AM, Maxim Yanchenko <maximyanchenko@yandex.ru>wrote:
Michel MORIN <mimomorin <at> gmail.com> writes:
Maxim Yanchenko wrote:
Am I doing anything wrong, or range::stride is broken?
I think it's a bug of strided_range. Could you please create a ticket for this at https://svn.boost.org/trac/boost? (It would be better to provide a minimal test case.)
Thanks for confirmation, created a ticket: https://svn.boost.org/trac/boost/ticket/5014
I wanted to apologize for this mistake. I can assure you that I am working on this right now. I will submit a fix to boost-trunk today. After a couple of days of passes on boost-trunk I shall merge to boost-release. Sorry for the error and any inconvenience it may have caused. Regards, Neil Groves
Neil Groves <neil <at> grovescomputing.com> writes:
On Wed, Dec 22, 2010 at 11:20 AM, Maxim Yanchenko
Michel MORIN <mimomorin <at> ...> writes:
Maxim Yanchenko wrote:
Am I doing anything wrong, or range::stride is broken? I think it's a bug of strided_range. Thanks for confirmation, created a ticket: https://svn.boost.org/trac/boost/ticket/5014 I wanted to apologize for this mistake. I can assure you that I am working on this right now. I will submit a fix to boost-trunk today. After a couple of days of passes on boost-trunk I shall merge to boost-release.
Thanks, Neil, great news. Just in case - why stride works for Random Access Sequences only? Why can't I use it for Input sequence like istream_range (e.g. "process every 10th word")? I hope it's already in your Todo list. Also, I don't see any easy way to skip x first elements. "slice" doesn't help as I need to know size that I might not know in advance, for example, in this setup: v | filtered(by) | sliced(5,???) And similar question about skipping n elements at the end of the sequence. Basically, it would be great to have Python-style slice, as it's concise and easy to use, like here:
a=[1,2,3,4,5,6,7,8,9,10] a[3:-3] [4, 5, 6, 7]
Thanks, Maxim
Hi Neil, Neil Groves wrote:
I will submit a fix to boost-trunk today. After a couple of days of passes on boost-trunk I shall merge to boost-release.
The ticket (#5014) just has been closed, but the test case in the ticket still prints out wrong results. This is because, when constructing strided_range, the end iterator of an input range should advance forward rather than backward. Advancing the end iterator forward might cause overflow, so implementing strided_iterator needs some care to handle "overflowed" end iterators. I can think of the following implementation: // Partial specialization (for Random Access Range) template <typename BaseIterator> class strided_iterator<BaseIterator, boost::random_access_traversal_tag> : public iterator_facade</* ... */> { public: // ... private: // iterator_facade core operations reference dereference() const { return *(m_begin + m_stride * m_offset); } bool equal(strided_iterator const& other) const { return m_begin == other.m_begin && m_offset == other.m_offset; } void increment() { ++m_offset; } void decrement() { --m_offset; } void advance(difference_type n) { m_offset += n; } difference_type distance_to(strided_iterator const& other) const { other.m_offset - m_offset; } // data BaseIterator m_begin; // the begin iterator of an input range difference_type m_offset; // the number of strides taken by this iterator difference_type m_stride; }; For Single Pass Range (including Forward and Bidirectional Ranges), I think it's better to use a different implementation to avoid using size() function. To achieve this, strided_iterator stores the end iterator of the input range: (When constructing strided_range, the end iterator of an input range does not need to be advanced anymore in this implementation.) // Primary template (for Single Pass, Forward and Bidirectional Ranges) template <typename BaseIterator, typename TraversalCategory> class strided_iterator : public iterator_adaptor</* ... */> { public: // ... private: // adapted core operations void increment() { difference_type i = 0; do { ++this->base_reference(); ++i; } while (this->base_reference() != m_end && i < m_stride); } // data difference_type m_stride; BaseIterator m_end; }; I don't know whether we should implement decrement() function for Bidirectional Range. Regards, Michel
On Thu, Dec 23, 2010 at 7:31 PM, Michel MORIN <mimomorin@gmail.com> wrote:
Hi Neil,
Neil Groves wrote:
I will submit a fix to boost-trunk today. After a couple of days of passes on boost-trunk I shall merge to boost-release.
The ticket (#5014) just has been closed, but the test case in the ticket still prints out wrong results.
You are correct. The change I made yesterday on the trunk for the strided adaptor is fundamentally flawed in a number of ways. I have committed a new fix to the trunk and added your test cases, plus additional test cases to cover all of the flaws I noticed from yesterdays changes.
I don't know whether we should implement decrement() function for Bidirectional Range.
My new implementation works safely for all traversal types, and correctly and safely handles decrement.
Regards, Michel
Please accept my apologies for the previous 'intellectually challenged' commit. Regards, Neil Groves
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)"? 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. Neil Groves wrote:
I have committed a new fix to the trunk and added your test cases The test case is credited to Maxim!
[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? Regards, Michel
On Sun, Dec 26, 2010 at 4:45 AM, Michel MORIN <mimomorin@gmail.com> 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
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
participants (3)
-
Maxim Yanchenko -
Michel MORIN -
Neil Groves