folly/test/FBStringTest.cpp

   1 /*
   2  * Copyright 2013 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 <cstdlib>
  23
  24 #include <list>
  25 #include <fstream>
  26 #include <boost/algorithm/string.hpp>
  27 #include <boost/random.hpp>
  28 #include <gtest/gtest.h>
  29
  30 #include <gflags/gflags.h>
  31
  32 #include "folly/Foreach.h"
  33 #include "folly/Random.h"
  34 #include "folly/Conv.h"
  35
  36 using namespace std;
  37 using namespace folly;
  38
  39 static const int seed = folly::randomNumberSeed();
  40 typedef boost::mt19937 RandomT;
  41 static RandomT rng(seed);
  42 static const size_t maxString = 100;
  43 static const bool avoidAliasing = true;
  44
  45 template <class Integral1, class Integral2>
  46 Integral2 random(Integral1 low, Integral2 up) {
  47   boost::uniform_int<> range(low, up);
  48   return range(rng);
  49 }
  50
  51 template <class String>
  52 void randomString(String* toFill, unsigned int maxSize = 1000) {
  53   assert(toFill);
  54   toFill->resize(random(0, maxSize));
  55   FOR_EACH (i, *toFill) {
  56     *i = random('a', 'z');
  57   }
  58 }
  59
  60 template <class String, class Integral>
  61 void Num2String(String& str, Integral n) {
  62
  63   std::string tmp = folly::to<std::string>(n);
  64   str = String(tmp.begin(), tmp.end());
  65 }
  66
  67 std::list<char> RandomList(unsigned int maxSize) {
  68   std::list<char> lst(random(0u, maxSize));
  69   std::list<char>::iterator i = lst.begin();
  70   for (; i != lst.end(); ++i) {
  71     *i = random('a', 'z');
  72  }
  73   return lst;
  74 }
  75
  76 ////////////////////////////////////////////////////////////////////////////////
  77 // Tests begin here
  78 ////////////////////////////////////////////////////////////////////////////////
  79
  80 template <class String> void clause11_21_4_2_a(String & test) {
  81   test.String::~String();
  82   new(&test) String();
  83 }
  84 template <class String> void clause11_21_4_2_b(String & test) {
  85   String test2(test);
  86   assert(test2 == test);
  87 }
  88 template <class String> void clause11_21_4_2_c(String & test) {
  89   // Test move constructor. There is a more specialized test, see
  90   // TEST(FBString, testMoveCtor)
  91   String donor(test);
  92   String test2(std::move(donor));
  93   EXPECT_EQ(test2, test);
  94   // Technically not required, but all implementations that actually
  95   // support move will move large strings. Make a guess for 128 as the
  96   // maximum small string optimization that's reasonable.
  97   EXPECT_LE(donor.size(), 128);
  98 }
  99 template <class String> void clause11_21_4_2_d(String & test) {
 100   // Copy constructor with position and length
 101   const size_t pos = random(0, test.size());
 102   String s(test, pos, random(0, 9)
 103            ? random(0, (size_t)(test.size() - pos))
 104            : String::npos); // test for npos, too, in 10% of the cases
 105   test = s;
 106 }
 107 template <class String> void clause11_21_4_2_e(String & test) {
 108   // Constructor from char*, size_t
 109   const size_t
 110     pos = random(0, test.size()),
 111     n = random(0, test.size() - pos);
 112   String before(test.data(), test.size());
 113   String s(test.c_str() + pos, n);
 114   String after(test.data(), test.size());
 115   EXPECT_EQ(before, after);
 116   test.swap(s);
 117 }
 118 template <class String> void clause11_21_4_2_f(String & test) {
 119   // Constructor from char*
 120   const size_t
 121     pos = random(0, test.size()),
 122     n = random(0, test.size() - pos);
 123   String before(test.data(), test.size());
 124   String s(test.c_str() + pos);
 125   String after(test.data(), test.size());
 126   EXPECT_EQ(before, after);
 127   test.swap(s);
 128 }
 129 template <class String> void clause11_21_4_2_g(String & test) {
 130   // Constructor from size_t, char
 131   const size_t n = random(0, test.size());
 132   const auto c = test.front();
 133   test = String(n, c);
 134 }
 135 template <class String> void clause11_21_4_2_h(String & test) {
 136   // Constructors from various iterator pairs
 137   // Constructor from char*, char*
 138   String s1(test.begin(), test.end());
 139   EXPECT_EQ(test, s1);
 140   String s2(test.data(), test.data() + test.size());
 141   EXPECT_EQ(test, s2);
 142   // Constructor from other iterators
 143   std::list<char> lst;
 144   for (auto c : test) lst.push_back(c);
 145   String s3(lst.begin(), lst.end());
 146   EXPECT_EQ(test, s3);
 147   // Constructor from wchar_t iterators
 148   std::list<wchar_t> lst1;
 149   for (auto c : test) lst1.push_back(c);
 150   String s4(lst1.begin(), lst1.end());
 151   EXPECT_EQ(test, s4);
 152   // Constructor from wchar_t pointers
 153   wchar_t t[20];
 154   t[0] = 'a';
 155   t[1] = 'b';
 156   fbstring s5(t, t + 2);;
 157   EXPECT_EQ("ab", s5);
 158 }
 159 template <class String> void clause11_21_4_2_i(String & test) {
 160   // From initializer_list<char>
 161   std::initializer_list<typename String::value_type>
 162     il = { 'h', 'e', 'l', 'l', 'o' };
 163   String s(il);
 164   test.swap(s);
 165 }
 166 template <class String> void clause11_21_4_2_j(String & test) {
 167   // Assignment from const String&
 168   auto size = random(0, 2000);
 169   String s(size, '\0');
 170   EXPECT_EQ(s.size(), size);
 171   FOR_EACH_RANGE (i, 0, s.size()) {
 172     s[i] = random('a', 'z');
 173   }
 174   test = s;
 175 }
 176 template <class String> void clause11_21_4_2_k(String & test) {
 177   // Assignment from String&&
 178   auto size = random(0, 2000);
 179   String s(size, '\0');
 180   EXPECT_EQ(s.size(), size);
 181   FOR_EACH_RANGE (i, 0, s.size()) {
 182     s[i] = random('a', 'z');
 183   }
 184   test = std::move(s);
 185   if (typeid(String) == typeid(fbstring)) {
 186     EXPECT_LE(s.size(), 128);
 187   }
 188 }
 189 template <class String> void clause11_21_4_2_l(String & test) {
 190   // Assignment from char*
 191   String s(random(0, 1000), '\0');
 192   size_t i = 0;
 193   for (; i != s.size(); ++i) {
 194     s[i] = random('a', 'z');
 195   }
 196   test = s.c_str();
 197 }
 198 template <class String> void clause11_21_4_2_lprime(String & test) {
 199   // Aliased assign
 200   const size_t pos = random(0, test.size());
 201   if (avoidAliasing) {
 202     test = String(test.c_str() + pos);
 203   } else {
 204     test = test.c_str() + pos;
 205   }
 206 }
 207 template <class String> void clause11_21_4_2_m(String & test) {
 208   // Assignment from char
 209   test = random('a', 'z');
 210 }
 211 template <class String> void clause11_21_4_2_n(String & test) {
 212   // Assignment from initializer_list<char>
 213   initializer_list<typename String::value_type>
 214     il = { 'h', 'e', 'l', 'l', 'o' };
 215   test = il;
 216 }
 217
 218 template <class String> void clause11_21_4_3(String & test) {
 219   // Iterators. The code below should leave test unchanged
 220   EXPECT_EQ(test.size(), test.end() - test.begin());
 221   EXPECT_EQ(test.size(), test.rend() - test.rbegin());
 222   EXPECT_EQ(test.size(), test.cend() - test.cbegin());
 223   EXPECT_EQ(test.size(), test.crend() - test.crbegin());
 224
 225   auto s = test.size();
 226   test.resize(test.end() - test.begin());
 227   EXPECT_EQ(s, test.size());
 228   test.resize(test.rend() - test.rbegin());
 229   EXPECT_EQ(s, test.size());
 230 }
 231
 232 template <class String> void clause11_21_4_4(String & test) {
 233   // exercise capacity, size, max_size
 234   EXPECT_EQ(test.size(), test.length());
 235   EXPECT_LE(test.size(), test.max_size());
 236   EXPECT_LE(test.capacity(), test.max_size());
 237   EXPECT_LE(test.size(), test.capacity());
 238
 239   // exercise shrink_to_fit. Nonbinding request so we can't really do
 240   // much beyond calling it.
 241   auto copy = test;
 242   copy.reserve(copy.capacity() * 3);
 243   copy.shrink_to_fit();
 244   EXPECT_EQ(copy, test);
 245
 246   // exercise empty
 247   string empty("empty");
 248   string notempty("not empty");
 249   if (test.empty()) test = String(empty.begin(), empty.end());
 250   else test = String(notempty.begin(), notempty.end());
 251 }
 252
 253 template <class String> void clause11_21_4_5(String & test) {
 254   // exercise element access
 255   if (!test.empty()) {
 256     EXPECT_EQ(test[0], test.front());
 257     EXPECT_EQ(test[test.size() - 1], test.back());
 258     auto const i = random(0, test.size() - 1);
 259     EXPECT_EQ(test[i], test.at(i));
 260     test = test[i];
 261   }
 262 }
 263
 264 template <class String> void clause11_21_4_6_1(String & test) {
 265   // 21.3.5 modifiers (+=)
 266   String test1;
 267   randomString(&test1);
 268   assert(test1.size() == char_traits
 269       <typename String::value_type>::length(test1.c_str()));
 270   auto len = test.size();
 271   test += test1;
 272   EXPECT_EQ(test.size(), test1.size() + len);
 273   FOR_EACH_RANGE (i, 0, test1.size()) {
 274     EXPECT_EQ(test[len + i], test1[i]);
 275   }
 276   // aliasing modifiers
 277   String test2 = test;
 278   auto dt = test2.data();
 279   auto sz = test.c_str();
 280   len = test.size();
 281   EXPECT_EQ(memcmp(sz, dt, len), 0);
 282   String copy(test.data(), test.size());
 283   EXPECT_EQ(char_traits
 284       <typename String::value_type>::length(test.c_str()), len);
 285   test += test;
 286   //test.append(test);
 287   EXPECT_EQ(test.size(), 2 * len);
 288   EXPECT_EQ(char_traits
 289       <typename String::value_type>::length(test.c_str()), 2 * len);
 290   FOR_EACH_RANGE (i, 0, len) {
 291     EXPECT_EQ(test[i], copy[i]);
 292     EXPECT_EQ(test[i], test[len + i]);
 293   }
 294   len = test.size();
 295   EXPECT_EQ(char_traits
 296       <typename String::value_type>::length(test.c_str()), len);
 297   // more aliasing
 298   auto const pos = random(0, test.size());
 299   EXPECT_EQ(char_traits
 300       <typename String::value_type>::length(test.c_str() + pos), len - pos);
 301   if (avoidAliasing) {
 302     String addMe(test.c_str() + pos);
 303     EXPECT_EQ(addMe.size(), len - pos);
 304     test += addMe;
 305   } else {
 306     test += test.c_str() + pos;
 307   }
 308   EXPECT_EQ(test.size(), 2 * len - pos);
 309   // single char
 310   len = test.size();
 311   test += random('a', 'z');
 312   EXPECT_EQ(test.size(), len + 1);
 313   // initializer_list
 314   initializer_list<typename String::value_type> il { 'a', 'b', 'c' };
 315   test += il;
 316 }
 317
 318 template <class String> void clause11_21_4_6_2(String & test) {
 319   // 21.3.5 modifiers (append, push_back)
 320   String s;
 321
 322   // Test with a small string first
 323   char c = random('a', 'z');
 324   s.push_back(c);
 325   EXPECT_EQ(s[s.size() - 1], c);
 326   EXPECT_EQ(s.size(), 1);
 327   s.resize(s.size() - 1);
 328
 329   randomString(&s, maxString);
 330   test.append(s);
 331   randomString(&s, maxString);
 332   test.append(s, random(0, s.size()), random(0, maxString));
 333   randomString(&s, maxString);
 334   test.append(s.c_str(), random(0, s.size()));
 335   randomString(&s, maxString);
 336   test.append(s.c_str());
 337   test.append(random(0, maxString), random('a', 'z'));
 338   std::list<char> lst(RandomList(maxString));
 339   test.append(lst.begin(), lst.end());
 340   c = random('a', 'z');
 341   test.push_back(c);
 342   EXPECT_EQ(test[test.size() - 1], c);
 343   // initializer_list
 344   initializer_list<typename String::value_type> il { 'a', 'b', 'c' };
 345   test.append(il);
 346 }
 347
 348 template <class String> void clause11_21_4_6_3_a(String & test) {
 349   // assign
 350   String s;
 351   randomString(&s);
 352   test.assign(s);
 353   EXPECT_EQ(test, s);
 354   // move assign
 355   test.assign(std::move(s));
 356   if (typeid(String) == typeid(fbstring)) {
 357     EXPECT_LE(s.size(), 128);
 358   }
 359 }
 360
 361 template <class String> void clause11_21_4_6_3_b(String & test) {
 362   // assign
 363   String s;
 364   randomString(&s, maxString);
 365   test.assign(s, random(0, s.size()), random(0, maxString));
 366 }
 367
 368 template <class String> void clause11_21_4_6_3_c(String & test) {
 369   // assign
 370   String s;
 371   randomString(&s, maxString);
 372   test.assign(s.c_str(), random(0, s.size()));
 373 }
 374
 375 template <class String> void clause11_21_4_6_3_d(String & test) {
 376   // assign
 377   String s;
 378   randomString(&s, maxString);
 379   test.assign(s.c_str());
 380 }
 381
 382 template <class String> void clause11_21_4_6_3_e(String & test) {
 383   // assign
 384   String s;
 385   randomString(&s, maxString);
 386   test.assign(random(0, maxString), random('a', 'z'));
 387 }
 388
 389 template <class String> void clause11_21_4_6_3_f(String & test) {
 390   // assign from bidirectional iterator
 391   std::list<char> lst(RandomList(maxString));
 392   test.assign(lst.begin(), lst.end());
 393 }
 394
 395 template <class String> void clause11_21_4_6_3_g(String & test) {
 396   // assign from aliased source
 397   test.assign(test);
 398 }
 399
 400 template <class String> void clause11_21_4_6_3_h(String & test) {
 401   // assign from aliased source
 402   test.assign(test, random(0, test.size()), random(0, maxString));
 403 }
 404
 405 template <class String> void clause11_21_4_6_3_i(String & test) {
 406   // assign from aliased source
 407   test.assign(test.c_str(), random(0, test.size()));
 408 }
 409
 410 template <class String> void clause11_21_4_6_3_j(String & test) {
 411   // assign from aliased source
 412   test.assign(test.c_str());
 413 }
 414
 415 template <class String> void clause11_21_4_6_3_k(String & test) {
 416   // assign from initializer_list
 417   initializer_list<typename String::value_type> il { 'a', 'b', 'c' };
 418   test.assign(il);
 419 }
 420
 421 template <class String> void clause11_21_4_6_4(String & test) {
 422   // insert
 423   String s;
 424   randomString(&s, maxString);
 425   test.insert(random(0, test.size()), s);
 426   randomString(&s, maxString);
 427   test.insert(random(0, test.size()),
 428               s, random(0, s.size()),
 429               random(0, maxString));
 430   randomString(&s, maxString);
 431   test.insert(random(0, test.size()),
 432               s.c_str(), random(0, s.size()));
 433   randomString(&s, maxString);
 434   test.insert(random(0, test.size()), s.c_str());
 435   test.insert(random(0, test.size()),
 436               random(0, maxString), random('a', 'z'));
 437   typename String::size_type pos = random(0, test.size());
 438   typename String::iterator res =
 439     test.insert(test.begin() + pos, random('a', 'z'));
 440   EXPECT_EQ(res - test.begin(), pos);
 441   std::list<char> lst(RandomList(maxString));
 442   pos = random(0, test.size());
 443   // Uncomment below to see a bug in gcc
 444   /*res = */test.insert(test.begin() + pos, lst.begin(), lst.end());
 445   // insert from initializer_list
 446   initializer_list<typename String::value_type> il { 'a', 'b', 'c' };
 447   pos = random(0, test.size());
 448   // Uncomment below to see a bug in gcc
 449   /*res = */test.insert(test.begin() + pos, il);
 450 }
 451
 452 template <class String> void clause11_21_4_6_5(String & test) {
 453   // erase and pop_back
 454   if (!test.empty()) {
 455     test.erase(random(0, test.size()), random(0, maxString));
 456   }
 457   if (!test.empty()) {
 458     // TODO: is erase(end()) allowed?
 459     test.erase(test.begin() + random(0, test.size() - 1));
 460   }
 461   if (!test.empty()) {
 462     auto const i = test.begin() + random(0, test.size());
 463     if (i != test.end()) {
 464       test.erase(i, i + random(0, size_t(test.end() - i)));
 465     }
 466   }
 467   if (!test.empty()) {
 468     // Can't test pop_back with std::string, doesn't support it yet.
 469     //test.pop_back();
 470   }
 471 }
 472
 473 template <class String> void clause11_21_4_6_6(String & test) {
 474   auto pos = random(0, test.size());
 475   if (avoidAliasing) {
 476     test.replace(pos, random(0, test.size() - pos),
 477                  String(test));
 478   } else {
 479     test.replace(pos, random(0, test.size() - pos), test);
 480   }
 481   pos = random(0, test.size());
 482   String s;
 483   randomString(&s, maxString);
 484   test.replace(pos, pos + random(0, test.size() - pos), s);
 485   auto pos1 = random(0, test.size());
 486   auto pos2 = random(0, test.size());
 487   if (avoidAliasing) {
 488     test.replace(pos1, pos1 + random(0, test.size() - pos1),
 489                  String(test),
 490                  pos2, pos2 + random(0, test.size() - pos2));
 491   } else {
 492     test.replace(pos1, pos1 + random(0, test.size() - pos1),
 493                  test, pos2, pos2 + random(0, test.size() - pos2));
 494   }
 495   pos1 = random(0, test.size());
 496   String str;
 497   randomString(&str, maxString);
 498   pos2 = random(0, str.size());
 499   test.replace(pos1, pos1 + random(0, test.size() - pos1),
 500                str, pos2, pos2 + random(0, str.size() - pos2));
 501   pos = random(0, test.size());
 502   if (avoidAliasing) {
 503     test.replace(pos, random(0, test.size() - pos),
 504                  String(test).c_str(), test.size());
 505   } else {
 506     test.replace(pos, random(0, test.size() - pos),
 507                  test.c_str(), test.size());
 508   }
 509   pos = random(0, test.size());
 510   randomString(&str, maxString);
 511   test.replace(pos, pos + random(0, test.size() - pos),
 512                str.c_str(), str.size());
 513   pos = random(0, test.size());
 514   randomString(&str, maxString);
 515   test.replace(pos, pos + random(0, test.size() - pos),
 516                str.c_str());
 517   pos = random(0, test.size());
 518   test.replace(pos, random(0, test.size() - pos),
 519                random(0, maxString), random('a', 'z'));
 520   pos = random(0, test.size());
 521   if (avoidAliasing) {
 522     test.replace(
 523       test.begin() + pos,
 524       test.begin() + pos + random(0, test.size() - pos),
 525       String(test));
 526   } else {
 527     test.replace(
 528       test.begin() + pos,
 529       test.begin() + pos + random(0, test.size() - pos),
 530       test);
 531   }
 532   pos = random(0, test.size());
 533   if (avoidAliasing) {
 534     test.replace(
 535       test.begin() + pos,
 536       test.begin() + pos + random(0, test.size() - pos),
 537       String(test).c_str(),
 538       test.size() - random(0, test.size()));
 539   } else {
 540     test.replace(
 541       test.begin() + pos,
 542       test.begin() + pos + random(0, test.size() - pos),
 543       test.c_str(),
 544       test.size() - random(0, test.size()));
 545   }
 546   pos = random(0, test.size());
 547   auto const n = random(0, test.size() - pos);
 548   typename String::iterator b = test.begin();
 549   String str1;
 550   randomString(&str1, maxString);
 551   const String & str3 = str1;
 552   const typename String::value_type* ss = str3.c_str();
 553   test.replace(
 554     b + pos,
 555     b + pos + n,
 556     ss);
 557   pos = random(0, test.size());
 558   test.replace(
 559     test.begin() + pos,
 560     test.begin() + pos + random(0, test.size() - pos),
 561     random(0, maxString), random('a', 'z'));
 562 }
 563
 564 template <class String> void clause11_21_4_6_7(String & test) {
 565   std::vector<typename String::value_type>
 566     vec(random(0, maxString));
 567   test.copy(
 568     &vec[0],
 569     vec.size(),
 570     random(0, test.size()));
 571 }
 572
 573 template <class String> void clause11_21_4_6_8(String & test) {
 574   String s;
 575   randomString(&s, maxString);
 576   s.swap(test);
 577 }
 578
 579 template <class String> void clause11_21_4_7_1(String & test) {
 580   // 21.3.6 string operations
 581   // exercise c_str() and data()
 582   assert(test.c_str() == test.data());
 583   // exercise get_allocator()
 584   String s;
 585   randomString(&s, maxString);
 586   assert(test.get_allocator() == s.get_allocator());
 587 }
 588
 589 template <class String> void clause11_21_4_7_2_a(String & test) {
 590   String str = test.substr(
 591     random(0, test.size()),
 592     random(0, test.size()));
 593   Num2String(test, test.find(str, random(0, test.size())));
 594 }
 595
 596 template <class String> void clause11_21_4_7_2_b(String & test) {
 597   auto from = random(0, test.size());
 598   auto length = random(0, test.size() - from);
 599   String str = test.substr(from, length);
 600   Num2String(test, test.find(str.c_str(),
 601                              random(0, test.size()),
 602                              random(0, str.size())));
 603 }
 604
 605 template <class String> void clause11_21_4_7_2_c(String & test) {
 606   String str = test.substr(
 607     random(0, test.size()),
 608     random(0, test.size()));
 609   Num2String(test, test.find(str.c_str(),
 610                              random(0, test.size())));
 611 }
 612
 613 template <class String> void clause11_21_4_7_2_d(String & test) {
 614   Num2String(test, test.find(
 615                random('a', 'z'),
 616                random(0, test.size())));
 617 }
 618
 619 template <class String> void clause11_21_4_7_3_a(String & test) {
 620   String str = test.substr(
 621     random(0, test.size()),
 622     random(0, test.size()));
 623   Num2String(test, test.rfind(str, random(0, test.size())));
 624 }
 625
 626 template <class String> void clause11_21_4_7_3_b(String & test) {
 627   String str = test.substr(
 628     random(0, test.size()),
 629     random(0, test.size()));
 630   Num2String(test, test.rfind(str.c_str(),
 631                               random(0, test.size()),
 632                               random(0, str.size())));
 633 }
 634
 635 template <class String> void clause11_21_4_7_3_c(String & test) {
 636   String str = test.substr(
 637     random(0, test.size()),
 638     random(0, test.size()));
 639   Num2String(test, test.rfind(str.c_str(),
 640                               random(0, test.size())));
 641 }
 642
 643 template <class String> void clause11_21_4_7_3_d(String & test) {
 644   Num2String(test, test.rfind(
 645                random('a', 'z'),
 646                random(0, test.size())));
 647 }
 648
 649 template <class String> void clause11_21_4_7_4_a(String & test) {
 650   String str;
 651   randomString(&str, maxString);
 652   Num2String(test, test.find_first_of(str,
 653                                       random(0, test.size())));
 654 }
 655
 656 template <class String> void clause11_21_4_7_4_b(String & test) {
 657   String str;
 658   randomString(&str, maxString);
 659   Num2String(test, test.find_first_of(str.c_str(),
 660                                       random(0, test.size()),
 661                                       random(0, str.size())));
 662 }
 663
 664 template <class String> void clause11_21_4_7_4_c(String & test) {
 665   String str;
 666   randomString(&str, maxString);
 667   Num2String(test, test.find_first_of(str.c_str(),
 668                                       random(0, test.size())));
 669 }
 670
 671 template <class String> void clause11_21_4_7_4_d(String & test) {
 672   Num2String(test, test.find_first_of(
 673                random('a', 'z'),
 674                random(0, test.size())));
 675 }
 676
 677 template <class String> void clause11_21_4_7_5_a(String & test) {
 678   String str;
 679   randomString(&str, maxString);
 680   Num2String(test, test.find_last_of(str,
 681                                      random(0, test.size())));
 682 }
 683
 684 template <class String> void clause11_21_4_7_5_b(String & test) {
 685   String str;
 686   randomString(&str, maxString);
 687   Num2String(test, test.find_last_of(str.c_str(),
 688                                      random(0, test.size()),
 689                                      random(0, str.size())));
 690 }
 691
 692 template <class String> void clause11_21_4_7_5_c(String & test) {
 693   String str;
 694   randomString(&str, maxString);
 695   Num2String(test, test.find_last_of(str.c_str(),
 696                                      random(0, test.size())));
 697 }
 698
 699 template <class String> void clause11_21_4_7_5_d(String & test) {
 700   Num2String(test, test.find_last_of(
 701                random('a', 'z'),
 702                random(0, test.size())));
 703 }
 704
 705 template <class String> void clause11_21_4_7_6_a(String & test) {
 706   String str;
 707   randomString(&str, maxString);
 708   Num2String(test, test.find_first_not_of(str,
 709                                           random(0, test.size())));
 710 }
 711
 712 template <class String> void clause11_21_4_7_6_b(String & test) {
 713   String str;
 714   randomString(&str, maxString);
 715   Num2String(test, test.find_first_not_of(str.c_str(),
 716                                           random(0, test.size()),
 717                                           random(0, str.size())));
 718 }
 719
 720 template <class String> void clause11_21_4_7_6_c(String & test) {
 721   String str;
 722   randomString(&str, maxString);
 723   Num2String(test, test.find_first_not_of(str.c_str(),
 724                                           random(0, test.size())));
 725 }
 726
 727 template <class String> void clause11_21_4_7_6_d(String & test) {
 728   Num2String(test, test.find_first_not_of(
 729                random('a', 'z'),
 730                random(0, test.size())));
 731 }
 732
 733 template <class String> void clause11_21_4_7_7_a(String & test) {
 734   String str;
 735   randomString(&str, maxString);
 736   Num2String(test, test.find_last_not_of(str,
 737                                          random(0, test.size())));
 738 }
 739
 740 template <class String> void clause11_21_4_7_7_b(String & test) {
 741   String str;
 742   randomString(&str, maxString);
 743   Num2String(test, test.find_last_not_of(str.c_str(),
 744                                          random(0, test.size()),
 745                                          random(0, str.size())));
 746 }
 747
 748 template <class String> void clause11_21_4_7_7_c(String & test) {
 749   String str;
 750   randomString(&str, maxString);
 751   Num2String(test, test.find_last_not_of(str.c_str(),
 752                                          random(0, test.size())));
 753 }
 754
 755 template <class String> void clause11_21_4_7_7_d(String & test) {
 756   Num2String(test, test.find_last_not_of(
 757                random('a', 'z'),
 758                random(0, test.size())));
 759 }
 760
 761 template <class String> void clause11_21_4_7_8(String & test) {
 762   test = test.substr(random(0, test.size()), random(0, test.size()));
 763 }
 764
 765 template <class String> void clause11_21_4_7_9_a(String & test) {
 766   String s;
 767   randomString(&s, maxString);
 768   int tristate = test.compare(s);
 769   if (tristate > 0) tristate = 1;
 770   else if (tristate < 0) tristate = 2;
 771   Num2String(test, tristate);
 772 }
 773
 774 template <class String> void clause11_21_4_7_9_b(String & test) {
 775   String s;
 776   randomString(&s, maxString);
 777   int tristate = test.compare(
 778     random(0, test.size()),
 779     random(0, test.size()),
 780     s);
 781   if (tristate > 0) tristate = 1;
 782   else if (tristate < 0) tristate = 2;
 783   Num2String(test, tristate);
 784 }
 785
 786 template <class String> void clause11_21_4_7_9_c(String & test) {
 787   String str;
 788   randomString(&str, maxString);
 789   int tristate = test.compare(
 790     random(0, test.size()),
 791     random(0, test.size()),
 792     str,
 793     random(0, str.size()),
 794     random(0, str.size()));
 795   if (tristate > 0) tristate = 1;
 796   else if (tristate < 0) tristate = 2;
 797   Num2String(test, tristate);
 798 }
 799
 800 template <class String> void clause11_21_4_7_9_d(String & test) {
 801   String s;
 802   randomString(&s, maxString);
 803   int tristate = test.compare(s.c_str());
 804   if (tristate > 0) tristate = 1;
 805   else if (tristate < 0) tristate = 2;
 806                 Num2String(test, tristate);
 807 }
 808
 809 template <class String> void clause11_21_4_7_9_e(String & test) {
 810   String str;
 811   randomString(&str, maxString);
 812   int tristate = test.compare(
 813     random(0, test.size()),
 814     random(0, test.size()),
 815     str.c_str(),
 816     random(0, str.size()));
 817   if (tristate > 0) tristate = 1;
 818   else if (tristate < 0) tristate = 2;
 819   Num2String(test, tristate);
 820 }
 821
 822 template <class String> void clause11_21_4_8_1_a(String & test) {
 823   String s1;
 824   randomString(&s1, maxString);
 825   String s2;
 826   randomString(&s2, maxString);
 827   test = s1 + s2;
 828 }
 829
 830 template <class String> void clause11_21_4_8_1_b(String & test) {
 831   String s;
 832   randomString(&s, maxString);
 833   String s1;
 834   randomString(&s1, maxString);
 835   test = s.c_str() + s1;
 836 }
 837
 838 template <class String> void clause11_21_4_8_1_c(String & test) {
 839   String s;
 840   randomString(&s, maxString);
 841   test = typename String::value_type(random('a', 'z')) + s;
 842 }
 843
 844 template <class String> void clause11_21_4_8_1_d(String & test) {
 845   String s;
 846   randomString(&s, maxString);
 847   String s1;
 848   randomString(&s1, maxString);
 849   test = s + s1.c_str();
 850 }
 851
 852 template <class String> void clause11_21_4_8_1_e(String & test) {
 853   String s;
 854   randomString(&s, maxString);
 855   String s1;
 856   randomString(&s1, maxString);
 857   test = s + s1.c_str();
 858 }
 859
 860 template <class String> void clause11_21_4_8_1_f(String & test) {
 861   String s;
 862   randomString(&s, maxString);
 863   test = s + typename String::value_type(random('a', 'z'));
 864 }
 865
 866 // Numbering here is from C++11
 867 template <class String> void clause11_21_4_8_9_a(String & test) {
 868   basic_stringstream<typename String::value_type> stst(test.c_str());
 869   String str;
 870   while (stst) {
 871     stst >> str;
 872     test += str + test;
 873   }
 874 }
 875
 876 TEST(FBString, testAllClauses) {
 877   EXPECT_TRUE(1) << "Starting with seed: " << seed;
 878   std::string r;
 879   std::wstring wr;
 880   folly::fbstring c;
 881   folly::basic_fbstring<wchar_t> wc;
 882 #define TEST_CLAUSE(x)                                              \
 883   do {                                                              \
 884       if (1) {} else EXPECT_TRUE(1) << "Testing clause " << #x;     \
 885       randomString(&r);                                             \
 886       c = r;                                                        \
 887       EXPECT_EQ(c, r);                                              \
 888       wr = std::wstring(r.begin(), r.end());                        \
 889       wc = folly::basic_fbstring<wchar_t>(wr.c_str());              \
 890       auto localSeed = seed + count;                                \
 891       rng = RandomT(localSeed);                                     \
 892       clause11_##x(r);                                                \
 893       rng = RandomT(localSeed);                                     \
 894       clause11_##x(c);                                                \
 895       EXPECT_EQ(r, c)                                               \
 896         << "Lengths: " << r.size() << " vs. " << c.size()           \
 897         << "\nReference: '" << r << "'"                             \
 898         << "\nActual:    '" << c.data()[0] << "'";                  \
 899       rng = RandomT(localSeed);                                     \
 900       clause11_##x(wc);                                               \
 901       int wret = wcslen(wc.c_str());                                \
 902       char mb[wret+1];                                              \
 903       int ret = wcstombs(mb, wc.c_str(), sizeof(mb));               \
 904       if (ret == wret) mb[wret] = '\0';                             \
 905       const char *mc = c.c_str();                                   \
 906       std::string one(mb);                                          \
 907       std::string two(mc);                                          \
 908       EXPECT_EQ(one, two);                                          \
 909     } while (++count % 100 != 0)
 910
 911   int count = 0;
 912   TEST_CLAUSE(21_4_2_a);
 913   TEST_CLAUSE(21_4_2_b);
 914   TEST_CLAUSE(21_4_2_c);
 915   TEST_CLAUSE(21_4_2_d);
 916   TEST_CLAUSE(21_4_2_e);
 917   TEST_CLAUSE(21_4_2_f);
 918   TEST_CLAUSE(21_4_2_g);
 919   TEST_CLAUSE(21_4_2_h);
 920   TEST_CLAUSE(21_4_2_i);
 921   TEST_CLAUSE(21_4_2_j);
 922   TEST_CLAUSE(21_4_2_k);
 923   TEST_CLAUSE(21_4_2_l);
 924   TEST_CLAUSE(21_4_2_lprime);
 925   TEST_CLAUSE(21_4_2_m);
 926   TEST_CLAUSE(21_4_2_n);
 927   TEST_CLAUSE(21_4_3);
 928   TEST_CLAUSE(21_4_4);
 929   TEST_CLAUSE(21_4_5);
 930   TEST_CLAUSE(21_4_6_1);
 931   TEST_CLAUSE(21_4_6_2);
 932   TEST_CLAUSE(21_4_6_3_a);
 933   TEST_CLAUSE(21_4_6_3_b);
 934   TEST_CLAUSE(21_4_6_3_c);
 935   TEST_CLAUSE(21_4_6_3_d);
 936   TEST_CLAUSE(21_4_6_3_e);
 937   TEST_CLAUSE(21_4_6_3_f);
 938   TEST_CLAUSE(21_4_6_3_g);
 939   TEST_CLAUSE(21_4_6_3_h);
 940   TEST_CLAUSE(21_4_6_3_i);
 941   TEST_CLAUSE(21_4_6_3_j);
 942   TEST_CLAUSE(21_4_6_3_k);
 943   TEST_CLAUSE(21_4_6_4);
 944   TEST_CLAUSE(21_4_6_5);
 945   TEST_CLAUSE(21_4_6_6);
 946   TEST_CLAUSE(21_4_6_7);
 947   TEST_CLAUSE(21_4_6_8);
 948   TEST_CLAUSE(21_4_7_1);
 949
 950   TEST_CLAUSE(21_4_7_2_a);
 951   TEST_CLAUSE(21_4_7_2_b);
 952   TEST_CLAUSE(21_4_7_2_c);
 953   TEST_CLAUSE(21_4_7_2_d);
 954   TEST_CLAUSE(21_4_7_3_a);
 955   TEST_CLAUSE(21_4_7_3_b);
 956   TEST_CLAUSE(21_4_7_3_c);
 957   TEST_CLAUSE(21_4_7_3_d);
 958   TEST_CLAUSE(21_4_7_4_a);
 959   TEST_CLAUSE(21_4_7_4_b);
 960   TEST_CLAUSE(21_4_7_4_c);
 961   TEST_CLAUSE(21_4_7_4_d);
 962   TEST_CLAUSE(21_4_7_5_a);
 963   TEST_CLAUSE(21_4_7_5_b);
 964   TEST_CLAUSE(21_4_7_5_c);
 965   TEST_CLAUSE(21_4_7_5_d);
 966   TEST_CLAUSE(21_4_7_6_a);
 967   TEST_CLAUSE(21_4_7_6_b);
 968   TEST_CLAUSE(21_4_7_6_c);
 969   TEST_CLAUSE(21_4_7_6_d);
 970   TEST_CLAUSE(21_4_7_7_a);
 971   TEST_CLAUSE(21_4_7_7_b);
 972   TEST_CLAUSE(21_4_7_7_c);
 973   TEST_CLAUSE(21_4_7_7_d);
 974   TEST_CLAUSE(21_4_7_8);
 975   TEST_CLAUSE(21_4_7_9_a);
 976   TEST_CLAUSE(21_4_7_9_b);
 977   TEST_CLAUSE(21_4_7_9_c);
 978   TEST_CLAUSE(21_4_7_9_d);
 979   TEST_CLAUSE(21_4_7_9_e);
 980   TEST_CLAUSE(21_4_8_1_a);
 981   TEST_CLAUSE(21_4_8_1_b);
 982   TEST_CLAUSE(21_4_8_1_c);
 983   TEST_CLAUSE(21_4_8_1_d);
 984   TEST_CLAUSE(21_4_8_1_e);
 985   TEST_CLAUSE(21_4_8_1_f);
 986   TEST_CLAUSE(21_4_8_9_a);
 987 }
 988
 989 TEST(FBString, testGetline) {
 990   fbstring s1 = "\
 991 Lorem ipsum dolor sit amet, consectetur adipiscing elit. Cras accumsan \n\
 992 elit ut urna consectetur in sagittis mi auctor. Nulla facilisi. In nec \n\
 993 dolor leo, vitae imperdiet neque. Donec ut erat mauris, a faucibus \n\
 994 elit. Integer consectetur gravida augue, sit amet mattis mauris auctor \n\
 995 sed. Morbi congue libero eu nunc sodales adipiscing. In lectus nunc, \n\
 996 vulputate a fringilla at, venenatis quis justo. Proin eu velit \n\
 997 nibh. Maecenas vitae tellus eros. Pellentesque habitant morbi \n\
 998 tristique senectus et netus et malesuada fames ac turpis \n\
 999 egestas. Vivamus faucibus feugiat consequat. Donec fermentum neque sit \n\
1000 amet ligula suscipit porta. Phasellus facilisis felis in purus luctus \n\
1001 quis posuere leo tempor. Nam nunc purus, luctus a pharetra ut, \n\
1002 placerat at dui. Donec imperdiet, diam quis convallis pulvinar, dui \n\
1003 est commodo lorem, ut tincidunt diam nibh et nibh. Maecenas nec velit \n\
1004 massa, ut accumsan magna. Donec imperdiet tempor nisi et \n\
1005 laoreet. Phasellus lectus quam, ultricies ut tincidunt in, dignissim \n\
1006 id eros. Mauris vulputate tortor nec neque pellentesque sagittis quis \n\
1007 sed nisl. In diam lacus, lobortis ut posuere nec, ornare id quam.";
1008   char f[] = "/tmp/fbstring_testing.XXXXXX";
1009   int fd = mkstemp(f);
1010   EXPECT_TRUE(fd > 0);
1011   if (fd > 0) {
1012     close(fd);  // Yeah
1013     std::ofstream out(f);
1014     if (!(out << s1)) {
1015       EXPECT_TRUE(0) << "Couldn't write to temp file.";
1016       return;
1017     }
1018   }
1019   vector<fbstring> v;
1020   boost::split(v, s1, boost::is_any_of("\n"));
1021   {
1022     ifstream input(f);
1023     fbstring line;
1024     FOR_EACH (i, v) {
1025       EXPECT_TRUE(getline(input, line));
1026       EXPECT_EQ(line, *i);
1027     }
1028   }
1029   unlink(f);
1030 }
1031
1032 TEST(FBString, testMoveCtor) {
1033   // Move constructor. Make sure we allocate a large string, so the
1034   // small string optimization doesn't kick in.
1035   auto size = random(100, 2000);
1036   fbstring s(size, 'a');
1037   fbstring test = std::move(s);
1038   EXPECT_TRUE(s.empty());
1039   EXPECT_EQ(size, test.size());
1040 }
1041
1042 TEST(FBString, testMoveAssign) {
1043   // Move constructor. Make sure we allocate a large string, so the
1044   // small string optimization doesn't kick in.
1045   auto size = random(100, 2000);
1046   fbstring s(size, 'a');
1047   fbstring test;
1048   test = std::move(s);
1049   EXPECT_TRUE(s.empty());
1050   EXPECT_EQ(size, test.size());
1051 }
1052
1053 TEST(FBString, testMoveOperatorPlusLhs) {
1054   // Make sure we allocate a large string, so the
1055   // small string optimization doesn't kick in.
1056   auto size1 = random(100, 2000);
1057   auto size2 = random(100, 2000);
1058   fbstring s1(size1, 'a');
1059   fbstring s2(size2, 'b');
1060   fbstring test;
1061   test = std::move(s1) + s2;
1062   EXPECT_TRUE(s1.empty());
1063   EXPECT_EQ(size1 + size2, test.size());
1064 }
1065
1066 TEST(FBString, testMoveOperatorPlusRhs) {
1067   // Make sure we allocate a large string, so the
1068   // small string optimization doesn't kick in.
1069   auto size1 = random(100, 2000);
1070   auto size2 = random(100, 2000);
1071   fbstring s1(size1, 'a');
1072   fbstring s2(size2, 'b');
1073   fbstring test;
1074   test = s1 + std::move(s2);
1075   EXPECT_EQ(size1 + size2, test.size());
1076 }
1077
1078 TEST(FBString, testConstructionFromLiteralZero) {
1079   try {
1080     std::string s(0);
1081     EXPECT_TRUE(false);
1082   } catch (const std::logic_error&) {
1083   } catch (...) {
1084     EXPECT_TRUE(false);
1085   }
1086
1087   try {
1088     fbstring s(0);
1089     EXPECT_TRUE(false);
1090   } catch (const std::logic_error& e) {
1091   } catch (...) {
1092     EXPECT_TRUE(false);
1093   }
1094 }
1095
1096 TEST(FBString, testFixedBugs) {
1097   { // D479397
1098     fbstring str(1337, 'f');
1099     fbstring cp = str;
1100     cp.clear();
1101     cp.c_str();
1102     EXPECT_EQ(str.front(), 'f');
1103   }
1104   { // D481173, --extra-cxxflags=-DFBSTRING_CONSERVATIVE
1105     fbstring str(1337, 'f');
1106     for (int i = 0; i < 2; ++i) {
1107       fbstring cp = str;
1108       cp[1] = 'b';
1109       EXPECT_EQ(cp.c_str()[cp.size()], '\0');
1110       cp.push_back('?');
1111     }
1112   }
1113   { // D580267
1114     {
1115       fbstring str(1337, 'f');
1116       fbstring cp = str;
1117       cp.push_back('f');
1118     }
1119     {
1120       fbstring str(1337, 'f');
1121       fbstring cp = str;
1122       cp += "bb";
1123     }
1124   }
1125   { // D661622
1126     folly::basic_fbstring<wchar_t> s;
1127     EXPECT_EQ(0, s.size());
1128   }
1129   { // D785057
1130     fbstring str(1337, 'f');
1131     std::swap(str, str);
1132     EXPECT_EQ(1337, str.size());
1133   }
1134 }
1135
1136
1137 TEST(FBString, testHash) {
1138   fbstring a;
1139   fbstring b;
1140   a.push_back(0);
1141   a.push_back(1);
1142   b.push_back(0);
1143   b.push_back(2);
1144   std::hash<fbstring> hashfunc;
1145   EXPECT_NE(hashfunc(a), hashfunc(b));
1146 }
1147
1148 TEST(FBString, testFrontBack) {
1149   fbstring str("hello");
1150   EXPECT_EQ(str.front(), 'h');
1151   EXPECT_EQ(str.back(), 'o');
1152   str.front() = 'H';
1153   EXPECT_EQ(str.front(), 'H');
1154   str.back() = 'O';
1155   EXPECT_EQ(str.back(), 'O');
1156   EXPECT_EQ(str, "HellO");
1157 }
1158
1159 int main(int argc, char** argv) {
1160   testing::InitGoogleTest(&argc, argv);
1161   google::ParseCommandLineFlags(&argc, &argv, true);
1162   return RUN_ALL_TESTS();
1163 }