# HG changeset patch
# User Richard M. Stallman <rms@gnu.org>
# Date 1085263557 0
# Node ID c5ea37f370b503bfce27bf28b56c673404f5c546
# Parent  1874eee23678670c65a4531d96cc5eb8a94cb489
(Regexp Special): Nested repetition can be infloop.

diff -r 1874eee23678 -r c5ea37f370b5 lispref/searching.texi
--- 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{+}