arith_yacc.c revision 218466
1218466Sjilles/*- 2218466Sjilles * Copyright (c) 1993 3218466Sjilles * The Regents of the University of California. All rights reserved. 4218466Sjilles * Copyright (c) 2007 5218466Sjilles * Herbert Xu <herbert@gondor.apana.org.au>. All rights reserved. 6218466Sjilles * 7218466Sjilles * This code is derived from software contributed to Berkeley by 8218466Sjilles * Kenneth Almquist. 9218466Sjilles * 10218466Sjilles * Redistribution and use in source and binary forms, with or without 11218466Sjilles * modification, are permitted provided that the following conditions 12218466Sjilles * are met: 13218466Sjilles * 1. Redistributions of source code must retain the above copyright 14218466Sjilles * notice, this list of conditions and the following disclaimer. 15218466Sjilles * 2. Redistributions in binary form must reproduce the above copyright 16218466Sjilles * notice, this list of conditions and the following disclaimer in the 17218466Sjilles * documentation and/or other materials provided with the distribution. 18218466Sjilles * 3. Neither the name of the University nor the names of its contributors 19218466Sjilles * may be used to endorse or promote products derived from this software 20218466Sjilles * without specific prior written permission. 21218466Sjilles * 22218466Sjilles * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 23218466Sjilles * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24218466Sjilles * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25218466Sjilles * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 26218466Sjilles * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27218466Sjilles * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28218466Sjilles * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29218466Sjilles * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30218466Sjilles * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31218466Sjilles * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32218466Sjilles * SUCH DAMAGE. 33218466Sjilles */ 34218466Sjilles 35218466Sjilles#include <sys/cdefs.h> 36218466Sjilles__FBSDID("$FreeBSD: head/bin/sh/arith_yacc.c 218466 2011-02-08 23:18:06Z jilles $"); 37218466Sjilles 38218466Sjilles#include <sys/limits.h> 39218466Sjilles#include <errno.h> 40218466Sjilles#include <inttypes.h> 41218466Sjilles#include <stdlib.h> 42218466Sjilles#include <stdio.h> 43218466Sjilles#include "arith.h" 44218466Sjilles#include "arith_yacc.h" 45218466Sjilles#include "expand.h" 46218466Sjilles#include "shell.h" 47218466Sjilles#include "error.h" 48218466Sjilles#include "memalloc.h" 49218466Sjilles#include "output.h" 50218466Sjilles#include "options.h" 51218466Sjilles#include "var.h" 52218466Sjilles 53218466Sjilles#if ARITH_BOR + 11 != ARITH_BORASS || ARITH_ASS + 11 != ARITH_EQ 54218466Sjilles#error Arithmetic tokens are out of order. 55218466Sjilles#endif 56218466Sjilles 57218466Sjillesstatic const char *arith_startbuf; 58218466Sjilles 59218466Sjillesconst char *arith_buf; 60218466Sjillesunion yystype yylval; 61218466Sjilles 62218466Sjillesstatic int last_token; 63218466Sjilles 64218466Sjilles#define ARITH_PRECEDENCE(op, prec) [op - ARITH_BINOP_MIN] = prec 65218466Sjilles 66218466Sjillesstatic const char prec[ARITH_BINOP_MAX - ARITH_BINOP_MIN] = { 67218466Sjilles ARITH_PRECEDENCE(ARITH_MUL, 0), 68218466Sjilles ARITH_PRECEDENCE(ARITH_DIV, 0), 69218466Sjilles ARITH_PRECEDENCE(ARITH_REM, 0), 70218466Sjilles ARITH_PRECEDENCE(ARITH_ADD, 1), 71218466Sjilles ARITH_PRECEDENCE(ARITH_SUB, 1), 72218466Sjilles ARITH_PRECEDENCE(ARITH_LSHIFT, 2), 73218466Sjilles ARITH_PRECEDENCE(ARITH_RSHIFT, 2), 74218466Sjilles ARITH_PRECEDENCE(ARITH_LT, 3), 75218466Sjilles ARITH_PRECEDENCE(ARITH_LE, 3), 76218466Sjilles ARITH_PRECEDENCE(ARITH_GT, 3), 77218466Sjilles ARITH_PRECEDENCE(ARITH_GE, 3), 78218466Sjilles ARITH_PRECEDENCE(ARITH_EQ, 4), 79218466Sjilles ARITH_PRECEDENCE(ARITH_NE, 4), 80218466Sjilles ARITH_PRECEDENCE(ARITH_BAND, 5), 81218466Sjilles ARITH_PRECEDENCE(ARITH_BXOR, 6), 82218466Sjilles ARITH_PRECEDENCE(ARITH_BOR, 7), 83218466Sjilles}; 84218466Sjilles 85218466Sjilles#define ARITH_MAX_PREC 8 86218466Sjilles 87218466Sjillesstatic __dead2 void yyerror(const char *s) 88218466Sjilles{ 89218466Sjilles error("arithmetic expression: %s: \"%s\"", s, arith_startbuf); 90218466Sjilles /* NOTREACHED */ 91218466Sjilles} 92218466Sjilles 93218466Sjillesstatic arith_t arith_lookupvarint(char *varname) 94218466Sjilles{ 95218466Sjilles const char *str; 96218466Sjilles char *p; 97218466Sjilles arith_t result; 98218466Sjilles 99218466Sjilles str = lookupvar(varname); 100218466Sjilles if (str == NULL || *str == '\0') 101218466Sjilles str = "0"; 102218466Sjilles errno = 0; 103218466Sjilles result = strtoarith_t(str, &p, 0); 104218466Sjilles if (errno != 0 || *p != '\0') 105218466Sjilles yyerror("variable conversion error"); 106218466Sjilles return result; 107218466Sjilles} 108218466Sjilles 109218466Sjillesstatic inline int arith_prec(int op) 110218466Sjilles{ 111218466Sjilles return prec[op - ARITH_BINOP_MIN]; 112218466Sjilles} 113218466Sjilles 114218466Sjillesstatic inline int higher_prec(int op1, int op2) 115218466Sjilles{ 116218466Sjilles return arith_prec(op1) < arith_prec(op2); 117218466Sjilles} 118218466Sjilles 119218466Sjillesstatic arith_t do_binop(int op, arith_t a, arith_t b) 120218466Sjilles{ 121218466Sjilles 122218466Sjilles switch (op) { 123218466Sjilles default: 124218466Sjilles case ARITH_REM: 125218466Sjilles case ARITH_DIV: 126218466Sjilles if (!b) 127218466Sjilles yyerror("division by zero"); 128218466Sjilles return op == ARITH_REM ? a % b : a / b; 129218466Sjilles case ARITH_MUL: 130218466Sjilles return a * b; 131218466Sjilles case ARITH_ADD: 132218466Sjilles return a + b; 133218466Sjilles case ARITH_SUB: 134218466Sjilles return a - b; 135218466Sjilles case ARITH_LSHIFT: 136218466Sjilles return a << b; 137218466Sjilles case ARITH_RSHIFT: 138218466Sjilles return a >> b; 139218466Sjilles case ARITH_LT: 140218466Sjilles return a < b; 141218466Sjilles case ARITH_LE: 142218466Sjilles return a <= b; 143218466Sjilles case ARITH_GT: 144218466Sjilles return a > b; 145218466Sjilles case ARITH_GE: 146218466Sjilles return a >= b; 147218466Sjilles case ARITH_EQ: 148218466Sjilles return a == b; 149218466Sjilles case ARITH_NE: 150218466Sjilles return a != b; 151218466Sjilles case ARITH_BAND: 152218466Sjilles return a & b; 153218466Sjilles case ARITH_BXOR: 154218466Sjilles return a ^ b; 155218466Sjilles case ARITH_BOR: 156218466Sjilles return a | b; 157218466Sjilles } 158218466Sjilles} 159218466Sjilles 160218466Sjillesstatic arith_t assignment(int var, int noeval); 161218466Sjilles 162218466Sjillesstatic arith_t primary(int token, union yystype *val, int op, int noeval) 163218466Sjilles{ 164218466Sjilles arith_t result; 165218466Sjilles 166218466Sjillesagain: 167218466Sjilles switch (token) { 168218466Sjilles case ARITH_LPAREN: 169218466Sjilles result = assignment(op, noeval); 170218466Sjilles if (last_token != ARITH_RPAREN) 171218466Sjilles yyerror("expecting ')'"); 172218466Sjilles last_token = yylex(); 173218466Sjilles return result; 174218466Sjilles case ARITH_NUM: 175218466Sjilles last_token = op; 176218466Sjilles return val->val; 177218466Sjilles case ARITH_VAR: 178218466Sjilles last_token = op; 179218466Sjilles return noeval ? val->val : arith_lookupvarint(val->name); 180218466Sjilles case ARITH_ADD: 181218466Sjilles token = op; 182218466Sjilles *val = yylval; 183218466Sjilles op = yylex(); 184218466Sjilles goto again; 185218466Sjilles case ARITH_SUB: 186218466Sjilles *val = yylval; 187218466Sjilles return -primary(op, val, yylex(), noeval); 188218466Sjilles case ARITH_NOT: 189218466Sjilles *val = yylval; 190218466Sjilles return !primary(op, val, yylex(), noeval); 191218466Sjilles case ARITH_BNOT: 192218466Sjilles *val = yylval; 193218466Sjilles return ~primary(op, val, yylex(), noeval); 194218466Sjilles default: 195218466Sjilles yyerror("expecting primary"); 196218466Sjilles } 197218466Sjilles} 198218466Sjilles 199218466Sjillesstatic arith_t binop2(arith_t a, int op, int prec, int noeval) 200218466Sjilles{ 201218466Sjilles for (;;) { 202218466Sjilles union yystype val; 203218466Sjilles arith_t b; 204218466Sjilles int op2; 205218466Sjilles int token; 206218466Sjilles 207218466Sjilles token = yylex(); 208218466Sjilles val = yylval; 209218466Sjilles 210218466Sjilles b = primary(token, &val, yylex(), noeval); 211218466Sjilles 212218466Sjilles op2 = last_token; 213218466Sjilles if (op2 >= ARITH_BINOP_MIN && op2 < ARITH_BINOP_MAX && 214218466Sjilles higher_prec(op2, op)) { 215218466Sjilles b = binop2(b, op2, arith_prec(op), noeval); 216218466Sjilles op2 = last_token; 217218466Sjilles } 218218466Sjilles 219218466Sjilles a = noeval ? b : do_binop(op, a, b); 220218466Sjilles 221218466Sjilles if (op2 < ARITH_BINOP_MIN || op2 >= ARITH_BINOP_MAX || 222218466Sjilles arith_prec(op2) >= prec) 223218466Sjilles return a; 224218466Sjilles 225218466Sjilles op = op2; 226218466Sjilles } 227218466Sjilles} 228218466Sjilles 229218466Sjillesstatic arith_t binop(int token, union yystype *val, int op, int noeval) 230218466Sjilles{ 231218466Sjilles arith_t a = primary(token, val, op, noeval); 232218466Sjilles 233218466Sjilles op = last_token; 234218466Sjilles if (op < ARITH_BINOP_MIN || op >= ARITH_BINOP_MAX) 235218466Sjilles return a; 236218466Sjilles 237218466Sjilles return binop2(a, op, ARITH_MAX_PREC, noeval); 238218466Sjilles} 239218466Sjilles 240218466Sjillesstatic arith_t and(int token, union yystype *val, int op, int noeval) 241218466Sjilles{ 242218466Sjilles arith_t a = binop(token, val, op, noeval); 243218466Sjilles arith_t b; 244218466Sjilles 245218466Sjilles op = last_token; 246218466Sjilles if (op != ARITH_AND) 247218466Sjilles return a; 248218466Sjilles 249218466Sjilles token = yylex(); 250218466Sjilles *val = yylval; 251218466Sjilles 252218466Sjilles b = and(token, val, yylex(), noeval | !a); 253218466Sjilles 254218466Sjilles return a && b; 255218466Sjilles} 256218466Sjilles 257218466Sjillesstatic arith_t or(int token, union yystype *val, int op, int noeval) 258218466Sjilles{ 259218466Sjilles arith_t a = and(token, val, op, noeval); 260218466Sjilles arith_t b; 261218466Sjilles 262218466Sjilles op = last_token; 263218466Sjilles if (op != ARITH_OR) 264218466Sjilles return a; 265218466Sjilles 266218466Sjilles token = yylex(); 267218466Sjilles *val = yylval; 268218466Sjilles 269218466Sjilles b = or(token, val, yylex(), noeval | !!a); 270218466Sjilles 271218466Sjilles return a || b; 272218466Sjilles} 273218466Sjilles 274218466Sjillesstatic arith_t cond(int token, union yystype *val, int op, int noeval) 275218466Sjilles{ 276218466Sjilles arith_t a = or(token, val, op, noeval); 277218466Sjilles arith_t b; 278218466Sjilles arith_t c; 279218466Sjilles 280218466Sjilles if (last_token != ARITH_QMARK) 281218466Sjilles return a; 282218466Sjilles 283218466Sjilles b = assignment(yylex(), noeval | !a); 284218466Sjilles 285218466Sjilles if (last_token != ARITH_COLON) 286218466Sjilles yyerror("expecting ':'"); 287218466Sjilles 288218466Sjilles token = yylex(); 289218466Sjilles *val = yylval; 290218466Sjilles 291218466Sjilles c = cond(token, val, yylex(), noeval | !!a); 292218466Sjilles 293218466Sjilles return a ? b : c; 294218466Sjilles} 295218466Sjilles 296218466Sjillesstatic arith_t assignment(int var, int noeval) 297218466Sjilles{ 298218466Sjilles union yystype val = yylval; 299218466Sjilles int op = yylex(); 300218466Sjilles arith_t result; 301218466Sjilles char sresult[DIGITS(result) + 1]; 302218466Sjilles 303218466Sjilles if (var != ARITH_VAR) 304218466Sjilles return cond(var, &val, op, noeval); 305218466Sjilles 306218466Sjilles if (op != ARITH_ASS && (op < ARITH_ASS_MIN || op >= ARITH_ASS_MAX)) 307218466Sjilles return cond(var, &val, op, noeval); 308218466Sjilles 309218466Sjilles result = assignment(yylex(), noeval); 310218466Sjilles if (noeval) 311218466Sjilles return result; 312218466Sjilles 313218466Sjilles if (op != ARITH_ASS) 314218466Sjilles result = do_binop(op - 11, arith_lookupvarint(val.name), result); 315218466Sjilles snprintf(sresult, sizeof(sresult), ARITH_FORMAT_STR, result); 316218466Sjilles setvar(val.name, sresult, 0); 317218466Sjilles return result; 318218466Sjilles} 319218466Sjilles 320218466Sjillesarith_t arith(const char *s) 321218466Sjilles{ 322218466Sjilles struct stackmark smark; 323218466Sjilles arith_t result; 324218466Sjilles 325218466Sjilles setstackmark(&smark); 326218466Sjilles 327218466Sjilles arith_buf = arith_startbuf = s; 328218466Sjilles 329218466Sjilles result = assignment(yylex(), 0); 330218466Sjilles 331218466Sjilles if (last_token) 332218466Sjilles yyerror("expecting EOF"); 333218466Sjilles 334218466Sjilles popstackmark(&smark); 335218466Sjilles 336218466Sjilles return result; 337218466Sjilles} 338218466Sjilles 339218466Sjilles/* 340218466Sjilles * The exp(1) builtin. 341218466Sjilles */ 342218466Sjillesint 343218466Sjillesexpcmd(int argc, char **argv) 344218466Sjilles{ 345218466Sjilles const char *p; 346218466Sjilles char *concat; 347218466Sjilles char **ap; 348218466Sjilles arith_t i; 349218466Sjilles 350218466Sjilles if (argc > 1) { 351218466Sjilles p = argv[1]; 352218466Sjilles if (argc > 2) { 353218466Sjilles /* 354218466Sjilles * Concatenate arguments. 355218466Sjilles */ 356218466Sjilles STARTSTACKSTR(concat); 357218466Sjilles ap = argv + 2; 358218466Sjilles for (;;) { 359218466Sjilles while (*p) 360218466Sjilles STPUTC(*p++, concat); 361218466Sjilles if ((p = *ap++) == NULL) 362218466Sjilles break; 363218466Sjilles STPUTC(' ', concat); 364218466Sjilles } 365218466Sjilles STPUTC('\0', concat); 366218466Sjilles p = grabstackstr(concat); 367218466Sjilles } 368218466Sjilles } else 369218466Sjilles p = ""; 370218466Sjilles 371218466Sjilles i = arith(p); 372218466Sjilles 373218466Sjilles out1fmt(ARITH_FORMAT_STR "\n", i); 374218466Sjilles return !i; 375218466Sjilles} 376218466Sjilles 377