Add fuzzy matching for name completion.

[przepompownia]

In #2561 @mamazu pointed out where matching of completion input to available names has place. First thing I did was playing with regex-based fuzzy matching (created years ago for my phpcd fork) #2561 (comment) especially checking if it can be intolerably slow.

The benefit seems to be considerable even at some cost of performance.

The implementation is simple itself and to replace if it were invented and can be combined with other Criteria classes (for example ShortNameBeginsWith could be checked first, fuzzy matching otherwise) into compound Criteria.

On the other side, to avoid checking

        if (!$record instanceof HasShortName) {
            return false;
        }

        if (!$this->name) {
            return false;
        }

more than once such compound matching should be implemented in a single class - to discuss.

[mamazu]

Fixes #2561

[dantleech]

I'm not sure if this will negatively impact completion both with performance and the fact that completion clients perform fuzzy matching and cache the results and how this would conflict with them.

Case insensitive matching is a no-brainer, fuzzy matching is harder.

[mamazu]

We could reopen #2561 and just merge that.

[przepompownia]

On the client side I still use nvim-cmp that seems to use fuzzy matching on its side

but only within results found at the moment. If the client gets next parts of the response from Phpactor, the result is in practice always not as I expect (if it were, I wouldn't propose such feature). This is annoying and is not the case for lua-language-server for example.

I have not any exact proof what happens on each side in each above cases so please correct me if I wrong.

[romanzipp]

I managed to get your fork working on LazyVim, absolute game changer!

I'm currently using blink instead of nvim-cmp. Also I'm not that deep into vim and autocompletion, so I never got that fuzzy matching to work, no matter how I tweaked the blink config. It seemed to me that blink discarded all recent completions when it got "no matches" from phpactor. Is that accurate?

[przepompownia]

@romanzipp

I use built-in Nvim completion plugin (vim.lsp.completion.enable()) over a year, tweaking completeopt to my needs and replacing autotrigger (worth trying too if trigger character set may be enough) by (debounced) triggering completion request on InsertCharPre event (maybe to remove when the new autocomplete Vim option will become usable there) and displaying docs popup on CompleteChanged (to be replaced by neovim/neovim#32820). Even if that configuration is far from perfect (especially it can trigger too many requests), I never tried to configure blink to make it usable for me.

Regardless of the plugin choice mixing client side fuzzy matching with the server equivalent not always can give desired result. Too much requests triggered on typing yields new results list in the responses while it seems that in many cases we need to filter only the first response on the client side (e.g. with completeopt+=fuzzy in Nvim). It seems that only limited responses needs additional more precise requests to fit such limits and then need to be filtered out only on the client side.

Maybe in your case you need to inspect what request is sent in that moment to get empty response (and maybe the new empty list as a result).

It's offtopic here, so I'll try to hide it right after submit.