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 <__config> 15 #include <__format/extended_grapheme_cluster_table.h> 16 #include <__type_traits/make_unsigned.h> 17 #include <__utility/unreachable.h> 18 #include <bit> 19 20 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 21 # pragma GCC system_header 22 #endif 23 24 _LIBCPP_BEGIN_NAMESPACE_STD 25 26 #if _LIBCPP_STD_VER > 17 27 28 namespace __unicode { 29 30 # if _LIBCPP_STD_VER > 20 31 32 /// The result of consuming a code point using P2286' semantics 33 /// 34 /// TODO FMT Combine __consume and __consume_p2286 in one function. 35 struct __consume_p2286_result { 36 // A size of 0 means well formed. This to differenciate between 37 // a valid code point and a code unit that's invalid like 0b11111xxx. 38 int __ill_formed_size; 39 40 // If well formed the consumed code point. 41 // Otherwise the ill-formed code units as unsigned 8-bit values. They are 42 // stored in reverse order, to make it easier to extract the values. 43 char32_t __value; 44 }; 45 46 # endif // _LIBCPP_STD_VER > 20 47 48 # ifndef _LIBCPP_HAS_NO_UNICODE 49 50 /// Implements the grapheme cluster boundary rules 51 /// 52 /// These rules are used to implement format's width estimation as stated in 53 /// [format.string.std]/11 54 /// 55 /// The Standard refers to UAX \#29 for Unicode 12.0.0 56 /// https://www.unicode.org/reports/tr29/#Grapheme_Cluster_Boundary_Rules 57 /// 58 /// The data tables used are 59 /// https://www.unicode.org/Public/UCD/latest/ucd/auxiliary/GraphemeBreakProperty.txt 60 /// https://www.unicode.org/Public/UCD/latest/ucd/emoji/emoji-data.txt 61 /// https://www.unicode.org/Public/UCD/latest/ucd/auxiliary/GraphemeBreakTest.txt (for testing only) 62 63 inline constexpr char32_t __replacement_character = U'\ufffd'; 64 65 _LIBCPP_HIDE_FROM_ABI constexpr bool __is_continuation(const char* __char, int __count) { 66 do { 67 if ((*__char & 0b1000'0000) != 0b1000'0000) 68 return false; 69 --__count; 70 ++__char; 71 } while (__count); 72 return true; 73 } 74 75 /// Helper class to extract a code unit from a Unicode character range. 76 /// 77 /// The stored range is a view. There are multiple specialization for different 78 /// character types. 79 template <class _CharT> 80 class __code_point_view; 81 82 /// UTF-8 specialization. 83 template <> 84 class __code_point_view<char> { 85 public: 86 _LIBCPP_HIDE_FROM_ABI constexpr explicit __code_point_view(const char* __first, const char* __last) 87 : __first_(__first), __last_(__last) {} 88 89 _LIBCPP_HIDE_FROM_ABI constexpr bool __at_end() const noexcept { return __first_ == __last_; } 90 _LIBCPP_HIDE_FROM_ABI constexpr const char* __position() const noexcept { return __first_; } 91 92 _LIBCPP_HIDE_FROM_ABI constexpr char32_t __consume() noexcept { 93 _LIBCPP_ASSERT(__first_ != __last_, "can't move beyond the end of input"); 94 95 // Based on the number of leading 1 bits the number of code units in the 96 // code point can be determined. See 97 // https://en.wikipedia.org/wiki/UTF-8#Encoding 98 switch (_VSTD::countl_one(static_cast<unsigned char>(*__first_))) { 99 case 0: 100 return *__first_++; 101 102 case 2: 103 if (__last_ - __first_ < 2 || !__unicode::__is_continuation(__first_ + 1, 1)) [[unlikely]] 104 break; 105 else { 106 char32_t __value = static_cast<unsigned char>(*__first_++) & 0x1f; 107 __value <<= 6; 108 __value |= static_cast<unsigned char>(*__first_++) & 0x3f; 109 return __value; 110 } 111 112 case 3: 113 if (__last_ - __first_ < 3 || !__unicode::__is_continuation(__first_ + 1, 2)) [[unlikely]] 114 break; 115 else { 116 char32_t __value = static_cast<unsigned char>(*__first_++) & 0x0f; 117 __value <<= 6; 118 __value |= static_cast<unsigned char>(*__first_++) & 0x3f; 119 __value <<= 6; 120 __value |= static_cast<unsigned char>(*__first_++) & 0x3f; 121 return __value; 122 } 123 124 case 4: 125 if (__last_ - __first_ < 4 || !__unicode::__is_continuation(__first_ + 1, 3)) [[unlikely]] 126 break; 127 else { 128 char32_t __value = static_cast<unsigned char>(*__first_++) & 0x07; 129 __value <<= 6; 130 __value |= static_cast<unsigned char>(*__first_++) & 0x3f; 131 __value <<= 6; 132 __value |= static_cast<unsigned char>(*__first_++) & 0x3f; 133 __value <<= 6; 134 __value |= static_cast<unsigned char>(*__first_++) & 0x3f; 135 return __value; 136 } 137 } 138 // An invalid number of leading ones can be garbage or a code unit in the 139 // middle of a code point. By consuming one code unit the parser may get 140 // "in sync" after a few code units. 141 ++__first_; 142 return __replacement_character; 143 } 144 145 # if _LIBCPP_STD_VER > 20 146 _LIBCPP_HIDE_FROM_ABI constexpr __consume_p2286_result __consume_p2286() noexcept { 147 _LIBCPP_ASSERT(__first_ != __last_, "can't move beyond the end of input"); 148 149 // Based on the number of leading 1 bits the number of code units in the 150 // code point can be determined. See 151 // https://en.wikipedia.org/wiki/UTF-8#Encoding 152 switch (std::countl_one(static_cast<unsigned char>(*__first_))) { 153 case 0: 154 return {0, static_cast<unsigned char>(*__first_++)}; 155 156 case 2: 157 if (__last_ - __first_ < 2) [[unlikely]] 158 break; 159 160 if (__unicode::__is_continuation(__first_ + 1, 1)) { 161 char32_t __value = static_cast<unsigned char>(*__first_++) & 0x1f; 162 __value <<= 6; 163 __value |= static_cast<unsigned char>(*__first_++) & 0x3f; 164 return {0, __value}; 165 } 166 break; 167 168 case 3: 169 if (__last_ - __first_ < 3) [[unlikely]] 170 break; 171 172 if (__unicode::__is_continuation(__first_ + 1, 2)) { 173 char32_t __value = static_cast<unsigned char>(*__first_++) & 0x0f; 174 __value <<= 6; 175 __value |= static_cast<unsigned char>(*__first_++) & 0x3f; 176 __value <<= 6; 177 __value |= static_cast<unsigned char>(*__first_++) & 0x3f; 178 return {0, __value}; 179 } 180 break; 181 182 case 4: 183 if (__last_ - __first_ < 4) [[unlikely]] 184 break; 185 186 if (__unicode::__is_continuation(__first_ + 1, 3)) { 187 char32_t __value = static_cast<unsigned char>(*__first_++) & 0x07; 188 __value <<= 6; 189 __value |= static_cast<unsigned char>(*__first_++) & 0x3f; 190 __value <<= 6; 191 __value |= static_cast<unsigned char>(*__first_++) & 0x3f; 192 __value <<= 6; 193 __value |= static_cast<unsigned char>(*__first_++) & 0x3f; 194 195 if (__value > 0x10FFFF) // Outside the valid Unicode range? 196 return {4, __value}; 197 198 return {0, __value}; 199 } 200 break; 201 } 202 // An invalid number of leading ones can be garbage or a code unit in the 203 // middle of a code point. By consuming one code unit the parser may get 204 // "in sync" after a few code units. 205 return {1, static_cast<unsigned char>(*__first_++)}; 206 } 207 # endif // _LIBCPP_STD_VER > 20 208 209 private: 210 const char* __first_; 211 const char* __last_; 212 }; 213 214 # ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS 215 _LIBCPP_HIDE_FROM_ABI constexpr bool __is_surrogate_pair_high(wchar_t __value) { 216 return __value >= 0xd800 && __value <= 0xdbff; 217 } 218 219 _LIBCPP_HIDE_FROM_ABI constexpr bool __is_surrogate_pair_low(wchar_t __value) { 220 return __value >= 0xdc00 && __value <= 0xdfff; 221 } 222 223 /// This specialization depends on the size of wchar_t 224 /// - 2 UTF-16 (for example Windows and AIX) 225 /// - 4 UTF-32 (for example Linux) 226 template <> 227 class __code_point_view<wchar_t> { 228 public: 229 static_assert(sizeof(wchar_t) == 2 || sizeof(wchar_t) == 4, "sizeof(wchar_t) has a not implemented value"); 230 231 _LIBCPP_HIDE_FROM_ABI constexpr explicit __code_point_view(const wchar_t* __first, const wchar_t* __last) 232 : __first_(__first), __last_(__last) {} 233 234 _LIBCPP_HIDE_FROM_ABI constexpr const wchar_t* __position() const noexcept { return __first_; } 235 _LIBCPP_HIDE_FROM_ABI constexpr bool __at_end() const noexcept { return __first_ == __last_; } 236 237 _LIBCPP_HIDE_FROM_ABI constexpr char32_t __consume() noexcept { 238 _LIBCPP_ASSERT(__first_ != __last_, "can't move beyond the end of input"); 239 240 if constexpr (sizeof(wchar_t) == 2) { 241 char32_t __result = *__first_++; 242 // Is the code unit part of a surrogate pair? See 243 // https://en.wikipedia.org/wiki/UTF-16#U+D800_to_U+DFFF 244 if (__result >= 0xd800 && __result <= 0xDfff) { 245 // Malformed Unicode. 246 if (__first_ == __last_) [[unlikely]] 247 return __replacement_character; 248 249 __result -= 0xd800; 250 __result <<= 10; 251 __result += *__first_++ - 0xdc00; 252 __result += 0x10000; 253 } 254 return __result; 255 256 } else if constexpr (sizeof(wchar_t) == 4) { 257 char32_t __result = *__first_++; 258 if (__result > 0x10FFFF) [[unlikely]] 259 return __replacement_character; 260 return __result; 261 } else { 262 __libcpp_unreachable(); 263 } 264 } 265 266 # if _LIBCPP_STD_VER > 20 267 _LIBCPP_HIDE_FROM_ABI constexpr __consume_p2286_result __consume_p2286() noexcept { 268 _LIBCPP_ASSERT(__first_ != __last_, "can't move beyond the end of input"); 269 270 char32_t __result = *__first_++; 271 if constexpr (sizeof(wchar_t) == 2) { 272 // https://en.wikipedia.org/wiki/UTF-16#U+D800_to_U+DFFF 273 if (__is_surrogate_pair_high(__result)) { 274 // Malformed Unicode. 275 if (__first_ == __last_ || !__is_surrogate_pair_low(*(__first_ + 1))) [[unlikely]] 276 return {1, __result}; 277 278 __result -= 0xd800; 279 __result <<= 10; 280 __result += *__first_++ - 0xdc00; 281 __result += 0x10000; 282 } else if (__is_surrogate_pair_low(__result)) 283 // A code point shouldn't start with the low surrogate pair 284 return {1, __result}; 285 } else { 286 if (__result > 0x10FFFF) [[unlikely]] 287 return {1, __result}; 288 } 289 290 return {0, __result}; 291 } 292 # endif // _LIBCPP_STD_VER > 20 293 294 private: 295 const wchar_t* __first_; 296 const wchar_t* __last_; 297 }; 298 # endif // _LIBCPP_HAS_NO_WIDE_CHARACTERS 299 300 _LIBCPP_HIDE_FROM_ABI constexpr bool __at_extended_grapheme_cluster_break( 301 bool& __ri_break_allowed, 302 bool __has_extened_pictographic, 303 __extended_grapheme_custer_property_boundary::__property __prev, 304 __extended_grapheme_custer_property_boundary::__property __next) { 305 using __extended_grapheme_custer_property_boundary::__property; 306 307 __has_extened_pictographic |= __prev == __property::__Extended_Pictographic; 308 309 // https://www.unicode.org/reports/tr29/tr29-39.html#Grapheme_Cluster_Boundary_Rules 310 311 // *** Break at the start and end of text, unless the text is empty. *** 312 313 _LIBCPP_ASSERT(__prev != __property::__sot, "should be handled in the constructor"); // GB1 314 _LIBCPP_ASSERT(__prev != __property::__eot, "should be handled by our caller"); // GB2 315 316 // *** Do not break between a CR and LF. Otherwise, break before and after controls. *** 317 if (__prev == __property::__CR && __next == __property::__LF) // GB3 318 return false; 319 320 if (__prev == __property::__Control || __prev == __property::__CR || __prev == __property::__LF) // GB4 321 return true; 322 323 if (__next == __property::__Control || __next == __property::__CR || __next == __property::__LF) // GB5 324 return true; 325 326 // *** Do not break Hangul syllable sequences. *** 327 if (__prev == __property::__L && 328 (__next == __property::__L || __next == __property::__V || __next == __property::__LV || 329 __next == __property::__LVT)) // GB6 330 return false; 331 332 if ((__prev == __property::__LV || __prev == __property::__V) && 333 (__next == __property::__V || __next == __property::__T)) // GB7 334 return false; 335 336 if ((__prev == __property::__LVT || __prev == __property::__T) && __next == __property::__T) // GB8 337 return false; 338 339 // *** Do not break before extending characters or ZWJ. *** 340 if (__next == __property::__Extend || __next == __property::__ZWJ) 341 return false; // GB9 342 343 // *** Do not break before SpacingMarks, or after Prepend characters. *** 344 if (__next == __property::__SpacingMark) // GB9a 345 return false; 346 347 if (__prev == __property::__Prepend) // GB9b 348 return false; 349 350 // *** Do not break within emoji modifier sequences or emoji zwj sequences. *** 351 352 // GB11 \p{Extended_Pictographic} Extend* ZWJ x \p{Extended_Pictographic} 353 // 354 // Note that several parts of this rule are matched by GB9: Any x (Extend | ZWJ) 355 // - \p{Extended_Pictographic} x Extend 356 // - Extend x Extend 357 // - \p{Extended_Pictographic} x ZWJ 358 // - Extend x ZWJ 359 // 360 // So the only case left to test is 361 // - \p{Extended_Pictographic}' x ZWJ x \p{Extended_Pictographic} 362 // where \p{Extended_Pictographic}' is stored in __has_extened_pictographic 363 if (__has_extened_pictographic && __prev == __property::__ZWJ && __next == __property::__Extended_Pictographic) 364 return false; 365 366 // *** Do not break within emoji flag sequences *** 367 368 // That is, do not break between regional indicator (RI) symbols if there 369 // is an odd number of RI characters before the break point. 370 371 if (__prev == __property::__Regional_Indicator && __next == __property::__Regional_Indicator) { // GB12 + GB13 372 __ri_break_allowed = !__ri_break_allowed; 373 return __ri_break_allowed; 374 } 375 376 // *** Otherwise, break everywhere. *** 377 return true; // GB999 378 } 379 380 /// Helper class to extract an extended grapheme cluster from a Unicode character range. 381 /// 382 /// This function is used to determine the column width of an extended grapheme 383 /// cluster. In order to do that only the first code point is evaluated. 384 /// Therefore only this code point is extracted. 385 template <class _CharT> 386 class __extended_grapheme_cluster_view { 387 public: 388 _LIBCPP_HIDE_FROM_ABI constexpr explicit __extended_grapheme_cluster_view(const _CharT* __first, const _CharT* __last) 389 : __code_point_view_(__first, __last), 390 __next_code_point_(__code_point_view_.__consume()), 391 __next_prop_(__extended_grapheme_custer_property_boundary::__get_property(__next_code_point_)) {} 392 393 struct __cluster { 394 /// The first code point of the extended grapheme cluster. 395 /// 396 /// The first code point is used to estimate the width of the extended 397 /// grapheme cluster. 398 char32_t __code_point_; 399 400 /// Points one beyond the last code unit in the extended grapheme cluster. 401 /// 402 /// It's expected the caller has the start position and thus can determine 403 /// the code unit range of the extended grapheme cluster. 404 const _CharT* __last_; 405 }; 406 407 _LIBCPP_HIDE_FROM_ABI constexpr __cluster __consume() { 408 _LIBCPP_ASSERT( 409 __next_prop_ != __extended_grapheme_custer_property_boundary::__property::__eot, 410 "can't move beyond the end of input"); 411 char32_t __code_point = __next_code_point_; 412 if (!__code_point_view_.__at_end()) 413 return {__code_point, __get_break()}; 414 415 __next_prop_ = __extended_grapheme_custer_property_boundary::__property::__eot; 416 return {__code_point, __code_point_view_.__position()}; 417 } 418 419 private: 420 __code_point_view<_CharT> __code_point_view_; 421 422 char32_t __next_code_point_; 423 __extended_grapheme_custer_property_boundary::__property __next_prop_; 424 425 _LIBCPP_HIDE_FROM_ABI constexpr const _CharT* __get_break() { 426 bool __ri_break_allowed = true; 427 bool __has_extened_pictographic = false; 428 while (true) { 429 const _CharT* __result = __code_point_view_.__position(); 430 __extended_grapheme_custer_property_boundary::__property __prev = __next_prop_; 431 if (__code_point_view_.__at_end()) { 432 __next_prop_ = __extended_grapheme_custer_property_boundary::__property::__eot; 433 return __result; 434 } 435 __next_code_point_ = __code_point_view_.__consume(); 436 __next_prop_ = __extended_grapheme_custer_property_boundary::__get_property(__next_code_point_); 437 438 __has_extened_pictographic |= 439 __prev == __extended_grapheme_custer_property_boundary::__property::__Extended_Pictographic; 440 441 if (__at_extended_grapheme_cluster_break(__ri_break_allowed, __has_extened_pictographic, __prev, __next_prop_)) 442 return __result; 443 } 444 } 445 }; 446 447 template <class _CharT> 448 __extended_grapheme_cluster_view(const _CharT*, const _CharT*) -> __extended_grapheme_cluster_view<_CharT>; 449 450 # else // _LIBCPP_HAS_NO_UNICODE 451 452 // For ASCII every character is a "code point". 453 // This makes it easier to write code agnostic of the _LIBCPP_HAS_NO_UNICODE define. 454 template <class _CharT> 455 class __code_point_view { 456 public: 457 _LIBCPP_HIDE_FROM_ABI constexpr explicit __code_point_view(const _CharT* __first, const _CharT* __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 const _CharT* __position() const noexcept { return __first_; } 462 463 _LIBCPP_HIDE_FROM_ABI constexpr char32_t __consume() noexcept { 464 _LIBCPP_ASSERT(__first_ != __last_, "can't move beyond the end of input"); 465 return *__first_++; 466 } 467 468 # if _LIBCPP_STD_VER > 20 469 _LIBCPP_HIDE_FROM_ABI constexpr __consume_p2286_result __consume_p2286() noexcept { 470 _LIBCPP_ASSERT(__first_ != __last_, "can't move beyond the end of input"); 471 472 return {0, std::make_unsigned_t<_CharT>(*__first_++)}; 473 } 474 # endif // _LIBCPP_STD_VER > 20 475 476 private: 477 const _CharT* __first_; 478 const _CharT* __last_; 479 }; 480 481 # endif // _LIBCPP_HAS_NO_UNICODE 482 483 } // namespace __unicode 484 485 #endif //_LIBCPP_STD_VER > 17 486 487 _LIBCPP_END_NAMESPACE_STD 488 489 #endif // _LIBCPP___FORMAT_UNICODE_H 490