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

コミット

commit 0355a717517f7e1435e6f9eeb94e2b77d33eb43b
Author: Marcel van Lohuizen <mpvl@golang.org>
Date:   Wed May 9 12:03:55 2012 +0200

    exp/locale/collate: Add maketables tool and generated tables.
    Also set maxContractLen automatically.
    Note that the table size is much bigger than it needs to be.
    Optimization is best done, though, when the language specific
    tables are added.
    
    R=r
    CC=golang-dev
    https://golang.org/cl/6167044

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

https://github.com/golang/go/commit/0355a717517f7e1435e6f9eeb94e2b77d33eb43b

元コミット内容

exp/locale/collate パッケージに maketables ツールと生成されたテーブルを追加しました。 また、maxContractLen を自動的に設定するようにしました。 テーブルサイズは必要以上に大きいですが、言語固有のテーブルが追加された際に最適化を行うのが最善です。

変更の背景

このコミットは、Go言語の実験的な exp/locale/collate パッケージにおける、Unicode Collation Algorithm (UCA) の実装に関連するものです。UCAは、異なる言語や文化圏におけるテキストのソート順序を定義するための国際標準です。このアルゴリズムは非常に複雑で、大量のデータ（照合要素テーブル）を必要とします。

これまでの実装では、照合テーブルが手動で管理されていたか、あるいは効率的な生成メカニズムが不足していた可能性があります。このコミットの目的は、UCAのデータ（特にDUCET: Default Unicode Collation Element Table）からGo言語のコードとして利用可能な照合テーブルを自動生成するツール (maketables) を導入し、その生成されたテーブルをリポジトリに含めることです。これにより、照合機能の正確性と保守性が向上します。

また、照合処理において重要な「収縮（Contraction）」の最大長 (maxContractLen) を自動的に決定する機能も追加されています。収縮とは、複数の文字が単一の照合要素として扱われるケース（例: ドイツ語の "ß" が "ss" としてソートされる場合など）を指します。この値の自動設定は、手動での設定ミスを防ぎ、アルゴリズムの正確な動作を保証するために重要です。

コミットメッセージにある「テーブルサイズは必要以上に大きい」という言及は、初期実装段階でのデータ構造の最適化がまだ不十分であることを示唆しています。これは、まず機能を実現し、その後にパフォーマンスやメモリ使用量の最適化を行うという一般的なソフトウェア開発のアプローチに沿っています。特に、言語固有のテーブルが追加される際に、より効率的なデータ表現が求められることが予想されます。

前提知識の解説

Unicode Collation Algorithm (UCA)

UCAは、Unicode文字列を言語的に正しい順序でソートするためのアルゴリズムです。単なるコードポイント順のソートでは、多言語環境での正しいソート順序（例: ドイツ語のウムラウトやスペイン語のñなど）を実現できません。UCAは、以下の主要な概念に基づいています。

• 照合要素 (Collation Element): 各文字または文字のシーケンスに割り当てられる数値のキーで、ソートの基本単位となります。
• 照合レベル (Collation Level): UCAは複数のレベルでソートを行います。
  • Primary Level: 基本的な文字の区別（例: 'a' と 'b'）。
  • Secondary Level: アクセントやダイアクリティカルマークの区別（例: 'a' と 'á'）。
  • Tertiary Level: 大文字・小文字の区別や句読点の区別（例: 'a' と 'A'）。
  • Quaternary Level: 可変照合要素（Variable Collation Elements）の扱いを定義します。これは、句読点や記号などの扱いを制御するために使用されます。
• Default Unicode Collation Element Table (DUCET): Unicode Consortiumによって提供される、UCAのデフォルトの照合要素の定義を含むデータファイルです。このファイルは、各Unicodeコードポイントがどのように照合されるべきか（どの照合要素にマッピングされるか）を規定しています。
• 収縮 (Contraction): 複数の文字のシーケンスが単一の照合要素として扱われる場合です。例えば、チェコ語の "ch" は単一の文字として扱われ、"h" と "i" の間にソートされます。
• 拡張 (Expansion): 単一の文字が複数の照合要素に展開される場合です。例えば、ドイツ語の "ß" が "ss" としてソートされる場合などです。
• 正規化 (Normalization): UCAは、照合を行う前に文字列を特定のUnicode正規化形式（通常はNFD: Normalization Form Canonical Decomposition）に変換することを推奨しています。これにより、異なる表現を持つ同じ文字（例: 合成済み文字と分解済み文字）が同じように扱われることが保証されます。

Go言語の exp パッケージ

Go言語の標準ライブラリには、安定版のAPIが含まれていますが、新しい機能や実験的なAPIは exp (experimental) リポジトリで開発されることがあります。exp/locale/collate は、Go言語でロケールに依存したテキスト照合機能を提供するための実験的なパッケージです。exp パッケージのコードは、将来的に標準ライブラリに統合される可能性がありますが、その時点ではAPIの変更や削除が行われる可能性があることを意味します。

go generate とコード生成

Go言語では、go generate コマンドを使用してコード生成を行うことが一般的です。これは、ソースコード内の特定のコメント (//go:generate) を解析し、そこに記述されたコマンドを実行することで、Goのソースファイルを自動生成する仕組みです。このコミットで追加される maketables ツールは、この go generate のワークフローの一部として利用されることが想定されます。

技術的詳細

このコミットは、Go言語の exp/locale/collate パッケージにおける照合テーブルの生成プロセスを自動化し、その結果をリポジトリに含めることを目的としています。

maketables ツールの役割

maketables は、Unicode Consortiumが提供するDUCET (Default Unicode Collation Element Table) をダウンロードし、そのデータを解析してGo言語のソースコード（tables.go）として出力するツールです。このツールは、以下の主要な機能を持ちます。

1. DUCETの取得: http://unicode.org/Public/UCA/ から指定されたUnicodeバージョンの allkeys.txt (DUCET) をHTTP経由でダウンロードします。デバッグ目的でローカルファイルを使用するオプションも提供されています。
2. DUCETの解析: allkeys.txt は特定のフォーマットを持つテキストファイルであり、maketables ツールはこのファイルを1行ずつ読み込み、正規表現などを用いて照合要素の定義を抽出します。
   • 各行は、左辺（照合される文字またはシーケンス）と右辺（対応する照合要素）に分かれています。
   • 照合要素は、プライマリ、セカンダリ、ターシャリの3つのレベルのキーで構成されます。
   • 可変照合要素（Variable Collation Elements）の範囲を特定し、variableTop の値を決定します。
3. 照合テーブルの構築: 解析されたDUCETデータは、exp/locale/collate/build パッケージの Builder を使用して、Go言語の内部データ構造（トライ木など）に変換されます。
   • Builder は、照合要素、収縮、拡張などの情報を効率的に検索できるデータ構造に変換する役割を担います。
   • 特に、収縮の処理において、processContractions メソッド内で maxContractLen が自動的に計算され、設定されます。これは、収縮シーケンスの最大長を追跡し、照合器が適切なバッファサイズを確保できるようにするために重要です。
4. Goソースコードの生成: 構築された内部データ構造は、tables.go というGoソースファイルとして標準出力に出力されます。このファイルには、照合器が実行時に使用する静的なデータテーブルが含まれます。
   • 生成される tables.go には、rootExpandElem (拡張要素のデータ) や rootContractElem (収縮要素のデータ) など、大量の数値データが含まれています。これらのデータは、UCAの複雑なルールを効率的に適用するために必要です。
   • rootValues は、各Unicodeコードポイントに対応する照合要素のプライマリ、セカンダリ、ターシャリのキーを格納する主要なテーブルです。

maxContractLen の自動設定

src/pkg/exp/locale/collate/build/builder.go の processContractions 関数内で、e.contraction() が真の場合（つまり、現在のエントリが収縮を表す場合）、その収縮文字列の長さ len(e.str) が現在の b.t.maxContractLen よりも大きい場合に、b.t.maxContractLen が更新されます。これにより、生成されるテーブルのメタデータとして、最も長い収縮シーケンスの長さが正確に記録され、照合器が実行時にこの情報を使用して適切な処理を行うことができます。

tables.go の役割

tables.go は maketables ツールによって生成されるファイルであり、手動で編集されるべきではありません。このファイルには、UCAのルールに基づいた膨大な照合データがGoのコードとして埋め込まれています。これにより、exp/locale/collate パッケージは外部データファイルに依存することなく、自己完結型で照合機能を提供できます。

ビルドプロセスへの統合

src/pkg/exp/locale/collate/Makefile の変更は、maketables ツールをビルドプロセスに統合する方法を示しています。

• maketables: maketables.go ルールは、maketables.go から実行可能な maketables ツールをビルドします。
• tables: maketables ルールは、ビルドされた maketables ツールを実行し、その出力を tables.go にリダイレクトします。その後、gofmt -w tables.go を実行して、生成されたコードをGoの標準フォーマットに整形します。
• testshort: maketables は、テスト時に maketables ツールがコンパイルされることを保証し、ツール自体の健全性をチェックします。

このMakefileの変更により、開発者は make tables コマンドを実行するだけで、最新のDUCETデータに基づいて照合テーブルを更新できるようになります。

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

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

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

   • maketables ツールをビルドし、tables.go を生成するためのルールが追加されました。
   • CLEANFILES+=maketables が追加され、クリーンアップ時に maketables 実行ファイルも削除されるようになりました。
   • testshort: maketables が追加され、テスト時に maketables がコンパイルされることを保証します。

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

   • func (b *Builder) processContractions() 内で、収縮文字列の長さ (len(e.str)) を基に b.t.maxContractLen を自動的に更新するロジックが追加されました。

     if e.contraction() {
         if len(e.str) > b.t.maxContractLen {
             b.t.maxContractLen = len(e.str)
         }
         // ... 既存のロジック ...
     }
     

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

   • func (t *table) print(w io.Writer, name string) 関数内で、生成されるテーブルの出力に t.maxContractLen の値を含めるように変更されました。

     p("%d,\\n\", t.maxContractLen)\n
     

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

   • Root = Collator{} の定義が削除されました。これは、tables.go で生成される Root 照合器を使用するように変更されたためです。

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

   • このファイル全体が新規追加されました。DUCETをダウンロード、解析し、Go言語の照合テーブルを生成するメインのロジックが含まれています。
   • flag パッケージを使用して、DUCETのURLやローカルファイルの使用を制御するコマンドライン引数を定義しています。
   • openReader 関数は、URLまたはローカルファイルからデータを読み込むための io.ReadCloser を返します。
   • parseUCA 関数は、DUCETファイルを解析し、build.Builder に照合要素を追加します。この関数内で maxVar (可変照合要素の最大値) と minNonVar (非可変照合要素の最小値) を特定し、variableTop の値を決定します。
   • main 関数は、build.NewBuilder() でビルダーを初期化し、parseUCA でDUCETを解析し、b.Build("") でテーブルを構築し、最終的に b.Print(os.Stdout) で生成されたテーブルを標準出力に出力します。

6. src/pkg/exp/locale/collate/tables.go:

   • このファイル全体が新規追加されました。maketables ツールによって生成される、実際の照合データ（rootExpandElem, rootContractElem, rootValues など）を含むGoソースファイルです。このファイルは非常に大きく、コミットログにはその一部のみが表示されています。

コアとなるコードの解説

maketables.go の parseUCA 関数

この関数は、DUCETファイル (allkeys.txt) を読み込み、その内容を解析して build.Builder に照合要素を追加する中心的な役割を担います。

func parseUCA(builder *build.Builder) int {
    maxVar, minNonVar := 0, 1<<30 // maxVar: 可変照合要素の最大値, minNonVar: 非可変照合要素の最小値
    r, err := openReader(*ducet) // DUCETファイルを開く
    failonerror(err)
    defer r.Close()
    input := bufio.NewReader(r)
    colelem := regexp.MustCompile(`\[([.*])([0-9A-F.]+)\]`) // 照合要素の正規表現
    for i := 1; err == nil; i++ {
        l, prefix, e := input.ReadLine()
        err = e
        line := string(l)
        // ... (コメント行やプロパティ行のスキップ/解析) ...

        // 照合エントリの解析
        part := strings.Split(line, " ; ")
        // ... (エラーチェック) ...

        lhs := []rune{} // 左辺 (照合される文字シーケンス)
        for _, v := range strings.Split(part[0], " ") {
            // ... (左辺のUnicodeコードポイントを解析) ...
            lhs = append(lhs, rune(convHex(i, v)))
        }

        var n int
        rhs := [][]int{} // 右辺 (照合要素のシーケンス)
        for _, m := range colelem.FindAllStringSubmatch(part[1], -1) {
            // ... (右辺の照合要素を解析) ...
            elem := []int{}
            for _, h := range strings.Split(m[2], ".") {
                elem = append(elem, convHex(i, h))
            }
            if p := elem[0]; m[1] == "*" { // 可変照合要素の場合
                if p > maxVar {
                    maxVar = p
                }
            } else if p > 0 && p < minNonVar { // 非可変照合要素の場合
                minNonVar = p
            }
            rhs = append(rhs, elem)
        }
        // ... (コメントのチェック) ...
        builder.Add(lhs, rhs) // ビルダーに照合要素を追加
    }
    if maxVar >= minNonVar {
        log.Fatalf("found maxVar > minNonVar (%d > %d)", maxVar, minNonVar)
    }
    return maxVar // 可変照合要素の最大値を返す
}

この関数は、DUCETの各行を解析し、左辺の文字シーケンスと右辺の照合要素のシーケンスを抽出します。特に、照合要素のプライマリキーが可変照合要素の範囲内にあるかどうかをチェックし、maxVar と minNonVar を更新することで、variableTop の値を正確に決定します。最終的に、解析されたデータは builder.Add メソッドを通じて build.Builder に渡され、内部的なデータ構造が構築されます。

builder.go の processContractions 関数における maxContractLen の自動設定

この変更は、照合器が収縮を処理する際に、必要なバッファサイズを動的に決定できるようにするために重要です。

func (b *Builder) processContractions() {
    // ...
    for _, e := range b.entry {
        if e.contraction() { // エントリが収縮の場合
            if len(e.str) > b.t.maxContractLen { // 現在の収縮文字列の長さが最大長より大きい場合
                b.t.maxContractLen = len(e.str) // maxContractLenを更新
            }
            // ...
        }
    }
    // ...
}

このコードスニペットは、Builder が照合要素を処理する際に、すべての収縮シーケンスを走査し、その中で最も長いシーケンスの長さを maxContractLen として記録します。この値は、生成される tables.go に含まれ、実行時に照合器が収縮を効率的に処理するために利用されます。

tables.go の生成

tables.go は、maketables ツールによって生成されるGoのソースファイルであり、Goのビルドシステムによってコンパイルされます。このファイルには、以下のようなデータ構造が含まれます。

• rootExpandElem: 拡張要素のデータ。
• rootContractElem: 収縮要素のデータ。
• rootValues: 各Unicodeコードポイントに対応する照合要素のプライマリ、セカンダリ、ターシャリのキーを格納する主要なテーブル。
• rootTable: 上記のデータ構造をまとめた table 型のインスタンス。
• _Root および Root: collate.Collator 型のインスタンスで、rootTable を参照し、照合の強度 (Strength) や可変照合要素のトップ (variableTop) などの設定を含みます。

これらのデータは、Goの照合パッケージが効率的に動作するために不可欠です。

関連リンク

• Unicode Collation Algorithm (UCA): https://unicode.org/reports/tr10/
• Default Unicode Collation Element Table (DUCET): https://unicode.org/Public/UCA/ (コミット時点のバージョンは 6.0.0 が使用されていますが、最新版は適宜確認してください)
• Go言語の exp リポジトリ: https://go.googlesource.com/exp

参考にした情報源リンク

• https://github.com/golang/go/commit/0355a717517f7e1435e6f9eeb94e2b77d33eb43b
• Unicode Collation Algorithm (UCA) の公式ドキュメント
• Go言語の exp/locale/collate パッケージのソースコード (コミット前後の変更点)
• Go言語のコード生成に関する一般的な情報 (go generate など)
• Go言語の Makefile の慣習に関する情報