Wish: exact matches displayed first

Wish: exact matches displayed first

[Jean Delvare]

Hi all,

I wish a search in "make menuconfig" would return an exact match, if it
exists, first in the list. At the moment, looking for "PCI", for
example, returns several dozen entries (anything matching "PCI") and
CONFIG_PCI is far away from the top. Ideally I would expect this query
to return CONFIG_PCI first.

Thanks,
-- 
Jean Delvare
Suse L3

Re: Wish: exact matches displayed first

[Yann E. MORIN]

Jean, All,

On Mon, May 06, 2013 at 09:50:29AM +0200, Jean Delvare wrote:
> I wish a search in "make menuconfig" would return an exact match, if it
> exists, first in the list. At the moment, looking for "PCI", for
> example, returns several dozen entries (anything matching "PCI") and
> CONFIG_PCI is far away from the top. Ideally I would expect this query
> to return CONFIG_PCI first.

Indeed, this has bugged me a few times, too.
I'll see what I can do.

Regards,
Yann E. MORIN.

-- 
.-----------------.--------------------.------------------.--------------------.
|  Yann E. MORIN  | Real-Time Embedded | /"\ ASCII RIBBON | Erics' conspiracy: |
| +33 662 376 056 | Software  Designer | \ / CAMPAIGN     |  ___               |
| +33 223 225 172 `------------.-------:  X  AGAINST      |  \e/  There is no  |
| http://ymorin.is-a-geek.org/ | _/*\_ | / \ HTML MAIL    |   v   conspiracy.  |
'------------------------------^-------^------------------^--------------------'

Re: Wish: exact matches displayed first

[Yann E. MORIN]

Jean, All,

On Mon, May 06, 2013 at 12:00:07PM +0200, Yann E. MORIN wrote:
> On Mon, May 06, 2013 at 09:50:29AM +0200, Jean Delvare wrote:
> > I wish a search in "make menuconfig" would return an exact match, if it
> > exists, first in the list. At the moment, looking for "PCI", for
> > example, returns several dozen entries (anything matching "PCI") and
> > CONFIG_PCI is far away from the top. Ideally I would expect this query
> > to return CONFIG_PCI first.
> 
> Indeed, this has bugged me a few times, too.
> I'll see what I can do.

BTW, did you know that you can search using extended regular expressions?
Searching for ^PCI$ will yield only the CONFIG_PCI symbol.

Otherwise, I have a patch (that I'll submit shortly) to sort the symbols
by releveance.

Regards,
Yann E. MORIN.

-- 
.-----------------.--------------------.------------------.--------------------.
|  Yann E. MORIN  | Real-Time Embedded | /"\ ASCII RIBBON | Erics' conspiracy: |
| +33 662 376 056 | Software  Designer | \ / CAMPAIGN     |  ___               |
| +33 223 225 172 `------------.-------:  X  AGAINST      |  \e/  There is no  |
| http://ymorin.is-a-geek.org/ | _/*\_ | / \ HTML MAIL    |   v   conspiracy.  |
'------------------------------^-------^------------------^--------------------'

[PATCH] kconfig: sort found symbols by relevance

[Yann E. MORIN]

From: "Yann E. MORIN" <yann.morin.1998@free.fr>

When searching for symbols, return the symbols sorted by relevance.

Relevance is the ratio of the length of the matched string and the
length of the symbol name. Symbols of equal relevance are sorted
alphabetically.

Reported-by: Jean Delvare <jdelvare@suse.de>
Signed-off-by: "Yann E. MORIN" <yann.morin.1998@free.fr>
Cc: Jean Delvare <jdelvare@suse.de>
Cc: Michal Marek <mmarek@suse.cz>
Cc: Roland Eggner <edvx1@systemanalysen.net>
Cc: Wang YanQing <udknight@gmail.com>
---
 scripts/kconfig/symbol.c | 66 +++++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 57 insertions(+), 9 deletions(-)

diff --git a/scripts/kconfig/symbol.c b/scripts/kconfig/symbol.c
index ecc5aa5..baba030 100644
--- a/scripts/kconfig/symbol.c
+++ b/scripts/kconfig/symbol.c
@@ -943,38 +943,86 @@ const char *sym_escape_string_value(const char *in)
 	return res;
 }
 
+struct sym_match {
+	struct symbol	*sym;
+	int 		rel;
+};
+
+/* Compare matched symbols as thus:
+ * - highest relevance first
+ * - equal relevance sorted alphabetically
+ */
+static int sym_rel_comp( const void *sym1, const void *sym2 )
+{
+	struct sym_match **s1 = (struct sym_match **)sym1;
+	struct sym_match **s2 = (struct sym_match **)sym2;
+
+	if ( (*s1)->rel > (*s2)->rel )
+		return -1;
+	else if ( (*s1)->rel < (*s2)->rel )
+		return 1;
+	else
+		return strcmp( (*s1)->sym->name, (*s2)->sym->name );
+}
+
 struct symbol **sym_re_search(const char *pattern)
 {
 	struct symbol *sym, **sym_arr = NULL;
+	struct sym_match **sym_match_arr = NULL;
 	int i, cnt, size;
 	regex_t re;
+	regmatch_t match[1];
 
 	cnt = size = 0;
 	/* Skip if empty */
 	if (strlen(pattern) == 0)
 		return NULL;
-	if (regcomp(&re, pattern, REG_EXTENDED|REG_NOSUB|REG_ICASE))
+	if (regcomp(&re, pattern, REG_EXTENDED|REG_ICASE))
 		return NULL;
 
 	for_all_symbols(i, sym) {
+		struct sym_match *tmp_sym_match;
 		if (sym->flags & SYMBOL_CONST || !sym->name)
 			continue;
-		if (regexec(&re, sym->name, 0, NULL, 0))
+		if (regexec(&re, sym->name, 1, match, 0))
 			continue;
 		if (cnt + 1 >= size) {
-			void *tmp = sym_arr;
+			void *tmp;
 			size += 16;
-			sym_arr = realloc(sym_arr, size * sizeof(struct symbol *));
-			if (!sym_arr) {
-				free(tmp);
-				return NULL;
+			tmp = realloc(sym_match_arr, size * sizeof(struct sym_match *));
+			if (!tmp) {
+				goto sym_re_search_free;
 			}
+			sym_match_arr = tmp;
 		}
 		sym_calc_value(sym);
-		sym_arr[cnt++] = sym;
+		tmp_sym_match = (struct sym_match*)malloc(sizeof(struct sym_match));
+		if (!tmp_sym_match)
+			goto sym_re_search_free;
+		tmp_sym_match->sym = sym;
+		/* As regexec return 0, we know we have a match, so
+		 * we can use match[0].rm_[se]o without further checks
+		 */
+		tmp_sym_match->rel = (100*(match[0].rm_eo-match[0].rm_so))
+				     /strlen(sym->name);
+		sym_match_arr[cnt++] = tmp_sym_match;
 	}
-	if (sym_arr)
+
+	if( sym_match_arr ) {
+		qsort( sym_match_arr, cnt, sizeof(struct sym_match*), sym_rel_comp );
+		sym_arr = malloc( (cnt+1) * sizeof(struct symbol) );
+		if (!sym_arr)
+			goto sym_re_search_free;
+		for ( i=0; i<cnt; i++ )
+			sym_arr[i] = sym_match_arr[i]->sym;
 		sym_arr[cnt] = NULL;
+	}
+sym_re_search_free:
+	if (sym_match_arr) {
+		for ( i=0; i<cnt; i++ )
+			free( sym_match_arr[i] );
+		free( sym_match_arr );
+	}
 	regfree(&re);
 
 	return sym_arr;
-- 
1.8.1.2

Re: Wish: exact matches displayed first

[Thomas Petazzoni]

Dear Yann E. MORIN,

On Mon, 6 May 2013 14:54:59 +0200, Yann E. MORIN wrote:

> On Mon, May 06, 2013 at 12:00:07PM +0200, Yann E. MORIN wrote:
> > On Mon, May 06, 2013 at 09:50:29AM +0200, Jean Delvare wrote:
> > > I wish a search in "make menuconfig" would return an exact match, if it
> > > exists, first in the list. At the moment, looking for "PCI", for
> > > example, returns several dozen entries (anything matching "PCI") and
> > > CONFIG_PCI is far away from the top. Ideally I would expect this query
> > > to return CONFIG_PCI first.
> > 
> > Indeed, this has bugged me a few times, too.
> > I'll see what I can do.
> 
> BTW, did you know that you can search using extended regular expressions?
> Searching for ^PCI$ will yield only the CONFIG_PCI symbol.

Wow, I didn't know that. Is this documented/advertised somewhere?

Thomas
-- 
Thomas Petazzoni, Free Electrons
Kernel, drivers, real-time and embedded Linux
development, consulting, training and support.
http://free-electrons.com

Re: Wish: exact matches displayed first

[Yann E. MORIN]

Thomas, All,

On Mon, May 06, 2013 at 03:04:46PM +0200, Thomas Petazzoni wrote:
> On Mon, 6 May 2013 14:54:59 +0200, Yann E. MORIN wrote:
> > BTW, did you know that you can search using extended regular expressions?
> > Searching for ^PCI$ will yield only the CONFIG_PCI symbol.
> 
> Wow, I didn't know that. Is this documented/advertised somewhere?

Yes. In Documentation/kbuild/kconfig.txt:

    [...] This will tell you that you can also use
    regular expressions (regexes) in the search string, [...]

Regards,
Yann E. MORIN.

-- 
.-----------------.--------------------.------------------.--------------------.
|  Yann E. MORIN  | Real-Time Embedded | /"\ ASCII RIBBON | Erics' conspiracy: |
| +33 662 376 056 | Software  Designer | \ / CAMPAIGN     |  ___               |
| +33 223 225 172 `------------.-------:  X  AGAINST      |  \e/  There is no  |
| http://ymorin.is-a-geek.org/ | _/*\_ | / \ HTML MAIL    |   v   conspiracy.  |
'------------------------------^-------^------------------^--------------------'

Re: Wish: exact matches displayed first

[Jean Delvare]

Salut Yann,

Le Monday 06 May 2013 à 14:54 +0200, Yann E. MORIN a écrit :
> Jean, All,
> 
> On Mon, May 06, 2013 at 12:00:07PM +0200, Yann E. MORIN wrote:
> > On Mon, May 06, 2013 at 09:50:29AM +0200, Jean Delvare wrote:
> > > I wish a search in "make menuconfig" would return an exact match, if it
> > > exists, first in the list. At the moment, looking for "PCI", for
> > > example, returns several dozen entries (anything matching "PCI") and
> > > CONFIG_PCI is far away from the top. Ideally I would expect this query
> > > to return CONFIG_PCI first.
> > 
> > Indeed, this has bugged me a few times, too.
> > I'll see what I can do.
> 
> BTW, did you know that you can search using extended regular expressions?
> Searching for ^PCI$ will yield only the CONFIG_PCI symbol.

No, I didn't know. Thanks for the tip, it's very useful. If I can
remember it, that is ;)

> Otherwise, I have a patch (that I'll submit shortly) to sort the symbols
> by releveance.

I will be happy to test it!

-- 
Jean Delvare
Suse L3

Re: Wish: exact matches displayed first

[Jean Delvare]

Le Monday 06 May 2013 à 15:53 +0200, Yann E. MORIN a écrit :
> Thomas, All,
> 
> On Mon, May 06, 2013 at 03:04:46PM +0200, Thomas Petazzoni wrote:
> > On Mon, 6 May 2013 14:54:59 +0200, Yann E. MORIN wrote:
> > > BTW, did you know that you can search using extended regular expressions?
> > > Searching for ^PCI$ will yield only the CONFIG_PCI symbol.
> > 
> > Wow, I didn't know that. Is this documented/advertised somewhere?
> 
> Yes. In Documentation/kbuild/kconfig.txt:
> 
>     [...] This will tell you that you can also use
>     regular expressions (regexes) in the search string, [...]

Maybe this could be mentioned in the prompt itself, for all the
ignorants amongst us?

-- 
Jean Delvare
Suse L3

Re: Wish: exact matches displayed first

[Yann E. MORIN]

Jean, All,

On Mon, May 06, 2013 at 04:19:51PM +0200, Jean Delvare wrote:
> Le Monday 06 May 2013 à 15:53 +0200, Yann E. MORIN a écrit :
> > Thomas, All,
> > 
> > On Mon, May 06, 2013 at 03:04:46PM +0200, Thomas Petazzoni wrote:
> > > On Mon, 6 May 2013 14:54:59 +0200, Yann E. MORIN wrote:
> > > > BTW, did you know that you can search using extended regular expressions?
> > > > Searching for ^PCI$ will yield only the CONFIG_PCI symbol.
> > > 
> > > Wow, I didn't know that. Is this documented/advertised somewhere?
> > 
> > Yes. In Documentation/kbuild/kconfig.txt:
> > 
> >     [...] This will tell you that you can also use
> >     regular expressions (regexes) in the search string, [...]
> 
> Maybe this could be mentioned in the prompt itself, for all the
> ignorants amongst us?

In the search dialog, if you select 'Help', you'll get:

    Search for symbols and display their relations.
    Regular expressions are allowed.
    Example: search for "^FOO"

I guess it being presented in the help text is enough, no? ;-)

Regards,
Yann E. MORIN.

-- 
.-----------------.--------------------.------------------.--------------------.
|  Yann E. MORIN  | Real-Time Embedded | /"\ ASCII RIBBON | Erics' conspiracy: |
| +33 662 376 056 | Software  Designer | \ / CAMPAIGN     |  ___               |
| +33 223 225 172 `------------.-------:  X  AGAINST      |  \e/  There is no  |
| http://ymorin.is-a-geek.org/ | _/*\_ | / \ HTML MAIL    |   v   conspiracy.  |
'------------------------------^-------^------------------^--------------------'

Re: Wish: exact matches displayed first

[Jean Delvare]

Le Monday 06 May 2013 à 16:27 +0200, Yann E. MORIN a écrit :
> On Mon, May 06, 2013 at 04:19:51PM +0200, Jean Delvare wrote:
> > Le Monday 06 May 2013 à 15:53 +0200, Yann E. MORIN a écrit :

> > > Yes. In Documentation/kbuild/kconfig.txt:
> > > 
> > >     [...] This will tell you that you can also use
> > >     regular expressions (regexes) in the search string, [...]
> > 
> > Maybe this could be mentioned in the prompt itself, for all the
> > ignorants amongst us?
> 
> In the search dialog, if you select 'Help', you'll get:
> 
>     Search for symbols and display their relations.
>     Regular expressions are allowed.
>     Example: search for "^FOO"
> 
> I guess it being presented in the help text is enough, no? ;-)

OK, fair enough :)

-- 
Jean Delvare
Suse L3

Re: [PATCH] kconfig: sort found symbols by relevance

[Jean Delvare]

Le Monday 06 May 2013 à 15:02 +0200, Yann E. MORIN a écrit :
> From: "Yann E. MORIN" <yann.morin.1998@free.fr>
> 
> When searching for symbols, return the symbols sorted by relevance.
> 
> Relevance is the ratio of the length of the matched string and the
> length of the symbol name. Symbols of equal relevance are sorted
> alphabetically.
> 
> Reported-by: Jean Delvare <jdelvare@suse.de>
> Signed-off-by: "Yann E. MORIN" <yann.morin.1998@free.fr>
> Cc: Jean Delvare <jdelvare@suse.de>
> Cc: Michal Marek <mmarek@suse.cz>
> Cc: Roland Eggner <edvx1@systemanalysen.net>
> Cc: Wang YanQing <udknight@gmail.com>
> ---
>  scripts/kconfig/symbol.c | 66 +++++++++++++++++++++++++++++++++++++++++-------
>  1 file changed, 57 insertions(+), 9 deletions(-)

I did not look at the code, only tested it, and it does what I asked for
originally: exact match is listed first. So thank you :)

However I am not sure if your implementation is what we want. Your
definition of "relevance" is somewhat arbitrary and may not be
immediately to others. For example, my own definition of "relevance" was
that symbols which start with the subject string are more relevant than
the symbols which have the string in the middle. Others would possibly
have other definitions.

So in the end you have somewhat complex code for a sort order which may
surprise or confuse the user. It may put close to each other options
which are completely unrelated, and suboptions very far from their
parent.

I am wondering if it might not be better to go for a more simple
strategy: exact match on top and then sort alphabetically. Or even just
sort alphabetically - now that I know regexps are supported, it is easy
to get the exact match when I need it.

Just my two cents, maybe others have a diverging opinion.

Thanks for your work anyway,
-- 
Jean Delvare
Suse L3

Re: [PATCH] kconfig: sort found symbols by relevance

[Yann E. MORIN]

Jean, All,

On Mon, May 06, 2013 at 05:28:32PM +0200, Jean Delvare wrote:
> Le Monday 06 May 2013 à 15:02 +0200, Yann E. MORIN a écrit :
> > From: "Yann E. MORIN" <yann.morin.1998@free.fr>
> > 
> > When searching for symbols, return the symbols sorted by relevance.
> > 
> > Relevance is the ratio of the length of the matched string and the
> > length of the symbol name. Symbols of equal relevance are sorted
> > alphabetically.
> > 
> > Reported-by: Jean Delvare <jdelvare@suse.de>
> > Signed-off-by: "Yann E. MORIN" <yann.morin.1998@free.fr>
> > Cc: Jean Delvare <jdelvare@suse.de>
> > Cc: Michal Marek <mmarek@suse.cz>
> > Cc: Roland Eggner <edvx1@systemanalysen.net>
> > Cc: Wang YanQing <udknight@gmail.com>
> > ---
> >  scripts/kconfig/symbol.c | 66 +++++++++++++++++++++++++++++++++++++++++-------
> >  1 file changed, 57 insertions(+), 9 deletions(-)
> 
> I did not look at the code, only tested it, and it does what I asked for
> originally: exact match is listed first. So thank you :)
> 
> However I am not sure if your implementation is what we want. Your
> definition of "relevance" is somewhat arbitrary and may not be
> immediately to others. For example, my own definition of "relevance" was
> that symbols which start with the subject string are more relevant than
> the symbols which have the string in the middle. Others would possibly
> have other definitions.

Yes, I understand. That was mostly a proposal. I'm open for discussion! :-)

> So in the end you have somewhat complex code for a sort order which may
> surprise or confuse the user. It may put close to each other options
> which are completely unrelated, and suboptions very far from their
> parent.

The notion of "sub-options" is very fuzzy: as symbols are stored in an
hash-based array, it is not possible to now how they relate to each other
order-wise, once the parsing of the Kconfig is done. So we can't expect
the search results to reflect the 'proximity' of symbol declarations.

> I am wondering if it might not be better to go for a more simple
> strategy: exact match on top and then sort alphabetically. Or even just
> sort alphabetically - now that I know regexps are supported, it is easy
> to get the exact match when I need it.

Also, to prefer exact match requires we check how much of the symbol
name was matched (hence my initial 'relevance' heuristic).

However, here is a proposal for another heuristic that seems to work
relatively well for me (but is a very little bit more complex, I'm
afraid), that tries hard to get the most relevant symbols first:

Compare matched symbols as thus:
  - first, symbols with a prompt,   [1]
  - then, smallest offset,          [2]
  - then, shortest match,           [3]
  - then, highest relevance,        [4]
  - finally, alphabetical sort      [5]

When searching for 'P.*CI' :

[1] Symbols of interest are probably those with a prompt, as they can be
    changed, while symbols with no prompt are only for info. Thus:
        PCIEASPM comes before PCI_ATS

[2] Symbols that match earlier in the name are to be preferred over
    symbols which match later. Thus:
        PCI_MSI comes before WDTPCI

[3] The shortest match is (IMHO) more interesting than a longer one.
    Thus:
        PCI comes before PCMCIA

[4] The relevance is the ratio of the length of the match against the
    length of the symbol. The more of a symbol name we match, the more
    instersting that symbol is. Thus:
        PCIEAER comes before PCIEASPM

[5] As fallback, sort symbols alphabetically (no example, it's explicit
    enough, I guess :-) )

Of course 'P.*CI' is really a torture-test search, real searches will
probably be more precise in the first place. This heuristic seems to
also work well with real searches. YMMV, of course...

What do you (and others!) think about this? I'll post the patch shortly
for testing.

> Thanks for your work anyway,

Cheers! :-)

Regards,
Yann E. MORIN.

-- 
.-----------------.--------------------.------------------.--------------------.
|  Yann E. MORIN  | Real-Time Embedded | /"\ ASCII RIBBON | Erics' conspiracy: |
| +33 662 376 056 | Software  Designer | \ / CAMPAIGN     |  ___               |
| +33 223 225 172 `------------.-------:  X  AGAINST      |  \e/  There is no  |
| http://ymorin.is-a-geek.org/ | _/*\_ | / \ HTML MAIL    |   v   conspiracy.  |
'------------------------------^-------^------------------^--------------------'

[PATCH] kconfig: sort found symbols by relevance

[Yann E. MORIN]

From: "Yann E. MORIN" <yann.morin.1998@free.fr>

When searching for symbols, return the symbols sorted by relevance.

Relevance is the ratio of the length of the matched string and the
length of the symbol name. Symbols of equal relevance are sorted
alphabetically.

Reported-by: Jean Delvare <jdelvare@suse.de>
Signed-off-by: "Yann E. MORIN" <yann.morin.1998@free.fr>
Cc: Jean Delvare <jdelvare@suse.de>
Cc: Michal Marek <mmarek@suse.cz>
Cc: Roland Eggner <edvx1@systemanalysen.net>
Cc: Wang YanQing <udknight@gmail.com>
---
 scripts/kconfig/symbol.c | 66 +++++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 57 insertions(+), 9 deletions(-)

diff --git a/scripts/kconfig/symbol.c b/scripts/kconfig/symbol.c
index ecc5aa5..baba030 100644
--- a/scripts/kconfig/symbol.c
+++ b/scripts/kconfig/symbol.c
@@ -943,38 +943,86 @@ const char *sym_escape_string_value(const char *in)
 	return res;
 }
 
+struct sym_match {
+	struct symbol	*sym;
+	int 		rel;
+};
+
+/* Compare matched symbols as thus:
+ * - highest relevance first
+ * - equal relevance sorted alphabetically
+ */
+static int sym_rel_comp( const void *sym1, const void *sym2 )
+{
+	struct sym_match **s1 = (struct sym_match **)sym1;
+	struct sym_match **s2 = (struct sym_match **)sym2;
+
+	if ( (*s1)->rel > (*s2)->rel )
+		return -1;
+	else if ( (*s1)->rel < (*s2)->rel )
+		return 1;
+	else
+		return strcmp( (*s1)->sym->name, (*s2)->sym->name );
+}
+
 struct symbol **sym_re_search(const char *pattern)
 {
 	struct symbol *sym, **sym_arr = NULL;
+	struct sym_match **sym_match_arr = NULL;
 	int i, cnt, size;
 	regex_t re;
+	regmatch_t match[1];
 
 	cnt = size = 0;
 	/* Skip if empty */
 	if (strlen(pattern) == 0)
 		return NULL;
-	if (regcomp(&re, pattern, REG_EXTENDED|REG_NOSUB|REG_ICASE))
+	if (regcomp(&re, pattern, REG_EXTENDED|REG_ICASE))
 		return NULL;
 
 	for_all_symbols(i, sym) {
+		struct sym_match *tmp_sym_match;
 		if (sym->flags & SYMBOL_CONST || !sym->name)
 			continue;
-		if (regexec(&re, sym->name, 0, NULL, 0))
+		if (regexec(&re, sym->name, 1, match, 0))
 			continue;
 		if (cnt + 1 >= size) {
-			void *tmp = sym_arr;
+			void *tmp;
 			size += 16;
-			sym_arr = realloc(sym_arr, size * sizeof(struct symbol *));
-			if (!sym_arr) {
-				free(tmp);
-				return NULL;
+			tmp = realloc(sym_match_arr, size * sizeof(struct sym_match *));
+			if (!tmp) {
+				goto sym_re_search_free;
 			}
+			sym_match_arr = tmp;
 		}
 		sym_calc_value(sym);
-		sym_arr[cnt++] = sym;
+		tmp_sym_match = (struct sym_match*)malloc(sizeof(struct sym_match));
+		if (!tmp_sym_match)
+			goto sym_re_search_free;
+		tmp_sym_match->sym = sym;
+		/* As regexec return 0, we know we have a match, so
+		 * we can use match[0].rm_[se]o without further checks
+		 */
+		tmp_sym_match->rel = (100*(match[0].rm_eo-match[0].rm_so))
+				     /strlen(sym->name);
+		sym_match_arr[cnt++] = tmp_sym_match;
 	}
-	if (sym_arr)
+
+	if( sym_match_arr ) {
+		qsort( sym_match_arr, cnt, sizeof(struct sym_match*), sym_rel_comp );
+		sym_arr = malloc( (cnt+1) * sizeof(struct symbol) );
+		if (!sym_arr)
+			goto sym_re_search_free;
+		for ( i=0; i<cnt; i++ )
+			sym_arr[i] = sym_match_arr[i]->sym;
 		sym_arr[cnt] = NULL;
+	}
+sym_re_search_free:
+	if (sym_match_arr) {
+		for ( i=0; i<cnt; i++ )
+			free( sym_match_arr[i] );
+		free( sym_match_arr );
+	}
 	regfree(&re);
 
 	return sym_arr;
-- 
1.8.1.2

Re: [PATCH] kconfig: sort found symbols by relevance

[Yann E. MORIN]

Jean, All,

On Mon, May 06, 2013 at 08:20:47PM +0200, Yann E. MORIN wrote:
> When searching for symbols, return the symbols sorted by relevance.

Woops... Worng version of the patch. Forget it...
Sorry...

Regards,
Yann E. MORIN.

-- 
.-----------------.--------------------.------------------.--------------------.
|  Yann E. MORIN  | Real-Time Embedded | /"\ ASCII RIBBON | Erics' conspiracy: |
| +33 662 376 056 | Software  Designer | \ / CAMPAIGN     |  ___               |
| +33 223 225 172 `------------.-------:  X  AGAINST      |  \e/  There is no  |
| http://ymorin.is-a-geek.org/ | _/*\_ | / \ HTML MAIL    |   v   conspiracy.  |
'------------------------------^-------^------------------^--------------------'

[PATCH v3] kconfig: sort found symbols by relevance

[Yann E. MORIN]

From: "Yann E. MORIN" <yann.morin.1998@free.fr>

When searching for symbols, return the symbols sorted by relevance.

Sorting is done as thus:
  - first, symbols with a prompt,   [1]
  - then, smallest offset,          [2]
  - then, shortest match,           [3]
  - then, highest relative match,   [4]
  - finally, alphabetical sort      [5]

So, searching (eg.) for 'P.*CI' :

[1] Symbols of interest are probably those with a prompt, as they can be
    changed, while symbols with no prompt are only for info. Thus:
        PCIEASPM comes before PCI_ATS

[2] Symbols that match earlier in the name are to be preferred over
    symbols which match later. Thus:
        PCI_MSI comes before WDTPCI

[3] The shortest match is (IMHO) more interesting than a longer one.
    Thus:
        PCI comes before PCMCIA

[4] The relative match is the ratio of the length of the match against
    the length of the symbol. The more of a symbol name we match, the
    more instersting that symbol is. Thus:
        PCIEAER comes before PCIEASPM

[5] As fallback, sort symbols alphabetically

This heuristic tries hard to get interesting symbols first in the list.

In any case, exact match can (as previously) be requested by using
start-of-line and end-of-line in the searc regexp: ^PCI$

Reported-by: Jean Delvare <jdelvare@suse.de>
Signed-off-by: "Yann E. MORIN" <yann.morin.1998@free.fr>
Cc: Jean Delvare <jdelvare@suse.de>
Cc: Michal Marek <mmarek@suse.cz>
Cc: Roland Eggner <edvx1@systemanalysen.net>
Cc: Wang YanQing <udknight@gmail.com>
---
 scripts/kconfig/symbol.c | 96 +++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 87 insertions(+), 9 deletions(-)

diff --git a/scripts/kconfig/symbol.c b/scripts/kconfig/symbol.c
index ecc5aa5..20f8107 100644
--- a/scripts/kconfig/symbol.c
+++ b/scripts/kconfig/symbol.c
@@ -943,38 +943,116 @@ const char *sym_escape_string_value(const char *in)
 	return res;
 }
 
+struct sym_match {
+	struct symbol	*sym;
+	off_t		so, eo;
+};
+
+/* Compare matched symbols as thus:
+ * - first, symbols with a prompt,
+ * - then, smallest offset,
+ * - then, shortest match,
+ * - then, highest relative match,
+ * - finally, alphabetical sort
+ */
+static int sym_rel_comp( const void *sym1, const void *sym2 )
+{
+	struct sym_match *s1 = *(struct sym_match **)sym1;
+	struct sym_match *s2 = *(struct sym_match **)sym2;
+	struct property *p;
+	bool p1 = false, p2 = false;
+	int l1, l2, r1, r2;
+
+	for_all_prompts(s1->sym, p) {
+		p1 = true;
+	}
+	for_all_prompts(s2->sym, p) {
+		p2 = true;
+	}
+	if (p1 && !p2)
+		return -1;
+	if (!p1 && p2)
+		return 1;
+
+	if ( s1->so < s2->so )
+		return -1;
+	if ( s1->so > s2->so )
+		return 1;
+
+	l1 = s1->eo - s1->so;
+	l2 = s2->eo - s2->so;
+	if ( l1 > l2 )
+		return 1;
+	if ( l1 < l2 )
+		return -1;
+
+	r1 = 100*l1 / strlen(s1->sym->name);
+	r2 = 100*l2 / strlen(s2->sym->name);
+	if ( r1 > r2 )
+		return -1;
+	if ( r1 < r2 )
+		return 1;
+
+	return strcmp( s1->sym->name, s2->sym->name );
+}
+
 struct symbol **sym_re_search(const char *pattern)
 {
 	struct symbol *sym, **sym_arr = NULL;
+	struct sym_match **sym_match_arr = NULL;
 	int i, cnt, size;
 	regex_t re;
+	regmatch_t match[1];
 
 	cnt = size = 0;
 	/* Skip if empty */
 	if (strlen(pattern) == 0)
 		return NULL;
-	if (regcomp(&re, pattern, REG_EXTENDED|REG_NOSUB|REG_ICASE))
+	if (regcomp(&re, pattern, REG_EXTENDED|REG_ICASE))
 		return NULL;
 
 	for_all_symbols(i, sym) {
+		struct sym_match *tmp_sym_match;
 		if (sym->flags & SYMBOL_CONST || !sym->name)
 			continue;
-		if (regexec(&re, sym->name, 0, NULL, 0))
+		if (regexec(&re, sym->name, 1, match, 0))
 			continue;
 		if (cnt + 1 >= size) {
-			void *tmp = sym_arr;
+			void *tmp;
 			size += 16;
-			sym_arr = realloc(sym_arr, size * sizeof(struct symbol *));
-			if (!sym_arr) {
-				free(tmp);
-				return NULL;
+			tmp = realloc(sym_match_arr, size * sizeof(struct sym_match *));
+			if (!tmp) {
+				goto sym_re_search_free;
 			}
+			sym_match_arr = tmp;
 		}
 		sym_calc_value(sym);
-		sym_arr[cnt++] = sym;
+		tmp_sym_match = (struct sym_match*)malloc(sizeof(struct sym_match));
+		if (!tmp_sym_match)
+			goto sym_re_search_free;
+		tmp_sym_match->sym = sym;
+		/* As regexec return 0, we know we have a match, so
+		 * we can use match[0].rm_[se]o without further checks
+		 */
+		tmp_sym_match->so = match[0].rm_so;
+		tmp_sym_match->eo = match[0].rm_eo;
+		sym_match_arr[cnt++] = tmp_sym_match;
 	}
-	if (sym_arr)
+	if( sym_match_arr ) {
+		qsort( sym_match_arr, cnt, sizeof(struct sym_match*), sym_rel_comp );
+		sym_arr = malloc( (cnt+1) * sizeof(struct symbol) );
+		if (!sym_arr)
+			goto sym_re_search_free;
+		for ( i=0; i<cnt; i++ )
+			sym_arr[i] = sym_match_arr[i]->sym;
 		sym_arr[cnt] = NULL;
+	}
+sym_re_search_free:
+	if (sym_match_arr) {
+		for ( i=0; i<cnt; i++ )
+			free( sym_match_arr[i] );
+		free( sym_match_arr );
+	}
 	regfree(&re);
 
 	return sym_arr;
-- 
1.8.1.2

Re: [PATCH] kconfig: sort found symbols by relevance

[Wang YanQing]

On Mon, May 06, 2013 at 05:28:32PM +0200, Jean Delvare wrote:
> Le Monday 06 May 2013 à 15:02 +0200, Yann E. MORIN a écrit :
> > From: "Yann E. MORIN" <yann.morin.1998@free.fr>
> > 
> > When searching for symbols, return the symbols sorted by relevance.
> > 
> > Relevance is the ratio of the length of the matched string and the
> > length of the symbol name. Symbols of equal relevance are sorted
> > alphabetically.
> I did not look at the code, only tested it, and it does what I asked for
> originally: exact match is listed first. So thank you :)
> 
> However I am not sure if your implementation is what we want. Your
> definition of "relevance" is somewhat arbitrary and may not be
> immediately to others. For example, my own definition of "relevance" was
> that symbols which start with the subject string are more relevant than
> the symbols which have the string in the middle. Others would possibly
> have other definitions.

But no matter what the definition of relevance in text search, 
in the middle or start or end, the searcher always want the "results" 
look like what they input literal.

I think Yann's definition make sense. It is just a pattern matching ratio question.

If you want in start, just use ^PCI(reguar search), then with the help of 
this patch, will make people life easier.

This patch is not to replace the regular search, you can just use them together.

BTW, I haven't read the code right now, maybe I will read it tonight.
I test it, it works well, and I find it is useful to use it with regular search.

Thanks.

Re: [PATCH v3] kconfig: sort found symbols by relevance

[Wang YanQing]

On Mon, May 06, 2013 at 11:15:31PM +0200, Yann E. MORIN wrote:
> From: "Yann E. MORIN" <yann.morin.1998@free.fr>
> 
> When searching for symbols, return the symbols sorted by relevance.
> 
> Sorting is done as thus:
>   - first, symbols with a prompt,   [1]
>   - then, smallest offset,          [2]
>   - then, shortest match,           [3]
>   - then, highest relative match,   [4]
>   - finally, alphabetical sort      [5]
> 
> So, searching (eg.) for 'P.*CI' :
> 
> [1] Symbols of interest are probably those with a prompt, as they can be
>     changed, while symbols with no prompt are only for info. Thus:
>         PCIEASPM comes before PCI_ATS

Search the value of symbols with no prompt are useful too

> [2] Symbols that match earlier in the name are to be preferred over
>     symbols which match later. Thus:
>         PCI_MSI comes before WDTPCI

We can achieve this with ^PCI regular search

> [3] The shortest match is (IMHO) more interesting than a longer one.
>     Thus:
>         PCI comes before PCMCIA

We can achieve this with ^PCI regular search plus your previous heuristic

> [4] The relative match is the ratio of the length of the match against
>     the length of the symbol. The more of a symbol name we match, the
>     more instersting that symbol is. Thus:
>         PCIEAER comes before PCIEASPM

This is what your first heuristic

> [5] As fallback, sort symbols alphabetically
This is in your first heuristic too.

> This heuristic tries hard to get interesting symbols first in the list.
I don't mean your this heuristic is bad, but
maybe provide mechanism to user will make guesser life easier.

Thanks.

Re: [PATCH v3] kconfig: sort found symbols by relevance

[Yann E. MORIN]

Wang, All,

On Thu, May 09, 2013 at 11:27:31PM +0800, Wang YanQing wrote:
> On Mon, May 06, 2013 at 11:15:31PM +0200, Yann E. MORIN wrote:
> > From: "Yann E. MORIN" <yann.morin.1998@free.fr>
> > 
> > When searching for symbols, return the symbols sorted by relevance.
> > 
> > Sorting is done as thus:
> >   - first, symbols with a prompt,   [1]
> >   - then, smallest offset,          [2]
> >   - then, shortest match,           [3]
> >   - then, highest relative match,   [4]
> >   - finally, alphabetical sort      [5]
> > 
> > So, searching (eg.) for 'P.*CI' :
> > 
> > [1] Symbols of interest are probably those with a prompt, as they can be
> >     changed, while symbols with no prompt are only for info. Thus:
> >         PCIEASPM comes before PCI_ATS
> 
> Search the value of symbols with no prompt are useful too

My reasonning here is that often I need to toggle a symbol, but am not
sure what menu it's in, so I search for it.

Sometime, I also need to search for prompt-less symbols, too, to see why
a symbol I want is not visible. But that's not the most common use-case.

Also, the examples provided were with a very verbose search: 'P.*CI'
which is expected to return a hell of a lot of symbols. More precise
searches will yield substancially fewer symbols, so the search results
will probably fit in 1 or 2 pages, not 10+ like 'P.*CI'

> > [2] Symbols that match earlier in the name are to be preferred over
> >     symbols which match later. Thus:
> >         PCI_MSI comes before WDTPCI
> 
> We can achieve this with ^PCI regular search

Yes, but I expect users do enter the begining of symbols, not a string
in the middle or at the end.

Also, as Jean and Thomas have proven, not many people know that searches
can be regular expressions.

> > [3] The shortest match is (IMHO) more interesting than a longer one.
> >     Thus:
> >         PCI comes before PCMCIA
> 
> We can achieve this with ^PCI regular search plus your previous heuristic

This one is not about location of the match, it's about the length of
the match: the shortest the match, the more interesting it is (IMHO). So
we'd prefer FOO_PCI_BAR_BUZ over A_PACI_B  (when searching for 'P.*CI').

> > [4] The relative match is the ratio of the length of the match against
> >     the length of the symbol. The more of a symbol name we match, the
> >     more instersting that symbol is. Thus:
> >         PCIEAER comes before PCIEASPM
> 
> This is what your first heuristic
> 
> > [5] As fallback, sort symbols alphabetically
> This is in your first heuristic too.
> 
> > This heuristic tries hard to get interesting symbols first in the list.
> I don't mean your this heuristic is bad, but

This heuristic is just that: a heuristic. It kicks in only if the user
dit not provide an anchored regexp (ie with start- or end-of-line).

For the ten-or-so tests I did, the sorting was rather appropriate,
though that's only ten-or-so tests and is not exhaustive (and probably
subject to testing bias, too).

What I'm trying to achieve here is come up with a way to sort symbols
for searches of *non-anchored* regexps. Anchored regexps will always
provide the results they used to provide so far.

Maybe we can emphasize in the UI the fact that regexps, and especially
anchored regexps, can be used.

> maybe provide mechanism to user will make guesser life easier.

Sorry, I can't make sense of this sentence. :-( Can you elaborate a bit
what you meant, please?

Regards,
Yann E. MORIN.

-- 
.-----------------.--------------------.------------------.--------------------.
|  Yann E. MORIN  | Real-Time Embedded | /"\ ASCII RIBBON | Erics' conspiracy: |
| +33 662 376 056 | Software  Designer | \ / CAMPAIGN     |  ___               |
| +33 223 225 172 `------------.-------:  X  AGAINST      |  \e/  There is no  |
| http://ymorin.is-a-geek.org/ | _/*\_ | / \ HTML MAIL    |   v   conspiracy.  |
'------------------------------^-------^------------------^--------------------'

Re: [PATCH v3] kconfig: sort found symbols by relevance

[Wang YanQing]

On Thu, May 09, 2013 at 06:12:17PM +0200, Yann E. MORIN wrote:
> Wang, All,
> 
> On Thu, May 09, 2013 at 11:27:31PM +0800, Wang YanQing wrote:
> > On Mon, May 06, 2013 at 11:15:31PM +0200, Yann E. MORIN wrote:
> > > From: "Yann E. MORIN" <yann.morin.1998@free.fr>
> > > 
> > > When searching for symbols, return the symbols sorted by relevance.
> > > 
> > > Sorting is done as thus:
> > >   - first, symbols with a prompt,   [1]
> > >   - then, smallest offset,          [2]
> > >   - then, shortest match,           [3]
> > >   - then, highest relative match,   [4]
> > >   - finally, alphabetical sort      [5]
> > > 
> > > So, searching (eg.) for 'P.*CI' :
> > > 
> > > [1] Symbols of interest are probably those with a prompt, as they can be
> > >     changed, while symbols with no prompt are only for info. Thus:
> > >         PCIEASPM comes before PCI_ATS
> > 
> > Search the value of symbols with no prompt are useful too
> 
> My reasonning here is that often I need to toggle a symbol, but am not
> sure what menu it's in, so I search for it.
> 
> Sometime, I also need to search for prompt-less symbols, too, to see why
> a symbol I want is not visible. But that's not the most common use-case.
> 
> Also, the examples provided were with a very verbose search: 'P.*CI'
> which is expected to return a hell of a lot of symbols. More precise
> searches will yield substancially fewer symbols, so the search results
> will probably fit in 1 or 2 pages, not 10+ like 'P.*CI'
> 
> > > [2] Symbols that match earlier in the name are to be preferred over
> > >     symbols which match later. Thus:
> > >         PCI_MSI comes before WDTPCI
> > 
> > We can achieve this with ^PCI regular search
> 
> Yes, but I expect users do enter the begining of symbols, not a string
> in the middle or at the end.
> 
> Also, as Jean and Thomas have proven, not many people know that searches
> can be regular expressions.

Ok, indeed, I don't know regular expression in menuconfig before you
point it out :)

> > > [3] The shortest match is (IMHO) more interesting than a longer one.
> > >     Thus:
> > >         PCI comes before PCMCIA
> > 
> > We can achieve this with ^PCI regular search plus your previous heuristic
> 
> This one is not about location of the match, it's about the length of
> the match: the shortest the match, the more interesting it is (IMHO). So
> we'd prefer FOO_PCI_BAR_BUZ over A_PACI_B  (when searching for 'P.*CI').

Ok, I get your meaning.

> > > [4] The relative match is the ratio of the length of the match against
> > >     the length of the symbol. The more of a symbol name we match, the
> > >     more instersting that symbol is. Thus:
> > >         PCIEAER comes before PCIEASPM
> > 
> > This is what your first heuristic
> > 
> > > [5] As fallback, sort symbols alphabetically
> > This is in your first heuristic too.
> > 
> > > This heuristic tries hard to get interesting symbols first in the list.
> > I don't mean your this heuristic is bad, but
> 
> This heuristic is just that: a heuristic. It kicks in only if the user
> dit not provide an anchored regexp (ie with start- or end-of-line).
> 
> For the ten-or-so tests I did, the sorting was rather appropriate,
> though that's only ten-or-so tests and is not exhaustive (and probably
> subject to testing bias, too).

I hope more people will find the sorting is appropriate if Michal Marek accept 
it :)

> What I'm trying to achieve here is come up with a way to sort symbols
> for searches of *non-anchored* regexps. Anchored regexps will always
> provide the results they used to provide so far.
> 
> Maybe we can emphasize in the UI the fact that regexps, and especially
> anchored regexps, can be used.
> 
> > maybe provide mechanism to user will make guesser life easier.
> 
> Sorry, I can't make sense of this sentence. :-( Can you elaborate a bit
> what you meant, please?

The mechanism means first heuristic in previous Email patch.

I though we could get this heuristic's result by composite your first heuristic
in previous Email patch with regular expression, it seams like I lost something,
see above.

Thanks.

Re: [PATCH v3] kconfig: sort found symbols by relevance

[Yann E. MORIN]

Wang, All,

On Fri, May 10, 2013 at 08:51:25AM +0800, Wang YanQing wrote:
> On Thu, May 09, 2013 at 06:12:17PM +0200, Yann E. MORIN wrote:
[--SNIP--]
> > For the ten-or-so tests I did, the sorting was rather appropriate,
> > though that's only ten-or-so tests and is not exhaustive (and probably
> > subject to testing bias, too).
> 
> I hope more people will find the sorting is appropriate if Michal Marek accept 
> it :)

OK, I'll queue it in my tree, and will push it to Michal for 3.11, as it
is a bit too late for 3.10, now.

> > > maybe provide mechanism to user will make guesser life easier.
> > Sorry, I can't make sense of this sentence. :-( Can you elaborate a bit
> > what you meant, please?
> 
> The mechanism means first heuristic in previous Email patch.
> 
> I though we could get this heuristic's result by composite your first heuristic
> in previous Email patch with regular expression, it seams like I lost something,
> see above.

OK, so I'll keep it as-is (I will just fix some coding-style issues I've
spotted).

Thanks for the input!

Regards,
Yann E. MORIN.

-- 
.-----------------.--------------------.------------------.--------------------.
|  Yann E. MORIN  | Real-Time Embedded | /"\ ASCII RIBBON | Erics' conspiracy: |
| +33 662 376 056 | Software  Designer | \ / CAMPAIGN     |  ___               |
| +33 223 225 172 `------------.-------:  X  AGAINST      |  \e/  There is no  |
| http://ymorin.is-a-geek.org/ | _/*\_ | / \ HTML MAIL    |   v   conspiracy.  |
'------------------------------^-------^------------------^--------------------'