Saxon

It does theoretically terminate, as can be established by trying it on a much shorter string. The problem is that the backtracking makes it exponential in the length of the string. That is, if matching a one-character string takes 1 microsecond, then matching a 137 character string takes 2^137 microseconds, which takes you well beyond the expected life of the solar system.

I'll have a look to see if there is an optimization that can be applied. An obvious one is to extract the precondition matches(., '\d{4}'), but that only helps for strings that don't match this precondition. On the other hand, a string that does match '\d{4}' will match quickly anyway, because the backtracking never kicks in.

The backtracking algorithm was rewritten in 9.6, largely to avoid exploding the amount of stack space needed rather than to reduce time. There's a space-time trade-off involved here and we may have swung too far the other way...

There's almost certainly a way of rewriting the regex that will perform much better. As far as I can see the leading pattern ^(\S+[\s,])+ matches every string that starts with a non-space character, that is, it's equivalent to ^\S. The problem is that a typical string matches the pattern in many different ways, and we are trying them all.

Another approach we could use here is to augment the "history" mechanism that we currently use to avoid looping when we try to match a zero-length string repeatedly at the same position. Again there's a bit of space-time tradeoff here, but if we were to remember the substrings that ^(\S+[\s,]*)+ has already matched, then we don't need to repeat the same match attempt during backtracking. But this might only work in cases where there's no need to remember the captured substrings.

For 9.7 I have added a system of preconditions to the regex matcher. In this particular case (regex='^(\S+[\s,]*)+\d{4}'), the pattern \d{4} is recognized as a precondition, and if this does not match somewhere in the input string, the entire regex returns false. This avoids the exponential backtracking that otherwise occurs in the non-matching case.

Marking this as "resolved" on the basis that improvements have been made in 9.7 which will benefit some cases including this particular one. No change for 9.6.

Bug fix went out in the 9.7 release only