[libc++] Add the std::ranges::drop range adaptor object

[ldionne]

Summary

This introduces forward declarations of string_view and span to
keep drop_view.h as miminal as possible, and to avoid the possibility
of circular dependencies since span and string_view both depend on
some parts of ranges too. They don't technically depend on drop_view
right now, but this is guarding against future headache.

[ldionne]

Generate missing files.

[• Quuxplusone]

I haven't really looked at the implementation yet, other than to say "ergh, this doesn't look like how I did it." ;) I'll wait for test/forward-declaration updates before looking again, in case the test updates flush out any issues with the implementation.

libcxx/include/CMakeLists.txt

204–205

This introduces forward declarations of string_view and span

On the cost side, there are several red flags associated with this part of the PR:

• requires unusual-looking modulemap changes
• introduces a new detail subdirectory (countermeasure: you could simply change the names to __string/stringfwd.h and __span/spanfwd.h, after moving the existing __string file out of the way; I expect that'd look fine)
• the idea of "forward declarations" in general (counterpoint: they already exist, you're just moving them a bit further away from their corresponding definitions). If we're talking about "future headaches," I would imagine "forward declaration, separated from its definition, accidentally bit-rots and drifts away from that definition" is a vastly more likely headache than anything involving circular dependencies between span and drop_view-etc.

How about renaming these to __string/stringfwd.h and __span/spanfwd.h, and perhaps granularizing the rest of <string> and/or <span> in a preliminary PR while you're at it? (I suggest foofwd.h by analogy with iosfwd. I can see a case for just __foo/fwd.h, but that might be ambiguous when <foo> contains multiple types and only some of them are being forward-declared in the detail header.)

libcxx/test/std/ranges/range.adaptors/range.drop/adaptor.pass.cpp

52

Here and throughout, can you think of a good way to test that result.end() also has its correct value?

88

Simpler: assert(result.empty()), since iota_view provides an .empty() method?

109–115

I'd like to see more value-category tests, i.e. std::views::drop(static_cast<const View&&>(view), 2) for all four interesting cvref-qualifications, and ditto for all four cvref-qualifications on at least one of the "passthrough" types.

[var-const]

Note: it looks like drop is not mentioned in docs/Status/RangesPaper.csv.

[var-const]

In D116950#3280986, @var-const wrote:

Note: it looks like drop is not mentioned in docs/Status/RangesPaper.csv.

Hmm, it looks like that page only tracks things that were in the original One Ranges Proposal, and drop_view was added by P1035 "Input Range Adaptors" (among other things).

[ldionne]

Rebasing onto main -- after talking with @var-const, he'll commandeer this because I'm busy with other stuff at the moment, and we should really get this landed.

[• Quuxplusone]

libcxx/include/__ranges/drop_view.h

142–143

https://eel.is/c++draft/range.drop#overview-2.2.1
IIUC, this should also permit fixed spans like std::span<T, 42>. This needs a regression test.

151–152

This smells like it doesn't exactly match what's supposed to happen in
https://eel.is/c++draft/range.drop#overview-2.2.4
Note that subranges with StoreSize=true are handled in https://eel.is/c++draft/range.drop#overview-2.3 instead. It's a whole maze.

@var-const, you should definitely take a look at my D115122 for comparison. On glancing at it right now, I'm not sure that I do the subrange bullet points correctly, either, though!

[ldionne]

Superseded by D125156

libcxx/include/CMakeLists.txt

set(files
   __functional/pointer_to_binary_function.h
   __functional/pointer_to_unary_function.h
   __functional/ranges_operations.h
   __functional/reference_wrapper.h
   __functional/unary_function.h
   __functional/unary_negate.h
   __functional/unwrap_ref.h
   __functional/weak_result_type.h
+  __fwd/span.h
+  __fwd/string_view.h
   __hash_table
   __iterator/access.h
   __iterator/advance.h
   __iterator/back_insert_iterator.h
   __iterator/common_iterator.h
   __iterator/concepts.h
   __iterator/counted_iterator.h
   __iterator/data.h

libcxx/include/__fwd/span.h

+// -*- C++ -*-
+//===---------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===---------------------------------------------------------------------===//
+
+#ifndef _LIBCPP_FWD_SPAN_H
+#define _LIBCPP_FWD_SPAN_H
+
+#include <__config>
+#include <cstddef>
+#include <limits>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if _LIBCPP_STD_VER > 17
+
+inline constexpr size_t dynamic_extent = numeric_limits<size_t>::max();
+template <typename _Tp, size_t _Extent = dynamic_extent> class span;
+
+#endif
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP_FWD_SPAN_H

libcxx/include/__fwd/string_view.h

+// -*- C++ -*-
+//===---------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===---------------------------------------------------------------------===//
+
+#ifndef _LIBCPP_FWD_STRING_VIEW_H
+#define _LIBCPP_FWD_STRING_VIEW_H
+
+#include <__config>
+#include <iosfwd> // char_traits
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template<class _CharT, class _Traits = char_traits<_CharT> >
+class _LIBCPP_TEMPLATE_VIS basic_string_view;
+
+typedef basic_string_view<char>     string_view;
+#ifndef _LIBCPP_HAS_NO_CHAR8_T
+typedef basic_string_view<char8_t>  u8string_view;
+#endif
+typedef basic_string_view<char16_t> u16string_view;
+typedef basic_string_view<char32_t> u32string_view;
+#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
+typedef basic_string_view<wchar_t>  wstring_view;
+#endif
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_FWD_STRING_VIEW_H

libcxx/include/__ranges/drop_view.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 #ifndef _LIBCPP___RANGES_DROP_VIEW_H
 #define _LIBCPP___RANGES_DROP_VIEW_H
 
 #include <__config>
 #include <__debug>
+#include <__functional/bind_back.h>
+#include <__fwd/span.h>
+#include <__fwd/string_view.h>
 #include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/next.h>
 #include <__ranges/access.h>
 #include <__ranges/all.h>
 #include <__ranges/concepts.h>
+#include <__ranges/empty_view.h>
 #include <__ranges/enable_borrowed_range.h>
+#include <__ranges/iota_view.h>
 #include <__ranges/non_propagating_cache.h>
+#include <__ranges/range_adaptor.h>
 #include <__ranges/size.h>
+#include <__ranges/subrange.h>
 #include <__ranges/view_interface.h>
+#include <__utility/auto_cast.h>
+#include <__utility/forward.h>
 #include <__utility/move.h>
 #include <concepts>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
public:
     { return __size(*this); }
   };
 
   template<class _Range>
   drop_view(_Range&&, range_difference_t<_Range>) -> drop_view<views::all_t<_Range>>;
 
   template<class _Tp>
   inline constexpr bool enable_borrowed_range<drop_view<_Tp>> = enable_borrowed_range<_Tp>;
+
+  namespace views {
+  namespace __drop {
+    template<class _Tp>
+    constexpr bool __is_empty_view = false;
+
+    template<class _Tp>
+    constexpr bool __is_empty_view<empty_view<_Tp>> = true;
+
+    template<class _Tp>
+    constexpr bool __is_passthrough_specialization = false;
+
+    template<class _Tp>
+    constexpr bool __is_passthrough_specialization<span<_Tp, dynamic_extent>> = true;
+
+    template<class _CharT, class _Traits>
+    constexpr bool __is_passthrough_specialization<basic_string_view<_CharT, _Traits>> = true;
+
+    template<class _Np, class _Bound>
+    constexpr bool __is_passthrough_specialization<iota_view<_Np, _Bound>> = true;
+
+    template<class _Iter, class _Sent, subrange_kind _Kind>
+    constexpr bool __is_passthrough_specialization<subrange<_Iter, _Sent, _Kind>> = true;
+
+    struct __fn {
+      template<class _Range, convertible_to<range_difference_t<_Range>> _Np>
+        requires __is_empty_view<remove_cvref_t<_Range>>
+      [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
+      constexpr auto operator()(_Range&& __range, _Np&&) const
+        noexcept(noexcept(_LIBCPP_AUTO_CAST(_VSTD::forward<_Range>(__range))))
+        -> decltype(      _LIBCPP_AUTO_CAST(_VSTD::forward<_Range>(__range)))
+        { return          _LIBCPP_AUTO_CAST(_VSTD::forward<_Range>(__range)); }
+
+      template<class _Rng, convertible_to<range_difference_t<_Rng>> _Np,
+               class _RawRng = remove_cvref_t<_Rng>,
+               class _Dist = range_difference_t<_Rng>>
+        requires (!__is_empty_view<_RawRng> &&
+                  random_access_range<_RawRng> &&
+                  sized_range<_RawRng> &&
+                  __is_passthrough_specialization<_RawRng>)
+      [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
+      constexpr auto operator()(_Rng&& __rng, _Np&& __n) const
+        noexcept(noexcept(_RawRng(ranges::begin(_VSTD::forward<_Rng>(__rng)) + _VSTD::min<_Dist>(ranges::size(_VSTD::forward<_Rng>(__rng)), _VSTD::forward<_Np>(__n)),
+                                  ranges::end(_VSTD::forward<_Rng>(__rng)))))
+        -> decltype(      _RawRng(ranges::begin(_VSTD::forward<_Rng>(__rng)) + _VSTD::min<_Dist>(ranges::size(_VSTD::forward<_Rng>(__rng)), _VSTD::forward<_Np>(__n)),
+                                  ranges::end(_VSTD::forward<_Rng>(__rng))))
+        { return          _RawRng(ranges::begin(_VSTD::forward<_Rng>(__rng)) + _VSTD::min<_Dist>(ranges::size(_VSTD::forward<_Rng>(__rng)), _VSTD::forward<_Np>(__n)),
+                                  ranges::end(_VSTD::forward<_Rng>(__rng))); }
+
+      template<class _Range, convertible_to<range_difference_t<_Range>> _Np>
+      [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
+      constexpr auto operator()(_Range&& __range, _Np&& __n) const
+        noexcept(noexcept(drop_view(_VSTD::forward<_Range>(__range), _VSTD::forward<_Np>(__n))))
+        -> decltype(      drop_view(_VSTD::forward<_Range>(__range), _VSTD::forward<_Np>(__n)))
+        { return          drop_view(_VSTD::forward<_Range>(__range), _VSTD::forward<_Np>(__n)); }
+
+      template<class _Np>
+        requires constructible_from<decay_t<_Np>, _Np>
+      [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
+      constexpr auto operator()(_Np&& __n) const
+        noexcept(is_nothrow_constructible_v<decay_t<_Np>, _Np>)
+      { return __range_adaptor_closure_t(_VSTD::__bind_back(*this, _VSTD::forward<_Np>(__n))); }
+    };
+  }
+
+  inline namespace __cpo {
+    inline constexpr auto drop = __drop::__fn{};
+  }
+  } // namespace views
 } // namespace ranges
 
 #endif // !defined(_LIBCPP_HAS_NO_RANGES)
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___RANGES_DROP_VIEW_H

libcxx/include/module.modulemap

module std [system] {
   module shared_mutex {
     header "shared_mutex"
     export version
   }
   module span {
     header "span"
     export ranges.__ranges.enable_borrowed_range
     export version
+    module span_fwd { private header "__fwd/span.h" }
   }
   module sstream {
     header "sstream"
     // FIXME: should re-export istream, ostream, ios, streambuf, string?
     export *
   }
   module stack {
     header "stack"
module string {
     export __string
     export *
   }
   module string_view {
     header "string_view"
     export initializer_list
     export __string
     export *
+    module string_view_fwd { private header "__fwd/string_view.h" }
   }
   module strstream {
     header "strstream"
     export *
   }
   module system_error {
     header "system_error"
     export *

libcxx/include/span

template<class R>
     span(R&&) -> span<remove_reference_t<ranges::range_reference_t<R>>>;
 
 } // namespace std
 
 */
 
 #include <__config>
 #include <__debug>
+#include <__fwd/span.h>
 #include <__iterator/concepts.h>
 #include <__iterator/wrap_iter.h>
 #include <__ranges/concepts.h>
 #include <__ranges/data.h>
 #include <__ranges/enable_borrowed_range.h>
 #include <__ranges/enable_view.h>
 #include <__ranges/size.h>
 #include <array>        // for array
 #include <cstddef>      // for byte
 #include <iterator>     // for iterators
 #include <limits>
 #include <type_traits>  // for remove_cv, etc
 #include <version>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
-_LIBCPP_PUSH_MACROS
-#include <__undef_macros>
-
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 #if _LIBCPP_STD_VER > 17
 
-inline constexpr size_t dynamic_extent = numeric_limits<size_t>::max();
-template <typename _Tp, size_t _Extent = dynamic_extent> class span;
-
-
 template <class _Tp>
 struct __is_std_array : false_type {};
 
 template <class _Tp, size_t _Sz>
 struct __is_std_array<array<_Tp, _Sz>> : true_type {};
 
 template <class _Tp>
 struct __is_std_span : false_type {};

 template<ranges::contiguous_range _Range>
     span(_Range&&) -> span<remove_reference_t<ranges::range_reference_t<_Range>>>;
 #endif
 
 #endif // _LIBCPP_STD_VER > 17
 
 _LIBCPP_END_NAMESPACE_STD
 
-_LIBCPP_POP_MACROS
-
 #endif // _LIBCPP_SPAN

libcxx/include/string_view

 
 }  // namespace std
 
 
 */
 
 #include <__config>
 #include <__debug>
+#include <__fwd/string_view.h>
 #include <__ranges/concepts.h>
 #include <__ranges/data.h>
 #include <__ranges/enable_borrowed_range.h>
 #include <__ranges/enable_view.h>
 #include <__ranges/size.h>
 #include <__string>
 #include <algorithm>
 #include <compare>
 #include <iosfwd>
 #include <iterator>
 #include <limits>
 #include <stdexcept>
 #include <type_traits>
 #include <version>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
-
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template<class _CharT, class _Traits = char_traits<_CharT> >
-    class _LIBCPP_TEMPLATE_VIS basic_string_view;
-
-typedef basic_string_view<char>     string_view;
-#ifndef _LIBCPP_HAS_NO_CHAR8_T
-typedef basic_string_view<char8_t>  u8string_view;
-#endif
-typedef basic_string_view<char16_t> u16string_view;
-typedef basic_string_view<char32_t> u32string_view;
-#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
-typedef basic_string_view<wchar_t>  wstring_view;
-#endif
-
 template<class _CharT, class _Traits>
 class
     _LIBCPP_PREFERRED_NAME(string_view)
 #ifndef _LIBCPP_HAS_NO_CHAR8_T
     _LIBCPP_PREFERRED_NAME(u8string_view)
 #endif
     _LIBCPP_PREFERRED_NAME(u16string_view)
     _LIBCPP_PREFERRED_NAME(u32string_view)

libcxx/test/std/ranges/range.adaptors/range.drop/adaptor.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// std::views::drop
+
+#include <ranges>
+
+#include <cassert>
+#include <concepts>
+#include <span>
+#include <string_view>
+#include <utility>
+
+struct View : std::ranges::view_base {
+  int* begin_;
+  int* end_;
+  constexpr explicit View(int* b, int* e) : begin_(b), end_(e) { }
+  constexpr int* begin() const { return begin_; }
+  constexpr int* end() const { return end_; }
+};
+
+template <class View, class T>
+concept CanBePiped = requires (View&& view, T&& t) {
+  { std::forward<View>(view) | std::forward<T>(t) };
+};
+
+constexpr bool test() {
+  // views::drop(r, n) is equivalent to r if r is a ranges::empty_view
+  {
+    std::ranges::empty_view<int> view;
+    std::same_as<std::ranges::empty_view<int>> auto result = std::views::drop(view, 3);
+    (void)result;
+  }
+
+  // views::drop(r, n) is equivalent to T(begin(r) + min(size(r), n), end(r)) if:
+  {
+    // r is a std::span with dynamic_extent
+    {
+      {
+        int buff[] = {1, 2, 3, 4};
+        std::span<int, std::dynamic_extent> span(buff);
+        std::same_as<std::span<int, std::dynamic_extent>> auto result = std::views::drop(span, 2);
+        assert(result.begin() == span.begin() + 2);
+      }
+      {
+        int buff[] = {1, 2, 3, 4};
+        std::span<int, std::dynamic_extent> span(buff);
+        std::same_as<std::span<int, std::dynamic_extent>> auto result = std::views::drop(span, 10);
+        assert(result.begin() == span.begin() + 4);
+      }
+    }
+
+    // r is a std::basic_string_view
+    {
+      {
+        char buff[5] = "1234";
+        std::string_view str(buff);
+        std::same_as<std::string_view> auto result = std::views::drop(str, 2);
+        assert(result.begin() == buff + 2);
+      }
+      {
+        char buff[5] = "1234";
+        std::string_view str(buff);
+        std::same_as<std::string_view> auto result = std::views::drop(str, 10);
+        assert(result.begin() == buff + 4);
+      }
+    }
+
+    // r is a ranges::iota_view
+    {
+      {
+        std::ranges::iota_view<int, int> view(0, 4);
+        std::same_as<std::ranges::iota_view<int, int>> auto result = std::views::drop(view, 2);
+        assert(*result.begin() == 2);
+      }
+      {
+        std::ranges::iota_view<int, int> view(0, 4);
+        std::same_as<std::ranges::iota_view<int, int>> auto result = std::views::drop(view, 10);
+        assert(std::ranges::empty(result));
+      }
+    }
+
+    // r is a ranges::subrange
+    {
+      {
+        int buff[] = {1, 2, 3, 4};
+        std::ranges::subrange<int*, int*> subrange(buff, buff + 4);
+        std::same_as<std::ranges::subrange<int*, int*>> auto result = std::views::drop(subrange, 2);
+        assert(result.begin() == buff + 2);
+      }
+      {
+        int buff[] = {1, 2, 3, 4};
+        std::ranges::subrange<int*, int*> subrange(buff, buff + 4);
+        std::same_as<std::ranges::subrange<int*, int*>> auto result = std::views::drop(subrange, 10);
+        assert(result.begin() == buff + 4);
+      }
+    }
+  }
+
+  // Otherwise, views::drop(r, n) is ranges::drop_view{r, n}
+  {
+    int buff[] = {1, 2, 3, 4};
+    View view(buff, buff + 4);
+    std::same_as<std::ranges::drop_view<View>> auto result = std::views::drop(view, 2);
+    assert(result.begin() == buff + 2);
+  }
+
+  // Test that std::views::drop is a range adaptor
+  {
+    int buff[] = {1, 2, 3, 4};
+    View view(buff, buff + 4);
+
+    // Test `v | views::drop(n)`
+    {
+      std::same_as<std::ranges::drop_view<View>> auto result = view | std::views::drop(1);
+      assert(result.begin() == buff + 1);
+    }
+
+    // Test `adaptor | views::drop(n)`
+    {
+      auto f = [](int i) { return i; };
+      auto const partial = std::views::transform(f) | std::views::drop(1);
+      using Result = std::ranges::drop_view<std::ranges::transform_view<View, decltype(f)>>;
+      std::same_as<Result> auto result = partial(view);
+      assert(result.begin().base() == buff + 1);
+    }
+
+    // Test `views::drop(n) | adaptor`
+    {
+      auto f = [](int i) { return i; };
+      auto const partial = std::views::drop(1) | std::views::transform(f);
+      using Result = std::ranges::transform_view<std::ranges::drop_view<View>, decltype(f)>;
+      std::same_as<Result> auto result = partial(view);
+      assert(result.begin().base() == buff + 1);
+    }
+
+    // Check SFINAE friendliness
+    {
+      struct NotAView { };
+      struct NotADifferenceType { };
+      static_assert( std::is_invocable_v<decltype(std::views::drop), View, int>);
+      static_assert(!std::is_invocable_v<decltype(std::views::drop)>);
+      static_assert(!std::is_invocable_v<decltype(std::views::drop), NotAView, int>);
+      static_assert(!std::is_invocable_v<decltype(std::views::drop), View, NotADifferenceType>);
+      static_assert( CanBePiped<View, decltype(std::views::drop(1))>);
+      static_assert(!CanBePiped<NotAView,     decltype(std::views::drop(1))>);
+      static_assert(!CanBePiped<View, decltype(std::views::drop(NotADifferenceType{}))>);
+    }
+  }
+
+  {
+    static_assert(std::same_as<decltype(std::views::drop), decltype(std::ranges::views::drop)>);
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}