2 * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org>
3 * Released under the terms of the GNU GPL v2.0.
14 static int expr_eq(struct expr *e1, struct expr *e2);
15 static struct expr *expr_eliminate_yn(struct expr *e);
17 struct expr *expr_alloc_symbol(struct symbol *sym)
19 struct expr *e = xcalloc(1, sizeof(*e));
25 struct expr *expr_alloc_one(enum expr_type type, struct expr *ce)
27 struct expr *e = xcalloc(1, sizeof(*e));
33 struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e2)
35 struct expr *e = xcalloc(1, sizeof(*e));
42 struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2)
44 struct expr *e = xcalloc(1, 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(const struct expr *org)
72 e = xmalloc(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 &&
147 (e1->left.sym == &symbol_yes || e1->left.sym == &symbol_no))
149 if (!expr_eq(e1, e2))
152 expr_free(e1); expr_free(e2);
155 e1 = expr_alloc_symbol(&symbol_no);
156 e2 = expr_alloc_symbol(&symbol_no);
159 e1 = expr_alloc_symbol(&symbol_yes);
160 e2 = expr_alloc_symbol(&symbol_yes);
167 void expr_eliminate_eq(struct expr **ep1, struct expr **ep2)
174 __expr_eliminate_eq(e1->type, ep1, ep2);
178 if (e1->type != e2->type) switch (e2->type) {
181 __expr_eliminate_eq(e2->type, ep1, ep2);
185 e1 = expr_eliminate_yn(e1);
186 e2 = expr_eliminate_yn(e2);
192 static int expr_eq(struct expr *e1, struct expr *e2)
196 if (e1->type != e2->type)
201 return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym;
203 return e1->left.sym == e2->left.sym;
205 return expr_eq(e1->left.expr, e2->left.expr);
210 old_count = trans_count;
211 expr_eliminate_eq(&e1, &e2);
212 res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
213 e1->left.sym == e2->left.sym);
216 trans_count = old_count;
225 expr_fprint(e1, stdout);
227 expr_fprint(e2, stdout);
234 static struct expr *expr_eliminate_yn(struct expr *e)
238 if (e) switch (e->type) {
240 e->left.expr = expr_eliminate_yn(e->left.expr);
241 e->right.expr = expr_eliminate_yn(e->right.expr);
242 if (e->left.expr->type == E_SYMBOL) {
243 if (e->left.expr->left.sym == &symbol_no) {
244 expr_free(e->left.expr);
245 expr_free(e->right.expr);
247 e->left.sym = &symbol_no;
248 e->right.expr = NULL;
250 } else if (e->left.expr->left.sym == &symbol_yes) {
253 *e = *(e->right.expr);
258 if (e->right.expr->type == E_SYMBOL) {
259 if (e->right.expr->left.sym == &symbol_no) {
260 expr_free(e->left.expr);
261 expr_free(e->right.expr);
263 e->left.sym = &symbol_no;
264 e->right.expr = NULL;
266 } else if (e->right.expr->left.sym == &symbol_yes) {
269 *e = *(e->left.expr);
276 e->left.expr = expr_eliminate_yn(e->left.expr);
277 e->right.expr = expr_eliminate_yn(e->right.expr);
278 if (e->left.expr->type == E_SYMBOL) {
279 if (e->left.expr->left.sym == &symbol_no) {
282 *e = *(e->right.expr);
285 } else if (e->left.expr->left.sym == &symbol_yes) {
286 expr_free(e->left.expr);
287 expr_free(e->right.expr);
289 e->left.sym = &symbol_yes;
290 e->right.expr = NULL;
294 if (e->right.expr->type == E_SYMBOL) {
295 if (e->right.expr->left.sym == &symbol_no) {
298 *e = *(e->left.expr);
301 } else if (e->right.expr->left.sym == &symbol_yes) {
302 expr_free(e->left.expr);
303 expr_free(e->right.expr);
305 e->left.sym = &symbol_yes;
306 e->right.expr = NULL;
320 struct expr *expr_trans_bool(struct expr *e)
328 e->left.expr = expr_trans_bool(e->left.expr);
329 e->right.expr = expr_trans_bool(e->right.expr);
333 if (e->left.sym->type == S_TRISTATE) {
334 if (e->right.sym == &symbol_no) {
349 static struct expr *expr_join_or(struct expr *e1, struct expr *e2)
352 struct symbol *sym1, *sym2;
355 return expr_copy(e1);
356 if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
358 if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
360 if (e1->type == E_NOT) {
362 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
364 sym1 = tmp->left.sym;
367 if (e2->type == E_NOT) {
368 if (e2->left.expr->type != E_SYMBOL)
370 sym2 = e2->left.expr->left.sym;
375 if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
377 if (sym1->type == S_TRISTATE) {
378 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
379 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
380 (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) {
381 // (a='y') || (a='m') -> (a!='n')
382 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no);
384 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
385 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
386 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) {
387 // (a='y') || (a='n') -> (a!='m')
388 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod);
390 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
391 ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
392 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) {
393 // (a='m') || (a='n') -> (a!='y')
394 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes);
397 if (sym1->type == S_BOOLEAN && sym1 == sym2) {
398 if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) ||
399 (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL))
400 return expr_alloc_symbol(&symbol_yes);
404 printf("optimize (");
405 expr_fprint(e1, stdout);
407 expr_fprint(e2, stdout);
413 static struct expr *expr_join_and(struct expr *e1, struct expr *e2)
416 struct symbol *sym1, *sym2;
419 return expr_copy(e1);
420 if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
422 if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
424 if (e1->type == E_NOT) {
426 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
428 sym1 = tmp->left.sym;
431 if (e2->type == E_NOT) {
432 if (e2->left.expr->type != E_SYMBOL)
434 sym2 = e2->left.expr->left.sym;
439 if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
442 if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) ||
443 (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes))
444 // (a) && (a='y') -> (a='y')
445 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
447 if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) ||
448 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no))
449 // (a) && (a!='n') -> (a)
450 return expr_alloc_symbol(sym1);
452 if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) ||
453 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod))
454 // (a) && (a!='m') -> (a='y')
455 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
457 if (sym1->type == S_TRISTATE) {
458 if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) {
459 // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
460 sym2 = e1->right.sym;
461 if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
462 return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
463 : expr_alloc_symbol(&symbol_no);
465 if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) {
466 // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
467 sym2 = e2->right.sym;
468 if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
469 return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
470 : expr_alloc_symbol(&symbol_no);
472 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
473 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
474 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes)))
475 // (a!='y') && (a!='n') -> (a='m')
476 return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod);
478 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
479 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
480 (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes)))
481 // (a!='y') && (a!='m') -> (a='n')
482 return expr_alloc_comp(E_EQUAL, sym1, &symbol_no);
484 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
485 ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
486 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod)))
487 // (a!='m') && (a!='n') -> (a='m')
488 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
490 if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) ||
491 (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) ||
492 (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) ||
493 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes))
498 printf("optimize (");
499 expr_fprint(e1, stdout);
501 expr_fprint(e2, stdout);
507 static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2)
513 if (e1->type == type) {
514 expr_eliminate_dups1(type, &e1->left.expr, &e2);
515 expr_eliminate_dups1(type, &e1->right.expr, &e2);
518 if (e2->type == type) {
519 expr_eliminate_dups1(type, &e1, &e2->left.expr);
520 expr_eliminate_dups1(type, &e1, &e2->right.expr);
527 case E_OR: case E_AND:
528 expr_eliminate_dups1(e1->type, &e1, &e1);
535 tmp = expr_join_or(e1, e2);
537 expr_free(e1); expr_free(e2);
538 e1 = expr_alloc_symbol(&symbol_no);
544 tmp = expr_join_and(e1, e2);
546 expr_free(e1); expr_free(e2);
547 e1 = expr_alloc_symbol(&symbol_yes);
559 struct expr *expr_eliminate_dups(struct expr *e)
565 oldcount = trans_count;
569 case E_OR: case E_AND:
570 expr_eliminate_dups1(e->type, &e, &e);
576 e = expr_eliminate_yn(e);
578 trans_count = oldcount;
582 struct expr *expr_transform(struct expr *e)
595 e->left.expr = expr_transform(e->left.expr);
596 e->right.expr = expr_transform(e->right.expr);
601 if (e->left.sym->type != S_BOOLEAN)
603 if (e->right.sym == &symbol_no) {
605 e->left.expr = expr_alloc_symbol(e->left.sym);
609 if (e->right.sym == &symbol_mod) {
610 printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name);
612 e->left.sym = &symbol_no;
616 if (e->right.sym == &symbol_yes) {
623 if (e->left.sym->type != S_BOOLEAN)
625 if (e->right.sym == &symbol_no) {
630 if (e->right.sym == &symbol_mod) {
631 printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name);
633 e->left.sym = &symbol_yes;
637 if (e->right.sym == &symbol_yes) {
639 e->left.expr = expr_alloc_symbol(e->left.sym);
645 switch (e->left.expr->type) {
648 tmp = e->left.expr->left.expr;
652 e = expr_transform(e);
660 e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL;
663 // !(a || b) -> !a && !b
666 e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
668 tmp->right.expr = NULL;
669 e = expr_transform(e);
672 // !(a && b) -> !a || !b
675 e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
677 tmp->right.expr = NULL;
678 e = expr_transform(e);
681 if (e->left.expr->left.sym == &symbol_yes) {
687 e->left.sym = &symbol_no;
690 if (e->left.expr->left.sym == &symbol_mod) {
696 e->left.sym = &symbol_mod;
699 if (e->left.expr->left.sym == &symbol_no) {
705 e->left.sym = &symbol_yes;
719 int expr_contains_symbol(struct expr *dep, struct symbol *sym)
727 return expr_contains_symbol(dep->left.expr, sym) ||
728 expr_contains_symbol(dep->right.expr, sym);
730 return dep->left.sym == sym;
733 return dep->left.sym == sym ||
734 dep->right.sym == sym;
736 return expr_contains_symbol(dep->left.expr, sym);
743 bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
750 return expr_depends_symbol(dep->left.expr, sym) ||
751 expr_depends_symbol(dep->right.expr, sym);
753 return dep->left.sym == sym;
755 if (dep->left.sym == sym) {
756 if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod)
761 if (dep->left.sym == sym) {
762 if (dep->right.sym == &symbol_no)
772 struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)
774 struct expr *e1, *e2;
777 e = expr_alloc_symbol(sym);
778 if (type == E_UNEQUAL)
779 e = expr_alloc_one(E_NOT, e);
784 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
785 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
786 if (sym == &symbol_yes)
787 e = expr_alloc_two(E_AND, e1, e2);
788 if (sym == &symbol_no)
789 e = expr_alloc_two(E_OR, e1, e2);
790 if (type == E_UNEQUAL)
791 e = expr_alloc_one(E_NOT, e);
794 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
795 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
796 if (sym == &symbol_yes)
797 e = expr_alloc_two(E_OR, e1, e2);
798 if (sym == &symbol_no)
799 e = expr_alloc_two(E_AND, e1, e2);
800 if (type == E_UNEQUAL)
801 e = expr_alloc_one(E_NOT, e);
804 return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym);
807 if (type == E_EQUAL) {
808 if (sym == &symbol_yes)
810 if (sym == &symbol_mod)
811 return expr_alloc_symbol(&symbol_no);
812 if (sym == &symbol_no)
813 return expr_alloc_one(E_NOT, expr_copy(e));
815 if (sym == &symbol_yes)
816 return expr_alloc_one(E_NOT, expr_copy(e));
817 if (sym == &symbol_mod)
818 return expr_alloc_symbol(&symbol_yes);
819 if (sym == &symbol_no)
824 return expr_alloc_comp(type, e->left.sym, sym);
833 tristate expr_calc_value(struct expr *e)
836 const char *str1, *str2;
843 sym_calc_value(e->left.sym);
844 return e->left.sym->curr.tri;
846 val1 = expr_calc_value(e->left.expr);
847 val2 = expr_calc_value(e->right.expr);
848 return EXPR_AND(val1, val2);
850 val1 = expr_calc_value(e->left.expr);
851 val2 = expr_calc_value(e->right.expr);
852 return EXPR_OR(val1, val2);
854 val1 = expr_calc_value(e->left.expr);
855 return EXPR_NOT(val1);
857 sym_calc_value(e->left.sym);
858 sym_calc_value(e->right.sym);
859 str1 = sym_get_string_value(e->left.sym);
860 str2 = sym_get_string_value(e->right.sym);
861 return !strcmp(str1, str2) ? yes : no;
863 sym_calc_value(e->left.sym);
864 sym_calc_value(e->right.sym);
865 str1 = sym_get_string_value(e->left.sym);
866 str2 = sym_get_string_value(e->right.sym);
867 return !strcmp(str1, str2) ? no : yes;
869 printf("expr_calc_value: %d?\n", e->type);
874 static int expr_compare_type(enum expr_type t1, enum expr_type t2)
898 printf("[%dgt%d?]", t1, t2);
902 static inline struct expr *
903 expr_get_leftmost_symbol(const struct expr *e)
909 while (e->type != E_SYMBOL)
916 * Given expression `e1' and `e2', returns the leaf of the longest
917 * sub-expression of `e1' not containing 'e2.
919 struct expr *expr_simplify_unmet_dep(struct expr *e1, struct expr *e2)
925 return expr_alloc_and(
926 expr_simplify_unmet_dep(e1->left.expr, e2),
927 expr_simplify_unmet_dep(e1->right.expr, e2));
930 e = expr_alloc_and(expr_copy(e1), expr_copy(e2));
931 e = expr_eliminate_dups(e);
932 ret = (!expr_eq(e, e1)) ? e1 : NULL;
941 return expr_get_leftmost_symbol(ret);
944 void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken)
951 if (expr_compare_type(prevtoken, e->type) > 0)
955 if (e->left.sym->name)
956 fn(data, e->left.sym, e->left.sym->name);
958 fn(data, NULL, "<choice>");
962 expr_print(e->left.expr, fn, data, E_NOT);
965 if (e->left.sym->name)
966 fn(data, e->left.sym, e->left.sym->name);
968 fn(data, NULL, "<choice>");
970 fn(data, e->right.sym, e->right.sym->name);
973 if (e->left.sym->name)
974 fn(data, e->left.sym, e->left.sym->name);
976 fn(data, NULL, "<choice>");
977 fn(data, NULL, "!=");
978 fn(data, e->right.sym, e->right.sym->name);
981 expr_print(e->left.expr, fn, data, E_OR);
982 fn(data, NULL, " || ");
983 expr_print(e->right.expr, fn, data, E_OR);
986 expr_print(e->left.expr, fn, data, E_AND);
987 fn(data, NULL, " && ");
988 expr_print(e->right.expr, fn, data, E_AND);
991 fn(data, e->right.sym, e->right.sym->name);
993 fn(data, NULL, " ^ ");
994 expr_print(e->left.expr, fn, data, E_LIST);
999 fn(data, e->left.sym, e->left.sym->name);
1000 fn(data, NULL, " ");
1001 fn(data, e->right.sym, e->right.sym->name);
1002 fn(data, NULL, "]");
1007 sprintf(buf, "<unknown type %d>", e->type);
1008 fn(data, NULL, buf);
1012 if (expr_compare_type(prevtoken, e->type) > 0)
1013 fn(data, NULL, ")");
1016 static void expr_print_file_helper(void *data, struct symbol *sym, const char *str)
1018 xfwrite(str, strlen(str), 1, data);
1021 void expr_fprint(struct expr *e, FILE *out)
1023 expr_print(e, expr_print_file_helper, out, E_NONE);
1026 static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str)
1028 struct gstr *gs = (struct gstr*)data;
1029 const char *sym_str = NULL;
1032 sym_str = sym_get_string_value(sym);
1034 if (gs->max_width) {
1035 unsigned extra_length = strlen(str);
1036 const char *last_cr = strrchr(gs->s, '\n');
1037 unsigned last_line_length;
1040 extra_length += 4 + strlen(sym_str);
1045 last_line_length = strlen(gs->s) - (last_cr - gs->s);
1047 if ((last_line_length + extra_length) > gs->max_width)
1048 str_append(gs, "\\\n");
1051 str_append(gs, str);
1052 if (sym && sym->type != S_UNKNOWN)
1053 str_printf(gs, " [=%s]", sym_str);
1056 void expr_gstr_print(struct expr *e, struct gstr *gs)
1058 expr_print(e, expr_print_gstr_helper, gs, E_NONE);