[C++] Add operator--() to RunEndEncodedArraySpan::Iterator and make it stop violating loop invariants #34893
Comments
|
take |
zeroshade
pushed a commit
that referenced
this issue
Apr 12, 2023
…st on backwards iteration (#34896) ### Rationale for this change The value of `RunEndEncodedArraySpan::Iterator::physical_pos_` from the instance returned by `RunEndEncodedArraySpan::end()` is smaller (by 1) than the results of successive applications of `operator++()` until `logical_pos_` reaches the logical length of the run-end encoded array. To support backwards iteration, the `Iterator` returned by `RunEndEncodedArraySpan::end()` should be well-formed. There was no `operator--()` in `RunEndEncodedArraySpan::Iterator` before this PR, so one can't go backwards from `end()` and this latent bug doesn't manifest. ### What changes are included in this PR? - Addition of `RunEndEncodedArraySpan::Iterator::operator--()` - Addition of `MergedRunsIterator::operator--()` - Rename `isEnd()` to `is_end()` (it was a code-style violation) - More test cases ### Are these changes tested? By existing and new unit tests. ### Are there any user-facing changes? A public function -- `isEnd` -- was renamed, but this code hasn't been released yet, so it's OK. * Closes: #34893 Authored-by: Felipe Oliveira Carvalho <felipekde@gmail.com> Signed-off-by: Matt Topol <zotthewizard@gmail.com>
liujiacheng777
pushed a commit
to LoongArch-Python/arrow
that referenced
this issue
May 11, 2023
…manifest on backwards iteration (apache#34896) ### Rationale for this change The value of `RunEndEncodedArraySpan::Iterator::physical_pos_` from the instance returned by `RunEndEncodedArraySpan::end()` is smaller (by 1) than the results of successive applications of `operator++()` until `logical_pos_` reaches the logical length of the run-end encoded array. To support backwards iteration, the `Iterator` returned by `RunEndEncodedArraySpan::end()` should be well-formed. There was no `operator--()` in `RunEndEncodedArraySpan::Iterator` before this PR, so one can't go backwards from `end()` and this latent bug doesn't manifest. ### What changes are included in this PR? - Addition of `RunEndEncodedArraySpan::Iterator::operator--()` - Addition of `MergedRunsIterator::operator--()` - Rename `isEnd()` to `is_end()` (it was a code-style violation) - More test cases ### Are these changes tested? By existing and new unit tests. ### Are there any user-facing changes? A public function -- `isEnd` -- was renamed, but this code hasn't been released yet, so it's OK. * Closes: apache#34893 Authored-by: Felipe Oliveira Carvalho <felipekde@gmail.com> Signed-off-by: Matt Topol <zotthewizard@gmail.com>
ArgusLi
pushed a commit
to Bit-Quill/arrow
that referenced
this issue
May 15, 2023
…manifest on backwards iteration (apache#34896) ### Rationale for this change The value of `RunEndEncodedArraySpan::Iterator::physical_pos_` from the instance returned by `RunEndEncodedArraySpan::end()` is smaller (by 1) than the results of successive applications of `operator++()` until `logical_pos_` reaches the logical length of the run-end encoded array. To support backwards iteration, the `Iterator` returned by `RunEndEncodedArraySpan::end()` should be well-formed. There was no `operator--()` in `RunEndEncodedArraySpan::Iterator` before this PR, so one can't go backwards from `end()` and this latent bug doesn't manifest. ### What changes are included in this PR? - Addition of `RunEndEncodedArraySpan::Iterator::operator--()` - Addition of `MergedRunsIterator::operator--()` - Rename `isEnd()` to `is_end()` (it was a code-style violation) - More test cases ### Are these changes tested? By existing and new unit tests. ### Are there any user-facing changes? A public function -- `isEnd` -- was renamed, but this code hasn't been released yet, so it's OK. * Closes: apache#34893 Authored-by: Felipe Oliveira Carvalho <felipekde@gmail.com> Signed-off-by: Matt Topol <zotthewizard@gmail.com>
rtpsw
pushed a commit
to rtpsw/arrow
that referenced
this issue
May 16, 2023
…manifest on backwards iteration (apache#34896) ### Rationale for this change The value of `RunEndEncodedArraySpan::Iterator::physical_pos_` from the instance returned by `RunEndEncodedArraySpan::end()` is smaller (by 1) than the results of successive applications of `operator++()` until `logical_pos_` reaches the logical length of the run-end encoded array. To support backwards iteration, the `Iterator` returned by `RunEndEncodedArraySpan::end()` should be well-formed. There was no `operator--()` in `RunEndEncodedArraySpan::Iterator` before this PR, so one can't go backwards from `end()` and this latent bug doesn't manifest. ### What changes are included in this PR? - Addition of `RunEndEncodedArraySpan::Iterator::operator--()` - Addition of `MergedRunsIterator::operator--()` - Rename `isEnd()` to `is_end()` (it was a code-style violation) - More test cases ### Are these changes tested? By existing and new unit tests. ### Are there any user-facing changes? A public function -- `isEnd` -- was renamed, but this code hasn't been released yet, so it's OK. * Closes: apache#34893 Authored-by: Felipe Oliveira Carvalho <felipekde@gmail.com> Signed-off-by: Matt Topol <zotthewizard@gmail.com>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Describe the enhancement requested
The value of
RunEndEncodedArraySpan::Iterator::physical_pos_from the instance returned byRunEndEncodedArraySpan::end()is smaller (by 1) than the results of successive applications ofoperator++untillogical_pos_reaches the logical length of the run-end encoded array.Why this is important?
To support backwards iteration, the
Iteratorreturned byRunEndEncodedArraySpan::end()should be well-formed.Why this is not a bug?
There is no
operator--()inRunEndEncodedArraySpan::Iteratoryet, so you can't go backwards fromend(). A fix for this issue adds that operator and uses it in tests that guarantee iterators are always valid and don't assume iteration only happens in one direction.Component(s)
C++
The text was updated successfully, but these errors were encountered: