From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Daniel Mendler Newsgroups: gmane.emacs.devel Subject: Improvement proposals for `completing-read' Date: Wed, 7 Apr 2021 13:16:52 +0200 Message-ID: Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="34727"; mail-complaints-to="usenet@ciao.gmane.io" To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Wed Apr 07 13:17:52 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 1lU6C0-0008tB-8v for ged-emacs-devel@m.gmane-mx.org; Wed, 07 Apr 2021 13:17:52 +0200 Original-Received: from localhost ([::1]:38556 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lU6Bz-0000aU-9P for ged-emacs-devel@m.gmane-mx.org; Wed, 07 Apr 2021 07:17:51 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:36396) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lU6BS-00009P-9E for emacs-devel@gnu.org; Wed, 07 Apr 2021 07:17:18 -0400 Original-Received: from server.qxqx.de ([2a01:4f8:121:346::180]:36613 helo=mail.qxqx.de) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lU6BO-0001f0-Nz for emacs-devel@gnu.org; Wed, 07 Apr 2021 07:17:17 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=qxqx.de; s=mail1392553390; h=Content-Transfer-Encoding:Content-Type:MIME-Version:Date: Message-ID:Subject:From:To:Sender:Reply-To:Cc:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: In-Reply-To:References:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=2W7f3r7ET9OWE5LAUb+p47ENYLX3hWlO1XHGAcP3L6E=; b=RIe6HDcHJl5d9e0p5N6/hBjXno A8sRvJAC35PJeo9cy3JuKFuNUkDSiuZwE1gCWWTV3H+MUw+7Ua2MlkkMam6RxtdFjdAWxgbevde1Q yzh9ji4ZGGDri5H1RqJKZ8wjpwtMxIahxw+jfZo/Zsynur3ASUcFVsL7UyeoF5xuBgVE=; Content-Language: en-US Received-SPF: pass client-ip=2a01:4f8:121:346::180; envelope-from=mail@daniel-mendler.de; helo=mail.qxqx.de X-Spam_score_int: -41 X-Spam_score: -4.2 X-Spam_bar: ---- X-Spam_report: (-4.2 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_PASS=-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:267503 Archived-At: While working on a set of packages around completion ([Selectrum], [Consult], [Marginalia], [Embark], [Orderless], [Vertico], ...) it became clear that there are a few spots where improvements to the `completing-read' API can be made. After submitting my Vertico package to GNU ELPA two days ago there has been the follow-up discussion in the thread "Stepping Back: A Wealth Of Completion systems", where the potential introduction of a `selecting-read' function has been proposed by Philip Kaludercic. I want to respond to that and echo the opinion stated by Stefan Monnier: I kind of agree, yet at the same time, the difference between the two is very small in most cases. So I think it might be worthwhile to look at it instead as making it possible for the caller to give a *hint* about what kind of UI would be best. 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 the effort for the implementors of completion UIs. If a replacement can be made which supersedes `completing-read' fully, this cost is reduced, but such a change is still very impactful given that many packages use `completing-read'. I see `completing-read' as a comparatively complicated API, which is hard use and hard to implement in its full extent. For the end-user it helps to wrap the function in a more friendly API. Eric Abrahamsen has used such an approach in his Gnorb package, see `gnorb-select-from-list'. I have done the same in my Consult package, see `consult--read'. Maybe moving to a more comfortable (but mostly `completing-read' compatible) API would mitigate the usability issues people are observing? For now I want to be a bit more concrete and look at `completing-read' and `minibuffer.el' directly and propose a few moderate improvements. The improvements can help package authors in the short term, since they address issues with the current state of the API. I am willing to follow-up with patches, which implement the proposals. The proposals have been inspired by the work on the aforementioned packages and came to light in discussions with the respective authors of the packages: Clemens Radermacher of Selectrum, Omar Antolín Camarena of Embark and Orderless, and also Dmitry Gutov and Protesilaos Stavrou. I am very much interested in your opinion regarding the following proposals. Daniel Mendler [Selectrum] [Consult] [Marginalia] [Embark] [Orderless] [Vertico] Improvement proposals for `completing-read' =========================================== .. Proposal 1: Disabling the history .. Proposal 2: More efficient sorting .. Proposal 3: Sort file names by history .. Proposal 4: Add support for `group-function' .. Proposal 5: Forbid the null completions for `REQUIRE-MATCH=t' .. Proposal 6: Return text properties from `completing-read' .. Proposal 7: Allow duplicates and retain object identity .. Proposal 8: Completion style optimization of filtering and highlighting 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) `---- 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'. 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. The Vertico package contains the function `vertico--sort' which special cases file names. This approach could be adopted by `completion-all-sorted-completions'. Unfortunately `vertico--sort' does not sort file names by history if the file names are completed using `partial-completion' and I have not found an efficient way to do that. More generally, one may want to sort completion candidates if `completion-boundaries' are used by the `minibuffer-completion-table'. However since sorting files already requires special casing and files are most important, I did not implement this in `vertico--sort'. 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. 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. This is useful for example if candidates originate from different sources. Grouping is popular in Helm, for example as seen in [helm-m-x]. For now, I implemented `group-function' support under the name `x-group-function' in the Vertico package. My Consult package uses this functionality for candidates originating from [multiple sources]. Grouping can be added to the default completion system by modifying `completion-all-sorted-completions' and `completion--insert-strings'. A proof of concept can be found on the [Consult wiki]. Furthermore support for `x-group-function' has been added to [Selectrum] and the external [Icomplete-vertical] package, which is to be distinguished from the Icomplete-vertical patches proposed on emacs-devel. [helm-m-x] [multiple sources] [Consult wiki] [Selectrum] [Icomplete-vertical] 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. Note that null completion cannot occur if a default value is passed to `completing-read'. Therefore null completion can be avoided by a wrapper, which passes a special default argument. Unfortunately this leads to flicker. ,---- | (defun completing-read-non-null (prompt table) | (let ((ret)) | (while (eq (setq ret (completing-read prompt table nil t nil nil | 'null-completion)) | 'null-completion)) | ret)) | (completing-read-non-null "Prompt: " '(first second third)) `---- 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. 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. When storing the selected candidate in the history, the text properties should still be stripped to avoid serialization problems. There is still null completion, see Proposal 5. As of now the user has to look up the associated data in an an association list, but there is the more serious issue of duplicate candidates as addressed in the next section. Example: ,---- | (completing-read "Text properties: " | (list (propertize "first" 'id 0) | (propertize "second" 'id 1) | (propertize "third" 'id 2)) | nil t) `---- 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. It is reasonable to handle the deduplication on a case by case basis in each completion table. Furthermore empty strings are removed by default completion for some reason. I rather consider this a bug in a completion table if it returns undesired empty candidates. Allowing duplicates is slightly more efficient and allows to retain the object identity of the candidates. If a candidate is selected which is part of the collection, this exact candidate should be returned. This subsumes Proposal 6 and allows to use text properties for disambiguation of candidates. Note that this proposal is useful mainly for completion tables which disable sorting by setting `display/cycle-sort-function' to the identity function. Currently if identical candidate strings are used for completion, these strings must be manually disambiguated by adding some unique prefixes or suffixes. I had this issue when implementing the `consult-line' command, which is a Swiper-like command based on `completing-read'. Furthermore the disambiguation issue occurs when mixing candidates from different candidate sources. Example: ,---- | (completing-read "Duplicates: " | (list (propertize "dup" 'id 0) | (propertize "dup" 'id 1) | (propertize "dup" 'id 2)) | nil t) `---- 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. 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'. 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 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. 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.