2 * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org>
3 * Released under the terms of the GNU GPL v2.0.
10 #define LKC_DIRECT_LINK
13 struct expr *expr_alloc_symbol(struct symbol *sym)
15 struct expr *e = malloc(sizeof(*e));
16 memset(e, 0, sizeof(*e));
22 struct expr *expr_alloc_one(enum expr_type type, struct expr *ce)
24 struct expr *e = malloc(sizeof(*e));
25 memset(e, 0, sizeof(*e));
31 struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e2)
33 struct expr *e = malloc(sizeof(*e));
34 memset(e, 0, sizeof(*e));
41 struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2)
43 struct expr *e = malloc(sizeof(*e));
44 memset(e, 0, sizeof(*e));
51 struct expr *expr_alloc_and(struct expr *e1, struct expr *e2)
55 return e2 ? expr_alloc_two(E_AND, e1, e2) : e1;
58 struct expr *expr_copy(struct expr *org)
65 e = malloc(sizeof(*org));
66 memcpy(e, org, sizeof(*org));
72 e->left.expr = expr_copy(org->left.expr);
76 e->left.sym = org->left.sym;
77 e->right.sym = org->right.sym;
82 e->left.expr = expr_copy(org->left.expr);
83 e->right.expr = expr_copy(org->right.expr);
86 printf("can't copy type %d\n", e->type);
95 void expr_free(struct expr *e)
104 expr_free(e->left.expr);
111 expr_free(e->left.expr);
112 expr_free(e->right.expr);
115 printf("how to free type %d?\n", e->type);
121 static int trans_count;
126 static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2)
128 if (e1->type == type) {
129 __expr_eliminate_eq(type, &e1->left.expr, &e2);
130 __expr_eliminate_eq(type, &e1->right.expr, &e2);
133 if (e2->type == type) {
134 __expr_eliminate_eq(type, &e1, &e2->left.expr);
135 __expr_eliminate_eq(type, &e1, &e2->right.expr);
138 if (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
139 e1->left.sym == e2->left.sym && (e1->left.sym->flags & (SYMBOL_YES|SYMBOL_NO)))
141 if (!expr_eq(e1, e2))
144 expr_free(e1); expr_free(e2);
147 e1 = expr_alloc_symbol(&symbol_no);
148 e2 = expr_alloc_symbol(&symbol_no);
151 e1 = expr_alloc_symbol(&symbol_yes);
152 e2 = expr_alloc_symbol(&symbol_yes);
159 void expr_eliminate_eq(struct expr **ep1, struct expr **ep2)
161 if (!e1 || !e2 || e1->type != e2->type)
163 __expr_eliminate_eq(e1->type, ep1, ep2);
164 e1 = expr_eliminate_yn(e1);
165 e2 = expr_eliminate_yn(e2);
171 int expr_eq(struct expr *e1, struct expr *e2)
175 if (e1->type != e2->type)
180 return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym;
182 return e1->left.sym == e2->left.sym;
184 return expr_eq(e1->left.expr, e2->left.expr);
189 old_count = trans_count;
190 expr_eliminate_eq(&e1, &e2);
191 res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
192 e1->left.sym == e2->left.sym);
195 trans_count = old_count;
202 print_expr(0, e1, 0);
204 print_expr(0, e2, 0);
210 struct expr *expr_eliminate_yn(struct expr *e)
214 if (e) switch (e->type) {
216 e->left.expr = expr_eliminate_yn(e->left.expr);
217 e->right.expr = expr_eliminate_yn(e->right.expr);
218 if (e->left.expr->type == E_SYMBOL) {
219 if (e->left.expr->left.sym == &symbol_no) {
220 expr_free(e->left.expr);
221 expr_free(e->right.expr);
223 e->left.sym = &symbol_no;
224 e->right.expr = NULL;
226 } else if (e->left.expr->left.sym == &symbol_yes) {
229 *e = *(e->right.expr);
234 if (e->right.expr->type == E_SYMBOL) {
235 if (e->right.expr->left.sym == &symbol_no) {
236 expr_free(e->left.expr);
237 expr_free(e->right.expr);
239 e->left.sym = &symbol_no;
240 e->right.expr = NULL;
242 } else if (e->right.expr->left.sym == &symbol_yes) {
245 *e = *(e->left.expr);
252 e->left.expr = expr_eliminate_yn(e->left.expr);
253 e->right.expr = expr_eliminate_yn(e->right.expr);
254 if (e->left.expr->type == E_SYMBOL) {
255 if (e->left.expr->left.sym == &symbol_no) {
258 *e = *(e->right.expr);
261 } else if (e->left.expr->left.sym == &symbol_yes) {
262 expr_free(e->left.expr);
263 expr_free(e->right.expr);
265 e->left.sym = &symbol_yes;
266 e->right.expr = NULL;
270 if (e->right.expr->type == E_SYMBOL) {
271 if (e->right.expr->left.sym == &symbol_no) {
274 *e = *(e->left.expr);
277 } else if (e->right.expr->left.sym == &symbol_yes) {
278 expr_free(e->left.expr);
279 expr_free(e->right.expr);
281 e->left.sym = &symbol_yes;
282 e->right.expr = NULL;
296 struct expr *expr_trans_bool(struct expr *e)
304 e->left.expr = expr_trans_bool(e->left.expr);
305 e->right.expr = expr_trans_bool(e->right.expr);
309 if (e->left.sym->type == S_TRISTATE) {
310 if (e->right.sym == &symbol_no) {
325 struct expr *expr_join_or(struct expr *e1, struct expr *e2)
328 struct symbol *sym1, *sym2;
331 return expr_copy(e1);
332 if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
334 if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
336 if (e1->type == E_NOT) {
338 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
340 sym1 = tmp->left.sym;
343 if (e2->type == E_NOT) {
344 if (e2->left.expr->type != E_SYMBOL)
346 sym2 = e2->left.expr->left.sym;
351 if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
353 if (sym1->type == S_TRISTATE) {
354 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
355 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
356 (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) {
357 // (a='y') || (a='m') -> (a!='n')
358 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no);
360 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
361 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
362 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) {
363 // (a='y') || (a='n') -> (a!='m')
364 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod);
366 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
367 ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
368 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) {
369 // (a='m') || (a='n') -> (a!='y')
370 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes);
373 if (sym1->type == S_BOOLEAN && sym1 == sym2) {
374 if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) ||
375 (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL))
376 return expr_alloc_symbol(&symbol_yes);
380 print_expr(0, e1, 0);
382 print_expr(0, e2, 0);
387 struct expr *expr_join_and(struct expr *e1, struct expr *e2)
390 struct symbol *sym1, *sym2;
393 return expr_copy(e1);
394 if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
396 if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
398 if (e1->type == E_NOT) {
400 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
402 sym1 = tmp->left.sym;
405 if (e2->type == E_NOT) {
406 if (e2->left.expr->type != E_SYMBOL)
408 sym2 = e2->left.expr->left.sym;
413 if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
416 if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) ||
417 (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes))
418 // (a) && (a='y') -> (a='y')
419 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
421 if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) ||
422 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no))
423 // (a) && (a!='n') -> (a)
424 return expr_alloc_symbol(sym1);
426 if (sym1->type == S_TRISTATE) {
427 if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) {
428 // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
429 sym2 = e1->right.sym;
430 if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
431 return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
432 : expr_alloc_symbol(&symbol_no);
434 if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) {
435 // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
436 sym2 = e2->right.sym;
437 if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
438 return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
439 : expr_alloc_symbol(&symbol_no);
441 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
442 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
443 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes)))
444 // (a!='y') && (a!='n') -> (a='m')
445 return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod);
447 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
448 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
449 (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes)))
450 // (a!='y') && (a!='m') -> (a='n')
451 return expr_alloc_comp(E_EQUAL, sym1, &symbol_no);
453 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
454 ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
455 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod)))
456 // (a!='m') && (a!='n') -> (a='m')
457 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
459 if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) ||
460 (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) ||
461 (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) ||
462 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes))
466 print_expr(0, e1, 0);
468 print_expr(0, e2, 0);
473 static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2)
479 if (e1->type == type) {
480 expr_eliminate_dups1(type, &e1->left.expr, &e2);
481 expr_eliminate_dups1(type, &e1->right.expr, &e2);
484 if (e2->type == type) {
485 expr_eliminate_dups1(type, &e1, &e2->left.expr);
486 expr_eliminate_dups1(type, &e1, &e2->right.expr);
493 case E_OR: case E_AND:
494 expr_eliminate_dups1(e1->type, &e1, &e1);
501 tmp = expr_join_or(e1, e2);
503 expr_free(e1); expr_free(e2);
504 e1 = expr_alloc_symbol(&symbol_no);
510 tmp = expr_join_and(e1, e2);
512 expr_free(e1); expr_free(e2);
513 e1 = expr_alloc_symbol(&symbol_yes);
525 static void expr_eliminate_dups2(enum expr_type type, struct expr **ep1, struct expr **ep2)
529 struct expr *tmp, *tmp1, *tmp2;
531 if (e1->type == type) {
532 expr_eliminate_dups2(type, &e1->left.expr, &e2);
533 expr_eliminate_dups2(type, &e1->right.expr, &e2);
536 if (e2->type == type) {
537 expr_eliminate_dups2(type, &e1, &e2->left.expr);
538 expr_eliminate_dups2(type, &e1, &e2->right.expr);
545 expr_eliminate_dups2(e1->type, &e1, &e1);
546 // (FOO || BAR) && (!FOO && !BAR) -> n
547 tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1)));
548 tmp2 = expr_copy(e2);
549 tmp = expr_extract_eq_and(&tmp1, &tmp2);
550 if (expr_is_yes(tmp1)) {
552 e1 = expr_alloc_symbol(&symbol_no);
560 expr_eliminate_dups2(e1->type, &e1, &e1);
561 // (FOO && BAR) || (!FOO || !BAR) -> y
562 tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1)));
563 tmp2 = expr_copy(e2);
564 tmp = expr_extract_eq_or(&tmp1, &tmp2);
565 if (expr_is_no(tmp1)) {
567 e1 = expr_alloc_symbol(&symbol_yes);
581 struct expr *expr_eliminate_dups(struct expr *e)
587 oldcount = trans_count;
591 case E_OR: case E_AND:
592 expr_eliminate_dups1(e->type, &e, &e);
593 expr_eliminate_dups2(e->type, &e, &e);
599 e = expr_eliminate_yn(e);
601 trans_count = oldcount;
605 struct expr *expr_transform(struct expr *e)
618 e->left.expr = expr_transform(e->left.expr);
619 e->right.expr = expr_transform(e->right.expr);
624 if (e->left.sym->type != S_BOOLEAN)
626 if (e->right.sym == &symbol_no) {
628 e->left.expr = expr_alloc_symbol(e->left.sym);
632 if (e->right.sym == &symbol_mod) {
633 printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name);
635 e->left.sym = &symbol_no;
639 if (e->right.sym == &symbol_yes) {
646 if (e->left.sym->type != S_BOOLEAN)
648 if (e->right.sym == &symbol_no) {
653 if (e->right.sym == &symbol_mod) {
654 printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name);
656 e->left.sym = &symbol_yes;
660 if (e->right.sym == &symbol_yes) {
662 e->left.expr = expr_alloc_symbol(e->left.sym);
668 switch (e->left.expr->type) {
671 tmp = e->left.expr->left.expr;
675 e = expr_transform(e);
683 e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL;
686 // !(a || b) -> !a && !b
689 e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
691 tmp->right.expr = NULL;
692 e = expr_transform(e);
695 // !(a && b) -> !a || !b
698 e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
700 tmp->right.expr = NULL;
701 e = expr_transform(e);
704 if (e->left.expr->left.sym == &symbol_yes) {
710 e->left.sym = &symbol_no;
713 if (e->left.expr->left.sym == &symbol_mod) {
719 e->left.sym = &symbol_mod;
722 if (e->left.expr->left.sym == &symbol_no) {
728 e->left.sym = &symbol_yes;
742 int expr_contains_symbol(struct expr *dep, struct symbol *sym)
750 return expr_contains_symbol(dep->left.expr, sym) ||
751 expr_contains_symbol(dep->right.expr, sym);
753 return dep->left.sym == sym;
756 return dep->left.sym == sym ||
757 dep->right.sym == sym;
759 return expr_contains_symbol(dep->left.expr, sym);
766 bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
773 return expr_depends_symbol(dep->left.expr, sym) ||
774 expr_depends_symbol(dep->right.expr, sym);
776 return dep->left.sym == sym;
778 if (dep->left.sym == sym) {
779 if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod)
784 if (dep->left.sym == sym) {
785 if (dep->right.sym == &symbol_no)
795 struct expr *expr_extract_eq_and(struct expr **ep1, struct expr **ep2)
797 struct expr *tmp = NULL;
798 expr_extract_eq(E_AND, &tmp, ep1, ep2);
800 *ep1 = expr_eliminate_yn(*ep1);
801 *ep2 = expr_eliminate_yn(*ep2);
806 struct expr *expr_extract_eq_or(struct expr **ep1, struct expr **ep2)
808 struct expr *tmp = NULL;
809 expr_extract_eq(E_OR, &tmp, ep1, ep2);
811 *ep1 = expr_eliminate_yn(*ep1);
812 *ep2 = expr_eliminate_yn(*ep2);
817 void expr_extract_eq(enum expr_type type, struct expr **ep, struct expr **ep1, struct expr **ep2)
821 if (e1->type == type) {
822 expr_extract_eq(type, ep, &e1->left.expr, &e2);
823 expr_extract_eq(type, ep, &e1->right.expr, &e2);
826 if (e2->type == type) {
827 expr_extract_eq(type, ep, ep1, &e2->left.expr);
828 expr_extract_eq(type, ep, ep1, &e2->right.expr);
831 if (expr_eq(e1, e2)) {
832 *ep = *ep ? expr_alloc_two(type, *ep, e1) : e1;
835 e1 = expr_alloc_symbol(&symbol_yes);
836 e2 = expr_alloc_symbol(&symbol_yes);
837 } else if (type == E_OR) {
838 e1 = expr_alloc_symbol(&symbol_no);
839 e2 = expr_alloc_symbol(&symbol_no);
846 struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)
848 struct expr *e1, *e2;
851 e = expr_alloc_symbol(sym);
852 if (type == E_UNEQUAL)
853 e = expr_alloc_one(E_NOT, e);
858 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
859 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
860 if (sym == &symbol_yes)
861 e = expr_alloc_two(E_AND, e1, e2);
862 if (sym == &symbol_no)
863 e = expr_alloc_two(E_OR, e1, e2);
864 if (type == E_UNEQUAL)
865 e = expr_alloc_one(E_NOT, e);
868 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
869 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
870 if (sym == &symbol_yes)
871 e = expr_alloc_two(E_OR, e1, e2);
872 if (sym == &symbol_no)
873 e = expr_alloc_two(E_AND, e1, e2);
874 if (type == E_UNEQUAL)
875 e = expr_alloc_one(E_NOT, e);
878 return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym);
881 if (type == E_EQUAL) {
882 if (sym == &symbol_yes)
884 if (sym == &symbol_mod)
885 return expr_alloc_symbol(&symbol_no);
886 if (sym == &symbol_no)
887 return expr_alloc_one(E_NOT, expr_copy(e));
889 if (sym == &symbol_yes)
890 return expr_alloc_one(E_NOT, expr_copy(e));
891 if (sym == &symbol_mod)
892 return expr_alloc_symbol(&symbol_yes);
893 if (sym == &symbol_no)
898 return expr_alloc_comp(type, e->left.sym, sym);
906 tristate expr_calc_value(struct expr *e)
909 const char *str1, *str2;
916 sym_calc_value(e->left.sym);
917 return S_TRI(e->left.sym->curr);
919 val1 = expr_calc_value(e->left.expr);
920 val2 = expr_calc_value(e->right.expr);
921 return E_AND(val1, val2);
923 val1 = expr_calc_value(e->left.expr);
924 val2 = expr_calc_value(e->right.expr);
925 return E_OR(val1, val2);
927 val1 = expr_calc_value(e->left.expr);
930 sym_calc_value(e->left.sym);
931 sym_calc_value(e->right.sym);
932 str1 = sym_get_string_value(e->left.sym);
933 str2 = sym_get_string_value(e->right.sym);
934 return !strcmp(str1, str2) ? yes : no;
936 sym_calc_value(e->left.sym);
937 sym_calc_value(e->right.sym);
938 str1 = sym_get_string_value(e->left.sym);
939 str2 = sym_get_string_value(e->right.sym);
940 return !strcmp(str1, str2) ? no : yes;
942 printf("expr_calc_value: %d?\n", e->type);
947 int expr_compare_type(enum expr_type t1, enum expr_type t2)
974 printf("[%dgt%d?]", t1, t2);
979 void expr_print(struct expr *e, void (*fn)(void *, const char *), void *data, int prevtoken)
986 if (expr_compare_type(prevtoken, e->type) > 0)
990 if (e->left.sym->name)
991 fn(data, e->left.sym->name);
993 fn(data, "<choice>");
997 expr_print(e->left.expr, fn, data, E_NOT);
1000 fn(data, e->left.sym->name);
1002 fn(data, e->right.sym->name);
1005 fn(data, e->left.sym->name);
1007 fn(data, e->right.sym->name);
1010 expr_print(e->left.expr, fn, data, E_OR);
1012 expr_print(e->right.expr, fn, data, E_OR);
1015 expr_print(e->left.expr, fn, data, E_AND);
1017 expr_print(e->right.expr, fn, data, E_AND);
1021 expr_print(e->left.expr, fn, data, E_CHOICE);
1024 fn(data, e->right.sym->name);
1029 sprintf(buf, "<unknown type %d>", e->type);
1034 if (expr_compare_type(prevtoken, e->type) > 0)
1038 static void expr_print_file_helper(void *data, const char *str)
1040 fwrite(str, strlen(str), 1, data);
1043 void expr_fprint(struct expr *e, FILE *out)
1045 expr_print(e, expr_print_file_helper, out, E_NONE);
1048 void print_expr(int mask, struct expr *e, int prevtoken)
1050 if (!(cdebug & mask))
1052 expr_fprint(e, stdout);