Subject: bug#61514: 30.0.50; sadistically long xml line hangs emacs

From: Gregory Heytings <[email-masked]>
Date: Sun, 19 Feb 2023 23:48:57 +0000

>
> I'm not surprised.  There's something weird going on there.  Do you 
> understand the logic in this snippet near the end of 
> re_match_2_internal:
>
>    /* We goto here if a matching operation fails. */
>    fail:
>      maybe_quit ();
>      if (!FAIL_STACK_EMPTY ())
> 	{
> 	  [...]
> 	}
>      else
> 	break;   /* Matching at this starting point really fails.  */
>    } /* for (;;) */
>
>  if (best_regs_set)
>    goto restore_best_regs;
>
>  unbind_to (count, Qnil);
>  SAFE_FREE ();
>
>  if (max_redisplay_ticks > 0 && nchars > 0)
>    update_redisplay_ticks (nchars / 50 + 1, NULL);
>
>  return -1;				/* Failure to match.  */
>
> What is the mechanism to empty the failure stack, which eventually 
> causes us to report a failure?  What I see is that the stack is either 
> not being emptied, or being emptied very slowly.  Do the "magic" numbers 
> you came up with explain that?
>

As Stefan just said, it's POP_FAILURE_POINT which reduces the failure 
stack and restarts the search (if appropriate).

After more investigation (and trying to make sense of the magical 
numbers), my conclusion is that there is most probably no bug in the 
regexp engine, and that the sole culprit here is the regexp in nXML.  I 
truncated the file to only 10k characters: it opens after a few seconds. 
Then I added 10k characters at a time, and opening the file took more and 
more time, but eventually succeeded.  I stopped at 50k characters, where 
opening the file took something like two minutes.  By extrapolation, 
opening the file truncated to 250k characters should take a year or so ;-)

Lowering emacs_re_max_failures just makes the regexp engine fail earlier, 
because there is not enough room in the failure stack.  In a sense it is 
better to fail earlier, but to do that in all cases, we would have to 
lower emacs_re_max_failures say to 10000, which I guess wouldn't be good 
because the it would fail too much.