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