--- /dev/null
+// Copyright 2012 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 colltab
+
+import (
+ "fmt"
+ "unicode"
+)
+
+// Level identifies the collation comparison level.
+// The primary level corresponds to the basic sorting of text.
+// The secondary level corresponds to accents and related linguistic elements.
+// The tertiary level corresponds to casing and related concepts.
+// The quaternary level is derived from the other levels by the
+// various algorithms for handling variable elements.
+type Level int
+
+const (
+ Primary Level = iota
+ Secondary
+ Tertiary
+ Quaternary
+ Identity
+
+ NumLevels
+)
+
+const (
+ defaultSecondary = 0x20
+ defaultTertiary = 0x2
+ maxTertiary = 0x1F
+ MaxQuaternary = 0x1FFFFF // 21 bits.
+)
+
+// Elem is a representation of a collation element. This API provides ways to encode
+// and decode Elems. Implementations of collation tables may use values greater
+// or equal to PrivateUse for their own purposes. However, these should never be
+// returned by AppendNext.
+type Elem uint32
+
+const (
+ maxCE Elem = 0xAFFFFFFF
+ PrivateUse = minContract
+ minContract = 0xC0000000
+ maxContract = 0xDFFFFFFF
+ minExpand = 0xE0000000
+ maxExpand = 0xEFFFFFFF
+ minDecomp = 0xF0000000
+)
+
+type ceType int
+
+const (
+ ceNormal ceType = iota // ceNormal includes implicits (ce == 0)
+ ceContractionIndex // rune can be a start of a contraction
+ ceExpansionIndex // rune expands into a sequence of collation elements
+ ceDecompose // rune expands using NFKC decomposition
+)
+
+func (ce Elem) ctype() ceType {
+ if ce <= maxCE {
+ return ceNormal
+ }
+ if ce <= maxContract {
+ return ceContractionIndex
+ } else {
+ if ce <= maxExpand {
+ return ceExpansionIndex
+ }
+ return ceDecompose
+ }
+ panic("should not reach here")
+ return ceType(-1)
+}
+
+// For normal collation elements, we assume that a collation element either has
+// a primary or non-default secondary value, not both.
+// Collation elements with a primary value are of the form
+// 01pppppp pppppppp ppppppp0 ssssssss
+// - p* is primary collation value
+// - s* is the secondary collation value
+// 00pppppp pppppppp ppppppps sssttttt, where
+// - p* is primary collation value
+// - s* offset of secondary from default value.
+// - t* is the tertiary collation value
+// 100ttttt cccccccc pppppppp pppppppp
+// - t* is the tertiar collation value
+// - c* is the canonical combining class
+// - p* is the primary collation value
+// Collation elements with a secondary value are of the form
+// 1010cccc ccccssss ssssssss tttttttt, where
+// - c* is the canonical combining class
+// - s* is the secondary collation value
+// - t* is the tertiary collation value
+// 11qqqqqq qqqqqqqq qqqqqqq0 00000000
+// - q* quaternary value
+const (
+ ceTypeMask = 0xC0000000
+ ceTypeMaskExt = 0xE0000000
+ ceIgnoreMask = 0xF00FFFFF
+ ceType1 = 0x40000000
+ ceType2 = 0x00000000
+ ceType3or4 = 0x80000000
+ ceType4 = 0xA0000000
+ ceTypeQ = 0xC0000000
+ Ignore = ceType4
+ firstNonPrimary = 0x80000000
+ lastSpecialPrimary = 0xA0000000
+ secondaryMask = 0x80000000
+ hasTertiaryMask = 0x40000000
+ primaryValueMask = 0x3FFFFE00
+ maxPrimaryBits = 21
+ compactPrimaryBits = 16
+ maxSecondaryBits = 12
+ maxTertiaryBits = 8
+ maxCCCBits = 8
+ maxSecondaryCompactBits = 8
+ maxSecondaryDiffBits = 4
+ maxTertiaryCompactBits = 5
+ primaryShift = 9
+ compactSecondaryShift = 5
+ minCompactSecondary = defaultSecondary - 4
+)
+
+func makeImplicitCE(primary int) Elem {
+ return ceType1 | Elem(primary<<primaryShift) | defaultSecondary
+}
+
+// MakeElem returns an Elem for the given values. It will return an error
+// if the given combination of values is invalid.
+func MakeElem(primary, secondary, tertiary int, ccc uint8) (Elem, error) {
+ if w := primary; w >= 1<<maxPrimaryBits || w < 0 {
+ return 0, fmt.Errorf("makeCE: primary weight out of bounds: %x >= %x", w, 1<<maxPrimaryBits)
+ }
+ if w := secondary; w >= 1<<maxSecondaryBits || w < 0 {
+ return 0, fmt.Errorf("makeCE: secondary weight out of bounds: %x >= %x", w, 1<<maxSecondaryBits)
+ }
+ if w := tertiary; w >= 1<<maxTertiaryBits || w < 0 {
+ return 0, fmt.Errorf("makeCE: tertiary weight out of bounds: %x >= %x", w, 1<<maxTertiaryBits)
+ }
+ ce := Elem(0)
+ if primary != 0 {
+ if ccc != 0 {
+ if primary >= 1<<compactPrimaryBits {
+ return 0, fmt.Errorf("makeCE: primary weight with non-zero CCC out of bounds: %x >= %x", primary, 1<<compactPrimaryBits)
+ }
+ if secondary != defaultSecondary {
+ return 0, fmt.Errorf("makeCE: cannot combine non-default secondary value (%x) with non-zero CCC (%x)", secondary, ccc)
+ }
+ ce = Elem(tertiary << (compactPrimaryBits + maxCCCBits))
+ ce |= Elem(ccc) << compactPrimaryBits
+ ce |= Elem(primary)
+ ce |= ceType3or4
+ } else if tertiary == defaultTertiary {
+ if secondary >= 1<<maxSecondaryCompactBits {
+ return 0, fmt.Errorf("makeCE: secondary weight with non-zero primary out of bounds: %x >= %x", secondary, 1<<maxSecondaryCompactBits)
+ }
+ ce = Elem(primary<<(maxSecondaryCompactBits+1) + secondary)
+ ce |= ceType1
+ } else {
+ d := secondary - defaultSecondary + maxSecondaryDiffBits
+ if d >= 1<<maxSecondaryDiffBits || d < 0 {
+ return 0, fmt.Errorf("makeCE: secondary weight diff out of bounds: %x < 0 || %x > %x", d, d, 1<<maxSecondaryDiffBits)
+ }
+ if tertiary >= 1<<maxTertiaryCompactBits {
+ return 0, fmt.Errorf("makeCE: tertiary weight with non-zero primary out of bounds: %x > %x", tertiary, 1<<maxTertiaryCompactBits)
+ }
+ ce = Elem(primary<<maxSecondaryDiffBits + d)
+ ce = ce<<maxTertiaryCompactBits + Elem(tertiary)
+ }
+ } else {
+ ce = Elem(secondary<<maxTertiaryBits + tertiary)
+ ce += Elem(ccc) << (maxSecondaryBits + maxTertiaryBits)
+ ce |= ceType4
+ }
+ return ce, nil
+}
+
+// MakeQuaternary returns an Elem with the given quaternary value.
+func MakeQuaternary(v int) Elem {
+ return ceTypeQ | Elem(v<<primaryShift)
+}
+
+// Mask sets weights for any level smaller than l to 0.
+// The resulting Elem can be used to test for equality with
+// other Elems to which the same mask has been applied.
+func (ce Elem) Mask(l Level) uint32 {
+ return 0
+}
+
+// CCC returns the canonical combining class associated with the underlying character,
+// if applicable, or 0 otherwise.
+func (ce Elem) CCC() uint8 {
+ if ce&ceType3or4 != 0 {
+ if ce&ceType4 == ceType3or4 {
+ return uint8(ce >> 16)
+ }
+ return uint8(ce >> 20)
+ }
+ return 0
+}
+
+// Primary returns the primary collation weight for ce.
+func (ce Elem) Primary() int {
+ if ce >= firstNonPrimary {
+ if ce > lastSpecialPrimary {
+ return 0
+ }
+ return int(uint16(ce))
+ }
+ return int(ce&primaryValueMask) >> primaryShift
+}
+
+// Secondary returns the secondary collation weight for ce.
+func (ce Elem) Secondary() int {
+ switch ce & ceTypeMask {
+ case ceType1:
+ return int(uint8(ce))
+ case ceType2:
+ return minCompactSecondary + int((ce>>compactSecondaryShift)&0xF)
+ case ceType3or4:
+ if ce < ceType4 {
+ return defaultSecondary
+ }
+ return int(ce>>8) & 0xFFF
+ case ceTypeQ:
+ return 0
+ }
+ panic("should not reach here")
+}
+
+// Tertiary returns the tertiary collation weight for ce.
+func (ce Elem) Tertiary() uint8 {
+ if ce&hasTertiaryMask == 0 {
+ if ce&ceType3or4 == 0 {
+ return uint8(ce & 0x1F)
+ }
+ if ce&ceType4 == ceType4 {
+ return uint8(ce)
+ }
+ return uint8(ce>>24) & 0x1F // type 2
+ } else if ce&ceTypeMask == ceType1 {
+ return defaultTertiary
+ }
+ // ce is a quaternary value.
+ return 0
+}
+
+func (ce Elem) updateTertiary(t uint8) Elem {
+ if ce&ceTypeMask == ceType1 {
+ // convert to type 4
+ nce := ce & primaryValueMask
+ nce |= Elem(uint8(ce)-minCompactSecondary) << compactSecondaryShift
+ ce = nce
+ } else if ce&ceTypeMaskExt == ceType3or4 {
+ ce &= ^Elem(maxTertiary << 24)
+ return ce | (Elem(t) << 24)
+ } else {
+ // type 2 or 4
+ ce &= ^Elem(maxTertiary)
+ }
+ return ce | Elem(t)
+}
+
+// Quaternary returns the quaternary value if explicitly specified,
+// 0 if ce == Ignore, or MaxQuaternary otherwise.
+// Quaternary values are used only for shifted variants.
+func (ce Elem) Quaternary() int {
+ if ce&ceTypeMask == ceTypeQ {
+ return int(ce&primaryValueMask) >> primaryShift
+ } else if ce&ceIgnoreMask == Ignore {
+ return 0
+ }
+ return MaxQuaternary
+}
+
+// Weight returns the collation weight for the given level.
+func (ce Elem) Weight(l Level) int {
+ switch l {
+ case Primary:
+ return ce.Primary()
+ case Secondary:
+ return ce.Secondary()
+ case Tertiary:
+ return int(ce.Tertiary())
+ case Quaternary:
+ return ce.Quaternary()
+ }
+ return 0 // return 0 (ignore) for undefined levels.
+}
+
+// For contractions, collation elements are of the form
+// 110bbbbb bbbbbbbb iiiiiiii iiiinnnn, where
+// - n* is the size of the first node in the contraction trie.
+// - i* is the index of the first node in the contraction trie.
+// - b* is the offset into the contraction collation element table.
+// See contract.go for details on the contraction trie.
+const (
+ maxNBits = 4
+ maxTrieIndexBits = 12
+ maxContractOffsetBits = 13
+)
+
+func splitContractIndex(ce Elem) (index, n, offset int) {
+ n = int(ce & (1<<maxNBits - 1))
+ ce >>= maxNBits
+ index = int(ce & (1<<maxTrieIndexBits - 1))
+ ce >>= maxTrieIndexBits
+ offset = int(ce & (1<<maxContractOffsetBits - 1))
+ return
+}
+
+// For expansions, Elems are of the form 11100000 00000000 bbbbbbbb bbbbbbbb,
+// where b* is the index into the expansion sequence table.
+const maxExpandIndexBits = 16
+
+func splitExpandIndex(ce Elem) (index int) {
+ return int(uint16(ce))
+}
+
+// Some runes can be expanded using NFKD decomposition. Instead of storing the full
+// sequence of collation elements, we decompose the rune and lookup the collation
+// elements for each rune in the decomposition and modify the tertiary weights.
+// The Elem, in this case, is of the form 11110000 00000000 wwwwwwww vvvvvvvv, where
+// - v* is the replacement tertiary weight for the first rune,
+// - w* is the replacement tertiary weight for the second rune,
+// Tertiary weights of subsequent runes should be replaced with maxTertiary.
+// See https://www.unicode.org/reports/tr10/#Compatibility_Decompositions for more details.
+func splitDecompose(ce Elem) (t1, t2 uint8) {
+ return uint8(ce), uint8(ce >> 8)
+}
+
+const (
+ // These constants were taken from https://www.unicode.org/versions/Unicode6.0.0/ch12.pdf.
+ minUnified rune = 0x4E00
+ maxUnified = 0x9FFF
+ minCompatibility = 0xF900
+ maxCompatibility = 0xFAFF
+ minRare = 0x3400
+ maxRare = 0x4DBF
+)
+const (
+ commonUnifiedOffset = 0x10000
+ rareUnifiedOffset = 0x20000 // largest rune in common is U+FAFF
+ otherOffset = 0x50000 // largest rune in rare is U+2FA1D
+ illegalOffset = otherOffset + int(unicode.MaxRune)
+ maxPrimary = illegalOffset + 1
+)
+
+// implicitPrimary returns the primary weight for the a rune
+// for which there is no entry for the rune in the collation table.
+// We take a different approach from the one specified in
+// https://unicode.org/reports/tr10/#Implicit_Weights,
+// but preserve the resulting relative ordering of the runes.
+func implicitPrimary(r rune) int {
+ if unicode.Is(unicode.Ideographic, r) {
+ if r >= minUnified && r <= maxUnified {
+ // The most common case for CJK.
+ return int(r) + commonUnifiedOffset
+ }
+ if r >= minCompatibility && r <= maxCompatibility {
+ // This will typically not hit. The DUCET explicitly specifies mappings
+ // for all characters that do not decompose.
+ return int(r) + commonUnifiedOffset
+ }
+ return int(r) + rareUnifiedOffset
+ }
+ return int(r) + otherOffset
+}
Code Review / barometer.git / blobdiff