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_INTERNAL(__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_INTERNAL(__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_INTERNAL(__prev != __property::__sot, "should be handled in the constructor"); // GB1 309 _LIBCPP_ASSERT_INTERNAL(__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 && (__next == __property::__L || __next == __property::__V || 323 __next == __property::__LV || __next == __property::__LVT)) // GB6 324 return false; 325 326 if ((__prev == __property::__LV || __prev == __property::__V) && 327 (__next == __property::__V || __next == __property::__T)) // GB7 328 return false; 329 330 if ((__prev == __property::__LVT || __prev == __property::__T) && __next == __property::__T) // GB8 331 return false; 332 333 // *** Do not break before extending characters or ZWJ. *** 334 if (__next == __property::__Extend || __next == __property::__ZWJ) 335 return false; // GB9 336 337 // *** Do not break before SpacingMarks, or after Prepend characters. *** 338 if (__next == __property::__SpacingMark) // GB9a 339 return false; 340 341 if (__prev == __property::__Prepend) // GB9b 342 return false; 343 344 // *** Do not break within emoji modifier sequences or emoji zwj sequences. *** 345 346 // GB11 \p{Extended_Pictographic} Extend* ZWJ x \p{Extended_Pictographic} 347 // 348 // Note that several parts of this rule are matched by GB9: Any x (Extend | ZWJ) 349 // - \p{Extended_Pictographic} x Extend 350 // - Extend x Extend 351 // - \p{Extended_Pictographic} x ZWJ 352 // - Extend x ZWJ 353 // 354 // So the only case left to test is 355 // - \p{Extended_Pictographic}' x ZWJ x \p{Extended_Pictographic} 356 // where \p{Extended_Pictographic}' is stored in __has_extened_pictographic 357 if (__has_extened_pictographic && __prev == __property::__ZWJ && __next == __property::__Extended_Pictographic) 358 return false; 359 360 // *** Do not break within emoji flag sequences *** 361 362 // That is, do not break between regional indicator (RI) symbols if there 363 // is an odd number of RI characters before the break point. 364 365 if (__prev == __property::__Regional_Indicator && __next == __property::__Regional_Indicator) { // GB12 + GB13 366 __ri_break_allowed = !__ri_break_allowed; 367 return __ri_break_allowed; 368 } 369 370 // *** Otherwise, break everywhere. *** 371 return true; // GB999 372 } 373 374 /// Helper class to extract an extended grapheme cluster from a Unicode character range. 375 /// 376 /// This function is used to determine the column width of an extended grapheme 377 /// cluster. In order to do that only the first code point is evaluated. 378 /// Therefore only this code point is extracted. 379 template <class _CharT> 380 class __extended_grapheme_cluster_view { 381 using _Iterator = typename basic_string_view<_CharT>::const_iterator; 382 383 public: 384 _LIBCPP_HIDE_FROM_ABI constexpr explicit __extended_grapheme_cluster_view(_Iterator __first, _Iterator __last) 385 : __code_point_view_(__first, __last), 386 __next_code_point_(__code_point_view_.__consume().__code_point), 387 __next_prop_(__extended_grapheme_custer_property_boundary::__get_property(__next_code_point_)) {} 388 389 struct __cluster { 390 /// The first code point of the extended grapheme cluster. 391 /// 392 /// The first code point is used to estimate the width of the extended 393 /// grapheme cluster. 394 char32_t __code_point_; 395 396 /// Points one beyond the last code unit in the extended grapheme cluster. 397 /// 398 /// It's expected the caller has the start position and thus can determine 399 /// the code unit range of the extended grapheme cluster. 400 _Iterator __last_; 401 }; 402 403 _LIBCPP_HIDE_FROM_ABI constexpr __cluster __consume() { 404 _LIBCPP_ASSERT_INTERNAL(__next_prop_ != __extended_grapheme_custer_property_boundary::__property::__eot, 405 "can't move beyond the end of input"); 406 407 char32_t __code_point = __next_code_point_; 408 if (!__code_point_view_.__at_end()) 409 return {__code_point, __get_break()}; 410 411 __next_prop_ = __extended_grapheme_custer_property_boundary::__property::__eot; 412 return {__code_point, __code_point_view_.__position()}; 413 } 414 415 private: 416 __code_point_view<_CharT> __code_point_view_; 417 418 char32_t __next_code_point_; 419 __extended_grapheme_custer_property_boundary::__property __next_prop_; 420 421 _LIBCPP_HIDE_FROM_ABI constexpr _Iterator __get_break() { 422 bool __ri_break_allowed = true; 423 bool __has_extened_pictographic = false; 424 while (true) { 425 _Iterator __result = __code_point_view_.__position(); 426 __extended_grapheme_custer_property_boundary::__property __prev = __next_prop_; 427 if (__code_point_view_.__at_end()) { 428 __next_prop_ = __extended_grapheme_custer_property_boundary::__property::__eot; 429 return __result; 430 } 431 __next_code_point_ = __code_point_view_.__consume().__code_point; 432 __next_prop_ = __extended_grapheme_custer_property_boundary::__get_property(__next_code_point_); 433 434 __has_extened_pictographic |= 435 __prev == __extended_grapheme_custer_property_boundary::__property::__Extended_Pictographic; 436 437 if (__at_extended_grapheme_cluster_break(__ri_break_allowed, __has_extened_pictographic, __prev, __next_prop_)) 438 return __result; 439 } 440 } 441 }; 442 443 template <contiguous_iterator _Iterator> 444 __extended_grapheme_cluster_view(_Iterator, _Iterator) -> __extended_grapheme_cluster_view<iter_value_t<_Iterator>>; 445 446 # else // _LIBCPP_HAS_NO_UNICODE 447 448 // For ASCII every character is a "code point". 449 // This makes it easier to write code agnostic of the _LIBCPP_HAS_NO_UNICODE define. 450 template <class _CharT> 451 class __code_point_view { 452 using _Iterator = typename basic_string_view<_CharT>::const_iterator; 453 454 public: 455 _LIBCPP_HIDE_FROM_ABI constexpr explicit __code_point_view(_Iterator __first, _Iterator __last) 456 : __first_(__first), __last_(__last) {} 457 458 _LIBCPP_HIDE_FROM_ABI constexpr bool __at_end() const noexcept { return __first_ == __last_; } 459 _LIBCPP_HIDE_FROM_ABI constexpr _Iterator __position() const noexcept { return __first_; } 460 461 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr __consume_result __consume() noexcept { 462 _LIBCPP_ASSERT_INTERNAL(__first_ != __last_, "can't move beyond the end of input"); 463 return {static_cast<char32_t>(*__first_++)}; 464 } 465 466 private: 467 _Iterator __first_; 468 _Iterator __last_; 469 }; 470 471 # endif // _LIBCPP_HAS_NO_UNICODE 472 473 } // namespace __unicode 474 475 #endif //_LIBCPP_STD_VER >= 20 476 477 _LIBCPP_END_NAMESPACE_STD 478 479 #endif // _LIBCPP___FORMAT_UNICODE_H 480