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 []byte) {
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 []byte) 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.
410 // See https://unicode.org/reports/tr15/#Hangul for details on decomposing Hangul.
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.
423 // See https://unicode.org/reports/tr15/#Hangul for details on combining Hangul.
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() {
464 // Lazily load the map used by the combine func below, but do
465 // it outside of the loop.
466 recompMapOnce.Do(buildRecompMap)
467 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 }
513