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

["João Távora" <joaotavora@gmail.com>]

Dmitry Gutov <dgutov@yandex.ru> writes:

> On 20.08.2021 13:35, João Távora wrote:

> Even if the constant factor is somehow significant (which would be a
> surprise, but OK, some pathological cases might turn up), if you do
> any kind of grouping at all, you will incur the same cost, won't you?

Some tables and grouping strategies, like the xref table, seem to be
"naturally" grouped by the way you harvest candidates.  For others, we
could make just make it so that they are.  That "make it so" wouldn't
necessarily mean calling `group-function` for every candidate.

> Unless you only apply the grouping to the first V matches (where it's
> the number of lines visible in the minibuffer). But even then my
> suggestion can be adapted to this approach. Using the example from the
> message I replied to, you would put all the matches in 'xref.el' into
> the same group, not two groups.
>
> The cost of the grouping function doesn't matter when making this
> choice.

Yes, I think you see what you mean.  But I also imagine it would be
terrifyingly confusing for a user of a scrolling dropdown to see
candidates jump back and forth into their groups as the user scrolls
down to see a new candidate and hide another.  If what I imagine isn't
what you mean, maybe you could code something up and show what you mean.

> I took an existing example of a grouping UI and suggested a slightly
> different one. With no expected difference in performance.

As I wrote, that's a fine presumption/intutition, though it is, IMHO,
vunerable to the graces of whatever 'group-function' has been coded by
the completion table author.  You should now confirm your intuition with
an actual patch and benchmarks.

My original point about "doing too much work" is that it is almost
impossible that it will somehow make the process _quicker_ than what it
actually is right now.  My suggestion to eliminate sorting _does_ makes
it quicker, demonstrably.

But maybe the two suggestions can even coexist: eliminate a+l+r sorting
and add re-grouping.  That is likely quicker than the current state.

>> You suggestion, as far as I can see, has none of these three elements.
>> So if you or someone else wants to experiment with the re-grouping (with
>> whichever implemention),
>
> Why do you call it re-grouping? Grouping happens after sorting, there
> is no prior grouping step.

For example, in xref.el the matches provided by the completion table
are, IIUC, already "naturally" grouped, because they are collected file
by file, and the file is the group.  That grouping is then completely
destroyed by a+l+r sorting.  Your proposal would, I presume, destroy
that sorting to restore grouping.  Hence "re-group".

Note that I previously assumed, mistakenly, that the entries in C-x 8
RET were also naturally grouped.  They're not.  They could very easily
be, and with no performance penalty.

>>>> 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.
>>> Right. I just don't think either is costly, most of the time.
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>> Did you read my previous message where I reported that C-x 8 RET
>> currently takes about a second to compute completions and only 0.6
>> seconds when sorting is removed?
> I was talking about the grouping step, obviously. Not being costly.

You wrote "I just don't think either is costly".  

> Try disabling grouping. Is completion still slow? Then it's a problem
> with sorting speed that needs to be solved separately anyway.

icomplete.el doesn't do any grouping, it merely prints the grouping
information as headers for the few matches that it will print.
completion-all-sorted-completions also doesn't care about grouping.  So
there's nothing to disable in that regard.

>> This is flex doing its thing.
> Yup. This is what I suggested to change.

As I explained two or three times now: you can.  In a new dmitry-flex
style.  That style is only a few lines of code away, I suppose.  Or a
defcustom, if you prefer those.  The current behaviour for 'flex' is the
correct one.  It was conceived like this.  flex scoring trumps grouping,
table orders, etc...  If you don't like this you can change this, like
everything in Emacs.

João