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 * $FreeBSD: src/bin/sh/arith_yacc.c,v 1.3 2011/03/05 13:27:13 jilles Exp $ 35 */ 36 37 #include <sys/limits.h> 38 #include <errno.h> 39 #include <inttypes.h> 40 #include <stdlib.h> 41 #include <stdio.h> 42 #include "arith.h" 43 #include "arith_yacc.h" 44 #include "expand.h" 45 #include "shell.h" 46 #include "error.h" 47 #include "memalloc.h" 48 #include "output.h" 49 #include "options.h" 50 #include "var.h" 51 52 #if ARITH_BOR + 11 != ARITH_BORASS || ARITH_ASS + 11 != ARITH_EQ 53 #error Arithmetic tokens are out of order. 54 #endif 55 56 static const char *arith_startbuf; 57 58 const char *arith_buf; 59 union yystype yylval; 60 61 static int last_token; 62 63 #define ARITH_PRECEDENCE(op, prec) [op - ARITH_BINOP_MIN] = prec 64 65 static const char prec[ARITH_BINOP_MAX - ARITH_BINOP_MIN] = { 66 ARITH_PRECEDENCE(ARITH_MUL, 0), 67 ARITH_PRECEDENCE(ARITH_DIV, 0), 68 ARITH_PRECEDENCE(ARITH_REM, 0), 69 ARITH_PRECEDENCE(ARITH_ADD, 1), 70 ARITH_PRECEDENCE(ARITH_SUB, 1), 71 ARITH_PRECEDENCE(ARITH_LSHIFT, 2), 72 ARITH_PRECEDENCE(ARITH_RSHIFT, 2), 73 ARITH_PRECEDENCE(ARITH_LT, 3), 74 ARITH_PRECEDENCE(ARITH_LE, 3), 75 ARITH_PRECEDENCE(ARITH_GT, 3), 76 ARITH_PRECEDENCE(ARITH_GE, 3), 77 ARITH_PRECEDENCE(ARITH_EQ, 4), 78 ARITH_PRECEDENCE(ARITH_NE, 4), 79 ARITH_PRECEDENCE(ARITH_BAND, 5), 80 ARITH_PRECEDENCE(ARITH_BXOR, 6), 81 ARITH_PRECEDENCE(ARITH_BOR, 7), 82 }; 83 84 #define ARITH_MAX_PREC 8 85 86 static __dead2 void 87 yyerror(const char *s) 88 { 89 error("arithmetic expression: %s: \"%s\"", s, arith_startbuf); 90 /* NOTREACHED */ 91 } 92 93 static arith_t 94 arith_lookupvarint(char *varname) 95 { 96 const char *str; 97 char *p; 98 arith_t result; 99 100 str = lookupvar(varname); 101 if (str == NULL || *str == '\0') 102 str = "0"; 103 errno = 0; 104 result = strtoarith_t(str, &p, 0); 105 if (errno != 0 || *p != '\0') 106 yyerror("variable conversion error"); 107 return result; 108 } 109 110 static inline int 111 arith_prec(int op) 112 { 113 return prec[op - ARITH_BINOP_MIN]; 114 } 115 116 static inline int 117 higher_prec(int op1, int op2) 118 { 119 return arith_prec(op1) < arith_prec(op2); 120 } 121 122 static arith_t 123 do_binop(int op, arith_t a, arith_t b) 124 { 125 126 switch (op) { 127 default: 128 case ARITH_REM: 129 case ARITH_DIV: 130 if (!b) 131 yyerror("division by zero"); 132 if (a == ARITH_MIN && b == -1) 133 yyerror("divide error"); 134 return op == ARITH_REM ? a % b : a / b; 135 case ARITH_MUL: 136 return a * b; 137 case ARITH_ADD: 138 return a + b; 139 case ARITH_SUB: 140 return a - b; 141 case ARITH_LSHIFT: 142 return a << b; 143 case ARITH_RSHIFT: 144 return a >> b; 145 case ARITH_LT: 146 return a < b; 147 case ARITH_LE: 148 return a <= b; 149 case ARITH_GT: 150 return a > b; 151 case ARITH_GE: 152 return a >= b; 153 case ARITH_EQ: 154 return a == b; 155 case ARITH_NE: 156 return a != b; 157 case ARITH_BAND: 158 return a & b; 159 case ARITH_BXOR: 160 return a ^ b; 161 case ARITH_BOR: 162 return a | b; 163 } 164 } 165 166 static arith_t assignment(int var, int noeval); 167 168 static arith_t 169 primary(int token, union yystype *val, int op, int noeval) 170 { 171 arith_t result; 172 173 again: 174 switch (token) { 175 case ARITH_LPAREN: 176 result = assignment(op, noeval); 177 if (last_token != ARITH_RPAREN) 178 yyerror("expecting ')'"); 179 last_token = yylex(); 180 return result; 181 case ARITH_NUM: 182 last_token = op; 183 return val->val; 184 case ARITH_VAR: 185 last_token = op; 186 return noeval ? val->val : arith_lookupvarint(val->name); 187 case ARITH_ADD: 188 token = op; 189 *val = yylval; 190 op = yylex(); 191 goto again; 192 case ARITH_SUB: 193 *val = yylval; 194 return -primary(op, val, yylex(), noeval); 195 case ARITH_NOT: 196 *val = yylval; 197 return !primary(op, val, yylex(), noeval); 198 case ARITH_BNOT: 199 *val = yylval; 200 return ~primary(op, val, yylex(), noeval); 201 default: 202 yyerror("expecting primary"); 203 } 204 } 205 206 static arith_t 207 binop2(arith_t a, int op, int precedence, int noeval) 208 { 209 for (;;) { 210 union yystype val; 211 arith_t b; 212 int op2; 213 int token; 214 215 token = yylex(); 216 val = yylval; 217 218 b = primary(token, &val, yylex(), noeval); 219 220 op2 = last_token; 221 if (op2 >= ARITH_BINOP_MIN && op2 < ARITH_BINOP_MAX && 222 higher_prec(op2, op)) { 223 b = binop2(b, op2, arith_prec(op), noeval); 224 op2 = last_token; 225 } 226 227 a = noeval ? b : do_binop(op, a, b); 228 229 if (op2 < ARITH_BINOP_MIN || op2 >= ARITH_BINOP_MAX || 230 arith_prec(op2) >= precedence) 231 return a; 232 233 op = op2; 234 } 235 } 236 237 static arith_t 238 binop(int token, union yystype *val, int op, int noeval) 239 { 240 arith_t a = primary(token, val, op, noeval); 241 242 op = last_token; 243 if (op < ARITH_BINOP_MIN || op >= ARITH_BINOP_MAX) 244 return a; 245 246 return binop2(a, op, ARITH_MAX_PREC, noeval); 247 } 248 249 static arith_t 250 and(int token, union yystype *val, int op, int noeval) 251 { 252 arith_t a = binop(token, val, op, noeval); 253 arith_t b; 254 255 op = last_token; 256 if (op != ARITH_AND) 257 return a; 258 259 token = yylex(); 260 *val = yylval; 261 262 b = and(token, val, yylex(), noeval | !a); 263 264 return a && b; 265 } 266 267 static arith_t 268 or(int token, union yystype *val, int op, int noeval) 269 { 270 arith_t a = and(token, val, op, noeval); 271 arith_t b; 272 273 op = last_token; 274 if (op != ARITH_OR) 275 return a; 276 277 token = yylex(); 278 *val = yylval; 279 280 b = or(token, val, yylex(), noeval | !!a); 281 282 return a || b; 283 } 284 285 static arith_t 286 cond(int token, union yystype *val, int op, int noeval) 287 { 288 arith_t a = or(token, val, op, noeval); 289 arith_t b; 290 arith_t c; 291 292 if (last_token != ARITH_QMARK) 293 return a; 294 295 b = assignment(yylex(), noeval | !a); 296 297 if (last_token != ARITH_COLON) 298 yyerror("expecting ':'"); 299 300 token = yylex(); 301 *val = yylval; 302 303 c = cond(token, val, yylex(), noeval | !!a); 304 305 return a ? b : c; 306 } 307 308 static arith_t 309 assignment(int var, int noeval) 310 { 311 union yystype val = yylval; 312 int op = yylex(); 313 arith_t result; 314 char sresult[DIGITS(result) + 1]; 315 316 if (var != ARITH_VAR) 317 return cond(var, &val, op, noeval); 318 319 if (op != ARITH_ASS && (op < ARITH_ASS_MIN || op >= ARITH_ASS_MAX)) 320 return cond(var, &val, op, noeval); 321 322 result = assignment(yylex(), noeval); 323 if (noeval) 324 return result; 325 326 if (op != ARITH_ASS) 327 result = do_binop(op - 11, arith_lookupvarint(val.name), result); 328 snprintf(sresult, sizeof(sresult), ARITH_FORMAT_STR, result); 329 setvar(val.name, sresult, 0); 330 return result; 331 } 332 333 arith_t 334 arith(const char *s) 335 { 336 struct stackmark smark; 337 arith_t result; 338 339 setstackmark(&smark); 340 341 arith_buf = arith_startbuf = s; 342 343 result = assignment(yylex(), 0); 344 345 if (last_token) 346 yyerror("expecting EOF"); 347 348 popstackmark(&smark); 349 350 return result; 351 } 352 353 /* 354 * The exp(1) builtin. 355 */ 356 int 357 expcmd(int argc, char **argv) 358 { 359 const char *p; 360 char *concat; 361 char **ap; 362 arith_t i; 363 364 if (argc > 1) { 365 p = argv[1]; 366 if (argc > 2) { 367 /* 368 * Concatenate arguments. 369 */ 370 STARTSTACKSTR(concat); 371 ap = argv + 2; 372 for (;;) { 373 while (*p) 374 STPUTC(*p++, concat); 375 if ((p = *ap++) == NULL) 376 break; 377 STPUTC(' ', concat); 378 } 379 STPUTC('\0', concat); 380 p = grabstackstr(concat); 381 } 382 } else 383 p = ""; 384 385 i = arith(p); 386 387 out1fmt(ARITH_FORMAT_STR "\n", i); 388 return !i; 389 } 390 391