[libc++] [ranges] Fix bugs in ranges::empty().

[• Quuxplusone]

Summary

It was missing the cast to bool in bool(__t.empty()).
It was wrongly using std::forward in some places.

[• Quuxplusone]

libcxx/include/__ranges/empty.h

60–67

Note the sneaky requires-clause hiding in among the "write it three times" business.
I'd be willing to pull this out into a helper concept, e.g.

template<class _Tp>
concept __forward_iterable =
  forward_iterator<decltype(ranges::begin(declval<_Tp&>()))>;

template <__forward_iterable _Tp>
_LIBCPP_HIDE_FROM_ABI
static constexpr auto __go(_Tp&& __t, __priority_tag<0>)
  noexcept(noexcept(bool(ranges::begin(__t) == ranges::end(__t))))
  -> decltype(      bool(ranges::begin(__t) == ranges::end(__t)))
  { return          bool(ranges::begin(__t) == ranges::end(__t)); }

but I'm ambivalent on whether that's better.
I'm also unclear on how to observe the difference between this constraint and a simple forward_range<_Tp&>. @tcanens perhaps?

[ldionne]

I don't especially like the fact that we're moving away from requires clauses and back to straight SFINAE. Can you check what effect this has on diagnostics?

[• Quuxplusone]

libcxx/include/__ranges/empty.h

76

@ldionne wrote:

I don't especially like the fact that we're moving away from requires clauses and back to straight SFINAE. Can you check what effect this has on diagnostics?

Old: 32 lines; new: 8 lines. I would call the new version "frustratingly opaque" but the old version "annoyingly verbose."
https://godbolt.org/z/GseTh84jx
I can't think of any way to improve this. I thought of constraining operator() on requires range<decay_t<_Tp>>, but (1) ranges::empty(e) doesn't require e to satisfy range (if it provides .empty()), and (2) that doesn't help because SFINAE kicks in prior to constraint checking, and (3) the constraint doesn't help the user anyway because the failure case 99% of the time will be that e is a range but can't be checked for emptiness for some other obscure reason.

[ldionne]

libcxx/include/__ranges/empty.h

76

Honestly, the output after is pretty terrible. It doesn't show anything at all, so it's basically impossible to know what's going wrong. I don't think we want to use this new technique in our ranges implementation. I would rather we revert to the more verbose and arguably not so great technique we had before, where we have to manually exclude other overloads.

[• Quuxplusone]

I added a late-breaking value-category-related test case to the ranges::empty test; this fixes that too.

[ldionne]

Thanks for fixing those bugs. We talked about it offline and I wasn't able to come up with a significantly better solution than the explicit mutual exclusion of concepts we had before, however I'm still not really comfortable moving to this 100% SFINAE based approach due to diagnostics concerns. If we do it here, one could argue that we should do it everywhere, cause it *is* simpler from a writing-the-code perspective. But I don't want to encourage that general direction.

So IMO we should fix the bugs you're fixing without changing the approach we had, i.e. the somewhat clunky helper concepts we used to define (and which is consistent with the approach taken in the rest of ranges).

[• Quuxplusone]

Review comments.
Update with my proposed new-and-improved way of getting reasonable diagnostics when the SFINAE fails.

Guess what? We had a test/libcxx/ test that was supposed to test these diagnostics, but it was testing ranges::begin instead of ranges::empty.

New-and-improved CPO design coming to all the other ranges.access CPOs, in a PR depending on this one that I'll upload shortly.

[• Quuxplusone]

"Patch application failed" in buildkite. Rebase and try again.

[• Quuxplusone]

Harmonize with D115607; #if 0 out some tests that will work only after D115607 lands (because they depend on ranges::begin not to hard-error in silly ways).

[• Quuxplusone]

Does removing the old parent revision make buildkite happier about applying the patch?

[ldionne]

Can you please:

1. Fix the bug(s) you are fixing without using a new CPO design
2. Open a different review that proposes a new CPO design so we can discuss it separately

[• Quuxplusone]

Remove an unused parameter name. NFC.

[• Quuxplusone]

Rebase. NFC.

[• Quuxplusone]

To be rebased after D115686 and D115838.

[• Quuxplusone]

Scale back to just the bugfixes I'm aware of; isolate the refactoring into a separate (and still to-be-written) PR.

[• Quuxplusone]

Rebase on D116198. Expect CI to remain green.

[Mordante]

LGTM

[philnik]

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

157–164 ↗

(On Diff #395960)

Why the == false and == true? Seems weird.

[• Quuxplusone]

Accepting-as-libc++ to land this. (@ldionne is out; but his "requested changes" applied to the previous version of this PR, which did a lot of rewriting in addition to the bugfixes. I believe scaling it back to just the bugfixes addresses those comments sufficiently.)

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

157–164 ↗

(On Diff #395960)

As mentioned in the other review, these tests don't really verify return types at all, so here I infer that the writer was trying to sort of hint at "...and empty(e) should return bool(true), not just anything that happens to be truthy." Of course the compiler doesn't care what you're hinting at, so this isn't very useful as a test. ;) I think I'll remove these == trues and change == false to !, but in a separate NFC patch.

[ldionne]

LGTM post-commit. Thanks.

libcxx/include/__ranges/empty.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_EMPTY_H
 #define _LIBCPP___RANGES_EMPTY_H
 
 #include <__config>
 #include <__iterator/concepts.h>
 #include <__ranges/access.h>
 #include <__ranges/size.h>
 #include <__utility/forward.h>
+#include <__utility/priority_tag.h>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 #if !defined(_LIBCPP_HAS_NO_RANGES)
 
-// clang-format off
-namespace ranges {
 // [range.prim.empty]
+
+namespace ranges {
 namespace __empty {
   template <class _Tp>
-  concept __member_empty = requires(_Tp&& __t) {
-    bool(_VSTD::forward<_Tp>(__t).empty());
+  concept __basic_requirements =
+    requires (_Tp __t) { bool(__t.empty()); } ||
+    requires (_Tp __t) { ranges::size(__t) == 0; } ||
+    requires (_Tp __t) {
+      { ranges::begin(__t) } -> forward_iterator;
+      bool(ranges::begin(__t) == ranges::end(__t));
     };
 
-  template<class _Tp>
-  concept __can_invoke_size =
-    !__member_empty<_Tp> &&
-    requires(_Tp&& __t) { ranges::size(_VSTD::forward<_Tp>(__t)); };
+  struct __fn {
+    template <class _Tp> requires is_unbounded_array_v<remove_reference_t<_Tp>>
+    _LIBCPP_HIDE_FROM_ABI
+    static constexpr void __go(_Tp&& __t, __priority_tag<3>) = delete;
 
     template <class _Tp>
-  concept __can_compare_begin_end =
-    !__member_empty<_Tp> &&
-    !__can_invoke_size<_Tp> &&
-    requires(_Tp&& __t) {
-      bool(ranges::begin(__t) == ranges::end(__t));
-      { ranges::begin(__t) } -> forward_iterator;
-    };
+    _LIBCPP_HIDE_FROM_ABI
+    static constexpr auto __go(_Tp&& __t, __priority_tag<2>)
+      noexcept(noexcept(bool(__t.empty())))
+      -> decltype(      bool(__t.empty()))
+      { return          bool(__t.empty()); }
 
-  struct __fn {
-    template <__member_empty _Tp>
-    [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr bool operator()(_Tp&& __t) const
-        noexcept(noexcept(bool(__t.empty()))) {
-      return __t.empty();
-    }
+    template <class _Tp>
+    _LIBCPP_HIDE_FROM_ABI
+    static constexpr auto __go(_Tp&& __t, __priority_tag<1>)
+      noexcept(noexcept(ranges::size(__t) == 0))
+      -> decltype(      ranges::size(__t) == 0)
+      { return          ranges::size(__t) == 0; }
 
-    template <__can_invoke_size _Tp>
-    [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr bool operator()(_Tp&& __t) const
-        noexcept(noexcept(ranges::size(_VSTD::forward<_Tp>(__t)))) {
-      return ranges::size(_VSTD::forward<_Tp>(__t)) == 0;
-    }
+    template <class _Tp>
+    _LIBCPP_HIDE_FROM_ABI
+    static constexpr auto __go(_Tp&& __t, __priority_tag<0>)
+      noexcept(noexcept(bool(ranges::begin(__t) == ranges::end(__t))))
+      -> decltype(      bool(ranges::begin(__t) == ranges::end(__t)))
+      requires forward_iterator<decltype(ranges::begin(__t))>
+      { return          bool(ranges::begin(__t) == ranges::end(__t)); }
 
-    template<__can_compare_begin_end _Tp>
-    [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr bool operator()(_Tp&& __t) const
-        noexcept(noexcept(bool(ranges::begin(__t) == ranges::end(__t)))) {
-      return ranges::begin(__t) == ranges::end(__t);
-    }
+    template <class _Tp>
+    [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
+    constexpr decltype(auto) operator()(_Tp&& __t) const
+      noexcept(noexcept(__go(_VSTD::forward<_Tp>(__t), __priority_tag<3>())))
+      requires __basic_requirements<_Tp&&> &&
+      (requires {       __go(_VSTD::forward<_Tp>(__t), __priority_tag<3>()); })
+      { return          __go(_VSTD::forward<_Tp>(__t), __priority_tag<3>()); }
   };
 }
 
 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
 
 #endif // _LIBCPP___RANGES_EMPTY_H

libcxx/test/libcxx/ranges/range.access/empty.verify.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: libcpp-has-no-incomplete-ranges
+
+// std::ranges::empty
+//   Substitution failure should give reasonably nice diagnostics.
+
+#include <ranges>
+
+void f() {
+  // expected-error@*:* {{no matching function for call}}
+  // expected-note@*:* {{'bool(__t.empty())' would be invalid}}
+  // expected-note@*:* {{'ranges::size(__t) == 0' would be invalid}}
+  // expected-note@*:* {{'ranges::begin(__t)' would be invalid}}
+  std::ranges::empty(42);
+}

libcxx/test/libcxx/ranges/range.access/range.prim/empty.incomplete.verify.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: libcpp-has-no-incomplete-ranges
-
-// Test the libc++ specific behavior that we provide a better diagnostic when calling
-// std::ranges::empty on an array of incomplete type.
-
-#include <ranges>
-
-struct Incomplete;
-
-void f(Incomplete arr[]) {
-  // expected-error@*:* {{is SFINAE-unfriendly on arrays of an incomplete type.}}
-  // expected-error@*:* {{call to deleted function call operator in type}}
-  // expected-error@*:* {{attempt to use a deleted function}}
-  std::ranges::begin(arr);
-}
-
-void f(Incomplete(&arr)[]) {
-  // expected-error@*:* {{is SFINAE-unfriendly on arrays of an incomplete type.}}
-  std::ranges::begin(arr);
-}
-
-void f(Incomplete(&&arr)[]) {
-  // expected-error@*:* {{is SFINAE-unfriendly on arrays of an incomplete type.}}
-  std::ranges::begin(arr);
-}
-
-void f2(Incomplete arr[2]) {
-  // expected-error@*:* {{call to deleted function call operator in type}}
-  // expected-error@*:* {{attempt to use a deleted function}}
-  std::ranges::begin(arr);
-}
-
-void f(Incomplete(&arr)[2]) {
-  std::ranges::begin(arr);
-}
-
-void f(Incomplete(&&arr)[2]) {
-  std::ranges::begin(arr);
-}
-
-void f(Incomplete(&arr)[2][2]) {
-  std::ranges::begin(arr);
-}

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

 // UNSUPPORTED: libcpp-no-concepts
 // UNSUPPORTED: libcpp-has-no-incomplete-ranges
 
 // std::ranges::empty
 
 #include <ranges>
 
 #include <cassert>
+#include <utility>
 #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(&)[]>);
 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();
+struct Incomplete;
+static_assert(!std::is_invocable_v<RangeEmptyT, Incomplete[]>);
+static_assert(!std::is_invocable_v<RangeEmptyT, Incomplete(&)[]>);
+static_assert(!std::is_invocable_v<RangeEmptyT, Incomplete(&&)[]>);
+
+extern Incomplete array_of_incomplete[42];
+static_assert(!std::ranges::empty(array_of_incomplete));
+static_assert(!std::ranges::empty(std::move(array_of_incomplete)));
+static_assert(!std::ranges::empty(std::as_const(array_of_incomplete)));
+static_assert(!std::ranges::empty(static_cast<const Incomplete(&&)[42]>(array_of_incomplete)));
+
+struct InputRangeWithoutSize {
+    cpp17_input_iterator<int*> begin() const;
+    cpp17_input_iterator<int*> end() const;
+};
+static_assert(!std::is_invocable_v<RangeEmptyT, const InputRangeWithoutSize&>);
+
+struct NonConstEmpty {
   bool empty();
 };
-static_assert(!std::is_invocable_v<RangeSizeT, const NonConstSizeAndEmpty&>);
-static_assert(!std::is_invocable_v<RangeEmptyT, const NonConstSizeAndEmpty&>);
+static_assert(!std::is_invocable_v<RangeEmptyT, const NonConstEmpty&>);
 
 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 /*TODO: explicit*/ operator bool() noexcept(false) { return true; }
+  constexpr explicit operator bool() noexcept(false) { return true; }
 };
 struct BoolConvertibleReturnType {
   constexpr BoolConvertible empty() noexcept { return {}; }
 };
 static_assert(!noexcept(std::ranges::empty(BoolConvertibleReturnType())));
 
 struct InputIterators {
   cpp17_input_iterator<int*> begin() const;
constexpr bool testBeginEqualsEnd() {
 
   DisabledSizeRangeWithBeginEnd d;
   assert(std::ranges::empty(d) == true);
 
   BeginEndAndEmpty e;
   assert(std::ranges::empty(e) == false); // e.empty()
   assert(std::ranges::empty(std::as_const(e)) == true); // e.begin() == e.end()
 
-#if 0 // TODO FIXME
   assert(std::ranges::empty(EvilBeginEnd()));
-#endif
 
   return true;
 }
 
 int main(int, char**) {
   testEmptyMember();
   static_assert(testEmptyMember());
 
   testUsingRangesSize();
   static_assert(testUsingRangesSize());
 
   testBeginEqualsEnd();
   static_assert(testBeginEqualsEnd());
 
   return 0;
 }