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

このコミットは、Go言語の実験的なロケールパッケージ exp/locale/collate 内の build サブパッケージにある contract.go ファイルに対するバグ修正です。具体的には、コレーション（照合順序）テーブルの構築に関連するコードのロジックが修正されています。

コミット

commit a8357f0160681d02e7b9abaf3a6ad3b87bb5a933
Author: Marcel van Lohuizen <mpvl@golang.org>
Date:   Mon Aug 20 10:56:41 2012 +0200

    exp/locale/collate/build: fixed bug that was exposed by experimenting
    with table changes.
    NOTE: there is no test for this, but 1) the code has now the same
    control flow as scan in exp/locale/collate/contract.go, which is
    tested and 2) Builder verifies the generated table so bugs in this
    code are quickly and easily found (which is how this bug was discovered).
    
    R=r
    CC=golang-dev
    https://golang.org/cl/6461082

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

https://github.com/golang/go/commit/a8357f0160681d02e7b9abaf3a6ad3b87bb5a933

元コミット内容

exp/locale/collate/build: テーブル変更の実験によって露呈したバグを修正。 注：これに対するテストはないが、1) このコードは現在、exp/locale/collate/contract.go の scan と同じ制御フローを持つようになり、そちらはテストされている。2) Builder が生成されたテーブルを検証するため、このコードのバグは迅速かつ容易に発見される（このバグがどのように発見されたか）。

変更の背景

このコミットは、Go言語の実験的なロケールパッケージ exp/locale/collate の開発中に発見されたバグを修正するものです。コミットメッセージによると、このバグはコレーションテーブルの変更を試みている最中に露呈しました。exp/locale/collate パッケージは、異なる言語や地域（ロケール）における文字列の照合（ソート順序の決定）を扱うためのものであり、そのための内部的なデータ構造（テーブル）を構築する際に問題が発生していたと考えられます。

開発者は、新しいテーブルの変更を試す過程で、既存のコードに潜在していたロジックの誤りを発見しました。この修正は、その誤りを訂正し、コレーションテーブルの構築プロセスが正しく機能するようにすることを目的としています。特に、Builder が生成されたテーブルを検証する仕組みがあるため、このようなバグが早期に発見されたと述べられています。

前提知識の解説

1. ロケール (Locale)

ロケールとは、ユーザーの言語、国、および文化的な設定を定義する一連のパラメータのことです。これには、日付と時刻の形式、通貨記号、数値の区切り文字、そして文字列の照合（ソート）順序などが含まれます。プログラムが異なる地域で正しく動作するためには、これらのロケール固有のルールを考慮する必要があります。

2. コレーション (Collation)

コレーションとは、文字列を特定のロケールルールに基づいて比較し、ソート順序を決定するプロセスのことです。単純な辞書順ソートとは異なり、コレーションはアクセント記号、大文字・小文字、特殊文字、複合文字（例: ドイツ語の ß と ss）などを考慮に入れます。例えば、スウェーデン語では å, ä, ö がアルファベットの最後に位置するなど、言語によってソート順序は大きく異なります。

3. Unicode Collation Algorithm (UCA)

Unicode Collation Algorithm (UCA) は、Unicode Consortium によって定義された、多言語環境での文字列照合のための標準アルゴリズムです。UCAは、言語固有のルールを考慮しつつ、一貫性のあるソート順序を提供することを目的としています。多くのプログラミング言語やデータベースシステムが、このUCAに基づいてコレーション機能を提供しています。Go言語の exp/locale/collate パッケージも、このUCAの実装を目指していると考えられます。

4. トライ (Trie) または プレフィックスツリー (Prefix Tree)

トライは、文字列の集合を効率的に格納し、検索するために使用されるツリーデータ構造です。各ノードは文字列のプレフィックスを表し、ルートからノードへのパスが文字列を形成します。コレーションのような文字列処理において、共通のプレフィックスを持つ文字列を効率的に処理するために利用されることがあります。contractTrieSet という名前から、このコミットで修正されているコードがトライのようなデータ構造を扱っていることが示唆されます。

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

Go言語の標準ライブラリには、exp というプレフィックスを持つパッケージが存在することがあります。これらは「実験的 (experimental)」なパッケージであり、まだ安定版としてリリースされていない、あるいは将来的に変更される可能性のある機能を含んでいます。開発中の新機能や、特定の目的のために試行的に導入された機能がここに置かれることが多いです。exp/locale/collate もその一つであり、Go言語が国際化対応を強化する過程で開発されていたものと推測されます。

6. contract.go と scan

contract.go は、コレーションの「縮約 (contraction)」を扱うファイルであると推測されます。縮約とは、複数の文字が単一のコレーション要素として扱われる場合（例: スペイン語の ch が c と d の間にソートされる場合）を指します。scan は、おそらく入力文字列を走査し、これらの縮約や拡張（単一の文字が複数のコレーション要素として扱われる場合）を識別する関数であると考えられます。

技術的詳細

このコミットは、src/pkg/exp/locale/collate/build/contract.go ファイル内の contractTrieSet 構造体の lookup メソッドのロジックを修正しています。contractTrieSet は、コレーションの縮約（複数の文字が単一のコレーション要素として扱われるケース）を効率的に検索するためのトライ（または類似のプレフィックスツリー）のようなデータ構造を管理していると考えられます。

lookup メソッドは、与えられたバイト列 str に対して、コレーションの縮約パターンを検索し、対応するインデックスと、マッチしたバイト列の長さを返します。このメソッドは、内部的に states という配列（おそらくトライのノードを表す）を走査し、現在の文字 c とノードの状態 e を比較しながら、適切なパスをたどります。

修正の核心は、ループ内の p++ (ポインタ/インデックスのインクリメント) と i++ (状態インデックスのインクリメント) の位置の変更にあります。

変更前:

		if c >= e.l {
			p++ // ここでpがインクリメントされる
			if e.l == c {
				// ...
			} else if e.n == final && c <= e.h {
				return int(c-e.l) + int(e.i), p
			}
		} else {
			i++ // ここでiがインクリメントされる
		}

変更後:

		if c >= e.l {
			if e.l == c {
				p++ // 条件が満たされた場合のみpがインクリメントされる
				// ...
			} else if e.n == final && c <= e.h {
				p++ // 条件が満たされた場合のみpがインクリメントされる
				return int(c-e.l) + int(e.i), p
			}
			continue // ループの次のイテレーションへ
		}
		i++ // 常にiがインクリメントされる

この変更により、p (入力文字列の現在の位置) のインクリメントが、特定の条件 (e.l == c または e.n == final && c <= e.h) が満たされた場合にのみ行われるようになりました。また、i (状態配列のインデックス) のインクリメントは、c >= e.l の条件が満たされない場合、または c >= e.l が満たされたが、e.l == c や e.n == final && c <= e.h のいずれの条件も満たされなかった場合に、ループの最後に常に実行されるようになりました。

コミットメッセージにある「scan と同じ制御フロー」という記述は、この lookup メソッドのロジックが、exp/locale/collate/contract.go 内の別の関数 scan のロジックと整合性が取れていなかったことを示唆しています。scan 関数は、おそらく文字列を走査してコレーション要素を識別する主要な関数であり、lookup はその内部で縮約を解決するために呼び出される補助関数であると考えられます。両者の制御フローを一致させることで、コレーション処理全体の正確性と堅牢性が向上します。

この修正は、トライデータ構造の走査ロジックにおける微妙なバグを修正するものであり、特定の入力パターンで誤った結果を返したり、無限ループに陥ったりする可能性があった問題を解決していると考えられます。

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

diff --git a/src/pkg/exp/locale/collate/build/contract.go b/src/pkg/exp/locale/collate/build/contract.go
index 45d8f74b9b..f7cf64a730 100644
--- a/src/pkg/exp/locale/collate/build/contract.go
+++ b/src/pkg/exp/locale/collate/build/contract.go
@@ -241,8 +241,8 @@ func (ct *contractTrieSet) lookup(h ctHandle, str []byte) (index, ns int) {
 	t.e := states[i]
 	t.c := str[p]
 	t.if c >= e.l {
-	t.		p++
 	t.		if e.l == c {
+	t.			p++
 	t.			if e.i != noIndex {
 	t.				index, ns = int(e.i), p
 	t.			}
@@ -252,12 +252,13 @@ func (ct *contractTrieSet) lookup(h ctHandle, str []byte) (index, ns int) {
 	t.			} else {
 	t.				return
 	t.			}
+	t.			continue
 	t.		} else if e.n == final && c <= e.h {
+	t.			p++
 	t.			return int(c-e.l) + int(e.i), p
 	t.		}
-	t.	} else {
-	t.		i++
 	t.	}
+	t.	i++
 	t.}
 	t.return
 }

コアとなるコードの解説

変更は func (ct *contractTrieSet) lookup(h ctHandle, str []byte) (index, ns int) 関数内で行われています。この関数は、str バイト列の中からコレーションの縮約パターンを検索するためのものです。

主要な変更点は以下の通りです。

1. p++ の移動:

   • 変更前は、if c >= e.l の条件が真であれば、無条件に p (入力文字列の現在のインデックス) がインクリメントされていました。
   • 変更後は、p のインクリメントが if e.l == c または else if e.n == final && c <= e.h の内部に移動しました。これは、p がインクリメントされるのは、実際に現在の文字 c が現在の状態 e とマッチした場合のみであることを意味します。これにより、マッチしない文字で不必要に p が進んでしまうバグが修正されます。

2. continue の追加:

   • if c >= e.l のブロック内で、e.l == c または e.n == final && c <= e.h のいずれかの条件が満たされた後、continue が追加されました。これにより、マッチが見つかった場合、現在のループの残りの部分をスキップして、次の文字の処理に移ることができます。これは、トライの走査ロジックにおいて、現在のノードでの処理が完了したら次の入力文字に進むという一般的なパターンに合致します。

3. i++ の移動:

   • 変更前は、if c >= e.l の条件が偽の場合にのみ i (状態配列のインデックス) がインクリメントされていました。
   • 変更後は、i++ が if c >= e.l ブロックの外、つまりループの最後に移動しました。これにより、i はループの各イテレーションで常にインクリメントされるようになりました。これは、トライの走査において、現在の状態を処理した後、次の可能な状態（兄弟ノードなど）に進むというロジックを反映していると考えられます。

これらの変更は、lookup 関数がトライデータ構造を正しく走査し、コレーションの縮約を正確に識別するためのものです。特に、p と i のインクリメントのタイミングと条件を厳密に制御することで、バグが修正され、scan 関数との制御フローの整合性が確保されました。

関連リンク

• Go言語の公式ドキュメント: https://golang.org/
• Unicode Collation Algorithm (UCA): https://unicode.org/reports/tr10/
• Go言語のコードレビューシステム (Gerrit): https://go-review.googlesource.com/ (コミットメッセージにある https://golang.org/cl/6461082 は、このGerritシステムへのリンクです)

参考にした情報源リンク

• https://github.com/golang/go/commit/a8357f0160681d02e7b9abaf3a6ad3b87bb5a933
• https://golang.org/cl/6461082
• Go言語の exp/locale パッケージに関する情報 (当時のGo言語のソースコードリポジトリや関連する設計ドキュメント)
• Unicode Collation Algorithm (UCA) に関する一般的な情報源
• トライ (Trie) データ構造に関する一般的な情報源