1 // Copyright 2022 The Pigweed Authors 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not 4 // use this file except in compliance with the License. You may obtain a copy of 5 // the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 12 // License for the specific language governing permissions and limitations under 13 // the License. 14 #pragma once 15 16 #include <limits> 17 #include <string> // for std::char_traits 18 #include <string_view> 19 #include <type_traits> 20 21 #include "pw_assert/assert.h" 22 23 namespace pw::string_impl { 24 25 // pw::InlineString<>::size_type is unsigned short so the capacity and current 26 // size fit into a single word. 27 using size_type = unsigned short; 28 29 // Reserved capacity that is used to represent a generic-length 30 // pw::InlineString. 31 inline constexpr size_t kGeneric = size_type(-1); 32 33 template <typename T> 34 inline constexpr bool kUseStdCharTraits = 35 #if !defined(__cpp_lib_constexpr_string) || __cpp_lib_constexpr_string < 201907L 36 false && 37 #endif // __cpp_lib_constexpr_string 38 !std::is_same_v<T, std::byte>; 39 40 // Provide a minimal custom traits class for use by std::byte and if 41 // std::char_traits is not yet fully constexpr (__cpp_lib_constexpr_string). 42 template <typename T, bool = kUseStdCharTraits<T>> 43 struct char_traits { 44 using char_type = T; 45 using int_type = unsigned int; 46 assignchar_traits47 static constexpr void assign(T& dest, const T& source) noexcept { 48 dest = source; 49 } 50 assignchar_traits51 static constexpr T* assign(T* dest, size_t count, T value) { 52 for (size_t i = 0; i < count; ++i) { 53 dest[i] = value; 54 } 55 return dest; 56 } 57 eqchar_traits58 static constexpr bool eq(T lhs, T rhs) { return lhs == rhs; } 59 movechar_traits60 static constexpr T* move(T* dest, const T* source, size_t count) { 61 if (dest < source) { 62 char_traits<T>::copy(dest, source, count); 63 } else if (source < dest) { 64 for (size_t i = count; i != 0; --i) { 65 char_traits<T>::assign(dest[i - 1], source[i - 1]); 66 } 67 } 68 return dest; 69 } 70 copychar_traits71 static constexpr T* copy(T* dest, const T* source, size_t count) { 72 for (size_t i = 0; i < count; ++i) { 73 char_traits<T>::assign(dest[i], source[i]); 74 } 75 return dest; 76 } 77 comparechar_traits78 static constexpr int compare(const T* lhs, const T* rhs, size_t count) { 79 for (size_t i = 0; i < count; ++i) { 80 if (lhs[i] < rhs[i]) { 81 return -1; 82 } 83 if (rhs[i] < lhs[i]) { 84 return 1; 85 } 86 } 87 return 0; 88 } 89 }; 90 91 // Use std::char_traits for character types when it fully supports constexpr. 92 template <typename T> 93 struct char_traits<T, true> : public std::char_traits<T> {}; 94 95 // string_views for byte strings need to use Pigweed's custom char_traits since 96 // std::char_traits<std::byte> is not defined. (Alternately, could specialize 97 // std::char_traits, but this is simpler.) basic_string_view<byte> won't be 98 // commonly used (byte spans are more common), but support it for completeness. 99 template <typename T> 100 struct StringViewType { 101 using type = std::basic_string_view<T>; 102 }; 103 104 template <> 105 struct StringViewType<std::byte> { 106 using type = std::basic_string_view<std::byte, char_traits<std::byte>>; 107 }; 108 109 template <typename T> 110 using View = typename StringViewType<T>::type; 111 112 // Aliases for disabling overloads with SFINAE. 113 template <typename CharType, typename T> 114 using EnableIfNonArrayCharPointer = std::enable_if_t< 115 std::is_pointer<T>::value && !std::is_array<T>::value && 116 std::is_same<CharType, std::remove_cv_t<std::remove_pointer_t<T>>>::value>; 117 118 template <typename T> 119 using EnableIfInputIterator = std::enable_if_t< 120 std::is_convertible<typename std::iterator_traits<T>::iterator_category, 121 std::input_iterator_tag>::value>; 122 123 template <typename CharType, typename T> 124 using EnableIfStringViewLike = 125 std::enable_if_t<std::is_convertible<const T&, View<CharType>>() && 126 !std::is_convertible<const T&, const CharType*>()>; 127 128 template <typename CharType, typename T> 129 using EnableIfStringViewLikeButNotStringView = 130 std::enable_if_t<!std::is_same<T, View<CharType>>() && 131 std::is_convertible<const T&, View<CharType>>() && 132 !std::is_convertible<const T&, const CharType*>()>; 133 134 // Used in static_asserts to check that a C array fits in an InlineString. 135 constexpr bool NullTerminatedArrayFitsInString( 136 size_t null_terminated_array_size, size_t capacity) { 137 return null_terminated_array_size > 0u && 138 null_terminated_array_size - 1 <= capacity && 139 null_terminated_array_size - 1 < kGeneric; 140 } 141 142 // Used to safely convert various numeric types to `size_type`. 143 template <typename T> 144 constexpr size_type CheckedCastToSize(T num) { 145 static_assert(std::is_unsigned<T>::value, 146 "Attempted to convert signed value to string length, but only " 147 "unsigned types are allowed."); 148 PW_ASSERT(num < std::numeric_limits<size_type>::max()); 149 return static_cast<size_type>(num); 150 } 151 152 // Constexpr utility functions for pw::InlineString. These are NOT intended for 153 // general use. These mostly map directly to general purpose standard library 154 // utilities that are not constexpr until C++20. 155 156 // Calculates the length of a C string up to the capacity. Returns capacity + 1 157 // if the string is longer than the capacity. This replaces 158 // std::char_traits<T>::length, which is unbounded. The string must contain at 159 // least one character. 160 template <typename T> 161 constexpr size_t BoundedStringLength(const T* string, size_t capacity) { 162 size_t length = 0; 163 for (; length <= capacity; ++length) { 164 if (char_traits<T>::eq(string[length], T())) { 165 break; 166 } 167 } 168 return length; // length is capacity + 1 if T() was not found. 169 } 170 171 // As with std::string, InlineString treats literals and character arrays as 172 // null-terminated strings. ArrayStringLength checks that the array size fits 173 // within size_t and asserts if no null terminator was found in the array. 174 template <typename T> 175 constexpr size_t ArrayStringLength(const T* array, 176 size_t max_string_length, 177 size_t capacity) { 178 const size_t max_length = std::min(max_string_length, capacity); 179 const size_t length = BoundedStringLength(array, max_length); 180 PW_ASSERT(length <= max_string_length); // The array is not null terminated 181 return length; 182 } 183 184 template <typename T, size_t kCharArraySize> 185 constexpr size_t ArrayStringLength(const T (&array)[kCharArraySize], 186 size_t capacity) { 187 static_assert(kCharArraySize > 0u, "C arrays cannot have a length of 0"); 188 static_assert(kCharArraySize - 1 < kGeneric, 189 "The size of this literal or character array is too large " 190 "for pw::InlineString<>::size_t"); 191 return ArrayStringLength( 192 array, static_cast<size_t>(kCharArraySize - 1), capacity); 193 } 194 195 // Constexpr version of std::copy that returns the number of copied characters. 196 // Does NOT null-terminate the string. 197 template <typename InputIterator, typename T> 198 constexpr size_t IteratorCopy(InputIterator begin, 199 InputIterator end, 200 T* const string_begin, 201 const T* const string_end) { 202 T* current_position = string_begin; 203 204 // If `InputIterator` is a `LegacyRandomAccessIterator`, the bounds check can 205 // be done up front, allowing the compiler more flexibility in optimizing the 206 // loop. 207 using category = 208 typename std::iterator_traits<InputIterator>::iterator_category; 209 if constexpr (std::is_same_v<category, std::random_access_iterator_tag>) { 210 PW_ASSERT(begin <= end); 211 PW_ASSERT(end - begin <= string_end - string_begin); 212 for (InputIterator it = begin; it != end; ++it) { 213 char_traits<T>::assign(*current_position++, *it); 214 } 215 } else { 216 for (InputIterator it = begin; it != end; ++it) { 217 PW_ASSERT(current_position != string_end); 218 char_traits<T>::assign(*current_position++, *it); 219 } 220 } 221 return static_cast<size_t>(current_position - string_begin); 222 } 223 224 // Constexpr lexicographical comparison. 225 template <typename T> 226 constexpr int Compare(const T* lhs, 227 size_t lhs_size, 228 const T* rhs, 229 size_t rhs_size) noexcept { 230 int result = char_traits<T>::compare(lhs, rhs, std::min(lhs_size, rhs_size)); 231 if (result != 0 || lhs_size == rhs_size) { 232 return result; 233 } 234 return lhs_size < rhs_size ? -1 : 1; 235 } 236 237 } // namespace pw::string_impl 238