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 <typename E,
1049           class T = std::char_traits<E>,
1050           class A = std::allocator<E>,
1051           class Storage = fbstring_core<E> >
1052 #endif
1053 class basic_fbstring {
1054   static void enforce(
1055       bool condition,
1056       void (*throw_exc)(const char*),
1057       const char* msg) {
1058     if (!condition) {
1059       throw_exc(msg);
1060     }
1061   }
1062
1063   bool isSane() const {
1064     return
1065       begin() <= end() &&
1066       empty() == (size() == 0) &&
1067       empty() == (begin() == end()) &&
1068       size() <= max_size() &&
1069       capacity() <= max_size() &&
1070       size() <= capacity() &&
1071       begin()[size()] == '\0';
1072   }
1073
1074   struct Invariant {
1075     Invariant& operator=(const Invariant&) = delete;
1076     explicit Invariant(const basic_fbstring& s) noexcept : s_(s) {
1077       FBSTRING_ASSERT(s_.isSane());
1078     }
1079     ~Invariant() noexcept {
1080       FBSTRING_ASSERT(s_.isSane());
1081     }
1082
1083    private:
1084     const basic_fbstring& s_;
1085   };
1086
1087  public:
1088   // types
1089   typedef T traits_type;
1090   typedef typename traits_type::char_type value_type;
1091   typedef A allocator_type;
1092   typedef typename A::size_type size_type;
1093   typedef typename A::difference_type difference_type;
1094
1095   typedef typename A::reference reference;
1096   typedef typename A::const_reference const_reference;
1097   typedef typename A::pointer pointer;
1098   typedef typename A::const_pointer const_pointer;
1099
1100   typedef E* iterator;
1101   typedef const E* const_iterator;
1102   typedef std::reverse_iterator<iterator
1103 #ifdef NO_ITERATOR_TRAITS
1104                                 , value_type
1105 #endif
1106                                 > reverse_iterator;
1107   typedef std::reverse_iterator<const_iterator
1108 #ifdef NO_ITERATOR_TRAITS
1109                                 , const value_type
1110 #endif
1111                                 > const_reverse_iterator;
1112
1113   static constexpr size_type npos = size_type(-1);
1114   typedef std::true_type IsRelocatable;
1115
1116 private:
1117   static void procrustes(size_type& n, size_type nmax) {
1118     if (n > nmax) {
1119       n = nmax;
1120     }
1121   }
1122
1123   static size_type traitsLength(const value_type* s);
1124
1125 public:
1126   // C++11 21.4.2 construct/copy/destroy
1127
1128   // Note: while the following two constructors can be (and previously were)
1129   // collapsed into one constructor written this way:
1130   //
1131   //   explicit basic_fbstring(const A& a = A()) noexcept { }
1132   //
1133   // This can cause Clang (at least version 3.7) to fail with the error:
1134   //   "chosen constructor is explicit in copy-initialization ...
1135   //   in implicit initialization of field '(x)' with omitted initializer"
1136   //
1137   // if used in a struct which is default-initialized.  Hence the split into
1138   // these two separate constructors.
1139
1140   basic_fbstring() noexcept : basic_fbstring(A()) {
1141   }
1142
1143   explicit basic_fbstring(const A&) noexcept {
1144   }
1145
1146   basic_fbstring(const basic_fbstring& str)
1147       : store_(str.store_) {
1148   }
1149
1150   // Move constructor
1151   basic_fbstring(basic_fbstring&& goner) noexcept
1152       : store_(std::move(goner.store_)) {
1153   }
1154
1155 #ifndef _LIBSTDCXX_FBSTRING
1156   // This is defined for compatibility with std::string
1157   template <typename A2>
1158   /* implicit */ basic_fbstring(const std::basic_string<E, T, A2>& str)
1159       : store_(str.data(), str.size()) {}
1160 #endif
1161
1162   basic_fbstring(const basic_fbstring& str,
1163                  size_type pos,
1164                  size_type n = npos,
1165                  const A& /* a */ = A()) {
1166     assign(str, pos, n);
1167   }
1168
1169   FOLLY_MALLOC_NOINLINE
1170   /* implicit */ basic_fbstring(const value_type* s, const A& /*a*/ = A())
1171       : store_(s, traitsLength(s)) {}
1172
1173   FOLLY_MALLOC_NOINLINE
1174   basic_fbstring(const value_type* s, size_type n, const A& /*a*/ = A())
1175       : store_(s, n) {
1176   }
1177
1178   FOLLY_MALLOC_NOINLINE
1179   basic_fbstring(size_type n, value_type c, const A& /*a*/ = A()) {
1180     auto const pData = store_.expandNoinit(n);
1181     fbstring_detail::podFill(pData, pData + n, c);
1182   }
1183
1184   template <class InIt>
1185   FOLLY_MALLOC_NOINLINE basic_fbstring(
1186       InIt begin,
1187       InIt end,
1188       typename std::enable_if<
1189           !std::is_same<InIt, value_type*>::value,
1190           const A>::type& /*a*/ = A()) {
1191     assign(begin, end);
1192   }
1193
1194   // Specialization for const char*, const char*
1195   FOLLY_MALLOC_NOINLINE
1196   basic_fbstring(const value_type* b, const value_type* e, const A& /*a*/ = A())
1197       : store_(b, size_type(e - b)) {
1198   }
1199
1200   // Nonstandard constructor
1201   basic_fbstring(value_type *s, size_type n, size_type c,
1202                  AcquireMallocatedString a)
1203       : store_(s, n, c, a) {
1204   }
1205
1206   // Construction from initialization list
1207   FOLLY_MALLOC_NOINLINE
1208   basic_fbstring(std::initializer_list<value_type> il) {
1209     assign(il.begin(), il.end());
1210   }
1211
1212   ~basic_fbstring() noexcept {}
1213
1214   basic_fbstring& operator=(const basic_fbstring& lhs);
1215
1216   // Move assignment
1217   basic_fbstring& operator=(basic_fbstring&& goner) noexcept;
1218
1219 #ifndef _LIBSTDCXX_FBSTRING
1220   // Compatibility with std::string
1221   template <typename A2>
1222   basic_fbstring& operator=(const std::basic_string<E, T, A2>& rhs) {
1223     return assign(rhs.data(), rhs.size());
1224   }
1225
1226   // Compatibility with std::string
1227   std::basic_string<E, T, A> toStdString() const {
1228     return std::basic_string<E, T, A>(data(), size());
1229   }
1230 #else
1231   // A lot of code in fbcode still uses this method, so keep it here for now.
1232   const basic_fbstring& toStdString() const {
1233     return *this;
1234   }
1235 #endif
1236
1237   basic_fbstring& operator=(const value_type* s) {
1238     return assign(s);
1239   }
1240
1241   // This actually goes directly against the C++ spec, but the
1242   // value_type overload is dangerous, so we're explicitly deleting
1243   // any overloads of operator= that could implicitly convert to
1244   // value_type.
1245   // Note that we do need to explicitly specify the template types because
1246   // otherwise MSVC 2017 will aggressively pre-resolve value_type to
1247   // traits_type::char_type, which won't compare as equal when determining
1248   // which overload the implementation is referring to.
1249   // Also note that MSVC 2015 Update 3 requires us to explicitly specify the
1250   // namespace in-which to search for basic_fbstring, otherwise it tries to
1251   // look for basic_fbstring::basic_fbstring, which is just plain wrong.
1252   template <typename TP>
1253   typename std::enable_if<
1254       std::is_same<
1255           typename std::decay<TP>::type,
1256           typename folly::basic_fbstring<E, T, A, Storage>::value_type>::value,
1257       basic_fbstring<E, T, A, Storage>&>::type
1258   operator=(TP c);
1259
1260   basic_fbstring& operator=(std::initializer_list<value_type> il) {
1261     return assign(il.begin(), il.end());
1262   }
1263
1264   // C++11 21.4.3 iterators:
1265   iterator begin() {
1266     return store_.mutableData();
1267   }
1268
1269   const_iterator begin() const {
1270     return store_.data();
1271   }
1272
1273   const_iterator cbegin() const {
1274     return begin();
1275   }
1276
1277   iterator end() {
1278     return store_.mutableData() + store_.size();
1279   }
1280
1281   const_iterator end() const {
1282     return store_.data() + store_.size();
1283   }
1284
1285   const_iterator cend() const { return end(); }
1286
1287   reverse_iterator rbegin() {
1288     return reverse_iterator(end());
1289   }
1290
1291   const_reverse_iterator rbegin() const {
1292     return const_reverse_iterator(end());
1293   }
1294
1295   const_reverse_iterator crbegin() const { return rbegin(); }
1296
1297   reverse_iterator rend() {
1298     return reverse_iterator(begin());
1299   }
1300
1301   const_reverse_iterator rend() const {
1302     return const_reverse_iterator(begin());
1303   }
1304
1305   const_reverse_iterator crend() const { return rend(); }
1306
1307   // Added by C++11
1308   // C++11 21.4.5, element access:
1309   const value_type& front() const { return *begin(); }
1310   const value_type& back() const {
1311     FBSTRING_ASSERT(!empty());
1312     // Should be begin()[size() - 1], but that branches twice
1313     return *(end() - 1);
1314   }
1315   value_type& front() { return *begin(); }
1316   value_type& back() {
1317     FBSTRING_ASSERT(!empty());
1318     // Should be begin()[size() - 1], but that branches twice
1319     return *(end() - 1);
1320   }
1321   void pop_back() {
1322     FBSTRING_ASSERT(!empty());
1323     store_.shrink(1);
1324   }
1325
1326   // C++11 21.4.4 capacity:
1327   size_type size() const { return store_.size(); }
1328
1329   size_type length() const { return size(); }
1330
1331   size_type max_size() const {
1332     return std::numeric_limits<size_type>::max();
1333   }
1334
1335   void resize(size_type n, value_type c = value_type());
1336
1337   size_type capacity() const { return store_.capacity(); }
1338
1339   void reserve(size_type res_arg = 0) {
1340     enforce(res_arg <= max_size(), std::__throw_length_error, "");
1341     store_.reserve(res_arg);
1342   }
1343
1344   void shrink_to_fit() {
1345     // Shrink only if slack memory is sufficiently large
1346     if (capacity() < size() * 3 / 2) {
1347       return;
1348     }
1349     basic_fbstring(cbegin(), cend()).swap(*this);
1350   }
1351
1352   void clear() { resize(0); }
1353
1354   bool empty() const { return size() == 0; }
1355
1356   // C++11 21.4.5 element access:
1357   const_reference operator[](size_type pos) const {
1358     return *(begin() + pos);
1359   }
1360
1361   reference operator[](size_type pos) {
1362     return *(begin() + pos);
1363   }
1364
1365   const_reference at(size_type n) const {
1366     enforce(n <= size(), std::__throw_out_of_range, "");
1367     return (*this)[n];
1368   }
1369
1370   reference at(size_type n) {
1371     enforce(n < size(), std::__throw_out_of_range, "");
1372     return (*this)[n];
1373   }
1374
1375   // C++11 21.4.6 modifiers:
1376   basic_fbstring& operator+=(const basic_fbstring& str) {
1377     return append(str);
1378   }
1379
1380   basic_fbstring& operator+=(const value_type* s) {
1381     return append(s);
1382   }
1383
1384   basic_fbstring& operator+=(const value_type c) {
1385     push_back(c);
1386     return *this;
1387   }
1388
1389   basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1390     append(il);
1391     return *this;
1392   }
1393
1394   basic_fbstring& append(const basic_fbstring& str);
1395
1396   basic_fbstring&
1397   append(const basic_fbstring& str, const size_type pos, size_type n);
1398
1399   basic_fbstring& append(const value_type* s, size_type n);
1400
1401   basic_fbstring& append(const value_type* s) {
1402     return append(s, traitsLength(s));
1403   }
1404
1405   basic_fbstring& append(size_type n, value_type c);
1406
1407   template<class InputIterator>
1408   basic_fbstring& append(InputIterator first, InputIterator last) {
1409     insert(end(), first, last);
1410     return *this;
1411   }
1412
1413   basic_fbstring& append(std::initializer_list<value_type> il) {
1414     return append(il.begin(), il.end());
1415   }
1416
1417   void push_back(const value_type c) {             // primitive
1418     store_.push_back(c);
1419   }
1420
1421   basic_fbstring& assign(const basic_fbstring& str) {
1422     if (&str == this) return *this;
1423     return assign(str.data(), str.size());
1424   }
1425
1426   basic_fbstring& assign(basic_fbstring&& str) {
1427     return *this = std::move(str);
1428   }
1429
1430   basic_fbstring&
1431   assign(const basic_fbstring& str, const size_type pos, size_type n);
1432
1433   basic_fbstring& assign(const value_type* s, const size_type n);
1434
1435   basic_fbstring& assign(const value_type* s) {
1436     return assign(s, traitsLength(s));
1437   }
1438
1439   basic_fbstring& assign(std::initializer_list<value_type> il) {
1440     return assign(il.begin(), il.end());
1441   }
1442
1443   template <class ItOrLength, class ItOrChar>
1444   basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1445     return replace(begin(), end(), first_or_n, last_or_c);
1446   }
1447
1448   basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1449     return insert(pos1, str.data(), str.size());
1450   }
1451
1452   basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1453                          size_type pos2, size_type n) {
1454     enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1455     procrustes(n, str.length() - pos2);
1456     return insert(pos1, str.data() + pos2, n);
1457   }
1458
1459   basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1460     enforce(pos <= length(), std::__throw_out_of_range, "");
1461     insert(begin() + pos, s, s + n);
1462     return *this;
1463   }
1464
1465   basic_fbstring& insert(size_type pos, const value_type* s) {
1466     return insert(pos, s, traitsLength(s));
1467   }
1468
1469   basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1470     enforce(pos <= length(), std::__throw_out_of_range, "");
1471     insert(begin() + pos, n, c);
1472     return *this;
1473   }
1474
1475   iterator insert(const_iterator p, const value_type c) {
1476     const size_type pos = p - cbegin();
1477     insert(p, 1, c);
1478     return begin() + pos;
1479   }
1480
1481 #ifndef _LIBSTDCXX_FBSTRING
1482  private:
1483   typedef std::basic_istream<value_type, traits_type> istream_type;
1484   istream_type& getlineImpl(istream_type& is, value_type delim);
1485
1486  public:
1487   friend inline istream_type& getline(istream_type& is,
1488                                       basic_fbstring& str,
1489                                       value_type delim) {
1490     return str.getlineImpl(is, delim);
1491   }
1492
1493   friend inline istream_type& getline(istream_type& is, basic_fbstring& str) {
1494     return getline(is, str, '\n');
1495   }
1496 #endif
1497
1498 private:
1499  iterator
1500  insertImplDiscr(const_iterator i, size_type n, value_type c, std::true_type);
1501
1502  template <class InputIter>
1503  iterator
1504  insertImplDiscr(const_iterator i, InputIter b, InputIter e, std::false_type);
1505
1506  template <class FwdIterator>
1507  iterator insertImpl(
1508      const_iterator i,
1509      FwdIterator s1,
1510      FwdIterator s2,
1511      std::forward_iterator_tag);
1512
1513  template <class InputIterator>
1514  iterator insertImpl(
1515      const_iterator i,
1516      InputIterator b,
1517      InputIterator e,
1518      std::input_iterator_tag);
1519
1520 public:
1521   template <class ItOrLength, class ItOrChar>
1522   iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1523     using Sel = std::integral_constant<
1524         bool,
1525         std::numeric_limits<ItOrLength>::is_specialized>;
1526     return insertImplDiscr(p, first_or_n, last_or_c, Sel());
1527   }
1528
1529   iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1530     return insert(p, il.begin(), il.end());
1531   }
1532
1533   basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1534     Invariant checker(*this);
1535
1536     enforce(pos <= length(), std::__throw_out_of_range, "");
1537     procrustes(n, length() - pos);
1538     std::copy(begin() + pos + n, end(), begin() + pos);
1539     resize(length() - n);
1540     return *this;
1541   }
1542
1543   iterator erase(iterator position) {
1544     const size_type pos(position - begin());
1545     enforce(pos <= size(), std::__throw_out_of_range, "");
1546     erase(pos, 1);
1547     return begin() + pos;
1548   }
1549
1550   iterator erase(iterator first, iterator last) {
1551     const size_type pos(first - begin());
1552     erase(pos, last - first);
1553     return begin() + pos;
1554   }
1555
1556   // Replaces at most n1 chars of *this, starting with pos1 with the
1557   // content of str
1558   basic_fbstring& replace(size_type pos1, size_type n1,
1559                           const basic_fbstring& str) {
1560     return replace(pos1, n1, str.data(), str.size());
1561   }
1562
1563   // Replaces at most n1 chars of *this, starting with pos1,
1564   // with at most n2 chars of str starting with pos2
1565   basic_fbstring& replace(size_type pos1, size_type n1,
1566                           const basic_fbstring& str,
1567                           size_type pos2, size_type n2) {
1568     enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1569     return replace(pos1, n1, str.data() + pos2,
1570                    std::min(n2, str.size() - pos2));
1571   }
1572
1573   // Replaces at most n1 chars of *this, starting with pos, with chars from s
1574   basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1575     return replace(pos, n1, s, traitsLength(s));
1576   }
1577
1578   // Replaces at most n1 chars of *this, starting with pos, with n2
1579   // occurrences of c
1580   //
1581   // consolidated with
1582   //
1583   // Replaces at most n1 chars of *this, starting with pos, with at
1584   // most n2 chars of str.  str must have at least n2 chars.
1585   template <class StrOrLength, class NumOrChar>
1586   basic_fbstring& replace(size_type pos, size_type n1,
1587                           StrOrLength s_or_n2, NumOrChar n_or_c) {
1588     Invariant checker(*this);
1589
1590     enforce(pos <= size(), std::__throw_out_of_range, "");
1591     procrustes(n1, length() - pos);
1592     const iterator b = begin() + pos;
1593     return replace(b, b + n1, s_or_n2, n_or_c);
1594   }
1595
1596   basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1597     return replace(i1, i2, str.data(), str.length());
1598   }
1599
1600   basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1601     return replace(i1, i2, s, traitsLength(s));
1602   }
1603
1604 private:
1605  basic_fbstring& replaceImplDiscr(
1606      iterator i1,
1607      iterator i2,
1608      const value_type* s,
1609      size_type n,
1610      std::integral_constant<int, 2>);
1611
1612  basic_fbstring& replaceImplDiscr(
1613      iterator i1,
1614      iterator i2,
1615      size_type n2,
1616      value_type c,
1617      std::integral_constant<int, 1>);
1618
1619  template <class InputIter>
1620  basic_fbstring& replaceImplDiscr(
1621      iterator i1,
1622      iterator i2,
1623      InputIter b,
1624      InputIter e,
1625      std::integral_constant<int, 0>);
1626
1627 private:
1628  template <class FwdIterator>
1629  bool replaceAliased(iterator /* i1 */,
1630                      iterator /* i2 */,
1631                      FwdIterator /* s1 */,
1632                      FwdIterator /* s2 */,
1633                      std::false_type) {
1634     return false;
1635   }
1636
1637   template <class FwdIterator>
1638   bool replaceAliased(
1639       iterator i1,
1640       iterator i2,
1641       FwdIterator s1,
1642       FwdIterator s2,
1643       std::true_type);
1644
1645   template <class FwdIterator>
1646   void replaceImpl(
1647       iterator i1,
1648       iterator i2,
1649       FwdIterator s1,
1650       FwdIterator s2,
1651       std::forward_iterator_tag);
1652
1653   template <class InputIterator>
1654   void replaceImpl(
1655       iterator i1,
1656       iterator i2,
1657       InputIterator b,
1658       InputIterator e,
1659       std::input_iterator_tag);
1660
1661  public:
1662   template <class T1, class T2>
1663   basic_fbstring& replace(iterator i1, iterator i2,
1664                           T1 first_or_n_or_s, T2 last_or_c_or_n) {
1665     constexpr bool num1 = std::numeric_limits<T1>::is_specialized,
1666                    num2 = std::numeric_limits<T2>::is_specialized;
1667     using Sel =
1668         std::integral_constant<int, num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>;
1669     return replaceImplDiscr(i1, i2, first_or_n_or_s, last_or_c_or_n, Sel());
1670   }
1671
1672   size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1673     enforce(pos <= size(), std::__throw_out_of_range, "");
1674     procrustes(n, size() - pos);
1675
1676     if (n != 0) {
1677       fbstring_detail::podCopy(data() + pos, data() + pos + n, s);
1678     }
1679     return n;
1680   }
1681
1682   void swap(basic_fbstring& rhs) {
1683     store_.swap(rhs.store_);
1684   }
1685
1686   const value_type* c_str() const {
1687     return store_.c_str();
1688   }
1689
1690   const value_type* data() const { return c_str(); }
1691
1692   allocator_type get_allocator() const {
1693     return allocator_type();
1694   }
1695
1696   size_type find(const basic_fbstring& str, size_type pos = 0) const {
1697     return find(str.data(), pos, str.length());
1698   }
1699
1700   size_type find(const value_type* needle, size_type pos, size_type nsize)
1701       const;
1702
1703   size_type find(const value_type* s, size_type pos = 0) const {
1704     return find(s, pos, traitsLength(s));
1705   }
1706
1707   size_type find (value_type c, size_type pos = 0) const {
1708     return find(&c, pos, 1);
1709   }
1710
1711   size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1712     return rfind(str.data(), pos, str.length());
1713   }
1714
1715   size_type rfind(const value_type* s, size_type pos, size_type n) const;
1716
1717   size_type rfind(const value_type* s, size_type pos = npos) const {
1718     return rfind(s, pos, traitsLength(s));
1719   }
1720
1721   size_type rfind(value_type c, size_type pos = npos) const {
1722     return rfind(&c, pos, 1);
1723   }
1724
1725   size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1726     return find_first_of(str.data(), pos, str.length());
1727   }
1728
1729   size_type find_first_of(const value_type* s, size_type pos, size_type n)
1730       const;
1731
1732   size_type find_first_of(const value_type* s, size_type pos = 0) const {
1733     return find_first_of(s, pos, traitsLength(s));
1734   }
1735
1736   size_type find_first_of(value_type c, size_type pos = 0) const {
1737     return find_first_of(&c, pos, 1);
1738   }
1739
1740   size_type find_last_of(const basic_fbstring& str, size_type pos = npos)
1741       const {
1742     return find_last_of(str.data(), pos, str.length());
1743   }
1744
1745   size_type find_last_of(const value_type* s, size_type pos, size_type n) const;
1746
1747   size_type find_last_of (const value_type* s,
1748                           size_type pos = npos) const {
1749     return find_last_of(s, pos, traitsLength(s));
1750   }
1751
1752   size_type find_last_of (value_type c, size_type pos = npos) const {
1753     return find_last_of(&c, pos, 1);
1754   }
1755
1756   size_type find_first_not_of(const basic_fbstring& str,
1757                               size_type pos = 0) const {
1758     return find_first_not_of(str.data(), pos, str.size());
1759   }
1760
1761   size_type find_first_not_of(const value_type* s, size_type pos, size_type n)
1762       const;
1763
1764   size_type find_first_not_of(const value_type* s,
1765                               size_type pos = 0) const {
1766     return find_first_not_of(s, pos, traitsLength(s));
1767   }
1768
1769   size_type find_first_not_of(value_type c, size_type pos = 0) const {
1770     return find_first_not_of(&c, pos, 1);
1771   }
1772
1773   size_type find_last_not_of(const basic_fbstring& str,
1774                              size_type pos = npos) const {
1775     return find_last_not_of(str.data(), pos, str.length());
1776   }
1777
1778   size_type find_last_not_of(const value_type* s, size_type pos, size_type n)
1779       const;
1780
1781   size_type find_last_not_of(const value_type* s,
1782                              size_type pos = npos) const {
1783     return find_last_not_of(s, pos, traitsLength(s));
1784   }
1785
1786   size_type find_last_not_of (value_type c, size_type pos = npos) const {
1787     return find_last_not_of(&c, pos, 1);
1788   }
1789
1790   basic_fbstring substr(size_type pos = 0, size_type n = npos) const& {
1791     enforce(pos <= size(), std::__throw_out_of_range, "");
1792     return basic_fbstring(data() + pos, std::min(n, size() - pos));
1793   }
1794
1795   basic_fbstring substr(size_type pos = 0, size_type n = npos) && {
1796     enforce(pos <= size(), std::__throw_out_of_range, "");
1797     erase(0, pos);
1798     if (n < size()) {
1799       resize(n);
1800     }
1801     return std::move(*this);
1802   }
1803
1804   int compare(const basic_fbstring& str) const {
1805     // FIX due to Goncalo N M de Carvalho July 18, 2005
1806     return compare(0, size(), str);
1807   }
1808
1809   int compare(size_type pos1, size_type n1,
1810               const basic_fbstring& str) const {
1811     return compare(pos1, n1, str.data(), str.size());
1812   }
1813
1814   int compare(size_type pos1, size_type n1,
1815               const value_type* s) const {
1816     return compare(pos1, n1, s, traitsLength(s));
1817   }
1818
1819   int compare(size_type pos1, size_type n1,
1820               const value_type* s, size_type n2) const {
1821     enforce(pos1 <= size(), std::__throw_out_of_range, "");
1822     procrustes(n1, size() - pos1);
1823     // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1824     const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1825     return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1826   }
1827
1828   int compare(size_type pos1, size_type n1,
1829               const basic_fbstring& str,
1830               size_type pos2, size_type n2) const {
1831     enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
1832     return compare(pos1, n1, str.data() + pos2,
1833                    std::min(n2, str.size() - pos2));
1834   }
1835
1836   // Code from Jean-Francois Bastien (03/26/2007)
1837   int compare(const value_type* s) const {
1838     // Could forward to compare(0, size(), s, traitsLength(s))
1839     // but that does two extra checks
1840     const size_type n1(size()), n2(traitsLength(s));
1841     const int r = traits_type::compare(data(), s, std::min(n1, n2));
1842     return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1843   }
1844
1845 private:
1846   // Data
1847   Storage store_;
1848 };
1849
1850 template <typename E, class T, class A, class S>
1851 FOLLY_MALLOC_NOINLINE inline typename basic_fbstring<E, T, A, S>::size_type
1852 basic_fbstring<E, T, A, S>::traitsLength(const value_type* s) {
1853   return s ? traits_type::length(s)
1854            : (std::__throw_logic_error(
1855                   "basic_fbstring: null pointer initializer not valid"),
1856               0);
1857 }
1858
1859 template <typename E, class T, class A, class S>
1860 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1861     const basic_fbstring& lhs) {
1862   Invariant checker(*this);
1863
1864   if (FBSTRING_UNLIKELY(&lhs == this)) {
1865     return *this;
1866   }
1867
1868   return assign(lhs.data(), lhs.size());
1869 }
1870
1871 // Move assignment
1872 template <typename E, class T, class A, class S>
1873 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1874     basic_fbstring&& goner) noexcept {
1875   if (FBSTRING_UNLIKELY(&goner == this)) {
1876     // Compatibility with std::basic_string<>,
1877     // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1878     return *this;
1879   }
1880   // No need of this anymore
1881   this->~basic_fbstring();
1882   // Move the goner into this
1883   new (&store_) S(std::move(goner.store_));
1884   return *this;
1885 }
1886
1887 template <typename E, class T, class A, class S>
1888 template <typename TP>
1889 inline typename std::enable_if<
1890     std::is_same<
1891         typename std::decay<TP>::type,
1892         typename basic_fbstring<E, T, A, S>::value_type>::value,
1893     basic_fbstring<E, T, A, S>&>::type
1894 basic_fbstring<E, T, A, S>::operator=(TP c) {
1895   Invariant checker(*this);
1896
1897   if (empty()) {
1898     store_.expandNoinit(1);
1899   } else if (store_.isShared()) {
1900     basic_fbstring(1, c).swap(*this);
1901     return *this;
1902   } else {
1903     store_.shrink(size() - 1);
1904   }
1905   front() = c;
1906   return *this;
1907 }
1908
1909 template <typename E, class T, class A, class S>
1910 inline void basic_fbstring<E, T, A, S>::resize(
1911     const size_type n, const value_type c /*= value_type()*/) {
1912   Invariant checker(*this);
1913
1914   auto size = this->size();
1915   if (n <= size) {
1916     store_.shrink(size - n);
1917   } else {
1918     auto const delta = n - size;
1919     auto pData = store_.expandNoinit(delta);
1920     fbstring_detail::podFill(pData, pData + delta, c);
1921   }
1922   FBSTRING_ASSERT(this->size() == n);
1923 }
1924
1925 template <typename E, class T, class A, class S>
1926 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1927     const basic_fbstring& str) {
1928 #ifndef NDEBUG
1929   auto desiredSize = size() + str.size();
1930 #endif
1931   append(str.data(), str.size());
1932   FBSTRING_ASSERT(size() == desiredSize);
1933   return *this;
1934 }
1935
1936 template <typename E, class T, class A, class S>
1937 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1938     const basic_fbstring& str, const size_type pos, size_type n) {
1939   const size_type sz = str.size();
1940   enforce(pos <= sz, std::__throw_out_of_range, "");
1941   procrustes(n, sz - pos);
1942   return append(str.data() + pos, n);
1943 }
1944
1945 template <typename E, class T, class A, class S>
1946 FOLLY_MALLOC_NOINLINE inline basic_fbstring<E, T, A, S>&
1947 basic_fbstring<E, T, A, S>::append(const value_type* s, size_type n) {
1948   Invariant checker(*this);
1949
1950   if (FBSTRING_UNLIKELY(!n)) {
1951     // Unlikely but must be done
1952     return *this;
1953   }
1954   auto const oldSize = size();
1955   auto const oldData = data();
1956   auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
1957
1958   // Check for aliasing (rare). We could use "<=" here but in theory
1959   // those do not work for pointers unless the pointers point to
1960   // elements in the same array. For that reason we use
1961   // std::less_equal, which is guaranteed to offer a total order
1962   // over pointers. See discussion at http://goo.gl/Cy2ya for more
1963   // info.
1964   std::less_equal<const value_type*> le;
1965   if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1966     FBSTRING_ASSERT(le(s + n, oldData + oldSize));
1967     // expandNoinit() could have moved the storage, restore the source.
1968     s = data() + (s - oldData);
1969     fbstring_detail::podMove(s, s + n, pData);
1970   } else {
1971     fbstring_detail::podCopy(s, s + n, pData);
1972   }
1973
1974   FBSTRING_ASSERT(size() == oldSize + n);
1975   return *this;
1976 }
1977
1978 template <typename E, class T, class A, class S>
1979 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1980     size_type n, value_type c) {
1981   Invariant checker(*this);
1982   auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
1983   fbstring_detail::podFill(pData, pData + n, c);
1984   return *this;
1985 }
1986
1987 template <typename E, class T, class A, class S>
1988 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::assign(
1989     const basic_fbstring& str, const size_type pos, size_type n) {
1990   const size_type sz = str.size();
1991   enforce(pos <= sz, std::__throw_out_of_range, "");
1992   procrustes(n, sz - pos);
1993   return assign(str.data() + pos, n);
1994 }
1995
1996 template <typename E, class T, class A, class S>
1997 FOLLY_MALLOC_NOINLINE inline basic_fbstring<E, T, A, S>&
1998 basic_fbstring<E, T, A, S>::assign(const value_type* s, const size_type n) {
1999   Invariant checker(*this);
2000
2001   if (n == 0) {
2002     resize(0);
2003   } else if (size() >= n) {
2004     // s can alias this, we need to use podMove.
2005     fbstring_detail::podMove(s, s + n, store_.mutableData());
2006     store_.shrink(size() - n);
2007     FBSTRING_ASSERT(size() == n);
2008   } else {
2009     // If n is larger than size(), s cannot alias this string's
2010     // storage.
2011     resize(0);
2012     // Do not use exponential growth here: assign() should be tight,
2013     // to mirror the behavior of the equivalent constructor.
2014     fbstring_detail::podCopy(s, s + n, store_.expandNoinit(n));
2015   }
2016
2017   FBSTRING_ASSERT(size() == n);
2018   return *this;
2019 }
2020
2021 #ifndef _LIBSTDCXX_FBSTRING
2022 template <typename E, class T, class A, class S>
2023 inline typename basic_fbstring<E, T, A, S>::istream_type&
2024 basic_fbstring<E, T, A, S>::getlineImpl(istream_type & is, value_type delim) {
2025   Invariant checker(*this);
2026
2027   clear();
2028   size_t size = 0;
2029   while (true) {
2030     size_t avail = capacity() - size;
2031     // fbstring has 1 byte extra capacity for the null terminator,
2032     // and getline null-terminates the read string.
2033     is.getline(store_.expandNoinit(avail), avail + 1, delim);
2034     size += is.gcount();
2035
2036     if (is.bad() || is.eof() || !is.fail()) {
2037       // Done by either failure, end of file, or normal read.
2038       if (!is.bad() && !is.eof()) {
2039         --size; // gcount() also accounts for the delimiter.
2040       }
2041       resize(size);
2042       break;
2043     }
2044
2045     FBSTRING_ASSERT(size == this->size());
2046     FBSTRING_ASSERT(size == capacity());
2047     // Start at minimum allocation 63 + terminator = 64.
2048     reserve(std::max<size_t>(63, 3 * size / 2));
2049     // Clear the error so we can continue reading.
2050     is.clear();
2051   }
2052   return is;
2053 }
2054 #endif
2055
2056 template <typename E, class T, class A, class S>
2057 inline typename basic_fbstring<E, T, A, S>::size_type
2058 basic_fbstring<E, T, A, S>::find(
2059     const value_type* needle, const size_type pos, const size_type nsize)
2060     const {
2061   auto const size = this->size();
2062   // nsize + pos can overflow (eg pos == npos), guard against that by checking
2063   // that nsize + pos does not wrap around.
2064   if (nsize + pos > size || nsize + pos < pos) {
2065     return npos;
2066   }
2067
2068   if (nsize == 0) {
2069     return pos;
2070   }
2071   // Don't use std::search, use a Boyer-Moore-like trick by comparing
2072   // the last characters first
2073   auto const haystack = data();
2074   auto const nsize_1 = nsize - 1;
2075   auto const lastNeedle = needle[nsize_1];
2076
2077   // Boyer-Moore skip value for the last char in the needle. Zero is
2078   // not a valid value; skip will be computed the first time it's
2079   // needed.
2080   size_type skip = 0;
2081
2082   const E* i = haystack + pos;
2083   auto iEnd = haystack + size - nsize_1;
2084
2085   while (i < iEnd) {
2086     // Boyer-Moore: match the last element in the needle
2087     while (i[nsize_1] != lastNeedle) {
2088       if (++i == iEnd) {
2089         // not found
2090         return npos;
2091       }
2092     }
2093     // Here we know that the last char matches
2094     // Continue in pedestrian mode
2095     for (size_t j = 0;;) {
2096       FBSTRING_ASSERT(j < nsize);
2097       if (i[j] != needle[j]) {
2098         // Not found, we can skip
2099         // Compute the skip value lazily
2100         if (skip == 0) {
2101           skip = 1;
2102           while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
2103             ++skip;
2104           }
2105         }
2106         i += skip;
2107         break;
2108       }
2109       // Check if done searching
2110       if (++j == nsize) {
2111         // Yay
2112         return i - haystack;
2113       }
2114     }
2115   }
2116   return npos;
2117 }
2118
2119 template <typename E, class T, class A, class S>
2120 inline typename basic_fbstring<E, T, A, S>::iterator
2121 basic_fbstring<E, T, A, S>::insertImplDiscr(
2122     const_iterator i, size_type n, value_type c, std::true_type) {
2123   Invariant checker(*this);
2124
2125   FBSTRING_ASSERT(i >= cbegin() && i <= cend());
2126   const size_type pos = i - cbegin();
2127
2128   auto oldSize = size();
2129   store_.expandNoinit(n, /* expGrowth = */ true);
2130   auto b = begin();
2131   fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
2132   fbstring_detail::podFill(b + pos, b + pos + n, c);
2133
2134   return b + pos;
2135 }
2136
2137 template <typename E, class T, class A, class S>
2138 template <class InputIter>
2139 inline typename basic_fbstring<E, T, A, S>::iterator
2140 basic_fbstring<E, T, A, S>::insertImplDiscr(
2141     const_iterator i, InputIter b, InputIter e, std::false_type) {
2142   return insertImpl(
2143       i, b, e, typename std::iterator_traits<InputIter>::iterator_category());
2144 }
2145
2146 template <typename E, class T, class A, class S>
2147 template <class FwdIterator>
2148 inline typename basic_fbstring<E, T, A, S>::iterator
2149 basic_fbstring<E, T, A, S>::insertImpl(
2150     const_iterator i,
2151     FwdIterator s1,
2152     FwdIterator s2,
2153     std::forward_iterator_tag) {
2154   Invariant checker(*this);
2155
2156   FBSTRING_ASSERT(i >= cbegin() && i <= cend());
2157   const size_type pos = i - cbegin();
2158   auto n = std::distance(s1, s2);
2159   FBSTRING_ASSERT(n >= 0);
2160
2161   auto oldSize = size();
2162   store_.expandNoinit(n, /* expGrowth = */ true);
2163   auto b = begin();
2164   fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
2165   std::copy(s1, s2, b + pos);
2166
2167   return b + pos;
2168 }
2169
2170 template <typename E, class T, class A, class S>
2171 template <class InputIterator>
2172 inline typename basic_fbstring<E, T, A, S>::iterator
2173 basic_fbstring<E, T, A, S>::insertImpl(
2174     const_iterator i,
2175     InputIterator b,
2176     InputIterator e,
2177     std::input_iterator_tag) {
2178   const auto pos = i - cbegin();
2179   basic_fbstring temp(cbegin(), i);
2180   for (; b != e; ++b) {
2181     temp.push_back(*b);
2182   }
2183   temp.append(i, cend());
2184   swap(temp);
2185   return begin() + pos;
2186 }
2187
2188 template <typename E, class T, class A, class S>
2189 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2190     iterator i1,
2191     iterator i2,
2192     const value_type* s,
2193     size_type n,
2194     std::integral_constant<int, 2>) {
2195   FBSTRING_ASSERT(i1 <= i2);
2196   FBSTRING_ASSERT(begin() <= i1 && i1 <= end());
2197   FBSTRING_ASSERT(begin() <= i2 && i2 <= end());
2198   return replace(i1, i2, s, s + n);
2199 }
2200
2201 template <typename E, class T, class A, class S>
2202 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2203     iterator i1,
2204     iterator i2,
2205     size_type n2,
2206     value_type c,
2207     std::integral_constant<int, 1>) {
2208   const size_type n1 = i2 - i1;
2209   if (n1 > n2) {
2210     std::fill(i1, i1 + n2, c);
2211     erase(i1 + n2, i2);
2212   } else {
2213     std::fill(i1, i2, c);
2214     insert(i2, n2 - n1, c);
2215   }
2216   FBSTRING_ASSERT(isSane());
2217   return *this;
2218 }
2219
2220 template <typename E, class T, class A, class S>
2221 template <class InputIter>
2222 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2223     iterator i1,
2224     iterator i2,
2225     InputIter b,
2226     InputIter e,
2227     std::integral_constant<int, 0>) {
2228   using Cat = typename std::iterator_traits<InputIter>::iterator_category;
2229   replaceImpl(i1, i2, b, e, Cat());
2230   return *this;
2231 }
2232
2233 template <typename E, class T, class A, class S>
2234 template <class FwdIterator>
2235 inline bool basic_fbstring<E, T, A, S>::replaceAliased(
2236     iterator i1, iterator i2, FwdIterator s1, FwdIterator s2, std::true_type) {
2237   std::less_equal<const value_type*> le{};
2238   const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
2239   if (!aliased) {
2240     return false;
2241   }
2242   // Aliased replace, copy to new string
2243   basic_fbstring temp;
2244   temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
2245   temp.append(begin(), i1).append(s1, s2).append(i2, end());
2246   swap(temp);
2247   return true;
2248 }
2249
2250 template <typename E, class T, class A, class S>
2251 template <class FwdIterator>
2252 inline void basic_fbstring<E, T, A, S>::replaceImpl(
2253     iterator i1,
2254     iterator i2,
2255     FwdIterator s1,
2256     FwdIterator s2,
2257     std::forward_iterator_tag) {
2258   Invariant checker(*this);
2259
2260   // Handle aliased replace
2261   using Sel = std::integral_constant<
2262       bool,
2263       std::is_same<FwdIterator, iterator>::value ||
2264           std::is_same<FwdIterator, const_iterator>::value>;
2265   if (replaceAliased(i1, i2, s1, s2, Sel())) {
2266     return;
2267   }
2268
2269   auto const n1 = i2 - i1;
2270   FBSTRING_ASSERT(n1 >= 0);
2271   auto const n2 = std::distance(s1, s2);
2272   FBSTRING_ASSERT(n2 >= 0);
2273
2274   if (n1 > n2) {
2275     // shrinks
2276     std::copy(s1, s2, i1);
2277     erase(i1 + n2, i2);
2278   } else {
2279     // grows
2280     s1 = fbstring_detail::copy_n(s1, n1, i1).first;
2281     insert(i2, s1, s2);
2282   }
2283   FBSTRING_ASSERT(isSane());
2284 }
2285
2286 template <typename E, class T, class A, class S>
2287 template <class InputIterator>
2288 inline void basic_fbstring<E, T, A, S>::replaceImpl(
2289     iterator i1,
2290     iterator i2,
2291     InputIterator b,
2292     InputIterator e,
2293     std::input_iterator_tag) {
2294   basic_fbstring temp(begin(), i1);
2295   temp.append(b, e).append(i2, end());
2296   swap(temp);
2297 }
2298
2299 template <typename E, class T, class A, class S>
2300 inline typename basic_fbstring<E, T, A, S>::size_type
2301 basic_fbstring<E, T, A, S>::rfind(
2302     const value_type* s, size_type pos, size_type n) const {
2303   if (n > length()) {
2304     return npos;
2305   }
2306   pos = std::min(pos, length() - n);
2307   if (n == 0) {
2308     return pos;
2309   }
2310
2311   const_iterator i(begin() + pos);
2312   for (;; --i) {
2313     if (traits_type::eq(*i, *s) && traits_type::compare(&*i, s, n) == 0) {
2314       return i - begin();
2315     }
2316     if (i == begin()) {
2317       break;
2318     }
2319   }
2320   return npos;
2321 }
2322
2323 template <typename E, class T, class A, class S>
2324 inline typename basic_fbstring<E, T, A, S>::size_type
2325 basic_fbstring<E, T, A, S>::find_first_of(
2326     const value_type* s, size_type pos, size_type n) const {
2327   if (pos > length() || n == 0) {
2328     return npos;
2329   }
2330   const_iterator i(begin() + pos), finish(end());
2331   for (; i != finish; ++i) {
2332     if (traits_type::find(s, n, *i) != 0) {
2333       return i - begin();
2334     }
2335   }
2336   return npos;
2337 }
2338
2339 template <typename E, class T, class A, class S>
2340 inline typename basic_fbstring<E, T, A, S>::size_type
2341 basic_fbstring<E, T, A, S>::find_last_of(
2342     const value_type* s, size_type pos, size_type n) const {
2343   if (!empty() && n > 0) {
2344     pos = std::min(pos, length() - 1);
2345     const_iterator i(begin() + pos);
2346     for (;; --i) {
2347       if (traits_type::find(s, n, *i) != 0) {
2348         return i - begin();
2349       }
2350       if (i == begin()) {
2351         break;
2352       }
2353     }
2354   }
2355   return npos;
2356 }
2357
2358 template <typename E, class T, class A, class S>
2359 inline typename basic_fbstring<E, T, A, S>::size_type
2360 basic_fbstring<E, T, A, S>::find_first_not_of(
2361     const value_type* s, size_type pos, size_type n) const {
2362   if (pos < length()) {
2363     const_iterator i(begin() + pos), finish(end());
2364     for (; i != finish; ++i) {
2365       if (traits_type::find(s, n, *i) == 0) {
2366         return i - begin();
2367       }
2368     }
2369   }
2370   return npos;
2371 }
2372
2373 template <typename E, class T, class A, class S>
2374 inline typename basic_fbstring<E, T, A, S>::size_type
2375 basic_fbstring<E, T, A, S>::find_last_not_of(
2376     const value_type* s, size_type pos, size_type n) const {
2377   if (!this->empty()) {
2378     pos = std::min(pos, size() - 1);
2379     const_iterator i(begin() + pos);
2380     for (;; --i) {
2381       if (traits_type::find(s, n, *i) == 0) {
2382         return i - begin();
2383       }
2384       if (i == begin()) {
2385         break;
2386       }
2387     }
2388   }
2389   return npos;
2390 }
2391
2392 // non-member functions
2393 // C++11 21.4.8.1/1
2394 template <typename E, class T, class A, class S>
2395 inline
2396 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2397                                      const basic_fbstring<E, T, A, S>& rhs) {
2398
2399   basic_fbstring<E, T, A, S> result;
2400   result.reserve(lhs.size() + rhs.size());
2401   result.append(lhs).append(rhs);
2402   return std::move(result);
2403 }
2404
2405 // C++11 21.4.8.1/2
2406 template <typename E, class T, class A, class S>
2407 inline
2408 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2409                                      const basic_fbstring<E, T, A, S>& rhs) {
2410   return std::move(lhs.append(rhs));
2411 }
2412
2413 // C++11 21.4.8.1/3
2414 template <typename E, class T, class A, class S>
2415 inline
2416 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2417                                      basic_fbstring<E, T, A, S>&& rhs) {
2418   if (rhs.capacity() >= lhs.size() + rhs.size()) {
2419     // Good, at least we don't need to reallocate
2420     return std::move(rhs.insert(0, lhs));
2421   }
2422   // Meh, no go. Forward to operator+(const&, const&).
2423   auto const& rhsC = rhs;
2424   return lhs + rhsC;
2425 }
2426
2427 // C++11 21.4.8.1/4
2428 template <typename E, class T, class A, class S>
2429 inline
2430 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2431                                      basic_fbstring<E, T, A, S>&& rhs) {
2432   return std::move(lhs.append(rhs));
2433 }
2434
2435 // C++11 21.4.8.1/5
2436 template <typename E, class T, class A, class S>
2437 inline
2438 basic_fbstring<E, T, A, S> operator+(
2439   const E* lhs,
2440   const basic_fbstring<E, T, A, S>& rhs) {
2441   //
2442   basic_fbstring<E, T, A, S> result;
2443   const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2444   result.reserve(len + rhs.size());
2445   result.append(lhs, len).append(rhs);
2446   return result;
2447 }
2448
2449 // C++11 21.4.8.1/6
2450 template <typename E, class T, class A, class S>
2451 inline
2452 basic_fbstring<E, T, A, S> operator+(
2453   const E* lhs,
2454   basic_fbstring<E, T, A, S>&& rhs) {
2455   //
2456   const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2457   if (rhs.capacity() >= len + rhs.size()) {
2458     // Good, at least we don't need to reallocate
2459     rhs.insert(rhs.begin(), lhs, lhs + len);
2460     return rhs;
2461   }
2462   // Meh, no go. Do it by hand since we have len already.
2463   basic_fbstring<E, T, A, S> result;
2464   result.reserve(len + rhs.size());
2465   result.append(lhs, len).append(rhs);
2466   return result;
2467 }
2468
2469 // C++11 21.4.8.1/7
2470 template <typename E, class T, class A, class S>
2471 inline
2472 basic_fbstring<E, T, A, S> operator+(
2473   E lhs,
2474   const basic_fbstring<E, T, A, S>& rhs) {
2475
2476   basic_fbstring<E, T, A, S> result;
2477   result.reserve(1 + rhs.size());
2478   result.push_back(lhs);
2479   result.append(rhs);
2480   return result;
2481 }
2482
2483 // C++11 21.4.8.1/8
2484 template <typename E, class T, class A, class S>
2485 inline
2486 basic_fbstring<E, T, A, S> operator+(
2487   E lhs,
2488   basic_fbstring<E, T, A, S>&& rhs) {
2489   //
2490   if (rhs.capacity() > rhs.size()) {
2491     // Good, at least we don't need to reallocate
2492     rhs.insert(rhs.begin(), lhs);
2493     return rhs;
2494   }
2495   // Meh, no go. Forward to operator+(E, const&).
2496   auto const& rhsC = rhs;
2497   return lhs + rhsC;
2498 }
2499
2500 // C++11 21.4.8.1/9
2501 template <typename E, class T, class A, class S>
2502 inline
2503 basic_fbstring<E, T, A, S> operator+(
2504   const basic_fbstring<E, T, A, S>& lhs,
2505   const E* rhs) {
2506
2507   typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2508   typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2509
2510   basic_fbstring<E, T, A, S> result;
2511   const size_type len = traits_type::length(rhs);
2512   result.reserve(lhs.size() + len);
2513   result.append(lhs).append(rhs, len);
2514   return result;
2515 }
2516
2517 // C++11 21.4.8.1/10
2518 template <typename E, class T, class A, class S>
2519 inline
2520 basic_fbstring<E, T, A, S> operator+(
2521   basic_fbstring<E, T, A, S>&& lhs,
2522   const E* rhs) {
2523   //
2524   return std::move(lhs += rhs);
2525 }
2526
2527 // C++11 21.4.8.1/11
2528 template <typename E, class T, class A, class S>
2529 inline
2530 basic_fbstring<E, T, A, S> operator+(
2531   const basic_fbstring<E, T, A, S>& lhs,
2532   E rhs) {
2533
2534   basic_fbstring<E, T, A, S> result;
2535   result.reserve(lhs.size() + 1);
2536   result.append(lhs);
2537   result.push_back(rhs);
2538   return result;
2539 }
2540
2541 // C++11 21.4.8.1/12
2542 template <typename E, class T, class A, class S>
2543 inline
2544 basic_fbstring<E, T, A, S> operator+(
2545   basic_fbstring<E, T, A, S>&& lhs,
2546   E rhs) {
2547   //
2548   return std::move(lhs += rhs);
2549 }
2550
2551 template <typename E, class T, class A, class S>
2552 inline
2553 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2554                 const basic_fbstring<E, T, A, S>& rhs) {
2555   return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2556
2557 template <typename E, class T, class A, class S>
2558 inline
2559 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2560                 const basic_fbstring<E, T, A, S>& rhs) {
2561   return rhs == lhs; }
2562
2563 template <typename E, class T, class A, class S>
2564 inline
2565 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2566                 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2567   return lhs.compare(rhs) == 0; }
2568
2569 template <typename E, class T, class A, class S>
2570 inline
2571 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2572                 const basic_fbstring<E, T, A, S>& rhs) {
2573   return !(lhs == rhs); }
2574
2575 template <typename E, class T, class A, class S>
2576 inline
2577 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2578                 const basic_fbstring<E, T, A, S>& rhs) {
2579   return !(lhs == rhs); }
2580
2581 template <typename E, class T, class A, class S>
2582 inline
2583 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2584                 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2585   return !(lhs == rhs); }
2586
2587 template <typename E, class T, class A, class S>
2588 inline
2589 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2590                const basic_fbstring<E, T, A, S>& rhs) {
2591   return lhs.compare(rhs) < 0; }
2592
2593 template <typename E, class T, class A, class S>
2594 inline
2595 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2596                const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2597   return lhs.compare(rhs) < 0; }
2598
2599 template <typename E, class T, class A, class S>
2600 inline
2601 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2602                const basic_fbstring<E, T, A, S>& rhs) {
2603   return rhs.compare(lhs) > 0; }
2604
2605 template <typename E, class T, class A, class S>
2606 inline
2607 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2608                const basic_fbstring<E, T, A, S>& rhs) {
2609   return rhs < lhs; }
2610
2611 template <typename E, class T, class A, class S>
2612 inline
2613 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2614                const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2615   return rhs < lhs; }
2616
2617 template <typename E, class T, class A, class S>
2618 inline
2619 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2620                const basic_fbstring<E, T, A, S>& rhs) {
2621   return rhs < lhs; }
2622
2623 template <typename E, class T, class A, class S>
2624 inline
2625 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2626                 const basic_fbstring<E, T, A, S>& rhs) {
2627   return !(rhs < lhs); }
2628
2629 template <typename E, class T, class A, class S>
2630 inline
2631 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2632                 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2633   return !(rhs < lhs); }
2634
2635 template <typename E, class T, class A, class S>
2636 inline
2637 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2638                 const basic_fbstring<E, T, A, S>& rhs) {
2639   return !(rhs < lhs); }
2640
2641 template <typename E, class T, class A, class S>
2642 inline
2643 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2644                 const basic_fbstring<E, T, A, S>& rhs) {
2645   return !(lhs < rhs); }
2646
2647 template <typename E, class T, class A, class S>
2648 inline
2649 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2650                 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2651   return !(lhs < rhs); }
2652
2653 template <typename E, class T, class A, class S>
2654 inline
2655 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2656                 const basic_fbstring<E, T, A, S>& rhs) {
2657  return !(lhs < rhs);
2658 }
2659
2660 // C++11 21.4.8.8
2661 template <typename E, class T, class A, class S>
2662 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2663   lhs.swap(rhs);
2664 }
2665
2666 // TODO: make this faster.
2667 template <typename E, class T, class A, class S>
2668 inline
2669 std::basic_istream<
2670   typename basic_fbstring<E, T, A, S>::value_type,
2671   typename basic_fbstring<E, T, A, S>::traits_type>&
2672   operator>>(
2673     std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2674     typename basic_fbstring<E, T, A, S>::traits_type>& is,
2675     basic_fbstring<E, T, A, S>& str) {
2676   typedef std::basic_istream<
2677       typename basic_fbstring<E, T, A, S>::value_type,
2678       typename basic_fbstring<E, T, A, S>::traits_type>
2679       _istream_type;
2680   typename _istream_type::sentry sentry(is);
2681   size_t extracted = 0;
2682   auto err = _istream_type::goodbit;
2683   if (sentry) {
2684     auto n = is.width();
2685     if (n <= 0) {
2686       n = str.max_size();
2687     }
2688     str.erase();
2689     for (auto got = is.rdbuf()->sgetc(); extracted != size_t(n); ++extracted) {
2690       if (got == T::eof()) {
2691         err |= _istream_type::eofbit;
2692         is.width(0);
2693         break;
2694       }
2695       if (isspace(got)) {
2696         break;
2697       }
2698       str.push_back(got);
2699       got = is.rdbuf()->snextc();
2700     }
2701   }
2702   if (!extracted) {
2703     err |= _istream_type::failbit;
2704   }
2705   if (err) {
2706     is.setstate(err);
2707   }
2708   return is;
2709 }
2710
2711 template <typename E, class T, class A, class S>
2712 inline
2713 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2714                    typename basic_fbstring<E, T, A, S>::traits_type>&
2715 operator<<(
2716   std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2717   typename basic_fbstring<E, T, A, S>::traits_type>& os,
2718     const basic_fbstring<E, T, A, S>& str) {
2719 #if _LIBCPP_VERSION
2720   typedef std::basic_ostream<
2721       typename basic_fbstring<E, T, A, S>::value_type,
2722       typename basic_fbstring<E, T, A, S>::traits_type>
2723       _ostream_type;
2724   typename _ostream_type::sentry _s(os);
2725   if (_s) {
2726     typedef std::ostreambuf_iterator<
2727       typename basic_fbstring<E, T, A, S>::value_type,
2728       typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
2729     size_t __len = str.size();
2730     bool __left =
2731         (os.flags() & _ostream_type::adjustfield) == _ostream_type::left;
2732     if (__pad_and_output(_Ip(os),
2733                          str.data(),
2734                          __left ? str.data() + __len : str.data(),
2735                          str.data() + __len,
2736                          os,
2737                          os.fill()).failed()) {
2738       os.setstate(_ostream_type::badbit | _ostream_type::failbit);
2739     }
2740   }
2741 #elif defined(_MSC_VER)
2742   typedef decltype(os.precision()) streamsize;
2743   // MSVC doesn't define __ostream_insert
2744   os.write(str.data(), static_cast<streamsize>(str.size()));
2745 #else
2746   std::__ostream_insert(os, str.data(), str.size());
2747 #endif
2748   return os;
2749 }
2750
2751 template <typename E1, class T, class A, class S>
2752 constexpr typename basic_fbstring<E1, T, A, S>::size_type
2753     basic_fbstring<E1, T, A, S>::npos;
2754
2755 #ifndef _LIBSTDCXX_FBSTRING
2756 // basic_string compatibility routines
2757
2758 template <typename E, class T, class A, class S, class A2>
2759 inline bool operator==(
2760     const basic_fbstring<E, T, A, S>& lhs,
2761     const std::basic_string<E, T, A2>& rhs) {
2762   return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2763 }
2764
2765 template <typename E, class T, class A, class S, class A2>
2766 inline bool operator==(
2767     const std::basic_string<E, T, A2>& lhs,
2768     const basic_fbstring<E, T, A, S>& rhs) {
2769   return rhs == lhs;
2770 }
2771
2772 template <typename E, class T, class A, class S, class A2>
2773 inline bool operator!=(
2774     const basic_fbstring<E, T, A, S>& lhs,
2775     const std::basic_string<E, T, A2>& rhs) {
2776   return !(lhs == rhs);
2777 }
2778
2779 template <typename E, class T, class A, class S, class A2>
2780 inline bool operator!=(
2781     const std::basic_string<E, T, A2>& lhs,
2782     const basic_fbstring<E, T, A, S>& rhs) {
2783   return !(lhs == rhs);
2784 }
2785
2786 template <typename E, class T, class A, class S, class A2>
2787 inline bool operator<(
2788     const basic_fbstring<E, T, A, S>& lhs,
2789     const std::basic_string<E, T, A2>& rhs) {
2790   return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) < 0;
2791 }
2792
2793 template <typename E, class T, class A, class S, class A2>
2794 inline bool operator>(
2795     const basic_fbstring<E, T, A, S>& lhs,
2796     const std::basic_string<E, T, A2>& rhs) {
2797   return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) > 0;
2798 }
2799
2800 template <typename E, class T, class A, class S, class A2>
2801 inline bool operator<(
2802     const std::basic_string<E, T, A2>& lhs,
2803     const basic_fbstring<E, T, A, S>& rhs) {
2804   return rhs > lhs;
2805 }
2806
2807 template <typename E, class T, class A, class S, class A2>
2808 inline bool operator>(
2809     const std::basic_string<E, T, A2>& lhs,
2810     const basic_fbstring<E, T, A, S>& rhs) {
2811   return rhs < lhs;
2812 }
2813
2814 template <typename E, class T, class A, class S, class A2>
2815 inline bool operator<=(
2816     const basic_fbstring<E, T, A, S>& lhs,
2817     const std::basic_string<E, T, A2>& rhs) {
2818   return !(lhs > rhs);
2819 }
2820
2821 template <typename E, class T, class A, class S, class A2>
2822 inline bool operator>=(
2823     const basic_fbstring<E, T, A, S>& lhs,
2824     const std::basic_string<E, T, A2>& rhs) {
2825   return !(lhs < rhs);
2826 }
2827
2828 template <typename E, class T, class A, class S, class A2>
2829 inline bool operator<=(
2830     const std::basic_string<E, T, A2>& lhs,
2831     const basic_fbstring<E, T, A, S>& rhs) {
2832   return !(lhs > rhs);
2833 }
2834
2835 template <typename E, class T, class A, class S, class A2>
2836 inline bool operator>=(
2837     const std::basic_string<E, T, A2>& lhs,
2838     const basic_fbstring<E, T, A, S>& rhs) {
2839   return !(lhs < rhs);
2840 }
2841
2842 #if !defined(_LIBSTDCXX_FBSTRING)
2843 typedef basic_fbstring<char> fbstring;
2844 #endif
2845
2846 // fbstring is relocatable
2847 template <class T, class R, class A, class S>
2848 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2849
2850 #endif
2851
2852 FOLLY_FBSTRING_END_NAMESPACE
2853
2854 #ifndef _LIBSTDCXX_FBSTRING
2855
2856 // Hash functions to make fbstring usable with e.g. hash_map
2857 //
2858 // Handle interaction with different C++ standard libraries, which
2859 // expect these types to be in different namespaces.
2860
2861 #define FOLLY_FBSTRING_HASH1(T)                                        \
2862   template <>                                                          \
2863   struct hash< ::folly::basic_fbstring<T>> {                           \
2864     size_t operator()(const ::folly::basic_fbstring<T>& s) const {     \
2865       return ::folly::hash::fnv32_buf(s.data(), s.size() * sizeof(T)); \
2866     }                                                                  \
2867   };
2868
2869 // The C++11 standard says that these four are defined
2870 #define FOLLY_FBSTRING_HASH \
2871   FOLLY_FBSTRING_HASH1(char) \
2872   FOLLY_FBSTRING_HASH1(char16_t) \
2873   FOLLY_FBSTRING_HASH1(char32_t) \
2874   FOLLY_FBSTRING_HASH1(wchar_t)
2875
2876 namespace std {
2877
2878 FOLLY_FBSTRING_HASH
2879
2880 }  // namespace std
2881
2882 #undef FOLLY_FBSTRING_HASH
2883 #undef FOLLY_FBSTRING_HASH1
2884
2885 #endif // _LIBSTDCXX_FBSTRING
2886
2887 FOLLY_POP_WARNING
2888
2889 #undef FBSTRING_DISABLE_SSO
2890 #undef FBSTRING_SANITIZE_ADDRESS
2891 #undef throw
2892 #undef FBSTRING_LIKELY
2893 #undef FBSTRING_UNLIKELY
2894 #undef FBSTRING_ASSERT