java - この正規表現では壊滅的なバックトラッキングが発生するべきではありません

Question

Java の正規表現エンジンがこの正規表現で壊滅的なバックトラッキングモードになる理由を誰か説明できますか? 私が知る限り、すべての交替は他のすべての交替と相互に排他的です。

^(?:[^'\"\\s~:/@#\\|\\^\\&\\[\\]\\(\\)\\\\\\{\\}][^\"\\s~:/@#\\|\\^\\&\\[\\]\\(\\)\\\\\\{\\}]*|
\"(?:[^\"]+|\"\")+\"|
'(?:[^']+|'')+')

文章：'pão de açúcar itaucard mastercard platinum SUSTENTABILIDADE])

一部の代替に所有格一致を追加すると問題が解決しますが、その理由はわかりません.Javaの正規表現ライブラリは、相互に排他的なブランチでバックトラックするには非常にバグが多いに違いありません。

 ^(?:[^'\"\\s~:/@#\\|\\^\\&\\[\\]\\(\\)\\\\\\{\\}][^\"\\s~:/@#\\|\\^\\&\\[\\]\\(\\)\\\\\\{\\}]*|
 \"(?:[^\"]++|\"\")++\"|
 '(?:[^']++|'')++')

score 18 · Accepted Answer

編集: Java のバージョンを最後に追加しました — 本質的に不器用で、読みにくく、保守できないにもかかわらずです。

醜いパターンはもうありません。

最初に行う必要があるのは、人間が読み取り可能であり、結果として保守可能であるというあらゆる可能性に耐えられる方法で正規表現を作成することです。 次に行う必要があるのは、これをプロファイリングして、実際に何を行っているかを確認することです。

つまり、少なくともPattern.COMMENTSmode (または prefix "(?x)") でコンパイルしてから、空白を追加して視覚的なゆとりを持たせる必要があります。私が理解できる限り、実際に一致させようとしているパターンは次のとおりです。

^ 
(?: [^'"\s~:/@\#|^&\[\]()\\{}]    # alt 1: unquoted
    [^"\s~:/@\#|^&\[\]()\\{}] *
  | " (?: [^"]+ | "" )+ "        # alt 2: double quoted
  | ' (?: [^']+ | '' )+ '        # alt 3: single quoted
)

ご覧のとおり、視覚と心をある種の認知チャンキングとして誘導するために、可能な場所に垂直方向と水平方向の両方の空白を導入しました. 不要なバックスラッシュもすべて削除しました。これらはすべて、完全なエラーか、読者を混乱させるだけの難読化ツールです。

垂直方向の空白を適用するときに、どの行から次の行まで同じである部分を同じ列に配置して、どの部分が同じでどの部分が異なるかをすぐに確認できるようにしたことに注意してください。

それを行うと、あなたがここにいるのは、最初に固定された試合であり、その後に3つの選択肢の選択が続くことが最終的にわかります. したがって、これら 3 つの選択肢に説明的なコメントを付けて、推測する必要がないようにしました。

また、あなたの最初の選択肢には、微妙に異なる (否定された) 角かっこで囲まれた 2 つの文字クラスがあることにも気付きました。2 番目のものには、最初のものに見られる一重引用符の除外がありません。これは意図的なものですか？たとえそうであったとしても、私の好みにはこれがあまりにも重複していると思います。更新の一貫性の問題を回避するために、その一部またはすべてを変数に含める必要があります。

プロファイリング

あなたがしなければならない 2 つのことの 2 番目の、そしてより重要なことは、これをプロファイリングすることです。そのパターンがコンパイルされている正規表現プログラムを正確に確認する必要があり、データ上で実行されるときにその実行を追跡する必要があります。

Java のPatternクラスは現在、これを行うことができませんが、私は OraSun の現在のコード管理者とある程度話しましたが、彼はこの機能を Java に追加することに熱心であり、その方法を正確に知っていると考えています。彼は、最初の部分であるコンパイルを行うプロトタイプまで送ってくれました。そのため、これらのいずれかが利用可能になることを期待しています。

その間、代わりに正規表現がプログラミング言語の不可欠な部分であり、厄介な後付けとしてボルトで固定されたものではないツールに目を向けましょう。この基準を満たす言語はいくつかありますが、パターンマッチングの技術が Perl に見られるほど洗練されたレベルに達した言語はありません。

次に、同等のプログラムを示します。

#!/usr/bin/env perl
use v5.10;      # first release with possessive matches
use utf8;       # we have utf8 literals
use strict;     # require variable declarations, etc
use warnings;   # check for boneheadedness

my $match = qr{
    ^ (?: [^'"\s~:/@\#|^&\[\]()\\{}]
          [^"\s~:/@\#|^&\[\]()\\{}] *
        | " (?: [^"]+ | "" )+ "
        | ' (?: [^']+ | '' )+ '
    )
}x;

my $text = "'pão de açúcar itaucard mastercard platinum SUSTENTABILIDAD])";

my $count = 0;

while ($text =~ /$match/g) {
    print "Got it: $&\n";
    $count++;
}

if ($count == 0) {
    print "Match failed.\n";
}

そのプログラムを実行すると、一致が失敗したという予想どおりの回答が得られます。問題は、その理由と方法です。

ここで 2 つのことを調べたいと思います。そのパターンがコンパイルされてどの正規表現プログラムになるかを確認し、その正規表現プログラムの実行をトレースします。

これらは両方とも

use re "debug";

.pragma を介してコマンドラインで指定することもできます-Mre=debug。これは、ソースコードのハッキングを避けるためにここで行うことです。

正規表現のコンパイル

reデバッグプラグマは通常、パターンのコンパイルとその実行の両方を表示します。これらを分離するには、Perl の「コンパイルのみ」スイッチを使用できます-c。これは、コンパイルしたプログラムを実行しようとしません。そうすれば、コンパイルされたパターンだけを見ることができます。これらを実行すると、次の 36 行の出力が生成されます。

$ perl -c -Mre=debug /tmp/bt
Compiling REx "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"...
Final program:
   1: BOL (2)
   2: BRANCH (26)
   3:   ANYOF[^\x09\x0a\x0c\x0d "#&-)/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl] (14)
  14:   STAR (79)
  15:     ANYOF[^\x09\x0a\x0c\x0d "#&()/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl] (0)
  26: BRANCH (FAIL)
  27:   TRIE-EXACT["'] (79)
        <"> (29)
  29:     CURLYX[0] {1,32767} (49)
  31:       BRANCH (44)
  32:         PLUS (48)
  33:           ANYOF[\x00-!#-\xff][{unicode_all}] (0)
  44:       BRANCH (FAIL)
  45:         EXACT <""> (48)
  47:       TAIL (48)
  48:     WHILEM[1/2] (0)
  49:     NOTHING (50)
  50:     EXACT <"> (79)
        <'> (55)
  55:     CURLYX[0] {1,32767} (75)
  57:       BRANCH (70)
  58:         PLUS (74)
  59:           ANYOF[\x00-&(-\xff][{unicode_all}] (0)
  70:       BRANCH (FAIL)
  71:         EXACT <''> (74)
  73:       TAIL (74)
  74:     WHILEM[2/2] (0)
  75:     NOTHING (76)
  76:     EXACT <'> (79)
  78: TAIL (79)
  79: END (0)
anchored(BOL) minlen 1 
/tmp/bt syntax OK
Freeing REx: "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"...

ご覧のとおり、コンパイルされた正規表現プログラムは、独自の「正規表現アセンブリ言語」のようなものです。(それはまた、私が実演した Java プロトタイプが吐き出すものと非常によく似ているので、いつか Java でもこの種のものを見ることになると思います。) すべての詳細はこれに不可欠というわけではありません。ただし、ノード 2 の命令は BRANCH であり、失敗すると分岐 26 の別の BRANCH を実行することに注意してください。正規表現プログラムの唯一の他の部分であるその 2 番目の BRANCH は、単一の TRIE-EXACT ノードで構成されています。これらの 2 つのトライブランチ内で何が起こるかは、これから説明します。

正規表現の実行

今度は、実行時に何が起こるかを見てみましょう。使用しているテキスト文字列は、かなりの量のバックトラッキングを引き起こします。つまり、最終的に失敗する前に、多くの出力を通過する必要があります。どのくらいの出力？さて、これだけ：

$ perl -Mre=debug /tmp/bt 2>&1 | wc -l
9987

10,000 歩というのは、「壊滅的なバックトラッキングモード」という意味だと思います。それをもっと分かりやすいものに切り詰めることができないことを見てみましょう。入力文字列の長さは 61 文字です。'pão何が起こっているのかをよりよく確認するために、わずか 4 文字のだけに切り詰めることができます。(まあ、NFC では、つまり、NFD では 5 つのコードポイントですが、ここでは何も変わりません)。その結果、167 行の出力が得られます。

$ perl -Mre=debug /tmp/bt 2>&1 | wc -l
167

実際、文字列がこれだけの文字数の場合に得られる正規表現 (コンパイルと) 実行プロファイリングの行は次のとおりです。

chars   lines   string
    1     63   ‹'›
    2     78   ‹'p›  
    3    109   ‹'pã›
    4    167   ‹'pão› 
    5    290   ‹'pão ›
    6    389   ‹'pão d›
    7    487   ‹'pão de›
    8    546   ‹'pão de ›
    9    615   ‹'pão de a›
   10    722   ‹'pão de aç›
  ....
   61   9987   ‹'pão de açúcar itaucard mastercard platinum SUSTENTABILIDAD])›

文字列が 4 文字の場合のデバッグ出力を見てみましょう'pão。今回はコンパイル部分を省略して、実行部分のみを示します。

$ perl -Mre=debug /tmp/bt
Matching REx "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"... against "'p%x{e3}o"
UTF-8 string...
   0 <> <'p%x{e3}o>  |  1:BOL(2)
   0 <> <'p%x{e3}o>  |  2:BRANCH(26)
   0 <> <'p%x{e3}o>  |  3:  ANYOF[^\x09\x0a\x0c\x0d "#&-)/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl](14)
                            failed...
   0 <> <'p%x{e3}o>  | 26:BRANCH(78)
   0 <> <'p%x{e3}o>  | 27:  TRIE-EXACT["'](79)
   0 <> <'p%x{e3}o>  |      State:    1 Accepted: N Charid:  2 CP:  27 After State:    3
   1 <'> <p%x{e3}o>  |      State:    3 Accepted: Y Charid:  0 CP:   0 After State:    0
                            got 1 possible matches
                            TRIE matched word #2, continuing
                            only one match left, short-circuiting: #2 <'>
   1 <'> <p%x{e3}o>  | 55:  CURLYX[0] {1,32767}(75)
   1 <'> <p%x{e3}o>  | 74:    WHILEM[2/2](0)
                              whilem: matched 0 out of 1..32767
   1 <'> <p%x{e3}o>  | 57:      BRANCH(70)   1 <'> <p%x{e3}o>          | 58:        PLUS(74)
                                  ANYOF[\x00-&(-\xff][{unicode_all}] can match 3 times out of 2147483647...
   5 <'p%x{e3}o> <>  | 74:          WHILEM[2/2](0)
                                    whilem: matched 1 out of 1..32767
   5 <'p%x{e3}o> <>  | 57:            BRANCH(70)
   5 <'p%x{e3}o> <>  | 58:              PLUS(74)
                                        ANYOF[\x00-&(-\xff][{unicode_all}] can match 0 times out of 2147483647...
                                        failed...
   5 <'p%x{e3}o> <>  | 70:            BRANCH(73)
   5 <'p%x{e3}o> <>  | 71:              EXACT <''>(74)
                                        failed...
                                      BRANCH failed...
                                    whilem: failed, trying continuation...
   5 <'p%x{e3}o> <>  | 75:            NOTHING(76)
   5 <'p%x{e3}o> <>  | 76:            EXACT <'>(79)
                                      failed...
                                    failed...
   4 <'p%x{e3}> <o>  | 74:          WHILEM[2/2](0)
                                    whilem: matched 1 out of 1..32767
   4 <'p%x{e3}> <o>  | 57:            BRANCH(70)
   4 <'p%x{e3}> <o>  | 58:              PLUS(74)
                                        ANYOF[\x00-&(-\xff][{unicode_all}] can match 1 times out of 2147483647...
   5 <'p%x{e3}o> <>  | 74:                WHILEM[2/2](0)
                                          whilem: matched 2 out of 1..32767
   5 <'p%x{e3}o> <>  | 57:                  BRANCH(70)
   5 <'p%x{e3}o> <>  | 58:                    PLUS(74)
                                              ANYOF[\x00-&(-\xff][{unicode_all}] can match 0 times out of 2147483647...
                                              failed...
   5 <'p%x{e3}o> <>  | 70:                  BRANCH(73)
   5 <'p%x{e3}o> <>  | 71:                    EXACT <''>(74)
                                              failed...
                                            BRANCH failed...
                                          whilem: failed, trying continuation...
   5 <'p%x{e3}o> <>  | 75:                  NOTHING(76)
   5 <'p%x{e3}o> <>  | 76:                  EXACT <'>(79)
                                            failed...
                                          failed...
                                        failed...
   4 <'p%x{e3}> <o>  | 70:            BRANCH(73)
   4 <'p%x{e3}> <o>  | 71:              EXACT <''>(74)
                                        failed...
                                      BRANCH failed...
                                    whilem: failed, trying continuation...
   4 <'p%x{e3}> <o>  | 75:            NOTHING(76)
   4 <'p%x{e3}> <o>  | 76:            EXACT <'>(79)
                                      failed...
                                    failed...
   2 <'p> <%x{e3}o>  | 74:          WHILEM[2/2](0)
                                    whilem: matched 1 out of 1..32767
   2 <'p> <%x{e3}o>  | 57:            BRANCH(70)
   2 <'p> <%x{e3}o>  | 58:              PLUS(74)
                                        ANYOF[\x00-&(-\xff][{unicode_all}] can match 2 times out of 2147483647...
   5 <'p%x{e3}o> <>  | 74:                WHILEM[2/2](0)
                                          whilem: matched 2 out of 1..32767
   5 <'p%x{e3}o> <>  | 57:                  BRANCH(70)
   5 <'p%x{e3}o> <>  | 58:                    PLUS(74)
                                              ANYOF[\x00-&(-\xff][{unicode_all}] can match 0 times out of 2147483647...
                                              failed...
   5 <'p%x{e3}o> <>  | 70:                  BRANCH(73)
   5 <'p%x{e3}o> <>  | 71:                    EXACT <''>(74)
                                              failed...
                                            BRANCH failed...
                                          whilem: failed, trying continuation...
   5 <'p%x{e3}o> <>  | 75:                  NOTHING(76)
   5 <'p%x{e3}o> <>  | 76:                  EXACT <'>(79)
                                            failed...
                                          failed...
   4 <'p%x{e3}> <o>  | 74:                WHILEM[2/2](0)
                                          whilem: matched 2 out of 1..32767
   4 <'p%x{e3}> <o>  | 57:                  BRANCH(70)
   4 <'p%x{e3}> <o>  | 58:                    PLUS(74)
                                              ANYOF[\x00-&(-\xff][{unicode_all}] can match 1 times out of 2147483647...
   5 <'p%x{e3}o> <>  | 74:                      WHILEM[2/2](0)
                                                whilem: matched 3 out of 1..32767
   5 <'p%x{e3}o> <>  | 57:                        BRANCH(70)
   5 <'p%x{e3}o> <>  | 58:                          PLUS(74)
                                                    ANYOF[\x00-&(-\xff][{unicode_all}] can match 0 times out of 2147483647.
..
                                                    failed...
   5 <'p%x{e3}o> <>  | 70:                        BRANCH(73)
   5 <'p%x{e3}o> <>  | 71:                          EXACT <''>(74)
                                                    failed...
                                                  BRANCH failed...
                                                whilem: failed, trying continuation...
   5 <'p%x{e3}o> <>  | 75:                        NOTHING(76)
   5 <'p%x{e3}o> <>  | 76:                        EXACT <'>(79)
                                                  failed...
                                                failed...
                                              failed...
   4 <'p%x{e3}> <o>  | 70:                  BRANCH(73)
   4 <'p%x{e3}> <o>  | 71:                    EXACT <''>(74)
                                              failed...
                                            BRANCH failed...
                                          whilem: failed, trying continuation...
   4 <'p%x{e3}> <o>  | 75:                  NOTHING(76)
   4 <'p%x{e3}> <o>  | 76:                  EXACT <'>(79)
                                            failed...
                                          failed...
                                        failed...
   2 <'p> <%x{e3}o>  | 70:            BRANCH(73)
   2 <'p> <%x{e3}o>  | 71:              EXACT <''>(74)
                                        failed...
                                      BRANCH failed...
                                    whilem: failed, trying continuation...
   2 <'p> <%x{e3}o>  | 75:            NOTHING(76)
   2 <'p> <%x{e3}o>  | 76:            EXACT <'>(79)
                                      failed...
                                    failed...
                                  failed...
   1 <'> <p%x{e3}o>  | 70:      BRANCH(73)
   1 <'> <p%x{e3}o>  | 71:        EXACT <''>(74)
                                  failed...
                                BRANCH failed...
                              failed...
                            failed...
                          BRANCH failed...
Match failed
Match failed.
Freeing REx: "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"...

そこで起こっているのは、ターゲット文字列が単一引用符で始まるため、単一引用符に一致した後の 3 つの選択肢の最後であるノード 55 に、トライがすぐに分岐することです。それはこれです：

  | ' (?: [^']+ | '' )+ '        # alt 3: single quoted

ノード 55 は、次のトライブランチです。

        <'> (55)
  55:     CURLYX[0] {1,32767} (75)
  57:       BRANCH (70)
  58:         PLUS (74)
  59:           ANYOF[\x00-&(-\xff][{unicode_all}] (0)
  70:       BRANCH (FAIL)
  71:         EXACT <''> (74)

そして、壊滅的なバックオフが発生している場所を示す実行トレースは次のとおりです。

   1 <'> <p%x{e3}o>  | 74:    WHILEM[2/2](0)
                              whilem: matched 0 out of 1..32767
   1 <'> <p%x{e3}o>  | 57:      BRANCH(70)
   1 <'> <p%x{e3}o>  | 58:        PLUS(74)
                                  ANYOF[\x00-&(-\xff][{unicode_all}] can match 3 times out of 2147483647...
   5 <'p%x{e3}o> <>  | 74:          WHILEM[2/2](0)
                                    whilem: matched 1 out of 1..32767
   5 <'p%x{e3}o> <>  | 57:            BRANCH(70)
   5 <'p%x{e3}o> <>  | 58:              PLUS(74)
                                        ANYOF[\x00-&(-\xff][{unicode_all}] can match 0 times out of 2147483647...
                                        failed...
   5 <'p%x{e3}o> <>  | 70:            BRANCH(73)
   5 <'p%x{e3}o> <>  | 71:              EXACT <''>(74)
                                        failed...
                                      BRANCH failed...
                                    whilem: failed, trying continuation...
   5 <'p%x{e3}o> <>  | 75:            NOTHING(76)
   5 <'p%x{e3}o> <>  | 76:            EXACT <'>(79)
                                      failed...
                                    failed...
   4 <'p%x{e3}> <o>  | 74:          WHILEM[2/2](0)
                                    whilem: matched 1 out of 1..32767
   4 <'p%x{e3}> <o>  | 57:            BRANCH(70)
   4 <'p%x{e3}> <o>  | 58:              PLUS(74)
                                        ANYOF[\x00-&(-\xff][{unicode_all}] can match 1 times out of 2147483647...
   5 <'p%x{e3}o> <>  | 74:                WHILEM[2/2](0)
                                          whilem: matched 2 out of 1..32767

ノード 58 は、文字列内の残りの 3 文字すべてをむさぼり食ったpão. これにより、単一引用符の完全一致の終了が失敗しました。したがって、一重引用符のペアである代替を試みますが、これも失敗します。

この時点で、私はあなたのパターンに疑問を呈する必要があります. すべきではない

' (?: [^']+ | '' )+ '

本当にこれだけですか？

' [^']* '

何が起こっているかというと、論理的に決して起こり得ない何かを探してバックトラックする方法がたくさんあるということです。ネストされた量指定子があり、それがあらゆる種類の絶望的で無知な多忙な仕事を引き起こしています。

パターンをこれに単純化すると、次のようになります。

^ (?: [^'"\s~:/@\#|^&\[\]()\\{}] +
    | " [^"]* "
    | ' [^']* '
  )

入力文字列のサイズに関係なく、同じ数のトレース出力行が得られるようになりました: わずか 40 行で、これにはコンパイルが含まれます。文字列全体のコンパイルと実行の両方を確認します。

Compiling REx "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"...
Final program:
   1: BOL (2)
   2: BRANCH (26)
   3:   ANYOF[^\x09\x0a\x0c\x0d "#&-)/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl] (14)
  14:   STAR (61)
  15:     ANYOF[^\x09\x0a\x0c\x0d "#&()/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl] (0)
  26: BRANCH (FAIL)
  27:   TRIE-EXACT["'] (61)
        <"> (29)
  29:     STAR (41)
  30:       ANYOF[\x00-!#-\xff][{unicode_all}] (0)
  41:     EXACT <"> (61)
        <'> (46)
  46:     STAR (58)
  47:       ANYOF[\x00-&(-\xff][{unicode_all}] (0)
  58:     EXACT <'> (61)
  60: TAIL (61)
  61: END (0)
anchored(BOL) minlen 1 
Matching REx "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"... against "'p%x{e3}o de a%x{e7}%x{fa}car itaucard mast
ercard platinum S"...
UTF-8 string...
   0 <> <'p%x{e3}o >  |  1:BOL(2)
   0 <> <'p%x{e3}o >  |  2:BRANCH(26)
   0 <> <'p%x{e3}o >  |  3:  ANYOF[^\x09\x0a\x0c\x0d "#&-)/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl](14)
                             failed...
   0 <> <'p%x{e3}o >  | 26:BRANCH(60)
   0 <> <'p%x{e3}o >  | 27:  TRIE-EXACT["'](61)
   0 <> <'p%x{e3}o >  |      State:    1 Accepted: N Charid:  2 CP:  27 After State:    3
   1 <'> <p%x{e3}o d> |      State:    3 Accepted: Y Charid:  0 CP:   0 After State:    0
                             got 1 possible matches
                             TRIE matched word #2, continuing
                             only one match left, short-circuiting: #2 <'>
   1 <'> <p%x{e3}o d> | 46:  STAR(58)
                             ANYOF[\x00-&(-\xff][{unicode_all}] can match 60 times out of 2147483647...
                             failed...
                           BRANCH failed...
Match failed
Match failed.
Freeing REx: "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"...

所有格マッチングがここでの答えかもしれないと考えていたのは知っていますが、本当の問題は元のパターンの誤ったロジックだと思います。これがどれだけ正常に実行されているかがわかりますか?

古いパターンで所有格を使用して実行すると、意味がないと思いますが、一定の実行時間は得られますが、より多くの手順が必要になります。このパターンで

   ^ (?: [^'"\s~:/@\#|^&\[\]()\\{}] +    # alt 1: unquoted
       | " (?: [^"]++ | "" )++ "        # alt 2: double quoted
       | ' (?: [^']++ | '' )++ '        # alt 3: single quoted
     )

コンパイルと実行プロファイルは次のとおりです。

Compiling REx "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"...
Final program:
   1: BOL (2)
   2: BRANCH (26)
   3:   ANYOF[^\x09\x0a\x0c\x0d "#&-)/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl] (14)
  14:   STAR (95)
  15:     ANYOF[^\x09\x0a\x0c\x0d "#&()/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl] (0)
  26: BRANCH (FAIL)
  27:   TRIE-EXACT["'] (95)
        <"> (29)
  29:     SUSPEND (58)
  31:       CURLYX[0] {1,32767} (55)
  33:         BRANCH (50)
  34:           SUSPEND (54)
  36:             PLUS (48)
  37:               ANYOF[\x00-!#-\xff][{unicode_all}] (0)
  48:             SUCCEED (0)
  49:           TAIL (53)
  50:         BRANCH (FAIL)
  51:           EXACT <""> (54)
  53:         TAIL (54)
  54:       WHILEM[1/2] (0)
  55:       NOTHING (56)
  56:       SUCCEED (0)
  57:     TAIL (58)
  58:     EXACT <"> (95)
        <'> (63)
  63:     SUSPEND (92)
  65:       CURLYX[0] {1,32767} (89)
  67:         BRANCH (84)
  68:           SUSPEND (88)
  70:             PLUS (82)
  71:               ANYOF[\x00-&(-\xff][{unicode_all}] (0)
  82:             SUCCEED (0)
  83:           TAIL (87)
  84:         BRANCH (FAIL)
  85:           EXACT <''> (88)
  87:         TAIL (88)
  88:       WHILEM[2/2] (0)
  89:       NOTHING (90)
  90:       SUCCEED (0)
  91:     TAIL (92)
  92:     EXACT <'> (95)
  94: TAIL (95)
  95: END (0)
anchored(BOL) minlen 1 
Matching REx "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"... against "'p%x{e3}o de a%x{e7}%x{fa}car itaucard mastercard platinum S"...
UTF-8 string...
   0 <> <'p%x{e3}o > |  1:BOL(2)
   0 <> <'p%x{e3}o > |  2:BRANCH(26)
   0 <> <'p%x{e3}o > |  3:  ANYOF[^\x09\x0a\x0c\x0d "#&-)/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl](14)
                            failed...
   0 <> <'p%x{e3}o > | 26:BRANCH(94)
   0 <> <'p%x{e3}o > | 27:  TRIE-EXACT["'](95)
   0 <> <'p%x{e3}o > |      State:    1 Accepted: N Charid:  2 CP:  27 After State:    3
   1 <'> <p%x{e3}o d>|      State:    3 Accepted: Y Charid:  0 CP:   0 After State:    0
                            got 1 possible matches
                            TRIE matched word #2, continuing
                            only one match left, short-circuiting: #2 <'>
   1 <'> <p%x{e3}o d>| 63:  SUSPEND(92)
   1 <'> <p%x{e3}o d>| 65:    CURLYX[0] {1,32767}(89)
   1 <'> <p%x{e3}o d>| 88:      WHILEM[2/2](0)
                                whilem: matched 0 out of 1..32767
   1 <'> <p%x{e3}o d>| 67:        BRANCH(84)
   1 <'> <p%x{e3}o d>| 68:          SUSPEND(88)
   1 <'> <p%x{e3}o d>| 70:            PLUS(82)
                                      ANYOF[\x00-&(-\xff][{unicode_all}] can match 60 times out of 2147483647...
  64 <NTABILIDAD])> <| 82:              SUCCEED(0)
                                        subpattern success...
  64 <NTABILIDAD])> <| 88:          WHILEM[2/2](0)
                                    whilem: matched 1 out of 1..32767
  64 <NTABILIDAD])> <| 67:            BRANCH(84)
  64 <NTABILIDAD])> <| 68:              SUSPEND(88)
  64 <NTABILIDAD])> <| 70:                PLUS(82)
                                          ANYOF[\x00-&(-\xff][{unicode_all}] can match 0 times out of 2147483647...
                                          failed...
                                        failed...
  64 <NTABILIDAD])> <| 84:            BRANCH(87)
  64 <NTABILIDAD])> <| 85:              EXACT <''>(88)
                                        failed...
                                      BRANCH failed...
                                    whilem: failed, trying continuation...
  64 <NTABILIDAD])> <| 89:            NOTHING(90)
  64 <NTABILIDAD])> <| 90:            SUCCEED(0)
                                      subpattern success...
  64 <NTABILIDAD])> <| 92:  EXACT <'>(95)
                failed...
              BRANCH failed...
Match failed
Match failed.
Freeing REx: "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"...

私はまだ私のソリューションが好きです。短いです。

編集

Java バージョンは、同じパターンの Perl バージョンよりも 100 倍多くのステップを実際に取っているようです。その理由はわかりません — Perl 正規表現コンパイラーは、Java 正規表現コンパイラーよりも最適化において約 100 倍スマートです。話すことは決してありませんし、すべきです。

同等の Java プログラムを次に示します。適切にループできるように、先頭のアンカーを削除しました。

$ cat java.crap
import java.util.regex.*;

public class crap {

public static void
main(String[ ] argv) {
    String input = "'pão de açúcar itaucard mastercard platinum SUSTENTABILIDAD])";
    String regex = "\n"
                + "(?: [^'\"\\s~:/@\\#|^&\\[\\]()\\\\{}]    # alt 1: unquoted         \n"
                + "    [^\"\\s~:/@\\#|^&\\[\\]()\\\\{}] *                     \n"
                + "  | \" (?: [^\"]++ | \"\" )++ \"       # alt 2: double quoted   \n"
                + "  | ' (?: [^']++ | '' )++ '       # alt 3: single quoted   \n"
                + ")                                                          \n"
                ;
    System.out.printf("Matching ‹%s› =~ qr{%s}x\n\n", input, regex);

    Pattern regcomp = Pattern.compile(regex, Pattern.COMMENTS);
    Matcher regexec = regcomp.matcher(input);

    int count;
    for (count = 0; regexec.find(); count++) {
       System.out.printf("Found match: ‹%s›\n", regexec.group());
    }
    if (count == 0) {
        System.out.printf("Match failed.\n");
    }
  }
}

実行すると、次のようになります。

$ javac -encoding UTF-8 crap.java && java -Dfile.encoding=UTF-8 crap
Matching ‹'pão de açúcar itaucard mastercard platinum SUSTENTABILIDAD])› =~ qr{
(?: [^'"\s~:/@\#|^&\[\]()\\{}]    # alt 1: unquoted         
    [^"\s~:/@\#|^&\[\]()\\{}] *                     
  | " (?: [^"]++ | "" )++ "       # alt 2: double quoted   
  | ' (?: [^']++ | '' )++ '       # alt 3: single quoted   
)                                                          
}x

Found match: ‹pão›
Found match: ‹de›
Found match: ‹açúcar›
Found match: ‹itaucard›
Found match: ‹mastercard›
Found match: ‹platinum›
Found match: ‹SUSTENTABILIDAD›

お分かりのように、Java でのパターンマッチングについては非常に多くのことが語られていますが、そのどれも口うるさい警察に通用するものではありません。それは単にお尻の王室の痛みです。

score 6 · Accepted Answer

私もこれを驚かせたことを認めなければなりませんが、RegexBuddyでも同じ結果が得られます。つまり、100万ステップ後に試行を終了します。壊滅的なバックトラッキングに関する警告は、ネストされた数量詞に焦点を当てる傾向があることを私は知っていますが、私の経験では、交代は少なくとも同じくらい危険です。実際、正規表現の最後の部分をこれから変更すると、次のようになります。

'(?:[^']+|'')+'

...これに：

'(?:[^']*(?:''[^']*)*)'

...11ステップで失敗します。これは、フリードルの「展開されたループ」手法の例であり、彼は次のように分解します。

opening normal * ( special normal * ) * closing
   '     [^']        ''     [^']           '

ネストされた星は、次の場合に限り安全です。

specialnormal同じものに一致することはありません、
special常に少なくとも1つの文字と一致し、
specialアトミックです（一致する方法は1つだけでなければなりません）。

その場合、正規表現は最小限のバックトラックと一致せず、バックトラックなしで成功します。一方、オルタネーションバージョンはバックトラックすることがほぼ保証されており、一致する可能性がない場合は、ターゲットストリングの長さが長くなると、すぐに制御不能になります。一部のフレーバーで過度にバックトラックしない場合は、この問題に対処するために特別に最適化が組み込まれているためです。これまでのところ、ほとんどのフレーバーでは実行されていません。

score 0 · Accepted Answer

この正規表現でJavaの正規表現エンジンが壊滅的なモードになる理由を誰かが説明できますか?

文字列の場合:

'pão de açúcar itaucard mastercard platinum SUSTENTABILIDADE])

正規表現のこの部分が問題になるようです：

'(?:[^']+|'')+'

最初'に一致してから最後に一致しないため'、ネストされた量指定子のすべての組み合わせをバックトラックします。

正規表現のバックトラックを許可すると、バックトラックします (失敗した場合)。それを防ぐには、アトミックグループや所有量指定子を使用します。

ところで、その正規表現ではほとんどのエスケープは必要ありません。文字クラス ( []) でエスケープする必要があるのは charsだけ^-]です。ただし、通常は、エスケープする必要がないように配置できます。もちろん\、文字列を引用符で囲んでいるものは何でも（二重）エスケープする必要があります。

"^(?:[^]['\"\\s~:/@#|^&(){}\\\\][^][\"\s~:/@#|^&(){}\\\\]*|\"(?:[^\"]++|\"\")++\"|'(?:[^']++|'')++')"

java - この正規表現では壊滅的なバックトラッキングが発生するべきではありません

3 に答える 3

醜いパターンはもうありません。

プロファイリング

正規表現のコンパイル

正規表現の実行

編集

Related