folly/FBString.h

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