[elpa] externals/dict-tree d0e339d 117/154: Don't wrap rank and filter functions for regexp and fuzzy queries.

[Stefan Monnier]

branch: externals/dict-tree
commit d0e339d5347b77bbb64f5b3d6a1bb178160ba7e8
Author: Toby S. Cubitt <toby-predictive@dr-qubit.org>
Commit: Toby S. Cubitt <toby-predictive@dr-qubit.org>

    Don't wrap rank and filter functions for regexp and fuzzy queries.
    
    Otherwise, wrapped user-supplied filter and rank functions will not work for
    trie stacks, so will throw errors when used on meta-dicts.
---
 dict-tree.el | 288 +++++++++++++++++++++++++++++++++++++----------------------
 1 file changed, 180 insertions(+), 108 deletions(-)

diff --git a/dict-tree.el b/dict-tree.el
index f8b0107..2bca191 100644
--- a/dict-tree.el
+++ b/dict-tree.el
@@ -216,20 +216,6 @@ If START or END is negative, it counts from the end."
                 (cons (car b) (dictree--cell-data (cdr b)))))))
 
 
-;; return wrapped rankfun to ignore fuzzy query distance data
-;; (these always get wrapped again by `dictree--wrap-rankfun')
-(if (trie-lexical-binding-p)
-    (defun dictree--wrap-fuzzy-rankfun (rankfun)  ; INTERNAL USE ONLY
-      (lambda (a b)
-       (funcall rankfun
-                (cons (caar a) (cdr a))
-                (cons (caar b) (cdr b)))))
-  (defun dictree--wrap-fuzzy-rankfun (rankfun)  ; INTERNAL USE ONLY
-    `(lambda (a b)
-       (,rankfun (cons (caar a) (cdr a))
-                (cons (caar b) (cdr b))))))
-
-
 ;; return wrapped combfun to deal with data wrapping
 (if (trie-lexical-binding-p)
     (defun dictree--wrap-combfun (combfun)  ; INTERNAL USE ONLY
@@ -264,6 +250,55 @@ If START or END is negative, it counts from the end."
     `(lambda (res) (,resultfun (car res) (dictree--cell-data (cdr res))))))
 
 
+;; return wrapped rankfun to ignore regexp grouping data
+;; (these functions always get wrapped again by `dictree--wrap-rankfun')
+(if (trie-lexical-binding-p)
+    (defun dictree--wrap-regexp-rankfun (rankfun)
+      (lambda (a b)
+       ;; if car of argument contains a key+group list rather than a straight
+       ;; key, remove group list
+       ;; FIXME: the test for straight key, below, will fail if the key is a
+       ;;        list, and the first element of the key is itself a list
+       ;;        (there might be no easy way to fully fix this...)
+       (unless (or (atom (car a))
+                   (and (listp (car a)) (not (sequencep (caar a)))))
+         (setq a (cons (caar a) (cdr a))))
+       (unless (or (atom (car b))
+                   (and (listp (car b)) (not (sequencep (caar b)))))
+         (setq b (cons (caar b) (cdr b))))
+       (funcall rankfun a b)))
+  (defun dictree--wrap-regexp-rankfun (rankfun)
+    `(lambda (a b)
+       ;; if car of argument contains a key+group list rather than a straight
+       ;; key, remove group list
+       ;; FIXME: the test for straight key, below, will fail if the key is a
+       ;;        list, and the first element of the key is itself a list
+       ;;        (there might be no easy way to fully fix this...)
+       (unless (or (atom (car a))
+                  (and (listp (car a))
+                      (not (sequencep (caar a)))))
+        (setq a (cons (caar a) (cdr a))))
+       (unless (or (atom (car b))
+                  (and (listp (car b))
+                       (not (sequencep (caar b)))))
+        (setq b (cons (caar b) (cdr b))))
+       (,rankfun a b))))
+
+
+;; return wrapped rankfun to ignore fuzzy query distance data
+;; (these functions always get wrapped again by `dictree--wrap-rankfun')
+(if (trie-lexical-binding-p)
+    (defun dictree--wrap-fuzzy-rankfun (rankfun)  ; INTERNAL USE ONLY
+      (lambda (a b)
+       (funcall rankfun
+                (cons (nth 0 (car a)) (cdr a))
+                (cons (nth 0 (car b)) (cdr b)))))
+  (defun dictree--wrap-fuzzy-rankfun (rankfun)  ; INTERNAL USE ONLY
+    `(lambda (a b)
+       (,rankfun (cons (nth 0 (car a)) (cdr a))
+                (cons (nth 0 (car b)) (cdr b))))))
+
+
 ;; construct lexicographic sort function from DICT's comparison function
 (if (trie-lexical-binding-p)
     (defun dictree--construct-sortfun (dict)  ; INTERNAL USE ONLY
@@ -1455,12 +1490,12 @@ PREFIX is a prefix of STR."
     ;; if key was...
     (cond
      ;; deleted and in cached result: remove cache entry and re-run the
-     ;; same completion to update the cache
+     ;; same regexp search to update the cache
      ((and deleted cmpl)
       (remhash (list regexp auxargs reverse) (dictree-complete-cache dict))
       (dictree-regexp-search dict regexp nil maxnum reverse))
-     ;; modified and not in cached result: merge it into the completion
-     ;; list, retaining only the first maxnum
+     ;; modified and not in cached result: merge it into the results list,
+     ;; retaining only the first maxnum
      ((and (not deleted) (not cmpl))
       (save-match-data
        (set-match-data nil)
@@ -1513,8 +1548,8 @@ PREFIX is a prefix of STR."
      ((and deleted cmpl)
       (remhash (list regexp auxargs reverse) cache)
       (dictree-regexp-search dict regexp 'ranked maxnum reverse))
-     ;; modified and not in cached result: merge it into the completion
-     ;; list, retaining only the first maxnum
+     ;; modified and not in cached result: merge it into the results list,
+     ;; retaining only the first maxnum
      ((and (not deleted) (not cmpl))
       (save-match-data
        (set-match-data nil)
@@ -1561,13 +1596,13 @@ PREFIX is a prefix of STR."
     ;; if key was...
     (cond
      ;; deleted and in cached result: remove cache entry and re-run the
-     ;; same completion to update the cache
+     ;; same query to update the cache
      ((and deleted match)
       (remhash (list string auxargs reverse)
               (dictree-fuzzy-match-cache dict))
       (dictree-fuzzy-match dict string (car auxargs) nil maxnum reverse))
-     ;; modified and not in cached result: merge it into the completion
-     ;; list, retaining only the first maxnum
+     ;; modified and not in cached result: merge it into the results list,
+     ;; retaining only the first maxnum
      ((and (not deleted) (not match))
       (setf (dictree--cache-results cache-entry)
            (dictree--merge
@@ -1590,8 +1625,8 @@ PREFIX is a prefix of STR."
 
 (defun dictree--synchronize-ranked-fuzzy-match-cache
   (dict cache-entry string auxargs reverse key newdata deleted)
-  ;; Synchronize DICT's ranked completion CACHE-ENTRY for STRING and REVERSE, 
for
-  ;; a KEY whose data was either updated to NEWDATA or DELETED.
+  ;; Synchronize DICT's ranked fuzzy-match CACHE-ENTRY for STRING and REVERSE,
+  ;; for a KEY whose data was either updated to NEWDATA or DELETED.
   (let* ((matches (dictree--cache-results cache-entry))
         (maxnum (dictree--cache-maxnum cache-entry))
         (match (assoc key matches))
@@ -1604,7 +1639,7 @@ PREFIX is a prefix of STR."
       (remhash (list string auxargs reverse)
               (dictree--fuzzy-match-ranked-cache dict))
       (dictree-fuzzy-match dict string (car auxargs) 'ranked maxnum reverse))
-     ;; modified and not in cached result: merge it into the completion list,
+     ;; modified and not in cached result: merge it into the results list,
      ;; retaining only the first maxnum
      ((and (not deleted) (not match))
       (setf (dictree--cache-results cache-entry)
@@ -1641,14 +1676,14 @@ PREFIX is a prefix of STR."
         (distance (Lewenstein-distance key prefix)))
     ;; if key was...
     (cond
-     ;; deleted and in cached result: remove cache entry and re-run the
-     ;; same completion to update the cache
+     ;; deleted and in cached result: remove cache entry and re-run the same
+     ;; query to update the cache
      ((and deleted cmpl)
       (remhash (list prefix auxargs reverse)
               (dictree-fuzzy-complete-cache dict))
       (dictree-fuzzy-complete dict prefix (car auxargs) nil maxnum reverse))
-     ;; modified and not in cached result: merge it into the completion
-     ;; list, retaining only the first maxnum
+     ;; modified and not in cached result: merge it into the results list,
+     ;; retaining only the first maxnum
      ((and (not deleted) (not cmpl))
       (setf (dictree--cache-results cache-entry)
            (dictree--merge
@@ -1671,8 +1706,8 @@ PREFIX is a prefix of STR."
 
 (defun dictree--synchronize-ranked-fuzzy-complete-cache
   (dict cache-entry prefix auxargs reverse key newdata deleted)
-  ;; Synchronize DICT's ranked completion CACHE-ENTRY for PREFIX and REVERSE, 
for
-  ;; a KEY whose data was either updated to NEWDATA or DELETED.
+  ;; Synchronize DICT's ranked fuzzy-completion CACHE-ENTRY for PREFIX and
+  ;; REVERSE, for a KEY whose data was either updated to NEWDATA or DELETED.
   (let* ((completions (dictree--cache-results cache-entry))
         (maxnum (dictree--cache-maxnum cache-entry))
         (cmpl (assoc key completions))
@@ -1931,10 +1966,7 @@ If TYPE is string, it must be possible to apply the 
function
 `string' to the elements of sequences stored in DICT.
 
 FUNCTION is applied in ascending order, or descending order if
-REVERSE is non-nil.
-
-Note: to avoid nasty dynamic scoping bugs, FUNCTION must *not*
-bind any variables with names commencing \"--\"."
+REVERSE is non-nil."
 
   ;; "rename" FUNCTION to something hopefully unique to lessen the
   ;; likelihood of dynamic scoping bugs caused by a supplied function
@@ -1991,11 +2023,7 @@ stored in DICT.
 The FUNCTION will be applied and the results combined in
 asscending \"lexicographic\" order (i.e. the order defined by the
 dictionary's comparison function; cf. `dictree-create'), or
-descending order if REVERSE is non-nil.
-
-Note: to avoid nasty dynamic scoping bugs, FUNCTION and
-COMBINATOR must *not* bind any variables with names
-commencing \"--\"."
+descending order if REVERSE is non-nil."
 
   ;; try to avoid dynamic scoping bugs
   (let ((--dictree-mapf--function function)
@@ -2046,12 +2074,9 @@ Note that if you don't care about the order in which 
FUNCTION is
 applied, just that the resulting list is in the correct order,
 then
 
-  (trie-mapf function #'cons trie type (not reverse))
-
-is more efficient.
+  (dictree-mapf function #'cons dict type (not reverse))
 
-Note: to avoid nasty dynamic scoping bugs, FUNCTION must *not*
-bind any variables with names commencing \"--\"."
+is more efficient."
   (nreverse (dictree-mapf function #'cons dict type reverse)))
 
 
@@ -2341,7 +2366,7 @@ included in the stack. All sequences in the list must be 
of the
 same type.
 
 Note that any modification to DICT *immediately* invalidates all
-trie-stacks created before the modification (in particular,
+dictree-stacks created before the modification (in particular,
 calling `dictree-stack-pop' will give unpredictable results).
 
 Operations on dictree-stacks are significantly more efficient
@@ -2515,8 +2540,7 @@ Returns nil if the stack is empty."
        (setq res
              (dictree--do-query dic arg auxargs triefun stackfun
                                 rank-function maxnum reverse
-                                (when filter
-                                  (dictree--wrap-filter filter)))))
+                                (dictree--wrap-filter filter))))
 
        ;; if there's a cache entry with enough results, use it
        ((and (setq cache-entry
@@ -2594,7 +2618,7 @@ Returns nil if the stack is empty."
          (when (or (null filter) (funcall filter res))
            (if rank-function
                (heap-add heap res)   ; for ranked query, add to heap
-             (push res results)) ; for lexicographic query, add to list
+             (push res results))     ; for lexicographic query, add to list
            (incf i)))
        (if (null rank-function)
            ;; for lexicographic query, reverse and return result list (we
@@ -2647,8 +2671,8 @@ If optional argument RANK-FUNCTION is t, the completions 
are
 sorted according to the dictionary's rank-function (see
 `dictree-create'). Any non-nil value that *is* a function
 over-rides this. In that case, RANK-FUNCTION should accept two
-arguments, both cons cells. The car of each contains a sequence
-from the trie (of the same type as PREFIX), the cdr contains its
+arguments, both cons cells. The car of each contains a completion
+from DICT (of the same type as PREFIX), the cdr contains its
 associated data. The RANK-FUNCTION should return non-nil if first
 argument is ranked strictly higher than the second, nil
 otherwise.
@@ -2713,7 +2737,7 @@ completion, and its associated data."
 (defun dictree-regexp-search
   (dict regexp
    &optional rank-function maxnum reverse no-cache filter resultfun)
-  "Return an alist containing all matches for REGEXP in TRIE
+  "Return an alist containing all matches for REGEXP in DICT
 along with their associated data, in the order defined by
 RANKFUN, defauling to \"lexicographic\" order. If REVERSE is
 non-nil, the completions are sorted in the reverse order. Returns
@@ -2728,12 +2752,13 @@ keys, use a meta-dictionary; see 
`dictree-create-meta-dict'.)
 
 REGEXP is a regular expression, but it need not necessarily be a
 string. It must be a sequence (vector, list of string) whose
-elements are either elements of the same type as elements of the
-trie keys (which behave as literals in the regexp), or any of the
+elements are either of the same type as elements of DICT
+keys (these behave as literals in the regexp), or any of the
 usual regexp special characters and backslash constructs. If
 REGEXP is a string, it must be possible to apply `string' to
-individual elements of the keys stored in the trie. The matches
-returned in the alist will be sequences of the same type as KEY.
+individual elements of the keys stored in DICT. The matches
+returned in the alist will be sequences of the same type as
+REGEXP.
 
 Only a subset of the full Emacs regular expression syntax is
 supported. There is no support for regexp constructs that are
@@ -2747,20 +2772,14 @@ beginning and end of the regexp to get an unanchored 
match).
 
 If the regexp contains any non-shy grouping constructs, subgroup
 match data is included in the results. In this case, the car of
-each match is no longer just a key. Instead, it is a list whose
-first element is the matching key, and whose remaining elements
-are cons cells whose cars and cdrs give the start and end indices
+each match is no longer just a key. Instead, each element of the
+results list has the form
+
+    ((KEY (START1 . END1) (START2 . END2) ...) . DATA)
+
+where the (START . END) cons cells give the start and end indices
 of the elements that matched the corresponding groups, in order.
 
-If optional argument RANK-FUNCTION is t, the matches are sorted
-according to the dictionary's rank-function (see
-`dictree-create'). Any non-nil value that *is* a function
-over-rides this. In that case, RANK-FUNCTION should accept two
-arguments, both cons cells. The car of each contains a sequence
-from the dictionary (of the same type as REGEXP), the cdr
-contains its associated data. The RANK-FUNCTION should return
-non-nil if first argument is ranked strictly higher than the
-second, nil otherwise.
 
 The optional integer argument MAXNUM limits the results to the
 first MAXNUM matches. The default is to return all matches.
@@ -2769,17 +2788,41 @@ If the optional argument NO-CACHE is non-nil, it 
prevents caching
 of the result. Ignored for dictionaries that do not have wildcard
 caching enabled.
 
+
+If optional argument RANK-FUNCTION is t, the matches are sorted
+according to the dictionary's rank-function (see
+`dictree-create').
+
+Any other non-nil value of RANK-FUNCTION should be a function
+which accepts two arguments. If the regexp does not contain any
+non-shy grouping constructs, both arguments are (KEY . DATA) cons
+cells, where the car is a sequence of the same type as REGEXP. If
+the regexp does contain non-shy grouping constructs, both
+arguments are of the form
+
+    ((KEY (START1 . END1) (START2 . END2) ...) . DATA)
+
+RANKFUN should return non-nil if first argument is ranked
+strictly higher than the second, nil otherwise.
+
+
 The FILTER argument sets a filter function for the matches. If
 supplied, it is called for each possible match with two
-arguments: the matching key, and its associated data. If the
-filter function returns nil, the match is not included in the
-results, and does not count towards MAXNUM.
+arguments: a key and its associated data. If the regexp contains
+non-shy grouping constructs, the first argument is of the form
+
+    (KEY (START1 . END1) (START2 . END2) ...)
+
+If the FILTER function returns nil, the match is not included in
+the results, and does not count towards MAXNUM.
+
 
 RESULTFUN defines a function used to process results before
 adding them to the final result list. If specified, it should
-accept two arguments: a key and its associated data. It's return
-value is what gets added to the final result list, instead of the
-default key-data cons cell."
+accept two arguments, of the same form as those for FILTER (see
+above). Its return value is what gets added to the final result
+list, instead of the default key-data cons cell."
+
   ;; run regexp query
   (dictree--query
    dict regexp nil
@@ -2797,7 +2840,8 @@ default key-data cons cell."
    (when rank-function
      (if (functionp rank-function)
         rank-function
-       (dictree-rank-function (if (listp dict) (car dict) dict))))
+       (dictree--wrap-regexp-rankfun
+       (dictree-rank-function (if (listp dict) (car dict) dict)))))
    maxnum reverse no-cache filter resultfun))
 
 
@@ -2815,6 +2859,14 @@ the order defined by RANKFUN, defauling to 
\"lexicographic\"
 order. If REVERSE is non-nil, the matches are sorted in the
 reverse order. Returns nil if no completions are found.
 
+Returns a list of matches, with elements of the form:
+
+    ((KEY . DIST) . DATA)
+
+where KEY is a matching key from the trie, DATA its associated
+data, and DIST is its Lewenstein distance \(edit distance\) from
+STRING.
+
 DICT can also be a list of dictionaries, in which case matches
 are sought in all dictionaries in the list. (Note that if the
 same key appears in multiple dictionaries, the alist may contain
@@ -2822,19 +2874,20 @@ the same key multiple times, each copy associated with 
the data
 from a different dictionary. If you want to combine identical
 keys, use a meta-dictionary; see `dictree-create-meta-dict'.)
 
-STRING is a sequence (vector, list or string), whose elements are
-of the same type as elements of the trie keys. If STRING is a
-string, it must be possible to apply `string' to individual
-elements of the keys stored in the trie. The KEYs returned in the
-list will be sequences of the same type as STRING.
+STRING is a sequence (vector, list or string), whose elements
+must be of the same type as elements of the keys stored in
+DICT. If STRING is a string, it must be possible to apply
+`string' to individual elements of DICT keys. The KEYs returned
+in the list will be sequences of the same type as STRING.
 
 DISTANCE must be an integer, and specifies the maximum Lewenstein
 distance \(edit distances\) of matches from STRING.
 
-If optional argument RANK-FUNCTION is 'distance, the matches are
-sorted according to their Lewenstein distance from STRING. If it
-is t, the matches are sorted according to the dictionary's
-rank-function (see `dictree-create').
+
+If optional argument RANK-FUNCTION is the symbol `distance', the
+matches are sorted according to their Lewenstein distance from
+STRING. If it is t, the matches are sorted according to the
+dictionary's rank-function (see `dictree-create').
 
 Any other non-nil value of RANK-FUNCTION should be a function
 which accepts two arguments, both of the form
@@ -2847,6 +2900,7 @@ its associated data. The RANK-FUNCTION should return 
non-nil if
 the first argument is ranked strictly higher than the second, nil
 otherwise.
 
+
 The optional integer argument MAXNUM limits the results to the
 first MAXNUM matches. The default is to return all matches.
 
@@ -2855,15 +2909,16 @@ caching of the result.
 
 The FILTER argument sets a filter function for the matches. If
 supplied, it is called for each possible match with two
-arguments: the matching key, and its associated data. If the
-filter function returns nil, the match is not included in the
-results, and does not count towards MAXNUM.
+arguments: a (KEY . DIST) cons cell, and DATA. If the filter
+function returns nil, the match is not included in the results,
+and does not count towards MAXNUM.
 
 RESULTFUN defines a function used to process results before
 adding them to the final result list. If specified, it should
-accept two arguments: a KEY and a (DIST . DATA) cons cell. Its
+accept two arguments: a (KEY . DIST) cons cell, and DATA. Its
 return value is what gets added to the final result list, instead
 of the default key-dist-data list."
+
   ;; run fuzzy-match query
   (dictree--query
    dict string (list distance)
@@ -2897,6 +2952,15 @@ the order defined by RANKFUN, defauling to 
\"lexicographic\"
 order. If REVERSE is non-nil, the matches are sorted in the
 reverse order. Returns nil if no completions are found.
 
+Returns a list of completions, with elements of the form:
+
+    ((KEY DIST PFXLEN) . DATA)
+
+where KEY is a matching completion from the trie, DATA its
+associated data, PFXLEN is the length of the prefix part of KEY,
+and DIST is its Lewenstein distance \(edit distance\) from
+PREFIX.
+
 DICT can also be a list of dictionaries, in which case matches
 are sought in all dictionaries in the list. (Note that if the
 same key appears in multiple dictionaries, the alist may contain
@@ -2904,26 +2968,32 @@ the same key multiple times, each copy associated with 
the data
 from a different dictionary. If you want to combine identical
 keys, use a meta-dictionary; see `dictree-create-meta-dict'.)
 
-PREFIX is a sequence (vector, list or string), whose elements are
-of the same type as elements of the trie keys. If STRING is a
-string, it must be possible to apply `string' to individual
-elements of the keys stored in the trie. The KEYs returned in the
-list will be sequences of the same type as STRING.
+PREFIX is a sequence (vector, list or string), whose elements
+must be of the same type as elements of the keys stored in
+DICT. If PREFIX is a string, it must be possible to apply
+`string' to individual elements of DICT keys. The KEYs returned
+in the list will be sequences of the same type as PREFIX.
 
 DISTANCE must be an integer, and specifies the maximum Lewenstein
 distance \(edit distances\) of prefixes from PREFIX.
 
-If optional argument RANK-FUNCTION is 'distance, the matches are
-sorted according to their Lewenstein distance from STRING. If it
-is any other non-nil value that is not a function, the matches
-are sorted according to the dictionary's rank-function (see
-`dictree-create'). Any non-nil value that *is* a function
-over-rides this. In that case, RANK-FUNCTION should accept two
-arguments, both cons cells. The car of each contains a sequence
-from the dictionary (of the same type as STRING), the cdr
-contains its associated data. The RANK-FUNCTION should return
-non-nil if first argument is ranked strictly higher than the
-second, nil otherwise.
+
+If optional argument RANK-FUNCTION is the symbol `distance', the
+matches are sorted by increasing Lewenstein distance of their
+prefix \(with same-distance prefixes ordered
+lexicographically\). If it is t, the matches are sorted according
+to the dictionary's rank-function (see `dictree-create').
+
+Any other non-nil value of RANK-FUNCTION should be a function
+that accepts two arguments, both of the form:
+
+    ((KEY DIST PFXLEN) . DATA)
+
+where KEY is a completion (of the same type as PREFIX), DIST is
+its Lewenstein distances from PREFIX, and DATA is its associated
+data. RANKFUN should return non-nil if first argument is ranked
+strictly higher than the second, nil otherwise.
+
 
 The optional integer argument MAXNUM limits the results to the
 first MAXNUM matches. The default is to return all matches.
@@ -2932,17 +3002,19 @@ If the optional argument NO-CACHE is non-nil, it 
prevents caching
 of the result. Ignored for dictionaries that do not have
 fuzzy-match caching enabled.
 
+
 The FILTER argument sets a filter function for the matches. If
 supplied, it is called for each possible match with two
-arguments: the matching key, and its associated data. If the
-filter function returns nil, the match is not included in the
-results, and does not count towards MAXNUM.
+arguments: a (KEY DIST PFXLEN) list, and DATA. If the filter
+function returns nil, the match is not included in the results,
+and does not count towards MAXNUM.
 
 RESULTFUN defines a function used to process results before
 adding them to the final result list. If specified, it should
-accept two arguments: a KEY and a (DIST . DATA) cons cell. Its
+accept two arguments: a (KEY DIST PFXLEN) list, and DATA. Its
 return value is what gets added to the final result list, instead
 of the default key-dist-data list."
+
   ;; run fuzzy-complete query
   (dictree--query
    dict prefix (list distance)