From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: =?UTF-8?Q?Jo=C3=A3o_?= =?UTF-8?Q?T=C3=A1vora?= Newsgroups: gmane.emacs.bugs Subject: bug#47711: bug#48841: bug#47711: bug#48841: bug#47711: [PATCH VERSION 2] Add new `completion-filter-completions` API and deferred highlighting Date: Thu, 26 Oct 2023 22:49:07 +0100 Message-ID: <87zg05awbw.fsf@gmail.com> References: <3d3f894f-a6fa-53ae-5d50-c3aa9bffc73e@daniel-mendler.de> <56ab18b1-4348-9b2c-85bb-af9b76cd429a@daniel-mendler.de> <328f87eb-6474-1442-e1ca-9ae8deb2a84a@yandex.ru> <83fsvcbio7.fsf@gnu.org> <9f432d18-e70f-54c1-0173-1899fb66d176@gutov.dev> <877cnafv39.fsf@gmail.com> <8734xy73n7.fsf@gmail.com> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="9092"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Cc: Dmitry Gutov , Eli Zaretskii , 47711@debbugs.gnu.org, Daniel Mendler To: Stefan Monnier Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Thu Oct 26 23:46:47 2023 Return-path: Envelope-to: geb-bug-gnu-emacs@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 1qw8Bi-0002Ci-Ii for geb-bug-gnu-emacs@m.gmane-mx.org; Thu, 26 Oct 2023 23:46:46 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1qw8BU-0006vf-JL; Thu, 26 Oct 2023 17:46:32 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1qw8BT-0006vU-8X for bug-gnu-emacs@gnu.org; Thu, 26 Oct 2023 17:46:31 -0400 Original-Received: from debbugs.gnu.org ([2001:470:142:5::43]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1qw8BT-0000rk-0V for bug-gnu-emacs@gnu.org; Thu, 26 Oct 2023 17:46:31 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1qw8Bx-0007Xj-V8 for bug-gnu-emacs@gnu.org; Thu, 26 Oct 2023 17:47:01 -0400 X-Loop: help-debbugs@gnu.org Resent-From: =?UTF-8?Q?Jo=C3=A3o_?= =?UTF-8?Q?T=C3=A1vora?= Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Thu, 26 Oct 2023 21:47:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 47711 X-GNU-PR-Package: emacs Original-Received: via spool by 47711-submit@debbugs.gnu.org id=B47711.169835680928974 (code B ref 47711); Thu, 26 Oct 2023 21:47:01 +0000 Original-Received: (at 47711) by debbugs.gnu.org; 26 Oct 2023 21:46:49 +0000 Original-Received: from localhost ([127.0.0.1]:34645 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1qw8Bk-0007XF-0A for submit@debbugs.gnu.org; Thu, 26 Oct 2023 17:46:48 -0400 Original-Received: from mail-wr1-x434.google.com ([2a00:1450:4864:20::434]:58455) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1qw8Bh-0007Wz-M5 for 47711@debbugs.gnu.org; Thu, 26 Oct 2023 17:46:46 -0400 Original-Received: by mail-wr1-x434.google.com with SMTP id ffacd0b85a97d-307d58b3efbso900758f8f.0 for <47711@debbugs.gnu.org>; Thu, 26 Oct 2023 14:46:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1698356768; x=1698961568; darn=debbugs.gnu.org; h=mime-version:user-agent:message-id:date:references:in-reply-to :subject:cc:to:from:from:to:cc:subject:date:message-id:reply-to; bh=sZT+TP0Tt9zQl4/Sj82+ly5Zcv1s+BsVANc11Ug75XQ=; b=bgAjaPk1rFU4c6+tVz4A0w88hA51KeRa8cgS17hWiWjzf/5jQ8MPbOoTwseWa0GVHc Kf8xzlFwBxqYxC0eSRgjcp6bmk0dsnW3LZtJo3bMD8bLW34fd8YIh4vJ+qzN4/UCert+ JXlJoT1uvJxZ73cu7b/2NtdUkzEBwXMJDd2ct+rJV72j+a4Xujlj0AR1RTj7iD71ieJR nDMoJlvveTWTIMK7cnHLXaJD1N/AtxY01UKxrLRfv/AX9iLJu3w8UXN2NODBQYijl35B 2mWmxzUcgzI4Zfw6sEgoEPk4KA+YJgF3QMQ8avLu8j2zpJVHYFTsxxE/4amMpofs0I3V lHqQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698356768; x=1698961568; h=mime-version:user-agent:message-id:date:references:in-reply-to :subject:cc:to:from:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=sZT+TP0Tt9zQl4/Sj82+ly5Zcv1s+BsVANc11Ug75XQ=; b=v+tQ31N9OkQILwDbilwZ6ZDwRnrYJHwEPSf1HcQCrUBl+nhnd7ERbFVynngXqcih4d X7O7atFGHinPIxJRyDree05Zj6OoyVqoy4lcvyqmJXZrrm30g4/2uwsdwetxyQ3NBWK0 Ekf866ffT5R+1TYMjoQmUgJY8E9Iahjq/jaDc+IY9OAlW8hh+Y+s14OLAypt1W7cjw7x iJVBGpYwrpXDAPthZ1F7FF8xlnEHY9Rn6KucVHAvki6HVVZBjbBrY3pY8WiAAGriQ5K2 mSx2GAzKMEXr0IhrMFFk2IRrnwTZOrjnZPYkVDKLv8i59sHe5VJtz5pDR+q00JF+FW5f gFWg== X-Gm-Message-State: AOJu0YxD907jLUo7WiOJxcTaLVkIZeIxnLsn4RJocl7J4yi3GzubgyHg 7kTjFqNqZrk2wjSZVK4mwHzuKkBMtUpxUA== X-Google-Smtp-Source: AGHT+IGf+DhENhVd1Rfcqxsvq6+v0+gbKKRHuNF3zAgvvT7Yo+oZFqillvzPEuLfxoR4eGgb1MSvzQ== X-Received: by 2002:a5d:4fc9:0:b0:31f:9b4f:1910 with SMTP id h9-20020a5d4fc9000000b0031f9b4f1910mr626685wrw.63.1698356768099; Thu, 26 Oct 2023 14:46:08 -0700 (PDT) Original-Received: from krug (87-196-80-249.net.novis.pt. [87.196.80.249]) by smtp.gmail.com with ESMTPSA id g4-20020a5d46c4000000b0032d72f48555sm312973wrs.36.2023.10.26.14.46.06 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 26 Oct 2023 14:46:07 -0700 (PDT) In-Reply-To: <8734xy73n7.fsf@gmail.com> ("=?UTF-8?Q?Jo=C3=A3o_?= =?UTF-8?Q?T=C3=A1vora?="'s message of "Wed, 25 Oct 2023 23:12:28 +0100") X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.bugs:273321 Archived-At: --=-=-= Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Jo=C3=A3o T=C3=A1vora writes: > So, backed by the new ability to conduct good benchmarks, I looked at > the problem anew. I found some insight in the problem, and came up with > a new "lazy-hilit" patch which performs just as well, if not slightly > better, than Daniel's, while keeping the changes to lisp/minibuffer.el > much more minimal and not adding replacement for the longstanding > completion-all-completions. Working on this a bit more, I've now been able to optimize the "lazy hilit" patch even further by recognizing that in many situations we don't need to match the "PCM" pattern to each string twice. The first time we do it, we can calculate a score immediately and store it in the string. The average response times for the "yo-yoo" test described previously: master: 2.604s 2021 lazy-hilit patch: 1.240s 2023 Daniel+Dmitry: 0.831s 2023 lazy-hilit v1: 0.792s And the new one: 2023 lazy-hilit v2: 0.518s I'm now keeping my work in a branch called feature/completion-lazy-hilit, but I still attach the diff here. Jo=C3=A3o PS: for the flex style in particular, there are even more optimizations possible. For example one could take advantage of the fact that in flex, a longer pattern should always yield a subset of the completions produced by a shorter pattern in the same completion session. But this requires solid concepts of a "completion session". --=-=-= Content-Type: text/x-patch Content-Disposition: inline; filename=lazy-hilit-2023-v2.diff diff --git a/lisp/icomplete.el b/lisp/icomplete.el index e6fdd1f1836..3e888c8b06a 100644 --- a/lisp/icomplete.el +++ b/lisp/icomplete.el @@ -722,7 +722,8 @@ icomplete-exhibit ;; Check if still in the right buffer (bug#61308) (or (window-minibuffer-p) completion-in-region--data) (icomplete-simple-completing-p)) ;Shouldn't be necessary. - (let ((saved-point (point))) + (let ((saved-point (point)) + (completion-lazy-hilit t)) (save-excursion (goto-char (icomplete--field-end)) ;; Insert the match-status information: @@ -754,12 +755,13 @@ icomplete-exhibit (overlay-end rfn-eshadow-overlay))) (let* ((field-string (icomplete--field-string)) (text (while-no-input + (benchmark-progn (icomplete-completions field-string (icomplete--completion-table) (icomplete--completion-predicate) (if (window-minibuffer-p) - (eq minibuffer--require-match t))))) + (eq minibuffer--require-match t)))))) (buffer-undo-list t) deactivate-mark) ;; Do nothing if while-no-input was aborted. @@ -901,7 +903,7 @@ icomplete--render-vertical 'icomplete-selected-match 'append comp) collect (concat prefix (make-string (- max-prefix-len (length prefix)) ? ) - comp + (completion-lazy-hilit comp) (make-string (- max-comp-len (length comp)) ? ) suffix) into lines-aux @@ -1067,7 +1069,8 @@ icomplete-completions (if (< prospects-len prospects-max) (push comp prospects) (setq limit t))) - (setq prospects (nreverse prospects)) + (setq prospects + (nreverse (mapcar #'completion-lazy-hilit prospects))) ;; Decorate first of the prospects. (when prospects (let ((first (copy-sequence (pop prospects)))) diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el index 2120e31775e..b38eb49aba8 100644 --- a/lisp/minibuffer.el +++ b/lisp/minibuffer.el @@ -1234,6 +1234,7 @@ completion-all-completions POINT is the position of point within STRING. The return value is a list of completions and may contain the base-size in the last `cdr'." + (setq completion-lazy-hilit-fn nil) ;; FIXME: We need to additionally return the info needed for the ;; second part of completion-base-position. (completion--nth-completion 2 string table pred point metadata)) @@ -3720,21 +3721,33 @@ completion-pcm--all-completions ;; Use all-completions to do an initial cull. This is a big win, ;; since all-completions is written in C! - (let* (;; Convert search pattern to a standard regular expression. - (regex (completion-pcm--pattern->regex pattern)) - (case-fold-search completion-ignore-case) - (completion-regexp-list (cons regex completion-regexp-list)) - (compl (all-completions - (concat prefix - (if (stringp (car pattern)) (car pattern) "")) - table pred))) - (if (not (functionp table)) - ;; The internal functions already obeyed completion-regexp-list. - compl - (let ((poss ())) - (dolist (c compl) - (when (string-match-p regex c) (push c poss))) - (nreverse poss)))))) + (let* ((case-fold-search completion-ignore-case) + (completion-regexp-list (cons + ;; Convert search pattern to a + ;; standard regular expression. + (completion-pcm--pattern->regex pattern) + completion-regexp-list)) + (completions (all-completions + (concat prefix + (if (stringp (car pattern)) (car pattern) "")) + table pred))) + (cond ((or (not (functionp table)) + (cl-loop for e in pattern never (stringp e))) + ;; The internal functions already obeyed completion-regexp-list. + completions) + (t + ;; The pattern has something interesting to match, in + ;; which case we take the opportunity to add an early + ;; completion-score cookie to each completion. + (cl-loop with re = (completion-pcm--pattern->regex pattern 'group) + for orig in completions + for comp = (copy-sequence orig) + for score = (completion--flex-score comp re t) + when score + do (put-text-property 0 1 'completion-score + score + comp) + and collect comp)))))) (defvar flex-score-match-tightness 3 "Controls how the `flex' completion style scores its matches. @@ -3749,108 +3762,195 @@ flex-score-match-tightness than the latter (which has two \"holes\" and three one-letter-long matches).") +(defvar-local completion-lazy-hilit nil + "If non-nil, request completion lazy highlighting. + +Completion-presenting frontends may opt to bind this variable to +non-nil value in the context of completion-producing calls (such +as `completion-all-sorted-completions'). This hints the +intervening completion styles that they do not need to +fontify (i.e. propertize with the `face' property) completion +strings with highlights of the matching parts. + +When doing so, it is the frontend -- not the style -- who becomes +responsible this fontification. The frontend binds this variable +to non-nil, and calls the function with the same name +`completion-lazy-hilit' on each completion string that is to be +displayed to the user. + +Note that only some completion styles take advantage of this +variable for optimization purposes. Other styles will ignore the +hint and greedily fontify as usual. It is still safe for a +frontend to call `completion-lazy-hilit' in these situations. + +To author a completion style that takes advantage see +`completion-lazy-hilit-fn' and look in the source of +`completion-pcm--hilit-commonality'.") + +(defvar completion-lazy-hilit-fn nil + "Used by completions styles to honouring `completion-lazy-hilit'. +When a given style wants to enable support for +`completion-lazy-hilit' (which see), that style should set this +variable to a function of one argument, a fresh string to be +displayed to the user. The function is responsible for +destructively highlighting the string.") + +(defun completion-lazy-hilit (str) + "Return a copy of completion STR that is `face'-propertized. +See documentation for variable `completion-lazy-hilit' for more +details." + (if (and completion-lazy-hilit completion-lazy-hilit-fn) + (funcall completion-lazy-hilit-fn (copy-sequence str)) + str)) + +(defun completion--hilit-from-re (string regexp) + "Fontify STRING with `completions-common-part' using REGEXP." + (let* ((md (and regexp (string-match regexp string) (cddr (match-data t)))) + (me (and md (match-end 0))) + (from 0)) + (while md + (add-face-text-property from (pop md) 'completions-common-part nil string) + (setq from (pop md))) + (unless (or (not me) (= from me)) + (add-face-text-property from me 'completions-common-part nil string)) + string)) + +(defun completion--flex-score-1 (md-groups match-end len) + "Compute matching score of completion. +The score lies in the range between 0 and 1, where 1 corresponds to +the full match. +MD-GROUPS is the \"group\" part of the match data. +MATCH-END is the end of the match. +LEN is the length of the completion string." + (let* ((from 0) + ;; To understand how this works, consider these simple + ;; ascii diagrams showing how the pattern "foo" + ;; flex-matches "fabrobazo", "fbarbazoo" and + ;; "barfoobaz": + + ;; f abr o baz o + ;; + --- + --- + + + ;; f barbaz oo + ;; + ------ ++ + + ;; bar foo baz + ;; +++ + + ;; "+" indicates parts where the pattern matched. A + ;; "hole" in the middle of the string is indicated by + ;; "-". Note that there are no "holes" near the edges + ;; of the string. The completion score is a number + ;; bound by (0..1] (i.e., larger than (but not equal + ;; to) zero, and smaller or equal to one): the higher + ;; the better and only a perfect match (pattern equals + ;; string) will have score 1. The formula takes the + ;; form of a quotient. For the numerator, we use the + ;; number of +, i.e. the length of the pattern. For + ;; the denominator, it first computes + ;; + ;; hole_i_contrib = 1 + (Li-1)^(1/tightness) + ;; + ;; , for each hole "i" of length "Li", where tightness + ;; is given by `flex-score-match-tightness'. The + ;; final value for the denominator is then given by: + ;; + ;; (SUM_across_i(hole_i_contrib) + 1) * len + ;; + ;; , where "len" is the string's length. + (score-numerator 0) + (score-denominator 0) + (last-b 0)) + (while (and md-groups (car md-groups)) + (let ((a from) + (b (pop md-groups))) + (setq + score-numerator (+ score-numerator (- b a))) + (unless (or (= a last-b) + (zerop last-b) + (= a len)) + (setq + score-denominator (+ score-denominator + 1 + (expt (- a last-b 1) + (/ 1.0 + flex-score-match-tightness))))) + (setq + last-b b)) + (setq from (pop md-groups))) + ;; If `pattern' doesn't have an explicit trailing any, the + ;; regex `re' won't produce match data representing the + ;; region after the match. We need to account to account + ;; for that extra bit of match (bug#42149). + (unless (= from match-end) + (let ((a from) + (b match-end)) + (setq + score-numerator (+ score-numerator (- b a))) + (unless (or (= a last-b) + (zerop last-b) + (= a len)) + (setq + score-denominator (+ score-denominator + 1 + (expt (- a last-b 1) + (/ 1.0 + flex-score-match-tightness))))) + (setq + last-b b))) + (/ score-numerator (* len (1+ score-denominator)) 1.0))) + +(defvar completion--flex-score-last-md nil + "Helper variable for `completion--flex-score'.") + +(defun completion--flex-score (str re &optional dont-error) + "Compute flex score of completion STR based on RE. +If DONT-ERROR, just return nil if RE doesn't match STR." + (cond ((string-match re str) + (let* ((match-end (match-end 0)) + (md (cddr + (setq + completion--flex-score-last-md + (match-data t completion--flex-score-last-md))))) + (completion--flex-score-1 md match-end (length str)))) + ((not dont-error) + (error "Internal error: %s does not match %s" re str)))) + (defun completion-pcm--hilit-commonality (pattern completions) "Show where and how well PATTERN matches COMPLETIONS. PATTERN, a list of symbols and strings as seen `completion-pcm--merge-completions', is assumed to match every -string in COMPLETIONS. Return a deep copy of COMPLETIONS where -each string is propertized with `completion-score', a number -between 0 and 1, and with faces `completions-common-part', -`completions-first-difference' in the relevant segments." +string in COMPLETIONS. + +If `completion-lazy-hilit' is nil, return a deep copy of +COMPLETIONS where each string is propertized with +`completion-score', a number between 0 and 1, and with faces +`completions-common-part', `completions-first-difference' in the +relevant segments. + +Else, if `completion-lazy-hilit' is t, return COMPLETIONS where +each string now has a `completion-score' property and no +highlighting." (cond ((and completions (cl-loop for e in pattern thereis (stringp e))) (let* ((re (completion-pcm--pattern->regex pattern 'group)) - (point-idx (completion-pcm--pattern-point-idx pattern)) - (case-fold-search completion-ignore-case) - last-md) - (mapcar - (lambda (str) - ;; Don't modify the string itself. - (setq str (copy-sequence str)) - (unless (string-match re str) - (error "Internal error: %s does not match %s" re str)) - (let* ((pos (if point-idx (match-beginning point-idx) (match-end 0))) - (match-end (match-end 0)) - (md (cddr (setq last-md (match-data t last-md)))) - (from 0) - (end (length str)) - ;; To understand how this works, consider these simple - ;; ascii diagrams showing how the pattern "foo" - ;; flex-matches "fabrobazo", "fbarbazoo" and - ;; "barfoobaz": - - ;; f abr o baz o - ;; + --- + --- + - - ;; f barbaz oo - ;; + ------ ++ - - ;; bar foo baz - ;; +++ - - ;; "+" indicates parts where the pattern matched. A - ;; "hole" in the middle of the string is indicated by - ;; "-". Note that there are no "holes" near the edges - ;; of the string. The completion score is a number - ;; bound by (0..1] (i.e., larger than (but not equal - ;; to) zero, and smaller or equal to one): the higher - ;; the better and only a perfect match (pattern equals - ;; string) will have score 1. The formula takes the - ;; form of a quotient. For the numerator, we use the - ;; number of +, i.e. the length of the pattern. For - ;; the denominator, it first computes - ;; - ;; hole_i_contrib = 1 + (Li-1)^(1/tightness) - ;; - ;; , for each hole "i" of length "Li", where tightness - ;; is given by `flex-score-match-tightness'. The - ;; final value for the denominator is then given by: - ;; - ;; (SUM_across_i(hole_i_contrib) + 1) * len - ;; - ;; , where "len" is the string's length. - (score-numerator 0) - (score-denominator 0) - (last-b 0) - (update-score-and-face - (lambda (a b) - "Update score and face given match range (A B)." - (add-face-text-property a b - 'completions-common-part - nil str) - (setq - score-numerator (+ score-numerator (- b a))) - (unless (or (= a last-b) - (zerop last-b) - (= a (length str))) - (setq - score-denominator (+ score-denominator - 1 - (expt (- a last-b 1) - (/ 1.0 - flex-score-match-tightness))))) - (setq - last-b b)))) - (while md - (funcall update-score-and-face from (pop md)) - (setq from (pop md))) - ;; If `pattern' doesn't have an explicit trailing any, the - ;; regex `re' won't produce match data representing the - ;; region after the match. We need to account to account - ;; for that extra bit of match (bug#42149). - (unless (= from match-end) - (funcall update-score-and-face from match-end)) - (if (> (length str) pos) - (add-face-text-property - pos (1+ pos) - 'completions-first-difference - nil str)) - (unless (zerop (length str)) - (put-text-property - 0 1 'completion-score - (/ score-numerator (* end (1+ score-denominator)) 1.0) str))) - str) - completions))) + (score-maybe (lambda (str) + (unless (get-text-property 0 'completion-score str) + (put-text-property 0 1 'completion-score + (completion--flex-score str re) + str))))) + (cond (completion-lazy-hilit + (setq completion-lazy-hilit-fn + (lambda (str) (completion--hilit-from-re str re))) + (mapc score-maybe completions)) + (t + (mapcar + (lambda (str) + (setq str (copy-sequence str)) + (funcall score-maybe str) + (completion--hilit-from-re str re) + str) + completions))))) (t completions))) (defun completion-pcm--find-all-completions (string table pred point --=-=-=--