Selectrum: Selectrum not working with tables made by `completion-table-in-turn`.

[okamsn]

In Amx, keybindings are included in the candidate's text, but it is set-up so that a commands name is enough to fully match a candidate. However, this currently does not work in Selectrum, as reported in https://github.com/DarwinAwardWinner/amx/issues/43.

User DarwinAwardWinner, author of Amx, believes that this is because Selectrum doesn't correctly handle collections made with completion-table-in-turn. They give an example of what should happen in https://github.com/DarwinAwardWinner/amx/issues/43#issuecomment-704971709, using test-completion.

[okamsn]

I think the problem occurs in selectrum--normalize-collection, which uses the following to transform the table into a list of strings. I think that since it passes "", it isn't checking the other tables given to completion-table-in-turn.

(defun selectrum--normalize-collection (collection &optional predicate)
  "Normalize COLLECTION into a list of strings.
COLLECTION may be a list of strings or symbols or cons cells, an
obarray, a hash table, or a function, as per the docstring of
`try-completion'. The returned list may be mutated without
damaging the original COLLECTION.

If PREDICATE is non-nil, then it filters the collection as in
`try-completion'."
  (cond
   ;; Check for `functionp' first, because anonymous functions can be
   ;; mistaken for lists.
   ((functionp collection)
    (funcall collection "" predicate t))
...)

[clemera]

You have found the root of the problem, this also comes up when dealing with dynamic completion tables in general, see #114 and #156 where I tried to come up with an approach which allows to configure certain tables with special behaviour. Sooner or later we have to come up with a general solution for this, it's a question of performance vs full compatibility and how to support this while keeping the UI as responsive as it is now.

[DarwinAwardWinner]

You might want to have a look at the code in ido-cr+ to handle updating the list of completions for dynamic collections: https://github.com/DarwinAwardWinner/ido-completing-read-plus/blob/b9ca2566b867464c25b720e2148d240961c110e7/ido-completing-read%2B.el#L935

Fair warning, it's elaborate and probably not optimal, and you might not want to take the same approach. But you might find something useful in there.

[clemera]

Thanks, I will see if I can make use of it, next time I look into it, currently I don't have much time.

[DarwinAwardWinner]

Feel free to ping me if anything is unclear. It's not the most comprehensible code I've ever written.

[DarwinAwardWinner]

Hmm, having considered the specific use of completion-table-in-turn in amx, I've realized something: every item in the 2nd collection is a substring of an item in the 1st collection, which means that if I'm not mistaken,test-completion is the only way to determine whether a given input is in the 2nd collection, since try-completion, all-completions, and similar methods will always hit either the 1st collection or nothing.

However, I think this is an atypical use of completion-table-in-turn, and I have an idea of how to fix it on the amx side, so maybe you don't have to worry about it.

[clemera]

I looked a bit into it and it's like you described: In the case the 2nd collection only contains substrings of the 1st all-completions and try-completion will never query the 2nd table. I don't know the details about your use case but can you flip the order of the tables passed to completion-table-in-turn? I think if the 1st collection contains the substrings of the 2nd it should work as expected.

[DarwinAwardWinner]

I can't just swap the order, because then amx will almost never show key bindings. I have a possible idea for that, though.

[clemera]

Does the problem still exist?

[okamsn]

For this issue in particular, the problem was that Selectrum would not automatically select a candidate like "man" because the command's bindings were being appended to the command name.

This still happens, since the commands with keybindings shown are still valid candidates. What changes were you expecting?

For what it's worth, I've stopped using Amx on Emacs 28, which now has a built-in feature to display the command keybindings as annotations. It is similar to what I requested in DarwinAwardWinner/amx#43.

[DarwinAwardWinner]

Yes, this is still an issue. However, as mentioned before, the issue in the case of amx specifically is the result of amx using completion-table-in-turn in a somewhat non-standard way. Arguably I should be fixing that in amx (when I have the time).

However, the more general issue of handing completion tables created by completion-table-in-turn is still probably an important one that should be addressed, if it hasn't been already. Here's a brief outline of how I handle function collections in ido-completing-read+:

• re-generate the full list of completions after every input by calling all-completions on every prefix of the current input from the empty string to the full input
• cache the results of the above computation aggressively to make the performance acceptable
• use a short idle timer (1/4 sec) to avoid re-generating the completion list too frequently while the user is actively typing
• skip the idle timer and update immediately on every input if there are 1 or zero matches for the current input
• When the user presses RET with no current matches, check test-completion before saying it doesn't match, since sometimes that's the only way to tell whether the current input is a valid completion

See ido-cr+-schedule-dynamic-collection-update and the functions it calls for the details.

[clemera]

@okamsn

This still happens, since the commands with keybindings shown are still valid candidates. What changes were you expecting?

The way we do the table normalization changed a while ago and I thought that might have changed "something" but looking into this more I realized the underlying problem isn't touched by this (which is about handling of dynamic tables in general).

@DarwinAwardWinner
Thanks for your help, dynamic tables are still the weak spot for Selectrum. The problem is we don't want to slow down interaction with dynamic tables in general. A compromise could the to have a list of tables which we know don't need to be recomputed.

[DarwinAwardWinner]

A compromise could the to have a list of tables which we know don't need to be recomputed.

Unfortunately this isn't really possible, because many dynamic completion tables are constructed as closures on the fly right before calling completing-read on them (and elisp closures are generally opaque). More practical would be to have a list of calling functions/commands that are known not to require recomputation despite passing a function for the collection argument. In ido-cr+, I have code that actually inspects the entire call stack of the current command looking for functions for which ido should either be enabled or disabled: https://github.com/DarwinAwardWinner/ido-completing-read-plus/blob/master/ido-completing-read%2B.el#L659-L696. Feel free to borrow that code if you want to take a similar approach. (If you don't want to use cl-loop, there's also mapbacktrace.)

[minad]

@DarwinAwardWinner As I see it, the problem is also that the completing-read specification of dynamic tables is not well defined and messed up since it mixes candidate generation and filtering. At first glance it does sound correct to pass the dynamic input string as argument to the completion table. However if you do that for every table action, then the all-completions function will use this input string for prefix filtering. This makes only sense for the basic completion style and effectively disables the more sophisticated styles, like substring, flex, orderless and so on. For this reason the completion styles filtering takes place outside of the completion table, in the function completion-all-completions, which calls the completion style, which then calls the completion table (e.g. in completion-substring--all-completions and completion-pcm--all-completions). Since using a prefix filtering is often undesired, the passed input string often is the empty string. Therefore I don't really understand when the dynamic recomputation should actually happen. Certainly not when the empty string is passed as input. Selectrum as of now simply takes the approach to not support dynamic tables at all (#114). One thing @clemera and I observed is that the metadata action and the boundaries action always get passed the actual input string (#443, #448).

[DarwinAwardWinner]

I agree the specification of dynamic tables is ill-defined. IIRC there used to be cases where dynamic completion tables literally implemented their own completion system within completing-read. (I'm not sure if any examples of this are still in the current Emacs codebase, but the point is it's possible.) Given that level of flexibility, supporting every possible dynamic completion table simply isn't practical or even desirable.

As for supporting different completion styles, I'm lucky in ido-cr+ in that I only need to support the kinds of completion that ido supports. Of course, that still includes "flex-matching", and there are definitely edge cases where my solution will fail. However, in most cases, calling all-completions on every substring of the current input and then taking the union of the results is sufficient to find what the user is looking for. And as long as at least one of those substrings manages to surface the desired completion, then the full input can flex-match to it.

Incidentally, if you want a good example of a dynamic completion table in the wild, do C-h i and then g to run Info-goto-node (don't call it manually; it must be called from an Info buffer). Normally, it just completes Info topics from the current file. For example, if you're in the Elisp manual and pressg followed by TAB a few times, you'll be offered a list of completions for Info nodes within the Elisp manual and nothing else. Yet, you can also type (Emacs) and then press TAB, and now it will offer completions for Info nodes within the Emacs manual, even though those were obviously not offered when the input was empty. I don't fully understand how this completion table is implemented. It's a deep rabbit hole of layered abstractions. In ido-cr+ I just avoid using ido entirely for it and fall back to completing-read-default.

[minad]

I guess it is time to ask these questions on the Emacs devel list.

The idea to have various combinators for completion tables is a neat functional idea. It makes sense to have a caching (unary) combinator. And maybe some binary combinators could be useful. But from what I see, the completion-table-in-turn combinator does not make sense. A combinator which combines the candidates of two tables sounds more reasonable, than trying the tables in turn. But such a combinator does not exist and I do not see how it could be formulated, if you assume that the tables do some dynamic computation or use completion boundaries.

Furthermore, as I argued passing an non-empty input string is nonsensical for all completion styles except basic. The info completion table you mentioned does not seem particularly user friendly to me, not even with default completion, for which it has been designed. Maybe the proper way forward would be to remove all occurrences of problematic completion tables from the Emacs code base and then clarify the specification.

From my experience with Consult, you can achieve a lot with very restricted completion tables. However the asynchronous completion tables force the completion ui to refresh the candidate lists as soon as new asynchronous candidates are incoming. Probably there is no need for the complexity of the current completion tables, but I think completion boundaries are needed in any case also to support file completion?

[DarwinAwardWinner]

From what I can see, the purpose of completion-table-in-turn is to have "hidden" completion candidates that only show up if none of the regular candidates match. You would do (completion-table-in-turn regular-collection hidden-collection). For example, perhaps you are reading a command name, but you don't want to pollute the default completion list with the various mouse commands (e.g. mouse-set-point) because they usually only make sense when executed via mouse events. So you stuff those in the 2nd collection, and now the user can still enter them if they know what they're looking for, but the completion doesn't suggest them by default.

A combinator which combines the candidates of two tables sounds more reasonable, than trying the tables in turn. But such a combinator does not exist and I do not see how it could be formulated, if you assume that the tables do some dynamic computation or use completion boundaries.

Such a combinator does exist, named completion-table-merge. However, it seems the Emacs devs agree with your point about boundaries, since it contains this comment FIXME: same caveats as in `completion-table-in-turn'. And looking at completion-table-in-turn:

;; FIXME: the boundaries may come from TABLE1 even when the completion list
;; is returned by TABLE2 (because TABLE1 returned an empty list).
;; Same potential problem if any of the tables use quoting.

Also completion--embedded-envvar-table has a FIXME referencing this limitation to explain some code written to work around it.

So you're right, it seems that these combinators are indeed ill-specified and have broken edge cases that the developers are aware of. In fact, there's a whole bunch of FIXME comments all throughout minibuffer.el, more than any other elisp file that implements core emacs functionality.

[minad]

From what I can see, the purpose of completion-table-in-turn is to have "hidden" completion candidates that only show up if none of the regular candidates match.

This makes sense. You can implement tables which do not show candidates but which allow completion for these particular hidden candidates. Hidden candidates can be implemented too via predicates, but then you cannot complete them. (For example, in consult-buffer you first have to explicitly unhide the hidden candidates.)

completion-table-merge

This function even looks somehow reasonable. I think it works well for static tables.

My main problem with dynamic tables is really that I don't get when to recompute the candidate set. If we assume that the dynamic computation depends on the input string but is otherwise pure and does not access e.g. the minibuffer-contents, then we get the aforementioned prefix filtering problem. If the dynamic computation is impure, e.g., depends on minibuffer-contents, we cannot tell anything. Everything is possible and you really have to recompute the candidate set always. But for many static tables (wrapped in closures) the frequent recomputations are unnecessary and expensive. The approach you are taking in your ido-cr package is probably all one can do. But this is some kind of a sad state - the completion system should not have to maintain a list of its well/misbehaving/static/dynamic callers.

EDIT: I think the goal should be to get the completion-file-name-table to work with Selectrum. From this table one can infer what is needed for full support/compliance.

[DarwinAwardWinner]

static tables (wrapped in closures)

Incidentally, I did look into the possibility of implementing heuristics to identify such closures and treat them as static, but I concluded it wasn't practical, since closures returned by compiled code are just arrays of bytecode with the closed-over values stored somewhere inside, so you'd have to implement some kind of "near equality" test on compiled bytecode.

[minad]

Yes, I also thought about doing some bytecode analysis, but this does not sound like a good idea to me :laughing:

Maybe it is simply not possible to do better than default completion. As an experiment, maybe I will try at some point to play with a minimalistic completion system (similar to Omar's Embark live completion). Install a post command hook, open a completion-like buffer above the minibuffer, print only 10 candidates there. I wonder how slow this will be if one obtains the candidates every time. This would be very similar to icomplete/icomplete-vertical. There is certainly a bit of optimization potential in icomplete, e.g., icomplete uses inefficient sorting which is O(n*m) for n candidates and history length m. But I am not sure if there is much to win. I really like that Selectrum is so snappy.

[DarwinAwardWinner]

Maybe it is simply not possible to do better than default completion.

I'm pretty sure at this point that completing-read-default has enough idiosyncrasies that no completion system can be compatible with all the edge cases unless it behaves exactly like completing-read-default. This is why I've designed ido-cr+ with the approach of checking for cases that ido can't handle and just "punting" them back to completing-read-default, rather than try to support everything.

[DarwinAwardWinner]

By the way, one improvement you could make that should have no noticeable performance impact and would probably fix the specific case of amx is to use test-completion when the user presses RET (or possibly C-j). If the current input matches according to test-completion, you allow the user to exit with it even if a match is required and that input is not an element of the list returned by all-completions. Here's where I do this in ido-cr+: https://github.com/DarwinAwardWinner/ido-completing-read-plus/blob/master/ido-completing-read%2B.el#L819-L850

[minad]

I think @clemera added something like this in https://github.com/raxod502/selectrum/commit/000544dc2381ed7c87d1c92a050006ee993a753b.

[DarwinAwardWinner]

In that case, the specific interaction between amx and selectrum might already be fixed (though of course the more general issue of dynamic tables is not).

[minad]

See also https://debbugs.gnu.org/cgi/bugreport.cgi?bug=47771 regarding an issue with Info-goto-node completion. It throws unexpected errors.