composition.go 14 KB

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