[libcxx][ranges] adds `ranges::range`, `ranges::common_range`, and range aliases

[cjdb]

Summary

• std::ranges::range
• std::ranges::sentinel_t
• std::ranges::range_difference_t
• std::ranges::range_value_t
• std::ranges::range_reference_t
• std::ranges::range_rvalue_reference_t
• std::ranges::common_range

range_size_t depends on sized_range and will be added alongside it.

Implements parts of:

• P0896R4 The One Ranges Proposal`

Depends on D100255.

[cjdb]

rebases to activate CI

[cjdb]

rebases to activate CI

[miscco]

libcxx/include/ranges

27–30

Is there some duplication here?

[cjdb]

uploading so @EricWF can take a look

[cjdb]

rebases to activate CI

[Mordante]

In general looks good. Some minor remarks, but would like to see it pass the CI.

libcxx/include/CMakeLists.txt

137

This seems unintentional.

libcxx/include/__ranges/concepts.h

30

Is the synopsis in the <ranges> header?

42

Please _Uglify. Note more to _Uglify below.

44

Shouldn't

template<sized_­range R>
    using range_size_t = decltype(ranges::size(declval<R&>()));

be included here? Or is it somewhere else? If it's somewhere else can you add a comment like you did for iterator_t?

libcxx/test/std/containers/unord/unord.multimap/range_concept_conformance.compile.pass.cpp

19 ↗

(On Diff #339408)

Why no non-const version?

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

22 ↗

(On Diff #339408)

Can you also test std::basic_string with other character types, wchar_t, char8_t, char16_t, and char32_t?

[cjdb]

• adds std::ranges::common_range
• adds conformance tests
• adds missing content to synopsis
• _Uglifies names

libcxx/include/CMakeLists.txt

137

Oops.

libcxx/include/__ranges/concepts.h

44

Please see the commit message.

libcxx/include/ranges

27–30

Where?

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

22 ↗

(On Diff #339408)

I'm not convinced those will yield anything useful since they're aliases, not specialisations.

[cjdb]

fixes Windows build failure

[Mordante]

libcxx/include/__ranges/concepts.h

44

I see, missed that during the original review.

libcxx/test/std/containers/associative/map/range_concept_conformance.compile.pass.cpp

12 ↗

(On Diff #340329)

Not too fond of this, see my post-commit comments for D101205.

[ldionne]

Overall LGTM, but I think it makes more sense for iterator_t to live in __ranges/concepts.h if possible.

libcxx/include/__ranges/concepts.h

39

That's kinda weird, would it be possible to define it here instead?

[cjdb]

libcxx/include/__ranges/concepts.h

39

Your options are:

• it lives here exclusively, __ranges/access.h (__ranges/end.h in current D100255) needs to use decltype(ranges::begin(declval<_Rp&>())) wherever it currently uses iterator_t
• it lives in __ranges/access.h exclusively, comment remains
• it lives in both

[• Quuxplusone]

libcxx/include/__ranges/concepts.h

39

FWIW, I'd look at the definitions on cppreference:

• iterator_t is the type of ranges::begin, so it belongs next to begin
• sentinel_t is the type of ranges::end, so it belongs next to end
• range_size_tis the type of ranges::size, so it belongs next to size

The other four typedefs probably might as well go into <ranges> until we have a reason to move them elsewhere.

libcxx/include/ranges

50–51

This is listed twice.

[cjdb]

libcxx/include/__ranges/concepts.h

39

FWIW, I'd look at the definitions on cppreference:

Having written a fair chunk of the ranges section of cppreference, I can confidently say it's designed for consumers of C++, not for implementers, so different groupings make sense.

• iterator_t is the type of ranges::begin, so it belongs next to begin
• sentinel_t is the type of ranges::end, so it belongs next to end
• range_size_tis the type of ranges::size, so it belongs next to size

This is a good suggestion (even though cppreference doesn't group them like this), but I'd prefer to group them as per the standard's synopsis.

The other four typedefs probably might as well go into <ranges> until we have a reason to move them elsewhere.

That would make using them in <ranges/*> very awkward.

[ldionne]

libcxx/include/__ranges/concepts.h

39

Hmm, I think I buy Arthur's argument. Either do that or leave as-is, non blocking as far as I'm concerned. Thanks for explaining why I can't just have what I asked for in the first place, though.

[cjdb]

rebases to activate CI

libcxx/include/CMakeLists.txt

set(files
   numeric
   optional
   ostream
   queue
   random
   ratio
   ranges
   __ranges/access.h
+  __ranges/concepts.h
   regex
   scoped_allocator
   semaphore
   set
   setjmp.h
   shared_mutex
   span
   sstream
   stack

libcxx/include/__ranges/concepts.h

+// -*- C++ -*-
+//===-------------------------- concepts ----------------------------------===//
+//
+// 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 <__ranges/access.h>
+#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 ranges {
+// [range.range]
+template <class _Tp>
+concept range = requires(_Tp& __t) {
+  ranges::begin(__t); // sometimes equality-preserving
+  ranges::end(__t);
+};
+
+// `iterator_t` is repeated in <__ranges/access.h> and <__ranges/concepts.h> for clarity's sake.
+template <class _Tp>
+using iterator_t = decltype(ranges::begin(declval<_Tp&>()));
+
+template <range _Rp>
+using sentinel_t = decltype(ranges::end(declval<_Rp&>()));
+
+template <range R>
+using range_difference_t = iter_difference_t<iterator_t<R> >;
+
+template <range R>
+using range_value_t = iter_value_t<iterator_t<R> >;
+
+template <range R>
+using range_reference_t = iter_reference_t<iterator_t<R> >;
+
+template <range R>
+using range_rvalue_reference_t = iter_rvalue_reference_t<iterator_t<R> >;
+} // namespace ranges
+
+#endif // !defined(_LIBCPP_HAS_NO_RANGES)
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP_RANGES_CONCEPTS_H

libcxx/include/ranges

 //     inline constexpr unspecified begin = unspecified;
 //     inline constexpr unspecified end = unspecified;
 //     inline constexpr unspecified cbegin = unspecified;
 //     inline constexpr unspecified cend = unspecified;
 //   }
 //
 //   // [range.range], ranges
 //   template<class T>
+//     concept range = see below;
+//
+//   template<class T>
+//     using iterator_t = decltype(ranges::begin(declval<T&>()));
+//   template<class T>
 //     using iterator_t = decltype(ranges::begin(declval<T&>()));
+//   template<range R>
+//     using sentinel_t = decltype(ranges::end(declval<R&>()));
+//   template<range R>
+//     using range_difference_t = iter_difference_t<iterator_t<R>>;
+//   template<range R>
+//     using range_value_t = iter_value_t<iterator_t<R>>;
+//   template<range R>
+//     using range_reference_t = iter_reference_t<iterator_t<R>>;
+//   template<range R>
+//     using range_rvalue_reference_t = iter_rvalue_reference_t<iterator_t<R>>;
 // }
 
 #ifndef _LIBCPP_RANGES
 #define _LIBCPP_RANGES
 
 #include <compare>              // see [compare.syn]
 #include <initializer_list>     // see [initializer.list.syn]
 #include <iterator>             // see [iterator.synopsis]
 
 #include <__ranges/access.h>
+#include <__ranges/concepts.h>
 
 #endif // _LIBCPP_RANGES

libcxx/test/std/ranges/range.range/helper_aliases.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 R>
+// using range_difference_t = iter_difference_t<iterator_t<R>>;
+
+// template<range R>
+// using range_value_t = iter_value_t<iterator_t<R>>;
+
+// template<range R>
+// using range_reference_t = iter_reference_t<iterator_t<R>>;
+
+// template<range R>
+// using range_rvalue_reference_t = iter_rvalue_reference_t<iterator_t<R>>;
+
+#include <ranges>
+
+#include <concepts>
+#include <deque>
+#include <vector>
+
+#include "test_range.h"
+
+namespace stdr = std::ranges;
+
+static_assert(std::same_as<
+              stdr::range_difference_t<std::vector<int> >,
+              std::iter_difference_t<stdr::iterator_t<std::vector<int> > > >);
+static_assert(
+    std::same_as<stdr::range_difference_t<range<std::deque<int> > >,
+                 std::iter_difference_t<stdr::iterator_t<std::deque<int> > > >);
+
+static_assert(
+    std::same_as<stdr::range_value_t<std::vector<int> >,
+                 std::iter_value_t<stdr::iterator_t<std::vector<int> > > >);
+static_assert(
+    std::same_as<stdr::range_value_t<range<std::deque<int> > >,
+                 std::iter_value_t<stdr::iterator_t<std::deque<int> > > >);
+
+static_assert(
+    std::same_as<stdr::range_reference_t<std::vector<int> >,
+                 std::iter_reference_t<stdr::iterator_t<std::vector<int> > > >);
+static_assert(
+    std::same_as<stdr::range_reference_t<range<std::deque<int> > >,
+                 std::iter_reference_t<stdr::iterator_t<std::deque<int> > > >);
+
+static_assert(
+    std::same_as<
+        stdr::range_rvalue_reference_t<std::vector<int> >,
+        std::iter_rvalue_reference_t<stdr::iterator_t<std::vector<int> > > >);
+static_assert(
+    std::same_as<
+        stdr::range_rvalue_reference_t<range<std::deque<int> > >,
+        std::iter_rvalue_reference_t<stdr::iterator_t<std::deque<int> > > >);

libcxx/test/std/ranges/range.range/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<class T>
+// concept range;
+
+#include <ranges>
+
+#include <array>
+#include <deque>
+#include <forward_list>
+#include <list>
+#include <map>
+#include <set>
+#include <string>
+#include <string_view>
+#include <unordered_map>
+#include <unordered_set>
+#include <vector>
+
+#include "test_range.h"
+
+namespace stdr = std::ranges;
+
+static_assert(stdr::range<std::array<int, 10> >);
+static_assert(stdr::range<std::deque<int> >);
+static_assert(stdr::range<std::forward_list<int> >);
+static_assert(stdr::range<std::list<int> >);
+static_assert(stdr::range<std::map<int, long> >);
+static_assert(stdr::range<std::multimap<int, long> >);
+static_assert(stdr::range<std::multiset<int> >);
+static_assert(stdr::range<std::set<int> >);
+static_assert(stdr::range<std::string>);
+static_assert(stdr::range<std::string_view>);
+static_assert(stdr::range<std::unordered_map<int, long> >);
+static_assert(stdr::range<std::unordered_multimap<int, long> >);
+static_assert(stdr::range<std::unordered_multiset<int> >);
+static_assert(stdr::range<std::unordered_set<int> >);
+static_assert(stdr::range<std::vector<int> >);
+
+static_assert(stdr::range<range<std::array<int, 10> > >);
+static_assert(stdr::range<range<std::deque<int> > >);
+static_assert(stdr::range<range<std::forward_list<int> > >);
+static_assert(stdr::range<range<std::list<int> > >);
+static_assert(stdr::range<range<std::map<int, long> > >);
+static_assert(stdr::range<range<std::multimap<int, long> > >);
+static_assert(stdr::range<range<std::multiset<int> > >);
+static_assert(stdr::range<range<std::set<int> > >);
+static_assert(stdr::range<range<std::string> >);
+static_assert(stdr::range<range<std::string_view> >);
+static_assert(stdr::range<range<std::unordered_map<int, long> > >);
+static_assert(stdr::range<range<std::unordered_multimap<int, long> > >);
+static_assert(stdr::range<range<std::unordered_multiset<int> > >);
+static_assert(stdr::range<range<std::unordered_set<int> > >);
+static_assert(stdr::range<range<std::vector<int> > >);
+
+struct incompatible_iterators {
+  std::vector<int>::iterator begin();
+  std::deque<int>::iterator end();
+};
+static_assert(!stdr::range<incompatible_iterators>);
+
+struct int_begin_int_end {
+  int begin();
+  int end();
+};
+static_assert(!stdr::range<int_begin_int_end>);
+
+struct iterator_begin_int_end {
+  std::vector<int>::iterator begin();
+  int end();
+};
+static_assert(!stdr::range<iterator_begin_int_end>);
+
+struct int_begin_iterator_end {
+  int begin();
+  std::vector<int>::iterator end();
+};
+static_assert(!stdr::range<int_begin_iterator_end>);

libcxx/test/std/ranges/range.range/sentinel_t.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>
+// using sentinel_t = decltype(ranges::end(declval<_Rp&>()));
+
+#include <ranges>
+
+#include <concepts>
+#include <forward_list>
+#include <iterator>
+#include <list>
+#include <deque>
+#include <vector>
+
+#include "test_range.h"
+
+namespace stdr = std::ranges;
+
+static_assert(std::same_as<stdr::sentinel_t<std::forward_list<int> >,
+                           std::forward_list<int>::iterator>);
+static_assert(std::same_as<stdr::sentinel_t<std::forward_list<int> const>,
+                           std::forward_list<int>::const_iterator>);
+
+static_assert(std::same_as<stdr::sentinel_t<std::deque<int> >,
+                           std::deque<int>::iterator>);
+static_assert(std::same_as<stdr::sentinel_t<std::deque<int> const>,
+                           std::deque<int>::const_iterator>);
+
+static_assert(
+    std::same_as<stdr::sentinel_t<std::list<int> >, std::list<int>::iterator>);
+static_assert(std::same_as<stdr::sentinel_t<std::list<int> const>,
+                           std::list<int>::const_iterator>);
+
+static_assert(std::same_as<stdr::sentinel_t<std::vector<int> >,
+                           std::vector<int>::iterator>);
+static_assert(std::same_as<stdr::sentinel_t<std::vector<int> const>,
+                           std::vector<int>::const_iterator>);
+
+static_assert(
+    std::same_as<stdr::sentinel_t<range<std::forward_list<int> > >, sentinel>);
+static_assert(
+    std::same_as<stdr::sentinel_t<range<std::forward_list<int> const> >,
+                 sentinel>);
+
+static_assert(
+    std::same_as<stdr::sentinel_t<range<std::deque<int> > >, sentinel>);
+static_assert(
+    std::same_as<stdr::sentinel_t<range<std::deque<int> const> >, sentinel>);
+
+static_assert(
+    std::same_as<stdr::sentinel_t<range<std::list<int> > >, sentinel>);
+static_assert(
+    std::same_as<stdr::sentinel_t<range<std::list<int> const> >, sentinel>);
+
+static_assert(
+    std::same_as<stdr::sentinel_t<range<std::vector<int> > >, sentinel>);
+static_assert(
+    std::same_as<stdr::sentinel_t<range<std::vector<int> const> >, sentinel>);

libcxx/test/support/test_range.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 LIBCXX_TEST_SUPPORT_TEST_RANGE_H
+#define LIBCXX_TEST_SUPPORT_TEST_RANGE_H
+
+#include <ranges>
+
+#ifdef _LIBCPP_HAS_NO_RANGES
+#error "test/suppoort/test_range.h" can only be included in builds supporting ranges
+#endif
+
+struct sentinel {
+  bool operator==(std::input_or_output_iterator auto) const;
+};
+
+template <class R>
+struct range {
+  std::ranges::iterator_t<R> begin();
+  std::ranges::iterator_t<R const> begin() const;
+  sentinel end();
+  sentinel end() const;
+};
+
+#endif // LIBCXX_TEST_SUPPORT_TEST_RANGE_H