Completion should be fuzzy search rather than exact search

[kutsan]

I don't know how can I explain but giving this context, correct completion is only provided when you start typing the word as it is supposed to be.

I think marrig should also provide margin-right but it does not.

I'm sorry in advance if it's related to language server client that I'm using.

[haorenW1025]

This should be an enhancement and it should highly dependent on what server you use. I can try to implement though.

[haorenW1025]

Please update to the latest branch and use this setting

let g:completion_enable_fuzzy_match = 1

[clason]

A compromise between strict and fuzzy matching would be substring matching (i.e., matching on right in the example above); that can also be useful (and cheaper). You could include this in a single option
g:completion_match = strict/full (default), substring, or fuzzy.

[hrsh7th]

Some completion engine applying multiple match algorithm.

For example, coc.nvim does matching prefix or fuzzy both but prefix matched items will be first of pum.

It is very good experience, I think.

[clason]

So you always want prefix > substr > fuzzy in case multiple matchers match (with the option to disable the third or second option, not include -- and compute, of course -- such matches at all)?

[hrsh7th]

prefix exact -> prefix ignorecase -> substr -> fuzzy etc...

I think always check first character match is good but here is some different opinion may be exists.

[haorenW1025]

@clason @hrsh7th Thanks you both for the suggestion. I think I can create a option like

g:completion_match_strategy = ['prefix', 'substr', 'fuzzy']

When matching a word, simply loop through this option and assign priority from high to low. That way, users like me who only like one strategy can still only use one of them, others who wants more matching can setup the strategy they want. I'll need to refactor the code a little bit so it might takes some time implementing this.

[haorenW1025]

@clason An issue with substring match is it will suggest a lot of items when your prefix is a single character. Any thought on how to deal with this issue? Or I should simply avoid it when using substring match?

[clason]

@haorenW1025 I don't have the issue (at least in my use cases): Searching filters a list of candidates shown after a trigger character is entered, any match will reduce the number suggestions, whether initial or substring?

But I see your point. Maybe make the number of prefix characters (optionally?) configurable per match method (i.e., it can be different for prefix, substring, and fuzzy matching)? But then it quickly starts to become complicated... Maybe people will just avoid substring matching if their source returns too many irrelevant candidates.

[haorenW1025]

@clason I'd say it would be too complicated. I'll suggest not using substring match if user encounter this problem in the documentation.

Also, feel free to try the PR and tell me what you think, you can enable multiple matching by

let g:completion_matching_strategy_list = ['exact', 'substr', 'fuzzy']

[clason]

Works fine, from what I can tell! (And really speeds up filtering long lists of matches to the point where only a few <c-n> are necessary.)

Two questions:

1. Is there an option somewhere to make the matching case insensitive?
2. It seems the matching only takes word into account, not menu?

[haorenW1025]

Is there an option somewhere to make the matching case insensitive?

Not yet, I'm thinking of having this as a separate option since all three matching strategy can benefit from this.

It seems the matching only takes word into account, not menu?

Yes, why should I take menu into account? I think that should only be a additional information to the word. Can you explain a little?

[clason]

Not yet, I'm thinking of having this as a separate option since all three matching strategy can benefit from this.

Makes sense, just seeing that I haven't missed anything.

Yes, why should I take menu into account? I think that should only be a additional information to the word. Can you explain a little?

Indeed, and that additional information could be useful ;) For example, you could filter on information contained in signature help.

(My specific use case is the following: the word is a key to a bibliography entry, and menu -- or rather, the completion item -- contains the full entry such as the authors, title etc. So if I don't remember the key, I can filter on author name or a word in the title that I don't remember. Admittedly not the typical lsp use case...)

[haorenW1025]

Yeah that seems to only happens in texlab. Implement that shouldn't be very hard, but I still want it to be customizable, so maybe I would use a new option for that. Something like

let g:completion_matching_items = ['word', 'menu', 'kind' ...]

[clason]

Makes sense. If it's only one server, maybe don't worry about it for now. (It's nice to have, but I can always fall back to omnicomplete (from vimtex) for that.) I'm a bit worried about losing the blazing performance that completion-nvim now has ;)

Case insensitive is I think more important to me.

[haorenW1025]

@clason Try update to the latest commit and set this

let g:completion_matching_ignore_case = 1

[clason]

@haorenW1025 Yes, that works nicely, thank you!

(But now I can't get fuzzy matching working anymore -- did that option change?)

[haorenW1025]

@clason I didn't change that... Did you use the option completion_matching_strategy_list? I've tested it on my side and it seems to work fine.

[clason]

@haorenW1025 You're right, this is due to a change in texlab at the same time (I didn't realize that this would affect this): latex-lsp/texlab@38fabd6

Is this something that fundamentally conflicts with fuzzy matching, or can this be worked around somehow?

[clason]

Going down the rabbit hole of server- vs client-side filtering: microsoft/language-server-protocol#898 (comment) (Spoiler: it's complicated.)

It seems to me to be useful to a) have a mechanism to decide whether client or server is responsible for sorting and filtering, b) make it configurable/overridable in the on_attach function (so it's server-specific) and c) document it prominently. What do you think?

[haorenW1025]

@clason The problem now is fuzzy match and substring match are highly dependent on what server returns. If the server decided to filter out irrelevant items(like texlab did recently) then it'll not work. Another example is clangd also filter out all the irrelevant things. As a completion engine I think there is little we can do about that... If the language server did provide the mechanism you mentioned I think it should be setup in nvim-lsp but not here.

[clason]

@haorenW1025 Yes, this is a difficult situation. I agree that if the server filters/sorts, the client cannot (and should not) do anything about it. Unfortunately, there does not seem to be a good way according to the protocol to negotiate this -- and since it's not in the specification, it probably won't be in nvim-lsp, either.

The simplest way is therefore to let the user make an informed decision: tell completion-nvim to either match/sort or not (as you already can), but on a per-server basis.

One way could be to have optional keys for the on_attach method, e.g.

on_attach({sorter={"none"}, matcher = {"exact", "substring"}})

with some reasonable defaults?

(To be sure: I'm not saying completion-nvim should configure the server behavior -- I don't think that's possible -- but be configurable depending on the (fixed) server behavior: If the user knows that the server filters, they can disable matching by completion-nvim; if they know the server doesn't, they can enable matching by completion-nvim. The only issue here is that the user may have different servers, some of which filter and some of which don't...)

[haorenW1025]

Yeah that's possible and should also be a better way to setup than using global variables. I'll work on that in the same PR to avoid continuously changing interface on master branch. Thanks for the suggestion:)

[haorenW1025]

PR have been merged, feel free to reopen or open another issue for any feature suggestion:)

[clason]

Thanks for merging this! Did you change the API back from the on_attach(matcher={...}) syntax?

[haorenW1025]

Nope the on_attach should still work. I'm planning to add more stuff into that so I didn't change the documentation. Also the g:... setup will still work and it'll be a fallback value if you don't use the on_attach setup.

[clason]

Hmm, yes, you're right, it's just throwing an error:

Error executing vim.schedule lua callback: ...nvim/plugins/completion-nvim/lua/completion/matching.lua:53: attempt to call a nil value

(also, I think there's a typo in the readme: the second g:...matching_strategy should be ...ignore_case, right?)

[clason]

Ah, because it's substring now, not substr :)

[haorenW1025]

It seems I change it and forgot about it...But substring should be better anyway. I've updated README and fix some typos.

[clason]

No worries. Thanks for that useful feature!