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