Export of internal Abseil changes

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

Internal change

PiperOrigin-RevId: 430442277

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

Small refactoring to work towards allowing for node_btree_* containers.

- Change common_params::transfer to rely on slot_policy transfer instead of manually doing construct/destruct. Transfer is not construct/destruct for node containers.
- Move maps' value_compare into btree.h from btree_map.h so it can be reused for node_btree_map.h.
- Also add a test for maps' value_compare protected members.

PiperOrigin-RevId: 430245542

--
0126e0b6295342317d9c9f0a66e2d7009b858426 by Martijn Vels <mvels@google.com>:

Add CordRepSubString::Create function with hard checks on IsFlat() | IsExternal()

This hardens internal invariants, IsFlat() || IsExternal() is a cheap, single predicted branch, and removes boilerplate code from cord.cc

PiperOrigin-RevId: 429676041

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

tweaks to status.h documentation to reflect general-purpose communication

PiperOrigin-RevId: 429584104
GitOrigin-RevId: 91d76b3ac9edff91f206d9eee60423c39eeeaf93
Change-Id: I54d6d116a564f86a842b983ca76559bf9b388f72

9 files changed, 129 insertions, 101 deletions

diff --git a/absl/container/btree_map.h b/absl/container/btree_map.h
index ad484ce0..286817f1 100644
--- a/absl/container/btree_map.h
+++ b/absl/container/btree_map.h
@@ -59,7 +59,7 @@ ABSL_NAMESPACE_BEGIN
 namespace container_internal {
 
 template <typename Key, typename Data, typename Compare, typename Alloc,
-          int TargetNodeSize, bool Multi>
+          int TargetNodeSize, bool IsMulti>
 struct map_params;
 
 }  // namespace container_internal
@@ -85,7 +85,7 @@ class btree_map
     : public container_internal::btree_map_container<
           container_internal::btree<container_internal::map_params<
               Key, Value, Compare, Alloc, /*TargetNodeSize=*/256,
-              /*Multi=*/false>>> {
+              /*IsMulti=*/false>>> {
   using Base = typename btree_map::btree_map_container;
 
  public:
@@ -507,7 +507,7 @@ class btree_multimap
     : public container_internal::btree_multimap_container<
           container_internal::btree<container_internal::map_params<
               Key, Value, Compare, Alloc, /*TargetNodeSize=*/256,
-              /*Multi=*/true>>> {
+              /*IsMulti=*/true>>> {
   using Base = typename btree_multimap::btree_multimap_container;
 
  public:
@@ -817,9 +817,9 @@ namespace container_internal {
 // A parameters structure for holding the type parameters for a btree_map.
 // Compare and Alloc should be nothrow copy-constructible.
 template <typename Key, typename Data, typename Compare, typename Alloc,
-          int TargetNodeSize, bool Multi>
-struct map_params : common_params<Key, Compare, Alloc, TargetNodeSize, Multi,
-                                  map_slot_policy<Key, Data>> {
+          int TargetNodeSize, bool IsMulti>
+struct map_params : common_params<Key, Compare, Alloc, TargetNodeSize, IsMulti,
+                                  /*IsMap=*/true, map_slot_policy<Key, Data>> {
   using super_type = typename map_params::common_params;
   using mapped_type = Data;
   // This type allows us to move keys when it is safe to do so. It is safe
@@ -829,25 +829,6 @@ 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 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;
-
-   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;
-
   template <typename V>
   static auto key(const V &value) -> decltype(value.first) {
     return value.first;
diff --git a/absl/container/btree_set.h b/absl/container/btree_set.h
index 78826830..7b6655ad 100644
--- a/absl/container/btree_set.h
+++ b/absl/container/btree_set.h
@@ -61,7 +61,7 @@ template <typename Key>
 struct set_slot_policy;
 
 template <typename Key, typename Compare, typename Alloc, int TargetNodeSize,
-          bool Multi>
+          bool IsMulti>
 struct set_params;
 
 }  // namespace container_internal
@@ -87,7 +87,7 @@ class btree_set
     : public container_internal::btree_set_container<
           container_internal::btree<container_internal::set_params<
               Key, Compare, Alloc, /*TargetNodeSize=*/256,
-              /*Multi=*/false>>> {
+              /*IsMulti=*/false>>> {
   using Base = typename btree_set::btree_set_container;
 
  public:
@@ -427,7 +427,7 @@ class btree_multiset
     : public container_internal::btree_multiset_container<
           container_internal::btree<container_internal::set_params<
               Key, Compare, Alloc, /*TargetNodeSize=*/256,
-              /*Multi=*/true>>> {
+              /*IsMulti=*/true>>> {
   using Base = typename btree_multiset::btree_multiset_container;
 
  public:
@@ -757,6 +757,12 @@ struct set_slot_policy {
   }
 
   template <typename Alloc>
+  static void transfer(Alloc *alloc, slot_type *new_slot, slot_type *old_slot) {
+    construct(alloc, new_slot, old_slot);
+    destroy(alloc, old_slot);
+  }
+
+  template <typename Alloc>
   static void swap(Alloc * /*alloc*/, slot_type *a, slot_type *b) {
     using std::swap;
     swap(*a, *b);
@@ -771,14 +777,11 @@ struct set_slot_policy {
 // A parameters structure for holding the type parameters for a btree_set.
 // Compare and Alloc should be nothrow copy-constructible.
 template <typename Key, typename Compare, typename Alloc, int TargetNodeSize,
-          bool Multi>
-struct set_params : common_params<Key, Compare, Alloc, TargetNodeSize, Multi,
-                                  set_slot_policy<Key>> {
+          bool IsMulti>
+struct set_params : common_params<Key, Compare, Alloc, TargetNodeSize, IsMulti,
+                                  /*IsMap=*/false, 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::original_key_compare;
-  using is_map_container = std::false_type;
 
   template <typename V>
   static const V &key(const V &value) {
diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc
index e829e0ba..4d4c64b2 100644
--- a/absl/container/btree_test.cc
+++ b/absl/container/btree_test.cc
@@ -1762,6 +1762,22 @@ TEST(Btree, ValueComp) {
   EXPECT_FALSE(m2.value_comp()(std::make_pair("b", 0), std::make_pair("a", 0)));
 }
 
+// Test that we have the protected members from the std::map::value_compare API.
+// See https://en.cppreference.com/w/cpp/container/map/value_compare.
+TEST(Btree, MapValueCompProtected) {
+  struct key_compare {
+    bool operator()(int l, int r) const { return l < r; }
+    int id;
+  };
+  using value_compare = absl::btree_map<int, int, key_compare>::value_compare;
+  struct value_comp_child : public value_compare {
+    explicit value_comp_child(key_compare kc) : value_compare(kc) {}
+    int GetId() const { return comp.id; }
+  };
+  value_comp_child c(key_compare{10});
+  EXPECT_EQ(c.GetId(), 10);
+}
+
 TEST(Btree, DefaultConstruction) {
   absl::btree_set<int> s;
   absl::btree_map<int, int> m;
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index 6c10b00f..a22c9bd7 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -335,8 +335,27 @@ constexpr bool compare_has_valid_result_type() {
          std::is_convertible<compare_result_type, absl::weak_ordering>::value;
 }
 
+template <typename original_key_compare, typename value_type>
+class map_value_compare {
+  template <typename Params>
+  friend class btree;
+
+  // Note: this `protected` is part of the API of std::map::value_compare. See
+  // https://en.cppreference.com/w/cpp/container/map/value_compare.
+ protected:
+  explicit map_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);
+  }
+};
+
 template <typename Key, typename Compare, typename Alloc, int TargetNodeSize,
-          bool Multi, typename SlotPolicy>
+          bool IsMulti, bool IsMap, typename SlotPolicy>
 struct common_params {
   using original_key_compare = Compare;
 
@@ -384,6 +403,12 @@ struct common_params {
   using reference = value_type &;
   using const_reference = const value_type &;
 
+  using value_compare =
+      absl::conditional_t<IsMap,
+                          map_value_compare<original_key_compare, value_type>,
+                          original_key_compare>;
+  using is_map_container = std::integral_constant<bool, IsMap>;
+
   // For the given lookup key type, returns whether we can have multiple
   // equivalent keys in the btree. If this is a multi-container, then we can.
   // Otherwise, we can have multiple equivalent keys only if all of the
@@ -394,9 +419,9 @@ struct common_params {
   //   that we know has the same equivalence classes for all lookup types.
   template <typename LookupKey>
   constexpr static bool can_have_multiple_equivalent_keys() {
-    return Multi || (IsTransparent<key_compare>::value &&
-                     !std::is_same<LookupKey, Key>::value &&
-                     !kIsKeyCompareStringAdapted);
+    return IsMulti || (IsTransparent<key_compare>::value &&
+                       !std::is_same<LookupKey, Key>::value &&
+                       !kIsKeyCompareStringAdapted);
   }
 
   enum {
@@ -435,8 +460,7 @@ struct common_params {
     slot_policy::destroy(alloc, slot);
   }
   static void transfer(Alloc *alloc, slot_type *new_slot, slot_type *old_slot) {
-    construct(alloc, new_slot, old_slot);
-    destroy(alloc, old_slot);
+    slot_policy::transfer(alloc, new_slot, old_slot);
   }
   static void swap(Alloc *alloc, slot_type *a, slot_type *b) {
     slot_policy::swap(alloc, a, b);
diff --git a/absl/status/status.h b/absl/status/status.h
index db4b340a..2d003ce6 100644
--- a/absl/status/status.h
+++ b/absl/status/status.h
@@ -24,11 +24,11 @@
 //   * A set of helper functions for creating status codes and checking their
 //     values
 //
-// Within Google, `absl::Status` is the primary mechanism for gracefully
-// handling errors across API boundaries (and in particular across RPC
-// boundaries). Some of these errors may be recoverable, but others may not.
-// Most functions that can produce a recoverable error should be designed to
-// return an `absl::Status` (or `absl::StatusOr`).
+// Within Google, `absl::Status` is the primary mechanism for communicating
+// errors in C++, and is used to represent error state in both in-process
+// library calls as well as RPC calls. Some of these errors may be recoverable,
+// but others may not. Most functions that can produce a recoverable error
+// should be designed to return an `absl::Status` (or `absl::StatusOr`).
 //
 // Example:
 //
diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc
index 6547c2da..b65dc58b 100644
--- a/absl/strings/cord.cc
+++ b/absl/strings/cord.cc
@@ -151,23 +151,6 @@ void InitializeCordRepExternal(absl::string_view data, CordRepExternal* rep) {
 
 }  // namespace cord_internal
 
-static CordRep* NewSubstring(CordRep* child, size_t offset, size_t length) {
-  // Never create empty substring nodes
-  if (length == 0) {
-    CordRep::Unref(child);
-    return nullptr;
-  } else {
-    CordRepSubstring* rep = new CordRepSubstring();
-    assert(child->IsExternal() || child->IsFlat());
-    assert((offset + length) <= child->length);
-    rep->length = length;
-    rep->tag = cord_internal::SUBSTRING;
-    rep->start = offset;
-    rep->child = child;
-    return VerifyTree(rep);
-  }
-}
-
 // Creates a CordRep from the provided string. If the string is large enough,
 // and not wasteful, we move the string into an external cord rep, preserving
 // the already allocated string contents.
@@ -643,7 +626,7 @@ static CordRep* RemovePrefixFrom(CordRep* node, size_t n) {
       start += node->substring()->start;
       node = node->substring()->child;
     }
-    node = NewSubstring(CordRep::Ref(node), start, len);
+    node = CordRepSubstring::Create(CordRep::Ref(node), start, len);
   }
   while (!rhs_stack.empty()) {
     node = Concat(node, CordRep::Ref(rhs_stack.back()));
@@ -678,7 +661,7 @@ static CordRep* RemoveSuffixFrom(CordRep* node, size_t n) {
       start = node->substring()->start;
       node = node->substring()->child;
     }
-    node = NewSubstring(CordRep::Ref(node), start, len);
+    node = CordRepSubstring::Create(CordRep::Ref(node), start, len);
   }
   while (!lhs_stack.empty()) {
     node = Concat(CordRep::Ref(lhs_stack.back()), node);
@@ -768,7 +751,7 @@ static CordRep* NewSubRange(CordRep* node, size_t pos, size_t n) {
         pos += node->substring()->start;
         node = node->substring()->child;
       }
-      results.push_back(NewSubstring(CordRep::Ref(node), pos, n));
+      results.push_back(CordRepSubstring::Create(CordRep::Ref(node), pos, n));
     }
   } while (!todo.empty());
   assert(results.size() == 1);
@@ -1157,12 +1140,7 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) {
                                            : payload->flat()->Data();
   const size_t offset = current_chunk_.data() - data;
 
-  CordRepSubstring* tree = new CordRepSubstring();
-  tree->tag = cord_internal::SUBSTRING;
-  tree->length = n;
-  tree->start = offset;
-  tree->child = CordRep::Ref(payload);
-
+  auto* tree = CordRepSubstring::Create(CordRep::Ref(payload), offset, n);
   subcord.contents_.EmplaceTree(VerifyTree(tree), method);
   bytes_remaining_ -= n;
   current_chunk_.remove_prefix(n);
diff --git a/absl/strings/cord_test.cc b/absl/strings/cord_test.cc
index 9dcc4ce5..f69209de 100644
--- a/absl/strings/cord_test.cc
+++ b/absl/strings/cord_test.cc
@@ -56,6 +56,7 @@ using absl::cord_internal::CordRepCrc;
 using absl::cord_internal::CordRepExternal;
 using absl::cord_internal::CordRepFlat;
 using absl::cord_internal::CordRepSubstring;
+using absl::cord_internal::CordzUpdateTracker;
 using absl::cord_internal::kFlatOverhead;
 using absl::cord_internal::kMaxFlatLength;
 
@@ -212,14 +213,9 @@ class CordTestPeer {
     ABSL_RAW_CHECK(src.ExpectedChecksum() == absl::nullopt,
                    "Can not be hardened");
     Cord cord;
-    auto* rep = new cord_internal::CordRepSubstring;
-    rep->tag = cord_internal::SUBSTRING;
-    rep->child = cord_internal::CordRep::Ref(
-        cord_internal::SkipCrcNode(src.contents_.tree()));
-    rep->start = offset;
-    rep->length = length;
-    cord.contents_.EmplaceTree(rep,
-                               cord_internal::CordzUpdateTracker::kSubCord);
+    auto* tree = cord_internal::SkipCrcNode(src.contents_.tree());
+    auto* rep = CordRepSubstring::Create(CordRep::Ref(tree), offset, length);
+    cord.contents_.EmplaceTree(rep, CordzUpdateTracker::kSubCord);
     return cord;
   }
 };
@@ -645,15 +641,6 @@ TEST_P(CordTest, TryFlatSubstrExternal) {
   EXPECT_EQ(sub.TryFlat(), "ell");
 }
 
-TEST_P(CordTest, TryFlatSubstrConcat) {
-  absl::Cord c = absl::MakeFragmentedCord({"hello", " world"});
-  absl::Cord sub = absl::CordTestPeer::MakeSubstring(c, 1, c.size() - 1);
-  MaybeHarden(sub);
-  EXPECT_EQ(sub.TryFlat(), absl::nullopt);
-  c.RemovePrefix(1);
-  EXPECT_EQ(c.TryFlat(), absl::nullopt);
-}
-
 TEST_P(CordTest, TryFlatCommonlyAssumedInvariants) {
   // The behavior tested below is not part of the API contract of Cord, but it's
   // something we intend to be true in our current implementation.  This test
diff --git a/absl/strings/internal/cord_internal.cc b/absl/strings/internal/cord_internal.cc
index 06119350..b6b06cfa 100644
--- a/absl/strings/internal/cord_internal.cc
+++ b/absl/strings/internal/cord_internal.cc
@@ -17,11 +17,13 @@
 #include <cassert>
 #include <memory>
 
+#include "absl/base/internal/raw_logging.h"
 #include "absl/container/inlined_vector.h"
 #include "absl/strings/internal/cord_rep_btree.h"
 #include "absl/strings/internal/cord_rep_crc.h"
 #include "absl/strings/internal/cord_rep_flat.h"
 #include "absl/strings/internal/cord_rep_ring.h"
+#include "absl/strings/str_cat.h"
 
 namespace absl {
 ABSL_NAMESPACE_BEGIN
@@ -33,6 +35,11 @@ ABSL_CONST_INIT std::atomic<bool> shallow_subcords_enabled(
     kCordShallowSubcordsDefault);
 ABSL_CONST_INIT std::atomic<bool> cord_btree_exhaustive_validation(false);
 
+void LogFatalNodeType(CordRep* rep) {
+  ABSL_INTERNAL_LOG(FATAL, absl::StrCat("Unexpected node type: ",
+                                        static_cast<int>(rep->tag)));
+}
+
 void CordRep::Destroy(CordRep* rep) {
   assert(rep != nullptr);
 
diff --git a/absl/strings/internal/cord_internal.h b/absl/strings/internal/cord_internal.h
index 8db6aa6d..ece3db15 100644
--- a/absl/strings/internal/cord_internal.h
+++ b/absl/strings/internal/cord_internal.h
@@ -21,6 +21,7 @@
 #include <cstdint>
 #include <type_traits>
 
+#include "absl/base/attributes.h"
 #include "absl/base/config.h"
 #include "absl/base/internal/endian.h"
 #include "absl/base/internal/invoke.h"
@@ -33,6 +34,19 @@ namespace absl {
 ABSL_NAMESPACE_BEGIN
 namespace cord_internal {
 
+// The overhead of a vtable is too much for Cord, so we roll our own subclasses
+// using only a single byte to differentiate classes from each other - the "tag"
+// byte.  Define the subclasses first so we can provide downcasting helper
+// functions in the base class.
+struct CordRep;
+struct CordRepConcat;
+struct CordRepExternal;
+struct CordRepFlat;
+struct CordRepSubstring;
+struct CordRepCrc;
+class CordRepRing;
+class CordRepBtree;
+
 class CordzInfo;
 
 // Default feature enable states for cord ring buffers
@@ -74,6 +88,9 @@ enum Constants {
   kMaxBytesToCopy = 511
 };
 
+// Emits a fatal error "Unexpected node type: xyz" and aborts the program.
+ABSL_ATTRIBUTE_NORETURN void LogFatalNodeType(CordRep* rep);
+
 // Compact class for tracking the reference count and state flags for CordRep
 // instances.  Data is stored in an atomic int32_t for compactness and speed.
 class RefcountAndFlags {
@@ -156,19 +173,6 @@ class RefcountAndFlags {
   std::atomic<int32_t> count_;
 };
 
-// The overhead of a vtable is too much for Cord, so we roll our own subclasses
-// using only a single byte to differentiate classes from each other - the "tag"
-// byte.  Define the subclasses first so we can provide downcasting helper
-// functions in the base class.
-
-struct CordRepConcat;
-struct CordRepExternal;
-struct CordRepFlat;
-struct CordRepSubstring;
-struct CordRepCrc;
-class CordRepRing;
-class CordRepBtree;
-
 // Various representations that we allow
 enum CordRepKind {
   UNUSED_0 = 0,
@@ -276,6 +280,12 @@ struct CordRep {
 struct CordRepSubstring : public CordRep {
   size_t start;  // Starting offset of substring in child
   CordRep* child;
+
+  // Creates a substring on `child`, adopting a reference on `child`.
+  // Requires `child` to be either a flat or external node, and `pos` and `n` to
+  // form a non-empty partial sub range of `'child`, i.e.:
+  // `n > 0 && n < length && n + pos <= length`
+  static inline CordRepSubstring* Create(CordRep* child, size_t pos, size_t n);
 };
 
 // Type for function pointer that will invoke the releaser function and also
@@ -339,6 +349,28 @@ struct CordRepExternalImpl
   }
 };
 
+inline CordRepSubstring* CordRepSubstring::Create(CordRep* child, size_t pos,
+                                                  size_t n) {
+  assert(child != nullptr);
+  assert(n > 0);
+  assert(n < child->length);
+  assert(pos < child->length);
+  assert(n <= child->length - pos);
+
+  // TODO(b/217376272): Harden internal logic.
+  // Move to strategical places inside the Cord logic and make this an assert.
+  if (ABSL_PREDICT_FALSE(!(child->IsExternal() || child->IsFlat()))) {
+    LogFatalNodeType(child);
+  }
+
+  CordRepSubstring* rep = new CordRepSubstring();
+  rep->length = n;
+  rep->tag = SUBSTRING;
+  rep->start = pos;
+  rep->child = child;
+  return rep;
+}
+
 inline void CordRepExternal::Delete(CordRep* rep) {
   assert(rep != nullptr && rep->IsExternal());
   auto* rep_external = static_cast<CordRepExternal*>(rep);