付録
付録 1：履歴 1
Boost 1.55.0（2013 年 11 月 11 日）
Boost 1.54.0（2013 年 7 月 1 日）
Boost 1.53.0（2013 年 2 月 4 日）
最近の Boost 版スマートポイントの変更に対応した。チケット #7809 を修正した。
Boost 1.52.0（2012 年 11 月 5 日）
sub_match で Boost.Range が使えるようにした。チケット #7237 を修正した。
Boost 1.50.0（2012 年 6 月 28 日）
たちの悪い lexical_cast ハックを幾分マシなものにした。
C++11 で問題になる MPL の assert を static assert に置き換えた。チケット #6864 を修正した。
Boost 1.49.0（2012 年 2 月 24 日）
gcc で未使用として警告が出ていた変数を削除した。
Boost 1.45.0（2010 年 11 月 19 日）
xpressive::asがワイド文字版のsub_matchオブジェクトを処理できなかったバグを修正（チケット #4496）。
Boost 1.44.0（2010 年 8 月 13 日）
nested_resultsにおける、typedefを使った移植性のないusingディレクティブを置き換えた。非ローカル変数に対するプレースホルダを使ったユーザー定義表明をサポートした。
Boost 1.43.0（2010 年 5 月 6 日）
<boost/xpressive/regex_error.hpp>へのインクルードが欠けていたのを修正。
Boost 1.42.0（2010 年 2 月 2 日）
Boost 1.41.0（2009 年 11 月 17 日）
\Q～\E引用メタを使用した場合に無限ループする場合があるバグを修正（チケット #3586）。MSVC で到達不能コードの警告を出ないようにした。
MSVC で
/Za（「言語拡張を無効にする」）モードにした場合に発生する警告とエラーを解決した。様々なコンパイラの C++0x モードに関するバグを修正した。
Boost 1.40.0（2009 年 8 月 27 日）
Visual C++ 10.0 で動作するようになった（チケット #3124）。
Boost 1.39.0（2009 年 5 月 2 日）
GCC の最適化で純粋仮想関数呼び出しによる実行時エラーが発生する問題（チケット #2655）の回避策を追加。
Boost 1.38.0（2009 年 2 月 8 日）
std::basic_regexとの互換性のために、basic_regexに入れ子のsyntax_option_flagsとvalue_type型定義を追加。Proto v4 への移植。
boost/xpressive/protoにあった Proto v2 は削除した。regex_errorをboost::exceptionから継承するようにした。
バージョン 2.1.0（2008 年 6 月 12 日）
新機能
静的正規表現に
skipプリミティブを追加。入力文字列内の、正規表現マッチ中に無視する部分を指定できる。regex_replaceアルゴリズムの範囲ベースのインターフェイス。regex_replaceが書式化文字列に加えて、書式化オブジェクトと書式化ラムダ式を受け付けるようになった。
バグ修正
前方先読み、後方先読み、独立部分式における意味アクションがクラッシュせず、積極実行されるようになった。
バージョン 2.0.1（2007 年 10 月 23 日）
バグ修正
sub_match<>コンストラクタが、既定コンストラクタで構築したイテレータをコピーするとデバッグ表明にヒットする。
バージョン 2.0.0（2007 年 10 月 12 日）
新機能
意味アクション。
カスタムの表明。
名前付き捕捉
動的正規表現文法。
(?R)構造による動的再帰正規表現。非文字データ検索のサポート。
不正な静的正規表現に対するエラーを改善した。
正規表現アルゴリズムの範囲ベースのインターフェイス。
regex_constants::match_flag_type::format_perl、regex_constants::match_flag_type::format_sedおよびregex_constants::match_flag_type::format_all。operator+(std::string, sub_match<>)とその変種。バージョン 2。このバージョンの正規表現特性は
tolowerとtoupperをもつ。
バグ修正
~(set='a') のような 1 文字の否定が動作するようになった。
バージョン 1.0.2（2007 年 4 月 27 日）
バグ修正
事前の予告どおり、10 番目以降の後方参照が動作するようになった。
このバージョンは Boost 1.34 とともにリリースされた。
バージョン 1.0.1（2006 年 10 月 2 日）
バグ修正
match_results::positionが入れ子の結果に対して動作するようになった。
バージョン 1.0.0（2006 年 3 月 16 日）
バージョン 1.0！
バージョン 0.9.6（2005 年 6 月 19 日）
Boost の受理に向けてレビューされたバージョン。レビューが始まったのは 2005 年 11 月 8 日。2005 年 11 月 28 日、xpressive は Boost に受理された。
バージョン 0.9.3（2005 年 6 月 30 日）
新機能
TR1 形式の
regex_traitsインターフェイス。高速化。
regex_constants::syntax_option_type::ignore_white_space。
バージョン 0.9.0（2004 年 9 月 2 日）
新機能
いろいろ。
バージョン 0.0.1（2003 年 11 月 16 日）
xpressive のアナウンス：http://lists.boost.org/Archives/boost/2003/11/56312.php
- 1
訳注 原文ではバージョン 2.1.0 までしか記述がありませんが、翻訳版では Boost のリリースノートから以降の履歴を抜粋しました。2.1.0 が Boost 1.36（2008 年 8 月 14 日）に相当します。
付録 2：未実装の項目
以下の機能は xpressive 2.x で実装を予定している。
syntax_option_type::collate[.a.]のような照合シーケンス[=a=]のような等価クラスsyntax_option_type::nosubsを使用したときの入れ子結果の生成制御。静的正規表現におけるnosubs修飾子。
ウィッシュリスト。あなたやあなたの会社がお金をくれるなら考えてもいいよ！
単純な正規表現を高速化する、最適化 DFA バックエンド。
basic 、extended 、awk 、grep および egrep 正規表現構文のための別の正規表現コンパイラフロントエンド。
動的正規表現構文のより細かい制御。
ICU を使った完全な Unicode サポート。
地域化サポートの強化（可能な限り
std::localeのカスタムファセットを使う）。
付録 3：Boost.Regexとの違い
xpressive のユーザーの多くは Boost.Regex ライブラリになじんでいると思うので、xpressive と Boost.Regex の重大な違いについて見落としているとしたら私の怠慢である。特に以下の点を挙げる。
xpressive::basic_regex<>は、文字型ではなくイテレータ型に対するテンプレートである。xpressive::basic_regex<>は、文字列から直接構築できない。文字列から正規表現オブジェクトを構築するには、代わりにbasic_regex::compileかregex_compiler<>を使用しなければならない。xpressive::basic_regex<>はimbueメンバ関数を持たない。代わりにxpressive::regex_compiler<>ファクトリにimbueメンバ関数がある。boost::basic_regex<>はstd::basic_string<>メンバのサブセットをもつが、xpressive::basic_regex<>にはない。欠けているメンバは、assign、operator[]、max_size、begin、end、size、compareおよび operator=(std::basic_string<>) である。boost::basic_regex<>にあってxpressive::basic_regex<>にないメンバ関数は、set_expression、get_allocator、imbue、getloc、getflagsおよびstrである。xpressive::basic_regex<>は RegexTraits テンプレート引数をもたない。正規表現構文と地域化に関する振る舞いをカスタマイズするには、regex_compiler<>およびカスタムのstd::locale正規表現ファセットを使用する。xpressive::basic_regex<>およびxpressive::match_results<>は Allocator テンプレート引数を持たない。これはこういう設計である。match_not_dot_nullおよびmatch_not_dot_newlineはmatch_flag_type列挙からsyntax_option_type列挙に移動しており、名前もnot_dot_nullおよびnot_dot_newlineに変更している。syntax_option_type列挙値はサポートしない：escape_in_lists、char_classes、intervals、limited_ops、newline_alt、bk_plus_qm、bk_braces、bk_parens、bk_refs、bk_vbar、use_except、failbit、literal、perlex、basic、extended、emacs、awk、grep、egrep、sed、JavaScript、JScript。match_flag_type列挙値はサポートしない：match_not_bob、match_not_eob、match_perl、match_posixおよびmatch_extra。
また、現在の実装では xpressive の正規表現アルゴリズムは病的な振る舞いや例外によるアボートを検出しない。病的な振る舞いをせず効率のよいパターンを書くのはあなたの責任である。
付録 4：パフォーマンスの比較
xpressive の効率は Boost.Regex に負けず劣らずである。パフォーマンスベンチマークを走らせ、静的正規表現、動的正規表現、Boost.Regex を 2 つのプラットフォーム（gcc（Cygwin）、Visual C++）で比較した。テストは短いマッチと長い検索を行った。いずれのプラットフォームでも、短いマッチでは xpressive が高速であり、長い検索では大体 Boost.Regex と同じだった。2
xpressive 対 Boost.Regex（GCC（Cygwin））
静的正規表現
動的正規表現
以上のパフォーマンス比較結果を次に示す。
テスト仕様
- ハードウェア：
ハイパースレッディング 3GHz Xeon 1GB RAM
- オペレーティングシステム：
Windows XP Professional + Cygwin
- コンパイラ：
GNU C++ 3.4.4（Cygwin 版）
- C++ 標準ライブラリ：
GNU libstdc++ 3.4.4
- Boost.Regex のバージョン：
1.33+ 、BOOST_REGEX_USE_CPP_LOCALE, BOOST_REGEX_RECURSIVE
- xpressive のバージョン：
0.9.6a
比較 1：短いマッチ
以下のテストでは入力文字列に対する正規表現マッチに要した時間を評価項目とする。各テスト結果の上側の数値は最速時間に対して正規化しており、1.0 が最もよい。下側の（括弧で囲んだ）数値は実際の秒時間である。最良の結果は強調してある。
静的 xpressive |
動的 xpressive |
Boost |
テキスト |
正規表現 |
|---|---|---|---|---|
1 (8.79e-07s) |
1.08 (9.54e-07s) |
2.51 (2.2e‑06s) |
|
|
1.06 (1.07e-06s) |
1 (1.01e-06s) |
4.01 (4.06e-06s) |
|
|
1 (1.4e-06s) |
1.13 (1.58e-06s) |
2.89 (4.05e-06s) |
|
|
1 (1.28e-06s) |
1.16 (1.49e-06s) |
3.07 (3.94e-06s) |
|
|
1 (1.22e-06s) |
1.2 (1.46e-06s) |
3.22 (3.93e-06s) |
|
|
1.04 (8.64e-07s) |
1 (8.34e-07s) |
2.5 (2.09e-06s) |
|
|
1.11 (9.09e-07s) |
1 (8.19e-07s) |
2.47 (2.03e-06s) |
|
|
1.12 (9.38e-07s) |
1 (8.34e-07s) |
2.5 (2.08e-06s) |
|
|
1 (7.9e-07s) |
1.06 (8.34e-07s) |
2.49 (1.96e-06s) |
|
|
1 (8.19e-07s) |
1.04 (8.49e-07s) |
2.4 (1.97e-06s) |
|
|
1.09 (8.95e-07s) |
1 (8.19e-07s) |
2.4 (1.96e-06s) |
|
|
1.11 (8.79e-07s) |
1 (7.9e-07s) |
2.57 (2.03e-06s) |
|
|
1.09 (8.94e-07s) |
1 (8.19e-07s) |
2.47 (2.03e-06s) |
|
|
比較 2：長い検索
次のテストは長い英文テキストからすべてのマッチを見つけるのに要した時間を測定した。Project Gutenberg の Mark Twain の完全なテキストを使用した。テキストの長さは 19 MB である。上と同様に上側の数値は正規化時間であり、下側の数値は実際の時間である。最短時間は強調した。
静的 xpressive |
動的 xpressive |
Boost |
正規表現 |
|---|---|---|---|
1 (0.0263s) |
1 (0.0263s) |
1.78 (0.0469s) |
|
1 (0.0234s) |
1 (0.0234s) |
1.79 (0.042s) |
|
1.84 (1.26s) |
2.21 (1.51s) |
1 (0.687s) |
|
1.09 (0.192s) |
2 (0.351s) |
1 (0.176s) |
|
1.41 (0.08s) |
1.21 (0.0684s) |
1 (0.0566s) |
|
1.56 (0.195s) |
1.12 (0.141s) |
1 (0.125s) |
|
xpressive 対 Boost.Regex（Visual C++）
静的 xpressive
動的 xpressive
以上のパフォーマンス比較結果を次に示す。
テスト仕様
- ハードウェア：
ハイパースレッディング 3GHz Xeon 1GB RAM
- オペレーティングシステム：
Windows XP Professional
- コンパイラ：
Visual C++ .NET 2003（7.1）
- C++ 標準ライブラリ：
Dinkumware バージョン 313
- Boost.Regex のバージョン：
1.33+ 、BOOST_REGEX_USE_CPP_LOCALE, BOOST_REGEX_RECURSIVE
- xpressive のバージョン：
0.9.6a
比較 1：短いマッチ
以下のテストでは入力文字列に対する正規表現マッチに要した時間を評価項目とする。各テスト結果の上側の数値は最速時間に対して正規化しており、1.0 が最もよい。下側の（括弧で囲んだ）数値は実際の秒時間である。最良の結果は強調してある。
静的 xpressive |
動的 xpressive |
Boost |
テキスト |
正規表現 |
|---|---|---|---|---|
1 (3.2e-007s) |
1.37 (4.4e-007s) |
2.38 (7.6e‑007s) |
|
|
1 (6.4e-007s) |
1.12 (7.15e-007s) |
1.72 (1.1e-006s) |
|
|
1 (9.82e-007s) |
1.3 (1.28e-06s) |
1.61 (1.58e-006s) |
|
|
1 (8.94e-007s) |
1.3 (1.16e-006s) |
1.7 (1.1e-006s) |
|
|
1 (9.09e-007s) |
1.28 (1.16e-006s) |
1.67 (1.52e-006s) |
|
|
1 (3.06e-007s) |
1.07 (3.28e-007s) |
1.95 (5.96e-007s) |
|
|
1 (3.13e-007s) |
1.09 (3.42e-007s) |
1.86 (5.81e-007s) |
|
|
1 (3.2e-007s) |
1.09 (3.5e-007s) |
1.86 (5.96e-007s) |
|
|
1 (2.68e-007s) |
1.22 (3.28e-007s) |
2 (5.36e-007s) |
|
|
1 (2.76e-007s) |
1.16 (3.2e-007s) |
1.94 (5.36e-007s) |
|
|
1 (2.98e-007s) |
1 (3.06e-007s) |
1.85 (5.51e-007s) |
|
|
1 (3.2e-007s) |
1.12 (3.58e-007s) |
1.81 (5.81e-007s) |
|
|
1 (3.28e-007s) |
1.11 (3.65e-007s) |
1.77 (5.81e-007s) |
|
|
比較 2：長い検索
次のテストは長い英文テキストからすべてのマッチを見つけるのに要した時間を測定した。Project Gutenberg の Mark Twain の完全なテキストを使用した。テキストの長さは 19 MB である。上と同様に上側の数値は正規化時間であり、下側の数値は実際の時間である。最短時間は強調した。
静的 xpressive |
動的 xpressive |
Boost |
正規表現 |
|---|---|---|---|
1 (0.019s) |
1 (0.019s) |
2.98 (0.0566s) |
|
1 (0.0176s) |
1 (0.0176s) |
3.17 (0.0556s) |
|
3.62 (1.78s) |
3.97 (1.95s) |
1 (0.492s) |
|
2.32 (0.344s) |
3.06 (0.453s) |
1 (0.148s) |
|
1 (0.0576s) |
1.05 (0.0606s) |
1.15 (0.0664s) |
|
1.24 (0.164s) |
1.44 (0.191s) |
1 (0.133s) |
|
- 2
おことわり：すべてのベンチマークについて、真のテストとはあなたのパターンとあなたの入力に対してあなたのプラットフォームで xpressive がどう動くかである。よってあなたのアプリケーションで効率が重要なのであれば、あなた自身でテストをするのが最もよい。
付録 5：実装ノート
tracking_ptr<> による循環型コレクション
xpressive では正規表現オブジェクトがお互いや自分自身を値や参照で参照する場合がある。また参照先の正規表現が生存するために参照カウントを使っている。これにより循環参照が生じ、メモリリークが起きる可能性がある。xpressive は tracking_ptr<> という型を使ってリークを回避している。本ドキュメントでは tracking_ptr<> の、高水準な観点からの振る舞いについて述べる。
制限
以下に挙げる設計上の制限を満たす解法でなければならない。
懸垂参照が発生しない：直接・間接的に参照しているオブジェクトはすべて参照が必要な限りは生存しなければならない。
メモリリークが発生しない：オブジェクトは、最終的にはすべて確実に解放しなければならない。
ユーザーの介入がない：ユーザーによる明示的な循環回収ルーチン呼び出しを必要としてはならない。
クリーンアップ処理が例外を送出しない：回収処理はデストラクタから呼び出される可能性が高いため、どのような事情があろうとも例外を送出してはならない。
ハンドル・ボディイディオム
tracking_ptr<> を使うには、型をハンドルとボディに分離しなければならない。xpressive の場合、ハンドル型は basic_regex<> でありボディは regex_impl<> である。ハンドルがボディへの tracking_ptr<> をもつ。
ボディ型は enable_reference_tracking<> を継承しなければならない。これで tracking_ptr<> が使用する帳簿（bookkeeping）となるデータ構造がボディに与えられる。
std::set<shared_ptr<body> > refs_：このボディが参照するボディのコレクション。std::set<weak_ptr<body> > refs_：このボディを参照するボディのコレクション。
参照と依存
上記 1. を「参照」、2. を「依存」と呼ぶことにする。tracking_ptr<> は直接参照されるオブジェクトと（他の参照を介して）間接的に参照されるオブジェクトの両方を参照の集合として扱う、ということは理解しておかなければならない。依存の集合についても同じことが当てはまる。言い換えると、各ボディはそのボディが必要とする他のあらゆるボディに対する直接の参照カウンタをもつ。
なぜこれが重要なのか？あるボディを参照するハンドルがなくなった時点で、そのすべての参照を懸垂参照を心配せずに即座に解放可能だからである。
参照と依存は相互交流の関係である。動作を以下に示す。
オブジェクトが他のオブジェクトを参照として得ると、参照先のオブジェクトは参照元のオブジェクトを依存として得る。
これに加えて参照元のオブジェクトは参照先のオブジェクトがもつ参照をすべて得、参照先のオブジェクトは参照元のオブジェクトがもつ依存をすべて得る。
オブジェクトが新たな参照を獲得すると、その参照はすべての依存オブジェクトにも追加される。
オブジェクトが新たな依存を獲得すると、その依存はすべての参照オブジェクトにも追加される。
オブジェクトが自分自身の依存をもつことは認められない。オブジェクトが自分自身を参照することは可能であり、よくある。
次のコードを考える。
sregex expr;
{
sregex group = '(' >> by_ref(expr) >> ')'; // (1)
sregex fact = +_d | group; // (2)
sregex term = fact >> *(('*' >> fact) | ('/' >> fact)); // (3)
expr = term >> *(('+' >> term) | ('-' >> term)); // (4)
} // (5)
参照と依存がどのように伝播するか 1 行ずつ見ていく。
式 |
効果 |
|---|---|
1） |
group: cnt1 refs{expr} deps={}
expr: cnt2 refs{} deps={group}
|
2） |
group: cnt2 refs{expr} deps={fact}
expr: cnt3 refs{} deps={group,fact}
fact: cnt1 refs{expr,group} deps={}
|
3） |
group: cnt3 refs{expr} deps={fact,term}
expr: cnt4 refs{} deps={group,fact,term}
fact: cnt2 refs{expr,group} deps={term}
term: cnt1 refs{expr,group,fact} deps={}
|
4） |
group: cnt5 refs{expr,group,fact,term} deps={expr,fact,term}
expr: cnt5 refs{expr,group,fact,term} deps={group,fact,term}
fact: cnt5 refs{expr,group,fact,term} deps={expr,group,term}
term: cnt5 refs{expr,group,fact,term} deps={expr,group,fact}
|
5） |
expr: cnt2 refs{expr,group,fact,term} deps={group,fact,term}
|
オブジェクトの循環が発生したときに参照と依存がどのように伝播するかを示している。（4）の行で循環が閉じられ、以降、各オブジェクトは他のオブジェクトに対して参照カウントをもつ。これでなぜリークしないのか？ 先を続けよう。
循環を破る（循環ブレーカ）
ボディは参照と依存の集合をもつ、というところまでは分かった。循環をいつどこで破るかがまだ決まっていない。これはハンドルの一部になっている tracking_ptr<> の仕事である。tracking_ptr<> は 2 つの shared_ptr をもつ。1 つ目は明らかなように shared_ptr<body> であり、このハンドルが参照するボディへの参照である。2 つ目の shared_ptr は循環を破るのに使用し、ボディへのハンドルがすべてスコープから出たときに、ボディがもつ参照の集合を解放する。
このことから分かるように 1 つのボディに対するハンドルは 2 つ以上になる可能性がある。実際、tracking_ptr<> は「書き込み時コピー」セマンティクスを用いており、ハンドルをコピーするとボディは共有される。あるボディへのハンドルは、そのうちすべてスコープの外に出る。このとき、他のボディ（当該ボディそのものかもしれない）が参照を保持していてボディへの参照カウントは0より大きいかもしれない。しかし循環ブレーカはハンドル内にしか存在しないので、循環ブレーカの参照カウントは間違いなく 0 である。ハンドルが存在しなければ循環ブレーカも存在しない。
循環ブレーカが行うことは何だろう？ ボディが std::set<shared_ptr<body> > 型の参照の集合をもつことを思い出していただきたい。この型を「references_type」と呼ぶことにする。循環ブレーカは shared_ptr<references_type> であり、以下に示すカスタムの削除オブジェクトを使う。
template<typename DerivedT>
struct reference_deleter
{
void operator ()(std::set<shared_ptr<DerivedT> > *refs) const
{
refs->clear();
}
};
循環ブレーカの役割は、ボディへの最後のハンドルがなくなったときにボディがもつ参照の集合を解放すること、それだけである。
すべてのボディが最終的に解放されることが保証されるのは明らかである。ハンドルがすべてスコープから出ると、ボディがもつすべての参照が解放され、後には何も（非 0 の参照カウントも）残らない。リークが起こらないことが保証される。
以上のことから懸垂参照が発生しないことが保証される、と言うのは少し難しい。A 、B 、C の 3 つのボディがあるとしよう。A は B を参照し、B は C を参照する。B へのハンドルがすべてスコープから出ると、B がもつ参照の集合が解放される。A が（間接的に）使用しているにも関わらず、これでは C が削除されてしまうのではないか？ そうはならない。A は B だけでなく C も直接参照し続けるように、上記のように参照と依存を伝播しているため、このような状況は起こらない。B がもつ参照の集合が解放されても、各ボディは A が使用中のため削除されない。
将来
std::set 、shared_ptr 、weak_ptr を使っているが、軒並み効率が悪い。手ごろなので使っているだけなのだが。改善できると思う。
また、オブジェクトが必要以上に長い時間生存する場合がある。
sregex b;
{
sregex a = _;
b = by_ref(a);
b = _;
}
// a がこの時点でまだ生存している！
参照と依存を伝播する手法であるため、std::set は拡大するのみである。参照が不要になった場合でも縮小しない。xpressive ではこれは問題にならない。参照オブジェクトのグラフは大きくならず、それぞれ孤立したままである。汎用の参照カウント式循環コレクション機構として tracking_ptr<> を使おうとすると、この問題に焦点が当てられることになるだろう。