Add container overloads for absl::c_copy and absl::c_copy_n These versions accept a container as the output destination. The primary motivation for these overloads is to add bounds checking. We determine if an object is a container by checking if they support `std::begin`/`std::end`. PiperOrigin-RevId: 907840607 Change-Id: I10430108dc734f1e93c0cef6ca33d251520ac3e8
diff --git a/absl/algorithm/BUILD.bazel b/absl/algorithm/BUILD.bazel index e891d8a..7d8350c 100644 --- a/absl/algorithm/BUILD.bazel +++ b/absl/algorithm/BUILD.bazel
@@ -69,7 +69,6 @@ ":algorithm", "//absl/base:config", "//absl/base:core_headers", - "//absl/base:iterator_traits_internal", "//absl/meta:type_traits", ], ) @@ -85,7 +84,6 @@ "//absl/base:config", "//absl/base:core_headers", "//absl/memory", - "//absl/meta:type_traits", "//absl/random", "//absl/types:span", "@googletest//:gtest",
diff --git a/absl/algorithm/CMakeLists.txt b/absl/algorithm/CMakeLists.txt index 13230ee..cdd5d14 100644 --- a/absl/algorithm/CMakeLists.txt +++ b/absl/algorithm/CMakeLists.txt
@@ -49,7 +49,6 @@ DEPS absl::algorithm absl::config - absl::iterator_traits_internal absl::core_headers absl::meta PUBLIC @@ -67,7 +66,6 @@ absl::config absl::core_headers absl::memory - absl::meta absl::random_random absl::span GTest::gmock_main
diff --git a/absl/algorithm/container.h b/absl/algorithm/container.h index 71e6660..a823ee1 100644 --- a/absl/algorithm/container.h +++ b/absl/algorithm/container.h
@@ -52,7 +52,6 @@ #include "absl/algorithm/algorithm.h" #include "absl/base/config.h" -#include "absl/base/internal/iterator_traits.h" #include "absl/base/macros.h" #include "absl/meta/type_traits.h" @@ -107,42 +106,6 @@ return end(c); } -// Helper to check that the `OutputRange` has enough space. -// Only performs the check if the iterators are ForwardIterators or better. -template <typename InputSequence, typename Size, typename OutputRange> -bool CheckCopyNSize(InputSequence& input, Size n, OutputRange& output) { - using InputIter = ContainerIter<InputSequence>; - using OutputIter = ContainerIter<OutputRange>; - - if constexpr (base_internal::IsAtLeastForwardIterator<InputIter>::value) { - if (n > std::distance(container_algorithm_internal::c_begin(input), - container_algorithm_internal::c_end(input))) { - return false; - } - } - if constexpr (base_internal::IsAtLeastForwardIterator<OutputIter>::value) { - if (n > std::distance(container_algorithm_internal::c_begin(output), - container_algorithm_internal::c_end(output))) { - return false; - } - } - return true; -} - -template <typename InputSequence, typename OutputRange> -bool CheckCopySize(InputSequence& input, OutputRange& output) { - using InputIter = ContainerIter<InputSequence>; - using OutputIter = ContainerIter<OutputRange>; - if constexpr (base_internal::IsAtLeastForwardIterator<InputIter>::value && - base_internal::IsAtLeastForwardIterator<OutputIter>::value) { - return std::distance(container_algorithm_internal::c_begin(input), - container_algorithm_internal::c_end(input)) <= - std::distance(container_algorithm_internal::c_begin(output), - container_algorithm_internal::c_end(output)); - } - return true; -} - template <typename T> struct IsUnorderedContainer : std::false_type {}; @@ -154,27 +117,6 @@ struct IsUnorderedContainer<std::unordered_set<Key, Hash, KeyEqual, Allocator>> : std::true_type {}; -template <typename T, typename = void> -struct HasBeginEnd : std::false_type {}; - -template <typename T> -struct HasBeginEnd<T, std::void_t<decltype(container_algorithm_internal::begin( - std::declval<T (*)()>()())), - decltype(container_algorithm_internal::end( - std::declval<T (*)()>()()))>> - : std::true_type {}; - -// We don't support multidimensional arrays yet -template <class T> -using IsMultidimensionalArray = std::is_array<std::remove_extent_t<T>>; - -template <typename Iter, typename = void> -struct IsIterator : std::false_type {}; - -template <typename Iter> -struct IsIterator< - Iter, std::void_t<typename std::iterator_traits<Iter>::iterator_category>> - : std::true_type {}; } // namespace container_algorithm_internal // PUBLIC API @@ -579,42 +521,10 @@ // Container-based version of the <algorithm> `std::copy()` function to copy a // container's elements into an iterator. template <typename InputSequence, typename OutputIterator> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - std::enable_if_t<container_algorithm_internal::IsIterator< - absl::remove_cvref_t<OutputIterator>>::value && - !container_algorithm_internal::IsMultidimensionalArray< - InputSequence>::value, - std::decay_t<OutputIterator>> - c_copy(const InputSequence& input, OutputIterator&& output) { +ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIterator +c_copy(const InputSequence& input, OutputIterator output) { return std::copy(container_algorithm_internal::c_begin(input), - container_algorithm_internal::c_end(input), - std::forward<OutputIterator>(output)); -} - -// Copies elements from `input` to `output`. `absl::c_copy(input, output)` is -// equivalent to `std::copy(std::begin(input), std::end(input), -// std::begin(output))`. -// -// The `output` container must be large enough to hold all elements of `input`; -// this function does not resize `output`. - -// If `std::size(input) > std::size(output)`, behavior is undefined. -// If `std::size(output) > std::size(input)`, only `std::size(input)` elements -// are copied, and `output` is not truncated. -template <typename InputSequence, typename OutputRange> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - std::enable_if_t<container_algorithm_internal::HasBeginEnd< - std::add_lvalue_reference_t<OutputRange>>::value && - !container_algorithm_internal::IsMultidimensionalArray< - std::remove_reference_t<OutputRange>>::value && - !container_algorithm_internal::IsMultidimensionalArray< - InputSequence>::value, - void> - c_copy(const InputSequence& input, OutputRange&& output) { - ABSL_HARDENING_ASSERT( - container_algorithm_internal::CheckCopySize(input, output)); - absl::c_copy(input, container_algorithm_internal::c_begin( - std::forward<OutputRange>(output))); + container_algorithm_internal::c_end(input), output); } // c_copy_n() @@ -622,41 +532,9 @@ // Container-based version of the <algorithm> `std::copy_n()` function to copy a // container's first N elements into an iterator. template <typename C, typename Size, typename OutputIterator> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 std::enable_if_t< - container_algorithm_internal::IsIterator< - absl::remove_cvref_t<OutputIterator>>::value && - !container_algorithm_internal::IsMultidimensionalArray<C>::value, - std::decay_t<OutputIterator>> -c_copy_n(const C& input, Size n, OutputIterator&& output) { - return std::copy_n(container_algorithm_internal::c_begin(input), n, - std::forward<OutputIterator>(output)); -} - -// Copies the first `n` elements from `input` to `output`. -// `absl::c_copy_n(input, n, output)` is equivalent to -// `std::copy_n(std::begin(input), n, std::begin(output))`. -// -// The `output` container must be large enough to hold N elements; this function -// does not resize `output`. -// -// If `n > std::size(output)` or `n > std::size(input)`, behavior is -// undefined. -// If `std::size(output) > n`, only `n` elements are copied, and `output` is not -// truncated. -template <typename C, typename Size, typename OutputRange> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 std::enable_if_t< - container_algorithm_internal::HasBeginEnd< - std::add_lvalue_reference_t<OutputRange>>::value && - !container_algorithm_internal::IsMultidimensionalArray< - std::remove_reference_t<OutputRange>>::value && - !container_algorithm_internal::IsMultidimensionalArray<C>::value, - void> -c_copy_n(const C& input, Size n, OutputRange&& output) { - ABSL_HARDENING_ASSERT( - container_algorithm_internal::CheckCopyNSize(input, n, output)); - absl::c_copy_n( - input, n, - container_algorithm_internal::c_begin(std::forward<OutputRange>(output))); +ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIterator +c_copy_n(const C& input, Size n, OutputIterator output) { + return std::copy_n(container_algorithm_internal::c_begin(input), n, output); } // c_copy_if() @@ -941,8 +819,8 @@ typename Iterator = container_algorithm_internal::ContainerIter<C>> ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 Iterator c_rotate(C& sequence, Iterator middle) { - return absl::rotate(container_algorithm_internal::c_begin(sequence), middle, - container_algorithm_internal::c_end(sequence)); + return std::rotate(container_algorithm_internal::c_begin(sequence), middle, + container_algorithm_internal::c_end(sequence)); } // c_rotate_copy()
diff --git a/absl/algorithm/container_test.cc b/absl/algorithm/container_test.cc index 69e48f6..8a898be 100644 --- a/absl/algorithm/container_test.cc +++ b/absl/algorithm/container_test.cc
@@ -17,7 +17,6 @@ #include <algorithm> #include <array> #include <cstddef> -#include <forward_list> #include <functional> #include <initializer_list> #include <iterator> @@ -26,7 +25,6 @@ #include <ostream> #include <random> #include <set> -#include <type_traits> #include <unordered_set> #include <utility> #include <valarray> @@ -38,7 +36,6 @@ #include "absl/base/config.h" #include "absl/base/macros.h" #include "absl/memory/memory.h" -#include "absl/meta/type_traits.h" #include "absl/random/random.h" #include "absl/types/span.h" @@ -715,190 +712,6 @@ EXPECT_EQ(expected, actual); } -TEST(MutatingTest, CopyNWithNegativeN) { -#ifdef _LIBCPP_VERSION - GTEST_SKIP() << "libc++ does not handle negative counts correctly"; -#else - const std::vector<int> input = {1, 2, 3}; - std::vector<int> actual = {0, 0, 0}; - absl::c_copy_n(input, -1, actual.begin()); - EXPECT_THAT(actual, ElementsAre(0, 0, 0)); -#endif -} - -TEST(MutatingTest, CopyToContainer) { - const std::vector<int> input = {1, 2, 3}; - std::vector<int> actual = {0, 0, 0, 4, 5}; - absl::c_copy(input, actual); - EXPECT_THAT(actual, ElementsAre(1, 2, 3, 4, 5)); -} - -TEST(MutatingTest, CopyNToContainer) { - const std::vector<int> input = {1, 2, 3, 4, 5}; - std::vector<int> actual = {0, 0, 0, 0, 0}; - absl::c_copy_n(input, 2, actual); - EXPECT_THAT(actual, ElementsAre(1, 2, 0, 0, 0)); -} - -TEST(MutatingTest, CopyNToContainerWithZeroN) { - const std::vector<int> input = {1, 2, 3, 4, 5}; - std::vector<int> actual = {0, 0, 0, 0, 0}; - absl::c_copy_n(input, 0, actual); - EXPECT_THAT(actual, ElementsAre(0, 0, 0, 0, 0)); -} - -TEST(MutatingTest, CopyNToContainerWithNegativeN) { -#ifdef _LIBCPP_VERSION - GTEST_SKIP() << "libc++ does not handle negative counts correctly"; -#else - const std::vector<int> input = {1, 2, 3}; - std::vector<int> actual = {0, 0, 0}; - absl::c_copy_n(input, -1, actual); - EXPECT_THAT(actual, ElementsAre(0, 0, 0)); -#endif -} - -TEST(MutatingTest, CopyToDifferentContainerType) { - const std::list<int> input = {1, 2, 3}; - std::array<int, 5> actual = {0, 0, 0, 4, 5}; - absl::c_copy(input, actual); - EXPECT_THAT(actual, ElementsAre(1, 2, 3, 4, 5)); -} - -TEST(MutatingTest, CopyNToDifferentContainerType) { - const std::list<int> input = {1, 2, 3, 4, 5}; - std::array<int, 5> actual = {0, 0, 0, 0, 0}; - absl::c_copy_n(input, 2, actual); - EXPECT_THAT(actual, ElementsAre(1, 2, 0, 0, 0)); -} - -TEST(MutatingTest, CopyToCArray) { - const std::vector<int> input = {1, 2, 3}; - int actual[5] = {0, 0, 0, 4, 5}; - absl::c_copy(input, actual); - EXPECT_THAT(actual, ElementsAre(1, 2, 3, 4, 5)); -} - -TEST(MutatingTest, CopyNToCArray) { - const std::vector<int> input = {1, 2, 3, 4, 5}; - int actual[5] = {0, 0, 0, 0, 0}; - absl::c_copy_n(input, 2, actual); - EXPECT_THAT(actual, ElementsAre(1, 2, 0, 0, 0)); -} - -TEST(MutatingTest, CopyFromCArray) { - const int input[5] = {1, 2, 3, 4, 5}; - std::vector<int> actual = {0, 0, 0, 0, 0}; - absl::c_copy(input, actual); - EXPECT_THAT(actual, ElementsAre(1, 2, 3, 4, 5)); -} - -TEST(MutatingTest, CopyNFromCArray) { - const int input[5] = {1, 2, 3, 4, 5}; - std::vector<int> actual = {0, 0, 0, 0, 0}; - absl::c_copy_n(input, 2, actual); - EXPECT_THAT(actual, ElementsAre(1, 2, 0, 0, 0)); -} - -TEST(MutatingTest, CopyContainerWithNoSizeMethod) { - const std::forward_list<int> input = {1, 2, 3}; - std::forward_list<int> actual = {0, 0, 0, 4, 5}; - absl::c_copy(input, actual); - EXPECT_THAT(actual, ElementsAre(1, 2, 3, 4, 5)); -} - -TEST(MutatingTest, CopyNContainerWithNoSizeMethod) { - const std::forward_list<int> input = {1, 2, 3, 4, 5}; - std::forward_list<int> actual = {0, 0, 0, 0, 0}; - absl::c_copy_n(input, 2, actual); - EXPECT_THAT(actual, ElementsAre(1, 2, 0, 0, 0)); -} - -#if GTEST_HAS_DEATH_TEST - -bool IsHardened() { - bool hardened = false; - ABSL_HARDENING_ASSERT([&hardened]() { - hardened = true; - return true; - }()); - return hardened; -} - -TEST(MutatingTest, CopyToCArrayInvalidSize) { - const std::vector<int> input = {1, 2, 3}; - int actual[2] = {0, 0}; - if (IsHardened()) { - EXPECT_DEATH(absl::c_copy(input, actual), ""); - } -} - -TEST(MutatingTest, CopyNToCArrayInvalidSize) { - const std::vector<int> input = {1, 2, 3}; - int actual[2] = {0, 0}; - if (IsHardened()) { - EXPECT_DEATH(absl::c_copy_n(input, 3, actual), ""); - } -} - -TEST(MutatingTest, CopyNToCArrayNGreaterThanInput) { - const std::vector<int> input = {1, 2, 3}; - int actual[4] = {0, 0, 0, 0}; - if (IsHardened()) { - EXPECT_DEATH(absl::c_copy_n(input, 4, actual), ""); - } -} - -TEST(MutatingTest, CopyToContainerInvalidSize) { - const std::list<int> input = {1, 2, 3, 4, 5}; - std::list<int> actual = {0, 0, 0}; - if (IsHardened()) { - EXPECT_DEATH(absl::c_copy(input, actual), ""); - } -} - -TEST(MutatingTest, CopyNToContainerNGreaterThanInput) { - const std::vector<int> input = {1, 2, 3}; - std::vector<int> actual = {0, 0, 0, 0}; - if (IsHardened()) { - EXPECT_DEATH(absl::c_copy_n(input, 4, actual), ""); - } -} - -TEST(MutatingTest, CopyNToContainerNGreaterThanOutput) { - const std::vector<int> input = {1, 2, 3}; - std::vector<int> actual = {0, 0}; - if (IsHardened()) { - EXPECT_DEATH(absl::c_copy_n(input, 3, actual), ""); - } -} - -TEST(MutatingTest, CopyToForwardListInvalidSize) { - const std::forward_list<int> input = {1, 2, 3, 4, 5}; - std::forward_list<int> actual = {0, 0, 0}; - if (IsHardened()) { - EXPECT_DEATH(absl::c_copy(input, actual), ""); - } -} - -TEST(MutatingTest, CopyNToForwardListNGreaterThanInput) { - const std::forward_list<int> input = {1, 2, 3}; - std::forward_list<int> actual = {0, 0, 0, 0}; - if (IsHardened()) { - EXPECT_DEATH(absl::c_copy_n(input, 4, actual), ""); - } -} - -TEST(MutatingTest, CopyNToForwardListNGreaterThanOutput) { - const std::forward_list<int> input = {1, 2, 3}; - std::forward_list<int> actual = {0, 0}; - if (IsHardened()) { - EXPECT_DEATH(absl::c_copy_n(input, 3, actual), ""); - } -} - -#endif // GTEST_HAS_DEATH_TEST - TEST(MutatingTest, CopyIf) { const std::list<int> input = {1, 2, 3}; std::vector<int> output; @@ -2416,42 +2229,4 @@ #endif // defined(ABSL_INTERNAL_CPLUSPLUS_LANG) && // ABSL_INTERNAL_CPLUSPLUS_LANG >= 202002L -template <typename Container, typename Output, typename = void> -struct CanCopy : std::false_type {}; -template <typename Container, typename Output> -struct CanCopy<Container, Output, - absl::void_t<decltype(absl::c_copy(std::declval<Container>(), - std::declval<Output>()))>> - : std::true_type {}; - -template <typename Container, typename Output, typename = void> -struct CanCopyN : std::false_type {}; -template <typename Container, typename Output> -struct CanCopyN<Container, Output, - absl::void_t<decltype(absl::c_copy_n( - std::declval<Container>(), std::declval<ptrdiff_t>(), - std::declval<Output>()))>> : std::true_type {}; - -TEST(CanCopyTest, CopyToMultiDimArray) { - static_assert(CanCopy<std::vector<int>, int (&)[10]>::value); - static_assert(!CanCopy<std::vector<int>, int (&)[2][2]>::value); - static_assert(CanCopyN<std::vector<int>, int (&)[10]>::value); - static_assert(!CanCopyN<std::vector<int>, int (&)[2][2]>::value); - - static_assert(CanCopy<int[10], int (&)[10]>::value); - static_assert(!CanCopy<int[10], int (&)[2][2]>::value); - static_assert(CanCopyN<int[10], int (&)[10]>::value); - static_assert(!CanCopyN<int[10], int (&)[2][2]>::value); - static_assert(!CanCopy<int[2][2], int (&)[4]>::value); - static_assert(!CanCopy<int[2][2], int (&)[2][2]>::value); - static_assert(!CanCopyN<int[2][2], int (&)[4]>::value); - static_assert(!CanCopyN<int[2][2], int (&)[2][2]>::value); -} - -TEST(CanCopyTest, BlockNonWritableIterators) { - using Vec = std::vector<int>; - - static_assert(CanCopy<Vec, Vec::iterator>::value); - static_assert(CanCopy<Vec, std::back_insert_iterator<Vec>>::value); -} } // namespace