arith_yacc.c revision 218626
159243Sobrien/*- 259243Sobrien * Copyright (c) 1993 359243Sobrien * The Regents of the University of California. All rights reserved. 459243Sobrien * Copyright (c) 2007 559243Sobrien * Herbert Xu <herbert@gondor.apana.org.au>. All rights reserved. 659243Sobrien * 759243Sobrien * This code is derived from software contributed to Berkeley by 859243Sobrien * Kenneth Almquist. 959243Sobrien * 1059243Sobrien * Redistribution and use in source and binary forms, with or without 1159243Sobrien * modification, are permitted provided that the following conditions 1259243Sobrien * are met: 1359243Sobrien * 1. Redistributions of source code must retain the above copyright 1459243Sobrien * notice, this list of conditions and the following disclaimer. 1559243Sobrien * 2. Redistributions in binary form must reproduce the above copyright 1659243Sobrien * notice, this list of conditions and the following disclaimer in the 1759243Sobrien * documentation and/or other materials provided with the distribution. 1859243Sobrien * 3. Neither the name of the University nor the names of its contributors 1959243Sobrien * may be used to endorse or promote products derived from this software 2059243Sobrien * without specific prior written permission. 2159243Sobrien * 2259243Sobrien * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 2359243Sobrien * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2459243Sobrien * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2559243Sobrien * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 2659243Sobrien * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2759243Sobrien * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2859243Sobrien * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2959243Sobrien * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 3059243Sobrien * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 3159243Sobrien * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 3259243Sobrien * SUCH DAMAGE. 3359243Sobrien */ 3459243Sobrien 3559243Sobrien#include <sys/cdefs.h> 3659243Sobrien__FBSDID("$FreeBSD: head/bin/sh/arith_yacc.c 218626 2011-02-12 23:44:05Z jilles $"); 3759243Sobrien 3859243Sobrien#include <sys/limits.h> 3959243Sobrien#include <errno.h> 4059243Sobrien#include <inttypes.h> 4159243Sobrien#include <stdlib.h> 4259243Sobrien#include <stdio.h> 4359243Sobrien#include "arith.h" 4459243Sobrien#include "arith_yacc.h" 4559243Sobrien#include "expand.h" 4659243Sobrien#include "shell.h" 4759243Sobrien#include "error.h" 4859243Sobrien#include "memalloc.h" 4959243Sobrien#include "output.h" 5059243Sobrien#include "options.h" 5159243Sobrien#include "var.h" 5259243Sobrien 5359243Sobrien#if ARITH_BOR + 11 != ARITH_BORASS || ARITH_ASS + 11 != ARITH_EQ 5459243Sobrien#error Arithmetic tokens are out of order. 5559243Sobrien#endif 5659243Sobrien 5759243Sobrienstatic const char *arith_startbuf; 5859243Sobrien 5959243Sobrienconst char *arith_buf; 6059243Sobrienunion yystype yylval; 6159243Sobrien 6259243Sobrienstatic int last_token; 6359243Sobrien 6459243Sobrien#define ARITH_PRECEDENCE(op, prec) [op - ARITH_BINOP_MIN] = prec 6559243Sobrien 6659243Sobrienstatic const char prec[ARITH_BINOP_MAX - ARITH_BINOP_MIN] = { 6759243Sobrien ARITH_PRECEDENCE(ARITH_MUL, 0), 6859243Sobrien ARITH_PRECEDENCE(ARITH_DIV, 0), 6959243Sobrien ARITH_PRECEDENCE(ARITH_REM, 0), 7059243Sobrien ARITH_PRECEDENCE(ARITH_ADD, 1), 7159243Sobrien ARITH_PRECEDENCE(ARITH_SUB, 1), 7259243Sobrien ARITH_PRECEDENCE(ARITH_LSHIFT, 2), 7359243Sobrien ARITH_PRECEDENCE(ARITH_RSHIFT, 2), 7459243Sobrien ARITH_PRECEDENCE(ARITH_LT, 3), 7559243Sobrien ARITH_PRECEDENCE(ARITH_LE, 3), 7659243Sobrien ARITH_PRECEDENCE(ARITH_GT, 3), 7759243Sobrien ARITH_PRECEDENCE(ARITH_GE, 3), 7859243Sobrien ARITH_PRECEDENCE(ARITH_EQ, 4), 7959243Sobrien ARITH_PRECEDENCE(ARITH_NE, 4), 8059243Sobrien ARITH_PRECEDENCE(ARITH_BAND, 5), 8159243Sobrien ARITH_PRECEDENCE(ARITH_BXOR, 6), 8259243Sobrien ARITH_PRECEDENCE(ARITH_BOR, 7), 8359243Sobrien}; 8459243Sobrien 8559243Sobrien#define ARITH_MAX_PREC 8 8659243Sobrien 8759243Sobrienstatic __dead2 void yyerror(const char *s) 8859243Sobrien{ 8959243Sobrien error("arithmetic expression: %s: \"%s\"", s, arith_startbuf); 9059243Sobrien /* NOTREACHED */ 9159243Sobrien} 9259243Sobrien 9359243Sobrienstatic arith_t arith_lookupvarint(char *varname) 9459243Sobrien{ 9559243Sobrien const char *str; 9659243Sobrien char *p; 9759243Sobrien arith_t result; 9859243Sobrien 9959243Sobrien str = lookupvar(varname); 10059243Sobrien if (str == NULL || *str == '\0') 10159243Sobrien str = "0"; 10259243Sobrien errno = 0; 10359243Sobrien result = strtoarith_t(str, &p, 0); 10459243Sobrien if (errno != 0 || *p != '\0') 10559243Sobrien yyerror("variable conversion error"); 10659243Sobrien return result; 10759243Sobrien} 10859243Sobrien 10959243Sobrienstatic inline int arith_prec(int op) 11059243Sobrien{ 11159243Sobrien return prec[op - ARITH_BINOP_MIN]; 11259243Sobrien} 11359243Sobrien 11459243Sobrienstatic inline int higher_prec(int op1, int op2) 11559243Sobrien{ 11659243Sobrien return arith_prec(op1) < arith_prec(op2); 11759243Sobrien} 11859243Sobrien 11959243Sobrienstatic arith_t do_binop(int op, arith_t a, arith_t b) 12059243Sobrien{ 12159243Sobrien 12259243Sobrien switch (op) { 12359243Sobrien default: 12459243Sobrien case ARITH_REM: 12559243Sobrien case ARITH_DIV: 12659243Sobrien if (!b) 12759243Sobrien yyerror("division by zero"); 12859243Sobrien if (a == ARITH_MIN && b == -1) 12959243Sobrien yyerror("divide error"); 13059243Sobrien return op == ARITH_REM ? a % b : a / b; 13159243Sobrien case ARITH_MUL: 13259243Sobrien return a * b; 13359243Sobrien case ARITH_ADD: 13459243Sobrien return a + b; 13559243Sobrien case ARITH_SUB: 13659243Sobrien return a - b; 13759243Sobrien case ARITH_LSHIFT: 13859243Sobrien return a << b; 13959243Sobrien case ARITH_RSHIFT: 14059243Sobrien return a >> b; 14159243Sobrien case ARITH_LT: 14259243Sobrien return a < b; 14359243Sobrien case ARITH_LE: 14459243Sobrien return a <= b; 14559243Sobrien case ARITH_GT: 14659243Sobrien return a > b; 14759243Sobrien case ARITH_GE: 14859243Sobrien return a >= b; 14959243Sobrien case ARITH_EQ: 15059243Sobrien return a == b; 15159243Sobrien case ARITH_NE: 15259243Sobrien return a != b; 15359243Sobrien case ARITH_BAND: 15459243Sobrien return a & b; 15559243Sobrien case ARITH_BXOR: 15659243Sobrien return a ^ b; 15759243Sobrien case ARITH_BOR: 15859243Sobrien return a | b; 15959243Sobrien } 16059243Sobrien} 16159243Sobrien 16259243Sobrienstatic arith_t assignment(int var, int noeval); 16359243Sobrien 16459243Sobrienstatic arith_t primary(int token, union yystype *val, int op, int noeval) 16559243Sobrien{ 16659243Sobrien arith_t result; 16759243Sobrien 16859243Sobrienagain: 16959243Sobrien switch (token) { 17059243Sobrien case ARITH_LPAREN: 17159243Sobrien result = assignment(op, noeval); 17259243Sobrien if (last_token != ARITH_RPAREN) 17359243Sobrien yyerror("expecting ')'"); 17459243Sobrien last_token = yylex(); 17559243Sobrien return result; 17659243Sobrien case ARITH_NUM: 17759243Sobrien last_token = op; 17859243Sobrien return val->val; 17959243Sobrien case ARITH_VAR: 18059243Sobrien last_token = op; 18159243Sobrien return noeval ? val->val : arith_lookupvarint(val->name); 18259243Sobrien case ARITH_ADD: 18359243Sobrien token = op; 18459243Sobrien *val = yylval; 18559243Sobrien op = yylex(); 18659243Sobrien goto again; 18759243Sobrien case ARITH_SUB: 18859243Sobrien *val = yylval; 18959243Sobrien return -primary(op, val, yylex(), noeval); 19059243Sobrien case ARITH_NOT: 19159243Sobrien *val = yylval; 19259243Sobrien return !primary(op, val, yylex(), noeval); 19359243Sobrien case ARITH_BNOT: 19459243Sobrien *val = yylval; 19559243Sobrien return ~primary(op, val, yylex(), noeval); 19659243Sobrien default: 19759243Sobrien yyerror("expecting primary"); 19859243Sobrien } 19959243Sobrien} 20059243Sobrien 20159243Sobrienstatic arith_t binop2(arith_t a, int op, int prec, int noeval) 20259243Sobrien{ 20359243Sobrien for (;;) { 20459243Sobrien union yystype val; 20559243Sobrien arith_t b; 20659243Sobrien int op2; 20759243Sobrien int token; 20859243Sobrien 20959243Sobrien token = yylex(); 21059243Sobrien val = yylval; 21159243Sobrien 21259243Sobrien b = primary(token, &val, yylex(), noeval); 21359243Sobrien 21459243Sobrien op2 = last_token; 21559243Sobrien if (op2 >= ARITH_BINOP_MIN && op2 < ARITH_BINOP_MAX && 21659243Sobrien higher_prec(op2, op)) { 21759243Sobrien b = binop2(b, op2, arith_prec(op), noeval); 21859243Sobrien op2 = last_token; 21959243Sobrien } 22059243Sobrien 22159243Sobrien a = noeval ? b : do_binop(op, a, b); 22259243Sobrien 22359243Sobrien if (op2 < ARITH_BINOP_MIN || op2 >= ARITH_BINOP_MAX || 22459243Sobrien arith_prec(op2) >= prec) 22559243Sobrien return a; 22659243Sobrien 22759243Sobrien op = op2; 22859243Sobrien } 22959243Sobrien} 23059243Sobrien 23159243Sobrienstatic arith_t binop(int token, union yystype *val, int op, int noeval) 23259243Sobrien{ 23359243Sobrien arith_t a = primary(token, val, op, noeval); 23459243Sobrien 23559243Sobrien op = last_token; 23659243Sobrien if (op < ARITH_BINOP_MIN || op >= ARITH_BINOP_MAX) 23759243Sobrien return a; 23859243Sobrien 23959243Sobrien return binop2(a, op, ARITH_MAX_PREC, noeval); 24059243Sobrien} 24159243Sobrien 24259243Sobrienstatic arith_t and(int token, union yystype *val, int op, int noeval) 24359243Sobrien{ 24459243Sobrien arith_t a = binop(token, val, op, noeval); 24559243Sobrien arith_t b; 24659243Sobrien 24759243Sobrien op = last_token; 24859243Sobrien if (op != ARITH_AND) 24959243Sobrien return a; 25059243Sobrien 25159243Sobrien token = yylex(); 25259243Sobrien *val = yylval; 25359243Sobrien 25459243Sobrien b = and(token, val, yylex(), noeval | !a); 25559243Sobrien 25659243Sobrien return a && b; 25759243Sobrien} 25859243Sobrien 25959243Sobrienstatic arith_t or(int token, union yystype *val, int op, int noeval) 26059243Sobrien{ 26159243Sobrien arith_t a = and(token, val, op, noeval); 26259243Sobrien arith_t b; 26359243Sobrien 26459243Sobrien op = last_token; 26559243Sobrien if (op != ARITH_OR) 26659243Sobrien return a; 26759243Sobrien 26859243Sobrien token = yylex(); 26959243Sobrien *val = yylval; 27059243Sobrien 27159243Sobrien b = or(token, val, yylex(), noeval | !!a); 27259243Sobrien 27359243Sobrien return a || b; 27459243Sobrien} 27559243Sobrien 27659243Sobrienstatic arith_t cond(int token, union yystype *val, int op, int noeval) 27759243Sobrien{ 27859243Sobrien arith_t a = or(token, val, op, noeval); 279 arith_t b; 280 arith_t c; 281 282 if (last_token != ARITH_QMARK) 283 return a; 284 285 b = assignment(yylex(), noeval | !a); 286 287 if (last_token != ARITH_COLON) 288 yyerror("expecting ':'"); 289 290 token = yylex(); 291 *val = yylval; 292 293 c = cond(token, val, yylex(), noeval | !!a); 294 295 return a ? b : c; 296} 297 298static arith_t assignment(int var, int noeval) 299{ 300 union yystype val = yylval; 301 int op = yylex(); 302 arith_t result; 303 char sresult[DIGITS(result) + 1]; 304 305 if (var != ARITH_VAR) 306 return cond(var, &val, op, noeval); 307 308 if (op != ARITH_ASS && (op < ARITH_ASS_MIN || op >= ARITH_ASS_MAX)) 309 return cond(var, &val, op, noeval); 310 311 result = assignment(yylex(), noeval); 312 if (noeval) 313 return result; 314 315 if (op != ARITH_ASS) 316 result = do_binop(op - 11, arith_lookupvarint(val.name), result); 317 snprintf(sresult, sizeof(sresult), ARITH_FORMAT_STR, result); 318 setvar(val.name, sresult, 0); 319 return result; 320} 321 322arith_t arith(const char *s) 323{ 324 struct stackmark smark; 325 arith_t result; 326 327 setstackmark(&smark); 328 329 arith_buf = arith_startbuf = s; 330 331 result = assignment(yylex(), 0); 332 333 if (last_token) 334 yyerror("expecting EOF"); 335 336 popstackmark(&smark); 337 338 return result; 339} 340 341/* 342 * The exp(1) builtin. 343 */ 344int 345expcmd(int argc, char **argv) 346{ 347 const char *p; 348 char *concat; 349 char **ap; 350 arith_t i; 351 352 if (argc > 1) { 353 p = argv[1]; 354 if (argc > 2) { 355 /* 356 * Concatenate arguments. 357 */ 358 STARTSTACKSTR(concat); 359 ap = argv + 2; 360 for (;;) { 361 while (*p) 362 STPUTC(*p++, concat); 363 if ((p = *ap++) == NULL) 364 break; 365 STPUTC(' ', concat); 366 } 367 STPUTC('\0', concat); 368 p = grabstackstr(concat); 369 } 370 } else 371 p = ""; 372 373 i = arith(p); 374 375 out1fmt(ARITH_FORMAT_STR "\n", i); 376 return !i; 377} 378 379