[autocomplete-plus] Allow interleaving of results from different providers

[savetheclocktower]

Have you checked for existing feature requests?

• [X] Completed

Summary

Right now, autocomplete-plus is very rigid in how it returns suggestions:

• Providers are sorted by their (static) suggestionPriority, with higher values going earlier.
• Each provider decides whether or not autocomplete-plus should be filtering the suggestions, so filtering happens on a per-provider basis.
• The results are concatenated in order and presented in order.

So if autocomplete-snippets were to have a higher suggestionPriority than autocomplete-css, then its least helpful suggestion (as judged by our fuzzy-matcher) is still displayed before autocomplete-css’s most helpful suggestion:

Here, warning is favored over width simply because of the arbitrary ordering of providers. autocomplete-snippets doesn't have a higher suggestionPriority than autocomplete-css; they have the same value. I'm not yet sure how ties are broken; maybe it's activation order. But the fact that the user didn't choose to elevate autocomplete-snippets’s suggestions is all the more proof that we shouldn't be doing this.

---

What we should do instead is this:

• Process each provider's suggestions; filter the ones that opt into filtering.
  • Filtering goes through the fuzzy-matcher. Anything with a score of 0 or less is excluded; everything else is sorted according to its score.
• Concatenate the results into one flat list.
  • Filter the suggestions again. In this filtering “mode,” we will score each option, but we will not exclude anything at this point. The suggestions are therefore sorted by score^*; all providers’ suggestions are free to intermingle.
• Show the suggestions to the user. The best-scoring suggestion should be at the top.

* Actually, autocomplete-plus stacks the deck a bit and makes it so that something must really score ahead of its peers in order to be elevated. We could keep this algorithm, abandon it, or make it configurable.

I was able to get this outcome with just a few minutes of work:

What benefits does this feature provide?

I think most people expect that, after the process of fuzzy-matching, the best suggestion will be at the top. We should behave that way.

Any alternatives?

I'm not seeing any.

There are related features we could look into. For instance, there's hardly any visibility into the suggestionPriority property, even though it's the main determiner of suggestion order. (A given provider package may allow its suggestionPriority to be configurable, but most don't, and there's no way to control it from autocomplete-plus.)

We could maybe do something a bit less disruptive and simply alter how we break ties insuggestionPriority. Instead of using some arbitrary criterion, we could break ties by ordering according to the score of the best match. That's another way we could guarantee that the best match would be the first one shown, at least when suggestionPriority is equal.

Other examples:

No response

[savetheclocktower]

@mauricioszabo, from #994:

Anyway... I feel we need to fix this in autocomplete-plus indeed. What is very weird is that autocomplete-plus don't require a score field for completions, so it might not be clear how to "sort" these results... as soon as you open the issue, @savetheclocktower, let's discuss how to best approach this case. I might have some ideas :)

To generate the screenshot above, I just scored everything according to our fuzzy-matcher. That way, even providers that opt out of filterSuggestions still get scored by the fuzzy-matcher, even if it's not grounds for exclusion from the list.

[mauricioszabo]

The idea is sound, but I'd like to keep that behind a config toggle. In fact, I would go ahead and add a score attribute to the suggestion, such that autocomplete-plus doesn't re-filter things that a provider already filtered - as an example, suppose I have a provider that filters public methods first, then private ones; it would be rude to undo this sorting...

So my idea is: if we add a toggle for it (no idea how that option would be called... something like "sort suggestions with Pulsar's fuzzy finder?") we could solve this issue, and completely ignore the score attribute; or we could only apply this "filtering mode" (scoring everything again) for suggestions that didn't provide any score... need to think about this clearly.

Finally - I would love to see some option in autocomplete-plus to re-prioritize providers (instead of letting the provider decide arbitrarily how much its own suggestions are "worthy").

[mauricioszabo]

Also - suggestions without prefixes are currently not being scored by our fuzzyFinder, so it might be part of the issue; also the fact that we now accept ranges too... and the sorting algorithm is quite weird (there's a sortScore that's mostly to preserve order, and it's used in place of score if that one doesn't exist, but only if provider asks for its suggestions to be filtered).

[savetheclocktower]

as an example, suppose I have a provider that filters public methods first, then private ones; it would be rude to undo this sorting...

There's a tension here. I agree that it makes sense not to reorder things from the provider when there's no prefix; but once the user starts typing, I think that they rightly expect that the characters they type will be the main determiner of the ordering of the results.

So I'm happy for my free-for-all proposal to be something a user must opt into. But I think that static ordering of providers is basically a bug, so I'd also like to improve on the status quo, since lots of people won't dive into the autocomplete-plus settings. Since neither of us likes the priority system, how about this as a new default?

• autocomplete-plus does not reorder results from a provider when filterSuggestions: false, but…
• if a prefix is present, all results are scored against the prefix, and…
• …suggestions remain grouped by provider, but those groups are ordered by either the best score or the average score in each group, ignoring suggestionPriority.

So my idea is: if we add a toggle for it (no idea how that option would be called... something like "sort suggestions with Pulsar's fuzzy finder?") we could solve this issue, and completely ignore the score attribute; or we could only apply this "filtering mode" (scoring everything again) for suggestions that didn't provide any score... need to think about this clearly.

Suppose we call the setting Fuzzy-Matching Behavior and make it an enum:

• Filter and preserve order
• Filter and reorder providers
• Filter and reorder suggestions

The setting description would explain:

When completing a partially-typed token, Filter and preserve order means that results will be winnowed, but will still be grouped by provider. Filter and reorder providers means that results will be winnowed and groups of suggestions will be sorted by relevance; provider priority will no longer matter. Filter and reorder suggestions means that results will be winnowed and grouping will be abandoned; results will be sorted only by how well they match what the user has typed.

It's wordy and I don't love it, but it's a start.

Also - suggestions without prefixes are currently not being scored by our fuzzyFinder, so it might be part of the issue;

How would you score results without a prefix?

Finally - I would love to see some option in autocomplete-plus to re-prioritize providers (instead of letting the provider decide arbitrarily how much its own suggestions are "worthy").

Agreed. I made an attempt at this for symbols-view; you list all the providers you like (by display name or by package name) and it gives them score bumps in the order that they were listed. It suffers from the fact that we don't have a good way of representing arrays/objects in the settings UI, but it's a start.

[savetheclocktower]

Relatedly, I feel more and more like I'm ready to jump into autocomplete-plus. I think it's clear that it needs revisiting and that we need it to be able to do all the things that LSP expects an autocompleter to do.

[mauricioszabo]

@savetheclocktower prefix is not text. Prefix is basically: suppose you have hel, and autocomplete suggests something for you. It might offer text or snippet (and that's what we'll score, which already poses a problem I haven't predicted because snippets are not actually that good as means of filtering) and a prefix (or a ranges but that implementation is still not stable).

So, supposing a candidate have prefix he and text hello, when the user accepts that suggestion this will become hellol (with the trailing l). If the prefix is hell, then it'll be hell (because it won't replace anything in the editor... ok, sorry for the pun :D) and if the prefix is hel, then the contents will be hello, with no trailing l or anything. It can also have prefix el, and then the replacement will be hhello

[mauricioszabo]

Also:

I think that they rightly expect that the characters they type will be the main determiner of the ordering of the results.

That might be the case, but the default provider might ask to complete some variable name when the user is typing something like user.getN. LSP does offer a way to sort results, and servers can choose to send this parameter, so users might want for their results to be sorted according to what LSP returned, instead of getting some random completion as the first option.

As an example, the default provider gives a "proximity boost" so getNemesis might have a higher priority than getName when we sort these. Which also.... makes me think, because the "proximity boost" will basically always be ignored if we decide to re-sort results...