vendor/golang.org/x/text/internal/export/idna/gen.go

   1 // Copyright 2016 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 // +build ignore
   6
   7 // This program generates the trie for idna operations. The Unicode casing
   8 // algorithm requires the lookup of various properties and mappings for each
   9 // rune. The table generated by this generator combines several of the most
  10 // frequently used of these into a single trie so that they can be accessed
  11 // with a single lookup.
  12 package main
  13
  14 import (
  15         "fmt"
  16         "io"
  17         "log"
  18         "unicode"
  19         "unicode/utf8"
  20
  21         "golang.org/x/text/internal/gen"
  22         "golang.org/x/text/internal/triegen"
  23         "golang.org/x/text/internal/ucd"
  24 )
  25
  26 func main() {
  27         gen.Init()
  28         genTables()
  29         gen.Repackage("gen_trieval.go", "trieval.go", "idna")
  30         gen.Repackage("gen_common.go", "common_test.go", "idna")
  31 }
  32
  33 var runes = map[rune]info{}
  34
  35 func genTables() {
  36         t := triegen.NewTrie("idna")
  37
  38         ucd.Parse(gen.OpenUCDFile("UnicodeData.txt"), func(p *ucd.Parser) {
  39                 r := p.Rune(0)
  40
  41                 const cccVirama = 9
  42                 if p.Int(ucd.CanonicalCombiningClass) == cccVirama {
  43                         runes[p.Rune(0)] = viramaModifier
  44                 }
  45                 switch {
  46                 case unicode.In(r, unicode.Mark):
  47                         runes[r] |= modifier
  48                 }
  49         })
  50
  51         ucd.Parse(gen.OpenUCDFile("extracted/DerivedJoiningType.txt"), func(p *ucd.Parser) {
  52                 switch v := p.String(1); v {
  53                 case "L", "D", "T", "R":
  54                         runes[p.Rune(0)] |= joinType[v] << joinShift
  55                 }
  56         })
  57
  58         ucd.Parse(gen.OpenUnicodeFile("idna", "", "IdnaMappingTable.txt"), func(p *ucd.Parser) {
  59                 r := p.Rune(0)
  60
  61                 // The mappings table explicitly defines surrogates as invalid.
  62                 if !utf8.ValidRune(r) {
  63                         return
  64                 }
  65
  66                 cat := catFromEntry(p)
  67                 isMapped := cat == mapped || cat == disallowedSTD3Mapped || cat == deviation
  68                 if !isMapped {
  69                         // Only include additional category information for non-mapped
  70                         // runes. The additional information is only used after mapping and
  71                         // the bits would clash with mapping information.
  72                         // TODO: it would be possible to inline this data and avoid
  73                         // additional lookups. This is quite tedious, though, so let's first
  74                         // see if we need this.
  75                         cat |= category(runes[r])
  76                 }
  77
  78                 s := string(p.Runes(2))
  79                 if s != "" && !isMapped {
  80                         log.Fatalf("%U: Mapping with non-mapping category %d", r, cat)
  81                 }
  82                 t.Insert(r, uint64(makeEntry(r, s))+uint64(cat))
  83         })
  84
  85         w := gen.NewCodeWriter()
  86         defer w.WriteGoFile("tables.go", "idna")
  87
  88         gen.WriteUnicodeVersion(w)
  89
  90         w.WriteVar("mappings", string(mappings))
  91         w.WriteVar("xorData", string(xorData))
  92
  93         sz, err := t.Gen(w, triegen.Compact(&normCompacter{}))
  94         if err != nil {
  95                 log.Fatal(err)
  96         }
  97         w.Size += sz
  98 }
  99
 100 var (
 101         // mappings contains replacement strings for mapped runes, each prefixed
 102         // with a byte containing the length of the following string.
 103         mappings = []byte{}
 104         mapCache = map[string]int{}
 105
 106         // xorData is like mappings, except that it contains XOR data.
 107         // We split these two tables so that we don't get an overflow.
 108         xorData  = []byte{}
 109         xorCache = map[string]int{}
 110 )
 111
 112 // makeEntry creates a trie entry.
 113 func makeEntry(r rune, mapped string) info {
 114         orig := string(r)
 115
 116         if len(orig) != len(mapped) {
 117                 // Store the mapped value as is in the mappings table.
 118                 index := len(mappings)
 119                 if x, ok := mapCache[mapped]; ok {
 120                         index = x
 121                 } else {
 122                         mapCache[mapped] = index
 123                         mappings = append(mappings, byte(len(mapped)))
 124                         mappings = append(mappings, mapped...)
 125                 }
 126                 return info(index) << indexShift
 127         }
 128
 129         // Create per-byte XOR mask.
 130         var b []byte
 131         for i := 0; i < len(orig); i++ {
 132                 b = append(b, orig[i]^mapped[i])
 133         }
 134
 135         // Remove leading 0 bytes, but keep at least one byte.
 136         for ; len(b) > 1 && b[0] == 0; b = b[1:] {
 137         }
 138
 139         if len(b) == 1 {
 140                 return xorBit | inlineXOR | info(b[0])<<indexShift
 141         }
 142         mapped = string(b)
 143
 144         // Store the mapped value as is in the mappings table.
 145         index := len(xorData)
 146         if x, ok := xorCache[mapped]; ok {
 147                 index = x
 148         } else {
 149                 xorCache[mapped] = index
 150                 xorData = append(xorData, byte(len(mapped)))
 151                 xorData = append(xorData, mapped...)
 152         }
 153         return xorBit | info(index)<<indexShift
 154 }
 155
 156 // The following code implements a triegen.Compacter that was originally
 157 // designed for normalization. The IDNA table has some similarities with the
 158 // norm table. Using this compacter, together with the XOR pattern approach,
 159 // reduces the table size by roughly 100K. It can probably be compressed further
 160 // by also including elements of the compacter used by cases, but for now it is
 161 // good enough.
 162
 163 const maxSparseEntries = 16
 164
 165 type normCompacter struct {
 166         sparseBlocks [][]uint64
 167         sparseOffset []uint16
 168         sparseCount  int
 169 }
 170
 171 func mostFrequentStride(a []uint64) int {
 172         counts := make(map[int]int)
 173         var v int
 174         for _, x := range a {
 175                 if stride := int(x) - v; v != 0 && stride >= 0 {
 176                         counts[stride]++
 177                 }
 178                 v = int(x)
 179         }
 180         var maxs, maxc int
 181         for stride, cnt := range counts {
 182                 if cnt > maxc || (cnt == maxc && stride < maxs) {
 183                         maxs, maxc = stride, cnt
 184                 }
 185         }
 186         return maxs
 187 }
 188
 189 func countSparseEntries(a []uint64) int {
 190         stride := mostFrequentStride(a)
 191         var v, count int
 192         for _, tv := range a {
 193                 if int(tv)-v != stride {
 194                         if tv != 0 {
 195                                 count++
 196                         }
 197                 }
 198                 v = int(tv)
 199         }
 200         return count
 201 }
 202
 203 func (c *normCompacter) Size(v []uint64) (sz int, ok bool) {
 204         if n := countSparseEntries(v); n <= maxSparseEntries {
 205                 return (n+1)*4 + 2, true
 206         }
 207         return 0, false
 208 }
 209
 210 func (c *normCompacter) Store(v []uint64) uint32 {
 211         h := uint32(len(c.sparseOffset))
 212         c.sparseBlocks = append(c.sparseBlocks, v)
 213         c.sparseOffset = append(c.sparseOffset, uint16(c.sparseCount))
 214         c.sparseCount += countSparseEntries(v) + 1
 215         return h
 216 }
 217
 218 func (c *normCompacter) Handler() string {
 219         return "idnaSparse.lookup"
 220 }
 221
 222 func (c *normCompacter) Print(w io.Writer) (retErr error) {
 223         p := func(f string, x ...interface{}) {
 224                 if _, err := fmt.Fprintf(w, f, x...); retErr == nil && err != nil {
 225                         retErr = err
 226                 }
 227         }
 228
 229         ls := len(c.sparseBlocks)
 230         p("// idnaSparseOffset: %d entries, %d bytes\n", ls, ls*2)
 231         p("var idnaSparseOffset = %#v\n\n", c.sparseOffset)
 232
 233         ns := c.sparseCount
 234         p("// idnaSparseValues: %d entries, %d bytes\n", ns, ns*4)
 235         p("var idnaSparseValues = [%d]valueRange {", ns)
 236         for i, b := range c.sparseBlocks {
 237                 p("\n// Block %#x, offset %#x", i, c.sparseOffset[i])
 238                 var v int
 239                 stride := mostFrequentStride(b)
 240                 n := countSparseEntries(b)
 241                 p("\n{value:%#04x,lo:%#02x},", stride, uint8(n))
 242                 for i, nv := range b {
 243                         if int(nv)-v != stride {
 244                                 if v != 0 {
 245                                         p(",hi:%#02x},", 0x80+i-1)
 246                                 }
 247                                 if nv != 0 {
 248                                         p("\n{value:%#04x,lo:%#02x", nv, 0x80+i)
 249                                 }
 250                         }
 251                         v = int(nv)
 252                 }
 253                 if v != 0 {
 254                         p(",hi:%#02x},", 0x80+len(b)-1)
 255                 }
 256         }
 257         p("\n}\n\n")
 258         return
 259 }