;;; fussy.el --- Fuzzy completion style using `flx' and/or `fzf-native' -*- lexical-binding: t; -*-

;; Copyright 2022 James Nguyen

;; Author: James Nguyen <james@jojojames.com>
;; Package-Version: 20260613.1231
;; Package-Revision: 78730ceefb23
;; Package-Requires: ((emacs "29.1") (flx "0.5") (compat "30.0.0.0"))
;; Keywords: matching
;; Homepage: https://github.com/jojojames/fussy

;; 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 <http://www.gnu.org/licenses/>.

;;; Commentary:

;; This is a fuzzy Emacs completion style similar to the built-in
;; `flex' style, but using `flx' (or `fzf-native') for scoring.
;; It also supports various other fuzzy scoring systems in place of those two.

;; 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''s `company-capf'.

;; It is not currently usable with `ido' which doesn't support
;; `completion-styles' and has its own sorting and filtering system.  In
;; addition to those packages, other `company-mode' backends will not hook into
;; this package.  `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.

;; To use this style, prepend `fussy' to `completion-styles'.

;; For improved performance,`fussy-filter-fn' and `fussy-score-fn' for filtering
;; and scoring matches are good initial starting points for customization.

;; The various available scoring backends in `fussy-score-fn' have varying
;; levels of performance and match quality.
;; For a faster version that implements the same matching as `flx', use
;; https://github.com/jcs-elpa/flx-rs which is a native module written in Rust.

;; Other notable scoring backends supported by this package:
;; flx: https://github.com/lewang/flx
;; fzf: https://github.com/junegunn/fzf
;;   (e.g. https://github.com/dangduc/fzf-native)
;; skim: https://github.com/lotabout/fuzzy-matcher

;; For an exhaustive list of scoring backends, take a look at
;; https://github.com/jojojames/fussy#scoring-backends

(require 'flx)
(require 'compat)
(eval-when-compile (require 'subr-x))

;;; Code:

(defvar fzf-native-case-mode)
(defvar fzf-native-fuzzy)
(defvar fzf-native-batch-highlight)
(defvar fzf-native-filter-only-length)
(defvar fzf-native-filter-only-logic)
(defvar ivy-re-builders-alist)

;;
;; (@* "Landmarks" )
;;

;; `fussy-all-completions'
;; `fussy-score'
;; `fussy-filter-default'

;;
;; (@* "Customizations" )
;;

(defgroup fussy nil
  "Fuzzy completion style using `flx.'."
  :group 'flx
  :link '(url-link :tag "GitHub" "https://github.com/jojojames/fussy"))

(defcustom fussy-max-query-length 100
  "Collections with queries longer than this are not scored using `flx'.

See `fussy-all-completions' for implementation details."
  :group 'fussy
  :type 'integer)

(defcustom fussy-max-candidate-limit 30000
  "Apply optimizations for collections greater than this limit.

`fussy-all-completions' will apply some optimizations.

N -> this variable's value

1. The collection (to be scored) will initially be filtered based on
 `fussy-max-limit-preferred-candidate-fn'.

2. Score only up to N * `fussy-percent-of-candidates-to-score' words.
The rest won't be scored.

Additional implementation details:
https://github.com/abo-abo/swiper/issues/207#issuecomment-141541960"
  :group 'fussy
  :type 'integer)

(defcustom fussy-percent-of-candidates-to-score .7
  "When `fussy-max-candidate-limit' is hit, this variable determines the %
of candidates out of all candidates to score. For example, if
`fussy-max-candidate-limit' is 30000 and the collection is 40000, the # of
candidates to score will be 28000."
  :group 'fussy
  :type 'number)

(defcustom fussy-ignore-case t
  "If t, ignores `completion-ignore-case'.

If this is set to nil, highlighting may break for cases where we're
highlighting with `completion-pcm--hilit-commonality'."
  :group 'fussy
  :type 'boolean)

(defcustom fussy-fzf-case-mode 'smart
  "Case-sensitivity mode propagated to `fzf-native-case-mode'.
Mirrors fzf-native's enum:
smart    Case-insensitive when the query is all lowercase; case-sensitive
         once it contains any uppercase character (fzf's default).
ignore   Always case-insensitive.
respect  Always case-sensitive.

Applied via `setq-local' inside `fussy-all-completions-v1' when
`fussy-ignore-case' is non-nil, alongside `completion-ignore-case'.
Only meaningful when `fussy-score-ALL-fn' is `fussy-fzf-score'."
  :group 'fussy
  :type '(choice (const :tag "Smart case (default)" smart)
                 (const :tag "Ignore case"          ignore)
                 (const :tag "Respect case"         respect)))

(defcustom fussy-fzf-fuzzy t
  "Whether to fuzzy match with `fzf-native'.

If t, use fuzzy matching, if nil, use exact/substring matching.

If t, prefixing a term with ' switches that term to exact matching.

If nil, prefixing a term with ' switches that term to fuzzy matching.

Read at the start of every scoring call.

Propagated to `fzf-native-fuzzy' via `setq-local' inside
`fussy-all-completions-v1'.  Only meaningful when `fussy-score-ALL-fn'
is `fussy-fzf-score'."
  :group 'fussy
  :type 'boolean)

(defcustom fussy-score-threshold-to-filter nil
  "Candidates with scores of N or less are filtered.

Some backends such as `fussy-fuz-score' return negative scores
for low-quality matches.

If this is set to nil, threshold is defined by alist of
thresholds for score functions. Set this to a number to override
`fussy-score-threshold-to-filter-alist'.

Raise N to see fewer candidates. Lower N to see more
candidates. Keep N at 0 or more for performance."
  :group 'fussy
  :type 'integer)

(defcustom fussy-score-threshold-to-filter-alist
  '((flx-score . -100)
    (fussy-flx-rs-score . -100)
    (fussy-fuz-score . -100)
    (fussy-fuz-bin-score . -100)
    (fussy-hotfuzz-score . 0))
  "Candidates with scores of N or less are filtered for a given
`fussy-score-fn'.

Some backends such as `fussy-fuz-score' return negative scores
for low-quality matches.

Setting `fussy-score-threshold-to-filter' to a number will
override this alist.

If `fussy-score-fn' is not in the mapping, default to a threshold
of 0 wherever alist is used."
  :group 'fussy
  :type 'alist)

(defcustom fussy-max-word-length-to-score 400
  "Words that are longer than this length are not scored."
  :group 'fussy
  :type 'integer)

(defcustom fussy-propertize-fn
  #'fussy-propertize-common-part
  "Function used to propertize matches.

Takes STR \(to be propertized\) and
SCORE \(list of indices of STR to be propertized\).

This function is expected to return STR.

If this is nil, don't propertize (e.g. highlight matches) at all.
This can also be set to nil to assume highlighting from a different source."
  :type `(choice
          (const :tag "No highlighting" nil)
          (const :tag "By completions-common face."
                 ,#'fussy-propertize-common-part)
          (const :tag "By flx propertization." ,'flx-propertize)
          (function :tag "Custom function"))
  :group 'fussy)

(defcustom fussy-compare-same-score-fn
  #'fussy-histlen->strlen<
  "Function used to compare matches with the same \\='completion-score.

FN takes in and compares two candidate strings C1 and C2 and
returns which candidates should have precedence.

If this is nil, do nothing."
  :type `(choice
          (const :tag "Don't compare candidates with same score." nil)
          (const :tag "Shorter candidates have precedence."
                 ,#'fussy-strlen<)
          (const :tag "Longer candidates have precedence."
                 ,#'fussy-strlen>)
          (const :tag "Recent candidates have precedence."
                 ,#'fussy-histlen<)
          (const :tag "Recent (then shorter length) candidates have precedence."
                 ,#'fussy-histlen->strlen<)
          (function :tag "Custom function"))
  :group 'fussy)

(defcustom fussy-default-sort-fn
  #'fussy-histlen->strlen<
  "Function used to sort matches when not filtering.

If this is nil, do nothing."
  :type `(choice
          (const :tag "Don't sort candidates." nil)
          (const :tag "Shorter candidates have precedence."
                 ,#'fussy-strlen<)
          (const :tag "Longer candidates have precedence."
                 ,#'fussy-strlen>)
          (const :tag "Recent candidates have precedence."
                 ,#'fussy-histlen<)
          (const :tag "Recent (then shorter length) candidates have precedence."
                 ,#'fussy-histlen->strlen<)
          (function :tag "Custom function"))
  :group 'fussy)

(defcustom fussy-max-limit-preferred-candidate-fn nil
  "Function used when collection length is greater than\

`fussy-max-candidate-limit'.

FN takes in and compares two candidate strings C1 and C2 and
returns which candidates should have precedence.

If this is nil, take the first `fussy-max-candidate-limit' number
of candidates that was returned by the completion table."
  :type `(choice
          (const :tag "Take the first X number of candidates." nil)
          (const :tag "Shorter candidates have precedence."
                 ,#'fussy-strlen<)
          (const :tag "Longer candidates have precedence."
                 ,#'fussy-strlen>)
          (const :tag "Recent candidates have precedence."
                 ,#'fussy-histlen<)
          (const :tag "Recent (then shorter length) candidates have precedence."
                 ,#'fussy-histlen->strlen<)
          (function :tag "Custom function"))
  :group 'fussy)

(defcustom fussy-filter-fn
  #'fussy-filter-flex
  "Function used for filtering candidates before scoring.

FN takes in the same arguments as `fussy-try-completions'.

This FN should not be nil.

Use `fussy-filter-default' for faster filtering through the
`all-completions' (written in C) interface.

If using `fussy-filter-default', `fussy-default-regex-fn' can be configured."
  :type `(choice
          (const :tag "Built in Flex Filtering"
                 ,#'fussy-filter-flex)
          (const :tag "Built in Faster Flex Filtering in C"
                 ,#'fussy-filter-default)
          (const :tag "By Scoring"
                 ,#'fussy-filter-by-scoring)
          (function :tag "Custom function"))
  :group 'fussy)

(defcustom fussy-default-regex-fn
  #'fussy-pattern-default
  "Function used to create regex for `fussy-filter-default'.

It takes in a STR and returns a regex usable with `all-completions'.

The return value of this FN is meant to be pushed to `completion-regexp-list'.

Flex 1 is what is used in `company-flx'.  It seems to be the fastest from an eye
test but all the regex are comparable in performance.

Flex 2 functions match the regex returned by `orderless-flex'.  Flex 2 functions
are more exhaustive than Flex 1 functions."
  :type `(choice
          (const :tag "Flex 1"
                 ,#'fussy-pattern-flex-1)
          (const :tag "Flex 2"
                 ,#'fussy-pattern-flex-2)
          (const :tag "Default"
                 ,#'fussy-pattern-default)
          (const :tag "First Letter"
                 ,#'fussy-pattern-first-letter)
          (const :tag "None"
                 ,#'fussy-pattern-default-to-backend)
          (function :tag "Custom function"))
  :group 'fussy)

(defcustom fussy-score-fn
  'flx-score
  "Function used for scoring candidates.

FN should at least take in STR and QUERY.

This may or may not be used by `fussy-score-ALL-fn'."
  :type `(choice
          (const :tag "Score using Flx"
                 ,'flx-score)
          (const :tag "Score using Flx-RS"
                 ,#'fussy-flx-rs-score)
          (const :tag "Score using Fuz"
                 ,#'fussy-fuz-score)
          (const :tag "Score using Fuz-Bin"
                 ,#'fussy-fuz-bin-score)
          (const :tag "Score using LiquidMetal"
                 ,#'fussy-liquidmetal-score)
          (const :tag "Score using Sublime-Fuzzy"
                 ,#'fussy-sublime-fuzzy-score)
          (const :tag "Score using Hotfuzz"
                 ,#'fussy-hotfuzz-score)
          (function :tag "Custom function"))
  :group 'fussy)

(defcustom fussy-AND-component-separator nil
  "Separator used to split the query string into AND components.
This mirrors `orderless-component-separator' and can be either:
- A regexp string passed to `split-string', e.g. \"[ &]\" to split on
  spaces or ampersands.
- A function that takes a string and returns a list of component strings,
  e.g. `orderless-escapable-split-on-space'.
When non-nil, the query is split on this separator and the resulting
components are rejoined with spaces (AND semantics) before being passed
to the scoring backend.  This is useful for in-buffer completion
(e.g. `company-mode') where pressing SPC would otherwise dismiss the
completion UI, allowing you to use a different separator character
(e.g. \"&\") for multi-token AND queries.
See also `fussy-OR-component-separator' for OR semantics.
When nil (the default), the query is passed to the scoring backend as-is.
Example:
  ;; Use & as an AND separator in addition to space:
  (setq fussy-AND-component-separator \"[ &]+\")
  ;; Or with a custom function matching orderless behavior:
  (setq fussy-AND-component-separator #\='orderless-escapable-split-on-space)"
  :type `(choice
          (const :tag "No separator (disabled)" nil)
          (string :tag "Regexp separator, e.g. \\"[ &]+\\"")
          (const :tag "Spaces" " +")
          (const :tag "Spaces, hyphen or slash" " +\\|[-/]")
          (function :tag "Custom function"))
  :group 'fussy)

(defcustom fussy-OR-component-separator nil
  "Separator used to split the query string into OR groups.
Can be either:
- A regexp string passed to `split-string', e.g. \"|\" or \"[ |]+\".
- A function that takes a string and returns a list of OR-group strings.
When non-nil, the query is first split on this separator into OR groups.
Each OR group is then processed by `fussy-AND-component-separator' (if set)
to produce AND components within the group.  OR groups are rejoined with
\" | \" which `fzf-native' understands natively as OR.
This maps to fzf's native | operator:
  e.g. \"d | x\" matches candidates containing either \"d\" OR \"x\".
       \"d x\" matches candidates containing both \"d\" AND \"x\".
Only meaningful when `fussy-score-ALL-fn' is `fussy-fzf-score', since
other backends do not understand the | OR operator.
Example — use | for OR and & for AND within each OR group:
  (setq fussy-OR-component-separator \"|\")    ;; split on |
  (setq fussy-AND-component-separator \"[ &]+\") ;; AND within each group
  ;; Typing \"abc&def|ghi\" scores as fzf query \"abc def | ghi\"
  ;; i.e. (abc AND def) OR ghi"
  :type `(choice
          (const :tag "No OR separator (disabled)" nil)
          (string :tag "Regexp OR separator, e.g. \\\"|\\\"")
          (function :tag "Custom function"))
  :group 'fussy)

(defcustom fussy-score-ALL-fn 'fussy-score
  "Function used for score ALL candidates.

FN should take in ARGS: candidates string &optional cache.

This function may call out to `fussy-score-fn' to score matches or
does the heavy lifting itself.

For example `fussy-score' makes use of `fussy-score-fn' but
`fussy-fzf-score' sends its entire collection to `fzf-native' instead."
  :type `(choice
          (const :tag "Default scoring"
                 ,'fussy-score)
          (const :tag "Scoring using `fzf-native-score-all'."
                 ,#'fussy-fzf-score)
          (const :tag "Scoring using `fuz-score-all-skim' or `fuz-score-all-clangd'."
                 ,#'fussy-fuz-score-all)
          (function :tag "Custom function"))
  :group 'fussy)

(defcustom fussy-fuz-use-skim-p t
  "If t, use skim fuzzy matching algorithm with `fuz'.

If nil, use clangd fuzzy matching algorithm with `fuz'.

This boolean is only used if `fussy-fuz-score' is the `fussy-score-fn'."
  :group 'fussy
  :type 'boolean)

(defcustom fussy-score-fns-without-indices '(fussy-hotfuzz-score
                                             fussy-sublime-fuzzy-score
                                             fussy-liquidmetal-score)
  "List of scoring functions that only returns the score.

e.g. Instead of returning LIST SCORE MATCH_1 MATCH_2 which something like
`flx-score' does, it returns LIST SCORE.

Scoring functions in this list's highlighting are then taken care of by

`completion-pcm--hilit-commonality'.  See `fussy--use-pcm-highlight-p'.

Functions in this list should match `fussy-score-fn'."
  :type '(list function)
  :group 'fussy)

(defcustom fussy-fzf-native-highlight 25
  "Control C-layer match highlighting for fzf-native scoring.

The C function `fzf-native-score-all' reads this variable directly
via `symbol-value' and applies `completions-common-part' face to
candidate strings.

Default is 25 but this can easily be pushed to every candidate for tiny
latency cost.

Values:
  nil       — No highlighting.
  t         — Highlight all matched candidates.
  N (integer) — Highlight only the top N best-scoring candidates."
  :group 'fussy
  :type '(choice
          (const :tag "Disabled" nil)
          (const :tag "All candidates" t)
          (integer :tag "Top N candidates" 25)))

(defcustom fussy-prefer-prefix t
  "When using `fussy-filter-default', whether to prefer infix or prefix.

If t, prefix is used with `all-completions', if nil, use infix.

Infix is generally faster for `all-completions' but is not exhaustive.
Prefix can be slower but is exhaustive. For `completing-read',exhaustive
filtering is generally more preferable but for `completion-at-point-functions',
using infix can be a good tradeoff.

This variable should be let-bound/wrapped over `completion-at-point-functions',
e.g. `company-capf' and set to nil for typing performance and kept to t for
normal `completing-read' scenarios.

See comments in `fussy-filter-default' for examples of what infix or prefix
can look like."
  :type 'boolean
  :group 'fussy)

(defcustom fussy-filter-unscored-candidates t
  "Whether or not to filter unscored candidates.

This only applies when `fussy-max-candidate-limit' is reached."
  :type 'boolean
  :group 'fussy)

(defcustom fussy-use-cache nil
  "Whether or not to use cache in `fussy-all-completions'."
  :type 'boolean
  :group 'fussy)

(defcustom fussy-company-prefix-length 0
  "The prefix length before using `fussy' with `company'."
  :group 'fussy
  :type 'integer)

(defcustom fussy-company-filter-only-length nil
  "Prefix length below which `fussy-company--fetch-candidates' takes the
fzf-native filter-only path.

When set to a positive integer N, *overrides* `fussy-company-prefix-length':
prefixes strictly shorter than N take the filter-only path instead of
the bypass — fussy stays in `completion-styles' and the C side runs the
cheap `fzf_has_match' filter.

  fussy-company-prefix-length    : first N-1 chars *skip fussy altogether*.
  fussy-company-filter-only-length: first N-1 chars run fussy in filter-only
                                    mode (cheap match, no DP scoring).

Set to nil to disable the override and fall back to the bypass behaviour.
Only meaningful when `fussy-score-ALL-fn' is `fussy-fzf-score'."
  :group 'fussy
  :type '(choice (const :tag "Disabled (use bypass)" nil)
                 (integer :tag "Max prefix length for filter-only")))

(defcustom fussy-company-gc-cons-threshold (* 128 1024 1024)
  "Floor for `gc-cons-threshold' during `fussy-company--fetch-candidates'.

`fussy-company--fetch-candidates' raises `gc-cons-threshold' to at
least this value for the duration of the fetch, so GC defers to a
natural pause between input bursts rather than firing mid-keystroke.

If you already set `gc-cons-threshold' globally higher (e.g. via the
`gcmh' package), the higher value wins — the binding uses `max'.

Set to 0 to opt out of the bump entirely."
  :group 'fussy
  :type 'integer)

;;;###autoload
(defcustom fussy-adjust-metadata-fn
  #'fussy--adjust-metadata
  "Used for `completion--adjust-metadata' to adjust completion metadata.

`completion--adjust-metadata' is what is used to set up sorting of candidates
based on `completion-score'.  The default `flex' completion style in
`completion-styles' uses `completion--flex-adjust-metadata' which respects
the original completion table's sort functions:

  e.g. display-sort-function, cycle-sort-function

The default of `fussy-adjust-metadata-fn' is used instead to ignore
existing sort functions in favor of sorting based only on the scoring done by
`fussy-score-fn'."
  :type `(choice
          (const :tag "Adjust metadata using fussy."
                 ,#'fussy--adjust-metadata)
          (const :tag "Adjust metadata using flex."
                 ,#'completion--flex-adjust-metadata)
          (function :tag "Custom function"))
  :group 'fussy)

(defmacro fussy--measure-time (&rest body)
  "Measure the time it takes to evaluate BODY.
https://lists.gnu.org/archive/html/help-gnu-emacs/2008-06/msg00087.html"
  `(let ((time (current-time)))
     (let ((result ,@body))
       (message "%.06f" (float-time (time-since time)))
       result)))

(defcustom fussy-debug nil
  "When non-nil, emit debug messages via `fussy--debug'."
  :group 'fussy
  :type 'boolean)

(defsubst fussy--debug (format-string &rest args)
  "Emit a `fussy' debug message when `fussy-debug' is non-nil.
FORMAT-STRING and ARGS are passed to `message'."
  (when fussy-debug
    (apply #'message (concat "[fussy] " format-string) args)))

;;
;; (@* "Constants and Variables" )
;;

(defvar completion-lazy-hilit)
(defvar completion-lazy-hilit-fn)

(defvar-local fussy--hist-hash nil
  "Hash table representing `minibuffer-history-variable'.

KEYs are values in the list.
VALUES are positions of the values in the list.

See `fussy--history-hash-table'.")

(defvar-local fussy--hist-hash-last-val nil
  "Last value of the history variable used to build `fussy--hist-hash'.")

(defvar-local fussy--score-threshold-to-filter-alist-cache nil
  "Cached value of threshold derived from alist for score functions.

If `fussy-score-threshold-to-filter' is non-nil, the cache is
ignored.

See `fussy-score-threshold-to-filter-alist'.")

(defvar-local fussy--all-cache nil
  "Hash table representing a cache for `fussy-all-completions'.")

(defvar fussy--last-was-filter-only)

(defsubst fussy--needs-hist-hash-p ()
  "Whether `fussy-compare-same-score-fn' actually reads history.

Used to skip building `fussy--hist-hash' when the active tie-breaker
doesn't consult `minibuffer-history-variable'."
  (memq fussy-compare-same-score-fn
        '(fussy-histlen< fussy-histlen->strlen<)))

;;
;; (@* "All Completions Interface/API" )
;;

;;;###autoload
(defun fussy-try-completions (string table pred point)
  "Try to flex-complete STRING in TABLE given PRED and POINT.

Implement `try-completions' interface by using `completion-flex-try-completion'."
  (fussy--debug "called `fussy-try-completions'...")
  (completion-flex-try-completion string table pred point))

(defvar-local fussy--current-result nil
  "Current result of `fussy-all-completions'.")
(defvar-local fussy--current-prefix nil
  "Current prefix of `fussy-all-completions'.")
(defvar-local fussy--current-infix nil
  "Current infix of `fussy-all-completions'.")
(defvar fussy--filtering-p nil
  "Is `fussy' filtering currently?")

(defcustom fussy-cancel-on-input-fn #'minibufferp
  "Predicate deciding whether `fussy-all-completions' is abortable.

When this returns non-nil the call is wrapped in `while-no-input'
and a fresh keystroke arriving mid-fetch returns the previous
result tagged with the new prefix.  Right for large
`completing-read'-driven collections (vertico, ivy, icomplete,
default `*Completions*').

When this returns nil the call runs synchronously and Emacs's
input loop queues keystrokes for after it returns — same model
`completion-flex-all-completions' uses.  Right for in-buffer
completion (`company-mode' popup, `corfu'), where the abort path
otherwise flickers the popup with stale results during fast typing.

Default `minibufferp' matches that split exactly."
  :type 'function
  :group 'fussy)

;;;###autoload
(defun fussy-all-completions (string table pred point)
  "Run `fussy-all-completions-v1', optionally wrapped in `while-no-input'.

Wrapping is gated by `fussy-cancel-on-input-fn'.

If another input arrived -> t -> return current result.
If input was cancelled -> nil -> return nil.
If result came back -> :default -> return result."
  (pcase
      (if (funcall fussy-cancel-on-input-fn)
          (while-no-input (fussy-all-completions-v1 string table pred point))
        (fussy-all-completions-v1 string table pred point))
    ('nil
     (fussy--debug "fn: %S nil" 'fussy-all-completions)
     nil)
    ('t
     (fussy--debug "fn: %S quoteT" 'fussy-all-completions)
     (when (consp fussy--current-result)
       (nconc fussy--current-result (length fussy--current-prefix))))
    (`,collection
     ;; Collection can be 0 when there are no candidates returned.
     (when (consp collection)
       (let ((base-size (length fussy--current-prefix)))
         (when fussy-use-cache
           (fussy--debug "putting %s into hash with coll length %s"
                         string (length collection))
           (puthash string (cl-copy-list collection)
                    fussy--all-cache))
         (if (> base-size 0)
             (nconc collection base-size)
           collection))))))

;;;###autoload
(defun fussy-all-completions-v1 (string table pred point)
  "Get flex-completions of STRING in TABLE, given PRED and POINT.

Implement `all-completions' interface with additional fuzzy / `flx' scoring."
  (fussy--debug "called `fussy-all-completions'...")
  (when (fussy--fzf-p)
    (fussy--ensure-fzf-loaded))
  (setf fussy--current-result nil)
  (when (fussy--needs-hist-hash-p)
    (setf fussy--hist-hash (fussy--history-hash-table)))
  (when (and fussy-use-cache
             (or
              (not fussy--all-cache)
              (equal string "")))
    (setf fussy--all-cache
          (make-hash-table :test 'equal)))
  (when fussy-ignore-case
    ;; `completion-ignore-case' is usually set up in `minibuffer-with-setup-hook'.
    ;; e.g. `read-file-name-default'
    ;; Many search functions leverage this variable. In the case of fuzzy
    ;; matching, it is better to match insensitively.
    ;; For example, the implementation of `completion-pcm--hilit-commonality'
    ;; uses `case-fold-search' which sets its value to `completion-ignore-case'.
    ;; Other examples include `completion-pcm--all-completions' which is used by
    ;; `fussy-filter-flex'. `all-completions' also uses this variable.
    (setq-local completion-ignore-case t))
  ;; Propagate to fzf-native's per-call case mode so the C scorer matches
  ;; the elisp-side case treatment.
  (setq-local fzf-native-case-mode fussy-fzf-case-mode)
  (setq-local fzf-native-fuzzy fussy-fzf-fuzzy)
  (setq-local fzf-native-batch-highlight fussy-fzf-native-highlight)
  (let* ((metadata (completion-metadata string table pred))
         (cache (if (memq (completion-metadata-get metadata 'category)
                          '(file
                            project-file))
                    flx-file-cache
                  flx-strings-cache))
         (beforepoint (substring string 0 point))
         (afterpoint (substring string point))
         (bounds (completion-boundaries beforepoint table pred afterpoint))
         (prefix (substring beforepoint 0 (car bounds)))
         (infix (concat
                 (substring beforepoint (car bounds))
                 (substring afterpoint 0 (cdr bounds)))))
    (setf fussy--filtering-p (not (string= infix "")))
    (setf fussy--current-prefix prefix)
    (setf fussy--current-infix infix)
    ;; Lazy-hilit opt-in: when the frontend has requested lazy highlighting
    ;; (vertico, icomplete on Emacs 28+ bind `completion-lazy-hilit'), set
    ;; `completion-lazy-hilit-fn' so face is applied per /visible/ candidate
    ;; at render time rather than eagerly across the top-N.
    ;;
    ;; The fzf path needs an explicit set — `fzf-native-highlight-all' is
    ;; eager-only.  The pcm path is left alone: Emacs's own
    ;; `completion-pcm--hilit-commonality' (called downstream via
    ;; `fussy--pcm-highlight') sets the lazy fn itself when invoked.  Non-fzf
    ;; non-pcm backends keep eager (see Chunk 8 in fzfa's sort-hilit-design).
    ;;
    ;; `infix' is captured lexically — sidesteps the buffer-local
    ;; `fussy--current-infix'.  Vertico's `vertico--hilit' passes the
    ;; `completion--unquoted' string for file completion (Emacs bug#77754),
    ;; so face lands on whichever variant is actually displayed.
    (when (and (bound-and-true-p completion-lazy-hilit)
               fussy-propertize-fn
               (fussy--fzf-p)
               (fboundp 'fzf-native-highlight-one)
               (not (string-empty-p infix)))
      (let ((query infix))
        (setq completion-lazy-hilit-fn
              (lambda (cand)
                (fzf-native-highlight-one cand query)))))
    (if-let* ((cached-all (and fussy-use-cache
                               (cl-copy-list
                                (gethash string fussy--all-cache)))))
        (progn
          (setf fussy--current-result cached-all)
          (fussy--debug "%s from hash with length %d"
                        string (length cached-all))
          (fussy--highlight-collection
           (if (fussy--fzf-p) infix
             (fussy--recreate-regex-pattern
              beforepoint afterpoint bounds))
           cached-all)
          cached-all)
      (pcase-let*
          ((`(,all ,pattern ,_prefix)
            (if-let* ((cached-all
                       (and
                        (fussy--use-cache-instead-of-filter-p string)
                        (cl-copy-list
                         (gethash
                          (substring string 0 (- (length string) 1))
                          fussy--all-cache)))))
                (let* ((_ (setf fussy--current-result cached-all))
                       (pattern (fussy--recreate-regex-pattern
                                 beforepoint afterpoint bounds))
                       (candidates (if (fussy--filter-by-scoring-p)
                                       (fussy-outer-score cached-all infix cache)
                                     cached-all)))
                  (fussy--debug "using cache for filter")
                  (setf fussy--current-result candidates)
                  (list candidates pattern prefix))
              (funcall fussy-filter-fn
                       string table pred point))))
        (fussy--debug
         "fn: %S string: %s prefix: %s infix: %s all: %S pattern: %s"
         'fussy-all-completions
         string prefix infix (or all '("nada")) pattern)
        (when all
          (setf fussy--current-result all)
          (if (or (length> infix fussy-max-query-length)
                  (fussy--filter-by-scoring-p) ;; We don't need to score again.
                  (string= infix ""))
              (progn
                (if (fussy--fzf-p)
                    ;; `fussy--sort' (wrapped by
                    ;; `fussy-fzf--sort-highlight-advice') will re-highlight
                    ;; the post-sort top-N for the full-scoring case. Only
                    ;; highlight here when filter-only is the active path,
                    ;; since `fussy--adjust-metadata' skips installing
                    ;; `fussy--sort' in that case and no later highlight
                    ;; pass will run.
                    (when fussy--last-was-filter-only
                      (fussy--highlight-collection infix all))
                  (fussy--highlight-collection pattern all))
                all)
            (if (length< all fussy-max-candidate-limit)
                (fussy--highlight-collection
                 pattern
                 (fussy-outer-score all infix cache))
              (let ((unscored-candidates '())
                    (candidates-to-score '()))
                ;; Presort candidates by
                ;; `fussy-max-limit-preferred-candidate-fn'.
                (setf unscored-candidates
                      (if fussy-max-limit-preferred-candidate-fn
                          (sort
                           all fussy-max-limit-preferred-candidate-fn)
                        ;; If `fussy-max-limit-preferred-candidate-fn'
                        ;; is nil, we'll partition the candidates as is.
                        all))
                ;; Partition the candidates into sorted and unsorted groups.
                (dotimes (_n (* (length unscored-candidates)
                                fussy-percent-of-candidates-to-score))
                  (push (pop unscored-candidates) candidates-to-score)
                  (setf fussy--current-result candidates-to-score))
                (append
                 ;; Compute all of the fuzzy scores only for candidates.
                 (fussy--highlight-collection
                  pattern
                  (fussy-outer-score candidates-to-score infix cache))
                 unscored-candidates)))))))))

;;
;; (@* "Scoring & Highlighting" )
;;

(defun fussy-valid-score-p (score)
  "Return whether SCORE is valid."
  (and score
       ;; Score of '(nil) can be returned...
       (car score)
       (> (car score)
          (or fussy-score-threshold-to-filter
              fussy--score-threshold-to-filter-alist-cache
              (setq fussy--score-threshold-to-filter-alist-cache
                    (or (alist-get
                         fussy-score-fn
                         fussy-score-threshold-to-filter-alist)
                        0))))))

(defun fussy--normalize-and-components (string)
  "Split STRING into AND components using `fussy-AND-component-separator'.

Returns STRING with components joined by spaces (fzf AND semantics).
If `fussy-AND-component-separator' is nil, returns STRING unchanged."
  (if fussy-AND-component-separator
      (let ((components
             (if (functionp fussy-AND-component-separator)
                 (funcall fussy-AND-component-separator string)
               (split-string string fussy-AND-component-separator))))
        (string-join components " "))
    string))

(defun fussy--normalize-or-components (string)
  "Split STRING into OR groups using `fussy-OR-component-separator'.

Returns STRING with OR groups joined by \" | \" (fzf OR semantics).
If `fussy-OR-component-separator' is nil, returns STRING unchanged."
  (if fussy-OR-component-separator
      (let ((or-groups
             (if (functionp fussy-OR-component-separator)
                 (funcall fussy-OR-component-separator string)
               (split-string string fussy-OR-component-separator t))))
        (string-join or-groups " | "))
    string))

(defun fussy-normalize-query (string)
  "Normalize STRING using component separators.

See `fussy-AND-component-separator' and `fussy-OR-component-separator'.

Applies `fussy--normalize-and-components' first, then
`fussy--normalize-or-components'.  AND normalization converts custom
separators (e.g. \"&\") into spaces within each token group.  OR
normalization then splits on the OR separator and rejoins groups with
\" | \" which `fzf-native' understands natively as the OR operator.

When both separators are nil, STRING is returned unchanged.

Examples (with fussy-OR-component-separator \"|\" and
          fussy-AND-component-separator \"[ &]+\"):
  \"foo|bar\"     -> \"foo | bar\"       (foo OR bar)
  \"foo&baz|bar\" -> \"foo baz | bar\"  (foo AND baz) OR bar
  \"foo bar\"     -> \"foo bar\"         (spaces already AND in fzf)"
  (fussy--normalize-or-components
   (fussy--normalize-and-components string)))

(defun fussy-outer-score (candidates string &optional cache)
  "Function used to wrap `fussy-score-ALL-fn'."
  ;; Lazy-load `fzf-native' on first use of the fzf scoring backend.
  ;; `fussy-all-completions-v1' already does this for the
  ;; completion-styles path; do it here too so direct callers — the
  ;; ivy filter advice and `fussy-ivy-sort' — also lazy-load before
  ;; calling `fussy-fzf-score', which silently returns nil when
  ;; `fzf-native-score-all' is unbound (showing zero candidates).
  (when (fussy--fzf-p)
    (fussy--ensure-fzf-loaded))
  (funcall fussy-score-ALL-fn candidates (fussy-normalize-query string) cache))

(defvar fussy--last-was-filter-only nil
  "Non-nil when the most recent `fussy-fzf-score' call ran in filter-only mode.

Set by `fussy-fzf-score' immediately before it calls `fzf-native-score-all',
using `fzf-native-filter-only-p' to mirror the C-side decision.")

(defun fussy-fzf-score (candidates string &optional _cache)
  "Score and propertize CANDIDATES using STRING.

This implementation uses `fzf-native-score-all' to do all its scoring in one go.

Ignore CACHE. This is only added to match `fussy-score'."
  (when (fboundp 'fzf-native-score-all)
    ;; Record whether `fzf-native' will take its filter-only path so
    ;; `fussy--adjust-metadata' can skip the score-based sort.
    (setq fussy--last-was-filter-only
          (and (fboundp 'fzf-native-filter-only-p)
               (fzf-native-filter-only-p (length string) (length candidates))))
    ;; Highlight after `fussy--sort'.
    (let ((fzf-native-batch-highlight nil))
      (fzf-native-score-all candidates string))))

(defun fussy-score (candidates string &optional cache)
  "Score and propertize CANDIDATES using STRING.

Use CACHE for scoring.

Set a text-property \='completion-score on candidates with their score.
`completion--adjust-metadata' later uses this \='completion-score for sorting."
  (let ((result '())
        (string (replace-regexp-in-string "\\\s" "" string)))
    (dolist (x candidates)
      (if (> (length x) fussy-max-word-length-to-score)
          ;; Don't score x but don't filter it out either.
          (unless fussy-filter-unscored-candidates
            (push (copy-sequence x) result))
        (let ((score (funcall fussy-score-fn x string cache)))
          (fussy--debug "fn: %S candidate: %s query: %s score %S"
                        'fussy-score x string score)
          ;; Candidates with a score of N or less are filtered.
          (when (fussy-valid-score-p score)
            (setf x (copy-sequence x))
            (put-text-property 0 1 'completion-score (car score) x)

            ;; If we're using pcm highlight, we don't need to propertize the
            ;; string here. This is faster than the pcm highlight but doesn't
            ;; seem to work with `find-file'.
            (when (fussy--should-propertize-p)
              (setf
               x (funcall fussy-propertize-fn x score)))
            (push x result)))))
    ;; Returns nil if empty.
    result))

(defun fussy--should-propertize-p ()
  "Whether or not to call `fussy-propertize-fn'.

If `fussy--use-pcm-highlight-p' is t, highlighting will be handled in
`fussy--maybe-highlight'.

If `fussy-propertize-fn' is nil, no highlighting should take place."
  (and
   (not (fussy--use-pcm-highlight-p))
   (not (fussy--fzf-p))
   fussy-propertize-fn))

(defun fussy--highlight-collection (query-or-pattern collection)
  "Highlight COLLECTION.

QUERY-OR-PATTERN is routed by the active scoring backend:
- `fussy--fzf-p' — interpreted as a query string and passed to
  `fzf-native-highlight-all'.
- `fussy--use-pcm-highlight-p' — interpreted as a pcm pattern list and
  passed to `completion-pcm--hilit-commonality'.
- Otherwise — ignored.  COLLECTION returned unchanged on the assumption
  that highlighting was applied elsewhere (e.g. by `fussy-propertize-fn'
  during scoring).

COLLECTION is mutated in place for the fzf path (via setcar/aset inside
`fzf-native-highlight-all') and returned.  Pass a list of one to use
this as the per-candidate highlighter behind
`completion-lazy-hilit-fn'."
  (when collection
    (cond
     ((fussy--fzf-p)
      ;; Skip the eager pass when the frontend has opted into lazy hilit —
      ;; `fussy-all-completions' has already set `completion-lazy-hilit-fn'
      ;; to a closure calling `fzf-native-highlight-one' per visible
      ;; candidate.  Avoids redundant eager face on top-N that the lazy fn
      ;; will overwrite at render time.
      (when (and (fboundp 'fzf-native-highlight-all)
                 (stringp query-or-pattern)
                 (not (string-empty-p query-or-pattern))
                 (not (bound-and-true-p completion-lazy-hilit)))
        (fzf-native-highlight-all collection query-or-pattern))
      collection)
     ((fussy--use-pcm-highlight-p)
      ;; `completion-pcm--hilit-commonality' is itself lazy-aware (Emacs
      ;; 30+) — under lazy it sets `completion-lazy-hilit-fn' and returns
      ;; the collection unchanged.  Safe to call unconditionally.
      (fussy--pcm-highlight query-or-pattern collection))
     (:default
      ;; Assume that the collection's highlighting is handled elsewhere.
      collection))))

(defun fussy--pcm-highlight (pattern collection)
  "Highlight with pcm-style for COLLECTION using PATTERN.

pcm-style refers to using `completion-pcm--hilit-commonality' for highlighting."
  (completion-pcm--hilit-commonality pattern collection))

(defun fussy-propertize-common-part (str score)
  "Return propertized copy of STR according to score.

If SCORE does not have indices to highlight, return STR unmodified."
  (if (or
       ;; Has only score but no indices or nil.
       (<= (length score) 1)
       ;; Indices are higher than the length of str indicating the indices are
       ;; incorrect. Skip highlighting to avoid breaking completion.
       ;; Take the last index to compare against str because all indices need
       ;; to be less than the length of str in order for highlighting to work.
       (>= (car (last score)) (length str)))
      str
    ;; Has a score and an index to highlight.
    (let ((block-started (cadr score))
          (last-char nil)
          ;; Originally we used `substring-no-properties' when setting str but
          ;; that strips text properties that other packages may set.
          ;; One example is `consult', which sprinkles text properties onto
          ;; the candidate. e.g. `consult--line-prefix' will check for
          ;; 'consult-location on str candidate.
          (str (if (consp str) (car str) str)))
      (dolist (char (cdr score))
        (when (and last-char
                   (not (= (1+ last-char) char)))
          (add-face-text-property block-started (1+ last-char)
                                  'completions-common-part nil str)
          (setf block-started char))
        (setf last-char char))
      (add-face-text-property block-started (1+ last-char)
                              'completions-common-part nil str)
      (when (and
             last-char
             (> (length str) (+ 2 last-char)))
        (add-face-text-property (1+ last-char) (+ 2 last-char)
                                'completions-first-difference
                                nil
                                str))
      (if (consp str)
          (cons str (cdr str))
        str))))

;;
;; (@* "Bootstrap" )
;;

;;;###autoload
(progn
  (put 'fussy 'completion--adjust-metadata fussy-adjust-metadata-fn)
  (add-to-list 'completion-styles-alist
               '(fussy fussy-try-completions fussy-all-completions
                       "Smart Fuzzy completion with scoring.")))

;;;###autoload
(defun fussy-setup ()
  "Set up `fussy'."
  (unless (memq 'fussy completion-styles)
    (push 'fussy completion-styles))

  ;; https://github.com/minad/consult/issues/585
  ;; https://github.com/axelf4/hotfuzz?tab=readme-ov-file#dynamic-module
  (with-eval-after-load 'consult
    (defvar consult--tofu-char)
    (defvar consult--tofu-range)
    (setq consult--tofu-char #x100000
          consult--tofu-range #x00fffe))

  ;; For example, project-find-file uses 'project-files which uses
  ;; substring completion by default. Set our own defaults.
  (setq completion-category-overrides
        '((file
           ;; https://github.com/jojojames/fussy/issues/46
           ;; https://github.com/minad/vertico?tab=readme-ov-file#tramp-hostname-and-username-completion-fixed-on-emacs-29
           (styles fussy basic))
          (buffer
           (styles fussy basic))
          (consult-location
           (styles fussy basic))
          (unicode-name
           (styles fussy basic))
          (project-file
           (styles fussy basic))
          (xref-location
           (styles fussy basic))
          (info-menu
           (styles fussy basic))
          (symbol-help
           (styles fussy basic)))))

(defun fussy-fzf--sort-highlight-advice (orig-fn completions)
  "Around advice for `fussy--sort' under `fussy-setup-fzf'.

Run ORIG-FN to sort COMPLETIONS, then re-highlight the post-sort
top-N via `fzf-native-highlight-all'.  Needed because the C-side
scorer highlights the top-N by its own score-order, but
`fussy--sort' re-orders ties via `fussy-compare-same-score-fn',
so the displayed top-N would otherwise differ from the highlighted
top-N (most candidates tying at the same score for short queries).

For file completion specifically, candidates carry an internal
`completion--unquoted' text property whose value is the display
string (Emacs bug#77754 — quoted paths need unquoting before
display).  Vertico reads that property and renders the inner
string, not the outer candidate.  The outer `highlight-all' pass
faces only the outer candidate, so without further work the
displayed unquoted layer stays plain.  We propagate face onto the
unquoted layer with a second per-candidate highlight pass and
re-attach the faced copy as the property's value.

Skip both eager passes when the frontend has opted into lazy hilit
\(vertico, icomplete on Emacs 28+).  `fussy-all-completions' has
already set `completion-lazy-hilit-fn' to a per-candidate closure;
vertico drives face at render time against the displayed string
\(unquoted for files), which is the natural way to resolve
bug#77754.  The eager pass here would be redundant under lazy."
  (let ((sorted (funcall orig-fn completions)))
    (when (and sorted
               (fboundp 'fzf-native-highlight-all)
               (stringp fussy--current-infix)
               (not (string= fussy--current-infix ""))
               (not (bound-and-true-p completion-lazy-hilit)))
      (fzf-native-highlight-all sorted fussy--current-infix)
      ;; Second pass: propagate face onto each candidate's
      ;; `completion--unquoted' property string, for vertico file
      ;; completion (bug#77754).
      (dolist (cand sorted)
        (when (and (stringp cand) (> (length cand) 0))
          (when-let* ((unq (get-text-property
                            0 'completion--unquoted cand))
                      ((stringp unq))
                      (cell (list (copy-sequence unq))))
            (fzf-native-highlight-all cell fussy--current-infix)
            (put-text-property 0 (length cand)
                               'completion--unquoted (car cell)
                               cand)))))
    sorted))

(defvar fussy--fzf-loaded-p nil
  "Non-nil once `fzf-native' has been loaded on demand by fussy.")

(defun fussy--ensure-fzf-loaded ()
  "Load `fzf-native' the first time fussy's fzf path is exercised."
  (unless fussy--fzf-loaded-p
    (require 'fzf-native)
    (when (fboundp 'fzf-native-ensure-loaded)
      (fzf-native-ensure-loaded))
    (setq fussy--fzf-loaded-p t)))

;;;###autoload
(defun fussy-setup-fzf ()
  "Set up `fussy' for `fzf-native'.

`fzf-native' itself is not loaded here; it is deferred to the first
`fussy-all-completions' call that actually needs it."
  (fussy-setup)
  (setq fussy-filter-fn 'fussy-filter-by-scoring)
  (setq fussy-score-ALL-fn 'fussy-fzf-score)
  (setq fussy-use-cache t)
  (advice-add 'fussy--sort :around #'fussy-fzf--sort-highlight-advice))

;;;###autoload
(defun fussy-setup-fuz ()
  "Set up `fussy' for `fuz' with multithreaded batch scoring.

Uses `fuz-score-all-skim' or `fuz-score-all-clangd' (controlled by
`fussy-fuz-use-skim-p') to score the entire candidate collection in
one parallel Rust call instead of per-candidate Elisp iteration."
  (fussy-setup)
  (setq fussy-filter-fn 'fussy-filter-by-scoring)
  (setq fussy-score-fn 'fussy-fuz-score)
  (setq fussy-score-ALL-fn 'fussy-fuz-score-all)
  (setq fussy-use-cache t))

;;
;; (@* "Sorting" )
;;

(defun fussy--adjust-metadata (metadata)
  "If actually doing filtering, adjust METADATA's sorting."
  (if (and fussy--filtering-p
           ;; We only call `fussy-sort' if we scored the candidates.
           (not fussy--last-was-filter-only))
      `(metadata
        (display-sort-function . fussy--sort)
        (cycle-sort-function . fussy--sort)
        ,@(cdr metadata))
    (let ((category (completion-metadata-get metadata 'category)))
      (if (memq category '(command buffer))
          `(metadata
            (display-sort-function . fussy--default-sort)
            (cycle-sort-function . fussy--default-sort)
            ,@(cdr metadata))
        metadata))))

(defun fussy--default-sort (completions)
  "Sort COMPLETIONS using `fussy-default-sort-fn'.

Used when there's no need to sort. e.g. User hasn't typed anything."
  (if (or (null fussy-default-sort-fn)
          (length< completions 1200))
      (if fussy-default-sort-fn
          (sort completions fussy-default-sort-fn)
        completions)
    (let* ((uses-hist (memq fussy-default-sort-fn
                            '(fussy-histlen->strlen< fussy-histlen<)))
           (uses-len (memq fussy-default-sort-fn
                           '(fussy-histlen->strlen< fussy-strlen< fussy-strlen>)))
           (hist (when uses-hist (fussy--history-hash-table))))
      (mapcar
       #'car
       (sort
        (mapcar
         (lambda (c)
           (let ((hpos (if (and uses-hist hist)
                           (or (gethash c hist) most-positive-fixnum)
                         0))
                 (len (when uses-len (length c))))
             (list c hpos len)))
         completions)
        (lambda (a b)
          (cond
           ((eq fussy-default-sort-fn #'fussy-histlen->strlen<)
            (let ((h1 (nth 1 a))
                  (h2 (nth 1 b)))
              (if (= h1 h2)
                  (< (nth 2 a) (nth 2 b))
                (< h1 h2))))
           ((eq fussy-default-sort-fn #'fussy-histlen<)
            (< (nth 1 a) (nth 1 b)))
           ((eq fussy-default-sort-fn #'fussy-strlen<)
            (< (nth 2 a) (nth 2 b)))
           ((eq fussy-default-sort-fn #'fussy-strlen>)
            (> (nth 2 a) (nth 2 b)))
           (t (funcall fussy-default-sort-fn (car a) (car b))))))))))

(defun fussy--sort (completions)
  "Sort COMPLETIONS using `completion-score' and completion length."
  (if (or (null fussy-compare-same-score-fn)
          ;; If not many candidates, just do the old fashion N Log N.
          (length< completions 1200))
      (sort
       completions
       (lambda (c1 c2)
         (let ((s1 (or (get-text-property 0 'completion-score c1) 0))
               (s2 (or (get-text-property 0 'completion-score c2) 0)))
           (if (and (= s1 s2)
                    fussy-compare-same-score-fn)
               (funcall fussy-compare-same-score-fn c1 c2)
             ;; Candidates with higher completion score have precedence.
             (> s1 s2)))))
    ;; Schwartzian transform for larger collections to avoid repeated
    ;; property/hash lookups in the sort predicate.
    (let* ((uses-hist (memq fussy-compare-same-score-fn
                            '(fussy-histlen->strlen< fussy-histlen<)))
           (uses-len (memq fussy-compare-same-score-fn
                           '(fussy-histlen->strlen< fussy-strlen< fussy-strlen>)))
           (hist (when uses-hist (fussy--history-hash-table))))
      (mapcar
       #'car
       (sort
        (mapcar
         (lambda (c)
           (let ((score (or (get-text-property 0 'completion-score c) 0))
                 (hpos (if (and uses-hist hist)
                           (or (gethash c hist) most-positive-fixnum)
                         0))
                 (len (when uses-len (length c))))
             ;; candidate, score, history-pos, length
             (list c score hpos len)))
         completions)
        (lambda (a b)
          (let ((s1 (nth 1 a))
                (s2 (nth 1 b)))
            (if (= s1 s2)
                (cond
                 ((eq fussy-compare-same-score-fn #'fussy-histlen->strlen<)
                  (let ((h1 (nth 2 a))
                        (h2 (nth 2 b)))
                    (if (= h1 h2)
                        (< (nth 3 a) (nth 3 b))
                      (< h1 h2))))
                 ((eq fussy-compare-same-score-fn #'fussy-histlen<)
                  (< (nth 2 a) (nth 2 b)))
                 ((eq fussy-compare-same-score-fn #'fussy-strlen<)
                  (< (nth 3 a) (nth 3 b)))
                 ((eq fussy-compare-same-score-fn #'fussy-strlen>)
                  (> (nth 3 a) (nth 3 b)))
                 (t (funcall fussy-compare-same-score-fn (car a) (car b))))
              (> s1 s2)))))))))

;;
;; (@* "Candidate Comparisons" )
;;

(defun fussy-strlen< (c1 c2)
  "Return t if C1's length is less than C2's length."
  (< (length c1) (length c2)))

(defun fussy-strlen> (c1 c2)
  "Return t if C1's length is greater than C2's length."
  (> (length c1) (length c2)))

(defun fussy-histlen< (c1 c2)
  "Return t if C1 occurred more recently than C2.

Check C1 and C2 in `minibuffer-history-variable' which is stored in
`fussy--hist-hash'."
  (if-let* ((hist fussy--hist-hash)
            (c1-pos (or (gethash c1 hist) most-positive-fixnum))
            (c2-pos (or (gethash c2 hist) most-positive-fixnum)))
      (< c1-pos c2-pos)
    nil))

(defun fussy-histlen->strlen< (c1 c2)
  "Return t if C1 occurs more recently than C2 or is shorter than C2."
  (if-let* ((hist fussy--hist-hash)
            (c1-pos (or (gethash c1 hist) most-positive-fixnum))
            (c2-pos (or (gethash c2 hist) most-positive-fixnum)))
      (if (= c1-pos c2-pos)
          (fussy-strlen< c1 c2)
        (< c1-pos c2-pos))
    (fussy-strlen< c1 c2)))

;;
;; (@* "Utils" )
;;

(defun fussy--recreate-regex-pattern (beforepoint afterpoint bounds)
  "Utility function to create regex pattern for highlighting.

`fussy--highlight-collection' consumes this pattern.
This usually comes out as a result of the initial filtering of candidates,
but when we're pulling from the cache, the pattern is not there, so we
rebuild it here. We could also try caching the pattern instead of creating it
again."
  (cond
   ((eq fussy-filter-fn 'fussy-filter-flex)
    ;; This comes from `fussy-emacs-legacy-completion-substring--all-completions'
    ;; Look at `fussy-filter-flex'.
    (let* ((basic-pattern (completion-basic--pattern
                           beforepoint afterpoint bounds))
           (pattern (if (not (stringp (car basic-pattern)))
                        basic-pattern
                      (cons 'prefix basic-pattern)))
           (pattern
            (completion-pcm--optimize-pattern
             (fussy-emacs-legacy-completion-flex--make-flex-pattern pattern))))
      pattern))
   (:default ;; `fussy-filter-default'
    (fussy-make-pcm-highlight-pattern
     beforepoint afterpoint bounds))))

(defun fussy--fzf-p ()
  "Return whether or not we're using fzf."
  (eq fussy-score-ALL-fn 'fussy-fzf-score))

(defun fussy--fuz-score-all-p ()
  "Return whether or not we're using fuz's multithreaded batch scoring."
  (eq fussy-score-ALL-fn 'fussy-fuz-score-all))

(defun fussy--filter-by-scoring-p ()
  "Return whether or not we're filtering matches through our scoring function."
  (eq fussy-filter-fn 'fussy-filter-by-scoring))

(defun fussy--use-pcm-highlight-p ()
  "Check if highlighting should use `completion-pcm--hilit-commonality'.

Check if `fussy-score-fn' used doesn't return match indices.
Check if `fzf' is being used (highlighting is done in the C layer)."
  (cond
   ;; fzf-native applies highlighting directly in the C layer when
   ;; `fussy-fzf-native-highlight' is non-nil; never run pcm fallback.
   ((fussy--fzf-p) nil)
   ((fussy--filter-by-scoring-p) t)
   ;; These don't generate match indices to highlight at all so we should
   ;; highlight with `completion-pcm--hilit-commonality'.
   ((memq fussy-score-fn fussy-score-fns-without-indices) t)
   (:default nil)))

(defun fussy--history-hash-table ()
  "Return hash table representing `minibuffer-history-variable'.

Key is the history string and Value is the history position."
  (let ((hist (and (not (eq minibuffer-history-variable t))
                   (symbol-value minibuffer-history-variable))))
    (cond
     ((eq hist fussy--hist-hash-last-val)
      fussy--hist-hash)
     (t
      (setq fussy--hist-hash-last-val hist)
      (setq fussy--hist-hash
            (when hist
              (let ((table (make-hash-table :test 'equal
                                            :size (length hist))))
                (cl-loop for index from 0
                         for item in hist
                         unless (gethash item table)
                         do (puthash item index table))
                table)))))))

(defconst fussy--consult--tofu-char #x200000
  "Special character used to encode line prefixes for disambiguation.
We use invalid characters outside the Unicode range.")

(defconst fussy--consult--tofu-range #x100000
  "Special character range.")

(defsubst fussy--consult--tofu-p (char)
  "Return non-nil if CHAR is a tofu."
  (<= fussy--consult--tofu-char char
      (+ fussy--consult--tofu-char fussy--consult--tofu-range -1)))

(defun fussy--print-hash-table (table)
  "Print TABLE."
  (message "------------------------------------------------------------------")
  (maphash (lambda (key value)
             (message "key: %s # of elements: %s" key (length value)))
           table)
  (message "------------------------------------------------------------------"))

(defun fussy--use-cache-instead-of-filter-p (string)
  "Check if this STRING should use the cache or filter instead."
  (let ((length (length string)))
    (and
     fussy-use-cache
     (> length 0)
     ;; e.g. ~/.emacs.d/url/ should not use entry from "~/.emacs.d/url".
     ;; <spc> ^ ! ' . | are related to fzf filtering.
     ;; : for /ssh: /scpx: /sudo:
     (not (or
           ;; "a|"
           (memq (aref string (1- length))
                 '(?  ?/ ?^ ?! ?' ?. ?| ?:))
           (and (> length 1)
                ;; "a|b"
                (memq (aref string (- length 2))
                      '(?  ?/ ?^ ?! ?' ?. ?| ?:))))))))

(defun fussy-wipe-cache (&rest _)
  "Wipe buffer local `fussy--all-cache'."
  (fussy--debug "Setting `fussy--all-cache' to nil..")
  (setf fussy--all-cache nil))

;;
;; (@* "Filtering" )
;;

(define-obsolete-function-alias 'fussy-filter-orderless-flex
  'fussy-filter-flex "2.0"
  "Use `fussy-filter-flex' instead.  Orderless integration was removed.")

(define-obsolete-function-alias 'fussy-filter-orderless
  'fussy-filter-default "2.0"
  "Use `fussy-filter-default' instead.  Orderless integration was removed.")

(defun fussy-filter-flex (string table pred point)
  "Match STRING to the entries in TABLE.

Respect PRED and POINT.  The filter here is the same as in
`completion-flex-all-completions'."
  (pcase-let ((`(,completions ,pattern ,prefix ,_suffix ,_carbounds)
               (fussy-emacs-legacy-completion-substring--all-completions
                string
                table pred point
                #'fussy-emacs-legacy-completion-flex--make-flex-pattern)))
    (list completions pattern prefix)))

(defun fussy-filter-default (string table pred point)
  "Match STRING to the entries in TABLE.

Respect PRED and POINT.  This filter uses the `all-completions' interface
that's written in C for faster filtering."
  (let* ((beforepoint (substring string 0 point))
         (afterpoint (substring string point))
         (bounds (completion-boundaries beforepoint table pred afterpoint))
         (prefix (substring beforepoint 0 (car bounds)))
         (infix (concat
                 (substring beforepoint (car bounds))
                 (substring afterpoint 0 (cdr bounds))))
         (regexp (funcall fussy-default-regex-fn infix))
         (completion-regexp-list regexp)
         (category (alist-get 'category
                              (completion-metadata string table pred)))
         (completions
          (cond
           ((eq category 'buffer)
            ;; When string begins with space in `switch-to-buffer' category,
            ;; hidden buffers should be shown, so set the prefix to be " ".
            (all-completions (if (and
                                  (= (length prefix) 0)
                                  (string-prefix-p " " infix))
                                 " "
                               prefix)
                             table pred))
           (:default
            ;; Commentary on why we prefer prefix over infix.
            ;; For `find-file', if the prefix exists, we're in a different
            ;; directory, so should be retrieving candidates from that directory
            ;; instead.
            ;; ex. We started in ~/ home directory. User starts typing cod.
            ;; infix will be: c -> co -> cod
            ;; prefix will be ~/
            ;; User then enters a directory called ~/Code and types abc.
            ;; infix will be: a -> ab -> abc
            ;; prefix will be ~/Code
            ;; For `project-find-file', the prefix will usually be empty and only
            ;; the infix will be matched against.
            ;; So, *knock on wood*, it seems safe to prefer prefix completion over
            ;; infix completion.
            ;; Is there an easier way to check if string is empty or nil?
            (if (or (/= (length prefix) 0)
                    fussy-prefer-prefix)
                ;; Always use prefix if available for correctness.
                ;; For example, `find-file', should always use prefix.
                (or (all-completions prefix table pred)
                    (all-completions infix table pred))
              ;; When prefix is nil, the choice if infix or prefix is preference..
              ;; Infix is much faster than prefix but can be "wrong" or not
              ;; exhaustive for matches. Prefix will be exhaustive and "correct"
              ;; but can be slow. Generally, we should prefer prefix for
              ;; correctness.
              ;; We allow an escape hatch to infix for extra performance with
              ;; `fussy-prefer-prefix' set to nil.
              (or (all-completions infix table pred)
                  (all-completions prefix table pred))))))
         ;; Create this pattern for the sole purpose of highlighting with
         ;; `completion-pcm--hilit-commonality'. We don't actually need this
         ;; for `all-completions' to work since we're just using
         ;; `completion-regexp-list' with `all-completions'.
         ;; In addition to that, we only need this pattern if we're highlighting
         ;; using `completion-pcm--hilit-commonality' so skip evaluating the
         ;; pattern if this is not the pcm highlight case.
         (pattern
          (fussy-make-pcm-highlight-pattern beforepoint afterpoint bounds)))
    (fussy--debug
     "prefix: %s infix: %s pattern %s completions %S regexp_list: %S"
     prefix infix pattern completions completion-regexp-list)
    (list completions pattern prefix)))

(defun fussy-filter-by-scoring (string table pred point)
  "Match STRING to the entries in TABLE.

Use `fussy-score-ALL-fn' for filtering."
  (let*
      ((beforepoint (substring string 0 point))
       (afterpoint (substring string point))
       (bounds (completion-boundaries beforepoint table pred afterpoint))
       (prefix (substring beforepoint 0 (car bounds)))
       (infix (concat
               (substring beforepoint (car bounds))
               (substring afterpoint 0 (cdr bounds))))
       (completion-regexp-list nil)
       (bufferp (eq 'buffer
                    (alist-get 'category
                               (completion-metadata string table pred))))
       ;; When string begins with space in `switch-to-buffer' category,
       ;; hidden buffers should be shown, so set the prefix to be " ".
       (prefix-2 (if (and
                      bufferp
                      (= (length prefix) 0)
                      (string-prefix-p " " infix))
                     " "
                   prefix))
       (completions
        (if (or (fussy--fzf-p) (fussy--fuz-score-all-p))
            ;; Gather all valid candidates and score in batch.
            ;; `fussy-outer-score' normalizes INFIX once.
            (fussy-outer-score
             (all-completions prefix-2 table pred) infix)
          ;; Fallback path: Score per-candidate (slow). The predicate
          ;; calls `fussy-score-fn' directly (bypassing
          ;; `fussy-outer-score'), so we must normalize once up-front
          ;; before the hot loop.
          (let ((normalized-infix (fussy-normalize-query infix)))
            (all-completions
             prefix-2 table
             (apply-partially 'fussy-filter-by-scoring-predicate
                              normalized-infix table pred)))))
       (pattern
        (fussy--recreate-regex-pattern beforepoint afterpoint bounds)))
    (list completions pattern prefix)))

(defun fussy-filter-by-scoring-predicate (string table pred candidate
                                                 &optional hash-table-value)
  ;; From `all-completions' documentation.
  ;; COLLECTION can also be a function to do the completion itself.
  ;; It receives three arguments: STRING, PREDICATE and t.
  ;; Whatever it returns becomes the value of `all-completions'.
  ;; If optional third argument PREDICATE is non-nil, it must be a function
  ;; of one or two arguments, and is used to test each possible completion.
  ;; A possible completion is accepted only if PREDICATE returns non-nil.
  ;;
  ;; The argument given to PREDICATE is either a string or a cons cell (whose
  ;; car is a string) from the alist, or a symbol from the obarray.
  ;; If COLLECTION is a hash-table, PREDICATE is called with two arguments:
  ;; the string key and the associated value.
  "Predicate for `all-completions' api.

STRING should be applied partially.
TABLE should be applied partially.
PRED should be applied partially.
See `fussy-filter-by-scoring'.

CANDIDATE is the possible completion, either a string, a cons cell
(whos car is a string), or a symbol from the obarray.

If COLLECTION is a hash-table, candidate is the string key and
hash-table-value is the associated value."
  ;; First call pred, if pred returns t, we can proceed to filter with the next step.
  ;; If pred returns nil, we don't need to filter
  (if (and pred
           (not (if (hash-table-p table)
                    (funcall pred candidate hash-table-value)
                  (funcall pred candidate))))
      nil
    ;; e.g. (> (car (funcall fussy-score-fn "abc" "a")) 0)
    (if-let* ((x (cond
                  ((hash-table-p table) candidate)
                  ((stringp candidate) candidate)
                  ((consp candidate) (car candidate))
                  ((symbolp candidate) (symbol-name candidate))
                  (:default nil))))
        ;; Note: `string' is already normalized in `fussy-filter-by-scoring'.
        (let ((score (funcall fussy-score-fn x string)))
          (fussy--debug "c: %s s: %s score: %S" x string score)
          (fussy-valid-score-p score))
      t)))

(defun fussy-make-pcm-highlight-pattern (beforepoint afterpoint bounds)
  "Create flex pattern for highlighting.

Respect BEFOREPOINT, AFTERPOINT, and BOUNDS."
  (when (fussy--use-pcm-highlight-p)
    ;; Note to self:
    ;; The way we create the pattern here can be found in
    ;; `fussy-emacs-legacy-completion-substring--all-completions'.
    (let* ((basic-pattern (completion-basic--pattern
                           beforepoint afterpoint bounds))
           (pattern (if (not (stringp (car basic-pattern)))
                        basic-pattern
                      (cons 'prefix basic-pattern))))
      (completion-pcm--optimize-pattern
       (fussy-emacs-legacy-completion-flex--make-flex-pattern pattern)))))

;;
;; (@* "Pattern Compiler" )
;;
;; Random note:
;; These return something similar to what `orderless-pattern-compiler'
;; These can be applied where `orderless-pattern-compiler' can apply.
;; e.g. They return \(list some-regex\).
;;

(defun fussy-pattern-flex-1 (str)
  "Make STR flex pattern.

This may be the fastest regex to use but is not exhaustive."
  (list
   (concat "\\`"
           (mapconcat
            (lambda (x)
              (setf x (string x))
              (concat "[^" x "]*" (regexp-quote x)))
            str
            ""))))

(defun fussy-pattern-flex-2 (str)
  "Make STR flex pattern.

This is a copy of the `orderless-flex' pattern written without `rx'.

This one may be slower than `fussy-pattern-flex-1' but is more
exhaustive on matches."
  (list
   (concat
    (when (> (length str) 1)
      "\\(?:\\(?:")
    (mapconcat
     (lambda (x)
       (format "\\(%c\\)" x))
     str
     ".*")
    (when (> (length str) 1)
      "\\)\\)"))))

(defun fussy-pattern-flex-3 (str)
  "Make STR flex pattern."
  (list
   (mapconcat (lambda (c) (regexp-quote (char-to-string c)))
              str
              ".*")))

(defun fussy-pattern-default (str)
  "Default pattern to pass to `completion-regexp-list' when filtering.."
  (ignore str)
  (fussy-pattern-default-to-backend str))

(define-inline fussy-pattern-default-to-backend (_str)
  "Return nothing, expect backend to filter/score.

This seems faster from benchmarking...

**With regex set:**
1. C-side `all-completions` walks all N candidates and applies the regex and
 keeps M.
2. fussy scores those M candidates.
- Cost: N regex matches + M fzf scores.

**With regex nil:**
1. C-side `all-completions` walks all N candidates (no filtering on the regex
 side, just prefix).
2. fussy scores all N candidates. fzf returns 0 for non-matches → effectively
 filters.
- **Cost**: N fzf scores."
  (inline-quote nil))

(defun fussy-pattern-first-letter (str)
  "Make pattern for STR.

str: abc
result: LIST ^a"
  (if (and str (> (length str) 0))
      `(,(format "^%s" (substring str 0 1)))
    nil))

;;
;; (@* "Integration with other Packages" )
;;

;; `eglot' integration
;;;###autoload
(defun fussy-eglot-setup ()
  "Set up `fussy' with `eglot'."
  (with-eval-after-load 'eglot
    ;; `eglot' defaults to flex, so set an override to point `fussy' instead.
    (add-to-list 'completion-category-overrides
                 '(eglot-capf (styles fussy eglot--dumb-flex)))
    (add-to-list 'completion-category-overrides
                 '(eglot (styles fussy basic)))))

;; `company' integration.
(defvar company-backend)
(defvar company-prefix)

(defun fussy-company-sort-by-completion-score (candidates)
  "`company' transformer to sort CANDIDATES."
  (if (functionp company-backend)
      candidates
    (fussy--sort candidates)))

(defun fussy-company--transformer (f &rest args)
  "Advise `company--transform-candidates'.

Mirrors `fussy-company--fetch-candidates': both the filter-only path
(opt-in via positive `fussy-company-filter-only-length') and the
bypass path (prefix shorter than `fussy-company-prefix-length') skip
fussy's score-based transformer, because no `completion-score' is
attached in those modes."
  (cond
   ;; Filter-only path: opt-in via positive `fussy-company-filter-only-length'.
   ((and (fussy--fzf-p)
         (integerp fussy-company-filter-only-length)
         (> fussy-company-filter-only-length 0)
         (length< company-prefix fussy-company-filter-only-length))
    (apply f args))
   ;; Short prefix → transform normally (fussy is stripped upstream).
   ((length< company-prefix fussy-company-prefix-length)
    (apply f args))
   (t
    (let ((company-transformers
           ;; `fussy-score' still needs to do sorting.
           ;; `fussy-fzf-score' sorts on its own.
           (if (eq fussy-score-ALL-fn 'fussy-score)
               '(fussy-company-sort-by-completion-score)
             '())))
      ;; Warning: Unused lexical variable `company-transformers'
      (ignore company-transformers)
      (apply f args)))))

(defun fussy-company--fetch-candidates (f &rest args)
  "Advise `company--fetch-candidates'.

When the user has opted in to fzf-native filter-only mode by setting
`fussy-company-filter-only-length' to a positive integer N, prefixes
strictly shorter than N keep fussy in the completion pipeline and let
fzf-native take its cheap `fzf_has_match' (aka filter only) path.

Otherwise (no opt-in, prefix at/above threshold, or non-fzf scorer)
behave as before: strip fussy from `completion-styles' for prefixes
shorter than `fussy-company-prefix-length', else run fussy as usual."
  (let* ((prefix (nth 0 args))
         (_suffix (nth 1 args))
         (fzf (fussy--fzf-p))
         (fussy-prefer-prefix nil)
         (fussy-max-candidate-limit 5000)
         (gc-cons-threshold (max gc-cons-threshold
                                 fussy-company-gc-cons-threshold))
         ;; Tie-breaker and cache cost more than they save in company's
         ;; short popup cycles.
         (fussy-compare-same-score-fn nil)
         (fussy-use-cache nil)
         (fussy-AND-component-separator
          (if fzf "[ &]" fussy-AND-component-separator))
         (fussy-OR-component-separator
          (if fzf "|" fussy-OR-component-separator)))
    (cond
     ;; Filter-only path: opt-in via a positive `fussy-company-filter-only-length'.
     ((and fzf
           (integerp fussy-company-filter-only-length)
           (> fussy-company-filter-only-length 0)
           (length< prefix fussy-company-filter-only-length))
      (let ((fzf-native-filter-only-length fussy-company-filter-only-length)
            (fzf-native-filter-only-logic 'or))
        (apply f args)))
     ;; Short prefix → run completion without fussy.
     ((length< prefix fussy-company-prefix-length)
      (let ((completion-styles (remq 'fussy completion-styles))
            (completion-category-overrides nil))
        (apply f args)))
     (t (apply f args)))))

(defun fussy-company--preprocess-candidates (candidates)
  "Advise `company--preprocess-candidates'.

This is to try to avoid a additional sort step."
  ;; (cl-assert (cl-every #'stringp candidates))
  ;; (unless (company-call-backend 'sorted)
  ;;   (setq candidates (sort candidates 'string<)))
  (when (and (fboundp 'company-call-backend)
             (fboundp 'company--strip-duplicates))
    (when (company-call-backend 'duplicates)
      (company--strip-duplicates candidates)))
  candidates)

(defun fussy-company-setup ()
  "Set up `company' with `fussy'."
  (with-eval-after-load 'company
    (advice-add 'company--transform-candidates
                :around 'fussy-company--transformer)
    (advice-add 'company--fetch-candidates
                :around 'fussy-company--fetch-candidates)
    (advice-add 'company--preprocess-candidates
                :override 'fussy-company--preprocess-candidates)))

;; `corfu' integration.
(defun fussy-corfu--capf-wrapper (f &rest args)
  "Advise `corfu--capf-wrapper'.

Mirrors `fussy-company--fetch-candidates'."
  (let ((fussy-max-candidate-limit 5000)
        (fussy-prefer-prefix nil)
        (fussy-default-regex-fn 'fussy-pattern-first-letter)
        (fussy-compare-same-score-fn nil)
        (fussy-use-cache nil)
        (gc-cons-threshold (max gc-cons-threshold
                                fussy-company-gc-cons-threshold)))
    (apply f args)))

;;;###autoload
(defun fussy-corfu-setup ()
  "Set up `corfu' with `fussy'."
  (with-eval-after-load 'corfu
    (advice-add 'corfu--capf-wrapper
                :around 'fussy-corfu--capf-wrapper)))

;; `fuz' integration.
(declare-function "fuz-fuzzy-match-skim" "fuz")
(declare-function "fuz-calc-score-skim" "fuz")
(declare-function "fuz-fuzzy-match-clangd" "fuz")
(declare-function "fuz-calc-score-clangd" "fuz")
(declare-function "fuz-score-all-skim" "fuz")
(declare-function "fuz-score-all-clangd" "fuz")

;; `ivy' integration.
(defvar ivy-flx-limit)
(defvar ivy-text)
(defvar ivy--all-candidates)
(defvar ivy-re-builders-alist)
(defvar ivy-last)
(declare-function ivy-state-caller "ivy")
(declare-function ivy--regex-fuzzy "ivy")

;;;###autoload
(defun fussy-ivy-sort (name candidates)
  "Sort CANDIDATES by NAME using `fussy'.

Designed to be used as an :override advice for `ivy--flx-sort'.
It utilizes `fussy-score-ALL-fn' for batch scoring and respects
`fussy' tie-breaking and normalization."
  (if (or (null candidates)
          (string= name "")
          (string= name "^"))
      candidates
    (condition-case err
        (let* ((flx-name (if (string-prefix-p "^" name) (substring name 1) name))
               (query (fussy-normalize-query flx-name))
               ;; Use a higher limit for fzf/fuz backends which handle batching.
               (limit (if (or (fussy--fzf-p) (fussy--fuz-score-all-p))
                          (length candidates)
                        (min (length candidates)
                             (or (and (boundp 'ivy-flx-limit) ivy-flx-limit) 200))))
               (to-sort (cl-subseq candidates 0 limit))
               (rest (cl-subseq candidates limit))
               ;; Map from string representation to original candidates.
               ;; We handle duplicates by keeping a list of candidates per string.
               (map (make-hash-table :test 'equal)))
          (dolist (c to-sort)
            ;; Candidates from `ivy-read' are strings, or cons cells when
            ;; the collection is an alist; take the string form for the
            ;; map key.  Replaces the removed `ivy--flx-candidate-string'.
            (let ((s (if (consp c) (car c) c)))
              (push c (gethash s map))))

          (let* ((strings (let (keys) (maphash (lambda (k _v) (push k keys)) map) keys))
                 ;; `fussy-outer-score' handles batching and normalization.
                 (scored (fussy-outer-score strings query)))

            ;; If the backend didn't sort (like pure flx), sort it now.
            (when (eq fussy-score-ALL-fn 'fussy-score)
              (setq scored (fussy--sort scored)))

            (let ((result '()))
              (dolist (s scored)
                (when-let* ((orig-cands (gethash s map)))
                  (dolist (c (nreverse orig-cands))
                    (push c result))
                  (remhash s map)))
              ;; Keep remaining candidates that didn't match fuzzy-score but might
              ;; have matched ivy's re-builder.
              (maphash (lambda (_k v)
                         (dolist (c (nreverse v))
                           (push c result)))
                       map)
              (nconc (nreverse result) rest))))
      (error
       (message "fussy-ivy-sort error: %S" err)
       candidates))))

(defun fussy-ivy-re-filter-advice (orig filter candidates &optional mkpred)
  "Replace ivy's regex filter with `fzf-native' / `fussy' scoring.

Self-gates by checking the active re-builder via
`ivy-re-builders-alist': only kicks in when it's `ivy--regex-fuzzy'
(the value `fussy-ivy-setup' installs as the default).  Explicit
per-caller entries — `ivy--regex-plus' for grep tools / `swiper',
`ivy--regex' for raw regex callers — pass through to ORIG so their
shell tools / line matchers receive the regex they expect.

For multi-word and fzf-extended-syntax queries (`a b' = AND,
`a | b' = OR, `!ext' = exclude, `^pre' / `suf$' / `\\='exact'),
`ivy--regex-fuzzy''s output regex is more restrictive than
fzf-native's matcher — without this advice, candidates fzf would
score as matches are silently dropped before `fussy-ivy-sort'
sees them.

Per fzf-native's pattern grammar (see fzf.c:`fzf_parse_pattern')
a standalone whitespace-surrounded `|' is the only operator that
widens the match set versus a prefix of the query.  When the query
contains such a `|', ivy's incremental filter against
`ivy--old-cands' would miss items matching only the right side of
the OR — so this advice forces use of `ivy--all-candidates' in
that case.  All other extended operators only narrow, so the
incremental CANDIDATES passed by ivy is safe to score directly."
  (let* ((caller (ivy-state-caller ivy-last))
         (rebuilder (or (cdr (assq caller ivy-re-builders-alist))
                        (cdr (assq t       ivy-re-builders-alist)))))
    (cond
     ;; Empty input -> return CANDIDATES
     ((or (null ivy-text) (string-empty-p ivy-text))
      candidates)
     ;; Take over `ivy--regex-fuzzy'.
     ;; If | is in query, always use full candidate set.
     ((eq rebuilder #'ivy--regex-fuzzy)
      (let ((source-cands
             (if (member "|" (split-string ivy-text))
                 ivy--all-candidates
               candidates)))
        (or (fussy-outer-score source-cands ivy-text)
            ;; Empty result: pass nil through so ivy shows "no match".
            nil)))
     ;; Fall through to original function.
     (t
      (funcall orig filter candidates mkpred)))))

;;;###autoload
(defun fussy-ivy-setup ()
  "Set up `fussy' for `ivy'."
  (interactive)
  (when (require 'ivy nil t)
    (advice-add 'ivy--flx-sort  :override #'fussy-ivy-sort)
    (advice-add 'ivy--re-filter :around   #'fussy-ivy-re-filter-advice)
    ;; Only update the t (default) entry — preserves any per-caller
    ;; overrides the user has set in either order.
    (setf (alist-get t ivy-re-builders-alist) #'ivy--regex-fuzzy)))

(defun fussy-flx-rs-score (str query &rest args)
  "Score STR for QUERY with ARGS using `flx-rs-score'."
  (require 'flx-rs)
  (when (fboundp 'flx-rs-score)
    (flx-rs-score str query args)))

(defun fussy-fuz-score (str query &rest _args)
  "Score STR for QUERY using `fuz'.

skim or clangd algorithm can be used."
  (require 'fuz)
  (if fussy-fuz-use-skim-p
      (when (fboundp 'fuz-fuzzy-match-skim)
        (fuz-fuzzy-match-skim query str))
    (when (fboundp 'fuz-fuzzy-match-clangd)
      (fuz-fuzzy-match-clangd query str))))

(defun fussy-fuz-score-all (candidates string &optional _cache)
  "Score CANDIDATES for STRING using fuz's multithreaded batch scoring.

Uses `fuz-score-all-skim' or `fuz-score-all-clangd' based on
`fussy-fuz-use-skim-p'.  The entire collection is scored in one call
using Rust/rayon parallelism.

Ignore CACHE.  This is only added to match `fussy-score'."
  (require 'fuz)
  (if fussy-fuz-use-skim-p
      (when (fboundp 'fuz-score-all-skim)
        (fuz-score-all-skim candidates string))
    (when (fboundp 'fuz-score-all-clangd)
      (fuz-score-all-clangd candidates string))))

;; `fuz-bin' integration.
(declare-function "fuz-bin-dyn-score-skim" "fuz-bin")
(declare-function "fuz-bin-score-skim" "fuz-bin")
(declare-function "fuz-bin-dyn-score-clangd" "fuz-bin")
(declare-function "fuz-bin-score-clangd" "fuz-bin")

(defun fussy-fuz-bin-score (str query &rest _args)
  "Score STR for QUERY using `fuz-bin'.

skim or clangd algorithm can be used."
  (require 'fuz-bin)
  (fussy--debug "before: str: %s query: %s" str query)
  (if fussy-fuz-use-skim-p
      (when (fboundp 'fuz-bin-score-skim)
        (fuz-bin-score-skim query str))
    (when (fboundp 'fuz-bin-score-clangd)
      (fuz-bin-score-clangd query str))))

;; `liquidmetal' integration
(declare-function "liquidmetal-score" "liquidmetal")

(defun fussy-liquidmetal-score (str query &rest _args)
  "Score STR for QUERY using `liquidmetal'."
  (require 'liquidmetal)
  (when (fboundp 'liquidmetal-score)
    (list (liquidmetal-score str query))))

;; `sublime-fuzzy' integration
(declare-function "sublime-fuzzy-score" "sublime-fuzzy")

(defun fussy-sublime-fuzzy-score (str query &rest _args)
  "Score STR for QUERY using `sublime-fuzzy'."
  (require 'sublime-fuzzy)
  (when (fboundp 'sublime-fuzzy-score)
    (list (sublime-fuzzy-score query str))))

;; `hotfuzz' integration
(declare-function "hotfuzz--cost" "hotfuzz")

(defun fussy-hotfuzz-score (str query &rest _args)
  "Score STR for QUERY using `hotfuzz'."
  (require 'hotfuzz)
  (when (fboundp 'hotfuzz--cost)
    ;; Looks like the score is flipped for `hotfuzz'.
    ;; See `hotfuzz-all-completions'.
    (list (+ 10000 (- (hotfuzz--cost query str))))))

;;; Legacy

;; This package uses internal Emacs functions.  Some of these functions
;; were modified in https://github.com/emacsmirror/emacs/commit/aa181cd35220,

(defun fussy-emacs-legacy-completion-flex--make-flex-pattern (pattern)
  "Convert PCM-style PATTERN into PCM-style flex pattern.

This turns
    (prefix \"foo\" point)
into
    (prefix \"f\" any \"o\" any \"o\" any point)
which is at the core of flex logic.  The extra
`any' is optimized away later on."
  (mapcan (lambda (elem)
            (if (stringp elem)
                (mapcan (lambda (char)
                          (list (string char) 'any))
                        elem)
              (list elem)))
          pattern))

(defun fussy-emacs-legacy-completion-substring--all-completions
    (string table pred point &optional transform-pattern-fn)
  "Match the presumed substring STRING to the entries in TABLE.
Respect PRED and POINT.  The pattern used is a PCM-style
substring pattern, but it be massaged by TRANSFORM-PATTERN-FN, if
that is non-nil."
  (let* ((beforepoint (substring string 0 point))
         (afterpoint (substring string point))
         (bounds (completion-boundaries beforepoint table pred afterpoint))
         (suffix (substring afterpoint (cdr bounds)))
         (prefix (substring beforepoint 0 (car bounds)))
         (basic-pattern (completion-basic--pattern
                         beforepoint afterpoint bounds))
         (pattern (if (not (stringp (car basic-pattern)))
                      basic-pattern
                    (cons 'prefix basic-pattern)))
         (pattern (completion-pcm--optimize-pattern
                   (if transform-pattern-fn
                       (funcall transform-pattern-fn pattern)
                     pattern)))
         (all (completion-pcm--all-completions prefix pattern table pred)))
    (list all pattern prefix suffix (car bounds))))

(provide 'fussy)
;;; fussy.el ends here
