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

このコミットは、Go言語の実験的なロケールパッケージ exp/locale/collate において、照合（collation）のテーラリング（tailoring）機能の実装に向けた最初の変更を導入するものです。具体的には、照合要素（collation elements）の内部表現を改善し、テーラリングをより容易に適用できるようにするための基盤を構築しています。

コミット

commit 18aa55c169774b96b210f234e88c98e78a1c513f
Author: Marcel van Lohuizen <mpvl@golang.org>
Date:   Sat Sep 1 14:13:37 2012 +0200

    exp/locale/collate: first changes that introduce implementation of tailorings:
    - Elements in the array are now sorted as a linked list.  This makes it easier to
      apply tailorings.
    - Added code to sort entries by collation elements.
    - Added logical reset points.  This is used for tailoring relative to certain
      properties, rather than characters.
    
    NOTE: all code for type entry should now be in order.go.  To keep the diffs for
    this CL reasonable, though, the existing code is left in builder.go.  I'll move
    this in a separate CL.
    
    R=r
    CC=golang-dev
    https://golang.org/cl/6493063

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

https://github.com/golang/go/commit/18aa55c169774b96b210f234e88c98e78a1c513f

元コミット内容

exp/locale/collate: テーラリングの実装を導入する最初の変更点:

• 配列内の要素が連結リストとしてソートされるようになりました。これにより、テーラリングの適用が容易になります。
• 照合要素によってエントリをソートするコードが追加されました。
• 論理的なリセットポイントが追加されました。これは、文字ではなく特定のプロパティに対するテーラリングに使用されます。

注記: entry 型のすべてのコードは order.go に移動されるべきです。しかし、この変更リスト（CL）の差分を妥当な範囲に保つため、既存のコードは builder.go に残されています。これは別のCLで移動されます。

変更の背景

このコミットの背景には、Go言語の国際化（i18n）対応、特にテキストのソート順序を扱う照合（Collation）機能の強化があります。Unicode Collation Algorithm (UCA) は、多言語環境でのテキストソートの標準を提供しますが、特定の言語や地域（ロケール）においては、UCAのデフォルトルールに加えて、さらに細かい調整（テーラリング）が必要になります。

例えば、ドイツ語では「ä」が「a」と「e」の間にソートされるべきであったり、スウェーデン語では「å」が「a」の後にソートされるべきであったりします。このようなロケール固有のソート規則を適用するためには、UCAの基本ルールを「テーラリング」する必要があります。

このコミット以前の exp/locale/collate パッケージは、テーラリングを効率的にサポートするための内部構造が不足していました。特に、照合要素のリストが固定的な配列として扱われていたため、新しいテーラリングルールを挿入したり、既存のルールを変更したりする際に、大規模なデータ構造の再構築が必要となり、非効率的でした。

このコミットは、テーラリングをより柔軟かつ効率的に適用できるように、内部データ構造を連結リストベースに変更し、テーラリングの適用に必要なソート機能と「論理的なリセットポイント」という新しい概念を導入することで、この課題に対処しようとしています。これにより、将来的に複雑なテーラリングルールをGoの照合エンジンに組み込むための強固な基盤が築かれます。

前提知識の解説

照合（Collation）

照合とは、テキストデータを特定の順序で並べ替えるプロセスです。これは、辞書順ソート、電話帳ソート、データベースのインデックス作成など、様々なアプリケーションで不可欠です。多言語環境では、単に文字コードの順序でソートするだけでは不十分であり、言語や地域によって異なるソート規則（例: アクセント記号付き文字、合字、特殊文字の扱い）を考慮する必要があります。

Unicode Collation Algorithm (UCA)

UCAは、Unicode Consortiumによって定義された、多言語テキストの照合のための標準アルゴリズムです。UCAは、テキストを「照合要素（Collation Elements）」のシーケンスに変換し、これらの要素を比較することでソート順を決定します。照合要素は通常、プライマリ（Primary）、セカンダリ（Secondary）、ターシャリ（Tertiary）、クォータナリ（Quaternary）の4つのレベルの重み（weight）を持ちます。

• プライマリ（Primary）: 基本的な文字の順序を決定します（例: 'a' と 'b'）。
• セカンダリ（Secondary）: アクセント記号やダイアクリティカルマークの違いを扱います（例: 'a' と 'á'）。
• ターシャリ（Tertiary）: 大文字と小文字、または文字の幅の違いを扱います（例: 'a' と 'A'）。
• クォータナリ（Quaternary）: 可変要素（variable elements）の扱いを決定します。これは通常、句読点や記号のソート順に影響します。

テーラリング（Tailoring）

UCAは包括的なアルゴリズムですが、特定の言語やロケールでは、UCAのデフォルトルールでは対応できない、より具体的なソート規則が必要になります。このロケール固有の調整を「テーラリング」と呼びます。テーラリングは、既存の照合要素の重みを変更したり、新しい照合要素を挿入したり、特定の文字シーケンスのソート順を定義したりすることで行われます。

例えば、UCAのデフォルトでは「ch」が「c」と「h」の2文字として扱われる場合でも、スペイン語の伝統的な照合では「ch」を単一の文字として「c」の後にソートする、といったテーラリングが考えられます。

連結リスト（Linked List）

連結リストは、データ要素（ノード）が順序付けられたシーケンスで構成されるデータ構造です。各ノードはデータ自体と、次のノードへの参照（ポインタ）を含みます。これにより、配列のように連続したメモリ領域を必要とせず、要素の挿入や削除が効率的に行えます。テーラリングにおいて、照合要素の間に新しい要素を挿入する必要がある場合、連結リストは配列よりも柔軟な構造を提供します。

論理的なリセットポイント（Logical Reset Points）

UCAのテーラリングルールでは、特定の文字やプロパティに基づいてソート順を調整することがあります。例えば、「すべての句読点は、他のすべての文字の後にソートされる」といったルールです。このようなルールを効率的に適用するために、「論理的なリセットポイント」が導入されます。これは、特定の照合レベル（プライマリ、セカンダリなど）において、ソート順がリセットされる仮想的な位置を示します。これにより、特定のプロパティを持つ文字群全体に対して、相対的なテーラリングを適用することが可能になります。

技術的詳細

このコミットは、exp/locale/collate パッケージの内部構造に根本的な変更を加えています。主な変更点は以下の通りです。

1. entry 構造体の変更と連結リスト化:

   • src/pkg/exp/locale/collate/build/builder.go 内の entry 構造体に、prev, next (それぞれ前後の entry へのポインタ)、および level (次のエントリとの違いがある照合レベル) フィールドが追加されました。これにより、entry のシーケンスが連結リストとして扱われるようになり、テーラリングによる要素の挿入や削除が容易になります。
   • exclude フィールドが追加され、テーブルに含めるべきではないエントリ（例: 暗黙的に導出される値や論理的なリセットポイント）をマークできるようになりました。
   • logical フィールドが追加され、エントリが論理的なアンカー（リセットポイント）であるかどうかを示します。

2. ordering 構造体の導入:

   • src/pkg/exp/locale/collate/build/order.go という新しいファイルが追加され、ordering という構造体が定義されました。この構造体は、照合要素の順序付けを管理する中心的な役割を担います。
   • entryMap (文字列から entry へのマップ) と ordered (entry のスライス) を持ち、照合要素の検索と順序付けを効率的に行います。
   • makeRootOrdering 関数は、初期の ordering オブジェクトを作成し、UCAのルールで定義されているいくつかの重要な論理的なリセットポイント（例: first tertiary ignorable, __END__）で初期化します。これらのアンカーは、テーラリングの基準点として機能します。

3. 照合要素のソート機能の追加:

   • ordering 構造体には sort() メソッドが追加されました。これは、entry のスライスを照合要素に基づいてソートし、連結リストの prev, next, level フィールドを適切に設定します。これにより、テーラリングが適用された後の照合要素の正しい順序が維持されます。
   • entryLess 関数は、2つの entry を比較し、どちらが先にソートされるべきかを決定します。これは、照合要素の比較だけでなく、論理的なアンカーの特性も考慮します。

4. 照合要素の比較と重み計算の改善:

   • src/pkg/exp/locale/collate/build/colelem.go に、nextWeight, nextVal, compareWeights といった新しい関数が追加されました。
   • nextWeight は、与えられた照合要素のシーケンスとレベルに基づいて、次に可能な照合重みを計算します。これは、テーラリングで新しい要素を挿入する際に、適切な重みを割り当てるために使用されます。
   • compareWeights は、2つの照合要素のシーケンスを比較し、どちらが先にソートされるべきか、および違いが見つかった照合レベルを返します。これは、照合のソートロジックの核心部分です。

5. Builder 構造体の変更:

   • src/pkg/exp/locale/collate/build/builder.go の Builder 構造体から、entryMap と entry フィールドが削除され、代わりに root (型は ordering) が追加されました。これにより、照合要素の管理が ordering 構造体に委譲され、Builder の責務が簡素化されました。
   • Add メソッドは、新しいエントリを b.root.newEntry を介して ordering に追加するようになりました。
   • simplify, processExpansions, processContractions, buildTrie などの既存のメソッドは、b.entry を直接操作する代わりに、b.root の front() メソッドや nextIndexed() メソッドを使用して連結リストを走査するように変更されました。

この変更により、照合要素の内部表現がより柔軟になり、将来的に複雑なテーラリングルールを効率的に実装するための基盤が確立されました。特に、連結リストと論理的なリセットポイントの導入は、テーラリングの適用におけるパフォーマンスと正確性を向上させる上で重要な役割を果たします。

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

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

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

   • entry 構造体に prev, next, level, exclude, logical フィールドが追加。
   • Builder 構造体から entryMap と entry フィールドが削除され、root ordering フィールドが追加。
   • Add メソッドが b.root.newEntry を使用するように変更。
   • simplify, processExpansions, processContractions, buildTrie メソッドが、b.root を介して entry を走査するように変更。
   • genColElems 関数が Builder から ordering に移動。

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

   • TestGenColElems, TestSimplify, TestExpand, TestContract などのテストが、b.entry の代わりに b.root を使用するように更新。

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

   • nextWeight 関数が追加。
   • nextVal 関数が追加。
   • compareWeights 関数が追加。

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

   • nextWeightTests と compareTests という新しいテストデータ構造が追加。
   • TestNextWeight と TestCompareWeights という新しいテスト関数が追加。

5. src/pkg/exp/locale/collate/build/order.go (新規ファイル):

   • logicalAnchor 型と定数 (firstAnchor, noAnchor, lastAnchor) が定義。
   • entry 構造体のメソッド (nextIndexed, remove, insertAfter) が定義。
   • entryLess 関数が定義。
   • sortedEntries 型と sort.Interface の実装が定義。
   • ordering 構造体が定義。
   • ordering のメソッド (insert, newEntry, find, makeRootOrdering, clone, front, sort, genColElems) が定義。

6. src/pkg/exp/locale/collate/build/order_test.go (新規ファイル):

   • makeList 関数が定義。
   • TestNextIndexed, TestRemove, TestInsertAfter, TestEntryLess といった ordering および entry の新しい動作を検証するテスト関数が追加。

コアとなるコードの解説

src/pkg/exp/locale/collate/build/order.go

このファイルは、照合要素の順序付けとテーラリングの適用を管理する新しい中心的なロジックを含んでいます。

type entry struct の変更 (概念的な移動)

コミットメッセージにあるように、entry 型のコードは最終的に order.go に移動される予定ですが、このコミットでは builder.go に残されています。しかし、その動作は order.go で定義されたメソッドによって補完されます。

• nextIndexed() (*entry, collate.Level): このメソッドは、現在のエントリから連結リストをたどり、テーブルにインデックス付けする必要がある次のエントリを返します。exclude フラグが設定されているエントリ（例: 論理的なリセットポイントや暗黙的に導出されるエントリ）はスキップされます。返される collate.Level は、現在のエントリと次のインデックス付きエントリとの間で違いが生じる照合レベルを示します。

• remove(): このメソッドは、エントリを連結リストから削除します。これは、テーラリングによってエントリが不要になった場合に使用されます。アンカー（論理的なリセットポイント）は削除できないという制約があります。

• insertAfter(n *entry): このメソッドは、指定されたエントリ n を現在のエントリ e の直後に挿入します。これにより、連結リストの途中に新しいテーラリングルールを効率的に追加できます。

entryLess(a, b *entry) bool

この関数は、2つの entry を比較し、a が b の前にソートされるべき場合に true を返します。これは、compareWeights 関数を使用して照合要素を比較し、さらに論理的なアンカーの特性（firstAnchor は常に最初に、lastAnchor は常に最後にソートされる）を考慮します。

type ordering struct

この新しい構造体は、照合要素のコレクションとその順序付けを管理します。

• entryMap map[string]*entry: 文字列（ルーンのシーケンス）から対応する entry へのマップ。これにより、特定の文字列の照合要素を効率的に検索できます。
• ordered []*entry: entry のスライス。これは、照合要素のソートされた順序を保持するために使用されます。

makeRootOrdering() ordering

この関数は、新しい ordering オブジェクトを初期化し、UCAで定義されているいくつかの重要な論理的なリセットポイント（アンカー）を追加します。これらのアンカーは、テーラリングの基準点として機能し、連結リストの先頭と末尾に配置されます。

sort()

ordering 構造体のこのメソッドは、ordered スライス内のすべての entry を照合要素に基づいてソートします。ソート後、各エントリの prev, next, level フィールドが適切に設定され、連結リストが構築されます。これにより、テーラリングが適用された後の照合要素の正しい順序が維持されます。

genColElems(str string) [][]int

このメソッドは、与えられた文字列のルーンから照合要素の配列を生成します。これは、ordering の find メソッドを使用して、各ルーンに対応する照合要素を取得します。

src/pkg/exp/locale/collate/build/colelem.go

このファイルには、照合要素の重みを操作および比較するための新しいユーティリティ関数が追加されています。

nextWeight(level collate.Level, elems [][]int) [][]int

この関数は、与えられた照合要素のシーケンス elems と照合レベル level に基づいて、次に可能な照合重みを計算します。これは、テーラリングで新しい要素を挿入する際に、既存の要素の間に適切な重みを割り当てるために使用されます。例えば、プライマリレベルで次の重みを計算する場合、最初の照合要素のプライマリ重みをインクリメントし、セカンダリとターシャリの重みをデフォルト値にリセットします。

nextVal(elems [][]int, i int, level collate.Level) (index, value int)

このヘルパー関数は、照合要素のシーケンス elems 内で、指定された level において非ゼロの重みを持つ次の要素を見つけます。これは、compareWeights 関数内で使用され、異なるレベルでの比較を効率的に行います。

compareWeights(a, b [][]int) (result int, level collate.Level)

この重要な関数は、2つの照合要素のシーケンス a と b を比較します。

• result は、a が b より小さい場合は -1、大きい場合は 1、等しい場合は 0 を返します。
• level は、違いが見つかった最初の照合レベル（プライマリ、セカンダリ、ターシャリ、クォータナリ、または Identity）を返します。

この関数は、UCAの照合ルールに従って、プライマリからクォータナリまでの各レベルで要素を比較します。これにより、正確なソート順序が決定されます。

これらの変更により、Goの照合エンジンは、より複雑でロケール固有のテーラリングルールを効率的に処理できるようになり、国際化対応が強化されます。

関連リンク

• Unicode Collation Algorithm (UCA): https://unicode.org/reports/tr10/
• Common Locale Data Repository (CLDR): https://cldr.unicode.org/
• Go言語の exp/locale パッケージ (現在の golang.org/x/text/collate に相当): https://pkg.go.dev/golang.org/x/text/collate

参考にした情報源リンク

• コミット情報: /home/orange/Project/comemo/commit_data/13729.txt
• GitHub上のコミットページ: https://github.com/golang/go/commit/18aa55c169774b96b210f234e88c98e78a1c513f
• Go言語の公式ドキュメント (特に golang.org/x/text/collate パッケージに関するもの)
• Unicode Collation Algorithm (UCA) の仕様書
• CLDRのドキュメント (テーラリングルールに関する情報)
• 連結リストに関する一般的なデータ構造の知識
• Go言語のテストフレームワーク testing パッケージに関する知識