From 6527b03dcc029cf9edb7bf7dbaeab420092e04c9 Mon Sep 17 00:00:00 2001 From: Szabolcs Nagy Date: Wed, 30 Jul 2014 19:02:08 +0200 Subject: plural rule evaluator rewrite for dcngettext using an operator precedence parser the code size became smaller and it is only slower by about %10 size of old vs new pleval.o on different archs: (with inlined isspace added to pleval.c for now) old: text data bss dec hex filename 828 0 0 828 33c pl.i386.o 1152 0 0 1152 480 pl.arm.o 1704 0 0 1704 6a8 pl.mips.o 1328 0 0 1328 530 pl.ppc.o 992 0 0 992 3e0 pl.x64.o new: text data bss dec hex filename 693 0 0 693 2b5 pl.i386.o 972 0 0 972 3cc pl.arm.o 1276 0 0 1276 4fc pl.mips.o 1087 0 0 1087 43f pl.ppc.o 846 0 0 846 34e pl.x64.o --- src/locale/pleval.c | 234 ++++++++++++++++++++++++---------------------------- 1 file changed, 106 insertions(+), 128 deletions(-) (limited to 'src/locale') diff --git a/src/locale/pleval.c b/src/locale/pleval.c index 03370bcf..961dabc0 100644 --- a/src/locale/pleval.c +++ b/src/locale/pleval.c @@ -11,177 +11,155 @@ And = Eq | And '&&' Eq Eq = Rel | Eq '==' Rel | Eq '!=' Rel Rel = Add | Rel '<=' Add | Rel '>=' Add | Rel '<' Add | Rel '>' Add Add = Mul | Add '+' Mul | Add '-' Mul -Mul = Term | Mul '*' Term | Mul '/' Term | Mul '%' Term -Term = '(' Expr ')' | '!' Term | decimal | 'n' +Mul = Prim | Mul '*' Prim | Mul '/' Prim | Mul '%' Prim +Prim = '(' Expr ')' | '!' Prim | decimal | 'n' internals: recursive descent expression evaluator with stack depth limit. -eval* functions return the value of the subexpression and set -the current string pointer to the next non-space char. +for binary operators an operator-precedence parser is used. +eval* functions store the result of the parsed subexpression +and return a pointer to the next non-space character. */ struct st { - const char *s; + unsigned long r; unsigned long n; - int err; + int op; }; -static const char *skipspace(const char *s) +/* TODO: this should go into ctypes.h */ +#undef isspace +#define isspace(a) __isspace(a) +static __inline int __isspace(int _c) { - while (isspace(*s)) s++; - return s; + return _c == ' ' || (unsigned)_c-'\t' < 5; } -static unsigned long fail(struct st *st) +static const char *skipspace(const char *s) { - st->err = 1; - return 0; + while (isspace(*s)) s++; + return s; } -static unsigned long evalexpr(struct st *st, int d); +static const char *evalexpr(struct st *st, const char *s, int d); -static unsigned long evalterm(struct st *st, int d) +static const char *evalprim(struct st *st, const char *s, int d) { - unsigned long a; char *e; - if (--d < 0) return fail(st); - st->s = skipspace(st->s); - if (isdigit(*st->s)) { - a = strtoul(st->s, &e, 10); - if (e == st->s || a == -1) return fail(st); - st->s = skipspace(e); - return a; - } - if (*st->s == 'n') { - st->s = skipspace(st->s + 1); - return st->n; + if (--d < 0) return ""; + s = skipspace(s); + if (isdigit(*s)) { + st->r = strtoul(s, &e, 10); + if (e == s || st->r == -1) return ""; + return skipspace(e); } - if (*st->s == '(') { - st->s++; - a = evalexpr(st, d); - if (*st->s != ')') return fail(st); - st->s = skipspace(st->s + 1); - return a; + if (*s == 'n') { + st->r = st->n; + return skipspace(s+1); } - if (*st->s == '!') { - st->s++; - return !evalterm(st, d); + if (*s == '(') { + s = evalexpr(st, s+1, d); + if (*s != ')') return ""; + return skipspace(s+1); } - return fail(st); -} - -static unsigned long evalmul(struct st *st, int d) -{ - unsigned long b, a = evalterm(st, d); - int op; - for (;;) { - op = *st->s; - if (op != '*' && op != '/' && op != '%') - return a; - st->s++; - b = evalterm(st, d); - if (op == '*') { - a *= b; - } else if (!b) { - return fail(st); - } else if (op == '%') { - a %= b; - } else { - a /= b; - } + if (*s == '!') { + s = evalprim(st, s+1, d); + st->r = !st->r; + return s; } + return ""; } -static unsigned long evaladd(struct st *st, int d) +static int binop(struct st *st, int op, unsigned long left) { - unsigned long a = 0; - int sub = 0; - for (;;) { - a += (sub ? -1 : 1) * evalmul(st, d); - if (*st->s != '+' && *st->s != '-') - return a; - sub = *st->s == '-'; - st->s++; + unsigned long a = left, b = st->r; + switch (op) { + case 0: st->r = a||b; return 0; + case 1: st->r = a&&b; return 0; + case 2: st->r = a==b; return 0; + case 3: st->r = a!=b; return 0; + case 4: st->r = a>=b; return 0; + case 5: st->r = a<=b; return 0; + case 6: st->r = a>b; return 0; + case 7: st->r = ar = a+b; return 0; + case 9: st->r = a-b; return 0; + case 10: st->r = a*b; return 0; + case 11: if (b) {st->r = a%b; return 0;} return 1; + case 12: if (b) {st->r = a/b; return 0;} return 1; } + return 1; } -static unsigned long evalrel(struct st *st, int d) +static const char *parseop(struct st *st, const char *s) { - unsigned long b, a = evaladd(st, d); - int less, eq; - for (;;) { - if (*st->s != '<' && *st->s != '>') - return a; - less = st->s[0] == '<'; - eq = st->s[1] == '='; - st->s += 1 + eq; - b = evaladd(st, d); - a = (less ? a < b : a > b) || (eq && a == b); - } -} - -static unsigned long evaleq(struct st *st, int d) -{ - unsigned long a = evalrel(st, d); - int c; - for (;;) { - c = st->s[0]; - if ((c != '=' && c != '!') || st->s[1] != '=') - return a; - st->s += 2; - a = (evalrel(st, d) == a) ^ (c == '!'); - } -} - -static unsigned long evaland(struct st *st, int d) -{ - unsigned long a = evaleq(st, d); - for (;;) { - if (st->s[0] != '&' || st->s[1] != '&') - return a; - st->s += 2; - a = evaleq(st, d) && a; - } + static const char opch[11] = "|&=!><+-*%/"; + static const char opch2[6] = "|&===="; + int i; + for (i=0; i<11; i++) + if (*s == opch[i]) { + /* note: >,< are accepted with or without = */ + if (i<6 && s[1] == opch2[i]) { + st->op = i; + return s+2; + } + if (i>=4) { + st->op = i+2; + return s+1; + } + break; + } + st->op = 13; + return s; } -static unsigned long evalor(struct st *st, int d) +static const char *evalbinop(struct st *st, const char *s, int minprec, int d) { - unsigned long a = evaland(st, d); + static const char prec[14] = {1,2,3,3,4,4,4,4,5,5,6,6,6,0}; + unsigned long left; + int op; + d--; + s = evalprim(st, s, d); + s = parseop(st, s); for (;;) { - if (st->s[0] != '|' || st->s[1] != '|') - return a; - st->s += 2; - a = evaland(st, d) || a; + /* + st->r (left hand side value) and st->op are now set, + get the right hand side or back out if op has low prec, + if op was missing then prec[op]==0 + */ + op = st->op; + if (prec[op] <= minprec) + return s; + left = st->r; + s = evalbinop(st, s, prec[op], d); + if (binop(st, op, left)) + return ""; } } -static unsigned long evalexpr(struct st *st, int d) +static const char *evalexpr(struct st *st, const char *s, int d) { - unsigned long a1, a2, a3; + unsigned long a, b; if (--d < 0) - return fail(st); - a1 = evalor(st, d-6); - if (*st->s != '?') - return a1; - st->s++; - a2 = evalexpr(st, d); - if (*st->s != ':') - return fail(st); - st->s++; - a3 = evalexpr(st, d); - return a1 ? a2 : a3; + return ""; + s = evalbinop(st, s, 0, d); + if (*s != '?') + return s; + a = st->r; + s = evalexpr(st, s+1, d); + if (*s != ':') + return ""; + b = st->r; + s = evalexpr(st, s+1, d); + st->r = a ? b : st->r; + return s; } unsigned long __pleval(const char *s, unsigned long n) { - unsigned long a; struct st st; - st.s = s; st.n = n; - st.err = 0; - a = evalexpr(&st, 100); - if (st.err || *st.s != ';') - return -1; - return a; + s = evalexpr(&st, s, 100); + return *s == ';' ? st.r : -1; } -- cgit v1.2.1