• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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
5package norm
6
7import "unicode/utf8"
8
9const (
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.
22type ssState int
23
24const (
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.
34type 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.
38func (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.
44func (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.
71func (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
86func (ss streamSafe) isMax() bool {
87	return ss == maxNonStarters
88}
89
90// GraphemeJoiner is inserted after maxNonStarters non-starter runes.
91const 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.
98type 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
114func (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
121func (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
128func (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.
134func (rb *reorderBuffer) reset() {
135	rb.nrune = 0
136	rb.nbyte = 0
137}
138
139func (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.
149func 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.
159func (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.
171func (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.
184func (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.
206type insertErr int
207
208const (
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.
218func (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.
234func (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.
249func (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.
267func (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.
273func (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.
278func (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.
287func (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.
294func (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.
302func (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.
308const (
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
334const hangulUTF8Size = 3
335
336func 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
358func 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.
381func isJamoVT(b []byte) bool {
382	// True if (rune & 0xff00) == jamoLBase
383	return b[0] == jamoLBase0 && (b[1]&0xFC) == jamoLBase1
384}
385
386func 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.
394func 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.
411func (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.
424func (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.
463func (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}
509