new repo

[bytom/vapor.git] / vendor / golang.org / x / text / internal / triegen / triegen.go

// Copyright 2014 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package triegen implements a code generator for a trie for associating
// unsigned integer values with UTF-8 encoded runes.
//
// Many of the go.text packages use tries for storing per-rune information.  A
// trie is especially useful if many of the runes have the same value. If this
// is the case, many blocks can be expected to be shared allowing for
// information on many runes to be stored in little space.
//
// As most of the lookups are done directly on []byte slices, the tries use the
// UTF-8 bytes directly for the lookup. This saves a conversion from UTF-8 to
// runes and contributes a little bit to better performance. It also naturally
// provides a fast path for ASCII.
//
// Space is also an issue. There are many code points defined in Unicode and as
// a result tables can get quite large. So every byte counts. The triegen
// package automatically chooses the smallest integer values to represent the
// tables. Compacters allow further compression of the trie by allowing for
// alternative representations of individual trie blocks.
//
// triegen allows generating multiple tries as a single structure. This is
// useful when, for example, one wants to generate tries for several languages
// that have a lot of values in common. Some existing libraries for
// internationalization store all per-language data as a dynamically loadable
// chunk. The go.text packages are designed with the assumption that the user
// typically wants to compile in support for all supported languages, in line
// with the approach common to Go to create a single standalone binary. The
// multi-root trie approach can give significant storage savings in this
// scenario.
//
// triegen generates both tables and code. The code is optimized to use the
// automatically chosen data types. The following code is generated for a Trie
// or multiple Tries named "foo":
//      - type fooTrie
//              The trie type.
//
//      - func newFooTrie(x int) *fooTrie
//              Trie constructor, where x is the index of the trie passed to Gen.
//
//      - func (t *fooTrie) lookup(s []byte) (v uintX, sz int)
//              The lookup method, where uintX is automatically chosen.
//
//      - func lookupString, lookupUnsafe and lookupStringUnsafe
//              Variants of the above.
//
//      - var fooValues and fooIndex and any tables generated by Compacters.
//              The core trie data.
//
//      - var fooTrieHandles
//              Indexes of starter blocks in case of multiple trie roots.
//
// It is recommended that users test the generated trie by checking the returned
// value for every rune. Such exhaustive tests are possible as the the number of
// runes in Unicode is limited.
package triegen // import "golang.org/x/text/internal/triegen"

// TODO: Arguably, the internally optimized data types would not have to be
// exposed in the generated API. We could also investigate not generating the
// code, but using it through a package. We would have to investigate the impact
// on performance of making such change, though. For packages like unicode/norm,
// small changes like this could tank performance.

import (
        "encoding/binary"
        "fmt"
        "hash/crc64"
        "io"
        "log"
        "unicode/utf8"
)

// builder builds a set of tries for associating values with runes. The set of
// tries can share common index and value blocks.
type builder struct {
        Name string

        // ValueType is the type of the trie values looked up.
        ValueType string

        // ValueSize is the byte size of the ValueType.
        ValueSize int

        // IndexType is the type of trie index values used for all UTF-8 bytes of
        // a rune except the last one.
        IndexType string

        // IndexSize is the byte size of the IndexType.
        IndexSize int

        // SourceType is used when generating the lookup functions. If the user
        // requests StringSupport, all lookup functions will be generated for
        // string input as well.
        SourceType string

        Trie []*Trie

        IndexBlocks []*node
        ValueBlocks [][]uint64
        Compactions []compaction
        Checksum    uint64

        ASCIIBlock   string
        StarterBlock string

        indexBlockIdx map[uint64]int
        valueBlockIdx map[uint64]nodeIndex
        asciiBlockIdx map[uint64]int

        // Stats are used to fill out the template.
        Stats struct {
                NValueEntries int
                NValueBytes   int
                NIndexEntries int
                NIndexBytes   int
                NHandleBytes  int
        }

        err error
}

// A nodeIndex encodes the index of a node, which is defined by the compaction
// which stores it and an index within the compaction. For internal nodes, the
// compaction is always 0.
type nodeIndex struct {
        compaction int
        index      int
}

// compaction keeps track of stats used for the compaction.
type compaction struct {
        c         Compacter
        blocks    []*node
        maxHandle uint32
        totalSize int

        // Used by template-based generator and thus exported.
        Cutoff  uint32
        Offset  uint32
        Handler string
}

func (b *builder) setError(err error) {
        if b.err == nil {
                b.err = err
        }
}

// An Option can be passed to Gen.
type Option func(b *builder) error

// Compact configures the trie generator to use the given Compacter.
func Compact(c Compacter) Option {
        return func(b *builder) error {
                b.Compactions = append(b.Compactions, compaction{
                        c:       c,
                        Handler: c.Handler() + "(n, b)"})
                return nil
        }
}

// Gen writes Go code for a shared trie lookup structure to w for the given
// Tries. The generated trie type will be called nameTrie. newNameTrie(x) will
// return the *nameTrie for tries[x]. A value can be looked up by using one of
// the various lookup methods defined on nameTrie. It returns the table size of
// the generated trie.
func Gen(w io.Writer, name string, tries []*Trie, opts ...Option) (sz int, err error) {
        // The index contains two dummy blocks, followed by the zero block. The zero
        // block is at offset 0x80, so that the offset for the zero block for
        // continuation bytes is 0.
        b := &builder{
                Name:        name,
                Trie:        tries,
                IndexBlocks: []*node{{}, {}, {}},
                Compactions: []compaction{{
                        Handler: name + "Values[n<<6+uint32(b)]",
                }},
                // The 0 key in indexBlockIdx and valueBlockIdx is the hash of the zero
                // block.
                indexBlockIdx: map[uint64]int{0: 0},
                valueBlockIdx: map[uint64]nodeIndex{0: {}},
                asciiBlockIdx: map[uint64]int{},
        }
        b.Compactions[0].c = (*simpleCompacter)(b)

        for _, f := range opts {
                if err := f(b); err != nil {
                        return 0, err
                }
        }
        b.build()
        if b.err != nil {
                return 0, b.err
        }
        if err = b.print(w); err != nil {
                return 0, err
        }
        return b.Size(), nil
}

// A Trie represents a single root node of a trie. A builder may build several
// overlapping tries at once.
type Trie struct {
        root *node

        hiddenTrie
}

// hiddenTrie contains values we want to be visible to the template generator,
// but hidden from the API documentation.
type hiddenTrie struct {
        Name         string
        Checksum     uint64
        ASCIIIndex   int
        StarterIndex int
}

// NewTrie returns a new trie root.
func NewTrie(name string) *Trie {
        return &Trie{
                &node{
                        children: make([]*node, blockSize),
                        values:   make([]uint64, utf8.RuneSelf),
                },
                hiddenTrie{Name: name},
        }
}

// Gen is a convenience wrapper around the Gen func passing t as the only trie
// and uses the name passed to NewTrie. It returns the size of the generated
// tables.
func (t *Trie) Gen(w io.Writer, opts ...Option) (sz int, err error) {
        return Gen(w, t.Name, []*Trie{t}, opts...)
}

// node is a node of the intermediate trie structure.
type node struct {
        // children holds this node's children. It is always of length 64.
        // A child node may be nil.
        children []*node

        // values contains the values of this node. If it is non-nil, this node is
        // either a root or leaf node:
        // For root nodes, len(values) == 128 and it maps the bytes in [0x00, 0x7F].
        // For leaf nodes, len(values) ==  64 and it maps the bytes in [0x80, 0xBF].
        values []uint64

        index nodeIndex
}

// Insert associates value with the given rune. Insert will panic if a non-zero
// value is passed for an invalid rune.
func (t *Trie) Insert(r rune, value uint64) {
        if value == 0 {
                return
        }
        s := string(r)
        if []rune(s)[0] != r && value != 0 {
                // Note: The UCD tables will always assign what amounts to a zero value
                // to a surrogate. Allowing a zero value for an illegal rune allows
                // users to iterate over [0..MaxRune] without having to explicitly
                // exclude surrogates, which would be tedious.
                panic(fmt.Sprintf("triegen: non-zero value for invalid rune %U", r))
        }
        if len(s) == 1 {
                // It is a root node value (ASCII).
                t.root.values[s[0]] = value
                return
        }

        n := t.root
        for ; len(s) > 1; s = s[1:] {
                if n.children == nil {
                        n.children = make([]*node, blockSize)
                }
                p := s[0] % blockSize
                c := n.children[p]
                if c == nil {
                        c = &node{}
                        n.children[p] = c
                }
                if len(s) > 2 && c.values != nil {
                        log.Fatalf("triegen: insert(%U): found internal node with values", r)
                }
                n = c
        }
        if n.values == nil {
                n.values = make([]uint64, blockSize)
        }
        if n.children != nil {
                log.Fatalf("triegen: insert(%U): found leaf node that also has child nodes", r)
        }
        n.values[s[0]-0x80] = value
}

// Size returns the number of bytes the generated trie will take to store. It
// needs to be exported as it is used in the templates.
func (b *builder) Size() int {
        // Index blocks.
        sz := len(b.IndexBlocks) * blockSize * b.IndexSize

        // Skip the first compaction, which represents the normal value blocks, as
        // its totalSize does not account for the ASCII blocks, which are managed
        // separately.
        sz += len(b.ValueBlocks) * blockSize * b.ValueSize
        for _, c := range b.Compactions[1:] {
                sz += c.totalSize
        }

        // TODO: this computation does not account for the fixed overhead of a using
        // a compaction, either code or data. As for data, though, the typical
        // overhead of data is in the order of bytes (2 bytes for cases). Further,
        // the savings of using a compaction should anyway be substantial for it to
        // be worth it.

        // For multi-root tries, we also need to account for the handles.
        if len(b.Trie) > 1 {
                sz += 2 * b.IndexSize * len(b.Trie)
        }
        return sz
}

func (b *builder) build() {
        // Compute the sizes of the values.
        var vmax uint64
        for _, t := range b.Trie {
                vmax = maxValue(t.root, vmax)
        }
        b.ValueType, b.ValueSize = getIntType(vmax)

        // Compute all block allocations.
        // TODO: first compute the ASCII blocks for all tries and then the other
        // nodes. ASCII blocks are more restricted in placement, as they require two
        // blocks to be placed consecutively. Processing them first may improve
        // sharing (at least one zero block can be expected to be saved.)
        for _, t := range b.Trie {
                b.Checksum += b.buildTrie(t)
        }

        // Compute the offsets for all the Compacters.
        offset := uint32(0)
        for i := range b.Compactions {
                c := &b.Compactions[i]
                c.Offset = offset
                offset += c.maxHandle + 1
                c.Cutoff = offset
        }

        // Compute the sizes of indexes.
        // TODO: different byte positions could have different sizes. So far we have
        // not found a case where this is beneficial.
        imax := uint64(b.Compactions[len(b.Compactions)-1].Cutoff)
        for _, ib := range b.IndexBlocks {
                if x := uint64(ib.index.index); x > imax {
                        imax = x
                }
        }
        b.IndexType, b.IndexSize = getIntType(imax)
}

func maxValue(n *node, max uint64) uint64 {
        if n == nil {
                return max
        }
        for _, c := range n.children {
                max = maxValue(c, max)
        }
        for _, v := range n.values {
                if max < v {
                        max = v
                }
        }
        return max
}

func getIntType(v uint64) (string, int) {
        switch {
        case v < 1<<8:
                return "uint8", 1
        case v < 1<<16:
                return "uint16", 2
        case v < 1<<32:
                return "uint32", 4
        }
        return "uint64", 8
}

const (
        blockSize = 64

        // Subtract two blocks to offset 0x80, the first continuation byte.
        blockOffset = 2

        // Subtract three blocks to offset 0xC0, the first non-ASCII starter.
        rootBlockOffset = 3
)

var crcTable = crc64.MakeTable(crc64.ISO)

func (b *builder) buildTrie(t *Trie) uint64 {
        n := t.root

        // Get the ASCII offset. For the first trie, the ASCII block will be at
        // position 0.
        hasher := crc64.New(crcTable)
        binary.Write(hasher, binary.BigEndian, n.values)
        hash := hasher.Sum64()

        v, ok := b.asciiBlockIdx[hash]
        if !ok {
                v = len(b.ValueBlocks)
                b.asciiBlockIdx[hash] = v

                b.ValueBlocks = append(b.ValueBlocks, n.values[:blockSize], n.values[blockSize:])
                if v == 0 {
                        // Add the zero block at position 2 so that it will be assigned a
                        // zero reference in the lookup blocks.
                        // TODO: always do this? This would allow us to remove a check from
                        // the trie lookup, but at the expense of extra space. Analyze
                        // performance for unicode/norm.
                        b.ValueBlocks = append(b.ValueBlocks, make([]uint64, blockSize))
                }
        }
        t.ASCIIIndex = v

        // Compute remaining offsets.
        t.Checksum = b.computeOffsets(n, true)
        // We already subtracted the normal blockOffset from the index. Subtract the
        // difference for starter bytes.
        t.StarterIndex = n.index.index - (rootBlockOffset - blockOffset)
        return t.Checksum
}

func (b *builder) computeOffsets(n *node, root bool) uint64 {
        // For the first trie, the root lookup block will be at position 3, which is
        // the offset for UTF-8 non-ASCII starter bytes.
        first := len(b.IndexBlocks) == rootBlockOffset
        if first {
                b.IndexBlocks = append(b.IndexBlocks, n)
        }

        // We special-case the cases where all values recursively are 0. This allows
        // for the use of a zero block to which all such values can be directed.
        hash := uint64(0)
        if n.children != nil || n.values != nil {
                hasher := crc64.New(crcTable)
                for _, c := range n.children {
                        var v uint64
                        if c != nil {
                                v = b.computeOffsets(c, false)
                        }
                        binary.Write(hasher, binary.BigEndian, v)
                }
                binary.Write(hasher, binary.BigEndian, n.values)
                hash = hasher.Sum64()
        }

        if first {
                b.indexBlockIdx[hash] = rootBlockOffset - blockOffset
        }

        // Compacters don't apply to internal nodes.
        if n.children != nil {
                v, ok := b.indexBlockIdx[hash]
                if !ok {
                        v = len(b.IndexBlocks) - blockOffset
                        b.IndexBlocks = append(b.IndexBlocks, n)
                        b.indexBlockIdx[hash] = v
                }
                n.index = nodeIndex{0, v}
        } else {
                h, ok := b.valueBlockIdx[hash]
                if !ok {
                        bestI, bestSize := 0, blockSize*b.ValueSize
                        for i, c := range b.Compactions[1:] {
                                if sz, ok := c.c.Size(n.values); ok && bestSize > sz {
                                        bestI, bestSize = i+1, sz
                                }
                        }
                        c := &b.Compactions[bestI]
                        c.totalSize += bestSize
                        v := c.c.Store(n.values)
                        if c.maxHandle < v {
                                c.maxHandle = v
                        }
                        h = nodeIndex{bestI, int(v)}
                        b.valueBlockIdx[hash] = h
                }
                n.index = h
        }
        return hash
}