folly/test/FBStringTest.cpp

   1 /*
   2  * Copyright 2012 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 //
  18 // Author: andrei.alexandrescu@fb.com
  19
  20 #include "folly/FBString.h"
  21
  22 #include <list>
  23 #include <fstream>
  24 #include <boost/algorithm/string.hpp>
  25 #include <boost/random.hpp>
  26 #include <gtest/gtest.h>
  27
  28 #include <gflags/gflags.h>
  29
  30 #include "folly/Foreach.h"
  31 #include "folly/Random.h"
  32 #include "folly/Benchmark.h"
  33
  34 using namespace std;
  35 using namespace folly;
  36
  37 static const int seed = folly::randomNumberSeed();
  38 typedef boost::mt19937 RandomT;
  39 static RandomT rng(seed);
  40 static const size_t maxString = 100;
  41 static const bool avoidAliasing = true;
  42
  43 template <class Integral1, class Integral2>
  44 Integral2 random(Integral1 low, Integral2 up) {
  45   boost::uniform_int<> range(low, up);
  46   return range(rng);
  47 }
  48
  49 template <class String>
  50 void randomString(String* toFill, unsigned int maxSize = 1000) {
  51   assert(toFill);
  52   toFill->resize(random(0, maxSize));
  53   FOR_EACH (i, *toFill) {
  54     *i = random('a', 'z');
  55   }
  56 }
  57
  58 template <class String, class Integral>
  59 void Num2String(String& str, Integral n) {
  60   str.resize(30, '\0');
  61   sprintf(&str[0], "%lu", static_cast<unsigned long>(n));
  62   str.resize(strlen(str.c_str()));
  63 }
  64
  65 std::list<char> RandomList(unsigned int maxSize) {
  66   std::list<char> lst(random(0u, maxSize));
  67   std::list<char>::iterator i = lst.begin();
  68   for (; i != lst.end(); ++i) {
  69     *i = random('a', 'z');
  70  }
  71   return lst;
  72 }
  73
  74 // void preventOptimization(void * p) {
  75 //   return folly::preventOptimization((int)(long) p);
  76 // }
  77
  78 ////////////////////////////////////////////////////////////////////////////////
  79 // Tests begin here
  80 ////////////////////////////////////////////////////////////////////////////////
  81
  82 template <class String> void clause_21_3_1_a(String & test) {
  83   test.String::~String();
  84   new(&test) String();
  85 }
  86 template <class String> void clause_21_3_1_b(String & test) {
  87   // Copy constructor
  88   const size_t pos = random(0, test.size());
  89   String s(test, pos, random(0, (size_t)(test.size() - pos)));
  90   test = s;
  91 }
  92 template <class String> void clause_21_3_1_c(String & test) {
  93   // Constructor from char*, size_t
  94   const size_t
  95     pos = random(0, test.size()),
  96     n = random(0, test.size() - pos);
  97   std::string before(test.data(), test.size());
  98   String s(test.c_str() + pos, n);
  99   std::string after(test.data(), test.size());
 100   EXPECT_EQ(before, after);
 101
 102   // Constructor from char*, char*
 103   String s1(test.begin(), test.end());
 104   EXPECT_EQ(test, s1);
 105   String s2(test.data(), test.data() + test.size());
 106   EXPECT_EQ(test, s2);
 107
 108   // Constructor from iterators
 109   std::list<char> lst;
 110   for (auto c : test) lst.push_back(c);
 111   String s3(lst.begin(), lst.end());
 112   EXPECT_EQ(test, s3);
 113
 114   // Constructor from wchar_t iterators
 115   std::list<wchar_t> lst1;
 116   for (auto c : test) lst1.push_back(c);
 117   String s4(lst1.begin(), lst1.end());
 118   EXPECT_EQ(test, s4);
 119
 120   // Constructor from wchar_t pointers
 121   wchar_t t[20];
 122   t[0] = 'a';
 123   t[1] = 'b';
 124   String s5(t, t + 2);;
 125   EXPECT_EQ("ab", s5);
 126
 127   test = s;
 128 }
 129 template <class String> void clause_21_3_1_d(String & test) {
 130   // Assignment
 131   auto size = random(0, 2000);
 132   String s(size, '\0');
 133   EXPECT_EQ(s.size(), size);
 134   FOR_EACH_RANGE (i, 0, s.size()) {
 135     s[i] = random('a', 'z');
 136   }
 137   test = s;
 138 }
 139 template <class String> void clause_21_3_1_e(String & test) {
 140   // Assignment from char*
 141   String s(random(0, 1000), '\0');
 142   size_t i = 0;
 143   for (; i != s.size(); ++i) {
 144     s[i] = random('a', 'z');
 145   }
 146   test = s.c_str();
 147 }
 148 template <class String> void clause_21_3_1_f(String & test) {
 149   // Aliased assign
 150   const size_t pos = random(0, test.size());
 151   if (avoidAliasing) {
 152     test = String(test.c_str() + pos);
 153   } else {
 154     test = test.c_str() + pos;
 155   }
 156 }
 157 template <class String> void clause_21_3_1_g(String & test) {
 158   // Assignment from char
 159   test = random('a', 'z');
 160 }
 161
 162 template <class String> void clause_21_3_2(String & test) {
 163   // Iterators. The code below should leave test unchanged
 164   EXPECT_EQ(test.size(), test.end() - test.begin());
 165   EXPECT_EQ(test.size(), test.rend() - test.rbegin());
 166
 167   auto s = test.size();
 168   test.resize(test.end() - test.begin());
 169   EXPECT_EQ(s, test.size());
 170   test.resize(test.rend() - test.rbegin());
 171   EXPECT_EQ(s, test.size());
 172 }
 173
 174 template <class String> void clause_21_3_3(String & test) {
 175   // exercise capacity, size, max_size
 176   EXPECT_EQ(test.size(), test.length());
 177   EXPECT_LE(test.size(), test.max_size());
 178   EXPECT_LE(test.capacity(), test.max_size());
 179   EXPECT_LE(test.size(), test.capacity());
 180   // exercise empty
 181   if (test.empty()) test = "empty";
 182   else test = "not empty";
 183 }
 184
 185 template <class String> void clause_21_3_4(String & test) {
 186   // exercise element access 21.3.4
 187   if (!test.empty()) {
 188     auto const i = random(0, test.size() - 1);
 189     EXPECT_EQ(test[i], test.at(i));
 190     test = test[i];
 191   }
 192 }
 193
 194 template <class String> void clause_21_3_5_a(String & test) {
 195   // 21.3.5 modifiers (+=)
 196   String test1;
 197   randomString(&test1);
 198   assert(test1.size() == strlen(test1.c_str()));
 199   auto len = test.size();
 200   test += test1;
 201   EXPECT_EQ(test.size(), test1.size() + len);
 202   FOR_EACH_RANGE (i, 0, test1.size()) {
 203     EXPECT_EQ(test[len + i], test1[i]);
 204   }
 205   // aliasing modifiers
 206   String test2 = test;
 207   auto dt = test2.data();
 208   auto sz = test.c_str();
 209   len = test.size();
 210   EXPECT_EQ(memcmp(sz, dt, len), 0);
 211   String copy(test.data(), test.size());
 212   EXPECT_EQ(strlen(test.c_str()), len);
 213   test += test;
 214   //test.append(test);
 215   EXPECT_EQ(test.size(), 2 * len);
 216   EXPECT_EQ(strlen(test.c_str()), 2 * len);
 217   FOR_EACH_RANGE (i, 0, len) {
 218     EXPECT_EQ(test[i], copy[i]);
 219     EXPECT_EQ(test[i], test[len + i]);
 220   }
 221   len = test.size();
 222   EXPECT_EQ(strlen(test.c_str()), len);
 223   // more aliasing
 224   auto const pos = random(0, test.size());
 225   EXPECT_EQ(strlen(test.c_str() + pos), len - pos);
 226   if (avoidAliasing) {
 227     String addMe(test.c_str() + pos);
 228     EXPECT_EQ(addMe.size(), len - pos);
 229     test += addMe;
 230   } else {
 231     test += test.c_str() + pos;
 232   }
 233   EXPECT_EQ(test.size(), 2 * len - pos);
 234   // single char
 235   len = test.size();
 236   test += random('a', 'z');
 237   EXPECT_EQ(test.size(), len + 1);
 238 }
 239
 240 template <class String> void clause_21_3_5_b(String & test) {
 241   // 21.3.5 modifiers (append, push_back)
 242   String s;
 243
 244   // Test with a small string first
 245   char c = random('a', 'z');
 246   s.push_back(c);
 247   EXPECT_EQ(s[s.size() - 1], c);
 248   EXPECT_EQ(s.size(), 1);
 249   s.resize(s.size() - 1);
 250
 251   randomString(&s, maxString);
 252   test.append(s);
 253   randomString(&s, maxString);
 254   test.append(s, random(0, s.size()), random(0, maxString));
 255   randomString(&s, maxString);
 256   test.append(s.c_str(), random(0, s.size()));
 257   randomString(&s, maxString);
 258   test.append(s.c_str());
 259   test.append(random(0, maxString), random('a', 'z'));
 260   std::list<char> lst(RandomList(maxString));
 261   test.append(lst.begin(), lst.end());
 262   c = random('a', 'z');
 263   test.push_back(c);
 264   EXPECT_EQ(test[test.size() - 1], c);
 265 }
 266
 267 template <class String> void clause_21_3_5_c(String & test) {
 268   // assign
 269   String s;
 270   randomString(&s);
 271   test.assign(s);
 272 }
 273
 274 template <class String> void clause_21_3_5_d(String & test) {
 275   // assign
 276   String s;
 277   randomString(&s, maxString);
 278   test.assign(s, random(0, s.size()), random(0, maxString));
 279 }
 280
 281 template <class String> void clause_21_3_5_e(String & test) {
 282   // assign
 283   String s;
 284   randomString(&s, maxString);
 285   test.assign(s.c_str(), random(0, s.size()));
 286 }
 287
 288 template <class String> void clause_21_3_5_f(String & test) {
 289   // assign
 290   String s;
 291   randomString(&s, maxString);
 292   test.assign(s.c_str());
 293 }
 294
 295 template <class String> void clause_21_3_5_g(String & test) {
 296   // assign
 297   String s;
 298   randomString(&s, maxString);
 299   test.assign(random(0, maxString), random('a', 'z'));
 300 }
 301
 302 template <class String> void clause_21_3_5_h(String & test) {
 303   // assign from bidirectional iterator
 304   std::list<char> lst(RandomList(maxString));
 305   test.assign(lst.begin(), lst.end());
 306 }
 307
 308 template <class String> void clause_21_3_5_i(String & test) {
 309   // assign from aliased source
 310   test.assign(test);
 311 }
 312
 313 template <class String> void clause_21_3_5_j(String & test) {
 314   // assign from aliased source
 315   test.assign(test, random(0, test.size()), random(0, maxString));
 316 }
 317
 318 template <class String> void clause_21_3_5_k(String & test) {
 319   // assign from aliased source
 320   test.assign(test.c_str(), random(0, test.size()));
 321 }
 322
 323 template <class String> void clause_21_3_5_l(String & test) {
 324   // assign from aliased source
 325   test.assign(test.c_str());
 326 }
 327
 328 template <class String> void clause_21_3_5_m(String & test) {
 329   // insert
 330   String s;
 331   randomString(&s, maxString);
 332   test.insert(random(0, test.size()), s);
 333   randomString(&s, maxString);
 334   test.insert(random(0, test.size()),
 335               s, random(0, s.size()),
 336               random(0, maxString));
 337   randomString(&s, maxString);
 338   test.insert(random(0, test.size()),
 339               s.c_str(), random(0, s.size()));
 340   randomString(&s, maxString);
 341   test.insert(random(0, test.size()), s.c_str());
 342   test.insert(random(0, test.size()),
 343               random(0, maxString), random('a', 'z'));
 344   test.insert(test.begin() + random(0, test.size()),
 345               random('a', 'z'));
 346   std::list<char> lst(RandomList(maxString));
 347   test.insert(test.begin() + random(0, test.size()),
 348               lst.begin(), lst.end());
 349 }
 350
 351 template <class String> void clause_21_3_5_n(String & test) {
 352   // erase
 353   if (!test.empty()) {
 354     test.erase(random(0, test.size()), random(0, maxString));
 355   }
 356   if (!test.empty()) {
 357     // TODO: is erase(end()) allowed?
 358     test.erase(test.begin() + random(0, test.size() - 1));
 359   }
 360   if (!test.empty()) {
 361     auto const i = test.begin() + random(0, test.size());
 362     if (i != test.end()) {
 363       test.erase(i, i + random(0, size_t(test.end() - i)));
 364     }
 365   }
 366 }
 367
 368 template <class String> void clause_21_3_5_o(String & test) {
 369   auto pos = random(0, test.size());
 370   if (avoidAliasing) {
 371     test.replace(pos, random(0, test.size() - pos),
 372                  String(test));
 373   } else {
 374     test.replace(pos, random(0, test.size() - pos), test);
 375   }
 376   pos = random(0, test.size());
 377   String s;
 378   randomString(&s, maxString);
 379   test.replace(pos, pos + random(0, test.size() - pos), s);
 380   auto pos1 = random(0, test.size());
 381   auto pos2 = random(0, test.size());
 382   if (avoidAliasing) {
 383     test.replace(pos1, pos1 + random(0, test.size() - pos1),
 384                  String(test),
 385                  pos2, pos2 + random(0, test.size() - pos2));
 386   } else {
 387     test.replace(pos1, pos1 + random(0, test.size() - pos1),
 388                  test, pos2, pos2 + random(0, test.size() - pos2));
 389   }
 390   pos1 = random(0, test.size());
 391   String str;
 392   randomString(&str, maxString);
 393   pos2 = random(0, str.size());
 394   test.replace(pos1, pos1 + random(0, test.size() - pos1),
 395                str, pos2, pos2 + random(0, str.size() - pos2));
 396   pos = random(0, test.size());
 397   if (avoidAliasing) {
 398     test.replace(pos, random(0, test.size() - pos),
 399                  String(test).c_str(), test.size());
 400   } else {
 401     test.replace(pos, random(0, test.size() - pos),
 402                  test.c_str(), test.size());
 403   }
 404   pos = random(0, test.size());
 405   randomString(&str, maxString);
 406   test.replace(pos, pos + random(0, test.size() - pos),
 407                str.c_str(), str.size());
 408   pos = random(0, test.size());
 409   randomString(&str, maxString);
 410   test.replace(pos, pos + random(0, test.size() - pos),
 411                str.c_str());
 412   pos = random(0, test.size());
 413   test.replace(pos, random(0, test.size() - pos),
 414                random(0, maxString), random('a', 'z'));
 415   pos = random(0, test.size());
 416   if (avoidAliasing) {
 417     test.replace(
 418       test.begin() + pos,
 419       test.begin() + pos + random(0, test.size() - pos),
 420       String(test));
 421   } else {
 422     test.replace(
 423       test.begin() + pos,
 424       test.begin() + pos + random(0, test.size() - pos),
 425       test);
 426   }
 427   pos = random(0, test.size());
 428   if (avoidAliasing) {
 429     test.replace(
 430       test.begin() + pos,
 431       test.begin() + pos + random(0, test.size() - pos),
 432       String(test).c_str(),
 433       test.size() - random(0, test.size()));
 434   } else {
 435     test.replace(
 436       test.begin() + pos,
 437       test.begin() + pos + random(0, test.size() - pos),
 438       test.c_str(),
 439       test.size() - random(0, test.size()));
 440   }
 441   pos = random(0, test.size());
 442   auto const n = random(0, test.size() - pos);
 443   typename String::iterator b = test.begin();
 444   String str1;
 445   randomString(&str1, maxString);
 446   const String & str3 = str1;
 447   const typename String::value_type* ss = str3.c_str();
 448   test.replace(
 449     b + pos,
 450     b + pos + n,
 451     ss);
 452   pos = random(0, test.size());
 453   test.replace(
 454     test.begin() + pos,
 455     test.begin() + pos + random(0, test.size() - pos),
 456     random(0, maxString), random('a', 'z'));
 457 }
 458
 459 template <class String> void clause_21_3_5_p(String & test) {
 460   std::vector<typename String::value_type>
 461     vec(random(0, maxString));
 462   test.copy(
 463     &vec[0],
 464     vec.size(),
 465     random(0, test.size()));
 466 }
 467
 468 template <class String> void clause_21_3_5_q(String & test) {
 469   String s;
 470   randomString(&s, maxString);
 471   s.swap(test);
 472 }
 473
 474 template <class String> void clause_21_3_6_a(String & test) {
 475   // 21.3.6 string operations
 476   // exercise c_str() and data()
 477   assert(test.c_str() == test.data());
 478   // exercise get_allocator()
 479   String s;
 480   randomString(&s, maxString);
 481   assert(test.get_allocator() == s.get_allocator());
 482 }
 483
 484 template <class String> void clause_21_3_6_b(String & test) {
 485   String str = test.substr(
 486     random(0, test.size()),
 487     random(0, test.size()));
 488   Num2String(test, test.find(str, random(0, test.size())));
 489 }
 490
 491 template <class String> void clause_21_3_6_c(String & test) {
 492   auto from = random(0, test.size());
 493   auto length = random(0, test.size() - from);
 494   String str = test.substr(from, length);
 495   Num2String(test, test.find(str.c_str(),
 496                              random(0, test.size()),
 497                              random(0, str.size())));
 498 }
 499
 500 template <class String> void clause_21_3_6_d(String & test) {
 501   String str = test.substr(
 502     random(0, test.size()),
 503     random(0, test.size()));
 504   Num2String(test, test.find(str.c_str(),
 505                              random(0, test.size())));
 506 }
 507
 508 template <class String> void clause_21_3_6_e(String & test) {
 509   Num2String(test, test.find(
 510                random('a', 'z'),
 511                random(0, test.size())));
 512 }
 513
 514 template <class String> void clause_21_3_6_f(String & test) {
 515   String str = test.substr(
 516     random(0, test.size()),
 517     random(0, test.size()));
 518   Num2String(test, test.rfind(str, random(0, test.size())));
 519 }
 520
 521 template <class String> void clause_21_3_6_g(String & test) {
 522   String str = test.substr(
 523     random(0, test.size()),
 524     random(0, test.size()));
 525   Num2String(test, test.rfind(str.c_str(),
 526                               random(0, test.size()),
 527                               random(0, str.size())));
 528 }
 529
 530 template <class String> void clause_21_3_6_h(String & test) {
 531   String str = test.substr(
 532     random(0, test.size()),
 533     random(0, test.size()));
 534   Num2String(test, test.rfind(str.c_str(),
 535                               random(0, test.size())));
 536 }
 537
 538 template <class String> void clause_21_3_6_i(String & test) {
 539   Num2String(test, test.rfind(
 540                random('a', 'z'),
 541                random(0, test.size())));
 542 }
 543
 544 template <class String> void clause_21_3_6_j(String & test) {
 545   String str;
 546   randomString(&str, maxString);
 547   Num2String(test, test.find_first_of(str,
 548                                       random(0, test.size())));
 549 }
 550
 551 template <class String> void clause_21_3_6_k(String & test) {
 552   String str;
 553   randomString(&str, maxString);
 554   Num2String(test, test.find_first_of(str.c_str(),
 555                                       random(0, test.size()),
 556                                       random(0, str.size())));
 557 }
 558
 559 template <class String> void clause_21_3_6_l(String & test) {
 560   String str;
 561   randomString(&str, maxString);
 562   Num2String(test, test.find_first_of(str.c_str(),
 563                                       random(0, test.size())));
 564 }
 565
 566 template <class String> void clause_21_3_6_m(String & test) {
 567   Num2String(test, test.find_first_of(
 568                random('a', 'z'),
 569                random(0, test.size())));
 570 }
 571
 572 template <class String> void clause_21_3_6_n(String & test) {
 573   String str;
 574   randomString(&str, maxString);
 575   Num2String(test, test.find_last_of(str,
 576                                      random(0, test.size())));
 577 }
 578
 579 template <class String> void clause_21_3_6_o(String & test) {
 580   String str;
 581   randomString(&str, maxString);
 582   Num2String(test, test.find_last_of(str.c_str(),
 583                                      random(0, test.size()),
 584                                      random(0, str.size())));
 585 }
 586
 587 template <class String> void clause_21_3_6_p(String & test) {
 588   String str;
 589   randomString(&str, maxString);
 590   Num2String(test, test.find_last_of(str.c_str(),
 591                                      random(0, test.size())));
 592 }
 593
 594 template <class String> void clause_21_3_6_q(String & test) {
 595   Num2String(test, test.find_last_of(
 596                random('a', 'z'),
 597                random(0, test.size())));
 598 }
 599
 600 template <class String> void clause_21_3_6_r(String & test) {
 601   String str;
 602   randomString(&str, maxString);
 603   Num2String(test, test.find_first_not_of(str,
 604                                           random(0, test.size())));
 605 }
 606
 607 template <class String> void clause_21_3_6_s(String & test) {
 608   String str;
 609   randomString(&str, maxString);
 610   Num2String(test, test.find_first_not_of(str.c_str(),
 611                                           random(0, test.size()),
 612                                           random(0, str.size())));
 613 }
 614
 615 template <class String> void clause_21_3_6_t(String & test) {
 616   String str;
 617   randomString(&str, maxString);
 618   Num2String(test, test.find_first_not_of(str.c_str(),
 619                                           random(0, test.size())));
 620 }
 621
 622 template <class String> void clause_21_3_6_u(String & test) {
 623   Num2String(test, test.find_first_not_of(
 624                random('a', 'z'),
 625                random(0, test.size())));
 626 }
 627
 628 template <class String> void clause_21_3_6_v(String & test) {
 629   String str;
 630   randomString(&str, maxString);
 631   Num2String(test, test.find_last_not_of(str,
 632                                          random(0, test.size())));
 633 }
 634
 635 template <class String> void clause_21_3_6_w(String & test) {
 636   String str;
 637   randomString(&str, maxString);
 638   Num2String(test, test.find_last_not_of(str.c_str(),
 639                                          random(0, test.size()),
 640                                          random(0, str.size())));
 641 }
 642
 643 template <class String> void clause_21_3_6_x(String & test) {
 644   String str;
 645   randomString(&str, maxString);
 646   Num2String(test, test.find_last_not_of(str.c_str(),
 647                                          random(0, test.size())));
 648 }
 649
 650 template <class String> void clause_21_3_6_y(String & test) {
 651   Num2String(test, test.find_last_not_of(
 652                random('a', 'z'),
 653                random(0, test.size())));
 654 }
 655
 656 template <class String> void clause_21_3_6_z(String & test) {
 657   test = test.substr(random(0, test.size()), random(0, test.size()));
 658 }
 659
 660 template <class String> void clause_21_3_7_a(String & test) {
 661   String s;
 662   randomString(&s, maxString);
 663   int tristate = test.compare(s);
 664   if (tristate > 0) tristate = 1;
 665   else if (tristate < 0) tristate = 2;
 666   Num2String(test, tristate);
 667 }
 668
 669 template <class String> void clause_21_3_7_b(String & test) {
 670   String s;
 671   randomString(&s, maxString);
 672   int tristate = test.compare(
 673     random(0, test.size()),
 674     random(0, test.size()),
 675     s);
 676   if (tristate > 0) tristate = 1;
 677   else if (tristate < 0) tristate = 2;
 678   Num2String(test, tristate);
 679 }
 680
 681 template <class String> void clause_21_3_7_c(String & test) {
 682   String str;
 683   randomString(&str, maxString);
 684   int tristate = test.compare(
 685     random(0, test.size()),
 686     random(0, test.size()),
 687     str,
 688     random(0, str.size()),
 689     random(0, str.size()));
 690   if (tristate > 0) tristate = 1;
 691   else if (tristate < 0) tristate = 2;
 692   Num2String(test, tristate);
 693 }
 694
 695 template <class String> void clause_21_3_7_d(String & test) {
 696   String s;
 697   randomString(&s, maxString);
 698   int tristate = test.compare(s.c_str());
 699   if (tristate > 0) tristate = 1;
 700   else if (tristate < 0) tristate = 2;
 701                 Num2String(test, tristate);
 702 }
 703
 704 template <class String> void clause_21_3_7_e(String & test) {
 705   String str;
 706   randomString(&str, maxString);
 707   int tristate = test.compare(
 708     random(0, test.size()),
 709     random(0, test.size()),
 710     str.c_str(),
 711     random(0, str.size()));
 712   if (tristate > 0) tristate = 1;
 713   else if (tristate < 0) tristate = 2;
 714   Num2String(test, tristate);
 715 }
 716
 717 template <class String> void clause_21_3_7_f(String & test) {
 718   String s1;
 719   randomString(&s1, maxString);
 720   String s2;
 721   randomString(&s2, maxString);
 722   test = s1 + s2;
 723 }
 724
 725 template <class String> void clause_21_3_7_g(String & test) {
 726   String s;
 727   randomString(&s, maxString);
 728   String s1;
 729   randomString(&s1, maxString);
 730   test = s.c_str() + s1;
 731 }
 732
 733 template <class String> void clause_21_3_7_h(String & test) {
 734   String s;
 735   randomString(&s, maxString);
 736   test = typename String::value_type(random('a', 'z')) + s;
 737 }
 738
 739 template <class String> void clause_21_3_7_i(String & test) {
 740   String s;
 741   randomString(&s, maxString);
 742   String s1;
 743   randomString(&s1, maxString);
 744   test = s + s1.c_str();
 745 }
 746
 747 template <class String> void clause_21_3_7_j(String & test) {
 748   String s;
 749   randomString(&s, maxString);
 750   String s1;
 751   randomString(&s1, maxString);
 752   test = s + s1.c_str();
 753 }
 754
 755 template <class String> void clause_21_3_7_k(String & test) {
 756   String s;
 757   randomString(&s, maxString);
 758   test = s + typename String::value_type(random('a', 'z'));
 759 }
 760
 761 // Numbering here is from C++11
 762 template <class String> void clause_21_4_8_9_a(String & test) {
 763   stringstream s("asd asdfjhuhdf    asdfasdf\tasdsdf");
 764   String str;
 765   while (s) {
 766     s >> str;
 767     test += str + test;
 768   }
 769 }
 770
 771 TEST(FBString, testAllClauses) {
 772   EXPECT_TRUE(1) << "Starting with seed: " << seed;
 773   std::string r;
 774   folly::fbstring c;
 775 #define TEST_CLAUSE(x)                                              \
 776   do {                                                              \
 777       if (1) {} else EXPECT_TRUE(1) << "Testing clause " << #x;     \
 778       randomString(&r);                                             \
 779       c = r;                                                        \
 780       EXPECT_EQ(c, r);                                              \
 781       auto localSeed = seed + count;                                \
 782       rng = RandomT(localSeed);                                     \
 783       clause_##x(r);                                                \
 784       rng = RandomT(localSeed);                                     \
 785       clause_##x(c);                                                \
 786       EXPECT_EQ(r, c)                                               \
 787         << "Lengths: " << r.size() << " vs. " << c.size()           \
 788         << "\nReference: '" << r << "'"                             \
 789         << "\nActual:    '" << c.data()[0] << "'";                  \
 790     } while (++count % 100 != 0)
 791
 792   int count = 0;
 793   TEST_CLAUSE(21_3_1_a);
 794   TEST_CLAUSE(21_3_1_b);
 795   TEST_CLAUSE(21_3_1_c);
 796   TEST_CLAUSE(21_3_1_d);
 797   TEST_CLAUSE(21_3_1_e);
 798   TEST_CLAUSE(21_3_1_f);
 799   TEST_CLAUSE(21_3_1_g);
 800
 801   TEST_CLAUSE(21_3_2);
 802   TEST_CLAUSE(21_3_3);
 803   TEST_CLAUSE(21_3_4);
 804   TEST_CLAUSE(21_3_5_a);
 805   TEST_CLAUSE(21_3_5_b);
 806   TEST_CLAUSE(21_3_5_c);
 807   TEST_CLAUSE(21_3_5_d);
 808   TEST_CLAUSE(21_3_5_e);
 809   TEST_CLAUSE(21_3_5_f);
 810   TEST_CLAUSE(21_3_5_g);
 811   TEST_CLAUSE(21_3_5_h);
 812   TEST_CLAUSE(21_3_5_i);
 813   TEST_CLAUSE(21_3_5_j);
 814   TEST_CLAUSE(21_3_5_k);
 815   TEST_CLAUSE(21_3_5_l);
 816   TEST_CLAUSE(21_3_5_m);
 817   TEST_CLAUSE(21_3_5_n);
 818   TEST_CLAUSE(21_3_5_o);
 819   TEST_CLAUSE(21_3_5_p);
 820
 821   TEST_CLAUSE(21_3_6_a);
 822   TEST_CLAUSE(21_3_6_b);
 823   TEST_CLAUSE(21_3_6_c);
 824   TEST_CLAUSE(21_3_6_d);
 825   TEST_CLAUSE(21_3_6_e);
 826   TEST_CLAUSE(21_3_6_f);
 827   TEST_CLAUSE(21_3_6_g);
 828   TEST_CLAUSE(21_3_6_h);
 829   TEST_CLAUSE(21_3_6_i);
 830   TEST_CLAUSE(21_3_6_j);
 831   TEST_CLAUSE(21_3_6_k);
 832   TEST_CLAUSE(21_3_6_l);
 833   TEST_CLAUSE(21_3_6_m);
 834   TEST_CLAUSE(21_3_6_n);
 835   TEST_CLAUSE(21_3_6_o);
 836   TEST_CLAUSE(21_3_6_p);
 837   TEST_CLAUSE(21_3_6_q);
 838   TEST_CLAUSE(21_3_6_r);
 839   TEST_CLAUSE(21_3_6_s);
 840   TEST_CLAUSE(21_3_6_t);
 841   TEST_CLAUSE(21_3_6_u);
 842   TEST_CLAUSE(21_3_6_v);
 843   TEST_CLAUSE(21_3_6_w);
 844   TEST_CLAUSE(21_3_6_x);
 845   TEST_CLAUSE(21_3_6_y);
 846   TEST_CLAUSE(21_3_6_z);
 847
 848   TEST_CLAUSE(21_3_7_a);
 849   TEST_CLAUSE(21_3_7_b);
 850   TEST_CLAUSE(21_3_7_c);
 851   TEST_CLAUSE(21_3_7_d);
 852   TEST_CLAUSE(21_3_7_e);
 853   TEST_CLAUSE(21_3_7_f);
 854   TEST_CLAUSE(21_3_7_g);
 855   TEST_CLAUSE(21_3_7_h);
 856   TEST_CLAUSE(21_3_7_i);
 857   TEST_CLAUSE(21_3_7_j);
 858   TEST_CLAUSE(21_3_7_k);
 859
 860   TEST_CLAUSE(21_4_8_9_a);
 861 }
 862
 863 TEST(FBString, testGetline) {
 864   fbstring s1 = "\
 865 Lorem ipsum dolor sit amet, consectetur adipiscing elit. Cras accumsan \n\
 866 elit ut urna consectetur in sagittis mi auctor. Nulla facilisi. In nec \n\
 867 dolor leo, vitae imperdiet neque. Donec ut erat mauris, a faucibus \n\
 868 elit. Integer consectetur gravida augue, sit amet mattis mauris auctor \n\
 869 sed. Morbi congue libero eu nunc sodales adipiscing. In lectus nunc, \n\
 870 vulputate a fringilla at, venenatis quis justo. Proin eu velit \n\
 871 nibh. Maecenas vitae tellus eros. Pellentesque habitant morbi \n\
 872 tristique senectus et netus et malesuada fames ac turpis \n\
 873 egestas. Vivamus faucibus feugiat consequat. Donec fermentum neque sit \n\
 874 amet ligula suscipit porta. Phasellus facilisis felis in purus luctus \n\
 875 quis posuere leo tempor. Nam nunc purus, luctus a pharetra ut, \n\
 876 placerat at dui. Donec imperdiet, diam quis convallis pulvinar, dui \n\
 877 est commodo lorem, ut tincidunt diam nibh et nibh. Maecenas nec velit \n\
 878 massa, ut accumsan magna. Donec imperdiet tempor nisi et \n\
 879 laoreet. Phasellus lectus quam, ultricies ut tincidunt in, dignissim \n\
 880 id eros. Mauris vulputate tortor nec neque pellentesque sagittis quis \n\
 881 sed nisl. In diam lacus, lobortis ut posuere nec, ornare id quam.";
 882   const char* f = "/tmp/fbstring_testing";
 883   {
 884     std::ofstream out(f);
 885     if (!(out << s1)) {
 886       EXPECT_TRUE(0) << "Couldn't write to temp file.";
 887       return;
 888     }
 889   }
 890   vector<fbstring> v;
 891   boost::split(v, s1, boost::is_any_of("\n"));
 892   ifstream input(f);
 893   fbstring line;
 894   FOR_EACH (i, v) {
 895     EXPECT_TRUE(getline(input, line));
 896     EXPECT_EQ(line, *i);
 897   }
 898 }
 899
 900 TEST(FBString, testMoveCtor) {
 901   // Move constructor. Make sure we allocate a large string, so the
 902   // small string optimization doesn't kick in.
 903   auto size = random(100, 2000);
 904   fbstring s(size, 'a');
 905   fbstring test = std::move(s);
 906   EXPECT_TRUE(s.empty());
 907   EXPECT_EQ(size, test.size());
 908 }
 909
 910 TEST(FBString, testMoveAssign) {
 911   // Move constructor. Make sure we allocate a large string, so the
 912   // small string optimization doesn't kick in.
 913   auto size = random(100, 2000);
 914   fbstring s(size, 'a');
 915   fbstring test;
 916   test = std::move(s);
 917   EXPECT_TRUE(s.empty());
 918   EXPECT_EQ(size, test.size());
 919 }
 920
 921 TEST(FBString, testMoveOperatorPlusLhs) {
 922   // Make sure we allocate a large string, so the
 923   // small string optimization doesn't kick in.
 924   auto size1 = random(100, 2000);
 925   auto size2 = random(100, 2000);
 926   fbstring s1(size1, 'a');
 927   fbstring s2(size2, 'b');
 928   fbstring test;
 929   test = std::move(s1) + s2;
 930   EXPECT_TRUE(s1.empty());
 931   EXPECT_EQ(size1 + size2, test.size());
 932 }
 933
 934 TEST(FBString, testMoveOperatorPlusRhs) {
 935   // Make sure we allocate a large string, so the
 936   // small string optimization doesn't kick in.
 937   auto size1 = random(100, 2000);
 938   auto size2 = random(100, 2000);
 939   fbstring s1(size1, 'a');
 940   fbstring s2(size2, 'b');
 941   fbstring test;
 942   test = s1 + std::move(s2);
 943   EXPECT_EQ(size1 + size2, test.size());
 944 }
 945
 946 TEST(FBString, testConstructionFromLiteralZero) {
 947   try {
 948     std::string s(0);
 949     EXPECT_TRUE(false);
 950   } catch (const std::logic_error&) {
 951   } catch (...) {
 952     EXPECT_TRUE(false);
 953   }
 954
 955   try {
 956     fbstring s(0);
 957     EXPECT_TRUE(false);
 958   } catch (const std::logic_error& e) {
 959   } catch (...) {
 960     EXPECT_TRUE(false);
 961   }
 962 }
 963
 964 TEST(FBString, testFixedBugs) {
 965   { // D479397
 966     fbstring str(1337, 'f');
 967     fbstring cp = str;
 968     cp.clear();
 969     cp.c_str();
 970     EXPECT_EQ(str.front(), 'f');
 971   }
 972   { // D481173, --extra-cxxflags=-DFBSTRING_CONSERVATIVE
 973     fbstring str(1337, 'f');
 974     for (int i = 0; i < 2; ++i) {
 975       fbstring cp = str;
 976       cp[1] = 'b';
 977       EXPECT_EQ(cp.c_str()[cp.size()], '\0');
 978       cp.push_back('?');
 979     }
 980   }
 981 }
 982
 983 #define CONCAT(A, B) CONCAT_HELPER(A, B)
 984 #define CONCAT_HELPER(A, B) A##B
 985 #define BENCHFUN(F) CONCAT(CONCAT(BM_, F), CONCAT(_, STRING))
 986
 987 #define STRING string
 988 #include "folly/test/FBStringTestBenchmarks.cpp.h"
 989 #undef STRING
 990 #define STRING fbstring
 991 #include "folly/test/FBStringTestBenchmarks.cpp.h"
 992 #undef STRING
 993
 994 int main(int argc, char** argv) {
 995   testing::InitGoogleTest(&argc, argv);
 996   google::ParseCommandLineFlags(&argc, &argv, true);
 997   auto ret = RUN_ALL_TESTS();
 998   if (!ret && FLAGS_benchmark) {
 999     folly::runBenchmarks();
1000   }
1001
1002   return ret;
1003 }
1004
1005 /*
1006 malloc
1007
1008 BENCHFUN(defaultCtor)                  100000  1.426 s   14.26 us  68.47 k
1009 BM_copyCtor_string/32k                 100000  63.48 ms  634.8 ns  1.502 M
1010 BM_ctorFromArray_string/32k            100000  303.3 ms  3.033 us  321.9 k
1011 BM_ctorFromChar_string/1M              100000  9.915 ms  99.15 ns  9.619 M
1012 BM_assignmentOp_string/256             100000  69.09 ms  690.9 ns   1.38 M
1013 BENCHFUN(assignmentFill)               100000  1.775 ms  17.75 ns  53.73 M
1014 BM_resize_string/512k                  100000  1.667 s   16.67 us  58.58 k
1015 BM_findSuccessful_string/512k          100000  287.3 ms  2.873 us  339.9 k
1016 BM_findUnsuccessful_string/512k        100000  320.3 ms  3.203 us  304.9 k
1017 BM_replace_string/256                  100000  69.68 ms  696.8 ns  1.369 M
1018 BM_push_back_string/1k                 100000  433.1 ms  4.331 us  225.5 k
1019
1020 BENCHFUN(defaultCtor)                  100000  1.086 s   10.86 us  89.91 k
1021 BM_copyCtor_fbstring/32k               100000  4.218 ms  42.18 ns  22.61 M
1022 BM_ctorFromArray_fbstring/32k          100000  145.2 ms  1.452 us  672.7 k
1023 BM_ctorFromChar_fbstring/1M            100000   9.21 ms   92.1 ns  10.35 M
1024 BM_assignmentOp_fbstring/256           100000  61.95 ms  619.5 ns   1.54 M
1025 BENCHFUN(assignmentFill)               100000   1.41 ms   14.1 ns  67.64 M
1026 BM_resize_fbstring/512k                100000  1.668 s   16.68 us  58.56 k
1027 BM_findSuccessful_fbstring/512k        100000   20.6 ms    206 ns  4.629 M
1028 BM_findUnsuccessful_fbstring/512k      100000  141.3 ms  1.413 us  691.1 k
1029 BM_replace_fbstring/256                100000  77.12 ms  771.2 ns  1.237 M
1030 BM_push_back_fbstring/1k               100000  1.745 s   17.45 us  55.95 k
1031
1032 jemalloc
1033
1034 BENCHFUN(defaultCtor)                  100000  1.426 s   14.26 us   68.5 k
1035 BM_copyCtor_string/32k                 100000  275.7 ms  2.757 us  354.2 k
1036 BM_ctorFromArray_string/32k            100000    270 ms    2.7 us  361.7 k
1037 BM_ctorFromChar_string/1M              100000  10.36 ms  103.6 ns  9.206 M
1038 BM_assignmentOp_string/256             100000  70.44 ms  704.3 ns  1.354 M
1039 BENCHFUN(assignmentFill)               100000  1.766 ms  17.66 ns     54 M
1040 BM_resize_string/512k                  100000  1.675 s   16.75 us  58.29 k
1041 BM_findSuccessful_string/512k          100000  90.89 ms  908.9 ns  1.049 M
1042 BM_findUnsuccessful_string/512k        100000  315.1 ms  3.151 us  309.9 k
1043 BM_replace_string/256                  100000  71.14 ms  711.4 ns  1.341 M
1044 BM_push_back_string/1k                 100000  425.1 ms  4.251 us  229.7 k
1045
1046 BENCHFUN(defaultCtor)                  100000  1.082 s   10.82 us  90.23 k
1047 BM_copyCtor_fbstring/32k               100000  4.213 ms  42.13 ns  22.64 M
1048 BM_ctorFromArray_fbstring/32k          100000  113.2 ms  1.132 us    863 k
1049 BM_ctorFromChar_fbstring/1M            100000  9.162 ms  91.62 ns  10.41 M
1050 BM_assignmentOp_fbstring/256           100000  61.34 ms  613.4 ns  1.555 M
1051 BENCHFUN(assignmentFill)               100000  1.408 ms  14.08 ns  67.73 M
1052 BM_resize_fbstring/512k                100000  1.671 s   16.71 us  58.43 k
1053 BM_findSuccessful_fbstring/512k        100000  8.723 ms  87.23 ns  10.93 M
1054 BM_findUnsuccessful_fbstring/512k      100000  141.3 ms  1.413 us  691.2 k
1055 BM_replace_fbstring/256                100000  77.83 ms  778.3 ns  1.225 M
1056 BM_push_back_fbstring/1k               100000  1.744 s   17.44 us  55.99 k
1057 */