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

このコミットは、Go言語の実験的なロケールパッケージ exp/locale/collate に、Unicode Collation Algorithm (UCA) の中核をなす「照合要素 (collation elements)」の表現と操作に関するコードを追加するものです。具体的には、照合要素を uint32 型で表現し、通常の文字、結合文字 (contractions)、展開文字 (expansions)、分解文字 (decompositions) に対応するための構造と関数が導入されています。これにより、Go言語でより正確な文字列のソートと比較が可能になります。

コミット

commit bb3f3c97759ef9819ff18f8f9d34603867658d00
Author: Marcel van Lohuizen <mpvl@golang.org>
Date:   Wed Apr 25 13:16:24 2012 +0200

    exp/locale/collate: added representation for collation elements
    (see http://www.unicode.org/reports/tr10/).
    
    R=r, r
    CC=golang-dev
    https://golang.org/cl/5981048

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

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

元コミット内容

exp/locale/collate: added representation for collation elements
(see http://www.unicode.org/reports/tr10/).

変更の背景

このコミットは、Go言語が国際化対応を強化する一環として、文字列のソート順序を言語や地域（ロケール）に応じて適切に処理するための基盤を構築するために行われました。特に、Unicode Collation Algorithm (UCA) は、異なる言語における文字の並び順の複雑さを扱うための標準的なアルゴリズムです。UCAは、文字を「照合要素」と呼ばれる数値表現に変換し、それらを比較することでソート順を決定します。このコミットは、その照合要素をGo言語内で効率的かつ正確に表現・操作するためのデータ構造と関数を導入することで、UCAの実装に向けた重要なステップを踏み出しています。これにより、Goアプリケーションが多言語環境でより自然なソート結果を提供できるようになります。

前提知識の解説

Unicode Collation Algorithm (UCA) と Unicode Technical Report #10 (TR10)

Unicode Collation Algorithm (UCA) は、Unicode文字列の比較とソートのための標準的なアルゴリズムです。これは、Unicode Technical Report #10 (TR10) で詳細に定義されています。UCAの目的は、異なる言語や文化圏における文字列のソート順序の複雑さを統一的に扱うことです。例えば、ドイツ語では 'ä' は 'a' と 'e' の間にソートされることがありますが、スウェーデン語では 'z' の後にソートされるなど、言語によってソート規則が大きく異なります。UCAはこれらの差異を吸収し、一貫したソート結果を提供します。

照合要素 (Collation Elements)

UCAの中核をなすのが「照合要素」です。これは、各Unicode文字（または文字のシーケンス）に割り当てられる数値のリストであり、文字列のソート順を決定するために使用されます。照合要素は通常、複数のレベルの「重み (weights)」で構成されます。

プライマリ重み (Primary Weight): 文字の基本的な順序を決定します。例えば、'a' と 'b' の違いを区別します。これは最も重要なレベルであり、異なる文字を区別するために使用されます。
セカンダリ重み (Secondary Weight): プライマリ重みが同じ文字間の違いを区別します。主にアクセント記号やダイアクリティカルマーク（例: 'a' と 'á'）を区別するために使用されます。
ターシャリ重み (Tertiary Weight): プライマリ重みとセカンダリ重みが同じ文字間の違いを区別します。主に大文字・小文字の違い（例: 'a' と 'A'）や、幅の違い（全角・半角）などを区別するために使用されます。
クォータナリ重み (Quaternary Weight): 一部の実装では、句読点や空白文字など、さらに細かい区別を行うためにこのレベルが使用されることがあります。

これらの重みは、文字列を比較する際に階層的に適用されます。まずプライマリ重みが比較され、それが同じであればセカンダリ重みが比較され、といった具合に進みます。

結合 (Contractions) と展開 (Expansions)

UCAでは、単一のUnicode文字が複数の照合要素にマッピングされたり（展開）、複数のUnicode文字のシーケンスが単一の照合要素にマッピングされたり（結合）することがあります。

結合 (Contractions): 特定の文字の並び（例: チェコ語の "ch"）が、単一の文字として扱われる場合です。この場合、複数の文字が結合されて一つの照合要素にマッピングされます。
展開 (Expansions): 単一の文字が、ソートの目的で複数の照合要素に分解される場合です。例えば、ドイツ語の 'ß' が 'ss' として扱われるようなケースです。

暗黙的な重み (Implicit Weights)

UCAでは、明示的に照合要素が定義されていない文字に対しても、そのUnicodeコードポイントに基づいて暗黙的なプライマリ重みが割り当てられます。これにより、すべてのUnicode文字がソート可能になります。

技術的詳細

このコミットでは、Go言語において照合要素を uint32 型で表現するための詳細なビットフィールド構造が定義されています。これにより、単一の uint32 値の中にプライマリ、セカンダリ、ターシャリの各重み、および結合や展開、分解といった特殊な照合要素の情報を効率的に格納できるようになっています。

照合要素の表現 (`uint32`)

照合要素は uint32 型で表現され、その値の範囲によって異なる種類の照合要素を識別します。

通常の照合要素 (Normal Collation Elements):
- 0x00000000 から 0x7FFFFFFF の範囲。
- プライマリ重みを持つ場合: 010ppppp pppppppp pppppppp tttttttt の形式。
  - p*: プライマリ照合値 (21ビット)
  - t*: ターシャリ照合値 (8ビット)
  - isPrimary フラグ (0x40000000) がセットされます。
  - セカンダリ重みは defaultSecondary (0x20) になります。
- セカンダリ重みを持つ場合: 00000000 ssssssss ssssssss tttttttt の形式。
  - s*: セカンダリ照合値 (16ビット)
  - t*: ターシャリ照合値 (8ビット)
  - プライマリ重みは0になります。
結合インデックス (Contraction Index):
- 0x80000000 から 0xBFFFFFFF の範囲。
- 10bbbbbb bbbbbbbb iiiiiiii iiinnnnn の形式。
  - n*: 結合トライの最初のノードのサイズ (5ビット)
  - i*: 結合トライの最初のノードのインデックス (11ビット)
  - b*: 結合照合要素テーブルへのオフセット (14ビット)
  - contractID フラグ (0x80000000) がセットされます。
展開インデックス (Expansion Index):
- 0xC0000000 から 0xDFFFFFFF の範囲。
- 110bbbbb bbbbbbbb bbbbbbbb bbbbbbbb の形式。
  - b*: 展開シーケンステーブルへのインデックス (29ビット)
  - expandID フラグ (0xC0000000) がセットされます。
分解 (Decomposition):
- 0xE0000000 から始まる範囲。
- 11100000 00000000 wwwwwwww vvvvvvvv の形式。
  - v*: 最初のルーンの代替ターシャリ重み (8ビット)
  - w*: 2番目のルーンの代替ターシャリ重み (8ビット)
  - decompID フラグ (0xE0000000) がセットされます。
  - これはNFKD分解を使用してルーンを展開し、ターシャリ重みを変更する場合に使用されます。

主要な関数

makeCE(weights []int) (uint32, error): プライマリ、セカンダリ、ターシャリの重みから通常の照合要素 (uint32) を生成します。重みの範囲チェックも行います。
makeContractIndex(h ctHandle, offset int) (uint32, error): 結合トライのハンドルとオフセットから結合インデックスの照合要素を生成します。
makeExpandIndex(index int) (uint32, error): 展開シーケンステーブルのインデックスから展開インデックスの照合要素を生成します。
makeDecompose(t1, t2 int) (uint32, error): 2つのターシャリ重みから分解の照合要素を生成します。
implicitPrimary(r rune) int: Unicode Collation Algorithm (TR10) の「Implicit Weights」とは異なるアプローチで、明示的なエントリがないルーンに対する暗黙的なプライマリ重みを返します。CJK統合漢字や互換漢字、その他の文字に対して異なるオフセットを適用し、相対的な順序を維持します。
splitCE(ce colElem) weights: 通常の照合要素 (colElem) をプライマリ、セカンダリ、ターシャリの各重みに分解します。
splitContractIndex(ce colElem) (index, n, offset int): 結合インデックスの照合要素を、トライのインデックス、サイズ、オフセットに分解します。
splitExpandIndex(ce colElem) (index int): 展開インデックスの照合要素を展開シーケンステーブルのインデックスに分解します。
splitDecompose(ce colElem) (t1, t2 uint8): 分解の照合要素を2つのターシャリ重みに分解します。

これらの関数は、照合要素の生成と解析を担い、Go言語でのUCA実装の基盤となります。

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

このコミットでは、以下の4つのファイルが新規追加されています。

src/pkg/exp/locale/collate/build/colelem.go: 照合要素を構築するための関数 (makeCE, makeContractIndex, makeExpandIndex, makeDecompose, implicitPrimary) が含まれています。これらは主にデータ生成ツールによって使用されることを想定しています。
src/pkg/exp/locale/collate/build/colelem_test.go: build/colelem.go で定義された照合要素構築関数の単体テストが含まれています。
src/pkg/exp/locale/collate/colelem.go: 照合要素の型定義 (colElem) と、照合要素を解析するための関数 (ctype, splitCE, splitContractIndex, splitExpandIndex, splitDecompose, implicitPrimary) が含まれています。これらはランタイムで使用されることを想定しています。
src/pkg/exp/locale/collate/colelem_test.go: collate/colelem.go で定義された照合要素解析関数の単体テストが含まれています。

これらのファイルは、Go言語の実験的なロケールパッケージ exp/locale/collate の一部として、照合要素の表現と操作に関する機能を提供します。

コアとなるコードの解説

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

このファイルは、照合要素を生成するためのユーティリティ関数を提供します。

// A collation element is represented as an uint32.
// In the typical case, a rune maps to a single collation element. If a rune
// can be the start of a contraction or expands into multiple collation elements,
// then the collation element that is associated with a rune will have a special
// form to represent such m to n mappings.  Such special collation elements
// have a value >= 0x80000000.

// For normal collation elements, we assume that a collation element either has
// a primary or non-default secondary value, not both.
// Collation elements with a primary value are of the form
// 010ppppp pppppppp pppppppp tttttttt, where
//   - p* is primary collation value
//   - t* is the tertiary collation value
// Collation elements with a secondary value are of the form
// 00000000 ssssssss ssssssss tttttttt, where
//   - s* is the secondary collation value
//   - t* is the tertiary collation value
const (
	maxPrimaryBits   = 21
	maxSecondaryBits = 16
	maxTertiaryBits  = 8

	isPrimary = 0x40000000
)

func makeCE(weights []int) (uint32, error) {
	// ... (重みから通常の照合要素を生成するロジック)
}

// For contractions, collation elements are of the form
// 10bbbbbb bbbbbbbb iiiiiiii iiinnnnn, where
//   - n* is the size of the first node in the contraction trie.
//   - i* is the index of the first node in the contraction trie.
//   - b* is the offset into the contraction collation element table.
const (
	contractID            = 0x80000000
	maxNBits              = 5
	maxTrieIndexBits      = 11
	maxContractOffsetBits = 14
)

func makeContractIndex(h ctHandle, offset int) (uint32, error) {
	// ... (結合インデックスの照合要素を生成するロジック)
}

// For expansions, collation elements are of the form
// 110bbbbb bbbbbbbb bbbbbbbb bbbbbbbb,
// where b* is the index into the expansion sequence table.
const (
	expandID           = 0xC0000000
	maxExpandIndexBits = 29
)

func makeExpandIndex(index int) (uint32, error) {
	// ... (展開インデックスの照合要素を生成するロジック)
}

// Some runes can be expanded using NFKD decomposition. Instead of storing the full
// sequence of collation elements, we decompose the rune and lookup the collation
// elements for each rune in the decomposition and modify the tertiary weights.
// The collation element, in this case, is of the form
// 11100000 00000000 wwwwwwww vvvvvvvv, where
//   - v* is the replacement tertiary weight for the first rune,
//   - w* is the replacement tertiary weight for the second rune,
const (
	decompID = 0xE0000000
)

func makeDecompose(t1, t2 int) (uint32, error) {
	// ... (分解の照合要素を生成するロジック)
}

func implicitPrimary(r rune) int {
	// ... (暗黙的なプライマリ重みを計算するロジック)
}

このファイルでは、uint32 のビットフィールドを使って、プライマリ、セカンダリ、ターシャリの重みを格納する方法や、結合、展開、分解といった特殊な照合要素を識別するためのフラグ (isPrimary, contractID, expandID, decompID) が定義されています。makeCE、makeContractIndex、makeExpandIndex、makeDecompose は、それぞれのタイプの照合要素を生成するファクトリ関数として機能します。implicitPrimary は、UCAのルールに従って、明示的な照合要素が定義されていない文字に対するプライマリ重みを計算します。

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

このファイルは、ランタイムで照合要素を扱うための型と関数を提供します。

package collate

import (
	"unicode"
)

// weights holds the decoded weights per collation level.
type weights struct {
	primary   uint32
	secondary uint16
	tertiary  uint8
	quaternary uint32 // TODO: compute quaternary on the fly or compress this value into 8 bits
}

const (
	defaultSecondary = 0x20
	defaultTertiary  = 0x2
	maxTertiary      = 0x1F
)

// colElem is a representation of a collation element.
type colElem uint32

const (
	maxCE       colElem = 0x7FFFFFFF
	minContract         = 0x80000000
	maxContract         = 0xBFFFFFFF
	minExpand           = 0xC0000000
	maxExpand           = 0xDFFFFFFF
	minDecomp           = 0xE0000000
)

type ceType int

const (
	ceNormal           ceType = iota // ceNormal includes implicits (ce == 0)
	ceContractionIndex               // rune can be a start of a contraction
	ceExpansionIndex                 // rune expands into a sequence of collation elements
	ceDecompose                      // rune expands using NFKC decomposition
)

func (ce colElem) ctype() ceType {
	// ... (照合要素のタイプを識別するロジック)
}

func splitCE(ce colElem) weights {
	// ... (通常の照合要素を重みに分解するロジック)
}

func splitContractIndex(ce colElem) (index, n, offset int) {
	// ... (結合インデックスを分解するロジック)
}

func splitExpandIndex(ce colElem) (index int) {
	// ... (展開インデックスを分解するロジック)
}

func splitDecompose(ce colElem) (t1, t2 uint8) {
	// ... (分解の照合要素をターシャリ重みに分解するロジック)
}

func implicitPrimary(r rune) int {
	// ... (build/colelem.go と同じロジック)
}

このファイルでは、colElem 型が uint32 のエイリアスとして定義され、照合要素の表現として使用されます。weights 構造体は、分解されたプライマリ、セカンダリ、ターシャリ重みを保持します。ctype() メソッドは、colElem の値に基づいてそのタイプ（通常、結合、展開、分解）を識別します。splitCE、splitContractIndex、splitExpandIndex、splitDecompose は、それぞれのタイプの照合要素から元の情報を抽出するための関数です。implicitPrimary は build パッケージのものと同じロジックで、ランタイムでも暗黙的なプライマリ重みを計算できるように提供されています。

これらのファイルは、Go言語でUnicode Collation Algorithmを実装するための低レベルなプリミティブを提供し、文字列の国際化対応におけるソートと比較の正確性を保証します。

comemo