blob: 006221b6a4e7988dbbd82ca5386b55c16afdf834
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 | || op == TOK_REM || op == TOK_REM_ASSIGN) { |
420 | /* |
421 | * bash 4.2.45 x86 64bit: SEGV on 'echo $((2**63 / -1))' |
422 | * |
423 | * MAX_NEGATIVE_INT / -1 = MAX_POSITIVE_INT+1 |
424 | * and thus is not representable. |
425 | * Some CPUs segfault trying such op. |
426 | * Others overflow MAX_POSITIVE_INT+1 to |
427 | * MAX_NEGATIVE_INT (0x7fff+1 = 0x8000). |
428 | * Make sure to at least not SEGV here: |
429 | */ |
430 | if (right_side_val == -1 |
431 | && rez << 1 == 0 /* MAX_NEGATIVE_INT or 0 */ |
432 | ) { |
433 | right_side_val = 1; |
434 | } |
435 | if (op == TOK_DIV || op == TOK_DIV_ASSIGN) |
436 | rez /= right_side_val; |
437 | else { |
438 | rez %= right_side_val; |
439 | } |
440 | } |
441 | } |
442 | |
443 | if (is_assign_op(op)) { |
444 | char buf[sizeof(arith_t)*3 + 2]; |
445 | |
446 | if (top_of_stack->var == NULL) { |
447 | /* Hmm, 1=2 ? */ |
448 | //TODO: actually, bash allows ++7 but for some reason it evals to 7, not 8 |
449 | goto err; |
450 | } |
451 | /* Save to shell variable */ |
452 | sprintf(buf, ARITH_FMT, rez); |
453 | setvar(top_of_stack->var, buf); |
454 | /* After saving, make previous value for v++ or v-- */ |
455 | if (op == TOK_POST_INC) |
456 | rez--; |
457 | else if (op == TOK_POST_DEC) |
458 | rez++; |
459 | } |
460 | |
461 | top_of_stack->val = rez; |
462 | /* Erase var name, it is just a number now */ |
463 | top_of_stack->var = NULL; |
464 | return NULL; |
465 | err: |
466 | return "arithmetic syntax error"; |
467 | #undef NUMPTR |
468 | } |
469 | |
470 | /* longest must be first */ |
471 | static const char op_tokens[] ALIGN1 = { |
472 | '<','<','=',0, TOK_LSHIFT_ASSIGN, |
473 | '>','>','=',0, TOK_RSHIFT_ASSIGN, |
474 | '<','<', 0, TOK_LSHIFT, |
475 | '>','>', 0, TOK_RSHIFT, |
476 | '|','|', 0, TOK_OR, |
477 | '&','&', 0, TOK_AND, |
478 | '!','=', 0, TOK_NE, |
479 | '<','=', 0, TOK_LE, |
480 | '>','=', 0, TOK_GE, |
481 | '=','=', 0, TOK_EQ, |
482 | '|','=', 0, TOK_OR_ASSIGN, |
483 | '&','=', 0, TOK_AND_ASSIGN, |
484 | '*','=', 0, TOK_MUL_ASSIGN, |
485 | '/','=', 0, TOK_DIV_ASSIGN, |
486 | '%','=', 0, TOK_REM_ASSIGN, |
487 | '+','=', 0, TOK_PLUS_ASSIGN, |
488 | '-','=', 0, TOK_MINUS_ASSIGN, |
489 | '-','-', 0, TOK_POST_DEC, |
490 | '^','=', 0, TOK_XOR_ASSIGN, |
491 | '+','+', 0, TOK_POST_INC, |
492 | '*','*', 0, TOK_EXPONENT, |
493 | '!', 0, TOK_NOT, |
494 | '<', 0, TOK_LT, |
495 | '>', 0, TOK_GT, |
496 | '=', 0, TOK_ASSIGN, |
497 | '|', 0, TOK_BOR, |
498 | '&', 0, TOK_BAND, |
499 | '*', 0, TOK_MUL, |
500 | '/', 0, TOK_DIV, |
501 | '%', 0, TOK_REM, |
502 | '+', 0, TOK_ADD, |
503 | '-', 0, TOK_SUB, |
504 | '^', 0, TOK_BXOR, |
505 | /* uniq */ |
506 | '~', 0, TOK_BNOT, |
507 | ',', 0, TOK_COMMA, |
508 | '?', 0, TOK_CONDITIONAL, |
509 | ':', 0, TOK_CONDITIONAL_SEP, |
510 | ')', 0, TOK_RPAREN, |
511 | '(', 0, TOK_LPAREN, |
512 | 0 |
513 | }; |
514 | #define ptr_to_rparen (&op_tokens[sizeof(op_tokens)-7]) |
515 | |
516 | static arith_t FAST_FUNC |
517 | evaluate_string(arith_state_t *math_state, const char *expr) |
518 | { |
519 | operator lasttok; |
520 | const char *errmsg; |
521 | const char *start_expr = expr = skip_whitespace(expr); |
522 | unsigned expr_len = strlen(expr) + 2; |
523 | /* Stack of integers */ |
524 | /* The proof that there can be no more than strlen(startbuf)/2+1 |
525 | * integers in any given correct or incorrect expression |
526 | * is left as an exercise to the reader. */ |
527 | var_or_num_t *const numstack = alloca((expr_len / 2) * sizeof(numstack[0])); |
528 | var_or_num_t *numstackptr = numstack; |
529 | /* Stack of operator tokens */ |
530 | operator *const stack = alloca(expr_len * sizeof(stack[0])); |
531 | operator *stackptr = stack; |
532 | |
533 | /* Start with a left paren */ |
534 | *stackptr++ = lasttok = TOK_LPAREN; |
535 | errmsg = NULL; |
536 | |
537 | while (1) { |
538 | const char *p; |
539 | operator op; |
540 | operator prec; |
541 | char arithval; |
542 | |
543 | expr = skip_whitespace(expr); |
544 | arithval = *expr; |
545 | if (arithval == '\0') { |
546 | if (expr == start_expr) { |
547 | /* Null expression */ |
548 | numstack->val = 0; |
549 | goto ret; |
550 | } |
551 | |
552 | /* This is only reached after all tokens have been extracted from the |
553 | * input stream. If there are still tokens on the operator stack, they |
554 | * are to be applied in order. At the end, there should be a final |
555 | * result on the integer stack */ |
556 | |
557 | if (expr != ptr_to_rparen + 1) { |
558 | /* If we haven't done so already, |
559 | * append a closing right paren |
560 | * and let the loop process it */ |
561 | expr = ptr_to_rparen; |
562 | continue; |
563 | } |
564 | /* At this point, we're done with the expression */ |
565 | if (numstackptr != numstack + 1) { |
566 | /* ...but if there isn't, it's bad */ |
567 | goto err; |
568 | } |
569 | if (numstack->var) { |
570 | /* expression is $((var)) only, lookup now */ |
571 | errmsg = arith_lookup_val(math_state, numstack); |
572 | } |
573 | goto ret; |
574 | } |
575 | |
576 | p = endofname(expr); |
577 | if (p != expr) { |
578 | /* Name */ |
579 | size_t var_name_size = (p-expr) + 1; /* +1 for NUL */ |
580 | numstackptr->var = alloca(var_name_size); |
581 | safe_strncpy(numstackptr->var, expr, var_name_size); |
582 | expr = p; |
583 | num: |
584 | numstackptr->second_val_present = 0; |
585 | numstackptr++; |
586 | lasttok = TOK_NUM; |
587 | continue; |
588 | } |
589 | |
590 | if (isdigit(arithval)) { |
591 | /* Number */ |
592 | numstackptr->var = NULL; |
593 | errno = 0; |
594 | numstackptr->val = strto_arith_t(expr, (char**) &expr, 0); |
595 | if (errno) |
596 | numstackptr->val = 0; /* bash compat */ |
597 | goto num; |
598 | } |
599 | |
600 | /* Should be an operator */ |
601 | p = op_tokens; |
602 | while (1) { |
603 | // TODO: bash allows 7+++v, treats it as 7 + ++v |
604 | // we treat it as 7++ + v and reject |
605 | /* Compare expr to current op_tokens[] element */ |
606 | const char *e = expr; |
607 | while (1) { |
608 | if (*p == '\0') { |
609 | /* Match: operator is found */ |
610 | expr = e; |
611 | goto tok_found; |
612 | } |
613 | if (*p != *e) |
614 | break; |
615 | p++; |
616 | e++; |
617 | } |
618 | /* No match, go to next element of op_tokens[] */ |
619 | while (*p) |
620 | p++; |
621 | p += 2; /* skip NUL and TOK_foo bytes */ |
622 | if (*p == '\0') { |
623 | /* No next element, operator not found */ |
624 | //math_state->syntax_error_at = expr; |
625 | goto err; |
626 | } |
627 | } |
628 | tok_found: |
629 | op = p[1]; /* fetch TOK_foo value */ |
630 | /* NB: expr now points past the operator */ |
631 | |
632 | /* post grammar: a++ reduce to num */ |
633 | if (lasttok == TOK_POST_INC || lasttok == TOK_POST_DEC) |
634 | lasttok = TOK_NUM; |
635 | |
636 | /* Plus and minus are binary (not unary) _only_ if the last |
637 | * token was a number, or a right paren (which pretends to be |
638 | * a number, since it evaluates to one). Think about it. |
639 | * It makes sense. */ |
640 | if (lasttok != TOK_NUM) { |
641 | switch (op) { |
642 | case TOK_ADD: |
643 | op = TOK_UPLUS; |
644 | break; |
645 | case TOK_SUB: |
646 | op = TOK_UMINUS; |
647 | break; |
648 | case TOK_POST_INC: |
649 | op = TOK_PRE_INC; |
650 | break; |
651 | case TOK_POST_DEC: |
652 | op = TOK_PRE_DEC; |
653 | break; |
654 | } |
655 | } |
656 | /* We don't want an unary operator to cause recursive descent on the |
657 | * stack, because there can be many in a row and it could cause an |
658 | * operator to be evaluated before its argument is pushed onto the |
659 | * integer stack. |
660 | * But for binary operators, "apply" everything on the operator |
661 | * stack until we find an operator with a lesser priority than the |
662 | * one we have just extracted. If op is right-associative, |
663 | * then stop "applying" on the equal priority too. |
664 | * Left paren is given the lowest priority so it will never be |
665 | * "applied" in this way. |
666 | */ |
667 | prec = PREC(op); |
668 | if ((prec > 0 && prec < UNARYPREC) || prec == SPEC_PREC) { |
669 | /* not left paren or unary */ |
670 | if (lasttok != TOK_NUM) { |
671 | /* binary op must be preceded by a num */ |
672 | goto err; |
673 | } |
674 | while (stackptr != stack) { |
675 | operator prev_op = *--stackptr; |
676 | if (op == TOK_RPAREN) { |
677 | /* The algorithm employed here is simple: while we don't |
678 | * hit an open paren nor the bottom of the stack, pop |
679 | * tokens and apply them */ |
680 | if (prev_op == TOK_LPAREN) { |
681 | /* Any operator directly after a |
682 | * close paren should consider itself binary */ |
683 | lasttok = TOK_NUM; |
684 | goto next; |
685 | } |
686 | } else { |
687 | operator prev_prec = PREC(prev_op); |
688 | fix_assignment_prec(prec); |
689 | fix_assignment_prec(prev_prec); |
690 | if (prev_prec < prec |
691 | || (prev_prec == prec && is_right_associative(prec)) |
692 | ) { |
693 | stackptr++; |
694 | break; |
695 | } |
696 | } |
697 | errmsg = arith_apply(math_state, prev_op, numstack, &numstackptr); |
698 | if (errmsg) |
699 | goto err_with_custom_msg; |
700 | } |
701 | if (op == TOK_RPAREN) |
702 | goto err; |
703 | } |
704 | |
705 | /* Push this operator to the stack and remember it */ |
706 | *stackptr++ = lasttok = op; |
707 | next: ; |
708 | } /* while (1) */ |
709 | |
710 | err: |
711 | errmsg = "arithmetic syntax error"; |
712 | err_with_custom_msg: |
713 | numstack->val = -1; |
714 | ret: |
715 | math_state->errmsg = errmsg; |
716 | return numstack->val; |
717 | } |
718 | |
719 | arith_t FAST_FUNC |
720 | arith(arith_state_t *math_state, const char *expr) |
721 | { |
722 | math_state->errmsg = NULL; |
723 | math_state->list_of_recursed_names = NULL; |
724 | return evaluate_string(math_state, expr); |
725 | } |
726 | |
727 | /* |
728 | * Copyright (c) 1989, 1991, 1993, 1994 |
729 | * The Regents of the University of California. All rights reserved. |
730 | * |
731 | * This code is derived from software contributed to Berkeley by |
732 | * Kenneth Almquist. |
733 | * |
734 | * Redistribution and use in source and binary forms, with or without |
735 | * modification, are permitted provided that the following conditions |
736 | * are met: |
737 | * 1. Redistributions of source code must retain the above copyright |
738 | * notice, this list of conditions and the following disclaimer. |
739 | * 2. Redistributions in binary form must reproduce the above copyright |
740 | * notice, this list of conditions and the following disclaimer in the |
741 | * documentation and/or other materials provided with the distribution. |
742 | * 3. Neither the name of the University nor the names of its contributors |
743 | * may be used to endorse or promote products derived from this software |
744 | * without specific prior written permission. |
745 | * |
746 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
747 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
748 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
749 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE |
750 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
751 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
752 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
753 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
754 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
755 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
756 | * SUCH DAMAGE. |
757 | */ |
758 |