From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Dario Gjorgjevski Newsgroups: gmane.emacs.bugs Subject: bug#42149: Substring and flex completion ignore implicit trailing =?UTF-8?Q?=E2=80=98any=E2=80=99?= Date: Wed, 14 Oct 2020 10:22:09 +0200 Message-ID: References: <87k0znsdjb.fsf@gmail.com> <87sgbsv7gg.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="29106"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux) Cc: 42149@debbugs.gnu.org, =?UTF-8?Q?Jo=C3=A3o_?= =?UTF-8?Q?T=C3=A1vora?= To: Stefan Monnier Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Wed Oct 14 10:28:59 2020 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 1kSc9a-0007PF-De for geb-bug-gnu-emacs@m.gmane-mx.org; Wed, 14 Oct 2020 10:28:58 +0200 Original-Received: from localhost ([::1]:43224 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1kSc9Y-0001YH-BD for geb-bug-gnu-emacs@m.gmane-mx.org; Wed, 14 Oct 2020 04:28:56 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:33120) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kSc3q-0001FK-NU for bug-gnu-emacs@gnu.org; Wed, 14 Oct 2020 04:23:04 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:38456) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1kSc3q-0007gH-Dd for bug-gnu-emacs@gnu.org; Wed, 14 Oct 2020 04:23:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1kSc3q-0005jS-8E for bug-gnu-emacs@gnu.org; Wed, 14 Oct 2020 04:23:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Dario Gjorgjevski Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Wed, 14 Oct 2020 08:23:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 42149 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch Original-Received: via spool by 42149-submit@debbugs.gnu.org id=B42149.160266374221970 (code B ref 42149); Wed, 14 Oct 2020 08:23:02 +0000 Original-Received: (at 42149) by debbugs.gnu.org; 14 Oct 2020 08:22:22 +0000 Original-Received: from localhost ([127.0.0.1]:50002 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1kSc3B-0005iH-AQ for submit@debbugs.gnu.org; Wed, 14 Oct 2020 04:22:22 -0400 Original-Received: from mail-ej1-f41.google.com ([209.85.218.41]:32998) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1kSc38-0005i3-M3 for 42149@debbugs.gnu.org; Wed, 14 Oct 2020 04:22:20 -0400 Original-Received: by mail-ej1-f41.google.com with SMTP id c22so3640250ejx.0 for <42149@debbugs.gnu.org>; Wed, 14 Oct 2020 01:22:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:references:date:in-reply-to:message-id :user-agent:mime-version; bh=BHa7UoQ8hOJrbsmjFnULLSOjNf+626kcWrG0KDPHiBY=; b=gq7+Rw3M3JsmRXKNYtB/eAjz1mwHeEsST8xy+nINP0OXHo610kvoo/K9TmsTm/q2B8 UneujoXQUgY4V2A1moOwWQBWF/PitaD3iQqbSs7iMLRBc0cV0+4HHet2u0hmImzPrA1Z VJDhsBAItMgTg5ngEKZoxLPL65QvHs1kDfXWbD471gesPULnN8u/sZHBrb53uu1F+6IX ck/gWGh5u8Xyg1Zti8W0r/zX/RuAIKaoIOpkkDeL/8JxHguTkt4zRRhxEfvviUL+gemU tBNar6ElEm/sGwBJwPb197yiuZvMM3TShmd2jufeog8g75zE0Rx8PLNBPzfXAvy//TP2 e7rA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:references:date:in-reply-to :message-id:user-agent:mime-version; bh=BHa7UoQ8hOJrbsmjFnULLSOjNf+626kcWrG0KDPHiBY=; b=CPNmI1uG3W1qilEEZQxj7eBHnNeVOSwrIFcwx3oFKklqHYjJqrHPkYdrY45mFpLQWw fVDMrdEyeyaAZUOavRHnBH3bVF8JOoMyfciEuWfdvOy4QbAbs//DV80RczTufrERVtEL Y/WMz8bzJ6eZdLwVoR4c81PsIPvwiQtbmfFtyoszq2a8oZf2hZUZo1esmoxgsk/BBZOt DbUFZNIgWWqXWsC1fPl8GFbc0oG4Dj2sOrMQL2+2KvoZ4cQoRV7dExvjE2dT23LUXHoX cyWi0xRGx8RqT7YMybxp/bPVzQd974vxG0yY58P1cZc0OnWsnsymry4ekKPvNih1kojh uP7Q== X-Gm-Message-State: AOAM531Q34oAW1yy3S99rRZL1y+j/qkGER8GxA3JqSV0WDeANQVJlgsB q1a+NZhmleGiDWAOblGtZXpuAzspohUsKg== X-Google-Smtp-Source: ABdhPJwIayxkmnL4gw+NvT/NISvNiZgOiIdW4Kmi0BeU5sz4jKWYiUAOGW9QQJPZQtMLZxjF6ivvpg== X-Received: by 2002:a17:906:f201:: with SMTP id gt1mr3858763ejb.229.1602663732330; Wed, 14 Oct 2020 01:22:12 -0700 (PDT) Original-Received: from ZALANDO-31298 ([79.140.120.73]) by smtp.gmail.com with ESMTPSA id p2sm1258186ejd.34.2020.10.14.01.22.10 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Wed, 14 Oct 2020 01:22:11 -0700 (PDT) In-Reply-To: (Dario Gjorgjevski's message of "Thu, 10 Sep 2020 13:26:31 +0200") 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" Xref: news.gmane.io gmane.emacs.bugs:190489 Archived-At: --=-=-= Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Hi Stefan, hi Jo=C3=A3o, I rebased my patch on top of the fix introduced for bug#41705 and confirmed that it does not cause a regression. Have you been able to look into it? Please let me know if you think there=E2=80=99s something mi= ssing or if I should add additional tests. I am attaching the patch below. --=-=-= Content-Type: text/x-diff; charset=utf-8 Content-Disposition: attachment; filename=0001-Fix-and-optimize-scoring-in-PCM-completion.patch Content-Transfer-Encoding: quoted-printable Content-Description: Fix (and optimize) scoring in PCM completion >From e1d07804aeb155a5ff3b6a1c410ec757269a43d3 Mon Sep 17 00:00:00 2001 From: Dario Gjorgjevski Date: Wed, 14 Oct 2020 10:06:40 +0200 Subject: [PATCH] Fix (and optimize) scoring in PCM completion MIME-Version: 1.0 Content-Type: text/plain; charset=3DUTF-8 Content-Transfer-Encoding: 8bit * lisp/minibuffer.el (completion-pcm--hilit-commonality): Fix scoring to also include the last part of the query string. This was especially evident for single-character query strings, e.g., =E2=80=98(completion-flex-all-completions "1" '("1" "foo1") nil 1)=E2=80=99= would match both "1" and "foo1" with a completion-score of 0. This adjustment makes the completion-score of "1" be 1 and of "foo1" by 0.25. Furthermore, fix =E2=80=98completions-first-difference=E2=80=99 and =E2=80=98completions-common-part=E2=80=99 sometimes overlapping. See also = bug#42149. Furthermore, some optimizations are done. (completion-pcm--optimize-pattern): Turn multiple consecutive occurrences of =E2=80=98any=E2=80=99 into just a single one. (completion-pcm--count-leading-holes): New function. (completion-pcm--match-size): New function. * test/lisp/minibuffer-tests.el (completion-pcm-all-completions-test, completion-substring-all-completions-test, completion-flex-all-completions-test): Regression tests. --- lisp/minibuffer.el | 99 +++++++++++++++----------- test/lisp/minibuffer-tests.el | 127 ++++++++++++++++++++++++++++++++++ 2 files changed, 184 insertions(+), 42 deletions(-) diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el index 427636e866..38bb4d0785 100644 --- a/lisp/minibuffer.el +++ b/lisp/minibuffer.el @@ -3110,6 +3110,7 @@ or a symbol, see `completion-pcm--merge-completions'." (while p (pcase p (`(,(or 'any 'any-delim) point . ,rest) (setq p `(point . ,rest))) + (`(any any . ,rest) (setq p `(any . ,rest))) ;; This is not just a performance improvement: it turns a ;; terminating `point' into an implicit `any', which affects ;; the final position of point (because `point' gets turned @@ -3193,21 +3194,32 @@ one large \"hole\" and a clumped-together \"oo\" ma= tch) higher than the latter (which has two \"holes\" and three one-letter-long matches).") =20 +(defun completion-pcm--count-leading-holes (pattern) + "Count the number of leading holes in PATTERN." + (length (seq-take-while #'symbolp pattern))) + +(defun completion-pcm--match-size (pattern) + "Return the match size of PATTERN." + (apply #'+ + (mapcar + (lambda (part) (if (stringp part) (length part) 0)) + pattern))) + (defun completion-pcm--hilit-commonality (pattern completions) (when completions (let* ((re (completion-pcm--pattern->regex pattern 'group)) (point-idx (completion-pcm--pattern-point-idx pattern)) - (case-fold-search completion-ignore-case)) + (case-fold-search completion-ignore-case) + (num-leading-holes (completion-pcm--count-leading-holes pattern= )) + (score-numerator (float (completion-pcm--match-size pattern)))) (mapcar (lambda (str) - ;; Don't modify the string itself. + ;; 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))) (md (match-data)) - (start (pop md)) - (end (pop md)) (len (length str)) ;; To understand how this works, consider these bad ;; ascii(tm) diagrams showing how the pattern "foo" @@ -3243,47 +3255,50 @@ one-letter-long matches).") ;; (SUM_across_i(hole_i_contrib) + 1) * len ;; ;; , where "len" is the string's length. - (score-numerator 0) + (full-match-start (pop md)) + (full-match-end (pop md)) + (match-start) (score-denominator 0) - (last-b 0) - (update-score - (lambda (a b) - "Update score variables given match range (A B)." - (setq - score-numerator (+ score-numerator (- b a))) - (unless (or (=3D a last-b) - (zerop last-b) - (=3D a (length str))) - (setq - score-denominator (+ score-denominator - 1 - (expt (- a last-b 1) - (/ 1.0 - flex-score-match-tight= ness))))) - (setq - last-b b)))) - (funcall update-score start start) + (hilit (lambda (match-start match-end) + (add-face-text-property + match-start match-end + 'completions-common-part + nil str) + ;; Maybe move `pos' away so we don not end up + ;; putting `completions-first-difference' over + ;; text that actually matches. + (when (and (>=3D pos match-start) (< pos match-en= d)) + (setq pos match-end))))) + ;; Make sure that leading holes are explicitly discarded. + ;; Trailing holes are taken care of by + ;; `completion-pcm--optimize-pattern'. + (if (zerop num-leading-holes) + (setq match-start full-match-start) + (dotimes (_ (1- (* 2 num-leading-holes))) + (pop md)) + (setq match-start (pop md))) (while md - (funcall update-score start (car md)) + (let ((hole-start (pop md)) + (hole-end (pop md))) + (funcall hilit match-start hole-start) + (unless (=3D hole-start hole-end) + (setq + score-denominator (+ score-denominator + 1 + (expt + (- hole-end hole-start 1) + (/ 1.0 flex-score-match-tightness)= )))) + (setq match-start hole-end))) + (funcall hilit match-start full-match-end) + (when (> len pos) (add-face-text-property - start (pop md) - 'completions-common-part - nil str) - (setq start (pop md))) - (funcall update-score len len) - (add-face-text-property - start end - 'completions-common-part - nil str) - (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 (* len (1+ score-denominator)) 1.0) str))) + pos (1+ pos) + 'completions-first-difference + nil str)) + (put-text-property + 0 1 + 'completion-score + (/ score-numerator (* len (1+ score-denominator))) str)) str) completions)))) =20 diff --git a/test/lisp/minibuffer-tests.el b/test/lisp/minibuffer-tests.el index 5da86f3614..a473fec441 100644 --- a/test/lisp/minibuffer-tests.el +++ b/test/lisp/minibuffer-tests.el @@ -104,5 +104,132 @@ nil (length input)) (cons output (length output))))))) =20 +(ert-deftest completion-pcm-all-completions-test () + ;; Point is at end, this does not match anything + (should (equal + (completion-pcm-all-completions + "foo" '("hello" "world" "barfoobar") nil 3) + nil)) + ;; Point is at beginning, this matches "barfoobar" + (should (equal + (car (completion-pcm-all-completions + "foo" '("hello" "world" "barfoobar") nil 0)) + "barfoobar")) + ;; Full match! + (should (eql + (get-text-property + 0 'completion-score + (car (completion-pcm-all-completions + "R" '("R" "hello") nil 1))) + 1.0)) + ;; One fourth of a match and no match due to point being at the end + (should (eql + (get-text-property + 0 'completion-score + (car (completion-pcm-all-completions + "RO" '("RaOb") nil 1))) + (/ 1.0 4.0))) + (should (equal + (completion-pcm-all-completions + "RO" '("RaOb") nil 2) + nil)) + ;; Point is at beginning, but `completions-first-difference' is + ;; moved after it + (should (equal + (get-text-property + 1 'face + (car (completion-pcm-all-completions + "f" '("few" "many") nil 0))) + 'completions-first-difference)) + ;; Wildcards and delimiters work + (should (equal + (car (completion-pcm-all-completions + "li-pac*" '("list-packages") nil 7)) + "list-packages")) + (should (equal + (car (completion-pcm-all-completions + "li-pac*" '("do-not-list-packages") nil 7)) + nil))) + +(ert-deftest completion-substring-all-completions-test () + ;; One third of a match! + (should (equal + (car (completion-substring-all-completions + "foo" '("hello" "world" "barfoobar") nil 3)) + "barfoobar")) + (should (eql + (get-text-property + 0 'completion-score + (car (completion-substring-all-completions + "foo" '("hello" "world" "barfoobar") nil 3))) + (/ 1.0 3.0))) + ;; Full match! + (should (eql + (get-text-property + 0 'completion-score + (car (completion-substring-all-completions + "R" '("R" "hello") nil 1))) + 1.0)) + ;; Substring match + (should (equal + (car (completion-substring-all-completions + "custgroup" '("customize-group") nil 4)) + "customize-group")) + (should (equal + (car (completion-substring-all-completions + "custgroup" '("customize-group") nil 5)) + nil)) + ;; `completions-first-difference' should be at the right place + (should (equal + (get-text-property + 4 'face + (car (completion-substring-all-completions + "jab" '("dabjobstabby" "many") nil 1))) + 'completions-first-difference)) + (should (equal + (get-text-property + 6 'face + (car (completion-substring-all-completions + "jab" '("dabjabstabby" "many") nil 1))) + 'completions-first-difference)) + (should (equal + (get-text-property + 6 'face + (car (completion-substring-all-completions + "jab" '("dabjabstabby" "many") nil 3))) + 'completions-first-difference))) + +(ert-deftest completion-flex-all-completions-test () + ;; Fuzzy match + (should (equal + (car (completion-flex-all-completions + "foo" '("hello" "world" "fabrobazo") nil 3)) + "fabrobazo")) + ;; Full match! + (should (eql + (get-text-property + 0 'completion-score + (car (completion-flex-all-completions + "R" '("R" "hello") nil 1))) + 1.0)) + ;; Another fuzzy match, but more of a "substring" one + (should (equal + (car (completion-flex-all-completions + "custgroup" '("customize-group-other-window") nil 4)) + "customize-group-other-window")) + ;; `completions-first-difference' should be at the right place + (should (equal + (get-text-property + 4 'face + (car (completion-flex-all-completions + "custgroup" '("customize-group-other-window") nil 4))) + 'completions-first-difference)) + (should (equal + (get-text-property + 15 'face + (car (completion-flex-all-completions + "custgroup" '("customize-group-other-window") nil 9))) + 'completions-first-difference))) + (provide 'completion-tests) ;;; completion-tests.el ends here --=20 2.17.1 --=-=-= Content-Type: text/plain Best regards, Dario -- dario.gjorgjevski@gmail.com :: +49 1525 8666837 % gpg --keyserver 'hkps://hkps.pool.sks-keyservers.net' \ \`> --recv-keys '744A4F0B4F1C9371' --=-=-=--