Annotation of /trunk/mkinitrd-magellan/busybox/coreutils/expr.c
Parent Directory | Revision Log
Revision 816 -
(hide annotations)
(download)
Fri Apr 24 18:33:46 2009 UTC (15 years, 1 month ago) by niro
File MIME type: text/plain
File size: 9855 byte(s)
Fri Apr 24 18:33:46 2009 UTC (15 years, 1 month ago) by niro
File MIME type: text/plain
File size: 9855 byte(s)
-updated to busybox-1.13.4
1 | niro | 532 | /* 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 | niro | 816 | #include "libbb.h" |
29 | niro | 532 | #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 | niro | 816 | /* The kinds of value we can have. */ |
48 | enum { | ||
49 | INTEGER, | ||
50 | STRING | ||
51 | }; | ||
52 | |||
53 | niro | 532 | /* A value is.... */ |
54 | struct valinfo { | ||
55 | niro | 816 | smallint type; /* Which kind. */ |
56 | union { /* The value itself. */ | ||
57 | niro | 532 | 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 | niro | 816 | struct globals { |
65 | char **args; | ||
66 | }; | ||
67 | #define G (*(struct globals*)&bb_common_bufsiz1) | ||
68 | niro | 532 | |
69 | niro | 816 | /* forward declarations */ |
70 | niro | 532 | 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 | niro | 816 | v = xzalloc(sizeof(VALUE)); |
80 | if (INTEGER) /* otherwise xzaaloc did it already */ | ||
81 | v->type = INTEGER; | ||
82 | niro | 532 | v->u.i = i; |
83 | return v; | ||
84 | } | ||
85 | |||
86 | /* Return a VALUE for S. */ | ||
87 | |||
88 | niro | 816 | static VALUE *str_value(const char *s) |
89 | niro | 532 | { |
90 | VALUE *v; | ||
91 | |||
92 | niro | 816 | v = xzalloc(sizeof(VALUE)); |
93 | if (STRING) /* otherwise xzaaloc did it already */ | ||
94 | v->type = STRING; | ||
95 | niro | 532 | v->u.s = xstrdup(s); |
96 | return v; | ||
97 | } | ||
98 | |||
99 | /* Free VALUE V, including structure components. */ | ||
100 | |||
101 | niro | 816 | static void freev(VALUE *v) |
102 | niro | 532 | { |
103 | niro | 816 | if (v->type == STRING) |
104 | niro | 532 | free(v->u.s); |
105 | free(v); | ||
106 | } | ||
107 | |||
108 | /* Return nonzero if V is a null-string or zero-number. */ | ||
109 | |||
110 | niro | 816 | static int null(VALUE *v) |
111 | niro | 532 | { |
112 | niro | 816 | if (v->type == INTEGER) |
113 | niro | 532 | return v->u.i == 0; |
114 | niro | 816 | /* STRING: */ |
115 | return v->u.s[0] == '\0' || LONE_CHAR(v->u.s, '0'); | ||
116 | niro | 532 | } |
117 | |||
118 | niro | 816 | /* Coerce V to a STRING value (can't fail). */ |
119 | niro | 532 | |
120 | niro | 816 | static void tostring(VALUE *v) |
121 | niro | 532 | { |
122 | niro | 816 | if (v->type == INTEGER) { |
123 | niro | 532 | v->u.s = xasprintf("%" PF_REZ "d", PF_REZ_TYPE v->u.i); |
124 | niro | 816 | v->type = STRING; |
125 | niro | 532 | } |
126 | } | ||
127 | |||
128 | niro | 816 | /* Coerce V to an INTEGER value. Return 1 on success, 0 on failure. */ |
129 | niro | 532 | |
130 | niro | 816 | static bool toarith(VALUE *v) |
131 | niro | 532 | { |
132 | niro | 816 | if (v->type == STRING) { |
133 | niro | 532 | 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 | niro | 816 | v->type = INTEGER; |
144 | niro | 532 | } |
145 | return 1; | ||
146 | } | ||
147 | |||
148 | niro | 816 | /* Return str[0]+str[1] if the next token matches STR exactly. |
149 | niro | 532 | STR must not be NULL. */ |
150 | |||
151 | niro | 816 | static int nextarg(const char *str) |
152 | niro | 532 | { |
153 | niro | 816 | if (*G.args == NULL || strcmp(*G.args, str) != 0) |
154 | niro | 532 | return 0; |
155 | niro | 816 | return (unsigned char)str[0] + (unsigned char)str[1]; |
156 | niro | 532 | } |
157 | |||
158 | /* The comparison operator handling functions. */ | ||
159 | |||
160 | niro | 816 | static int cmp_common(VALUE *l, VALUE *r, int op) |
161 | niro | 532 | { |
162 | niro | 816 | arith_t ll, rr; |
163 | niro | 532 | |
164 | niro | 816 | ll = l->u.i; |
165 | rr = r->u.i; | ||
166 | if (l->type == STRING || r->type == STRING) { | ||
167 | niro | 532 | tostring(l); |
168 | tostring(r); | ||
169 | niro | 816 | 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 | niro | 532 | if (op == '<') |
175 | niro | 816 | 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 | niro | 532 | } |
187 | |||
188 | /* The arithmetic operator handling functions. */ | ||
189 | |||
190 | niro | 816 | static arith_t arithmetic_common(VALUE *l, VALUE *r, int op) |
191 | niro | 532 | { |
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 | niro | 816 | if (op == '-') |
201 | niro | 532 | return li - ri; |
202 | niro | 816 | if (op == '*') |
203 | niro | 532 | return li * ri; |
204 | niro | 816 | if (ri == 0) |
205 | bb_error_msg_and_die("division by zero"); | ||
206 | if (op == '/') | ||
207 | niro | 532 | return li / ri; |
208 | niro | 816 | return li % ri; |
209 | niro | 532 | } |
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 | niro | 816 | static VALUE *docolon(VALUE *sv, VALUE *pv) |
216 | niro | 532 | { |
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 | niro | 816 | bb_error_msg("\ |
227 | niro | 532 | 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 | niro | 816 | xregcomp(&re_buffer, pv->u.s, 0); |
234 | niro | 532 | |
235 | /* expr uses an anchored pattern match, so check that there was a | ||
236 | * match and that the match starts at offset 0. */ | ||
237 | niro | 816 | if (regexec(&re_buffer, sv->u.s, NMATCH, re_regs, 0) != REG_NOMATCH |
238 | && re_regs[0].rm_so == 0 | ||
239 | ) { | ||
240 | niro | 532 | /* 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 | niro | 816 | } else { |
245 | niro | 532 | v = int_value(re_regs[0].rm_eo); |
246 | niro | 816 | } |
247 | niro | 532 | } 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 | niro | 816 | //FIXME: sounds like here is a bit missing: regfree(&re_buffer); |
255 | niro | 532 | return v; |
256 | } | ||
257 | |||
258 | /* Handle bare operands and ( expr ) syntax. */ | ||
259 | |||
260 | static VALUE *eval7(void) | ||
261 | { | ||
262 | VALUE *v; | ||
263 | |||
264 | niro | 816 | if (!*G.args) |
265 | niro | 532 | bb_error_msg_and_die("syntax error"); |
266 | |||
267 | if (nextarg("(")) { | ||
268 | niro | 816 | G.args++; |
269 | niro | 532 | v = eval(); |
270 | if (!nextarg(")")) | ||
271 | bb_error_msg_and_die("syntax error"); | ||
272 | niro | 816 | G.args++; |
273 | niro | 532 | return v; |
274 | } | ||
275 | |||
276 | if (nextarg(")")) | ||
277 | bb_error_msg_and_die("syntax error"); | ||
278 | |||
279 | niro | 816 | return str_value(*G.args++); |
280 | niro | 532 | } |
281 | |||
282 | /* Handle match, substr, index, length, and quote keywords. */ | ||
283 | |||
284 | static VALUE *eval6(void) | ||
285 | { | ||
286 | niro | 816 | static const char keywords[] ALIGN1 = |
287 | "quote\0""length\0""match\0""index\0""substr\0"; | ||
288 | niro | 532 | |
289 | niro | 816 | 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 | niro | 532 | bb_error_msg_and_die("syntax error"); |
300 | niro | 816 | return str_value(*G.args++); |
301 | } | ||
302 | if (key == 2) { /* length */ | ||
303 | niro | 532 | r = eval6(); |
304 | tostring(r); | ||
305 | v = int_value(strlen(r->u.s)); | ||
306 | freev(r); | ||
307 | niro | 816 | } else |
308 | niro | 532 | l = eval6(); |
309 | niro | 816 | |
310 | if (key == 3) { /* match */ | ||
311 | niro | 532 | r = eval6(); |
312 | v = docolon(l, r); | ||
313 | freev(l); | ||
314 | freev(r); | ||
315 | niro | 816 | } |
316 | if (key == 4) { /* index */ | ||
317 | niro | 532 | 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 | niro | 816 | } |
326 | if (key == 5) { /* substr */ | ||
327 | niro | 532 | i1 = eval6(); |
328 | i2 = eval6(); | ||
329 | tostring(l); | ||
330 | if (!toarith(i1) || !toarith(i2) | ||
331 | niro | 816 | || i1->u.i > (arith_t) strlen(l->u.s) |
332 | || i1->u.i <= 0 || i2->u.i <= 0) | ||
333 | niro | 532 | v = str_value(""); |
334 | else { | ||
335 | v = xmalloc(sizeof(VALUE)); | ||
336 | niro | 816 | v->type = STRING; |
337 | niro | 532 | 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 | niro | 816 | } |
343 | return v; | ||
344 | |||
345 | niro | 532 | } |
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 | niro | 816 | G.args++; |
357 | niro | 532 | 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 | niro | 816 | op = nextarg("*"); |
377 | if (!op) { op = nextarg("/"); | ||
378 | if (!op) { op = nextarg("%"); | ||
379 | if (!op) return l; | ||
380 | }} | ||
381 | G.args++; | ||
382 | niro | 532 | 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 | niro | 816 | op = nextarg("+"); |
401 | if (!op) { | ||
402 | op = nextarg("-"); | ||
403 | if (!op) return l; | ||
404 | } | ||
405 | G.args++; | ||
406 | niro | 532 | 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 | niro | 816 | 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 | niro | 532 | 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 | niro | 816 | G.args++; |
453 | niro | 532 | 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 | niro | 816 | G.args++; |
473 | niro | 532 | r = eval1(); |
474 | if (null(l)) { | ||
475 | freev(l); | ||
476 | l = r; | ||
477 | } else | ||
478 | freev(r); | ||
479 | } | ||
480 | return l; | ||
481 | } | ||
482 | niro | 816 | |
483 | int expr_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE; | ||
484 | int expr_main(int argc, char **argv) | ||
485 | { | ||
486 | VALUE *v; | ||
487 | |||
488 | if (argc == 1) { | ||
489 | bb_error_msg_and_die("too few arguments"); | ||
490 | } | ||
491 | |||
492 | G.args = argv + 1; | ||
493 | |||
494 | v = eval(); | ||
495 | if (*G.args) | ||
496 | bb_error_msg_and_die("syntax error"); | ||
497 | |||
498 | if (v->type == INTEGER) | ||
499 | printf("%" PF_REZ "d\n", PF_REZ_TYPE v->u.i); | ||
500 | else | ||
501 | puts(v->u.s); | ||
502 | |||
503 | fflush_stdout_and_exit(null(v)); | ||
504 | } |