Lines Matching +full:- +full:e
1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org>
21 static struct expr *expr_eliminate_yn(struct expr *e);
24 * expr_lookup - return the expression with the given type and sub-nodes
25 * This looks up an expression with the specified type and sub-nodes. If such
35 struct expr *e;
40 hash_for_each_possible(expr_hashtable, e, node, hash) {
41 if (e->type == type && e->left._initdata == l &&
42 e->right._initdata == r)
43 return e;
46 e = xmalloc(sizeof(*e));
47 e->type = type;
48 e->left._initdata = l;
49 e->right._initdata = r;
51 hash_add(expr_hashtable, &e->node, hash);
53 return e;
106 if ((*ep1)->type == type) {
107 l = (*ep1)->left.expr;
108 r = (*ep1)->right.expr;
114 if ((*ep2)->type == type) {
115 l = (*ep2)->left.expr;
116 r = (*ep2)->right.expr;
125 if ((*ep1)->type == E_SYMBOL && (*ep2)->type == E_SYMBOL &&
126 (*ep1)->left.sym == (*ep2)->left.sym &&
127 ((*ep1)->left.sym == &symbol_yes || (*ep1)->left.sym == &symbol_no))
153 * ep1: A && B -> ep1: y
154 * ep2: A && B && C -> ep2: C
156 * ep1: A || B -> ep1: n
157 * ep2: A || B || C -> ep2: C
159 * ep1: A && (B && FOO) -> ep1: FOO
160 * ep2: (BAR && B) && A -> ep2: BAR
162 * ep1: A && (B || C) -> ep1: y
163 * ep2: (C || B) && A -> ep2: y
169 * - 'e1', 'e2 || e3', and 'e4 || e5', against each other
170 * - e2 against e3
171 * - e4 against e5
182 switch ((*ep1)->type) {
185 __expr_eliminate_eq((*ep1)->type, ep1, ep2);
189 if ((*ep1)->type != (*ep2)->type) switch ((*ep2)->type) {
192 __expr_eliminate_eq((*ep2)->type, ep1, ep2);
218 if (e1->type != e2->type)
220 switch (e1->type) {
227 return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym;
229 return e1->left.sym == e2->left.sym;
231 return expr_eq(e1->left.expr, e2->left.expr);
236 res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
237 e1->left.sym == e2->left.sym);
259 * expr && n -> n
260 * expr && y -> expr
261 * expr || n -> expr
262 * expr || y -> y
266 static struct expr *expr_eliminate_yn(struct expr *e)
270 if (e) switch (e->type) {
272 l = expr_eliminate_yn(e->left.expr);
273 r = expr_eliminate_yn(e->right.expr);
274 if (l->type == E_SYMBOL) {
275 if (l->left.sym == &symbol_no)
277 else if (l->left.sym == &symbol_yes)
280 if (r->type == E_SYMBOL) {
281 if (r->left.sym == &symbol_no)
283 else if (r->left.sym == &symbol_yes)
288 l = expr_eliminate_yn(e->left.expr);
289 r = expr_eliminate_yn(e->right.expr);
290 if (l->type == E_SYMBOL) {
291 if (l->left.sym == &symbol_no)
293 else if (l->left.sym == &symbol_yes)
296 if (r->type == E_SYMBOL) {
297 if (r->left.sym == &symbol_no)
299 else if (r->left.sym == &symbol_yes)
306 return e;
310 * e1 || e2 -> ?
319 if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
321 if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
323 if (e1->type == E_NOT) {
324 tmp = e1->left.expr;
325 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
327 sym1 = tmp->left.sym;
329 sym1 = e1->left.sym;
330 if (e2->type == E_NOT) {
331 if (e2->left.expr->type != E_SYMBOL)
333 sym2 = e2->left.expr->left.sym;
335 sym2 = e2->left.sym;
338 if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
340 if (sym1->type == S_TRISTATE) {
341 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
342 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
343 (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) {
344 // (a='y') || (a='m') -> (a!='n')
347 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
348 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
349 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) {
350 // (a='y') || (a='n') -> (a!='m')
353 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
354 ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
355 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) {
356 // (a='m') || (a='n') -> (a!='y')
360 if (sym1->type == S_BOOLEAN) {
361 // a || !a -> y
362 if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) ||
363 (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL))
384 if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
386 if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
388 if (e1->type == E_NOT) {
389 tmp = e1->left.expr;
390 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
392 sym1 = tmp->left.sym;
394 sym1 = e1->left.sym;
395 if (e2->type == E_NOT) {
396 if (e2->left.expr->type != E_SYMBOL)
398 sym2 = e2->left.expr->left.sym;
400 sym2 = e2->left.sym;
403 if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
406 if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) ||
407 (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes))
408 // (a) && (a='y') -> (a='y')
411 if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) ||
412 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no))
413 // (a) && (a!='n') -> (a)
416 if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) ||
417 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod))
418 // (a) && (a!='m') -> (a='y')
421 if (sym1->type == S_TRISTATE) {
422 if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) {
423 // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
424 sym2 = e1->right.sym;
425 if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
426 return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
429 if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) {
430 // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
431 sym2 = e2->right.sym;
432 if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
433 return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
436 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
437 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
438 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes)))
439 // (a!='y') && (a!='n') -> (a='m')
442 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
443 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
444 (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes)))
445 // (a!='y') && (a!='m') -> (a='n')
448 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
449 ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
450 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod)))
451 // (a!='m') && (a!='n') -> (a='m')
454 if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) ||
455 (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) ||
456 (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) ||
457 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes))
484 if ((*ep1)->type == type) {
485 l = (*ep1)->left.expr;
486 r = (*ep1)->right.expr;
492 if ((*ep2)->type == type) {
493 l = (*ep2)->left.expr;
494 r = (*ep2)->right.expr;
526 * Rewrites 'e' in-place to remove ("join") duplicate and other redundant
531 * A || B || A -> A || B
532 * A && B && A=y -> A=y && B
536 struct expr *expr_eliminate_dups(struct expr *e)
539 if (!e)
540 return e;
547 switch (e->type) {
549 l = expr_eliminate_dups(e->left.expr);
550 r = expr_eliminate_dups(e->right.expr);
551 expr_eliminate_dups1(e->type, &l, &r);
552 e = expr_alloc_two(e->type, l, r);
556 e = expr_eliminate_yn(e);
559 return e;
567 * A=n -> !A
568 * A=m -> n
569 * A=y -> A
570 * A!=n -> A
571 * A!=m -> y
572 * A!=y -> !A
575 * !!A -> A
576 * !(A=B) -> A!=B
577 * !(A!=B) -> A=B
578 * !(A<=B) -> A>B
579 * !(A>=B) -> A<B
580 * !(A<B) -> A>=B
581 * !(A>B) -> A<=B
582 * !(A || B) -> !A && !B
583 * !(A && B) -> !A || !B
586 * !y -> n
587 * !m -> m
588 * !n -> y
592 struct expr *expr_transform(struct expr *e)
594 if (!e)
596 switch (e->type) {
606 e = expr_alloc_two(e->type,
607 expr_transform(e->left.expr),
608 expr_transform(e->right.expr));
611 switch (e->type) {
613 if (e->left.sym->type != S_BOOLEAN)
615 if (e->right.sym == &symbol_no) {
616 // A=n -> !A
617 e = expr_alloc_one(E_NOT, expr_alloc_symbol(e->left.sym));
620 if (e->right.sym == &symbol_mod) {
621 // A=m -> n
622 printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name);
623 e = expr_alloc_symbol(&symbol_no);
626 if (e->right.sym == &symbol_yes) {
627 // A=y -> A
628 e = expr_alloc_symbol(e->left.sym);
633 if (e->left.sym->type != S_BOOLEAN)
635 if (e->right.sym == &symbol_no) {
636 // A!=n -> A
637 e = expr_alloc_symbol(e->left.sym);
640 if (e->right.sym == &symbol_mod) {
641 // A!=m -> y
642 printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name);
643 e = expr_alloc_symbol(&symbol_yes);
646 if (e->right.sym == &symbol_yes) {
647 // A!=y -> !A
648 e = expr_alloc_one(E_NOT, e->left.expr);
653 switch (e->left.expr->type) {
655 // !!A -> A
656 e = e->left.expr->left.expr;
660 // !(A=B) -> A!=B
661 e = expr_alloc_comp(e->left.expr->type == E_EQUAL ? E_UNEQUAL : E_EQUAL,
662 e->left.expr->left.sym,
663 e->left.expr->right.sym);
667 // !(A<=B) -> A>B
668 e = expr_alloc_comp(e->left.expr->type == E_LEQ ? E_GTH : E_LTH,
669 e->left.expr->left.sym,
670 e->left.expr->right.sym);
674 // !(A<B) -> A>=B
675 e = expr_alloc_comp(e->left.expr->type == E_LTH ? E_GEQ : E_LEQ,
676 e->left.expr->left.sym,
677 e->left.expr->right.sym);
680 // !(A || B) -> !A && !B
681 e = expr_alloc_and(expr_alloc_one(E_NOT, e->left.expr->left.expr),
682 expr_alloc_one(E_NOT, e->left.expr->right.expr));
683 e = expr_transform(e);
686 // !(A && B) -> !A || !B
687 e = expr_alloc_or(expr_alloc_one(E_NOT, e->left.expr->left.expr),
688 expr_alloc_one(E_NOT, e->left.expr->right.expr));
689 e = expr_transform(e);
692 if (e->left.expr->left.sym == &symbol_yes)
693 // !'y' -> 'n'
694 e = expr_alloc_symbol(&symbol_no);
695 else if (e->left.expr->left.sym == &symbol_mod)
696 // !'m' -> 'm'
697 e = expr_alloc_symbol(&symbol_mod);
698 else if (e->left.expr->left.sym == &symbol_no)
699 // !'n' -> 'y'
700 e = expr_alloc_symbol(&symbol_yes);
709 return e;
717 switch (dep->type) {
720 return expr_contains_symbol(dep->left.expr, sym) ||
721 expr_contains_symbol(dep->right.expr, sym);
723 return dep->left.sym == sym;
730 return dep->left.sym == sym ||
731 dep->right.sym == sym;
733 return expr_contains_symbol(dep->left.expr, sym);
745 switch (dep->type) {
747 return expr_depends_symbol(dep->left.expr, sym) ||
748 expr_depends_symbol(dep->right.expr, sym);
750 return dep->left.sym == sym;
752 if (dep->left.sym == sym) {
753 if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod)
758 if (dep->left.sym == sym) {
759 if (dep->right.sym == &symbol_no)
771 * expression 'e'.
775 * A -> A!=n
776 * !A -> A=n
777 * A && B -> !(A=n || B=n)
778 * A || B -> !(A=n && B=n)
779 * A && (B || C) -> !(A=n || (B=n && C=n))
783 struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)
787 if (!e) {
788 e = expr_alloc_symbol(sym);
790 e = expr_alloc_one(E_NOT, e);
791 return e;
793 switch (e->type) {
795 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
796 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
798 e = expr_alloc_two(E_AND, e1, e2);
800 e = expr_alloc_two(E_OR, e1, e2);
802 e = expr_alloc_one(E_NOT, e);
803 return e;
805 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
806 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
808 e = expr_alloc_two(E_OR, e1, e2);
810 e = expr_alloc_two(E_AND, e1, e2);
812 e = expr_alloc_one(E_NOT, e);
813 return e;
815 return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym);
824 return e;
828 return expr_alloc_one(E_NOT, e);
831 return expr_alloc_one(E_NOT, e);
835 return e;
839 return expr_alloc_comp(type, e->left.sym, sym);
869 val->s = !strcmp(str, "n") ? 0 :
871 !strcmp(str, "y") ? 2 : -1;
874 val->s = strtoll(str, &tail, 10);
878 val->u = strtoull(str, &tail, 16);
882 val->s = strtoll(str, &tail, 0);
886 return !errno && !*tail && tail > str && isxdigit(tail[-1])
890 static tristate __expr_calc_value(struct expr *e)
898 switch (e->type) {
900 sym_calc_value(e->left.sym);
901 return e->left.sym->curr.tri;
903 val1 = expr_calc_value(e->left.expr);
904 val2 = expr_calc_value(e->right.expr);
907 val1 = expr_calc_value(e->left.expr);
908 val2 = expr_calc_value(e->right.expr);
911 val1 = expr_calc_value(e->left.expr);
921 printf("expr_calc_value: %d?\n", e->type);
925 sym_calc_value(e->left.sym);
926 sym_calc_value(e->right.sym);
927 str1 = sym_get_string_value(e->left.sym);
928 str2 = sym_get_string_value(e->right.sym);
930 if (e->left.sym->type != S_STRING || e->right.sym->type != S_STRING) {
931 k1 = expr_parse_string(str1, e->left.sym->type, &lval);
932 k2 = expr_parse_string(str2, e->right.sym->type, &rval);
938 res = (lval.u > rval.u) - (lval.u < rval.u);
940 res = (lval.s > rval.s) - (lval.s < rval.s);
942 switch(e->type) {
956 printf("expr_calc_value: relation %d?\n", e->type);
962 * expr_calc_value - return the tristate value of the given expression
963 * @e: expression
966 tristate expr_calc_value(struct expr *e)
968 if (!e)
971 if (!e->val_is_valid) {
972 e->val = __expr_calc_value(e);
973 e->val_is_valid = true;
976 return e->val;
980 * expr_invalidate_all - invalidate all cached expression values
984 struct expr *e;
986 hash_for_each(expr_hashtable, e, node)
987 e->val_is_valid = false;
1021 void expr_print(const struct expr *e,
1025 if (!e) {
1030 if (expr_compare_type(prevtoken, e->type) > 0)
1032 switch (e->type) {
1034 if (e->left.sym->name)
1035 fn(data, e->left.sym, e->left.sym->name);
1041 expr_print(e->left.expr, fn, data, E_NOT);
1044 if (e->left.sym->name)
1045 fn(data, e->left.sym, e->left.sym->name);
1049 fn(data, e->right.sym, e->right.sym->name);
1053 if (e->left.sym->name)
1054 fn(data, e->left.sym, e->left.sym->name);
1057 fn(data, NULL, e->type == E_LEQ ? "<=" : "<");
1058 fn(data, e->right.sym, e->right.sym->name);
1062 if (e->left.sym->name)
1063 fn(data, e->left.sym, e->left.sym->name);
1066 fn(data, NULL, e->type == E_GEQ ? ">=" : ">");
1067 fn(data, e->right.sym, e->right.sym->name);
1070 if (e->left.sym->name)
1071 fn(data, e->left.sym, e->left.sym->name);
1075 fn(data, e->right.sym, e->right.sym->name);
1078 expr_print(e->left.expr, fn, data, E_OR);
1080 expr_print(e->right.expr, fn, data, E_OR);
1083 expr_print(e->left.expr, fn, data, E_AND);
1085 expr_print(e->right.expr, fn, data, E_AND);
1089 fn(data, e->left.sym, e->left.sym->name);
1091 fn(data, e->right.sym, e->right.sym->name);
1097 sprintf(buf, "<unknown type %d>", e->type);
1102 if (expr_compare_type(prevtoken, e->type) > 0)
1111 void expr_fprint(struct expr *e, FILE *out)
1113 expr_print(e, expr_print_file_helper, out, E_NONE);
1124 if (gs->max_width) {
1126 const char *last_cr = strrchr(gs->s, '\n');
1133 last_cr = gs->s;
1135 last_line_length = strlen(gs->s) - (last_cr - gs->s);
1137 if ((last_line_length + extra_length) > gs->max_width)
1142 if (sym && sym->type != S_UNKNOWN)
1146 void expr_gstr_print(const struct expr *e, struct gstr *gs)
1148 expr_print(e, expr_print_gstr_helper, gs, E_NONE);
1156 static void expr_print_revdep(struct expr *e,
1160 if (e->type == E_OR) {
1161 expr_print_revdep(e->left.expr, fn, data, pr_type, title);
1162 expr_print_revdep(e->right.expr, fn, data, pr_type, title);
1163 } else if (expr_calc_value(e) == pr_type) {
1169 fn(data, NULL, " - ");
1170 expr_print(e, fn, data, E_NONE);
1175 void expr_gstr_print_revdep(struct expr *e, struct gstr *gs,
1178 expr_print_revdep(e, expr_print_gstr_helper, gs, pr_type, &title);