diff options
Diffstat (limited to 'expr.c')
-rw-r--r-- | expr.c | 531 |
1 files changed, 531 insertions, 0 deletions
@@ -0,0 +1,531 @@ | |||
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 | } | ||