folly/test/FBStringTest.cpp

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