Export of internal Abseil changes

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

Remove division from the profile guided optimization

PiperOrigin-RevId: 428444108

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

Rename btree_node::leaf to is_leaf and also add is_internal for readability improvements.

PiperOrigin-RevId: 428076422

--
6a90d18477cc3a6de84282b6e38d6f294aa72748 by Evan Brown <ezb@google.com>:

In sanitizer mode, add generation integers to b-tree nodes and iterators and validate that iterators have not been invalidated already when they're used.

Even though generation integers are stored in all nodes, we only use the one stored in the root node for validation. The reason we keep one in all the nodes is that nodes can become a root node after they are allocated.

Also change the order of args in init_leaf to not violate the style guide.

PiperOrigin-RevId: 428054226

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

Physically remove CordRepConcat

This CL removes all uses of CordRepConcat. This change is executed by removing all the dead 'btree_enabled()' and 'IsConcat' branches, and all subsequent dead code. This change explicitly does not optimize any of the remaining code other than the most trivial ones such as removing 'stack' loop vars and loops.

PiperOrigin-RevId: 428002308

--
7cc83d96118149cf1aa1258a066b8fd4517df5f6 by Evan Brown <ezb@google.com>:

Change btree_iterator from a struct to a class.

Motivation: btree_iterator has private members and invariants so it should be a class.

Also merge two private sections.

PiperOrigin-RevId: 427768836

--
524d478b0af422e1a867a8823d9fbad149030360 by Martijn Vels <mvels@google.com>:

Physically block the creation of new CordRepConcat nodes.

This change removes CordRepConcat creation, issuing a FATAL errors on the (practically impossible) call path on broken invariants. This change is deliberately limited in impact, subsequent changes will be more voluminous ripping out the (now dead) CordRepConcat code.

PiperOrigin-RevId: 427741022

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

Update the implementation of ABSL_DEPRECATED to work with GCC, and
recommend using the standard attribute [[deprecated]] for C++14 and newer

GCC users that are experiencing new warnings can silence them with
-Wno-deprecated-declatations.

GCC users that want to see the warnings but not error on them can use
-Wno-error=deprecated-declarations.
PiperOrigin-RevId: 427228952

--
0ab4ee5660f3a072054dc4ab5056925c26977c7a by Laramie Leavitt <lar@google.com>:

Change comment to avoid overflow.

PiperOrigin-RevId: 427090218
GitOrigin-RevId: ceee18732f9499d3a53d46d5974f12ea0774b900
Change-Id: Ida00477b6a3d02a8b7bb467be7621b618385d1e9

20 files changed, 450 insertions, 968 deletions

diff --git a/absl/base/attributes.h b/absl/base/attributes.h
index 91aabffe..5721356d 100644
--- a/absl/base/attributes.h
+++ b/absl/base/attributes.h
@@ -646,6 +646,9 @@
 // declarations. The macro argument is used as a custom diagnostic message (e.g.
 // suggestion of a better alternative).
 //
+// For code or headers that are assured to only build with C++14 and up, prefer
+// just using the standard `[[deprecated("message")]]` directly over this macro.
+//
 // Examples:
 //
 //   class ABSL_DEPRECATED("Use Bar instead") Foo {...};
@@ -661,13 +664,12 @@
 //   };
 //
 // Every usage of a deprecated entity will trigger a warning when compiled with
-// clang's `-Wdeprecated-declarations` option. This option is turned off by
-// default, but the warnings will be reported by clang-tidy.
-#if defined(__clang__) && defined(__cplusplus) && __cplusplus >= 201103L
+// GCC/Clang's `-Wdeprecated-declarations` option. Google's production toolchain
+// turns this warning off by default, instead relying on clang-tidy to report
+// new uses of deprecated code.
+#if ABSL_HAVE_ATTRIBUTE(deprecated)
 #define ABSL_DEPRECATED(message) __attribute__((deprecated(message)))
-#endif
-
-#ifndef ABSL_DEPRECATED
+#else
 #define ABSL_DEPRECATED(message)
 #endif
 
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel
index 728c4be1..bc25bac9 100644
--- a/absl/container/BUILD.bazel
+++ b/absl/container/BUILD.bazel
@@ -914,6 +914,7 @@ cc_library(
         ":container_memory",
         ":layout",
         "//absl/base:core_headers",
+        "//absl/base:raw_logging_internal",
         "//absl/base:throw_delegate",
         "//absl/memory",
         "//absl/meta:type_traits",
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt
index b819deeb..648a3dba 100644
--- a/absl/container/CMakeLists.txt
+++ b/absl/container/CMakeLists.txt
@@ -35,6 +35,7 @@ absl_cc_library(
     absl::core_headers
     absl::layout
     absl::memory
+    absl::raw_logging_internal
     absl::strings
     absl::throw_delegate
     absl::type_traits
diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc
index b2c3d73f..e829e0ba 100644
--- a/absl/container/btree_test.cc
+++ b/absl/container/btree_test.cc
@@ -1213,6 +1213,11 @@ class BtreeNodePeer {
   constexpr static bool UsesLinearNodeSearch() {
     return btree_node<typename Btree::params_type>::use_linear_search::value;
   }
+
+  template <typename Btree>
+  constexpr static bool UsesGenerations() {
+    return Btree::params_type::kEnableGenerations;
+  }
 };
 
 namespace {
@@ -1478,8 +1483,10 @@ TEST(Btree, MovesComparisonsCopiesSwapsTracking) {
   EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<decltype(set61)>(), 61);
   EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<decltype(set100)>(), 100);
   if (sizeof(void *) == 8) {
-    EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<absl::btree_set<int32_t>>(),
-              BtreeNodePeer::GetNumSlotsPerNode<decltype(set61)>());
+    EXPECT_EQ(
+        BtreeNodePeer::GetNumSlotsPerNode<absl::btree_set<int32_t>>(),
+        // When we have generations, there is one fewer slot.
+        BtreeNodePeer::UsesGenerations<absl::btree_set<int32_t>>() ? 60 : 61);
   }
 
   // Test key insertion/deletion in random order.
@@ -1533,8 +1540,10 @@ TEST(Btree, MovesComparisonsCopiesSwapsTrackingThreeWayCompare) {
   EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<decltype(set61)>(), 61);
   EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<decltype(set100)>(), 100);
   if (sizeof(void *) == 8) {
-    EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<absl::btree_set<int32_t>>(),
-              BtreeNodePeer::GetNumSlotsPerNode<decltype(set61)>());
+    EXPECT_EQ(
+        BtreeNodePeer::GetNumSlotsPerNode<absl::btree_set<int32_t>>(),
+        // When we have generations, there is one fewer slot.
+        BtreeNodePeer::UsesGenerations<absl::btree_set<int32_t>>() ? 60 : 61);
   }
 
   // Test key insertion/deletion in random order.
@@ -3020,8 +3029,38 @@ TEST(Btree, InvalidComparatorsCaught) {
       }
     };
     absl::btree_set<int, ThreeWaySumGreaterZeroCmp> set;
-    EXPECT_DEATH(set.insert({0, 1, 2}),
-                 R"regex(lhs_comp_rhs < 0 -> rhs_comp_lhs > 0)regex");
+    EXPECT_DEATH(set.insert({0, 1, 2}), "lhs_comp_rhs < 0 -> rhs_comp_lhs > 0");
+  }
+}
+#endif
+
+#ifndef _MSC_VER
+// This test crashes on MSVC.
+TEST(Btree, InvalidIteratorUse) {
+  if (!BtreeNodePeer::UsesGenerations<absl::btree_set<int>>())
+    GTEST_SKIP() << "Generation validation for iterators is disabled.";
+
+  {
+    absl::btree_set<int> set;
+    for (int i = 0; i < 10; ++i) set.insert(i);
+    auto it = set.begin();
+    set.erase(it++);
+    EXPECT_DEATH(set.erase(it++), "invalidated iterator");
+  }
+  {
+    absl::btree_set<int> set;
+    for (int i = 0; i < 10; ++i) set.insert(i);
+    auto it = set.insert(20).first;
+    set.insert(30);
+    EXPECT_DEATH(*it, "invalidated iterator");
+  }
+  {
+    absl::btree_set<int> set;
+    for (int i = 0; i < 10000; ++i) set.insert(i);
+    auto it = set.find(5000);
+    ASSERT_NE(it, set.end());
+    set.erase(1);
+    EXPECT_DEATH(*it, "invalidated iterator");
   }
 }
 #endif
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index bbc319c1..6c10b00f 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -58,6 +58,7 @@
 #include <type_traits>
 #include <utility>
 
+#include "absl/base/internal/raw_logging.h"
 #include "absl/base/macros.h"
 #include "absl/container/internal/common.h"
 #include "absl/container/internal/compressed_tuple.h"
@@ -74,6 +75,16 @@ namespace absl {
 ABSL_NAMESPACE_BEGIN
 namespace container_internal {
 
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+#error ABSL_BTREE_ENABLE_GENERATIONS cannot be directly set
+#elif defined(ABSL_HAVE_ADDRESS_SANITIZER) || \
+    defined(ABSL_HAVE_MEMORY_SANITIZER)
+// When compiled in sanitizer mode, we add generation integers to the nodes and
+// iterators. When iterators are used, we validate that the container has not
+// been mutated since the iterator was constructed.
+#define ABSL_BTREE_ENABLE_GENERATIONS
+#endif
+
 template <typename Compare, typename T, typename U>
 using compare_result_t = absl::result_of_t<const Compare(const T &, const U &)>;
 
@@ -348,6 +359,12 @@ struct common_params {
   static constexpr bool kIsKeyCompareTransparent =
       IsTransparent<original_key_compare>::value ||
       kIsKeyCompareStringAdapted;
+  static constexpr bool kEnableGenerations =
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+      true;
+#else
+      false;
+#endif
 
   // A type which indicates if we have a key-compare-to functor or a plain old
   // key-compare functor.
@@ -518,6 +535,13 @@ class btree_node {
   //   // A pointer to the node's parent.
   //   btree_node *parent;
   //
+  //   // When ABSL_BTREE_ENABLE_GENERATIONS is defined, we also have a
+  //   // generation integer in order to check that when iterators are
+  //   // used, they haven't been invalidated already. Only the generation on
+  //   // the root is used, but we have one on each node because whether a node
+  //   // is root or not can change.
+  //   uint32_t generation;
+  //
   //   // The position of the node in the node's parent.
   //   field_type position;
   //   // The index of the first populated value in `values`.
@@ -564,13 +588,16 @@ class btree_node {
   btree_node() = default;
 
  private:
-  using layout_type = absl::container_internal::Layout<btree_node *, field_type,
-                                                       slot_type, btree_node *>;
+  using layout_type =
+      absl::container_internal::Layout<btree_node *, uint32_t, field_type,
+                                       slot_type, btree_node *>;
   constexpr static size_type SizeWithNSlots(size_type n) {
-    return layout_type(/*parent*/ 1,
-                       /*position, start, finish, max_count*/ 4,
-                       /*slots*/ n,
-                       /*children*/ 0)
+    return layout_type(
+               /*parent*/ 1,
+               /*generation*/ params_type::kEnableGenerations ? 1 : 0,
+               /*position, start, finish, max_count*/ 4,
+               /*slots*/ n,
+               /*children*/ 0)
         .AllocSize();
   }
   // A lower bound for the overhead of fields other than slots in a leaf node.
@@ -609,16 +636,20 @@ class btree_node {
 
   // Leaves can have less than kNodeSlots values.
   constexpr static layout_type LeafLayout(const int slot_count = kNodeSlots) {
-    return layout_type(/*parent*/ 1,
-                       /*position, start, finish, max_count*/ 4,
-                       /*slots*/ slot_count,
-                       /*children*/ 0);
+    return layout_type(
+        /*parent*/ 1,
+        /*generation*/ params_type::kEnableGenerations ? 1 : 0,
+        /*position, start, finish, max_count*/ 4,
+        /*slots*/ slot_count,
+        /*children*/ 0);
   }
   constexpr static layout_type InternalLayout() {
-    return layout_type(/*parent*/ 1,
-                       /*position, start, finish, max_count*/ 4,
-                       /*slots*/ kNodeSlots,
-                       /*children*/ kNodeSlots + 1);
+    return layout_type(
+        /*parent*/ 1,
+        /*generation*/ params_type::kEnableGenerations ? 1 : 0,
+        /*position, start, finish, max_count*/ 4,
+        /*slots*/ kNodeSlots,
+        /*children*/ kNodeSlots + 1);
   }
   constexpr static size_type LeafSize(const int slot_count = kNodeSlots) {
     return LeafLayout(slot_count).AllocSize();
@@ -632,44 +663,47 @@ class btree_node {
   template <size_type N>
   inline typename layout_type::template ElementType<N> *GetField() {
     // We assert that we don't read from values that aren't there.
-    assert(N < 3 || !leaf());
+    assert(N < 4 || is_internal());
     return InternalLayout().template Pointer<N>(reinterpret_cast<char *>(this));
   }
   template <size_type N>
   inline const typename layout_type::template ElementType<N> *GetField() const {
-    assert(N < 3 || !leaf());
+    assert(N < 4 || is_internal());
     return InternalLayout().template Pointer<N>(
         reinterpret_cast<const char *>(this));
   }
   void set_parent(btree_node *p) { *GetField<0>() = p; }
-  field_type &mutable_finish() { return GetField<1>()[2]; }
-  slot_type *slot(int i) { return &GetField<2>()[i]; }
+  field_type &mutable_finish() { return GetField<2>()[2]; }
+  slot_type *slot(int i) { return &GetField<3>()[i]; }
   slot_type *start_slot() { return slot(start()); }
   slot_type *finish_slot() { return slot(finish()); }
-  const slot_type *slot(int i) const { return &GetField<2>()[i]; }
-  void set_position(field_type v) { GetField<1>()[0] = v; }
-  void set_start(field_type v) { GetField<1>()[1] = v; }
-  void set_finish(field_type v) { GetField<1>()[2] = v; }
+  const slot_type *slot(int i) const { return &GetField<3>()[i]; }
+  void set_position(field_type v) { GetField<2>()[0] = v; }
+  void set_start(field_type v) { GetField<2>()[1] = v; }
+  void set_finish(field_type v) { GetField<2>()[2] = v; }
   // This method is only called by the node init methods.
-  void set_max_count(field_type v) { GetField<1>()[3] = v; }
+  void set_max_count(field_type v) { GetField<2>()[3] = v; }
 
  public:
   // Whether this is a leaf node or not. This value doesn't change after the
   // node is created.
-  bool leaf() const { return GetField<1>()[3] != kInternalNodeMaxCount; }
+  bool is_leaf() const { return GetField<2>()[3] != kInternalNodeMaxCount; }
+  // Whether this is an internal node or not. This value doesn't change after
+  // the node is created.
+  bool is_internal() const { return !is_leaf(); }
 
   // Getter for the position of this node in its parent.
-  field_type position() const { return GetField<1>()[0]; }
+  field_type position() const { return GetField<2>()[0]; }
 
   // Getter for the offset of the first value in the `values` array.
   field_type start() const {
-    // TODO(ezb): when floating storage is implemented, return GetField<1>()[1];
-    assert(GetField<1>()[1] == 0);
+    // TODO(ezb): when floating storage is implemented, return GetField<2>()[1];
+    assert(GetField<2>()[1] == 0);
     return 0;
   }
 
   // Getter for the offset after the last value in the `values` array.
-  field_type finish() const { return GetField<1>()[2]; }
+  field_type finish() const { return GetField<2>()[2]; }
 
   // Getters for the number of values stored in this node.
   field_type count() const {
@@ -679,7 +713,7 @@ class btree_node {
   field_type max_count() const {
     // Internal nodes have max_count==kInternalNodeMaxCount.
     // Leaf nodes have max_count in [1, kNodeSlots].
-    const field_type max_count = GetField<1>()[3];
+    const field_type max_count = GetField<2>()[3];
     return max_count == field_type{kInternalNodeMaxCount}
                ? field_type{kNodeSlots}
                : max_count;
@@ -690,21 +724,44 @@ class btree_node {
   // Getter for whether the node is the root of the tree. The parent of the
   // root of the tree is the leftmost node in the tree which is guaranteed to
   // be a leaf.
-  bool is_root() const { return parent()->leaf(); }
+  bool is_root() const { return parent()->is_leaf(); }
   void make_root() {
     assert(parent()->is_root());
+    set_generation(parent()->generation());
     set_parent(parent()->parent());
   }
 
+  // Gets the root node's generation integer, which is the one used by the tree.
+  uint32_t *get_root_generation() const {
+    assert(params_type::kEnableGenerations);
+    const btree_node *curr = this;
+    for (; !curr->is_root(); curr = curr->parent()) continue;
+    return const_cast<uint32_t *>(&curr->GetField<1>()[0]);
+  }
+
+  // Returns the generation for iterator validation.
+  uint32_t generation() const {
+    return params_type::kEnableGenerations ? *get_root_generation() : 0;
+  }
+  // Updates generation. Should only be called on a root node or during node
+  // initialization.
+  void set_generation(uint32_t generation) {
+    if (params_type::kEnableGenerations) GetField<1>()[0] = generation;
+  }
+  // Updates the generation. We do this whenever the node is mutated.
+  void next_generation() {
+    if (params_type::kEnableGenerations) ++*get_root_generation();
+  }
+
   // Getters for the key/value at position i in the node.
   const key_type &key(int i) const { return params_type::key(slot(i)); }
   reference value(int i) { return params_type::element(slot(i)); }
   const_reference value(int i) const { return params_type::element(slot(i)); }
 
   // Getters/setter for the child at position i in the node.
-  btree_node *child(int i) const { return GetField<3>()[i]; }
+  btree_node *child(int i) const { return GetField<4>()[i]; }
   btree_node *start_child() const { return child(start()); }
-  btree_node *&mutable_child(int i) { return GetField<3>()[i]; }
+  btree_node *&mutable_child(int i) { return GetField<4>()[i]; }
   void clear_child(int i) {
     absl::container_internal::SanitizerPoisonObject(&mutable_child(i));
   }
@@ -861,7 +918,8 @@ class btree_node {
   void merge(btree_node *src, allocator_type *alloc);
 
   // Node allocation/deletion routines.
-  void init_leaf(btree_node *parent, int max_count) {
+  void init_leaf(int max_count, btree_node *parent) {
+    set_generation(0);
     set_parent(parent);
     set_position(0);
     set_start(0);
@@ -871,7 +929,7 @@ class btree_node {
         start_slot(), max_count * sizeof(slot_type));
   }
   void init_internal(btree_node *parent) {
-    init_leaf(parent, kNodeSlots);
+    init_leaf(kNodeSlots, parent);
     // Set `max_count` to a sentinel value to indicate that this node is
     // internal.
     set_max_count(kInternalNodeMaxCount);
@@ -890,15 +948,18 @@ class btree_node {
  private:
   template <typename... Args>
   void value_init(const field_type i, allocator_type *alloc, Args &&... args) {
+    next_generation();
     absl::container_internal::SanitizerUnpoisonObject(slot(i));
     params_type::construct(alloc, slot(i), std::forward<Args>(args)...);
   }
   void value_destroy(const field_type i, allocator_type *alloc) {
+    next_generation();
     params_type::destroy(alloc, slot(i));
     absl::container_internal::SanitizerPoisonObject(slot(i));
   }
   void value_destroy_n(const field_type i, const field_type n,
                        allocator_type *alloc) {
+    next_generation();
     for (slot_type *s = slot(i), *end = slot(i + n); s != end; ++s) {
       params_type::destroy(alloc, s);
       absl::container_internal::SanitizerPoisonObject(s);
@@ -914,6 +975,7 @@ class btree_node {
   // Transfers value from slot `src_i` in `src_node` to slot `dest_i` in `this`.
   void transfer(const size_type dest_i, const size_type src_i,
                 btree_node *src_node, allocator_type *alloc) {
+    next_generation();
     transfer(slot(dest_i), src_node->slot(src_i), alloc);
   }
 
@@ -922,6 +984,7 @@ class btree_node {
   void transfer_n(const size_type n, const size_type dest_i,
                   const size_type src_i, btree_node *src_node,
                   allocator_type *alloc) {
+    next_generation();
     for (slot_type *src = src_node->slot(src_i), *end = src + n,
                    *dest = slot(dest_i);
          src != end; ++src, ++dest) {
@@ -934,6 +997,7 @@ class btree_node {
   void transfer_n_backward(const size_type n, const size_type dest_i,
                            const size_type src_i, btree_node *src_node,
                            allocator_type *alloc) {
+    next_generation();
     for (slot_type *src = src_node->slot(src_i + n - 1), *end = src - n,
                    *dest = slot(dest_i + n - 1);
          src != end; --src, --dest) {
@@ -944,14 +1008,13 @@ class btree_node {
   template <typename P>
   friend class btree;
   template <typename N, typename R, typename P>
-  friend struct btree_iterator;
+  friend class btree_iterator;
   friend class BtreeNodePeer;
   friend struct btree_access;
 };
 
 template <typename Node, typename Reference, typename Pointer>
-struct btree_iterator {
- private:
+class btree_iterator {
   using key_type = typename Node::key_type;
   using size_type = typename Node::size_type;
   using params_type = typename Node::params_type;
@@ -979,9 +1042,15 @@ struct btree_iterator {
   using reference = Reference;
   using iterator_category = std::bidirectional_iterator_tag;
 
-  btree_iterator() : node(nullptr), position(-1) {}
-  explicit btree_iterator(Node *n) : node(n), position(n->start()) {}
-  btree_iterator(Node *n, int p) : node(n), position(p) {}
+  btree_iterator() : btree_iterator(nullptr, -1) {}
+  explicit btree_iterator(Node *n) : btree_iterator(n, n->start()) {}
+  btree_iterator(Node *n, int p) : node_(n), position_(p) {
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+    // Use `~uint32_t{}` as a sentinel value for iterator generations so it
+    // doesn't match the initial value for the actual generation.
+    generation_ = n != nullptr ? n->generation() : ~uint32_t{};
+#endif
+  }
 
   // NOTE: this SFINAE allows for implicit conversions from iterator to
   // const_iterator, but it specifically avoids hiding the copy constructor so
@@ -992,58 +1061,32 @@ struct btree_iterator {
                     std::is_same<btree_iterator, const_iterator>::value,
                 int> = 0>
   btree_iterator(const btree_iterator<N, R, P> other)  // NOLINT
-      : node(other.node), position(other.position) {}
-
- private:
-  // This SFINAE allows explicit conversions from const_iterator to
-  // iterator, but also avoids hiding the copy constructor.
-  // NOTE: the const_cast is safe because this constructor is only called by
-  // non-const methods and the container owns the nodes.
-  template <typename N, typename R, typename P,
-            absl::enable_if_t<
-                std::is_same<btree_iterator<N, R, P>, const_iterator>::value &&
-                    std::is_same<btree_iterator, iterator>::value,
-                int> = 0>
-  explicit btree_iterator(const btree_iterator<N, R, P> other)
-      : node(const_cast<node_type *>(other.node)), position(other.position) {}
-
-  // Increment/decrement the iterator.
-  void increment() {
-    if (node->leaf() && ++position < node->finish()) {
-      return;
-    }
-    increment_slow();
-  }
-  void increment_slow();
-
-  void decrement() {
-    if (node->leaf() && --position >= node->start()) {
-      return;
-    }
-    decrement_slow();
+      : node_(other.node_), position_(other.position_) {
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+    generation_ = other.generation_;
+#endif
   }
-  void decrement_slow();
 
- public:
   bool operator==(const iterator &other) const {
-    return node == other.node && position == other.position;
+    return node_ == other.node_ && position_ == other.position_;
   }
   bool operator==(const const_iterator &other) const {
-    return node == other.node && position == other.position;
+    return node_ == other.node_ && position_ == other.position_;
   }
   bool operator!=(const iterator &other) const {
-    return node != other.node || position != other.position;
+    return node_ != other.node_ || position_ != other.position_;
   }
   bool operator!=(const const_iterator &other) const {
-    return node != other.node || position != other.position;
+    return node_ != other.node_ || position_ != other.position_;
   }
 
   // Accessors for the key/value the iterator is pointing at.
   reference operator*() const {
-    ABSL_HARDENING_ASSERT(node != nullptr);
-    ABSL_HARDENING_ASSERT(node->start() <= position);
-    ABSL_HARDENING_ASSERT(node->finish() > position);
-    return node->value(position);
+    ABSL_HARDENING_ASSERT(node_ != nullptr);
+    ABSL_HARDENING_ASSERT(node_->start() <= position_);
+    ABSL_HARDENING_ASSERT(node_->finish() > position_);
+    assert_valid_generation();
+    return node_->value(position_);
   }
   pointer operator->() const { return &operator*(); }
 
@@ -1083,15 +1126,74 @@ struct btree_iterator {
   friend class base_checker;
   friend struct btree_access;
 
-  const key_type &key() const { return node->key(position); }
-  slot_type *slot() { return node->slot(position); }
+  // This SFINAE allows explicit conversions from const_iterator to
+  // iterator, but also avoids hiding the copy constructor.
+  // NOTE: the const_cast is safe because this constructor is only called by
+  // non-const methods and the container owns the nodes.
+  template <typename N, typename R, typename P,
+            absl::enable_if_t<
+                std::is_same<btree_iterator<N, R, P>, const_iterator>::value &&
+                    std::is_same<btree_iterator, iterator>::value,
+                int> = 0>
+  explicit btree_iterator(const btree_iterator<N, R, P> other)
+      : node_(const_cast<node_type *>(other.node_)),
+        position_(other.position_) {
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+    generation_ = other.generation_;
+#endif
+  }
+
+  // Increment/decrement the iterator.
+  void increment() {
+    assert_valid_generation();
+    if (node_->is_leaf() && ++position_ < node_->finish()) {
+      return;
+    }
+    increment_slow();
+  }
+  void increment_slow();
+
+  void decrement() {
+    assert_valid_generation();
+    if (node_->is_leaf() && --position_ >= node_->start()) {
+      return;
+    }
+    decrement_slow();
+  }
+  void decrement_slow();
+
+  // Updates the generation. For use internally right before we return an
+  // iterator to the user.
+  void update_generation() {
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+    if (node_ != nullptr) generation_ = node_->generation();
+#endif
+  }
+
+  const key_type &key() const { return node_->key(position_); }
+  slot_type *slot() { return node_->slot(position_); }
+
+  void assert_valid_generation() const {
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+    if (node_ != nullptr && node_->generation() != generation_) {
+      ABSL_INTERNAL_LOG(
+          FATAL,
+          "Attempting to use an invalidated iterator. The corresponding b-tree "
+          "container has been mutated since this iterator was constructed.");
+    }
+#endif
+  }
 
   // The node in the tree the iterator is pointing at.
-  Node *node;
+  Node *node_;
   // The position within the node of the tree the iterator is pointing at.
   // NOTE: this is an int rather than a field_type because iterators can point
   // to invalid positions (such as -1) in certain circumstances.
-  int position;
+  int position_;
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+  // Used to check that the iterator hasn't been invalidated.
+  uint32_t generation_;
+#endif
 };
 
 template <typename Params>
@@ -1106,6 +1208,9 @@ class btree {
   struct alignas(node_type::Alignment()) EmptyNodeType : node_type {
     using field_type = typename node_type::field_type;
     node_type *parent;
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+    uint32_t generation = 0;
+#endif
     field_type position = 0;
     field_type start = 0;
     field_type finish = 0;
@@ -1490,12 +1595,12 @@ class btree {
   }
   node_type *new_leaf_node(node_type *parent) {
     node_type *n = allocate(node_type::LeafSize());
-    n->init_leaf(parent, kNodeSlots);
+    n->init_leaf(kNodeSlots, parent);
     return n;
   }
   node_type *new_leaf_root_node(const int max_count) {
     node_type *n = allocate(node_type::LeafSize(max_count));
-    n->init_leaf(/*parent=*/n, max_count);
+    n->init_leaf(max_count, /*parent=*/n);
     return n;
   }
 
@@ -1519,10 +1624,10 @@ class btree {
   void try_shrink();
 
   iterator internal_end(iterator iter) {
-    return iter.node != nullptr ? iter : end();
+    return iter.node_ != nullptr ? iter : end();
   }
   const_iterator internal_end(const_iterator iter) const {
-    return iter.node != nullptr ? iter : end();
+    return iter.node_ != nullptr ? iter : end();
   }
 
   // Emplaces a value into the btree immediately before iter. Requires that
@@ -1532,9 +1637,8 @@ class btree {
 
   // Returns an iterator pointing to the first value >= the value "iter" is
   // pointing at. Note that "iter" might be pointing to an invalid location such
-  // as iter.position == iter.node->finish(). This routine simply moves iter up
-  // in the tree to a valid location.
-  // Requires: iter.node is non-null.
+  // as iter.position_ == iter.node_->finish(). This routine simply moves iter
+  // up in the tree to a valid location. Requires: iter.node_ is non-null.
   template <typename IterType>
   static IterType internal_last(IterType iter);
 
@@ -1570,7 +1674,7 @@ class btree {
     if (node == nullptr || (node == root() && empty())) {
       return node_stats(0, 0);
     }
-    if (node->leaf()) {
+    if (node->is_leaf()) {
       return node_stats(1, 0);
     }
     node_stats res(0, 1);
@@ -1612,7 +1716,7 @@ inline void btree_node<P>::emplace_value(const size_type i,
   value_init(i, alloc, std::forward<Args>(args)...);
   set_finish(finish() + 1);
 
-  if (!leaf() && finish() > i + 1) {
+  if (is_internal() && finish() > i + 1) {
     for (field_type j = finish(); j > i + 1; --j) {
       set_child(j, child(j - 1));
     }
@@ -1630,7 +1734,7 @@ inline void btree_node<P>::remove_values(const field_type i,
   const field_type src_i = i + to_erase;
   transfer_n(orig_finish - src_i, i, src_i, this, alloc);
 
-  if (!leaf()) {
+  if (is_internal()) {
     // Delete all children between begin and end.
     for (int j = 0; j < to_erase; ++j) {
       clear_and_delete(child(i + j + 1), alloc);
@@ -1667,7 +1771,7 @@ void btree_node<P>::rebalance_right_to_left(const int to_move,
   right->transfer_n(right->count() - to_move, right->start(),
                     right->start() + to_move, right, alloc);
 
-  if (!leaf()) {
+  if (is_internal()) {
     // Move the child pointers from the right to the left node.
     for (int i = 0; i < to_move; ++i) {
       init_child(finish() + i + 1, right->child(i));
@@ -1714,7 +1818,7 @@ void btree_node<P>::rebalance_left_to_right(const int to_move,
   // 4) Move the new delimiting value to the parent from the left node.
   parent()->transfer(position(), finish() - to_move, this, alloc);
 
-  if (!leaf()) {
+  if (is_internal()) {
     // Move the child pointers from the left to the right node.
     for (int i = right->finish(); i >= right->start(); --i) {
       right->init_child(i + to_move, right->child(i));
@@ -1760,7 +1864,7 @@ void btree_node<P>::split(const int insert_position, btree_node *dest,
   value_destroy(finish(), alloc);
   parent()->init_child(position() + 1, dest);
 
-  if (!leaf()) {
+  if (is_internal()) {
     for (int i = dest->start(), j = finish() + 1; i <= dest->finish();
          ++i, ++j) {
       assert(child(j) != nullptr);
@@ -1781,7 +1885,7 @@ void btree_node<P>::merge(btree_node *src, allocator_type *alloc) {
   // Move the values from the right to the left node.
   transfer_n(src->count(), finish() + 1, src->start(), src, alloc);
 
-  if (!leaf()) {
+  if (is_internal()) {
     // Move the child pointers from the right to the left node.
     for (int i = src->start(), j = finish() + 1; i <= src->finish(); ++i, ++j) {
       init_child(j, src->child(i));
@@ -1799,7 +1903,7 @@ void btree_node<P>::merge(btree_node *src, allocator_type *alloc) {
 
 template <typename P>
 void btree_node<P>::clear_and_delete(btree_node *node, allocator_type *alloc) {
-  if (node->leaf()) {
+  if (node->is_leaf()) {
     node->value_destroy_n(node->start(), node->count(), alloc);
     deallocate(LeafSize(node->max_count()), node, alloc);
     return;
@@ -1813,7 +1917,15 @@ void btree_node<P>::clear_and_delete(btree_node *node, allocator_type *alloc) {
   btree_node *delete_root_parent = node->parent();
 
   // Navigate to the leftmost leaf under node, and then delete upwards.
-  while (!node->leaf()) node = node->start_child();
+  while (node->is_internal()) node = node->start_child();
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+  // When generations are enabled, we delete the leftmost leaf last in case it's
+  // the parent of the root and we need to check whether it's a leaf before we
+  // can update the root's generation.
+  // TODO(ezb): if we change btree_node::is_root to check a bool inside the node
+  // instead of checking whether the parent is a leaf, we can remove this logic.
+  btree_node *leftmost_leaf = node;
+#endif
   // Use `int` because `pos` needs to be able to hold `kNodeSlots+1`, which
   // isn't guaranteed to be a valid `field_type`.
   int pos = node->position();
@@ -1823,14 +1935,17 @@ void btree_node<P>::clear_and_delete(btree_node *node, allocator_type *alloc) {
     assert(pos <= parent->finish());
     do {
       node = parent->child(pos);
-      if (!node->leaf()) {
+      if (node->is_internal()) {
         // Navigate to the leftmost leaf under node.
-        while (!node->leaf()) node = node->start_child();
+        while (node->is_internal()) node = node->start_child();
         pos = node->position();
         parent = node->parent();
       }
       node->value_destroy_n(node->start(), node->count(), alloc);
-      deallocate(LeafSize(node->max_count()), node, alloc);
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+      if (leftmost_leaf != node)
+#endif
+        deallocate(LeafSize(node->max_count()), node, alloc);
       ++pos;
     } while (pos <= parent->finish());
 
@@ -1842,7 +1957,12 @@ void btree_node<P>::clear_and_delete(btree_node *node, allocator_type *alloc) {
       parent = node->parent();
       node->value_destroy_n(node->start(), node->count(), alloc);
       deallocate(InternalSize(), node, alloc);
-      if (parent == delete_root_parent) return;
+      if (parent == delete_root_parent) {
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+        deallocate(LeafSize(leftmost_leaf->max_count()), leftmost_leaf, alloc);
+#endif
+        return;
+      }
       ++pos;
     } while (pos > parent->finish());
   }
@@ -1852,49 +1972,49 @@ void btree_node<P>::clear_and_delete(btree_node *node, allocator_type *alloc) {
 // btree_iterator methods
 template <typename N, typename R, typename P>
 void btree_iterator<N, R, P>::increment_slow() {
-  if (node->leaf()) {
-    assert(position >= node->finish());
+  if (node_->is_leaf()) {
+    assert(position_ >= node_->finish());
     btree_iterator save(*this);
-    while (position == node->finish() && !node->is_root()) {
-      assert(node->parent()->child(node->position()) == node);
-      position = node->position();
-      node = node->parent();
+    while (position_ == node_->finish() && !node_->is_root()) {
+      assert(node_->parent()->child(node_->position()) == node_);
+      position_ = node_->position();
+      node_ = node_->parent();
     }
     // TODO(ezb): assert we aren't incrementing end() instead of handling.
-    if (position == node->finish()) {
+    if (position_ == node_->finish()) {
       *this = save;
     }
   } else {
-    assert(position < node->finish());
-    node = node->child(position + 1);
-    while (!node->leaf()) {
-      node = node->start_child();
+    assert(position_ < node_->finish());
+    node_ = node_->child(position_ + 1);
+    while (node_->is_internal()) {
+      node_ = node_->start_child();
     }
-    position = node->start();
+    position_ = node_->start();
   }
 }
 
 template <typename N, typename R, typename P>
 void btree_iterator<N, R, P>::decrement_slow() {
-  if (node->leaf()) {
-    assert(position <= -1);
+  if (node_->is_leaf()) {
+    assert(position_ <= -1);
     btree_iterator save(*this);
-    while (position < node->start() && !node->is_root()) {
-      assert(node->parent()->child(node->position()) == node);
-      position = node->position() - 1;
-      node = node->parent();
+    while (position_ < node_->start() && !node_->is_root()) {
+      assert(node_->parent()->child(node_->position()) == node_);
+      position_ = node_->position() - 1;
+      node_ = node_->parent();
     }
     // TODO(ezb): assert we aren't decrementing begin() instead of handling.
-    if (position < node->start()) {
+    if (position_ < node_->start()) {
       *this = save;
     }
   } else {
-    assert(position >= node->start());
-    node = node->child(position);
-    while (!node->leaf()) {
-      node = node->child(node->finish());
+    assert(position_ >= node_->start());
+    node_ = node_->child(position_);
+    while (node_->is_internal()) {
+      node_ = node_->child(node_->finish());
     }
-    position = node->finish() - 1;
+    position_ = node_->finish() - 1;
   }
 }
 
@@ -2009,7 +2129,7 @@ auto btree<P>::insert_unique(const K &key, Args &&... args)
     }
   } else {
     iterator last = internal_last(iter);
-    if (last.node && !compare_keys(key, last.key())) {
+    if (last.node_ && !compare_keys(key, last.key())) {
       // The key already exists in the tree, do nothing.
       return {last, false};
     }
@@ -2067,7 +2187,7 @@ auto btree<P>::insert_multi(const key_type &key, ValueType &&v) -> iterator {
   }
 
   iterator iter = internal_upper_bound(key);
-  if (iter.node == nullptr) {
+  if (iter.node_ == nullptr) {
     iter = end();
   }
   return internal_emplace(iter, std::forward<ValueType>(v));
@@ -2154,21 +2274,22 @@ auto btree<P>::operator=(btree &&other) noexcept -> btree & {
 template <typename P>
 auto btree<P>::erase(iterator iter) -> iterator {
   bool internal_delete = false;
-  if (!iter.node->leaf()) {
+  if (iter.node_->is_internal()) {
     // Deletion of a value on an internal node. First, move the largest value
     // from our left child here, then delete that position (in remove_values()
     // below). We can get to the largest value from our left child by
     // decrementing iter.
     iterator internal_iter(iter);
     --iter;
-    assert(iter.node->leaf());
-    params_type::move(mutable_allocator(), iter.node->slot(iter.position),
-                      internal_iter.node->slot(internal_iter.position));
+    assert(iter.node_->is_leaf());
+    params_type::move(mutable_allocator(), iter.node_->slot(iter.position_),
+                      internal_iter.node_->slot(internal_iter.position_));
     internal_delete = true;
   }
 
   // Delete the key from the leaf.
-  iter.node->remove_values(iter.position, /*to_erase=*/1, mutable_allocator());
+  iter.node_->remove_values(iter.position_, /*to_erase=*/1,
+                            mutable_allocator());
   --size_;
 
   // We want to return the next value after the one we just erased. If we
@@ -2176,7 +2297,7 @@ auto btree<P>::erase(iterator iter) -> iterator {
   // value is ++(++iter). If we erased from a leaf node (internal_delete ==
   // false) then the next value is ++iter. Note that ++iter may point to an
   // internal node and the value in the internal node may move to a leaf node
-  // (iter.node) when rebalancing is performed at the leaf level.
+  // (iter.node_) when rebalancing is performed at the leaf level.
 
   iterator res = rebalance_after_delete(iter);
 
@@ -2193,14 +2314,14 @@ auto btree<P>::rebalance_after_delete(iterator iter) -> iterator {
   iterator res(iter);
   bool first_iteration = true;
   for (;;) {
-    if (iter.node == root()) {
+    if (iter.node_ == root()) {
       try_shrink();
       if (empty()) {
         return end();
       }
       break;
     }
-    if (iter.node->count() >= kMinNodeValues) {
+    if (iter.node_->count() >= kMinNodeValues) {
       break;
     }
     bool merged = try_merge_or_rebalance(&iter);
@@ -2213,14 +2334,15 @@ auto btree<P>::rebalance_after_delete(iterator iter) -> iterator {
     if (!merged) {
       break;
     }
-    iter.position = iter.node->position();
-    iter.node = iter.node->parent();
+    iter.position_ = iter.node_->position();
+    iter.node_ = iter.node_->parent();
   }
+  res.update_generation();
 
   // Adjust our return value. If we're pointing at the end of a node, advance
   // the iterator.
-  if (res.position == res.node->finish()) {
-    res.position = res.node->finish() - 1;
+  if (res.position_ == res.node_->finish()) {
+    res.position_ = res.node_->finish() - 1;
     ++res;
   }
 
@@ -2242,28 +2364,31 @@ auto btree<P>::erase_range(iterator begin, iterator end)
     return {count, this->end()};
   }
 
-  if (begin.node == end.node) {
-    assert(end.position > begin.position);
-    begin.node->remove_values(begin.position, end.position - begin.position,
-                              mutable_allocator());
+  if (begin.node_ == end.node_) {
+    assert(end.position_ > begin.position_);
+    begin.node_->remove_values(begin.position_, end.position_ - begin.position_,
+                               mutable_allocator());
     size_ -= count;
     return {count, rebalance_after_delete(begin)};
   }
 
   const size_type target_size = size_ - count;
   while (size_ > target_size) {
-    if (begin.node->leaf()) {
+    if (begin.node_->is_leaf()) {
       const size_type remaining_to_erase = size_ - target_size;
-      const size_type remaining_in_node = begin.node->finish() - begin.position;
+      const size_type remaining_in_node =
+          begin.node_->finish() - begin.position_;
       const size_type to_erase =
           (std::min)(remaining_to_erase, remaining_in_node);
-      begin.node->remove_values(begin.position, to_erase, mutable_allocator());
+      begin.node_->remove_values(begin.position_, to_erase,
+                                 mutable_allocator());
       size_ -= to_erase;
       begin = rebalance_after_delete(begin);
     } else {
       begin = erase(begin);
     }
   }
+  begin.update_generation();
   return {count, begin};
 }
 
@@ -2300,16 +2425,16 @@ void btree<P>::verify() const {
   assert(leftmost() != nullptr);
   assert(rightmost_ != nullptr);
   assert(empty() || size() == internal_verify(root(), nullptr, nullptr));
-  assert(leftmost() == (++const_iterator(root(), -1)).node);
-  assert(rightmost_ == (--const_iterator(root(), root()->finish())).node);
-  assert(leftmost()->leaf());
-  assert(rightmost_->leaf());
+  assert(leftmost() == (++const_iterator(root(), -1)).node_);
+  assert(rightmost_ == (--const_iterator(root(), root()->finish())).node_);
+  assert(leftmost()->is_leaf());
+  assert(rightmost_->is_leaf());
 }
 
 template <typename P>
 void btree<P>::rebalance_or_split(iterator *iter) {
-  node_type *&node = iter->node;
-  int &insert_position = iter->position;
+  node_type *&node = iter->node_;
+  int &insert_position = iter->position_;
   assert(node->count() == node->max_count());
   assert(kNodeSlots == node->max_count());
 
@@ -2384,16 +2509,17 @@ void btree<P>::rebalance_or_split(iterator *iter) {
     // Create a new root node and set the current root node as the child of the
     // new root.
     parent = new_internal_node(parent);
+    parent->set_generation(root()->generation());
     parent->init_child(parent->start(), root());
     mutable_root() = parent;
     // If the former root was a leaf node, then it's now the rightmost node.
-    assert(!parent->start_child()->leaf() ||
+    assert(parent->start_child()->is_internal() ||
            parent->start_child() == rightmost_);
   }
 
   // Split the node.
   node_type *split_node;
-  if (node->leaf()) {
+  if (node->is_leaf()) {
     split_node = new_leaf_node(parent);
     node->split(insert_position, split_node, mutable_allocator());
     if (rightmost_ == node) rightmost_ = split_node;
@@ -2416,50 +2542,51 @@ void btree<P>::merge_nodes(node_type *left, node_type *right) {
 
 template <typename P>
 bool btree<P>::try_merge_or_rebalance(iterator *iter) {
-  node_type *parent = iter->node->parent();
-  if (iter->node->position() > parent->start()) {
+  node_type *parent = iter->node_->parent();
+  if (iter->node_->position() > parent->start()) {
     // Try merging with our left sibling.
-    node_type *left = parent->child(iter->node->position() - 1);
+    node_type *left = parent->child(iter->node_->position() - 1);
     assert(left->max_count() == kNodeSlots);
-    if (1U + left->count() + iter->node->count() <= kNodeSlots) {
-      iter->position += 1 + left->count();
-      merge_nodes(left, iter->node);
-      iter->node = left;
+    if (1U + left->count() + iter->node_->count() <= kNodeSlots) {
+      iter->position_ += 1 + left->count();
+      merge_nodes(left, iter->node_);
+      iter->node_ = left;
       return true;
     }
   }
-  if (iter->node->position() < parent->finish()) {
+  if (iter->node_->position() < parent->finish()) {
     // Try merging with our right sibling.
-    node_type *right = parent->child(iter->node->position() + 1);
+    node_type *right = parent->child(iter->node_->position() + 1);
     assert(right->max_count() == kNodeSlots);
-    if (1U + iter->node->count() + right->count() <= kNodeSlots) {
-      merge_nodes(iter->node, right);
+    if (1U + iter->node_->count() + right->count() <= kNodeSlots) {
+      merge_nodes(iter->node_, right);
       return true;
     }
     // Try rebalancing with our right sibling. We don't perform rebalancing if
-    // we deleted the first element from iter->node and the node is not
+    // we deleted the first element from iter->node_ and the node is not
     // empty. This is a small optimization for the common pattern of deleting
     // from the front of the tree.
     if (right->count() > kMinNodeValues &&
-        (iter->node->count() == 0 || iter->position > iter->node->start())) {
-      int to_move = (right->count() - iter->node->count()) / 2;
+        (iter->node_->count() == 0 || iter->position_ > iter->node_->start())) {
+      int to_move = (right->count() - iter->node_->count()) / 2;
       to_move = (std::min)(to_move, right->count() - 1);
-      iter->node->rebalance_right_to_left(to_move, right, mutable_allocator());
+      iter->node_->rebalance_right_to_left(to_move, right, mutable_allocator());
       return false;
     }
   }
-  if (iter->node->position() > parent->start()) {
+  if (iter->node_->position() > parent->start()) {
     // Try rebalancing with our left sibling. We don't perform rebalancing if
-    // we deleted the last element from iter->node and the node is not
+    // we deleted the last element from iter->node_ and the node is not
     // empty. This is a small optimization for the common pattern of deleting
     // from the back of the tree.
-    node_type *left = parent->child(iter->node->position() - 1);
+    node_type *left = parent->child(iter->node_->position() - 1);
     if (left->count() > kMinNodeValues &&
-        (iter->node->count() == 0 || iter->position < iter->node->finish())) {
-      int to_move = (left->count() - iter->node->count()) / 2;
+        (iter->node_->count() == 0 ||
+         iter->position_ < iter->node_->finish())) {
+      int to_move = (left->count() - iter->node_->count()) / 2;
       to_move = (std::min)(to_move, left->count() - 1);
-      left->rebalance_left_to_right(to_move, iter->node, mutable_allocator());
-      iter->position += to_move;
+      left->rebalance_left_to_right(to_move, iter->node_, mutable_allocator());
+      iter->position_ += to_move;
       return false;
     }
   }
@@ -2473,7 +2600,7 @@ void btree<P>::try_shrink() {
     return;
   }
   // Deleted the last item on the root node, shrink the height of the tree.
-  if (orig_root->leaf()) {
+  if (orig_root->is_leaf()) {
     assert(size() == 0);
     mutable_root() = rightmost_ = EmptyNode();
   } else {
@@ -2487,15 +2614,16 @@ void btree<P>::try_shrink() {
 template <typename P>
 template <typename IterType>
 inline IterType btree<P>::internal_last(IterType iter) {
-  assert(iter.node != nullptr);
-  while (iter.position == iter.node->finish()) {
-    iter.position = iter.node->position();
-    iter.node = iter.node->parent();
-    if (iter.node->leaf()) {
-      iter.node = nullptr;
+  assert(iter.node_ != nullptr);
+  while (iter.position_ == iter.node_->finish()) {
+    iter.position_ = iter.node_->position();
+    iter.node_ = iter.node_->parent();
+    if (iter.node_->is_leaf()) {
+      iter.node_ = nullptr;
       break;
     }
   }
+  iter.update_generation();
   return iter;
 }
 
@@ -2503,37 +2631,39 @@ template <typename P>
 template <typename... Args>
 inline auto btree<P>::internal_emplace(iterator iter, Args &&... args)
     -> iterator {
-  if (!iter.node->leaf()) {
+  if (iter.node_->is_internal()) {
     // We can't insert on an internal node. Instead, we'll insert after the
     // previous value which is guaranteed to be on a leaf node.
     --iter;
-    ++iter.position;
+    ++iter.position_;
   }
-  const field_type max_count = iter.node->max_count();
+  const field_type max_count = iter.node_->max_count();
   allocator_type *alloc = mutable_allocator();
-  if (iter.node->count() == max_count) {
+  if (iter.node_->count() == max_count) {
     // Make room in the leaf for the new item.
     if (max_count < kNodeSlots) {
       // Insertion into the root where the root is smaller than the full node
       // size. Simply grow the size of the root node.
-      assert(iter.node == root());
-      iter.node =
+      assert(iter.node_ == root());
+      iter.node_ =
           new_leaf_root_node((std::min<int>)(kNodeSlots, 2 * max_count));
       // Transfer the values from the old root to the new root.
       node_type *old_root = root();
-      node_type *new_root = iter.node;
+      node_type *new_root = iter.node_;
       new_root->transfer_n(old_root->count(), new_root->start(),
                            old_root->start(), old_root, alloc);
       new_root->set_finish(old_root->finish());
       old_root->set_finish(old_root->start());
+      new_root->set_generation(old_root->generation());
       node_type::clear_and_delete(old_root, alloc);
       mutable_root() = rightmost_ = new_root;
     } else {
       rebalance_or_split(&iter);
     }
   }
-  iter.node->emplace_value(iter.position, alloc, std::forward<Args>(args)...);
+  iter.node_->emplace_value(iter.position_, alloc, std::forward<Args>(args)...);
   ++size_;
+  iter.update_generation();
   return iter;
 }
 
@@ -2544,8 +2674,8 @@ inline auto btree<P>::internal_locate(const K &key) const
   iterator iter(const_cast<node_type *>(root()));
   for (;;) {
     SearchResult<int, is_key_compare_to::value> res =
-        iter.node->lower_bound(key, key_comp());
-    iter.position = res.value;
+        iter.node_->lower_bound(key, key_comp());
+    iter.position_ = res.value;
     if (res.IsEq()) {
       return {iter, MatchKind::kEq};
     }
@@ -2553,10 +2683,10 @@ inline auto btree<P>::internal_locate(const K &key) const
     // down the tree if the keys are equal, but determining equality would
     // require doing an extra comparison on each node on the way down, and we
     // will need to go all the way to the leaf node in the expected case.
-    if (iter.node->leaf()) {
+    if (iter.node_->is_leaf()) {
       break;
     }
-    iter.node = iter.node->child(iter.position);
+    iter.node_ = iter.node_->child(iter.position_);
   }
   // Note: in the non-key-compare-to case, the key may actually be equivalent
   // here (and the MatchKind::kNe is ignored).
@@ -2576,13 +2706,13 @@ auto btree<P>::internal_lower_bound(const K &key) const
   SearchResult<int, is_key_compare_to::value> res;
   bool seen_eq = false;
   for (;;) {
-    res = iter.node->lower_bound(key, key_comp());
-    iter.position = res.value;
-    if (iter.node->leaf()) {
+    res = iter.node_->lower_bound(key, key_comp());
+    iter.position_ = res.value;
+    if (iter.node_->is_leaf()) {
       break;
     }
     seen_eq = seen_eq || res.IsEq();
-    iter.node = iter.node->child(iter.position);
+    iter.node_ = iter.node_->child(iter.position_);
   }
   if (res.IsEq()) return {iter, MatchKind::kEq};
   return {internal_last(iter), seen_eq ? MatchKind::kEq : MatchKind::kNe};
@@ -2593,11 +2723,11 @@ template <typename K>
 auto btree<P>::internal_upper_bound(const K &key) const -> iterator {
   iterator iter(const_cast<node_type *>(root()));
   for (;;) {
-    iter.position = iter.node->upper_bound(key, key_comp());
-    if (iter.node->leaf()) {
+    iter.position_ = iter.node_->upper_bound(key, key_comp());
+    if (iter.node_->is_leaf()) {
       break;
     }
-    iter.node = iter.node->child(iter.position);
+    iter.node_ = iter.node_->child(iter.position_);
   }
   return internal_last(iter);
 }
@@ -2612,7 +2742,7 @@ auto btree<P>::internal_find(const K &key) const -> iterator {
     }
   } else {
     const iterator iter = internal_last(res.value);
-    if (iter.node != nullptr && !compare_keys(key, iter.key())) {
+    if (iter.node_ != nullptr && !compare_keys(key, iter.key())) {
       return iter;
     }
   }
@@ -2634,7 +2764,7 @@ int btree<P>::internal_verify(const node_type *node, const key_type *lo,
     assert(!compare_keys(node->key(i), node->key(i - 1)));
   }
   int count = node->count();
-  if (!node->leaf()) {
+  if (node->is_internal()) {
     for (int i = node->start(); i <= node->finish(); ++i) {
       assert(node->child(i) != nullptr);
       assert(node->child(i)->parent() == node);
@@ -2659,8 +2789,8 @@ struct btree_access {
         ++it;
         continue;
       }
-      auto *node = it.node;
-      if (!node->leaf()) {
+      auto *node = it.node_;
+      if (node->is_internal()) {
         // Handle internal nodes normally.
         it = container.erase(it);
         continue;
@@ -2669,26 +2799,28 @@ struct btree_access {
       // at once before doing rebalancing.
 
       // The current position to transfer slots to.
-      int to_pos = it.position;
-      node->value_destroy(it.position, alloc);
-      while (++it.position < node->finish()) {
+      int to_pos = it.position_;
+      node->value_destroy(it.position_, alloc);
+      while (++it.position_ < node->finish()) {
+        it.update_generation();
         if (pred(*it)) {
-          node->value_destroy(it.position, alloc);
+          node->value_destroy(it.position_, alloc);
         } else {
-          node->transfer(node->slot(to_pos++), node->slot(it.position),
-                         alloc);
+          node->transfer(node->slot(to_pos++), node->slot(it.position_), alloc);
         }
       }
       const int num_deleted = node->finish() - to_pos;
       tree.size_ -= num_deleted;
       node->set_finish(to_pos);
-      it.position = to_pos;
+      it.position_ = to_pos;
       it = tree.rebalance_after_delete(it);
     }
     return initial_size - container.size();
   }
 };
 
+#undef ABSL_BTREE_ENABLE_GENERATIONS
+
 }  // namespace container_internal
 ABSL_NAMESPACE_END
 }  // namespace absl
diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h
index bae5c6e2..cc2e1793 100644
--- a/absl/container/internal/btree_container.h
+++ b/absl/container/internal/btree_container.h
@@ -537,6 +537,7 @@ class btree_multiset_container : public btree_container<Tree> {
   using params_type = typename Tree::params_type;
   using init_type = typename params_type::init_type;
   using is_key_compare_to = typename params_type::is_key_compare_to;
+  friend class BtreeNodePeer;
 
   template <class K>
   using key_arg = typename super_type::template key_arg<K>;
@@ -668,6 +669,7 @@ template <typename Tree>
 class btree_multimap_container : public btree_multiset_container<Tree> {
   using super_type = btree_multiset_container<Tree>;
   using params_type = typename Tree::params_type;
+  friend class BtreeNodePeer;
 
  public:
   using mapped_type = typename params_type::mapped_type;
diff --git a/absl/random/mocking_bit_gen.h b/absl/random/mocking_bit_gen.h
index 7b2b80eb..89fa5a47 100644
--- a/absl/random/mocking_bit_gen.h
+++ b/absl/random/mocking_bit_gen.h
@@ -87,7 +87,7 @@ class BitGenRef;
 //
 //   ON_CALL(absl::MockUniform<int>(), Call(bitgen, testing::_, testing::_))
 //       .WillByDefault([] (int low, int high) {
-//           return (low + high) / 2;
+//           return low + (high - low) / 2;
 //       });
 //
 //   EXPECT_EQ(absl::Uniform<int>(gen, 0, 10), 5);
diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel
index 617577cd..129affec 100644
--- a/absl/strings/BUILD.bazel
+++ b/absl/strings/BUILD.bazel
@@ -271,7 +271,6 @@ cc_library(
         "internal/cord_rep_btree.cc",
         "internal/cord_rep_btree_navigator.cc",
         "internal/cord_rep_btree_reader.cc",
-        "internal/cord_rep_concat.cc",
         "internal/cord_rep_consume.cc",
         "internal/cord_rep_crc.cc",
         "internal/cord_rep_ring.cc",
diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt
index e73a1ea0..f31eef4d 100644
--- a/absl/strings/CMakeLists.txt
+++ b/absl/strings/CMakeLists.txt
@@ -568,7 +568,6 @@ absl_cc_library(
     "internal/cord_rep_btree.cc"
     "internal/cord_rep_btree_navigator.cc"
     "internal/cord_rep_btree_reader.cc"
-    "internal/cord_rep_concat.cc"
     "internal/cord_rep_crc.cc"
     "internal/cord_rep_consume.cc"
     "internal/cord_rep_ring.cc"
diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc
index 59722107..4ee722da 100644
--- a/absl/strings/cord.cc
+++ b/absl/strings/cord.cc
@@ -53,7 +53,6 @@ ABSL_NAMESPACE_BEGIN
 
 using ::absl::cord_internal::CordRep;
 using ::absl::cord_internal::CordRepBtree;
-using ::absl::cord_internal::CordRepConcat;
 using ::absl::cord_internal::CordRepCrc;
 using ::absl::cord_internal::CordRepExternal;
 using ::absl::cord_internal::CordRepFlat;
@@ -66,53 +65,6 @@ using ::absl::cord_internal::kMinFlatLength;
 using ::absl::cord_internal::kInlinedVectorSize;
 using ::absl::cord_internal::kMaxBytesToCopy;
 
-constexpr uint64_t Fibonacci(unsigned char n, uint64_t a = 0, uint64_t b = 1) {
-  return n == 0 ? a : Fibonacci(n - 1, b, a + b);
-}
-
-static_assert(Fibonacci(63) == 6557470319842,
-              "Fibonacci values computed incorrectly");
-
-// Minimum length required for a given depth tree -- a tree is considered
-// balanced if
-//      length(t) >= min_length[depth(t)]
-// The root node depth is allowed to become twice as large to reduce rebalancing
-// for larger strings (see IsRootBalanced).
-static constexpr uint64_t min_length[] = {
-    Fibonacci(2),          Fibonacci(3),  Fibonacci(4),  Fibonacci(5),
-    Fibonacci(6),          Fibonacci(7),  Fibonacci(8),  Fibonacci(9),
-    Fibonacci(10),         Fibonacci(11), Fibonacci(12), Fibonacci(13),
-    Fibonacci(14),         Fibonacci(15), Fibonacci(16), Fibonacci(17),
-    Fibonacci(18),         Fibonacci(19), Fibonacci(20), Fibonacci(21),
-    Fibonacci(22),         Fibonacci(23), Fibonacci(24), Fibonacci(25),
-    Fibonacci(26),         Fibonacci(27), Fibonacci(28), Fibonacci(29),
-    Fibonacci(30),         Fibonacci(31), Fibonacci(32), Fibonacci(33),
-    Fibonacci(34),         Fibonacci(35), Fibonacci(36), Fibonacci(37),
-    Fibonacci(38),         Fibonacci(39), Fibonacci(40), Fibonacci(41),
-    Fibonacci(42),         Fibonacci(43), Fibonacci(44), Fibonacci(45),
-    Fibonacci(46),         Fibonacci(47),
-    0xffffffffffffffffull,  // Avoid overflow
-};
-
-static const int kMinLengthSize = ABSL_ARRAYSIZE(min_length);
-
-static inline constexpr bool btree_enabled() { return true; }
-
-static inline bool IsRootBalanced(CordRep* node) {
-  if (!node->IsConcat()) {
-    return true;
-  } else if (node->concat()->depth() <= 15) {
-    return true;
-  } else if (node->concat()->depth() > kMinLengthSize) {
-    return false;
-  } else {
-    // Allow depth to become twice as large as implied by fibonacci rule to
-    // reduce rebalancing for larger strings.
-    return (node->length >= min_length[node->concat()->depth() / 2]);
-  }
-}
-
-static CordRep* Rebalance(CordRep* node);
 static void DumpNode(CordRep* rep, bool include_data, std::ostream* os,
                      int indent = 0);
 static bool VerifyNode(CordRep* root, CordRep* start_node,
@@ -134,24 +86,6 @@ static inline CordRep* VerifyTree(CordRep* node) {
   return node;
 }
 
-// Return the depth of a node
-static int Depth(const CordRep* rep) {
-  if (rep->IsConcat()) {
-    return rep->concat()->depth();
-  } else {
-    return 0;
-  }
-}
-
-static void SetConcatChildren(CordRepConcat* concat, CordRep* left,
-                              CordRep* right) {
-  concat->left = left;
-  concat->right = right;
-
-  concat->length = left->length + right->length;
-  concat->set_depth(1 + std::max(Depth(left), Depth(right)));
-}
-
 // Create a concatenation of the specified nodes.
 // Does not change the refcounts of "left" and "right".
 // The returned node has a refcount of 1.
@@ -167,42 +101,15 @@ static CordRep* RawConcat(CordRep* left, CordRep* right) {
     CordRep::Unref(right);
     return left;
   }
-
-  CordRepConcat* rep = new CordRepConcat();
-  rep->tag = cord_internal::CONCAT;
-  SetConcatChildren(rep, left, right);
-
-  return rep;
+  ABSL_INTERNAL_LOG(FATAL, "CordRepConcat is no longer supported");
+  return nullptr;
 }
 
 static CordRep* Concat(CordRep* left, CordRep* right) {
   CordRep* rep = RawConcat(left, right);
-  if (rep != nullptr && !IsRootBalanced(rep)) {
-    rep = Rebalance(rep);
-  }
   return VerifyTree(rep);
 }
 
-// Make a balanced tree out of an array of leaf nodes.
-static CordRep* MakeBalancedTree(CordRep** reps, size_t n) {
-  // Make repeated passes over the array, merging adjacent pairs
-  // until we are left with just a single node.
-  while (n > 1) {
-    size_t dst = 0;
-    for (size_t src = 0; src < n; src += 2) {
-      if (src + 1 < n) {
-        reps[dst] = Concat(reps[src], reps[src + 1]);
-      } else {
-        reps[dst] = reps[src];
-      }
-      dst++;
-    }
-    n = dst;
-  }
-
-  return reps[0];
-}
-
 static CordRepFlat* CreateFlat(const char* data, size_t length,
                                size_t alloc_hint) {
   CordRepFlat* flat = CordRepFlat::New(length + alloc_hint);
@@ -228,21 +135,7 @@ static CordRep* NewBtree(const char* data, size_t length, size_t alloc_hint) {
 // The returned node has a refcount of 1.
 static CordRep* NewTree(const char* data, size_t length, size_t alloc_hint) {
   if (length == 0) return nullptr;
-  if (btree_enabled()) {
-    return NewBtree(data, length, alloc_hint);
-  }
-  absl::FixedArray<CordRep*> reps((length - 1) / kMaxFlatLength + 1);
-  size_t n = 0;
-  do {
-    const size_t len = std::min(length, kMaxFlatLength);
-    CordRepFlat* rep = CordRepFlat::New(len + alloc_hint);
-    rep->length = len;
-    memcpy(rep->Data(), data, len);
-    reps[n++] = VerifyTree(rep);
-    data += len;
-    length -= len;
-  } while (length != 0);
-  return MakeBalancedTree(reps.data(), n);
+  return NewBtree(data, length, alloc_hint);
 }
 
 namespace cord_internal {
@@ -350,11 +243,7 @@ void Cord::InlineRep::AppendTreeToInlined(CordRep* tree,
   assert(!is_tree());
   if (!data_.is_empty()) {
     CordRepFlat* flat = MakeFlatWithExtraCapacity(0);
-    if (btree_enabled()) {
-      tree = CordRepBtree::Append(CordRepBtree::Create(flat), tree);
-    } else {
-      tree = Concat(flat, tree);
-    }
+    tree = CordRepBtree::Append(CordRepBtree::Create(flat), tree);
   }
   EmplaceTree(tree, method);
 }
@@ -362,11 +251,7 @@ void Cord::InlineRep::AppendTreeToInlined(CordRep* tree,
 void Cord::InlineRep::AppendTreeToTree(CordRep* tree, MethodIdentifier method) {
   assert(is_tree());
   const CordzUpdateScope scope(data_.cordz_info(), method);
-  if (btree_enabled()) {
-    tree = CordRepBtree::Append(ForceBtree(data_.as_tree()), tree);
-  } else {
-    tree = Concat(cord_internal::RemoveCrcNode(data_.as_tree()), tree);
-  }
+  tree = CordRepBtree::Append(ForceBtree(data_.as_tree()), tree);
   SetTree(tree, scope);
 }
 
@@ -386,11 +271,7 @@ void Cord::InlineRep::PrependTreeToInlined(CordRep* tree,
   assert(!is_tree());
   if (!data_.is_empty()) {
     CordRepFlat* flat = MakeFlatWithExtraCapacity(0);
-    if (btree_enabled()) {
-      tree = CordRepBtree::Prepend(CordRepBtree::Create(flat), tree);
-    } else {
-      tree = Concat(tree, flat);
-    }
+    tree = CordRepBtree::Prepend(CordRepBtree::Create(flat), tree);
   }
   EmplaceTree(tree, method);
 }
@@ -399,11 +280,7 @@ void Cord::InlineRep::PrependTreeToTree(CordRep* tree,
                                         MethodIdentifier method) {
   assert(is_tree());
   const CordzUpdateScope scope(data_.cordz_info(), method);
-  if (btree_enabled()) {
-    tree = CordRepBtree::Prepend(ForceBtree(data_.as_tree()), tree);
-  } else {
-    tree = Concat(tree, cord_internal::RemoveCrcNode(data_.as_tree()));
-  }
+  tree = CordRepBtree::Prepend(ForceBtree(data_.as_tree()), tree);
   SetTree(tree, scope);
 }
 
@@ -433,12 +310,7 @@ static inline bool PrepareAppendRegion(CordRep* root, char** region,
     }
   }
 
-  // Search down the right-hand path for a non-full FLAT node.
   CordRep* dst = root;
-  while (dst->IsConcat() && dst->refcount.IsOne()) {
-    dst = dst->concat()->right;
-  }
-
   if (!dst->IsFlat() || !dst->refcount.IsOne()) {
     *region = nullptr;
     *size = 0;
@@ -453,12 +325,7 @@ static inline bool PrepareAppendRegion(CordRep* root, char** region,
     return false;
   }
 
-  size_t size_increase = std::min(capacity - in_use, max_length);
-
-  // We need to update the length fields for all nodes, including the leaf node.
-  for (CordRep* rep = root; rep != dst; rep = rep->concat()->right) {
-    rep->length += size_increase;
-  }
+  const size_t size_increase = std::min(capacity - in_use, max_length);
   dst->length += size_increase;
 
   *region = dst->flat()->Data() + in_use;
@@ -627,27 +494,11 @@ void Cord::InlineRep::AppendArray(absl::string_view src,
     return;
   }
 
-  if (btree_enabled()) {
-    // TODO(b/192061034): keep legacy 10% growth rate: consider other rates.
-    rep = ForceBtree(rep);
-    const size_t min_growth = std::max<size_t>(rep->length / 10, src.size());
-    rep = CordRepBtree::Append(rep->btree(), src, min_growth - src.size());
-  } else {
-    // Use new block(s) for any remaining bytes that were not handled above.
-    // Alloc extra memory only if the right child of the root of the new tree
-    // is going to be a FLAT node, which will permit further inplace appends.
-    size_t length = src.size();
-    if (src.size() < kMaxFlatLength) {
-      // The new length is either
-      // - old size + 10%
-      // - old_size + src.size()
-      // This will cause a reasonable conservative step-up in size that is
-      // still large enough to avoid excessive amounts of small fragments
-      // being added.
-      length = std::max<size_t>(rep->length / 10, src.size());
-    }
-    rep = Concat(rep, NewTree(src.data(), src.size(), length - src.size()));
-  }
+  // TODO(b/192061034): keep legacy 10% growth rate: consider other rates.
+  rep = ForceBtree(rep);
+  const size_t min_growth = std::max<size_t>(rep->length / 10, src.size());
+  rep = CordRepBtree::Append(rep->btree(), src, min_growth - src.size());
+
   CommitTree(root, rep, scope, method);
 }
 
@@ -779,18 +630,6 @@ static CordRep* RemovePrefixFrom(CordRep* node, size_t n) {
   absl::InlinedVector<CordRep*, kInlinedVectorSize> rhs_stack;
 
   assert(!node->IsCrc());
-  while (node->IsConcat()) {
-    assert(n <= node->length);
-    if (n < node->concat()->left->length) {
-      // Push right to stack, descend left.
-      rhs_stack.push_back(node->concat()->right);
-      node = node->concat()->left;
-    } else {
-      // Drop left, descend right.
-      n -= node->concat()->left->length;
-      node = node->concat()->right;
-    }
-  }
   assert(n <= node->length);
 
   if (n == 0) {
@@ -822,19 +661,6 @@ static CordRep* RemoveSuffixFrom(CordRep* node, size_t n) {
   bool inplace_ok = node->refcount.IsOne();
   assert(!node->IsCrc());
 
-  while (node->IsConcat()) {
-    assert(n <= node->length);
-    if (n < node->concat()->right->length) {
-      // Push left to stack, descend right.
-      lhs_stack.push_back(node->concat()->left);
-      node = node->concat()->right;
-    } else {
-      // Drop right, descend left.
-      n -= node->concat()->right->length;
-      node = node->concat()->left;
-    }
-    inplace_ok = inplace_ok && node->refcount.IsOne();
-  }
   assert(n <= node->length);
 
   if (n == 0) {
@@ -936,22 +762,12 @@ static CordRep* NewSubRange(CordRep* node, size_t pos, size_t n) {
       results.push_back(Concat(left, right));
     } else if (pos == 0 && n == node->length) {
       results.push_back(CordRep::Ref(node));
-    } else if (!node->IsConcat()) {
+    } else {
       if (node->IsSubstring()) {
         pos += node->substring()->start;
         node = node->substring()->child;
       }
       results.push_back(NewSubstring(CordRep::Ref(node), pos, n));
-    } else if (pos + n <= node->concat()->left->length) {
-      todo.push_back(SubRange(node->concat()->left, pos, n));
-    } else if (pos >= node->concat()->left->length) {
-      pos -= node->concat()->left->length;
-      todo.push_back(SubRange(node->concat()->right, pos, n));
-    } else {
-      size_t left_n = node->concat()->left->length - pos;
-      todo.push_back(SubRange(nullptr, 0, 0));  // Concat()
-      todo.push_back(SubRange(node->concat()->right, 0, n - left_n));
-      todo.push_back(SubRange(node->concat()->left, pos, left_n));
     }
   } while (!todo.empty());
   assert(results.size() == 1);
@@ -999,147 +815,6 @@ Cord Cord::Subcord(size_t pos, size_t new_size) const {
 }
 
 // --------------------------------------------------------------------
-// Balancing
-
-class CordForest {
- public:
-  explicit CordForest(size_t length)
-      : root_length_(length), trees_(kMinLengthSize, nullptr) {}
-
-  void Build(CordRep* cord_root) {
-    std::vector<CordRep*> pending = {cord_root};
-    assert(cord_root->IsConcat());
-
-    while (!pending.empty()) {
-      CordRep* node = pending.back();
-      pending.pop_back();
-      CheckNode(node);
-      if (ABSL_PREDICT_FALSE(!node->IsConcat())) {
-        AddNode(node);
-        continue;
-      }
-
-      CordRepConcat* concat_node = node->concat();
-      if (concat_node->depth() >= kMinLengthSize ||
-          concat_node->length < min_length[concat_node->depth()]) {
-        pending.push_back(concat_node->right);
-        pending.push_back(concat_node->left);
-
-        if (concat_node->refcount.IsOne()) {
-          concat_node->left = concat_freelist_;
-          concat_freelist_ = concat_node;
-        } else {
-          CordRep::Ref(concat_node->right);
-          CordRep::Ref(concat_node->left);
-          CordRep::Unref(concat_node);
-        }
-      } else {
-        AddNode(node);
-      }
-    }
-  }
-
-  CordRep* ConcatNodes() {
-    CordRep* sum = nullptr;
-    for (auto* node : trees_) {
-      if (node == nullptr) continue;
-
-      sum = PrependNode(node, sum);
-      root_length_ -= node->length;
-      if (root_length_ == 0) break;
-    }
-    ABSL_INTERNAL_CHECK(sum != nullptr, "Failed to locate sum node");
-    return VerifyTree(sum);
-  }
-
- private:
-  CordRep* AppendNode(CordRep* node, CordRep* sum) {
-    return (sum == nullptr) ? node : MakeConcat(sum, node);
-  }
-
-  CordRep* PrependNode(CordRep* node, CordRep* sum) {
-    return (sum == nullptr) ? node : MakeConcat(node, sum);
-  }
-
-  void AddNode(CordRep* node) {
-    CordRep* sum = nullptr;
-
-    // Collect together everything with which we will merge with node
-    int i = 0;
-    for (; node->length > min_length[i + 1]; ++i) {
-      auto& tree_at_i = trees_[i];
-
-      if (tree_at_i == nullptr) continue;
-      sum = PrependNode(tree_at_i, sum);
-      tree_at_i = nullptr;
-    }
-
-    sum = AppendNode(node, sum);
-
-    // Insert sum into appropriate place in the forest
-    for (; sum->length >= min_length[i]; ++i) {
-      auto& tree_at_i = trees_[i];
-      if (tree_at_i == nullptr) continue;
-
-      sum = MakeConcat(tree_at_i, sum);
-      tree_at_i = nullptr;
-    }
-
-    // min_length[0] == 1, which means sum->length >= min_length[0]
-    assert(i > 0);
-    trees_[i - 1] = sum;
-  }
-
-  // Make concat node trying to resue existing CordRepConcat nodes we
-  // already collected in the concat_freelist_.
-  CordRep* MakeConcat(CordRep* left, CordRep* right) {
-    if (concat_freelist_ == nullptr) return RawConcat(left, right);
-
-    CordRepConcat* rep = concat_freelist_;
-    if (concat_freelist_->left == nullptr) {
-      concat_freelist_ = nullptr;
-    } else {
-      concat_freelist_ = concat_freelist_->left->concat();
-    }
-    SetConcatChildren(rep, left, right);
-
-    return rep;
-  }
-
-  static void CheckNode(CordRep* node) {
-    ABSL_INTERNAL_CHECK(node->length != 0u, "");
-    if (node->IsConcat()) {
-      ABSL_INTERNAL_CHECK(node->concat()->left != nullptr, "");
-      ABSL_INTERNAL_CHECK(node->concat()->right != nullptr, "");
-      ABSL_INTERNAL_CHECK(node->length == (node->concat()->left->length +
-                                           node->concat()->right->length),
-                          "");
-    }
-  }
-
-  size_t root_length_;
-
-  // use an inlined vector instead of a flat array to get bounds checking
-  absl::InlinedVector<CordRep*, kInlinedVectorSize> trees_;
-
-  // List of concat nodes we can re-use for Cord balancing.
-  CordRepConcat* concat_freelist_ = nullptr;
-};
-
-static CordRep* Rebalance(CordRep* node) {
-  VerifyTree(node);
-  assert(node->IsConcat());
-
-  if (node->length == 0) {
-    return nullptr;
-  }
-
-  CordForest forest(node->length);
-  forest.Build(node);
-  return forest.ConcatNodes();
-}
-
-// --------------------------------------------------------------------
 // Comparators
 
 namespace {
@@ -1203,11 +878,6 @@ inline absl::string_view Cord::InlineRep::FindFlatStartPiece() const {
     return tree->Data(tree->begin());
   }
 
-  // Walk down the left branches until we hit a non-CONCAT node.
-  while (node->IsConcat()) {
-    node = node->concat()->left;
-  }
-
   // Get the child node if we encounter a SUBSTRING.
   size_t offset = 0;
   size_t length = node->length;
@@ -1436,13 +1106,6 @@ Cord::ChunkIterator& Cord::ChunkIterator::AdvanceStack() {
   CordRep* node = stack_of_right_children.back();
   stack_of_right_children.pop_back();
 
-  // Walk down the left branches until we hit a non-CONCAT node. Save the
-  // right children to the stack for subsequent traversal.
-  while (node->IsConcat()) {
-    stack_of_right_children.push_back(node->concat()->right);
-    node = node->concat()->left;
-  }
-
   // Get the child node if we encounter a SUBSTRING.
   size_t offset = 0;
   size_t length = node->length;
@@ -1557,22 +1220,6 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) {
     return subcord;
   }
 
-  // Walk down the appropriate branches until we hit a non-CONCAT node. Save the
-  // right children to the stack for subsequent traversal.
-  while (node->IsConcat()) {
-    if (node->concat()->left->length > n) {
-      // Push right, descend left.
-      stack_of_right_children.push_back(node->concat()->right);
-      node = node->concat()->left;
-    } else {
-      // Read left, descend right.
-      subnode = Concat(subnode, CordRep::Ref(node->concat()->left));
-      n -= node->concat()->left->length;
-      bytes_remaining_ -= node->concat()->left->length;
-      node = node->concat()->right;
-    }
-  }
-
   // Get the child node if we encounter a SUBSTRING.
   size_t offset = 0;
   size_t length = node->length;
@@ -1630,21 +1277,6 @@ void Cord::ChunkIterator::AdvanceBytesSlowPath(size_t n) {
     return;
   }
 
-  // Walk down the appropriate branches until we hit a non-CONCAT node. Save the
-  // right children to the stack for subsequent traversal.
-  while (node->IsConcat()) {
-    if (node->concat()->left->length > n) {
-      // Push right, descend left.
-      stack_of_right_children.push_back(node->concat()->right);
-      node = node->concat()->left;
-    } else {
-      // Skip left, descend right.
-      n -= node->concat()->left->length;
-      bytes_remaining_ -= node->concat()->left->length;
-      node = node->concat()->right;
-    }
-  }
-
   // Get the child node if we encounter a SUBSTRING.
   size_t offset = 0;
   size_t length = node->length;
@@ -1681,16 +1313,6 @@ char Cord::operator[](size_t i) const {
     } else if (rep->IsExternal()) {
       // Get the "i"th character from the external array.
       return rep->external()->base[offset];
-    } else if (rep->IsConcat()) {
-      // Recursively branch to the side of the concatenation that the "i"th
-      // character is on.
-      size_t left_length = rep->concat()->left->length;
-      if (offset < left_length) {
-        rep = rep->concat()->left;
-      } else {
-        offset -= left_length;
-        rep = rep->concat()->right;
-      }
     } else {
       // This must be a substring a node, so bypass it to get to the child.
       assert(rep->IsSubstring());
@@ -1772,43 +1394,13 @@ absl::string_view Cord::FlattenSlowPath() {
     return;
   }
 
-  int stack_pos = 0;
-  constexpr int stack_max = 128;
-  // Stack of right branches for tree traversal
-  absl::cord_internal::CordRep* stack[stack_max];
+  // This is a leaf node, so invoke our callback.
   absl::cord_internal::CordRep* current_node = cord_internal::SkipCrcNode(rep);
-  while (true) {
-    if (current_node->IsConcat()) {
-      if (stack_pos == stack_max) {
-        // There's no more room on our stack array to add another right branch,
-        // and the idea is to avoid allocations, so call this function
-        // recursively to navigate this subtree further.  (This is not something
-        // we expect to happen in practice).
-        ForEachChunkAux(current_node, callback);
-
-        // Pop the next right branch and iterate.
-        current_node = stack[--stack_pos];
-        continue;
-      } else {
-        // Save the right branch for later traversal and continue down the left
-        // branch.
-        stack[stack_pos++] = current_node->concat()->right;
-        current_node = current_node->concat()->left;
-        continue;
-      }
-    }
-    // This is a leaf node, so invoke our callback.
-    absl::string_view chunk;
-    bool success = GetFlatAux(current_node, &chunk);
-    assert(success);
-    if (success) {
-      callback(chunk);
-    }
-    if (stack_pos == 0) {
-      // end of traversal
-      return;
-    }
-    current_node = stack[--stack_pos];
+  absl::string_view chunk;
+  bool success = GetFlatAux(current_node, &chunk);
+  assert(success);
+  if (success) {
+    callback(chunk);
   }
 }
 
@@ -1823,18 +1415,11 @@ static void DumpNode(CordRep* rep, bool include_data, std::ostream* os,
     *os << " [";
     if (include_data) *os << static_cast<void*>(rep);
     *os << "]";
-    *os << " " << (IsRootBalanced(rep) ? 'b' : 'u');
     *os << " " << std::setw(indent) << "";
     if (rep->IsCrc()) {
       *os << "CRC crc=" << rep->crc()->crc << "\n";
       indent += kIndentStep;
       rep = rep->crc()->child;
-    } else if (rep->IsConcat()) {
-      *os << "CONCAT depth=" << Depth(rep) << "\n";
-      indent += kIndentStep;
-      indents.push_back(indent);
-      stack.push_back(rep->concat()->right);
-      rep = rep->concat()->left;
     } else if (rep->IsSubstring()) {
       *os << "SUBSTRING @ " << rep->substring()->start << "\n";
       indent += kIndentStep;
@@ -1871,7 +1456,7 @@ static std::string ReportError(CordRep* root, CordRep* node) {
 }
 
 static bool VerifyNode(CordRep* root, CordRep* start_node,
-                       bool full_validation) {
+                       bool /* full_validation */) {
   absl::InlinedVector<CordRep*, 2> worklist;
   worklist.push_back(start_node);
   do {
@@ -1884,19 +1469,7 @@ static bool VerifyNode(CordRep* root, CordRep* start_node,
       ABSL_INTERNAL_CHECK(!node->IsCrc(), ReportError(root, node));
     }
 
-    if (node->IsConcat()) {
-      ABSL_INTERNAL_CHECK(node->concat()->left != nullptr,
-                          ReportError(root, node));
-      ABSL_INTERNAL_CHECK(node->concat()->right != nullptr,
-                          ReportError(root, node));
-      ABSL_INTERNAL_CHECK((node->length == node->concat()->left->length +
-                                               node->concat()->right->length),
-                          ReportError(root, node));
-      if (full_validation) {
-        worklist.push_back(node->concat()->right);
-        worklist.push_back(node->concat()->left);
-      }
-    } else if (node->IsFlat()) {
+    if (node->IsFlat()) {
       ABSL_INTERNAL_CHECK(node->length <= node->flat()->Capacity(),
                           ReportError(root, node));
     } else if (node->IsExternal()) {
@@ -1937,7 +1510,6 @@ uint8_t CordTestAccess::LengthToTag(size_t s) {
   ABSL_INTERNAL_CHECK(s <= kMaxFlatLength, absl::StrCat("Invalid length ", s));
   return cord_internal::AllocatedSizeToTag(s + cord_internal::kFlatOverhead);
 }
-size_t CordTestAccess::SizeofCordRepConcat() { return sizeof(CordRepConcat); }
 size_t CordTestAccess::SizeofCordRepExternal() {
   return sizeof(CordRepExternal);
 }
diff --git a/absl/strings/cord.h b/absl/strings/cord.h
index 49d51da2..7f34ef48 100644
--- a/absl/strings/cord.h
+++ b/absl/strings/cord.h
@@ -1553,7 +1553,6 @@ class CordTestAccess {
  public:
   static size_t FlatOverhead();
   static size_t MaxFlatLength();
-  static size_t SizeofCordRepConcat();
   static size_t SizeofCordRepExternal();
   static size_t SizeofCordRepSubstring();
   static size_t FlatTagToLength(uint8_t tag);
diff --git a/absl/strings/cord_analysis.cc b/absl/strings/cord_analysis.cc
index c0d9ea79..3fa15b01 100644
--- a/absl/strings/cord_analysis.cc
+++ b/absl/strings/cord_analysis.cc
@@ -128,45 +128,6 @@ void AnalyzeDataEdge(CordRepRef<mode> rep, RawUsage<mode>& raw_usage) {
   raw_usage.Add(size, rep);
 }
 
-// Computes the memory size of the provided Concat tree.
-template <Mode mode>
-void AnalyzeConcat(CordRepRef<mode> rep, RawUsage<mode>& raw_usage) {
-  absl::InlinedVector<CordRepRef<mode>, 47> pending;
-
-  while (rep.rep != nullptr) {
-    const CordRepConcat* concat = rep.rep->concat();
-    CordRepRef<mode> left = rep.Child(concat->left);
-    CordRepRef<mode> right = rep.Child(concat->right);
-
-    raw_usage.Add(sizeof(CordRepConcat), rep);
-
-    switch ((IsDataEdge(left.rep) ? 1 : 0) | (IsDataEdge(right.rep) ? 2 : 0)) {
-      case 0:  // neither left or right are data edges
-        rep = left;
-        pending.push_back(right);
-        break;
-      case 1:  // only left is a data edge
-        AnalyzeDataEdge(left, raw_usage);
-        rep = right;
-        break;
-      case 2:  // only right is a data edge
-        AnalyzeDataEdge(right, raw_usage);
-        rep = left;
-        break;
-      case 3:  // left and right are data edges
-        AnalyzeDataEdge(right, raw_usage);
-        AnalyzeDataEdge(left, raw_usage);
-        if (!pending.empty()) {
-          rep = pending.back();
-          pending.pop_back();
-        } else {
-          rep.rep = nullptr;
-        }
-        break;
-    }
-  }
-}
-
 // Computes the memory size of the provided Ring tree.
 template <Mode mode>
 void AnalyzeRing(CordRepRef<mode> rep, RawUsage<mode>& raw_usage) {
@@ -211,8 +172,6 @@ size_t GetEstimatedUsage(const CordRep* rep) {
     AnalyzeDataEdge(repref, raw_usage);
   } else if (repref.rep->tag == BTREE) {
     AnalyzeBtree(repref, raw_usage);
-  } else if (repref.rep->IsConcat()) {
-    AnalyzeConcat(repref, raw_usage);
   } else if (repref.rep->tag == RING) {
     AnalyzeRing(repref, raw_usage);
   } else {
diff --git a/absl/strings/internal/cord_internal.cc b/absl/strings/internal/cord_internal.cc
index 75544191..06119350 100644
--- a/absl/strings/internal/cord_internal.cc
+++ b/absl/strings/internal/cord_internal.cc
@@ -36,53 +36,31 @@ ABSL_CONST_INIT std::atomic<bool> cord_btree_exhaustive_validation(false);
 void CordRep::Destroy(CordRep* rep) {
   assert(rep != nullptr);
 
-  absl::InlinedVector<CordRep*, Constants::kInlinedVectorSize> pending;
   while (true) {
     assert(!rep->refcount.IsImmortal());
-    if (rep->IsConcat()) {
-      CordRepConcat* rep_concat = rep->concat();
-      CordRep* right = rep_concat->right;
-      if (!right->refcount.Decrement()) {
-        pending.push_back(right);
-      }
-      CordRep* left = rep_concat->left;
-      delete rep_concat;
-      rep = nullptr;
-      if (!left->refcount.Decrement()) {
-        rep = left;
-        continue;
-      }
-    } else if (rep->tag == BTREE) {
+    if (rep->tag == BTREE) {
       CordRepBtree::Destroy(rep->btree());
-      rep = nullptr;
+      return;
     } else if (rep->tag == RING) {
       CordRepRing::Destroy(rep->ring());
-      rep = nullptr;
+      return;
     } else if (rep->tag == EXTERNAL) {
       CordRepExternal::Delete(rep);
-      rep = nullptr;
+      return;
     } else if (rep->tag == SUBSTRING) {
       CordRepSubstring* rep_substring = rep->substring();
-      CordRep* child = rep_substring->child;
+      rep = rep_substring->child;
       delete rep_substring;
-      rep = nullptr;
-      if (!child->refcount.Decrement()) {
-        rep = child;
-        continue;
+      if (rep->refcount.Decrement()) {
+        return;
       }
     } else if (rep->tag == CRC) {
       CordRepCrc::Destroy(rep->crc());
-      rep = nullptr;
+      return;
     } else {
+      assert(rep->IsFlat());
       CordRepFlat::Delete(rep);
-      rep = nullptr;
-    }
-
-    if (!pending.empty()) {
-      rep = pending.back();
-      pending.pop_back();
-    } else {
-      break;
+      return;
     }
   }
 }
diff --git a/absl/strings/internal/cord_internal.h b/absl/strings/internal/cord_internal.h
index b9ecbba6..8db6aa6d 100644
--- a/absl/strings/internal/cord_internal.h
+++ b/absl/strings/internal/cord_internal.h
@@ -171,7 +171,7 @@ class CordRepBtree;
 
 // Various representations that we allow
 enum CordRepKind {
-  CONCAT = 0,
+  UNUSED_0 = 0,
   SUBSTRING = 1,
   CRC = 2,
   BTREE = 3,
@@ -239,7 +239,6 @@ struct CordRep {
 
   // Returns true if this instance's tag matches the requested type.
   constexpr bool IsRing() const { return tag == RING; }
-  constexpr bool IsConcat() const { return tag == CONCAT; }
   constexpr bool IsSubstring() const { return tag == SUBSTRING; }
   constexpr bool IsCrc() const { return tag == CRC; }
   constexpr bool IsExternal() const { return tag == EXTERNAL; }
@@ -248,8 +247,6 @@ struct CordRep {
 
   inline CordRepRing* ring();
   inline const CordRepRing* ring() const;
-  inline CordRepConcat* concat();
-  inline const CordRepConcat* concat() const;
   inline CordRepSubstring* substring();
   inline const CordRepSubstring* substring() const;
   inline CordRepCrc* crc();
@@ -276,21 +273,6 @@ struct CordRep {
   static inline void Unref(CordRep* rep);
 };
 
-struct CordRepConcat : public CordRep {
-  CordRep* left;
-  CordRep* right;
-
-  uint8_t depth() const { return storage[0]; }
-  void set_depth(uint8_t depth) { storage[0] = depth; }
-
-  // Extracts the right-most flat in the provided concat tree if the entire path
-  // to that flat is not shared, and the flat has the requested extra capacity.
-  // Returns the (potentially new) top level tree node and the extracted flat,
-  // or {tree, nullptr} if no flat was extracted.
-  static ExtractResult ExtractAppendBuffer(CordRepConcat* tree,
-                                           size_t extra_capacity);
-};
-
 struct CordRepSubstring : public CordRep {
   size_t start;  // Starting offset of substring in child
   CordRep* child;
@@ -569,16 +551,6 @@ class InlineData {
 
 static_assert(sizeof(InlineData) == kMaxInline + 1, "");
 
-inline CordRepConcat* CordRep::concat() {
-  assert(IsConcat());
-  return static_cast<CordRepConcat*>(this);
-}
-
-inline const CordRepConcat* CordRep::concat() const {
-  assert(IsConcat());
-  return static_cast<const CordRepConcat*>(this);
-}
-
 inline CordRepSubstring* CordRep::substring() {
   assert(IsSubstring());
   return static_cast<CordRepSubstring*>(this);
diff --git a/absl/strings/internal/cord_rep_concat.cc b/absl/strings/internal/cord_rep_concat.cc
deleted file mode 100644
index 3457b55c..00000000
--- a/absl/strings/internal/cord_rep_concat.cc
+++ /dev/null
@@ -1,63 +0,0 @@
-// 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.
-// 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 <cstdint>
-
-#include "absl/base/config.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 {
-
-CordRepConcat::ExtractResult CordRepConcat::ExtractAppendBuffer(
-    CordRepConcat* tree, size_t extra_capacity) {
-  absl::InlinedVector<CordRepConcat*, kInlinedVectorSize> stack;
-  CordRepConcat* concat = tree;
-  CordRep* rep = concat->right;
-
-  // Dive down the tree, making sure no edges are shared
-  while (concat->refcount.IsOne() && rep->IsConcat()) {
-    stack.push_back(concat);
-    concat = rep->concat();
-    rep = concat->right;
-  }
-  // Validate we ended on a non shared flat.
-  if (concat->refcount.IsOne() && rep->IsFlat() &&
-      rep->refcount.IsOne()) {
-    // Verify it has at least the requested extra capacity
-    CordRepFlat* flat = rep->flat();
-    size_t remaining = flat->Capacity() - flat->length;
-    if (extra_capacity > remaining) return {tree, nullptr};
-
-    // Check if we have a parent to adjust, or if we must return the left node.
-    rep = concat->left;
-    if (!stack.empty()) {
-      stack.back()->right = rep;
-      for (CordRepConcat* parent : stack) {
-        parent->length -= flat->length;
-      }
-      rep = tree;
-    }
-    delete concat;
-    return {rep, flat};
-  }
-  return {tree, nullptr};
-}
-
-}  // namespace cord_internal
-ABSL_NAMESPACE_END
-}  // namespace absl
diff --git a/absl/strings/internal/cord_rep_consume.cc b/absl/strings/internal/cord_rep_consume.cc
index 253339be..20a55797 100644
--- a/absl/strings/internal/cord_rep_consume.cc
+++ b/absl/strings/internal/cord_rep_consume.cc
@@ -40,88 +40,21 @@ CordRep* ClipSubstring(CordRepSubstring* substring) {
   return child;
 }
 
-// Unrefs the provided `concat`, and returns `{concat->left, concat->right}`
-// Adds or assumes a reference on `concat->left` and `concat->right`.
-// Returns an array of 2 elements containing the left and right nodes.
-std::array<CordRep*, 2> ClipConcat(CordRepConcat* concat) {
-  std::array<CordRep*, 2> result{concat->left, concat->right};
-  if (concat->refcount.IsOne()) {
-    delete concat;
-  } else {
-    CordRep::Ref(result[0]);
-    CordRep::Ref(result[1]);
-    CordRep::Unref(concat);
-  }
-  return result;
-}
+}  // namespace
 
-void Consume(bool forward, CordRep* rep, ConsumeFn consume_fn) {
+void Consume(CordRep* rep, ConsumeFn consume_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->IsConcat()) {
-      std::array<CordRep*, 2> res = ClipConcat(rep->concat());
-      CordRep* left = res[0];
-      CordRep* right = res[1];
-
-      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 (forward) {
-        stack.push_back({right, 0, length_right});
-        rep = left;
-        length = length_left;
-      } else {
-        stack.push_back({left, offset, length_left});
-        rep = right;
-        offset = 0;
-        length = length_right;
-      }
-    } else if (rep->tag == SUBSTRING) {
-      offset += rep->substring()->start;
-      rep = ClipSubstring(rep->substring());
-    } else {
-      consume_fn(rep, offset, length);
-      if (stack.empty()) return;
-
-      rep = stack.back().rep;
-      offset = stack.back().offset;
-      length = stack.back().length;
-      stack.pop_back();
-    }
+  if (rep->tag == SUBSTRING) {
+    offset += rep->substring()->start;
+    rep = ClipSubstring(rep->substring());
   }
-}
-
-}  // namespace
-
-void Consume(CordRep* rep, ConsumeFn consume_fn) {
-  return Consume(true, rep, std::move(consume_fn));
+  consume_fn(rep, offset, length);
 }
 
 void ReverseConsume(CordRep* rep, ConsumeFn consume_fn) {
-  return Consume(false, rep, std::move(consume_fn));
+  return Consume(rep, std::move(consume_fn));
 }
 
 }  // namespace cord_internal
diff --git a/absl/strings/internal/cord_rep_flat.h b/absl/strings/internal/cord_rep_flat.h
index ae8b3a2a..e3e27fcd 100644
--- a/absl/strings/internal/cord_rep_flat.h
+++ b/absl/strings/internal/cord_rep_flat.h
@@ -73,9 +73,11 @@ static_assert(AllocatedSizeToTagUnchecked(kMinFlatSize) == FLAT, "");
 static_assert(AllocatedSizeToTagUnchecked(kMaxLargeFlatSize) == MAX_FLAT_TAG,
               "");
 
-// Helper functions for rounded div, and rounding to exact sizes.
-constexpr size_t DivUp(size_t n, size_t m) { return (n + m - 1) / m; }
-constexpr size_t RoundUp(size_t n, size_t m) { return DivUp(n, m) * m; }
+// RoundUp logically performs `((n + m - 1) / m) * m` to round up to the nearest
+// multiple of `m`, optimized for the invariant that `m` is a power of 2.
+constexpr size_t RoundUp(size_t n, size_t m) {
+  return (n + m - 1) & (0 - m);
+}
 
 // Returns the size to the nearest equal or larger value that can be
 // expressed exactly as a tag value.
diff --git a/absl/strings/internal/cord_rep_test_util.h b/absl/strings/internal/cord_rep_test_util.h
index 692d7db5..18a0a195 100644
--- a/absl/strings/internal/cord_rep_test_util.h
+++ b/absl/strings/internal/cord_rep_test_util.h
@@ -114,9 +114,6 @@ inline void CordVisitReps(cord_internal::CordRep* rep, Fn&& fn) {
     for (cord_internal::CordRep* edge : rep->btree()->Edges()) {
       CordVisitReps(edge, fn);
     }
-  } else if (rep->IsConcat()) {
-    CordVisitReps(rep->concat()->left, fn);
-    CordVisitReps(rep->concat()->right, fn);
   }
 }
 
diff --git a/absl/strings/internal/cordz_info.cc b/absl/strings/internal/cordz_info.cc
index 24605260..c891d0ed 100644
--- a/absl/strings/internal/cordz_info.cc
+++ b/absl/strings/internal/cordz_info.cc
@@ -98,8 +98,6 @@ class CordRepAnalyzer {
         AnalyzeRing(repref);
       } else if (repref.rep->tag == BTREE) {
         AnalyzeBtree(repref);
-      } else if (repref.rep->IsConcat()) {
-        AnalyzeConcat(repref);
       } else {
         // We should have either a concat, btree, or ring node if not null.
         assert(false);
@@ -141,14 +139,6 @@ class CordRepAnalyzer {
     }
   };
 
-  // Returns `rr` if `rr.rep` is not null and a CONCAT type.
-  // Asserts that `rr.rep` is a concat node or null.
-  static RepRef AssertConcat(RepRef repref) {
-    const CordRep* rep = repref.rep;
-    assert(rep == nullptr || rep->IsConcat());
-    return (rep != nullptr && rep->IsConcat()) ? repref : RepRef{nullptr, 0};
-  }
-
   // Counts a flat of the provide allocated size
   void CountFlat(size_t size) {
     statistics_.node_count++;
@@ -201,34 +191,6 @@ class CordRepAnalyzer {
     return rep;
   }
 
-  // Analyzes the provided concat node in a flattened recursive way.
-  void AnalyzeConcat(RepRef rep) {
-    absl::InlinedVector<RepRef, 47> pending;
-
-    while (rep.rep != nullptr) {
-      const CordRepConcat* concat = rep.rep->concat();
-      RepRef left = rep.Child(concat->left);
-      RepRef right = rep.Child(concat->right);
-
-      statistics_.node_count++;
-      statistics_.node_counts.concat++;
-      memory_usage_.Add(sizeof(CordRepConcat), rep.refcount);
-
-      right = AssertConcat(CountLinearReps(right, memory_usage_));
-      rep = AssertConcat(CountLinearReps(left, memory_usage_));
-      if (rep.rep != nullptr) {
-        if (right.rep != nullptr) {
-          pending.push_back(right);
-        }
-      } else if (right.rep != nullptr) {
-        rep = right;
-      } else if (!pending.empty()) {
-        rep = pending.back();
-        pending.pop_back();
-      }
-    }
-  }
-
   // Analyzes the provided ring.
   void AnalyzeRing(RepRef rep) {
     statistics_.node_count++;
diff --git a/absl/strings/internal/cordz_info_statistics_test.cc b/absl/strings/internal/cordz_info_statistics_test.cc
index 40f93dd3..476c38d2 100644
--- a/absl/strings/internal/cordz_info_statistics_test.cc
+++ b/absl/strings/internal/cordz_info_statistics_test.cc
@@ -148,10 +148,6 @@ double FairShareImpl(CordRep* rep, size_t ref) {
     rep->ring()->ForEach([&](CordRepRing::index_type i) {
       self += FairShareImpl(rep->ring()->entry_child(i), 1);
     });
-  } else if (rep->IsConcat()) {
-    self = SizeOf(rep->concat());
-    children = FairShareImpl(rep->concat()->left, ref) +
-               FairShareImpl(rep->concat()->right, ref);
   } else {
     assert(false);
   }