Java regex to match start/end tags causes stack overflow

Question

The standard implementation of the Java Pattern class uses recursion to implement many forms of regular expressions (e.g., certain operators, alternation).

This approach causes stack overflow issues with input strings that exceed a (relatively small) length, which may not even be more than 1,000 characters, depending on the regex involved.

A typical example of this is the following regex using alternation to extract a possibly multiline element (named Data) from a surrounding XML string, which has already been supplied:

<Data>(?<data>(?:.|\r|\n)+?)</Data>

The above regex is used in with the Matcher.find() method to read the "data" capturing group and works as expected, until the length of the supplied input string exceeds 1,200 characters or so, in which case it causes a stack overflow.

Can the above regex be rewritten to avoid the stack overflow issue?

You should not use regular expressions for parsing problems like XML. XML parsers are not hard to find. — user207421
– user207421, Commented Aug 10, 2016 at 21:32
Of course! We do use an XML parser, but before that we are doing some text pre-processing which is more complex than the example above. :-) — PNS
– PNS, Commented Aug 10, 2016 at 23:20

Wiktor Stribiżew · Accepted Answer · 2016-08-10 21:22:55Z

7

Some more details on the origin of the stack overflow issue:

Sometimes the regex Pattern class will throw a StackOverflowError. This is a manifestation of the known bug #5050507, which has been in the java.util.regex package since Java 1.4. The bug is here to stay because it has "won't fix" status. This error occurs because the Pattern class compiles a regular expression into a small program which is then executed to find a match. This program is used recursively, and sometimes when too many recursive calls are made this error occurs. See the description of the bug for more details. It seems it's triggered mostly by the use of alternations.

Your regex (that has alternations) is matching any 1+ characters between two tags.

You may either use a lazy dot matching pattern with the Pattern.DOTALL modifier (or the equivalent embedded flag (?s)) that will make the . match newline symbols as well:

(?s)<Data>(?<data>.+?)</Data>

See this regex demo

However, lazy dot matching patterns still consume lots of memory in case of huge inputs. The best way out is to use an unroll-the-loop method:

<Data>(?<data>[^<]*(?:<(?!/?Data>)[^<]*)*)</Data>

See the regex demo

Details:

<Data> - literal text <Data>
(?<data> - start of the capturing group "data"
- [^<]* - zero or more characters other than <
- (?:<(?!/?Data>)[^<]*)* - 0 or more sequences of:
  - <(?!/?Data>) - a < that is not followed with Data> or /Data>
  - [^<]* - zero or more characters other than <
) - end of the "data" group
</Data> - closing delimiter

edited Aug 10, 2016 at 21:22

answered Aug 10, 2016 at 21:03

Wiktor Stribiżew

631k41 gold badges502 silver badges632 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

PNS Over a year ago

Yes, there is no point having an alternation as per my example above, since \r and \n can be replaced by the (?s) directive. Both alternatives in your answer work as expected. Thanks and +1. :-)

Toby Over a year ago

I have the same problem with a far simpler regex: (.|\s)* can you explain how I'd avoid the SO pls? I'm trying to create a pattern to match any character including line terminators etc. Thx

Wiktor Stribiżew Over a year ago

@Toby Same as here. Or, just replace (.|\s)* with (?s:.*)

Toby Over a year ago

@WiktorStribiżew thanks, that worked a treat! I tried (?s)(.+?)* and it deferred the problem but larger input would still SO. Life saver!

Wiktor Stribiżew Over a year ago

@Toby You need to either use appropriate parser for your input (if it is (X)HTML or JSON, or similar), or make sure you unroll the lazy dot pattern.

Collectives™ on Stack Overflow

Java regex to match start/end tags causes stack overflow

1 Answer 1

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related