* [Bug libstdc++/97828] std::ranges::search_n does not work with counted_iterator<_List_iterator<...>>
2020-11-14 15:32 [Bug libstdc++/97828] New: std::ranges::search_n does not work with counted_iterator<_List_iterator<...>> ensadc at mailnesia dot com
@ 2020-11-16 11:24 ` ensadc at mailnesia dot com
2020-11-16 11:34 ` ensadc at mailnesia dot com
` (8 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: ensadc at mailnesia dot com @ 2020-11-16 11:24 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97828
--- Comment #1 from ensadc at mailnesia dot com ---
Compilation failure with `std::list`: https://godbolt.org/z/vbqhax
Wrong result with `std::vector`: https://godbolt.org/z/axYbYr (expected output:
"42 42 42"; actual: "42 0 42")
It appears that `__remainder` is not reset when the sequence of equal values is
interrupted. When the algorithm sees `0, 42, 42`, it decrements `__remainder`
to 1, but when it sees that the next value is 0, it does not increment
`__remainder`.
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug libstdc++/97828] std::ranges::search_n does not work with counted_iterator<_List_iterator<...>>
2020-11-14 15:32 [Bug libstdc++/97828] New: std::ranges::search_n does not work with counted_iterator<_List_iterator<...>> ensadc at mailnesia dot com
2020-11-16 11:24 ` [Bug libstdc++/97828] " ensadc at mailnesia dot com
@ 2020-11-16 11:34 ` ensadc at mailnesia dot com
2020-11-16 16:06 ` space.mission at yandex dot ru
` (7 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: ensadc at mailnesia dot com @ 2020-11-16 11:34 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97828
--- Comment #2 from ensadc at mailnesia dot com ---
This seems to fix the bug (note: not thoroughly tested)
diff --git a/libstdc++-v3/include/bits/ranges_algo.h
b/libstdc++-v3/include/bits/ranges_algo.h
index f1a4cc24c0d..414ce0b1baa 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -579,21 +579,24 @@ namespace ranges
}
}
- if constexpr (sized_sentinel_for<_Sent, _Iter>)
+ if constexpr (random_access_iterator<_Iter>
+ && sized_sentinel_for<_Sent, _Iter>)
{
auto __tail_size = __last - __first;
auto __remainder = __count;
while (__remainder <= __tail_size)
{
+ auto __t = __remainder;
__first += __remainder;
__tail_size -= __remainder;
auto __backtrack = __first;
while (__value_comp(std::__invoke(__proj, *--__backtrack)))
{
- if (--__remainder == 0)
+ if (--__t == 0)
return {__first - __count, __first};
}
+ __remainder = __count - __remainder + __t;
}
auto __i = __first + __tail_size;
return {__i, __i};
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug libstdc++/97828] std::ranges::search_n does not work with counted_iterator<_List_iterator<...>>
2020-11-14 15:32 [Bug libstdc++/97828] New: std::ranges::search_n does not work with counted_iterator<_List_iterator<...>> ensadc at mailnesia dot com
2020-11-16 11:24 ` [Bug libstdc++/97828] " ensadc at mailnesia dot com
2020-11-16 11:34 ` ensadc at mailnesia dot com
@ 2020-11-16 16:06 ` space.mission at yandex dot ru
2020-11-16 16:33 ` redi at gcc dot gnu.org
` (6 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: space.mission at yandex dot ru @ 2020-11-16 16:06 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97828
Alexey Mission <space.mission at yandex dot ru> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |space.mission at yandex dot ru
--- Comment #3 from Alexey Mission <space.mission at yandex dot ru> ---
Please see also cppreference.com where this bug is also spotted:
https://en.cppreference.com/w/Talk:cpp/algorithm/ranges/search_n
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug libstdc++/97828] std::ranges::search_n does not work with counted_iterator<_List_iterator<...>>
2020-11-14 15:32 [Bug libstdc++/97828] New: std::ranges::search_n does not work with counted_iterator<_List_iterator<...>> ensadc at mailnesia dot com
` (2 preceding siblings ...)
2020-11-16 16:06 ` space.mission at yandex dot ru
@ 2020-11-16 16:33 ` redi at gcc dot gnu.org
2020-11-16 16:36 ` redi at gcc dot gnu.org
` (5 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: redi at gcc dot gnu.org @ 2020-11-16 16:33 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97828
--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Alexey Mission from comment #3)
> Please see also cppreference.com where this bug is also spotted:
> https://en.cppreference.com/w/Talk:cpp/algorithm/ranges/search_n
Reporting bugs in a talk page on cppreference is stupid.
I don't read talk pages on cppreference, so telling me to pay attention there
is also stupid.
"Sure, the problem is that they want a reporter ''signed in blood'' lol before
acquiring an account to report." -- nonsense, you just send an email asking for
an account.
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug libstdc++/97828] std::ranges::search_n does not work with counted_iterator<_List_iterator<...>>
2020-11-14 15:32 [Bug libstdc++/97828] New: std::ranges::search_n does not work with counted_iterator<_List_iterator<...>> ensadc at mailnesia dot com
` (3 preceding siblings ...)
2020-11-16 16:33 ` redi at gcc dot gnu.org
@ 2020-11-16 16:36 ` redi at gcc dot gnu.org
2020-11-16 17:22 ` ppalka at gcc dot gnu.org
` (4 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: redi at gcc dot gnu.org @ 2020-11-16 16:36 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97828
--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Also, don't paste copyrighted code into talk pages on cppreference.
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug libstdc++/97828] std::ranges::search_n does not work with counted_iterator<_List_iterator<...>>
2020-11-14 15:32 [Bug libstdc++/97828] New: std::ranges::search_n does not work with counted_iterator<_List_iterator<...>> ensadc at mailnesia dot com
` (4 preceding siblings ...)
2020-11-16 16:36 ` redi at gcc dot gnu.org
@ 2020-11-16 17:22 ` ppalka at gcc dot gnu.org
2020-11-16 20:26 ` ppalka at gcc dot gnu.org
` (3 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: ppalka at gcc dot gnu.org @ 2020-11-16 17:22 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97828
Patrick Palka <ppalka at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Ever confirmed|0 |1
Status|UNCONFIRMED |ASSIGNED
Assignee|unassigned at gcc dot gnu.org |ppalka at gcc dot gnu.org
Last reconfirmed| |2020-11-16
Target Milestone|--- |10.3
--- Comment #6 from Patrick Palka <ppalka at gcc dot gnu.org> ---
Confirmed, your analysis makes sense to me.
For the implementation bug, I guess it would be better to mirror how
std::search_n updates __remainder and do
__remainder = __count + 1 - (__first - __backtrack);
right after the while loop.
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug libstdc++/97828] std::ranges::search_n does not work with counted_iterator<_List_iterator<...>>
2020-11-14 15:32 [Bug libstdc++/97828] New: std::ranges::search_n does not work with counted_iterator<_List_iterator<...>> ensadc at mailnesia dot com
` (5 preceding siblings ...)
2020-11-16 17:22 ` ppalka at gcc dot gnu.org
@ 2020-11-16 20:26 ` ppalka at gcc dot gnu.org
2020-11-17 15:29 ` cvs-commit at gcc dot gnu.org
` (2 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: ppalka at gcc dot gnu.org @ 2020-11-16 20:26 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97828
--- Comment #7 from Patrick Palka <ppalka at gcc dot gnu.org> ---
Patch posted at
https://gcc.gnu.org/pipermail/libstdc++/2020-November/051458.html
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug libstdc++/97828] std::ranges::search_n does not work with counted_iterator<_List_iterator<...>>
2020-11-14 15:32 [Bug libstdc++/97828] New: std::ranges::search_n does not work with counted_iterator<_List_iterator<...>> ensadc at mailnesia dot com
` (6 preceding siblings ...)
2020-11-16 20:26 ` ppalka at gcc dot gnu.org
@ 2020-11-17 15:29 ` cvs-commit at gcc dot gnu.org
2020-11-17 16:28 ` cvs-commit at gcc dot gnu.org
2020-11-17 16:30 ` ppalka at gcc dot gnu.org
9 siblings, 0 replies; 11+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2020-11-17 15:29 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97828
--- Comment #8 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Patrick Palka <ppalka@gcc.gnu.org>:
https://gcc.gnu.org/g:8661f4faa875f361cd22a197774c1fa04cd0580b
commit r11-5096-g8661f4faa875f361cd22a197774c1fa04cd0580b
Author: Patrick Palka <ppalka@redhat.com>
Date: Tue Nov 17 10:28:20 2020 -0500
libstdc++: Fix ranges::search_n for random access iterators [PR97828]
My ranges transcription of the std::search_n implementation for random
access iterators missed a crucial part of the algorithm which the
existing tests didn't exercise. When __remainder is less than __count
at the start of an iteration of the outer while loop, it means we're
continuing a partial match of __count - __remainder elements from the
previous iteration. If at the end of the iteration we don't complete
this partial match, we need to reset __remainder so that it's only
offset by the size of the most recent partial match before starting the
next iteration.
This patch fixes this appropriately, mirroring how it's done in the
corresponding std::search_n implementation.
libstdc++-v3/ChangeLog:
PR libstdc++/97828
* include/bits/ranges_algo.h (__search_n_fn::operator()): Check
random_access_iterator before using the backtracking
implementation. When the backwards scan fails prematurely,
reset __remainder appropriately.
* testsuite/25_algorithms/search_n/97828.cc: New test.
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug libstdc++/97828] std::ranges::search_n does not work with counted_iterator<_List_iterator<...>>
2020-11-14 15:32 [Bug libstdc++/97828] New: std::ranges::search_n does not work with counted_iterator<_List_iterator<...>> ensadc at mailnesia dot com
` (7 preceding siblings ...)
2020-11-17 15:29 ` cvs-commit at gcc dot gnu.org
@ 2020-11-17 16:28 ` cvs-commit at gcc dot gnu.org
2020-11-17 16:30 ` ppalka at gcc dot gnu.org
9 siblings, 0 replies; 11+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2020-11-17 16:28 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97828
--- Comment #9 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-10 branch has been updated by Patrick Palka
<ppalka@gcc.gnu.org>:
https://gcc.gnu.org/g:04cb64dadb5c115b4ad093ff92c3f5a0a87ef15f
commit r10-9036-g04cb64dadb5c115b4ad093ff92c3f5a0a87ef15f
Author: Patrick Palka <ppalka@redhat.com>
Date: Tue Nov 17 10:28:20 2020 -0500
libstdc++: Fix ranges::search_n for random access iterators [PR97828]
My ranges transcription of the std::search_n implementation for random
access iterators missed a crucial part of the algorithm which the
existing tests didn't exercise. When __remainder is less than __count
at the start of an iteration of the outer while loop, it means we're
continuing a partial match of __count - __remainder elements from the
previous iteration. If at the end of the iteration we don't complete
this partial match, we need to reset __remainder so that it's only
offset by the size of the most recent partial match before starting the
next iteration.
This patch fixes this appropriately, mirroring how it's done in the
corresponding std::search_n implementation.
libstdc++-v3/ChangeLog:
PR libstdc++/97828
* include/bits/ranges_algo.h (__search_n_fn::operator()): Check
random_access_iterator before using the backtracking
implementation. When the backwards scan fails prematurely,
reset __remainder appropriately.
* testsuite/25_algorithms/search_n/97828.cc: New test.
(cherry picked from commit 8661f4faa875f361cd22a197774c1fa04cd0580b)
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug libstdc++/97828] std::ranges::search_n does not work with counted_iterator<_List_iterator<...>>
2020-11-14 15:32 [Bug libstdc++/97828] New: std::ranges::search_n does not work with counted_iterator<_List_iterator<...>> ensadc at mailnesia dot com
` (8 preceding siblings ...)
2020-11-17 16:28 ` cvs-commit at gcc dot gnu.org
@ 2020-11-17 16:30 ` ppalka at gcc dot gnu.org
9 siblings, 0 replies; 11+ messages in thread
From: ppalka at gcc dot gnu.org @ 2020-11-17 16:30 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97828
Patrick Palka <ppalka at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|ASSIGNED |RESOLVED
Resolution|--- |FIXED
--- Comment #10 from Patrick Palka <ppalka at gcc dot gnu.org> ---
Fixed for GCC 10.3 and 11, thanks for the bug report.
^ permalink raw reply [flat|nested] 11+ messages in thread