Sort completions by match algorithm

[ysthakur]

Currently, every completer (except the help completer, which is special) respects the user's chosen match algorithm to fetch suggestions but individually chooses how it wants to sort its suggestions (Ascending, LevenshteinDistance, or None). I think suggestions should instead be sorted based only on the user's chosen match algorithm.

For prefix matching, sorting in alphabetical order (Ascending) makes the most sense. Sorting by levenshtein distance is essentially sorting based on length, which doesn't make much sense. In the future, we might want to offer a substring matching algorithm, but even there, I feel sorting in alphabetical order makes more sense.

For fuzzy matching, sorting by the scores provided by the fuzzy matcher makes the most sense. We're currently disregarding those scores, as pointed out in https://github.com/nushell/nushell/issues/12680. I assume no one wants to filter fuzzily but then sort those completions in alphabetical order, because that gets you somewhat unhelpful results. As for levenshtein distance, using the fuzzy matcher's score would not only be similar but would also (presumably) be better and avoid computing a distance again.

The only completer using SortBy::None is CustomCompletions. In fact, CustomCompletions has a sort_by field that, as far as I can tell, is only ever set to SortBy::None. So it's not as if we're giving custom completers a choice anyway - the completions they provide are unsorted no matter what. Edit: Sorry, completers do actually get a choice, but only between no sorting and sorting in alphabetical order. Since Nushell is filtering these custom completions according to the chosen match algorithm, it might as well sort them according to that match algorithm too.

• Perhaps, in the future, we might want to add an option to not have Nushell mess with custom completions at all (no filtering, no sorting). That's an issue for later, though.

I mentioned the help completer before. It implements the Completer trait from Reedline, not Nushell. It ignores the user's chosen match algorithm and uses substring matching. Then it sorts by levenshtein distance.

Describe the solution you'd like

The SortBy enum should be removed, and suggestions should be sorted based on the user's chosen match algorithm. If the match algorithm is Prefix, then suggestions should be sorted in alphabetical order. If it's Fuzzy, suggestions should be sorted based on the score provided by SkimMatcherV2 (or whatever Nucleo provides, if we switch to that in the future).

This includes the help completer. It doesn't currently access the user's chosen match algorithm, but it does have access to the engine state, so it could totally get the config from there and use the match algorithm from there.

Describe alternatives you've considered

This isn't a huge deal, so we could just not change anything. However, we've already had one user complain about it (https://github.com/nushell/nushell/issues/12680), and I feel it would simplify things if we didn't have a different sort order for every completer.

Additional context and details

Command completions currently sort by levenshtein distance, so this is how they look when you use prefix matching. Observe how the completions are basically sorted by length.

And file completions currently sort in alphabetical order, so this is how they look when you use fuzzy matching. Since I've typed in "Cro", Cross.toml should be the first suggestion.

[fdncred]

I'm in favor of things sorting alphabetically case insensitive

[ysthakur]

@fdncred You mean just if someone has $env.config.completions = "prefix", or also if they have fuzzy matching?

[fdncred]

i like to have things sorted alphabetically all the time and use fuzzy matching on top of it to filter out no-hits.

[ysthakur]

I see, how about adding a $env.config.completions.sort option that can be set to either "alphabetical" (always alphabetical) or "default" (change depending on match algorithm)?

[fdncred]

ya, i'd be fine with an alpha setting. i'm just so sick of levenshtein