[libcxx][ranges] Add ranges::empty CPO.

[cjdb]

Summary

Depends on D101079. Refs D101189.

[zoecarver]

libcxx/include/__ranges/empty.h

3

Change this here and in other patches.

[• Quuxplusone]

libcxx/include/CMakeLists.txt

43–44

At some point we should alphabetize end vs ena.

libcxx/include/__ranges/empty.h

49

Doesn't clearly implement a case corresponding to the bullet point ["If T is an array of unknown bound, ranges​::​empty(E) is ill-formed."](https://eel.is/c++draft/range.access#range.prim.empty-2.1)
But I think that bullet point is actually redundant; arrays of unknown bound also don't have ranges::end(E) or ranges::size(E) or t.begin().
Do we understand the intent (in all these CPOs) when T is a reference to an array of unknown bound?

51–54

As usual, replace X with bool(X) in the noexcept-spec and also in the return. Also, __t should be an lvalue according to "let t be an lvalue that denotes the reified object for E." So:

[[nodiscard]] constexpr bool operator()(_Tp&& __t) const
    noexcept(noexcept(bool(__t.empty()))) {
  return __t.empty();
}

Optionally, figure out a way to detect the difference here and write a regression test for it. (I say "optionally" because IMHO it doesn't really matter.)

As above so on lines 34 and 57/58: t is an lvalue, lose the forwarding.

64–65

libcxx/include/ranges

62–64

At some point, alphabetize end and ena.

libcxx/test/std/ranges/range.access/range.prim/empty.pass.cpp

25–30

(A) If you're intending this to be found (or rather not found) by ADL, please make it a hidden friend.
(B) Please make the functions look as much like "realistic/simple code" as you can. In this case, that means marking empty() and size() as const-qualified member functions throughout. E.g.:

struct HasMemberAndFunction {
    constexpr bool empty() const { return true; ]
    friend bool empty(const HasMemberAndFunction&) { return false; }
};

And normally I'd say "no constexpr"; but here you need them to be constexpr because you're testing the constexpr-callableness of ranges::empty.

Btw, if you ever run into a situation where you need to test for sure that some specific function was entered, you can use the old "was_called = true;" trick. You just need to make bool& was_called a data member, and initialize it in the constructor to refer to a local variable of the function doing the testing. (Global variables can't be modified in constexpr contexts, but locals can.)

Finally, please add a test that intentionally has a non-const size and empty:

struct S { int size(); bool empty(); };
static_assert(!requires (const S& s) { std::ranges::size(s); });
static_assert(!requires (const S& s) { std::ranges::empty(s); });

41

From context, I suspect you meant to mark this function noexcept.

90

If this was cut-and-pasted from the ranges::size tests... should this now say RangeEmptyT?

[zoecarver]

Thanks for the review, Arthur. Will update shortly.

libcxx/test/std/ranges/range.access/range.prim/empty.pass.cpp

90

This (and below) is intentional. I wanted to make sure that this wasn't choosing the __can_invoke_size overload.

[zoecarver]

libcxx/include/__ranges/empty.h

51–54

Good catch, thanks. I'm not going to do bool(X) for the overload on L57 because we know that it's a primitive type.

libcxx/test/std/ranges/range.access/range.prim/empty.pass.cpp

25–30

Finally, please add a test that intentionally has a non-const size and empty:
struct S { int size(); bool empty(); };
static_assert(!requires (const S& s) { std::ranges::size(s); });
static_assert(!requires (const S& s) { std::ranges::empty(s); });

That test will fail to compile, but I get what you mean. Added.

[zoecarver]

• Apply Arthur's comments.
• Rebase.

[zoecarver]

As usual, replace X with bool(X) in the noexcept-spec and also in the return. Also, __t should be an lvalue according to "let t be an lvalue that denotes the reified object for E." So:

This comment actually goes for all recent CPOs (begin, end, size, etc.).

CC @cjdb.

[cjdb]

libcxx/include/__ranges/empty.h

51–54

and also in the return

This shouldn't be necessary thanks to boolean-testable. @tcanens I don't think the wording permit us to use it right now; did we miss one in the cleanup?

[tcanens]

libcxx/include/__ranges/empty.h

39

I'd expect this one and the next to require !__member_empty?

49

Doesn't clearly implement a case corresponding to the bullet point ["If T is an array of unknown bound, ranges​::​empty(E) is ill-formed."](https://eel.is/c++draft/range.access#range.prim.empty-2.1)
But I think that bullet point is actually redundant; arrays of unknown bound also don't have ranges::end(E) or ranges::size(E) or t.begin().

The difference is that for array of unknown bound of incomplete type, ranges::begin / ranges::end are IFNDR, but ranges::empty is ill-formed DR.

Do we understand the intent (in all these CPOs) when T is a reference to an array of unknown bound?

T is the type of some expression. Expressions don't have reference type.

51–54

and also in the return

This shouldn't be necessary thanks to boolean-testable. @tcanens I don't think the wording permit us to use it right now; did we miss one in the cleanup?

This one doesn't even require the result to be implicitly convertible to bool, which is probably why I didn't touch it with boolean-testable. I don't know what the original intended design is - @CaseyCarter?

[ldionne]

libcxx/include/__ranges/empty.h

39

I think the expression we check should be ranges::size(_VSTD::forward<_Tp>(__t)) == 0 instead, according to the spec.

I'm actually not sure why the spec mandates checking == 0 since ranges::size(E) is always supposed to be integer-like, but oh well.

71

Do we need const here? Shouldn't constexpr imply const for objects? I thought I didn't see it on the other CPOs.

[zoecarver]

libcxx/include/__ranges/empty.h

39

@tcanens you're right. @ldionne I don't think we need the == 0 because the return type is integral. But you might be right about forwarding the expression. I know __t is required to be an lvalue, so that's why I didn't have it originally. I guess it comes down to whether or not a copy is going to happen when we call size, and I don't think we can guarantee that won't happen, so I think maybe we should forward it.

[zoecarver]

• Apply review comments: a. Remove const. b. Forward to ranges::size. c. Check no member.

[zoecarver]

Add:

// XFAIL: msvc && clang

[ldionne]

LGTM with nitpick.

libcxx/include/__ranges/empty.h

3

Woops, still not done. Actually, I've been removing the file names from the start of the files. I don't think they add anything, they just get out of sync like this. I'd just remove it.

[cjdb]

LGTM with semiregular test.

[cjdb]

Ping. Can this be merged or is there a blocker besides CI?

[• Quuxplusone]

libcxx/include/__ranges/empty.h

49

@tcanens: "Expressions don't have reference type" — What if T is the type of the expression foo(), where foo is declared as int (&foo())[]? Wouldn't foo() have reference type then? Or would you simply say it has type "array of unknown bound" and is an lvalue?
Anyway, libstdc++ and MSVC both agree that in that case ranges::empty should SFINAE away, which is the expected/simple/obvious answer anyway.

libcxx/test/std/ranges/range.access/range.prim/empty.pass.cpp

13

Remove XFAIL here (and throughout); the msvc issue is fixed.

26

Add:

static_assert(!std::is_invocable_v<RangeEmptyT, int(&)[]>);
static_assert(!std::is_invocable_v<RangeEmptyT, int(&&)[]>);

72

constexpr size_t size() const { return size_; }

97

I'm still confused about why sentinel needs to be comparable to every-iterator-type-ever.
I would rather see it scoped down to whatever specific type you're planning to compare it to (via nested member types, as shown in another of these reviews).

112–113

You have some pass-by-const-value here. Remove const. Also, remove the definition and constexprness from any of these functions that you don't expect to be called.

129

constexpr size_t size() const { return 1; }

[tcanens]

libcxx/include/__ranges/empty.h

49

Or would you simply say it has type "array of unknown bound" and is an lvalue?

This. See [expr.type]/1.

libcxx/test/std/ranges/range.access/range.prim/empty.pass.cpp

26

I'd suggest a test case for "array of unknown bound of incomplete type" (ideally for all the ranges CPOs). We spent a decent chunk of time in LWG pinning down what should happen for those.

[cjdb]

libcxx/test/std/ranges/range.access/range.prim/empty.pass.cpp

26

Like this? https://github.com/llvm/llvm-project/blob/main/libcxx/test/std/ranges/range.access/range.access.begin/incomplete.compile.verify.cpp

[tcanens]

libcxx/test/std/ranges/range.access/range.prim/empty.pass.cpp

26

Yep. For empty and size it's simpler since those are supposed to be ill-formed DR.

[cjdb]

Commandeering with @zoecarver's permission.

libcxx/test/std/ranges/range.access/range.prim/empty.pass.cpp

97

The effort-to-reward ratio for this doesn't really pay off. What do we gain from doing this? What do we lose by keeping it as-is?

[zoecarver]

• Apply review feedback and rebase.

[zoecarver]

• Fix comment in empty.incomplete.verify.cpp

[zoecarver]

• Fix bots: change expected-error regex.

libcxx/include/CMakeLists.txt

set(files
   __memory/unique_ptr.h
   __mutex_base
   __node_handle
   __nullptr
   __ranges/begin.h
   __ranges/cbegin.h
   __ranges/cend.h
   __ranges/concepts.h
-  __ranges/end.h
+  __ranges/empty.h
   __ranges/enable_borrowed_range.h
+  __ranges/end.h
   __ranges/size.h
   __split_buffer
   __sso_allocator
   __std_stream
   __string
   __threading_support
   __tree
   __tuple

libcxx/include/__ranges/empty.h

+// -*- C++ -*-
+//===------------------------ __ranges/end.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_EMPTY_H
+#define _LIBCPP___RANGES_EMPTY_H
+
+#include <__config>
+#include <__iterator/concepts.h>
+#include <__ranges/size.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)
+
+// clang-format off
+namespace ranges {
+// [range.prim.empty]
+namespace __empty {
+  template <class _Tp>
+  concept __member_empty = requires(_Tp&& __t) {
+    bool(_VSTD::forward<_Tp>(__t).empty());
+  };
+
+  template<class _Tp>
+  concept __can_invoke_size =
+    !__member_empty<_Tp> &&
+    requires(_Tp&& __t) { ranges::size(_VSTD::forward<_Tp>(__t)); };
+
+  template <class _Tp>
+  concept __can_compare_begin_end =
+    !__can_invoke_size<_Tp> &&
+    requires(_Tp&& __t) {
+      bool(ranges::begin(__t) == ranges::end(__t));
+      { ranges::begin(__t) } -> forward_iterator;
+    };
+
+  struct __fn {
+    template <__member_empty _Tp>
+    [[nodiscard]] constexpr bool operator()(_Tp&& __t) const
+        noexcept(noexcept(bool(__t.empty()))) {
+      return __t.empty();
+    }
+
+    template <__can_invoke_size _Tp>
+    [[nodiscard]] constexpr bool operator()(_Tp&& __t) const
+        noexcept(noexcept(ranges::size(_VSTD::forward<_Tp>(__t)))) {
+      return ranges::size(_VSTD::forward<_Tp>(__t)) == 0;
+    }
+
+    template<__can_compare_begin_end _Tp>
+    [[nodiscard]] constexpr bool operator()(_Tp&& __t) const
+        noexcept(noexcept(bool(ranges::begin(__t) == ranges::end(__t)))) {
+      return ranges::begin(__t) == ranges::end(__t);
+    }
+  };
+}
+
+inline namespace __cpo {
+  inline constexpr auto empty = __empty::__fn{};
+} // namespace __cpo
+} // namespace ranges
+// clang-format off
+
+#endif // !defined(_LIBCPP_HAS_NO_RANGES)
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___RANGES_EMPTY_H

libcxx/include/ranges

 
 */
 
 #include <__config>
 #include <__ranges/begin.h>
 #include <__ranges/cbegin.h>
 #include <__ranges/cend.h>
 #include <__ranges/concepts.h>
-#include <__ranges/end.h>
+#include <__ranges/empty.h>
 #include <__ranges/enable_borrowed_range.h>
+#include <__ranges/end.h>
 #include <__ranges/size.h>
 #include <compare>          // Required by the standard.
 #include <initializer_list> // Required by the standard.
 #include <iterator>         // Required by the standard.
 #include <type_traits>
 #include <version>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)

libcxx/test/std/ranges/range.access/range.prim/empty.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
+
+// std::ranges::empty
+
+#include <ranges>
+
+#include <cassert>
+#include "test_macros.h"
+#include "test_iterators.h"
+
+using RangeEmptyT = decltype(std::ranges::empty);
+using RangeSizeT = decltype(std::ranges::size);
+
+static_assert(!std::is_invocable_v<RangeEmptyT, int[]>);
+static_assert( std::is_invocable_v<RangeEmptyT, int[1]>);
+static_assert( std::is_invocable_v<RangeEmptyT, const int[1]>);
+static_assert( std::is_invocable_v<RangeEmptyT, int (&&)[1]>);
+static_assert( std::is_invocable_v<RangeEmptyT, int (&)[1]>);
+static_assert( std::is_invocable_v<RangeEmptyT, const int (&)[1]>);
+
+struct NonConstSizeAndEmpty {
+  int size();
+  bool empty();
+};
+static_assert(!std::is_invocable_v<RangeSizeT, const NonConstSizeAndEmpty&>);
+static_assert(!std::is_invocable_v<RangeEmptyT, const NonConstSizeAndEmpty&>);
+
+struct HasMemberAndFunction {
+  constexpr bool empty() const { return true; }
+  // We should never do ADL lookup for std::ranges::empty.
+  friend bool empty(const HasMemberAndFunction&) { return false; }
+};
+
+struct BadReturnType {
+  BadReturnType empty() { return {}; }
+};
+static_assert(!std::is_invocable_v<RangeEmptyT, BadReturnType>);
+
+struct BoolConvertible {
+  constexpr operator bool() noexcept(false) { return true; }
+};
+struct BoolConvertibleReturnType {
+  constexpr BoolConvertible empty() noexcept { return {}; }
+};
+
+static_assert(!noexcept(std::ranges::empty(BoolConvertibleReturnType())));
+
+constexpr bool testEmptyMember() {
+  HasMemberAndFunction a;
+  assert(std::ranges::empty(a) == true);
+
+  BoolConvertibleReturnType b;
+  assert(std::ranges::empty(b) == true);
+
+  return true;
+}
+
+struct SizeMember {
+  size_t size_;
+  constexpr size_t size() { return size_; }
+};
+
+struct SizeFunction {
+  size_t size_;
+  friend constexpr size_t size(SizeFunction sf) { return sf.size_; }
+};
+
+constexpr bool testUsingRangesSize() {
+  SizeMember a{1};
+  assert(std::ranges::empty(a) == false);
+  SizeMember b{0};
+  assert(std::ranges::empty(b) == true);
+
+  SizeFunction c{1};
+  assert(std::ranges::empty(c) == false);
+  SizeFunction d{0};
+  assert(std::ranges::empty(d) == true);
+
+  return true;
+}
+
+struct other_forward_iterator : forward_iterator<int*> { };
+
+struct sentinel {
+  constexpr bool operator==(std::input_or_output_iterator auto) const { return true; }
+};
+
+struct BeginEndNotSizedSentinel {
+  friend constexpr forward_iterator<int*> begin(BeginEndNotSizedSentinel) { return {}; }
+  friend constexpr sentinel end(BeginEndNotSizedSentinel) { return {}; }
+};
+static_assert(!std::is_invocable_v<RangeSizeT, BeginEndNotSizedSentinel&>);
+
+struct InvalidMinusBeginEnd {
+  friend constexpr random_access_iterator<int*> begin(InvalidMinusBeginEnd) { return {}; }
+  friend constexpr sentinel end(InvalidMinusBeginEnd) { return {}; }
+};
+
+// Int is integer-like, but it is not other_forward_iterator's difference_type.
+constexpr int operator-(const sentinel, const random_access_iterator<int*>) { return 2; }
+constexpr int operator-(const random_access_iterator<int*>, const sentinel) { return 2; }
+static_assert(!std::is_invocable_v<RangeSizeT, InvalidMinusBeginEnd&>);
+
+// This type will use ranges::size.
+struct IntPtrBeginAndEnd {
+  int buff[8];
+  constexpr int* begin() { return buff; }
+  constexpr int* end() { return buff + 8; }
+};
+static_assert(std::is_invocable_v<RangeSizeT, IntPtrBeginAndEnd&>);
+
+// size is disabled here, and it isn't sized_sentinel_for, so we have to compare begin
+// and end again.
+struct DisabledSizeRangeWithBeginEnd {
+  friend constexpr forward_iterator<int*> begin(DisabledSizeRangeWithBeginEnd) { return {}; }
+  friend constexpr sentinel end(DisabledSizeRangeWithBeginEnd) { return {}; }
+  constexpr size_t size() { return 1; }
+};
+
+template<>
+inline constexpr bool std::disable_sized_range<DisabledSizeRangeWithBeginEnd> = true;
+static_assert(!std::is_invocable_v<RangeSizeT, DisabledSizeRangeWithBeginEnd&>);
+
+constexpr bool testBeginEqualsEnd() {
+  BeginEndNotSizedSentinel a;
+  assert(std::ranges::empty(a) == true);
+
+  InvalidMinusBeginEnd b;
+  assert(std::ranges::empty(b) == true);
+
+  IntPtrBeginAndEnd c;
+  assert(std::ranges::empty(c) == false);
+
+  DisabledSizeRangeWithBeginEnd d;
+  assert(std::ranges::empty(d) == true);
+
+  return true;
+}
+
+int main(int, char**) {
+  testEmptyMember();
+  static_assert(testEmptyMember());
+
+  testUsingRangesSize();
+  static_assert(testUsingRangesSize());
+
+  testBeginEqualsEnd();
+  static_assert(testBeginEqualsEnd());
+
+  return 0;
+}