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

このコミットは、Go言語の実験的なロケールパッケージ exp/locale/collate における、照合要素（collation element, colElem）の内部表現の変更、暗黙的なプライマリ値のオフセット調整、および重み変換コードのバグ修正を目的としています。特に、tables.go ファイルは、照合テーブルのデータ構造が大幅に変更されており、これは照合要素の新しい表現形式に対応するためのものです。

コミット

commit 882b6ef4542e7055c7dcd262b22c434b957195df
Author: Marcel van Lohuizen <mpvl@golang.org>
Date:   Fri Jul 13 11:38:22 2012 +0200

    exp/locale/collate: This CL includes the following changes:
    - Changed the representation of colElem to support a few cases
      for some languages not supported by the current format.
    - Changed offsets for implicit primary values. This makes the
      values both easier to read and debug (last 4 nibbles are identical to
      implicit primary value) and also results in better packing.
    - Fixed bug in weight conversion code that did not pop up yet by
      sheer luck.
    Note that tables.go also includes changes to the contraction trie
    from CL 6346092.
    
    R=r, mpvl
    CC=golang-dev
    https://golang.org/cl/6392060

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

https://github.com/golang/go/commit/882b6ef4542e7055c7dcd262b22c434b957192df

元コミット内容

このコミットは、exp/locale/collate パッケージに対して以下の変更を導入しています。

colElem の表現形式を変更し、既存の形式ではサポートされていなかった一部の言語の特定のケースに対応できるようにしました。
暗黙的なプライマリ値のオフセットを変更しました。これにより、値の可読性とデバッグのしやすさが向上し（下位4ビットが暗黙的なプライマリ値と同一になる）、より効率的なパッキングが可能になりました。
重み変換コードのバグを修正しました。このバグはこれまで偶然にも顕在化していませんでした。
tables.go には、CL 6346092 で導入された収縮トライ（contraction trie）に関する変更も含まれています。

変更の背景

この変更の背景には、Unicode Collation Algorithm (UCA) に基づく照合処理の正確性と効率性の向上が挙げられます。特に、以下の点が課題となっていました。

既存の colElem 表現の限界: 従来の colElem のデータ構造では、特定の言語（特にCJK言語など）における複雑な照合ルールや、特殊な文字の照合要素を効率的かつ正確に表現するのに限界がありました。これにより、一部の言語で期待通りの照合順序が得られない可能性がありました。
暗黙的なプライマリ値の最適化: UCAでは、多くの文字に対して明示的な照合要素を定義する代わりに、コードポイントに基づいて「暗黙的なプライマリ値」を生成する仕組みがあります。この暗黙的な値のオフセットが最適化されていなかったため、デバッグが困難であったり、データパッキングの効率が悪かったりする問題がありました。新しいオフセットは、値のパターンをより直感的にし、デバッグを容易にするとともに、データ構造のコンパクト化に貢献します。
潜在的なバグの修正: 重み変換コードに未発見のバグが存在していました。これは、特定の入力パターンで誤った照合要素が生成される可能性を秘めていましたが、これまでのテストケースや使用状況では表面化していませんでした。このコミットは、将来的な問題を防ぐためにこのバグを修正しています。
収縮トライの更新: 照合における「収縮（Contraction）」とは、複数の文字が結合して一つの照合要素を形成するルールです（例: スペイン語の "ch" が一つの文字として扱われる）。この処理を効率的に行うためのデータ構造である収縮トライが、以前のコミット（CL 6346092）で変更されており、今回のコミットではその変更が tables.go に反映されています。

これらの変更は、Go言語のロケールパッケージが、より広範な言語と複雑な照合ルールに対応し、かつ内部的な効率性を高めるために不可欠でした。

前提知識の解説

このコミットを理解するためには、以下の概念を把握しておく必要があります。

1. Unicode Collation Algorithm (UCA)

UCAは、Unicode Consortiumによって定義された、多言語テキストのソート（照合）順序を決定するための標準アルゴリズムです。UCAは、言語や文化によって異なるソート規則に対応できるよう、柔軟なフレームワークを提供します。

2. 照合要素 (Collation Element, CE)

UCAでは、各文字または文字シーケンスは、ソート順序を決定するための数値の並びである「照合要素」に変換されます。照合要素は通常、以下の3つのレベルの重み（weight）で構成されます。

プライマリ重み (Primary Weight): 大文字と小文字、アクセント記号などを無視した、基本的な文字の順序を決定します。例えば、'a' と 'A' は同じプライマリ重みを持ちます。
セカンダリ重み (Secondary Weight): アクセント記号やダイアクリティカルマーク（分音記号）の違いを区別します。例えば、'a' と 'á' は異なるセカンダリ重みを持ちます。
ターシャリ重み (Tertiary Weight): 大文字と小文字、幅の違い（全角/半角など）を区別します。例えば、'a' と 'A' は異なるターシャリ重みを持ちます。

これらの重みは、通常、プライマリ、セカンダリ、ターシャリの順に比較され、ソート順序が決定されます。

3. DUCET (Default Unicode Collation Element Table)

DUCETは、UCAのデフォルトの照合要素テーブルです。これは、各Unicodeコードポイントに対応するデフォルトの照合要素を定義しています。特定の言語や文化に特化した照合ルールは、DUCETを基にカスタマイズされます。

4. CLDR (Common Locale Data Repository)

CLDRは、Unicode Consortiumが提供する、ロケール（地域設定）に関するデータのリポジトリです。これには、日付、時刻、通貨、数値の書式設定、そして照合ルールなど、多岐にわたるロケール情報が含まれています。Go言語の exp/locale/collate パッケージは、CLDRの照合データを利用して照合テーブルを構築しています。

5. 収縮 (Contraction) と拡張 (Expansion)

収縮 (Contraction): 複数の文字が結合して一つの照合要素を形成するルールです。例えば、スペイン語の "ch" や "ll" は、それぞれ単一の文字として扱われることがあります。
拡張 (Expansion): 一つの文字が複数の照合要素に展開されるルールです。例えば、ドイツ語の "ß" は "ss" として扱われることがあります。

6. 暗黙的なプライマリ値 (Implicit Primary Values)

UCAでは、DUCETに明示的に定義されていない多くのUnicode文字（特にCJK統合漢字など）に対して、そのコードポイントに基づいてプライマリ重みを「暗黙的に」生成するメカニズムがあります。これにより、テーブルのサイズを大幅に削減できます。これらの暗黙的な値は、特定のアルゴリズムに従って計算されます。

7. 収縮トライ (Contraction Trie)

収縮ルールを効率的に検索するためのデータ構造です。トライ（接頭辞木）を使用することで、入力文字列の接頭辞に基づいて、どの収縮ルールが適用されるかを高速に判断できます。

技術的詳細

このコミットの技術的な変更は、主に colElem の内部表現と、それに伴う照合要素の生成・解析ロジックの変更に集約されます。

1. `colElem` の新しい表現形式

従来の colElem は、プライマリ、セカンダリ、ターシャリの各重みをビットフィールドとしてパックする形式でしたが、このコミットではそのビット割り当てが変更されています。

従来の形式 (例):
- プライマリ重みを持つ要素: 000ppppp pppppppp pppppppp tttttttt (p: プライマリ, t: ターシャリ)
- セカンダリ重みを持つ要素: 01000000 ssssssss ssssssss tttttttt (s: セカンダリ, t: ターシャリ)
- 収縮: 10bbbbbb bbbbbbbb iiiiiiii iiinnnnn
- 拡張: 110bbbbb bbbbbbbb bbbbbbbb bbbbbbbb
- 分解: 11100000 00000000 wwwwwwww vvvvvvvv
新しい形式 (例):
- プライマリ重みを持つ要素 (デフォルトターシャリ): 010ppppp pppppppp pppppppp ssssssss (p: プライマリ, s: セカンダリ)
- プライマリ重みを持つ要素 (非デフォルトターシャリ): 00pppppp pppppppp ppppppps sssttttt (p: プライマリ, s: セカンダリ差分, t: ターシャリ)
- セカンダリ重みを持つ要素: 10000000 0000ssss ssssssss tttttttt (s: セカンダリ, t: ターシャリ)
- 収縮: 110bbbbb bbbbbbbb iiiiiiii iiiinnnn
- 拡張: 11100000 00000000 bbbbbbbb bbbbbbbb
- 分解: 11110000 00000000 wwwwwwww vvvvvvvv

この変更により、特にプライマリ重みを持つ要素の表現がより柔軟になり、セカンダリ重みとターシャリ重みの両方を効率的に格納できるようになりました。これは、一部の言語で必要とされる複雑な照合ルールに対応するために重要です。

2. 暗黙的なプライマリ値のオフセット変更

convertLargeWeights 関数内で、暗黙的なプライマリ値の計算に使用されるオフセット定数 (commonUnifiedOffset, rareUnifiedOffset, otherOffset) が変更されました。

従来のオフセット:
- commonUnifiedOffset = 0xFB40
- rareUnifiedOffset = 0x1FB40
- otherOffset = 0x4FB40
新しいオフセット:
- commonUnifiedOffset = 0x10000
- rareUnifiedOffset = 0x20000
- otherOffset = 0x50000

この変更は、暗黙的なプライマリ値の生成ロジックを改善し、値の範囲をより適切に管理することを目的としています。コミットメッセージにあるように、「下位4ビットが暗黙的なプライマリ値と同一になる」という特性は、デバッグの容易さに貢献します。また、より良いパッキング（データ圧縮）にも繋がります。

3. 重み変換コードのバグ修正

convertLargeWeights 関数内のロジックにバグが存在していました。特に、2つの照合要素が結合して一つの大きなプライマリ重みを形成するケース（DUCETで [.FBxx.0020.0002.C][.BBBB.0000.0000.C] のように表現されるCJK文字など）において、誤った計算が行われる可能性がありました。

従来のコードでは、結合されたプライマリ重みを implicitPrimary(r) で計算していましたが、新しいコードでは np という変数に計算結果を格納し、その np に基づいてオフセットを加算するロジックに変更されています。

// 変更前
// r := rune(((p & highBitsMask) << shiftBits) + elems[i+1][0]&lowBitsMask)
// ce[0] = implicitPrimary(r)

// 変更後
np := ((p & highBitsMask) << shiftBits) + elems[i+1][0]&lowBitsMask
switch {
case p < rarePrimaryStart:
    np += commonUnifiedOffset
case p < otherPrimaryStart:
    np += rareUnifiedOffset
default:
    p += otherOffset // ここは `np += otherOffset` の間違いか、意図的なものか要確認
}
ce[0] = np

注記: 上記のコードスニペットの p += otherOffset は、コミットの差分を見る限り np += otherOffset の間違いである可能性が高いです。もし p が変更されると、その後の ce[0] = np の計算に影響を与え、意図しない結果になる可能性があります。しかし、Goのコンパイラやリンターがこの種の論理エラーを検出しない限り、このままコミットされた可能性があります。この解説では、コミットされたコードのままを記述しています。

この修正により、特にCJK文字のような大きなプライマリ重みを持つ文字の照合要素が正しく生成されるようになります。

4. `contractCJK` 関数の削除

src/pkg/exp/locale/collate/build/builder.go から contractCJK 関数が削除されました。この関数は、CJK文字の大きな重みを変換するために convertLargeWeights を呼び出していましたが、Add メソッド内で convertLargeWeights が直接呼び出されるようになったため、冗長と判断され削除されました。これにより、コードの簡素化と処理フローの合理化が図られています。

5. `tables.go` の大幅な変更

tables.go は、Go言語の照合パッケージが使用する実際の照合データテーブルを定義しているファイルです。colElem の表現形式が変更されたため、このファイル内のすべての照合要素データが新しい形式に合わせて更新されました。これにより、ファイルサイズが大幅に増加（約13KBの変更）していますが、これは新しいデータ表現の正確性を反映したものです。

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

このコミットにおけるコアとなるコードの変更箇所は以下のファイルに集中しています。

src/pkg/exp/locale/collate/build/builder.go:
- Add メソッド内で convertLargeWeights が直接呼び出されるようになりました。
- contractCJK 関数が削除されました。
- simplify 関数が contractCJK に依存しなくなりました。
- convertLargeWeights 関数内の定数 (firstLargePrimary が cjkPrimaryStart などに) とロジックが変更されました。特に、暗黙的なプライマリ値の計算ロジックが修正されました。
src/pkg/exp/locale/collate/build/builder_test.go:
- convLargeTests の期待値が新しい暗黙的なプライマリ値のオフセットに合わせて更新されました。
- genColTests の期待値も同様に更新されました。
src/pkg/exp/locale/collate/build/colelem.go:
- makeCE 関数内の colElem のビット割り当てロジックが大幅に変更されました。
- maxPrimaryBits, maxSecondaryBits, maxTertiaryBits などの定数値が変更されました。
- isSecondary と isPrimary のビットマスクが変更されました。
- makeContractIndex, makeExpandIndex, makeDecompose 関数内のビット割り当て定数とロジックが変更されました。
- 暗黙的なプライマリ値のオフセット定数 (commonUnifiedOffset, rareUnifiedOffset, otherOffset, illegalOffset) が変更されました。
src/pkg/exp/locale/collate/build/colelem_test.go:
- ceTests の期待値が新しい colElem の表現形式に合わせて更新されました。
- implicitTests の期待値が新しい暗黙的なプライマリ値のオフセットに合わせて更新されました。
src/pkg/exp/locale/collate/colelem.go:
- colElem の型定義に関連する定数 (maxCE, minContract, maxContract など) が新しいビット割り当てに合わせて更新されました。
- splitCE 関数内の colElem の解析ロジックが新しいビット割り当てに合わせて大幅に変更されました。
- splitContractIndex, splitExpandIndex, splitDecompose 関数内のビット割り当て定数とロジックが変更されました。
- 暗黙的なプライマリ値のオフセット定数も build/colelem.go と同様に変更されました。
src/pkg/exp/locale/collate/colelem_test.go:
- makeCE, makeContractIndex, makeExpandIndex, makeDecompose のテストヘルパー関数が、新しい colElem 表現に合わせて更新されました。
- TestColElem と TestImplicit のテストケースの期待値が更新されました。
src/pkg/exp/locale/collate/tables.go:
- rootExpandElem 配列のデータが、新しい colElem の表現形式に合わせて全面的に更新されました。これがコミットの大部分を占める変更です。

コアとなるコードの解説

`colElem` 表現の変更と `makeCE`/`splitCE`

最も重要な変更は、照合要素 colElem の内部表現の再設計です。これは、32ビットの uint32 型でプライマリ、セカンダリ、ターシャリの重み、および収縮や拡張などの特殊な情報を効率的にパックするためのものです。

makeCE (build/colelem.go, colelem_test.go): この関数は、プライマリ、セカンダリ、ターシャリの重みから colElem を生成します。新しい表現では、プライマリ重みがゼロでない場合、セカンダリ重みがデフォルト値であるか、またはターシャリ重みがデフォルト値であるかによって、異なるビット割り当てが使用されます。これにより、より多くの情報をコンパクトに格納できるようになりました。特に、セカンダリ重みの「差分」を格納する新しい形式が導入され、より効率的なパッキングが可能になっています。
splitCE (colelem.go): この関数は、colElem からプライマリ、セカンダリ、ターシャリの重みを抽出します。makeCE の逆の操作を行い、新しいビット割り当てロジックに基づいて重みを正しくデコードします。

これらの変更は、Goの照合エンジンがUnicodeの複雑な照合ルール、特に一部の言語で必要とされる微妙な重みの違いを正確に表現できるようにするために不可欠です。

暗黙的なプライマリ値の計算 (`convertLargeWeights`)

convertLargeWeights 関数は、DUCETに明示的に定義されていない文字（主にCJK統合漢字）の暗黙的なプライマリ重みを計算する役割を担っています。

新しいオフセット定数: commonUnifiedOffset, rareUnifiedOffset, otherOffset の値が変更されました。これらのオフセットは、Unicodeのコードポイント範囲に基づいて、暗黙的なプライマリ重みを生成する際に使用されます。新しい値は、生成される重みがより予測可能で、デバッグしやすくなるように調整されています。コミットメッセージにある「下位4ビットが暗黙的なプライマリ値と同一になる」という特性は、このオフセット調整によって実現されています。
バグ修正: 従来のコードでは、2つの照合要素が結合して一つの大きなプライマリ重みを形成する特定のケースで、計算が誤っていました。修正されたロジックでは、結合された重み np を計算した後、適切なオフセットを加算することで、正しい暗黙的なプライマリ重みが生成されるようになっています。これにより、特にCJK文字の照合順序の正確性が保証されます。

https://github.com/golang/go/commit/882b6ef4542e7055c7dcd262b22c434b95719df (本コミットのGitHubページ)
https://golang.org/cl/6392060 (本コミットのGerrit Code Reviewページ)
https://golang.org/cl/6346092 (関連する収縮トライの変更コミット)
Unicode Technical Report #10: Unicode Collation Algorithm
CLDR - Unicode Common Locale Data Repository
Go言語のソースコード (exp/locale/collate) (コミット当時のGoリポジトリの構造に基づく)
Collation Element (Wikipedia)
Implicit Weights in UCA (UCAのTR10ドキュメント内の暗黙的な重みに関するセクション)
Go言語の exp パッケージについて (Go 1.1のリリースノートより、exp パッケージの性質について)

comemo