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

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

このコミットは、Go言語の標準ライブラリ regexp パッケージに (*Regexp).Longest メソッドを追加するものです。この新機能により、正規表現のマッチングセマンティクスを「左端最長一致 (leftmost-longest)」に設定できるようになり、特定の正規表現パターンにおいて、より直感的で期待されるマッチ結果を得られるようになります。これは、Goの regexp パッケージが採用しているRE2エンジンのデフォルトの「左端優先 (leftmost-first)」マッチング動作と、Perl互換正規表現 (PCRE) などで一般的な「左端最長一致」との間の差異を埋めるための重要な改善です。

コミット

commit f41ffc2bf4a5a29bdff0b11a787e2536859ea61d
Author: Andrew Gerrand <adg@golang.org>
Date:   Mon Feb 4 15:28:55 2013 +1100

    regexp: add (*Regexp).Longest
    
    Fixes #3696.
    
    R=rsc
    CC=golang-dev
    https://golang.org/cl/7133051

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

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

元コミット内容

regexp: add (*Regexp).Longest

このコミットは、Go言語の正規表現パッケージに (*Regexp).Longest メソッドを追加します。これにより、正規表現のマッチングセマンティクスを「左端最長一致」に設定できるようになります。この変更は、Issue #3696 を解決することを目的としています。

変更の背景

Go言語の regexp パッケージは、Googleが開発したRE2正規表現エンジンに基づいています。RE2は、線形時間でのマッチングを保証し、バックトラッキングによる性能劣化を防ぐという優れた特性を持っています。しかし、その設計思想から、Perl互換正規表現 (PCRE) など、他の多くの言語で広く使われている正規表現エンジンとは異なるマッチングセマンティクスを持っています。

具体的には、RE2はデフォルトで「左端優先 (leftmost-first)」のマッチングを行います。これは、複数のマッチ候補がある場合、最も左側で開始するマッチを選択し、その中で最も早く見つかったマッチ（最短のマッチ）を優先するという動作です。これに対し、PCREなどは「左端最長一致 (leftmost-longest)」のマッチングをデフォルトとすることが多く、これは最も左側で開始するマッチを選択し、その中で最も長いマッチを優先するという動作です。

このセマンティクスの違いは、特にオプションのグループや繰り返しを含む正規表現において、ユーザーの期待と異なる結果を生むことがありました。例えば、a(|b) のような正規表現を文字列 ab に適用する場合、デフォルトの「左端優先」では a がマッチしますが、「左端最長一致」では ab がマッチすることが期待されます。Issue #3696 は、このようなユーザーの混乱や、特定のユースケースでの不便さを解消するために提起されたものと考えられます。

このコミットは、(*Regexp).Longest メソッドを導入することで、ユーザーが明示的に「左端最長一致」のセマンティクスを選択できるようにし、より柔軟な正規表現処理を可能にすることを目的としています。

前提知識の解説

正規表現 (Regular Expression)

正規表現は、文字列のパターンを記述するための強力なツールです。特定の文字列の検索、置換、抽出などに広く利用されます。

正規表現エンジンのマッチングセマンティクス

正規表現エンジンが文字列とパターンを比較する際、複数のマッチ候補が存在する場合があります。このとき、どの候補を「最終的なマッチ」として選択するかを決定するルールが「マッチングセマンティクス」です。

  1. 左端優先 (Leftmost-First):

    • 最も左側で開始するマッチを優先します。
    • 同じ開始位置で複数のマッチ候補がある場合、正規表現の定義順（左から右）で最初に成功したマッチを優先します。これは、最短のマッチになる傾向があります。
    • Goの regexp パッケージ（RE2エンジン）のデフォルト動作です。

  2. 左端最長一致 (Leftmost-Longest):

    • 最も左側で開始するマッチを優先します。
    • 同じ開始位置で複数のマッチ候補がある場合、その中で最も長い文字列にマッチする候補を優先します。
    • Perl、Python、JavaScriptなどの多くの言語で採用されているPCREエンジンのデフォルト動作です。

Go言語の regexp パッケージとRE2

Go言語の標準ライブラリ regexp は、Googleが開発したRE2正規表現エンジンをベースにしています。RE2は、以下のような特徴を持ちます。

  • 線形時間保証: 入力文字列の長さに比例する時間でマッチングが完了することを保証します。これにより、悪意のある正規表現（ReDoS攻撃など）によるサービス拒否攻撃を防ぐことができます。
  • バックトラッキングなし: PCREなどで見られるバックトラッキング（試行錯誤的にマッチを探索するプロセス）を行いません。これが線形時間保証の理由です。
  • 機能の制限: 線形時間保証とバックトラッキングなしを実現するため、PCREが持つ一部の高度な機能（例：後方参照、先読み・後読みアサーション、再帰パターンなど）はサポートしていません。

このコミットで追加される Longest メソッドは、RE2エンジンの内部的なマッチングアルゴリズムに影響を与え、左端最長一致のセマンティクスをエミュレートするためのものです。

技術的詳細

(*Regexp).Longest メソッドは、Regexp 構造体の内部に longest というブール型のフラグを設定します。このフラグは、正規表現のマッチング処理を行う際に参照され、マッチングアルゴリズムの挙動を変更します。

具体的には、regexp パッケージの内部では、正規表現パターンを有限オートマトン（NFA: Non-deterministic Finite Automaton）に変換し、そのオートマトンを使って文字列を走査します。デフォルトのRE2の動作では、NFAが複数の状態に同時に存在できる特性を利用し、最も早く受理状態に到達したパスを優先します。

Longest() メソッドが呼び出され re.longest が true に設定されると、マッチングアルゴリズムは、単に最初にマッチを見つけるだけでなく、同じ開始位置から可能な限り長いマッチを探すように動作を変更します。これは、NFAの探索戦略を調整することで実現されます。例えば、NFAが複数のパスを同時に探索している場合、longest フラグが設定されていれば、より多くの文字を消費するパス（より長いマッチを生成する可能性のあるパス）を優先的に探索したり、すべての可能なマッチを列挙した上で最長のものを選び出すようなロジックが内部的に適用されると考えられます。

この変更は、正規表現のコンパイル時ではなく、Longest() メソッドが呼び出された時点で Regexp オブジェクトの振る舞いを変更するため、既存の Regexp オブジェクトに対して動的にマッチングセマンティクスを切り替えることが可能です。

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

このコミットでは、主に以下の2つのファイルが変更されています。

  1. src/pkg/regexp/exec_test.go: Longest メソッドの動作を検証するための新しいテストケース TestLongest が追加されています。
  2. src/pkg/regexp/regexp.go: Regexp 構造体に Longest() メソッドが追加され、内部の longest フラグを設定するロジックが実装されています。
diff --git a/src/pkg/regexp/exec_test.go b/src/pkg/regexp/exec_test.go
index e5d52b40df..d3eddf2a74 100644
--- a/src/pkg/regexp/exec_test.go
+++ b/src/pkg/regexp/exec_test.go
@@ -706,3 +706,17 @@ func BenchmarkMatchHard_1K(b *testing.B)    { benchmark(b, hard, 1<<10) }
 func BenchmarkMatchHard_32K(b *testing.B)   { benchmark(b, hard, 32<<10) }
 func BenchmarkMatchHard_1M(b *testing.B)    { benchmark(b, hard, 1<<20) }
 func BenchmarkMatchHard_32M(b *testing.B)   { benchmark(b, hard, 32<<20) }\n+\n+func TestLongest(t *testing.T) {\n+\tre, err := Compile(`a(|b)`)\n+\tif err != nil {\n+\t\tt.Fatal(err)\n+\t}\n+\tif g, w := re.FindString(\"ab\"), \"a\"; g != w {\n+\t\tt.Errorf(\"first match was %q, want %q\", g, w)\n+\t}\n+\tre.Longest()\n+\tif g, w := re.FindString(\"ab\"), \"ab\"; g != w {\n+\t\tt.Errorf(\"longest match was %q, want %q\", g, w)\n+\t}\n+}\ndiff --git a/src/pkg/regexp/regexp.go b/src/pkg/regexp/regexp.go
index c516a1566f..c0ecc01c35 100644
--- a/src/pkg/regexp/regexp.go
+++ b/src/pkg/regexp/regexp.go
@@ -130,6 +130,14 @@ func CompilePOSIX(expr string) (*Regexp, error) {
 	return compile(expr, syntax.POSIX, true)
 }\n \n+// Longest sets the match semantics of the regexp to leftmost-longest.\n+// That is, when matching against text, the regexp returns a match that\n+// begins as early as possible in the input (leftmost), and among those\n+// it chooses a match that is as long as possible.\n+func (re *Regexp) Longest() {\n+\tre.longest = true\n+}\n+\n func compile(expr string, mode syntax.Flags, longest bool) (*Regexp, error) {
 	re, err := syntax.Parse(expr, mode)
 	if err != nil {

コアとなるコードの解説

src/pkg/regexp/regexp.go の変更

// Longest sets the match semantics of the regexp to leftmost-longest.
// That is, when matching against text, the regexp returns a match that
// begins as early as possible in the input (leftmost), and among those
// it chooses a match that is as long as possible.
func (re *Regexp) Longest() {
	re.longest = true
}
  • func (re *Regexp) Longest(): Regexp 型のポインタレシーバを持つメソッドとして Longest が追加されました。
  • re.longest = true: このメソッドの唯一の役割は、Regexp 構造体の内部フィールドである longest を true に設定することです。この longest フィールドは、正規表現のマッチング処理を行う内部ロジックで参照され、マッチングセマンティクスを「左端最長一致」に変更するために使用されます。

src/pkg/regexp/exec_test.go の変更

func TestLongest(t *testing.T) {
	re, err := Compile(`a(|b)`)
	if err != nil {
		t.Fatal(err)
	}
	if g, w := re.FindString("ab"), "a"; g != w {
		t.Errorf("first match was %q, want %q", g, w)
	}
	re.Longest()
	if g, w := re.FindString("ab"), "ab"; g != w {
		t.Errorf("longest match was %q, want %q", g, w)
	}
}
  • re, err := Compile(a(|b)): まず、正規表現 a(|b) をコンパイルします。この正規表現は、a の後に空文字列または b が続くパターンを意味します。
  • if g, w := re.FindString("ab"), "a"; g != w: Longest() メソッドを呼び出す前に、文字列 ab に対して FindString を実行します。デフォルトの「左端優先」セマンティクスでは、a がマッチすることが期待されます。テストでは、実際に a がマッチするかを確認しています。
  • re.Longest(): ここで、Longest() メソッドを呼び出し、正規表現オブジェクトのマッチングセマンティクスを「左端最長一致」に切り替えます。
  • if g, w := re.FindString("ab"), "ab"; g != w: Longest() を呼び出した後、再度文字列 ab に対して FindString を実行します。「左端最長一致」セマンティクスでは、ab がマッチすることが期待されます。テストでは、実際に ab がマッチするかを確認し、Longest() メソッドが正しく機能していることを検証しています。

このテストケースは、Longest() メソッドが正規表現のマッチング結果に与える影響を明確に示しており、ユーザーが期待する「左端最長一致」の動作が実現されていることを保証します。

関連リンク

参考にした情報源リンク