Sporadic Stack Overflow error in java Matcher

Question

I have a some file parser code where I sporadically get stack overflow errors on m.matches() (where m is a Matcher).

I run my app again and it parses the same file with no stack overflow.

It's true my Pattern is a bit complex. It's basically a bunch of optional zero length positive lookaheads with named groups inside of them so that I can match a bunch of variable name/value pairs irregardless of their order. But I would expect that if some string would cause a stack overflow error it would always cause it... not just sometimes... any ideas?

A much simplified version of my Pattern "prefix(?=\\s+user=(?<user>\\S+))?(?=\\s+repo=(?<repo>\\S+))?.*?"

full regex is...

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... (it's about 9800 lines long)

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)

example of line I got error on. (Though I have run it 10 times since and not gotten any error)

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

interestingly... this line seems to be an error... the log seems to put a line break in the wrong place resulting in two log entries being on a single line followed by a blank line. It's this long line that caused the error... well once anyway... now it runs just fine without stack overflow

Does the regex work at all? Try (?s)prefix(?=.*\\s+user=(?<user>\\S+))(?=.*\\s+repo=(?<repo>\\S+)).You applied ? quantifier to lookaheads which is meaningless. .*? at the end does not match anything, just empty string. See this demo — Wiktor Stribiżew
Your simplified regex won't cause the issue in the question. Please post the real regex or a scaled down regex where the problem can be reproduced. — nhahtdh
@nhahtdh Full regex posted. Not sure you can reproduce easily... I parse 100,000+ lines just fine then it randomly dies with this error. Start it up it parses same line just fine. — Ben
@stribizhev Yes - the regex works almost all of the time exactly as desired. The .* is needed at the end... it matches EVERYTHING in the line basically... because none of the forward lookup's claim anything... and java requires that the WHOLE line be matched. The ? at the very end... you are right... not really needed... :-) but it will not work without the .*... try the code below... — Ben
Pattern p = Pattern.compile("(?=.*\\s+user=(?<user>\\S+))?"); Matcher m = p.matcher("user=username"); if (!m.matches()) { System.out.println("not matched without .* at the end"); } p = Pattern.compile("(?=.*\\s+user=(?<user>\\S+))?.*"); m = p.matcher("user=username"); if (m.matches()) { System.out.println(" matched with .* at the end"); } — Ben

nhahtdh nhahtdh · Accepted Answer · 2015-10-07T09:21:32

There are 2 ways to fix your problem:

Parse the input string properly and get the key values from the Map.

I strongly recommend using this method, since the code will be much cleaner, and we no longer have to watch the limit on the input size.
Modify the existing regex to greatly reduce the impact of the implementation flaw which causes StackOverflowError.

Parse the input string

You can parse the input string with the following regex:

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

All quantifiers are made possessive (*+ instead of *, ++ instead of +), since the pattern I wrote doesn't need backtracking.
You can find the basic regex (\w++)=([^\s"]++|"[^"]*+") to match key-value pairs in the middle.
\G is to make sure the match starts from where the last match leaves off. It is used to prevent the engine from "bump-along" when it fails to match.
\s*+ and (?:\s++|$) are for consuming excess spaces. I specify (?:\s++|$) instead of \s*+ to prevent key="value"key=value from being recognized as valid input.

The full example code can be found below:

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;
}

You might want to unquote the values, depending on your requirement.

You can also rewrite the function to pass a List of keys you want to extract, and pick them out in the while loop as you go to avoid storing keys that you don't care about.

Modify the regex

The problem is due to the outer repetition (?:[^"]|"[^"]*")* being implemented with recursion, leading to StackOverflowError when the input string is long enough.

Specifically, in each repetition, it matches either a quoted token, or a single non-quoted character. As a result, the stack grows linearly with the number of non-quoted characters and blows up.

You can replace all instance of (?:[^"]|"[^"]*")* with [^"]*(?:"[^"]*"[^"]*)*. The stack will now grow linearly as the number of quoted tokens, so StackOverflowError will not occur, unless you have thousands of quoted tokens in the input string.

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+))?");

It follows equivalent expansion of the regex (A|B)* → A*(BA*)*. Which to use as A or B depends on their number of repetitions - whichever repeats more should be A and the other should be B.

Deep diving into the implementation

StackOverflowError in Pattern is a known problem, which could happen when your pattern contains a repetition of a non-deterministic¹ capturing/non-capturing group, which is the subpattern (?:[^"]|"[^"]*")* in your case.

^{¹ This is a terminology used in the source code of Pattern, which is probably intended to be an indicator that the pattern has fixed length. However, the implementation considers alternation | to be non-deterministic, regardless of the actual pattern.}

Greedy or lazy repetition of a non-deterministic capturing/non-capturing group is compiled into Loop/LazyLoop classes, which implement repetition by recursion. As a result, such pattern is extremely prone to trigger StackOverflowError, especially when the group contains a branch where only a single character is matched at a time.

On the other hand, deterministic² repetition, possessive repetition, and repetition of independent group (?>...) (a.k.a. atomic group or non-backtracking group) are compiled into Curly/GroupCurly classes, which processes the repetition with loop in most cases, so there will be no StackOverflowError.

^{² The repeated pattern is a character class, or a fixed length capturing/non-capturing group without any alternation}

You can see how a fragment of your original regex is compiled below. Take note of the problematic part, which starts with Loop, and compare it to your stack trace.

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

Sporadic Stack Overflow error in java Matcher

2 Answers

Parse the input string

Modify the regex

Deep diving into the implementation