Skip to content

Commit e911503

Browse files
Martin Walchmichal42
Martin Walch
authored and
michal42
committed
Kconfig: Remove bad inference rules expr_eliminate_dups2()
expr_eliminate_dups2() in scripts/kconfig/expr.c applies two invalid inference rules: (FOO || BAR) && (!FOO && !BAR) -> n (FOO && BAR) || (!FOO || !BAR) -> y They would be correct in propositional logic, but this is a three-valued logic, and here it is wrong in that it changes semantics. It becomes immediately visible when assigning the value 1 to both, FOO and BAR: (FOO || BAR) && (!FOO && !BAR) -> min(max(1, 1), min(2-1, 2-1)) = min(1, 1) = 1 while n evaluates to 0 and (FOO && BAR) || (!FOO || !BAR) -> max(min(1, 1), max(2-1, 2-1)) = max(1, 1) = 1 with y evaluating to 2. Fix it by removing expr_eliminate_dups2() and the functions that have no use anywhere else: expr_extract_eq_and(), expr_extract_eq_or(), and expr_extract_eq() from scripts/kconfig/expr.c Currently the bug is not triggered in mainline, so this patch does not modify the configuration space there. To observe the bug consider this example: config MODULES def_bool y option modules config FOO def_tristate m config BAR def_tristate m config TEST1 def_tristate y depends on (FOO || BAR) && (!FOO && !BAR) if TEST1 = n comment "TEST1 broken" endif config TEST2 def_tristate y depends on (FOO && BAR) || (!FOO || !BAR) if TEST2 = y comment "TEST2 broken" endif config TEST3 def_tristate y depends on m && !m if TEST3 = n comment "TEST3 broken" endif TEST1, TEST2 and TEST3 should all evaluate to m, but without the patch, none of them does. It is probably not obvious that TEST3 is the same bug, but it becomes clear when considering what happens internally to the expression m && !m": First it expands to (m && MODULES) && !(m && MODULES), then it is transformed into (m && MODULES) && (!m || !MODULES), and finally due to the bug it is replaced with n. As a side effect, this patch reduces code size in expr.c by roughly 10% and slightly improves startup time for all configuration frontends. Signed-off-by: Martin Walch <walch.martin@web.de> Signed-off-by: Michal Marek <mmarek@suse.cz>
1 parent b787f68 commit e911503

File tree

1 file changed

+0
-111
lines changed

1 file changed

+0
-111
lines changed

‎scripts/kconfig/expr.c

Lines changed: 0 additions & 111 deletions
Original file line numberDiff line numberDiff line change
@@ -13,9 +13,6 @@
1313

1414
static int expr_eq(struct expr *e1, struct expr *e2);
1515
static struct expr *expr_eliminate_yn(struct expr *e);
16-
static struct expr *expr_extract_eq_and(struct expr **ep1, struct expr **ep2);
17-
static struct expr *expr_extract_eq_or(struct expr **ep1, struct expr **ep2);
18-
static void expr_extract_eq(enum expr_type type, struct expr **ep, struct expr **ep1, struct expr **ep2);
1916

2017
struct expr *expr_alloc_symbol(struct symbol *sym)
2118
{
@@ -559,62 +556,6 @@ static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct
559556
#undef e2
560557
}
561558

562-
static void expr_eliminate_dups2(enum expr_type type, struct expr **ep1, struct expr **ep2)
563-
{
564-
#define e1 (*ep1)
565-
#define e2 (*ep2)
566-
struct expr *tmp, *tmp1, *tmp2;
567-
568-
if (e1->type == type) {
569-
expr_eliminate_dups2(type, &e1->left.expr, &e2);
570-
expr_eliminate_dups2(type, &e1->right.expr, &e2);
571-
return;
572-
}
573-
if (e2->type == type) {
574-
expr_eliminate_dups2(type, &e1, &e2->left.expr);
575-
expr_eliminate_dups2(type, &e1, &e2->right.expr);
576-
}
577-
if (e1 == e2)
578-
return;
579-
580-
switch (e1->type) {
581-
case E_OR:
582-
expr_eliminate_dups2(e1->type, &e1, &e1);
583-
// (FOO || BAR) && (!FOO && !BAR) -> n
584-
tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1)));
585-
tmp2 = expr_copy(e2);
586-
tmp = expr_extract_eq_and(&tmp1, &tmp2);
587-
if (expr_is_yes(tmp1)) {
588-
expr_free(e1);
589-
e1 = expr_alloc_symbol(&symbol_no);
590-
trans_count++;
591-
}
592-
expr_free(tmp2);
593-
expr_free(tmp1);
594-
expr_free(tmp);
595-
break;
596-
case E_AND:
597-
expr_eliminate_dups2(e1->type, &e1, &e1);
598-
// (FOO && BAR) || (!FOO || !BAR) -> y
599-
tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1)));
600-
tmp2 = expr_copy(e2);
601-
tmp = expr_extract_eq_or(&tmp1, &tmp2);
602-
if (expr_is_no(tmp1)) {
603-
expr_free(e1);
604-
e1 = expr_alloc_symbol(&symbol_yes);
605-
trans_count++;
606-
}
607-
expr_free(tmp2);
608-
expr_free(tmp1);
609-
expr_free(tmp);
610-
break;
611-
default:
612-
;
613-
}
614-
#undef e1
615-
#undef e2
616-
}
617-
618559
struct expr *expr_eliminate_dups(struct expr *e)
619560
{
620561
int oldcount;
@@ -627,7 +568,6 @@ struct expr *expr_eliminate_dups(struct expr *e)
627568
switch (e->type) {
628569
case E_OR: case E_AND:
629570
expr_eliminate_dups1(e->type, &e, &e);
630-
expr_eliminate_dups2(e->type, &e, &e);
631571
default:
632572
;
633573
}
@@ -829,57 +769,6 @@ bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
829769
return false;
830770
}
831771

832-
static struct expr *expr_extract_eq_and(struct expr **ep1, struct expr **ep2)
833-
{
834-
struct expr *tmp = NULL;
835-
expr_extract_eq(E_AND, &tmp, ep1, ep2);
836-
if (tmp) {
837-
*ep1 = expr_eliminate_yn(*ep1);
838-
*ep2 = expr_eliminate_yn(*ep2);
839-
}
840-
return tmp;
841-
}
842-
843-
static struct expr *expr_extract_eq_or(struct expr **ep1, struct expr **ep2)
844-
{
845-
struct expr *tmp = NULL;
846-
expr_extract_eq(E_OR, &tmp, ep1, ep2);
847-
if (tmp) {
848-
*ep1 = expr_eliminate_yn(*ep1);
849-
*ep2 = expr_eliminate_yn(*ep2);
850-
}
851-
return tmp;
852-
}
853-
854-
static void expr_extract_eq(enum expr_type type, struct expr **ep, struct expr **ep1, struct expr **ep2)
855-
{
856-
#define e1 (*ep1)
857-
#define e2 (*ep2)
858-
if (e1->type == type) {
859-
expr_extract_eq(type, ep, &e1->left.expr, &e2);
860-
expr_extract_eq(type, ep, &e1->right.expr, &e2);
861-
return;
862-
}
863-
if (e2->type == type) {
864-
expr_extract_eq(type, ep, ep1, &e2->left.expr);
865-
expr_extract_eq(type, ep, ep1, &e2->right.expr);
866-
return;
867-
}
868-
if (expr_eq(e1, e2)) {
869-
*ep = *ep ? expr_alloc_two(type, *ep, e1) : e1;
870-
expr_free(e2);
871-
if (type == E_AND) {
872-
e1 = expr_alloc_symbol(&symbol_yes);
873-
e2 = expr_alloc_symbol(&symbol_yes);
874-
} else if (type == E_OR) {
875-
e1 = expr_alloc_symbol(&symbol_no);
876-
e2 = expr_alloc_symbol(&symbol_no);
877-
}
878-
}
879-
#undef e1
880-
#undef e2
881-
}
882-
883772
struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)
884773
{
885774
struct expr *e1, *e2;

0 commit comments

Comments
 (0)