[FR] Provide a way to not order suggested autocompletion variants alphabetically

[Drugoy]

Currently such such .usage's:

fake <I>;
<I> ::= { echo '3\n2\n1' };

fake <I>;
<I> ::= c | b | a ;

produce shell autocompletion rules where the items are suggested in alphabetical order (1 2 3 in the first case and a b c in the second) instead of the way they were ordered in the .usage files (I'd expect 3 2 1 in the first case and c b a in the second).

[adaszko]

This is more involved than it initially seems. The reason is we go through all the GRAMMAR -> REGEX -> MINIMAL DFA -> SHELL SCRIPT transformations. While it is easy to keep track the order of alternatives at the GRAMMAR and REGEX steps, keeping track of them at the DFA stage is I think impossible in the general case. Consider this extended grammar:

fake (<I> | <J>);
<I> ::= c | b | a ;
<J> ::= a | b | c ;

The resulting minimal DFA is going to look like this:

As you can see, there are conflicting expectations as to the order of transitions in the DFA: on one hand we expect (a, b, c), on the other (c, b, a). There’s no right answer in this case.

[Drugoy]

I think what you described is a corner case, so let's exclude it from the initial FR:
suppose that all arguments to be autocompleted are named args (as in --host being the arg name in the psql --host blah).
The list of such args shouldn't be alphabetically ordered.
Then there are lists of possible values for a specific named arg - nor those lists should be alphabetically ordered.

Is the task in such a reduced case achievable?

[adaszko]

For cases like psql above, you can simply specify options as a sequence in the grammar. E.g. for psql to first complete —host, only then —dbname you write:

psql --host <HOST> --dbname <DBNAME>;

[Drugoy]

1. Let's talk about the list of named args.
   Your suggested .usage treats args --host and --dbname as non-optional. But they are both optional. And I even might use --service instead. Or any combination of these. So I wrote such a .usage:

psql [<OPTION>];                                                                                                                                                                                        
                                                                                                                                                                                                        
<OPTION> ::= --service <SVC>                                                                                                                                                                            
        | --host                                                                                                                                                                                        
        | --port <PORT>                                                                                                                                                                                 
        | --dbname                                                                                                                                                                                      
        ;                                                                                                                                                                                               
                                                                                                                                                                                                        
<SVC> ::= { sed -n 's/^\s*\[\(.*\)\]/\1/p' ~/.pg_service.conf };                                                                                                                                        
<PORT> ::= 5432;

but I still get suggested --dbname first, while I'd like the first suggested arg to be --service (then --host, then --port, then --dbname).
2. Now about lists of suggested auto-completions as values for specific named args (--service in my example).
If I execute the sed from the above .usage - I get a list of services in the order of their presence in the file ~/.pg_service.conf, but when I get them as the list of suggested auto-completions - they get sorted alphabetically.
I'd prefer to have a control over sorting in such cases: sometimes sorting is desired, but sometimes it is not.

[adaszko]

What shell are you on?

[Drugoy]

zsh 5.8

[adaszko]

It’s zsh that’s doing the sorting, not complgen:

complgen produces completions in this order: --host --service --port --dbname whereas they get displayed sorted by zsh

[Drugoy]

I am sorry, I don't understand zsh completions. Guys on #zsh @ irc.freenode.net said that it's just the way your util generates the completion rules that makes them sorted.
I've found that built-in zsh's completion list for gcc -{TAB} is not sorted, for example (in particular -imacros going way after -Wzerotrip). I've tried to compare the file produced by complgen and /usr/share/zsh/functions/Completion/Unix/_gcc zsh's native autocompletion file and they are simply too different for me to figure out how to make complgen's artifact not sort suggested values.

[adaszko]

I figured out the how to disable zsh’s sorting. It’s a matter of passing the right options to compadd.

The way it’s currently called: compadd -d descrs -a args.
The way it’s ought to be called to preserve order: compadd -J unsorted -o nosort -d descrs -a args.

That’s not the whole story though. Hash tables are used extensively throughout complgen to represent DFA transitions. In order to get the order of options from the grammar, the hash table would need to be replaced with something that preserves the insertion order.

[Drugoy]

Guys on the channel first only suggested adding -o nosort, which I tried and which didn't affect the result (so I hadn't even mentioned it to you).
But then they wrote this:

the autogenerating zsh completions cli tool doesn't use the helper functions that allow the user to change the sorting order if they desired
but adding -V matches to compadd will leave them in the unsorted order, or if you truly want to use -o nosort, you still need -J matches
the sort style is for helper functions to know what to pass to the eventual compadd call: -V, -J and/or -o
directly calling compadd in your completer like that is ill advised in my opinion tho. you miss out on a lot of the perks that zsh completion system offers

After replacing compadd in the script, produced by complgen with compadd -J unsorted -o nosort I got the desired behavior and became a tad bit happier :)

[adaszko]

After replacing compadd in the script, produced by complgen with compadd -J unsorted -o nosort I got the desired behavior and became a tad bit happier :)

Nice! If you get tired of editing it manually after every compilation and you’re up for a contribution, this functionality could be encoded in an additional option, like complgen compile --disable-sorting. For zsh, it would do compadd -J unsorted -o nosort, for bash complete -o nosort, for fish, complete --keep-order. Should be a pretty short and easy patch.