Saxon

Thanks for submitting this.

All regular expression evaluators "go exponential" in some worst cases involving extreme amounts of backtracking, but with some algorithms the "worst cases" arise more frequently than others. Some algorithms punt on evaluating multiple branches in parallel, which tends to use more memory in simple cases but make it less likely that evaluation will take exponential time in more complex cases.

We've put some effort over the years into eliminating some of these problems in the Saxon regex engine (which is derived from the Apache Jakarta engine) but we're fully aware it's not the world's best regex engine. For cases it doesn't handle well, it's worth trying the switch to use the standard JDK regex engine instead (add ";j" to the flags argument). Of course, that way, the regex semantics are no longer conformant with the XPath rules.

I'll take a look at this example, but it's so complex that it may be very difficult to work out exactly what's going on.

Very often it's not really the complexity of the regex that's the problem, but the size of the input. Even quite simple regular expressions can have performance that's exponential in the size of the input.

Thanks for the thoughts, Michael. Last night (after posting this) I tried to run the entire 5900 test file and (even with -Xmx6g) java (in particular, “OpenJDK Runtime Environment (8.0_212-b03) (build 1.8.0_212-8u212-b03-0ubuntu1.16.04.1-b03)” ran out of memory.

I can try changing the regex to use Java rules and using ':j', but probably shouldn’t spend time on that until some other projects are finished.

You will find it much easier to read and understand what the regex is doing if you read instead the source code that generated it: https://github.com/NEU-DSG/wwp-public-code-share/blob/master/tagsDecl/CSS3_selector_regex_generator.perl. But note that this is just a sketch of the actual intended program (which I have not written yet), so please read it in the spirit of dirty laundry, as it were.

As for the complexity of regex vs size of input issue I really don’t know, but it does look like the out-of-memory issue mentioned above occurred on one of the impossible long test cases (about 80% through 1,025 of .span, )

No worries. If I come across a regexp that “explodes” but is more reasonable for humans, will let you know.