From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: Improvement proposals for `completing-read' Date: Wed, 07 Apr 2021 13:11:39 -0400 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="17197"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux) Cc: emacs-devel@gnu.org To: Daniel Mendler Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Wed Apr 07 19:12:58 2021 Return-path: Envelope-to: ged-emacs-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1lUBjb-0004Hh-V8 for ged-emacs-devel@m.gmane-mx.org; Wed, 07 Apr 2021 19:12:56 +0200 Original-Received: from localhost ([::1]:42668 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lUBja-000413-UL for ged-emacs-devel@m.gmane-mx.org; Wed, 07 Apr 2021 13:12:54 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:37264) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lUBic-0003ZE-MX for emacs-devel@gnu.org; Wed, 07 Apr 2021 13:11:54 -0400 Original-Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:8087) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lUBiS-0004lU-Aw for emacs-devel@gnu.org; Wed, 07 Apr 2021 13:11:53 -0400 Original-Received: from pmg1.iro.umontreal.ca (localhost.localdomain [127.0.0.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id CBDD4100216; Wed, 7 Apr 2021 13:11:42 -0400 (EDT) Original-Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id 44C781001FE; Wed, 7 Apr 2021 13:11:40 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1617815500; bh=SjU+xLdHtjsRejTxOt7ANJHPt0CBhOJ0IP0Vs5/ntYo=; h=From:To:Cc:Subject:References:Date:In-Reply-To:From; b=m/p59dABhQOi1gF3KtXnaLku8E4pMSKV8o2coPQZjNLV1AddwhYl7HLD4ivd0kc0Z NV5c0YB6a7vX5+/6PVjUzWWNZ0KC8IJ3rdANOZVF7pBDGm1uW5vUL9GRtAGm4FIcdX VSK8YDyJNufI8Js2HfanOVl/AVdWFiGY35MMb2sKgnpTJ9HiShSHIZ3fGxkdMLy+Wx W7OzIkqvFRJHH5S3gkkMnBFXZ+7MaYd685OEawx1tsUR2G7hh0lm9Izh4obkjYMFR3 XqIQBIVa3aZdA3loBhJTZ0mWGVhfzSBaCrwxg+tIM2yrr05evj68h/cHhsun8e1/2K BiIahhbfJ+ryA== Original-Received: from alfajor (104-222-126-84.cpe.teksavvy.com [104.222.126.84]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 1FEE81202D7; Wed, 7 Apr 2021 13:11:40 -0400 (EDT) In-Reply-To: (Daniel Mendler's message of "Wed, 7 Apr 2021 13:16:52 +0200") Received-SPF: pass client-ip=132.204.25.50; envelope-from=monnier@iro.umontreal.ca; helo=mailscanner.iro.umontreal.ca X-Spam_score_int: -42 X-Spam_score: -4.3 X-Spam_bar: ---- X-Spam_report: (-4.3 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.io gmane.emacs.devel:267543 Archived-At: > It might deserve a completely new function to replace > `completing-read', but I think it would be good to make this > new function such that it makes `completing-read' obsolete. > > The cost of introduction of a new function is not to be underestimated > in particular if it sits at a central place. Introducing another > function which only differs slightly from the existing `completing-read' > function could do more harm than good if it increases inconsistency and All I meant is that the design could start from a clean slate, and afterwards look at the result and see whether/how it can be retrofitted into `completing-read`. > Proposal 1: Disabling the history > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > > I propose to allow the symbol `t' as `HIST' argument to > `completing-read' in order to disable the history. This aligns > `completing-read' with `read-from-minibuffer'. This change requires a > modification of the function `completion-all-sorted-completions', > which sorts the candidates by history position and currently assumes > that the `minibuffer-history-variable' is a variable symbol. > > Example: > ,---- > | (completing-read "No History: " '(first second third) nil nil nil t) > `---- [ I'm not sure there's a great benefit here, since in the situation where simplicity is what matters, using nil seems like a much better choice, but: ] Good idea. > Proposal 2: More efficient sorting > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > > Currently candidate sorting is `O(m*n*log(n))' with history length m > and candidate list length n. This leads to a noticeable slowdown for > large values of `history-length'. I propose to improve the speed of > `completion-all-sorted-completions' by using a hash table. The Vertico > package provides an optimized sorting function, see `vertico--sort'. You're asking whether we should fix a performance bug, the answer is: yes. > Proposal 3: Sort file names by history > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > > Currently `completion-all-sorted-completions' does not sort file > candidates based on history, when the candidates are file names and > the history elements are paths. I think this is just a bug in that we don't pay attention to boundaries when sorting. It's probably just a matter of prepending the prefix removed from the all-completions output when looking for an element in the list (the end of this prefix is returned in the last `cdr` of `completion-all-completions`). Similarly, we may want to compare with `string-prefix-p` rather than `equal`. > Proposal 4: Add support for `group-function' > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > > Completion tables can provide the functions `display-sort-function', > `cycle-sort-function', `annotation-function' and `affixation-function' > as completion metadata. I am proposing the addition of a > `group-function', which receives a list of candidates and returns a > list of groups `((group-title . group-candidates) ...)'. The group > function should retain the present order of the candidates within the > groups. Sounds fine to me, yes. [ This touches a delicate issue, of course: since some completion styles have their idea of sorting (e.g. `flex`), some UIs have other ideas, and then some completion tables have yet more ideas. I'm not super-happy with all those functions, to be honest, but it's not clear what an API should look like to better decouple the UIs, styles, and backends in this respect, so for now the best is probably to keep piling on stuff until a clearer picture emerges. ] > This function is used in two ways. After sorting the candidates, the > group function is called with the candidate list in order to produce a > grouped list. Then the completion UI can call the group function a > second time when displaying the candidate groups in order to determine > the group titles. I'd have expected the "list of lists" result to already include the group titles. > This is useful for example if candidates originate from different > sources. Grouping is popular in Helm, for example as seen in > [helm-m-x]. Of course, it may be difficult for your function to recover the origin of a candidate if the same candidate can come from two or more sources. > Proposal 5: Forbid the null completions for `REQUIRE-MATCH=t' > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > > If `completing-read' is passed `t' as argument to `REQUIRE-MATCH', the > completion must match a candidate from the completion table. However > there is also the possibility to exit the minibuffer with a null > completion. I propose to disallow this possibility. This change makes > it easier for users of `completing-read' since they can rely on > setting `REQUIRE-MATCH' to `t' and do not have to handle the null > completion specially. [...] > If it is desired to avoid a backward incompatible change one could > consider adding a new special value for `REQUIRE-MATCH', for example > `'require-candidate', which explicitly forbids null completion. I generally like the idea (I've also been bothered by this possibility to return an empty string), but I haven't looked into fixing the problem. There's already an obvious way to tell `completing-read` whether the null string is acceptable (by making the completion-table's `test-completion` return non-nil for it), so maybe we don't need a special new value. But I don't have a good sense of the scale of the potential compatibility breakage [I suspect that such a change might also fix some code which doesn't bother to check for an empty output. ] IOW, this deserves a bit for `grep`ping through all the ELisp code you can get your hands on and try to see how/if it would be affected by such a change. As you say, in the worst case we can introduce a new value for REQUIRE-MATCH, so as to be backward-compatibility-safe. But I'd be interested to see if there are cases where the current empty-string "(mis)feature" is actually beneficial. > Proposal 6: Return text properties from `completing-read' > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > > As of now, `completing-read' strips text properties from the result > string. This behavior is reasonable for strings, which are not present > in the collection if `REQUIRE-MATCH/=t'. However if a candidate string > is selected, which is a member of the collection, the text properties > can be retained. If this is implemented and `REQUIRE-MATCH=t', the > user of `completing-read' can always rely on text properties to attach > arbitrary data to the candidates. I think what you mean is that the text properties should be stripped from the text taken from the minibuffer, but should be preserved from the text taken from the completion tables's candidates (and then together with that, you'd want to guarantee that when require-match is non-nil the string object returned is actually one of those candidates returned by the completion table)? This is one of the important differences between "completion" and "selection" in that completion is about using a completion-table as a helper to write a chunk of text (but the resulting text in the end should not be affected by how the user used the completion table to come up with the final text), whereas selection is about choosing among a set of candidates and the result is expected to be `eq` to one of the candidates. I agree that it would be good to move towards making `completing-read` better support the "selection" use case. > Proposal 7: Allow duplicates and retain object identity > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > > If a completion table contains duplicates, these duplicates should not > be removed. There are not many completion tables which generate > duplicate candidates and there exist multiple completion systems which > do not perform deduplication at all. [ I've been resisting this for quite some years, as Drew can testify. ] While I agree with preserving object identity, the issue of duplicates is more problematic, because it means the user can't choose between them using self-insert-command + RET. IOW such completion-tables are fundamentally making assumptions about the kind of UI with which they can be used. > Proposal 8: Completion style optimization of filtering and highlighting > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > > While working on Selectrum and Vertico it has been found that > highlighting has a significant cost. This matters if the number of > displayed candidates differs greatly from the number of filtered > candidates. Therefore it would be good to have a possibility to > separate highlighting and filtering. Agreed. It doesn't seem easy to retro fit this into the current API, tho. [ The redesign of the completion API which I had started back in 2019 (see scratch/completion-api for a very rough sketch of the general direction) also aimed to fix this. ] > In the Orderless completion-style, there is a variable > `orderless-skip-highlighting' which can be set to `t' or to > a predicate function. Depending on the value of this variable > highlighting is applied or not applied by > `completion-all-completions'. That's not a great solution, but as a temporary patch until we have a better API it's OK. > In the first step, all the candidates can be computed and filtered > with `orderless-skip-highlighting=t', see > `vertico--recompute-candidates'. Afterwards, when displaying the > candidates, the completion UI has to pass the small subset of > candidates once again through `completion-all-completions', this time > with `orderless-skip-highlighting=nil', see `vertico--highlight'. I suspect "pass the small subset of candidates once again through `completion-all-completions'" can be tricky to do (e.g. for things like file-name completion with `partial-completion`). > I propose to generalize this Orderless feature by introducing a > variable `completion-skip-highlighting', which behaves the same as > `orderless-skip-highlighting' and is implemented for all built-in > completion styles. In Orderless, the filtering and highlighting is > already separate internally, therefore skipping the highlighting > turned out to be a natural decision in Orderless. The situation could > be different for the built-in styles. I think in all styles I can think of highlighting is done as a separate step. > As an alternative, one can introduce a third function > `completion-highlight-completions', which is specified in > `completion-styles-alist'. But I suspect that the introduction of an > extra function requires more effort. I'd rather not go there, indeed. Stefan