1 /* $OpenBSD: expr.c,v 1.17 2006/06/21 18:28:24 deraadt Exp $ */
2 /* $NetBSD: expr.c,v 1.3.6.1 1996/06/04 20:41:47 cgd Exp $ */
3
4 /*
5 * Written by J.T. Conklin <jtc@netbsd.org>.
6 * Public domain.
7 */
8
9 #include "config.h"
10 #include <stdio.h>
11 #include <stdlib.h>
12 #include <string.h>
13 #include <locale.h>
14 #include <ctype.h>
15 #ifdef KMK_WITH_REGEX
16 #include <regex.h>
17 #endif
18 #include <setjmp.h>
19 #include <assert.h>
20 #ifdef HAVE_ALLOCA_H
21 # include <alloca.h>
22 #endif
23 #include "err.h"
24 #include "getopt.h"
25 #include "kmkbuiltin.h"
26
27 static struct val *make_int(int);
28 static struct val *make_str(char *);
29 static void free_value(struct val *);
30 static int is_integer(struct val *, int *);
31 static int to_integer(struct val *);
32 static void to_string(struct val *);
33 static int is_zero_or_null(struct val *);
34 static void nexttoken(int);
35 static void error(void);
36 static struct val *eval6(void);
37 static struct val *eval5(void);
38 static struct val *eval4(void);
39 static struct val *eval3(void);
40 static struct val *eval2(void);
41 static struct val *eval1(void);
42 static struct val *eval0(void);
43
44 enum token {
45 OR, AND, EQ, LT, GT, ADD, SUB, MUL, DIV, MOD, MATCH, RP, LP,
46 NE, LE, GE, OPERAND, EOI
47 };
48
49 struct val {
50 enum {
51 integer,
52 string
53 } type;
54
55 union {
56 char *s;
57 int i;
58 } u;
59 };
60
61 static enum token token;
62 static struct val *tokval;
63 static char **av;
64 static jmp_buf g_expr_jmp;
65 static void **recorded_allocations;
66 static int num_recorded_allocations;
67
68
expr_mem_record_alloc(void * ptr)69 static void expr_mem_record_alloc(void *ptr)
70 {
71 if (!(num_recorded_allocations & 31)) {
72 void *newtab = realloc(recorded_allocations, (num_recorded_allocations + 33) * sizeof(void *));
73 if (!newtab)
74 longjmp(g_expr_jmp, err(3, NULL));
75 recorded_allocations = (void **)newtab;
76 }
77 recorded_allocations[num_recorded_allocations++] = ptr;
78 }
79
80
expr_mem_record_free(void * ptr)81 static void expr_mem_record_free(void *ptr)
82 {
83 int i = num_recorded_allocations;
84 while (i-- > 0)
85 if (recorded_allocations[i] == ptr) {
86 num_recorded_allocations--;
87 recorded_allocations[i] = recorded_allocations[num_recorded_allocations];
88 return;
89 }
90 assert(i >= 0);
91 }
92
expr_mem_init(void)93 static void expr_mem_init(void)
94 {
95 num_recorded_allocations = 0;
96 recorded_allocations = NULL;
97 }
98
expr_mem_cleanup(void)99 static void expr_mem_cleanup(void)
100 {
101 if (recorded_allocations) {
102 while (num_recorded_allocations-- > 0)
103 free(recorded_allocations[num_recorded_allocations]);
104 free(recorded_allocations);
105 recorded_allocations = NULL;
106 }
107 }
108
109
110 static struct val *
make_int(int i)111 make_int(int i)
112 {
113 struct val *vp;
114
115 vp = (struct val *) malloc(sizeof(*vp));
116 if (vp == NULL)
117 longjmp(g_expr_jmp, err(3, NULL));
118 expr_mem_record_alloc(vp);
119 vp->type = integer;
120 vp->u.i = i;
121 return vp;
122 }
123
124
125 static struct val *
make_str(char * s)126 make_str(char *s)
127 {
128 struct val *vp;
129
130 vp = (struct val *) malloc(sizeof(*vp));
131 if (vp == NULL || ((vp->u.s = strdup(s)) == NULL))
132 longjmp(g_expr_jmp, err(3, NULL));
133 expr_mem_record_alloc(vp->u.s);
134 expr_mem_record_alloc(vp);
135 vp->type = string;
136 return vp;
137 }
138
139
140 static void
free_value(struct val * vp)141 free_value(struct val *vp)
142 {
143 if (vp->type == string) {
144 expr_mem_record_free(vp->u.s);
145 free(vp->u.s);
146 }
147 free(vp);
148 expr_mem_record_free(vp);
149 }
150
151
152 /* determine if vp is an integer; if so, return it's value in *r */
153 static int
is_integer(struct val * vp,int * r)154 is_integer(struct val *vp, int *r)
155 {
156 char *s;
157 int neg;
158 int i;
159
160 if (vp->type == integer) {
161 *r = vp->u.i;
162 return 1;
163 }
164
165 /*
166 * POSIX.2 defines an "integer" as an optional unary minus
167 * followed by digits.
168 */
169 s = vp->u.s;
170 i = 0;
171
172 neg = (*s == '-');
173 if (neg)
174 s++;
175
176 while (*s) {
177 if (!isdigit(*s))
178 return 0;
179
180 i *= 10;
181 i += *s - '0';
182
183 s++;
184 }
185
186 if (neg)
187 i *= -1;
188
189 *r = i;
190 return 1;
191 }
192
193
194 /* coerce to vp to an integer */
195 static int
to_integer(struct val * vp)196 to_integer(struct val *vp)
197 {
198 int r;
199
200 if (vp->type == integer)
201 return 1;
202
203 if (is_integer(vp, &r)) {
204 expr_mem_record_free(vp->u.s);
205 free(vp->u.s);
206 vp->u.i = r;
207 vp->type = integer;
208 return 1;
209 }
210
211 return 0;
212 }
213
214
215 /* coerce to vp to an string */
216 static void
to_string(struct val * vp)217 to_string(struct val *vp)
218 {
219 char *tmp;
220
221 if (vp->type == string)
222 return;
223
224 if (asprintf(&tmp, "%d", vp->u.i) == -1)
225 longjmp(g_expr_jmp, err(3, NULL));
226 expr_mem_record_alloc(tmp);
227
228 vp->type = string;
229 vp->u.s = tmp;
230 }
231
232 static int
is_zero_or_null(struct val * vp)233 is_zero_or_null(struct val *vp)
234 {
235 if (vp->type == integer) {
236 return (vp->u.i == 0);
237 } else {
238 return (*vp->u.s == 0 || (to_integer(vp) && vp->u.i == 0));
239 }
240 /* NOTREACHED */
241 }
242
243 static void
nexttoken(int pat)244 nexttoken(int pat)
245 {
246 char *p;
247
248 if ((p = *av) == NULL) {
249 token = EOI;
250 return;
251 }
252 av++;
253
254
255 if (pat == 0 && p[0] != '\0') {
256 if (p[1] == '\0') {
257 const char *x = "|&=<>+-*/%:()";
258 char *i; /* index */
259
260 if ((i = strchr(x, *p)) != NULL) {
261 token = i - x;
262 return;
263 }
264 } else if (p[1] == '=' && p[2] == '\0') {
265 switch (*p) {
266 case '<':
267 token = LE;
268 return;
269 case '>':
270 token = GE;
271 return;
272 case '!':
273 token = NE;
274 return;
275 }
276 }
277 }
278 tokval = make_str(p);
279 token = OPERAND;
280 return;
281 }
282
283 #ifdef __GNUC__
284 __attribute__((noreturn))
285 #endif
286 static void
error(void)287 error(void)
288 {
289 longjmp(g_expr_jmp, errx(2, "syntax error"));
290 /* NOTREACHED */
291 }
292
293 static struct val *
eval6(void)294 eval6(void)
295 {
296 struct val *v;
297
298 if (token == OPERAND) {
299 nexttoken(0);
300 return tokval;
301
302 } else if (token == RP) {
303 nexttoken(0);
304 v = eval0();
305
306 if (token != LP) {
307 error();
308 /* NOTREACHED */
309 }
310 nexttoken(0);
311 return v;
312 } else {
313 error();
314 }
315 /* NOTREACHED */
316 }
317
318 /* Parse and evaluate match (regex) expressions */
319 static struct val *
eval5(void)320 eval5(void)
321 {
322 #ifdef KMK_WITH_REGEX
323 regex_t rp;
324 regmatch_t rm[2];
325 char errbuf[256];
326 int eval;
327 struct val *r;
328 struct val *v;
329 #endif
330 struct val *l;
331
332 l = eval6();
333 while (token == MATCH) {
334 #ifdef KMK_WITH_REGEX
335 nexttoken(1);
336 r = eval6();
337
338 /* coerce to both arguments to strings */
339 to_string(l);
340 to_string(r);
341
342 /* compile regular expression */
343 if ((eval = regcomp(&rp, r->u.s, 0)) != 0) {
344 regerror(eval, &rp, errbuf, sizeof(errbuf));
345 longjmp(g_expr_jmp, errx(2, "%s", errbuf));
346 }
347
348 /* compare string against pattern -- remember that patterns
349 are anchored to the beginning of the line */
350 if (regexec(&rp, l->u.s, 2, rm, 0) == 0 && rm[0].rm_so == 0) {
351 if (rm[1].rm_so >= 0) {
352 *(l->u.s + rm[1].rm_eo) = '\0';
353 v = make_str(l->u.s + rm[1].rm_so);
354
355 } else {
356 v = make_int((int)(rm[0].rm_eo - rm[0].rm_so));
357 }
358 } else {
359 if (rp.re_nsub == 0) {
360 v = make_int(0);
361 } else {
362 v = make_str("");
363 }
364 }
365
366 /* free arguments and pattern buffer */
367 free_value(l);
368 free_value(r);
369 regfree(&rp);
370
371 l = v;
372 #else
373 longjmp(g_expr_jmp, errx(2, "regex not supported, sorry."));
374 #endif
375 }
376
377 return l;
378 }
379
380 /* Parse and evaluate multiplication and division expressions */
381 static struct val *
eval4(void)382 eval4(void)
383 {
384 struct val *l, *r;
385 enum token op;
386
387 l = eval5();
388 while ((op = token) == MUL || op == DIV || op == MOD) {
389 nexttoken(0);
390 r = eval5();
391
392 if (!to_integer(l) || !to_integer(r)) {
393 longjmp(g_expr_jmp, errx(2, "non-numeric argument"));
394 }
395
396 if (op == MUL) {
397 l->u.i *= r->u.i;
398 } else {
399 if (r->u.i == 0) {
400 longjmp(g_expr_jmp, errx(2, "division by zero"));
401 }
402 if (op == DIV) {
403 l->u.i /= r->u.i;
404 } else {
405 l->u.i %= r->u.i;
406 }
407 }
408
409 free_value(r);
410 }
411
412 return l;
413 }
414
415 /* Parse and evaluate addition and subtraction expressions */
416 static struct val *
eval3(void)417 eval3(void)
418 {
419 struct val *l, *r;
420 enum token op;
421
422 l = eval4();
423 while ((op = token) == ADD || op == SUB) {
424 nexttoken(0);
425 r = eval4();
426
427 if (!to_integer(l) || !to_integer(r)) {
428 longjmp(g_expr_jmp, errx(2, "non-numeric argument"));
429 }
430
431 if (op == ADD) {
432 l->u.i += r->u.i;
433 } else {
434 l->u.i -= r->u.i;
435 }
436
437 free_value(r);
438 }
439
440 return l;
441 }
442
443 /* Parse and evaluate comparison expressions */
444 static struct val *
eval2(void)445 eval2(void)
446 {
447 struct val *l, *r;
448 enum token op;
449 int v = 0, li, ri;
450
451 l = eval3();
452 while ((op = token) == EQ || op == NE || op == LT || op == GT ||
453 op == LE || op == GE) {
454 nexttoken(0);
455 r = eval3();
456
457 if (is_integer(l, &li) && is_integer(r, &ri)) {
458 switch (op) {
459 case GT:
460 v = (li > ri);
461 break;
462 case GE:
463 v = (li >= ri);
464 break;
465 case LT:
466 v = (li < ri);
467 break;
468 case LE:
469 v = (li <= ri);
470 break;
471 case EQ:
472 v = (li == ri);
473 break;
474 case NE:
475 v = (li != ri);
476 break;
477 default:
478 break;
479 }
480 } else {
481 to_string(l);
482 to_string(r);
483
484 switch (op) {
485 case GT:
486 v = (strcoll(l->u.s, r->u.s) > 0);
487 break;
488 case GE:
489 v = (strcoll(l->u.s, r->u.s) >= 0);
490 break;
491 case LT:
492 v = (strcoll(l->u.s, r->u.s) < 0);
493 break;
494 case LE:
495 v = (strcoll(l->u.s, r->u.s) <= 0);
496 break;
497 case EQ:
498 v = (strcoll(l->u.s, r->u.s) == 0);
499 break;
500 case NE:
501 v = (strcoll(l->u.s, r->u.s) != 0);
502 break;
503 default:
504 break;
505 }
506 }
507
508 free_value(l);
509 free_value(r);
510 l = make_int(v);
511 }
512
513 return l;
514 }
515
516 /* Parse and evaluate & expressions */
517 static struct val *
eval1(void)518 eval1(void)
519 {
520 struct val *l, *r;
521
522 l = eval2();
523 while (token == AND) {
524 nexttoken(0);
525 r = eval2();
526
527 if (is_zero_or_null(l) || is_zero_or_null(r)) {
528 free_value(l);
529 free_value(r);
530 l = make_int(0);
531 } else {
532 free_value(r);
533 }
534 }
535
536 return l;
537 }
538
539 /* Parse and evaluate | expressions */
540 static struct val *
eval0(void)541 eval0(void)
542 {
543 struct val *l, *r;
544
545 l = eval1();
546 while (token == OR) {
547 nexttoken(0);
548 r = eval1();
549
550 if (is_zero_or_null(l)) {
551 free_value(l);
552 l = r;
553 } else {
554 free_value(r);
555 }
556 }
557
558 return l;
559 }
560
561
562 int
kmk_builtin_expr(int argc,char * argv[],char ** envp)563 kmk_builtin_expr(int argc, char *argv[], char **envp)
564 {
565 struct val *vp;
566 int rval;
567
568 /* re-init globals */
569 token = 0;
570 tokval = 0;
571 av = 0;
572 expr_mem_init();
573
574 #ifdef kmk_builtin_expr /* kmk already does this. */
575 (void) setlocale(LC_ALL, "");
576 #endif
577
578 if (argc > 1 && !strcmp(argv[1], "--"))
579 argv++;
580
581 av = argv + 1;
582
583 rval = setjmp(g_expr_jmp);
584 if (!rval) {
585 nexttoken(0);
586 vp = eval0();
587
588 if (token != EOI) {
589 error();
590 /* NOTREACHED */
591 }
592
593 if (vp->type == integer)
594 printf("%d\n", vp->u.i);
595 else
596 printf("%s\n", vp->u.s);
597
598 rval = is_zero_or_null(vp);
599 }
600 /* else: longjmp */
601
602 /* cleanup */
603 expr_mem_cleanup();
604 return rval;
605 }
606