[nongnu] elpa/flx 46dd7d7edb 144/182: Improve readability

[ELPA Syncer]

branch: elpa/flx
commit 46dd7d7edbbd2846feb5552b5434c92e945bbf72
Author: PythonNut <PythonNut@users.noreply.github.com>
Commit: PythonNut <PythonNut@users.noreply.github.com>

    Improve readability
---
 flx.el | 112 +++++++++++++++++++++++++++++++++++++++++------------------------
 1 file changed, 71 insertions(+), 41 deletions(-)

diff --git a/flx.el b/flx.el
index 4a2c15fbaa..0e476ec615 100644
--- a/flx.el
+++ b/flx.el
@@ -245,18 +245,30 @@ See documentation for logic."
             (puthash str res cache))
           res))))
 
-(defun flx-find-best-match (greater-than
-                            q-index
-                            query-length
+(defun flx-find-best-match (str-info
                             heatmap
-                            match-cache
-                            str-info
-                            query)
+                            greater-than
+                            query
+                            query-length
+                            q-index
+                            match-cache)
+  "Recursively compute the best match for a string, passed as STR-INFO and
+HEATMAP, according to QUERY.
+
+This function uses MATCH-CACHE to memoize its return values.
+For other parameters, see `flx-score'"
+
+  ;; Here, we use a simple N'ary hashing scheme
+  ;; You could use (/ hash-key query-length) to get greater-than
+  ;; Or, (mod hash-key query-length) to get q-index
+  ;; We use this instead of a cons key for the sake of efficiency
   (let* ((hash-key (+ q-index
                       (* (or greater-than 0)
                          query-length)))
          (hash-value (gethash hash-key match-cache)))
     (if hash-value
+        ;; Here, we use the value 'no-match to distinguish a cache miss
+        ;; from a nil (i.e. non-matching) return value
         (if (eq hash-value 'no-match)
             nil
           hash-value)
@@ -264,41 +276,52 @@ See documentation for logic."
                        (gethash (aref query q-index) str-info)
                        greater-than))
             (match)
-            (score)
+            (temp-score)
             (best-score most-negative-fixnum))
 
+        ;; Matches are of the form:
+        ;; ((match_indexes) . (score . contiguous-count))
         (if (>= q-index (1- query-length))
+            ;; At the tail end of the recursion, simply
+            ;; generate all possible matches with their scores
+            ;; and return the list to parent.
             (setq match (mapcar (lambda (index)
                                   (cons (list index)
                                         (cons (aref heatmap index) 0)))
                                 indexes))
           (dolist (index indexes)
-            (dolist (elem (flx-find-best-match index (1+ q-index)
-                                               query-length
+            (dolist (elem (flx-find-best-match str-info
                                                heatmap
-                                               match-cache
-                                               str-info
-                                               query))
-              (setq score (if (= (1- (caar elem)) index)
-                              (+ (cadr elem)
-                                 (aref heatmap index)
-                                 (* (min (cddr elem)
-                                         3)
-                                    15)
-                                 60)
-                            (+ (cadr elem)
-                               (aref heatmap index))))
-
-              ;; we only care about the optimal score
-              (when (> score best-score)
-                (setq best-score score
+                                               index
+                                               query
+                                               query-length
+                                               (1+ q-index)
+                                               match-cache))
+              (setq temp-score
+                    (if (= (1- (caar elem)) index)
+                        (+ (cadr elem)
+                           (aref heatmap index)
+
+                           ;; boost contiguous matches
+                           (* (min (cddr elem)
+                                   3)
+                              15)
+                           60)
+                      (+ (cadr elem)
+                         (aref heatmap index))))
+
+              ;; We only care about the optimal match, so only
+              ;; forward the match with the best score to parent
+              (when (> temp-score best-score)
+                (setq best-score temp-score
                       match (list (cons (cons index (car elem))
-                                        (cons score
+                                        (cons temp-score
                                               (if (= (1- (caar elem))
                                                      index)
                                                   (1+ (cddr elem))
                                                 0)))))))))
 
+        ;; Calls are cached to avoid exponential time complexity
         (puthash hash-key
                  (if match match 'no-match)
                  match-cache)
@@ -315,22 +338,29 @@ See documentation for logic."
          (full-match-boost (and (< 1 query-length)
                                 (< query-length 5)))
 
-         ;; Dynamic Programming table
+         ;; Dynamic Programming table for memoizing flx-find-best-match
          (match-cache (make-hash-table :test 'eql :size 10))
-         (res (flx-find-best-match nil 0
-                                   query-length
-                                   heatmap
-                                   match-cache
-                                   str-info
-                                   query)))
-      ;; postprocess candidate
-      (and res
-           (cons (if (and full-match-boost
-                          (=  (length (caar res))
-                              (length str)))
-                     (+ (cl-cadar res) 10000)
-                   (cl-cadar res))
-               (caar res))))))
+
+         (optimal-match (flx-find-best-match str-info
+                                             heatmap
+                                             nil
+                                             query
+                                             query-length
+                                             0
+                                             match-cache)))
+      ;; Postprocess candidate
+      (and optimal-match
+           (cons
+            ;; This is the computed score, adjusted to boost the scores
+            ;; of exact matches.
+            (if (and full-match-boost
+                     (=  (length (caar optimal-match))
+                         (length str)))
+                (+ (cl-cadar optimal-match) 10000)
+              (cl-cadar optimal-match))
+
+            ;; This is the list of match positions
+            (caar optimal-match))))))
 
 (defun flx-propertize (obj score &optional add-score)
   "Return propertized copy of obj according to score.