mirrors/emacs
1
Fork 0
mirror of git://git.sv.gnu.org/emacs.git synced 2026-03-29 18:21:21 -07:00
Code Issues Projects Releases Wiki Activity
emacs/test/lisp
History
Exact
João Távora a0b5ff9bb7 Rewrite flex completion scoring with Gotoh algorithm 
The greedy regexp matching, broken scoring and broken highlight were
sources of frequent complaints about the 'flex' matching style.  This
commit fixes that.

It was inspired by the 'hotfuzz' style available at
https://github.com/axelf4/hotfuzz which is a modified version of Gotoh's
1982 dynamic programming algorithm (see: GOTOH, Osamu. An improved
algorithm for matching biological sequences. Journal of molecular
biology, 1982, 162.3: 705-708.).  That style is slightly more
sophisticated than 'flex' (has special rules for matching things at word
boundaries, a C module with multithreading support).  It's almost (but
not entirely) void of hacks so it'd make a good candidate to replace
'flex' entirely, but no progress has been made in getting it into
Emacs's core in over 2 years, so I thought I'd try my hand at it.

The new 'flex' implementation also uses Gotoh algorithm (apparently
a common choice for these kinds of task) and happens mostly in a new C
function.  It is strictly more correct than the "old" flex.  For
example, when matching the pattern 'goto' to, say, 'eglot--goto' and
'eglot--bol', no longer is the latter returned first, which was a
substantial annoyance.  And of course the highlighting is also correctly
placed on the 'goto' not scattered across the candidate.

Regarding performance, it is faster than the naive 'flex', but that's
mainly because this commit also includes changes to the Elisp code which
make faster regexp's for the filtering step.  It is slower than
'hotfuzz' when that style's C-module extension is leveraged.  'hotfuzz'
does the filtering and sorting steps together in C code and has
multithreaded workers there.  The matching and scoring algorithm itself
is not the bottleneck.

The flex style was completely decoupled from the pcm/substring styles in
lisp/minibuffer.el.  Test code were refactored and more tests were
added.

* src/minibuf.c (completion--flex-cost-gotoh): New function.

* lisp/minibuffer.el (completion-flex--pattern-str): New variable.
(flex-score-match-tightness): Make obsolete.
(completion--flex-all-completions-1): New helper function.
(completion-flex-try-completion, completion-flex-all-completions): Rewrite.
(completion-substring--all-completions): No longer take transform-pattern-fn.
(completion--flex-adjust-metadata): Tweak.
(completion--flex-score, completion--flex-score-1)
(completion--flex-score-last-md, completion-flex--make-flex-pattern): Delete.

* test/lisp/minibuffer-tests.el (completion--sorted-flex-completions):
New helper function.
(completion-flex-test-non-ascii): New test.
(completion--pcm-score): Delete.
(completion-pcm-test-3, completion-pcm-test-4)
(completion-substring-test-1, completion-substring-test-2)
(completion-flex-test-2, completion-flex-test-3): Tweak.
2026-02-07 21:23:19 +00:00
..
align-resources Support lua-ts-mode in align.el 2023-10-21 12:25:25 +02:00
auth-source-resources
bookmark-resources
calc calc: Improve handling of invalid 'calc-string-maximum-character' 2026-01-17 14:48:06 +02:00
calendar ; calendar-bahai: Move tests and convert to ERT 2026-01-24 13:25:14 +02:00
cedet ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
custom-resources
dabbrev-resources ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
dired-resources/insert-directory
emacs-lisp ; Fix package-vc-tests for older versions of Git 2026-01-29 10:29:40 +02:00
emulation ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
epg-resources Replace aging OpenPGP artifacts in the epg tests. 2022-10-06 14:53:39 +02:00
erc ; Don't use cl-letf with generic function in ERC test 2026-01-11 05:25:03 -08:00
eshell ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
faces-resources ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
files-resources Ensure .dir-locals-2.el behavior as documented (bug#75890) 2025-03-22 16:47:27 -04:00
gnus ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
hfy-cmap-resources
image ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
international ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
language ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
loadhist-resources ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
mail ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
mh-e ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
minibuffer-resources
net New Tramp test 2026-01-28 12:43:38 +01:00
nxml ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
obsolete ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
org ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
pcmpl-linux-resources
play ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
progmodes Add JSON path utility command to json-ts-mode 2026-01-21 19:27:03 +02:00
saveplace-resources
so-long-tests ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
term ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
textmodes ; Fix one of ispell-tests 2026-01-18 22:15:18 +02:00
time-resources
url ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
use-package ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
vc ; * test/lisp/vc/ediff-mult-tests.el: use ert-with-temp-directory 2026-02-05 17:36:18 +01:00
xdg-resources
abbrev-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
align-tests.el Fix aligning buffer regions containing multiple alignment sections 2026-02-05 10:51:16 +02:00
allout-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
allout-widgets-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
ansi-color-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
ansi-osc-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
apropos-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
arc-mode-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
auth-source-pass-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
auth-source-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
autoinsert-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
autorevert-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
battery-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
bookmark-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
buff-menu-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
button-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
calculator-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
char-fold-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
color-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
comint-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
completion-preview-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
completion-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
cus-edit-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
custom-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
dabbrev-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
delim-col-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
descr-text-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
desktop-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
dired-aux-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
dired-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
dired-x-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
dnd-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
dom-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
edmacro-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
electric-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
elide-head-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
env-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
epg-config-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
epg-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
faces-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
ffap-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
filenotify-tests.el ; Instrument filenotify test 2026-01-27 18:49:37 +01:00
files-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
files-x-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
find-cmd-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
follow-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
font-lock-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
format-spec-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
help-fns-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
help-mode-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
help-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
hfy-cmap-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
hi-lock-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
hl-line-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
htmlfontify-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
ibuffer-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
ido-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
image-file-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
image-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
imenu-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
info-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
info-xref-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
isearch-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
jit-lock-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
json-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
jsonrpc-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
kmacro-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
loadhist-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
lpr-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
ls-lisp-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
man-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
md4-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
minibuffer-tests.el Rewrite flex completion scoring with Gotoh algorithm 2026-02-07 21:23:19 +00:00
misc-tests.el New function 'truncate-string-pixelwise' (bug#80244) 2026-01-31 11:04:40 +02:00
mouse-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
mwheel-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
newcomment-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
obarray-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
paren-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
password-cache-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
pcmpl-linux-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
pcomplete-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
proced-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
ps-print-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
register-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
repeat-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
replace-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
rot13-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
savehist-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
saveplace-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
scroll-lock-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
server-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
ses-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
shadowfile-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
shell-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
simple-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
sort-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
soundex-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
speedbar-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
sqlite-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
startup-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
subr-tests.el Support cons cell for 'line-spacing' 2026-01-24 13:32:44 +02:00
tab-bar-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
tabify-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
tar-mode-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
tempo-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
term-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
thingatpt-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
thread-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
time-stamp-tests.el time-stamp-helper-string-used: New test 2026-01-05 15:23:01 -08:00
time-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
timezone-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
uniquify-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
version-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
visual-wrap-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
wdired-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
which-key-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
whitespace-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
wid-edit-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
winner-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
x-dnd-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
xdg-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
xml-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
xt-mouse-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00
yank-media-tests.el ; Add 2026 to copyright years. 2026-01-01 12:54:34 +00:00