Ошибка совпадения стека в java-счете

Ответ 1

Есть 2 способа исправить вашу проблему:

• Соберите правильную строку ввода и получите значения ключа из Map.

  Я настоятельно рекомендую использовать этот метод, так как код будет намного чище, и нам больше не нужно смотреть ограничение на размер ввода.

• Измените существующее регулярное выражение, чтобы значительно уменьшить влияние ошибки реализации, которая вызывает StackOverflowError.

Разбор входной строки

Вы можете разобрать входную строку со следующим регулярным выражением:

\G\s*+(\w++)=([^\s"]++|"[^"]*+")(?:\s++|$)

• Все квантификаторы становятся собственными (*+ вместо *, ++ вместо +), так как шаблон, который я написал, не нуждается в обратном слежении.

• Вы можете найти основное регулярное выражение (\w++)=([^\s"]++|"[^"]*+") для сопоставления пар ключ-значение в середине.

• \G заключается в том, чтобы убедиться, что матч начинается с того момента, когда последнее совпадение заканчивается. Он используется, чтобы не допустить, чтобы движок "обрушился", когда он не соответствует.

• \s*+ и (?:\s++|$) предназначены для потребления лишних пробелов. Я указываю (?:\s++|$) вместо \s*+, чтобы предотвратить распознавание key="value"key=value как допустимого ввода.

Полный примерный код можно найти ниже:

private static final Pattern KEY_VALUE = Pattern.compile("\\G\\s*+(\\w++)=([^\\s\"]++|\"[^\"]*+\")(?:\\s++|$)");

public static Map<String, String> parseKeyValue(String kvString) {
    Matcher matcher = KEY_VALUE.matcher(kvString);

    Map<String, String> output = new HashMap<String, String>();
    int lastIndex = -1;

    while (matcher.find()) {
        output.put(matcher.group(1), matcher.group(2));
        lastIndex = matcher.end();
    }

    // Make sure that we match everything from the input string
    if (lastIndex != kvString.length()) {
        return null;
    }

    return output;
}

Возможно, вы захотите исключить значения в зависимости от ваших требований.

Вы также можете переписать функцию, чтобы передать List ключей, которые хотите извлечь, и выбрать их в цикле while, когда вы идете, чтобы избежать сохранения ключей, которые вам не нужны.

Изменить регулярное выражение

Проблема заключается в том, что внешнее повторение (?:[^"]|"[^"]*")* реализуется с рекурсией, что приводит к StackOverflowError, когда входная строка достаточно длинная.

В частности, в каждом повторении он совпадает либо с котируемым токеном, либо с одним символом без кавычек. В результате стек растет линейно с количеством некатегоризированных символов и взрывается.

Вы можете заменить все экземпляры (?:[^"]|"[^"]*")* на [^"]*(?:"[^"]*"[^"]*)*. Стек теперь будет линейно увеличиваться по числу котируемых токенов, поэтому StackOverflowError не будет возникать, если в строке ввода нет тысяч котируемых токенов.

Pattern KEY_CAPTURE = Pattern.compile("app=github(?=[^\"]*(?:\"[^\"]*\"[^\"]*)*\\s+user=(?<user>\\S+))?(?=[^\"]*(?:\"[^\"]*\"[^\"]*)*\\s+repo=(?<repo>\\S+))?(?=[^\"]*(?:\"[^\"]*\"[^\"]*)*\\s+remote_address=(?<ip>\\S+))?(?=[^\"]*(?:\"[^\"]*\"[^\"]*)*\\s+now=\"(?<time>\\S+)\\+\\d\\d:\\d\\d\")?(?=[^\"]*(?:\"[^\"]*\"[^\"]*)*\\s+url=\"(?<url>\\S+)\")?(?=[^\"]*(?:\"[^\"]*\"[^\"]*)*\\s+referer=\"(?<referer>\\S+)\")?(?=[^\"]*(?:\"[^\"]*\"[^\"]*)*\\s+status=(?<status>\\S+))?(?=[^\"]*(?:\"[^\"]*\"[^\"]*)*\\s+elapsed=(?<elapsed>\\S+))?(?=[^\"]*(?:\"[^\"]*\"[^\"]*)*\\s+request_method=(?<requestmethod>\\S+))?(?=[^\"]*(?:\"[^\"]*\"[^\"]*)*\\s+created_at=\"(?<createdat>\\S+)(?:-|\\+)\\d\\d:\\d\\d\")?(?=[^\"]*(?:\"[^\"]*\"[^\"]*)*\\s+pull_request_id=(?<pullrequestid>\\d+))?(?=[^\"]*(?:\"[^\"]*\"[^\"]*)*\\s+at=(?<at>\\S+))?(?=[^\"]*(?:\"[^\"]*\"[^\"]*)*\\s+fn=(?<fn>\\S+))?(?=[^\"]*(?:\"[^\"]*\"[^\"]*)*\\s+method=(?<method>\\S+))?(?=[^\"]*(?:\"[^\"]*\"[^\"]*)*\\s+current_user=(?<user2>\\S+))?(?=[^\"]*(?:\"[^\"]*\"[^\"]*)*\\s+content_length=(?<contentlength>\\S+))?(?=[^\"]*(?:\"[^\"]*\"[^\"]*)*\\s+request_category=(?<requestcategory>\\S+))?(?=[^\"]*(?:\"[^\"]*\"[^\"]*)*\\s+controller=(?<controller>\\S+))?(?=[^\"]*(?:\"[^\"]*\"[^\"]*)*\\s+action=(?<action>\\S+))?");

Это следует из эквивалентного разложения регулярного выражения (A|B)* → A*(BA*)*. Что использовать в качестве A или B зависит от их количества повторений - в зависимости от того, какие повторы больше должны быть A, а другое должно быть B.

Глубокое погружение в реализацию

StackOverflowError в Pattern - известная проблема, которая может произойти, когда ваш шаблон содержит повторение недетерминированной группы ¹ для захвата/не захвата, которая является подшаблоном (?:[^"]|"[^"]*")* в вашем случае.

^{1 Это терминология, используемая в исходном коде Pattern, который, вероятно, должен быть индикатором того, что шаблон имеет фиксированную длину. Однако реализация считает, что чередование | является недетерминированным независимо от фактического шаблона.}

Жадное или ленивое повторение группы недетерминированного захвата/не захвата компилируется в классы Loop/LazyLoop, которые реализуют повторение путем рекурсии. В результате такой шаблон чрезвычайно подвержен запуску StackOverflowError, особенно когда группа содержит ветвь, в которой одновременно сопоставляется только один символ.

С другой стороны, детерминированное повторение ² притяжательное повторение и повторение независимой группы (?>...) (как группа атома или группа без обратного отслеживания) скомпилированы в Curly/GroupCurly классы, которые обрабатывают повторение с помощью цикла в большинстве случаев, поэтому не будет StackOverflowError.

^{2 Повторяемый шаблон представляет собой класс символов или группу захвата/не фиксирования фиксированной длины без какого-либо чередования}

Вы можете увидеть, как скомпилирован фрагмент исходного реджикса. Обратите внимание на проблемную часть, которая начинается с Loop и сравнивает ее с вашей трассировкой стека.

app=github(?=(?:[^"]|"[^"]*")*\s+user=(?<user>\S+))?(?=(?:[^"]|"[^"]*")*\s+repo=(?<repo>\S+))?
BnM. Boyer-Moore (BMP only version) (length=10)
  app=github
Ques. Greedy optional quantifier
  Pos. Positive look-ahead
    GroupHead. local=0
    Prolog. Loop wrapper
    Loop [1889ca51]. Greedy quantifier {0,2147483647}
      GroupHead. local=1
      Branch. Alternation (in printed order):
        CharProperty.complement. S̄:
          BitClass. Match any of these 1 character(s):
            "
        ---
        Single. Match code point: U+0022 QUOTATION MARK
        Curly. Greedy quantifier {0,2147483647}
          CharProperty.complement. S̄:
            BitClass. Match any of these 1 character(s):
              "
          Node. Accept match
        Single. Match code point: U+0022 QUOTATION MARK
        ---
      BranchConn [7e41986c]. Connect branches to sequel.
      GroupTail [47e1b36]. local=1, group=0. --[next]--> Loop [1889ca51]
    Curly. Greedy quantifier {1,2147483647}
      Ctype. POSIX (US-ASCII): SPACE
      Node. Accept match
    Slice. Match the following sequence (BMP only version) (length=5)
      user=
    GroupHead. local=3
    Curly. Greedy quantifier {1,2147483647}
      CharProperty.complement. S̄:
        Ctype. POSIX (US-ASCII): SPACE
      Node. Accept match
    GroupTail [732c7887]. local=3, group=2. --[next]--> GroupTail [6c9d2223]
    GroupTail [6c9d2223]. local=0, group=0. --[next]--> Node [4ea5d7f2]
    Node. Accept match
  Node. Accept match
Ques. Greedy optional quantifier
  Pos. Positive look-ahead
    GroupHead. local=4
    Prolog. Loop wrapper
    Loop [402c5f8a]. Greedy quantifier {0,2147483647}
      GroupHead. local=5
      Branch. Alternation (in printed order):
        CharProperty.complement. S̄:
          BitClass. Match any of these 1 character(s):
            "
        ---
        Single. Match code point: U+0022 QUOTATION MARK
        Curly. Greedy quantifier {0,2147483647}
          CharProperty.complement. S̄:
            BitClass. Match any of these 1 character(s):
              "
          Node. Accept match
        Single. Match code point: U+0022 QUOTATION MARK
        ---
      BranchConn [21347df0]. Connect branches to sequel.
      GroupTail [7d382897]. local=5, group=0. --[next]--> Loop [402c5f8a]
    Curly. Greedy quantifier {1,2147483647}
      Ctype. POSIX (US-ASCII): SPACE
      Node. Accept match
    Slice. Match the following sequence (BMP only version) (length=5)
      repo=
    GroupHead. local=7
    Curly. Greedy quantifier {1,2147483647}
      CharProperty.complement. S̄:
        Ctype. POSIX (US-ASCII): SPACE
      Node. Accept match
    GroupTail [71f111ba]. local=7, group=4. --[next]--> GroupTail [9c304c7]
    GroupTail [9c304c7]. local=4, group=0. --[next]--> Node [4ea5d7f2]
    Node. Accept match
  Node. Accept match
LastNode.
Node. Accept match

Ответ 2

Окончательный ответ:

Переместите эту функциональность (?:[^"]|"[^"]*")* в группу чередования с помощью другие.

Пример: https://ideone.com/YuVcMg

Его нельзя сломать!

Замечание - я заметил, что вы сказали, что удалили новую строку и закончили с помощью конец одной записи без разделителя между следующим,
как это request_category=apiapp=github

Это нормально, но эти регулярные выражения будут в основном ударять по нему, когда он попадает в \S+.

По этой причине лучше заменить \S+ на (?:(?!app=github)\S)+,
который не выполняется в следующем регулярном выражении. Ниже приведено следующее:

"(?s)app=github(?>\\s+user=(?<user>(?:(?!app=github)\\S)+)|\\s+repo=(?<repo>(?:(?!app=github)\\S)+)|\\s+remote_address=(?<ip>(?:(?!app=github)\\S)+)|\\s+now=\\\\?\"(?<time>(?:(?!app=github)\\S)+)\\+\\d\\d:\\d\\d\\\\?\"|\\s+url=\\\\?\"(?<url>(?:(?!app=github)\\S)+)\\\\?\"|\\s+referer=\\\\?\"(?<referer>(?:(?!app=github)\\S)+)\\\\?\"|\\s+status=(?<status>(?:(?!app=github)\\S)+)|\\s+elapsed=(?<elapsed>(?:(?!app=github)\\S)+)|\\s+request_method=(?<requestmethod>(?:(?!app=github)\\S)+)|\\s+created_at=\\\\?\"(?<createdat>(?:(?!app=github)\\S)+)[-+]\\d\\d:\\d\\d\\\\?\"|\\s+pull_request_id=(?<pullrequestid>\\d+)|\\s+at=(?<at>(?:(?!app=github)\\S)+)|\\s+fn=(?<fn>(?:(?!app=github)\\S)+)|\\s+method=(?<method>(?:(?!app=github)\\S)+)|\\s+current_user=(?<user2>(?:(?!app=github)\\S)+)|\\s+content_length=(?<contentlength>(?:(?!app=github)\\S)+)|\\s+request_category=(?<requestcategory>(?:(?!app=github)\\S)+)|\\s+controller=(?<controller>(?:(?!app=github)\\S)+)|\\s+action=(?<action>(?:(?!app=github)\\S)+)|\"[^\"]*\"|(?!app=github).)+"

И ссылка на этот пример: https://ideone.com/hdwufO

Regex

Raw:

(?s)app=github(?>\s+user=(?<user>\S+)|\s+repo=(?<repo>\S+)|\s+remote_address=(?<ip>\S+)|\s+now=\\?"(?<time>\S+)\+\d\d:\d\d\\?"|\s+url=\\?"(?<url>\S+)\\?"|\s+referer=\\?"(?<referer>\S+)\\?"|\s+status=(?<status>\S+)|\s+elapsed=(?<elapsed>\S+)|\s+request_method=(?<requestmethod>\S+)|\s+created_at=\\?"(?<createdat>\S+)[-+]\d\d:\d\d\\?"|\s+pull_request_id=(?<pullrequestid>\d+)|\s+at=(?<at>\S+)|\s+fn=(?<fn>\S+)|\s+method=(?<method>\S+)|\s+current_user=(?<user2>\S+)|\s+content_length=(?<contentlength>\S+)|\s+request_category=(?<requestcategory>\S+)|\s+controller=(?<controller>\S+)|\s+action=(?<action>\S+)|"[^"]*"|(?!app=github).)+

Строка:

"(?s)app=github(?>\\s+user=(?<user>\\S+)|\\s+repo=(?<repo>\\S+)|\\s+remote_address=(?<ip>\\S+)|\\s+now=\\\\?\"(?<time>\\S+)\\+\\d\\d:\\d\\d\\\\?\"|\\s+url=\\\\?\"(?<url>\\S+)\\\\?\"|\\s+referer=\\\\?\"(?<referer>\\S+)\\\\?\"|\\s+status=(?<status>\\S+)|\\s+elapsed=(?<elapsed>\\S+)|\\s+request_method=(?<requestmethod>\\S+)|\\s+created_at=\\\\?\"(?<createdat>\\S+)[-+]\\d\\d:\\d\\d\\\\?\"|\\s+pull_request_id=(?<pullrequestid>\\d+)|\\s+at=(?<at>\\S+)|\\s+fn=(?<fn>\\S+)|\\s+method=(?<method>\\S+)|\\s+current_user=(?<user2>\\S+)|\\s+content_length=(?<contentlength>\\S+)|\\s+request_category=(?<requestcategory>\\S+)|\\s+controller=(?<controller>\\S+)|\\s+action=(?<action>\\S+)|\"[^\"]*\"|(?!app=github).)+"

Отформатирован:

 (?s)
 app = github
 (?>
      \s+ 
      user =
      (?<user> \S+ )                # (1)
   |  
      \s+  repo =
      (?<repo> \S+ )                # (2)
   |  
      \s+ remote_address =
      (?<ip> \S+ )                  # (3)
   |  
      \s+ now= \\? "
      (?<time> \S+ )                # (4)
      \+ \d\d : \d\d \\? "
   |  
      \s+ url = \\? "
      (?<url> \S+ )                 # (5)
      \\? "
   |  
      \s+ referer = \\? "
      (?<referer> \S+ )             # (6)
      \\? "
   |  
      \s+ status =
      (?<status> \S+ )              # (7)
   |  
      \s+ elapsed =
      (?<elapsed> \S+ )             # (8)
   |  
      \s+ request_method =
      (?<requestmethod> \S+ )       # (9)
   |  
      \s+ created_at = \\? "
      (?<createdat> \S+ )           # (10)
      [-+] 
      \d\d : \d\d \\? "
   |  
      \s+ pull_request_id =
      (?<pullrequestid> \d+ )       # (11)
   |  
      \s+ at=
      (?<at> \S+ )                  # (12)
   |  
      \s+ fn=
      (?<fn> \S+ )                  # (13)
   |  
      \s+ method =
      (?<method> \S+ )              # (14)
   |  
      \s+ current_user =
      (?<user2> \S+ )               # (15)
   |  
      \s+ content_length =
      (?<contentlength> \S+ )       # (16)
   |  
      \s+ request_categor y=
      (?<requestcategory> \S+ )     # (17)
   |  
      \s+ controller =
      (?<controller> \S+ )          # (18)
   |  
      \s+ action =
      (?<action> \S+ )              # (19)
   |  
      " [^"]* "                     # None of the above, give quotes a chance
   |  
      (?! app = github )            # Failsafe, consume a character, advance by 1
      . 
 )+