[インデックス 13091] ファイルの概要
本コミットは、Go言語の実験的なロケールパッケージ exp/locale/collate において、主要な照合（Collation）機能の実装を追加するものです。具体的には、文字列の比較（Compare、CompareString）および照合キーの生成（Key、KeyFromString）に関する機能が導入されています。このコミットでは、検索機能はまだ実装されていません。また、既存のテストファイル table_test.go の型定義が新しいテストでの再利用を可能にするために変更され、不正なルーン（Unicodeコードポイント）に対するプライマリ値の数が1つに削減されています。
コミット
commit ec099b2bc7ef98af4711f4dab200ffadb26d24df
Author: Marcel van Lohuizen <mpvl@golang.org>
Date: Thu May 17 19:48:56 2012 +0200
exp/locale/collate: implementation of main collation functionality for
key and simple comparisson. Search is not yet implemented in this CL.
Changed some of the types of table_test.go to allow reuse in the new test.
Also reduced number of primary values for illegal runes to 1 (both map to
the same).
R=r
CC=golang-dev
https://golang.org/cl/6202062
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/ec099b2bc7ef98af4711f4dab200ffadb26d24df
元コミット内容
exp/locale/collate: implementation of main collation functionality for
key and simple comparisson. Search is not yet implemented in this CL.
Changed some of the types of table_test.go to allow reuse in the new test.
Also reduced number of primary values for illegal runes to 1 (both map to
the same).
変更の背景
このコミットの背景には、Go言語が国際化（i18n）と地域化（l10n）のサポートを強化するという目標があります。特に、異なる言語や文化圏において文字列を正しくソートするためには、単なるバイナリ比較ではなく、言語固有のルールに基づいた照合が必要不可欠です。Unicode Collation Algorithm (UCA) は、この複雑な要件を満たすための標準的なアルゴリズムを提供します。
このコミットは、exp/locale/collate パッケージの初期段階の実装として、UCAの主要な機能である照合キーの生成と、それを用いた文字列比較の基盤を構築することを目的としています。これにより、将来的にGoアプリケーションが多言語環境でより自然な文字列ソートを提供できるようになります。
また、テストコードの改善も重要な背景です。新しい照合機能の導入に伴い、既存のテストハーネスを再利用しつつ、新しいテストケースを効率的に追加できるように、テスト関連の型定義が調整されています。不正なルーンのプライマリ値の削減は、内部的なデータ構造の簡素化と効率化に寄与します。
前提知識の解説
照合 (Collation)
照合とは、文字列を特定の言語や文化圏のルールに従って順序付けるプロセスです。例えば、英語では 'a' の次に 'b' が来ますが、スウェーデン語では 'z' の後に 'å', 'ä', 'ö' が来ます。また、アクセント記号の有無や大文字・小文字の区別、合字（ligature）の扱いなども言語によって異なります。
Unicode Collation Algorithm (UCA)
UCAは、Unicode Consortiumによって定義された、多言語環境での文字列照合のための標準アルゴリズムです。UCAは、各文字に「照合要素（Collation Element）」と呼ばれる一連の重み（weights）を割り当てることで、この複雑な問題を解決します。
照合要素 (Collation Element) と重み (Weights)
UCAでは、各文字（または文字のシーケンス）は1つ以上の照合要素に分解されます。各照合要素は、通常、以下の4つのレベルの重みを持っています。
- プライマリ重み (Primary Weight): 文字の基本的な形状やアルファベット順を決定します。例えば、'a' と 'A' は異なる文字ですが、プライマリ重みは同じになることが多いです。これは、大文字・小文字を区別しない比較（Strength Level 1）に用いられます。
- セカンダリ重み (Secondary Weight): アクセント記号やダイアクリティカルマーク（分音記号）の違いを区別します。例えば、'a' と 'á' はプライマリ重みが同じでも、セカンダリ重みが異なります。これは、アクセントを区別する比較（Strength Level 2）に用いられます。
- ターシャリ重み (Tertiary Weight): 大文字・小文字の違いや、文字の幅（全角・半角など）を区別します。例えば、'a' と 'A' はターシャリ重みが異なります。これは、大文字・小文字を区別する比較（Strength Level 3）に用いられます。
- クォータナリ重み (Quaternary Weight): 可変要素（Variable Elements）の扱いを決定します。UCAでは、句読点や記号などの一部の文字を「可変要素」として扱い、特定の照合設定（Alternate Handling）に基づいて、プライマリレベルで無視したり、クォータナリレベルで比較したりします。これは、Strength Level 4 で使用されます。
これらの重みは、照合キー（Collation Key）と呼ばれるバイトシーケンスに変換されます。照合キーは、辞書順にソート可能な形式であり、2つの文字列の照合キーをバイナリ比較することで、UCAに基づく文字列の順序を決定できます。
正規化 (Normalization)
UCAは、照合を行う前に文字列を特定のUnicode正規化形式（通常はNFD: Normalization Form Canonical Decomposition）に変換することを推奨しています。これは、同じ文字でも異なるUnicodeシーケンスで表現される可能性があるため、比較の前に一貫した形式に揃えるためです。例えば、é は単一のコードポイント U+00E9 で表現することも、e (U+0065) と結合文字 ´ (U+0301) の組み合わせで表現することもできます。正規化により、これらが同じものとして扱われます。
可変要素 (Variable Elements) と Alternate Handling
UCAでは、スペース、句読点、記号などを「可変要素」と呼びます。これらの要素の扱いは、Alternate Handling オプションによって制御されます。
- Non-Ignorable (AltNonIgnorable): 可変要素も他の文字と同様にプライマリレベルから比較されます。
- Shifted (AltShifted): 可変要素はプライマリレベルでは無視され、クォータナリレベルで比較されます。これにより、句読点やスペースの有無にかかわらず、主要な単語の順序が維持されます。
- ShiftTrimmed (AltShiftTrimmed): Shifted と同様ですが、末尾の可変要素は無視されます。
- Blanked (AltBlanked): 可変要素はすべてのレベルで無視されます。
variableTop は、どのプライマリ重みまでが可変要素として扱われるかを定義する閾値です。
技術的詳細
本コミットは、exp/locale/collate パッケージに以下の主要な技術的詳細を導入しています。
-
照合キー生成のコアロジック (
keyFromElems,appendPrimary):keyFromElems関数は、照合要素の重み（プライマリ、セカンダリ、ターシャリ、クォータナリ）をバイトシーケンスである照合キーに変換する中心的なロジックを実装しています。- 各レベルの重みは、特定の区切りバイト（
sep= 0）で区切られてキーに追加されます。 - プライマリ重みは、可変長エンコーディング（最大23ビットをサポート）を使用してキーに追加されます。これにより、大きなプライマリ重みも効率的に表現できます。
- セカンダリ重みは、
Backwardsオプションが有効な場合、逆順に追加されます。これはフランス語のアクセントソートなど、特定の言語の要件に対応するためです。 - ターシャリ重みとクォータナリ重みも同様にキーに追加されます。クォータナリ重みは、
AlternateオプションとvariableTopの設定に基づいて処理されます。
-
重み処理 (
processWeights):processWeights関数は、Alternate Handlingの設定（AltShifted,AltShiftTrimmed,AltBlanked）に基づいて、照合要素の重みを調整します。AltShiftedおよびAltShiftTrimmedの場合、variableTop以下のプライマリ重みを持つ要素は、プライマリ重みがクォータナリ重みに移動され、プライマリ、セカンダリ、ターシャリ重みはゼロになります。これにより、これらの要素がプライマリレベルでは無視され、クォータナリレベルで比較されるようになります。AltBlankedの場合、variableTop以下のプライマリ重みを持つ要素は、すべての重みがゼロになります（完全に無視されます）。
-
文字列から照合要素への変換 (
getColElems,getColElemsString,iter):getColElemsおよびgetColElemsString関数は、入力バイトスライスまたは文字列を正規化し、それを照合要素のシーケンスに変換します。iter構造体は、正規化された入力から照合要素を効率的に抽出するためのイテレータを提供します。これは、exp/normパッケージの正規化機能と連携して動作します。- バッファリング機構（
ba、buf）により、入力のチャンク処理と効率的なメモリ管理が行われます。
-
比較機能 (
Compare,CompareString):CompareおよびCompareStringメソッドは、2つの文字列の照合キーを生成し、それらをbytes.Compareを使用してバイナリ比較することで、文字列の順序を決定します。- 現時点では、キーを生成してから比較するというシンプルなアプローチが取られていますが、将来的な最適化（インクリメンタルな比較など）の可能性がコメントで示唆されています。
-
テストフレームワークの拡張:
collate_test.goが新規追加され、processWeights、keyFromElems、GetColElems、Key、Compareなどの主要機能に対する広範なテストケースが追加されています。table_test.goのWeights型がColElemsに変更され、collate.Weightsを直接使用するように修正されています。これにより、テストコードの再利用性と整合性が向上しています。export_test.goには、テスト目的で内部関数や型をエクスポートするためのヘルパー関数が追加されています。
-
不正なルーンのプライマリ値の削減:
colelem.goおよびbuild/colelem.goにおいて、illegalOffsetに続くmaxPrimaryの値がillegalOffset + 2からillegalOffset + 1に変更されています。これは、不正なルーンに対するプライマリ値が1つに集約されたことを意味し、内部的なデータ管理の簡素化に貢献します。
これらの変更により、Go言語の exp/locale/collate パッケージは、UCAに基づく堅牢な文字列照合機能の基盤を確立しています。
コアとなるコードの変更箇所
src/pkg/exp/locale/collate/build/colelem.go
--- a/src/pkg/exp/locale/collate/build/colelem.go
+++ b/src/pkg/exp/locale/collate/build/colelem.go
@@ -153,7 +153,7 @@ const (
rareUnifiedOffset = 0x1FB40
otherOffset = 0x4FB40
illegalOffset = otherOffset + unicode.MaxRune
- maxPrimary = illegalOffset + 2 // there are 2 illegal values.
+ maxPrimary = illegalOffset + 1
)
// implicitPrimary returns the primary weight for the a rune
maxPrimary の定義が変更され、不正なルーンに対するプライマリ値の数が削減されました。
src/pkg/exp/locale/collate/colelem.go
--- a/src/pkg/exp/locale/collate/colelem.go
+++ b/src/pkg/exp/locale/collate/colelem.go
@@ -22,6 +22,7 @@ const (
defaultSecondary = 0x20
defaultTertiary = 0x2
maxTertiary = 0x1F
+ maxQuaternary = 0x1FFFFF // 21 bits.
)
// colElem is a representation of a collation element.
@@ -145,7 +146,8 @@ const (
commonUnifiedOffset = 0xFB40
rareUnifiedOffset = 0x1FB40
otherOffset = 0x4FB40
- maxPrimary = otherOffset + unicode.MaxRune
+ illegalOffset = otherOffset + unicode.MaxRune
+ maxPrimary = illegalOffset + 1
)
// implicitPrimary returns the primary weight for the a rune
maxQuaternary が追加され、illegalOffset と maxPrimary の定義が build/colelem.go と同様に変更されました。
src/pkg/exp/locale/collate/collate.go
--- a/src/pkg/exp/locale/collate/collate.go
+++ b/src/pkg/exp/locale/collate/collate.go
@@ -8,6 +8,7 @@
package collate
import (
+ "bytes"
"exp/norm"
)
@@ -67,6 +68,7 @@ type Collator struct {
// This option exists predominantly to support reverse sorting of accents in French.
Backwards bool
+ // TODO: implement:
// With HiraganaQuaternary enabled, Hiragana codepoints will get lower values
// than all the other non-variable code points. Strength must be greater or
// equal to Quaternary for this to take effect.
@@ -122,25 +124,46 @@ func (b *Buffer) ResetKeys() {
// Compare returns an integer comparing the two byte slices.
// The result will be 0 if a==b, -1 if a < b, and +1 if a > b.
+// Compare calls ResetKeys, thereby invalidating keys
+// previously generated using Key or KeyFromString using buf.
func (c *Collator) Compare(buf *Buffer, a, b []byte) int {
- // TODO: implement
- return 0
+ // TODO: for now we simply compute keys and compare. Once we
+ // have good benchmarks, move to an implementation that works
+ // incrementally for the majority of cases.
+ // - Benchmark with long strings that only vary in modifiers.
+ buf.ResetKeys()
+ ka := c.Key(buf, a)
+ kb := c.Key(buf, b)
+ defer buf.ResetKeys()
+ return bytes.Compare(ka, kb)
}
// CompareString returns an integer comparing the two strings.
// The result will be 0 if a==b, -1 if a < b, and +1 if a > b.
+// CompareString calls ResetKeys, thereby invalidating keys
+// previously generated using Key or KeyFromString using buf.
func (c *Collator) CompareString(buf *Buffer, a, b string) int {
- // TODO: implement
- return 0
+ buf.ResetKeys()
+ ka := c.KeyFromString(buf, a)
+ kb := c.KeyFromString(buf, b)
+ defer buf.ResetKeys()
+ return bytes.Compare(ka, kb)
+}
+
+func (c *Collator) Prefix(buf *Buffer, s, prefix []byte) int {
+ // iterate over s, track bytes consumed.
+ return 0
}
// Key returns the collation key for str.
// Passing the buffer buf may avoid memory allocations.
-// The returned slice will point to an allocation in Buffer and will retain
+// The returned slice will point to an allocation in Buffer and will remain
// valid until the next call to buf.ResetKeys().
func (c *Collator) Key(buf *Buffer, str []byte) []byte {
- // TODO: implement
- return nil
+ // See http://www.unicode.org/reports/tr10/#Main_Algorithm for more details.
+ buf.init()
+ c.getColElems(buf, str)
+ return c.key(buf, buf.ce)
}
// KeyFromString returns the collation key for str.
@@ -148,6 +171,175 @@ func (c *Collator) Key(buf *Buffer, str []byte) []byte {\
// The returned slice will point to an allocation in Buffer and will retain
// valid until the next call to buf.ResetKeys().
func (c *Collator) KeyFromString(buf *Buffer, str string) []byte {
- // TODO: implement
- return nil
+ // See http://www.unicode.org/reports/tr10/#Main_Algorithm for more details.
+ buf.init()
+ c.getColElemsString(buf, str)
+ return c.key(buf, buf.ce)
+}
+
+func (c *Collator) key(buf *Buffer, w []weights) []byte {
+ processWeights(c.Alternate, c.variableTop, w)
+ kn := len(buf.key)
+ c.keyFromElems(buf, w)
+ return buf.key[kn:]
+}
+
+func (c *Collator) getColElems(buf *Buffer, str []byte) {
+ i := c.iter()
+ i.src.SetInput(c.f, str)
+ for !i.done() {
+ buf.ce = i.next(buf.ce)
+ }
+}
+
+func (c *Collator) getColElemsString(buf *Buffer, str string) {
+ i := c.iter()
+ i.src.SetInputString(c.f, str)
+ for !i.done() {
+ buf.ce = i.next(buf.ce)
+ }
+}
+
+type iter struct {
+ src norm.Iter
+ ba [1024]byte
+ buf []byte
+ t *table
+ p int
+ minBufSize int
+ _done, eof bool
+}
+
+func (c *Collator) iter() iter {
+ i := iter{t: c.t, minBufSize: c.t.maxContractLen}
+ i.buf = i.ba[:0]
+ return i
+}
+
+func (i *iter) done() bool {
+ return i._done
+}
+
+func (i *iter) next(ce []weights) []weights {
+ if !i.eof && len(i.buf)-i.p < i.minBufSize {
+ // replenish buffer
+ n := copy(i.buf, i.buf[i.p:])
+ n += i.src.Next(i.buf[n:cap(i.buf)])
+ i.buf = i.buf[:n]
+ i.p = 0
+ i.eof = i.src.Done()
+ }
+ if i.p == len(i.buf) {
+ i._done = true
+ return ce
+ }
+ ce, sz := i.t.appendNext(ce, i.buf[i.p:])
+ i.p += sz
+ return ce
+}
+
+func appendPrimary(key []byte, p uint32) []byte {
+ // Convert to variable length encoding; supports up to 23 bits.
+ if p <= 0x7FFF {
+ key = append(key, uint8(p>>8), uint8(p))
+ } else {
+ key = append(key, uint8(p>>16)|0x80, uint8(p>>8), uint8(p))
+ }
+ return key
+}
+
+// keyFromElems converts the weights ws to a compact sequence of bytes.
+// The result will be appended to the byte buffer in buf.
+func (c *Collator) keyFromElems(buf *Buffer, ws []weights) {
+ for _, v := range ws {
+ if w := v.primary; w > 0 {
+ buf.key = appendPrimary(buf.key, w)
+ }
+ }
+ if Secondary <= c.Strength {
+ buf.key = append(buf.key, 0, 0)
+ // TODO: we can use one 0 if we can guarantee that all non-zero weights are > 0xFF.
+ if !c.Backwards {
+ for _, v := range ws {
+ if w := v.secondary; w > 0 {
+ buf.key = append(buf.key, uint8(w>>8), uint8(w))
+ }
+ }
+ } else {
+ for i := len(ws) - 1; i >= 0; i-- {
+ if w := ws[i].secondary; w > 0 {
+ buf.key = append(buf.key, uint8(w>>8), uint8(w))
+ }
+ }
+ }
+ } else if c.CaseLevel {
+ buf.key = append(buf.key, 0, 0)
+ }
+ if Tertiary <= c.Strength || c.CaseLevel {
+ buf.key = append(buf.key, 0, 0)
+ for _, v := range ws {
+ if w := v.tertiary; w > 0 {
+ buf.key = append(buf.key, w)
+ }
+ }
+ // Derive the quaternary weights from the options and other levels.
+ // Note that we represent maxQuaternary as 0xFF. The first byte of the
+ // representation of a a primary weight is always smaller than 0xFF,
+ // so using this single byte value will compare correctly.
+ if Quaternary <= c.Strength {
+ if c.Alternate == AltShiftTrimmed {
+ lastNonFFFF := len(buf.key)
+ buf.key = append(buf.key, 0)
+ for _, v := range ws {
+ if w := v.quaternary; w == maxQuaternary {
+ buf.key = append(buf.key, 0xFF)
+ } else if w > 0 {
+ buf.key = appendPrimary(buf.key, w)
+ lastNonFFFF = len(buf.key)
+ }
+ }
+ buf.key = buf.key[:lastNonFFFF]
+ } else {
+ buf.key = append(buf.key, 0)
+ for _, v := range ws {
+ if w := v.quaternary; w == maxQuaternary {
+ buf.key = append(buf.key, 0xFF)
+ } else if w > 0 {
+ buf.key = appendPrimary(buf.key, w)
+ }
+ }
+ }
+ }
+ }
+}
+
+func processWeights(vw AlternateHandling, top uint32, wa []weights) {
+ ignore := false
+ switch vw {
+ case AltShifted, AltShiftTrimmed:
+ for i := range wa {
+ if p := wa[i].primary; p <= top && p != 0 {
+ wa[i] = weights{quaternary: p}
+ ignore = true
+ } else if p == 0 {
+ if ignore {
+ wa[i] = weights{}
+ } else if wa[i].tertiary != 0 {
+ wa[i].quaternary = maxQuaternary
+ }
+ } else {
+ wa[i].quaternary = maxQuaternary
+ ignore = false
+ }
+ }
+ case AltBlanked:
+ for i := range wa {
+ if p := wa[i].primary; p <= top && (ignore || p != 0) {
+ wa[i] = weights{}
+ ignore = true
+ } else {
+ ignore = false
+ }
+ }
+ }
}
このファイルは、照合機能の核心部分であり、Compare, CompareString, Key, KeyFromString メソッドの実装、照合要素の処理、照合キーの生成ロジック、および重み調整ロジックが追加されています。
src/pkg/exp/locale/collate/collate_test.go (新規ファイル)
--- /dev/null
+++ b/src/pkg/exp/locale/collate/collate_test.go
@@ -0,0 +1,422 @@
+// 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 collate_test
+
+import (
+ "bytes"
+ "exp/locale/collate"
+ "testing"
+)
+
+type weightsTest struct {
+ opt opts
+ in, out ColElems
+}
+
+type opts struct {
+ lev int
+ alt collate.AlternateHandling
+ top int
+
+ backwards bool
+ caseLevel bool
+}
+
+func (o opts) level() collate.Level {
+ if o.lev == 0 {
+ return collate.Quaternary
+ }
+ return collate.Level(o.lev - 1)
+}
+
+func (o opts) collator() *collate.Collator {
+ c := &collate.Collator{
+ Strength: o.level(),
+ Alternate: o.alt,
+ Backwards: o.backwards,
+ CaseLevel: o.caseLevel,
+ }
+ collate.SetTop(c, o.top)
+ return c
+}
+
+const (
+ maxQ = 0x1FFFFF
+)
+
+func wpq(p, q int) collate.Weights {
+ return collate.W(p, defaults.Secondary, defaults.Tertiary, q)
+}
+
+func wsq(s, q int) collate.Weights {
+ return collate.W(0, s, defaults.Tertiary, q)
+}
+
+func wq(q int) collate.Weights {
+ return collate.W(0, 0, 0, q)
+}
+
+var zero = w(0, 0, 0, 0)
+
+var processTests = []weightsTest{
+ // Shifted
+ { // simple sequence of non-variables
+ opt: opts{alt: collate.AltShifted, top: 100},
+ in: ColElems{w(200), w(300), w(400)},
+ out: ColElems{wpq(200, maxQ), wpq(300, maxQ), wpq(400, maxQ)},
+ },
+ { // first is a variable
+ opt: opts{alt: collate.AltShifted, top: 250},
+ in: ColElems{w(200), w(300), w(400)},
+ out: ColElems{wq(200), wpq(300, maxQ), wpq(400, maxQ)},
+ },
+ { // all but first are variable
+ opt: opts{alt: collate.AltShifted, top: 999},
+ in: ColElems{w(1000), w(200), w(300), w(400)},
+ out: ColElems{wpq(1000, maxQ), wq(200), wq(300), wq(400)},
+ },
+ { // first is a modifier
+ opt: opts{alt: collate.AltShifted, top: 999},
+ in: ColElems{w(0, 10), w(1000)},
+ out: ColElems{wsq(10, maxQ), wpq(1000, maxQ)},
+ },
+ { // primary ignorables
+ opt: opts{alt: collate.AltShifted, top: 250},
+ in: ColElems{w(200), w(0, 10), w(300), w(0, 15), w(400)},
+ out: ColElems{wq(200), zero, wpq(300, maxQ), wsq(15, maxQ), wpq(400, maxQ)},
+ },
+ { // secondary ignorables
+ opt: opts{alt: collate.AltShifted, top: 250},
+ in: ColElems{w(200), w(0, 0, 10), w(300), w(0, 0, 15), w(400)},
+ out: ColElems{wq(200), zero, wpq(300, maxQ), w(0, 0, 15, maxQ), wpq(400, maxQ)},
+ },
+ { // tertiary ignorables, no change
+ opt: opts{alt: collate.AltShifted, top: 250},
+ in: ColElems{w(200), zero, w(300), zero, w(400)},
+ out: ColElems{wq(200), zero, wpq(300, maxQ), zero, wpq(400, maxQ)},
+ },
+
+ // ShiftTrimmed (same as Shifted)
+ { // simple sequence of non-variables
+ opt: opts{alt: collate.AltShiftTrimmed, top: 100},
+ in: ColElems{w(200), w(300), w(400)},
+ out: ColElems{wpq(200, maxQ), wpq(300, maxQ), wpq(400, maxQ)},
+ },
+ { // first is a variable
+ opt: opts{alt: collate.AltShiftTrimmed, top: 250},
+ in: ColElems{w(200), w(300), w(400)},
+ out: ColElems{wq(200), wpq(300, maxQ), wpq(400, maxQ)},
+ },
+ { // all but first are variable
+ opt: opts{alt: collate.AltShiftTrimmed, top: 999},
+ in: ColElems{w(1000), w(200), w(300), w(400)},
+ out: ColElems{wpq(1000, maxQ), wq(200), wq(300), wq(400)},
+ },
+ { // first is a modifier
+ opt: opts{alt: collate.AltShiftTrimmed, top: 999},
+ in: ColElems{w(0, 10), w(1000)},
+ out: ColElems{wsq(10, maxQ), wpq(1000, maxQ)},
+ },
+ { // primary ignorables
+ opt: opts{alt: collate.AltShiftTrimmed, top: 250},
+ in: ColElems{w(200), w(0, 10), w(300), w(0, 15), w(400)},
+ out: ColElems{wq(200), zero, wpq(300, maxQ), wsq(15, maxQ), wpq(400, maxQ)},
+ },
+ { // secondary ignorables
+ opt: opts{alt: collate.AltShiftTrimmed, top: 250},
+ in: ColElems{w(200), w(0, 0, 10), w(300), w(0, 0, 15), w(400)},
+ out: ColElems{wq(200), zero, wpq(300, maxQ), w(0, 0, 15, maxQ), wpq(400, maxQ)},
+ },
+ { // tertiary ignorables, no change
+ opt: opts{alt: collate.AltShiftTrimmed, top: 250},
+ in: ColElems{w(200), zero, w(300), zero, w(400)},
+ out: ColElems{wq(200), zero, wpq(300, maxQ), zero, wpq(400, maxQ)},
+ },
+
+ // Blanked
+ { // simple sequence of non-variables
+ opt: opts{alt: collate.AltBlanked, top: 100},
+ in: ColElems{w(200), w(300), w(400)},
+ out: ColElems{w(200), w(300), w(400)},
+ },
+ { // first is a variable
+ opt: opts{alt: collate.AltBlanked, top: 250},
+ in: ColElems{w(200), w(300), w(400)},
+ out: ColElems{zero, w(300), w(400)},
+ },
+ { // all but first are variable
+ opt: opts{alt: collate.AltBlanked, top: 999},
+ in: ColElems{w(1000), w(200), w(300), w(400)},
+ out: ColElems{w(1000), zero, zero, zero},
+ },
+ { // first is a modifier
+ opt: opts{alt: collate.AltBlanked, top: 999},
+ in: ColElems{w(0, 10), w(1000)},
+ out: ColElems{w(0, 10), w(1000)},
+ },
+ { // primary ignorables
+ opt: opts{alt: collate.AltBlanked, top: 250},
+ in: ColElems{w(200), w(0, 10), w(300), w(0, 15), w(400)},
+ out: ColElems{zero, zero, w(300), w(0, 15), w(400)},
+ },
+ { // secondary ignorables
+ opt: opts{alt: collate.AltBlanked, top: 250},
+ in: ColElems{w(200), w(0, 0, 10), w(300), w(0, 0, 15), w(400)},
+ out: ColElems{zero, zero, w(300), w(0, 0, 15), w(400)},
+ },
+ { // tertiary ignorables, no change
+ opt: opts{alt: collate.AltBlanked, top: 250},
+ in: ColElems{w(200), zero, w(300), zero, w(400)},
+ out: ColElems{zero, zero, w(300), zero, w(400)},
+ },
+
+ // Non-ignorable: input is always equal to output.
+ { // all but first are variable
+ opt: opts{alt: collate.AltNonIgnorable, top: 999},
+ in: ColElems{w(1000), w(200), w(300), w(400)},
+ out: ColElems{w(1000), w(200), w(300), w(400)},
+ },
+ { // primary ignorables
+ opt: opts{alt: collate.AltNonIgnorable, top: 250},
+ in: ColElems{w(200), w(0, 10), w(300), w(0, 15), w(400)},
+ out: ColElems{w(200), w(0, 10), w(300), w(0, 15), w(400)},
+ },
+ { // secondary ignorables
+ opt: opts{alt: collate.AltNonIgnorable, top: 250},
+ in: ColElems{w(200), w(0, 0, 10), w(300), w(0, 0, 15), w(400)},
+ out: ColElems{w(200), w(0, 0, 10), w(300), w(0, 0, 15), w(400)},
+ },
+ { // tertiary ignorables, no change
+ opt: opts{alt: collate.AltNonIgnorable, top: 250},
+ in: ColElems{w(200), zero, w(300), zero, w(400)},
+ out: ColElems{w(200), zero, w(300), zero, w(400)},
+ },
+}
+
+func TestProcessWeights(t *testing.T) {
+ for i, tt := range processTests {
+ res := collate.ProcessWeights(tt.opt.alt, tt.opt.top, tt.in)
+ if len(res) != len(tt.out) {
+ t.Errorf("%d: len(ws) was %d; want %d (%v should be %v)", i, len(res), len(tt.out), res, tt.out)
+ continue
+ }
+ for j, w := range res {
+ if w != tt.out[j] {
+ t.Errorf("%d: Weights %d was %v; want %v", i, j, w, tt.out[j])
+ }
+ }
+ }
+}
+
+type keyFromElemTest struct {
+ opt opts
+ in ColElems
+ out []byte
+}
+
+var defS = byte(defaults.Secondary)
+var defT = byte(defaults.Tertiary)
+
+const sep = 0 // separator byte
+
+var keyFromElemTests = []keyFromElemTest{
+ { // simple primary and secondary weights.
+ opts{},
+ ColElems{w(0x200), w(0x7FFF), w(0, 0x30), w(0x100)},
+ []byte{0x2, 0, 0x7F, 0xFF, 0x1, 0x00, // primary
+ sep, sep, 0, defS, 0, defS, 0, 0x30, 0, defS, // secondary
+ sep, sep, defT, defT, defT, defT, // tertiary
+ sep, 0xFF, 0xFF, 0xFF, 0xFF, // quaternary
+ },
+ },
+ { // same as first, but with zero element that need to be removed
+ opts{},
+ ColElems{w(0x200), zero, w(0x7FFF), w(0, 0x30), zero, w(0x100)},
+ []byte{0x2, 0, 0x7F, 0xFF, 0x1, 0x00, // primary
+ sep, sep, 0, defS, 0, defS, 0, 0x30, 0, defS, // secondary
+ sep, sep, defT, defT, defT, defT, // tertiary
+ sep, 0xFF, 0xFF, 0xFF, 0xFF, // quaternary
+ },
+ },
+ { // same as first, with large primary values
+ opts{},
+ ColElems{w(0x200), w(0x8000), w(0, 0x30), w(0x12345)},
+ []byte{0x2, 0, 0x80, 0x80, 0x00, 0x81, 0x23, 0x45, // primary
+ sep, sep, 0, defS, 0, defS, 0, 0x30, 0, defS, // secondary
+ sep, sep, defT, defT, defT, defT, // tertiary
+ sep, 0xFF, 0xFF, 0xFF, 0xFF, // quaternary
+ },
+ },
+ { // same as first, but with the secondary level backwards
+ opts{backwards: true},
+ ColElems{w(0x200), w(0x7FFF), w(0, 0x30), w(0x100)},
+ []byte{0x2, 0, 0x7F, 0xFF, 0x1, 0x00, // primary
+ sep, sep, 0, defS, 0, 0x30, 0, defS, 0, defS, // secondary
+ sep, sep, defT, defT, defT, defT, // tertiary
+ sep, 0xFF, 0xFF, 0xFF, 0xFF, // quaternary
+ },
+ },
+ { // same as first, ignoring quaternary level
+ opts{lev: 3},
+ ColElems{w(0x200), zero, w(0x7FFF), w(0, 0x30), zero, w(0x100)},
+ []byte{0x2, 0, 0x7F, 0xFF, 0x1, 0x00, // primary
+ sep, sep, 0, defS, 0, defS, 0, 0x30, 0, defS, // secondary
+ sep, sep, defT, defT, defT, defT, // tertiary
+ },
+ },
+ { // same as first, ignoring tertiary level
+ opts{lev: 2},
+ ColElems{w(0x200), zero, w(0x7FFF), w(0, 0x30), zero, w(0x100)},
+ []byte{0x2, 0, 0x7F, 0xFF, 0x1, 0x00, // primary
+ sep, sep, 0, defS, 0, defS, 0, 0x30, 0, defS, // secondary
+ },
+ },
+ { // same as first, ignoring secondary level
+ opts{lev: 1},
+ ColElems{w(0x200), zero, w(0x7FFF), w(0, 0x30), zero, w(0x100)},
+ []byte{0x2, 0, 0x7F, 0xFF, 0x1, 0x00},
+ },
+ { // simple primary and secondary weights.
+ opts{alt: collate.AltShiftTrimmed, top: 0x250},
+ ColElems{w(0x300), w(0x200), w(0x7FFF), w(0, 0x30), w(0x800)},
+ []byte{0x3, 0, 0x7F, 0xFF, 0x8, 0x00, // primary
+ sep, sep, 0, defS, 0, defS, 0, 0x30, 0, defS, // secondary
+ sep, sep, defT, defT, defT, defT, // tertiary
+ sep, 0xFF, 0x2, 0, // quaternary
+ },
+ },
+ { // as first, primary with case level enabled
+ opts{lev: 1, caseLevel: true},
+ ColElems{w(0x200), w(0x7FFF), w(0, 0x30), w(0x100)},
+ []byte{0x2, 0, 0x7F, 0xFF, 0x1, 0x00, // primary
+ sep, sep, // secondary
+ sep, sep, defT, defT, defT, defT, // tertiary
+ },
+ },
+}
+
+func TestKeyFromElems(t *testing.T) {
+ buf := collate.Buffer{}
+ for i, tt := range keyFromElemTests {
+ buf.ResetKeys()
+ ws := collate.ProcessWeights(tt.opt.alt, tt.opt.top, tt.in)
+ res := collate.KeyFromElems(tt.opt.collator(), &buf, ws)
+ if len(res) != len(tt.out) {
+ t.Errorf("%d: len(ws) was %d; want %d (%X should be %X)", i, len(res), len(tt.out), res, tt.out)
+ }
+ n := len(res)
+ if len(tt.out) < n {
+ n = len(tt.out)
+ }
+ for j, c := range res[:n] {
+ if c != tt.out[j] {
+ t.Errorf("%d: byte %d was %X; want %X", i, j, c, tt.out[j])
+ }
+ }
+ }
+}
+
+func TestGetColElems(t *testing.T) {
+ for i, tt := range appendNextTests {
+ c, err := makeTable(tt.in)
+ if err != nil {
+ // error is reported in TestAppendNext
+ continue
+ }
+ buf := collate.Buffer{}
+ // Create one large test per table
+ str := make([]byte, 0, 4000)
+ out := ColElems{}
+ for len(str) < 3000 {
+ for _, chk := range tt.chk {
+ str = append(str, chk.in[:chk.n]...)
+ out = append(out, chk.out...)
+ }
+ }
+ for j, chk := range append(tt.chk, check{string(str), len(str), out}) {
+ ws := collate.GetColElems(c, &buf, []byte(chk.in)[:chk.n])
+ if len(ws) != len(chk.out) {
+ t.Errorf("%d:%d: len(ws) was %d; want %d", i, j, len(ws), len(chk.out))
+ continue
+ }
+ cnt := 0
+ for k, w := range ws {
+ if w != chk.out[k] {
+ t.Errorf("%d:%d: Weights %d was %v; want %v", i, j, k, w, chk.out[k])
+ cnt++
+ }
+ if cnt > 10 {
+ break
+ }
+ }
+ }
+ }
+}
+
+type keyTest struct {
+ in string
+ out []byte
+}
+
+var keyTests = []keyTest{
+ {"abc",
+ []byte{0, 100, 0, 200, 1, 44, 0, 0, 0, 32, 0, 32, 0, 32, 0, 0, 2, 2, 2, 0, 255, 255, 255},
+ },
+ {"a\u0301",
+ []byte{0, 102, 0, 0, 0, 32, 0, 0, 2, 0, 255},
+ },
+ {"aaaaa",
+ []byte{0, 100, 0, 100, 0, 100, 0, 100, 0, 100, 0, 0,
+ 0, 32, 0, 32, 0, 32, 0, 32, 0, 32, 0, 0,
+ 2, 2, 2, 2, 2, 0,
+ 255, 255, 255, 255, 255,
+ },
+ },
+}
+
+func TestKey(t *testing.T) {
+ c, _ := makeTable(appendNextTests[4].in)
+ buf := collate.Buffer{}
+ keys1 := [][]byte{}
+ keys2 := [][]byte{}
+ for _, tt := range keyTests {
+ keys1 = append(keys1, c.Key(&buf, []byte(tt.in)))
+ keys2 = append(keys2, c.KeyFromString(&buf, tt.in))
+ }
+ // Separate generation from testing to ensure buffers are not overwritten.
+ for i, tt := range keyTests {
+ if bytes.Compare(keys1[i], tt.out) != 0 {
+ t.Errorf("%d: Key(%q) = %d; want %d", i, tt.in, keys1[i], tt.out)
+ }
+ if bytes.Compare(keys2[i], tt.out) != 0 {
+ t.Errorf("%d: KeyFromString(%q) = %d; want %d", i, tt.in, keys2[i], tt.out)
+ }
+ }
+}
+
+type compareTest struct {
+ a, b string
+ res int // comparison result
+}
+
+var compareTests = []compareTest{
+ {"a\u0301", "a", 1},
+ {"a", "a\u0301", -1},
+ {"a\u0301", "a\u0301", 0},
+ {"a", "a", 0},
+}
+
+func TestCompare(t *testing.T) {
+ c, _ := makeTable(appendNextTests[4].in)
+ buf := collate.Buffer{}
+ for i, tt := range compareTests {
+ if res := c.Compare(&buf, []byte(tt.a), []byte(tt.b)); res != tt.res {
+ t.Errorf("%d: Compare(%q, %q) == %d; want %d", i, tt.a, tt.b, res, tt.res)
+ }
+ if res := c.CompareString(&buf, tt.a, tt.b); tt.res != res {
+ t.Errorf("%d: CompareString(%q, %q) == %d; want %d", i, tt.a, tt.b, res, tt.res)
+ }
+ }
+}
照合機能のテストケースが多数追加されています。processWeights、keyFromElems、GetColElems、Key、Compare、CompareString など、主要な機能の動作が検証されています。
src/pkg/exp/locale/collate/export_test.go
--- a/src/pkg/exp/locale/collate/export_test.go
+++ b/src/pkg/exp/locale/collate/export_test.go
@@ -6,24 +6,30 @@ package collate
// Export for testing.
-import "fmt"
+import (
+ "exp/norm"
+ "fmt"
+)
type Weights struct {
- Primary, Secondary, Tertiary int
+ Primary, Secondary, Tertiary, Quaternary int
}
func W(ce ...int) Weights {
- w := Weights{ce[0], defaultSecondary, defaultTertiary}
+ w := Weights{ce[0], defaultSecondary, defaultTertiary, 0}
if len(ce) > 1 {
w.Secondary = ce[1]
}
if len(ce) > 2 {
w.Tertiary = ce[2]
}
+ if len(ce) > 3 {
+ w.Quaternary = ce[3]
+ }
return w
}
func (w Weights) String() string {
- return fmt.Sprintf("[%d.%d.%d]", w.Primary, w.Secondary, w.Tertiary)
+ return fmt.Sprintf("[%d.%d.%d.%d]", w.Primary, w.Secondary, w.Tertiary, w.Quaternary)
}
type Table struct {
@@ -35,15 +41,52 @@ func GetTable(c *Collator) *Table {
return &Table{c.t, nil}
}
-func convertWeights(ws []weights) []Weights {
+func convertToWeights(ws []weights) []Weights {
out := make([]Weights, len(ws))
for i, w := range ws {
- out[i] = Weights{int(w.primary), int(w.secondary), int(w.tertiary)}
+ out[i] = Weights{int(w.primary), int(w.secondary), int(w.tertiary), int(w.quaternary)}
}
return out
}
+func convertFromWeights(ws []Weights) []weights {
+ out := make([]weights, len(ws))
+ for i, w := range ws {
+ out[i] = weights{uint32(w.Primary), uint16(w.Secondary), uint8(w.Tertiary), uint32(w.Quaternary)}
+ }
+ return out
+}
+
func (t *Table) AppendNext(s []byte) ([]Weights, int) {
w, n := t.t.appendNext(nil, s)
- return convertWeights(w), n
+ return convertToWeights(w), n
+}
+
+func SetTop(c *Collator, top int) {
+ c.variableTop = uint32(top)
+}
+
+func InitCollator(c *Collator) {
+ c.Strength = Quaternary
+ c.f = norm.NFD
+ c.t.maxContractLen = 30
+}
+
+func GetColElems(c *Collator, buf *Buffer, str []byte) []Weights {
+ buf.ResetKeys()
+ InitCollator(c)
+ c.getColElems(buf, str)
+ return convertToWeights(buf.ce)
+}
+
+func ProcessWeights(h AlternateHandling, top int, w []Weights) []Weights {
+ in := convertFromWeights(w)
+ processWeights(h, uint32(top), in)
+ return convertToWeights(in)
+}
+
+func KeyFromElems(c *Collator, buf *Buffer, w []Weights) []byte {
+ k := len(buf.key)
+ c.keyFromElems(buf, convertFromWeights(w))
+ return buf.key[k:]
}
テストのために内部構造をエクスポートするヘルパー関数が追加・修正されています。特に Weights 構造体に Quaternary フィールドが追加され、W 関数や String メソッドもそれに対応するように変更されています。また、convertToWeights と convertFromWeights が追加され、内部の weights 型とテスト用の Weights 型の変換を容易にしています。
src/pkg/exp/locale/collate/table_test.go
--- a/src/pkg/exp/locale/collate/table_test.go
+++ b/src/pkg/exp/locale/collate/table_test.go
@@ -11,9 +11,7 @@ import (
"testing"
)
-type Weights struct {
- collate.Weights
-}
+type ColElems []collate.Weights
type input struct {
str string
@@ -23,7 +21,7 @@ type input struct {
type check struct {\n \tin string\n \tn int\n-\tout []Weights\n+\tout ColElems\n }\n \n type tableTest struct {\n@@ -31,8 +29,8 @@ type tableTest struct {\n \tchk []check\n }\n \n-func w(ce ...int) Weights {\n-\treturn Weights{collate.W(ce...)}\n+func w(ce ...int) collate.Weights {\n+\treturn collate.W(ce...)\n }\n \n var defaults = w(0)\n@@ -46,7 +44,11 @@ func makeTable(in []input) (*collate.Collator, error) {\n \tfor _, r := range in {\n \t\tb.Add([]rune(r.str), r.ces)\n \t}\n-\treturn b.Build(\"\")\n+\tc, err := b.Build(\"\")\n+\tif err == nil {\n+\t\tcollate.InitCollator(c)\n+\t}\n+\treturn c, err\n }\n \n // modSeq holds a seqeunce of modifiers in increasing order of CCC long enough\n@@ -60,8 +62,8 @@ var modSeq = []rune{\n }\n \n var mods []input\n-var modW = func() []Weights {\n-\tws := []Weights{}\n+var modW = func() ColElems {\n+\tws := ColElems{}\n \tfor _, r := range modSeq {\n \t\trune := norm.NFC.PropertiesString(string(r))\n \t\tws = append(ws, w(0, int(rune.CCC())))\n@@ -79,14 +81,14 @@ var appendNextTests = []tableTest{\n \t\t\t{\"ß\", [][]int{{120}}},\n \t\t},\n \t\t[]check{\n-\t\t\t{\"a\", 1, []Weights{w(100)}},\n-\t\t\t{\"b\", 1, []Weights{w(105)}},\n-\t\t\t{\"c\", 1, []Weights{w(110)}},\n-\t\t\t{\"d\", 1, []Weights{w(0x4FBA4)}},\n-\t\t\t{\"ab\", 1, []Weights{w(100)}},\n-\t\t\t{\"bc\", 1, []Weights{w(105)}},\n-\t\t\t{\"dd\", 1, []Weights{w(0x4FBA4)}},\n-\t\t\t{\"ß\", 2, []Weights{w(120)}},\n+\t\t\t{\"a\", 1, ColElems{w(100)}},\n+\t\t\t{\"b\", 1, ColElems{w(105)}},\n+\t\t\t{\"c\", 1, ColElems{w(110)}},\n+\t\t\t{\"d\", 1, ColElems{w(0x4FBA4)}},\n+\t\t\t{\"ab\", 1, ColElems{w(100)}},\n+\t\t\t{\"bc\", 1, ColElems{w(105)}},\n+\t\t\t{\"dd\", 1, ColElems{w(0x4FBA4)}},\n+\t\t\t{\"ß\", 2, ColElems{w(120)}},\n \t\t},\n \t},\n \t{ // test expansion\n@@ -97,10 +99,10 @@ var appendNextTests = []tableTest{\n \t\t\t{\"W\", [][]int{{100}, {0, 25}, {100}, {0, 25}}},\n \t\t},\n \t\t[]check{\n-\t\t\t{\"u\", 1, []Weights{w(100)}},\n-\t\t\t{\"U\", 1, []Weights{w(100), w(0, 25)}},\n-\t\t\t{\"w\", 1, []Weights{w(100), w(100)}},\n-\t\t\t{\"W\", 1, []Weights{w(100), w(0, 25), w(100), w(0, 25)}},\n+\t\t\t{\"u\", 1, ColElems{w(100)}},\n+\t\t\t{\"U\", 1, ColElems{w(100), w(0, 25)}},\n+\t\t\t{\"w\", 1, ColElems{w(100), w(100)}},\n+\t\t\t{\"W\", 1, ColElems{w(100), w(0, 25), w(100), w(0, 25)}},\n \t\t},\n \t},\n \t{ // test decompose\n@@ -111,7 +113,7 @@ var appendNextTests = []tableTest{\n \t\t\t{\"\\u01C5\", [][]int{pt(104, 9), pt(130, 4), {0, 40, 0x1F}}}, // Dž = D+z+caron\n \t\t},\n \t\t[]check{\n-\t\t\t{\"\\u01C5\", 2, []Weights{w(pt(104, 9)...), w(pt(130, 4)...), w(0, 40, 0x1F)}},\n+\t\t\t{\"\\u01C5\", 2, ColElems{w(pt(104, 9)...), w(pt(130, 4)...), w(0, 40, 0x1F)}},\n \t\t},\n \t},\n \t{ // test basic contraction\n@@ -125,16 +127,16 @@ var appendNextTests = []tableTest{\n \t\t\t{\"d\", [][]int{{400}}},\n \t\t},\n \t\t[]check{\n-\t\t\t{\"a\", 1, []Weights{w(100)}},\n-\t\t\t{\"aa\", 1, []Weights{w(100)}},\n-\t\t\t{\"aac\", 1, []Weights{w(100)}},\n-\t\t\t{\"ab\", 2, []Weights{w(101)}},\n-\t\t\t{\"abb\", 2, []Weights{w(101)}},\n-\t\t\t{\"aab\", 3, []Weights{w(101), w(101)}},\n-\t\t\t{\"aaba\", 3, []Weights{w(101), w(101)}},\n-\t\t\t{\"abc\", 3, []Weights{w(102)}},\n-\t\t\t{\"abcd\", 3, []Weights{w(102)}},\n-\t\t\t{\"d\", 1, []Weights{w(400)}},\n+\t\t\t{\"a\", 1, ColElems{w(100)}},\n+\t\t\t{\"aa\", 1, ColElems{w(100)}},\n+\t\t\t{\"aac\", 1, ColElems{w(100)}},\n+\t\t\t{\"d\", 1, ColElems{w(400)}},\n+\t\t\t{\"ab\", 2, ColElems{w(101)}},\n+\t\t\t{\"abb\", 2, ColElems{w(101)}},\n+\t\t\t{\"aab\", 3, ColElems{w(101), w(101)}},\n+\t\t\t{\"aaba\", 3, ColElems{w(101), w(101)}},\n+\t\t\t{\"abc\", 3, ColElems{w(102)}},\n+\t\t\t{\"abcd\", 3, ColElems{w(102)}},\n \t\t},\n \t},\n \t{ // test discontinuous contraction\n@@ -177,75 +179,75 @@ var appendNextTests = []tableTest{\n \t\t\t{\"\\u302F\\u18A9\", [][]int{{0, 130}}},\n \t\t}...),\n \t\t[]check{\n-\t\t\t{\"ab\", 1, []Weights{w(100)}}, // closing segment\n-\t\t\t{\"a\\u0316\\u0300b\", 5, []Weights{w(101), w(0, 220)}}, // closing segment\n-\t\t\t{\"a\\u0316\\u0300\", 5, []Weights{w(101), w(0, 220)}}, // no closing segment\n-\t\t\t{\"a\\u0316\\u0300\\u035Cb\", 5, []Weights{w(101), w(0, 220)}}, // completes before segment end\n-\t\t\t{\"a\\u0316\\u0300\\u035C\", 5, []Weights{w(101), w(0, 220)}}, // completes before segment end\n+\t\t\t{\"ab\", 1, ColElems{w(100)}}, // closing segment\n+\t\t\t{\"a\\u0316\\u0300b\", 5, ColElems{w(101), w(0, 220)}}, // closing segment\n+\t\t\t{\"a\\u0316\\u0300\", 5, ColElems{w(101), w(0, 220)}}, // no closing segment\n+\t\t\t{\"a\\u0316\\u0300\\u035Cb\", 5, ColElems{w(101), w(0, 220)}}, // completes before segment end\n+\t\t\t{\"a\\u0316\\u0300\\u035C\", 5, ColElems{w(101), w(0, 220)}}, // completes before segment end\n \n-\t\t\t{\"a\\u0316\\u0301b\", 5, []Weights{w(102), w(0, 220)}}, // closing segment\n-\t\t\t{\"a\\u0316\\u0301\", 5, []Weights{w(102), w(0, 220)}}, // no closing segment\n-\t\t\t{\"a\\u0316\\u0301\\u035Cb\", 5, []Weights{w(102), w(0, 220)}}, // completes before segment end\n-\t\t\t{\"a\\u0316\\u0301\\u035C\", 5, []Weights{w(102), w(0, 220)}}, // completes before segment end\n+\t\t\t{\"a\\u0316\\u0301b\", 5, ColElems{w(102), w(0, 220)}}, // closing segment\n+\t\t\t{\"a\\u0316\\u0301\", 5, ColElems{w(102), w(0, 220)}}, // no closing segment\n+\t\t\t{\"a\\u0316\\u0301\\u035Cb\", 5, ColElems{w(102), w(0, 220)}}, // completes before segment end\n+\t\t\t{\"a\\u0316\\u0301\\u035C\", 5, ColElems{w(102), w(0, 220)}}, // completes before segment end\n \n \t\t\t// match blocked by modifier with same ccc\n-\t\t\t{\"a\\u0301\\u0315\\u031A\\u035Fb\", 3, []Weights{w(102)}},\n+\t\t\t{\"a\\u0301\\u0315\\u031A\\u035Fb\", 3, ColElems{w(102)}},\n \n \t\t\t// multiple gaps\n-\t\t\t{\"a\\u0301\\u035Db\", 6, []Weights{w(120)}},\n-\t\t\t{\"a\\u0301\\u035F\", 5, []Weights{w(121)}},\n-\t\t\t{\"a\\u0301\\u035Fb\", 6, []Weights{w(122)}},\n-\t\t\t{\"a\\u0316\\u0301\\u035F\", 7, []Weights{w(121), w(0, 220)}},\n-\t\t\t{\"a\\u0301\\u0315\\u035Fb\", 7, []Weights{w(121), w(0, 232)}},\n-\t\t\t{\"a\\u0316\\u0301\\u0315\\u035Db\", 5, []Weights{w(102), w(0, 220)}},\n-\t\t\t{\"a\\u0316\\u0301\\u0315\\u035F\", 9, []Weights{w(121), w(0, 220), w(0, 232)}},\n-\t\t\t{\"a\\u0316\\u0301\\u0315\\u035Fb\", 9, []Weights{w(121), w(0, 220), w(0, 232)}},\n-\t\t\t{\"a\\u0316\\u0301\\u0315\\u035F\\u035D\", 9, []Weights{w(121), w(0, 220), w(0, 232)}},\n-\t\t\t{\"a\\u0316\\u0301\\u0315\\u035F\\u035Db\", 9, []Weights{w(121), w(0, 220), w(0, 232)}},\n+\t\t\t{\"a\\u0301\\u035Db\", 6, ColElems{w(120)}},\n+\t\t\t{\"a\\u0301\\u035F\", 5, ColElems{w(121)}},\n+\t\t\t{\"a\\u0301\\u035Fb\", 6, ColElems{w(122)}},\n+\t\t\t{\"a\\u0316\\u0301\\u035F\", 7, ColElems{w(121), w(0, 220)}},\n+\t\t\t{\"a\\u0301\\u0315\\u035Fb\", 7, ColElems{w(121), w(0, 232)}},\n+\t\t\t{\"a\\u0316\\u0301\\u0315\\u035Db\", 5, ColElems{w(102), w(0, 220)}},\n+\t\t\t{\"a\\u0316\\u0301\\u0315\\u035F\", 9, ColElems{w(121), w(0, 220), w(0, 232)}},\n+\t\t\t{\"a\\u0316\\u0301\\u0315\\u035Fb\", 9, ColElems{w(121), w(0, 220), w(0, 232)}},\n+\t\t\t{\"a\\u0316\\u0301\\u0315\\u035F\\u035D\", 9, ColElems{w(121), w(0, 220), w(0, 232)}},\n+\t\t\t{\"a\\u0316\\u0301\\u0315\\u035F\\u035Db\", 9, ColElems{w(121), w(0, 220), w(0, 232)}},\n \n \t\t\t// handling of segment overflow\n \t\t\t{ // just fits within segment\n \t\t\t\t\"a\" + string(modSeq[:30]) + \"\\u0301\",\n \t\t\t\t3 + len(string(modSeq[:30])),\n-\t\t\t\tappend([]Weights{w(102)}, modW[:30]...),\n+\t\t\t\tappend(ColElems{w(102)}, modW[:30]...),\n \t\t\t},\n-\t\t\t{\"a\" + string(modSeq[:31]) + \"\\u0301\", 1, []Weights{w(100)}}, // overflow\n-\t\t\t{\"a\" + string(modSeq) + \"\\u0301\", 1, []Weights{w(100)}},\n+\t\t\t{\"a\" + string(modSeq[:31]) + \"\\u0301\", 1, ColElems{w(100)}}, // overflow\n+\t\t\t{\"a\" + string(modSeq) + \"\\u0301\", 1, ColElems{w(100)}},\n \t\t\t{ // just fits within segment with two interstitial runes\n \t\t\t\t\"a\" + string(modSeq[:28]) + \"\\u0301\\u0315\\u035F\",\n \t\t\t\t7 + len(string(modSeq[:28])),\n-\t\t\t\tappend(append([]Weights{w(121)}, modW[:28]...), w(0, 232)),\n+\t\t\t\tappend(append(ColElems{w(121)}, modW[:28]...), w(0, 232)),\n \t\t\t},\n \t\t\t{ // second half does not fit within segment\n \t\t\t\t\"a\" + string(modSeq[:29]) + \"\\u0301\\u0315\\u035F\",\n \t\t\t\t3 + len(string(modSeq[:29])),\n-\t\t\t\tappend([]Weights{w(102)}, modW[:29]...),\n+\t\t\t\tappend(ColElems{w(102)}, modW[:29]...),\n \t\t\t},\n \n \t\t\t// discontinuity can only occur in last normalization segment\n-\t\t\t{\"a\\u035Eb\\u035E\", 6, []Weights{w(115)}},\n-\t\t\t{\"a\\u0316\\u035Eb\\u035E\", 5, []Weights{w(110), w(0, 220)}},\n-\t\t\t{\"a\\u035Db\\u035D\", 6, []Weights{w(117)}},\n-\t\t\t{\"a\\u0316\\u035Db\\u035D\", 1, []Weights{w(100)}},\n-\t\t\t{\"a\\u035Eb\\u0316\\u035E\", 8, []Weights{w(115), w(0, 220)}},\n-\t\t\t{\"a\\u035Db\\u0316\\u035D\", 8, []Weights{w(117), w(0, 220)}},\n-\t\t\t{\"ac\\u035Eaca\\u035E\", 9, []Weights{w(116)}},\n-\t\t\t{\"a\\u0316c\\u035Eaca\\u035E\", 1, []Weights{w(100)}},\n-\t\t\t{\"ac\\u035Eac\\u0316a\\u035E\", 1, []Weights{w(100)}},\n+\t\t\t{\"a\\u035Eb\\u035E\", 6, ColElems{w(115)}},\n+\t\t\t{\"a\\u0316\\u035Eb\\u035E\", 5, ColElems{w(110), w(0, 220)}},\n+\t\t\t{\"a\\u035Db\\u035D\", 6, ColElems{w(117)}},\n+\t\t\t{\"a\\u0316\\u035Db\\u035D\", 1, ColElems{w(100)}},\n+\t\t\t{\"a\\u035Eb\\u0316\\u035E\", 8, ColElems{w(115), w(0, 220)}},\n+\t\t\t{\"a\\u035Db\\u0316\\u035D\", 8, ColElems{w(117), w(0, 220)}},\n+\t\t\t{\"ac\\u035Eaca\\u035E\", 9, ColElems{w(116)}},\n+\t\t\t{\"a\\u0316c\\u035Eaca\\u035E\", 1, ColElems{w(100)}},\n+\t\t\t{\"ac\\u035Eac\\u0316a\\u035E\", 1, ColElems{w(100)}},\n \n \t\t\t// expanding contraction\n-\t\t\t{\"\\u03B1\\u0345\", 4, []Weights{w(901), w(902)}},\n+\t\t\t{\"\\u03B1\\u0345\", 4, ColElems{w(901), w(902)}},\n \n \t\t\t// Theoretical possibilities\n \t\t\t// contraction within a gap\n-\t\t\t{\"a\\u302F\\u18A9\\u0301\", 9, []Weights{w(102), w(0, 130)}},\n+\t\t\t{\"a\\u302F\\u18A9\\u0301\", 9, ColElems{w(102), w(0, 130)}},\n \t\t\t// expansion within a gap\n-\t\t\t{\"a\\u0317\\u0301\", 5, []Weights{w(102), w(0, 220), w(0, 220)}},\n-\t\t\t{\"a\\u302E\\u18A9\\u0301\", 9, []Weights{w(102), w(0, 131), w(0, 132)}},\n+\t\t\t{\"a\\u0317\\u0301\", 5, ColElems{w(102), w(0, 220), w(0, 220)}},\n+\t\t\t{\"a\\u302E\\u18A9\\u0301\", 9, ColElems{w(102), w(0, 131), w(0, 132)}},\n \t\t\t{\n \t\t\t\t\"a\\u0317\\u302E\\u18A9\\u0301\",\n \t\t\t\t11,\n-\t\t\t\t[]Weights{w(102), w(0, 220), w(0, 220), w(0, 131), w(0, 132)},\n+\t\t\t\tColElems{w(102), w(0, 220), w(0, 220), w(0, 131), w(0, 132)},\n \t\t\t},\n \t\t},\n \t},\
@@ -269,7 +271,7 @@ func TestAppendNext(t *testing.T) {\n \t\t\t\tcontinue\n \t\t\t}\n \t\t\tfor k, w := range ws {\n-\t\t\t\tif w != chk.out[k].Weights {\n+\t\t\t\tif w != chk.out[k] {\n \t\t\t\t\tt.Errorf(\"%d:%d: Weights %d was %v; want %v\", i, j, k, w, chk.out[k])\n \t\t\t\t}\n \t\t\t}\n```
`Weights` 型が `ColElems` に変更され、`collate.Weights` を直接使用するように修正されています。これにより、テストコードの整合性が向上しています。
## コアとなるコードの解説
このコミットの核心は、Unicode Collation Algorithm (UCA) に基づく文字列の比較と照合キー生成のロジックをGo言語で実装した点にあります。
### 照合キーの生成 (`Key`, `KeyFromString`, `key`, `keyFromElems`, `appendPrimary`)
* `Collator.Key` と `Collator.KeyFromString` は、それぞれバイトスライスと文字列から照合キーを生成するエントリポイントです。これらは内部的に `getColElems` (または `getColElemsString`) を呼び出して入力文字列を照合要素のシーケンスに変換し、その後 `key` メソッドを呼び出します。
* `Collator.key` メソッドは、まず `processWeights` を呼び出して、`Alternate Handling` の設定に基づいて照合要素の重みを調整します。その後、`keyFromElems` を呼び出して、調整された重みから最終的なバイトシーケンスとしての照合キーを構築します。
* `keyFromElems` 関数は、UCAの主要な概念であるプライマリ、セカンダリ、ターシャリ、クォータナリの各レベルの重みを、特定のルールに従ってバイトシーケンスに変換します。
* **プライマリ重み**: `appendPrimary` 関数によって追加されます。これは、最大23ビットの値を効率的にエンコードするための可変長エンコーディングを使用します。
* **セカンダリ重み**: `Collator.Strength` が `Secondary` 以上の場合にキーに追加されます。`Collator.Backwards` が `true` の場合、セカンダリ重みは逆順に追加され、フランス語のアクセントソートなどの特殊な要件に対応します。
* **ターシャリ重み**: `Collator.Strength` が `Tertiary` 以上、または `Collator.CaseLevel` が `true` の場合に追加されます。
* **クォータナリ重み**: `Collator.Strength` が `Quaternary` 以上の場合に追加されます。`Alternate Handling` の設定に応じて、可変要素のクォータナリ重みがどのようにキーに組み込まれるかが決定されます。`AltShiftTrimmed` の場合、末尾の `maxQuaternary` 値は除去されます。
* 各レベルの重みの間には、区切りバイト（`0x00`）が挿入され、異なるレベルの重みが混同されないようにします。
### 重みの処理 (`processWeights`)
* `processWeights` 関数は、UCAの `Alternate Handling` ルールを実装しています。これは、句読点や記号などの「可変要素」の扱いを制御します。
* `AltShifted` または `AltShiftTrimmed` が設定されている場合、`variableTop` 以下のプライマリ重みを持つ要素（可変要素）は、そのプライマリ重みがクォータナリ重みに移動され、プライマリ、セカンダリ、ターシャリ重みはゼロになります。これにより、これらの要素はプライマリレベルでは無視され、クォータナリレベルでのみ比較に影響を与えます。
* `AltBlanked` が設定されている場合、可変要素はすべてのレベルで完全に無視されます（すべての重みがゼロになります）。
### 文字列の比較 (`Compare`, `CompareString`)
* `Collator.Compare` と `Collator.CompareString` は、2つの入力文字列（またはバイトスライス）の照合キーを生成し、そのキーを `bytes.Compare` を用いてバイナリ比較することで、文字列の照合順序を決定します。
* このアプローチは、UCAの「照合キーを生成し、それをバイナリ比較する」という基本的な原則に従っています。
### 照合要素の抽出 (`getColElems`, `iter`)
* `getColElems` と `getColElemsString` は、入力文字列をUnicode正規化形式（NFD）に変換し、そこから照合要素を抽出する役割を担います。
* `iter` 構造体は、この抽出プロセスを効率的に行うためのイテレータです。`exp/norm` パッケージの正規化イテレータと連携し、入力データをチャンクごとに処理し、照合要素に変換します。
これらの機能が連携することで、Go言語の `exp/locale/collate` パッケージは、多言語環境での複雑な文字列ソート要件に対応するための強力な基盤を提供します。
## 関連リンク
* [Unicode Collation Algorithm (UCA)](http://www.unicode.org/reports/tr10/)
* [Go言語の `exp/locale` パッケージ (GoDoc)](https://pkg.go.dev/exp/locale) (コミット当時の情報であり、現在のGoの標準ライブラリとは異なる可能性があります)
## 参考にした情報源リンク
* [Unicode Collation Algorithm - Wikipedia](https://en.wikipedia.org/wiki/Unicode_collation_algorithm)
* [Go言語の国際化と地域化に関する議論 (golang-devメーリングリストなど)](https://groups.google.com/g/golang-dev) (具体的なスレッドは特定できませんが、当時の開発議論の場として)
* [Go言語の `exp/norm` パッケージ (GoDoc)](https://pkg.go.dev/exp/norm) (Unicode正規化に関するパッケージ)
* [Go言語のソースコード (GitHub)](https://github.com/golang/go)
* [Unicode Technical Standard #10: Unicode Collation Algorithm](https://www.unicode.org/reports/tr10/) (UCAの公式仕様)
* [Unicode Character Database (UCD)](https://www.unicode.org/ucd/) (UCAのデータはここから派生します)