home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / gnu / bash-1.12 / expr.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-01  |  13.4 KB  |  617 lines
  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.  All arithmetic is done as long integers with no checking for overflow
  22.  (though division by 0 is caught and flagged as an error).
  23.  
  24.  The following operators are handled, grouped into a set of levels in
  25.  order of decreasing precedence.
  26.  
  27.     "-"            [level 0 (unary negation)]
  28.     "!"            [level 1]
  29.     "*", "/", "%"        [level 2]
  30.     "+", "-"        [level 3]
  31.     "<=", ">=", "<", ">"    [level 4]
  32.     "==", "!="        [level 5]
  33.     "="            [level 6 (assignment)]
  34.  
  35.  (Note that most of these operators have special meaning to bash, and an
  36.  entire expression should be quoted, e.g. "a=$a+1" or "a=a+1" to ensure
  37.  that it is passed intact to the evaluator when using `let'.  When using
  38.  the $[] form, the text between the `[' and `]' is treated as if in double
  39.  quotes.)
  40.  
  41.  Sub-expressions within parentheses have a precedence level greater than
  42.  all of the above levels and are evaluated first.  Within a single prece-
  43.  dence group, evaluation is left-to-right, except for the arithmetic
  44.  assignment operator (`='), which is evaluated right-to-left (as in C).
  45.  
  46.  The expression evaluator returns the value of the expression (assignment
  47.  statements have as a value what is returned by the RHS).  The `let'
  48.  builtin, on the other hand, returns 0 if the last expression evaluates to
  49.  a non-zero, and 1 otherwise.
  50.  
  51.  Implementation is a recursive-descent parser.
  52.  
  53.  Chet Ramey
  54.  chet@ins.CWRU.Edu
  55. */
  56.  
  57. #include <stdio.h>
  58. #include "shell.h"
  59.  
  60. #define variable_starter(c) (isletter(c) || (c == '_'))
  61. #define variable_character(c) (isletter(c) || (c == '_') || digit(c))
  62.  
  63. #if defined (NULL)
  64. #undef NULL
  65. #endif
  66. #define NULL 0
  67.  
  68. static char    *expression = (char *) NULL;    /* The current expression */
  69. static char    *tp = (char *) NULL;        /* token lexical position */
  70. static int    curtok = 0;            /* the current token */
  71. static int    lasttok = 0;            /* the previous token */
  72. static char    *tokstr = (char *) NULL;    /* current token string */
  73. static int    tokval = 0;            /* current token value */
  74. static jmp_buf    evalbuf;
  75.  
  76. static void    readtok();            /* lexical analyzer */
  77. static long    assignment(), exp0(), exp1(), exp2(), exp3(), exp4(), exp5();
  78. static long    strlong();
  79. static void    evalerror();
  80.  
  81. /*
  82.  * Because of the $[...] construct, expressions may include newlines.  This
  83.  * redefines `whitespace' so that a newline is added.
  84.  */
  85.  
  86. #ifdef whitespace
  87. #undef whitespace
  88. #endif
  89.  
  90. #define whitespace(c)    ((c) == ' ' || (c) == '\t' || (c) == '\n')
  91.  
  92. /* A structure defining a single expression context. */
  93. typedef struct {
  94.   int curtok, lasttok;
  95.   char *expression, *tp;
  96.   int tokval;
  97.   char *tokstr;
  98. } EXPR_CONTEXT;
  99.  
  100. /* Global var which contains the stack of expression contexts. */
  101. static EXPR_CONTEXT **expr_stack;
  102. static int expr_depth = 0;       /* Location in the stack. */
  103. static int expr_stack_size = 0;       /* Number of slots already allocated. */
  104.  
  105. /* Size be which the expression stack grows when neccessary. */
  106. #define EXPR_STACK_GROW_SIZE 10
  107.  
  108. /* Maximum amount of recursion allowed.  This prevents a non-integer
  109.    variable such as "num=num+2" from infinitely adding to itself when
  110.    "let num=num+2" is given.  I have to talk to Chet about this hack. */
  111. #define MAX_EXPR_RECURSION_LEVEL 1024
  112.  
  113. extern long atol ();
  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 EQ    '='
  124. #define GT    '>'
  125. #define LT    '<'
  126. #define PLUS    '+'
  127. #define MINUS    '-'
  128. #define MUL    '*'
  129. #define DIV    '/'
  130. #define MOD    '%'
  131. #define NOT    '!'
  132. #define LPAR    '('
  133. #define RPAR    ')'
  134.  
  135. /* Push and save away the contents of the globals describing the
  136.    current expression context. */
  137. static void
  138. pushexp ()
  139. {
  140.   EXPR_CONTEXT *context;
  141.  
  142.   context = (EXPR_CONTEXT *)xmalloc (sizeof (EXPR_CONTEXT));
  143.  
  144.   if (expr_depth >= MAX_EXPR_RECURSION_LEVEL)
  145.     evalerror ("expression recursion level exceeded");
  146.  
  147.   if (expr_depth >= expr_stack_size)
  148.     {
  149.       expr_stack = (EXPR_CONTEXT **)
  150.     xrealloc (expr_stack, (expr_stack_size += EXPR_STACK_GROW_SIZE)
  151.           * sizeof (EXPR_CONTEXT *));
  152.     }
  153.  
  154.   context->curtok = curtok;
  155.   context->lasttok = lasttok;
  156.   context->expression = expression;
  157.   context->tp = tp;
  158.   context->tokval = tokval;
  159.   context->tokstr = tokstr;
  160.   expr_stack[expr_depth++] = context;
  161. }
  162.  
  163. /* Pop the the contents of the expression context stack into the
  164.    globals describing the current expression context. */
  165. static void
  166. popexp ()
  167. {
  168.   EXPR_CONTEXT *context;
  169.  
  170.   if (expr_depth == 0)
  171.     evalerror ("Recursion stack underflow");
  172.  
  173.   context = expr_stack[--expr_depth];
  174.   curtok = context->curtok;
  175.   lasttok = context->lasttok;
  176.   expression = context->expression;
  177.   tp = context->tp;
  178.   tokval = context->tokval;
  179.   tokstr = context->tokstr;
  180.   free (context);
  181. }
  182.  
  183. /* Evaluate EXPR, and return the arithmetic result.
  184.  
  185.    The `while' loop after the longjmp is caught relies on the above
  186.    implementation of pushexp and popexp leaving in expr_stack[0] the
  187.    values that the variables had when the program started.  That is,
  188.    the first things saved are the initial values of the variables that 
  189.    were assigned at program startup or by the compiler.  Therefore, it is
  190.    safe to let the loop terminate when expr_depth == 0, without freeing up
  191.    any of the expr_depth[0] stuff. */
  192. long
  193. evalexp (expr)
  194.      char *expr;
  195. {
  196.   long val = 0L;
  197.   jmp_buf old_evalbuf;
  198.  
  199.   if (expr == NULL || *expr == NULL)
  200.     return (0);
  201.  
  202.   /* Save the value of evalbuf to protect it around possible recursive
  203.      calls to evalexp (). */
  204.   bcopy ((char *)evalbuf, (char *)old_evalbuf, sizeof (jmp_buf));
  205.  
  206.   if (setjmp (evalbuf))
  207.     {
  208.       if (tokstr)        /* Clean up local allocation. */
  209.     free (tokstr);
  210.  
  211.       if (expression)
  212.     free (expression);
  213.  
  214.       while (--expr_depth)
  215.     {
  216.       if (expr_stack[expr_depth]->tokstr)
  217.         free (expr_stack[expr_depth]->tokstr);
  218.  
  219.       if (expr_stack[expr_depth]->expression)
  220.         free (expr_stack[expr_depth]->expression);
  221.     }
  222.       longjmp (top_level, DISCARD);
  223.     }
  224.  
  225.   pushexp ();
  226.   curtok = lasttok = 0;
  227.   expression = savestring (expr);
  228.   tp = expression;
  229.  
  230.   tokstr = (char *)NULL;
  231.   tokval = 0l;
  232.  
  233.   readtok ();
  234.  
  235.   val = assignment ();
  236.  
  237.   if (curtok != 0) 
  238.     evalerror ("syntax error in expression");
  239.  
  240.   if (expression)
  241.     free (expression);
  242.  
  243.   popexp ();
  244.  
  245.   /* Restore the value of evalbuf so that any subsequent longjmp calls
  246.      will have a valid location to jump to. */
  247.   bcopy ((char *)old_evalbuf, (char *)evalbuf, sizeof (jmp_buf));
  248.  
  249.   return (val);
  250. }
  251.  
  252. /* Bind/create a shell variable with the name LHS to the RHS.
  253.    This creates or modifies a variable such that it is an integer.
  254.  
  255.    This should really be in variables.c, but it is here so that all of the
  256.    expression evaluation stuff is localized.  Since we don't want any
  257.    recursive evaluation from bind_variable() (possible without this code,
  258.    since bind_variable() calls the evaluator for variables with the integer
  259.    attribute set), we temporarily turn off the integer attribute for each
  260.    variable we set here, then turn it back on after binding as necessary. */
  261.  
  262. void
  263. bind_int_variable (lhs, rhs)
  264.      char *lhs, *rhs;
  265. {
  266.   register SHELL_VAR *v;
  267.   int isint = 0;
  268.  
  269.   v = find_variable (lhs);
  270.   if (v)
  271.     {
  272.       isint = integer_p (v);
  273.       v->attributes &= ~att_integer;
  274.     }
  275.  
  276.   v = bind_variable (lhs, rhs);
  277.   if (isint)
  278.     v->attributes |= att_integer;
  279. }
  280.  
  281. static long
  282. assignment ()
  283. {
  284.   register long    value;
  285.   char *lhs;
  286.   char *rhs;
  287.  
  288.   value = exp5 ();
  289.   if (curtok == EQ)
  290.     {
  291.       if (lasttok != STR)
  292.     evalerror ("attempted assignment to non-variable");
  293.  
  294.       lhs = savestring (tokstr);
  295.       readtok ();
  296.       value = assignment ();
  297.       rhs = itos (value);
  298.       bind_int_variable (lhs, rhs);
  299.       free (rhs);
  300.       free (lhs);
  301.       free (tokstr);
  302.       tokstr = (char *)NULL;        /* For freeing on errors. */
  303.     }
  304.   return (value);
  305. }
  306.  
  307. static long
  308. exp5 ()
  309. {
  310.   register long val1, val2;
  311.  
  312.   val1 = exp4 ();
  313.  
  314.   while ((curtok == EQEQ) || (curtok == NEQ))
  315.     {
  316.       int op = curtok;
  317.  
  318.       readtok ();
  319.       val2 = exp4 ();
  320.       if (op == EQEQ)
  321.     val1 = (val1 == val2);
  322.       else if (op == NEQ)
  323.     val1 = (val1 != val2);
  324.     }
  325.   return (val1);
  326. }
  327.  
  328. static long
  329. exp4 ()
  330. {
  331.   register long val1, val2;
  332.  
  333.   val1 = exp3 ();
  334.   while ((curtok == LEQ) ||
  335.      (curtok == GEQ) ||
  336.      (curtok == LT) ||
  337.      (curtok == GT))
  338.     {
  339.       int op = curtok;
  340.  
  341.       readtok ();
  342.       val2 = exp3 ();
  343.  
  344.       if (op == LEQ)
  345.     val1 = val1 <= val2;
  346.       else if (op == GEQ)
  347.     val1 = val1 >= val2;
  348.       else if (op == LT)
  349.     val1 = val1 < val2;
  350.       else if (op == GT)
  351.     val1 = val1 > val2;
  352.     }
  353.   return (val1);
  354. }
  355.  
  356. static long
  357. exp3 ()
  358. {
  359.   register long val1, val2;
  360.  
  361.   val1 = exp2 ();
  362.  
  363.   while ((curtok == PLUS) || (curtok == MINUS))
  364.     {
  365.       int op = curtok;
  366.  
  367.       readtok ();
  368.       val2 = exp2 ();
  369.  
  370.       if (op == PLUS)
  371.     val1 += val2;
  372.       else if (op == MINUS)
  373.     val1 -= val2;
  374.     }
  375.   return (val1);
  376. }
  377.  
  378. static long
  379. exp2 ()
  380. {
  381.   register long val1, val2;
  382.  
  383.   val1 = exp1 ();
  384.  
  385.   while ((curtok == MUL) ||
  386.          (curtok == DIV) ||
  387.          (curtok == MOD))
  388.     {
  389.       int op = curtok;
  390.  
  391.       readtok ();
  392.  
  393.       val2 = exp1 ();
  394.  
  395.       if (((op == DIV) || (op == MOD)) && (val2 == 0))
  396.     evalerror ("division by 0");
  397.  
  398.       if (op == MUL)
  399.         val1 *= val2;
  400.       else if (op == DIV)
  401.         val1 /= val2;
  402.       else if (op == MOD)
  403.         val1 %= val2;
  404.     }
  405.   return (val1);
  406. }
  407.  
  408. static long
  409. exp1 ()
  410. {
  411.   register long val;
  412.  
  413.   if (curtok == NOT)
  414.     {
  415.       readtok ();
  416.       val = !exp0 ();
  417.     }
  418.   else
  419.     val = exp0 ();
  420.  
  421.   return (val);
  422. }
  423.  
  424. static long
  425. exp0 ()
  426. {
  427.   register long val = 0L;
  428.  
  429.   if (curtok == MINUS)
  430.     {
  431.       readtok ();
  432.       val = - exp0 ();
  433.     }
  434.   else if (curtok == LPAR)
  435.     {
  436.       readtok ();
  437.       val = assignment ();
  438.  
  439.       if (curtok != RPAR)
  440.     evalerror ("missing `)'");
  441.  
  442.       /* Skip over closing paren. */
  443.       readtok ();
  444.  
  445.     }
  446.   else if ((curtok == NUM) || (curtok == STR))
  447.     {
  448.       val = tokval;
  449.       readtok ();
  450.     }
  451.   else
  452.     evalerror ("syntax error in expression");
  453.  
  454.   return (val);
  455. }
  456.  
  457. /* Lexical analyzer/token reader for the expression evaluator.  Reads the
  458.    next token and puts its value into curtok, while advancing past it.
  459.    Updates value of tp.  May also set tokval (for number) or tokstr (for
  460.    string). */
  461. static void
  462. readtok ()
  463. {
  464.   register char *cp = tp;
  465.   register int c, c1;
  466.  
  467.   /* Skip leading whitespace. */
  468.   c = 0;
  469.   while (cp && (c = *cp) && (whitespace(c)))
  470.     cp++;
  471.  
  472.   if (c)
  473.     cp++;
  474.     
  475.   tp = cp - 1;
  476.  
  477.   if (c == '\0')
  478.     {
  479.       lasttok = curtok;
  480.       curtok = 0;
  481.       tp = cp;
  482.       return;
  483.     }
  484.  
  485.   if (variable_starter (c))
  486.     {
  487.       /* Semi-bogus K*rn shell compatibility feature -- variable
  488.      names not preceded with a dollar sign are shell variables. */
  489.       char *value;
  490.  
  491.       while (variable_character (c))
  492.     c = *cp++;
  493.  
  494.       c = *--cp;
  495.       *cp = '\0';
  496.  
  497.       tokstr = savestring (tp);
  498.       value = get_string_value (tokstr);
  499.  
  500.       if (value && *value)
  501.     tokval = evalexp (value);
  502.       else
  503.     tokval = 0;
  504.  
  505.       *cp = c;
  506.       lasttok = curtok;
  507.       curtok = STR;
  508.     }
  509.   else if (digit(c))
  510.     {
  511.       while (digit (c) || isletter (c) || c == '#')
  512.     c = *cp++;
  513.  
  514.       c = *--cp;
  515.       *cp = '\0';
  516.  
  517.       tokval = strlong (tp);
  518.       *cp = c;
  519.       lasttok = curtok;
  520.       curtok = NUM;
  521.  
  522.     }
  523.   else
  524.     {
  525.       c1 = *cp++;
  526.       if ((c == EQ) && (c1 == EQ)) 
  527.     c = EQEQ;
  528.       else if ((c == NOT) && (c1 == EQ))
  529.     c = NEQ;
  530.       else if ((c == GT) && (c1 == EQ))
  531.     c = GEQ;
  532.       else if ((c == LT) && (c1 == EQ))
  533.     c = LEQ;
  534.       else
  535.     cp--;            /* `unget' the character */
  536.       lasttok = curtok;
  537.       curtok = c;
  538.     }
  539.   tp = cp;
  540. }
  541.  
  542. static void
  543. evalerror (msg)
  544.      char *msg;
  545. {
  546.   builtin_error ("%s: %s (remainder of expression is \"%s\")",
  547.          expression, msg, (tp && *tp) ? tp : "");
  548.   longjmp (evalbuf, 1);
  549. }
  550.  
  551. /* Convert a string to a long integer, with an arbitrary base.
  552.    0nnn -> base 8
  553.    0xnn -> base 16
  554.    Anything else: [base#]number (this is from the ISO Pascal spec). */
  555. static long
  556. strlong (num)
  557.      char *num;
  558. {
  559.   register char *s = num;
  560.   register int c;
  561.   int base = 10;
  562.   long val = 0L;
  563.  
  564.   if (s == NULL || *s == NULL)
  565.     return 0L;
  566.  
  567.   if (*s == '0')
  568.     {
  569.       s++;
  570.  
  571.       if (s == NULL || *s == NULL)
  572.     return 0L;
  573.       
  574.        /* Base 16? */
  575.       if (*s == 'x' || *s == 'X')
  576.     {
  577.       base = 16;
  578.       s++;
  579.     }
  580.       else
  581.     base = 8;
  582.     }
  583.  
  584.   for (c = *s++; c; c = *s++)
  585.     {
  586.       if (c == '#')
  587.     {
  588.       base = (int)val;
  589.  
  590.       /* Illegal base specifications are silently reset to base 10.
  591.          I don't think that this is a good idea? */
  592.       if (base < 2 || base > 36)
  593.         base = 10;
  594.  
  595.       val = 0L;
  596.     }
  597.       else
  598.     if (isletter(c) || digit(c))
  599.       {
  600.         if (digit(c))
  601.           c = digit_value(c);
  602.         else if (c >= 'a' && c <= 'z')
  603.           c -= 'a' - 10;
  604.         else if (c >= 'A' && c <= 'Z')
  605.           c -= 'A' - 10;
  606.  
  607.         if (c >= base)
  608.           evalerror ("value too great for base");
  609.  
  610.         val = (val * base) + c;
  611.       }
  612.     else
  613.       break;
  614.     }
  615.   return (val);
  616. }
  617.