Quelle  cord_test.cc   Sprache: C

// Copyright 2020 The Abseil Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "absl/strings/cord.h"

#include <algorithm>
#include <array>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <limits>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>

#include "gmock/gmock.h"
#include "gtest/gtest.h"
#include "absl/base/attributes.h"
#include "absl/base/config.h"
#include "absl/base/internal/endian.h"
#include "absl/base/macros.h"
#include "absl/base/no_destructor.h"
#include "absl/base/options.h"
#include "absl/container/fixed_array.h"
#include "absl/functional/function_ref.h"
#include "absl/hash/hash.h"
#include "absl/hash/hash_testing.h"
#include "absl/log/check.h"
#include "absl/log/log.h"
#include "absl/random/random.h"
#include "absl/strings/cord_buffer.h"
#include "absl/strings/cord_test_helpers.h"
#include "absl/strings/cordz_test_helpers.h"
#include "absl/strings/internal/cord_internal.h"
#include "absl/strings/internal/cord_rep_crc.h"
#include "absl/strings/internal/cord_rep_flat.h"
#include "absl/strings/internal/cordz_statistics.h"
#include "absl/strings/internal/cordz_update_tracker.h"
#include "absl/strings/internal/string_constant.h"
#include "absl/strings/match.h"
#include "absl/strings/str_cat.h"
#include "absl/strings/str_format.h"
#include "absl/strings/string_view.h"
#include "absl/types/compare.h"
#include "absl/types/optional.h"

// convenience local constants
static constexpr auto FLAT = absl::cord_internal::FLAT;
static constexpr auto MAX_FLAT_TAG = absl::cord_internal::MAX_FLAT_TAG;

typedef std::mt19937_64 RandomEngine;

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;
using absl::cord_internal::CordRepSubstring;
using absl::cord_internal::CordzUpdateTracker;
using absl::cord_internal::kFlatOverhead;
using absl::cord_internal::kMaxFlatLength;
using ::testing::ElementsAre;
using ::testing::Le;

static std::string RandomLowercaseString(RandomEngine* rng);
static std::string RandomLowercaseString(RandomEngine* rng, size_t length);

static int GetUniformRandomUpTo(RandomEngine* rng, int upper_bound) {
  if (upper_bound > 0) {
    std::uniform_int_distribution<int> uniform(0, upper_bound - 1);
    return uniform(*rng);
  } else {
    return 0;
  }
}

static size_t GetUniformRandomUpTo(RandomEngine* rng, size_t upper_bound) {
  if (upper_bound > 0) {
    std::uniform_int_distribution<size_t> uniform(0, upper_bound - 1);
    return uniform(*rng);
  } else {
    return 0;
  }
}

static int32_t GenerateSkewedRandom(RandomEngine* rng, int max_log) {
  const uint32_t base = (*rng)() % (max_log + 1);
  const uint32_t mask = ((base < 32) ? (1u << base) : 0u) - 1u;
  return (*rng)() & mask;
}

static std::string RandomLowercaseString(RandomEngine* rng) {
  int length;
  std::bernoulli_distribution one_in_1k(0.001);
  std::bernoulli_distribution one_in_10k(0.0001);
  // With low probability, make a large fragment
  if (one_in_10k(*rng)) {
    length = GetUniformRandomUpTo(rng, 1048576);
  } else if (one_in_1k(*rng)) {
    length = GetUniformRandomUpTo(rng, 10000);
  } else {
    length = GenerateSkewedRandom(rng, 10);
  }
  return RandomLowercaseString(rng, length);
}

static std::string RandomLowercaseString(RandomEngine* rng, size_t length) {
  std::string result(length, '\0');
  std::uniform_int_distribution<int> chars('a', 'z');
  std::generate(result.begin(), result.end(),
                [&]() { return static_cast<char>(chars(*rng)); });
  return result;
}

static void DoNothing(absl::string_view /* data */, void* /* arg */) {}

static void DeleteExternalString(absl::string_view data, void* arg) {
  std::string* s = reinterpret_cast<std::string*>(arg);
  EXPECT_EQ(data, *s);
  delete s;
}

// Add "s" to *dst via `MakeCordFromExternal`
static void AddExternalMemory(absl::string_view s, absl::Cord* dst) {
  std::string* str = new std::string(s.data(), s.size());
  dst->Append(absl::MakeCordFromExternal(*str, [str](absl::string_view data) {
    DeleteExternalString(data, str);
  }));
}

static void DumpGrowth() {
  absl::Cord str;
  for (int i = 0; i < 1000; i++) {
    char c = 'a' + i % 26;
    str.Append(absl::string_view(&c, 1));
  }
}

// Make a Cord with some number of fragments.  Return the size (in bytes)
// of the smallest fragment.
static size_t AppendWithFragments(const std::string& s, RandomEngine* rng,
                                  absl::Cord* cord) {
  size_t j = 0;
  const size_t max_size = s.size() / 5;  // Make approx. 10 fragments
  size_t min_size = max_size;            // size of smallest fragment
  while (j < s.size()) {
    size_t N = 1 + GetUniformRandomUpTo(rng, max_size);
    if (N > (s.size() - j)) {
      N = s.size() - j;
    }
    if (N < min_size) {
      min_size = N;
    }

    std::bernoulli_distribution coin_flip(0.5);
    if (coin_flip(*rng)) {
      // Grow by adding an external-memory.
      AddExternalMemory(absl::string_view(s.data() + j, N), cord);
    } else {
      cord->Append(absl::string_view(s.data() + j, N));
    }
    j += N;
  }
  return min_size;
}

// Add an external memory that contains the specified std::string to cord
static void AddNewStringBlock(const std::string& str, absl::Cord* dst) {
  char* data = new char[str.size()];
  memcpy(data, str.data(), str.size());
  dst->Append(absl::MakeCordFromExternal(
      absl::string_view(data, str.size()),
      [](absl::string_view s) { delete[] s.data(); }));
}

// Make a Cord out of many different types of nodes.
static absl::Cord MakeComposite() {
  absl::Cord cord;
  cord.Append("the");
  AddExternalMemory(" quick brown", &cord);
  AddExternalMemory(" fox jumped", &cord);

  absl::Cord full(" over");
  AddExternalMemory(" the lazy", &full);
  AddNewStringBlock(" dog slept the whole day away", &full);
  absl::Cord substring = full.Subcord(0, 18);

  // Make substring long enough to defeat the copying fast path in Append.
  substring.Append(std::string(1000, '.'));
  cord.Append(substring);
  cord = cord.Subcord(0, cord.size() - 998);  // Remove most of extra junk

  return cord;
}

namespace absl {
ABSL_NAMESPACE_BEGIN

class CordTestPeer {
 public:
  static void ForEachChunk(
      const Cord& c, absl::FunctionRef<void(absl::string_view)> callback) {
    c.ForEachChunk(callback);
  }

  static bool IsTree(const Cord& c) { return c.contents_.is_tree(); }
  static CordRep* Tree(const Cord& c) { return c.contents_.tree(); }

  static cord_internal::CordzInfo* GetCordzInfo(const Cord& c) {
    return c.contents_.cordz_info();
  }

  static Cord MakeSubstring(Cord src, size_t offset, size_t length) {
    CHECK(src.contents_.is_tree()) << "Can not be inlined";
    CHECK(!src.ExpectedChecksum().has_value()) << "Can not be hardened";
    Cord cord;
    auto* tree = cord_internal::SkipCrcNode(src.contents_.tree());
    auto* rep = CordRepSubstring::Create(CordRep::Ref(tree), offset, length);
    cord.contents_.EmplaceTree(rep, CordzUpdateTracker::kSubCord);
    return cord;
  }
};

ABSL_NAMESPACE_END
}  // namespace absl



// The CordTest fixture runs all tests with and without expected CRCs being set
// on the subject Cords.
class CordTest : public testing::TestWithParam<bool /*useCrc*/> {
 public:
  // Returns true if test is running with Crc enabled.
  bool UseCrc() const { return GetParam(); }
  void MaybeHarden(absl::Cord& c) {
    if (UseCrc()) {
      c.SetExpectedChecksum(1);
    }
  }
  absl::Cord MaybeHardened(absl::Cord c) {
    MaybeHarden(c);
    return c;
  }

  // Returns human readable string representation of the test parameter.
  static std::string ToString(testing::TestParamInfo<bool> useCrc) {
    if (useCrc.param) {
      return "BtreeHardened";
    } else {
      return "Btree";
    }
  }
};

INSTANTIATE_TEST_SUITE_P(WithParam, CordTest, testing::Bool(),
                         CordTest::ToString);

TEST(CordRepFlat, AllFlatCapacities) {
  // Explicitly and redundantly assert built-in min/max limits
  static_assert(absl::cord_internal::kFlatOverhead < 32, "");
  static_assert(absl::cord_internal::kMinFlatSize == 32, "");
  static_assert(absl::cord_internal::kMaxLargeFlatSize == 256 << 10, "");
  EXPECT_EQ(absl::cord_internal::TagToAllocatedSize(FLAT), 32);
  EXPECT_EQ(absl::cord_internal::TagToAllocatedSize(MAX_FLAT_TAG), 256 << 10);

  // Verify all tags to map perfectly back and forth, and
  // that sizes are monotonically increasing.
  size_t last_size = 0;
  for (int tag = FLAT; tag <= MAX_FLAT_TAG; ++tag) {
    size_t size = absl::cord_internal::TagToAllocatedSize(tag);
    ASSERT_GT(size, last_size);
    ASSERT_EQ(absl::cord_internal::TagToAllocatedSize(tag), size);
    last_size = size;
  }

  // All flat size from 32 - 512 are 8 byte granularity
  for (size_t size = 32; size <= 512; size += 8) {
    ASSERT_EQ(absl::cord_internal::RoundUpForTag(size), size);
    uint8_t tag = absl::cord_internal::AllocatedSizeToTag(size);
    ASSERT_EQ(absl::cord_internal::TagToAllocatedSize(tag), size);
  }

  // All flat sizes from 512 - 8192 are 64 byte granularity
  for (size_t size = 512; size <= 8192; size += 64) {
    ASSERT_EQ(absl::cord_internal::RoundUpForTag(size), size);
    uint8_t tag = absl::cord_internal::AllocatedSizeToTag(size);
    ASSERT_EQ(absl::cord_internal::TagToAllocatedSize(tag), size);
  }

  // All flat sizes from 8KB to 256KB are 4KB granularity
  for (size_t size = 8192; size <= 256 * 1024; size += 4 * 1024) {
    ASSERT_EQ(absl::cord_internal::RoundUpForTag(size), size);
    uint8_t tag = absl::cord_internal::AllocatedSizeToTag(size);
    ASSERT_EQ(absl::cord_internal::TagToAllocatedSize(tag), size);
  }
}

TEST(CordRepFlat, MaxFlatSize) {
  CordRepFlat* flat = CordRepFlat::New(kMaxFlatLength);
  EXPECT_EQ(flat->Capacity(), kMaxFlatLength);
  CordRep::Unref(flat);

  flat = CordRepFlat::New(kMaxFlatLength * 4);
  EXPECT_EQ(flat->Capacity(), kMaxFlatLength);
  CordRep::Unref(flat);
}

TEST(CordRepFlat, MaxLargeFlatSize) {
  const size_t size = 256 * 1024 - kFlatOverhead;
  CordRepFlat* flat = CordRepFlat::New(CordRepFlat::Large(), size);
  EXPECT_GE(flat->Capacity(), size);
  CordRep::Unref(flat);
}

TEST(CordRepFlat, AllFlatSizes) {
  const size_t kMaxSize = 256 * 1024;
  for (size_t size = 32; size <= kMaxSize; size *=2) {
    const size_t length = size - kFlatOverhead - 1;
    CordRepFlat* flat = CordRepFlat::New(CordRepFlat::Large(), length);
    EXPECT_GE(flat->Capacity(), length);
    memset(flat->Data(), 0xCD, flat->Capacity());
    CordRep::Unref(flat);
  }
}

TEST_P(CordTest, AllFlatSizes) {
  using absl::strings_internal::CordTestAccess;

  for (size_t s = 0; s < CordTestAccess::MaxFlatLength(); s++) {
    // Make a string of length s.
    std::string src;
    while (src.size() < s) {
      src.push_back('a' + (src.size() % 26));
    }

    absl::Cord dst(src);
    MaybeHarden(dst);
    EXPECT_EQ(std::string(dst), src) << s;
  }
}

// We create a Cord at least 128GB in size using the fact that Cords can
// internally reference-count; thus the Cord is enormous without actually
// consuming very much memory.
TEST_P(CordTest, GigabyteCordFromExternal) {
  const size_t one_gig = 1024U * 1024U * 1024U;
  size_t max_size = 2 * one_gig;
  if (sizeof(max_size) > 4) max_size = 128 * one_gig;

  size_t length = 128 * 1024;
  char* data = new char[length];
  absl::Cord from = absl::MakeCordFromExternal(
      absl::string_view(data, length),
      [](absl::string_view sv) { delete[] sv.data(); });

  // This loop may seem odd due to its combination of exponential doubling of
  // size and incremental size increases.  We do it incrementally to be sure the
  // Cord will need rebalancing and will exercise code that, in the past, has
  // caused crashes in production.  We grow exponentially so that the code will
  // execute in a reasonable amount of time.
  absl::Cord c;
  c.Append(from);
  while (c.size() < max_size) {
    c.Append(c);
    c.Append(from);
    c.Append(from);
    c.Append(from);
    c.Append(from);
    MaybeHarden(c);
  }

  for (int i = 0; i < 1024; ++i) {
    c.Append(from);
  }
  LOG(INFO) << "Made a Cord with " << c.size() << " bytes!";
  // Note: on a 32-bit build, this comes out to   2,818,048,000 bytes.
  // Note: on a 64-bit build, this comes out to 171,932,385,280 bytes.
}

static absl::Cord MakeExternalCord(int size) {
  char* buffer = new char[size];
  memset(buffer, 'x', size);
  absl::Cord cord;
  cord.Append(absl::MakeCordFromExternal(
      absl::string_view(buffer, size),
      [](absl::string_view s) { delete[] s.data(); }));
  return cord;
}

// Extern to fool clang that this is not constant. Needed to suppress
// a warning of unsafe code we want to test.
extern bool my_unique_true_boolean;
bool my_unique_true_boolean = true;

TEST_P(CordTest, Assignment) {
  absl::Cord x(absl::string_view("hi there"));
  absl::Cord y(x);
  MaybeHarden(y);
  ASSERT_EQ(x.ExpectedChecksum(), absl::nullopt);
  ASSERT_EQ(std::string(x), "hi there");
  ASSERT_EQ(std::string(y), "hi there");
  ASSERT_TRUE(x == y);
  ASSERT_TRUE(x <= y);
  ASSERT_TRUE(y <= x);

  x = absl::string_view("foo");
  ASSERT_EQ(std::string(x), "foo");
  ASSERT_EQ(std::string(y), "hi there");
  ASSERT_TRUE(x < y);
  ASSERT_TRUE(y > x);
  ASSERT_TRUE(x != y);
  ASSERT_TRUE(x <= y);
  ASSERT_TRUE(y >= x);

  x = "foo";
  ASSERT_EQ(x, "foo");

  // Test that going from inline rep to tree we don't leak memory.
  std::vector<std::pair<absl::string_view, absl::string_view>>
      test_string_pairs = {{"hi there", "foo"},
                           {"loooooong coooooord", "short cord"},
                           {"short cord", "loooooong coooooord"},
                           {"loooooong coooooord1", "loooooong coooooord2"}};
  for (std::pair<absl::string_view, absl::string_view> test_strings :
       test_string_pairs) {
    absl::Cord tmp(test_strings.first);
    absl::Cord z(std::move(tmp));
    ASSERT_EQ(std::string(z), test_strings.first);
    tmp = test_strings.second;
    z = std::move(tmp);
    ASSERT_EQ(std::string(z), test_strings.second);
  }
  {
    // Test that self-move assignment doesn't crash/leak.
    // Do not write such code!
    absl::Cord my_small_cord("foo");
    absl::Cord my_big_cord("loooooong coooooord");
    // Bypass clang's warning on self move-assignment.
    absl::Cord* my_small_alias =
        my_unique_true_boolean ? &my_small_cord : &my_big_cord;
    absl::Cord* my_big_alias =
        !my_unique_true_boolean ? &my_small_cord : &my_big_cord;

    *my_small_alias = std::move(my_small_cord);
    *my_big_alias = std::move(my_big_cord);
    // my_small_cord and my_big_cord are in an unspecified but valid
    // state, and will be correctly destroyed here.
  }
}

TEST_P(CordTest, StartsEndsWith) {
  absl::Cord x(absl::string_view("abcde"));
  MaybeHarden(x);
  absl::Cord empty("");

  ASSERT_TRUE(x.StartsWith(absl::Cord("abcde")));
  ASSERT_TRUE(x.StartsWith(absl::Cord("abc")));
  ASSERT_TRUE(x.StartsWith(absl::Cord("")));
  ASSERT_TRUE(empty.StartsWith(absl::Cord("")));
  ASSERT_TRUE(x.EndsWith(absl::Cord("abcde")));
  ASSERT_TRUE(x.EndsWith(absl::Cord("cde")));
  ASSERT_TRUE(x.EndsWith(absl::Cord("")));
  ASSERT_TRUE(empty.EndsWith(absl::Cord("")));

  ASSERT_TRUE(!x.StartsWith(absl::Cord("xyz")));
  ASSERT_TRUE(!empty.StartsWith(absl::Cord("xyz")));
  ASSERT_TRUE(!x.EndsWith(absl::Cord("xyz")));
  ASSERT_TRUE(!empty.EndsWith(absl::Cord("xyz")));

  ASSERT_TRUE(x.StartsWith("abcde"));
  ASSERT_TRUE(x.StartsWith("abc"));
  ASSERT_TRUE(x.StartsWith(""));
  ASSERT_TRUE(empty.StartsWith(""));
  ASSERT_TRUE(x.EndsWith("abcde"));
  ASSERT_TRUE(x.EndsWith("cde"));
  ASSERT_TRUE(x.EndsWith(""));
  ASSERT_TRUE(empty.EndsWith(""));

  ASSERT_TRUE(!x.StartsWith("xyz"));
  ASSERT_TRUE(!empty.StartsWith("xyz"));
  ASSERT_TRUE(!x.EndsWith("xyz"));
  ASSERT_TRUE(!empty.EndsWith("xyz"));
}

TEST_P(CordTest, Contains) {
  auto flat_haystack = absl::Cord("this is a flat cord");
  auto fragmented_haystack = absl::MakeFragmentedCord(
      {"this", " ", "is", " ", "a", " ", "fragmented", " ", "cord"});

  EXPECT_TRUE(flat_haystack.Contains(""));
  EXPECT_TRUE(fragmented_haystack.Contains(""));
  EXPECT_TRUE(flat_haystack.Contains(absl::Cord("")));
  EXPECT_TRUE(fragmented_haystack.Contains(absl::Cord("")));
  EXPECT_TRUE(absl::Cord("").Contains(""));
  EXPECT_TRUE(absl::Cord("").Contains(absl::Cord("")));
  EXPECT_FALSE(absl::Cord("").Contains(flat_haystack));
  EXPECT_FALSE(absl::Cord("").Contains(fragmented_haystack));

  EXPECT_FALSE(flat_haystack.Contains("z"));
  EXPECT_FALSE(fragmented_haystack.Contains("z"));
  EXPECT_FALSE(flat_haystack.Contains(absl::Cord("z")));
  EXPECT_FALSE(fragmented_haystack.Contains(absl::Cord("z")));

  EXPECT_FALSE(flat_haystack.Contains("is an"));
  EXPECT_FALSE(fragmented_haystack.Contains("is an"));
  EXPECT_FALSE(flat_haystack.Contains(absl::Cord("is an")));
  EXPECT_FALSE(fragmented_haystack.Contains(absl::Cord("is an")));
  EXPECT_FALSE(
      flat_haystack.Contains(absl::MakeFragmentedCord({"is", " ", "an"})));
  EXPECT_FALSE(fragmented_haystack.Contains(
      absl::MakeFragmentedCord({"is", " ", "an"})));

  EXPECT_TRUE(flat_haystack.Contains("is a"));
  EXPECT_TRUE(fragmented_haystack.Contains("is a"));
  EXPECT_TRUE(flat_haystack.Contains(absl::Cord("is a")));
  EXPECT_TRUE(fragmented_haystack.Contains(absl::Cord("is a")));
  EXPECT_TRUE(
      flat_haystack.Contains(absl::MakeFragmentedCord({"is", " ", "a"})));
  EXPECT_TRUE(
      fragmented_haystack.Contains(absl::MakeFragmentedCord({"is", " ", "a"})));
}

TEST_P(CordTest, Find) {
  auto flat_haystack = absl::Cord("this is a flat cord");
  auto fragmented_haystack = absl::MakeFragmentedCord(
      {"this", " ", "is", " ", "a", " ", "fragmented", " ", "cord"});
  auto empty_haystack = absl::Cord("");

  EXPECT_EQ(flat_haystack.Find(""), flat_haystack.char_begin());
  EXPECT_EQ(fragmented_haystack.Find(""), fragmented_haystack.char_begin());
  EXPECT_EQ(flat_haystack.Find(absl::Cord("")), flat_haystack.char_begin());
  EXPECT_EQ(fragmented_haystack.Find(absl::Cord("")),
            fragmented_haystack.char_begin());
  EXPECT_EQ(empty_haystack.Find(""), empty_haystack.char_begin());
  EXPECT_EQ(empty_haystack.Find(absl::Cord("")), empty_haystack.char_begin());
  EXPECT_EQ(empty_haystack.Find(flat_haystack), empty_haystack.char_end());
  EXPECT_EQ(empty_haystack.Find(fragmented_haystack),
            empty_haystack.char_end());

  EXPECT_EQ(flat_haystack.Find("z"), flat_haystack.char_end());
  EXPECT_EQ(fragmented_haystack.Find("z"), fragmented_haystack.char_end());
  EXPECT_EQ(flat_haystack.Find(absl::Cord("z")), flat_haystack.char_end());
  EXPECT_EQ(fragmented_haystack.Find(absl::Cord("z")),
            fragmented_haystack.char_end());

  EXPECT_EQ(flat_haystack.Find("is an"), flat_haystack.char_end());
  EXPECT_EQ(fragmented_haystack.Find("is an"), fragmented_haystack.char_end());
  EXPECT_EQ(flat_haystack.Find(absl::Cord("is an")), flat_haystack.char_end());
  EXPECT_EQ(fragmented_haystack.Find(absl::Cord("is an")),
            fragmented_haystack.char_end());
  EXPECT_EQ(flat_haystack.Find(absl::MakeFragmentedCord({"is", " ", "an"})),
            flat_haystack.char_end());
  EXPECT_EQ(
      fragmented_haystack.Find(absl::MakeFragmentedCord({"is", " ", "an"})),
      fragmented_haystack.char_end());

  EXPECT_EQ(flat_haystack.Find("is a"),
            std::next(flat_haystack.char_begin(), 5));
  EXPECT_EQ(fragmented_haystack.Find("is a"),
            std::next(fragmented_haystack.char_begin(), 5));
  EXPECT_EQ(flat_haystack.Find(absl::Cord("is a")),
            std::next(flat_haystack.char_begin(), 5));
  EXPECT_EQ(fragmented_haystack.Find(absl::Cord("is a")),
            std::next(fragmented_haystack.char_begin(), 5));
  EXPECT_EQ(flat_haystack.Find(absl::MakeFragmentedCord({"is", " ", "a"})),
            std::next(flat_haystack.char_begin(), 5));
  EXPECT_EQ(
      fragmented_haystack.Find(absl::MakeFragmentedCord({"is", " ", "a"})),
      std::next(fragmented_haystack.char_begin(), 5));
}

TEST_P(CordTest, Subcord) {
  RandomEngine rng(GTEST_FLAG_GET(random_seed));
  const std::string s = RandomLowercaseString(&rng, 1024);

  absl::Cord a;
  AppendWithFragments(s, &rng, &a);
  MaybeHarden(a);
  ASSERT_EQ(s, std::string(a));

  // Check subcords of a, from a variety of interesting points.
  std::set<size_t> positions;
  for (int i = 0; i <= 32; ++i) {
    positions.insert(i);
    positions.insert(i * 32 - 1);
    positions.insert(i * 32);
    positions.insert(i * 32 + 1);
    positions.insert(a.size() - i);
  }
  positions.insert(237);
  positions.insert(732);
  for (size_t pos : positions) {
    if (pos > a.size()) continue;
    for (size_t end_pos : positions) {
      if (end_pos < pos || end_pos > a.size()) continue;
      absl::Cord sa = a.Subcord(pos, end_pos - pos);
      ASSERT_EQ(absl::string_view(s).substr(pos, end_pos - pos),
                std::string(sa))
          << a;
      if (pos != 0 || end_pos != a.size()) {
        ASSERT_EQ(sa.ExpectedChecksum(), absl::nullopt);
      }
    }
  }

  // Do the same thing for an inline cord.
  const std::string sh = "short";
  absl::Cord c(sh);
  for (size_t pos = 0; pos <= sh.size(); ++pos) {
    for (size_t n = 0; n <= sh.size() - pos; ++n) {
      absl::Cord sc = c.Subcord(pos, n);
      ASSERT_EQ(sh.substr(pos, n), std::string(sc)) << c;
    }
  }

  // Check subcords of subcords.
  absl::Cord sa = a.Subcord(0, a.size());
  std::string ss = s.substr(0, s.size());
  while (sa.size() > 1) {
    sa = sa.Subcord(1, sa.size() - 2);
    ss = ss.substr(1, ss.size() - 2);
    ASSERT_EQ(ss, std::string(sa)) << a;
    if (HasFailure()) break;  // halt cascade
  }

  // It is OK to ask for too much.
  sa = a.Subcord(0, a.size() + 1);
  EXPECT_EQ(s, std::string(sa));

  // It is OK to ask for something beyond the end.
  sa = a.Subcord(a.size() + 1, 0);
  EXPECT_TRUE(sa.empty());
  sa = a.Subcord(a.size() + 1, 1);
  EXPECT_TRUE(sa.empty());
}

TEST_P(CordTest, Swap) {
  absl::string_view a("Dexter");
  absl::string_view b("Mandark");
  absl::Cord x(a);
  absl::Cord y(b);
  MaybeHarden(x);
  swap(x, y);
  if (UseCrc()) {
    ASSERT_EQ(x.ExpectedChecksum(), absl::nullopt);
    ASSERT_EQ(y.ExpectedChecksum(), 1);
  }
  ASSERT_EQ(x, absl::Cord(b));
  ASSERT_EQ(y, absl::Cord(a));
  x.swap(y);
  if (UseCrc()) {
    ASSERT_EQ(x.ExpectedChecksum(), 1);
    ASSERT_EQ(y.ExpectedChecksum(), absl::nullopt);
  }
  ASSERT_EQ(x, absl::Cord(a));
  ASSERT_EQ(y, absl::Cord(b));
}

static void VerifyCopyToString(const absl::Cord& cord) {
  std::string initially_empty;
  absl::CopyCordToString(cord, &initially_empty);
  EXPECT_EQ(initially_empty, cord);

  constexpr size_t kInitialLength = 1024;
  std::string has_initial_contents(kInitialLength, 'x');
  const char* address_before_copy = has_initial_contents.data();
  absl::CopyCordToString(cord, &has_initial_contents);
  EXPECT_EQ(has_initial_contents, cord);

  if (cord.size() <= kInitialLength) {
    EXPECT_EQ(has_initial_contents.data(), address_before_copy)
        << "CopyCordToString allocated new string storage; "
           "has_initial_contents = \""
        << has_initial_contents << "\"";
  }
}

TEST_P(CordTest, CopyToString) {
  VerifyCopyToString(absl::Cord());  // empty cords cannot carry CRCs
  VerifyCopyToString(MaybeHardened(absl::Cord("small cord")));
  VerifyCopyToString(MaybeHardened(
      absl::MakeFragmentedCord({"fragmented ", "cord ", "to ", "test ",
                                "copying ", "to ", "a ", "string."})));
}

static void VerifyAppendCordToString(const absl::Cord& cord) {
  std::string initially_empty;
  absl::AppendCordToString(cord, &initially_empty);
  EXPECT_EQ(initially_empty, cord);

  const absl::string_view kInitialContents = "initial contents.";
  std::string expected_after_append =
      absl::StrCat(kInitialContents, std::string(cord));

  std::string no_reserve(kInitialContents);
  absl::AppendCordToString(cord, &no_reserve);
  EXPECT_EQ(no_reserve, expected_after_append);

  std::string has_reserved_capacity(kInitialContents);
  has_reserved_capacity.reserve(has_reserved_capacity.size() + cord.size());
  const char* address_before_copy = has_reserved_capacity.data();
  absl::AppendCordToString(cord, &has_reserved_capacity);
  EXPECT_EQ(has_reserved_capacity, expected_after_append);
  EXPECT_EQ(has_reserved_capacity.data(), address_before_copy)
      << "AppendCordToString allocated new string storage; "
         "has_reserved_capacity = \""
      << has_reserved_capacity << "\"";
}

TEST_P(CordTest, AppendToString) {
  VerifyAppendCordToString(absl::Cord());  // empty cords cannot carry CRCs
  VerifyAppendCordToString(MaybeHardened(absl::Cord("small cord")));
  VerifyAppendCordToString(MaybeHardened(
      absl::MakeFragmentedCord({"fragmented ", "cord ", "to ", "test ",
                                "appending ", "to ", "a ", "string."})));
}

TEST_P(CordTest, AppendEmptyBuffer) {
  absl::Cord cord;
  cord.Append(absl::CordBuffer());
  cord.Append(absl::CordBuffer::CreateWithDefaultLimit(2000));
}

TEST_P(CordTest, AppendEmptyBufferToFlat) {
  absl::Cord cord(std::string(2000, 'x'));
  cord.Append(absl::CordBuffer());
  cord.Append(absl::CordBuffer::CreateWithDefaultLimit(2000));
}

TEST_P(CordTest, AppendEmptyBufferToTree) {
  absl::Cord cord(std::string(2000, 'x'));
  cord.Append(std::string(2000, 'y'));
  cord.Append(absl::CordBuffer());
  cord.Append(absl::CordBuffer::CreateWithDefaultLimit(2000));
}

TEST_P(CordTest, AppendSmallBuffer) {
  absl::Cord cord;
  absl::CordBuffer buffer = absl::CordBuffer::CreateWithDefaultLimit(3);
  ASSERT_THAT(buffer.capacity(), Le(15));
  memcpy(buffer.data(), "Abc", 3);
  buffer.SetLength(3);
  cord.Append(std::move(buffer));
  EXPECT_EQ(buffer.length(), 0);    // NOLINT
  EXPECT_GT(buffer.capacity(), 0);  // NOLINT

  buffer = absl::CordBuffer::CreateWithDefaultLimit(3);
  memcpy(buffer.data(), "defgh", 5);
  buffer.SetLength(5);
  cord.Append(std::move(buffer));
  EXPECT_EQ(buffer.length(), 0);    // NOLINT
  EXPECT_GT(buffer.capacity(), 0);  // NOLINT

  EXPECT_THAT(cord.Chunks(), ElementsAre("Abcdefgh"));
}

TEST_P(CordTest, AppendAndPrependBufferArePrecise) {
  // Create a cord large enough to force 40KB flats.
  std::string test_data(absl::cord_internal::kMaxFlatLength * 10, 'x');
  absl::Cord cord1(test_data);
  absl::Cord cord2(test_data);
  const size_t size1 = cord1.EstimatedMemoryUsage();
  const size_t size2 = cord2.EstimatedMemoryUsage();

  absl::CordBuffer buffer = absl::CordBuffer::CreateWithDefaultLimit(3);
  memcpy(buffer.data(), "Abc", 3);
  buffer.SetLength(3);
  cord1.Append(std::move(buffer));

  buffer = absl::CordBuffer::CreateWithDefaultLimit(3);
  memcpy(buffer.data(), "Abc", 3);
  buffer.SetLength(3);
  cord2.Prepend(std::move(buffer));

#ifndef NDEBUG
  // Allow 32 bytes new CordRepFlat, and 128 bytes for 'glue nodes'
  constexpr size_t kMaxDelta = 128 + 32;
#else
  // Allow 256 bytes extra for 'allocation debug overhead'
  constexpr size_t kMaxDelta = 128 + 32 + 256;
#endif

  EXPECT_LE(cord1.EstimatedMemoryUsage() - size1, kMaxDelta);
  EXPECT_LE(cord2.EstimatedMemoryUsage() - size2, kMaxDelta);

  EXPECT_EQ(cord1, absl::StrCat(test_data, "Abc"));
  EXPECT_EQ(cord2, absl::StrCat("Abc", test_data));
}

TEST_P(CordTest, PrependSmallBuffer) {
  absl::Cord cord;
  absl::CordBuffer buffer = absl::CordBuffer::CreateWithDefaultLimit(3);
  ASSERT_THAT(buffer.capacity(), Le(15));
  memcpy(buffer.data(), "Abc", 3);
  buffer.SetLength(3);
  cord.Prepend(std::move(buffer));
  EXPECT_EQ(buffer.length(), 0);    // NOLINT
  EXPECT_GT(buffer.capacity(), 0);  // NOLINT

  buffer = absl::CordBuffer::CreateWithDefaultLimit(3);
  memcpy(buffer.data(), "defgh", 5);
  buffer.SetLength(5);
  cord.Prepend(std::move(buffer));
  EXPECT_EQ(buffer.length(), 0);    // NOLINT
  EXPECT_GT(buffer.capacity(), 0);  // NOLINT

  EXPECT_THAT(cord.Chunks(), ElementsAre("defghAbc"));
}

TEST_P(CordTest, AppendLargeBuffer) {
  absl::Cord cord;

  std::string s1(700, '1');
  absl::CordBuffer buffer = absl::CordBuffer::CreateWithDefaultLimit(s1.size());
  memcpy(buffer.data(), s1.data(), s1.size());
  buffer.SetLength(s1.size());
  cord.Append(std::move(buffer));
  EXPECT_EQ(buffer.length(), 0);    // NOLINT
  EXPECT_GT(buffer.capacity(), 0);  // NOLINT

  std::string s2(1000, '2');
  buffer = absl::CordBuffer::CreateWithDefaultLimit(s2.size());
  memcpy(buffer.data(), s2.data(), s2.size());
  buffer.SetLength(s2.size());
  cord.Append(std::move(buffer));
  EXPECT_EQ(buffer.length(), 0);    // NOLINT
  EXPECT_GT(buffer.capacity(), 0);  // NOLINT

  EXPECT_THAT(cord.Chunks(), ElementsAre(s1, s2));
}

TEST_P(CordTest, PrependLargeBuffer) {
  absl::Cord cord;

  std::string s1(700, '1');
  absl::CordBuffer buffer = absl::CordBuffer::CreateWithDefaultLimit(s1.size());
  memcpy(buffer.data(), s1.data(), s1.size());
  buffer.SetLength(s1.size());
  cord.Prepend(std::move(buffer));
  EXPECT_EQ(buffer.length(), 0);    // NOLINT
  EXPECT_GT(buffer.capacity(), 0);  // NOLINT

  std::string s2(1000, '2');
  buffer = absl::CordBuffer::CreateWithDefaultLimit(s2.size());
  memcpy(buffer.data(), s2.data(), s2.size());
  buffer.SetLength(s2.size());
  cord.Prepend(std::move(buffer));
  EXPECT_EQ(buffer.length(), 0);    // NOLINT
  EXPECT_GT(buffer.capacity(), 0);  // NOLINT

  EXPECT_THAT(cord.Chunks(), ElementsAre(s2, s1));
}

class CordAppendBufferTest : public testing::TestWithParam<bool> {
 public:
  size_t is_default() const { return GetParam(); }

  // Returns human readable string representation of the test parameter.
  static std::string ToString(testing::TestParamInfo<bool> param) {
    return param.param ? "DefaultLimit" : "CustomLimit";
  }

  size_t limit() const {
    return is_default() ? absl::CordBuffer::kDefaultLimit
                        : absl::CordBuffer::kCustomLimit;
  }

  size_t maximum_payload() const {
    return is_default() ? absl::CordBuffer::MaximumPayload()
                        : absl::CordBuffer::MaximumPayload(limit());
  }

  absl::CordBuffer GetAppendBuffer(absl::Cord& cord, size_t capacity,
                                   size_t min_capacity = 16) {
    return is_default()
               ? cord.GetAppendBuffer(capacity, min_capacity)
               : cord.GetCustomAppendBuffer(limit(), capacity, min_capacity);
  }
};

INSTANTIATE_TEST_SUITE_P(WithParam, CordAppendBufferTest, testing::Bool(),
                         CordAppendBufferTest::ToString);

TEST_P(CordAppendBufferTest, GetAppendBufferOnEmptyCord) {
  absl::Cord cord;
  absl::CordBuffer buffer = GetAppendBuffer(cord, 1000);
  EXPECT_GE(buffer.capacity(), 1000);
  EXPECT_EQ(buffer.length(), 0);
}

TEST_P(CordAppendBufferTest, GetAppendBufferOnInlinedCord) {
  static constexpr int kInlinedSize = sizeof(absl::CordBuffer) - 1;
  for (int size : {6, kInlinedSize - 3, kInlinedSize - 2, 1000}) {
    absl::Cord cord("Abc");
    absl::CordBuffer buffer = GetAppendBuffer(cord, size, 1);
    EXPECT_GE(buffer.capacity(), 3 + size);
    EXPECT_EQ(buffer.length(), 3);
    EXPECT_EQ(absl::string_view(buffer.data(), buffer.length()), "Abc");
    EXPECT_TRUE(cord.empty());
  }
}

TEST_P(CordAppendBufferTest, GetAppendBufferOnInlinedCordCapacityCloseToMax) {
  // Cover the use case where we have a non empty inlined cord with some size
  // 'n', and ask for something like 'uint64_max - k', assuming internal logic
  // could overflow on 'uint64_max - k + size', and return a valid, but
  // inefficiently smaller buffer if it would provide is the max allowed size.
  for (size_t dist_from_max = 0; dist_from_max <= 4; ++dist_from_max) {
    absl::Cord cord("Abc");
    size_t size = std::numeric_limits<size_t>::max() - dist_from_max;
    absl::CordBuffer buffer = GetAppendBuffer(cord, size, 1);
    EXPECT_GE(buffer.capacity(), maximum_payload());
    EXPECT_EQ(buffer.length(), 3);
    EXPECT_EQ(absl::string_view(buffer.data(), buffer.length()), "Abc");
    EXPECT_TRUE(cord.empty());
  }
}

TEST_P(CordAppendBufferTest, GetAppendBufferOnFlat) {
  // Create a cord with a single flat and extra capacity
  absl::Cord cord;
  absl::CordBuffer buffer = absl::CordBuffer::CreateWithDefaultLimit(500);
  const size_t expected_capacity = buffer.capacity();
  buffer.SetLength(3);
  memcpy(buffer.data(), "Abc", 3);
  cord.Append(std::move(buffer));

  buffer = GetAppendBuffer(cord, 6);
  EXPECT_EQ(buffer.capacity(), expected_capacity);
  EXPECT_EQ(buffer.length(), 3);
  EXPECT_EQ(absl::string_view(buffer.data(), buffer.length()), "Abc");
  EXPECT_TRUE(cord.empty());
}

TEST_P(CordAppendBufferTest, GetAppendBufferOnFlatWithoutMinCapacity) {
  // Create a cord with a single flat and extra capacity
  absl::Cord cord;
  absl::CordBuffer buffer = absl::CordBuffer::CreateWithDefaultLimit(500);
  buffer.SetLength(30);
  memset(buffer.data(), 'x', 30);
  cord.Append(std::move(buffer));

  buffer = GetAppendBuffer(cord, 1000, 900);
  EXPECT_GE(buffer.capacity(), 1000);
  EXPECT_EQ(buffer.length(), 0);
  EXPECT_EQ(cord, std::string(30, 'x'));
}

TEST_P(CordAppendBufferTest, GetAppendBufferOnTree) {
  RandomEngine rng;
  for (int num_flats : {2, 3, 100}) {
    // Create a cord with `num_flats` flats and extra capacity
    absl::Cord cord;
    std::string prefix;
    std::string last;
    for (int i = 0; i < num_flats - 1; ++i) {
      prefix += last;
      last = RandomLowercaseString(&rng, 10);
      absl::CordBuffer buffer = absl::CordBuffer::CreateWithDefaultLimit(500);
      buffer.SetLength(10);
      memcpy(buffer.data(), last.data(), 10);
      cord.Append(std::move(buffer));
    }
    absl::CordBuffer buffer = GetAppendBuffer(cord, 6);
    EXPECT_GE(buffer.capacity(), 500);
    EXPECT_EQ(buffer.length(), 10);
    EXPECT_EQ(absl::string_view(buffer.data(), buffer.length()), last);
    EXPECT_EQ(cord, prefix);
  }
}

TEST_P(CordAppendBufferTest, GetAppendBufferOnTreeWithoutMinCapacity) {
  absl::Cord cord;
  for (int i = 0; i < 2; ++i) {
    absl::CordBuffer buffer = absl::CordBuffer::CreateWithDefaultLimit(500);
    buffer.SetLength(3);
    memcpy(buffer.data(), i ? "def" : "Abc", 3);
    cord.Append(std::move(buffer));
  }
  absl::CordBuffer buffer = GetAppendBuffer(cord, 1000, 900);
  EXPECT_GE(buffer.capacity(), 1000);
  EXPECT_EQ(buffer.length(), 0);
  EXPECT_EQ(cord, "Abcdef");
}

TEST_P(CordAppendBufferTest, GetAppendBufferOnSubstring) {
  // Create a large cord with a single flat and some extra capacity
  absl::Cord cord;
  absl::CordBuffer buffer = absl::CordBuffer::CreateWithDefaultLimit(500);
  buffer.SetLength(450);
  memset(buffer.data(), 'x', 450);
  cord.Append(std::move(buffer));
  cord.RemovePrefix(1);

  // Deny on substring
  buffer = GetAppendBuffer(cord, 6);
  EXPECT_EQ(buffer.length(), 0);
  EXPECT_EQ(cord, std::string(449, 'x'));
}

TEST_P(CordAppendBufferTest, GetAppendBufferOnSharedCord) {
  // Create a shared cord with a single flat and extra capacity
  absl::Cord cord;
  absl::CordBuffer buffer = absl::CordBuffer::CreateWithDefaultLimit(500);
  buffer.SetLength(3);
  memcpy(buffer.data(), "Abc", 3);
  cord.Append(std::move(buffer));
  absl::Cord shared_cord = cord;

  // Deny on flat
  buffer = GetAppendBuffer(cord, 6);
  EXPECT_EQ(buffer.length(), 0);
  EXPECT_EQ(cord, "Abc");

  buffer = absl::CordBuffer::CreateWithDefaultLimit(500);
  buffer.SetLength(3);
  memcpy(buffer.data(), "def", 3);
  cord.Append(std::move(buffer));
  shared_cord = cord;

  // Deny on tree
  buffer = GetAppendBuffer(cord, 6);
  EXPECT_EQ(buffer.length(), 0);
  EXPECT_EQ(cord, "Abcdef");
}

TEST_P(CordTest, TryFlatEmpty) {
  absl::Cord c;
  EXPECT_EQ(c.TryFlat(), "");
}

TEST_P(CordTest, TryFlatFlat) {
  absl::Cord c("hello");
  MaybeHarden(c);
  EXPECT_EQ(c.TryFlat(), "hello");
}

TEST_P(CordTest, TryFlatSubstrInlined) {
  absl::Cord c("hello");
  c.RemovePrefix(1);
  MaybeHarden(c);
  EXPECT_EQ(c.TryFlat(), "ello");
}

TEST_P(CordTest, TryFlatSubstrFlat) {
  absl::Cord c("longer than 15 bytes");
  absl::Cord sub = absl::CordTestPeer::MakeSubstring(c, 1, c.size() - 1);
  MaybeHarden(sub);
  EXPECT_EQ(sub.TryFlat(), "onger than 15 bytes");
}

TEST_P(CordTest, TryFlatConcat) {
  absl::Cord c = absl::MakeFragmentedCord({"hel", "lo"});
  MaybeHarden(c);
  EXPECT_EQ(c.TryFlat(), absl::nullopt);
}

TEST_P(CordTest, TryFlatExternal) {
  absl::Cord c = absl::MakeCordFromExternal("hell", [](absl::string_view) {});
  MaybeHarden(c);
  EXPECT_EQ(c.TryFlat(), "hell");
}

TEST_P(CordTest, TryFlatSubstrExternal) {
  absl::Cord c = absl::MakeCordFromExternal("hell", [](absl::string_view) {});
  absl::Cord sub = absl::CordTestPeer::MakeSubstring(c, 1, c.size() - 1);
  MaybeHarden(sub);
  EXPECT_EQ(sub.TryFlat(), "ell");
}

TEST_P(CordTest, TryFlatCommonlyAssumedInvariants) {
  // The behavior tested below is not part of the API contract of Cord, but it's
  // something we intend to be true in our current implementation.  This test
  // exists to detect and prevent accidental breakage of the implementation.
  absl::string_view fragments[] = {"A fragmented test",
                                   " cord",
                                   " to test subcords",
                                   " of ",
                                   "a",
                                   " cord for",
                                   " each chunk "
                                   "returned by the ",
                                   "iterator"};
  absl::Cord c = absl::MakeFragmentedCord(fragments);
  MaybeHarden(c);
  int fragment = 0;
  int offset = 0;
  absl::Cord::CharIterator itc = c.char_begin();
  for (absl::string_view sv : c.Chunks()) {
    absl::string_view expected = fragments[fragment];
    absl::Cord subcord1 = c.Subcord(offset, sv.length());
    absl::Cord subcord2 = absl::Cord::AdvanceAndRead(&itc, sv.size());
    EXPECT_EQ(subcord1.TryFlat(), expected);
    EXPECT_EQ(subcord2.TryFlat(), expected);
    ++fragment;
    offset += sv.length();
  }
}

static bool IsFlat(const absl::Cord& c) {
  return c.chunk_begin() == c.chunk_end() || ++c.chunk_begin() == c.chunk_end();
}

static void VerifyFlatten(absl::Cord c) {
  std::string old_contents(c);
  absl::string_view old_flat;
  bool already_flat_and_non_empty = IsFlat(c) && !c.empty();
  if (already_flat_and_non_empty) {
    old_flat = *c.chunk_begin();
  }
  absl::string_view new_flat = c.Flatten();

  // Verify that the contents of the flattened Cord are correct.
  EXPECT_EQ(new_flat, old_contents);
  EXPECT_EQ(std::string(c), old_contents);

  // If the Cord contained data and was already flat, verify that the data
  // wasn't copied.
  if (already_flat_and_non_empty) {
    EXPECT_EQ(old_flat.data(), new_flat.data())
        << "Allocated new memory even though the Cord was already flat.";
  }

  // Verify that the flattened Cord is in fact flat.
  EXPECT_TRUE(IsFlat(c));
}

TEST_P(CordTest, Flatten) {
  VerifyFlatten(absl::Cord());
  VerifyFlatten(MaybeHardened(absl::Cord("small cord")));
  VerifyFlatten(
      MaybeHardened(absl::Cord("larger than small buffer optimization")));
  VerifyFlatten(MaybeHardened(
      absl::MakeFragmentedCord({"small ", "fragmented ", "cord"})));

  // Test with a cord that is longer than the largest flat buffer
  RandomEngine rng(GTEST_FLAG_GET(random_seed));
  VerifyFlatten(MaybeHardened(absl::Cord(RandomLowercaseString(&rng, 8192))));
}

// Test data
namespace {
class TestData {
 private:
  std::vector<std::string> data_;

  // Return a std::string of the specified length.
  static std::string MakeString(int length) {
    std::string result;
    char buf[30];
    snprintf(buf, sizeof(buf), "(%d)", length);
    while (result.size() < length) {
      result += buf;
    }
    result.resize(length);
    return result;
  }

 public:
  TestData() {
    // short strings increasing in length by one
    for (int i = 0; i < 30; i++) {
      data_.push_back(MakeString(i));
    }

    // strings around half kMaxFlatLength
    static const int kMaxFlatLength = 4096 - 9;
    static const int kHalf = kMaxFlatLength / 2;

    for (int i = -10; i <= +10; i++) {
      data_.push_back(MakeString(kHalf + i));
    }

    for (int i = -10; i <= +10; i++) {
      data_.push_back(MakeString(kMaxFlatLength + i));
    }
  }

  size_t size() const { return data_.size(); }
  const std::string& data(size_t i) const { return data_[i]; }
};
}  // namespace

TEST_P(CordTest, MultipleLengths) {
  TestData d;
  for (size_t i = 0; i < d.size(); i++) {
    std::string a = d.data(i);

    {  // Construct from Cord
      absl::Cord tmp(a);
      absl::Cord x(tmp);
      MaybeHarden(x);
      EXPECT_EQ(a, std::string(x)) << "'" << a << "'";
    }

    {  // Construct from absl::string_view
      absl::Cord x(a);
      MaybeHarden(x);
      EXPECT_EQ(a, std::string(x)) << "'" << a << "'";
    }

    {  // Append cord to self
      absl::Cord self(a);
      MaybeHarden(self);
      self.Append(self);
      EXPECT_EQ(a + a, std::string(self)) << "'" << a << "' + '" << a << "'";
    }

    {  // Prepend cord to self
      absl::Cord self(a);
      MaybeHarden(self);
      self.Prepend(self);
      EXPECT_EQ(a + a, std::string(self)) << "'" << a << "' + '" << a << "'";
    }

    // Try to append/prepend others
    for (size_t j = 0; j < d.size(); j++) {
      std::string b = d.data(j);

      {  // CopyFrom Cord
        absl::Cord x(a);
        absl::Cord y(b);
        MaybeHarden(x);
        x = y;
        EXPECT_EQ(b, std::string(x)) << "'" << a << "' + '" << b << "'";
      }

      {  // CopyFrom absl::string_view
        absl::Cord x(a);
        MaybeHarden(x);
        x = b;
        EXPECT_EQ(b, std::string(x)) << "'" << a << "' + '" << b << "'";
      }

      {  // Cord::Append(Cord)
        absl::Cord x(a);
        absl::Cord y(b);
        MaybeHarden(x);
        x.Append(y);
        EXPECT_EQ(a + b, std::string(x)) << "'" << a << "' + '" << b << "'";
      }

      {  // Cord::Append(absl::string_view)
        absl::Cord x(a);
        MaybeHarden(x);
        x.Append(b);
        EXPECT_EQ(a + b, std::string(x)) << "'" << a << "' + '" << b << "'";
      }

      {  // Cord::Prepend(Cord)
        absl::Cord x(a);
        absl::Cord y(b);
        MaybeHarden(x);
        x.Prepend(y);
        EXPECT_EQ(b + a, std::string(x)) << "'" << b << "' + '" << a << "'";
      }

      {  // Cord::Prepend(absl::string_view)
        absl::Cord x(a);
        MaybeHarden(x);
        x.Prepend(b);
        EXPECT_EQ(b + a, std::string(x)) << "'" << b << "' + '" << a << "'";
      }
    }
  }
}

namespace {

TEST_P(CordTest, RemoveSuffixWithExternalOrSubstring) {
  absl::Cord cord = absl::MakeCordFromExternal(
      "foo bar baz", [](absl::string_view s) { DoNothing(s, nullptr); });
  EXPECT_EQ("foo bar baz", std::string(cord));

  MaybeHarden(cord);

  // This RemoveSuffix() will wrap the EXTERNAL node in a SUBSTRING node.
  cord.RemoveSuffix(4);
  EXPECT_EQ("foo bar", std::string(cord));

  MaybeHarden(cord);

  // This RemoveSuffix() will adjust the SUBSTRING node in-place.
  cord.RemoveSuffix(4);
  EXPECT_EQ("foo", std::string(cord));
}

TEST_P(CordTest, RemoveSuffixMakesZeroLengthNode) {
  absl::Cord c;
  c.Append(absl::Cord(std::string(100, 'x')));
  absl::Cord other_ref = c;  // Prevent inplace appends
  EXPECT_THAT(other_ref, testing::Eq(c));
  MaybeHarden(c);
  c.Append(absl::Cord(std::string(200, 'y')));
  c.RemoveSuffix(200);
  EXPECT_EQ(std::string(100, 'x'), std::string(c));
}

}  // namespace

// CordSpliceTest contributed by hendrie.
namespace {

// Create a cord with an external memory block filled with 'z'
absl::Cord CordWithZedBlock(size_t size) {
  char* data = new char[size];
  if (size > 0) {
    memset(data, 'z', size);
  }
  absl::Cord cord = absl::MakeCordFromExternal(
      absl::string_view(data, size),
      [](absl::string_view s) { delete[] s.data(); });
  return cord;
}

// Establish that ZedBlock does what we think it does.
TEST_P(CordTest, CordSpliceTestZedBlock) {
  absl::Cord blob = CordWithZedBlock(10);
  MaybeHarden(blob);
  EXPECT_EQ(10, blob.size());
  std::string s;
  absl::CopyCordToString(blob, &s);
  EXPECT_EQ("zzzzzzzzzz", s);
}

TEST_P(CordTest, CordSpliceTestZedBlock0) {
  absl::Cord blob = CordWithZedBlock(0);
  MaybeHarden(blob);
  EXPECT_EQ(0, blob.size());
  std::string s;
  absl::CopyCordToString(blob, &s);
  EXPECT_EQ("", s);
}

TEST_P(CordTest, CordSpliceTestZedBlockSuffix1) {
  absl::Cord blob = CordWithZedBlock(10);
  MaybeHarden(blob);
  EXPECT_EQ(10, blob.size());
  absl::Cord suffix(blob);
  suffix.RemovePrefix(9);
  EXPECT_EQ(1, suffix.size());
  std::string s;
  absl::CopyCordToString(suffix, &s);
  EXPECT_EQ("z", s);
}

// Remove all of a prefix block
TEST_P(CordTest, CordSpliceTestZedBlockSuffix0) {
  absl::Cord blob = CordWithZedBlock(10);
  MaybeHarden(blob);
  EXPECT_EQ(10, blob.size());
  absl::Cord suffix(blob);
  suffix.RemovePrefix(10);
  EXPECT_EQ(0, suffix.size());
  std::string s;
  absl::CopyCordToString(suffix, &s);
  EXPECT_EQ("", s);
}

absl::Cord BigCord(size_t len, char v) {
  std::string s(len, v);
  return absl::Cord(s);
}

// Splice block into cord.
absl::Cord SpliceCord(const absl::Cord& blob, int64_t offset,
                      const absl::Cord& block) {
  CHECK_GE(offset, 0);
  CHECK_LE(static_cast<size_t>(offset) + block.size(), blob.size());
  absl::Cord result(blob);
  result.RemoveSuffix(blob.size() - offset);
  result.Append(block);
  absl::Cord suffix(blob);
  suffix.RemovePrefix(offset + block.size());
  result.Append(suffix);
  CHECK_EQ(blob.size(), result.size());
  return result;
}

// Taking an empty suffix of a block breaks appending.
TEST_P(CordTest, CordSpliceTestRemoveEntireBlock1) {
  absl::Cord zero = CordWithZedBlock(10);
  MaybeHarden(zero);
  absl::Cord suffix(zero);
  suffix.RemovePrefix(10);
  absl::Cord result;
  result.Append(suffix);
}

TEST_P(CordTest, CordSpliceTestRemoveEntireBlock2) {
  absl::Cord zero = CordWithZedBlock(10);
  MaybeHarden(zero);
  absl::Cord prefix(zero);
  prefix.RemoveSuffix(10);
  absl::Cord suffix(zero);
  suffix.RemovePrefix(10);
  absl::Cord result(prefix);
  result.Append(suffix);
}

TEST_P(CordTest, CordSpliceTestRemoveEntireBlock3) {
  absl::Cord blob = CordWithZedBlock(10);
  absl::Cord block = BigCord(10, 'b');
  MaybeHarden(blob);
  MaybeHarden(block);
  blob = SpliceCord(blob, 0, block);
}

struct CordCompareTestCase {
  template <typename LHS, typename RHS>
  CordCompareTestCase(const LHS& lhs, const RHS& rhs, bool use_crc)
      : lhs_cord(lhs), rhs_cord(rhs) {
    if (use_crc) {
      lhs_cord.SetExpectedChecksum(1);
    }
  }

  absl::Cord lhs_cord;
  absl::Cord rhs_cord;
};

const auto sign = [](int x) { return x == 0 ? 0 : (x > 0 ? 1 : -1); };

void VerifyComparison(const CordCompareTestCase& test_case) {
  std::string lhs_string(test_case.lhs_cord);
  std::string rhs_string(test_case.rhs_cord);
  int expected = sign(lhs_string.compare(rhs_string));
  EXPECT_EQ(expected, test_case.lhs_cord.Compare(test_case.rhs_cord))
      << "LHS=" << lhs_string << "; RHS=" << rhs_string;
  EXPECT_EQ(expected, test_case.lhs_cord.Compare(rhs_string))
      << "LHS=" << lhs_string << "; RHS=" << rhs_string;
  EXPECT_EQ(-expected, test_case.rhs_cord.Compare(test_case.lhs_cord))
      << "LHS=" << rhs_string << "; RHS=" << lhs_string;
  EXPECT_EQ(-expected, test_case.rhs_cord.Compare(lhs_string))
      << "LHS=" << rhs_string << "; RHS=" << lhs_string;
}

TEST_P(CordTest, Compare) {
  absl::Cord subcord("aaaaaBBBBBcccccDDDDD");
  subcord = subcord.Subcord(3, 10);

  absl::Cord tmp("aaaaaaaaaaaaaaaa");
  tmp.Append("BBBBBBBBBBBBBBBB");
  absl::Cord concat = absl::Cord("cccccccccccccccc");
  concat.Append("DDDDDDDDDDDDDDDD");
  concat.Prepend(tmp);

  absl::Cord concat2("aaaaaaaaaaaaa");
  concat2.Append("aaaBBBBBBBBBBBBBBBBccccc");
  concat2.Append("cccccccccccDDDDDDDDDDDDDD");
  concat2.Append("DD");

  const bool use_crc = UseCrc();

  std::vector<CordCompareTestCase> test_cases = {{
      // Inline cords
      {"abcdef", "abcdef", use_crc},
      {"abcdef", "abcdee", use_crc},
      {"abcdef", "abcdeg", use_crc},
      {"bbcdef", "abcdef", use_crc},
      {"bbcdef", "abcdeg", use_crc},
      {"abcdefa", "abcdef", use_crc},
      {"abcdef", "abcdefa", use_crc},

      // Small flat cords
      {"aaaaaBBBBBcccccDDDDD", "aaaaaBBBBBcccccDDDDD", use_crc},
      {"aaaaaBBBBBcccccDDDDD", "aaaaaBBBBBxccccDDDDD", use_crc},
      {"aaaaaBBBBBcxcccDDDDD", "aaaaaBBBBBcccccDDDDD", use_crc},
      {"aaaaaBBBBBxccccDDDDD", "aaaaaBBBBBcccccDDDDX", use_crc},
      {"aaaaaBBBBBcccccDDDDDa", "aaaaaBBBBBcccccDDDDD", use_crc},
      {"aaaaaBBBBBcccccDDDDD", "aaaaaBBBBBcccccDDDDDa", use_crc},

      // Subcords
      {subcord, subcord, use_crc},
      {subcord, "aaBBBBBccc", use_crc},
      {subcord, "aaBBBBBccd", use_crc},
      {subcord, "aaBBBBBccb", use_crc},
      {subcord, "aaBBBBBxcb", use_crc},
      {subcord, "aaBBBBBccca", use_crc},
      {subcord, "aaBBBBBcc", use_crc},

      // Concats
      {concat, concat, use_crc},
      {concat,
       "aaaaaaaaaaaaaaaaBBBBBBBBBBBBBBBBccccccccccccccccDDDDDDDDDDDDDDDD",
       use_crc},
      {concat,
       "aaaaaaaaaaaaaaaaBBBBBBBBBBBBBBBBcccccccccccccccxDDDDDDDDDDDDDDDD",
       use_crc},
      {concat,
       "aaaaaaaaaaaaaaaaBBBBBBBBBBBBBBBBacccccccccccccccDDDDDDDDDDDDDDDD",
       use_crc},
      {concat,
       "aaaaaaaaaaaaaaaaBBBBBBBBBBBBBBBBccccccccccccccccDDDDDDDDDDDDDDD",
       use_crc},
      {concat,
       "aaaaaaaaaaaaaaaaBBBBBBBBBBBBBBBBccccccccccccccccDDDDDDDDDDDDDDDDe",
       use_crc},

      {concat, concat2, use_crc},
  }};

  for (const auto& tc : test_cases) {
    VerifyComparison(tc);
  }
}

TEST_P(CordTest, CompareAfterAssign) {
  absl::Cord a("aaaaaa1111111");
  absl::Cord b("aaaaaa2222222");
  MaybeHarden(a);
  a = "cccccc";
  b = "cccccc";
  EXPECT_EQ(a, b);
  EXPECT_FALSE(a < b);

  a = "aaaa";
  b = "bbbbb";
  a = "";
  b = "";
  EXPECT_EQ(a, b);
  EXPECT_FALSE(a < b);
}

// Test CompareTo() and ComparePrefix() against string and substring
// comparison methods from basic_string.
static void TestCompare(const absl::Cord& c, const absl::Cord& d,
                        RandomEngine* rng) {
  // char_traits<char>::lt is guaranteed to do an unsigned comparison:
  // https://en.cppreference.com/w/cpp/string/char_traits/cmp. We also expect
  // Cord comparisons to be based on unsigned byte comparisons regardless of
  // whether char is signed.
  int expected = sign(std::string(c).compare(std::string(d)));
  EXPECT_EQ(expected, sign(c.Compare(d))) << c << ", " << d;
}

TEST_P(CordTest, CompareComparisonIsUnsigned) {
  RandomEngine rng(GTEST_FLAG_GET(random_seed));
  std::uniform_int_distribution<uint32_t> uniform_uint8(0, 255);
  char x = static_cast<char>(uniform_uint8(rng));
  TestCompare(
      absl::Cord(std::string(GetUniformRandomUpTo(&rng, 100), x)),
      absl::Cord(std::string(GetUniformRandomUpTo(&rng, 100), x ^ 0x80)), &rng);
}

TEST_P(CordTest, CompareRandomComparisons) {
  const int kIters = 5000;
  RandomEngine rng(GTEST_FLAG_GET(random_seed));

  int n = GetUniformRandomUpTo(&rng, 5000);
  absl::Cord a[] = {MakeExternalCord(n),
                    absl::Cord("ant"),
                    absl::Cord("elephant"),
                    absl::Cord("giraffe"),
                    absl::Cord(std::string(GetUniformRandomUpTo(&rng, 100),
                                           GetUniformRandomUpTo(&rng, 100))),
                    absl::Cord(""),
                    absl::Cord("x"),
                    absl::Cord("A"),
                    absl::Cord("B"),
                    absl::Cord("C")};
  for (int i = 0; i < kIters; i++) {
    absl::Cord c, d;
    for (int j = 0; j < (i % 7) + 1; j++) {
      c.Append(a[GetUniformRandomUpTo(&rng, ABSL_ARRAYSIZE(a))]);
      d.Append(a[GetUniformRandomUpTo(&rng, ABSL_ARRAYSIZE(a))]);
    }
    std::bernoulli_distribution coin_flip(0.5);
    MaybeHarden(c);
    MaybeHarden(d);
    TestCompare(coin_flip(rng) ? c : absl::Cord(std::string(c)),
                coin_flip(rng) ? d : absl::Cord(std::string(d)), &rng);
  }
}

template <typename T1, typename T2>
void CompareOperators() {
  const T1 a("a");
  const T2 b("b");

  EXPECT_TRUE(a == a);
  // For pointer type (i.e. `const char*`), operator== compares the address
  // instead of the string, so `a == const char*("a")` isn't necessarily true.
  EXPECT_TRUE(std::is_pointer<T1>::value || a == T1("a"));
  EXPECT_TRUE(std::is_pointer<T2>::value || a == T2("a"));
  EXPECT_FALSE(a == b);

  EXPECT_TRUE(a != b);
  EXPECT_FALSE(a != a);

  EXPECT_TRUE(a < b);
  EXPECT_FALSE(b < a);

  EXPECT_TRUE(b > a);
  EXPECT_FALSE(a > b);

  EXPECT_TRUE(a >= a);
  EXPECT_TRUE(b >= a);
  EXPECT_FALSE(a >= b);

  EXPECT_TRUE(a <= a);
  EXPECT_TRUE(a <= b);
  EXPECT_FALSE(b <= a);
}

TEST_P(CordTest, ComparisonOperators_Cord_Cord) {
  CompareOperators<absl::Cord, absl::Cord>();
}

TEST_P(CordTest, ComparisonOperators_Cord_StringPiece) {
  CompareOperators<absl::Cord, absl::string_view>();
}

TEST_P(CordTest, ComparisonOperators_StringPiece_Cord) {
  CompareOperators<absl::string_view, absl::Cord>();
}

TEST_P(CordTest, ComparisonOperators_Cord_string) {
  CompareOperators<absl::Cord, std::string>();
}

TEST_P(CordTest, ComparisonOperators_string_Cord) {
  CompareOperators<std::string, absl::Cord>();
}

TEST_P(CordTest, ComparisonOperators_stdstring_Cord) {
  CompareOperators<std::string, absl::Cord>();
}

TEST_P(CordTest, ComparisonOperators_Cord_stdstring) {
  CompareOperators<absl::Cord, std::string>();
}

TEST_P(CordTest, ComparisonOperators_charstar_Cord) {
  CompareOperators<const char*, absl::Cord>();
}

TEST_P(CordTest, ComparisonOperators_Cord_charstar) {
  CompareOperators<absl::Cord, const char*>();
}

TEST_P(CordTest, ConstructFromExternalReleaserInvoked) {
  // Empty external memory means the releaser should be called immediately.
  {
    bool invoked = false;
    auto releaser = [&invoked](absl::string_view) { invoked = true; };
    {
      auto c = absl::MakeCordFromExternal("", releaser);
      EXPECT_THAT(c, testing::Eq(""));
      EXPECT_TRUE(invoked);
    }
  }

  // If the size of the data is small enough, a future constructor
  // implementation may copy the bytes and immediately invoke the releaser
  // instead of creating an external node. We make a large dummy std::string to
  // make this test independent of such an optimization.
  std::string large_dummy(2048, 'c');
  {
    bool invoked = false;
    auto releaser = [&invoked](absl::string_view) { invoked = true; };
    {
      auto c = absl::MakeCordFromExternal(large_dummy, releaser);
      EXPECT_THAT(c, testing::Eq(large_dummy));
      EXPECT_FALSE(invoked);
    }
    EXPECT_TRUE(invoked);
  }

  {
    bool invoked = false;
    auto releaser = [&invoked](absl::string_view) { invoked = true; };
    {
      absl::Cord copy;
      {
        auto c = absl::MakeCordFromExternal(large_dummy, releaser);
        copy = c;
        EXPECT_FALSE(invoked);
      }
      EXPECT_FALSE(invoked);
    }
    EXPECT_TRUE(invoked);
  }
}

TEST_P(CordTest, ConstructFromExternalCompareContents) {
  RandomEngine rng(GTEST_FLAG_GET(random_seed));

  for (int length = 1; length <= 2048; length *= 2) {
    std::string data = RandomLowercaseString(&rng, length);
    auto* external = new std::string(data);
    auto cord =
        absl::MakeCordFromExternal(*external, [external](absl::string_view sv) {
          EXPECT_EQ(external->data(), sv.data());
          EXPECT_EQ(external->size(), sv.size());
          delete external;
        });
    MaybeHarden(cord);
    EXPECT_EQ(data, cord);
  }
}

TEST_P(CordTest, ConstructFromExternalLargeReleaser) {
  RandomEngine rng(GTEST_FLAG_GET(random_seed));
  constexpr size_t kLength = 256;
  std::string data = RandomLowercaseString(&rng, kLength);
  std::array<char, kLength> data_array;
  for (size_t i = 0; i < kLength; ++i) data_array[i] = data[i];
  bool invoked = false;
  auto releaser = [data_array, &invoked](absl::string_view data) {
    EXPECT_EQ(data, absl::string_view(data_array.data(), data_array.size()));
    invoked = true;
  };
  (void)MaybeHardened(absl::MakeCordFromExternal(data, releaser));
  EXPECT_TRUE(invoked);
}

TEST_P(CordTest, ConstructFromExternalFunctionPointerReleaser) {
  static absl::string_view data("hello world");
  static bool invoked;
  auto* releaser =
      static_cast<void (*)(absl::string_view)>([](absl::string_view sv) {
        EXPECT_EQ(data, sv);
        invoked = true;
      });
  invoked = false;
  (void)MaybeHardened(absl::MakeCordFromExternal(data, releaser));
  EXPECT_TRUE(invoked);

  invoked = false;
  (void)MaybeHardened(absl::MakeCordFromExternal(data, *releaser));
  EXPECT_TRUE(invoked);
}

TEST_P(CordTest, ConstructFromExternalMoveOnlyReleaser) {
  struct Releaser {
    explicit Releaser(bool* invoked) : invoked(invoked) {}
    Releaser(Releaser&& other) noexcept : invoked(other.invoked) {}
    void operator()(absl::string_view) const { *invoked = true; }

    bool* invoked;
  };

  bool invoked = false;
  (void)MaybeHardened(absl::MakeCordFromExternal("dummy", Releaser(&invoked)));
  EXPECT_TRUE(invoked);
}

TEST_P(CordTest, ConstructFromExternalNoArgLambda) {
  bool invoked = false;
  (void)MaybeHardened(
      absl::MakeCordFromExternal("dummy", [&invoked]() { invoked = true; }));
  EXPECT_TRUE(invoked);
}

TEST_P(CordTest, ConstructFromExternalStringViewArgLambda) {
  bool invoked = false;
  (void)MaybeHardened(absl::MakeCordFromExternal(
      "dummy", [&invoked](absl::string_view) { invoked = true; }));
  EXPECT_TRUE(invoked);
}

TEST_P(CordTest, ConstructFromExternalNonTrivialReleaserDestructor) {
  struct Releaser {
    explicit Releaser(bool* destroyed) : destroyed(destroyed) {}
    ~Releaser() { *destroyed = true; }
    void operator()(absl::string_view) const {}

    bool* destroyed;
  };

  bool destroyed = false;
  Releaser releaser(&destroyed);
  (void)MaybeHardened(absl::MakeCordFromExternal("dummy", releaser));
  EXPECT_TRUE(destroyed);
}

TEST_P(CordTest, ConstructFromExternalReferenceQualifierOverloads) {
  enum InvokedAs { kMissing, kLValue, kRValue };
  enum CopiedAs { kNone, kMove, kCopy };
  struct Tracker {
    CopiedAs copied_as = kNone;
    InvokedAs invoked_as = kMissing;

    void Record(InvokedAs rhs) {
      ASSERT_EQ(invoked_as, kMissing);
      invoked_as = rhs;
    }

    void Record(CopiedAs rhs) {
      if (copied_as == kNone || rhs == kCopy) copied_as = rhs;
    }
  } tracker;

  class Releaser {
   public:
    explicit Releaser(Tracker* tracker) : tr_(tracker) { *tracker = Tracker(); }
    Releaser(Releaser&& rhs) : tr_(rhs.tr_) { tr_->Record(kMove); }
    Releaser(const Releaser& rhs) : tr_(rhs.tr_) { tr_->Record(kCopy); }

    void operator()(absl::string_view) & { tr_->Record(kLValue); }
    void operator()(absl::string_view) && { tr_->Record(kRValue); }

   private:
    Tracker* tr_;
  };

  const Releaser releaser1(&tracker);
  (void)MaybeHardened(absl::MakeCordFromExternal("", releaser1));
  EXPECT_EQ(tracker.copied_as, kCopy);
  EXPECT_EQ(tracker.invoked_as, kRValue);

  const Releaser releaser2(&tracker);
  (void)MaybeHardened(absl::MakeCordFromExternal("", releaser2));
  EXPECT_EQ(tracker.copied_as, kCopy);
  EXPECT_EQ(tracker.invoked_as, kRValue);

  Releaser releaser3(&tracker);
  (void)MaybeHardened(absl::MakeCordFromExternal("", std::move(releaser3)));
  EXPECT_EQ(tracker.copied_as, kMove);
  EXPECT_EQ(tracker.invoked_as, kRValue);

  Releaser releaser4(&tracker);
  (void)MaybeHardened(absl::MakeCordFromExternal("dummy", releaser4));
  EXPECT_EQ(tracker.copied_as, kCopy);
  EXPECT_EQ(tracker.invoked_as, kRValue);

  const Releaser releaser5(&tracker);
  (void)MaybeHardened(absl::MakeCordFromExternal("dummy", releaser5));
  EXPECT_EQ(tracker.copied_as, kCopy);
  EXPECT_EQ(tracker.invoked_as, kRValue);

  Releaser releaser6(&tracker);
  (void)MaybeHardened(absl::MakeCordFromExternal("foo", std::move(releaser6)));
  EXPECT_EQ(tracker.copied_as, kMove);
  EXPECT_EQ(tracker.invoked_as, kRValue);
}

TEST_P(CordTest, ExternalMemoryBasicUsage) {
  static const char* strings[] = {"", "hello", "there"};
  for (const char* str : strings) {
    absl::Cord dst("(prefix)");
    MaybeHarden(dst);
    AddExternalMemory(str, &dst);
    MaybeHarden(dst);
    dst.Append("(suffix)");
    EXPECT_EQ((std::string("(prefix)") + str + std::string("(suffix)")),
              std::string(dst));
  }
}

TEST_P(CordTest, ExternalMemoryRemovePrefixSuffix) {
  // Exhaustively try all sub-strings.
  absl::Cord cord = MakeComposite();
  std::string s = std::string(cord);
  for (int offset = 0; offset <= s.size(); offset++) {
    for (int length = 0; length <= s.size() - offset; length++) {
      absl::Cord result(cord);
      MaybeHarden(result);
      result.RemovePrefix(offset);
      MaybeHarden(result);
      result.RemoveSuffix(result.size() - length);
      EXPECT_EQ(s.substr(offset, length), std::string(result))
          << offset << " " << length;
    }
  }
}

TEST_P(CordTest, ExternalMemoryGet) {
  absl::Cord cord("hello");
  AddExternalMemory(" world!", &cord);
  MaybeHarden(cord);
  AddExternalMemory(" how are ", &cord);
  cord.Append(" you?");
  MaybeHarden(cord);
  std::string s = std::string(cord);
  for (int i = 0; i < s.size(); i++) {
    EXPECT_EQ(s[i], cord[i]);
  }
}

// CordMemoryUsage tests verify the correctness of the EstimatedMemoryUsage()
// We use whiteboxed expectations based on our knowledge of the layout and size
// of empty and inlined cords, and flat nodes.

constexpr auto kFairShare = absl::CordMemoryAccounting::kFairShare;
constexpr auto kTotalMorePrecise =
    absl::CordMemoryAccounting::kTotalMorePrecise;

// Creates a cord of `n` `c` values, making sure no string stealing occurs.
absl::Cord MakeCord(size_t n, char c) {
  const std::string s(n, c);
  return absl::Cord(s);
}

TEST(CordTest, CordMemoryUsageEmpty) {
  absl::Cord cord;
  EXPECT_EQ(sizeof(absl::Cord), cord.EstimatedMemoryUsage());
  EXPECT_EQ(sizeof(absl::Cord), cord.EstimatedMemoryUsage(kFairShare));
  EXPECT_EQ(sizeof(absl::Cord), cord.EstimatedMemoryUsage(kTotalMorePrecise));
}

TEST(CordTest, CordMemoryUsageInlined) {
  absl::Cord a("hello");
  EXPECT_EQ(a.EstimatedMemoryUsage(), sizeof(absl::Cord));
  EXPECT_EQ(a.EstimatedMemoryUsage(kFairShare), sizeof(absl::Cord));
  EXPECT_EQ(a.EstimatedMemoryUsage(kTotalMorePrecise), sizeof(absl::Cord));
}

TEST(CordTest, CordMemoryUsageExternalMemory) {
  absl::Cord cord;
  AddExternalMemory(std::string(1000, 'x'), &cord);
  const size_t expected =
      sizeof(absl::Cord) + 1000 + sizeof(CordRepExternal) + sizeof(intptr_t);
  EXPECT_EQ(cord.EstimatedMemoryUsage(), expected);
  EXPECT_EQ(cord.EstimatedMemoryUsage(kFairShare), expected);
  EXPECT_EQ(cord.EstimatedMemoryUsage(kTotalMorePrecise), expected);
}

TEST(CordTest, CordMemoryUsageFlat) {
  absl::Cord cord = MakeCord(1000, 'a');
  const size_t flat_size =
      absl::CordTestPeer::Tree(cord)->flat()->AllocatedSize();
  EXPECT_EQ(cord.EstimatedMemoryUsage(), sizeof(absl::Cord) + flat_size);
  EXPECT_EQ(cord.EstimatedMemoryUsage(kFairShare),
            sizeof(absl::Cord) + flat_size);
  EXPECT_EQ(cord.EstimatedMemoryUsage(kTotalMorePrecise),
            sizeof(absl::Cord) + flat_size);
}

TEST(CordTest, CordMemoryUsageSubStringSharedFlat) {
  absl::Cord flat = MakeCord(2000, 'a');
  const size_t flat_size =
      absl::CordTestPeer::Tree(flat)->flat()->AllocatedSize();
  absl::Cord cord = flat.Subcord(500, 1000);
  EXPECT_EQ(cord.EstimatedMemoryUsage(),
            sizeof(absl::Cord) + sizeof(CordRepSubstring) + flat_size);
  EXPECT_EQ(cord.EstimatedMemoryUsage(kTotalMorePrecise),
            sizeof(absl::Cord) + sizeof(CordRepSubstring) + flat_size);
  EXPECT_EQ(cord.EstimatedMemoryUsage(kFairShare),
            sizeof(absl::Cord) + sizeof(CordRepSubstring) + flat_size / 2);
}

TEST(CordTest, CordMemoryUsageFlatShared) {
  absl::Cord shared = MakeCord(1000, 'a');
  absl::Cord cord(shared);
  const size_t flat_size =
      absl::CordTestPeer::Tree(cord)->flat()->AllocatedSize();
  EXPECT_EQ(cord.EstimatedMemoryUsage(), sizeof(absl::Cord) + flat_size);
  EXPECT_EQ(cord.EstimatedMemoryUsage(kTotalMorePrecise),
            sizeof(absl::Cord) + flat_size);
  EXPECT_EQ(cord.EstimatedMemoryUsage(kFairShare),
            sizeof(absl::Cord) + flat_size / 2);
}

TEST(CordTest, CordMemoryUsageFlatHardenedAndShared) {
  absl::Cord shared = MakeCord(1000, 'a');
  absl::Cord cord(shared);
  const size_t flat_size =
      absl::CordTestPeer::Tree(cord)->flat()->AllocatedSize();
  cord.SetExpectedChecksum(1);
  EXPECT_EQ(cord.EstimatedMemoryUsage(),
            sizeof(absl::Cord) + sizeof(CordRepCrc) + flat_size);
  EXPECT_EQ(cord.EstimatedMemoryUsage(kFairShare),
--> --------------------

--> maximum size reached

--> --------------------