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

6 files changed, 115 insertions, 95 deletions

diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc
index 4a495067..9b1b6436 100644
--- a/absl/container/btree_test.cc
+++ b/absl/container/btree_test.cc
@@ -2680,6 +2680,12 @@ struct MultiKey {
   int i2;
 };
 
+bool operator==(const MultiKey a, const MultiKey b) {
+  return a.i1 == b.i1 && a.i2 == b.i2;
+}
+
+// A heterogeneous comparator that has different equivalence classes for
+// different lookup types.
 struct MultiKeyComp {
   using is_transparent = void;
   bool operator()(const MultiKey a, const MultiKey b) const {
@@ -2690,8 +2696,6 @@ struct MultiKeyComp {
   bool operator()(const MultiKey a, const int b) const { return a.i1 < b; }
 };
 
-// Test that when there's a heterogeneous comparator that behaves differently
-// for some heterogeneous operators, we get equal_range() right.
 TEST(Btree, MultiKeyEqualRange) {
   absl::btree_set<MultiKey, MultiKeyComp> set;
 
@@ -2709,6 +2713,19 @@ TEST(Btree, MultiKeyEqualRange) {
   }
 }
 
+TEST(Btree, MultiKeyErase) {
+  absl::btree_set<MultiKey, MultiKeyComp> set = {
+      {1, 1}, {2, 1}, {2, 2}, {3, 1}};
+  EXPECT_EQ(set.erase(2), 2);
+  EXPECT_THAT(set, ElementsAre(MultiKey{1, 1}, MultiKey{3, 1}));
+}
+
+TEST(Btree, MultiKeyCount) {
+  const absl::btree_set<MultiKey, MultiKeyComp> set = {
+      {1, 1}, {2, 1}, {2, 2}, {3, 1}};
+  EXPECT_EQ(set.count(2), 2);
+}
+
 TEST(Btree, AllocConstructor) {
   using Alloc = CountingAllocator<int>;
   using Set = absl::btree_set<int, std::less<int>, Alloc>;
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index 8547d68e..f2fc31df 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -423,6 +423,7 @@ struct SearchResult {
 // useful information.
 template <typename V>
 struct SearchResult<V, false> {
+  SearchResult() {}
   explicit SearchResult(V value) : value(value) {}
   SearchResult(V value, MatchKind /*match*/) : value(value) {}
 
@@ -1200,11 +1201,11 @@ class btree {
   // Finds the first element whose key is not less than key.
   template <typename K>
   iterator lower_bound(const K &key) {
-    return internal_end(internal_lower_bound(key));
+    return internal_end(internal_lower_bound(key).value);
   }
   template <typename K>
   const_iterator lower_bound(const K &key) const {
-    return internal_end(internal_lower_bound(key));
+    return internal_end(internal_lower_bound(key).value);
   }
 
   // Finds the first element whose key is greater than key.
@@ -1289,16 +1290,6 @@ class btree {
   // to the element after the last erased element.
   std::pair<size_type, iterator> erase_range(iterator begin, iterator end);
 
-  // Erases the specified key from the btree. Returns 1 if an element was
-  // erased and 0 otherwise.
-  template <typename K>
-  size_type erase_unique(const K &key);
-
-  // Erases all of the entries matching the specified key from the
-  // btree. Returns the number of elements erased.
-  template <typename K>
-  size_type erase_multi(const K &key);
-
   // Finds the iterator corresponding to a key or returns end() if the key is
   // not present.
   template <typename K>
@@ -1310,23 +1301,6 @@ class btree {
     return internal_end(internal_find(key));
   }
 
-  // Returns a count of the number of times the key appears in the btree.
-  template <typename K>
-  size_type count_unique(const K &key) const {
-    const iterator begin = internal_find(key);
-    if (begin.node == nullptr) {
-      // The key doesn't exist in the tree.
-      return 0;
-    }
-    return 1;
-  }
-  // Returns a count of the number of times the key appears in the btree.
-  template <typename K>
-  size_type count_multi(const K &key) const {
-    const auto range = equal_range(key);
-    return std::distance(range.first, range.second);
-  }
-
   // Clear the btree, deleting all of the values it contains.
   void clear();
 
@@ -1514,7 +1488,8 @@ class btree {
 
   // Internal routine which implements lower_bound().
   template <typename K>
-  iterator internal_lower_bound(const K &key) const;
+  SearchResult<iterator, is_key_compare_to::value> internal_lower_bound(
+      const K &key) const;
 
   // Internal routine which implements upper_bound().
   template <typename K>
@@ -1918,10 +1893,13 @@ constexpr bool btree<P>::static_assert_validation() {
 template <typename P>
 template <typename K>
 auto btree<P>::equal_range(const K &key) -> std::pair<iterator, iterator> {
-  const iterator lower = lower_bound(key);
-  // TODO(ezb): we should be able to avoid this comparison when there's a
-  // three-way comparator.
-  if (lower == end() || compare_keys(key, lower.key())) return {lower, lower};
+  const SearchResult<iterator, is_key_compare_to::value> res =
+      internal_lower_bound(key);
+  const iterator lower = internal_end(res.value);
+  if (res.HasMatch() ? !res.IsEq()
+                     : lower == end() || compare_keys(key, lower.key())) {
+    return {lower, lower};
+  }
 
   const iterator next = std::next(lower);
   // When the comparator is heterogeneous, we can't assume that comparison with
@@ -1941,7 +1919,7 @@ auto btree<P>::equal_range(const K &key) -> std::pair<iterator, iterator> {
   // Try once more to avoid the call to upper_bound() if there's only one
   // equivalent key. This should prevent all calls to upper_bound() in cases of
   // unique-containers with heterogeneous comparators in which all comparison
-  // operators are equivalent.
+  // operators have the same equivalence classes.
   if (next == end() || compare_keys(key, next.key())) return {lower, next};
 
   // In this case, we need to call upper_bound() to avoid worst case O(N)
@@ -2226,31 +2204,6 @@ auto btree<P>::erase_range(iterator begin, iterator end)
 }
 
 template <typename P>
-template <typename K>
-auto btree<P>::erase_unique(const K &key) -> size_type {
-  const iterator iter = internal_find(key);
-  if (iter.node == nullptr) {
-    // The key doesn't exist in the tree, return nothing done.
-    return 0;
-  }
-  erase(iter);
-  return 1;
-}
-
-template <typename P>
-template <typename K>
-auto btree<P>::erase_multi(const K &key) -> size_type {
-  const iterator begin = internal_lower_bound(key);
-  if (begin.node == nullptr) {
-    // The key doesn't exist in the tree, return nothing done.
-    return 0;
-  }
-  // Delete all of the keys between begin and upper_bound(key).
-  const iterator end = internal_end(internal_upper_bound(key));
-  return erase_range(begin, end).first;
-}
-
-template <typename P>
 void btree<P>::clear() {
   if (!empty()) {
     node_type::clear_and_delete(root(), mutable_allocator());
@@ -2548,16 +2501,24 @@ inline auto btree<P>::internal_locate(const K &key) const
 
 template <typename P>
 template <typename K>
-auto btree<P>::internal_lower_bound(const K &key) const -> iterator {
+auto btree<P>::internal_lower_bound(const K &key) const
+    -> SearchResult<iterator, is_key_compare_to::value> {
   iterator iter(const_cast<node_type *>(root()));
+  SearchResult<int, is_key_compare_to::value> res;
+  bool seen_eq = false;
   for (;;) {
-    iter.position = iter.node->lower_bound(key, key_comp()).value;
+    res = iter.node->lower_bound(key, key_comp());
+    iter.position = res.value;
+    // TODO(ezb): we should be able to terminate early on IsEq() if there can't
+    // be multiple equivalent keys in container for this lookup type.
     if (iter.node->leaf()) {
       break;
     }
+    seen_eq = seen_eq || res.IsEq();
     iter.node = iter.node->child(iter.position);
   }
-  return internal_last(iter);
+  if (res.IsEq()) return {iter, MatchKind::kEq};
+  return {internal_last(iter), seen_eq ? MatchKind::kEq : MatchKind::kNe};
 }
 
 template <typename P>
diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h
index 3792bc21..887eda41 100644
--- a/absl/container/internal/btree_container.h
+++ b/absl/container/internal/btree_container.h
@@ -104,6 +104,11 @@ class btree_container {
 
   // Lookup routines.
   template <typename K = key_type>
+  size_type count(const key_arg<K> &key) const {
+    auto equal_range = this->equal_range(key);
+    return std::distance(equal_range.first, equal_range.second);
+  }
+  template <typename K = key_type>
   iterator find(const key_arg<K> &key) {
     return tree_.find(key);
   }
@@ -152,6 +157,11 @@ class btree_container {
   iterator erase(const_iterator first, const_iterator last) {
     return tree_.erase_range(iterator(first), iterator(last)).second;
   }
+  template <typename K = key_type>
+  size_type erase(const key_arg<K> &key) {
+    auto equal_range = this->equal_range(key);
+    return tree_.erase_range(equal_range.first, equal_range.second).first;
+  }
 
   // Extract routines.
   node_type extract(iterator position) {
@@ -270,12 +280,6 @@ class btree_set_container : public btree_container<Tree> {
                       const allocator_type &alloc)
       : btree_set_container(init.begin(), init.end(), alloc) {}
 
-  // Lookup routines.
-  template <typename K = key_type>
-  size_type count(const key_arg<K> &key) const {
-    return this->tree_.count_unique(key);
-  }
-
   // Insertion routines.
   std::pair<iterator, bool> insert(const value_type &v) {
     return this->tree_.insert_unique(params_type::key(v), v);
@@ -333,16 +337,10 @@ class btree_set_container : public btree_container<Tree> {
     return res.first;
   }
 
-  // Deletion routines.
-  // TODO(ezb): we should support heterogeneous comparators that have different
-  // behavior for K!=key_type.
-  template <typename K = key_type>
-  size_type erase(const key_arg<K> &key) {
-    return this->tree_.erase_unique(key);
-  }
-  using super_type::erase;
-
   // Node extraction routines.
+  // TODO(ezb): when the comparator is heterogeneous and has different
+  // equivalence classes for different lookup types, we should extract the first
+  // equivalent value if there are multiple.
   template <typename K = key_type>
   node_type extract(const key_arg<K> &key) {
     auto it = this->find(key);
@@ -578,12 +576,6 @@ class btree_multiset_container : public btree_container<Tree> {
                            const allocator_type &alloc)
       : btree_multiset_container(init.begin(), init.end(), alloc) {}
 
-  // Lookup routines.
-  template <typename K = key_type>
-  size_type count(const key_arg<K> &key) const {
-    return this->tree_.count_multi(key);
-  }
-
   // Insertion routines.
   iterator insert(const value_type &v) { return this->tree_.insert_multi(v); }
   iterator insert(value_type &&v) {
@@ -628,14 +620,9 @@ class btree_multiset_container : public btree_container<Tree> {
     return res;
   }
 
-  // Deletion routines.
-  template <typename K = key_type>
-  size_type erase(const key_arg<K> &key) {
-    return this->tree_.erase_multi(key);
-  }
-  using super_type::erase;
-
   // Node extraction routines.
+  // TODO(ezb): we are supposed to extract the first equivalent key if there are
+  // multiple, but this isn't guaranteed to extract the first one.
   template <typename K = key_type>
   node_type extract(const key_arg<K> &key) {
     auto it = this->find(key);
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) {
diff --git a/ci/cmake_common.sh b/ci/cmake_common.sh
index 15ffde2e..aec8a117 100755
--- a/ci/cmake_common.sh
+++ b/ci/cmake_common.sh
@@ -17,7 +17,7 @@
 readonly ABSL_GOOGLETEST_COMMIT="8567b09290fe402cf01923e2131c5635b8ed851b"
 
 # Avoid depending on GitHub by looking for a cached copy of the commit first.
-if [[ -r "${KOKORO_GFILE_DIR}/distdir/${ABSL_GOOGLETEST_COMMIT}.zip" ]]; then
+if [[ -r "${KOKORO_GFILE_DIR:-}/distdir/${ABSL_GOOGLETEST_COMMIT}.zip" ]]; then
   DOCKER_EXTRA_ARGS="--mount type=bind,source=${KOKORO_GFILE_DIR}/distdir,target=/distdir,readonly ${DOCKER_EXTRA_ARGS:-}"
   ABSL_GOOGLETEST_DOWNLOAD_URL="file:///distdir/${ABSL_GOOGLETEST_COMMIT}.zip"
 else
diff --git a/ci/linux_docker_containers.sh b/ci/linux_docker_containers.sh
index afad301e..1c29d9a1 100644
--- a/ci/linux_docker_containers.sh
+++ b/ci/linux_docker_containers.sh
@@ -15,7 +15,7 @@
 # The file contains Docker container identifiers currently used by test scripts.
 # Test scripts should source this file to get the identifiers.
 
-readonly LINUX_ALPINE_CONTAINER="gcr.io/google.com/absl-177019/alpine:20191016"
+readonly LINUX_ALPINE_CONTAINER="gcr.io/google.com/absl-177019/alpine:20201026"
 readonly LINUX_CLANG_LATEST_CONTAINER="gcr.io/google.com/absl-177019/linux_hybrid-latest:20201008"
 readonly LINUX_GCC_LATEST_CONTAINER="gcr.io/google.com/absl-177019/linux_hybrid-latest:20201008"
 readonly LINUX_GCC_FLOOR_CONTAINER="gcr.io/google.com/absl-177019/linux_gcc-floor:20201015"