1 #include "absl/strings/cord.h"
2
3 #include <algorithm>
4 #include <climits>
5 #include <cstdio>
6 #include <iterator>
7 #include <map>
8 #include <numeric>
9 #include <random>
10 #include <sstream>
11 #include <type_traits>
12 #include <utility>
13 #include <vector>
14
15 #include "gmock/gmock.h"
16 #include "gtest/gtest.h"
17 #include "absl/base/casts.h"
18 #include "absl/base/config.h"
19 #include "absl/base/internal/endian.h"
20 #include "absl/base/internal/raw_logging.h"
21 #include "absl/base/macros.h"
22 #include "absl/container/fixed_array.h"
23 #include "absl/strings/cord_test_helpers.h"
24 #include "absl/strings/str_cat.h"
25 #include "absl/strings/str_format.h"
26 #include "absl/strings/string_view.h"
27
28 typedef std::mt19937_64 RandomEngine;
29
30 static std::string RandomLowercaseString(RandomEngine* rng);
31 static std::string RandomLowercaseString(RandomEngine* rng, size_t length);
32
GetUniformRandomUpTo(RandomEngine * rng,int upper_bound)33 static int GetUniformRandomUpTo(RandomEngine* rng, int upper_bound) {
34 if (upper_bound > 0) {
35 std::uniform_int_distribution<int> uniform(0, upper_bound - 1);
36 return uniform(*rng);
37 } else {
38 return 0;
39 }
40 }
41
GetUniformRandomUpTo(RandomEngine * rng,size_t upper_bound)42 static size_t GetUniformRandomUpTo(RandomEngine* rng, size_t upper_bound) {
43 if (upper_bound > 0) {
44 std::uniform_int_distribution<size_t> uniform(0, upper_bound - 1);
45 return uniform(*rng);
46 } else {
47 return 0;
48 }
49 }
50
GenerateSkewedRandom(RandomEngine * rng,int max_log)51 static int32_t GenerateSkewedRandom(RandomEngine* rng, int max_log) {
52 const uint32_t base = (*rng)() % (max_log + 1);
53 const uint32_t mask = ((base < 32) ? (1u << base) : 0u) - 1u;
54 return (*rng)() & mask;
55 }
56
RandomLowercaseString(RandomEngine * rng)57 static std::string RandomLowercaseString(RandomEngine* rng) {
58 int length;
59 std::bernoulli_distribution one_in_1k(0.001);
60 std::bernoulli_distribution one_in_10k(0.0001);
61 // With low probability, make a large fragment
62 if (one_in_10k(*rng)) {
63 length = GetUniformRandomUpTo(rng, 1048576);
64 } else if (one_in_1k(*rng)) {
65 length = GetUniformRandomUpTo(rng, 10000);
66 } else {
67 length = GenerateSkewedRandom(rng, 10);
68 }
69 return RandomLowercaseString(rng, length);
70 }
71
RandomLowercaseString(RandomEngine * rng,size_t length)72 static std::string RandomLowercaseString(RandomEngine* rng, size_t length) {
73 std::string result(length, '\0');
74 std::uniform_int_distribution<int> chars('a', 'z');
75 std::generate(result.begin(), result.end(),
76 [&]() { return static_cast<char>(chars(*rng)); });
77 return result;
78 }
79
DoNothing(absl::string_view,void *)80 static void DoNothing(absl::string_view /* data */, void* /* arg */) {}
81
DeleteExternalString(absl::string_view data,void * arg)82 static void DeleteExternalString(absl::string_view data, void* arg) {
83 std::string* s = reinterpret_cast<std::string*>(arg);
84 EXPECT_EQ(data, *s);
85 delete s;
86 }
87
88 // Add "s" to *dst via `MakeCordFromExternal`
AddExternalMemory(absl::string_view s,absl::Cord * dst)89 static void AddExternalMemory(absl::string_view s, absl::Cord* dst) {
90 std::string* str = new std::string(s.data(), s.size());
91 dst->Append(absl::MakeCordFromExternal(*str, [str](absl::string_view data) {
92 DeleteExternalString(data, str);
93 }));
94 }
95
DumpGrowth()96 static void DumpGrowth() {
97 absl::Cord str;
98 for (int i = 0; i < 1000; i++) {
99 char c = 'a' + i % 26;
100 str.Append(absl::string_view(&c, 1));
101 }
102 }
103
104 // Make a Cord with some number of fragments. Return the size (in bytes)
105 // of the smallest fragment.
AppendWithFragments(const std::string & s,RandomEngine * rng,absl::Cord * cord)106 static size_t AppendWithFragments(const std::string& s, RandomEngine* rng,
107 absl::Cord* cord) {
108 size_t j = 0;
109 const size_t max_size = s.size() / 5; // Make approx. 10 fragments
110 size_t min_size = max_size; // size of smallest fragment
111 while (j < s.size()) {
112 size_t N = 1 + GetUniformRandomUpTo(rng, max_size);
113 if (N > (s.size() - j)) {
114 N = s.size() - j;
115 }
116 if (N < min_size) {
117 min_size = N;
118 }
119
120 std::bernoulli_distribution coin_flip(0.5);
121 if (coin_flip(*rng)) {
122 // Grow by adding an external-memory.
123 AddExternalMemory(absl::string_view(s.data() + j, N), cord);
124 } else {
125 cord->Append(absl::string_view(s.data() + j, N));
126 }
127 j += N;
128 }
129 return min_size;
130 }
131
132 // Add an external memory that contains the specified std::string to cord
AddNewStringBlock(const std::string & str,absl::Cord * dst)133 static void AddNewStringBlock(const std::string& str, absl::Cord* dst) {
134 char* data = new char[str.size()];
135 memcpy(data, str.data(), str.size());
136 dst->Append(absl::MakeCordFromExternal(
137 absl::string_view(data, str.size()),
138 [](absl::string_view s) { delete[] s.data(); }));
139 }
140
141 // Make a Cord out of many different types of nodes.
MakeComposite()142 static absl::Cord MakeComposite() {
143 absl::Cord cord;
144 cord.Append("the");
145 AddExternalMemory(" quick brown", &cord);
146 AddExternalMemory(" fox jumped", &cord);
147
148 absl::Cord full(" over");
149 AddExternalMemory(" the lazy", &full);
150 AddNewStringBlock(" dog slept the whole day away", &full);
151 absl::Cord substring = full.Subcord(0, 18);
152
153 // Make substring long enough to defeat the copying fast path in Append.
154 substring.Append(std::string(1000, '.'));
155 cord.Append(substring);
156 cord = cord.Subcord(0, cord.size() - 998); // Remove most of extra junk
157
158 return cord;
159 }
160
161 namespace absl {
162 ABSL_NAMESPACE_BEGIN
163
164 class CordTestPeer {
165 public:
ForEachChunk(const Cord & c,absl::FunctionRef<void (absl::string_view)> callback)166 static void ForEachChunk(
167 const Cord& c, absl::FunctionRef<void(absl::string_view)> callback) {
168 c.ForEachChunk(callback);
169 }
170 };
171
172 ABSL_NAMESPACE_END
173 } // namespace absl
174
TEST(Cord,AllFlatSizes)175 TEST(Cord, AllFlatSizes) {
176 using absl::strings_internal::CordTestAccess;
177
178 for (size_t s = 0; s < CordTestAccess::MaxFlatLength(); s++) {
179 // Make a string of length s.
180 std::string src;
181 while (src.size() < s) {
182 src.push_back('a' + (src.size() % 26));
183 }
184
185 absl::Cord dst(src);
186 EXPECT_EQ(std::string(dst), src) << s;
187 }
188 }
189
190 // We create a Cord at least 128GB in size using the fact that Cords can
191 // internally reference-count; thus the Cord is enormous without actually
192 // consuming very much memory.
TEST(GigabyteCord,FromExternal)193 TEST(GigabyteCord, FromExternal) {
194 const size_t one_gig = 1024U * 1024U * 1024U;
195 size_t max_size = 2 * one_gig;
196 if (sizeof(max_size) > 4) max_size = 128 * one_gig;
197
198 size_t length = 128 * 1024;
199 char* data = new char[length];
200 absl::Cord from = absl::MakeCordFromExternal(
201 absl::string_view(data, length),
202 [](absl::string_view sv) { delete[] sv.data(); });
203
204 // This loop may seem odd due to its combination of exponential doubling of
205 // size and incremental size increases. We do it incrementally to be sure the
206 // Cord will need rebalancing and will exercise code that, in the past, has
207 // caused crashes in production. We grow exponentially so that the code will
208 // execute in a reasonable amount of time.
209 absl::Cord c;
210 ABSL_RAW_LOG(INFO, "Made a Cord with %zu bytes!", c.size());
211 c.Append(from);
212 while (c.size() < max_size) {
213 c.Append(c);
214 c.Append(from);
215 c.Append(from);
216 c.Append(from);
217 c.Append(from);
218 }
219
220 for (int i = 0; i < 1024; ++i) {
221 c.Append(from);
222 }
223 ABSL_RAW_LOG(INFO, "Made a Cord with %zu bytes!", c.size());
224 // Note: on a 32-bit build, this comes out to 2,818,048,000 bytes.
225 // Note: on a 64-bit build, this comes out to 171,932,385,280 bytes.
226 }
227
MakeExternalCord(int size)228 static absl::Cord MakeExternalCord(int size) {
229 char* buffer = new char[size];
230 memset(buffer, 'x', size);
231 absl::Cord cord;
232 cord.Append(absl::MakeCordFromExternal(
233 absl::string_view(buffer, size),
234 [](absl::string_view s) { delete[] s.data(); }));
235 return cord;
236 }
237
238 // Extern to fool clang that this is not constant. Needed to suppress
239 // a warning of unsafe code we want to test.
240 extern bool my_unique_true_boolean;
241 bool my_unique_true_boolean = true;
242
TEST(Cord,Assignment)243 TEST(Cord, Assignment) {
244 absl::Cord x(absl::string_view("hi there"));
245 absl::Cord y(x);
246 ASSERT_EQ(std::string(x), "hi there");
247 ASSERT_EQ(std::string(y), "hi there");
248 ASSERT_TRUE(x == y);
249 ASSERT_TRUE(x <= y);
250 ASSERT_TRUE(y <= x);
251
252 x = absl::string_view("foo");
253 ASSERT_EQ(std::string(x), "foo");
254 ASSERT_EQ(std::string(y), "hi there");
255 ASSERT_TRUE(x < y);
256 ASSERT_TRUE(y > x);
257 ASSERT_TRUE(x != y);
258 ASSERT_TRUE(x <= y);
259 ASSERT_TRUE(y >= x);
260
261 x = "foo";
262 ASSERT_EQ(x, "foo");
263
264 // Test that going from inline rep to tree we don't leak memory.
265 std::vector<std::pair<absl::string_view, absl::string_view>>
266 test_string_pairs = {{"hi there", "foo"},
267 {"loooooong coooooord", "short cord"},
268 {"short cord", "loooooong coooooord"},
269 {"loooooong coooooord1", "loooooong coooooord2"}};
270 for (std::pair<absl::string_view, absl::string_view> test_strings :
271 test_string_pairs) {
272 absl::Cord tmp(test_strings.first);
273 absl::Cord z(std::move(tmp));
274 ASSERT_EQ(std::string(z), test_strings.first);
275 tmp = test_strings.second;
276 z = std::move(tmp);
277 ASSERT_EQ(std::string(z), test_strings.second);
278 }
279 {
280 // Test that self-move assignment doesn't crash/leak.
281 // Do not write such code!
282 absl::Cord my_small_cord("foo");
283 absl::Cord my_big_cord("loooooong coooooord");
284 // Bypass clang's warning on self move-assignment.
285 absl::Cord* my_small_alias =
286 my_unique_true_boolean ? &my_small_cord : &my_big_cord;
287 absl::Cord* my_big_alias =
288 !my_unique_true_boolean ? &my_small_cord : &my_big_cord;
289
290 *my_small_alias = std::move(my_small_cord);
291 *my_big_alias = std::move(my_big_cord);
292 // my_small_cord and my_big_cord are in an unspecified but valid
293 // state, and will be correctly destroyed here.
294 }
295 }
296
TEST(Cord,StartsEndsWith)297 TEST(Cord, StartsEndsWith) {
298 absl::Cord x(absl::string_view("abcde"));
299 absl::Cord empty("");
300
301 ASSERT_TRUE(x.StartsWith(absl::Cord("abcde")));
302 ASSERT_TRUE(x.StartsWith(absl::Cord("abc")));
303 ASSERT_TRUE(x.StartsWith(absl::Cord("")));
304 ASSERT_TRUE(empty.StartsWith(absl::Cord("")));
305 ASSERT_TRUE(x.EndsWith(absl::Cord("abcde")));
306 ASSERT_TRUE(x.EndsWith(absl::Cord("cde")));
307 ASSERT_TRUE(x.EndsWith(absl::Cord("")));
308 ASSERT_TRUE(empty.EndsWith(absl::Cord("")));
309
310 ASSERT_TRUE(!x.StartsWith(absl::Cord("xyz")));
311 ASSERT_TRUE(!empty.StartsWith(absl::Cord("xyz")));
312 ASSERT_TRUE(!x.EndsWith(absl::Cord("xyz")));
313 ASSERT_TRUE(!empty.EndsWith(absl::Cord("xyz")));
314
315 ASSERT_TRUE(x.StartsWith("abcde"));
316 ASSERT_TRUE(x.StartsWith("abc"));
317 ASSERT_TRUE(x.StartsWith(""));
318 ASSERT_TRUE(empty.StartsWith(""));
319 ASSERT_TRUE(x.EndsWith("abcde"));
320 ASSERT_TRUE(x.EndsWith("cde"));
321 ASSERT_TRUE(x.EndsWith(""));
322 ASSERT_TRUE(empty.EndsWith(""));
323
324 ASSERT_TRUE(!x.StartsWith("xyz"));
325 ASSERT_TRUE(!empty.StartsWith("xyz"));
326 ASSERT_TRUE(!x.EndsWith("xyz"));
327 ASSERT_TRUE(!empty.EndsWith("xyz"));
328 }
329
TEST(Cord,Subcord)330 TEST(Cord, Subcord) {
331 RandomEngine rng(testing::GTEST_FLAG(random_seed));
332 const std::string s = RandomLowercaseString(&rng, 1024);
333
334 absl::Cord a;
335 AppendWithFragments(s, &rng, &a);
336 ASSERT_EQ(s.size(), a.size());
337
338 // Check subcords of a, from a variety of interesting points.
339 std::set<size_t> positions;
340 for (int i = 0; i <= 32; ++i) {
341 positions.insert(i);
342 positions.insert(i * 32 - 1);
343 positions.insert(i * 32);
344 positions.insert(i * 32 + 1);
345 positions.insert(a.size() - i);
346 }
347 positions.insert(237);
348 positions.insert(732);
349 for (size_t pos : positions) {
350 if (pos > a.size()) continue;
351 for (size_t end_pos : positions) {
352 if (end_pos < pos || end_pos > a.size()) continue;
353 absl::Cord sa = a.Subcord(pos, end_pos - pos);
354 EXPECT_EQ(absl::string_view(s).substr(pos, end_pos - pos),
355 std::string(sa))
356 << a;
357 }
358 }
359
360 // Do the same thing for an inline cord.
361 const std::string sh = "short";
362 absl::Cord c(sh);
363 for (size_t pos = 0; pos <= sh.size(); ++pos) {
364 for (size_t n = 0; n <= sh.size() - pos; ++n) {
365 absl::Cord sc = c.Subcord(pos, n);
366 EXPECT_EQ(sh.substr(pos, n), std::string(sc)) << c;
367 }
368 }
369
370 // Check subcords of subcords.
371 absl::Cord sa = a.Subcord(0, a.size());
372 std::string ss = s.substr(0, s.size());
373 while (sa.size() > 1) {
374 sa = sa.Subcord(1, sa.size() - 2);
375 ss = ss.substr(1, ss.size() - 2);
376 EXPECT_EQ(ss, std::string(sa)) << a;
377 if (HasFailure()) break; // halt cascade
378 }
379
380 // It is OK to ask for too much.
381 sa = a.Subcord(0, a.size() + 1);
382 EXPECT_EQ(s, std::string(sa));
383
384 // It is OK to ask for something beyond the end.
385 sa = a.Subcord(a.size() + 1, 0);
386 EXPECT_TRUE(sa.empty());
387 sa = a.Subcord(a.size() + 1, 1);
388 EXPECT_TRUE(sa.empty());
389 }
390
TEST(Cord,Swap)391 TEST(Cord, Swap) {
392 absl::string_view a("Dexter");
393 absl::string_view b("Mandark");
394 absl::Cord x(a);
395 absl::Cord y(b);
396 swap(x, y);
397 ASSERT_EQ(x, absl::Cord(b));
398 ASSERT_EQ(y, absl::Cord(a));
399 x.swap(y);
400 ASSERT_EQ(x, absl::Cord(a));
401 ASSERT_EQ(y, absl::Cord(b));
402 }
403
VerifyCopyToString(const absl::Cord & cord)404 static void VerifyCopyToString(const absl::Cord& cord) {
405 std::string initially_empty;
406 absl::CopyCordToString(cord, &initially_empty);
407 EXPECT_EQ(initially_empty, cord);
408
409 constexpr size_t kInitialLength = 1024;
410 std::string has_initial_contents(kInitialLength, 'x');
411 const char* address_before_copy = has_initial_contents.data();
412 absl::CopyCordToString(cord, &has_initial_contents);
413 EXPECT_EQ(has_initial_contents, cord);
414
415 if (cord.size() <= kInitialLength) {
416 EXPECT_EQ(has_initial_contents.data(), address_before_copy)
417 << "CopyCordToString allocated new string storage; "
418 "has_initial_contents = \""
419 << has_initial_contents << "\"";
420 }
421 }
422
TEST(Cord,CopyToString)423 TEST(Cord, CopyToString) {
424 VerifyCopyToString(absl::Cord());
425 VerifyCopyToString(absl::Cord("small cord"));
426 VerifyCopyToString(
427 absl::MakeFragmentedCord({"fragmented ", "cord ", "to ", "test ",
428 "copying ", "to ", "a ", "string."}));
429 }
430
TEST(TryFlat,Empty)431 TEST(TryFlat, Empty) {
432 absl::Cord c;
433 EXPECT_EQ(c.TryFlat(), "");
434 }
435
TEST(TryFlat,Flat)436 TEST(TryFlat, Flat) {
437 absl::Cord c("hello");
438 EXPECT_EQ(c.TryFlat(), "hello");
439 }
440
TEST(TryFlat,SubstrInlined)441 TEST(TryFlat, SubstrInlined) {
442 absl::Cord c("hello");
443 c.RemovePrefix(1);
444 EXPECT_EQ(c.TryFlat(), "ello");
445 }
446
TEST(TryFlat,SubstrFlat)447 TEST(TryFlat, SubstrFlat) {
448 absl::Cord c("longer than 15 bytes");
449 c.RemovePrefix(1);
450 EXPECT_EQ(c.TryFlat(), "onger than 15 bytes");
451 }
452
TEST(TryFlat,Concat)453 TEST(TryFlat, Concat) {
454 absl::Cord c = absl::MakeFragmentedCord({"hel", "lo"});
455 EXPECT_EQ(c.TryFlat(), absl::nullopt);
456 }
457
TEST(TryFlat,External)458 TEST(TryFlat, External) {
459 absl::Cord c = absl::MakeCordFromExternal("hell", [](absl::string_view) {});
460 EXPECT_EQ(c.TryFlat(), "hell");
461 }
462
TEST(TryFlat,SubstrExternal)463 TEST(TryFlat, SubstrExternal) {
464 absl::Cord c = absl::MakeCordFromExternal("hell", [](absl::string_view) {});
465 c.RemovePrefix(1);
466 EXPECT_EQ(c.TryFlat(), "ell");
467 }
468
TEST(TryFlat,SubstrConcat)469 TEST(TryFlat, SubstrConcat) {
470 absl::Cord c = absl::MakeFragmentedCord({"hello", " world"});
471 c.RemovePrefix(1);
472 EXPECT_EQ(c.TryFlat(), absl::nullopt);
473 }
474
IsFlat(const absl::Cord & c)475 static bool IsFlat(const absl::Cord& c) {
476 return c.chunk_begin() == c.chunk_end() || ++c.chunk_begin() == c.chunk_end();
477 }
478
VerifyFlatten(absl::Cord c)479 static void VerifyFlatten(absl::Cord c) {
480 std::string old_contents(c);
481 absl::string_view old_flat;
482 bool already_flat_and_non_empty = IsFlat(c) && !c.empty();
483 if (already_flat_and_non_empty) {
484 old_flat = *c.chunk_begin();
485 }
486 absl::string_view new_flat = c.Flatten();
487
488 // Verify that the contents of the flattened Cord are correct.
489 EXPECT_EQ(new_flat, old_contents);
490 EXPECT_EQ(std::string(c), old_contents);
491
492 // If the Cord contained data and was already flat, verify that the data
493 // wasn't copied.
494 if (already_flat_and_non_empty) {
495 EXPECT_EQ(old_flat.data(), new_flat.data())
496 << "Allocated new memory even though the Cord was already flat.";
497 }
498
499 // Verify that the flattened Cord is in fact flat.
500 EXPECT_TRUE(IsFlat(c));
501 }
502
TEST(Cord,Flatten)503 TEST(Cord, Flatten) {
504 VerifyFlatten(absl::Cord());
505 VerifyFlatten(absl::Cord("small cord"));
506 VerifyFlatten(absl::Cord("larger than small buffer optimization"));
507 VerifyFlatten(absl::MakeFragmentedCord({"small ", "fragmented ", "cord"}));
508
509 // Test with a cord that is longer than the largest flat buffer
510 RandomEngine rng(testing::GTEST_FLAG(random_seed));
511 VerifyFlatten(absl::Cord(RandomLowercaseString(&rng, 8192)));
512 }
513
514 // Test data
515 namespace {
516 class TestData {
517 private:
518 std::vector<std::string> data_;
519
520 // Return a std::string of the specified length.
MakeString(int length)521 static std::string MakeString(int length) {
522 std::string result;
523 char buf[30];
524 snprintf(buf, sizeof(buf), "(%d)", length);
525 while (result.size() < length) {
526 result += buf;
527 }
528 result.resize(length);
529 return result;
530 }
531
532 public:
TestData()533 TestData() {
534 // short strings increasing in length by one
535 for (int i = 0; i < 30; i++) {
536 data_.push_back(MakeString(i));
537 }
538
539 // strings around half kMaxFlatLength
540 static const int kMaxFlatLength = 4096 - 9;
541 static const int kHalf = kMaxFlatLength / 2;
542
543 for (int i = -10; i <= +10; i++) {
544 data_.push_back(MakeString(kHalf + i));
545 }
546
547 for (int i = -10; i <= +10; i++) {
548 data_.push_back(MakeString(kMaxFlatLength + i));
549 }
550 }
551
size() const552 size_t size() const { return data_.size(); }
data(size_t i) const553 const std::string& data(size_t i) const { return data_[i]; }
554 };
555 } // namespace
556
TEST(Cord,MultipleLengths)557 TEST(Cord, MultipleLengths) {
558 TestData d;
559 for (size_t i = 0; i < d.size(); i++) {
560 std::string a = d.data(i);
561
562 { // Construct from Cord
563 absl::Cord tmp(a);
564 absl::Cord x(tmp);
565 EXPECT_EQ(a, std::string(x)) << "'" << a << "'";
566 }
567
568 { // Construct from absl::string_view
569 absl::Cord x(a);
570 EXPECT_EQ(a, std::string(x)) << "'" << a << "'";
571 }
572
573 { // Append cord to self
574 absl::Cord self(a);
575 self.Append(self);
576 EXPECT_EQ(a + a, std::string(self)) << "'" << a << "' + '" << a << "'";
577 }
578
579 { // Prepend cord to self
580 absl::Cord self(a);
581 self.Prepend(self);
582 EXPECT_EQ(a + a, std::string(self)) << "'" << a << "' + '" << a << "'";
583 }
584
585 // Try to append/prepend others
586 for (size_t j = 0; j < d.size(); j++) {
587 std::string b = d.data(j);
588
589 { // CopyFrom Cord
590 absl::Cord x(a);
591 absl::Cord y(b);
592 x = y;
593 EXPECT_EQ(b, std::string(x)) << "'" << a << "' + '" << b << "'";
594 }
595
596 { // CopyFrom absl::string_view
597 absl::Cord x(a);
598 x = b;
599 EXPECT_EQ(b, std::string(x)) << "'" << a << "' + '" << b << "'";
600 }
601
602 { // Cord::Append(Cord)
603 absl::Cord x(a);
604 absl::Cord y(b);
605 x.Append(y);
606 EXPECT_EQ(a + b, std::string(x)) << "'" << a << "' + '" << b << "'";
607 }
608
609 { // Cord::Append(absl::string_view)
610 absl::Cord x(a);
611 x.Append(b);
612 EXPECT_EQ(a + b, std::string(x)) << "'" << a << "' + '" << b << "'";
613 }
614
615 { // Cord::Prepend(Cord)
616 absl::Cord x(a);
617 absl::Cord y(b);
618 x.Prepend(y);
619 EXPECT_EQ(b + a, std::string(x)) << "'" << b << "' + '" << a << "'";
620 }
621
622 { // Cord::Prepend(absl::string_view)
623 absl::Cord x(a);
624 x.Prepend(b);
625 EXPECT_EQ(b + a, std::string(x)) << "'" << b << "' + '" << a << "'";
626 }
627 }
628 }
629 }
630
631 namespace {
632
TEST(Cord,RemoveSuffixWithExternalOrSubstring)633 TEST(Cord, RemoveSuffixWithExternalOrSubstring) {
634 absl::Cord cord = absl::MakeCordFromExternal(
635 "foo bar baz", [](absl::string_view s) { DoNothing(s, nullptr); });
636
637 EXPECT_EQ("foo bar baz", std::string(cord));
638
639 // This RemoveSuffix() will wrap the EXTERNAL node in a SUBSTRING node.
640 cord.RemoveSuffix(4);
641 EXPECT_EQ("foo bar", std::string(cord));
642
643 // This RemoveSuffix() will adjust the SUBSTRING node in-place.
644 cord.RemoveSuffix(4);
645 EXPECT_EQ("foo", std::string(cord));
646 }
647
TEST(Cord,RemoveSuffixMakesZeroLengthNode)648 TEST(Cord, RemoveSuffixMakesZeroLengthNode) {
649 absl::Cord c;
650 c.Append(absl::Cord(std::string(100, 'x')));
651 absl::Cord other_ref = c; // Prevent inplace appends
652 c.Append(absl::Cord(std::string(200, 'y')));
653 c.RemoveSuffix(200);
654 EXPECT_EQ(std::string(100, 'x'), std::string(c));
655 }
656
657 } // namespace
658
659 // CordSpliceTest contributed by hendrie.
660 namespace {
661
662 // Create a cord with an external memory block filled with 'z'
CordWithZedBlock(size_t size)663 absl::Cord CordWithZedBlock(size_t size) {
664 char* data = new char[size];
665 if (size > 0) {
666 memset(data, 'z', size);
667 }
668 absl::Cord cord = absl::MakeCordFromExternal(
669 absl::string_view(data, size),
670 [](absl::string_view s) { delete[] s.data(); });
671 return cord;
672 }
673
674 // Establish that ZedBlock does what we think it does.
TEST(CordSpliceTest,ZedBlock)675 TEST(CordSpliceTest, ZedBlock) {
676 absl::Cord blob = CordWithZedBlock(10);
677 EXPECT_EQ(10, blob.size());
678 std::string s;
679 absl::CopyCordToString(blob, &s);
680 EXPECT_EQ("zzzzzzzzzz", s);
681 }
682
TEST(CordSpliceTest,ZedBlock0)683 TEST(CordSpliceTest, ZedBlock0) {
684 absl::Cord blob = CordWithZedBlock(0);
685 EXPECT_EQ(0, blob.size());
686 std::string s;
687 absl::CopyCordToString(blob, &s);
688 EXPECT_EQ("", s);
689 }
690
TEST(CordSpliceTest,ZedBlockSuffix1)691 TEST(CordSpliceTest, ZedBlockSuffix1) {
692 absl::Cord blob = CordWithZedBlock(10);
693 EXPECT_EQ(10, blob.size());
694 absl::Cord suffix(blob);
695 suffix.RemovePrefix(9);
696 EXPECT_EQ(1, suffix.size());
697 std::string s;
698 absl::CopyCordToString(suffix, &s);
699 EXPECT_EQ("z", s);
700 }
701
702 // Remove all of a prefix block
TEST(CordSpliceTest,ZedBlockSuffix0)703 TEST(CordSpliceTest, ZedBlockSuffix0) {
704 absl::Cord blob = CordWithZedBlock(10);
705 EXPECT_EQ(10, blob.size());
706 absl::Cord suffix(blob);
707 suffix.RemovePrefix(10);
708 EXPECT_EQ(0, suffix.size());
709 std::string s;
710 absl::CopyCordToString(suffix, &s);
711 EXPECT_EQ("", s);
712 }
713
BigCord(size_t len,char v)714 absl::Cord BigCord(size_t len, char v) {
715 std::string s(len, v);
716 return absl::Cord(s);
717 }
718
719 // Splice block into cord.
SpliceCord(const absl::Cord & blob,int64_t offset,const absl::Cord & block)720 absl::Cord SpliceCord(const absl::Cord& blob, int64_t offset,
721 const absl::Cord& block) {
722 ABSL_RAW_CHECK(offset >= 0, "");
723 ABSL_RAW_CHECK(offset + block.size() <= blob.size(), "");
724 absl::Cord result(blob);
725 result.RemoveSuffix(blob.size() - offset);
726 result.Append(block);
727 absl::Cord suffix(blob);
728 suffix.RemovePrefix(offset + block.size());
729 result.Append(suffix);
730 ABSL_RAW_CHECK(blob.size() == result.size(), "");
731 return result;
732 }
733
734 // Taking an empty suffix of a block breaks appending.
TEST(CordSpliceTest,RemoveEntireBlock1)735 TEST(CordSpliceTest, RemoveEntireBlock1) {
736 absl::Cord zero = CordWithZedBlock(10);
737 absl::Cord suffix(zero);
738 suffix.RemovePrefix(10);
739 absl::Cord result;
740 result.Append(suffix);
741 }
742
TEST(CordSpliceTest,RemoveEntireBlock2)743 TEST(CordSpliceTest, RemoveEntireBlock2) {
744 absl::Cord zero = CordWithZedBlock(10);
745 absl::Cord prefix(zero);
746 prefix.RemoveSuffix(10);
747 absl::Cord suffix(zero);
748 suffix.RemovePrefix(10);
749 absl::Cord result(prefix);
750 result.Append(suffix);
751 }
752
TEST(CordSpliceTest,RemoveEntireBlock3)753 TEST(CordSpliceTest, RemoveEntireBlock3) {
754 absl::Cord blob = CordWithZedBlock(10);
755 absl::Cord block = BigCord(10, 'b');
756 blob = SpliceCord(blob, 0, block);
757 }
758
759 struct CordCompareTestCase {
760 template <typename LHS, typename RHS>
CordCompareTestCase__anona6e5a3920b11::CordCompareTestCase761 CordCompareTestCase(const LHS& lhs, const RHS& rhs)
762 : lhs_cord(lhs), rhs_cord(rhs) {}
763
764 absl::Cord lhs_cord;
765 absl::Cord rhs_cord;
766 };
767
__anona6e5a3920d02(int x) 768 const auto sign = [](int x) { return x == 0 ? 0 : (x > 0 ? 1 : -1); };
769
VerifyComparison(const CordCompareTestCase & test_case)770 void VerifyComparison(const CordCompareTestCase& test_case) {
771 std::string lhs_string(test_case.lhs_cord);
772 std::string rhs_string(test_case.rhs_cord);
773 int expected = sign(lhs_string.compare(rhs_string));
774 EXPECT_EQ(expected, test_case.lhs_cord.Compare(test_case.rhs_cord))
775 << "LHS=" << lhs_string << "; RHS=" << rhs_string;
776 EXPECT_EQ(expected, test_case.lhs_cord.Compare(rhs_string))
777 << "LHS=" << lhs_string << "; RHS=" << rhs_string;
778 EXPECT_EQ(-expected, test_case.rhs_cord.Compare(test_case.lhs_cord))
779 << "LHS=" << rhs_string << "; RHS=" << lhs_string;
780 EXPECT_EQ(-expected, test_case.rhs_cord.Compare(lhs_string))
781 << "LHS=" << rhs_string << "; RHS=" << lhs_string;
782 }
783
TEST(Cord,Compare)784 TEST(Cord, Compare) {
785 absl::Cord subcord("aaaaaBBBBBcccccDDDDD");
786 subcord = subcord.Subcord(3, 10);
787
788 absl::Cord tmp("aaaaaaaaaaaaaaaa");
789 tmp.Append("BBBBBBBBBBBBBBBB");
790 absl::Cord concat = absl::Cord("cccccccccccccccc");
791 concat.Append("DDDDDDDDDDDDDDDD");
792 concat.Prepend(tmp);
793
794 absl::Cord concat2("aaaaaaaaaaaaa");
795 concat2.Append("aaaBBBBBBBBBBBBBBBBccccc");
796 concat2.Append("cccccccccccDDDDDDDDDDDDDD");
797 concat2.Append("DD");
798
799 std::vector<CordCompareTestCase> test_cases = {{
800 // Inline cords
801 {"abcdef", "abcdef"},
802 {"abcdef", "abcdee"},
803 {"abcdef", "abcdeg"},
804 {"bbcdef", "abcdef"},
805 {"bbcdef", "abcdeg"},
806 {"abcdefa", "abcdef"},
807 {"abcdef", "abcdefa"},
808
809 // Small flat cords
810 {"aaaaaBBBBBcccccDDDDD", "aaaaaBBBBBcccccDDDDD"},
811 {"aaaaaBBBBBcccccDDDDD", "aaaaaBBBBBxccccDDDDD"},
812 {"aaaaaBBBBBcxcccDDDDD", "aaaaaBBBBBcccccDDDDD"},
813 {"aaaaaBBBBBxccccDDDDD", "aaaaaBBBBBcccccDDDDX"},
814 {"aaaaaBBBBBcccccDDDDDa", "aaaaaBBBBBcccccDDDDD"},
815 {"aaaaaBBBBBcccccDDDDD", "aaaaaBBBBBcccccDDDDDa"},
816
817 // Subcords
818 {subcord, subcord},
819 {subcord, "aaBBBBBccc"},
820 {subcord, "aaBBBBBccd"},
821 {subcord, "aaBBBBBccb"},
822 {subcord, "aaBBBBBxcb"},
823 {subcord, "aaBBBBBccca"},
824 {subcord, "aaBBBBBcc"},
825
826 // Concats
827 {concat, concat},
828 {concat,
829 "aaaaaaaaaaaaaaaaBBBBBBBBBBBBBBBBccccccccccccccccDDDDDDDDDDDDDDDD"},
830 {concat,
831 "aaaaaaaaaaaaaaaaBBBBBBBBBBBBBBBBcccccccccccccccxDDDDDDDDDDDDDDDD"},
832 {concat,
833 "aaaaaaaaaaaaaaaaBBBBBBBBBBBBBBBBacccccccccccccccDDDDDDDDDDDDDDDD"},
834 {concat,
835 "aaaaaaaaaaaaaaaaBBBBBBBBBBBBBBBBccccccccccccccccDDDDDDDDDDDDDDD"},
836 {concat,
837 "aaaaaaaaaaaaaaaaBBBBBBBBBBBBBBBBccccccccccccccccDDDDDDDDDDDDDDDDe"},
838
839 {concat, concat2},
840 }};
841
842 for (const auto& tc : test_cases) {
843 VerifyComparison(tc);
844 }
845 }
846
TEST(Cord,CompareAfterAssign)847 TEST(Cord, CompareAfterAssign) {
848 absl::Cord a("aaaaaa1111111");
849 absl::Cord b("aaaaaa2222222");
850 a = "cccccc";
851 b = "cccccc";
852 EXPECT_EQ(a, b);
853 EXPECT_FALSE(a < b);
854
855 a = "aaaa";
856 b = "bbbbb";
857 a = "";
858 b = "";
859 EXPECT_EQ(a, b);
860 EXPECT_FALSE(a < b);
861 }
862
863 // Test CompareTo() and ComparePrefix() against string and substring
864 // comparison methods from basic_string.
TestCompare(const absl::Cord & c,const absl::Cord & d,RandomEngine * rng)865 static void TestCompare(const absl::Cord& c, const absl::Cord& d,
866 RandomEngine* rng) {
867 typedef std::basic_string<uint8_t> ustring;
868 ustring cs(reinterpret_cast<const uint8_t*>(std::string(c).data()), c.size());
869 ustring ds(reinterpret_cast<const uint8_t*>(std::string(d).data()), d.size());
870 // ustring comparison is ideal because we expect Cord comparisons to be
871 // based on unsigned byte comparisons regardless of whether char is signed.
872 int expected = sign(cs.compare(ds));
873 EXPECT_EQ(expected, sign(c.Compare(d))) << c << ", " << d;
874 }
875
TEST(Compare,ComparisonIsUnsigned)876 TEST(Compare, ComparisonIsUnsigned) {
877 RandomEngine rng(testing::GTEST_FLAG(random_seed));
878 std::uniform_int_distribution<uint32_t> uniform_uint8(0, 255);
879 char x = static_cast<char>(uniform_uint8(rng));
880 TestCompare(
881 absl::Cord(std::string(GetUniformRandomUpTo(&rng, 100), x)),
882 absl::Cord(std::string(GetUniformRandomUpTo(&rng, 100), x ^ 0x80)), &rng);
883 }
884
TEST(Compare,RandomComparisons)885 TEST(Compare, RandomComparisons) {
886 const int kIters = 5000;
887 RandomEngine rng(testing::GTEST_FLAG(random_seed));
888
889 int n = GetUniformRandomUpTo(&rng, 5000);
890 absl::Cord a[] = {MakeExternalCord(n),
891 absl::Cord("ant"),
892 absl::Cord("elephant"),
893 absl::Cord("giraffe"),
894 absl::Cord(std::string(GetUniformRandomUpTo(&rng, 100),
895 GetUniformRandomUpTo(&rng, 100))),
896 absl::Cord(""),
897 absl::Cord("x"),
898 absl::Cord("A"),
899 absl::Cord("B"),
900 absl::Cord("C")};
901 for (int i = 0; i < kIters; i++) {
902 absl::Cord c, d;
903 for (int j = 0; j < (i % 7) + 1; j++) {
904 c.Append(a[GetUniformRandomUpTo(&rng, ABSL_ARRAYSIZE(a))]);
905 d.Append(a[GetUniformRandomUpTo(&rng, ABSL_ARRAYSIZE(a))]);
906 }
907 std::bernoulli_distribution coin_flip(0.5);
908 TestCompare(coin_flip(rng) ? c : absl::Cord(std::string(c)),
909 coin_flip(rng) ? d : absl::Cord(std::string(d)), &rng);
910 }
911 }
912
913 template <typename T1, typename T2>
CompareOperators()914 void CompareOperators() {
915 const T1 a("a");
916 const T2 b("b");
917
918 EXPECT_TRUE(a == a);
919 // For pointer type (i.e. `const char*`), operator== compares the address
920 // instead of the string, so `a == const char*("a")` isn't necessarily true.
921 EXPECT_TRUE(std::is_pointer<T1>::value || a == T1("a"));
922 EXPECT_TRUE(std::is_pointer<T2>::value || a == T2("a"));
923 EXPECT_FALSE(a == b);
924
925 EXPECT_TRUE(a != b);
926 EXPECT_FALSE(a != a);
927
928 EXPECT_TRUE(a < b);
929 EXPECT_FALSE(b < a);
930
931 EXPECT_TRUE(b > a);
932 EXPECT_FALSE(a > b);
933
934 EXPECT_TRUE(a >= a);
935 EXPECT_TRUE(b >= a);
936 EXPECT_FALSE(a >= b);
937
938 EXPECT_TRUE(a <= a);
939 EXPECT_TRUE(a <= b);
940 EXPECT_FALSE(b <= a);
941 }
942
TEST(ComparisonOperators,Cord_Cord)943 TEST(ComparisonOperators, Cord_Cord) {
944 CompareOperators<absl::Cord, absl::Cord>();
945 }
946
TEST(ComparisonOperators,Cord_StringPiece)947 TEST(ComparisonOperators, Cord_StringPiece) {
948 CompareOperators<absl::Cord, absl::string_view>();
949 }
950
TEST(ComparisonOperators,StringPiece_Cord)951 TEST(ComparisonOperators, StringPiece_Cord) {
952 CompareOperators<absl::string_view, absl::Cord>();
953 }
954
TEST(ComparisonOperators,Cord_string)955 TEST(ComparisonOperators, Cord_string) {
956 CompareOperators<absl::Cord, std::string>();
957 }
958
TEST(ComparisonOperators,string_Cord)959 TEST(ComparisonOperators, string_Cord) {
960 CompareOperators<std::string, absl::Cord>();
961 }
962
TEST(ComparisonOperators,stdstring_Cord)963 TEST(ComparisonOperators, stdstring_Cord) {
964 CompareOperators<std::string, absl::Cord>();
965 }
966
TEST(ComparisonOperators,Cord_stdstring)967 TEST(ComparisonOperators, Cord_stdstring) {
968 CompareOperators<absl::Cord, std::string>();
969 }
970
TEST(ComparisonOperators,charstar_Cord)971 TEST(ComparisonOperators, charstar_Cord) {
972 CompareOperators<const char*, absl::Cord>();
973 }
974
TEST(ComparisonOperators,Cord_charstar)975 TEST(ComparisonOperators, Cord_charstar) {
976 CompareOperators<absl::Cord, const char*>();
977 }
978
TEST(ConstructFromExternal,ReleaserInvoked)979 TEST(ConstructFromExternal, ReleaserInvoked) {
980 // Empty external memory means the releaser should be called immediately.
981 {
982 bool invoked = false;
983 auto releaser = [&invoked](absl::string_view) { invoked = true; };
984 {
985 auto c = absl::MakeCordFromExternal("", releaser);
986 EXPECT_TRUE(invoked);
987 }
988 }
989
990 // If the size of the data is small enough, a future constructor
991 // implementation may copy the bytes and immediately invoke the releaser
992 // instead of creating an external node. We make a large dummy std::string to
993 // make this test independent of such an optimization.
994 std::string large_dummy(2048, 'c');
995 {
996 bool invoked = false;
997 auto releaser = [&invoked](absl::string_view) { invoked = true; };
998 {
999 auto c = absl::MakeCordFromExternal(large_dummy, releaser);
1000 EXPECT_FALSE(invoked);
1001 }
1002 EXPECT_TRUE(invoked);
1003 }
1004
1005 {
1006 bool invoked = false;
1007 auto releaser = [&invoked](absl::string_view) { invoked = true; };
1008 {
1009 absl::Cord copy;
1010 {
1011 auto c = absl::MakeCordFromExternal(large_dummy, releaser);
1012 copy = c;
1013 EXPECT_FALSE(invoked);
1014 }
1015 EXPECT_FALSE(invoked);
1016 }
1017 EXPECT_TRUE(invoked);
1018 }
1019 }
1020
TEST(ConstructFromExternal,CompareContents)1021 TEST(ConstructFromExternal, CompareContents) {
1022 RandomEngine rng(testing::GTEST_FLAG(random_seed));
1023
1024 for (int length = 1; length <= 2048; length *= 2) {
1025 std::string data = RandomLowercaseString(&rng, length);
1026 auto* external = new std::string(data);
1027 auto cord =
1028 absl::MakeCordFromExternal(*external, [external](absl::string_view sv) {
1029 EXPECT_EQ(external->data(), sv.data());
1030 EXPECT_EQ(external->size(), sv.size());
1031 delete external;
1032 });
1033 EXPECT_EQ(data, cord);
1034 }
1035 }
1036
TEST(ConstructFromExternal,LargeReleaser)1037 TEST(ConstructFromExternal, LargeReleaser) {
1038 RandomEngine rng(testing::GTEST_FLAG(random_seed));
1039 constexpr size_t kLength = 256;
1040 std::string data = RandomLowercaseString(&rng, kLength);
1041 std::array<char, kLength> data_array;
1042 for (size_t i = 0; i < kLength; ++i) data_array[i] = data[i];
1043 bool invoked = false;
1044 auto releaser = [data_array, &invoked](absl::string_view data) {
1045 EXPECT_EQ(data, absl::string_view(data_array.data(), data_array.size()));
1046 invoked = true;
1047 };
1048 (void)absl::MakeCordFromExternal(data, releaser);
1049 EXPECT_TRUE(invoked);
1050 }
1051
TEST(ConstructFromExternal,FunctionPointerReleaser)1052 TEST(ConstructFromExternal, FunctionPointerReleaser) {
1053 static absl::string_view data("hello world");
1054 static bool invoked;
1055 auto* releaser =
1056 static_cast<void (*)(absl::string_view)>([](absl::string_view sv) {
1057 EXPECT_EQ(data, sv);
1058 invoked = true;
1059 });
1060 invoked = false;
1061 (void)absl::MakeCordFromExternal(data, releaser);
1062 EXPECT_TRUE(invoked);
1063
1064 invoked = false;
1065 (void)absl::MakeCordFromExternal(data, *releaser);
1066 EXPECT_TRUE(invoked);
1067 }
1068
TEST(ConstructFromExternal,MoveOnlyReleaser)1069 TEST(ConstructFromExternal, MoveOnlyReleaser) {
1070 struct Releaser {
1071 explicit Releaser(bool* invoked) : invoked(invoked) {}
1072 Releaser(Releaser&& other) noexcept : invoked(other.invoked) {}
1073 void operator()(absl::string_view) const { *invoked = true; }
1074
1075 bool* invoked;
1076 };
1077
1078 bool invoked = false;
1079 (void)absl::MakeCordFromExternal("dummy", Releaser(&invoked));
1080 EXPECT_TRUE(invoked);
1081 }
1082
TEST(ConstructFromExternal,NoArgLambda)1083 TEST(ConstructFromExternal, NoArgLambda) {
1084 bool invoked = false;
1085 (void)absl::MakeCordFromExternal("dummy", [&invoked]() { invoked = true; });
1086 EXPECT_TRUE(invoked);
1087 }
1088
TEST(ConstructFromExternal,StringViewArgLambda)1089 TEST(ConstructFromExternal, StringViewArgLambda) {
1090 bool invoked = false;
1091 (void)absl::MakeCordFromExternal(
1092 "dummy", [&invoked](absl::string_view) { invoked = true; });
1093 EXPECT_TRUE(invoked);
1094 }
1095
TEST(ConstructFromExternal,NonTrivialReleaserDestructor)1096 TEST(ConstructFromExternal, NonTrivialReleaserDestructor) {
1097 struct Releaser {
1098 explicit Releaser(bool* destroyed) : destroyed(destroyed) {}
1099 ~Releaser() { *destroyed = true; }
1100 void operator()(absl::string_view) const {}
1101
1102 bool* destroyed;
1103 };
1104
1105 bool destroyed = false;
1106 Releaser releaser(&destroyed);
1107 (void)absl::MakeCordFromExternal("dummy", releaser);
1108 EXPECT_TRUE(destroyed);
1109 }
1110
TEST(ConstructFromExternal,ReferenceQualifierOverloads)1111 TEST(ConstructFromExternal, ReferenceQualifierOverloads) {
1112 struct Releaser {
1113 void operator()(absl::string_view) & { *lvalue_invoked = true; }
1114 void operator()(absl::string_view) && { *rvalue_invoked = true; }
1115
1116 bool* lvalue_invoked;
1117 bool* rvalue_invoked;
1118 };
1119
1120 bool lvalue_invoked = false;
1121 bool rvalue_invoked = false;
1122 Releaser releaser = {&lvalue_invoked, &rvalue_invoked};
1123 (void)absl::MakeCordFromExternal("", releaser);
1124 EXPECT_FALSE(lvalue_invoked);
1125 EXPECT_TRUE(rvalue_invoked);
1126 rvalue_invoked = false;
1127
1128 (void)absl::MakeCordFromExternal("dummy", releaser);
1129 EXPECT_FALSE(lvalue_invoked);
1130 EXPECT_TRUE(rvalue_invoked);
1131 rvalue_invoked = false;
1132
1133 // NOLINTNEXTLINE: suppress clang-tidy std::move on trivially copyable type.
1134 (void)absl::MakeCordFromExternal("dummy", std::move(releaser));
1135 EXPECT_FALSE(lvalue_invoked);
1136 EXPECT_TRUE(rvalue_invoked);
1137 }
1138
TEST(ExternalMemory,BasicUsage)1139 TEST(ExternalMemory, BasicUsage) {
1140 static const char* strings[] = {"", "hello", "there"};
1141 for (const char* str : strings) {
1142 absl::Cord dst("(prefix)");
1143 AddExternalMemory(str, &dst);
1144 dst.Append("(suffix)");
1145 EXPECT_EQ((std::string("(prefix)") + str + std::string("(suffix)")),
1146 std::string(dst));
1147 }
1148 }
1149
TEST(ExternalMemory,RemovePrefixSuffix)1150 TEST(ExternalMemory, RemovePrefixSuffix) {
1151 // Exhaustively try all sub-strings.
1152 absl::Cord cord = MakeComposite();
1153 std::string s = std::string(cord);
1154 for (int offset = 0; offset <= s.size(); offset++) {
1155 for (int length = 0; length <= s.size() - offset; length++) {
1156 absl::Cord result(cord);
1157 result.RemovePrefix(offset);
1158 result.RemoveSuffix(result.size() - length);
1159 EXPECT_EQ(s.substr(offset, length), std::string(result))
1160 << offset << " " << length;
1161 }
1162 }
1163 }
1164
TEST(ExternalMemory,Get)1165 TEST(ExternalMemory, Get) {
1166 absl::Cord cord("hello");
1167 AddExternalMemory(" world!", &cord);
1168 AddExternalMemory(" how are ", &cord);
1169 cord.Append(" you?");
1170 std::string s = std::string(cord);
1171 for (int i = 0; i < s.size(); i++) {
1172 EXPECT_EQ(s[i], cord[i]);
1173 }
1174 }
1175
1176 // CordMemoryUsage tests verify the correctness of the EstimatedMemoryUsage()
1177 // These tests take into account that the reported memory usage is approximate
1178 // and non-deterministic. For all tests, We verify that the reported memory
1179 // usage is larger than `size()`, and less than `size() * 1.5` as a cord should
1180 // never reserve more 'extra' capacity than half of its size as it grows.
1181 // Additionally we have some whiteboxed expectations based on our knowledge of
1182 // the layout and size of empty and inlined cords, and flat nodes.
1183
TEST(CordMemoryUsage,Empty)1184 TEST(CordMemoryUsage, Empty) {
1185 EXPECT_EQ(sizeof(absl::Cord), absl::Cord().EstimatedMemoryUsage());
1186 }
1187
TEST(CordMemoryUsage,Embedded)1188 TEST(CordMemoryUsage, Embedded) {
1189 absl::Cord a("hello");
1190 EXPECT_EQ(a.EstimatedMemoryUsage(), sizeof(absl::Cord));
1191 }
1192
TEST(CordMemoryUsage,EmbeddedAppend)1193 TEST(CordMemoryUsage, EmbeddedAppend) {
1194 absl::Cord a("a");
1195 absl::Cord b("bcd");
1196 EXPECT_EQ(b.EstimatedMemoryUsage(), sizeof(absl::Cord));
1197 a.Append(b);
1198 EXPECT_EQ(a.EstimatedMemoryUsage(), sizeof(absl::Cord));
1199 }
1200
TEST(CordMemoryUsage,ExternalMemory)1201 TEST(CordMemoryUsage, ExternalMemory) {
1202 static const int kLength = 1000;
1203 absl::Cord cord;
1204 AddExternalMemory(std::string(kLength, 'x'), &cord);
1205 EXPECT_GT(cord.EstimatedMemoryUsage(), kLength);
1206 EXPECT_LE(cord.EstimatedMemoryUsage(), kLength * 1.5);
1207 }
1208
TEST(CordMemoryUsage,Flat)1209 TEST(CordMemoryUsage, Flat) {
1210 static const int kLength = 125;
1211 absl::Cord a(std::string(kLength, 'a'));
1212 EXPECT_GT(a.EstimatedMemoryUsage(), kLength);
1213 EXPECT_LE(a.EstimatedMemoryUsage(), kLength * 1.5);
1214 }
1215
TEST(CordMemoryUsage,AppendFlat)1216 TEST(CordMemoryUsage, AppendFlat) {
1217 using absl::strings_internal::CordTestAccess;
1218 absl::Cord a(std::string(CordTestAccess::MaxFlatLength(), 'a'));
1219 size_t length = a.EstimatedMemoryUsage();
1220 a.Append(std::string(CordTestAccess::MaxFlatLength(), 'b'));
1221 size_t delta = a.EstimatedMemoryUsage() - length;
1222 EXPECT_GT(delta, CordTestAccess::MaxFlatLength());
1223 EXPECT_LE(delta, CordTestAccess::MaxFlatLength() * 1.5);
1224 }
1225
1226 // Regtest for a change that had to be rolled back because it expanded out
1227 // of the InlineRep too soon, which was observable through MemoryUsage().
TEST(CordMemoryUsage,InlineRep)1228 TEST(CordMemoryUsage, InlineRep) {
1229 constexpr size_t kMaxInline = 15; // Cord::InlineRep::N
1230 const std::string small_string(kMaxInline, 'x');
1231 absl::Cord c1(small_string);
1232
1233 absl::Cord c2;
1234 c2.Append(small_string);
1235 EXPECT_EQ(c1, c2);
1236 EXPECT_EQ(c1.EstimatedMemoryUsage(), c2.EstimatedMemoryUsage());
1237 }
1238
1239 } // namespace
1240
1241 // Regtest for 7510292 (fix a bug introduced by 7465150)
TEST(Cord,Concat_Append)1242 TEST(Cord, Concat_Append) {
1243 // Create a rep of type CONCAT
1244 absl::Cord s1("foobarbarbarbarbar");
1245 s1.Append("abcdefgabcdefgabcdefgabcdefgabcdefgabcdefgabcdefg");
1246 size_t size = s1.size();
1247
1248 // Create a copy of s1 and append to it.
1249 absl::Cord s2 = s1;
1250 s2.Append("x");
1251
1252 // 7465150 modifies s1 when it shouldn't.
1253 EXPECT_EQ(s1.size(), size);
1254 EXPECT_EQ(s2.size(), size + 1);
1255 }
1256
TEST(MakeFragmentedCord,MakeFragmentedCordFromInitializerList)1257 TEST(MakeFragmentedCord, MakeFragmentedCordFromInitializerList) {
1258 absl::Cord fragmented =
1259 absl::MakeFragmentedCord({"A ", "fragmented ", "Cord"});
1260
1261 EXPECT_EQ("A fragmented Cord", fragmented);
1262
1263 auto chunk_it = fragmented.chunk_begin();
1264
1265 ASSERT_TRUE(chunk_it != fragmented.chunk_end());
1266 EXPECT_EQ("A ", *chunk_it);
1267
1268 ASSERT_TRUE(++chunk_it != fragmented.chunk_end());
1269 EXPECT_EQ("fragmented ", *chunk_it);
1270
1271 ASSERT_TRUE(++chunk_it != fragmented.chunk_end());
1272 EXPECT_EQ("Cord", *chunk_it);
1273
1274 ASSERT_TRUE(++chunk_it == fragmented.chunk_end());
1275 }
1276
TEST(MakeFragmentedCord,MakeFragmentedCordFromVector)1277 TEST(MakeFragmentedCord, MakeFragmentedCordFromVector) {
1278 std::vector<absl::string_view> chunks = {"A ", "fragmented ", "Cord"};
1279 absl::Cord fragmented = absl::MakeFragmentedCord(chunks);
1280
1281 EXPECT_EQ("A fragmented Cord", fragmented);
1282
1283 auto chunk_it = fragmented.chunk_begin();
1284
1285 ASSERT_TRUE(chunk_it != fragmented.chunk_end());
1286 EXPECT_EQ("A ", *chunk_it);
1287
1288 ASSERT_TRUE(++chunk_it != fragmented.chunk_end());
1289 EXPECT_EQ("fragmented ", *chunk_it);
1290
1291 ASSERT_TRUE(++chunk_it != fragmented.chunk_end());
1292 EXPECT_EQ("Cord", *chunk_it);
1293
1294 ASSERT_TRUE(++chunk_it == fragmented.chunk_end());
1295 }
1296
TEST(CordChunkIterator,Traits)1297 TEST(CordChunkIterator, Traits) {
1298 static_assert(std::is_copy_constructible<absl::Cord::ChunkIterator>::value,
1299 "");
1300 static_assert(std::is_copy_assignable<absl::Cord::ChunkIterator>::value, "");
1301
1302 // Move semantics to satisfy swappable via std::swap
1303 static_assert(std::is_move_constructible<absl::Cord::ChunkIterator>::value,
1304 "");
1305 static_assert(std::is_move_assignable<absl::Cord::ChunkIterator>::value, "");
1306
1307 static_assert(
1308 std::is_same<
1309 std::iterator_traits<absl::Cord::ChunkIterator>::iterator_category,
1310 std::input_iterator_tag>::value,
1311 "");
1312 static_assert(
1313 std::is_same<std::iterator_traits<absl::Cord::ChunkIterator>::value_type,
1314 absl::string_view>::value,
1315 "");
1316 static_assert(
1317 std::is_same<
1318 std::iterator_traits<absl::Cord::ChunkIterator>::difference_type,
1319 ptrdiff_t>::value,
1320 "");
1321 static_assert(
1322 std::is_same<std::iterator_traits<absl::Cord::ChunkIterator>::pointer,
1323 const absl::string_view*>::value,
1324 "");
1325 static_assert(
1326 std::is_same<std::iterator_traits<absl::Cord::ChunkIterator>::reference,
1327 absl::string_view>::value,
1328 "");
1329 }
1330
VerifyChunkIterator(const absl::Cord & cord,size_t expected_chunks)1331 static void VerifyChunkIterator(const absl::Cord& cord,
1332 size_t expected_chunks) {
1333 EXPECT_EQ(cord.chunk_begin() == cord.chunk_end(), cord.empty()) << cord;
1334 EXPECT_EQ(cord.chunk_begin() != cord.chunk_end(), !cord.empty());
1335
1336 absl::Cord::ChunkRange range = cord.Chunks();
1337 EXPECT_EQ(range.begin() == range.end(), cord.empty());
1338 EXPECT_EQ(range.begin() != range.end(), !cord.empty());
1339
1340 std::string content(cord);
1341 size_t pos = 0;
1342 auto pre_iter = cord.chunk_begin(), post_iter = cord.chunk_begin();
1343 size_t n_chunks = 0;
1344 while (pre_iter != cord.chunk_end() && post_iter != cord.chunk_end()) {
1345 EXPECT_FALSE(pre_iter == cord.chunk_end()); // NOLINT: explicitly test ==
1346 EXPECT_FALSE(post_iter == cord.chunk_end()); // NOLINT
1347
1348 EXPECT_EQ(pre_iter, post_iter);
1349 EXPECT_EQ(*pre_iter, *post_iter);
1350
1351 EXPECT_EQ(pre_iter->data(), (*pre_iter).data());
1352 EXPECT_EQ(pre_iter->size(), (*pre_iter).size());
1353
1354 absl::string_view chunk = *pre_iter;
1355 EXPECT_FALSE(chunk.empty());
1356 EXPECT_LE(pos + chunk.size(), content.size());
1357 EXPECT_EQ(absl::string_view(content.c_str() + pos, chunk.size()), chunk);
1358
1359 int n_equal_iterators = 0;
1360 for (absl::Cord::ChunkIterator it = range.begin(); it != range.end();
1361 ++it) {
1362 n_equal_iterators += static_cast<int>(it == pre_iter);
1363 }
1364 EXPECT_EQ(n_equal_iterators, 1);
1365
1366 ++pre_iter;
1367 EXPECT_EQ(*post_iter++, chunk);
1368
1369 pos += chunk.size();
1370 ++n_chunks;
1371 }
1372 EXPECT_EQ(expected_chunks, n_chunks);
1373 EXPECT_EQ(pos, content.size());
1374 EXPECT_TRUE(pre_iter == cord.chunk_end()); // NOLINT: explicitly test ==
1375 EXPECT_TRUE(post_iter == cord.chunk_end()); // NOLINT
1376 }
1377
TEST(CordChunkIterator,Operations)1378 TEST(CordChunkIterator, Operations) {
1379 absl::Cord empty_cord;
1380 VerifyChunkIterator(empty_cord, 0);
1381
1382 absl::Cord small_buffer_cord("small cord");
1383 VerifyChunkIterator(small_buffer_cord, 1);
1384
1385 absl::Cord flat_node_cord("larger than small buffer optimization");
1386 VerifyChunkIterator(flat_node_cord, 1);
1387
1388 VerifyChunkIterator(
1389 absl::MakeFragmentedCord({"a ", "small ", "fragmented ", "cord ", "for ",
1390 "testing ", "chunk ", "iterations."}),
1391 8);
1392
1393 absl::Cord reused_nodes_cord(std::string(40, 'c'));
1394 reused_nodes_cord.Prepend(absl::Cord(std::string(40, 'b')));
1395 reused_nodes_cord.Prepend(absl::Cord(std::string(40, 'a')));
1396 size_t expected_chunks = 3;
1397 for (int i = 0; i < 8; ++i) {
1398 reused_nodes_cord.Prepend(reused_nodes_cord);
1399 expected_chunks *= 2;
1400 VerifyChunkIterator(reused_nodes_cord, expected_chunks);
1401 }
1402
1403 RandomEngine rng(testing::GTEST_FLAG(random_seed));
1404 absl::Cord flat_cord(RandomLowercaseString(&rng, 256));
1405 absl::Cord subcords;
1406 for (int i = 0; i < 128; ++i) subcords.Prepend(flat_cord.Subcord(i, 128));
1407 VerifyChunkIterator(subcords, 128);
1408 }
1409
TEST(CordCharIterator,Traits)1410 TEST(CordCharIterator, Traits) {
1411 static_assert(std::is_copy_constructible<absl::Cord::CharIterator>::value,
1412 "");
1413 static_assert(std::is_copy_assignable<absl::Cord::CharIterator>::value, "");
1414
1415 // Move semantics to satisfy swappable via std::swap
1416 static_assert(std::is_move_constructible<absl::Cord::CharIterator>::value,
1417 "");
1418 static_assert(std::is_move_assignable<absl::Cord::CharIterator>::value, "");
1419
1420 static_assert(
1421 std::is_same<
1422 std::iterator_traits<absl::Cord::CharIterator>::iterator_category,
1423 std::input_iterator_tag>::value,
1424 "");
1425 static_assert(
1426 std::is_same<std::iterator_traits<absl::Cord::CharIterator>::value_type,
1427 char>::value,
1428 "");
1429 static_assert(
1430 std::is_same<
1431 std::iterator_traits<absl::Cord::CharIterator>::difference_type,
1432 ptrdiff_t>::value,
1433 "");
1434 static_assert(
1435 std::is_same<std::iterator_traits<absl::Cord::CharIterator>::pointer,
1436 const char*>::value,
1437 "");
1438 static_assert(
1439 std::is_same<std::iterator_traits<absl::Cord::CharIterator>::reference,
1440 const char&>::value,
1441 "");
1442 }
1443
VerifyCharIterator(const absl::Cord & cord)1444 static void VerifyCharIterator(const absl::Cord& cord) {
1445 EXPECT_EQ(cord.char_begin() == cord.char_end(), cord.empty());
1446 EXPECT_EQ(cord.char_begin() != cord.char_end(), !cord.empty());
1447
1448 absl::Cord::CharRange range = cord.Chars();
1449 EXPECT_EQ(range.begin() == range.end(), cord.empty());
1450 EXPECT_EQ(range.begin() != range.end(), !cord.empty());
1451
1452 size_t i = 0;
1453 absl::Cord::CharIterator pre_iter = cord.char_begin();
1454 absl::Cord::CharIterator post_iter = cord.char_begin();
1455 std::string content(cord);
1456 while (pre_iter != cord.char_end() && post_iter != cord.char_end()) {
1457 EXPECT_FALSE(pre_iter == cord.char_end()); // NOLINT: explicitly test ==
1458 EXPECT_FALSE(post_iter == cord.char_end()); // NOLINT
1459
1460 EXPECT_LT(i, cord.size());
1461 EXPECT_EQ(content[i], *pre_iter);
1462
1463 EXPECT_EQ(pre_iter, post_iter);
1464 EXPECT_EQ(*pre_iter, *post_iter);
1465 EXPECT_EQ(&*pre_iter, &*post_iter);
1466
1467 EXPECT_EQ(&*pre_iter, pre_iter.operator->());
1468
1469 const char* character_address = &*pre_iter;
1470 absl::Cord::CharIterator copy = pre_iter;
1471 ++copy;
1472 EXPECT_EQ(character_address, &*pre_iter);
1473
1474 int n_equal_iterators = 0;
1475 for (absl::Cord::CharIterator it = range.begin(); it != range.end(); ++it) {
1476 n_equal_iterators += static_cast<int>(it == pre_iter);
1477 }
1478 EXPECT_EQ(n_equal_iterators, 1);
1479
1480 absl::Cord::CharIterator advance_iter = range.begin();
1481 absl::Cord::Advance(&advance_iter, i);
1482 EXPECT_EQ(pre_iter, advance_iter);
1483
1484 advance_iter = range.begin();
1485 EXPECT_EQ(absl::Cord::AdvanceAndRead(&advance_iter, i), cord.Subcord(0, i));
1486 EXPECT_EQ(pre_iter, advance_iter);
1487
1488 advance_iter = pre_iter;
1489 absl::Cord::Advance(&advance_iter, cord.size() - i);
1490 EXPECT_EQ(range.end(), advance_iter);
1491
1492 advance_iter = pre_iter;
1493 EXPECT_EQ(absl::Cord::AdvanceAndRead(&advance_iter, cord.size() - i),
1494 cord.Subcord(i, cord.size() - i));
1495 EXPECT_EQ(range.end(), advance_iter);
1496
1497 ++i;
1498 ++pre_iter;
1499 post_iter++;
1500 }
1501 EXPECT_EQ(i, cord.size());
1502 EXPECT_TRUE(pre_iter == cord.char_end()); // NOLINT: explicitly test ==
1503 EXPECT_TRUE(post_iter == cord.char_end()); // NOLINT
1504
1505 absl::Cord::CharIterator zero_advanced_end = cord.char_end();
1506 absl::Cord::Advance(&zero_advanced_end, 0);
1507 EXPECT_EQ(zero_advanced_end, cord.char_end());
1508
1509 absl::Cord::CharIterator it = cord.char_begin();
1510 for (absl::string_view chunk : cord.Chunks()) {
1511 while (!chunk.empty()) {
1512 EXPECT_EQ(absl::Cord::ChunkRemaining(it), chunk);
1513 chunk.remove_prefix(1);
1514 ++it;
1515 }
1516 }
1517 }
1518
TEST(CordCharIterator,Operations)1519 TEST(CordCharIterator, Operations) {
1520 absl::Cord empty_cord;
1521 VerifyCharIterator(empty_cord);
1522
1523 absl::Cord small_buffer_cord("small cord");
1524 VerifyCharIterator(small_buffer_cord);
1525
1526 absl::Cord flat_node_cord("larger than small buffer optimization");
1527 VerifyCharIterator(flat_node_cord);
1528
1529 VerifyCharIterator(
1530 absl::MakeFragmentedCord({"a ", "small ", "fragmented ", "cord ", "for ",
1531 "testing ", "character ", "iteration."}));
1532
1533 absl::Cord reused_nodes_cord("ghi");
1534 reused_nodes_cord.Prepend(absl::Cord("def"));
1535 reused_nodes_cord.Prepend(absl::Cord("abc"));
1536 for (int i = 0; i < 4; ++i) {
1537 reused_nodes_cord.Prepend(reused_nodes_cord);
1538 VerifyCharIterator(reused_nodes_cord);
1539 }
1540
1541 RandomEngine rng(testing::GTEST_FLAG(random_seed));
1542 absl::Cord flat_cord(RandomLowercaseString(&rng, 256));
1543 absl::Cord subcords;
1544 for (int i = 0; i < 4; ++i) subcords.Prepend(flat_cord.Subcord(16 * i, 128));
1545 VerifyCharIterator(subcords);
1546 }
1547
TEST(Cord,StreamingOutput)1548 TEST(Cord, StreamingOutput) {
1549 absl::Cord c =
1550 absl::MakeFragmentedCord({"A ", "small ", "fragmented ", "Cord", "."});
1551 std::stringstream output;
1552 output << c;
1553 EXPECT_EQ("A small fragmented Cord.", output.str());
1554 }
1555
TEST(Cord,ForEachChunk)1556 TEST(Cord, ForEachChunk) {
1557 for (int num_elements : {1, 10, 200}) {
1558 SCOPED_TRACE(num_elements);
1559 std::vector<std::string> cord_chunks;
1560 for (int i = 0; i < num_elements; ++i) {
1561 cord_chunks.push_back(absl::StrCat("[", i, "]"));
1562 }
1563 absl::Cord c = absl::MakeFragmentedCord(cord_chunks);
1564
1565 std::vector<std::string> iterated_chunks;
1566 absl::CordTestPeer::ForEachChunk(c,
1567 [&iterated_chunks](absl::string_view sv) {
1568 iterated_chunks.emplace_back(sv);
1569 });
1570 EXPECT_EQ(iterated_chunks, cord_chunks);
1571 }
1572 }
1573
TEST(Cord,SmallBufferAssignFromOwnData)1574 TEST(Cord, SmallBufferAssignFromOwnData) {
1575 constexpr size_t kMaxInline = 15;
1576 std::string contents = "small buff cord";
1577 EXPECT_EQ(contents.size(), kMaxInline);
1578 for (size_t pos = 0; pos < contents.size(); ++pos) {
1579 for (size_t count = contents.size() - pos; count > 0; --count) {
1580 absl::Cord c(contents);
1581 absl::string_view flat = c.Flatten();
1582 c = flat.substr(pos, count);
1583 EXPECT_EQ(c, contents.substr(pos, count))
1584 << "pos = " << pos << "; count = " << count;
1585 }
1586 }
1587 }
1588
TEST(Cord,Format)1589 TEST(Cord, Format) {
1590 absl::Cord c;
1591 absl::Format(&c, "There were %04d little %s.", 3, "pigs");
1592 EXPECT_EQ(c, "There were 0003 little pigs.");
1593 absl::Format(&c, "And %-3llx bad wolf!", 1);
1594 EXPECT_EQ(c, "There were 0003 little pigs.And 1 bad wolf!");
1595 }
1596
TEST(CordDeathTest,Hardening)1597 TEST(CordDeathTest, Hardening) {
1598 absl::Cord cord("hello");
1599 // These statement should abort the program in all builds modes.
1600 EXPECT_DEATH_IF_SUPPORTED(cord.RemovePrefix(6), "");
1601 EXPECT_DEATH_IF_SUPPORTED(cord.RemoveSuffix(6), "");
1602
1603 bool test_hardening = false;
1604 ABSL_HARDENING_ASSERT([&]() {
1605 // This only runs when ABSL_HARDENING_ASSERT is active.
1606 test_hardening = true;
1607 return true;
1608 }());
1609 if (!test_hardening) return;
1610
1611 EXPECT_DEATH_IF_SUPPORTED(cord[5], "");
1612 EXPECT_DEATH_IF_SUPPORTED(*cord.chunk_end(), "");
1613 EXPECT_DEATH_IF_SUPPORTED(static_cast<void>(cord.chunk_end()->empty()), "");
1614 EXPECT_DEATH_IF_SUPPORTED(++cord.chunk_end(), "");
1615 }
1616