Project Awesome project awesome
♥

Fuzzy & Narrowing > fussy

Emacs completion-style leveraging flx / fzf / etc

Package 154 stars GitHub

#+TITLE: Fussy #+STARTUP: noindent

[[https://github.com/jojojames/fussy/actions/workflows/build.yaml][file:https://github.com/jojojames/fussy/actions/workflows/build.yaml/badge.svg]] [[https://melpa.org/#/fussy][file:https://melpa.org/packages/fussy-badge.svg]] [[https://stable.melpa.org/#/fussy][file:https://stable.melpa.org/packages/fussy-badge.svg]]

[[./screenshots/fussy.png]]

This is a package to provide a completion-style to Emacs that is able to leverage [[https://github.com/lewang/flx][flx]] as well as various other libraries such as [[https://github.com/dangduc/fzf-native][fzf-native]] to provide intelligent scoring and sorting.

This package is intended to be used with packages that leverage completion-styles, e.g. completing-read and completion-at-point-functions.

It is usable with icomplete (as well as fido-mode), selectrum, vertico, corfu, helm and company-mode.

It is not currently usable with ido which doesn't support completion-styles and has its own sorting and filtering system. ivy support can be somewhat baked in following https://github.com/jojojames/fussy#ivy-integration but the performance gains may not be as high as the other completion-read APIs.

  • Installation : M-x package-install RET fussy RET Or clone / download this repository and modify your load-path:

#+begin_src emacs-lisp :tangle yes (add-to-list 'load-path (expand-file-name "/path/to/fussy/" user-emacs-directory)) #+end_src ** Emacs -Q example #+begin_src emacs-lisp :tangle yes (add-to-list 'package-archives '("melpa" . "https://melpa.org/packages/")) (require 'package) (package-initialize) (package-refresh-contents)

(unless (package-installed-p 'fussy) (package-install 'fussy)) (fussy-setup) #+end_src ** Use-Package Example #+begin_src emacs-lisp :tangle yes ;; flx (use-package fussy :ensure t :config (fussy-setup)) #+end_src

or

#+begin_src emacs-lisp :tangle yes ;; fzf (use-package fzf-native :vc (:url "https://github.com/dangduc/fzf-native") :config (fzf-native-load-dyn))

(use-package fussy :config (fussy-setup-fzf) (fussy-eglot-setup) (fussy-company-setup)) #+end_src

Additional (listed below) scoring libraries can also be used. ** Flx [[https://github.com/lewang/flx][flx]] is a dependency of fussy and the default scoring algorithm.

flx has a great scoring algorithm but is one of the slower implementations compared to the other scoring backends written as native modules. ** Flx-rs [[https://github.com/jcs-elpa/flx-rs][flx-rs]] is a native module written in Rust that matches the original flx scoring algorithm. It is about 10 times faster than the original implementation written in Emacs Lisp. We can use this package instead for extra performance with the same scoring strategy.

One downside of this package is that it doesn't yet support using flx's file cache so filename matching is currently slightly worse than the original Emacs lisp implementation.

#+begin_src emacs-lisp :tangle yes (use-package flx-rs :ensure t :straight (flx-rs :repo "jcs-elpa/flx-rs" :fetcher github :files (:defaults "bin")) :config (setq fussy-score-fn 'fussy-flx-rs-score) (flx-rs-load-dyn)) #+end_src ** Fzf-Native Use [[https://github.com/dangduc/fzf-native][fzf-native]] for scoring.

Provides fuzzy matching scoring based on the fzf algorithm (by [[https://github.com/junegunn][junegunn]]) through a dynamic module for a native C implementation of fzf, [[https://github.com/nvim-telescope/telescope-fzf-native.nvim][telescope-fzf-native.nvim]].

#+begin_src emacs-lisp :tangle yes (use-package fzf-native :vc (:url "https://github.com/dangduc/fzf-native") :config (fzf-native-load-dyn)) #+end_src

** Fuz Another option is to use the [[https://github.com/rustify-emacs/fuz.el][fuz]] library (also in Rust) for scoring.

This library has two fuzzy matching algorithms, skim and clangd.

Skim: Just like [[https://github.com/junegunn/fzf][fzf]] v2, the algorithm is based on Smith-Waterman algorithm which is normally used in DNA sequence alignment

Clangd: The algorithm is based on clangd's [[https://github.com/MaskRay/ccls/blob/master/src/fuzzy_match.cc][FuzzyMatch.cpp]].

For more information: [[https://github.com/lotabout/fuzzy-matcher][fuzzy-matcher]]

#+begin_src emacs-lisp :tangle yes (use-package fuz :ensure nil :straight (fuz :type git :host github :repo "rustify-emacs/fuz.el") :config (setq fussy-score-fn 'fussy-fuz-score) (unless (require 'fuz-core nil t) (fuz-build-and-load-dymod))) #+end_src

For batch scoring using Rust/rayon parallelism, use fussy-fuz-score-all instead. It calls fuz-score-all-skim or fuz-score-all-clangd to score the entire candidate collection in a single call.

#+begin_src emacs-lisp :tangle yes (use-package fuz :ensure nil :straight (fuz :type git :host github :repo "rustify-emacs/fuz.el") :config (setq fussy-score-fn 'fussy-fuz-score-all) (unless (require 'fuz-core nil t) (fuz-build-and-load-dymod))) #+end_src

#+begin_src emacs-lisp :tangle yes ;; Same as fuz but with prebuilt binaries. (use-package fuz-bin :ensure t :straight (fuz-bin :repo "jcs-elpa/fuz-bin" :fetcher github :files (:defaults "bin")) :config (setq fussy-score-fn 'fussy-fuz-bin-score) (fuz-bin-load-dyn)) #+end_src ** Liquid Metal This is the algorithm used by the old [[https://www.emacswiki.org/emacs/lusty-explorer.el][lusty-explorer]].

A mimetic poly-alloy of the Quicksilver scoring algorithm, essentially LiquidMetal.

Flex matching short abbreviations against longer strings is a boon in productivity for typists. Applications like Quicksilver, Alfred, LaunchBar, and Launchy have made this method of keyboard entry a popular one. It's time to bring this same functionality to web controls. LiquidMetal makes scoring long strings against abbreviations easy.

For more information: [[https://github.com/rmm5t/liquidmetal][liquidmetal]]

#+begin_src emacs-lisp :tangle yes (use-package liquidmetal :ensure t :straight t :config (setq fussy-score-fn 'fussy-liquidmetal-score)) #+end_src

** Sublime-Fuzzy Fuzzy matching algorithm based on Sublime Text's string search. Iterates through characters of a search string and calculates a score. This is another fuzzy implementation written in Rust.

For more information: [[https://github.com/Schlechtwetterfront/fuzzy-rs][fuzzy-rs]]

#+begin_src emacs-lisp :tangle yes (use-package sublime-fuzzy :ensure t :straight (sublime-fuzzy :repo "jcs-elpa/sublime-fuzzy" :fetcher github :files (:defaults "bin")) :config (setq fussy-score-fn 'fussy-sublime-fuzzy-score) (sublime-fuzzy-load-dyn)) #+end_src ** Hotfuzz This is a fuzzy Emacs completion style similar to the built-in flex style, but with a better scoring algorithm. Specifically, it is non-greedy and ranks completions that match at word; path component; or camelCase boundaries higher.

For more information: [[https://github.com/axelf4/hotfuzz][hotfuzz]]

Note, hotfuzz has its own completion-style that may be worth using over this one.

#+begin_src emacs-lisp :tangle yes (use-package hotfuzz :ensure t :straight t :config (setq fussy-score-fn 'fussy-hotfuzz-score)) #+end_src

  • Recommendations fussy is written to be configure-less by the user. For defaults, it uses the built-in flex algorithm for filtering and flx for scoring and sorting.

However, users are encouraged to try the various available scoring backends. These scoring backends are configured through fussy-score-fn. See its docstring for configuration.

For improved performance, use a scoring backend backed by a native module. Examples include but are not limited to:

  • fzf-native [RECOMMENDED]
  • flx-rs
  • fuz/fuz-bin

flx-rs will provide an algorithm that matches the original flx algorithm while the other two matches other popular packages (skim and fzf).

Below is a sample config that uses flx-rs for improved performance.

fuz-bin or fuz may be a better choice for performance than flx-rs but uses a different algorithm.

#+begin_src emacs-lisp :tangle yes (use-package flx-rs :ensure t :straight (flx-rs :repo "jcs-elpa/flx-rs" :fetcher github :files (:defaults "bin")) :config (setq fussy-score-fn 'fussy-flx-rs-score) (flx-rs-load-dyn))

(use-package fussy :ensure t :straight (fussy :type git :host github :repo "jojojames/fussy") :config (setq fussy-score-fn 'fussy-flx-rs-score) (fussy-setup) (fussy-eglot-setup) (fussy-company-setup)) #+end_src

For the most performant option, use [[https://github.com/dangduc/fzf-native][fzf-native]] and see my configuration for an example. See Benchmarking below for basic runs.

  • My Configuration Documenting my configuration for the users that may want to copy. Unlike the former configuration, this section will be kept up to date with my init.el.

#+begin_src emacs-lisp :tangle yes (use-package fzf-native :vc (:url "https://github.com/dangduc/fzf-native") :config (fzf-native-load-dyn)))

(use-package fussy :vc (:url "https://github.com/jojojames/fussy") :config (setq fussy-compare-same-score-fn 'fussy-histlen->strlen<) (fussy-setup-fzf) (fussy-eglot-setup) (fussy-company-setup)) #+end_src

  • Scoring Samples Listed below are samples of scores that backends return given a candidate string and a search string to match against it. This may help in determining a preferred scoring backend. ** Flx

#+begin_src emacs-lisp :tangle yes (flx-score "Makefile" "mkfile") (281 0 2 4 5 6 7) (flx-score "fork/yasnippet-snippets/snippets/chef-mode/cookbook_file" "mkfile") (222 38 46 52 53 54 55) #+end_src ** Fuz #+begin_src emacs-lisp :tangle yes ;; candidate: Makefile query: mkfile score 77 ;; candidate: fork/yasnippet-snippets/snippets/chef-mode/cookbook_file query: mkfile score 68 #+end_src ** Fzf #+begin_src emacs-lisp :tangle yes ;; candidate: Makefile query: mkfile 118 ;; candidate: fork/yasnippet-snippets/snippets/chef-mode/cookbook_file query: mkfile 128 #+end_src

  • Filtering Choices Before scoring and sorting candidates, we must somehow filter them from the completion table. The approaches below are several ways to do that, each with varying advantages and disadvantages. ** Scoring This filtering method uses the configured fussy-score-fn (or fussy-score-ALL-fn) to filter candidates. This ensures that filtering is 1:1 with scoring, allowing for advanced pattern matching features specific to each backend to be used during the filtering phase. e.g. https://github.com/junegunn/fzf#search-syntax

#+begin_src emacs-lisp :tangle yes (setq fussy-filter-fn 'fussy-filter-by-scoring) #+end_src

** Flex This is the default filtering method and is 1:1 to the filtering done when using the flex completion-style. Advantages are no additional dependencies (e.g. orderless) and likely bug-free/stable to use.

The only disadvantage is that it's the slowest of the filtering methods.

#+begin_src emacs-lisp :tangle yes

;; Flex (setq fussy-filter-fn 'fussy-filter-flex) #+end_src

** Fast This is another usable filtering method and leverages the all-completions API written in C to do its filtering. It seems to be the fastest of the filtering methods from quick benchmarking as well as requiring no additional dependencies (e.g. orderless).

Implementation may be buggy though, so use with caution.

#+begin_src emacs-lisp :tangle yes ;; Fast (setq fussy-filter-fn 'fussy-filter-default) #+end_src ** Orderless [[https://github.com/oantolin/orderless][orderless]] can also be used for filtering. It uses the all-completions API like fussy-filter-default so is also faster than the default filtering but has a dependency on orderless.

#+begin_src emacs-lisp :tangle yes ;; Orderless (setq fussy-filter-fn 'fussy-filter-orderless-flex) #+end_src

To use [[https://github.com/oantolin/orderless][orderless]] filtering:

#+begin_src emacs-lisp :tangle yes (use-package orderless :straight t :ensure t :commands (orderless-filter))

(setq fussy-filter-fn 'fussy-filter-orderless)

;; Highlight matches with `company-mode'. (with-eval-after-load 'orderless ;; https://www.reddit.com/r/emacs/comments/nichkl/how_to_use_different_completion_styles_in_the/ ;; https://github.com/oantolin/orderless#company (defun orderless-just-one-face (fn &rest args) (let ((orderless-match-faces [completions-common-part])) (ignore orderless-match-faces) (apply fn args))) (advice-add 'company-capf--candidates :around #'orderless-just-one-face)) #+end_src

  • Caching Results and filtering can be cached for improved performance by setting fussy-use-cache to t.

With this set to t:

If user already entered the same query:

e.g. User types "a" -> "ab" and then backspaces into "a" again.

Results from the originally entered "a" will be used for the second entered "a".

If user is entering a new query but there exists results from a previous query in the cache:

e.g. User types "a" and then "ab". Results from "a" will then be used for filtering in "ab".

To use this with company and corfu, use an advice to reset the cache upon new completion requests.

#+begin_src emacs-lisp :tangle yes (advice-add 'corfu--capf-wrapper :before 'fussy-wipe-cache) (fussy-company-setup) #+end_src

  • Benchmarking On a Macbook Air M5.

#+begin_src emacs-lisp :tangle yes (setq random-col (all-completions "" 'help--symbol-completion-table nil))

(benchmark-run 10 (dolist (x random-col) (flx-score x "a"))) (4.52991 29 1.269130000000004)

(benchmark-run 10 (dolist (x random-col) (fussy-fzf-native-score x "a"))) (1.298745 2 0.08969299999999691)

;; Handles entire list at once. (benchmark-run 10 (fussy-fzf-score random-col "a")) (0.123468 0 0.0) #+end_src

Using https://github.com/jojojames/emacs-completion-bench

| Style | Time (s) | #GC | GC time (s) | Rel | |--------------------------------------------+----------+-----+-------------+-------| | basic (sort-fn: off) | 0.063761 | 0 | 0.000000 | 1.00 | | hotfuzz (sort-fn: off) | 0.130336 | 0 | 0.000000 | 2.04 | | fussy / fzf-score / default (off) | 0.186001 | 0 | 0.000000 | 2.92 | | fussy / fzf-score / by-scoring (off) | 0.289635 | 0 | 0.000000 | 4.54 | | orderless (off) | 0.325188 | 0 | 0.000000 | 5.10 | | substring (off) | 0.632855 | 0 | 0.000000 | 9.92 | | fussy / fuz-bin (on) | 0.635636 | 0 | 0.000000 | 9.97 | | orderless + flex (off) | 0.844695 | 0 | 0.000000 | 13.25 | | fussy / fzf-native (on) | 0.855334 | 0 | 0.000000 | 13.42 | | fussy / flx (on) | 1.384747 | 2 | 0.177668 | 21.71 | | flex (off) | 1.957198 | 0 | 0.000000 | 30.69 | | fussy / flx-rs (on) | 4.017352 | 0 | 0.000000 | 63.00 |

  • Integrations ** Eglot Integration

#+begin_src emacs-lisp :tangle yes (fussy-eglot-setup) #+end_src

** Company Integration Call fussy-company-setup. This function advises a few company-mode functions. #+begin_src emacs-lisp :tangle yes (fussy-company-setup) #+end_src ** Icomplete/Fido Integration fido uses the built in flex completion-style by default. We can advise icomplete's setup hook to set up fussy with fido-mode.

#+begin_src emacs-lisp :tangle yes (use-package icomplete :ensure nil :straight nil :config (defun fussy-fido-setup () "Use fussy' with fido-mode'." (setq-local completion-styles '(fussy basic))) (advice-add 'icomplete--fido-mode-setup :after 'fussy-fido-setup) (setq icomplete-tidy-shadowed-file-names t icomplete-show-matches-on-no-input t icomplete-compute-delay 0 icomplete-delay-completions-threshold 50) ;; Or `fido-mode'. (fido-vertical-mode)) #+end_src ** Corfu Integration #+begin_src emacs-lisp :tangle yes ;; For cache functionality. (advice-add 'corfu--capf-wrapper :before 'fussy-wipe-cache)

(add-hook 'corfu-mode-hook (lambda () (setq-local fussy-max-candidate-limit 5000 fussy-default-regex-fn 'fussy-pattern-first-letter fussy-prefer-prefix nil))) #+end_src ** Orderless orderless can be used as the filtering function and paired with another scoring function. There may be incompatibilities between what orderless uses and what the scoring backend uses.

#+begin_src emacs-lisp :tangle yes (use-package orderless :straight t :ensure t :commands (orderless-filter))

(setq fussy-filter-fn 'fussy-filter-orderless) ;; or `fussy-filter-orderless-flex' #+end_src ** Helm Integration Integration with [[https://github.com/emacs-helm/helm][helm]] is possible by setting helm-completion-style to emacs instead of helm.

#+begin_src emacs-lisp :tangle yes (setq helm-completion-style 'emacs) #+end_src

For more information: https://github.com/emacs-helm/helm/blob/master/helm-mode.el#L269

** Ivy Integration Since ivy doesn't support completion-styles, we have to hack fussy into it. We can advise ivy--flx-sort and replace it with our own sorting function.

#+begin_src emacs-lisp :tangle yes (defun ivy--fussy-sort (name cands) "Sort according to closeness to string NAME the string list CANDS." (condition-case nil (let* ((bolp (= (string-to-char name) ?^)) ;; An optimized regex for fuzzy matching ;; "abc" → "^[^a]*a[^b]*b[^c]c" (fuzzy-regex (concat "\`" (and bolp (regexp-quote (substring name 1 2))) (mapconcat (lambda (x) (setq x (char-to-string x)) (concat "[^" x "]" (regexp-quote x))) (if bolp (substring name 2) name) ""))) ;; Strip off the leading "^" for flx matching (flx-name (if bolp (substring name 1) name)) cands-left cands-to-sort)

      ;; Filter out non-matching candidates
      (dolist (cand cands)
        (when (string-match-p fuzzy-regex cand)
          (push cand cands-left)))

      ;; pre-sort the candidates by length before partitioning
      (setq cands-left (cl-sort cands-left #'< :key #'length))

      ;; partition the candidates into sorted and unsorted groups
      (dotimes (_ (min (length cands-left) ivy-flx-limit))
        (push (pop cands-left) cands-to-sort))

      (nconc
       ;; Compute all of the flx scores in one pass and sort
       (mapcar #'car
               (sort (mapcar
                      (lambda (cand)
                        (cons cand
                              (car
                               (funcall
                                fussy-score-fn
                                cand flx-name
                                ivy--flx-cache))))
                      cands-to-sort)
                     (lambda (c1 c2)
                       ;; Break ties by length
                       (if (/= (cdr c1) (cdr c2))
                           (> (cdr c1)
                              (cdr c2))
                         (< (length (car c1))
                            (length (car c2)))))))
       ;; Add the unsorted candidates
       cands-left))
  (error cands)))

(advice-add 'ivy--flx-sort :override 'ivy--fussy-sort) #+end_src

For more information: https://github.com/abo-abo/swiper/issues/848#issuecomment-1143129670

  • Contributing Set up eask.

#+begin_src sh :tangle yes $ brew install node $ npm install -g @emacs-eask/eask #+end_src #+begin_src emacs-lisp :tangle yes make test #+end_src

Back to Emacs