Merge tag '20220623.1-1' into bullseye-backports-staging

1 files changed, 48 insertions, 172 deletions

diff --git a/absl/strings/internal/cord_rep_ring.cc b/absl/strings/internal/cord_rep_ring.cc
index 4d31d1d9..af2fc768 100644
--- a/absl/strings/internal/cord_rep_ring.cc
+++ b/absl/strings/internal/cord_rep_ring.cc
@@ -26,21 +26,13 @@
 #include "absl/base/macros.h"
 #include "absl/container/inlined_vector.h"
 #include "absl/strings/internal/cord_internal.h"
+#include "absl/strings/internal/cord_rep_consume.h"
 #include "absl/strings/internal/cord_rep_flat.h"
 
 namespace absl {
 ABSL_NAMESPACE_BEGIN
 namespace cord_internal {
 
-// See https://bugs.llvm.org/show_bug.cgi?id=48477
-#ifdef __clang__
-#pragma clang diagnostic push
-#pragma clang diagnostic ignored "-Wshadow"
-#if __has_warning("-Wshadow-field")
-#pragma clang diagnostic ignored "-Wshadow-field"
-#endif
-#endif
-
 namespace {
 
 using index_type = CordRepRing::index_type;
@@ -48,7 +40,7 @@ using index_type = CordRepRing::index_type;
 enum class Direction { kForward, kReversed };
 
 inline bool IsFlatOrExternal(CordRep* rep) {
-  return rep->tag >= FLAT || rep->tag == EXTERNAL;
+  return rep->IsFlat() || rep->IsExternal();
 }
 
 // Verifies that n + extra <= kMaxCapacity: throws std::length_error otherwise.
@@ -58,14 +50,6 @@ inline void CheckCapacity(size_t n, size_t extra) {
   }
 }
 
-// Removes a reference from `rep` only.
-// Asserts that the refcount after decrement is not zero.
-inline bool UnrefNeverOne(CordRep* rep) {
-  bool result = rep->refcount.Decrement();
-  assert(result);
-  return result;
-}
-
 // Creates a flat from the provided string data, allocating up to `extra`
 // capacity in the returned flat depending on kMaxFlatLength limitations.
 // Requires `len` to be less or equal to `kMaxFlatLength`
@@ -77,40 +61,6 @@ CordRepFlat* CreateFlat(const char* s, size_t n, size_t extra = 0) {  // NOLINT
   return rep;
 }
 
-// Unrefs the provided `substring`, and returns `substring->child`
-// Adds or assumes a reference on `substring->child`
-CordRep* ClipSubstring(CordRepSubstring* substring) {
-  CordRep* child = substring->child;
-  if (substring->refcount.IsOne()) {
-    delete substring;
-  } else {
-    CordRep::Ref(child);
-    if (ABSL_PREDICT_FALSE(!substring->refcount.Decrement())) {
-      UnrefNeverOne(child);
-      delete substring;
-    }
-  }
-  return child;
-}
-
-// Unrefs the provided `concat`, and returns `{concat->left, concat->right}`
-// Adds or assumes a reference on `concat->left` and `concat->right`.
-std::pair<CordRep*, CordRep*> ClipConcat(CordRepConcat* concat) {
-  auto result = std::make_pair(concat->left, concat->right);
-  if (concat->refcount.IsOne()) {
-    delete concat;
-  } else {
-    CordRep::Ref(result.first);
-    CordRep::Ref(result.second);
-    if (ABSL_PREDICT_FALSE(!concat->refcount.Decrement())) {
-      UnrefNeverOne(result.first);
-      UnrefNeverOne(result.second);
-      delete concat;
-    }
-  }
-  return result;
-}
-
 // Unrefs the entries in `[head, tail)`.
 // Requires all entries to be a FLAT or EXTERNAL node.
 void UnrefEntries(const CordRepRing* rep, index_type head, index_type tail) {
@@ -126,79 +76,6 @@ void UnrefEntries(const CordRepRing* rep, index_type head, index_type tail) {
   });
 }
 
-template <typename F>
-void Consume(Direction direction, CordRep* rep, F&& fn) {
-  size_t offset = 0;
-  size_t length = rep->length;
-  struct Entry {
-    CordRep* rep;
-    size_t offset;
-    size_t length;
-  };
-  absl::InlinedVector<Entry, 40> stack;
-
-  for (;;) {
-    if (rep->tag >= FLAT || rep->tag == EXTERNAL || rep->tag == RING) {
-      fn(rep, offset, length);
-      if (stack.empty()) return;
-
-      rep = stack.back().rep;
-      offset = stack.back().offset;
-      length = stack.back().length;
-      stack.pop_back();
-    } else if (rep->tag == SUBSTRING) {
-      offset += rep->substring()->start;
-      rep = ClipSubstring(rep->substring());
-    } else if (rep->tag == CONCAT) {
-      auto res = ClipConcat(rep->concat());
-      CordRep* left = res.first;
-      CordRep* right = res.second;
-
-      if (left->length <= offset) {
-        // Don't need left node
-        offset -= left->length;
-        CordRep::Unref(left);
-        rep = right;
-        continue;
-      }
-
-      size_t length_left = left->length - offset;
-      if (length_left >= length) {
-        // Don't need right node
-        CordRep::Unref(right);
-        rep = left;
-        continue;
-      }
-
-      // Need both nodes
-      size_t length_right = length - length_left;
-      if (direction == Direction::kReversed) {
-        stack.push_back({left, offset, length_left});
-        rep = right;
-        offset = 0;
-        length = length_right;
-      } else {
-        stack.push_back({right, 0, length_right});
-        rep = left;
-        length = length_left;
-      }
-    } else {
-      assert("Valid tag" == nullptr);
-      return;
-    }
-  }
-}
-
-template <typename F>
-void Consume(CordRep* rep, F&& fn) {
-  return Consume(Direction::kForward, rep, std::forward<F>(fn));
-}
-
-template <typename F>
-void RConsume(CordRep* rep, F&& fn) {
-  return Consume(Direction::kReversed, rep, std::forward<F>(fn));
-}
-
 }  // namespace
 
 std::ostream& operator<<(std::ostream& s, const CordRepRing& rep) {
@@ -252,7 +129,9 @@ class CordRepRing::Filler {
   index_type pos_;
 };
 
-constexpr size_t CordRepRing::kMaxCapacity; // NOLINT: needed for c++11
+#ifdef ABSL_INTERNAL_NEED_REDUNDANT_CONSTEXPR_DECL
+constexpr size_t CordRepRing::kMaxCapacity;
+#endif
 
 bool CordRepRing::IsValid(std::ostream& output) const {
   if (capacity_ == 0) {
@@ -301,7 +180,7 @@ bool CordRepRing::IsValid(std::ostream& output) const {
     if (offset >= child->length || entry_length > child->length - offset) {
       output << "entry[" << head << "] has offset " << offset
              << " and entry length " << entry_length
-             << " which are outside of the childs length of " << child->length;
+             << " which are outside of the child's length of " << child->length;
       return false;
     }
 
@@ -352,7 +231,7 @@ void CordRepRing::SetCapacityForTesting(size_t capacity) {
 }
 
 void CordRepRing::Delete(CordRepRing* rep) {
-  assert(rep != nullptr && rep->tag == RING);
+  assert(rep != nullptr && rep->IsRing());
 #if defined(__cpp_sized_deallocation)
   size_t size = AllocSize(rep->capacity_);
   rep->~CordRepRing();
@@ -400,10 +279,11 @@ CordRepRing* CordRepRing::Mutable(CordRepRing* rep, size_t extra) {
   // Get current number of entries, and check for max capacity.
   size_t entries = rep->entries();
 
-  size_t min_extra = (std::max)(extra, rep->capacity() * 2 - entries);
   if (!rep->refcount.IsOne()) {
-    return Copy(rep, rep->head(), rep->tail(), min_extra);
+    return Copy(rep, rep->head(), rep->tail(), extra);
   } else if (entries + extra > rep->capacity()) {
+    const size_t min_grow = rep->capacity() + rep->capacity() / 2;
+    const size_t min_extra = (std::max)(extra, min_grow - entries);
     CordRepRing* newrep = CordRepRing::New(entries, min_extra);
     newrep->Fill<false>(rep, rep->head(), rep->tail());
     CordRepRing::Delete(rep);
@@ -449,12 +329,12 @@ Span<char> CordRepRing::GetPrependBuffer(size_t size) {
 }
 
 CordRepRing* CordRepRing::CreateFromLeaf(CordRep* child, size_t offset,
-                                         size_t length, size_t extra) {
+                                         size_t len, size_t extra) {
   CordRepRing* rep = CordRepRing::New(1, extra);
   rep->head_ = 0;
   rep->tail_ = rep->advance(0);
-  rep->length = length;
-  rep->entry_end_pos()[0] = length;
+  rep->length = len;
+  rep->entry_end_pos()[0] = len;
   rep->entry_child()[0] = child;
   rep->entry_data_offset()[0] = static_cast<offset_type>(offset);
   return Validate(rep);
@@ -462,16 +342,16 @@ CordRepRing* CordRepRing::CreateFromLeaf(CordRep* child, size_t offset,
 
 CordRepRing* CordRepRing::CreateSlow(CordRep* child, size_t extra) {
   CordRepRing* rep = nullptr;
-  Consume(child, [&](CordRep* child, size_t offset, size_t length) {
-    if (IsFlatOrExternal(child)) {
-      rep = rep ? AppendLeaf(rep, child, offset, length)
-                : CreateFromLeaf(child, offset, length, extra);
+  Consume(child, [&](CordRep* child_arg, size_t offset, size_t len) {
+    if (IsFlatOrExternal(child_arg)) {
+      rep = rep ? AppendLeaf(rep, child_arg, offset, len)
+                : CreateFromLeaf(child_arg, offset, len, extra);
     } else if (rep) {
-      rep = AddRing<AddMode::kAppend>(rep, child->ring(), offset, length);
-    } else if (offset == 0 && child->length == length) {
-      rep = Mutable(child->ring(), extra);
+      rep = AddRing<AddMode::kAppend>(rep, child_arg->ring(), offset, len);
+    } else if (offset == 0 && child_arg->length == len) {
+      rep = Mutable(child_arg->ring(), extra);
     } else {
-      rep = SubRing(child->ring(), offset, length, extra);
+      rep = SubRing(child_arg->ring(), offset, len, extra);
     }
   });
   return Validate(rep, nullptr, __LINE__);
@@ -482,7 +362,7 @@ CordRepRing* CordRepRing::Create(CordRep* child, size_t extra) {
   if (IsFlatOrExternal(child)) {
     return CreateFromLeaf(child, 0, length, extra);
   }
-  if (child->tag == RING) {
+  if (child->IsRing()) {
     return Mutable(child->ring(), extra);
   }
   return CreateSlow(child, extra);
@@ -490,18 +370,18 @@ CordRepRing* CordRepRing::Create(CordRep* child, size_t extra) {
 
 template <CordRepRing::AddMode mode>
 CordRepRing* CordRepRing::AddRing(CordRepRing* rep, CordRepRing* ring,
-                                  size_t offset, size_t length) {
+                                  size_t offset, size_t len) {
   assert(offset < ring->length);
   constexpr bool append = mode == AddMode::kAppend;
   Position head = ring->Find(offset);
-  Position tail = ring->FindTail(head.index, offset + length);
+  Position tail = ring->FindTail(head.index, offset + len);
   const index_type entries = ring->entries(head.index, tail.index);
 
   rep = Mutable(rep, entries);
 
   // The delta for making ring[head].end_pos into 'len - offset'
   const pos_type delta_length =
-      (append ? rep->begin_pos_ + rep->length : rep->begin_pos_ - length) -
+      (append ? rep->begin_pos_ + rep->length : rep->begin_pos_ - len) -
       ring->entry_begin_pos(head.index) - head.offset;
 
   // Start filling at `tail`, or `entries` before `head`
@@ -542,36 +422,36 @@ CordRepRing* CordRepRing::AddRing(CordRepRing* rep, CordRepRing* ring,
   }
 
   // Commit changes
-  rep->length += length;
+  rep->length += len;
   if (append) {
     rep->tail_ = filler.pos();
   } else {
     rep->head_ = filler.head();
-    rep->begin_pos_ -= length;
+    rep->begin_pos_ -= len;
   }
 
   return Validate(rep);
 }
 
 CordRepRing* CordRepRing::AppendSlow(CordRepRing* rep, CordRep* child) {
-  Consume(child, [&rep](CordRep* child, size_t offset, size_t length) {
-    if (child->tag == RING) {
-      rep = AddRing<AddMode::kAppend>(rep, child->ring(), offset, length);
+  Consume(child, [&rep](CordRep* child_arg, size_t offset, size_t len) {
+    if (child_arg->IsRing()) {
+      rep = AddRing<AddMode::kAppend>(rep, child_arg->ring(), offset, len);
     } else {
-      rep = AppendLeaf(rep, child, offset, length);
+      rep = AppendLeaf(rep, child_arg, offset, len);
     }
   });
   return rep;
 }
 
 CordRepRing* CordRepRing::AppendLeaf(CordRepRing* rep, CordRep* child,
-                                     size_t offset, size_t length) {
+                                     size_t offset, size_t len) {
   rep = Mutable(rep, 1);
   index_type back = rep->tail_;
   const pos_type begin_pos = rep->begin_pos_ + rep->length;
   rep->tail_ = rep->advance(rep->tail_);
-  rep->length += length;
-  rep->entry_end_pos()[back] = begin_pos + length;
+  rep->length += len;
+  rep->entry_end_pos()[back] = begin_pos + len;
   rep->entry_child()[back] = child;
   rep->entry_data_offset()[back] = static_cast<offset_type>(offset);
   return Validate(rep, nullptr, __LINE__);
@@ -582,31 +462,31 @@ CordRepRing* CordRepRing::Append(CordRepRing* rep, CordRep* child) {
   if (IsFlatOrExternal(child)) {
     return AppendLeaf(rep, child, 0, length);
   }
-  if (child->tag == RING) {
+  if (child->IsRing()) {
     return AddRing<AddMode::kAppend>(rep, child->ring(), 0, length);
   }
   return AppendSlow(rep, child);
 }
 
 CordRepRing* CordRepRing::PrependSlow(CordRepRing* rep, CordRep* child) {
-  RConsume(child, [&](CordRep* child, size_t offset, size_t length) {
-    if (IsFlatOrExternal(child)) {
-      rep = PrependLeaf(rep, child, offset, length);
+  ReverseConsume(child, [&](CordRep* child_arg, size_t offset, size_t len) {
+    if (IsFlatOrExternal(child_arg)) {
+      rep = PrependLeaf(rep, child_arg, offset, len);
     } else {
-      rep = AddRing<AddMode::kPrepend>(rep, child->ring(), offset, length);
+      rep = AddRing<AddMode::kPrepend>(rep, child_arg->ring(), offset, len);
     }
   });
   return Validate(rep);
 }
 
 CordRepRing* CordRepRing::PrependLeaf(CordRepRing* rep, CordRep* child,
-                                      size_t offset, size_t length) {
+                                      size_t offset, size_t len) {
   rep = Mutable(rep, 1);
   index_type head = rep->retreat(rep->head_);
   pos_type end_pos = rep->begin_pos_;
   rep->head_ = head;
-  rep->length += length;
-  rep->begin_pos_ -= length;
+  rep->length += len;
+  rep->begin_pos_ -= len;
   rep->entry_end_pos()[head] = end_pos;
   rep->entry_child()[head] = child;
   rep->entry_data_offset()[head] = static_cast<offset_type>(offset);
@@ -618,7 +498,7 @@ CordRepRing* CordRepRing::Prepend(CordRepRing* rep, CordRep* child) {
   if (IsFlatOrExternal(child)) {
     return PrependLeaf(rep, child, 0, length);
   }
-  if (child->tag == RING) {
+  if (child->IsRing()) {
     return AddRing<AddMode::kPrepend>(rep, child->ring(), 0, length);
   }
   return PrependSlow(rep, child);
@@ -786,18 +666,18 @@ char CordRepRing::GetCharacter(size_t offset) const {
 }
 
 CordRepRing* CordRepRing::SubRing(CordRepRing* rep, size_t offset,
-                                  size_t length, size_t extra) {
+                                  size_t len, size_t extra) {
   assert(offset <= rep->length);
-  assert(offset <= rep->length - length);
+  assert(offset <= rep->length - len);
 
-  if (length == 0) {
+  if (len == 0) {
     CordRep::Unref(rep);
     return nullptr;
   }
 
   // Find position of first byte
   Position head = rep->Find(offset);
-  Position tail = rep->FindTail(head.index, offset + length);
+  Position tail = rep->FindTail(head.index, offset + len);
   const size_t new_entries = rep->entries(head.index, tail.index);
 
   if (rep->refcount.IsOne() && extra <= (rep->capacity() - new_entries)) {
@@ -814,7 +694,7 @@ CordRepRing* CordRepRing::SubRing(CordRepRing* rep, size_t offset,
   }
 
   // Adjust begin_pos and length
-  rep->length = length;
+  rep->length = len;
   rep->begin_pos_ += offset;
 
   // Adjust head and tail blocks
@@ -888,10 +768,6 @@ CordRepRing* CordRepRing::RemoveSuffix(CordRepRing* rep, size_t len,
   return Validate(rep);
 }
 
-#ifdef __clang__
-#pragma clang diagnostic pop
-#endif
-
 }  // namespace cord_internal
 ABSL_NAMESPACE_END
 }  // namespace absl