[elpa] externals/xr 699521793d 6/7: Add check for repetition of effective repetition

[ELPA Syncer]

branch: externals/xr
commit 699521793d152d9966a8107caf1511ad8d47873b
Author: Mattias Engdegård <mattiase@acm.org>
Commit: Mattias Engdegård <mattiase@acm.org>

    Add check for repetition of effective repetition
    
    This finds a repeated sequences a single repetition along with things
    that match the empty string. For example, \(?:a*b+c?\)+ will match
    a sequence of 'b's but with terrible backtracking.
    Only enabled for checks = `all`.
---
 README     | 12 ++++++++++++
 xr-test.el |  4 ++++
 xr.el      | 19 ++++++++++++++++++-
 3 files changed, 34 insertions(+), 1 deletion(-)

diff --git a/README b/README
index 5a47cd510a..4399f71e7e 100644
--- a/README
+++ b/README
@@ -256,6 +256,18 @@ The xr package can be used interactively or by other code 
as a library.
     In general, A?, where A matches the empty string, can be
     simplified to just A.
 
+  - Repetition of effective repetition
+
+    A repetition construct is applied to an expression that itself
+    contains a repetition, in addition to some patterns that may match
+    the empty string. This can lead to bad matching performance.
+
+    Example: \(?:a*b+\)* is equivalent to the much faster \(?:a\|b\)* .
+
+    Another example: \(?:a*b+\)+ is better written a*b[ab]* .
+
+    This check is only enable when CHECKS=all.
+
   - Possibly mistyped ':?' at start of group
 
     A group starts as \(:? which makes it likely that it was really
diff --git a/xr-test.el b/xr-test.el
index fd60cb2b21..0cb3ae24b5 100644
--- a/xr-test.el
+++ b/xr-test.el
@@ -508,6 +508,10 @@
                 (10 . "Or-pattern more efficiently expressed as character 
alternative")
                 (23 . "Or-pattern more efficiently expressed as character 
alternative"))
             nil)))
+        (should (equal (xr-lint "\\(?:a?b+c?d*\\)*" nil checks)
+                       (if (eq checks 'all)
+                           '((14 . "Repetition of effective repetition"))
+                         nil)))
         ))))
 
 (ert-deftest xr-lint-repetition-of-empty ()
diff --git a/xr.el b/xr.el
index e7ede29080..cf90c56404 100644
--- a/xr.el
+++ b/xr.el
@@ -648,7 +648,24 @@ like (* (* X) ... (* X))."
                         (if (eq operator-char ??)
                             "Optional expression"
                           "Repetition of expression")
-                        " matching an empty string")))))
+                        " matching an empty string")))
+                     ((and (eq checks 'all)
+                           (memq operator-char '(?* ?+))
+                           (consp operand)
+                           (eq (car operand) 'seq)
+                           (let ((nonzero-items
+                                  (mapcan
+                                   (lambda (item)
+                                     (and (not (xr--matches-empty-p item))
+                                          (list item)))
+                                   (cdr operand))))
+                             (and (= (length nonzero-items) 1)
+                                  (consp (car nonzero-items))
+                                  (memq (caar nonzero-items)
+                                        '( opt zero-or-more one-or-more
+                                           +? *? ?? >=)))))
+                      (xr--report warnings item-start
+                                  "Repetition of effective repetition"))))
                   ;; (* (* X) ... (* X)) etc: wrap-around subsumption
                   (unless (eq operator-char ??)
                     (xr--check-wrap-around-repetition