[Bug libstdc++/100664] New: ranges::drop_view fails to meet its complexity requirements

[Bug libstdc++/100664] New: ranges::drop_view fails to meet its complexity requirements

[hewillk at gmail dot com]

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

            Bug ID: 100664
           Summary: ranges::drop_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#L2043, the _S_needs_cached_begin of reverse_view is defined as:


   static constexpr bool _S_needs_cached_begin
     = !(random_access_range<const _Vp> && sized_range<const _Vp>);


I think this definition is insufficient, because there may be a non-simple_view
V that can satisfy random_access_range<const _Vp> && sized_range<const _Vp> but
not random_access_range<_Vp> && sized_range<_Vp>, in this case, the complexity
of ranges::next would be O(n).

There is no such view in the standard library, but it can be easily
implemented:
(https://godbolt.org/z/oxY4e77br)



  template <view V>
  struct common_non_const_view : view_interface<common_non_const_view<V>> {
   private:
    using I = iterator_t<V>;
    using S = sentinel_t<V>;
    V base_ = V();

   public:
    common_non_const_view() = default;
    constexpr common_non_const_view(V base) : base_(std::move(base)) {}

    constexpr auto begin()
    { return std::common_iterator<I, S>{ranges::begin(base_)}; }
    constexpr auto begin() const requires ranges::range<const V>
    { return std::ranges::begin(base_); }

    constexpr auto end()
    { return std::common_iterator<I, S>{ranges::end(base_)}; }
    constexpr auto end() const requires ranges::range<const V>
    { return ranges::end(base_); }

    constexpr auto size() requires sized_range<V> 
    { return ranges::size(base_); }
    constexpr auto size() const requires sized_range<const V>
    { return ranges::size(base_); }
  };

  subrange sub(std::counted_iterator(views::iota(0).begin(), 42),
std::default_sentinel);

  const common_non_const_view cr{sub};
  static_assert(random_access_range<decltype(cr)>);
  static_assert(sized_range<decltype(cr)>);

  common_non_const_view r{sub};
  static_assert(!random_access_range<decltype(r)>);
  static_assert(forward_range<decltype(r)>);
  static_assert(sized_range<decltype(r)>);



The above *const* common_non_const_view models random_access_range and
sized_range, but the non-const one only models sized_range. Since it also
models forward_range, we still need to cache the results of ranges::next() in
the begin() of drop_view, just as says in [[range.drop#view-4]]:


  auto drop = r | std::views::drop(41);
  static_assert(forward_range<decltype(drop)>);
  auto it = drop.begin(); // need cached

[Bug libstdc++/100664] ranges::drop_view fails to meet its complexity requirements

[hewillk at gmail dot com]

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

--- Comment #1 from 康桓瑋 <hewillk at gmail dot com> ---
(In reply to 康桓瑋 from comment #0)
> Hi, in ranges#L2043, the _S_needs_cached_begin of reverse_view is defined as:

This is drop_view, sorry for the typo.

[Bug libstdc++/100664] ranges::drop_view fails to meet its complexity requirements

[hewillk at gmail dot com]

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

--- Comment #2 from 康桓瑋 <hewillk at gmail dot com> ---
(In reply to 康桓瑋 from comment #0)
> Hi, in ranges#L2043, the _S_needs_cached_begin of reverse_view is defined as:
> 
> 
>    static constexpr bool _S_needs_cached_begin
>      = !(random_access_range<const _Vp> && sized_range<const _Vp>);
> 
> 
> I think this definition is insufficient, because there may be a
> non-simple_view V that can satisfy random_access_range<const _Vp> &&
> sized_range<const _Vp> but not random_access_range<_Vp> && sized_range<_Vp>,
> in this case, the complexity of ranges::next would be O(n).
> 

I think _S_needs_cached_begin can be defined as:

  // ranges::next(begin(base), count, end(base)) is O(1) if _Vp satisfies
  // both random_access_range and sized_range. Otherwise, cache its result.
  static constexpr bool _S_needs_cached_begin
    = !(__detail::__simple_view<_Vp>
        && random_access_range<const _Vp>
        && sized_range<const _Vp>)
        && !(random_access_range<_Vp> && sized_range<_Vp>);