[インデックス 13013] ファイルの概要

このコミットは、Go言語の実験的なUnicodeロケールパッケージ（exp/locale/collate）とUnicode正規化パッケージ（exp/norm）における2つの重要なバグ修正に焦点を当てています。これらのバグは、回帰テストによって発見され、特にUnicodeの照合順序（Collation）とトライ（Trie）データ構造の実装に関連するものでした。

コミット

commit 10838165d8249175020155751469bc7729d78fb9
Author: Marcel van Lohuizen <mpvl@golang.org>
Date:   Wed May 2 17:01:41 2012 +0200

    exp/locale/collate: fixed two bugs uncovered by regression tests.
    The first bug was that tertiary ignorables had the same colElem as
    implicit colElems, yielding unexpected results. The current encoding
    ensures that a non-implicit colElem is never 0.  This fix uncovered
    another bug of the trie that indexed incorrectly into the null block.
    This was caused by an unfinished optimization that would avoid the
    need to max out the most-significant bits of continuation bytes.
    This bug was also present in the trie used in exp/norm and has been
    fixed there as well. The appearence of the bug was rare, as the lower
    blocks happened to be nearly nil.
    
    R=r
    CC=golang-dev
    https://golang.org/cl/6127070

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/10838165d8249175020155751469bc7729d78fb9

元コミット内容

exp/locale/collate: fixed two bugs uncovered by regression tests.
The first bug was that tertiary ignorables had the same colElem as
implicit colElems, yielding unexpected results. The current encoding
ensures that a non-implicit colElem is never 0.  This fix uncovered
another bug of the trie that indexed incorrectly into the null block.
This was caused by an unfinished optimization that would avoid the
need to max out the most-significant bits of continuation bytes.
This bug was also present in the trie used in exp/norm and has been
fixed there as well. The appearence of the bug was rare, as the lower
blocks happened to be nearly nil.

R=r
CC=golang-dev
https://golang.org/cl/6127070

変更の背景

このコミットは、Go言語の実験的なUnicode関連パッケージにおける2つの重要なバグを修正するために行われました。これらのバグは、Unicodeの照合順序（Collation）と正規化（Normalization）という、テキスト処理において非常に重要な機能の正確性に影響を与えるものでした。

1. 照合要素（Collation Element）の重複問題: Unicode Collation Algorithm (UCA) において、文字の比較順序を決定するために「照合要素（Collation Element, CE）」が使用されます。CEは通常、プライマリ、セカンダリ、ターシャリの3つのレベルの重みで構成されます。このバグは、ターシャリレベルで無視されるべき文字（tertiary ignorables）が、暗黙的な照合要素（implicit colElems）と同じ内部表現を持ってしまうというものでした。これにより、本来異なるべき文字が同じ順序として扱われたり、予期せぬ照合結果が生じる可能性がありました。特に、非暗黙的な照合要素が0にならないようにすることで、この重複を回避する必要がありました。

2. トライ（Trie）データ構造のインデックス問題: Unicodeの照合や正規化の処理では、大量の文字プロパティやマッピング情報を効率的に検索するためにトライデータ構造が広く利用されます。このバグは、トライが「ヌルブロック（null block）」に対して誤ったインデックス付けを行うというものでした。これは、UTF-8の継続バイトの最上位ビットを最大化する最適化が未完成であったことに起因していました。この最適化の意図は、継続バイトの処理を簡素化することでしたが、結果としてトライのインデックス計算に誤りを生じさせていました。このバグは、exp/locale/collateだけでなく、Unicode正規化を扱うexp/normパッケージのトライにも存在しており、稀にしか発生しないものの、データ構造の根本的な正確性に影響を与えていました。

これらのバグは、Go言語のUnicodeサポートの正確性と堅牢性を向上させるために、回帰テストによって発見され、修正されました。

前提知識の解説

Unicode Collation Algorithm (UCA) と照合要素 (Collation Element)

Unicode Collation Algorithm (UCA) は、異なる言語や文化圏のテキストを、それぞれの言語の慣習に従ってソート（照合）するための国際標準アルゴリズムです。UCAは、単なるコードポイント順のソートではなく、以下のような複雑なルールを考慮します。

• アクセントとダイアクリティカルマーク: 例えば、a, á, à などは、言語によっては同じ文字として扱われたり、異なる順序で扱われたりします。
• 大文字と小文字: A と a の順序関係。
• 合字 (Ligatures): fi のような合字を f と i の組み合わせとして扱うか。
• 無視される文字: ハイフンや句読点など、特定のレベルではソートに影響を与えない文字。

UCAでは、各文字または文字シーケンスを「照合要素（Collation Element, CE）」と呼ばれる数値のシーケンスに変換します。CEは通常、以下の3つのレベルの重みで構成されます。

1. プライマリ重み (Primary Weight): 文字の基本的な形状やアルファベット順を決定します。例えば、a と b はプライマリ重みが異なります。
2. セカンダリ重み (Secondary Weight): アクセントやダイアクリティカルマークの違いを区別します。例えば、a と á はプライマリ重みが同じでも、セカンダリ重みが異なります。
3. ターシャリ重み (Tertiary Weight): 大文字と小文字、または文字の幅（全角/半角）などの違いを区別します。例えば、a と A はプライマリ、セカンダリ重みが同じでも、ターシャリ重みが異なります。

ターシャリ無視可能 (Tertiary Ignorables): 特定の文字（例えば、一部の句読点や制御文字）は、プライマリ、セカンダリレベルではソートに影響を与えず、ターシャリレベルでも無視されることがあります。これらを「ターシャリ無視可能」と呼びます。

暗黙的な照合要素 (Implicit ColElems): UCAでは、特定のUnicodeコードポイント（特にCJK統合漢字など）に対して、明示的な照合要素が定義されていない場合があります。このような場合、アルゴリズムはコードポイントに基づいて「暗黙的な」照合要素を生成します。

トライ (Trie) データ構造

トライ（Trie、またはプレフィックスツリー）は、キーが文字列である連想配列を実装するためによく使われるツリーデータ構造です。各ノードは文字列のプレフィックスに対応し、ルートノードは空の文字列に対応します。子ノードへのエッジは、そのプレフィックスに続く文字を表します。

Unicodeの照合や正規化では、数万から数十万の文字に対するプロパティやマッピング情報を効率的に検索する必要があります。トライは、以下のような理由でこれらの用途に適しています。

• 高速なプレフィックス検索: 文字列のプレフィックスに基づいて情報を検索するのに非常に効率的です。
• 空間効率: 共通のプレフィックスを持つキーを共有するため、メモリ使用量を削減できます。
• UTF-8処理: UTF-8エンコードされたバイトシーケンスを効率的に処理するために、バイト単位でトライを構築することが一般的です。

ヌルブロック (Null Block): トライの実装において、データが存在しない、またはデフォルト値を持つ領域を効率的に表現するために「ヌルブロック」という概念が用いられることがあります。これは、多くのエントリが同じデフォルト値を持つ場合に、そのブロック全体をヌルブロックとして参照することで、メモリ使用量を削減する最適化手法です。

継続バイト (Continuation Bytes): UTF-8エンコーディングでは、1バイト文字（ASCII）以外の文字は複数バイトで表現されます。2バイト目以降のバイトは「継続バイト」と呼ばれ、特定のビットパターン（10xxxxxx）を持ちます。トライがUTF-8バイトシーケンスを処理する際、これらの継続バイトを適切にデコードし、次のノードへのインデックスとして使用する必要があります。

技術的詳細

照合要素のエンコーディング修正

最初のバグは、exp/locale/collate/build/colelem.go および src/pkg/exp/locale/collate/colelem.go で修正されています。

元のコードでは、照合要素（colElem）のエンコーディングにおいて、プライマリ重みを持つCEとセカンダリ重みを持つCEのビットパターンが、特定の条件下でターシャリ無視可能文字や暗黙的な照合要素と衝突する可能性がありました。特に、非暗黙的な照合要素が0になることが問題でした。

修正の核心は、isPrimary 定数を isSecondary に変更し、プライマリ重みを持つCEのエンコーディングから isPrimary フラグを削除した点です。代わりに、セカンダリ重みを持つCEに isSecondary フラグ（0x40000000）を明示的に設定するように変更されました。

• 変更前:

  • プライマリ重みを持つCE: 010ppppp pppppppp pppppppp tttttttt (最上位から2番目のビットが1)
  • セカンダリ重みを持つCE: 00000000 ssssssss ssssssss tttttttt (最上位から2番目のビットが0)
  • isPrimary = 0x40000000 (最上位から2番目のビットが1)

• 変更後:

  • プライマリ重みを持つCE: 000ppppp pppppppp pppppppp tttttttt (最上位から2番目のビットが0)
  • セカンダリ重みを持つCE: 01000000 ssssssss ssssssss tttttttt (最上位から2番目のビットが1)
  • isSecondary = 0x40000000 (最上位から2番目のビットが1)

この変更により、プライマリ重みを持つCEとセカンダリ重みを持つCEが、最上位から2番目のビットによって明確に区別されるようになりました。プライマリ重みを持つCEは、このビットが常に0であるため、暗黙的な照合要素やターシャリ無視可能文字と衝突する可能性が低減されます。特に、splitCE 関数でのCEのタイプ判定ロジックが if ce&secondaryMask == 0 に変更され、この新しいエンコーディングスキームに対応しています。

トライのインデックス修正

2つ目のバグは、トライデータ構造のインデックス計算に関するもので、src/pkg/exp/locale/collate/build/trie.go、src/pkg/exp/locale/collate/trie.go、src/pkg/exp/norm/trie.go、src/pkg/exp/norm/triegen.go で修正されています。

このバグは、トライがヌルブロックを誤ってインデックス付けすることに起因していました。これは、UTF-8の継続バイトの最上位ビットを最大化する未完成の最適化が原因でした。具体的には、トライのルックアップテーブルや値ブロックへのオフセット計算において、継続バイトの処理が不適切でした。

修正のポイントは以下の通りです。

1. blockOffset の導入: build/trie.go と norm/triegen.go で blockOffset = 2 が導入されました。これは、継続バイトに 0x80 が追加されることを補償するために、ブロックのオフセットから2ブロック分を減算するための定数です。これにより、トライのインデックス計算が正しく行われるようになります。
2. maskx の削除とバイト値の直接使用: collate/trie.go と norm/trie.go から maskx (0x3F) などのマスク定数が削除されました。これは、継続バイトの最上位ビットをマスクして下位6ビットのみを使用するという、未完成の最適化に関連するものでした。このマスクを削除し、バイト値を直接インデックスとして使用することで、トライのインデックス計算が簡素化され、ヌルブロックへの誤ったインデックス付けが修正されました。
   • 変更前: t.values[int(n)<<6+int(b&maskx)]
   • 変更後: t.values[int(n)<<6+int(b)] この変更は、lookupValue、lookup、lookupString、lookupUnsafe、lookupStringUnsafe といったトライの主要なルックアップ関数に適用されています。
3. テストデータの更新: build/trie_test.go、collate/trie_test.go、norm/tables.go、norm/triedata_test.go のテストデータが、新しいインデックス計算ロジックに合わせて更新されました。特に、nfcLookup と nfkcLookup の値が大幅に変更されており、これはトライの内部構造が修正された結果、ルックアップテーブルのエントリが再計算されたことを示しています。

これらの修正により、トライはUTF-8バイトシーケンスを正しく処理し、ヌルブロックを含むすべてのブロックに対して正確なインデックス付けを行うことができるようになりました。これにより、Unicodeの照合と正規化の処理におけるデータ検索の正確性と信頼性が向上しました。

コアとなるコードの変更箇所

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
@@ -25,11 +25,11 @@ const (
 // 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
-// 010ppppp pppppppp pppppppp tttttttt, where
+// 000ppppp pppppppp pppppppp tttttttt, where
 //   - p* is primary collation value
 //   - t* is the tertiary collation value
 // Collation elements with a secondary value are of the form
-// 00000000 ssssssss ssssssss tttttttt, where
+// 01000000 ssssssss ssssssss tttttttt, where
 //   - s* is the secondary collation value
 //   - t* is the tertiary collation value
 const (
@@ -37,7 +37,7 @@ const (
 	maxSecondaryBits = 16
 	maxTertiaryBits  = 8
 
-	isPrimary = 0x40000000
+	isSecondary = 0x40000000
 )
 
 func makeCE(weights []int) (uint32, error) {
@@ -57,10 +57,10 @@ func makeCE(weights []int) (uint32, error) {
 			return 0, fmt.Errorf("makeCE: non-default secondary weight for non-zero primary: %X", weights)
 		}
 		ce = uint32(weights[0]<<maxTertiaryBits + weights[2])
-		ce |= isPrimary
 	} else {
 		// secondary weight form
 		ce = uint32(weights[1]<<maxTertiaryBits + weights[2])
+		ce |= isSecondary
 	}
 	return ce, nil
 }

src/pkg/exp/locale/collate/build/trie.go

--- a/src/pkg/exp/locale/collate/build/trie.go
+++ b/src/pkg/exp/locale/collate/build/trie.go
@@ -19,7 +19,10 @@ import (
 	"reflect"
 )
 
-const blockSize = 64
+const (
+	blockSize   = 64
+	blockOffset = 2 // Substract 2 blocks to compensate for the 0x80 added to continuation bytes.
+)
 
 type trie struct {
 	index  []uint16
@@ -102,7 +105,7 @@ func computeOffsets(index *nodeIndex, n *trieNode) int64 {
 	if n.isInternal() {
 		v, ok := index.lookupBlockIdx[h]
 		if !ok {
-			v = int64(len(index.lookupBlocks))
+			v = int64(len(index.lookupBlocks)) - blockOffset
 			index.lookupBlocks = append(index.lookupBlocks, n)
 			index.lookupBlockIdx[h] = v
 		}
@@ -110,7 +113,7 @@ func computeOffsets(index *nodeIndex, n *trieNode) int64 {
 	} else {
 		v, ok := index.valueBlockIdx[h]
 		if !ok {
-			v = int64(len(index.valueBlocks))
+			v = int64(len(index.valueBlocks)) - blockOffset
 			index.valueBlocks = append(index.valueBlocks, n)
 			index.valueBlockIdx[h] = v
 		}

src/pkg/exp/locale/collate/colelem.go

--- a/src/pkg/exp/locale/collate/colelem.go
+++ b/src/pkg/exp/locale/collate/colelem.go
@@ -68,17 +68,18 @@ func (ce colElem) ctype() ceType {
 // 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
-// 010ppppp pppppppp pppppppp tttttttt, where
+// 000ppppp pppppppp pppppppp tttttttt, where
 //   - p* is primary collation value
 //   - t* is the tertiary collation value
 // Collation elements with a secondary value are of the form
-// 00000000 ssssssss ssssssss tttttttt, where
+// 01000000 ssssssss ssssssss tttttttt, where
 //   - s* is the secondary collation value
 //   - t* is the tertiary collation value
 func splitCE(ce colElem) weights {
+	const secondaryMask = 0x40000000
 	w := weights{}
 	w.tertiary = uint8(ce)
-	if ce&0x40000000 != 0 {
+	if ce&secondaryMask == 0 {
 		// primary weight form
 		w.primary = uint32((ce >> 8) & 0x1FFFFF)
 		w.secondary = defaultSecondary

src/pkg/exp/locale/collate/trie.go

--- a/src/pkg/exp/locale/collate/trie.go
+++ b/src/pkg/exp/locale/collate/trie.go
@@ -27,15 +27,10 @@ const (
 	t5 = 0xF8 // 1111 1000
 	t6 = 0xFC // 1111 1100
 	te = 0xFE // 1111 1110
-
-	maskx = 0x3F // 0011 1111
-	mask2 = 0x1F // 0001 1111
-	mask3 = 0x0F // 0000 1111
-	mask4 = 0x07 // 0000 0111
 )
 
 func (t *trie) lookupValue(n uint16, b byte) colElem {
-	return colElem(t.values[int(n)<<6+int(b&maskx)])
+	return colElem(t.values[int(n)<<6+int(b)])
 }
 
 // lookup returns the trie value for the first UTF-8 encoding in s and
@@ -67,7 +62,7 @@ func (t *trie) lookup(s []byte) (v colElem, sz int) {
 		if c1 < tx || t2 <= c1 {
 			return 0, 1
 		}
-		o := int(i)<<6 + int(c1)&maskx
+		o := int(i)<<6 + int(c1)
 		i = t.index[o]
 		c2 := s[2]
 		if c2 < tx || t2 <= c2 {
@@ -83,13 +78,13 @@ func (t *trie) lookup(s []byte) (v colElem, sz int) {
 		if c1 < tx || t2 <= c1 {
 			return 0, 1
 		}
-		o := int(i)<<6 + int(c1)&maskx
+		o := int(i)<<6 + int(c1)
 		i = t.index[o]
 		c2 := s[2]
 		if c2 < tx || t2 <= c2 {
 			return 0, 2
 		}
-		o = int(i)<<6 + int(c2)&maskx
+		o = int(i)<<6 + int(c2)
 		i = t.index[o]
 		c3 := s[3]
 		if c3 < tx || t2 <= c3 {

src/pkg/exp/norm/trie.go

--- a/src/pkg/exp/norm/trie.go
+++ b/src/pkg/exp/norm/trie.go
@@ -23,7 +23,7 @@ type trie struct {
 // the value for b is by r.value + (b - r.lo) * stride.\n func (t *trie) lookupValue(n uint8, b byte) uint16 {
 \tif n < t.cutoff {\n-\t\treturn t.values[uint16(n)<<6+uint16(b&maskx)]\n+\t\treturn t.values[uint16(n)<<6+uint16(b)]\n \t}\n \toffset := t.sparseOffset[n-t.cutoff]\n \theader := t.sparse[offset]\n@@ -53,11 +53,6 @@ const (\n \tt5 = 0xF8 // 1111 1000\n \tt6 = 0xFC // 1111 1100\n \tte = 0xFE // 1111 1110\n-\n-\tmaskx = 0x3F // 0011 1111\n-\tmask2 = 0x1F // 0001 1111\n-\tmask3 = 0x0F // 0000 1111\n-\tmask4 = 0x07 // 0000 0111\n )\n \n // lookup returns the trie value for the first UTF-8 encoding in s and\n@@ -89,7 +84,7 @@ func (t *trie) lookup(s []byte) (v uint16, sz int) {\n \t\tif c1 < tx || t2 <= c1 {\n \t\t\treturn 0, 1\n \t\t}\n-\t\to := uint16(i)<<6 + uint16(c1)&maskx\n+\t\to := uint16(i)<<6 + uint16(c1)\n \t\ti = t.index[o]\n \t\tc2 := s[2]\n \t\tif c2 < tx || t2 <= c2 {\n@@ -105,13 +100,13 @@ func (t *trie) lookup(s []byte) (v uint16, sz int) {\n \t\tif c1 < tx || t2 <= c1 {\n \t\t\treturn 0, 1\n \t\t}\n-\t\to := uint16(i)<<6 + uint16(c1)&maskx\n+\t\to = uint16(i)<<6 + uint16(c1)\n \t\ti = t.index[o]\n \t\tc2 := s[2]\n \t\tif c2 < tx || t2 <= c2 {\n \t\t\treturn 0, 2\n \t\t}\n-\t\to = uint16(i)<<6 + uint16(c2)&maskx\n+\t\to = uint16(i)<<6 + uint16(c2)\n \t\ti = t.index[o]\n \t\tc3 := s[3]\n \t\tif c3 < tx || t2 <= c3 {\n@@ -152,7 +147,7 @@ func (t *trie) lookupString(s string) (v uint16, sz int) {\n \t\tif c1 < tx || t2 <= c1 {\n \t\t\treturn 0, 1\n \t\t}\n-\t\to := uint16(i)<<6 + uint16(c1)&maskx\n+\t\to = uint16(i)<<6 + uint16(c1)\n \t\ti = t.index[o]\n \t\tc2 := s[2]\n \t\tif c2 < tx || t2 <= c2 {\n@@ -168,13 +163,13 @@ func (t *trie) lookupString(s string) (v uint16, sz int) {\n \t\tif c1 < tx || t2 <= c1 {\n \t\t\treturn 0, 1\n \t\t}\n-\t\to := uint16(i)<<6 + uint16(c1)&maskx\n+\t\to = uint16(i)<<6 + uint16(c1)\n \t\ti = t.index[o]\n \t\tc2 := s[2]\n \t\tif c2 < tx || t2 <= c2 {\n \t\t\treturn 0, 2\n \t\t}\n-\t\to = uint16(i)<<6 + uint16(c2)&maskx\n+\t\to = uint16(i)<<6 + uint16(c2)\n \t\ti = t.index[o]\n \t\tc3 := s[3]\n \t\tif c3 < tx || t2 <= c3 {\n@@ -200,11 +195,11 @@ func (t *trie) lookupUnsafe(s []byte) uint16 {\n \tif c0 < t3 {\n \t\treturn t.lookupValue(i, s[1])\n \t}\n-\ti = t.index[uint16(i)<<6+uint16(s[1])&maskx]\n+\ti = t.index[uint16(i)<<6+uint16(s[1])]\n \tif c0 < t4 {\n \t\treturn t.lookupValue(i, s[2])\n \t}\n-\ti = t.index[uint16(i)<<6+uint16(s[2])&maskx]\n+\ti = t.index[uint16(i)<<6+uint16(s[2])]\n \tif c0 < t5 {\n \t\treturn t.lookupValue(i, s[3])\n \t}\n@@ -225,11 +220,11 @@ func (t *trie) lookupStringUnsafe(s string) uint16 {\n \tif c0 < t3 {\n \t\treturn t.lookupValue(i, s[1])\n \t}\n-\ti = t.index[uint16(i)<<6+uint16(s[1])&maskx]\n+\ti = t.index[uint16(i)<<6+uint16(s[1])]\n \tif c0 < t4 {\n \t\treturn t.lookupValue(i, s[2])\n \t}\n-\ti = t.index[uint16(i)<<6+uint16(s[2])&maskx]\n+\ti = t.index[uint16(i)<<6+uint16(s[2])]\n \tif c0 < t5 {\n \t\treturn t.lookupValue(i, s[3])\n \t}\n```

### `src/pkg/exp/norm/triegen.go`

```diff
--- a/src/pkg/exp/norm/triegen.go
+++ b/src/pkg/exp/norm/triegen.go
@@ -19,8 +19,11 @@ import (
 	"unicode/utf8"
 )
 
-const blockSize = 64
-const maxSparseEntries = 16
+const (
+	blockSize        = 64
+	blockOffset      = 2 // Substract two blocks to compensate for the 0x80 added to continuation bytes.
+	maxSparseEntries = 16
+)
 
 // Intermediate trie structure
 type trieNode struct {
@@ -157,7 +160,7 @@ func computeOffsets(index *nodeIndex, n *trieNode) int {
 	if n.isInternal() {
 		v, ok := index.lookupBlockIdx[h]
 		if !ok {
-			v = len(index.lookupBlocks)
+			v = len(index.lookupBlocks) - blockOffset
 			index.lookupBlocks = append(index.lookupBlocks, n)
 			index.lookupBlockIdx[h] = v
 		}
@@ -166,7 +169,7 @@ func computeOffsets(index *nodeIndex, n *trieNode) int {
 	t\tv, ok := index.valueBlockIdx[h]
 	t\tif !ok {
 	t\t\tif c := n.countSparseEntries(); c > maxSparseEntries {
-\t\t\t\tv = len(index.valueBlocks)
+\t\t\t\tv = len(index.valueBlocks) - blockOffset
 	t\t\t\tindex.valueBlocks = append(index.valueBlocks, n)
 	t\t\t\tindex.valueBlockIdx[h] = v
 	t\t\t} else {
@@ -295,7 +298,7 @@ func (t *trieNode) printTables(name string) int {
 	}\n \tfmt.Print("\\n}\\n\\n")\n \n-\tcutoff := len(index.valueBlocks)\n+\tcutoff := len(index.valueBlocks) - blockOffset\n \tni := len(index.lookupBlocks) * blockSize\n \tfmt.Printf("// %sLookup: %d bytes\\n", name, ni)\n \tfmt.Printf("// Block 0 is the null block.\\n")

コアとなるコードの解説

照合要素のエンコーディング修正 (colelem.go)

この修正は、Unicode照合要素（Collation Element, CE）の内部表現における曖昧さを解消することを目的としています。CEは、文字のソート順を決定するためのプライマリ、セカンダリ、ターシャリの3つの重みレベルをエンコードした32ビットの数値です。

• isPrimary から isSecondary への変更:
  • 以前は isPrimary = 0x40000000 という定数があり、プライマリ重みを持つCEにこのビットを立てることで、プライマリCEであることを示していました。
  • しかし、この設計では、プライマリ重みが0のCE（つまり、セカンダリ重みやターシャリ重みのみを持つCE）と、暗黙的な照合要素やターシャリ無視可能文字のCEが衝突する可能性がありました。特に、CEが0になるケースが問題でした。
  • 修正後は、isSecondary = 0x40000000 となり、このビットはセカンダリ重みを持つCEにのみ設定されます。
• makeCE 関数のロジック変更:
  • プライマリ重みを持つCEを作成する際、以前は ce |= isPrimary で 0x40000000 ビットを立てていましたが、修正後はこの行が削除されました。これにより、プライマリCEの最上位から2番目のビットは常に0になります。
  • セカンダリ重みを持つCEを作成する際、以前はビット操作がありませんでしたが、修正後は ce |= isSecondary で 0x40000000 ビットを立てるようになりました。これにより、セカンダリCEの最上位から2番目のビットは常に1になります。
• splitCE 関数のロジック変更:
  • CEをプライマリ、セカンダリ、ターシャリの重みに分解する splitCE 関数では、if ce&0x40000000 != 0 という条件でCEのタイプを判定していました。
  • 修正後は、const secondaryMask = 0x40000000 を導入し、if ce&secondaryMask == 0 という条件に変更されました。
  • この新しいロジックでは、0x40000000 ビットが0であればプライマリCE、1であればセカンダリCEと判断します。これにより、プライマリCEとセカンダリCEの区別が明確になり、特に非暗黙的なCEが0になる問題を回避できるようになりました。

この変更により、照合要素のエンコーディングがより堅牢になり、異なるタイプのCE間の衝突が防止され、照合アルゴリズムの正確性が向上しました。

トライのインデックス修正 (trie.go, triegen.go)

この修正は、トライデータ構造がUTF-8バイトシーケンスを処理する際のインデックス計算の誤りを修正することを目的としています。特に、ヌルブロックへの誤ったインデックス付けと、UTF-8継続バイトの処理に関する問題が対象です。

• blockOffset の導入:
  • const blockOffset = 2 が導入されました。この定数は、トライのブロックオフセット計算において、UTF-8の継続バイトに 0x80 が追加されること（これはUTF-8の仕様の一部であり、バイトが継続バイトであることを示す）を補償するために使用されます。
  • computeOffsets 関数では、len(index.lookupBlocks) や len(index.valueBlocks) から blockOffset を減算することで、実際のブロックインデックスが正しく計算されるようになりました。これにより、トライの内部構造がより正確にマッピングされ、ヌルブロックへの誤った参照が修正されます。
• maskx などのマスク定数の削除:
  • 以前のコードでは、maskx = 0x3F などの定数を使用して、UTF-8バイトの下位6ビットのみを抽出していました。これは、UTF-8の継続バイトの最上位2ビット（10）を無視し、データ部分のみをインデックスとして使用しようとする最適化の名残でした。
  • しかし、この最適化が未完成であったため、トライのインデックス計算に誤りを生じさせていました。
  • 修正後は、これらのマスク定数が削除され、int(b&maskx) のようなバイト操作が int(b) のようにバイト値を直接使用するように変更されました。
  • これにより、トライはUTF-8バイトの全ビットを考慮してインデックスを計算するようになり、継続バイトの処理が簡素化され、インデックスの正確性が向上しました。
• ルックアップ関数の修正:
  • lookupValue、lookup、lookupString、lookupUnsafe、lookupStringUnsafe といったトライの主要なルックアップ関数において、バイト値からインデックスを計算する部分が int(b&maskx) から int(b) に変更されました。
  • この変更は、トライがUTF-8バイトシーケンスをトラバースする際のインデックス計算の根本的な修正であり、ヌルブロックへの誤った参照を防ぎ、トライのデータ検索の信頼性を高めます。

これらの修正により、トライデータ構造はUnicodeの照合と正規化の処理において、より正確かつ堅牢に機能するようになりました。特に、稀にしか発生しなかったトライのインデックス問題が解決され、Go言語のUnicodeサポートの品質が向上しました。

関連リンク

• Unicode Collation Algorithm (UCA)
• Unicode Normalization Forms
• Trie (データ構造) - Wikipedia
• UTF-8 - Wikipedia

参考にした情報源リンク

• コミットメッセージと差分情報 (./commit_data/13013.txt)
• Go言語の公式ドキュメント（exp/locale/collate および exp/norm パッケージに関する情報）
• Unicode Consortiumの技術報告書 (TR10, TR15)
• トライデータ構造に関する一般的な情報源
• UTF-8エンコーディングに関する一般的な情報源
• Go言語の実験的なロケールパッケージに関する議論 (golang-devメーリングリストなど) (具体的なスレッドは特定できませんでしたが、一般的な情報収集として)
• Gerrit Code Review for Go (コミットメッセージに記載されているGerritリンクから関連するレビューや議論を辿る)