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   // Test with actual input iterators
 452   stringstream ss;
 453   ss << "hello cruel world";
 454   auto i = istream_iterator<char>(ss);
 455   test.insert(test.begin(), i, istream_iterator<char>());
 456 }
 457
 458 template <class String> void clause11_21_4_6_5(String & test) {
 459   // erase and pop_back
 460   if (!test.empty()) {
 461     test.erase(random(0, test.size()), random(0, maxString));
 462   }
 463   if (!test.empty()) {
 464     // TODO: is erase(end()) allowed?
 465     test.erase(test.begin() + random(0, test.size() - 1));
 466   }
 467   if (!test.empty()) {
 468     auto const i = test.begin() + random(0, test.size());
 469     if (i != test.end()) {
 470       test.erase(i, i + random(0, size_t(test.end() - i)));
 471     }
 472   }
 473   if (!test.empty()) {
 474     // Can't test pop_back with std::string, doesn't support it yet.
 475     //test.pop_back();
 476   }
 477 }
 478
 479 template <class String> void clause11_21_4_6_6(String & test) {
 480   auto pos = random(0, test.size());
 481   if (avoidAliasing) {
 482     test.replace(pos, random(0, test.size() - pos),
 483                  String(test));
 484   } else {
 485     test.replace(pos, random(0, test.size() - pos), test);
 486   }
 487   pos = random(0, test.size());
 488   String s;
 489   randomString(&s, maxString);
 490   test.replace(pos, pos + random(0, test.size() - pos), s);
 491   auto pos1 = random(0, test.size());
 492   auto pos2 = random(0, test.size());
 493   if (avoidAliasing) {
 494     test.replace(pos1, pos1 + random(0, test.size() - pos1),
 495                  String(test),
 496                  pos2, pos2 + random(0, test.size() - pos2));
 497   } else {
 498     test.replace(pos1, pos1 + random(0, test.size() - pos1),
 499                  test, pos2, pos2 + random(0, test.size() - pos2));
 500   }
 501   pos1 = random(0, test.size());
 502   String str;
 503   randomString(&str, maxString);
 504   pos2 = random(0, str.size());
 505   test.replace(pos1, pos1 + random(0, test.size() - pos1),
 506                str, pos2, pos2 + random(0, str.size() - pos2));
 507   pos = random(0, test.size());
 508   if (avoidAliasing) {
 509     test.replace(pos, random(0, test.size() - pos),
 510                  String(test).c_str(), test.size());
 511   } else {
 512     test.replace(pos, random(0, test.size() - pos),
 513                  test.c_str(), test.size());
 514   }
 515   pos = random(0, test.size());
 516   randomString(&str, maxString);
 517   test.replace(pos, pos + random(0, test.size() - pos),
 518                str.c_str(), str.size());
 519   pos = random(0, test.size());
 520   randomString(&str, maxString);
 521   test.replace(pos, pos + random(0, test.size() - pos),
 522                str.c_str());
 523   pos = random(0, test.size());
 524   test.replace(pos, random(0, test.size() - pos),
 525                random(0, maxString), random('a', 'z'));
 526   pos = random(0, test.size());
 527   if (avoidAliasing) {
 528     test.replace(
 529       test.begin() + pos,
 530       test.begin() + pos + random(0, test.size() - pos),
 531       String(test));
 532   } else {
 533     test.replace(
 534       test.begin() + pos,
 535       test.begin() + pos + random(0, test.size() - pos),
 536       test);
 537   }
 538   pos = random(0, test.size());
 539   if (avoidAliasing) {
 540     test.replace(
 541       test.begin() + pos,
 542       test.begin() + pos + random(0, test.size() - pos),
 543       String(test).c_str(),
 544       test.size() - random(0, test.size()));
 545   } else {
 546     test.replace(
 547       test.begin() + pos,
 548       test.begin() + pos + random(0, test.size() - pos),
 549       test.c_str(),
 550       test.size() - random(0, test.size()));
 551   }
 552   pos = random(0, test.size());
 553   auto const n = random(0, test.size() - pos);
 554   typename String::iterator b = test.begin();
 555   String str1;
 556   randomString(&str1, maxString);
 557   const String & str3 = str1;
 558   const typename String::value_type* ss = str3.c_str();
 559   test.replace(
 560     b + pos,
 561     b + pos + n,
 562     ss);
 563   pos = random(0, test.size());
 564   test.replace(
 565     test.begin() + pos,
 566     test.begin() + pos + random(0, test.size() - pos),
 567     random(0, maxString), random('a', 'z'));
 568 }
 569
 570 template <class String> void clause11_21_4_6_7(String & test) {
 571   std::vector<typename String::value_type>
 572     vec(random(0, maxString));
 573   test.copy(
 574     &vec[0],
 575     vec.size(),
 576     random(0, test.size()));
 577 }
 578
 579 template <class String> void clause11_21_4_6_8(String & test) {
 580   String s;
 581   randomString(&s, maxString);
 582   s.swap(test);
 583 }
 584
 585 template <class String> void clause11_21_4_7_1(String & test) {
 586   // 21.3.6 string operations
 587   // exercise c_str() and data()
 588   assert(test.c_str() == test.data());
 589   // exercise get_allocator()
 590   String s;
 591   randomString(&s, maxString);
 592   assert(test.get_allocator() == s.get_allocator());
 593 }
 594
 595 template <class String> void clause11_21_4_7_2_a(String & test) {
 596   String str = test.substr(
 597     random(0, test.size()),
 598     random(0, test.size()));
 599   Num2String(test, test.find(str, random(0, test.size())));
 600 }
 601
 602 template <class String> void clause11_21_4_7_2_b(String & test) {
 603   auto from = random(0, test.size());
 604   auto length = random(0, test.size() - from);
 605   String str = test.substr(from, length);
 606   Num2String(test, test.find(str.c_str(),
 607                              random(0, test.size()),
 608                              random(0, str.size())));
 609 }
 610
 611 template <class String> void clause11_21_4_7_2_c(String & test) {
 612   String str = test.substr(
 613     random(0, test.size()),
 614     random(0, test.size()));
 615   Num2String(test, test.find(str.c_str(),
 616                              random(0, test.size())));
 617 }
 618
 619 template <class String> void clause11_21_4_7_2_d(String & test) {
 620   Num2String(test, test.find(
 621                random('a', 'z'),
 622                random(0, test.size())));
 623 }
 624
 625 template <class String> void clause11_21_4_7_3_a(String & test) {
 626   String str = test.substr(
 627     random(0, test.size()),
 628     random(0, test.size()));
 629   Num2String(test, test.rfind(str, random(0, test.size())));
 630 }
 631
 632 template <class String> void clause11_21_4_7_3_b(String & test) {
 633   String str = test.substr(
 634     random(0, test.size()),
 635     random(0, test.size()));
 636   Num2String(test, test.rfind(str.c_str(),
 637                               random(0, test.size()),
 638                               random(0, str.size())));
 639 }
 640
 641 template <class String> void clause11_21_4_7_3_c(String & test) {
 642   String str = test.substr(
 643     random(0, test.size()),
 644     random(0, test.size()));
 645   Num2String(test, test.rfind(str.c_str(),
 646                               random(0, test.size())));
 647 }
 648
 649 template <class String> void clause11_21_4_7_3_d(String & test) {
 650   Num2String(test, test.rfind(
 651                random('a', 'z'),
 652                random(0, test.size())));
 653 }
 654
 655 template <class String> void clause11_21_4_7_4_a(String & test) {
 656   String str;
 657   randomString(&str, maxString);
 658   Num2String(test, test.find_first_of(str,
 659                                       random(0, test.size())));
 660 }
 661
 662 template <class String> void clause11_21_4_7_4_b(String & test) {
 663   String str;
 664   randomString(&str, maxString);
 665   Num2String(test, test.find_first_of(str.c_str(),
 666                                       random(0, test.size()),
 667                                       random(0, str.size())));
 668 }
 669
 670 template <class String> void clause11_21_4_7_4_c(String & test) {
 671   String str;
 672   randomString(&str, maxString);
 673   Num2String(test, test.find_first_of(str.c_str(),
 674                                       random(0, test.size())));
 675 }
 676
 677 template <class String> void clause11_21_4_7_4_d(String & test) {
 678   Num2String(test, test.find_first_of(
 679                random('a', 'z'),
 680                random(0, test.size())));
 681 }
 682
 683 template <class String> void clause11_21_4_7_5_a(String & test) {
 684   String str;
 685   randomString(&str, maxString);
 686   Num2String(test, test.find_last_of(str,
 687                                      random(0, test.size())));
 688 }
 689
 690 template <class String> void clause11_21_4_7_5_b(String & test) {
 691   String str;
 692   randomString(&str, maxString);
 693   Num2String(test, test.find_last_of(str.c_str(),
 694                                      random(0, test.size()),
 695                                      random(0, str.size())));
 696 }
 697
 698 template <class String> void clause11_21_4_7_5_c(String & test) {
 699   String str;
 700   randomString(&str, maxString);
 701   Num2String(test, test.find_last_of(str.c_str(),
 702                                      random(0, test.size())));
 703 }
 704
 705 template <class String> void clause11_21_4_7_5_d(String & test) {
 706   Num2String(test, test.find_last_of(
 707                random('a', 'z'),
 708                random(0, test.size())));
 709 }
 710
 711 template <class String> void clause11_21_4_7_6_a(String & test) {
 712   String str;
 713   randomString(&str, maxString);
 714   Num2String(test, test.find_first_not_of(str,
 715                                           random(0, test.size())));
 716 }
 717
 718 template <class String> void clause11_21_4_7_6_b(String & test) {
 719   String str;
 720   randomString(&str, maxString);
 721   Num2String(test, test.find_first_not_of(str.c_str(),
 722                                           random(0, test.size()),
 723                                           random(0, str.size())));
 724 }
 725
 726 template <class String> void clause11_21_4_7_6_c(String & test) {
 727   String str;
 728   randomString(&str, maxString);
 729   Num2String(test, test.find_first_not_of(str.c_str(),
 730                                           random(0, test.size())));
 731 }
 732
 733 template <class String> void clause11_21_4_7_6_d(String & test) {
 734   Num2String(test, test.find_first_not_of(
 735                random('a', 'z'),
 736                random(0, test.size())));
 737 }
 738
 739 template <class String> void clause11_21_4_7_7_a(String & test) {
 740   String str;
 741   randomString(&str, maxString);
 742   Num2String(test, test.find_last_not_of(str,
 743                                          random(0, test.size())));
 744 }
 745
 746 template <class String> void clause11_21_4_7_7_b(String & test) {
 747   String str;
 748   randomString(&str, maxString);
 749   Num2String(test, test.find_last_not_of(str.c_str(),
 750                                          random(0, test.size()),
 751                                          random(0, str.size())));
 752 }
 753
 754 template <class String> void clause11_21_4_7_7_c(String & test) {
 755   String str;
 756   randomString(&str, maxString);
 757   Num2String(test, test.find_last_not_of(str.c_str(),
 758                                          random(0, test.size())));
 759 }
 760
 761 template <class String> void clause11_21_4_7_7_d(String & test) {
 762   Num2String(test, test.find_last_not_of(
 763                random('a', 'z'),
 764                random(0, test.size())));
 765 }
 766
 767 template <class String> void clause11_21_4_7_8(String & test) {
 768   test = test.substr(random(0, test.size()), random(0, test.size()));
 769 }
 770
 771 template <class String> void clause11_21_4_7_9_a(String & test) {
 772   String s;
 773   randomString(&s, maxString);
 774   int tristate = test.compare(s);
 775   if (tristate > 0) tristate = 1;
 776   else if (tristate < 0) tristate = 2;
 777   Num2String(test, tristate);
 778 }
 779
 780 template <class String> void clause11_21_4_7_9_b(String & test) {
 781   String s;
 782   randomString(&s, maxString);
 783   int tristate = test.compare(
 784     random(0, test.size()),
 785     random(0, test.size()),
 786     s);
 787   if (tristate > 0) tristate = 1;
 788   else if (tristate < 0) tristate = 2;
 789   Num2String(test, tristate);
 790 }
 791
 792 template <class String> void clause11_21_4_7_9_c(String & test) {
 793   String str;
 794   randomString(&str, maxString);
 795   int tristate = test.compare(
 796     random(0, test.size()),
 797     random(0, test.size()),
 798     str,
 799     random(0, str.size()),
 800     random(0, str.size()));
 801   if (tristate > 0) tristate = 1;
 802   else if (tristate < 0) tristate = 2;
 803   Num2String(test, tristate);
 804 }
 805
 806 template <class String> void clause11_21_4_7_9_d(String & test) {
 807   String s;
 808   randomString(&s, maxString);
 809   int tristate = test.compare(s.c_str());
 810   if (tristate > 0) tristate = 1;
 811   else if (tristate < 0) tristate = 2;
 812                 Num2String(test, tristate);
 813 }
 814
 815 template <class String> void clause11_21_4_7_9_e(String & test) {
 816   String str;
 817   randomString(&str, maxString);
 818   int tristate = test.compare(
 819     random(0, test.size()),
 820     random(0, test.size()),
 821     str.c_str(),
 822     random(0, str.size()));
 823   if (tristate > 0) tristate = 1;
 824   else if (tristate < 0) tristate = 2;
 825   Num2String(test, tristate);
 826 }
 827
 828 template <class String> void clause11_21_4_8_1_a(String & test) {
 829   String s1;
 830   randomString(&s1, maxString);
 831   String s2;
 832   randomString(&s2, maxString);
 833   test = s1 + s2;
 834 }
 835
 836 template <class String> void clause11_21_4_8_1_b(String & test) {
 837   String s;
 838   randomString(&s, maxString);
 839   String s1;
 840   randomString(&s1, maxString);
 841   test = s.c_str() + s1;
 842 }
 843
 844 template <class String> void clause11_21_4_8_1_c(String & test) {
 845   String s;
 846   randomString(&s, maxString);
 847   test = typename String::value_type(random('a', 'z')) + s;
 848 }
 849
 850 template <class String> void clause11_21_4_8_1_d(String & test) {
 851   String s;
 852   randomString(&s, maxString);
 853   String s1;
 854   randomString(&s1, maxString);
 855   test = s + s1.c_str();
 856 }
 857
 858 template <class String> void clause11_21_4_8_1_e(String & test) {
 859   String s;
 860   randomString(&s, maxString);
 861   String s1;
 862   randomString(&s1, maxString);
 863   test = s + s1.c_str();
 864 }
 865
 866 template <class String> void clause11_21_4_8_1_f(String & test) {
 867   String s;
 868   randomString(&s, maxString);
 869   test = s + typename String::value_type(random('a', 'z'));
 870 }
 871
 872 // Numbering here is from C++11
 873 template <class String> void clause11_21_4_8_9_a(String & test) {
 874   basic_stringstream<typename String::value_type> stst(test.c_str());
 875   String str;
 876   while (stst) {
 877     stst >> str;
 878     test += str + test;
 879   }
 880 }
 881
 882 TEST(FBString, testAllClauses) {
 883   EXPECT_TRUE(1) << "Starting with seed: " << seed;
 884   std::string r;
 885   std::wstring wr;
 886   folly::fbstring c;
 887   folly::basic_fbstring<wchar_t> wc;
 888 #define TEST_CLAUSE(x)                                              \
 889   do {                                                              \
 890       if (1) {} else EXPECT_TRUE(1) << "Testing clause " << #x;     \
 891       randomString(&r);                                             \
 892       c = r;                                                        \
 893       EXPECT_EQ(c, r);                                              \
 894       wr = std::wstring(r.begin(), r.end());                        \
 895       wc = folly::basic_fbstring<wchar_t>(wr.c_str());              \
 896       auto localSeed = seed + count;                                \
 897       rng = RandomT(localSeed);                                     \
 898       clause11_##x(r);                                                \
 899       rng = RandomT(localSeed);                                     \
 900       clause11_##x(c);                                                \
 901       EXPECT_EQ(r, c)                                               \
 902         << "Lengths: " << r.size() << " vs. " << c.size()           \
 903         << "\nReference: '" << r << "'"                             \
 904         << "\nActual:    '" << c.data()[0] << "'";                  \
 905       rng = RandomT(localSeed);                                     \
 906       clause11_##x(wc);                                               \
 907       int wret = wcslen(wc.c_str());                                \
 908       char mb[wret+1];                                              \
 909       int ret = wcstombs(mb, wc.c_str(), sizeof(mb));               \
 910       if (ret == wret) mb[wret] = '\0';                             \
 911       const char *mc = c.c_str();                                   \
 912       std::string one(mb);                                          \
 913       std::string two(mc);                                          \
 914       EXPECT_EQ(one, two);                                          \
 915     } while (++count % 100 != 0)
 916
 917   int count = 0;
 918   TEST_CLAUSE(21_4_2_a);
 919   TEST_CLAUSE(21_4_2_b);
 920   TEST_CLAUSE(21_4_2_c);
 921   TEST_CLAUSE(21_4_2_d);
 922   TEST_CLAUSE(21_4_2_e);
 923   TEST_CLAUSE(21_4_2_f);
 924   TEST_CLAUSE(21_4_2_g);
 925   TEST_CLAUSE(21_4_2_h);
 926   TEST_CLAUSE(21_4_2_i);
 927   TEST_CLAUSE(21_4_2_j);
 928   TEST_CLAUSE(21_4_2_k);
 929   TEST_CLAUSE(21_4_2_l);
 930   TEST_CLAUSE(21_4_2_lprime);
 931   TEST_CLAUSE(21_4_2_m);
 932   TEST_CLAUSE(21_4_2_n);
 933   TEST_CLAUSE(21_4_3);
 934   TEST_CLAUSE(21_4_4);
 935   TEST_CLAUSE(21_4_5);
 936   TEST_CLAUSE(21_4_6_1);
 937   TEST_CLAUSE(21_4_6_2);
 938   TEST_CLAUSE(21_4_6_3_a);
 939   TEST_CLAUSE(21_4_6_3_b);
 940   TEST_CLAUSE(21_4_6_3_c);
 941   TEST_CLAUSE(21_4_6_3_d);
 942   TEST_CLAUSE(21_4_6_3_e);
 943   TEST_CLAUSE(21_4_6_3_f);
 944   TEST_CLAUSE(21_4_6_3_g);
 945   TEST_CLAUSE(21_4_6_3_h);
 946   TEST_CLAUSE(21_4_6_3_i);
 947   TEST_CLAUSE(21_4_6_3_j);
 948   TEST_CLAUSE(21_4_6_3_k);
 949   TEST_CLAUSE(21_4_6_4);
 950   TEST_CLAUSE(21_4_6_5);
 951   TEST_CLAUSE(21_4_6_6);
 952   TEST_CLAUSE(21_4_6_7);
 953   TEST_CLAUSE(21_4_6_8);
 954   TEST_CLAUSE(21_4_7_1);
 955
 956   TEST_CLAUSE(21_4_7_2_a);
 957   TEST_CLAUSE(21_4_7_2_b);
 958   TEST_CLAUSE(21_4_7_2_c);
 959   TEST_CLAUSE(21_4_7_2_d);
 960   TEST_CLAUSE(21_4_7_3_a);
 961   TEST_CLAUSE(21_4_7_3_b);
 962   TEST_CLAUSE(21_4_7_3_c);
 963   TEST_CLAUSE(21_4_7_3_d);
 964   TEST_CLAUSE(21_4_7_4_a);
 965   TEST_CLAUSE(21_4_7_4_b);
 966   TEST_CLAUSE(21_4_7_4_c);
 967   TEST_CLAUSE(21_4_7_4_d);
 968   TEST_CLAUSE(21_4_7_5_a);
 969   TEST_CLAUSE(21_4_7_5_b);
 970   TEST_CLAUSE(21_4_7_5_c);
 971   TEST_CLAUSE(21_4_7_5_d);
 972   TEST_CLAUSE(21_4_7_6_a);
 973   TEST_CLAUSE(21_4_7_6_b);
 974   TEST_CLAUSE(21_4_7_6_c);
 975   TEST_CLAUSE(21_4_7_6_d);
 976   TEST_CLAUSE(21_4_7_7_a);
 977   TEST_CLAUSE(21_4_7_7_b);
 978   TEST_CLAUSE(21_4_7_7_c);
 979   TEST_CLAUSE(21_4_7_7_d);
 980   TEST_CLAUSE(21_4_7_8);
 981   TEST_CLAUSE(21_4_7_9_a);
 982   TEST_CLAUSE(21_4_7_9_b);
 983   TEST_CLAUSE(21_4_7_9_c);
 984   TEST_CLAUSE(21_4_7_9_d);
 985   TEST_CLAUSE(21_4_7_9_e);
 986   TEST_CLAUSE(21_4_8_1_a);
 987   TEST_CLAUSE(21_4_8_1_b);
 988   TEST_CLAUSE(21_4_8_1_c);
 989   TEST_CLAUSE(21_4_8_1_d);
 990   TEST_CLAUSE(21_4_8_1_e);
 991   TEST_CLAUSE(21_4_8_1_f);
 992   TEST_CLAUSE(21_4_8_9_a);
 993 }
 994
 995 TEST(FBString, testGetline) {
 996   fbstring s1 = "\
 997 Lorem ipsum dolor sit amet, consectetur adipiscing elit. Cras accumsan \n\
 998 elit ut urna consectetur in sagittis mi auctor. Nulla facilisi. In nec \n\
 999 dolor leo, vitae imperdiet neque. Donec ut erat mauris, a faucibus \n\
1000 elit. Integer consectetur gravida augue, sit amet mattis mauris auctor \n\
1001 sed. Morbi congue libero eu nunc sodales adipiscing. In lectus nunc, \n\
1002 vulputate a fringilla at, venenatis quis justo. Proin eu velit \n\
1003 nibh. Maecenas vitae tellus eros. Pellentesque habitant morbi \n\
1004 tristique senectus et netus et malesuada fames ac turpis \n\
1005 egestas. Vivamus faucibus feugiat consequat. Donec fermentum neque sit \n\
1006 amet ligula suscipit porta. Phasellus facilisis felis in purus luctus \n\
1007 quis posuere leo tempor. Nam nunc purus, luctus a pharetra ut, \n\
1008 placerat at dui. Donec imperdiet, diam quis convallis pulvinar, dui \n\
1009 est commodo lorem, ut tincidunt diam nibh et nibh. Maecenas nec velit \n\
1010 massa, ut accumsan magna. Donec imperdiet tempor nisi et \n\
1011 laoreet. Phasellus lectus quam, ultricies ut tincidunt in, dignissim \n\
1012 id eros. Mauris vulputate tortor nec neque pellentesque sagittis quis \n\
1013 sed nisl. In diam lacus, lobortis ut posuere nec, ornare id quam.";
1014   char f[] = "/tmp/fbstring_testing.XXXXXX";
1015   int fd = mkstemp(f);
1016   EXPECT_TRUE(fd > 0);
1017   if (fd > 0) {
1018     close(fd);  // Yeah
1019     std::ofstream out(f);
1020     if (!(out << s1)) {
1021       EXPECT_TRUE(0) << "Couldn't write to temp file.";
1022       return;
1023     }
1024   }
1025   vector<fbstring> v;
1026   boost::split(v, s1, boost::is_any_of("\n"));
1027   {
1028     ifstream input(f);
1029     fbstring line;
1030     FOR_EACH (i, v) {
1031       EXPECT_TRUE(getline(input, line));
1032       EXPECT_EQ(line, *i);
1033     }
1034   }
1035   unlink(f);
1036 }
1037
1038 TEST(FBString, testMoveCtor) {
1039   // Move constructor. Make sure we allocate a large string, so the
1040   // small string optimization doesn't kick in.
1041   auto size = random(100, 2000);
1042   fbstring s(size, 'a');
1043   fbstring test = std::move(s);
1044   EXPECT_TRUE(s.empty());
1045   EXPECT_EQ(size, test.size());
1046 }
1047
1048 TEST(FBString, testMoveAssign) {
1049   // Move constructor. Make sure we allocate a large string, so the
1050   // small string optimization doesn't kick in.
1051   auto size = random(100, 2000);
1052   fbstring s(size, 'a');
1053   fbstring test;
1054   test = std::move(s);
1055   EXPECT_TRUE(s.empty());
1056   EXPECT_EQ(size, test.size());
1057 }
1058
1059 TEST(FBString, testMoveOperatorPlusLhs) {
1060   // Make sure we allocate a large string, so the
1061   // small string optimization doesn't kick in.
1062   auto size1 = random(100, 2000);
1063   auto size2 = random(100, 2000);
1064   fbstring s1(size1, 'a');
1065   fbstring s2(size2, 'b');
1066   fbstring test;
1067   test = std::move(s1) + s2;
1068   EXPECT_TRUE(s1.empty());
1069   EXPECT_EQ(size1 + size2, test.size());
1070 }
1071
1072 TEST(FBString, testMoveOperatorPlusRhs) {
1073   // Make sure we allocate a large string, so the
1074   // small string optimization doesn't kick in.
1075   auto size1 = random(100, 2000);
1076   auto size2 = random(100, 2000);
1077   fbstring s1(size1, 'a');
1078   fbstring s2(size2, 'b');
1079   fbstring test;
1080   test = s1 + std::move(s2);
1081   EXPECT_EQ(size1 + size2, test.size());
1082 }
1083
1084 TEST(FBString, testConstructionFromLiteralZero) {
1085   try {
1086     std::string s(0);
1087     EXPECT_TRUE(false);
1088   } catch (const std::logic_error&) {
1089   } catch (...) {
1090     EXPECT_TRUE(false);
1091   }
1092
1093   try {
1094     fbstring s(0);
1095     EXPECT_TRUE(false);
1096   } catch (const std::logic_error& e) {
1097   } catch (...) {
1098     EXPECT_TRUE(false);
1099   }
1100 }
1101
1102 TEST(FBString, testFixedBugs) {
1103   { // D479397
1104     fbstring str(1337, 'f');
1105     fbstring cp = str;
1106     cp.clear();
1107     cp.c_str();
1108     EXPECT_EQ(str.front(), 'f');
1109   }
1110   { // D481173, --extra-cxxflags=-DFBSTRING_CONSERVATIVE
1111     fbstring str(1337, 'f');
1112     for (int i = 0; i < 2; ++i) {
1113       fbstring cp = str;
1114       cp[1] = 'b';
1115       EXPECT_EQ(cp.c_str()[cp.size()], '\0');
1116       cp.push_back('?');
1117     }
1118   }
1119   { // D580267
1120     {
1121       fbstring str(1337, 'f');
1122       fbstring cp = str;
1123       cp.push_back('f');
1124     }
1125     {
1126       fbstring str(1337, 'f');
1127       fbstring cp = str;
1128       cp += "bb";
1129     }
1130   }
1131   { // D661622
1132     folly::basic_fbstring<wchar_t> s;
1133     EXPECT_EQ(0, s.size());
1134   }
1135   { // D785057
1136     fbstring str(1337, 'f');
1137     std::swap(str, str);
1138     EXPECT_EQ(1337, str.size());
1139   }
1140 }
1141
1142
1143 TEST(FBString, testHash) {
1144   fbstring a;
1145   fbstring b;
1146   a.push_back(0);
1147   a.push_back(1);
1148   b.push_back(0);
1149   b.push_back(2);
1150   std::hash<fbstring> hashfunc;
1151   EXPECT_NE(hashfunc(a), hashfunc(b));
1152 }
1153
1154 TEST(FBString, testFrontBack) {
1155   fbstring str("hello");
1156   EXPECT_EQ(str.front(), 'h');
1157   EXPECT_EQ(str.back(), 'o');
1158   str.front() = 'H';
1159   EXPECT_EQ(str.front(), 'H');
1160   str.back() = 'O';
1161   EXPECT_EQ(str.back(), 'O');
1162   EXPECT_EQ(str, "HellO");
1163 }
1164
1165 int main(int argc, char** argv) {
1166   testing::InitGoogleTest(&argc, argv);
1167   google::ParseCommandLineFlags(&argc, &argv, true);
1168   return RUN_ALL_TESTS();
1169 }