Contribute this to Emacs?

[joaotavora]

Hi @axelf4 I just found out about this project. I'm the guy who created flex. As far as I can see, hotfuzz is like flex but presumably better in every possible way. If that is true, I think we should just replace Emacs's flex with it, so long as you're willing to contribute the code to GNU Emacs (signing FSF papers, etc). WDYT?

[manuel-uberti]

I would love to see this readily available in Emacs!

[manuel-uberti]

@axelf4 friendly ping :)

[manuel-uberti]

@axelf4 another friendly ping

[jwr]

Just wanted to say thank you for writing hotfuzz. This is by far the best completion I've ever tested in Emacs (and I've tested quite a few). The C library also makes it really fast. I'm not sure why it isn't more popular, it is so much better than everything else.

If it could be included in Emacs, or at least land in melpa-stable, it would make it more popular and likely better in the long term!

[axelf4]

Sorry for the late response!

This being an attempt at a canonical Emacs Lisp implementation of the algorithm by Gotoh used by most fuzzy searchers, I agree it would make sense for something like this to ship with GNU Emacs. I have signed FSF copyright assignment papers, but the one time I tried submitting a package for GNU ELPA I received no response, which made me a bit predisposed against that ordeal. :) That said, if the GNU Emacs maintainers agree, I would be very willing to contribute this to Emacs.

As far as I can see, hotfuzz is like flex but presumably better in every possible way.

That is not completely true. The Lisp implementation of hotfuzz manages to be about as fast as flex, while having more "expressive" candidate scoring, but only by making the, admittedly entirely reasonable, additional assumption that completion-all-completions results are not edited before being passed to display-/cycle-sort-function. This allows lazy highlighting and a cheaper Schwartzian transform, and would need to be codified in the completions API.

[joaotavora]

I received no response, which made me a bit predisposed against that ordeal. :) That said, if the GNU Emacs maintainers agree, I would be very willing to contribute this to Emacs.

You should contact @monnier.

That is not completely true. The Lisp implementation of hotfuzz manages to be about as fast as flex, while having more "expressive" candidate scoring, but only by making the, admittedly entirely reasonable, additional assumption that completion-all-completions results are not edited before being passed to display-/cycle-sort-function. This allows lazy highlighting and a cheaper Schwartzian transform, and would need to be codified in the completions API.

Interesting, but I don't understand exactly what you mean. Can you show an example (maybe a contrived example) of a use case (interactive or programmatic) where the "additional assumption" plays a role? I.e. where hotfuzz misbehaves and flex doesn't? "lazy highlighting" as in completion-lazy-hilit is part of the completions API, not sure that counts as "codified in".

[axelf4]

Interesting, but I don't understand exactly what you mean. Can you show an example (maybe a contrived example) of a use case (interactive or programmatic) where the "additional assumption" plays a role? I.e. where hotfuzz misbehaves and flex doesn't?

Hotfuzz both filters and sorts the completions already in completion-all-completions, then adds a completion-sorted text property to the first completion of the returned list. The adjusted display-sort-function checks for the text property, and if found, returns the list as-is, and otherwise calls the original display-sort-function. The motivation is that i.a. (I) display-sort-function does not have access to the search string; (II) It allows the dynamic module to do more filtering and scoring in parallel, and only copy each Emacs string value once; and (III) The qsort library routine is unstable anyway, so sorting beforehand is a waste of time.

It breaks down in contrived cases like:

(let ((all (completion-all-completions
            string table nil (length string) md)))
  (setcdr (last all) nil)

  (setq all (shuffle all)) ; Not OK if using hotfuzz, but fine with flex
  (pop all) ; ... same here

  ;; Not OK if using flex or hotfuzz, though technically ought to be
  ;; allowed as the documentation makes no mention of this limitation.
  (dolist (x all)
    (set-text-properties 0 (length x) () x))

  (funcall (completion-metadata-get md 'display-sort-function) all))

since the display-sort-function cannot find the completion-sorted text property, or is otherwise just the identity function.

I cannot think of any non-contrived examples (would not be a very good assumption to make otherwise!).

"lazy highlighting" as in completion-lazy-hilit is part of the completions API, not sure that counts as "codified in".

I meant that the added assumption would need to be codified.

[joaotavora]

Thanks for clarifying @axelf4 👍