Export of internal Abseil changes

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

Optimize substring logic now that CONCAT is removed

This CL adds a static Substring() method to CordRepSubstring, and implements substring logic in cord.cc in terms of the new function. This cleans up various helper functions and logic remaining from previous complex CONCAT logic that is no longer needed.

PiperOrigin-RevId: 431756805
Change-Id: I39c875b5af119916780e68598c7fc619fb2e8476

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

Allow macro expansion within ABSL_FLAG and ABSL_DECLARE_FLAG args

PiperOrigin-RevId: 431721184
Change-Id: I6e19713fb541205d796f940998db5ee25178d55e

--
1b328badd92304ed1c634f23e1c191be57b7bb15 by Laramie Leavitt <lar@google.com>:

Add #include for std:: types

PiperOrigin-RevId: 431546757
Change-Id: I75efbcd3c77e6f53e4db66494101d30d670d988e

--
e25323b299d4d3840218702860f537cdd2a3926f by Thomas Köppe <tkoeppe@google.com>:

Add hashing support for pointers to member.

Also add tests for function pointers to the existing "pointer" test.

PiperOrigin-RevId: 431067588
Change-Id: I3686010635d9fee34c47a418b72402e10737cdbc

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

Avoid use of std::pow in ChiSquare test.

PiperOrigin-RevId: 431015830
Change-Id: Idd767ff2f51009ee171de48757207b38330ffea3

--
28c359135d89061177958580fe4a7493802499cb by Laramie Leavitt <lar@google.com>:

Add #include <type_traits> for std::false_type

PiperOrigin-RevId: 431005757
Change-Id: I85a6a918778601e19512aaea744424cf39018521

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

#include <utility> for std::declval

PiperOrigin-RevId: 431004934
Change-Id: I295237b2d44e9a15e4083698ea121b68ce0a1bb7
GitOrigin-RevId: f0b7d230a90c82c6fee7adcb46a213d2582b6a7b

11 files changed, 188 insertions, 139 deletions

diff --git a/absl/flags/declare.h b/absl/flags/declare.h
index a791b667..d1437bb9 100644
--- a/absl/flags/declare.h
+++ b/absl/flags/declare.h
@@ -60,7 +60,11 @@ ABSL_NAMESPACE_END
 // The ABSL_DECLARE_FLAG(type, name) macro expands to:
 //
 //   extern absl::Flag<type> FLAGS_name;
-#define ABSL_DECLARE_FLAG(type, name)                        \
+#define ABSL_DECLARE_FLAG(type, name) ABSL_DECLARE_FLAG_INTERNAL(type, name)
+
+// Internal implementation of ABSL_DECLARE_FLAG to allow macro expansion of its
+// arguments. Clients must use ABSL_DECLARE_FLAG instead.
+#define ABSL_DECLARE_FLAG_INTERNAL(type, name)               \
   extern absl::Flag<type> FLAGS_##name;                      \
   namespace absl /* block flags in namespaces */ {}          \
   /* second redeclaration is to allow applying attributes */ \
diff --git a/absl/flags/flag.h b/absl/flags/flag.h
index 50106082..d2750b31 100644
--- a/absl/flags/flag.h
+++ b/absl/flags/flag.h
@@ -163,7 +163,6 @@ ABSL_NAMESPACE_END
 // Note: do not construct objects of type `absl::Flag<T>` directly. Only use the
 // `ABSL_FLAG()` macro for such construction.
 #define ABSL_FLAG(Type, name, default_value, help) \
-  extern ::absl::Flag<Type> FLAGS_##name;          \
   ABSL_FLAG_IMPL(Type, name, default_value, help)
 
 // ABSL_FLAG().OnUpdate()
@@ -266,6 +265,7 @@ ABSL_NAMESPACE_END
 // global name for FLAGS_no<flag_name> symbol, thus preventing the possibility
 // of defining two flags with names foo and nofoo.
 #define ABSL_FLAG_IMPL(Type, name, default_value, help)                       \
+  extern ::absl::Flag<Type> FLAGS_##name;                                     \
   namespace absl /* block flags in namespaces */ {}                           \
   ABSL_FLAG_IMPL_DECLARE_DEF_VAL_WRAPPER(name, Type, default_value)           \
   ABSL_FLAG_IMPL_DECLARE_HELP_WRAPPER(name, help)                             \
diff --git a/absl/flags/flag_test.cc b/absl/flags/flag_test.cc
index 6e974a5b..ced332d4 100644
--- a/absl/flags/flag_test.cc
+++ b/absl/flags/flag_test.cc
@@ -977,3 +977,16 @@ TEST_F(FlagTest, TesTypeWrappingEnum) {
   value = absl::GetFlag(FLAGS_test_enum_wrapper_flag);
   EXPECT_EQ(value.e, B);
 }
+
+// This is a compile test to ensure macros are expanded within ABSL_FLAG and
+// ABSL_DECLARE_FLAG.
+#define FLAG_NAME_MACRO(name) prefix_ ## name
+ABSL_DECLARE_FLAG(int, FLAG_NAME_MACRO(test_macro_named_flag));
+ABSL_FLAG(int, FLAG_NAME_MACRO(test_macro_named_flag), 0,
+          "Testing macro expansion within ABSL_FLAG");
+
+TEST_F(FlagTest, MacroWithinAbslFlag) {
+  EXPECT_EQ(absl::GetFlag(FLAGS_prefix_test_macro_named_flag), 0);
+  absl::SetFlag(&FLAGS_prefix_test_macro_named_flag, 1);
+  EXPECT_EQ(absl::GetFlag(FLAGS_prefix_test_macro_named_flag), 1);
+}
diff --git a/absl/hash/hash_test.cc b/absl/hash/hash_test.cc
index 39ff8f52..ffa45e6e 100644
--- a/absl/hash/hash_test.cc
+++ b/absl/hash/hash_test.cc
@@ -185,6 +185,8 @@ TEST(HashValueTest, FloatingPoint) {
 
 TEST(HashValueTest, Pointer) {
   EXPECT_TRUE((is_hashable<int*>::value));
+  EXPECT_TRUE((is_hashable<int(*)(char, float)>::value));
+  EXPECT_TRUE((is_hashable<void(*)(int, int, ...)>::value));
 
   int i;
   int* ptr = &i;
@@ -224,6 +226,85 @@ TEST(HashValueTest, PointerAlignment) {
   }
 }
 
+TEST(HashValueTest, PointerToMember) {
+  struct Bass {
+    void q() {}
+  };
+
+  struct A : Bass {
+    virtual ~A() = default;
+    virtual void vfa() {}
+
+    static auto pq() -> void (A::*)() { return &A::q; }
+  };
+
+  struct B : Bass {
+    virtual ~B() = default;
+    virtual void vfb() {}
+
+    static auto pq() -> void (B::*)() { return &B::q; }
+  };
+
+  struct Foo : A, B {
+    void f1() {}
+    void f2() const {}
+
+    int g1() & { return 0; }
+    int g2() const & { return 0; }
+    int g3() && { return 0; }
+    int g4() const && { return 0; }
+
+    int h1() & { return 0; }
+    int h2() const & { return 0; }
+    int h3() && { return 0; }
+    int h4() const && { return 0; }
+
+    int a;
+    int b;
+
+    const int c = 11;
+    const int d = 22;
+  };
+
+  EXPECT_TRUE((is_hashable<float Foo::*>::value));
+  EXPECT_TRUE((is_hashable<double (Foo::*)(int, int)&&>::value));
+
+  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(
+      std::make_tuple(&Foo::a, &Foo::b, static_cast<int Foo::*>(nullptr))));
+
+  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(
+      std::make_tuple(&Foo::c, &Foo::d, static_cast<const int Foo::*>(nullptr),
+                      &Foo::a, &Foo::b)));
+
+  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
+      &Foo::f1, static_cast<void (Foo::*)()>(nullptr))));
+
+  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
+      &Foo::f2, static_cast<void (Foo::*)() const>(nullptr))));
+
+  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
+      &Foo::g1, &Foo::h1, static_cast<int (Foo::*)() &>(nullptr))));
+
+  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
+      &Foo::g2, &Foo::h2, static_cast<int (Foo::*)() const &>(nullptr))));
+
+  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
+      &Foo::g3, &Foo::h3, static_cast<int (Foo::*)() &&>(nullptr))));
+
+  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
+      &Foo::g4, &Foo::h4, static_cast<int (Foo::*)() const &&>(nullptr))));
+
+  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(
+      std::make_tuple(static_cast<void (Foo::*)()>(&Foo::vfa),
+                      static_cast<void (Foo::*)()>(&Foo::vfb),
+                      static_cast<void (Foo::*)()>(nullptr))));
+
+  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(
+      std::make_tuple(static_cast<void (Foo::*)()>(Foo::A::pq()),
+                      static_cast<void (Foo::*)()>(Foo::B::pq()),
+                      static_cast<void (Foo::*)()>(nullptr))));
+}
+
 TEST(HashValueTest, PairAndTuple) {
   EXPECT_TRUE((is_hashable<std::pair<int, int>>::value));
   EXPECT_TRUE((is_hashable<std::pair<const int&, const int&>>::value));
diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h
index a424e014..f8103334 100644
--- a/absl/hash/internal/hash.h
+++ b/absl/hash/internal/hash.h
@@ -421,6 +421,39 @@ H AbslHashValue(H hash_state, std::nullptr_t) {
   return H::combine(std::move(hash_state), static_cast<void*>(nullptr));
 }
 
+// AbslHashValue() for hashing pointers-to-member
+template <typename H, typename T, typename C>
+H AbslHashValue(H hash_state, T C::* ptr) {
+  auto salient_ptm_size = [](std::size_t n) -> std::size_t {
+#if defined(_MSC_VER)
+    // Pointers-to-member-function on MSVC consist of one pointer plus 0, 1, 2,
+    // or 3 ints. In 64-bit mode, they are 8-byte aligned and thus can contain
+    // padding (namely when they have 1 or 3 ints). The value below is a lower
+    // bound on the number of salient, non-padding bytes that we use for
+    // hashing.
+    if (alignof(T C::*) == alignof(int)) {
+      // No padding when all subobjects have the same size as the total
+      // alignment. This happens in 32-bit mode.
+      return n;
+    } else {
+      // Padding for 1 int (size 16) or 3 ints (size 24).
+      // With 2 ints, the size is 16 with no padding, which we pessimize.
+      return n == 24 ? 20 : n == 16 ? 12 : n;
+    }
+#else
+    // On other platforms, we assume that pointers-to-members do not have
+    // padding.
+#ifdef __cpp_lib_has_unique_object_representations
+    static_assert(std::has_unique_object_representations_v<T C::*>);
+#endif  // __cpp_lib_has_unique_object_representations
+    return n;
+#endif
+  };
+  return H::combine_contiguous(std::move(hash_state),
+                               reinterpret_cast<unsigned char*>(&ptr),
+                               salient_ptm_size(sizeof ptr));
+}
+
 // -----------------------------------------------------------------------------
 // AbslHashValue for Composite Types
 // -----------------------------------------------------------------------------
diff --git a/absl/random/bit_gen_ref.h b/absl/random/bit_gen_ref.h
index 9555460f..e475221a 100644
--- a/absl/random/bit_gen_ref.h
+++ b/absl/random/bit_gen_ref.h
@@ -24,6 +24,10 @@
 #ifndef ABSL_RANDOM_BIT_GEN_REF_H_
 #define ABSL_RANDOM_BIT_GEN_REF_H_
 
+#include <limits>
+#include <type_traits>
+#include <utility>
+
 #include "absl/base/internal/fast_type_id.h"
 #include "absl/base/macros.h"
 #include "absl/meta/type_traits.h"
diff --git a/absl/random/internal/chi_square.cc b/absl/random/internal/chi_square.cc
index 640d48ce..fbe01732 100644
--- a/absl/random/internal/chi_square.cc
+++ b/absl/random/internal/chi_square.cc
@@ -125,7 +125,8 @@ double ChiSquareValue(int dof, double p) {
     const double variance = 2.0 / (9 * dof);
     // Cannot use this method if the variance is 0.
     if (variance != 0) {
-      return std::pow(z * std::sqrt(variance) + mean, 3.0) * dof;
+      double term = z * std::sqrt(variance) + mean;
+      return dof * (term * term * term);
     }
   }
 
diff --git a/absl/random/internal/distribution_caller.h b/absl/random/internal/distribution_caller.h
index f1ad5ccd..0f162a4e 100644
--- a/absl/random/internal/distribution_caller.h
+++ b/absl/random/internal/distribution_caller.h
@@ -18,6 +18,7 @@
 #define ABSL_RANDOM_INTERNAL_DISTRIBUTION_CALLER_H_
 
 #include <utility>
+#include <type_traits>
 
 #include "absl/base/config.h"
 #include "absl/base/internal/fast_type_id.h"
diff --git a/absl/random/internal/mock_helpers.h b/absl/random/internal/mock_helpers.h
index 9d6ab21e..882b0518 100644
--- a/absl/random/internal/mock_helpers.h
+++ b/absl/random/internal/mock_helpers.h
@@ -18,6 +18,7 @@
 
 #include <tuple>
 #include <type_traits>
+#include <utility>
 
 #include "absl/base/internal/fast_type_id.h"
 #include "absl/types/optional.h"
diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc
index b65dc58b..c6ec1ecf 100644
--- a/absl/strings/cord.cc
+++ b/absl/strings/cord.cc
@@ -87,30 +87,6 @@ static inline CordRep* VerifyTree(CordRep* node) {
   return node;
 }
 
-// Create a concatenation of the specified nodes.
-// Does not change the refcounts of "left" and "right".
-// The returned node has a refcount of 1.
-static CordRep* RawConcat(CordRep* left, CordRep* right) {
-  // Avoid making degenerate concat nodes (one child is empty)
-  if (left == nullptr) return right;
-  if (right == nullptr) return left;
-  if (left->length == 0) {
-    CordRep::Unref(left);
-    return right;
-  }
-  if (right->length == 0) {
-    CordRep::Unref(right);
-    return left;
-  }
-  ABSL_INTERNAL_LOG(FATAL, "CordRepConcat is no longer supported");
-  return nullptr;
-}
-
-static CordRep* Concat(CordRep* left, CordRep* right) {
-  CordRep* rep = RawConcat(left, right);
-  return VerifyTree(rep);
-}
-
 static CordRepFlat* CreateFlat(const char* data, size_t length,
                                size_t alloc_hint) {
   CordRepFlat* flat = CordRepFlat::New(length + alloc_hint);
@@ -608,68 +584,6 @@ inline void Cord::Prepend(T&& src) {
 
 template void Cord::Prepend(std::string&& src);
 
-static CordRep* RemovePrefixFrom(CordRep* node, size_t n) {
-  if (n >= node->length) return nullptr;
-  if (n == 0) return CordRep::Ref(node);
-  absl::InlinedVector<CordRep*, kInlinedVectorSize> rhs_stack;
-
-  assert(!node->IsCrc());
-  assert(n <= node->length);
-
-  if (n == 0) {
-    CordRep::Ref(node);
-  } else {
-    size_t start = n;
-    size_t len = node->length - n;
-    if (node->IsSubstring()) {
-      // Consider in-place update of node, similar to in RemoveSuffixFrom().
-      start += node->substring()->start;
-      node = node->substring()->child;
-    }
-    node = CordRepSubstring::Create(CordRep::Ref(node), start, len);
-  }
-  while (!rhs_stack.empty()) {
-    node = Concat(node, CordRep::Ref(rhs_stack.back()));
-    rhs_stack.pop_back();
-  }
-  return node;
-}
-
-// RemoveSuffixFrom() is very similar to RemovePrefixFrom(), with the
-// exception that removing a suffix has an optimization where a node may be
-// edited in place iff that node and all its ancestors have a refcount of 1.
-static CordRep* RemoveSuffixFrom(CordRep* node, size_t n) {
-  if (n >= node->length) return nullptr;
-  if (n == 0) return CordRep::Ref(node);
-  absl::InlinedVector<CordRep*, kInlinedVectorSize> lhs_stack;
-  bool inplace_ok = node->refcount.IsOne();
-  assert(!node->IsCrc());
-
-  assert(n <= node->length);
-
-  if (n == 0) {
-    CordRep::Ref(node);
-  } else if (inplace_ok && !node->IsExternal()) {
-    // Consider making a new buffer if the current node capacity is much
-    // larger than the new length.
-    CordRep::Ref(node);
-    node->length -= n;
-  } else {
-    size_t start = 0;
-    size_t len = node->length - n;
-    if (node->IsSubstring()) {
-      start = node->substring()->start;
-      node = node->substring()->child;
-    }
-    node = CordRepSubstring::Create(CordRep::Ref(node), start, len);
-  }
-  while (!lhs_stack.empty()) {
-    node = Concat(CordRep::Ref(lhs_stack.back()), node);
-    lhs_stack.pop_back();
-  }
-  return node;
-}
-
 void Cord::RemovePrefix(size_t n) {
   ABSL_INTERNAL_CHECK(n <= size(),
                       absl::StrCat("Requested prefix size ", n,
@@ -681,14 +595,20 @@ void Cord::RemovePrefix(size_t n) {
     auto constexpr method = CordzUpdateTracker::kRemovePrefix;
     CordzUpdateScope scope(contents_.cordz_info(), method);
     tree = cord_internal::RemoveCrcNode(tree);
-    if (tree->IsBtree()) {
+    if (n >= tree->length) {
+      CordRep::Unref(tree);
+      tree = nullptr;
+    } else if (tree->IsBtree()) {
       CordRep* old = tree;
       tree = tree->btree()->SubTree(n, tree->length - n);
       CordRep::Unref(old);
+    } else if (tree->IsSubstring() && tree->refcount.IsOne()) {
+      tree->substring()->start += n;
+      tree->length -= n;
     } else {
-      CordRep* newrep = RemovePrefixFrom(tree, n);
+      CordRep* rep = CordRepSubstring::Substring(tree, n, tree->length - n);
       CordRep::Unref(tree);
-      tree = VerifyTree(newrep);
+      tree = rep;
     }
     contents_.SetTreeOrEmpty(tree, scope);
   }
@@ -705,59 +625,23 @@ void Cord::RemoveSuffix(size_t n) {
     auto constexpr method = CordzUpdateTracker::kRemoveSuffix;
     CordzUpdateScope scope(contents_.cordz_info(), method);
     tree = cord_internal::RemoveCrcNode(tree);
-    if (tree->IsBtree()) {
+    if (n >= tree->length) {
+      CordRep::Unref(tree);
+      tree = nullptr;
+    } else if (tree->IsBtree()) {
       tree = CordRepBtree::RemoveSuffix(tree->btree(), n);
+    } else if (!tree->IsExternal() && tree->refcount.IsOne()) {
+      assert(tree->IsFlat() || tree->IsSubstring());
+      tree->length -= n;
     } else {
-      CordRep* newrep = RemoveSuffixFrom(tree, n);
+      CordRep* rep = CordRepSubstring::Substring(tree, 0, tree->length - n);
       CordRep::Unref(tree);
-      tree = VerifyTree(newrep);
+      tree = rep;
     }
     contents_.SetTreeOrEmpty(tree, scope);
   }
 }
 
-// Work item for NewSubRange().
-struct SubRange {
-  SubRange(CordRep* a_node, size_t a_pos, size_t a_n)
-      : node(a_node), pos(a_pos), n(a_n) {}
-  CordRep* node;  // nullptr means concat last 2 results.
-  size_t pos;
-  size_t n;
-};
-
-static CordRep* NewSubRange(CordRep* node, size_t pos, size_t n) {
-  absl::InlinedVector<CordRep*, kInlinedVectorSize> results;
-  absl::InlinedVector<SubRange, kInlinedVectorSize> todo;
-  assert(!node->IsCrc());
-  todo.push_back(SubRange(node, pos, n));
-  do {
-    const SubRange& sr = todo.back();
-    node = sr.node;
-    pos = sr.pos;
-    n = sr.n;
-    todo.pop_back();
-
-    if (node == nullptr) {
-      assert(results.size() >= 2);
-      CordRep* right = results.back();
-      results.pop_back();
-      CordRep* left = results.back();
-      results.pop_back();
-      results.push_back(Concat(left, right));
-    } else if (pos == 0 && n == node->length) {
-      results.push_back(CordRep::Ref(node));
-    } else {
-      if (node->IsSubstring()) {
-        pos += node->substring()->start;
-        node = node->substring()->child;
-      }
-      results.push_back(CordRepSubstring::Create(CordRep::Ref(node), pos, n));
-    }
-  } while (!todo.empty());
-  assert(results.size() == 1);
-  return results[0];
-}
-
 Cord Cord::Subcord(size_t pos, size_t new_size) const {
   Cord sub_cord;
   size_t length = size();
@@ -791,7 +675,7 @@ Cord Cord::Subcord(size_t pos, size_t new_size) const {
   if (tree->IsBtree()) {
     tree = tree->btree()->SubTree(pos, new_size);
   } else {
-    tree = NewSubRange(tree, pos, new_size);
+    tree = CordRepSubstring::Substring(tree, pos, new_size);
   }
   sub_cord.contents_.EmplaceTree(tree, contents_.data_,
                                  CordzUpdateTracker::kSubCord);
@@ -1140,7 +1024,7 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) {
                                            : payload->flat()->Data();
   const size_t offset = current_chunk_.data() - data;
 
-  auto* tree = CordRepSubstring::Create(CordRep::Ref(payload), offset, n);
+  auto* tree = CordRepSubstring::Substring(payload, offset, n);
   subcord.contents_.EmplaceTree(VerifyTree(tree), method);
   bytes_remaining_ -= n;
   current_chunk_.remove_prefix(n);
diff --git a/absl/strings/internal/cord_internal.h b/absl/strings/internal/cord_internal.h
index ece3db15..2087ffec 100644
--- a/absl/strings/internal/cord_internal.h
+++ b/absl/strings/internal/cord_internal.h
@@ -286,6 +286,14 @@ struct CordRepSubstring : public CordRep {
   // form a non-empty partial sub range of `'child`, i.e.:
   // `n > 0 && n < length && n + pos <= length`
   static inline CordRepSubstring* Create(CordRep* child, size_t pos, size_t n);
+
+  // Creates a substring of `rep`. Does not adopt a reference on `rep`.
+  // Requires `IsDataEdge(rep) && n > 0 && pos + n <= rep->length`.
+  // If `n == rep->length` then this method returns `CordRep::Ref(rep)`
+  // If `rep` is a substring of a flat or external node, then this method will
+  // return a new substring of that flat or external node with `pos` adjusted
+  // with the original `start` position.
+  static inline CordRep* Substring(CordRep* rep, size_t pos, size_t n);
 };
 
 // Type for function pointer that will invoke the releaser function and also
@@ -371,6 +379,25 @@ inline CordRepSubstring* CordRepSubstring::Create(CordRep* child, size_t pos,
   return rep;
 }
 
+inline CordRep* CordRepSubstring::Substring(CordRep* rep, size_t pos,
+                                            size_t n) {
+  assert(rep != nullptr);
+  assert(n != 0);
+  assert(pos < rep->length);
+  assert(n <= rep->length - pos);
+  if (n == rep->length) return CordRep::Ref(rep);
+  if (rep->IsSubstring()) {
+    pos += rep->substring()->start;
+    rep = rep->substring()->child;
+  }
+  CordRepSubstring* substr = new CordRepSubstring();
+  substr->length = n;
+  substr->tag = SUBSTRING;
+  substr->start = pos;
+  substr->child = CordRep::Ref(rep);
+  return substr;
+}
+
 inline void CordRepExternal::Delete(CordRep* rep) {
   assert(rep != nullptr && rep->IsExternal());
   auto* rep_external = static_cast<CordRepExternal*>(rep);