From patchwork Tue Jun 18 22:45:08 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Yann E. MORIN" X-Patchwork-Id: 2745531 Return-Path: X-Original-To: patchwork-linux-kbuild@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork1.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.19.201]) by patchwork1.web.kernel.org (Postfix) with ESMTP id 56A469F39E for ; Tue, 18 Jun 2013 22:45:46 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id 3ECAC20218 for ; Tue, 18 Jun 2013 22:45:45 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 0416F2024B for ; Tue, 18 Jun 2013 22:45:44 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S933838Ab3FRWpj (ORCPT ); Tue, 18 Jun 2013 18:45:39 -0400 Received: from mail-we0-f170.google.com ([74.125.82.170]:52462 "EHLO mail-we0-f170.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S933822Ab3FRWpi (ORCPT ); Tue, 18 Jun 2013 18:45:38 -0400 Received: by mail-we0-f170.google.com with SMTP id w57so3947156wes.1 for ; Tue, 18 Jun 2013 15:45:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=sender:from:to:cc:subject:date:message-id:x-mailer:in-reply-to :references:in-reply-to:references; bh=xBW8WloyOFMaDm1p2Tfys9BYi0KNyEp6rmqMosyaFts=; b=yYVZwNy4Cxifm6XKJ15uFDB74+Tmvje6C8IlkX+uauDAG7fGq9L8itXTQseksDxCqM BoXdGHNwtWFliSHdQyRXQSsjdY/NDb5aGa27s0QJp2cZBntPBTPq0RsameCp/Nmq93o1 1RTR/CX9sA1eUXTzpQrL0i1rXkS+eZGhf4d5Eu1E1ue1vkaMhWReVTIGoPdSl8DR7Hq3 sadR0x9cRSVe52mfIEHus6BNKitiqqSh6A8VDInhcZDqqhfMWHt35b6o+4qpSnFAr8xy yBbgppi/NRIjTtED4yKWXNbqZpD8e0I1DWATZUrK88KfAjrGmNnnOivl5mN+sN9HRcC4 I3CQ== X-Received: by 10.194.249.69 with SMTP id ys5mr14842wjc.39.1371595536497; Tue, 18 Jun 2013 15:45:36 -0700 (PDT) Received: from gourin.bzh.lan (ks3095497.kimsufi.com. [94.23.60.27]) by mx.google.com with ESMTPSA id o14sm5307237wiv.3.2013.06.18.15.45.34 for (version=TLSv1.1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Tue, 18 Jun 2013 15:45:35 -0700 (PDT) From: "Yann E. MORIN" To: linux-kbuild@vger.kernel.org Cc: linux-kernel@vger.kernel.org, Michal Marek , "Yann E. MORIN" , Jean Delvare , Roland Eggner , Wang YanQing Subject: [PATCH 12/14] kconfig: sort found symbols by relevance Date: Wed, 19 Jun 2013 00:45:08 +0200 Message-Id: <3e2346029e33ef9405b87d72a32d96d0aafb524a.1371595499.git.yann.morin.1998@free.fr> X-Mailer: git-send-email 1.8.1.2 In-Reply-To: References: In-Reply-To: References: Sender: linux-kbuild-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kbuild@vger.kernel.org X-Spam-Status: No, score=-8.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, FREEMAIL_FROM,RCVD_IN_DNSWL_HI,RP_MATCHES_RCVD,T_DKIM_INVALID, UNPARSEABLE_RELAY autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: "Yann E. MORIN" 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 search regexp: ^PCI$ Reported-by: Jean Delvare Signed-off-by: "Yann E. MORIN" Cc: Jean Delvare Cc: Michal Marek Cc: Roland Eggner Cc: Wang YanQing --- 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 ab8f4c8..d08e300 100644 --- a/scripts/kconfig/symbol.c +++ b/scripts/kconfig/symbol.c @@ -954,38 +954,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 (l1sym->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;