folly/FixedString.h

   1 /*
   2  * Copyright 2017 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: Eric Niebler (eniebler)
  18 // Fixed-size string type, for constexpr string handling.
  19
  20 #pragma once
  21
  22 #include <cassert>
  23 #include <cstddef>
  24 #include <initializer_list>
  25 #include <iosfwd>
  26 #include <stdexcept>
  27 #include <string>
  28 #include <type_traits>
  29 #include <utility>
  30
  31 #include <folly/ConstexprMath.h>
  32 #include <folly/Portability.h>
  33 #include <folly/Range.h>
  34 #include <folly/Utility.h>
  35 #include <folly/portability/BitsFunctexcept.h>
  36 #include <folly/portability/Constexpr.h>
  37
  38 namespace folly {
  39
  40 template <class Char, std::size_t N>
  41 class BasicFixedString;
  42
  43 template <std::size_t N>
  44 using FixedString = BasicFixedString<char, N>;
  45
  46 namespace detail {
  47 namespace fixedstring {
  48
  49 // This is a template so that the class static npos can be defined in the
  50 // header.
  51 template <class = void>
  52 struct FixedStringBase_ {
  53   static constexpr std::size_t npos = static_cast<std::size_t>(-1);
  54 };
  55
  56 template <class Void>
  57 constexpr std::size_t FixedStringBase_<Void>::npos;
  58
  59 using FixedStringBase = FixedStringBase_<>;
  60
  61 // Intentionally NOT constexpr. By making this not constexpr, we make
  62 // checkOverflow below ill-formed in a constexpr context when the condition
  63 // it's testing for fails. In this way, precondition violations are reported
  64 // at compile-time instead of at runtime.
  65 [[noreturn]] inline void assertOutOfBounds() {
  66   assert(false && "Array index out of bounds in BasicFixedString");
  67   std::__throw_out_of_range("Array index out of bounds in BasicFixedString");
  68 }
  69
  70 constexpr std::size_t checkOverflow(std::size_t i, std::size_t max) {
  71   return i <= max ? i : (assertOutOfBounds(), max);
  72 }
  73
  74 constexpr std::size_t checkOverflowOrNpos(std::size_t i, std::size_t max) {
  75   return i == FixedStringBase::npos
  76       ? max
  77       : (i <= max ? i : (assertOutOfBounds(), max));
  78 }
  79
  80 // Intentionally NOT constexpr. See note above for assertOutOfBounds
  81 [[noreturn]] inline void assertNotNullTerminated() noexcept {
  82   assert(
  83       false &&
  84       "Non-null terminated string used to initialize a BasicFixedString");
  85   std::terminate(); // Fail hard, fail fast.
  86 }
  87
  88 // Parsing help for human readers: the following is a constexpr noexcept
  89 // function that accepts a reference to an array as a parameter and returns
  90 // a reference to the same array.
  91 template <class Char, std::size_t N>
  92 constexpr const Char (&checkNullTerminated(const Char (&a)[N]) noexcept)[N] {
  93   // Strange decltype(a)(a) used to make MSVC happy.
  94   return a[N - 1u] == Char(0)
  95 #ifndef NDEBUG
  96           // In Debug mode, guard against embedded nulls:
  97           && N - 1u == folly::detail::constexpr_strlen_internal(a, 0u)
  98 #endif
  99       ? decltype(a)(a)
 100       : (assertNotNullTerminated(), decltype(a)(a));
 101 }
 102
 103 enum class Cmp : int { LT = -1, EQ = 0, GT = 1 };
 104
 105 // Rather annoyingly, GCC's -Warray-bounds warning issues false positives for
 106 // this code. See https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61971
 107 #if defined(__GNUC__) && !defined(__clang__) && __GNUC__ <= 5
 108 #pragma GCC diagnostic push
 109 #pragma GCC diagnostic ignored "-Warray-bounds"
 110 #endif
 111
 112 template <class Left, class Right>
 113 constexpr Cmp compare_(
 114     const Left& left,
 115     std::size_t left_pos,
 116     std::size_t left_size,
 117     const Right& right,
 118     std::size_t right_pos,
 119     std::size_t right_size) noexcept {
 120   return left_pos == left_size
 121       ? (right_pos == right_size ? Cmp::EQ : Cmp::LT)
 122       : (right_pos == right_size ? Cmp::GT
 123                                  : (left[left_pos] < right[right_pos]
 124                                         ? Cmp::LT
 125                                         : (left[left_pos] > right[right_pos]
 126                                                ? Cmp::GT
 127                                                : fixedstring::compare_(
 128                                                      left,
 129                                                      left_pos + 1u,
 130                                                      left_size,
 131                                                      right,
 132                                                      right_pos + 1u,
 133                                                      right_size))));
 134 }
 135
 136 template <class Left, class Right>
 137 constexpr bool equal_(
 138     const Left& left,
 139     std::size_t left_size,
 140     const Right& right,
 141     std::size_t right_size) noexcept {
 142   return left_size == right_size &&
 143       Cmp::EQ == compare_(left, 0u, left_size, right, 0u, right_size);
 144 }
 145
 146 template <class Char, class Left, class Right>
 147 constexpr Char char_at_(
 148     const Left& left,
 149     std::size_t left_count,
 150     const Right& right,
 151     std::size_t right_count,
 152     std::size_t i) noexcept {
 153   return i < left_count
 154       ? left[i]
 155       : i < (left_count + right_count) ? right[i - left_count] : Char(0);
 156 }
 157
 158 template <class Char, class Left, class Right>
 159 constexpr Char char_at_(
 160     const Left& left,
 161     std::size_t left_size,
 162     std::size_t left_pos,
 163     std::size_t left_count,
 164     const Right& right,
 165     std::size_t right_pos,
 166     std::size_t right_count,
 167     std::size_t i) noexcept {
 168   return i < left_pos
 169       ? left[i]
 170       : (i < right_count + left_pos ? right[i - left_pos + right_pos]
 171                                     : (i < left_size - left_count + right_count
 172                                            ? left[i - right_count + left_count]
 173                                            : Char(0)));
 174 }
 175
 176 template <class Left, class Right>
 177 constexpr bool find_at_(
 178     const Left& left,
 179     const Right& right,
 180     std::size_t pos,
 181     std::size_t count) noexcept {
 182   return 0u == count || (left[pos + count - 1u] == right[count - 1u] &&
 183                          find_at_(left, right, pos, count - 1u));
 184 }
 185
 186 template <class Char, class Right>
 187 constexpr bool
 188 find_one_of_at_(Char ch, const Right& right, std::size_t pos) noexcept {
 189   return 0u != pos &&
 190       (ch == right[pos - 1u] || find_one_of_at_(ch, right, pos - 1u));
 191 }
 192
 193 template <class Left, class Right>
 194 constexpr std::size_t find_(
 195     const Left& left,
 196     std::size_t left_size,
 197     const Right& right,
 198     std::size_t pos,
 199     std::size_t count) noexcept {
 200   return find_at_(left, right, pos, count) ? pos
 201                                            : left_size <= pos + count
 202           ? FixedStringBase::npos
 203           : find_(left, left_size, right, pos + 1u, count);
 204 }
 205
 206 template <class Left, class Right>
 207 constexpr std::size_t rfind_(
 208     const Left& left,
 209     const Right& right,
 210     std::size_t pos,
 211     std::size_t count) noexcept {
 212   return find_at_(left, right, pos, count)
 213       ? pos
 214       : 0u == pos ? FixedStringBase::npos
 215                   : rfind_(left, right, pos - 1u, count);
 216 }
 217
 218 template <class Left, class Right>
 219 constexpr std::size_t find_first_of_(
 220     const Left& left,
 221     std::size_t left_size,
 222     const Right& right,
 223     std::size_t pos,
 224     std::size_t count) noexcept {
 225   return find_one_of_at_(left[pos], right, count) ? pos
 226                                                   : left_size <= pos + 1u
 227           ? FixedStringBase::npos
 228           : find_first_of_(left, left_size, right, pos + 1u, count);
 229 }
 230
 231 template <class Left, class Right>
 232 constexpr std::size_t find_first_not_of_(
 233     const Left& left,
 234     std::size_t left_size,
 235     const Right& right,
 236     std::size_t pos,
 237     std::size_t count) noexcept {
 238   return !find_one_of_at_(left[pos], right, count) ? pos
 239                                                    : left_size <= pos + 1u
 240           ? FixedStringBase::npos
 241           : find_first_not_of_(left, left_size, right, pos + 1u, count);
 242 }
 243
 244 template <class Left, class Right>
 245 constexpr std::size_t find_last_of_(
 246     const Left& left,
 247     const Right& right,
 248     std::size_t pos,
 249     std::size_t count) noexcept {
 250   return find_one_of_at_(left[pos], right, count)
 251       ? pos
 252       : 0u == pos ? FixedStringBase::npos
 253                   : find_last_of_(left, right, pos - 1u, count);
 254 }
 255
 256 template <class Left, class Right>
 257 constexpr std::size_t find_last_not_of_(
 258     const Left& left,
 259     const Right& right,
 260     std::size_t pos,
 261     std::size_t count) noexcept {
 262   return !find_one_of_at_(left[pos], right, count)
 263       ? pos
 264       : 0u == pos ? FixedStringBase::npos
 265                   : find_last_not_of_(left, right, pos - 1u, count);
 266 }
 267
 268 struct Helper {
 269   template <class Char, class Left, class Right, std::size_t... Is>
 270   static constexpr BasicFixedString<Char, sizeof...(Is)> concat_(
 271       const Left& left,
 272       std::size_t left_count,
 273       const Right& right,
 274       std::size_t right_count,
 275       folly::index_sequence<Is...> is) noexcept {
 276     return {left, left_count, right, right_count, is};
 277   }
 278
 279   template <class Char, class Left, class Right, std::size_t... Is>
 280   static constexpr BasicFixedString<Char, sizeof...(Is)> replace_(
 281       const Left& left,
 282       std::size_t left_size,
 283       std::size_t left_pos,
 284       std::size_t left_count,
 285       const Right& right,
 286       std::size_t right_pos,
 287       std::size_t right_count,
 288       folly::index_sequence<Is...> is) noexcept {
 289     return {left,
 290             left_size,
 291             left_pos,
 292             left_count,
 293             right,
 294             right_pos,
 295             right_count,
 296             is};
 297   }
 298
 299   template <class Char, std::size_t N>
 300   static constexpr const Char (
 301       &data_(const BasicFixedString<Char, N>& that) noexcept)[N + 1u] {
 302     return that.data_;
 303   }
 304 };
 305
 306 #if defined(__GNUC__) && !defined(__clang__) && __GNUC__ <= 4
 307 #pragma GCC diagnostic pop
 308 #endif
 309
 310 template <class T>
 311 FOLLY_CPP14_CONSTEXPR void constexpr_swap(T& a, T& b) noexcept(
 312     noexcept(a = T(std::move(a)))) {
 313   T tmp((std::move(a)));
 314   a = std::move(b);
 315   b = std::move(tmp);
 316 }
 317
 318 // For constexpr reverse iteration over a BasicFixedString
 319 template <class T>
 320 struct ReverseIterator {
 321  private:
 322   T* p_ = nullptr;
 323   struct dummy_ {
 324     T* p_ = nullptr;
 325   };
 326   using other = typename std::conditional<
 327       std::is_const<T>::value,
 328       ReverseIterator<typename std::remove_const<T>::type>,
 329       dummy_>::type;
 330
 331  public:
 332   using value_type = typename std::remove_const<T>::type;
 333   using reference = T&;
 334   using pointer = T*;
 335   using difference_type = std::ptrdiff_t;
 336   using iterator_category = std::random_access_iterator_tag;
 337
 338   constexpr ReverseIterator() = default;
 339   constexpr ReverseIterator(const ReverseIterator&) = default;
 340   FOLLY_CPP14_CONSTEXPR ReverseIterator& operator=(const ReverseIterator&) =
 341       default;
 342   constexpr explicit ReverseIterator(T* p) noexcept : p_(p) {}
 343   constexpr /* implicit */ ReverseIterator(const other& that) noexcept
 344       : p_(that.p_) {}
 345   friend constexpr bool operator==(
 346       ReverseIterator a,
 347       ReverseIterator b) noexcept {
 348     return a.p_ == b.p_;
 349   }
 350   friend constexpr bool operator!=(
 351       ReverseIterator a,
 352       ReverseIterator b) noexcept {
 353     return !(a == b);
 354   }
 355   constexpr reference operator*() const {
 356     return *(p_ - 1);
 357   }
 358   FOLLY_CPP14_CONSTEXPR ReverseIterator& operator++() noexcept {
 359     --p_;
 360     return *this;
 361   }
 362   FOLLY_CPP14_CONSTEXPR ReverseIterator operator++(int)noexcept {
 363     auto tmp(*this);
 364     --p_;
 365     return tmp;
 366   }
 367   FOLLY_CPP14_CONSTEXPR ReverseIterator& operator--() noexcept {
 368     ++p_;
 369     return *this;
 370   }
 371   FOLLY_CPP14_CONSTEXPR ReverseIterator operator--(int)noexcept {
 372     auto tmp(*this);
 373     ++p_;
 374     return tmp;
 375   }
 376   FOLLY_CPP14_CONSTEXPR ReverseIterator& operator+=(std::ptrdiff_t i) noexcept {
 377     p_ -= i;
 378     return *this;
 379   }
 380   friend constexpr ReverseIterator operator+(
 381       std::ptrdiff_t i,
 382       ReverseIterator that) noexcept {
 383     return ReverseIterator{that.p_ - i};
 384   }
 385   friend constexpr ReverseIterator operator+(
 386       ReverseIterator that,
 387       std::ptrdiff_t i) noexcept {
 388     return ReverseIterator{that.p_ - i};
 389   }
 390   FOLLY_CPP14_CONSTEXPR ReverseIterator& operator-=(std::ptrdiff_t i) noexcept {
 391     p_ += i;
 392     return *this;
 393   }
 394   friend constexpr ReverseIterator operator-(
 395       ReverseIterator that,
 396       std::ptrdiff_t i) noexcept {
 397     return ReverseIterator{that.p_ + i};
 398   }
 399   friend constexpr std::ptrdiff_t operator-(
 400       ReverseIterator a,
 401       ReverseIterator b) noexcept {
 402     return b.p_ - a.p_;
 403   }
 404   constexpr reference operator[](std::ptrdiff_t i) const noexcept {
 405     return *(*this + i);
 406   }
 407 };
 408
 409 } // namespace fixedstring
 410 } // namespace detail
 411
 412 // Defined in folly/Hash.h
 413 std::uint32_t hsieh_hash32_buf(const void* buf, std::size_t len);
 414
 415 /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
 416  * \class BasicFixedString
 417  *
 418  * \tparam Char The character type. Must be a scalar type.
 419  * \tparam N The capacity and max size of string instances of this type.
 420  *
 421  * \brief A class for holding up to `N` characters of type `Char` that is
 422  *        amenable to `constexpr` string manipulation. It is guaranteed to not
 423  *        perform any dynamic allocation.
 424  *
 425  * `BasicFixedString` is a `std::string` work-alike that stores characters in an
 426  * internal buffer. It has minor interface differences that make it easy to work
 427  * with strings in a `constexpr` context.
 428  *
 429  * \par Example:
 430  * \par
 431  * \code
 432  * constexpr auto hello = makeFixedString("hello");         // a FixedString<5>
 433  * constexpr auto world = makeFixedString("world");         // a FixedString<5>
 434  * constexpr auto hello_world = hello + ' ' + world + '!';  // a FixedString<12>
 435  * static_assert(hello_world == "hello world!", "neato!");
 436  * \endcode
 437  * \par
 438  * `FixedString<N>` is an alias for `BasicFixedString<char, N>`.
 439  *
 440  * \par Constexpr and In-place Mutation
 441  * \par
 442  * On a C++14 compiler, `BasicFixedString` supports the full `std::string`
 443  * interface as `constexpr` member functions. On a C++11 compiler, the mutating
 444  * members are not `constexpr`, but non-mutating alternatives, which create a
 445  * new string, can be used instead. For example, instead of this:
 446  * \par
 447  * \code
 448  * constexpr FixedString<10> replace_example_cpp14() {
 449  *   FixedString<10> test{"****"};
 450  *   test.replace(1, 2, "!!!!");
 451  *   return test; // returns "*!!!!*"
 452  * }
 453  * \endcode
 454  * \par
 455  * You might write this instead:
 456  * \par
 457  * \code
 458  * constexpr FixedString<10> replace_example_cpp11() {
 459  *   // GNU compilers have an extension that make it possible to create
 460  *   // FixedString objects with a `""_fs` user-defined literal.
 461  *   using namespace folly;
 462  *   return makeFixedString("****").creplace(1, 2, "!!!!"); // "*!!!!*"
 463  * }
 464  * \endcode
 465  *
 466  * \par User-defined Literals
 467  * Instead of using the `folly::makeFixedString` helper function, you can use
 468  * a user-defined literal to make `FixedString` instances. The UDL feature of
 469  * C++ has some limitations that make this less than ideal; you must tell the
 470  * compiler roughly how many characters are in the string. The suffixes `_fs4`,
 471  * `_fs8`, `_fs16`, `_fs32`, `_fs64`, and `_fs128` exist to create instances
 472  * of types `FixedString<4>`, `FixedString<8>`, etc. For example:
 473  * \par
 474  * \code
 475  * using namespace folly::string_literals;
 476  * constexpr auto hello = "hello"_fs8; // A FixedString<8> containing "hello"
 477  * \endcode
 478  * \par
 479  * See Error Handling below for what to expect when you try to exceed the
 480  * capacity of a `FixedString` by storing too many characters in it.
 481  * \par
 482  * If your compiler supports GNU extensions, there is one additional suffix you
 483  * can use: `_fs`. This suffix always creates `FixedString` objects of exactly
 484  * the right size. For example:
 485  * \par
 486  * \code
 487  * using namespace folly::string_literals;
 488  * // NOTE: Only works on compilers with GNU extensions enabled. Clang and
 489  * // gcc support this (-Wgnu-string-literal-operator-template):
 490  * constexpr auto hello = "hello"_fs; // A FixedString<5> containing "hello"
 491  * \endcode
 492  *
 493  * \par Error Handling:
 494  * The capacity of a `BasicFixedString` is set at compile time. When the user
 495  * asks the string to exceed its capacity, one of three things will happen,
 496  * depending on the context:
 497  *\par
 498  *  -# If the attempt is made while evaluating a constant expression, the
 499  *     program will fail to compile.
 500  *  -# Otherwise, if the program is being run in debug mode, it will `assert`.
 501  *  -# Otherwise, the failed operation will throw a `std::out_of_range`
 502  *     exception.
 503  *\par
 504  * This is also the case if an invalid offset is passed to any member function,
 505  * or if `pop_back` or `cpop_back` is called on an empty `BasicFixedString`.
 506  *
 507  * Member functions documented as having preconditions will assert in Debug
 508  * mode (`!defined(NDEBUG)`) on precondition failures. Those documented with
 509  * \b Throws clauses will throw the specified exception on failure. Those with
 510  * both a precondition and a \b Throws clause will assert in Debug and throw
 511  * in Release mode.
 512  */
 513 template <class Char, std::size_t N>
 514 class BasicFixedString : private detail::fixedstring::FixedStringBase {
 515  private:
 516   template <class, std::size_t>
 517   friend class BasicFixedString;
 518   friend struct detail::fixedstring::Helper;
 519
 520   // FUTURE: use constexpr_log2 to fold instantiations of BasicFixedString
 521   // together. All BasicFixedString<C, N> instantiations could share the
 522   // implementation of BasicFixedString<C, M>, where M is the next highest power
 523   // of 2 after N.
 524   //
 525   // Also, because of alignment of the data_ and size_ members, N should never
 526   // be smaller than `(alignof(std::size_t)/sizeof(C))-1` (-1 because of the
 527   // null terminator). OR, create a specialization for BasicFixedString<C, 0u>
 528   // that does not have a size_ member, since it is unnecessary.
 529   Char data_[N + 1u]; // +1 for the null terminator
 530   std::size_t size_; // Nbr of chars, not incl. null terminator. size_ <= N.
 531
 532   using Indices = folly::make_index_sequence<N>;
 533
 534   template <class That, std::size_t... Is>
 535   constexpr BasicFixedString(
 536       const That& that,
 537       std::size_t size,
 538       folly::index_sequence<Is...>,
 539       std::size_t pos = 0,
 540       std::size_t count = npos) noexcept
 541       : data_{(Is < (size - pos) && Is < count ? that[Is + pos] : Char(0))...,
 542               Char(0)},
 543         size_{folly::constexpr_min(size - pos, count)} {}
 544
 545   template <std::size_t... Is>
 546   constexpr BasicFixedString(
 547       std::size_t count,
 548       Char ch,
 549       folly::index_sequence<Is...>) noexcept
 550       : data_{((Is < count) ? ch : Char(0))..., Char(0)}, size_{count} {}
 551
 552   // Concatenation constructor
 553   template <class Left, class Right, std::size_t... Is>
 554   constexpr BasicFixedString(
 555       const Left& left,
 556       std::size_t left_size,
 557       const Right& right,
 558       std::size_t right_size,
 559       folly::index_sequence<Is...>) noexcept
 560       : data_{detail::fixedstring::char_at_<Char>(
 561                   left,
 562                   left_size,
 563                   right,
 564                   right_size,
 565                   Is)...,
 566               Char(0)},
 567         size_{left_size + right_size} {}
 568
 569   // Replace constructor
 570   template <class Left, class Right, std::size_t... Is>
 571   constexpr BasicFixedString(
 572       const Left& left,
 573       std::size_t left_size,
 574       std::size_t left_pos,
 575       std::size_t left_count,
 576       const Right& right,
 577       std::size_t right_pos,
 578       std::size_t right_count,
 579       folly::index_sequence<Is...>) noexcept
 580       : data_{detail::fixedstring::char_at_<Char>(
 581                   left,
 582                   left_size,
 583                   left_pos,
 584                   left_count,
 585                   right,
 586                   right_pos,
 587                   right_count,
 588                   Is)...,
 589               Char(0)},
 590         size_{left_size - left_count + right_count} {}
 591
 592  public:
 593   using size_type = std::size_t;
 594   using difference_type = std::ptrdiff_t;
 595   using reference = Char&;
 596   using const_reference = const Char&;
 597   using pointer = Char*;
 598   using const_pointer = const Char*;
 599   using iterator = Char*;
 600   using const_iterator = const Char*;
 601   using reverse_iterator = detail::fixedstring::ReverseIterator<Char>;
 602   using const_reverse_iterator =
 603       detail::fixedstring::ReverseIterator<const Char>;
 604
 605   using detail::fixedstring::FixedStringBase::npos;
 606
 607   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
 608    * Default construct
 609    * \post `size() == 0`
 610    * \post `at(0) == Char(0)`
 611    */
 612   constexpr BasicFixedString() : data_{}, size_{} {}
 613
 614   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
 615    * Copy construct
 616    * \post `size() == that.size()`
 617    * \post `0 == strncmp(data(), that.data(), size())`
 618    * \post `at(size()) == Char(0)`
 619    */
 620   constexpr BasicFixedString(const BasicFixedString& /*that*/) = default;
 621
 622   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
 623    * Construct from a differently-sized BasicFixedString
 624    * \pre `that.size() <= N`
 625    * \post `size() == that.size()`
 626    * \post `0 == strncmp(data(), that.data(), size())`
 627    * \post `at(size()) == Char(0)`
 628    * \throw std::out_of_range when that.size() > N. When M <= N, this
 629    *   constructor will never throw.
 630    * \note Conversions from larger-capacity BasicFixedString objects to smaller
 631    *   ones (`M > N`) are allowed as long as the *size()* of the source string
 632    *   is small enough.
 633    */
 634   template <std::size_t M>
 635   constexpr /* implicit */ BasicFixedString(
 636       const BasicFixedString<Char, M>& that) noexcept(M <= N)
 637       : BasicFixedString{that, 0u, that.size_} {}
 638
 639   // Why is this deleted? To avoid confusion with the constructor that takes
 640   // a const Char* and a count.
 641   template <std::size_t M>
 642   constexpr BasicFixedString(
 643       const BasicFixedString<Char, M>& that,
 644       std::size_t pos) noexcept(false) = delete;
 645
 646   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
 647    * Construct from an BasicFixedString, an offset, and a count
 648    * \param that The source string
 649    * \param pos The starting position in `that`
 650    * \param count The number of characters to copy. If `npos`, `count` is taken
 651    *              to be `that.size()-pos`.
 652    * \pre `pos <= that.size()`
 653    * \pre `count <= that.size()-pos && count <= N`
 654    * \post `size() == count`
 655    * \post `0 == strncmp(data(), that.data()+pos, size())`
 656    * \post `at(size()) == Char(0)`
 657    * \throw std::out_of_range when pos+count > that.size(), or when
 658    *        `count > N`
 659    */
 660   template <std::size_t M>
 661   constexpr BasicFixedString(
 662       const BasicFixedString<Char, M>& that,
 663       std::size_t pos,
 664       std::size_t count) noexcept(false)
 665       : BasicFixedString{
 666             that.data_,
 667             that.size_,
 668             folly::make_index_sequence<(M < N ? M : N)>{},
 669             pos,
 670             detail::fixedstring::checkOverflow(
 671                 detail::fixedstring::checkOverflowOrNpos(
 672                     count,
 673                     that.size_ -
 674                         detail::fixedstring::checkOverflow(pos, that.size_)),
 675                 N)} {}
 676
 677   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
 678    * Construct from a string literal
 679    * \pre `M-1 <= N`
 680    * \pre `that[M-1] == Char(0)`
 681    * \post `0 == strncmp(data(), that, M-1)`
 682    * \post `size() == M-1`
 683    * \post `at(size()) == Char(0)`
 684    */
 685   template <std::size_t M, class = typename std::enable_if<(M - 1u <= N)>::type>
 686   constexpr /* implicit */ BasicFixedString(const Char (&that)[M]) noexcept
 687       : BasicFixedString{detail::fixedstring::checkNullTerminated(that),
 688                          M - 1u,
 689                          folly::make_index_sequence<M - 1u>{}} {}
 690
 691   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
 692    * Construct from a `const Char*` and count
 693    * \pre `that` points to an array of at least `count` characters.
 694    * \pre `count <= N`
 695    * \post `size() == count`
 696    * \post `0 == strncmp(data(), that, size())`
 697    * \post `at(size()) == Char(0)`
 698    * \throw std::out_of_range when count > N
 699    */
 700   constexpr BasicFixedString(const Char* that, std::size_t count) noexcept(
 701       false)
 702       : BasicFixedString{that,
 703                          detail::fixedstring::checkOverflow(count, N),
 704                          Indices{}} {}
 705
 706   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
 707    * Construct an BasicFixedString that contains `count` characters, all
 708    *   of which are `ch`.
 709    * \pre `count <= N`
 710    * \post `size() == count`
 711    * \post `npos == find_first_not_of(ch)`
 712    * \post `at(size()) == Char(0)`
 713    * \throw std::out_of_range when count > N
 714    */
 715   constexpr BasicFixedString(std::size_t count, Char ch) noexcept(false)
 716       : BasicFixedString{detail::fixedstring::checkOverflow(count, N),
 717                          ch,
 718                          Indices{}} {}
 719
 720   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
 721    * Construct an BasicFixedString from a `std::initializer_list` of
 722    *   characters.
 723    * \pre `il.size() <= N`
 724    * \post `size() == count`
 725    * \post `0 == strncmp(data(), il.begin(), size())`
 726    * \post `at(size()) == Char(0)`
 727    * \throw std::out_of_range when il.size() > N
 728    */
 729   constexpr BasicFixedString(std::initializer_list<Char> il) noexcept(false)
 730       : BasicFixedString{il.begin(), il.size()} {}
 731
 732   FOLLY_CPP14_CONSTEXPR BasicFixedString& operator=(
 733       const BasicFixedString&) noexcept = default;
 734
 735   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
 736    * Assign from a `BasicFixedString<Char, M>`.
 737    * \pre `that.size() <= N`
 738    * \post `size() == that.size()`
 739    * \post `0 == strncmp(data(), that.begin(), size())`
 740    * \post `at(size()) == Char(0)`
 741    * \throw std::out_of_range when that.size() > N. When M <= N, this
 742    *   assignment operator will never throw.
 743    * \note Assignments from larger-capacity BasicFixedString objects to smaller
 744    *   ones (`M > N`) are allowed as long as the *size* of the source string is
 745    *   small enough.
 746    * \return `*this`
 747    */
 748   template <std::size_t M>
 749   FOLLY_CPP14_CONSTEXPR BasicFixedString& operator=(
 750       const BasicFixedString<Char, M>& that) noexcept(M <= N) {
 751     detail::fixedstring::checkOverflow(that.size_, N);
 752     size_ = that.copy(data_, that.size_);
 753     data_[size_] = Char(0);
 754     return *this;
 755   }
 756
 757   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
 758    * Assign from a null-terminated array of characters.
 759    * \pre `M < N`
 760    * \pre `that` has no embedded null characters
 761    * \pre `that[M-1]==Char(0)`
 762    * \post `size() == M-1`
 763    * \post `0 == strncmp(data(), that, size())`
 764    * \post `at(size()) == Char(0)`
 765    * \return `*this`
 766    */
 767   template <std::size_t M, class = typename std::enable_if<(M - 1u <= N)>::type>
 768   FOLLY_CPP14_CONSTEXPR BasicFixedString& operator=(
 769       const Char (&that)[M]) noexcept {
 770     return assign(detail::fixedstring::checkNullTerminated(that), M - 1u);
 771   }
 772
 773   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
 774    * Assign from an `initializer_list` of characters.
 775    * \pre `il.size() <= N`
 776    * \post `size() == il.size()`
 777    * \post `0 == strncmp(data(), il.begin(), size())`
 778    * \post `at(size()) == Char(0)`
 779    * \throw std::out_of_range when il.size() > N
 780    * \return `*this`
 781    */
 782   FOLLY_CPP14_CONSTEXPR BasicFixedString& operator=(
 783       std::initializer_list<Char> il) noexcept(false) {
 784     detail::fixedstring::checkOverflow(il.size(), N);
 785     for (std::size_t i = 0u; i < il.size(); ++i) {
 786       data_[i] = il.begin()[i];
 787     }
 788     size_ = il.size();
 789     data_[size_] = Char(0);
 790     return *this;
 791   }
 792
 793   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
 794    * Conversion to folly::Range
 795    * \return `Range<Char*>{begin(), end()}`
 796    */
 797   FOLLY_CPP14_CONSTEXPR Range<Char*> toRange() noexcept {
 798     return {begin(), end()};
 799   }
 800
 801   /**
 802    * \overload
 803    */
 804   constexpr Range<const Char*> toRange() const noexcept {
 805     return {begin(), end()};
 806   }
 807
 808   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
 809    * Conversion to std::basic_string<Char>
 810    * \return `std::basic_string<Char>{begin(), end()}`
 811    */
 812   /* implicit */ operator std::basic_string<Char>() const noexcept(false) {
 813     return std::basic_string<Char>{begin(), end()};
 814   }
 815
 816   std::basic_string<Char> toStdString() const noexcept(false) {
 817     return std::basic_string<Char>{begin(), end()};
 818   }
 819
 820   // Think hard about whether this is a good idea. It's certainly better than
 821   // an implicit conversion to `const Char*` since `delete "hi"_fs` will fail
 822   // to compile. But it creates ambiguities when passing a FixedString to an
 823   // API that has overloads for `const char*` and `folly::Range`, for instance.
 824   // using ArrayType = Char[N];
 825   // FOLLY_CPP14_CONSTEXPR /* implicit */ operator ArrayType&() noexcept {
 826   //   return data_;
 827   // }
 828
 829   // using ConstArrayType = const Char[N];
 830   // constexpr /* implicit */ operator ConstArrayType&() const noexcept {
 831   //   return data_;
 832   // }
 833
 834   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
 835    * Assigns a sequence of `count` characters of value `ch`.
 836    * \param count The count of characters.
 837    * \param ch
 838    * \pre `count <= N`
 839    * \post `size() == count`
 840    * \post `npos == find_first_not_of(ch)`
 841    * \post `at(size()) == Char(0)`
 842    * \throw std::out_of_range when count > N
 843    * \return `*this`
 844    */
 845   FOLLY_CPP14_CONSTEXPR BasicFixedString& assign(
 846       std::size_t count,
 847       Char ch) noexcept(false) {
 848     detail::fixedstring::checkOverflow(count, N);
 849     for (std::size_t i = 0u; i < count; ++i) {
 850       data_[i] = ch;
 851     }
 852     size_ = count;
 853     data_[size_] = Char(0);
 854     return *this;
 855   }
 856
 857   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
 858    * Assigns characters from an `BasicFixedString` to this object.
 859    * \note Equivalent to `assign(that, 0, that.size())`
 860    */
 861   template <std::size_t M>
 862   FOLLY_CPP14_CONSTEXPR BasicFixedString& assign(
 863       const BasicFixedString<Char, M>& that) noexcept(M <= N) {
 864     return *this = that;
 865   }
 866
 867   // Why is this overload deleted? So users aren't confused by the difference
 868   // between str.assign("foo", N) and str.assign("foo"_fs, N). In the former,
 869   // N is a count of characters. In the latter, it would be a position, which
 870   // totally changes the meaning of the code.
 871   template <std::size_t M>
 872   FOLLY_CPP14_CONSTEXPR BasicFixedString& assign(
 873       const BasicFixedString<Char, M>& that,
 874       std::size_t pos) noexcept(false) = delete;
 875
 876   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
 877    * Assigns `count` characters from an `BasicFixedString` to this object,
 878    *   starting at position `pos` in the source object.
 879    * \param that The source string.
 880    * \param pos The starting position in the source string.
 881    * \param count The number of characters to copy. If `npos`, `count` is taken
 882    *              to be `that.size()-pos`.
 883    * \pre `pos <= that.size()`
 884    * \pre `count <= that.size()-pos`
 885    * \pre `count <= N`
 886    * \post `size() == count`
 887    * \post `0 == strncmp(data(), that.begin() + pos, count)`
 888    * \post `at(size()) == Char(0)`
 889    * \throw std::out_of_range when pos > that.size() or count > that.size()-pos
 890    *        or count > N.
 891    * \return `*this`
 892    */
 893   template <std::size_t M>
 894   FOLLY_CPP14_CONSTEXPR BasicFixedString& assign(
 895       const BasicFixedString<Char, M>& that,
 896       std::size_t pos,
 897       std::size_t count) noexcept(false) {
 898     detail::fixedstring::checkOverflow(pos, that.size_);
 899     return assign(
 900         that.data_ + pos,
 901         detail::fixedstring::checkOverflowOrNpos(count, that.size_ - pos));
 902   }
 903
 904   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
 905    * Assigns characters from an `BasicFixedString` to this object.
 906    * \pre `that` contains no embedded nulls.
 907    * \pre `that[M-1] == Char(0)`
 908    * \note Equivalent to `assign(that, M - 1)`
 909    */
 910   template <std::size_t M, class = typename std::enable_if<(M - 1u <= N)>::type>
 911   FOLLY_CPP14_CONSTEXPR BasicFixedString& assign(
 912       const Char (&that)[M]) noexcept {
 913     return assign(detail::fixedstring::checkNullTerminated(that), M - 1u);
 914   }
 915
 916   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
 917    * Assigns `count` characters from a range of characters to this object.
 918    * \param that A pointer to a range of characters.
 919    * \param count The number of characters to copy.
 920    * \pre `that` points to at least `count` characters.
 921    * \pre `count <= N`
 922    * \post `size() == count`
 923    * \post `0 == strncmp(data(), that, count)`
 924    * \post `at(size()) == Char(0)`
 925    * \throw std::out_of_range when count > N
 926    * \return `*this`
 927    */
 928   FOLLY_CPP14_CONSTEXPR BasicFixedString& assign(
 929       const Char* that,
 930       std::size_t count) noexcept(false) {
 931     detail::fixedstring::checkOverflow(count, N);
 932     for (std::size_t i = 0u; i < count; ++i) {
 933       data_[i] = that[i];
 934     }
 935     size_ = count;
 936     data_[size_] = Char(0);
 937     return *this;
 938   }
 939
 940   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
 941    * Swap the contents of this string with `that`.
 942    */
 943   FOLLY_CPP14_CONSTEXPR void swap(BasicFixedString& that) noexcept {
 944     // less-than-or-equal here to copy the null terminator:
 945     for (std::size_t i = 0u; i <= folly::constexpr_max(size_, that.size_);
 946          ++i) {
 947       detail::fixedstring::constexpr_swap(data_[i], that.data_[i]);
 948     }
 949     detail::fixedstring::constexpr_swap(size_, that.size_);
 950   }
 951
 952   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
 953    * Return a pointer to a range of `size()+1` characters, the last of which
 954    * is `Char(0)`.
 955    */
 956   FOLLY_CPP14_CONSTEXPR Char* data() noexcept {
 957     return data_;
 958   }
 959
 960   /**
 961    * \overload
 962    */
 963   constexpr const Char* data() const noexcept {
 964     return data_;
 965   }
 966
 967   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
 968    * \return `data()`.
 969    */
 970   constexpr const Char* c_str() const noexcept {
 971     return data_;
 972   }
 973
 974   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
 975    * \return `data()`.
 976    */
 977   FOLLY_CPP14_CONSTEXPR Char* begin() noexcept {
 978     return data_;
 979   }
 980
 981   /**
 982    * \overload
 983    */
 984   constexpr const Char* begin() const noexcept {
 985     return data_;
 986   }
 987
 988   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
 989    * \return `data()`.
 990    */
 991   constexpr const Char* cbegin() const noexcept {
 992     return begin();
 993   }
 994
 995   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
 996    * \return `data() + size()`.
 997    */
 998   FOLLY_CPP14_CONSTEXPR Char* end() noexcept {
 999     return data_ + size_;
1000   }
1001
1002   /**
1003    * \overload
1004    */
1005   constexpr const Char* end() const noexcept {
1006     return data_ + size_;
1007   }
1008
1009   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
1010    * \return `data() + size()`.
1011    */
1012   constexpr const Char* cend() const noexcept {
1013     return end();
1014   }
1015
1016   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
1017    * Returns a reverse iterator to the first character of the reversed string.
1018    * It corresponds to the last + 1 character of the non-reversed string.
1019    */
1020   FOLLY_CPP14_CONSTEXPR reverse_iterator rbegin() noexcept {
1021     return reverse_iterator{data_ + size_};
1022   }
1023
1024   /**
1025    * \overload
1026    */
1027   constexpr const_reverse_iterator rbegin() const noexcept {
1028     return const_reverse_iterator{data_ + size_};
1029   }
1030
1031   /**
1032    * \note Equivalent to `rbegin()` on a const-qualified reference to `*this`.
1033    */
1034   constexpr const_reverse_iterator crbegin() const noexcept {
1035     return rbegin();
1036   }
1037
1038   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
1039    * Returns a reverse iterator to the last + 1 character of the reversed
1040    * string. It corresponds to the first character of the non-reversed string.
1041    */
1042   FOLLY_CPP14_CONSTEXPR reverse_iterator rend() noexcept {
1043     return reverse_iterator{data_};
1044   }
1045
1046   /**
1047    * \overload
1048    */
1049   constexpr const_reverse_iterator rend() const noexcept {
1050     return const_reverse_iterator{data_};
1051   }
1052
1053   /**
1054    * \note Equivalent to `rend()` on a const-qualified reference to `*this`.
1055    */
1056   constexpr const_reverse_iterator crend() const noexcept {
1057     return rend();
1058   }
1059
1060   /**
1061    * \return The number of `Char` elements in the string.
1062    */
1063   constexpr std::size_t size() const noexcept {
1064     return size_;
1065   }
1066
1067   /**
1068    * \return The number of `Char` elements in the string.
1069    */
1070   constexpr std::size_t length() const noexcept {
1071     return size_;
1072   }
1073
1074   /**
1075    * \return True if and only if `size() == 0`.
1076    */
1077   constexpr bool empty() const noexcept {
1078     return 0u == size_;
1079   }
1080
1081   /**
1082    * \return `N`.
1083    */
1084   static constexpr std::size_t capacity() noexcept {
1085     return N;
1086   }
1087
1088   /**
1089    * \return `N`.
1090    */
1091   static constexpr std::size_t max_size() noexcept {
1092     return N;
1093   }
1094
1095   // We would need to reimplement folly::Hash to make this
1096   // constexpr. :-(
1097   std::uint32_t hash() const noexcept {
1098     return folly::hsieh_hash32_buf(data_, size_);
1099   }
1100
1101   /**
1102    * \note `at(size())` is allowed will return `Char(0)`.
1103    * \return `*(data() + i)`
1104    * \throw std::out_of_range when i > size()
1105    */
1106   FOLLY_CPP14_CONSTEXPR Char& at(std::size_t i) noexcept(false) {
1107     return i <= size_
1108         ? data_[i]
1109         : (std::__throw_out_of_range("Out of range in BasicFixedString::at"),
1110            data_[size_]);
1111   }
1112
1113   /**
1114    * \overload
1115    */
1116   constexpr const Char& at(std::size_t i) const noexcept(false) {
1117     return i <= size_
1118         ? data_[i]
1119         : (std::__throw_out_of_range("Out of range in BasicFixedString::at"),
1120            data_[size_]);
1121   }
1122
1123   /**
1124    * \pre `i <= size()`
1125    * \note `(*this)[size()]` is allowed will return `Char(0)`.
1126    * \return `*(data() + i)`
1127    */
1128   FOLLY_CPP14_CONSTEXPR Char& operator[](std::size_t i) noexcept {
1129 #ifdef NDEBUG
1130     return data_[i];
1131 #else
1132     return data_[detail::fixedstring::checkOverflow(i, size_)];
1133 #endif
1134   }
1135
1136   /**
1137    * \overload
1138    */
1139   constexpr const Char& operator[](std::size_t i) const noexcept {
1140 #ifdef NDEBUG
1141     return data_[i];
1142 #else
1143     return data_[detail::fixedstring::checkOverflow(i, size_)];
1144 #endif
1145   }
1146
1147   /**
1148    * \note Equivalent to `(*this)[0]`
1149    */
1150   FOLLY_CPP14_CONSTEXPR Char& front() noexcept {
1151     return (*this)[0u];
1152   }
1153
1154   /**
1155    * \overload
1156    */
1157   constexpr const Char& front() const noexcept {
1158     return (*this)[0u];
1159   }
1160
1161   /**
1162    * \note Equivalent to `at(size()-1)`
1163    * \pre `!empty()`
1164    */
1165   FOLLY_CPP14_CONSTEXPR Char& back() noexcept {
1166 #ifdef NDEBUG
1167     return data_[size_ - 1u];
1168 #else
1169     return data_[size_ - detail::fixedstring::checkOverflow(1u, size_)];
1170 #endif
1171   }
1172
1173   /**
1174    * \overload
1175    */
1176   constexpr const Char& back() const noexcept {
1177 #ifdef NDEBUG
1178     return data_[size_ - 1u];
1179 #else
1180     return data_[size_ - detail::fixedstring::checkOverflow(1u, size_)];
1181 #endif
1182   }
1183
1184   /**
1185    * Clears the contents of this string.
1186    * \post `size() == 0u`
1187    * \post `at(size()) == Char(0)`
1188    */
1189   FOLLY_CPP14_CONSTEXPR void clear() noexcept {
1190     data_[0u] = Char(0);
1191     size_ = 0u;
1192   }
1193
1194   /**
1195    * \note Equivalent to `append(1u, ch)`.
1196    */
1197   FOLLY_CPP14_CONSTEXPR void push_back(Char ch) noexcept(false) {
1198     detail::fixedstring::checkOverflow(1u, N - size_);
1199     data_[size_] = ch;
1200     data_[++size_] = Char(0);
1201   }
1202
1203   /**
1204    * \note Equivalent to `cappend(1u, ch)`.
1205    */
1206   constexpr BasicFixedString<Char, N + 1u> cpush_back(Char ch) const noexcept {
1207     return cappend(ch);
1208   }
1209
1210   /**
1211    * Removes the last character from the string.
1212    * \pre `!empty()`
1213    * \post `size()` is one fewer than before calling `pop_back()`.
1214    * \post `at(size()) == Char(0)`
1215    * \post The characters in the half-open range `[0,size()-1)` are unmodified.
1216    * \throw std::out_of_range if empty().
1217    */
1218   FOLLY_CPP14_CONSTEXPR void pop_back() noexcept(false) {
1219     detail::fixedstring::checkOverflow(1u, size_);
1220     --size_;
1221     data_[size_] = Char(0);
1222   }
1223
1224   /**
1225    * Returns a new string with the first `size()-1` characters from this string.
1226    * \pre `!empty()`
1227    * \note Equivalent to `BasicFixedString<Char, N-1u>{*this, 0u, size()-1u}`
1228    * \throw std::out_of_range if empty().
1229    */
1230   constexpr BasicFixedString<Char, N - 1u> cpop_back() const noexcept(false) {
1231     return {*this, 0u, size_ - detail::fixedstring::checkOverflow(1u, size_)};
1232   }
1233
1234   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
1235    * Appends `count` copies of `ch` to this string.
1236    * \pre `count + old_size <= N`
1237    * \post The first `old_size` characters of the string are unmodified.
1238    * \post `size() == old_size + count`
1239    * \throw std::out_of_range if count > N - size().
1240    */
1241   FOLLY_CPP14_CONSTEXPR BasicFixedString& append(
1242       std::size_t count,
1243       Char ch) noexcept(false) {
1244     detail::fixedstring::checkOverflow(count, N - size_);
1245     for (std::size_t i = 0u; i < count; ++i)
1246       data_[size_ + i] = ch;
1247     size_ += count;
1248     data_[size_] = Char(0);
1249     return *this;
1250   }
1251
1252   /**
1253    * \note Equivalent to `append(*this, 0, that.size())`.
1254    */
1255   template <std::size_t M>
1256   FOLLY_CPP14_CONSTEXPR BasicFixedString& append(
1257       const BasicFixedString<Char, M>& that) noexcept(false) {
1258     return append(that, 0u, that.size_);
1259   }
1260
1261   // Why is this overload deleted? So as not to get confused with
1262   // append("null-terminated", N), where N would be a count instead
1263   // of a position.
1264   template <std::size_t M>
1265   FOLLY_CPP14_CONSTEXPR BasicFixedString& append(
1266       const BasicFixedString<Char, M>& that,
1267       std::size_t pos) noexcept(false) = delete;
1268
1269   /**
1270    * Appends `count` characters from another string to this one, starting at a
1271    * given offset, `pos`.
1272    * \param that The source string.
1273    * \param pos The starting position in the source string.
1274    * \param count The number of characters to append. If `npos`, `count` is
1275    *              taken to be `that.size()-pos`.
1276    * \pre `pos <= that.size()`
1277    * \pre `count <= that.size() - pos`
1278    * \pre `old_size + count <= N`
1279    * \post The first `old_size` characters of the string are unmodified.
1280    * \post `size() == old_size + count`
1281    * \post `at(size()) == Char(0)`
1282    * \throw std::out_of_range if pos + count > that.size() or if
1283    *        `old_size + count > N`.
1284    */
1285   template <std::size_t M>
1286   FOLLY_CPP14_CONSTEXPR BasicFixedString& append(
1287       const BasicFixedString<Char, M>& that,
1288       std::size_t pos,
1289       std::size_t count) noexcept(false) {
1290     detail::fixedstring::checkOverflow(pos, that.size_);
1291     count = detail::fixedstring::checkOverflowOrNpos(count, that.size_ - pos);
1292     detail::fixedstring::checkOverflow(count, N - size_);
1293     for (std::size_t i = 0u; i < count; ++i)
1294       data_[size_ + i] = that.data_[pos + i];
1295     size_ += count;
1296     data_[size_] = Char(0);
1297     return *this;
1298   }
1299
1300   /**
1301    * \note Equivalent to `append(that, strlen(that))`.
1302    */
1303   FOLLY_CPP14_CONSTEXPR BasicFixedString& append(const Char* that) noexcept(
1304       false) {
1305     return append(that, folly::constexpr_strlen(that));
1306   }
1307
1308   /**
1309    * Appends `count` characters from the specified character array.
1310    * \pre `that` points to a range of at least `count` characters.
1311    * \pre `count + old_size <= N`
1312    * \post The first `old_size` characters of the string are unmodified.
1313    * \post `size() == old_size + count`
1314    * \post `at(size()) == Char(0)`
1315    * \throw std::out_of_range if old_size + count > N.
1316    */
1317   FOLLY_CPP14_CONSTEXPR BasicFixedString& append(
1318       const Char* that,
1319       std::size_t count) noexcept(false) {
1320     detail::fixedstring::checkOverflow(count, N - size_);
1321     for (std::size_t i = 0u; i < count; ++i)
1322       data_[size_ + i] = that[i];
1323     size_ += count;
1324     data_[size_] = Char(0);
1325     return *this;
1326   }
1327
1328   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
1329    * Creates a new string by appending a character to an existing string, which
1330    *   is left unmodified.
1331    * \note Equivalent to `*this + ch`
1332    */
1333   constexpr BasicFixedString<Char, N + 1u> cappend(Char ch) const noexcept {
1334     return *this + ch;
1335   }
1336
1337   /**
1338    * Creates a new string by appending a string to an existing string, which
1339    *   is left unmodified.
1340    * \note Equivalent to `*this + ch`
1341    */
1342   template <std::size_t M>
1343   constexpr BasicFixedString<Char, N + M> cappend(
1344       const BasicFixedString<Char, M>& that) const noexcept {
1345     return *this + that;
1346   }
1347
1348   // Deleted to avoid confusion with append("char*", N), where N is a count
1349   // instead of a position.
1350   template <std::size_t M>
1351   constexpr BasicFixedString<Char, N + M> cappend(
1352       const BasicFixedString<Char, M>& that,
1353       std::size_t pos) const noexcept(false) = delete;
1354
1355   /**
1356    * Creates a new string by appending characters from one string to another,
1357    *   which is left unmodified.
1358    * \note Equivalent to `*this + that.substr(pos, count)`
1359    */
1360   template <std::size_t M>
1361   constexpr BasicFixedString<Char, N + M> cappend(
1362       const BasicFixedString<Char, M>& that,
1363       std::size_t pos,
1364       std::size_t count) const noexcept(false) {
1365     return creplace(size_, 0u, that, pos, count);
1366   }
1367
1368   /**
1369    * Creates a new string by appending a string literal to a string,
1370    *   which is left unmodified.
1371    * \note Equivalent to `*this + that`
1372    */
1373   template <std::size_t M>
1374   constexpr BasicFixedString<Char, N + M - 1u> cappend(
1375       const Char (&that)[M]) const noexcept {
1376     return creplace(size_, 0u, that);
1377   }
1378
1379   // Deleted to avoid confusion with append("char*", N), where N is a count
1380   // instead of a position
1381   template <std::size_t M>
1382   constexpr BasicFixedString<Char, N + M - 1u> cappend(
1383       const Char (&that)[M],
1384       std::size_t pos) const noexcept(false) = delete;
1385
1386   /**
1387    * Creates a new string by appending characters from one string to another,
1388    *   which is left unmodified.
1389    * \note Equivalent to `*this + makeFixedString(that).substr(pos, count)`
1390    */
1391   template <std::size_t M>
1392   constexpr BasicFixedString<Char, N + M - 1u>
1393   cappend(const Char (&that)[M], std::size_t pos, std::size_t count) const
1394       noexcept(false) {
1395     return creplace(size_, 0u, that, pos, count);
1396   }
1397
1398   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
1399    * Appends characters from a null-terminated string literal to this string.
1400    * \note Equivalent to `append(that)`.
1401    */
1402   FOLLY_CPP14_CONSTEXPR BasicFixedString& operator+=(const Char* that) noexcept(
1403       false) {
1404     return append(that);
1405   }
1406
1407   /**
1408    * Appends characters from another string to this one.
1409    * \note Equivalent to `append(that)`.
1410    */
1411   template <std::size_t M>
1412   FOLLY_CPP14_CONSTEXPR BasicFixedString& operator+=(
1413       const BasicFixedString<Char, M>& that) noexcept(false) {
1414     return append(that, 0u, that.size_);
1415   }
1416
1417   /**
1418    * Appends a character to this string.
1419    * \note Equivalent to `push_back(ch)`.
1420    */
1421   FOLLY_CPP14_CONSTEXPR BasicFixedString& operator+=(Char ch) noexcept(false) {
1422     push_back(ch);
1423     return *this;
1424   }
1425
1426   /**
1427    * Appends characters from an `initializer_list` to this string.
1428    * \note Equivalent to `append(il.begin(), il.size())`.
1429    */
1430   FOLLY_CPP14_CONSTEXPR BasicFixedString& operator+=(
1431       std::initializer_list<Char> il) noexcept(false) {
1432     return append(il.begin(), il.size());
1433   }
1434
1435   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
1436    * Erase all characters from this string.
1437    * \note Equivalent to `clear()`
1438    * \return *this;
1439    */
1440   FOLLY_CPP14_CONSTEXPR BasicFixedString& erase() noexcept {
1441     clear();
1442     return *this;
1443   }
1444
1445   /**
1446    * Erases `count` characters from position `pos`. If `count` is `npos`,
1447    *   erases from `pos` to the end of the string.
1448    * \pre `pos <= size()`
1449    * \pre `count <= size() - pos || count == npos`
1450    * \post `size() == old_size - min(count, old_size - pos)`
1451    * \post `at(size()) == Char(0)`
1452    * \return *this;
1453    * \throw std::out_of_range when pos > size().
1454    */
1455   FOLLY_CPP14_CONSTEXPR BasicFixedString& erase(
1456       std::size_t pos,
1457       std::size_t count = npos) noexcept(false) {
1458     using A = const Char[1];
1459     return replace(
1460         pos,
1461         detail::fixedstring::checkOverflowOrNpos(
1462             count, size_ - detail::fixedstring::checkOverflow(pos, size_)),
1463         A{Char(0)},
1464         0u);
1465   }
1466
1467   /**
1468    * \note Equivalent to `erase(first - data(), 1)`
1469    * \return A pointer to the first character after the erased character.
1470    */
1471   FOLLY_CPP14_CONSTEXPR Char* erase(const Char* first) noexcept(false) {
1472     erase(first - data_, 1u);
1473     return data_ + (first - data_);
1474   }
1475
1476   /**
1477    * \note Equivalent to `erase(first - data(), last - first)`
1478    * \return A pointer to the first character after the erased characters.
1479    */
1480   FOLLY_CPP14_CONSTEXPR Char* erase(
1481       const Char* first,
1482       const Char* last) noexcept(false) {
1483     erase(first - data_, last - first);
1484     return data_ + (first - data_);
1485   }
1486
1487   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
1488    * Create a new string by erasing all the characters from this string.
1489    * \note Equivalent to `BasicFixedString<Char, 0>{}`
1490    */
1491   constexpr BasicFixedString<Char, 0u> cerase() const noexcept {
1492     return {};
1493   }
1494
1495   /**
1496    * Create a new string by erasing all the characters after position `pos` from
1497    *   this string.
1498    * \note Equivalent to `creplace(pos, min(count, pos - size()), "")`
1499    */
1500   constexpr BasicFixedString cerase(std::size_t pos, std::size_t count = npos)
1501       const noexcept(false) {
1502     using A = const Char[1];
1503     return creplace(
1504         pos,
1505         detail::fixedstring::checkOverflowOrNpos(
1506             count, size_ - detail::fixedstring::checkOverflow(pos, size_)),
1507         A{Char(0)});
1508   }
1509
1510   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
1511    * Compare two strings for lexicographical ordering.
1512    * \note Equivalent to
1513    * `compare(0, size(), that.data(), that.size())`
1514    */
1515   template <std::size_t M>
1516   constexpr int compare(const BasicFixedString<Char, M>& that) const noexcept {
1517     return compare(0u, size_, that, 0u, that.size_);
1518   }
1519
1520   /**
1521    * Compare two strings for lexicographical ordering.
1522    * \note Equivalent to
1523    * `compare(this_pos, this_count, that.data(), that.size())`
1524    */
1525   template <std::size_t M>
1526   constexpr int compare(
1527       std::size_t this_pos,
1528       std::size_t this_count,
1529       const BasicFixedString<Char, M>& that) const noexcept(false) {
1530     return compare(this_pos, this_count, that, 0u, that.size_);
1531   }
1532
1533   /**
1534    * Compare two strings for lexicographical ordering.
1535    * \note Equivalent to
1536    * `compare(this_pos, this_count, that.data() + that_pos, that_count)`
1537    */
1538   template <std::size_t M>
1539   constexpr int compare(
1540       std::size_t this_pos,
1541       std::size_t this_count,
1542       const BasicFixedString<Char, M>& that,
1543       std::size_t that_pos,
1544       std::size_t that_count) const noexcept(false) {
1545     return static_cast<int>(detail::fixedstring::compare_(
1546         data_,
1547         detail::fixedstring::checkOverflow(this_pos, size_),
1548         detail::fixedstring::checkOverflow(this_count, size_ - this_pos) +
1549             this_pos,
1550         that.data_,
1551         detail::fixedstring::checkOverflow(that_pos, that.size_),
1552         detail::fixedstring::checkOverflow(that_count, that.size_ - that_pos) +
1553             that_pos));
1554   }
1555
1556   /**
1557    * Compare two strings for lexicographical ordering.
1558    * \note Equivalent to `compare(0, size(), that, strlen(that))`
1559    */
1560   constexpr int compare(const Char* that) const noexcept {
1561     return compare(0u, size_, that, folly::constexpr_strlen(that));
1562   }
1563
1564   /**
1565    * \overload
1566    */
1567   constexpr int compare(Range<const Char*> that) const noexcept {
1568     return compare(0u, size_, that.begin(), that.size());
1569   }
1570
1571   /**
1572    * Compare two strings for lexicographical ordering.
1573    * \note Equivalent to
1574    *   `compare(this_pos, this_count, that, strlen(that))`
1575    */
1576   constexpr int compare(
1577       std::size_t this_pos,
1578       std::size_t this_count,
1579       const Char* that) const noexcept(false) {
1580     return compare(this_pos, this_count, that, folly::constexpr_strlen(that));
1581   }
1582
1583   /**
1584    * \overload
1585    */
1586   constexpr int compare(
1587       std::size_t this_pos,
1588       std::size_t this_count,
1589       Range<const Char*> that) const noexcept(false) {
1590     return compare(this_pos, this_count, that.begin(), that.size());
1591   }
1592
1593   /**
1594    * Compare two strings for lexicographical ordering.
1595    *
1596    * Let `A` be the the
1597    *   character sequence {`(*this)[this_pos]`, ...
1598    *   `(*this)[this_pos + this_count - 1]`}. Let `B` be the character sequence
1599    *   {`that[0]`, ...`that[count - 1]`}. Then...
1600    *
1601    * \return
1602    *   - `< 0` if `A` is ordered before the `B`
1603    *   - `> 0` if `B` is ordered before `A`
1604    *   - `0` if `A` equals `B`.
1605    *
1606    * \throw std::out_of_range if this_pos + this_count > size().
1607    */
1608   constexpr int compare(
1609       std::size_t this_pos,
1610       std::size_t this_count,
1611       const Char* that,
1612       std::size_t that_count) const noexcept(false) {
1613     return static_cast<int>(detail::fixedstring::compare_(
1614         data_,
1615         detail::fixedstring::checkOverflow(this_pos, size_),
1616         detail::fixedstring::checkOverflowOrNpos(this_count, size_ - this_pos) +
1617             this_pos,
1618         that,
1619         0u,
1620         that_count));
1621   }
1622
1623   constexpr int compare(
1624       std::size_t this_pos,
1625       std::size_t this_count,
1626       Range<const Char*> that,
1627       std::size_t that_count) const noexcept(false) {
1628     return compare(
1629         this_pos,
1630         this_count,
1631         that.begin(),
1632         detail::fixedstring::checkOverflow(that_count, that.size()));
1633   }
1634
1635   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
1636    * Return a substring from `pos` to the end of the string.
1637    * \note Equivalent to `BasicFixedString{*this, pos}`
1638    */
1639   constexpr BasicFixedString substr(std::size_t pos) const noexcept(false) {
1640     return {*this, pos};
1641   }
1642
1643   /**
1644    * Return a substring from `pos` to the end of the string.
1645    * \note Equivalent to `BasicFixedString{*this, pos, count}`
1646    */
1647   constexpr BasicFixedString substr(std::size_t pos, std::size_t count) const
1648       noexcept(false) {
1649     return {*this, pos, count};
1650   }
1651
1652   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
1653    * Replace the characters in the range denoted by the half-open range
1654    *   [`first`, `last`) with the string `that`.
1655    * \pre `first` and `last` point to characters within this string (including
1656    *   the terminating null).
1657    * \note Equivalent to
1658    *   `replace(first - data(), last - first, that.data(), that.size())`
1659    */
1660   template <std::size_t M>
1661   FOLLY_CPP14_CONSTEXPR BasicFixedString& replace(
1662       const Char* first,
1663       const Char* last,
1664       const BasicFixedString<Char, M>& that) noexcept(false) {
1665     return replace(first - data_, last - first, that, 0u, that.size_);
1666   }
1667
1668   /**
1669    * Replace `this_count` characters starting from position `this_pos` with the
1670    *   characters from string `that` starting at position `that_pos`.
1671    * \pre `that_pos <= that.size()`
1672    * \note Equivalent to
1673    *   <tt>replace(this_pos, this_count, that.data() + that_pos,
1674    *   that.size() - that_pos)</tt>
1675    */
1676   template <std::size_t M>
1677   FOLLY_CPP14_CONSTEXPR BasicFixedString& replace(
1678       std::size_t this_pos,
1679       std::size_t this_count,
1680       const BasicFixedString<Char, M>& that,
1681       std::size_t that_pos = 0u) noexcept(false) {
1682     return replace(this_pos, this_count, that, that_pos, that.size_ - that_pos);
1683   }
1684
1685   /**
1686    * Replace `this_count` characters starting from position `this_pos` with
1687    *   `that_count` characters from string `that` starting at position
1688    *   `that_pos`.
1689    * \pre `that_pos <= that.size() && that_count <= that.size() - that_pos`
1690    * \note Equivalent to
1691    *   `replace(this_pos, this_count, that.data() + that_pos, that_count)`
1692    */
1693   template <std::size_t M>
1694   FOLLY_CPP14_CONSTEXPR BasicFixedString& replace(
1695       std::size_t this_pos,
1696       std::size_t this_count,
1697       const BasicFixedString<Char, M>& that,
1698       std::size_t that_pos,
1699       std::size_t that_count) noexcept(false) {
1700     return *this = creplace(this_pos, this_count, that, that_pos, that_count);
1701   }
1702
1703   /**
1704    * Replace `this_count` characters starting from position `this_pos` with
1705    *   the characters from the string literal `that`.
1706    * \note Equivalent to
1707    *   `replace(this_pos, this_count, that, strlen(that))`
1708    */
1709   FOLLY_CPP14_CONSTEXPR BasicFixedString& replace(
1710       std::size_t this_pos,
1711       std::size_t this_count,
1712       const Char* that) noexcept(false) {
1713     return replace(this_pos, this_count, that, folly::constexpr_strlen(that));
1714   }
1715
1716   /**
1717    * Replace the characters denoted by the half-open range [`first`,`last`) with
1718    *   the characters from the string literal `that`.
1719    * \pre `first` and `last` point to characters within this string (including
1720    *   the terminating null).
1721    * \note Equivalent to
1722    *   `replace(first - data(), last - first, that, strlen(that))`
1723    */
1724   FOLLY_CPP14_CONSTEXPR BasicFixedString& replace(
1725       const Char* first,
1726       const Char* last,
1727       const Char* that) noexcept(false) {
1728     return replace(
1729         first - data_, last - first, that, folly::constexpr_strlen(that));
1730   }
1731
1732   /**
1733    * Replace `this_count` characters starting from position `this_pos` with
1734    *   `that_count` characters from the character sequence pointed to by `that`.
1735    * \param this_pos The starting offset within `*this` of the first character
1736    *   to be replaced.
1737    * \param this_count The number of characters to be replaced. If `npos`,
1738    *   it is treated as if `this_count` were `size() - this_pos`.
1739    * \param that A pointer to the replacement string.
1740    * \param that_count The number of characters in the replacement string.
1741    * \pre `this_pos <= size() && this_count <= size() - this_pos`
1742    * \pre `that` points to a contiguous sequence of at least `that_count`
1743    *   characters
1744    * \throw std::out_of_range on any of the following conditions:
1745    *   - `this_pos > size()`
1746    *   - `this_count > size() - this_pos`
1747    *   - `size() - this_count + that_count > N`
1748    */
1749   FOLLY_CPP14_CONSTEXPR BasicFixedString& replace(
1750       std::size_t this_pos,
1751       std::size_t this_count,
1752       const Char* that,
1753       std::size_t that_count) noexcept(false) {
1754     return *this = detail::fixedstring::Helper::replace_<Char>(
1755                data_,
1756                size_,
1757                detail::fixedstring::checkOverflow(this_pos, size_),
1758                detail::fixedstring::checkOverflowOrNpos(
1759                    this_count, size_ - this_pos),
1760                that,
1761                0u,
1762                that_count,
1763                Indices{});
1764   }
1765
1766   /**
1767    * Replace `this_count` characters starting from position `this_pos` with
1768    *   `that_count` characters `ch`.
1769    * \note Equivalent to
1770    *   `replace(this_pos, this_count, BasicFixedString{that_count, ch})`
1771    */
1772   FOLLY_CPP14_CONSTEXPR BasicFixedString& replace(
1773       std::size_t this_pos,
1774       std::size_t this_count,
1775       std::size_t that_count,
1776       Char ch) noexcept(false) {
1777     return replace(this_pos, this_count, BasicFixedString{that_count, ch});
1778   }
1779
1780   /**
1781    * Replace the characters denoted by the half-open range [`first`,`last`)
1782    *   with `that_count` characters `ch`.
1783    * \note Equivalent to
1784    *   `replace(first - data(), last - first, BasicFixedString{that_count, ch})`
1785    */
1786   FOLLY_CPP14_CONSTEXPR BasicFixedString& replace(
1787       const Char* first,
1788       const Char* last,
1789       std::size_t that_count,
1790       Char ch) noexcept(false) {
1791     return replace(
1792         first - data_, last - first, BasicFixedString{that_count, ch});
1793   }
1794
1795   /**
1796    * Replace the characters denoted by the half-open range [`first`,`last`) with
1797    *   the characters from the string literal `that`.
1798    * \pre `first` and `last` point to characters within this string (including
1799    *   the terminating null).
1800    * \note Equivalent to
1801    *   `replace(this_pos, this_count, il.begin(), il.size())`
1802    */
1803   FOLLY_CPP14_CONSTEXPR BasicFixedString& replace(
1804       const Char* first,
1805       const Char* last,
1806       std::initializer_list<Char> il) noexcept(false) {
1807     return replace(first - data_, last - first, il.begin(), il.size());
1808   }
1809
1810   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
1811    * Construct a new string by replacing `this_count` characters starting from
1812    *   position `this_pos` within this string with the characters from string
1813    *   `that` starting at position `that_pos`.
1814    * \pre `that_pos <= that.size()`
1815    * \note Equivalent to
1816    *   <tt>creplace(this_pos, this_count, that, that_pos,
1817    *   that.size() - that_pos)</tt>
1818    */
1819   template <std::size_t M>
1820   constexpr BasicFixedString<Char, N + M> creplace(
1821       std::size_t this_pos,
1822       std::size_t this_count,
1823       const BasicFixedString<Char, M>& that,
1824       std::size_t that_pos = 0u) const noexcept(false) {
1825     return creplace(
1826         this_pos,
1827         this_count,
1828         that,
1829         that_pos,
1830         that.size_ - detail::fixedstring::checkOverflow(that_pos, that.size_));
1831   }
1832
1833   /**
1834    * Construct a new string by replacing `this_count` characters starting from
1835    *   position `this_pos` within this string with `that_count` characters from
1836    *   string `that` starting at position `that_pos`.
1837    * \param this_pos The starting offset within `*this` of the first character
1838    *   to be replaced.
1839    * \param this_count The number of characters to be replaced. If `npos`,
1840    *   it is treated as if `this_count` were `size() - this_pos`.
1841    * \param that A string that contains the replacement string.
1842    * \param that_pos The offset to the first character in the replacement
1843    *   string.
1844    * \param that_count The number of characters in the replacement string.
1845    * \pre `this_pos <= size() && this_count <= size() - this_pos`
1846    * \pre `that_pos <= that.size() && that_count <= that.size() - that_pos`
1847    * \post The size of the returned string is `size() - this_count + that_count`
1848    * \note Equivalent to <tt>BasicFixedString<Char, N + M>{substr(0, this_pos) +
1849    *    that.substr(that_pos, that_count) + substr(this_pos + this_count)}</tt>
1850    * \throw std::out_of_range on any of the following conditions:
1851    *   - `this_pos > size()`
1852    *   - `this_count > size() - this_pos`
1853    *   - `that_pos > that.size()`
1854    *   - `that_count > that.size() - that_pos`
1855    */
1856   template <std::size_t M>
1857   constexpr BasicFixedString<Char, N + M> creplace(
1858       std::size_t this_pos,
1859       std::size_t this_count,
1860       const BasicFixedString<Char, M>& that,
1861       std::size_t that_pos,
1862       std::size_t that_count) const noexcept(false) {
1863     return detail::fixedstring::Helper::replace_<Char>(
1864         data_,
1865         size_,
1866         detail::fixedstring::checkOverflow(this_pos, size_),
1867         detail::fixedstring::checkOverflowOrNpos(this_count, size_ - this_pos),
1868         that.data_,
1869         detail::fixedstring::checkOverflow(that_pos, that.size_),
1870         detail::fixedstring::checkOverflowOrNpos(
1871             that_count, that.size_ - that_pos),
1872         folly::make_index_sequence<N + M>{});
1873   }
1874
1875   /**
1876    * Construct a new string by replacing the characters denoted by the half-open
1877    *   range [`first`,`last`) within this string with the characters from string
1878    *   `that` starting at position `that_pos`.
1879    * \pre `that_pos <= that.size()`
1880    * \note Equivalent to
1881    *   <tt>creplace(first - data(), last - first, that, that_pos,
1882    *   that.size() - that_pos)</tt>
1883    */
1884   template <std::size_t M>
1885   constexpr BasicFixedString<Char, N + M> creplace(
1886       const Char* first,
1887       const Char* last,
1888       const BasicFixedString<Char, M>& that,
1889       std::size_t that_pos = 0u) const noexcept(false) {
1890     return creplace(
1891         first - data_,
1892         last - first,
1893         that,
1894         that_pos,
1895         that.size_ - detail::fixedstring::checkOverflow(that_pos, that.size_));
1896   }
1897
1898   /**
1899    * Construct a new string by replacing the characters denoted by the half-open
1900    *   range [`first`,`last`) within this string with the `that_count`
1901    *   characters from string `that` starting at position `that_pos`.
1902    * \note Equivalent to
1903    *   <tt>creplace(first - data(), last - first, that, that_pos,
1904    *   that_count)</tt>
1905    */
1906   template <std::size_t M>
1907   constexpr BasicFixedString<Char, N + M> creplace(
1908       const Char* first,
1909       const Char* last,
1910       const BasicFixedString<Char, M>& that,
1911       std::size_t that_pos,
1912       std::size_t that_count) const noexcept(false) {
1913     return creplace(first - data_, last - first, that, that_pos, that_count);
1914   }
1915
1916   /**
1917    * Construct a new string by replacing `this_count` characters starting from
1918    *   position `this_pos` within this string with `M-1` characters from
1919    *   character array `that`.
1920    * \pre `strlen(that) == M-1`
1921    * \note Equivalent to
1922    *   <tt>creplace(this_pos, this_count, that, 0, M - 1)</tt>
1923    */
1924   template <std::size_t M>
1925   constexpr BasicFixedString<Char, N + M - 1u> creplace(
1926       std::size_t this_pos,
1927       std::size_t this_count,
1928       const Char (&that)[M]) const noexcept(false) {
1929     return creplace(this_pos, this_count, that, 0u, M - 1u);
1930   }
1931
1932   /**
1933    * Replace `this_count` characters starting from position `this_pos` with
1934    *   `that_count` characters from the character array `that` starting at
1935    *   position `that_pos`.
1936    * \param this_pos The starting offset within `*this` of the first character
1937    *   to be replaced.
1938    * \param this_count The number of characters to be replaced. If `npos`,
1939    *   it is treated as if `this_count` were `size() - this_pos`.
1940    * \param that An array of characters containing the replacement string.
1941    * \param that_pos The starting offset of the replacement string.
1942    * \param that_count The number of characters in the replacement string.  If
1943    *   `npos`, it is treated as if `that_count` were `M - 1 - that_pos`
1944    * \pre `this_pos <= size() && this_count <= size() - this_pos`
1945    * \pre `that_pos <= M - 1 && that_count <= M - 1 - that_pos`
1946    * \post The size of the returned string is `size() - this_count + that_count`
1947    * \note Equivalent to <tt>BasicFixedString<Char, N + M - 1>{
1948    *    substr(0, this_pos) +
1949    *    makeFixedString(that).substr(that_pos, that_count) +
1950    *    substr(this_pos + this_count)}</tt>
1951    * \throw std::out_of_range on any of the following conditions:
1952    *   - `this_pos > size()`
1953    *   - `this_count > size() - this_pos`
1954    *   - `that_pos >= M`
1955    *   - `that_count >= M - that_pos`
1956    */
1957   template <std::size_t M>
1958   constexpr BasicFixedString<Char, N + M - 1u> creplace(
1959       std::size_t this_pos,
1960       std::size_t this_count,
1961       const Char (&that)[M],
1962       std::size_t that_pos,
1963       std::size_t that_count) const noexcept(false) {
1964     return detail::fixedstring::Helper::replace_<Char>(
1965         data_,
1966         size_,
1967         detail::fixedstring::checkOverflow(this_pos, size_),
1968         detail::fixedstring::checkOverflowOrNpos(this_count, size_ - this_pos),
1969         detail::fixedstring::checkNullTerminated(that),
1970         detail::fixedstring::checkOverflow(that_pos, M - 1u),
1971         detail::fixedstring::checkOverflowOrNpos(that_count, M - 1u - that_pos),
1972         folly::make_index_sequence<N + M - 1u>{});
1973   }
1974
1975   /**
1976    * Construct a new string by replacing the characters denoted by the half-open
1977    *   range [`first`,`last`) within this string with the first `M-1`
1978    *   characters from the character array `that`.
1979    * \pre `strlen(that) == M-1`
1980    * \note Equivalent to
1981    *   <tt>creplace(first - data(), last - first, that, 0, M-1)</tt>
1982    */
1983   template <std::size_t M>
1984   constexpr BasicFixedString<Char, N + M - 1u>
1985   creplace(const Char* first, const Char* last, const Char (&that)[M]) const
1986       noexcept(false) {
1987     return creplace(first - data_, last - first, that, 0u, M - 1u);
1988   }
1989
1990   /**
1991    * Construct a new string by replacing the characters denoted by the half-open
1992    *   range [`first`,`last`) within this string with the `that_count`
1993    *   characters from the character array `that` starting at position
1994    *   `that_pos`.
1995    * \pre `strlen(that) == M-1`
1996    * \note Equivalent to
1997    *   `creplace(first - data(), last - first, that, that_pos, that_count)`
1998    */
1999   template <std::size_t M>
2000   constexpr BasicFixedString<Char, N + M - 1u> creplace(
2001       const Char* first,
2002       const Char* last,
2003       const Char (&that)[M],
2004       std::size_t that_pos,
2005       std::size_t that_count) const noexcept(false) {
2006     return creplace(first - data_, last - first, that, that_pos, that_count);
2007   }
2008
2009   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
2010   * Copies `min(count, size())` characters starting from offset `0`
2011   *   from this string into the buffer pointed to by `dest`.
2012   * \return The number of characters copied.
2013    */
2014   FOLLY_CPP14_CONSTEXPR std::size_t copy(Char* dest, std::size_t count) const
2015       noexcept {
2016     return copy(dest, count, 0u);
2017   }
2018
2019   /**
2020    * Copies `min(count, size() - pos)` characters starting from offset `pos`
2021    *   from this string into the buffer pointed to by `dest`.
2022    * \pre `pos <= size()`
2023    * \return The number of characters copied.
2024    * \throw std::out_of_range if `pos > size()`
2025    */
2026   FOLLY_CPP14_CONSTEXPR std::size_t
2027   copy(Char* dest, std::size_t count, std::size_t pos) const noexcept(false) {
2028     detail::fixedstring::checkOverflow(pos, size_);
2029     for (std::size_t i = 0u; i < count; ++i) {
2030       if (i + pos == size_)
2031         return size_;
2032       dest[i] = data_[i + pos];
2033     }
2034     return count;
2035   }
2036
2037   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
2038    * Resizes the current string.
2039    * \note Equivalent to `resize(count, Char(0))`
2040    */
2041   FOLLY_CPP14_CONSTEXPR void resize(std::size_t count) noexcept(false) {
2042     resize(count, Char(0));
2043   }
2044
2045   /**
2046    * Resizes the current string by setting the size to `count` and setting
2047    *   `data()[count]` to `Char(0)`. If `count > old_size`, the characters
2048    *   in the range [`old_size`,`count`) are set to `ch`.
2049    */
2050   FOLLY_CPP14_CONSTEXPR void resize(std::size_t count, Char ch) noexcept(
2051       false) {
2052     detail::fixedstring::checkOverflow(count, N);
2053     if (count == size_) {
2054     } else if (count < size_) {
2055       size_ = count;
2056       data_[size_] = Char(0);
2057     } else {
2058       for (; size_ < count; ++size_) {
2059         data_[size_] = ch;
2060       }
2061       data_[size_] = Char(0);
2062     }
2063   }
2064
2065   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
2066    * Finds the first occurrence of the character sequence `that` in this string.
2067    * \note Equivalent to `find(that.data(), 0, that.size())`
2068    */
2069   template <std::size_t M>
2070   constexpr std::size_t find(const BasicFixedString<Char, M>& that) const
2071       noexcept {
2072     return find(that, 0u);
2073   }
2074
2075   /**
2076    * Finds the first occurrence of the character sequence `that` in this string,
2077    *   starting at offset `pos`.
2078    * \pre `pos <= size()`
2079    * \note Equivalent to `find(that.data(), pos, that.size())`
2080    */
2081   template <std::size_t M>
2082   constexpr std::size_t find(
2083       const BasicFixedString<Char, M>& that,
2084       std::size_t pos) const noexcept(false) {
2085     return that.size_ <= size_ - detail::fixedstring::checkOverflow(pos, size_)
2086         ? detail::fixedstring::find_(data_, size_, that.data_, pos, that.size_)
2087         : npos;
2088   }
2089
2090   /**
2091    * Finds the first occurrence of the character sequence `that` in this string.
2092    * \note Equivalent to `find(that.data(), 0, strlen(that))`
2093    */
2094   constexpr std::size_t find(const Char* that) const noexcept {
2095     return find(that, 0u, folly::constexpr_strlen(that));
2096   }
2097
2098   /**
2099    * Finds the first occurrence of the character sequence `that` in this string,
2100    *   starting at offset `pos`.
2101    * \pre `pos <= size()`
2102    * \note Equivalent to `find(that.data(), pos, strlen(that))`
2103    */
2104   constexpr std::size_t find(const Char* that, std::size_t pos) const
2105       noexcept(false) {
2106     return find(that, pos, folly::constexpr_strlen(that));
2107   }
2108
2109   /**
2110    * Finds the first occurrence of the first `count` characters in the buffer
2111    *   pointed to by `that` in this string, starting at offset `pos`.
2112    * \pre `pos <= size()`
2113    * \pre `that` points to a buffer containing at least `count` contiguous
2114    *   characters.
2115    * \return The lowest offset `i` such that `i >= pos` and
2116    *   `0 == strncmp(data() + i, that, count)`; or `npos` if there is no such
2117    *   offset `i`.
2118    * \throw std::out_of_range when `pos > size()`
2119    */
2120   constexpr std::size_t find(
2121       const Char* that,
2122       std::size_t pos,
2123       std::size_t count) const noexcept(false) {
2124     return count <= size_ - detail::fixedstring::checkOverflow(pos, size_)
2125         ? detail::fixedstring::find_(data_, size_, that, pos, count)
2126         : npos;
2127   }
2128
2129   /**
2130    * Finds the first occurrence of the character `ch` in this string.
2131    * \note Equivalent to `find(&ch, 0, 1)`
2132    */
2133   constexpr std::size_t find(Char ch) const noexcept {
2134     return find(ch, 0u);
2135   }
2136
2137   /**
2138    * Finds the first occurrence of the character character `c` in this string,
2139    *   starting at offset `pos`.
2140    * \pre `pos <= size()`
2141    * \note Equivalent to `find(&ch, pos, 1)`
2142    */
2143   constexpr std::size_t find(Char ch, std::size_t pos) const noexcept(false) {
2144     using A = const Char[1u];
2145     return 0u == size_ - detail::fixedstring::checkOverflow(pos, size_)
2146         ? npos
2147         : detail::fixedstring::find_(data_, size_, A{ch}, pos, 1u);
2148   }
2149
2150   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
2151    * Finds the last occurrence of characters in the string
2152    *   `that` in this string.
2153    * \note Equivalent to `rfind(that.data(), size(), that.size())`
2154    */
2155   template <std::size_t M>
2156   constexpr std::size_t rfind(const BasicFixedString<Char, M>& that) const
2157       noexcept {
2158     return rfind(that, size_);
2159   }
2160
2161   /**
2162    * Finds the last occurrence of characters in the string
2163    *   `that` in this string, starting at offset `pos`.
2164    * \note Equivalent to `rfind(that.data(), pos, that.size())`
2165    */
2166   template <std::size_t M>
2167   constexpr std::size_t rfind(
2168       const BasicFixedString<Char, M>& that,
2169       std::size_t pos) const noexcept(false) {
2170     return that.size_ <= size_
2171         ? detail::fixedstring::rfind_(
2172               data_,
2173               that.data_,
2174               folly::constexpr_min(
2175                   detail::fixedstring::checkOverflow(pos, size_),
2176                   size_ - that.size_),
2177               that.size_)
2178         : npos;
2179   }
2180
2181   /**
2182    * Finds the last occurrence of characters in the buffer
2183    *   pointed to by `that` in this string.
2184    * \note Equivalent to `rfind(that, size(), strlen(that))`
2185    */
2186   constexpr std::size_t rfind(const Char* that) const noexcept {
2187     return rfind(that, size_, folly::constexpr_strlen(that));
2188   }
2189
2190   /**
2191    * Finds the last occurrence of characters in the buffer
2192    *   pointed to by `that` in this string, starting at offset `pos`.
2193    * \note Equivalent to `rfind(that, pos, strlen(that))`
2194    */
2195   constexpr std::size_t rfind(const Char* that, std::size_t pos) const
2196       noexcept(false) {
2197     return rfind(that, pos, folly::constexpr_strlen(that));
2198   }
2199
2200   /**
2201    * Finds the last occurrence of the first `count` characters in the buffer
2202    *   pointed to by `that` in this string, starting at offset `pos`.
2203    * \pre `pos <= size()`
2204    * \pre `that` points to a buffer containing at least `count` contiguous
2205    *   characters.
2206    * \return The largest offset `i` such that `i <= pos` and
2207    *   `i + count <= size()` and `0 == strncmp(data() + i, that, count)`; or
2208    *   `npos` if there is no such offset `i`.
2209    * \throw std::out_of_range when `pos > size()`
2210    */
2211   constexpr std::size_t rfind(
2212       const Char* that,
2213       std::size_t pos,
2214       std::size_t count) const noexcept(false) {
2215     return count <= size_
2216         ? detail::fixedstring::rfind_(
2217               data_,
2218               that,
2219               folly::constexpr_min(
2220                   detail::fixedstring::checkOverflow(pos, size_),
2221                   size_ - count),
2222               count)
2223         : npos;
2224   }
2225
2226   /**
2227    * Finds the last occurrence of the character character `ch` in this string.
2228    * \note Equivalent to `rfind(&ch, size(), 1)`
2229    */
2230   constexpr std::size_t rfind(Char ch) const noexcept {
2231     return rfind(ch, size_);
2232   }
2233
2234   /**
2235    * Finds the last occurrence of the character character `ch` in this string,
2236    *   starting at offset `pos`.
2237    * \pre `pos <= size()`
2238    * \note Equivalent to `rfind(&ch, pos, 1)`
2239    */
2240   constexpr std::size_t rfind(Char ch, std::size_t pos) const noexcept(false) {
2241     using A = const Char[1u];
2242     return 0u == size_
2243         ? npos
2244         : detail::fixedstring::rfind_(
2245               data_,
2246               A{ch},
2247               folly::constexpr_min(
2248                   detail::fixedstring::checkOverflow(pos, size_), size_ - 1u),
2249               1u);
2250   }
2251
2252   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
2253    * Finds the first occurrence of any character in `that` in this string.
2254    * \note Equivalent to `find_first_of(that.data(), 0, that.size())`
2255    */
2256   template <std::size_t M>
2257   constexpr std::size_t find_first_of(
2258       const BasicFixedString<Char, M>& that) const noexcept {
2259     return find_first_of(that, 0u);
2260   }
2261
2262   /**
2263    * Finds the first occurrence of any character in `that` in this string,
2264    *   starting at offset `pos`
2265    * \note Equivalent to `find_first_of(that.data(), pos, that.size())`
2266    */
2267   template <std::size_t M>
2268   constexpr std::size_t find_first_of(
2269       const BasicFixedString<Char, M>& that,
2270       std::size_t pos) const noexcept(false) {
2271     return size_ == detail::fixedstring::checkOverflow(pos, size_)
2272         ? npos
2273         : detail::fixedstring::find_first_of_(
2274               data_, size_, that.data_, pos, that.size_);
2275   }
2276
2277   /**
2278    * Finds the first occurrence of any character in the null-terminated
2279    *   character sequence pointed to by `that` in this string.
2280    * \note Equivalent to `find_first_of(that, 0, strlen(that))`
2281    */
2282   constexpr std::size_t find_first_of(const Char* that) const noexcept {
2283     return find_first_of(that, 0u, folly::constexpr_strlen(that));
2284   }
2285
2286   /**
2287    * Finds the first occurrence of any character in the null-terminated
2288    *   character sequence pointed to by `that` in this string,
2289    *   starting at offset `pos`
2290    * \note Equivalent to `find_first_of(that, pos, strlen(that))`
2291    */
2292   constexpr std::size_t find_first_of(const Char* that, std::size_t pos) const
2293       noexcept(false) {
2294     return find_first_of(that, pos, folly::constexpr_strlen(that));
2295   }
2296
2297   /**
2298    * Finds the first occurrence of any character in the first `count` characters
2299    *   in the buffer pointed to by `that` in this string, starting at offset
2300    *  `pos`.
2301    * \pre `pos <= size()`
2302    * \pre `that` points to a buffer containing at least `count` contiguous
2303    *   characters.
2304    * \return The smallest offset `i` such that `i >= pos` and
2305    *   `std::find(that, that+count, at(i)) != that+count`; or
2306    *   `npos` if there is no such offset `i`.
2307    * \throw std::out_of_range when `pos > size()`
2308    */
2309   constexpr std::size_t find_first_of(
2310       const Char* that,
2311       std::size_t pos,
2312       std::size_t count) const noexcept(false) {
2313     return size_ == detail::fixedstring::checkOverflow(pos, size_)
2314         ? npos
2315         : detail::fixedstring::find_first_of_(data_, size_, that, pos, count);
2316   }
2317
2318   /**
2319    * Finds the first occurrence of `ch` in this string.
2320    * \note Equivalent to `find_first_of(&ch, 0, 1)`
2321    */
2322   constexpr std::size_t find_first_of(Char ch) const noexcept {
2323     return find_first_of(ch, 0u);
2324   }
2325
2326   /**
2327    * Finds the first occurrence of `ch` in this string,
2328    *   starting at offset `pos`.
2329    * \note Equivalent to `find_first_of(&ch, pos, 1)`
2330    */
2331   constexpr std::size_t find_first_of(Char ch, std::size_t pos) const
2332       noexcept(false) {
2333     using A = const Char[1u];
2334     return size_ == detail::fixedstring::checkOverflow(pos, size_)
2335         ? npos
2336         : detail::fixedstring::find_first_of_(data_, size_, A{ch}, pos, 1u);
2337   }
2338
2339   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
2340    * Finds the first occurrence of any character not in `that` in this string.
2341    * \note Equivalent to `find_first_not_of(that.data(), 0, that.size())`
2342    */
2343   template <std::size_t M>
2344   constexpr std::size_t find_first_not_of(
2345       const BasicFixedString<Char, M>& that) const noexcept {
2346     return find_first_not_of(that, 0u);
2347   }
2348
2349   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
2350    * Finds the first occurrence of any character not in `that` in this string.
2351    * \note Equivalent to `find_first_not_of(that.data(), 0, that.size())`
2352    */
2353   template <std::size_t M>
2354   constexpr std::size_t find_first_not_of(
2355       const BasicFixedString<Char, M>& that,
2356       std::size_t pos) const noexcept(false) {
2357     return size_ == detail::fixedstring::checkOverflow(pos, size_)
2358         ? npos
2359         : detail::fixedstring::find_first_not_of_(
2360               data_, size_, that.data_, pos, that.size_);
2361   }
2362
2363   /**
2364    * Finds the first occurrence of any character not in the null-terminated
2365    *   character sequence pointed to by `that` in this string.
2366    * \note Equivalent to `find_first_not_of(that, 0, strlen(that))`
2367    */
2368   constexpr std::size_t find_first_not_of(const Char* that) const noexcept {
2369     return find_first_not_of(that, 0u, folly::constexpr_strlen(that));
2370   }
2371
2372   /**
2373    * Finds the first occurrence of any character not in the null-terminated
2374    *   character sequence pointed to by `that` in this string,
2375    *   starting at offset `pos`
2376    * \note Equivalent to `find_first_not_of(that, pos, strlen(that))`
2377    */
2378   constexpr std::size_t find_first_not_of(const Char* that, std::size_t pos)
2379       const noexcept(false) {
2380     return find_first_not_of(that, pos, folly::constexpr_strlen(that));
2381   }
2382
2383   /**
2384    * Finds the first occurrence of any character not in the first `count`
2385    *   characters in the buffer pointed to by `that` in this string, starting at
2386    *   offset `pos`.
2387    * \pre `pos <= size()`
2388    * \pre `that` points to a buffer containing at least `count` contiguous
2389    *   characters.
2390    * \return The smallest offset `i` such that `i >= pos` and
2391    *   `std::find(that, that+count, at(i)) == that+count`; or
2392    *   `npos` if there is no such offset `i`.
2393    * \throw std::out_of_range when `pos > size()`
2394    */
2395   constexpr std::size_t find_first_not_of(
2396       const Char* that,
2397       std::size_t pos,
2398       std::size_t count) const noexcept(false) {
2399     return size_ == detail::fixedstring::checkOverflow(pos, size_)
2400         ? npos
2401         : detail::fixedstring::find_first_not_of_(
2402               data_, size_, that, pos, count);
2403   }
2404
2405   /**
2406    * Finds the first occurrence of any character other than `ch` in this string.
2407    * \note Equivalent to `find_first_not_of(&ch, 0, 1)`
2408    */
2409   constexpr std::size_t find_first_not_of(Char ch) const noexcept {
2410     return find_first_not_of(ch, 0u);
2411   }
2412
2413   /**
2414    * Finds the first occurrence of any character other than `ch` in this string,
2415    *   starting at offset `pos`.
2416    * \note Equivalent to `find_first_not_of(&ch, pos, 1)`
2417    */
2418   constexpr std::size_t find_first_not_of(Char ch, std::size_t pos) const
2419       noexcept(false) {
2420     using A = const Char[1u];
2421     return 1u <= size_ - detail::fixedstring::checkOverflow(pos, size_)
2422         ? detail::fixedstring::find_first_not_of_(data_, size_, A{ch}, pos, 1u)
2423         : npos;
2424   }
2425
2426   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
2427    * Finds the last occurrence of any character in `that` in this string.
2428    * \note Equivalent to `find_last_of(that.data(), size(), that.size())`
2429    */
2430   template <std::size_t M>
2431   constexpr std::size_t find_last_of(
2432       const BasicFixedString<Char, M>& that) const noexcept {
2433     return find_last_of(that, size_);
2434   }
2435
2436   /**
2437    * Finds the last occurrence of any character in `that` in this string,
2438    *   starting at offset `pos`
2439    * \note Equivalent to `find_last_of(that.data(), pos, that.size())`
2440    */
2441   template <std::size_t M>
2442   constexpr std::size_t find_last_of(
2443       const BasicFixedString<Char, M>& that,
2444       std::size_t pos) const noexcept(false) {
2445     return 0u == size_
2446         ? npos
2447         : detail::fixedstring::find_last_of_(
2448               data_,
2449               that.data_,
2450               folly::constexpr_min(
2451                   detail::fixedstring::checkOverflow(pos, size_), size_ - 1u),
2452               that.size_);
2453   }
2454
2455   /**
2456    * Finds the last occurrence of any character in the null-terminated
2457    *   character sequence pointed to by `that` in this string.
2458    * \note Equivalent to `find_last_of(that, size(), strlen(that))`
2459    */
2460   constexpr std::size_t find_last_of(const Char* that) const noexcept {
2461     return find_last_of(that, size_, folly::constexpr_strlen(that));
2462   }
2463
2464   /**
2465    * Finds the last occurrence of any character in the null-terminated
2466    *   character sequence pointed to by `that` in this string,
2467    *   starting at offset `pos`
2468    * \note Equivalent to `find_last_of(that, pos, strlen(that))`
2469    */
2470   constexpr std::size_t find_last_of(const Char* that, std::size_t pos) const
2471       noexcept(false) {
2472     return find_last_of(that, pos, folly::constexpr_strlen(that));
2473   }
2474
2475   /**
2476    * Finds the last occurrence of any character in the first `count` characters
2477    *   in the buffer pointed to by `that` in this string, starting at offset
2478    *  `pos`.
2479    * \pre `pos <= size()`
2480    * \pre `that` points to a buffer containing at least `count` contiguous
2481    *   characters.
2482    * \return The largest offset `i` such that `i <= pos` and
2483    *   `i < size()` and `std::find(that, that+count, at(i)) != that+count`; or
2484    *   `npos` if there is no such offset `i`.
2485    * \throw std::out_of_range when `pos > size()`
2486    */
2487   constexpr std::size_t find_last_of(
2488       const Char* that,
2489       std::size_t pos,
2490       std::size_t count) const noexcept(false) {
2491     return 0u == size_
2492         ? npos
2493         : detail::fixedstring::find_last_of_(
2494               data_,
2495               that,
2496               folly::constexpr_min(
2497                   detail::fixedstring::checkOverflow(pos, size_), size_ - 1u),
2498               count);
2499   }
2500
2501   /**
2502    * Finds the last occurrence of `ch` in this string.
2503    * \note Equivalent to `find_last_of(&ch, size(), 1)`
2504    */
2505   constexpr std::size_t find_last_of(Char ch) const noexcept {
2506     return find_last_of(ch, size_);
2507   }
2508
2509   /**
2510    * Finds the last occurrence of `ch` in this string,
2511    *   starting at offset `pos`.
2512    * \note Equivalent to `find_last_of(&ch, pos, 1)`
2513    */
2514   constexpr std::size_t find_last_of(Char ch, std::size_t pos) const
2515       noexcept(false) {
2516     using A = const Char[1u];
2517     return 0u == size_
2518         ? npos
2519         : detail::fixedstring::find_last_of_(
2520               data_,
2521               A{ch},
2522               folly::constexpr_min(
2523                   detail::fixedstring::checkOverflow(pos, size_), size_ - 1u),
2524               1u);
2525   }
2526
2527   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
2528    * Finds the last occurrence of any character not in `that` in this string.
2529    * \note Equivalent to `find_last_not_of(that.data(), size(), that.size())`
2530    */
2531   template <std::size_t M>
2532   constexpr std::size_t find_last_not_of(
2533       const BasicFixedString<Char, M>& that) const noexcept {
2534     return find_last_not_of(that, size_);
2535   }
2536
2537   /**
2538    * Finds the last occurrence of any character not in `that` in this string,
2539    *   starting at offset `pos`
2540    * \note Equivalent to `find_last_not_of(that.data(), pos, that.size())`
2541    */
2542   template <std::size_t M>
2543   constexpr std::size_t find_last_not_of(
2544       const BasicFixedString<Char, M>& that,
2545       std::size_t pos) const noexcept(false) {
2546     return 0u == size_
2547         ? npos
2548         : detail::fixedstring::find_last_not_of_(
2549               data_,
2550               that.data_,
2551               folly::constexpr_min(
2552                   detail::fixedstring::checkOverflow(pos, size_), size_ - 1u),
2553               that.size_);
2554   }
2555
2556   /**
2557    * Finds the last occurrence of any character not in the null-terminated
2558    *   character sequence pointed to by `that` in this string.
2559    * \note Equivalent to `find_last_not_of(that, size(), strlen(that))`
2560    */
2561   constexpr std::size_t find_last_not_of(const Char* that) const noexcept {
2562     return find_last_not_of(that, size_, folly::constexpr_strlen(that));
2563   }
2564
2565   /**
2566    * Finds the last occurrence of any character not in the null-terminated
2567    *   character sequence pointed to by `that` in this string,
2568    *   starting at offset `pos`
2569    * \note Equivalent to `find_last_not_of(that, pos, strlen(that))`
2570    */
2571   constexpr std::size_t find_last_not_of(const Char* that, std::size_t pos)
2572       const noexcept(false) {
2573     return find_last_not_of(that, pos, folly::constexpr_strlen(that));
2574   }
2575
2576   /**
2577    * Finds the last occurrence of any character not in the first `count`
2578    *   characters in the buffer pointed to by `that` in this string, starting at
2579    *   offset `pos`.
2580    * \pre `pos <= size()`
2581    * \pre `that` points to a buffer containing at least `count` contiguous
2582    *   characters.
2583    * \return The largest offset `i` such that `i <= pos` and
2584    *   `i < size()` and `std::find(that, that+count, at(i)) == that+count`; or
2585    *   `npos` if there is no such offset `i`.
2586    * \throw std::out_of_range when `pos > size()`
2587    */
2588   constexpr std::size_t find_last_not_of(
2589       const Char* that,
2590       std::size_t pos,
2591       std::size_t count) const noexcept(false) {
2592     return 0u == size_
2593         ? npos
2594         : detail::fixedstring::find_last_not_of_(
2595               data_,
2596               that,
2597               folly::constexpr_min(
2598                   detail::fixedstring::checkOverflow(pos, size_), size_ - 1u),
2599               count);
2600   }
2601
2602   /**
2603    * Finds the last occurrence of any character other than `ch` in this string.
2604    * \note Equivalent to `find_last_not_of(&ch, size(), 1)`
2605    */
2606   constexpr std::size_t find_last_not_of(Char ch) const noexcept {
2607     return find_last_not_of(ch, size_);
2608   }
2609
2610   /**
2611    * Finds the last occurrence of any character other than `ch` in this string,
2612    *   starting at offset `pos`.
2613    * \note Equivalent to `find_last_not_of(&ch, pos, 1)`
2614    */
2615   constexpr std::size_t find_last_not_of(Char ch, std::size_t pos) const
2616       noexcept(false) {
2617     using A = const Char[1u];
2618     return 0u == size_
2619         ? npos
2620         : detail::fixedstring::find_last_not_of_(
2621               data_,
2622               A{ch},
2623               folly::constexpr_min(
2624                   detail::fixedstring::checkOverflow(pos, size_), size_ - 1u),
2625               1u);
2626   }
2627
2628   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
2629    * Asymmetric relational operators
2630    */
2631   friend constexpr bool operator==(
2632       const Char* a,
2633       const BasicFixedString& b) noexcept {
2634     return detail::fixedstring::equal_(
2635         a, folly::constexpr_strlen(a), b.data_, b.size_);
2636   }
2637
2638   /**
2639    * \overload
2640    */
2641   friend constexpr bool operator==(
2642       const BasicFixedString& a,
2643       const Char* b) noexcept {
2644     return b == a;
2645   }
2646
2647   /**
2648    * \overload
2649    */
2650   friend constexpr bool operator==(
2651       Range<const Char*> a,
2652       const BasicFixedString& b) noexcept {
2653     return detail::fixedstring::equal_(a.begin(), a.size(), b.data_, b.size_);
2654   }
2655
2656   /**
2657    * \overload
2658    */
2659   friend constexpr bool operator==(
2660       const BasicFixedString& a,
2661       Range<const Char*> b) noexcept {
2662     return b == a;
2663   }
2664
2665   friend constexpr bool operator!=(
2666       const Char* a,
2667       const BasicFixedString& b) noexcept {
2668     return !(a == b);
2669   }
2670
2671   /**
2672    * \overload
2673    */
2674   friend constexpr bool operator!=(
2675       const BasicFixedString& a,
2676       const Char* b) noexcept {
2677     return !(b == a);
2678   }
2679
2680   /**
2681    * \overload
2682    */
2683   friend constexpr bool operator!=(
2684       Range<const Char*> a,
2685       const BasicFixedString& b) noexcept {
2686     return !(a == b);
2687   }
2688
2689   /**
2690    * \overload
2691    */
2692   friend constexpr bool operator!=(
2693       const BasicFixedString& a,
2694       Range<const Char*> b) noexcept {
2695     return !(a == b);
2696   }
2697
2698   friend constexpr bool operator<(
2699       const Char* a,
2700       const BasicFixedString& b) noexcept {
2701     return detail::fixedstring::Cmp::LT ==
2702         detail::fixedstring::compare_(
2703                a, 0u, folly::constexpr_strlen(a), b.data_, 0u, b.size_);
2704   }
2705
2706   /**
2707    * \overload
2708    */
2709   friend constexpr bool operator<(
2710       const BasicFixedString& a,
2711       const Char* b) noexcept {
2712     return detail::fixedstring::Cmp::LT ==
2713         detail::fixedstring::compare_(
2714                a.data_, 0u, a.size_, b, 0u, folly::constexpr_strlen(b));
2715   }
2716
2717   /**
2718    * \overload
2719    */
2720   friend constexpr bool operator<(
2721       Range<const Char*> a,
2722       const BasicFixedString& b) noexcept {
2723     return detail::fixedstring::Cmp::LT ==
2724         detail::fixedstring::compare_(
2725                a.begin(), 0u, a.size(), b.data_, 0u, b.size_);
2726   }
2727
2728   /**
2729    * \overload
2730    */
2731   friend constexpr bool operator<(
2732       const BasicFixedString& a,
2733       Range<const Char*> b) noexcept {
2734     return detail::fixedstring::Cmp::LT ==
2735         detail::fixedstring::compare_(
2736                a.data_, 0u, a.size_, b.begin(), 0u, b.size());
2737   }
2738
2739   friend constexpr bool operator>(
2740       const Char* a,
2741       const BasicFixedString& b) noexcept {
2742     return b < a;
2743   }
2744
2745   /**
2746    * \overload
2747    */
2748   friend constexpr bool operator>(
2749       const BasicFixedString& a,
2750       const Char* b) noexcept {
2751     return b < a;
2752   }
2753
2754   /**
2755    * \overload
2756    */
2757   friend constexpr bool operator>(
2758       Range<const Char*> a,
2759       const BasicFixedString& b) noexcept {
2760     return b < a;
2761   }
2762
2763   /**
2764    * \overload
2765    */
2766   friend constexpr bool operator>(
2767       const BasicFixedString& a,
2768       Range<const Char*> b) noexcept {
2769     return b < a;
2770   }
2771
2772   friend constexpr bool operator<=(
2773       const Char* a,
2774       const BasicFixedString& b) noexcept {
2775     return !(b < a);
2776   }
2777
2778   /**
2779    * \overload
2780    */
2781   friend constexpr bool operator<=(
2782       const BasicFixedString& a,
2783       const Char* b) noexcept {
2784     return !(b < a);
2785   }
2786
2787   /**
2788    * \overload
2789    */
2790   friend constexpr bool operator<=(
2791       Range<const Char*> const& a,
2792       const BasicFixedString& b) noexcept {
2793     return !(b < a);
2794   }
2795
2796   /**
2797    * \overload
2798    */
2799   friend constexpr bool operator<=(
2800       const BasicFixedString& a,
2801       Range<const Char*> b) noexcept {
2802     return !(b < a);
2803   }
2804
2805   friend constexpr bool operator>=(
2806       const Char* a,
2807       const BasicFixedString& b) noexcept {
2808     return !(a < b);
2809   }
2810
2811   /**
2812    * \overload
2813    */
2814   friend constexpr bool operator>=(
2815       const BasicFixedString& a,
2816       const Char* b) noexcept {
2817     return !(a < b);
2818   }
2819
2820   /**
2821    * \overload
2822    */
2823   friend constexpr bool operator>=(
2824       Range<const Char*> a,
2825       const BasicFixedString& b) noexcept {
2826     return !(a < b);
2827   }
2828
2829   /**
2830    * \overload
2831    */
2832   friend constexpr bool operator>=(
2833       const BasicFixedString& a,
2834       Range<const Char*> const& b) noexcept {
2835     return !(a < b);
2836   }
2837
2838   /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
2839    * Asymmetric concatenation
2840    */
2841   template <std::size_t M>
2842   friend constexpr BasicFixedString<Char, N + M - 1u> operator+(
2843       const Char (&a)[M],
2844       const BasicFixedString& b) noexcept {
2845     return detail::fixedstring::Helper::concat_<Char>(
2846         detail::fixedstring::checkNullTerminated(a),
2847         M - 1u,
2848         b.data_,
2849         b.size_,
2850         folly::make_index_sequence<N + M - 1u>{});
2851   }
2852
2853   /**
2854    * \overload
2855    */
2856   template <std::size_t M>
2857   friend constexpr BasicFixedString<Char, N + M - 1u> operator+(
2858       const BasicFixedString& a,
2859       const Char (&b)[M]) noexcept {
2860     return detail::fixedstring::Helper::concat_<Char>(
2861         a.data_,
2862         a.size_,
2863         detail::fixedstring::checkNullTerminated(b),
2864         M - 1u,
2865         folly::make_index_sequence<N + M - 1u>{});
2866   }
2867
2868   /**
2869    * \overload
2870    */
2871   friend constexpr BasicFixedString<Char, N + 1u> operator+(
2872       Char a,
2873       const BasicFixedString& b) noexcept {
2874     using A = const Char[2u];
2875     return detail::fixedstring::Helper::concat_<Char>(
2876         A{a, Char(0)},
2877         1u,
2878         b.data_,
2879         b.size_,
2880         folly::make_index_sequence<N + 1u>{});
2881   }
2882
2883   /**
2884    * \overload
2885    */
2886   friend constexpr BasicFixedString<Char, N + 1u> operator+(
2887       const BasicFixedString& a,
2888       Char b) noexcept {
2889     using A = const Char[2u];
2890     return detail::fixedstring::Helper::concat_<Char>(
2891         a.data_,
2892         a.size_,
2893         A{b, Char(0)},
2894         1u,
2895         folly::make_index_sequence<N + 1u>{});
2896   }
2897 };
2898
2899 template <class C, std::size_t N>
2900 inline std::basic_ostream<C>& operator<<(
2901     std::basic_ostream<C>& os,
2902     const BasicFixedString<C, N>& string) {
2903   using StreamSize = decltype(os.width());
2904   os.write(string.begin(), static_cast<StreamSize>(string.size()));
2905   return os;
2906 }
2907
2908 /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
2909  * Symmetric relational operators
2910  */
2911 template <class Char, std::size_t A, std::size_t B>
2912 constexpr bool operator==(
2913     const BasicFixedString<Char, A>& a,
2914     const BasicFixedString<Char, B>& b) noexcept {
2915   return detail::fixedstring::equal_(
2916       detail::fixedstring::Helper::data_(a),
2917       a.size(),
2918       detail::fixedstring::Helper::data_(b),
2919       b.size());
2920 }
2921
2922 template <class Char, std::size_t A, std::size_t B>
2923 constexpr bool operator!=(
2924     const BasicFixedString<Char, A>& a,
2925     const BasicFixedString<Char, B>& b) {
2926   return !(a == b);
2927 }
2928
2929 template <class Char, std::size_t A, std::size_t B>
2930 constexpr bool operator<(
2931     const BasicFixedString<Char, A>& a,
2932     const BasicFixedString<Char, B>& b) noexcept {
2933   return detail::fixedstring::Cmp::LT ==
2934       detail::fixedstring::compare_(
2935              detail::fixedstring::Helper::data_(a),
2936              0u,
2937              a.size(),
2938              detail::fixedstring::Helper::data_(b),
2939              0u,
2940              b.size());
2941 }
2942
2943 template <class Char, std::size_t A, std::size_t B>
2944 constexpr bool operator>(
2945     const BasicFixedString<Char, A>& a,
2946     const BasicFixedString<Char, B>& b) noexcept {
2947   return b < a;
2948 }
2949
2950 template <class Char, std::size_t A, std::size_t B>
2951 constexpr bool operator<=(
2952     const BasicFixedString<Char, A>& a,
2953     const BasicFixedString<Char, B>& b) noexcept {
2954   return !(b < a);
2955 }
2956
2957 template <class Char, std::size_t A, std::size_t B>
2958 constexpr bool operator>=(
2959     const BasicFixedString<Char, A>& a,
2960     const BasicFixedString<Char, B>& b) noexcept {
2961   return !(a < b);
2962 }
2963
2964 /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
2965  * Symmetric concatenation
2966  */
2967 template <class Char, std::size_t N, std::size_t M>
2968 constexpr BasicFixedString<Char, N + M> operator+(
2969     const BasicFixedString<Char, N>& a,
2970     const BasicFixedString<Char, M>& b) noexcept {
2971   return detail::fixedstring::Helper::concat_<Char>(
2972       detail::fixedstring::Helper::data_(a),
2973       a.size(),
2974       detail::fixedstring::Helper::data_(b),
2975       b.size(),
2976       folly::make_index_sequence<N + M>{});
2977 }
2978
2979 /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
2980  * Construct a `BasicFixedString` object from a null-terminated array of
2981  * characters. The capacity and size of the string will be equal to one less
2982  * than the size of the array.
2983  * \pre `a` contains no embedded null characters.
2984  * \pre `a[N-1] == Char(0)`
2985  * \post For a returned string `s`, `s[i]==a[i]` for every `i` in [`0`,`N-1`].
2986  */
2987 template <class Char, std::size_t N>
2988 constexpr BasicFixedString<Char, N - 1u> makeFixedString(
2989     const Char (&a)[N]) noexcept {
2990   return {a};
2991 }
2992
2993 /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
2994  * Swap function
2995  */
2996 template <class Char, std::size_t N>
2997 FOLLY_CPP14_CONSTEXPR void swap(
2998     BasicFixedString<Char, N>& a,
2999     BasicFixedString<Char, N>& b) noexcept {
3000   a.swap(b);
3001 }
3002
3003 inline namespace literals {
3004 inline namespace string_literals {
3005 inline namespace {
3006 // "const std::size_t&" is so that folly::npos has the same address in every
3007 // translation unit. This is to avoid potential violations of the ODR.
3008 constexpr const std::size_t& npos = detail::fixedstring::FixedStringBase::npos;
3009 }
3010
3011 #if defined(__GNUC__)
3012 #pragma GCC diagnostic push
3013 #pragma GCC diagnostic ignored "-Wpragmas"
3014 #pragma GCC diagnostic ignored "-Wgnu-string-literal-operator-template"
3015
3016 /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
3017  * User-defined literals for creating FixedString objects from string literals
3018  * on the compilers that support it.
3019  *
3020  * \par Example:
3021  * \par
3022  * \code
3023  * using namespace folly::string_literals;
3024  * constexpr auto hello = "hello world!"_fs;
3025  * \endcode
3026  *
3027  * \note This requires a GNU compiler extension
3028  *   (-Wgnu-string-literal-operator-template) supported by clang and gcc,
3029  *   proposed for standardization in
3030  *   <http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0424r0.pdf>.
3031  *   \par
3032  *   For portable code, prefer the suffixes `_fs4`, `_fs8`, `_fs16`, `_fs32`,
3033  *   `_fs64`, and `_fs128` for creating instances of types `FixedString<4>`,
3034  *   `FixedString<8>`, `FixedString<16>`, etc.
3035  */
3036 template <class Char, Char... Cs>
3037 constexpr BasicFixedString<Char, sizeof...(Cs)> operator"" _fs() noexcept {
3038   using A = const Char[sizeof...(Cs) + 1u];
3039   // The `+` in `+A{etc}` forces the array type to decay to a pointer
3040   return {+A{Cs..., Char(0)}, sizeof...(Cs)};
3041 }
3042
3043 #pragma GCC diagnostic pop
3044 #endif
3045
3046 #define FOLLY_DEFINE_FIXED_STRING_UDL(N)                     \
3047   constexpr FixedString<N> operator"" _fs##N(                \
3048       const char* that, std::size_t count) noexcept(false) { \
3049     return {that, count};                                    \
3050   }                                                          \
3051 /**/
3052
3053 // Define UDLs _fs4, _fs8, _fs16, etc for FixedString<[4, 8, 16, ...]>
3054 FOLLY_DEFINE_FIXED_STRING_UDL(4)
3055 FOLLY_DEFINE_FIXED_STRING_UDL(8)
3056 FOLLY_DEFINE_FIXED_STRING_UDL(16)
3057 FOLLY_DEFINE_FIXED_STRING_UDL(32)
3058 FOLLY_DEFINE_FIXED_STRING_UDL(64)
3059 FOLLY_DEFINE_FIXED_STRING_UDL(128)
3060
3061 #undef FOLLY_DEFINE_FIXED_STRING_UDL
3062 }
3063 }
3064
3065 // TODO:
3066 // // numeric conversions:
3067 // template <std::size_t N>
3068 // constexpr int stoi(const FixedString<N>& str, int base = 10);
3069 // template <std::size_t N>
3070 // constexpr unsigned stou(const FixedString<N>& str, int base = 10);
3071 // template <std::size_t N>
3072 // constexpr long stol(const FixedString<N>& str, int base = 10);
3073 // template <std::size_t N>
3074 // constexpr unsigned long stoul(const FixedString<N>& str, int base = 10;
3075 // template <std::size_t N>
3076 // constexpr long long stoll(const FixedString<N>& str, int base = 10);
3077 // template <std::size_t N>
3078 // constexpr unsigned long long stoull(const FixedString<N>& str,
3079 // int base = 10);
3080 // template <std::size_t N>
3081 // constexpr float stof(const FixedString<N>& str);
3082 // template <std::size_t N>
3083 // constexpr double stod(const FixedString<N>& str);
3084 // template <std::size_t N>
3085 // constexpr long double stold(const FixedString<N>& str);
3086 // template <int val>
3087 // constexpr FixedString</*...*/> to_fixed_string_i() noexcept;
3088 // template <unsigned val>
3089 // constexpr FixedString</*...*/> to_fixed_string_u() noexcept;
3090 // template <long val>
3091 // constexpr FixedString</*...*/> to_fixed_string_l() noexcept;
3092 // template <unsigned long val>
3093 // constexpr FixedString</*...*/> to_fixed_string_ul() noexcept;
3094 // template <long long val>
3095 // constexpr FixedString</*...*/> to_fixed_string_ll() noexcept
3096 // template <unsigned long long val>
3097 // constexpr FixedString</*...*/> to_fixed_string_ull() noexcept;
3098 }