]>
Commit | Line | Data |
---|---|---|
15c0b25d AP |
1 | // Copyright 2011 The Go Authors. All rights reserved. |
2 | // Use of this source code is governed by a BSD-style | |
3 | // license that can be found in the LICENSE file. | |
4 | ||
5 | package norm | |
6 | ||
7 | import "unicode/utf8" | |
8 | ||
9 | const ( | |
10 | maxNonStarters = 30 | |
11 | // The maximum number of characters needed for a buffer is | |
12 | // maxNonStarters + 1 for the starter + 1 for the GCJ | |
13 | maxBufferSize = maxNonStarters + 2 | |
14 | maxNFCExpansion = 3 // NFC(0x1D160) | |
15 | maxNFKCExpansion = 18 // NFKC(0xFDFA) | |
16 | ||
17 | maxByteBufferSize = utf8.UTFMax * maxBufferSize // 128 | |
18 | ) | |
19 | ||
20 | // ssState is used for reporting the segment state after inserting a rune. | |
21 | // It is returned by streamSafe.next. | |
22 | type ssState int | |
23 | ||
24 | const ( | |
25 | // Indicates a rune was successfully added to the segment. | |
26 | ssSuccess ssState = iota | |
27 | // Indicates a rune starts a new segment and should not be added. | |
28 | ssStarter | |
29 | // Indicates a rune caused a segment overflow and a CGJ should be inserted. | |
30 | ssOverflow | |
31 | ) | |
32 | ||
33 | // streamSafe implements the policy of when a CGJ should be inserted. | |
34 | type streamSafe uint8 | |
35 | ||
36 | // first inserts the first rune of a segment. It is a faster version of next if | |
37 | // it is known p represents the first rune in a segment. | |
38 | func (ss *streamSafe) first(p Properties) { | |
39 | *ss = streamSafe(p.nTrailingNonStarters()) | |
40 | } | |
41 | ||
42 | // insert returns a ssState value to indicate whether a rune represented by p | |
43 | // can be inserted. | |
44 | func (ss *streamSafe) next(p Properties) ssState { | |
45 | if *ss > maxNonStarters { | |
46 | panic("streamSafe was not reset") | |
47 | } | |
48 | n := p.nLeadingNonStarters() | |
49 | if *ss += streamSafe(n); *ss > maxNonStarters { | |
50 | *ss = 0 | |
51 | return ssOverflow | |
52 | } | |
53 | // The Stream-Safe Text Processing prescribes that the counting can stop | |
54 | // as soon as a starter is encountered. However, there are some starters, | |
55 | // like Jamo V and T, that can combine with other runes, leaving their | |
56 | // successive non-starters appended to the previous, possibly causing an | |
57 | // overflow. We will therefore consider any rune with a non-zero nLead to | |
58 | // be a non-starter. Note that it always hold that if nLead > 0 then | |
59 | // nLead == nTrail. | |
60 | if n == 0 { | |
61 | *ss = streamSafe(p.nTrailingNonStarters()) | |
62 | return ssStarter | |
63 | } | |
64 | return ssSuccess | |
65 | } | |
66 | ||
67 | // backwards is used for checking for overflow and segment starts | |
68 | // when traversing a string backwards. Users do not need to call first | |
69 | // for the first rune. The state of the streamSafe retains the count of | |
70 | // the non-starters loaded. | |
71 | func (ss *streamSafe) backwards(p Properties) ssState { | |
72 | if *ss > maxNonStarters { | |
73 | panic("streamSafe was not reset") | |
74 | } | |
75 | c := *ss + streamSafe(p.nTrailingNonStarters()) | |
76 | if c > maxNonStarters { | |
77 | return ssOverflow | |
78 | } | |
79 | *ss = c | |
80 | if p.nLeadingNonStarters() == 0 { | |
81 | return ssStarter | |
82 | } | |
83 | return ssSuccess | |
84 | } | |
85 | ||
86 | func (ss streamSafe) isMax() bool { | |
87 | return ss == maxNonStarters | |
88 | } | |
89 | ||
90 | // GraphemeJoiner is inserted after maxNonStarters non-starter runes. | |
91 | const GraphemeJoiner = "\u034F" | |
92 | ||
93 | // reorderBuffer is used to normalize a single segment. Characters inserted with | |
94 | // insert are decomposed and reordered based on CCC. The compose method can | |
95 | // be used to recombine characters. Note that the byte buffer does not hold | |
96 | // the UTF-8 characters in order. Only the rune array is maintained in sorted | |
97 | // order. flush writes the resulting segment to a byte array. | |
98 | type reorderBuffer struct { | |
99 | rune [maxBufferSize]Properties // Per character info. | |
100 | byte [maxByteBufferSize]byte // UTF-8 buffer. Referenced by runeInfo.pos. | |
101 | nbyte uint8 // Number or bytes. | |
102 | ss streamSafe // For limiting length of non-starter sequence. | |
103 | nrune int // Number of runeInfos. | |
104 | f formInfo | |
105 | ||
106 | src input | |
107 | nsrc int | |
108 | tmpBytes input | |
109 | ||
110 | out []byte | |
111 | flushF func(*reorderBuffer) bool | |
112 | } | |
113 | ||
114 | func (rb *reorderBuffer) init(f Form, src []byte) { | |
115 | rb.f = *formTable[f] | |
116 | rb.src.setBytes(src) | |
117 | rb.nsrc = len(src) | |
118 | rb.ss = 0 | |
119 | } | |
120 | ||
121 | func (rb *reorderBuffer) initString(f Form, src string) { | |
122 | rb.f = *formTable[f] | |
123 | rb.src.setString(src) | |
124 | rb.nsrc = len(src) | |
125 | rb.ss = 0 | |
126 | } | |
127 | ||
128 | func (rb *reorderBuffer) setFlusher(out []byte, f func(*reorderBuffer) bool) { | |
129 | rb.out = out | |
130 | rb.flushF = f | |
131 | } | |
132 | ||
133 | // reset discards all characters from the buffer. | |
134 | func (rb *reorderBuffer) reset() { | |
135 | rb.nrune = 0 | |
136 | rb.nbyte = 0 | |
137 | } | |
138 | ||
139 | func (rb *reorderBuffer) doFlush() bool { | |
140 | if rb.f.composing { | |
141 | rb.compose() | |
142 | } | |
143 | res := rb.flushF(rb) | |
144 | rb.reset() | |
145 | return res | |
146 | } | |
147 | ||
148 | // appendFlush appends the normalized segment to rb.out. | |
149 | func appendFlush(rb *reorderBuffer) bool { | |
150 | for i := 0; i < rb.nrune; i++ { | |
151 | start := rb.rune[i].pos | |
152 | end := start + rb.rune[i].size | |
153 | rb.out = append(rb.out, rb.byte[start:end]...) | |
154 | } | |
155 | return true | |
156 | } | |
157 | ||
158 | // flush appends the normalized segment to out and resets rb. | |
159 | func (rb *reorderBuffer) flush(out []byte) []byte { | |
160 | for i := 0; i < rb.nrune; i++ { | |
161 | start := rb.rune[i].pos | |
162 | end := start + rb.rune[i].size | |
163 | out = append(out, rb.byte[start:end]...) | |
164 | } | |
165 | rb.reset() | |
166 | return out | |
167 | } | |
168 | ||
169 | // flushCopy copies the normalized segment to buf and resets rb. | |
170 | // It returns the number of bytes written to buf. | |
171 | func (rb *reorderBuffer) flushCopy(buf []byte) int { | |
172 | p := 0 | |
173 | for i := 0; i < rb.nrune; i++ { | |
174 | runep := rb.rune[i] | |
175 | p += copy(buf[p:], rb.byte[runep.pos:runep.pos+runep.size]) | |
176 | } | |
177 | rb.reset() | |
178 | return p | |
179 | } | |
180 | ||
181 | // insertOrdered inserts a rune in the buffer, ordered by Canonical Combining Class. | |
182 | // It returns false if the buffer is not large enough to hold the rune. | |
183 | // It is used internally by insert and insertString only. | |
184 | func (rb *reorderBuffer) insertOrdered(info Properties) { | |
185 | n := rb.nrune | |
186 | b := rb.rune[:] | |
187 | cc := info.ccc | |
188 | if cc > 0 { | |
189 | // Find insertion position + move elements to make room. | |
190 | for ; n > 0; n-- { | |
191 | if b[n-1].ccc <= cc { | |
192 | break | |
193 | } | |
194 | b[n] = b[n-1] | |
195 | } | |
196 | } | |
197 | rb.nrune += 1 | |
198 | pos := uint8(rb.nbyte) | |
199 | rb.nbyte += utf8.UTFMax | |
200 | info.pos = pos | |
201 | b[n] = info | |
202 | } | |
203 | ||
204 | // insertErr is an error code returned by insert. Using this type instead | |
205 | // of error improves performance up to 20% for many of the benchmarks. | |
206 | type insertErr int | |
207 | ||
208 | const ( | |
209 | iSuccess insertErr = -iota | |
210 | iShortDst | |
211 | iShortSrc | |
212 | ) | |
213 | ||
214 | // insertFlush inserts the given rune in the buffer ordered by CCC. | |
215 | // If a decomposition with multiple segments are encountered, they leading | |
216 | // ones are flushed. | |
217 | // It returns a non-zero error code if the rune was not inserted. | |
218 | func (rb *reorderBuffer) insertFlush(src input, i int, info Properties) insertErr { | |
219 | if rune := src.hangul(i); rune != 0 { | |
220 | rb.decomposeHangul(rune) | |
221 | return iSuccess | |
222 | } | |
223 | if info.hasDecomposition() { | |
224 | return rb.insertDecomposed(info.Decomposition()) | |
225 | } | |
226 | rb.insertSingle(src, i, info) | |
227 | return iSuccess | |
228 | } | |
229 | ||
230 | // insertUnsafe inserts the given rune in the buffer ordered by CCC. | |
231 | // It is assumed there is sufficient space to hold the runes. It is the | |
232 | // responsibility of the caller to ensure this. This can be done by checking | |
233 | // the state returned by the streamSafe type. | |
234 | func (rb *reorderBuffer) insertUnsafe(src input, i int, info Properties) { | |
235 | if rune := src.hangul(i); rune != 0 { | |
236 | rb.decomposeHangul(rune) | |
237 | } | |
238 | if info.hasDecomposition() { | |
239 | // TODO: inline. | |
240 | rb.insertDecomposed(info.Decomposition()) | |
241 | } else { | |
242 | rb.insertSingle(src, i, info) | |
243 | } | |
244 | } | |
245 | ||
246 | // insertDecomposed inserts an entry in to the reorderBuffer for each rune | |
247 | // in dcomp. dcomp must be a sequence of decomposed UTF-8-encoded runes. | |
248 | // It flushes the buffer on each new segment start. | |
249 | func (rb *reorderBuffer) insertDecomposed(dcomp []byte) insertErr { | |
250 | rb.tmpBytes.setBytes(dcomp) | |
251 | // As the streamSafe accounting already handles the counting for modifiers, | |
252 | // we don't have to call next. However, we do need to keep the accounting | |
253 | // intact when flushing the buffer. | |
254 | for i := 0; i < len(dcomp); { | |
255 | info := rb.f.info(rb.tmpBytes, i) | |
256 | if info.BoundaryBefore() && rb.nrune > 0 && !rb.doFlush() { | |
257 | return iShortDst | |
258 | } | |
259 | i += copy(rb.byte[rb.nbyte:], dcomp[i:i+int(info.size)]) | |
260 | rb.insertOrdered(info) | |
261 | } | |
262 | return iSuccess | |
263 | } | |
264 | ||
265 | // insertSingle inserts an entry in the reorderBuffer for the rune at | |
266 | // position i. info is the runeInfo for the rune at position i. | |
267 | func (rb *reorderBuffer) insertSingle(src input, i int, info Properties) { | |
268 | src.copySlice(rb.byte[rb.nbyte:], i, i+int(info.size)) | |
269 | rb.insertOrdered(info) | |
270 | } | |
271 | ||
272 | // insertCGJ inserts a Combining Grapheme Joiner (0x034f) into rb. | |
273 | func (rb *reorderBuffer) insertCGJ() { | |
274 | rb.insertSingle(input{str: GraphemeJoiner}, 0, Properties{size: uint8(len(GraphemeJoiner))}) | |
275 | } | |
276 | ||
277 | // appendRune inserts a rune at the end of the buffer. It is used for Hangul. | |
278 | func (rb *reorderBuffer) appendRune(r rune) { | |
279 | bn := rb.nbyte | |
280 | sz := utf8.EncodeRune(rb.byte[bn:], rune(r)) | |
281 | rb.nbyte += utf8.UTFMax | |
282 | rb.rune[rb.nrune] = Properties{pos: bn, size: uint8(sz)} | |
283 | rb.nrune++ | |
284 | } | |
285 | ||
286 | // assignRune sets a rune at position pos. It is used for Hangul and recomposition. | |
287 | func (rb *reorderBuffer) assignRune(pos int, r rune) { | |
288 | bn := rb.rune[pos].pos | |
289 | sz := utf8.EncodeRune(rb.byte[bn:], rune(r)) | |
290 | rb.rune[pos] = Properties{pos: bn, size: uint8(sz)} | |
291 | } | |
292 | ||
293 | // runeAt returns the rune at position n. It is used for Hangul and recomposition. | |
294 | func (rb *reorderBuffer) runeAt(n int) rune { | |
295 | inf := rb.rune[n] | |
296 | r, _ := utf8.DecodeRune(rb.byte[inf.pos : inf.pos+inf.size]) | |
297 | return r | |
298 | } | |
299 | ||
300 | // bytesAt returns the UTF-8 encoding of the rune at position n. | |
301 | // It is used for Hangul and recomposition. | |
302 | func (rb *reorderBuffer) bytesAt(n int) []byte { | |
303 | inf := rb.rune[n] | |
304 | return rb.byte[inf.pos : int(inf.pos)+int(inf.size)] | |
305 | } | |
306 | ||
307 | // For Hangul we combine algorithmically, instead of using tables. | |
308 | const ( | |
309 | hangulBase = 0xAC00 // UTF-8(hangulBase) -> EA B0 80 | |
310 | hangulBase0 = 0xEA | |
311 | hangulBase1 = 0xB0 | |
312 | hangulBase2 = 0x80 | |
313 | ||
314 | hangulEnd = hangulBase + jamoLVTCount // UTF-8(0xD7A4) -> ED 9E A4 | |
315 | hangulEnd0 = 0xED | |
316 | hangulEnd1 = 0x9E | |
317 | hangulEnd2 = 0xA4 | |
318 | ||
319 | jamoLBase = 0x1100 // UTF-8(jamoLBase) -> E1 84 00 | |
320 | jamoLBase0 = 0xE1 | |
321 | jamoLBase1 = 0x84 | |
322 | jamoLEnd = 0x1113 | |
323 | jamoVBase = 0x1161 | |
324 | jamoVEnd = 0x1176 | |
325 | jamoTBase = 0x11A7 | |
326 | jamoTEnd = 0x11C3 | |
327 | ||
328 | jamoTCount = 28 | |
329 | jamoVCount = 21 | |
330 | jamoVTCount = 21 * 28 | |
331 | jamoLVTCount = 19 * 21 * 28 | |
332 | ) | |
333 | ||
334 | const hangulUTF8Size = 3 | |
335 | ||
336 | func isHangul(b []byte) bool { | |
337 | if len(b) < hangulUTF8Size { | |
338 | return false | |
339 | } | |
340 | b0 := b[0] | |
341 | if b0 < hangulBase0 { | |
342 | return false | |
343 | } | |
344 | b1 := b[1] | |
345 | switch { | |
346 | case b0 == hangulBase0: | |
347 | return b1 >= hangulBase1 | |
348 | case b0 < hangulEnd0: | |
349 | return true | |
350 | case b0 > hangulEnd0: | |
351 | return false | |
352 | case b1 < hangulEnd1: | |
353 | return true | |
354 | } | |
355 | return b1 == hangulEnd1 && b[2] < hangulEnd2 | |
356 | } | |
357 | ||
358 | func isHangulString(b string) bool { | |
359 | if len(b) < hangulUTF8Size { | |
360 | return false | |
361 | } | |
362 | b0 := b[0] | |
363 | if b0 < hangulBase0 { | |
364 | return false | |
365 | } | |
366 | b1 := b[1] | |
367 | switch { | |
368 | case b0 == hangulBase0: | |
369 | return b1 >= hangulBase1 | |
370 | case b0 < hangulEnd0: | |
371 | return true | |
372 | case b0 > hangulEnd0: | |
373 | return false | |
374 | case b1 < hangulEnd1: | |
375 | return true | |
376 | } | |
377 | return b1 == hangulEnd1 && b[2] < hangulEnd2 | |
378 | } | |
379 | ||
380 | // Caller must ensure len(b) >= 2. | |
381 | func isJamoVT(b []byte) bool { | |
382 | // True if (rune & 0xff00) == jamoLBase | |
383 | return b[0] == jamoLBase0 && (b[1]&0xFC) == jamoLBase1 | |
384 | } | |
385 | ||
386 | func isHangulWithoutJamoT(b []byte) bool { | |
387 | c, _ := utf8.DecodeRune(b) | |
388 | c -= hangulBase | |
389 | return c < jamoLVTCount && c%jamoTCount == 0 | |
390 | } | |
391 | ||
392 | // decomposeHangul writes the decomposed Hangul to buf and returns the number | |
393 | // of bytes written. len(buf) should be at least 9. | |
394 | func decomposeHangul(buf []byte, r rune) int { | |
395 | const JamoUTF8Len = 3 | |
396 | r -= hangulBase | |
397 | x := r % jamoTCount | |
398 | r /= jamoTCount | |
399 | utf8.EncodeRune(buf, jamoLBase+r/jamoVCount) | |
400 | utf8.EncodeRune(buf[JamoUTF8Len:], jamoVBase+r%jamoVCount) | |
401 | if x != 0 { | |
402 | utf8.EncodeRune(buf[2*JamoUTF8Len:], jamoTBase+x) | |
403 | return 3 * JamoUTF8Len | |
404 | } | |
405 | return 2 * JamoUTF8Len | |
406 | } | |
407 | ||
408 | // decomposeHangul algorithmically decomposes a Hangul rune into | |
409 | // its Jamo components. | |
107c1cdb | 410 | // See https://unicode.org/reports/tr15/#Hangul for details on decomposing Hangul. |
15c0b25d AP |
411 | func (rb *reorderBuffer) decomposeHangul(r rune) { |
412 | r -= hangulBase | |
413 | x := r % jamoTCount | |
414 | r /= jamoTCount | |
415 | rb.appendRune(jamoLBase + r/jamoVCount) | |
416 | rb.appendRune(jamoVBase + r%jamoVCount) | |
417 | if x != 0 { | |
418 | rb.appendRune(jamoTBase + x) | |
419 | } | |
420 | } | |
421 | ||
422 | // combineHangul algorithmically combines Jamo character components into Hangul. | |
107c1cdb | 423 | // See https://unicode.org/reports/tr15/#Hangul for details on combining Hangul. |
15c0b25d AP |
424 | func (rb *reorderBuffer) combineHangul(s, i, k int) { |
425 | b := rb.rune[:] | |
426 | bn := rb.nrune | |
427 | for ; i < bn; i++ { | |
428 | cccB := b[k-1].ccc | |
429 | cccC := b[i].ccc | |
430 | if cccB == 0 { | |
431 | s = k - 1 | |
432 | } | |
433 | if s != k-1 && cccB >= cccC { | |
434 | // b[i] is blocked by greater-equal cccX below it | |
435 | b[k] = b[i] | |
436 | k++ | |
437 | } else { | |
438 | l := rb.runeAt(s) // also used to compare to hangulBase | |
439 | v := rb.runeAt(i) // also used to compare to jamoT | |
440 | switch { | |
441 | case jamoLBase <= l && l < jamoLEnd && | |
442 | jamoVBase <= v && v < jamoVEnd: | |
443 | // 11xx plus 116x to LV | |
444 | rb.assignRune(s, hangulBase+ | |
445 | (l-jamoLBase)*jamoVTCount+(v-jamoVBase)*jamoTCount) | |
446 | case hangulBase <= l && l < hangulEnd && | |
447 | jamoTBase < v && v < jamoTEnd && | |
448 | ((l-hangulBase)%jamoTCount) == 0: | |
449 | // ACxx plus 11Ax to LVT | |
450 | rb.assignRune(s, l+v-jamoTBase) | |
451 | default: | |
452 | b[k] = b[i] | |
453 | k++ | |
454 | } | |
455 | } | |
456 | } | |
457 | rb.nrune = k | |
458 | } | |
459 | ||
460 | // compose recombines the runes in the buffer. | |
461 | // It should only be used to recompose a single segment, as it will not | |
462 | // handle alternations between Hangul and non-Hangul characters correctly. | |
463 | func (rb *reorderBuffer) compose() { | |
107c1cdb ND |
464 | // Lazily load the map used by the combine func below, but do |
465 | // it outside of the loop. | |
466 | recompMapOnce.Do(buildRecompMap) | |
467 | ||
15c0b25d AP |
468 | // UAX #15, section X5 , including Corrigendum #5 |
469 | // "In any character sequence beginning with starter S, a character C is | |
470 | // blocked from S if and only if there is some character B between S | |
471 | // and C, and either B is a starter or it has the same or higher | |
472 | // combining class as C." | |
473 | bn := rb.nrune | |
474 | if bn == 0 { | |
475 | return | |
476 | } | |
477 | k := 1 | |
478 | b := rb.rune[:] | |
479 | for s, i := 0, 1; i < bn; i++ { | |
480 | if isJamoVT(rb.bytesAt(i)) { | |
481 | // Redo from start in Hangul mode. Necessary to support | |
482 | // U+320E..U+321E in NFKC mode. | |
483 | rb.combineHangul(s, i, k) | |
484 | return | |
485 | } | |
486 | ii := b[i] | |
487 | // We can only use combineForward as a filter if we later | |
488 | // get the info for the combined character. This is more | |
489 | // expensive than using the filter. Using combinesBackward() | |
490 | // is safe. | |
491 | if ii.combinesBackward() { | |
492 | cccB := b[k-1].ccc | |
493 | cccC := ii.ccc | |
494 | blocked := false // b[i] blocked by starter or greater or equal CCC? | |
495 | if cccB == 0 { | |
496 | s = k - 1 | |
497 | } else { | |
498 | blocked = s != k-1 && cccB >= cccC | |
499 | } | |
500 | if !blocked { | |
501 | combined := combine(rb.runeAt(s), rb.runeAt(i)) | |
502 | if combined != 0 { | |
503 | rb.assignRune(s, combined) | |
504 | continue | |
505 | } | |
506 | } | |
507 | } | |
508 | b[k] = b[i] | |
509 | k++ | |
510 | } | |
511 | rb.nrune = k | |
512 | } |