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

このコミットは、Go言語のリリースノート go1.3.txt を更新し、regexp パッケージに加えられた重要な変更、具体的には「RE2からのワンパス最適化の追加」について言及するものです。このコミット自体はコードの機能的な変更ではなく、Go 1.3リリースにおける正規表現エンジンの改善を公式ドキュメントに反映させるためのものです。

コミット

commit 15068b6df752bd91ae1bbe7ac6d50f853f027d98
Author: Brad Fitzpatrick <bradfitz@golang.org>
Date:   Wed Mar 12 14:23:40 2014 -0700

    doc: update go1.3.txt for regexp change
    
    LGTM=rsc
    R=rsc
    CC=golang-codereviews
    https://golang.org/cl/72640043

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

https://github.com/golang/go/commit/15068b6df752bd91ae1bbe7ac6d50f853f027d98

元コミット内容

このコミットは、doc/go1.3.txt ファイルに以下の1行を追加しています。

--- a/doc/go1.3.txt
+++ b/doc/go1.3.txt
@@ -18,6 +18,7 @@ net/http: use TCP keep-alives for ListenAndServe and ListenAndServeTLS (CL 48300
 net: add Dialer.KeepAlive option (CL 68380043)
 net: enable fast socket creation using SOCK_CLOEXEC and Accept4 on FreeBSD 10 (69100043)
 os/exec: fix Command with relative paths (CL 59580044)
+regexp: add one-pass optimization from RE2 (CL 13345046)
 runtime/debug: add SetPanicOnFault (CL 66590044)
 runtime: output how long goroutines are blocked (CL 50420043)
 sync: add Pool (CL 41860043, 46010043)

追加された行は regexp: add one-pass optimization from RE2 (CL 13345046) であり、これはGo 1.3リリースで regexp パッケージに導入された新しい最適化について言及しています。

変更の背景

Go言語の regexp パッケージは、Googleが開発した高性能な正規表現エンジンであるRE2ライブラリに基づいています。RE2は、線形時間でのマッチングを保証し、バックトラッキングによる指数関数的な遅延（ReDoS攻撃の原因となる）を防ぐことで知られています。

このコミットの背景にあるのは、Go 1.3リリースに向けて regexp パッケージのパフォーマンスをさらに向上させるという目標です。特に、特定の正規表現パターンにおいて、より高速なマッチングを実現するための「ワンパス最適化」がRE2から取り込まれました。この最適化は、正規表現のマッチングプロセスを効率化し、特に単純なパターンでの処理速度を向上させることを目的としています。

このコミット自体は、その技術的な変更（CL 13345046）がGo 1.3の公式リリースノートに適切に記載されるようにするためのものです。これにより、ユーザーはGo 1.3で導入された regexp パッケージの改善点を把握できるようになります。

前提知識の解説

正規表現 (Regular Expression)

正規表現は、文字列のパターンを記述するための強力なツールです。テキスト検索、置換、検証など、様々な場面で利用されます。正規表現エンジンは、このパターンに基づいて文字列を解析し、マッチングを行います。

RE2は、Googleが開発した正規表現ライブラリです。従来の正規表現エンジンが抱えるバックトラッキングによる性能問題（最悪の場合、入力文字列の長さに応じて指数関数的な時間が必要となる）を解決するために設計されました。RE2は、決定性有限オートマトン（DFA）に基づいており、入力文字列の長さに線形な時間でマッチングを完了することを保証します。これにより、ReDoS（Regular Expression Denial of Service）攻撃のようなセキュリティ脆弱性を防ぐことができます。Go言語の標準ライブラリの regexp パッケージは、このRE2の設計思想とアルゴリズムをベースにしています。

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

正規表現のマッチングは、一般的に複雑なアルゴリズムを伴います。ワンパス最適化とは、特定の単純な正規表現パターンに対して、入力文字列を一度だけ走査（ワンパス）するだけでマッチングを完了できるようにする最適化手法です。これにより、より複雑なアルゴリズムを適用する場合に比べて、処理速度が大幅に向上します。例えば、固定文字列の検索や、単純な文字クラスのマッチングなどがワンパスで処理できる典型的なケースです。

技術的詳細

このコミットが参照している regexp: add one-pass optimization from RE2 (CL 13345046) の技術的詳細は、Goの regexp パッケージがRE2のアルゴリズムをどのように採用し、さらに特定のケースでパフォーマンスを向上させたかに関わります。

RE2は、正規表現をDFA（決定性有限オートマトン）に変換してマッチングを行います。DFAは、入力文字列の各文字を一度だけ読み込むことで、常に線形時間でマッチングを完了できます。しかし、DFAの構築には時間がかかり、また、非常に大きなDFAが生成される可能性もあります。

ワンパス最適化は、DFAの特性を活かしつつ、さらに効率を高めるためのものです。具体的には、正規表現が特定の構造（例えば、固定文字列の連結や、単純な文字クラスの繰り返しなど）を持つ場合、DFAを完全に構築する代わりに、より単純な状態機械や直接的な文字列検索アルゴリズムにフォールバックすることで、オーバーヘッドを削減し、マッチングを高速化します。

この最適化は、特に以下のような場合に効果を発揮します。

固定文字列の検索: foo のような単純な文字列リテラルを検索する場合、正規表現エンジンは内部的にKMP法やBoyer-Moore法のような高速な文字列検索アルゴリズムに切り替えることができます。
単純な文字クラス: [a-z]+ のような単純な文字クラスの繰り返しも、ワンパスで効率的に処理できます。
先頭固定パターン: ^prefix のように、マッチングが文字列の先頭から始まることが保証されているパターンでは、不要な探索を省くことができます。

この最適化は、RE2の設計思想に沿ったものであり、Goの regexp パッケージがRE2の堅牢性と線形時間保証を維持しつつ、一般的なユースケースでの実用的なパフォーマンスを向上させるための重要なステップでした。

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

このコミット自体は、doc/go1.3.txt というドキュメントファイルへの変更のみです。

--- a/doc/go1.3.txt
+++ b/doc/go1.3.txt
@@ -18,6 +18,7 @@ net/http: use TCP keep-alives for ListenAndServe and ListenAndServeTLS (CL 48300
 net: add Dialer.KeepAlive option (CL 68380043)
 net: enable fast socket creation using SOCK_CLOEXEC and Accept4 on FreeBSD 10 (69100043)
 os/exec: fix Command with relative paths (CL 59580044)
+regexp: add one-pass optimization from RE2 (CL 13345046)
 runtime/debug: add SetPanicOnFault (CL 66590044)
 runtime: output how long goroutines are blocked (CL 50420043)
 sync: add Pool (CL 41860043, 46010043)

実際の regexp パッケージの変更は、参照されている CL 13345046 で行われました。このコミットは、その変更をリリースノートに反映させるためのものです。

コアとなるコードの解説

このコミット自体には、Goのランタイムやライブラリの機能的なコード変更は含まれていません。変更されたのは、Go 1.3のリリースノートを記述する doc/go1.3.txt ファイルです。

doc/go1.3.txt は、Goの各リリースで導入された新機能、改善点、バグ修正などをまとめたドキュメントです。このファイルに regexp: add one-pass optimization from RE2 (CL 13345046) という行が追加されたことで、Go 1.3のユーザーは、regexp パッケージのパフォーマンスが向上したことを知ることができます。

このドキュメントの更新は、Goプロジェクトにおけるリリースプロセスの重要な一部であり、ユーザーが新しいバージョンで何が変更されたかを理解するのに役立ちます。

参考にした情報源リンク

Go 1.3 Release Notes: 上記の関連リンクと同じく、Go 1.3の公式リリースノートは、このコミットの背景と目的を理解する上で最も直接的な情報源です。
- https://go.dev/doc/go1.3
Go Change List 13345046: regexp パッケージのワンパス最適化に関する実際のコード変更と議論が含まれています。
- https://go.dev/cl/13345046
RE2 Documentation: RE2の設計原則とアルゴリズムに関する情報は、ワンパス最適化の技術的詳細を深く理解するために役立ちます。
- https://github.com/google/re2/wiki/WhyRE2
- https://github.com/google/re2/wiki/RegularExpressions
Go Blog - Regular Expressions in Go: Goの regexp パッケージの設計思想とRE2との関係について解説している公式ブログ記事。
- https://go.dev/blog/regexp
Wikipedia - RE2: RE2に関する一般的な情報と特徴。
- https://en.wikipedia.org/wiki/RE2

Keyboard shortcuts

comemo