Warn about nested repetition.

1 files changed, 8 insertions, 0 deletions

diff --git a/lispref/searching.texi b/lispref/searching.texi
index 0de6b907771..ec082152aad 100644
--- a/lispref/searching.texi
+++ b/lispref/searching.texi
@@ -225,6 +225,14 @@ tries to match all three @samp{a}s; but the rest of the pattern is
 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, @samp{\(x+y*\)*a} could take hours to
+match the sequence @samp{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz}.  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
+carefully.
+
 @item +
 @cindex @samp{+} in regexp
 is a suffix operator similar to @samp{*} except that the preceding