From 093cc27604df1c4a179b73bc3f00d4d1ce2ce113 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Wed, 30 Sep 2020 13:36:40 -0700 Subject: Export of internal Abseil changes -- 0674e1ab1c1f71c5362b9e2337333e67f7ed865d by Andy Getzendanner : btree: fix sign-compare warnings Import of https://github.com/abseil/abseil-cpp/pull/800 PiperOrigin-RevId: 334668397 -- 3b1f289781e4c68e244a7534f95eb0719ca1e8e1 by Abseil Team : Avoid iterating past the end of either container in absl::c_transform. The API for the two-range absl::c_transform is misleading as it doesn't check the bounds of the second range against the first one. This commit cleans up the internals of the overload to make sure that buggy calls are not exploitable; non-buggy calls are unaffected. This is consistent with C++20 ranges (see http://wg21.link/alg.transform). PiperOrigin-RevId: 334629614 -- 1184d9c2e7031860638b709c489cbd1b0d861040 by Abseil Team : Avoid iterating past the end of either container in absl::c_swap_ranges. The API for absl::c_swap_ranges is misleading as it doesn't check the bounds of the second range against the first one. This commit cleans up the internals of the overload to make sure that buggy calls are not exploitable; non-buggy calls are unaffected. This is consistent with C++20 ranges (see http://wg21.link/alg.swap). PiperOrigin-RevId: 334618454 GitOrigin-RevId: 0674e1ab1c1f71c5362b9e2337333e67f7ed865d Change-Id: Ifac0e99b1209bb7589bf74215b1d354dd30eabaa --- absl/algorithm/container.h | 33 ++++++++++++++++++++++++--------- absl/algorithm/container_test.cc | 23 +++++++++++++++++++++++ 2 files changed, 47 insertions(+), 9 deletions(-) (limited to 'absl/algorithm') diff --git a/absl/algorithm/container.h b/absl/algorithm/container.h index 2457d78b..5c033571 100644 --- a/absl/algorithm/container.h +++ b/absl/algorithm/container.h @@ -539,12 +539,20 @@ BidirectionalIterator c_move_backward(C&& src, BidirectionalIterator dest) { // c_swap_ranges() // // Container-based version of the `std::swap_ranges()` function to -// swap a container's elements with another container's elements. +// swap a container's elements with another container's elements. Swaps the +// first N elements of `c1` and `c2`, where N = min(size(c1), size(c2)). template container_algorithm_internal::ContainerIter c_swap_ranges(C1& c1, C2& c2) { - return std::swap_ranges(container_algorithm_internal::c_begin(c1), - container_algorithm_internal::c_end(c1), - container_algorithm_internal::c_begin(c2)); + auto first1 = container_algorithm_internal::c_begin(c1); + auto last1 = container_algorithm_internal::c_end(c1); + auto first2 = container_algorithm_internal::c_begin(c2); + auto last2 = container_algorithm_internal::c_end(c2); + + using std::swap; + for (; first1 != last1 && first2 != last2; ++first1, (void)++first2) { + swap(*first1, *first2); + } + return first2; } // c_transform() @@ -562,16 +570,23 @@ OutputIterator c_transform(const InputSequence& input, OutputIterator output, } // Overload of c_transform() for performing a transformation using a binary -// predicate. +// predicate. Applies `binary_op` to the first N elements of `c1` and `c2`, +// where N = min(size(c1), size(c2)). template OutputIterator c_transform(const InputSequence1& input1, const InputSequence2& input2, OutputIterator output, BinaryOp&& binary_op) { - return std::transform(container_algorithm_internal::c_begin(input1), - container_algorithm_internal::c_end(input1), - container_algorithm_internal::c_begin(input2), output, - std::forward(binary_op)); + auto first1 = container_algorithm_internal::c_begin(input1); + auto last1 = container_algorithm_internal::c_end(input1); + auto first2 = container_algorithm_internal::c_begin(input2); + auto last2 = container_algorithm_internal::c_end(input2); + for (; first1 != last1 && first2 != last2; + ++first1, (void)++first2, ++output) { + *output = binary_op(*first1, *first2); + } + + return output; } // c_replace() diff --git a/absl/algorithm/container_test.cc b/absl/algorithm/container_test.cc index 0a4abe94..3abf5cea 100644 --- a/absl/algorithm/container_test.cc +++ b/absl/algorithm/container_test.cc @@ -676,6 +676,15 @@ TEST(MutatingTest, SwapRanges) { absl::c_swap_ranges(odds, evens); EXPECT_THAT(odds, ElementsAre(1, 3, 5)); EXPECT_THAT(evens, ElementsAre(2, 4, 6)); + + odds.pop_back(); + absl::c_swap_ranges(odds, evens); + EXPECT_THAT(odds, ElementsAre(2, 4)); + EXPECT_THAT(evens, ElementsAre(1, 3, 6)); + + absl::c_swap_ranges(evens, odds); + EXPECT_THAT(odds, ElementsAre(1, 3)); + EXPECT_THAT(evens, ElementsAre(2, 4, 6)); } TEST_F(NonMutatingTest, Transform) { @@ -690,6 +699,20 @@ TEST_F(NonMutatingTest, Transform) { EXPECT_EQ(std::vector({1, 5, 4}), z); *end = 7; EXPECT_EQ(std::vector({1, 5, 4, 7}), z); + + z.clear(); + y.pop_back(); + end = absl::c_transform(x, y, std::back_inserter(z), std::plus()); + EXPECT_EQ(std::vector({1, 5}), z); + *end = 7; + EXPECT_EQ(std::vector({1, 5, 7}), z); + + z.clear(); + std::swap(x, y); + end = absl::c_transform(x, y, std::back_inserter(z), std::plus()); + EXPECT_EQ(std::vector({1, 5}), z); + *end = 7; + EXPECT_EQ(std::vector({1, 5, 7}), z); } TEST(MutatingTest, Replace) { -- cgit v1.2.3