The former implementation was not correct regarding whiteouts in
?: conditional branches. The new one also parses a bit better, in
effect on equal level than bash with its recursive descendent parser.
---
v3 of the patch that includes all the fixes that were
unfortunately necessary. Now hopefully a hundred percent correct.
It adds a FEATURE_SH_MATH_ERROR_TRACK configuration option, and
hides most compatibility shims behind a request macro. Size:
Current busybox implementation (incorrect)
2938 0 0 2938 b7a math.o
With/out ERROR_TRACK
4889 0 0 4889 1319 shell/math.o
5039 0 0 5039 13af shell/math.o
It surely could be shrinked a bit by removing compatibility shims
and fitting neatlessly in busybox. But it grows quite a bit...
When i run the test (i will post the new positive one as a reply;
the negative one exists for my mailer, but since sh(1) will just
bail out for each and every test, it is a bit hard to do) there
remains the very same difference to the very first version
i posted, namely
#?0|kent:tmp$ diff- tg.mx tg.busy
--- tg.mx 2022-08-19 18:24:05.427687786 +0200
+++ tg.busy 2022-08-19 18:23:02.411022307 +0200
@@ -9,7 +9,7 @@
<1>
<1>
<1>
-<9223372036854775807>
+<0>
<10>
<9191919191919>
<13>
which comes due to
e "<$((999999999999999999999999999999999999999999999))>"
I have not touched the busybox way of parsing integers.
When i compare the test run from tg.mx and bash i still see
#?0|kent:tmp$ bash tarith-good.in > tg.bash
tarith-good.in: line 284: 1>>>1: syntax error: operand expected (error token
is ">1")
tarith-good.in: line 285: 1 >>> 1 : syntax error: operand expected (error
token is "> 1 ")
tarith-good.in: line 288: 1111>>>2222: syntax error: operand expected (error
token is ">2222")
tarith-good.in: line 289: 2222>>>1111: syntax error: operand expected (error
token is ">1111")
tarith-good.in: line 293: -0x10 >>> -0x11 : syntax error: operand expected
(error token is "> -0x11 ")
tarith-good.in: line 312: 0xFFFFFFFFFFFFFFFF>>>11: syntax error: operand
expected (error token is ">11")
tarith-good.in: line 657: I**=1: syntax error: operand expected (error token
is "=1")
tarith-good.in: line 658: I**=2: syntax error: operand expected (error token
is "=2")
tarith-good.in: line 659: I**=1+1: syntax error: operand expected (error
token is "=1+1")
tarith-good.in: line 665: I>>>=1: syntax error: operand expected (error token
is ">=1")
tarith-good.in: line 888: +10++I: syntax error in expression (error token is
"++I")
because bash does not support unsigned right shift, exponent-
assignment, and it cannot (read: does not want to!) parse "+10++I"
(it can parse "+10++11"). If i leave out these missing tests the
diff boils down to
@@ -9,7 +10,7 @@
<1>
<1>
<1>
-<9223372036854775807>
+<802379605485813759>
<10>
<9191919191919>
<13>
aka the same thing as above. (bash simply walks on decoding the
integer not looking out for overflow, says it's expr.c.)
So given how bad the Dijkstra algorithm fits into anything other
than unary and binary calculations, i think it still comes out as
an acceptible piece of code, and i hope you like it.
Sorry for all the noise in this thread.
Ciao.
shell/Config.src | 8 +
shell/ash.c | 6 +-
shell/hush.c | 23 +-
shell/math.c | 710 +++---------------------
shell/math.h | 7 +-
shell/shexp-arith.h | 1288 +++++++++++++++++++++++++++++++++++++++++++
6 files changed, 1406 insertions(+), 636 deletions(-)
create mode 100644 shell/shexp-arith.h
diff --git a/shell/Config.src b/shell/Config.src
index 5efbf99959..32aaab58e8 100644
--- a/shell/Config.src
+++ b/shell/Config.src
@@ -108,6 +108,14 @@ config FEATURE_SH_MATH_BASE
default y
depends on FEATURE_SH_MATH
+config FEATURE_SH_MATH_ERROR_TRACK
+ bool "Extend POSIX math support with error location tracking"
+ default y
+ depends on FEATURE_SH_MATH
+ help
+ Enable error location tracking in the shell's math support.
+ Without it only the type of error will be logged.
+
config FEATURE_SH_EXTRA_QUIET
bool "Hide message on interactive shell startup"
default y
diff --git a/shell/ash.c b/shell/ash.c
index 55c1034f55..4029a3c04f 100644
--- a/shell/ash.c
+++ b/shell/ash.c
@@ -6029,8 +6029,12 @@ ash_arith(const char *s)
INT_OFF;
result = arith(&math_state, s);
- if (math_state.errmsg)
+ if (math_state.errmsg) {
ash_msg_and_raise_error(math_state.errmsg);
+# if ENABLE_FEATURE_SH_MATH_ERROR_TRACK
+ free(math_state.errmsg);
+# endif
+ }
INT_ON;
return result;
diff --git a/shell/hush.c b/shell/hush.c
index 051b123e78..be01ed035c 100644
--- a/shell/hush.c
+++ b/shell/hush.c
@@ -6475,7 +6475,7 @@ static NOINLINE int
encode_then_append_var_plusminus(o_string *output, int n,
}
#if ENABLE_FEATURE_SH_MATH
-static arith_t expand_and_evaluate_arith(const char *arg, const char
**errmsg_p)
+static arith_t expand_and_evaluate_arith(const char *arg, char **errmsg_p)
{
arith_state_t math_state;
arith_t res;
@@ -6489,8 +6489,13 @@ static arith_t expand_and_evaluate_arith(const char
*arg, const char **errmsg_p)
free(exp_str);
if (errmsg_p)
*errmsg_p = math_state.errmsg;
- if (math_state.errmsg)
+ if (math_state.errmsg) {
msg_and_die_if_script(math_state.errmsg);
+# if ENABLE_FEATURE_SH_MATH_ERROR_TRACK
+ if (errmsg_p == NULL)
+ free(math_state.errmsg);
+# endif
+ }
return res;
}
#endif
@@ -6814,11 +6819,15 @@ static NOINLINE int expand_one_var(o_string *output,
int n,
*/
arith_t beg, len;
unsigned vallen;
- const char *errmsg;
+ char *errmsg;
beg = expand_and_evaluate_arith(exp_word, &errmsg);
- if (errmsg)
+ if (errmsg) {
+# if ENABLE_FEATURE_SH_MATH_ERROR_TRACK
+ free(errmsg);
+# endif
goto empty_result;
+ }
debug_printf_varexp("beg:'%s'=%lld\n", exp_word, (long
long)beg);
*p++ = SPECIAL_VAR_SYMBOL;
exp_word = p;
@@ -6838,8 +6847,12 @@ static NOINLINE int expand_one_var(o_string *output, int
n,
goto empty_result;
}
len = expand_and_evaluate_arith(exp_word, &errmsg);
- if (errmsg)
+ if (errmsg) {
+# if ENABLE_FEATURE_SH_MATH_ERROR_TRACK
+ free(errmsg);
+# endif
goto empty_result;
+ }
debug_printf_varexp("len:'%s'=%lld\n", exp_word, (long
long)len);
debug_printf_varexp("from val:'%s'\n", val);
if (len < 0) {
diff --git a/shell/math.c b/shell/math.c
index 76d22c9bd5..b9b3d7acb1 100644
--- a/shell/math.c
+++ b/shell/math.c
@@ -116,398 +116,6 @@
#include "libbb.h"
#include "math.h"
-typedef unsigned char operator;
-
-/* An operator's token id is a bit of a bitfield. The lower 5 bits are the
- * precedence, and 3 high bits are an ID unique across operators of that
- * precedence. The ID portion is so that multiple operators can have the
- * same precedence, ensuring that the leftmost one is evaluated first.
- * Consider * and /
- */
-#define tok_decl(prec,id) (((id)<<5) | (prec))
-#define PREC(op) ((op) & 0x1F)
-
-#define TOK_LPAREN tok_decl(0,0)
-
-#define TOK_COMMA tok_decl(1,0)
-
-/* All assignments are right associative and have the same precedence,
- * but there are 11 of them, which doesn't fit into 3 bits for unique id.
- * Abusing another precedence level:
- */
-#define TOK_ASSIGN tok_decl(2,0)
-#define TOK_AND_ASSIGN tok_decl(2,1)
-#define TOK_OR_ASSIGN tok_decl(2,2)
-#define TOK_XOR_ASSIGN tok_decl(2,3)
-#define TOK_PLUS_ASSIGN tok_decl(2,4)
-#define TOK_MINUS_ASSIGN tok_decl(2,5)
-#define TOK_LSHIFT_ASSIGN tok_decl(2,6)
-#define TOK_RSHIFT_ASSIGN tok_decl(2,7)
-
-#define TOK_MUL_ASSIGN tok_decl(3,0)
-#define TOK_DIV_ASSIGN tok_decl(3,1)
-#define TOK_REM_ASSIGN tok_decl(3,2)
-
-#define fix_assignment_prec(prec) do { if (prec == 3) prec = 2; } while (0)
-
-/* Ternary conditional operator is right associative too */
-#define TOK_CONDITIONAL tok_decl(4,0)
-#define TOK_CONDITIONAL_SEP tok_decl(4,1)
-
-#define TOK_OR tok_decl(5,0)
-
-#define TOK_AND tok_decl(6,0)
-
-#define TOK_BOR tok_decl(7,0)
-
-#define TOK_BXOR tok_decl(8,0)
-
-#define TOK_BAND tok_decl(9,0)
-
-#define TOK_EQ tok_decl(10,0)
-#define TOK_NE tok_decl(10,1)
-
-#define TOK_LT tok_decl(11,0)
-#define TOK_GT tok_decl(11,1)
-#define TOK_GE tok_decl(11,2)
-#define TOK_LE tok_decl(11,3)
-
-#define TOK_LSHIFT tok_decl(12,0)
-#define TOK_RSHIFT tok_decl(12,1)
-
-#define TOK_ADD tok_decl(13,0)
-#define TOK_SUB tok_decl(13,1)
-
-#define TOK_MUL tok_decl(14,0)
-#define TOK_DIV tok_decl(14,1)
-#define TOK_REM tok_decl(14,2)
-
-/* Exponent is right associative */
-#define TOK_EXPONENT tok_decl(15,1)
-
-/* Unary operators */
-#define UNARYPREC 16
-#define TOK_BNOT tok_decl(UNARYPREC,0)
-#define TOK_NOT tok_decl(UNARYPREC,1)
-
-#define TOK_UMINUS tok_decl(UNARYPREC+1,0)
-#define TOK_UPLUS tok_decl(UNARYPREC+1,1)
-
-#define PREC_PRE (UNARYPREC+2)
-
-#define TOK_PRE_INC tok_decl(PREC_PRE, 0)
-#define TOK_PRE_DEC tok_decl(PREC_PRE, 1)
-
-#define PREC_POST (UNARYPREC+3)
-
-#define TOK_POST_INC tok_decl(PREC_POST, 0)
-#define TOK_POST_DEC tok_decl(PREC_POST, 1)
-
-#define SPEC_PREC (UNARYPREC+4)
-
-#define TOK_NUM tok_decl(SPEC_PREC, 0)
-#define TOK_RPAREN tok_decl(SPEC_PREC, 1)
-
-static int
-is_assign_op(operator op)
-{
- operator prec = PREC(op);
- fix_assignment_prec(prec);
- 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);
-}
-
-
-typedef struct {
- arith_t val;
- /* 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;
-} remembered_name;
-
-
-static arith_t
-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 = math_state->lookupvar(t->var);
- if (p) {
- remembered_name *cur;
- remembered_name cur_save;
-
- /* 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) {
- /* Yes */
- return "expression recursion loop
detected";
- }
- }
-
- /* push current var name */
- cur = math_state->list_of_recursed_names;
- cur_save.var = t->var;
- cur_save.next = cur;
- 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;
-
- return math_state->errmsg;
- }
- /* 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 const char*
-arith_apply(arith_state_t *math_state, operator op, var_or_num_t *numstack,
var_or_num_t **numstackptr)
-{
-#define NUMPTR (*numstackptr)
-
- 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;
-
- 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 = top_of_stack->val;
- if (op == TOK_UMINUS)
- rez = -rez;
- else if (op == TOK_NOT)
- rez = !rez;
- else if (op == TOK_BNOT)
- rez = ~rez;
- else if (op == TOK_POST_INC || op == TOK_PRE_INC)
- rez++;
- else if (op == TOK_POST_DEC || op == TOK_PRE_DEC)
- rez--;
- else if (op != TOK_UPLUS) {
- /* Binary operators */
- arith_t right_side_val;
- char bad_second_val;
-
- /* 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";
- }
-
- top_of_stack--; /* now points to left side */
-
- if (op != TOK_ASSIGN) {
- /* Resolve left side value (unless the op is '=') */
- err = arith_lookup_val(math_state, top_of_stack);
- if (err)
- return err;
- }
-
- 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;
- }
- else if (op == TOK_BOR || op == TOK_OR_ASSIGN)
- rez |= right_side_val;
- else if (op == TOK_OR)
- rez = right_side_val || rez;
- else if (op == TOK_BAND || op == TOK_AND_ASSIGN)
- rez &= right_side_val;
- else if (op == TOK_BXOR || op == TOK_XOR_ASSIGN)
- rez ^= right_side_val;
- else if (op == TOK_AND)
- rez = rez && right_side_val;
- else if (op == TOK_EQ)
- rez = (rez == right_side_val);
- else if (op == TOK_NE)
- rez = (rez != right_side_val);
- else if (op == TOK_GE)
- rez = (rez >= right_side_val);
- else if (op == TOK_RSHIFT || op == TOK_RSHIFT_ASSIGN)
- rez >>= right_side_val;
- else if (op == TOK_LSHIFT || op == TOK_LSHIFT_ASSIGN)
- rez <<= right_side_val;
- else if (op == TOK_GT)
- rez = (rez > right_side_val);
- else if (op == TOK_LT)
- rez = (rez < right_side_val);
- else if (op == TOK_LE)
- rez = (rez <= right_side_val);
- else if (op == TOK_MUL || op == TOK_MUL_ASSIGN)
- rez *= right_side_val;
- else if (op == TOK_ADD || op == TOK_PLUS_ASSIGN)
- rez += right_side_val;
- else if (op == TOK_SUB || op == TOK_MINUS_ASSIGN)
- rez -= right_side_val;
- else if (op == TOK_ASSIGN || op == TOK_COMMA)
- rez = right_side_val;
- else if (op == TOK_EXPONENT) {
- arith_t c;
- if (right_side_val < 0)
- return "exponent less than 0";
- c = 1;
- while (--right_side_val >= 0)
- c *= rez;
- rez = c;
- }
- 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 (is_assign_op(op)) {
- char buf[sizeof(arith_t)*3 + 2];
-
- if (top_of_stack->var == NULL) {
- /* Hmm, 1=2 ? */
- goto err;
- }
- /* Save to shell variable */
- sprintf(buf, ARITH_FMT, rez);
- math_state->setvar(top_of_stack->var, buf);
- /* After saving, make previous value for v++ or v-- */
- if (op == TOK_POST_INC)
- rez--;
- if (op == TOK_POST_DEC)
- rez++;
- }
-
- top_of_stack->val = rez;
- /* Erase var name, it is just a number now */
- top_of_stack->var = NULL;
- return NULL;
- err:
- return "arithmetic syntax error";
-#undef NUMPTR
-}
-
-/* longest must be first */
-static const char op_tokens[] ALIGN1 = {
- '<','<','=',0, TOK_LSHIFT_ASSIGN,
- '>','>','=',0, TOK_RSHIFT_ASSIGN,
- '<','<', 0, TOK_LSHIFT,
- '>','>', 0, TOK_RSHIFT,
- '|','|', 0, TOK_OR,
- '&','&', 0, TOK_AND,
- '!','=', 0, TOK_NE,
- '<','=', 0, TOK_LE,
- '>','=', 0, TOK_GE,
- '=','=', 0, TOK_EQ,
- '|','=', 0, TOK_OR_ASSIGN,
- '&','=', 0, TOK_AND_ASSIGN,
- '*','=', 0, TOK_MUL_ASSIGN,
- '/','=', 0, TOK_DIV_ASSIGN,
- '%','=', 0, TOK_REM_ASSIGN,
- '+','=', 0, TOK_PLUS_ASSIGN,
- '-','=', 0, TOK_MINUS_ASSIGN,
- '-','-', 0, TOK_POST_DEC,
- '^','=', 0, TOK_XOR_ASSIGN,
- '+','+', 0, TOK_POST_INC,
- '*','*', 0, TOK_EXPONENT,
- '!', 0, TOK_NOT,
- '<', 0, TOK_LT,
- '>', 0, TOK_GT,
- '=', 0, TOK_ASSIGN,
- '|', 0, TOK_BOR,
- '&', 0, TOK_BAND,
- '*', 0, TOK_MUL,
- '/', 0, TOK_DIV,
- '%', 0, TOK_REM,
- '+', 0, TOK_ADD,
- '-', 0, TOK_SUB,
- '^', 0, TOK_BXOR,
- /* uniq */
- '~', 0, TOK_BNOT,
- ',', 0, TOK_COMMA,
- '?', 0, TOK_CONDITIONAL,
- ':', 0, TOK_CONDITIONAL_SEP,
- ')', 0, TOK_RPAREN,
- '(', 0, TOK_LPAREN,
- 0
-};
-#define ptr_to_rparen (&op_tokens[sizeof(op_tokens)-7])
-
#if ENABLE_FEATURE_SH_MATH_BASE
static arith_t strto_arith_t(const char *nptr, char **endptr)
{
@@ -577,250 +185,96 @@ static arith_t strto_arith_t(const char *nptr, char
**endptr)
# endif
#endif
-static arith_t
-evaluate_string(arith_state_t *math_state, const char *expr)
-{
- operator lasttok;
- 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. */
- 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;
-
- /* Start with a left paren */
- *stackptr++ = lasttok = TOK_LPAREN;
- errmsg = NULL;
-
- while (1) {
- const char *p;
- operator op;
- operator prec;
-
- expr = skip_whitespace(expr);
- if (*expr == '\0') {
- if (expr == start_expr) {
- /* Null expression */
- numstack->val = 0;
- goto ret;
- }
-
- /* This is only reached after all tokens have been
extracted from the
- * input stream. If there are still tokens on the
operator stack, they
- * are to be applied in order. At the end, there should
be a final
- * result on the integer stack */
-
- if (expr != ptr_to_rparen + 1) {
- /* If we haven't done so already,
- * append a closing right paren
- * and let the loop process it */
- expr = ptr_to_rparen;
-//bb_error_msg("expr=')'");
- continue;
- }
- /* At this point, we're done with the expression */
- if (numstackptr != numstack + 1) {
- /* ...but if there isn't, it's bad */
- goto err;
- }
- goto ret;
- }
-
- p = endofname(expr);
- if (p != expr) {
- /* Name */
- size_t var_name_size = (p - expr) + 1; /* +1 for NUL */
- numstackptr->var = alloca(var_name_size);
- safe_strncpy(numstackptr->var, expr, var_name_size);
-//bb_error_msg("var:'%s'", numstackptr->var);
- expr = p;
- num:
- numstackptr->second_val_present = 0;
- numstackptr++;
- lasttok = TOK_NUM;
- continue;
- }
-
- if (isdigit(*expr)) {
- /* Number */
- numstackptr->var = NULL;
- errno = 0;
- numstackptr->val = strto_arith_t(expr, (char**) &expr);
-//bb_error_msg("val:%lld", numstackptr->val);
- if (errno)
- numstackptr->val = 0; /* bash compat */
- goto num;
- }
-
- /* Should be an operator */
-
- /* Special case: XYZ--, XYZ++, --XYZ, ++XYZ are recognized
- * only if XYZ is a variable name, not a number or EXPR. IOW:
- * "a+++v" is a++ + v.
- * "(a)+++7" is ( a ) + + + 7.
- * "7+++v" is 7 + ++v, not 7++ + v.
- * "--7" is - - 7, not --7.
- * "++++a" is + + ++a, not ++ ++a.
- */
- if ((expr[0] == '+' || expr[0] == '-')
- && (expr[1] == expr[0])
- ) {
- if (numstackptr == numstack || !numstackptr[-1].var) {
/* not a VAR++ */
- char next = skip_whitespace(expr + 2)[0];
- if (!(isalpha(next) || next == '_')) { /* not a
++VAR */
- //bb_error_msg("special %c%c", expr[0],
expr[0]);
- op = (expr[0] == '+' ? TOK_ADD :
TOK_SUB);
- expr++;
- goto tok_found1;
- }
- }
- }
-
- p = op_tokens;
- while (1) {
- /* Compare expr to current op_tokens[] element */
- const char *e = expr;
- while (1) {
- if (*p == '\0') {
- /* Match: operator is found */
- expr = e;
- goto tok_found;
- }
- if (*p != *e)
- break;
- p++;
- e++;
- }
- /* 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 */
- //math_state->syntax_error_at = expr;
- goto err;
- }
- }
- tok_found:
- op = p[1]; /* fetch TOK_foo value */
- tok_found1:
- /* NB: expr now points past the operator */
-
- /* post grammar: a++ reduce to num */
- if (lasttok == TOK_POST_INC || lasttok == TOK_POST_DEC)
- lasttok = TOK_NUM;
-
- /* Plus and minus are binary (not unary) _only_ if the last
- * token was a number, or a right paren (which pretends to be
- * a number, since it evaluates to one). Think about it.
- * It makes sense. */
- if (lasttok != TOK_NUM) {
- switch (op) {
- case TOK_ADD:
- op = TOK_UPLUS;
- break;
- case TOK_SUB:
- op = TOK_UMINUS;
- break;
- case TOK_POST_INC:
- op = TOK_PRE_INC;
- break;
- case TOK_POST_DEC:
- op = TOK_PRE_DEC;
- break;
- }
- }
- /* We don't want an unary operator to cause recursive descent
on the
- * stack, because there can be many in a row and it could cause
an
- * operator to be evaluated before its argument is pushed onto
the
- * 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. 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.
- */
- prec = PREC(op);
-//bb_error_msg("prec:%02x", prec);
- if ((prec > 0 && prec < UNARYPREC) || prec == SPEC_PREC) {
- /* not left paren or unary */
- if (lasttok != TOK_NUM) {
- /* binary op must be preceded by a num */
- goto err;
- }
- /* The algorithm employed here is simple: while we don't
- * hit an open paren nor the bottom of the stack, pop
- * tokens and apply them */
- while (stackptr != stack) {
- operator prev_op = *--stackptr;
- if (op == TOK_RPAREN) {
-//bb_error_msg("op == TOK_RPAREN");
- if (prev_op == TOK_LPAREN) {
-//bb_error_msg("prev_op == TOK_LPAREN");
-//bb_error_msg(" %p %p numstackptr[-1].var:'%s'", numstack, numstackptr-1,
numstackptr[-1].var);
- if (numstackptr[-1].var) {
- /* Expression is (var),
lookup now */
- errmsg =
arith_lookup_val(math_state, &numstackptr[-1]);
- if (errmsg)
- goto
err_with_custom_msg;
- /* Erase var name:
(var) is just a number, for example, (var) = 1 is not valid */
- numstackptr[-1].var =
NULL;
- }
- /* Any operator directly after a
- * close paren should consider
itself binary */
- lasttok = TOK_NUM;
- goto next;
- }
-//bb_error_msg("prev_op != TOK_LPAREN");
- } else {
- operator prev_prec = PREC(prev_op);
-//bb_error_msg("op != TOK_RPAREN");
- fix_assignment_prec(prec);
- fix_assignment_prec(prev_prec);
- if (prev_prec < prec
- || (prev_prec == prec &&
is_right_associative(prec))
- ) {
- stackptr++;
- break;
- }
- }
-//bb_error_msg("arith_apply(prev_op:%02x)", prev_op);
- errmsg = arith_apply(math_state, prev_op,
numstack, &numstackptr);
- if (errmsg)
- goto err_with_custom_msg;
- }
- if (op == TOK_RPAREN)
- goto err;
- }
+#define a_SHEXP_ARITH_COMPAT_SHIMS
+# define s64 arith_t
+# if ENABLE_FEATURE_SH_MATH_64
+# define S64_MIN LLONG_MIN
+# define u64 unsigned long long
+# else
+# define S64_MIN LONG_MIN
+# define u64 unsigned long
+# endif
+# define savestr(X) xstrdup(X)
+# define su_IDEC_STATE_EMASK (1u<<0)
+# define su_IDEC_STATE_CONSUMED (1u<<1)
+#define a_SHEXP_ARITH_COOKIE arith_state_t *
+#if ENABLE_FEATURE_SH_MATH_ERROR_TRACK
+# define a_SHEXP_ARITH_ERROR_TRACK
+#endif
- /* Push this operator to the stack and remember it */
-//bb_error_msg("push op:%02x", op);
- *stackptr++ = lasttok = op;
- next: ;
- } /* while (1) */
+#define su_ienc_s64(X,Y,Z) (sprintf(X, ARITH_FMT, Y), X)
+#define n_var_vlook(X,Y) (*self->sac_cookie->lookupvar)(X)
+#define n_var_vset(X,Y,Z) (*self->sac_cookie->setvar)(X, (char*)(Y))
+#define su_idec_cp(A,B,C,D,E) a_idec_x(A, B, E)
+
+static inline uint32_t a_idec_x(void *resp, char const *cbuf,
+ char const **endptr_or_nil){
+ uint32_t rv;
+ arith_t res;
+ char const *eptr;
+
+ if(endptr_or_nil == NULL)
+ endptr_or_nil = &eptr;
+
+ errno = 0;
+ res = strto_arith_t(cbuf, (char**)endptr_or_nil);
+ rv = 0;
+ if(errno == 0){
+ if(**endptr_or_nil == '\0')
+ rv = su_IDEC_STATE_CONSUMED;
+ }else{
+ rv = su_IDEC_STATE_EMASK;
+ res = 0;
+ }
- err:
- errmsg = "arithmetic syntax error";
- err_with_custom_msg:
- numstack->val = -1;
- ret:
- math_state->errmsg = errmsg;
- return numstack->val;
+ *(arith_t*)resp = res;
+ return rv;
}
+#include "shexp-arith.h"
+
arith_t FAST_FUNC
arith(arith_state_t *math_state, const char *expr)
{
+#if ENABLE_FEATURE_SH_MATH_ERROR_TRACK
+ char *err_rest;
+#endif
+ char const *emsg;
+ s64 res;
+
math_state->errmsg = NULL;
- math_state->list_of_recursed_names = NULL;
- return evaluate_string(math_state, expr);
+
+ switch(a_shexp_arith_eval(math_state, &res, expr, UZ_MAX
+#if ENABLE_FEATURE_SH_MATH_ERROR_TRACK
+ , &err_rest
+#endif
+ )){
+ default:
+ return res;
+#undef a_X
+#define a_X(X,N) case CONCAT(a_SHEXP_ARITH_ERR_,X): emsg = N_(N); break
+ a_X(NOMEM, "out of memory");
+ a_X(SYNTAX, "syntax error");
+ a_X(ASSIGN_NO_VAR, "assignment without variable");
+ a_X(DIV_BY_ZERO, "division by zero");
+ a_X(EXP_INVALID, "invalid exponent");
+ a_X(NO_OP, "syntax error, expected operand");
+ a_X(COND_NO_COLON, "syntax error, incomplete ?: condition");
+ a_X(COND_PREC_INVALID, "?: condition, invalid precedence (1:v2:v3=3)");
+ a_X(NAME_LOOP, "recursive variable name reference");
+ a_X(OP_INVALID, "unknown operator");
+ }
+#undef a_X
+
+ math_state->errmsg =
+#if ENABLE_FEATURE_SH_MATH_ERROR_TRACK
+ xasprintf("%s (rest: %s)", emsg, err_rest);
+#else
+ emsg
+#endif
+ ;
+
+ return -1;
}
/*
diff --git a/shell/math.h b/shell/math.h
index 41ef6e8dfa..4bb8d5cdfa 100644
--- a/shell/math.h
+++ b/shell/math.h
@@ -76,11 +76,14 @@ typedef void FAST_FUNC (*arith_var_set_t)(const char
*name, const char *v
//typedef const char* FAST_FUNC (*arith_var_endofname_t)(const char *name);
typedef struct arith_state_t {
- const char *errmsg;
+ /* ENABLE_FEATURE_SH_MATH_ERROR_TRACK: must be free(3)d if !NULL */
+#if !ENABLE_FEATURE_SH_MATH_ERROR_TRACK
+ const
+#endif
+ char *errmsg;
arith_var_lookup_t lookupvar;
arith_var_set_t setvar;
// arith_var_endofname_t endofname;
- void *list_of_recursed_names;
} arith_state_t;
arith_t FAST_FUNC arith(arith_state_t *state, const char *expr);
diff --git a/shell/shexp-arith.h b/shell/shexp-arith.h
new file mode 100644
index 0000000000..bc2ca52784
--- /dev/null
+++ b/shell/shexp-arith.h
@@ -0,0 +1,1288 @@
+/*@ S-nail - a mail user agent derived from Berkeley Mail.
+ *@ Signed 64-bit sh(1)ell-style $(( ARITH ))metic expression evaluator.
+ *@ POW2 bases are parsed as unsigned, operation overflow -> limit constant(s),
+ *@ saturated mode is not supported, division by zero is handled via error.
+ *@ The expression length limit is ~100.000.000 on 32-bit, U32_MAX otherwise.
+ *@ After reading on Dijkstra's two stack algorithm, as well as bash:expr.c.
+ *@ Most heavily inspired by busybox -- conclusion: the Dijkstra algorithm
+ *@ scales very badly to ternary as are used to implement conditionals and
+ *@ their ignored sub-expressions.
+ *@
+ *@ #define's:
+ *@ - a_SHEXP_ARITH_COMPAT_SHIMS: for inclusion in other code bases, setting
+ *@ this defines most necessary compat macros.
+ *@ We still need s64, u64, S64_MIN, savestr(CP) <> strdup(3) that does not
+ *@ return NIL (only with _ERROR_TRACK). Plus stdint.h, ctype.h, string.h.
+ *@ We need su_idec_cp(), su_ienc_s64(), n_var_vlook() and n_var_vset().
+ *@ We need su_IDEC_STATE_EMASK (= 1) and su_IDEC_STATE_CONSUMED (= 2), e.g.:
+ *@ errno = 0;
+ *@ res = strto_arith_t(cbuf, (char**)endptr_or_nil);
+ *@ rv = 0;
+ *@ if(errno == 0){
+ *@ if(**endptr_or_nil == '\0')
+ *@ rv = su_IDEC_STATE_CONSUMED;
+ *@ }else{
+ *@ rv = su_IDEC_STATE_EMASK;
+ *@ res = 0;
+ *@ }
+ *@ *S(s64*,resp) = res;
+ *@ - a_SHEXP_ARITH_COOKIE: adds struct a_shexp_arith_ctx:sac_cookie, and
+ *@ a cookie arg to a_shexp_arith_eval().
+ *@ - a_SHEXP_ARITH_ERROR_TRACK: add "char **error_track_or_nil" to
+ *@ a_shexp_arith_eval(), and according error stack handling, so that users
+ *@ can be given hint where an error occurred. ("Three stack algorithm.")
+ *
+ * Copyright (c) 2022 Steffen Nurpmeso <stef...@sdaoden.eu>.
+ * SPDX-License-Identifier: ISC
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+/* Tracking of error location in input */
+#ifdef a_SHEXP_ARITH_ERROR_TRACK
+# undef a_SHEXP_ARITH_ERROR_TRACK
+# define a_SHEXP_ARITH_ERROR_TRACK(X) X
+#else
+# define a_SHEXP_ARITH_ERROR_TRACK(X)
+#endif
+
+/* IFS whitespace removal */
+#undef a_SHEXP_ARITH_IFS
+#ifdef mx_SOURCE
+# define a_SHEXP_ARITH_IFS(X) X
+#else
+# define a_SHEXP_ARITH_IFS(X)
+#endif
+
+/* (Most necessary) Compat shims */
+#ifdef a_SHEXP_ARITH_COMPAT_SHIMS
+# define boole bool
+# define FAL0 false
+# define TRU1 true
+# define u8 uint8_t
+# define u16 uint16_t
+# define u32 uint32_t
+# define U32_MAX UINT32_MAX
+# define ul unsigned long
+# define up uintptr_t
+# define UZ_MAX SIZE_MAX
+# define uz size_t
+# define a_SHEXP_ISVARC(C) ((C) == '_' || isalnum(S(unsigned char,C)))
+# define a_SHEXP_ISVARC_BAD1ST(C) su_cs_is_digit(C)
+# define a_SHEXP_ISVARC_BADNST(C) FAL0
+# define ASSERT(X)
+# define ASSERT_NYD_EXEC(X,Y)
+# define BITENUM_IS(X,Y) X
+# define CONCAT(S1,S2) su__CONCAT_1(S1, S2)
+# define su__CONCAT_1(S1,S2) su__CONCAT_2(S1, S2)
+# define su__CONCAT_2(S1,S2) S1 ## S2
+# define DBGX(X)
+# define FALLTHRU
+# define N_(X) X
+# define NIL NULL
+# define NYD_IN S(void,0)
+# define NYD2_IN S(void,0)
+# define NYD_OU S(void,0)
+# define NYD2_OU S(void,0)
+# define P2UZ(X) S(size_t,X)
+# define S(X,Y) ((X)(Y))
+# define su_ALIGNOF(X) ((sizeof(X) + 15) & ~15)
+# define su_COMMA ,
+# define su_cs_cmp(X,Y) strcmp(X, Y)
+# define su_cs_is_digit(X) isdigit(S(unsigned char,X))
+# define su_cs_is_space(X) isspace(S(unsigned char,X))
+# define su_empty ""
+# define su_IDEC_STATE_EBASE 0 /* (could cause $CC optimiz.) */
+# define su_IENC_BUFFER_SIZE 80u
+# define su_LOFI_ALLOC(X) alloca(X)
+# define su_LOFI_FREE(X)
+# define su_mem_move(X,Y,Z) memmove(X, Y, Z)
+# define STRUCT_ZERO(X,Y) memset(Y, 0, sizeof(X))
+# define UNLIKELY(X) X
+# define UNUSED(X) S(void,X)
+# if LONG_MAX - 1 > 0x7FFFFFFFl - 1
+# define su_64(X) X
+# else
+# define su_64(X)
+# endif
+#endif /* a_SHEXP_ARITH_COMPAT_SHIMS */
+
+/* -- >8 -- 8< -- */
+
+#if 1
+# define a_SHEXP_ARITH_DBG 0
+# define a_SHEXP_ARITH_L(X)
+#else
+# define a_SHEXP_ARITH_DBG 1
+# define a_SHEXP_ARITH_L(X) a_shexp__arith_log X
+#endif
+
+/* We parse with base 0: set _RESCAN to allow "I=' -10';$((10#$I))" */
+#define a_SHEXP_ARITH_IDEC_MODE (su_IDEC_MODE_SIGNED_TYPE |\
+ su_IDEC_MODE_POW2BASE_UNSIGNED | su_IDEC_MODE_LIMIT_NOERROR |\
+ su_IDEC_MODE_BASE0_NUMBER_SIGN_RESCAN)
+
+enum a_shexp_arith_error{
+ a_SHEXP_ARITH_ERR_NONE,
+ a_SHEXP_ARITH_ERR_NOMEM, /* Out of memory */
+ a_SHEXP_ARITH_ERR_SYNTAX, /* General syntax error */
+ a_SHEXP_ARITH_ERR_ASSIGN_NO_VAR, /* Assignment without variable */
+ a_SHEXP_ARITH_ERR_DIV_BY_ZERO,
+ a_SHEXP_ARITH_ERR_EXP_INVALID, /* Invalid exponent */
+ a_SHEXP_ARITH_ERR_NO_OP, /* Expected an argument here */
+ a_SHEXP_ARITH_ERR_COND_NO_COLON, /* Incomplete ?: condition */
+ a_SHEXP_ARITH_ERR_COND_PREC_INVALID, /* 1 ? VAR1 : VAR2 = 3 */
+ a_SHEXP_ARITH_ERR_NAME_LOOP, /* Variable self-reference loop */
+ a_SHEXP_ARITH_ERR_OP_INVALID /* Unknown operator */
+};
+
+/* Operators and precedences in increasing precedence order.
+ * (The operator stack as such is u16: [OP_FLAGS |] (OP<<8) | PREC.) */
+enum a_shexp_arith_ops{
+#undef a_X
+#define a_X(N,P,O) \
+ CONCAT(a_SHEXP_ARITH_PREC_,N) = CONCAT(P,u),\
+ CONCAT(a_SHEXP_ARITH_OP_,N) =\
+ (CONCAT(O,u) << 8) | CONCAT(a_SHEXP_ARITH_PREC_,N)
+
+ a_X(PAREN_LEFT, 0, 0),
+
+ a_X(COMMA, 1, 0),
+
+ a_X(ASSIGN, 2, 0),
+ a_X(ASSIGN_BIT_OR, 2, 1),
+ a_X(ASSIGN_BIT_XOR, 2, 2),
+ a_X(ASSIGN_BIT_AND, 2, 3),
+ a_X(ASSIGN_SHIFT_LEFT, 2, 4), a_X(ASSIGN_SHIFT_RIGHT, 2, 5),
+ a_X(ASSIGN_SHIFT_RIGHTU, 2, 6),
+ a_X(ASSIGN_ADD, 2, 7), a_X(ASSIGN_SUB, 2, 8),
+ a_X(ASSIGN_MUL, 2, 9), a_X(ASSIGN_DIV, 2, 10), a_X(ASSIGN_MOD, 2, 11),
+ a_X(ASSIGN_EXP, 2, 12),
+
+ a_X(COND, 3, 0),
+ a_X(COND_COLON, 3, 1),
+
+ a_X(OR, 4, 0),
+ a_X(AND, 5, 0),
+ a_X(BIT_OR, 6, 0),
+ a_X(BIT_XOR, 7, 0),
+ a_X(BIT_AND, 8, 0),
+ a_X(EQ, 9, 0), a_X(NE, 9, 1),
+ a_X(LE, 10, 0), a_X(GE, 10, 1), a_X(LT, 10, 2), a_X(GT, 10, 3),
+ a_X(SHIFT_LEFT, 11, 0), a_X(SHIFT_RIGHT, 11, 1), a_X(SHIFT_RIGHTU, 11, 2),
+ a_X(ADD, 12, 0), a_X(SUB, 12, 1),
+ a_X(MUL, 13, 0), a_X(DIV, 13, 1), a_X(MOD, 13, 2),
+ a_X(EXP, 14, 0),
+
+ /* Further operators are unary, pre- or postfix */
+ a_SHEXP_ARITH_PREC_UNARY = 15,
+ a_SHEXP_ARITH_PREC_PREFIX = 16,
+ a_SHEXP_ARITH_PREC_POSTFIX = 18,
+
+ a_X(UNARY_NOT, 15, 0), a_X(UNARY_BIT_NOT, 15, 1),
+ a_X(PREFIX_INC, 16, 0), a_X(PREFIX_DEC, 16, 1),
+ a_X(UNARY_PLUS, 17, 1), a_X(UNARY_MINUS, 17, 0),
+ a_X(POSTFIX_INC, 18, 0), a_X(POSTFIX_DEC, 18, 1),
+
+ /* Beyond operator profanity; the first "is a number" */
+ a_SHEXP_ARITH_PREC_SKY = 19,
+ a_X(NUM, 19, 0), a_X(PAREN_RIGHT, 19, 1),
+
+#undef a_X
+};
+
+enum arith_op_flags{
+ /* Mask off operator and precision */
+ a_SHEXP_ARITH_OP_MASK = 0x1FFF,
+ a_SHEXP_ARITH_OP_FLAG_COND_SAW_COLON = 1u<<13,
+ a_SHEXP_ARITH_OP_FLAG_OUTER_WHITEOUT = 1u<<14,
+ a_SHEXP_ARITH_OP_FLAG_WHITEOUT = 1u<<15,
+ a_SHEXP_ARITH_OP_FLAG_WHITE_MASK = a_SHEXP_ARITH_OP_FLAG_OUTER_WHITEOUT |
+ a_SHEXP_ARITH_OP_FLAG_WHITEOUT,
+ a_SHEXP_ARITH_OP_FLAG_MASK = a_SHEXP_ARITH_OP_FLAG_COND_SAW_COLON |
+ a_SHEXP_ARITH_OP_FLAG_WHITE_MASK
+};
+
+struct a_shexp_arith_name_stack{
+ struct a_shexp_arith_name_stack *sans_last;
+ char const *sans_var;
+};
+
+struct a_shexp_arith_val{
+ s64 sav_val;
+ char *sav_var; /* Named variable or NIL */
+};
+
+struct a_shexp_arith_stack{
+ struct a_shexp_arith_val *sas_nums;
+ struct a_shexp_arith_val *sas_nums_top;
+ u16 *sas_ops;
+ u16 *sas_ops_top;
+ a_SHEXP_ARITH_ERROR_TRACK(
+ char **sas_error_track;
+ char **sas_error_track_top;
+ )
+};
+
+struct a_shexp_arith_ctx{
+ enum a_shexp_arith_error sac_error;
+ boole sac_have_error_track;
+ u8 sac__pad[3];
+ s64 sac_rv;
+ struct a_shexp_arith_stack *sac_stack;
+ struct a_shexp_arith_name_stack *sac_name_stack;
+ a_SHEXP_ARITH_ERROR_TRACK( char **sac_error_track_or_nil; )
+ a_SHEXP_ARITH_IFS( char const *sac_ifs_ws; )
+#ifdef a_SHEXP_ARITH_COOKIE
+ a_SHEXP_ARITH_COOKIE sac_cookie;
+#endif
+};
+
+/* Sort by ~expected usage -- however, longest first if ambiguous!
+ * Follow busybox, save space by compressing data in char[] not struct[]!
+ * (XXX Instead use 1-st byte jump table like for commands) */
+static char const a_shexp_arith_op_toks[] = {
+#undef a_X
+#define a_X(X) \
+ S(char,(CONCAT(a_SHEXP_ARITH_OP_,X) & 0xFF00u) >> 8),\
+ S(char,CONCAT(a_SHEXP_ARITH_PREC_,X))
+
+ '+','+','\0', a_X(POSTFIX_INC),
+ '+','=','\0', a_X(ASSIGN_ADD),
+ '+','\0', a_X(ADD),
+ '-','-','\0', a_X(POSTFIX_DEC),
+ '-','=','\0', a_X(ASSIGN_SUB),
+ '-','\0', a_X(SUB),
+ '*','*','=','\0', a_X(ASSIGN_EXP),
+ '*','*','\0', a_X(EXP),
+ '*','=','\0', a_X(ASSIGN_MUL),
+ '*','\0', a_X(MUL),
+ '/','=','\0', a_X(ASSIGN_DIV),
+ '/','\0', a_X(DIV),
+ '%','=','\0', a_X(ASSIGN_MOD),
+ '%','\0', a_X(MOD),
+ '|','|','\0', a_X(OR),
+ '|','=','\0', a_X(ASSIGN_BIT_OR),
+ '|','\0', a_X(BIT_OR),
+ '^','=','\0', a_X(ASSIGN_BIT_XOR),
+ '^','\0', a_X(BIT_XOR),
+ '&','&','\0', a_X(AND),
+ '&','=','\0', a_X(ASSIGN_BIT_AND),
+ '&','\0', a_X(BIT_AND),
+ '<','<','=',0, a_X(ASSIGN_SHIFT_LEFT),
+ '<','<','\0', a_X(SHIFT_LEFT),
+ '>','>','>','=',0, a_X(ASSIGN_SHIFT_RIGHTU),
+ '>','>','>','\0', a_X(SHIFT_RIGHTU),
+ '>','>','=',0, a_X(ASSIGN_SHIFT_RIGHT),
+ '>','>','\0', a_X(SHIFT_RIGHT),
+
+ '~','\0', a_X(UNARY_BIT_NOT),
+ '!','=','\0', a_X(NE),
+ '!','\0', a_X(UNARY_NOT),
+
+ ')','\0', a_X(PAREN_RIGHT),
+ '(','\0', a_X(PAREN_LEFT),
+ ',','\0', a_X(COMMA),
+
+ '<','=','\0', a_X(LE),
+ '>','=','\0', a_X(GE),
+ '=','=','\0', a_X(EQ),
+ '<','\0', a_X(LT),
+ '>','\0', a_X(GT),
+ '=','\0', a_X(ASSIGN),
+
+ '?','\0', a_X(COND),
+ ':','\0', a_X(COND_COLON),
+
+ '\0'
+#undef a_X
+};
+
+/* Our "public" entry point. exp_buf can be NIL if exp_len is 0, it need not
+ * be NUL terminated (stop for NUL or out of length).
+ * Upon error *error_track_or_nil is set to a "newly allocated" string that
+ * points to where parse stopped, or NIL upon initial setup failure. */
+static enum a_shexp_arith_error a_shexp_arith_eval(
+#ifdef a_SHEXP_ARITH_COOKIE
+ a_SHEXP_ARITH_COOKIE cookie,
+#endif
+ s64 *resp, char const *exp_buf, uz exp_len
+ a_SHEXP_ARITH_ERROR_TRACK( su_COMMA char **error_track_or_nil ));
+
+static void a_shexp__arith_eval(struct a_shexp_arith_ctx *self,
+ char const *exp_buf, uz exp_len);
+
+/* Count non-WS as well as normalized WS ([:"space":]+ -> ' ') in exp_buf,
+ * return count. If store!=NIL, also copy normalization.
+ * An all-WS exp_buf returns 0 */
+static uz a_shexp__arith_ws_squeeze(struct a_shexp_arith_ctx *self,
+ char const *exp_buf, uz exp_len, char *store_or_nil);
+
+/* Resolve and evaluate the "self-contained string" savp->sav_var.
+ * Take care to avoid name lookup loops */
+static boole a_shexp__arith_val_eval(struct a_shexp_arith_ctx *self,
+ struct a_shexp_arith_val *savp);
+
+/* Work top of the stack, which may pop & push etc */
+static boole a_shexp__arith_op_apply(struct a_shexp_arith_ctx *self);
+
+static boole a_shexp__arith_op_apply_colons(struct a_shexp_arith_ctx *self);
+
+#if a_SHEXP_ARITH_DBG
+static void a_shexp__arith_log(char const *fmt, ...);
+#endif
+
+static enum a_shexp_arith_error
+a_shexp_arith_eval(
+#ifdef a_SHEXP_ARITH_COOKIE
+ a_SHEXP_ARITH_COOKIE cookie,
+#endif
+ s64 *resp, char const *exp_buf, uz exp_len
+ a_SHEXP_ARITH_ERROR_TRACK( su_COMMA char **error_track_or_nil )){
+ struct a_shexp_arith_stack sas_stack;
+ struct a_shexp_arith_ctx self;
+ NYD_IN;
+
+ a_SHEXP_ARITH_L(("> arith_eval %zu <%.*s>\n",
+ exp_len, S(int,exp_len != UZ_MAX ? exp_len : su_cs_len(exp_buf)),
+ exp_buf));
+
+ a_SHEXP_ARITH_ERROR_TRACK(DBGX(
+ if(error_track_or_nil != NIL)
+ *error_track_or_nil = NIL;
+ ));
+
+ STRUCT_ZERO(struct a_shexp_arith_ctx, &self);
+#ifdef a_SHEXP_ARITH_COOKIE
+ self.sac_cookie = cookie;
+#endif
+ a_SHEXP_ARITH_ERROR_TRACK(
+ if((self.sac_error_track_or_nil = error_track_or_nil) != NIL)
+ self.sac_have_error_track = TRU1;
+ )
+
+ ASSERT_NYD_EXEC(resp != NIL,
+ self.sac_error = a_SHEXP_ARITH_ERR_NO_OP);
+ DBGX( *resp = 0; )
+ ASSERT_NYD_EXEC(exp_len == 0 || exp_buf != NIL,
+ self.sac_error = a_SHEXP_ARITH_ERR_NO_OP);
+
+ a_SHEXP_ARITH_IFS( self.sac_ifs_ws = ok_vlook(ifs_ws); )
+ self.sac_stack = &sas_stack;
+ a_shexp__arith_eval(&self, exp_buf, exp_len);
+ *resp = self.sac_rv;
+
+ a_SHEXP_ARITH_L(("< arith_eval %zu <%.*s> -> <%lld> ERR<%d>\n",
+ exp_len, S(int,exp_len != UZ_MAX ? exp_len : su_cs_len(exp_buf)),
+ exp_buf, self.sac_rv, self.sac_error));
+
+ NYD_OU;
+ return self.sac_error;
+}
+
+static void
+a_shexp__arith_eval(struct a_shexp_arith_ctx *self,
+ char const *exp_buf, uz exp_len){
+ char *ep, *varp, *cp, c;
+ u16 lop;
+ struct a_shexp_arith_stack *sasp;
+ void *mem_p;
+ NYD2_IN;
+
+ a_SHEXP_ARITH_L((" > _arith_eval %zu <%.*s>\n",
+ exp_len, S(int,exp_len != UZ_MAX ? exp_len : su_cs_len(exp_buf)),
+ exp_buf));
+
+ mem_p = NIL;
+ sasp = self->sac_stack;
+
+ /* Create a single continuous allocation for anything */
+ /* C99 */{
+ union {void *v; char *c;} p;
+ uz i, j, a;
+
+ /* Done for empty expression */
+ if((i = a_shexp__arith_ws_squeeze(self, exp_buf, exp_len, NIL)) == 0)
+ goto jleave;
+ ++i;
+
+ /* Overflow check: since arithmetic expressions are rarely long enough
+ * to come near this limit, xxx laxe & fuzzy, not exact; max U32_MAX! */
+ if(su_64( i > U32_MAX || ) i >= UZ_MAX / 2 ||
+ i >= ((UZ_MAX - (i a_SHEXP_ARITH_ERROR_TRACK( * 2))) /
+ ((su_ALIGNOF(*sasp->sas_nums) + sizeof(*sasp->sas_ops) * 2)
+ a_SHEXP_ARITH_ERROR_TRACK(
+ + sizeof(*sasp->sas_error_track) * 2 ))
+ )){
+ self->sac_error = a_SHEXP_ARITH_ERR_NOMEM;
+ goto jleave;
+ }
+
+ ++i;
+ j = su_ALIGNOF(*sasp->sas_nums) * (i >> 1);
+ a = j + (sizeof(*sasp->sas_ops) * i) +
+ a_SHEXP_ARITH_ERROR_TRACK( (sizeof(*sasp->sas_error_track) * i) + )
+ 1 + (i a_SHEXP_ARITH_ERROR_TRACK( * 2 ));
+ mem_p = p.v = su_LOFI_ALLOC(a);
+ if(p.v == NIL){
+ /* (For MX LOFI has _MUSTFAIL set though) */
+ self->sac_error = a_SHEXP_ARITH_ERR_NOMEM;
+ goto jleave;
+ }
+ sasp->sas_nums = sasp->sas_nums_top = S(struct a_shexp_arith_val*,p.v);
+ p.c += j;
+ sasp->sas_ops = sasp->sas_ops_top = S(u16*,p.v);
+ p.c += sizeof(*sasp->sas_ops) * i;
+ a_SHEXP_ARITH_ERROR_TRACK(
+ sasp->sas_error_track_top = sasp->sas_error_track = S(char**,p.v);
+ p.c += sizeof(*sasp->sas_error_track) * i;
+ )
+
+ ep = ++p.c; /* ++ to copy varnames in !_ARITH_ERROR cases */
+ i = a_shexp__arith_ws_squeeze(self, exp_buf, exp_len, ep);
+ varp = &ep[
+#if 0 a_SHEXP_ARITH_ERROR_TRACK( + 1)
+ i + 1
+#else
+ -1
+#endif
+ ];
+
+ a_SHEXP_ARITH_L((" ! _arith_eval ALLOC <%lu> "
+ "nums=%p (%lu) ops=%p varp=%p %lu <%s>\n",
+ S(ul,a), sasp->sas_nums, S(ul,j / su_ALIGNOF(*sasp->sas_nums)),
+ sasp->sas_ops, varp, S(ul,i - 1), ep));
+ }
+
+ /* Start with a left paren */
+ a_SHEXP_ARITH_ERROR_TRACK( *sasp->sas_error_track_top++ = ep; )
+ *sasp->sas_ops_top++ = lop = a_SHEXP_ARITH_OP_PAREN_LEFT;
+
+ for(;;) Jouter:{
+ u16 op;
+
+ a_SHEXP_ARITH_L((" = _arith_eval TICK LOP <0x%02X %u> "
+ "nums=%lu ops=%lu DATA %lu <%s>\n",
+ lop, lop & 0xFF, S(ul,sasp->sas_nums_top - sasp->sas_nums),
+ S(ul,sasp->sas_ops_top - sasp->sas_ops), S(ul,su_cs_len(ep)), ep));
+
+ if(*ep == '\0'){
+ /* At the end of the expression pop anything left.
+ * Assume we have read PAREN_RIGHT */
+ if(exp_buf != NIL){
+ exp_buf = NIL;
+ op = a_SHEXP_ARITH_OP_PAREN_RIGHT;
+ ASSERT(sasp->sas_ops_top > sasp->sas_ops);
+ goto jtok_go;
+ }
+
+ /* After PAREN_RIGHT, we must be finished */
+ if(sasp->sas_nums_top != &sasp->sas_nums[1])
+ self->sac_error = a_SHEXP_ARITH_ERR_SYNTAX;
+ break;
+ }
+
+ /* Skip (normalized) WS now */
+ if(*ep == ' ')
+ ++ep;
+ ASSERT(!su_cs_is_space(*ep));
+
+ /* A number? */
+ if(su_cs_is_digit(*ep)){
+ BITENUM_IS(u32,su_idec_state) is;
+
+ is = su_idec_cp(&sasp->sas_nums_top->sav_val, ep, 0,
+ a_SHEXP_ARITH_IDEC_MODE, S(char const**,&ep));
+ if((is &= su_IDEC_STATE_EMASK) && is != su_IDEC_STATE_EBASE)
+ sasp->sas_nums_top->sav_val = 0;
+ sasp->sas_nums_top->sav_var = NIL;
+
+ ++sasp->sas_nums_top;
+ lop = a_SHEXP_ARITH_OP_NUM;
+ a_SHEXP_ARITH_L((" + _arith_eval NUM <%lld>\n",
+ sasp->sas_nums_top[-1].sav_val));
+ continue;
+ }
+
+ /* Is it a variable name? */
+ for(cp = ep; (c = *cp, a_SHEXP_ISVARC(c)); ++cp)
+ if(cp == ep && a_SHEXP_ISVARC_BAD1ST(c))
+ break;
+
+ if(cp != ep){
+ for(;;){
+ c = cp[-1];
+ if(!a_SHEXP_ISVARC_BADNST(c))
+ break;
+ if(--cp == ep){
+ self->sac_error = a_SHEXP_ARITH_ERR_SYNTAX;
+ goto jleave;
+ }
+ }
+
+ /* Copy over to pre-allocated var storage */
+ /* C99 */{
+ uz i;
+
+ i = P2UZ(cp - ep);
+ /* (Need to move for !_ARITH_ERROR cases) */
+ su_mem_move(sasp->sas_nums_top->sav_var = varp, ep, i);
+ varp += i;
+ *varp++ = '\0';
+ }
+ ep = cp;
+
+ ++sasp->sas_nums_top;
+ lop = a_SHEXP_ARITH_OP_NUM;
+
+ a_SHEXP_ARITH_L((" + _arith_eval VAR <%s>\n",
+ sasp->sas_nums_top[-1].sav_var));
+ continue;
+ }
+
+ /* An operator.
+ * We turn prefix operators to multiple unary plus/minus if
+ * not attached to a variable name (++10 -> + + 10).
+ * (We adjust postfix to prefix below) */
+ if((ep[0] == '+' || ep[0] == '-') && (ep[1] == ep[0])){
+ if(sasp->sas_nums_top == sasp->sas_nums ||
+ sasp->sas_nums_top[-1].sav_var == NIL){
+ if((c = ep[2]) == ' ')
+ c = ep[3];
+
+ if(c != '\0' && (!a_SHEXP_ISVARC(c) || a_SHEXP_ISVARC_BAD1ST(c))){
+ op = (ep[0] == '+') ? a_SHEXP_ARITH_OP_ADD
+ : a_SHEXP_ARITH_OP_SUB;
+ ++ep;
+ a_SHEXP_ARITH_L((" + _arith_eval OP PREFIX INC/DEC SPLIT "
+ "<%c%c> -> <%c>\n", ep[0], ep[0], ep[0]));
+ goto jtok_go;
+ }
+ }
+ }
+
+ /* Operator search */
+ /* C99 */{
+ char const *tokp;
+
+ /* 3=NUL+OP+PREC */
+ for(tokp = a_shexp_arith_op_toks; *tokp != '\0'; tokp += 3){
+ for(cp = ep;; ++tokp, ++cp){
+ if(*tokp == '\0'){
+ ep = cp;
+ op = (S(u16,tokp[1]) << 8) | S(u8,tokp[2]);
+ goto jtok_go;
+ }else if(*tokp != *cp)
+ break;
+ }
+
+ while(*tokp != '\0')
+ ++tokp;
+ }
+ self->sac_error = a_SHEXP_ARITH_ERR_OP_INVALID;
+ goto jleave;
+ }
+
+jtok_go:/* C99 */{
+ u8 prec;
+
+ prec = op & 0xFF;
+ a_SHEXP_ARITH_L((" + _arith_eval OP <0x%02X %u> LOP <0x%02X %u> "
+ "nums=%lu ops=%lu %lu <%s>\n",
+ op, prec, lop, lop & 0xFF, S(ul,sasp->sas_nums_top - sasp->sas_nums),
+ S(ul,sasp->sas_ops_top - sasp->sas_ops), S(ul,su_cs_len(ep)), ep));
+
+ if(op == a_SHEXP_ARITH_OP_UNARY_PLUS){
+ a_SHEXP_ARITH_L((" + _arith_eval IGNORE UNARY PLUS\n"));
+ continue;
+ }
+
+ /* Correct our understanding of what there is.
+ * Post grammar: VAR++ reduces to num */
+ if((lop & 0xFF) == a_SHEXP_ARITH_PREC_POSTFIX){
+ lop = a_SHEXP_ARITH_OP_NUM;
+ a_SHEXP_ARITH_L((" + _arith_eval LOP POSTFIX REDUCED to NUM\n"));
+ }
+ /* Adjust some binary/postfix operators to make them flow */
+ else if(lop != a_SHEXP_ARITH_OP_NUM){
+ switch(op){
+ case a_SHEXP_ARITH_OP_ADD:
+ a_SHEXP_ARITH_L((" + _arith_eval OP ADJUST: IGNORE UNARY PLUS\n"));
+ continue;
+ case a_SHEXP_ARITH_OP_SUB:
+ op = a_SHEXP_ARITH_OP_UNARY_MINUS;
+ goto junapre;
+ case a_SHEXP_ARITH_OP_POSTFIX_INC:
+ op = a_SHEXP_ARITH_OP_PREFIX_INC;
+ goto junapre;
+ case a_SHEXP_ARITH_OP_POSTFIX_DEC:
+ op = a_SHEXP_ARITH_OP_PREFIX_DEC;
+junapre:
+ prec = a_SHEXP_ARITH_PREC_PREFIX;
+ a_SHEXP_ARITH_L((" + _arith_eval OP ADJUST TO UNARY/PREFIX\n"));
+ break;
+ }
+ }
+ /* Special: +10++VAR -> +10 + +VAR. (Since we do handle +10++11
+ * correctly via "prefix split", we should also handle this) */
+ else if(prec == a_SHEXP_ARITH_PREC_POSTFIX){
+ ASSERT(lop == a_SHEXP_ARITH_OP_NUM);
+ if((c = ep[0]) == ' ')
+ c = ep[1];
+ if(c != '\0' && (a_SHEXP_ISVARC(c) && !a_SHEXP_ISVARC_BAD1ST(c))){
+ c = *--ep;
+ op = (c == '+') ? a_SHEXP_ARITH_OP_ADD : a_SHEXP_ARITH_OP_SUB;
+ prec = op & 0xFF;
+ a_SHEXP_ARITH_L((" + _arith_eval OP POSTFIX INC/DEC SPLIT "
+ "<%c%c> -> <%c>\n", c, c, c));
+ }
+ }
+
+ /* Check whether we can work it a bit */
+ if((prec > a_SHEXP_ARITH_PREC_PAREN_LEFT &&
+ prec < a_SHEXP_ARITH_PREC_UNARY) ||
+ prec >= a_SHEXP_ARITH_PREC_SKY){
+ if(lop != a_SHEXP_ARITH_OP_NUM){
+ self->sac_error = a_SHEXP_ARITH_ERR_NO_OP;
+ goto jleave;
+ }
+
+ /* Pop as much as possible */
+ while(sasp->sas_ops_top != sasp->sas_ops){
+ a_SHEXP_ARITH_ERROR_TRACK( --sasp->sas_error_track_top; )
+ lop = *--sasp->sas_ops_top & a_SHEXP_ARITH_OP_MASK;
+
+ a_SHEXP_ARITH_L((" + _arith_eval TRY POP - OP "
+ "<0x%02X %u>, NEW LOP <0x%02X %u 0x%X> nums=%lu ops=%lu\n",
+ op, op & 0xFF, lop, lop & 0xFF,
+ (*sasp->sas_ops_top & a_SHEXP_ARITH_OP_FLAG_MASK),
+ S(ul,sasp->sas_nums_top - sasp->sas_nums),
+ S(ul,sasp->sas_ops_top - sasp->sas_ops)));
+
+ /* Special-case parenthesis groups */
+ if(op == a_SHEXP_ARITH_OP_PAREN_RIGHT){
+ if(lop == a_SHEXP_ARITH_OP_PAREN_LEFT){
+ ASSERT(sasp->sas_nums_top > sasp->sas_nums);
+ /* Resolve VAR to NUM */
+ if(sasp->sas_nums_top[-1].sav_var != NIL){
+ ASSERT(!(*sasp->sas_ops_top &
+ a_SHEXP_ARITH_OP_FLAG_WHITE_MASK));
+ if(!a_shexp__arith_val_eval(self,
+ &sasp->sas_nums_top[-1]))
+ goto jleave;
+ }
+ sasp->sas_nums_top[-1].sav_var = NIL;
+ a_SHEXP_ARITH_L((" + _arith_eval OP () RESOLVED <%lld>\n",
+ sasp->sas_nums_top[-1].sav_val));
+ lop = a_SHEXP_ARITH_OP_NUM;
+ goto Jouter;
+ }
+ }else{
+ u8 lprec;
+
+ lprec = lop & 0xFF;
+
+ /* */
+ if(op == a_SHEXP_ARITH_OP_COND){
+ u16 x;
+
+ x = *sasp->sas_ops_top;
+ x &= a_SHEXP_ARITH_OP_FLAG_MASK;
+ if(x & a_SHEXP_ARITH_OP_FLAG_WHITEOUT){
+ x ^= a_SHEXP_ARITH_OP_FLAG_WHITEOUT;
+ x |= a_SHEXP_ARITH_OP_FLAG_OUTER_WHITEOUT;
+ }
+ op |= x;
+
+ /* Resolve as much as possible */
+ while(lprec > a_SHEXP_ARITH_PREC_COND){
+ if(!a_shexp__arith_op_apply(self))
+ goto jleave;
+ a_SHEXP_ARITH_ERROR_TRACK( --sasp->sas_error_track_top; )
+ lop = *--sasp->sas_ops_top & a_SHEXP_ARITH_OP_MASK;
+ lprec = lop & 0xFF;
+ }
+
+ ASSERT(sasp->sas_nums_top > sasp->sas_nums);
+ --sasp->sas_nums_top;
+
+ if(sasp->sas_nums_top->sav_var != NIL){
+ if(!(op & a_SHEXP_ARITH_OP_FLAG_WHITE_MASK) &&
+ (op & a_SHEXP_ARITH_OP_MASK) !=
+ a_SHEXP_ARITH_OP_ASSIGN &&
+ !a_shexp__arith_val_eval(self, sasp->sas_nums_top))
+ goto jleave;
+ sasp->sas_nums_top->sav_var = NIL;
+ }
+
+ if((sasp->sas_nums_top)->sav_val == 0)
+ op |= a_SHEXP_ARITH_OP_FLAG_WHITEOUT;
+ op |= *sasp->sas_ops_top & a_SHEXP_ARITH_OP_FLAG_MASK;
+
+ /* Delay ternary */
+ a_SHEXP_ARITH_ERROR_TRACK( ++sasp->sas_error_track_top; )
+ ++sasp->sas_ops_top;
+ break;
+ }else if(op == a_SHEXP_ARITH_OP_COND_COLON){
+ uz recur;
+ u16 *opsp, x;
+ boole delay;
+
+ delay = TRU1;
+
+ /* Find our counterpart ? so we can toggle whiteout */
+ opsp = sasp->sas_ops_top;
+ for(recur = 1;; --opsp){
+ if(opsp == sasp->sas_ops){
+ self->sac_error = a_SHEXP_ARITH_ERR_SYNTAX;
+ goto jleave;
+ }
+
+ x = *opsp & a_SHEXP_ARITH_OP_MASK;
+ if(x == a_SHEXP_ARITH_OP_COND_COLON)
+ ++recur;
+ else if(x == a_SHEXP_ARITH_OP_COND && --recur == 0){
+ *opsp |= a_SHEXP_ARITH_OP_FLAG_COND_SAW_COLON;
+ break;
+ }
+ }
+ op |= *opsp & a_SHEXP_ARITH_OP_FLAG_MASK;
+ op ^= a_SHEXP_ARITH_OP_FLAG_WHITEOUT;
+
+ /* Resolve innermost condition asap.
+ * In "1 ? 0 ? 5 : 6 : 3", resolve innermost upon :3 */
+ while(lprec > a_SHEXP_ARITH_PREC_PAREN_LEFT &&
+ lprec != a_SHEXP_ARITH_PREC_COND){
+ if(!a_shexp__arith_op_apply(self))
+ goto jleave;
+ a_SHEXP_ARITH_ERROR_TRACK( --sasp->sas_error_track_top; )
+ lop = *--sasp->sas_ops_top & a_SHEXP_ARITH_OP_MASK;
+ lprec = lop & 0xFF;
+ }
+
+ /* If we now see a COLON, we have to resolve further!
+ * Code flow restrictions of the Dijkstra algorithm!, which
+ * fits ternary badly (the way we do): pop as pop can! */
+ if(lop == a_SHEXP_ARITH_OP_COND_COLON){
+ delay = FAL0;
+ if(!a_shexp__arith_op_apply_colons(self))
+ goto jleave;
+ lop = *sasp->sas_ops_top & a_SHEXP_ARITH_OP_MASK;
+ }
+
+ if(lop != a_SHEXP_ARITH_OP_COND){
+ self->sac_error = a_SHEXP_ARITH_ERR_SYNTAX;
+ goto jleave;
+ }
+
+ if(delay){
+ a_SHEXP_ARITH_ERROR_TRACK( ++sasp->sas_error_track_top; )
+ ++sasp->sas_ops_top;
+ }
+ a_SHEXP_ARITH_L((" + _arith_eval %sTERNARY ?:%s\n",
+ (delay ? "DELAY " : su_empty),
+ ((op & a_SHEXP_ARITH_OP_FLAG_WHITE_MASK)
+ ? " WHITEOUT" : su_empty)));
+ break;
+ }
+ /* Is this a right-associative operation? */
+ else{
+ boole doit;
+
+ doit = FAL0;
+ if(lprec < prec){
+ doit = TRU1;
+ a_SHEXP_ARITH_L((" + _arith_eval DELAY PRECEDENCE\n"));
+ }else if(lprec == prec && prec == a_SHEXP_ARITH_PREC_ASSIGN){
+ doit = TRU1;
+ a_SHEXP_ARITH_L((" + _arith_eval DELAY RIGHT ASSOC\n"));
+ }else if(lprec == a_SHEXP_ARITH_PREC_COND){
+ if(lop == a_SHEXP_ARITH_OP_COND){
+ doit = TRU1;
+ a_SHEXP_ARITH_L((" + _arith_eval DELAY CONDITION\n"));
+ }
+ /* Without massive rewrite this is the location to detect
+ * in-whiteout precedence bugs as in
+ * $((0?I1=10:(1?I3:I2=12)))
+ * which would be parsed like (1?I3:I2)=12 without error
+ * (different to 0?I3:I2=12) otherwise */
+ else if(op != a_SHEXP_ARITH_OP_COMMA){
+ self->sac_error = a_SHEXP_ARITH_ERR_COND_PREC_INVALID;
+ goto jleave;
+ }
+ }
+
+ if(doit){
+ /* If we are about to delay and LHV is a VAR, expand that
+ * immediately to expand in correct order things like
+ * I1=I2=10 I2=3; echo $((I1,I2))
+ * I1=I2=10 I2=3; echo $((I1+=I2)) */
+ if(sasp->sas_nums_top[-1].sav_var != NIL){
+ if(op != a_SHEXP_ARITH_OP_ASSIGN &&
+ !(*sasp->sas_ops_top &
+ a_SHEXP_ARITH_OP_FLAG_WHITE_MASK) &&
+ !a_shexp__arith_val_eval(self,
+ &sasp->sas_nums_top[-1]))
+ goto jleave;
+ if(prec != a_SHEXP_ARITH_PREC_ASSIGN)
+ sasp->sas_nums_top[-1].sav_var = NIL;
+ }
+
+ a_SHEXP_ARITH_ERROR_TRACK( ++sasp->sas_error_track_top; )
+ ++sasp->sas_ops_top;
+ break;
+ }
+ }
+ }
+
+ /* */
+ if(!a_shexp__arith_op_apply(self))
+ goto jleave;
+
+ if(lop == a_SHEXP_ARITH_OP_COND_COLON){
+ ASSERT(sasp->sas_ops_top > sasp->sas_ops &&
+ &sasp->sas_ops_top[-1] > sasp->sas_ops);
+ ASSERT((sasp->sas_ops_top[-1] & a_SHEXP_ARITH_OP_MASK
+ ) == a_SHEXP_ARITH_OP_COND);
+ a_SHEXP_ARITH_ERROR_TRACK( --sasp->sas_error_track_top; )
+ --sasp->sas_ops_top;
+ *sasp->sas_ops_top ^= a_SHEXP_ARITH_OP_FLAG_WHITEOUT;
+ }
+ }
+
+ if(op == a_SHEXP_ARITH_OP_PAREN_RIGHT){
+ self->sac_error = a_SHEXP_ARITH_ERR_SYNTAX;
+ goto jleave;
+ }
+ }
+
+ /* Push this operator to the stack and remember it */
+ a_SHEXP_ARITH_ERROR_TRACK( *sasp->sas_error_track_top++ = ep; )
+ if(sasp->sas_ops_top > sasp->sas_ops &&
+ (op & 0xFF) != a_SHEXP_ARITH_PREC_COND)
+ op |= sasp->sas_ops_top[-1] & a_SHEXP_ARITH_OP_FLAG_MASK;
+ *sasp->sas_ops_top++ = op;
+ lop = op & a_SHEXP_ARITH_OP_MASK;
+ a_SHEXP_ARITH_L((" + _arith_eval OP PUSH <0x%02X %u> nums=%lu ops=%lu\n",
+ op, (op & 0xFF), S(ul,sasp->sas_nums_top - sasp->sas_nums),
+ S(ul,sasp->sas_ops_top - sasp->sas_ops)));
+ }
+ }
+
+ self->sac_rv = sasp->sas_nums->sav_val;
+
+jleave:
+#if 0 a_SHEXP_ARITH_ERROR_TRACK( + 1 )
+ if(self->sac_error != a_SHEXP_ARITH_ERR_NONE && mem_p != NIL &&
+ self->sac_have_error_track){
+ if(sasp->sas_error_track_top > sasp->sas_error_track)
+ --sasp->sas_error_track_top;
+ *self->sac_error_track_or_nil = savestr(*sasp->sas_error_track_top);
+ }
+#endif
+
+ if(mem_p != NIL)
+ su_LOFI_FREE(mem_p);
+
+ a_SHEXP_ARITH_L((" < _arith_eval <%lld> ERR<%d>\n",
+ self->sac_rv, self->sac_error));
+
+ NYD2_OU;
+}
+
+static uz
+a_shexp__arith_ws_squeeze(struct a_shexp_arith_ctx *self,
+ char const *exp_buf, uz exp_len, char *store_or_nil){
+ a_SHEXP_ARITH_IFS( char const *ifs_ws; )
+ char c;
+ boole last_ws, ws;
+ uz rv;
+ NYD2_IN;
+ UNUSED(self);
+
+ rv = 0;
+ a_SHEXP_ARITH_IFS( ifs_ws = self->sac_ifs_ws; )
+
+ for(;; ++exp_buf, --exp_len){
+ if(UNLIKELY(exp_len == 0) || UNLIKELY((c = *exp_buf) == '\0'))
+ goto jleave;
+ if(!(su_cs_is_space(c)
+ a_SHEXP_ARITH_IFS( || su_cs_find_c(ifs_ws, c) != NIL )
+ ))
+ break;
+ }
+
+ for(last_ws = FAL0;; ++exp_buf, --exp_len){
+ if(UNLIKELY(exp_len == 0) || UNLIKELY((c = *exp_buf) == '\0'))
+ break;
+
+ ws = (su_cs_is_space(c)
+ a_SHEXP_ARITH_IFS( || su_cs_find_c(ifs_ws, c) != NIL )
+ );
+ if(ws){
+ if(last_ws)
+ continue;
+ c = ' ';
+ }
+ last_ws = ws;
+
+ ++rv;
+ if(store_or_nil != NIL)
+ *store_or_nil++ = c;
+ }
+
+ if(last_ws){
+ --rv;
+ if(store_or_nil != NIL)
+ --store_or_nil;
+ }
+
+jleave:
+ if(store_or_nil != NIL)
+ *store_or_nil = '\0';
+
+ NYD2_OU;
+ return rv;
+}
+
+static boole
+a_shexp__arith_val_eval(struct a_shexp_arith_ctx *self,
+ struct a_shexp_arith_val *savp){
+ struct a_shexp_arith_name_stack sans_stack, *sansp;
+ struct a_shexp_arith_stack sas_stack, *sasp;
+ char const *cp;
+ NYD_IN;
+ ASSERT(savp->sav_var != NIL);
+
+ a_SHEXP_ARITH_L(("> _arith_val_eval %p <%s>\n", savp, savp->sav_var));
+
+ savp->sav_val = 0;
+
+ /* Also look in program environment XXX configurable? */
+ cp = n_var_vlook(savp->sav_var, TRU1);
+ if(cp == NIL)
+ goto jleave;
+
+ for(sansp = self->sac_name_stack; sansp != NIL; sansp = sansp->sans_last){
+ if(!su_cs_cmp(sansp->sans_var, savp->sav_var)){
+ self->sac_error = a_SHEXP_ARITH_ERR_NAME_LOOP;
+ goto jleave;
+ }
+ }
+
+ /* cp must be a self-contained expression.
+ * However, in most cases it solely consists of an integer, shortcut that */
+ if(su_idec_cp(&savp->sav_val, cp, 0, a_SHEXP_ARITH_IDEC_MODE, NIL
+ ) & su_IDEC_STATE_CONSUMED){
+ a_SHEXP_ARITH_L((" + _arith_val_eval NUM DIRECT <%lld>\n",
+ savp->sav_val));
+ }else{
+ sasp = self->sac_stack;
+ self->sac_stack = &sas_stack;
+
+ sans_stack.sans_last = sansp = self->sac_name_stack;
+ sans_stack.sans_var = savp->sav_var;
+ self->sac_name_stack = &sans_stack;
+
+ a_shexp__arith_eval(self, cp, UZ_MAX);
+ savp->sav_val = self->sac_rv;
+ /* .sav_var may be needed further on for updating purposes */
+
+ self->sac_stack = sasp;
+ self->sac_name_stack = sansp;
+ }
+
+ cp = NIL;
+jleave:
+ a_SHEXP_ARITH_L(("< _arith_val_eval %p <%s> <%lld> -> OK <%d>\n",
+ savp, savp->sav_var, savp->sav_val,
+ (cp == NIL && self->sac_error == a_SHEXP_ARITH_ERR_NONE)));
+
+ NYD_OU;
+ return (cp == NIL && self->sac_error == a_SHEXP_ARITH_ERR_NONE);
+}
+
+static boole
+a_shexp__arith_op_apply(struct a_shexp_arith_ctx *self){
+ struct a_shexp_arith_val *nums_top;
+ u8 prec;
+ u16 op;
+ struct a_shexp_arith_stack *sasp;
+ s64 val;
+ boole rv, ign;
+ NYD_IN;
+
+ rv = FAL0;
+ val = 0;
+ sasp = self->sac_stack;
+ op = *sasp->sas_ops_top & a_SHEXP_ARITH_OP_MASK;
+ ign = ((*sasp->sas_ops_top & a_SHEXP_ARITH_OP_FLAG_WHITE_MASK) != 0);
+
+ a_SHEXP_ARITH_L((" > _arith_op_apply %s<0x%02X %u> "
+ "nums_top=%p (%lu) ops_top=%p (%lu)\n",
+ (ign ? "WHITEOUT " : su_empty), op, (op & 0xFF), sasp->sas_nums_top,
+ S(ul,sasp->sas_nums_top - sasp->sas_nums),
+ sasp->sas_ops_top, S(ul,sasp->sas_ops_top - sasp->sas_ops)));
+
+ /* At least one argument is always needed */
+ if((nums_top = sasp->sas_nums_top) == sasp->sas_nums){
+ self->sac_error = a_SHEXP_ARITH_ERR_NO_OP;
+ goto jleave;
+ }
+ --nums_top;
+
+ /* Resolve name ([R]VAL) to value as necessary */
+ if(!ign && nums_top->sav_var != NIL &&
+ !a_shexp__arith_val_eval(self, nums_top))
+ goto jleave;
+
+ val = nums_top->sav_val;
+ prec = op & 0xFF;
+
+ /* Not a binary operator? */
+ if(prec >= a_SHEXP_ARITH_PREC_UNARY && prec < a_SHEXP_ARITH_PREC_SKY){
+ if(ign)
+ goto jquick;
+
+ switch(op){
+ default: break;
+ case a_SHEXP_ARITH_OP_UNARY_NOT: val = !val; break;
+ case a_SHEXP_ARITH_OP_UNARY_BIT_NOT: val = ~val; break;
+ case a_SHEXP_ARITH_OP_UNARY_MINUS: val = -val; break;
+ case a_SHEXP_ARITH_OP_PREFIX_INC: FALLTHRU
+ case a_SHEXP_ARITH_OP_POSTFIX_INC: ++val; break;
+ case a_SHEXP_ARITH_OP_PREFIX_DEC: FALLTHRU
+ case a_SHEXP_ARITH_OP_POSTFIX_DEC: --val; break;
+ }
+ }else if(op == a_SHEXP_ARITH_OP_COND){
+ if(!(*sasp->sas_ops_top & a_SHEXP_ARITH_OP_FLAG_COND_SAW_COLON)){
+ self->sac_error = a_SHEXP_ARITH_ERR_COND_NO_COLON;
+ goto jleave;
+ }
+ goto jquick;
+ }else if(op == a_SHEXP_ARITH_OP_COND_COLON){
+ ASSERT(sasp->sas_ops_top > sasp->sas_ops);
+ ASSERT(nums_top > sasp->sas_nums);
+
+ if(!ign){
+ /* Move the ternary value over to LHV where we find it as a result,
+ * and ensure LHV's name is forgotten so not to evaluate it (for
+ * example in 0?I1:I2 I1 would be evaluated when resolving the virtual
+ * outer group, because it still exists on number stack) */
+ nums_top[-1].sav_val = nums_top[0].sav_val;
+ nums_top[-1].sav_var = NIL;
+ }else
+ val = nums_top[-1].sav_val;
+
+ sasp->sas_nums_top = nums_top;
+
+ if((sasp->sas_ops_top[-1] & a_SHEXP_ARITH_OP_MASK
+ ) == a_SHEXP_ARITH_OP_COND_COLON){
+ a_SHEXP_ARITH_ERROR_TRACK( --sasp->sas_error_track_top; )
+ --sasp->sas_ops_top;
+ if(!a_shexp__arith_op_apply_colons(self))
+ goto jleave;
+ ASSERT(sasp->sas_nums_top > sasp->sas_nums);
+ if(!ign)
+ sasp->sas_nums_top[-1].sav_val = val;
+ }
+ }else{
+ /* Binaries need two numbers: one is popped, the other replaced */
+ s64 rval;
+
+ if(nums_top == sasp->sas_nums){
+ self->sac_error = a_SHEXP_ARITH_ERR_NO_OP;
+ goto jleave;
+ }
+ sasp->sas_nums_top = nums_top--;
+
+ if(ign)
+ goto jquick;
+
+ /* Resolve LHV as necessary */
+ if(op != a_SHEXP_ARITH_OP_ASSIGN && nums_top->sav_var != NIL &&
+ !a_shexp__arith_val_eval(self, nums_top))
+ goto jleave;
+
+ rval = val;
+ val = nums_top->sav_val; /* (may be bogus for assign, fixed soon) */
+
+ /* In precedence order (excluding assignments) */
+ switch(op){
+ default: break;
+ case a_SHEXP_ARITH_OP_COMMA: FALLTHRU
+
+ case a_SHEXP_ARITH_OP_ASSIGN: val = rval; break;
+
+ case a_SHEXP_ARITH_OP_OR: val = (val != 0 || rval != 0); break;
+ case a_SHEXP_ARITH_OP_AND: val = (val != 0 && rval != 0); break;
+
+ case a_SHEXP_ARITH_OP_BIT_OR: FALLTHRU
+ case a_SHEXP_ARITH_OP_ASSIGN_BIT_OR: val |= rval; break;
+ case a_SHEXP_ARITH_OP_BIT_XOR: FALLTHRU
+ case a_SHEXP_ARITH_OP_ASSIGN_BIT_XOR: val ^= rval; break;
+ case a_SHEXP_ARITH_OP_BIT_AND: FALLTHRU
+ case a_SHEXP_ARITH_OP_ASSIGN_BIT_AND: val &= rval; break;
+
+ case a_SHEXP_ARITH_OP_EQ: val = (val == rval); break;
+ case a_SHEXP_ARITH_OP_NE: val = (val != rval); break;
+
+ case a_SHEXP_ARITH_OP_LE: val = (val <= rval); break;
+ case a_SHEXP_ARITH_OP_GE: val = (val >= rval); break;
+ case a_SHEXP_ARITH_OP_LT: val = (val < rval); break;
+ case a_SHEXP_ARITH_OP_GT: val = (val > rval); break;
+
+ case a_SHEXP_ARITH_OP_SHIFT_LEFT: FALLTHRU
+ case a_SHEXP_ARITH_OP_ASSIGN_SHIFT_LEFT: val <<= rval; break;
+
+ case a_SHEXP_ARITH_OP_SHIFT_RIGHT: FALLTHRU
+ case a_SHEXP_ARITH_OP_ASSIGN_SHIFT_RIGHT: val >>= rval; break;
+
+ case a_SHEXP_ARITH_OP_SHIFT_RIGHTU: FALLTHRU
+ case a_SHEXP_ARITH_OP_ASSIGN_SHIFT_RIGHTU:
+ val = S(s64,S(u64,val) >> rval);
+ break;
+
+ case a_SHEXP_ARITH_OP_ADD: FALLTHRU
+ case a_SHEXP_ARITH_OP_ASSIGN_ADD: val += rval; break;
+ case a_SHEXP_ARITH_OP_SUB: FALLTHRU
+ case a_SHEXP_ARITH_OP_ASSIGN_SUB: val -= rval; break;
+
+ case a_SHEXP_ARITH_OP_MUL: FALLTHRU
+ case a_SHEXP_ARITH_OP_ASSIGN_MUL: val *= rval; break;
+ /* For /,%, avoid lvh=S64_MIN, rhv=-1:
+ * CHANGES, bash 4.3 [ac50fbac377e32b98d2de396f016ea81e8ee9961]:
+ * Fixed a bug that caused floating-point exceptions and
+ * overflow errors for the / and % arithmetic operators when
+ * using INTMAX_MIN and -1. */
+ case a_SHEXP_ARITH_OP_DIV: FALLTHRU
+ case a_SHEXP_ARITH_OP_ASSIGN_DIV:
+ if(rval == 0){
+ self->sac_error = a_SHEXP_ARITH_ERR_DIV_BY_ZERO;
+ goto jleave;
+ }else if(val != S64_MIN || rval != -1)
+ val /= rval;
+ break;
+ case a_SHEXP_ARITH_OP_MOD: FALLTHRU
+ case a_SHEXP_ARITH_OP_ASSIGN_MOD:
+ if(rval == 0){
+ self->sac_error = a_SHEXP_ARITH_ERR_DIV_BY_ZERO;
+ goto jleave;
+ }else if(val == S64_MIN && rval == -1)
+ val = 0;
+ else
+ val %= rval;
+ break;
+
+ case a_SHEXP_ARITH_OP_EXP: FALLTHRU
+ case a_SHEXP_ARITH_OP_ASSIGN_EXP:
+ if(rval < 0){
+ self->sac_error = a_SHEXP_ARITH_ERR_EXP_INVALID;
+ goto jleave;
+ }else{
+ s64 i;
+
+ for(i = 1; rval > 0; --rval)
+ i *= val;
+ val = i;
+ }
+ break;
+ }
+ }
+
+ /* Assignment updates a variable, which must exist.
+ * For prefix and postfix operators, too: we already turned them into
+ * multiple unary plus/minus unless we had seen a variable name */
+jquick:
+ if(prec == a_SHEXP_ARITH_PREC_ASSIGN || prec == a_SHEXP_ARITH_PREC_PREFIX ||
+ prec == a_SHEXP_ARITH_PREC_POSTFIX){
+ char buf[su_IENC_BUFFER_SIZE], *bp;
+
+ if(nums_top->sav_var == NIL){
+ self->sac_error = a_SHEXP_ARITH_ERR_ASSIGN_NO_VAR;
+ goto jleave;
+ }
+
+ if(!ign){
+ bp = su_ienc_s64(buf, val, 10);
+ n_var_vset(nums_top->sav_var, S(up,bp), FAL0);
+ }
+
+ /* And restore the stack value again for postfix operators */
+ if(op == a_SHEXP_ARITH_OP_POSTFIX_INC)
+ --val;
+ else if(op == a_SHEXP_ARITH_OP_POSTFIX_DEC)
+ ++val;
+
+ if(!ign)
+ a_SHEXP_ARITH_L((" + _arith_op_apply VAR <%s> SET <%s> VAL <%lld>\n",
+ nums_top->sav_var, bp, val));
+ }
+
+ nums_top->sav_val = val;
+ nums_top->sav_var = NIL;
+
+ rv = TRU1;
+jleave:
+ a_SHEXP_ARITH_L((" < _arith_op_apply RV %d <0x%02X %u> RES<%lld> ERR<%d> "
+ "nums=%lu ops=%lu\n",
+ rv, op, op & 0xFF, val, self->sac_error,
+ S(ul,sasp->sas_nums_top - sasp->sas_nums),
+ S(ul,sasp->sas_ops_top - sasp->sas_ops)));
+
+ NYD_OU;
+ return rv;
+}
+
+static boole
+a_shexp__arith_op_apply_colons(struct a_shexp_arith_ctx *self){
+ u16 lop, lprec;
+ boole next_stop;
+ NYD_IN;
+
+ for(next_stop = FAL0;;){
+ if(!a_shexp__arith_op_apply(self)){
+ next_stop = FAL0;
+ break;
+ }
+ if(next_stop)
+ break;
+ a_SHEXP_ARITH_ERROR_TRACK( --self->sac_stack->sas_error_track_top; )
+ lop = *--self->sac_stack->sas_ops_top & a_SHEXP_ARITH_OP_MASK;
+ lprec = lop & 0xFF;
+ next_stop = (lprec == a_SHEXP_ARITH_PREC_PAREN_LEFT ||
+ lop == a_SHEXP_ARITH_OP_COND);
+ }
+
+ NYD_OU;
+ return next_stop;
+}
+
+#if a_SHEXP_ARITH_DBG
+static void
+a_shexp__arith_log(char const *fmt, ...){
+ va_list ap;
+
+ va_start(ap, fmt);
+ vfprintf(stderr, fmt, ap);
+ va_end(ap);
+}
+#endif
+
+#undef a_SHEXP_ARITH_ERROR_TRACK
+#undef a_SHEXP_ARITH_IFS
+#undef a_SHEXP_ARITH_DBG
+#undef a_SHEXP_ARITH_L
+#undef a_SHEXP_ARITH_IDEC_MODE
+
+/* s-it-mode */
--
2.37.2
--steffen
|
|Der Kragenbaer, The moon bear,
|der holt sich munter he cheerfully and one by one
|einen nach dem anderen runter wa.ks himself off
|(By Robert Gernhardt)
_______________________________________________
busybox mailing list
busybox@busybox.net
http://lists.busybox.net/mailman/listinfo/busybox
