java - java Matcher中的零星堆栈溢出错误

标签 java regex

我有一些文件解析器代码，我偶尔会在 m.matches() (其中 m 是匹配器)上遇到堆栈溢出错误。

我再次运行我的应用程序，它解析同一个文件，没有堆栈溢出。

确实，我的模式有点复杂。它基本上是一堆可选的零长度正向前瞻，其中包含命名组，以便我可以匹配一堆变量名称/值对，而不管它们的顺序如何。但我希望如果某个字符串会导致堆栈溢出错误，它总是会导致它......不仅仅是有时......有什么想法吗？

我的模式的简化版本
"prefix(?=\\s+user=(?<user>\\S+))?(?=\\s+repo=(?<repo>\\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+))?.*?

Top of stack overflow error stack...(大概9800行长)
Exception: java.lang.StackOverflowError
    at java.util.regex.Pattern$BranchConn.match(Pattern.java:4480)
    at java.util.regex.Pattern$CharProperty.match(Pattern.java:3706)
    at java.util.regex.Pattern$Branch.match(Pattern.java:4516)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4570)
    at java.util.regex.Pattern$Loop.match(Pattern.java:4697)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4629)
    at java.util.regex.Pattern$BranchConn.match(Pattern.java:4480)
    at java.util.regex.Pattern$CharProperty.match(Pattern.java:3706)
    at java.util.regex.Pattern$Branch.match(Pattern.java:4516)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4570)
    at java.util.regex.Pattern$Loop.match(Pattern.java:4697)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4629)
    at java.util.regex.Pattern$BranchConn.match(Pattern.java:4480)
    at java.util.regex.Pattern$CharProperty.match(Pattern.java:3706)
    at java.util.regex.Pattern$Branch.match(Pattern.java:4516)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4570)
    at java.util.regex.Pattern$Loop.match(Pattern.java:4697)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4629)
    at java.util.regex.Pattern$BranchConn.match(Pattern.java:4480)
    at java.util.regex.Pattern$CharProperty.match(Pattern.java:3706)
    at java.util.regex.Pattern$Branch.match(Pattern.java:4516)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4570)
    at java.util.regex.Pattern$Loop.match(Pattern.java:4697)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4629)
    at java.util.regex.Pattern$BranchConn.match(Pattern.java:4480)
    at java.util.regex.Pattern$CharProperty.match(Pattern.java:3706)
    at java.util.regex.Pattern$Branch.match(Pattern.java:4516)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4570)
    at java.util.regex.Pattern$Loop.match(Pattern.java:4697)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4629)
    at java.util.regex.Pattern$BranchConn.match(Pattern.java:4480)
    at java.util.regex.Pattern$CharProperty.match(Pattern.java:3706)
    at java.util.regex.Pattern$Branch.match(Pattern.java:4516)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4570)
    at java.util.regex.Pattern$Loop.match(Pattern.java:4697)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4629)
    at java.util.regex.Pattern$BranchConn.match(Pattern.java:4480)
    at java.util.regex.Pattern$CharProperty.match(Pattern.java:3706)
    at java.util.regex.Pattern$Branch.match(Pattern.java:4516)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4570)
    at java.util.regex.Pattern$Loop.match(Pattern.java:4697)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4629)

我出错的行示例。 (虽然我已经运行了 10 次并且没有出现任何错误)
app=github env=production enterprise=true auth_fingerprint=\"token:6b29527b:9.99.999.99\" controller=\"Api::GitCommits\" path_info=\"/api/v3/repos/XYZ-ABCDE/abcdefg-abc/git/commits/77ae1376f969059f5f1e23cc5669bff8cca50563.diff\" query_string=nil version=v3 auth=oauth current_user=abcdefghijk oauth_access_id=24 oauth_application_id=0 oauth_scopes=\"gist,notifications,repo,user\" route=\"/repositories/:repository_id/git/commits/:id\" org=XYZ-ABCDE oauth_party=personal repo=XYZ-ABCDE/abcdefg-abc repo_visibility=private now=\"2015-09-24T13:44:52+00:00\" request_id=675fa67e-c1de-4bfa-a965-127b928d427a server_id=c31404fc-b7d0-41a1-8017-fc1a6dce8111 remote_address=9.99.999.99 request_method=get content_length=92 content_type=\"application/json; charset=utf-8\" user_agent=nil accept=application/json language=nil referer=nil x_requested_with=nil status=404 elapsed=0.041 url=\"https://git.abc.abcd.abc.com/api/v3/repos/XYZ-ABCDE/abcdefg-abc/git/commits/77ae1376f969059f5f1e23cc5669bff8cca50563.diff\" worker_request_count=77192 request_category=apiapp=github env=production enterprise=true auth_fingerprint=\"token:6b29527b:9.99.999.99\" controller=\"Api::GitCommits\" path_info=\"/api/v3/repos/XYZ-ABCDE/abcdefg-abc/git/commits/9bee255c7b13c589f4e9f1cb2d4ebb5b8519ba9c.diff\" query_string=nil version=v3 auth=oauth current_user=abcdefghijk oauth_access_id=24 oauth_application_id=0 oauth_scopes=\"gist,notifications,repo,user\" route=\"/repositories/:repository_id/git/commits/:id\" org=XYZ-ABCDE oauth_party=personal repo=XYZ-ABCDE/abcdefg-abc repo_visibility=private now=\"2015-09-24T13:44:52+00:00\" request_id=89fcb32e-9ab5-47f7-9464-e5f5cff175e8 server_id=1b74880a-5124-4483-adce-111b60dac111 remote_address=9.99.999.99 request_method=get content_length=92 content_type=\"application/json; charset=utf-8\" user_agent=nil accept=application/json language=nil referer=nil x_requested_with=nil status=404 elapsed=0.024 url=\"https://git.abc.abcd.abc.com/api/v3/repos/XYZ-ABCDE/abcdefg-abc/git/commits/9bee255c7b13c589f4e9f1cb2d4ebb5b8519ba9c.diff\" worker_request_count=76263 request_category=api

有趣的是...这行似乎是一个错误...日志似乎在错误的地方放了一个换行符，导致两个日志条目在一行上，然后是一个空行。正是这一长行导致了错误......无论如何一次......现在它运行良好而没有堆栈溢出

最佳答案

有两种方法可以解决您的问题:

  • 正确解析输入字符串并从 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 捕获/非捕获组(即子模式 (?:[^"]|"[^"]*")*)时，可能会发生这种情况。在你的情况下。

    1 这是Pattern 的源代码中使用的术语，这可能旨在指示模式具有固定长度。但是，实现考虑了交替|无论实际模式如何，都是不确定的。

    非确定性捕获/非捕获组的贪婪或懒惰重复被编译成 Loop/LazyLoop类，通过递归实现重复。因此，这种形态极易触发StackOverflowError ，尤其是当该组包含一次仅匹配一个字符的分支时。

    另一方面，确定性2重复、所有格重复、独立群重复(?>...) (又名原子组或非回溯组)被编译成 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

    关于java - java Matcher中的零星堆栈溢出错误，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32876288/

    上一篇：java - 如何检测Java中的电源溢出

    下一篇：Java 泛型 : Multiple Bounds

    相关文章：

    java - 在 Android 中的两个 Activity 之间来回发送数据

    java - 使用java将参数从flex传递到数据库

    python - 如何将确切的单词与正则表达式 python 匹配？

    python - 如何获取正则表达式来捕获 "x dollar(s) and x cents"？

    .net - 使用 Powershell 正则表达式查找 PHP 字符串，例如 "<?php eval "

    javascript - 替换javascript中所有出现的包含特殊字符的字符串

    java - Java中如何检测字符串中是否包含emoji？

    java - 为什么 hasNext() 不会变成 false？

    java - 如何使用Java API将配置单元字符串查询转换为抽象语法树？

    r - 使用 R 中的 str_count 计算整个单词/数字的出现次数

    ©2024 IT工具网  联系我们