Subject: bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function`

From: João Távora <[email-masked]>
Date: Fri, 20 Aug 2021 00:39:29 +0100

On Thu, Aug 19, 2021, 23:37 Dmitry Gutov <[email-masked]> wrote:

> On 19.08.2021 22:41, João Távora wrote:
>
> > That's a possiblity. But it might be performing too much work, at least
> > at first sight.
>
> Not sure I understand. Grouping is a linear operation, isn't it? O(N).

> Which is generally cheaper than the sorting step that came before.
>

Yes, but you'd be adding to it and that is always worse than _not_ adding
to it. And there's a constant factor in front of that O(N). So that's why I
think measurements should be taken, always.

Not to mention that if the table is already "naturally" grouped upfront,
your're incurring in both the sorting cost and the grouping cost, when you
could just be skipping both with little to no downsides, I would presume.

Of course, maybe I presume wrong, but Kévins report, who does use
completions-group, seems to confirm it.

> For the C-x 8 RET case and the xref table (the only
> > tables I know which use this) things seem to be naturally put into
> > groups already.  So sorting them alphabetically, by length, by history,
> > and _then_ destroying most (but not all) with the grouping could be not
> > so interesting if the there's a big a price to pay.
>
> Could be it misses information.
>

? Don't understand this...

OTOH, if you split completions belonging to the same group apart, you
> can end up with a list where there as as many group headers, as there
> completions (in the extreme case).
>

That's true. That's why my idea is to skip sorting altogether when tables
have a group-function, under the assumption that good speed matters much
more than applying the default sorting within each group.

For example, what does it matter to have a recently chosen UTF-8 completion
bubble up to the top of a group that's buried deep down in the long list of
groups? Not much, I think. And largely the same for the length and
lexicographical sorting.

I'd even venture to say it's like this for any table with a group-function,
though I only know two such tables. And that's why I proposed that generic
minibuffer.el patch. But, the alternative, to do it per table, could also
be fine and is reasonably short, too.

What behavior does (setq completions-group t) have?

Seems to be a flag that controls the presence of 'group-function' in some
tables. Can't speak of the other UIs, but icomplete just honors
'group-function' and does not double check the flag. It could, if it were
relevant, I guess.

It affects the default UI, IIUC.

Yes, I believe so. But what is the relevance?

João