1/* vi: set sw=4 ts=4: */ 2/* 3 * Mini expr implementation for busybox 4 * 5 * based on GNU expr Mike Parker. 6 * Copyright (C) 86, 1991-1997, 1999 Free Software Foundation, Inc. 7 * 8 * Busybox modifications 9 * Copyright (c) 2000 Edward Betts <edward@debian.org>. 10 * Copyright (C) 2003-2005 Vladimir Oleynik <dzo@simtreas.ru> 11 * - reduced 464 bytes. 12 * - 64 math support 13 * 14 * Licensed under GPLv2 or later, see file LICENSE in this tarball for details. 15 */ 16 17/* This program evaluates expressions. Each token (operator, operand, 18 * parenthesis) of the expression must be a separate argument. The 19 * parser used is a reasonably general one, though any incarnation of 20 * it is language-specific. It is especially nice for expressions. 21 * 22 * No parse tree is needed; a new node is evaluated immediately. 23 * One function can handle multiple operators all of equal precedence, 24 * provided they all associate ((x op x) op x). */ 25 26/* no getopt needed */ 27 28#include "libbb.h" 29#include "xregex.h" 30 31#if ENABLE_EXPR_MATH_SUPPORT_64 32typedef int64_t arith_t; 33 34#define PF_REZ "ll" 35#define PF_REZ_TYPE (long long) 36#define STRTOL(s, e, b) strtoll(s, e, b) 37#else 38typedef long arith_t; 39 40#define PF_REZ "l" 41#define PF_REZ_TYPE (long) 42#define STRTOL(s, e, b) strtol(s, e, b) 43#endif 44 45/* TODO: use bb_strtol[l]? It's easier to check for errors... */ 46 47/* The kinds of value we can have. */ 48enum { 49 INTEGER, 50 STRING 51}; 52 53/* A value is.... */ 54struct valinfo { 55 smallint type; /* Which kind. */ 56 union { /* The value itself. */ 57 arith_t i; 58 char *s; 59 } u; 60}; 61typedef struct valinfo VALUE; 62 63/* The arguments given to the program, minus the program name. */ 64struct globals { 65 char **args; 66} FIX_ALIASING; 67#define G (*(struct globals*)&bb_common_bufsiz1) 68 69/* forward declarations */ 70static VALUE *eval(void); 71 72 73/* Return a VALUE for I. */ 74 75static VALUE *int_value(arith_t i) 76{ 77 VALUE *v; 78 79 v = xzalloc(sizeof(VALUE)); 80 if (INTEGER) /* otherwise xzaaloc did it already */ 81 v->type = INTEGER; 82 v->u.i = i; 83 return v; 84} 85 86/* Return a VALUE for S. */ 87 88static VALUE *str_value(const char *s) 89{ 90 VALUE *v; 91 92 v = xzalloc(sizeof(VALUE)); 93 if (STRING) /* otherwise xzaaloc did it already */ 94 v->type = STRING; 95 v->u.s = xstrdup(s); 96 return v; 97} 98 99/* Free VALUE V, including structure components. */ 100 101static void freev(VALUE *v) 102{ 103 if (v->type == STRING) 104 free(v->u.s); 105 free(v); 106} 107 108/* Return nonzero if V is a null-string or zero-number. */ 109 110static int null(VALUE *v) 111{ 112 if (v->type == INTEGER) 113 return v->u.i == 0; 114 /* STRING: */ 115 return v->u.s[0] == '\0' || LONE_CHAR(v->u.s, '0'); 116} 117 118/* Coerce V to a STRING value (can't fail). */ 119 120static void tostring(VALUE *v) 121{ 122 if (v->type == INTEGER) { 123 v->u.s = xasprintf("%" PF_REZ "d", PF_REZ_TYPE v->u.i); 124 v->type = STRING; 125 } 126} 127 128/* Coerce V to an INTEGER value. Return 1 on success, 0 on failure. */ 129 130static bool toarith(VALUE *v) 131{ 132 if (v->type == STRING) { 133 arith_t i; 134 char *e; 135 136 /* Don't interpret the empty string as an integer. */ 137 /* Currently does not worry about overflow or int/long differences. */ 138 i = STRTOL(v->u.s, &e, 10); 139 if ((v->u.s == e) || *e) 140 return 0; 141 free(v->u.s); 142 v->u.i = i; 143 v->type = INTEGER; 144 } 145 return 1; 146} 147 148/* Return str[0]+str[1] if the next token matches STR exactly. 149 STR must not be NULL. */ 150 151static int nextarg(const char *str) 152{ 153 if (*G.args == NULL || strcmp(*G.args, str) != 0) 154 return 0; 155 return (unsigned char)str[0] + (unsigned char)str[1]; 156} 157 158/* The comparison operator handling functions. */ 159 160static int cmp_common(VALUE *l, VALUE *r, int op) 161{ 162 arith_t ll, rr; 163 164 ll = l->u.i; 165 rr = r->u.i; 166 if (l->type == STRING || r->type == STRING) { 167 tostring(l); 168 tostring(r); 169 ll = strcmp(l->u.s, r->u.s); 170 rr = 0; 171 } 172 /* calculating ll - rr and checking the result is prone to overflows. 173 * We'll do it differently: */ 174 if (op == '<') 175 return ll < rr; 176 if (op == ('<' + '=')) 177 return ll <= rr; 178 if (op == '=' || (op == '=' + '=')) 179 return ll == rr; 180 if (op == '!' + '=') 181 return ll != rr; 182 if (op == '>') 183 return ll > rr; 184 /* >= */ 185 return ll >= rr; 186} 187 188/* The arithmetic operator handling functions. */ 189 190static arith_t arithmetic_common(VALUE *l, VALUE *r, int op) 191{ 192 arith_t li, ri; 193 194 if (!toarith(l) || !toarith(r)) 195 bb_error_msg_and_die("non-numeric argument"); 196 li = l->u.i; 197 ri = r->u.i; 198 if (op == '+') 199 return li + ri; 200 if (op == '-') 201 return li - ri; 202 if (op == '*') 203 return li * ri; 204 if (ri == 0) 205 bb_error_msg_and_die("division by zero"); 206 if (op == '/') 207 return li / ri; 208 return li % ri; 209} 210 211/* Do the : operator. 212 SV is the VALUE for the lhs (the string), 213 PV is the VALUE for the rhs (the pattern). */ 214 215static VALUE *docolon(VALUE *sv, VALUE *pv) 216{ 217 enum { NMATCH = 2 }; 218 VALUE *v; 219 regex_t re_buffer; 220 regmatch_t re_regs[NMATCH]; 221 222 tostring(sv); 223 tostring(pv); 224 225 if (pv->u.s[0] == '^') { 226 bb_error_msg( 227"warning: '%s': using '^' as the first character\n" 228"of a basic regular expression is not portable; it is ignored", pv->u.s); 229 } 230 231 memset(&re_buffer, 0, sizeof(re_buffer)); 232 memset(re_regs, 0, sizeof(re_regs)); 233 xregcomp(&re_buffer, pv->u.s, 0); 234 235 /* expr uses an anchored pattern match, so check that there was a 236 * match and that the match starts at offset 0. */ 237 if (regexec(&re_buffer, sv->u.s, NMATCH, re_regs, 0) != REG_NOMATCH 238 && re_regs[0].rm_so == 0 239 ) { 240 /* Were \(...\) used? */ 241 if (re_buffer.re_nsub > 0 && re_regs[1].rm_so >= 0) { 242 sv->u.s[re_regs[1].rm_eo] = '\0'; 243 v = str_value(sv->u.s + re_regs[1].rm_so); 244 } else { 245 v = int_value(re_regs[0].rm_eo); 246 } 247 } else { 248 /* Match failed -- return the right kind of null. */ 249 if (re_buffer.re_nsub > 0) 250 v = str_value(""); 251 else 252 v = int_value(0); 253 } 254 regfree(&re_buffer); 255 return v; 256} 257 258/* Handle bare operands and ( expr ) syntax. */ 259 260static VALUE *eval7(void) 261{ 262 VALUE *v; 263 264 if (!*G.args) 265 bb_error_msg_and_die("syntax error"); 266 267 if (nextarg("(")) { 268 G.args++; 269 v = eval(); 270 if (!nextarg(")")) 271 bb_error_msg_and_die("syntax error"); 272 G.args++; 273 return v; 274 } 275 276 if (nextarg(")")) 277 bb_error_msg_and_die("syntax error"); 278 279 return str_value(*G.args++); 280} 281 282/* Handle match, substr, index, length, and quote keywords. */ 283 284static VALUE *eval6(void) 285{ 286 static const char keywords[] ALIGN1 = 287 "quote\0""length\0""match\0""index\0""substr\0"; 288 289 VALUE *r, *i1, *i2; 290 VALUE *l = l; /* silence gcc */ 291 VALUE *v = v; /* silence gcc */ 292 int key = *G.args ? index_in_strings(keywords, *G.args) + 1 : 0; 293 294 if (key == 0) /* not a keyword */ 295 return eval7(); 296 G.args++; /* We have a valid token, so get the next argument. */ 297 if (key == 1) { /* quote */ 298 if (!*G.args) 299 bb_error_msg_and_die("syntax error"); 300 return str_value(*G.args++); 301 } 302 if (key == 2) { /* length */ 303 r = eval6(); 304 tostring(r); 305 v = int_value(strlen(r->u.s)); 306 freev(r); 307 } else 308 l = eval6(); 309 310 if (key == 3) { /* match */ 311 r = eval6(); 312 v = docolon(l, r); 313 freev(l); 314 freev(r); 315 } 316 if (key == 4) { /* index */ 317 r = eval6(); 318 tostring(l); 319 tostring(r); 320 v = int_value(strcspn(l->u.s, r->u.s) + 1); 321 if (v->u.i == (arith_t) strlen(l->u.s) + 1) 322 v->u.i = 0; 323 freev(l); 324 freev(r); 325 } 326 if (key == 5) { /* substr */ 327 i1 = eval6(); 328 i2 = eval6(); 329 tostring(l); 330 if (!toarith(i1) || !toarith(i2) 331 || i1->u.i > (arith_t) strlen(l->u.s) 332 || i1->u.i <= 0 || i2->u.i <= 0) 333 v = str_value(""); 334 else { 335 v = xmalloc(sizeof(VALUE)); 336 v->type = STRING; 337 v->u.s = xstrndup(l->u.s + i1->u.i - 1, i2->u.i); 338 } 339 freev(l); 340 freev(i1); 341 freev(i2); 342 } 343 return v; 344 345} 346 347/* Handle : operator (pattern matching). 348 Calls docolon to do the real work. */ 349 350static VALUE *eval5(void) 351{ 352 VALUE *l, *r, *v; 353 354 l = eval6(); 355 while (nextarg(":")) { 356 G.args++; 357 r = eval6(); 358 v = docolon(l, r); 359 freev(l); 360 freev(r); 361 l = v; 362 } 363 return l; 364} 365 366/* Handle *, /, % operators. */ 367 368static VALUE *eval4(void) 369{ 370 VALUE *l, *r; 371 int op; 372 arith_t val; 373 374 l = eval5(); 375 while (1) { 376 op = nextarg("*"); 377 if (!op) { op = nextarg("/"); 378 if (!op) { op = nextarg("%"); 379 if (!op) return l; 380 }} 381 G.args++; 382 r = eval5(); 383 val = arithmetic_common(l, r, op); 384 freev(l); 385 freev(r); 386 l = int_value(val); 387 } 388} 389 390/* Handle +, - operators. */ 391 392static VALUE *eval3(void) 393{ 394 VALUE *l, *r; 395 int op; 396 arith_t val; 397 398 l = eval4(); 399 while (1) { 400 op = nextarg("+"); 401 if (!op) { 402 op = nextarg("-"); 403 if (!op) return l; 404 } 405 G.args++; 406 r = eval4(); 407 val = arithmetic_common(l, r, op); 408 freev(l); 409 freev(r); 410 l = int_value(val); 411 } 412} 413 414/* Handle comparisons. */ 415 416static VALUE *eval2(void) 417{ 418 VALUE *l, *r; 419 int op; 420 arith_t val; 421 422 l = eval3(); 423 while (1) { 424 op = nextarg("<"); 425 if (!op) { op = nextarg("<="); 426 if (!op) { op = nextarg("="); 427 if (!op) { op = nextarg("=="); 428 if (!op) { op = nextarg("!="); 429 if (!op) { op = nextarg(">="); 430 if (!op) { op = nextarg(">"); 431 if (!op) return l; 432 }}}}}} 433 G.args++; 434 r = eval3(); 435 toarith(l); 436 toarith(r); 437 val = cmp_common(l, r, op); 438 freev(l); 439 freev(r); 440 l = int_value(val); 441 } 442} 443 444/* Handle &. */ 445 446static VALUE *eval1(void) 447{ 448 VALUE *l, *r; 449 450 l = eval2(); 451 while (nextarg("&")) { 452 G.args++; 453 r = eval2(); 454 if (null(l) || null(r)) { 455 freev(l); 456 freev(r); 457 l = int_value(0); 458 } else 459 freev(r); 460 } 461 return l; 462} 463 464/* Handle |. */ 465 466static VALUE *eval(void) 467{ 468 VALUE *l, *r; 469 470 l = eval1(); 471 while (nextarg("|")) { 472 G.args++; 473 r = eval1(); 474 if (null(l)) { 475 freev(l); 476 l = r; 477 } else 478 freev(r); 479 } 480 return l; 481} 482 483int expr_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE; 484int expr_main(int argc UNUSED_PARAM, char **argv) 485{ 486 VALUE *v; 487 488 xfunc_error_retval = 2; /* coreutils compat */ 489 G.args = argv + 1; 490 if (*G.args == NULL) { 491 bb_error_msg_and_die("too few arguments"); 492 } 493 v = eval(); 494 if (*G.args) 495 bb_error_msg_and_die("syntax error"); 496 if (v->type == INTEGER) 497 printf("%" PF_REZ "d\n", PF_REZ_TYPE v->u.i); 498 else 499 puts(v->u.s); 500 fflush_stdout_and_exit(null(v)); 501} 502