trieval.go (6419B)
1 // Code generated by running "go generate" in golang.org/x/text. DO NOT EDIT. 2 3 package cases 4 5 // This file contains definitions for interpreting the trie value of the case 6 // trie generated by "go run gen*.go". It is shared by both the generator 7 // program and the resultant package. Sharing is achieved by the generator 8 // copying gen_trieval.go to trieval.go and changing what's above this comment. 9 10 // info holds case information for a single rune. It is the value returned 11 // by a trie lookup. Most mapping information can be stored in a single 16-bit 12 // value. If not, for example when a rune is mapped to multiple runes, the value 13 // stores some basic case data and an index into an array with additional data. 14 // 15 // The per-rune values have the following format: 16 // 17 // if (exception) { 18 // 15..4 unsigned exception index 19 // } else { 20 // 15..8 XOR pattern or index to XOR pattern for case mapping 21 // Only 13..8 are used for XOR patterns. 22 // 7 inverseFold (fold to upper, not to lower) 23 // 6 index: interpret the XOR pattern as an index 24 // or isMid if case mode is cIgnorableUncased. 25 // 5..4 CCC: zero (normal or break), above or other 26 // } 27 // 3 exception: interpret this value as an exception index 28 // (TODO: is this bit necessary? Probably implied from case mode.) 29 // 2..0 case mode 30 // 31 // For the non-exceptional cases, a rune must be either uncased, lowercase or 32 // uppercase. If the rune is cased, the XOR pattern maps either a lowercase 33 // rune to uppercase or an uppercase rune to lowercase (applied to the 10 34 // least-significant bits of the rune). 35 // 36 // See the definitions below for a more detailed description of the various 37 // bits. 38 type info uint16 39 40 const ( 41 casedMask = 0x0003 42 fullCasedMask = 0x0007 43 ignorableMask = 0x0006 44 ignorableValue = 0x0004 45 46 inverseFoldBit = 1 << 7 47 isMidBit = 1 << 6 48 49 exceptionBit = 1 << 3 50 exceptionShift = 4 51 numExceptionBits = 12 52 53 xorIndexBit = 1 << 6 54 xorShift = 8 55 56 // There is no mapping if all xor bits and the exception bit are zero. 57 hasMappingMask = 0xff80 | exceptionBit 58 ) 59 60 // The case mode bits encodes the case type of a rune. This includes uncased, 61 // title, upper and lower case and case ignorable. (For a definition of these 62 // terms see Chapter 3 of The Unicode Standard Core Specification.) In some rare 63 // cases, a rune can be both cased and case-ignorable. This is encoded by 64 // cIgnorableCased. A rune of this type is always lower case. Some runes are 65 // cased while not having a mapping. 66 // 67 // A common pattern for scripts in the Unicode standard is for upper and lower 68 // case runes to alternate for increasing rune values (e.g. the accented Latin 69 // ranges starting from U+0100 and U+1E00 among others and some Cyrillic 70 // characters). We use this property by defining a cXORCase mode, where the case 71 // mode (always upper or lower case) is derived from the rune value. As the XOR 72 // pattern for case mappings is often identical for successive runes, using 73 // cXORCase can result in large series of identical trie values. This, in turn, 74 // allows us to better compress the trie blocks. 75 const ( 76 cUncased info = iota // 000 77 cTitle // 001 78 cLower // 010 79 cUpper // 011 80 cIgnorableUncased // 100 81 cIgnorableCased // 101 // lower case if mappings exist 82 cXORCase // 11x // case is cLower | ((rune&1) ^ x) 83 84 maxCaseMode = cUpper 85 ) 86 87 func (c info) isCased() bool { 88 return c&casedMask != 0 89 } 90 91 func (c info) isCaseIgnorable() bool { 92 return c&ignorableMask == ignorableValue 93 } 94 95 func (c info) isNotCasedAndNotCaseIgnorable() bool { 96 return c&fullCasedMask == 0 97 } 98 99 func (c info) isCaseIgnorableAndNotCased() bool { 100 return c&fullCasedMask == cIgnorableUncased 101 } 102 103 func (c info) isMid() bool { 104 return c&(fullCasedMask|isMidBit) == isMidBit|cIgnorableUncased 105 } 106 107 // The case mapping implementation will need to know about various Canonical 108 // Combining Class (CCC) values. We encode two of these in the trie value: 109 // cccZero (0) and cccAbove (230). If the value is cccOther, it means that 110 // CCC(r) > 0, but not 230. A value of cccBreak means that CCC(r) == 0 and that 111 // the rune also has the break category Break (see below). 112 const ( 113 cccBreak info = iota << 4 114 cccZero 115 cccAbove 116 cccOther 117 118 cccMask = cccBreak | cccZero | cccAbove | cccOther 119 ) 120 121 const ( 122 starter = 0 123 above = 230 124 iotaSubscript = 240 125 ) 126 127 // The exceptions slice holds data that does not fit in a normal info entry. 128 // The entry is pointed to by the exception index in an entry. It has the 129 // following format: 130 // 131 // Header: 132 // 133 // byte 0: 134 // 7..6 unused 135 // 5..4 CCC type (same bits as entry) 136 // 3 unused 137 // 2..0 length of fold 138 // 139 // byte 1: 140 // 7..6 unused 141 // 5..3 length of 1st mapping of case type 142 // 2..0 length of 2nd mapping of case type 143 // 144 // case 1st 2nd 145 // lower -> upper, title 146 // upper -> lower, title 147 // title -> lower, upper 148 // 149 // Lengths with the value 0x7 indicate no value and implies no change. 150 // A length of 0 indicates a mapping to zero-length string. 151 // 152 // Body bytes: 153 // 154 // case folding bytes 155 // lowercase mapping bytes 156 // uppercase mapping bytes 157 // titlecase mapping bytes 158 // closure mapping bytes (for NFKC_Casefold). (TODO) 159 // 160 // Fallbacks: 161 // 162 // missing fold -> lower 163 // missing title -> upper 164 // all missing -> original rune 165 // 166 // exceptions starts with a dummy byte to enforce that there is no zero index 167 // value. 168 const ( 169 lengthMask = 0x07 170 lengthBits = 3 171 noChange = 0 172 ) 173 174 // References to generated trie. 175 176 var trie = newCaseTrie(0) 177 178 var sparse = sparseBlocks{ 179 values: sparseValues[:], 180 offsets: sparseOffsets[:], 181 } 182 183 // Sparse block lookup code. 184 185 // valueRange is an entry in a sparse block. 186 type valueRange struct { 187 value uint16 188 lo, hi byte 189 } 190 191 type sparseBlocks struct { 192 values []valueRange 193 offsets []uint16 194 } 195 196 // lookup returns the value from values block n for byte b using binary search. 197 func (s *sparseBlocks) lookup(n uint32, b byte) uint16 { 198 lo := s.offsets[n] 199 hi := s.offsets[n+1] 200 for lo < hi { 201 m := lo + (hi-lo)/2 202 r := s.values[m] 203 if r.lo <= b && b <= r.hi { 204 return r.value 205 } 206 if b < r.lo { 207 hi = m 208 } else { 209 lo = m + 1 210 } 211 } 212 return 0 213 } 214 215 // lastRuneForTesting is the last rune used for testing. Everything after this 216 // is boring. 217 const lastRuneForTesting = rune(0x1FFFF)