folly/FBString.h

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