source: MondoRescue/branches/3.3/mindi-busybox/shell/math.c@ 3621

Last change on this file since 3621 was 3621, checked in by Bruno Cornec, 7 years ago

New 3?3 banch for incorporation of latest busybox 1.25. Changing minor version to handle potential incompatibilities.
  • Property svn:eol-style set to native
File size: 23.2 KB
Line 
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
123typedef 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
215static int
216is_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
225static int
226is_right_associative(operator prec)
227{
228 return prec == PREC(TOK_ASSIGN)
229 || prec == PREC(TOK_EXPONENT)
230 || prec == PREC(TOK_CONDITIONAL);
231}
232
233
234typedef 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
248typedef struct remembered_name {
249 struct remembered_name *next;
250 const char *var;
251} remembered_name;
252
253
254static arith_t FAST_FUNC
255evaluate_string(arith_state_t *math_state, const char *expr);
256
257static const char*
258arith_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 */
299static NOINLINE const char*
300arith_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 */
471static 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
516static arith_t FAST_FUNC
517evaluate_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
719arith_t FAST_FUNC
720arith(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 */
Note: See TracBrowser for help on using the repository browser.