Export of internal Abseil changes

--
642ab296a2c9629c44f3f2ce6911cd2488bcf416 by Derek Mauro <dmauro@google.com>:

Remove an obsolete check in CMakeLists.txt

PiperOrigin-RevId: 352852564

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

Clarify that the calling *thread* must have locked the mutex in order to unlock
it.

PiperOrigin-RevId: 352801804

--
24e1f5f72756046f5265abf618e951c341f09b8d by Derek Mauro <dmauro@google.com>:

Fixes failing CMake string comparisons
https://cmake.org/cmake/help/latest/policy/CMP0054.html

Fixes #791

PiperOrigin-RevId: 352791054

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

Introduce CordRepRing class

This change introduces the CordRepRing class that implements all the lower level / internal implementation for upcoming CordRepRing ring buffer support in cord.

PiperOrigin-RevId: 352771994

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

Optimize InlineData representation for cord sampling (cordz)

This CL changes InlineData to allow us to store a (future) Cordz Info pointer directly into the inline representation:

- make InlineData a class that provides a public API to set the active union members (tree or chars) and safely access that data.
- change 'tree' and 'profiled' bits to be the 2 least significant bits, allowing us 62 continquous bits for storing a Cordz Info pointer.

PiperOrigin-RevId: 352642411

--
dc55ba71bbce0e6a83e05a453990c51ac3d68426 by Mark Barolak <mbar@google.com>:

Add unit test coverage for the mutating overload of absl::AsciiStrToLower.

PiperOrigin-RevId: 352626006
GitOrigin-RevId: 642ab296a2c9629c44f3f2ce6911cd2488bcf416
Change-Id: I6c5929dd830d3c630e14e7fd5387fc3e25a69100

11 files changed, 3358 insertions, 129 deletions

diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel
index 70016791..d7c322f6 100644
--- a/absl/strings/BUILD.bazel
+++ b/absl/strings/BUILD.bazel
@@ -269,10 +269,12 @@ cc_library(
     name = "cord_internal",
     srcs = [
         "internal/cord_internal.cc",
+        "internal/cord_rep_ring.cc",
     ],
     hdrs = [
         "internal/cord_internal.h",
         "internal/cord_rep_flat.h",
+        "internal/cord_rep_ring.h",
     ],
     copts = ABSL_DEFAULT_COPTS,
     visibility = [
@@ -281,9 +283,13 @@ cc_library(
     deps = [
         ":strings",
         "//absl/base:base_internal",
+        "//absl/base:config",
         "//absl/base:core_headers",
+        "//absl/base:raw_logging_internal",
+        "//absl/base:throw_delegate",
         "//absl/container:compressed_tuple",
         "//absl/container:inlined_vector",
+        "//absl/container:layout",
         "//absl/meta:type_traits",
     ],
 )
@@ -348,6 +354,23 @@ cc_test(
 )
 
 cc_test(
+    name = "cord_ring_test",
+    size = "medium",
+    srcs = ["cord_ring_test.cc"],
+    copts = ABSL_TEST_COPTS,
+    visibility = ["//visibility:private"],
+    deps = [
+        ":cord_internal",
+        ":strings",
+        "//absl/base:config",
+        "//absl/base:core_headers",
+        "//absl/base:raw_logging_internal",
+        "//absl/debugging:leak_check",
+        "@com_google_googletest//:gtest_main",
+    ],
+)
+
+cc_test(
     name = "substitute_test",
     size = "small",
     srcs = ["substitute_test.cc"],
diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt
index 654d0fd6..a6204bf6 100644
--- a/absl/strings/CMakeLists.txt
+++ b/absl/strings/CMakeLists.txt
@@ -558,6 +558,8 @@ absl_cc_library(
     "cord.cc"
     "internal/cord_internal.cc"
     "internal/cord_internal.h"
+    "internal/cord_rep_ring.h"
+    "internal/cord_rep_ring.cc"
     "internal/cord_rep_flat.h"
   COPTS
     ${ABSL_DEFAULT_COPTS}
@@ -565,6 +567,7 @@ absl_cc_library(
     absl::base
     absl::base_internal
     absl::compressed_tuple
+    absl::config
     absl::core_headers
     absl::endian
     absl::fixed_array
@@ -574,6 +577,7 @@ absl_cc_library(
     absl::raw_logging_internal
     absl::strings
     absl::strings_internal
+    absl::throw_delegate
     absl::type_traits
   PUBLIC
 )
@@ -609,3 +613,20 @@ absl_cc_test(
     absl::fixed_array
     gmock_main
 )
+
+absl_cc_test(
+  NAME
+    cord_ring_test
+  SRCS
+    "cord_ring_test.cc"
+  COPTS
+    ${ABSL_TEST_COPTS}
+  DEPS
+    absl::config
+    absl::cord
+    absl::strings
+    absl::base
+    absl::core_headers
+    absl::raw_logging_internal
+    gmock_main
+)
diff --git a/absl/strings/ascii_test.cc b/absl/strings/ascii_test.cc
index 5ecd23f8..83af7825 100644
--- a/absl/strings/ascii_test.cc
+++ b/absl/strings/ascii_test.cc
@@ -197,11 +197,15 @@ TEST(AsciiStrTo, Lower) {
   const std::string str("GHIJKL");
   const std::string str2("MNOPQR");
   const absl::string_view sp(str2);
+  std::string mutable_str("STUVWX");
 
   EXPECT_EQ("abcdef", absl::AsciiStrToLower(buf));
   EXPECT_EQ("ghijkl", absl::AsciiStrToLower(str));
   EXPECT_EQ("mnopqr", absl::AsciiStrToLower(sp));
 
+  absl::AsciiStrToLower(&mutable_str);
+  EXPECT_EQ("stuvwx", mutable_str);
+
   char mutable_buf[] = "Mutable";
   std::transform(mutable_buf, mutable_buf + strlen(mutable_buf),
                  mutable_buf, absl::ascii_tolower);
diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc
index c118bdd8..df8c26d4 100644
--- a/absl/strings/cord.cc
+++ b/absl/strings/cord.cc
@@ -255,50 +255,49 @@ inline void Cord::InlineRep::set_data(const char* data, size_t n,
                                       bool nullify_tail) {
   static_assert(kMaxInline == 15, "set_data is hard-coded for a length of 15");
 
-  cord_internal::SmallMemmove(data_.as_chars, data, n, nullify_tail);
-  set_tagged_size(static_cast<char>(n));
+  cord_internal::SmallMemmove(data_.as_chars(), data, n, nullify_tail);
+  set_inline_size(n);
 }
 
 inline char* Cord::InlineRep::set_data(size_t n) {
   assert(n <= kMaxInline);
   ResetToEmpty();
-  set_tagged_size(static_cast<char>(n));
-  return data_.as_chars;
+  set_inline_size(n);
+  return data_.as_chars();
 }
 
 inline CordRep* Cord::InlineRep::force_tree(size_t extra_hint) {
-  size_t len = tagged_size();
-  if (len > kMaxInline) {
-    return data_.as_tree.rep;
+  if (data_.is_tree()) {
+    return data_.as_tree();
   }
 
+  size_t len = inline_size();
   CordRepFlat* result = CordRepFlat::New(len + extra_hint);
   result->length = len;
-  static_assert(kMinFlatLength >= sizeof(data_.as_chars), "");
-  memcpy(result->Data(), data_.as_chars, sizeof(data_.as_chars));
+  static_assert(kMinFlatLength >= sizeof(data_), "");
+  memcpy(result->Data(), data_.as_chars(), sizeof(data_));
   set_tree(result);
   return result;
 }
 
 inline void Cord::InlineRep::reduce_size(size_t n) {
-  size_t tag = tagged_size();
+  size_t tag = inline_size();
   assert(tag <= kMaxInline);
   assert(tag >= n);
   tag -= n;
-  memset(data_.as_chars + tag, 0, n);
-  set_tagged_size(static_cast<char>(tag));
+  memset(data_.as_chars() + tag, 0, n);
+  set_inline_size(static_cast<char>(tag));
 }
 
 inline void Cord::InlineRep::remove_prefix(size_t n) {
-  cord_internal::SmallMemmove(data_.as_chars, data_.as_chars + n,
-                              tagged_size() - n);
+  cord_internal::SmallMemmove(data_.as_chars(), data_.as_chars() + n,
+                              inline_size() - n);
   reduce_size(n);
 }
 
 void Cord::InlineRep::AppendTree(CordRep* tree) {
   if (tree == nullptr) return;
-  size_t len = tagged_size();
-  if (len == 0) {
+  if (data_.is_empty()) {
     set_tree(tree);
   } else {
     set_tree(Concat(force_tree(0), tree));
@@ -307,8 +306,7 @@ void Cord::InlineRep::AppendTree(CordRep* tree) {
 
 void Cord::InlineRep::PrependTree(CordRep* tree) {
   assert(tree != nullptr);
-  size_t len = tagged_size();
-  if (len == 0) {
+  if (data_.is_empty()) {
     set_tree(tree);
   } else {
     set_tree(Concat(tree, force_tree(0)));
@@ -363,12 +361,14 @@ void Cord::InlineRep::GetAppendRegion(char** region, size_t* size,
   }
 
   // Try to fit in the inline buffer if possible.
-  size_t inline_length = tagged_size();
-  if (inline_length < kMaxInline && max_length <= kMaxInline - inline_length) {
-    *region = data_.as_chars + inline_length;
-    *size = max_length;
-    set_tagged_size(static_cast<char>(inline_length + max_length));
-    return;
+  if (!is_tree()) {
+    size_t inline_length = inline_size();
+    if (max_length <= kMaxInline - inline_length) {
+      *region = data_.as_chars() + inline_length;
+      *size = max_length;
+      set_inline_size(inline_length + max_length);
+      return;
+    }
   }
 
   CordRep* root = force_tree(max_length);
@@ -390,12 +390,14 @@ void Cord::InlineRep::GetAppendRegion(char** region, size_t* size) {
   const size_t max_length = std::numeric_limits<size_t>::max();
 
   // Try to fit in the inline buffer if possible.
-  size_t inline_length = tagged_size();
-  if (inline_length < kMaxInline) {
-    *region = data_.as_chars + inline_length;
-    *size = kMaxInline - inline_length;
-    set_tagged_size(kMaxInline);
-    return;
+  if (!data_.is_tree()) {
+    size_t inline_length = inline_size();
+    if (inline_length < kMaxInline) {
+      *region = data_.as_chars() + inline_length;
+      *size = kMaxInline - inline_length;
+      set_inline_size(kMaxInline);
+      return;
+    }
   }
 
   CordRep* root = force_tree(max_length);
@@ -549,24 +551,25 @@ template Cord& Cord::operator=(std::string&& src);
 // we keep it here to make diffs easier.
 void Cord::InlineRep::AppendArray(const char* src_data, size_t src_size) {
   if (src_size == 0) return;  // memcpy(_, nullptr, 0) is undefined.
-  // Try to fit in the inline buffer if possible.
-  size_t inline_length = tagged_size();
-  if (inline_length < kMaxInline && src_size <= kMaxInline - inline_length) {
-    // Append new data to embedded array
-    set_tagged_size(static_cast<char>(inline_length + src_size));
-    memcpy(data_.as_chars + inline_length, src_data, src_size);
-    return;
-  }
-
-  CordRep* root = tree();
 
   size_t appended = 0;
-  if (root) {
+  CordRep* root = nullptr;
+  if (is_tree()) {
+    root = data_.as_tree();
     char* region;
     if (PrepareAppendRegion(root, &region, &appended, src_size)) {
       memcpy(region, src_data, appended);
     }
   } else {
+    // Try to fit in the inline buffer if possible.
+    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);
+      return;
+    }
+
     // It is possible that src_data == data_, but when we transition from an
     // InlineRep to a tree we need to assign data_ = root via set_tree. To
     // avoid corrupting the source data before we copy it, delay calling
@@ -578,7 +581,7 @@ void Cord::InlineRep::AppendArray(const char* src_data, size_t src_size) {
     root = CordRepFlat::New(std::max<size_t>(size1, size2));
     appended = std::min(
         src_size, root->flat()->Capacity() - inline_length);
-    memcpy(root->flat()->Data(), data_.as_chars, inline_length);
+    memcpy(root->flat()->Data(), data_.as_chars(), inline_length);
     memcpy(root->flat()->Data() + inline_length, src_data, appended);
     root->length = inline_length + appended;
     set_tree(root);
@@ -684,18 +687,19 @@ void Cord::Prepend(const Cord& src) {
 
 void Cord::Prepend(absl::string_view src) {
   if (src.empty()) return;  // memcpy(_, nullptr, 0) is undefined.
-  size_t cur_size = contents_.size();
-  if (!contents_.is_tree() && cur_size + src.size() <= InlineRep::kMaxInline) {
-    // Use embedded storage.
-    char data[InlineRep::kMaxInline + 1] = {0};
-    data[InlineRep::kMaxInline] = cur_size + src.size();  // set size
-    memcpy(data, src.data(), src.size());
-    memcpy(data + src.size(), contents_.data(), cur_size);
-    memcpy(reinterpret_cast<void*>(&contents_), data,
-           InlineRep::kMaxInline + 1);
-  } else {
-    contents_.PrependTree(NewTree(src.data(), src.size(), 0));
+  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());
+      return;
+    }
   }
+  contents_.PrependTree(NewTree(src.data(), src.size(), 0));
 }
 
 template <typename T, Cord::EnableIfString<T>>
@@ -888,7 +892,7 @@ Cord Cord::Subcord(size_t pos, size_t new_size) const {
   } else if (new_size <= InlineRep::kMaxInline) {
     Cord::ChunkIterator it = chunk_begin();
     it.AdvanceBytes(pos);
-    char* dest = sub_cord.contents_.data_.as_chars;
+    char* dest = sub_cord.contents_.data_.as_chars();
     size_t remaining_size = new_size;
     while (remaining_size > it->size()) {
       cord_internal::SmallMemmove(dest, it->data(), it->size());
@@ -897,7 +901,7 @@ Cord Cord::Subcord(size_t pos, size_t new_size) const {
       ++it;
     }
     cord_internal::SmallMemmove(dest, it->data(), remaining_size);
-    sub_cord.contents_.set_tagged_size(new_size);
+    sub_cord.contents_.set_inline_size(new_size);
   } else {
     sub_cord.contents_.set_tree(NewSubRange(tree, pos, new_size));
   }
@@ -1086,9 +1090,8 @@ bool ComputeCompareResult<bool>(int memcmp_res) {
 // Helper routine. Locates the first flat chunk of the Cord without
 // initializing the iterator.
 inline absl::string_view Cord::InlineRep::FindFlatStartPiece() const {
-  size_t n = tagged_size();
-  if (n <= kMaxInline) {
-    return absl::string_view(data_.as_chars, n);
+  if (!is_tree()) {
+    return absl::string_view(data_.as_chars(), data_.inline_size());
   }
 
   CordRep* node = tree();
diff --git a/absl/strings/cord.h b/absl/strings/cord.h
index 7136f034..9d8764a0 100644
--- a/absl/strings/cord.h
+++ b/absl/strings/cord.h
@@ -665,8 +665,6 @@ class Cord {
    public:
     static constexpr unsigned char kMaxInline = cord_internal::kMaxInline;
     static_assert(kMaxInline >= sizeof(absl::cord_internal::CordRep*), "");
-    static constexpr unsigned char kTreeFlag = cord_internal::kTreeFlag;
-    static constexpr unsigned char kProfiledFlag = cord_internal::kProfiledFlag;
 
     constexpr InlineRep() : data_() {}
     InlineRep(const InlineRep& src);
@@ -685,6 +683,7 @@ class Cord {
     char* set_data(size_t n);  // Write data to the result
     // Returns nullptr if holding bytes
     absl::cord_internal::CordRep* tree() const;
+    absl::cord_internal::CordRep* as_tree() const;
     // Discards old pointer, if any
     void set_tree(absl::cord_internal::CordRep* rep);
     // Replaces a tree with a new root. This is faster than set_tree, but it
@@ -728,13 +727,13 @@ class Cord {
       memcpy(&(*dst)[0], &data_, sizeof(data_) - 1);
       // erase is faster than resize because the logic for memory allocation is
       // not needed.
-      dst->erase(tagged_size());
+      dst->erase(inline_size());
     }
 
     // Copies the inline contents into `dst`. Assumes the cord is not empty.
     void CopyToArray(char* dst) const;
 
-    bool is_tree() const { return tagged_size() > kMaxInline; }
+    bool is_tree() const { return data_.is_tree(); }
 
    private:
     friend class Cord;
@@ -745,14 +744,8 @@ class Cord {
 
     void ResetToEmpty() { data_ = {}; }
 
-    // This uses reinterpret_cast instead of the union to avoid accessing the
-    // inactive union element. The tagged size is not a common prefix.
-    void set_tagged_size(char new_tag) {
-      reinterpret_cast<char*>(&data_)[kMaxInline] = new_tag;
-    }
-    char tagged_size() const {
-      return reinterpret_cast<const char*>(&data_)[kMaxInline];
-    }
+    void set_inline_size(size_t size) { data_.set_inline_size(size); }
+    size_t inline_size() const { return data_.inline_size(); }
 
     cord_internal::InlineData data_;
   };
@@ -948,35 +941,39 @@ inline void Cord::InlineRep::Swap(Cord::InlineRep* rhs) {
 }
 
 inline const char* Cord::InlineRep::data() const {
-  return is_tree() ? nullptr : data_.as_chars;
+  return is_tree() ? nullptr : data_.as_chars();
+}
+
+inline absl::cord_internal::CordRep* Cord::InlineRep::as_tree() const {
+  assert(data_.is_tree());
+  return data_.as_tree();
 }
 
 inline absl::cord_internal::CordRep* Cord::InlineRep::tree() const {
   if (is_tree()) {
-    return data_.as_tree.rep;
+    return as_tree();
   } else {
     return nullptr;
   }
 }
 
-inline bool Cord::InlineRep::empty() const { return tagged_size() == 0; }
+inline bool Cord::InlineRep::empty() const { return data_.is_empty(); }
 
 inline size_t Cord::InlineRep::size() const {
-  const char tag = tagged_size();
-  if (tag <= kMaxInline) return tag;
-  return static_cast<size_t>(tree()->length);
+  return is_tree() ? as_tree()->length : inline_size();
 }
 
 inline void Cord::InlineRep::set_tree(absl::cord_internal::CordRep* rep) {
   if (rep == nullptr) {
     ResetToEmpty();
   } else {
-    bool was_tree = is_tree();
-    data_.as_tree = {rep, {}, tagged_size()};
-    if (!was_tree) {
-      // If we were not a tree already, set the tag.
-      // Otherwise, leave it alone because it might have the profile bit on.
-      set_tagged_size(kTreeFlag);
+    if (data_.is_tree()) {
+      // `data_` already holds a 'tree' value and an optional cordz_info value.
+      // Replace the tree value only, leaving the cordz_info value unchanged.
+      data_.set_tree(rep);
+    } else {
+      // `data_` contains inlined data: initialize data_ to tree value `rep`.
+      data_.make_tree(rep);
     }
   }
 }
@@ -987,7 +984,7 @@ inline void Cord::InlineRep::replace_tree(absl::cord_internal::CordRep* rep) {
     set_tree(rep);
     return;
   }
-  data_.as_tree = {rep, {}, tagged_size()};
+  data_.set_tree(rep);
 }
 
 inline absl::cord_internal::CordRep* Cord::InlineRep::clear() {
@@ -998,9 +995,9 @@ inline absl::cord_internal::CordRep* Cord::InlineRep::clear() {
 
 inline void Cord::InlineRep::CopyToArray(char* dst) const {
   assert(!is_tree());
-  size_t n = tagged_size();
+  size_t n = inline_size();
   assert(n != 0);
-  cord_internal::SmallMemmove(dst, data_.as_chars, n);
+  cord_internal::SmallMemmove(dst, data_.as_chars(), n);
 }
 
 constexpr inline Cord::Cord() noexcept {}
@@ -1011,11 +1008,9 @@ constexpr Cord::Cord(strings_internal::StringConstant<T>)
                         cord_internal::kMaxInline
                     ? cord_internal::InlineData(
                           strings_internal::StringConstant<T>::value)
-                    : cord_internal::InlineData(cord_internal::AsTree{
+                    : cord_internal::InlineData(
                           &cord_internal::ConstInitExternalStorage<
-                              strings_internal::StringConstant<T>>::value,
-                          {},
-                          cord_internal::kTreeFlag})) {}
+                              strings_internal::StringConstant<T>>::value)) {}
 
 inline Cord& Cord::operator=(const Cord& x) {
   contents_ = x.contents_;
@@ -1107,12 +1102,12 @@ inline bool Cord::StartsWith(absl::string_view rhs) const {
 
 inline Cord::ChunkIterator::ChunkIterator(const Cord* cord)
     : bytes_remaining_(cord->size()) {
-  if (cord->empty()) return;
   if (cord->contents_.is_tree()) {
-    stack_of_right_children_.push_back(cord->contents_.tree());
+    stack_of_right_children_.push_back(cord->contents_.as_tree());
     operator++();
   } else {
-    current_chunk_ = absl::string_view(cord->contents_.data(), cord->size());
+    current_chunk_ =
+        absl::string_view(cord->contents_.data(), bytes_remaining_);
   }
 }
 
diff --git a/absl/strings/cord_ring_test.cc b/absl/strings/cord_ring_test.cc
new file mode 100644
index 00000000..7d75e106
--- /dev/null
+++ b/absl/strings/cord_ring_test.cc
@@ -0,0 +1,1572 @@
+// Copyright 2020 The Abseil Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// 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.
+
+#include <cstdlib>
+#include <ctime>
+#include <memory>
+#include <random>
+#include <sstream>
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "absl/base/config.h"
+#include "absl/base/internal/raw_logging.h"
+#include "absl/base/macros.h"
+#include "absl/debugging/leak_check.h"
+#include "absl/strings/internal/cord_internal.h"
+#include "absl/strings/internal/cord_rep_ring.h"
+#include "absl/strings/str_cat.h"
+#include "absl/strings/string_view.h"
+
+extern thread_local bool cord_ring;
+
+// TOOD(b/177688959): weird things happened with the original test
+#define ASAN_BUG_177688959_FIXED false
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace {
+
+using RandomEngine = std::mt19937_64;
+
+using ::absl::cord_internal::CordRep;
+using ::absl::cord_internal::CordRepConcat;
+using ::absl::cord_internal::CordRepExternal;
+using ::absl::cord_internal::CordRepFlat;
+using ::absl::cord_internal::CordRepRing;
+using ::absl::cord_internal::CordRepSubstring;
+
+using ::absl::cord_internal::CONCAT;
+using ::absl::cord_internal::EXTERNAL;
+using ::absl::cord_internal::SUBSTRING;
+
+using testing::ElementsAre;
+using testing::ElementsAreArray;
+using testing::Eq;
+using testing::Ge;
+using testing::Le;
+using testing::Lt;
+using testing::Ne;
+using testing::SizeIs;
+
+using index_type = CordRepRing::index_type;
+
+enum InputShareMode { kPrivate, kShared, kSharedIndirect };
+
+// TestParam class used by all test fixtures.
+// Not all fixtures use all possible input combinations
+struct TestParam {
+  TestParam() = default;
+  explicit TestParam(InputShareMode input_share_mode)
+      : input_share_mode(input_share_mode) {}
+
+  // Run the test with the 'rep under test' to be privately owned.
+  // Otherwise, the rep has a shared ref count of 2 or higher.
+  bool refcount_is_one = true;
+
+  // Run the test with the 'rep under test' being allocated with enough capacity
+  // to accommodate any modifications made to it. Otherwise, the rep has zero
+  // extra (reserve) capacity.
+  bool with_capacity = true;
+
+  // For test providing possibly shared input such as Append(.., CordpRep*),
+  // this field defines if that input is adopted with a refcount of one
+  // (privately owned / donated), or shared. For composite inputs such as
+  // 'substring of flat', we also have the 'shared indirect' value which means
+  // the top level node is not shared, but the contained child node is shared.
+  InputShareMode input_share_mode = kPrivate;
+
+  std::string ToString() const {
+    return absl::StrCat(refcount_is_one ? "Private" : "Shared",
+                        with_capacity ? "" : "_NoCapacity",
+                        (input_share_mode == kPrivate) ? ""
+                        : (input_share_mode == kShared)
+                            ? "_SharedInput"
+                            : "_IndirectSharedInput");
+  }
+};
+using TestParams = std::vector<TestParam>;
+
+// Matcher validating when mutable copies are required / performed.
+MATCHER_P2(EqIfPrivate, param, rep,
+           absl::StrCat("Equal 0x", absl::Hex(rep), " if private")) {
+  return param.refcount_is_one ? arg == rep : arg != rep;
+}
+
+// Matcher validating when mutable copies are required / performed.
+MATCHER_P2(EqIfPrivateAndCapacity, param, rep,
+           absl::StrCat("Equal 0x", absl::Hex(rep),
+                        " if private and capacity")) {
+  return (param.refcount_is_one && param.with_capacity) ? arg == rep
+                                                        : arg != rep;
+}
+
+MATCHER_P2(EqIfInputPrivate, param, rep, "Equal if input is private") {
+  return param.input_share_mode == kPrivate ? arg == rep : arg != rep;
+}
+
+// Matcher validating the core in-variants of the CordRepRing instance.
+MATCHER(IsValidRingBuffer, "RingBuffer is valid") {
+  std::stringstream ss;
+  if (!arg->IsValid(ss)) {
+    *result_listener << "\nERROR: " << ss.str() << "\nRING = " << *arg;
+    return false;
+  }
+  return true;
+}
+
+// Returns the flats contained in the provided CordRepRing
+std::vector<string_view> ToFlats(const CordRepRing* r) {
+  std::vector<string_view> flats;
+  flats.reserve(r->entries());
+  index_type pos = r->head();
+  do {
+    flats.push_back(r->entry_data(pos));
+  } while ((pos = r->advance(pos)) != r->tail());
+  return flats;
+}
+
+class not_a_string_view {
+ public:
+  explicit not_a_string_view(absl::string_view s)
+      : data_(s.data()), size_(s.size()) {}
+  explicit not_a_string_view(const void* data, size_t size)
+      : data_(data), size_(size) {}
+
+  not_a_string_view remove_prefix(size_t n) const {
+    return not_a_string_view(static_cast<const char*>(data_) + n, size_ - n);
+  }
+
+  not_a_string_view remove_suffix(size_t n) const {
+    return not_a_string_view(data_, size_ - n);
+  }
+
+  const void* data() const { return data_; }
+  size_t size() const { return size_; }
+
+ private:
+  const void* data_;
+  size_t size_;
+};
+
+bool operator==(not_a_string_view lhs, not_a_string_view rhs) {
+  return lhs.data() == rhs.data() && lhs.size() == rhs.size();
+}
+
+std::ostream& operator<<(std::ostream& s, not_a_string_view rhs) {
+  return s << "{ data: " << rhs.data() << " size: " << rhs.size() << "}";
+}
+
+std::vector<not_a_string_view> ToRawFlats(const CordRepRing* r) {
+  std::vector<not_a_string_view> flats;
+  flats.reserve(r->entries());
+  index_type pos = r->head();
+  do {
+    flats.emplace_back(r->entry_data(pos));
+  } while ((pos = r->advance(pos)) != r->tail());
+  return flats;
+}
+
+// Returns the value contained in the provided CordRepRing
+std::string ToString(const CordRepRing* r) {
+  std::string value;
+  value.reserve(r->length);
+  index_type pos = r->head();
+  do {
+    absl::string_view sv = r->entry_data(pos);
+    value.append(sv.data(), sv.size());
+  } while ((pos = r->advance(pos)) != r->tail());
+  return value;
+}
+
+// Creates a flat for testing
+CordRep* MakeFlat(absl::string_view s, size_t extra = 0) {
+  CordRepFlat* flat = CordRepFlat::New(s.length() + extra);
+  memcpy(flat->Data(), s.data(), s.length());
+  flat->length = s.length();
+  return flat;
+}
+
+// Creates an external node for testing
+CordRepExternal* MakeExternal(absl::string_view s) {
+  struct Rep : public CordRepExternal {
+    std::string s;
+    explicit Rep(absl::string_view s) : s(s) {
+      this->tag = EXTERNAL;
+      this->base = s.data();
+      this->length = s.length();
+      this->releaser_invoker = [](CordRepExternal* self) {
+        delete static_cast<Rep*>(self);
+      };
+    }
+  };
+  return new Rep(s);
+}
+
+CordRepExternal* MakeFakeExternal(size_t length) {
+  struct Rep : public CordRepExternal {
+    std::string s;
+    explicit Rep(size_t len) {
+      this->tag = EXTERNAL;
+      this->base = this->storage;
+      this->length = len;
+      this->releaser_invoker = [](CordRepExternal* self) {
+        delete static_cast<Rep*>(self);
+      };
+    }
+  };
+  return new Rep(length);
+}
+
+// Creates a flat or an external node for testing depending on the size.
+CordRep* MakeLeaf(absl::string_view s, size_t extra = 0) {
+  if (s.size() <= absl::cord_internal::kMaxFlatLength) {
+    return MakeFlat(s, extra);
+  } else {
+    return MakeExternal(s);
+  }
+}
+
+// Creates a substring node
+CordRepSubstring* MakeSubstring(size_t start, size_t len, CordRep* rep) {
+  auto* sub = new CordRepSubstring;
+  sub->tag = SUBSTRING;
+  sub->start = start;
+  sub->length = (len <= 0) ? rep->length - start + len : len;
+  sub->child = rep;
+  return sub;
+}
+
+// Creates a substring node removing the specified prefix
+CordRepSubstring* RemovePrefix(size_t start, CordRep* rep) {
+  return MakeSubstring(start, rep->length - start, rep);
+}
+
+// Creates a substring node removing the specified suffix
+CordRepSubstring* RemoveSuffix(size_t length, CordRep* rep) {
+  return MakeSubstring(0, rep->length - length, rep);
+}
+
+CordRepConcat* MakeConcat(CordRep* left, CordRep* right, int depth = 0) {
+  auto* concat = new CordRepConcat;
+  concat->tag = CONCAT;
+  concat->length = left->length + right->length;
+  concat->left = left;
+  concat->right = right;
+  concat->set_depth(depth);
+  return concat;
+}
+
+enum Composition { kMix, kAppend, kPrepend };
+
+Composition RandomComposition() {
+  RandomEngine rng(testing::GTEST_FLAG(random_seed));
+  return (rng() & 1) ? kMix : ((rng() & 1) ? kAppend : kPrepend);
+}
+
+absl::string_view ToString(Composition composition) {
+  switch (composition) {
+    case kAppend:
+      return "Append";
+    case kPrepend:
+      return "Prepend";
+    case kMix:
+      return "Mix";
+  }
+  assert(false);
+  return "???";
+}
+
+constexpr const char* kFox = "The quick brown fox jumps over the lazy dog";
+constexpr const char* kFoxFlats[] = {"The ", "quick ", "brown ",
+                                     "fox ", "jumps ", "over ",
+                                     "the ", "lazy ",  "dog"};
+constexpr const char* kAlphabet = "abcdefghijklmnopqrstuvwxyz";
+
+CordRepRing* FromFlats(Span<const char* const> flats,
+                       Composition composition = kAppend) {
+  if (flats.empty()) return nullptr;
+  CordRepRing* ring = nullptr;
+  switch (composition) {
+    case kAppend:
+      ring = CordRepRing::Create(MakeLeaf(flats.front()), flats.size() - 1);
+      for (int i = 1; i < flats.size(); ++i) {
+        ring = CordRepRing::Append(ring, MakeLeaf(flats[i]));
+      }
+      break;
+    case kPrepend:
+      ring = CordRepRing::Create(MakeLeaf(flats.back()), flats.size() - 1);
+      for (int i = static_cast<int>(flats.size() - 2); i >= 0; --i) {
+        ring = CordRepRing::Prepend(ring, MakeLeaf(flats[i]));
+      }
+      break;
+    case kMix:
+      size_t middle1 = flats.size() / 2, middle2 = middle1;
+      ring = CordRepRing::Create(MakeLeaf(flats[middle1]), flats.size() - 1);
+      if (!flats.empty()) {
+        if ((flats.size() & 1) == 0) {
+          ring = CordRepRing::Prepend(ring, MakeLeaf(flats[--middle1]));
+        }
+        for (int i = 1; i <= middle1; ++i) {
+          ring = CordRepRing::Prepend(ring, MakeLeaf(flats[middle1 - i]));
+          ring = CordRepRing::Append(ring, MakeLeaf(flats[middle2 + i]));
+        }
+      }
+      break;
+  }
+  EXPECT_THAT(ToFlats(ring), ElementsAreArray(flats));
+  return ring;
+}
+
+std::ostream& operator<<(std::ostream& s, const TestParam& param) {
+  return s << param.ToString();
+}
+
+std::string TestParamToString(const testing::TestParamInfo<TestParam>& info) {
+  return info.param.ToString();
+}
+
+class CordRingTest : public testing::Test {
+ public:
+  ~CordRingTest() override {
+#if ASAN_BUG_177688959_FIXED
+    for (CordRep* rep : unrefs_) {
+      CordRep::Unref(rep);
+    }
+#endif
+  }
+
+  template <typename CordRepType>
+  CordRepType* NeedsUnref(CordRepType* rep) {
+    assert(rep);
+#if ASAN_BUG_177688959_FIXED
+    unrefs_.push_back(rep);
+#endif
+    return rep;
+  }
+
+  template <typename CordRepType>
+  CordRepType* Ref(CordRepType* rep) {
+    CordRep::Ref(rep);
+    return NeedsUnref(rep);
+  }
+
+  void Unref(CordRep* rep) {
+#if !ASAN_BUG_177688959_FIXED
+    CordRep::Unref(rep);
+#endif
+  }
+
+ private:
+#if ASAN_BUG_177688959_FIXED
+  std::vector<CordRep*> unrefs_;
+#endif
+};
+
+class CordRingTestWithParam : public testing::TestWithParam<TestParam> {
+ public:
+  ~CordRingTestWithParam() override {
+#if ASAN_BUG_177688959_FIXED
+    for (CordRep* rep : unrefs_) {
+      CordRep::Unref(rep);
+    }
+#endif
+  }
+
+  CordRepRing* CreateWithCapacity(CordRep* child, size_t extra_capacity) {
+    if (!GetParam().with_capacity) extra_capacity = 0;
+    CordRepRing* ring = CordRepRing::Create(child, extra_capacity);
+    ring->SetCapacityForTesting(1 + extra_capacity);
+    return RefIfShared(ring);
+  }
+
+  bool Shared() const { return !GetParam().refcount_is_one; }
+  bool InputShared() const { return GetParam().input_share_mode == kShared; }
+  bool InputSharedIndirect() const {
+    return GetParam().input_share_mode == kSharedIndirect;
+  }
+
+  template <typename CordRepType>
+  CordRepType* NeedsUnref(CordRepType* rep) {
+    assert(rep);
+#if ASAN_BUG_177688959_FIXED
+    unrefs_.push_back(rep);
+#endif
+    return rep;
+  }
+
+  template <typename CordRepType>
+  CordRepType* Ref(CordRepType* rep) {
+    CordRep::Ref(rep);
+    return NeedsUnref(rep);
+  }
+
+  void Unref(CordRep* rep) {
+#if !ASAN_BUG_177688959_FIXED
+    CordRep::Unref(rep);
+#endif
+  }
+
+  template <typename CordRepType>
+  CordRepType* RefIfShared(CordRepType* rep) {
+    return Shared() ? Ref(rep) : rep;
+  }
+
+  void UnrefIfShared(CordRep* rep) {
+    if (Shared()) Unref(rep);
+  }
+
+  template <typename CordRepType>
+  CordRepType* RefIfInputShared(CordRepType* rep) {
+    return InputShared() ? Ref(rep) : rep;
+  }
+
+  void UnrefIfInputShared(CordRep* rep) {
+    if (InputShared()) Unref(rep);
+  }
+
+  template <typename CordRepType>
+  CordRepType* RefIfInputSharedIndirect(CordRepType* rep) {
+    return InputSharedIndirect() ? Ref(rep) : rep;
+  }
+
+  void UnrefIfInputSharedIndirect(CordRep* rep) {
+    if (InputSharedIndirect()) Unref(rep);
+  }
+
+ private:
+#if ASAN_BUG_177688959_FIXED
+  std::vector<CordRep*> unrefs_;
+#endif
+};
+
+class CordRingCreateTest : public CordRingTestWithParam {
+ public:
+  static TestParams CreateTestParams() {
+    TestParams params;
+    params.emplace_back(InputShareMode::kPrivate);
+    params.emplace_back(InputShareMode::kShared);
+    return params;
+  }
+};
+
+class CordRingSubTest : public CordRingTestWithParam {
+ public:
+  static TestParams CreateTestParams() {
+    TestParams params;
+    for (bool refcount_is_one : {true, false}) {
+      TestParam param;
+      param.refcount_is_one = refcount_is_one;
+      params.push_back(param);
+    }
+    return params;
+  }
+};
+
+class CordRingBuildTest : public CordRingTestWithParam {
+ public:
+  static TestParams CreateTestParams() {
+    TestParams params;
+    for (bool refcount_is_one : {true, false}) {
+      for (bool with_capacity : {true, false}) {
+        TestParam param;
+        param.refcount_is_one = refcount_is_one;
+        param.with_capacity = with_capacity;
+        params.push_back(param);
+      }
+    }
+    return params;
+  }
+};
+
+class CordRingCreateFromTreeTest : public CordRingTestWithParam {
+ public:
+  static TestParams CreateTestParams() {
+    TestParams params;
+    params.emplace_back(InputShareMode::kPrivate);
+    params.emplace_back(InputShareMode::kShared);
+    params.emplace_back(InputShareMode::kSharedIndirect);
+    return params;
+  }
+};
+
+class CordRingBuildInputTest : public CordRingTestWithParam {
+ public:
+  static TestParams CreateTestParams() {
+    TestParams params;
+    for (bool refcount_is_one : {true, false}) {
+      for (bool with_capacity : {true, false}) {
+        for (InputShareMode share_mode : {kPrivate, kShared, kSharedIndirect}) {
+          TestParam param;
+          param.refcount_is_one = refcount_is_one;
+          param.with_capacity = with_capacity;
+          param.input_share_mode = share_mode;
+          params.push_back(param);
+        }
+      }
+    }
+    return params;
+  }
+};
+
+INSTANTIATE_TEST_CASE_P(WithParam, CordRingSubTest,
+                        testing::ValuesIn(CordRingSubTest::CreateTestParams()),
+                        TestParamToString);
+
+INSTANTIATE_TEST_CASE_P(
+    WithParam, CordRingCreateTest,
+    testing::ValuesIn(CordRingCreateTest::CreateTestParams()),
+    TestParamToString);
+
+INSTANTIATE_TEST_CASE_P(
+    WithParam, CordRingCreateFromTreeTest,
+    testing::ValuesIn(CordRingCreateFromTreeTest::CreateTestParams()),
+    TestParamToString);
+
+INSTANTIATE_TEST_CASE_P(
+    WithParam, CordRingBuildTest,
+    testing::ValuesIn(CordRingBuildTest::CreateTestParams()),
+    TestParamToString);
+
+INSTANTIATE_TEST_CASE_P(
+    WithParam, CordRingBuildInputTest,
+    testing::ValuesIn(CordRingBuildInputTest::CreateTestParams()),
+    TestParamToString);
+
+TEST_P(CordRingCreateTest, CreateFromFlat) {
+  absl::string_view str1 = "abcdefghijklmnopqrstuvwxyz";
+  CordRepRing* result = NeedsUnref(CordRepRing::Create(MakeFlat(str1)));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result->length, Eq(str1.size()));
+  EXPECT_THAT(ToFlats(result), ElementsAre(str1));
+  Unref(result);
+}
+
+TEST_P(CordRingCreateTest, CreateFromRing) {
+  CordRepRing* ring = RefIfShared(FromFlats(kFoxFlats));
+  CordRepRing* result = NeedsUnref(CordRepRing::Create(ring));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfPrivate(GetParam(), ring));
+  EXPECT_THAT(ToFlats(result), ElementsAreArray(kFoxFlats));
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingCreateFromTreeTest, CreateFromSubstringRing) {
+  CordRepRing* ring = RefIfInputSharedIndirect(FromFlats(kFoxFlats));
+  CordRep* sub = RefIfInputShared(MakeSubstring(2, 11, ring));
+  CordRepRing* result = NeedsUnref(CordRepRing::Create(sub));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfInputPrivate(GetParam(), ring));
+  EXPECT_THAT(ToString(result), string_view(kFox).substr(2, 11));
+  UnrefIfInputSharedIndirect(ring);
+  UnrefIfInputShared(sub);
+  Unref(result);
+}
+
+TEST_F(CordRingTest, CreateWithIllegalExtraCapacity) {
+  CordRep* flat = NeedsUnref(MakeFlat("Hello world"));
+#if defined(ABSL_HAVE_EXCEPTIONS)
+  try {
+    CordRepRing::Create(flat, CordRepRing::kMaxCapacity);
+    GTEST_FAIL() << "expected std::length_error exception";
+  } catch (const std::length_error&) {
+  }
+#elif defined(GTEST_HAS_DEATH_TEST)
+  EXPECT_DEATH(CordRepRing::Create(flat, CordRepRing::kMaxCapacity), ".*");
+#endif
+  Unref(flat);
+}
+
+TEST_P(CordRingCreateFromTreeTest, CreateFromSubstringOfFlat) {
+  absl::string_view str1 = "abcdefghijklmnopqrstuvwxyz";
+  auto* flat = RefIfInputShared(MakeFlat(str1));
+  auto* child = RefIfInputSharedIndirect(MakeSubstring(4, 20, flat));
+  CordRepRing* result = NeedsUnref(CordRepRing::Create(child));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result->length, Eq(20));
+  EXPECT_THAT(ToFlats(result), ElementsAre(str1.substr(4, 20)));
+  Unref(result);
+  UnrefIfInputShared(flat);
+  UnrefIfInputSharedIndirect(child);
+}
+
+TEST_P(CordRingCreateTest, CreateFromExternal) {
+  absl::string_view str1 = "abcdefghijklmnopqrstuvwxyz";
+  auto* child = RefIfInputShared(MakeExternal(str1));
+  CordRepRing* result = NeedsUnref(CordRepRing::Create(child));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result->length, Eq(str1.size()));
+  EXPECT_THAT(ToFlats(result), ElementsAre(str1));
+  Unref(result);
+  UnrefIfInputShared(child);
+}
+
+TEST_P(CordRingCreateFromTreeTest, CreateFromSubstringOfExternal) {
+  absl::string_view str1 = "abcdefghijklmnopqrstuvwxyz";
+  auto* external = RefIfInputShared(MakeExternal(str1));
+  auto* child = RefIfInputSharedIndirect(MakeSubstring(1, 24, external));
+  CordRepRing* result = NeedsUnref(CordRepRing::Create(child));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result->length, Eq(24));
+  EXPECT_THAT(ToFlats(result), ElementsAre(str1.substr(1, 24)));
+  Unref(result);
+  UnrefIfInputShared(external);
+  UnrefIfInputSharedIndirect(child);
+}
+
+TEST_P(CordRingCreateFromTreeTest, CreateFromSubstringOfLargeExternal) {
+  auto* external = RefIfInputShared(MakeFakeExternal(1 << 20));
+  auto str = not_a_string_view(external->base, 1 << 20)
+                 .remove_prefix(1 << 19)
+                 .remove_suffix(6);
+  auto* child =
+      RefIfInputSharedIndirect(MakeSubstring(1 << 19, (1 << 19) - 6, external));
+  CordRepRing* result = NeedsUnref(CordRepRing::Create(child));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result->length, Eq(str.size()));
+  EXPECT_THAT(ToRawFlats(result), ElementsAre(str));
+  Unref(result);
+  UnrefIfInputShared(external);
+  UnrefIfInputSharedIndirect(child);
+}
+
+TEST_P(CordRingBuildInputTest, CreateFromConcat) {
+  CordRep* flats[] = {MakeFlat("abcdefgh"), MakeFlat("ijklm"),
+                      MakeFlat("nopqrstuv"), MakeFlat("wxyz")};
+  auto* left = MakeConcat(RefIfInputSharedIndirect(flats[0]), flats[1]);
+  auto* right = MakeConcat(flats[2], RefIfInputSharedIndirect(flats[3]));
+  auto* concat = RefIfInputShared(MakeConcat(left, right));
+  CordRepRing* result = NeedsUnref(CordRepRing::Create(concat));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result->length, Eq(26));
+  EXPECT_THAT(ToString(result), Eq(kAlphabet));
+  UnrefIfInputSharedIndirect(flats[0]);
+  UnrefIfInputSharedIndirect(flats[3]);
+  UnrefIfInputShared(concat);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildInputTest, CreateFromSubstringConcat) {
+  for (size_t off = 0; off < 26; ++off) {
+    for (size_t len = 1; len < 26 - off; ++len) {
+      CordRep* flats[] = {MakeFlat("abcdefgh"), MakeFlat("ijklm"),
+                          MakeFlat("nopqrstuv"), MakeFlat("wxyz")};
+      auto* left = MakeConcat(RefIfInputSharedIndirect(flats[0]), flats[1]);
+      auto* right = MakeConcat(flats[2], RefIfInputSharedIndirect(flats[3]));
+      auto* concat = MakeConcat(left, right);
+      auto* child = RefIfInputShared(MakeSubstring(off, len, concat));
+      CordRepRing* result = NeedsUnref(CordRepRing::Create(child));
+      ASSERT_THAT(result, IsValidRingBuffer());
+      ASSERT_THAT(result->length, Eq(len));
+      ASSERT_THAT(ToString(result), string_view(kAlphabet).substr(off, len));
+      UnrefIfInputSharedIndirect(flats[0]);
+      UnrefIfInputSharedIndirect(flats[3]);
+      UnrefIfInputShared(child);
+      Unref(result);
+    }
+  }
+}
+
+TEST_P(CordRingCreateTest, Properties) {
+  absl::string_view str1 = "abcdefghijklmnopqrstuvwxyz";
+  CordRepRing* result = NeedsUnref(CordRepRing::Create(MakeFlat(str1), 120));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result->head(), Eq(0));
+  EXPECT_THAT(result->tail(), Eq(1));
+  EXPECT_THAT(result->capacity(), Ge(120 + 1));
+  EXPECT_THAT(result->capacity(), Le(2 * 120 + 1));
+  EXPECT_THAT(result->entries(), Eq(1));
+  EXPECT_THAT(result->begin_pos(), Eq(0));
+  Unref(result);
+}
+
+TEST_P(CordRingCreateTest, EntryForNewFlat) {
+  absl::string_view str1 = "abcdefghijklmnopqrstuvwxyz";
+  CordRep* child = MakeFlat(str1);
+  CordRepRing* result = NeedsUnref(CordRepRing::Create(child, 120));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result->entry_child(0), Eq(child));
+  EXPECT_THAT(result->entry_end_pos(0), Eq(str1.length()));
+  EXPECT_THAT(result->entry_data_offset(0), Eq(0));
+  Unref(result);
+}
+
+TEST_P(CordRingCreateTest, EntryForNewFlatSubstring) {
+  absl::string_view str1 = "1234567890abcdefghijklmnopqrstuvwxyz";
+  CordRep* child = MakeFlat(str1);
+  CordRep* substring = MakeSubstring(10, 26, child);
+  CordRepRing* result = NeedsUnref(CordRepRing::Create(substring, 1));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result->entry_child(0), Eq(child));
+  EXPECT_THAT(result->entry_end_pos(0), Eq(26));
+  EXPECT_THAT(result->entry_data_offset(0), Eq(10));
+  Unref(result);
+}
+
+TEST_P(CordRingBuildTest, AppendFlat) {
+  absl::string_view str1 = "abcdefghijklmnopqrstuvwxyz";
+  absl::string_view str2 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
+  CordRepRing* ring = CreateWithCapacity(MakeExternal(str1), 1);
+  CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, MakeFlat(str2)));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+  EXPECT_THAT(result->length, Eq(str1.size() + str2.size()));
+  EXPECT_THAT(ToFlats(result), ElementsAre(str1, str2));
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildTest, PrependFlat) {
+  absl::string_view str1 = "abcdefghijklmnopqrstuvwxyz";
+  absl::string_view str2 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
+  CordRepRing* ring = CreateWithCapacity(MakeExternal(str1), 1);
+  CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, MakeFlat(str2)));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+  EXPECT_THAT(result->length, Eq(str1.size() + str2.size()));
+  EXPECT_THAT(ToFlats(result), ElementsAre(str2, str1));
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildTest, AppendString) {
+  absl::string_view str1 = "abcdefghijklmnopqrstuvwxyz";
+  absl::string_view str2 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
+  CordRepRing* ring = CreateWithCapacity(MakeExternal(str1), 1);
+  CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, str2));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+  EXPECT_THAT(result->length, Eq(str1.size() + str2.size()));
+  EXPECT_THAT(ToFlats(result), ElementsAre(str1, str2));
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildTest, AppendStringHavingExtra) {
+  absl::string_view str1 = "1234";
+  absl::string_view str2 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
+  CordRepRing* ring = CreateWithCapacity(MakeFlat(str1, 26), 0);
+  CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, str2));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result->length, Eq(str1.size() + str2.size()));
+  EXPECT_THAT(result, EqIfPrivate(GetParam(), ring));
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildTest, AppendStringHavingPartialExtra) {
+  absl::string_view str1 = "1234";
+  absl::string_view str2 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
+
+  // Create flat with at least one extra byte. We don't expect to have sized
+  // alloc and capacity rounding to grant us enough to not make it partial.
+  auto* flat = MakeFlat(str1, 1);
+  size_t avail = flat->flat()->Capacity() - flat->length;
+  ASSERT_THAT(avail, Lt(str2.size())) << " adjust test for larger flats!";
+
+  // Construct the flats we do expect using all of `avail`.
+  absl::string_view str1a = str2.substr(0, avail);
+  absl::string_view str2a = str2.substr(avail);
+
+  CordRepRing* ring = CreateWithCapacity(flat, 1);
+  CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, str2));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result->length, Eq(str1.size() + str2.size()));
+  EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+  if (GetParam().refcount_is_one) {
+    EXPECT_THAT(ToFlats(result), ElementsAre(StrCat(str1, str1a), str2a));
+  } else {
+    EXPECT_THAT(ToFlats(result), ElementsAre(str1, str2));
+  }
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildTest, AppendStringHavingExtraInSubstring) {
+  absl::string_view str1 = "123456789_1234";
+  absl::string_view str2 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
+  CordRep* flat = RemovePrefix(10, MakeFlat(str1, 26));
+  CordRepRing* ring = CreateWithCapacity(flat, 0);
+  CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, str2));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfPrivate(GetParam(), ring));
+  EXPECT_THAT(result->length, Eq(4 + str2.size()));
+  if (GetParam().refcount_is_one) {
+    EXPECT_THAT(ToFlats(result), ElementsAre(StrCat("1234", str2)));
+  } else {
+    EXPECT_THAT(ToFlats(result), ElementsAre("1234", str2));
+  }
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildTest, AppendStringHavingSharedExtra) {
+  absl::string_view str1 = "123456789_1234";
+  absl::string_view str2 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
+  for (int shared_type = 0; shared_type < 2; ++shared_type) {
+    SCOPED_TRACE(absl::StrCat("Shared extra type ", shared_type));
+
+    // Create a flat that is shared in some way.
+    CordRep* flat = nullptr;
+    CordRep* flat1 = nullptr;
+    if (shared_type == 0) {
+      // Shared flat
+      flat = CordRep::Ref(MakeFlat(str1.substr(10), 100));
+    } else if (shared_type == 1) {
+      // Shared flat inside private substring
+      flat1 = CordRep::Ref(MakeFlat(str1));
+      flat = RemovePrefix(10, flat1);
+    } else {
+      // Private flat inside shared substring
+      flat = CordRep::Ref(RemovePrefix(10, MakeFlat(str1, 100)));
+    }
+
+    CordRepRing* ring = CreateWithCapacity(flat, 1);
+    CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, str2));
+    ASSERT_THAT(result, IsValidRingBuffer());
+    EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+    EXPECT_THAT(result->length, Eq(4 + str2.size()));
+    EXPECT_THAT(ToFlats(result), ElementsAre("1234", str2));
+    UnrefIfShared(ring);
+    Unref(result);
+
+    CordRep::Unref(shared_type == 1 ? flat1 : flat);
+  }
+}
+
+TEST_P(CordRingBuildTest, AppendStringWithExtra) {
+  absl::string_view str1 = "1234";
+  absl::string_view str2 = "1234567890";
+  absl::string_view str3 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
+  CordRepRing* ring = CreateWithCapacity(MakeExternal(str1), 1);
+  CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, str2, 26));
+  result = CordRepRing::Append(result, str3);
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result->length, Eq(str1.size() + str2.size() + str3.size()));
+  EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+  EXPECT_THAT(ToFlats(result), ElementsAre(str1, StrCat(str2, str3)));
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildTest, PrependString) {
+  absl::string_view str1 = "abcdefghijklmnopqrstuvwxyz";
+  absl::string_view str2 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
+  // Use external rep to avoid appending to first flat
+  CordRepRing* ring = CreateWithCapacity(MakeExternal(str1), 1);
+  CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, str2));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  if (GetParam().with_capacity && GetParam().refcount_is_one) {
+    EXPECT_THAT(result, Eq(ring));
+  } else {
+    EXPECT_THAT(result, Ne(ring));
+  }
+  EXPECT_THAT(result->length, Eq(str1.size() + str2.size()));
+  EXPECT_THAT(ToFlats(result), ElementsAre(str2, str1));
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildTest, PrependStringHavingExtra) {
+  absl::string_view str1 = "abcdefghijklmnopqrstuvwxyz1234";
+  absl::string_view str2 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
+  CordRep* flat = RemovePrefix(26, MakeFlat(str1));
+  CordRepRing* ring = CreateWithCapacity(flat, 0);
+  CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, str2));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfPrivate(GetParam(), ring));
+  EXPECT_THAT(result->length, Eq(4 + str2.size()));
+  if (GetParam().refcount_is_one) {
+    EXPECT_THAT(ToFlats(result), ElementsAre(StrCat(str2, "1234")));
+  } else {
+    EXPECT_THAT(ToFlats(result), ElementsAre(str2, "1234"));
+  }
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildTest, PrependStringHavingSharedExtra) {
+  absl::string_view str1 = "123456789_ABCDEFGHIJKLMNOPQRSTUVWXYZ";
+  absl::string_view str2 = "abcdefghij";
+  absl::string_view str1a = str1.substr(10);
+  for (int shared_type = 1; shared_type < 2; ++shared_type) {
+    SCOPED_TRACE(absl::StrCat("Shared extra type ", shared_type));
+
+    // Create a flat that is shared in some way.
+    CordRep* flat = nullptr;
+    CordRep* flat1 = nullptr;
+    if (shared_type == 1) {
+      // Shared flat inside private substring
+      flat = RemovePrefix(10, flat1 = CordRep::Ref(MakeFlat(str1)));
+    } else {
+      // Private flat inside shared substring
+      flat = CordRep::Ref(RemovePrefix(10, MakeFlat(str1, 100)));
+    }
+
+    CordRepRing* ring = CreateWithCapacity(flat, 1);
+    CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, str2));
+    ASSERT_THAT(result, IsValidRingBuffer());
+    EXPECT_THAT(result->length, Eq(str1a.size() + str2.size()));
+    EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+    EXPECT_THAT(ToFlats(result), ElementsAre(str2, str1a));
+    UnrefIfShared(ring);
+    Unref(result);
+    CordRep::Unref(shared_type == 1 ? flat1 : flat);
+  }
+}
+
+TEST_P(CordRingBuildTest, PrependStringWithExtra) {
+  absl::string_view str1 = "1234";
+  absl::string_view str2 = "1234567890";
+  absl::string_view str3 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
+  CordRepRing* ring = CreateWithCapacity(MakeExternal(str1), 1);
+  CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, str2, 26));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  result = CordRepRing::Prepend(result, str3);
+  EXPECT_THAT(result->length, Eq(str1.size() + str2.size() + str3.size()));
+  EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+  EXPECT_THAT(ToFlats(result), ElementsAre(StrCat(str3, str2), str1));
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildTest, AppendPrependStringMix) {
+  const auto& flats = kFoxFlats;
+  CordRepRing* ring = CreateWithCapacity(MakeFlat(flats[4]), 8);
+  CordRepRing* result = ring;
+  for (int i = 1; i <= 4; ++i) {
+    result = CordRepRing::Prepend(result, flats[4 - i]);
+    result = CordRepRing::Append(result, flats[4 + i]);
+  }
+  UnrefIfShared(ring);
+  NeedsUnref(result);
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+  EXPECT_THAT(ToString(result), kFox);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildTest, AppendPrependStringMixWithExtra) {
+  const auto& flats = kFoxFlats;
+  CordRepRing* ring = CreateWithCapacity(MakeFlat(flats[4], 100), 8);
+  CordRepRing* result = ring;
+  for (int i = 1; i <= 4; ++i) {
+    result = CordRepRing::Prepend(result, flats[4 - i], 100);
+    result = CordRepRing::Append(result, flats[4 + i], 100);
+  }
+  NeedsUnref(result);
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+  if (GetParam().refcount_is_one) {
+    EXPECT_THAT(ToFlats(result),
+                ElementsAre("The quick brown fox ", "jumps over the lazy dog"));
+  } else {
+    EXPECT_THAT(ToFlats(result), ElementsAre("The quick brown fox ", "jumps ",
+                                             "over the lazy dog"));
+  }
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildTest, AppendPrependStringMixWithPrependedExtra) {
+  const auto& flats = kFoxFlats;
+  CordRep* flat = MakeFlat(StrCat(std::string(50, '.'), flats[4]), 50);
+  CordRepRing* ring = CreateWithCapacity(RemovePrefix(50, flat), 0);
+  CordRepRing* result = ring;
+  for (int i = 1; i <= 4; ++i) {
+    result = CordRepRing::Prepend(result, flats[4 - i], 100);
+    result = CordRepRing::Append(result, flats[4 + i], 100);
+  }
+  result = NeedsUnref(result);
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfPrivate(GetParam(), ring));
+  if (GetParam().refcount_is_one) {
+    EXPECT_THAT(ToFlats(result), ElementsAre(kFox));
+  } else {
+    EXPECT_THAT(ToFlats(result), ElementsAre("The quick brown fox ", "jumps ",
+                                             "over the lazy dog"));
+  }
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingSubTest, SubRing) {
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  auto flats = MakeSpan(kFoxFlats);
+  string_view all = kFox;
+  for (size_t offset = 0; offset < all.size() - 1; ++offset) {
+    CordRepRing* ring = RefIfShared(FromFlats(flats, composition));
+    CordRepRing* result = CordRepRing::SubRing(ring, offset, 0);
+    EXPECT_THAT(result, nullptr);
+    UnrefIfShared(ring);
+
+    for (size_t len = 1; len < all.size() - offset; ++len) {
+      ring = RefIfShared(FromFlats(flats, composition));
+      result = NeedsUnref(CordRepRing::SubRing(ring, offset, len));
+      ASSERT_THAT(result, IsValidRingBuffer());
+      ASSERT_THAT(result, EqIfPrivate(GetParam(), ring));
+      ASSERT_THAT(ToString(result), Eq(all.substr(offset, len)));
+      UnrefIfShared(ring);
+      Unref(result);
+    }
+  }
+}
+
+TEST_P(CordRingSubTest, SubRingFromLargeExternal) {
+  auto composition = RandomComposition();
+  std::string large_string(1 << 20, '.');
+  const char* flats[] = {
+      "abcdefghijklmnopqrstuvwxyz",
+      large_string.c_str(),
+      "ABCDEFGHIJKLMNOPQRSTUVWXYZ",
+  };
+  std::string buffer = absl::StrCat(flats[0], flats[1], flats[2]);
+  absl::string_view all = buffer;
+  for (size_t offset = 0; offset < 30; ++offset) {
+    CordRepRing* ring = RefIfShared(FromFlats(flats, composition));
+    CordRepRing* result = CordRepRing::SubRing(ring, offset, 0);
+    EXPECT_THAT(result, nullptr);
+    UnrefIfShared(ring);
+
+    for (size_t len = all.size() - 30; len < all.size() - offset; ++len) {
+      ring = RefIfShared(FromFlats(flats, composition));
+      result = NeedsUnref(CordRepRing::SubRing(ring, offset, len));
+      ASSERT_THAT(result, IsValidRingBuffer());
+      ASSERT_THAT(result, EqIfPrivate(GetParam(), ring));
+      auto str = ToString(result);
+      ASSERT_THAT(str, SizeIs(len));
+      ASSERT_THAT(str, Eq(all.substr(offset, len)));
+      UnrefIfShared(ring);
+      Unref(result);
+    }
+  }
+}
+
+TEST_P(CordRingSubTest, RemovePrefix) {
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  auto flats = MakeSpan(kFoxFlats);
+  string_view all = kFox;
+  CordRepRing* ring = RefIfShared(FromFlats(flats, composition));
+  CordRepRing* result = CordRepRing::RemovePrefix(ring, all.size());
+  EXPECT_THAT(result, nullptr);
+  UnrefIfShared(ring);
+
+  for (size_t len = 1; len < all.size(); ++len) {
+    ring = RefIfShared(FromFlats(flats, composition));
+    result = NeedsUnref(CordRepRing::RemovePrefix(ring, len));
+    ASSERT_THAT(result, IsValidRingBuffer());
+    EXPECT_THAT(result, EqIfPrivate(GetParam(), ring));
+    EXPECT_THAT(ToString(result), Eq(all.substr(len)));
+    UnrefIfShared(ring);
+    Unref(result);
+  }
+}
+
+TEST_P(CordRingSubTest, RemovePrefixFromLargeExternal) {
+  CordRepExternal* external1 = MakeFakeExternal(1 << 20);
+  CordRepExternal* external2 = MakeFakeExternal(1 << 20);
+  CordRepRing* ring = CordRepRing::Create(external1, 1);
+  ring = CordRepRing::Append(ring, external2);
+  CordRepRing* result = NeedsUnref(CordRepRing::RemovePrefix(ring, 1 << 16));
+  EXPECT_THAT(
+      ToRawFlats(result),
+      ElementsAre(
+          not_a_string_view(external1->base, 1 << 20).remove_prefix(1 << 16),
+          not_a_string_view(external2->base, 1 << 20)));
+  Unref(result);
+}
+
+TEST_P(CordRingSubTest, RemoveSuffix) {
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  auto flats = MakeSpan(kFoxFlats);
+  string_view all = kFox;
+  CordRepRing* ring = RefIfShared(FromFlats(flats, composition));
+  CordRepRing* result = CordRepRing::RemoveSuffix(ring, all.size());
+  EXPECT_THAT(result, nullptr);
+  UnrefIfShared(ring);
+
+  for (size_t len = 1; len < all.size(); ++len) {
+    ring = RefIfShared(FromFlats(flats, composition));
+    result = NeedsUnref(CordRepRing::RemoveSuffix(ring, len));
+    ASSERT_THAT(result, IsValidRingBuffer());
+    EXPECT_THAT(result, EqIfPrivate(GetParam(), ring));
+    EXPECT_THAT(ToString(result), Eq(all.substr(0, all.size() - len)));
+    UnrefIfShared(ring);
+    Unref(result);
+  }
+}
+
+TEST_P(CordRingSubTest, AppendRing) {
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  auto flats = MakeSpan(kFoxFlats).subspan(1);
+  CordRepRing* ring = CreateWithCapacity(MakeFlat(kFoxFlats[0]), flats.size());
+  CordRepRing* child = FromFlats(flats, composition);
+  CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, child));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfPrivate(GetParam(), ring));
+  EXPECT_THAT(ToFlats(result), ElementsAreArray(kFoxFlats));
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildInputTest, AppendRingWithFlatOffset) {
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  auto flats = MakeSpan(kFoxFlats);
+  CordRepRing* ring = CreateWithCapacity(MakeFlat("Head"), flats.size());
+  CordRep* child = RefIfInputSharedIndirect(FromFlats(flats, composition));
+  CordRep* stripped = RemovePrefix(10, child);
+  CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, stripped));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+  EXPECT_THAT(ToFlats(result), ElementsAre("Head", "brown ", "fox ", "jumps ",
+                                           "over ", "the ", "lazy ", "dog"));
+  UnrefIfInputSharedIndirect(child);
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildInputTest, AppendRingWithBrokenOffset) {
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  auto flats = MakeSpan(kFoxFlats);
+  CordRepRing* ring = CreateWithCapacity(MakeFlat("Head"), flats.size());
+  CordRep* child = RefIfInputSharedIndirect(FromFlats(flats, composition));
+  CordRep* stripped = RemovePrefix(21, child);
+  CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, stripped));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+  EXPECT_THAT(ToFlats(result),
+              ElementsAre("Head", "umps ", "over ", "the ", "lazy ", "dog"));
+  UnrefIfInputSharedIndirect(child);
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildInputTest, AppendRingWithFlatLength) {
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  auto flats = MakeSpan(kFoxFlats);
+  CordRepRing* ring = CreateWithCapacity(MakeFlat("Head"), flats.size());
+  CordRep* child = RefIfInputSharedIndirect(FromFlats(flats, composition));
+  CordRep* stripped = RemoveSuffix(8, child);
+  CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, stripped));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+  EXPECT_THAT(ToFlats(result), ElementsAre("Head", "The ", "quick ", "brown ",
+                                           "fox ", "jumps ", "over ", "the "));
+  UnrefIfInputSharedIndirect(child);
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildTest, AppendRingWithBrokenFlatLength) {
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  auto flats = MakeSpan(kFoxFlats);
+  CordRepRing* ring = CreateWithCapacity(MakeFlat("Head"), flats.size());
+  CordRep* child = RefIfInputSharedIndirect(FromFlats(flats, composition));
+  CordRep* stripped = RemoveSuffix(15, child);
+  CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, stripped));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+  EXPECT_THAT(ToFlats(result), ElementsAre("Head", "The ", "quick ", "brown ",
+                                           "fox ", "jumps ", "ov"));
+  UnrefIfInputSharedIndirect(child);
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildTest, AppendRingMiddlePiece) {
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  auto flats = MakeSpan(kFoxFlats);
+  CordRepRing* ring = CreateWithCapacity(MakeFlat("Head"), flats.size());
+  CordRep* child = RefIfInputSharedIndirect(FromFlats(flats, composition));
+  CordRep* stripped = MakeSubstring(7, child->length - 27, child);
+  CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, stripped));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+  EXPECT_THAT(ToFlats(result),
+              ElementsAre("Head", "ck ", "brown ", "fox ", "jum"));
+  UnrefIfInputSharedIndirect(child);
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildTest, AppendRingSinglePiece) {
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  auto flats = MakeSpan(kFoxFlats);
+  CordRepRing* ring = CreateWithCapacity(MakeFlat("Head"), flats.size());
+  CordRep* child = RefIfInputSharedIndirect(FromFlats(flats, composition));
+  CordRep* stripped = RefIfInputShared(MakeSubstring(11, 3, child));
+  CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, stripped));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+  EXPECT_THAT(ToFlats(result), ElementsAre("Head", "row"));
+  UnrefIfInputSharedIndirect(child);
+  UnrefIfInputShared(stripped);
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildInputTest, AppendRingSinglePieceWithPrefix) {
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  auto flats = MakeSpan(kFoxFlats);
+  size_t extra_capacity = 1 + (GetParam().with_capacity ? flats.size() : 0);
+  CordRepRing* ring = CordRepRing::Create(MakeFlat("Head"), extra_capacity);
+  ring->SetCapacityForTesting(1 + extra_capacity);
+  ring = RefIfShared(CordRepRing::Prepend(ring, MakeFlat("Prepend")));
+  assert(ring->IsValid(std::cout));
+  CordRepRing* child = RefIfInputSharedIndirect(FromFlats(flats, composition));
+  CordRep* stripped = RefIfInputShared(MakeSubstring(11, 3, child));
+  CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, stripped));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+  EXPECT_THAT(ToFlats(result), ElementsAre("Prepend", "Head", "row"));
+  UnrefIfInputSharedIndirect(child);
+  UnrefIfInputShared(stripped);
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildInputTest, PrependRing) {
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  auto fox = MakeSpan(kFoxFlats);
+  auto flats = MakeSpan(fox).subspan(0, fox.size() - 1);
+  CordRepRing* ring = CreateWithCapacity(MakeFlat(fox.back()), flats.size());
+  CordRepRing* child = RefIfInputShared(FromFlats(flats, composition));
+  CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, child));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+  EXPECT_THAT(ToFlats(result), ElementsAreArray(kFoxFlats));
+  UnrefIfInputShared(child);
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildInputTest, PrependRingWithFlatOffset) {
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  auto flats = MakeSpan(kFoxFlats);
+  CordRepRing* ring = CreateWithCapacity(MakeFlat("Tail"), flats.size());
+  CordRep* child = RefIfInputShared(FromFlats(flats, composition));
+  CordRep* stripped = RefIfInputSharedIndirect(RemovePrefix(10, child));
+  CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, stripped));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+  EXPECT_THAT(ToFlats(result), ElementsAre("brown ", "fox ", "jumps ", "over ",
+                                           "the ", "lazy ", "dog", "Tail"));
+  UnrefIfInputShared(child);
+  UnrefIfInputSharedIndirect(stripped);
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildInputTest, PrependRingWithBrokenOffset) {
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  auto flats = MakeSpan(kFoxFlats);
+  CordRepRing* ring = CreateWithCapacity(MakeFlat("Tail"), flats.size());
+  CordRep* child = RefIfInputShared(FromFlats(flats, composition));
+  CordRep* stripped = RefIfInputSharedIndirect(RemovePrefix(21, child));
+  CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, stripped));
+  EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+  EXPECT_THAT(ToFlats(result),
+              ElementsAre("umps ", "over ", "the ", "lazy ", "dog", "Tail"));
+  UnrefIfInputShared(child);
+  UnrefIfInputSharedIndirect(stripped);
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildInputTest, PrependRingWithFlatLength) {
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  auto flats = MakeSpan(kFoxFlats);
+  CordRepRing* ring = CreateWithCapacity(MakeFlat("Tail"), flats.size());
+  CordRep* child = RefIfInputShared(FromFlats(flats, composition));
+  CordRep* stripped = RefIfInputSharedIndirect(RemoveSuffix(8, child));
+  CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, stripped));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+  EXPECT_THAT(ToFlats(result), ElementsAre("The ", "quick ", "brown ", "fox ",
+                                           "jumps ", "over ", "the ", "Tail"));
+  UnrefIfShared(ring);
+  UnrefIfInputShared(child);
+  UnrefIfInputSharedIndirect(stripped);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildInputTest, PrependRingWithBrokenFlatLength) {
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  auto flats = MakeSpan(kFoxFlats);
+  CordRepRing* ring = CreateWithCapacity(MakeFlat("Tail"), flats.size());
+  CordRep* child = RefIfInputShared(FromFlats(flats, composition));
+  CordRep* stripped = RefIfInputSharedIndirect(RemoveSuffix(15, child));
+  CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, stripped));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+  EXPECT_THAT(ToFlats(result), ElementsAre("The ", "quick ", "brown ", "fox ",
+                                           "jumps ", "ov", "Tail"));
+  UnrefIfInputShared(child);
+  UnrefIfInputSharedIndirect(stripped);
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildInputTest, PrependRingMiddlePiece) {
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  auto flats = MakeSpan(kFoxFlats);
+  CordRepRing* ring = CreateWithCapacity(MakeFlat("Tail"), flats.size());
+  CordRep* child = RefIfInputShared(FromFlats(flats, composition));
+  CordRep* stripped =
+      RefIfInputSharedIndirect(MakeSubstring(7, child->length - 27, child));
+  CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, stripped));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+  EXPECT_THAT(ToFlats(result),
+              ElementsAre("ck ", "brown ", "fox ", "jum", "Tail"));
+  UnrefIfInputShared(child);
+  UnrefIfInputSharedIndirect(stripped);
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildInputTest, PrependRingSinglePiece) {
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  auto flats = MakeSpan(kFoxFlats);
+  CordRepRing* ring = CreateWithCapacity(MakeFlat("Tail"), flats.size());
+  CordRep* child = RefIfInputShared(FromFlats(flats, composition));
+  CordRep* stripped = RefIfInputSharedIndirect(MakeSubstring(11, 3, child));
+  CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, stripped));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+  EXPECT_THAT(ToFlats(result), ElementsAre("row", "Tail"));
+  UnrefIfInputShared(child);
+  UnrefIfInputSharedIndirect(stripped);
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_P(CordRingBuildInputTest, PrependRingSinglePieceWithPrefix) {
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  auto flats = MakeSpan(kFoxFlats);
+  size_t extra_capacity = 1 + (GetParam().with_capacity ? flats.size() : 0);
+  CordRepRing* ring = CordRepRing::Create(MakeFlat("Tail"), extra_capacity);
+  ring->SetCapacityForTesting(1 + extra_capacity);
+  ring = RefIfShared(CordRepRing::Prepend(ring, MakeFlat("Prepend")));
+  CordRep* child = RefIfInputShared(FromFlats(flats, composition));
+  CordRep* stripped = RefIfInputSharedIndirect(MakeSubstring(11, 3, child));
+  CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, stripped));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring));
+  EXPECT_THAT(ToFlats(result), ElementsAre("row", "Prepend", "Tail"));
+  UnrefIfInputShared(child);
+  UnrefIfInputSharedIndirect(stripped);
+  UnrefIfShared(ring);
+  Unref(result);
+}
+
+TEST_F(CordRingTest, Find) {
+  constexpr const char* flats[] = {
+      "abcdefghij", "klmnopqrst", "uvwxyz",     "ABCDEFGHIJ",
+      "KLMNOPQRST", "UVWXYZ",     "1234567890", "~!@#$%^&*()_",
+      "+-=",        "[]\\{}|;':", ",/<>?",      "."};
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  CordRepRing* ring = NeedsUnref(FromFlats(flats, composition));
+  std::string value = ToString(ring);
+  for (int i = 0; i < value.length(); ++i) {
+    CordRepRing::Position found = ring->Find(i);
+    auto data = ring->entry_data(found.index);
+    ASSERT_THAT(found.offset, Lt(data.length()));
+    ASSERT_THAT(data[found.offset], Eq(value[i]));
+  }
+  Unref(ring);
+}
+
+TEST_F(CordRingTest, FindWithHint) {
+  constexpr const char* flats[] = {
+      "abcdefghij", "klmnopqrst", "uvwxyz",     "ABCDEFGHIJ",
+      "KLMNOPQRST", "UVWXYZ",     "1234567890", "~!@#$%^&*()_",
+      "+-=",        "[]\\{}|;':", ",/<>?",      "."};
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  CordRepRing* ring = NeedsUnref(FromFlats(flats, composition));
+  std::string value = ToString(ring);
+
+#if defined(GTEST_HAS_DEATH_TEST)
+  // Test hint beyond valid position
+  index_type head = ring->head();
+  EXPECT_DEBUG_DEATH(ring->Find(ring->advance(head), 0), ".*");
+  EXPECT_DEBUG_DEATH(ring->Find(ring->advance(head), 9), ".*");
+  EXPECT_DEBUG_DEATH(ring->Find(ring->advance(head, 3), 24), ".*");
+#endif
+
+  int flat_pos = 0;
+  size_t flat_offset = 0;
+  for (auto sflat : flats) {
+    string_view flat(sflat);
+    for (int offset = 0; offset < flat.length(); ++offset) {
+      for (int start = 0; start <= flat_pos; ++start) {
+        index_type hint = ring->advance(ring->head(), start);
+        CordRepRing::Position found = ring->Find(hint, flat_offset + offset);
+        ASSERT_THAT(found.index, Eq(ring->advance(ring->head(), flat_pos)));
+        ASSERT_THAT(found.offset, Eq(offset));
+      }
+    }
+    ++flat_pos;
+    flat_offset += flat.length();
+  }
+  Unref(ring);
+}
+
+TEST_F(CordRingTest, FindInLargeRing) {
+  constexpr const char* flats[] = {
+      "abcdefghij", "klmnopqrst", "uvwxyz",     "ABCDEFGHIJ",
+      "KLMNOPQRST", "UVWXYZ",     "1234567890", "~!@#$%^&*()_",
+      "+-=",        "[]\\{}|;':", ",/<>?",      "."};
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  CordRepRing* ring = FromFlats(flats, composition);
+  for (int i = 0; i < 13; ++i) {
+    ring = CordRepRing::Append(ring, FromFlats(flats, composition));
+  }
+  NeedsUnref(ring);
+  std::string value = ToString(ring);
+  for (int i = 0; i < value.length(); ++i) {
+    CordRepRing::Position pos = ring->Find(i);
+    auto data = ring->entry_data(pos.index);
+    ASSERT_THAT(pos.offset, Lt(data.length()));
+    ASSERT_THAT(data[pos.offset], Eq(value[i]));
+  }
+  Unref(ring);
+}
+
+TEST_F(CordRingTest, FindTail) {
+  constexpr const char* flats[] = {
+      "abcdefghij", "klmnopqrst", "uvwxyz",     "ABCDEFGHIJ",
+      "KLMNOPQRST", "UVWXYZ",     "1234567890", "~!@#$%^&*()_",
+      "+-=",        "[]\\{}|;':", ",/<>?",      "."};
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  CordRepRing* ring = NeedsUnref(FromFlats(flats, composition));
+  std::string value = ToString(ring);
+
+  for (int i = 0; i < value.length(); ++i) {
+    CordRepRing::Position pos = ring->FindTail(i + 1);
+    auto data = ring->entry_data(ring->retreat(pos.index));
+    ASSERT_THAT(pos.offset, Lt(data.length()));
+    ASSERT_THAT(data[data.length() - pos.offset - 1], Eq(value[i]));
+  }
+  Unref(ring);
+}
+
+TEST_F(CordRingTest, FindTailWithHint) {
+  constexpr const char* flats[] = {
+      "abcdefghij", "klmnopqrst", "uvwxyz",     "ABCDEFGHIJ",
+      "KLMNOPQRST", "UVWXYZ",     "1234567890", "~!@#$%^&*()_",
+      "+-=",        "[]\\{}|;':", ",/<>?",      "."};
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  CordRepRing* ring = NeedsUnref(FromFlats(flats, composition));
+  std::string value = ToString(ring);
+
+  // Test hint beyond valid position
+#if defined(GTEST_HAS_DEATH_TEST)
+  index_type head = ring->head();
+  EXPECT_DEBUG_DEATH(ring->FindTail(ring->advance(head), 1), ".*");
+  EXPECT_DEBUG_DEATH(ring->FindTail(ring->advance(head), 10), ".*");
+  EXPECT_DEBUG_DEATH(ring->FindTail(ring->advance(head, 3), 26), ".*");
+#endif
+
+  for (int i = 0; i < value.length(); ++i) {
+    CordRepRing::Position pos = ring->FindTail(i + 1);
+    auto data = ring->entry_data(ring->retreat(pos.index));
+    ASSERT_THAT(pos.offset, Lt(data.length()));
+    ASSERT_THAT(data[data.length() - pos.offset - 1], Eq(value[i]));
+  }
+  Unref(ring);
+}
+
+TEST_F(CordRingTest, FindTailInLargeRing) {
+  constexpr const char* flats[] = {
+      "abcdefghij", "klmnopqrst", "uvwxyz",     "ABCDEFGHIJ",
+      "KLMNOPQRST", "UVWXYZ",     "1234567890", "~!@#$%^&*()_",
+      "+-=",        "[]\\{}|;':", ",/<>?",      "."};
+  auto composition = RandomComposition();
+  SCOPED_TRACE(ToString(composition));
+  CordRepRing* ring = FromFlats(flats, composition);
+  for (int i = 0; i < 13; ++i) {
+    ring = CordRepRing::Append(ring, FromFlats(flats, composition));
+  }
+  NeedsUnref(ring);
+  std::string value = ToString(ring);
+  for (int i = 0; i < value.length(); ++i) {
+    CordRepRing::Position pos = ring->FindTail(i + 1);
+    auto data = ring->entry_data(ring->retreat(pos.index));
+    ASSERT_THAT(pos.offset, Lt(data.length()));
+    ASSERT_THAT(data[data.length() - pos.offset - 1], Eq(value[i]));
+  }
+  Unref(ring);
+}
+
+TEST_F(CordRingTest, GetCharacter) {
+  auto flats = MakeSpan(kFoxFlats);
+  CordRepRing* ring = CordRepRing::Create(MakeFlat("Tail"), flats.size());
+  CordRep* child = FromFlats(flats, kAppend);
+  CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, child));
+  std::string value = ToString(result);
+  for (int i = 0; i < value.length(); ++i) {
+    ASSERT_THAT(result->GetCharacter(i), Eq(value[i]));
+  }
+  Unref(result);
+}
+
+TEST_F(CordRingTest, GetCharacterWithSubstring) {
+  absl::string_view str1 = "abcdefghijklmnopqrstuvwxyz";
+  auto* child = MakeSubstring(4, 20, MakeFlat(str1));
+  CordRepRing* result = NeedsUnref(CordRepRing::Create(child));
+  ASSERT_THAT(result, IsValidRingBuffer());
+  std::string value = ToString(result);
+  for (int i = 0; i < value.length(); ++i) {
+    ASSERT_THAT(result->GetCharacter(i), Eq(value[i]));
+  }
+  Unref(result);
+}
+
+TEST_F(CordRingTest, Dump) {
+  std::stringstream ss;
+  auto flats = MakeSpan(kFoxFlats);
+  CordRepRing* ring = NeedsUnref(FromFlats(flats, kPrepend));
+  ss << *ring;
+  Unref(ring);
+}
+
+}  // namespace
+ABSL_NAMESPACE_END
+}  // namespace absl
diff --git a/absl/strings/internal/cord_internal.cc b/absl/strings/internal/cord_internal.cc
index 59f2e4d9..905ffd0c 100644
--- a/absl/strings/internal/cord_internal.cc
+++ b/absl/strings/internal/cord_internal.cc
@@ -19,6 +19,7 @@
 
 #include "absl/container/inlined_vector.h"
 #include "absl/strings/internal/cord_rep_flat.h"
+#include "absl/strings/internal/cord_rep_ring.h"
 
 namespace absl {
 ABSL_NAMESPACE_BEGIN
@@ -48,6 +49,9 @@ void CordRep::Destroy(CordRep* rep) {
         rep = left;
         continue;
       }
+    } else if (rep->tag == RING) {
+      CordRepRing::Destroy(rep->ring());
+      rep = nullptr;
     } else if (rep->tag == EXTERNAL) {
       CordRepExternal::Delete(rep);
       rep = nullptr;
diff --git a/absl/strings/internal/cord_internal.h b/absl/strings/internal/cord_internal.h
index b586ea37..011b49d3 100644
--- a/absl/strings/internal/cord_internal.h
+++ b/absl/strings/internal/cord_internal.h
@@ -1,4 +1,4 @@
-// Copyright 2020 The Abseil Authors.
+// Copyright 2021 The Abseil Authors.
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
 // you may not use this file except in compliance with the License.
@@ -21,6 +21,7 @@
 #include <cstdint>
 #include <type_traits>
 
+#include "absl/base/config.h"
 #include "absl/base/internal/invoke.h"
 #include "absl/base/optimization.h"
 #include "absl/container/internal/compressed_tuple.h"
@@ -145,13 +146,14 @@ struct CordRepConcat;
 struct CordRepExternal;
 struct CordRepFlat;
 struct CordRepSubstring;
+class CordRepRing;
 
 // Various representations that we allow
 enum CordRepKind {
-  CONCAT        = 0,
-  EXTERNAL      = 1,
-  SUBSTRING     = 2,
-  RING          = 3,
+  CONCAT = 0,
+  EXTERNAL = 1,
+  SUBSTRING = 2,
+  RING = 3,
 
   // We have different tags for different sized flat arrays,
   // starting with FLAT, and limited to MAX_FLAT_TAG. The 224 value is based on
@@ -160,7 +162,7 @@ enum CordRepKind {
   // as the Tag <---> Size logic so that FLAT stil represents the minimum flat
   // allocation size. (32 bytes as of now).
   FLAT = 4,
-  MAX_FLAT_TAG = 224,
+  MAX_FLAT_TAG = 224
 };
 
 struct CordRep {
@@ -177,6 +179,8 @@ struct CordRep {
   uint8_t tag;
   char storage[1];  // Starting point for flat array: MUST BE LAST FIELD
 
+  inline CordRepRing* ring();
+  inline const CordRepRing* ring() const;
   inline CordRepConcat* concat();
   inline const CordRepConcat* concat() const;
   inline CordRepSubstring* substring();
@@ -306,45 +310,165 @@ CordRepExternal ConstInitExternalStorage<Str>::value(Str::value);
 
 enum {
   kMaxInline = 15,
-  // Tag byte & kMaxInline means we are storing a pointer.
-  kTreeFlag = 1 << 4,
-  // Tag byte & kProfiledFlag means we are profiling the Cord.
-  kProfiledFlag = 1 << 5
-};
-
-// If the data has length <= kMaxInline, we store it in `as_chars`, and
-// store the size in `tagged_size`.
-// Else we store it in a tree and store a pointer to that tree in
-// `as_tree.rep` and store a tag in `tagged_size`.
-struct AsTree {
-  absl::cord_internal::CordRep* rep;
-  char padding[kMaxInline + 1 - sizeof(absl::cord_internal::CordRep*) - 1];
-  char tagged_size;
 };
 
 constexpr char GetOrNull(absl::string_view data, size_t pos) {
   return pos < data.size() ? data[pos] : '\0';
 }
 
-union InlineData {
-  constexpr InlineData() : as_chars{} {}
-  explicit constexpr InlineData(AsTree tree) : as_tree(tree) {}
+// We store cordz_info as 64 bit pointer value in big endian format. This
+// guarantees that the least significant byte of cordz_info matches the last
+// byte of the inline data representation in as_chars_, which holds the inlined
+// size or the 'is_tree' bit.
+using cordz_info_t = int64_t;
+
+// Assert that the `cordz_info` pointer value perfectly overlaps the last half
+// of `as_chars_` and can hold a pointer value.
+static_assert(sizeof(cordz_info_t) * 2 == kMaxInline + 1, "");
+static_assert(sizeof(cordz_info_t) >= sizeof(intptr_t), "");
+
+// BigEndianByte() creates a big endian representation of 'value', i.e.: a big
+// endian value where the last byte in the host's representation holds 'value`,
+// with all other bytes being 0.
+static constexpr cordz_info_t BigEndianByte(unsigned char value) {
+#if defined(ABSL_IS_BIG_ENDIAN)
+  return value;
+#else
+  return static_cast<cordz_info_t>(value) << ((sizeof(cordz_info_t) - 1) * 8);
+#endif
+}
+
+class InlineData {
+ public:
+  // kNullCordzInfo holds the big endian representation of intptr_t(1)
+  // This is the 'null' / initial value of 'cordz_info'. The null value
+  // is specifically big endian 1 as with 64-bit pointers, the last
+  // byte of cordz_info overlaps with the last byte holding the tag.
+  static constexpr cordz_info_t kNullCordzInfo = BigEndianByte(1);
+
+  // kFakeCordzInfo holds a 'fake', non-null cordz-info value we use to
+  // emulate the previous 'kProfiled' tag logic in 'set_profiled' until
+  // cord code is changed to store cordz_info values in InlineData.
+  static constexpr cordz_info_t kFakeCordzInfo = BigEndianByte(9);
+
+  constexpr InlineData() : as_chars_{0} {}
+  explicit constexpr InlineData(CordRep* rep) : as_tree_(rep) {}
   explicit constexpr InlineData(absl::string_view chars)
-      : as_chars{GetOrNull(chars, 0),  GetOrNull(chars, 1),
-                 GetOrNull(chars, 2),  GetOrNull(chars, 3),
-                 GetOrNull(chars, 4),  GetOrNull(chars, 5),
-                 GetOrNull(chars, 6),  GetOrNull(chars, 7),
-                 GetOrNull(chars, 8),  GetOrNull(chars, 9),
-                 GetOrNull(chars, 10), GetOrNull(chars, 11),
-                 GetOrNull(chars, 12), GetOrNull(chars, 13),
-                 GetOrNull(chars, 14), static_cast<char>(chars.size())} {}
-
-  AsTree as_tree;
-  char as_chars[kMaxInline + 1];
+      : as_chars_{
+            GetOrNull(chars, 0),  GetOrNull(chars, 1),
+            GetOrNull(chars, 2),  GetOrNull(chars, 3),
+            GetOrNull(chars, 4),  GetOrNull(chars, 5),
+            GetOrNull(chars, 6),  GetOrNull(chars, 7),
+            GetOrNull(chars, 8),  GetOrNull(chars, 9),
+            GetOrNull(chars, 10), GetOrNull(chars, 11),
+            GetOrNull(chars, 12), GetOrNull(chars, 13),
+            GetOrNull(chars, 14), static_cast<char>((chars.size() << 1))} {}
+
+  // Returns true if the current instance is empty.
+  // The 'empty value' is an inlined data value of zero length.
+  bool is_empty() const { return tag() == 0; }
+
+  // Returns true if the current instance holds a tree value.
+  bool is_tree() const { return (tag() & 1) != 0; }
+
+  // Returns true if the current instance holds a cordz_info value.
+  // Requires the current instance to hold a tree value.
+  bool is_profiled() const {
+    assert(is_tree());
+    return as_tree_.cordz_info != kNullCordzInfo;
+  }
+
+  // Returns a read only pointer to the character data inside this instance.
+  // Requires the current instance to hold inline data.
+  const char* as_chars() const {
+    assert(!is_tree());
+    return as_chars_;
+  }
+
+  // Returns a mutable pointer to the character data inside this instance.
+  // Should be used for 'write only' operations setting an inlined value.
+  // Applications can set the value of inlined data either before or after
+  // setting the inlined size, i.e., both of the below are valid:
+  //
+  //   // Set inlined data and inline size
+  //   memcpy(data_.as_chars(), data, size);
+  //   data_.set_inline_size(size);
+  //
+  //   // Set inlined size and inline data
+  //   data_.set_inline_size(size);
+  //   memcpy(data_.as_chars(), data, size);
+  //
+  // It's an error to read from the returned pointer without a preceding write
+  // if the current instance does not hold inline data, i.e.: is_tree() == true.
+  char* as_chars() { return as_chars_; }
+
+  // Returns the tree value of this value.
+  // Requires the current instance to hold a tree value.
+  CordRep* as_tree() const {
+    assert(is_tree());
+    return as_tree_.rep;
+  }
+
+  // Initialize this instance to holding the tree value `rep`,
+  // initializing the cordz_info to null, i.e.: 'not profiled'.
+  void make_tree(CordRep* rep) {
+    as_tree_.rep = rep;
+    as_tree_.cordz_info = kNullCordzInfo;
+  }
+
+  // Set the tree value of this instance to 'rep`.
+  // Requires the current instance to already hold a tree value.
+  // Does not affect the value of cordz_info.
+  void set_tree(CordRep* rep) {
+    assert(is_tree());
+    as_tree_.rep = rep;
+  }
+
+  // Returns the size of the inlined character data inside this instance.
+  // Requires the current instance to hold inline data.
+  size_t inline_size() const {
+    assert(!is_tree());
+    return tag() >> 1;
+  }
+
+  // Sets the size of the inlined character data inside this instance.
+  // Requires `size` to be <= kMaxInline.
+  // See the documentation on 'as_chars()' for more information and examples.
+  void set_inline_size(size_t size) {
+    ABSL_ASSERT(size <= kMaxInline);
+    tag() = static_cast<char>(size << 1);
+  }
+
+  // Sets or unsets the 'is_profiled' state of this instance.
+  // Requires the current instance to hold a tree value.
+  void set_profiled(bool profiled) {
+    assert(is_tree());
+    as_tree_.cordz_info = profiled ? kFakeCordzInfo : kNullCordzInfo;
+  }
+
+ private:
+  // See cordz_info_t for forced alignment and size of `cordz_info` details.
+  struct AsTree {
+    explicit constexpr AsTree(absl::cord_internal::CordRep* tree)
+        : rep(tree), cordz_info(kNullCordzInfo) {}
+    absl::cord_internal::CordRep* rep;
+    alignas(sizeof(cordz_info_t)) cordz_info_t cordz_info;
+  };
+
+  char& tag() { return reinterpret_cast<char*>(this)[kMaxInline]; }
+  char tag() const { return reinterpret_cast<const char*>(this)[kMaxInline]; }
+
+  // If the data has length <= kMaxInline, we store it in `as_chars_`, and
+  // store the size in the last char of `as_chars_` shifted left + 1.
+  // Else we store it in a tree and store a pointer to that tree in
+  // `as_tree_.rep` and store a tag in `tagged_size`.
+  union  {
+    char as_chars_[kMaxInline + 1];
+    AsTree as_tree_;
+  };
 };
+
 static_assert(sizeof(InlineData) == kMaxInline + 1, "");
-static_assert(sizeof(AsTree) == sizeof(InlineData), "");
-static_assert(offsetof(AsTree, tagged_size) == kMaxInline, "");
 
 inline CordRepConcat* CordRep::concat() {
   assert(tag == CONCAT);
@@ -386,6 +510,16 @@ inline const CordRepFlat* CordRep::flat() const {
   return reinterpret_cast<const CordRepFlat*>(this);
 }
 
+inline CordRepRing* CordRep::ring() {
+  assert(tag == RING);
+  return reinterpret_cast<CordRepRing*>(this);
+}
+
+inline const CordRepRing* CordRep::ring() const {
+  assert(tag == RING);
+  return reinterpret_cast<const CordRepRing*>(this);
+}
+
 inline CordRep* CordRep::Ref(CordRep* rep) {
   assert(rep != nullptr);
   rep->refcount.Increment();
diff --git a/absl/strings/internal/cord_rep_flat.h b/absl/strings/internal/cord_rep_flat.h
index 8c7d160e..5f7d55ce 100644
--- a/absl/strings/internal/cord_rep_flat.h
+++ b/absl/strings/internal/cord_rep_flat.h
@@ -104,7 +104,8 @@ struct CordRepFlat : public CordRep {
   // Flat CordReps are allocated and constructed with raw ::operator new and
   // placement new, and must be destructed and deallocated accordingly.
   static void Delete(CordRep*rep) {
-    assert(rep->tag >= FLAT);
+    assert(rep->tag >= FLAT && rep->tag <= MAX_FLAT_TAG);
+
 #if defined(__cpp_sized_deallocation)
     size_t size = TagToAllocatedSize(rep->tag);
     rep->~CordRep();
@@ -115,6 +116,7 @@ struct CordRepFlat : public CordRep {
 #endif
   }
 
+  // Returns a pointer to the data inside this flat rep.
   char* Data() { return storage; }
   const char* Data() const { return storage; }
 
diff --git a/absl/strings/internal/cord_rep_ring.cc b/absl/strings/internal/cord_rep_ring.cc
new file mode 100644
index 00000000..358b0d92
--- /dev/null
+++ b/absl/strings/internal/cord_rep_ring.cc
@@ -0,0 +1,895 @@
+// Copyright 2020 The Abseil Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// 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.
+#include "absl/strings/internal/cord_rep_ring.h"
+
+#include <cassert>
+#include <cstddef>
+#include <cstdint>
+#include <iostream>
+#include <limits>
+#include <memory>
+#include <string>
+
+#include "absl/base/internal/raw_logging.h"
+#include "absl/base/internal/throw_delegate.h"
+#include "absl/base/macros.h"
+#include "absl/container/inlined_vector.h"
+#include "absl/strings/internal/cord_internal.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"
+#pragma clang diagnostic ignored "-Wshadow-field"
+#endif
+
+namespace {
+
+using index_type = CordRepRing::index_type;
+
+enum class Direction { kForward, kReversed };
+
+inline bool IsFlatOrExternal(CordRep* rep) {
+  return rep->tag >= FLAT || rep->tag == EXTERNAL;
+}
+
+// Verifies that n + extra <= kMaxCapacity: throws std::length_error otherwise.
+inline void CheckCapacity(size_t n, size_t extra) {
+  if (ABSL_PREDICT_FALSE(extra > CordRepRing::kMaxCapacity - n)) {
+    base_internal::ThrowStdLengthError("Maximum capacity exceeded");
+  }
+}
+
+// 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`
+CordRepFlat* CreateFlat(const char* s, size_t n, size_t extra = 0) {  // NOLINT
+  assert(n <= kMaxFlatLength);
+  auto* rep = CordRepFlat::New(n + extra);
+  rep->length = n;
+  memcpy(rep->Data(), s, n);
+  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) {
+  rep->ForEach(head, tail, [rep](index_type ix) {
+    CordRep* child = rep->entry_child(ix);
+    if (!child->refcount.Decrement()) {
+      if (child->tag >= FLAT) {
+        CordRepFlat::Delete(child->flat());
+      } else {
+        CordRepExternal::Delete(child->external());
+      }
+    }
+  });
+}
+
+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) {
+  // Note: 'pos' values are defined as size_t (for overflow reasons), but that
+  // prints really awkward for small prepended values such as -5. ssize_t is not
+  // portable (POSIX), so we use ptrdiff_t instead to cast to signed values.
+  s << "  CordRepRing(" << &rep << ", length = " << rep.length
+    << ", head = " << rep.head_ << ", tail = " << rep.tail_
+    << ", cap = " << rep.capacity_ << ", rc = " << rep.refcount.Get()
+    << ", begin_pos_ = " << static_cast<ptrdiff_t>(rep.begin_pos_) << ") {\n";
+  CordRepRing::index_type head = rep.head();
+  do {
+    CordRep* child = rep.entry_child(head);
+    s << " entry[" << head << "] length = " << rep.entry_length(head)
+      << ", child " << child << ", clen = " << child->length
+      << ", tag = " << static_cast<int>(child->tag)
+      << ", rc = " << child->refcount.Get()
+      << ", offset = " << rep.entry_data_offset(head)
+      << ", end_pos = " << static_cast<ptrdiff_t>(rep.entry_end_pos(head))
+      << "\n";
+    head = rep.advance(head);
+  } while (head != rep.tail());
+  return s << "}\n";
+}
+
+void CordRepRing::AddDataOffset(index_type index, size_t n) {
+  entry_data_offset()[index] += static_cast<offset_type>(n);
+}
+
+void CordRepRing::SubLength(index_type index, size_t n) {
+  entry_end_pos()[index] -= n;
+}
+
+class CordRepRing::Filler {
+ public:
+  Filler(CordRepRing* rep, index_type pos) : rep_(rep), head_(pos), pos_(pos) {}
+
+  index_type head() const { return head_; }
+  index_type pos() const { return pos_; }
+
+  void Add(CordRep* child, size_t offset, pos_type end_pos) {
+    rep_->entry_end_pos()[pos_] = end_pos;
+    rep_->entry_child()[pos_] = child;
+    rep_->entry_data_offset()[pos_] = static_cast<offset_type>(offset);
+    pos_ = rep_->advance(pos_);
+  }
+
+ private:
+  CordRepRing* rep_;
+  index_type head_;
+  index_type pos_;
+};
+
+constexpr size_t CordRepRing::kMaxCapacity; // NOLINT: needed for c++11
+
+bool CordRepRing::IsValid(std::ostream& output) const {
+  if (capacity_ == 0) {
+    output << "capacity == 0";
+    return false;
+  }
+
+  if (head_ >= capacity_ || tail_ >= capacity_) {
+    output << "head " << head_ << " and/or tail " << tail_ << "exceed capacity "
+           << capacity_;
+    return false;
+  }
+
+  const index_type back = retreat(tail_);
+  size_t pos_length = Distance(begin_pos_, entry_end_pos(back));
+  if (pos_length != length) {
+    output << "length " << length << " does not match positional length "
+           << pos_length << " from begin_pos " << begin_pos_ << " and entry["
+           << back << "].end_pos " << entry_end_pos(back);
+    return false;
+  }
+
+  index_type head = head_;
+  pos_type begin_pos = begin_pos_;
+  do {
+    pos_type end_pos = entry_end_pos(head);
+    size_t entry_length = Distance(begin_pos, end_pos);
+    if (entry_length == 0) {
+      output << "entry[" << head << "] has an invalid length " << entry_length
+             << " from begin_pos " << begin_pos << " and end_pos " << end_pos;
+      return false;
+    }
+
+    CordRep* child = entry_child(head);
+    if (child == nullptr) {
+      output << "entry[" << head << "].child == nullptr";
+      return false;
+    }
+    if (child->tag < FLAT && child->tag != EXTERNAL) {
+      output << "entry[" << head << "].child has an invalid tag "
+             << static_cast<int>(child->tag);
+      return false;
+    }
+
+    size_t offset = entry_data_offset(head);
+    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;
+      return false;
+    }
+
+    begin_pos = end_pos;
+    head = advance(head);
+  } while (head != tail_);
+
+  return true;
+}
+
+#ifdef EXTRA_CORD_RING_VALIDATION
+CordRepRing* CordRepRing::Validate(CordRepRing* rep, const char* file,
+                                   int line) {
+  if (!rep->IsValid(std::cerr)) {
+    std::cerr << "\nERROR: CordRepRing corrupted";
+    if (line) std::cerr << " at line " << line;
+    if (file) std::cerr << " in file " << file;
+    std::cerr << "\nContent = " << *rep;
+    abort();
+  }
+  return rep;
+}
+#endif  // EXTRA_CORD_RING_VALIDATION
+
+CordRepRing* CordRepRing::New(size_t capacity, size_t extra) {
+  CheckCapacity(capacity, extra);
+
+  size_t size = AllocSize(capacity += extra);
+  void* mem = ::operator new(size);
+  auto* rep = new (mem) CordRepRing(static_cast<index_type>(capacity));
+  rep->tag = RING;
+  rep->capacity_ = static_cast<index_type>(capacity);
+  rep->begin_pos_ = 0;
+  return rep;
+}
+
+void CordRepRing::SetCapacityForTesting(size_t capacity) {
+  // Adjust for the changed layout
+  assert(capacity <= capacity_);
+  assert(head() == 0 || head() < tail());
+  memmove(Layout::Partial(capacity).Pointer<1>(data_) + head(),
+          Layout::Partial(capacity_).Pointer<1>(data_) + head(),
+          entries() * sizeof(Layout::ElementType<1>));
+  memmove(Layout::Partial(capacity, capacity).Pointer<2>(data_) + head(),
+          Layout::Partial(capacity_, capacity_).Pointer<2>(data_) + head(),
+          entries() * sizeof(Layout::ElementType<2>));
+  capacity_ = static_cast<index_type>(capacity);
+}
+
+void CordRepRing::Delete(CordRepRing* rep) {
+  assert(rep != nullptr && rep->tag == RING);
+#if defined(__cpp_sized_deallocation)
+  size_t size = AllocSize(rep->capacity_);
+  rep->~CordRepRing();
+  ::operator delete(rep, size);
+#else
+  rep->~CordRepRing();
+  ::operator delete(rep);
+#endif
+}
+
+void CordRepRing::Destroy(CordRepRing* rep) {
+  UnrefEntries(rep, rep->head(), rep->tail());
+  Delete(rep);
+}
+
+template <bool ref>
+void CordRepRing::Fill(const CordRepRing* src, index_type head,
+                       index_type tail) {
+  this->length = src->length;
+  head_ = 0;
+  tail_ = advance(0, src->entries(head, tail));
+  begin_pos_ = src->begin_pos_;
+
+  // TODO(mvels): there may be opportunities here for large buffers.
+  auto* dst_pos = entry_end_pos();
+  auto* dst_child = entry_child();
+  auto* dst_offset = entry_data_offset();
+  src->ForEach(head, tail, [&](index_type index) {
+    *dst_pos++ = src->entry_end_pos(index);
+    CordRep* child = src->entry_child(index);
+    *dst_child++ = ref ? CordRep::Ref(child) : child;
+    *dst_offset++ = src->entry_data_offset(index);
+  });
+}
+
+CordRepRing* CordRepRing::Copy(CordRepRing* rep, index_type head,
+                               index_type tail, size_t extra) {
+  CordRepRing* newrep = CordRepRing::New(rep->entries(head, tail), extra);
+  newrep->Fill<true>(rep, head, tail);
+  CordRep::Unref(rep);
+  return newrep;
+}
+
+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);
+  } else if (entries + extra > rep->capacity()) {
+    CordRepRing* newrep = CordRepRing::New(entries, min_extra);
+    newrep->Fill<false>(rep, rep->head(), rep->tail());
+    CordRepRing::Delete(rep);
+    return newrep;
+  } else {
+    return rep;
+  }
+}
+
+Span<char> CordRepRing::GetAppendBuffer(size_t size) {
+  assert(refcount.IsOne());
+  index_type back = retreat(tail_);
+  CordRep* child = entry_child(back);
+  if (child->tag >= FLAT && child->refcount.IsOne()) {
+    size_t capacity = child->flat()->Capacity();
+    pos_type end_pos = entry_end_pos(back);
+    size_t data_offset = entry_data_offset(back);
+    size_t entry_length = Distance(entry_begin_pos(back), end_pos);
+    size_t used = data_offset + entry_length;
+    if (size_t n = (std::min)(capacity - used, size)) {
+      child->length = data_offset + entry_length + n;
+      entry_end_pos()[back] = end_pos + n;
+      this->length += n;
+      return {child->flat()->Data() + used, n};
+    }
+  }
+  return {nullptr, 0};
+}
+
+Span<char> CordRepRing::GetPrependBuffer(size_t size) {
+  assert(refcount.IsOne());
+  CordRep* child = entry_child(head_);
+  size_t data_offset = entry_data_offset(head_);
+  if (data_offset && child->refcount.IsOne() && child->tag >= FLAT) {
+    size_t n = (std::min)(data_offset, size);
+    this->length += n;
+    begin_pos_ -= n;
+    data_offset -= n;
+    entry_data_offset()[head_] = static_cast<offset_type>(data_offset);
+    return {child->flat()->Data() + data_offset, n};
+  }
+  return {nullptr, 0};
+}
+
+CordRepRing* CordRepRing::CreateFromLeaf(CordRep* child, size_t offset,
+                                         size_t length, 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->entry_child()[0] = child;
+  rep->entry_data_offset()[0] = static_cast<offset_type>(offset);
+  return Validate(rep);
+}
+
+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);
+    } else if (rep) {
+      rep = AddRing<AddMode::kAppend>(rep, child->ring(), offset, length);
+    } else if (offset == 0 && child->length == length) {
+      rep = Mutable(child->ring(), extra);
+    } else {
+      rep = SubRing(child->ring(), offset, length, extra);
+    }
+  });
+  return Validate(rep, nullptr, __LINE__);
+}
+
+CordRepRing* CordRepRing::Create(CordRep* child, size_t extra) {
+  size_t length = child->length;
+  if (IsFlatOrExternal(child)) {
+    return CreateFromLeaf(child, 0, length, extra);
+  }
+  if (child->tag == RING) {
+    return Mutable(child->ring(), extra);
+  }
+  return CreateSlow(child, extra);
+}
+
+template <CordRepRing::AddMode mode>
+CordRepRing* CordRepRing::AddRing(CordRepRing* rep, CordRepRing* ring,
+                                  size_t offset, size_t length) {
+  assert(offset < ring->length);
+  constexpr bool append = mode == AddMode::kAppend;
+  Position head = ring->Find(offset);
+  Position tail = ring->FindTail(head.index, offset + length);
+  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) -
+      ring->entry_begin_pos(head.index) - head.offset;
+
+  // Start filling at `tail`, or `entries` before `head`
+  Filler filler(rep, append ? rep->tail_ : rep->retreat(rep->head_, entries));
+
+  if (ring->refcount.IsOne()) {
+    // Copy entries from source stealing the ref and adjusting the end position.
+    // Commit the filler as this is no-op.
+    ring->ForEach(head.index, tail.index, [&](index_type ix) {
+      filler.Add(ring->entry_child(ix), ring->entry_data_offset(ix),
+                 ring->entry_end_pos(ix) + delta_length);
+    });
+
+    // Unref entries we did not copy over, and delete source.
+    if (head.index != ring->head_) UnrefEntries(ring, ring->head_, head.index);
+    if (tail.index != ring->tail_) UnrefEntries(ring, tail.index, ring->tail_);
+    CordRepRing::Delete(ring);
+  } else {
+    ring->ForEach(head.index, tail.index, [&](index_type ix) {
+      CordRep* child = ring->entry_child(ix);
+      filler.Add(child, ring->entry_data_offset(ix),
+                 ring->entry_end_pos(ix) + delta_length);
+      CordRep::Ref(child);
+    });
+    CordRepRing::Unref(ring);
+  }
+
+  if (head.offset) {
+    // Increase offset of first 'source' entry appended or prepended.
+    // This is always the entry in `filler.head()`
+    rep->AddDataOffset(filler.head(), head.offset);
+  }
+
+  if (tail.offset) {
+    // Reduce length of last 'source' entry appended or prepended.
+    // This is always the entry tailed by `filler.pos()`
+    rep->SubLength(rep->retreat(filler.pos()), tail.offset);
+  }
+
+  // Commit changes
+  rep->length += length;
+  if (append) {
+    rep->tail_ = filler.pos();
+  } else {
+    rep->head_ = filler.head();
+    rep->begin_pos_ -= length;
+  }
+
+  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);
+    } else {
+      rep = AppendLeaf(rep, child, offset, length);
+    }
+  });
+  return rep;
+}
+
+CordRepRing* CordRepRing::AppendLeaf(CordRepRing* rep, CordRep* child,
+                                     size_t offset, size_t length) {
+  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->entry_child()[back] = child;
+  rep->entry_data_offset()[back] = static_cast<offset_type>(offset);
+  return Validate(rep, nullptr, __LINE__);
+}
+
+CordRepRing* CordRepRing::Append(CordRepRing* rep, CordRep* child) {
+  size_t length = child->length;
+  if (IsFlatOrExternal(child)) {
+    return AppendLeaf(rep, child, 0, length);
+  }
+  if (child->tag == RING) {
+    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);
+    } else {
+      rep = AddRing<AddMode::kPrepend>(rep, child->ring(), offset, length);
+    }
+  });
+  return Validate(rep);
+}
+
+CordRepRing* CordRepRing::PrependLeaf(CordRepRing* rep, CordRep* child,
+                                      size_t offset, size_t length) {
+  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->entry_end_pos()[head] = end_pos;
+  rep->entry_child()[head] = child;
+  rep->entry_data_offset()[head] = static_cast<offset_type>(offset);
+  return Validate(rep);
+}
+
+CordRepRing* CordRepRing::Prepend(CordRepRing* rep, CordRep* child) {
+  size_t length = child->length;
+  if (IsFlatOrExternal(child)) {
+    return PrependLeaf(rep, child, 0, length);
+  }
+  if (child->tag == RING) {
+    return AddRing<AddMode::kPrepend>(rep, child->ring(), 0, length);
+  }
+  return PrependSlow(rep, child);
+}
+
+CordRepRing* CordRepRing::Append(CordRepRing* rep, absl::string_view data,
+                                 size_t extra) {
+  if (rep->refcount.IsOne()) {
+    Span<char> avail = rep->GetAppendBuffer(data.length());
+    if (!avail.empty()) {
+      memcpy(avail.data(), data.data(), avail.length());
+      data.remove_prefix(avail.length());
+    }
+  }
+  if (data.empty()) return Validate(rep);
+
+  const size_t flats = (data.length() - 1) / kMaxFlatLength + 1;
+  rep = Mutable(rep, flats);
+
+  Filler filler(rep, rep->tail_);
+  pos_type pos = rep->begin_pos_ + rep->length;
+
+  while (data.length() >= kMaxFlatLength) {
+    auto* flat = CreateFlat(data.data(), kMaxFlatLength);
+    filler.Add(flat, 0, pos += kMaxFlatLength);
+    data.remove_prefix(kMaxFlatLength);
+  }
+
+  if (data.length()) {
+    auto* flat = CreateFlat(data.data(), data.length(), extra);
+    filler.Add(flat, 0, pos += data.length());
+  }
+
+  rep->length = pos - rep->begin_pos_;
+  rep->tail_ = filler.pos();
+
+  return Validate(rep);
+}
+
+CordRepRing* CordRepRing::Prepend(CordRepRing* rep, absl::string_view data,
+                                  size_t extra) {
+  if (rep->refcount.IsOne()) {
+    Span<char> avail = rep->GetPrependBuffer(data.length());
+    if (!avail.empty()) {
+      const char* tail = data.data() + data.length() - avail.length();
+      memcpy(avail.data(), tail, avail.length());
+      data.remove_suffix(avail.length());
+    }
+  }
+  if (data.empty()) return rep;
+
+  const size_t flats = (data.length() - 1) / kMaxFlatLength + 1;
+  rep = Mutable(rep, flats);
+  pos_type pos = rep->begin_pos_;
+  Filler filler(rep, rep->retreat(rep->head_, static_cast<index_type>(flats)));
+
+  size_t first_size = data.size() - (flats - 1) * kMaxFlatLength;
+  CordRepFlat* flat = CordRepFlat::New(first_size + extra);
+  flat->length = first_size + extra;
+  memcpy(flat->Data() + extra, data.data(), first_size);
+  data.remove_prefix(first_size);
+  filler.Add(flat, extra, pos);
+  pos -= first_size;
+
+  while (!data.empty()) {
+    assert(data.size() >= kMaxFlatLength);
+    flat = CreateFlat(data.data(), kMaxFlatLength);
+    filler.Add(flat, 0, pos);
+    pos -= kMaxFlatLength;
+    data.remove_prefix(kMaxFlatLength);
+  }
+
+  rep->head_ = filler.head();
+  rep->length += rep->begin_pos_ - pos;
+  rep->begin_pos_ = pos;
+
+  return Validate(rep);
+}
+
+// 32 entries is 32 * sizeof(pos_type) = 4 cache lines on x86
+static constexpr index_type kBinarySearchThreshold = 32;
+static constexpr index_type kBinarySearchEndCount = 8;
+
+template <bool wrap>
+CordRepRing::index_type CordRepRing::FindBinary(index_type head,
+                                                index_type tail,
+                                                size_t offset) const {
+  index_type count = tail + (wrap ? capacity_ : 0) - head;
+  do {
+    count = (count - 1) / 2;
+    assert(count < entries(head, tail_));
+    index_type mid = wrap ? advance(head, count) : head + count;
+    index_type after_mid = wrap ? advance(mid) : mid + 1;
+    bool larger = (offset >= entry_end_offset(mid));
+    head = larger ? after_mid : head;
+    tail = larger ? tail : mid;
+    assert(head != tail);
+  } while (ABSL_PREDICT_TRUE(count > kBinarySearchEndCount));
+  return head;
+}
+
+CordRepRing::Position CordRepRing::FindSlow(index_type head,
+                                            size_t offset) const {
+  index_type tail = tail_;
+
+  // Binary search until we are good for linear search
+  // Optimize for branchless / non wrapping ops
+  if (tail > head) {
+    index_type count = tail - head;
+    if (count > kBinarySearchThreshold) {
+      head = FindBinary<false>(head, tail, offset);
+    }
+  } else {
+    index_type count = capacity_ + tail - head;
+    if (count > kBinarySearchThreshold) {
+      head = FindBinary<true>(head, tail, offset);
+    }
+  }
+
+  pos_type pos = entry_begin_pos(head);
+  pos_type end_pos = entry_end_pos(head);
+  while (offset >= Distance(begin_pos_, end_pos)) {
+    head = advance(head);
+    pos = end_pos;
+    end_pos = entry_end_pos(head);
+  }
+
+  return {head, offset - Distance(begin_pos_, pos)};
+}
+
+CordRepRing::Position CordRepRing::FindTailSlow(index_type head,
+                                                size_t offset) const {
+  index_type tail = tail_;
+  const size_t tail_offset = offset - 1;
+
+  // Binary search until we are good for linear search
+  // Optimize for branchless / non wrapping ops
+  if (tail > head) {
+    index_type count = tail - head;
+    if (count > kBinarySearchThreshold) {
+      head = FindBinary<false>(head, tail, tail_offset);
+    }
+  } else {
+    index_type count = capacity_ + tail - head;
+    if (count > kBinarySearchThreshold) {
+      head = FindBinary<true>(head, tail, tail_offset);
+    }
+  }
+
+  size_t end_offset = entry_end_offset(head);
+  while (tail_offset >= end_offset) {
+    head = advance(head);
+    end_offset = entry_end_offset(head);
+  }
+
+  return {advance(head), end_offset - offset};
+}
+
+char CordRepRing::GetCharacter(size_t offset) const {
+  assert(offset < length);
+
+  Position pos = Find(offset);
+  size_t data_offset = entry_data_offset(pos.index) + pos.offset;
+  return GetRepData(entry_child(pos.index))[data_offset];
+}
+
+CordRepRing* CordRepRing::SubRing(CordRepRing* rep, size_t offset,
+                                  size_t length, size_t extra) {
+  assert(offset <= rep->length);
+  assert(offset <= rep->length - length);
+
+  if (length == 0) {
+    CordRep::Unref(rep);
+    return nullptr;
+  }
+
+  // Find position of first byte
+  Position head = rep->Find(offset);
+  Position tail = rep->FindTail(head.index, offset + length);
+  const size_t new_entries = rep->entries(head.index, tail.index);
+
+  if (rep->refcount.IsOne() && extra <= (rep->capacity() - new_entries)) {
+    // We adopt a privately owned rep and no extra entries needed.
+    if (head.index != rep->head_) UnrefEntries(rep, rep->head_, head.index);
+    if (tail.index != rep->tail_) UnrefEntries(rep, tail.index, rep->tail_);
+    rep->head_ = head.index;
+    rep->tail_ = tail.index;
+  } else {
+    // Copy subset to new rep
+    rep = Copy(rep, head.index, tail.index, extra);
+    head.index = rep->head_;
+    tail.index = rep->tail_;
+  }
+
+  // Adjust begin_pos and length
+  rep->length = length;
+  rep->begin_pos_ += offset;
+
+  // Adjust head and tail blocks
+  if (head.offset) {
+    rep->AddDataOffset(head.index, head.offset);
+  }
+  if (tail.offset) {
+    rep->SubLength(rep->retreat(tail.index), tail.offset);
+  }
+
+  return Validate(rep);
+}
+
+CordRepRing* CordRepRing::RemovePrefix(CordRepRing* rep, size_t len,
+                                       size_t extra) {
+  assert(len <= rep->length);
+  if (len == rep->length) {
+    CordRep::Unref(rep);
+    return nullptr;
+  }
+
+  Position head = rep->Find(len);
+  if (rep->refcount.IsOne()) {
+    if (head.index != rep->head_) UnrefEntries(rep, rep->head_, head.index);
+    rep->head_ = head.index;
+  } else {
+    rep = Copy(rep, head.index, rep->tail_, extra);
+    head.index = rep->head_;
+  }
+
+  // Adjust begin_pos and length
+  rep->length -= len;
+  rep->begin_pos_ += len;
+
+  // Adjust head block
+  if (head.offset) {
+    rep->AddDataOffset(head.index, head.offset);
+  }
+
+  return Validate(rep);
+}
+
+CordRepRing* CordRepRing::RemoveSuffix(CordRepRing* rep, size_t len,
+                                       size_t extra) {
+  assert(len <= rep->length);
+
+  if (len == rep->length) {
+    CordRep::Unref(rep);
+    return nullptr;
+  }
+
+  Position tail = rep->FindTail(rep->length - len);
+  if (rep->refcount.IsOne()) {
+    // We adopt a privately owned rep, scrub.
+    if (tail.index != rep->tail_) UnrefEntries(rep, tail.index, rep->tail_);
+    rep->tail_ = tail.index;
+  } else {
+    // Copy subset to new rep
+    rep = Copy(rep, rep->head_, tail.index, extra);
+    tail.index = rep->tail_;
+  }
+
+  // Adjust length
+  rep->length -= len;
+
+  // Adjust tail block
+  if (tail.offset) {
+    rep->SubLength(rep->retreat(tail.index), tail.offset);
+  }
+
+  return Validate(rep);
+}
+
+#ifdef __clang__
+#pragma clang diagnostic pop
+#endif
+
+}  // namespace cord_internal
+ABSL_NAMESPACE_END
+}  // namespace absl
diff --git a/absl/strings/internal/cord_rep_ring.h b/absl/strings/internal/cord_rep_ring.h
new file mode 100644
index 00000000..e6f6b59c
--- /dev/null
+++ b/absl/strings/internal/cord_rep_ring.h
@@ -0,0 +1,576 @@
+// Copyright 2020 The Abseil Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// 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.
+
+#ifndef ABSL_STRINGS_INTERNAL_CORD_REP_RING_H_
+#define ABSL_STRINGS_INTERNAL_CORD_REP_RING_H_
+
+#include <cassert>
+#include <cstddef>
+#include <cstdint>
+#include <iosfwd>
+#include <limits>
+#include <memory>
+
+#include "absl/container/internal/layout.h"
+#include "absl/strings/internal/cord_internal.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"
+#pragma clang diagnostic ignored "-Wshadow-field"
+#endif
+
+// All operations modifying a ring buffer are implemented as static methods
+// requiring a CordRepRing instance with a reference adopted by the method.
+//
+// The methods return the modified ring buffer, which may be equal to the input
+// if the input was not shared, and having large enough capacity to accommodate
+// any newly added node(s). Otherwise, a copy of the input rep with the new
+// node(s) added is returned.
+//
+// Any modification on non shared ring buffers with enough capacity will then
+// require minimum atomic operations. Caller should where possible provide
+// reasonable `extra` hints for both anticipated extra `flat` byte space, as
+// well as anticipated extra nodes required for complex operations.
+//
+// Example of code creating a ring buffer, adding some data to it,
+// and discarding the buffer when done:
+//
+//   void FunWithRings() {
+//     // Create ring with 3 flats
+//     CordRep* flat = CreateFlat("Hello");
+//     CordRepRing* ring = CordRepRing::Create(flat, 2);
+//     ring = CordRepRing::Append(ring, CreateFlat(" "));
+//     ring = CordRepRing::Append(ring, CreateFlat("world"));
+//     DoSomethingWithRing(ring);
+//     CordRep::Unref(ring);
+//   }
+//
+// Example of code Copying an existing ring buffer and modifying it:
+//
+//   void MoreFunWithRings(CordRepRing* src) {
+//     CordRepRing* ring = CordRep::Ref(src)->ring();
+//     ring = CordRepRing::Append(ring, CreateFlat("Hello"));
+//     ring = CordRepRing::Append(ring, CreateFlat(" "));
+//     ring = CordRepRing::Append(ring, CreateFlat("world"));
+//     DoSomethingWithRing(ring);
+//     CordRep::Unref(ring);
+//   }
+//
+class CordRepRing : public CordRep {
+ public:
+  // `pos_type` represents a 'logical position'. A CordRepRing instance has a
+  // `begin_pos` (default 0), and each node inside the buffer will have an
+  // `end_pos` which is the `end_pos` of the previous node (or `begin_pos`) plus
+  // this node's length. The purpose is to allow for a binary search on this
+  // position, while allowing O(1) prepend and append operations.
+  using pos_type = uint64_t;
+
+  // `index_type` is the type for the `head`, `tail` and `capacity` indexes.
+  // Ring buffers are limited to having no more than four billion entries.
+  using index_type = uint32_t;
+
+  // `offset_type` is the type for the data offset inside a child rep's data.
+  using offset_type = uint32_t;
+
+  // Position holds the node index and relative offset into the node for
+  // some physical offset in the contained data as returned by the Find()
+  // and FindTail() methods.
+  struct Position {
+    index_type index;
+    size_t offset;
+  };
+
+  // The maximum # of child nodes that can be hosted inside a CordRepRing.
+  static constexpr size_t kMaxCapacity = (std::numeric_limits<uint32_t>::max)();
+
+  // CordRepring can not be default constructed, moved, copied or assigned.
+  CordRepRing() = delete;
+  CordRepRing(const CordRepRing&) = delete;
+  CordRepRing& operator=(const CordRepRing&) = delete;
+
+  // Returns true if this instance is valid, false if some or all of the
+  // invariants are broken. Intended for debug purposes only.
+  // `output` receives an explanation of the broken invariants.
+  bool IsValid(std::ostream& output) const;
+
+  // Returns the size in bytes for a CordRepRing with `capacity' entries.
+  static constexpr size_t AllocSize(size_t capacity);
+
+  // Returns the distance in bytes from `pos` to `end_pos`.
+  static constexpr size_t Distance(pos_type pos, pos_type end_pos);
+
+  // Creates a new ring buffer from the provided `rep`. Adopts a reference
+  // on `rep`. The returned ring buffer has a capacity of at least `extra + 1`
+  static CordRepRing* Create(CordRep* child, size_t extra = 0);
+
+  // `head`, `tail` and `capacity` indexes defining the ring buffer boundaries.
+  index_type head() const { return head_; }
+  index_type tail() const { return tail_; }
+  index_type capacity() const { return capacity_; }
+
+  // Returns the number of entries in this instance.
+  index_type entries() const { return entries(head_, tail_); }
+
+  // Returns the logical begin position of this instance.
+  pos_type begin_pos() const { return begin_pos_; }
+
+  // Returns the number of entries for a given head-tail range.
+  // Requires `head` and `tail` values to be less than `capacity()`.
+  index_type entries(index_type head, index_type tail) const {
+    assert(head < capacity_ && tail < capacity_);
+    return tail - head + ((tail > head) ? 0 : capacity_);
+  }
+
+  // Returns the logical end position of entry `index`.
+  pos_type const& entry_end_pos(index_type index) const {
+    assert(IsValidIndex(index));
+    return Layout::Partial().Pointer<0>(data_)[index];
+  }
+
+  // Returns the child pointer of entry `index`.
+  CordRep* const& entry_child(index_type index) const {
+    assert(IsValidIndex(index));
+    return Layout::Partial(capacity()).Pointer<1>(data_)[index];
+  }
+
+  // Returns the data offset of entry `index`
+  offset_type const& entry_data_offset(index_type index) const {
+    assert(IsValidIndex(index));
+    return Layout::Partial(capacity(), capacity()).Pointer<2>(data_)[index];
+  }
+
+  // Appends the provided child node to the `rep` instance.
+  // Adopts a reference from `rep` and `child` which may not be null.
+  // If the provided child is a FLAT or EXTERNAL node, or a SUBSTRING node
+  // containing a FLAT or EXTERNAL node, then flat or external the node is added
+  // 'as is', with an offset added for the SUBSTRING case.
+  // If the provided child is a RING or CONCAT tree, or a SUBSTRING of a RING or
+  // CONCAT tree, then all child nodes not excluded by any start offset or
+  // length values are added recursively.
+  static CordRepRing* Append(CordRepRing* rep, CordRep* child);
+
+  // Appends the provided string data to the `rep` instance.
+  // This function will attempt to utilize any remaining capacity in the last
+  // node of the input if that node is not shared (directly or indirectly), and
+  // of type FLAT. Remaining data will be added as one or more FLAT nodes.
+  // Any last node added to the ring buffer will be allocated with up to
+  // `extra` bytes of capacity for (anticipated) subsequent append actions.
+  static CordRepRing* Append(CordRepRing* rep, string_view data,
+                             size_t extra = 0);
+
+  // Prepends the provided child node to the `rep` instance.
+  // Adopts a reference from `rep` and `child` which may not be null.
+  // If the provided child is a FLAT or EXTERNAL node, or a SUBSTRING node
+  // containing a FLAT or EXTERNAL node, then flat or external the node is
+  // prepended 'as is', with an optional offset added for the SUBSTRING case.
+  // If the provided child is a RING or CONCAT tree, or a SUBSTRING of a RING
+  // or CONCAT tree, then all child nodes not excluded by any start offset or
+  // length values are added recursively.
+  static CordRepRing* Prepend(CordRepRing* rep, CordRep* child);
+
+  // Prepends the provided string data to the `rep` instance.
+  // This function will attempt to utilize any remaining capacity in the first
+  // node of the input if that node is not shared (directly or indirectly), and
+  // of type FLAT. Remaining data will be added as one or more FLAT nodes.
+  // Any first node prepnded to the ring buffer will be allocated with up to
+  // `extra` bytes of capacity for (anticipated) subsequent prepend actions.
+  static CordRepRing* Prepend(CordRepRing* rep, string_view data,
+                              size_t extra = 0);
+
+  // Returns a span referencing potentially unused capacity in the last node.
+  // The returned span may be empty if no such capacity is available, or if the
+  // current instance is shared. Else, a span of size `n <= size` is returned.
+  // If non empty, the ring buffer is adjusted to the new length, with the newly
+  // added capacity left uninitialized. Callers should assign a value to the
+  // entire span before any other operations on this instance.
+  Span<char> GetAppendBuffer(size_t size);
+
+  // Returns a span referencing potentially unused capacity in the first node.
+  // This function is identical to GetAppendBuffer except that it returns a span
+  // referencing up to `size` capacity directly before the existing data.
+  Span<char> GetPrependBuffer(size_t size);
+
+  // Returns a cord ring buffer containing `length` bytes of data starting at
+  // `offset`. If the input is not shared, this function will remove all head
+  // and tail child nodes outside of the requested range, and adjust the new
+  // head and tail nodes as required. If the input is shared, this function
+  // returns a new instance sharing some or all of the nodes from the input.
+  static CordRepRing* SubRing(CordRepRing* r, size_t offset, size_t length,
+                              size_t extra = 0);
+
+  // Returns a cord ring buffer with the first `length` bytes removed.
+  // If the input is not shared, this function will remove all head child nodes
+  // fully inside the first `length` bytes, and adjust the new head as required.
+  // If the input is shared, this function returns a new instance sharing some
+  // or all of the nodes from the input.
+  static CordRepRing* RemoveSuffix(CordRepRing* r, size_t length,
+                                   size_t extra = 0);
+
+  // Returns a cord ring buffer with the last `length` bytes removed.
+  // If the input is not shared, this function will remove all head child nodes
+  // fully inside the first `length` bytes, and adjust the new head as required.
+  // If the input is shared, this function returns a new instance sharing some
+  // or all of the nodes from the input.
+  static CordRepRing* RemovePrefix(CordRepRing* r, size_t len,
+                                   size_t extra = 0);
+
+  // Returns the character at `offset`. Requires that `offset < length`.
+  char GetCharacter(size_t offset) const;
+
+  // Testing only: set capacity to requested capacity.
+  void SetCapacityForTesting(size_t capacity);
+
+  // Returns the CordRep data pointer for the provided CordRep.
+  // Requires that the provided `rep` is either a FLAT or EXTERNAL CordRep.
+  static const char* GetLeafData(const CordRep* rep);
+
+  // Returns the CordRep data pointer for the provided CordRep.
+  // Requires that `rep` is either a FLAT, EXTERNAL, or SUBSTRING CordRep.
+  static const char* GetRepData(const CordRep* rep);
+
+  // Advances the provided position, wrapping around capacity as needed.
+  // Requires `index` < capacity()
+  inline index_type advance(index_type index) const;
+
+  // Advances the provided position by 'n`, wrapping around capacity as needed.
+  // Requires `index` < capacity() and `n` <= capacity.
+  inline index_type advance(index_type index, index_type n) const;
+
+  // Retreats the provided position, wrapping around 0 as needed.
+  // Requires `index` < capacity()
+  inline index_type retreat(index_type index) const;
+
+  // Retreats the provided position by 'n', wrapping around 0 as needed.
+  // Requires `index` < capacity()
+  inline index_type retreat(index_type index, index_type n) const;
+
+  // Returns the logical begin position of entry `index`
+  pos_type const& entry_begin_pos(index_type index) const {
+    return (index == head_) ? begin_pos_ : entry_end_pos(retreat(index));
+  }
+
+  // Returns the physical start offset of entry `index`
+  size_t entry_start_offset(index_type index) const {
+    return Distance(begin_pos_, entry_begin_pos(index));
+  }
+
+  // Returns the physical end offset of entry `index`
+  size_t entry_end_offset(index_type index) const {
+    return Distance(begin_pos_, entry_end_pos(index));
+  }
+
+  // Returns the data length for entry `index`
+  size_t entry_length(index_type index) const {
+    return Distance(entry_begin_pos(index), entry_end_pos(index));
+  }
+
+  // Returns the data for entry `index`
+  absl::string_view entry_data(index_type index) const;
+
+  // Returns the position for `offset` as {index, prefix}. `index` holds the
+  // index of the entry at the specified offset and `prefix` holds the relative
+  // offset inside that entry.
+  // Requires `offset` < length.
+  //
+  // For example we can implement GetCharacter(offset) as:
+  //   char GetCharacter(size_t offset) {
+  //     Position pos = this->Find(offset);
+  //     return this->entry_data(pos.pos)[pos.offset];
+  //   }
+  inline Position Find(size_t offset) const;
+
+  // Find starting at `head`
+  inline Position Find(index_type head, size_t offset) const;
+
+  // Returns the tail position for `offset` as {tail index, suffix}.
+  // `tail index` holds holds the index of the entry holding the offset directly
+  // before 'offset` advanced by one. 'suffix` holds the relative offset from
+  // that relative offset in the entry to the end of the entry.
+  // For example, FindTail(length) will return {tail(), 0}, FindTail(length - 5)
+  // will return {retreat(tail), 5)} provided the preceding entry contains at
+  // least 5 bytes of data.
+  // Requires offset >= 1 && offset <= length.
+  //
+  // This function is very useful in functions that need to clip the end of some
+  // ring buffer such as 'RemovePrefix'.
+  // For example, we could implement RemovePrefix for non shared instances as:
+  //   void RemoveSuffix(size_t n) {
+  //     Position pos = FindTail(length - n);
+  //     UnrefEntries(pos.pos, this->tail_);
+  //     this->tail_ = pos.pos;
+  //     entry(retreat(pos.pos)).end_pos -= pos.offset;
+  //   }
+  inline Position FindTail(size_t offset) const;
+
+  // Find tail starting at `head`
+  inline Position FindTail(index_type head, size_t offset) const;
+
+  // Invokes f(index_type index) for each entry inside the range [head, tail>
+  template <typename F>
+  void ForEach(index_type head, index_type tail, F&& f) const {
+    index_type n1 = (tail > head) ? tail : capacity_;
+    for (index_type i = head; i < n1; ++i) f(i);
+    if (tail <= head) {
+      for (index_type i = 0; i < tail; ++i) f(i);
+    }
+  }
+
+  // Invokes f(index_type index) for each entry inside this instance.
+  template <typename F>
+  void ForEach(F&& f) const {
+    ForEach(head_, tail_, std::forward<F>(f));
+  }
+
+  // Dump this instance's data tp stream `s` in human readable format, excluding
+  // the actual data content itself. Intended for debug purposes only.
+  friend std::ostream& operator<<(std::ostream& s, const CordRepRing& rep);
+
+ private:
+  enum class AddMode { kAppend, kPrepend };
+
+  using Layout = container_internal::Layout<pos_type, CordRep*, offset_type>;
+
+  class Filler;
+  class Transaction;
+  class CreateTransaction;
+
+  static constexpr size_t kLayoutAlignment = Layout::Partial().Alignment();
+
+  // Creates a new CordRepRing.
+  explicit CordRepRing(index_type capacity) : capacity_(capacity) {}
+
+  // Returns true if `index` is a valid index into this instance.
+  bool IsValidIndex(index_type index) const;
+
+  // Debug use only: validates the provided CordRepRing invariants.
+  // Verification of all CordRepRing methods can be enabled by defining
+  // EXTRA_CORD_RING_VALIDATION, i.e.: `--copts=-DEXTRA_CORD_RING_VALIDATION`
+  // Verification is VERY expensive, so only do it for debugging purposes.
+  static CordRepRing* Validate(CordRepRing* rep, const char* file = nullptr,
+                               int line = 0);
+
+  // Allocates a CordRepRing large enough to hold `capacity + extra' entries.
+  // The returned capacity may be larger if the allocated memory allows for it.
+  // The maximum capacity of a CordRepRing is capped at kMaxCapacity.
+  // Throws `std::length_error` if `capacity + extra' exceeds kMaxCapacity.
+  static CordRepRing* New(size_t capacity, size_t extra);
+
+  // Deallocates (but does not destroy) the provided ring buffer.
+  static void Delete(CordRepRing* rep);
+
+  // Destroys the provided ring buffer, decrementing the reference count of all
+  // contained child CordReps. The provided 1\`rep` should have a ref count of
+  // one (pre decrement destroy call observing `refcount.IsOne()`) or zero (post
+  // decrement destroy call observing `!refcount.Decrement()`).
+  static void Destroy(CordRepRing* rep);
+
+  // Returns a mutable reference to the logical end position array.
+  pos_type* entry_end_pos() {
+    return Layout::Partial().Pointer<0>(data_);
+  }
+
+  // Returns a mutable reference to the child pointer array.
+  CordRep** entry_child() {
+    return Layout::Partial(capacity()).Pointer<1>(data_);
+  }
+
+  // Returns a mutable reference to the data offset array.
+  offset_type* entry_data_offset() {
+    return Layout::Partial(capacity(), capacity()).Pointer<2>(data_);
+  }
+
+  // Find implementations for the non fast path 0 / length cases.
+  Position FindSlow(index_type head, size_t offset) const;
+  Position FindTailSlow(index_type head, size_t offset) const;
+
+  // Finds the index of the first node that is inside a reasonable distance
+  // of the node at `offset` from which we can continue with a linear search.
+  template <bool wrap>
+  index_type FindBinary(index_type head, index_type tail, size_t offset) const;
+
+  // Fills the current (initialized) instance from the provided source, copying
+  // entries [head, tail). Adds a reference to copied entries if `ref` is true.
+  template <bool ref>
+  void Fill(const CordRepRing* src, index_type head, index_type tail);
+
+  // Create a copy of 'rep', copying all entries [head, tail), allocating room
+  // for `extra` entries. Adds a reference on all copied entries.
+  static CordRepRing* Copy(CordRepRing* rep, index_type head, index_type tail,
+                           size_t extra = 0);
+
+  // Returns a Mutable CordRepRing reference from `rep` with room for at least
+  // `extra` additional nodes. Adopts a reference count from `rep`.
+  // This function will return `rep` if, and only if:
+  // - rep.entries + extra <= rep.capacity
+  // - rep.refcount == 1
+  // Otherwise, this function will create a new copy of `rep` with additional
+  // capacity to satisfy `extra` extra nodes, and unref the old `rep` instance.
+  //
+  // If a new CordRepRing can not be allocated, or the new capacity would exceed
+  // the maxmimum capacity, then the input is consumed only, and an exception is
+  // thrown.
+  static CordRepRing* Mutable(CordRepRing* rep, size_t extra);
+
+  // Slow path for Append(CordRepRing* rep, CordRep* child). This function is
+  // exercised if the provided `child` in Append() is not a leaf node, i.e., a
+  // ring buffer or old (concat) cord tree.
+  static CordRepRing* AppendSlow(CordRepRing* rep, CordRep* child);
+
+  // Appends the provided leaf node. Requires `child` to be FLAT or EXTERNAL.
+  static CordRepRing* AppendLeaf(CordRepRing* rep, CordRep* child,
+                                 size_t offset, size_t length);
+
+  // Prepends the provided leaf node. Requires `child` to be FLAT or EXTERNAL.
+  static CordRepRing* PrependLeaf(CordRepRing* rep, CordRep* child,
+                                  size_t offset, size_t length);
+
+  // Slow path for Prepend(CordRepRing* rep, CordRep* child). This function is
+  // exercised if the provided `child` in Prepend() is not a leaf node, i.e., a
+  // ring buffer or old (concat) cord tree.
+  static CordRepRing* PrependSlow(CordRepRing* rep, CordRep* child);
+
+  // Slow path for Create(CordRep* child, size_t extra). This function is
+  // exercised if the provided `child` in Prepend() is not a leaf node, i.e., a
+  // ring buffer or old (concat) cord tree.
+  static CordRepRing* CreateSlow(CordRep* child, size_t extra);
+
+  // Creates a new ring buffer from the provided `child` leaf node. Requires
+  // `child` to be FLAT or EXTERNAL. on `rep`.
+  // The returned ring buffer has a capacity of at least `1 + extra`
+  static CordRepRing* CreateFromLeaf(CordRep* child, size_t offset,
+                                     size_t length, size_t extra);
+
+  // Appends or prepends (depending on AddMode) the ring buffer in `ring' to
+  // `rep` starting at `offset` with length `length`.
+  template <AddMode mode>
+  static CordRepRing* AddRing(CordRepRing* rep, CordRepRing* ring,
+                              size_t offset, size_t length);
+
+  // Increases the data offset for entry `index` by `n`.
+  void AddDataOffset(index_type index, size_t n);
+
+  // Descreases the length for entry `index` by `n`.
+  void SubLength(index_type index, size_t n);
+
+  index_type head_;
+  index_type tail_;
+  index_type capacity_;
+  pos_type begin_pos_;
+
+  alignas(kLayoutAlignment) char data_[kLayoutAlignment];
+
+  friend struct CordRep;
+};
+
+constexpr size_t CordRepRing::AllocSize(size_t capacity) {
+  return sizeof(CordRepRing) - sizeof(data_) +
+         Layout(capacity, capacity, capacity).AllocSize();
+}
+
+inline constexpr size_t CordRepRing::Distance(pos_type pos, pos_type end_pos) {
+  return (end_pos - pos);
+}
+
+inline const char* CordRepRing::GetLeafData(const CordRep* rep) {
+  return rep->tag != EXTERNAL ? rep->flat()->Data() : rep->external()->base;
+}
+
+inline const char* CordRepRing::GetRepData(const CordRep* rep) {
+  if (rep->tag >= FLAT) return rep->flat()->Data();
+  if (rep->tag == EXTERNAL) return rep->external()->base;
+  return GetLeafData(rep->substring()->child) + rep->substring()->start;
+}
+
+inline CordRepRing::index_type CordRepRing::advance(index_type index) const {
+  assert(index < capacity_);
+  return ++index == capacity_ ? 0 : index;
+}
+
+inline CordRepRing::index_type CordRepRing::advance(index_type index,
+                                                    index_type n) const {
+  assert(index < capacity_ && n <= capacity_);
+  return (index += n) >= capacity_ ? index - capacity_ : index;
+}
+
+inline CordRepRing::index_type CordRepRing::retreat(index_type index) const {
+  assert(index < capacity_);
+  return (index > 0 ? index : capacity_) - 1;
+}
+
+inline CordRepRing::index_type CordRepRing::retreat(index_type index,
+                                                    index_type n) const {
+  assert(index < capacity_ && n <= capacity_);
+  return index >= n ? index - n : capacity_ - n + index;
+}
+
+inline absl::string_view CordRepRing::entry_data(index_type index) const {
+  size_t data_offset = entry_data_offset(index);
+  return {GetRepData(entry_child(index)) + data_offset, entry_length(index)};
+}
+
+inline bool CordRepRing::IsValidIndex(index_type index) const {
+  if (index >= capacity_) return false;
+  return (tail_ > head_) ? (index >= head_ && index < tail_)
+                         : (index >= head_ || index < tail_);
+}
+
+#ifndef EXTRA_CORD_RING_VALIDATION
+inline CordRepRing* CordRepRing::Validate(CordRepRing* rep,
+                                          const char* /*file*/, int /*line*/) {
+  return rep;
+}
+#endif
+
+inline CordRepRing::Position CordRepRing::Find(size_t offset) const {
+  assert(offset < length);
+  return (offset == 0) ? Position{head_, 0} : FindSlow(head_, offset);
+}
+
+inline CordRepRing::Position CordRepRing::Find(index_type head,
+                                               size_t offset) const {
+  assert(offset < length);
+  assert(IsValidIndex(head) && offset >= entry_start_offset(head));
+  return (offset == 0) ? Position{head_, 0} : FindSlow(head, offset);
+}
+
+inline CordRepRing::Position CordRepRing::FindTail(size_t offset) const {
+  assert(offset > 0 && offset <= length);
+  return (offset == length) ? Position{tail_, 0} : FindTailSlow(head_, offset);
+}
+
+inline CordRepRing::Position CordRepRing::FindTail(index_type head,
+                                                   size_t offset) const {
+  assert(offset > 0 && offset <= length);
+  assert(IsValidIndex(head) && offset >= entry_start_offset(head) + 1);
+  return (offset == length) ? Position{tail_, 0} : FindTailSlow(head, offset);
+}
+
+std::ostream& operator<<(std::ostream& s, const CordRepRing& rep);
+
+#ifdef __clang__
+#pragma clang diagnostic pop
+#endif
+
+}  // namespace cord_internal
+ABSL_NAMESPACE_END
+}  // namespace absl
+
+#endif  // ABSL_STRINGS_INTERNAL_CORD_REP_RING_H_