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
__is_continuation(const char * __char,int __count)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:
__code_point_view(const char * __first,const char * __last)86 _LIBCPP_HIDE_FROM_ABI constexpr explicit __code_point_view(const char* __first, const char* __last)
87 : __first_(__first), __last_(__last) {}
88
__at_end()89 _LIBCPP_HIDE_FROM_ABI constexpr bool __at_end() const noexcept { return __first_ == __last_; }
__position()90 _LIBCPP_HIDE_FROM_ABI constexpr const char* __position() const noexcept { return __first_; }
91
__consume()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
__consume_p2286()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
__is_surrogate_pair_high(wchar_t __value)215 _LIBCPP_HIDE_FROM_ABI constexpr bool __is_surrogate_pair_high(wchar_t __value) {
216 return __value >= 0xd800 && __value <= 0xdbff;
217 }
218
__is_surrogate_pair_low(wchar_t __value)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
__code_point_view(const wchar_t * __first,const wchar_t * __last)231 _LIBCPP_HIDE_FROM_ABI constexpr explicit __code_point_view(const wchar_t* __first, const wchar_t* __last)
232 : __first_(__first), __last_(__last) {}
233
__position()234 _LIBCPP_HIDE_FROM_ABI constexpr const wchar_t* __position() const noexcept { return __first_; }
__at_end()235 _LIBCPP_HIDE_FROM_ABI constexpr bool __at_end() const noexcept { return __first_ == __last_; }
236
__consume()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
__consume_p2286()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
__at_extended_grapheme_cluster_break(bool & __ri_break_allowed,bool __has_extened_pictographic,__extended_grapheme_custer_property_boundary::__property __prev,__extended_grapheme_custer_property_boundary::__property __next)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:
__extended_grapheme_cluster_view(const _CharT * __first,const _CharT * __last)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
__consume()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
__get_break()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:
__code_point_view(const _CharT * __first,const _CharT * __last)457 _LIBCPP_HIDE_FROM_ABI constexpr explicit __code_point_view(const _CharT* __first, const _CharT* __last)
458 : __first_(__first), __last_(__last) {}
459
__at_end()460 _LIBCPP_HIDE_FROM_ABI constexpr bool __at_end() const noexcept { return __first_ == __last_; }
__position()461 _LIBCPP_HIDE_FROM_ABI constexpr const _CharT* __position() const noexcept { return __first_; }
462
__consume()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
__consume_p2286()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