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