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: Thu, 15 Oct 2020 16:25:08 +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="15985"; 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, Stefan Monnier To: =?UTF-8?Q?Jo=C3=A3o_?= =?UTF-8?Q?T=C3=A1vora?= Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Thu Oct 15 16:26:14 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 1kT4Cq-0003zu-Ma for geb-bug-gnu-emacs@m.gmane-mx.org; Thu, 15 Oct 2020 16:26:12 +0200 Original-Received: from localhost ([::1]:52440 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1kT4Cp-00059q-Ox for geb-bug-gnu-emacs@m.gmane-mx.org; Thu, 15 Oct 2020 10:26:11 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:35784) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kT4Ch-00059G-JZ for bug-gnu-emacs@gnu.org; Thu, 15 Oct 2020 10:26:03 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:44595) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1kT4Cf-0006fY-T5 for bug-gnu-emacs@gnu.org; Thu, 15 Oct 2020 10:26:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1kT4Cf-0007eu-Pk for bug-gnu-emacs@gnu.org; Thu, 15 Oct 2020 10:26:01 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Dario Gjorgjevski Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Thu, 15 Oct 2020 14:26:01 +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.160277191929361 (code B ref 42149); Thu, 15 Oct 2020 14:26:01 +0000 Original-Received: (at 42149) by debbugs.gnu.org; 15 Oct 2020 14:25:19 +0000 Original-Received: from localhost ([127.0.0.1]:56141 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1kT4By-0007dU-Uf for submit@debbugs.gnu.org; Thu, 15 Oct 2020 10:25:19 -0400 Original-Received: from mail-ed1-f41.google.com ([209.85.208.41]:39903) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1kT4Bx-0007dD-2o for 42149@debbugs.gnu.org; Thu, 15 Oct 2020 10:25:17 -0400 Original-Received: by mail-ed1-f41.google.com with SMTP id t21so3293461eds.6 for <42149@debbugs.gnu.org>; Thu, 15 Oct 2020 07:25:17 -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=iATF0ADaNr+N1YgWVZumKdQ+jA/QmwfUIKIoA4eOYJc=; b=br+TuSD0qfacyMCkFBLZvY0NENKatyf2e3TW2+bsKOrMuquj1vScHnT2pljLOCSQeM jTIylr7V23MSKdN8CBJ1QtljrR5DukiND+lZvHmvpZK8fA8Z1KeNquIw/D9w0dbRZfep BECGa+w8p+CzcSZ8xmYg7ma1h5GCrakGEhA9a6Q4MaDVQ5sSJrM/qHzoHDrkFleq07k/ M8QVsVQ8MkLE4djII3tfP53zH05BNwrLIa5gXMOUmp2bTUqpNhpWrTK0aMuCjQASE+Bi CYJwm4bmGWdezpN3UPojp4zSL4AdWtWwmsr5e6dG2XZiXW+7uBCojrjdvTKEoXvtGUCC inGw== 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=iATF0ADaNr+N1YgWVZumKdQ+jA/QmwfUIKIoA4eOYJc=; b=OMKePTVRHVb0ZmaFEb/7BVGMEJNczc97HlEvY4YK7SE51nMvJBCJhQiomgG3lV6GUN 6bXBLiR1y2ZanzryhVUE5oYw3SklI9k11XVyBibe37K+qdWrhYUXdk+2dbAJ7sJw6P3D VT9xN8nOe+7qNLTRYnMpI73ox+iXDIIbaX6TgMCEhusCicoQjLgNplprS8KbCNMv29rB 6UVO9xQIwqje1YdteMbOwdvoA4fpG7oHag7+LytEOitgpDViHBVae0+RoPQhXCuBCtsu c6qp3yYNu5fjL3nvA/ILLoI2NRnR6LVTePKKNArQNA4wEO81MYJGW/bM3T4CewGOE13k zPTA== X-Gm-Message-State: AOAM5307JVAwcrzR+JHsKBKyipaQZLdHhyyo7Eot3+l9JK+xr9XLk90s ps/NAkSQa+9bqVP32L7SLwq9ltMvA/znng== X-Google-Smtp-Source: ABdhPJyLOUrE1wrQb5a/xeYdlHgo6uxwXCNpDUkFTq4LPUL/SJir94AqwdqXHlxlln8VpWkFnvPrrg== X-Received: by 2002:aa7:d781:: with SMTP id s1mr4811949edq.102.1602771910930; Thu, 15 Oct 2020 07:25:10 -0700 (PDT) Original-Received: from ZALANDO-31298 ([79.140.121.18]) by smtp.gmail.com with ESMTPSA id i4sm1697949ejz.62.2020.10.15.07.25.09 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Thu, 15 Oct 2020 07:25:09 -0700 (PDT) In-Reply-To: (Dario Gjorgjevski's message of "Wed, 14 Oct 2020 11:01:51 +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:190585 Archived-At: --=-=-= Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Hi Jo=C3=A3o, hi Stefan, Please find attached a patch with an edited commit message. It should be better. --=-=-= Content-Type: text/x-diff; charset=utf-8 Content-Disposition: attachment; filename=0001-Fix-PCM-scoring-ignoring-last-part-of-query-string.patch Content-Transfer-Encoding: quoted-printable Content-Description: Fix PCM scoring ignoring last part of query string >From 59c4b64e830bef4258dba06e77e674f33b603918 Mon Sep 17 00:00:00 2001 From: Dario Gjorgjevski Date: Wed, 14 Oct 2020 10:06:40 +0200 Subject: [PATCH] Fix PCM scoring ignoring last part of query string MIME-Version: 1.0 Content-Type: text/plain; charset=3DUTF-8 Content-Transfer-Encoding: 8bit This issue is especially evident for single-character query strings, e.g., (completion-flex-all-completions "1" '("1" "foo1") nil 1) would match both "1" and "foo1" with a completion score of 0, whereas they should have completion scores of 1 and 0.25 respectively. See also bug#42149. Furthermore, =E2=80=98completions-first-difference=E2=80=99 and =E2=80=98completions-common-part=E2=80=99 would sometimes overlap depending= on the position of point within the query string. The former is fixed by correcting the part of =E2=80=98completion-pcm--hilit-commonality=E2=80=99 responsible for looping= over the holes in the query string. The latter is fixed by explicitly moving the position of =E2=80=98completions-first-difference=E2=80=99 in case an o= verlap with =E2=80=98completions-common-part=E2=80=99 is detected. * lisp/minibuffer.el (completion-pcm--hilit-commonality): Correctly loop over the holes in the query string; detect overlaps of =E2=80=98completions-first-difference=E2=80=99 with =E2=80=98completions-co= mmon-part=E2=80=99; pre-compute the numerator. (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' --=-=-=--