arith_yacc.c revision 227369
1168404Spjd/*- 2168404Spjd * Copyright (c) 1993 3168404Spjd * The Regents of the University of California. All rights reserved. 4168404Spjd * Copyright (c) 2007 5168404Spjd * Herbert Xu <herbert@gondor.apana.org.au>. All rights reserved. 6168404Spjd * 7168404Spjd * This code is derived from software contributed to Berkeley by 8168404Spjd * Kenneth Almquist. 9168404Spjd * 10168404Spjd * Redistribution and use in source and binary forms, with or without 11168404Spjd * modification, are permitted provided that the following conditions 12168404Spjd * are met: 13168404Spjd * 1. Redistributions of source code must retain the above copyright 14168404Spjd * notice, this list of conditions and the following disclaimer. 15168404Spjd * 2. Redistributions in binary form must reproduce the above copyright 16168404Spjd * notice, this list of conditions and the following disclaimer in the 17168404Spjd * documentation and/or other materials provided with the distribution. 18168404Spjd * 3. Neither the name of the University nor the names of its contributors 19168404Spjd * may be used to endorse or promote products derived from this software 20168404Spjd * without specific prior written permission. 21168404Spjd * 22219089Spjd * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 23228103Smm * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24239620Smm * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25168404Spjd * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 26168404Spjd * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27168404Spjd * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28168404Spjd * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29168404Spjd * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30168404Spjd * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31168404Spjd * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32168404Spjd * SUCH DAMAGE. 33168404Spjd */ 34168404Spjd 35168404Spjd#include <sys/cdefs.h> 36168404Spjd__FBSDID("$FreeBSD: head/bin/sh/arith_yacc.c 227369 2011-11-08 23:54:39Z jilles $"); 37168404Spjd 38168404Spjd#include <limits.h> 39168404Spjd#include <errno.h> 40168404Spjd#include <inttypes.h> 41168404Spjd#include <stdlib.h> 42168404Spjd#include <stdio.h> 43219089Spjd#include "arith.h" 44168404Spjd#include "arith_yacc.h" 45168404Spjd#include "expand.h" 46168404Spjd#include "shell.h" 47168404Spjd#include "error.h" 48219089Spjd#include "memalloc.h" 49168404Spjd#include "output.h" 50168404Spjd#include "options.h" 51168404Spjd#include "var.h" 52168404Spjd 53168404Spjd#if ARITH_BOR + 11 != ARITH_BORASS || ARITH_ASS + 11 != ARITH_EQ 54219089Spjd#error Arithmetic tokens are out of order. 55168404Spjd#endif 56168404Spjd 57168404Spjdstatic const char *arith_startbuf; 58168404Spjd 59168404Spjdconst char *arith_buf; 60168404Spjdunion yystype yylval; 61168404Spjd 62168404Spjdstatic int last_token; 63168404Spjd 64168404Spjd#define ARITH_PRECEDENCE(op, prec) [op - ARITH_BINOP_MIN] = prec 65168404Spjd 66168404Spjdstatic const char prec[ARITH_BINOP_MAX - ARITH_BINOP_MIN] = { 67168404Spjd ARITH_PRECEDENCE(ARITH_MUL, 0), 68168404Spjd ARITH_PRECEDENCE(ARITH_DIV, 0), 69168404Spjd ARITH_PRECEDENCE(ARITH_REM, 0), 70168404Spjd ARITH_PRECEDENCE(ARITH_ADD, 1), 71168404Spjd ARITH_PRECEDENCE(ARITH_SUB, 1), 72168404Spjd ARITH_PRECEDENCE(ARITH_LSHIFT, 2), 73168404Spjd ARITH_PRECEDENCE(ARITH_RSHIFT, 2), 74168404Spjd ARITH_PRECEDENCE(ARITH_LT, 3), 75168404Spjd ARITH_PRECEDENCE(ARITH_LE, 3), 76168404Spjd ARITH_PRECEDENCE(ARITH_GT, 3), 77168404Spjd ARITH_PRECEDENCE(ARITH_GE, 3), 78168404Spjd ARITH_PRECEDENCE(ARITH_EQ, 4), 79168404Spjd ARITH_PRECEDENCE(ARITH_NE, 4), 80168404Spjd ARITH_PRECEDENCE(ARITH_BAND, 5), 81168404Spjd ARITH_PRECEDENCE(ARITH_BXOR, 6), 82168404Spjd ARITH_PRECEDENCE(ARITH_BOR, 7), 83168404Spjd}; 84168404Spjd 85168404Spjd#define ARITH_MAX_PREC 8 86168404Spjd 87168404Spjdstatic __dead2 void yyerror(const char *s) 88168404Spjd{ 89168404Spjd error("arithmetic expression: %s: \"%s\"", s, arith_startbuf); 90168404Spjd /* NOTREACHED */ 91168404Spjd} 92168404Spjd 93168404Spjdstatic arith_t arith_lookupvarint(char *varname) 94168404Spjd{ 95168404Spjd const char *str; 96168404Spjd char *p; 97168404Spjd arith_t result; 98168404Spjd 99168404Spjd str = lookupvar(varname); 100168404Spjd if (uflag && str == NULL) 101168404Spjd yyerror("variable not set"); 102168404Spjd if (str == NULL || *str == '\0') 103168404Spjd str = "0"; 104168404Spjd errno = 0; 105168404Spjd result = strtoarith_t(str, &p, 0); 106168404Spjd if (errno != 0 || *p != '\0') 107168404Spjd yyerror("variable conversion error"); 108168404Spjd return result; 109168404Spjd} 110168404Spjd 111168404Spjdstatic inline int arith_prec(int op) 112168404Spjd{ 113168404Spjd return prec[op - ARITH_BINOP_MIN]; 114168404Spjd} 115168404Spjd 116168404Spjdstatic inline int higher_prec(int op1, int op2) 117168404Spjd{ 118219089Spjd return arith_prec(op1) < arith_prec(op2); 119168404Spjd} 120168404Spjd 121168404Spjdstatic arith_t do_binop(int op, arith_t a, arith_t b) 122168404Spjd{ 123168404Spjd 124168404Spjd switch (op) { 125168404Spjd default: 126168404Spjd case ARITH_REM: 127168404Spjd case ARITH_DIV: 128168404Spjd if (!b) 129168404Spjd yyerror("division by zero"); 130168404Spjd if (a == ARITH_MIN && b == -1) 131168404Spjd yyerror("divide error"); 132168404Spjd return op == ARITH_REM ? a % b : a / b; 133168404Spjd case ARITH_MUL: 134168404Spjd return (uintmax_t)a * (uintmax_t)b; 135168404Spjd case ARITH_ADD: 136168404Spjd return (uintmax_t)a + (uintmax_t)b; 137168404Spjd case ARITH_SUB: 138168404Spjd return (uintmax_t)a - (uintmax_t)b; 139168404Spjd case ARITH_LSHIFT: 140168404Spjd return a << b; 141168404Spjd case ARITH_RSHIFT: 142168404Spjd return a >> b; 143168404Spjd case ARITH_LT: 144168404Spjd return a < b; 145168404Spjd case ARITH_LE: 146168404Spjd return a <= b; 147168404Spjd case ARITH_GT: 148168404Spjd return a > b; 149168404Spjd case ARITH_GE: 150168404Spjd return a >= b; 151168404Spjd case ARITH_EQ: 152168404Spjd return a == b; 153168404Spjd case ARITH_NE: 154168404Spjd return a != b; 155168404Spjd case ARITH_BAND: 156168404Spjd return a & b; 157168404Spjd case ARITH_BXOR: 158168404Spjd return a ^ b; 159168404Spjd case ARITH_BOR: 160168404Spjd return a | b; 161168404Spjd } 162168404Spjd} 163168404Spjd 164168404Spjdstatic arith_t assignment(int var, int noeval); 165168404Spjd 166168404Spjdstatic arith_t primary(int token, union yystype *val, int op, int noeval) 167168404Spjd{ 168168404Spjd arith_t result; 169168404Spjd 170168404Spjdagain: 171168404Spjd switch (token) { 172168404Spjd case ARITH_LPAREN: 173168404Spjd result = assignment(op, noeval); 174168404Spjd if (last_token != ARITH_RPAREN) 175168404Spjd yyerror("expecting ')'"); 176168404Spjd last_token = yylex(); 177168404Spjd return result; 178168404Spjd case ARITH_NUM: 179168404Spjd last_token = op; 180168404Spjd return val->val; 181168404Spjd case ARITH_VAR: 182168404Spjd last_token = op; 183168404Spjd return noeval ? val->val : arith_lookupvarint(val->name); 184168404Spjd case ARITH_ADD: 185168404Spjd token = op; 186168404Spjd *val = yylval; 187168404Spjd op = yylex(); 188168404Spjd goto again; 189168404Spjd case ARITH_SUB: 190168404Spjd *val = yylval; 191168404Spjd return -primary(op, val, yylex(), noeval); 192168404Spjd case ARITH_NOT: 193168404Spjd *val = yylval; 194168404Spjd return !primary(op, val, yylex(), noeval); 195168404Spjd case ARITH_BNOT: 196168404Spjd *val = yylval; 197168404Spjd return ~primary(op, val, yylex(), noeval); 198168404Spjd default: 199168404Spjd yyerror("expecting primary"); 200168404Spjd } 201168404Spjd} 202168404Spjd 203168404Spjdstatic arith_t binop2(arith_t a, int op, int precedence, int noeval) 204168404Spjd{ 205168404Spjd for (;;) { 206168404Spjd union yystype val; 207168404Spjd arith_t b; 208168404Spjd int op2; 209168404Spjd int token; 210168404Spjd 211168404Spjd token = yylex(); 212168404Spjd val = yylval; 213168404Spjd 214168404Spjd b = primary(token, &val, yylex(), noeval); 215168404Spjd 216168404Spjd op2 = last_token; 217168404Spjd if (op2 >= ARITH_BINOP_MIN && op2 < ARITH_BINOP_MAX && 218168404Spjd higher_prec(op2, op)) { 219185029Spjd b = binop2(b, op2, arith_prec(op), noeval); 220185029Spjd op2 = last_token; 221185029Spjd } 222168404Spjd 223168404Spjd a = noeval ? b : do_binop(op, a, b); 224185029Spjd 225185029Spjd if (op2 < ARITH_BINOP_MIN || op2 >= ARITH_BINOP_MAX || 226168404Spjd arith_prec(op2) >= precedence) 227168404Spjd return a; 228168926Spjd 229168404Spjd op = op2; 230168404Spjd } 231168404Spjd} 232168404Spjd 233168404Spjdstatic arith_t binop(int token, union yystype *val, int op, int noeval) 234168404Spjd{ 235168404Spjd arith_t a = primary(token, val, op, noeval); 236168404Spjd 237168404Spjd op = last_token; 238168404Spjd if (op < ARITH_BINOP_MIN || op >= ARITH_BINOP_MAX) 239168404Spjd return a; 240168404Spjd 241168404Spjd return binop2(a, op, ARITH_MAX_PREC, noeval); 242168404Spjd} 243168404Spjd 244168404Spjdstatic arith_t and(int token, union yystype *val, int op, int noeval) 245168404Spjd{ 246168404Spjd arith_t a = binop(token, val, op, noeval); 247168404Spjd arith_t b; 248168404Spjd 249168404Spjd op = last_token; 250168404Spjd if (op != ARITH_AND) 251168404Spjd return a; 252168404Spjd 253168404Spjd token = yylex(); 254168404Spjd *val = yylval; 255168404Spjd 256168404Spjd b = and(token, val, yylex(), noeval | !a); 257168404Spjd 258168404Spjd return a && b; 259168404Spjd} 260168404Spjd 261168404Spjdstatic arith_t or(int token, union yystype *val, int op, int noeval) 262168404Spjd{ 263168404Spjd arith_t a = and(token, val, op, noeval); 264168404Spjd arith_t b; 265168404Spjd 266168404Spjd op = last_token; 267168404Spjd if (op != ARITH_OR) 268168404Spjd return a; 269168404Spjd 270168404Spjd token = yylex(); 271168404Spjd *val = yylval; 272168404Spjd 273168404Spjd b = or(token, val, yylex(), noeval | !!a); 274168404Spjd 275168404Spjd return a || b; 276168404Spjd} 277168404Spjd 278168404Spjdstatic arith_t cond(int token, union yystype *val, int op, int noeval) 279168404Spjd{ 280168404Spjd arith_t a = or(token, val, op, noeval); 281168404Spjd arith_t b; 282168404Spjd arith_t c; 283168404Spjd 284168404Spjd if (last_token != ARITH_QMARK) 285168404Spjd return a; 286168404Spjd 287168404Spjd b = assignment(yylex(), noeval | !a); 288168404Spjd 289168404Spjd if (last_token != ARITH_COLON) 290168404Spjd yyerror("expecting ':'"); 291168404Spjd 292168404Spjd token = yylex(); 293168404Spjd *val = yylval; 294168404Spjd 295168404Spjd c = cond(token, val, yylex(), noeval | !!a); 296168404Spjd 297168404Spjd return a ? b : c; 298168404Spjd} 299168404Spjd 300168404Spjdstatic arith_t assignment(int var, int noeval) 301168404Spjd{ 302168404Spjd union yystype val = yylval; 303168404Spjd int op = yylex(); 304168404Spjd arith_t result; 305168404Spjd char sresult[DIGITS(result) + 1]; 306168404Spjd 307168404Spjd if (var != ARITH_VAR) 308168404Spjd return cond(var, &val, op, noeval); 309168404Spjd 310168404Spjd if (op != ARITH_ASS && (op < ARITH_ASS_MIN || op >= ARITH_ASS_MAX)) 311168404Spjd return cond(var, &val, op, noeval); 312168404Spjd 313168404Spjd result = assignment(yylex(), noeval); 314168404Spjd if (noeval) 315168404Spjd return result; 316168404Spjd 317168404Spjd if (op != ARITH_ASS) 318168404Spjd result = do_binop(op - 11, arith_lookupvarint(val.name), result); 319168404Spjd snprintf(sresult, sizeof(sresult), ARITH_FORMAT_STR, result); 320168404Spjd setvar(val.name, sresult, 0); 321168404Spjd return result; 322168404Spjd} 323168404Spjd 324168404Spjdarith_t arith(const char *s) 325168404Spjd{ 326168404Spjd struct stackmark smark; 327168404Spjd arith_t result; 328168404Spjd 329168404Spjd setstackmark(&smark); 330168404Spjd 331168404Spjd arith_buf = arith_startbuf = s; 332168404Spjd 333168404Spjd result = assignment(yylex(), 0); 334168404Spjd 335168404Spjd if (last_token) 336168404Spjd yyerror("expecting EOF"); 337168404Spjd 338168404Spjd popstackmark(&smark); 339168404Spjd 340168404Spjd return result; 341168404Spjd} 342168404Spjd 343168404Spjd/* 344168404Spjd * The exp(1) builtin. 345168404Spjd */ 346168404Spjdint 347168404Spjdletcmd(int argc, char **argv) 348168404Spjd{ 349168404Spjd const char *p; 350168404Spjd char *concat; 351168404Spjd char **ap; 352168404Spjd arith_t i; 353168404Spjd 354168404Spjd if (argc > 1) { 355168404Spjd p = argv[1]; 356168404Spjd if (argc > 2) { 357168404Spjd /* 358168404Spjd * Concatenate arguments. 359168404Spjd */ 360168404Spjd STARTSTACKSTR(concat); 361168404Spjd ap = argv + 2; 362168404Spjd for (;;) { 363168404Spjd while (*p) 364168404Spjd STPUTC(*p++, concat); 365168404Spjd if ((p = *ap++) == NULL) 366168404Spjd break; 367168404Spjd STPUTC(' ', concat); 368168404Spjd } 369185029Spjd STPUTC('\0', concat); 370185029Spjd p = grabstackstr(concat); 371185029Spjd } 372185029Spjd } else 373185029Spjd p = ""; 374185029Spjd 375185029Spjd i = arith(p); 376185029Spjd 377185029Spjd out1fmt(ARITH_FORMAT_STR "\n", i); 378185029Spjd return !i; 379185029Spjd} 380185029Spjd 381185029Spjd