From 0c26f14b7e200b39134ec70c77fab8c467cf3290 Mon Sep 17 00:00:00 2001 From: Stefan Monnier Date: Mon, 30 May 2016 23:22:49 -0400 Subject: * lisp/emacs-lisp/autoload.el: Use radix-tree. (autoload--make-defs-autoload): Rewrite. (autoload--split-prefixes-1): Remove. (autoload-def-prefixes-max-entries): Rename from autoload-defs-autoload-max-size. (autoload-popular-prefixes): Remove. (autoload-def-prefixes-max-length): New const. * lisp/emacs-lisp/radix-tree.el: New file. --- lisp/emacs-lisp/autoload.el | 86 +++++++++++++++++---------------------------- 1 file changed, 32 insertions(+), 54 deletions(-) (limited to 'lisp/emacs-lisp/autoload.el') diff --git a/lisp/emacs-lisp/autoload.el b/lisp/emacs-lisp/autoload.el index 11316f1d9d6..afd8e4ee03e 100644 --- a/lisp/emacs-lisp/autoload.el +++ b/lisp/emacs-lisp/autoload.el @@ -500,41 +500,26 @@ Return non-nil in the case where no autoloads were added at point." (let ((generated-autoload-file buffer-file-name)) (autoload-generate-file-autoloads file (current-buffer)))) -(defun autoload--split-prefixes-1 (strs) - (let ((prefixes ())) - (dolist (str strs) - (string-match "\\`[^-:/_]*[-:/_]*" str) - (let* ((prefix (match-string 0 str)) - (tail (substring str (match-end 0))) - (cell (assoc prefix prefixes))) - (cond - ((null cell) (push (list prefix tail) prefixes)) - ((equal (cadr cell) tail) nil) - (t (setcdr cell (cons tail (cdr cell))))))) - prefixes)) - (defvar autoload-compute-prefixes t "If non-nil, autoload will add code to register the prefixes used in a file. Standard prefixes won't be registered anyway. I.e. if a file \"foo.el\" defines variables or functions that use \"foo-\" as prefix, that will not be registered. But all other prefixes will be included.") -(defconst autoload-defs-autoload-max-size 5 +(defconst autoload-def-prefixes-max-entries 5 "Target length of the list of definition prefixes per file. If set too small, the prefixes will be too generic (i.e. they'll use little memory, we'll end up looking in too many files when we need a particular prefix), and if set too large, they will be too specific (i.e. they will cost more memory use).") -(defvar autoload-popular-prefixes nil) +(defconst autoload-def-prefixes-max-length 12 + "Target size of definition prefixes. +Don't try to split prefixes that are already longer than that.") + +(require 'radix-tree) (defun autoload--make-defs-autoload (defs file) - ;; FIXME: avoid redundant entries. E.g. opascal currently has - ;; "opascal-" "opascal--literal-start-re" "opascal--syntax-propertize" - ;; where only the first one should be kept. - ;; FIXME: Avoid keeping too-long-prefixes. E.g. ob-scheme currently has - ;; "org-babel-scheme-" "org-babel-default-header-args:scheme" - ;; "org-babel-expand-body:scheme" "org-babel-execute:scheme". ;; Remove the defs that obey the rule that file foo.el (or ;; foo-mode.el) uses "foo-" as prefix. @@ -548,39 +533,32 @@ cost more memory use).") ;; Then compute a small set of prefixes that cover all the ;; remaining definitions. - (let ((prefixes (autoload--split-prefixes-1 defs)) - (again t)) - ;; (message "Initial prefixes %s : %S" file (mapcar #'car prefixes)) - (while again - (setq again nil) - (let ((newprefixes - (sort - (mapcar (lambda (cell) - (cons cell - (autoload--split-prefixes-1 (cdr cell)))) - prefixes) - (lambda (x y) (< (length (cdr x)) (length (cdr y))))))) - (setq prefixes nil) - (while newprefixes - (let ((x (pop newprefixes))) - (if (or (equal '("") (cdar x)) - (and (cddr x) - (not (member (caar x) - autoload-popular-prefixes)) - (> (+ (length prefixes) (length newprefixes) - (length (cdr x))) - autoload-defs-autoload-max-size))) - ;; Nothing to split or would split too deep. - (push (car x) prefixes) - ;; (message "Expand %S to %S" (caar x) (cdr x)) - (setq again t) - (setq prefixes - (nconc (mapcar (lambda (cell) - (cons (concat (caar x) - (car cell)) - (cdr cell))) - (cdr x)) - prefixes))))))) + (let* ((tree (let ((tree radix-tree-empty)) + (dolist (def defs) + (setq tree (radix-tree-insert tree def t))) + tree)) + (prefixes (list (cons "" tree)))) + (while + (let ((newprefixes nil) + (changes nil)) + (dolist (pair prefixes) + (let ((prefix (car pair))) + (if (or (> (length prefix) autoload-def-prefixes-max-length) + (radix-tree-lookup (cdr pair) "")) + ;; No point splitting it any further. + (push pair newprefixes) + (setq changes t) + (radix-tree-iter-subtrees + (cdr pair) (lambda (sprefix subtree) + (push (cons (concat prefix sprefix) subtree) + newprefixes)))))) + (and changes + (or (and (null (cdr prefixes)) (equal "" (caar prefixes))) + (<= (length newprefixes) + autoload-def-prefixes-max-entries)) + (setq prefixes newprefixes) + (< (length prefixes) autoload-def-prefixes-max-entries)))) + ;; (message "Final prefixes %s : %S" file (mapcar #'car prefixes)) (when prefixes `(if (fboundp 'register-definition-prefixes) -- cgit v1.2.3 From 01030eed9395f5004e7d0721394697d1ca90cc2f Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Mon, 30 May 2016 23:19:54 -0700 Subject: ; Spelling fixes --- lisp/emacs-lisp/autoload.el | 2 +- lisp/emacs-lisp/radix-tree.el | 2 +- lisp/net/tramp-gvfs.el | 2 +- lisp/net/tramp-sh.el | 2 +- 4 files changed, 4 insertions(+), 4 deletions(-) (limited to 'lisp/emacs-lisp/autoload.el') diff --git a/lisp/emacs-lisp/autoload.el b/lisp/emacs-lisp/autoload.el index afd8e4ee03e..424b8e31936 100644 --- a/lisp/emacs-lisp/autoload.el +++ b/lisp/emacs-lisp/autoload.el @@ -967,7 +967,7 @@ write its autoloads into the specified file instead." t files-re)) dirs))) (done ()) ;Files processed; to remove duplicates. - (changed nil) ;Non-nil if some change occured. + (changed nil) ;Non-nil if some change occurred. (last-time) ;; Files with no autoload cookies or whose autoloads go to other ;; files because of file-local autoload-generated-file settings. diff --git a/lisp/emacs-lisp/radix-tree.el b/lisp/emacs-lisp/radix-tree.el index a6984b8034c..d4b5cd211e4 100644 --- a/lisp/emacs-lisp/radix-tree.el +++ b/lisp/emacs-lisp/radix-tree.el @@ -38,7 +38,7 @@ ;; of array, so every level's lookup is O(N) rather than O(1). We could easily ;; solve this by using char-tables instead of alists, but that would make every ;; level take up a lot more memory, and it would make the resulting -;; datastructure harder to read (by a human) when printed out. +;; data structure harder to read (by a human) when printed out. ;;; Code: diff --git a/lisp/net/tramp-gvfs.el b/lisp/net/tramp-gvfs.el index 96773928068..ac390e5d5a6 100644 --- a/lisp/net/tramp-gvfs.el +++ b/lisp/net/tramp-gvfs.el @@ -410,7 +410,7 @@ Every entry is a list (NAME ADDRESS).") (defconst tramp-gvfs-file-attributes '("type" "standard::display-name" - ;; We don't need this one. It is used as delimeter in case the + ;; We don't need this one. It is used as delimiter in case the ;; display name contains spaces, which is hard to parse. "standard::icon" "standard::symlink-target" diff --git a/lisp/net/tramp-sh.el b/lisp/net/tramp-sh.el index bfa3cc62ae2..e9f78b7d1ce 100644 --- a/lisp/net/tramp-sh.el +++ b/lisp/net/tramp-sh.el @@ -4717,7 +4717,7 @@ connection if a previous connection has died for some reason." (options (tramp-ssh-controlmaster-options vec)) (process-connection-type tramp-process-connection-type) (process-adaptive-read-buffering nil) - ;; There are unfortune settings for "cmdproxy" on + ;; There are unfortunate settings for "cmdproxy" on ;; W32 systems. (process-coding-system-alist nil) (coding-system-for-read nil) -- cgit v1.2.3