Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Go言語の実験的なUnicode正規化パッケージ exp/norm における微妙なバグを修正するものです。具体的には、Goのマップイテレーションがランダムなオフセットを持つことによって引き起こされた、テーブル生成の非決定性を解消し、出力されるテーブルデータが予測可能になるように変更が加えられました。これにより、正規化処理の正確性と安定性が向上しています。

コミット

commit 110964ac81193dac22c56456026bc5b687a72bc1
Author: Marcel van Lohuizen <mpvl@golang.org>
Date:   Mon Jan 23 19:36:52 2012 +0100

    exp/norm: fixes a subtle bug introduced by change 10087: random offset
    for map iteration. New code makes table output predictable and fixes
    bug.

    R=rsc, r
    CC=golang-dev
    https://golang.org/cl/5573044

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

https://github.com/golang/go/commit/110964ac81193dac22c56456026bc5b687a72bc1

元コミット内容

exp/norm: 変更 10087 によって導入された、マップイテレーションのランダムオフセットに起因する微妙なバグを修正。新しいコードはテーブル出力を予測可能にし、バグを修正する。

変更の背景

この変更は、Go言語のexp/normパッケージにおける、Unicode正規化テーブルの生成プロセスに潜んでいたバグを修正するために行われました。Go言語のマップ（map）は、意図的にイテレーション順序がランダム化されています。これは、開発者が特定のイテレーション順序に依存するようなコードを書くことを防ぎ、より堅牢なプログラムを促進するための設計上の決定です。しかし、このランダム化が、exp/normパッケージ内でUnicode正規化に必要なデータテーブルを生成する際に、予期せぬ非決定的な挙動を引き起こしていました。

具体的には、以前の変更（コミット10087）によって、テーブル生成ロジックがマップのイテレーション順序に暗黙的に依存する形になってしまい、その結果、生成されるテーブルの内容が実行ごとに異なる可能性が生じていました。このような非決定性は、Unicode正規化のような厳密な仕様に基づく処理においては致命的であり、異なる環境や実行タイミングで異なる正規化結果を生み出す原因となります。このコミットは、この非決定性を排除し、テーブル生成プロセスを予測可能で安定したものにすることを目的としています。

前提知識の解説

Unicode正規化 (Unicode Normalization)

Unicode正規化とは、異なるバイト列で表現されうる同じ意味を持つ文字列を、一意のバイト列に変換するプロセスです。例えば、アクセント付きの文字「é」は、単一のコードポイント（U+00E9）で表現することもできますし、「e」と結合文字のアクセント（U+0065 U+0301）の組み合わせで表現することもできます。これらは見た目上は同じですが、バイト列としては異なります。正規化は、このような差異を吸収し、文字列の比較や検索を正確に行うために不可欠です。

Unicodeには主に以下の4つの正規化形式があります。

  • NFC (Normalization Form Canonical Composition): 正準等価な文字を可能な限り合成します。最も一般的に使用される形式です。
  • NFD (Normalization Form Canonical Decomposition): 正準等価な文字を可能な限り分解します。
  • NFKC (Normalization Form Compatibility Composition): 互換等価な文字も合成します。見た目が似ているが意味が異なる文字（例: 全角数字と半角数字）も同じ形式に変換するため、情報が失われる可能性があります。
  • NFKD (Normalization Form Compatibility Decomposition): 互換等価な文字も分解します。

exp/normパッケージは、これらの正規化処理に必要なデータ（どの文字がどのように分解・合成されるかなど）を内部に持っています。これらのデータは通常、Unicode Consortiumが提供するデータに基づいて生成されます。

Go言語のマップイテレーションのランダム化

Go言語の組み込み型であるmap（ハッシュマップ）は、キーと値のペアを格納する順序なしのコレクションです。Goの仕様では、マップのイテレーション順序は保証されていません。さらに、Go 1.0以降、マップのイテレーション順序は意図的にランダム化されています。これは、開発者がマップの順序に依存するバグを早期に発見し、修正することを促すためのものです。もしイテレーション順序が常に同じであれば、開発者はその順序に依存したコードを書いてしまい、将来的にGoのランタイムがマップの実装を変更した際に予期せぬバグが発生する可能性があります。このランダム化は、マップの内部ハッシュテーブルの開始オフセットをランダムにすることで実現されています。

トライ木 (Trie)

トライ木（プレフィックス木、デジタル木とも呼ばれる）は、文字列の集合を効率的に格納し、検索するために使用される木構造のデータ構造です。各ノードは文字列のプレフィックスに対応し、子ノードへのエッジは次の文字を表します。これにより、共通のプレフィックスを持つ文字列を効率的に表現できます。Unicode正規化の文脈では、文字の分解・合成ルールを高速にルックアップするために、トライ木のようなデータ構造が利用されることがあります。

valueRange 構造体とスパース配列

コミットで変更されているvalueRange構造体は、おそらくUnicodeのコードポイント範囲とそれに対応する値（例えば、分解されたコードポイントや正規化情報）を表現するためのものです。loとhiフィールドは範囲の下限と上限を示し、valueフィールドは関連するデータを示します。

nfcDecompSparseValuesやnfkcDecompSparseValuesといった配列は、スパース配列（疎な配列）として実装されていると考えられます。これは、データがまばらに存在するような場合に、メモリを節約するために、実際に値が存在する部分だけを格納する手法です。通常、このような配列は、インデックスを実際のデータ位置にマッピングするための別のオフセット配列（例: nfkcDecompSparseOffset）と組み合わせて使用されます。

技術的詳細

このコミットの核心は、Goのマップイテレーションのランダム性によって引き起こされる、Unicode正規化テーブルの生成における非決定性を排除することです。

src/pkg/exp/norm/triegen.goは、Unicodeの正規化データからGoのソースコード（tables.go）を生成するツールです。このツールは、Unicodeのプロパティデータ（文字の分解マッピングなど）を読み込み、それを効率的なルックアップテーブル（トライ木やスパース配列など）に変換します。

問題は、triegen.go内のtrieNode.mostFrequentStride()関数にありました。この関数は、トライ木を最適化する際に、最も頻繁に出現する「ストライド」（連続する値のパターン）を見つけるために、内部でマップを使用していた可能性があります。Goのマップイテレーションがランダムであるため、この関数が返す「最も頻繁なストライド」の選択が、複数の同等な選択肢がある場合に非決定的なものとなっていました。その結果、生成されるtables.go内のデータ配列（nfcDecompSparseValues, nfkcDecompSparseValues, charInfoSparseValuesなど）の順序や内容が、実行ごとに微妙に異なる可能性がありました。

この非決定性は、tables.go内のvalueRange構造体のvalueフィールドが0x0005や0x0007のような非ゼロの値から0x0000に変更されている箇所に現れています。これは、特定のvalueRangeエントリが、以前はマップイテレーションのランダム性によって異なるvalueを持っていた可能性があることを示唆しています。0x0000に統一することで、これらのエントリが常に同じ初期値を持つようになり、テーブル生成の決定性が保証されます。

また、triegen.goのtrieNode.mostFrequentStride()関数内の比較ロジックが変更されています。

-		if cnt > maxc {
+		if cnt > maxc || (cnt == maxc && stride < maxs) {

以前は、単にcnt > maxc（カウントが最大値より大きい場合）でmaxsとmaxcを更新していました。これは、複数のストライドが同じ最大カウントを持つ場合に、マップイテレーションの順序に依存して、最初に現れたものが選択されることを意味します。新しいコードcnt > maxc || (cnt == maxc && stride < maxs)は、カウントが同じである場合には、より小さいstride値を持つものを優先的に選択するように変更されています。これにより、同等な選択肢がある場合でも、常に同じストライドが選択されるようになり、テーブル生成の決定性が保証されます。

この修正により、tables.go内のデータ配列のサイズもわずかに減少しています（例: nfkcDecompSparseValuesが605エントリから603エントリに、charInfoSparseValuesが760エントリから757エントリに）。これは、決定的なストライド選択によって、より効率的なトライ木の構造が生成され、冗長なエントリが削減されたことを示唆しています。最終的に、生成されるテーブルの合計サイズもわずかに減少しています（48756バイトから48736バイトへ）。

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

diff --git a/src/pkg/exp/norm/tables.go b/src/pkg/exp/norm/tables.go
index 55ff052dcb..9044a72fd4 100644
--- a/src/pkg/exp/norm/tables.go
+++ b/src/pkg/exp/norm/tables.go
@@ -2804,12 +2804,12 @@ var nfcDecompSparseValues = [341]valueRange{
 	{value: 0x0005, lo: 0x01},
 	{value: 0x068d, lo: 0xa2, hi: 0xa6},
 	// Block 0xc, offset 0xd
-	{value: 0x0005, lo: 0x03},
+	{value: 0x0000, lo: 0x03},
 	{value: 0x06ba, lo: 0x80, hi: 0x80},
 	{value: 0x06bf, lo: 0x82, hi: 0x82},
 	{value: 0x06c4, lo: 0x93, hi: 0x93},
 	// Block 0xd, offset 0xe
-	{value: 0x0007, lo: 0x03},
+	{value: 0x0000, lo: 0x03},
 	{value: 0x06c9, lo: 0xa9, hi: 0xa9},
 	{value: 0x06d0, lo: 0xb1, hi: 0xb1},
 	{value: 0x06d7, lo: 0xb4, hi: 0xb4},
@@ -2822,7 +2822,7 @@ var nfcDecompSparseValues = [341]valueRange{
 	{value: 0x0724, lo: 0x9c, hi: 0x9d},
 	{value: 0x0732, lo: 0x9f, hi: 0x9f},
 	// Block 0x10, offset 0x11
-	{value: 0x0007, lo: 0x02},
+	{value: 0x0000, lo: 0x02},
 	{value: 0x0739, lo: 0xb3, hi: 0xb3},
 	{value: 0x0740, lo: 0xb6, hi: 0xb6},
 	// Block 0x11, offset 0x12
@@ -2868,7 +2868,7 @@ var nfcDecompSparseValues = [341]valueRange{
 	{value: 0x0854, lo: 0xb5, hi: 0xb6},
 	{value: 0x086c, lo: 0xb8, hi: 0xb8},
 	// Block 0x1a, offset 0x1b
-	{value: 0x0007, lo: 0x07},
+	{value: 0x0000, lo: 0x07},
 	{value: 0x087d, lo: 0x81, hi: 0x81},
 	{value: 0x0884, lo: 0x93, hi: 0x93},
 	{value: 0x088b, lo: 0x9d, hi: 0x9d},
@@ -2880,7 +2880,7 @@ var nfcDecompSparseValues = [341]valueRange{
 	{value: 0x0000, lo: 0x01},
 	{value: 0x08ae, lo: 0xa6, hi: 0xa6},
 	// Block 0x1c, offset 0x1d
-	{value: 0x0007, lo: 0x08},
+	{value: 0x0000, lo: 0x08},
 	{value: 0x08b9, lo: 0x86, hi: 0x86},
 	{value: 0x08c0, lo: 0x88, hi: 0x88},
 	{value: 0x08c7, lo: 0x8a, hi: 0x8a},
@@ -2924,7 +2924,7 @@ var nfcDecompSparseValues = [341]valueRange{
 	{value: 0x0006, lo: 0x01},
 	{value: 0x15b1, lo: 0x8d, hi: 0x8f},
 	// Block 0x23, offset 0x24
-	{value: 0x0006, lo: 0x05},
+	{value: 0x0000, lo: 0x05},
 	{value: 0x15c3, lo: 0x84, hi: 0x84},
 	{value: 0x15c9, lo: 0x89, hi: 0x89},
 	{value: 0x15cf, lo: 0x8c, hi: 0x8c},
@@ -2960,7 +2960,7 @@ var nfcDecompSparseValues = [341]valueRange{
 	{value: 0x0000, lo: 0x01},
 	{value: 0x1814, lo: 0x9c, hi: 0x9c},
 	// Block 0x29, offset 0x2a
-	{value: 0x0007, lo: 0x0c},
+	{value: 0x0000, lo: 0x0c},
 	{value: 0x1c39, lo: 0x94, hi: 0x94},
 	{value: 0x1c4a, lo: 0x9e, hi: 0x9e},
 	{value: 0x1c58, lo: 0xac, hi: 0xac},
@@ -3084,7 +3084,7 @@ var nfcDecompSparseValues = [341]valueRange{
 	{value: 0x3191, lo: 0x83, hi: 0x84},
 	{value: 0x319b, lo: 0x86, hi: 0x8e},
 	// Block 0x33, offset 0x34
-	{value: 0x0009, lo: 0x03},
+	{value: 0x0000, lo: 0x03},
 	{value: 0x3a73, lo: 0x9a, hi: 0x9a},
 	{value: 0x3a7c, lo: 0x9c, hi: 0x9c},
 	{value: 0x3a85, lo: 0xab, hi: 0xab},
@@ -3897,10 +3897,10 @@ var nfkcDecompValues = [4224]uint16{
 }
 
 // nfkcDecompSparseOffset: 93 entries, 186 bytes
-var nfkcDecompSparseOffset = []uint16{0x0, 0xc, 0x16, 0x1e, 0x24, 0x27, 0x31, 0x37, 0x3e, 0x44, 0x4c, 0x59, 0x60, 0x66, 0x6e, 0x70, 0x72, 0x74, 0x78, 0x7c, 0x7e, 0x82, 0x85, 0x88, 0x8c, 0x8e, 0x90, 0x92, 0x96, 0x98, 0x9c, 0x9e, 0xa0, 0xa2, 0xa4, 0xae, 0xb6, 0xb8, 0xba, 0xc3, 0xc6, 0xcd, 0xd8, 0xe6, 0xf4, 0xfe, 0x102, 0x104, 0x10e, 0x11a, 0x11f, 0x122, 0x124, 0x126, 0x129, 0x12b, 0x12d, 0x12f, 0x131, 0x133, 0x135, 0x137, 0x139, 0x13b, 0x140, 0x14f, 0x15d, 0x15f, 0x161, 0x169, 0x179, 0x17b, 0x186, 0x18d, 0x198, 0x1a4, 0x1b5, 0x1c6, 0x1cd, 0x1de, 0x1ec, 0x1fa, 0x209, 0x21a, 0x21f, 0x22c, 0x230, 0x234, 0x238, 0x23a, 0x249, 0x24b, 0x24f}
+var nfkcDecompSparseOffset = []uint16{0x0, 0xc, 0x16, 0x1e, 0x24, 0x27, 0x31, 0x37, 0x3e, 0x44, 0x4c, 0x59, 0x60, 0x66, 0x6e, 0x70, 0x72, 0x74, 0x78, 0x7c, 0x7e, 0x82, 0x85, 0x88, 0x8c, 0x8e, 0x90, 0x92, 0x96, 0x98, 0x9c, 0x9e, 0xa0, 0xa2, 0xa4, 0xae, 0xb6, 0xb8, 0xba, 0xc3, 0xc6, 0xcd, 0xd8, 0xe6, 0xf4, 0xfe, 0x102, 0x104, 0x10c, 0x118, 0x11d, 0x120, 0x122, 0x124, 0x127, 0x129, 0x12b, 0x12d, 0x12f, 0x131, 0x133, 0x135, 0x137, 0x139, 0x13e, 0x14d, 0x15b, 0x15d, 0x15f, 0x167, 0x177, 0x179, 0x184, 0x18b, 0x196, 0x1a2, 0x1b3, 0x1c4, 0x1cb, 0x1dc, 0x1ea, 0x1f8, 0x207, 0x218, 0x21d, 0x22a, 0x22e, 0x232, 0x236, 0x238, 0x247, 0x249, 0x24d}
 
 // nfkcDecompSparseValues: 605 entries, 2420 bytes
-var nfkcDecompSparseValues = [605]valueRange{
+// nfkcDecompSparseValues: 603 entries, 2412 bytes
+var nfkcDecompSparseValues = [603]valueRange{
 	// Block 0x0, offset 0x1
 	{value: 0x0002, lo: 0x0b},
 	{value: 0x0001, lo: 0xa0, hi: 0xa0},
@@ -4035,12 +4035,12 @@ var nfkcDecompSparseValues = [605]valueRange{
 	{value: 0x0005, lo: 0x01},
 	{value: 0x06a6, lo: 0xb5, hi: 0xb8},
 	// Block 0x11, offset 0x12
-	{value: 0x0005, lo: 0x03},
+	{value: 0x0000, lo: 0x03},
 	{value: 0x06ba, lo: 0x80, hi: 0x80},
 	{value: 0x06bf, lo: 0x82, hi: 0x82},
 	{value: 0x06c4, lo: 0x93, hi: 0x93},
 	// Block 0x12, offset 0x13
-	{value: 0x0007, lo: 0x03},
+	{value: 0x0000, lo: 0x03},
 	{value: 0x06c9, lo: 0xa9, hi: 0xa9},
 	{value: 0x06d0, lo: 0xb1, hi: 0xb1},
 	{value: 0x06d7, lo: 0xb4, hi: 0xb4},
@@ -4053,7 +4053,7 @@ var nfkcDecompSparseValues = [605]valueRange{
 	{value: 0x0724, lo: 0x9c, hi: 0x9d},
 	{value: 0x0732, lo: 0x9f, hi: 0x9f},
 	// Block 0x15, offset 0x16
-	{value: 0x0007, lo: 0x02},
+	{value: 0x0000, lo: 0x02},
 	{value: 0x0739, lo: 0xb3, hi: 0xb3},
 	{value: 0x0740, lo: 0xb6, hi: 0xb6},
 	// Block 0x16, offset 0x17
@@ -4111,7 +4111,7 @@ var nfkcDecompSparseValues = [605]valueRange{
 	{value: 0x0854, lo: 0xb5, hi: 0xb7},
 	{value: 0x086c, lo: 0xb8, hi: 0xb9},
 	// Block 0x23, offset 0x24
-	{value: 0x0007, lo: 0x07},
+	{value: 0x0000, lo: 0x07},
 	{value: 0x087d, lo: 0x81, hi: 0x81},
 	{value: 0x0884, lo: 0x93, hi: 0x93},
 	{value: 0x088b, lo: 0x9d, hi: 0x9d},
@@ -4126,7 +4126,7 @@ var nfkcDecompSparseValues = [605]valueRange{
 	{value: 0x0000, lo: 0x01},
 	{value: 0x08b5, lo: 0xbc, hi: 0xbc},
 	// Block 0x26, offset 0x27
-	{value: 0x0007, lo: 0x08},
+	{value: 0x0000, lo: 0x08},
 	{value: 0x08b9, lo: 0x86, hi: 0x86},
 	{value: 0x08c0, lo: 0x88, hi: 0x88},
 	{value: 0x08c7, lo: 0x8a, hi: 0x8a},
@@ -4209,16 +4209,14 @@ var nfkcDecompSparseValues = [605]valueRange{
 	{value: 0x0006, lo: 0x01},
 	{value: 0x15b1, lo: 0x8d, hi: 0x8f},
 	// Block 0x2f, offset 0x30
-	{value: 0x0006, lo: 0x09},
+	{value: 0x0007, lo: 0x07},
 	{value: 0x15c3, lo: 0x84, hi: 0x84},
 	{value: 0x15c9, lo: 0x89, hi: 0x89},
 	{value: 0x15cf, lo: 0x8c, hi: 0x8c},
 	{value: 0x15d5, lo: 0xa4, hi: 0xa4},
 	{value: 0x15db, lo: 0xa6, hi: 0xa6},
-	{value: 0x15e1, lo: 0xac, hi: 0xac},
-	{value: 0x15e8, lo: 0xad, hi: 0xad},
-	{value: 0x15f2, lo: 0xaf, hi: 0xaf},
-	{value: 0x15f9, lo: 0xb0, hi: 0xb0},\n+\t{value: 0x15e1, lo: 0xac, hi: 0xad},\n+\t{value: 0x15f2, lo: 0xaf, hi: 0xb0},\n \t// Block 0x30, offset 0x31
 	{value: 0x0006, lo: 0x0b},
 	{value: 0x1603, lo: 0x81, hi: 0x81},
@@ -4249,9 +4247,9 @@ var nfkcDecompSparseValues = [605]valueRange{
 	{value: 0x0000, lo: 0x01},
 	{value: 0x17fc, lo: 0x8c, hi: 0x8c},
 	// Block 0x35, offset 0x36
-	{value: 0x0004, lo: 0x02},
-	{value: 0x1809, lo: 0xb4, hi: 0xb5},
-	{value: 0x1810, lo: 0xb6, hi: 0xb6},
+	{value: 0x0003, lo: 0x02},
+	{value: 0x1809, lo: 0xb4, hi: 0xb4},
+	{value: 0x180d, lo: 0xb5, hi: 0xb6},
 	// Block 0x36, offset 0x37
 	{value: 0x0000, lo: 0x01},
 	{value: 0x1814, lo: 0x9c, hi: 0x9c},
@@ -4280,17 +4278,17 @@ var nfkcDecompSparseValues = [605]valueRange{
 	{value: 0x0004, lo: 0x01},
 	{value: 0x1b26, lo: 0x80, hi: 0x95},
 	// Block 0x3f, offset 0x40
-	{value: 0x0300, lo: 0x04},
+	{value: 0x0004, lo: 0x04},
 	{value: 0x0001, lo: 0x80, hi: 0x80},
 	{value: 0x1b7e, lo: 0xb6, hi: 0xb6},
-	{value: 0x1882, lo: 0xb8, hi: 0xb9},
-	{value: 0x1b86, lo: 0xba, hi: 0xba},
+	{value: 0x1882, lo: 0xb8, hi: 0xb8},
+	{value: 0x1b82, lo: 0xb9, hi: 0xba},
 	// Block 0x40, offset 0x41
-	{value: 0x0007, lo: 0x0e},
+	{value: 0x0005, lo: 0x0e},
 	{value: 0x1c39, lo: 0x94, hi: 0x94},
-	{value: 0x1c40, lo: 0x9b, hi: 0x9b},
-	{value: 0x1c45, lo: 0x9c, hi: 0x9c},
-	{value: 0x1c4a, lo: 0x9e, hi: 0x9f},
+	{value: 0x1c40, lo: 0x9b, hi: 0x9c},
+	{value: 0x1c4a, lo: 0x9e, hi: 0x9e},
+	{value: 0x1c51, lo: 0x9f, hi: 0x9f},
 	{value: 0x1c58, lo: 0xac, hi: 0xac},
 	{value: 0x1c5f, lo: 0xae, hi: 0xae},
 	{value: 0x1c66, lo: 0xb0, hi: 0xb0},
@@ -4543,7 +4541,7 @@ var nfkcDecompSparseValues = [605]valueRange{
 	{value: 0x3a53, lo: 0xa6, hi: 0xa6},
 	{value: 0x3a57, lo: 0xa8, hi: 0xae},
 	// Block 0x55, offset 0x56
-	{value: 0x0009, lo: 0x03},
+	{value: 0x0000, lo: 0x03},
 	{value: 0x3a73, lo: 0x9a, hi: 0x9a},
 	{value: 0x3a7c, lo: 0x9c, hi: 0x9c},
 	{value: 0x3a85, lo: 0xab, hi: 0xab},
@@ -5760,10 +5758,10 @@ var charInfoValues = [1024]uint16{
 }
 
 // charInfoSparseOffset: 156 entries, 312 bytes
-var charInfoSparseOffset = []uint16{0x0, 0x8, 0x13, 0x21, 0x25, 0x2f, 0x36, 0x39, 0x3c, 0x4a, 0x56, 0x58, 0x62, 0x67, 0x6e, 0x7d, 0x8a, 0x92, 0x96, 0x9b, 0x9d, 0xa5, 0xab, 0xae, 0xb5, 0xb9, 0xbd, 0xbf, 0xc1, 0xc8, 0xcc, 0xd1, 0xd7, 0xda, 0xe3, 0xe5, 0xed, 0xf1, 0xf3, 0xf6, 0xf9, 0xff, 0x10f, 0x11b, 0x11d, 0x123, 0x125, 0x127, 0x129, 0x12b, 0x12d, 0x12f, 0x131, 0x134, 0x137, 0x139, 0x13c, 0x13f, 0x143, 0x152, 0x15a, 0x15c, 0x15f, 0x161, 0x16a, 0x16e, 0x172, 0x174, 0x183, 0x187, 0x18d, 0x195, 0x199, 0x1a2, 0x1ab, 0x1b6, 0x1bc, 0x1c0, 0x1ce, 0x1dd, 0x1e1, 0x1e8, 0x1ed, 0x1fc, 0x208, 0x20b, 0x20d, 0x20f, 0x211, 0x213, 0x215, 0x217, 0x219, 0x21b, 0x21d, 0x220, 0x222, 0x224, 0x226, 0x228, 0x231, 0x233, 0x236, 0x239, 0x23c, 0x23e, 0x241, 0x243, 0x245, 0x247, 0x24a, 0x24c, 0x24e, 0x250, 0x252, 0x258, 0x25a, 0x25c, 0x25e, 0x260, 0x262, 0x26c, 0x26f, 0x271, 0x27b, 0x280, 0x282, 0x284, 0x286, 0x288, 0x28b, 0x28e, 0x292, 0x29a, 0x29c, 0x29e, 0x2a5, 0x2a7, 0x2ae, 0x2b6, 0x2bd, 0x2c3, 0x2c5, 0x2c7, 0x2ca, 0x2d3, 0x2d6, 0x2dd, 0x2e2, 0x2e5, 0x2e8, 0x2ec, 0x2ee, 0x2f0, 0x2f3, 0x2f6}
+var charInfoSparseOffset = []uint16{0x0, 0x8, 0x13, 0x21, 0x25, 0x2f, 0x36, 0x39, 0x3c, 0x4a, 0x56, 0x58, 0x62, 0x67, 0x6e, 0x7d, 0x8a, 0x92, 0x96, 0x9b, 0x9d, 0xa5, 0xab, 0xae, 0xb5, 0xb9, 0xbd, 0xbf, 0xc1, 0xc8, 0xcc, 0xd1, 0xd6, 0xd9, 0xe2, 0xe4, 0xec, 0xf0, 0xf2, 0xf5, 0xf8, 0xfe, 0x10e, 0x11a, 0x11c, 0x122, 0x124, 0x126, 0x128, 0x12a, 0x12c, 0x12e, 0x130, 0x133, 0x136, 0x138, 0x13b, 0x13e, 0x142, 0x151, 0x159, 0x15b, 0x15e, 0x160, 0x169, 0x16d, 0x171, 0x173, 0x182, 0x186, 0x18c, 0x194, 0x198, 0x1a1, 0x1aa, 0x1b5, 0x1bb, 0x1bf, 0x1cd, 0x1dc, 0x1e0, 0x1e7, 0x1ec, 0x1fa, 0x206, 0x209, 0x20b, 0x20d, 0x20f, 0x211, 0x213, 0x215, 0x217, 0x219, 0x21b, 0x21e, 0x220, 0x222, 0x224, 0x226, 0x22f, 0x231, 0x234, 0x237, 0x23a, 0x23c, 0x23f, 0x241, 0x243, 0x245, 0x248, 0x24a, 0x24c, 0x24e, 0x250, 0x256, 0x258, 0x25a, 0x25c, 0x25e, 0x260, 0x26a, 0x26d, 0x26f, 0x279, 0x27e, 0x280, 0x282, 0x284, 0x286, 0x289, 0x28c, 0x290, 0x298, 0x29a, 0x29c, 0x2a3, 0x2a5, 0x2ab, 0x2b3, 0x2ba, 0x2c0, 0x2c2, 0x2c4, 0x2c7, 0x2d0, 0x2d3, 0x2da, 0x2df, 0x2e2, 0x2e5, 0x2e9, 0x2eb, 0x2ed, 0x2f0, 0x2f3}
 
 // charInfoSparseValues: 760 entries, 3040 bytes
-var charInfoSparseValues = [760]valueRange{
+// charInfoSparseValues: 757 entries, 3028 bytes
 	// Block 0x0, offset 0x1
 	{value: 0x0000, lo: 0x07},
 	{value: 0x3000, lo: 0xa0, hi: 0xa0},
@@ -5942,7 +5940,7 @@ var charInfoSparseValues = [760]valueRange{
 	{value: 0x0000, lo: 0x01},
 	{value: 0x00dc, lo: 0x99, hi: 0x9b},
 	// Block 0x14, offset 0x15
-	{value: 0x7700, lo: 0x07},
+	{value: 0x0000, lo: 0x07},
 	{value: 0x8800, lo: 0xa8, hi: 0xa8},
 	{value: 0x1100, lo: 0xa9, hi: 0xa9},
 	{value: 0x8800, lo: 0xb0, hi: 0xb0},
@@ -5958,7 +5956,7 @@ var charInfoSparseValues = [760]valueRange{
 	{value: 0x00e6, lo: 0x93, hi: 0x94},
 	{value: 0x3300, lo: 0x98, hi: 0x9f},
 	// Block 0x16, offset 0x17
-	{value: 0x65f9, lo: 0x02},
+	{value: 0x0000, lo: 0x02},
 	{value: 0x0007, lo: 0xbc, hi: 0xbc},
 	{value: 0x6600, lo: 0xbe, hi: 0xbe},
 	// Block 0x17, offset 0x18
@@ -5994,7 +5992,7 @@ var charInfoSparseValues = [760]valueRange{
 	{value: 0x6600, lo: 0x96, hi: 0x97},
 	{value: 0x3300, lo: 0x9c, hi: 0x9d},
 	// Block 0x1d, offset 0x1e
-	{value: 0x5500, lo: 0x03},
+	{value: 0x0000, lo: 0x03},
 	{value: 0x8800, lo: 0x92, hi: 0x92},
 	{value: 0x1100, lo: 0x94, hi: 0x94},
 	{value: 0x6600, lo: 0xbe, hi: 0xbe},
@@ -6005,14 +6003,13 @@ var charInfoSparseValues = [760]valueRange{
 	{value: 0x0009, lo: 0x8d, hi: 0x8d},
 	{value: 0x6600, lo: 0x97, hi: 0x97},
 	// Block 0x1f, offset 0x20
-	{value: 0x004b, lo: 0x05},
+	{value: 0x6607, lo: 0x04},
 	{value: 0x8800, lo: 0x86, hi: 0x86},
 	{value: 0x1100, lo: 0x88, hi: 0x88},
 	{value: 0x0009, lo: 0x8d, hi: 0x8d},
-	{value: 0x0054, lo: 0x95, hi: 0x95},
-	{value: 0x665b, lo: 0x96, hi: 0x96},
+	{value: 0x0054, lo: 0x95, hi: 0x96},
 	// Block 0x20, offset 0x21
-	{value: 0x87f9, lo: 0x02},
+	{value: 0x0000, lo: 0x02},
 	{value: 0x0007, lo: 0xbc, hi: 0xbc},
 	{value: 0x8800, lo: 0xbf, hi: 0xbf},
 	// Block 0x21, offset 0x22
@@ -6126,7 +6123,7 @@ var charInfoSparseValues = [760]valueRange{
 	{value: 0x0009, lo: 0x94, hi: 0x94},
 	{value: 0x0009, lo: 0xb4, hi: 0xb4},
 	// Block 0x35, offset 0x36
-	{value: 0x00dd, lo: 0x02},
+	{value: 0x0000, lo: 0x02},
 	{value: 0x0009, lo: 0x92, hi: 0x92},
 	{value: 0x00e6, lo: 0x9d, hi: 0x9d},
 	// Block 0x36, offset 0x37
@@ -6340,7 +6337,7 @@ var charInfoSparseValues = [760]valueRange{
 	{value: 0x8800, lo: 0x92, hi: 0x92},
 	{value: 0x8800, lo: 0x94, hi: 0x94},
 	// Block 0x52, offset 0x53
-	{value: 0x7700, lo: 0x0e},
+	{value: 0x0000, lo: 0x0d},
 	{value: 0x8800, lo: 0x83, hi: 0x83},
 	{value: 0x1100, lo: 0x84, hi: 0x84},
 	{value: 0x8800, lo: 0x88, hi: 0x88},
@@ -6348,12 +6345,11 @@ var charInfoSparseValues = [760]valueRange{
 	{value: 0x8800, lo: 0x8b, hi: 0x8b},
 	{value: 0x1100, lo: 0x8c, hi: 0x8c},
 	{value: 0x8800, lo: 0xa3, hi: 0xa3},
-	{value: 0x1100, lo: 0xa4, hi: 0xa5},
+	{value: 0x1100, lo: 0xa4, hi: 0xa4},\n+\t{value: 0x8800, lo: 0xa5, hi: 0xa5},\n \t{value: 0x1100, lo: 0xa6, hi: 0xa6},
-	{value: 0x3000, lo: 0xac, hi: 0xac},
-	{value: 0x3000, lo: 0xad, hi: 0xad},
-	{value: 0x3000, lo: 0xaf, hi: 0xaf},
-	{value: 0x3000, lo: 0xb0, hi: 0xb0},
+	{value: 0x3000, lo: 0xac, hi: 0xad},\n+\t{value: 0x3000, lo: 0xaf, hi: 0xb0},\n \t{value: 0x8800, lo: 0xbc, hi: 0xbc},
 	// Block 0x53, offset 0x54
 	{value: 0x0000, lo: 0x0b},
@@ -6581,22 +6577,21 @@ var charInfoSparseValues = [760]valueRange{
 	{value: 0x0000, lo: 0x01},
 	{value: 0x00dc, lo: 0xbd, hi: 0xbd},
 	// Block 0x89, offset 0x8a
-	{value: 0x0000, lo: 0x06},
+	{value: 0x00db, lo: 0x05},
 	{value: 0x00dc, lo: 0x8d, hi: 0x8d},
 	{value: 0x00e6, lo: 0x8f, hi: 0x8f},
 	{value: 0x00e6, lo: 0xb8, hi: 0xb8},
-	{value: 0x0001, lo: 0xb9, hi: 0xb9},
-	{value: 0x00dc, lo: 0xba, hi: 0xba},
+	{value: 0x0001, lo: 0xb9, hi: 0xba},\n \t{value: 0x0009, lo: 0xbf, hi: 0xbf},
 	// Block 0x8a, offset 0x8b
-	{value: 0x7700, lo: 0x07},
+	{value: 0x65fe, lo: 0x07},
 	{value: 0x8800, lo: 0x99, hi: 0x99},
-	{value: 0x1100, lo: 0x9a, hi: 0x9b},
+	{value: 0x1100, lo: 0x9a, hi: 0x9a},\n+\t{value: 0x8800, lo: 0x9b, hi: 0x9b},\n \t{value: 0x1100, lo: 0x9c, hi: 0x9c},
 	{value: 0x8800, lo: 0xa5, hi: 0xa5},
 	{value: 0x1100, lo: 0xab, hi: 0xab},
-	{value: 0x0009, lo: 0xb9, hi: 0xb9},
-	{value: 0x6607, lo: 0xba, hi: 0xba},
+	{value: 0x0009, lo: 0xb9, hi: 0xba},\n \t// Block 0x8b, offset 0x8c
 	{value: 0x0000, lo: 0x06},
 	{value: 0x3300, lo: 0x9e, hi: 0xa4},
@@ -6768,4 +6763,4 @@ var charInfoLookup = [1152]uint8{
 
 var charInfoTrie = trie{charInfoLookup[:], charInfoValues[:], charInfoSparseValues[:], charInfoSparseOffset[:], 16}
 
-// Total size of tables: 48KB (48756 bytes)
+// Total size of tables: 48KB (48736 bytes)
diff --git a/src/pkg/exp/norm/triegen.go b/src/pkg/exp/norm/triegen.go
index 5edadac0a4..4ad9e0e057 100644
--- a/src/pkg/exp/norm/triegen.go
+++ b/src/pkg/exp/norm/triegen.go
@@ -65,11 +65,13 @@ func (n trieNode) mostFrequentStride() int {
 			\t\t\tcounts[stride]++
 			\t\t}\n \t\t\tv = t.value
+\t\t} else {
+\t\t\tv = 0
 \t\t}\n \t}\n \tvar maxs, maxc int
 \tfor stride, cnt := range counts {
-\t\tif cnt > maxc {\n+\t\tif cnt > maxc || (cnt == maxc && stride < maxs) {\n \t\t\tmaxs, maxc = stride, cnt
 \t\t}\n \t}\n```

## コアとなるコードの解説

### `src/pkg/exp/norm/tables.go` の変更

このファイルは、`triegen.go`によって生成されるUnicode正規化データテーブルを定義しています。変更の大部分は、`nfcDecompSparseValues`, `nfkcDecompSparseValues`, `charInfoSparseValues`といった`valueRange`型の配列内の特定の`value`フィールドが、非ゼロの値（例: `0x0005`, `0x0007`, `0x7700`など）から`0x0000`に変更されている点です。

これは、`triegen.go`のテーブル生成ロジックが、マップイテレーションのランダム性によって、これらの`valueRange`エントリの`value`フィールドに非決定的な値（おそらく、本来はゼロであるべきか、あるいは特定のデフォルト値であるべきものが、ランダムな順序によって異なる値が割り当てられていた）を割り当てていたことを示唆しています。`0x0000`に統一することで、これらのエントリが常に予測可能な初期値を持つようになり、テーブル全体の決定性が保証されます。

また、`nfkcDecompSparseOffset`と`charInfoSparseOffset`配列の要素がわずかに変更され、それに伴い`nfkcDecompSparseValues`と`charInfoSparseValues`の配列サイズも減少しています。これは、`triegen.go`の最適化ロジックがより決定的に動作するようになった結果、より効率的なデータ構造が生成され、冗長なエントリが削減されたことを示しています。最終的に、テーブルの合計サイズもわずかに減少しています。

### `src/pkg/exp/norm/triegen.go` の変更

このファイルは、Unicode正規化テーブルを生成するGoプログラムです。主要な変更点は`trieNode.mostFrequentStride()`関数内にあります。

1.  **`v = 0` の追加**:
    ```go
    		} else {
    			v = 0
    		}
    ```
    この変更は、`t.value`が特定の条件を満たさない場合に、`v`（おそらくトライ木のノードの値）が明示的に`0`に設定されることを保証します。これにより、マップイテレーションのランダム性によって`v`が未定義または非決定的な値になることを防ぎ、テーブル生成の決定性を高めます。

2.  **ストライド選択ロジックの変更**:
    ```diff
    -		if cnt > maxc {
    +		if cnt > maxc || (cnt == maxc && stride < maxs) {
    ```
    これがこのコミットの最も重要な変更点です。
    *   以前のコード`if cnt > maxc`は、最も頻繁に出現するストライドを選択する際に、複数のストライドが同じ最大出現回数（`maxc`）を持つ場合に、マップイテレーションの順序に依存して、最初に現れたものを選択していました。
    *   新しいコード`if cnt > maxc || (cnt == maxc && stride < maxs)`は、この非決定性を排除します。
        *   `cnt > maxc`: 以前と同様に、より高い出現回数を持つストライドを優先します。
        *   `cnt == maxc && stride < maxs`: **出現回数が同じである場合（`cnt == maxc`）には、より小さい`stride`値を持つものを優先的に選択します。**

    この変更により、`mostFrequentStride()`関数は常に同じ決定的なストライドを選択するようになります。これにより、`tables.go`で生成されるデータ配列の構造と内容が、実行ごとに常に同じになることが保証され、マップイテレーションのランダム性によるバグが修正されます。

## 関連リンク

*   Go CL 5573044: [https://golang.org/cl/5573044](https://golang.org/cl/5573044)

## 参考にした情報源リンク

*   Go言語のマップイテレーションのランダム化に関する情報:
    *   [Go Slices, Arrays, and Maps: The Ultimate Guide](https://www.digitalocean.com/community/tutorials/go-slices-arrays-and-maps) (マップの順序が保証されないことについて言及)
    *   [The Go Programming Language Specification - Map types](https://go.dev/ref/spec#Map_types) (マップのイテレーション順序が定義されていないことを明記)
*   Unicode正規化に関する情報:
    *   [Unicode® Standard Annex #15: Unicode Normalization Forms](https://www.unicode.org/reports/tr15/)
    *   [Wikipedia: Unicode正規化](https://ja.wikipedia.org/wiki/Unicode%E6%AD%A3%E8%A6%8F%E5%8C%96)
*   トライ木に関する情報:
    *   [Wikipedia: トライ木](https://ja.wikipedia.org/wiki/%E3%83%88%E3%83%A9%E3%82%A4%E6%9C%A8)
*   Go言語のソースコードとコミット履歴 (GitHub):
    *   [golang/go repository](https://github.com/golang/go)
    *   [Go source code](https://go.dev/src/)
*   Go言語のコードレビューシステム (Gerrit):
    *   [Go Code Review](https://go-review.googlesource.com/)
    *   [CL 5573044 on Go Code Review](https://go-review.googlesource.com/c/go/+/5573044) (このコミットの元の変更リスト)