Mercurial > emacs
changeset 55736:c5ea37f370b5
(Regexp Special): Nested repetition can be infloop.
| author | Richard M. Stallman <rms@gnu.org> |
|---|---|
| date | Sat, 22 May 2004 22:05:57 +0000 |
| parents | 1874eee23678 |
| children | 2ac351855ad7 |
| files | lispref/searching.texi |
| diffstat | 1 files changed, 9 insertions(+), 7 deletions(-) [+] |
line wrap: on
line diff
--- a/lispref/searching.texi Sat May 22 22:04:56 2004 +0000 +++ b/lispref/searching.texi Sat May 22 22:05:57 2004 +0000 @@ -244,13 +244,15 @@ The next alternative is for @samp{a*} to match only two @samp{a}s. With this choice, the rest of the regexp matches successfully.@refill -Nested repetition operators can be extremely slow if they specify -backtracking loops. For example, it could take hours for the regular -expression @samp{\(x+y*\)*a} to try to match the sequence -@samp{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz}, before it ultimately fails. -The slowness is because Emacs must try each imaginable way of grouping -the 35 @samp{x}s before concluding that none of them can work. To make -sure your regular expressions run fast, check nested repetitions +Nested repetition operators can be extremely slow or loop infinitely +if they use repetition operators inside repetition operators. For +example, it could take hours for the regular expression +@samp{\(x+y*\)*a} to try to match the sequence +@samp{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz}, before it ultimately +fails. Emacs must try each way of grouping the 35 @samp{x}s before +concluding that none of them can work. Even worse, @samp{\(x*\)*} can +match the null string in infinitely many ways, so it causes an +infinite loop. To avoid these problems, check nested repetitions carefully. @item @samp{+}