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