java Matcher中的偶发堆栈溢出错误
我有一些文件解析器代码，我偶尔会在m.matches（）上获得堆栈溢出错误（其中m是匹配器）。
我再次运行我的应用程序，它解析相同的文件，没有堆栈溢出。
这是真的我的模式有点复杂。 它基本上是一堆可选的零长度正向前瞻，其中包含命名组，因此我可以匹配一堆变量名称/值对，而不管它们的顺序如何。 但我希望如果某些字符串会导致堆栈溢出错误，那么它总是会导致它……不仅仅是有时……任何想法？
我的Pattern "prefix(?=\\s+user=(?\\S+))?(?=\\s+repo=(?\\S+))?.*?"简化版本"prefix(?=\\s+user=(?\\S+))?(?=\\s+repo=(?\\S+))?.*?"
完全正则表达式是……
app=github(?=(?:[^"]|"[^"]*")*\s+user=(?\S+))?(?=(?:[^"]|"[^"]*")*\s+repo=(?\S+))?(?=(?:[^"]|"[^"]*")*\s+remote_address=(?\S+))?(?=(?:[^"]|"[^"]*")*\s+now="(?\S+)\+\d\d:\d\d")?(?=(?:[^"]|"[^"]*")*\s+url="(?\S+)")?(?=(?:[^"]|"[^"]*")*\s+referer="(?\S+)")?(?=(?:[^"]|"[^"]*")*\s+status=(?\S+))?(?=(?:[^"]|"[^"]*")*\s+elapsed=(?\S+))?(?=(?:[^"]|"[^"]*")*\s+request_method=(?\S+))?(?=(?:[^"]|"[^"]*")*\s+created_at="(?\S+)(?:-|\+)\d\d:\d\d")?(?=(?:[^"]|"[^"]*")*\s+pull_request_id=(?\d+))?(?=(?:[^"]|"[^"]*")*\s+at=(?\S+))?(?=(?:[^"]|"[^"]*")*\s+fn=(?\S+))?(?=(?:[^"]|"[^"]*")*\s+method=(?\S+))?(?=(?:[^"]|"[^"]*")*\s+current_user=(?\S+))?(?=(?:[^"]|"[^"]*")*\s+content_length=(?\S+))?(?=(?:[^"]|"[^"]*")*\s+request_category=(?\S+))?(?=(?:[^"]|"[^"]*")*\s+controller=(?\S+))?(?=(?:[^"]|"[^"]*")*\s+action=(?\S+))?.*?
栈顶溢出错误堆栈…（大约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 parseKeyValue(String kvString) { Matcher matcher = KEY_VALUE.matcher(kvString); Map output = new HashMap(); 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=(?\\S+))?(?=[^\"]*(?:\"[^\"]*\"[^\"]*)*\\s+repo=(?\\S+))?(?=[^\"]*(?:\"[^\"]*\"[^\"]*)*\\s+remote_address=(?\\S+))?(?=[^\"]*(?:\"[^\"]*\"[^\"]*)*\\s+now=\"(?
它遵循正则表达式(A|B)* → A*(BA*)*等效扩展。 哪个用作A或B取决于它们的重复次数 – 无论哪个重复更多应该是A而另一个应该是B.
深入探讨实施
Pattern中的StackOverflowError是一个已知问题，当您的模式包含重复的非确定性 1捕获/非捕获组(?:[^"]|"[^"]*")*子模式(?:[^"]|"[^"]*")*时，可能会发生这种情况。 (?:[^"]|"[^"]*")*在你的情况下。
1这是Pattern的源代码中使用的术语， 可能是模式具有固定长度的指示符。 但是，实现考虑了交替| 无论实际模式如何，都是非确定性的。
将非确定性捕获/非捕获组的贪婪或惰性重复编译到Loop / LazyLoop类中，这些类通过递归实现重复。 因此，此类模式极易触发StackOverflowError ，尤其是当组包含一次只匹配单个字符的分支时。
另一方面， 确定性 2重复，占有重复和独立组重复(?>...) （又称primefaces组或非回溯组）被编译成Curly / GroupCurly类，它们在大多数情况下用循环处理重复case，所以不会有StackOverflowError 。
2重复模式是一个字符类，或固定长度的捕获/非捕获组，没有任何交替
您可以在下面看到如何编译原始正则表达式的片段。 记下以Loop开头的有问题的部分，并将其与堆栈跟踪进行比较。
app=github(?=(?:[^"]|"[^"]*")*\s+user=(?\S+))?(?=(?:[^"]|"[^"]*")*\s+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
最终答案：
将此(?:[^"]|"[^"]*")*function移动到一个交替组中
其他。
示例： https ： //ideone.com/YuVcMg
它无法破碎！
旁注 – 我注意到你说你删除了换行符并最终结束了
一条记录的末尾没有隔板之间的分隔符，
喜欢这个request_category=apiapp=github没关系，但这些正则表达式会在它击中时大部分被它击败
\S+。因此，最好用
(?:(?!app=github)\S)+替换\S+(?:(?!app=github)\S)+，
这不是在下面的正则表达式中完成的。 以下是添加的内容：
"(?s)app=github(?>\\s+user=(?(?:(?!app=github)\\S)+)|\\s+repo=(?(?:(?!app=github)\\S)+)|\\s+remote_address=(?(?:(?!app=github)\\S)+)|\\s+now=\\\\?\"(?
并使用它链接到该示例： https ： //ideone.com/hdwufO
正则表达式
生的：
(?s)app=github(?>\s+user=(?\S+)|\s+repo=(?\S+)|\s+remote_address=(?\S+)|\s+now=\\?"(?
弦：
"(?s)app=github(?>\\s+user=(?\\S+)|\\s+repo=(?\\S+)|\\s+remote_address=(?\\S+)|\\s+now=\\\\?\"(?
格式：
(?s) app = github (?> \s+ user = (? \S+ ) # (1) | \s+ repo = (? \S+ ) # (2) | \s+ remote_address = (? \S+ ) # (3) | \s+ now= \\? " (?