那些遇到过的问题

java Matcher中的偶发堆栈溢出错误

Ben*_*Ben 13 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+))?.*?
Run Code Online (Sandbox Code Playgroud)

栈顶溢出错误堆栈...(大约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)
Run Code Online (Sandbox Code Playgroud)

我遇到错误的行示例.(虽然我已经运行了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
Run Code Online (Sandbox Code Playgroud)

有趣的是...这一行似乎是一个错误...日志似乎在一个错误的位置放置一个换行符导致两个日志条目在一行上后跟一个空行.正是这条长线引起了错误......好吧无论如何......现在它运行得很好没有堆栈溢出

nha*_*tdh 11

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

  • 正确解析输入字符串并从中获取键值Map.

    我强烈建议使用这种方法,因为代码会更清晰,我们不再需要观察输入大小的限制.

  • 修改现有的正则表达式可以大大减少导致实现缺陷的影响StackOverflowError.

解析输入字符串

您可以使用以下正则表达式解析输入字符串:

\G\s*+(\w++)=([^\s"]++|"[^"]*+")(?:\s++|$)
Run Code Online (Sandbox Code Playgroud)

  • 由于我写的模式不需要回溯,因此所有量词都被占有(*+而不是代替).*+++

  • 您可以找到基本正则表达式(\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;
}
Run Code Online (Sandbox Code Playgroud)

您可能希望根据您的要求取消引用值.

您还可以重写函数以传递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+))?");
Run Code Online (Sandbox Code Playgroud)

它遵循正则表达式的等效扩展(A|B)*→ A*(BA*)*.哪个用作A或B取决于它们的重复次数 - 无论哪个重复更多应该是A而另一个应该是B.

深入探讨实施

StackOverflowErrorin Pattern是一个已知问题,当您的模式包含重复的非确定性1捕获/非捕获组((?:[^"]|"[^"]*")*在您的情况下是子模式)时,可能会发生这种情况.

1这是源代码中使用的术语Pattern,可能是模式具有固定长度的指示符.但是,|无论实际模式如何,实现都认为交替是非确定性的.

将非确定性捕获/非捕获组的贪婪或惰性重复编译到Loop/ LazyLoopclasses中,其通过递归实现重复.因此,这种模式极易触发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
Run Code Online (Sandbox Code Playgroud)

  • 哇谢谢!非常完整和翔实的答案!我喜欢你喜欢的建议......更清洁,更灵活!我花了一段时间来弄清楚它是如何工作的...... [^"]*(？:"[^ \"]*"[^"]*)*...我很好奇......这样做了吗？防止递归的同样的事情？(？:[^"] ++ |"[^"]*")* (2认同)

归档时间：

查看次数：

843 次

最近记录：

10 年，8 月 前
为什么^(？:x + y){5} $的性能比^ x + yx + yx + yx + yx + y $慢 4
更多相关链接
相关归档
你如何断言在JUnit 4测试中抛出某个异常？ 1915
String,StringBuffer和StringBuilder 206
Boolean.valueOf()有时会产生NullPointerException 113
是否有一组用于测试字符编码问题的"Lorem ipsums"文件？ 84
Java:将字符串转换为ByteBuffer和来自ByteBuffer的字符串以及相关问题 79
如何从字符串中仅删除某些子字符串？ 18
我可以使用什么正则表达式来匹配以点十进制表示法表示的任何有效IP地址？ 9
正则表达式匹配10-14位数 9
jQuerys $ .trim(),bug还是编写不好？ 9
不区分大小写的正则表达式 8
难疑归档
撤消尚未推送的Git合并 3695
如何列出目录的所有文件？ 3474
使用Java创建内存泄漏 3076
为什么我不应该在PHP中使用mysql_*函数？ 2432
.NET中的decimal,float和double之间的区别？ 2015
如何生成随机字母数字字符串？ 1679
在Node.js中编写文件 1538
match_parent和fill_parent有什么区别？ 1371
为什么我需要一直做`--set-upstream`？ 1364
如何在Bash中将字符串转换为小写？ 1158