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

[Stefan Monnier]

>> OK, thanks.  Stefan, do you have any further comments/objections on
>> that version?

LGTM.

> By the way, I noted that a variant of the regexp still produces stack
>  overflows:
>
> (with-current-buffer (get-buffer-create "*bug*")
>   (erase-buffer)
>   (insert (make-string 266665 ?x) "=")
>   (goto-char (point-min))
>   (looking-at "[^y]*=*"))
>
> 266665 overflows, 266664 does not.  Is that expected?

Yes, there's "nothing" we can do about it (short of a significant
redesign of the engine): [^y] also matches = so at every iteration of
the loop, both paths (perform one more iteration, or exit the loop) are
valid, so we need to try them both, which we do via backtracking.

We'd need a "Thompson NFA" or something along the same lines to avoid
it.

Of course, we could also just backtrack less deep by exploring the
search space in a different order (e.g. the `*?` repetition does that),
but if we want to still return the same end result, we'd then have to
explore more of the search space (and after the fact, choose which
match we should return) rather than stop at the first match.


        Stefan