Re: nnmail-split-header-length-limit is EVIL!

[Peter Seibel <peter@javamonkey.com>]

>>>>> "Dale" == Dale Hagglund <rdh@best.com> writes:

    Dale> Greg Stark <gsstark@mit.edu> writes:
    >> Could anyone actually explain why emacs has any trouble running a
    >> regexp over a few k of text? 

    Dale> As far as I know, this usually results from regexps that
    Dale> have lots of potential backtracking.  You end up with a
    Dale> situation where the match-time can be exponential in the
    Dale> length of the string being matched.

    Dale> I haven't seen any examples of complete regular expressions
    Dale> that cause the problems we're talking about here, but since
    Dale> they included at least some user-specified sub-regexps, it
    Dale> might be hard to address the problem from the regexp side.
    Dale> Do we have any known regexp/string pairs that deonstrate the
    Dale> problem?

Try eval'ing the expression below with the data line below it. It'll
run quickly as is. Then add a's on the end of one or two at a time and
watch it slow down. Seriously, don't add to many a's all at once or
you'll hang your emacs. C-g doesn't get it out--at least for me. But
the first few you add may not have any noticible effect--combinatorial
explosion never looks bad in the beginning.

(search-forward-regexp "\\(.*\\)*x")

xaaaaaa

The problem is that the * is greedy so after the . matches the 'x'
it'll match everything else in the line. Then the '.' doesn't match
the end of the line but eol isn't an 'x' either so the regex engine
backs up one from the end of the line and in the state of having
matched a bunch of stuff (everything except the last 'a' in the line)
with the '.*' inside the parens and having matched the whole
parenthesized pattern once, it then tries to finish matching by
matching the parenthesized expression twice which it can do by
matching the last 'a' with the second time through the parenthesized
expression. But it still fail to match an x (since it's now at the end
of the line) so it backtracks again, backing up one more character on
the first pass through and then matches the second time though,
matching two characters this time and then bombing out at when it hits
eol. That sort of backtracking and then matching forward and failing
goes on for quite a while until the whole thing succeeds by matching
zero characters zero times to satisfy the '\\(.*\\)*' and then matches
the 'x' satisfying the regex as a whole. The O'Reilly book, _Mastering
Regular Expressions_ by Jeffrey Friedl explains this sort of stuff
quite well. (He also wrote an article in The Perl Journal about this
particular problem of combinatorial explosions in regexps.

-Peter

-- 
Peter Seibel        Perl/Java/English Hacker        peter@javamonkey.com

  There's no good culture without a dash of bad taste; a monopoly of
  good taste suggests restraint -- you're not pushing the envelope.

                                        -- Jean-Louis Gassee