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