bug#47711: [PATCH VERSION 2] Add new `completion-filter-completions` API and deferred highlighting

[Daniel Mendler]

On 8/13/21 2:05 PM, João Távora wrote:
>> The existing API `completion-all-completions`
>> necessarily has to allocate all the strings in order to attach
>> highlighting and scoring.  The new API solves this in a clean way by
>> both deferring highlighting and scoring.
> 
> I'm not sure you understand my alternative idea.  As far as I
> understand (and have actually measured) the lines:
> 
>    ;; Don't modify the string itself.
>    (setq str (copy-sequence str))
> 
> in minibuffer.el, in the function completion-pcm--hilit-commonality
> 
> Are the cause of the problem that _I am talking about_ and that
> I have actually measured.  Again you may be referring to a
> _different_ problem that I am unaware of.

You are right that the call to `copy-sequence` is a major bottleneck in
the filtering.  However you are wrong that this line can simply be
removed/disabled and the candidates can be modified.  The API guarantees
and has always guaranteed that the candidate strings are not mutated.
It is important to keep this property since this will preclude many bugs
due to string mutation.  By separating the filtering and mutation
(highlighting, scoring) my patch addresses the problem at hand in the
proper way.

Note that the UI also has no possibility to opt-out of the mutation.
The UI is actually not the one being concerned about the mutation here,
it is the backends (completion tables), which produce the strings.  If
one starts mutating these strings you will see bugs cropping up
throughout Emacs where shared strings suddenly have spurious additional
properties due to the completion filtering.

Mutation would be a reasonable choice here if the problem could not be
solved in a proper way.  But in fact it can be solved in a proper way
without mutating the strings at all as my patch shows.

> If one removes these lines, the process becomes much faster, but there is a
> problem with highlighting.  My idea is indeed to defer highlighting by not
> setting the 'face property directly on that shared string, but some
> other property
> that is read later from the shared string by compliant frontents.

This solution is much more ad-hoc and you still mutate the string which
is not allowed.

> The advantage that I see is that those adaptations apart, it is a small
> localized and effective change.

Note that your idea also does not address the other issues which are
addressed by my patch.  The new API `completion-filter-completions`
returns data which hasn't been available before, e.g., the end position,
which cannot be fixed given the existing API.

>> The main problem is that `completion-all-completions` allocates all the
>> strings every time the completions are filtered.  This is the same
>> performance issue you encountered in fido-mode/icomplete-mode.
> 
> OK. I encountered at least two different performance problems there, with
> quite different causes. So let's stick to the string-allocation problem.  Post
> a code snippet that demonstrates the problem the way you see it/experience it?

You can try my Vertico completion UI, which is available on GNU ELPA.
It implements deferred highlighting and there the performance difference
is perceivable.  Currently Vertico uses an advice-based hack to avoid
the over-eager string-allocations and the highlighting.

>> The second problem addressed by the new API
>> `completion-filter-completions` is that `completion-all-completions` is
>> limited in what it can return.  For example it cannot return the end
>> position of the completion.
> 
> And why is this a problem? Can you post an example of something you'd
> like to do, but can't?  Regardless, it does seem indeed like a "second" 
> problem
> (as you state) so perhaps something that can be addressed separately.

Please look at the FIXMEs in minibuffer.el which address this.
Currently only the beginning position of the completion boundary is
returned, which is only half of the information.

> I understand you've put time and effort into producing this work. We are
> all indebted and I promise to read it. But every API writer in history of
> programming has claimed those things and reality often shows otherwise.
> So it's not that your work can't be those things you claim, maybe it is, but
> generally the larger and broader the work the harder it is to reason about.

I stand by my claim and I also stand by the claim that
removing/disabling `copy-sequence` is not a proper way to address the
issues at hand and will introduce many bugs in the long run.  Please
take your time to look at the patch in earnest.  I would also like to
see others chime in here with their opinion.

Daniel