From owner-svn-src-head@freebsd.org Wed Nov 20 19:43:35 2019 Return-Path: Delivered-To: svn-src-head@mailman.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.nyi.freebsd.org (Postfix) with ESMTP id 8FE0F1C038D; Wed, 20 Nov 2019 19:43:35 +0000 (UTC) (envelope-from cem@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) server-signature RSA-PSS (4096 bits) client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "Let's Encrypt Authority X3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 47JCmR3HjMz4GCH; Wed, 20 Nov 2019 19:43:35 +0000 (UTC) (envelope-from cem@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 54137279D4; Wed, 20 Nov 2019 19:43:35 +0000 (UTC) (envelope-from cem@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id xAKJhZGO096460; Wed, 20 Nov 2019 19:43:35 GMT (envelope-from cem@FreeBSD.org) Received: (from cem@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id xAKJhY2Z096458; Wed, 20 Nov 2019 19:43:34 GMT (envelope-from cem@FreeBSD.org) Message-Id: <201911201943.xAKJhY2Z096458@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: cem set sender to cem@FreeBSD.org using -f From: Conrad Meyer Date: Wed, 20 Nov 2019 19:43:34 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r354912 - in head: contrib/netbsd-tests/usr.bin/unifdef usr.bin/unifdef X-SVN-Group: head X-SVN-Commit-Author: cem X-SVN-Commit-Paths: in head: contrib/netbsd-tests/usr.bin/unifdef usr.bin/unifdef X-SVN-Commit-Revision: 354912 X-SVN-Commit-Repository: base MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-head@freebsd.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: SVN commit messages for the src tree for head/-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 20 Nov 2019 19:43:35 -0000 Author: cem Date: Wed Nov 20 19:43:34 2019 New Revision: 354912 URL: https://svnweb.freebsd.org/changeset/base/354912 Log: Re-apply fixed r354847 unifdef(1): Improve worst-case bound on symbol resolution Use RB_TREE to make some algorithms O(lg N) and O(N lg N) instead of O(N) and O(N^2). While here, remove arbitrarily limit on number of macros understood. Reverts r354877 and r354878, which disabled the (correct) test. PR: 242095 Reported by: lwhsu Modified: head/contrib/netbsd-tests/usr.bin/unifdef/t_basic.sh head/usr.bin/unifdef/unifdef.c Modified: head/contrib/netbsd-tests/usr.bin/unifdef/t_basic.sh ============================================================================== --- head/contrib/netbsd-tests/usr.bin/unifdef/t_basic.sh Wed Nov 20 19:07:22 2019 (r354911) +++ head/contrib/netbsd-tests/usr.bin/unifdef/t_basic.sh Wed Nov 20 19:43:34 2019 (r354912) @@ -35,9 +35,6 @@ basic_head() { } basic_body() { - if [ "$(atf_config_get ci false)" = "true" ]; then - atf_skip "https://bugs.freebsd.org/242095" - fi atf_check -s ignore -o file:$(atf_get_srcdir)/d_basic.out \ -x "unifdef -U__FreeBSD__ $(atf_get_srcdir)/d_basic.in" Modified: head/usr.bin/unifdef/unifdef.c ============================================================================== --- head/usr.bin/unifdef/unifdef.c Wed Nov 20 19:07:22 2019 (r354911) +++ head/usr.bin/unifdef/unifdef.c Wed Nov 20 19:43:34 2019 (r354912) @@ -45,8 +45,11 @@ * it possible to handle all "dodgy" directives correctly. */ +#include #include +#include +#include #include #include #include @@ -149,7 +152,6 @@ static char const * const linestate_name[] = { */ #define MAXDEPTH 64 /* maximum #if nesting */ #define MAXLINE 4096 /* maximum length of line */ -#define MAXSYMS 16384 /* maximum number of symbols */ /* * Sometimes when editing a keyword the replacement text is longer, so @@ -158,6 +160,26 @@ static char const * const linestate_name[] = { #define EDITSLOP 10 /* + * C17/18 allow 63 characters per macro name, but up to 127 arbitrarily large + * parameters. + */ +struct macro { + RB_ENTRY(macro) entry; + const char *name; + const char *value; + bool ignore; /* -iDsym or -iUsym */ +}; + +static int +macro_cmp(struct macro *a, struct macro *b) +{ + return (strcmp(a->name, b->name)); +} + +static RB_HEAD(MACROMAP, macro) macro_tree = RB_INITIALIZER(¯o_tree); +RB_GENERATE_STATIC(MACROMAP, macro, entry, macro_cmp); + +/* * Globals. */ @@ -174,11 +196,6 @@ static bool symlist; /* -s: output symbol static bool symdepth; /* -S: output symbol depth */ static bool text; /* -t: this is a text file */ -static const char *symname[MAXSYMS]; /* symbol name */ -static const char *value[MAXSYMS]; /* -Dsym=value */ -static bool ignore[MAXSYMS]; /* -iDsym or -iUsym */ -static int nsyms; /* number of symbols */ - static FILE *input; /* input file pointer */ static const char *filename; /* input file name */ static int linenum; /* current line number */ @@ -227,12 +244,12 @@ static char *astrcat(const char *, const ch static void cleantemp(void); static void closeio(void); static void debug(const char *, ...); -static void debugsym(const char *, int); +static void debugsym(const char *, const struct macro *); static bool defundef(void); static void defundefile(const char *); static void done(void); static void error(const char *); -static int findsym(const char **); +static struct macro *findsym(const char **); static void flushline(bool); static void hashline(void); static void help(void); @@ -807,7 +824,7 @@ static Linetype parseline(void) { const char *cp; - int cursym; + struct macro *cursym; Linetype retval; Comment_state wascomment; @@ -829,15 +846,15 @@ parseline(void) if ((cp = matchsym("ifdef", keyword)) != NULL || (cp = matchsym("ifndef", keyword)) != NULL) { cp = skipcomment(cp); - if ((cursym = findsym(&cp)) < 0) + if ((cursym = findsym(&cp)) == NULL) retval = LT_IF; else { retval = (keyword[2] == 'n') ? LT_FALSE : LT_TRUE; - if (value[cursym] == NULL) + if (cursym->value == NULL) retval = (retval == LT_TRUE) ? LT_FALSE : LT_TRUE; - if (ignore[cursym]) + if (cursym->ignore) retval = (retval == LT_TRUE) ? LT_TRUEI : LT_FALSEI; } @@ -1037,7 +1054,7 @@ eval_unary(const struct ops *ops, long *valp, const ch { const char *cp; char *ep; - int sym; + struct macro *sym; bool defparen; Linetype lt; @@ -1102,27 +1119,27 @@ eval_unary(const struct ops *ops, long *valp, const ch debug("eval%d defined missing ')'", prec(ops)); return (LT_ERROR); } - if (sym < 0) { + if (sym == NULL) { debug("eval%d defined unknown", prec(ops)); lt = LT_IF; } else { - debug("eval%d defined %s", prec(ops), symname[sym]); - *valp = (value[sym] != NULL); + debug("eval%d defined %s", prec(ops), sym->name); + *valp = (sym->value != NULL); lt = *valp ? LT_TRUE : LT_FALSE; } constexpr = false; } else if (!endsym(*cp)) { debug("eval%d symbol", prec(ops)); sym = findsym(&cp); - if (sym < 0) { + if (sym == NULL) { lt = LT_IF; cp = skipargs(cp); - } else if (value[sym] == NULL) { + } else if (sym->value == NULL) { *valp = 0; lt = LT_FALSE; } else { - *valp = strtol(value[sym], &ep, 0); - if (*ep != '\0' || ep == value[sym]) + *valp = strtol(sym->value, &ep, 0); + if (*ep != '\0' || ep == sym->value) return (LT_ERROR); lt = *valp ? LT_TRUE : LT_FALSE; cp = skipargs(cp); @@ -1439,17 +1456,18 @@ matchsym(const char *s, const char *t) * Look for the symbol in the symbol table. If it is found, we return * the symbol table index, else we return -1. */ -static int +static struct macro * findsym(const char **strp) { const char *str; - int symind; + char *strkey; + struct macro key, *res; str = *strp; *strp = skipsym(str); if (symlist) { if (*strp == str) - return (-1); + return (NULL); if (symdepth && firstsym) printf("%s%3d", zerosyms ? "" : "\n", depth); firstsym = zerosyms = false; @@ -1458,15 +1476,26 @@ findsym(const char **strp) (int)(*strp-str), str, symdepth ? "" : "\n"); /* we don't care about the value of the symbol */ - return (0); + return (NULL); } - for (symind = 0; symind < nsyms; ++symind) { - if (matchsym(symname[symind], str) != NULL) { - debugsym("findsym", symind); - return (symind); - } - } - return (-1); + + /* + * 'str' just points into the current mid-parse input and is not + * nul-terminated. We know the length of the symbol, *strp - str, but + * need to provide a nul-terminated lookup key for RB_FIND's comparison + * function. Create one here. + */ + strkey = malloc(*strp - str + 1); + memcpy(strkey, str, *strp - str); + strkey[*strp - str] = 0; + + key.name = strkey; + res = RB_FIND(MACROMAP, ¯o_tree, &key); + if (res != NULL) + debugsym("findsym", res); + + free(strkey); + return (res); } /* @@ -1476,22 +1505,23 @@ static void indirectsym(void) { const char *cp; - int changed, sym, ind; + int changed; + struct macro *sym, *ind; do { changed = 0; - for (sym = 0; sym < nsyms; ++sym) { - if (value[sym] == NULL) + RB_FOREACH(sym, MACROMAP, ¯o_tree) { + if (sym->value == NULL) continue; - cp = value[sym]; + cp = sym->value; ind = findsym(&cp); - if (ind == -1 || ind == sym || + if (ind == NULL || ind == sym || *cp != '\0' || - value[ind] == NULL || - value[ind] == value[sym]) + ind->value == NULL || + ind->value == sym->value) continue; debugsym("indir...", sym); - value[sym] = value[ind]; + sym->value = ind->value; debugsym("...ectsym", sym); changed++; } @@ -1523,29 +1553,29 @@ addsym1(bool ignorethis, bool definethis, char *symval * Add a symbol to the symbol table. */ static void -addsym2(bool ignorethis, const char *sym, const char *val) +addsym2(bool ignorethis, const char *symname, const char *val) { - const char *cp = sym; - int symind; + const char *cp = symname; + struct macro *sym, *r; - symind = findsym(&cp); - if (symind < 0) { - if (nsyms >= MAXSYMS) - errx(2, "too many symbols"); - symind = nsyms++; + sym = findsym(&cp); + if (sym == NULL) { + sym = calloc(1, sizeof(*sym)); + sym->ignore = ignorethis; + sym->name = symname; + sym->value = val; + r = RB_INSERT(MACROMAP, ¯o_tree, sym); + assert(r == NULL); } - ignore[symind] = ignorethis; - symname[symind] = sym; - value[symind] = val; - debugsym("addsym", symind); + debugsym("addsym", sym); } static void -debugsym(const char *why, int symind) +debugsym(const char *why, const struct macro *sym) { - debug("%s %s%c%s", why, symname[symind], - value[symind] ? '=' : ' ', - value[symind] ? value[symind] : "undef"); + debug("%s %s%c%s", why, sym->name, + sym->value ? '=' : ' ', + sym->value ? sym->value : "undef"); } /*