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

このコミットは、Go言語の実験的なパッケージ exp/locale/collate/build 内の trie.go ファイルに対する変更です。具体的には、トライ（Trie）データ構造の構築ロジックにおけるバグ修正が目的です。この修正は、特に最初のバイトのブロックが値とインデックスブロックに対して異なるインデックスを必要とする問題に対処し、多数の回帰（regression）を修正します。

コミット

commit 6653d76ef6c243b2061325c09e9628735218378c
Author: Marcel van Lohuizen <mpvl@golang.org>
Date:   Wed Oct 24 11:41:05 2012 +0200

    exp/locale/collate/build: fixed problem where blocks for first byte need
    different indexes for values and index blocks. Fixes many regressions.
    
    R=r
    CC=golang-dev
    https://golang.org/cl/6737057

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

https://github.com/golang/go/commit/6653d76ef6c243b2061325c09e9628735218378c

元コミット内容

exp/locale/collate/build: 最初のバイトのブロックが値とインデックスブロックに対して異なるインデックスを必要とする問題を修正しました。これにより、多くの回帰が修正されます。

変更の背景

このコミットの背景には、Go言語の国際化（i18n）およびローカライゼーション（l10n）機能の一部である、照合（collation）データの構築プロセスにおける根本的な問題がありました。照合とは、文字列を特定のロケール（言語や地域）の規則に従ってソートするプロセスです。このプロセスでは、効率的なルックアップのためにトライ（Trie）データ構造がよく使用されます。

問題は、トライの構築時に、特に文字列の最初のバイト（または最初の文字）に対応するブロックが、そのブロックが参照する「値」のインデックスと「次のインデックスブロック」のインデックスを同じように扱っていた点にありました。しかし、実際にはこれらのインデックスは異なる参照を持つ必要がありました。この不一致が原因で、照合ロジックにおいて多数の誤った動作（回帰）が発生していました。

このコミットは、この設計上の欠陥を修正し、値とインデックスブロックの参照を分離することで、照合データの正確な構築を保証し、既存の回帰を解消することを目的としています。

前提知識の解説

1. トライ（Trie）データ構造

トライ（Trie、またはプレフィックスツリー）は、キーが文字列である連想配列を実装するためによく使われるツリーデータ構造です。各ノードは文字列のプレフィックスに対応し、ルートからノードへのパスがキーを表します。トライは、文字列の検索、プレフィックス検索、ソートなどに非常に効率的です。

• ノード: 各ノードは、通常、子ノードへのポインタの配列（またはマップ）と、そのノードが完全なキーの終端である場合に格納される値（または値への参照）を持ちます。
• 効率性: 文字列の長さ L に対して、検索や挿入の操作が O(L) の時間計算量で行えます。これはハッシュテーブルよりも高速な場合があります。
• メモリ使用量: 共通のプレフィックスを持つ文字列が多いため、メモリを節約できる場合がありますが、ノードの数が増えるとメモリ消費が大きくなることもあります。

2. Unicode Collation Algorithm (UCA)

Unicode Collation Algorithm (UCA) は、Unicode文字列を言語固有の規則に従ってソートするための標準アルゴリズムです。異なる言語では、文字の順序、アクセント記号の扱い、大文字・小文字の区別などが異なります。UCAは、これらの複雑なルールを処理し、一貫したソート順序を提供します。

• 照合要素（Collation Elements）: UCAは、各文字または文字シーケンスを「照合要素」のシーケンスに変換します。これらの要素は、プライマリ、セカンダリ、ターシャリなどのレベルを持ち、それぞれ異なる重要度で比較されます。
• データテーブル: UCAの実装には、各Unicodeコードポイントに対応する照合要素を定義する大規模なデータテーブルが必要です。このデータテーブルは、トライのような効率的なデータ構造に格納されることが一般的です。

3. Go言語の exp パッケージ

Go言語の標準ライブラリには、安定版の機能が含まれていますが、exp（experimental）パッケージは、まだ実験段階にあるか、将来的に標準ライブラリに統合される可能性のある機能を提供します。これらのパッケージは、APIが変更される可能性があり、本番環境での使用には注意が必要です。

• exp/locale/collate: このパッケージは、Go言語におけるUnicode Collation Algorithmの実装を提供します。文字列の照合（ソート）機能を実現するために使用されます。
• exp/locale/collate/build: このサブパッケージは、照合に必要なデータ構造（特にトライ）を構築するためのツールやロジックを含んでいます。このコミットが修正しているのは、この構築プロセスの一部です。

技術的詳細

このコミットの核心は、trieNode 構造体の変更と、それに伴うトライ構築ロジックの調整です。

trieNode 構造体の変更

変更前:

type trieNode struct {
	index []*trieNode
	value []uint32
	b     byte
	ref   uint16 // 単一の参照フィールド
}

変更後:

type trieNode struct {
	index    []*trieNode
	value    []uint32
	b        byte
	refValue uint16 // 値ブロックへの参照
	refIndex uint16 // インデックスブロックへの参照
}

以前は ref という単一の uint16 フィールドで参照を管理していましたが、これが refValue と refIndex の2つのフィールドに分割されました。これにより、ノードが参照する「値のブロック」と「次のインデックスブロック」を個別に管理できるようになります。これは、特にトライの最初のバイトのブロックが、値とインデックスブロックに対して異なるオフセットを持つ必要があるという問題に対応するための重要な変更です。

computeOffsets 関数の変更

computeOffsets 関数は、トライのノードが参照するブロックのオフセットを計算し、重複するブロックを検出して共有するためのハッシュベースの最適化を行います。

• インデックスブロックの処理: 変更前は、子ノード nn の ref を直接ハッシュ計算に使用していました。 変更後は、nn.refIndex と nn.refValue の両方をハッシュ計算に含めるようになりました。これにより、インデックスブロックのハッシュが、そのブロックが参照する値とインデックスの両方の特性を反映するようになります。 また、n.ref = uint16(len(b.lookupBlocks)) - blockOffset だった部分が n.refIndex = uint16(len(b.lookupBlocks)) - blockOffset に変更され、インデックスブロックの参照が refIndex に明示的に格納されるようになりました。

• 値ブロックの処理: 変更前は、値ブロックのハッシュ計算後、n.ref = uint16(len(b.valueBlocks)) - blockOffset で参照を格納していました。 変更後は、n.refValue = uint16(len(b.valueBlocks)) - blockOffset に変更され、値ブロックの参照が refValue に格納されます。さらに、n.refIndex = n.refValue という行が追加され、値ブロックの場合、インデックス参照も値参照と同じになるように設定されます。これは、値ブロックがそれ自体で終端であり、次のインデックスブロックを持たないため、インデックス参照も値ブロック自身を指すようにすることで一貫性を保つためと考えられます。

addStartValueBlock 関数の変更

この関数は、トライの開始点となる値ブロックを追加する際に使用されます。 変更前は n.ref = uint16(len(b.valueBlocks)) で参照を格納し、return n.ref で返していました。 変更後は n.refValue = uint16(len(b.valueBlocks)) に変更され、n.refIndex = n.refValue が追加されます。戻り値も n.refValue に変更されています。これにより、開始値ブロックも refValue と refIndex を適切に設定するようになります。

genLookupBlock 関数の変更

この関数は、最終的なトライのルックアップブロックを生成する際に使用されます。 変更前は v = nn.ref と単一の参照を使用していました。 変更後は、if n.index != nil { v = nn.refIndex } else { v = nn.refValue } という条件分岐が追加されました。これは、現在のノードがインデックスブロックであるか（n.index != nil）、それとも値ブロックであるかによって、子ノードの refIndex または refValue のどちらを参照すべきかを適切に選択するためです。これにより、生成されるルックアップテーブルが正しい参照を持つことが保証されます。

addTrie 関数の変更

この関数は、トライ全体を構築し、そのハンドルを返します。 変更前は h.lookupStart = n.ref - 1 でルックアップの開始オフセットを設定していました。 変更後は h.lookupStart = n.refIndex - 1 に変更され、ルックアップの開始が refIndex を基に設定されるようになりました。これは、ルックアップが主にインデックスブロックを辿るため、refIndex を使用するのが適切であることを示しています。

これらの変更は全体として、トライノードが値とインデックスブロックへの参照を明確に区別できるようにし、トライ構築ロジックがこの区別を適切に処理するようにすることで、照合データの正確性と安定性を向上させています。

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

--- a/src/pkg/exp/locale/collate/build/trie.go
+++ b/src/pkg/exp/locale/collate/build/trie.go
@@ -35,10 +35,11 @@ type trie struct {
 
 // trieNode is the intermediate trie structure used for generating a trie.
 type trieNode struct {
-	index []*trieNode
-	value []uint32
-	b     byte
-	ref   uint16
+	index    []*trieNode
+	value    []uint32
+	b        byte
+	refValue uint16
+	refIndex uint16
 }
 
 func newNode() *trieNode {
@@ -108,18 +109,20 @@ func (b *trieBuilder) computeOffsets(n *trieNode) *trieNode {
 	hasher := fnv.New32()
 	if n.index != nil {
 		for i, nn := range n.index {
-			v := uint16(0)
+			var vi, vv uint16
 			if nn != nil {
 				nn = b.computeOffsets(nn)
 				n.index[i] = nn
-				v = nn.ref
+				vi = nn.refIndex
+				vv = nn.refValue
 			}
-			hasher.Write([]byte{byte(v >> 8), byte(v)})\n
+			hasher.Write([]byte{byte(vi >> 8), byte(vi)})
+			hasher.Write([]byte{byte(vv >> 8), byte(vv)})
 		}
 		h := hasher.Sum32()
 		nn, ok := b.lookupBlockIdx[h]
 		if !ok {
-			n.ref = uint16(len(b.lookupBlocks)) - blockOffset
+			n.refIndex = uint16(len(b.lookupBlocks)) - blockOffset
 			b.lookupBlocks = append(b.lookupBlocks, n)
 			b.lookupBlockIdx[h] = n
 		} else {
@@ -132,7 +135,8 @@ func (b *trieBuilder) computeOffsets(n *trieNode) *trieNode {
 		h := hasher.Sum32()
 		nn, ok := b.valueBlockIdx[h]
 		if !ok {
-			n.ref = uint16(len(b.valueBlocks)) - blockOffset
+			n.refValue = uint16(len(b.valueBlocks)) - blockOffset
+			n.refIndex = n.refValue
 			b.valueBlocks = append(b.valueBlocks, n)
 			b.valueBlockIdx[h] = n
 		} else {
@@ -150,7 +154,8 @@ func (b *trieBuilder) addStartValueBlock(n *trieNode) uint16 {
 	h := hasher.Sum32()
 	nn, ok := b.valueBlockIdx[h]
 	if !ok {
-		n.ref = uint16(len(b.valueBlocks))
+		n.refValue = uint16(len(b.valueBlocks))
+		n.refIndex = n.refValue
 		b.valueBlocks = append(b.valueBlocks, n)
 		// Add a dummy block to accommodate the double block size.
 		b.valueBlocks = append(b.valueBlocks, nil)
@@ -158,7 +163,7 @@ func (b *trieBuilder) addStartValueBlock(n *trieNode) uint16 {
 	} else {
 		n = nn
 	}
-	return n.ref
+	return n.refValue
 }
 
 func genValueBlock(t *trie, n *trieNode) {
@@ -173,7 +178,11 @@ func genLookupBlock(t *trie, n *trieNode) {
 	for _, nn := range n.index {
 		v := uint16(0)
 		if nn != nil {
-			v = nn.ref
+			if n.index != nil {
+				v = nn.refIndex
+			} else {
+				v = nn.refValue
+			}
 		}
 		t.index = append(t.index, v)
 	}
@@ -192,7 +201,7 @@ func (b *trieBuilder) addTrie(n *trieNode) *trieHandle {\n 	}\n 	n = b.computeOffsets(n)\n 	// Offset by one extra block as the first byte starts at 0xC0 instead of 0x80.\n-\th.lookupStart = n.ref - 1
+\th.lookupStart = n.refIndex - 1
 	return h
 }
 

コアとなるコードの解説

このコミットの主要な変更は、trieNode 構造体における参照の分離と、それに伴うトライ構築ロジックの適応です。

1. trieNode 構造体の変更:

   • ref uint16 フィールドが削除され、代わりに refValue uint16 と refIndex uint16 の2つのフィールドが追加されました。
   • これは、トライノードが「値ブロック」と「次のインデックスブロック」への参照を個別に持つ必要があるという、以前の設計上の欠陥を修正するためのものです。特に、照合データでは、あるノードが直接的な値を持つ場合と、さらに深いインデックス構造を持つ場合があり、これらの参照が混同されると問題が発生していました。

2. computeOffsets 関数の変更:

   • この関数は、トライのノードが参照するブロックのオフセットを計算し、重複するブロックを共有することでメモリ使用量を最適化します。
   • 子ノードのハッシュ計算において、以前は単一の nn.ref を使用していましたが、変更後は nn.refIndex と nn.refValue の両方をハッシュに含めるようになりました。これにより、ブロックの同一性判定がより正確になり、値とインデックスの参照の違いが考慮されるようになりました。
   • n.ref への代入が n.refIndex または n.refValue への代入に置き換えられ、それぞれの参照が適切なフィールドに格納されるようになりました。特に、値ブロックの場合には n.refIndex = n.refValue とすることで、インデックス参照も値参照と同じになるように設定されています。

3. addStartValueBlock 関数の変更:

   • この関数は、トライの開始点となる値ブロックを追加する際に使用されます。
   • ここでも、n.ref への代入が n.refValue と n.refIndex への代入に置き換えられ、戻り値も n.refValue に変更されました。これにより、開始値ブロックも新しい参照モデルに準拠するようになりました。

4. genLookupBlock 関数の変更:

   • この関数は、最終的なルックアップテーブルを生成します。
   • 子ノードの参照 v を取得する際に、if n.index != nil { v = nn.refIndex } else { v = nn.refValue } という条件分岐が導入されました。これは、現在のノードがインデックスブロックを指しているのか、それとも値ブロックを指しているのかによって、子ノードの refIndex と refValue のどちらを使用すべきかを適切に判断するためです。これにより、生成されるルックアップテーブルが常に正しい参照を持つことが保証されます。

5. addTrie 関数の変更:

   • トライ全体の構築を管理するこの関数では、ルックアップの開始オフセットを設定する際に、以前の n.ref ではなく n.refIndex を使用するようになりました。これは、ルックアッププロセスが主にインデックスブロックを辿るため、refIndex を参照するのが論理的に正しいからです。

これらの変更は、トライデータ構造の内部表現をより正確にし、特に照合データのように複雑な参照関係を持つ場合に発生する可能性のあるバグを修正します。これにより、Go言語の国際化機能における照合の正確性と堅牢性が大幅に向上しました。

関連リンク

• Go Collation CL: https://golang.org/cl/6737057
• Go言語の exp/locale パッケージに関するドキュメント（当時のもの、または関連する最新情報）:
  • Go言語の公式ドキュメントやGoDocで golang.org/x/text/collate を検索すると、現在の照合パッケージに関する情報が見つかる可能性があります。このコミットは exp パッケージ内の古いバージョンに関するものですが、概念は共通しています。

参考にした情報源リンク

• Unicode Collation Algorithm (UCA): https://unicode.org/reports/tr10/
• Trie (データ構造) - Wikipedia: https://ja.wikipedia.org/wiki/Trie
• Go言語の exp パッケージに関する一般的な情報（当時のGoのリリースノートやブログ記事など）
• Go言語の fnv パッケージ（ハッシュ関数）: https://pkg.go.dev/hash/fnv
• Go言語の uint16 型に関する情報（Go言語の基本型）```markdown

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

このコミットは、Go言語の実験的なパッケージ exp/locale/collate/build 内の trie.go ファイルに対する変更です。具体的には、トライ（Trie）データ構造の構築ロジックにおけるバグ修正が目的です。この修正は、特に最初のバイトのブロックが値とインデックスブロックに対して異なるインデックスを必要とする問題に対処し、多数の回帰（regression）を修正します。

コミット

commit 6653d76ef6c243b2061325c09e9628735218378c
Author: Marcel van Lohuizen <mpvl@golang.org>
Date:   Wed Oct 24 11:41:05 2012 +0200

    exp/locale/collate/build: fixed problem where blocks for first byte need
    different indexes for values and index blocks. Fixes many regressions.
    
    R=r
    CC=golang-dev
    https://golang.org/cl/6737057

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

https://github.com/golang/go/commit/6653d76ef6c243b2061325c09e9628735218378c

元コミット内容

exp/locale/collate/build: 最初のバイトのブロックが値とインデックスブロックに対して異なるインデックスを必要とする問題を修正しました。これにより、多くの回帰が修正されます。

変更の背景

このコミットの背景には、Go言語の国際化（i18n）およびローカライゼーション（l10n）機能の一部である、照合（collation）データの構築プロセスにおける根本的な問題がありました。照合とは、文字列を特定のロケール（言語や地域）の規則に従ってソートするプロセスです。このプロセスでは、効率的なルックアップのためにトライ（Trie）データ構造がよく使用されます。

問題は、トライの構築時に、特に文字列の最初のバイト（または最初の文字）に対応するブロックが、そのブロックが参照する「値」のインデックスと「次のインデックスブロック」のインデックスを同じように扱っていた点にありました。しかし、実際にはこれらのインデックスは異なる参照を持つ必要がありました。この不一致が原因で、照合ロジックにおいて多数の誤った動作（回帰）が発生していました。

このコミットは、この設計上の欠陥を修正し、値とインデックスブロックの参照を分離することで、照合データの正確な構築を保証し、既存の回帰を解消することを目的としています。

前提知識の解説

1. トライ（Trie）データ構造

トライ（Trie、またはプレフィックスツリー）は、キーが文字列である連想配列を実装するためによく使われるツリーデータ構造です。各ノードは文字列のプレフィックスに対応し、ルートからノードへのパスがキーを表します。トライは、文字列の検索、プレフィックス検索、ソートなどに非常に効率的です。

• ノード: 各ノードは、通常、子ノードへのポインタの配列（またはマップ）と、そのノードが完全なキーの終端である場合に格納される値（または値への参照）を持ちます。
• 効率性: 文字列の長さ L に対して、検索や挿入の操作が O(L) の時間計算量で行えます。これはハッシュテーブルよりも高速な場合があります。
• メモリ使用量: 共通のプレフィックスを持つ文字列が多いため、メモリを節約できる場合がありますが、ノードの数が増えるとメモリ消費が大きくなることもあります。

2. Unicode Collation Algorithm (UCA)

Unicode Collation Algorithm (UCA) は、Unicode文字列を言語固有の規則に従ってソートするための標準アルゴリズムです。異なる言語では、文字の順序、アクセント記号の扱い、大文字・小文字の区別などが異なります。UCAは、これらの複雑なルールを処理し、一貫したソート順序を提供します。

• 照合要素（Collation Elements）: UCAは、各文字または文字シーケンスを「照合要素」のシーケンスに変換します。これらの要素は、プライマリ、セカンダリ、ターシャリなどのレベルを持ち、それぞれ異なる重要度で比較されます。
• データテーブル: UCAの実装には、各Unicodeコードポイントに対応する照合要素を定義する大規模なデータテーブルが必要です。このデータテーブルは、トライのような効率的なデータ構造に格納されることが一般的です。

3. Go言語の exp パッケージ

Go言語の標準ライブラリには、安定版の機能が含まれていますが、exp（experimental）パッケージは、まだ実験段階にあるか、将来的に標準ライブラリに統合される可能性のある機能を提供します。これらのパッケージは、APIが変更される可能性があり、本番環境での使用には注意が必要です。

• exp/locale/collate: このパッケージは、Go言語におけるUnicode Collation Algorithmの実装を提供します。文字列の照合（ソート）機能を実現するために使用されます。
• exp/locale/collate/build: このサブパッケージは、照合に必要なデータ構造（特にトライ）を構築するためのツールやロジックを含んでいます。このコミットが修正しているのは、この構築プロセスの一部です。

技術的詳細

このコミットの核心は、trieNode 構造体の変更と、それに伴うトライ構築ロジックの調整です。

trieNode 構造体の変更

変更前:

type trieNode struct {
	index []*trieNode
	value []uint32
	b     byte
	ref   uint16 // 単一の参照フィールド
}

変更後:

type trieNode struct {
	index    []*trieNode
	value    []uint32
	b        byte
	refValue uint16 // 値ブロックへの参照
	refIndex uint16 // インデックスブロックへの参照
}

以前は ref という単一の uint16 フィールドで参照を管理していましたが、これが refValue と refIndex の2つのフィールドに分割されました。これにより、ノードが参照する「値のブロック」と「次のインデックスブロック」を個別に管理できるようになります。これは、特にトライの最初のバイトのブロックが、値とインデックスブロックに対して異なるオフセットを持つ必要があるという問題に対応するための重要な変更です。

computeOffsets 関数の変更

computeOffsets 関数は、トライのノードが参照するブロックのオフセットを計算し、重複するブロックを検出して共有するためのハッシュベースの最適化を行います。

• インデックスブロックの処理: 変更前は、子ノード nn の ref を直接ハッシュ計算に使用していました。 変更後は、nn.refIndex と nn.refValue の両方をハッシュ計算に含めるようになりました。これにより、インデックスブロックのハッシュが、そのブロックが参照する値とインデックスの両方の特性を反映するようになります。 また、n.ref = uint16(len(b.lookupBlocks)) - blockOffset だった部分が n.refIndex = uint16(len(b.lookupBlocks)) - blockOffset に変更され、インデックスブロックの参照が refIndex に明示的に格納されるようになりました。

• 値ブロックの処理: 変更前は、値ブロックのハッシュ計算後、n.ref = uint16(len(b.valueBlocks)) - blockOffset で参照を格納していました。 変更後は、n.refValue = uint16(len(b.valueBlocks)) - blockOffset に変更され、値ブロックの参照が refValue に格納されます。さらに、n.refIndex = n.refValue という行が追加され、値ブロックの場合、インデックス参照も値参照と同じになるように設定されます。これは、値ブロックがそれ自体で終端であり、次のインデックスブロックを持たないため、インデックス参照も値ブロック自身を指すようにすることで一貫性を保つためと考えられます。

addStartValueBlock 関数の変更

この関数は、トライの開始点となる値ブロックを追加する際に使用されます。 変更前は n.ref = uint16(len(b.valueBlocks)) で参照を格納し、return n.ref で返していました。 変更後は n.refValue = uint16(len(b.valueBlocks)) に変更され、n.refIndex = n.refValue が追加されます。戻り値も n.refValue に変更されています。これにより、開始値ブロックも refValue と refIndex を適切に設定するようになります。

genLookupBlock 関数の変更

この関数は、最終的なトライのルックアップブロックを生成する際に使用されます。 変更前は v = nn.ref と単一の参照を使用していました。 変更後は、if n.index != nil { v = nn.refIndex } else { v = nn.refValue } という条件分岐が追加されました。これは、現在のノードがインデックスブロックであるか（n.index != nil）、それとも値ブロックであるかによって、子ノードの refIndex または refValue のどちらを参照すべきかを適切に選択するためです。これにより、生成されるルックアップテーブルが正しい参照を持つことが保証されます。

addTrie 関数の変更

この関数は、トライ全体を構築し、そのハンドルを返します。 変更前は h.lookupStart = n.ref - 1 でルックアップの開始オフセットを設定していました。 変更後は h.lookupStart = n.refIndex - 1 に変更され、ルックアップの開始が refIndex を基に設定されるようになりました。これは、ルックアップが主にインデックスブロックを辿るため、refIndex を使用するのが適切であることを示しています。

これらの変更は全体として、トライノードが値とインデックスブロックへの参照を明確に区別できるようにし、トライ構築ロジックがこの区別を適切に処理するようにすることで、照合データの正確性と安定性を向上させています。

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

--- a/src/pkg/exp/locale/collate/build/trie.go
+++ b/src/pkg/exp/locale/collate/build/trie.go
@@ -35,10 +35,11 @@ type trie struct {
 
 // trieNode is the intermediate trie structure used for generating a trie.
 type trieNode struct {
-	index []*trieNode
-	value []uint32
-	b     byte
-	ref   uint16
+	index    []*trieNode
+	value    []uint32
+	b        byte
+	refValue uint16
+	refIndex uint16
 }
 
 func newNode() *trieNode {
@@ -108,18 +109,20 @@ func (b *trieBuilder) computeOffsets(n *trieNode) *trieNode {
 	hasher := fnv.New32()
 	if n.index != nil {
 		for i, nn := range n.index {
-			v := uint16(0)
+			var vi, vv uint16
 			if nn != nil {
 				nn = b.computeOffsets(nn)
 				n.index[i] = nn
-				v = nn.ref
+				vi = nn.refIndex
+				vv = nn.refValue
 			}
-			hasher.Write([]byte{byte(v >> 8), byte(v)})\n
+			hasher.Write([]byte{byte(vi >> 8), byte(vi)})
+			hasher.Write([]byte{byte(vv >> 8), byte(vv)})
 		}
 		h := hasher.Sum32()
 		nn, ok := b.lookupBlockIdx[h]
 		if !ok {
-			n.ref = uint16(len(b.lookupBlocks)) - blockOffset
+			n.refIndex = uint16(len(b.lookupBlocks)) - blockOffset
 			b.lookupBlocks = append(b.lookupBlocks, n)
 			b.lookupBlockIdx[h] = n
 		} else {
@@ -132,7 +135,8 @@ func (b *trieBuilder) computeOffsets(n *trieNode) *trieNode {
 		h := hasher.Sum32()
 		nn, ok := b.valueBlockIdx[h]
 		if !ok {
-			n.ref = uint16(len(b.valueBlocks)) - blockOffset
+			n.refValue = uint16(len(b.valueBlocks)) - blockOffset
+			n.refIndex = n.refValue
 			b.valueBlocks = append(b.valueBlocks, n)
 			b.valueBlockIdx[h] = n
 		} else {
@@ -150,7 +154,8 @@ func (b *trieBuilder) addStartValueBlock(n *trieNode) uint16 {
 	h := hasher.Sum32()
 	nn, ok := b.valueBlockIdx[h]
 	if !ok {
-		n.ref = uint16(len(b.valueBlocks))
+		n.refValue = uint16(len(b.valueBlocks))
+		n.refIndex = n.refValue
 		b.valueBlocks = append(b.valueBlocks, n)
 		// Add a dummy block to accommodate the double block size.
 		b.valueBlocks = append(b.valueBlocks, nil)
@@ -158,7 +163,7 @@ func (b *trieBuilder) addStartValueBlock(n *trieNode) uint16 {
 	} else {
 		n = nn
 	}
-	return n.ref
+	return n.refValue
 }
 
 func genValueBlock(t *trie, n *trieNode) {
@@ -173,7 +178,11 @@ func genLookupBlock(t *trie, n *trieNode) {
 	for _, nn := range n.index {
 		v := uint16(0)
 		if nn != nil {
-			v = nn.ref
+			if n.index != nil {
+				v = nn.refIndex
+			} else {
+				v = nn.refValue
+			}
 		}
 		t.index = append(t.index, v)
 	}
@@ -192,7 +201,7 @@ func (b *trieBuilder) addTrie(n *trieNode) *trieHandle {\n 	}\n 	n = b.computeOffsets(n)\n 	// Offset by one extra block as the first byte starts at 0xC0 instead of 0x80.\n-\th.lookupStart = n.ref - 1
+\th.lookupStart = n.refIndex - 1
 	return h
 }
 

コアとなるコードの解説

このコミットの主要な変更は、trieNode 構造体における参照の分離と、それに伴うトライ構築ロジックの適応です。

1. trieNode 構造体の変更:

   • ref uint16 フィールドが削除され、代わりに refValue uint16 と refIndex uint16 の2つのフィールドが追加されました。
   • これは、トライノードが「値ブロック」と「次のインデックスブロック」への参照を個別に持つ必要があるという、以前の設計上の欠陥を修正するためのものです。特に、照合データでは、あるノードが直接的な値を持つ場合と、さらに深いインデックス構造を持つ場合があり、これらの参照が混同されると問題が発生していました。

2. computeOffsets 関数の変更:

   • この関数は、トライのノードが参照するブロックのオフセットを計算し、重複するブロックを共有することでメモリ使用量を最適化します。
   • 子ノードのハッシュ計算において、以前は単一の nn.ref を使用していましたが、変更後は nn.refIndex と nn.refValue の両方をハッシュに含めるようになりました。これにより、ブロックの同一性判定がより正確になり、値とインデックスの参照の違いが考慮されるようになりました。
   • n.ref への代入が n.refIndex または n.refValue への代入に置き換えられ、それぞれの参照が適切なフィールドに格納されるようになりました。特に、値ブロックの場合には n.refIndex = n.refValue とすることで、インデックス参照も値参照と同じになるように設定されています。

3. addStartValueBlock 関数の変更:

   • この関数は、トライの開始点となる値ブロックを追加する際に使用されます。
   • ここでも、n.ref への代入が n.refValue と n.refIndex への代入に置き換えられ、戻り値も n.refValue に変更されました。これにより、開始値ブロックも新しい参照モデルに準拠するようになりました。

4. genLookupBlock 関数の変更:

   • この関数は、最終的なルックアップテーブルを生成します。
   • 子ノードの参照 v を取得する際に、if n.index != nil { v = nn.refIndex } else { v = nn.refValue } という条件分岐が導入されました。これは、現在のノードがインデックスブロックを指しているのか、それとも値ブロックを指しているのかによって、子ノードの refIndex と refValue のどちらを使用すべきかを適切に判断するためです。これにより、生成されるルックアップテーブルが常に正しい参照を持つことが保証されます。

5. addTrie 関数の変更:

   • トライ全体の構築を管理するこの関数では、ルックアップの開始オフセットを設定する際に、以前の n.ref ではなく n.refIndex を使用するようになりました。これは、ルックアッププロセスが主にインデックスブロックを辿るため、refIndex を参照するのが論理的に正しいからです。

これらの変更は、トライデータ構造の内部表現をより正確にし、特に照合データのように複雑な参照関係を持つ場合に発生する可能性のあるバグを修正します。これにより、Go言語の国際化機能における照合の正確性と堅牢性が大幅に向上しました。

関連リンク

• Go Collation CL: https://golang.org/cl/6737057
• Go言語の exp/locale パッケージに関するドキュメント（当時のもの、または関連する最新情報）:
  • Go言語の公式ドキュメントやGoDocで golang.org/x/text/collate を検索すると、現在の照合パッケージに関する情報が見つかる可能性があります。このコミットは exp パッケージ内の古いバージョンに関するものですが、概念は共通しています。

参考にした情報源リンク

• Unicode Collation Algorithm (UCA): https://unicode.org/reports/tr10/
• Trie (データ構造) - Wikipedia: https://ja.wikipedia.org/wiki/Trie
• Go言語の exp パッケージに関する一般的な情報（当時のGoのリリースノートやブログ記事など）
• Go言語の fnv パッケージ（ハッシュ関数）: https://pkg.go.dev/hash/fnv
• Go言語の uint16 型に関する情報（Go言語の基本型）