arith_yacc.c revision 218466
1107120Sjulian/*- 2107120Sjulian * Copyright (c) 1993 3107120Sjulian * The Regents of the University of California. All rights reserved. 4107120Sjulian * Copyright (c) 2007 5107120Sjulian * Herbert Xu <herbert@gondor.apana.org.au>. All rights reserved. 6107120Sjulian * 7107120Sjulian * This code is derived from software contributed to Berkeley by 8107120Sjulian * Kenneth Almquist. 9107120Sjulian * 10107120Sjulian * Redistribution and use in source and binary forms, with or without 11107120Sjulian * modification, are permitted provided that the following conditions 12107120Sjulian * are met: 13107120Sjulian * 1. Redistributions of source code must retain the above copyright 14107120Sjulian * notice, this list of conditions and the following disclaimer. 15107120Sjulian * 2. Redistributions in binary form must reproduce the above copyright 16107120Sjulian * notice, this list of conditions and the following disclaimer in the 17107120Sjulian * documentation and/or other materials provided with the distribution. 18107120Sjulian * 3. Neither the name of the University nor the names of its contributors 19107120Sjulian * may be used to endorse or promote products derived from this software 20107120Sjulian * without specific prior written permission. 21107120Sjulian * 22107120Sjulian * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 23107120Sjulian * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24107120Sjulian * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25107120Sjulian * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 26107120Sjulian * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27107120Sjulian * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28121054Semax * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29107120Sjulian * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30107120Sjulian * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31107120Sjulian * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32107120Sjulian * SUCH DAMAGE. 33107120Sjulian */ 34107120Sjulian 35107120Sjulian#include <sys/cdefs.h> 36107120Sjulian__FBSDID("$FreeBSD: head/bin/sh/arith_yacc.c 218466 2011-02-08 23:18:06Z jilles $"); 37121054Semax 38107120Sjulian#include <sys/limits.h> 39107120Sjulian#include <errno.h> 40107120Sjulian#include <inttypes.h> 41107120Sjulian#include <stdlib.h> 42107120Sjulian#include <stdio.h> 43107120Sjulian#include "arith.h" 44107120Sjulian#include "arith_yacc.h" 45107120Sjulian#include "expand.h" 46107120Sjulian#include "shell.h" 47107120Sjulian#include "error.h" 48107120Sjulian#include "memalloc.h" 49107120Sjulian#include "output.h" 50107120Sjulian#include "options.h" 51107120Sjulian#include "var.h" 52107120Sjulian 53107120Sjulian#if ARITH_BOR + 11 != ARITH_BORASS || ARITH_ASS + 11 != ARITH_EQ 54107120Sjulian#error Arithmetic tokens are out of order. 55107120Sjulian#endif 56107120Sjulian 57107120Sjulianstatic const char *arith_startbuf; 58107120Sjulian 59107120Sjulianconst char *arith_buf; 60107120Sjulianunion yystype yylval; 61107120Sjulian 62107120Sjulianstatic int last_token; 63107120Sjulian 64107120Sjulian#define ARITH_PRECEDENCE(op, prec) [op - ARITH_BINOP_MIN] = prec 65107120Sjulian 66107120Sjulianstatic const char prec[ARITH_BINOP_MAX - ARITH_BINOP_MIN] = { 67107120Sjulian ARITH_PRECEDENCE(ARITH_MUL, 0), 68107120Sjulian ARITH_PRECEDENCE(ARITH_DIV, 0), 69114879Sjulian ARITH_PRECEDENCE(ARITH_REM, 0), 70107120Sjulian ARITH_PRECEDENCE(ARITH_ADD, 1), 71107120Sjulian ARITH_PRECEDENCE(ARITH_SUB, 1), 72107120Sjulian ARITH_PRECEDENCE(ARITH_LSHIFT, 2), 73107120Sjulian ARITH_PRECEDENCE(ARITH_RSHIFT, 2), 74107120Sjulian ARITH_PRECEDENCE(ARITH_LT, 3), 75107120Sjulian ARITH_PRECEDENCE(ARITH_LE, 3), 76107120Sjulian ARITH_PRECEDENCE(ARITH_GT, 3), 77107120Sjulian ARITH_PRECEDENCE(ARITH_GE, 3), 78107120Sjulian ARITH_PRECEDENCE(ARITH_EQ, 4), 79107120Sjulian ARITH_PRECEDENCE(ARITH_NE, 4), 80107120Sjulian ARITH_PRECEDENCE(ARITH_BAND, 5), 81107120Sjulian ARITH_PRECEDENCE(ARITH_BXOR, 6), 82107120Sjulian ARITH_PRECEDENCE(ARITH_BOR, 7), 83107120Sjulian}; 84107120Sjulian 85107120Sjulian#define ARITH_MAX_PREC 8 86107120Sjulian 87107120Sjulianstatic __dead2 void yyerror(const char *s) 88107120Sjulian{ 89114879Sjulian error("arithmetic expression: %s: \"%s\"", s, arith_startbuf); 90107120Sjulian /* NOTREACHED */ 91107120Sjulian} 92107120Sjulian 93107120Sjulianstatic arith_t arith_lookupvarint(char *varname) 94107120Sjulian{ 95107120Sjulian const char *str; 96107120Sjulian char *p; 97107120Sjulian arith_t result; 98107120Sjulian 99107120Sjulian str = lookupvar(varname); 100107120Sjulian if (str == NULL || *str == '\0') 101107120Sjulian str = "0"; 102107120Sjulian errno = 0; 103107120Sjulian result = strtoarith_t(str, &p, 0); 104188130Semax if (errno != 0 || *p != '\0') 105188130Semax yyerror("variable conversion error"); 106188130Semax return result; 107188130Semax} 108107120Sjulian 109107120Sjulianstatic inline int arith_prec(int op) 110107120Sjulian{ 111107120Sjulian return prec[op - ARITH_BINOP_MIN]; 112107120Sjulian} 113107120Sjulian 114107120Sjulianstatic inline int higher_prec(int op1, int op2) 115107120Sjulian{ 116107120Sjulian return arith_prec(op1) < arith_prec(op2); 117107120Sjulian} 118107120Sjulian 119107120Sjulianstatic arith_t do_binop(int op, arith_t a, arith_t b) 120107120Sjulian{ 121107120Sjulian 122107120Sjulian switch (op) { 123107120Sjulian default: 124107120Sjulian case ARITH_REM: 125107120Sjulian case ARITH_DIV: 126107120Sjulian if (!b) 127107120Sjulian yyerror("division by zero"); 128107120Sjulian return op == ARITH_REM ? a % b : a / b; 129107120Sjulian case ARITH_MUL: 130107120Sjulian return a * b; 131107120Sjulian case ARITH_ADD: 132107120Sjulian return a + b; 133107120Sjulian case ARITH_SUB: 134107120Sjulian return a - b; 135107120Sjulian case ARITH_LSHIFT: 136107120Sjulian return a << b; 137107120Sjulian case ARITH_RSHIFT: 138107120Sjulian return a >> b; 139107120Sjulian case ARITH_LT: 140107120Sjulian return a < b; 141107120Sjulian case ARITH_LE: 142107120Sjulian return a <= b; 143107120Sjulian case ARITH_GT: 144107120Sjulian return a > b; 145107120Sjulian case ARITH_GE: 146107120Sjulian return a >= b; 147107120Sjulian case ARITH_EQ: 148107120Sjulian return a == b; 149107120Sjulian case ARITH_NE: 150107120Sjulian return a != b; 151107120Sjulian case ARITH_BAND: 152107120Sjulian return a & b; 153107120Sjulian case ARITH_BXOR: 154107120Sjulian return a ^ b; 155107120Sjulian case ARITH_BOR: 156107120Sjulian return a | b; 157107120Sjulian } 158107120Sjulian} 159107120Sjulian 160107120Sjulianstatic arith_t assignment(int var, int noeval); 161107120Sjulian 162107120Sjulianstatic arith_t primary(int token, union yystype *val, int op, int noeval) 163122758Sharti{ 164107120Sjulian arith_t result; 165107120Sjulian 166107120Sjulianagain: 167107120Sjulian switch (token) { 168107120Sjulian case ARITH_LPAREN: 169107120Sjulian result = assignment(op, noeval); 170107120Sjulian if (last_token != ARITH_RPAREN) 171107120Sjulian yyerror("expecting ')'"); 172107120Sjulian last_token = yylex(); 173107120Sjulian return result; 174107120Sjulian case ARITH_NUM: 175107120Sjulian last_token = op; 176107120Sjulian return val->val; 177107120Sjulian case ARITH_VAR: 178107120Sjulian last_token = op; 179107120Sjulian return noeval ? val->val : arith_lookupvarint(val->name); 180107120Sjulian case ARITH_ADD: 181107120Sjulian token = op; 182107120Sjulian *val = yylval; 183107120Sjulian op = yylex(); 184107120Sjulian goto again; 185107120Sjulian case ARITH_SUB: 186107120Sjulian *val = yylval; 187107120Sjulian return -primary(op, val, yylex(), noeval); 188107120Sjulian case ARITH_NOT: 189107120Sjulian *val = yylval; 190107120Sjulian return !primary(op, val, yylex(), noeval); 191107120Sjulian case ARITH_BNOT: 192107120Sjulian *val = yylval; 193107120Sjulian return ~primary(op, val, yylex(), noeval); 194107120Sjulian default: 195107120Sjulian yyerror("expecting primary"); 196107120Sjulian } 197107120Sjulian} 198107120Sjulian 199107120Sjulianstatic arith_t binop2(arith_t a, int op, int prec, int noeval) 200107120Sjulian{ 201107120Sjulian for (;;) { 202107120Sjulian union yystype val; 203107120Sjulian arith_t b; 204107120Sjulian int op2; 205107120Sjulian int token; 206107120Sjulian 207107120Sjulian token = yylex(); 208107120Sjulian val = yylval; 209107120Sjulian 210107120Sjulian b = primary(token, &val, yylex(), noeval); 211107120Sjulian 212107120Sjulian op2 = last_token; 213107120Sjulian if (op2 >= ARITH_BINOP_MIN && op2 < ARITH_BINOP_MAX && 214107120Sjulian higher_prec(op2, op)) { 215107120Sjulian b = binop2(b, op2, arith_prec(op), noeval); 216107120Sjulian op2 = last_token; 217107120Sjulian } 218107120Sjulian 219107120Sjulian a = noeval ? b : do_binop(op, a, b); 220107120Sjulian 221107120Sjulian if (op2 < ARITH_BINOP_MIN || op2 >= ARITH_BINOP_MAX || 222107120Sjulian arith_prec(op2) >= prec) 223107120Sjulian return a; 224107120Sjulian 225107120Sjulian op = op2; 226107120Sjulian } 227107120Sjulian} 228107120Sjulian 229107120Sjulianstatic arith_t binop(int token, union yystype *val, int op, int noeval) 230107120Sjulian{ 231107120Sjulian arith_t a = primary(token, val, op, noeval); 232107120Sjulian 233107120Sjulian op = last_token; 234107120Sjulian if (op < ARITH_BINOP_MIN || op >= ARITH_BINOP_MAX) 235107120Sjulian return a; 236107120Sjulian 237107120Sjulian return binop2(a, op, ARITH_MAX_PREC, noeval); 238107120Sjulian} 239107120Sjulian 240107120Sjulianstatic arith_t and(int token, union yystype *val, int op, int noeval) 241107120Sjulian{ 242107120Sjulian arith_t a = binop(token, val, op, noeval); 243107120Sjulian arith_t b; 244107120Sjulian 245107120Sjulian op = last_token; 246107120Sjulian if (op != ARITH_AND) 247107120Sjulian return a; 248107120Sjulian 249107120Sjulian token = yylex(); 250107120Sjulian *val = yylval; 251107120Sjulian 252107120Sjulian b = and(token, val, yylex(), noeval | !a); 253107120Sjulian 254107120Sjulian return a && b; 255107120Sjulian} 256107120Sjulian 257107120Sjulianstatic arith_t or(int token, union yystype *val, int op, int noeval) 258114879Sjulian{ 259107120Sjulian arith_t a = and(token, val, op, noeval); 260244040Seadler arith_t b; 261107120Sjulian 262107120Sjulian op = last_token; 263114879Sjulian if (op != ARITH_OR) 264114879Sjulian return a; 265107120Sjulian 266107120Sjulian token = yylex(); 267107120Sjulian *val = yylval; 268107120Sjulian 269 b = or(token, val, yylex(), noeval | !!a); 270 271 return a || b; 272} 273 274static arith_t cond(int token, union yystype *val, int op, int noeval) 275{ 276 arith_t a = or(token, val, op, noeval); 277 arith_t b; 278 arith_t c; 279 280 if (last_token != ARITH_QMARK) 281 return a; 282 283 b = assignment(yylex(), noeval | !a); 284 285 if (last_token != ARITH_COLON) 286 yyerror("expecting ':'"); 287 288 token = yylex(); 289 *val = yylval; 290 291 c = cond(token, val, yylex(), noeval | !!a); 292 293 return a ? b : c; 294} 295 296static arith_t assignment(int var, int noeval) 297{ 298 union yystype val = yylval; 299 int op = yylex(); 300 arith_t result; 301 char sresult[DIGITS(result) + 1]; 302 303 if (var != ARITH_VAR) 304 return cond(var, &val, op, noeval); 305 306 if (op != ARITH_ASS && (op < ARITH_ASS_MIN || op >= ARITH_ASS_MAX)) 307 return cond(var, &val, op, noeval); 308 309 result = assignment(yylex(), noeval); 310 if (noeval) 311 return result; 312 313 if (op != ARITH_ASS) 314 result = do_binop(op - 11, arith_lookupvarint(val.name), result); 315 snprintf(sresult, sizeof(sresult), ARITH_FORMAT_STR, result); 316 setvar(val.name, sresult, 0); 317 return result; 318} 319 320arith_t arith(const char *s) 321{ 322 struct stackmark smark; 323 arith_t result; 324 325 setstackmark(&smark); 326 327 arith_buf = arith_startbuf = s; 328 329 result = assignment(yylex(), 0); 330 331 if (last_token) 332 yyerror("expecting EOF"); 333 334 popstackmark(&smark); 335 336 return result; 337} 338 339/* 340 * The exp(1) builtin. 341 */ 342int 343expcmd(int argc, char **argv) 344{ 345 const char *p; 346 char *concat; 347 char **ap; 348 arith_t i; 349 350 if (argc > 1) { 351 p = argv[1]; 352 if (argc > 2) { 353 /* 354 * Concatenate arguments. 355 */ 356 STARTSTACKSTR(concat); 357 ap = argv + 2; 358 for (;;) { 359 while (*p) 360 STPUTC(*p++, concat); 361 if ((p = *ap++) == NULL) 362 break; 363 STPUTC(' ', concat); 364 } 365 STPUTC('\0', concat); 366 p = grabstackstr(concat); 367 } 368 } else 369 p = ""; 370 371 i = arith(p); 372 373 out1fmt(ARITH_FORMAT_STR "\n", i); 374 return !i; 375} 376 377