branch: externals/dict-tree commit 5834dacf871ba8b6f8ca0e99a4450cbdaee933a5 Author: Toby Cubitt <toby-predict...@dr-qubit.org> Commit: tsc25 <toby-predict...@dr-qubit.org>
Replaced bare avl-trees which were an ugly optimisation needed for efficiently printing and reading tries, with trie-transform-for-print and trie-transform-from-read functions. --- dict-tree.el | 537 +++++++++++++++++++++++++++++++---------------------------- 1 file changed, 279 insertions(+), 258 deletions(-) diff --git a/dict-tree.el b/dict-tree.el index b61387f..d8a4b3e 100644 --- a/dict-tree.el +++ b/dict-tree.el @@ -1428,24 +1428,24 @@ bind any variables with names commencing \"--\"." ;; try to avoid dynamic binding bugs (let ((--dictree--mapc--function function)) - ;; for a normal dictionary, map the function over its trie - (if (not (dictree--meta-dict-p dict)) - (trie-mapc - (lambda (key cell) - (funcall --dictree--mapc--function - key - (dictree--cell-data cell) - (dictree--cell-plist cell))) - (dictree--trie dict) - type reverse) - ;; for a meta-dict, use a dictree-stack - (let ((stack (dictree-stack dict)) - entry) - (while (setq entry (dictree--stack-pop stack)) - (funcall --dictree--mapc--function - (car entry) - (dictree--cell-data (cdr entry)) - (dictree--cell-plist (cdr entry))))) + (if (dictree--meta-dict-p dict) + ;; for a meta-dict, use a dictree-stack + (let ((stack (dictree-stack dict)) + entry) + (while (setq entry (dictree--stack-pop stack)) + (funcall --dictree--mapc--function + (car entry) + (dictree--cell-data (cdr entry)) + (dictree--cell-plist (cdr entry))))) + ;; for a normal dictionary, map the function over its trie + (trie-mapc + (lambda (key cell) + (funcall --dictree--mapc--function + key + (dictree--cell-data cell) + (dictree--cell-plist cell))) + (dictree--trie dict) + type reverse) ))) @@ -2038,13 +2038,12 @@ the compiled version will be created, whereas if it is the symbol (let (dictname buff tmpfile) ;; add .el(c) extension to the filename if not already there (cond + ;; remove .el(c) extension from filename ((string= (substring filename -3) ".el") (setq filename (substring filename 0 -3))) ((string= (substring filename -4) ".elc") (setq filename (substring filename 0 -4)))) - - ;; remove .el(c) extension from filename to create saved dictionary - ;; name + ;; create saved dictionary name from filename (setq dictname (file-name-nondirectory filename)) (save-excursion @@ -2054,8 +2053,8 @@ the compiled version will be created, whereas if it is the symbol (set-buffer buff) ;; call the appropriate write function to write the dictionary code (if (dictree--meta-dict-p dict) - (dictree--write-meta-dict-code dict dictname) - (dictree--write-dict-code dict dictname)) + (dictree--write-meta-dict-code dict dictname filename) + (dictree--write-dict-code dict dictname filename)) (save-buffer) (kill-buffer buff)) @@ -2092,6 +2091,7 @@ the compiled version will be created, whereas if it is the symbol ;; if writing to a different name, unload dictionary under old name and ;; reload it under new one (setf (dictree-modified dict) nil) + (setf (dictree--filename dict) filename) (unless (string= dictname (dictree-name dict)) (dictree-unload dict) (dictree-load filename))) @@ -2213,247 +2213,268 @@ NOT be saved even if its autosave flag is set." -(defun dictree--write-dict-code (dict dictname) +(defun dictree--write-dict-code (dict dictname filename) ;; Write code for normal dictionary DICT to current buffer, giving it the - ;; name DICTNAME. + ;; name DICTNAME and file FILENAME. (let (hashcode tmpdict tmptrie lookup-alist complete-alist complete-ranked-alist) ;; --- convert trie data --- - ;; if dictionary doesn't use any custom save functions, write dictionary's - ;; trie directly as is - (setq tmptrie (dictree--trie dict)) - ;; otherwise, create a temporary trie and populate it with the converted - ;; contents of the dictionary's trie - (when (or (dictree--data-savefun dict) (dictree--plist-savefun dict)) - (setq tmptrie - (trie-create-custom - (trie-comparison-function tmptrie) - :createfun (trie--createfun tmptrie) - :insertfun (trie--insertfun tmptrie) - :deletefun (trie--deletefun tmptrie) - :lookupfun (trie--lookupfun tmptrie) - :mapfun (trie--mapfun tmptrie) - :emptyfun (trie--emptyfun tmptrie) - :stack-createfun (trie--stack-createfun tmptrie) - :stack-popfun (trie--stack-popfun tmptrie) - :stack-emptyfun (trie--stack-emptyfun tmptrie))) - (trie-mapc - (lambda (key cell) - (trie-insert tmptrie key - (dictree--cell-create - (funcall (or (dictree--data-savefun dict) 'identity) - (dictree--cell-data cell)) - (funcall (or (dictree--plist-savefun dict) 'identity) - (dictree--cell-plist cell))))) - (dictree--trie dict))) - ;; generate code to convert contents of trie back to original form - (cond - ;; convert both data and plist - ((and (dictree--data-loadfun dict) (dictree--plist-loadfun dict)) - (setq hashcode - (concat - hashcode - "(trie-map\n" - " (lambda (key cell)\n" - " (dictree--cell-create\n" - " (funcall (dictree--data-loadfun " dictname ")\n" - " (dictree--cell-data cell))\n" - " (funcall (dictree--plist-loadfun " dictname ")\n" - " (dictree--cell-plist cell))))\n" - " (dictree--trie " dictname "))\n"))) - ;; convert only data - ((dictree--data-loadfun dict) - (setq hashcode - (concat - hashcode - "(trie-map\n" - " (lambda (key cell)\n" - " (dictree--cell-create\n" - " (funcall (dictree--data-loadfun " dictname ")\n" - " (dictree--cell-data cell))\n" - " (dictree--cell-plist cell)))\n" - " (dictree--trie " dictname "))\n"))) - ;; convert only plist - ((dictree--plist-loadfun dict) - (setq hashcode - (concat - hashcode - "(trie-map\n" - " (lambda (key cell)\n" - " (dictree--cell-create\n" - " (dictree--cell-data cell)\n" - " (funcall (dictree--plist-loadfun " dictname ")\n" - " (dictree--cell-plist cell))))\n" - " (dictree--trie " dictname "))\n")))) - - - ;; --- convert hash tables to alists --- - ;; convert lookup cache hash table to alist, if it exists - (when (dictree--lookup-cache-threshold dict) - (maphash - (lambda (key val) - (push - (cons key - (cons (mapcar 'car (dictree--cache-completions val)) - (dictree--cache-maxnum val))) - lookup-alist)) - (dictree--lookup-cache dict)) - ;; generate code to reconstruct the lookup hash table - (setq hashcode - (concat - hashcode - "(let ((lookup-cache (make-hash-table :test 'equal))\n" - " (trie (dictree--trie " dictname ")))\n" - " (mapc\n" - " (lambda (entry)\n" - " (puthash\n" - " (car entry)\n" - " (dictree--cache-create\n" - " (mapcar\n" - " (lambda (key)\n" - " (cons key (trie-member trie key)))\n" - " (dictree--cache-completions (cdr entry)))\n" - " (dictree--cache-maxnum (cdr entry)))\n" - " lookup-cache))\n" - " (dictree--lookup-cache " dictname "))\n" - " (setf (dictree--lookup-cache " dictname ")\n" - " lookup-cache))\n" - ))) - - ;; convert completion cache hash table to alist, if it exists - (when (dictree--complete-cache-threshold dict) - (maphash - (lambda (key val) - (push - (cons key - (cons (mapcar 'car (dictree--cache-completions val)) - (dictree--cache-maxnum val))) - complete-alist)) - (dictree-complete-cache dict)) - ;; generate code to reconstruct the completion hash table - (setq - hashcode - (concat - hashcode - "(let ((complete-cache (make-hash-table :test 'equal))\n" - " (trie (dictree--trie " dictname ")))\n" - " (mapc\n" - " (lambda (entry)\n" - " (puthash\n" - " (car entry)\n" - " (dictree--cache-create\n" - " (mapcar\n" - " (lambda (key)\n" - " (cons key (trie-member trie key)))\n" - " (dictree--cache-completions (cdr entry)))\n" - " (dictree--cache-maxnum (cdr entry)))\n" - " complete-cache))\n" - " (dictree--complete-cache " dictname "))\n" - " (setf (dictree--complete-cache " dictname ")\n" - " complete-cache))\n" - ))) - - ;; convert ranked completion cache hash table to alist, if it exists - (when (dictree--complete-ranked-cache-threshold dict) - (maphash - (lambda (key val) - (push - (cons key - (cons (mapcar 'car (dictree--cache-completions val)) - (dictree--cache-maxnum val))) - complete-ranked-alist)) - (dictree--complete-ranked-cache dict)) - ;; generate code to reconstruct the ordered hash table - (setq hashcode - (concat + ;; transform trie to print form + (trie-transform-for-print (dictree--trie dict)) + (unwind-protect + (progn + ;; if dictionary doesn't use any custom save functions, write + ;; dictionary's trie directly as is + (setq tmptrie (dictree--trie dict)) + ;; otherwise, create a temporary trie and populate it with the + ;; converted contents of the dictionary's trie + (when (or (dictree--data-savefun dict) + (dictree--plist-savefun dict)) + (setq tmptrie + (trie-create-custom + (trie-comparison-function tmptrie) + :createfun (trie--createfun tmptrie) + :insertfun (trie--insertfun tmptrie) + :deletefun (trie--deletefun tmptrie) + :lookupfun (trie--lookupfun tmptrie) + :mapfun (trie--mapfun tmptrie) + :emptyfun (trie--emptyfun tmptrie) + :stack-createfun (trie--stack-createfun tmptrie) + :stack-popfun (trie--stack-popfun tmptrie) + :stack-emptyfun (trie--stack-emptyfun tmptrie))) + (trie-mapc + (lambda (key cell) + (trie-insert tmptrie key + (dictree--cell-create + (funcall (or (dictree--data-savefun dict) + 'identity) + (dictree--cell-data cell)) + (funcall (or (dictree--plist-savefun dict) + 'identity) + (dictree--cell-plist cell))))) + (dictree--trie dict))) + ;; generate code to convert contents of trie back to original form + (cond + ;; convert both data and plist + ((and (dictree--data-loadfun dict) (dictree--plist-loadfun dict)) + (setq hashcode + (concat + hashcode + "(trie-map\n" + " (lambda (key cell)\n" + " (dictree--cell-create\n" + " (funcall (dictree--data-loadfun " dictname ")\n" + " (dictree--cell-data cell))\n" + " (funcall (dictree--plist-loadfun " dictname ")\n" + " (dictree--cell-plist cell))))\n" + " (dictree--trie " dictname "))\n"))) + ;; convert only data + ((dictree--data-loadfun dict) + (setq hashcode + (concat + hashcode + "(trie-map\n" + " (lambda (key cell)\n" + " (dictree--cell-create\n" + " (funcall (dictree--data-loadfun " dictname ")\n" + " (dictree--cell-data cell))\n" + " (dictree--cell-plist cell)))\n" + " (dictree--trie " dictname "))\n"))) + ;; convert only plist + ((dictree--plist-loadfun dict) + (setq hashcode + (concat + hashcode + "(trie-map\n" + " (lambda (key cell)\n" + " (dictree--cell-create\n" + " (dictree--cell-data cell)\n" + " (funcall (dictree--plist-loadfun " dictname ")\n" + " (dictree--cell-plist cell))))\n" + " (dictree--trie " dictname "))\n")))) + + + ;; --- convert hash tables to alists --- + ;; convert lookup cache hash table to alist, if it exists + (when (dictree--lookup-cache-threshold dict) + (maphash + (lambda (key val) + (push + (cons key + (cons (mapcar 'car (dictree--cache-completions val)) + (dictree--cache-maxnum val))) + lookup-alist)) + (dictree--lookup-cache dict)) + ;; generate code to reconstruct the lookup hash table + (setq hashcode + (concat + hashcode + "(let ((lookup-cache (make-hash-table :test 'equal))\n" + " (trie (dictree--trie " dictname ")))\n" + " (mapc\n" + " (lambda (entry)\n" + " (puthash\n" + " (car entry)\n" + " (dictree--cache-create\n" + " (mapcar\n" + " (lambda (key)\n" + " (cons key (trie-member trie key)))\n" + " (dictree--cache-completions (cdr entry)))\n" + " (dictree--cache-maxnum (cdr entry)))\n" + " lookup-cache))\n" + " (dictree--lookup-cache " dictname "))\n" + " (setf (dictree--lookup-cache " dictname ")\n" + " lookup-cache))\n" + ))) + + ;; convert completion cache hash table to alist, if it exists + (when (dictree--complete-cache-threshold dict) + (maphash + (lambda (key val) + (push + (cons key + (cons (mapcar 'car (dictree--cache-completions val)) + (dictree--cache-maxnum val))) + complete-alist)) + (dictree-complete-cache dict)) + ;; generate code to reconstruct the completion hash table + (setq hashcode - "(let ((complete-ranked-cache (make-hash-table :test 'equal))\n" - " (trie (dictree--trie " dictname ")))\n" - " (mapc\n" - " (lambda (entry)\n" - " (puthash\n" - " (car entry)\n" - " (dictree--cache-create\n" - " (mapcar\n" - " (lambda (key)\n" - " (cons key (trie-member trie key)))\n" - " (dictree--cache-completions (cdr entry)))\n" - " (dictree--cache-maxnum (cdr entry)))\n" - " complete-ranked-cache))\n" - " (dictree--complete-ranked-cache " dictname "))\n" - " (setf (dictree--complete-ranked-cache " dictname ")\n" - " complete-ranked-cache))\n" - ))) - - - ;; --- write to file --- - ;; generate the structure to save - (setq tmpdict (dictree-create)) - (setf (dictree--name tmpdict) dictname) - (setf (dictree--filename tmpdict) nil) ; filename gets set on loading - (setf (dictree--autosave tmpdict) (dictree--autosave dict)) - (setf (dictree--modified tmpdict) nil) - (setf (dictree--comparison-function tmpdict) - (dictree--comparison-function dict)) - (setf (dictree--insert-function tmpdict) - (dictree--insert-function dict)) - (setf (dictree--insfun tmpdict) - (dictree--insfun dict)) - (setf (dictree--rank-function tmpdict) - (dictree--rank-function dict)) - (setf (dictree--rankfun tmpdict) - (dictree--rankfun dict)) - (setf (dictree--cache-policy tmpdict) - (dictree--cache-policy dict)) - (setf (dictree--cache-update-policy tmpdict) - (dictree--cache-update-policy dict)) - (setf (dictree--lookup-cache tmpdict) lookup-alist) - (setf (dictree--lookup-cache-threshold tmpdict) - (dictree--lookup-cache-threshold dict)) - (setf (dictree--complete-cache tmpdict) complete-alist) - (setf (dictree--complete-cache-threshold tmpdict) - (dictree--complete-cache-threshold dict)) - (setf (dictree--complete-ranked-cache tmpdict) complete-ranked-alist) - (setf (dictree--complete-ranked-cache-threshold tmpdict) - (dictree--complete-ranked-cache-threshold dict)) - (setf (dictree--trie tmpdict) tmptrie) - (setf (dictree--key-savefun tmpdict) (dictree--key-savefun dict)) - (setf (dictree--key-loadfun tmpdict) (dictree--key-loadfun dict)) - (setf (dictree--data-savefun tmpdict) (dictree--data-savefun dict)) - (setf (dictree--data-loadfun tmpdict) (dictree--data-loadfun dict)) - (setf (dictree--plist-savefun tmpdict) (dictree--plist-savefun dict)) - (setf (dictree--plist-loadfun tmpdict) (dictree--plist-loadfun dict)) - (setf (dictree--meta-dict-list tmpdict) nil) - - ;; write lisp code that generates the dictionary object - (let ((restore-print-circle print-circle) - (restore-print-level print-level) - (restore-print-length print-length)) - (setq print-circle nil - print-level nil - print-length nil) - (insert "(eval-when-compile (require 'cl))\n") - (insert "(require 'dict-tree)\n") - (insert "(defvar " dictname " nil \"Dictionary " dictname ".\")\n") - (insert "(setq " dictname " '" (prin1-to-string tmpdict) ")\n") - (insert hashcode) - (insert "(setf (dictree-filename " dictname ")\n" - " (locate-library \"" dictname "\"))\n") - (insert "(unless (memq " dictname " dictree-loaded-list)\n" - " (push " dictname " dictree-loaded-list))\n") -;; (insert "(provide '" dictname ")\n") - (setq print-circle restore-print-circle - print-level restore-print-level - print-length restore-print-length) + (concat + hashcode + "(let ((complete-cache (make-hash-table :test 'equal))\n" + " (trie (dictree--trie " dictname ")))\n" + " (mapc\n" + " (lambda (entry)\n" + " (puthash\n" + " (car entry)\n" + " (dictree--cache-create\n" + " (mapcar\n" + " (lambda (key)\n" + " (cons key (trie-member trie key)))\n" + " (dictree--cache-completions (cdr entry)))\n" + " (dictree--cache-maxnum (cdr entry)))\n" + " complete-cache))\n" + " (dictree--complete-cache " dictname "))\n" + " (setf (dictree--complete-cache " dictname ")\n" + " complete-cache))\n" + ))) + + ;; convert ranked completion cache hash table to alist, if it exists + (when (dictree--complete-ranked-cache-threshold dict) + (maphash + (lambda (key val) + (push + (cons key + (cons (mapcar 'car (dictree--cache-completions val)) + (dictree--cache-maxnum val))) + complete-ranked-alist)) + (dictree--complete-ranked-cache dict)) + ;; generate code to reconstruct the ordered hash table + (setq hashcode + (concat + hashcode + "(let ((complete-ranked-cache (make-hash-table :test 'equal))\n" + " (trie (dictree--trie " dictname ")))\n" + " (mapc\n" + " (lambda (entry)\n" + " (puthash\n" + " (car entry)\n" + " (dictree--cache-create\n" + " (mapcar\n" + " (lambda (key)\n" + " (cons key (trie-member trie key)))\n" + " (dictree--cache-completions (cdr entry)))\n" + " (dictree--cache-maxnum (cdr entry)))\n" + " complete-ranked-cache))\n" + " (dictree--complete-ranked-cache " dictname "))\n" + " (setf (dictree--complete-ranked-cache " dictname ")\n" + " complete-ranked-cache))\n" + ))) + + + ;; --- write to file --- + ;; generate the structure to save + (setq tmpdict (dictree-create)) + (setf (dictree--trie tmpdict) tmptrie) + (setf (dictree--name tmpdict) dictname) + (setf (dictree--filename tmpdict) filename) + (setf (dictree--autosave tmpdict) + (dictree--autosave dict)) + (setf (dictree--modified tmpdict) nil) + (setf (dictree--comparison-function tmpdict) + (dictree--comparison-function dict)) + (setf (dictree--insert-function tmpdict) + (dictree--insert-function dict)) + (setf (dictree--insfun tmpdict) + (dictree--insfun dict)) + (setf (dictree--rank-function tmpdict) + (dictree--rank-function dict)) + (setf (dictree--rankfun tmpdict) + (dictree--rankfun dict)) + (setf (dictree--cache-policy tmpdict) + (dictree--cache-policy dict)) + (setf (dictree--cache-update-policy tmpdict) + (dictree--cache-update-policy dict)) + (setf (dictree--lookup-cache tmpdict) + lookup-alist) + (setf (dictree--lookup-cache-threshold tmpdict) + (dictree--lookup-cache-threshold dict)) + (setf (dictree--complete-cache tmpdict) + complete-alist) + (setf (dictree--complete-cache-threshold tmpdict) + (dictree--complete-cache-threshold dict)) + (setf (dictree--complete-ranked-cache tmpdict) + complete-ranked-alist) + (setf (dictree--complete-ranked-cache-threshold tmpdict) + (dictree--complete-ranked-cache-threshold dict)) + (setf (dictree--key-savefun tmpdict) + (dictree--key-savefun dict)) + (setf (dictree--key-loadfun tmpdict) + (dictree--key-loadfun dict)) + (setf (dictree--data-savefun tmpdict) + (dictree--data-savefun dict)) + (setf (dictree--data-loadfun tmpdict) + (dictree--data-loadfun dict)) + (setf (dictree--plist-savefun tmpdict) + (dictree--plist-savefun dict)) + (setf (dictree--plist-loadfun tmpdict) + (dictree--plist-loadfun dict)) + (setf (dictree--meta-dict-list tmpdict) nil) + + ;; write lisp code that generates the dictionary object + (let ((restore-print-circle print-circle) + (restore-print-level print-level) + (restore-print-length print-length)) + (setq print-circle nil + print-level nil + print-length nil) + (insert "(eval-when-compile (require 'cl))\n") + (insert "(require 'dict-tree)\n") + (insert "(defvar " dictname " nil \"Dictionary " dictname ".\")\n") + (insert "(setq " dictname " '" (prin1-to-string tmpdict) ")\n") + (insert "(trie-transform-from-read (dictree--trie " dictname "))\n") + (when hashcode (insert hashcode)) +;;; (insert "(setf (dictree-filename " dictname ")\n" +;;; " (locate-library \"" dictname "\"))\n") + (insert "(unless (memq " dictname " dictree-loaded-list)\n" + " (push " dictname " dictree-loaded-list))\n") +;;; (insert "(provide '" dictname ")\n") + (setq print-circle restore-print-circle + print-level restore-print-level + print-length restore-print-length))) + + ;; transform trie back to usable form + (trie-transform-from-read (dictree--trie dict)) ; unwind-protected ))) -(defun dictree--write-meta-dict-code (dict dictname) - "Write code for meta-dictionary DICT to current buffer, -giving it the name DICTNAME." +(defun dictree--write-meta-dict-code (dict dictname filename) + ;; Write code for meta-dictionary DICT to current buffer, giving it the name + ;; DICTNAME and file FILENAME. (let (hashcode tmpdict lookup-alist complete-alist complete-ranked-alist) @@ -2513,7 +2534,7 @@ giving it the name DICTNAME." ;; generate the structure to save (setq tmpdict (dictree-create)) (setf (dictree--meta-dict-name tmpdict) dictname) - (setf (dictree--meta-dict-filename tmpdict) nil) ; set on loading + (setf (dictree--meta-dict-filename tmpdict) filename) (setf (dictree--meta-dict-autosave tmpdict) (dictree--autosave dict)) (setf (dictree--meta-dict-modified tmpdict) nil) (setf (dictree--meta-dict-combine-function tmpdict) @@ -2551,12 +2572,12 @@ giving it the name DICTNAME." " " dictname "\n" " (mapcar (lambda (name) (eval (intern-soft name)))\n" " (dictree--meta-dict-dictlist " dictname " )))\n") - (insert hashcode) - (insert "(setf (dictree-filename " dictname ")" - " (locate-library \"" dictname "\"))\n") + (when hashcode (insert hashcode)) +;;; (insert "(setf (dictree-filename " dictname ")" +;;; " (locate-library \"" dictname "\"))\n") (insert "(unless (memq " dictname " dictree-loaded-list)" " (push " dictname " dictree-loaded-list))\n") -;; (insert "(provide '" dictname ")\n") +;;; (insert "(provide '" dictname ")\n") ))