folly/FBString.h

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