[STLExtras] Allow for non-member `begin`/`end` in `append_range`

[kuhar]

Summary

This makes append_range useable with, C arrays and types with custom
begin/end functions.

[kazu]

Thanks!

[foad]

Hi, this patch is provoking a build failure in an LLVM_ENABLE_EXPENSIVE_CHECKS build on my Ubuntu 22.04.2 machine using Clang 14 as the host compiler:

[189/189] Building CXX object unittests/ADT/CMakeFiles/ADTTests.dir/STLExtrasTest.cpp.o
FAILED: unittests/ADT/CMakeFiles/ADTTests.dir/STLExtrasTest.cpp.o 
/usr/lib/ccache/clang++ -DEXPENSIVE_CHECKS -DGTEST_HAS_RTTI=0 -D_DEBUG -D_GLIBCXX_ASSERTIONS -D_GLIBCXX_DEBUG -D_GNU_SOURCE -D_LIBCPP_ENABLE_ASSERTIONS -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -I/home/jayfoad2/llvm-expensive/unittests/ADT -I/home/jayfoad2/git/llvm-project/llvm/unittests/ADT -I/home/jayfoad2/llvm-expensive/include -I/home/jayfoad2/git/llvm-project/llvm/include -I/home/jayfoad2/git/llvm-project/third-party/unittest/googletest/include -I/home/jayfoad2/git/llvm-project/third-party/unittest/googlemock/include -fPIC -fno-semantic-interposition -fvisibility-inlines-hidden -Werror=date-time -Werror=unguarded-availability-new -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wc++98-compat-extra-semi -Wimplicit-fallthrough -Wcovered-switch-default -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wsuggest-override -Wstring-conversion -Wmisleading-indentation -Wctad-maybe-unsupported -fdiagnostics-color -g  -Wno-variadic-macros -Wno-gnu-zero-variadic-macro-arguments -fno-exceptions -fno-rtti -Wno-suggest-override -std=c++17 -MD -MT unittests/ADT/CMakeFiles/ADTTests.dir/STLExtrasTest.cpp.o -MF unittests/ADT/CMakeFiles/ADTTests.dir/STLExtrasTest.cpp.o.d -o unittests/ADT/CMakeFiles/ADTTests.dir/STLExtrasTest.cpp.o -c /home/jayfoad2/git/llvm-project/llvm/unittests/ADT/STLExtrasTest.cpp
In file included from /home/jayfoad2/git/llvm-project/llvm/unittests/ADT/STLExtrasTest.cpp:9:
In file included from /home/jayfoad2/git/llvm-project/llvm/include/llvm/ADT/STLExtras.h:20:
In file included from /home/jayfoad2/git/llvm-project/llvm/include/llvm/ADT/Hashing.h:51:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/algorithm:60:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/stl_algobase.h:69:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/debug/debug.h:133:
/usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/debug/functions.h:110:44: error: no matching function for call to '__addressof'
      return __foreign_iterator_aux4(__it, std::__addressof(*__other));
                                           ^~~~~~~~~~~~~~~~
/usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/debug/functions.h:164:14: note: in instantiation of function template specialization '__gnu_debug::__foreign_iterator_aux3<__gnu_cxx::__normal_iterator<const int *, std::__cxx1998::vector<int>>, std::vector<int>, std::random_access_iterator_tag, llvm::detail::SafeIntIterator<int, false>>' requested here
      return __foreign_iterator_aux3(__it, __other, __other_end, __tag());
             ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/debug/functions.h:186:5: note: in instantiation of function template specialization '__gnu_debug::__foreign_iterator_aux2<__gnu_cxx::__normal_iterator<const int *, std::__cxx1998::vector<int>>, std::vector<int>, std::random_access_iterator_tag, llvm::detail::SafeIntIterator<int, false>>' requested here
        || __foreign_iterator_aux2(__it, std::__miter_base(__other),
           ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/debug/functions.h:198:14: note: in instantiation of function template specialization '__gnu_debug::__foreign_iterator_aux<__gnu_cxx::__normal_iterator<const int *, std::__cxx1998::vector<int>>, std::vector<int>, std::random_access_iterator_tag, llvm::detail::SafeIntIterator<int, false>>' requested here
      return __foreign_iterator_aux(__it, __other, __other_end, _Integral());
             ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/debug/vector:626:4: note: in instantiation of function template specialization '__gnu_debug::__foreign_iterator<__gnu_cxx::__normal_iterator<const int *, std::__cxx1998::vector<int>>, std::vector<int>, std::random_access_iterator_tag, llvm::detail::SafeIntIterator<int, false>>' requested here
          __glibcxx_check_insert_range(__position, __first, __last, __dist);
          ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/debug/macros.h:183:36: note: expanded from macro '__glibcxx_check_insert_range'
_GLIBCXX_DEBUG_VERIFY(__gnu_debug::__foreign_iterator(_Position,_First,_Last),\
                                   ^
/home/jayfoad2/git/llvm-project/llvm/include/llvm/ADT/STLExtras.h:2017:5: note: in instantiation of function template specialization 'std::vector<int>::insert<llvm::detail::SafeIntIterator<int, false>, void>' requested here
  C.insert(C.end(), adl_begin(R), adl_end(R));
    ^
/home/jayfoad2/git/llvm-project/llvm/unittests/ADT/STLExtrasTest.cpp:367:3: note: in instantiation of function template specialization 'llvm::append_range<std::vector<int>, llvm::iota_range<int>>' requested here
  append_range(V, llvm::seq(6, 8));
  ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/move.h:49:5: note: candidate function [with _Tp = int] not viable: expects an lvalue for 1st argument
    __addressof(_Tp& __r) _GLIBCXX_NOEXCEPT
    ^
1 error generated.
ninja: build stopped: subcommand failed.

Do you have any idea what is wrong here? Thanks!

[kuhar]

Hi Jay,

In D144420#4164373, @foad wrote:

Do you have any idea what is wrong here? Thanks!

Thanks for the error message, I was able to reproduce it on my system. The first thing I checked was whether std:: vs. adl_ matters here and I can see the same error with std::begin/std::end. Seems like the iterator debug code gets confused at some point and expects to be able to take an address of integers returned from llvm::seq. Digging in deeper now to see how to fix this...

[kuhar]

I removed this test in https://github.com/llvm/llvm-project/commit/010a97974a158ebca0bdb58346a2b303ab8a401e and filed a new issue against SafeIntIterator: https://github.com/llvm/llvm-project/issues/61122

The test with std::string below the compilation error is very similar, so this shouldn't meaningfully impact the test coverage of append_range.

[foad]

In D144420#4164834, @kuhar wrote:

I removed this test in https://github.com/llvm/llvm-project/commit/010a97974a158ebca0bdb58346a2b303ab8a401e and filed a new issue against SafeIntIterator: https://github.com/llvm/llvm-project/issues/61122

Thanks!

llvm/include/llvm/ADT/STLExtras.h

void erase_value(Container &C, ValueType V) {
   C.erase(std::remove(C.begin(), C.end(), V), C.end());
 }
 
 /// Wrapper function to append a range to a container.
 ///
 /// C.insert(C.end(), R.begin(), R.end());
 template <typename Container, typename Range>
 inline void append_range(Container &C, Range &&R) {
-  C.insert(C.end(), R.begin(), R.end());
+  C.insert(C.end(), adl_begin(R), adl_end(R));
 }
 
 /// Given a sequence container Cont, replace the range [ContIt, ContEnd) with
 /// the range [ValIt, ValEnd) (which is not from the same container).
 template<typename Container, typename RandomAccessIterator>
 void replace(Container &Cont, typename Container::iterator ContIt,
              typename Container::iterator ContEnd, RandomAccessIterator ValIt,
              RandomAccessIterator ValEnd) {

llvm/unittests/ADT/STLExtrasTest.cpp

 //===- STLExtrasTest.cpp - Unit tests for STL extras ----------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/Sequence.h"
+#include "llvm/ADT/StringRef.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 #include <climits>
 #include <list>
 #include <vector>
 
 using namespace llvm;
TEST(STLExtrasTest, EraseIf) {
   EXPECT_EQ(4u, V.size());
   EXPECT_EQ(1, V[0]);
   EXPECT_EQ(3, V[1]);
   EXPECT_EQ(5, V[2]);
   EXPECT_EQ(7, V[3]);
 }
 
 TEST(STLExtrasTest, AppendRange) {
-  auto AppendVals = {3};
   std::vector<int> V = {1, 2};
-  append_range(V, AppendVals);
-  EXPECT_EQ(1, V[0]);
-  EXPECT_EQ(2, V[1]);
-  EXPECT_EQ(3, V[2]);
+  auto AppendVals1 = {3};
+  append_range(V, AppendVals1);
+  EXPECT_THAT(V, ElementsAre(1, 2, 3));
+
+  int AppendVals2[] = {4, 5};
+  append_range(V, AppendVals2);
+  EXPECT_THAT(V, ElementsAre(1, 2, 3, 4, 5));
+
+  append_range(V, llvm::seq(6, 8));
+  EXPECT_THAT(V, ElementsAre(1, 2, 3, 4, 5, 6, 7));
+
+  std::string Str;
+  append_range(Str, "abc");
+  EXPECT_THAT(Str, ElementsAre('a', 'b', 'c', '\0'));
+  append_range(Str, "def");
+  EXPECT_THAT(Str, ElementsAre('a', 'b', 'c', '\0', 'd', 'e', 'f', '\0'));
 }
 
 namespace some_namespace {
 struct some_struct {
   std::vector<int> data;
   std::string swap_val;
 };