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

このコミットは、Go言語の実験的なUnicode正規化パッケージ exp/norm に、セグメント境界でイテレーションを行うための新しい Iter 型を追加するものです。この Iter 型は、主に collate のような他の低レベルライブラリで使用されることを想定しています。特に、照合器で使用されるNFD (Normalization Form Canonical Decomposition) への正規化のパフォーマンス最適化に重点が置かれており、文字列が正規化されているかどうかのチェックのオーバーヘッドは、単に文字列を分解するのと比較して無視できるレベルであるとされています。ほとんどの文字列がFCD (Fast C-style Decomposition) 形式であると仮定することで、このイテレータは最小限のオーバーヘッドで文字列を分解し、正規化することを可能にします。

コミット

commit ecd24f381e189df32f558ffab04b829cd4713649
Author: Marcel van Lohuizen <mpvl@golang.org>
Date:   Tue Feb 21 13:13:21 2012 +0100

    exp/norm: Added Iter type for iterating on segment boundaries.  This type is mainly to be used
    by other low-level libraries, like collate.  Extra care has been given to optimize the performance
    of normalizing to NFD, as this is what will be used by the collator.  The overhead of checking
    whether a string is normalized vs simply decomposing a string is neglible.  Assuming that most
    strings are in the FCD form, this iterator can be used to decompose strings and normalize with
    minimal overhead.
    
    R=r
    CC=golang-dev
    https://golang.org/cl/5676057

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

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

元コミット内容

exp/norm: セグメント境界でイテレーションを行うための Iter 型を追加しました。この型は主に collate のような他の低レベルライブラリで使用されることを目的としています。照合器で使用されるNFDへの正規化のパフォーマンスを最適化するために特に注意が払われています。文字列が正規化されているかどうかをチェックするオーバーヘッドは、単に文字列を分解するのと比較して無視できるレベルです。ほとんどの文字列がFCD形式であると仮定すると、このイテレータは最小限のオーバーヘッドで文字列を分解し、正規化するために使用できます。

変更の背景

この変更の主な背景は、Unicode文字列の正規化処理、特にNFD (Normalization Form Canonical Decomposition) への正規化の効率を向上させることにあります。

• パフォーマンスの最適化: 照合（文字列の比較やソート）のような操作では、文字列を正規化された形式（特にNFD）に変換することが不可欠です。このコミットは、この変換プロセスをより効率的に行うための新しいイテレータ (Iter 型) を導入することで、パフォーマンスの向上を目指しています。
• 低レベルライブラリのサポート: collate のような低レベルライブラリが、正規化された文字列を効率的に処理できるように、セグメント境界でのイテレーション機能を提供します。
• FCD (Fast C-style Decomposition) 形式の活用: 多くの文字列がFCD形式であるという仮定に基づき、正規化チェックのオーバーヘッドを最小限に抑えつつ、分解と正規化を効率的に実行できるメカニズムを提供します。これにより、不必要な再分解を避け、処理速度を向上させます。

前提知識の解説

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

Unicode正規化形式 (Normalization Forms)

Unicodeには、同じ文字を異なるバイトシーケンスで表現できる場合があります（例: 「é」は単一のコードポイントU+00E9で表現することも、基本文字「e」と結合文字「´」U+0301の組み合わせで表現することもできます）。これにより、文字列の比較やソートが複雑になるため、Unicodeではいくつかの正規化形式を定義しています。

• NFD (Normalization Form Canonical Decomposition): 正準分解形式。すべての結合文字を分解し、正準順序で並べ替えます。例えば、「é」は「e」と「´」に分解されます。
• NFC (Normalization Form Canonical Composition): 正準合成形式。NFDに分解された後、可能な限り正準な合成を行います。例えば、「e」と「´」は「é」に合成されます。
• NFKD (Normalization Form Compatibility Decomposition): 互換分解形式。NFDと同様に分解を行いますが、互換性分解も行います。例えば、全角文字やリガチャ（合字）なども分解されます。
• NFKC (Normalization Form Compatibility Composition): 互換合成形式。NFKDに分解された後、可能な限り互換性合成を行います。

Canonical Combining Class (CCC)

結合文字（アクセント記号など）は、基本文字と組み合わされて表示されます。これらの結合文字には、表示順序を決定するための「Canonical Combining Class (CCC)」というプロパティがあります。CCCの値が小さい結合文字ほど、基本文字に近い位置に表示されます。正規化では、結合文字はCCCの昇順に並べ替えられます。

Hangul Decomposition (ハングル分解)

ハングル文字は、子音、母音、終子音の組み合わせで構成される複合文字です。Unicodeでは、これらの複合ハングル文字を個々のJamo（子音と母音の構成要素）に分解することができます。この分解は、正規化プロセスの一部として行われます。

Fast C-style Decomposition (FCD)

FCDは、文字列が正規化されているかどうかを効率的にチェックするための最適化された形式です。FCD形式の文字列は、結合文字が正準順序で並べられていることを保証します。これにより、完全な正規化プロセスを実行する前に、文字列がすでに正規化されているかどうかを迅速に判断できます。

技術的詳細

このコミットの核となるのは、exp/norm パッケージに導入された新しい Iter 型です。この型は、Unicode正規化のプロセスを効率的に、特にセグメント単位で処理するために設計されています。

Iter 型は、入力文字列またはバイトスライスを特定の正規化形式（NFC、NFD、NFKC、NFKD）に正規化しながらイテレーションを行います。主な機能は以下の通りです。

• セグメント境界でのイテレーション: Unicode正規化では、特定の文字の並び（セグメント）が正規化の単位となります。Iter は、このセグメント境界を認識し、一度に一つの正規化されたセグメントを処理します。これにより、大きな文字列全体を一度に正規化するのではなく、部分的に処理することが可能になり、メモリ効率とパフォーマンスが向上します。
• reorderBuffer の活用: Iter は内部的に reorderBuffer を使用して、結合文字の並べ替えや分解・合成を行います。reorderBuffer は、Unicodeの正規化アルゴリズムにおいて、結合文字の正準順序を維持するために重要な役割を果たします。
• NFD最適化: コミットメッセージにあるように、NFDへの正規化に特に最適化が施されています。これは、照合器がNFD形式を頻繁に利用するためです。nextDecomposed 関数は、NFDおよびNFKD形式の処理を担当し、分解された文字を効率的に出力します。
• NFC/NFKC処理: nextComposed 関数は、NFCおよびNFKC形式の処理を担当し、分解された文字を合成して出力します。
• FCD形式の効率的な処理: ほとんどの文字列がFCD形式であるという仮定に基づき、Iter は正規化チェックのオーバーヘッドを最小限に抑えるように設計されています。これにより、すでに正規化されている部分については、不必要な処理をスキップできます。
• Hangul分解の改善: ハングル文字の分解ロジックが改善され、より効率的にJamoに分解できるようになりました。

Iter の導入により、exp/norm パッケージは、より柔軟で高性能なUnicode正規化機能を提供できるようになります。特に、ストリーム処理や、部分的な正規化が必要なシナリオにおいて、その真価を発揮します。

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

このコミットでは、主に以下のファイルが変更または新規追加されています。

• src/pkg/exp/norm/composition.go:
  • reorderBuffer に flushCopy メソッドが追加されました。これは、正規化されたセグメントをバッファにコピーし、reorderBuffer をリセットする役割を持ちます。
  • insert メソッドがリファクタリングされ、ハングル文字の分解と一般的な分解処理が insertDecomposed および insertSingle という新しいヘルパー関数に分割されました。
  • insertDecomposed は、分解されたUTF-8エンコードされたルーンのシーケンスを reorderBuffer に挿入します。
  • insertSingle は、単一のルーンを reorderBuffer に挿入します。
  • isHangul および isHangulString 関数に、入力バイトスライス/文字列の長さチェックが追加され、hangulUTF8Size 定数が導入されました。
  • decomposeHangul 関数が追加され、ハングルルーンをJamoに分解してバッファに書き込む機能を提供します。
• src/pkg/exp/norm/composition_test.go:
  • TestFlush が flushCopy メソッドのテストを含むように更新されました。
• src/pkg/exp/norm/input.go:
  • input インターフェースの skipASCII メソッドのシグネチャが変更され、max 引数が追加されました。これにより、ASCII文字のスキップ範囲を制限できるようになりました。
• src/pkg/exp/norm/iter.go: 新規追加ファイル
  • Iter 構造体が定義されました。これは、正規化された文字列またはバイトスライスをイテレーションするための主要な型です。
  • SetInput および SetInputString メソッドが追加され、Iter を初期化して入力ソースと正規化形式を設定します。
  • Pos、Done、Next メソッドが追加され、イテレーションの制御と次の正規化されたセグメントの取得を可能にします。
  • initNext、setStart、min といったヘルパー関数が追加されました。
  • nextDecomposed 関数が追加され、NFDおよびNFKD形式の正規化イテレーションロジックを実装します。
  • nextComposed 関数が追加され、NFCおよびNFKC形式の正規化イテレーションロジックを実装します。
• src/pkg/exp/norm/iter_test.go: 新規追加ファイル
  • Iter 型のテストケースが多数追加されました。これには、異なるバッファサイズでの正規化テスト、分解形式と合成形式のイテレーションテスト、セグメンテーションテストなどが含まれます。
• src/pkg/exp/norm/normalize.go:
  • quickSpan 関数と decomposeToLastBoundary 関数で、skipASCII の呼び出しが新しいシグネチャに合わせて更新されました。
  • decomposeToLastBoundary で、ハングル分解のロジックが調整されました。
• src/pkg/exp/norm/normalize_test.go:
  • iterBench 関数が追加され、Iter 型のベンチマークを測定できるようになりました。
  • appendBenchmarks 関数が追加され、Append と Iter の両方のベンチマークをまとめて実行できるようにしました。
  • 新しいベンチマーク BenchmarkOverflow が追加され、非常に長い結合文字シーケンスの処理性能を評価します。

コアとなるコードの解説

src/pkg/exp/norm/iter.go (新規追加)

このファイルは、新しい Iter 型の定義と、その主要なメソッドを含んでいます。

// An Iter iterates over a string or byte slice, while normalizing it
// to a given Form.
type Iter struct {
	rb   reorderBuffer
	info runeInfo // first character saved from previous iteration
	next iterFunc // implementation of next depends on form

	p        int // current position in input source
	outStart int // start of current segment in output buffer
	inStart  int // start of current segment in input source
	maxp     int // position in output buffer after which not to start a new segment
	maxseg   int // for tracking an excess of combining characters

	tccc uint8
	done bool
}

// SetInput initializes i to iterate over src after normalizing it to Form f.
func (i *Iter) SetInput(f Form, src []byte) {
	i.rb.init(f, src)
	if i.rb.f.composing {
		i.next = nextComposed
	} else {
		i.next = nextDecomposed
	}
	i.p = 0
	if i.done = len(src) == 0; !i.done {
		i.info = i.rb.f.info(i.rb.src, i.p)
	}
}

// Next writes f(i.input[i.Pos():n]...) to buffer buf, where n is the
// largest boundary of i.input such that the result fits in buf.  
// It returns the number of bytes written to buf.
// len(buf) should be at least MaxSegmentSize. 
// Done must be false before calling Next.
func (i *Iter) Next(buf []byte) int {
	return i.next(i, buf)
}

• Iter 構造体は、正規化処理の状態を保持します。reorderBuffer (rb) は、文字の並べ替えや分解/合成に使用されます。next フィールドは、選択された正規化形式（合成形式か分解形式か）に応じて、nextComposed または nextDecomposed のいずれかの関数ポインタを保持します。
• SetInput メソッドは、イテレータを初期化し、入力ソースと正規化形式を設定します。入力形式に基づいて、適切な next 関数が設定されます。
• Next メソッドは、イテレータの主要なインターフェースです。呼び出されると、現在の正規化形式に応じた next 関数（nextComposed または nextDecomposed）が実行され、正規化された次のセグメントが buf に書き込まれ、書き込まれたバイト数が返されます。

nextDecomposed 関数 (NFD/NFKDの処理)

// nextDecomposed is the implementation of Next for forms NFD and NFKD.
func nextDecomposed(i *Iter, out []byte) int {
	var outp int
	i.initNext(len(out), i.p)
doFast:
	inCopyStart, outCopyStart := i.p, outp // invariant xCopyStart <= i.xStart
	for {
		if sz := int(i.info.size); sz <= 1 {
			// ASCII or illegal byte.  Either way, advance by 1.
			i.p++
			outp++
			max := min(i.rb.nsrc, len(out)-outp+i.p)
			if np := i.rb.src.skipASCII(i.p, max); np > i.p {
				outp += np - i.p
				i.p = np
				if i.p >= i.rb.nsrc {
					break
				}
				// ASCII may combine with consecutive runes.
				if i.setStart(outp-1, i.p-1) {
					i.p--
					outp--
					i.info.size = 1
					break
				}
			}
		} else if d := i.info.decomposition(); d != nil {
			// ... (decomposition logic) ...
		} else if r := i.rb.src.hangul(i.p); r != 0 {
			// ... (Hangul decomposition logic) ...
		} else {
			// ... (copy single rune) ...
		}
		// ... (boundary checks and loop continuation) ...
	}
	// ... (final copy and done check) ...
doNorm:
	// ... (normalization logic for combining characters) ...
}

• この関数は、NFDおよびNFKD形式の正規化ロジックを実装しています。
• doFast ラベルは、高速パスを示しており、結合文字の並べ替えが必要ない場合に直接バイトをコピーします。
• ASCII文字や不正なバイト、分解を持つ文字、ハングル文字など、様々なケースを効率的に処理します。
• doNorm ラベルは、結合文字の並べ替えが必要な場合に呼び出される正規化パスです。reorderBuffer を使用して、文字を正準順序に並べ替えます。

nextComposed 関数 (NFC/NFKCの処理)

// nextComposed is the implementation of Next for forms NFC and NFKC.
func nextComposed(i *Iter, out []byte) int {
	var outp int
	i.initNext(len(out), i.p)
doFast:
	inCopyStart, outCopyStart := i.p, outp // invariant xCopyStart <= i.xStart
	var prevCC uint8
	for {
		if !i.info.isYesC() { // Check if character can be composed
			goto doNorm
		}
		// ... (composition logic) ...
	}
	// ... (final copy and done check) ...
doNorm:
	// ... (normalization and composition logic) ...
}

• この関数は、NFCおよびNFKC形式の正規化ロジックを実装しています。
• isYesC() は、文字が合成可能かどうかをチェックします。合成可能な文字でない場合や、結合文字の順序が不正な場合は、doNorm パスにジャンプして合成処理を行います。
• doNorm パスでは、reorderBuffer を使用して分解と合成を行い、正規化されたセグメントを生成します。

src/pkg/exp/norm/composition.go の変更

// flushCopy copies the normalized segment to buf and resets rb.
// It returns the number of bytes written to buf.
func (rb *reorderBuffer) flushCopy(buf []byte) int {
	p := 0
	for i := 0; i < rb.nrune; i++ {
		runep := rb.rune[i]
		p += copy(buf[p:], rb.byte[runep.pos:runep.pos+runep.size])
	}
	rb.reset()
	return p
}

// insertDecomposed inserts an entry in to the reorderBuffer for each rune
// in dcomp.  dcomp must be a sequence of decomposed UTF-8-encoded runes.
func (rb *reorderBuffer) insertDecomposed(dcomp []byte) bool {
	// ... (implementation) ...
}

// insertSingle inserts an entry in the reorderBuffer for the rune at
// position i. info is the runeInfo for the rune at position i.
func (rb *reorderBuffer) insertSingle(src input, i int, info runeInfo) bool {
	// ... (implementation) ...
}

// decomposeHangul writes the decomposed Hangul to buf and returns the number
// of bytes written.  len(buf) should be at least 9.
func decomposeHangul(buf []byte, r rune) int {
	// ... (implementation) ...
}

• flushCopy は、reorderBuffer に格納された正規化されたバイトシーケンスを効率的に出力バッファにコピーするための新しいヘルパー関数です。
• insertDecomposed と insertSingle は、reorderBuffer への文字の挿入ロジックをより細かく制御するために導入されました。これにより、分解されたシーケンスや単一のルーンの挿入が明確に分離されます。
• decomposeHangul は、ハングル文字をそのJamo構成要素に分解し、UTF-8エンコードされたバイトとしてバッファに書き込むための新しい関数です。これは、ハングル文字の正規化処理において重要な役割を果たします。

これらの変更は、Iter 型がUnicode正規化を効率的に、かつセグメント単位で処理できるようにするための基盤を提供します。特に、パフォーマンスが重視される照合などのシナリオにおいて、その効果が期待されます。

関連リンク

• https://golang.org/cl/5676057 (Go Code Review)

参考にした情報源リンク

• Unicode Normalization Forms - Wikipedia
• Unicode Standard Annex #15: Unicode Normalization Forms
• Canonical Combining Class - Unicode Glossary
• Hangul Syllable Decomposition - Unicode Standard (Chapter 3, Section 3.12)
• Fast C-style Decomposition (FCD) - ICU User Guide
• Go言語のUnicode正規化パッケージ exp/norm のソースコード (現在の golang.org/x/text/unicode/norm パッケージは、この exp/norm の後継にあたります。)