Normalize.cpp 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316
  1. /*
  2. * Copyright (c) 2022, mat
  3. *
  4. * SPDX-License-Identifier: BSD-2-Clause
  5. */
  6. #include <AK/Find.h>
  7. #include <AK/QuickSort.h>
  8. #include <AK/Utf8View.h>
  9. #include <AK/Vector.h>
  10. #include <LibUnicode/CharacterTypes.h>
  11. #include <LibUnicode/Normalize.h>
  12. #if ENABLE_UNICODE_DATA
  13. # include <LibUnicode/UnicodeData.h>
  14. #else
  15. struct Unicode::CodePointDecomposition { };
  16. #endif
  17. namespace Unicode {
  18. Optional<CodePointDecomposition const> __attribute__((weak)) code_point_decomposition(u32) { return {}; }
  19. Optional<CodePointDecomposition const> __attribute__((weak)) code_point_decomposition_by_index(size_t) { return {}; }
  20. NormalizationForm normalization_form_from_string(StringView form)
  21. {
  22. if (form == "NFD"sv)
  23. return NormalizationForm::NFD;
  24. if (form == "NFC"sv)
  25. return NormalizationForm::NFC;
  26. if (form == "NFKD"sv)
  27. return NormalizationForm::NFKD;
  28. if (form == "NFKC"sv)
  29. return NormalizationForm::NFKC;
  30. VERIFY_NOT_REACHED();
  31. }
  32. StringView normalization_form_to_string(NormalizationForm form)
  33. {
  34. switch (form) {
  35. case NormalizationForm::NFD:
  36. return "NFD"sv;
  37. case NormalizationForm::NFC:
  38. return "NFC"sv;
  39. case NormalizationForm::NFKD:
  40. return "NFKD"sv;
  41. case NormalizationForm::NFKC:
  42. return "NFKC"sv;
  43. }
  44. VERIFY_NOT_REACHED();
  45. }
  46. ALWAYS_INLINE static bool is_starter(u32 code_point)
  47. {
  48. return Unicode::canonical_combining_class(code_point) == 0;
  49. }
  50. // From https://www.unicode.org/versions/Unicode15.0.0/ch03.pdf#G56669
  51. static constexpr u32 HANGUL_SYLLABLE_BASE = 0xAC00;
  52. static constexpr u32 HANGUL_LEADING_BASE = 0x1100;
  53. static constexpr u32 HANGUL_VOWEL_BASE = 0x1161;
  54. static constexpr u32 HANGUL_TRAILING_BASE = 0x11A7;
  55. static constexpr u32 HANGUL_LEADING_COUNT = 19;
  56. static constexpr u32 HANGUL_VOWEL_COUNT = 21;
  57. static constexpr u32 HANGUL_TRAILING_COUNT = 28;
  58. // NCount in the standard.
  59. static constexpr u32 HANGUL_BLOCK_COUNT = HANGUL_VOWEL_COUNT * HANGUL_TRAILING_COUNT;
  60. static constexpr u32 HANGUL_SYLLABLE_COUNT = HANGUL_LEADING_COUNT * HANGUL_BLOCK_COUNT;
  61. ALWAYS_INLINE static bool is_hangul_code_point(u32 code_point)
  62. {
  63. return code_point >= HANGUL_SYLLABLE_BASE && code_point < HANGUL_SYLLABLE_BASE + HANGUL_SYLLABLE_COUNT;
  64. }
  65. ALWAYS_INLINE static bool is_hangul_leading(u32 code_point)
  66. {
  67. return code_point >= HANGUL_LEADING_BASE && code_point < HANGUL_LEADING_BASE + HANGUL_LEADING_COUNT;
  68. }
  69. ALWAYS_INLINE static bool is_hangul_vowel(u32 code_point)
  70. {
  71. return code_point >= HANGUL_VOWEL_BASE && code_point < HANGUL_VOWEL_BASE + HANGUL_VOWEL_COUNT;
  72. }
  73. ALWAYS_INLINE static bool is_hangul_trailing(u32 code_point)
  74. {
  75. return code_point >= HANGUL_TRAILING_BASE && code_point < HANGUL_TRAILING_BASE + HANGUL_TRAILING_COUNT;
  76. }
  77. // https://www.unicode.org/versions/Unicode15.0.0/ch03.pdf#G56669
  78. static ErrorOr<void> decompose_hangul_code_point(u32 code_point, Vector<u32>& code_points_output)
  79. {
  80. auto const index = code_point - HANGUL_SYLLABLE_BASE;
  81. auto const leading_index = index / HANGUL_BLOCK_COUNT;
  82. auto const vowel_index = (index % HANGUL_BLOCK_COUNT) / HANGUL_TRAILING_COUNT;
  83. auto const trailing_index = index % HANGUL_TRAILING_COUNT;
  84. auto const leading_part = HANGUL_LEADING_BASE + leading_index;
  85. auto const vowel_part = HANGUL_VOWEL_BASE + vowel_index;
  86. auto const trailing_part = HANGUL_TRAILING_BASE + trailing_index;
  87. TRY(code_points_output.try_append(leading_part));
  88. TRY(code_points_output.try_append(vowel_part));
  89. if (trailing_index != 0)
  90. TRY(code_points_output.try_append(trailing_part));
  91. return {};
  92. }
  93. // L, V and LV, T Hangul Syllable Composition
  94. // https://www.unicode.org/versions/Unicode15.0.0/ch03.pdf#G59688
  95. static u32 combine_hangul_code_points(u32 a, u32 b)
  96. {
  97. if (is_hangul_leading(a) && is_hangul_vowel(b)) {
  98. auto const leading_index = a - HANGUL_LEADING_BASE;
  99. auto const vowel_index = b - HANGUL_VOWEL_BASE;
  100. auto const leading_vowel_index = leading_index * HANGUL_BLOCK_COUNT + vowel_index * HANGUL_TRAILING_COUNT;
  101. return HANGUL_SYLLABLE_BASE + leading_vowel_index;
  102. }
  103. // LV characters are the first in each "T block", so use this check to avoid combining LVT with T.
  104. if (is_hangul_code_point(a) && (a - HANGUL_SYLLABLE_BASE) % HANGUL_TRAILING_COUNT == 0 && is_hangul_trailing(b)) {
  105. return a + b - HANGUL_TRAILING_BASE;
  106. }
  107. return 0;
  108. }
  109. static u32 combine_code_points([[maybe_unused]] u32 a, [[maybe_unused]] u32 b)
  110. {
  111. #if ENABLE_UNICODE_DATA
  112. Array<u32, 2> const points { a, b };
  113. // FIXME: Do something better than linear search to find reverse mappings.
  114. for (size_t index = 0;; ++index) {
  115. auto mapping_maybe = Unicode::code_point_decomposition_by_index(index);
  116. if (!mapping_maybe.has_value())
  117. break;
  118. auto& mapping = mapping_maybe.value();
  119. if (mapping.tag == CompatibilityFormattingTag::Canonical && mapping.decomposition == points) {
  120. if (code_point_has_property(mapping.code_point, Property::Full_Composition_Exclusion))
  121. continue;
  122. return mapping.code_point;
  123. }
  124. }
  125. #endif
  126. return 0;
  127. }
  128. enum class UseCompatibility {
  129. Yes,
  130. No
  131. };
  132. static ErrorOr<void> decompose_code_point(u32 code_point, Vector<u32>& code_points_output, [[maybe_unused]] UseCompatibility use_compatibility)
  133. {
  134. if (is_hangul_code_point(code_point))
  135. return decompose_hangul_code_point(code_point, code_points_output);
  136. #if ENABLE_UNICODE_DATA
  137. auto const mapping = Unicode::code_point_decomposition(code_point);
  138. if (mapping.has_value() && (mapping->tag == CompatibilityFormattingTag::Canonical || use_compatibility == UseCompatibility::Yes)) {
  139. for (auto code_point : mapping->decomposition) {
  140. TRY(decompose_code_point(code_point, code_points_output, use_compatibility));
  141. }
  142. } else {
  143. TRY(code_points_output.try_append(code_point));
  144. }
  145. #endif
  146. return {};
  147. }
  148. // This can be any sorting algorithm that maintains order (like std::stable_sort),
  149. // however bubble sort is easier to implement, so go with it (for now).
  150. template<typename T, typename LessThan>
  151. void bubble_sort(Span<T> span, LessThan less_than)
  152. {
  153. for (size_t i = 0; i < span.size() - 1; ++i) {
  154. for (size_t j = 0; j < span.size() - 1 - i; ++j) {
  155. if (!less_than(span[j], span[j + 1]))
  156. swap(span[j], span[j + 1]);
  157. }
  158. }
  159. }
  160. // The Canonical Ordering Algorithm, as specified in Version 15.0.0 of the Unicode Standard.
  161. // See Section 3.11, D109; and UAX #15 https://unicode.org/reports/tr15
  162. // https://www.unicode.org/versions/Unicode15.0.0/ch03.pdf#G49591
  163. static void canonical_ordering_algorithm(Span<u32> code_points)
  164. {
  165. for (size_t i = 0; i < code_points.size(); ++i) {
  166. if (!is_starter(code_points[i])) {
  167. auto starter = find_if(code_points.begin() + i, code_points.end(), is_starter);
  168. auto const span_size = static_cast<size_t>(starter - (code_points.begin() + i));
  169. // Nothing to reorder, so continue.
  170. if (span_size <= 1)
  171. continue;
  172. Span<u32> const span { code_points.data() + i, span_size };
  173. bubble_sort(span, [](u32 a, u32 b) {
  174. // Use <= to keep ordering.
  175. return Unicode::canonical_combining_class(a) <= Unicode::canonical_combining_class(b);
  176. });
  177. // Skip over span we just sorted.
  178. i += span_size - 1;
  179. }
  180. }
  181. }
  182. // See Section 3.11, D115 of Version 15.0.0 of the Unicode Standard.
  183. static bool is_blocked(Span<u32> code_points, size_t a, size_t c)
  184. {
  185. if (!is_starter(code_points[a]) || a == c - 1)
  186. return false;
  187. auto const c_combining_class = Unicode::canonical_combining_class(code_points[c]);
  188. auto const b_combining_class = Unicode::canonical_combining_class(code_points[c - 1]);
  189. return b_combining_class == 0 || b_combining_class >= c_combining_class;
  190. }
  191. // The Canonical Composition Algorithm, as specified in Version 15.0.0 of the Unicode Standard.
  192. // See Section 3.11, D117; and UAX #15 https://unicode.org/reports/tr15
  193. // https://www.unicode.org/versions/Unicode15.0.0/ch03.pdf#G50628
  194. static void canonical_composition_algorithm(Vector<u32>& code_points)
  195. {
  196. for (size_t i = 1; i < code_points.size(); ++i) {
  197. auto const current_character = code_points[i];
  198. // R1. Seek back (left) to find the last Starter L preceding C in the character sequence
  199. for (ssize_t j = i - 1; j >= 0; --j) {
  200. if (!is_starter(code_points[j]))
  201. continue;
  202. // R2. If there is such an L, and C is not blocked from L,
  203. // and there exists a Primary Composite P which is canonically equivalent to <L, C>,
  204. // then replace L by P in the sequence and delete C from the sequence.
  205. if (is_blocked(code_points.span(), j, i))
  206. continue;
  207. auto composite = combine_hangul_code_points(code_points[j], current_character);
  208. if (composite == 0)
  209. composite = combine_code_points(code_points[j], current_character);
  210. if (composite != 0) {
  211. code_points[j] = composite;
  212. code_points.remove(i);
  213. --i;
  214. break;
  215. }
  216. }
  217. }
  218. }
  219. static ErrorOr<Vector<u32>> normalize_nfd(Utf8View string)
  220. {
  221. Vector<u32> result;
  222. for (auto const code_point : string)
  223. TRY(decompose_code_point(code_point, result, UseCompatibility::No));
  224. canonical_ordering_algorithm(result);
  225. return result;
  226. }
  227. static ErrorOr<Vector<u32>> normalize_nfc(Utf8View string)
  228. {
  229. auto result = TRY(normalize_nfd(string));
  230. canonical_composition_algorithm(result);
  231. return result;
  232. }
  233. static ErrorOr<Vector<u32>> normalize_nfkd(Utf8View string)
  234. {
  235. Vector<u32> result;
  236. for (auto const code_point : string)
  237. TRY(decompose_code_point(code_point, result, UseCompatibility::Yes));
  238. canonical_ordering_algorithm(result);
  239. return result;
  240. }
  241. static ErrorOr<Vector<u32>> normalize_nfkc(Utf8View string)
  242. {
  243. auto result = TRY(normalize_nfkd(string));
  244. canonical_composition_algorithm(result);
  245. return result;
  246. }
  247. static ErrorOr<Vector<u32>> normalize_implementation(Utf8View string, NormalizationForm form)
  248. {
  249. switch (form) {
  250. case NormalizationForm::NFD:
  251. return normalize_nfd(string);
  252. case NormalizationForm::NFC:
  253. return normalize_nfc(string);
  254. case NormalizationForm::NFKD:
  255. return normalize_nfkd(string);
  256. case NormalizationForm::NFKC:
  257. return normalize_nfkc(string);
  258. }
  259. VERIFY_NOT_REACHED();
  260. }
  261. ErrorOr<DeprecatedString> normalize(StringView string, NormalizationForm form)
  262. {
  263. auto const code_points = TRY(normalize_implementation(Utf8View { string }, form));
  264. StringBuilder builder;
  265. for (auto code_point : code_points)
  266. TRY(builder.try_append_code_point(code_point));
  267. return builder.to_deprecated_string();
  268. }
  269. }