Remove sorting of user-supplied insert completions

[aver-d]

Hi, for a plugin I'm writing I need insert-mode completions to be displayed in a pre-determined order.

The implementation for displaying user-generated completions in complete_option includes a sort

kakoune/src/insert_completer.cc

Line 315 in 079b006

std::sort(matches.begin(), matches.end());

As far as I'm aware, there's no other way I can show the custom-generated completions without this sorting.

Would it be possible to either make the sort optional or simply remove this one line and leave sorting to the user if it's required?

[mawww]

It would be tricky to remove/disable this sort, because this is not simply an alphabetical sort, its sorting candidates according to their fuzzy matching relevance. When no text has been written by the user to filter out candidates yet, this will be alphabetically sorted as that is the last condition when comparing two ranked matches, but as soon as some text has been written, the sorting will be based on the number of matching word boundaries, whether the user entered text is a prefix or just a subsequence, wether the matched part is contiguous...

Disabling this behaviour would be possible, after all we could just display candidates that matches the entered text without sorting them at all, but it would require a very strong motivating use case to add that complexity inside the insert completion code.

Can you describe our use case in more details ?

[aver-d]

Hi, and thanks for the response.

In case I wasn't clear, I didn't mean for there to be any change in the way that kakoune currently operates – only that it be useful to have a choice to display a static list of completions candidates (provided by an external process) to be shown as originally supplied.

So, for example, set window my_completions ${header}:d||d:b||b:a||a:c||c could show in order d b a c, not a b c d.

You mention there are two stages: (1) an initial lexicographic sort and (2) subsequent fuzzy matching.

I had been considering the problem in a way that had seemed to me would result in less work for kakoune. Neither stage 1 nor 2 would occur. The user is presented with a list of candidates and can either select an item or make a change to the buffer. Either way, the list is then immediately cleared, so there's no opportunity for stage 2 fuzzy matching to occur – the external process instead just sends a new list which reflects the new buffer state. I'd been able to get new completions to appear inside a few milliseconds, so just recompiling and commenting out that sort line seemed enough to resolve what appears to be the only problem of this extra sort (Though I appreciate you're more familiar with kakoune's implementation and there may be further issues I hadn't encountered during my brief trial).

In terms of use cases, although initially ordering candidates alphabetically is normally a reasonable choice, another way would be likelihood of selection. One simple example might be a dictionary lookup of English words. An external process could provide a list of candidates for an input infor

Displaying with an ordering based on google's n-gram data frequency...

information     285127664
informed         34787210
informal         15413598
inform           12294536

may be more useful than the conversion to a lexicographic ordering...

inform
informal
information
informed

Of course, there's no way for kakoune to know what would be a “best” ordering for each and every situation. So, to give flexibility for all cases it'd be nice to have an extra option which would make kakoune responsible solely for displaying and selecting candidates, with no additional logic.

[mawww]

Ok, I think I got a better understanding of what you are trying to achieve.

I see two possible directions to provide that features:

• Add a new type of completer, say static-option=<option-name> supported in the completers option, which only appears when you are exactly at the position specified in the option, and hence does not need any kind of fuzzy matching/sorting.
• Add a way to specify a sorting key to completion candidates that would have priority over lexicographical sorting. In the given example, all candidates will match equaly well for the fuzzy matcher, as they are all prefix-matched by infor, if we had a way to pass the n-gram data frequency (or whatever other value the completion script decides to give to the completion candidates) and have that value being compared in priority to lexicographical comparison, we would get the result you want.

However, to be more precise, there arent two stages to completion sorting, we just sort ranked matches against each other, and the comparison operator between two ranked match will compare various properties (number of word boundaries matched, is it a prefix, a full match...), when all those properties are equal, the last comparison that happens is lexicographical. This is all done in the same operation, its just the definition of RankedMatch::operator< which is pretty complex.

[Screwtapello]

I bumped into this the other day, with my predictive-text plugin. I could have sworn that this worked as I expected (candidates presented in given order) when I first made the plugin in 2021-06, but I checked out some revisions from around that time and I couldn't reproduce that behaviour - Kakoune sorted the completions every time.

For the record, here's the test-case I came up with:

echo |
    kak -n -e '
        declare-option completions mycomp
        set-option global completers option=mycomp
        set-option global mycomp 1.1@1 bbbbb||bbbbb zzzzz||zzzzz aaaaa||aaaaa
        exec i
    '

Expected result:

• An empty buffer with a completion menu listing bbbbb, zzzzz, aaaaa

Actual result:

• An empty buffer with a completion menu listing aaaaa, bbbbb, zzzzz

I see two possible directions to provide that features...

The most general solution would be to add a "weight" field to the completion list, and let the second-last test compare weights before the last lexicographical comparison. However, the syntax of "completions" options is already pretty dense, I'm not sure if there's a safe way to squeeze an optional "weight" field in there or if we'd want to break compatibility and just make it 4 required fields (text, select command, menu text, weight).

If there were some way to make the weight automatically be "distance from the end of the list" (so the first item has the highest weight and the last item has the lowest), that would basically Do The Right Thing so far as I can tell.

[krobelus]

I have an experimental change that might do the trick, see #4813