[ADT] Fix definition of `adl_begin`/`adl_end` and `Iter`/`ValueOfRange`

[kuhar]

Summary

• Make IterOfRange and ValueOfRange work with types that require custom begin/end functions.
• Allow for adl_begin/adl_end to be used in constant-evaluated contexts.
• Use SFINAE-friendly trailing return type deductions adl_begin/adl_end so that they are useable in template argument deduction.
• Add missing documentation comments.

This is required for future work in https://reviews.llvm.org/D144503.

[kuhar]

Drop unnecessary include

[dblaikie]

Fix adl_begin/adl_end so that they work with incomplete types. These require trailing return types, per. 7.5.2.: > In a trailing-return-type, the class being defined is not required to be complete for purposes of class member access. Class members declared later are not visible.

Not sure I follow here - could you describe this in more detail, why adding a trailing return type helps? What happens if the trailing return type isn't used here?

[kuhar]

In D144583#4145554, @dblaikie wrote:

Fix adl_begin/adl_end so that they work with incomplete types. These require trailing return types, per. 7.5.2.: > In a trailing-return-type, the class being defined is not required to be complete for purposes of class member access. Class members declared later are not visible.

Not sure I follow here - could you describe this in more detail, why adding a trailing return type helps? What happens if the trailing return type isn't used here?

If you return just auto, it fails to compile code like:

template <typename R, typename T = ValueOfRange<R>>
void foo(R&&) { ...

if R is an incomplete type and it cannot lookup the definition of .begin() inside std::begin.

We rely on this in a few places, e.g., llvm::interleave or mlir::Diagnostic::operator<<:

class Operation;
...

/// Stream in a range.
template <typename T, typename ValueT = llvm::detail::ValueOfRange<T>>
std::enable_if_t<!std::is_constructible<DiagnosticArgument, T>::value,
                 Diagnostic &>
operator<<(T &&range) {
  return appendRange(range);
}

Error:

In file included from /usr/local/google/home/kubak/llvm/llvm-project/mlir/lib/IR/MLIRContext.cpp:9:                                                                  
In file included from /usr/local/google/home/kubak/llvm/llvm-project/mlir/include/mlir/IR/MLIRContext.h:13:                                                          
In file included from /usr/local/google/home/kubak/llvm/llvm-project/mlir/include/mlir/Support/TypeID.h:20:                                                          
/usr/local/google/home/kubak/llvm/llvm-project/llvm/include/llvm/ADT/STLExtras.h:67:10: error: no matching function for call to 'begin'                              
  return begin(container);                                                                                                                                      
         ^~~~~~~                                                                                                                                                  
/usr/local/google/home/kubak/llvm/llvm-project/llvm/include/llvm/ADT/STLExtras.h:89:39: note: in instantiation of function template specialization 'llvm::adl_begin<m
lir::Operation &>' requested here                                                                                                                                    
    std::remove_reference_t<decltype(*adl_begin(std::declval<RangeT &>()))>;                                                                                         
                                      ^                                                                                                                              
/usr/local/google/home/kubak/llvm/llvm-project/mlir/include/mlir/IR/Diagnostics.h:209:57: note: in instantiation of template type alias 'ValueOfRange' requested here
  template <typename T, typename ValueT = llvm::detail::ValueOfRange<T>>                                                                                             
                                                        ^                                                                                                            
/usr/local/google/home/kubak/llvm/llvm-project/mlir/include/mlir/IR/Diagnostics.h:212:3: note: in instantiation of default argument for 'operator<<<Operation &>' req
uired here                                                                                                                                                           
  operator<<(T &&range) {                                                                                                                                            
  ^~~~~~~~~~~~~~~~~~~~~                                                                                                                                              
/usr/local/google/home/kubak/llvm/llvm-project/mlir/include/mlir/IR/Diagnostics.h:201:56: note: while substituting deduced template arguments into function template 
'operator<<' [with T = Operation &, ValueT = (no value)]                                                                                                             
  Diagnostic &operator<<(Operation *op) { return *this << *op; }                                                                                                     
                                                       ^                                                                                                             
/usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/initializer_list:90:5: note: candidate template ignored: could not match 'initializer_list<_Tp>' a
gainst 'mlir::Operation'                                                                                                                                             
    begin(initializer_list<_Tp> __ils) noexcept                                                                                                                      
    ^                                                                                                                                                                
/usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/range_access.h:52:5: note: candidate template ignored: substitution failure [with _Container 
= mlir::Operation]: member access into incomplete type 'mlir::Operation'                                                                                             
    begin(_Container& __cont) -> decltype(__cont.begin())                                                                                                            
    ^                                           ~                                                                                                                    
/usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/range_access.h:63:5: note: candidate template ignored: substitution failure [with _Container 
= mlir::Operation]: member access into incomplete type 'const mlir::Operation'                                                                                       
    begin(const _Container& __cont) -> decltype(__cont.begin())                                                                                                      
    ^                                                 ~                                                                                                              
/usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/range_access.h:95:5: note: candidate template ignored: could not match '_Tp[_Nm]' against 'ml
ir::Operation'                                                                                                                                                       
    begin(_Tp (&__arr)[_Nm]) noexcept                                                                                                                                
    ^                                                                                                                                                                
/usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/range_access.h:113:31: note: candidate template ignored: could not match 'valarray<_Tp>' agai
nst 'mlir::Operation'                                                                                                                                                
  template<typename _Tp> _Tp* begin(valarray<_Tp>&) noexcept;                                                                                                        
                              ^                                                                                                                                      
/usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/range_access.h:114:37: note: candidate template ignored: could not match 'valarray<_Tp>' agai
nst 'mlir::Operation'                                                                                                                                                
  template<typename _Tp> const _Tp* begin(const valarray<_Tp>&) noexcept;

I'm not sure how to describe this best.

[kuhar]

Edit: I think this boils down to trailing return types participating in SFINE and not wanting to emit hard errors when none of the available begin functions matches when adl_begin is used within a template argument.

[kuhar]

Add missing include

[kuhar]

Rebase

[kuhar]

Ping

[zero9178]

In D144583#4145846, @kuhar wrote:

Edit: I think this boils down to trailing return types participating in SFINE and not wanting to emit hard errors when none of the available begin functions matches when adl_begin is used within a template argument.

I can see the issue as well. During overload resolution, instantiations of ValueOfRange would otherwise immediately error, instead of being a substitution failure. This is best seen in llvm::interleave:
Instantiating it with a container leads to it calling interleave(c.begin(), c.end(), ...) aka with iterators. This once again tries to find the right interleave overload and when considering:

template <typename Container, typename UnaryFunctor, typename StreamT,
          typename T = detail::ValueOfRange<Container>>
inline void interleave(const Container &c, StreamT &os, UnaryFunctor each_fn,
                       const StringRef &separator)

it actually errors out during substitution of ValueOfRange instead of being failing the substitution and removing the candidate from the overload set.

It seems the C++ standard also specifies std::begin and friends with the trailing return type, possibly for the same reason.

In that sense LGTM.

Edit: To add why this makes a difference: SFINAE is only relevant during the template substitutions of the function signature, not the body. Having the begin call in the signature leads to it being a substitution failure, not an error. If that were not there and the return type remained auto, it'd have to instantiate the function body and then error out on no fitting begin existing.

[dblaikie]

Sounds OK - probably worth splitting up similar work in the future, I think there's enough nuance that understanding and testing each axis/feature in a change like this could be clearer when done separately.

llvm/include/llvm/ADT/STLExtras.h

 #endif
 
 namespace llvm {
 
 // Only used by compiler if both template types are the same.  Useful when
 // using SFINAE to test for the existence of member functions.
 template <typename T, T> struct SameType;
 
+namespace adl_detail {
+
+using std::begin;
+
+template <typename RangeT>
+constexpr auto begin_impl(RangeT &&range)
+    -> decltype(begin(std::forward<RangeT>(range))) {
+  return begin(std::forward<RangeT>(range));
+}
+
+using std::end;
+
+template <typename RangeT>
+constexpr auto end_impl(RangeT &&range)
+    -> decltype(end(std::forward<RangeT>(range))) {
+  return end(std::forward<RangeT>(range));
+}
+
+using std::swap;
+
+template <typename T>
+constexpr void swap_impl(T &&lhs,
+                         T &&rhs) noexcept(noexcept(swap(std::declval<T>(),
+                                                         std::declval<T>()))) {
+  swap(std::forward<T>(lhs), std::forward<T>(rhs));
+}
+
+} // end namespace adl_detail
+
+/// Returns the begin iterator to \p range using `std::begin` and
+/// function found through Argument-Dependent Lookup (ADL).
+template <typename RangeT>
+constexpr auto adl_begin(RangeT &&range)
+    -> decltype(adl_detail::begin_impl(std::forward<RangeT>(range))) {
+  return adl_detail::begin_impl(std::forward<RangeT>(range));
+}
+
+/// Returns the end iterator to \p range using `std::end` and
+/// functions found through Argument-Dependent Lookup (ADL).
+template <typename RangeT>
+constexpr auto adl_end(RangeT &&range)
+    -> decltype(adl_detail::end_impl(std::forward<RangeT>(range))) {
+  return adl_detail::end_impl(std::forward<RangeT>(range));
+}
+
+/// Swaps \p lhs with \p rhs using `std::swap` and functions found through
+/// Argument-Dependent Lookup (ADL).
+template <typename T>
+constexpr void adl_swap(T &&lhs, T &&rhs) noexcept(
+    noexcept(adl_detail::swap_impl(std::declval<T>(), std::declval<T>()))) {
+  adl_detail::swap_impl(std::forward<T>(lhs), std::forward<T>(rhs));
+}
+
 namespace detail {
 
 template <typename RangeT>
-using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
+using IterOfRange = decltype(adl_begin(std::declval<RangeT &>()));
 
 template <typename RangeT>
 using ValueOfRange =
-    std::remove_reference_t<decltype(*std::begin(std::declval<RangeT &>()))>;
+    std::remove_reference_t<decltype(*adl_begin(std::declval<RangeT &>()))>;
 
 } // end namespace detail
 
 //===----------------------------------------------------------------------===//
 //     Extra additions to <type_traits>
 //===----------------------------------------------------------------------===//
 
 template <typename T> struct make_const_ptr {
if constexpr (IsPtr) {
       // T is a function reference... dereference the stored pointer.
       return *Func;
     }
   }
 };
 
 } // namespace callable_detail
 
-namespace adl_detail {
-
-using std::begin;
-
-template <typename ContainerTy>
-decltype(auto) adl_begin(ContainerTy &&container) {
-  return begin(std::forward<ContainerTy>(container));
-}
-
-using std::end;
-
-template <typename ContainerTy>
-decltype(auto) adl_end(ContainerTy &&container) {
-  return end(std::forward<ContainerTy>(container));
-}
-
-using std::swap;
-
-template <typename T>
-void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval<T>(),
-                                                       std::declval<T>()))) {
-  swap(std::forward<T>(lhs), std::forward<T>(rhs));
-}
-
-} // end namespace adl_detail
-
-template <typename ContainerTy>
-decltype(auto) adl_begin(ContainerTy &&container) {
-  return adl_detail::adl_begin(std::forward<ContainerTy>(container));
-}
-
-template <typename ContainerTy>
-decltype(auto) adl_end(ContainerTy &&container) {
-  return adl_detail::adl_end(std::forward<ContainerTy>(container));
-}
-
-template <typename T>
-void adl_swap(T &&lhs, T &&rhs) noexcept(
-    noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) {
-  adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs));
-}
-
 /// Returns true if the given container only contains a single element.
 template <typename ContainerTy> bool hasSingleElement(ContainerTy &&C) {
   auto B = std::begin(C), E = std::end(C);
   return B != E && std::next(B) == E;
 }
 
 /// Return a range covering \p RangeOrContainer with the first N elements
 /// excluded.

llvm/unittests/ADT/STLExtrasTest.cpp

 }
 
 void swap(some_struct &lhs, some_struct &rhs) {
   // make swap visible as non-adl swap would even seem to
   // work with std::swap which defaults to moving
   lhs.swap_val = "lhs";
   rhs.swap_val = "rhs";
 }
+
+struct requires_move {};
+int *begin(requires_move &&) { return nullptr; }
+int *end(requires_move &&) { return nullptr; }
 } // namespace some_namespace
 
 TEST(STLExtrasTest, ADLTest) {
   some_namespace::some_struct s{{1, 2, 3, 4, 5}, ""};
   some_namespace::some_struct s2{{2, 4, 6, 8, 10}, ""};
 
   EXPECT_EQ(*adl_begin(s), 1);
   EXPECT_EQ(*(adl_end(s) - 1), 5);
 
   adl_swap(s, s2);
   EXPECT_EQ(s.swap_val, "lhs");
   EXPECT_EQ(s2.swap_val, "rhs");
 
   int count = 0;
   llvm::for_each(s, [&count](int) { ++count; });
-  EXPECT_EQ(5, count);
+  EXPECT_EQ(count, 5);
+}
+
+TEST(STLExtrasTest, ADLTestTemporaryRange) {
+  EXPECT_EQ(adl_begin(some_namespace::requires_move{}), nullptr);
+  EXPECT_EQ(adl_end(some_namespace::requires_move{}), nullptr);
+}
+
+TEST(STLExtrasTest, ADLTestConstexpr) {
+  // `std::begin`/`std::end` are marked as `constexpr`; check that
+  // `adl_begin`/`adl_end` also work in constant-evaluated contexts.
+  static constexpr int c_arr[] = {7, 8, 9};
+  static_assert(adl_begin(c_arr) == c_arr);
+  static_assert(adl_end(c_arr) == c_arr + 3);
+
+  static constexpr std::array<int, 2> std_arr = {1, 2};
+  static_assert(adl_begin(std_arr) == std_arr.begin());
+  static_assert(adl_end(std_arr) == std_arr.end());
+  SUCCEED();
 }
 
 TEST(STLExtrasTest, DropBeginTest) {
   SmallVector<int, 5> vec{0, 1, 2, 3, 4};
 
   for (int n = 0; n < 5; ++n) {
     int i = n;
     for (auto &v : drop_begin(vec, n)) {