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: Re: [PATCH] `completing-read`: Add `group-function` support to completion metadata (REVISED PATCH) Date: Sun, 25 Apr 2021 23:26:11 +0200 Message-ID: <4d9971af-9af1-97a6-61fc-d88d4d192dcc@daniel-mendler.de> References: <0bbdeece-90d5-160c-07ec-2ad8edbf9872@daniel-mendler.de> <87k0oqf5z7.fsf@mail.linkov.net> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="28622"; mail-complaints-to="usenet@ciao.gmane.io" Cc: Gregory Heytings , "emacs-devel@gnu.org" , Stefan Monnier , Dmitry Gutov To: Juri Linkov Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Sun Apr 25 23:27:06 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 1lamHS-0007KI-AS for ged-emacs-devel@m.gmane-mx.org; Sun, 25 Apr 2021 23:27:06 +0200 Original-Received: from localhost ([::1]:39164 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lamHR-0005qp-Dk for ged-emacs-devel@m.gmane-mx.org; Sun, 25 Apr 2021 17:27:05 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:51690) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lamGg-0005Py-Nu for emacs-devel@gnu.org; Sun, 25 Apr 2021 17:26:18 -0400 Original-Received: from server.qxqx.de ([2a01:4f8:121:346::180]:33519 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 1lamGd-000270-Vo for emacs-devel@gnu.org; Sun, 25 Apr 2021 17:26:18 -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:In-Reply-To: MIME-Version:Date:Message-ID:From:References:Cc:To:Subject:Sender:Reply-To: Content-ID:Content-Description:Resent-Date:Resent-From:Resent-Sender: Resent-To:Resent-Cc:Resent-Message-ID:List-Id:List-Help:List-Unsubscribe: List-Subscribe:List-Post:List-Owner:List-Archive; bh=DB/g0+KOxEMvNgyBB7uCA0/58I9Nn2eNkLbfmrsQwlU=; b=KE9h7eXaCxTtRks/HAfdtRtmnm cVhVYNMAsnVx335z3Syli9WCSxsx/sN6/SdQUWO647NWM5cGFn8EhbEIvDuRKW2CPGa11jI4d4FKS 2nWh5MyAVFlkigCSi/0XPP1q83luY9oa5IW16DPs5EcsJVV9u1c4kIrVbJrPoA5eeAEE=; In-Reply-To: <87k0oqf5z7.fsf@mail.linkov.net> 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:268427 Archived-At: On 4/25/21 10:45 PM, Juri Linkov wrote:> I tried and it looks really nice. One question about performance: > there are 3 calls of the same function on every completion candidate: > twice it's called with the nil arg, and one call with the 'transform' arg: Thanks, I am glad you like the UI. >> +(defun minibuffer--group-by (fun elems) >> + (let* ((key (funcall fun cand nil)) > >> @@ -1780,6 +1829,12 @@ completion--insert-strings >> + (let ((title (funcall group-fun (if (consp str) (car str) str) nil))) > >> @@ -1825,8 +1880,15 @@ completion--insert-strings >> + (funcall group-fun str 'transform) > >> @@ -2098,15 +2171,22 @@ minibuffer-completion-help >> + (minibuffer--group-by group-fun completions))) > > My concern is how fast it will work on a large list of candidate strings? The current implementation already focuses quite a bit on efficiency since I am using it in my continuously updating vertical UI (Vertico). The function `minibuffer--group-by` is linear time and significantly faster than the sorting which comes before it. It is crucial that the group function does not allocate when called with transform=nil, otherwise `minibuffer--group-by` would lead to a slowdown. Then the calls to the group function with transform/=nil are allowed to be more costly, since they only occur for the candidates which are displayed by the UI. These calls will then not matter in comparison to the other costs of displaying the candidates. > Would it be possible to optimize it to call the group function only once > on every candidate? This might require changing the data structure, > for example, to an alist like is returned by `seq-group-by`. One could return a cons of the transformed candidate and the title, but this has the downside that you always compute/allocate the transformed candidate. It is better to perform the candidate transformation lazily only for the candidates which are actually displayed. This is similar to the computation of annotations/affixations, which are only computed lazily if the completion UI displays only a subset of the actual candidates. Dmitry, Stefan and I discussed multiple possible incarnations of such a group-function functionality (https://github.com/minad/consult/issues/283). The current solution turned out to be an efficient and simple solution. We also discussed solutions which avoided multiple function calls for every candidate, but these were more complex. Note that I am using group functions heavily in my Consult package with the design proposed here. > Another variant is to put additional text properties on candidate strings, > e.g. a text property on redundant prefix with the group title that > completion--insert-strings then could fetch from the input string. Yes, this would be possible, but it would be a less flexible design. I followed the design of the annotation/affixation-functions for this. I also like about the design that it is somehow "pluggable", you add the group-function and you can augment your completion table with grouping without having to do other adjustments to how the candidates are generated. (Note that you may still want to attach a title property to the candidates to ensure that the transform=nil call is fast and non-allocating, as I did in the xref modifications in this patch.) Daniel