coreutils/expr.c

   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
  32 typedef 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
  38 typedef 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.  */
  48 enum {
  49         INTEGER,
  50         STRING
  51 };
  52
  53 /* A value is.... */
  54 struct valinfo {
  55         smallint type;                  /* Which kind. */
  56         union {                         /* The value itself. */
  57                 arith_t i;
  58                 char *s;
  59         } u;
  60 };
  61 typedef struct valinfo VALUE;
  62
  63 /* The arguments given to the program, minus the program name.  */
  64 struct globals {
  65         char **args;
  66 };
  67 #define G (*(struct globals*)&bb_common_bufsiz1)
  68
  69 /* forward declarations */
  70 static VALUE *eval(void);
  71
  72
  73 /* Return a VALUE for I.  */
  74
  75 static 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
  88 static 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
 101 static 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
 110 static 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
 120 static 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
 130 static 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
 151 static 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
 160 static 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
 190 static 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
 215 static VALUE *docolon(VALUE *sv, VALUE *pv)
 216 {
 217         VALUE *v;
 218         regex_t re_buffer;
 219         const int NMATCH = 2;
 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: unportable BRE: `%s': using `^' as the first character\n\
 228 of a basic regular expression is not portable; it is being 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) {
 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 //FIXME: sounds like here is a bit missing: regfree(&re_buffer);
 255         return v;
 256 }
 257
 258 /* Handle bare operands and ( expr ) syntax.  */
 259
 260 static 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
 284 static 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
 350 static 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
 368 static 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
 392 static 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
 416 static 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
 446 static 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
 466 static 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
 483 int expr_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
 484 int 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 }