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