branch: scratch/editorconfig-wip commit 785be24cbdfc783840e3000fc578d794e01612b8 Author: Stefan Monnier <monn...@iro.umontreal.ca> Commit: Stefan Monnier <monn...@iro.umontreal.ca>
WiP: eliminate O(N^2) complexity in fnmatch translation --- editorconfig-fnmatch.el | 162 +++++++++++++++++++++++++----------------------- 1 file changed, 84 insertions(+), 78 deletions(-) diff --git a/editorconfig-fnmatch.el b/editorconfig-fnmatch.el index 520aeb16c2..cb793124e5 100644 --- a/editorconfig-fnmatch.el +++ b/editorconfig-fnmatch.el @@ -53,13 +53,9 @@ (require 'cl-lib) -(defvar editorconfig-fnmatch--cache-hashtable - nil +(defconst editorconfig-fnmatch--cache-hashtable + (make-hash-table :test 'equal) "Cache of shell pattern and its translation.") -;; Clear cache on file reload -(setq editorconfig-fnmatch--cache-hashtable - (make-hash-table :test 'equal)) - (defconst editorconfig-fnmatch--left-brace-regexp "\\(^\\|[^\\]\\){" @@ -128,7 +124,7 @@ translation is found for PATTERN." (length (length pattern)) (brace-level 0) (in-brackets nil) - ;; List of strings of resulting regexp + ;; List of strings of resulting regexp, in reverse order. (result ()) (is-escaped nil) (matching-braces (= (editorconfig-fnmatch--match-num @@ -141,8 +137,7 @@ translation is found for PATTERN." current-char pos has-slash - has-comma - num-range) + has-comma) (while (< index length) (if (and (not is-escaped) @@ -151,8 +146,8 @@ translation is found for PATTERN." pattern index) (eq index (match-beginning 0))) - (setq result `(,@result ,(regexp-quote (match-string 0 pattern))) - index (match-end 0) + (push (regexp-quote (match-string 0 pattern)) result) + (setq index (match-end 0) is-escaped nil) (setq current-char (aref pattern index) @@ -161,21 +156,23 @@ translation is found for PATTERN." (cl-case current-char (?* (setq pos index) - (if (and (< pos length) - (= (aref pattern pos) ?*)) - (setq result `(,@result ".*")) - (setq result `(,@result "[^/]*")))) + (push (if (and (< pos length) + (= (aref pattern pos) ?*)) + ".*" + "[^/]*") + result)) (?? - (setq result `(,@result "[^/]"))) + (push "[^/]" result)) (?\[ (if in-brackets - (setq result `(,@result "\\[")) + (push "\\[" result) (if (= (aref pattern index) ?/) ;; Slash after an half-open bracket - (setq result `(,@result "\\[/") - index (+ index 1)) + (progn + (setq index (+ index 1)) + (push "\\[/" result)) (setq pos index has-slash nil) (while (and (< pos length) @@ -186,28 +183,30 @@ translation is found for PATTERN." (setq has-slash t) (setq pos (1+ pos)))) (if has-slash - (setq result `(,@result ,(concat "\\[" - (substring pattern - index - (1+ pos)) - "\\]")) - index (+ pos 2)) - (if (and (< index length) - (memq (aref pattern index) - '(?! ?^))) - (setq index (1+ index) - result `(,@result "[^")) - (setq result `(,@result "["))) - (setq in-brackets t))))) + (progn + (push (concat "\\[" + (substring pattern + index + (1+ pos)) + "\\]") + result) + (setq index (+ pos 2))) + (setq in-brackets t) + (push (if (and (< index length) + (memq (aref pattern index) + '(?! ?^))) + (progn + (setq index (1+ index)) + "[^") + "[") + result))))) (?- - (if in-brackets - (setq result `(,@result "-")) - (setq result `(,@result "\\-")))) + (push (if in-brackets "-" "\\-") result)) (?\] - (setq result `(,@result "]") - in-brackets nil)) + (setq in-brackets nil) + (push "]" result)) (?{ (setq pos index @@ -223,62 +222,69 @@ translation is found for PATTERN." ?\\) (not is-escaped)) pos (1+ pos)))) - (if (and (not has-comma) - (< pos length)) - (let ((pattern-sub (substring pattern index pos))) - (setq num-range (string-match editorconfig-fnmatch--numeric-range-regexp - pattern-sub)) - (if num-range - (let ((number-start (string-to-number (match-string 1 - pattern-sub))) - (number-end (string-to-number (match-string 2 - pattern-sub)))) - (setq result `(,@result ,(concat "\\(?:" - (mapconcat #'number-to-string - (cl-loop for i from number-start to number-end - collect i) - "\\|") - "\\)")))) - (let ((inner (editorconfig-fnmatch--do-translate pattern-sub t))) - (setq result `(,@result ,(format "{%s}" inner))))) - (setq index (1+ pos))) - (if matching-braces - (setq result `(,@result "\\(?:") - brace-level (1+ brace-level)) - (setq result `(,@result "{"))))) + (push (if (and (not has-comma) + (< pos length)) + (let* ((pattern-sub (substring pattern index pos)) + (num-range (string-match editorconfig-fnmatch--numeric-range-regexp + pattern-sub))) + (setq index (1+ pos)) + (if num-range + (let ((number-start (string-to-number (match-string 1 + pattern-sub))) + (number-end (string-to-number (match-string 2 + pattern-sub)))) + (concat "\\(?:" + (mapconcat #'number-to-string + (cl-loop for i from number-start to number-end + collect i) + "\\|") + "\\)")) + (let ((inner (editorconfig-fnmatch--do-translate pattern-sub t))) + (format "{%s}" inner)))) + (if matching-braces + (progn + (setq brace-level (1+ brace-level)) + "\\(?:") + "{")) + result)) (?, - (if (and (> brace-level 0) - (not is-escaped)) - (setq result `(,@result "\\|")) - (setq result `(,@result "\\,")))) + (push (if (and (> brace-level 0) + (not is-escaped)) + "\\|" + "\\,") + result)) (?} - (if (and (> brace-level 0) - (not is-escaped)) - (setq result `(,@result "\\)") - brace-level (- brace-level 1)) - (setq result `(,@result "}")))) + (push (if (and (> brace-level 0) + (not is-escaped)) + (progn + (setq brace-level (- brace-level 1)) + "\\)") + "}") + result)) (?/ - (if (and (<= (+ index 3) (length pattern)) - (string= (substring pattern index (+ index 3)) "**/")) - (setq result `(,@result "\\(?:/\\|/.*/\\)") - index (+ index 3)) - (setq result `(,@result "/")))) + (push (if (and (<= (+ index 3) (length pattern)) + (string= (substring pattern index (+ index 3)) "**/")) + (progn + (setq index (+ index 3)) + "\\(?:/\\|/.*/\\)") + "/") + result)) (t (unless (= current-char ?\\) - (setq result `(,@result ,(regexp-quote (char-to-string current-char))))))) + (push (regexp-quote (char-to-string current-char)) result)))) (if (= current-char ?\\) (progn (when is-escaped - (setq result `(,@result "\\\\"))) + (push "\\\\" result)) (setq is-escaped (not is-escaped))) (setq is-escaped nil)))) (unless nested - (setq result `("^" ,@result "\\'"))) - (apply #'concat result))) + (setq result `("\\'" ,@result "\\`"))) + (apply #'concat (nreverse result)))) (provide 'editorconfig-fnmatch) ;;; editorconfig-fnmatch.el ends here