1 files changed, 92 insertions, 40 deletions

diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc
index 85a67a08..1d33dd83 100644
--- a/absl/strings/cord.cc
+++ b/absl/strings/cord.cc
@@ -20,6 +20,7 @@
 #include <cstdio>
 #include <cstdlib>
 #include <iomanip>
+#include <ios>
 #include <iostream>
 #include <limits>
 #include <ostream>
@@ -34,6 +35,7 @@
 #include "absl/base/port.h"
 #include "absl/container/fixed_array.h"
 #include "absl/container/inlined_vector.h"
+#include "absl/crc/internal/crc_cord_state.h"
 #include "absl/strings/cord_buffer.h"
 #include "absl/strings/escaping.h"
 #include "absl/strings/internal/cord_data_edge.h"
@@ -166,9 +168,7 @@ constexpr unsigned char Cord::InlineRep::kMaxInline;
 
 inline void Cord::InlineRep::set_data(const char* data, size_t n) {
   static_assert(kMaxInline == 15, "set_data is hard-coded for a length of 15");
-
-  cord_internal::SmallMemmove<true>(data_.as_chars(), data, n);
-  set_inline_size(n);
+  data_.set_inline_data(data, n);
 }
 
 inline char* Cord::InlineRep::set_data(size_t n) {
@@ -184,7 +184,7 @@ inline void Cord::InlineRep::reduce_size(size_t n) {
   assert(tag >= n);
   tag -= n;
   memset(data_.as_chars() + tag, 0, n);
-  set_inline_size(static_cast<char>(tag));
+  set_inline_size(tag);
 }
 
 inline void Cord::InlineRep::remove_prefix(size_t n) {
@@ -419,6 +419,7 @@ Cord& Cord::operator=(absl::string_view src) {
 // we keep it here to make diffs easier.
 void Cord::InlineRep::AppendArray(absl::string_view src,
                                   MethodIdentifier method) {
+  MaybeRemoveEmptyCrcNode();
   if (src.empty()) return;  // memcpy(_, nullptr, 0) is undefined.
 
   size_t appended = 0;
@@ -436,8 +437,8 @@ void Cord::InlineRep::AppendArray(absl::string_view src,
     size_t inline_length = inline_size();
     if (src.size() <= kMaxInline - inline_length) {
       // Append new data to embedded array
-      memcpy(data_.as_chars() + inline_length, src.data(), src.size());
       set_inline_size(inline_length + src.size());
+      memcpy(data_.as_chars() + inline_length, src.data(), src.size());
       return;
     }
 
@@ -478,6 +479,10 @@ inline CordRep* Cord::TakeRep() && {
 template <typename C>
 inline void Cord::AppendImpl(C&& src) {
   auto constexpr method = CordzUpdateTracker::kAppendCord;
+
+  contents_.MaybeRemoveEmptyCrcNode();
+  if (src.empty()) return;
+
   if (empty()) {
     // Since destination is empty, we can avoid allocating a node,
     if (src.contents_.is_tree()) {
@@ -537,18 +542,23 @@ static CordRep::ExtractResult ExtractAppendBuffer(CordRep* rep,
   }
 }
 
-static CordBuffer CreateAppendBuffer(InlineData& data, size_t capacity) {
+static CordBuffer CreateAppendBuffer(InlineData& data, size_t block_size,
+                                     size_t capacity) {
   // Watch out for overflow, people can ask for size_t::max().
   const size_t size = data.inline_size();
-  capacity = (std::min)(std::numeric_limits<size_t>::max() - size, capacity);
-  CordBuffer buffer = CordBuffer::CreateWithDefaultLimit(size + capacity);
+  const size_t max_capacity = std::numeric_limits<size_t>::max() - size;
+  capacity = (std::min)(max_capacity, capacity) + size;
+  CordBuffer buffer =
+      block_size ? CordBuffer::CreateWithCustomLimit(block_size, capacity)
+                 : CordBuffer::CreateWithDefaultLimit(capacity);
   cord_internal::SmallMemmove(buffer.data(), data.as_chars(), size);
   buffer.SetLength(size);
   data = {};
   return buffer;
 }
 
-CordBuffer Cord::GetAppendBufferSlowPath(size_t capacity, size_t min_capacity) {
+CordBuffer Cord::GetAppendBufferSlowPath(size_t block_size, size_t capacity,
+                                         size_t min_capacity) {
   auto constexpr method = CordzUpdateTracker::kGetAppendBuffer;
   CordRep* tree = contents_.tree();
   if (tree != nullptr) {
@@ -558,9 +568,10 @@ CordBuffer Cord::GetAppendBufferSlowPath(size_t capacity, size_t min_capacity) {
       contents_.SetTreeOrEmpty(result.tree, scope);
       return CordBuffer(result.extracted->flat());
     }
-    return CordBuffer::CreateWithDefaultLimit(capacity);
+    return block_size ? CordBuffer::CreateWithCustomLimit(block_size, capacity)
+                      : CordBuffer::CreateWithDefaultLimit(capacity);
   }
-  return CreateAppendBuffer(contents_.data_, capacity);
+  return CreateAppendBuffer(contents_.data_, block_size, capacity);
 }
 
 void Cord::Append(const Cord& src) {
@@ -584,6 +595,9 @@ void Cord::Append(T&& src) {
 template void Cord::Append(std::string&& src);
 
 void Cord::Prepend(const Cord& src) {
+  contents_.MaybeRemoveEmptyCrcNode();
+  if (src.empty()) return;
+
   CordRep* src_tree = src.contents_.tree();
   if (src_tree != nullptr) {
     CordRep::Ref(src_tree);
@@ -598,16 +612,18 @@ void Cord::Prepend(const Cord& src) {
 }
 
 void Cord::PrependArray(absl::string_view src, MethodIdentifier method) {
+  contents_.MaybeRemoveEmptyCrcNode();
   if (src.empty()) return;  // memcpy(_, nullptr, 0) is undefined.
+
   if (!contents_.is_tree()) {
     size_t cur_size = contents_.inline_size();
     if (cur_size + src.size() <= InlineRep::kMaxInline) {
       // Use embedded storage.
-      char data[InlineRep::kMaxInline + 1] = {0};
-      memcpy(data, src.data(), src.size());
-      memcpy(data + src.size(), contents_.data(), cur_size);
-      memcpy(contents_.data_.as_chars(), data, InlineRep::kMaxInline + 1);
-      contents_.set_inline_size(cur_size + src.size());
+      InlineData data;
+      data.set_inline_size(cur_size + src.size());
+      memcpy(data.as_chars(), src.data(), src.size());
+      memcpy(data.as_chars() + src.size(), contents_.data(), cur_size);
+      contents_.data_ = data;
       return;
     }
   }
@@ -620,8 +636,8 @@ void Cord::AppendPrecise(absl::string_view src, MethodIdentifier method) {
   assert(src.size() <= cord_internal::kMaxFlatLength);
   if (contents_.remaining_inline_capacity() >= src.size()) {
     const size_t inline_length = contents_.inline_size();
-    memcpy(contents_.data_.as_chars() + inline_length, src.data(), src.size());
     contents_.set_inline_size(inline_length + src.size());
+    memcpy(contents_.data_.as_chars() + inline_length, src.data(), src.size());
   } else {
     contents_.AppendTree(CordRepFlat::Create(src), method);
   }
@@ -631,12 +647,12 @@ void Cord::PrependPrecise(absl::string_view src, MethodIdentifier method) {
   assert(!src.empty());
   assert(src.size() <= cord_internal::kMaxFlatLength);
   if (contents_.remaining_inline_capacity() >= src.size()) {
-    const size_t inline_length = contents_.inline_size();
-    char data[InlineRep::kMaxInline + 1] = {0};
-    memcpy(data, src.data(), src.size());
-    memcpy(data + src.size(), contents_.data(), inline_length);
-    memcpy(contents_.data_.as_chars(), data, InlineRep::kMaxInline + 1);
-    contents_.set_inline_size(inline_length + src.size());
+    const size_t cur_size = contents_.inline_size();
+    InlineData data;
+    data.set_inline_size(cur_size + src.size());
+    memcpy(data.as_chars(), src.data(), src.size());
+    memcpy(data.as_chars() + src.size(), contents_.data(), cur_size);
+    contents_.data_ = data;
   } else {
     contents_.PrependTree(CordRepFlat::Create(src), method);
   }
@@ -658,6 +674,7 @@ void Cord::RemovePrefix(size_t n) {
   ABSL_INTERNAL_CHECK(n <= size(),
                       absl::StrCat("Requested prefix size ", n,
                                    " exceeds Cord's size ", size()));
+  contents_.MaybeRemoveEmptyCrcNode();
   CordRep* tree = contents_.tree();
   if (tree == nullptr) {
     contents_.remove_prefix(n);
@@ -688,6 +705,7 @@ void Cord::RemoveSuffix(size_t n) {
   ABSL_INTERNAL_CHECK(n <= size(),
                       absl::StrCat("Requested suffix size ", n,
                                    " exceeds Cord's size ", size()));
+  contents_.MaybeRemoveEmptyCrcNode();
   CordRep* tree = contents_.tree();
   if (tree == nullptr) {
     contents_.reduce_size(n);
@@ -726,6 +744,7 @@ Cord Cord::Subcord(size_t pos, size_t new_size) const {
   }
 
   if (new_size <= InlineRep::kMaxInline) {
+    sub_cord.contents_.set_inline_size(new_size);
     char* dest = sub_cord.contents_.data_.as_chars();
     Cord::ChunkIterator it = chunk_begin();
     it.AdvanceBytes(pos);
@@ -737,7 +756,6 @@ Cord Cord::Subcord(size_t pos, size_t new_size) const {
       ++it;
     }
     cord_internal::SmallMemmove(dest, it->data(), remaining_size);
-    sub_cord.contents_.set_inline_size(new_size);
     return sub_cord;
   }
 
@@ -835,26 +853,44 @@ inline absl::string_view Cord::InlineRep::FindFlatStartPiece() const {
   return absl::string_view(node->external()->base + offset, length);
 }
 
-void Cord::SetExpectedChecksum(uint32_t crc) {
+void Cord::SetCrcCordState(crc_internal::CrcCordState state) {
   auto constexpr method = CordzUpdateTracker::kSetExpectedChecksum;
-  if (empty()) return;
-
-  if (!contents_.is_tree()) {
+  if (empty()) {
+    contents_.MaybeRemoveEmptyCrcNode();
+    CordRep* rep = CordRepCrc::New(nullptr, std::move(state));
+    contents_.EmplaceTree(rep, method);
+  } else if (!contents_.is_tree()) {
     CordRep* rep = contents_.MakeFlatWithExtraCapacity(0);
-    rep = CordRepCrc::New(rep, crc);
+    rep = CordRepCrc::New(rep, std::move(state));
     contents_.EmplaceTree(rep, method);
   } else {
     const CordzUpdateScope scope(contents_.data_.cordz_info(), method);
-    CordRep* rep = CordRepCrc::New(contents_.data_.as_tree(), crc);
+    CordRep* rep = CordRepCrc::New(contents_.data_.as_tree(), std::move(state));
     contents_.SetTree(rep, scope);
   }
 }
 
+void Cord::SetExpectedChecksum(uint32_t crc) {
+  // Construct a CrcCordState with a single chunk.
+  crc_internal::CrcCordState state;
+  state.mutable_rep()->prefix_crc.push_back(
+      crc_internal::CrcCordState::PrefixCrc(size(), absl::crc32c_t{crc}));
+  SetCrcCordState(std::move(state));
+}
+
+const crc_internal::CrcCordState* Cord::MaybeGetCrcCordState() const {
+  if (!contents_.is_tree() || !contents_.tree()->IsCrc()) {
+    return nullptr;
+  }
+  return &contents_.tree()->crc()->crc_cord_state;
+}
+
 absl::optional<uint32_t> Cord::ExpectedChecksum() const {
   if (!contents_.is_tree() || !contents_.tree()->IsCrc()) {
     return absl::nullopt;
   }
-  return contents_.tree()->crc()->crc;
+  return static_cast<uint32_t>(
+      contents_.tree()->crc()->crc_cord_state.Checksum());
 }
 
 inline int Cord::CompareSlowPath(absl::string_view rhs, size_t compared_size,
@@ -922,6 +958,7 @@ inline int Cord::CompareSlowPath(const Cord& rhs, size_t compared_size,
 }
 
 inline absl::string_view Cord::GetFirstChunk(const Cord& c) {
+  if (c.empty()) return {};
   return c.contents_.FindFlatStartPiece();
 }
 inline absl::string_view Cord::GetFirstChunk(absl::string_view sv) {
@@ -1092,7 +1129,7 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) {
                          : current_leaf_;
   const char* data = payload->IsExternal() ? payload->external()->base
                                            : payload->flat()->Data();
-  const size_t offset = current_chunk_.data() - data;
+  const size_t offset = static_cast<size_t>(current_chunk_.data() - data);
 
   auto* tree = CordRepSubstring::Substring(payload, offset, n);
   subcord.contents_.EmplaceTree(VerifyTree(tree), method);
@@ -1159,6 +1196,10 @@ absl::string_view Cord::FlattenSlowPath() {
 
 /* static */ bool Cord::GetFlatAux(CordRep* rep, absl::string_view* fragment) {
   assert(rep != nullptr);
+  if (rep->length == 0) {
+    *fragment = absl::string_view();
+    return true;
+  }
   rep = cord_internal::SkipCrcNode(rep);
   if (rep->IsFlat()) {
     *fragment = absl::string_view(rep->flat()->Data(), rep->length);
@@ -1190,6 +1231,7 @@ absl::string_view Cord::FlattenSlowPath() {
     absl::cord_internal::CordRep* rep,
     absl::FunctionRef<void(absl::string_view)> callback) {
   assert(rep != nullptr);
+  if (rep->length == 0) return;
   rep = cord_internal::SkipCrcNode(rep);
 
   if (rep->IsBtree()) {
@@ -1223,8 +1265,12 @@ static void DumpNode(CordRep* rep, bool include_data, std::ostream* os,
     if (include_data) *os << static_cast<void*>(rep);
     *os << "]";
     *os << " " << std::setw(indent) << "";
-    if (rep->IsCrc()) {
-      *os << "CRC crc=" << rep->crc()->crc << "\n";
+    bool leaf = false;
+    if (rep == nullptr) {
+      *os << "NULL\n";
+      leaf = true;
+    } else if (rep->IsCrc()) {
+      *os << "CRC crc=" << rep->crc()->crc_cord_state.Checksum() << "\n";
       indent += kIndentStep;
       rep = rep->crc()->child;
     } else if (rep->IsSubstring()) {
@@ -1232,6 +1278,7 @@ static void DumpNode(CordRep* rep, bool include_data, std::ostream* os,
       indent += kIndentStep;
       rep = rep->substring()->child;
     } else {  // Leaf or ring
+      leaf = true;
       if (rep->IsExternal()) {
         *os << "EXTERNAL [";
         if (include_data)
@@ -1245,6 +1292,8 @@ static void DumpNode(CordRep* rep, bool include_data, std::ostream* os,
       } else {
         CordRepBtree::Dump(rep, /*label=*/ "", include_data, *os);
       }
+    }
+    if (leaf) {
       if (stack.empty()) break;
       rep = stack.back();
       stack.pop_back();
@@ -1290,11 +1339,14 @@ static bool VerifyNode(CordRep* root, CordRep* start_node,
                               node->substring()->child->length,
                           ReportError(root, node));
     } else if (node->IsCrc()) {
-      ABSL_INTERNAL_CHECK(node->crc()->child != nullptr,
-                          ReportError(root, node));
-      ABSL_INTERNAL_CHECK(node->crc()->length == node->crc()->child->length,
-                          ReportError(root, node));
-      worklist.push_back(node->crc()->child);
+      ABSL_INTERNAL_CHECK(
+          node->crc()->child != nullptr || node->crc()->length == 0,
+          ReportError(root, node));
+      if (node->crc()->child != nullptr) {
+        ABSL_INTERNAL_CHECK(node->crc()->length == node->crc()->child->length,
+                            ReportError(root, node));
+        worklist.push_back(node->crc()->child);
+      }
     }
   } while (!worklist.empty());
   return true;
@@ -1302,7 +1354,7 @@ static bool VerifyNode(CordRep* root, CordRep* start_node,
 
 std::ostream& operator<<(std::ostream& out, const Cord& cord) {
   for (absl::string_view chunk : cord.Chunks()) {
-    out.write(chunk.data(), chunk.size());
+    out.write(chunk.data(), static_cast<std::streamsize>(chunk.size()));
   }
   return out;
 }