Towards#5468. This extends the skip heuristic to the remaining unhandled assertions: word boundaries and lookahead assertions.

• The handling of word boundaries turns out to be much simpler in_Matcher2::_Skip() than in_Matcher2::_Is_wbound(), because we don't have to do any special handling for the start or end of the input string:_Skip() is never called for the start (or as the comment at the top says,--_First_arg is valid) and it cannot skip beyond the end of the input string (_Last) anyway. So we only have to handle the middle case and have to keep looking for the first position where the word character property changes (\b) or where it does not change (\B).
• For negative lookahead assertions, the easiest thing to do is to just ignore the assertion body (i.e., to assume that the assertion succeeds) and keep looking for a suitable node that can be used for skipping in the remainder of the main regex.
  • Keep in mind that_Skip() is just a heuristic, so it's fine if we don't exclude some non-matches. There is only one thing we must not do here: Skip something that could match.
• For positive lookahead assertions, we can look for the first place where the start of the assertion and the regex after the assertion both match.
  • Because this is implemented via recursion, I enforce a maximum recursion depth of 50 to prevent stack overflow. This limit is only reached by regexes that start with more than fifty positive lookahead assertions, so this should be more than enough for any practical regex. And the worst thing that happens if it is reached is that the optimization is (maybe only partially) disengaged.
  • While the code might look similar to the one that caused the quadratic slowdown in<regex>: Nonlinear slowdown with increasing string length #5452, this does not suffer from the same problem because we only move forward in the checks: If evaluating the start of the assertion body or the regex after the assertion body tells us that we should skip until position x, then we search next for the first possible position the other part of the regex matches starting from x. No position is evaluated more than once for the assertion and once for the remainder of the regex after the assertion, which implies a running time linear in the input.
• The skip heuristic now also continues evaluation beyond_N_endif nodes. (Nothing relevant happens at such nodes. They don't imply anything about the input string. Their only feature is that all the branches of an_N_if node join here again, but the problematic case is when branching happens, not when branches end.)
  • Because of<regex>: Avoid generating unnecessary single-branch_N_if nodes #5539, this doesn't actually make a difference if the current matcher and parser are combined. It can improve performance, though, when the current matcher evaluates an NFA generated by an old parser.

Tests

I added some tests for lookahead assertions. The tests useregex_replace() because it performs several searches into a single test call.

There already was test coverage for skipping of word boundaries inVSO_0000000_regex_use'stest_DDB_153116_replacements() function. But the test coverage had a gap: It didn't check for correct behavior if two (or more) non-word characters are next to each other. I closed this gap by adding some spaces to the existing tests.

Benchmark