gen_trieval.go 6.4 KB

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