Imenu missing completion entries when flattening by group

[brownts]

I'm attempting to use the Emacs 30 "imenu-flatten" setting configured for grouping in combination with Vertico. When I do this, Vertico doesn't show all of the candidates if there are multiple groups which contain a candidate with the same name. The following is a reproducer that can be used which demonstrates that when vertico-mode is not enabled, the default completion shows all entries, however when vertico-mode is enabled, there is a missing candidate.

This is similar (but different) to an issue I reported on the Emacs bug mailing list here, which requires completions-format to be set to vertical or the built-in completion has a similar issue (which hasn't been resolved).

(progn
  (setopt completions-group t)
  (setopt completions-format 'vertical)
  (setopt imenu-flatten 'group)

  (require 'imenu)
  (require 'vertico)

  (dolist (arg '(-1 +1))
    (vertico-mode arg)
    (setopt imenu-eager-completion-buffer vertico-mode)
    (imenu-choose-buffer-index (format "(vertico-mode = %s) Index item: " vertico-mode)
                               `(("XYZ" . (("123" . ,(point-min-marker))))
                                 ("Bar" . (("Foo" . ,(point-min-marker))))
                                 ("Baz" . (("Foo" . ,(point-max-marker))))))))

[minad]

Hi.

Thanks for the report. I had noticed this discussion before on the Emacs bug tracker. Vertico filters out duplicate candidates as in this case where the strings "Foo" are equal. A while ago the default completion UI didn't support completion candidates with text properties, but this has been changed recently.

Instead of calling delete-consecutive-dups in vertico--recompute we could use the code from Corfu which takes text properties into account:

https://github.com/minad/corfu/blob/ec846c6aa373931508cc078b49a3a8ba8265c453/corfu.el#L607C1-L632C8

Would this solve the issue satisfactorily?

I don't think this issue is particularily urgent, given that support for minibuffer-allow-text-properties in completing-read will arrive only in Emacs 30 and given that imenu couldn't handle duplicates in the past. In my Consult package I use deduplication via invisible tofu characters, which is a bit hacky but works reliably on older Emacs versions. See also consult-imenu. In the future I can hopefully replace the tofu mechanism with text properties, but it will be a few years until then, since my packages also support Emacs 28 and 29.

[minad]

I just checked icomplete-mode on Emacs 30 and it still seems to delete duplicate candidates (with respect to equal), such that your test from above fails there too. I believe this happens due completion-all-sorted-completions calling delete-dups. Furthermore in default completion formatting functions like completion--insert-column delete consecutive duplicate strings, which only preserves duplicates if groups or annotations are used, but not based on other text properties or candidate formatting. So overall the situation regarding duplicate candidates with text properties is unsatisfactory and incoherent.

My preferred solution would be to simply never delete duplicate candidates in the completion UI and instead fix completion tables which produce unwanted duplicates. This would be the most efficient solution. Completion tables which actually want to produce duplicates (modulo text properties) would function correctly. Alternatively duplicate candidates could be preserved if they differ in their text properties, as I've implemented in Corfu, but this is not the most elegant nor the most efficient solution.

[brownts]

Instead of calling delete-consecutive-dups in vertico--recompute we could use the code from Corfu which takes text properties into account:

https://github.com/minad/corfu/blob/ec846c6aa373931508cc078b49a3a8ba8265c453/corfu.el#L607C1-L632C8

Would this solve the issue satisfactorily?

I believe so since it appears imenu-flatten adds the group information as a text property on the entry.

See also consult-imenu.

Yes, consult-imenu is my preferred Imenu package. I value the live preview and intelligent handling of duplicates (with numbering). I was just testing out the new imenu-flatten functionality in Emacs 30 and making sure it worked properly with the major modes I maintain; that's when I stumbled across the issue with missing entries.

I just checked icomplete-mode on Emacs 30 and it still seems to delete duplicate candidates (with respect to equal), such that your test from above fails there too. I believe this happens due completion-all-sorted-completions calling delete-dups. Furthermore in default completion formatting functions like completion--insert-column delete consecutive duplicate strings, which only preserves duplicates if groups or annotations are used, but not based on other text properties or candidate formatting. So overall the situation regarding duplicate candidates with text properties is unsatisfactory and incoherent.

I sent another message on the mailing list pointing out your discovery here with a reproducer for icomplete-vertical-mode. Hopefully it gets some traction, as I think it would be important that imenu-flatten isn't broken out of the gate in Emacs 30...not sure how common it would be to use this with grouping. Honestly, I was trying to replicate the consult-imenu layout in imenu-flatten.

My preferred solution would be to simply never delete duplicate candidates in the completion UI and instead fix completion tables which produce unwanted duplicates. This would be the most efficient solution. Completion tables which actually want to produce duplicates (modulo text properties) would function correctly. Alternatively duplicate candidates could be preserved if they differ in their text properties, as I've implemented in Corfu, but this is not the most elegant nor the most efficient solution.

Agreed. When I used Company, I had issues when combined with lsp-mode where the completion detail was lazily pulled from the language server, that there didn't appear to be enough information available to prevent Company from de-duplicating overloaded functions. I ended up adding advice to defeat the de-duplication functionality.

When I use Corfu, I don't seem to run into that issue.

[minad]

I believe so since it appears imenu-flatten adds the group information as a text property on the entry.

Can you please test this?

Hopefully it gets some traction, as I think it would be important that imenu-flatten isn't broken out of the gate in Emacs 30...not sure how common it would be to use this with grouping.

It is important for me that the issue is not about imenu only. It is about text properties and duplicate candidates in general. This should be fixed in a coherent way, and not only for imenu. In fact, the imenu fix to add text properties added a little inconsistency to the completing-read mechanism.

Maybe we can ask Stefan @monnier to comment on this. Stefan what do you think about duplicate candidates? My suggestion would be to never delete duplicate candidates. This will ensure that duplicate propertized candidates are always displayed and it will remove the performance penalty of removing duplicates. This matters with thousands of candidates. We already improved there with lazy highlighting, so it would be good to go even further regarding performance.

Of course then the problem is shifted to the completion tables to disambiguate duplicates, by adding suffixes, fontifying, annotating or by grouping them. Right now there exist multiple buggy (in my opinion) completion tables which produce identical duplicates and then expect the UI to clean that up. I assume that each of these tables can be fixed one by one (I am willing to help and review and fix the tables in the Emacs/GNU ELPA code base.)

Alternatively we could add some completion metadata retain-duplicates which is nil by default and would lead to the retention of duplicates if set. This would be the backward compatible solution. Another alternative would be to delete duplicates modulo equal-with-properties instead of equal as I have done in Corfu. This works quite well there, but is not pretty and not efficient.

Agreed. When I used Company, I had issues when combined with lsp-mode where the completion detail was lazily pulled from the language server, that there didn't appear to be enough information available to prevent Company from de-duplicating overloaded functions. I ended up adding advice to defeat the de-duplication functionality.

As far as I know this has also been fixed in Company with a different mechanism, where candidates are deduplicated module equal and the result of the annotation-function. This is the less general and less efficient approach than the one in Corfu where equal-with-properties is used.

You see, there is quite a bit of incoherence regarding duplicates, but it is a real problem. Some completion tables generate duplicates out of laziness of cleaning them up, some completion tables generate duplicates and expect the UI to display and differentiate them, and most completion tables do not produce duplicates at all and are penalized by the deduplication. To be clear, the candidate differentiation in the UI can only take place when the candidates are selected via Completions or by pressing RET on a selected candidate in an Icomplete/Ivy/Helm/Vertico-style menu. As long as candidates are only completed in the minibuffer, no disambiguation can happen. But then when completion and duplicates are present the Completions buffer can popup since the result is not unique.

[minad]

@brownts @monnier

It occurred to me that another even simpler idea would be to disable the deduplication in the completion UIs if minibuffer-allow-text-properties is set in the minibuffer. I don't really like this since one has to use minibuffer-with-setup-hook to properly set the variable, so I would prefer the more transparent retain-duplicates metadata, which could also instruct the UI itself to set minibuffer-allow-text-properties, which I consider more of an implementation detail.

[minad]

Another reason why minibuffer-allow-text-properties does't work as a general solution is that we cannot use it in Company or Corfu. There the deduplication necessarily must be configured by some completion metadata like retain-duplicates, since we are not in a minibuffer context.

[monnier]

You see, there is quite a bit of incoherence regarding duplicates, but it is a real problem.

As long as we're using a completion API rather some new selection API, my opinion is that duplicates should be eliminated. E.g. replace the text property by some informative suffix. I can imagine circumstances where this can be a problem, e.g. because the actual text is then inserted in the buffer and we don't want the informative suffix in there, but for Imenu this does not apply.

[minad]

completing-read is only about completion only as long as no candidates are displayed. As soon as candidates are displayed, differentiating them via selection becomes a possibility. At that point we are on the selection pathway and we don't need another new API for that. All completion UIs support such selection, the Completions buffer, or various other UIs like the Icomplete or Vertico minibuffer menu.

In my Consult package the suffixes are noninformative and cryptic (Unicode tofus). For such candidates, inserting them into a buffer is a problem, arguably a worse one than if the suffixes are informative. It would be better to replace this mechanism with text properties plus retain-duplicates completion metadata.

[monnier]

`completing-read` is only about completion only as long as no candidates are displayed. As soon as candidates are displayed, differentiating them via selection becomes a possibility. At that point we are on the selection pathway and we don't need another new API for that. **All** completion UIs support such selection, the *Completions* buffer, or various other UIs like the Icomplete or Vertico minibuffer menu.

Maybe the UIs do, but the API is not designed for that, so using a completion table that relies on selection "increases friction".

In my Consult package the suffixes are noninformative and cryptic (Unicode tofus). For such candidates, inserting them into a buffer is a problem, arguably a worse one than if the suffixes are informative.

So, make them informative? In the mean time, inserting them is a UI problem, and as you say, all the UIs allow the users to "select". 🙂

It would be better to replace this mechanism with text properties plus `retain-duplicates` completion metadata.

Except that, as you encountered, it bumps into various problems because the infrastructure is designed for completion, not selection.

[minad]

Maybe the UIs do, but the API is not designed for that, so using
a completion table that relies on selection "increases friction".

Yes, but that's the problem of those completion tables and nevertheless such tables can be very useful for many people.

So, make them informative? In the mean time, inserting them is a UI problem, and as you say, all
the UIs allow the users to "select". 🙂

Duplicates arise naturally, e.g., identical lines in a file, or when candidates are merged from multiple completion tables. But there is not necessarily a way to disambiguate them with a useful and informative suffix. It is better to simply display them as is. And in the completion case, simply return the first one of the duplicates from completing-read (or just the plain string without properties).

Except that, as you encountered, it bumps into various problems because
the infrastructure is designed for completion, not selection.

There is no problem with disamiguation suffixes, except that they are technically ugly, and that it introduces some edge cases, e.g., when inserting candidates with suffixes. I would prefer to replace this with a retain-duplicates metadatum.

Anyway, this discussion was about Imenu which has been modified in Emacs 30 to use completion candidates with text properties, while the completing-read infrastructure is not ready for this. I tried to make proposals to resolve this in a general way.

[monnier]

I would prefer to replace this with a `retain-duplicates` metadatum.

I thank we made our positions clear, indeed.

Anyway, this discussion was about Imenu which has been modified in Emacs 30 to use completion candidates with text properties, while the `completing-read` infrastructure is not ready for this.

Right, I think this is best fixed in Imenu.

[minad]

Okay, how do you envision a selection API to look like and how should it differ from completion, and also how do you envision the UI to look like? I appreciate that the completion API can be used for completion and selection under a unified API and under a unified UI. For example file names can be nicely completed step by step, but at the same time I like that candidates can be displayed and selected, in case you don't know how to proceed otherwise. Even if we come up with a selection mechanism I guess I would still want to filter the candidates, and this has to happen by entering strings, which can be filter expressions or a query language. The difference could be that the objects we select from have an identity, a string and a display representation. But then, in completing-read right now, the objects have first and foremost a string representation. The string representation can be modified via display properties, so we also have a display representation, even if not cleanly separated. Object identity is lacking and can only be obtained by suffixes to the string representation. Alternatively it could be obtained via text properties and retain-duplicates. I think in contrast to a selection system with abstracted objects with identity and different representation methods the string-based completion mechanism isn't as clean as it could be, from an engineering or OOP perspective. But then I also kind of like the idea of centering the mechanism around strings - it kinds of fits the Emacs model which is first and foremost text. Using propertized strings is hacky but also somehow elegantly unifying, at least to a certain extent, until it is not. The same with Unix pipes. This is nice and elegant as long as everything we work with is simply formatted but as soon we want to add more structure, structured data, maybe with stronger type guarantees, the model comes to its limits.

[monnier]

Okay, how do you envision a selection API to look like and how should it differ from completion, and also how do you envision the UI to look like? I appreciate that the completion API can be used for completion and selection under a unified API and under a unified UI.

I don't know, but I think the main one is that the return value would have to be `eq` to one of the objects in the set of candidates. Also I'd probably make it so the candidates can be objects of any type and have some side-info about how to turn each candidate into a human-palatable form.