about summary refs log tree commit diff
path: root/absl/strings
diff options
context:
space:
mode:
Diffstat (limited to 'absl/strings')
-rw-r--r--absl/strings/BUILD.bazel1
-rw-r--r--absl/strings/CMakeLists.txt1
-rw-r--r--absl/strings/cord.cc291
-rw-r--r--absl/strings/cord.h638
-rw-r--r--absl/strings/cord_test.cc68
-rw-r--r--absl/strings/internal/str_format/extension.h18
-rw-r--r--absl/strings/string_view.h2
7 files changed, 667 insertions, 352 deletions
diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel
index 64f55fb4f93d..389011224891 100644
--- a/absl/strings/BUILD.bazel
+++ b/absl/strings/BUILD.bazel
@@ -313,6 +313,7 @@ cc_test(
         ":strings",
         "//absl/base",
         "//absl/base:config",
+        "//absl/base:core_headers",
         "//absl/base:endian",
         "//absl/base:raw_logging_internal",
         "//absl/container:fixed_array",
diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt
index c7874ecf10da..d3a8bd7eb1e5 100644
--- a/absl/strings/CMakeLists.txt
+++ b/absl/strings/CMakeLists.txt
@@ -578,6 +578,7 @@ absl_cc_test(
     absl::strings
     absl::base
     absl::config
+    absl::core_headers
     absl::endian
     absl::raw_logging_internal
     absl::fixed_array
diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc
index 4f64f79965c7..7de7766c5116 100644
--- a/absl/strings/cord.cc
+++ b/absl/strings/cord.cc
@@ -28,9 +28,9 @@
 
 #include "absl/base/casts.h"
 #include "absl/base/internal/raw_logging.h"
+#include "absl/base/macros.h"
 #include "absl/base/port.h"
 #include "absl/container/fixed_array.h"
-#include "absl/container/inlined_vector.h"
 #include "absl/strings/escaping.h"
 #include "absl/strings/internal/cord_internal.h"
 #include "absl/strings/internal/resize_uninitialized.h"
@@ -132,6 +132,14 @@ inline const CordRepExternal* CordRep::external() const {
   return static_cast<const CordRepExternal*>(this);
 }
 
+using CordTreeConstPath = CordTreePath<const CordRep*, MaxCordDepth()>;
+
+// This type is used to store the list of pending nodes during re-balancing.
+// Its maximum size is 2 * MaxCordDepth() because the tree has a maximum
+// possible depth of MaxCordDepth() and every concat node along a tree path
+// could theoretically be split during rebalancing.
+using RebalancingStack = CordTreePath<CordRep*, 2 * MaxCordDepth()>;
+
 }  // namespace cord_internal
 
 static const size_t kFlatOverhead = offsetof(CordRep, data);
@@ -180,98 +188,78 @@ static constexpr size_t TagToLength(uint8_t tag) {
 // Enforce that kMaxFlatSize maps to a well-known exact tag value.
 static_assert(TagToAllocatedSize(224) == kMaxFlatSize, "Bad tag logic");
 
-constexpr uint64_t Fibonacci(unsigned char n, uint64_t a = 0, uint64_t b = 1) {
-  return n == 0 ? a : Fibonacci(n - 1, b, a + b);
+constexpr size_t Fibonacci(uint8_t n, const size_t a = 0, const size_t b = 1) {
+  return n == 0
+             ? a
+             : n == 1 ? b
+                      : Fibonacci(n - 1, b,
+                                  (a > (size_t(-1) - b)) ? size_t(-1) : a + b);
 }
 
-static_assert(Fibonacci(63) == 6557470319842,
-              "Fibonacci values computed incorrectly");
-
 // Minimum length required for a given depth tree -- a tree is considered
 // balanced if
-//      length(t) >= min_length[depth(t)]
-// The root node depth is allowed to become twice as large to reduce rebalancing
-// for larger strings (see IsRootBalanced).
-static constexpr uint64_t min_length[] = {
-    Fibonacci(2),
-    Fibonacci(3),
-    Fibonacci(4),
-    Fibonacci(5),
-    Fibonacci(6),
-    Fibonacci(7),
-    Fibonacci(8),
-    Fibonacci(9),
-    Fibonacci(10),
-    Fibonacci(11),
-    Fibonacci(12),
-    Fibonacci(13),
-    Fibonacci(14),
-    Fibonacci(15),
-    Fibonacci(16),
-    Fibonacci(17),
-    Fibonacci(18),
-    Fibonacci(19),
-    Fibonacci(20),
-    Fibonacci(21),
-    Fibonacci(22),
-    Fibonacci(23),
-    Fibonacci(24),
-    Fibonacci(25),
-    Fibonacci(26),
-    Fibonacci(27),
-    Fibonacci(28),
-    Fibonacci(29),
-    Fibonacci(30),
-    Fibonacci(31),
-    Fibonacci(32),
-    Fibonacci(33),
-    Fibonacci(34),
-    Fibonacci(35),
-    Fibonacci(36),
-    Fibonacci(37),
-    Fibonacci(38),
-    Fibonacci(39),
-    Fibonacci(40),
-    Fibonacci(41),
-    Fibonacci(42),
-    Fibonacci(43),
-    Fibonacci(44),
-    Fibonacci(45),
-    Fibonacci(46),
-    Fibonacci(47),
-    0xffffffffffffffffull,  // Avoid overflow
-};
-
-static const int kMinLengthSize = ABSL_ARRAYSIZE(min_length);
-
-// The inlined size to use with absl::InlinedVector.
-//
-// Note: The InlinedVectors in this file (and in cord.h) do not need to use
-// the same value for their inlined size. The fact that they do is historical.
-// It may be desirable for each to use a different inlined size optimized for
-// that InlinedVector's usage.
-//
-// TODO(jgm): Benchmark to see if there's a more optimal value than 47 for
-// the inlined vector size (47 exists for backward compatibility).
-static const int kInlinedVectorSize = 47;
-
-static inline bool IsRootBalanced(CordRep* node) {
-  if (node->tag != CONCAT) {
-    return true;
-  } else if (node->concat()->depth() <= 15) {
-    return true;
-  } else if (node->concat()->depth() > kMinLengthSize) {
-    return false;
-  } else {
-    // Allow depth to become twice as large as implied by fibonacci rule to
-    // reduce rebalancing for larger strings.
-    return (node->length >= min_length[node->concat()->depth() / 2]);
-  }
+//      length(t) >= kMinLength[depth(t)]
+// The node depth is allowed to become larger to reduce rebalancing
+// for larger strings (see ShouldRebalance).
+constexpr size_t kMinLength[] = {
+    Fibonacci(2),  Fibonacci(3),  Fibonacci(4),  Fibonacci(5),  Fibonacci(6),
+    Fibonacci(7),  Fibonacci(8),  Fibonacci(9),  Fibonacci(10), Fibonacci(11),
+    Fibonacci(12), Fibonacci(13), Fibonacci(14), Fibonacci(15), Fibonacci(16),
+    Fibonacci(17), Fibonacci(18), Fibonacci(19), Fibonacci(20), Fibonacci(21),
+    Fibonacci(22), Fibonacci(23), Fibonacci(24), Fibonacci(25), Fibonacci(26),
+    Fibonacci(27), Fibonacci(28), Fibonacci(29), Fibonacci(30), Fibonacci(31),
+    Fibonacci(32), Fibonacci(33), Fibonacci(34), Fibonacci(35), Fibonacci(36),
+    Fibonacci(37), Fibonacci(38), Fibonacci(39), Fibonacci(40), Fibonacci(41),
+    Fibonacci(42), Fibonacci(43), Fibonacci(44), Fibonacci(45), Fibonacci(46),
+    Fibonacci(47), Fibonacci(48), Fibonacci(49), Fibonacci(50), Fibonacci(51),
+    Fibonacci(52), Fibonacci(53), Fibonacci(54), Fibonacci(55), Fibonacci(56),
+    Fibonacci(57), Fibonacci(58), Fibonacci(59), Fibonacci(60), Fibonacci(61),
+    Fibonacci(62), Fibonacci(63), Fibonacci(64), Fibonacci(65), Fibonacci(66),
+    Fibonacci(67), Fibonacci(68), Fibonacci(69), Fibonacci(70), Fibonacci(71),
+    Fibonacci(72), Fibonacci(73), Fibonacci(74), Fibonacci(75), Fibonacci(76),
+    Fibonacci(77), Fibonacci(78), Fibonacci(79), Fibonacci(80), Fibonacci(81),
+    Fibonacci(82), Fibonacci(83), Fibonacci(84), Fibonacci(85), Fibonacci(86),
+    Fibonacci(87), Fibonacci(88), Fibonacci(89), Fibonacci(90), Fibonacci(91),
+    Fibonacci(92), Fibonacci(93), Fibonacci(94), Fibonacci(95)};
+
+static_assert(sizeof(kMinLength) / sizeof(size_t) >=
+                  (cord_internal::MaxCordDepth() + 1),
+              "Not enough elements in kMinLength array to cover all the "
+              "supported Cord depth(s)");
+
+inline bool ShouldRebalance(const CordRep* node) {
+  if (node->tag != CONCAT) return false;
+
+  size_t node_depth = node->concat()->depth();
+
+  if (node_depth <= 15) return false;
+
+  // Rebalancing Cords is expensive, so we reduce how often rebalancing occurs
+  // by allowing shallow Cords to have twice the depth that the Fibonacci rule
+  // would otherwise imply. Deep Cords need to follow the rule more closely,
+  // however to ensure algorithm correctness. We implement this with linear
+  // interpolation. Cords of depth 16 are treated as though they have a depth
+  // of 16 * 1/2, and Cords of depth MaxCordDepth() interpolate to
+  // MaxCordDepth() * 1.
+  return node->length <
+         kMinLength[(node_depth * (cord_internal::MaxCordDepth() - 16)) /
+                    (2 * cord_internal::MaxCordDepth() - 16 - node_depth)];
+}
+
+// Unlike root balancing condition this one is part of the re-balancing
+// algorithm and has to be always matching against right depth for
+// algorithm to be correct.
+inline bool IsNodeBalanced(const CordRep* node) {
+  if (node->tag != CONCAT) return true;
+
+  size_t node_depth = node->concat()->depth();
+
+  return node->length >= kMinLength[node_depth];
 }
 
 static CordRep* Rebalance(CordRep* node);
-static void DumpNode(CordRep* rep, bool include_data, std::ostream* os);
-static bool VerifyNode(CordRep* root, CordRep* start_node,
+static void DumpNode(const CordRep* rep, bool include_data, std::ostream* os);
+static bool VerifyNode(const CordRep* root, const CordRep* start_node,
                        bool full_validation);
 
 static inline CordRep* VerifyTree(CordRep* node) {
@@ -318,7 +306,8 @@ __attribute__((preserve_most))
 static void UnrefInternal(CordRep* rep) {
   assert(rep != nullptr);
 
-  absl::InlinedVector<CordRep*, kInlinedVectorSize> pending;
+  cord_internal::RebalancingStack pending;
+
   while (true) {
     if (rep->tag == CONCAT) {
       CordRepConcat* rep_concat = rep->concat();
@@ -400,6 +389,11 @@ static void SetConcatChildren(CordRepConcat* concat, CordRep* left,
 
   concat->length = left->length + right->length;
   concat->set_depth(1 + std::max(Depth(left), Depth(right)));
+
+  ABSL_INTERNAL_CHECK(concat->depth() <= cord_internal::MaxCordDepth(),
+                      "Cord depth exceeds max");
+  ABSL_INTERNAL_CHECK(concat->length >= left->length, "Cord is too long");
+  ABSL_INTERNAL_CHECK(concat->length >= right->length, "Cord is too long");
 }
 
 // Create a concatenation of the specified nodes.
@@ -425,7 +419,7 @@ static CordRep* RawConcat(CordRep* left, CordRep* right) {
 
 static CordRep* Concat(CordRep* left, CordRep* right) {
   CordRep* rep = RawConcat(left, right);
-  if (rep != nullptr && !IsRootBalanced(rep)) {
+  if (rep != nullptr && ShouldRebalance(rep)) {
     rep = Rebalance(rep);
   }
   return VerifyTree(rep);
@@ -720,6 +714,14 @@ void Cord::InlineRep::ClearSlow() {
   memset(data_, 0, sizeof(data_));
 }
 
+inline Cord::InternalChunkIterator Cord::internal_chunk_begin() const {
+  return InternalChunkIterator(this);
+}
+
+inline Cord::InternalChunkRange Cord::InternalChunks() const {
+  return InternalChunkRange(this);
+}
+
 // --------------------------------------------------------------------
 // Constructors and destructors
 
@@ -916,7 +918,7 @@ void Cord::Prepend(absl::string_view src) {
 static CordRep* RemovePrefixFrom(CordRep* node, size_t n) {
   if (n >= node->length) return nullptr;
   if (n == 0) return Ref(node);
-  absl::InlinedVector<CordRep*, kInlinedVectorSize> rhs_stack;
+  cord_internal::CordTreeMutablePath rhs_stack;
 
   while (node->tag == CONCAT) {
     assert(n <= node->length);
@@ -957,7 +959,7 @@ static CordRep* RemovePrefixFrom(CordRep* node, size_t n) {
 static CordRep* RemoveSuffixFrom(CordRep* node, size_t n) {
   if (n >= node->length) return nullptr;
   if (n == 0) return Ref(node);
-  absl::InlinedVector<CordRep*, kInlinedVectorSize> lhs_stack;
+  absl::cord_internal::CordTreeMutablePath lhs_stack;
   bool inplace_ok = node->refcount.IsOne();
 
   while (node->tag == CONCAT) {
@@ -1028,6 +1030,7 @@ void Cord::RemoveSuffix(size_t n) {
 
 // Work item for NewSubRange().
 struct SubRange {
+  SubRange() = default;
   SubRange(CordRep* a_node, size_t a_pos, size_t a_n)
       : node(a_node), pos(a_pos), n(a_n) {}
   CordRep* node;  // nullptr means concat last 2 results.
@@ -1036,8 +1039,11 @@ struct SubRange {
 };
 
 static CordRep* NewSubRange(CordRep* node, size_t pos, size_t n) {
-  absl::InlinedVector<CordRep*, kInlinedVectorSize> results;
-  absl::InlinedVector<SubRange, kInlinedVectorSize> todo;
+  cord_internal::CordTreeMutablePath results;
+  // The algorithm below in worst case scenario adds up to 3 nodes to the `todo`
+  // list, but we also pop one out on every cycle. If original tree has depth d
+  // todo list can grew up to 2*d in size.
+  cord_internal::CordTreePath<SubRange, 2 * cord_internal::MaxCordDepth()> todo;
   todo.push_back(SubRange(node, pos, n));
   do {
     const SubRange& sr = todo.back();
@@ -1074,7 +1080,7 @@ static CordRep* NewSubRange(CordRep* node, size_t pos, size_t n) {
     }
   } while (!todo.empty());
   assert(results.size() == 1);
-  return results[0];
+  return results.back();
 }
 
 Cord Cord::Subcord(size_t pos, size_t new_size) const {
@@ -1090,7 +1096,7 @@ Cord Cord::Subcord(size_t pos, size_t new_size) const {
   } else if (new_size == 0) {
     // We want to return empty subcord, so nothing to do.
   } else if (new_size <= InlineRep::kMaxInline) {
-    Cord::ChunkIterator it = chunk_begin();
+    Cord::InternalChunkIterator it = internal_chunk_begin();
     it.AdvanceBytes(pos);
     char* dest = sub_cord.contents_.data_;
     size_t remaining_size = new_size;
@@ -1113,11 +1119,12 @@ Cord Cord::Subcord(size_t pos, size_t new_size) const {
 
 class CordForest {
  public:
-  explicit CordForest(size_t length)
-      : root_length_(length), trees_(kMinLengthSize, nullptr) {}
+  explicit CordForest(size_t length) : root_length_(length), trees_({}) {}
 
   void Build(CordRep* cord_root) {
-    std::vector<CordRep*> pending = {cord_root};
+    // We are adding up to two nodes to the `pending` list, but we also popping
+    // one, so the size of `pending` will never exceed `MaxCordDepth()`.
+    cord_internal::CordTreeMutablePath pending(cord_root);
 
     while (!pending.empty()) {
       CordRep* node = pending.back();
@@ -1129,21 +1136,20 @@ class CordForest {
       }
 
       CordRepConcat* concat_node = node->concat();
-      if (concat_node->depth() >= kMinLengthSize ||
-          concat_node->length < min_length[concat_node->depth()]) {
-        pending.push_back(concat_node->right);
-        pending.push_back(concat_node->left);
-
-        if (concat_node->refcount.IsOne()) {
-          concat_node->left = concat_freelist_;
-          concat_freelist_ = concat_node;
-        } else {
-          Ref(concat_node->right);
-          Ref(concat_node->left);
-          Unref(concat_node);
-        }
-      } else {
+      if (IsNodeBalanced(concat_node)) {
         AddNode(node);
+        continue;
+      }
+      pending.push_back(concat_node->right);
+      pending.push_back(concat_node->left);
+
+      if (concat_node->refcount.IsOne()) {
+        concat_node->left = concat_freelist_;
+        concat_freelist_ = concat_node;
+      } else {
+        Ref(concat_node->right);
+        Ref(concat_node->left);
+        Unref(concat_node);
       }
     }
   }
@@ -1175,7 +1181,7 @@ class CordForest {
 
     // Collect together everything with which we will merge with node
     int i = 0;
-    for (; node->length > min_length[i + 1]; ++i) {
+    for (; node->length >= kMinLength[i + 1]; ++i) {
       auto& tree_at_i = trees_[i];
 
       if (tree_at_i == nullptr) continue;
@@ -1186,7 +1192,7 @@ class CordForest {
     sum = AppendNode(node, sum);
 
     // Insert sum into appropriate place in the forest
-    for (; sum->length >= min_length[i]; ++i) {
+    for (; sum->length >= kMinLength[i]; ++i) {
       auto& tree_at_i = trees_[i];
       if (tree_at_i == nullptr) continue;
 
@@ -1194,7 +1200,7 @@ class CordForest {
       tree_at_i = nullptr;
     }
 
-    // min_length[0] == 1, which means sum->length >= min_length[0]
+    // kMinLength[0] == 1, which means sum->length >= kMinLength[0]
     assert(i > 0);
     trees_[i - 1] = sum;
   }
@@ -1227,9 +1233,7 @@ class CordForest {
   }
 
   size_t root_length_;
-
-  // use an inlined vector instead of a flat array to get bounds checking
-  absl::InlinedVector<CordRep*, kInlinedVectorSize> trees_;
+  std::array<cord_internal::CordRep*, cord_internal::MaxCordDepth()> trees_;
 
   // List of concat nodes we can re-use for Cord balancing.
   CordRepConcat* concat_freelist_ = nullptr;
@@ -1330,7 +1334,7 @@ inline absl::string_view Cord::InlineRep::FindFlatStartPiece() const {
 
 inline int Cord::CompareSlowPath(absl::string_view rhs, size_t compared_size,
                                  size_t size_to_compare) const {
-  auto advance = [](Cord::ChunkIterator* it, absl::string_view* chunk) {
+  auto advance = [](Cord::InternalChunkIterator* it, absl::string_view* chunk) {
     if (!chunk->empty()) return true;
     ++*it;
     if (it->bytes_remaining_ == 0) return false;
@@ -1338,7 +1342,7 @@ inline int Cord::CompareSlowPath(absl::string_view rhs, size_t compared_size,
     return true;
   };
 
-  Cord::ChunkIterator lhs_it = chunk_begin();
+  Cord::InternalChunkIterator lhs_it = internal_chunk_begin();
 
   // compared_size is inside first chunk.
   absl::string_view lhs_chunk =
@@ -1360,7 +1364,7 @@ inline int Cord::CompareSlowPath(absl::string_view rhs, size_t compared_size,
 
 inline int Cord::CompareSlowPath(const Cord& rhs, size_t compared_size,
                                  size_t size_to_compare) const {
-  auto advance = [](Cord::ChunkIterator* it, absl::string_view* chunk) {
+  auto advance = [](Cord::InternalChunkIterator* it, absl::string_view* chunk) {
     if (!chunk->empty()) return true;
     ++*it;
     if (it->bytes_remaining_ == 0) return false;
@@ -1368,8 +1372,8 @@ inline int Cord::CompareSlowPath(const Cord& rhs, size_t compared_size,
     return true;
   };
 
-  Cord::ChunkIterator lhs_it = chunk_begin();
-  Cord::ChunkIterator rhs_it = rhs.chunk_begin();
+  Cord::InternalChunkIterator lhs_it = internal_chunk_begin();
+  Cord::InternalChunkIterator rhs_it = rhs.internal_chunk_begin();
 
   // compared_size is inside both first chunks.
   absl::string_view lhs_chunk =
@@ -1503,8 +1507,11 @@ void Cord::CopyToArraySlowPath(char* dst) const {
   }
 }
 
-Cord::ChunkIterator& Cord::ChunkIterator::operator++() {
-  assert(bytes_remaining_ > 0 && "Attempted to iterate past `end()`");
+template <typename StorageType>
+Cord::GenericChunkIterator<StorageType>&
+Cord::GenericChunkIterator<StorageType>::operator++() {
+  ABSL_HARDENING_ASSERT(bytes_remaining_ > 0 &&
+                        "Attempted to iterate past `end()`");
   assert(bytes_remaining_ >= current_chunk_.size());
   bytes_remaining_ -= current_chunk_.size();
 
@@ -1542,8 +1549,10 @@ Cord::ChunkIterator& Cord::ChunkIterator::operator++() {
   return *this;
 }
 
-Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) {
-  assert(bytes_remaining_ >= n && "Attempted to iterate past `end()`");
+template <typename StorageType>
+Cord Cord::GenericChunkIterator<StorageType>::AdvanceAndReadBytes(size_t n) {
+  ABSL_HARDENING_ASSERT(bytes_remaining_ >= n &&
+                        "Attempted to iterate past `end()`");
   Cord subcord;
 
   if (n <= InlineRep::kMaxInline) {
@@ -1655,7 +1664,8 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) {
   return subcord;
 }
 
-void Cord::ChunkIterator::AdvanceBytesSlowPath(size_t n) {
+template <typename StorageType>
+void Cord::GenericChunkIterator<StorageType>::AdvanceBytesSlowPath(size_t n) {
   assert(bytes_remaining_ >= n && "Attempted to iterate past `end()`");
   assert(n >= current_chunk_.size());  // This should only be called when
                                        // iterating to a new node.
@@ -1714,7 +1724,7 @@ void Cord::ChunkIterator::AdvanceBytesSlowPath(size_t n) {
 }
 
 char Cord::operator[](size_t i) const {
-  assert(i < size());
+  ABSL_HARDENING_ASSERT(i < size());
   size_t offset = i;
   const CordRep* rep = contents_.tree();
   if (rep == nullptr) {
@@ -1841,18 +1851,18 @@ absl::string_view Cord::FlattenSlowPath() {
   }
 }
 
-static void DumpNode(CordRep* rep, bool include_data, std::ostream* os) {
+static void DumpNode(const CordRep* rep, bool include_data, std::ostream* os) {
   const int kIndentStep = 1;
   int indent = 0;
-  absl::InlinedVector<CordRep*, kInlinedVectorSize> stack;
-  absl::InlinedVector<int, kInlinedVectorSize> indents;
+  cord_internal::CordTreeConstPath stack;
+  cord_internal::CordTreePath<int, cord_internal::MaxCordDepth()> indents;
   for (;;) {
     *os << std::setw(3) << rep->refcount.Get();
     *os << " " << std::setw(7) << rep->length;
     *os << " [";
-    if (include_data) *os << static_cast<void*>(rep);
+    if (include_data) *os << static_cast<const void*>(rep);
     *os << "]";
-    *os << " " << (IsRootBalanced(rep) ? 'b' : 'u');
+    *os << " " << (IsNodeBalanced(rep) ? 'b' : 'u');
     *os << " " << std::setw(indent) << "";
     if (rep->tag == CONCAT) {
       *os << "CONCAT depth=" << Depth(rep) << "\n";
@@ -1873,7 +1883,7 @@ static void DumpNode(CordRep* rep, bool include_data, std::ostream* os) {
       } else {
         *os << "FLAT cap=" << TagToLength(rep->tag) << " [";
         if (include_data)
-          *os << absl::CEscape(std::string(rep->data, rep->length));
+          *os << absl::CEscape(absl::string_view(rep->data, rep->length));
         *os << "]\n";
       }
       if (stack.empty()) break;
@@ -1886,19 +1896,19 @@ static void DumpNode(CordRep* rep, bool include_data, std::ostream* os) {
   ABSL_INTERNAL_CHECK(indents.empty(), "");
 }
 
-static std::string ReportError(CordRep* root, CordRep* node) {
+static std::string ReportError(const CordRep* root, const CordRep* node) {
   std::ostringstream buf;
   buf << "Error at node " << node << " in:";
   DumpNode(root, true, &buf);
   return buf.str();
 }
 
-static bool VerifyNode(CordRep* root, CordRep* start_node,
+static bool VerifyNode(const CordRep* root, const CordRep* start_node,
                        bool full_validation) {
-  absl::InlinedVector<CordRep*, 2> worklist;
+  cord_internal::CordTreeConstPath worklist;
   worklist.push_back(start_node);
   do {
-    CordRep* node = worklist.back();
+    const CordRep* node = worklist.back();
     worklist.pop_back();
 
     ABSL_INTERNAL_CHECK(node != nullptr, ReportError(root, node));
@@ -1948,7 +1958,7 @@ static bool VerifyNode(CordRep* root, CordRep* start_node,
   // Iterate over the tree. cur_node is never a leaf node and leaf nodes will
   // never be appended to tree_stack. This reduces overhead from manipulating
   // tree_stack.
-  absl::InlinedVector<const CordRep*, kInlinedVectorSize> tree_stack;
+  cord_internal::CordTreeConstPath tree_stack;
   const CordRep* cur_node = rep;
   while (true) {
     const CordRep* next_node = nullptr;
@@ -1995,6 +2005,9 @@ std::ostream& operator<<(std::ostream& out, const Cord& cord) {
   return out;
 }
 
+template class Cord::GenericChunkIterator<cord_internal::CordTreeMutablePath>;
+template class Cord::GenericChunkIterator<cord_internal::CordTreeDynamicPath>;
+
 namespace strings_internal {
 size_t CordTestAccess::FlatOverhead() { return kFlatOverhead; }
 size_t CordTestAccess::MaxFlatLength() { return kMaxFlatLength; }
diff --git a/absl/strings/cord.h b/absl/strings/cord.h
index 66645eef6e48..3ab3cb87f520 100644
--- a/absl/strings/cord.h
+++ b/absl/strings/cord.h
@@ -11,25 +11,52 @@
 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 // See the License for the specific language governing permissions and
 // limitations under the License.
-
-// A Cord is a sequence of characters with some unusual access propreties.
-// A Cord supports efficient insertions and deletions at the start and end of
-// the byte sequence, but random access reads are slower, and random access
-// modifications are not supported by the API.  Cord also provides cheap copies
-// (using a copy-on-write strategy) and cheap substring operations.
 //
-// Thread safety
-// -------------
+// -----------------------------------------------------------------------------
+// File: cord.h
+// -----------------------------------------------------------------------------
+//
+// This file defines the `absl::Cord` data structure and operations on that data
+// structure. A Cord is a string-like sequence of characters optimized for
+// specific use cases. Unlike a `std::string`, which stores an array of
+// contiguous characters, Cord data is stored in a structure consisting of
+// separate, reference-counted "chunks." (Currently, this implementation is a
+// tree structure, though that implementation may change.)
+//
+// Because a Cord consists of these chunks, data can be added to or removed from
+// a Cord during its lifetime. Chunks may also be shared between Cords. Unlike a
+// `std::string`, a Cord can therefore accomodate data that changes over its
+// lifetime, though it's not quite "mutable"; it can change only in the
+// attachment, detachment, or rearrangement of chunks of its constituent data.
+//
+// A Cord provides some benefit over `std::string` under the following (albeit
+// narrow) circumstances:
+//
+//   * Cord data is designed to grow and shrink over a Cord's lifetime. Cord
+//     provides efficient insertions and deletions at the start and end of the
+//     character sequences, avoiding copies in those cases. Static data should
+//     generally be stored as strings.
+//   * External memory consisting of string-like data can be directly added to
+//     a Cord without requiring copies or allocations.
+//   * Cord data may be shared and copied cheaply. Cord provides a copy-on-write
+//     implementation and cheap sub-Cord operations. Copying a Cord is an O(1)
+//     operation.
+//
+// As a consequence to the above, Cord data is generally large. Small data
+// should generally use strings, as construction of a Cord requires some
+// overhead. Small Cords (<= 15 bytes) are represented inline, but most small
+// Cords are expected to grow over their lifetimes.
+//
+// Note that because a Cord is made up of separate chunked data, random access
+// to character data within a Cord is slower than within a `std::string`.
+//
+// Thread Safety
+//
 // Cord has the same thread-safety properties as many other types like
 // std::string, std::vector<>, int, etc -- it is thread-compatible. In
-// particular, if no thread may call a non-const method, then it is safe to
-// concurrently call const methods. Copying a Cord produces a new instance that
-// can be used concurrently with the original in arbitrary ways.
-//
-// Implementation is similar to the "Ropes" described in:
-//    Ropes: An alternative to strings
-//    Hans J. Boehm, Russ Atkinson, Michael Plass
-//    Software Practice and Experience, December 1995
+// particular, if threads do not call non-const methods, then it is safe to call
+// const methods without synchronization. Copying a Cord produces a new instance
+// that can be used concurrently with the original in arbitrary ways.
 
 #ifndef ABSL_STRINGS_CORD_H_
 #define ABSL_STRINGS_CORD_H_
@@ -68,6 +95,90 @@ template <typename H>
 H HashFragmentedCord(H, const Cord&);
 }
 
+// Cord
+//
+// A Cord is a sequence of characters, designed to be more efficient than a
+// `std::string` in certain circumstances: namely, large string data that needs
+// to change over its lifetime or shared, especially when such data is shared
+// across API boundaries.
+//
+// A Cord stores its character data in a structure that allows efficient prepend
+// and append operations. This makes a Cord useful for large string data sent
+// over in a wire format that may need to be prepended or appended at some point
+// during the data exchange (e.g. HTTP, protocol buffers). For example, a
+// Cord is useful for storing an HTTP request, and prepending an HTTP header to
+// such a request.
+//
+// Cords should not be used for storing general string data, however. They
+// require overhead to construct and are slower than strings for random access.
+//
+// The Cord API provides the following common API operations:
+//
+// * Create or assign Cords out of existing string data, memory, or other Cords
+// * Append and prepend data to an existing Cord
+// * Create new Sub-Cords from existing Cord data
+// * Swap Cord data and compare Cord equality
+// * Write out Cord data by constructing a `std::string`
+//
+// Additionally, the API provides iterator utilities to iterate through Cord
+// data via chunks or character bytes.
+//
+
+namespace cord_internal {
+
+// It's expensive to keep a Cord's tree perfectly balanced, so instead we keep
+// trees approximately balanced.  A tree node N of depth D(N) that contains a
+// string of L(N) characters is considered balanced if L >= Fibonacci(D + 2).
+// The "+ 2" is used to ensure that every balanced leaf node contains at least
+//  one character. Here we presume that
+//   Fibonacci(0) = 0
+//   Fibonacci(1) = 1
+//   Fibonacci(2) = 1
+//   Fibonacci(3) = 2
+//   ...
+// The algorithm is based on paper by Hans Boehm et al:
+// https://www.cs.rit.edu/usr/local/pub/jeh/courses/QUARTERS/FP/Labs/CedarRope/rope-paper.pdf
+// In this paper authors shows that rebalancing based on cord forest of already
+// balanced subtrees can be proven to never produce tree of depth larger than
+// largest Fibonacci number representable in the same integral type as cord size
+// For 64 bit integers this is the 93rd Fibonacci number. For 32 bit integrals
+// this is 47th Fibonacci number.
+constexpr size_t MaxCordDepth() { return sizeof(size_t) == 8 ? 93 : 47; }
+
+// This class models fixed max size stack of CordRep pointers.
+// The elements are being pushed back and popped from the back.
+template <typename CordRepPtr, size_t N>
+class CordTreePath {
+ public:
+  CordTreePath() {}
+  explicit CordTreePath(CordRepPtr root) { push_back(root); }
+
+  bool empty() const { return size_ == 0; }
+  size_t size() const { return size_; }
+  void clear() { size_ = 0; }
+
+  CordRepPtr back() { return data_[size_ - 1]; }
+
+  void pop_back() {
+    --size_;
+    assert(size_ < N);
+  }
+  void push_back(CordRepPtr elem) { data_[size_++] = elem; }
+
+ private:
+  CordRepPtr data_[N];
+  size_t size_ = 0;
+};
+
+// Fixed length container for mutable "path" in cord tree, which can hold any
+// possible valid path in cord tree.
+using CordTreeMutablePath = CordTreePath<CordRep*, MaxCordDepth()>;
+// Variable length container for mutable "path" in cord tree. It starts with
+// capacity for 15 elements and grow if necessary.
+using CordTreeDynamicPath =
+    absl::InlinedVector<absl::cord_internal::CordRep*, 15>;
+}  // namespace cord_internal
+
 // A Cord is a sequence of characters.
 class Cord {
  private:
@@ -75,53 +186,124 @@ class Cord {
   using EnableIfString =
       absl::enable_if_t<std::is_same<T, std::string>::value, int>;
 
+  //----------------------------------------------------------------------------
+  // Cord::GenericChunkIterator
+  //----------------------------------------------------------------------------
+  //
+  // A `Cord::GenericChunkIterator` provides an interface for the standard
+  // `Cord::ChunkIterator` as well as some private implementations.
+  template <typename StorageType>
+  class GenericChunkIterator {
+   public:
+    using iterator_category = std::input_iterator_tag;
+    using value_type = absl::string_view;
+    using difference_type = ptrdiff_t;
+    using pointer = const value_type*;
+    using reference = value_type;
+
+    GenericChunkIterator() = default;
+
+    GenericChunkIterator& operator++();
+    GenericChunkIterator operator++(int);
+    bool operator==(const GenericChunkIterator& other) const;
+    bool operator!=(const GenericChunkIterator& other) const;
+    reference operator*() const;
+    pointer operator->() const;
+
+    friend class Cord;
+    friend class CharIterator;
+
+   private:
+    // Constructs a `begin()` iterator from `cord`.
+    explicit GenericChunkIterator(const Cord* cord);
+
+    // Removes `n` bytes from `current_chunk_`. Expects `n` to be smaller than
+    // `current_chunk_.size()`.
+    void RemoveChunkPrefix(size_t n);
+    Cord AdvanceAndReadBytes(size_t n);
+    void AdvanceBytes(size_t n);
+    // Iterates `n` bytes, where `n` is expected to be greater than or equal to
+    // `current_chunk_.size()`.
+    void AdvanceBytesSlowPath(size_t n);
+
+    // A view into bytes of the current `CordRep`. It may only be a view to a
+    // suffix of bytes if this is being used by `CharIterator`.
+    absl::string_view current_chunk_;
+    // The current leaf, or `nullptr` if the iterator points to short data.
+    // If the current chunk is a substring node, current_leaf_ points to the
+    // underlying flat or external node.
+    cord_internal::CordRep* current_leaf_ = nullptr;
+    // The number of bytes left in the `Cord` over which we are iterating.
+    size_t bytes_remaining_ = 0;
+    StorageType stack_of_right_children_;
+  };
+  template <typename IteratorType>
+  class GenericChunkRange {
+   public:
+    explicit GenericChunkRange(const Cord* cord) : cord_(cord) {}
+
+    IteratorType begin() const { return IteratorType(cord_); }
+    IteratorType end() const { return IteratorType(); }
+
+   private:
+    const Cord* cord_;
+  };
+
  public:
-  // --------------------------------------------------------------------
-  // Constructors, destructors and helper factories
+  // Cord::Cord() Constructors
 
-  // Create an empty cord
+  // Creates an empty Cord
   constexpr Cord() noexcept;
 
-  // Cord is copyable and efficiently movable.
-  // The moved-from state is valid but unspecified.
+  // Creates a Cord from an existing Cord. Cord is copyable and efficiently
+  // movable. The moved-from state is valid but unspecified.
   Cord(const Cord& src);
   Cord(Cord&& src) noexcept;
   Cord& operator=(const Cord& x);
   Cord& operator=(Cord&& x) noexcept;
 
-  // Create a cord out of "src". This constructor is explicit on
-  // purpose so that people do not get automatic type conversions.
+  // Creates a Cord from a `src` string. This constructor is marked explicit to
+  // prevent implicit Cord constructions from arguments convertible to an
+  // `absl::string_view`.
   explicit Cord(absl::string_view src);
   Cord& operator=(absl::string_view src);
 
-  // These are templated to avoid ambiguities for types that are convertible to
-  // both `absl::string_view` and `std::string`, such as `const char*`.
+  // Creates a Cord from a `std::string&&` rvalue. These constructors are
+  // templated to avoid ambiguities for types that are convertible to both
+  // `absl::string_view` and `std::string`, such as `const char*`.
   //
-  // Note that these functions reserve the right to reuse the `string&&`'s
+  // Note that these functions reserve the right to use the `string&&`'s
   // memory and that they will do so in the future.
   template <typename T, EnableIfString<T> = 0>
   explicit Cord(T&& src) : Cord(absl::string_view(src)) {}
   template <typename T, EnableIfString<T> = 0>
   Cord& operator=(T&& src);
 
-  // Destroy the cord
+  // Cord::~Cord()
+  //
+  // Destructs the Cord
   ~Cord() {
     if (contents_.is_tree()) DestroyCordSlow();
   }
 
-  // Creates a Cord that takes ownership of external memory. The contents of
-  // `data` are not copied.
+  // Cord::MakeCordFromExternal(data, callable)
+  //
+  // Creates a Cord that takes ownership of external string memory. The
+  // contents of `data` are not copied to the Cord; instead, the external
+  // memory is added to the Cord and reference-counted. This data may not be
+  // changed for the life of the Cord, though it may be prepended or appended
+  // to.
+  //
+  // `MakeCordFromExternal()` takes a callable "releaser" that is invoked when
+  // the reference count for `data` reaches zero. As noted above, this data must
+  // remain live until the releaser is invoked. The callable releaser also must:
   //
-  // This function takes a callable that is invoked when all Cords are
-  // finished with `data`. The data must remain live and unchanging until the
-  // releaser is called. The requirements for the releaser are that it:
-  //   * is move constructible,
-  //   * supports `void operator()(absl::string_view) const` or
-  //     `void operator()() const`,
-  //   * does not have alignment requirement greater than what is guaranteed by
-  //     ::operator new. This is dictated by alignof(std::max_align_t) before
-  //     C++17 and __STDCPP_DEFAULT_NEW_ALIGNMENT__ if compiling with C++17 or
-  //     it is supported by the implementation.
+  //   * be move constructible
+  //   * support `void operator()(absl::string_view) const` or `void operator()`
+  //   * not have alignment requirement greater than what is guaranteed by
+  //     `::operator new`. This alignment is dictated by
+  //     `alignof(std::max_align_t)` (pre-C++17 code) or
+  //     `__STDCPP_DEFAULT_NEW_ALIGNMENT__` (C++17 code).
   //
   // Example:
   //
@@ -135,8 +317,8 @@ class Cord {
   //       });
   // }
   //
-  // WARNING: It's likely a bug if your releaser doesn't do anything.
-  // For example, consider the following:
+  // WARNING: Because a Cord can be reference-counted, it's likely a bug if your
+  // releaser doesn't do anything. For example, consider the following:
   //
   // void Foo(const char* buffer, int len) {
   //   auto c = absl::MakeCordFromExternal(absl::string_view(buffer, len),
@@ -150,67 +332,100 @@ class Cord {
   template <typename Releaser>
   friend Cord MakeCordFromExternal(absl::string_view data, Releaser&& releaser);
 
-  // --------------------------------------------------------------------
-  // Mutations
-
+  // Cord::Clear()
+  //
+  // Releases the Cord data. Any nodes that share data with other Cords, if
+  // applicable, will have their reference counts reduced by 1.
   void Clear();
 
+  // Cord::Append()
+  //
+  // Appends data to the Cord, which may come from another Cord or other string
+  // data.
   void Append(const Cord& src);
   void Append(Cord&& src);
   void Append(absl::string_view src);
   template <typename T, EnableIfString<T> = 0>
   void Append(T&& src);
 
+  // Cord::Prepend()
+  //
+  // Prepends data to the Cord, which may come from another Cord or other string
+  // data.
   void Prepend(const Cord& src);
   void Prepend(absl::string_view src);
   template <typename T, EnableIfString<T> = 0>
   void Prepend(T&& src);
 
+  // Cord::RemovePrefix()
+  //
+  // Removes the first `n` bytes of a Cord.
   void RemovePrefix(size_t n);
   void RemoveSuffix(size_t n);
 
-  // Returns a new cord representing the subrange [pos, pos + new_size) of
+  // Cord::Subcord()
+  //
+  // Returns a new Cord representing the subrange [pos, pos + new_size) of
   // *this. If pos >= size(), the result is empty(). If
   // (pos + new_size) >= size(), the result is the subrange [pos, size()).
   Cord Subcord(size_t pos, size_t new_size) const;
 
+  // swap()
+  //
+  // Swaps the data of Cord `x` with Cord `y`.
   friend void swap(Cord& x, Cord& y) noexcept;
 
-  // --------------------------------------------------------------------
-  // Accessors
-
+  // Cord::size()
+  //
+  // Returns the size of the Cord.
   size_t size() const;
+
+  // Cord::empty()
+  //
+  // Determines whether the given Cord is empty, returning `true` is so.
   bool empty() const;
 
-  // Returns the approximate number of bytes pinned by this Cord.  Note that
-  // Cords that share memory could each be "charged" independently for the same
-  // shared memory.
+  // Cord:EstimatedMemoryUsage()
+  //
+  // Returns the *approximate* number of bytes held in full or in part by this
+  // Cord (which may not remain the same between invocations).  Note that Cords
+  // that share memory could each be "charged" independently for the same shared
+  // memory.
   size_t EstimatedMemoryUsage() const;
 
-  // --------------------------------------------------------------------
-  // Comparators
-
-  // Compares 'this' Cord with rhs. This function and its relatives
-  // treat Cords as sequences of unsigned bytes. The comparison is a
-  // straightforward lexicographic comparison. Return value:
+  // Cord::Compare()
+  //
+  // Compares 'this' Cord with rhs. This function and its relatives treat Cords
+  // as sequences of unsigned bytes. The comparison is a straightforward
+  // lexicographic comparison. `Cord::Compare()` returns values as follows:
+  //
   //   -1  'this' Cord is smaller
   //    0  two Cords are equal
   //    1  'this' Cord is larger
   int Compare(absl::string_view rhs) const;
   int Compare(const Cord& rhs) const;
 
-  // Does 'this' cord start/end with rhs
+  // Cord::StartsWith()
+  //
+  // Determines whether the Cord starts with the passed string data `rhs`.
   bool StartsWith(const Cord& rhs) const;
   bool StartsWith(absl::string_view rhs) const;
+
+  // Cord::EndsWidth()
+  //
+  // Determines whether the Cord ends with the passed string data `rhs`.
   bool EndsWith(absl::string_view rhs) const;
   bool EndsWith(const Cord& rhs) const;
 
-  // --------------------------------------------------------------------
-  // Conversion to other types
-
+  // Cord::operator std::string()
+  //
+  // Converts a Cord into a `std::string()`. This operator is marked explicit to
+  // prevent unintended Cord usage in functions that take a string.
   explicit operator std::string() const;
 
-  // Copies the contents from `src` to `*dst`.
+  // CopyCordToString()
+  //
+  // Copies the contents of a `src` Cord into a `*dst` string.
   //
   // This function optimizes the case of reusing the destination string since it
   // can reuse previously allocated capacity. However, this function does not
@@ -219,80 +434,46 @@ class Cord {
   // object, prefer to simply use the conversion operator to `std::string`.
   friend void CopyCordToString(const Cord& src, std::string* dst);
 
-  // --------------------------------------------------------------------
-  // Iteration
-
   class CharIterator;
 
-  // Type for iterating over the chunks of a `Cord`. See comments for
-  // `Cord::chunk_begin()`, `Cord::chunk_end()` and `Cord::Chunks()` below for
-  // preferred usage.
+  //----------------------------------------------------------------------------
+  // Cord::ChunkIterator
+  //----------------------------------------------------------------------------
+  //
+  // A `Cord::ChunkIterator` allows iteration over the constituent chunks of its
+  // Cord. Such iteration allows you to perform non-const operatons on the data
+  // of a Cord without modifying it.
+  //
+  // Generally, you do not instantiate a `Cord::ChunkIterator` directly;
+  // instead, you create one implicitly through use of the `Cord::Chunks()`
+  // member function.
   //
-  // Additional notes:
+  // The `Cord::ChunkIterator` has the following properties:
+  //
+  //   * The iterator is invalidated after any non-const operation on the
+  //     Cord object over which it iterates.
   //   * The `string_view` returned by dereferencing a valid, non-`end()`
   //     iterator is guaranteed to be non-empty.
-  //   * A `ChunkIterator` object is invalidated after any non-const
-  //     operation on the `Cord` object over which it iterates.
-  //   * Two `ChunkIterator` objects can be equality compared if and only if
-  //     they remain valid and iterate over the same `Cord`.
-  //   * This is a proxy iterator. This means the `string_view` returned by the
-  //     iterator does not live inside the Cord, and its lifetime is limited to
-  //     the lifetime of the iterator itself. To help prevent issues,
-  //     `ChunkIterator::reference` is not a true reference type and is
-  //     equivalent to `value_type`.
-  //   * The iterator keeps state that can grow for `Cord`s that contain many
+  //   * Two `ChunkIterator` objects can be compared equal if and only if they
+  //     remain valid and iterate over the same Cord.
+  //   * The iterator in this case is a proxy iterator; the `string_view`
+  //     returned by the iterator does not live inside the Cord, and its
+  //     lifetime is limited to the lifetime of the iterator itself. To help
+  //     prevent lifetime issues, `ChunkIterator::reference` is not a true
+  //     reference type and is equivalent to `value_type`.
+  //   * The iterator keeps state that can grow for Cords that contain many
   //     nodes and are imbalanced due to sharing. Prefer to pass this type by
   //     const reference instead of by value.
-  class ChunkIterator {
-   public:
-    using iterator_category = std::input_iterator_tag;
-    using value_type = absl::string_view;
-    using difference_type = ptrdiff_t;
-    using pointer = const value_type*;
-    using reference = value_type;
-
-    ChunkIterator() = default;
-
-    ChunkIterator& operator++();
-    ChunkIterator operator++(int);
-    bool operator==(const ChunkIterator& other) const;
-    bool operator!=(const ChunkIterator& other) const;
-    reference operator*() const;
-    pointer operator->() const;
-
-    friend class Cord;
-    friend class CharIterator;
-
-   private:
-    // Constructs a `begin()` iterator from `cord`.
-    explicit ChunkIterator(const Cord* cord);
-
-    // Removes `n` bytes from `current_chunk_`. Expects `n` to be smaller than
-    // `current_chunk_.size()`.
-    void RemoveChunkPrefix(size_t n);
-    Cord AdvanceAndReadBytes(size_t n);
-    void AdvanceBytes(size_t n);
-    // Iterates `n` bytes, where `n` is expected to be greater than or equal to
-    // `current_chunk_.size()`.
-    void AdvanceBytesSlowPath(size_t n);
-
-    // A view into bytes of the current `CordRep`. It may only be a view to a
-    // suffix of bytes if this is being used by `CharIterator`.
-    absl::string_view current_chunk_;
-    // The current leaf, or `nullptr` if the iterator points to short data.
-    // If the current chunk is a substring node, current_leaf_ points to the
-    // underlying flat or external node.
-    absl::cord_internal::CordRep* current_leaf_ = nullptr;
-    // The number of bytes left in the `Cord` over which we are iterating.
-    size_t bytes_remaining_ = 0;
-    absl::InlinedVector<absl::cord_internal::CordRep*, 4>
-        stack_of_right_children_;
-  };
+  using ChunkIterator =
+      GenericChunkIterator<cord_internal::CordTreeDynamicPath>;
 
+  // Cord::ChunkIterator::chunk_begin()
+  //
   // Returns an iterator to the first chunk of the `Cord`.
   //
-  // This is useful for getting a `ChunkIterator` outside the context of a
-  // range-based for-loop (in which case see `Cord::Chunks()` below).
+  // Generally, prefer using `Cord::Chunks()` within a range-based for loop for
+  // iterating over the chunks of a Cord. This method may be useful for getting
+  // a `ChunkIterator` where range-based for-loops are not useful.
   //
   // Example:
   //
@@ -301,26 +482,35 @@ class Cord {
   //     return std::find(c.chunk_begin(), c.chunk_end(), s);
   //   }
   ChunkIterator chunk_begin() const;
+
+  // Cord::ChunkItertator::chunk_end()
+  //
   // Returns an iterator one increment past the last chunk of the `Cord`.
+  //
+  // Generally, prefer using `Cord::Chunks()` within a range-based for loop for
+  // iterating over the chunks of a Cord. This method may be useful for getting
+  // a `ChunkIterator` where range-based for-loops may not be available.
   ChunkIterator chunk_end() const;
 
-  // Convenience wrapper over `Cord::chunk_begin()` and `Cord::chunk_end()` to
-  // enable range-based for-loop iteration over `Cord` chunks.
+  //----------------------------------------------------------------------------
+  // Cord::ChunkIterator::ChunkRange
+  //----------------------------------------------------------------------------
   //
-  // Prefer to use `Cord::Chunks()` below instead of constructing this directly.
-  class ChunkRange {
-   public:
-    explicit ChunkRange(const Cord* cord) : cord_(cord) {}
-
-    ChunkIterator begin() const;
-    ChunkIterator end() const;
-
-   private:
-    const Cord* cord_;
-  };
+  // `ChunkRange` is a helper class for iterating over the chunks of the `Cord`,
+  // producing an iterator which can be used within a range-based for loop.
+  // Construction of a `ChunkRange` will return an iterator pointing to the
+  // first chunk of the Cord. Generally, do not construct a `ChunkRange`
+  // directly; instead, prefer to use the `Cord::Chunks()` method.
+  //
+  // Implementation note: `ChunkRange` is simply a convenience wrapper over
+  // `Cord::chunk_begin()` and `Cord::chunk_end()`.
+  using ChunkRange = GenericChunkRange<ChunkIterator>;
 
-  // Returns a range for iterating over the chunks of a `Cord` with a
-  // range-based for-loop.
+  // Cord::Chunks()
+  //
+  // Returns a `Cord::ChunkIterator::ChunkRange` for iterating over the chunks
+  // of a `Cord` with a range-based for-loop. For most iteration tasks on a
+  // Cord, use `Cord::Chunks()` to retrieve this iterator.
   //
   // Example:
   //
@@ -337,22 +527,30 @@ class Cord {
   //   }
   ChunkRange Chunks() const;
 
-  // Type for iterating over the characters of a `Cord`. See comments for
-  // `Cord::char_begin()`, `Cord::char_end()` and `Cord::Chars()` below for
-  // preferred usage.
+  //----------------------------------------------------------------------------
+  // Cord::CharIterator
+  //----------------------------------------------------------------------------
+  //
+  // A `Cord::CharIterator` allows iteration over the constituent characters of
+  // a `Cord`.
+  //
+  // Generally, you do not instantiate a `Cord::CharIterator` directly; instead,
+  // you create one implicitly through use of the `Cord::Chars()` member
+  // function.
+  //
+  // A `Cord::CharIterator` has the following properties:
   //
-  // Additional notes:
-  //   * A `CharIterator` object is invalidated after any non-const
-  //     operation on the `Cord` object over which it iterates.
-  //   * Two `CharIterator` objects can be equality compared if and only if
-  //     they remain valid and iterate over the same `Cord`.
-  //   * The iterator keeps state that can grow for `Cord`s that contain many
+  //   * The iterator is invalidated after any non-const operation on the
+  //     Cord object over which it iterates.
+  //   * Two `CharIterator` objects can be compared equal if and only if they
+  //     remain valid and iterate over the same Cord.
+  //   * The iterator keeps state that can grow for Cords that contain many
   //     nodes and are imbalanced due to sharing. Prefer to pass this type by
   //     const reference instead of by value.
-  //   * This type cannot be a forward iterator because a `Cord` can reuse
-  //     sections of memory. This violates the requirement that if dereferencing
-  //     two iterators returns the same object, the iterators must compare
-  //     equal.
+  //   * This type cannot act as a forward iterator because a `Cord` can reuse
+  //     sections of memory. This fact violates the requirement for forward
+  //     iterators to compare equal if dereferencing them returns the same
+  //     object.
   class CharIterator {
    public:
     using iterator_category = std::input_iterator_tag;
@@ -378,34 +576,56 @@ class Cord {
     ChunkIterator chunk_iterator_;
   };
 
-  // Advances `*it` by `n_bytes` and returns the bytes passed as a `Cord`.
+  // Cord::CharIterator::AdvanceAndRead()
   //
-  // `n_bytes` must be less than or equal to the number of bytes remaining for
-  // iteration. Otherwise the behavior is undefined. It is valid to pass
-  // `char_end()` and 0.
+  // Advances the `Cord::CharIterator` by `n_bytes` and returns the bytes
+  // advanced as a separate `Cord`. `n_bytes` must be less than or equal to the
+  // number of bytes within the Cord; otherwise, behavior is undefined. It is
+  // valid to pass `char_end()` and `0`.
   static Cord AdvanceAndRead(CharIterator* it, size_t n_bytes);
 
-  // Advances `*it` by `n_bytes`.
+  // Cord::CharIterator::Advance()
   //
-  // `n_bytes` must be less than or equal to the number of bytes remaining for
-  // iteration. Otherwise the behavior is undefined. It is valid to pass
-  // `char_end()` and 0.
+  // Advances the `Cord::CharIterator` by `n_bytes`. `n_bytes` must be less than
+  // or equal to the number of bytes remaining within the Cord; otherwise,
+  // behavior is undefined. It is valid to pass `char_end()` and `0`.
   static void Advance(CharIterator* it, size_t n_bytes);
 
+  // Cord::CharIterator::ChunkRemaining()
+  //
   // Returns the longest contiguous view starting at the iterator's position.
   //
   // `it` must be dereferenceable.
   static absl::string_view ChunkRemaining(const CharIterator& it);
 
+  // Cord::CharIterator::char_begin()
+  //
   // Returns an iterator to the first character of the `Cord`.
+  //
+  // Generally, prefer using `Cord::Chars()` within a range-based for loop for
+  // iterating over the chunks of a Cord. This method may be useful for getting
+  // a `CharIterator` where range-based for-loops may not be available.
   CharIterator char_begin() const;
+
+  // Cord::CharIterator::char_end()
+  //
   // Returns an iterator to one past the last character of the `Cord`.
+  //
+  // Generally, prefer using `Cord::Chars()` within a range-based for loop for
+  // iterating over the chunks of a Cord. This method may be useful for getting
+  // a `CharIterator` where range-based for-loops are not useful.
   CharIterator char_end() const;
 
-  // Convenience wrapper over `Cord::char_begin()` and `Cord::char_end()` to
-  // enable range-based for-loop iterator over the characters of a `Cord`.
+  // Cord::CharIterator::CharRange
   //
-  // Prefer to use `Cord::Chars()` below instead of constructing this directly.
+  // `CharRange` is a helper class for iterating over the characters of a
+  // producing an iterator which can be used within a range-based for loop.
+  // Construction of a `CharRange` will return an iterator pointing to the first
+  // character of the Cord. Generally, do not construct a `CharRange` directly;
+  // instead, prefer to use the `Cord::Chars()` method show below.
+  //
+  // Implementation note: `CharRange` is simply a convenience wrapper over
+  // `Cord::char_begin()` and `Cord::char_end()`.
   class CharRange {
    public:
     explicit CharRange(const Cord* cord) : cord_(cord) {}
@@ -417,8 +637,11 @@ class Cord {
     const Cord* cord_;
   };
 
-  // Returns a range for iterating over the characters of a `Cord` with a
-  // range-based for-loop.
+  // Cord::CharIterator::Chars()
+  //
+  // Returns a `Cord::CharIterator` for iterating over the characters of a
+  // `Cord` with a range-based for-loop. For most character-based iteration
+  // tasks on a Cord, use `Cord::Chars()` to retrieve this iterator.
   //
   // Example:
   //
@@ -435,23 +658,26 @@ class Cord {
   //   }
   CharRange Chars() const;
 
-  // --------------------------------------------------------------------
-  // Miscellaneous
-
-  // Get the "i"th character of 'this' and return it.
-  // NOTE: This routine is reasonably efficient.  It is roughly
-  // logarithmic in the number of nodes that make up the cord.  Still,
-  // if you need to iterate over the contents of a cord, you should
-  // use a CharIterator/CordIterator rather than call operator[] or Get()
-  //  repeatedly in a loop.
+  // Cord::operator[]
+  //
+  // Get the "i"th character of the Cord and returns it, provided that
+  // 0 <= i < Cord.size().
   //
-  // REQUIRES: 0 <= i < size()
+  // NOTE: This routine is reasonably efficient. It is roughly
+  // logarithmic based on the number of chunks that make up the cord. Still,
+  // if you need to iterate over the contents of a cord, you should
+  // use a CharIterator/ChunkIterator rather than call operator[] or Get()
+  // repeatedly in a loop.
   char operator[](size_t i) const;
 
+  // Cord::TryFlat()
+  //
   // If this cord's representation is a single flat array, return a
   // string_view referencing that array.  Otherwise return nullopt.
   absl::optional<absl::string_view> TryFlat() const;
 
+  // Cord::Flatten()
+  //
   // Flattens the cord into a single array and returns a view of the data.
   //
   // If the cord was already flat, the contents are not modified.
@@ -574,6 +800,14 @@ class Cord {
   static bool GetFlatAux(absl::cord_internal::CordRep* rep,
                          absl::string_view* fragment);
 
+  // Iterators for use inside Cord implementation
+  using InternalChunkIterator =
+      GenericChunkIterator<cord_internal::CordTreeMutablePath>;
+  using InternalChunkRange = GenericChunkRange<InternalChunkIterator>;
+
+  InternalChunkIterator internal_chunk_begin() const;
+  InternalChunkRange InternalChunks() const;
+
   // Helper for ForEachChunk()
   static void ForEachChunkAux(
       absl::cord_internal::CordRep* rep,
@@ -608,6 +842,11 @@ class Cord {
   void AppendImpl(C&& src);
 };
 
+extern template class Cord::GenericChunkIterator<
+    cord_internal::CordTreeMutablePath>;
+extern template class Cord::GenericChunkIterator<
+    cord_internal::CordTreeDynamicPath>;
+
 ABSL_NAMESPACE_END
 }  // namespace absl
 
@@ -947,7 +1186,9 @@ inline bool Cord::StartsWith(absl::string_view rhs) const {
   return EqualsImpl(rhs, rhs_size);
 }
 
-inline Cord::ChunkIterator::ChunkIterator(const Cord* cord)
+template <typename StorageType>
+inline Cord::GenericChunkIterator<StorageType>::GenericChunkIterator(
+    const Cord* cord)
     : bytes_remaining_(cord->size()) {
   if (cord->empty()) return;
   if (cord->contents_.is_tree()) {
@@ -958,37 +1199,50 @@ inline Cord::ChunkIterator::ChunkIterator(const Cord* cord)
   }
 }
 
-inline Cord::ChunkIterator Cord::ChunkIterator::operator++(int) {
-  ChunkIterator tmp(*this);
+template <typename StorageType>
+inline Cord::GenericChunkIterator<StorageType>
+Cord::GenericChunkIterator<StorageType>::operator++(int) {
+  GenericChunkIterator tmp(*this);
   operator++();
   return tmp;
 }
 
-inline bool Cord::ChunkIterator::operator==(const ChunkIterator& other) const {
+template <typename StorageType>
+inline bool Cord::GenericChunkIterator<StorageType>::operator==(
+    const GenericChunkIterator<StorageType>& other) const {
   return bytes_remaining_ == other.bytes_remaining_;
 }
 
-inline bool Cord::ChunkIterator::operator!=(const ChunkIterator& other) const {
+template <typename StorageType>
+inline bool Cord::GenericChunkIterator<StorageType>::operator!=(
+    const GenericChunkIterator<StorageType>& other) const {
   return !(*this == other);
 }
 
-inline Cord::ChunkIterator::reference Cord::ChunkIterator::operator*() const {
-  assert(bytes_remaining_ != 0);
+template <typename StorageType>
+inline typename Cord::GenericChunkIterator<StorageType>::reference
+Cord::GenericChunkIterator<StorageType>::operator*() const {
+  ABSL_HARDENING_ASSERT(bytes_remaining_ != 0);
   return current_chunk_;
 }
 
-inline Cord::ChunkIterator::pointer Cord::ChunkIterator::operator->() const {
-  assert(bytes_remaining_ != 0);
+template <typename StorageType>
+inline typename Cord::GenericChunkIterator<StorageType>::pointer
+Cord::GenericChunkIterator<StorageType>::operator->() const {
+  ABSL_HARDENING_ASSERT(bytes_remaining_ != 0);
   return &current_chunk_;
 }
 
-inline void Cord::ChunkIterator::RemoveChunkPrefix(size_t n) {
+template <typename StorageType>
+inline void Cord::GenericChunkIterator<StorageType>::RemoveChunkPrefix(
+    size_t n) {
   assert(n < current_chunk_.size());
   current_chunk_.remove_prefix(n);
   bytes_remaining_ -= n;
 }
 
-inline void Cord::ChunkIterator::AdvanceBytes(size_t n) {
+template <typename StorageType>
+inline void Cord::GenericChunkIterator<StorageType>::AdvanceBytes(size_t n) {
   if (ABSL_PREDICT_TRUE(n < current_chunk_.size())) {
     RemoveChunkPrefix(n);
   } else if (n != 0) {
@@ -1002,14 +1256,6 @@ inline Cord::ChunkIterator Cord::chunk_begin() const {
 
 inline Cord::ChunkIterator Cord::chunk_end() const { return ChunkIterator(); }
 
-inline Cord::ChunkIterator Cord::ChunkRange::begin() const {
-  return cord_->chunk_begin();
-}
-
-inline Cord::ChunkIterator Cord::ChunkRange::end() const {
-  return cord_->chunk_end();
-}
-
 inline Cord::ChunkRange Cord::Chunks() const { return ChunkRange(this); }
 
 inline Cord::CharIterator& Cord::CharIterator::operator++() {
diff --git a/absl/strings/cord_test.cc b/absl/strings/cord_test.cc
index 4afa4a26969d..0ec93b4c45b9 100644
--- a/absl/strings/cord_test.cc
+++ b/absl/strings/cord_test.cc
@@ -18,6 +18,7 @@
 #include "absl/base/config.h"
 #include "absl/base/internal/endian.h"
 #include "absl/base/internal/raw_logging.h"
+#include "absl/base/macros.h"
 #include "absl/container/fixed_array.h"
 #include "absl/strings/cord_test_helpers.h"
 #include "absl/strings/str_cat.h"
@@ -1402,6 +1403,53 @@ TEST(CordChunkIterator, Operations) {
   VerifyChunkIterator(subcords, 128);
 }
 
+TEST(CordChunkIterator, MaxLengthFullTree) {
+  // Start with a 1-byte cord, and then double its length in a loop.  We should
+  // be able to do this until the point where we would overflow size_t.
+
+  absl::Cord cord;
+  size_t size = 1;
+  AddExternalMemory("x", &cord);
+  EXPECT_EQ(cord.size(), size);
+
+  const int kCordLengthDoublingLimit = std::numeric_limits<size_t>::digits - 1;
+  for (int i = 0; i < kCordLengthDoublingLimit; ++i) {
+    cord.Prepend(absl::Cord(cord));
+    size <<= 1;
+
+    EXPECT_EQ(cord.size(), size);
+
+    auto chunk_it = cord.chunk_begin();
+    EXPECT_EQ(*chunk_it, "x");
+  }
+
+  EXPECT_DEATH_IF_SUPPORTED(
+      (cord.Prepend(absl::Cord(cord)), *cord.chunk_begin()),
+      "Cord is too long");
+}
+
+TEST(CordChunkIterator, MaxDepth) {
+  // By reusing nodes, it's possible in pathological cases to build a Cord that
+  // exceeds both the maximum permissible length and depth.  In this case, the
+  // violation of the maximum depth is reported.
+  absl::Cord left_child;
+  AddExternalMemory("x", &left_child);
+  absl::Cord root = left_child;
+
+  for (int i = 0; i < absl::cord_internal::MaxCordDepth() - 2; ++i) {
+    size_t new_size = left_child.size() + root.size();
+    root.Prepend(left_child);
+    EXPECT_EQ(root.size(), new_size);
+
+    auto chunk_it = root.chunk_begin();
+    EXPECT_EQ(*chunk_it, "x");
+
+    std::swap(left_child, root);
+  }
+
+  EXPECT_DEATH_IF_SUPPORTED(root.Prepend(left_child), "Cord is too long");
+}
+
 TEST(CordCharIterator, Traits) {
   static_assert(std::is_copy_constructible<absl::Cord::CharIterator>::value,
                 "");
@@ -1580,3 +1628,23 @@ TEST(Cord, SmallBufferAssignFromOwnData) {
     }
   }
 }
+
+TEST(CordDeathTest, Hardening) {
+  absl::Cord cord("hello");
+  // These statement should abort the program in all builds modes.
+  EXPECT_DEATH_IF_SUPPORTED(cord.RemovePrefix(6), "");
+  EXPECT_DEATH_IF_SUPPORTED(cord.RemoveSuffix(6), "");
+
+  bool test_hardening = false;
+  ABSL_HARDENING_ASSERT([&]() {
+    // This only runs when ABSL_HARDENING_ASSERT is active.
+    test_hardening = true;
+    return true;
+  }());
+  if (!test_hardening) return;
+
+  EXPECT_DEATH_IF_SUPPORTED(cord[5], "");
+  EXPECT_DEATH_IF_SUPPORTED(*cord.chunk_end(), "");
+  EXPECT_DEATH_IF_SUPPORTED(static_cast<void>(cord.chunk_end()->empty()), "");
+  EXPECT_DEATH_IF_SUPPORTED(++cord.chunk_end(), "");
+}
diff --git a/absl/strings/internal/str_format/extension.h b/absl/strings/internal/str_format/extension.h
index 968850ebfc84..bae2c0784421 100644
--- a/absl/strings/internal/str_format/extension.h
+++ b/absl/strings/internal/str_format/extension.h
@@ -155,8 +155,7 @@ enum class FormatConversionChar : uint8_t {
     d, i, o, u, x, X,        // int
     f, F, e, E, g, G, a, A,  // float
     n, p,                    // misc
-    kNone,
-    none = kNone
+    kNone
 };
 // clang-format on
 
@@ -288,11 +287,6 @@ class FormatConversionSpec {
   // negative value.
   int precision() const { return precision_; }
 
-  // Deprecated (use has_x_flag() instead).
-  Flags flags() const { return flags_; }
-  // Deprecated
-  FormatConversionChar conv() const { return conversion_char(); }
-
  private:
   friend struct str_format_internal::FormatConversionSpecImplFriend;
   FormatConversionChar conv_ = FormatConversionChar::kNone;
@@ -344,15 +338,7 @@ enum class FormatConversionCharSet : uint64_t {
   kFloating = a | e | f | g | A | E | F | G,
   kNumeric = kIntegral | kFloating,
   kString = s,
-  kPointer = p,
-
-  // The following are deprecated
-  star = kStar,
-  integral = kIntegral,
-  floating = kFloating,
-  numeric = kNumeric,
-  string = kString,
-  pointer = kPointer
+  kPointer = p
 };
 
 // Type safe OR operator.
diff --git a/absl/strings/string_view.h b/absl/strings/string_view.h
index 8e348fcd69ce..8a9db8c3d796 100644
--- a/absl/strings/string_view.h
+++ b/absl/strings/string_view.h
@@ -48,7 +48,7 @@
 
 namespace absl {
 ABSL_NAMESPACE_BEGIN
-using std::string_view;
+using string_view = std::string_view;
 ABSL_NAMESPACE_END
 }  // namespace absl