[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[nongnu] elpa/editorconfig fbd078ad64: Eliminate some o n2 (#351)
|
From: |
ELPA Syncer |
|
Subject: |
[nongnu] elpa/editorconfig fbd078ad64: Eliminate some o n2 (#351) |
|
Date: |
Sun, 28 Jul 2024 15:59:49 -0400 (EDT) |
branch: elpa/editorconfig
commit fbd078ad647888c971abe3508dd0ba27fac97cb9
Author: monnier <monnier@iro.umontreal.ca>
Commit: GitHub <noreply@github.com>
Eliminate some o n2 (#351)
* (editorconfig-core-handle--parse-file): Streamline
* editorconfig-core-handle.el: Change copyright to the FSF since all
the contributors have signed the corresponding paperwork.
(editorconfig-core-handle--parse-file): Directly return
a `editorconfig-core-handle`; parse the buffer directly rather than
matching on strings extracted from the buffer; avoid O(N²) complexity
by constructing the lists in reverse and using `nreverse` at the end.
(editorconfig-core-handle): Simplify accordingly.
(editorconfig-core-handle--string-trim): Delete function, not used any more.
* (editorconfig-fnmatch-p): Speed up
* editorconfig-fnmatch.el: Change copyright to the FSF since all
the contributors have signed the corresponding paperwork.
(editorconfig-fnmatch-p): Remove autoload cookie since all users do
`require` anyway.
(editorconfig-fnmatch--do-translate): Push in reverse order and `reverse`
at the end to avoid the usual O(N²) complexity.
* (editorconfig-fnmatch--do-translate): Reduce redundancy
* editorconfig-fnmatch.el (editorconfig-fnmatch--do-translate):
Consolidate the `push`s outside of `cl-case`. Use `regexp-opt`.
* Fix 4 core-test failures
This fixes the failures I see in
155: semicolon_or_hash_in_property
156: backslashed_semicolon_or_hash_in_property
164: min_supported_key_length
165: min_supported_value_length
* editorconfig-core-handle.el (editorconfig-core-handle--parse-file):
Bump limits beyond the spec's minimum.
* editorconfig-core.el (editorconfig-core-get-properties): Sort the
result so it doesn't depend on arbitrary hash-table implementation choices.
* Update core-test submodule
---
core-test | 2 +-
editorconfig-core-handle.el | 127 +++++++++------------
editorconfig-core.el | 2 +-
editorconfig-fnmatch.el | 266 ++++++++++++++++++++++----------------------
4 files changed, 182 insertions(+), 215 deletions(-)
diff --git a/core-test b/core-test
index 48610d43b7..772112adb7 160000
--- a/core-test
+++ b/core-test
@@ -1 +1 @@
-Subproject commit 48610d43b7455af12195473377f93c4ceea654f5
+Subproject commit 772112adb7aec5fffedf869d0d5a54c8374a0547
diff --git a/editorconfig-core-handle.el b/editorconfig-core-handle.el
index 20f52a3b97..69eb45f06d 100644
--- a/editorconfig-core-handle.el
+++ b/editorconfig-core-handle.el
@@ -1,27 +1,29 @@
;;; editorconfig-core-handle.el --- Handle Class for EditorConfig File -*-
lexical-binding: t -*-
-;; Copyright (C) 2011-2024 EditorConfig Team
+;; Copyright (C) 2011-2024 Free Software Foundation, Inc.
;; Author: EditorConfig Team <editorconfig@googlegroups.com>
+;; Package: editorconfig
;; See
-;; https://github.com/editorconfig/editorconfig-emacs/graphs/contributors
-;; or the CONTRIBUTORS file for the list of contributors.
+;; https://github.com/editorconfig/editorconfig-emacs/graphs/contributors or
+;; https://github.com/editorconfig/editorconfig-emacs/blob/master/CONTRIBUTORS
+;; for the list of contributors.
;; This file is part of EditorConfig Emacs Plugin.
;; EditorConfig Emacs Plugin is free software: you can redistribute it and/or
;; modify it under the terms of the GNU General Public License as published by
-;; the Free Software Foundation, either version 3 of the License, or (at your
-;; option) any later version.
+;; the Free Software Foundation, either version 3 of the License, or
+;; (at your option) any later version.
;; EditorConfig Emacs Plugin is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
-;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
-;; Public License for more details.
+;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+;; See the GNU General Public License for more details.
-;; You should have received a copy of the GNU General Public License along with
-;; EditorConfig Emacs Plugin. If not, see <https://www.gnu.org/licenses/>.
+;; You should have received a copy of the GNU General Public License
+;; along with GNU Emacs. If not, see <https://www.gnu.org/licenses/>.
;;; Commentary:
@@ -75,8 +77,7 @@ Slots:
Last modified time of .editorconfig file.
`path'
- Absolute path to .editorconfig file.'
-"
+ Absolute path to .editorconfig file."
(top-props nil)
(sections nil)
(mtime nil)
@@ -94,12 +95,7 @@ If CONF does not exist return nil."
(equal (editorconfig-core-handle-mtime cached) mtime))
cached
(let ((parsed (editorconfig-core-handle--parse-file conf)))
- (puthash conf
- (make-editorconfig-core-handle :top-props (plist-get parsed
:top-props)
- :sections (plist-get parsed
:sections)
- :mtime mtime
- :path conf)
- editorconfig-core-handle--cache-hash))))))
+ (puthash conf parsed editorconfig-core-handle--cache-hash))))))
(defun editorconfig-core-handle-root-p (handle)
"Return non-nil if HANDLE represent root EditorConfig file.
@@ -153,21 +149,10 @@ This function is a fnmatch with a few modification for
EditorConfig usage."
(or (editorconfig-fnmatch-p name pattern)
(editorconfig-fnmatch-p name (concat "**/" pattern)))))
-(defsubst editorconfig-core-handle--string-trim (str)
- "Remove leading and trailing whitespaces from STR."
- (replace-regexp-in-string "[[:space:]]+\\'"
- ""
- (replace-regexp-in-string "\\`[[:space:]]+"
- ""
- str)))
-
(defun editorconfig-core-handle--parse-file (conf)
"Parse EditorConfig file CONF.
-This function returns cons of its top properties alist and
-alist of patterns and its properties alist.
-The list returned will be ordered by the lines they appear.
-
+This function returns a `editorconfig-core-handle'.
If CONF is not found return nil."
(when (file-readable-p conf)
(with-temp-buffer
@@ -175,12 +160,9 @@ If CONF is not found return nil."
;; code conversion
(insert-file-contents conf)
(goto-char (point-min))
- (let ((point-max (point-max))
- (sections ())
+ (let ((sections ())
(top-props nil)
- ;; String of current line
- (line "")
;; nil when pattern not appeared yet, "" when pattern is empty
("[]")
(pattern nil)
;; Alist of properties for current PATTERN
@@ -188,58 +170,49 @@ If CONF is not found return nil."
;; Current line num
(current-line-number 1))
- (while (not (eq (point) point-max))
- (setq line
- (buffer-substring-no-properties (line-beginning-position)
- (line-end-position)))
- (setq line
- (replace-regexp-in-string "\\(^\\| \\)\\(#\\|;\\).*$"
- ""
-
(editorconfig-core-handle--string-trim line)))
-
+ (while (not (eobp))
+ (skip-chars-forward " \t\f")
(cond
- ((string-equal "" line)
+ ((looking-at "\\(?:[#;].*\\)?$")
nil)
;; Start of section
- ((string-match "^\\[\\(.*\\)\\]$"
- line)
- (when pattern
- (setq sections
- `(,@sections ,(make-editorconfig-core-handle-section
- :name pattern
- :props props)))
- (setq pattern nil)
- (setq props nil))
- (setq pattern (match-string 1 line)))
-
- (t
- (let ((idx (string-match "=\\|:" line)))
- (unless idx
- (error "Error while reading config file: %s:%d:\n %s\n"
- conf current-line-number line))
- (let ((key (downcase (editorconfig-core-handle--string-trim
- (substring line 0 idx))))
- (value (editorconfig-core-handle--string-trim
- (substring line (1+ idx)))))
- (when (and (< (length key) 51)
- (< (length value) 256))
- (if pattern
- (when (< (length pattern) 4097)
- (setq props
- `(,@props (,key . ,value))))
- (setq top-props
- `(,@top-props (,key . ,value)))))))))
+ ((looking-at "\\[\\(.*\\)\\][ \t]*$")
+ (let ((newpattern (match-string 1)))
+ (when pattern
+ (push (make-editorconfig-core-handle-section
+ :name pattern
+ :props (nreverse props))
+ sections))
+ (setq props nil)
+ (setq pattern newpattern)))
+
+ ((looking-at "\\([^=: \t]+\\)[ \t]*[=:][ \t]*\\(.*?\\)[ \t]*$")
+ (let ((key (downcase (match-string 1)))
+ (value (match-string 2)))
+ (if pattern
+ (push `(,key . ,value)
+ props)
+ (push `(,key . ,value)
+ top-props))))
+
+ (t (error "Error while reading config file: %s:%d:\n %s\n"
+ conf current-line-number
+ (buffer-substring-no-properties (line-beginning-position)
+ (line-end-position)))))
(setq current-line-number (1+ current-line-number))
(goto-char (point-min))
(forward-line (1- current-line-number)))
(when pattern
- (setq sections
- `(,@sections ,(make-editorconfig-core-handle-section
- :name pattern
- :props props))))
- (list :top-props top-props
- :sections sections)))))
+ (push (make-editorconfig-core-handle-section
+ :name pattern
+ :props (nreverse props))
+ sections))
+ (make-editorconfig-core-handle
+ :top-props (nreverse top-props)
+ :sections (nreverse sections)
+ :mtime (nth 5 (file-attributes conf))
+ :path conf)))))
(provide 'editorconfig-core-handle)
;;; editorconfig-core-handle.el ends here
diff --git a/editorconfig-core.el b/editorconfig-core.el
index c7b52deaaf..905084d0a5 100644
--- a/editorconfig-core.el
+++ b/editorconfig-core.el
@@ -112,7 +112,7 @@ look like (KEY . VALUE)."
(maphash (lambda (key value)
(add-to-list 'result (cons (symbol-name key) value)))
hash)
- result))
+ (sort result (lambda (x y) (string< (car x) (car y))))))
(defun editorconfig-core--hash-merge (into update)
"Merge two hashes INTO and UPDATE.
diff --git a/editorconfig-fnmatch.el b/editorconfig-fnmatch.el
index 520aeb16c2..a3edfc3c5d 100644
--- a/editorconfig-fnmatch.el
+++ b/editorconfig-fnmatch.el
@@ -1,27 +1,29 @@
-;;; editorconfig-fnmatch.el --- Glob pattern matching in Emacs lisp -*-
lexical-binding: t -*-
+;;; editorconfig-fnmatch.el --- Glob pattern matching -*- lexical-binding: t
-*-
-;; Copyright (C) 2011-2024 EditorConfig Team
+;; Copyright (C) 2011-2024 Free Software Foundation, Inc.
;; Author: EditorConfig Team <editorconfig@googlegroups.com>
+;; Package: editorconfig
;; See
-;; https://github.com/editorconfig/editorconfig-emacs/graphs/contributors
-;; or the CONTRIBUTORS file for the list of contributors.
+;; https://github.com/editorconfig/editorconfig-emacs/graphs/contributors or
+;; https://github.com/editorconfig/editorconfig-emacs/blob/master/CONTRIBUTORS
+;; for the list of contributors.
;; This file is part of EditorConfig Emacs Plugin.
;; EditorConfig Emacs Plugin is free software: you can redistribute it and/or
;; modify it under the terms of the GNU General Public License as published by
-;; the Free Software Foundation, either version 3 of the License, or (at your
-;; option) any later version.
+;; the Free Software Foundation, either version 3 of the License, or
+;; (at your option) any later version.
;; EditorConfig Emacs Plugin is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
-;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
-;; Public License for more details.
+;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+;; See the GNU General Public License for more details.
-;; You should have received a copy of the GNU General Public License along with
-;; EditorConfig Emacs Plugin. If not, see <https://www.gnu.org/licenses/>.
+;; You should have received a copy of the GNU General Public License
+;; along with GNU Emacs. If not, see <https://www.gnu.org/licenses/>.
;;; Commentary:
@@ -83,7 +85,6 @@
string (substring string (match-end 0))))
num))
-;;;###autoload
(defun editorconfig-fnmatch-p (string pattern)
"Test whether STRING match PATTERN.
@@ -128,7 +129,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
@@ -146,139 +147,132 @@ translation is found for PATTERN."
(while (< index length)
(if (and (not is-escaped)
- (string-match "[^]\\*?[{},/\\-]+"
+ (string-match "[^]\\*?[{},/-]+"
;;(string-match "[^]\\*?[{},/\\-]+" "?.a")
pattern
index)
(eq index (match-beginning 0)))
- (setq result `(,@result ,(regexp-quote (match-string 0 pattern)))
- index (match-end 0)
- is-escaped nil)
+ (progn
+ (push (regexp-quote (match-string 0 pattern)) result)
+ (setq index (match-end 0)
+ is-escaped nil))
(setq current-char (aref pattern index)
index (1+ index))
- (cl-case current-char
- (?*
- (setq pos index)
- (if (and (< pos length)
- (= (aref pattern pos) ?*))
- (setq result `(,@result ".*"))
- (setq result `(,@result "[^/]*"))))
-
- (??
- (setq result `(,@result "[^/]")))
-
- (?\[
- (if in-brackets
- (setq result `(,@result "\\["))
- (if (= (aref pattern index) ?/)
- ;; Slash after an half-open bracket
- (setq result `(,@result "\\[/")
- index (+ index 1))
- (setq pos index
- has-slash nil)
- (while (and (< pos length)
- (not (= (aref pattern pos) ?\]))
- (not has-slash))
- (if (and (= (aref pattern pos) ?/)
- (not (= (aref pattern (- pos 1)) ?\\)))
- (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)))))
-
- (?-
- (if in-brackets
- (setq result `(,@result "-"))
- (setq result `(,@result "\\-"))))
-
- (?\]
- (setq result `(,@result "]")
- in-brackets nil))
-
- (?{
- (setq pos index
- has-comma nil)
- (while (and (or (and (< pos length)
- (not (= (aref pattern pos) ?})))
- is-escaped)
- (not has-comma))
- (if (and (eq (aref pattern pos) ?,)
- (not is-escaped))
- (setq has-comma t)
- (setq is-escaped (and (eq (aref pattern pos)
- ?\\)
- (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 "{")))))
-
- (?,
- (if (and (> brace-level 0)
- (not is-escaped))
- (setq result `(,@result "\\|"))
- (setq result `(,@result "\\,"))))
-
- (?}
- (if (and (> brace-level 0)
- (not is-escaped))
- (setq result `(,@result "\\)")
- brace-level (- brace-level 1))
- (setq result `(,@result "}"))))
-
- (?/
- (if (and (<= (+ index 3) (length pattern))
- (string= (substring pattern index (+ index 3)) "**/"))
- (setq result `(,@result "\\(?:/\\|/.*/\\)")
- index (+ index 3))
- (setq result `(,@result "/"))))
-
- (t
- (unless (= current-char ?\\)
- (setq result `(,@result ,(regexp-quote (char-to-string
current-char)))))))
-
- (if (= current-char ?\\)
- (progn (when is-escaped
- (setq result `(,@result "\\\\")))
- (setq is-escaped (not is-escaped)))
- (setq is-escaped nil))))
+ (push
+ (cl-case current-char
+ (?*
+ (setq pos index)
+ (if (and (< pos length)
+ (= (aref pattern pos) ?*))
+ ".*"
+ "[^/]*"))
+
+ (?? "[^/]")
+
+ (?\[
+ (if in-brackets
+ "\\["
+ (if (= (aref pattern index) ?/)
+ ;; Slash after an half-open bracket
+ (progn
+ (setq index (+ index 1))
+ "\\[/")
+ (setq pos index
+ has-slash nil)
+ (while (and (< pos length)
+ (not (= (aref pattern pos) ?\]))
+ (not has-slash))
+ (if (and (= (aref pattern pos) ?/)
+ (not (= (aref pattern (- pos 1)) ?\\)))
+ (setq has-slash t)
+ (setq pos (1+ pos))))
+ (if has-slash
+ (let ((content (substring pattern index (1+ pos))))
+ (setq index (+ pos 2))
+ (concat "\\[" content "\\]"))
+ (setq in-brackets t)
+ (if (and (< index length)
+ (memq (aref pattern index)
+ '(?! ?^)))
+ (progn
+ (setq index (1+ index))
+ "[^")
+ "[")))))
+
+ (?- (if in-brackets "-" "\\-"))
+
+ (?\] (setq in-brackets nil) "]")
+
+ (?\{
+ (setq pos index
+ has-comma nil)
+ (while (and (or (and (< pos length)
+ (not (= (aref pattern pos) ?})))
+ is-escaped)
+ (not has-comma))
+ (if (and (eq (aref pattern pos) ?,)
+ (not is-escaped))
+ (setq has-comma t)
+ (setq is-escaped (and (eq (aref pattern pos)
+ ?\\)
+ (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))
+ (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))))
+ (regexp-opt
+ (mapcar #'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))
+ "\\(?:")
+ "{")))
+
+ (?,
+ (if (and (> brace-level 0)
+ (not is-escaped))
+ "\\|" "\\,"))
+
+ (?\}
+ (if (and (> brace-level 0)
+ (not is-escaped))
+ (progn
+ (setq brace-level (- brace-level 1))
+ "\\)")
+ "}"))
+
+ (?/
+ (if (and (<= (+ index 3) (length pattern))
+ (string= (substring pattern index (+ index 3)) "**/"))
+ (progn
+ (setq index (+ index 3))
+ "\\(?:/\\|/.*/\\)")
+ "/"))
+
+ (?\\ (when is-escaped "\\\\"))
+ (t (regexp-quote (char-to-string current-char))))
+ result)
+
+ (setq is-escaped (and (= current-char ?\\) (not is-escaped)))))
(unless nested
- (setq result `("^" ,@result "\\'")))
- (apply #'concat result)))
+ (setq result `("\\'" ,@result "\\`")))
+ (apply #'concat (reverse result))))
(provide 'editorconfig-fnmatch)
;;; editorconfig-fnmatch.el ends here
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [nongnu] elpa/editorconfig fbd078ad64: Eliminate some o n2 (#351),
ELPA Syncer <=