[libcxx][ranges] Add `views::counted` CPO.

[zoecarver]

Go through list of things in the docs.

[ldionne]

libcxx/include/__ranges/counted.h

40

Throughout, could you use _Iter instead of _Tp and perhaps __it instead of __t? I think it conveys the meaning a bit better.

libcxx/test/std/ranges/range.adaptors/range.counted/counted.pass.cpp

2

We need to test that views::counted is a CPO, see http://eel.is/c++draft/customization.point.object.

4

Can you add a test that views::counted(iter, diff) is SFINAEd out when diff is not convertible to the iter_difference_t of iter, per http://eel.is/c++draft/range.adaptors#range.counted-2?

30

I'm not immediately seeing why this is std::span<const int> and not std::span<int>, can you explain?

74

Can you also add a test with a forward_iterator?

[zoecarver]

libcxx/test/std/ranges/range.adaptors/range.counted/counted.pass.cpp

2

Added a test for semiregular. Are there other tests you want? Maybe noexcept tests?

74

Good idea. But I don't think forward iterator tests that much new stuff, so I added tests for cpp20_input_iterator and output_iterator.

[zoecarver]

Address Louis' comments.

[ldionne]

libcxx/include/__ranges/counted.h

43

libcxx/test/std/ranges/range.adaptors/range.counted/counted.pass.cpp

2

I think that's fine.

30

Also, can you please static_assert(std::is_same_v<decltype(std::views::counted(...)), what-you-expect>);. Otherwise, we're potentially relying on conversions between span-to-const and span-to-non-const.

Let's figure out the const situation below, because it makes little sense to my understanding.

52

Can you also add tests for contiguous_iterator<int const*>? And for all the other iterator categories below.

[zoecarver]

Apply Louis' feedback.

[ldionne]

Based on the CI failures, you've got some missing #include. Ship it once the CI is happy!

[tcanens]

libcxx/include/__ranges/counted.h

43

There are things that are implicitly-but-not-explicitly convertible to iter_difference_t<_Iter>, in which case this compiles but the wording calls for rejection.

48

Why the static_cast to the same type?

The forward is also unnecessary - the to_address overload for non-pointers should take by const& anyway.

61

For __sent shouldn't it be a move?

[• Quuxplusone]

libcxx/include/__ranges/counted.h

61

Yes, and naming-bikeshed: can we call it __last instead of __sent? __sent looks like it should be a variable of type _Sent/_Sp, not an _Iter.
IOW, seeing forward<_Iter>(__sent) was the red flag here.

Also on line 56, noexcept(ranges::subrange(_VSTD::forward<_Iter>(__it), _VSTD::__decay_copy(__it)))
or something like that. Gross. Does the standard say "expression-equivalent" so we have to get this right? or is leaving it as non-noexcept an option?

libcxx/test/std/ranges/range.adaptors/range.counted/counted.pass.cpp

30

@ldionne: The situation here is easy, unless I'm mistaken: std::views::counted((int*)iter, 8) returns a span<int>, which is implicitly convertible to span<const int>, so that's what happens.
I agree that there should be a static_assert on the actual decltype, because actually tons of types are implicitly convertible to span<const int>. Including subrange<int*,int*>, for example, which would totally not be the conforming type to return here.

[zoecarver]

Apply review comments. Fix build.

libcxx/include/__ranges/counted.h

48

Now that the second parameter is a template type parameter type I'm going to keep the static_cast.

[zoecarver]

Fix build again.

[zoecarver]

Fix the 32 bit bots.

[zoecarver]

Fix the 32 bit bots for real.

libcxx/docs/Status/RangesPaper.csv

 `[range.filter] <http://wg21.link/range.filter>`_,filter_view,[range.all],Louis Dionne,Not started
 `[range.transform] <http://wg21.link/range.transform>`_,`transform_view <https://llvm.org/D103056>`_,[range.all],Zoe Carver,✅
 `[range.iota] <http://wg21.link/range.iota>`_,iota_view,[range.all],Zoe Carver,In Progress
 `[range.take] <http://wg21.link/range.take>`_,take_view,[range.all],Zoe Carver,✅
 `[range.join] <http://wg21.link/range.join>`_,join_view,[range.all],Zoe Carver,In Progress
 `[range.empty] <http://wg21.link/range.empty>`_,`empty_view <https://llvm.org/D103208>`_,[view.interface],Zoe Carver,✅
 `[range.single] <http://wg21.link/range.single>`_,single_view,[view.interface],Zoe Carver,✅
 `[range.split] <http://wg21.link/range.split>`_,split_view,[range.all],Zoe Carver,In Progress
-`[range.counted] <http://wg21.link/range.counted>`_,view::counted,[range.subrange],Zoe Carver,Not started
+`[range.counted] <http://wg21.link/range.counted>`_,view::counted,[range.subrange],Zoe Carver,✅
 `[range.common] <http://wg21.link/range.common>`_,common_view,[range.all],Zoe Carver,✅
 `[range.reverse] <http://wg21.link/range.reverse>`_,reverse_view,[range.all],Zoe Carver,✅

libcxx/include/CMakeLists.txt

set(files
   __node_handle
   __nullptr
   __random/uniform_int_distribution.h
   __ranges/access.h
   __ranges/all.h
   __ranges/common_view.h
   __ranges/concepts.h
   __ranges/copyable_box.h
+  __ranges/counted.h
   __ranges/dangling.h
   __ranges/data.h
   __ranges/drop_view.h
   __ranges/empty_view.h
   __ranges/empty.h
   __ranges/enable_borrowed_range.h
   __ranges/enable_view.h
   __ranges/non_propagating_cache.h

libcxx/include/__ranges/counted.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_COUNTED_H
+#define _LIBCPP___RANGES_COUNTED_H
+
+#include <__config>
+#include <__iterator/concepts.h>
+#include <__iterator/counted_iterator.h>
+#include <__iterator/default_sentinel.h>
+#include <__iterator/incrementable_traits.h>
+#include <__iterator/iterator_traits.h>
+#include <__memory/pointer_traits.h>
+#include <__ranges/concepts.h>
+#include <__ranges/subrange.h>
+#include <__utility/__decay_copy.h>
+#include <__utility/declval.h>
+#include <__utility/forward.h>
+#include <__utility/move.h>
+#include <span>
+#include <type_traits>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if !defined(_LIBCPP_HAS_NO_RANGES)
+
+namespace views {
+
+namespace __counted {
+  template<class _From, class _To>
+  concept __explicitly_convertible = requires {
+    _To(_From{});
+  };
+
+  struct __fn {
+    template<class _Iter, class _Diff>
+      requires contiguous_iterator<decay_t<_Iter>> &&
+               __explicitly_convertible<_Diff, iter_difference_t<_Iter>>
+    _LIBCPP_HIDE_FROM_ABI
+    constexpr auto operator()(_Iter&& __it, _Diff __c) const
+      noexcept(noexcept(
+        span(_VSTD::to_address(__it), static_cast<iter_difference_t<_Iter>>(__c))
+      ))
+    {
+      return span(_VSTD::to_address(__it), static_cast<iter_difference_t<_Iter>>(__c));
+    }
+
+    template<class _Iter, class _Diff>
+      requires random_access_iterator<decay_t<_Iter>> &&
+               __explicitly_convertible<_Diff, iter_difference_t<_Iter>>
+    _LIBCPP_HIDE_FROM_ABI
+    constexpr auto operator()(_Iter&& __it, _Diff __c) const
+      noexcept(
+        noexcept(__it + static_cast<iter_difference_t<_Iter>>(__c)) &&
+        noexcept(ranges::subrange(_VSTD::forward<_Iter>(__it), _VSTD::__decay_copy(__it)))
+      )
+    {
+      auto __last = __it + static_cast<iter_difference_t<_Iter>>(__c);
+      return ranges::subrange(_VSTD::forward<_Iter>(__it), _VSTD::move(__last));
+    }
+
+    template<class _Iter, class _Diff>
+      requires __explicitly_convertible<_Diff, iter_difference_t<_Iter>>
+    _LIBCPP_HIDE_FROM_ABI
+    constexpr auto operator()(_Iter&& __it, _Diff __c) const
+      noexcept(noexcept(
+        ranges::subrange(counted_iterator(_VSTD::forward<_Iter>(__it), __c), default_sentinel)
+      ))
+    {
+      return ranges::subrange(counted_iterator(_VSTD::forward<_Iter>(__it), __c), default_sentinel);
+    }
+  };
+}
+
+inline namespace __cpo {
+  inline constexpr auto counted = __counted::__fn{};
+} // namespace __cpo
+
+} // namespace views
+
+#endif // !defined(_LIBCPP_HAS_NO_RANGES)
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___RANGES_COUNTED_H

libcxx/include/module.modulemap

module ranges {
     export *
 
     module __ranges {
       module access                 { private header "__ranges/access.h"                }
       module all                    { private header "__ranges/all.h"                   }
       module common_view            { private header "__ranges/common_view.h"           }
       module concepts               { private header "__ranges/concepts.h"              }
       module copyable_box           { private header "__ranges/copyable_box.h"          }
+      module counted                { private header "__ranges/counted.h"               }
       module dangling               { private header "__ranges/dangling.h"              }
       module data                   { private header "__ranges/data.h"                  }
       module drop_view              { private header "__ranges/drop_view.h"             }
       module empty                  { private header "__ranges/empty.h"                 }
       module empty_view             { private header "__ranges/empty_view.h"            }
       module enable_borrowed_range  { private header "__ranges/enable_borrowed_range.h" }
       module enable_view            { private header "__ranges/enable_view.h"           }
       module non_propagating_cache  { private header "__ranges/non_propagating_cache.h" }

libcxx/include/ranges

namespace std::ranges {
 
   // [range.transform], transform view
   template<input_range V, copy_constructible F>
     requires view<V> && is_object_v<F> &&
              regular_invocable<F&, range_reference_t<V>> &&
              can-reference<invoke_result_t<F&, range_reference_t<V>>>
   class transform_view;
 
+  // [range.counted], counted view
+  namespace views { inline constexpr unspecified counted = unspecified; }
+
   // [range.common], common view
   template<view V>
     requires (!common_range<V> && copyable<iterator_t<V>>)
   class common_view;
 
  // [range.reverse], reverse view
   template<view V>
     requires bidirectional_range<V>

 #include <version>
 // Only enable the contents of the header when libc++ was build with LIBCXX_ENABLE_INCOMPLETE_FEATURES enabled
 #if !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 #include <__config>
 #include <__ranges/access.h>
 #include <__ranges/all.h>
 #include <__ranges/common_view.h>
+#include <__ranges/counted.h>
 #include <__ranges/concepts.h>
 #include <__ranges/dangling.h>
 #include <__ranges/data.h>
 #include <__ranges/drop_view.h>
 #include <__ranges/empty.h>
 #include <__ranges/empty_view.h>
 #include <__ranges/enable_borrowed_range.h>
 #include <__ranges/enable_view.h>

libcxx/test/libcxx/diagnostics/detail.headers/ranges/counted.module.verify.cpp

+// -*- 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
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: modules-build
+
+// WARNING: This test was generated by 'generate_private_header_tests.py'
+// and should not be edited manually.
+
+// expected-error@*:* {{use of private header from outside its module: '__ranges/counted.h'}}
+#include <__ranges/counted.h>

libcxx/test/std/ranges/range.adaptors/range.counted/counted.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: gcc-10
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// std::views::counted;
+
+#include <concepts>
+#include <ranges>
+#include <span>
+
+#include <cassert>
+#include "test_macros.h"
+#include "test_iterators.h"
+
+struct Unrelated {};
+
+struct ConvertibleToSize {
+  constexpr operator std::ptrdiff_t() const { return 8; }
+};
+
+struct ImplicitlyConvertible {
+    operator short();
+    explicit operator std::ptrdiff_t() = delete;
+};
+
+template<class Iter, class T>
+concept CountedInvocable = requires(Iter& i, T t) { std::views::counted(i, t); };
+
+constexpr bool test() {
+  int buffer[8] = {1, 2, 3, 4, 5, 6, 7, 8};
+
+  {
+    static_assert( CountedInvocable<contiguous_iterator<int*>, ConvertibleToSize>);
+    static_assert(!CountedInvocable<contiguous_iterator<int*>, ImplicitlyConvertible>);
+    static_assert(!CountedInvocable<contiguous_iterator<int*>, Unrelated>);
+
+    static_assert(std::semiregular<std::remove_const_t<decltype(std::views::counted)>>);
+  }
+
+  {
+    {
+      contiguous_iterator<int*> iter(buffer);
+      std::span<int> s = std::views::counted(iter, 8);
+      assert(s.size() == 8);
+      assert(s.data() == buffer);
+
+      ASSERT_SAME_TYPE(decltype(std::views::counted(iter, 8)), std::span<int>);
+    }
+    {
+      const contiguous_iterator<int*> iter(buffer);
+      std::span<int> s = std::views::counted(iter, 8);
+      assert(s.size() == 8);
+      assert(s.data() == buffer);
+
+      ASSERT_SAME_TYPE(decltype(std::views::counted(iter, 8)), std::span<int>);
+    }
+    {
+      contiguous_iterator<const int*> iter(buffer);
+      std::span<const int> s = std::views::counted(iter, 8);
+      assert(s.size() == 8);
+      assert(s.data() == buffer);
+
+      ASSERT_SAME_TYPE(decltype(std::views::counted(iter, 8)), std::span<const int>);
+    }
+    {
+      const contiguous_iterator<const int*> iter(buffer);
+      std::span<const int> s = std::views::counted(iter, 8);
+      assert(s.size() == 8);
+      assert(s.data() == buffer);
+
+      ASSERT_SAME_TYPE(decltype(std::views::counted(iter, 8)), std::span<const int>);
+    }
+  }
+
+  {
+    {
+      random_access_iterator<int*> iter(buffer);
+      std::ranges::subrange<random_access_iterator<int*>> s = std::views::counted(iter, 8);
+      assert(s.size() == 8);
+      assert(s.begin() == iter);
+
+      ASSERT_SAME_TYPE(decltype(std::views::counted(iter, 8)), std::ranges::subrange<random_access_iterator<int*>>);
+    }
+    {
+      const random_access_iterator<int*> iter(buffer);
+      std::ranges::subrange<random_access_iterator<int*>> s = std::views::counted(iter, 8);
+      assert(s.size() == 8);
+      assert(s.begin() == iter);
+
+      ASSERT_SAME_TYPE(decltype(std::views::counted(iter, 8)), std::ranges::subrange<random_access_iterator<int*>>);
+    }
+    {
+      random_access_iterator<const int*> iter(buffer);
+      std::ranges::subrange<random_access_iterator<const int*>> s = std::views::counted(iter, 8);
+      assert(s.size() == 8);
+      assert(s.begin() == iter);
+
+      ASSERT_SAME_TYPE(decltype(std::views::counted(iter, 8)), std::ranges::subrange<random_access_iterator<const int*>>);
+    }
+    {
+      const random_access_iterator<const int*> iter(buffer);
+      std::ranges::subrange<random_access_iterator<const int*>> s = std::views::counted(iter, 8);
+      assert(s.size() == 8);
+      assert(s.begin() == iter);
+
+      ASSERT_SAME_TYPE(decltype(std::views::counted(iter, 8)), std::ranges::subrange<random_access_iterator<const int*>>);
+    }
+  }
+
+  {
+    {
+      bidirectional_iterator<int*> iter(buffer);
+      std::ranges::subrange<
+        std::counted_iterator<bidirectional_iterator<int*>>,
+        std::default_sentinel_t> s = std::views::counted(iter, 8);
+      assert(s.size() == 8);
+      assert(s.begin() == std::counted_iterator(iter, 8));
+
+      ASSERT_SAME_TYPE(decltype(std::views::counted(iter, 8)),
+                       std::ranges::subrange<
+                         std::counted_iterator<bidirectional_iterator<int*>>,
+                         std::default_sentinel_t>);
+    }
+    {
+      const bidirectional_iterator<int*> iter(buffer);
+      std::ranges::subrange<
+        std::counted_iterator<bidirectional_iterator<int*>>,
+        std::default_sentinel_t> s = std::views::counted(iter, 8);
+      assert(s.size() == 8);
+      assert(s.begin() == std::counted_iterator(iter, 8));
+
+      ASSERT_SAME_TYPE(decltype(std::views::counted(iter, 8)),
+                       std::ranges::subrange<
+                         std::counted_iterator<bidirectional_iterator<int*>>,
+                         std::default_sentinel_t>);
+    }
+    {
+      output_iterator<const int*> iter(buffer);
+      std::ranges::subrange<
+        std::counted_iterator<output_iterator<const int*>>,
+        std::default_sentinel_t> s = std::views::counted(iter, 8);
+      assert(s.size() == 8);
+      assert(s.begin() == std::counted_iterator(iter, 8));
+
+      ASSERT_SAME_TYPE(decltype(std::views::counted(iter, 8)),
+                       std::ranges::subrange<
+                         std::counted_iterator<output_iterator<const int*>>,
+                         std::default_sentinel_t>);
+    }
+    {
+      const output_iterator<const int*> iter(buffer);
+      std::ranges::subrange<
+        std::counted_iterator<output_iterator<const int*>>,
+        std::default_sentinel_t> s = std::views::counted(iter, 8);
+      assert(s.size() == 8);
+      assert(s.begin() == std::counted_iterator(iter, 8));
+
+      ASSERT_SAME_TYPE(decltype(std::views::counted(iter, 8)),
+                       std::ranges::subrange<
+                         std::counted_iterator<output_iterator<const int*>>,
+                         std::default_sentinel_t>);
+    }
+    {
+      cpp20_input_iterator<int*> iter(buffer);
+      std::ranges::subrange<
+        std::counted_iterator<cpp20_input_iterator<int*>>,
+        std::default_sentinel_t> s = std::views::counted(std::move(iter), 8);
+      assert(s.size() == 8);
+      assert(s.begin().base().base() == buffer);
+
+      ASSERT_SAME_TYPE(decltype(std::views::counted(std::move(iter), 8)),
+                       std::ranges::subrange<
+                         std::counted_iterator<cpp20_input_iterator<int*>>,
+                         std::default_sentinel_t>);
+    }
+    {
+      std::ranges::subrange<
+        std::counted_iterator<cpp20_input_iterator<int*>>,
+        std::default_sentinel_t> s = std::views::counted(cpp20_input_iterator<int*>(buffer), 8);
+      assert(s.size() == 8);
+      assert(s.begin().base().base() == buffer);
+
+      ASSERT_SAME_TYPE(decltype(std::views::counted(cpp20_input_iterator<int*>(buffer), 8)),
+                       std::ranges::subrange<
+                         std::counted_iterator<cpp20_input_iterator<int*>>,
+                         std::default_sentinel_t>);
+    }
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}