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

このコミットは、Go言語の標準ライブラリであるregexpパッケージのドキュメントに、その正規表現エンジンの重要な特性である「入力サイズに対して線形時間で動作する」という保証を追加するものです。具体的には、src/pkg/regexp/regexp.goファイルに説明文が追記されています。

コミット

commit c790b029e6a6478819c0ad611fb649d6b99f62ce
Author: Rob Pike <r@golang.org>
Date:   Tue Mar 25 11:17:30 2014 +1100

    regexp: document that it is linear in the input size.
    Fixes #7488.
    
    LGTM=rsc
    R=rsc
    CC=golang-codereviews
    https://golang.org/cl/78050043

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

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

元コミット内容

regexp: document that it is linear in the input size. Fixes #7488.

このコミットは、Go言語のregexpパッケージが入力サイズに対して線形時間で動作することをドキュメントに明記するものです。これは、内部的な問題追跡システムにおけるIssue #7488を修正するものです。

正規表現エンジンには、大きく分けて2つの実装アプローチがあります。一つはバックトラッキング（後方参照）ベースのエンジンで、もう一つはオートマトン（NFA/DFA）ベースのエンジンです。Perl、Python、Ruby、Javaなどの多くの言語で採用されているバックトラッキングエンジンは、特定の正規表現パターンと入力文字列の組み合わせにおいて、最悪の場合に指数関数的な時間計算量（いわゆる「破滅的バックトラッキング」）に陥る可能性があります。これは、正規表現の処理が非常に遅くなり、サービス拒否攻撃（ReDoS）の原因となることもあります。

Go言語のregexpパッケージは、設計当初からこの問題に対処しており、バックトラッキングを使用しないオートマトンベースのアプローチ（具体的には、NFAをDFAに変換するアプローチ）を採用することで、入力文字列のサイズに対して常に線形時間でマッチングが完了することを保証しています。

このコミットは、この重要な特性がGoのregexpパッケージのドキュメントに明記されていなかったため、ユーザーがこの保証を知らずに利用する可能性があったことを背景としています。ドキュメントに明記することで、開発者がGoの正規表現エンジンのパフォーマンス特性を理解し、安心して利用できるようにすることが目的です。Fixes #7488という記述から、このドキュメントの不足が何らかの形で問題として認識されていたことが伺えます。

前提知識の解説

正規表現 (Regular Expression)

正規表現は、文字列のパターンを記述するための強力なツールです。テキスト検索、置換、検証など、様々な場面で利用されます。

正規表現エンジンの種類

正規表現エンジンは、その内部的な動作原理によって大きく二つに分類されます。

バックトラッキング（Backtracking）エンジン:
- 動作原理: 正規表現のパターンを左から右に、入力文字列を左から右にマッチングを試みます。もし途中でマッチングに失敗した場合、以前に選択肢があった場所に戻り（バックトラック）、別の選択肢を試します。
- 特徴: (a|b)*c のような選択肢や量指定子（*, +, ?）が複雑に絡み合うパターンでは、マッチングに失敗するたびに多くのバックトラックが発生し、最悪の場合、入力文字列の長さに応じて指数関数的な時間計算量となることがあります。これを「破滅的バックトラッキング (Catastrophic Backtracking)」と呼びます。
- 例: Perl, Python, Ruby, Java, PHP など多くの言語の標準正規表現ライブラリがこのタイプです。
- 利点: 後方参照（backreferences）や先読み・後読み（lookarounds）といった高度な機能の実装が比較的容易です。
オートマトン（Automaton）ベースエンジン:
- 動作原理: 正規表現を有限オートマトン（Finite Automaton）に変換してマッチングを行います。有限オートマトンには、非決定性有限オートマトン（NFA: Nondeterministic Finite Automaton）と決定性有限オートマトン（DFA: Deterministic Finite Automaton）があります。
  - NFA: 複数の状態に同時に存在できる概念的なマシンです。マッチングは、入力文字列を1文字ずつ読み込みながら、可能なすべてのパスを並行して探索するような形で進行します。
  - DFA: 各入力文字に対して、次に遷移する状態が常に一意に決定されるマシンです。
- 特徴: オートマトンベースのエンジンは、入力文字列の長さに比例する線形時間でマッチングが完了することを保証します。これは、バックトラッキングのように同じ入力文字を何度も再評価することがないためです。
- 例: Go言語のregexpパッケージ、RE2（Googleが開発した正規表現ライブラリ）、awk、grep など。
- 利点: 常に高速で安定したパフォーマンスを提供し、破滅的バックトラッキングの問題を回避できます。
- 欠点: 後方参照などの一部の高度な正規表現機能は、オートマトンでは効率的に表現できないため、サポートされない場合があります。

線形時間 (Linear Time Complexity)

アルゴリズムの計算量が入力サイズ N に対して O(N) で表現される場合、そのアルゴリズムは線形時間で動作すると言われます。これは、入力サイズが2倍になれば、処理時間も約2倍になることを意味します。正規表現のマッチングにおいて線形時間であることは、入力文字列がどんなに長くても、処理時間が予測可能で、急激に増加しないことを保証するため、非常に重要な特性です。

技術的詳細

Go言語のregexpパッケージは、Russ Cox氏が設計したRE2ライブラリのアルゴリズムに基づいています。RE2は、正規表現をNFAに変換し、そのNFAをシミュレートすることでマッチングを行います。このNFAシミュレーションは、入力文字列の各文字に対してNFAの状態セットを効率的に更新することで、線形時間でのマッチングを実現します。

具体的には、Goのregexpパッケージは、正規表現をコンパイルする際に、その正規表現に対応するNFAを構築します。そして、マッチング時には、入力文字列を1文字ずつ読み込みながら、現在アクティブなNFAの状態のセットを管理します。これにより、バックトラッキングを必要とせず、常に前方へ進むだけでマッチングを完了させることができます。このアプローチにより、どのような正規表現パターンと入力文字列の組み合わせであっても、最悪の場合の計算量が入力文字列の長さに比例する線形時間に抑えられます。

この特性は、特にWebアプリケーションやネットワークサービスなど、ユーザーからの任意の入力に対して正規表現マッチングを行う場合に非常に重要です。線形時間保証がない正規表現エンジンを使用すると、悪意のあるユーザーが巧妙に作成した入力文字列によって、正規表現処理が無限に近く遅延し、サービスが停止する可能性があります（ReDoS攻撃）。Goのregexpパッケージは、このセキュリティリスクを根本的に排除しています。

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

変更はsrc/pkg/regexp/regexp.goファイルのコメント部分に集中しています。

--- a/src/pkg/regexp/regexp.go
+++ b/src/pkg/regexp/regexp.go
@@ -11,6 +11,14 @@
 // For an overview of the syntax, run
 //   godoc regexp/syntax
 //
+// The regexp implementation provided by this package is
+// guaranteed to run in time linear in the size of the input.
+// (This is a property not guaranteed by most open source
+// implementations of regular expressions.) For more information
+// about this property, see
+//	http://swtch.com/~rsc/regexp/regexp1.html
+// or any book about automata theory.
+//
 // All characters are UTF-8-encoded code points.
 //
 // There are 16 methods of Regexp that match a regular expression and identify

具体的には、// godoc regexp/syntaxの行の下に8行のコメントが追加されています。

コアとなるコードの解説

追加されたコメントは、Goのregexpパッケージの最も重要なパフォーマンス特性を明確に説明しています。

// The regexp implementation provided by this package is
// guaranteed to run in time linear in the size of the input.
// (This is a property not guaranteed by most open source
// implementations of regular expressions.) For more information
// about this property, see
//	http://swtch.com/~rsc/regexp/regexp1.html
// or any book about automata theory.

The regexp implementation provided by this package is guaranteed to run in time linear in the size of the input.
- この行は、Goのregexpパッケージが入力文字列のサイズに対して線形時間で動作することを明確に保証しています。これは、パフォーマンスの予測可能性と安定性を示す重要な声明です。
(This is a property not guaranteed by most open source implementations of regular expressions.)
- この括弧内の文は、Goのregexpパッケージが他の多くのオープンソースの正規表現実装（特にバックトラッキングベースのもの）とは異なり、この線形時間保証を提供していることを強調しています。これにより、Goの正規表現エンジンの優位性が際立ちます。
For more information about this property, see http://swtch.com/~rsc/regexp/regexp1.html or any book about automata theory.
- この行は、この線形時間特性に関する詳細な情報源として、Russ Cox氏による有名な記事「Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...)」へのリンクを提供しています。また、オートマトン理論に関する書籍も参照するように促しており、この特性が理論的な裏付けに基づいていることを示唆しています。

これらのコメントの追加により、Goのregexpパッケージを利用する開発者は、そのパフォーマンス特性を正確に理解し、安心してアプリケーションに組み込むことができるようになりました。特に、セキュリティが懸念される正規表現関連の脆弱性（ReDoS）に対して、Goの正規表現エンジンが堅牢であるというメッセージを明確に伝えています。

参考にした情報源リンク

Russ Cox氏による記事「Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...)」: http://swtch.com/~rsc/regexp/regexp1.html

comemo