[Bug libstdc++/97828] New: std::ranges::search_n does not work with counted_iterator<_List_iterator<...>>

[Bug libstdc++/97828] New: std::ranges::search_n does not work with counted_iterator<_List_iterator<...>>

[ensadc at mailnesia dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97828

            Bug ID: 97828
           Summary: std::ranges::search_n does not work with
                    counted_iterator<_List_iterator<...>>
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Keywords: rejects-valid
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: ensadc at mailnesia dot com
  Target Milestone: ---

```
#include <ranges>
#include <algorithm>
#include <iostream>
#include <list>

int main() {
    using namespace std::ranges;
    std::list a = {0,42,42,0,42,42,42,0};
    auto b = a | views::take(5);
    auto count = 3;

    auto res = search_n(b, count, 42);

    for (int v : res) std::cout << v << ' ';
    std::cout << '\n';
}
```

This gives a rather long error message.

It appears that the `sized_sentinel_for` branch of std::ranges::search_n uses
random access iterator operations, without checking if the iterator is actually
random access.

(This branch also returns incorrect results for certain input, which can be
observed by changing `std::list` to `std::vector`.)

[Bug libstdc++/97828] std::ranges::search_n does not work with counted_iterator<_List_iterator<...>>

[ensadc at mailnesia dot com]

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`.

[Bug libstdc++/97828] std::ranges::search_n does not work with counted_iterator<_List_iterator<...>>

[ensadc at mailnesia dot com]

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};

[Bug libstdc++/97828] std::ranges::search_n does not work with counted_iterator<_List_iterator<...>>

[space.mission at yandex dot ru]

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

[Bug libstdc++/97828] std::ranges::search_n does not work with counted_iterator<_List_iterator<...>>

[redi at gcc dot gnu.org]

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.

[Bug libstdc++/97828] std::ranges::search_n does not work with counted_iterator<_List_iterator<...>>

[redi at gcc dot gnu.org]

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.

[Bug libstdc++/97828] std::ranges::search_n does not work with counted_iterator<_List_iterator<...>>

[ppalka at gcc dot gnu.org]

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.

[Bug libstdc++/97828] std::ranges::search_n does not work with counted_iterator<_List_iterator<...>>

[ppalka at gcc dot gnu.org]

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

[Bug libstdc++/97828] std::ranges::search_n does not work with counted_iterator<_List_iterator<...>>

[cvs-commit at gcc dot gnu.org]

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.

[Bug libstdc++/97828] std::ranges::search_n does not work with counted_iterator<_List_iterator<...>>

[cvs-commit at gcc dot gnu.org]

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)

[Bug libstdc++/97828] std::ranges::search_n does not work with counted_iterator<_List_iterator<...>>

[ppalka at gcc dot gnu.org]

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.