Imported from ../bash-1.14.7.tar.gz.
[platform/upstream/bash.git] / expr.c
1 /* expr.c -- arithmetic expression evaluation. */
2
3 /* Copyright (C) 1990, 1991 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 it
8    under the terms of the GNU General Public License as published by
9    the Free Software Foundation; either version 1, or (at your option)
10    any later version.
11
12    Bash is distributed in the hope that it will be useful, but WITHOUT
13    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
15    License for more details.
16
17    You should have received a copy of the GNU General Public License
18    along with Bash; see the file COPYING.  If not, write to the Free
19    Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
20
21 /*
22  All arithmetic is done as long 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         "-", "+"                [(unary operators)]
29         "!", "~"
30         "*", "/", "%"
31         "+", "-"
32         "<<", ">>"
33         "<=", ">=", "<", ">"
34         "==", "!="
35         "&"
36         "^"
37         "|"
38         "&&"
39         "||"
40         "="
41
42  (Note that most of these operators have special meaning to bash, and an
43  entire expression should be quoted, e.g. "a=$a+1" or "a=a+1" to ensure
44  that it is passed intact to the evaluator when using `let'.  When using
45  the $[] or $(( )) forms, the text between the `[' and `]' or `((' and `))'
46  is treated as if in double quotes.)
47
48  Sub-expressions within parentheses have a precedence level greater than
49  all of the above levels and are evaluated first.  Within a single prece-
50  dence group, evaluation is left-to-right, except for the arithmetic
51  assignment operator (`='), which is evaluated right-to-left (as in C).
52
53  The expression evaluator returns the value of the expression (assignment
54  statements have as a value what is returned by the RHS).  The `let'
55  builtin, on the other hand, returns 0 if the last expression evaluates to
56  a non-zero, and 1 otherwise.
57
58  Implementation is a recursive-descent parser.
59
60  Chet Ramey
61  chet@ins.CWRU.Edu
62 */
63
64 #include <stdio.h>
65 #include "bashansi.h"
66 #include "shell.h"
67
68 #define variable_starter(c) (isletter(c) || (c == '_'))
69 #define variable_character(c) (isletter(c) || (c == '_') || digit(c))
70
71 /* Because of the $((...)) construct, expressions may include newlines.
72    Here is a macro which accepts newlines, tabs and spaces as whitespace. */
73 #define cr_whitespace(c) (whitespace(c) || ((c) == '\n'))
74
75 extern char     *this_command_name;
76
77 static char     *expression = (char *) NULL;    /* The current expression */
78 static char     *tp = (char *) NULL;            /* token lexical position */
79 static char     *lasttp;
80 static int      curtok = 0;                     /* the current token */
81 static int      lasttok = 0;                    /* the previous token */
82 static int      assigntok = 0;                  /* the OP in OP= */
83 static char     *tokstr = (char *) NULL;        /* current token string */
84 static int      tokval = 0;                     /* current token value */
85 static jmp_buf  evalbuf;
86
87 static void     readtok ();                     /* lexical analyzer */
88 static long     expassign (), exp0 (), exp1 (), exp2 (), exp3 (),
89                 exp4 (), exp5 (), expshift (), expland (), explor (),
90                 expband (), expbor (), expbxor ();
91 static long     strlong ();
92 static void     evalerror ();
93
94 /* A structure defining a single expression context. */
95 typedef struct {
96   int curtok, lasttok;
97   char *expression, *tp;
98   int tokval;
99   char *tokstr;
100 } EXPR_CONTEXT;
101
102 /* Global var which contains the stack of expression contexts. */
103 static EXPR_CONTEXT **expr_stack;
104 static int expr_depth = 0;         /* Location in the stack. */
105 static int expr_stack_size = 0;    /* Number of slots already allocated. */
106
107 /* Size be which the expression stack grows when neccessary. */
108 #define EXPR_STACK_GROW_SIZE 10
109
110 /* Maximum amount of recursion allowed.  This prevents a non-integer
111    variable such as "num=num+2" from infinitely adding to itself when
112    "let num=num+2" is given.  I have to talk to Chet about this hack. */
113 #define MAX_EXPR_RECURSION_LEVEL 1024
114
115 /* The Tokens.  Singing "The Lion Sleeps Tonight". */
116
117 #define EQEQ    1       /* "==" */
118 #define NEQ     2       /* "!=" */
119 #define LEQ     3       /* "<=" */
120 #define GEQ     4       /* ">=" */
121 #define STR     5       /* string */
122 #define NUM     6       /* number */
123 #define LAND    7       /* "&&" Logical AND */
124 #define LOR     8       /* "||" Logical OR */
125 #define LSH     9       /* "<<" Left SHift */
126 #define RSH    10       /* ">>" Right SHift */
127 #define OP_ASSIGN 11    /* op= expassign as in Posix.2 */
128 #define EQ      '='
129 #define GT      '>'
130 #define LT      '<'
131 #define PLUS    '+'
132 #define MINUS   '-'
133 #define MUL     '*'
134 #define DIV     '/'
135 #define MOD     '%'
136 #define NOT     '!'
137 #define LPAR    '('
138 #define RPAR    ')'
139 #define BAND    '&'     /* Bitwise AND */
140 #define BOR     '|'     /* Either Bitwise OR, or what Chet is. */
141 #define BXOR    '^'     /* Bitwise eXclusive OR. */
142 #define BNOT    '~'     /* Bitwise NOT; Two's complement. */
143
144 /* Push and save away the contents of the globals describing the
145    current expression context. */
146 static void
147 pushexp ()
148 {
149   EXPR_CONTEXT *context;
150
151   context = (EXPR_CONTEXT *)xmalloc (sizeof (EXPR_CONTEXT));
152
153   if (expr_depth >= MAX_EXPR_RECURSION_LEVEL)
154     evalerror ("expression recursion level exceeded");
155
156   if (expr_depth >= expr_stack_size)
157     {
158       expr_stack = (EXPR_CONTEXT **)
159         xrealloc (expr_stack, (expr_stack_size += EXPR_STACK_GROW_SIZE)
160                   * sizeof (EXPR_CONTEXT *));
161     }
162
163   context->curtok = curtok;
164   context->lasttok = lasttok;
165   context->expression = expression;
166   context->tp = tp;
167   context->tokval = tokval;
168   context->tokstr = tokstr;
169   expr_stack[expr_depth++] = context;
170 }
171
172 /* Pop the the contents of the expression context stack into the
173    globals describing the current expression context. */
174 static void
175 popexp ()
176 {
177   EXPR_CONTEXT *context;
178
179   if (expr_depth == 0)
180     evalerror ("Recursion stack underflow");
181
182   context = expr_stack[--expr_depth];
183   curtok = context->curtok;
184   lasttok = context->lasttok;
185   expression = context->expression;
186   tp = context->tp;
187   tokval = context->tokval;
188   tokstr = context->tokstr;
189   free (context);
190 }
191
192 /* Evaluate EXPR, and return the arithmetic result.
193
194    The `while' loop after the longjmp is caught relies on the above
195    implementation of pushexp and popexp leaving in expr_stack[0] the
196    values that the variables had when the program started.  That is,
197    the first things saved are the initial values of the variables that 
198    were assigned at program startup or by the compiler.  Therefore, it is
199    safe to let the loop terminate when expr_depth == 0, without freeing up
200    any of the expr_depth[0] stuff. */
201 long
202 evalexp (expr)
203      char *expr;
204 {
205   long val = 0L;
206   jmp_buf old_evalbuf;
207   char *p;
208
209   for (p = expr; p && *p && cr_whitespace (*p); p++)
210     ;
211
212   if (p == NULL || *p == '\0')
213     return (0);
214
215   /* Save the value of evalbuf to protect it around possible recursive
216      calls to evalexp (). */
217   xbcopy ((char *)evalbuf, (char *)old_evalbuf, sizeof (jmp_buf));
218
219   if (setjmp (evalbuf))
220     {
221       if (tokstr)               /* Clean up local allocation. */
222         free (tokstr);
223
224       if (expression)
225         free (expression);
226
227       while (--expr_depth)
228         {
229           if (expr_stack[expr_depth]->tokstr)
230             free (expr_stack[expr_depth]->tokstr);
231
232           if (expr_stack[expr_depth]->expression)
233             free (expr_stack[expr_depth]->expression);
234         }
235       longjmp (top_level, DISCARD);
236     }
237
238   pushexp ();
239   curtok = lasttok = 0;
240   expression = savestring (expr);
241   tp = expression;
242
243   tokstr = (char *)NULL;
244   tokval = 0l;
245
246   readtok ();
247
248   val = expassign ();
249
250   if (curtok != 0) 
251     evalerror ("syntax error in expression");
252
253   if (tokstr)
254     free (tokstr);
255   if (expression)
256     free (expression);
257
258   popexp ();
259
260   /* Restore the value of evalbuf so that any subsequent longjmp calls
261      will have a valid location to jump to. */
262   xbcopy ((char *)old_evalbuf, (char *)evalbuf, sizeof (jmp_buf));
263
264   return (val);
265 }
266
267 /* Bind/create a shell variable with the name LHS to the RHS.
268    This creates or modifies a variable such that it is an integer.
269
270    This should really be in variables.c, but it is here so that all of the
271    expression evaluation stuff is localized.  Since we don't want any
272    recursive evaluation from bind_variable() (possible without this code,
273    since bind_variable() calls the evaluator for variables with the integer
274    attribute set), we temporarily turn off the integer attribute for each
275    variable we set here, then turn it back on after binding as necessary. */
276
277 void
278 bind_int_variable (lhs, rhs)
279      char *lhs, *rhs;
280 {
281   register SHELL_VAR *v;
282   int isint = 0;
283
284   v = find_variable (lhs);
285   if (v)
286     {
287       isint = integer_p (v);
288       v->attributes &= ~att_integer;
289     }
290
291   v = bind_variable (lhs, rhs);
292   if (isint)
293     v->attributes |= att_integer;
294 }
295
296 static long
297 expassign ()
298 {
299   register long value;
300   char *lhs, *rhs;
301
302   value = explor ();
303   if (curtok == EQ || curtok == OP_ASSIGN)
304     {
305       int special = curtok == OP_ASSIGN;
306       int op;
307       long lvalue;
308
309       if (lasttok != STR)
310         evalerror ("attempted expassign to non-variable");
311
312       if (special)
313         {
314           op = assigntok;               /* a OP= b */
315           lvalue = value;
316         }
317
318       lhs = savestring (tokstr);
319       readtok ();
320       value = expassign ();
321
322       if (special)
323         {
324           switch (op)
325             {
326             case MUL:
327               lvalue *= value;
328               break;
329             case DIV:
330               lvalue /= value;
331               break;
332             case MOD:
333               lvalue %= value;
334               break;
335             case PLUS:
336               lvalue += value;
337               break;
338             case MINUS:
339               lvalue -= value;
340               break;
341             case LSH:
342               lvalue <<= value;
343               break;
344             case RSH:
345               lvalue >>= value;
346               break;
347             case BAND:
348               lvalue &= value;
349               break;
350             case BOR:
351               lvalue |= value;
352               break;
353             default:
354               evalerror ("bug: bad expassign token %d", assigntok);
355               break;
356             }
357           value = lvalue;
358         }
359
360       rhs = itos (value);
361       bind_int_variable (lhs, rhs);
362       free (rhs);
363       free (lhs);
364       free (tokstr);
365       tokstr = (char *)NULL;            /* For freeing on errors. */
366     }
367   return (value);
368 }
369
370 /* Logical OR. */
371 static long
372 explor ()
373 {
374   register long val1, val2;
375
376   val1 = expland ();
377
378   while (curtok == LOR)
379     {
380       readtok ();
381       val2 = expland ();
382       val1 = val1 || val2;
383     }
384
385   return (val1);
386 }
387
388 /* Logical AND. */
389 static long
390 expland ()
391 {
392   register long val1, val2;
393
394   val1 = expbor ();
395
396   while (curtok == LAND)
397     {
398       readtok ();
399       val2 = expbor ();
400       val1 = val1 && val2;
401     }
402
403   return (val1);
404 }
405
406 /* Bitwise OR. */
407 static long
408 expbor ()
409 {
410   register long val1, val2;
411
412   val1 = expbxor ();
413
414   while (curtok == BOR)
415     {
416       readtok ();
417       val2 = expbxor ();
418       val1 = val1 | val2;
419     }
420
421   return (val1);
422 }
423
424 /* Bitwise XOR. */
425 static long
426 expbxor ()
427 {
428   register long val1, val2;
429
430   val1 = expband ();
431
432   while (curtok == BXOR)
433     {
434       readtok ();
435       val2 = expband ();
436       val1 = val1 ^ val2;
437     }
438
439   return (val1);
440 }
441
442 /* Bitwise AND. */
443 static long
444 expband ()
445 {
446   register long val1, val2;
447
448   val1 = exp5 ();
449
450   while (curtok == BAND)
451     {
452       readtok ();
453       val2 = exp5 ();
454       val1 = val1 & val2;
455     }
456
457   return (val1);
458 }
459
460 static long
461 exp5 ()
462 {
463   register long val1, val2;
464
465   val1 = exp4 ();
466
467   while ((curtok == EQEQ) || (curtok == NEQ))
468     {
469       int op = curtok;
470
471       readtok ();
472       val2 = exp4 ();
473       if (op == EQEQ)
474         val1 = (val1 == val2);
475       else if (op == NEQ)
476         val1 = (val1 != val2);
477     }
478   return (val1);
479 }
480
481 static long
482 exp4 ()
483 {
484   register long val1, val2;
485
486   val1 = expshift ();
487   while ((curtok == LEQ) ||
488          (curtok == GEQ) ||
489          (curtok == LT) ||
490          (curtok == GT))
491     {
492       int op = curtok;
493
494       readtok ();
495       val2 = expshift ();
496
497       if (op == LEQ)
498         val1 = val1 <= val2;
499       else if (op == GEQ)
500         val1 = val1 >= val2;
501       else if (op == LT)
502         val1 = val1 < val2;
503       else if (op == GT)
504         val1 = val1 > val2;
505     }
506   return (val1);
507 }
508
509 /* Left and right shifts. */
510 static long
511 expshift ()
512 {
513   register long val1, val2;
514
515   val1 = exp3 ();
516
517   while ((curtok == LSH) || (curtok == RSH))
518     {
519       int op = curtok;
520
521       readtok ();
522       val2 = exp3 ();
523
524       if (op == LSH)
525         val1 = val1 << val2;
526       else
527         val1 = val1 >> val2;
528     }
529
530   return (val1);
531 }
532
533 static long
534 exp3 ()
535 {
536   register long val1, val2;
537
538   val1 = exp2 ();
539
540   while ((curtok == PLUS) || (curtok == MINUS))
541     {
542       int op = curtok;
543
544       readtok ();
545       val2 = exp2 ();
546
547       if (op == PLUS)
548         val1 += val2;
549       else if (op == MINUS)
550         val1 -= val2;
551     }
552   return (val1);
553 }
554
555 static long
556 exp2 ()
557 {
558   register long val1, val2;
559
560   val1 = exp1 ();
561
562   while ((curtok == MUL) ||
563          (curtok == DIV) ||
564          (curtok == MOD))
565     {
566       int op = curtok;
567
568       readtok ();
569
570       val2 = exp1 ();
571
572       if (((op == DIV) || (op == MOD)) && (val2 == 0))
573         evalerror ("division by 0");
574
575       if (op == MUL)
576         val1 *= val2;
577       else if (op == DIV)
578         val1 /= val2;
579       else if (op == MOD)
580         val1 %= val2;
581     }
582   return (val1);
583 }
584
585 static long
586 exp1 ()
587 {
588   register long val;
589
590   if (curtok == NOT)
591     {
592       readtok ();
593       val = !exp1 ();
594     }
595   else if (curtok == BNOT)
596     {
597       readtok ();
598       val = ~exp1 ();
599     }
600   else
601     val = exp0 ();
602
603   return (val);
604 }
605
606 static long
607 exp0 ()
608 {
609   register long val = 0L;
610
611   if (curtok == MINUS)
612     {
613       readtok ();
614       val = - exp0 ();
615     }
616   else if (curtok == PLUS)
617     {
618       readtok ();
619       val = exp0 ();
620     }
621   else if (curtok == LPAR)
622     {
623       readtok ();
624       val = expassign ();
625
626       if (curtok != RPAR)
627         evalerror ("missing `)'");
628
629       /* Skip over closing paren. */
630       readtok ();
631     }
632   else if ((curtok == NUM) || (curtok == STR))
633     {
634       val = tokval;
635       readtok ();
636     }
637   else
638     evalerror ("syntax error in expression");
639
640   return (val);
641 }
642
643 /* Lexical analyzer/token reader for the expression evaluator.  Reads the
644    next token and puts its value into curtok, while advancing past it.
645    Updates value of tp.  May also set tokval (for number) or tokstr (for
646    string). */
647 static void
648 readtok ()
649 {
650   register char *cp = tp;
651   register int c, c1;
652
653   /* Skip leading whitespace. */
654   c = 0;
655   while (cp && (c = *cp) && (cr_whitespace (c)))
656     cp++;
657
658   if (c)
659     cp++;
660         
661   lasttp = tp = cp - 1;
662
663   if (c == '\0')
664     {
665       lasttok = curtok;
666       curtok = 0;
667       tp = cp;
668       return;
669     }
670
671   if (variable_starter (c))
672     {
673       /* Semi-bogus K*rn shell compatibility feature -- variable
674          names not preceded with a dollar sign are shell variables. */
675       char *value;
676
677       while (variable_character (c))
678         c = *cp++;
679
680       c = *--cp;
681       *cp = '\0';
682
683       if (tokstr)
684         free (tokstr);
685       tokstr = savestring (tp);
686       value = get_string_value (tokstr);
687
688       if (value && *value)
689         tokval = evalexp (value);
690       else
691         tokval = 0;
692
693       *cp = c;
694       lasttok = curtok;
695       curtok = STR;
696     }
697   else if (digit(c))
698     {
699       while (digit (c) || isletter (c) || c == '#')
700         c = *cp++;
701
702       c = *--cp;
703       *cp = '\0';
704
705       tokval = strlong (tp);
706       *cp = c;
707       lasttok = curtok;
708       curtok = NUM;
709     }
710   else
711     {
712       c1 = *cp++;
713       if ((c == EQ) && (c1 == EQ)) 
714         c = EQEQ;
715       else if ((c == NOT) && (c1 == EQ))
716         c = NEQ;
717       else if ((c == GT) && (c1 == EQ))
718         c = GEQ;
719       else if ((c == LT) && (c1 == EQ))
720         c = LEQ;
721       else if ((c == LT) && (c1 == LT))
722         {
723           if (*cp == '=')       /* a <<= b */
724             {
725               assigntok = LSH;
726               c = OP_ASSIGN;
727               cp++;
728             }
729           else
730             c = LSH;
731         }
732       else if ((c == GT) && (c1 == GT))
733         {
734           if (*cp == '=')
735             {
736               assigntok = RSH;  /* a >>= b */
737               c = OP_ASSIGN;
738               cp++;
739             }
740           else
741             c = RSH;
742         }
743       else if ((c == BAND) && (c1 == BAND))
744         c = LAND;
745       else if ((c == BOR) && (c1 == BOR))
746         c = LOR;
747       else if (c1 == EQ && member(c, "*/%+-&^|"))
748         {
749           assigntok = c;        /* a OP= b */
750           c = OP_ASSIGN;
751         }
752       else
753         cp--;                   /* `unget' the character */
754       lasttok = curtok;
755       curtok = c;
756     }
757   tp = cp;
758 }
759
760 static void
761 evalerror (msg)
762      char *msg;
763 {
764   char *name, *t;
765
766   name = this_command_name;
767   if (name == 0)
768     name = get_name_for_error ();
769   for (t = expression; whitespace (*t); t++)
770     ;
771   fprintf (stderr, "%s: %s: %s (remainder of expression is \"%s\")\n",
772                  name, t,
773                  msg, (lasttp && *lasttp) ? lasttp : "");
774   longjmp (evalbuf, 1);
775 }
776
777 /* Convert a string to a long integer, with an arbitrary base.
778    0nnn -> base 8
779    0xnn -> base 16
780    Anything else: [base#]number (this is from the ISO Pascal spec). */
781 static long
782 strlong (num)
783      char *num;
784 {
785   register char *s = num;
786   register int c;
787   int base = 10;
788   long val = 0L;
789
790   if (s == NULL || *s == '\0')
791     return 0L;
792
793   if (*s == '0')
794     {
795       s++;
796
797       if (s == NULL || *s == '\0')
798         return 0L;
799       
800        /* Base 16? */
801       if (*s == 'x' || *s == 'X')
802         {
803           base = 16;
804           s++;
805         }
806       else
807         base = 8;
808     }
809
810   for (c = *s++; c; c = *s++)
811     {
812       if (c == '#')
813         {
814           base = (int)val;
815
816           /* Illegal base specifications are silently reset to base 10.
817              I don't think that this is a good idea? */
818           if (base < 2 || base > 36)
819             base = 10;
820
821           val = 0L;
822         }
823       else
824         if (isletter(c) || digit(c))
825           {
826             if (digit(c))
827               c = digit_value(c);
828             else if (c >= 'a' && c <= 'z')
829               c -= 'a' - 10;
830             else if (c >= 'A' && c <= 'Z')
831               c -= 'A' - 10;
832
833             if (c >= base)
834               evalerror ("value too great for base");
835
836             val = (val * base) + c;
837           }
838         else
839           break;
840     }
841   return (val);
842 }
843
844 #if defined (EXPR_TEST)
845 char *
846 xmalloc (n)
847      int n;
848 {
849   return (malloc (n));
850 }
851
852 char *
853 xrealloc (s, n)
854      char *s;
855      int n;
856 {
857   return (realloc (s, n));
858 }
859
860 SHELL_VAR *find_variable () { return 0;}
861 SHELL_VAR *bind_variable () { return 0; }
862
863 char *get_string_value () { return 0; }
864
865 jmp_buf top_level;
866
867 main (argc, argv)
868      int argc;
869      char **argv;
870 {
871   register int i;
872   long v;
873
874   if (setjmp (top_level))
875     exit (0);
876
877   for (i = 1; i < argc; i++)
878     {
879       v = evalexp (argv[i]);
880       printf ("'%s' -> %ld\n", argv[i], v);
881     }
882   exit (0);
883 }
884
885 int
886 builtin_error (format, arg1, arg2, arg3, arg4, arg5)
887      char *format;
888 {
889   fprintf (stderr, "expr: ");
890   fprintf (stderr, format, arg1, arg2, arg3, arg4, arg5);
891   fprintf (stderr, "\n");
892   return 0;
893 }
894
895 char *
896 itos (n)
897      int n;
898 {
899   return ("42");
900 }
901
902 #endif /* EXPR_TEST */