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

このコミットは、Go言語の標準ライブラリであるregexpパッケージにおける正規表現エンジンの「ワンパス実行（one-pass execution）」に関する大幅な内部変更を導入するものです。主な目的は、特定の正規表現パターンに対してバックトラックを必要としない高速なマッチングを可能にするワンパス最適化のコードを、外部APIから隠蔽し、regexp/syntaxパッケージからregexpパッケージ内部へと移動させることです。これにより、APIの安定性を保ちつつ、実装の詳細に依存しない柔軟な改善を可能にしています。また、syntax.Inst構造体から不要なスライスフィールドを削除することで、ワンパスではない正規表現のメモリフットプリントの肥大化を防ぐ効果もあります。

コミット

commit 6c10e64a906039678f5dffda8b453005ffcdb92e
Author: Russ Cox <rsc@golang.org>
Date:   Wed May 28 14:08:44 2014 -0400

    regexp: hide one-pass code from exported API
    
    Update #8112
    
    Hide one-pass regexp API.
    
    This means moving the code from regexp/syntax to regexp,
    but it avoids being locked into the specific API chosen for
    the implementation.
    
    It also removes a slice field from the syntax.Inst, which
    should avoid bloating the memory footprint of a non-one-pass
    regexp unnecessarily.
    
    LGTM=r
    R=golang-codereviews, r
    CC=golang-codereviews, iant
    https://golang.org/cl/98610046

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

https://github.com/golang/go/commit/6c10e64a906039678f5dffda8b453005ffcdb92e

元コミット内容

regexp: hide one-pass code from exported API

Update #8112

Hide one-pass regexp API.

This means moving the code from regexp/syntax to regexp,
but it avoids being locked into the specific API chosen for
the implementation.

It also removes a slice field from the syntax.Inst, which
should avoid bloating the memory footprint of a non-one-pass
regexp unnecessarily.

変更の背景

このコミットの背景には、Go言語の正規表現エンジンにおけるパフォーマンス最適化とAPI設計の原則があります。

1. パフォーマンス最適化（ワンパス実行）: 正規表現のマッチングは、一般的にNFA（非決定性有限オートマトン）ベースの実装ではバックトラックを伴い、最悪の場合指数関数的な時間計算量になることがあります。しかし、一部の正規表現（特に先読みや後読み、複雑な量指定子などを含まないもの）は、入力文字列を一度スキャンするだけでマッチングが完了する「ワンパス」で実行可能です。このような正規表現を特定し、専用の高速パスで処理することで、マッチング性能を大幅に向上させることができます。コミットメッセージにあるUpdate #8112は、このワンパス実行の導入に関するIssue golang/go#8112に対応するものです。

2. APIの隠蔽と安定性: 当初、ワンパス実行に関連するAPI（例: CompileOnePass、OnePassPrefixなど）はregexp/syntaxパッケージに公開されていました。しかし、正規表現エンジンの内部実装は複雑であり、将来的な最適化やアルゴリズムの変更によってAPIが変更される可能性があります。このような内部的な詳細が外部に公開されていると、後方互換性を維持しながら改善を進めることが困難になります。このコミットは、ワンパス実行のロジックをregexpパッケージの内部に移動させ、外部から直接アクセスできないようにすることで、APIの安定性を確保し、将来的な変更の自由度を高めることを目的としています。

3. メモリフットプリントの削減: regexp/syntax.Inst構造体は、正規表現の構文ツリーを表現するための命令を定義しています。ワンパス実行のために追加されたNext []uint32フィールドは、ワンパスではない正規表現プログラムにとっても不要なメモリを消費する可能性がありました。このフィールドをsyntax.Instから削除し、ワンパス専用の構造体（onePassInst）に移動させることで、一般的な正規表現のメモリ使用量を削減し、効率を向上させています。

これらの変更は、Goの正規表現エンジンをより高速かつ効率的にし、同時に堅牢なAPI設計を維持するための重要なステップでした。

前提知識の解説

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

1. 正規表現エンジン:

   • NFA (Non-deterministic Finite Automaton): 非決定性有限オートマトン。Goのregexpパッケージが採用している正規表現エンジンの基本的なアプローチです。NFAは、ある状態から複数の遷移が可能であったり、入力なしで遷移したりすることができます。マッチング時には、可能なすべてのパスを同時に探索（またはバックトラック）することで、マッチを試みます。柔軟性が高い反面、複雑なパターンではバックトラックにより性能が劣化する可能性があります。
   • DFA (Deterministic Finite Automaton): 決定性有限オートマトン。DFAは、ある状態と入力に対して常に一意の次の状態が決定されます。バックトラックが不要なため、マッチングは常に線形時間で完了します。しかし、NFAよりも構築が複雑で、キャプチャグループなどの高度な機能の実装が難しい場合があります。
   • バックトラック: NFAベースの正規表現エンジンで、あるパスが失敗した場合に、以前の決定点に戻って別のパスを試すプロセス。これにより、正しいマッチを見つけることができますが、多くの選択肢がある場合や、パターンが入力とマッチしない場合に、非常に多くのバックトラックが発生し、性能問題（"redos"攻撃など）を引き起こすことがあります。

2. ワンパス実行 (One-Pass Execution):

   • 正規表現エンジンが、入力文字列を先頭から末尾まで一度だけスキャンする（バックトラックなしで）ことでマッチングを完了できる最適化手法です。これは、特定の種類の正規表現（例えば、a*bのような単純なパターンや、選択肢が明確に分離されているパターン）に対してのみ適用可能です。
   • ワンパス実行が可能な正規表現は、本質的にDFAのように動作すると考えることができます。この最適化により、マッチングの速度が大幅に向上し、最悪ケースの性能保証が得られます。

3. Go言語のregexpとregexp/syntaxパッケージ:

   • regexp/syntaxパッケージ: 正規表現の構文解析（パース）と、その結果としての抽象構文木（AST）の表現、そしてASTから正規表現プログラム（命令列）へのコンパイルを担当します。このパッケージは、正規表現の「意味」を表現する低レベルなプリミティブを提供します。以前は、ワンパス実行のロジックの一部もここに存在していました。
   • regexpパッケージ: ユーザーが直接利用する高レベルな正規表現APIを提供します。regexp/syntaxパッケージでコンパイルされたプログラムを受け取り、実際に文字列に対してマッチングを実行するエンジン（NFAエンジンや、このコミットで導入されたワンパスエンジン）を実装しています。

4. syntax.Inst構造体: regexp/syntaxパッケージで定義される、正規表現プログラムの個々の命令を表す構造体です。各命令は、操作の種類（Op）、次の命令へのポインタ（Out）、追加の引数（Arg）、マッチするルーン（Rune）などを含みます。

このコミットは、ワンパス実行というパフォーマンス最適化を、regexp/syntaxからregexpパッケージに移動させ、syntax.Instからワンパス関連のフィールドを削除することで、Goの正規表現エンジンの内部構造をよりクリーンで効率的なものに再構築しています。

技術的詳細

このコミットの技術的詳細は、主に以下の点に集約されます。

1. ワンパス実行ロジックの分離と移動:

   • 以前はregexp/syntaxパッケージ内に存在していたワンパス実行の検出とプログラム生成ロジック（CompileOnePass、OnePassPrefix、OnePassNextなど）が、新しく作成されたsrc/pkg/regexp/onepass.goファイルに完全に移動されました。
   • これにより、regexp/syntaxパッケージは純粋に正規表現の構文解析と基本的なプログラム表現に特化し、実行時の最適化ロジックはregexpパッケージの内部実装としてカプセル化されました。

2. onePassProgとonePassInst構造体の導入:

   • ワンパス実行のために、regexpパッケージ内にonePassProgとonePassInstという新しい構造体が定義されました。
   • onePassProgは、syntax.Progと同様に命令の配列（Inst）、開始命令のインデックス（Start）、キャプチャグループの数（NumCap）を持ちますが、その命令はonePassInst型です。
   • onePassInstは、syntax.Instを埋め込み（composition）つつ、ワンパス実行に必要な追加のフィールドNext []uint32を持ちます。このNextフィールドは、InstAltやInstAltMatchのような分岐命令において、入力ルーンに基づいて次に進むべき命令のインデックスを格納するために使用されます。これにより、バックトラックなしで決定的に次の状態へ遷移できます。

3. ワンパスプログラムのコンパイルロジック (compileOnePass):

   • regexp/onepass.goに実装されたcompileOnePass関数が、与えられたsyntax.Progがワンパス実行可能かどうかを分析し、可能であればonePassProgを生成します。
   • この関数は、正規表現プログラムの命令を走査し、特にInstAlt（選択肢）命令において、どの分岐に進むべきかを入力ルーンに基づいて決定できるかどうかをチェックします。
   • makeOnePass関数がこの分析と変換の主要な部分を担います。これは再帰的にプログラムを走査し、各命令がワンパスの条件を満たすかを確認します。
   • mergeRuneSets関数は、複数のルーンセット（正規表現の文字クラスなど）をマージし、重複がないか（つまり、曖昧さがないか）をチェックするために使用されます。重複がある場合、その正規表現はワンパス実行不可能と判断されます。

4. syntax.InstからのNextフィールドの削除:

   • src/pkg/regexp/syntax/prog.goからInst構造体のNext []uint32フィールドが削除されました。
   • これにより、ワンパス実行をサポートしない一般的な正規表現プログラムのメモリ使用量が削減されます。Nextフィールドは、ワンパス実行が必要な場合にのみonePassInst内で存在することになります。

5. regexp.Regexp構造体の更新:

   • src/pkg/regexp/regexp.goのRegexp構造体は、onepass *syntax.Progフィールドをonepass *onePassProgに変更しました。
   • 正規表現のコンパイル時（regexp.compile関数内）に、新しいregexp.compileOnePass関数が呼び出され、ワンパスプログラムが生成可能であればそれが利用されます。

これらの変更により、Goの正規表現エンジンは、ワンパス実行可能なパターンに対してはより高速な専用パスを利用し、それ以外のパターンに対しては従来のNFAベースのエンジンを利用するという、ハイブリッドなアプローチを採用するようになりました。これは、性能と機能のバランスを取る上で非常に効果的な戦略です。

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

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

1. api/next.txt:

   • pkg regexp/syntax, method (*Inst) OnePassNext(int32) uint32
   • pkg regexp/syntax, method (*Prog) CompileOnePass() *Prog
   • pkg regexp/syntax, method (*Prog) OnePassPrefix() (string, bool, uint32)
   • pkg regexp/syntax, type Inst struct, Next []uint32
   • pkg regexp/syntax, var NotOnePass *Prog これらのエントリが削除されました。これは、ワンパス関連のAPIがregexp/syntaxパッケージから外部に公開されなくなったことを示します。

2. src/pkg/regexp/exec.go:

   • type machine struct内のop *syntax.Progがop *onePassProgに変更されました。
   • func progMachine(p, op *syntax.Prog) *machineのシグネチャがfunc progMachine(p *syntax.Prog, op *onePassProg) *machineに変更されました。
   • m.op != syntax.NotOnePassがm.op != notOnePassに変更されました。
   • inst.OnePassNext(r)がonePassNext(&inst, r)に変更されました。 これらの変更は、正規表現実行エンジンがワンパスプログラムを扱うための型と関数の呼び出しを調整しています。

3. src/pkg/regexp/onepass.go (新規ファイル):

   • このファイル全体が新規追加されました。
   • type onePassProg struct：ワンパス実行用のプログラム構造体。
   • type onePassInst struct：ワンパス実行用の命令構造体。syntax.Instを埋め込み、Next []uint32フィールドを追加。
   • func onePassPrefix(p *syntax.Prog) (prefix string, complete bool, pc uint32)：ワンパス正規表現の固定プレフィックスを抽出。
   • func onePassNext(i *onePassInst, r rune) uint32：ワンパス命令の次の状態を決定。
   • type queueOnePass struct：ワンパス実行内部で使用されるキューの実装。
   • func mergeRuneSets(leftRunes, rightRunes *[]rune, leftPC, rightPC uint32) ([]rune, []uint32)：ルーンセットのマージと衝突検出。
   • func cleanupOnePass(prog *onePassProg, original *syntax.Prog)：ワンパスプログラムのクリーンアップ。
   • func onePassCopy(prog *syntax.Prog) *onePassProg：ワンパスプログラムのコピーを作成。
   • func makeOnePass(p *onePassProg) *onePassProg：ワンパスプログラムを構築する主要ロジック。
   • func compileOnePass(prog *syntax.Prog) (p *onePassProg)：syntax.ProgからonePassProgへのコンパイルを試みるエントリポイント。

4. src/pkg/regexp/onepass_test.go (新規ファイル):

   • このファイル全体が新規追加されました。
   • TestMergeRuneSet：mergeRuneSets関数のテスト。
   • TestCompileOnePass：compileOnePass関数のテスト。

5. src/pkg/regexp/regexp.go:

   • type Regexp struct内のonepass *syntax.Progがonepass *onePassProgに変更されました。
   • func compile(...)内で、prog.CompileOnePass()の呼び出しがcompileOnePass(prog)に変更されました。
   • regexp.onepass == syntax.NotOnePassがregexp.onepass == notOnePassに変更されました。
   • prog.OnePassPrefix()の呼び出しがonePassPrefix(prog)に変更されました。 これらの変更は、regexpパッケージが新しいワンパス実行ロジックと型を利用するように更新されたことを示します。

6. src/pkg/regexp/syntax/prog.go:

   • type Inst structからNext []uint32フィールドが削除されました。
   • func (p *Prog) OnePassPrefix(...)、func (i *Inst) OnePassNext(...)、type queue struct、func mergeRuneSets(...)、func (prog *Prog) cleanupOnePass(...)、func (prog *Prog) onePassCopy(...)、func (p *Prog) makeOnePass(...)、func (prog *Prog) walk(...)、func (prog *Prog) find(...)、var NotOnePass *Prog、func (prog *Prog) CompileOnePass(...)といった、ワンパス実行に関連するすべての関数、型、変数が削除されました。 このファイルは、ワンパス実行の内部ロジックから完全に切り離され、正規表現の構文表現に特化するようになりました。

7. src/pkg/regexp/syntax/prog_test.go:

   • runeMergeTests、TestMergeRuneSet、onePassTests、TestCompileOnePassといった、regexp/syntaxパッケージから移動されたワンパス関連のテストが削除されました。

これらの変更は、Goの正規表現エンジンにおけるワンパス最適化の責任をregexp/syntaxからregexpパッケージへと明確に分離し、APIの隠蔽と内部実装のクリーンアップを実現しています。

コアとなるコードの解説

このコミットの核心は、ワンパス実行ロジックをregexp/syntaxからregexpパッケージに移動し、そのための新しい構造体と関数を導入した点にあります。特に重要なのは、onepass.goで定義されるonePassProg、onePassInst、そしてcompileOnePass関数です。

src/pkg/regexp/onepass.go

type onePassInst struct

type onePassInst struct {
	syntax.Inst
	Next []uint32
}

この構造体は、ワンパス実行のための正規表現命令を表します。

• syntax.Instを埋め込んでいるため、syntax.Instが持つOp（操作）、Out（次の命令へのポインタ）、Arg（引数）、Rune（マッチするルーン）といったフィールドをそのまま利用できます。
• Next []uint32フィールドが追加されています。これは、特にInstAlt（選択肢）やInstAltMatch（マッチを伴う選択肢）のような分岐命令において、入力ルーンに基づいて次に進むべき命令のインデックスを格納するために使用されます。これにより、バックトラックなしで決定的に次の状態へ遷移することが可能になります。

type onePassProg struct

type onePassProg struct {
	Inst   []onePassInst
	Start  int // index of start instruction
	NumCap int // number of InstCapture insts in re
}

この構造体は、ワンパス実行可能な正規表現プログラム全体を表します。

• Inst []onePassInst：onePassInst型の命令の配列です。
• Start int：プログラムの開始命令のインデックス。
• NumCap int：キャプチャグループの数。

func compileOnePass(prog *syntax.Prog) (p *onePassProg)

func compileOnePass(prog *syntax.Prog) (p *onePassProg) {
	// ... (省略: ワンパス条件のチェック) ...

	// Creates a slightly optimized copy of the original Prog
	// that cleans up some Prog idioms that block valid onepass programs
	p = onePassCopy(prog)

	// checkAmbiguity on InstAlts, build onepass Prog if possible
	p = makeOnePass(p)

	if p != notOnePass {
		cleanupOnePass(p, prog)
	}
	return p
}

この関数は、regexp/syntaxパッケージから受け取った通常の正規表現プログラム（*syntax.Prog）がワンパス実行可能かどうかを判断し、可能であれば*onePassProgに変換して返します。

• ワンパス条件のチェック: 関数冒頭で、正規表現がワンパス実行の基本的な条件（例えば、アンカーされているか、InstMatchへの遷移がEmptyEndTextであるかなど）を満たしているかを確認します。満たさない場合は、すぐにnotOnePass（ワンパス不可を示す特別な値）を返します。
• onePassCopy(prog): 元のsyntax.Progのコピーを作成し、一部の正規表現のイディオム（例えば、空の遷移ループなど）をワンパス実行に適した形に書き換えます。
• makeOnePass(p): この関数がワンパス実行可能かどうかの主要な分析と、onePassProgの構築を行います。
  • makeOnePassは、プログラムの命令を走査し、特にInstAlt（選択肢）命令において、入力ルーンに基づいてどの分岐に進むべきかを決定できるかどうかをチェックします。
  • mergeRuneSets関数を使用して、複数のルーンセット（文字クラスなど）が重複しないか（つまり、曖昧さがないか）を確認します。曖昧さがある場合、その正規表現はワンパス実行不可能と判断され、notOnePassが返されます。
  • 各onePassInstのNextフィールドに、入力ルーンに応じた次の命令のインデックスを設定します。
• cleanupOnePass(p, prog): ワンパスプログラムが正常に構築された場合、不要な作業用メモリを解放し、特定のショートカット命令を復元します。

src/pkg/regexp/regexp.go

type Regexp struct {
	// ...
	onepass        *onePassProg   // onpass program or nil
	// ...
}

func compile(expr string, mode syntax.Flags, longest bool) (*Regexp, error) {
	// ...
	regexp := &Regexp{
		// ...
		onepass:     compileOnePass(prog), // ここで新しいcompileOnePassを呼び出す
		// ...
	}
	if regexp.onepass == notOnePass { // notOnePassと比較
		regexp.prefix, regexp.prefixComplete = prog.Prefix()
	} else {
		regexp.prefix, regexp.prefixComplete, regexp.prefixEnd = onePassPrefix(prog) // 新しいonePassPrefixを呼び出す
	}
	// ...
}

regexp.Regexp構造体のonepassフィールドの型が*syntax.Progから*onePassProgに変更されました。 compile関数内で、正規表現のコンパイル時にregexp/onepass.goで定義されたcompileOnePass関数が呼び出され、ワンパス実行可能なプログラムが生成されます。もしワンパスプログラムが生成されれば、それがregexp.onepassに格納され、マッチング時に利用されます。

src/pkg/regexp/syntax/prog.go

type Inst struct {
	Op   InstOp // operator
	Out  uint32 // all but InstMatch, InstFail
	Arg  uint32 // InstAlt, InstAltMatch, InstCapture, InstEmptyWidth
	Rune []rune
	// Next []uint32 // If input rune matches (削除された行)
}

Inst構造体からNext []uint32フィールドが削除されました。これにより、regexp/syntaxパッケージはワンパス実行の詳細から切り離され、より汎用的な正規表現の構文表現に特化するようになりました。ワンパス実行に必要なNextフィールドは、regexpパッケージ内のonePassInstに移動されました。

これらの変更により、Goの正規表現エンジンは、ワンパス実行可能な正規表現に対しては専用の高速パスを利用し、それ以外の正規表現に対しては従来のNFAエンジンを利用するという、効率的なハイブリッド戦略を実現しています。

関連リンク

• Go Issue #8112: regexp: one-pass execution
• Gerrit Change-Id: https://golang.org/cl/98610046

参考にした情報源リンク

• Go言語の正規表現パッケージのドキュメント: https://pkg.go.dev/regexp
• Go言語の正規表現構文パッケージのドキュメント: https://pkg.go.dev/regexp/syntax
• 正規表現エンジンの種類と性能に関する一般的な情報（NFA vs DFA, バックトラックなど）:
  • Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...) - Russ Coxによる記事。Goの正規表現エンジンの設計思想に大きな影響を与えています。
  • Regular Expression Matching in the Wild - Russ Coxによる続編。
• Go言語のソースコード（src/regexpおよびsrc/regexp/syntaxディレクトリ）
• Go言語のコミット履歴と関連するIssueトラッカー
• UnicodeのSimpleFoldに関する情報（ルーンのケースフォールディングに関連）