folly/FBString.h

   1 /*
   2  * Copyright 2016 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 // @author: Andrei Alexandrescu (aalexandre)
  18 // String type.
  19
  20 #pragma once
  21
  22 #include <atomic>
  23 #include <limits>
  24 #include <type_traits>
  25
  26 // This file appears in two locations: inside fbcode and in the
  27 // libstdc++ source code (when embedding fbstring as std::string).
  28 // To aid in this schizophrenic use, _LIBSTDCXX_FBSTRING is defined in
  29 // libstdc++'s c++config.h, to gate use inside fbcode v. libstdc++.
  30 #ifdef _LIBSTDCXX_FBSTRING
  31
  32 #pragma GCC system_header
  33
  34 // When used as std::string replacement always disable assertions.
  35 #ifndef NDEBUG
  36 #define NDEBUG
  37 #define FOLLY_DEFINED_NDEBUG_FOR_FBSTRING
  38 #endif // NDEBUG
  39
  40 // Handle the cases where the fbcode version (folly/Malloc.h) is included
  41 // either before or after this inclusion.
  42 #ifdef FOLLY_MALLOC_H_
  43 #undef FOLLY_MALLOC_H_
  44 #include "basic_fbstring_malloc.h" // nolint
  45 #else
  46 #include "basic_fbstring_malloc.h" // nolint
  47 #undef FOLLY_MALLOC_H_
  48 #endif
  49
  50 #else // !_LIBSTDCXX_FBSTRING
  51
  52 #include <folly/Portability.h>
  53
  54 // libc++ doesn't provide this header, nor does msvc
  55 #ifdef FOLLY_HAVE_BITS_CXXCONFIG_H
  56 #include <bits/c++config.h>
  57 #endif
  58
  59 #include <string>
  60 #include <cstring>
  61 #include <cassert>
  62 #include <algorithm>
  63
  64 #include <folly/Traits.h>
  65 #include <folly/Malloc.h>
  66 #include <folly/Hash.h>
  67 #include <folly/ScopeGuard.h>
  68
  69 #if FOLLY_HAVE_DEPRECATED_ASSOC
  70 #ifdef _GLIBCXX_SYMVER
  71 #include <ext/hash_set>
  72 #include <ext/hash_map>
  73 #endif
  74 #endif
  75
  76 #endif
  77
  78 // We defined these here rather than including Likely.h to avoid
  79 // redefinition errors when fbstring is imported into libstdc++.
  80 #if defined(__GNUC__) && __GNUC__ >= 4
  81 #define FBSTRING_LIKELY(x)   (__builtin_expect((x), 1))
  82 #define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
  83 #else
  84 #define FBSTRING_LIKELY(x)   (x)
  85 #define FBSTRING_UNLIKELY(x) (x)
  86 #endif
  87
  88 #pragma GCC diagnostic push
  89 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
  90 #pragma GCC diagnostic ignored "-Wshadow"
  91 // GCC 4.9 has a false positive in setSmallSize (probably
  92 // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59124), disable
  93 // compile-time array bound checking.
  94 #pragma GCC diagnostic ignored "-Warray-bounds"
  95
  96 // FBString cannot use throw when replacing std::string, though it may still
  97 // use std::__throw_*
  98 // nolint
  99 #define throw FOLLY_FBSTRING_MAY_NOT_USE_THROW
 100
 101 #ifdef _LIBSTDCXX_FBSTRING
 102 namespace std _GLIBCXX_VISIBILITY(default) {
 103 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 104 #else
 105 namespace folly {
 106 #endif
 107
 108 #if defined(__clang__)
 109 # if __has_feature(address_sanitizer)
 110 #  define FBSTRING_SANITIZE_ADDRESS
 111 # endif
 112 #elif defined (__GNUC__) && \
 113       (((__GNUC__ == 4) && (__GNUC_MINOR__ >= 8)) || (__GNUC__ >= 5)) && \
 114       __SANITIZE_ADDRESS__
 115 # define FBSTRING_SANITIZE_ADDRESS
 116 #endif
 117
 118 // When compiling with ASan, always heap-allocate the string even if
 119 // it would fit in-situ, so that ASan can detect access to the string
 120 // buffer after it has been invalidated (destroyed, resized, etc.).
 121 // Note that this flag doesn't remove support for in-situ strings, as
 122 // that would break ABI-compatibility and wouldn't allow linking code
 123 // compiled with this flag with code compiled without.
 124 #ifdef FBSTRING_SANITIZE_ADDRESS
 125 # define FBSTRING_DISABLE_SSO true
 126 #else
 127 # define FBSTRING_DISABLE_SSO false
 128 #endif
 129
 130 namespace fbstring_detail {
 131
 132 template <class InIt, class OutIt>
 133 inline
 134 OutIt copy_n(InIt b,
 135              typename std::iterator_traits<InIt>::difference_type n,
 136              OutIt d) {
 137   for (; n != 0; --n, ++b, ++d) {
 138     *d = *b;
 139   }
 140   return d;
 141 }
 142
 143 template <class Pod, class T>
 144 inline void pod_fill(Pod* b, Pod* e, T c) {
 145   assert(b && e && b <= e);
 146   /*static*/ if (sizeof(T) == 1) {
 147     memset(b, c, e - b);
 148   } else {
 149     auto const ee = b + ((e - b) & ~7u);
 150     for (; b != ee; b += 8) {
 151       b[0] = c;
 152       b[1] = c;
 153       b[2] = c;
 154       b[3] = c;
 155       b[4] = c;
 156       b[5] = c;
 157       b[6] = c;
 158       b[7] = c;
 159     }
 160     // Leftovers
 161     for (; b != e; ++b) {
 162       *b = c;
 163     }
 164   }
 165 }
 166
 167 /*
 168  * Lightly structured memcpy, simplifies copying PODs and introduces
 169  * some asserts. Unfortunately using this function may cause
 170  * measurable overhead (presumably because it adjusts from a begin/end
 171  * convention to a pointer/size convention, so it does some extra
 172  * arithmetic even though the caller might have done the inverse
 173  * adaptation outside).
 174  */
 175 template <class Pod>
 176 inline void pod_copy(const Pod* b, const Pod* e, Pod* d) {
 177   assert(e >= b);
 178   assert(d >= e || d + (e - b) <= b);
 179   memcpy(d, b, (e - b) * sizeof(Pod));
 180 }
 181
 182 /*
 183  * Lightly structured memmove, simplifies copying PODs and introduces
 184  * some asserts
 185  */
 186 template <class Pod>
 187 inline void pod_move(const Pod* b, const Pod* e, Pod* d) {
 188   assert(e >= b);
 189   memmove(d, b, (e - b) * sizeof(*b));
 190 }
 191
 192 } // namespace fbstring_detail
 193
 194 /**
 195  * Defines a special acquisition method for constructing fbstring
 196  * objects. AcquireMallocatedString means that the user passes a
 197  * pointer to a malloc-allocated string that the fbstring object will
 198  * take into custody.
 199  */
 200 enum class AcquireMallocatedString {};
 201
 202 /*
 203  * fbstring_core_model is a mock-up type that defines all required
 204  * signatures of a fbstring core. The fbstring class itself uses such
 205  * a core object to implement all of the numerous member functions
 206  * required by the standard.
 207  *
 208  * If you want to define a new core, copy the definition below and
 209  * implement the primitives. Then plug the core into basic_fbstring as
 210  * a template argument.
 211
 212 template <class Char>
 213 class fbstring_core_model {
 214 public:
 215   fbstring_core_model();
 216   fbstring_core_model(const fbstring_core_model &);
 217   ~fbstring_core_model();
 218   // Returns a pointer to string's buffer (currently only contiguous
 219   // strings are supported). The pointer is guaranteed to be valid
 220   // until the next call to a non-const member function.
 221   const Char * data() const;
 222   // Much like data(), except the string is prepared to support
 223   // character-level changes. This call is a signal for
 224   // e.g. reference-counted implementation to fork the data. The
 225   // pointer is guaranteed to be valid until the next call to a
 226   // non-const member function.
 227   Char * mutable_data();
 228   // Returns a pointer to string's buffer and guarantees that a
 229   // readable '\0' lies right after the buffer. The pointer is
 230   // guaranteed to be valid until the next call to a non-const member
 231   // function.
 232   const Char * c_str() const;
 233   // Shrinks the string by delta characters. Asserts that delta <=
 234   // size().
 235   void shrink(size_t delta);
 236   // Expands the string by delta characters (i.e. after this call
 237   // size() will report the old size() plus delta) but without
 238   // initializing the expanded region. The expanded region is
 239   // zero-terminated. Returns a pointer to the memory to be
 240   // initialized (the beginning of the expanded portion). The caller
 241   // is expected to fill the expanded area appropriately.
 242   // If expGrowth is true, exponential growth is guaranteed.
 243   // It is not guaranteed not to reallocate even if size() + delta <
 244   // capacity(), so all references to the buffer are invalidated.
 245   Char* expand_noinit(size_t delta, bool expGrowth);
 246   // Expands the string by one character and sets the last character
 247   // to c.
 248   void push_back(Char c);
 249   // Returns the string's size.
 250   size_t size() const;
 251   // Returns the string's capacity, i.e. maximum size that the string
 252   // can grow to without reallocation. Note that for reference counted
 253   // strings that's technically a lie - even assigning characters
 254   // within the existing size would cause a reallocation.
 255   size_t capacity() const;
 256   // Returns true if the data underlying the string is actually shared
 257   // across multiple strings (in a refcounted fashion).
 258   bool isShared() const;
 259   // Makes sure that at least minCapacity characters are available for
 260   // the string without reallocation. For reference-counted strings,
 261   // it should fork the data even if minCapacity < size().
 262   void reserve(size_t minCapacity);
 263 private:
 264   // Do not implement
 265   fbstring_core_model& operator=(const fbstring_core_model &);
 266 };
 267 */
 268
 269 /**
 270  * This is the core of the string. The code should work on 32- and
 271  * 64-bit and both big- and little-endianan architectures with any
 272  * Char size.
 273  *
 274  * The storage is selected as follows (assuming we store one-byte
 275  * characters on a 64-bit machine): (a) "small" strings between 0 and
 276  * 23 chars are stored in-situ without allocation (the rightmost byte
 277  * stores the size); (b) "medium" strings from 24 through 254 chars
 278  * are stored in malloc-allocated memory that is copied eagerly; (c)
 279  * "large" strings of 255 chars and above are stored in a similar
 280  * structure as medium arrays, except that the string is
 281  * reference-counted and copied lazily. the reference count is
 282  * allocated right before the character array.
 283  *
 284  * The discriminator between these three strategies sits in two
 285  * bits of the rightmost char of the storage. If neither is set, then the
 286  * string is small (and its length sits in the lower-order bits on
 287  * little-endian or the high-order bits on big-endian of that
 288  * rightmost character). If the MSb is set, the string is medium width.
 289  * If the second MSb is set, then the string is large. On little-endian,
 290  * these 2 bits are the 2 MSbs of MediumLarge::capacity_, while on
 291  * big-endian, these 2 bits are the 2 LSbs. This keeps both little-endian
 292  * and big-endian fbstring_core equivalent with merely different ops used
 293  * to extract capacity/category.
 294  */
 295 template <class Char> class fbstring_core {
 296 protected:
 297 // It's MSVC, so we just have to guess ... and allow an override
 298 #ifdef _MSC_VER
 299 # ifdef FOLLY_ENDIAN_BE
 300   static constexpr auto kIsLittleEndian = false;
 301 # else
 302   static constexpr auto kIsLittleEndian = true;
 303 # endif
 304 #else
 305   static constexpr auto kIsLittleEndian =
 306       __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__;
 307 #endif
 308 public:
 309   fbstring_core() noexcept { reset(); }
 310
 311   fbstring_core(const fbstring_core & rhs) {
 312     assert(&rhs != this);
 313     // Simplest case first: small strings are bitblitted
 314     if (rhs.category() == Category::isSmall) {
 315       static_assert(offsetof(MediumLarge, data_) == 0,
 316           "fbstring layout failure");
 317       static_assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_),
 318           "fbstring layout failure");
 319       static_assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_),
 320           "fbstring layout failure");
 321       // Just write the whole thing, don't look at details. In
 322       // particular we need to copy capacity anyway because we want
 323       // to set the size (don't forget that the last character,
 324       // which stores a short string's length, is shared with the
 325       // ml_.capacity field).
 326       ml_ = rhs.ml_;
 327       assert(category() == Category::isSmall && this->size() == rhs.size());
 328     } else if (rhs.category() == Category::isLarge) {
 329       // Large strings are just refcounted
 330       ml_ = rhs.ml_;
 331       RefCounted::incrementRefs(ml_.data_);
 332       assert(category() == Category::isLarge && size() == rhs.size());
 333     } else {
 334       // Medium strings are copied eagerly. Don't forget to allocate
 335       // one extra Char for the null terminator.
 336       auto const allocSize =
 337            goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
 338       ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
 339       // Also copies terminator.
 340       fbstring_detail::pod_copy(rhs.ml_.data_,
 341                                 rhs.ml_.data_ + rhs.ml_.size_ + 1,
 342                                 ml_.data_);
 343       ml_.size_ = rhs.ml_.size_;
 344       ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
 345       assert(category() == Category::isMedium);
 346     }
 347     assert(size() == rhs.size());
 348     assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
 349   }
 350
 351   fbstring_core(fbstring_core&& goner) noexcept {
 352     // Take goner's guts
 353     ml_ = goner.ml_;
 354     // Clean goner's carcass
 355     goner.reset();
 356   }
 357
 358   fbstring_core(const Char *const data,
 359                 const size_t size,
 360                 bool disableSSO = FBSTRING_DISABLE_SSO) {
 361 #ifndef NDEBUG
 362 #ifndef _LIBSTDCXX_FBSTRING
 363     SCOPE_EXIT {
 364       assert(this->size() == size);
 365       assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
 366     };
 367 #endif
 368 #endif
 369
 370     // Simplest case first: small strings are bitblitted
 371     if (!disableSSO && size <= maxSmallSize) {
 372       // Layout is: Char* data_, size_t size_, size_t capacity_
 373       static_assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t),
 374           "fbstring has unexpected size");
 375       static_assert(sizeof(Char*) == sizeof(size_t),
 376           "fbstring size assumption violation");
 377       // sizeof(size_t) must be a power of 2
 378       static_assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0,
 379           "fbstring size assumption violation");
 380
 381       // If data is aligned, use fast word-wise copying. Otherwise,
 382       // use conservative memcpy.
 383       // The word-wise path reads bytes which are outside the range of
 384       // the string, and makes ASan unhappy, so we disable it when
 385       // compiling with ASan.
 386 #ifndef FBSTRING_SANITIZE_ADDRESS
 387       if ((reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) == 0) {
 388         const size_t byteSize = size * sizeof(Char);
 389         constexpr size_t wordWidth = sizeof(size_t);
 390         switch ((byteSize + wordWidth - 1) / wordWidth) { // Number of words.
 391         case 3:
 392           ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
 393         case 2:
 394           ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
 395         case 1:
 396           ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
 397         case 0:
 398           break;
 399         }
 400       } else
 401 #endif
 402       {
 403         fbstring_detail::pod_copy(data, data + size, small_);
 404       }
 405       setSmallSize(size);
 406     } else {
 407       if (size <= maxMediumSize) {
 408         // Medium strings are allocated normally. Don't forget to
 409         // allocate one extra Char for the terminating null.
 410         auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
 411         ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
 412         fbstring_detail::pod_copy(data, data + size, ml_.data_);
 413         ml_.size_ = size;
 414         ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
 415       } else {
 416         // Large strings are allocated differently
 417         size_t effectiveCapacity = size;
 418         auto const newRC = RefCounted::create(data, & effectiveCapacity);
 419         ml_.data_ = newRC->data_;
 420         ml_.size_ = size;
 421         ml_.setCapacity(effectiveCapacity, Category::isLarge);
 422       }
 423       ml_.data_[size] = '\0';
 424     }
 425   }
 426
 427   ~fbstring_core() noexcept {
 428     auto const c = category();
 429     if (c == Category::isSmall) {
 430       return;
 431     }
 432     if (c == Category::isMedium) {
 433       free(ml_.data_);
 434       return;
 435     }
 436     RefCounted::decrementRefs(ml_.data_);
 437   }
 438
 439   // Snatches a previously mallocated string. The parameter "size"
 440   // is the size of the string, and the parameter "allocatedSize"
 441   // is the size of the mallocated block.  The string must be
 442   // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
 443   //
 444   // So if you want a 2-character string, pass malloc(3) as "data",
 445   // pass 2 as "size", and pass 3 as "allocatedSize".
 446   fbstring_core(Char * const data,
 447                 const size_t size,
 448                 const size_t allocatedSize,
 449                 AcquireMallocatedString) {
 450     if (size > 0) {
 451       assert(allocatedSize >= size + 1);
 452       assert(data[size] == '\0');
 453       // Use the medium string storage
 454       ml_.data_ = data;
 455       ml_.size_ = size;
 456       // Don't forget about null terminator
 457       ml_.setCapacity(allocatedSize - 1, Category::isMedium);
 458     } else {
 459       // No need for the memory
 460       free(data);
 461       reset();
 462     }
 463   }
 464
 465   // swap below doesn't test whether &rhs == this (and instead
 466   // potentially does extra work) on the premise that the rarity of
 467   // that situation actually makes the check more expensive than is
 468   // worth.
 469   void swap(fbstring_core & rhs) {
 470     auto const t = ml_;
 471     ml_ = rhs.ml_;
 472     rhs.ml_ = t;
 473   }
 474
 475   // In C++11 data() and c_str() are 100% equivalent.
 476   const Char * data() const {
 477     return c_str();
 478   }
 479
 480   Char * mutable_data() {
 481     auto const c = category();
 482     if (c == Category::isSmall) {
 483       return small_;
 484     }
 485     assert(c == Category::isMedium || c == Category::isLarge);
 486     if (c == Category::isLarge && RefCounted::refs(ml_.data_) > 1) {
 487       // Ensure unique.
 488       size_t effectiveCapacity = ml_.capacity();
 489       auto const newRC = RefCounted::create(& effectiveCapacity);
 490       // If this fails, someone placed the wrong capacity in an
 491       // fbstring.
 492       assert(effectiveCapacity >= ml_.capacity());
 493       // Also copies terminator.
 494       fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
 495                                 newRC->data_);
 496       RefCounted::decrementRefs(ml_.data_);
 497       ml_.data_ = newRC->data_;
 498     }
 499     return ml_.data_;
 500   }
 501
 502   const Char * c_str() const {
 503     auto const c = category();
 504     if (c == Category::isSmall) {
 505       assert(small_[smallSize()] == '\0');
 506       return small_;
 507     }
 508     assert(c == Category::isMedium || c == Category::isLarge);
 509     assert(ml_.data_[ml_.size_] == '\0');
 510     return ml_.data_;
 511   }
 512
 513   void shrink(const size_t delta) {
 514     if (category() == Category::isSmall) {
 515       // Check for underflow
 516       assert(delta <= smallSize());
 517       setSmallSize(smallSize() - delta);
 518     } else if (category() == Category::isMedium ||
 519                RefCounted::refs(ml_.data_) == 1) {
 520       // Medium strings and unique large strings need no special
 521       // handling.
 522       assert(ml_.size_ >= delta);
 523       ml_.size_ -= delta;
 524       ml_.data_[ml_.size_] = '\0';
 525     } else {
 526       assert(ml_.size_ >= delta);
 527       // Shared large string, must make unique. This is because of the
 528       // durn terminator must be written, which may trample the shared
 529       // data.
 530       if (delta) {
 531         fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
 532       }
 533       // No need to write the terminator.
 534     }
 535   }
 536
 537   void reserve(size_t minCapacity, bool disableSSO = FBSTRING_DISABLE_SSO) {
 538     if (category() == Category::isLarge) {
 539       // Ensure unique
 540       if (RefCounted::refs(ml_.data_) > 1) {
 541         // We must make it unique regardless; in-place reallocation is
 542         // useless if the string is shared. In order to not surprise
 543         // people, reserve the new block at current capacity or
 544         // more. That way, a string's capacity never shrinks after a
 545         // call to reserve.
 546         minCapacity = std::max(minCapacity, ml_.capacity());
 547         auto const newRC = RefCounted::create(& minCapacity);
 548         // Also copies terminator.
 549         fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
 550                                    newRC->data_);
 551         RefCounted::decrementRefs(ml_.data_);
 552         ml_.data_ = newRC->data_;
 553         ml_.setCapacity(minCapacity, Category::isLarge);
 554         // size remains unchanged
 555       } else {
 556         // String is not shared, so let's try to realloc (if needed)
 557         if (minCapacity > ml_.capacity()) {
 558           // Asking for more memory
 559           auto const newRC =
 560                RefCounted::reallocate(ml_.data_, ml_.size_,
 561                                       ml_.capacity(), minCapacity);
 562           ml_.data_ = newRC->data_;
 563           ml_.setCapacity(minCapacity, Category::isLarge);
 564         }
 565         assert(capacity() >= minCapacity);
 566       }
 567     } else if (category() == Category::isMedium) {
 568       // String is not shared
 569       if (minCapacity <= ml_.capacity()) {
 570         return; // nothing to do, there's enough room
 571       }
 572       if (minCapacity <= maxMediumSize) {
 573         // Keep the string at medium size. Don't forget to allocate
 574         // one extra Char for the terminating null.
 575         size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
 576         // Also copies terminator.
 577         ml_.data_ = static_cast<Char *>(
 578           smartRealloc(
 579             ml_.data_,
 580             (ml_.size_ + 1) * sizeof(Char),
 581             (ml_.capacity() + 1) * sizeof(Char),
 582             capacityBytes));
 583         ml_.setCapacity(capacityBytes / sizeof(Char) - 1, Category::isMedium);
 584       } else {
 585         // Conversion from medium to large string
 586         fbstring_core nascent;
 587         // Will recurse to another branch of this function
 588         nascent.reserve(minCapacity);
 589         nascent.ml_.size_ = ml_.size_;
 590         // Also copies terminator.
 591         fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
 592                                   nascent.ml_.data_);
 593         nascent.swap(*this);
 594         assert(capacity() >= minCapacity);
 595       }
 596     } else {
 597       assert(category() == Category::isSmall);
 598       if (!disableSSO && minCapacity <= maxSmallSize) {
 599         // small
 600         // Nothing to do, everything stays put
 601       } else if (minCapacity <= maxMediumSize) {
 602         // medium
 603         // Don't forget to allocate one extra Char for the terminating null
 604         auto const allocSizeBytes =
 605           goodMallocSize((1 + minCapacity) * sizeof(Char));
 606         auto const pData = static_cast<Char*>(checkedMalloc(allocSizeBytes));
 607         auto const size = smallSize();
 608         // Also copies terminator.
 609         fbstring_detail::pod_copy(small_, small_ + size + 1, pData);
 610         ml_.data_ = pData;
 611         ml_.size_ = size;
 612         ml_.setCapacity(allocSizeBytes / sizeof(Char) - 1, Category::isMedium);
 613       } else {
 614         // large
 615         auto const newRC = RefCounted::create(& minCapacity);
 616         auto const size = smallSize();
 617         // Also copies terminator.
 618         fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
 619         ml_.data_ = newRC->data_;
 620         ml_.size_ = size;
 621         ml_.setCapacity(minCapacity, Category::isLarge);
 622         assert(capacity() >= minCapacity);
 623       }
 624     }
 625     assert(capacity() >= minCapacity);
 626   }
 627
 628   Char * expand_noinit(const size_t delta,
 629                        bool expGrowth = false,
 630                        bool disableSSO = FBSTRING_DISABLE_SSO) {
 631     // Strategy is simple: make room, then change size
 632     assert(capacity() >= size());
 633     size_t sz, newSz;
 634     if (category() == Category::isSmall) {
 635       sz = smallSize();
 636       newSz = sz + delta;
 637       if (!disableSSO && FBSTRING_LIKELY(newSz <= maxSmallSize)) {
 638         setSmallSize(newSz);
 639         return small_ + sz;
 640       }
 641       reserve(expGrowth ? std::max(newSz, 2 * maxSmallSize) : newSz);
 642     } else {
 643       sz = ml_.size_;
 644       newSz = sz + delta;
 645       if (FBSTRING_UNLIKELY(newSz > capacity())) {
 646         // ensures not shared
 647         reserve(expGrowth ? std::max(newSz, 1 + capacity() * 3 / 2) : newSz);
 648       }
 649     }
 650     assert(capacity() >= newSz);
 651     // Category can't be small - we took care of that above
 652     assert(category() == Category::isMedium || category() == Category::isLarge);
 653     ml_.size_ = newSz;
 654     ml_.data_[newSz] = '\0';
 655     assert(size() == newSz);
 656     return ml_.data_ + sz;
 657   }
 658
 659   void push_back(Char c) {
 660     *expand_noinit(1, /* expGrowth = */ true) = c;
 661   }
 662
 663   size_t size() const {
 664     return category() == Category::isSmall ? smallSize() : ml_.size_;
 665   }
 666
 667   size_t capacity() const {
 668     switch (category()) {
 669       case Category::isSmall:
 670         return maxSmallSize;
 671       case Category::isLarge:
 672         // For large-sized strings, a multi-referenced chunk has no
 673         // available capacity. This is because any attempt to append
 674         // data would trigger a new allocation.
 675         if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
 676       default: {}
 677     }
 678     return ml_.capacity();
 679   }
 680
 681   bool isShared() const {
 682     return category() == Category::isLarge && RefCounted::refs(ml_.data_) > 1;
 683   }
 684
 685 private:
 686   // Disabled
 687   fbstring_core & operator=(const fbstring_core & rhs);
 688
 689   // Equivalent to setSmallSize(0) but a few ns faster in
 690   // microbenchmarks.
 691   void reset() {
 692     ml_.capacity_ = kIsLittleEndian
 693       ? maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)))
 694       : maxSmallSize << 2;
 695     small_[0] = '\0';
 696     assert(category() == Category::isSmall && size() == 0);
 697   }
 698
 699   struct RefCounted {
 700     std::atomic<size_t> refCount_;
 701     Char data_[1];
 702
 703     static RefCounted * fromData(Char * p) {
 704       return static_cast<RefCounted*>(
 705         static_cast<void*>(
 706           static_cast<unsigned char*>(static_cast<void*>(p))
 707           - sizeof(refCount_)));
 708     }
 709
 710     static size_t refs(Char * p) {
 711       return fromData(p)->refCount_.load(std::memory_order_acquire);
 712     }
 713
 714     static void incrementRefs(Char * p) {
 715       fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
 716     }
 717
 718     static void decrementRefs(Char * p) {
 719       auto const dis = fromData(p);
 720       size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
 721       assert(oldcnt > 0);
 722       if (oldcnt == 1) {
 723         free(dis);
 724       }
 725     }
 726
 727     static RefCounted * create(size_t * size) {
 728       // Don't forget to allocate one extra Char for the terminating
 729       // null. In this case, however, one Char is already part of the
 730       // struct.
 731       const size_t allocSize = goodMallocSize(
 732         sizeof(RefCounted) + *size * sizeof(Char));
 733       auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
 734       result->refCount_.store(1, std::memory_order_release);
 735       *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
 736       return result;
 737     }
 738
 739     static RefCounted * create(const Char * data, size_t * size) {
 740       const size_t effectiveSize = *size;
 741       auto result = create(size);
 742       fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
 743       return result;
 744     }
 745
 746     static RefCounted * reallocate(Char *const data,
 747                                    const size_t currentSize,
 748                                    const size_t currentCapacity,
 749                                    const size_t newCapacity) {
 750       assert(newCapacity > 0 && newCapacity > currentSize);
 751       auto const dis = fromData(data);
 752       assert(dis->refCount_.load(std::memory_order_acquire) == 1);
 753       // Don't forget to allocate one extra Char for the terminating
 754       // null. In this case, however, one Char is already part of the
 755       // struct.
 756       auto result = static_cast<RefCounted*>(
 757              smartRealloc(dis,
 758                           sizeof(RefCounted) + currentSize * sizeof(Char),
 759                           sizeof(RefCounted) + currentCapacity * sizeof(Char),
 760                           sizeof(RefCounted) + newCapacity * sizeof(Char)));
 761       assert(result->refCount_.load(std::memory_order_acquire) == 1);
 762       return result;
 763     }
 764   };
 765
 766   typedef std::conditional<sizeof(size_t) == 4, uint32_t, uint64_t>::type
 767           category_type;
 768
 769   enum class Category : category_type {
 770     isSmall = 0,
 771     isMedium = kIsLittleEndian
 772       ? sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000
 773       : 0x2,
 774     isLarge =  kIsLittleEndian
 775       ? sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000
 776       : 0x1,
 777   };
 778
 779   Category category() const {
 780     // works for both big-endian and little-endian
 781     return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
 782   }
 783
 784   struct MediumLarge {
 785     Char * data_;
 786     size_t size_;
 787     size_t capacity_;
 788
 789     size_t capacity() const {
 790       return kIsLittleEndian
 791         ? capacity_ & capacityExtractMask
 792         : capacity_ >> 2;
 793     }
 794
 795     void setCapacity(size_t cap, Category cat) {
 796         capacity_ = kIsLittleEndian
 797           ? cap | static_cast<category_type>(cat)
 798           : (cap << 2) | static_cast<category_type>(cat);
 799     }
 800   };
 801
 802   union {
 803     Char small_[sizeof(MediumLarge) / sizeof(Char)];
 804     MediumLarge ml_;
 805   };
 806
 807   enum : size_t {
 808     lastChar = sizeof(MediumLarge) - 1,
 809     maxSmallSize = lastChar / sizeof(Char),
 810     maxMediumSize = 254 / sizeof(Char),            // coincides with the small
 811                                                    // bin size in dlmalloc
 812     categoryExtractMask = kIsLittleEndian
 813       ? sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000
 814       : 0x3,
 815     capacityExtractMask = kIsLittleEndian
 816       ? ~categoryExtractMask
 817       : 0x0 /*unused*/,
 818   };
 819   static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
 820                 "Corrupt memory layout for fbstring.");
 821
 822   size_t smallSize() const {
 823     assert(category() == Category::isSmall);
 824     constexpr auto shift = kIsLittleEndian ? 0 : 2;
 825     auto smallShifted = static_cast<size_t>(small_[maxSmallSize]) >> shift;
 826     assert(static_cast<size_t>(maxSmallSize) >= smallShifted);
 827     return static_cast<size_t>(maxSmallSize) - smallShifted;
 828   }
 829
 830   void setSmallSize(size_t s) {
 831     // Warning: this should work with uninitialized strings too,
 832     // so don't assume anything about the previous value of
 833     // small_[maxSmallSize].
 834     assert(s <= maxSmallSize);
 835     constexpr auto shift = kIsLittleEndian ? 0 : 2;
 836     small_[maxSmallSize] = (maxSmallSize - s) << shift;
 837     small_[s] = '\0';
 838     assert(category() == Category::isSmall && size() == s);
 839   }
 840 };
 841
 842 #ifndef _LIBSTDCXX_FBSTRING
 843 /**
 844  * Dummy fbstring core that uses an actual std::string. This doesn't
 845  * make any sense - it's just for testing purposes.
 846  */
 847 template <class Char>
 848 class dummy_fbstring_core {
 849 public:
 850   dummy_fbstring_core() {
 851   }
 852   dummy_fbstring_core(const dummy_fbstring_core& another)
 853       : backend_(another.backend_) {
 854   }
 855   dummy_fbstring_core(const Char * s, size_t n)
 856       : backend_(s, n) {
 857   }
 858   void swap(dummy_fbstring_core & rhs) {
 859     backend_.swap(rhs.backend_);
 860   }
 861   const Char * data() const {
 862     return backend_.data();
 863   }
 864   Char * mutable_data() {
 865     //assert(!backend_.empty());
 866     return &*backend_.begin();
 867   }
 868   void shrink(size_t delta) {
 869     assert(delta <= size());
 870     backend_.resize(size() - delta);
 871   }
 872   Char * expand_noinit(size_t delta) {
 873     auto const sz = size();
 874     backend_.resize(size() + delta);
 875     return backend_.data() + sz;
 876   }
 877   void push_back(Char c) {
 878     backend_.push_back(c);
 879   }
 880   size_t size() const {
 881     return backend_.size();
 882   }
 883   size_t capacity() const {
 884     return backend_.capacity();
 885   }
 886   bool isShared() const {
 887     return false;
 888   }
 889   void reserve(size_t minCapacity) {
 890     backend_.reserve(minCapacity);
 891   }
 892
 893 private:
 894   std::basic_string<Char> backend_;
 895 };
 896 #endif // !_LIBSTDCXX_FBSTRING
 897
 898 /**
 899  * This is the basic_string replacement. For conformity,
 900  * basic_fbstring takes the same template parameters, plus the last
 901  * one which is the core.
 902  */
 903 #ifdef _LIBSTDCXX_FBSTRING
 904 template <typename E, class T, class A, class Storage>
 905 #else
 906 template <typename E,
 907           class T = std::char_traits<E>,
 908           class A = std::allocator<E>,
 909           class Storage = fbstring_core<E> >
 910 #endif
 911 class basic_fbstring {
 912
 913   static void enforce(
 914       bool condition,
 915       void (*throw_exc)(const char*),
 916       const char* msg) {
 917     if (!condition) throw_exc(msg);
 918   }
 919
 920   bool isSane() const {
 921     return
 922       begin() <= end() &&
 923       empty() == (size() == 0) &&
 924       empty() == (begin() == end()) &&
 925       size() <= max_size() &&
 926       capacity() <= max_size() &&
 927       size() <= capacity() &&
 928       begin()[size()] == '\0';
 929   }
 930
 931   struct Invariant;
 932   friend struct Invariant;
 933   struct Invariant {
 934 #ifndef NDEBUG
 935     explicit Invariant(const basic_fbstring& s) : s_(s) {
 936       assert(s_.isSane());
 937     }
 938     ~Invariant() {
 939       assert(s_.isSane());
 940     }
 941   private:
 942     const basic_fbstring& s_;
 943 #else
 944     explicit Invariant(const basic_fbstring&) {}
 945 #endif
 946     Invariant& operator=(const Invariant&);
 947   };
 948
 949 public:
 950   // types
 951   typedef T traits_type;
 952   typedef typename traits_type::char_type value_type;
 953   typedef A allocator_type;
 954   typedef typename A::size_type size_type;
 955   typedef typename A::difference_type difference_type;
 956
 957   typedef typename A::reference reference;
 958   typedef typename A::const_reference const_reference;
 959   typedef typename A::pointer pointer;
 960   typedef typename A::const_pointer const_pointer;
 961
 962   typedef E* iterator;
 963   typedef const E* const_iterator;
 964   typedef std::reverse_iterator<iterator
 965 #ifdef NO_ITERATOR_TRAITS
 966                                 , value_type
 967 #endif
 968                                 > reverse_iterator;
 969   typedef std::reverse_iterator<const_iterator
 970 #ifdef NO_ITERATOR_TRAITS
 971                                 , const value_type
 972 #endif
 973                                 > const_reverse_iterator;
 974
 975   static const size_type npos;                     // = size_type(-1)
 976   typedef std::true_type IsRelocatable;
 977
 978 private:
 979   static void procrustes(size_type& n, size_type nmax) {
 980     if (n > nmax) n = nmax;
 981   }
 982
 983 public:
 984   // C++11 21.4.2 construct/copy/destroy
 985
 986   // Note: while the following two constructors can be (and previously were)
 987   // collapsed into one constructor written this way:
 988   //
 989   //   explicit basic_fbstring(const A& a = A()) noexcept { }
 990   //
 991   // This can cause Clang (at least version 3.7) to fail with the error:
 992   //   "chosen constructor is explicit in copy-initialization ...
 993   //   in implicit initialization of field '(x)' with omitted initializer"
 994   //
 995   // if used in a struct which is default-initialized.  Hence the split into
 996   // these two separate constructors.
 997
 998   basic_fbstring() noexcept : basic_fbstring(A()) {
 999   }
1000
1001   explicit basic_fbstring(const A&) noexcept {
1002   }
1003
1004   basic_fbstring(const basic_fbstring& str)
1005       : store_(str.store_) {
1006   }
1007
1008   // Move constructor
1009   basic_fbstring(basic_fbstring&& goner) noexcept
1010       : store_(std::move(goner.store_)) {
1011   }
1012
1013 #ifndef _LIBSTDCXX_FBSTRING
1014   // This is defined for compatibility with std::string
1015   /* implicit */ basic_fbstring(const std::string& str)
1016       : store_(str.data(), str.size()) {
1017   }
1018 #endif
1019
1020   basic_fbstring(const basic_fbstring& str,
1021                  size_type pos,
1022                  size_type n = npos,
1023                  const A& /* a */ = A()) {
1024     assign(str, pos, n);
1025   }
1026
1027   /* implicit */ basic_fbstring(const value_type* s, const A& /*a*/ = A())
1028       : store_(s, s
1029           ? traits_type::length(s)
1030           : (std::__throw_logic_error(
1031                 "basic_fbstring: null pointer initializer not valid"),
1032              0)) {
1033   }
1034
1035   basic_fbstring(const value_type* s, size_type n, const A& /*a*/ = A())
1036       : store_(s, n) {
1037   }
1038
1039   basic_fbstring(size_type n, value_type c, const A& /*a*/ = A()) {
1040     auto const pData = store_.expand_noinit(n);
1041     fbstring_detail::pod_fill(pData, pData + n, c);
1042   }
1043
1044   template <class InIt>
1045   basic_fbstring(InIt begin, InIt end,
1046                  typename std::enable_if<
1047                  !std::is_same<typename std::remove_const<InIt>::type,
1048                  value_type*>::value, const A>::type & /*a*/ = A()) {
1049     assign(begin, end);
1050   }
1051
1052   // Specialization for const char*, const char*
1053   basic_fbstring(const value_type* b, const value_type* e)
1054       : store_(b, e - b) {
1055   }
1056
1057   // Nonstandard constructor
1058   basic_fbstring(value_type *s, size_type n, size_type c,
1059                  AcquireMallocatedString a)
1060       : store_(s, n, c, a) {
1061   }
1062
1063   // Construction from initialization list
1064   basic_fbstring(std::initializer_list<value_type> il) {
1065     assign(il.begin(), il.end());
1066   }
1067
1068   ~basic_fbstring() noexcept {
1069   }
1070
1071   basic_fbstring& operator=(const basic_fbstring& lhs) {
1072     Invariant checker(*this);
1073
1074     if (FBSTRING_UNLIKELY(&lhs == this)) {
1075       return *this;
1076     }
1077     auto const oldSize = size();
1078     auto const srcSize = lhs.size();
1079     if (capacity() >= srcSize && !store_.isShared()) {
1080       // great, just copy the contents
1081       if (oldSize < srcSize) {
1082         store_.expand_noinit(srcSize - oldSize);
1083       } else {
1084         store_.shrink(oldSize - srcSize);
1085       }
1086       assert(size() == srcSize);
1087       auto srcData = lhs.data();
1088       fbstring_detail::pod_copy(
1089           srcData, srcData + srcSize, store_.mutable_data());
1090     } else {
1091       // need to reallocate, so we may as well create a brand new string
1092       basic_fbstring(lhs).swap(*this);
1093     }
1094     return *this;
1095   }
1096
1097   // Move assignment
1098   basic_fbstring& operator=(basic_fbstring&& goner) noexcept {
1099     if (FBSTRING_UNLIKELY(&goner == this)) {
1100       // Compatibility with std::basic_string<>,
1101       // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1102       return *this;
1103     }
1104     // No need of this anymore
1105     this->~basic_fbstring();
1106     // Move the goner into this
1107     new(&store_) fbstring_core<E>(std::move(goner.store_));
1108     return *this;
1109   }
1110
1111 #ifndef _LIBSTDCXX_FBSTRING
1112   // Compatibility with std::string
1113   basic_fbstring & operator=(const std::string & rhs) {
1114     return assign(rhs.data(), rhs.size());
1115   }
1116
1117   // Compatibility with std::string
1118   std::string toStdString() const {
1119     return std::string(data(), size());
1120   }
1121 #else
1122   // A lot of code in fbcode still uses this method, so keep it here for now.
1123   const basic_fbstring& toStdString() const {
1124     return *this;
1125   }
1126 #endif
1127
1128   basic_fbstring& operator=(const value_type* s) {
1129     return assign(s);
1130   }
1131
1132   basic_fbstring& operator=(value_type c) {
1133     Invariant checker(*this);
1134
1135     if (empty()) {
1136       store_.expand_noinit(1);
1137     } else if (store_.isShared()) {
1138       basic_fbstring(1, c).swap(*this);
1139       return *this;
1140     } else {
1141       store_.shrink(size() - 1);
1142     }
1143     front() = c;
1144     return *this;
1145   }
1146
1147   basic_fbstring& operator=(std::initializer_list<value_type> il) {
1148     return assign(il.begin(), il.end());
1149   }
1150
1151   // C++11 21.4.3 iterators:
1152   iterator begin() { return store_.mutable_data(); }
1153
1154   const_iterator begin() const { return store_.data(); }
1155
1156   const_iterator cbegin() const { return begin(); }
1157
1158   iterator end() {
1159     return store_.mutable_data() + store_.size();
1160   }
1161
1162   const_iterator end() const {
1163     return store_.data() + store_.size();
1164   }
1165
1166   const_iterator cend() const { return end(); }
1167
1168   reverse_iterator rbegin() {
1169     return reverse_iterator(end());
1170   }
1171
1172   const_reverse_iterator rbegin() const {
1173     return const_reverse_iterator(end());
1174   }
1175
1176   const_reverse_iterator crbegin() const { return rbegin(); }
1177
1178   reverse_iterator rend() {
1179     return reverse_iterator(begin());
1180   }
1181
1182   const_reverse_iterator rend() const {
1183     return const_reverse_iterator(begin());
1184   }
1185
1186   const_reverse_iterator crend() const { return rend(); }
1187
1188   // Added by C++11
1189   // C++11 21.4.5, element access:
1190   const value_type& front() const { return *begin(); }
1191   const value_type& back() const {
1192     assert(!empty());
1193     // Should be begin()[size() - 1], but that branches twice
1194     return *(end() - 1);
1195   }
1196   value_type& front() { return *begin(); }
1197   value_type& back() {
1198     assert(!empty());
1199     // Should be begin()[size() - 1], but that branches twice
1200     return *(end() - 1);
1201   }
1202   void pop_back() {
1203     assert(!empty());
1204     store_.shrink(1);
1205   }
1206
1207   // C++11 21.4.4 capacity:
1208   size_type size() const { return store_.size(); }
1209
1210   size_type length() const { return size(); }
1211
1212   size_type max_size() const {
1213     return std::numeric_limits<size_type>::max();
1214   }
1215
1216   void resize(const size_type n, const value_type c = value_type()) {
1217     Invariant checker(*this);
1218
1219     auto size = this->size();
1220     if (n <= size) {
1221       store_.shrink(size - n);
1222     } else {
1223       auto const delta = n - size;
1224       auto pData = store_.expand_noinit(delta);
1225       fbstring_detail::pod_fill(pData, pData + delta, c);
1226     }
1227     assert(this->size() == n);
1228   }
1229
1230   size_type capacity() const { return store_.capacity(); }
1231
1232   void reserve(size_type res_arg = 0) {
1233     enforce(res_arg <= max_size(), std::__throw_length_error, "");
1234     store_.reserve(res_arg);
1235   }
1236
1237   void shrink_to_fit() {
1238     // Shrink only if slack memory is sufficiently large
1239     if (capacity() < size() * 3 / 2) {
1240       return;
1241     }
1242     basic_fbstring(cbegin(), cend()).swap(*this);
1243   }
1244
1245   void clear() { resize(0); }
1246
1247   bool empty() const { return size() == 0; }
1248
1249   // C++11 21.4.5 element access:
1250   const_reference operator[](size_type pos) const {
1251     return *(begin() + pos);
1252   }
1253
1254   reference operator[](size_type pos) {
1255     return *(begin() + pos);
1256   }
1257
1258   const_reference at(size_type n) const {
1259     enforce(n <= size(), std::__throw_out_of_range, "");
1260     return (*this)[n];
1261   }
1262
1263   reference at(size_type n) {
1264     enforce(n < size(), std::__throw_out_of_range, "");
1265     return (*this)[n];
1266   }
1267
1268   // C++11 21.4.6 modifiers:
1269   basic_fbstring& operator+=(const basic_fbstring& str) {
1270     return append(str);
1271   }
1272
1273   basic_fbstring& operator+=(const value_type* s) {
1274     return append(s);
1275   }
1276
1277   basic_fbstring& operator+=(const value_type c) {
1278     push_back(c);
1279     return *this;
1280   }
1281
1282   basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1283     append(il);
1284     return *this;
1285   }
1286
1287   basic_fbstring& append(const basic_fbstring& str) {
1288 #ifndef NDEBUG
1289     auto desiredSize = size() + str.size();
1290 #endif
1291     append(str.data(), str.size());
1292     assert(size() == desiredSize);
1293     return *this;
1294   }
1295
1296   basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1297                          size_type n) {
1298     const size_type sz = str.size();
1299     enforce(pos <= sz, std::__throw_out_of_range, "");
1300     procrustes(n, sz - pos);
1301     return append(str.data() + pos, n);
1302   }
1303
1304   basic_fbstring& append(const value_type* s, size_type n) {
1305     Invariant checker(*this);
1306
1307     if (FBSTRING_UNLIKELY(!n)) {
1308       // Unlikely but must be done
1309       return *this;
1310     }
1311     auto const oldSize = size();
1312     auto const oldData = data();
1313     // Check for aliasing (rare). We could use "<=" here but in theory
1314     // those do not work for pointers unless the pointers point to
1315     // elements in the same array. For that reason we use
1316     // std::less_equal, which is guaranteed to offer a total order
1317     // over pointers. See discussion at http://goo.gl/Cy2ya for more
1318     // info.
1319     std::less_equal<const value_type*> le;
1320     if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1321       assert(le(s + n, oldData + oldSize));
1322       const size_type offset = s - oldData;
1323       store_.reserve(oldSize + n);
1324       // Restore the source
1325       s = data() + offset;
1326     }
1327
1328     fbstring_detail::pod_copy(
1329         s, s + n, store_.expand_noinit(n, /* expGrowth = */ true));
1330     assert(size() == oldSize + n);
1331     return *this;
1332   }
1333
1334   basic_fbstring& append(const value_type* s) {
1335     return append(s, traits_type::length(s));
1336   }
1337
1338   basic_fbstring& append(size_type n, value_type c) {
1339     resize(size() + n, c);
1340     return *this;
1341   }
1342
1343   template<class InputIterator>
1344   basic_fbstring& append(InputIterator first, InputIterator last) {
1345     insert(end(), first, last);
1346     return *this;
1347   }
1348
1349   basic_fbstring& append(std::initializer_list<value_type> il) {
1350     return append(il.begin(), il.end());
1351   }
1352
1353   void push_back(const value_type c) {             // primitive
1354     store_.push_back(c);
1355   }
1356
1357   basic_fbstring& assign(const basic_fbstring& str) {
1358     if (&str == this) return *this;
1359     return assign(str.data(), str.size());
1360   }
1361
1362   basic_fbstring& assign(basic_fbstring&& str) {
1363     return *this = std::move(str);
1364   }
1365
1366   basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1367                          size_type n) {
1368     const size_type sz = str.size();
1369     enforce(pos <= sz, std::__throw_out_of_range, "");
1370     procrustes(n, sz - pos);
1371     return assign(str.data() + pos, n);
1372   }
1373
1374   basic_fbstring& assign(const value_type* s, const size_type n) {
1375     Invariant checker(*this);
1376
1377     // s can alias this, we need to use pod_move.
1378     if (size() >= n) {
1379       fbstring_detail::pod_move(s, s + n, store_.mutable_data());
1380       resize(n);
1381       assert(size() == n);
1382     } else {
1383       const value_type *const s2 = s + size();
1384       fbstring_detail::pod_move(s, s2, store_.mutable_data());
1385       append(s2, n - size());
1386       assert(size() == n);
1387     }
1388     assert(size() == n);
1389     return *this;
1390   }
1391
1392   basic_fbstring& assign(const value_type* s) {
1393     return assign(s, traits_type::length(s));
1394   }
1395
1396   basic_fbstring& assign(std::initializer_list<value_type> il) {
1397     return assign(il.begin(), il.end());
1398   }
1399
1400   template <class ItOrLength, class ItOrChar>
1401   basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1402     return replace(begin(), end(), first_or_n, last_or_c);
1403   }
1404
1405   basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1406     return insert(pos1, str.data(), str.size());
1407   }
1408
1409   basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1410                          size_type pos2, size_type n) {
1411     enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1412     procrustes(n, str.length() - pos2);
1413     return insert(pos1, str.data() + pos2, n);
1414   }
1415
1416   basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1417     enforce(pos <= length(), std::__throw_out_of_range, "");
1418     insert(begin() + pos, s, s + n);
1419     return *this;
1420   }
1421
1422   basic_fbstring& insert(size_type pos, const value_type* s) {
1423     return insert(pos, s, traits_type::length(s));
1424   }
1425
1426   basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1427     enforce(pos <= length(), std::__throw_out_of_range, "");
1428     insert(begin() + pos, n, c);
1429     return *this;
1430   }
1431
1432   iterator insert(const_iterator p, const value_type c) {
1433     const size_type pos = p - begin();
1434     insert(p, 1, c);
1435     return begin() + pos;
1436   }
1437
1438 #ifndef _LIBSTDCXX_FBSTRING
1439  private:
1440   typedef std::basic_istream<value_type, traits_type> istream_type;
1441
1442  public:
1443   friend inline istream_type& getline(istream_type& is,
1444                                       basic_fbstring& str,
1445                                       value_type delim) {
1446     Invariant checker(str);
1447
1448     str.clear();
1449     size_t size = 0;
1450     while (true) {
1451       size_t avail = str.capacity() - size;
1452       // fbstring has 1 byte extra capacity for the null terminator,
1453       // and getline null-terminates the read string.
1454       is.getline(str.store_.expand_noinit(avail), avail + 1, delim);
1455       size += is.gcount();
1456
1457       if (is.bad() || is.eof() || !is.fail()) {
1458         // Done by either failure, end of file, or normal read.
1459         if (!is.bad() && !is.eof()) {
1460           --size; // gcount() also accounts for the delimiter.
1461         }
1462         str.resize(size);
1463         break;
1464       }
1465
1466       assert(size == str.size());
1467       assert(size == str.capacity());
1468       // Start at minimum allocation 63 + terminator = 64.
1469       str.reserve(std::max<size_t>(63, 3 * size / 2));
1470       // Clear the error so we can continue reading.
1471       is.clear();
1472     }
1473     return is;
1474   }
1475
1476   friend inline istream_type& getline(istream_type& is, basic_fbstring& str) {
1477     return getline(is, str, '\n');
1478   }
1479 #endif
1480
1481 private:
1482   template <int i> class Selector {};
1483
1484   iterator insertImplDiscr(const_iterator i,
1485                            size_type n, value_type c, Selector<1>) {
1486     Invariant checker(*this);
1487
1488     assert(i >= begin() && i <= end());
1489     const size_type pos = i - begin();
1490
1491     auto oldSize = size();
1492     store_.expand_noinit(n, /* expGrowth = */ true);
1493     auto b = begin();
1494     fbstring_detail::pod_move(b + pos, b + oldSize, b + pos + n);
1495     fbstring_detail::pod_fill(b + pos, b + pos + n, c);
1496
1497     return b + pos;
1498   }
1499
1500   template<class InputIter>
1501   iterator insertImplDiscr(const_iterator i,
1502                            InputIter b, InputIter e, Selector<0>) {
1503     return insertImpl(i, b, e,
1504                typename std::iterator_traits<InputIter>::iterator_category());
1505   }
1506
1507   template <class FwdIterator>
1508   iterator insertImpl(const_iterator i,
1509                       FwdIterator s1,
1510                       FwdIterator s2,
1511                       std::forward_iterator_tag) {
1512     Invariant checker(*this);
1513
1514     assert(i >= begin() && i <= end());
1515     const size_type pos = i - begin();
1516     auto n = std::distance(s1, s2);
1517     assert(n >= 0);
1518
1519     auto oldSize = size();
1520     store_.expand_noinit(n, /* expGrowth = */ true);
1521     auto b = begin();
1522     fbstring_detail::pod_move(b + pos, b + oldSize, b + pos + n);
1523     std::copy(s1, s2, b + pos);
1524
1525     return b + pos;
1526   }
1527
1528   template <class InputIterator>
1529   iterator insertImpl(const_iterator i,
1530                       InputIterator b, InputIterator e,
1531                       std::input_iterator_tag) {
1532     const auto pos = i - begin();
1533     basic_fbstring temp(begin(), i);
1534     for (; b != e; ++b) {
1535       temp.push_back(*b);
1536     }
1537     temp.append(i, cend());
1538     swap(temp);
1539     return begin() + pos;
1540   }
1541
1542 public:
1543   template <class ItOrLength, class ItOrChar>
1544   iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1545     Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1546     return insertImplDiscr(p, first_or_n, last_or_c, sel);
1547   }
1548
1549   iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1550     return insert(p, il.begin(), il.end());
1551   }
1552
1553   basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1554     Invariant checker(*this);
1555
1556     enforce(pos <= length(), std::__throw_out_of_range, "");
1557     procrustes(n, length() - pos);
1558     std::copy(begin() + pos + n, end(), begin() + pos);
1559     resize(length() - n);
1560     return *this;
1561   }
1562
1563   iterator erase(iterator position) {
1564     const size_type pos(position - begin());
1565     enforce(pos <= size(), std::__throw_out_of_range, "");
1566     erase(pos, 1);
1567     return begin() + pos;
1568   }
1569
1570   iterator erase(iterator first, iterator last) {
1571     const size_type pos(first - begin());
1572     erase(pos, last - first);
1573     return begin() + pos;
1574   }
1575
1576   // Replaces at most n1 chars of *this, starting with pos1 with the
1577   // content of str
1578   basic_fbstring& replace(size_type pos1, size_type n1,
1579                           const basic_fbstring& str) {
1580     return replace(pos1, n1, str.data(), str.size());
1581   }
1582
1583   // Replaces at most n1 chars of *this, starting with pos1,
1584   // with at most n2 chars of str starting with pos2
1585   basic_fbstring& replace(size_type pos1, size_type n1,
1586                           const basic_fbstring& str,
1587                           size_type pos2, size_type n2) {
1588     enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1589     return replace(pos1, n1, str.data() + pos2,
1590                    std::min(n2, str.size() - pos2));
1591   }
1592
1593   // Replaces at most n1 chars of *this, starting with pos, with chars from s
1594   basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1595     return replace(pos, n1, s, traits_type::length(s));
1596   }
1597
1598   // Replaces at most n1 chars of *this, starting with pos, with n2
1599   // occurrences of c
1600   //
1601   // consolidated with
1602   //
1603   // Replaces at most n1 chars of *this, starting with pos, with at
1604   // most n2 chars of str.  str must have at least n2 chars.
1605   template <class StrOrLength, class NumOrChar>
1606   basic_fbstring& replace(size_type pos, size_type n1,
1607                           StrOrLength s_or_n2, NumOrChar n_or_c) {
1608     Invariant checker(*this);
1609
1610     enforce(pos <= size(), std::__throw_out_of_range, "");
1611     procrustes(n1, length() - pos);
1612     const iterator b = begin() + pos;
1613     return replace(b, b + n1, s_or_n2, n_or_c);
1614   }
1615
1616   basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1617     return replace(i1, i2, str.data(), str.length());
1618   }
1619
1620   basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1621     return replace(i1, i2, s, traits_type::length(s));
1622   }
1623
1624 private:
1625   basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1626                                    const value_type* s, size_type n,
1627                                    Selector<2>) {
1628     assert(i1 <= i2);
1629     assert(begin() <= i1 && i1 <= end());
1630     assert(begin() <= i2 && i2 <= end());
1631     return replace(i1, i2, s, s + n);
1632   }
1633
1634   basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1635                                    size_type n2, value_type c, Selector<1>) {
1636     const size_type n1 = i2 - i1;
1637     if (n1 > n2) {
1638       std::fill(i1, i1 + n2, c);
1639       erase(i1 + n2, i2);
1640     } else {
1641       std::fill(i1, i2, c);
1642       insert(i2, n2 - n1, c);
1643     }
1644     assert(isSane());
1645     return *this;
1646   }
1647
1648   template <class InputIter>
1649   basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1650                                    InputIter b, InputIter e,
1651                                    Selector<0>) {
1652     replaceImpl(i1, i2, b, e,
1653                 typename std::iterator_traits<InputIter>::iterator_category());
1654     return *this;
1655   }
1656
1657 private:
1658  template <class FwdIterator>
1659  bool replaceAliased(iterator /* i1 */,
1660                      iterator /* i2 */,
1661                      FwdIterator /* s1 */,
1662                      FwdIterator /* s2 */,
1663                      std::false_type) {
1664     return false;
1665   }
1666
1667   template <class FwdIterator>
1668   bool replaceAliased(iterator i1, iterator i2,
1669                       FwdIterator s1, FwdIterator s2, std::true_type) {
1670     static const std::less_equal<const value_type*> le =
1671       std::less_equal<const value_type*>();
1672     const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1673     if (!aliased) {
1674       return false;
1675     }
1676     // Aliased replace, copy to new string
1677     basic_fbstring temp;
1678     temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1679     temp.append(begin(), i1).append(s1, s2).append(i2, end());
1680     swap(temp);
1681     return true;
1682   }
1683
1684   template <class FwdIterator>
1685   void replaceImpl(iterator i1, iterator i2,
1686                    FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1687     Invariant checker(*this);
1688
1689     // Handle aliased replace
1690     if (replaceAliased(i1, i2, s1, s2,
1691           std::integral_constant<bool,
1692             std::is_same<FwdIterator, iterator>::value ||
1693             std::is_same<FwdIterator, const_iterator>::value>())) {
1694       return;
1695     }
1696
1697     auto const n1 = i2 - i1;
1698     assert(n1 >= 0);
1699     auto const n2 = std::distance(s1, s2);
1700     assert(n2 >= 0);
1701
1702     if (n1 > n2) {
1703       // shrinks
1704       std::copy(s1, s2, i1);
1705       erase(i1 + n2, i2);
1706     } else {
1707       // grows
1708       fbstring_detail::copy_n(s1, n1, i1);
1709       std::advance(s1, n1);
1710       insert(i2, s1, s2);
1711     }
1712     assert(isSane());
1713   }
1714
1715   template <class InputIterator>
1716   void replaceImpl(iterator i1, iterator i2,
1717                    InputIterator b, InputIterator e, std::input_iterator_tag) {
1718     basic_fbstring temp(begin(), i1);
1719     temp.append(b, e).append(i2, end());
1720     swap(temp);
1721   }
1722
1723 public:
1724   template <class T1, class T2>
1725   basic_fbstring& replace(iterator i1, iterator i2,
1726                           T1 first_or_n_or_s, T2 last_or_c_or_n) {
1727     const bool
1728       num1 = std::numeric_limits<T1>::is_specialized,
1729       num2 = std::numeric_limits<T2>::is_specialized;
1730     return replaceImplDiscr(
1731       i1, i2, first_or_n_or_s, last_or_c_or_n,
1732       Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1733   }
1734
1735   size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1736     enforce(pos <= size(), std::__throw_out_of_range, "");
1737     procrustes(n, size() - pos);
1738
1739     fbstring_detail::pod_copy(
1740       data() + pos,
1741       data() + pos + n,
1742       s);
1743     return n;
1744   }
1745
1746   void swap(basic_fbstring& rhs) {
1747     store_.swap(rhs.store_);
1748   }
1749
1750   const value_type* c_str() const {
1751     return store_.c_str();
1752   }
1753
1754   const value_type* data() const { return c_str(); }
1755
1756   allocator_type get_allocator() const {
1757     return allocator_type();
1758   }
1759
1760   size_type find(const basic_fbstring& str, size_type pos = 0) const {
1761     return find(str.data(), pos, str.length());
1762   }
1763
1764   size_type find(const value_type* needle, const size_type pos,
1765                  const size_type nsize) const {
1766     if (!nsize) return pos;
1767     auto const size = this->size();
1768     // nsize + pos can overflow (eg pos == npos), guard against that by checking
1769     // that nsize + pos does not wrap around.
1770     if (nsize + pos > size || nsize + pos < pos) return npos;
1771     // Don't use std::search, use a Boyer-Moore-like trick by comparing
1772     // the last characters first
1773     auto const haystack = data();
1774     auto const nsize_1 = nsize - 1;
1775     auto const lastNeedle = needle[nsize_1];
1776
1777     // Boyer-Moore skip value for the last char in the needle. Zero is
1778     // not a valid value; skip will be computed the first time it's
1779     // needed.
1780     size_type skip = 0;
1781
1782     const E * i = haystack + pos;
1783     auto iEnd = haystack + size - nsize_1;
1784
1785     while (i < iEnd) {
1786       // Boyer-Moore: match the last element in the needle
1787       while (i[nsize_1] != lastNeedle) {
1788         if (++i == iEnd) {
1789           // not found
1790           return npos;
1791         }
1792       }
1793       // Here we know that the last char matches
1794       // Continue in pedestrian mode
1795       for (size_t j = 0; ; ) {
1796         assert(j < nsize);
1797         if (i[j] != needle[j]) {
1798           // Not found, we can skip
1799           // Compute the skip value lazily
1800           if (skip == 0) {
1801             skip = 1;
1802             while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1803               ++skip;
1804             }
1805           }
1806           i += skip;
1807           break;
1808         }
1809         // Check if done searching
1810         if (++j == nsize) {
1811           // Yay
1812           return i - haystack;
1813         }
1814       }
1815     }
1816     return npos;
1817   }
1818
1819   size_type find(const value_type* s, size_type pos = 0) const {
1820     return find(s, pos, traits_type::length(s));
1821   }
1822
1823   size_type find (value_type c, size_type pos = 0) const {
1824     return find(&c, pos, 1);
1825   }
1826
1827   size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1828     return rfind(str.data(), pos, str.length());
1829   }
1830
1831   size_type rfind(const value_type* s, size_type pos, size_type n) const {
1832     if (n > length()) return npos;
1833     pos = std::min(pos, length() - n);
1834     if (n == 0) return pos;
1835
1836     const_iterator i(begin() + pos);
1837     for (; ; --i) {
1838       if (traits_type::eq(*i, *s)
1839           && traits_type::compare(&*i, s, n) == 0) {
1840         return i - begin();
1841       }
1842       if (i == begin()) break;
1843     }
1844     return npos;
1845   }
1846
1847   size_type rfind(const value_type* s, size_type pos = npos) const {
1848     return rfind(s, pos, traits_type::length(s));
1849   }
1850
1851   size_type rfind(value_type c, size_type pos = npos) const {
1852     return rfind(&c, pos, 1);
1853   }
1854
1855   size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1856     return find_first_of(str.data(), pos, str.length());
1857   }
1858
1859   size_type find_first_of(const value_type* s,
1860                           size_type pos, size_type n) const {
1861     if (pos > length() || n == 0) return npos;
1862     const_iterator i(begin() + pos),
1863       finish(end());
1864     for (; i != finish; ++i) {
1865       if (traits_type::find(s, n, *i) != 0) {
1866         return i - begin();
1867       }
1868     }
1869     return npos;
1870   }
1871
1872   size_type find_first_of(const value_type* s, size_type pos = 0) const {
1873     return find_first_of(s, pos, traits_type::length(s));
1874   }
1875
1876   size_type find_first_of(value_type c, size_type pos = 0) const {
1877     return find_first_of(&c, pos, 1);
1878   }
1879
1880   size_type find_last_of (const basic_fbstring& str,
1881                           size_type pos = npos) const {
1882     return find_last_of(str.data(), pos, str.length());
1883   }
1884
1885   size_type find_last_of (const value_type* s, size_type pos,
1886                           size_type n) const {
1887     if (!empty() && n > 0) {
1888       pos = std::min(pos, length() - 1);
1889       const_iterator i(begin() + pos);
1890       for (;; --i) {
1891         if (traits_type::find(s, n, *i) != 0) {
1892           return i - begin();
1893         }
1894         if (i == begin()) break;
1895       }
1896     }
1897     return npos;
1898   }
1899
1900   size_type find_last_of (const value_type* s,
1901                           size_type pos = npos) const {
1902     return find_last_of(s, pos, traits_type::length(s));
1903   }
1904
1905   size_type find_last_of (value_type c, size_type pos = npos) const {
1906     return find_last_of(&c, pos, 1);
1907   }
1908
1909   size_type find_first_not_of(const basic_fbstring& str,
1910                               size_type pos = 0) const {
1911     return find_first_not_of(str.data(), pos, str.size());
1912   }
1913
1914   size_type find_first_not_of(const value_type* s, size_type pos,
1915                               size_type n) const {
1916     if (pos < length()) {
1917       const_iterator
1918         i(begin() + pos),
1919         finish(end());
1920       for (; i != finish; ++i) {
1921         if (traits_type::find(s, n, *i) == 0) {
1922           return i - begin();
1923         }
1924       }
1925     }
1926     return npos;
1927   }
1928
1929   size_type find_first_not_of(const value_type* s,
1930                               size_type pos = 0) const {
1931     return find_first_not_of(s, pos, traits_type::length(s));
1932   }
1933
1934   size_type find_first_not_of(value_type c, size_type pos = 0) const {
1935     return find_first_not_of(&c, pos, 1);
1936   }
1937
1938   size_type find_last_not_of(const basic_fbstring& str,
1939                              size_type pos = npos) const {
1940     return find_last_not_of(str.data(), pos, str.length());
1941   }
1942
1943   size_type find_last_not_of(const value_type* s, size_type pos,
1944                              size_type n) const {
1945     if (!this->empty()) {
1946       pos = std::min(pos, size() - 1);
1947       const_iterator i(begin() + pos);
1948       for (;; --i) {
1949         if (traits_type::find(s, n, *i) == 0) {
1950           return i - begin();
1951         }
1952         if (i == begin()) break;
1953       }
1954     }
1955     return npos;
1956   }
1957
1958   size_type find_last_not_of(const value_type* s,
1959                              size_type pos = npos) const {
1960     return find_last_not_of(s, pos, traits_type::length(s));
1961   }
1962
1963   size_type find_last_not_of (value_type c, size_type pos = npos) const {
1964     return find_last_not_of(&c, pos, 1);
1965   }
1966
1967   basic_fbstring substr(size_type pos = 0, size_type n = npos) const& {
1968     enforce(pos <= size(), std::__throw_out_of_range, "");
1969     return basic_fbstring(data() + pos, std::min(n, size() - pos));
1970   }
1971
1972   basic_fbstring substr(size_type pos = 0, size_type n = npos) && {
1973     enforce(pos <= size(), std::__throw_out_of_range, "");
1974     erase(0, pos);
1975     if (n < size()) resize(n);
1976     return std::move(*this);
1977   }
1978
1979   int compare(const basic_fbstring& str) const {
1980     // FIX due to Goncalo N M de Carvalho July 18, 2005
1981     return compare(0, size(), str);
1982   }
1983
1984   int compare(size_type pos1, size_type n1,
1985               const basic_fbstring& str) const {
1986     return compare(pos1, n1, str.data(), str.size());
1987   }
1988
1989   int compare(size_type pos1, size_type n1,
1990               const value_type* s) const {
1991     return compare(pos1, n1, s, traits_type::length(s));
1992   }
1993
1994   int compare(size_type pos1, size_type n1,
1995               const value_type* s, size_type n2) const {
1996     enforce(pos1 <= size(), std::__throw_out_of_range, "");
1997     procrustes(n1, size() - pos1);
1998     // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1999     const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
2000     return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2001   }
2002
2003   int compare(size_type pos1, size_type n1,
2004               const basic_fbstring& str,
2005               size_type pos2, size_type n2) const {
2006     enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
2007     return compare(pos1, n1, str.data() + pos2,
2008                    std::min(n2, str.size() - pos2));
2009   }
2010
2011   // Code from Jean-Francois Bastien (03/26/2007)
2012   int compare(const value_type* s) const {
2013     // Could forward to compare(0, size(), s, traits_type::length(s))
2014     // but that does two extra checks
2015     const size_type n1(size()), n2(traits_type::length(s));
2016     const int r = traits_type::compare(data(), s, std::min(n1, n2));
2017     return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2018   }
2019
2020 private:
2021   // Data
2022   Storage store_;
2023 };
2024
2025 // non-member functions
2026 // C++11 21.4.8.1/1
2027 template <typename E, class T, class A, class S>
2028 inline
2029 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2030                                      const basic_fbstring<E, T, A, S>& rhs) {
2031
2032   basic_fbstring<E, T, A, S> result;
2033   result.reserve(lhs.size() + rhs.size());
2034   result.append(lhs).append(rhs);
2035   return std::move(result);
2036 }
2037
2038 // C++11 21.4.8.1/2
2039 template <typename E, class T, class A, class S>
2040 inline
2041 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2042                                      const basic_fbstring<E, T, A, S>& rhs) {
2043   return std::move(lhs.append(rhs));
2044 }
2045
2046 // C++11 21.4.8.1/3
2047 template <typename E, class T, class A, class S>
2048 inline
2049 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2050                                      basic_fbstring<E, T, A, S>&& rhs) {
2051   if (rhs.capacity() >= lhs.size() + rhs.size()) {
2052     // Good, at least we don't need to reallocate
2053     return std::move(rhs.insert(0, lhs));
2054   }
2055   // Meh, no go. Forward to operator+(const&, const&).
2056   auto const& rhsC = rhs;
2057   return lhs + rhsC;
2058 }
2059
2060 // C++11 21.4.8.1/4
2061 template <typename E, class T, class A, class S>
2062 inline
2063 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2064                                      basic_fbstring<E, T, A, S>&& rhs) {
2065   return std::move(lhs.append(rhs));
2066 }
2067
2068 // C++11 21.4.8.1/5
2069 template <typename E, class T, class A, class S>
2070 inline
2071 basic_fbstring<E, T, A, S> operator+(
2072   const E* lhs,
2073   const basic_fbstring<E, T, A, S>& rhs) {
2074   //
2075   basic_fbstring<E, T, A, S> result;
2076   const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2077   result.reserve(len + rhs.size());
2078   result.append(lhs, len).append(rhs);
2079   return result;
2080 }
2081
2082 // C++11 21.4.8.1/6
2083 template <typename E, class T, class A, class S>
2084 inline
2085 basic_fbstring<E, T, A, S> operator+(
2086   const E* lhs,
2087   basic_fbstring<E, T, A, S>&& rhs) {
2088   //
2089   const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2090   if (rhs.capacity() >= len + rhs.size()) {
2091     // Good, at least we don't need to reallocate
2092     rhs.insert(rhs.begin(), lhs, lhs + len);
2093     return rhs;
2094   }
2095   // Meh, no go. Do it by hand since we have len already.
2096   basic_fbstring<E, T, A, S> result;
2097   result.reserve(len + rhs.size());
2098   result.append(lhs, len).append(rhs);
2099   return result;
2100 }
2101
2102 // C++11 21.4.8.1/7
2103 template <typename E, class T, class A, class S>
2104 inline
2105 basic_fbstring<E, T, A, S> operator+(
2106   E lhs,
2107   const basic_fbstring<E, T, A, S>& rhs) {
2108
2109   basic_fbstring<E, T, A, S> result;
2110   result.reserve(1 + rhs.size());
2111   result.push_back(lhs);
2112   result.append(rhs);
2113   return result;
2114 }
2115
2116 // C++11 21.4.8.1/8
2117 template <typename E, class T, class A, class S>
2118 inline
2119 basic_fbstring<E, T, A, S> operator+(
2120   E lhs,
2121   basic_fbstring<E, T, A, S>&& rhs) {
2122   //
2123   if (rhs.capacity() > rhs.size()) {
2124     // Good, at least we don't need to reallocate
2125     rhs.insert(rhs.begin(), lhs);
2126     return rhs;
2127   }
2128   // Meh, no go. Forward to operator+(E, const&).
2129   auto const& rhsC = rhs;
2130   return lhs + rhsC;
2131 }
2132
2133 // C++11 21.4.8.1/9
2134 template <typename E, class T, class A, class S>
2135 inline
2136 basic_fbstring<E, T, A, S> operator+(
2137   const basic_fbstring<E, T, A, S>& lhs,
2138   const E* rhs) {
2139
2140   typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2141   typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2142
2143   basic_fbstring<E, T, A, S> result;
2144   const size_type len = traits_type::length(rhs);
2145   result.reserve(lhs.size() + len);
2146   result.append(lhs).append(rhs, len);
2147   return result;
2148 }
2149
2150 // C++11 21.4.8.1/10
2151 template <typename E, class T, class A, class S>
2152 inline
2153 basic_fbstring<E, T, A, S> operator+(
2154   basic_fbstring<E, T, A, S>&& lhs,
2155   const E* rhs) {
2156   //
2157   return std::move(lhs += rhs);
2158 }
2159
2160 // C++11 21.4.8.1/11
2161 template <typename E, class T, class A, class S>
2162 inline
2163 basic_fbstring<E, T, A, S> operator+(
2164   const basic_fbstring<E, T, A, S>& lhs,
2165   E rhs) {
2166
2167   basic_fbstring<E, T, A, S> result;
2168   result.reserve(lhs.size() + 1);
2169   result.append(lhs);
2170   result.push_back(rhs);
2171   return result;
2172 }
2173
2174 // C++11 21.4.8.1/12
2175 template <typename E, class T, class A, class S>
2176 inline
2177 basic_fbstring<E, T, A, S> operator+(
2178   basic_fbstring<E, T, A, S>&& lhs,
2179   E rhs) {
2180   //
2181   return std::move(lhs += rhs);
2182 }
2183
2184 template <typename E, class T, class A, class S>
2185 inline
2186 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2187                 const basic_fbstring<E, T, A, S>& rhs) {
2188   return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2189
2190 template <typename E, class T, class A, class S>
2191 inline
2192 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2193                 const basic_fbstring<E, T, A, S>& rhs) {
2194   return rhs == lhs; }
2195
2196 template <typename E, class T, class A, class S>
2197 inline
2198 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2199                 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2200   return lhs.compare(rhs) == 0; }
2201
2202 template <typename E, class T, class A, class S>
2203 inline
2204 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2205                 const basic_fbstring<E, T, A, S>& rhs) {
2206   return !(lhs == rhs); }
2207
2208 template <typename E, class T, class A, class S>
2209 inline
2210 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2211                 const basic_fbstring<E, T, A, S>& rhs) {
2212   return !(lhs == rhs); }
2213
2214 template <typename E, class T, class A, class S>
2215 inline
2216 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2217                 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2218   return !(lhs == rhs); }
2219
2220 template <typename E, class T, class A, class S>
2221 inline
2222 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2223                const basic_fbstring<E, T, A, S>& rhs) {
2224   return lhs.compare(rhs) < 0; }
2225
2226 template <typename E, class T, class A, class S>
2227 inline
2228 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2229                const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2230   return lhs.compare(rhs) < 0; }
2231
2232 template <typename E, class T, class A, class S>
2233 inline
2234 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2235                const basic_fbstring<E, T, A, S>& rhs) {
2236   return rhs.compare(lhs) > 0; }
2237
2238 template <typename E, class T, class A, class S>
2239 inline
2240 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2241                const basic_fbstring<E, T, A, S>& rhs) {
2242   return rhs < lhs; }
2243
2244 template <typename E, class T, class A, class S>
2245 inline
2246 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2247                const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2248   return rhs < lhs; }
2249
2250 template <typename E, class T, class A, class S>
2251 inline
2252 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2253                const basic_fbstring<E, T, A, S>& rhs) {
2254   return rhs < lhs; }
2255
2256 template <typename E, class T, class A, class S>
2257 inline
2258 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2259                 const basic_fbstring<E, T, A, S>& rhs) {
2260   return !(rhs < lhs); }
2261
2262 template <typename E, class T, class A, class S>
2263 inline
2264 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2265                 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2266   return !(rhs < lhs); }
2267
2268 template <typename E, class T, class A, class S>
2269 inline
2270 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2271                 const basic_fbstring<E, T, A, S>& rhs) {
2272   return !(rhs < lhs); }
2273
2274 template <typename E, class T, class A, class S>
2275 inline
2276 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2277                 const basic_fbstring<E, T, A, S>& rhs) {
2278   return !(lhs < rhs); }
2279
2280 template <typename E, class T, class A, class S>
2281 inline
2282 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2283                 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2284   return !(lhs < rhs); }
2285
2286 template <typename E, class T, class A, class S>
2287 inline
2288 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2289                 const basic_fbstring<E, T, A, S>& rhs) {
2290  return !(lhs < rhs);
2291 }
2292
2293 // C++11 21.4.8.8
2294 template <typename E, class T, class A, class S>
2295 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2296   lhs.swap(rhs);
2297 }
2298
2299 // TODO: make this faster.
2300 template <typename E, class T, class A, class S>
2301 inline
2302 std::basic_istream<
2303   typename basic_fbstring<E, T, A, S>::value_type,
2304   typename basic_fbstring<E, T, A, S>::traits_type>&
2305   operator>>(
2306     std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2307     typename basic_fbstring<E, T, A, S>::traits_type>& is,
2308     basic_fbstring<E, T, A, S>& str) {
2309   typename std::basic_istream<E, T>::sentry sentry(is);
2310   typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2311                              typename basic_fbstring<E, T, A, S>::traits_type>
2312                         __istream_type;
2313   typedef typename __istream_type::ios_base __ios_base;
2314   size_t extracted = 0;
2315   auto err = __ios_base::goodbit;
2316   if (sentry) {
2317     auto n = is.width();
2318     if (n <= 0) {
2319       n = str.max_size();
2320     }
2321     str.erase();
2322     for (auto got = is.rdbuf()->sgetc(); extracted != size_t(n); ++extracted) {
2323       if (got == T::eof()) {
2324         err |= __ios_base::eofbit;
2325         is.width(0);
2326         break;
2327       }
2328       if (isspace(got)) break;
2329       str.push_back(got);
2330       got = is.rdbuf()->snextc();
2331     }
2332   }
2333   if (!extracted) {
2334     err |= __ios_base::failbit;
2335   }
2336   if (err) {
2337     is.setstate(err);
2338   }
2339   return is;
2340 }
2341
2342 template <typename E, class T, class A, class S>
2343 inline
2344 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2345                    typename basic_fbstring<E, T, A, S>::traits_type>&
2346 operator<<(
2347   std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2348   typename basic_fbstring<E, T, A, S>::traits_type>& os,
2349     const basic_fbstring<E, T, A, S>& str) {
2350 #if _LIBCPP_VERSION
2351   typename std::basic_ostream<
2352     typename basic_fbstring<E, T, A, S>::value_type,
2353     typename basic_fbstring<E, T, A, S>::traits_type>::sentry __s(os);
2354   if (__s) {
2355     typedef std::ostreambuf_iterator<
2356       typename basic_fbstring<E, T, A, S>::value_type,
2357       typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
2358     size_t __len = str.size();
2359     bool __left =
2360       (os.flags() & std::ios_base::adjustfield) == std::ios_base::left;
2361     if (__pad_and_output(_Ip(os),
2362                          str.data(),
2363                          __left ? str.data() + __len : str.data(),
2364                          str.data() + __len,
2365                          os,
2366                          os.fill()).failed()) {
2367       os.setstate(std::ios_base::badbit | std::ios_base::failbit);
2368     }
2369   }
2370 #elif defined(_MSC_VER)
2371   // MSVC doesn't define __ostream_insert
2372   os.write(str.data(), str.size());
2373 #else
2374   std::__ostream_insert(os, str.data(), str.size());
2375 #endif
2376   return os;
2377 }
2378
2379 template <typename E1, class T, class A, class S>
2380 const typename basic_fbstring<E1, T, A, S>::size_type
2381 basic_fbstring<E1, T, A, S>::npos =
2382               static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2383
2384 #ifndef _LIBSTDCXX_FBSTRING
2385 // basic_string compatibility routines
2386
2387 template <typename E, class T, class A, class S>
2388 inline
2389 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2390                 const std::string& rhs) {
2391   return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2392 }
2393
2394 template <typename E, class T, class A, class S>
2395 inline
2396 bool operator==(const std::string& lhs,
2397                 const basic_fbstring<E, T, A, S>& rhs) {
2398   return rhs == lhs;
2399 }
2400
2401 template <typename E, class T, class A, class S>
2402 inline
2403 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2404                 const std::string& rhs) {
2405   return !(lhs == rhs);
2406 }
2407
2408 template <typename E, class T, class A, class S>
2409 inline
2410 bool operator!=(const std::string& lhs,
2411                 const basic_fbstring<E, T, A, S>& rhs) {
2412   return !(lhs == rhs);
2413 }
2414
2415 #if !defined(_LIBSTDCXX_FBSTRING)
2416 typedef basic_fbstring<char> fbstring;
2417 #endif
2418
2419 // fbstring is relocatable
2420 template <class T, class R, class A, class S>
2421 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2422
2423 #else
2424 _GLIBCXX_END_NAMESPACE_VERSION
2425 #endif
2426
2427 } // namespace folly
2428
2429 #ifndef _LIBSTDCXX_FBSTRING
2430
2431 // Hash functions to make fbstring usable with e.g. hash_map
2432 //
2433 // Handle interaction with different C++ standard libraries, which
2434 // expect these types to be in different namespaces.
2435
2436 #define FOLLY_FBSTRING_HASH1(T) \
2437   template <> \
2438   struct hash< ::folly::basic_fbstring<T> > { \
2439     size_t operator()(const ::folly::fbstring& s) const { \
2440       return ::folly::hash::fnv32_buf(s.data(), s.size()); \
2441     } \
2442   };
2443
2444 // The C++11 standard says that these four are defined
2445 #define FOLLY_FBSTRING_HASH \
2446   FOLLY_FBSTRING_HASH1(char) \
2447   FOLLY_FBSTRING_HASH1(char16_t) \
2448   FOLLY_FBSTRING_HASH1(char32_t) \
2449   FOLLY_FBSTRING_HASH1(wchar_t)
2450
2451 namespace std {
2452
2453 FOLLY_FBSTRING_HASH
2454
2455 }  // namespace std
2456
2457 #if FOLLY_HAVE_DEPRECATED_ASSOC
2458 #if defined(_GLIBCXX_SYMVER) && !defined(__BIONIC__)
2459 namespace __gnu_cxx {
2460
2461 FOLLY_FBSTRING_HASH
2462
2463 }  // namespace __gnu_cxx
2464 #endif // _GLIBCXX_SYMVER && !__BIONIC__
2465 #endif // FOLLY_HAVE_DEPRECATED_ASSOC
2466
2467 #undef FOLLY_FBSTRING_HASH
2468 #undef FOLLY_FBSTRING_HASH1
2469
2470 #endif // _LIBSTDCXX_FBSTRING
2471
2472 #pragma GCC diagnostic pop
2473
2474 #undef FBSTRING_DISABLE_SSO
2475 #undef FBSTRING_SANITIZE_ADDRESS
2476 #undef throw
2477 #undef FBSTRING_LIKELY
2478 #undef FBSTRING_UNLIKELY
2479
2480 #ifdef FOLLY_DEFINED_NDEBUG_FOR_FBSTRING
2481 #undef NDEBUG
2482 #undef FOLLY_DEFINED_NDEBUG_FOR_FBSTRING
2483 #endif // FOLLY_DEFINED_NDEBUG_FOR_FBSTRING