shell/math.c

   1 /*
   2  * Arithmetic code ripped out of ash shell for code sharing.
   3  *
   4  * This code is derived from software contributed to Berkeley by
   5  * Kenneth Almquist.
   6  *
   7  * Original BSD copyright notice is retained at the end of this file.
   8  *
   9  * Copyright (c) 1989, 1991, 1993, 1994
  10  *      The Regents of the University of California.  All rights reserved.
  11  *
  12  * Copyright (c) 1997-2005 Herbert Xu <herbert@gondor.apana.org.au>
  13  * was re-ported from NetBSD and debianized.
  14  *
  15  * rewrite arith.y to micro stack based cryptic algorithm by
  16  * Copyright (c) 2001 Aaron Lehmann <aaronl@vitelus.com>
  17  *
  18  * Modified by Paul Mundt <lethal@linux-sh.org> (c) 2004 to support
  19  * dynamic variables.
  20  *
  21  * Modified by Vladimir Oleynik <dzo@simtreas.ru> (c) 2001-2005 to be
  22  * used in busybox and size optimizations,
  23  * rewrote arith (see notes to this), added locale support,
  24  * rewrote dynamic variables.
  25  *
  26  * Licensed under GPLv2 or later, see file LICENSE in this source tree.
  27  */
  28 /* Copyright (c) 2001 Aaron Lehmann <aaronl@vitelus.com>
  29  *
  30  * Permission is hereby granted, free of charge, to any person obtaining
  31  * a copy of this software and associated documentation files (the
  32  * "Software"), to deal in the Software without restriction, including
  33  * without limitation the rights to use, copy, modify, merge, publish,
  34  * distribute, sublicense, and/or sell copies of the Software, and to
  35  * permit persons to whom the Software is furnished to do so, subject to
  36  * the following conditions:
  37  *
  38  * The above copyright notice and this permission notice shall be
  39  * included in all copies or substantial portions of the Software.
  40  *
  41  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  42  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  43  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  44  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  45  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  46  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  47  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  48  */
  49
  50 /* This is my infix parser/evaluator. It is optimized for size, intended
  51  * as a replacement for yacc-based parsers. However, it may well be faster
  52  * than a comparable parser written in yacc. The supported operators are
  53  * listed in #defines below. Parens, order of operations, and error handling
  54  * are supported. This code is thread safe. The exact expression format should
  55  * be that which POSIX specifies for shells.
  56  *
  57  * The code uses a simple two-stack algorithm. See
  58  * http://www.onthenet.com.au/~grahamis/int2008/week02/lect02.html
  59  * for a detailed explanation of the infix-to-postfix algorithm on which
  60  * this is based (this code differs in that it applies operators immediately
  61  * to the stack instead of adding them to a queue to end up with an
  62  * expression).
  63  */
  64
  65 /*
  66  * Aug 24, 2001              Manuel Novoa III
  67  *
  68  * Reduced the generated code size by about 30% (i386) and fixed several bugs.
  69  *
  70  * 1) In arith_apply():
  71  *    a) Cached values of *numptr and &(numptr[-1]).
  72  *    b) Removed redundant test for zero denominator.
  73  *
  74  * 2) In arith():
  75  *    a) Eliminated redundant code for processing operator tokens by moving
  76  *       to a table-based implementation.  Also folded handling of parens
  77  *       into the table.
  78  *    b) Combined all 3 loops which called arith_apply to reduce generated
  79  *       code size at the cost of speed.
  80  *
  81  * 3) The following expressions were treated as valid by the original code:
  82  *       1()  ,    0!  ,    1 ( *3 )   .
  83  *    These bugs have been fixed by internally enclosing the expression in
  84  *    parens and then checking that all binary ops and right parens are
  85  *    preceded by a valid expression (NUM_TOKEN).
  86  *
  87  * Note: It may be desirable to replace Aaron's test for whitespace with
  88  * ctype's isspace() if it is used by another busybox applet or if additional
  89  * whitespace chars should be considered.  Look below the "#include"s for a
  90  * precompiler test.
  91  */
  92 /*
  93  * Aug 26, 2001              Manuel Novoa III
  94  *
  95  * Return 0 for null expressions.  Pointed out by Vladimir Oleynik.
  96  *
  97  * Merge in Aaron's comments previously posted to the busybox list,
  98  * modified slightly to take account of my changes to the code.
  99  *
 100  */
 101 /*
 102  *  (C) 2003 Vladimir Oleynik <dzo@simtreas.ru>
 103  *
 104  * - allow access to variable,
 105  *   use recursive value indirection: c="2*2"; a="c"; echo $((a+=2)) produce 6
 106  * - implement assign syntax (VAR=expr, +=, *= etc)
 107  * - implement exponentiation (** operator)
 108  * - implement comma separated - expr, expr
 109  * - implement ++expr --expr expr++ expr--
 110  * - implement expr ? expr : expr (but second expr is always calculated)
 111  * - allow hexadecimal and octal numbers
 112  * - restore lost XOR operator
 113  * - protect $((num num)) as true zero expr (Manuel's error)
 114  * - always use special isspace(), see comment from bash ;-)
 115  */
 116 #include "libbb.h"
 117 #include "math.h"
 118
 119 #define lookupvar (math_state->lookupvar)
 120 #define setvar    (math_state->setvar   )
 121 //#define endofname (math_state->endofname)
 122
 123 typedef unsigned char operator;
 124
 125 /* An operator's token id is a bit of a bitfield. The lower 5 bits are the
 126  * precedence, and 3 high bits are an ID unique across operators of that
 127  * precedence. The ID portion is so that multiple operators can have the
 128  * same precedence, ensuring that the leftmost one is evaluated first.
 129  * Consider * and /
 130  */
 131 #define tok_decl(prec,id)       (((id)<<5) | (prec))
 132 #define PREC(op)                ((op) & 0x1F)
 133
 134 #define TOK_LPAREN              tok_decl(0,0)
 135
 136 #define TOK_COMMA               tok_decl(1,0)
 137
 138 /* All assignments are right associative and have the same precedence,
 139  * but there are 11 of them, which doesn't fit into 3 bits for unique id.
 140  * Abusing another precedence level:
 141  */
 142 #define TOK_ASSIGN              tok_decl(2,0)
 143 #define TOK_AND_ASSIGN          tok_decl(2,1)
 144 #define TOK_OR_ASSIGN           tok_decl(2,2)
 145 #define TOK_XOR_ASSIGN          tok_decl(2,3)
 146 #define TOK_PLUS_ASSIGN         tok_decl(2,4)
 147 #define TOK_MINUS_ASSIGN        tok_decl(2,5)
 148 #define TOK_LSHIFT_ASSIGN       tok_decl(2,6)
 149 #define TOK_RSHIFT_ASSIGN       tok_decl(2,7)
 150
 151 #define TOK_MUL_ASSIGN          tok_decl(3,0)
 152 #define TOK_DIV_ASSIGN          tok_decl(3,1)
 153 #define TOK_REM_ASSIGN          tok_decl(3,2)
 154
 155 #define fix_assignment_prec(prec) do { if (prec == 3) prec = 2; } while (0)
 156
 157 /* Ternary conditional operator is right associative too */
 158 #define TOK_CONDITIONAL         tok_decl(4,0)
 159 #define TOK_CONDITIONAL_SEP     tok_decl(4,1)
 160
 161 #define TOK_OR                  tok_decl(5,0)
 162
 163 #define TOK_AND                 tok_decl(6,0)
 164
 165 #define TOK_BOR                 tok_decl(7,0)
 166
 167 #define TOK_BXOR                tok_decl(8,0)
 168
 169 #define TOK_BAND                tok_decl(9,0)
 170
 171 #define TOK_EQ                  tok_decl(10,0)
 172 #define TOK_NE                  tok_decl(10,1)
 173
 174 #define TOK_LT                  tok_decl(11,0)
 175 #define TOK_GT                  tok_decl(11,1)
 176 #define TOK_GE                  tok_decl(11,2)
 177 #define TOK_LE                  tok_decl(11,3)
 178
 179 #define TOK_LSHIFT              tok_decl(12,0)
 180 #define TOK_RSHIFT              tok_decl(12,1)
 181
 182 #define TOK_ADD                 tok_decl(13,0)
 183 #define TOK_SUB                 tok_decl(13,1)
 184
 185 #define TOK_MUL                 tok_decl(14,0)
 186 #define TOK_DIV                 tok_decl(14,1)
 187 #define TOK_REM                 tok_decl(14,2)
 188
 189 /* Exponent is right associative */
 190 #define TOK_EXPONENT            tok_decl(15,1)
 191
 192 /* Unary operators */
 193 #define UNARYPREC               16
 194 #define TOK_BNOT                tok_decl(UNARYPREC,0)
 195 #define TOK_NOT                 tok_decl(UNARYPREC,1)
 196
 197 #define TOK_UMINUS              tok_decl(UNARYPREC+1,0)
 198 #define TOK_UPLUS               tok_decl(UNARYPREC+1,1)
 199
 200 #define PREC_PRE                (UNARYPREC+2)
 201
 202 #define TOK_PRE_INC             tok_decl(PREC_PRE, 0)
 203 #define TOK_PRE_DEC             tok_decl(PREC_PRE, 1)
 204
 205 #define PREC_POST               (UNARYPREC+3)
 206
 207 #define TOK_POST_INC            tok_decl(PREC_POST, 0)
 208 #define TOK_POST_DEC            tok_decl(PREC_POST, 1)
 209
 210 #define SPEC_PREC               (UNARYPREC+4)
 211
 212 #define TOK_NUM                 tok_decl(SPEC_PREC, 0)
 213 #define TOK_RPAREN              tok_decl(SPEC_PREC, 1)
 214
 215 static int
 216 is_assign_op(operator op)
 217 {
 218         operator prec = PREC(op);
 219         fix_assignment_prec(prec);
 220         return prec == PREC(TOK_ASSIGN)
 221         || prec == PREC_PRE
 222         || prec == PREC_POST;
 223 }
 224
 225 static int
 226 is_right_associative(operator prec)
 227 {
 228         return prec == PREC(TOK_ASSIGN)
 229         || prec == PREC(TOK_EXPONENT)
 230         || prec == PREC(TOK_CONDITIONAL);
 231 }
 232
 233
 234 typedef struct {
 235         arith_t val;
 236         /* We acquire second_val only when "expr1 : expr2" part
 237          * of ternary ?: op is evaluated.
 238          * We treat ?: as two binary ops: (expr ? (expr1 : expr2)).
 239          * ':' produces a new value which has two parts, val and second_val;
 240          * then '?' selects one of them based on its left side.
 241          */
 242         arith_t second_val;
 243         char second_val_present;
 244         /* If NULL then it's just a number, else it's a named variable */
 245         char *var;
 246 } var_or_num_t;
 247
 248 typedef struct remembered_name {
 249         struct remembered_name *next;
 250         const char *var;
 251 } remembered_name;
 252
 253
 254 static arith_t FAST_FUNC
 255 evaluate_string(arith_state_t *math_state, const char *expr);
 256
 257 static const char*
 258 arith_lookup_val(arith_state_t *math_state, var_or_num_t *t)
 259 {
 260         if (t->var) {
 261                 const char *p = lookupvar(t->var);
 262                 if (p) {
 263                         remembered_name *cur;
 264                         remembered_name cur_save;
 265
 266                         /* did we already see this name?
 267                          * testcase: a=b; b=a; echo $((a))
 268                          */
 269                         for (cur = math_state->list_of_recursed_names; cur; cur = cur->next) {
 270                                 if (strcmp(cur->var, t->var) == 0) {
 271                                         /* Yes */
 272                                         return "expression recursion loop detected";
 273                                 }
 274                         }
 275
 276                         /* push current var name */
 277                         cur = math_state->list_of_recursed_names;
 278                         cur_save.var = t->var;
 279                         cur_save.next = cur;
 280                         math_state->list_of_recursed_names = &cur_save;
 281
 282                         /* recursively evaluate p as expression */
 283                         t->val = evaluate_string(math_state, p);
 284
 285                         /* pop current var name */
 286                         math_state->list_of_recursed_names = cur;
 287
 288                         return math_state->errmsg;
 289                 }
 290                 /* treat undefined var as 0 */
 291                 t->val = 0;
 292         }
 293         return 0;
 294 }
 295
 296 /* "Applying" a token means performing it on the top elements on the integer
 297  * stack. For an unary operator it will only change the top element, but a
 298  * binary operator will pop two arguments and push the result */
 299 static NOINLINE const char*
 300 arith_apply(arith_state_t *math_state, operator op, var_or_num_t *numstack, var_or_num_t **numstackptr)
 301 {
 302 #define NUMPTR (*numstackptr)
 303
 304         var_or_num_t *top_of_stack;
 305         arith_t rez;
 306         const char *err;
 307
 308         /* There is no operator that can work without arguments */
 309         if (NUMPTR == numstack)
 310                 goto err;
 311
 312         top_of_stack = NUMPTR - 1;
 313
 314         /* Resolve name to value, if needed */
 315         err = arith_lookup_val(math_state, top_of_stack);
 316         if (err)
 317                 return err;
 318
 319         rez = top_of_stack->val;
 320         if (op == TOK_UMINUS)
 321                 rez = -rez;
 322         else if (op == TOK_NOT)
 323                 rez = !rez;
 324         else if (op == TOK_BNOT)
 325                 rez = ~rez;
 326         else if (op == TOK_POST_INC || op == TOK_PRE_INC)
 327                 rez++;
 328         else if (op == TOK_POST_DEC || op == TOK_PRE_DEC)
 329                 rez--;
 330         else if (op != TOK_UPLUS) {
 331                 /* Binary operators */
 332                 arith_t right_side_val;
 333                 char bad_second_val;
 334
 335                 /* Binary operators need two arguments */
 336                 if (top_of_stack == numstack)
 337                         goto err;
 338                 /* ...and they pop one */
 339                 NUMPTR = top_of_stack; /* this decrements NUMPTR */
 340
 341                 bad_second_val = top_of_stack->second_val_present;
 342                 if (op == TOK_CONDITIONAL) { /* ? operation */
 343                         /* Make next if (...) protect against
 344                          * $((expr1 ? expr2)) - that is, missing ": expr" */
 345                         bad_second_val = !bad_second_val;
 346                 }
 347                 if (bad_second_val) {
 348                         /* Protect against $((expr <not_?_op> expr1 : expr2)) */
 349                         return "malformed ?: operator";
 350                 }
 351
 352                 top_of_stack--; /* now points to left side */
 353
 354                 if (op != TOK_ASSIGN) {
 355                         /* Resolve left side value (unless the op is '=') */
 356                         err = arith_lookup_val(math_state, top_of_stack);
 357                         if (err)
 358                                 return err;
 359                 }
 360
 361                 right_side_val = rez;
 362                 rez = top_of_stack->val;
 363                 if (op == TOK_CONDITIONAL) /* ? operation */
 364                         rez = (rez ? right_side_val : top_of_stack[1].second_val);
 365                 else if (op == TOK_CONDITIONAL_SEP) { /* : operation */
 366                         if (top_of_stack == numstack) {
 367                                 /* Protect against $((expr : expr)) */
 368                                 return "malformed ?: operator";
 369                         }
 370                         top_of_stack->second_val_present = op;
 371                         top_of_stack->second_val = right_side_val;
 372                 }
 373                 else if (op == TOK_BOR || op == TOK_OR_ASSIGN)
 374                         rez |= right_side_val;
 375                 else if (op == TOK_OR)
 376                         rez = right_side_val || rez;
 377                 else if (op == TOK_BAND || op == TOK_AND_ASSIGN)
 378                         rez &= right_side_val;
 379                 else if (op == TOK_BXOR || op == TOK_XOR_ASSIGN)
 380                         rez ^= right_side_val;
 381                 else if (op == TOK_AND)
 382                         rez = rez && right_side_val;
 383                 else if (op == TOK_EQ)
 384                         rez = (rez == right_side_val);
 385                 else if (op == TOK_NE)
 386                         rez = (rez != right_side_val);
 387                 else if (op == TOK_GE)
 388                         rez = (rez >= right_side_val);
 389                 else if (op == TOK_RSHIFT || op == TOK_RSHIFT_ASSIGN)
 390                         rez >>= right_side_val;
 391                 else if (op == TOK_LSHIFT || op == TOK_LSHIFT_ASSIGN)
 392                         rez <<= right_side_val;
 393                 else if (op == TOK_GT)
 394                         rez = (rez > right_side_val);
 395                 else if (op == TOK_LT)
 396                         rez = (rez < right_side_val);
 397                 else if (op == TOK_LE)
 398                         rez = (rez <= right_side_val);
 399                 else if (op == TOK_MUL || op == TOK_MUL_ASSIGN)
 400                         rez *= right_side_val;
 401                 else if (op == TOK_ADD || op == TOK_PLUS_ASSIGN)
 402                         rez += right_side_val;
 403                 else if (op == TOK_SUB || op == TOK_MINUS_ASSIGN)
 404                         rez -= right_side_val;
 405                 else if (op == TOK_ASSIGN || op == TOK_COMMA)
 406                         rez = right_side_val;
 407                 else if (op == TOK_EXPONENT) {
 408                         arith_t c;
 409                         if (right_side_val < 0)
 410                                 return "exponent less than 0";
 411                         c = 1;
 412                         while (--right_side_val >= 0)
 413                             c *= rez;
 414                         rez = c;
 415                 }
 416                 else if (right_side_val == 0)
 417                         return "divide by zero";
 418                 else if (op == TOK_DIV || op == TOK_DIV_ASSIGN)
 419                         rez /= right_side_val;
 420                 else if (op == TOK_REM || op == TOK_REM_ASSIGN)
 421                         rez %= right_side_val;
 422         }
 423
 424         if (is_assign_op(op)) {
 425                 char buf[sizeof(arith_t)*3 + 2];
 426
 427                 if (top_of_stack->var == NULL) {
 428                         /* Hmm, 1=2 ? */
 429 //TODO: actually, bash allows ++7 but for some reason it evals to 7, not 8
 430                         goto err;
 431                 }
 432                 /* Save to shell variable */
 433                 sprintf(buf, ARITH_FMT, rez);
 434                 setvar(top_of_stack->var, buf);
 435                 /* After saving, make previous value for v++ or v-- */
 436                 if (op == TOK_POST_INC)
 437                         rez--;
 438                 else if (op == TOK_POST_DEC)
 439                         rez++;
 440         }
 441
 442         top_of_stack->val = rez;
 443         /* Erase var name, it is just a number now */
 444         top_of_stack->var = NULL;
 445         return NULL;
 446  err:
 447         return "arithmetic syntax error";
 448 #undef NUMPTR
 449 }
 450
 451 /* longest must be first */
 452 static const char op_tokens[] ALIGN1 = {
 453         '<','<','=',0, TOK_LSHIFT_ASSIGN,
 454         '>','>','=',0, TOK_RSHIFT_ASSIGN,
 455         '<','<',    0, TOK_LSHIFT,
 456         '>','>',    0, TOK_RSHIFT,
 457         '|','|',    0, TOK_OR,
 458         '&','&',    0, TOK_AND,
 459         '!','=',    0, TOK_NE,
 460         '<','=',    0, TOK_LE,
 461         '>','=',    0, TOK_GE,
 462         '=','=',    0, TOK_EQ,
 463         '|','=',    0, TOK_OR_ASSIGN,
 464         '&','=',    0, TOK_AND_ASSIGN,
 465         '*','=',    0, TOK_MUL_ASSIGN,
 466         '/','=',    0, TOK_DIV_ASSIGN,
 467         '%','=',    0, TOK_REM_ASSIGN,
 468         '+','=',    0, TOK_PLUS_ASSIGN,
 469         '-','=',    0, TOK_MINUS_ASSIGN,
 470         '-','-',    0, TOK_POST_DEC,
 471         '^','=',    0, TOK_XOR_ASSIGN,
 472         '+','+',    0, TOK_POST_INC,
 473         '*','*',    0, TOK_EXPONENT,
 474         '!',        0, TOK_NOT,
 475         '<',        0, TOK_LT,
 476         '>',        0, TOK_GT,
 477         '=',        0, TOK_ASSIGN,
 478         '|',        0, TOK_BOR,
 479         '&',        0, TOK_BAND,
 480         '*',        0, TOK_MUL,
 481         '/',        0, TOK_DIV,
 482         '%',        0, TOK_REM,
 483         '+',        0, TOK_ADD,
 484         '-',        0, TOK_SUB,
 485         '^',        0, TOK_BXOR,
 486         /* uniq */
 487         '~',        0, TOK_BNOT,
 488         ',',        0, TOK_COMMA,
 489         '?',        0, TOK_CONDITIONAL,
 490         ':',        0, TOK_CONDITIONAL_SEP,
 491         ')',        0, TOK_RPAREN,
 492         '(',        0, TOK_LPAREN,
 493         0
 494 };
 495 #define ptr_to_rparen (&op_tokens[sizeof(op_tokens)-7])
 496
 497 const char* FAST_FUNC
 498 endofname(const char *name)
 499 {
 500         if (!is_name(*name))
 501                 return name;
 502         while (*++name) {
 503                 if (!is_in_name(*name))
 504                         break;
 505         }
 506         return name;
 507 }
 508
 509 static arith_t FAST_FUNC
 510 evaluate_string(arith_state_t *math_state, const char *expr)
 511 {
 512         operator lasttok;
 513         const char *errmsg;
 514         const char *start_expr = expr = skip_whitespace(expr);
 515         unsigned expr_len = strlen(expr) + 2;
 516         /* Stack of integers */
 517         /* The proof that there can be no more than strlen(startbuf)/2+1
 518          * integers in any given correct or incorrect expression
 519          * is left as an exercise to the reader. */
 520         var_or_num_t *const numstack = alloca((expr_len / 2) * sizeof(numstack[0]));
 521         var_or_num_t *numstackptr = numstack;
 522         /* Stack of operator tokens */
 523         operator *const stack = alloca(expr_len * sizeof(stack[0]));
 524         operator *stackptr = stack;
 525
 526         /* Start with a left paren */
 527         *stackptr++ = lasttok = TOK_LPAREN;
 528         errmsg = NULL;
 529
 530         while (1) {
 531                 const char *p;
 532                 operator op;
 533                 operator prec;
 534                 char arithval;
 535
 536                 expr = skip_whitespace(expr);
 537                 arithval = *expr;
 538                 if (arithval == '\0') {
 539                         if (expr == start_expr) {
 540                                 /* Null expression */
 541                                 numstack->val = 0;
 542                                 goto ret;
 543                         }
 544
 545                         /* This is only reached after all tokens have been extracted from the
 546                          * input stream. If there are still tokens on the operator stack, they
 547                          * are to be applied in order. At the end, there should be a final
 548                          * result on the integer stack */
 549
 550                         if (expr != ptr_to_rparen + 1) {
 551                                 /* If we haven't done so already,
 552                                  * append a closing right paren
 553                                  * and let the loop process it */
 554                                 expr = ptr_to_rparen;
 555                                 continue;
 556                         }
 557                         /* At this point, we're done with the expression */
 558                         if (numstackptr != numstack + 1) {
 559                                 /* ...but if there isn't, it's bad */
 560                                 goto err;
 561                         }
 562                         if (numstack->var) {
 563                                 /* expression is $((var)) only, lookup now */
 564                                 errmsg = arith_lookup_val(math_state, numstack);
 565                         }
 566                         goto ret;
 567                 }
 568
 569                 p = endofname(expr);
 570                 if (p != expr) {
 571                         /* Name */
 572                         size_t var_name_size = (p-expr) + 1;  /* +1 for NUL */
 573                         numstackptr->var = alloca(var_name_size);
 574                         safe_strncpy(numstackptr->var, expr, var_name_size);
 575                         expr = p;
 576  num:
 577                         numstackptr->second_val_present = 0;
 578                         numstackptr++;
 579                         lasttok = TOK_NUM;
 580                         continue;
 581                 }
 582
 583                 if (isdigit(arithval)) {
 584                         /* Number */
 585                         numstackptr->var = NULL;
 586                         errno = 0;
 587                         numstackptr->val = strto_arith_t(expr, (char**) &expr, 0);
 588                         if (errno)
 589                                 numstackptr->val = 0; /* bash compat */
 590                         goto num;
 591                 }
 592
 593                 /* Should be an operator */
 594                 p = op_tokens;
 595                 while (1) {
 596 // TODO: bash allows 7+++v, treats it as 7 + ++v
 597 // we treat it as 7++ + v and reject
 598                         /* Compare expr to current op_tokens[] element */
 599                         const char *e = expr;
 600                         while (1) {
 601                                 if (*p == '\0') {
 602                                         /* Match: operator is found */
 603                                         expr = e;
 604                                         goto tok_found;
 605                                 }
 606                                 if (*p != *e)
 607                                         break;
 608                                 p++;
 609                                 e++;
 610                         }
 611                         /* No match, go to next element of op_tokens[] */
 612                         while (*p)
 613                                 p++;
 614                         p += 2; /* skip NUL and TOK_foo bytes */
 615                         if (*p == '\0') {
 616                                 /* No next element, operator not found */
 617                                 //math_state->syntax_error_at = expr;
 618                                 goto err;
 619                         }
 620                 }
 621  tok_found:
 622                 op = p[1]; /* fetch TOK_foo value */
 623                 /* NB: expr now points past the operator */
 624
 625                 /* post grammar: a++ reduce to num */
 626                 if (lasttok == TOK_POST_INC || lasttok == TOK_POST_DEC)
 627                         lasttok = TOK_NUM;
 628
 629                 /* Plus and minus are binary (not unary) _only_ if the last
 630                  * token was a number, or a right paren (which pretends to be
 631                  * a number, since it evaluates to one). Think about it.
 632                  * It makes sense. */
 633                 if (lasttok != TOK_NUM) {
 634                         switch (op) {
 635                         case TOK_ADD:
 636                                 op = TOK_UPLUS;
 637                                 break;
 638                         case TOK_SUB:
 639                                 op = TOK_UMINUS;
 640                                 break;
 641                         case TOK_POST_INC:
 642                                 op = TOK_PRE_INC;
 643                                 break;
 644                         case TOK_POST_DEC:
 645                                 op = TOK_PRE_DEC;
 646                                 break;
 647                         }
 648                 }
 649                 /* We don't want an unary operator to cause recursive descent on the
 650                  * stack, because there can be many in a row and it could cause an
 651                  * operator to be evaluated before its argument is pushed onto the
 652                  * integer stack.
 653                  * But for binary operators, "apply" everything on the operator
 654                  * stack until we find an operator with a lesser priority than the
 655                  * one we have just extracted.
 656                  * Left paren is given the lowest priority so it will never be
 657                  * "applied" in this way.
 658                  * if associativity is right and priority eq, applied also skip
 659                  */
 660                 prec = PREC(op);
 661                 if ((prec > 0 && prec < UNARYPREC) || prec == SPEC_PREC) {
 662                         /* not left paren or unary */
 663                         if (lasttok != TOK_NUM) {
 664                                 /* binary op must be preceded by a num */
 665                                 goto err;
 666                         }
 667                         while (stackptr != stack) {
 668                                 operator prev_op = *--stackptr;
 669                                 if (op == TOK_RPAREN) {
 670                                         /* The algorithm employed here is simple: while we don't
 671                                          * hit an open paren nor the bottom of the stack, pop
 672                                          * tokens and apply them */
 673                                         if (prev_op == TOK_LPAREN) {
 674                                                 /* Any operator directly after a
 675                                                  * close paren should consider itself binary */
 676                                                 lasttok = TOK_NUM;
 677                                                 goto next;
 678                                         }
 679                                 } else {
 680                                         operator prev_prec = PREC(prev_op);
 681                                         fix_assignment_prec(prec);
 682                                         fix_assignment_prec(prev_prec);
 683                                         if (prev_prec < prec
 684                                          || (prev_prec == prec && is_right_associative(prec))
 685                                         ) {
 686                                                 stackptr++;
 687                                                 break;
 688                                         }
 689                                 }
 690                                 errmsg = arith_apply(math_state, prev_op, numstack, &numstackptr);
 691                                 if (errmsg)
 692                                         goto err_with_custom_msg;
 693                         }
 694                         if (op == TOK_RPAREN)
 695                                 goto err;
 696                 }
 697
 698                 /* Push this operator to the stack and remember it */
 699                 *stackptr++ = lasttok = op;
 700  next: ;
 701         } /* while (1) */
 702
 703  err:
 704         errmsg = "arithmetic syntax error";
 705  err_with_custom_msg:
 706         numstack->val = -1;
 707  ret:
 708         math_state->errmsg = errmsg;
 709         return numstack->val;
 710 }
 711
 712 arith_t FAST_FUNC
 713 arith(arith_state_t *math_state, const char *expr)
 714 {
 715         math_state->errmsg = NULL;
 716         math_state->list_of_recursed_names = NULL;
 717         return evaluate_string(math_state, expr);
 718 }
 719
 720 /*
 721  * Copyright (c) 1989, 1991, 1993, 1994
 722  *      The Regents of the University of California.  All rights reserved.
 723  *
 724  * This code is derived from software contributed to Berkeley by
 725  * Kenneth Almquist.
 726  *
 727  * Redistribution and use in source and binary forms, with or without
 728  * modification, are permitted provided that the following conditions
 729  * are met:
 730  * 1. Redistributions of source code must retain the above copyright
 731  *    notice, this list of conditions and the following disclaimer.
 732  * 2. Redistributions in binary form must reproduce the above copyright
 733  *    notice, this list of conditions and the following disclaimer in the
 734  *    documentation and/or other materials provided with the distribution.
 735  * 3. Neither the name of the University nor the names of its contributors
 736  *    may be used to endorse or promote products derived from this software
 737  *    without specific prior written permission.
 738  *
 739  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 740  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 741  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 742  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 743  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 744  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 745  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 746  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 747  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 748  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 749  * SUCH DAMAGE.
 750  */