Export of internal Abseil changes

--
e5b45b15c19e85aaa33430ac2bd45fcc2e52dad5 by Greg Falcon <gfalcon@google.com>:

Add extra tests exercising ShiftLeft() at boundary conditions, to guard against logic errors in our memory bounds checking.

PiperOrigin-RevId: 339326030

--
cdfde78815ca016a57f90f53d08c3335bd355f30 by Evan Brown <ezb@google.com>:

Fix a bug in b-tree erase() and count() in which we weren't accounting for cases where the comparator is heterogeneous and has different equivalence classes for different lookup types.

Optimize equal_range to avoid comparisons when possible.

PiperOrigin-RevId: 339270230

--
b4aa337c156fa91f74f25c676c679ae146311968 by Derek Mauro <dmauro@google.com>:

Fix execution of the cmake build scripts when not on Kokoro

PiperOrigin-RevId: 339131253

--
fa3d1f602f711be72fde6b5f29d6341b9b5f8a2c by Derek Mauro <dmauro@google.com>:

Update Docker container used for Alpine Linux testing

PiperOrigin-RevId: 339074246
GitOrigin-RevId: e5b45b15c19e85aaa33430ac2bd45fcc2e52dad5
Change-Id: I2cc3adc4de3493203c8a944aedee40efa54af0c0

1 files changed, 55 insertions, 0 deletions

diff --git a/absl/strings/internal/charconv_bigint_test.cc b/absl/strings/internal/charconv_bigint_test.cc
index 363bcb03..a8b99458 100644
--- a/absl/strings/internal/charconv_bigint_test.cc
+++ b/absl/strings/internal/charconv_bigint_test.cc
@@ -69,6 +69,61 @@ TEST(BigUnsigned, ShiftLeft) {
     // And we should have fully rotated all bits off by now:
     EXPECT_EQ(a, BigUnsigned<84>(0u));
   }
+  {
+    // Bit shifting large and small numbers by large and small offsets.
+    // Intended to exercise bounds-checking corner on ShiftLeft() (directly
+    // and under asan).
+
+    // 2**(32*84)-1
+    const BigUnsigned<84> all_bits_one(
+        "1474444211396924248063325089479706787923460402125687709454567433186613"
+        "6228083464060749874845919674257665016359189106695900028098437021384227"
+        "3285029708032466536084583113729486015826557532750465299832071590813090"
+        "2011853039837649252477307070509704043541368002938784757296893793903797"
+        "8180292336310543540677175225040919704702800559606097685920595947397024"
+        "8303316808753252115729411497720357971050627997031988036134171378490368"
+        "6008000778741115399296162550786288457245180872759047016734959330367829"
+        "5235612397427686310674725251378116268607113017720538636924549612987647"
+        "5767411074510311386444547332882472126067840027882117834454260409440463"
+        "9345147252664893456053258463203120637089916304618696601333953616715125"
+        "2115882482473279040772264257431663818610405673876655957323083702713344"
+        "4201105427930770976052393421467136557055");
+    const BigUnsigned<84> zero(0u);
+    const BigUnsigned<84> one(1u);
+    // in bounds shifts
+    for (int i = 1; i < 84*32; ++i) {
+      // shifting all_bits_one to the left should result in a smaller number,
+      // since the high bits rotate off and the low bits are replaced with
+      // zeroes.
+      BigUnsigned<84> big_shifted = all_bits_one;
+      big_shifted.ShiftLeft(i);
+      EXPECT_GT(all_bits_one, big_shifted);
+      // Shifting 1 to the left should instead result in a larger number.
+      BigUnsigned<84> small_shifted = one;
+      small_shifted.ShiftLeft(i);
+      EXPECT_LT(one, small_shifted);
+    }
+    // Shifting by zero or a negative number has no effect
+    for (int no_op_shift : {0, -1, -84 * 32, std::numeric_limits<int>::min()}) {
+      BigUnsigned<84> big_shifted = all_bits_one;
+      big_shifted.ShiftLeft(no_op_shift);
+      EXPECT_EQ(all_bits_one, big_shifted);
+      BigUnsigned<84> small_shifted = one;
+      big_shifted.ShiftLeft(no_op_shift);
+      EXPECT_EQ(one, small_shifted);
+    }
+    // Shifting by an amount greater than the number of bits should result in
+    // zero.
+    for (int out_of_bounds_shift :
+         {84 * 32, 84 * 32 + 1, std::numeric_limits<int>::max()}) {
+      BigUnsigned<84> big_shifted = all_bits_one;
+      big_shifted.ShiftLeft(out_of_bounds_shift);
+      EXPECT_EQ(zero, big_shifted);
+      BigUnsigned<84> small_shifted = one;
+      small_shifted.ShiftLeft(out_of_bounds_shift);
+      EXPECT_EQ(zero, small_shifted);
+    }
+  }
 }
 
 TEST(BigUnsigned, MultiplyByUint32) {