Add scores to completion items

[sam-mccall]

Many things can affect the quality of a CompletionItem suggestion.

Currently the server can control ranking via sortText, but the interactions with client-side fuzzy-matching are unclear:

• some clients may sort the results by fuzzy match, losing the suggestion quality information
• clients that perform local fuzzy filtering don't have enough information to provide a ranking that takes into account both match quality and result quality.

One way this could be addressed is to define score = matchScore * resultScore, where matchScore is a 0-1 number describing the fuzzy-match quality of (filter, ci.filterText).
The server would rank/truncate results by score, and also provide resultScore to the client. This makes it explicit that the server has already ranked the results according to filterText, and allows the client to re-rank them when the filter changes without losing information - it computes the new matchScore and multiplies by resultScore.

(In practice, I don't think this requires the client and server to have identical fuzzy-match scorers, just as the current fuzzy-filter semantics are not precisely spelled out).

Obviously this is a complex change that would require client/server support, and some back-compat story. Maybe for v4?

[sam-mccall]

Oops, forgot to mention the motivating use case: I'm working on the clangd LSP server for C++, and we want to support completion at global scope, for huge codebases, including symbols you haven't imported yet.
Good ranking is essential for this to be viable. With the current protocol, we might have to set incomplete=true always (to force editors to re-query) which is painful for web-based editors.

[gorkem]

On jdt.ls we try to calculate a relevancy rank for sortText but that does not allow us to support some of the cases. A solution for this should consider ranking/sorting completionItems from multiple LSPs though.

[sam-mccall]

FWIW It seems VSCode largely ignores this part of the spec anyway, even in the absence of client-side filtering. (Or possibly interprets it in a way I don't understand).

For the query 's' we compute scores std::string > absl::StrCat > ::strcat and return matching sortText, but VSCode renders the results as std::string > ::strcat > absl::StrCat.

[sam-mccall]

@dbaeumer I'm assuming this isn't being worked on ("backlog"). Is this something that could get review attention if someone was willing to contribute work/patches to the spec/client/vscode?

This is an increasingly pressing issue for clangd, we have more VSCode users now and this hurts code completion quality on large codebases a lot vs other clients.

We're investigating adding a proprietary extension and trying to hack this into our VSCode plugin (unclear if possible). Happy to redirect this effort if you think it might lead somewhere.

On a pure technical side, I think the hardest part is adapting vscode's fuzzy-matcher to give a score on a well-defined scale.

[astoff]

In this scheme, it is possible that two editors, A and B, always agree on the relative ordering of the fuzzy matches, but compute their matchScore in such a way that the final sorting by score = matchScore * resultScore is different in A and B. It all depends on the scaling of the scores; if you play around a bit, you'll find examples.

The problem here is that the scoring criteria of the editor is unknown to the server and vice versa, so their product can interact in complicated ways. In a way, this is just a reflection of the fact that that fuzzy-match sorting is not canonical. But I'm not sure it's a good idea to spec a system that allows those random interactions.

[sam-mccall]

Since this doesn't seem to be going onywhere, clangd is going to add CompletionItem.score as an extension and try to add support in LSP clients we recommend.

[mickaelistria]

Since this doesn't seem to be going onywhere, clangd is going to add CompletionItem.score as an extension and try to add support in LSP clients we recommend.

I think you should have a look to #898 which is about the same topic. A score would not really help as the score, just like the initial sorting of elements, may become irrelevant whenever user type a keystroke, and would drive the client to decide whether to do fuzzy matching (some server like it) or to respect the LS ordering (some other servers do that).

In #898, I suggest that we add some semantics on sortText and filterText null state so it becomes more explicit what clients need to do. Or, if necessary, adding a new flag on CompletionList to explicit the client behavior.

[sam-mccall]

I'm aware of #898, the discussion there isn't going in a useful direction for us. We need a way to produce a final ranking based on a numeric combination of fuzzy-match factors and server-specific factors that are not exposed via LSP.

A score would not really help as the score, just like the initial sorting of elements, may become irrelevant whenever user type a keystroke

The score in the extension excludes any fuzzy-match component. Therefore clients that re-rank based on client-side fuzzy match can use this score as a multiplier. Clients that don't do that can ignore it.

[astoff]

server-specific factors that are not exposed via LSP

Isn't the ordering of the completion list enough information?

[mickaelistria]

Isn't the ordering of the completion list enough information?

There is nothing that states that, and there are language servers that assume the client does some filtering. More examples about it in #898 .

[sam-mccall]

Isn't the ordering of the completion list enough information?

No. Consider a completion list for f: [foo_bar (100 refs), fbar (99 refs)]. Now the input is extended to fb, the best result is [fbar, foo_bar].

If foo_bar had 10000000 refs and fbar had 1, then the best result is [foo_bar, fbar]. (Think up=>unique_ptr). And today, clients can't tell the difference - the order for the f query is the same in each case.

That said, if clients were willing to filter only and sort purely by sortText, then for servers with good ranking, user-visible ranking may still be better than it is today. But empirically they don't, VSCode, coc.nvim etc assume the server is dumb and re-rank.

[sam-mccall]

(I'm sure it seems like I'm obsessing over obscure cases - we frequently get bug reports about ranking from VSCode users)

[dbaeumer]

@sam-mccall thanks for your willingness to work on this.

I added a comment here #898 (comment) explaining how I think that should already work today. Can you please have a look.

[astoff]

If foo_bar had 10000000 refs and fbar had 1

Sure this can happen, but does it, in practice? It seems unlikely there isn't going to be some intermediate candidates in between these two (assuming here that number of refs is a relevant attribute and the server takes it into account for its own ranking).

My suggestion above was to try to come up with a formula using matchScore and resultRank (the latter being the index of the candidate in the array of completion items) instead of resultScore. It seems to me that something like this should work well enough, but of course one would need to try it out to decide.

[dbaeumer]

I will close the issues since I don't see us implementing this anytime soon especially since the LSP model leaves sorting and filtering to the client.