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_alloc_or(struct expr *e1, struct expr *e2)
62 return e2 ? expr_alloc_two(E_OR, e1, e2) : e1;
65 struct expr *expr_copy(struct expr *org)
72 e = malloc(sizeof(*org));
73 memcpy(e, org, sizeof(*org));
79 e->left.expr = expr_copy(org->left.expr);
83 e->left.sym = org->left.sym;
84 e->right.sym = org->right.sym;
89 e->left.expr = expr_copy(org->left.expr);
90 e->right.expr = expr_copy(org->right.expr);
93 printf("can't copy type %d\n", e->type);
102 void expr_free(struct expr *e)
111 expr_free(e->left.expr);
118 expr_free(e->left.expr);
119 expr_free(e->right.expr);
122 printf("how to free type %d?\n", e->type);
128 static int trans_count;
133 static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2)
135 if (e1->type == type) {
136 __expr_eliminate_eq(type, &e1->left.expr, &e2);
137 __expr_eliminate_eq(type, &e1->right.expr, &e2);
140 if (e2->type == type) {
141 __expr_eliminate_eq(type, &e1, &e2->left.expr);
142 __expr_eliminate_eq(type, &e1, &e2->right.expr);
145 if (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
146 e1->left.sym == e2->left.sym && (e1->left.sym->flags & (SYMBOL_YES|SYMBOL_NO)))
148 if (!expr_eq(e1, e2))
151 expr_free(e1); expr_free(e2);
154 e1 = expr_alloc_symbol(&symbol_no);
155 e2 = expr_alloc_symbol(&symbol_no);
158 e1 = expr_alloc_symbol(&symbol_yes);
159 e2 = expr_alloc_symbol(&symbol_yes);
166 void expr_eliminate_eq(struct expr **ep1, struct expr **ep2)
173 __expr_eliminate_eq(e1->type, ep1, ep2);
177 if (e1->type != e2->type) switch (e2->type) {
180 __expr_eliminate_eq(e2->type, ep1, ep2);
184 e1 = expr_eliminate_yn(e1);
185 e2 = expr_eliminate_yn(e2);
191 int expr_eq(struct expr *e1, struct expr *e2)
195 if (e1->type != e2->type)
200 return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym;
202 return e1->left.sym == e2->left.sym;
204 return expr_eq(e1->left.expr, e2->left.expr);
209 old_count = trans_count;
210 expr_eliminate_eq(&e1, &e2);
211 res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
212 e1->left.sym == e2->left.sym);
215 trans_count = old_count;
223 print_expr(0, e1, 0);
225 print_expr(0, e2, 0);
231 struct expr *expr_eliminate_yn(struct expr *e)
235 if (e) switch (e->type) {
237 e->left.expr = expr_eliminate_yn(e->left.expr);
238 e->right.expr = expr_eliminate_yn(e->right.expr);
239 if (e->left.expr->type == E_SYMBOL) {
240 if (e->left.expr->left.sym == &symbol_no) {
241 expr_free(e->left.expr);
242 expr_free(e->right.expr);
244 e->left.sym = &symbol_no;
245 e->right.expr = NULL;
247 } else if (e->left.expr->left.sym == &symbol_yes) {
250 *e = *(e->right.expr);
255 if (e->right.expr->type == E_SYMBOL) {
256 if (e->right.expr->left.sym == &symbol_no) {
257 expr_free(e->left.expr);
258 expr_free(e->right.expr);
260 e->left.sym = &symbol_no;
261 e->right.expr = NULL;
263 } else if (e->right.expr->left.sym == &symbol_yes) {
266 *e = *(e->left.expr);
273 e->left.expr = expr_eliminate_yn(e->left.expr);
274 e->right.expr = expr_eliminate_yn(e->right.expr);
275 if (e->left.expr->type == E_SYMBOL) {
276 if (e->left.expr->left.sym == &symbol_no) {
279 *e = *(e->right.expr);
282 } else if (e->left.expr->left.sym == &symbol_yes) {
283 expr_free(e->left.expr);
284 expr_free(e->right.expr);
286 e->left.sym = &symbol_yes;
287 e->right.expr = NULL;
291 if (e->right.expr->type == E_SYMBOL) {
292 if (e->right.expr->left.sym == &symbol_no) {
295 *e = *(e->left.expr);
298 } else if (e->right.expr->left.sym == &symbol_yes) {
299 expr_free(e->left.expr);
300 expr_free(e->right.expr);
302 e->left.sym = &symbol_yes;
303 e->right.expr = NULL;
317 struct expr *expr_trans_bool(struct expr *e)
325 e->left.expr = expr_trans_bool(e->left.expr);
326 e->right.expr = expr_trans_bool(e->right.expr);
330 if (e->left.sym->type == S_TRISTATE) {
331 if (e->right.sym == &symbol_no) {
346 struct expr *expr_join_or(struct expr *e1, struct expr *e2)
349 struct symbol *sym1, *sym2;
352 return expr_copy(e1);
353 if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
355 if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
357 if (e1->type == E_NOT) {
359 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
361 sym1 = tmp->left.sym;
364 if (e2->type == E_NOT) {
365 if (e2->left.expr->type != E_SYMBOL)
367 sym2 = e2->left.expr->left.sym;
372 if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
374 if (sym1->type == S_TRISTATE) {
375 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
376 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
377 (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) {
378 // (a='y') || (a='m') -> (a!='n')
379 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no);
381 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
382 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
383 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) {
384 // (a='y') || (a='n') -> (a!='m')
385 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod);
387 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
388 ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
389 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) {
390 // (a='m') || (a='n') -> (a!='y')
391 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes);
394 if (sym1->type == S_BOOLEAN && sym1 == sym2) {
395 if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) ||
396 (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL))
397 return expr_alloc_symbol(&symbol_yes);
401 print_expr(0, e1, 0);
403 print_expr(0, e2, 0);
408 struct expr *expr_join_and(struct expr *e1, struct expr *e2)
411 struct symbol *sym1, *sym2;
414 return expr_copy(e1);
415 if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
417 if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
419 if (e1->type == E_NOT) {
421 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
423 sym1 = tmp->left.sym;
426 if (e2->type == E_NOT) {
427 if (e2->left.expr->type != E_SYMBOL)
429 sym2 = e2->left.expr->left.sym;
434 if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
437 if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) ||
438 (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes))
439 // (a) && (a='y') -> (a='y')
440 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
442 if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) ||
443 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no))
444 // (a) && (a!='n') -> (a)
445 return expr_alloc_symbol(sym1);
447 if (sym1->type == S_TRISTATE) {
448 if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) {
449 // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
450 sym2 = e1->right.sym;
451 if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
452 return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
453 : expr_alloc_symbol(&symbol_no);
455 if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) {
456 // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
457 sym2 = e2->right.sym;
458 if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
459 return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
460 : expr_alloc_symbol(&symbol_no);
462 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
463 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
464 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes)))
465 // (a!='y') && (a!='n') -> (a='m')
466 return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod);
468 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
469 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
470 (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes)))
471 // (a!='y') && (a!='m') -> (a='n')
472 return expr_alloc_comp(E_EQUAL, sym1, &symbol_no);
474 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
475 ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
476 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod)))
477 // (a!='m') && (a!='n') -> (a='m')
478 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
480 if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) ||
481 (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) ||
482 (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) ||
483 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes))
487 print_expr(0, e1, 0);
489 print_expr(0, e2, 0);
494 static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2)
500 if (e1->type == type) {
501 expr_eliminate_dups1(type, &e1->left.expr, &e2);
502 expr_eliminate_dups1(type, &e1->right.expr, &e2);
505 if (e2->type == type) {
506 expr_eliminate_dups1(type, &e1, &e2->left.expr);
507 expr_eliminate_dups1(type, &e1, &e2->right.expr);
514 case E_OR: case E_AND:
515 expr_eliminate_dups1(e1->type, &e1, &e1);
522 tmp = expr_join_or(e1, e2);
524 expr_free(e1); expr_free(e2);
525 e1 = expr_alloc_symbol(&symbol_no);
531 tmp = expr_join_and(e1, e2);
533 expr_free(e1); expr_free(e2);
534 e1 = expr_alloc_symbol(&symbol_yes);
546 static void expr_eliminate_dups2(enum expr_type type, struct expr **ep1, struct expr **ep2)
550 struct expr *tmp, *tmp1, *tmp2;
552 if (e1->type == type) {
553 expr_eliminate_dups2(type, &e1->left.expr, &e2);
554 expr_eliminate_dups2(type, &e1->right.expr, &e2);
557 if (e2->type == type) {
558 expr_eliminate_dups2(type, &e1, &e2->left.expr);
559 expr_eliminate_dups2(type, &e1, &e2->right.expr);
566 expr_eliminate_dups2(e1->type, &e1, &e1);
567 // (FOO || BAR) && (!FOO && !BAR) -> n
568 tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1)));
569 tmp2 = expr_copy(e2);
570 tmp = expr_extract_eq_and(&tmp1, &tmp2);
571 if (expr_is_yes(tmp1)) {
573 e1 = expr_alloc_symbol(&symbol_no);
581 expr_eliminate_dups2(e1->type, &e1, &e1);
582 // (FOO && BAR) || (!FOO || !BAR) -> y
583 tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1)));
584 tmp2 = expr_copy(e2);
585 tmp = expr_extract_eq_or(&tmp1, &tmp2);
586 if (expr_is_no(tmp1)) {
588 e1 = expr_alloc_symbol(&symbol_yes);
602 struct expr *expr_eliminate_dups(struct expr *e)
608 oldcount = trans_count;
612 case E_OR: case E_AND:
613 expr_eliminate_dups1(e->type, &e, &e);
614 expr_eliminate_dups2(e->type, &e, &e);
620 e = expr_eliminate_yn(e);
622 trans_count = oldcount;
626 struct expr *expr_transform(struct expr *e)
639 e->left.expr = expr_transform(e->left.expr);
640 e->right.expr = expr_transform(e->right.expr);
645 if (e->left.sym->type != S_BOOLEAN)
647 if (e->right.sym == &symbol_no) {
649 e->left.expr = expr_alloc_symbol(e->left.sym);
653 if (e->right.sym == &symbol_mod) {
654 printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name);
656 e->left.sym = &symbol_no;
660 if (e->right.sym == &symbol_yes) {
667 if (e->left.sym->type != S_BOOLEAN)
669 if (e->right.sym == &symbol_no) {
674 if (e->right.sym == &symbol_mod) {
675 printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name);
677 e->left.sym = &symbol_yes;
681 if (e->right.sym == &symbol_yes) {
683 e->left.expr = expr_alloc_symbol(e->left.sym);
689 switch (e->left.expr->type) {
692 tmp = e->left.expr->left.expr;
696 e = expr_transform(e);
704 e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL;
707 // !(a || b) -> !a && !b
710 e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
712 tmp->right.expr = NULL;
713 e = expr_transform(e);
716 // !(a && b) -> !a || !b
719 e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
721 tmp->right.expr = NULL;
722 e = expr_transform(e);
725 if (e->left.expr->left.sym == &symbol_yes) {
731 e->left.sym = &symbol_no;
734 if (e->left.expr->left.sym == &symbol_mod) {
740 e->left.sym = &symbol_mod;
743 if (e->left.expr->left.sym == &symbol_no) {
749 e->left.sym = &symbol_yes;
763 int expr_contains_symbol(struct expr *dep, struct symbol *sym)
771 return expr_contains_symbol(dep->left.expr, sym) ||
772 expr_contains_symbol(dep->right.expr, sym);
774 return dep->left.sym == sym;
777 return dep->left.sym == sym ||
778 dep->right.sym == sym;
780 return expr_contains_symbol(dep->left.expr, sym);
787 bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
794 return expr_depends_symbol(dep->left.expr, sym) ||
795 expr_depends_symbol(dep->right.expr, sym);
797 return dep->left.sym == sym;
799 if (dep->left.sym == sym) {
800 if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod)
805 if (dep->left.sym == sym) {
806 if (dep->right.sym == &symbol_no)
816 struct expr *expr_extract_eq_and(struct expr **ep1, struct expr **ep2)
818 struct expr *tmp = NULL;
819 expr_extract_eq(E_AND, &tmp, ep1, ep2);
821 *ep1 = expr_eliminate_yn(*ep1);
822 *ep2 = expr_eliminate_yn(*ep2);
827 struct expr *expr_extract_eq_or(struct expr **ep1, struct expr **ep2)
829 struct expr *tmp = NULL;
830 expr_extract_eq(E_OR, &tmp, ep1, ep2);
832 *ep1 = expr_eliminate_yn(*ep1);
833 *ep2 = expr_eliminate_yn(*ep2);
838 void expr_extract_eq(enum expr_type type, struct expr **ep, struct expr **ep1, struct expr **ep2)
842 if (e1->type == type) {
843 expr_extract_eq(type, ep, &e1->left.expr, &e2);
844 expr_extract_eq(type, ep, &e1->right.expr, &e2);
847 if (e2->type == type) {
848 expr_extract_eq(type, ep, ep1, &e2->left.expr);
849 expr_extract_eq(type, ep, ep1, &e2->right.expr);
852 if (expr_eq(e1, e2)) {
853 *ep = *ep ? expr_alloc_two(type, *ep, e1) : e1;
856 e1 = expr_alloc_symbol(&symbol_yes);
857 e2 = expr_alloc_symbol(&symbol_yes);
858 } else if (type == E_OR) {
859 e1 = expr_alloc_symbol(&symbol_no);
860 e2 = expr_alloc_symbol(&symbol_no);
867 struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)
869 struct expr *e1, *e2;
872 e = expr_alloc_symbol(sym);
873 if (type == E_UNEQUAL)
874 e = expr_alloc_one(E_NOT, e);
879 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
880 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
881 if (sym == &symbol_yes)
882 e = expr_alloc_two(E_AND, e1, e2);
883 if (sym == &symbol_no)
884 e = expr_alloc_two(E_OR, e1, e2);
885 if (type == E_UNEQUAL)
886 e = expr_alloc_one(E_NOT, e);
889 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
890 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
891 if (sym == &symbol_yes)
892 e = expr_alloc_two(E_OR, e1, e2);
893 if (sym == &symbol_no)
894 e = expr_alloc_two(E_AND, e1, e2);
895 if (type == E_UNEQUAL)
896 e = expr_alloc_one(E_NOT, e);
899 return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym);
902 if (type == E_EQUAL) {
903 if (sym == &symbol_yes)
905 if (sym == &symbol_mod)
906 return expr_alloc_symbol(&symbol_no);
907 if (sym == &symbol_no)
908 return expr_alloc_one(E_NOT, expr_copy(e));
910 if (sym == &symbol_yes)
911 return expr_alloc_one(E_NOT, expr_copy(e));
912 if (sym == &symbol_mod)
913 return expr_alloc_symbol(&symbol_yes);
914 if (sym == &symbol_no)
919 return expr_alloc_comp(type, e->left.sym, sym);
928 tristate expr_calc_value(struct expr *e)
931 const char *str1, *str2;
938 sym_calc_value(e->left.sym);
939 return e->left.sym->curr.tri;
941 val1 = expr_calc_value(e->left.expr);
942 val2 = expr_calc_value(e->right.expr);
943 return E_AND(val1, val2);
945 val1 = expr_calc_value(e->left.expr);
946 val2 = expr_calc_value(e->right.expr);
947 return E_OR(val1, val2);
949 val1 = expr_calc_value(e->left.expr);
952 sym_calc_value(e->left.sym);
953 sym_calc_value(e->right.sym);
954 str1 = sym_get_string_value(e->left.sym);
955 str2 = sym_get_string_value(e->right.sym);
956 return !strcmp(str1, str2) ? yes : no;
958 sym_calc_value(e->left.sym);
959 sym_calc_value(e->right.sym);
960 str1 = sym_get_string_value(e->left.sym);
961 str2 = sym_get_string_value(e->right.sym);
962 return !strcmp(str1, str2) ? no : yes;
964 printf("expr_calc_value: %d?\n", e->type);
969 int expr_compare_type(enum expr_type t1, enum expr_type t2)
996 printf("[%dgt%d?]", t1, t2);
1001 void expr_print(struct expr *e, void (*fn)(void *, const char *), void *data, int prevtoken)
1008 if (expr_compare_type(prevtoken, e->type) > 0)
1012 if (e->left.sym->name)
1013 fn(data, e->left.sym->name);
1015 fn(data, "<choice>");
1019 expr_print(e->left.expr, fn, data, E_NOT);
1022 fn(data, e->left.sym->name);
1024 fn(data, e->right.sym->name);
1027 fn(data, e->left.sym->name);
1029 fn(data, e->right.sym->name);
1032 expr_print(e->left.expr, fn, data, E_OR);
1034 expr_print(e->right.expr, fn, data, E_OR);
1037 expr_print(e->left.expr, fn, data, E_AND);
1039 expr_print(e->right.expr, fn, data, E_AND);
1042 fn(data, e->right.sym->name);
1045 expr_print(e->left.expr, fn, data, E_CHOICE);
1050 fn(data, e->left.sym->name);
1052 fn(data, e->right.sym->name);
1058 sprintf(buf, "<unknown type %d>", e->type);
1063 if (expr_compare_type(prevtoken, e->type) > 0)
1067 static void expr_print_file_helper(void *data, const char *str)
1069 fwrite(str, strlen(str), 1, data);
1072 void expr_fprint(struct expr *e, FILE *out)
1074 expr_print(e, expr_print_file_helper, out, E_NONE);
1077 void print_expr(int mask, struct expr *e, int prevtoken)
1079 if (!(cdebug & mask))
1081 expr_fprint(e, stdout);