Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_text/src/unicode/norm.rs

9.7 KiB, 1 run

created by r1870400018:13906, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Normalisation, following UAX #15.
2//!
3//! The four normalisation forms differ along two axes: whether the decomposition is canonical or
4//! compatibility, and whether the result is left decomposed or recomposed. Each form decomposes
5//! the text, puts the combining marks into canonical order, and, for the composed forms, recombines
6//! what it can.
7//!
8//! ```
9//! use oxedyne_fe2o3_text::unicode::norm::{
10//! self,
11//! Form,
12//! };
13//!
14//! // The same text, spelled two ways.
15//! assert_eq!(norm::nfc("A\u{030A}"), "\u{00C5}");
16//! assert_eq!(norm::nfd("\u{00C5}"), "A\u{030A}");
17//!
18//! // A compatibility form folds away a presentation difference.
19//! assert_eq!(norm::normalise("\u{FB01}", Form::Nfkc), "fi");
20//! ```
21
22use crate::unicode::{
23 lookup,
24 tables::norm::{
25 CANON_KEYS,
26 CANON_OFFS,
27 CANON_POOL,
28 CCC_STARTS,
29 CCC_VALS,
30 COMPAT_KEYS,
31 COMPAT_OFFS,
32 COMPAT_POOL,
33 COMPOSE_FIRST,
34 COMPOSE_SECOND,
35 COMPOSE_VALS,
36 },
37};
38
39use oxedyne_fe2o3_core::prelude::*;
40
41/// The first Hangul syllable.
42const S_BASE: u32 = 0xAC00;
43/// The first Hangul leading jamo.
44const L_BASE: u32 = 0x1100;
45/// The first Hangul vowel jamo.
46const V_BASE: u32 = 0x1161;
47/// One before the first Hangul trailing jamo, which is why a trailing jamo index of zero means
48/// there is none.
49const T_BASE: u32 = 0x11A7;
50/// The number of Hangul leading jamo.
51const L_COUNT: u32 = 19;
52/// The number of Hangul vowel jamo.
53const V_COUNT: u32 = 21;
54/// The number of Hangul trailing jamo, counting the absent one.
55const T_COUNT: u32 = 28;
56/// The number of Hangul syllables per leading jamo.
57const N_COUNT: u32 = V_COUNT * T_COUNT;
58/// The number of Hangul syllables.
59const S_COUNT: u32 = L_COUNT * N_COUNT;
60
61/// A Unicode normalisation form.
62#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
63pub enum Form {
64 /// Canonical decomposition followed by canonical composition.
65 Nfc,
66 /// Canonical decomposition.
67 Nfd,
68 /// Compatibility decomposition followed by canonical composition.
69 Nfkc,
70 /// Compatibility decomposition.
71 Nfkd,
72}
73
74impl Form {
75
76 /// Whether the form decomposes compatibility as well as canonical equivalents.
77 pub fn is_compat(&self) -> bool {
78 matches!(self, Self::Nfkc | Self::Nfkd)
79 }
80
81 /// Whether the form recomposes after decomposing.
82 pub fn is_composed(&self) -> bool {
83 matches!(self, Self::Nfc | Self::Nfkc)
84 }
85}
86
87/// Returns the canonical combining class of `c`.
88pub fn combining_class(c: char) -> u8 {
89 lookup::flags(&CCC_STARTS, &CCC_VALS, c)
90}
91
92/// Returns `s` in the given normalisation form.
93pub fn normalise(s: &str, form: Form) -> String {
94
95 // Text that is entirely ASCII is already in every form, since no ASCII character decomposes,
96 // composes or carries a combining class.
97 if s.is_ascii() {
98 return s.to_string();
99 }
100
101 let mut buf = Vec::with_capacity(s.len());
102 for c in s.chars() {
103 decompose(c, form.is_compat(), &mut buf);
104 }
105 order(&mut buf);
106 if form.is_composed() {
107 buf = compose(&buf);
108 }
109 buf.into_iter().collect()
110}
111
112/// Returns `s` in normalisation form C.
113pub fn nfc(s: &str) -> String {
114 normalise(s, Form::Nfc)
115}
116
117/// Returns `s` in normalisation form D.
118pub fn nfd(s: &str) -> String {
119 normalise(s, Form::Nfd)
120}
121
122/// Returns `s` in normalisation form KC.
123pub fn nfkc(s: &str) -> String {
124 normalise(s, Form::Nfkc)
125}
126
127/// Returns `s` in normalisation form KD.
128pub fn nfkd(s: &str) -> String {
129 normalise(s, Form::Nfkd)
130}
131
132/// Whether `s` is already in the given form.
133pub fn is_normalised(s: &str, form: Form) -> bool {
134 normalise(s, form) == s
135}
136
137/// Whether `a` and `b` are canonically equivalent, that is, whether they are the same text spelled
138/// differently.
139pub fn eq_canonical(a: &str, b: &str) -> bool {
140 nfd(a) == nfd(b)
141}
142
143/// Whether `a` and `b` are compatibility equivalent.
144pub fn eq_compat(a: &str, b: &str) -> bool {
145 nfkd(a) == nfkd(b)
146}
147
148/// Appends the full decomposition of `c` to `out`, recursing until nothing decomposes further.
149fn decompose(c: char, compat: bool, out: &mut Vec<char>) {
150
151 let cp = c as u32;
152
153 // A Hangul syllable decomposes arithmetically rather than by table.
154 if cp >= S_BASE && cp < S_BASE + S_COUNT {
155 let i = cp - S_BASE;
156 let l = L_BASE + i / N_COUNT;
157 let v = V_BASE + (i % N_COUNT) / T_COUNT;
158 let t = T_BASE + i % T_COUNT;
159 push(out, l);
160 push(out, v);
161 if i % T_COUNT != 0 {
162 push(out, t);
163 }
164 return;
165 }
166
167 if compat {
168 if let Some(seq) = mapping(&COMPAT_KEYS, &COMPAT_OFFS, &COMPAT_POOL, c) {
169 for d in seq {
170 decompose(*d, compat, out);
171 }
172 return;
173 }
174 }
175
176 if let Some(seq) = mapping(&CANON_KEYS, &CANON_OFFS, &CANON_POOL, c) {
177 for d in seq {
178 decompose(*d, compat, out);
179 }
180 return;
181 }
182
183 out.push(c);
184}
185
186/// Returns the decomposition of `c` in one of the mapping tables.
187fn mapping<'a>(
188 keys: &[u32],
189 offs: &[u32],
190 pool: &'a [char],
191 c: char,
192)
193 -> Option<&'a [char]>
194{
195 let i = match lookup::find(keys, c) {
196 Some(i) => i,
197 None => return None,
198 };
199 let a = lookup::get(offs, i, 0) as usize;
200 let b = lookup::get(offs, i + 1, 0) as usize;
201 Some(lookup::pool(pool, a, b))
202}
203
204/// Puts the combining marks of `buf` into canonical order, which is a stable sort of each run of
205/// non-starters by combining class.
206fn order(buf: &mut [char]) {
207 let n = buf.len();
208 if n < 2 {
209 return;
210 }
211 // An insertion sort, which is stable, and which touches nothing outside a run of marks because
212 // a starter has class zero and so never moves.
213 for i in 1..n {
214 let c = buf[i];
215 let cc = combining_class(c);
216 if cc == 0 {
217 continue;
218 }
219 let mut j = i;
220 while j > 0 {
221 let prev = combining_class(buf[j - 1]);
222 if prev <= cc {
223 break;
224 }
225 buf[j] = buf[j - 1];
226 j -= 1;
227 }
228 buf[j] = c;
229 }
230}
231
232/// Recombines a decomposed, canonically ordered sequence.
233fn compose(buf: &[char]) -> Vec<char> {
234
235 let mut out: Vec<char> = Vec::with_capacity(buf.len());
236 let mut starter = None; // Index in `out` of the last starter
237 let mut prev_ccc = 0u8; // Class of the character last appended
238
239 for c in buf {
240 let cc = combining_class(*c);
241 if let Some(li) = starter {
242 // The character is blocked from the starter if anything between them has a class that
243 // is zero, or is not lower than its own. The sequence is canonically ordered, so the
244 // character immediately before it carries the highest class of the run.
245 let adjacent = out.len() == li + 1;
246 let blocked = !adjacent && prev_ccc >= cc;
247 if !blocked {
248 if let Some(comp) = primary_composite(lookup::get(&out, li, *c), *c) {
249 if let Some(slot) = out.get_mut(li) {
250 *slot = comp;
251 continue;
252 }
253 }
254 }
255 }
256 if cc == 0 {
257 starter = Some(out.len());
258 }
259 prev_ccc = cc;
260 out.push(*c);
261 }
262
263 out
264}
265
266/// Returns the primary composite of `a` and `b`, if the pair has one.
267fn primary_composite(a: char, b: char) -> Option<char> {
268
269 let (x, y) = (a as u32, b as u32);
270
271 // Hangul composes arithmetically: a leading and a vowel jamo make an LV syllable, and an LV
272 // syllable and a trailing jamo make an LVT syllable.
273 if x >= L_BASE && x < L_BASE + L_COUNT && y >= V_BASE && y < V_BASE + V_COUNT {
274 let li = x - L_BASE;
275 let vi = y - V_BASE;
276 return char::from_u32(S_BASE + (li * V_COUNT + vi) * T_COUNT);
277 }
278 if x >= S_BASE && x < S_BASE + S_COUNT && (x - S_BASE) % T_COUNT == 0
279 && y > T_BASE && y < T_BASE + T_COUNT
280 {
281 return char::from_u32(x + (y - T_BASE));
282 }
283
284 // The remaining composites are a sorted table of pairs.
285 let mut lo = 0usize;
286 let mut hi = COMPOSE_FIRST.len();
287 while lo < hi {
288 let mid = lo + (hi - lo) / 2;
289 let fa = lookup::get(&COMPOSE_FIRST, mid, 0);
290 let fb = lookup::get(&COMPOSE_SECOND, mid, 0);
291 if (fa, fb) < (x, y) {
292 lo = mid + 1;
293 } else if (fa, fb) > (x, y) {
294 hi = mid;
295 } else {
296 return COMPOSE_VALS.get(mid).copied();
297 }
298 }
299
300 None
301}
302
303/// Pushes a code point that a Hangul index has produced, which is always a valid character.
304fn push(out: &mut Vec<char>, cp: u32) {
305 if let Some(c) = char::from_u32(cp) {
306 out.push(c);
307 }
308}
309
310/// Returns an error if a generated normalisation table has lost an invariant the lookups rely on.
311/// The `tables_are_consistent` test calls it.
312pub fn check_tables() -> Outcome<()> {
313
314 if CANON_OFFS.len() != CANON_KEYS.len() + 1 {
315 return Err(err!(
316 "CANON_OFFS has {} entries, expected {} for {} keys.",
317 CANON_OFFS.len(), CANON_KEYS.len() + 1, CANON_KEYS.len(); Bug, Mismatch, Size));
318 }
319 if COMPAT_OFFS.len() != COMPAT_KEYS.len() + 1 {
320 return Err(err!(
321 "COMPAT_OFFS has {} entries, expected {} for {} keys.",
322 COMPAT_OFFS.len(), COMPAT_KEYS.len() + 1, COMPAT_KEYS.len(); Bug, Mismatch, Size));
323 }
324 if lookup::get(&CANON_OFFS, CANON_KEYS.len(), 0) as usize != CANON_POOL.len() {
325 return Err(err!("The last CANON_OFFS entry does not end the pool."; Bug, Mismatch));
326 }
327 if lookup::get(&COMPAT_OFFS, COMPAT_KEYS.len(), 0) as usize != COMPAT_POOL.len() {
328 return Err(err!("The last COMPAT_OFFS entry does not end the pool."; Bug, Mismatch));
329 }
330 if COMPOSE_FIRST.len() != COMPOSE_SECOND.len() || COMPOSE_FIRST.len() != COMPOSE_VALS.len() {
331 return Err(err!(
332 "The composition tables are {}, {} and {} long, and must agree.",
333 COMPOSE_FIRST.len(), COMPOSE_SECOND.len(), COMPOSE_VALS.len(); Bug, Mismatch, Size));
334 }
335 for i in 1..COMPOSE_FIRST.len() {
336 let a = (lookup::get(&COMPOSE_FIRST, i - 1, 0), lookup::get(&COMPOSE_SECOND, i - 1, 0));
337 let b = (lookup::get(&COMPOSE_FIRST, i, 0), lookup::get(&COMPOSE_SECOND, i, 0));
338 if a >= b {
339 return Err(err!(
340 "The composition table is not sorted at entry {}.", i; Bug, Order));
341 }
342 }
343 for i in 1..CCC_STARTS.len() {
344 if lookup::get(&CCC_STARTS, i - 1, 0) >= lookup::get(&CCC_STARTS, i, 0) {
345 return Err(err!(
346 "The combining class table is not sorted at entry {}.", i; Bug, Order));
347 }
348 }
349
350 // Every partition table must begin at U+0000, or a lookup below its first run start would fall
351 // off the front.
352 if lookup::get(&CCC_STARTS, 0, 1) != 0 {
353 return Err(err!("The combining class table does not begin at U+0000."; Bug, Invalid));
354 }
355
356 Ok(())
357}