Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Go言語の正規表現パッケージ（regexp）に、RE2ライブラリから着想を得た「ワンパス最適化」を導入するものです。この最適化により、特定の正規表現パターンにおいて約2.3倍の高速化が実現されます。

コミット

commit 76236ef13684fd63555ae4be90ca31e94eda670f
Author: David Covert <davidhcovert@gmail.com>
Date:   Fri Mar 7 15:30:02 2014 -0500

    regexp: add one-pass optimization from RE2
    
    This produces about a 2.3x speedup for patterns
    that can be handled this way.
    
    LGTM=rsc
    R=rsc
    CC=golang-codereviews
    https://golang.org/cl/13345046

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

https://github.com/golang/go/commit/76236ef13684fd63555ae4be90ca31e94eda670f

元コミット内容

このコミットは、Go言語の正規表現エンジンにRE2由来のワンパス最適化を実装し、特定のパターンマッチングを高速化することを目的としています。具体的には、正規表現の内部表現であるプログラム（syntax.Prog）を解析し、ワンパスで処理可能なパターンであれば、専用の高速なマッチングパスを使用します。これにより、該当するパターンでは約2.3倍の速度向上が見込まれます。

変更の背景

Go言語のregexpパッケージは、GoogleのRE2正規表現エンジンに基づいています。RE2は、バックトラッキングを伴わない決定性有限オートマトン（DFA）ベースのマッチングアルゴリズムを採用しており、最悪計算量が入力文字列の長さに線形であるという特徴があります。しかし、一部の正規表現パターン、特に先読みや後読み、または複雑なグループ化を伴わない単純なパターンでは、DFAベースのアプローチでもオーバーヘッドが生じることがあります。

このコミットの背景には、このような単純なパターンに対して、さらに効率的なマッチング手法を導入し、パフォーマンスを向上させたいという意図があります。RE2には、特定の正規表現が「ワンパス」で処理可能かどうかを判定し、その場合はよりシンプルな状態遷移でマッチングを行う最適化が存在します。この最適化をGoのregexpパッケージにも取り入れることで、より広範な正規表現のユースケースで高速化を実現しようとしています。

前提知識の解説

正規表現エンジンとオートマトン

正規表現のマッチングは、通常、有限オートマトン（Finite Automaton, FA）の概念に基づいて行われます。

  • 非決定性有限オートマトン (NFA: Nondeterministic Finite Automaton):

    • 同じ入力記号に対して複数の状態に遷移する可能性があるオートマトンです。
    • バックトラッキングを伴う実装が多く、最悪計算量が正規表現の長さに指数関数的に比例する場合があります（例: Perl, Pythonのreモジュール）。
    • しかし、NFAはキャプチャグループや後方参照といった高度な正規表現機能の実装が容易です。

  • 決定性有限オートマトン (DFA: Deterministic Finite Automaton):

    • 同じ入力記号に対して常に一意の状態に遷移するオートマトンです。
    • バックトラッキングが不要で、入力文字列の長さに線形時間でマッチングが完了します。最悪計算量が保証されるため、予測可能なパフォーマンスを提供します。
    • RE2やGoのregexpパッケージはDFAベースです。DFAはNFAよりも構築が複雑で、キャプチャグループの扱いが難しいという側面もあります。

RE2とGoのregexpパッケージ

Goのregexpパッケージは、RE2ライブラリの設計思想とアルゴリズムをベースにしています。RE2は、DFAベースのアプローチにより、高速かつ安全な正規表現マッチングを提供します。特に、正規表現の複雑さに依存しない線形時間のマッチングは、サービス拒否攻撃（ReDoS）のリスクを低減する上で重要です。

ワンパス最適化 (One-Pass Optimization)

ワンパス最適化とは、正規表現のマッチングにおいて、入力文字列を一度だけ走査する（ワンパス）ことで結果を得る手法です。これは、正規表現が持つ特定の構造（例えば、選択肢が入力文字によって明確に区別できる場合など）を利用して、バックトラッキングや複雑な状態管理を不要にするものです。

通常のDFAベースのマッチングでも線形時間ですが、ワンパス最適化はさらにオーバーヘッドを削減し、より直接的な状態遷移でマッチングを進めることができます。これは、特にシンプルなリテラル文字列のプレフィックスを持つパターンや、選択肢が明確に分離されているパターンで効果を発揮します。

例えば、^abc(d|e)*$のような正規表現では、^abcというプレフィックスが確定しており、その後の(d|e)*もdかeのどちらか一文字を消費するだけで次の状態が決定できます。このようなパターンはワンパスで処理可能です。

技術的詳細

このコミットでは、regexp/syntaxパッケージに正規表現の内部表現であるProg（プログラム）を解析し、ワンパス実行が可能かどうかを判定するロジックが追加されています。

  1. syntax.Progの拡張:

    • syntax.Inst構造体にNext []uint32フィールドが追加されました。これは、ワンパス実行時に次の命令ポインタ（PC）を格納するために使用されます。
    • syntax.InstOpにInstLastが追加され、命令の種類が増えたことを示しています。
    • syntax.ProgにCompileOnePass()メソッドが追加されました。これがワンパス最適化の主要な入り口となります。

  2. CompileOnePass()メソッド:

    • このメソッドは、現在のProgがワンパス実行可能かどうかを判定し、可能であればワンパス実行用の新しいProgを返します。不可能であればsyntax.NotOnePass（nil）を返します。
    • ワンパス実行の条件として、正規表現がアンカー（^）で開始されていること、およびInstMatchに到達する全てのパスがEmptyEndText（行末）で終わる必要があることなどがチェックされます。
    • 内部では、onePassCopy()で元のProgのコピーを作成し、makeOnePass()でワンパス実行可能な形に変換を試みます。
    • makeOnePass()は再帰的にプログラムを走査し、InstAlt（選択肢）命令において、次の入力文字によってどの分岐に進むべきかが一意に決定できるかを検証します。
    • mergeRuneSets関数は、InstAlt命令の各分岐がマッチするルーンセットを結合し、重複がないか（曖昧さがないか）をチェックします。重複がある場合はワンパス実行不可能と判断されます。
    • InstRune命令の処理が強化され、ケースフォールド（大文字小文字を区別しないマッチング）も考慮したルーンセットの生成が行われます。

  3. regexp.Regexpとregexp.machineの変更:

    • regexp.Regexp構造体にonepass *syntax.Progフィールドが追加され、ワンパス実行可能なプログラムが格納されます。
    • regexp.machine構造体にもop *syntax.Progフィールドが追加され、実行時にワンパスプログラムが利用されます。
    • Regexp.doExecuteメソッド内で、m.op != syntax.NotOnePassの場合にm.onepass(i, pos)が呼び出され、ワンパス実行が試みられます。これにより、ワンパス実行可能なパターンでは、従来のDFAベースのマッチングよりも高速なonepass関数が使用されます。

  4. onepass関数:

    • regexp/exec.goに追加されたonepass関数は、ワンパス実行可能な正規表現プログラムを効率的に実行します。
    • この関数は、入力文字列を先頭から順に走査し、各命令（InstRune, InstRune1, InstRuneAny, InstRuneAnyNotNL, InstEmptyWidth, InstCaptureなど）を直接処理します。
    • InstAltやInstAltMatch命令では、OnePassNextメソッドを使用して、現在の入力ルーンに基づいて次に進むべき命令ポインタを決定します。これにより、バックトラッキングなしで一意のパスを辿ることができます。
    • シンプルなリテラルプレフィックスを持つパターンでは、i.hasPrefix(m.re)による高速なプレフィックスチェックが行われ、マッチングの開始位置を効率的にスキップできます。

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

  • src/pkg/regexp/exec.go:

    • machine構造体にop *syntax.Progフィールドを追加。
    • progMachine関数がonepassプログラムを受け取るように変更。
    • onepass関数が新規追加され、ワンパス実行ロジックを実装。
    • doExecute関数内で、onepassプログラムが存在する場合にonepass関数を呼び出すように変更。

  • src/pkg/regexp/regexp.go:

    • Regexp構造体にonepass *syntax.ProgとprefixEnd uint32フィールドを追加。
    • compile関数内でprog.CompileOnePass()を呼び出し、onepassフィールドに結果を格納。
    • get関数内でprogMachineにonepassプログラムを渡すように変更。

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

    • Inst構造体にNext []uint32フィールドを追加。
    • InstOpにInstLastを追加し、InstOpのString()メソッドを更新。
    • skipNop関数がpcも返すように変更。
    • OnePassPrefix()関数を新規追加。
    • OnePassNext()関数を新規追加。
    • MatchRunePos()関数を新規追加し、MatchRuneから分離。
    • queue構造体と関連メソッド（newQueue, empty, next, clear, reset, contains, insert, insertNew）を新規追加。
    • mergeRuneSets()関数を新規追加。
    • cleanupOnePass()関数を新規追加。
    • onePassCopy()関数を新規追加。
    • runeSlice型と関連メソッド（Len, Less, Swap, Sort）を新規追加。
    • makeOnePass()関数を新規追加。
    • walk()関数を新規追加。
    • find()関数を新規追加。
    • CompileOnePass()関数を新規追加。

  • src/pkg/regexp/all_test.go:

    • ワンパス最適化のベンチマークテスト（BenchmarkOnePassShortA, BenchmarkNotOnePassShortAなど）を新規追加。

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

    • mergeRuneSets関数のテスト（TestMergeRuneSet）を新規追加。
    • CompileOnePass関数のテスト（TestCompileOnePass）を新規追加。

コアとなるコードの解説

regexp/syntax/prog.goにおけるワンパスプログラムの構築

このコミットの核心は、正規表現の抽象構文木（AST）から生成されるsyntax.Progを、ワンパス実行可能な形式に変換するロジックです。

Prog.CompileOnePass()関数がその入り口です。この関数は、まず正規表現がアンカー（^）で始まるなど、ワンパス実行の基本的な条件を満たしているかを確認します。次に、onePassCopy()でプログラムのコピーを作成し、makeOnePass()を呼び出して実際の変換処理を行います。

makeOnePass()は、プログラム内の各命令を再帰的に走査し、特にInstAlt（選択肢）命令に注目します。ワンパス実行の最大の課題は、a|bのような選択肢がある場合に、入力文字を見てどちらの分岐に進むべきかを即座に決定できるかどうかです。

makeOnePass()は、check関数とmergeRuneSets関数を組み合わせてこの問題を解決します。

  • check関数は、各命令から到達可能なパスを探索し、InstMatch（マッチ成功）に到達するパスがあるかどうか、およびInstAlt命令で曖昧さがないかを確認します。
  • mergeRuneSets関数は、InstAltの各分岐がマッチするルーン（文字）の範囲を結合します。もし、異なる分岐が同じルーン範囲にマッチする場合（例: a|a）、それは曖昧であり、ワンパス実行は不可能と判断されます。この関数は、結合されたルーンセットと、それぞれのルーンセットがどの分岐に対応するかを示すNext配列を返します。

成功した場合、InstAlt命令は、入力ルーンに基づいて次に進むべき命令ポインタを直接指し示すNext配列を持つようになります。これにより、実行時に複雑な状態管理やバックトラッキングなしに、一意のパスを辿ることが可能になります。

regexp/exec.goにおけるワンパス実行

regexp.machine構造体は、正規表現のマッチングを実行するエンジンです。このコミットでは、machineにop *syntax.Progフィールドが追加され、ワンパス実行可能なプログラムが格納されます。

Regexp.doExecuteメソッドは、マッチングの開始時に、machineにワンパスプログラムが設定されているかどうかを確認します。もし設定されていれば、新しく追加されたonepass関数が呼び出されます。

onepass関数は、非常にシンプルなループで入力文字列を走査します。各ステップで現在の命令を評価し、入力ルーンに基づいて次の命令に直接遷移します。

  • InstRuneやInstRune1のような文字マッチング命令では、現在の入力ルーンが命令のルーンセットにマッチするかをチェックし、マッチすれば次の命令に進みます。
  • InstAltやInstAltMatch命令では、inst.OnePassNext(r)を呼び出し、現在の入力ルーンrに基づいて、Next配列から次に進むべき命令ポインタを直接取得します。これにより、複数の分岐の中から正しいパスを迷うことなく選択できます。
  • InstCapture命令では、キャプチャグループの開始/終了位置を記録します。

この直接的な実行パスにより、従来のDFAベースのマッチングで必要だったキュー管理やスレッド（状態）の管理が不要になり、大幅な高速化が実現されます。

関連リンク

参考にした情報源リンク