Export of internal Abseil changes

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

Update Abseil dependency versions

PiperOrigin-RevId: 374415690

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

Fix the install test project, which is doing a mixed-mode build.
This manifests in failure with GCC 11, which defaults to C++17

Also explicitly reference python3 in the test script.
python2 is being removed by some Linux distros.

PiperOrigin-RevId: 374278107

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

Use `capacity + Group::kWidth` control bytes instead of `capacity + Group::kWidth + 1`.

We don't use the extra byte - we only need the first `capacity` ones that are valid, the one sentinel byte and then `Group::kWidth - 1` cloned control bytes. For example, in `EmptyGroup()`, where capacity is 0, we use `Group::kWidth` control bytes.

We need to update set_ctrl() to only mirror `Group::kWidth - 1` bytes instead of `Group::kWidth` bytes.

Note: this doesn't actually save memory unless `alignof(value_type)` is one.

Also add/update related comments.

PiperOrigin-RevId: 374198589

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

Improve b-tree value_comp() support.

- Don't expose internal adapted comparator functionality.
- Support value_comp() for maps using function pointer comparators.
- For maps, make value_compare's constructor and the member comparator be protected - [reference](https://en.cppreference.com/w/cpp/container/map/value_compare).

PiperOrigin-RevId: 373832649

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

Don't export adapted comparator functionality in key_comp().

PiperOrigin-RevId: 373651039
GitOrigin-RevId: 30af50146f07d7afdb196abf235f44ec44ea6409
Change-Id: I260480b0923cefeba81c543e2b7c34cacaa7d7c7

4 files changed, 73 insertions, 36 deletions

diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc
index 464dabac..d5d79151 100644
--- a/absl/container/btree_test.cc
+++ b/absl/container/btree_test.cc
@@ -1708,10 +1708,25 @@ TEST(Btree, StrSplitCompatible) {
   EXPECT_EQ(split_set, expected_set);
 }
 
-// We can't use EXPECT_EQ/etc. to compare absl::weak_ordering because they
-// convert literal 0 to int and absl::weak_ordering can only be compared with
-// literal 0. Defining this function allows for avoiding ClangTidy warnings.
-bool Identity(const bool b) { return b; }
+TEST(Btree, KeyComp) {
+  absl::btree_set<int> s;
+  EXPECT_TRUE(s.key_comp()(1, 2));
+  EXPECT_FALSE(s.key_comp()(2, 2));
+  EXPECT_FALSE(s.key_comp()(2, 1));
+
+  absl::btree_map<int, int> m1;
+  EXPECT_TRUE(m1.key_comp()(1, 2));
+  EXPECT_FALSE(m1.key_comp()(2, 2));
+  EXPECT_FALSE(m1.key_comp()(2, 1));
+
+  // Even though we internally adapt the comparator of `m2` to be three-way and
+  // heterogeneous, the comparator we expose through key_comp() is the original
+  // unadapted comparator.
+  absl::btree_map<std::string, int> m2;
+  EXPECT_TRUE(m2.key_comp()("a", "b"));
+  EXPECT_FALSE(m2.key_comp()("b", "b"));
+  EXPECT_FALSE(m2.key_comp()("b", "a"));
+}
 
 TEST(Btree, ValueComp) {
   absl::btree_set<int> s;
@@ -1724,13 +1739,13 @@ TEST(Btree, ValueComp) {
   EXPECT_FALSE(m1.value_comp()(std::make_pair(2, 0), std::make_pair(2, 0)));
   EXPECT_FALSE(m1.value_comp()(std::make_pair(2, 0), std::make_pair(1, 0)));
 
+  // Even though we internally adapt the comparator of `m2` to be three-way and
+  // heterogeneous, the comparator we expose through value_comp() is based on
+  // the original unadapted comparator.
   absl::btree_map<std::string, int> m2;
-  EXPECT_TRUE(Identity(
-      m2.value_comp()(std::make_pair("a", 0), std::make_pair("b", 0)) < 0));
-  EXPECT_TRUE(Identity(
-      m2.value_comp()(std::make_pair("b", 0), std::make_pair("b", 0)) == 0));
-  EXPECT_TRUE(Identity(
-      m2.value_comp()(std::make_pair("b", 0), std::make_pair("a", 0)) > 0));
+  EXPECT_TRUE(m2.value_comp()(std::make_pair("a", 0), std::make_pair("b", 0)));
+  EXPECT_FALSE(m2.value_comp()(std::make_pair("b", 0), std::make_pair("b", 0)));
+  EXPECT_FALSE(m2.value_comp()(std::make_pair("b", 0), std::make_pair("a", 0)));
 }
 
 TEST(Btree, DefaultConstruction) {
@@ -2906,8 +2921,7 @@ TEST(Btree, SupportsFunctionPtrComparator) {
   map[1] = 1;
   EXPECT_THAT(map, ElementsAre(Pair(1, 1)));
   EXPECT_TRUE(map.key_comp()(1, 2));
-  // TODO(ezb): support value_comp() in this case and uncomment.
-  // EXPECT_TRUE(map.value_comp()(std::make_pair(1, 1), std::make_pair(2, 2)));
+  EXPECT_TRUE(map.value_comp()(std::make_pair(1, 1), std::make_pair(2, 2)));
 }
 
 template <typename Compare>
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index d372a1d6..f636c5fc 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -88,7 +88,12 @@ struct StringBtreeDefaultLess {
 
   // Compatibility constructor.
   StringBtreeDefaultLess(std::less<std::string>) {}  // NOLINT
-  StringBtreeDefaultLess(std::less<string_view>) {}  // NOLINT
+  StringBtreeDefaultLess(std::less<absl::string_view>) {}  // NOLINT
+
+  // Allow converting to std::less for use in key_comp()/value_comp().
+  explicit operator std::less<std::string>() const { return {}; }
+  explicit operator std::less<absl::string_view>() const { return {}; }
+  explicit operator std::less<absl::Cord>() const { return {}; }
 
   absl::weak_ordering operator()(absl::string_view lhs,
                                  absl::string_view rhs) const {
@@ -115,7 +120,12 @@ struct StringBtreeDefaultGreater {
   StringBtreeDefaultGreater() = default;
 
   StringBtreeDefaultGreater(std::greater<std::string>) {}  // NOLINT
-  StringBtreeDefaultGreater(std::greater<string_view>) {}  // NOLINT
+  StringBtreeDefaultGreater(std::greater<absl::string_view>) {}  // NOLINT
+
+  // Allow converting to std::greater for use in key_comp()/value_comp().
+  explicit operator std::greater<std::string>() const { return {}; }
+  explicit operator std::greater<absl::string_view>() const { return {}; }
+  explicit operator std::greater<absl::Cord>() const { return {}; }
 
   absl::weak_ordering operator()(absl::string_view lhs,
                                  absl::string_view rhs) const {
@@ -217,6 +227,8 @@ struct prefers_linear_node_search<
 template <typename Key, typename Compare, typename Alloc, int TargetNodeSize,
           bool Multi, typename SlotPolicy>
 struct common_params {
+  using original_key_compare = Compare;
+
   // If Compare is a common comparator for a string-like type, then we adapt it
   // to use heterogeneous lookup and to be a key-compare-to comparator.
   using key_compare = typename key_compare_to_adapter<Compare>::type;
@@ -317,16 +329,21 @@ struct map_params : common_params<Key, Compare, Alloc, TargetNodeSize, Multi,
   using value_type = typename super_type::value_type;
   using init_type = typename super_type::init_type;
 
-  using key_compare = typename super_type::key_compare;
-  // Inherit from key_compare for empty base class optimization.
-  struct value_compare : private key_compare {
-    value_compare() = default;
-    explicit value_compare(const key_compare &cmp) : key_compare(cmp) {}
+  using original_key_compare = typename super_type::original_key_compare;
+  // Reference: https://en.cppreference.com/w/cpp/container/map/value_compare
+  class value_compare {
+    template <typename Params>
+    friend class btree;
 
-    template <typename T, typename U>
-    auto operator()(const T &left, const U &right) const
-        -> decltype(std::declval<key_compare>()(left.first, right.first)) {
-      return key_compare::operator()(left.first, right.first);
+   protected:
+    explicit value_compare(original_key_compare c) : comp(std::move(c)) {}
+
+    original_key_compare comp;  // NOLINT
+
+   public:
+    auto operator()(const value_type &lhs, const value_type &rhs) const
+        -> decltype(comp(lhs.first, rhs.first)) {
+      return comp(lhs.first, rhs.first);
     }
   };
   using is_map_container = std::true_type;
@@ -392,7 +409,8 @@ struct set_params : common_params<Key, Compare, Alloc, TargetNodeSize, Multi,
                                   set_slot_policy<Key>> {
   using value_type = Key;
   using slot_type = typename set_params::common_params::slot_type;
-  using value_compare = typename set_params::common_params::key_compare;
+  using value_compare =
+      typename set_params::common_params::original_key_compare;
   using is_map_container = std::false_type;
 
   template <typename V>
@@ -1129,6 +1147,7 @@ class btree {
   using size_type = typename Params::size_type;
   using difference_type = typename Params::difference_type;
   using key_compare = typename Params::key_compare;
+  using original_key_compare = typename Params::original_key_compare;
   using value_compare = typename Params::value_compare;
   using allocator_type = typename Params::allocator_type;
   using reference = typename Params::reference;
@@ -1338,7 +1357,9 @@ class btree {
     return compare_internal::compare_result_as_less_than(key_comp()(a, b));
   }
 
-  value_compare value_comp() const { return value_compare(key_comp()); }
+  value_compare value_comp() const {
+    return value_compare(original_key_compare(key_comp()));
+  }
 
   // Verifies the structure of the btree.
   void verify() const;
diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h
index 03be708e..4f5d56dd 100644
--- a/absl/container/internal/btree_container.h
+++ b/absl/container/internal/btree_container.h
@@ -51,7 +51,7 @@ class btree_container {
   using value_type = typename Tree::value_type;
   using size_type = typename Tree::size_type;
   using difference_type = typename Tree::difference_type;
-  using key_compare = typename Tree::key_compare;
+  using key_compare = typename Tree::original_key_compare;
   using value_compare = typename Tree::value_compare;
   using allocator_type = typename Tree::allocator_type;
   using reference = typename Tree::reference;
@@ -214,7 +214,7 @@ class btree_container {
   allocator_type get_allocator() const { return tree_.get_allocator(); }
 
   // The key comparator used by the btree.
-  key_compare key_comp() const { return tree_.key_comp(); }
+  key_compare key_comp() const { return key_compare(tree_.key_comp()); }
   value_compare value_comp() const { return tree_.value_comp(); }
 
   // Support absl::Hash.
@@ -247,7 +247,7 @@ class btree_set_container : public btree_container<Tree> {
   using key_type = typename Tree::key_type;
   using value_type = typename Tree::value_type;
   using size_type = typename Tree::size_type;
-  using key_compare = typename Tree::key_compare;
+  using key_compare = typename Tree::original_key_compare;
   using allocator_type = typename Tree::allocator_type;
   using iterator = typename Tree::iterator;
   using const_iterator = typename Tree::const_iterator;
@@ -398,7 +398,7 @@ class btree_map_container : public btree_set_container<Tree> {
   using key_type = typename Tree::key_type;
   using mapped_type = typename params_type::mapped_type;
   using value_type = typename Tree::value_type;
-  using key_compare = typename Tree::key_compare;
+  using key_compare = typename Tree::original_key_compare;
   using allocator_type = typename Tree::allocator_type;
   using iterator = typename Tree::iterator;
   using const_iterator = typename Tree::const_iterator;
@@ -543,7 +543,7 @@ class btree_multiset_container : public btree_container<Tree> {
   using key_type = typename Tree::key_type;
   using value_type = typename Tree::value_type;
   using size_type = typename Tree::size_type;
-  using key_compare = typename Tree::key_compare;
+  using key_compare = typename Tree::original_key_compare;
   using allocator_type = typename Tree::allocator_type;
   using iterator = typename Tree::iterator;
   using const_iterator = typename Tree::const_iterator;
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index b23e0078..669785e6 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -628,7 +628,9 @@ class raw_hash_set {
 
   static Layout MakeLayout(size_t capacity) {
     assert(IsValidCapacity(capacity));
-    return Layout(capacity + Group::kWidth + 1, capacity);
+    // The extra control bytes are for 1 sentinel byte followed by
+    // `Group::kWidth - 1` bytes that are cloned from the beginning.
+    return Layout(capacity + Group::kWidth, capacity);
   }
 
   using AllocTraits = absl::allocator_traits<allocator_type>;
@@ -1782,8 +1784,8 @@ class raw_hash_set {
     growth_left() = CapacityToGrowth(capacity()) - size_;
   }
 
-  // Sets the control byte, and if `i < Group::kWidth`, set the cloned byte at
-  // the end too.
+  // Sets the control byte, and if `i < Group::kWidth - 1`, set the cloned byte
+  // at the end too.
   void set_ctrl(size_t i, ctrl_t h) {
     assert(i < capacity_);
 
@@ -1794,8 +1796,8 @@ class raw_hash_set {
     }
 
     ctrl_[i] = h;
-    ctrl_[((i - Group::kWidth) & capacity_) + 1 +
-          ((Group::kWidth - 1) & capacity_)] = h;
+    constexpr size_t kClonedBytes = Group::kWidth - 1;
+    ctrl_[((i - kClonedBytes) & capacity_) + (kClonedBytes & capacity_)] = h;
   }
 
   size_t& growth_left() { return settings_.template get<0>(); }
@@ -1814,7 +1816,7 @@ class raw_hash_set {
   // TODO(alkis): Investigate removing some of these fields:
   // - ctrl/slots can be derived from each other
   // - size can be moved into the slot array
-  ctrl_t* ctrl_ = EmptyGroup();    // [(capacity + 1) * ctrl_t]
+  ctrl_t* ctrl_ = EmptyGroup();    // [(capacity + Group::kWidth) * ctrl_t]
   slot_type* slots_ = nullptr;     // [capacity * slot_type]
   size_t size_ = 0;                // number of full slots
   size_t capacity_ = 0;            // total number of slots