/*
- * arithmetic code ripped out of ash shell for code sharing
+ * Arithmetic code ripped out of ash shell for code sharing.
*
* This code is derived from software contributed to Berkeley by
* Kenneth Almquist.
* Licensed under GPLv2 or later, see file LICENSE in this source tree.
*/
/* Copyright (c) 2001 Aaron Lehmann <aaronl@vitelus.com>
-
- Permission is hereby granted, free of charge, to any person obtaining
- a copy of this software and associated documentation files (the
- "Software"), to deal in the Software without restriction, including
- without limitation the rights to use, copy, modify, merge, publish,
- distribute, sublicense, and/or sell copies of the Software, and to
- permit persons to whom the Software is furnished to do so, subject to
- the following conditions:
-
- The above copyright notice and this permission notice shall be
- included in all copies or substantial portions of the Software.
-
- THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
- EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
- MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
- IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
- CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
- TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
- SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
-*/
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+ * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+ * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
+ * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
+ * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ */
/* This is my infix parser/evaluator. It is optimized for size, intended
* as a replacement for yacc-based parsers. However, it may well be faster
* this is based (this code differs in that it applies operators immediately
* to the stack instead of adding them to a queue to end up with an
* expression).
- *
- * To use the routine, call it with an expression string and error return
- * pointer
*/
/*
#define fix_assignment_prec(prec) do { if (prec == 3) prec = 2; } while (0)
-/* ternary conditional operator is right associative too */
+/* Ternary conditional operator is right associative too */
#define TOK_CONDITIONAL tok_decl(4,0)
#define TOK_CONDITIONAL_SEP tok_decl(4,1)
#define TOK_DIV tok_decl(14,1)
#define TOK_REM tok_decl(14,2)
-/* exponent is right associative */
+/* Exponent is right associative */
#define TOK_EXPONENT tok_decl(15,1)
-/* unary operators */
+/* Unary operators */
#define UNARYPREC 16
#define TOK_BNOT tok_decl(UNARYPREC,0)
#define TOK_NOT tok_decl(UNARYPREC,1)
#define TOK_RPAREN tok_decl(SPEC_PREC, 1)
static int
-tok_have_assign(operator op)
+is_assign_op(operator op)
{
operator prec = PREC(op);
-
fix_assignment_prec(prec);
- return (prec == PREC(TOK_ASSIGN) ||
- prec == PREC_PRE || prec == PREC_POST);
+ return prec == PREC(TOK_ASSIGN)
+ || prec == PREC_PRE
+ || prec == PREC_POST;
}
static int
is_right_associative(operator prec)
{
- return (prec == PREC(TOK_ASSIGN) || prec == PREC(TOK_EXPONENT)
- || prec == PREC(TOK_CONDITIONAL));
+ return prec == PREC(TOK_ASSIGN)
+ || prec == PREC(TOK_EXPONENT)
+ || prec == PREC(TOK_CONDITIONAL);
}
+
typedef struct {
arith_t val;
- arith_t contidional_second_val;
- char contidional_second_val_initialized;
- char *var; /* if NULL then is regular number,
- else is variable name */
-} v_n_t;
-
-typedef struct chk_var_recursive_looped_t {
+ /* We acquire second_val only when "expr1 : expr2" part
+ * of ternary ?: op is evaluated.
+ * We treat ?: as two binary ops: (expr ? (expr1 : expr2)).
+ * ':' produces a new value which has two parts, val and second_val;
+ * then '?' selects one of them based on its left side.
+ */
+ arith_t second_val;
+ char second_val_present;
+ /* If NULL then it's just a number, else it's a named variable */
+ char *var;
+} var_or_num_t;
+
+typedef struct remembered_name {
+ struct remembered_name *next;
const char *var;
- struct chk_var_recursive_looped_t *next;
-} chk_var_recursive_looped_t;
+} remembered_name;
-static chk_var_recursive_looped_t *prev_chk_var_recursive;
-static int
-arith_lookup_val(arith_state_t *math_state, v_n_t *t)
+static arith_t FAST_FUNC
+evaluate_string(arith_state_t *math_state, const char *expr);
+
+static const char*
+arith_lookup_val(arith_state_t *math_state, var_or_num_t *t)
{
if (t->var) {
const char *p = lookupvar(t->var);
-
if (p) {
- chk_var_recursive_looped_t *cur;
- chk_var_recursive_looped_t cur_save;
-
- /* recursively try p as expression */
+ remembered_name *cur;
+ remembered_name cur_save;
- for (cur = prev_chk_var_recursive; cur; cur = cur->next) {
+ /* did we already see this name?
+ * testcase: a=b; b=a; echo $((a))
+ */
+ for (cur = math_state->list_of_recursed_names; cur; cur = cur->next) {
if (strcmp(cur->var, t->var) == 0) {
- /* expression recursion loop detected */
- return -5;
+ /* Yes */
+ return "expression recursion loop detected";
}
}
- /* save current var name */
- cur = prev_chk_var_recursive;
+
+ /* push current var name */
+ cur = math_state->list_of_recursed_names;
cur_save.var = t->var;
cur_save.next = cur;
- prev_chk_var_recursive = &cur_save;
+ math_state->list_of_recursed_names = &cur_save;
+
+ /* recursively evaluate p as expression */
+ t->val = evaluate_string(math_state, p);
+
+ /* pop current var name */
+ math_state->list_of_recursed_names = cur;
- t->val = arith(math_state, p);
- /* restore previous ptr after recursion */
- prev_chk_var_recursive = cur;
- return math_state->errcode;
+ return math_state->errmsg;
}
- /* allow undefined var as 0 */
+ /* treat undefined var as 0 */
t->val = 0;
}
return 0;
/* "Applying" a token means performing it on the top elements on the integer
* stack. For an unary operator it will only change the top element, but a
* binary operator will pop two arguments and push the result */
-static NOINLINE int
-arith_apply(arith_state_t *math_state, operator op, v_n_t *numstack, v_n_t **numstackptr)
+static NOINLINE const char*
+arith_apply(arith_state_t *math_state, operator op, var_or_num_t *numstack, var_or_num_t **numstackptr)
{
#define NUMPTR (*numstackptr)
- v_n_t *numptr_m1;
- arith_t numptr_val, rez;
- int err;
+ var_or_num_t *top_of_stack;
+ arith_t rez;
+ const char *err;
/* There is no operator that can work without arguments */
if (NUMPTR == numstack)
goto err;
- numptr_m1 = NUMPTR - 1;
- /* Check operand is var with noninteger value */
- err = arith_lookup_val(math_state, numptr_m1);
+ top_of_stack = NUMPTR - 1;
+
+ /* Resolve name to value, if needed */
+ err = arith_lookup_val(math_state, top_of_stack);
if (err)
return err;
- rez = numptr_m1->val;
+ rez = top_of_stack->val;
if (op == TOK_UMINUS)
- rez *= -1;
+ rez = -rez;
else if (op == TOK_NOT)
rez = !rez;
else if (op == TOK_BNOT)
rez--;
else if (op != TOK_UPLUS) {
/* Binary operators */
+ arith_t right_side_val;
+ char bad_second_val;
- /* check and binary operators need two arguments */
- if (numptr_m1 == numstack) goto err;
-
- /* ... and they pop one */
- --NUMPTR;
- numptr_val = rez;
- if (op == TOK_CONDITIONAL) {
- if (!numptr_m1->contidional_second_val_initialized) {
- /* protect $((expr1 ? expr2)) without ": expr" */
- goto err;
- }
- rez = numptr_m1->contidional_second_val;
- } else if (numptr_m1->contidional_second_val_initialized) {
- /* protect $((expr1 : expr2)) without "expr ? " */
+ /* Binary operators need two arguments */
+ if (top_of_stack == numstack)
goto err;
+ /* ...and they pop one */
+ NUMPTR = top_of_stack; /* this decrements NUMPTR */
+
+ bad_second_val = top_of_stack->second_val_present;
+ if (op == TOK_CONDITIONAL) { /* ? operation */
+ /* Make next if (...) protect against
+ * $((expr1 ? expr2)) - that is, missing ": expr" */
+ bad_second_val = !bad_second_val;
+ }
+ if (bad_second_val) {
+ /* Protect against $((expr <not_?_op> expr1 : expr2)) */
+ return "malformed ?: operator";
}
- numptr_m1 = NUMPTR - 1;
+
+ top_of_stack--; /* now points to left side */
+
if (op != TOK_ASSIGN) {
- /* check operand is var with noninteger value for not '=' */
- err = arith_lookup_val(math_state, numptr_m1);
+ /* Resolve left side value (unless the op is '=') */
+ err = arith_lookup_val(math_state, top_of_stack);
if (err)
return err;
}
- if (op == TOK_CONDITIONAL) {
- numptr_m1->contidional_second_val = rez;
+
+ right_side_val = rez;
+ rez = top_of_stack->val;
+ if (op == TOK_CONDITIONAL) /* ? operation */
+ rez = (rez ? right_side_val : top_of_stack[1].second_val);
+ else if (op == TOK_CONDITIONAL_SEP) { /* : operation */
+ if (top_of_stack == numstack) {
+ /* Protect against $((expr : expr)) */
+ return "malformed ?: operator";
+ }
+ top_of_stack->second_val_present = op;
+ top_of_stack->second_val = right_side_val;
}
- rez = numptr_m1->val;
- if (op == TOK_BOR || op == TOK_OR_ASSIGN)
- rez |= numptr_val;
+ else if (op == TOK_BOR || op == TOK_OR_ASSIGN)
+ rez |= right_side_val;
else if (op == TOK_OR)
- rez = numptr_val || rez;
+ rez = right_side_val || rez;
else if (op == TOK_BAND || op == TOK_AND_ASSIGN)
- rez &= numptr_val;
+ rez &= right_side_val;
else if (op == TOK_BXOR || op == TOK_XOR_ASSIGN)
- rez ^= numptr_val;
+ rez ^= right_side_val;
else if (op == TOK_AND)
- rez = rez && numptr_val;
+ rez = rez && right_side_val;
else if (op == TOK_EQ)
- rez = (rez == numptr_val);
+ rez = (rez == right_side_val);
else if (op == TOK_NE)
- rez = (rez != numptr_val);
+ rez = (rez != right_side_val);
else if (op == TOK_GE)
- rez = (rez >= numptr_val);
+ rez = (rez >= right_side_val);
else if (op == TOK_RSHIFT || op == TOK_RSHIFT_ASSIGN)
- rez >>= numptr_val;
+ rez >>= right_side_val;
else if (op == TOK_LSHIFT || op == TOK_LSHIFT_ASSIGN)
- rez <<= numptr_val;
+ rez <<= right_side_val;
else if (op == TOK_GT)
- rez = (rez > numptr_val);
+ rez = (rez > right_side_val);
else if (op == TOK_LT)
- rez = (rez < numptr_val);
+ rez = (rez < right_side_val);
else if (op == TOK_LE)
- rez = (rez <= numptr_val);
+ rez = (rez <= right_side_val);
else if (op == TOK_MUL || op == TOK_MUL_ASSIGN)
- rez *= numptr_val;
+ rez *= right_side_val;
else if (op == TOK_ADD || op == TOK_PLUS_ASSIGN)
- rez += numptr_val;
+ rez += right_side_val;
else if (op == TOK_SUB || op == TOK_MINUS_ASSIGN)
- rez -= numptr_val;
+ rez -= right_side_val;
else if (op == TOK_ASSIGN || op == TOK_COMMA)
- rez = numptr_val;
- else if (op == TOK_CONDITIONAL_SEP) {
- if (numptr_m1 == numstack) {
- /* protect $((expr : expr)) without "expr ? " */
- goto err;
- }
- numptr_m1->contidional_second_val_initialized = op;
- numptr_m1->contidional_second_val = numptr_val;
- } else if (op == TOK_CONDITIONAL) {
- rez = rez ?
- numptr_val : numptr_m1->contidional_second_val;
- } else if (op == TOK_EXPONENT) {
+ rez = right_side_val;
+ else if (op == TOK_EXPONENT) {
arith_t c;
- if (numptr_val < 0)
- return -3; /* exponent less than 0 */
+ if (right_side_val < 0)
+ return "exponent less than 0";
c = 1;
- while (--numptr_val >= 0)
- c *= rez;
+ while (--right_side_val >= 0)
+ c *= rez;
rez = c;
- } else if (numptr_val==0) /* zero divisor check */
- return -2;
- else if (op == TOK_DIV || op == TOK_DIV_ASSIGN)
- rez /= numptr_val;
- else if (op == TOK_REM || op == TOK_REM_ASSIGN)
- rez %= numptr_val;
+ }
+ else if (right_side_val == 0)
+ return "divide by zero";
+ else if (op == TOK_DIV || op == TOK_DIV_ASSIGN
+ || op == TOK_REM || op == TOK_REM_ASSIGN) {
+ /*
+ * bash 4.2.45 x86 64bit: SEGV on 'echo $((2**63 / -1))'
+ *
+ * MAX_NEGATIVE_INT / -1 = MAX_POSITIVE_INT+1
+ * and thus is not representable.
+ * Some CPUs segfault trying such op.
+ * Others overflow MAX_POSITIVE_INT+1 to
+ * MAX_NEGATIVE_INT (0x7fff+1 = 0x8000).
+ * Make sure to at least not SEGV here:
+ */
+ if (right_side_val == -1
+ && rez << 1 == 0 /* MAX_NEGATIVE_INT or 0 */
+ ) {
+ right_side_val = 1;
+ }
+ if (op == TOK_DIV || op == TOK_DIV_ASSIGN)
+ rez /= right_side_val;
+ else {
+ rez %= right_side_val;
+ }
+ }
}
- if (tok_have_assign(op)) {
+
+ if (is_assign_op(op)) {
char buf[sizeof(arith_t)*3 + 2];
- if (numptr_m1->var == NULL) {
+ if (top_of_stack->var == NULL) {
/* Hmm, 1=2 ? */
+//TODO: actually, bash allows ++7 but for some reason it evals to 7, not 8
goto err;
}
- /* save to shell variable */
- sprintf(buf, arith_t_fmt, rez);
- setvar(numptr_m1->var, buf);
- /* after saving, make previous value for v++ or v-- */
+ /* Save to shell variable */
+ sprintf(buf, ARITH_FMT, rez);
+ setvar(top_of_stack->var, buf);
+ /* After saving, make previous value for v++ or v-- */
if (op == TOK_POST_INC)
rez--;
else if (op == TOK_POST_DEC)
rez++;
}
- numptr_m1->val = rez;
- /* erase var name, it is just a number now */
- numptr_m1->var = NULL;
- return 0;
+
+ top_of_stack->val = rez;
+ /* Erase var name, it is just a number now */
+ top_of_stack->var = NULL;
+ return NULL;
err:
- return -1;
+ return "arithmetic syntax error";
#undef NUMPTR
}
};
#define ptr_to_rparen (&op_tokens[sizeof(op_tokens)-7])
-const char* FAST_FUNC
-endofname(const char *name)
-{
- if (!is_name(*name))
- return name;
- while (*++name) {
- if (!is_in_name(*name))
- break;
- }
- return name;
-}
-
-arith_t
-arith(arith_state_t *math_state, const char *expr)
+static arith_t FAST_FUNC
+evaluate_string(arith_state_t *math_state, const char *expr)
{
operator lasttok;
- int errcode;
+ const char *errmsg;
const char *start_expr = expr = skip_whitespace(expr);
unsigned expr_len = strlen(expr) + 2;
/* Stack of integers */
- /* The proof that there can be no more than strlen(startbuf)/2+1 integers
- * in any given correct or incorrect expression is left as an exercise to
- * the reader. */
- v_n_t *const numstack = alloca((expr_len / 2) * sizeof(numstack[0]));
- v_n_t *numstackptr = numstack;
+ /* The proof that there can be no more than strlen(startbuf)/2+1
+ * integers in any given correct or incorrect expression
+ * is left as an exercise to the reader. */
+ var_or_num_t *const numstack = alloca((expr_len / 2) * sizeof(numstack[0]));
+ var_or_num_t *numstackptr = numstack;
/* Stack of operator tokens */
operator *const stack = alloca(expr_len * sizeof(stack[0]));
operator *stackptr = stack;
- *stackptr++ = lasttok = TOK_LPAREN; /* start off with a left paren */
- errcode = 0;
+ /* Start with a left paren */
+ *stackptr++ = lasttok = TOK_LPAREN;
+ errmsg = NULL;
while (1) {
const char *p;
arithval = *expr;
if (arithval == '\0') {
if (expr == start_expr) {
- /* Null expression. */
+ /* Null expression */
numstack->val = 0;
goto ret;
}
}
if (numstack->var) {
/* expression is $((var)) only, lookup now */
- errcode = arith_lookup_val(math_state, numstack);
+ errmsg = arith_lookup_val(math_state, numstack);
}
goto ret;
}
safe_strncpy(numstackptr->var, expr, var_name_size);
expr = p;
num:
- numstackptr->contidional_second_val_initialized = 0;
+ numstackptr->second_val_present = 0;
numstackptr++;
lasttok = TOK_NUM;
continue;
/* Should be an operator */
p = op_tokens;
while (1) {
- const char *e = expr;
+// TODO: bash allows 7+++v, treats it as 7 + ++v
+// we treat it as 7++ + v and reject
/* Compare expr to current op_tokens[] element */
- while (*p && *e == *p)
- p++, e++;
- if (*p == '\0') { /* match: operator is found */
- expr = e;
- break;
+ const char *e = expr;
+ while (1) {
+ if (*p == '\0') {
+ /* Match: operator is found */
+ expr = e;
+ goto tok_found;
+ }
+ if (*p != *e)
+ break;
+ p++;
+ e++;
}
- /* Go to next element of op_tokens[] */
+ /* No match, go to next element of op_tokens[] */
while (*p)
p++;
p += 2; /* skip NUL and TOK_foo bytes */
- if (*p == '\0') /* no next element, operator not found */
+ if (*p == '\0') {
+ /* No next element, operator not found */
+ //math_state->syntax_error_at = expr;
goto err;
+ }
}
+ tok_found:
op = p[1]; /* fetch TOK_foo value */
/* NB: expr now points past the operator */
* integer stack.
* But for binary operators, "apply" everything on the operator
* stack until we find an operator with a lesser priority than the
- * one we have just extracted.
+ * one we have just extracted. If op is right-associative,
+ * then stop "applying" on the equal priority too.
* Left paren is given the lowest priority so it will never be
* "applied" in this way.
- * if associativity is right and priority eq, applied also skip
*/
prec = PREC(op);
if ((prec > 0 && prec < UNARYPREC) || prec == SPEC_PREC) {
break;
}
}
- errcode = arith_apply(math_state, prev_op, numstack, &numstackptr);
- if (errcode)
- goto ret;
+ errmsg = arith_apply(math_state, prev_op, numstack, &numstackptr);
+ if (errmsg)
+ goto err_with_custom_msg;
}
- if (op == TOK_RPAREN) {
+ if (op == TOK_RPAREN)
goto err;
- }
}
- /* Push this operator to the stack and remember it. */
+ /* Push this operator to the stack and remember it */
*stackptr++ = lasttok = op;
next: ;
} /* while (1) */
err:
- numstack->val = errcode = -1;
+ errmsg = "arithmetic syntax error";
+ err_with_custom_msg:
+ numstack->val = -1;
ret:
- math_state->errcode = errcode;
+ math_state->errmsg = errmsg;
return numstack->val;
}
+arith_t FAST_FUNC
+arith(arith_state_t *math_state, const char *expr)
+{
+ math_state->errmsg = NULL;
+ math_state->list_of_recursed_names = NULL;
+ return evaluate_string(math_state, expr);
+}
+
/*
* Copyright (c) 1989, 1991, 1993, 1994
* The Regents of the University of California. All rights reserved.
projects / oweals / busybox.git / blobdiff