string.hh (12527B)
1 #ifndef string_hh_INCLUDED 2 #define string_hh_INCLUDED 3 4 #include "memory.hh" 5 #include "hash.hh" 6 #include "units.hh" 7 #include "utf8.hh" 8 9 #include <climits> 10 #include <cstddef> 11 #include <cstring> 12 13 namespace Kakoune 14 { 15 16 class StringView; 17 18 template<typename Type, typename CharType> 19 class StringOps 20 { 21 public: 22 using value_type = CharType; 23 24 friend constexpr size_t hash_value(const Type& str) 25 { 26 return fnv1a(str.data(), (int)str.length()); 27 } 28 29 using iterator = CharType*; 30 using const_iterator = const CharType*; 31 using reverse_iterator = std::reverse_iterator<iterator>; 32 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 33 34 [[gnu::always_inline]] 35 iterator begin() { return type().data(); } 36 37 [[gnu::always_inline]] 38 const_iterator begin() const { return type().data(); } 39 40 [[gnu::always_inline]] 41 iterator end() { return type().data() + type().length(); } 42 43 [[gnu::always_inline]] 44 const_iterator end() const { return type().data() + type().length(); } 45 46 reverse_iterator rbegin() { return reverse_iterator{end()}; } 47 const_reverse_iterator rbegin() const { return const_reverse_iterator{end()}; } 48 49 reverse_iterator rend() { return reverse_iterator{begin()}; } 50 const_reverse_iterator rend() const { return const_reverse_iterator{begin()}; } 51 52 CharType& front() { return *type().data(); } 53 const CharType& front() const { return *type().data(); } 54 CharType& back() { return type().data()[(int)type().length() - 1]; } 55 const CharType& back() const { return type().data()[(int)type().length() - 1]; } 56 57 [[gnu::always_inline]] 58 CharType& operator[](ByteCount pos) { return type().data()[(int)pos]; } 59 60 [[gnu::always_inline]] 61 const CharType& operator[](ByteCount pos) const { return type().data()[(int)pos]; } 62 63 Codepoint operator[](CharCount pos) const 64 { return utf8::codepoint(utf8::advance(begin(), end(), pos), end()); } 65 66 CharCount char_length() const { return utf8::distance(begin(), end()); } 67 ColumnCount column_length() const { return utf8::column_distance(begin(), end()); } 68 69 [[gnu::always_inline]] 70 bool empty() const { return type().length() == 0_byte; } 71 72 bool starts_with(StringView str) const; 73 bool ends_with(StringView str) const; 74 75 ByteCount byte_count_to(CharCount count) const 76 { return utf8::advance(begin(), end(), count) - begin(); } 77 78 ByteCount byte_count_to(ColumnCount count) const 79 { return utf8::advance(begin(), end(), count) - begin(); } 80 81 CharCount char_count_to(ByteCount count) const 82 { return utf8::distance(begin(), begin() + count); } 83 84 ColumnCount column_count_to(ByteCount count) const 85 { return utf8::column_distance(begin(), begin() + count); } 86 87 StringView substr(ByteCount from, ByteCount length = -1) const; 88 StringView substr(CharCount from, CharCount length = -1) const; 89 StringView substr(ColumnCount from, ColumnCount length = -1) const; 90 91 private: 92 [[gnu::always_inline]] 93 Type& type() { return *static_cast<Type*>(this); } 94 [[gnu::always_inline]] 95 const Type& type() const { return *static_cast<const Type*>(this); } 96 }; 97 98 constexpr ByteCount strlen(const char* s) 99 { 100 int i = 0; 101 while (*s++ != 0) 102 ++i; 103 return {i}; 104 } 105 106 class String : public StringOps<String, char> 107 { 108 public: 109 String() {} 110 String(const char* content) : m_data(content, (size_t)strlen(content)) {} 111 String(const char* content, ByteCount len) : m_data(content, (size_t)len) {} 112 String(const char* begin, const char* end) : m_data(begin, end-begin) {} 113 explicit String(Codepoint cp, CharCount count = 1); 114 explicit String(Codepoint cp, ColumnCount count); 115 explicit String(StringView str); 116 117 struct NoCopy{}; 118 String(NoCopy, StringView str); 119 120 static String no_copy(StringView str); 121 122 [[gnu::always_inline]] 123 char* data() { return m_data.data(); } 124 125 [[gnu::always_inline]] 126 const char* data() const { return m_data.data(); } 127 128 [[gnu::always_inline]] 129 ByteCount length() const { return m_data.size(); } 130 131 [[gnu::always_inline]] 132 const char* c_str() const { return m_data.data(); } 133 134 [[gnu::always_inline]] 135 void append(const char* data, ByteCount count) { m_data.append(data, (size_t)count); } 136 137 void clear() { m_data.clear(); } 138 139 void push_back(char c) { m_data.append(&c, 1); } 140 void force_size(ByteCount size) { m_data.force_size((size_t)size); } 141 void reserve(ByteCount size) { m_data.reserve((size_t)size); } 142 void resize(ByteCount size, char c); 143 144 static const String ms_empty; 145 static constexpr const char* option_type_name = "str"; 146 147 // String data storage using small string optimization. 148 // 149 // The MSB of the last byte is used to flag if we are using the allocated buffer 150 // (1) or in-situ storage, the small one (0). That means the allocated capacity 151 // cannot use its most significant byte, so we effectively limit capacity to 152 // 2^24 on 32bit arch, and 2^56 on 64bit. 153 // 154 // There is also a special NoCopy mode in which the data referred to is un-owned. 155 // It is indicated by being in Long mode with capacity == 0. 156 struct Data 157 { 158 using Alloc = Allocator<char, MemoryDomain::String>; 159 160 Data() { set_empty(); } 161 Data(NoCopy, const char* data, size_t size) : u{Long{const_cast<char*>(data), 162 size, 163 /*capacity=*/0, 164 /*mode=*/Long::active_mask}} {} 165 166 Data(const char* data, size_t size, size_t capacity); 167 Data(const char* data, size_t size) : Data(data, size, size) {} 168 Data(const Data& other) : Data{other.data(), other.size()} {} 169 170 ~Data() { release(); } 171 Data(Data&& other) noexcept : u{other.u} { other.set_empty(); } 172 Data& operator=(const Data& other); 173 Data& operator=(Data&& other) noexcept; 174 175 bool is_long() const { return (u.l.mode & Long::active_mask) != 0; } 176 size_t size() const { return is_long() ? u.l.size : (Short::capacity - u.s.remaining_size); } 177 size_t capacity() const { return is_long() ? u.l.capacity : Short::capacity; } 178 179 const char* data() const { return is_long() ? u.l.ptr : u.s.string; } 180 char* data() { return is_long() ? u.l.ptr : u.s.string; } 181 182 template<bool copy = true> 183 void reserve(size_t new_capacity); 184 void set_size(size_t size); 185 void force_size(size_t new_size); 186 void append(const char* str, size_t len); 187 void clear(); 188 189 private: 190 struct Long 191 { 192 static constexpr size_t capacity_bits = CHAR_BIT * (sizeof(size_t) - 1); 193 static constexpr size_t max_capacity = ((size_t)1 << capacity_bits) - 1; 194 195 char* ptr; 196 size_t size; 197 size_t capacity : capacity_bits; 198 unsigned char mode; 199 static constexpr unsigned char active_mask = 0b1000'0000; 200 }; 201 static_assert(sizeof(Long) == sizeof(char*) * 3); 202 203 struct Short 204 { 205 static constexpr size_t capacity = sizeof(Long) - 1; 206 char string[capacity]; 207 // When string is full remaining_size will be 0 and be the null terminator. 208 // When string is empty remaining size will be 23 (0b00010111) 209 // and not collide with Long::active_mask. 210 unsigned char remaining_size; 211 }; 212 static_assert(offsetof(Long, mode) == offsetof(Short, remaining_size)); 213 214 union 215 { 216 Long l; 217 Short s; 218 } u; 219 220 void release() 221 { 222 if (is_long() and (u.l.capacity != 0)) 223 Alloc{}.deallocate(u.l.ptr, u.l.capacity+1); 224 } 225 226 void set_empty() { u.s.remaining_size = Short::capacity; u.s.string[0] = '\0'; } 227 void set_short(const char* data, size_t size); 228 }; 229 230 private: 231 Data m_data; 232 }; 233 234 class StringView : public StringOps<StringView, const char> 235 { 236 public: 237 StringView() = default; 238 constexpr StringView(const char* data, ByteCount length) 239 : m_data{data}, m_length{length} {} 240 constexpr StringView(const char* data) : m_data{data}, m_length{data ? strlen(data) : 0} {} 241 constexpr StringView(const char* begin, const char* end) : m_data{begin}, m_length{(int)(end - begin)} {} 242 StringView(const String& str) : m_data{str.data()}, m_length{(int)str.length()} {} 243 StringView(const char& c) : m_data(&c), m_length(1) {} 244 StringView(int c) = delete; 245 StringView(Codepoint c) = delete; 246 247 [[gnu::always_inline]] 248 constexpr const char* data() const { return m_data; } 249 250 [[gnu::always_inline]] 251 constexpr ByteCount length() const { return m_length; } 252 253 String str() const { return {m_data, m_length}; } 254 255 struct ZeroTerminatedString 256 { 257 ZeroTerminatedString(const char* begin, const char* end) 258 { 259 if (*end == '\0') 260 unowned = begin; 261 else 262 owned = String::Data(begin, end - begin); 263 } 264 operator const char*() const { return unowned ? unowned : owned.data(); } 265 266 private: 267 String::Data owned; 268 const char* unowned = nullptr; 269 }; 270 ZeroTerminatedString zstr() const { return {begin(), end()}; } 271 272 private: 273 const char* m_data; 274 ByteCount m_length; 275 }; 276 277 static_assert(std::is_trivial<StringView>::value, ""); 278 279 template<> struct HashCompatible<String, StringView> : std::true_type {}; 280 template<> struct HashCompatible<StringView, String> : std::true_type {}; 281 282 inline String::String(StringView str) : String{str.begin(), str.length()} {} 283 inline String::String(NoCopy, StringView str) : m_data{NoCopy{}, str.begin(), (size_t)str.length()} {} 284 inline String String::no_copy(StringView str) { return {NoCopy{}, str}; } 285 286 template<typename Type, typename CharType> 287 inline StringView StringOps<Type, CharType>::substr(ByteCount from, ByteCount length) const 288 { 289 const auto str_length = type().length(); 290 const auto max_length = str_length - from; 291 kak_assert(from >= 0 and max_length >= 0); 292 return StringView{type().data() + (int)from, length >= 0 and length < max_length ? length : max_length}; 293 } 294 295 template<typename Type, typename CharType> 296 inline StringView StringOps<Type, CharType>::substr(CharCount from, CharCount length) const 297 { 298 auto beg = utf8::advance(begin(), end(), from); 299 return StringView{beg, length >= 0 ? utf8::advance(beg, end(), length) : end()}; 300 } 301 302 template<typename Type, typename CharType> 303 inline StringView StringOps<Type, CharType>::substr(ColumnCount from, ColumnCount length) const 304 { 305 auto beg = utf8::advance(begin(), end(), from); 306 return StringView{beg, (length >= 0) ? utf8::advance(beg, end(), length) : end()}; 307 } 308 309 template<typename Type, typename CharType> 310 inline bool StringOps<Type, CharType>::starts_with(StringView str) const 311 { 312 if (type().length() < str.length()) 313 return false; 314 return substr(0, str.length()) == str; 315 } 316 317 template<typename Type, typename CharType> 318 inline bool StringOps<Type, CharType>::ends_with(StringView str) const 319 { 320 if (type().length() < str.length()) 321 return false; 322 return substr(type().length() - str.length()) == str; 323 } 324 325 inline String& operator+=(String& lhs, StringView rhs) 326 { 327 lhs.append(rhs.data(), rhs.length()); 328 return lhs; 329 } 330 331 inline String operator+(StringView lhs, StringView rhs) 332 { 333 String res; 334 res.reserve(lhs.length() + rhs.length()); 335 res.append(lhs.data(), lhs.length()); 336 res.append(rhs.data(), rhs.length()); 337 return res; 338 } 339 340 [[gnu::always_inline]] 341 inline bool operator==(const StringView& lhs, const StringView& rhs) 342 { 343 return lhs.length() == rhs.length() and 344 (lhs.empty() or std::memcmp(lhs.begin(), rhs.begin(), (size_t)lhs.length()) == 0); 345 } 346 347 inline auto operator<=>(const StringView& lhs, const StringView& rhs) 348 { 349 auto lit = lhs.begin(), lend = lhs.end(), rit = rhs.begin(), rend = rhs.end(); 350 while (lit != lend and rit != rend) { 351 if (auto cmp = *lit++ <=> *rit++; cmp != 0) 352 return cmp; 353 } 354 if (lit == lend and rit == rend) 355 return std::strong_ordering::equal; 356 return lit == lend ? std::strong_ordering::less : std::strong_ordering::greater; 357 358 } 359 360 inline String operator""_str(const char* str, size_t) 361 { 362 return String(str); 363 } 364 365 inline StringView operator""_sv(const char* str, size_t) 366 { 367 return StringView{str}; 368 } 369 370 } 371 372 #endif // string_hh_INCLUDED