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 <__utility/unreachable.h>
17 #include <bit>
18 
19 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
20 #  pragma GCC system_header
21 #endif
22 
23 _LIBCPP_BEGIN_NAMESPACE_STD
24 
25 #if _LIBCPP_STD_VER > 17
26 
27 #  ifndef _LIBCPP_HAS_NO_UNICODE
28 
29 /// Implements the grapheme cluster boundary rules
30 ///
31 /// These rules are used to implement format's width estimation as stated in
32 /// [format.string.std]/11
33 ///
34 /// The Standard refers to UAX \#29 for Unicode 12.0.0
35 /// https://www.unicode.org/reports/tr29/#Grapheme_Cluster_Boundary_Rules
36 ///
37 /// The data tables used are
38 /// https://www.unicode.org/Public/UCD/latest/ucd/auxiliary/GraphemeBreakProperty.txt
39 /// https://www.unicode.org/Public/UCD/latest/ucd/emoji/emoji-data.txt
40 /// https://www.unicode.org/Public/UCD/latest/ucd/auxiliary/GraphemeBreakTest.txt (for testing only)
41 
42 namespace __unicode {
43 
44 inline constexpr char32_t __replacement_character = U'\ufffd';
45 
__is_continuation(const char * __char,int __count)46 _LIBCPP_HIDE_FROM_ABI constexpr bool __is_continuation(const char* __char, int __count) {
47   do {
48     if ((*__char & 0b1000'0000) != 0b1000'0000)
49       return false;
50     --__count;
51     ++__char;
52   } while (__count);
53   return true;
54 }
55 
56 /// Helper class to extract a code unit from a Unicode character range.
57 ///
58 /// The stored range is a view. There are multiple specialization for different
59 /// character types.
60 template <class _CharT>
61 class __code_point_view;
62 
63 /// UTF-8 specialization.
64 template <>
65 class __code_point_view<char> {
66 public:
__code_point_view(const char * __first,const char * __last)67   _LIBCPP_HIDE_FROM_ABI constexpr explicit __code_point_view(const char* __first, const char* __last)
68       : __first_(__first), __last_(__last) {}
69 
__at_end()70   _LIBCPP_HIDE_FROM_ABI constexpr bool __at_end() const noexcept { return __first_ == __last_; }
__position()71   _LIBCPP_HIDE_FROM_ABI constexpr const char* __position() const noexcept { return __first_; }
72 
__consume()73   _LIBCPP_HIDE_FROM_ABI constexpr char32_t __consume() noexcept {
74     _LIBCPP_ASSERT(__first_ != __last_, "can't move beyond the end of input");
75 
76     // Based on the number of leading 1 bits the number of code units in the
77     // code point can be determined. See
78     // https://en.wikipedia.org/wiki/UTF-8#Encoding
79     switch (_VSTD::countl_one(static_cast<unsigned char>(*__first_))) {
80     case 0:
81       return *__first_++;
82 
83     case 2:
84       if (__last_ - __first_ < 2 || !__unicode::__is_continuation(__first_ + 1, 1)) [[unlikely]]
85         break;
86       else {
87         char32_t __value = static_cast<unsigned char>(*__first_++) & 0x1f;
88         __value <<= 6;
89         __value |= static_cast<unsigned char>(*__first_++) & 0x3f;
90         return __value;
91       }
92 
93     case 3:
94       if (__last_ - __first_ < 3 || !__unicode::__is_continuation(__first_ + 1, 2)) [[unlikely]]
95         break;
96       else {
97         char32_t __value = static_cast<unsigned char>(*__first_++) & 0x0f;
98         __value <<= 6;
99         __value |= static_cast<unsigned char>(*__first_++) & 0x3f;
100         __value <<= 6;
101         __value |= static_cast<unsigned char>(*__first_++) & 0x3f;
102         return __value;
103       }
104 
105     case 4:
106       if (__last_ - __first_ < 4 || !__unicode::__is_continuation(__first_ + 1, 3)) [[unlikely]]
107         break;
108       else {
109         char32_t __value = static_cast<unsigned char>(*__first_++) & 0x07;
110         __value <<= 6;
111         __value |= static_cast<unsigned char>(*__first_++) & 0x3f;
112         __value <<= 6;
113         __value |= static_cast<unsigned char>(*__first_++) & 0x3f;
114         __value <<= 6;
115         __value |= static_cast<unsigned char>(*__first_++) & 0x3f;
116         return __value;
117       }
118     }
119     // An invalid number of leading ones can be garbage or a code unit in the
120     // middle of a code point. By consuming one code unit the parser may get
121     // "in sync" after a few code units.
122     ++__first_;
123     return __replacement_character;
124   }
125 
126 private:
127   const char* __first_;
128   const char* __last_;
129 };
130 
131 #    ifndef TEST_HAS_NO_WIDE_CHARACTERS
132 /// This specialization depends on the size of wchar_t
133 /// - 2 UTF-16 (for example Windows and AIX)
134 /// - 4 UTF-32 (for example Linux)
135 template <>
136 class __code_point_view<wchar_t> {
137 public:
__code_point_view(const wchar_t * __first,const wchar_t * __last)138   _LIBCPP_HIDE_FROM_ABI constexpr explicit __code_point_view(const wchar_t* __first, const wchar_t* __last)
139       : __first_(__first), __last_(__last) {}
140 
__position()141   _LIBCPP_HIDE_FROM_ABI constexpr const wchar_t* __position() const noexcept { return __first_; }
__at_end()142   _LIBCPP_HIDE_FROM_ABI constexpr bool __at_end() const noexcept { return __first_ == __last_; }
143 
__consume()144   _LIBCPP_HIDE_FROM_ABI constexpr char32_t __consume() noexcept {
145     _LIBCPP_ASSERT(__first_ != __last_, "can't move beyond the end of input");
146 
147     if constexpr (sizeof(wchar_t) == 2) {
148       char32_t __result = *__first_++;
149       // Is the code unit part of a surrogate pair? See
150       // https://en.wikipedia.org/wiki/UTF-16#U+D800_to_U+DFFF
151       if (__result >= 0xd800 && __result <= 0xDfff) {
152         // Malformed Unicode.
153         if (__first_ == __last_) [[unlikely]]
154           return __replacement_character;
155 
156         __result -= 0xd800;
157         __result <<= 10;
158         __result += *__first_++ - 0xdc00;
159         __result += 0x10000;
160       }
161       return __result;
162 
163     } else if constexpr (sizeof(wchar_t) == 4) {
164       char32_t __result = *__first_++;
165       if (__result > 0x10FFFF) [[unlikely]]
166         return __replacement_character;
167       return __result;
168     } else {
169       // TODO FMT P2593R0 Use static_assert(false, "sizeof(wchar_t) has a not implemented value");
170       _LIBCPP_ASSERT(sizeof(wchar_t) == 0, "sizeof(wchar_t) has a not implemented value");
171       __libcpp_unreachable();
172     }
173   }
174 
175 private:
176   const wchar_t* __first_;
177   const wchar_t* __last_;
178 };
179 #    endif
180 
__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)181 _LIBCPP_HIDE_FROM_ABI constexpr bool __at_extended_grapheme_cluster_break(
182     bool& __ri_break_allowed,
183     bool __has_extened_pictographic,
184     __extended_grapheme_custer_property_boundary::__property __prev,
185     __extended_grapheme_custer_property_boundary::__property __next) {
186   using __extended_grapheme_custer_property_boundary::__property;
187 
188   __has_extened_pictographic |= __prev == __property::__Extended_Pictographic;
189 
190   // https://www.unicode.org/reports/tr29/tr29-39.html#Grapheme_Cluster_Boundary_Rules
191 
192   // *** Break at the start and end of text, unless the text is empty. ***
193 
194   _LIBCPP_ASSERT(__prev != __property::__sot, "should be handled in the constructor"); // GB1
195   _LIBCPP_ASSERT(__prev != __property::__eot, "should be handled by our caller");      // GB2
196 
197   // *** Do not break between a CR and LF. Otherwise, break before and after controls. ***
198   if (__prev == __property::__CR && __next == __property::__LF) // GB3
199     return false;
200 
201   if (__prev == __property::__Control || __prev == __property::__CR || __prev == __property::__LF) // GB4
202     return true;
203 
204   if (__next == __property::__Control || __next == __property::__CR || __next == __property::__LF) // GB5
205     return true;
206 
207   // *** Do not break Hangul syllable sequences. ***
208   if (__prev == __property::__L &&
209       (__next == __property::__L || __next == __property::__V || __next == __property::__LV ||
210        __next == __property::__LVT)) // GB6
211     return false;
212 
213   if ((__prev == __property::__LV || __prev == __property::__V) &&
214       (__next == __property::__V || __next == __property::__T)) // GB7
215     return false;
216 
217   if ((__prev == __property::__LVT || __prev == __property::__T) && __next == __property::__T) // GB8
218     return false;
219 
220   // *** Do not break before extending characters or ZWJ. ***
221   if (__next == __property::__Extend || __next == __property::__ZWJ)
222     return false; // GB9
223 
224   // *** Do not break before SpacingMarks, or after Prepend characters. ***
225   if (__next == __property::__SpacingMark) // GB9a
226     return false;
227 
228   if (__prev == __property::__Prepend) // GB9b
229     return false;
230 
231   // *** Do not break within emoji modifier sequences or emoji zwj sequences. ***
232 
233   // GB11 \p{Extended_Pictographic} Extend* ZWJ x \p{Extended_Pictographic}
234   //
235   // Note that several parts of this rule are matched by GB9: Any x (Extend | ZWJ)
236   // - \p{Extended_Pictographic} x Extend
237   // - Extend x Extend
238   // - \p{Extended_Pictographic} x ZWJ
239   // - Extend x ZWJ
240   //
241   // So the only case left to test is
242   // - \p{Extended_Pictographic}' x ZWJ x \p{Extended_Pictographic}
243   //   where  \p{Extended_Pictographic}' is stored in __has_extened_pictographic
244   if (__has_extened_pictographic && __prev == __property::__ZWJ && __next == __property::__Extended_Pictographic)
245     return false;
246 
247   // *** Do not break within emoji flag sequences ***
248 
249   // That is, do not break between regional indicator (RI) symbols if there
250   // is an odd number of RI characters before the break point.
251 
252   if (__prev == __property::__Regional_Indicator && __next == __property::__Regional_Indicator) { // GB12 + GB13
253     __ri_break_allowed = !__ri_break_allowed;
254     if (__ri_break_allowed)
255       return true;
256 
257     return false;
258   }
259 
260   // *** Otherwise, break everywhere. ***
261   return true; // GB999
262 }
263 
264 /// Helper class to extract an extended grapheme cluster from a Unicode character range.
265 ///
266 /// This function is used to determine the column width of an extended grapheme
267 /// cluster. In order to do that only the first code point is evaluated.
268 /// Therefore only this code point is extracted.
269 template <class _CharT>
270 class __extended_grapheme_cluster_view {
271 public:
__extended_grapheme_cluster_view(const _CharT * __first,const _CharT * __last)272   _LIBCPP_HIDE_FROM_ABI constexpr explicit __extended_grapheme_cluster_view(const _CharT* __first, const _CharT* __last)
273       : __code_point_view_(__first, __last),
274         __next_code_point_(__code_point_view_.__consume()),
275         __next_prop_(__extended_grapheme_custer_property_boundary::__get_property(__next_code_point_)) {}
276 
277   struct __cluster {
278     /// The first code point of the extended grapheme cluster.
279     ///
280     /// The first code point is used to estimate the width of the extended
281     /// grapheme cluster.
282     char32_t __code_point_;
283 
284     /// Points one beyond the last code unit in the extended grapheme cluster.
285     ///
286     /// It's expected the caller has the start position and thus can determine
287     /// the code unit range of the extended grapheme cluster.
288     const _CharT* __last_;
289   };
290 
__consume()291   _LIBCPP_HIDE_FROM_ABI constexpr __cluster __consume() {
292     _LIBCPP_ASSERT(
293         __next_prop_ != __extended_grapheme_custer_property_boundary::__property::__eot,
294         "can't move beyond the end of input");
295     char32_t __code_point = __next_code_point_;
296     if (!__code_point_view_.__at_end())
297       return {__code_point, __get_break()};
298 
299     __next_prop_ = __extended_grapheme_custer_property_boundary::__property::__eot;
300     return {__code_point, __code_point_view_.__position()};
301   }
302 
303 private:
304   __code_point_view<_CharT> __code_point_view_;
305 
306   char32_t __next_code_point_;
307   __extended_grapheme_custer_property_boundary::__property __next_prop_;
308 
__get_break()309   _LIBCPP_HIDE_FROM_ABI constexpr const _CharT* __get_break() {
310     bool __ri_break_allowed         = true;
311     bool __has_extened_pictographic = false;
312     while (true) {
313       const _CharT* __result                                          = __code_point_view_.__position();
314       __extended_grapheme_custer_property_boundary::__property __prev = __next_prop_;
315       if (__code_point_view_.__at_end()) {
316         __next_prop_ = __extended_grapheme_custer_property_boundary::__property::__eot;
317         return __result;
318       }
319       __next_code_point_ = __code_point_view_.__consume();
320       __next_prop_       = __extended_grapheme_custer_property_boundary::__get_property(__next_code_point_);
321 
322       __has_extened_pictographic |=
323           __prev == __extended_grapheme_custer_property_boundary::__property::__Extended_Pictographic;
324 
325       if (__at_extended_grapheme_cluster_break(__ri_break_allowed, __has_extened_pictographic, __prev, __next_prop_))
326         return __result;
327     }
328   }
329 };
330 
331 } // namespace __unicode
332 
333 #  endif //  _LIBCPP_HAS_NO_UNICODE
334 
335 #endif //_LIBCPP_STD_VER > 17
336 
337 _LIBCPP_END_NAMESPACE_STD
338 
339 #endif // _LIBCPP___FORMAT_UNICODE_H
340