[libcxx][ranges] Add contiguous_range.

[• Quuxplusone]

LGTM % comments.

libcxx/test/std/containers/sequences/deque/range_concept_conformance.compile.pass.cpp

26

deque<T> is not a contiguous range. Add ! here and below.

libcxx/test/std/containers/sequences/vector.bool/range_concept_conformance.compile.pass.cpp

26

vector<bool> is not a contiguous range. Add ! here and below.

libcxx/test/std/ranges/range.req/range.refinements/contiguous_range.compile.pass.cpp

15

contiguous_range

43–47

I was initially confused by the name, as this class has no data members... but then I saw: the trick is that X::data() member function has a return type that is different from std::add_pointer_t<ranges::range_reference_t<X>>.
I think it'd be worth replacing this test (or at augmenting it) with both of these:

struct WrongConstness {
    const int *begin() const;
    const int *end() const;
    int *data() const;
};
static_assert(std::ranges::random_access_range<WrongConstness>);
static_assert(!std::ranges::contiguous_range<WrongConstness>);

struct NotPtr {
    contiguous_iterator<const int*> begin() const;
    contiguous_iterator<const int*> end() const;
    contiguous_iterator<const int*> data() const;
};
static_assert(std::ranges::random_access_range<NotPtr>);
static_assert(!std::ranges::contiguous_range<NotPtr>);

libcxx/test/std/ranges/range.req/range.refinements/subsumption.compile.pass.cpp

28

Whitespace: Please indent requires by one level (here and throughout). E.g.

template<...>
  requires ...
bool foo() {
  return ...
}

It'd be nice to remove the [[nodiscard]]s while you're at it.

[cjdb]

libcxx/test/std/ranges/range.req/range.refinements/contiguous_range.compile.pass.cpp

43–47

I was initially confused by the name, as this class has no data members... but then I saw: the trick is that X::data() member function has a return type that is different from std::add_pointer_t<ranges::range_reference_t<X>>.

I propose renaming to BadDataMemberFunction.

We should also have a check for when a range can satisfy contiguous_range<R>, but not contiguous_range<R const>.

libcxx/test/std/ranges/range.req/range.refinements/subsumption.compile.pass.cpp

28

@ldionne left it up to me to decide how libc++ formats requires clauses, and I decided that they shouldn't be indented.

[ldionne]

Can we also remove the TODO in ref_view::data() in this patch?

libcxx/include/__ranges/concepts.h

1

We're missing a few concepts in the synopsis in <ranges>. I think we're only missing random_access_range and contiguous_range -- can you update that part of the synopsis in this patch?

[zoecarver]

libcxx/include/__ranges/concepts.h

1

Hmm, the two I implemented... 🤔

libcxx/test/std/ranges/range.req/range.refinements/contiguous_range.compile.pass.cpp

43–47

Thanks for the suggestions. Arthur, I added your first test only (with some modification). The NotPtr test doesn't work because contiguous_iterator has an element_type.

libcxx/test/std/ranges/range.req/range.refinements/subsumption.compile.pass.cpp

28

I'm going to match the existing format of this file. I would support a nfc commit that updated all the requires in this file.

[zoecarver]

Apply review comments.

[cjdb]

libcxx/test/std/ranges/range.req/range.refinements/contiguous_range.compile.pass.cpp

43–47

This still isn't complete, because now we're missing a test case for when both contiguous_range<T> and contiguous_range<T const> are true, and one for when only contiguous_range<T const> is true.

libcxx/test/std/ranges/range.req/range.refinements/subsumption.compile.pass.cpp

28

Let's not take any action till Louis and I resolve our discussion.

[• Quuxplusone]

libcxx/test/std/ranges/range.req/range.refinements/contiguous_range.compile.pass.cpp

43–47

Arthur, I added your first test only (with some modification). The NotPtr test doesn't work because contiguous_iterator has an element_type.

Ah. My intent with NotPtr was that contiguous_range<NotPtr> would not be satisfied because NotPtr().data()'s return type is not std::same_as<std::add_pointer_t<ranges::range_reference_t<T>>>. However, I see now that the thing-we're-taking-the-return-type-of in contiguous_range is not NotPtr().data() but instead std::ranges::data(NotPtr()), which actually evaluates to std::to_address(NotPtr().begin()), not NotPtr().data(), in this case.

So then actually maybe it would be worthwhile to add a test like this:

struct WrongObjectness { // https://godbolt.org/z/M7fbvj7fE
    const int *begin() const;
    const int *end() const;
    void *data() const;
};
static_assert(std::ranges::contiguous_range<WrongObjectness>);

which verifies that if data() exists but is completely the wrong return type, then there's no problem at all. (Did I ever mention how overcomplicated Ranges is? :P)

[ldionne]

Please resolve the concerns about testing raised by other reviewers, but apart from that, LGTM.

[zoecarver]

Rebase. Update based on review.

Will be landed when CI is green.

libcxx/test/std/ranges/range.req/range.refinements/contiguous_range.compile.pass.cpp

43–47

when both contiguous_range<T> and contiguous_range<T const> are true,

That's test_range<contiguous_iterator>.

and one for when only contiguous_range<T const> is true.

Added.

43–47

So then actually maybe it would be worthwhile to add a test like this:

I considered adding a test like this. I don't see how it's really different than the const tests (in both cases it fails because the types are not the same). I think it would be hard to write an implementation that said "if this is the same return type with different constness, that's bad, but if it's a totally unrelated types, that's OK."

I suppose it wouldn't hurt to have a case where they both returned const pointers. I'll add a similar test but where the return type is const char *.

[• Quuxplusone]

libcxx/test/std/ranges/range.req/range.refinements/contiguous_range.compile.pass.cpp

43–47

Wait, on this latest point I think I'm right and you're confused. My WrongObjectness test above is supposed to pass, not fail, even though the return type of data is not the same as the return type of begin — because it is so different that we wrap around and become a contiguous range again! (Try the godbolt link.)
If my WrongObjectness test did just fail, then it would be boring, I'd agree.

[zoecarver]

libcxx/test/std/ranges/range.req/range.refinements/contiguous_range.compile.pass.cpp

43–47

Oh, interesting. I see (because ranges::data won't pick the data member function). Sorry I didn't see this comment until I landed the patch. I'll make a follow up commit.

libcxx/include/__ranges/concepts.h

 // -*- C++ -*-
 //===--------------------- __ranges/concepts.h ----------------------------===//
 //
 // 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_CONCEPTS_H
 #define _LIBCPP___RANGES_CONCEPTS_H
 
 #include <__config>
 #include <__iterator/concepts.h>
 #include <__iterator/incrementable_traits.h>
 #include <__iterator/iter_move.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/readable_traits.h>
 #include <__ranges/access.h>
 #include <__ranges/enable_borrowed_range.h>
+#include <__ranges/data.h>
 #include <__ranges/enable_view.h>
 #include <__ranges/size.h>
 #include <concepts>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
namespace ranges {
 
   template <class _Tp>
   concept bidirectional_range = forward_range<_Tp> && bidirectional_iterator<iterator_t<_Tp> >;
 
   template <class _Tp>
   concept random_access_range =
       bidirectional_range<_Tp> && random_access_iterator<iterator_t<_Tp> >;
 
-  template <class _Tp>
+  template<class _Tp>
+  concept contiguous_range =
+    random_access_range<_Tp> &&
+    contiguous_iterator<iterator_t<_Tp>> &&
+    requires(_Tp& __t) {
+      { ranges::data(__t) } -> same_as<add_pointer_t<range_reference_t<_Tp>>>;
+    };
+
+  template <class _Tp>
   concept common_range = range<_Tp> && same_as<iterator_t<_Tp>, sentinel_t<_Tp> >;
 } // namespace ranges
 
 #endif // !defined(_LIBCPP_HAS_NO_RANGES)
 
 // clang-format on
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___RANGES_CONCEPTS_H

libcxx/include/__ranges/ref_view.h

public:
     constexpr bool empty() const
       requires requires { ranges::empty(*__range_); }
     { return ranges::empty(*__range_); }
 
     constexpr auto size() const
       requires sized_range<_Range>
     { return ranges::size(*__range_); }
 
-    // TODO: This needs to use contiguous_range.
     constexpr auto data() const
-      requires contiguous_iterator<iterator_t<_Range>>
+      requires contiguous_range<_Range>
     { return ranges::data(*__range_); }
   };
 
   template<class _Range>
   ref_view(_Range&) -> ref_view<_Range>;
 
 } // namespace ranges
 
 #endif // !defined(_LIBCPP_HAS_NO_RANGES)
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___RANGES_REF_VIEW_H

libcxx/include/ranges

template<class T>
     concept input_range = see below;
 
   template<class T>
     concept forward_range = see below;
 
   template<class T>
   concept bidirectional_range = see below;
 
+  template<class T>
+  concept random_access_range = see below;
+
+  template<class T>
+  concept contiguous_range = see below;
+
   template <class _Tp>
     concept common_range = see below;
 
   // [view.interface], class template view_interface
   template<class D>
     requires is_class_v<D> && same_as<D, remove_cv_t<D>>
   class view_interface;
 

libcxx/test/std/containers/sequences/array/range_concept_conformance.compile.pass.cpp

 
 using range = std::array<int, 10>;
 namespace stdr = std::ranges;
 
 static_assert(!stdr::view<range>);
 static_assert(std::same_as<stdr::iterator_t<range>, range::iterator>);
 static_assert(stdr::common_range<range>);
 static_assert(stdr::random_access_range<range>);
+static_assert(stdr::contiguous_range<range>);
 static_assert(stdr::sized_range<range>);
 static_assert(!stdr::borrowed_range<range>);
 
 static_assert(!stdr::view<range const>);
 static_assert(std::same_as<stdr::iterator_t<range const>, range::const_iterator>);
 static_assert(stdr::common_range<range const>);
 static_assert(stdr::random_access_range<range const>);
+static_assert(stdr::contiguous_range<range const>);
 static_assert(stdr::sized_range<range const>);
 static_assert(!stdr::borrowed_range<range const>);

libcxx/test/std/containers/sequences/deque/range_concept_conformance.compile.pass.cpp

 #include <ranges>
 
 using range = std::deque<int>;
 namespace stdr = std::ranges;
 
 static_assert(std::same_as<stdr::iterator_t<range>, range::iterator>);
 static_assert(stdr::common_range<range>);
 static_assert(stdr::random_access_range<range>);
+static_assert(!stdr::contiguous_range<range>);
 static_assert(!stdr::view<range>);
 static_assert(stdr::sized_range<range>);
 static_assert(!stdr::borrowed_range<range>);
 
 static_assert(std::same_as<stdr::iterator_t<range const>, range::const_iterator>);
 static_assert(stdr::common_range<range const>);
 static_assert(stdr::random_access_range<range const>);
+static_assert(!stdr::contiguous_range<range const>);
 static_assert(!stdr::view<range const>);
 static_assert(stdr::sized_range<range const>);
 static_assert(!stdr::borrowed_range<range const>);

libcxx/test/std/containers/sequences/vector.bool/range_concept_conformance.compile.pass.cpp

 #include <ranges>
 
 using range = std::vector<bool>;
 namespace stdr = std::ranges;
 
 static_assert(std::same_as<stdr::iterator_t<range>, range::iterator>);
 static_assert(stdr::common_range<range>);
 static_assert(stdr::random_access_range<range>);
+static_assert(!stdr::contiguous_range<range>);
 static_assert(!stdr::view<range>);
 static_assert(stdr::sized_range<range>);
 static_assert(!stdr::borrowed_range<range>);
 
 static_assert(std::same_as<stdr::iterator_t<range const>, range::const_iterator>);
 static_assert(stdr::common_range<range const>);
 static_assert(stdr::random_access_range<range const>);
+static_assert(!stdr::contiguous_range<range const>);
 static_assert(!stdr::view<range const>);
 static_assert(stdr::sized_range<range const>);
 static_assert(!stdr::borrowed_range<range const>);

libcxx/test/std/containers/sequences/vector/range_concept_conformance.compile.pass.cpp

 #include <ranges>
 
 using range = std::vector<int>;
 namespace stdr = std::ranges;
 
 static_assert(std::same_as<stdr::iterator_t<range>, range::iterator>);
 static_assert(stdr::common_range<range>);
 static_assert(stdr::random_access_range<range>);
+static_assert(stdr::contiguous_range<range>);
 static_assert(!stdr::view<range>);
 static_assert(stdr::sized_range<range>);
 static_assert(!stdr::borrowed_range<range>);
 
 static_assert(std::same_as<stdr::iterator_t<range const>, range::const_iterator>);
 static_assert(stdr::common_range<range const>);
 static_assert(stdr::random_access_range<range const>);
+static_assert(stdr::contiguous_range<range const>);
 static_assert(!stdr::view<range const>);
 static_assert(stdr::sized_range<range const>);
 static_assert(!stdr::borrowed_range<range const>);

libcxx/test/std/containers/views/range_concept_conformance.compile.pass.cpp

 #include <ranges>
 
 using range = std::span<int>;
 namespace stdr = std::ranges;
 
 static_assert(std::same_as<stdr::iterator_t<range>, range::iterator>);
 static_assert(stdr::common_range<range>);
 static_assert(stdr::random_access_range<range>);
+static_assert(stdr::contiguous_range<range>);
 static_assert(stdr::view<range> && stdr::enable_view<range>);
 static_assert(stdr::sized_range<range>);
 static_assert(stdr::borrowed_range<range>);
 
 static_assert(std::same_as<stdr::iterator_t<range const>, range::iterator>);
 static_assert(stdr::common_range<range const>);
 static_assert(stdr::random_access_range<range const>);
+static_assert(stdr::contiguous_range<range const>);
 static_assert(!stdr::view<range const> && !stdr::enable_view<range const>);
 static_assert(stdr::sized_range<range const>);
 static_assert(stdr::borrowed_range<range const>);

libcxx/test/std/ranges/range.req/range.refinements/contiguous_range.compile.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
+
+// template<range _Rp>
+// concept contiguous_range;
+
+#include <ranges>
+
+#include "test_range.h"
+#include "test_iterators.h"
+
+namespace ranges = std::ranges;
+
+template <template <class...> class I>
+constexpr bool check_range() {
+  constexpr bool result = ranges::contiguous_range<test_range<I> >;
+  static_assert(ranges::contiguous_range<test_range<I> const> == result);
+  static_assert(ranges::contiguous_range<test_non_const_common_range<I> > == result);
+  static_assert(ranges::contiguous_range<test_non_const_range<I> > == result);
+  static_assert(ranges::contiguous_range<test_common_range<I> > == result);
+  static_assert(ranges::contiguous_range<test_common_range<I> const> == result);
+  static_assert(!ranges::contiguous_range<test_non_const_common_range<I> const>);
+  static_assert(!ranges::contiguous_range<test_non_const_range<I> const>);
+  return result;
+}
+
+static_assert(!check_range<cpp20_input_iterator>());
+static_assert(!check_range<forward_iterator>());
+static_assert(!check_range<bidirectional_iterator>());
+static_assert(!check_range<random_access_iterator>());
+static_assert(check_range<contiguous_iterator>());
+
+struct ContiguousWhenNonConst {
+    const int *begin() const;
+    const int *end() const;
+    int *begin();
+    int *end();
+    int *data() const;
+};
+static_assert( std::ranges::random_access_range<ContiguousWhenNonConst>);
+static_assert( std::ranges::contiguous_range<ContiguousWhenNonConst>);
+static_assert(!std::ranges::contiguous_range<const ContiguousWhenNonConst>);
+
+struct ContiguousWhenConst {
+    const int *begin() const;
+    const int *end() const;
+    int *begin();
+    int *end();
+    const int *data() const;
+};
+static_assert( std::ranges::random_access_range<ContiguousWhenConst>);
+static_assert(!std::ranges::contiguous_range<ContiguousWhenConst>);
+static_assert( std::ranges::contiguous_range<const ContiguousWhenConst>);
+
+struct DataFunctionWrongReturnType {
+    const int *begin() const;
+    const int *end() const;
+    const char *data() const;
+};
+static_assert( std::ranges::random_access_range<DataFunctionWrongReturnType>);
+static_assert(!std::ranges::contiguous_range<const DataFunctionWrongReturnType>);

libcxx/test/std/ranges/range.req/range.refinements/subsumption.compile.pass.cpp

 
 #include <iterator>
 
 struct range {
   int* begin();
   int* end();
 };
 
-// clang-format off
 template<std::ranges::range R>
-requires std::input_iterator<std::ranges::iterator_t<R> >
+requires std::input_iterator<std::ranges::iterator_t<R>>
 [[nodiscard]] constexpr bool check_input_range_subsumption() {
   return false;
 }
 
 template<std::ranges::input_range>
 requires true
 [[nodiscard]] constexpr bool check_input_range_subsumption() {
   return true;
 }
-// clang-format on
 
 static_assert(check_input_range_subsumption<range>());
 
-// clang-format off
 template<std::ranges::input_range R>
-requires std::forward_iterator<std::ranges::iterator_t<R> >
+requires std::forward_iterator<std::ranges::iterator_t<R>>
 [[nodiscard]] constexpr bool check_forward_range_subsumption() {
   return false;
 }
 
 template<std::ranges::forward_range>
 requires true
 [[nodiscard]] constexpr bool check_forward_range_subsumption() {
   return true;
 }
-// clang-format on
 
 static_assert(check_forward_range_subsumption<range>());
 
-// clang-format off
 template<std::ranges::forward_range R>
-requires std::bidirectional_iterator<std::ranges::iterator_t<R> >
+requires std::bidirectional_iterator<std::ranges::iterator_t<R>>
 [[nodiscard]] constexpr bool check_bidirectional_range_subsumption() {
   return false;
 }
 
 template<std::ranges::bidirectional_range>
 requires true
 [[nodiscard]] constexpr bool check_bidirectional_range_subsumption() {
   return true;
 }
-// clang-format on
 
 static_assert(check_bidirectional_range_subsumption<range>());
 
 template<std::ranges::bidirectional_range R>
-requires std::random_access_iterator<std::ranges::iterator_t<R> >
+requires std::random_access_iterator<std::ranges::iterator_t<R>>
 constexpr bool check_random_access_range_subsumption() {
   return false;
 }
 
 template<std::ranges::random_access_range>
 requires true
 constexpr bool check_random_access_range_subsumption() {
   return true;
 }
 
 static_assert(check_random_access_range_subsumption<range>());
+
+template<std::ranges::random_access_range R>
+requires std::random_access_iterator<std::ranges::iterator_t<R>>
+constexpr bool check_contiguous_range_subsumption() {
+  return false;
+}
+
+template<std::ranges::contiguous_range>
+requires true
+constexpr bool check_contiguous_range_subsumption() {
+  return true;
+}
+
+static_assert(check_contiguous_range_subsumption<range>());

libcxx/test/std/re/re.results/range_concept_conformance.compile.pass.cpp

 #include <concepts>
 #include <ranges>
 
 namespace stdr = std::ranges;
 
 static_assert(std::same_as<stdr::iterator_t<std::cmatch>, std::cmatch::iterator>);
 static_assert(stdr::common_range<std::cmatch>);
 static_assert(stdr::random_access_range<std::cmatch>);
+static_assert(stdr::contiguous_range<std::cmatch>);
 static_assert(!stdr::view<std::cmatch>);
 static_assert(stdr::sized_range<std::cmatch>);
 static_assert(!stdr::borrowed_range<std::cmatch>);
 
 static_assert(std::same_as<stdr::iterator_t<std::cmatch const>, std::cmatch::const_iterator>);
 static_assert(stdr::common_range<std::cmatch const>);
 static_assert(stdr::random_access_range<std::cmatch const>);
+static_assert(stdr::contiguous_range<std::cmatch const>);
 static_assert(!stdr::view<std::cmatch const>);
 static_assert(stdr::sized_range<std::cmatch const>);
 static_assert(!stdr::borrowed_range<std::cmatch const>);

libcxx/test/std/strings/basic.string/range_concept_conformance.compile.pass.cpp

 #include <concepts>
 #include <ranges>
 
 namespace stdr = std::ranges;
 
 static_assert(std::same_as<stdr::iterator_t<std::string>, std::string::iterator>);
 static_assert(stdr::common_range<std::string>);
 static_assert(stdr::random_access_range<std::string>);
+static_assert(stdr::contiguous_range<std::string>);
 static_assert(!stdr::view<std::string>);
 static_assert(stdr::sized_range<std::string>);
 static_assert(!stdr::borrowed_range<std::string>);
 
 static_assert(std::same_as<stdr::iterator_t<std::string const>, std::string::const_iterator>);
 static_assert(stdr::common_range<std::string const>);
 static_assert(stdr::random_access_range<std::string const>);
+static_assert(stdr::contiguous_range<std::string const>);
 static_assert(!stdr::view<std::string const>);
 static_assert(stdr::sized_range<std::string const>);
 static_assert(!stdr::borrowed_range<std::string const>);

libcxx/test/std/strings/string.view/range_concept_conformance.compile.pass.cpp

 #include <concepts>
 #include <ranges>
 
 namespace stdr = std::ranges;
 
 static_assert(std::same_as<stdr::iterator_t<std::string_view>, std::string_view::iterator>);
 static_assert(stdr::common_range<std::string_view>);
 static_assert(stdr::random_access_range<std::string_view>);
+static_assert(stdr::contiguous_range<std::string_view>);
 static_assert(stdr::view<std::string_view> && stdr::enable_view<std::string_view>);
 static_assert(stdr::sized_range<std::string_view>);
 static_assert(stdr::borrowed_range<std::string_view>);
 
 static_assert(std::same_as<stdr::iterator_t<std::string_view const>, std::string_view::const_iterator>);
 static_assert(stdr::common_range<std::string_view const>);
 static_assert(stdr::random_access_range<std::string_view const>);
+static_assert(stdr::contiguous_range<std::string_view const>);
 static_assert(!stdr::view<std::string_view const> && !stdr::enable_view<std::string_view const>);
 static_assert(stdr::sized_range<std::string_view const>);
 static_assert(stdr::borrowed_range<std::string_view const>);