[libcxx][ranges] Add concepts in range.utility.helpers.

[zoecarver]

Summary

There are no changes to public APIs.

[• Quuxplusone]

LGTM % comments.

libcxx/include/__iterator/concepts.h

172–173

Nit: Please use _Ip not _Iter, for consistency.

libcxx/include/__iterator/iterator_traits.h

257–258

Before this change: C++20 uses the name has-arrow for something complicated; libc++ uses __has_arrow for a subtly different thing. This is obviously awful and I'm glad you're changing it.
After this change: C++20 uses the name has-arrow; libc++ uses __has_arrow for the same thing; libc++ also uses __has_arrow_op for a subtly different thing. This is arguably a step in the right direction, but still awful, because now it subtly matters whether you say __has_arrow or __has_arrow_op.

I think the right thing to do here is actually eliminate __has_arrow_op altogether. We use it in only one place. It's no hardship to inline it on line 264:

template<class _Ip>
  requires (requires(_Ip& __i) { __i.operator->(); }) && (!__has_member_pointer<_Ip>)

As a drive-by, you might also rename __iterator_traits_member_pointer_or_arrow_or_void to simply __iterator_traits_member_pointer, for consistency with __iterator_traits_member_reference.

libcxx/test/libcxx/ranges/range.utility.helpers/has_arrow.compile.pass.cpp

78

This surprises me, but I suppose it's because Incomplete* is not an input iterator, because ++it is ill-formed, because Incomplete is incomplete?

libcxx/test/libcxx/ranges/range.utility.helpers/not_same.compile.pass.cpp

16–22

As I think @tcanens remarked a few days ago: WG21 has an exposition-only concept not-same-as that is not the same thing as not same_as? That's just awful.
Due to its awfulness, I would suggest either giving this a scarier name, or dropping it altogether if humanly possible. (And/or filing a LWG issue, of course.)

If you keep this test, you should add

static_assert(!std::__not_same_as<int, int&>);
static_assert(!std::__not_same_as<int&, const int&>);
static_assert(!std::__not_same_as<int(&)(), int()>);
static_assert(std::__not_same_as<int(&)(), int(*)()>);

i.e., test some things where the ref-qualification is on the right-hand operand; and test some things where remove_cvref_t is visibly different from decay_t.

libcxx/test/libcxx/ranges/range.utility.helpers/simple_view.compile.pass.cpp

23

I suggest calling this WrongConstView or something, since if you ever saw this in real life it would be a bug.
Initially I thought SimpleView should be called Span (since it works like std::span), but that was when I was expecting the rest of the examples to be different positive examples (e.g. StringView) instead of negative examples.

30–33

I suggest you add a positive example OnlyConstView, with only friend const int* begin(const OnlyConstView&).
And then you can eliminate lines 40 and 42 from DifferentSentinel.

[zoecarver]

libcxx/test/libcxx/ranges/range.utility.helpers/not_same.compile.pass.cpp

16–22

I agree the name/concept is terrible. But it is widely used throughout the ranges library, so I think we're stuck with it for a little while.

Additionally, I think it's imperative that we continue to name exposition-only-concepts in a mechanical way: __exposition_only_concepts. This way we can easily lookup concepts, verify correctness, and prevent duplication.

I'll add those tests.

[zoecarver]

libcxx/test/libcxx/ranges/range.utility.helpers/has_arrow.compile.pass.cpp

78

Yes.

libcxx/test/libcxx/ranges/range.utility.helpers/simple_view.compile.pass.cpp

30–33

This isn't a view. A view requires that T is movable (i.e., not const) and that we can do ranges::begin(declval<T&>()). Therefor, we need all four members.

[zoecarver]

Address review comments.

[cjdb]

LGTM

libcxx/test/libcxx/ranges/range.utility.helpers/simple_view.compile.pass.cpp

36–39

This type isn't necessary: test_iterators.h has a sentinel_wrapper vocabulary test type that we can use instead.

[• Quuxplusone]

libcxx/test/libcxx/ranges/range.utility.helpers/simple_view.compile.pass.cpp

30–33

@zoecarver: I believe you've misunderstood. I'm asking that you add this test case:

struct OnlyConstView : std::ranges::view_base {
  friend int* begin(const OnlyConstView&);
  friend int* end(const OnlyConstView&);
};
static_assert(std::ranges::__simple_view<OnlyConstView>);

And then modify DifferentSentinel as follows:

struct DifferentSentinel : std::ranges::view_base {
  friend int* begin(DifferentSentinel const&);
  friend sentinel_wrapper<int*> end(DifferentSentinel const&);
};
static_assert(!std::ranges::__simple_view<DifferentSentinel>);

[zoecarver]

libcxx/test/libcxx/ranges/range.utility.helpers/simple_view.compile.pass.cpp

30–33

No, I understood you. Maybe the following snippet will help me explain what I'm trying to say:

struct OnlyConstView : std::ranges::view_base {
  friend int* begin(const OnlyConstView&);
  friend int* end(const OnlyConstView&);
};
static_assert(!std::ranges::range<OnlyConstView>);
static_assert( std::ranges::range<const OnlyConstView>);
static_assert(!std::ranges::view<OnlyConstView>);
static_assert(!std::ranges::view<const OnlyConstView>);
static_assert(!std::ranges::__simple_view<OnlyConstView>);
static_assert(!std::ranges::__simple_view<const OnlyConstView>);

Here, you can see that only const OnlyConstView is a range. This is because a range requires us to be able to do ranges::begin(declval<T&>()) (so T must be const). You'll also notice that in no case is this a view, because a view requires T to be movable, so it cannot be const. And __simple_view requires T to be a view, so this ins't a __simple_view either.

[• Quuxplusone]

libcxx/test/libcxx/ranges/range.utility.helpers/simple_view.compile.pass.cpp

30–33

Ahhh. This is https://cplusplus.github.io/LWG/issue3480 — the poison pill for ranges::begin is "bad" in the sense that begin(auto&) // poison-pill is a better-matching candidate than our actual ADL begin(const OnlyConstView&).
So the solution adopted in LWG3480 is to pass views by value, not by const reference — and arguably that's a more "classic STL" way to do it, anyway.
I'd replace this with:

struct ValueView : std::ranges::view_base {
  friend int* begin(ValueView);
  friend int* end(ValueView);
};
static_assert( std::ranges::range<ValueView>);
static_assert( std::ranges::range<const ValueView>);
static_assert( std::ranges::view<ValueView>);
static_assert(!std::ranges::view<const ValueView>);  // because const types are not assignable-to
static_assert( std::ranges::__simple_view<ValueView>);

However, if you think this is too far from the original intent of the test, I guess I'm ambivalent at this point. It basically depends on whether we think "pass views by value" is a good general rule.

[zoecarver]

• Fix versioning.
• Use test::sentinel_wrapper.

[tcanens]

libcxx/test/libcxx/ranges/range.utility.helpers/not_same.compile.pass.cpp

16–22

not-same-as has been editorially renamed to different-from: https://github.com/cplusplus/draft/commit/caf7428fd6c807f30538042cf9bf1b27b8772b01

[zoecarver]

I'm going to do the rename and land.

libcxx/test/libcxx/ranges/range.utility.helpers/not_same.compile.pass.cpp

16–22

Woohoo 🙏

Thanks @tcanens (and others).

libcxx/include/__iterator/concepts.h

concept contiguous_iterator =
   derived_from<_ITER_CONCEPT<_Ip>, contiguous_iterator_tag> &&
   is_lvalue_reference_v<iter_reference_t<_Ip>> &&
   same_as<iter_value_t<_Ip>, remove_cvref_t<iter_reference_t<_Ip>>> &&
   (is_pointer_v<_Ip> || requires { sizeof(__pointer_traits_element_type<_Ip>); }) &&
   requires(const _Ip& __i) {
     { _VSTD::to_address(__i) } -> same_as<add_pointer_t<iter_reference_t<_Ip>>>;
   };
 
+
+template<class _Ip>
+concept __has_arrow = input_iterator<_Ip> && (is_pointer_v<_Ip> || requires(_Ip __i) { __i.operator->(); });
+
 // clang-format on
 
 #endif // !defined(_LIBCPP_HAS_NO_RANGES)
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___ITERATOR_CONCEPTS_H

libcxx/include/__iterator/iterator_traits.h

 
 // [iterator.traits]/3.2.1
 // If the qualified-id `I::pointer` is valid and denotes a type, `pointer` names that type.
 template<__has_member_pointer _Ip>
 struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> { using type = typename _Ip::pointer; };
 
 // Otherwise, if `decltype(declval<I&>().operator->())` is well-formed, then `pointer` names that
 // type.
 template<class _Ip>
-concept __has_arrow =
-  requires(_Ip& __i) {
-    __i.operator->();
-  };
-
-template<class _Ip>
-  requires __has_arrow<_Ip> && (!__has_member_pointer<_Ip>)
+  requires requires(_Ip& __i) { __i.operator->(); } && (!__has_member_pointer<_Ip>)
 struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> {
   using type = decltype(declval<_Ip&>().operator->());
 };
 
 // Otherwise, `reference` names `iter-reference-t<I>`.
 template<class _Ip>
 struct __iterator_traits_member_reference { using type = iter_reference_t<_Ip>; };
 

libcxx/include/__ranges/view.h

 
 template <class _Tp>
 concept view =
   range<_Tp> &&
   movable<_Tp> &&
   default_initializable<_Tp> &&
   enable_view<_Tp>;
 
+template<class _Range>
+concept __simple_view =
+  view<_Range> && range<const _Range> &&
+  same_as<iterator_t<_Range>, iterator_t<const _Range>> &&
+  same_as<sentinel_t<_Range>, iterator_t<const _Range>>;
 } // end namespace ranges
 
 #endif // !_LIBCPP_HAS_NO_RANGES
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___RANGES_VIEW_H

libcxx/include/concepts

 // [concept.equiv]
 template<class _Rp, class _Tp, class _Up>
 concept equivalence_relation = relation<_Rp, _Tp, _Up>;
 
 // [concept.strictweakorder]
 template<class _Rp, class _Tp, class _Up>
 concept strict_weak_order = relation<_Rp, _Tp, _Up>;
 
+template<class _Tp, class _Up>
+concept __not_same_as = !same_as<remove_cvref_t<_Tp>, remove_cvref_t<_Up>>;
+
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_CONCEPTS)
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP_CONCEPTS

libcxx/test/libcxx/ranges/range.utility.helpers/has_arrow.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
+//
+//===----------------------------------------------------------------------===//
+
+// <ranges>
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+#include <ranges>
+
+#include "test_macros.h"
+
+struct simple_iter {
+    typedef std::input_iterator_tag         iterator_category;
+    typedef int                             value_type;
+    typedef std::ptrdiff_t                  difference_type;
+    typedef int*                            pointer;
+    typedef int&                            reference;
+
+    reference operator*() const;
+    pointer operator->() const;
+    friend bool operator==(const simple_iter&, const simple_iter&);
+    friend bool operator< (const simple_iter&, const simple_iter&);
+    friend bool operator<=(const simple_iter&, const simple_iter&);
+    friend bool operator> (const simple_iter&, const simple_iter&);
+    friend bool operator>=(const simple_iter&, const simple_iter&);
+
+    simple_iter& operator++();
+    simple_iter operator++(int);
+};
+
+struct no_star {
+    typedef std::input_iterator_tag         iterator_category;
+    typedef int                             value_type;
+    typedef std::ptrdiff_t                  difference_type;
+    typedef int*                            pointer;
+    typedef int&                            reference;
+
+ /* reference operator*() const; */
+    pointer operator->() const;
+    friend bool operator==(const simple_iter&, const simple_iter&);
+    friend bool operator< (const simple_iter&, const simple_iter&);
+    friend bool operator<=(const simple_iter&, const simple_iter&);
+    friend bool operator> (const simple_iter&, const simple_iter&);
+    friend bool operator>=(const simple_iter&, const simple_iter&);
+
+    simple_iter& operator++();
+    simple_iter operator++(int);
+};
+
+struct no_arrow {
+    typedef std::input_iterator_tag         iterator_category;
+    typedef int                             value_type;
+    typedef std::ptrdiff_t                  difference_type;
+    typedef int*                            pointer;
+    typedef int&                            reference;
+
+    reference operator*() const;
+ /* pointer operator->() const; */
+    friend bool operator==(const simple_iter&, const simple_iter&);
+    friend bool operator< (const simple_iter&, const simple_iter&);
+    friend bool operator<=(const simple_iter&, const simple_iter&);
+    friend bool operator> (const simple_iter&, const simple_iter&);
+    friend bool operator>=(const simple_iter&, const simple_iter&);
+
+    simple_iter& operator++();
+    simple_iter operator++(int);
+};
+
+struct E {};
+struct Incomplete;
+
+static_assert(std::__has_arrow<int*>);
+static_assert(std::__has_arrow<E*>);
+static_assert(!std::__has_arrow<Incomplete*>); // Because it's not an input_iterator.
+static_assert(std::__has_arrow<simple_iter>);
+static_assert(!std::__has_arrow<no_star>);
+static_assert(!std::__has_arrow<no_arrow>);

libcxx/test/libcxx/ranges/range.utility.helpers/not_same.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
+//
+//===----------------------------------------------------------------------===//
+
+// <ranges>
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+#include <ranges>
+
+#include "test_macros.h"
+
+static_assert(std::__not_same_as<int, char>);
+static_assert(std::__not_same_as<const int, char>);
+static_assert(!std::__not_same_as<const int, int>);
+static_assert(!std::__not_same_as<const volatile int, int>);
+static_assert(!std::__not_same_as<const int&, int>);
+static_assert(!std::__not_same_as<int&, int>);
+static_assert(!std::__not_same_as<int&&, int>);
+static_assert(!std::__not_same_as<int, int&>);
+static_assert(!std::__not_same_as<int&, const int&>);
+static_assert(!std::__not_same_as<int(&)(), int()>);
+static_assert(std::__not_same_as<int(&)(), int(*)()>);

libcxx/test/libcxx/ranges/range.utility.helpers/simple_view.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
+//
+//===----------------------------------------------------------------------===//
+
+// <ranges>
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+#include <ranges>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+struct SimpleView : std::ranges::view_base {
+  friend int* begin(SimpleView&);
+  friend int* begin(SimpleView const&);
+  friend int* end(SimpleView&);
+  friend int* end(SimpleView const&);
+};
+
+struct WrongConstView : std::ranges::view_base {
+  friend       int* begin(WrongConstView&);
+  friend const int* begin(WrongConstView const&);
+  friend       int* end(WrongConstView&);
+  friend const int* end(WrongConstView const&);
+};
+
+struct NoConstView : std::ranges::view_base {
+  friend int* begin(NoConstView&);
+  friend int* end(NoConstView&);
+};
+
+struct DifferentSentinel : std::ranges::view_base {
+  friend int* begin(DifferentSentinel&);
+  friend int* begin(DifferentSentinel const&);
+  friend sentinel_wrapper<int*> end(DifferentSentinel&);
+  friend sentinel_wrapper<int*> end(DifferentSentinel const&);
+};
+
+static_assert( std::ranges::__simple_view<SimpleView>);
+static_assert(!std::ranges::__simple_view<WrongConstView>);
+static_assert(!std::ranges::__simple_view<NoConstView>);
+static_assert(!std::ranges::__simple_view<DifferentSentinel>);