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:20:30 -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="661"; 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:44:25 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 1lUCE5-000AeN-84 for ged-emacs-devel@m.gmane-mx.org; Wed, 07 Apr 2021 19:44:25 +0200 Original-Received: from localhost ([::1]:38350 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lUCE4-0004xL-67 for ged-emacs-devel@m.gmane-mx.org; Wed, 07 Apr 2021 13:44:24 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:39994) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lUBr5-0003w0-NK for emacs-devel@gnu.org; Wed, 07 Apr 2021 13:20:39 -0400 Original-Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:5504) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lUBr1-0007wc-6x for emacs-devel@gnu.org; Wed, 07 Apr 2021 13:20:38 -0400 Original-Received: from pmg2.iro.umontreal.ca (localhost.localdomain [127.0.0.1]) by pmg2.iro.umontreal.ca (Proxmox) with ESMTP id CD4BA803C3; Wed, 7 Apr 2021 13:20:33 -0400 (EDT) Original-Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg2.iro.umontreal.ca (Proxmox) with ESMTP id 6C49380159; Wed, 7 Apr 2021 13:20:31 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1617816031; bh=5fsPSeYpVUSw6f6Tdre0YUHVLdUE2pIywKKgodoNzZc=; h=From:To:Cc:Subject:References:Date:In-Reply-To:From; b=Lz3IAUf98k4bM3/BLu6f6axWz3Hkv9olSF+xwMJchdhR7lbArITgdNZOst1mThpss HjeB7A5BMaJFAPCNAwcR37PLYokZjTMRW9n3NO6SupM566bxGX8jsNYB0hIYr9j4ZI dpoDCjvBihvUaFjGu8BbbnrtyL5L4caA8OBVJ4O81rPwPa8VIfwbUrLg+hAVC9XbTx heLJimcFqK5tb0Tl4hdahAj4JDHo5x5V4sWmBbwdSjl5PsxkdoZsY1NML2xy3BjItJ XHQ2VWqzQSclAX8WDxq/QPodMxU0vleX6HTufWTre6Ttakk3kpTcXCPQBh76LMO8Qb JiBkImrSltDJQ== Original-Received: from alfajor (104-222-126-84.cpe.teksavvy.com [104.222.126.84]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 39CE6120257; Wed, 7 Apr 2021 13:20:31 -0400 (EDT) In-Reply-To: (Stefan Monnier's message of "Wed, 07 Apr 2021 13:11:39 -0400") 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:267546 Archived-At: BTW, rereading the below, I see I'm sounding a bit too authoritative. I'm the original author of the minibuffer.el completion code, but remember that what I wrote is just my opinion: you'll want to convince the actual maintainers for some of those changes ;-) Stefan Stefan Monnier [2021-04-07 13:11:39] wrote: >> 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