Contents of /tags/mkinitrd-6_5_0/busybox/coreutils/expr.c
Parent Directory | Revision Log
Revision 1345 -
(show annotations)
(download)
Fri Jun 3 21:22:00 2011 UTC (13 years, 3 months ago) by niro
File MIME type: text/plain
File size: 9889 byte(s)
Fri Jun 3 21:22:00 2011 UTC (13 years, 3 months ago) by niro
File MIME type: text/plain
File size: 9889 byte(s)
tagged 'mkinitrd-6_5_0'
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 | } FIX_ALIASING; |
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 | enum { NMATCH = 2 }; |
218 | VALUE *v; |
219 | regex_t re_buffer; |
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: '%s': using '^' as the first character\n" |
228 | "of a basic regular expression is not portable; it is 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 && re_regs[1].rm_so >= 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 | 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 | } |