[Bug libstdc++/99752] New: ranges::find_end should return empty subrange when search range is empty

[Bug libstdc++/99752] New: ranges::find_end should return empty subrange when search range is empty

[hewillk at gmail dot com]

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

            Bug ID: 99752
           Summary: ranges::find_end should return empty subrange when
                    search range is empty
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: hewillk at gmail dot com
  Target Milestone: ---

In ranges::find_end implementation:

674     else
675       {
676         auto __i = ranges::next(__first1, __last1);
677         if (__first2 == __last2)
678           return {__i, __i};

when the examined range is not bidirectional_range and the search range is
empty, we still do the ranges::next call, this makes the following code
infinite loop:

#include <algorithm>
#include <ranges>

int main() {
  auto r = std::views::iota(0);
  std::ranges::empty_view<int> e;
  std::ranges::find_end(r, e);
}

But according to the [alg.find.end]: "i be last1 if [first2, last2) is empty", 
so I think this is a library bug since in such case ranges::find_end never
return.

Same situations in ranges::rotate with performance loss in more rare
conditions:

1573      {
1574    auto __lasti = ranges::next(__first, __last);
1575    if (__first == __middle)
1576      return {__lasti, __lasti};
1577    if (__last == __middle)
1578      return {std::move(__first), std::move(__lasti)};

[Bug libstdc++/99752] ranges::find_end should return empty subrange when search range is empty

[hewillk at gmail dot com]

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

--- Comment #1 from 康桓瑋 <hewillk at gmail dot com> ---
My pardon, since the ranges::find_end return type is ranges::subrange<I1>, we
still to get the common last1 iterator through the ranges::next call, so this
seems not a bug.

[Bug libstdc++/99752] ranges::find_end should return empty subrange when search range is empty

[hewillk at gmail dot com]

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

康桓瑋 <hewillk at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |INVALID

--- Comment #2 from 康桓瑋 <hewillk at gmail dot com> ---
Since the ranges::find_end return type is ranges::subrange<I1>, we still to get
the common last1 iterator through the ranges::next call, so this seems not a
bug.

[Bug libstdc++/99752] ranges::find_end should return empty subrange when search range is empty

[redi at gcc dot gnu.org]

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

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Your example is an infinite loop because you're asking for the last occurrence
of e in an infinite range. There is no end of an infinite range.