Disallow COW in FBString

[folly.git] / folly / FBString.h

/*
 * Copyright 2016 Facebook, Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

// @author: Andrei Alexandrescu (aalexandre)
// String type.

#pragma once

#include <atomic>
#include <limits>
#include <type_traits>

// This file appears in two locations: inside fbcode and in the
// libstdc++ source code (when embedding fbstring as std::string).
// To aid in this schizophrenic use, _LIBSTDCXX_FBSTRING is defined in
// libstdc++'s c++config.h, to gate use inside fbcode v. libstdc++.
#ifdef _LIBSTDCXX_FBSTRING

#pragma GCC system_header

#include "basic_fbstring_malloc.h"

// When used as std::string replacement always disable assertions.
#define FBSTRING_ASSERT(expr) /* empty */

#else // !_LIBSTDCXX_FBSTRING

#include <folly/Portability.h>

// libc++ doesn't provide this header, nor does msvc
#ifdef FOLLY_HAVE_BITS_CXXCONFIG_H
#include <bits/c++config.h>
#endif

#include <algorithm>
#include <cassert>
#include <cstring>
#include <string>
#include <utility>

#include <folly/Hash.h>
#include <folly/Malloc.h>
#include <folly/Traits.h>

#if FOLLY_HAVE_DEPRECATED_ASSOC
#ifdef _GLIBCXX_SYMVER
#include <ext/hash_set>
#include <ext/hash_map>
#endif
#endif

// When used in folly, assertions are not disabled.
#define FBSTRING_ASSERT(expr) assert(expr)

#endif

// We defined these here rather than including Likely.h to avoid
// redefinition errors when fbstring is imported into libstdc++.
#if defined(__GNUC__) && __GNUC__ >= 4
#define FBSTRING_LIKELY(x)   (__builtin_expect((x), 1))
#define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
#else
#define FBSTRING_LIKELY(x)   (x)
#define FBSTRING_UNLIKELY(x) (x)
#endif

#pragma GCC diagnostic push
// Ignore shadowing warnings within this file, so includers can use -Wshadow.
#pragma GCC diagnostic ignored "-Wshadow"
// GCC 4.9 has a false positive in setSmallSize (probably
// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59124), disable
// compile-time array bound checking.
#pragma GCC diagnostic ignored "-Warray-bounds"

// FBString cannot use throw when replacing std::string, though it may still
// use std::__throw_*
// nolint
#define throw FOLLY_FBSTRING_MAY_NOT_USE_THROW

#ifdef _LIBSTDCXX_FBSTRING
namespace std _GLIBCXX_VISIBILITY(default) {
_GLIBCXX_BEGIN_NAMESPACE_VERSION
#else
namespace folly {
#endif

#if defined(__clang__)
# if __has_feature(address_sanitizer)
#  define FBSTRING_SANITIZE_ADDRESS
# endif
#elif defined (__GNUC__) && \
      (((__GNUC__ == 4) && (__GNUC_MINOR__ >= 8)) || (__GNUC__ >= 5)) && \
      __SANITIZE_ADDRESS__
# define FBSTRING_SANITIZE_ADDRESS
#endif

// When compiling with ASan, always heap-allocate the string even if
// it would fit in-situ, so that ASan can detect access to the string
// buffer after it has been invalidated (destroyed, resized, etc.).
// Note that this flag doesn't remove support for in-situ strings, as
// that would break ABI-compatibility and wouldn't allow linking code
// compiled with this flag with code compiled without.
#ifdef FBSTRING_SANITIZE_ADDRESS
# define FBSTRING_DISABLE_SSO true
#else
# define FBSTRING_DISABLE_SSO false
#endif

namespace fbstring_detail {

template <class InIt, class OutIt>
inline std::pair<InIt, OutIt> copy_n(
    InIt b,
    typename std::iterator_traits<InIt>::difference_type n,
    OutIt d) {
  for (; n != 0; --n, ++b, ++d) {
    *d = *b;
  }
  return std::make_pair(b, d);
}

template <class Pod, class T>
inline void podFill(Pod* b, Pod* e, T c) {
  FBSTRING_ASSERT(b && e && b <= e);
  /*static*/ if (sizeof(T) == 1) {
    memset(b, c, e - b);
  } else {
    auto const ee = b + ((e - b) & ~7u);
    for (; b != ee; b += 8) {
      b[0] = c;
      b[1] = c;
      b[2] = c;
      b[3] = c;
      b[4] = c;
      b[5] = c;
      b[6] = c;
      b[7] = c;
    }
    // Leftovers
    for (; b != e; ++b) {
      *b = c;
    }
  }
}

/*
 * Lightly structured memcpy, simplifies copying PODs and introduces
 * some asserts. Unfortunately using this function may cause
 * measurable overhead (presumably because it adjusts from a begin/end
 * convention to a pointer/size convention, so it does some extra
 * arithmetic even though the caller might have done the inverse
 * adaptation outside).
 */
template <class Pod>
inline void podCopy(const Pod* b, const Pod* e, Pod* d) {
  FBSTRING_ASSERT(e >= b);
  FBSTRING_ASSERT(d >= e || d + (e - b) <= b);
  memcpy(d, b, (e - b) * sizeof(Pod));
}

/*
 * Lightly structured memmove, simplifies copying PODs and introduces
 * some asserts
 */
template <class Pod>
inline void podMove(const Pod* b, const Pod* e, Pod* d) {
  FBSTRING_ASSERT(e >= b);
  memmove(d, b, (e - b) * sizeof(*b));
}

// always inline
#if defined(__GNUC__) // Clang also defines __GNUC__
# define FBSTRING_ALWAYS_INLINE inline __attribute__((__always_inline__))
#elif defined(_MSC_VER)
# define FBSTRING_ALWAYS_INLINE __forceinline
#else
# define FBSTRING_ALWAYS_INLINE inline
#endif

[[noreturn]] FBSTRING_ALWAYS_INLINE void assume_unreachable() {
#if defined(__GNUC__) // Clang also defines __GNUC__
  __builtin_unreachable();
#elif defined(_MSC_VER)
  __assume(0);
#else
  // Well, it's better than nothing.
  std::abort();
#endif
}

} // namespace fbstring_detail

/**
 * Defines a special acquisition method for constructing fbstring
 * objects. AcquireMallocatedString means that the user passes a
 * pointer to a malloc-allocated string that the fbstring object will
 * take into custody.
 */
enum class AcquireMallocatedString {};

/*
 * fbstring_core_model is a mock-up type that defines all required
 * signatures of a fbstring core. The fbstring class itself uses such
 * a core object to implement all of the numerous member functions
 * required by the standard.
 *
 * If you want to define a new core, copy the definition below and
 * implement the primitives. Then plug the core into basic_fbstring as
 * a template argument.

template <class Char>
class fbstring_core_model {
public:
  fbstring_core_model();
  fbstring_core_model(const fbstring_core_model &);
  ~fbstring_core_model();
  // Returns a pointer to string's buffer (currently only contiguous
  // strings are supported). The pointer is guaranteed to be valid
  // until the next call to a non-const member function.
  const Char * data() const;
  // Much like data(), except the string is prepared to support
  // character-level changes. This call is a signal for
  // e.g. reference-counted implementation to fork the data. The
  // pointer is guaranteed to be valid until the next call to a
  // non-const member function.
  Char* mutableData();
  // Returns a pointer to string's buffer and guarantees that a
  // readable '\0' lies right after the buffer. The pointer is
  // guaranteed to be valid until the next call to a non-const member
  // function.
  const Char * c_str() const;
  // Shrinks the string by delta characters. Asserts that delta <=
  // size().
  void shrink(size_t delta);
  // Expands the string by delta characters (i.e. after this call
  // size() will report the old size() plus delta) but without
  // initializing the expanded region. The expanded region is
  // zero-terminated. Returns a pointer to the memory to be
  // initialized (the beginning of the expanded portion). The caller
  // is expected to fill the expanded area appropriately.
  // If expGrowth is true, exponential growth is guaranteed.
  // It is not guaranteed not to reallocate even if size() + delta <
  // capacity(), so all references to the buffer are invalidated.
  Char* expandNoinit(size_t delta, bool expGrowth);
  // Expands the string by one character and sets the last character
  // to c.
  void push_back(Char c);
  // Returns the string's size.
  size_t size() const;
  // Returns the string's capacity, i.e. maximum size that the string
  // can grow to without reallocation. Note that for reference counted
  // strings that's technically a lie - even assigning characters
  // within the existing size would cause a reallocation.
  size_t capacity() const;
  // Returns true if the data underlying the string is actually shared
  // across multiple strings (in a refcounted fashion).
  bool isShared() const;
  // Makes sure that at least minCapacity characters are available for
  // the string without reallocation. For reference-counted strings,
  // it should fork the data even if minCapacity < size().
  void reserve(size_t minCapacity);
private:
  // Do not implement
  fbstring_core_model& operator=(const fbstring_core_model &);
};
*/

/**
 * This is the core of the string. The code should work on 32- and
 * 64-bit and both big- and little-endianan architectures with any
 * Char size.
 *
 * The storage is selected as follows (assuming we store one-byte
 * characters on a 64-bit machine): (a) "small" strings between 0 and
 * 23 chars are stored in-situ without allocation (the rightmost byte
 * stores the size); (b) "medium" strings (> 23 chars) are stored in
 * malloc-allocated memory that is copied eagerly.
 * There exists a third storage category: (c) "large", which has the
 * copy-on-write optimization. COW was disallowed in C++11, so large is
 * now deprecated in fbstring_core. fbstring_core no longer creates large
 * strings, though still works with them. Later, large strings will be
 * completely removed.
 *
 * The discriminator between these three strategies sits in two
 * bits of the rightmost char of the storage. If neither is set, then the
 * string is small (and its length sits in the lower-order bits on
 * little-endian or the high-order bits on big-endian of that
 * rightmost character). If the MSb is set, the string is medium width.
 * If the second MSb is set, then the string is large. On little-endian,
 * these 2 bits are the 2 MSbs of MediumLarge::capacity_, while on
 * big-endian, these 2 bits are the 2 LSbs. This keeps both little-endian
 * and big-endian fbstring_core equivalent with merely different ops used
 * to extract capacity/category.
 */
template <class Char> class fbstring_core {
protected:
// It's MSVC, so we just have to guess ... and allow an override
#ifdef _MSC_VER
# ifdef FOLLY_ENDIAN_BE
  static constexpr auto kIsLittleEndian = false;
# else
  static constexpr auto kIsLittleEndian = true;
# endif
#else
  static constexpr auto kIsLittleEndian =
      __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__;
#endif
public:
  fbstring_core() noexcept { reset(); }

  fbstring_core(const fbstring_core & rhs) {
    FBSTRING_ASSERT(&rhs != this);
    if (rhs.category() == Category::isSmall) {
      makeSmall(rhs);
    } else {
      makeMedium(rhs);
    }
    FBSTRING_ASSERT(size() == rhs.size());
    FBSTRING_ASSERT(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
  }

  fbstring_core(fbstring_core&& goner) noexcept {
    // Take goner's guts
    ml_ = goner.ml_;
    // Clean goner's carcass
    goner.reset();
  }

  fbstring_core(const Char *const data,
                const size_t size,
                bool disableSSO = FBSTRING_DISABLE_SSO) {
    if (!disableSSO && size <= maxSmallSize) {
      initSmall(data, size);
    } else {
      initMedium(data, size);
    }
    FBSTRING_ASSERT(this->size() == size);
    FBSTRING_ASSERT(
        size == 0 || memcmp(this->data(), data, size * sizeof(Char)) == 0);
  }

  ~fbstring_core() noexcept {
    if (category() == Category::isSmall) {
      return;
    }
    destroyMediumLarge();
  }

  // Snatches a previously mallocated string. The parameter "size"
  // is the size of the string, and the parameter "allocatedSize"
  // is the size of the mallocated block.  The string must be
  // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
  //
  // So if you want a 2-character string, pass malloc(3) as "data",
  // pass 2 as "size", and pass 3 as "allocatedSize".
  fbstring_core(Char * const data,
                const size_t size,
                const size_t allocatedSize,
                AcquireMallocatedString) {
    if (size > 0) {
      FBSTRING_ASSERT(allocatedSize >= size + 1);
      FBSTRING_ASSERT(data[size] == '\0');
      // Use the medium string storage
      ml_.data_ = data;
      ml_.size_ = size;
      // Don't forget about null terminator
      ml_.setCapacity(allocatedSize - 1, Category::isMedium);
    } else {
      // No need for the memory
      free(data);
      reset();
    }
  }

  // swap below doesn't test whether &rhs == this (and instead
  // potentially does extra work) on the premise that the rarity of
  // that situation actually makes the check more expensive than is
  // worth.
  void swap(fbstring_core & rhs) {
    auto const t = ml_;
    ml_ = rhs.ml_;
    rhs.ml_ = t;
  }

  // In C++11 data() and c_str() are 100% equivalent.
  const Char * data() const {
    return c_str();
  }

  Char* mutableData() {
    switch (category()) {
    case Category::isSmall:
      return small_;
    case Category::isMedium:
      return ml_.data_;
    case Category::isLarge:
      return mutableDataLarge();
    }
    fbstring_detail::assume_unreachable();
  }

  const Char* c_str() const {
    const Char* ptr = ml_.data_;
    // With this syntax, GCC and Clang generate a CMOV instead of a branch.
    ptr = (category() == Category::isSmall) ? small_ : ptr;
    return ptr;
  }

  void shrink(const size_t delta) {
    if (category() == Category::isSmall) {
      shrinkSmall(delta);
    } else if (category() == Category::isMedium ||
               RefCounted::refs(ml_.data_) == 1) {
      shrinkMedium(delta);
    } else {
      shrinkLarge(delta);
    }
  }

  FOLLY_MALLOC_NOINLINE
  void reserve(size_t minCapacity, bool disableSSO = FBSTRING_DISABLE_SSO) {
    switch (category()) {
      case Category::isSmall:
        reserveSmall(minCapacity, disableSSO);
        break;
      case Category::isMedium:
        reserveMedium(minCapacity);
        break;
      case Category::isLarge:
        reserveLarge(minCapacity);
        break;
      default:
        fbstring_detail::assume_unreachable();
    }
    FBSTRING_ASSERT(capacity() >= minCapacity);
  }

  Char* expandNoinit(
      const size_t delta,
      bool expGrowth = false,
      bool disableSSO = FBSTRING_DISABLE_SSO);

  void push_back(Char c) {
    *expandNoinit(1, /* expGrowth = */ true) = c;
  }

  size_t size() const {
    size_t ret = ml_.size_;
    /* static */ if (kIsLittleEndian) {
      // We can save a couple instructions, because the category is
      // small iff the last char, as unsigned, is <= maxSmallSize.
      typedef typename std::make_unsigned<Char>::type UChar;
      auto maybeSmallSize = size_t(maxSmallSize) -
          size_t(static_cast<UChar>(small_[maxSmallSize]));
      // With this syntax, GCC and Clang generate a CMOV instead of a branch.
      ret = (static_cast<ssize_t>(maybeSmallSize) >= 0) ? maybeSmallSize : ret;
    } else {
      ret = (category() == Category::isSmall) ? smallSize() : ret;
    }
    return ret;
  }

  size_t capacity() const {
    switch (category()) {
      case Category::isSmall:
        return maxSmallSize;
      case Category::isLarge:
        // For large-sized strings, a multi-referenced chunk has no
        // available capacity. This is because any attempt to append
        // data would trigger a new allocation.
        if (RefCounted::refs(ml_.data_) > 1) {
          return ml_.size_;
        }
      default: {}
    }
    return ml_.capacity();
  }

  bool isShared() const {
    return category() == Category::isLarge && RefCounted::refs(ml_.data_) > 1;
  }

private:
  // Disabled
  fbstring_core & operator=(const fbstring_core & rhs);

  void reset() {
    setSmallSize(0);
  }

  FOLLY_MALLOC_NOINLINE void destroyMediumLarge() noexcept {
    auto const c = category();
    FBSTRING_ASSERT(c != Category::isSmall);
    if (c == Category::isMedium) {
      free(ml_.data_);
    } else {
      RefCounted::decrementRefs(ml_.data_);
    }
  }

  struct RefCounted {
    std::atomic<size_t> refCount_;
    Char data_[1];

    static RefCounted * fromData(Char * p) {
      return static_cast<RefCounted*>(
        static_cast<void*>(
          static_cast<unsigned char*>(static_cast<void*>(p))
          - sizeof(refCount_)));
    }

    static size_t refs(Char * p) {
      return fromData(p)->refCount_.load(std::memory_order_acquire);
    }

    static void incrementRefs(Char * p) {
      fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
    }

    static void decrementRefs(Char * p) {
      auto const dis = fromData(p);
      size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
      FBSTRING_ASSERT(oldcnt > 0);
      if (oldcnt == 1) {
        free(dis);
      }
    }

    static RefCounted * create(size_t * size) {
      // Don't forget to allocate one extra Char for the terminating
      // null. In this case, however, one Char is already part of the
      // struct.
      const size_t allocSize = goodMallocSize(
        sizeof(RefCounted) + *size * sizeof(Char));
      auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
      result->refCount_.store(1, std::memory_order_release);
      *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
      return result;
    }

    static RefCounted * create(const Char * data, size_t * size) {
      const size_t effectiveSize = *size;
      auto result = create(size);
      fbstring_detail::podCopy(data, data + effectiveSize, result->data_);
      return result;
    }

    static RefCounted * reallocate(Char *const data,
                                   const size_t currentSize,
                                   const size_t currentCapacity,
                                   const size_t newCapacity) {
      FBSTRING_ASSERT(newCapacity > 0 && newCapacity > currentSize);
      auto const dis = fromData(data);
      FBSTRING_ASSERT(dis->refCount_.load(std::memory_order_acquire) == 1);
      // Don't forget to allocate one extra Char for the terminating
      // null. In this case, however, one Char is already part of the
      // struct.
      auto result = static_cast<RefCounted*>(
             smartRealloc(dis,
                          sizeof(RefCounted) + currentSize * sizeof(Char),
                          sizeof(RefCounted) + currentCapacity * sizeof(Char),
                          sizeof(RefCounted) + newCapacity * sizeof(Char)));
      FBSTRING_ASSERT(result->refCount_.load(std::memory_order_acquire) == 1);
      return result;
    }
  };

  typedef uint8_t category_type;

  enum class Category : category_type {
    isSmall = 0,
    isMedium = kIsLittleEndian ? 0x80 : 0x2,
    isLarge = kIsLittleEndian ? 0x40 : 0x1,
  };

  Category category() const {
    // works for both big-endian and little-endian
    return static_cast<Category>(bytes_[lastChar] & categoryExtractMask);
  }

  struct MediumLarge {
    Char * data_;
    size_t size_;
    size_t capacity_;

    size_t capacity() const {
      return kIsLittleEndian
        ? capacity_ & capacityExtractMask
        : capacity_ >> 2;
    }

    void setCapacity(size_t cap, Category cat) {
      FBSTRING_ASSERT(cat != Category::isLarge);
      capacity_ = kIsLittleEndian
          ? cap | (static_cast<size_t>(cat) << kCategoryShift)
          : (cap << 2) | static_cast<size_t>(cat);
    }
  };

  union {
    uint8_t bytes_[sizeof(MediumLarge)]; // For accessing the last byte.
    Char small_[sizeof(MediumLarge) / sizeof(Char)];
    MediumLarge ml_;
  };

  constexpr static size_t lastChar = sizeof(MediumLarge) - 1;
  constexpr static size_t maxSmallSize = lastChar / sizeof(Char);
  constexpr static size_t maxMediumSize = 254 / sizeof(Char);
  constexpr static uint8_t categoryExtractMask = kIsLittleEndian ? 0xC0 : 0x3;
  constexpr static size_t kCategoryShift = (sizeof(size_t) - 1) * 8;
  constexpr static size_t capacityExtractMask = kIsLittleEndian
      ? ~(size_t(categoryExtractMask) << kCategoryShift)
      : 0x0 /* unused */;

  static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
                "Corrupt memory layout for fbstring.");

  size_t smallSize() const {
    FBSTRING_ASSERT(category() == Category::isSmall);
    constexpr auto shift = kIsLittleEndian ? 0 : 2;
    auto smallShifted = static_cast<size_t>(small_[maxSmallSize]) >> shift;
    FBSTRING_ASSERT(static_cast<size_t>(maxSmallSize) >= smallShifted);
    return static_cast<size_t>(maxSmallSize) - smallShifted;
  }

  void setSmallSize(size_t s) {
    // Warning: this should work with uninitialized strings too,
    // so don't assume anything about the previous value of
    // small_[maxSmallSize].
    FBSTRING_ASSERT(s <= maxSmallSize);
    constexpr auto shift = kIsLittleEndian ? 0 : 2;
    small_[maxSmallSize] = (maxSmallSize - s) << shift;
    small_[s] = '\0';
    FBSTRING_ASSERT(category() == Category::isSmall && size() == s);
  }

  void makeSmall(const fbstring_core&);
  void makeMedium(const fbstring_core&);
  void makeLarge(const fbstring_core&);

  void initSmall(const Char* data, size_t size);
  void initMedium(const Char* data, size_t size);
  void initLarge(const Char* data, size_t size);

  void reserveSmall(size_t minCapacity, bool disableSSO);
  void reserveMedium(size_t minCapacity);
  void reserveLarge(size_t minCapacity);

  void shrinkSmall(size_t delta);
  void shrinkMedium(size_t delta);
  void shrinkLarge(size_t delta);

  void unshare(size_t minCapacity = 0);
  Char* mutableDataLarge();
};

template <class Char>
inline void fbstring_core<Char>::makeSmall(const fbstring_core& rhs) {
  static_assert(offsetof(MediumLarge, data_) == 0, "fbstring layout failure");
  static_assert(
      offsetof(MediumLarge, size_) == sizeof(ml_.data_),
      "fbstring layout failure");
  static_assert(
      offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_),
      "fbstring layout failure");
  // Just write the whole thing, don't look at details. In
  // particular we need to copy capacity anyway because we want
  // to set the size (don't forget that the last character,
  // which stores a short string's length, is shared with the
  // ml_.capacity field).
  ml_ = rhs.ml_;
  FBSTRING_ASSERT(
      category() == Category::isSmall && this->size() == rhs.size());
}

template <class Char>
FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::makeMedium(
    const fbstring_core& rhs) {
  // Medium strings are copied eagerly. Don't forget to allocate
  // one extra Char for the null terminator.
  auto const allocSize = goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
  ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
  // Also copies terminator.
  fbstring_detail::podCopy(
      rhs.ml_.data_, rhs.ml_.data_ + rhs.ml_.size_ + 1, ml_.data_);
  ml_.size_ = rhs.ml_.size_;
  ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
  FBSTRING_ASSERT(category() == Category::isMedium);
}

template <class Char>
FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::makeLarge(
    const fbstring_core& rhs) {
  // Large strings are just refcounted
  ml_ = rhs.ml_;
  RefCounted::incrementRefs(ml_.data_);
  FBSTRING_ASSERT(category() == Category::isLarge && size() == rhs.size());
}

// Small strings are bitblitted
template <class Char>
inline void fbstring_core<Char>::initSmall(
    const Char* const data, const size_t size) {
  // Layout is: Char* data_, size_t size_, size_t capacity_
  static_assert(
      sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t),
      "fbstring has unexpected size");
  static_assert(
      sizeof(Char*) == sizeof(size_t), "fbstring size assumption violation");
  // sizeof(size_t) must be a power of 2
  static_assert(
      (sizeof(size_t) & (sizeof(size_t) - 1)) == 0,
      "fbstring size assumption violation");

// If data is aligned, use fast word-wise copying. Otherwise,
// use conservative memcpy.
// The word-wise path reads bytes which are outside the range of
// the string, and makes ASan unhappy, so we disable it when
// compiling with ASan.
#ifndef FBSTRING_SANITIZE_ADDRESS
  if ((reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) == 0) {
    const size_t byteSize = size * sizeof(Char);
    constexpr size_t wordWidth = sizeof(size_t);
    switch ((byteSize + wordWidth - 1) / wordWidth) { // Number of words.
      case 3:
        ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
      case 2:
        ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
      case 1:
        ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
      case 0:
        break;
    }
  } else
#endif
  {
    if (size != 0) {
      fbstring_detail::podCopy(data, data + size, small_);
    }
  }
  setSmallSize(size);
}

template <class Char>
FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::initMedium(
    const Char* const data, const size_t size) {
  // Medium strings are allocated normally. Don't forget to
  // allocate one extra Char for the terminating null.
  auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
  ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
  fbstring_detail::podCopy(data, data + size, ml_.data_);
  ml_.size_ = size;
  ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
  ml_.data_[size] = '\0';
}

template <class Char>
FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::initLarge(
    const Char* const data, const size_t size) {
  // Large strings are allocated differently
  size_t effectiveCapacity = size;
  auto const newRC = RefCounted::create(data, &effectiveCapacity);
  ml_.data_ = newRC->data_;
  ml_.size_ = size;
  ml_.setCapacity(effectiveCapacity, Category::isLarge);
  ml_.data_[size] = '\0';
}

template <class Char>
FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::unshare(
    size_t minCapacity) {
  FBSTRING_ASSERT(category() == Category::isLarge);
  size_t effectiveCapacity = std::max(minCapacity, ml_.capacity());
  auto const newRC = RefCounted::create(&effectiveCapacity);
  // If this fails, someone placed the wrong capacity in an
  // fbstring.
  FBSTRING_ASSERT(effectiveCapacity >= ml_.capacity());
  // Also copies terminator.
  fbstring_detail::podCopy(ml_.data_, ml_.data_ + ml_.size_ + 1, newRC->data_);
  RefCounted::decrementRefs(ml_.data_);
  ml_.data_ = newRC->data_;
  ml_.setCapacity(effectiveCapacity, Category::isLarge);
  // size_ remains unchanged.
}

template <class Char>
inline Char* fbstring_core<Char>::mutableDataLarge() {
  FBSTRING_ASSERT(category() == Category::isLarge);
  if (RefCounted::refs(ml_.data_) > 1) { // Ensure unique.
    unshare();
  }
  return ml_.data_;
}

template <class Char>
FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveLarge(
    size_t minCapacity) {
  FBSTRING_ASSERT(category() == Category::isLarge);
  if (RefCounted::refs(ml_.data_) > 1) { // Ensure unique
    // We must make it unique regardless; in-place reallocation is
    // useless if the string is shared. In order to not surprise
    // people, reserve the new block at current capacity or
    // more. That way, a string's capacity never shrinks after a
    // call to reserve.
    unshare(minCapacity);
  } else {
    // String is not shared, so let's try to realloc (if needed)
    if (minCapacity > ml_.capacity()) {
      // Asking for more memory
      auto const newRC = RefCounted::reallocate(
          ml_.data_, ml_.size_, ml_.capacity(), minCapacity);
      ml_.data_ = newRC->data_;
      ml_.setCapacity(minCapacity, Category::isLarge);
    }
    FBSTRING_ASSERT(capacity() >= minCapacity);
  }
}

template <class Char>
FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveMedium(
    const size_t minCapacity) {
  FBSTRING_ASSERT(category() == Category::isMedium);
  // String is not shared
  if (minCapacity <= ml_.capacity()) {
    return; // nothing to do, there's enough room
  }
  // Keep the string at medium size. Don't forget to allocate
  // one extra Char for the terminating null.
  size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
  // Also copies terminator.
  ml_.data_ = static_cast<Char*>(smartRealloc(
      ml_.data_,
      (ml_.size_ + 1) * sizeof(Char),
      (ml_.capacity() + 1) * sizeof(Char),
      capacityBytes));
  ml_.setCapacity(capacityBytes / sizeof(Char) - 1, Category::isMedium);
}

template <class Char>
FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveSmall(
    size_t minCapacity, const bool disableSSO) {
  FBSTRING_ASSERT(category() == Category::isSmall);
  if (!disableSSO && minCapacity <= maxSmallSize) {
    // small
    // Nothing to do, everything stays put
    return;
  }
  // Don't forget to allocate one extra Char for the terminating null
  auto const allocSizeBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
  auto const pData = static_cast<Char*>(checkedMalloc(allocSizeBytes));
  auto const size = smallSize();
  // Also copies terminator.
  fbstring_detail::podCopy(small_, small_ + size + 1, pData);
  ml_.data_ = pData;
  ml_.size_ = size;
  ml_.setCapacity(allocSizeBytes / sizeof(Char) - 1, Category::isMedium);
}

template <class Char>
inline Char* fbstring_core<Char>::expandNoinit(
    const size_t delta,
    bool expGrowth, /* = false */
    bool disableSSO /* = FBSTRING_DISABLE_SSO */) {
  // Strategy is simple: make room, then change size
  FBSTRING_ASSERT(capacity() >= size());
  size_t sz, newSz;
  if (category() == Category::isSmall) {
    sz = smallSize();
    newSz = sz + delta;
    if (!disableSSO && FBSTRING_LIKELY(newSz <= maxSmallSize)) {
      setSmallSize(newSz);
      return small_ + sz;
    }
    reserveSmall(
        expGrowth ? std::max(newSz, 2 * maxSmallSize) : newSz, disableSSO);
  } else {
    sz = ml_.size_;
    newSz = sz + delta;
    if (FBSTRING_UNLIKELY(newSz > capacity())) {
      // ensures not shared
      reserve(expGrowth ? std::max(newSz, 1 + capacity() * 3 / 2) : newSz);
    }
  }
  FBSTRING_ASSERT(capacity() >= newSz);
  // Category can't be small - we took care of that above
  FBSTRING_ASSERT(
      category() == Category::isMedium || category() == Category::isLarge);
  ml_.size_ = newSz;
  ml_.data_[newSz] = '\0';
  FBSTRING_ASSERT(size() == newSz);
  return ml_.data_ + sz;
}

template <class Char>
inline void fbstring_core<Char>::shrinkSmall(const size_t delta) {
  // Check for underflow
  FBSTRING_ASSERT(delta <= smallSize());
  setSmallSize(smallSize() - delta);
}

template <class Char>
inline void fbstring_core<Char>::shrinkMedium(const size_t delta) {
  // Medium strings and unique large strings need no special
  // handling.
  FBSTRING_ASSERT(ml_.size_ >= delta);
  ml_.size_ -= delta;
  ml_.data_[ml_.size_] = '\0';
}

template <class Char>
inline void fbstring_core<Char>::shrinkLarge(const size_t delta) {
  FBSTRING_ASSERT(ml_.size_ >= delta);
  // Shared large string, must make unique. This is because of the
  // durn terminator must be written, which may trample the shared
  // data.
  if (delta) {
    fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
  }
  // No need to write the terminator.
}

#ifndef _LIBSTDCXX_FBSTRING
/**
 * Dummy fbstring core that uses an actual std::string. This doesn't
 * make any sense - it's just for testing purposes.
 */
template <class Char>
class dummy_fbstring_core {
public:
  dummy_fbstring_core() {
  }
  dummy_fbstring_core(const dummy_fbstring_core& another)
      : backend_(another.backend_) {
  }
  dummy_fbstring_core(const Char * s, size_t n)
      : backend_(s, n) {
  }
  void swap(dummy_fbstring_core & rhs) {
    backend_.swap(rhs.backend_);
  }
  const Char * data() const {
    return backend_.data();
  }
  Char* mutableData() {
    return const_cast<Char*>(backend_.data());
  }
  void shrink(size_t delta) {
    FBSTRING_ASSERT(delta <= size());
    backend_.resize(size() - delta);
  }
  Char* expandNoinit(size_t delta) {
    auto const sz = size();
    backend_.resize(size() + delta);
    return backend_.data() + sz;
  }
  void push_back(Char c) {
    backend_.push_back(c);
  }
  size_t size() const {
    return backend_.size();
  }
  size_t capacity() const {
    return backend_.capacity();
  }
  bool isShared() const {
    return false;
  }
  void reserve(size_t minCapacity) {
    backend_.reserve(minCapacity);
  }

private:
  std::basic_string<Char> backend_;
};
#endif // !_LIBSTDCXX_FBSTRING

/**
 * This is the basic_string replacement. For conformity,
 * basic_fbstring takes the same template parameters, plus the last
 * one which is the core.
 */
#ifdef _LIBSTDCXX_FBSTRING
template <typename E, class T, class A, class Storage>
#else
template <typename E,
          class T = std::char_traits<E>,
          class A = std::allocator<E>,
          class Storage = fbstring_core<E> >
#endif
class basic_fbstring {
  static void enforce(
      bool condition,
      void (*throw_exc)(const char*),
      const char* msg) {
    if (!condition) {
      throw_exc(msg);
    }
  }

  bool isSane() const {
    return
      begin() <= end() &&
      empty() == (size() == 0) &&
      empty() == (begin() == end()) &&
      size() <= max_size() &&
      capacity() <= max_size() &&
      size() <= capacity() &&
      begin()[size()] == '\0';
  }

  struct Invariant {
    Invariant& operator=(const Invariant&) = delete;
    explicit Invariant(const basic_fbstring& s) noexcept : s_(s) {
      FBSTRING_ASSERT(s_.isSane());
    }
    ~Invariant() noexcept {
      FBSTRING_ASSERT(s_.isSane());
    }

   private:
    const basic_fbstring& s_;
  };

 public:
  // types
  typedef T traits_type;
  typedef typename traits_type::char_type value_type;
  typedef A allocator_type;
  typedef typename A::size_type size_type;
  typedef typename A::difference_type difference_type;

  typedef typename A::reference reference;
  typedef typename A::const_reference const_reference;
  typedef typename A::pointer pointer;
  typedef typename A::const_pointer const_pointer;

  typedef E* iterator;
  typedef const E* const_iterator;
  typedef std::reverse_iterator<iterator
#ifdef NO_ITERATOR_TRAITS
                                , value_type
#endif
                                > reverse_iterator;
  typedef std::reverse_iterator<const_iterator
#ifdef NO_ITERATOR_TRAITS
                                , const value_type
#endif
                                > const_reverse_iterator;

  static constexpr size_type npos = size_type(-1);
  typedef std::true_type IsRelocatable;

private:
  static void procrustes(size_type& n, size_type nmax) {
    if (n > nmax) {
      n = nmax;
    }
  }

  static size_type traitsLength(const value_type* s);

public:
  // C++11 21.4.2 construct/copy/destroy

  // Note: while the following two constructors can be (and previously were)
  // collapsed into one constructor written this way:
  //
  //   explicit basic_fbstring(const A& a = A()) noexcept { }
  //
  // This can cause Clang (at least version 3.7) to fail with the error:
  //   "chosen constructor is explicit in copy-initialization ...
  //   in implicit initialization of field '(x)' with omitted initializer"
  //
  // if used in a struct which is default-initialized.  Hence the split into
  // these two separate constructors.

  basic_fbstring() noexcept : basic_fbstring(A()) {
  }

  explicit basic_fbstring(const A&) noexcept {
  }

  basic_fbstring(const basic_fbstring& str)
      : store_(str.store_) {
  }

  // Move constructor
  basic_fbstring(basic_fbstring&& goner) noexcept
      : store_(std::move(goner.store_)) {
  }

#ifndef _LIBSTDCXX_FBSTRING
  // This is defined for compatibility with std::string
  /* implicit */ basic_fbstring(const std::string& str)
      : store_(str.data(), str.size()) {
  }
#endif

  basic_fbstring(const basic_fbstring& str,
                 size_type pos,
                 size_type n = npos,
                 const A& /* a */ = A()) {
    assign(str, pos, n);
  }

  FOLLY_MALLOC_NOINLINE
  /* implicit */ basic_fbstring(const value_type* s, const A& /*a*/ = A())
      : store_(s, traitsLength(s)) {}

  FOLLY_MALLOC_NOINLINE
  basic_fbstring(const value_type* s, size_type n, const A& /*a*/ = A())
      : store_(s, n) {
  }

  FOLLY_MALLOC_NOINLINE
  basic_fbstring(size_type n, value_type c, const A& /*a*/ = A()) {
    auto const pData = store_.expandNoinit(n);
    fbstring_detail::podFill(pData, pData + n, c);
  }

  template <class InIt>
  FOLLY_MALLOC_NOINLINE basic_fbstring(
      InIt begin,
      InIt end,
      typename std::enable_if<
          !std::is_same<InIt, value_type*>::value,
          const A>::type& /*a*/ = A()) {
    assign(begin, end);
  }

  // Specialization for const char*, const char*
  FOLLY_MALLOC_NOINLINE
  basic_fbstring(const value_type* b, const value_type* e, const A& /*a*/ = A())
      : store_(b, e - b) {
  }

  // Nonstandard constructor
  basic_fbstring(value_type *s, size_type n, size_type c,
                 AcquireMallocatedString a)
      : store_(s, n, c, a) {
  }

  // Construction from initialization list
  FOLLY_MALLOC_NOINLINE
  basic_fbstring(std::initializer_list<value_type> il) {
    assign(il.begin(), il.end());
  }

  ~basic_fbstring() noexcept {}

  basic_fbstring& operator=(const basic_fbstring& lhs);

  // Move assignment
  basic_fbstring& operator=(basic_fbstring&& goner) noexcept;

#ifndef _LIBSTDCXX_FBSTRING
  // Compatibility with std::string
  basic_fbstring & operator=(const std::string & rhs) {
    return assign(rhs.data(), rhs.size());
  }

  // Compatibility with std::string
  std::string toStdString() const {
    return std::string(data(), size());
  }
#else
  // A lot of code in fbcode still uses this method, so keep it here for now.
  const basic_fbstring& toStdString() const {
    return *this;
  }
#endif

  basic_fbstring& operator=(const value_type* s) {
    return assign(s);
  }

  basic_fbstring& operator=(value_type c);

  basic_fbstring& operator=(std::initializer_list<value_type> il) {
    return assign(il.begin(), il.end());
  }

  // C++11 21.4.3 iterators:
  iterator begin() {
    return store_.mutableData();
  }

  const_iterator begin() const {
    return store_.data();
  }

  const_iterator cbegin() const {
    return begin();
  }

  iterator end() {
    return store_.mutableData() + store_.size();
  }

  const_iterator end() const {
    return store_.data() + store_.size();
  }

  const_iterator cend() const { return end(); }

  reverse_iterator rbegin() {
    return reverse_iterator(end());
  }

  const_reverse_iterator rbegin() const {
    return const_reverse_iterator(end());
  }

  const_reverse_iterator crbegin() const { return rbegin(); }

  reverse_iterator rend() {
    return reverse_iterator(begin());
  }

  const_reverse_iterator rend() const {
    return const_reverse_iterator(begin());
  }

  const_reverse_iterator crend() const { return rend(); }

  // Added by C++11
  // C++11 21.4.5, element access:
  const value_type& front() const { return *begin(); }
  const value_type& back() const {
    FBSTRING_ASSERT(!empty());
    // Should be begin()[size() - 1], but that branches twice
    return *(end() - 1);
  }
  value_type& front() { return *begin(); }
  value_type& back() {
    FBSTRING_ASSERT(!empty());
    // Should be begin()[size() - 1], but that branches twice
    return *(end() - 1);
  }
  void pop_back() {
    FBSTRING_ASSERT(!empty());
    store_.shrink(1);
  }

  // C++11 21.4.4 capacity:
  size_type size() const { return store_.size(); }

  size_type length() const { return size(); }

  size_type max_size() const {
    return std::numeric_limits<size_type>::max();
  }

  void resize(size_type n, value_type c = value_type());

  size_type capacity() const { return store_.capacity(); }

  void reserve(size_type res_arg = 0) {
    enforce(res_arg <= max_size(), std::__throw_length_error, "");
    store_.reserve(res_arg);
  }

  void shrink_to_fit() {
    // Shrink only if slack memory is sufficiently large
    if (capacity() < size() * 3 / 2) {
      return;
    }
    basic_fbstring(cbegin(), cend()).swap(*this);
  }

  void clear() { resize(0); }

  bool empty() const { return size() == 0; }

  // C++11 21.4.5 element access:
  const_reference operator[](size_type pos) const {
    return *(begin() + pos);
  }

  reference operator[](size_type pos) {
    return *(begin() + pos);
  }

  const_reference at(size_type n) const {
    enforce(n <= size(), std::__throw_out_of_range, "");
    return (*this)[n];
  }

  reference at(size_type n) {
    enforce(n < size(), std::__throw_out_of_range, "");
    return (*this)[n];
  }

  // C++11 21.4.6 modifiers:
  basic_fbstring& operator+=(const basic_fbstring& str) {
    return append(str);
  }

  basic_fbstring& operator+=(const value_type* s) {
    return append(s);
  }

  basic_fbstring& operator+=(const value_type c) {
    push_back(c);
    return *this;
  }

  basic_fbstring& operator+=(std::initializer_list<value_type> il) {
    append(il);
    return *this;
  }

  basic_fbstring& append(const basic_fbstring& str);

  basic_fbstring&
  append(const basic_fbstring& str, const size_type pos, size_type n);

  basic_fbstring& append(const value_type* s, size_type n);

  basic_fbstring& append(const value_type* s) {
    return append(s, traitsLength(s));
  }

  basic_fbstring& append(size_type n, value_type c);

  template<class InputIterator>
  basic_fbstring& append(InputIterator first, InputIterator last) {
    insert(end(), first, last);
    return *this;
  }

  basic_fbstring& append(std::initializer_list<value_type> il) {
    return append(il.begin(), il.end());
  }

  void push_back(const value_type c) {             // primitive
    store_.push_back(c);
  }

  basic_fbstring& assign(const basic_fbstring& str) {
    if (&str == this) return *this;
    return assign(str.data(), str.size());
  }

  basic_fbstring& assign(basic_fbstring&& str) {
    return *this = std::move(str);
  }

  basic_fbstring&
  assign(const basic_fbstring& str, const size_type pos, size_type n);

  basic_fbstring& assign(const value_type* s, const size_type n);

  basic_fbstring& assign(const value_type* s) {
    return assign(s, traitsLength(s));
  }

  basic_fbstring& assign(std::initializer_list<value_type> il) {
    return assign(il.begin(), il.end());
  }

  template <class ItOrLength, class ItOrChar>
  basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
    return replace(begin(), end(), first_or_n, last_or_c);
  }

  basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
    return insert(pos1, str.data(), str.size());
  }

  basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
                         size_type pos2, size_type n) {
    enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
    procrustes(n, str.length() - pos2);
    return insert(pos1, str.data() + pos2, n);
  }

  basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
    enforce(pos <= length(), std::__throw_out_of_range, "");
    insert(begin() + pos, s, s + n);
    return *this;
  }

  basic_fbstring& insert(size_type pos, const value_type* s) {
    return insert(pos, s, traitsLength(s));
  }

  basic_fbstring& insert(size_type pos, size_type n, value_type c) {
    enforce(pos <= length(), std::__throw_out_of_range, "");
    insert(begin() + pos, n, c);
    return *this;
  }

  iterator insert(const_iterator p, const value_type c) {
    const size_type pos = p - cbegin();
    insert(p, 1, c);
    return begin() + pos;
  }

#ifndef _LIBSTDCXX_FBSTRING
 private:
  typedef std::basic_istream<value_type, traits_type> istream_type;
  istream_type& getlineImpl(istream_type& is, value_type delim);

 public:
  friend inline istream_type& getline(istream_type& is,
                                      basic_fbstring& str,
                                      value_type delim) {
    return str.getlineImpl(is, delim);
  }

  friend inline istream_type& getline(istream_type& is, basic_fbstring& str) {
    return getline(is, str, '\n');
  }
#endif

private:
 iterator
 insertImplDiscr(const_iterator i, size_type n, value_type c, std::true_type);

 template <class InputIter>
 iterator
 insertImplDiscr(const_iterator i, InputIter b, InputIter e, std::false_type);

 template <class FwdIterator>
 iterator insertImpl(
     const_iterator i,
     FwdIterator s1,
     FwdIterator s2,
     std::forward_iterator_tag);

 template <class InputIterator>
 iterator insertImpl(
     const_iterator i,
     InputIterator b,
     InputIterator e,
     std::input_iterator_tag);

public:
  template <class ItOrLength, class ItOrChar>
  iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
    using Sel = std::integral_constant<
        bool,
        std::numeric_limits<ItOrLength>::is_specialized>;
    return insertImplDiscr(p, first_or_n, last_or_c, Sel());
  }

  iterator insert(const_iterator p, std::initializer_list<value_type> il) {
    return insert(p, il.begin(), il.end());
  }

  basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
    Invariant checker(*this);

    enforce(pos <= length(), std::__throw_out_of_range, "");
    procrustes(n, length() - pos);
    std::copy(begin() + pos + n, end(), begin() + pos);
    resize(length() - n);
    return *this;
  }

  iterator erase(iterator position) {
    const size_type pos(position - begin());
    enforce(pos <= size(), std::__throw_out_of_range, "");
    erase(pos, 1);
    return begin() + pos;
  }

  iterator erase(iterator first, iterator last) {
    const size_type pos(first - begin());
    erase(pos, last - first);
    return begin() + pos;
  }

  // Replaces at most n1 chars of *this, starting with pos1 with the
  // content of str
  basic_fbstring& replace(size_type pos1, size_type n1,
                          const basic_fbstring& str) {
    return replace(pos1, n1, str.data(), str.size());
  }

  // Replaces at most n1 chars of *this, starting with pos1,
  // with at most n2 chars of str starting with pos2
  basic_fbstring& replace(size_type pos1, size_type n1,
                          const basic_fbstring& str,
                          size_type pos2, size_type n2) {
    enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
    return replace(pos1, n1, str.data() + pos2,
                   std::min(n2, str.size() - pos2));
  }

  // Replaces at most n1 chars of *this, starting with pos, with chars from s
  basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
    return replace(pos, n1, s, traitsLength(s));
  }

  // Replaces at most n1 chars of *this, starting with pos, with n2
  // occurrences of c
  //
  // consolidated with
  //
  // Replaces at most n1 chars of *this, starting with pos, with at
  // most n2 chars of str.  str must have at least n2 chars.
  template <class StrOrLength, class NumOrChar>
  basic_fbstring& replace(size_type pos, size_type n1,
                          StrOrLength s_or_n2, NumOrChar n_or_c) {
    Invariant checker(*this);

    enforce(pos <= size(), std::__throw_out_of_range, "");
    procrustes(n1, length() - pos);
    const iterator b = begin() + pos;
    return replace(b, b + n1, s_or_n2, n_or_c);
  }

  basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
    return replace(i1, i2, str.data(), str.length());
  }

  basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
    return replace(i1, i2, s, traitsLength(s));
  }

private:
 basic_fbstring& replaceImplDiscr(
     iterator i1,
     iterator i2,
     const value_type* s,
     size_type n,
     std::integral_constant<int, 2>);

 basic_fbstring& replaceImplDiscr(
     iterator i1,
     iterator i2,
     size_type n2,
     value_type c,
     std::integral_constant<int, 1>);

 template <class InputIter>
 basic_fbstring& replaceImplDiscr(
     iterator i1,
     iterator i2,
     InputIter b,
     InputIter e,
     std::integral_constant<int, 0>);

private:
 template <class FwdIterator>
 bool replaceAliased(iterator /* i1 */,
                     iterator /* i2 */,
                     FwdIterator /* s1 */,
                     FwdIterator /* s2 */,
                     std::false_type) {
    return false;
  }

  template <class FwdIterator>
  bool replaceAliased(
      iterator i1,
      iterator i2,
      FwdIterator s1,
      FwdIterator s2,
      std::true_type);

  template <class FwdIterator>
  void replaceImpl(
      iterator i1,
      iterator i2,
      FwdIterator s1,
      FwdIterator s2,
      std::forward_iterator_tag);

  template <class InputIterator>
  void replaceImpl(
      iterator i1,
      iterator i2,
      InputIterator b,
      InputIterator e,
      std::input_iterator_tag);

 public:
  template <class T1, class T2>
  basic_fbstring& replace(iterator i1, iterator i2,
                          T1 first_or_n_or_s, T2 last_or_c_or_n) {
    constexpr bool num1 = std::numeric_limits<T1>::is_specialized,
                   num2 = std::numeric_limits<T2>::is_specialized;
    using Sel =
        std::integral_constant<int, num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>;
    return replaceImplDiscr(i1, i2, first_or_n_or_s, last_or_c_or_n, Sel());
  }

  size_type copy(value_type* s, size_type n, size_type pos = 0) const {
    enforce(pos <= size(), std::__throw_out_of_range, "");
    procrustes(n, size() - pos);

    if (n != 0) {
      fbstring_detail::podCopy(data() + pos, data() + pos + n, s);
    }
    return n;
  }

  void swap(basic_fbstring& rhs) {
    store_.swap(rhs.store_);
  }

  const value_type* c_str() const {
    return store_.c_str();
  }

  const value_type* data() const { return c_str(); }

  allocator_type get_allocator() const {
    return allocator_type();
  }

  size_type find(const basic_fbstring& str, size_type pos = 0) const {
    return find(str.data(), pos, str.length());
  }

  size_type find(const value_type* needle, size_type pos, size_type nsize)
      const;

  size_type find(const value_type* s, size_type pos = 0) const {
    return find(s, pos, traitsLength(s));
  }

  size_type find (value_type c, size_type pos = 0) const {
    return find(&c, pos, 1);
  }

  size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
    return rfind(str.data(), pos, str.length());
  }

  size_type rfind(const value_type* s, size_type pos, size_type n) const;

  size_type rfind(const value_type* s, size_type pos = npos) const {
    return rfind(s, pos, traitsLength(s));
  }

  size_type rfind(value_type c, size_type pos = npos) const {
    return rfind(&c, pos, 1);
  }

  size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
    return find_first_of(str.data(), pos, str.length());
  }

  size_type find_first_of(const value_type* s, size_type pos, size_type n)
      const;

  size_type find_first_of(const value_type* s, size_type pos = 0) const {
    return find_first_of(s, pos, traitsLength(s));
  }

  size_type find_first_of(value_type c, size_type pos = 0) const {
    return find_first_of(&c, pos, 1);
  }

  size_type find_last_of(const basic_fbstring& str, size_type pos = npos)
      const {
    return find_last_of(str.data(), pos, str.length());
  }

  size_type find_last_of(const value_type* s, size_type pos, size_type n) const;

  size_type find_last_of (const value_type* s,
                          size_type pos = npos) const {
    return find_last_of(s, pos, traitsLength(s));
  }

  size_type find_last_of (value_type c, size_type pos = npos) const {
    return find_last_of(&c, pos, 1);
  }

  size_type find_first_not_of(const basic_fbstring& str,
                              size_type pos = 0) const {
    return find_first_not_of(str.data(), pos, str.size());
  }

  size_type find_first_not_of(const value_type* s, size_type pos, size_type n)
      const;

  size_type find_first_not_of(const value_type* s,
                              size_type pos = 0) const {
    return find_first_not_of(s, pos, traitsLength(s));
  }

  size_type find_first_not_of(value_type c, size_type pos = 0) const {
    return find_first_not_of(&c, pos, 1);
  }

  size_type find_last_not_of(const basic_fbstring& str,
                             size_type pos = npos) const {
    return find_last_not_of(str.data(), pos, str.length());
  }

  size_type find_last_not_of(const value_type* s, size_type pos, size_type n)
      const;

  size_type find_last_not_of(const value_type* s,
                             size_type pos = npos) const {
    return find_last_not_of(s, pos, traitsLength(s));
  }

  size_type find_last_not_of (value_type c, size_type pos = npos) const {
    return find_last_not_of(&c, pos, 1);
  }

  basic_fbstring substr(size_type pos = 0, size_type n = npos) const& {
    enforce(pos <= size(), std::__throw_out_of_range, "");
    return basic_fbstring(data() + pos, std::min(n, size() - pos));
  }

  basic_fbstring substr(size_type pos = 0, size_type n = npos) && {
    enforce(pos <= size(), std::__throw_out_of_range, "");
    erase(0, pos);
    if (n < size()) {
      resize(n);
    }
    return std::move(*this);
  }

  int compare(const basic_fbstring& str) const {
    // FIX due to Goncalo N M de Carvalho July 18, 2005
    return compare(0, size(), str);
  }

  int compare(size_type pos1, size_type n1,
              const basic_fbstring& str) const {
    return compare(pos1, n1, str.data(), str.size());
  }

  int compare(size_type pos1, size_type n1,
              const value_type* s) const {
    return compare(pos1, n1, s, traitsLength(s));
  }

  int compare(size_type pos1, size_type n1,
              const value_type* s, size_type n2) const {
    enforce(pos1 <= size(), std::__throw_out_of_range, "");
    procrustes(n1, size() - pos1);
    // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
    const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
    return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
  }

  int compare(size_type pos1, size_type n1,
              const basic_fbstring& str,
              size_type pos2, size_type n2) const {
    enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
    return compare(pos1, n1, str.data() + pos2,
                   std::min(n2, str.size() - pos2));
  }

  // Code from Jean-Francois Bastien (03/26/2007)
  int compare(const value_type* s) const {
    // Could forward to compare(0, size(), s, traitsLength(s))
    // but that does two extra checks
    const size_type n1(size()), n2(traitsLength(s));
    const int r = traits_type::compare(data(), s, std::min(n1, n2));
    return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
  }

private:
  // Data
  Storage store_;
};

template <typename E, class T, class A, class S>
FOLLY_MALLOC_NOINLINE inline typename basic_fbstring<E, T, A, S>::size_type
basic_fbstring<E, T, A, S>::traitsLength(const value_type* s) {
  return s ? traits_type::length(s)
           : (std::__throw_logic_error(
                  "basic_fbstring: null pointer initializer not valid"),
              0);
}

template <typename E, class T, class A, class S>
inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
    const basic_fbstring& lhs) {
  Invariant checker(*this);

  if (FBSTRING_UNLIKELY(&lhs == this)) {
    return *this;
  }

  return assign(lhs.data(), lhs.size());
}

// Move assignment
template <typename E, class T, class A, class S>
inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
    basic_fbstring&& goner) noexcept {
  if (FBSTRING_UNLIKELY(&goner == this)) {
    // Compatibility with std::basic_string<>,
    // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
    return *this;
  }
  // No need of this anymore
  this->~basic_fbstring();
  // Move the goner into this
  new (&store_) S(std::move(goner.store_));
  return *this;
}

template <typename E, class T, class A, class S>
inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
    const value_type c) {
  Invariant checker(*this);

  if (empty()) {
    store_.expandNoinit(1);
  } else if (store_.isShared()) {
    basic_fbstring(1, c).swap(*this);
    return *this;
  } else {
    store_.shrink(size() - 1);
  }
  front() = c;
  return *this;
}

template <typename E, class T, class A, class S>
inline void basic_fbstring<E, T, A, S>::resize(
    const size_type n, const value_type c /*= value_type()*/) {
  Invariant checker(*this);

  auto size = this->size();
  if (n <= size) {
    store_.shrink(size - n);
  } else {
    auto const delta = n - size;
    auto pData = store_.expandNoinit(delta);
    fbstring_detail::podFill(pData, pData + delta, c);
  }
  FBSTRING_ASSERT(this->size() == n);
}

template <typename E, class T, class A, class S>
inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
    const basic_fbstring& str) {
#ifndef NDEBUG
  auto desiredSize = size() + str.size();
#endif
  append(str.data(), str.size());
  FBSTRING_ASSERT(size() == desiredSize);
  return *this;
}

template <typename E, class T, class A, class S>
inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
    const basic_fbstring& str, const size_type pos, size_type n) {
  const size_type sz = str.size();
  enforce(pos <= sz, std::__throw_out_of_range, "");
  procrustes(n, sz - pos);
  return append(str.data() + pos, n);
}

template <typename E, class T, class A, class S>
FOLLY_MALLOC_NOINLINE inline basic_fbstring<E, T, A, S>&
basic_fbstring<E, T, A, S>::append(const value_type* s, size_type n) {
  Invariant checker(*this);

  if (FBSTRING_UNLIKELY(!n)) {
    // Unlikely but must be done
    return *this;
  }
  auto const oldSize = size();
  auto const oldData = data();
  auto pData = store_.expandNoinit(n, /* expGrowth = */ true);

  // Check for aliasing (rare). We could use "<=" here but in theory
  // those do not work for pointers unless the pointers point to
  // elements in the same array. For that reason we use
  // std::less_equal, which is guaranteed to offer a total order
  // over pointers. See discussion at http://goo.gl/Cy2ya for more
  // info.
  std::less_equal<const value_type*> le;
  if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
    FBSTRING_ASSERT(le(s + n, oldData + oldSize));
    // expandNoinit() could have moved the storage, restore the source.
    s = data() + (s - oldData);
    fbstring_detail::podMove(s, s + n, pData);
  } else {
    fbstring_detail::podCopy(s, s + n, pData);
  }

  FBSTRING_ASSERT(size() == oldSize + n);
  return *this;
}

template <typename E, class T, class A, class S>
inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
    size_type n, value_type c) {
  Invariant checker(*this);
  auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
  fbstring_detail::podFill(pData, pData + n, c);
  return *this;
}

template <typename E, class T, class A, class S>
inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::assign(
    const basic_fbstring& str, const size_type pos, size_type n) {
  const size_type sz = str.size();
  enforce(pos <= sz, std::__throw_out_of_range, "");
  procrustes(n, sz - pos);
  return assign(str.data() + pos, n);
}

template <typename E, class T, class A, class S>
FOLLY_MALLOC_NOINLINE inline basic_fbstring<E, T, A, S>&
basic_fbstring<E, T, A, S>::assign(const value_type* s, const size_type n) {
  Invariant checker(*this);

  if (n == 0) {
    resize(0);
  } else if (size() >= n) {
    // s can alias this, we need to use podMove.
    fbstring_detail::podMove(s, s + n, store_.mutableData());
    store_.shrink(size() - n);
    FBSTRING_ASSERT(size() == n);
  } else {
    // If n is larger than size(), s cannot alias this string's
    // storage.
    resize(0);
    // Do not use exponential growth here: assign() should be tight,
    // to mirror the behavior of the equivalent constructor.
    fbstring_detail::podCopy(s, s + n, store_.expandNoinit(n));
  }

  FBSTRING_ASSERT(size() == n);
  return *this;
}

#ifndef _LIBSTDCXX_FBSTRING
template <typename E, class T, class A, class S>
inline typename basic_fbstring<E, T, A, S>::istream_type&
basic_fbstring<E, T, A, S>::getlineImpl(istream_type & is, value_type delim) {
  Invariant checker(*this);

  clear();
  size_t size = 0;
  while (true) {
    size_t avail = capacity() - size;
    // fbstring has 1 byte extra capacity for the null terminator,
    // and getline null-terminates the read string.
    is.getline(store_.expandNoinit(avail), avail + 1, delim);
    size += is.gcount();

    if (is.bad() || is.eof() || !is.fail()) {
      // Done by either failure, end of file, or normal read.
      if (!is.bad() && !is.eof()) {
        --size; // gcount() also accounts for the delimiter.
      }
      resize(size);
      break;
    }

    FBSTRING_ASSERT(size == this->size());
    FBSTRING_ASSERT(size == capacity());
    // Start at minimum allocation 63 + terminator = 64.
    reserve(std::max<size_t>(63, 3 * size / 2));
    // Clear the error so we can continue reading.
    is.clear();
  }
  return is;
}
#endif

template <typename E, class T, class A, class S>
inline typename basic_fbstring<E, T, A, S>::size_type
basic_fbstring<E, T, A, S>::find(
    const value_type* needle, const size_type pos, const size_type nsize)
    const {
  auto const size = this->size();
  // nsize + pos can overflow (eg pos == npos), guard against that by checking
  // that nsize + pos does not wrap around.
  if (nsize + pos > size || nsize + pos < pos) {
    return npos;
  }

  if (nsize == 0) {
    return pos;
  }
  // Don't use std::search, use a Boyer-Moore-like trick by comparing
  // the last characters first
  auto const haystack = data();
  auto const nsize_1 = nsize - 1;
  auto const lastNeedle = needle[nsize_1];

  // Boyer-Moore skip value for the last char in the needle. Zero is
  // not a valid value; skip will be computed the first time it's
  // needed.
  size_type skip = 0;

  const E* i = haystack + pos;
  auto iEnd = haystack + size - nsize_1;

  while (i < iEnd) {
    // Boyer-Moore: match the last element in the needle
    while (i[nsize_1] != lastNeedle) {
      if (++i == iEnd) {
        // not found
        return npos;
      }
    }
    // Here we know that the last char matches
    // Continue in pedestrian mode
    for (size_t j = 0;;) {
      FBSTRING_ASSERT(j < nsize);
      if (i[j] != needle[j]) {
        // Not found, we can skip
        // Compute the skip value lazily
        if (skip == 0) {
          skip = 1;
          while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
            ++skip;
          }
        }
        i += skip;
        break;
      }
      // Check if done searching
      if (++j == nsize) {
        // Yay
        return i - haystack;
      }
    }
  }
  return npos;
}

template <typename E, class T, class A, class S>
inline typename basic_fbstring<E, T, A, S>::iterator
basic_fbstring<E, T, A, S>::insertImplDiscr(
    const_iterator i, size_type n, value_type c, std::true_type) {
  Invariant checker(*this);

  FBSTRING_ASSERT(i >= cbegin() && i <= cend());
  const size_type pos = i - cbegin();

  auto oldSize = size();
  store_.expandNoinit(n, /* expGrowth = */ true);
  auto b = begin();
  fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
  fbstring_detail::podFill(b + pos, b + pos + n, c);

  return b + pos;
}

template <typename E, class T, class A, class S>
template <class InputIter>
inline typename basic_fbstring<E, T, A, S>::iterator
basic_fbstring<E, T, A, S>::insertImplDiscr(
    const_iterator i, InputIter b, InputIter e, std::false_type) {
  return insertImpl(
      i, b, e, typename std::iterator_traits<InputIter>::iterator_category());
}

template <typename E, class T, class A, class S>
template <class FwdIterator>
inline typename basic_fbstring<E, T, A, S>::iterator
basic_fbstring<E, T, A, S>::insertImpl(
    const_iterator i,
    FwdIterator s1,
    FwdIterator s2,
    std::forward_iterator_tag) {
  Invariant checker(*this);

  FBSTRING_ASSERT(i >= cbegin() && i <= cend());
  const size_type pos = i - cbegin();
  auto n = std::distance(s1, s2);
  FBSTRING_ASSERT(n >= 0);

  auto oldSize = size();
  store_.expandNoinit(n, /* expGrowth = */ true);
  auto b = begin();
  fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
  std::copy(s1, s2, b + pos);

  return b + pos;
}

template <typename E, class T, class A, class S>
template <class InputIterator>
inline typename basic_fbstring<E, T, A, S>::iterator
basic_fbstring<E, T, A, S>::insertImpl(
    const_iterator i,
    InputIterator b,
    InputIterator e,
    std::input_iterator_tag) {
  const auto pos = i - cbegin();
  basic_fbstring temp(cbegin(), i);
  for (; b != e; ++b) {
    temp.push_back(*b);
  }
  temp.append(i, cend());
  swap(temp);
  return begin() + pos;
}

template <typename E, class T, class A, class S>
inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
    iterator i1,
    iterator i2,
    const value_type* s,
    size_type n,
    std::integral_constant<int, 2>) {
  FBSTRING_ASSERT(i1 <= i2);
  FBSTRING_ASSERT(begin() <= i1 && i1 <= end());
  FBSTRING_ASSERT(begin() <= i2 && i2 <= end());
  return replace(i1, i2, s, s + n);
}

template <typename E, class T, class A, class S>
inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
    iterator i1,
    iterator i2,
    size_type n2,
    value_type c,
    std::integral_constant<int, 1>) {
  const size_type n1 = i2 - i1;
  if (n1 > n2) {
    std::fill(i1, i1 + n2, c);
    erase(i1 + n2, i2);
  } else {
    std::fill(i1, i2, c);
    insert(i2, n2 - n1, c);
  }
  FBSTRING_ASSERT(isSane());
  return *this;
}

template <typename E, class T, class A, class S>
template <class InputIter>
inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
    iterator i1,
    iterator i2,
    InputIter b,
    InputIter e,
    std::integral_constant<int, 0>) {
  using Cat = typename std::iterator_traits<InputIter>::iterator_category;
  replaceImpl(i1, i2, b, e, Cat());
  return *this;
}

template <typename E, class T, class A, class S>
template <class FwdIterator>
inline bool basic_fbstring<E, T, A, S>::replaceAliased(
    iterator i1, iterator i2, FwdIterator s1, FwdIterator s2, std::true_type) {
  std::less_equal<const value_type*> le{};
  const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
  if (!aliased) {
    return false;
  }
  // Aliased replace, copy to new string
  basic_fbstring temp;
  temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
  temp.append(begin(), i1).append(s1, s2).append(i2, end());
  swap(temp);
  return true;
}

template <typename E, class T, class A, class S>
template <class FwdIterator>
inline void basic_fbstring<E, T, A, S>::replaceImpl(
    iterator i1,
    iterator i2,
    FwdIterator s1,
    FwdIterator s2,
    std::forward_iterator_tag) {
  Invariant checker(*this);

  // Handle aliased replace
  using Sel = std::integral_constant<
      bool,
      std::is_same<FwdIterator, iterator>::value ||
          std::is_same<FwdIterator, const_iterator>::value>;
  if (replaceAliased(i1, i2, s1, s2, Sel())) {
    return;
  }

  auto const n1 = i2 - i1;
  FBSTRING_ASSERT(n1 >= 0);
  auto const n2 = std::distance(s1, s2);
  FBSTRING_ASSERT(n2 >= 0);

  if (n1 > n2) {
    // shrinks
    std::copy(s1, s2, i1);
    erase(i1 + n2, i2);
  } else {
    // grows
    s1 = fbstring_detail::copy_n(s1, n1, i1).first;
    insert(i2, s1, s2);
  }
  FBSTRING_ASSERT(isSane());
}

template <typename E, class T, class A, class S>
template <class InputIterator>
inline void basic_fbstring<E, T, A, S>::replaceImpl(
    iterator i1,
    iterator i2,
    InputIterator b,
    InputIterator e,
    std::input_iterator_tag) {
  basic_fbstring temp(begin(), i1);
  temp.append(b, e).append(i2, end());
  swap(temp);
}

template <typename E, class T, class A, class S>
inline typename basic_fbstring<E, T, A, S>::size_type
basic_fbstring<E, T, A, S>::rfind(
    const value_type* s, size_type pos, size_type n) const {
  if (n > length()) {
    return npos;
  }
  pos = std::min(pos, length() - n);
  if (n == 0) {
    return pos;
  }

  const_iterator i(begin() + pos);
  for (;; --i) {
    if (traits_type::eq(*i, *s) && traits_type::compare(&*i, s, n) == 0) {
      return i - begin();
    }
    if (i == begin()) {
      break;
    }
  }
  return npos;
}

template <typename E, class T, class A, class S>
inline typename basic_fbstring<E, T, A, S>::size_type
basic_fbstring<E, T, A, S>::find_first_of(
    const value_type* s, size_type pos, size_type n) const {
  if (pos > length() || n == 0) {
    return npos;
  }
  const_iterator i(begin() + pos), finish(end());
  for (; i != finish; ++i) {
    if (traits_type::find(s, n, *i) != 0) {
      return i - begin();
    }
  }
  return npos;
}

template <typename E, class T, class A, class S>
inline typename basic_fbstring<E, T, A, S>::size_type
basic_fbstring<E, T, A, S>::find_last_of(
    const value_type* s, size_type pos, size_type n) const {
  if (!empty() && n > 0) {
    pos = std::min(pos, length() - 1);
    const_iterator i(begin() + pos);
    for (;; --i) {
      if (traits_type::find(s, n, *i) != 0) {
        return i - begin();
      }
      if (i == begin()) {
        break;
      }
    }
  }
  return npos;
}

template <typename E, class T, class A, class S>
inline typename basic_fbstring<E, T, A, S>::size_type
basic_fbstring<E, T, A, S>::find_first_not_of(
    const value_type* s, size_type pos, size_type n) const {
  if (pos < length()) {
    const_iterator i(begin() + pos), finish(end());
    for (; i != finish; ++i) {
      if (traits_type::find(s, n, *i) == 0) {
        return i - begin();
      }
    }
  }
  return npos;
}

template <typename E, class T, class A, class S>
inline typename basic_fbstring<E, T, A, S>::size_type
basic_fbstring<E, T, A, S>::find_last_not_of(
    const value_type* s, size_type pos, size_type n) const {
  if (!this->empty()) {
    pos = std::min(pos, size() - 1);
    const_iterator i(begin() + pos);
    for (;; --i) {
      if (traits_type::find(s, n, *i) == 0) {
        return i - begin();
      }
      if (i == begin()) {
        break;
      }
    }
  }
  return npos;
}

// non-member functions
// C++11 21.4.8.1/1
template <typename E, class T, class A, class S>
inline
basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
                                     const basic_fbstring<E, T, A, S>& rhs) {

  basic_fbstring<E, T, A, S> result;
  result.reserve(lhs.size() + rhs.size());
  result.append(lhs).append(rhs);
  return std::move(result);
}

// C++11 21.4.8.1/2
template <typename E, class T, class A, class S>
inline
basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
                                     const basic_fbstring<E, T, A, S>& rhs) {
  return std::move(lhs.append(rhs));
}

// C++11 21.4.8.1/3
template <typename E, class T, class A, class S>
inline
basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
                                     basic_fbstring<E, T, A, S>&& rhs) {
  if (rhs.capacity() >= lhs.size() + rhs.size()) {
    // Good, at least we don't need to reallocate
    return std::move(rhs.insert(0, lhs));
  }
  // Meh, no go. Forward to operator+(const&, const&).
  auto const& rhsC = rhs;
  return lhs + rhsC;
}

// C++11 21.4.8.1/4
template <typename E, class T, class A, class S>
inline
basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
                                     basic_fbstring<E, T, A, S>&& rhs) {
  return std::move(lhs.append(rhs));
}

// C++11 21.4.8.1/5
template <typename E, class T, class A, class S>
inline
basic_fbstring<E, T, A, S> operator+(
  const E* lhs,
  const basic_fbstring<E, T, A, S>& rhs) {
  //
  basic_fbstring<E, T, A, S> result;
  const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
  result.reserve(len + rhs.size());
  result.append(lhs, len).append(rhs);
  return result;
}

// C++11 21.4.8.1/6
template <typename E, class T, class A, class S>
inline
basic_fbstring<E, T, A, S> operator+(
  const E* lhs,
  basic_fbstring<E, T, A, S>&& rhs) {
  //
  const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
  if (rhs.capacity() >= len + rhs.size()) {
    // Good, at least we don't need to reallocate
    rhs.insert(rhs.begin(), lhs, lhs + len);
    return rhs;
  }
  // Meh, no go. Do it by hand since we have len already.
  basic_fbstring<E, T, A, S> result;
  result.reserve(len + rhs.size());
  result.append(lhs, len).append(rhs);
  return result;
}

// C++11 21.4.8.1/7
template <typename E, class T, class A, class S>
inline
basic_fbstring<E, T, A, S> operator+(
  E lhs,
  const basic_fbstring<E, T, A, S>& rhs) {

  basic_fbstring<E, T, A, S> result;
  result.reserve(1 + rhs.size());
  result.push_back(lhs);
  result.append(rhs);
  return result;
}

// C++11 21.4.8.1/8
template <typename E, class T, class A, class S>
inline
basic_fbstring<E, T, A, S> operator+(
  E lhs,
  basic_fbstring<E, T, A, S>&& rhs) {
  //
  if (rhs.capacity() > rhs.size()) {
    // Good, at least we don't need to reallocate
    rhs.insert(rhs.begin(), lhs);
    return rhs;
  }
  // Meh, no go. Forward to operator+(E, const&).
  auto const& rhsC = rhs;
  return lhs + rhsC;
}

// C++11 21.4.8.1/9
template <typename E, class T, class A, class S>
inline
basic_fbstring<E, T, A, S> operator+(
  const basic_fbstring<E, T, A, S>& lhs,
  const E* rhs) {

  typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
  typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;

  basic_fbstring<E, T, A, S> result;
  const size_type len = traits_type::length(rhs);
  result.reserve(lhs.size() + len);
  result.append(lhs).append(rhs, len);
  return result;
}

// C++11 21.4.8.1/10
template <typename E, class T, class A, class S>
inline
basic_fbstring<E, T, A, S> operator+(
  basic_fbstring<E, T, A, S>&& lhs,
  const E* rhs) {
  //
  return std::move(lhs += rhs);
}

// C++11 21.4.8.1/11
template <typename E, class T, class A, class S>
inline
basic_fbstring<E, T, A, S> operator+(
  const basic_fbstring<E, T, A, S>& lhs,
  E rhs) {

  basic_fbstring<E, T, A, S> result;
  result.reserve(lhs.size() + 1);
  result.append(lhs);
  result.push_back(rhs);
  return result;
}

// C++11 21.4.8.1/12
template <typename E, class T, class A, class S>
inline
basic_fbstring<E, T, A, S> operator+(
  basic_fbstring<E, T, A, S>&& lhs,
  E rhs) {
  //
  return std::move(lhs += rhs);
}

template <typename E, class T, class A, class S>
inline
bool operator==(const basic_fbstring<E, T, A, S>& lhs,
                const basic_fbstring<E, T, A, S>& rhs) {
  return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }

template <typename E, class T, class A, class S>
inline
bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
                const basic_fbstring<E, T, A, S>& rhs) {
  return rhs == lhs; }

template <typename E, class T, class A, class S>
inline
bool operator==(const basic_fbstring<E, T, A, S>& lhs,
                const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
  return lhs.compare(rhs) == 0; }

template <typename E, class T, class A, class S>
inline
bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
                const basic_fbstring<E, T, A, S>& rhs) {
  return !(lhs == rhs); }

template <typename E, class T, class A, class S>
inline
bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
                const basic_fbstring<E, T, A, S>& rhs) {
  return !(lhs == rhs); }

template <typename E, class T, class A, class S>
inline
bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
                const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
  return !(lhs == rhs); }

template <typename E, class T, class A, class S>
inline
bool operator<(const basic_fbstring<E, T, A, S>& lhs,
               const basic_fbstring<E, T, A, S>& rhs) {
  return lhs.compare(rhs) < 0; }

template <typename E, class T, class A, class S>
inline
bool operator<(const basic_fbstring<E, T, A, S>& lhs,
               const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
  return lhs.compare(rhs) < 0; }

template <typename E, class T, class A, class S>
inline
bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
               const basic_fbstring<E, T, A, S>& rhs) {
  return rhs.compare(lhs) > 0; }

template <typename E, class T, class A, class S>
inline
bool operator>(const basic_fbstring<E, T, A, S>& lhs,
               const basic_fbstring<E, T, A, S>& rhs) {
  return rhs < lhs; }

template <typename E, class T, class A, class S>
inline
bool operator>(const basic_fbstring<E, T, A, S>& lhs,
               const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
  return rhs < lhs; }

template <typename E, class T, class A, class S>
inline
bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
               const basic_fbstring<E, T, A, S>& rhs) {
  return rhs < lhs; }

template <typename E, class T, class A, class S>
inline
bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
                const basic_fbstring<E, T, A, S>& rhs) {
  return !(rhs < lhs); }

template <typename E, class T, class A, class S>
inline
bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
                const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
  return !(rhs < lhs); }

template <typename E, class T, class A, class S>
inline
bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
                const basic_fbstring<E, T, A, S>& rhs) {
  return !(rhs < lhs); }

template <typename E, class T, class A, class S>
inline
bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
                const basic_fbstring<E, T, A, S>& rhs) {
  return !(lhs < rhs); }

template <typename E, class T, class A, class S>
inline
bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
                const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
  return !(lhs < rhs); }

template <typename E, class T, class A, class S>
inline
bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
                const basic_fbstring<E, T, A, S>& rhs) {
 return !(lhs < rhs);
}

// C++11 21.4.8.8
template <typename E, class T, class A, class S>
void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
  lhs.swap(rhs);
}

// TODO: make this faster.
template <typename E, class T, class A, class S>
inline
std::basic_istream<
  typename basic_fbstring<E, T, A, S>::value_type,
  typename basic_fbstring<E, T, A, S>::traits_type>&
  operator>>(
    std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
    typename basic_fbstring<E, T, A, S>::traits_type>& is,
    basic_fbstring<E, T, A, S>& str) {
  typename std::basic_istream<E, T>::sentry sentry(is);
  typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
                             typename basic_fbstring<E, T, A, S>::traits_type>
                        __istream_type;
  typedef typename __istream_type::ios_base __ios_base;
  size_t extracted = 0;
  auto err = __ios_base::goodbit;
  if (sentry) {
    auto n = is.width();
    if (n <= 0) {
      n = str.max_size();
    }
    str.erase();
    for (auto got = is.rdbuf()->sgetc(); extracted != size_t(n); ++extracted) {
      if (got == T::eof()) {
        err |= __ios_base::eofbit;
        is.width(0);
        break;
      }
      if (isspace(got)) {
        break;
      }
      str.push_back(got);
      got = is.rdbuf()->snextc();
    }
  }
  if (!extracted) {
    err |= __ios_base::failbit;
  }
  if (err) {
    is.setstate(err);
  }
  return is;
}

template <typename E, class T, class A, class S>
inline
std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
                   typename basic_fbstring<E, T, A, S>::traits_type>&
operator<<(
  std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
  typename basic_fbstring<E, T, A, S>::traits_type>& os,
    const basic_fbstring<E, T, A, S>& str) {
#if _LIBCPP_VERSION
  typename std::basic_ostream<
    typename basic_fbstring<E, T, A, S>::value_type,
    typename basic_fbstring<E, T, A, S>::traits_type>::sentry __s(os);
  if (__s) {
    typedef std::ostreambuf_iterator<
      typename basic_fbstring<E, T, A, S>::value_type,
      typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
    size_t __len = str.size();
    bool __left =
      (os.flags() & std::ios_base::adjustfield) == std::ios_base::left;
    if (__pad_and_output(_Ip(os),
                         str.data(),
                         __left ? str.data() + __len : str.data(),
                         str.data() + __len,
                         os,
                         os.fill()).failed()) {
      os.setstate(std::ios_base::badbit | std::ios_base::failbit);
    }
  }
#elif defined(_MSC_VER)
  // MSVC doesn't define __ostream_insert
  os.write(str.data(), str.size());
#else
  std::__ostream_insert(os, str.data(), str.size());
#endif
  return os;
}

template <typename E1, class T, class A, class S>
constexpr typename basic_fbstring<E1, T, A, S>::size_type
    basic_fbstring<E1, T, A, S>::npos;

#ifndef _LIBSTDCXX_FBSTRING
// basic_string compatibility routines

template <typename E, class T, class A, class S>
inline
bool operator==(const basic_fbstring<E, T, A, S>& lhs,
                const std::string& rhs) {
  return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
}

template <typename E, class T, class A, class S>
inline
bool operator==(const std::string& lhs,
                const basic_fbstring<E, T, A, S>& rhs) {
  return rhs == lhs;
}

template <typename E, class T, class A, class S>
inline
bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
                const std::string& rhs) {
  return !(lhs == rhs);
}

template <typename E, class T, class A, class S>
inline
bool operator!=(const std::string& lhs,
                const basic_fbstring<E, T, A, S>& rhs) {
  return !(lhs == rhs);
}

#if !defined(_LIBSTDCXX_FBSTRING)
typedef basic_fbstring<char> fbstring;
#endif

// fbstring is relocatable
template <class T, class R, class A, class S>
FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);

#else
_GLIBCXX_END_NAMESPACE_VERSION
#endif

} // namespace folly

#ifndef _LIBSTDCXX_FBSTRING

// Hash functions to make fbstring usable with e.g. hash_map
//
// Handle interaction with different C++ standard libraries, which
// expect these types to be in different namespaces.

#define FOLLY_FBSTRING_HASH1(T)                                        \
  template <>                                                          \
  struct hash< ::folly::basic_fbstring<T>> {                           \
    size_t operator()(const ::folly::basic_fbstring<T>& s) const {     \
      return ::folly::hash::fnv32_buf(s.data(), s.size() * sizeof(T)); \
    }                                                                  \
  };

// The C++11 standard says that these four are defined
#define FOLLY_FBSTRING_HASH \
  FOLLY_FBSTRING_HASH1(char) \
  FOLLY_FBSTRING_HASH1(char16_t) \
  FOLLY_FBSTRING_HASH1(char32_t) \
  FOLLY_FBSTRING_HASH1(wchar_t)

namespace std {

FOLLY_FBSTRING_HASH

}  // namespace std

#if FOLLY_HAVE_DEPRECATED_ASSOC
#if defined(_GLIBCXX_SYMVER) && !defined(__BIONIC__)
namespace __gnu_cxx {

FOLLY_FBSTRING_HASH

}  // namespace __gnu_cxx
#endif // _GLIBCXX_SYMVER && !__BIONIC__
#endif // FOLLY_HAVE_DEPRECATED_ASSOC

#undef FOLLY_FBSTRING_HASH
#undef FOLLY_FBSTRING_HASH1

#endif // _LIBSTDCXX_FBSTRING

#pragma GCC diagnostic pop

#undef FBSTRING_DISABLE_SSO
#undef FBSTRING_SANITIZE_ADDRESS
#undef throw
#undef FBSTRING_LIKELY
#undef FBSTRING_UNLIKELY
#undef FBSTRING_ASSERT