1 // -*- C++ -*- 2 //===----------------------------------------------------------------------===// 3 // 4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5 // See https://llvm.org/LICENSE.txt for license information. 6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7 // 8 //===----------------------------------------------------------------------===// 9 10 #ifndef _LIBCPP___FORMAT_UNICODE_H 11 #define _LIBCPP___FORMAT_UNICODE_H 12 13 #include <__assert> 14 #include <__bit/countl.h> 15 #include <__concepts/same_as.h> 16 #include <__config> 17 #include <__format/extended_grapheme_cluster_table.h> 18 #include <__iterator/concepts.h> 19 #include <__iterator/readable_traits.h> // iter_value_t 20 #include <string_view> 21 22 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 23 # pragma GCC system_header 24 #endif 25 26 _LIBCPP_BEGIN_NAMESPACE_STD 27 28 #if _LIBCPP_STD_VER >= 20 29 30 namespace __unicode { 31 32 // Helper struct for the result of a consume operation. 33 // 34 // The status value for a correct code point is 0. This allows a valid value to 35 // be used without masking. 36 // When the decoding fails it know the number of code units affected. For the 37 // current use-cases that value is not needed, therefore it is not stored. 38 // The escape routine needs the number of code units for both a valid and 39 // invalid character and keeps track of it itself. Doing it in this result 40 // unconditionally would give some overhead when the value is unneeded. 41 struct __consume_result { 42 // When __status == __ok it contains the decoded code point. 43 // Else it contains the replacement character U+FFFD 44 char32_t __code_point : 31; 45 46 enum : char32_t { 47 // Consumed a well-formed code point. 48 __ok = 0, 49 // Encountered invalid UTF-8 50 __error = 1 51 } __status : 1 {__ok}; 52 }; 53 static_assert(sizeof(__consume_result) == sizeof(char32_t)); 54 55 # ifndef _LIBCPP_HAS_NO_UNICODE 56 57 /// Implements the grapheme cluster boundary rules 58 /// 59 /// These rules are used to implement format's width estimation as stated in 60 /// [format.string.std]/11 61 /// 62 /// The Standard refers to UAX \#29 for Unicode 12.0.0 63 /// https://www.unicode.org/reports/tr29/#Grapheme_Cluster_Boundary_Rules 64 /// 65 /// The data tables used are 66 /// https://www.unicode.org/Public/UCD/latest/ucd/auxiliary/GraphemeBreakProperty.txt 67 /// https://www.unicode.org/Public/UCD/latest/ucd/emoji/emoji-data.txt 68 /// https://www.unicode.org/Public/UCD/latest/ucd/auxiliary/GraphemeBreakTest.txt (for testing only) 69 70 inline constexpr char32_t __replacement_character = U'\ufffd'; 71 72 // The error of a consume operation. 73 // 74 // This sets the code point to the replacement character. This code point does 75 // not participate in the grapheme clustering, so grapheme clustering code can 76 // ignore the error status and always use the code point. 77 inline constexpr __consume_result __consume_result_error{__replacement_character, __consume_result::__error}; 78 79 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr bool __is_high_surrogate(char32_t __value) { 80 return __value >= 0xd800 && __value <= 0xdbff; 81 } 82 83 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr bool __is_low_surrogate(char32_t __value) { 84 return __value >= 0xdc00 && __value <= 0xdfff; 85 } 86 87 // https://www.unicode.org/glossary/#surrogate_code_point 88 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline constexpr bool __is_surrogate(char32_t __value) { 89 return __value >= 0xd800 && __value <= 0xdfff; 90 } 91 92 // https://www.unicode.org/glossary/#code_point 93 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline constexpr bool __is_code_point(char32_t __value) { 94 return __value <= 0x10ffff; 95 } 96 97 // https://www.unicode.org/glossary/#unicode_scalar_value 98 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline constexpr bool __is_scalar_value(char32_t __value) { 99 return __unicode::__is_code_point(__value) && !__unicode::__is_surrogate(__value); 100 } 101 102 template <contiguous_iterator _Iterator> 103 requires same_as<iter_value_t<_Iterator>, char> 104 _LIBCPP_HIDE_FROM_ABI constexpr bool __is_continuation(_Iterator __char, int __count) { 105 do { 106 if ((*__char & 0b1100'0000) != 0b1000'0000) 107 return false; 108 --__count; 109 ++__char; 110 } while (__count); 111 return true; 112 } 113 114 /// Helper class to extract a code unit from a Unicode character range. 115 /// 116 /// The stored range is a view. There are multiple specialization for different 117 /// character types. 118 template <class _CharT> 119 class __code_point_view; 120 121 /// UTF-8 specialization. 122 template <> 123 class __code_point_view<char> { 124 using _Iterator = basic_string_view<char>::const_iterator; 125 126 public: 127 _LIBCPP_HIDE_FROM_ABI constexpr explicit __code_point_view(_Iterator __first, _Iterator __last) 128 : __first_(__first), __last_(__last) {} 129 130 _LIBCPP_HIDE_FROM_ABI constexpr bool __at_end() const noexcept { return __first_ == __last_; } 131 _LIBCPP_HIDE_FROM_ABI constexpr _Iterator __position() const noexcept { return __first_; } 132 133 // https://www.unicode.org/versions/latest/ch03.pdf#G7404 134 // Based on Table 3-7, Well-Formed UTF-8 Byte Sequences 135 // 136 // Code Points First Byte Second Byte Third Byte Fourth Byte Remarks 137 // U+0000..U+007F 00..7F U+0000..U+007F 1 code unit range 138 // C0..C1 80..BF invalid overlong encoding 139 // U+0080..U+07FF C2..DF 80..BF U+0080..U+07FF 2 code unit range 140 // E0 80..9F 80..BF invalid overlong encoding 141 // U+0800..U+0FFF E0 A0..BF 80..BF U+0800..U+FFFF 3 code unit range 142 // U+1000..U+CFFF E1..EC 80..BF 80..BF 143 // U+D000..U+D7FF ED 80..9F 80..BF 144 // U+D800..U+DFFF ED A0..BF 80..BF invalid encoding of surrogate code point 145 // U+E000..U+FFFF EE..EF 80..BF 80..BF 146 // F0 80..8F 80..BF 80..BF invalid overlong encoding 147 // U+10000..U+3FFFF F0 90..BF 80..BF 80..BF U+10000..U+10FFFF 4 code unit range 148 // U+40000..U+FFFFF F1..F3 80..BF 80..BF 80..BF 149 // U+100000..U+10FFFF F4 80..8F 80..BF 80..BF 150 // F4 90..BF 80..BF 80..BF U+110000.. invalid code point range 151 // 152 // Unlike other parsers, these invalid entries are tested after decoding. 153 // - The parser always needs to consume these code units 154 // - The code is optimized for well-formed UTF-8 155 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr __consume_result __consume() noexcept { 156 _LIBCPP_ASSERT_UNCATEGORIZED(__first_ != __last_, "can't move beyond the end of input"); 157 158 // Based on the number of leading 1 bits the number of code units in the 159 // code point can be determined. See 160 // https://en.wikipedia.org/wiki/UTF-8#Encoding 161 switch (std::countl_one(static_cast<unsigned char>(*__first_))) { 162 case 0: 163 return {static_cast<unsigned char>(*__first_++)}; 164 165 case 2: { 166 if (__last_ - __first_ < 2 || !__unicode::__is_continuation(__first_ + 1, 1)) [[unlikely]] 167 break; 168 169 char32_t __value = static_cast<unsigned char>(*__first_++) & 0x1f; 170 __value <<= 6; 171 __value |= static_cast<unsigned char>(*__first_++) & 0x3f; 172 173 // These values should be encoded in 1 UTF-8 code unit. 174 if (__value < 0x0080) [[unlikely]] 175 return __consume_result_error; 176 177 return {__value}; 178 } 179 180 case 3: { 181 if (__last_ - __first_ < 3 || !__unicode::__is_continuation(__first_ + 1, 2)) [[unlikely]] 182 break; 183 184 char32_t __value = static_cast<unsigned char>(*__first_++) & 0x0f; 185 __value <<= 6; 186 __value |= static_cast<unsigned char>(*__first_++) & 0x3f; 187 __value <<= 6; 188 __value |= static_cast<unsigned char>(*__first_++) & 0x3f; 189 190 // These values should be encoded in 1 or 2 UTF-8 code units. 191 if (__value < 0x0800) [[unlikely]] 192 return __consume_result_error; 193 194 // A surrogate value is always encoded in 3 UTF-8 code units. 195 if (__unicode::__is_surrogate(__value)) [[unlikely]] 196 return __consume_result_error; 197 198 return {__value}; 199 } 200 201 case 4: { 202 if (__last_ - __first_ < 4 || !__unicode::__is_continuation(__first_ + 1, 3)) [[unlikely]] 203 break; 204 205 char32_t __value = static_cast<unsigned char>(*__first_++) & 0x07; 206 __value <<= 6; 207 __value |= static_cast<unsigned char>(*__first_++) & 0x3f; 208 __value <<= 6; 209 __value |= static_cast<unsigned char>(*__first_++) & 0x3f; 210 __value <<= 6; 211 __value |= static_cast<unsigned char>(*__first_++) & 0x3f; 212 213 // These values should be encoded in 1, 2, or 3 UTF-8 code units. 214 if (__value < 0x10000) [[unlikely]] 215 return __consume_result_error; 216 217 // A value too large is always encoded in 4 UTF-8 code units. 218 if (!__unicode::__is_code_point(__value)) [[unlikely]] 219 return __consume_result_error; 220 221 return {__value}; 222 } 223 } 224 // An invalid number of leading ones can be garbage or a code unit in the 225 // middle of a code point. By consuming one code unit the parser may get 226 // "in sync" after a few code units. 227 ++__first_; 228 return __consume_result_error; 229 } 230 231 private: 232 _Iterator __first_; 233 _Iterator __last_; 234 }; 235 236 # ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS 237 _LIBCPP_HIDE_FROM_ABI constexpr bool __is_surrogate_pair_high(wchar_t __value) { 238 return __value >= 0xd800 && __value <= 0xdbff; 239 } 240 241 _LIBCPP_HIDE_FROM_ABI constexpr bool __is_surrogate_pair_low(wchar_t __value) { 242 return __value >= 0xdc00 && __value <= 0xdfff; 243 } 244 245 /// This specialization depends on the size of wchar_t 246 /// - 2 UTF-16 (for example Windows and AIX) 247 /// - 4 UTF-32 (for example Linux) 248 template <> 249 class __code_point_view<wchar_t> { 250 using _Iterator = typename basic_string_view<wchar_t>::const_iterator; 251 252 public: 253 static_assert(sizeof(wchar_t) == 2 || sizeof(wchar_t) == 4, "sizeof(wchar_t) has a not implemented value"); 254 255 _LIBCPP_HIDE_FROM_ABI constexpr explicit __code_point_view(_Iterator __first, _Iterator __last) 256 : __first_(__first), __last_(__last) {} 257 258 _LIBCPP_HIDE_FROM_ABI constexpr _Iterator __position() const noexcept { return __first_; } 259 _LIBCPP_HIDE_FROM_ABI constexpr bool __at_end() const noexcept { return __first_ == __last_; } 260 261 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr __consume_result __consume() noexcept { 262 _LIBCPP_ASSERT_UNCATEGORIZED(__first_ != __last_, "can't move beyond the end of input"); 263 264 char32_t __value = static_cast<char32_t>(*__first_++); 265 if constexpr (sizeof(wchar_t) == 2) { 266 if (__unicode::__is_low_surrogate(__value)) [[unlikely]] 267 return __consume_result_error; 268 269 if (__unicode::__is_high_surrogate(__value)) { 270 if (__first_ == __last_ || !__unicode::__is_low_surrogate(static_cast<char32_t>(*__first_))) [[unlikely]] 271 return __consume_result_error; 272 273 __value -= 0xd800; 274 __value <<= 10; 275 __value += static_cast<char32_t>(*__first_++) - 0xdc00; 276 __value += 0x10000; 277 278 if (!__unicode::__is_code_point(__value)) [[unlikely]] 279 return __consume_result_error; 280 } 281 } else { 282 if (!__unicode::__is_scalar_value(__value)) [[unlikely]] 283 return __consume_result_error; 284 } 285 286 return {__value}; 287 } 288 289 private: 290 _Iterator __first_; 291 _Iterator __last_; 292 }; 293 # endif // _LIBCPP_HAS_NO_WIDE_CHARACTERS 294 295 _LIBCPP_HIDE_FROM_ABI constexpr bool __at_extended_grapheme_cluster_break( 296 bool& __ri_break_allowed, 297 bool __has_extened_pictographic, 298 __extended_grapheme_custer_property_boundary::__property __prev, 299 __extended_grapheme_custer_property_boundary::__property __next) { 300 using __extended_grapheme_custer_property_boundary::__property; 301 302 __has_extened_pictographic |= __prev == __property::__Extended_Pictographic; 303 304 // https://www.unicode.org/reports/tr29/tr29-39.html#Grapheme_Cluster_Boundary_Rules 305 306 // *** Break at the start and end of text, unless the text is empty. *** 307 308 _LIBCPP_ASSERT_UNCATEGORIZED(__prev != __property::__sot, "should be handled in the constructor"); // GB1 309 _LIBCPP_ASSERT_UNCATEGORIZED(__prev != __property::__eot, "should be handled by our caller"); // GB2 310 311 // *** Do not break between a CR and LF. Otherwise, break before and after controls. *** 312 if (__prev == __property::__CR && __next == __property::__LF) // GB3 313 return false; 314 315 if (__prev == __property::__Control || __prev == __property::__CR || __prev == __property::__LF) // GB4 316 return true; 317 318 if (__next == __property::__Control || __next == __property::__CR || __next == __property::__LF) // GB5 319 return true; 320 321 // *** Do not break Hangul syllable sequences. *** 322 if (__prev == __property::__L && 323 (__next == __property::__L || __next == __property::__V || __next == __property::__LV || 324 __next == __property::__LVT)) // GB6 325 return false; 326 327 if ((__prev == __property::__LV || __prev == __property::__V) && 328 (__next == __property::__V || __next == __property::__T)) // GB7 329 return false; 330 331 if ((__prev == __property::__LVT || __prev == __property::__T) && __next == __property::__T) // GB8 332 return false; 333 334 // *** Do not break before extending characters or ZWJ. *** 335 if (__next == __property::__Extend || __next == __property::__ZWJ) 336 return false; // GB9 337 338 // *** Do not break before SpacingMarks, or after Prepend characters. *** 339 if (__next == __property::__SpacingMark) // GB9a 340 return false; 341 342 if (__prev == __property::__Prepend) // GB9b 343 return false; 344 345 // *** Do not break within emoji modifier sequences or emoji zwj sequences. *** 346 347 // GB11 \p{Extended_Pictographic} Extend* ZWJ x \p{Extended_Pictographic} 348 // 349 // Note that several parts of this rule are matched by GB9: Any x (Extend | ZWJ) 350 // - \p{Extended_Pictographic} x Extend 351 // - Extend x Extend 352 // - \p{Extended_Pictographic} x ZWJ 353 // - Extend x ZWJ 354 // 355 // So the only case left to test is 356 // - \p{Extended_Pictographic}' x ZWJ x \p{Extended_Pictographic} 357 // where \p{Extended_Pictographic}' is stored in __has_extened_pictographic 358 if (__has_extened_pictographic && __prev == __property::__ZWJ && __next == __property::__Extended_Pictographic) 359 return false; 360 361 // *** Do not break within emoji flag sequences *** 362 363 // That is, do not break between regional indicator (RI) symbols if there 364 // is an odd number of RI characters before the break point. 365 366 if (__prev == __property::__Regional_Indicator && __next == __property::__Regional_Indicator) { // GB12 + GB13 367 __ri_break_allowed = !__ri_break_allowed; 368 return __ri_break_allowed; 369 } 370 371 // *** Otherwise, break everywhere. *** 372 return true; // GB999 373 } 374 375 /// Helper class to extract an extended grapheme cluster from a Unicode character range. 376 /// 377 /// This function is used to determine the column width of an extended grapheme 378 /// cluster. In order to do that only the first code point is evaluated. 379 /// Therefore only this code point is extracted. 380 template <class _CharT> 381 class __extended_grapheme_cluster_view { 382 using _Iterator = typename basic_string_view<_CharT>::const_iterator; 383 384 public: 385 _LIBCPP_HIDE_FROM_ABI constexpr explicit __extended_grapheme_cluster_view(_Iterator __first, _Iterator __last) 386 : __code_point_view_(__first, __last), 387 __next_code_point_(__code_point_view_.__consume().__code_point), 388 __next_prop_(__extended_grapheme_custer_property_boundary::__get_property(__next_code_point_)) {} 389 390 struct __cluster { 391 /// The first code point of the extended grapheme cluster. 392 /// 393 /// The first code point is used to estimate the width of the extended 394 /// grapheme cluster. 395 char32_t __code_point_; 396 397 /// Points one beyond the last code unit in the extended grapheme cluster. 398 /// 399 /// It's expected the caller has the start position and thus can determine 400 /// the code unit range of the extended grapheme cluster. 401 _Iterator __last_; 402 }; 403 404 _LIBCPP_HIDE_FROM_ABI constexpr __cluster __consume() { 405 _LIBCPP_ASSERT_UNCATEGORIZED( 406 __next_prop_ != __extended_grapheme_custer_property_boundary::__property::__eot, 407 "can't move beyond the end of input"); 408 409 char32_t __code_point = __next_code_point_; 410 if (!__code_point_view_.__at_end()) 411 return {__code_point, __get_break()}; 412 413 __next_prop_ = __extended_grapheme_custer_property_boundary::__property::__eot; 414 return {__code_point, __code_point_view_.__position()}; 415 } 416 417 private: 418 __code_point_view<_CharT> __code_point_view_; 419 420 char32_t __next_code_point_; 421 __extended_grapheme_custer_property_boundary::__property __next_prop_; 422 423 _LIBCPP_HIDE_FROM_ABI constexpr _Iterator __get_break() { 424 bool __ri_break_allowed = true; 425 bool __has_extened_pictographic = false; 426 while (true) { 427 _Iterator __result = __code_point_view_.__position(); 428 __extended_grapheme_custer_property_boundary::__property __prev = __next_prop_; 429 if (__code_point_view_.__at_end()) { 430 __next_prop_ = __extended_grapheme_custer_property_boundary::__property::__eot; 431 return __result; 432 } 433 __next_code_point_ = __code_point_view_.__consume().__code_point; 434 __next_prop_ = __extended_grapheme_custer_property_boundary::__get_property(__next_code_point_); 435 436 __has_extened_pictographic |= 437 __prev == __extended_grapheme_custer_property_boundary::__property::__Extended_Pictographic; 438 439 if (__at_extended_grapheme_cluster_break(__ri_break_allowed, __has_extened_pictographic, __prev, __next_prop_)) 440 return __result; 441 } 442 } 443 }; 444 445 template <contiguous_iterator _Iterator> 446 __extended_grapheme_cluster_view(_Iterator, _Iterator) -> __extended_grapheme_cluster_view<iter_value_t<_Iterator>>; 447 448 # else // _LIBCPP_HAS_NO_UNICODE 449 450 // For ASCII every character is a "code point". 451 // This makes it easier to write code agnostic of the _LIBCPP_HAS_NO_UNICODE define. 452 template <class _CharT> 453 class __code_point_view { 454 using _Iterator = typename basic_string_view<_CharT>::const_iterator; 455 456 public: 457 _LIBCPP_HIDE_FROM_ABI constexpr explicit __code_point_view(_Iterator __first, _Iterator __last) 458 : __first_(__first), __last_(__last) {} 459 460 _LIBCPP_HIDE_FROM_ABI constexpr bool __at_end() const noexcept { return __first_ == __last_; } 461 _LIBCPP_HIDE_FROM_ABI constexpr _Iterator __position() const noexcept { return __first_; } 462 463 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr __consume_result __consume() noexcept { 464 _LIBCPP_ASSERT_UNCATEGORIZED(__first_ != __last_, "can't move beyond the end of input"); 465 return {static_cast<char32_t>(*__first_++)}; 466 } 467 468 private: 469 _Iterator __first_; 470 _Iterator __last_; 471 }; 472 473 # endif // _LIBCPP_HAS_NO_UNICODE 474 475 } // namespace __unicode 476 477 #endif //_LIBCPP_STD_VER >= 20 478 479 _LIBCPP_END_NAMESPACE_STD 480 481 #endif // _LIBCPP___FORMAT_UNICODE_H 482