]> git.ipfire.org Git - thirdparty/bash.git/blob - expr.c
66e120d951ae47088b4437eb64713fc4eb93d54f
[thirdparty/bash.git] / expr.c
1 /* expr.c -- arithmetic expression evaluation. */
2
3 /* Copyright (C) 1990-2021 Free Software Foundation, Inc.
4
5 This file is part of GNU Bash, the Bourne Again SHell.
6
7 Bash is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
11
12 Bash is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with Bash. If not, see <http://www.gnu.org/licenses/>.
19 */
20
21 /*
22 All arithmetic is done as intmax_t integers with no checking for overflow
23 (though division by 0 is caught and flagged as an error).
24
25 The following operators are handled, grouped into a set of levels in
26 order of decreasing precedence.
27
28 "id++", "id--" [post-increment and post-decrement]
29 "-", "+" [(unary operators)]
30 "++id", "--id" [pre-increment and pre-decrement]
31 "!", "~"
32 "**" [(exponentiation)]
33 "*", "/", "%"
34 "+", "-"
35 "<<", ">>"
36 "<=", ">=", "<", ">"
37 "==", "!="
38 "&"
39 "^"
40 "|"
41 "&&"
42 "||"
43 "expr ? expr : expr"
44 "=", "*=", "/=", "%=", "+=", "-=", "<<=", ">>=", "&=", "^=", "|="
45 , [comma]
46
47 (Note that most of these operators have special meaning to bash, and an
48 entire expression should be quoted, e.g. "a=$a+1" or "a=a+1" to ensure
49 that it is passed intact to the evaluator when using `let'. When using
50 the $[] or $(( )) forms, the text between the `[' and `]' or `((' and `))'
51 is treated as if in double quotes.)
52
53 Sub-expressions within parentheses have a precedence level greater than
54 all of the above levels and are evaluated first. Within a single prece-
55 dence group, evaluation is left-to-right, except for the arithmetic
56 assignment operator (`='), which is evaluated right-to-left (as in C).
57
58 The expression evaluator returns the value of the expression (assignment
59 statements have as a value what is returned by the RHS). The `let'
60 builtin, on the other hand, returns 0 if the last expression evaluates to
61 a non-zero, and 1 otherwise.
62
63 Implementation is a recursive-descent parser.
64
65 Chet Ramey
66 chet@po.cwru.edu
67 */
68
69 #include "config.h"
70
71 #include <stdio.h>
72 #include "bashansi.h"
73
74 #if defined (HAVE_UNISTD_H)
75 # ifdef _MINIX
76 # include <sys/types.h>
77 # endif
78 # include <unistd.h>
79 #endif
80
81 #include "chartypes.h"
82 #include "bashintl.h"
83
84 #include "shell.h"
85 #include "arrayfunc.h"
86 #include "execute_cmd.h"
87 #include "flags.h"
88 #include "subst.h"
89 #include "typemax.h" /* INTMAX_MAX, INTMAX_MIN */
90
91 /* Because of the $((...)) construct, expressions may include newlines.
92 Here is a macro which accepts newlines, tabs and spaces as whitespace. */
93 #define cr_whitespace(c) (whitespace(c) || ((c) == '\n'))
94
95 /* Size be which the expression stack grows when necessary. */
96 #define EXPR_STACK_GROW_SIZE 10
97
98 /* Maximum amount of recursion allowed. This prevents a non-integer
99 variable such as "num=num+2" from infinitely adding to itself when
100 "let num=num+2" is given. */
101 #define MAX_EXPR_RECURSION_LEVEL 1024
102
103 /* The Tokens. Singing "The Lion Sleeps Tonight". */
104
105 #define EQEQ 1 /* "==" */
106 #define NEQ 2 /* "!=" */
107 #define LEQ 3 /* "<=" */
108 #define GEQ 4 /* ">=" */
109 #define STR 5 /* string */
110 #define NUM 6 /* number */
111 #define LAND 7 /* "&&" Logical AND */
112 #define LOR 8 /* "||" Logical OR */
113 #define LSH 9 /* "<<" Left SHift */
114 #define RSH 10 /* ">>" Right SHift */
115 #define OP_ASSIGN 11 /* op= expassign as in Posix.2 */
116 #define COND 12 /* exp1 ? exp2 : exp3 */
117 #define POWER 13 /* exp1**exp2 */
118 #define PREINC 14 /* ++var */
119 #define PREDEC 15 /* --var */
120 #define POSTINC 16 /* var++ */
121 #define POSTDEC 17 /* var-- */
122 #define EQ '='
123 #define GT '>'
124 #define LT '<'
125 #define PLUS '+'
126 #define MINUS '-'
127 #define MUL '*'
128 #define DIV '/'
129 #define MOD '%'
130 #define NOT '!'
131 #define LPAR '('
132 #define RPAR ')'
133 #define BAND '&' /* Bitwise AND */
134 #define BOR '|' /* Bitwise OR. */
135 #define BXOR '^' /* Bitwise eXclusive OR. */
136 #define BNOT '~' /* Bitwise NOT; Two's complement. */
137 #define QUES '?'
138 #define COL ':'
139 #define COMMA ','
140
141 /* This should be the function corresponding to the operator with the
142 lowest precedence. */
143 #define EXP_LOWEST expcomma
144
145 #ifndef MAX_INT_LEN
146 # define MAX_INT_LEN 32
147 #endif
148
149 struct lvalue
150 {
151 char *tokstr; /* possibly-rewritten lvalue if not NULL */
152 intmax_t tokval; /* expression evaluated value */
153 SHELL_VAR *tokvar; /* variable described by array or var reference */
154 intmax_t ind; /* array index if not -1 */
155 };
156
157 /* A structure defining a single expression context. */
158 typedef struct {
159 int curtok, lasttok;
160 char *expression, *tp, *lasttp;
161 intmax_t tokval;
162 char *tokstr;
163 int noeval;
164 struct lvalue lval;
165 } EXPR_CONTEXT;
166
167 static char *expression; /* The current expression */
168 static char *tp; /* token lexical position */
169 static char *lasttp; /* pointer to last token position */
170 static int curtok; /* the current token */
171 static int lasttok; /* the previous token */
172 static int assigntok; /* the OP in OP= */
173 static char *tokstr; /* current token string */
174 static intmax_t tokval; /* current token value */
175 static int noeval; /* set to 1 if no assignment to be done */
176 static procenv_t evalbuf;
177
178 /* set to 1 if the expression has already been run through word expansion */
179 static int already_expanded;
180
181 static struct lvalue curlval = {0, 0, 0, -1};
182 static struct lvalue lastlval = {0, 0, 0, -1};
183
184 static int _is_arithop PARAMS((int));
185 static void readtok PARAMS((void)); /* lexical analyzer */
186
187 static void init_lvalue PARAMS((struct lvalue *));
188 static struct lvalue *alloc_lvalue PARAMS((void));
189 static void free_lvalue PARAMS((struct lvalue *));
190
191 static intmax_t expr_streval PARAMS((char *, int, struct lvalue *));
192 static intmax_t strlong PARAMS((char *));
193 static void evalerror PARAMS((const char *));
194
195 static void pushexp PARAMS((void));
196 static void popexp PARAMS((void));
197 static void expr_unwind PARAMS((void));
198 static void expr_bind_variable PARAMS((char *, char *));
199 #if defined (ARRAY_VARS)
200 static void expr_bind_array_element PARAMS((char *, arrayind_t, char *));
201 #endif
202
203 static intmax_t subexpr PARAMS((char *));
204
205 static intmax_t expcomma PARAMS((void));
206 static intmax_t expassign PARAMS((void));
207 static intmax_t expcond PARAMS((void));
208 static intmax_t explor PARAMS((void));
209 static intmax_t expland PARAMS((void));
210 static intmax_t expbor PARAMS((void));
211 static intmax_t expbxor PARAMS((void));
212 static intmax_t expband PARAMS((void));
213 static intmax_t exp5 PARAMS((void));
214 static intmax_t exp4 PARAMS((void));
215 static intmax_t expshift PARAMS((void));
216 static intmax_t exp3 PARAMS((void));
217 static intmax_t expmuldiv PARAMS((void));
218 static intmax_t exppower PARAMS((void));
219 static intmax_t exp1 PARAMS((void));
220 static intmax_t exp0 PARAMS((void));
221
222 /* Global var which contains the stack of expression contexts. */
223 static EXPR_CONTEXT **expr_stack;
224 static int expr_depth; /* Location in the stack. */
225 static int expr_stack_size; /* Number of slots already allocated. */
226
227 #if defined (ARRAY_VARS)
228 extern const char * const bash_badsub_errmsg;
229 #endif
230
231 #define SAVETOK(X) \
232 do { \
233 (X)->curtok = curtok; \
234 (X)->lasttok = lasttok; \
235 (X)->tp = tp; \
236 (X)->lasttp = lasttp; \
237 (X)->tokval = tokval; \
238 (X)->tokstr = tokstr; \
239 (X)->noeval = noeval; \
240 (X)->lval = curlval; \
241 } while (0)
242
243 #define RESTORETOK(X) \
244 do { \
245 curtok = (X)->curtok; \
246 lasttok = (X)->lasttok; \
247 tp = (X)->tp; \
248 lasttp = (X)->lasttp; \
249 tokval = (X)->tokval; \
250 tokstr = (X)->tokstr; \
251 noeval = (X)->noeval; \
252 curlval = (X)->lval; \
253 } while (0)
254
255 /* Push and save away the contents of the globals describing the
256 current expression context. */
257 static void
258 pushexp ()
259 {
260 EXPR_CONTEXT *context;
261
262 if (expr_depth >= MAX_EXPR_RECURSION_LEVEL)
263 evalerror (_("expression recursion level exceeded"));
264
265 if (expr_depth >= expr_stack_size)
266 {
267 expr_stack_size += EXPR_STACK_GROW_SIZE;
268 expr_stack = (EXPR_CONTEXT **)xrealloc (expr_stack, expr_stack_size * sizeof (EXPR_CONTEXT *));
269 }
270
271 context = (EXPR_CONTEXT *)xmalloc (sizeof (EXPR_CONTEXT));
272
273 context->expression = expression;
274 SAVETOK(context);
275
276 expr_stack[expr_depth++] = context;
277 }
278
279 /* Pop the the contents of the expression context stack into the
280 globals describing the current expression context. */
281 static void
282 popexp ()
283 {
284 EXPR_CONTEXT *context;
285
286 if (expr_depth <= 0)
287 {
288 /* See the comment at the top of evalexp() for an explanation of why
289 this is done. */
290 expression = lasttp = 0;
291 evalerror (_("recursion stack underflow"));
292 }
293
294 context = expr_stack[--expr_depth];
295
296 expression = context->expression;
297 RESTORETOK (context);
298
299 free (context);
300 }
301
302 static void
303 expr_unwind ()
304 {
305 while (--expr_depth > 0)
306 {
307 if (expr_stack[expr_depth]->tokstr)
308 free (expr_stack[expr_depth]->tokstr);
309
310 if (expr_stack[expr_depth]->expression)
311 free (expr_stack[expr_depth]->expression);
312
313 free (expr_stack[expr_depth]);
314 }
315 if (expr_depth == 0)
316 free (expr_stack[expr_depth]); /* free the allocated EXPR_CONTEXT */
317
318 noeval = 0; /* XXX */
319 }
320
321 static void
322 expr_bind_variable (lhs, rhs)
323 char *lhs, *rhs;
324 {
325 SHELL_VAR *v;
326 int aflags;
327
328 if (lhs == 0 || *lhs == 0)
329 return; /* XXX */
330
331 #if defined (ARRAY_VARS)
332 aflags = (assoc_expand_once && already_expanded) ? ASS_NOEXPAND : 0;
333 aflags |= ASS_ALLOWALLSUB; /* allow assoc[@]=value */
334 #else
335 aflags = 0;
336 #endif
337 v = bind_int_variable (lhs, rhs, aflags);
338 if (v && (readonly_p (v) || noassign_p (v)))
339 sh_longjmp (evalbuf, 1); /* variable assignment error */
340 stupidly_hack_special_variables (lhs);
341 }
342
343 #if defined (ARRAY_VARS)
344 /* This is similar to the logic in arrayfunc.c:valid_array_reference when
345 you pass VA_NOEXPAND. */
346 static int
347 expr_skipsubscript (vp, cp)
348 char *vp, *cp;
349 {
350 int flags, isassoc;
351 SHELL_VAR *entry;
352
353 isassoc = 0;
354 entry = 0;
355 if (assoc_expand_once & already_expanded)
356 {
357 *cp = '\0';
358 isassoc = legal_identifier (vp) && (entry = find_variable (vp)) && assoc_p (entry);
359 *cp = '['; /* ] */
360 }
361 flags = (isassoc && assoc_expand_once && already_expanded) ? VA_NOEXPAND : 0;
362 return (skipsubscript (cp, 0, flags));
363 }
364
365 /* Rewrite tok, which is of the form vname[expression], to vname[ind], where
366 IND is the already-calculated value of expression. */
367 static void
368 expr_bind_array_element (tok, ind, rhs)
369 char *tok;
370 arrayind_t ind;
371 char *rhs;
372 {
373 char *lhs, *vname;
374 size_t llen;
375 char ibuf[INT_STRLEN_BOUND (arrayind_t) + 1], *istr;
376
377 istr = fmtumax (ind, 10, ibuf, sizeof (ibuf), 0);
378 vname = array_variable_name (tok, 0, (char **)NULL, (int *)NULL);
379
380 llen = strlen (vname) + sizeof (ibuf) + 3;
381 lhs = xmalloc (llen);
382
383 sprintf (lhs, "%s[%s]", vname, istr); /* XXX */
384
385 /*itrace("expr_bind_array_element: %s=%s", lhs, rhs);*/
386 expr_bind_variable (lhs, rhs);
387 free (vname);
388 free (lhs);
389 }
390 #endif /* ARRAY_VARS */
391
392 /* Evaluate EXPR, and return the arithmetic result. If VALIDP is
393 non-null, a zero is stored into the location to which it points
394 if the expression is invalid, non-zero otherwise. If a non-zero
395 value is returned in *VALIDP, the return value of evalexp() may
396 be used.
397
398 The `while' loop after the longjmp is caught relies on the above
399 implementation of pushexp and popexp leaving in expr_stack[0] the
400 values that the variables had when the program started. That is,
401 the first things saved are the initial values of the variables that
402 were assigned at program startup or by the compiler. Therefore, it is
403 safe to let the loop terminate when expr_depth == 0, without freeing up
404 any of the expr_depth[0] stuff. */
405 intmax_t
406 evalexp (expr, flags, validp)
407 char *expr;
408 int flags;
409 int *validp;
410 {
411 intmax_t val;
412 int c;
413 procenv_t oevalbuf;
414
415 val = 0;
416 noeval = 0;
417 already_expanded = (flags&EXP_EXPANDED);
418
419 FASTCOPY (evalbuf, oevalbuf, sizeof (evalbuf));
420
421 c = setjmp_nosigs (evalbuf);
422
423 if (c)
424 {
425 FREE (tokstr);
426 FREE (expression);
427 tokstr = expression = (char *)NULL;
428
429 expr_unwind ();
430 expr_depth = 0; /* XXX - make sure */
431
432 /* We copy in case we've called evalexp recursively */
433 FASTCOPY (oevalbuf, evalbuf, sizeof (evalbuf));
434
435 if (validp)
436 *validp = 0;
437 return (0);
438 }
439
440 val = subexpr (expr);
441
442 if (validp)
443 *validp = 1;
444
445 FASTCOPY (oevalbuf, evalbuf, sizeof (evalbuf));
446
447 return (val);
448 }
449
450 static intmax_t
451 subexpr (expr)
452 char *expr;
453 {
454 intmax_t val;
455 char *p;
456
457 for (p = expr; p && *p && cr_whitespace (*p); p++)
458 ;
459
460 if (p == NULL || *p == '\0')
461 return (0);
462
463 pushexp ();
464 expression = savestring (expr);
465 tp = expression;
466
467 curtok = lasttok = 0;
468 tokstr = (char *)NULL;
469 tokval = 0;
470 init_lvalue (&curlval);
471 lastlval = curlval;
472
473 readtok ();
474
475 val = EXP_LOWEST ();
476
477 /*TAG:bash-5.3 make it clear that these are arithmetic syntax errors */
478 if (curtok != 0)
479 evalerror (_("syntax error in expression"));
480
481 FREE (tokstr);
482 FREE (expression);
483
484 popexp ();
485
486 return val;
487 }
488
489 static intmax_t
490 expcomma ()
491 {
492 register intmax_t value;
493
494 value = expassign ();
495 while (curtok == COMMA)
496 {
497 readtok ();
498 value = expassign ();
499 }
500
501 return value;
502 }
503
504 static intmax_t
505 expassign ()
506 {
507 register intmax_t value;
508 char *lhs, *rhs;
509 arrayind_t lind;
510 #if defined (HAVE_IMAXDIV)
511 imaxdiv_t idiv;
512 #endif
513
514 value = expcond ();
515 if (curtok == EQ || curtok == OP_ASSIGN)
516 {
517 int special, op;
518 intmax_t lvalue;
519
520 special = curtok == OP_ASSIGN;
521
522 if (lasttok != STR)
523 evalerror (_("attempted assignment to non-variable"));
524
525 if (special)
526 {
527 op = assigntok; /* a OP= b */
528 lvalue = value;
529 }
530
531 if (tokstr == 0)
532 evalerror (_("syntax error in variable assignment"));
533
534 /* XXX - watch out for pointer aliasing issues here */
535 lhs = savestring (tokstr);
536 /* save ind in case rhs is string var and evaluation overwrites it */
537 lind = curlval.ind;
538 readtok ();
539 value = expassign ();
540
541 if (special)
542 {
543 if ((op == DIV || op == MOD) && value == 0)
544 {
545 if (noeval == 0)
546 evalerror (_("division by 0"));
547 else
548 value = 1;
549 }
550
551 switch (op)
552 {
553 case MUL:
554 /* Handle INTMAX_MIN and INTMAX_MAX * -1 specially here? */
555 lvalue *= value;
556 break;
557 case DIV:
558 case MOD:
559 if (lvalue == INTMAX_MIN && value == -1)
560 lvalue = (op == DIV) ? INTMAX_MIN : 0;
561 else
562 #if HAVE_IMAXDIV
563 {
564 idiv = imaxdiv (lvalue, value);
565 lvalue = (op == DIV) ? idiv.quot : idiv.rem;
566 }
567 #else
568 lvalue = (op == DIV) ? lvalue / value : lvalue % value;
569 #endif
570 break;
571 case PLUS:
572 lvalue += value;
573 break;
574 case MINUS:
575 lvalue -= value;
576 break;
577 case LSH:
578 lvalue <<= value;
579 break;
580 case RSH:
581 lvalue >>= value;
582 break;
583 case BAND:
584 lvalue &= value;
585 break;
586 case BOR:
587 lvalue |= value;
588 break;
589 case BXOR:
590 lvalue ^= value;
591 break;
592 default:
593 free (lhs);
594 evalerror (_("bug: bad expassign token"));
595 break;
596 }
597 value = lvalue;
598 }
599
600 rhs = itos (value);
601 if (noeval == 0)
602 {
603 #if defined (ARRAY_VARS)
604 if (lind != -1)
605 expr_bind_array_element (lhs, lind, rhs);
606 else
607 #endif
608 expr_bind_variable (lhs, rhs);
609 }
610 if (curlval.tokstr && curlval.tokstr == tokstr)
611 init_lvalue (&curlval);
612
613 free (rhs);
614 free (lhs);
615 FREE (tokstr);
616 tokstr = (char *)NULL; /* For freeing on errors. */
617 }
618
619 return (value);
620 }
621
622 /* Conditional expression (expr?expr:expr) */
623 static intmax_t
624 expcond ()
625 {
626 intmax_t cval, val1, val2, rval;
627 int set_noeval;
628
629 set_noeval = 0;
630 rval = cval = explor ();
631 if (curtok == QUES) /* found conditional expr */
632 {
633 if (cval == 0)
634 {
635 set_noeval = 1;
636 noeval++;
637 }
638
639 readtok ();
640 if (curtok == 0 || curtok == COL)
641 evalerror (_("expression expected"));
642
643 val1 = EXP_LOWEST ();
644
645 if (set_noeval)
646 noeval--;
647 if (curtok != COL)
648 evalerror (_("`:' expected for conditional expression"));
649
650 set_noeval = 0;
651 if (cval)
652 {
653 set_noeval = 1;
654 noeval++;
655 }
656
657 readtok ();
658 if (curtok == 0)
659 evalerror (_("expression expected"));
660 val2 = expcond ();
661
662 if (set_noeval)
663 noeval--;
664 rval = cval ? val1 : val2;
665 lasttok = COND;
666 }
667 return rval;
668 }
669
670 /* Logical OR. */
671 static intmax_t
672 explor ()
673 {
674 register intmax_t val1, val2;
675 int set_noeval;
676
677 val1 = expland ();
678
679 while (curtok == LOR)
680 {
681 set_noeval = 0;
682 if (val1 != 0)
683 {
684 noeval++;
685 set_noeval = 1;
686 }
687 readtok ();
688 val2 = expland ();
689 if (set_noeval)
690 noeval--;
691 val1 = val1 || val2;
692 lasttok = LOR;
693 }
694
695 return (val1);
696 }
697
698 /* Logical AND. */
699 static intmax_t
700 expland ()
701 {
702 register intmax_t val1, val2;
703 int set_noeval;
704
705 val1 = expbor ();
706
707 while (curtok == LAND)
708 {
709 set_noeval = 0;
710 if (val1 == 0)
711 {
712 set_noeval = 1;
713 noeval++;
714 }
715 readtok ();
716 val2 = expbor ();
717 if (set_noeval)
718 noeval--;
719 val1 = val1 && val2;
720 lasttok = LAND;
721 }
722
723 return (val1);
724 }
725
726 /* Bitwise OR. */
727 static intmax_t
728 expbor ()
729 {
730 register intmax_t val1, val2;
731
732 val1 = expbxor ();
733
734 while (curtok == BOR)
735 {
736 readtok ();
737 val2 = expbxor ();
738 val1 = val1 | val2;
739 lasttok = NUM;
740 }
741
742 return (val1);
743 }
744
745 /* Bitwise XOR. */
746 static intmax_t
747 expbxor ()
748 {
749 register intmax_t val1, val2;
750
751 val1 = expband ();
752
753 while (curtok == BXOR)
754 {
755 readtok ();
756 val2 = expband ();
757 val1 = val1 ^ val2;
758 lasttok = NUM;
759 }
760
761 return (val1);
762 }
763
764 /* Bitwise AND. */
765 static intmax_t
766 expband ()
767 {
768 register intmax_t val1, val2;
769
770 val1 = exp5 ();
771
772 while (curtok == BAND)
773 {
774 readtok ();
775 val2 = exp5 ();
776 val1 = val1 & val2;
777 lasttok = NUM;
778 }
779
780 return (val1);
781 }
782
783 static intmax_t
784 exp5 ()
785 {
786 register intmax_t val1, val2;
787
788 val1 = exp4 ();
789
790 while ((curtok == EQEQ) || (curtok == NEQ))
791 {
792 int op = curtok;
793
794 readtok ();
795 val2 = exp4 ();
796 if (op == EQEQ)
797 val1 = (val1 == val2);
798 else if (op == NEQ)
799 val1 = (val1 != val2);
800 lasttok = NUM;
801 }
802 return (val1);
803 }
804
805 static intmax_t
806 exp4 ()
807 {
808 register intmax_t val1, val2;
809
810 val1 = expshift ();
811 while ((curtok == LEQ) ||
812 (curtok == GEQ) ||
813 (curtok == LT) ||
814 (curtok == GT))
815 {
816 int op = curtok;
817
818 readtok ();
819 val2 = expshift ();
820
821 if (op == LEQ)
822 val1 = val1 <= val2;
823 else if (op == GEQ)
824 val1 = val1 >= val2;
825 else if (op == LT)
826 val1 = val1 < val2;
827 else /* (op == GT) */
828 val1 = val1 > val2;
829 lasttok = NUM;
830 }
831 return (val1);
832 }
833
834 /* Left and right shifts. */
835 static intmax_t
836 expshift ()
837 {
838 register intmax_t val1, val2;
839
840 val1 = exp3 ();
841
842 while ((curtok == LSH) || (curtok == RSH))
843 {
844 int op = curtok;
845
846 readtok ();
847 val2 = exp3 ();
848
849 if (op == LSH)
850 val1 = val1 << val2;
851 else
852 val1 = val1 >> val2;
853 lasttok = NUM;
854 }
855
856 return (val1);
857 }
858
859 static intmax_t
860 exp3 ()
861 {
862 register intmax_t val1, val2;
863
864 val1 = expmuldiv ();
865
866 while ((curtok == PLUS) || (curtok == MINUS))
867 {
868 int op = curtok;
869
870 readtok ();
871 val2 = expmuldiv ();
872
873 if (op == PLUS)
874 val1 += val2;
875 else if (op == MINUS)
876 val1 -= val2;
877 lasttok = NUM;
878 }
879 return (val1);
880 }
881
882 static intmax_t
883 expmuldiv ()
884 {
885 register intmax_t val1, val2;
886 #if defined (HAVE_IMAXDIV)
887 imaxdiv_t idiv;
888 #endif
889
890 val1 = exppower ();
891
892 while ((curtok == MUL) ||
893 (curtok == DIV) ||
894 (curtok == MOD))
895 {
896 int op = curtok;
897 char *stp, *sltp;
898
899 stp = tp;
900 readtok ();
901
902 val2 = exppower ();
903
904 /* Handle division by 0 and twos-complement arithmetic overflow */
905 if (((op == DIV) || (op == MOD)) && (val2 == 0))
906 {
907 if (noeval == 0)
908 {
909 sltp = lasttp;
910 lasttp = stp;
911 while (lasttp && *lasttp && whitespace (*lasttp))
912 lasttp++;
913 evalerror (_("division by 0"));
914 lasttp = sltp;
915 }
916 else
917 val2 = 1;
918 }
919 else if (op == MOD && val1 == INTMAX_MIN && val2 == -1)
920 {
921 val1 = 0;
922 continue;
923 }
924 else if (op == DIV && val1 == INTMAX_MIN && val2 == -1)
925 val2 = 1;
926
927 if (op == MUL)
928 val1 *= val2;
929 else if (op == DIV || op == MOD)
930 #if defined (HAVE_IMAXDIV)
931 {
932 idiv = imaxdiv (val1, val2);
933 val1 = (op == DIV) ? idiv.quot : idiv.rem;
934 }
935 #else
936 val1 = (op == DIV) ? val1 / val2 : val1 % val2;
937 #endif
938 lasttok = NUM;
939 }
940 return (val1);
941 }
942
943 static intmax_t
944 ipow (base, exp)
945 intmax_t base, exp;
946 {
947 intmax_t result;
948
949 result = 1;
950 while (exp)
951 {
952 if (exp & 1)
953 result *= base;
954 exp >>= 1;
955 base *= base;
956 }
957 return result;
958 }
959
960 static intmax_t
961 exppower ()
962 {
963 register intmax_t val1, val2, c;
964
965 val1 = exp1 ();
966 while (curtok == POWER)
967 {
968 readtok ();
969 val2 = exppower (); /* exponentiation is right-associative */
970 lasttok = NUM;
971 if (val2 == 0)
972 return (1);
973 if (val2 < 0)
974 evalerror (_("exponent less than 0"));
975 val1 = ipow (val1, val2);
976 }
977 return (val1);
978 }
979
980 static intmax_t
981 exp1 ()
982 {
983 register intmax_t val;
984
985 if (curtok == NOT)
986 {
987 readtok ();
988 val = !exp1 ();
989 lasttok = NUM;
990 }
991 else if (curtok == BNOT)
992 {
993 readtok ();
994 val = ~exp1 ();
995 lasttok = NUM;
996 }
997 else if (curtok == MINUS)
998 {
999 readtok ();
1000 val = - exp1 ();
1001 lasttok = NUM;
1002 }
1003 else if (curtok == PLUS)
1004 {
1005 readtok ();
1006 val = exp1 ();
1007 lasttok = NUM;
1008 }
1009 else
1010 val = exp0 ();
1011
1012 return (val);
1013 }
1014
1015 static intmax_t
1016 exp0 ()
1017 {
1018 register intmax_t val = 0, v2;
1019 char *vincdec;
1020 int stok;
1021 EXPR_CONTEXT ec;
1022
1023 /* XXX - might need additional logic here to decide whether or not
1024 pre-increment or pre-decrement is legal at this point. */
1025 if (curtok == PREINC || curtok == PREDEC)
1026 {
1027 stok = lasttok = curtok;
1028 readtok ();
1029 if (curtok != STR)
1030 /* readtok() catches this */
1031 evalerror (_("identifier expected after pre-increment or pre-decrement"));
1032
1033 v2 = tokval + ((stok == PREINC) ? 1 : -1);
1034 vincdec = itos (v2);
1035 if (noeval == 0)
1036 {
1037 #if defined (ARRAY_VARS)
1038 if (curlval.ind != -1)
1039 expr_bind_array_element (curlval.tokstr, curlval.ind, vincdec);
1040 else
1041 #endif
1042 if (tokstr)
1043 expr_bind_variable (tokstr, vincdec);
1044 }
1045 free (vincdec);
1046 val = v2;
1047
1048 curtok = NUM; /* make sure --x=7 is flagged as an error */
1049 readtok ();
1050 }
1051 else if (curtok == LPAR)
1052 {
1053 /* XXX - save curlval here? Or entire expression context? */
1054 readtok ();
1055 val = EXP_LOWEST ();
1056
1057 if (curtok != RPAR) /* ( */
1058 evalerror (_("missing `)'"));
1059
1060 /* Skip over closing paren. */
1061 readtok ();
1062 }
1063 else if ((curtok == NUM) || (curtok == STR))
1064 {
1065 val = tokval;
1066 if (curtok == STR)
1067 {
1068 SAVETOK (&ec);
1069 tokstr = (char *)NULL; /* keep it from being freed */
1070 noeval = 1;
1071 readtok ();
1072 stok = curtok;
1073
1074 /* post-increment or post-decrement */
1075 if (stok == POSTINC || stok == POSTDEC)
1076 {
1077 /* restore certain portions of EC */
1078 tokstr = ec.tokstr;
1079 noeval = ec.noeval;
1080 curlval = ec.lval;
1081 lasttok = STR; /* ec.curtok */
1082
1083 v2 = val + ((stok == POSTINC) ? 1 : -1);
1084 vincdec = itos (v2);
1085 if (noeval == 0)
1086 {
1087 #if defined (ARRAY_VARS)
1088 if (curlval.ind != -1)
1089 expr_bind_array_element (curlval.tokstr, curlval.ind, vincdec);
1090 else
1091 #endif
1092 expr_bind_variable (tokstr, vincdec);
1093 }
1094 free (vincdec);
1095 curtok = NUM; /* make sure x++=7 is flagged as an error */
1096 }
1097 else
1098 {
1099 /* XXX - watch out for pointer aliasing issues here */
1100 if (stok == STR) /* free new tokstr before old one is restored */
1101 FREE (tokstr);
1102 RESTORETOK (&ec);
1103 }
1104 }
1105
1106 readtok ();
1107 }
1108 else
1109 evalerror (_("syntax error: operand expected"));
1110
1111 return (val);
1112 }
1113
1114 static void
1115 init_lvalue (lv)
1116 struct lvalue *lv;
1117 {
1118 lv->tokstr = 0;
1119 lv->tokvar = 0;
1120 lv->tokval = lv->ind = -1;
1121 }
1122
1123 static struct lvalue *
1124 alloc_lvalue ()
1125 {
1126 struct lvalue *lv;
1127
1128 lv = xmalloc (sizeof (struct lvalue));
1129 init_lvalue (lv);
1130 return (lv);
1131 }
1132
1133 static void
1134 free_lvalue (lv)
1135 struct lvalue *lv;
1136 {
1137 free (lv); /* should be inlined */
1138 }
1139
1140 static intmax_t
1141 expr_streval (tok, e, lvalue)
1142 char *tok;
1143 int e;
1144 struct lvalue *lvalue;
1145 {
1146 SHELL_VAR *v;
1147 char *value;
1148 intmax_t tval;
1149 int initial_depth;
1150 #if defined (ARRAY_VARS)
1151 arrayind_t ind;
1152 int tflag, aflag;
1153 array_eltstate_t es;
1154 #endif
1155
1156 /*itrace("expr_streval: %s: noeval = %d expanded=%d", tok, noeval, already_expanded);*/
1157 /* If we are suppressing evaluation, just short-circuit here instead of
1158 going through the rest of the evaluator. */
1159 if (noeval)
1160 return (0);
1161
1162 initial_depth = expr_depth;
1163
1164 #if defined (ARRAY_VARS)
1165 tflag = (assoc_expand_once && already_expanded) ? AV_NOEXPAND : 0; /* for a start */
1166 #endif
1167
1168 /* [[[[[ */
1169 #if defined (ARRAY_VARS)
1170 aflag = tflag; /* use a different variable for now */
1171 if (shell_compatibility_level > 51)
1172 aflag |= AV_ATSTARKEYS;
1173 v = (e == ']') ? array_variable_part (tok, tflag, (char **)0, (int *)0) : find_variable (tok);
1174 #else
1175 v = find_variable (tok);
1176 #endif
1177 if (v == 0 && e != ']')
1178 v = find_variable_last_nameref (tok, 0);
1179
1180 if ((v == 0 || invisible_p (v)) && unbound_vars_is_error)
1181 {
1182 #if defined (ARRAY_VARS)
1183 value = (e == ']') ? array_variable_name (tok, tflag, (char **)0, (int *)0) : tok;
1184 #else
1185 value = tok;
1186 #endif
1187
1188 set_exit_status (EXECUTION_FAILURE);
1189 err_unboundvar (value);
1190
1191 #if defined (ARRAY_VARS)
1192 if (e == ']')
1193 FREE (value); /* array_variable_name returns new memory */
1194 #endif
1195
1196 if (no_longjmp_on_fatal_error && interactive_shell)
1197 sh_longjmp (evalbuf, 1);
1198
1199 if (interactive_shell)
1200 {
1201 expr_unwind ();
1202 top_level_cleanup ();
1203 jump_to_top_level (DISCARD);
1204 }
1205 else
1206 jump_to_top_level (FORCE_EOF);
1207 }
1208
1209 #if defined (ARRAY_VARS)
1210 init_eltstate (&es);
1211 es.ind = -1;
1212 /* If the second argument to get_array_value doesn't include AV_ALLOWALL,
1213 we don't allow references like array[@]. In this case, get_array_value
1214 is just like get_variable_value in that it does not return newly-allocated
1215 memory or quote the results. AFLAG is set above and is either AV_NOEXPAND
1216 or 0. */
1217 value = (e == ']') ? get_array_value (tok, aflag, &es) : get_variable_value (v);
1218 ind = es.ind;
1219 flush_eltstate (&es);
1220 #else
1221 value = get_variable_value (v);
1222 #endif
1223
1224 if (expr_depth < initial_depth)
1225 {
1226 if (no_longjmp_on_fatal_error && interactive_shell)
1227 sh_longjmp (evalbuf, 1);
1228 return (0);
1229 }
1230
1231 tval = (value && *value) ? subexpr (value) : 0;
1232
1233 if (lvalue)
1234 {
1235 lvalue->tokstr = tok; /* XXX */
1236 lvalue->tokval = tval;
1237 lvalue->tokvar = v; /* XXX */
1238 #if defined (ARRAY_VARS)
1239 lvalue->ind = ind;
1240 #else
1241 lvalue->ind = -1;
1242 #endif
1243 }
1244
1245 return (tval);
1246 }
1247
1248 static int
1249 _is_multiop (c)
1250 int c;
1251 {
1252 switch (c)
1253 {
1254 case EQEQ:
1255 case NEQ:
1256 case LEQ:
1257 case GEQ:
1258 case LAND:
1259 case LOR:
1260 case LSH:
1261 case RSH:
1262 case OP_ASSIGN:
1263 case COND:
1264 case POWER:
1265 case PREINC:
1266 case PREDEC:
1267 case POSTINC:
1268 case POSTDEC:
1269 return 1;
1270 default:
1271 return 0;
1272 }
1273 }
1274
1275 static int
1276 _is_arithop (c)
1277 int c;
1278 {
1279 switch (c)
1280 {
1281 case EQ:
1282 case GT:
1283 case LT:
1284 case PLUS:
1285 case MINUS:
1286 case MUL:
1287 case DIV:
1288 case MOD:
1289 case NOT:
1290 case LPAR:
1291 case RPAR:
1292 case BAND:
1293 case BOR:
1294 case BXOR:
1295 case BNOT:
1296 return 1; /* operator tokens */
1297 case QUES:
1298 case COL:
1299 case COMMA:
1300 return 1; /* questionable */
1301 default:
1302 return 0; /* anything else is invalid */
1303 }
1304 }
1305
1306 /* Lexical analyzer/token reader for the expression evaluator. Reads the
1307 next token and puts its value into curtok, while advancing past it.
1308 Updates value of tp. May also set tokval (for number) or tokstr (for
1309 string). */
1310 static void
1311 readtok ()
1312 {
1313 register char *cp, *xp;
1314 register unsigned char c, c1;
1315 register int e;
1316 struct lvalue lval;
1317
1318 /* Skip leading whitespace. */
1319 cp = tp;
1320 c = e = 0;
1321 while (cp && (c = *cp) && (cr_whitespace (c)))
1322 cp++;
1323
1324 if (c)
1325 cp++;
1326
1327 if (c == '\0')
1328 {
1329 lasttok = curtok;
1330 curtok = 0;
1331 tp = cp;
1332 return;
1333 }
1334 lasttp = tp = cp - 1;
1335
1336 if (legal_variable_starter (c))
1337 {
1338 /* variable names not preceded with a dollar sign are shell variables. */
1339 char *savecp;
1340 EXPR_CONTEXT ec;
1341 int peektok;
1342
1343 while (legal_variable_char (c))
1344 c = *cp++;
1345
1346 c = *--cp;
1347
1348 #if defined (ARRAY_VARS)
1349 if (c == '[')
1350 {
1351 e = expr_skipsubscript (tp, cp); /* XXX - was skipsubscript */
1352 if (cp[e] == ']')
1353 {
1354 cp += e + 1;
1355 c = *cp;
1356 e = ']';
1357 }
1358 else
1359 evalerror (bash_badsub_errmsg);
1360 }
1361 #endif /* ARRAY_VARS */
1362
1363 *cp = '\0';
1364 /* XXX - watch out for pointer aliasing issues here */
1365 if (curlval.tokstr && curlval.tokstr == tokstr)
1366 init_lvalue (&curlval);
1367
1368 FREE (tokstr);
1369 tokstr = savestring (tp);
1370 *cp = c;
1371
1372 /* XXX - make peektok part of saved token state? */
1373 SAVETOK (&ec);
1374 tokstr = (char *)NULL; /* keep it from being freed */
1375 tp = savecp = cp;
1376 noeval = 1;
1377 curtok = STR;
1378 readtok ();
1379 peektok = curtok;
1380 if (peektok == STR) /* free new tokstr before old one is restored */
1381 FREE (tokstr);
1382 RESTORETOK (&ec);
1383 cp = savecp;
1384
1385 /* The tests for PREINC and PREDEC aren't strictly correct, but they
1386 preserve old behavior if a construct like --x=9 is given. */
1387 if (lasttok == PREINC || lasttok == PREDEC || peektok != EQ)
1388 {
1389 lastlval = curlval;
1390 tokval = expr_streval (tokstr, e, &curlval);
1391 }
1392 else
1393 tokval = 0;
1394
1395 lasttok = curtok;
1396 curtok = STR;
1397 }
1398 else if (DIGIT(c))
1399 {
1400 while (ISALNUM (c) || c == '#' || c == '@' || c == '_')
1401 c = *cp++;
1402
1403 c = *--cp;
1404 *cp = '\0';
1405
1406 tokval = strlong (tp);
1407 *cp = c;
1408 lasttok = curtok;
1409 curtok = NUM;
1410 }
1411 else
1412 {
1413 c1 = *cp++;
1414 if ((c == EQ) && (c1 == EQ))
1415 c = EQEQ;
1416 else if ((c == NOT) && (c1 == EQ))
1417 c = NEQ;
1418 else if ((c == GT) && (c1 == EQ))
1419 c = GEQ;
1420 else if ((c == LT) && (c1 == EQ))
1421 c = LEQ;
1422 else if ((c == LT) && (c1 == LT))
1423 {
1424 if (*cp == '=') /* a <<= b */
1425 {
1426 assigntok = LSH;
1427 c = OP_ASSIGN;
1428 cp++;
1429 }
1430 else
1431 c = LSH;
1432 }
1433 else if ((c == GT) && (c1 == GT))
1434 {
1435 if (*cp == '=')
1436 {
1437 assigntok = RSH; /* a >>= b */
1438 c = OP_ASSIGN;
1439 cp++;
1440 }
1441 else
1442 c = RSH;
1443 }
1444 else if ((c == BAND) && (c1 == BAND))
1445 c = LAND;
1446 else if ((c == BOR) && (c1 == BOR))
1447 c = LOR;
1448 else if ((c == '*') && (c1 == '*'))
1449 c = POWER;
1450 else if ((c == '-' || c == '+') && c1 == c && curtok == STR)
1451 c = (c == '-') ? POSTDEC : POSTINC;
1452 #if STRICT_ARITH_PARSING
1453 else if ((c == '-' || c == '+') && c1 == c && curtok == NUM)
1454 #else
1455 else if ((c == '-' || c == '+') && c1 == c && curtok == NUM && (lasttok == PREINC || lasttok == PREDEC))
1456 #endif
1457 {
1458 /* This catches something like --FOO++ */
1459 /* TAG:bash-5.3 add gettext calls here or make this a separate function */
1460 if (c == '-')
1461 evalerror ("--: assignment requires lvalue");
1462 else
1463 evalerror ("++: assignment requires lvalue");
1464 }
1465 else if ((c == '-' || c == '+') && c1 == c)
1466 {
1467 /* Quickly scan forward to see if this is followed by optional
1468 whitespace and an identifier. */
1469 xp = cp;
1470 while (xp && *xp && cr_whitespace (*xp))
1471 xp++;
1472 if (legal_variable_starter ((unsigned char)*xp))
1473 c = (c == '-') ? PREDEC : PREINC;
1474 else
1475 /* Could force parsing as preinc or predec and throw an error */
1476 #if STRICT_ARITH_PARSING
1477 {
1478 /* Posix says unary plus and minus have higher priority than
1479 preinc and predec. */
1480 /* This catches something like --4++ */
1481 if (c == '-')
1482 evalerror ("--: assignment requires lvalue");
1483 else
1484 evalerror ("++: assignment requires lvalue");
1485 }
1486 #else
1487 cp--; /* not preinc or predec, so unget the character */
1488 #endif
1489 }
1490 else if (c1 == EQ && member (c, "*/%+-&^|"))
1491 {
1492 assigntok = c; /* a OP= b */
1493 c = OP_ASSIGN;
1494 }
1495 else if (_is_arithop (c) == 0)
1496 {
1497 cp--;
1498 /* use curtok, since it hasn't been copied to lasttok yet */
1499 if (curtok == 0 || _is_arithop (curtok) || _is_multiop (curtok))
1500 evalerror (_("syntax error: operand expected"));
1501 else
1502 evalerror (_("syntax error: invalid arithmetic operator"));
1503 }
1504 else
1505 cp--; /* `unget' the character */
1506
1507 /* Should check here to make sure that the current character is one
1508 of the recognized operators and flag an error if not. Could create
1509 a character map the first time through and check it on subsequent
1510 calls. */
1511 lasttok = curtok;
1512 curtok = c;
1513 }
1514 tp = cp;
1515 }
1516
1517 static void
1518 evalerror (msg)
1519 const char *msg;
1520 {
1521 char *name, *t;
1522
1523 name = this_command_name;
1524 for (t = expression; t && whitespace (*t); t++)
1525 ;
1526 internal_error (_("%s%s%s: %s (error token is \"%s\")"),
1527 name ? name : "", name ? ": " : "",
1528 t ? t : "", msg, (lasttp && *lasttp) ? lasttp : "");
1529 sh_longjmp (evalbuf, 1);
1530 }
1531
1532 /* Convert a string to an intmax_t integer, with an arbitrary base.
1533 0nnn -> base 8
1534 0[Xx]nn -> base 16
1535 Anything else: [base#]number (this is implemented to match ksh93)
1536
1537 Base may be >=2 and <=64. If base is <= 36, the numbers are drawn
1538 from [0-9][a-zA-Z], and lowercase and uppercase letters may be used
1539 interchangeably. If base is > 36 and <= 64, the numbers are drawn
1540 from [0-9][a-z][A-Z]_@ (a = 10, z = 35, A = 36, Z = 61, @ = 62, _ = 63 --
1541 you get the picture). */
1542
1543 #define VALID_NUMCHAR(c) (ISALNUM(c) || ((c) == '_') || ((c) == '@'))
1544
1545 static intmax_t
1546 strlong (num)
1547 char *num;
1548 {
1549 register char *s;
1550 register unsigned char c;
1551 int base, foundbase;
1552 intmax_t val, pval;
1553
1554 s = num;
1555
1556 base = 10;
1557 foundbase = 0;
1558 if (*s == '0')
1559 {
1560 s++;
1561
1562 if (*s == '\0')
1563 return 0;
1564
1565 /* Base 16? */
1566 if (*s == 'x' || *s == 'X')
1567 {
1568 base = 16;
1569 s++;
1570 #if STRICT_ARITH_PARSING
1571 if (*s == 0)
1572 evalerror (_("invalid number"));
1573 #endif
1574 }
1575 else
1576 base = 8;
1577 foundbase++;
1578 }
1579
1580 val = 0;
1581 for (c = *s++; c; c = *s++)
1582 {
1583 if (c == '#')
1584 {
1585 if (foundbase)
1586 evalerror (_("invalid number"));
1587
1588 /* Illegal base specifications raise an evaluation error. */
1589 if (val < 2 || val > 64)
1590 evalerror (_("invalid arithmetic base"));
1591
1592 base = val;
1593 val = 0;
1594 foundbase++;
1595
1596 /* Make sure a base# is followed by a character that can compose a
1597 valid integer constant. Jeremy Townshend <jeremy.townshend@gmail.com> */
1598 if (VALID_NUMCHAR (*s) == 0)
1599 evalerror (_("invalid integer constant"));
1600 }
1601 else if (VALID_NUMCHAR (c))
1602 {
1603 if (DIGIT(c))
1604 c = TODIGIT(c);
1605 else if (c >= 'a' && c <= 'z')
1606 c -= 'a' - 10;
1607 else if (c >= 'A' && c <= 'Z')
1608 c -= 'A' - ((base <= 36) ? 10 : 36);
1609 else if (c == '@')
1610 c = 62;
1611 else if (c == '_')
1612 c = 63;
1613
1614 if (c >= base)
1615 evalerror (_("value too great for base"));
1616
1617 #ifdef CHECK_OVERFLOW
1618 pval = val;
1619 val = (val * base) + c;
1620 if (val < 0 || val < pval) /* overflow */
1621 return INTMAX_MAX;
1622 #else
1623 val = (val * base) + c;
1624 #endif
1625 }
1626 else
1627 break;
1628 }
1629
1630 return (val);
1631 }
1632
1633 #if defined (EXPR_TEST)
1634 void *
1635 xmalloc (n)
1636 int n;
1637 {
1638 return (malloc (n));
1639 }
1640
1641 void *
1642 xrealloc (s, n)
1643 char *s;
1644 int n;
1645 {
1646 return (realloc (s, n));
1647 }
1648
1649 SHELL_VAR *find_variable () { return 0;}
1650 SHELL_VAR *bind_variable () { return 0; }
1651
1652 char *get_string_value () { return 0; }
1653
1654 procenv_t top_level;
1655
1656 main (argc, argv)
1657 int argc;
1658 char **argv;
1659 {
1660 register int i;
1661 intmax_t v;
1662 int expok;
1663
1664 if (setjmp (top_level))
1665 exit (0);
1666
1667 for (i = 1; i < argc; i++)
1668 {
1669 v = evalexp (argv[i], 0, &expok);
1670 if (expok == 0)
1671 fprintf (stderr, _("%s: expression error\n"), argv[i]);
1672 else
1673 printf ("'%s' -> %ld\n", argv[i], v);
1674 }
1675 exit (0);
1676 }
1677
1678 int
1679 builtin_error (format, arg1, arg2, arg3, arg4, arg5)
1680 char *format;
1681 {
1682 fprintf (stderr, "expr: ");
1683 fprintf (stderr, format, arg1, arg2, arg3, arg4, arg5);
1684 fprintf (stderr, "\n");
1685 return 0;
1686 }
1687
1688 char *
1689 itos (n)
1690 intmax_t n;
1691 {
1692 return ("42");
1693 }
1694
1695 #endif /* EXPR_TEST */