[Bug libstdc++/100621] New: ranges::reverse_view fails to meet its complexity requirements

[Bug libstdc++/100621] New: ranges::reverse_view fails to meet its complexity requirements

[hewillk at gmail dot com]

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

            Bug ID: 100621
           Summary: ranges::reverse_view fails to meet its complexity
                    requirements
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: hewillk at gmail dot com
  Target Milestone: ---

Hi, in ranges#L3230, the _S_needs_cached_begin of reverse_view is defined as:


  static constexpr bool _S_needs_cached_begin
    = !common_range<_Vp> && !random_access_range<_Vp>;


This definition seems incorrect, consider (https://godbolt.org/z/xfT5E4zK4):


  auto r = std::views::iota(0) | std::views::take(42) | std::views::drop(3);
  using V = decltype(r);
  static_assert(std::ranges::random_access_range<V>);
  static_assert(!std::ranges::common_range<V>);


This r is not a common_range but a random_access_range, so the value of
_S_needs_cached_begin is false, and because the following two asserts fail, the
complexity of ranges::next is O(n):


  using I = decltype(r.begin());
  using S = decltype(r.end());
  static_assert(!std::assignable_from<I&, S>);
  static_assert(!std::sized_sentinel_for<S, I>);

  auto rr = r | std::views::reverse;


This makes rr.begin() fails to meet its complexity requirements in
[range.reverse.view#3]: "Remarks: In order to provide the amortized constant
time complexity required by the range concept, this function caches the result
within the reverse_­view for use on subsequent calls.".

[Bug libstdc++/100621] ranges::reverse_view fails to meet its complexity requirements

[ppalka at gcc dot gnu.org]

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

Patrick Palka <ppalka at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2021-05-17
                 CC|                            |ppalka at gcc dot gnu.org
             Status|UNCONFIRMED                 |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |ppalka at gcc dot gnu.org

--- Comment #1 from Patrick Palka <ppalka at gcc dot gnu.org> ---
Confirmed.

[Bug libstdc++/100621] ranges::reverse_view fails to meet its complexity requirements

[ppalka at gcc dot gnu.org]

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

--- Comment #2 from Patrick Palka <ppalka at gcc dot gnu.org> ---
We need at least additionally check that the underlying random access range has
a sized sentinel before eliding the cache.

[Bug libstdc++/100621] ranges::reverse_view fails to meet its complexity requirements

[cvs-commit at gcc dot gnu.org]

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

--- Comment #3 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:03cf8d54e5c27cfe6b184cc96757cab30d8fa1df

commit r12-855-g03cf8d54e5c27cfe6b184cc96757cab30d8fa1df
Author: Patrick Palka <ppalka@redhat.com>
Date:   Tue May 18 00:26:25 2021 -0400

    libstdc++: Fix condition for memoizing reverse_view::begin() [PR100621]

    A range being a random access range isn't a sufficient condition for
    ranges::next(iter, sent) to have constant time complexity -- it must
    also have a sized sentinel.  This adjusts the memoization condition for
    reverse_view accordingly.

    libstdc++-v3/ChangeLog:

            PR libstdc++/100621
            * include/std/ranges (reverse_view::_S_needs_cached_begin):
            Set to true if the underlying non-common random-access range
            doesn't have a sized sentinel.

[Bug libstdc++/100621] ranges::reverse_view fails to meet its complexity requirements

[ppalka at gcc dot gnu.org]

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

Patrick Palka <ppalka at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
   Target Milestone|---                         |12.0
             Status|ASSIGNED                    |RESOLVED

--- Comment #4 from Patrick Palka <ppalka at gcc dot gnu.org> ---
Fixed for GCC 12.  This probably isn't suitable for backporting to 11/10 as it
changes the layout of some specializations of reverse_view.