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 48static const char *arith_startbuf; 49 50const char *arith_buf; 51union yystype yylval; 52 53static int last_token; 54 55#define ARITH_PRECEDENCE(op, prec) [op - ARITH_BINOP_MIN] = prec 56 57static 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 78static void yyerror(const char *s) __attribute__ ((noreturn)); 79static void yyerror(const char *s) 80{ 81 sh_error("arithmetic expression: %s: \"%s\"", s, arith_startbuf); 82 /* NOTREACHED */ 83} 84 85static inline int arith_prec(int op) 86{ 87 return prec[op - ARITH_BINOP_MIN]; 88} 89 90static inline int higher_prec(int op1, int op2) 91{ 92 return arith_prec(op1) < arith_prec(op2); 93} 94 95static 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 135static intmax_t assignment(int var, int noeval); 136 137static intmax_t primary(int token, union yystype *val, int op, int noeval) 138{ 139 intmax_t result; 140 141again: 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 174static 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 204static 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 215static 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 232static 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 249static 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 271static 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 292intmax_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} 305