"Fossies" - the Fresh Open Source Software Archive

Member "etcd-3.4.13/vendor/golang.org/x/text/unicode/norm/composition.go" (24 Aug 2020, 14452 Bytes) of package /linux/misc/etcd-3.4.13.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Go source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. See also the latest Fossies "Diffs" side-by-side code changes report for "composition.go": 3.4.12_vs_3.4.13.

    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 }