arith_yacc.c revision 227369
1110130Sjake/*- 2110130Sjake * Copyright (c) 1993 3110130Sjake * The Regents of the University of California. All rights reserved. 4110130Sjake * Copyright (c) 2007 5110130Sjake * Herbert Xu <herbert@gondor.apana.org.au>. All rights reserved. 6110130Sjake * 7110130Sjake * This code is derived from software contributed to Berkeley by 8110130Sjake * Kenneth Almquist. 9110130Sjake * 10110130Sjake * Redistribution and use in source and binary forms, with or without 11110130Sjake * modification, are permitted provided that the following conditions 12110130Sjake * are met: 13110130Sjake * 1. Redistributions of source code must retain the above copyright 14110130Sjake * notice, this list of conditions and the following disclaimer. 15110130Sjake * 2. Redistributions in binary form must reproduce the above copyright 16110130Sjake * notice, this list of conditions and the following disclaimer in the 17110130Sjake * documentation and/or other materials provided with the distribution. 18110130Sjake * 3. Neither the name of the University nor the names of its contributors 19110130Sjake * may be used to endorse or promote products derived from this software 20110130Sjake * without specific prior written permission. 21110130Sjake * 22110130Sjake * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 23110130Sjake * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24110130Sjake * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25110130Sjake * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 26110130Sjake * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27110130Sjake * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28110130Sjake * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29110130Sjake * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30110130Sjake * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31110130Sjake * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32110130Sjake * SUCH DAMAGE. 33110130Sjake */ 34110130Sjake 35110130Sjake#include <sys/cdefs.h> 36110130Sjake__FBSDID("$FreeBSD: head/bin/sh/arith_yacc.c 227369 2011-11-08 23:54:39Z jilles $"); 37110130Sjake 38110130Sjake#include <limits.h> 39110130Sjake#include <errno.h> 40110130Sjake#include <inttypes.h> 41110130Sjake#include <stdlib.h> 42110130Sjake#include <stdio.h> 43110130Sjake#include "arith.h" 44110130Sjake#include "arith_yacc.h" 45110130Sjake#include "expand.h" 46110130Sjake#include "shell.h" 47110130Sjake#include "error.h" 48110130Sjake#include "memalloc.h" 49110130Sjake#include "output.h" 50110130Sjake#include "options.h" 51110130Sjake#include "var.h" 52110130Sjake 53110130Sjake#if ARITH_BOR + 11 != ARITH_BORASS || ARITH_ASS + 11 != ARITH_EQ 54110130Sjake#error Arithmetic tokens are out of order. 55110130Sjake#endif 56110130Sjake 57110130Sjakestatic const char *arith_startbuf; 58110130Sjake 59110130Sjakeconst char *arith_buf; 60110130Sjakeunion yystype yylval; 61110130Sjake 62110130Sjakestatic int last_token; 63110130Sjake 64110130Sjake#define ARITH_PRECEDENCE(op, prec) [op - ARITH_BINOP_MIN] = prec 65110130Sjake 66110130Sjakestatic const char prec[ARITH_BINOP_MAX - ARITH_BINOP_MIN] = { 67110130Sjake ARITH_PRECEDENCE(ARITH_MUL, 0), 68110130Sjake ARITH_PRECEDENCE(ARITH_DIV, 0), 69110130Sjake ARITH_PRECEDENCE(ARITH_REM, 0), 70110130Sjake ARITH_PRECEDENCE(ARITH_ADD, 1), 71110130Sjake ARITH_PRECEDENCE(ARITH_SUB, 1), 72110130Sjake ARITH_PRECEDENCE(ARITH_LSHIFT, 2), 73113538Sjake ARITH_PRECEDENCE(ARITH_RSHIFT, 2), 74113538Sjake ARITH_PRECEDENCE(ARITH_LT, 3), 75110130Sjake ARITH_PRECEDENCE(ARITH_LE, 3), 76110130Sjake ARITH_PRECEDENCE(ARITH_GT, 3), 77110130Sjake ARITH_PRECEDENCE(ARITH_GE, 3), 78110130Sjake ARITH_PRECEDENCE(ARITH_EQ, 4), 79110130Sjake ARITH_PRECEDENCE(ARITH_NE, 4), 80110130Sjake ARITH_PRECEDENCE(ARITH_BAND, 5), 81110130Sjake ARITH_PRECEDENCE(ARITH_BXOR, 6), 82110130Sjake ARITH_PRECEDENCE(ARITH_BOR, 7), 83110130Sjake}; 84110130Sjake 85110130Sjake#define ARITH_MAX_PREC 8 86110130Sjake 87110130Sjakestatic __dead2 void yyerror(const char *s) 88110130Sjake{ 89110130Sjake error("arithmetic expression: %s: \"%s\"", s, arith_startbuf); 90110130Sjake /* NOTREACHED */ 91110130Sjake} 92110130Sjake 93110130Sjakestatic arith_t arith_lookupvarint(char *varname) 94110130Sjake{ 95110130Sjake const char *str; 96110130Sjake char *p; 97110130Sjake arith_t result; 98110130Sjake 99110130Sjake str = lookupvar(varname); 100110130Sjake if (uflag && str == NULL) 101110130Sjake yyerror("variable not set"); 102110130Sjake if (str == NULL || *str == '\0') 103110130Sjake str = "0"; 104110130Sjake errno = 0; 105110130Sjake result = strtoarith_t(str, &p, 0); 106110130Sjake if (errno != 0 || *p != '\0') 107113538Sjake yyerror("variable conversion error"); 108113538Sjake return result; 109110130Sjake} 110110130Sjake 111110130Sjakestatic inline int arith_prec(int op) 112110130Sjake{ 113110130Sjake return prec[op - ARITH_BINOP_MIN]; 114110130Sjake} 115110130Sjake 116110130Sjakestatic inline int higher_prec(int op1, int op2) 117110130Sjake{ 118110130Sjake return arith_prec(op1) < arith_prec(op2); 119110130Sjake} 120110130Sjake 121110130Sjakestatic arith_t do_binop(int op, arith_t a, arith_t b) 122110130Sjake{ 123110130Sjake 124110130Sjake switch (op) { 125110130Sjake default: 126110130Sjake case ARITH_REM: 127110130Sjake case ARITH_DIV: 128110130Sjake if (!b) 129110130Sjake yyerror("division by zero"); 130110130Sjake if (a == ARITH_MIN && b == -1) 131110130Sjake yyerror("divide error"); 132110130Sjake return op == ARITH_REM ? a % b : a / b; 133110130Sjake case ARITH_MUL: 134110130Sjake return (uintmax_t)a * (uintmax_t)b; 135110130Sjake case ARITH_ADD: 136110130Sjake return (uintmax_t)a + (uintmax_t)b; 137110130Sjake case ARITH_SUB: 138110130Sjake return (uintmax_t)a - (uintmax_t)b; 139110130Sjake case ARITH_LSHIFT: 140110130Sjake return a << b; 141110130Sjake case ARITH_RSHIFT: 142110130Sjake return a >> b; 143110130Sjake case ARITH_LT: 144110130Sjake return a < b; 145110130Sjake case ARITH_LE: 146110130Sjake return a <= b; 147110130Sjake case ARITH_GT: 148110130Sjake return a > b; 149110130Sjake case ARITH_GE: 150110130Sjake return a >= b; 151110130Sjake case ARITH_EQ: 152110130Sjake return a == b; 153110130Sjake case ARITH_NE: 154110130Sjake return a != b; 155110130Sjake case ARITH_BAND: 156110130Sjake return a & b; 157110130Sjake case ARITH_BXOR: 158110130Sjake return a ^ b; 159110130Sjake case ARITH_BOR: 160110130Sjake return a | b; 161110130Sjake } 162110130Sjake} 163110130Sjake 164110130Sjakestatic arith_t assignment(int var, int noeval); 165110130Sjake 166110130Sjakestatic arith_t primary(int token, union yystype *val, int op, int noeval) 167110130Sjake{ 168110130Sjake arith_t result; 169110130Sjake 170110130Sjakeagain: 171110130Sjake switch (token) { 172110130Sjake case ARITH_LPAREN: 173110130Sjake result = assignment(op, noeval); 174110130Sjake if (last_token != ARITH_RPAREN) 175110130Sjake yyerror("expecting ')'"); 176110130Sjake last_token = yylex(); 177110130Sjake return result; 178110130Sjake case ARITH_NUM: 179110130Sjake last_token = op; 180110130Sjake return val->val; 181110130Sjake case ARITH_VAR: 182110130Sjake last_token = op; 183110130Sjake return noeval ? val->val : arith_lookupvarint(val->name); 184110130Sjake case ARITH_ADD: 185110130Sjake token = op; 186110130Sjake *val = yylval; 187110130Sjake op = yylex(); 188110130Sjake goto again; 189110130Sjake case ARITH_SUB: 190110130Sjake *val = yylval; 191113538Sjake return -primary(op, val, yylex(), noeval); 192113538Sjake case ARITH_NOT: 193110130Sjake *val = yylval; 194110130Sjake return !primary(op, val, yylex(), noeval); 195110130Sjake case ARITH_BNOT: 196110130Sjake *val = yylval; 197110130Sjake return ~primary(op, val, yylex(), noeval); 198110130Sjake default: 199110130Sjake yyerror("expecting primary"); 200110130Sjake } 201110130Sjake} 202110130Sjake 203110130Sjakestatic arith_t binop2(arith_t a, int op, int precedence, int noeval) 204110130Sjake{ 205110130Sjake for (;;) { 206110130Sjake union yystype val; 207110130Sjake arith_t b; 208110130Sjake int op2; 209110130Sjake int token; 210110130Sjake 211110130Sjake token = yylex(); 212110130Sjake val = yylval; 213110130Sjake 214110130Sjake b = primary(token, &val, yylex(), noeval); 215110130Sjake 216110130Sjake op2 = last_token; 217110130Sjake if (op2 >= ARITH_BINOP_MIN && op2 < ARITH_BINOP_MAX && 218110130Sjake higher_prec(op2, op)) { 219110130Sjake b = binop2(b, op2, arith_prec(op), noeval); 220113538Sjake op2 = last_token; 221113538Sjake } 222113538Sjake 223113538Sjake a = noeval ? b : do_binop(op, a, b); 224113538Sjake 225113538Sjake if (op2 < ARITH_BINOP_MIN || op2 >= ARITH_BINOP_MAX || 226110130Sjake arith_prec(op2) >= precedence) 227110130Sjake return a; 228110130Sjake 229110130Sjake op = op2; 230110130Sjake } 231110130Sjake} 232110130Sjake 233110130Sjakestatic arith_t binop(int token, union yystype *val, int op, int noeval) 234110130Sjake{ 235110130Sjake arith_t a = primary(token, val, op, noeval); 236110130Sjake 237110130Sjake op = last_token; 238110130Sjake if (op < ARITH_BINOP_MIN || op >= ARITH_BINOP_MAX) 239110130Sjake return a; 240110130Sjake 241110130Sjake return binop2(a, op, ARITH_MAX_PREC, noeval); 242110130Sjake} 243110130Sjake 244110130Sjakestatic arith_t and(int token, union yystype *val, int op, int noeval) 245110130Sjake{ 246110130Sjake arith_t a = binop(token, val, op, noeval); 247110130Sjake arith_t b; 248110130Sjake 249110130Sjake op = last_token; 250110130Sjake if (op != ARITH_AND) 251110130Sjake return a; 252110130Sjake 253110130Sjake token = yylex(); 254110130Sjake *val = yylval; 255110130Sjake 256110130Sjake b = and(token, val, yylex(), noeval | !a); 257110130Sjake 258110130Sjake return a && b; 259113538Sjake} 260113538Sjake 261113538Sjakestatic arith_t or(int token, union yystype *val, int op, int noeval) 262113538Sjake{ 263113538Sjake arith_t a = and(token, val, op, noeval); 264113538Sjake arith_t b; 265110130Sjake 266113538Sjake op = last_token; 267113538Sjake if (op != ARITH_OR) 268113538Sjake return a; 269113538Sjake 270113538Sjake token = yylex(); 271113538Sjake *val = yylval; 272113538Sjake 273113538Sjake b = or(token, val, yylex(), noeval | !!a); 274113538Sjake 275113538Sjake return a || b; 276113538Sjake} 277113538Sjake 278113538Sjakestatic arith_t cond(int token, union yystype *val, int op, int noeval) 279113538Sjake{ 280113538Sjake arith_t a = or(token, val, op, noeval); 281113538Sjake arith_t b; 282113538Sjake arith_t c; 283113538Sjake 284113538Sjake if (last_token != ARITH_QMARK) 285113538Sjake return a; 286110130Sjake 287113538Sjake b = assignment(yylex(), noeval | !a); 288113538Sjake 289113538Sjake if (last_token != ARITH_COLON) 290113538Sjake yyerror("expecting ':'"); 291113538Sjake 292113538Sjake token = yylex(); 293113538Sjake *val = yylval; 294113538Sjake 295113538Sjake c = cond(token, val, yylex(), noeval | !!a); 296113538Sjake 297113538Sjake return a ? b : c; 298113538Sjake} 299113538Sjake 300113538Sjakestatic arith_t assignment(int var, int noeval) 301113538Sjake{ 302113538Sjake union yystype val = yylval; 303113538Sjake int op = yylex(); 304113538Sjake arith_t result; 305113538Sjake char sresult[DIGITS(result) + 1]; 306113538Sjake 307113538Sjake if (var != ARITH_VAR) 308113538Sjake return cond(var, &val, op, noeval); 309113538Sjake 310113538Sjake if (op != ARITH_ASS && (op < ARITH_ASS_MIN || op >= ARITH_ASS_MAX)) 311113538Sjake return cond(var, &val, op, noeval); 312110130Sjake 313110130Sjake result = assignment(yylex(), noeval); 314113538Sjake if (noeval) 315110130Sjake return result; 316110130Sjake 317110130Sjake if (op != ARITH_ASS) 318110130Sjake result = do_binop(op - 11, arith_lookupvarint(val.name), result); 319110130Sjake snprintf(sresult, sizeof(sresult), ARITH_FORMAT_STR, result); 320110130Sjake setvar(val.name, sresult, 0); 321110130Sjake return result; 322110130Sjake} 323110130Sjake 324110130Sjakearith_t arith(const char *s) 325110130Sjake{ 326110130Sjake struct stackmark smark; 327110130Sjake arith_t result; 328113538Sjake 329110130Sjake setstackmark(&smark); 330110130Sjake 331110130Sjake arith_buf = arith_startbuf = s; 332110130Sjake 333110130Sjake result = assignment(yylex(), 0); 334110130Sjake 335110130Sjake if (last_token) 336110130Sjake yyerror("expecting EOF"); 337110130Sjake 338110130Sjake popstackmark(&smark); 339110130Sjake 340110130Sjake return result; 341110130Sjake} 342110130Sjake 343110130Sjake/* 344110130Sjake * The exp(1) builtin. 345110130Sjake */ 346110130Sjakeint 347110130Sjakeletcmd(int argc, char **argv) 348110130Sjake{ 349110130Sjake const char *p; 350110130Sjake char *concat; 351110130Sjake char **ap; 352110130Sjake arith_t i; 353110130Sjake 354110130Sjake if (argc > 1) { 355110130Sjake p = argv[1]; 356110130Sjake if (argc > 2) { 357110130Sjake /* 358110130Sjake * Concatenate arguments. 359110130Sjake */ 360110130Sjake STARTSTACKSTR(concat); 361110130Sjake ap = argv + 2; 362110130Sjake for (;;) { 363110130Sjake while (*p) 364110130Sjake STPUTC(*p++, concat); 365110130Sjake if ((p = *ap++) == NULL) 366110130Sjake break; 367110130Sjake STPUTC(' ', concat); 368110130Sjake } 369110130Sjake STPUTC('\0', concat); 370110130Sjake p = grabstackstr(concat); 371110130Sjake } 372110130Sjake } else 373110130Sjake p = ""; 374110130Sjake 375110130Sjake i = arith(p); 376110130Sjake 377110130Sjake out1fmt(ARITH_FORMAT_STR "\n", i); 378110130Sjake return !i; 379110130Sjake} 380110130Sjake 381110130Sjake