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