Implement completion style.

[lewang]

See company-mode/company-mode#47

[bbatsov]

Yeah, that'd be awesome.

[PythonNut]

+1 Just wondering how this is going.

[PythonNut]

I ended up implementing this in company-flx.

If anyone else is interested in using it, I'd be open to splitting it out into its own package.

[tarsius]

If anyone else is interested in using it, I'd be open to splitting it out into its own package.

I would be very interested in that!

After switching from ivy to vertico I have suffered through months of fuzzy ("dumb fuzzy matching completion") until I finally had a look at company-flx even though I am not much interested in company but finally was desperate enough to look anywhere for appropriate try/all-completion functions. 🥴

I would expect others would like that too, but never found this package because of the "company" in the name.

Ideally this would be added to flx itself, but a separate package would work for me too. Maybe flx-completion or flx-minibuffer? The name should suggest that it brings flx completion to the minibuffer, even to people not familiar to the terminology. Or just vaguely, like me.

(By the way, why do you identify the style using the symbol fuzzy? My suggestion would be to go with flx; "fuzzy" seems too ambiguous by now. Many packages do "fuzzy" now, usually "dumb fuzzy". Only flx does the original smart fuzzy. 😀)

[PythonNut]

(By the way, why do you identify the style using the symbol fuzzy? My suggestion would be to go with flx; "fuzzy" seems too ambiguous by now. Many packages do "fuzzy" now, usually "dumb fuzzy". Only flx does the original smart fuzzy. grinning)

Hmm my understanding is that the completion style controls which candidates are considered matches, but doesn't give them an ordering. This is why I named the style fuzzy, because it does fuzzy matching but no sorting. The sorting with flx scores is done in a candidate transformer (company-flx-transformer). Is there a way to do that in vertico?

I've been hearing a lot about vertico recently, I wonder if I should give it a try.

[tarsius]

Is there a way to do that in vertico?

I don't know but my guess is that there isn't (yet?). Vertico interacts closely with the default completion mechanism, at least more closely than some alternatives, which has its advantages (things just work) and disadvantages (inherent limitations of the default mechanism are inherited).

To be honest I haven't given it too much thought and don't intend to get involved in the whole completion business anytime soon. I am just hoping that one day flx style completion as I got used to while using ivy will come to the default completion mechanism and the various interfaces that are built on top of it.

Of course I understand if you don't want to get involved either. But if you give vertico a try yourself, then it might be worth asking its author about "candidate transformation" or whatever mechanism it might offer for match ordering.

[jcs090218]

Would there be a progress on this? I would very likely to set things like

(setq completion-styles '(flx))

, etc.

[jojojames]

@PythonNut @jcs090218

I implemented it like so in my own config after going through the same troubles as @tarsius .

;; Function to measure time of flx-score.
;; Not used below.
(defmacro 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)))

(defun j-company-capf-with-og-completion-styles (f &rest args)
  "Set `completion-styles' to be the default Emacs `completion-styles'
while `company-capf' runs."
  (let ((completion-styles '(flx-smart)))
    (apply f args)))

(advice-add 'company-capf :around 'j-company-capf-with-og-completion-styles)

;; Speed up flx with rust (initial measurements are 5-10x speed improvements).
(use-package flx-rs
  :ensure t
  :straight t
  :init

  ;; Manual steps:
  ;; Install Rust
  ;; $ curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
  ;; Update rustup
  ;; $ rustup update
  ;; Build flx-rs.
  ;; $ cargo build ~/.emacs./straight/repos/flx-rs/core
  ;; Symlink to Straight BUILD directory.
  ;; $ ln -s ~/.emacs./straight/repos/flx-rs/bin ~/.emacs.d/straight/build/flx-rs/bin

  ;; This hasn't been tested.
  (unless (file-exists-p "~/.emacs.d/straight/build/flx-rs/bin")
    (unless (executable-find "cargo")
      (shell-command
       "curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh -s -- -y")
      (shell-command "rustup update"))
    (shell-command "~/.emacs./straight/repos/flx-rs/core; cargo build")
    (shell-command
     "ln -s ~/.emacs./straight/repos/flx-rs/bin ~/.emacs.d/straight/build/flx-rs/bin"))

  (flx-rs-load-dyn)
  ;; This is not necessary since `flx-all-completions' already checks for this
  ;; function. It'll still help other libraries that call `flx-score' though.
  (advice-add 'flx-score :override #'flx-rs-score))

(use-package flx
  :ensure t :straight t
  :config
  (defconst flx--max-needle-len 128)

  (defcustom flx-completion-ignore-case t "")

  (defcustom flx-completion-prefix-length-start 3 "")

;; Default flx face is ugly.
  (set-face-attribute
   'flx-highlight-face nil
   :inherit 'match
   :underline t
   :overline nil
   :weight 'bold)

  (defun flx-try-completions (string table pred point)
    (completion-flex-try-completion string table pred point))

  (defun flx-all-completions (string table pred point)
    (let ((completion-ignore-case flx-completion-ignore-case))
      (pcase-let ((`(,all ,_pattern ,prefix ,_suffix ,_carbounds)
                   (completion-substring--all-completions
                    string
                    table pred point
                    #'completion-flex--make-flex-pattern)))
        (when all
          (nconc
           (if (or (> (length string) flx--max-needle-len) (string= string ""))
               all
             (mapcar
              (lambda (x)
                (setq x (copy-sequence x))
                (let* ((score
                        (if (fboundp 'flx-rs-score)
                            (flx-rs-score x string)
                          (flx-score x string flx-strings-cache))))
                  (put-text-property 0 1 'completion-score
                                     (car score)
                                     x)
                  (setq x (flx-propertize x score)))
                x)
              all))
           (length prefix))))))

  (defun flx-smart-try-completions (string table pred point)
    (if (< (length string) flx-completion-prefix-length-start)
        (completion-basic-try-completion string table pred point)
      (completion-flex-try-completion string table pred point)))

  (defun flx-smart-all-completions (string table pred point)
    (if (< (length string) flx-completion-prefix-length-start)
        (completion-basic-all-completions
         string table pred point)
      (flx-all-completions
       string table pred point)))

  (add-to-list 'completion-styles-alist
               '(flx flx-try-completions flx-all-completions
                     "Flx Fuzzy completion."))
  (add-to-list 'completion-styles-alist
               '(flx-smart flx-smart-try-completions flx-smart-all-completions
                           "Smart Flx Fuzzy completion."))

;; This eventually does the sorting (I believe).
  (put 'flx 'completion--adjust-metadata #'completion--flex-adjust-metadata)
  (put 'flx-smart
       'completion--adjust-metadata #'completion--flex-adjust-metadata)

  (setq completion-styles '(flx)
        ;; For example, project-find-file uses 'project-files which uses
        ;; substring completion by default. Set to nil to make sure it's using
        ;; flx.
        completion-category-defaults nil
        completion-category-overrides
        '((file (styles basic partial-completion)))))

I tried creating a flx-smart version that doesn't pop up fuzzy matching until the prefix length is long enough but it's probably not too useful yet unless ~~

From casual benchmarking, the initial filtering may take the longest time, sometimes 40ms maybe...

e.g.

(completion-substring--all-completions
                    string
                    table pred point
                    #'completion-flex--make-flex-pattern)

I also looked at your implementation in company-flx (@PythonNut ) and that seems to work too though I've not tested out the differences that well.

I wrote this fairly quickly, so no idea if there are any mistakes (I'm using it now and it seems to work ok.), but happy to PR (or happy to toss this if the company-flx implementation is better) if flx is still being maintained.

Otherwise, I will probably create a new package for it.

(Also would be happy to understand the delta between the company-flx implementation and my own (I don't really understand it TBH).

[jojojames]

Looking more closely at the company-flx implementation of completion-styles,

(defun company-flx-completion (string table predicate point
                                      &optional all-p)
  "Helper function implementing a fuzzy completion-style"
  (let* ((beforepoint (substring string 0 point))
         (afterpoint (substring string point))
         (boundaries (completion-boundaries beforepoint table predicate afterpoint))
         (prefix (substring beforepoint 0 (car boundaries)))
         (infix (concat
                 (substring beforepoint (car boundaries))
                 (substring afterpoint 0 (cdr boundaries))))
         (suffix (substring afterpoint (cdr boundaries)))
         ;; |-              string                  -|
         ;;              point^
         ;;            |-  boundaries -|
         ;; |- prefix -|-    infix    -|-  suffix   -|
         ;;
         ;; Infix is the part supposed to be completed by table, AFAIKT.
         (regexp (concat "\\`"
                         (mapconcat
                          (lambda (x)
                            (setq x (string x))
                            (concat "[^" x "]*" (regexp-quote x)))
                          infix
                          "")))
         (completion-regexp-list (cons regexp completion-regexp-list))
         (candidates (or (all-completions prefix table predicate)
                         (all-completions infix table predicate))))

    (if all-p
        ;; Implement completion-all-completions interface
        (progn
          (message "using all-p")
          (when candidates
           ;; Not doing this may result in an error.
           (setcdr (last candidates) (length prefix))
           candidates))
      ;; Implement completion-try-completions interface
      (progn
        (message "not using all-p")
        (if (= (length candidates) 1)
           (if (equal infix (car candidates))
               t
             ;; Avoid quirk of double / for filename completion. I don't
             ;; know how this is *supposed* to be handled.
             (when (and (> (length (car candidates)) 0)
                        (> (length suffix) 0)
                        (char-equal (aref (car candidates)
                                          (1- (length (car candidates))))
                                    (aref suffix 0)))
               (setq suffix (substring suffix 1)))
             (cons (concat prefix (car candidates) suffix)
                   (length (concat prefix (car candidates)))))
         (if (= (length infix) 0)
             (cons string point)
           (cl-destructuring-bind (merged . holes)
               (company-flx-merge candidates)
             (cons
              (concat prefix merged suffix)
              (+ (length prefix)
                 (cl-position (apply #'max holes) holes))))))))))

I added two print statements ((message "not using all-p") (message "using all-p")) and "not using all-p" was never printed in any of my completing-read functions (the simple ones like find-file, etc) using both selectrum and vertico. That tells me this completion-style (at least for completing-read) is doing the default/simple fuzzy matching (e.g. abc* type matching).

When I comment the all-p part out, I start running into completing-read errors, for example, returning (cons string point) will return an error.

 (if (= (length infix) 0)
             (cons string point)

So I comment that part out too, and this part also returns an error:

(cl-destructuring-bind (merged . holes)
               (company-flx-merge candidates)
             (cons
              (concat prefix merged suffix)
              (+ (length prefix)
                 (cl-position (apply #'max holes) holes))```

[jojojames]

Anyways, I've pushed my flx completion-style code to its own repo for the time being now. Hoping I can one day push it to the main flx repo since that's probably the most appropriate place.

I'll eventually push to melpa if there're no further discussion on the flx issue.

https://github.com/jojojames/flx-completion

Can try like so:

(use-package flx-completion
  :ensure t
  :straight
  (flx-completion :type git :host github :repo "jojojames/flx-completion")
  :after flx
  :config
  (setq completion-styles '(flx)
        ;; For example, project-find-file uses 'project-files which uses
        ;; substring completion by default. Set to nil to make sure it's using
        ;; flx.
        completion-category-defaults nil
        completion-category-overrides
        '((file (styles basic partial-completion)))))

@tarsius @PythonNut @jcs090218

[tarsius]

I've only tested it for a few minutes, but can confirm I can again invoke toggle-debug-on-error they way I was used to. 😁