l4/pkg/dash/contrib/src/arith_yacc.c

   1 /*-
   2  * Copyright (c) 1993
   3  *      The Regents of the University of California.  All rights reserved.
   4  * Copyright (c) 2007
   5  *      Herbert Xu <herbert@gondor.apana.org.au>.  All rights reserved.
   6  *
   7  * This code is derived from software contributed to Berkeley by
   8  * Kenneth Almquist.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  * 3. Neither the name of the University nor the names of its contributors
  19  *    may be used to endorse or promote products derived from this software
  20  *    without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  */
  34
  35 #include <inttypes.h>
  36 #include <stdlib.h>
  37 #include "arith_yacc.h"
  38 #include "expand.h"
  39 #include "shell.h"
  40 #include "error.h"
  41 #include "output.h"
  42 #include "var.h"
  43
  44 #if ARITH_BOR + 11 != ARITH_BORASS || ARITH_ASS + 11 != ARITH_EQ
  45 #error Arithmetic tokens are out of order.
  46 #endif
  47
  48 static const char *arith_startbuf;
  49
  50 const char *arith_buf;
  51 union yystype yylval;
  52
  53 static int last_token;
  54
  55 #define ARITH_PRECEDENCE(op, prec) [op - ARITH_BINOP_MIN] = prec
  56
  57 static const char prec[ARITH_BINOP_MAX - ARITH_BINOP_MIN] = {
  58         ARITH_PRECEDENCE(ARITH_MUL, 0),
  59         ARITH_PRECEDENCE(ARITH_DIV, 0),
  60         ARITH_PRECEDENCE(ARITH_REM, 0),
  61         ARITH_PRECEDENCE(ARITH_ADD, 1),
  62         ARITH_PRECEDENCE(ARITH_SUB, 1),
  63         ARITH_PRECEDENCE(ARITH_LSHIFT, 2),
  64         ARITH_PRECEDENCE(ARITH_RSHIFT, 2),
  65         ARITH_PRECEDENCE(ARITH_LT, 3),
  66         ARITH_PRECEDENCE(ARITH_LE, 3),
  67         ARITH_PRECEDENCE(ARITH_GT, 3),
  68         ARITH_PRECEDENCE(ARITH_GE, 3),
  69         ARITH_PRECEDENCE(ARITH_EQ, 4),
  70         ARITH_PRECEDENCE(ARITH_NE, 4),
  71         ARITH_PRECEDENCE(ARITH_BAND, 5),
  72         ARITH_PRECEDENCE(ARITH_BXOR, 6),
  73         ARITH_PRECEDENCE(ARITH_BOR, 7),
  74 };
  75
  76 #define ARITH_MAX_PREC 8
  77
  78 static void yyerror(const char *s) __attribute__ ((noreturn));
  79 static void yyerror(const char *s)
  80 {
  81         sh_error("arithmetic expression: %s: \"%s\"", s, arith_startbuf);
  82         /* NOTREACHED */
  83 }
  84
  85 static inline int arith_prec(int op)
  86 {
  87         return prec[op - ARITH_BINOP_MIN];
  88 }
  89
  90 static inline int higher_prec(int op1, int op2)
  91 {
  92         return arith_prec(op1) < arith_prec(op2);
  93 }
  94
  95 static intmax_t do_binop(int op, intmax_t a, intmax_t b)
  96 {
  97         switch (op) {
  98         default:
  99         case ARITH_REM:
 100         case ARITH_DIV:
 101                 if (!b)
 102                         yyerror("division by zero");
 103                 return op == ARITH_REM ? a % b : a / b;
 104         case ARITH_MUL:
 105                 return a * b;
 106         case ARITH_ADD:
 107                 return a + b;
 108         case ARITH_SUB:
 109                 return a - b;
 110         case ARITH_LSHIFT:
 111                 return a << b;
 112         case ARITH_RSHIFT:
 113                 return a >> b;
 114         case ARITH_LT:
 115                 return a < b;
 116         case ARITH_LE:
 117                 return a <= b;
 118         case ARITH_GT:
 119                 return a > b;
 120         case ARITH_GE:
 121                 return a >= b;
 122         case ARITH_EQ:
 123                 return a == b;
 124         case ARITH_NE:
 125                 return a != b;
 126         case ARITH_BAND:
 127                 return a & b;
 128         case ARITH_BXOR:
 129                 return a ^ b;
 130         case ARITH_BOR:
 131                 return a | b;
 132         }
 133 }
 134
 135 static intmax_t assignment(int var, int noeval);
 136
 137 static intmax_t primary(int token, union yystype *val, int op, int noeval)
 138 {
 139         intmax_t result;
 140
 141 again:
 142         switch (token) {
 143         case ARITH_LPAREN:
 144                 result = assignment(op, noeval);
 145                 if (last_token != ARITH_RPAREN)
 146                         yyerror("expecting ')'");
 147                 last_token = yylex();
 148                 return result;
 149         case ARITH_NUM:
 150                 last_token = op;
 151                 return val->val;
 152         case ARITH_VAR:
 153                 last_token = op;
 154                 return noeval ? val->val : lookupvarint(val->name);
 155         case ARITH_ADD:
 156                 token = op;
 157                 *val = yylval;
 158                 op = yylex();
 159                 goto again;
 160         case ARITH_SUB:
 161                 *val = yylval;
 162                 return -primary(op, val, yylex(), noeval);
 163         case ARITH_NOT:
 164                 *val = yylval;
 165                 return !primary(op, val, yylex(), noeval);
 166         case ARITH_BNOT:
 167                 *val = yylval;
 168                 return ~primary(op, val, yylex(), noeval);
 169         default:
 170                 yyerror("expecting primary");
 171         }
 172 }
 173
 174 static intmax_t binop2(intmax_t a, int op, int prec, int noeval)
 175 {
 176         for (;;) {
 177                 union yystype val;
 178                 intmax_t b;
 179                 int op2;
 180                 int token;
 181
 182                 token = yylex();
 183                 val = yylval;
 184
 185                 b = primary(token, &val, yylex(), noeval);
 186
 187                 op2 = last_token;
 188                 if (op2 >= ARITH_BINOP_MIN && op2 < ARITH_BINOP_MAX &&
 189                     higher_prec(op2, op)) {
 190                         b = binop2(b, op2, arith_prec(op), noeval);
 191                         op2 = last_token;
 192                 }
 193
 194                 a = noeval ? b : do_binop(op, a, b);
 195
 196                 if (op2 < ARITH_BINOP_MIN || op2 >= ARITH_BINOP_MAX ||
 197                     arith_prec(op2) >= prec)
 198                         return a;
 199
 200                 op = op2;
 201         }
 202 }
 203
 204 static intmax_t binop(int token, union yystype *val, int op, int noeval)
 205 {
 206         intmax_t a = primary(token, val, op, noeval);
 207
 208         op = last_token;
 209         if (op < ARITH_BINOP_MIN || op >= ARITH_BINOP_MAX)
 210                 return a;
 211
 212         return binop2(a, op, ARITH_MAX_PREC, noeval);
 213 }
 214
 215 static intmax_t and(int token, union yystype *val, int op, int noeval)
 216 {
 217         intmax_t a = binop(token, val, op, noeval);
 218         intmax_t b;
 219
 220         op = last_token;
 221         if (op != ARITH_AND)
 222                 return a;
 223
 224         token = yylex();
 225         *val = yylval;
 226
 227         b = and(token, val, yylex(), noeval | !a);
 228
 229         return a && b;
 230 }
 231
 232 static intmax_t or(int token, union yystype *val, int op, int noeval)
 233 {
 234         intmax_t a = and(token, val, op, noeval);
 235         intmax_t b;
 236
 237         op = last_token;
 238         if (op != ARITH_OR)
 239                 return a;
 240
 241         token = yylex();
 242         *val = yylval;
 243
 244         b = or(token, val, yylex(), noeval | !!a);
 245
 246         return a || b;
 247 }
 248
 249 static intmax_t cond(int token, union yystype *val, int op, int noeval)
 250 {
 251         intmax_t a = or(token, val, op, noeval);
 252         intmax_t b;
 253         intmax_t c;
 254
 255         if (last_token != ARITH_QMARK)
 256                 return a;
 257
 258         b = assignment(yylex(), noeval | !a);
 259
 260         if (last_token != ARITH_COLON)
 261                 yyerror("expecting ':'");
 262
 263         token = yylex();
 264         *val = yylval;
 265
 266         c = cond(token, val, yylex(), noeval | !!a);
 267
 268         return a ? b : c;
 269 }
 270
 271 static intmax_t assignment(int var, int noeval)
 272 {
 273         union yystype val = yylval;
 274         int op = yylex();
 275         intmax_t result;
 276
 277         if (var != ARITH_VAR)
 278                 return cond(var, &val, op, noeval);
 279
 280         if (op != ARITH_ASS && (op < ARITH_ASS_MIN || op >= ARITH_ASS_MAX))
 281                 return cond(var, &val, op, noeval);
 282
 283         result = assignment(yylex(), noeval);
 284         if (noeval)
 285                 return result;
 286
 287         return setvarint(val.name,
 288                          op == ARITH_ASS ? result :
 289                          do_binop(op - 11, lookupvarint(val.name), result), 0);
 290 }
 291
 292 intmax_t arith(const char *s)
 293 {
 294         intmax_t result;
 295
 296         arith_buf = arith_startbuf = s;
 297
 298         result = assignment(yylex(), 0);
 299
 300         if (last_token)
 301                 yyerror("expecting EOF");
 302
 303         return result;
 304 }