Re: Pattern bug on (a*|)~^(*b)

[Bart Schaefer <schaefer@xxxxxxxxxxxxxxxx>]

On Thu, Jul 27, 2023 at 11:41 PM Stephane Chazelas
<stephane@xxxxxxxxxxxx> wrote:
>
> I have to say I'm with the OP and don't understand that
> explanation either.

In the absence of a direct response from PWS, I'll just point you to
his comments in pattern.c, some of which date from before we had a git
repository:

 * The strategy is to test the asserted pattern,
 * recording via P_EXCSYNC how far the part to
 * be excluded matched.  We then set the
 * length of the test string to that
 * point and see if the exclusion as far as
 * P_EXCEND also matches that string.
 * We need to keep testing the asserted pattern
 * by backtracking, since the first attempt
 * may be excluded while a later attempt may not.
 * For this we keep a pointer just after
 * the P_EXCLUDE which is tested by the P_EXCSYNC
 * to see if we matched there last time, in which
 * case we fail.  If there is nothing to backtrack
 * over, that doesn't matter:  we should fail anyway.
 * The pointer also tells us where the asserted
 * pattern matched for use by the exclusion.

 * P.S. in case you were wondering, this code
 * is horrible.

 * This is where we make sure that we are not
 * repeatedly matching zero-length strings in
 * a closure, which would cause an infinite loop,
 * and also remove exponential behaviour in
 * backtracking nested closures.

 * If we come round to the same branch again, and
 * there is already a 1, then the test fails.

By my reading, zero-length matches may be short-circuited to avoid
pathological behavior.