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