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

コミット

commit 52f0afe0dbf123f0b81bf358b6427c09bb96a597
Author: Marcel van Lohuizen <mpvl@golang.org>
Date:   Wed Apr 25 13:19:00 2012 +0200

    exp/locale/collate: Added skeleton for the higher-level types to provide
    context for change lists of lower-level types. The public APIs are defined
    in builder.go and collate.go. Type table is the glue between the lower and
    higher level code and might be a good starting point for understanding the
    collation code.
    
    R=r, r
    CC=golang-dev
    https://golang.org/cl/5999053

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

https://github.com/golang/go/commit/52f0afe0dbf123f0b81bf358b6427c09bb96a597

元コミット内容

exp/locale/collate パッケージにおいて、より高レベルな型（Collatorなど）のスケルトンが追加されました。これは、低レベルな型の変更リストにコンテキストを提供することを目的としています。公開APIは builder.go と collate.go で定義されています。table 型は、低レベルと高レベルのコード間の接着剤として機能し、collation コードを理解するための良い出発点となるでしょう。

変更の背景

このコミットは、Go言語の実験的な exp/locale/collate パッケージの初期開発段階の一部です。このパッケージは、Unicode Collation Algorithm (UCA) に基づいて文字列の比較とソートを行う機能を提供することを目的としています。

変更の背景には、以下の点が挙げられます。

• 国際化対応 (i18n) の強化: 異なる言語や地域における文字列の正しいソート順序は、単なるコードポイントの比較では実現できません。アクセント、大文字・小文字、結合文字、数字の扱いなど、言語固有のルールを考慮する必要があります。collate パッケージは、このような複雑な要件に対応するための基盤を提供します。
• 段階的な開発: コミットメッセージにあるように、この変更は「高レベルな型のスケルトン」を追加するものです。これは、まずAPIの構造と主要なデータ型を定義し、その後に詳細な実装を進めるという、トップダウンのアプローチを示唆しています。これにより、開発者は低レベルな変更を行う際に、それが最終的にどのような高レベルな機能に貢献するのかを理解しやすくなります。
• コードの理解促進: table 型が「低レベルと高レベルのコード間の接着剤」であり、「collation コードを理解するための良い出発点」であると明記されていることから、開発者がこの複雑なサブシステムを理解しやすくするための配慮がなされていることがわかります。

前提知識の解説

このコミットを理解するためには、以下の前提知識が役立ちます。

1. Unicode Collation Algorithm (UCA)

UCAは、Unicode文字列を言語的に正しい順序で比較・ソートするための国際標準アルゴリズムです。単なるコードポイントの数値比較ではなく、以下のような要素を考慮します。

• Primary Level (第一レベル): 文字の基本的な形状に基づいた比較。例えば、'a' と 'b' の違い。
• Secondary Level (第二レベル): アクセントやダイアクリティカルマーク（分音記号）に基づいた比較。例えば、'a' と 'á' の違い。
• Tertiary Level (第三レベル): 大文字・小文字、幅の違い（全角・半角）に基づいた比較。例えば、'a' と 'A' の違い。
• Quaternary Level (第四レベル): 可変要素（句読点や記号など）の扱いを制御するためのレベル。

UCAは、各文字に「照合要素 (Collation Element: CE)」と呼ばれる重みのシーケンスを割り当て、この重みを比較することでソート順を決定します。

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

Go言語の標準ライブラリには、exp (experimental) というプレフィックスを持つパッケージが存在します。これらは、まだ安定版としてリリースされていない、実験的な機能やAPIを提供します。exp パッケージのコードは、将来的に標準ライブラリに取り込まれる可能性がありますが、APIが変更されたり、削除されたりする可能性もあります。このコミットの exp/locale/collate もその一つです。

3. トライ木 (Trie)

トライ木（プレフィックス木とも呼ばれる）は、文字列の集合を効率的に格納し、検索するための木構造のデータ構造です。各ノードは文字列のプレフィックスに対応し、子ノードは次の文字に対応します。UCAの実装では、文字から照合要素へのマッピングを効率的に行うために、トライ木がよく利用されます。

4. 正規化 (Normalization)

Unicodeには、同じ文字を異なる方法で表現できる場合があります（例: 「が」は「か」と「゛」の結合、または単一の合成済み文字）。正規化は、これらの異なる表現を統一された形式に変換するプロセスです。UCAでは、比較の前に文字列を特定の正規化形式（通常はNFDまたはNFC）に変換することが推奨されます。このコミットでは exp/norm パッケージがインポートされており、正規化が考慮されていることがわかります。

5. 結合文字 (Combining Characters)

アクセントやダイアクリティカルマークなど、先行する文字と組み合わせて表示される文字を結合文字と呼びます。UCAでは、これらの結合文字もソート順に影響を与えるため、適切に処理する必要があります。

技術的詳細

このコミットは、Go言語の exp/locale/collate パッケージの初期構造を定義しています。主要なファイルとその役割は以下の通りです。

• src/pkg/exp/locale/collate/collate.go:

  • Level 型: UCAの比較レベル（Primary, Secondary, Tertiary, Quaternary, Identity）を定義します。これにより、ソートの厳密さを制御できます。
  • AlternateHandling 型: 可変要素（句読点や記号など）の扱い方を定義します。AltShifted, AltNonIgnorable, AltBlanked, AltShiftTrimmed などのオプションがあり、UCAの重要な設定の一つです。
  • Collator 構造体: 文字列の比較とソートを行うための主要な型です。Strength (比較レベルの最大値), Alternate (可変要素の扱い), Backwards (二次レベルの逆順ソート), HiraganaQuaternary (ひらがなの特殊な扱い), CaseLevel (大文字・小文字レベルの挿入), Numeric (数字の数値比較) などの設定フィールドを持ちます。
  • SetVariableTop メソッド: 可変要素の境界を設定するためのメソッドですが、このコミット時点では TODO: implement となっており、未実装です。
  • Root 変数: デフォルトの Collator インスタンスを提供します。
  • Buffer 構造体: 照合キー生成時のメモリ割り当てを避けるために再利用可能なバッファを提供します。ResetKeys メソッドでバッファをクリアできます。
  • Compare, CompareString, Key, KeyFromString メソッド: 文字列またはバイトスライスを比較し、照合キーを生成するための主要なAPIですが、このコミット時点ではすべて TODO: implement となっており、実際の比較ロジックはまだ実装されていません。

• src/pkg/exp/locale/collate/build/table.go:

  • table 構造体: collate パッケージの table 構造体とほぼ同じ構造を持つ中間的な型です。これは、照合データテーブルを構築する際に使用されます。
  • trie (メインのトライ木): 文字から照合要素へのマッピングを格納します。
  • expandElem: 拡張（一つの文字が複数の照合要素に展開される場合）に関する情報を格納します。
  • contractTries, contractElem, maxContractLen: 収縮（複数の文字が単一の照合要素に収縮される場合）に関する情報を格納します。
  • print メソッド: 構築された table をGoのソースコードとして出力する機能を提供します。これは、照合データをコンパイル時に埋め込むためのコード生成に利用されると考えられます。

• src/pkg/exp/locale/collate/export.go:

  • Init 関数: exp/locale/collate/build パッケージの Builder 型によって Collator インスタンスを作成するために使用されます。これは内部使用を意図しており、tableInitializer インターフェースを介してデータを受け取ります。
  • tableInitializer インターフェース: build パッケージの table 構造体が実装するインターフェースで、照合データテーブルの各要素（トライ木のインデックス、値、拡張要素、収縮トライ、収縮要素、最大収縮長）へのアクセスを提供します。

• src/pkg/exp/locale/collate/table.go:

  • table 構造体: collate パッケージの内部で実際に照合データが格納される構造体です。build パッケージの table とは異なり、こちらは実行時に使用されるデータ構造です。
  • appendNext メソッド: 入力バイトスライスから次のルーンまたは収縮に対応する重み（照合要素）を追加します。このメソッドは、トライ木 (t.index) を使用してルーンをルックアップし、拡張 (appendExpansion) や収縮 (matchContraction) の処理を行います。
  • getWeights 関数: colElem から重みを取得します。暗黙的な重み（UCAで定義されていない文字のデフォルト重み）の計算も行います。
  • appendExpansion メソッド: 拡張された照合要素を重みスライスに追加します。
  • matchContraction メソッド: 収縮をマッチングし、対応する重みを追加します。このメソッドは、正規化 (norm.NFC) や結合文字の処理 (CCC) を考慮しており、複雑なロジックを含んでいます。特に、非連続的な収縮（間に結合文字が挟まる場合）の処理や、セグメントオーバーフローのハンドリングが実装されています。

• src/pkg/exp/locale/collate/export_test.go:

  • テスト目的で内部の型や関数をエクスポートしています。Weights 型や GetTable 関数などが含まれ、table 構造体の appendNext メソッドのテストを可能にしています。

• src/pkg/exp/locale/collate/table_test.go:

  • appendNextTests 変数: appendNext メソッドの動作を検証するためのテストケースの集合です。
  • TestAppendNext 関数: appendNextTests を実行し、appendNext メソッドが期待通りに重みを生成し、バイトを消費するかどうかを検証します。特に、拡張、収縮、非連続的な収縮、正規化、結合文字の処理、セグメントオーバーフローなど、UCAの複雑な側面をカバーするテストが含まれています。

このコミットは、Go言語でUCAを実装するための基盤となるデータ構造と、そのデータ構造を操作する低レベルなロジック（特に appendNext メソッド）のスケルトンを導入しています。まだ完全な比較ロジックは含まれていませんが、照合要素の生成と処理の複雑な部分が既に考慮されていることがわかります。

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

このコミットで追加された主要なファイルと、その中で特に重要なコードの変更箇所は以下の通りです。

1. src/pkg/exp/locale/collate/collate.go:

   • Collator 構造体の定義と、その設定フィールド（Strength, Alternate, Backwards など）。
   • Buffer 構造体の定義と、ResetKeys メソッド。
   • Compare, CompareString, Key, KeyFromString メソッドのスケルトン（TODO: implement）。

2. src/pkg/exp/locale/collate/build/table.go:

   • table 構造体の定義（collate.table のビルド時中間表現）。
   • print メソッド: 構築された照合データをGoのソースコードとして出力する機能。

3. src/pkg/exp/locale/collate/table.go:

   • table 構造体の定義（実行時照合データ）。
   • appendNext メソッド: 文字列から照合要素を生成する主要なロジック。特に、拡張、収縮、非連続的な収縮、正規化の処理が含まれます。
   • matchContraction メソッド: 非連続的な収縮を含む、複雑な収縮マッチングロジック。

4. src/pkg/exp/locale/collate/export.go:

   • Init 関数と tableInitializer インターフェース: build パッケージと collate パッケージ間のデータ受け渡しを定義。

5. src/pkg/exp/locale/collate/table_test.go:

   • appendNextTests 変数: appendNext メソッドの動作を検証するための広範なテストケース。
   • TestAppendNext 関数: 上記テストケースを実行するテスト関数。

コアとなるコードの解説

このコミットの核心は、Unicode Collation Algorithm (UCA) の複雑なロジックをGo言語で実装するための基盤を構築している点にあります。特に src/pkg/exp/locale/collate/table.go 内の table 構造体と appendNext メソッドがその中心です。

collate.go の Collator

Collator 構造体は、ユーザーが照合動作をカスタマイズするための設定をカプセル化します。Strength は比較の深さを、Alternate は句読点や記号などの「可変要素」の扱い方を決定します。これらの設定は、UCAの柔軟性を反映しており、異なる言語やアプリケーションの要件に合わせてソート動作を調整するために不可欠です。

table.go の table 構造体

この table 構造体は、UCAの照合データ（Common Locale Data Repository: CLDR から派生）を効率的に格納するための内部表現です。

• index trie: これは、入力文字（ルーン）から対応する照合要素（重み）を高速にルックアップするためのトライ木です。UCAでは、単一の文字が複数の照合要素にマッピングされたり（拡張）、複数の文字が単一の照合要素にマッピングされたり（収縮）するため、このような複雑なマッピングを効率的に処理するためにトライ木が使用されます。
• expandElem: 拡張された照合要素のシーケンスを格納します。
• contractTries, contractElem, maxContractLen: 収縮に関する情報を格納します。収縮は、特定の文字シーケンスが単一の照合要素として扱われる場合に発生します。

table.go の appendNext メソッド

appendNext メソッドは、入力バイトスライス s から次の「照合可能な単位」（単一のルーン、または収縮を形成するルーンシーケンス）を抽出し、それに対応する照合要素の重みを w スライスに追加します。

このメソッドの複雑さは、UCAの以下の側面を処理する必要があることに起因します。

1. 通常のルックアップ: t.index.lookup(s) を使用して、トライ木から直接照合要素を取得します。
2. 拡張 (Expansion): tp == ceExpansionIndex の場合、一つのルーンが複数の照合要素に展開される処理 (t.appendExpansion) を行います。例えば、ドイツ語の ß が ss としてソートされる場合などです。
3. 収縮 (Contraction): tp == ceContractionIndex の場合、複数のルーンが単一の照合要素に収縮される処理 (t.matchContraction) を行います。例えば、チェコ語の ch が単一の文字として扱われる場合などです。
4. 分解 (Decomposition): tp == ceDecompose の場合、文字を正規化形式（NFCK）に分解し、その構成要素の照合要素を処理します。これは、結合文字の扱いに関連します。
5. 非連続的な収縮: matchContraction メソッド内で特に複雑なのが、非連続的な収縮の処理です。これは、収縮を形成する文字の間に結合文字が挟まっている場合でも、正しく収縮を認識して処理する能力を指します。例えば、a + COMBINING_ACUTE_ACCENT + b のようなシーケンスで、ab が収縮を形成する場合、間に挟まったアクセントを適切に処理する必要があります。norm.NFC.Properties や rune.LeadCCC(), rune.TrailCCC() を使用して、正規化と結合文字クラス (CCC) を考慮した複雑なスキャンロジックが実装されています。
6. セグメントオーバーフロー: matchContraction 内のコメントにあるように、正規化セグメントのサイズ制限（norm.MaxSegmentSize）を考慮した処理も行われています。これは、非常に長い結合文字のシーケンスが入力された場合に、バッファオーバーフローを防ぐためのものです。

このコミットは、これらの複雑なUCAのルールをGo言語で効率的に処理するための、低レベルなメカニズムの基礎を築いています。まだ高レベルなAPIは未実装ですが、この appendNext メソッドが、最終的な文字列比較の性能と正確性を決定する重要な部分となります。

関連リンク

• Unicode Collation Algorithm (UCA)
• Go言語の exp パッケージについて (Go 1.1のリリースノートですが、exp パッケージの概念について触れられています)
• Common Locale Data Repository (CLDR)

参考にした情報源リンク

• コミットメッセージと変更されたファイルの内容
• Unicode Collation Algorithm (UCA) の公式ドキュメント (TR10)
• Go言語の exp パッケージに関する一般的な情報
• トライ木に関する一般的なデータ構造の知識
• Unicode正規化に関する一般的な知識
• Go言語の exp/norm パッケージのドキュメント (GoDoc)
• Go言語のテストコードの読み方と理解