folly/FBString.h

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