Re: [hackers] [dmenu] [PATCH] Fix prefix match is treated as exact match

From: Silvan Jegen <s.jegen_AT_gmail.com>
Date: Sun, 21 Aug 2016 18:04:42 +0200

Hi

On Sun, Aug 21, 2016 at 01:35:34PM +0200, Hiltjo Posthuma wrote:
> On Sat, Aug 20, 2016 at 11:26:50PM +0200, David Dufberg Tøttrup wrote:
> >
> > From 10e65f4f8c1016ce90d6e0d159c78ca642d4bba3 Mon Sep 17 00:00:00 2001
> > From: =?UTF-8?q?David=20Dufberg=20T=C3=B8ttrup?= <david_AT_dufberg.se>
> > Date: Sat, 20 Aug 2016 16:20:19 +0200
> > Subject: [PATCH] Fix prefix match is treated as exact match
> >
> > Input text and items are only compared up to length of input but should be
> > compared against the full length of the item.
> > ---
> > dmenu.c | 7 ++++---
> > 1 file changed, 4 insertions(+), 3 deletions(-)
> >
> > diff --git a/dmenu.c b/dmenu.c
> > index 3b05752..ad3a2f1 100644
> > --- a/dmenu.c
> > +++ b/dmenu.c
> > _AT_@ -198,7 +198,7 @@ match(void)
> >
> > char buf[sizeof text], *s;
> > int i, tokc = 0;
> > - size_t len, textsize;
> > + size_t len, itemlen;
> > struct item *item, *lprefix, *lsubstr, *prefixend, *substrend;
> >
> > strcpy(buf, text);
> > _AT_@ -209,15 +209,16 @@ match(void)
> > len = tokc ? strlen(tokv[0]) : 0;
> >
> > matches = lprefix = lsubstr = matchend = prefixend = substrend = NULL;
> > - textsize = strlen(text);
> > for (item = items; item && item->text; item++) {
> > for (i = 0; i < tokc; i++)
> > if (!fstrstr(item->text, tokv[i]))
> > break;
> > if (i != tokc) /* not all tokens match */
> > continue;
> > +
> > + itemlen = strlen(item->text);
> > /* exact matches go first, then prefixes, then substrings */
> > - if (!tokc || !fstrncmp(text, item->text, textsize))
> > + if (!tokc || !fstrncmp(text, item->text, itemlen))
> > appenditem(item, &matches, &matchend);
> > else if (!fstrncmp(tokv[0], item->text, len))
> > appenditem(item, &lprefix, &prefixend);
> > --
> > 2.7.4
> >
> >
>
> Hi,
>
> This patch breaks prefix matching on multiple tokens, see also thread:
>
> "Fix incorrect ordering of matching results" on hackers_AT_ by Davide Del Zompo
> posted on 2015-08-14.

Just for reference, Davide's patch looked like this.

> commit acbf35a5e35b6f6a7dd3f8da49a6e5ec5ac075ce
> Author: Davide Del Zompo <davide.delzompo_AT_gmail.com>
> AuthorDate: Sun Oct 4 14:01:22 2015 +0200
> Commit: Hiltjo Posthuma <hiltjo_AT_codemadness.org>
> CommitDate: Sun Oct 4 14:03:07 2015 +0200
>
> fix incorrect ordering of match results
>
> look for exact matches comparing the user input against the item text
>
> diff --git a/dmenu.c b/dmenu.c
> index 509e566..c9fb38b 100644
> --- a/dmenu.c
> +++ b/dmenu.c
> _AT_@ -208,7 +208,7 @@ match(void)
>
> char buf[sizeof text], *s;
> int i, tokc = 0;
> - size_t len;
> + size_t len, textsize;
> struct item *item, *lprefix, *lsubstr, *prefixend, *substrend;
>
> strcpy(buf, text);
> _AT_@ -219,6 +219,7 @@ match(void)
> len = tokc ? strlen(tokv[0]) : 0;
>
> matches = lprefix = lsubstr = matchend = prefixend = substrend = NULL;
> + textsize = strlen(text) + 1;
> for (item = items; item && item->text; item++) {
> for (i = 0; i < tokc; i++)
> if (!fstrstr(item->text, tokv[i]))
> _AT_@ -226,7 +227,7 @@ match(void)
> if (i != tokc) /* not all tokens match */
> continue;
> /* exact matches go first, then prefixes, then substrings */
> - if (!tokc || !fstrncmp(tokv[0], item->text, len + 1))
> + if (!tokc || !fstrncmp(text, item->text, textsize))
> appenditem(item, &matches, &matchend);
> else if (!fstrncmp(tokv[0], item->text, len))
> appenditem(item, &lprefix, &prefixend);
--------

 

> It seems the matching has not worked as advertised in a while (since 2011). It
> matched only the prefix text of the first token.
>
> The way I interpret the comment it should match the text in this order:
> 1. Exact: compare input text against the whole line.
> 2. Prefix: compare input text as prefix against the whole line.
> 3. Token match (strstr check is done before).
>
> Then a question arides: should it also give precedence to a token matching as
> prefix on a string? For example "su le" should give the results:
>
> [ "suck less", "less suck" ] or
> [ "less suck", "suck less" ] (original order)

Having partial (==token-wise) substring matching is desirable in my
opinion because it can save a lot of key strokes. Also, if we have an
input list like this.

suckless
suck
less sucky
sucky less

Typing "suck" should give you the exact match first. If you want to get
both the partial substring matching and the exact match it is enough
to apply this patch.

diff --git a/dmenu.c b/dmenu.c
index 3b05752..8f67415 100644
--- a/dmenu.c
+++ b/dmenu.c
_AT_@ -217,7 +217,7 @@ match(void)
                 if (i != tokc) /* not all tokens match */
                         continue;
                 /* exact matches go first, then prefixes, then substrings */
- if (!tokc || !fstrncmp(text, item->text, textsize))
+ if (!tokc || !fstrncmp(text, item->text, textsize + 1))
                         appenditem(item, &matches, &matchend);
                 else if (!fstrncmp(tokv[0], item->text, len))
                         appenditem(item, &lprefix, &prefixend);


Are there other opinions (ideally accompanied by patches) on the preferred
ordering of matches?


Cheers,

Silvan

 
> Below is a patch which handles matching as described above except the token
> prefix case:
>
> diff --git a/dmenu.c b/dmenu.c
> index 3b05752..b1879b9 100644
> --- a/dmenu.c
> +++ b/dmenu.c
> _AT_@ -217,9 +217,9 @@ match(void)
> if (i != tokc) /* not all tokens match */
> continue;
> /* exact matches go first, then prefixes, then substrings */
> - if (!tokc || !fstrncmp(text, item->text, textsize))
> + if (!tokc || !fstrncmp(text, item->text, textsize + 1))
> appenditem(item, &matches, &matchend);
> - else if (!fstrncmp(tokv[0], item->text, len))
> + else if (!fstrncmp(text, item->text, textsize))
> appenditem(item, &lprefix, &prefixend);
> else
> appenditem(item, &lsubstr, &substrend);
>
>
> Testing and feedback would be very much appreciated!
>
> --
> Kind regards,
> Hiltjo
>
Received on Sun Aug 21 2016 - 18:04:42 CEST