diff options
Diffstat (limited to 'vendor/golang.org/x/text/unicode/norm/composition.go')
-rw-r--r-- | vendor/golang.org/x/text/unicode/norm/composition.go | 508 |
1 files changed, 508 insertions, 0 deletions
diff --git a/vendor/golang.org/x/text/unicode/norm/composition.go b/vendor/golang.org/x/text/unicode/norm/composition.go new file mode 100644 index 0000000..bab4c5d --- /dev/null +++ b/vendor/golang.org/x/text/unicode/norm/composition.go | |||
@@ -0,0 +1,508 @@ | |||
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. | ||
410 | // See http://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 http://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 | // UAX #15, section X5 , including Corrigendum #5 | ||
465 | // "In any character sequence beginning with starter S, a character C is | ||
466 | // blocked from S if and only if there is some character B between S | ||
467 | // and C, and either B is a starter or it has the same or higher | ||
468 | // combining class as C." | ||
469 | bn := rb.nrune | ||
470 | if bn == 0 { | ||
471 | return | ||
472 | } | ||
473 | k := 1 | ||
474 | b := rb.rune[:] | ||
475 | for s, i := 0, 1; i < bn; i++ { | ||
476 | if isJamoVT(rb.bytesAt(i)) { | ||
477 | // Redo from start in Hangul mode. Necessary to support | ||
478 | // U+320E..U+321E in NFKC mode. | ||
479 | rb.combineHangul(s, i, k) | ||
480 | return | ||
481 | } | ||
482 | ii := b[i] | ||
483 | // We can only use combineForward as a filter if we later | ||
484 | // get the info for the combined character. This is more | ||
485 | // expensive than using the filter. Using combinesBackward() | ||
486 | // is safe. | ||
487 | if ii.combinesBackward() { | ||
488 | cccB := b[k-1].ccc | ||
489 | cccC := ii.ccc | ||
490 | blocked := false // b[i] blocked by starter or greater or equal CCC? | ||
491 | if cccB == 0 { | ||
492 | s = k - 1 | ||
493 | } else { | ||
494 | blocked = s != k-1 && cccB >= cccC | ||
495 | } | ||
496 | if !blocked { | ||
497 | combined := combine(rb.runeAt(s), rb.runeAt(i)) | ||
498 | if combined != 0 { | ||
499 | rb.assignRune(s, combined) | ||
500 | continue | ||
501 | } | ||
502 | } | ||
503 | } | ||
504 | b[k] = b[i] | ||
505 | k++ | ||
506 | } | ||
507 | rb.nrune = k | ||
508 | } | ||