composition.go

     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 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
View as plain text