-
-
Notifications
You must be signed in to change notification settings - Fork 4
/
liquidmetal.el
170 lines (141 loc) · 6.74 KB
/
liquidmetal.el
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
;;; liquidmetal.el --- A mimetic poly-alloy of the Quicksilver scoring algorithm -*- lexical-binding: t; -*-
;; Copyright (C) 2021-2024 Shen, Jen-Chieh
;; Created date 2021-06-08 12:59:19
;; Author: Shen, Jen-Chieh <jcs090218@gmail.com>
;; URL: https://github.com/jcs-elpa/liquidmetal
;; Version: 1.3.0
;; Package-Requires: ((emacs "24.4"))
;; Keywords: matching fuzzy
;; This file is NOT part of GNU Emacs.
;; This program 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.
;; This program 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.
;; You should have received a copy of the GNU General Public License
;; along with this program. If not, see <https://www.gnu.org/licenses/>.
;;; Commentary:
;;
;; A mimetic poly-alloy of the Quicksilver scoring algorithm
;;
;; The algorithm is created by Ryan McGeary and it's ported from the repository
;; https://github.com/rmm5t/liquidmetal.
;;
;; For more information please visit the upstream repository or see the `why`
;; section in the README, https://github.com/rmm5t/liquidmetal#why.
;;
;;; Code:
(require 'subr-x)
(defconst liquidmetal-score-no-match 0.0
"The score indicating a negative match.")
(defconst liquidmetal-score-match 1.0
"The score indicating a full-match.")
(defconst liquidmetal-score-trailing 0.8
"The score to return when the abrreviation string is empty.")
(defconst liquidmetal-score-trailing-but-started 0.9
"Trailing score but not the start of string.")
(defconst liquidmetal-score-buffer 0.85
"Trailing score at the start of string.")
(defconst liquidmetal-word-separators "[ \t_-]"
"Separator to indentify a next new word.")
(defun liquidmetal--create-array (len)
"Create a empy array with LEN."
(let (new-array)
(dotimes (_ len) (push -1 new-array))
new-array))
(defun liquidmetal--set-array (array index value)
"Safe way to set VALUE to ARRAY's item by INDEX."
(let ((clone-array array) (diff (1+ (- index (length array)))))
(when (<= 0 index)
(setq clone-array (append clone-array (liquidmetal--create-array diff)))
(setf (nth index clone-array) value))
clone-array))
;;;###autoload
(defun liquidmetal-score (string abbreviation)
"Computes the score of matching STRING with ABBREVIATION.
The return value is in the range 0.0 to 1.0 the later being full-match."
(let ((len (length abbreviation)))
(cond ((= 0 len) liquidmetal-score-trailing)
((> len (length string)) liquidmetal-score-no-match)
(t (liquidmetal-build-score string abbreviation)))))
(defun liquidmetal-fill-array (array value from to)
"Fill ARRAY with VALUE FROM to TO."
(let ((clone-array array) (index from))
(while (< index to)
(if (nth index clone-array)
(setf (nth index clone-array) value)
(setq clone-array (append clone-array (list value))))
(setq index (1+ index)))
clone-array))
(defun liquidmetal-index-of (array item &optional start)
"Return the ITEM's index from ARRAY.
Optional argument START is the starting of the search index."
(unless start (setq start 0))
(when (< start 0) (setq start 0))
(string-match-p item array start))
(defun liquidmetal-is-new-word (string index)
"Return non-nil if character from INDEX of STRING is new word."
(let ((c (or (ignore-errors (substring string (1- index) index)) "")))
(if (string-empty-p c) t
(string-match-p liquidmetal-word-separators c))))
(defun liquidmetal-is-upper-case (string index)
"Return non-nil if character from INDEX of STRING is a uppercase."
(let ((c (or (ignore-errors (substring string index (1+ index))) "")))
(string= c (upcase c))))
(defun liquidmetal-score-all (string search abbrev search-index abbr-index scores &optional all-scores)
"Iterate through STRING and determine the overall score.
Argument STRING is target to search through.
Argument SEARCH is the lowercase of of STRING.
Argument ABBREV is the lowercase of abbreviation.
Argument SEARCH-INDEX is pass for iterating matching string.
Argument ABBR-INDEX is pass for iterating abbreviation string
Argument SCORES stores the last result to ALL-SCORES.
Optional argument ALL-SCORES is stored for recusrive result."
(if (= abbr-index (length abbrev))
(let* ((started (string= (substring search 0 1) (substring abbrev 0 1)))
(trail-score (if started liquidmetal-score-trailing-but-started liquidmetal-score-trailing)))
(setq scores (liquidmetal-fill-array scores trail-score (length scores) (length string)))
(push scores all-scores))
(let* ((c (substring abbrev abbr-index (1+ abbr-index)))
(index (liquidmetal-index-of search c search-index))
(score-index search-index))
(setq abbr-index (1+ abbr-index))
(when index
(while (progn
(setq index (liquidmetal-index-of search c (1+ search-index)))
index)
(cond ((liquidmetal-is-new-word string index)
(setq scores (liquidmetal--set-array scores (1- index) liquidmetal-score-match))
(setq scores
(liquidmetal-fill-array scores liquidmetal-score-buffer (1+ score-index) (1- index))))
((liquidmetal-is-upper-case string index)
(setq scores
(liquidmetal-fill-array scores liquidmetal-score-buffer (1+ score-index) index)))
(t
(setq scores
(liquidmetal-fill-array scores liquidmetal-score-no-match (1+ score-index) index))))
(if (nth index scores)
(setf (nth index scores) liquidmetal-score-match)
(push liquidmetal-score-match scores))
;; consume matched string and continue search
(setq search-index index)
(setq all-scores
(liquidmetal-score-all string search abbrev search-index abbr-index scores all-scores))))))
all-scores)
(defun liquidmetal-build-score (string abbreviation)
"Calculates the fuzzy score of matching STRING with ABBREVIATION."
(let* ((search (downcase string)) (abbrev (downcase abbreviation))
(all-scores (liquidmetal-score-all string search abbrev -1 0 nil))
(max-score 0.0) score-sum)
(if (= (length all-scores) 0) 0.0
(dolist (scores all-scores)
(setq score-sum (apply '+ scores))
(when (> score-sum max-score)
(setq max-score score-sum)))
(setq max-score (/ max-score (length string))))
max-score))
(provide 'liquidmetal)
;;; liquidmetal.el ends here