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  * This program is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU General Public License as published by
  16  * the Free Software Foundation; either version 2 of the License, or
  17  * (at your option) any later version.
  18  *
  19  * This program is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  22  * General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU General Public License
  25  * along with this program; if not, write to the Free Software
  26  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  27  *
  28  */
  29
  30 /* This program evaluates expressions.  Each token (operator, operand,
  31  * parenthesis) of the expression must be a separate argument.  The
  32  * parser used is a reasonably general one, though any incarnation of
  33  * it is language-specific.  It is especially nice for expressions.
  34  *
  35  * No parse tree is needed; a new node is evaluated immediately.
  36  * One function can handle multiple operators all of equal precedence,
  37  * provided they all associate ((x op x) op x). */
  38
  39 /* no getopt needed */
  40
  41 #include <stdio.h>
  42 #include <string.h>
  43 #include <stdlib.h>
  44 #include <regex.h>
  45 #include <sys/types.h>
  46 #include <errno.h>
  47 #include "busybox.h"
  48
  49
  50 /* The kinds of value we can have.  */
  51 enum valtype {
  52         integer,
  53         string
  54 };
  55 typedef enum valtype TYPE;
  56
  57 #if ENABLE_EXPR_MATH_SUPPORT_64
  58 typedef int64_t arith_t;
  59 #define PF_REZ      "ll"
  60 #define PF_REZ_TYPE (long long)
  61 #define STRTOL(s, e, b) strtoll(s, e, b)
  62 #else
  63 typedef long arith_t;
  64 #define PF_REZ      "l"
  65 #define PF_REZ_TYPE (long)
  66 #define STRTOL(s, e, b) strtol(s, e, b)
  67 #endif
  68
  69 /* A value is.... */
  70 struct valinfo {
  71         TYPE type;                      /* Which kind. */
  72         union {                         /* The value itself. */
  73                 arith_t i;
  74                 char *s;
  75         } u;
  76 };
  77 typedef struct valinfo VALUE;
  78
  79 /* The arguments given to the program, minus the program name.  */
  80 static char **args;
  81
  82 static VALUE *docolon (VALUE *sv, VALUE *pv);
  83 static VALUE *eval (void);
  84 static VALUE *int_value (arith_t i);
  85 static VALUE *str_value (char *s);
  86 static int nextarg (char *str);
  87 static int null (VALUE *v);
  88 static int toarith (VALUE *v);
  89 static void freev (VALUE *v);
  90 static void tostring (VALUE *v);
  91
  92 int expr_main (int argc, char **argv)
  93 {
  94         VALUE *v;
  95
  96         if (argc == 1) {
  97                 bb_error_msg_and_die("too few arguments");
  98         }
  99
 100         args = argv + 1;
 101
 102         v = eval ();
 103         if (*args)
 104                 bb_error_msg_and_die ("syntax error");
 105
 106         if (v->type == integer)
 107                 printf ("%" PF_REZ "d\n", PF_REZ_TYPE v->u.i);
 108         else
 109                 puts (v->u.s);
 110
 111         exit (null (v));
 112 }
 113
 114 /* Return a VALUE for I.  */
 115
 116 static VALUE *int_value (arith_t i)
 117 {
 118         VALUE *v;
 119
 120         v = xmalloc (sizeof(VALUE));
 121         v->type = integer;
 122         v->u.i = i;
 123         return v;
 124 }
 125
 126 /* Return a VALUE for S.  */
 127
 128 static VALUE *str_value (char *s)
 129 {
 130         VALUE *v;
 131
 132         v = xmalloc (sizeof(VALUE));
 133         v->type = string;
 134         v->u.s = bb_xstrdup (s);
 135         return v;
 136 }
 137
 138 /* Free VALUE V, including structure components.  */
 139
 140 static void freev (VALUE *v)
 141 {
 142         if (v->type == string)
 143                 free (v->u.s);
 144         free (v);
 145 }
 146
 147 /* Return nonzero if V is a null-string or zero-number.  */
 148
 149 static int null (VALUE *v)
 150 {
 151         switch (v->type) {
 152                 case integer:
 153                         return v->u.i == 0;
 154                 default: /* string: */
 155                         return v->u.s[0] == '\0' || strcmp (v->u.s, "0") == 0;
 156         }
 157 }
 158
 159 /* Coerce V to a string value (can't fail).  */
 160
 161 static void tostring (VALUE *v)
 162 {
 163         if (v->type == integer) {
 164                 v->u.s = bb_xasprintf ("%" PF_REZ "d", PF_REZ_TYPE v->u.i);
 165                 v->type = string;
 166         }
 167 }
 168
 169 /* Coerce V to an integer value.  Return 1 on success, 0 on failure.  */
 170
 171 static int toarith (VALUE *v)
 172 {
 173         if(v->type == string) {
 174                 arith_t i;
 175                 char *e;
 176
 177                 /* Don't interpret the empty string as an integer.  */
 178                 /* Currently does not worry about overflow or int/long differences. */
 179                 i = STRTOL(v->u.s, &e, 10);
 180                 if ((v->u.s == e) || *e)
 181                         return 0;
 182                 free (v->u.s);
 183                 v->u.i = i;
 184                 v->type = integer;
 185         }
 186         return 1;
 187 }
 188
 189 /* Return nonzero if the next token matches STR exactly.
 190    STR must not be NULL.  */
 191
 192 static int
 193 nextarg (char *str)
 194 {
 195         if (*args == NULL)
 196                 return 0;
 197         return strcmp (*args, str) == 0;
 198 }
 199
 200 /* The comparison operator handling functions.  */
 201
 202 static int cmp_common (VALUE *l, VALUE *r, int op)
 203 {
 204         int cmpval;
 205
 206         if (l->type == string || r->type == string) {
 207                 tostring (l);
 208                 tostring (r);
 209                 cmpval = strcmp (l->u.s, r->u.s);
 210         }
 211         else
 212                 cmpval = l->u.i - r->u.i;
 213         switch(op) {
 214                 case '<':
 215                         return cmpval < 0;
 216                 case ('L'+'E'):
 217                         return cmpval <= 0;
 218                 case '=':
 219                         return cmpval == 0;
 220                 case '!':
 221                         return cmpval != 0;
 222                 case '>':
 223                         return cmpval > 0;
 224                 default: /* >= */
 225                         return cmpval >= 0;
 226         }
 227 }
 228
 229 /* The arithmetic operator handling functions.  */
 230
 231 static arith_t arithmetic_common (VALUE *l, VALUE *r, int op)
 232 {
 233   arith_t li, ri;
 234
 235   if (!toarith (l) || !toarith (r))
 236     bb_error_msg_and_die ("non-numeric argument");
 237   li = l->u.i;
 238   ri = r->u.i;
 239   if((op == '/' || op == '%') && ri == 0)
 240     bb_error_msg_and_die ( "division by zero");
 241   switch(op) {
 242         case '+':
 243                 return li + ri;
 244         case '-':
 245                 return li - ri;
 246         case '*':
 247                 return li * ri;
 248         case '/':
 249                 return li / ri;
 250         default:
 251                 return li % ri;
 252   }
 253 }
 254
 255 /* Do the : operator.
 256    SV is the VALUE for the lhs (the string),
 257    PV is the VALUE for the rhs (the pattern).  */
 258
 259 static VALUE *docolon (VALUE *sv, VALUE *pv)
 260 {
 261         VALUE *v;
 262         regex_t re_buffer;
 263         const int NMATCH = 2;
 264         regmatch_t re_regs[NMATCH];
 265
 266         tostring (sv);
 267         tostring (pv);
 268
 269         if (pv->u.s[0] == '^') {
 270                 fprintf (stderr, "\
 271 warning: unportable BRE: `%s': using `^' as the first character\n\
 272 of a basic regular expression is not portable; it is being ignored",
 273                 pv->u.s);
 274         }
 275
 276         memset (&re_buffer, 0, sizeof (re_buffer));
 277         memset (re_regs, 0, sizeof (*re_regs));
 278         if( regcomp (&re_buffer, pv->u.s, 0) != 0 )
 279                 bb_error_msg_and_die("Invalid regular expression");
 280
 281         /* expr uses an anchored pattern match, so check that there was a
 282          * match and that the match starts at offset 0. */
 283         if (regexec (&re_buffer, sv->u.s, NMATCH, re_regs, 0) != REG_NOMATCH &&
 284                         re_regs[0].rm_so == 0) {
 285                 /* Were \(...\) used? */
 286                 if (re_buffer.re_nsub > 0) {
 287                         sv->u.s[re_regs[1].rm_eo] = '\0';
 288                         v = str_value (sv->u.s + re_regs[1].rm_so);
 289                 }
 290                 else
 291                         v = int_value (re_regs[0].rm_eo);
 292         }
 293         else {
 294                 /* Match failed -- return the right kind of null.  */
 295                 if (re_buffer.re_nsub > 0)
 296                         v = str_value ("");
 297                 else
 298                         v = int_value (0);
 299         }
 300         return v;
 301 }
 302
 303 /* Handle bare operands and ( expr ) syntax.  */
 304
 305 static VALUE *eval7 (void)
 306 {
 307         VALUE *v;
 308
 309         if (!*args)
 310                 bb_error_msg_and_die ( "syntax error");
 311
 312         if (nextarg ("(")) {
 313                 args++;
 314                 v = eval ();
 315                 if (!nextarg (")"))
 316                         bb_error_msg_and_die ( "syntax error");
 317                         args++;
 318                         return v;
 319                 }
 320
 321         if (nextarg (")"))
 322                 bb_error_msg_and_die ( "syntax error");
 323
 324         return str_value (*args++);
 325 }
 326
 327 /* Handle match, substr, index, length, and quote keywords.  */
 328
 329 static VALUE *eval6 (void)
 330 {
 331         VALUE *l, *r, *v, *i1, *i2;
 332
 333         if (nextarg ("quote")) {
 334                 args++;
 335                 if (!*args)
 336                         bb_error_msg_and_die ( "syntax error");
 337                 return str_value (*args++);
 338         }
 339         else if (nextarg ("length")) {
 340                 args++;
 341                 r = eval6 ();
 342                 tostring (r);
 343                 v = int_value (strlen (r->u.s));
 344                 freev (r);
 345                 return v;
 346         }
 347         else if (nextarg ("match")) {
 348                 args++;
 349                 l = eval6 ();
 350                 r = eval6 ();
 351                 v = docolon (l, r);
 352                 freev (l);
 353                 freev (r);
 354                 return v;
 355         }
 356         else if (nextarg ("index")) {
 357                 args++;
 358                 l = eval6 ();
 359                 r = eval6 ();
 360                 tostring (l);
 361                 tostring (r);
 362                 v = int_value (strcspn (l->u.s, r->u.s) + 1);
 363                 if (v->u.i == (arith_t) strlen (l->u.s) + 1)
 364                         v->u.i = 0;
 365                 freev (l);
 366                 freev (r);
 367                 return v;
 368         }
 369         else if (nextarg ("substr")) {
 370                 args++;
 371                 l = eval6 ();
 372                 i1 = eval6 ();
 373                 i2 = eval6 ();
 374                 tostring (l);
 375                 if (!toarith (i1) || !toarith (i2)
 376                         || i1->u.i > (arith_t) strlen (l->u.s)
 377                         || i1->u.i <= 0 || i2->u.i <= 0)
 378                 v = str_value ("");
 379                 else {
 380                         v = xmalloc (sizeof(VALUE));
 381                         v->type = string;
 382                         v->u.s = bb_xstrndup(l->u.s + i1->u.i - 1, i2->u.i);
 383                 }
 384                 freev (l);
 385                 freev (i1);
 386                 freev (i2);
 387                 return v;
 388         }
 389         else
 390                 return eval7 ();
 391 }
 392
 393 /* Handle : operator (pattern matching).
 394    Calls docolon to do the real work.  */
 395
 396 static VALUE *eval5 (void)
 397 {
 398         VALUE *l, *r, *v;
 399
 400         l = eval6 ();
 401         while (nextarg (":")) {
 402                 args++;
 403                 r = eval6 ();
 404                 v = docolon (l, r);
 405                 freev (l);
 406                 freev (r);
 407                 l = v;
 408         }
 409         return l;
 410 }
 411
 412 /* Handle *, /, % operators.  */
 413
 414 static VALUE *eval4 (void)
 415 {
 416         VALUE *l, *r;
 417         int op;
 418         arith_t val;
 419
 420         l = eval5 ();
 421         while (1) {
 422                 if (nextarg ("*"))
 423                         op = '*';
 424                 else if (nextarg ("/"))
 425                         op = '/';
 426                 else if (nextarg ("%"))
 427                         op = '%';
 428                 else
 429                         return l;
 430                 args++;
 431                 r = eval5 ();
 432                 val = arithmetic_common (l, r, op);
 433                 freev (l);
 434                 freev (r);
 435                 l = int_value (val);
 436         }
 437 }
 438
 439 /* Handle +, - operators.  */
 440
 441 static VALUE *eval3 (void)
 442 {
 443         VALUE *l, *r;
 444         int op;
 445         arith_t val;
 446
 447         l = eval4 ();
 448         while (1) {
 449                 if (nextarg ("+"))
 450                         op = '+';
 451                 else if (nextarg ("-"))
 452                         op = '-';
 453                 else
 454                         return l;
 455                 args++;
 456                 r = eval4 ();
 457                 val = arithmetic_common (l, r, op);
 458                 freev (l);
 459                 freev (r);
 460                 l = int_value (val);
 461         }
 462 }
 463
 464 /* Handle comparisons.  */
 465
 466 static VALUE *eval2 (void)
 467 {
 468         VALUE *l, *r;
 469         int op;
 470         arith_t val;
 471
 472         l = eval3 ();
 473         while (1) {
 474                 if (nextarg ("<"))
 475                         op = '<';
 476                 else if (nextarg ("<="))
 477                         op = 'L'+'E';
 478                 else if (nextarg ("=") || nextarg ("=="))
 479                         op = '=';
 480                 else if (nextarg ("!="))
 481                         op = '!';
 482                 else if (nextarg (">="))
 483                         op = 'G'+'E';
 484                 else if (nextarg (">"))
 485                         op = '>';
 486                 else
 487                         return l;
 488                 args++;
 489                 r = eval3 ();
 490                 toarith (l);
 491                 toarith (r);
 492                 val = cmp_common (l, r, op);
 493                 freev (l);
 494                 freev (r);
 495                 l = int_value (val);
 496         }
 497 }
 498
 499 /* Handle &.  */
 500
 501 static VALUE *eval1 (void)
 502 {
 503         VALUE *l, *r;
 504
 505         l = eval2 ();
 506         while (nextarg ("&")) {
 507                 args++;
 508                 r = eval2 ();
 509                 if (null (l) || null (r)) {
 510                         freev (l);
 511                         freev (r);
 512                         l = int_value (0);
 513                 }
 514                 else
 515                         freev (r);
 516         }
 517         return l;
 518 }
 519
 520 /* Handle |.  */
 521
 522 static VALUE *eval (void)
 523 {
 524         VALUE *l, *r;
 525
 526         l = eval1 ();
 527         while (nextarg ("|")) {
 528                 args++;
 529                 r = eval1 ();
 530                 if (null (l)) {
 531                         freev (l);
 532                         l = r;
 533                 }
 534                 else
 535                         freev (r);
 536         }
 537         return l;
 538 }