Mercurial > hg > index.cgi

comparison lwlib/lw_expr.c @ 0:2c24602be78f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial import from lwtools 3.0.1 version, with new hand built build system and file reorganization
author lost@l-w.ca
date Wed, 19 Jan 2011 22:27:17 -0700
parents
children 7317fbe024af
comparison
equal deleted inserted replaced
-1:000000000000 0:2c24602be78f
1 /*
2 lwexpr.c
3
4 Copyright © 2010 William Astle
5
6 This file is part of LWTOOLS.
7
8 LWTOOLS is free software: you can redistribute it and/or modify it under the
9 terms of the GNU General Public License as published by the Free Software
10 Foundation, either version 3 of the License, or (at your option) any later
11 version.
12
13 This program is distributed in the hope that it will be useful, but WITHOUT
14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
16 more details.
17
18 You should have received a copy of the GNU General Public License along with
19 this program. If not, see <http://www.gnu.org/licenses/>.
20 */
21
22 #include <stdarg.h>
23 #include <stdio.h>
24 #include <string.h>
25
26 #define ___lw_expr_c_seen___
27 #include "lw_alloc.h"
28 #include "lw_expr.h"
29 #include "lw_error.h"
30 #include "lw_string.h"
31
32 static lw_expr_fn_t *evaluate_special = NULL;
33 static lw_expr_fn2_t *evaluate_var = NULL;
34 static lw_expr_fn3_t *parse_term = NULL;
35
36 /* Q&D to break out of infinite recursion */
37 static int level = 0;
38 static int bailing = 0;
39
40 int lw_expr_istype(lw_expr_t e, int t)
41 {
42 if (e -> type == t)
43 return 1;
44 return 0;
45 }
46
47 int lw_expr_intval(lw_expr_t e)
48 {
49 if (e -> type == lw_expr_type_int)
50 return e -> value;
51 return -1;
52 }
53
54 int lw_expr_whichop(lw_expr_t e)
55 {
56 if (e -> type == lw_expr_type_oper)
57 return e -> value;
58 return -1;
59 }
60
61 int lw_expr_specint(lw_expr_t e)
62 {
63 if (e -> type == lw_expr_type_special)
64 return e -> value;
65 return -1;
66 }
67
68 void lw_expr_set_term_parser(lw_expr_fn3_t *fn)
69 {
70 parse_term = fn;
71 }
72
73 void lw_expr_set_special_handler(lw_expr_fn_t *fn)
74 {
75 evaluate_special = fn;
76 }
77
78 void lw_expr_set_var_handler(lw_expr_fn2_t *fn)
79 {
80 evaluate_var = fn;
81 }
82
83 lw_expr_t lw_expr_create(void)
84 {
85 lw_expr_t r;
86
87 r = lw_alloc(sizeof(struct lw_expr_priv));
88 r -> operands = NULL;
89
90 return r;
91 }
92
93 void lw_expr_destroy(lw_expr_t E)
94 {
95 struct lw_expr_opers *o;
96 if (!E)
97 return;
98 while (E -> operands)
99 {
100 o = E -> operands;
101 E -> operands = o -> next;
102 lw_expr_destroy(o -> p);
103 lw_free(o);
104 }
105 if (E -> type == lw_expr_type_var)
106 lw_free(E -> value2);
107 lw_free(E);
108 }
109
110 /* actually duplicates the entire expression */
111 void lw_expr_add_operand(lw_expr_t E, lw_expr_t O);
112 lw_expr_t lw_expr_copy(lw_expr_t E)
113 {
114 lw_expr_t r, t;
115 struct lw_expr_opers *o;
116
117 r = lw_alloc(sizeof(struct lw_expr_priv));
118 *r = *E;
119 r -> operands = NULL;
120
121 if (E -> type == lw_expr_type_var)
122 r -> value2 = lw_strdup(E -> value2);
123 for (o = E -> operands; o; o = o -> next)
124 {
125 lw_expr_add_operand(r, o -> p);
126 }
127
128 return r;
129 }
130
131 void lw_expr_add_operand(lw_expr_t E, lw_expr_t O)
132 {
133 struct lw_expr_opers *o, *t;
134
135 o = lw_alloc(sizeof(struct lw_expr_opers));
136 o -> p = lw_expr_copy(O);
137 o -> next = NULL;
138 for (t = E -> operands; t && t -> next; t = t -> next)
139 /* do nothing */ ;
140
141 if (t)
142 t -> next = o;
143 else
144 E -> operands = o;
145 }
146
147 lw_expr_t lw_expr_build_aux(int exprtype, va_list args)
148 {
149 lw_expr_t r;
150 int t;
151 void *p;
152
153 lw_expr_t te1, te2;
154
155 r = lw_expr_create();
156
157 switch (exprtype)
158 {
159 case lw_expr_type_int:
160 t = va_arg(args, int);
161 r -> type = lw_expr_type_int;
162 r -> value = t;
163 break;
164
165 case lw_expr_type_var:
166 p = va_arg(args, char *);
167 r -> type = lw_expr_type_var;
168 r -> value2 = lw_strdup(p);
169 break;
170
171 case lw_expr_type_special:
172 t = va_arg(args, int);
173 p = va_arg(args, char *);
174 r -> type = lw_expr_type_special;
175 r -> value = t;
176 r -> value2 = p;
177 break;
178
179 case lw_expr_type_oper:
180 t = va_arg(args, int);
181 te1 = va_arg(args, lw_expr_t);
182 if (t != lw_expr_oper_com && t != lw_expr_oper_neg)
183 te2 = va_arg(args, lw_expr_t);
184 else
185 te2 = NULL;
186
187 r -> type = lw_expr_type_oper;
188 r -> value = t;
189 lw_expr_add_operand(r, te1);
190 if (te2)
191 lw_expr_add_operand(r, te2);
192 break;
193
194 default:
195 lw_error("Invalid expression type specified to lw_expr_build");
196 }
197
198 return r;
199 }
200
201 lw_expr_t lw_expr_build(int exprtype, ...)
202 {
203 va_list args;
204 lw_expr_t r;
205
206 va_start(args, exprtype);
207 r = lw_expr_build_aux(exprtype, args);
208 va_end(args);
209 return r;
210 }
211
212 void lw_expr_print_aux(lw_expr_t E, char **obuf, int *buflen, int *bufloc)
213 {
214 struct lw_expr_opers *o;
215 int c = 0;
216 char buf[256];
217
218 if (!E)
219 {
220 strcpy(buf, "(NULL)");
221 return;
222 }
223 for (o = E -> operands; o; o = o -> next)
224 {
225 c++;
226 lw_expr_print_aux(o -> p, obuf, buflen, bufloc);
227 }
228
229 switch (E -> type)
230 {
231 case lw_expr_type_int:
232 if (E -> value < 0)
233 snprintf(buf, 256, "-%#x ", -(E -> value));
234 else
235 snprintf(buf, 256, "%#x ", E -> value);
236 break;
237
238 case lw_expr_type_var:
239 snprintf(buf, 256, "V(%s) ", (char *)(E -> value2));
240 break;
241
242 case lw_expr_type_special:
243 snprintf(buf, 256, "S(%d,%p) ", E -> value, E -> value2);
244 break;
245
246 case lw_expr_type_oper:
247 snprintf(buf, 256, "[%d]", c);
248 switch (E -> value)
249 {
250 case lw_expr_oper_plus:
251 strcat(buf, "+ ");
252 break;
253
254 case lw_expr_oper_minus:
255 strcat(buf, "- ");
256 break;
257
258 case lw_expr_oper_times:
259 strcat(buf, "* ");
260 break;
261
262 case lw_expr_oper_divide:
263 strcat(buf, "/ ");
264 break;
265
266 case lw_expr_oper_mod:
267 strcat(buf, "% ");
268 break;
269
270 case lw_expr_oper_intdiv:
271 strcat(buf, "\\ ");
272 break;
273
274 case lw_expr_oper_bwand:
275 strcat(buf, "BWAND ");
276 break;
277
278 case lw_expr_oper_bwor:
279 strcat(buf, "BWOR ");
280 break;
281
282 case lw_expr_oper_bwxor:
283 strcat(buf, "BWXOR ");
284 break;
285
286 case lw_expr_oper_and:
287 strcat(buf, "AND ");
288 break;
289
290 case lw_expr_oper_or:
291 strcat(buf, "OR ");
292 break;
293
294 case lw_expr_oper_neg:
295 strcat(buf, "NEG ");
296 break;
297
298 case lw_expr_oper_com:
299 strcat(buf, "COM ");
300 break;
301
302 default:
303 strcat(buf, "OPER ");
304 break;
305 }
306 break;
307 default:
308 snprintf(buf, 256, "ERR ");
309 break;
310 }
311
312 c = strlen(buf);
313 if (*bufloc + c >= *buflen)
314 {
315 *buflen += 128;
316 *obuf = lw_realloc(*obuf, *buflen);
317 }
318 strcpy(*obuf + *bufloc, buf);
319 *bufloc += c;
320 }
321
322 char *lw_expr_print(lw_expr_t E)
323 {
324 static char *obuf = NULL;
325 static int obufsize = 0;
326
327 int obufloc = 0;
328
329 lw_expr_print_aux(E, &obuf, &obufsize, &obufloc);
330
331 return obuf;
332 }
333
334 /*
335 Return:
336 nonzero if expressions are the same (identical pointers or matching values)
337 zero if expressions are not the same
338
339 */
340 int lw_expr_compare(lw_expr_t E1, lw_expr_t E2)
341 {
342 struct lw_expr_opers *o1, *o2;
343
344 if (E1 == E2)
345 return 1;
346
347 if (!E1 || !E2)
348 return 0;
349
350 if (!(E1 -> type == E2 -> type && E1 -> value == E2 -> value))
351 return 0;
352
353 if (E1 -> type == lw_expr_type_var)
354 {
355 if (!strcmp(E1 -> value2, E2 -> value2))
356 return 1;
357 else
358 return 0;
359 }
360
361 if (E1 -> type == lw_expr_type_special)
362 {
363 if (E1 -> value2 == E2 -> value2)
364 return 1;
365 else
366 return 0;
367 }
368
369 for (o1 = E1 -> operands, o2 = E2 -> operands; o1 && o2; o1 = o1 -> next, o2 = o2 -> next)
370 if (lw_expr_compare(o1 -> p, o2 -> p) == 0)
371 return 0;
372 if (o1 || o2)
373 return 0;
374
375 return 1;
376 }
377
378 /* return true if E is an operator of type oper */
379 int lw_expr_isoper(lw_expr_t E, int oper)
380 {
381 if (E -> type == lw_expr_type_oper && E -> value == oper)
382 return 1;
383 return 0;
384 }
385
386
387 void lw_expr_simplify_sortconstfirst(lw_expr_t E)
388 {
389 struct lw_expr_opers *o;
390
391 if (E -> type != lw_expr_type_oper)
392 return;
393 if (E -> value != lw_expr_oper_times && E -> value != lw_expr_oper_plus)
394 return;
395
396 for (o = E -> operands; o; o = o -> next)
397 {
398 if (o -> p -> type == lw_expr_type_oper && (o -> p -> value == lw_expr_oper_times || o -> p -> value == lw_expr_oper_plus))
399 lw_expr_simplify_sortconstfirst(o -> p);
400 }
401
402 for (o = E -> operands; o; o = o -> next)
403 {
404 if (o -> p -> type == lw_expr_type_int && o != E -> operands)
405 {
406 struct lw_expr_opers *o2;
407 for (o2 = E -> operands; o2 -> next != o; o2 = o2 -> next)
408 /* do nothing */ ;
409 o2 -> next = o -> next;
410 o -> next = E -> operands;
411 E -> operands = o;
412 o = o2;
413 }
414 }
415 }
416
417 void lw_expr_sortoperandlist(struct lw_expr_opers **o)
418 {
419 // fprintf(stderr, "lw_expr_sortoperandlist() not yet implemented\n");
420 }
421
422 // return 1 if the operand lists match, 0 if not
423 // may re-order the argument lists
424 int lw_expr_simplify_compareoperandlist(struct lw_expr_opers **ol1, struct lw_expr_opers **ol2)
425 {
426 struct lw_expr_opers *o1, *o2;
427
428 lw_expr_sortoperandlist(ol1);
429 lw_expr_sortoperandlist(ol2);
430
431 for (o1 = *ol1, o2 = *ol2; o1 && o2; o1 = o1 -> next, o2 = o2 -> next)
432 {
433 if (!lw_expr_compare(o1 -> p, o2 -> p))
434 return 0;
435 }
436 if (o1 || o2)
437 return 0;
438 return 1;
439 }
440
441 int lw_expr_simplify_isliketerm(lw_expr_t e1, lw_expr_t e2)
442 {
443 // first term is a "times"
444 if (e1 -> type == lw_expr_type_oper && e1 -> value == lw_expr_oper_times)
445 {
446 // second term is a "times"
447 if (e2 -> type == lw_expr_type_oper && e2 -> value == lw_expr_oper_times)
448 {
449 // both times - easy check
450 struct lw_expr_opers *o1, *o2;
451 for (o1 = e1 -> operands; o1; o1 = o1 -> next)
452 if (o1 -> p -> type != lw_expr_type_int)
453 break;
454
455 for (o2 = e2 -> operands; o2; o2 = o2 -> next)
456 if (o2 -> p -> type != lw_expr_type_int)
457 break;
458
459 if (lw_expr_simplify_compareoperandlist(&o1, &o2))
460 return 1;
461 return 0;
462 }
463
464 // not a times - have to assume it's the operand list
465 // with a "1 *" in front if it
466 if (!e1 -> operands -> next)
467 return 0;
468 if (e1 -> operands -> next -> next)
469 return 0;
470 if (!lw_expr_compare(e1 -> operands -> next -> p, e2))
471 return 0;
472 return 1;
473 }
474
475 // e1 is not a times
476 if (e2 -> type == lw_expr_type_oper && e2 -> value == lw_expr_oper_times)
477 {
478 // e2 is a times
479 if (e2 -> operands -> next -> next)
480 return 0;
481 if (!lw_expr_compare(e1, e2 -> operands -> next -> p))
482 return 0;
483 return 1;
484 }
485
486 // neither are times
487 if (!lw_expr_compare(e1, e2))
488 return 0;
489 return 1;
490 }
491
492 int lw_expr_contains(lw_expr_t E, lw_expr_t E1)
493 {
494 struct lw_expr_opers *o;
495
496 // NULL expr contains nothing :)
497 if (!E)
498 return 0;
499
500 if (E1 -> type != lw_expr_type_var && E1 -> type != lw_expr_type_special)
501 return 0;
502
503 if (lw_expr_compare(E, E1))
504 return 1;
505
506 for (o = E -> operands; o; o = o -> next)
507 {
508 if (lw_expr_contains(o -> p, E1))
509 return 1;
510 }
511 return 0;
512 }
513
514 void lw_expr_simplify_l(lw_expr_t E, void *priv);
515
516 void lw_expr_simplify_go(lw_expr_t E, void *priv)
517 {
518 struct lw_expr_opers *o;
519
520 // replace subtraction with O1 + -1(O2)...
521 // needed for like term collection
522 if (E -> type == lw_expr_type_oper && E -> value == lw_expr_oper_minus)
523 {
524 for (o = E -> operands -> next; o; o = o -> next)
525 {
526 lw_expr_t e1, e2;
527
528 e2 = lw_expr_build(lw_expr_type_int, -1);
529 e1 = lw_expr_build(lw_expr_type_oper, lw_expr_oper_times, e2, o -> p);
530 lw_expr_destroy(o -> p);
531 lw_expr_destroy(e2);
532 o -> p = e1;
533 }
534 E -> value = lw_expr_oper_plus;
535 }
536
537 // turn "NEG" into -1(O) - needed for like term collection
538 if (E -> type == lw_expr_type_oper && E -> value == lw_expr_oper_neg)
539 {
540 lw_expr_t e1;
541
542 E -> value = lw_expr_oper_times;
543 e1 = lw_expr_build(lw_expr_type_int, -1);
544 lw_expr_add_operand(E, e1);
545 lw_expr_destroy(e1);
546 }
547
548 again:
549 // try to resolve non-constant terms to constants here
550 if (E -> type == lw_expr_type_special && evaluate_special)
551 {
552 lw_expr_t te;
553
554 te = evaluate_special(E -> value, E -> value2, priv);
555 if (lw_expr_contains(te, E))
556 lw_expr_destroy(te);
557 if (te)
558 {
559 for (o = E -> operands; o; o = o -> next)
560 lw_expr_destroy(o -> p);
561 if (E -> type == lw_expr_type_var)
562 lw_free(E -> value2);
563 *E = *te;
564 E -> operands = NULL;
565
566 if (te -> type == lw_expr_type_var)
567 E -> value2 = lw_strdup(te -> value2);
568 for (o = te -> operands; o; o = o -> next)
569 {
570 lw_expr_add_operand(E, lw_expr_copy(o -> p));
571 }
572 lw_expr_destroy(te);
573 goto again;
574 }
575 return;
576 }
577
578 if (E -> type == lw_expr_type_var && evaluate_var)
579 {
580 lw_expr_t te;
581
582 te = evaluate_var(E -> value2, priv);
583 if (lw_expr_contains(te, E))
584 lw_expr_destroy(te);
585 else if (te)
586 {
587 for (o = E -> operands; o; o = o -> next)
588 lw_expr_destroy(o -> p);
589 if (E -> type == lw_expr_type_var)
590 lw_free(E -> value2);
591 *E = *te;
592 E -> operands = NULL;
593
594 if (te -> type == lw_expr_type_var)
595 E -> value2 = lw_strdup(te -> value2);
596 for (o = te -> operands; o; o = o -> next)
597 {
598 lw_expr_add_operand(E, lw_expr_copy(o -> p));
599 }
600 lw_expr_destroy(te);
601 goto again;
602 }
603 return;
604 }
605
606 // non-operators have no simplification to do!
607 if (E -> type != lw_expr_type_oper)
608 return;
609
610 // merge plus operations
611 if (E -> value == lw_expr_oper_plus)
612 {
613 lw_expr_t e2;
614
615 tryagainplus:
616 for (o = E -> operands; o; o = o -> next)
617 {
618 if (o -> p -> type == lw_expr_type_oper && o -> p -> value == lw_expr_oper_plus)
619 {
620 struct lw_expr_opers *o2, *o3;
621 // we have a + operation - bring operands up
622
623 for (o2 = E -> operands; o2 && o2 -> next != o; o2 = o2 -> next)
624 /* do nothing */ ;
625 if (o2)
626 o2 -> next = o -> p -> operands;
627 else
628 E -> operands = o -> p -> operands;
629 for (o2 = o -> p -> operands; o2 -> next; o2 = o2 -> next)
630 /* do nothing */ ;
631 o2 -> next = o -> next;
632 o -> p -> operands = NULL;
633 lw_expr_destroy(o -> p);
634 lw_free(o);
635 goto tryagainplus;
636 }
637 }
638 }
639
640 // merge times operations
641 if (E -> value == lw_expr_oper_times)
642 {
643 lw_expr_t e2;
644
645 tryagaintimes:
646 for (o = E -> operands; o; o = o -> next)
647 {
648 if (o -> p -> type == lw_expr_type_oper && o -> p -> value == lw_expr_oper_times)
649 {
650 struct lw_expr_opers *o2, *o3;
651 // we have a + operation - bring operands up
652
653 for (o2 = E -> operands; o2 && o2 -> next != o; o2 = o2 -> next)
654 /* do nothing */ ;
655 if (o2)
656 o2 -> next = o -> p -> operands;
657 else
658 E -> operands = o -> p -> operands;
659 for (o2 = o -> p -> operands; o2 -> next; o2 = o2 -> next)
660 /* do nothing */ ;
661 o2 -> next = o -> next;
662 o -> p -> operands = NULL;
663 lw_expr_destroy(o -> p);
664 lw_free(o);
665 goto tryagaintimes;
666 }
667 }
668 }
669
670 // simplify operands
671 for (o = E -> operands; o; o = o -> next)
672 lw_expr_simplify_l(o -> p, priv);
673
674 for (o = E -> operands; o; o = o -> next)
675 {
676 if (o -> p -> type != lw_expr_type_int)
677 break;
678 }
679
680 if (!o)
681 {
682 // we can do the operation here!
683 int tr = -42424242;
684
685 switch (E -> value)
686 {
687 case lw_expr_oper_neg:
688 tr = -(E -> operands -> p -> value);
689 break;
690
691 case lw_expr_oper_com:
692 tr = ~(E -> operands -> p -> value);
693 break;
694
695 case lw_expr_oper_plus:
696 tr = E -> operands -> p -> value;
697 for (o = E -> operands -> next; o; o = o -> next)
698 tr += o -> p -> value;
699 break;
700
701 case lw_expr_oper_minus:
702 tr = E -> operands -> p -> value;
703 for (o = E -> operands -> next; o; o = o -> next)
704 tr -= o -> p -> value;
705 break;
706
707 case lw_expr_oper_times:
708 tr = E -> operands -> p -> value;
709 for (o = E -> operands -> next; o; o = o -> next)
710 tr *= o -> p -> value;
711 break;
712
713 case lw_expr_oper_divide:
714 tr = E -> operands -> p -> value / E -> operands -> next -> p -> value;
715 break;
716
717 case lw_expr_oper_mod:
718 tr = E -> operands -> p -> value % E -> operands -> next -> p -> value;
719 break;
720
721 case lw_expr_oper_intdiv:
722 tr = E -> operands -> p -> value / E -> operands -> next -> p -> value;
723 break;
724
725 case lw_expr_oper_bwand:
726 tr = E -> operands -> p -> value & E -> operands -> next -> p -> value;
727 break;
728
729 case lw_expr_oper_bwor:
730 tr = E -> operands -> p -> value | E -> operands -> next -> p -> value;
731 break;
732
733 case lw_expr_oper_bwxor:
734 tr = E -> operands -> p -> value ^ E -> operands -> next -> p -> value;
735 break;
736
737 case lw_expr_oper_and:
738 tr = E -> operands -> p -> value && E -> operands -> next -> p -> value;
739 break;
740
741 case lw_expr_oper_or:
742 tr = E -> operands -> p -> value || E -> operands -> next -> p -> value;
743 break;
744
745 }
746
747 while (E -> operands)
748 {
749 o = E -> operands;
750 E -> operands = o -> next;
751 lw_expr_destroy(o -> p);
752 lw_free(o);
753 }
754 E -> type = lw_expr_type_int;
755 E -> value = tr;
756 return;
757 }
758
759 if (E -> value == lw_expr_oper_plus)
760 {
761 lw_expr_t e1;
762 int cval = 0;
763
764 e1 = lw_expr_create();
765 e1 -> operands = E -> operands;
766 E -> operands = 0;
767
768 for (o = e1 -> operands; o; o = o -> next)
769 {
770 if (o -> p -> type == lw_expr_type_int)
771 cval += o -> p -> value;
772 else
773 lw_expr_add_operand(E, o -> p);
774 }
775 lw_expr_destroy(e1);
776 if (cval)
777 {
778 e1 = lw_expr_build(lw_expr_type_int, cval);
779 lw_expr_add_operand(E, e1);
780 lw_expr_destroy(e1);
781 }
782 }
783
784 if (E -> value == lw_expr_oper_times)
785 {
786 lw_expr_t e1;
787 int cval = 1;
788
789 e1 = lw_expr_create();
790 e1 -> operands = E -> operands;
791 E -> operands = 0;
792
793 for (o = e1 -> operands; o; o = o -> next)
794 {
795 if (o -> p -> type == lw_expr_type_int)
796 cval *= o -> p -> value;
797 else
798 lw_expr_add_operand(E, o -> p);
799 }
800 lw_expr_destroy(e1);
801 if (cval != 1)
802 {
803 e1 = lw_expr_build(lw_expr_type_int, cval);
804 lw_expr_add_operand(E, e1);
805 lw_expr_destroy(e1);
806 }
807 }
808
809 if (E -> value == lw_expr_oper_times)
810 {
811 for (o = E -> operands; o; o = o -> next)
812 {
813 if (o -> p -> type == lw_expr_type_int && o -> p -> value == 0)
814 {
815 // one operand of times is 0, replace operation with 0
816 while (E -> operands)
817 {
818 o = E -> operands;
819 E -> operands = o -> next;
820 lw_expr_destroy(o -> p);
821 lw_free(o);
822 }
823 E -> type = lw_expr_type_int;
824 E -> value = 0;
825 return;
826 }
827 }
828 }
829
830 // sort "constants" to the start of each operand list for + and *
831 if (E -> value == lw_expr_oper_plus || E -> value == lw_expr_oper_times)
832 lw_expr_simplify_sortconstfirst(E);
833
834 // look for like terms and collect them together
835 if (E -> value == lw_expr_oper_plus)
836 {
837 struct lw_expr_opers *o2;
838 for (o = E -> operands; o; o = o -> next)
839 {
840 // skip constants
841 if (o -> p -> type == lw_expr_type_int)
842 continue;
843
844 // we have a term to match
845 // (o -> p) is first term
846 for (o2 = o -> next; o2; o2 = o2 -> next)
847 {
848 lw_expr_t e1, e2;
849
850 if (o2 -> p -> type == lw_expr_type_int)
851 continue;
852
853 if (lw_expr_simplify_isliketerm(o -> p, o2 -> p))
854 {
855 int coef, coef2;
856
857 // we have a like term here
858 // do something about it
859 if (o -> p -> type == lw_expr_type_oper && o -> p -> value == lw_expr_oper_times)
860 {
861 if (o -> p -> operands -> p -> type == lw_expr_type_int)
862 coef = o -> p -> operands -> p -> value;
863 else
864 coef = 1;
865 }
866 else
867 coef = 1;
868 if (o2 -> p -> type == lw_expr_type_oper && o2 -> p -> value == lw_expr_oper_times)
869 {
870 if (o2 -> p -> operands -> p -> type == lw_expr_type_int)
871 coef2 = o2 -> p -> operands -> p -> value;
872 else
873 coef2 = 1;
874 }
875 else
876 coef2 = 1;
877 coef += coef2;
878 e1 = lw_expr_create();
879 e1 -> type = lw_expr_type_oper;
880 e1 -> value = lw_expr_oper_times;
881 if (coef != 1)
882 {
883 e2 = lw_expr_build(lw_expr_type_int, coef);
884 lw_expr_add_operand(e1, e2);
885 lw_expr_destroy(e2);
886 }
887 lw_expr_destroy(o -> p);
888 o -> p = e1;
889 for (o = o2 -> p -> operands; o; o = o -> next)
890 {
891 if (o -> p -> type == lw_expr_type_int)
892 continue;
893 lw_expr_add_operand(e1, o -> p);
894 }
895 lw_expr_destroy(o2 -> p);
896 o2 -> p = lw_expr_build(lw_expr_type_int, 0);
897 goto again;
898 }
899 }
900 }
901 }
902
903
904 if (E -> value == lw_expr_oper_plus)
905 {
906 int c = 0, t = 0;
907 for (o = E -> operands; o; o = o -> next)
908 {
909 t++;
910 if (!(o -> p -> type == lw_expr_type_int && o -> p -> value == 0))
911 {
912 c++;
913 }
914 }
915 if (c == 1)
916 {
917 lw_expr_t r;
918 // find the value and "move it up"
919 while (E -> operands)
920 {
921 o = E -> operands;
922 if (o -> p -> type != lw_expr_type_int || o -> p -> value != 0)
923 {
924 r = lw_expr_copy(o -> p);
925 }
926 E -> operands = o -> next;
927 lw_expr_destroy(o -> p);
928 lw_free(o);
929 }
930 *E = *r;
931 return;
932 }
933 else if (c == 0)
934 {
935 // replace with 0
936 while (E -> operands)
937 {
938 o = E -> operands;
939 E -> operands = o -> next;
940 lw_expr_destroy(o -> p);
941 lw_free(o);
942 }
943 E -> type = lw_expr_type_int;
944 E -> value = 0;
945 return;
946 }
947 else if (c != t)
948 {
949 // collapse out zero terms
950 struct lw_expr_opers *o2;
951
952 for (o = E -> operands; o; o = o -> next)
953 {
954 if (o -> p -> type == lw_expr_type_int && o -> p -> value == 0)
955 {
956 if (o == E -> operands)
957 {
958 E -> operands = o -> next;
959 lw_expr_destroy(o -> p);
960 lw_free(o);
961 o = E -> operands;
962 }
963 else
964 {
965 for (o2 = E -> operands; o2 -> next == o; o2 = o2 -> next)
966 /* do nothing */ ;
967 o2 -> next = o -> next;
968 lw_expr_destroy(o -> p);
969 lw_free(o);
970 o = o2;
971 }
972 }
973 }
974 }
975 return;
976 }
977
978 /* handle <int> times <plus> - expand the terms - only with exactly two operands */
979 if (E -> value == lw_expr_oper_times)
980 {
981 lw_expr_t t1;
982 lw_expr_t E2;
983 lw_expr_t E3;
984 if (E -> operands && E -> operands -> next && !(E -> operands -> next -> next))
985 {
986 if (E -> operands -> p -> type == lw_expr_type_int)
987 {
988 /* <int> TIMES <other> */
989 E2 = E -> operands -> next -> p;
990 E3 = E -> operands -> p;
991 if (E2 -> type == lw_expr_type_oper && E2 -> value == lw_expr_oper_plus)
992 {
993 lw_free(E -> operands -> next);
994 lw_free(E -> operands);
995 E -> operands = NULL;
996 E -> value = lw_expr_oper_plus;
997
998 for (o = E2 -> operands; o; o = o -> next)
999 {
1000 t1 = lw_expr_build(lw_expr_type_oper, lw_expr_oper_times, E3, o -> p);
1001 lw_expr_add_operand(E, t1);
1002 }
1003
1004 lw_expr_destroy(E2);
1005 lw_expr_destroy(E3);
1006 }
1007 }
1008 else if (E -> operands -> next -> p -> type == lw_expr_type_int)
1009 {
1010 /* <other> TIMES <int> */
1011 E2 = E -> operands -> p;
1012 E3 = E -> operands -> next -> p;
1013 if (E2 -> type == lw_expr_type_oper && E2 -> value == lw_expr_oper_plus)
1014 {
1015 lw_free(E -> operands -> next);
1016 lw_free(E -> operands);
1017 E -> operands = NULL;
1018 E -> value = lw_expr_oper_plus;
1019
1020 for (o = E2 -> operands; o; o = o -> next)
1021 {
1022 t1 = lw_expr_build(lw_expr_type_oper, lw_expr_oper_times, E3, o -> p);
1023 lw_expr_add_operand(E, t1);
1024 }
1025
1026 lw_expr_destroy(E2);
1027 lw_expr_destroy(E3);
1028 }
1029 }
1030 }
1031 }
1032 }
1033
1034 void lw_expr_simplify_l(lw_expr_t E, void *priv)
1035 {
1036 lw_expr_t te;
1037 int c;
1038
1039 (level)++;
1040 // bail out if the level gets too deep
1041 if (level >= 500 || bailing)
1042 {
1043 bailing = 1;
1044 level--;
1045 if (level == 0)
1046 bailing = 0;
1047 return;
1048 }
1049 do
1050 {
1051 te = lw_expr_copy(E);
1052 lw_expr_simplify_go(E, priv);
1053 c = 0;
1054 if (lw_expr_compare(te, E) == 0)
1055 c = 1;
1056 lw_expr_destroy(te);
1057 }
1058 while (c);
1059 (level)--;
1060 }
1061
1062 void lw_expr_simplify(lw_expr_t E, void *priv)
1063 {
1064 lw_expr_simplify_l(E, priv);
1065 }
1066
1067 /*
1068
1069 The following two functions are co-routines which evaluate an infix
1070 expression. lw_expr_parse_term checks for unary prefix operators then, if
1071 none found, passes the string off the the defined helper function to
1072 determine what the term really is. It also handles parentheses.
1073
1074 lw_expr_parse_expr evaluates actual expressions with infix operators. It
1075 respects the order of operations.
1076
1077 The end of an expression is determined by the presence of any of the
1078 following conditions:
1079
1080 1. a NUL character
1081 2. a whitespace character
1082 3. a )
1083 4. a ,
1084 5. any character that is not recognized as a term
1085
1086 lw_expr_parse_term returns NULL if there is no term (end of expr, etc.)
1087
1088 lw_expr_parse_expr returns NULL if there is no expression or on a syntax
1089 error.
1090
1091 */
1092
1093 lw_expr_t lw_expr_parse_expr(char **p, void *priv, int prec);
1094
1095 lw_expr_t lw_expr_parse_term(char **p, void *priv)
1096 {
1097 lw_expr_t term, term2;
1098
1099 eval_next:
1100 if (!**p || isspace(**p) || **p == ')' || **p == ']')
1101 return NULL;
1102
1103 // parentheses
1104 if (**p == '(')
1105 {
1106 (*p)++;
1107 term = lw_expr_parse_expr(p, priv, 0);
1108 if (**p != ')')
1109 {
1110 lw_expr_destroy(term);
1111 return NULL;
1112 }
1113 (*p)++;
1114 return term;
1115 }
1116
1117 // unary +
1118 if (**p == '+')
1119 {
1120 (*p)++;
1121 goto eval_next;
1122 }
1123
1124 // unary - (prec 200)
1125 if (**p == '-')
1126 {
1127 (*p)++;
1128 term = lw_expr_parse_expr(p, priv, 200);
1129 if (!term)
1130 return NULL;
1131
1132 term2 = lw_expr_build(lw_expr_type_oper, lw_expr_oper_neg, term);
1133 lw_expr_destroy(term);
1134 return term2;
1135 }
1136
1137 // unary ^ or ~ (complement, prec 200)
1138 if (**p == '^' || **p == '~')
1139 {
1140 (*p)++;
1141 term = lw_expr_parse_expr(p, priv, 200);
1142 if (!term)
1143 return NULL;
1144
1145 term2 = lw_expr_build(lw_expr_type_oper, lw_expr_oper_com, term);
1146 lw_expr_destroy(term);
1147 return term2;
1148 }
1149
1150 // non-operator - pass to caller
1151 return parse_term(p, priv);
1152 }
1153
1154 lw_expr_t lw_expr_parse_expr(char **p, void *priv, int prec)
1155 {
1156 static const struct operinfo
1157 {
1158 int opernum;
1159 char *operstr;
1160 int operprec;
1161 } operators[] =
1162 {
1163 { lw_expr_oper_plus, "+", 100 },
1164 { lw_expr_oper_minus, "-", 100 },
1165 { lw_expr_oper_times, "*", 150 },
1166 { lw_expr_oper_divide, "/", 150 },
1167 { lw_expr_oper_mod, "%", 150 },
1168 { lw_expr_oper_intdiv, "\\", 150 },
1169
1170 { lw_expr_oper_and, "&&", 25 },
1171 { lw_expr_oper_or, "||", 25 },
1172
1173 { lw_expr_oper_bwand, "&", 50 },
1174 { lw_expr_oper_bwor, "|", 50 },
1175 { lw_expr_oper_bwxor, "^", 50 },
1176
1177 { lw_expr_oper_none, "", 0 }
1178 };
1179
1180 int opern, i;
1181 lw_expr_t term1, term2, term3;
1182
1183 if (!**p || isspace(**p) || **p == ')' || **p == ',' || **p == ']')
1184 return NULL;
1185
1186 term1 = lw_expr_parse_term(p, priv);
1187 if (!term1)
1188 return NULL;
1189
1190 eval_next:
1191 if (!**p || isspace(**p) || **p == ')' || **p == ',' || **p == ']')
1192 return term1;
1193
1194 // expecting an operator here
1195 for (opern = 0; operators[opern].opernum != lw_expr_oper_none; opern++)
1196 {
1197 for (i = 0; (*p)[i] && operators[opern].operstr[i] && ((*p)[i] == operators[opern].operstr[i]); i++)
1198 /* do nothing */;
1199 if (operators[opern].operstr[i] == '\0')
1200 break;
1201 }
1202
1203 if (operators[opern].opernum == lw_expr_oper_none)
1204 {
1205 // unrecognized operator
1206 lw_expr_destroy(term1);
1207 return NULL;
1208 }
1209
1210 // operator number is in opern, length of oper in i
1211
1212 // logic:
1213 // if the precedence of this operation is <= to the "prec" flag,
1214 // we simply return without advancing the input pointer; the operator
1215 // will be evaluated again in the enclosing function call
1216 if (operators[opern].operprec <= prec)
1217 return term1;
1218
1219 // logic:
1220 // we have a higher precedence operator here so we will advance the
1221 // input pointer to the next term and let the expression evaluator
1222 // loose on it after which time we will push our operator onto the
1223 // stack and then go on with the expression evaluation
1224 (*p) += i;
1225
1226 // evaluate next expression(s) of higher precedence
1227 term2 = lw_expr_parse_expr(p, priv, operators[opern].operprec);
1228 if (!term2)
1229 {
1230 lw_expr_destroy(term1);
1231 return NULL;
1232 }
1233
1234 // now create operator
1235 term3 = lw_expr_build(lw_expr_type_oper, operators[opern].opernum, term1, term2);
1236 lw_expr_destroy(term1);
1237 lw_expr_destroy(term2);
1238
1239 // the new "expression" is the next "left operand"
1240 term1 = term3;
1241
1242 // continue evaluating
1243 goto eval_next;
1244 }
1245
1246 lw_expr_t lw_expr_parse(char **p, void *priv)
1247 {
1248 return lw_expr_parse_expr(p, priv, 0);
1249 }
1250
1251 int lw_expr_testterms(lw_expr_t e, lw_expr_testfn_t *fn, void *priv)
1252 {
1253 struct lw_expr_opers *o;
1254 int r;
1255
1256 for (o = e -> operands; o; o = o -> next)
1257 {
1258 r = lw_expr_testterms(o -> p, fn, priv);
1259 if (r)
1260 return r;
1261 }
1262 return (fn)(e, priv);
1263 }
1264
1265 int lw_expr_type(lw_expr_t e)
1266 {
1267 return e -> type;
1268 }
1269
1270 void *lw_expr_specptr(lw_expr_t e)
1271 {
1272 return e -> value2;
1273 }