Export of internal Abseil changes

--
0674e1ab1c1f71c5362b9e2337333e67f7ed865d by Andy Getzendanner <durandal@google.com>:

btree: fix sign-compare warnings

Import of https://github.com/abseil/abseil-cpp/pull/800

PiperOrigin-RevId: 334668397

--
3b1f289781e4c68e244a7534f95eb0719ca1e8e1 by Abseil Team <absl-team@google.com>:

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 <absl-team@google.com>:

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

2 files changed, 47 insertions, 9 deletions

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 <algorithm> `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 <typename C1, typename C2>
 container_algorithm_internal::ContainerIter<C2> 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 <typename InputSequence1, typename InputSequence2,
           typename OutputIterator, typename BinaryOp>
 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<BinaryOp>(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<int>({1, 5, 4}), z);
   *end = 7;
   EXPECT_EQ(std::vector<int>({1, 5, 4, 7}), z);
+
+  z.clear();
+  y.pop_back();
+  end = absl::c_transform(x, y, std::back_inserter(z), std::plus<int>());
+  EXPECT_EQ(std::vector<int>({1, 5}), z);
+  *end = 7;
+  EXPECT_EQ(std::vector<int>({1, 5, 7}), z);
+
+  z.clear();
+  std::swap(x, y);
+  end = absl::c_transform(x, y, std::back_inserter(z), std::plus<int>());
+  EXPECT_EQ(std::vector<int>({1, 5}), z);
+  *end = 7;
+  EXPECT_EQ(std::vector<int>({1, 5, 7}), z);
 }
 
 TEST(MutatingTest, Replace) {