[libc++] [ranges] ADL-proof the [range.access] CPOs.

[• Quuxplusone]

Summary

For example, std::ranges::range<Holder<Incomplete>*> should be well-formed false, not a hard error at compile time.

[philnik]

libcxx/include/__ranges/access.h

43–46

enum E; E{}.begin() will never be a valid statement, right? So __class_or_enum should just be is_class_v<_Tp> || is_union_v<_Tp> or something similar.

[• Quuxplusone]

libcxx/include/__ranges/access.h

43–46

Right, but that would be longer; and breaking it down into two atomic constraints like that might lead to worse diagnostics (although I haven't tested that myself). Admittedly our diagnostics here are bad to begin with.
Since this is a pattern we seem to need a lot, I'd be amenable to creating a concept __class_or_union right next to concept __class_or_enum (in <__concepts/class_or_enum.h>). The only problem with that is the awkwardly asymmetric naming: in __class_or_enum the term "class" means "class-or-union type" already. Really what we mean (here and everywhere __class_or_enum is used) is something like concept __is_worth_triggering_adl_for. If it's a simple pointer or function type, we must not trigger ADL; but if it's a class or enum type, either we must trigger ADL (because the standard says so) or else it's harmless to trigger ADL (on an enum type).

[philnik]

libcxx/include/__ranges/access.h

43–46

I thought about a name myself but couldn't find a good one. __class seemed to be the obvious choice, but that sounds more like is_class_v and not is_class_v || is_union_v. On the other hand, if it says __class_or_enum I would think of is_class_v || is_enum_v and not is_class_v || is_enum_v || is_union_v. Maybe something like __class_type to make clear that it's not just is_class? IDK, maybe we should discuss this on discord?

[jloser]

LGTM! Regarding the class_or_enum discussion, note __unqualified_begin concept uses __class_or_enum, so we should change that (and others, where appropriate) if we want to say "class or union, but not enum".

[• Quuxplusone]

libcxx/include/__ranges/access.h

55

@jloser writes:

Regarding the class_or_enum discussion, note __unqualified_begin uses __class_or_enum, so we should change that (and others, where appropriate)

For __unqualified_begin, __class_or_enum is both sufficient and necessary: it's looking for begin(__t), which means it needs to do ADL even for enums (but, again, not for pointers).

I still don't understand why the well-formedness check of t.begin() triggers instantiation of Holder<Incomplete> when t is a pointer ( https://godbolt.org/z/Tfb3vTrvf ); I should ask around about that.

[ldionne]

Re @Quuxplusone

I still don't understand why the well-formedness check of t.begin() triggers instantiation of Holder<Incomplete> when t is a pointer ( https://godbolt.org/z/Tfb3vTrvf ); I should ask around about that.

Right, that's the first thing that I think about when I see this PR. This looks like a Clang bug to me, is that possible? I don't understand why t.begin() could ever trigger ADL, and hence why this fix is necessary from the library side at all. Instead, I would expect that we fix Clang and then add the tests.

Of course, I'm probably wrong, but it would be worth understanding this instead of blindly "fixing" the library.

[• Quuxplusone]

libcxx/include/__ranges/access.h

55

@ldionne wrote:

This looks like a Clang bug to me, is that possible? I don't understand why t.begin() could ever trigger ADL, and hence why this fix is necessary from the library side at all. Instead, I would expect that we fix Clang and then add the tests.

Yes, it's a Clang bug — and I just tracked it down and filed it as https://github.com/llvm/llvm-project/issues/52970 . However, even if we can get Clang14 fixed, we still need this as a workaround since we want libc++14 to work with Clang13.

[ldionne]

libcxx/include/__ranges/access.h

55

Yes, it's a Clang bug — and I just tracked it down and filed it as https://github.com/llvm/llvm-project/issues/52970 .

Woooh, I love when we do that! Thanks for looking into it!

In that case, I would suggest that we add this:

template <class _Tp>
concept __workaround_52970 = __class_or_enum<remove_cvref_t<_Tp>>;

Along with a suitable comment, and then we can use __workaround_52970<_Tp> in the affected concepts. Then, as soon as we drop support for Clang 13, we can grep-remove this workaround. WDYT?

[• Quuxplusone]

libcxx/include/__ranges/access.h

55

Sure, works for me. (This is another opportunity to open the can of worms of whether it should be, like, concept __workaround_52970 = is_class_v<remove_cvref_t<_Tp>> || is_union_v<remove_cvref_t<_Tp>>; — but I'm okay not opening that can.)

[• Quuxplusone]

Add some new expanded tests for data and size, in addition to the ADL ones.
Apply Louis's suggested workaround for the Clang bug.

[• Quuxplusone]

Oops, I had an uncommitted diff here. Add __uncvref_t to the workaround.

libcxx/include/__concepts/class_or_enum.h

 
 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_CONCEPTS)
 
 // Whether a type is a class type or enumeration type according to the Core wording.
 
 template<class _Tp>
 concept __class_or_enum = is_class_v<_Tp> || is_union_v<_Tp> || is_enum_v<_Tp>;
 
+// Work around Clang bug https://llvm.org/PR52970
+template<class _Tp>
+concept __workaround_52970 = is_class_v<__uncvref_t<_Tp>> || is_union_v<__uncvref_t<_Tp>>;
+
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_CONCEPTS)
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___CONCEPTS_CLASS_OR_ENUM_H

libcxx/include/__ranges/access.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_ACCESS_H
 #define _LIBCPP___RANGES_ACCESS_H
 
+#include <__concepts/class_or_enum.h>
 #include <__config>
 #include <__iterator/concepts.h>
 #include <__iterator/readable_traits.h>
 #include <__ranges/enable_borrowed_range.h>
 #include <__utility/as_const.h>
 #include <__utility/auto_cast.h>
 #include <concepts>
 #include <type_traits>

 
 // [range.access.begin]
 
 namespace ranges {
 namespace __begin {
   template <class _Tp>
   concept __member_begin =
     __can_borrow<_Tp> &&
+    __workaround_52970<_Tp> &&
     requires(_Tp&& __t) {
       { _LIBCPP_AUTO_CAST(__t.begin()) } -> input_or_output_iterator;
     };
 
   void begin(auto&) = delete;
   void begin(const auto&) = delete;
 
   template <class _Tp>
   concept __unqualified_begin =
     !__member_begin<_Tp> &&
     __can_borrow<_Tp> &&
     __class_or_enum<remove_cvref_t<_Tp>> &&
     requires(_Tp && __t) {
       { _LIBCPP_AUTO_CAST(begin(__t)) } -> input_or_output_iterator;
     };
 
   struct __fn {
     template <class _Tp>
       requires is_array_v<remove_cv_t<_Tp>>
     [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Tp& __t) const noexcept

 
 // [range.access.end]
 
 namespace ranges {
 namespace __end {
   template <class _Tp>
   concept __member_end =
     __can_borrow<_Tp> &&
+    __workaround_52970<_Tp> &&
     requires(_Tp&& __t) {
       typename iterator_t<_Tp>;
       { _LIBCPP_AUTO_CAST(__t.end()) } -> sentinel_for<iterator_t<_Tp>>;
     };
 
   void end(auto&) = delete;
   void end(const auto&) = delete;
 

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 <__concepts/class_or_enum.h>
 #include <__config>
 #include <__iterator/concepts.h>
 #include <__ranges/access.h>
 #include <__ranges/size.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)
 
 // [range.prim.empty]
 
 namespace ranges {
 namespace __empty {
   template <class _Tp>
-  concept __member_empty = requires(_Tp&& __t) {
+  concept __member_empty =
+    __workaround_52970<_Tp> &&
+    requires(_Tp&& __t) {
       bool(__t.empty());
     };
 
   template<class _Tp>
   concept __can_invoke_size =
     !__member_empty<_Tp> &&
     requires(_Tp&& __t) { ranges::size(__t); };
 
   template <class _Tp>
   concept __can_compare_begin_end =

libcxx/include/__ranges/size.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_SIZE_H
 #define _LIBCPP___RANGES_SIZE_H
 
+#include <__concepts/class_or_enum.h>
 #include <__config>
 #include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.h>
 #include <__ranges/access.h>
 #include <__utility/auto_cast.h>
 #include <concepts>
 #include <type_traits>
 

 namespace __size {
   void size(auto&) = delete;
   void size(const auto&) = delete;
 
   template <class _Tp>
   concept __size_enabled = !disable_sized_range<remove_cvref_t<_Tp>>;
 
   template <class _Tp>
-  concept __member_size = __size_enabled<_Tp> && requires(_Tp&& __t) {
+  concept __member_size =
+    __size_enabled<_Tp> &&
+    __workaround_52970<_Tp> &&
+    requires(_Tp&& __t) {
       { _LIBCPP_AUTO_CAST(__t.size()) } -> __integer_like;
     };
 
   template <class _Tp>
   concept __unqualified_size =
     __size_enabled<_Tp> &&
     !__member_size<_Tp> &&
     __class_or_enum<remove_cvref_t<_Tp>> &&
     requires(_Tp&& __t) {
       { _LIBCPP_AUTO_CAST(size(__t)) } -> __integer_like;

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

 static_assert(!noexcept(std::ranges::cbegin(ntmbrr)));
 
 struct BeginReturnsArrayRef {
     auto begin() const noexcept -> int(&)[10];
 } brar;
 static_assert(noexcept(std::ranges::begin(brar)));
 static_assert(noexcept(std::ranges::cbegin(brar)));
 
+// Test ADL-proofing.
+struct Incomplete;
+template<class T> struct Holder { T t; };
+static_assert(!std::is_invocable_v<RangeBeginT, Holder<Incomplete>*>);
+static_assert(!std::is_invocable_v<RangeCBeginT, Holder<Incomplete>*>);
+
 int main(int, char**) {
   static_assert(testReturnTypes());
 
   testArray();
   static_assert(testArray());
 
   testBeginMember();
   static_assert(testBeginMember());
 
   testBeginFunction();
   static_assert(testBeginFunction());
 
   return 0;
 }

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

 // UNSUPPORTED: libcpp-no-concepts
 // UNSUPPORTED: libcpp-has-no-incomplete-ranges
 
 // std::ranges::data
 
 #include <ranges>
 
 #include <cassert>
+#include <type_traits>
 #include "test_macros.h"
 #include "test_iterators.h"
 
 using RangeDataT = decltype(std::ranges::data);
 
 static int globalBuff[2];
 
 struct Incomplete;

 static_assert( std::is_invocable_v<RangeDataT, BeginMemberContiguousIterator const&>);
 static_assert(!std::is_invocable_v<RangeDataT, BeginMemberContiguousIterator const&&>);
 
 struct BeginMemberRandomAccess {
   int buff[8];
 
   random_access_iterator<const int*> begin() const;
 };
-static_assert(!std::is_invocable_v<RangeDataT, BeginMemberRandomAccess>);
-static_assert(!std::is_invocable_v<RangeDataT, BeginMemberRandomAccess const>);
-static_assert(!std::is_invocable_v<RangeDataT, BeginMemberRandomAccess const&>);
+static_assert(!std::is_invocable_v<RangeDataT, BeginMemberRandomAccess&>);
+static_assert(!std::is_invocable_v<RangeDataT, BeginMemberRandomAccess&&>);
+static_assert(!std::is_invocable_v<RangeDataT, const BeginMemberRandomAccess&>);
+static_assert(!std::is_invocable_v<RangeDataT, const BeginMemberRandomAccess&&>);
 
 struct BeginFriendContiguousIterator {
   int buff[8];
 
   friend constexpr ContiguousIter begin(const BeginFriendContiguousIterator &iter) {
     return ContiguousIter(iter.buff);
   }
 };
 static_assert( std::is_invocable_v<RangeDataT, BeginMemberContiguousIterator &>);
 static_assert(!std::is_invocable_v<RangeDataT, BeginMemberContiguousIterator &&>);
 static_assert( std::is_invocable_v<RangeDataT, BeginMemberContiguousIterator const&>);
 static_assert(!std::is_invocable_v<RangeDataT, BeginMemberContiguousIterator const&&>);
 
 struct BeginFriendRandomAccess {
   friend random_access_iterator<const int*> begin(const BeginFriendRandomAccess iter);
 };
-static_assert(!std::is_invocable_v<RangeDataT, BeginFriendRandomAccess>);
-static_assert(!std::is_invocable_v<RangeDataT, BeginFriendRandomAccess const>);
-static_assert(!std::is_invocable_v<RangeDataT, BeginFriendRandomAccess const&>);
+static_assert(!std::is_invocable_v<RangeDataT, BeginFriendRandomAccess&>);
+static_assert(!std::is_invocable_v<RangeDataT, BeginFriendRandomAccess&&>);
+static_assert(!std::is_invocable_v<RangeDataT, const BeginFriendRandomAccess&>);
+static_assert(!std::is_invocable_v<RangeDataT, const BeginFriendRandomAccess&&>);
 
 struct BeginMemberRvalue {
   int buff[8];
 
   ContiguousIter begin() &&;
 };
 static_assert(!std::is_invocable_v<RangeDataT, BeginMemberRvalue&&>);
 static_assert(!std::is_invocable_v<RangeDataT, BeginMemberRvalue const&>);
constexpr bool testViaRangesBegin() {
   assert(std::ranges::data(b) == b.buff);
 
   BeginMemberBorrowingEnabled c;
   assert(std::ranges::data(std::move(c)) == &globalBuff[1]);
 
   return true;
 }
 
+// Test ADL-proofing.
+struct Incomplete;
+template<class T> struct Holder { T t; };
+static_assert(!std::is_invocable_v<RangeDataT, Holder<Incomplete>*>);
+
+struct RandomButNotContiguous {
+  random_access_iterator<int*> begin() const;
+  random_access_iterator<int*> end() const;
+};
+static_assert(!std::is_invocable_v<RangeDataT, RandomButNotContiguous>);
+
 int main(int, char**) {
   testDataMember();
   static_assert(testDataMember());
 
   testViaRangesBegin();
   static_assert(testViaRangesBegin());
 
   return 0;
 }

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

constexpr bool testBeginEqualsEnd() {
   assert(!std::ranges::empty(e)); // e.empty()
   assert(std::ranges::empty(std::as_const(e))); // e.begin() == e.end()
 
   assert(std::ranges::empty(EvilBeginEnd()));
 
   return true;
 }
 
+// Test ADL-proofing.
+struct Incomplete;
+template<class T> struct Holder { T t; };
+static_assert(!std::is_invocable_v<RangeEmptyT, Holder<Incomplete>*>);
+
 int main(int, char**) {
   testEmptyMember();
   static_assert(testEmptyMember());
 
   testUsingRangesSize();
   static_assert(testUsingRangesSize());
 
   testBeginEqualsEnd();
   static_assert(testBeginEqualsEnd());
 
   return 0;
 }

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

 
 struct EndReturnsArrayRef {
     auto begin() const noexcept -> int(&)[10];
     auto end() const noexcept -> int(&)[10];
 } erar;
 static_assert(noexcept(std::ranges::end(erar)));
 static_assert(noexcept(std::ranges::cend(erar)));
 
+// Test ADL-proofing.
+struct Incomplete;
+template<class T> struct Holder { T t; };
+static_assert(!std::is_invocable_v<RangeEndT, Holder<Incomplete>*>);
+static_assert(!std::is_invocable_v<RangeCEndT, Holder<Incomplete>*>);
+
 int main(int, char**) {
   static_assert(testReturnTypes());
 
   testArray();
   static_assert(testArray());
 
   testEndMember();
   static_assert(testEndMember());
 
   testEndFunction();
   static_assert(testEndFunction());
 
   return 0;
 }

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

constexpr bool testRanges() {
   ASSERT_SAME_TYPE(decltype(std::ranges::size(d)), size_t);
 
   SizeBeginAndEndMembers e;
   assert(std::ranges::size(e) == 1);
 
   return true;
 }
 
+// Test ADL-proofing.
+struct Incomplete;
+template<class T> struct Holder { T t; };
+static_assert(!std::is_invocable_v<RangeSizeT, Holder<Incomplete>*>);
+
 int main(int, char**) {
   testArrayType();
   static_assert(testArrayType());
 
   testHasSizeMember();
   static_assert(testHasSizeMember());
 
   testHasSizeFunction();
   static_assert(testHasSizeFunction());
 
   testRanges();
   static_assert(testRanges());
 
   return 0;
 }

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

constexpr bool test() {
   // This gets converted to ptrdiff_t because it's wider.
   ShortUnsignedReturnType c;
   assert(std::ranges::ssize(c) == 42);
   ASSERT_SAME_TYPE(decltype(std::ranges::ssize(c)), ptrdiff_t);
 
   return true;
 }
 
+// Test ADL-proofing.
+struct Incomplete;
+template<class T> struct Holder { T t; };
+static_assert(!std::is_invocable_v<RangeSSizeT, Holder<Incomplete>*>);
+
 int main(int, char**) {
   test();
   static_assert(test());
 
   return 0;
 }

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

 };
 static_assert(!std::ranges::range<iterator_begin_int_end>);
 
 struct int_begin_iterator_end {
   int begin();
   int* end();
 };
 static_assert(!std::ranges::range<int_begin_iterator_end>);
+
+// Test ADL-proofing.
+struct Incomplete;
+template<class T> struct Holder { T t; };
+static_assert(!std::ranges::range<Holder<Incomplete>*>);