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

[Eli Zaretskii]

> Date: Sun, 19 Feb 2023 00:46:05 +0000
> From: Gregory Heytings <gregory@heytings.org>
> cc: "Mark A. Hershberger" <mah@everybody.org>, 61514@debbugs.gnu.org
> 
> > Interestingly, the following simple patch fixes both the original and 
> > the truncated cases:
> >
> > diff --git a/src/regex-emacs.c b/src/regex-emacs.c
> > index 2dca0d16ad9..eb943df46f0 100644
> > --- a/src/regex-emacs.c
> > +++ b/src/regex-emacs.c
> > @@ -877,7 +877,7 @@ #define INIT_FAILURE_ALLOC 20
> >    whose default stack limit is 2mb.  In order for a larger
> >    value to work reliably, you have to try to make it accord
> >    with the process stack limit.  */
> > -ptrdiff_t emacs_re_max_failures = 40000;
> > +ptrdiff_t emacs_re_max_failures = 37499;
> >
> > union fail_stack_elt
> > {
> >
> 
> After some further investigation, that's probably not TRT to do here. 
> With a file truncated to 100000 characters, the same bug happens with 
> emacs_re_max_failures >= 15000, and disappears with emacs_re_max_failures 
> <= 14999.  Hmmm...

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?

Maybe we should devise some mechanism whereby re_match_2_internal
forcibly returns a failure after too much bactracking (if that is what
happens here), when called from redisplay?

Stefan, any ideas?