Skip to contentSkip to conversation

kconfig: Add support for conflict resolution

PATCH In review Ole Schuerks 4 participants 22 messages Feb 8, 2025 – Apr 9, 2025 1 message not in the archive

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

v7 cover kconfig: Add support for conflict resolution

Hi,

This patch series (for next-20250207) provides support to enable users to express their desired target configuration and display possible resolutions to their conflicts. This support is provided within xconfig.

Conflict resolution is provided by translating kconfig's configuration option tree to a propositional formula and allowing our resolution algorithm and PicoSAT to calculate the possible fixes for an expressed target kernel configuration. PicoSAT is the smallest and most robust C SAT solver we could find which is also GPL compatible. PicoSAT is used as a dynamically loaded library. For Debian and Fedora, the apt and dnf packages named "picosat" provide the library. For other distros, we provide instructions on how PicoSAT needs to be compiled from the sources in the documentation.

New UI extensions are made to xconfig with panes and buttons to allow users to express new desired target options, calculate fixes, and apply any of found solutions.

You can see a YouTube video demonstrating this work [2]. This effort is part of the kernelnewbies Kconfig-SAT project [3], the approach and effort is also explained in detail in our paper [4]. The results from the evaluation have significantly improved since then: Around 80 % of the conflicts could be resolved, and 99.9 % of the generated fixes resolved the conflict. It is also our attempt at contributing back to the kernel community, whose configurator researchers studied a lot.

Patches applicable to next-20250207.

[0] https://gsd.uwaterloo.ca/sites/default/files/vamos12-survey.pdf
[1] https://www.linux-magazine.com/Issues/2021/244/Kconfig-Deep-Dive
[2] https://www.youtube.com/watch?v=vn2JgK_PTbc
[3] https://kernelnewbies.org/KernelProjects/kconfig-sat
[4] http://www.cse.chalmers.se/~bergert/paper/2021-icseseip-configfix.pdf

Thanks from the team! (and thanks to Luis Chamberlain for guiding us here)

Changelog v7:
* improve error handling when loading picosat symbols with dlsym(): use dlerror() instead of checking for NULL
* move list_at_index from scripts/include/list.h to scripts/kconfig/cf_utils.h
* change interface of list_for_each_entry_from and rename list_size to list_count_nodes to more closely match scripts/include/list.h
* change misleading name "rangefix" of fix generation algorithm to "fixgen"

Changelog v6:
* remove script for manually installing PicoSAT
* adapt documentation and help text in the GUI accordingly
* convert Qt signal/slot connects to new style

Changelog v5:
* use lists from scripts/include/list.h
* use PicoSAT as a dynamically loaded library
* Fix GUI bug that made the displayed tables editable
* Allow cycling through the desired values of a symbol in the conflict view in the GUI by clicking on the cell
* Fix usage of "NO" instead of "N" etc. in some places in the GUI
* Improve function naming
* Add documentation
* Simlify xcalloc to xmalloc in some places
* Fix allocation bug in fexpr_add_to_satmap() and init_data()
* Remove functions pexpr_eliminate_dups() and print_expr()

Ole Schuerks (11):
kconfig: Add PicoSAT interface
kconfig: Add definitions
kbuild: Add list_count_nodes and list_for_each_entry_from
kconfig: Add files for building constraints
kconfig: Add files for handling expressions
kconfig: Add files for fix generation
kconfig: Add files with utility functions
kconfig: Add tools
kconfig: Add xconfig-modifications
kconfig: Add loader.gif
kconfig: Add documentation for the conflict resolver

 Documentation/kbuild/kconfig.rst    |   56 +
 scripts/include/list.h              |   26 +
 scripts/kconfig/.gitignore          |    1 +
 scripts/kconfig/Makefile            |   11 +-
 scripts/kconfig/cf_constraints.c    | 1777 ++++++++++++++++++++++++
 scripts/kconfig/cf_constraints.h    |   24 +
 scripts/kconfig/cf_defs.h           |  391 ++++++
 scripts/kconfig/cf_expr.c           | 2003 +++++++++++++++++++++++++++
 scripts/kconfig/cf_expr.h           |  181 +++
 scripts/kconfig/cf_fixgen.c         | 1136 +++++++++++++++
 scripts/kconfig/cf_fixgen.h         |   21 +
 scripts/kconfig/cf_utils.c          |  980 +++++++++++++
 scripts/kconfig/cf_utils.h          |  136 ++
 scripts/kconfig/cfoutconfig.c       |  149 ++
 scripts/kconfig/configfix.c         |  352 +++++
 scripts/kconfig/configfix.h         |   31 +
 scripts/kconfig/expr.h              |   17 +
 scripts/kconfig/loader.gif          |  Bin 0 -> 4177 bytes
 scripts/kconfig/picosat_functions.c |   79 ++
 scripts/kconfig/picosat_functions.h |   35 +
 scripts/kconfig/qconf.cc            |  676 ++++++++-
 scripts/kconfig/qconf.h             |  111 ++
 22 files changed, 8189 insertions(+), 4 deletions(-)
 create mode 100644 scripts/kconfig/cf_constraints.c
 create mode 100644 scripts/kconfig/cf_constraints.h
 create mode 100644 scripts/kconfig/cf_defs.h
 create mode 100644 scripts/kconfig/cf_expr.c
 create mode 100644 scripts/kconfig/cf_expr.h
 create mode 100644 scripts/kconfig/cf_fixgen.c
 create mode 100644 scripts/kconfig/cf_fixgen.h
 create mode 100644 scripts/kconfig/cf_utils.c
 create mode 100644 scripts/kconfig/cf_utils.h
 create mode 100644 scripts/kconfig/cfoutconfig.c
 create mode 100644 scripts/kconfig/configfix.c
 create mode 100644 scripts/kconfig/configfix.h
 create mode 100644 scripts/kconfig/loader.gif
 create mode 100644 scripts/kconfig/picosat_functions.c
 create mode 100644 scripts/kconfig/picosat_functions.h
Signature · 1 line
2.39.5
#1 lore raw

PATCH v7 1/11 kconfig: Add PicoSAT interface

PicoSAT [0] is the SAT solver used in this project. It is used as a dynamically loaded library. Add PicoSAT dynamic library support to kconfig, which will be used in the subsequent patches.

---
 scripts/kconfig/picosat_functions.c | 79 +++++++++++++++++++++++++++++
 scripts/kconfig/picosat_functions.h | 35 +++++++++++++
 2 files changed, 114 insertions(+)
 create mode 100644 scripts/kconfig/picosat_functions.c
 create mode 100644 scripts/kconfig/picosat_functions.h
scripts/kconfig/picosat_functions.c new file +79 -0
new file mode 100644
index 000000000000..dcfc80d418c2
@@ -0,0 +1,79 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <dlfcn.h>
+#include <unistd.h>
+
+#include "array_size.h"
+
+#include "cf_defs.h"
+#include "picosat_functions.h"
+
+const char *picosat_lib_names[] = { "libpicosat-trace.so",
+				    "libpicosat-trace.so.0",
+				    "libpicosat-trace.so.1" };
+
+PicoSAT *(*picosat_init)(void);
+int (*picosat_add)(PicoSAT *pico, int lit);
+int (*picosat_deref)(PicoSAT *pico, int lit);
+void (*picosat_assume)(PicoSAT *pico, int lit);
+int (*picosat_sat)(PicoSAT *pico, int decision_limit);
+const int *(*picosat_failed_assumptions)(PicoSAT *pico);
+int (*picosat_added_original_clauses)(PicoSAT *pico);
+int (*picosat_enable_trace_generation)(PicoSAT *pico);
+void (*picosat_print)(PicoSAT *pico, FILE *file);
+
+#define PICOSAT_FUNCTION_LIST              \
+	X(picosat_init)                    \
+	X(picosat_add)                     \
+	X(picosat_deref)                   \
+	X(picosat_assume)                  \
+	X(picosat_sat)                     \
+	X(picosat_failed_assumptions)      \
+	X(picosat_added_original_clauses)  \
+	X(picosat_enable_trace_generation) \
+	X(picosat_print)
+
+static void load_function(const char *name, void **ptr, void *handle,
+			  bool *failed)
+{
+	const char *error_str;
+
+	if (*failed)
+		return;
+
+	dlerror(); // clear error
+	*ptr = dlsym(handle, name);
+	error_str = dlerror();
+	if (error_str) {
+		printd("While loading %s: %s\n", name, error_str);
+		*failed = true;
+	}
+}
+
+bool load_picosat(void)
+{
+	void *handle = NULL;
+	bool failed = false;
+
+	/*
+	 * Try different names for the .so library. This is necessary since
+	 * all packages don't use the same versioning.
+	 */
+	for (int i = 0; i < ARRAY_SIZE(picosat_lib_names) && !handle; ++i)
+		handle = dlopen(picosat_lib_names[i], RTLD_LAZY);
+	if (!handle) {
+		printd("%s\n", dlerror());
+		return false;
+	}
+
+#define X(name) load_function(#name, (void **) &name, handle, &failed);
+
+	PICOSAT_FUNCTION_LIST
+#undef X
+
+	if (failed) {
+		dlclose(handle);
+		return false;
+	} else
+		return true;
+}
scripts/kconfig/picosat_functions.h new file +35 -0
new file mode 100644
index 000000000000..5d8524afa844
@@ -0,0 +1,35 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+
+#ifndef PICOSAT_FUNCTIONS_H
+#define PICOSAT_FUNCTIONS_H
+
+#include <stdbool.h>
+#include <stdio.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#define PICOSAT_UNKNOWN         0
+#define PICOSAT_SATISFIABLE     10
+#define PICOSAT_UNSATISFIABLE   20
+
+typedef struct PicoSAT PicoSAT;
+
+extern PicoSAT *(*picosat_init)(void);
+extern int (*picosat_add)(PicoSAT *pico, int lit);
+extern int (*picosat_deref)(PicoSAT *pico, int lit);
+extern void (*picosat_assume)(PicoSAT *pico, int lit);
+extern int (*picosat_sat)(PicoSAT *pico, int decision_limit);
+extern const int *(*picosat_failed_assumptions)(PicoSAT *pico);
+extern int (*picosat_added_original_clauses)(PicoSAT *pico);
+extern int (*picosat_enable_trace_generation)(PicoSAT *pico);
+extern void (*picosat_print)(PicoSAT *pico, FILE *file);
+
+bool load_picosat(void);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif // PICOSAT_FUNCTIONS_H
Signature · 1 line
2.39.5
Reviewed-by on v7 1/11
#2 lore raw

Re: [PATCH v7 01/11] kconfig: Add PicoSAT interface

Quoted 5 lines · Ole Schuerks
scripts/kconfig/picosat_functions.c new file +5 -0
+bool load_picosat(void)
+{
+	void *handle = NULL;
+	bool failed = false;
+

scripts/kconfig/picosat_functions.c line 67

Quoted 10 lines
scripts/kconfig/picosat_functions.c new file +10 -0
+	/*
+	 * Try different names for the .so library. This is necessary since
+	 * all packages don't use the same versioning.
+	 */
+	for (int i = 0; i < ARRAY_SIZE(picosat_lib_names) && !handle; ++i)
+		handle = dlopen(picosat_lib_names[i], RTLD_LAZY);
+	if (!handle) {
+		printd("%s\n", dlerror());
+		return false;
+	}

This will only detect an error if the last dlopen() failed.

Other than that:

Luis

#3 lore raw

PATCH v7 2/11 kconfig: Add definitions

In reply to Ole Schuerks

Add structs that are used to store constraints of symbols and prepare the Makefile.

---
 scripts/kconfig/Makefile  |  11 +-
 scripts/kconfig/cf_defs.h | 391 ++++++++++++++++++++++++++++++++++++++
 scripts/kconfig/expr.h    |  17 ++
 3 files changed, 417 insertions(+), 2 deletions(-)
 create mode 100644 scripts/kconfig/cf_defs.h
scripts/kconfig/Makefile +9 -2
index fb50bd4f4103..db3069c13064 100644
@@ -43,6 +43,7 @@ menuconfig-prog	:= mconf
 nconfig-prog	:= nconf
 gconfig-prog	:= gconf
 xconfig-prog	:= qconf
+cfoutconfig-prog := cfoutconfig
 
 define config_rule
 PHONY += $(1)
@@ -53,7 +54,7 @@ PHONY += build_$(1)
 build_$(1): $(obj)/$($(1)-prog)
 endef
 
-$(foreach c, config menuconfig nconfig gconfig xconfig, $(eval $(call config_rule,$(c))))
+$(foreach c, config menuconfig nconfig gconfig xconfig cfoutconfig, $(eval $(call config_rule,$(c))))
 
 PHONY += localmodconfig localyesconfig
 localyesconfig localmodconfig: $(obj)/conf
@@ -154,6 +155,7 @@ help:
 	@echo  '                    default value without prompting'
 	@echo  '  tinyconfig	  - Configure the tiniest possible kernel'
 	@echo  '  testconfig	  - Run Kconfig unit tests (requires python3 and pytest)'
+	@echo  '  cfoutconfig     - Print constraints and DIMACS-output into files (requires PicoSAT)'
 	@echo  ''
 	@echo  'Configuration topic targets:'
 	@$(foreach f, $(all-config-fragments), \
@@ -198,10 +200,15 @@ $(foreach f, mconf.o $(lxdialog), \
 $(obj)/mconf: | $(obj)/mconf-libs
 $(addprefix $(obj)/, mconf.o $(lxdialog)): | $(obj)/mconf-cflags
 
+# configfix: Used for the xconfig target as well as for its debugging tools
+hostprogs        += cfoutconfig
+cfconf-objs      := configfix.o cf_constraints.o cf_expr.o cf_fixgen.o cf_utils.o picosat_functions.o
+cfoutconfig-objs := cfoutconfig.o $(common-objs) $(cfconf-objs)
+
 # qconf: Used for the xconfig target based on Qt
 hostprogs	+= qconf
 qconf-cxxobjs	:= qconf.o qconf-moc.o
-qconf-objs	:= images.o $(common-objs)
+qconf-objs	:= images.o $(common-objs) $(cfconf-objs)
 
 HOSTLDLIBS_qconf         = $(call read-file, $(obj)/qconf-libs)
 HOSTCXXFLAGS_qconf.o     = -std=c++11 -fPIC $(call read-file, $(obj)/qconf-cflags)
scripts/kconfig/cf_defs.h new file +391 -0

391 lines not on this page · raw message

scripts/kconfig/expr.h +17 -0
index 21578dcd4292..1b5427fe90e5 100644
@@ -140,6 +140,19 @@ struct symbol {
 	 * "Weak" reverse dependencies through being implied by other symbols
 	 */
 	struct expr_value implied;
+
+	/*
+	 * ConfigFix
+	 */
+	struct fexpr *fexpr_y;
+	struct fexpr *fexpr_m;
+	struct fexpr *fexpr_sel_y;
+	struct fexpr *fexpr_sel_m;
+	struct pexpr *list_sel_y;
+	struct pexpr *list_sel_m;
+	struct fexpr *noPromptCond;
+	struct fexpr_list *nb_vals; /* list of struct fexpr_node's; used for non-booleans */
+	struct pexpr_list *constraints; /* list of constraints for symbol */
 };
 
 #define SYMBOL_CONST      0x0001  /* symbol is const */
@@ -201,6 +214,10 @@ struct property {
 	for (st = sym->prop; st; st = st->next) \
 		if (st->type == (tok))
 #define for_all_defaults(sym, st) for_all_properties(sym, st, P_DEFAULT)
+#define for_all_choices(symbol, child, menu_ptr) \
+	list_for_each_entry(menu_ptr, &(symbol)->menus, link) \
+		for (child = (menu_ptr)->list; child; child = (child)->next) \
+			if ((child)->sym && sym_is_choice_value((child)->sym))
 #define for_all_prompts(sym, st) \
 	for (st = sym->prop; st; st = st->next) \
 		if (st->text)
Signature · 1 line
2.39.5
#4 lore raw

PATCH v7 3/11 kbuild: Add list_count_nodes and list_for_each_entry_from

In reply to Ole Schuerks

list_count_nodes and list_for_each_entry_from exist in include/linux/list.h. Add them to scripts/include/list.h.

---
 scripts/include/list.h | 26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)
scripts/include/list.h +26 -0
index 8bdcaadca709..b60f1cc878f1 100644
@@ -219,6 +219,20 @@ static inline int list_empty(const struct list_head *head)
 	return head->next == head;
 }
 
+/**
+ * list_count_nodes - count nodes in the list
+ * @head:	the head for your list.
+ */
+static inline size_t list_count_nodes(struct list_head *head)
+{
+	size_t count = 0;
+
+	for (struct list_head *pos = head->next; pos != head; pos = pos->next)
+		++count;
+
+	return count;
+}
+
 /**
  * list_entry - get the struct for this entry
  * @ptr:	the &struct list_head pointer.
@@ -310,6 +324,18 @@ static inline int list_empty(const struct list_head *head)
 	     !list_entry_is_head(pos, head, member);			\
 	     pos = n, n = list_next_entry(n, member))
 
+/**
+ * list_for_each_entry_from - iterate over list of given type from the current point
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your list.
+ * @member:	the name of the list_head within the struct.
+ *
+ * Iterate over list of given type, continuing from current position.
+ */
+#define list_for_each_entry_from(pos, head, member)			\
+	for (; !list_entry_is_head(pos, head, member);			\
+	     pos = list_next_entry(pos, member))
+
 /*
  * Double linked lists with a single pointer list head.
  * Mostly useful for hash tables where the two pointer list head is
Signature · 1 line
2.39.5
#6 lore raw

PATCH v7 4/11 kconfig: Add files for building constraints

In reply to Ole Schuerks

Add files for the translation of the Kconfig-model into propositional logic. The translation associates constraints in propositional logic with the individual symbols.

---
 scripts/kconfig/cf_constraints.c | 1777 ++++++++++++++++++++++++++++++
 scripts/kconfig/cf_constraints.h |   24 +
 2 files changed, 1801 insertions(+)
 create mode 100644 scripts/kconfig/cf_constraints.c
 create mode 100644 scripts/kconfig/cf_constraints.h
scripts/kconfig/cf_constraints.c new file +1777 -0
new file mode 100644
index 000000000000..886cf12868ad
@@ -0,0 +1,1777 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * Copyright (C) 2023 Patrick Franz <[email protected]>
+ */
+
+#include "cf_defs.h"
+#include "expr.h"
+#include "list.h"
+#define _GNU_SOURCE
+#include <assert.h>
+#include <locale.h>
+#include <stdarg.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include <unistd.h>
+
+#include "cf_utils.h"
+#include "internal.h"
+#include "cf_expr.h"
+#include "cf_constraints.h"
+#include "../include/list.h"
+
+#define KCR_CMP false
+#define NPC_OPTIMISATION true
+
+static void find_nonboolean_known_vals(struct cfdata *data);
+static void build_constraints_bool(struct cfdata *data);
+static void build_constraints_select(struct cfdata *data);
+static void build_constraints_nonbool(struct cfdata *data);
+
+static void build_tristate_constraint_clause(struct symbol *sym,
+					     struct cfdata *data);
+
+static void add_selects_kcr(struct symbol *sym, struct cfdata *data);
+static void add_selects(struct symbol *sym, struct cfdata *data);
+
+static void add_dependencies_bool(struct symbol *sym, struct cfdata *data);
+static void add_dependencies_bool_kcr(struct symbol *sym, struct cfdata *data);
+static void add_dependencies_nonbool(struct symbol *sym, struct cfdata *data);
+
+static void add_choice_prompt_cond(struct symbol *sym, struct cfdata *data);
+static void add_choice_dependencies(struct symbol *sym, struct cfdata *data);
+static void add_choice_constraints(struct symbol *sym, struct cfdata *data);
+static void add_invisible_constraints(struct symbol *sym, struct cfdata *data);
+static void sym_nonbool_at_least_1(struct symbol *sym, struct cfdata *data);
+static void sym_nonbool_at_most_1(struct symbol *sym, struct cfdata *data);
+static void sym_add_nonbool_values_from_default_range(struct symbol *sym,
+						      struct cfdata *data);
+static void sym_add_range_constraints(struct symbol *sym, struct cfdata *data);
+static void sym_add_nonbool_prompt_constraint(struct symbol *sym,
+					      struct cfdata *data);
+
+static struct default_map *create_default_map_entry(struct fexpr *val,
+						    struct pexpr *e);
+static struct defm_list *calc_default_conditions(struct symbol *sym, struct cfdata *data);
+static struct pexpr *get_default_y(struct defm_list *list, struct cfdata *data);
+static struct pexpr *get_default_m(struct defm_list *list, struct cfdata *data);
+static struct pexpr *get_default_any(struct symbol *sym, struct cfdata *data);
+static long sym_get_range_val(struct symbol *sym, int base);
+
+/* -------------------------------------- */
+
+/*
+ * build the constraints for each symbol
+ */
+void build_constraints(struct cfdata *data)
+{
+	printd("Building constraints...");
+
+	find_nonboolean_known_vals(data);
+	build_constraints_bool(data);
+	build_constraints_select(data);
+	build_constraints_nonbool(data);
+}
+
+/*
+ * need to go through the constraints once to find all "known values"
+ * for the non-Boolean symbols (and add them to sym->nb_vals for the given
+ * symbols).
+ * expr_calculate_pexpr_both and get_defaults have the side effect of creating
+ * known values.
+ */
+static void find_nonboolean_known_vals(struct cfdata *data)
+{
+	struct symbol *sym;
+	struct property *p;
+
+	for_all_symbols(sym) {
+		struct property *prompt;
+
+		if (sym->type == S_UNKNOWN)
+			continue;
+
+		if (sym_is_boolean(sym)) {
+			for_all_properties(sym, p, P_SELECT)
+				pexpr_put(expr_calculate_pexpr_both(
+					p->visible.expr, data));
+
+			for_all_properties(sym, p, P_IMPLY)
+				pexpr_put(expr_calculate_pexpr_both(
+					p->visible.expr, data));
+		}
+
+		if (sym->dir_dep.expr)
+			pexpr_put(expr_calculate_pexpr_both(sym->dir_dep.expr,
+							    data));
+
+		prompt = sym_get_prompt(sym);
+		if (prompt != NULL && prompt->visible.expr) {
+			pexpr_put(expr_calculate_pexpr_both(
+				prompt->visible.expr, data));
+			defm_list_destruct(calc_default_conditions(sym, data));
+		}
+
+		if (sym_is_nonboolean(sym)) {
+			const char *curr;
+
+			for_all_defaults(sym, p) {
+				if (p == NULL)
+					continue;
+
+				sym_create_nonbool_fexpr(
+					sym, p->expr->left.sym->name, data);
+			}
+			for_all_properties(sym, p, P_RANGE) {
+				if (p == NULL)
+					continue;
+
+				sym_create_nonbool_fexpr(
+					sym, p->expr->left.sym->name, data);
+				sym_create_nonbool_fexpr(
+					sym, p->expr->right.sym->name, data);
+			}
+			curr = sym_get_string_value(sym);
+			if (strcmp(curr, "") != 0)
+				sym_create_nonbool_fexpr(sym, (char *)curr,
+							 data);
+		}
+
+		if (sym->type == S_HEX || sym->type == S_INT)
+			sym_add_nonbool_values_from_default_range(sym, data);
+	}
+}
+
+/*
+ *  build constraints for boolean symbols
+ */
+static void build_constraints_bool(struct cfdata *data)
+{
+	struct symbol *sym;
+
+	for_all_symbols(sym) {
+		if (!sym_is_boolean(sym))
+			continue;
+
+		/* build tristate constraints */
+		if (sym->type == S_TRISTATE)
+			build_tristate_constraint_clause(sym, data);
+
+		/* build constraints for select statements
+		 * need to treat choice symbols separately
+		 */
+		if (!KCR_CMP) {
+			add_selects(sym, data);
+		} else {
+			if (sym->rev_dep.expr && !sym_is_choice(sym) &&
+			    !sym_is_choice_value(sym))
+				add_selects_kcr(sym, data);
+		}
+
+		/* build constraints for dependencies for booleans */
+		if (sym->dir_dep.expr && !sym_is_choice(sym) &&
+		    !sym_is_choice_value(sym)) {
+			if (!KCR_CMP)
+				add_dependencies_bool(sym, data);
+			else
+				add_dependencies_bool_kcr(sym, data);
+		}
+
+		/* build constraints for choice prompts */
+		if (sym_is_choice(sym))
+			add_choice_prompt_cond(sym, data);
+
+		/*
+		 * build constraints for dependencies (choice symbols and
+		 * options)
+		 */
+		if (sym_is_choice(sym) || sym_is_choice_value(sym))
+			add_choice_dependencies(sym, data);
+
+		/* build constraints for the choice groups */
+		if (sym_is_choice(sym))
+			add_choice_constraints(sym, data);
+
+		/* build invisible constraints */
+		add_invisible_constraints(sym, data);
+	}
+}
+
+/*
+ * build the constraints for select-variables
+ * skip non-Booleans, choice symbols/options och symbols without rev_dir
+ */
+static void build_constraints_select(struct cfdata *data)
+{
+	struct symbol *sym;
+
+	for_all_symbols(sym) {
+		struct pexpr *sel_y, *sel_m;
+		struct pexpr *c1, *c2;
+
+		if (KCR_CMP)
+			continue;
+
+		if (!sym_is_boolean(sym))
+			continue;
+
+		if (sym_is_choice(sym) || sym_is_choice_value(sym))
+			continue;
+
+		if (!sym->rev_dep.expr)
+			continue;
+
+		if (sym->list_sel_y == NULL)
+			continue;
+
+		sel_y = pexpr_implies(pexpr_alloc_symbol(sym->fexpr_sel_y),
+				      pexpr_alloc_symbol(sym->fexpr_y), data,
+				      PEXPR_ARGX);
+		sym_add_constraint(sym, sel_y, data);
+
+		c1 = pexpr_implies(pexpr_alloc_symbol(sym->fexpr_sel_y),
+				   sym->list_sel_y, data, PEXPR_ARG1);
+		sym_add_constraint(sym, c1, data);
+
+		/* only continue for tristates */
+		if (sym->type == S_BOOLEAN)
+			continue;
+
+		sel_m = pexpr_implies(pexpr_alloc_symbol(sym->fexpr_sel_m),
+					   sym_get_fexpr_both(sym, data), data,
+					   PEXPR_ARGX);
+		sym_add_constraint(sym, sel_m, data);
+
+		c2 = pexpr_implies(pexpr_alloc_symbol(sym->fexpr_sel_m),
+				   sym->list_sel_m, data, PEXPR_ARG1);
+		sym_add_constraint(sym, c2, data);
+		PEXPR_PUT(sel_y, sel_m, c1, c2);
+	}
+}
+
+/*
+ * build constraints for non-booleans
+ */
+static void build_constraints_nonbool(struct cfdata *data)
+{
+	struct symbol *sym;
+
+	for_all_symbols(sym) {
+		if (!sym_is_nonboolean(sym))
+			continue;
+
+		/* the symbol must have a value, if there is a prompt */
+		if (sym_has_prompt(sym))
+			sym_add_nonbool_prompt_constraint(sym, data);
+
+		/* build the range constraints for int/hex */
+		if (sym->type == S_HEX || sym->type == S_INT)
+			sym_add_range_constraints(sym, data);
+
+		/* build constraints for dependencies for non-booleans */
+		if (sym->dir_dep.expr)
+			add_dependencies_nonbool(sym, data);
+
+		/* build invisible constraints */
+		add_invisible_constraints(sym, data);
+
+		/* exactly one of the symbols must be true */
+		sym_nonbool_at_least_1(sym, data);
+		sym_nonbool_at_most_1(sym, data);
+	}
+}
+
+/*
+ * enforce tristate constraints
+ */
+static void build_tristate_constraint_clause(struct symbol *sym,
+					     struct cfdata *data)
+{
+	struct pexpr *X, *X_m, *modules, *c;
+
+	if (sym->type != S_TRISTATE)
+		return;
+
+	X = pexpr_alloc_symbol(sym->fexpr_y);
+	X_m = pexpr_alloc_symbol(sym->fexpr_m);
+	modules = pexpr_alloc_symbol(modules_sym->fexpr_y);
+
+	/* -X v -X_m */
+	c = pexpr_or(pexpr_not_share(X, data), pexpr_not_share(X_m, data),
+			  data, PEXPR_ARGX);
+	sym_add_constraint(sym, c, data);
+
+	/* X_m -> MODULES */
+	if (modules_sym->fexpr_y != NULL) {
+		struct pexpr *c2 = pexpr_implies_share(X_m, modules, data);
+
+		sym_add_constraint(sym, c2, data);
+		PEXPR_PUT(c2);
+	}
+	PEXPR_PUT(X, X_m, modules, c);
+}
+
+/*
+ * build the select constraints
+ * - RDep(X) implies X
+ */
+static void add_selects_kcr(struct symbol *sym, struct cfdata *data)
+{
+	struct pexpr *rdep_y = expr_calculate_pexpr_y(sym->rev_dep.expr, data);
+	struct pexpr *c1 = pexpr_implies(
+		rdep_y, pexpr_alloc_symbol(sym->fexpr_y), data, PEXPR_ARG2);
+
+	struct pexpr *rdep_both =
+		expr_calculate_pexpr_both(sym->rev_dep.expr, data);
+	struct pexpr *c2 = pexpr_implies(
+		rdep_both, sym_get_fexpr_both(sym, data), data, PEXPR_ARG2);
+
+	sym_add_constraint(sym, c1, data);
+	sym_add_constraint(sym, c2, data);
+	PEXPR_PUT(rdep_y, c1, rdep_both, c2);
+}
+
+/*
+ * build the select constraints simplified
+ * - RDep(X) implies X
+ */
+static void add_selects(struct symbol *sym, struct cfdata *data)
+{
+	struct property *p;
+
+	if (!sym_is_boolean(sym))
+		return;
+
+	for_all_properties(sym, p, P_SELECT) {
+		struct symbol *selected = p->expr->left.sym;
+		struct pexpr *cond_y, *cond_both;
+
+		if (selected->type == S_UNKNOWN)
+			continue;
+
+		if (!selected->rev_dep.expr)
+			continue;
+
+		if (p->visible.expr) {
+			cond_y = expr_calculate_pexpr_y(p->visible.expr, data);
+			cond_both = expr_calculate_pexpr_both(p->visible.expr,
+							      data);
+		} else {
+			cond_y =
+				pexpr_alloc_symbol(data->constants->const_true);
+			cond_both =
+				pexpr_alloc_symbol(data->constants->const_true);
+		}
+
+		if (selected->type == S_BOOLEAN) {
+			/* imply that symbol is selected to y */
+			struct pexpr *e1 = pexpr_and(
+				cond_both, sym_get_fexpr_both(sym, data), data,
+				PEXPR_ARG2);
+			struct pexpr *c1 = pexpr_implies(
+				e1, pexpr_alloc_symbol(selected->fexpr_sel_y),
+				data, PEXPR_ARG2);
+
+			sym_add_constraint(selected, c1, data);
+
+			if (selected->list_sel_y == NULL)
+				selected->list_sel_y = pexpr_get(e1);
+			else
+				selected->list_sel_y =
+					pexpr_or(selected->list_sel_y, e1, data,
+						 PEXPR_ARG1);
+			PEXPR_PUT(e1, c1);
+		}
+
+		if (selected->type == S_TRISTATE) {
+			struct pexpr *e2, *e3, *c2, *c3;
+
+			/* imply that symbol is selected to y */
+			e2 = pexpr_and(cond_y, pexpr_alloc_symbol(sym->fexpr_y),
+				       data, PEXPR_ARG2);
+			c2 = pexpr_implies(
+				e2, pexpr_alloc_symbol(selected->fexpr_sel_y),
+				data, PEXPR_ARG2);
+			sym_add_constraint(selected, c2, data);
+
+			if (selected->list_sel_y == NULL)
+				selected->list_sel_y = pexpr_get(e2);
+			else
+				selected->list_sel_y =
+					pexpr_or(selected->list_sel_y, e2,
+						      data, PEXPR_ARG1);
+
+			/* imply that symbol is selected to m */
+			e3 = pexpr_and(cond_both, sym_get_fexpr_both(sym, data),
+				       data, PEXPR_ARG2);
+			c3 = pexpr_implies(
+				e3, pexpr_alloc_symbol(selected->fexpr_sel_m),
+				data, PEXPR_ARG2);
+			sym_add_constraint(selected, c3, data);
+
+			if (selected->list_sel_m == NULL)
+				selected->list_sel_m = pexpr_get(e3);
+			else
+				selected->list_sel_m =
+					pexpr_or(selected->list_sel_m, e3,
+						      data, PEXPR_ARG1);
+			PEXPR_PUT(e2, c2, e3, c3);
+		}
+		PEXPR_PUT(cond_y, cond_both);
+	}
+}
+
+/*
+ * build the dependency constraints for booleans
+ *  - X implies Dep(X) or RDep(X)
+ */
+static void add_dependencies_bool(struct symbol *sym, struct cfdata *data)
+{
+	struct pexpr *dep_both;
+	struct pexpr *visible_m;
+	struct pexpr *visible_y;
+	struct pexpr *visible_both;
+	struct property *prompt;
+	struct pexpr *has_prompt;
+	struct pexpr *sel_y;
+
+	if (!sym_is_boolean(sym) || !sym->dir_dep.expr)
+		return;
+
+	prompt = sym_get_prompt(sym);
+	if (!prompt) {
+		visible_m = pexpr_alloc_symbol(data->constants->const_false);
+		visible_y = pexpr_get(visible_m);
+		visible_both = pexpr_get(visible_m);
+	} else if (prompt->expr == NULL) {
+		visible_m = pexpr_alloc_symbol(data->constants->const_true);
+		visible_y = pexpr_get(visible_m);
+		visible_both = pexpr_get(visible_m);
+	} else {
+		visible_m = expr_calculate_pexpr_m(prompt->expr, data);
+		visible_y = expr_calculate_pexpr_y(prompt->expr, data);
+		visible_both = pexpr_or_share(visible_y, visible_m, data);
+	}
+
+	dep_both = expr_calculate_pexpr_both(sym->dir_dep.expr, data);
+
+	sel_y = sym->rev_dep.expr ?
+			pexpr_alloc_symbol(sym->fexpr_sel_y) :
+			pexpr_alloc_symbol(data->constants->const_false);
+	has_prompt = pexpr_get(visible_both);
+	has_prompt = pexpr_and(
+			has_prompt,
+			pexpr_not(pexpr_and_share(sel_y, visible_m, data),
+				data),
+			data, PEXPR_ARGX);
+
+	if (sym->type == S_TRISTATE) {
+		struct pexpr *c1;
+		struct pexpr *c2;
+		struct pexpr *dep_y =
+			expr_calculate_pexpr_y(sym->dir_dep.expr, data);
+		struct pexpr *sel_both = sym_get_fexpr_sel_both(sym, data);
+		struct pexpr *cond_y1;
+		struct pexpr *cond_y2;
+		struct pexpr *cond_y;
+		struct pexpr *cond_m1;
+		struct pexpr *cond_m2;
+		struct pexpr *cond_m;
+
+		cond_y1 = pexpr_implies(pexpr_not_share(has_prompt, data),
+					pexpr_or_share(dep_y, sel_y, data),
+					data, PEXPR_ARGX);
+		cond_y2 = pexpr_implies_share(has_prompt, visible_y, data);
+		cond_y = pexpr_and_share(cond_y1, cond_y2, data);
+		cond_m1 =
+			pexpr_implies(pexpr_not_share(has_prompt, data),
+				      pexpr_or_share(dep_both, sel_both, data),
+				      data, PEXPR_ARGX);
+		cond_m2 = pexpr_implies(has_prompt,
+					pexpr_not_share(sel_y, data), data,
+					PEXPR_ARG2);
+		cond_m = pexpr_and_share(cond_m1, cond_m2, data);
+		c1 = pexpr_implies(pexpr_alloc_symbol(sym->fexpr_y), cond_y,
+				   data, PEXPR_ARG1);
+		c2 = pexpr_implies(pexpr_alloc_symbol(sym->fexpr_m), cond_m,
+				   data, PEXPR_ARG1);
+
+		sym_add_constraint(sym, c1, data);
+		sym_add_constraint(sym, c2, data);
+		PEXPR_PUT(c1, c2, dep_y, sel_both, cond_y1,
+			  cond_y2, cond_y, cond_m1, cond_m2, cond_m);
+	} else if (sym->type == S_BOOLEAN) {
+		struct pexpr *cond1;
+		struct pexpr *cond2;
+		struct pexpr *c;
+
+		cond1 = pexpr_implies(pexpr_not_share(has_prompt, data),
+				      pexpr_or(dep_both,
+					       pexpr_alloc_symbol(sym->fexpr_m),
+					       data, PEXPR_ARG2),
+				      data, PEXPR_ARGX);
+		cond2 = pexpr_implies_share(has_prompt, visible_y, data);
+		c = pexpr_implies(pexpr_alloc_symbol(sym->fexpr_y),
+				  pexpr_and_share(cond1, cond2, data), data,
+				  PEXPR_ARGX);
+
+		sym_add_constraint(sym, c, data);
+		PEXPR_PUT(c, cond1, cond2);
+	}
+	PEXPR_PUT(dep_both, has_prompt, sel_y, visible_y, visible_m,
+		  visible_both);
+}
+
+/*
+ * build the dependency constraints for booleans (KCR)
+ *  - X implies Dep(X) or RDep(X)
+ */
+static void add_dependencies_bool_kcr(struct symbol *sym, struct cfdata *data)
+{
+	struct pexpr *dep_both, *sel_both;
+
+	if (!sym_is_boolean(sym) || !sym->dir_dep.expr)
+		return;
+
+	dep_both = expr_calculate_pexpr_both(sym->dir_dep.expr, data);
+
+	sel_both = sym->rev_dep.expr ?
+			   expr_calculate_pexpr_both(sym->rev_dep.expr, data) :
+			   pexpr_alloc_symbol(data->constants->const_false);
+
+	if (sym->type == S_TRISTATE) {
+		struct pexpr *c1;
+		struct pexpr *c2;
+		{
+			struct pexpr *dep_y =
+				expr_calculate_pexpr_y(sym->dir_dep.expr, data);
+			struct pexpr *sel_y =
+				sym->rev_dep.expr ?
+					expr_calculate_pexpr_y(
+						sym->rev_dep.expr, data) :
+					pexpr_alloc_symbol(
+						data->constants->const_false);
+			c1 = pexpr_implies(pexpr_alloc_symbol(sym->fexpr_y),
+						pexpr_or(dep_y, sel_y,
+							      data, PEXPR_ARGX),
+						data, PEXPR_ARGX);
+		}
+		c2 = pexpr_implies(pexpr_alloc_symbol(sym->fexpr_m),
+					pexpr_or_share(dep_both, sel_both,
+						       data),
+					data, PEXPR_ARGX);
+
+		sym_add_constraint(sym, c1, data);
+		sym_add_constraint(sym, c2, data);
+		PEXPR_PUT(c1, c2);
+	} else if (sym->type == S_BOOLEAN) {
+		struct pexpr *c = pexpr_implies(
+			pexpr_alloc_symbol(sym->fexpr_y),
+			pexpr_or_share(dep_both, sel_both, data), data,
+			PEXPR_ARGX);
+
+		sym_add_constraint(sym, c, data);
+		PEXPR_PUT(c);
+	}
+
+	PEXPR_PUT(dep_both, sel_both);
+}
+
+/*
+ * build the dependency constraints for non-booleans
+ *
+ * sym is not 'n' implies `sym->dir_dep`
+ */
+static void add_dependencies_nonbool(struct symbol *sym, struct cfdata *data)
+{
+	struct pexpr *dep_both;
+	struct pexpr *nb_vals; // "sym is set to some value" / "sym is not 'n'"
+	struct fexpr_node *node;
+	struct pexpr *c;
+	bool first = true;
+
+	if (!sym_is_nonboolean(sym) || !sym->dir_dep.expr || sym->rev_dep.expr)
+		return;
+
+	dep_both = expr_calculate_pexpr_both(sym->dir_dep.expr, data);
+
+	nb_vals = pexpr_alloc_symbol(data->constants->const_false);
+	/* can skip the first non-boolean value, since this is 'n' */
+	CF_LIST_FOR_EACH(node, sym->nb_vals, fexpr) {
+		if (first) {
+			first = false;
+			continue;
+		}
+
+		nb_vals = pexpr_or(nb_vals, pexpr_alloc_symbol(node->elem),
+				   data, PEXPR_ARGX);
+	}
+
+	c = pexpr_implies(nb_vals, dep_both, data, PEXPR_ARGX);
+	sym_add_constraint(sym, c, data);
+	pexpr_put(c);
+}
+
+/*
+ * build the constraints for the choice prompt
+ */
+static void add_choice_prompt_cond(struct symbol *sym, struct cfdata *data)
+{
+	struct property *prompt;
+	struct pexpr *promptCondition;
+	struct pexpr *fe_both;
+	struct pexpr *pr_cond;
+	struct pexpr *req_cond;
+
+	if (!sym_is_boolean(sym))
+		return;
+
+	prompt = sym_get_prompt(sym);
+	if (prompt == NULL)
+		return;
+
+	promptCondition =
+		prompt->visible.expr ?
+			expr_calculate_pexpr_both(prompt->visible.expr, data) :
+			pexpr_alloc_symbol(data->constants->const_true);
+	fe_both = sym_get_fexpr_both(sym, data);
+	req_cond = pexpr_implies_share(promptCondition, fe_both, data);
+	sym_add_constraint(sym, req_cond, data);
+	pr_cond = pexpr_implies_share(fe_both, promptCondition, data);
+	sym_add_constraint(sym, pr_cond, data);
+	PEXPR_PUT(promptCondition, fe_both, req_cond, pr_cond);
+}
+
+/*
+ * build constraints for dependencies (choice symbols and options)
+ */
+static void add_choice_dependencies(struct symbol *sym, struct cfdata *data)
+{
+	struct property *prompt;
+	struct expr *to_parse;
+	struct pexpr *dep_both;
+
+	if (!sym_is_choice(sym) || !sym_is_choice_value(sym))
+		return;
+
+	prompt = sym_get_prompt(sym);
+	if (prompt == NULL)
+		return;
+
+	if (sym_is_choice(sym)) {
+		if (!prompt->visible.expr)
+			return;
+		to_parse = prompt->visible.expr;
+	} else {
+		if (!sym->dir_dep.expr)
+			return;
+		to_parse = sym->dir_dep.expr;
+	}
+
+	dep_both = expr_calculate_pexpr_both(to_parse, data);
+
+	if (sym->type == S_TRISTATE) {
+		struct pexpr *dep_y = expr_calculate_pexpr_y(to_parse, data);
+		struct pexpr *c1 =
+			pexpr_implies(pexpr_alloc_symbol(sym->fexpr_y), dep_y,
+				      data, PEXPR_ARG1);
+		struct pexpr *c2 =
+			pexpr_implies(pexpr_alloc_symbol(sym->fexpr_m),
+				      dep_both, data, PEXPR_ARG1);
+
+		sym_add_constraint_unique(sym, c1, data);
+		sym_add_constraint_unique(sym, c2, data);
+		PEXPR_PUT(dep_y, c1, c2);
+	} else if (sym->type == S_BOOLEAN) {
+		struct pexpr *c =
+			pexpr_implies(pexpr_alloc_symbol(sym->fexpr_y),
+				      dep_both, data, PEXPR_ARG1);
+
+		sym_add_constraint_unique(sym, c, data);
+		pexpr_put(c);
+	}
+	pexpr_put(dep_both);
+}
+
+/*
+ * build constraints for the choice groups
+ */
+static void add_choice_constraints(struct symbol *sym, struct cfdata *data)
+{
+	struct property *prompt;
+	struct symbol *choice, *choice2;
+	struct sym_node *node;
+	struct sym_list *items, *promptItems;
+	struct pexpr *c1;
+	struct menu *menu_ptr, *choiceval_menu;
+
+	if (!sym_is_boolean(sym))
+		return;
+
+	prompt = sym_get_prompt(sym);
+	if (prompt == NULL)
+		return;
+
+	/* create list of all choice options */
+	items = CF_LIST_INIT(sym);
+	/* create list of choice options with a prompt */
+	promptItems = CF_LIST_INIT(sym);
+
+	for_all_choices(sym, choiceval_menu, menu_ptr) {
+		choice = choiceval_menu->sym;
+
+		CF_PUSH_BACK(items, choice, sym);
+		if (sym_get_prompt(choice) != NULL)
+			CF_PUSH_BACK(promptItems, choice, sym);
+	}
+
+	/* if the choice is set to yes, at least one child must be set to yes */
+	c1 = NULL;
+	CF_LIST_FOR_EACH(node, promptItems, sym) {
+		choice = node->elem;
+		c1 = list_is_head(node->node.prev, &promptItems->list) ?
+			     pexpr_alloc_symbol(choice->fexpr_y) :
+			     pexpr_or(c1, pexpr_alloc_symbol(choice->fexpr_y),
+				      data, PEXPR_ARGX);
+	}
+	if (c1 != NULL) {
+		struct pexpr *c2 = pexpr_implies(
+			pexpr_alloc_symbol(sym->fexpr_y), c1, data, PEXPR_ARG1);
+
+		sym_add_constraint(sym, c2, data);
+		PEXPR_PUT(c1, c2);
+	}
+
+	/*
+	 * every choice option (even those without a prompt) implies the choice
+	 */
+	CF_LIST_FOR_EACH(node, items, sym) {
+		choice = node->elem;
+		c1 = pexpr_implies(sym_get_fexpr_both(choice, data),
+					sym_get_fexpr_both(sym, data), data,
+					PEXPR_ARGX);
+		sym_add_constraint(sym, c1, data);
+		pexpr_put(c1);
+	}
+
+	/* choice options can only select mod, if the entire choice is mod */
+	if (sym->type == S_TRISTATE) {
+		CF_LIST_FOR_EACH(node, items, sym) {
+			choice = node->elem;
+			if (choice->type == S_TRISTATE) {
+				c1 = pexpr_implies(
+					pexpr_alloc_symbol(choice->fexpr_m),
+					pexpr_alloc_symbol(sym->fexpr_m), data,
+					PEXPR_ARGX);
+				sym_add_constraint(sym, c1, data);
+				pexpr_put(c1);
+			}
+		}
+	}
+
+	/* tristate options cannot be m, if the choice symbol is boolean */
+	if (sym->type == S_BOOLEAN) {
+		CF_LIST_FOR_EACH(node, items, sym) {
+			choice = node->elem;
+			if (choice->type == S_TRISTATE) {
+				struct pexpr *e = pexpr_not(
+					pexpr_alloc_symbol(choice->fexpr_m),
+					data);
+				sym_add_constraint(sym, e, data);
+				pexpr_put(e);
+			}
+		}
+	}
+
+	/* all choice options are mutually exclusive for yes */
+	CF_LIST_FOR_EACH(node, promptItems, sym) {
+		struct sym_node *node2 = list_next_entry(node, node);
+
+		choice = node->elem;
+		list_for_each_entry_from(node2, &promptItems->list, node) {
+			choice2 = node2->elem;
+			c1 = pexpr_or(
+				pexpr_not(pexpr_alloc_symbol(choice->fexpr_y),
+					  data),
+				pexpr_not(pexpr_alloc_symbol(choice2->fexpr_y),
+					  data),
+				data, PEXPR_ARGX);
+			sym_add_constraint(sym, c1, data);
+			pexpr_put(c1);
+		}
+	}
+
+	/* if one choice option with a prompt is set to yes,
+	 * then no other option may be set to mod
+	 */
+	if (sym->type == S_TRISTATE) {
+		CF_LIST_FOR_EACH(node, promptItems, sym) {
+			struct sym_list *tmp;
+			struct sym_node *node2 = list_next_entry(node, node);
+
+			choice = node->elem;
+
+			tmp = CF_LIST_INIT(sym);
+			list_for_each_entry_from(node2, &promptItems->list,
+						 node) {
+				choice2 = node2->elem;
+				if (choice2->type == S_TRISTATE)
+					CF_PUSH_BACK(tmp, choice2, sym);
+			}
+			if (list_empty(&tmp->list))
+				continue;
+
+			CF_LIST_FOR_EACH(node2, tmp, sym) {
+				struct pexpr *choice2_mod =
+					pexpr_alloc_symbol(choice2->fexpr_m);
+
+				choice2 = node2->elem;
+				if (list_is_first(&node2->node, &tmp->list))
+					c1 = pexpr_not_share(choice2_mod, data);
+				else
+					c1 = pexpr_and(
+						c1,
+						pexpr_not_share(choice2_mod,
+								data),
+						data, PEXPR_ARGX);
+
+				PEXPR_PUT(choice2_mod);
+			}
+			c1 = pexpr_implies(pexpr_alloc_symbol(choice->fexpr_y),
+					   c1, data, PEXPR_ARGX);
+			sym_add_constraint(sym, c1, data);
+			pexpr_put(c1);
+		}
+	}
+	CF_LIST_FREE(promptItems, sym);
+	CF_LIST_FREE(items, sym);
+}
+
+/*
+ * build the constraints for invisible options such as defaults
+ */
+static void add_invisible_constraints(struct symbol *sym, struct cfdata *data)
+{
+	struct property *prompt = sym_get_prompt(sym);
+	struct pexpr *promptCondition_both, *promptCondition_yes, *noPromptCond;
+	struct pexpr *npc;
+	struct defm_list *defaults;
+	struct pexpr *default_y, *default_m, *default_both;
+
+	/* no constraints for the prompt, nothing to do here */
+	if (prompt != NULL && !prompt->visible.expr)
+		return;
+
+	if (prompt == NULL) {
+		promptCondition_both =
+			pexpr_alloc_symbol(data->constants->const_false);
+		promptCondition_yes =
+			pexpr_alloc_symbol(data->constants->const_false);
+		noPromptCond = pexpr_alloc_symbol(data->constants->const_true);
+	} else {
+		struct property *p;
+
+		promptCondition_both =
+			pexpr_alloc_symbol(data->constants->const_false);
+		promptCondition_yes =
+			pexpr_alloc_symbol(data->constants->const_false);
+
+		/* some symbols have multiple prompts */
+		for_all_prompts(sym, p) {
+			promptCondition_both =
+				pexpr_or(promptCondition_both,
+					      expr_calculate_pexpr_both(
+						      p->visible.expr, data),
+					      data, PEXPR_ARGX);
+			promptCondition_yes = pexpr_or(
+				promptCondition_yes,
+				expr_calculate_pexpr_y(p->visible.expr, data),
+				data, PEXPR_ARGX);
+		}
+		noPromptCond = pexpr_not_share(promptCondition_both, data);
+	}
+
+	if (NPC_OPTIMISATION) {
+		struct fexpr *npc_fe =
+			fexpr_create(data->sat_variable_nr++, FE_NPC, "");
+
+		if (sym_is_choice(sym))
+			str_append(&npc_fe->name, "Choice_");
+
+		str_append(&npc_fe->name, sym_get_name(sym));
+		str_append(&npc_fe->name, "_NPC");
+		sym->noPromptCond = npc_fe;
+		fexpr_add_to_satmap(npc_fe, data);
+
+		npc = pexpr_alloc_symbol(npc_fe);
+
+		if (!sym_is_choice_value(sym) && !sym_is_choice(sym)) {
+			struct pexpr *c =
+				pexpr_implies_share(noPromptCond, npc, data);
+			sym_add_constraint(sym, c, data);
+			pexpr_put(c);
+		}
+	} else {
+		npc = pexpr_get(noPromptCond);
+	}
+
+	defaults = calc_default_conditions(sym, data);
+	default_y = get_default_y(defaults, data);
+	default_m = get_default_m(defaults, data);
+	default_both = pexpr_or_share(default_y, default_m, data);
+
+	/*
+	 * tristate elements are only selectable as yes, if they are visible as
+	 * yes
+	 */
+	if (sym->type == S_TRISTATE) {
+		struct pexpr *e1 = pexpr_implies(
+			promptCondition_both,
+			pexpr_implies(pexpr_alloc_symbol(sym->fexpr_y),
+					   promptCondition_yes, data,
+					   PEXPR_ARG1),
+			data, PEXPR_ARG2);
+
+		sym_add_constraint(sym, e1, data);
+		pexpr_put(e1);
+	}
+
+	/* if invisible and off by default, then a symbol can only be
+	 * deactivated by its reverse dependencies
+	 */
+	if (sym->type == S_TRISTATE) {
+		struct pexpr *sel_y, *sel_m, *sel_both;
+		struct pexpr *c1, *c2, *c3;
+		struct pexpr *d1, *d2, *d3;
+		struct pexpr *e1, *e2, *e3;
+
+		if (sym->fexpr_sel_y != NULL) {
+			sel_y = pexpr_implies(
+				pexpr_alloc_symbol(sym->fexpr_y),
+				pexpr_alloc_symbol(sym->fexpr_sel_y), data,
+				PEXPR_ARGX);
+			sel_m = pexpr_implies(
+				pexpr_alloc_symbol(sym->fexpr_m),
+				pexpr_alloc_symbol(sym->fexpr_sel_m), data,
+				PEXPR_ARGX);
+			sel_both = pexpr_implies(
+				pexpr_alloc_symbol(sym->fexpr_y),
+				pexpr_or(pexpr_alloc_symbol(sym->fexpr_sel_m),
+					 pexpr_alloc_symbol(sym->fexpr_sel_y),
+					 data, PEXPR_ARGX),
+				data, PEXPR_ARGX);
+		} else {
+			sel_y = pexpr_not(pexpr_alloc_symbol(sym->fexpr_y),
+					  data);
+			sel_m = pexpr_not(pexpr_alloc_symbol(sym->fexpr_m),
+					  data);
+			sel_both = pexpr_get(sel_y);
+		}
+
+		c1 = pexpr_implies(pexpr_not_share(default_y, data), sel_y,
+				   data, PEXPR_ARG1);
+		c2 = pexpr_implies(pexpr_alloc_symbol(modules_sym->fexpr_y), c1,
+				   data, PEXPR_ARG1);
+		c3 = pexpr_implies_share(npc, c2, data);
+		sym_add_constraint(sym, c3, data);
+
+		d1 = pexpr_implies(pexpr_not_share(default_m, data), sel_m,
+				   data, PEXPR_ARG1);
+		d2 = pexpr_implies(pexpr_alloc_symbol(modules_sym->fexpr_y), d1,
+				   data, PEXPR_ARG1);
+		d3 = pexpr_implies_share(npc, d2, data);
+		sym_add_constraint(sym, d3, data);
+
+		e1 = pexpr_implies(pexpr_not_share(default_both, data),
+				   sel_both, data, PEXPR_ARG1);
+		e2 = pexpr_implies(
+			pexpr_not(pexpr_alloc_symbol(modules_sym->fexpr_y),
+				  data),
+			e1, data, PEXPR_ARG1);
+		e3 = pexpr_implies_share(npc, e2, data);
+		sym_add_constraint(sym, e3, data);
+		PEXPR_PUT(sel_y, sel_m, sel_both, c1, c2, c3, d1, d2, d3, e1,
+			  e2, e3);
+	} else if (sym->type == S_BOOLEAN) {
+		struct pexpr *sel_y;
+		struct pexpr *e1, *e2;
+
+		if (sym->fexpr_sel_y != NULL)
+			sel_y = pexpr_implies(
+				pexpr_alloc_symbol(sym->fexpr_y),
+				pexpr_alloc_symbol(sym->fexpr_sel_y), data,
+				PEXPR_ARGX);
+		else
+			sel_y = pexpr_not(pexpr_alloc_symbol(sym->fexpr_y),
+					  data);
+
+		e1 = pexpr_implies(pexpr_not_share(default_both, data),
+					sel_y, data, PEXPR_ARG1);
+		e2 = pexpr_implies_share(npc, e1, data);
+
+		sym_add_constraint_unique(sym, e2, data);
+		PEXPR_PUT(sel_y, e1, e2);
+	} else {
+		/* if non-boolean is invisible and no default's condition is
+		 * fulfilled, then the symbol is not set
+		 */
+		struct pexpr *default_any = get_default_any(sym, data);
+		struct pexpr *e1 =
+			pexpr_alloc_symbol(data->constants->const_true);
+		struct pexpr *e2, *e3;
+		struct fexpr_node *node;
+		bool first = true;
+
+		/* e1 = "sym is not set" */
+		CF_LIST_FOR_EACH(node, sym->nb_vals, fexpr) {
+			if (first) {
+				first = false;
+				continue;
+			}
+			e1 = pexpr_and(e1,
+				       pexpr_not(pexpr_alloc_symbol(node->elem),
+						 data),
+				       data, PEXPR_ARGX);
+		}
+
+		e2 = pexpr_implies(pexpr_not_share(default_any, data), e1,
+					data, PEXPR_ARG1);
+		e3 = pexpr_implies_share(npc, e2, data);
+
+		sym_add_constraint(sym, e3, data);
+		PEXPR_PUT(default_any, e1, e2, e3);
+	}
+
+	/* if invisible and on by default, then a symbol can only be deactivated
+	 * by its dependencies
+	 */
+	if (list_empty(&defaults->list)) {
+		// nothing to do
+	} else if (sym->type == S_TRISTATE) {
+		struct pexpr *e1;
+		struct pexpr *e2;
+
+		e1 = pexpr_implies(
+			npc,
+			pexpr_implies(default_y,
+				      pexpr_alloc_symbol(sym->fexpr_y), data,
+				      PEXPR_ARG2),
+			data, PEXPR_ARG2);
+		sym_add_constraint(sym, e1, data);
+
+		e2 = pexpr_implies(
+			npc,
+			pexpr_implies(default_m,
+					   sym_get_fexpr_both(sym, data),
+					   data, PEXPR_ARG2),
+			data, PEXPR_ARG2);
+		sym_add_constraint(sym, e2, data);
+		PEXPR_PUT(e1, e2);
+	} else if (sym->type == S_BOOLEAN) {
+		struct pexpr *c;
+		struct pexpr *c2;
+
+		c = pexpr_implies(default_both,
+				  pexpr_alloc_symbol(sym->fexpr_y), data,
+				  PEXPR_ARG2);
+
+		// TODO tristate choice hack
+
+		c2 = pexpr_implies_share(npc, c, data);
+		sym_add_constraint(sym, c2, data);
+		PEXPR_PUT(c, c2);
+	} else {
+		/* if non-boolean invisible, then it assumes the correct
+		 * default (if any).
+		 */
+		struct defm_node *node;
+		struct pexpr *cond, *c;
+		struct fexpr *f;
+
+		CF_LIST_FOR_EACH(node, defaults, defm) {
+			f = node->elem->val;
+			cond = node->elem->e;
+			c = pexpr_implies(npc,
+					  pexpr_implies(cond,
+							pexpr_alloc_symbol(f),
+							data, PEXPR_ARG2),
+					  data, PEXPR_ARG2);
+			sym_add_constraint(sym, c, data);
+			pexpr_put(c);
+		}
+	}
+
+	PEXPR_PUT(promptCondition_yes, promptCondition_both, noPromptCond, npc,
+		  default_y, default_m, default_both);
+	defm_list_destruct(defaults);
+}
+
+/*
+ * add the known values from the default and range properties
+ */
+static void sym_add_nonbool_values_from_default_range(struct symbol *sym,
+						      struct cfdata *data)
+{
+	struct property *p;
+
+	for_all_defaults(sym, p) {
+		if (p == NULL)
+			continue;
+
+		/* add the value to known values, if it doesn't exist yet */
+		sym_create_nonbool_fexpr(sym, p->expr->left.sym->name, data);
+	}
+
+	for_all_properties(sym, p, P_RANGE) {
+		if (p == NULL)
+			continue;
+
+		/* add the values to known values, if they don't exist yet */
+		sym_create_nonbool_fexpr(sym, p->expr->left.sym->name, data);
+		sym_create_nonbool_fexpr(sym, p->expr->right.sym->name, data);
+	}
+}
+
+/*
+ * build the range constraints for int/hex:
+ * For each range and each value in `sym->nb_vals` that's not in the range:
+ *	If the range's condition is fulfilled, then sym can't have this value.
+ */
+static void sym_add_range_constraints(struct symbol *sym, struct cfdata *data)
+{
+	struct property *prop;
+	struct pexpr *prevs;
+	struct pexpr *propCond;
+	struct pexpr_list *prevCond; // list of all conditions of the ranges
+		// from the previous iterations
+
+	prevCond = CF_LIST_INIT(pexpr);
+
+	for_all_properties(sym, prop, P_RANGE) {
+		int base;
+		long long range_min, range_max, tmp;
+		struct fexpr_node *node;
+		bool first;
+
+		if (prop == NULL)
+			continue;
+
+		prevs = pexpr_alloc_symbol(data->constants->const_true);
+		propCond = prop_get_condition(prop, data);
+
+		// construct prevs as "none of the previous ranges' conditions
+		// were fulfilled but this range's condition is"
+		if (list_empty(&prevCond->list)) {
+			pexpr_put(prevs);
+			prevs = pexpr_get(propCond);
+;
+		} else {
+			struct pexpr_node *node;
+
+			CF_LIST_FOR_EACH(node, prevCond, pexpr)
+				prevs = pexpr_and(pexpr_not_share(node->elem,
+								  data),
+						  prevs, data, PEXPR_ARGX);
+
+			prevs = pexpr_and(propCond, prevs, data,
+					       PEXPR_ARG2);
+		}
+		CF_PUSH_BACK(prevCond, pexpr_get(propCond), pexpr);
+
+		switch (sym->type) {
+		case S_INT:
+			base = 10;
+			break;
+		case S_HEX:
+			base = 16;
+			break;
+		default:
+			return;
+		}
+
+		range_min = sym_get_range_val(prop->expr->left.sym, base);
+		range_max = sym_get_range_val(prop->expr->right.sym, base);
+
+		first = true;
+		/* can skip the first non-boolean value, since this is 'n' */
+		CF_LIST_FOR_EACH(node, sym->nb_vals, fexpr) {
+			struct pexpr *not_nb_val;
+			struct pexpr *c;
+
+			if (first) {
+				first = false;
+				continue;
+			}
+
+			tmp = strtoll(str_get(&node->elem->nb_val), NULL, base);
+
+			/* known value is in range, nothing to do here */
+			if (tmp >= range_min && tmp <= range_max)
+				continue;
+
+			not_nb_val =
+				pexpr_not(pexpr_alloc_symbol(node->elem), data);
+			c = pexpr_implies_share(prevs, not_nb_val, data);
+			sym_add_constraint(sym, c, data);
+			PEXPR_PUT(not_nb_val, c);
+		}
+		PEXPR_PUT(prevs, propCond);
+	}
+
+	pexpr_list_free_put(prevCond);
+
+}
+
+/*
+ * at least 1 of the known values for a non-boolean symbol must be true
+ */
+static void sym_nonbool_at_least_1(struct symbol *sym, struct cfdata *data)
+{
+	struct pexpr *e;
+	struct fexpr_node *node;
+
+	if (!sym_is_nonboolean(sym))
+		return;
+
+	e = pexpr_alloc_symbol(data->constants->const_false);
+	CF_LIST_FOR_EACH(node, sym->nb_vals, fexpr)
+		e = pexpr_or(e, pexpr_alloc_symbol(node->elem), data,
+			     PEXPR_ARGX);
+
+	sym_add_constraint(sym, e, data);
+	pexpr_put(e);
+}
+
+/*
+ * at most 1 of the known values for a non-boolean symbol can be true
+ */
+static void sym_nonbool_at_most_1(struct symbol *sym, struct cfdata *data)
+{
+	struct fexpr_node *node1;
+
+	if (!sym_is_nonboolean(sym))
+		return;
+
+	/* iterate over all subsets of sym->nb_vals of size 2 */
+	CF_LIST_FOR_EACH(node1, sym->nb_vals, fexpr) {
+		struct pexpr *e1 = pexpr_alloc_symbol(node1->elem);
+		struct fexpr_node *node2;
+
+		list_for_each_entry_reverse(node2, &sym->nb_vals->list, node) {
+			struct pexpr *e2, *e;
+
+			if (node2 == node1)
+				break;
+			e2 = pexpr_alloc_symbol(node2->elem);
+			e = pexpr_or(pexpr_not_share(e1, data),
+						   pexpr_not_share(e2, data),
+						   data, PEXPR_ARGX);
+
+			sym_add_constraint(sym, e, data);
+			PEXPR_PUT(e, e2);
+		}
+		pexpr_put(e1);
+	}
+}
+
+/*
+ * a visible prompt for a non-boolean implies a value for the symbol
+ */
+static void sym_add_nonbool_prompt_constraint(struct symbol *sym,
+					      struct cfdata *data)
+{
+	struct property *prompt;
+	struct pexpr *promptCondition;
+	struct pexpr *n;
+	struct pexpr *c = NULL;
+
+	prompt = sym_get_prompt(sym);
+	if (prompt == NULL)
+		return;
+
+	promptCondition = prop_get_condition(prompt, data);
+	n = pexpr_alloc_symbol(sym_get_nonbool_fexpr(sym, "n"));
+
+	if (n->type != PE_SYMBOL || n->left.fexpr == NULL)
+		goto cleanup;
+
+	c = pexpr_implies(promptCondition, pexpr_not_share(n, data), data,
+			  PEXPR_ARG2);
+
+	sym_add_constraint(sym, c, data);
+
+cleanup:
+	PEXPR_PUT(n, promptCondition, c);
+}
+
+static struct default_map *create_default_map_entry(struct fexpr *val,
+						    struct pexpr *e)
+{
+	struct default_map *map = malloc(sizeof(struct default_map));
+
+	pexpr_get(e);
+	map->val = val;
+	map->e = e;
+
+	return map;
+}
+
+/**
+ * findDefaultEntry()
+ * @val: Value that the entry must have
+ * @defaults: List of defaults to search in
+ * @constants: To get ``constants->const_false`` from
+ *
+ * Finds an entry in @defaults whose &default_map.val attribute is the same
+ * pointer as the @val argument.
+ *
+ * Return: The condition &default_map.e of the found entry, or
+ * ``pexf(constants->const_false)`` if none was found. To be pexpr_put() by the
+ * caller.
+ */
+static struct pexpr *findDefaultEntry(struct fexpr *val,
+				      struct defm_list *defaults,
+				      struct constants *constants)
+{
+	struct defm_node *node;
+
+	CF_LIST_FOR_EACH(node, defaults, defm) {
+		if (val == node->elem->val) {
+			pexpr_get(node->elem->e);
+			return node->elem->e;
+		}
+	}
+
+	return pexpr_alloc_symbol(constants->const_false);
+}
+
+/*
+ * accumulated during execution of add_defaults(), a disjunction of the
+ * conditions for all default props of a symbol
+ */
+static struct pexpr *covered;
+
+static bool is_tri_as_num(struct symbol *sym)
+{
+	if (!sym->name)
+		return false;
+
+	return !strcmp(sym->name, "0")
+		|| !strcmp(sym->name, "1")
+		|| !strcmp(sym->name, "2");
+}
+
+/**
+ * add_to_default_map() - Add to or update an entry in a default list
+ * @entry: Will be consumed by this function, i.e. the caller should and need
+ * only access @entry via @defaults.
+ */
+static void add_to_default_map(struct defm_list *defaults,
+			       struct default_map *entry, struct symbol *sym)
+{
+	/* as this is a map, the entry must be replaced if it already exists */
+	if (sym_is_boolean(sym)) {
+		struct default_map *map;
+		struct defm_node *node;
+
+		CF_LIST_FOR_EACH(node, defaults, defm) {
+			map = node->elem;
+			if (map->val->sym == entry->val->sym) {
+				pexpr_put(map->e);
+				map->e = entry->e;
+				free(entry);
+				return;
+			}
+		}
+		CF_PUSH_BACK(defaults, entry, defm);
+	} else {
+		struct default_map *map;
+		struct defm_node *node;
+
+		CF_LIST_FOR_EACH(node, defaults, defm) {
+			map = node->elem;
+			if (map->val->satval == entry->val->satval) {
+				pexpr_put(map->e);
+				map->e = entry->e;
+				free(entry);
+				return;
+			}
+		}
+		CF_PUSH_BACK(defaults, entry, defm);
+	}
+}
+
+/**
+ * updateDefaultList() - Update a default list with a new value-condition pair
+ * @val: The value whose condition will be updated
+ * @newCond: The condition of the default prop. Does not include the condition
+ * that the earlier default's conditions are not fulfilled.
+ * @result: the default list
+ * @sym: the symbol that the defaults belong to
+ *
+ * Update the condition that @val will be used for @sym by considering the next
+ * default property, whose condition is given by @newCond.
+ */
+static void updateDefaultList(struct fexpr *val, struct pexpr *newCond,
+			      struct defm_list *result, struct symbol *sym,
+			      struct cfdata *data)
+{
+	// The current condition of @val deduced from the previous default props
+	struct pexpr *prevCond = findDefaultEntry(val, result, data->constants);
+	// New combined condition for @val
+	struct pexpr *condUseVal =
+		pexpr_or(prevCond,
+			 pexpr_and(newCond, pexpr_not_share(covered, data),
+				   data, PEXPR_ARG2),
+			 data, PEXPR_ARG2);
+	add_to_default_map(result, create_default_map_entry(val, condUseVal),
+			   sym);
+	covered = pexpr_or(covered, newCond, data, PEXPR_ARG1);
+	PEXPR_PUT(prevCond, condUseVal);
+}
+
+/**
+ * add_defaults() - Generate list of default values and their conditions
+ * @defaults: List of the default properties
+ * @ctx: Additional condition that needs to be fulfilled for any default. May be
+ * NULL.
+ * @result: List that will be filled
+ * @sym: Symbol that the defaults belong to
+ *
+ * Creates a map from values that @sym can assume to the conditions under which
+ * they will be assumed. Without @ctx, this will only consider the conditions
+ * directly associated with the defaults, e.g. sym->dir_dep would not be
+ * considered.
+ *
+ * As a side effect, the &symbol->nb_vals of @sym will be added for
+ * all default values (as well as the @symbol->nb_vals of other symbols @sym has
+ * as default (recursively)).
+ */
+static void add_defaults(struct prop_list *defaults, struct expr *ctx,
+			 struct defm_list *result, struct symbol *sym,
+			 struct cfdata *data)
+{
+	struct prop_node *node;
+	struct property *p;
+	struct expr *expr;
+
+	CF_LIST_FOR_EACH(node, defaults, prop) {
+		p = node->elem;
+		/* calculate expr as whether the default's condition (and the
+		 * one inherited from ctx) is fulfilled
+		 */
+		if (p->visible.expr) {
+			if (ctx == NULL)
+				expr = p->visible.expr;
+			else
+				expr = expr_alloc_and(p->visible.expr, ctx);
+		} else {
+			if (ctx == NULL)
+				expr = expr_alloc_symbol(&symbol_yes);
+			else
+				expr = expr_alloc_and(
+					expr_alloc_symbol(&symbol_yes), ctx);
+		}
+
+		/* if tristate and def.value = y */
+		if (p->expr->type == E_SYMBOL && sym->type == S_TRISTATE &&
+		    p->expr->left.sym == &symbol_yes) {
+			struct pexpr *expr_y =
+				expr_calculate_pexpr_y(expr, data);
+			struct pexpr *expr_m =
+				expr_calculate_pexpr_m(expr, data);
+
+			updateDefaultList(data->constants->symbol_yes_fexpr,
+					  expr_y, result, sym, data);
+			updateDefaultList(data->constants->symbol_mod_fexpr,
+					  expr_m, result, sym, data);
+			PEXPR_PUT(expr_y, expr_m);
+		}
+		/* if def.value = n/m/y */
+		else if (p->expr->type == E_SYMBOL &&
+			 sym_is_tristate_constant(p->expr->left.sym) &&
+			 sym_is_boolean(sym)) {
+			struct fexpr *s;
+			struct pexpr *expr_both =
+				expr_calculate_pexpr_both(expr, data);
+
+			if (p->expr->left.sym == &symbol_yes)
+				s = data->constants->symbol_yes_fexpr;
+			else if (p->expr->left.sym == &symbol_mod)
+				s = data->constants->symbol_mod_fexpr;
+			else
+				s = data->constants->symbol_no_fexpr;
+
+			updateDefaultList(s, expr_both, result, sym, data);
+			pexpr_put(expr_both);
+		}
+		/* if def.value = n/m/y, but written as 0/1/2 for a boolean */
+		else if (sym_is_boolean(sym) && p->expr->type == E_SYMBOL &&
+			 p->expr->left.sym->type == S_UNKNOWN &&
+			 is_tri_as_num(p->expr->left.sym)) {
+			struct fexpr *s;
+			struct pexpr *expr_both =
+				expr_calculate_pexpr_both(expr, data);
+
+			if (!strcmp(p->expr->left.sym->name, "0"))
+				s = data->constants->symbol_no_fexpr;
+			else if (!strcmp(p->expr->left.sym->name, "1"))
+				s = data->constants->symbol_mod_fexpr;
+			else
+				s = data->constants->symbol_yes_fexpr;
+
+			updateDefaultList(s, expr_both, result, sym, data);
+			pexpr_put(expr_both);
+		}
+		/* if def.value = non-boolean constant */
+		else if (expr_is_nonbool_constant(p->expr)) {
+			struct fexpr *s = sym_get_or_create_nonbool_fexpr(
+				sym, p->expr->left.sym->name, data);
+			struct pexpr *expr_both =
+				expr_calculate_pexpr_both(expr, data);
+
+			updateDefaultList(s, expr_both, result, sym, data);
+			pexpr_put(expr_both);
+		}
+		/* any expression which evaluates to n/m/y for a tristate */
+		else if (sym->type == S_TRISTATE) {
+			struct expr *e_tmp = expr_alloc_and(p->expr, expr);
+			struct pexpr *expr_y =
+				expr_calculate_pexpr_y(e_tmp, data);
+			struct pexpr *expr_m =
+				expr_calculate_pexpr_m(e_tmp, data);
+
+			updateDefaultList(data->constants->symbol_yes_fexpr,
+					  expr_y, result, sym, data);
+			updateDefaultList(data->constants->symbol_mod_fexpr,
+					  expr_m, result, sym, data);
+			PEXPR_PUT(expr_y, expr_m);
+		}
+		/* if non-boolean && def.value = non-boolean symbol */
+		else if (p->expr->type == E_SYMBOL && sym_is_nonboolean(sym) &&
+			 sym_is_nonboolean(p->expr->left.sym)) {
+			CF_DEF_LIST(nb_sym_defaults, prop);
+			struct property *p_tmp;
+
+			/* Add defaults of other symbol as possible defaults for
+			 * this symbol
+			 */
+			for_all_defaults(p->expr->left.sym, p_tmp)
+				CF_PUSH_BACK(nb_sym_defaults, p_tmp, prop);
+
+			add_defaults(nb_sym_defaults, expr, result, sym, data);
+			CF_LIST_FREE(nb_sym_defaults, prop);
+		}
+		/* any expression which evaluates to n/m/y */
+		else {
+			struct expr *e_tmp = expr_alloc_and(p->expr, expr);
+			struct pexpr *expr_both =
+				expr_calculate_pexpr_both(e_tmp, data);
+
+			updateDefaultList(data->constants->symbol_yes_fexpr,
+					  expr_both, result, sym, data);
+
+			pexpr_put(expr_both);
+		}
+	}
+}
+
+/**
+ * get_defaults() - Generate list of default values and their conditions
+ * @sym: Symbol whose defaults we want to look at
+ *
+ * Creates a map from values that @sym can assume to the conditions under which
+ * they will be assumed. This will only consider the conditions
+ * directly associated with the defaults, e.g. sym->dir_dep would not be
+ * considered.
+ *
+ * As a side effect, the &symbol->nb_vals of @sym will be added for
+ * all default values (as well as the @symbol->nb_vals of other symbols @sym has
+ * as default (recursively)).
+ */
+static struct defm_list *calc_default_conditions(struct symbol *sym,
+						 struct cfdata *data)
+{
+	CF_DEF_LIST(result, defm);
+	struct prop_list *defaults; /* list of default props of sym */
+	struct property *p;
+
+	covered = pexpr_alloc_symbol(data->constants->const_false);
+
+	defaults = CF_LIST_INIT(prop);
+	for_all_defaults(sym, p)
+		CF_PUSH_BACK(defaults, p, prop);
+
+	add_defaults(defaults, NULL, result, sym, data);
+	CF_LIST_FREE(defaults, prop);
+	pexpr_put(covered);
+
+	return result;
+}
+
+/*
+ * return the condition for "y", False if it doesn't exist
+ */
+static struct pexpr *get_default_y(struct defm_list *list, struct cfdata *data)
+{
+	struct default_map *entry;
+	struct defm_node *node;
+
+	CF_LIST_FOR_EACH(node, list, defm) {
+		entry = node->elem;
+		if (entry->val->type == FE_SYMBOL &&
+		    entry->val->sym == &symbol_yes) {
+			pexpr_get(entry->e);
+			return entry->e;
+		}
+	}
+
+	return pexpr_alloc_symbol(data->constants->const_false);
+}
+
+/*
+ * return the condition for "m", False if it doesn't exist
+ */
+static struct pexpr *get_default_m(struct defm_list *list, struct cfdata *data)
+{
+	struct default_map *entry;
+	struct defm_node *node;
+
+	CF_LIST_FOR_EACH(node, list, defm) {
+		entry = node->elem;
+		if (entry->val->type == FE_SYMBOL &&
+		    entry->val->sym == &symbol_mod) {
+			pexpr_get(entry->e);
+			return entry->e;
+		}
+	}
+
+	return pexpr_alloc_symbol(data->constants->const_false);
+}
+
+/*
+ * return the constraint when _some_ default value will be applied
+ */
+static struct pexpr *get_default_any(struct symbol *sym, struct cfdata *data)
+{
+	struct property *prop;
+	struct expr *e;
+	struct pexpr *p;
+
+	if (!sym_is_nonboolean(sym))
+		return NULL;
+
+	p = pexpr_alloc_symbol(data->constants->const_false);
+	for_all_defaults(sym, prop) {
+		if (prop->visible.expr)
+			e = prop->visible.expr;
+		else
+			e = expr_alloc_symbol(&symbol_yes);
+
+		if (expr_can_evaluate_to_mod(e))
+			p = pexpr_or(p, expr_calculate_pexpr_both(e, data),
+				     data, PEXPR_ARGX);
+
+		p = pexpr_or(p, expr_calculate_pexpr_y(e, data), data,
+			     PEXPR_ARGX);
+	}
+
+	return p;
+}
+
+/*
+ * get the value for the range
+ */
+static long sym_get_range_val(struct symbol *sym, int base)
+{
+	sym_calc_value(sym);
+	switch (sym->type) {
+	case S_INT:
+		base = 10;
+		break;
+	case S_HEX:
+		base = 16;
+		break;
+	default:
+		break;
+	}
+	return strtol(sym->curr.val, NULL, base);
+}
+
+/*
+ * count the number of all constraints
+ */
+unsigned int count_constraints(void)
+{
+	unsigned int c = 0;
+	struct symbol *sym;
+
+	for_all_symbols(sym) {
+		if (sym->type == S_UNKNOWN)
+			continue;
+
+		c += list_count_nodes(&sym->constraints->list);
+	}
+
+	return c;
+}
+
+/*
+ * add a constraint for a symbol
+ */
+void sym_add_constraint(struct symbol *sym, struct pexpr *constraint,
+			struct cfdata *data)
+{
+	if (!constraint)
+		return;
+
+	/* no need to add that */
+	if (constraint->type == PE_SYMBOL &&
+	    constraint->left.fexpr == data->constants->const_true)
+		return;
+
+	/* this should never happen */
+	if (constraint->type == PE_SYMBOL &&
+	    constraint->left.fexpr == data->constants->const_false)
+		perror("Adding const_false.");
+
+	CF_PUSH_BACK(sym->constraints, pexpr_get(constraint), pexpr);
+
+	if (!pexpr_is_nnf(constraint))
+		pexpr_print("Not NNF:", constraint, -1);
+}
+
+/*
+ * add a constraint for a symbol, but check for duplicate constraints
+ */
+void sym_add_constraint_unique(struct symbol *sym, struct pexpr *constraint,
+			   struct cfdata *data)
+{
+	struct pexpr_node *node;
+
+	if (!constraint)
+		return;
+
+	/* no need to add that */
+	if (constraint->type == PE_SYMBOL &&
+	    constraint->left.fexpr == data->constants->const_true)
+		return;
+
+	/* this should never happen */
+	if (constraint->type == PE_SYMBOL &&
+	    constraint->left.fexpr == data->constants->const_false)
+		perror("Adding const_false.");
+
+	/* check the constraints for the same symbol */
+	CF_LIST_FOR_EACH(node, sym->constraints, pexpr)
+		if (pexpr_test_eq(constraint, node->elem, data))
+			return;
+
+	CF_PUSH_BACK(sym->constraints, pexpr_get(constraint), pexpr);
+
+	if (!pexpr_is_nnf(constraint))
+		pexpr_print("Not NNF:", constraint, -1);
+}
scripts/kconfig/cf_constraints.h new file +24 -0
new file mode 100644
index 000000000000..a68dc9ba4f03
@@ -0,0 +1,24 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * Copyright (C) 2023 Patrick Franz <[email protected]>
+ */
+
+#ifndef CF_CONSTRAINTS_H
+#define CF_CONSTRAINTS_H
+
+#include "cf_defs.h"
+#include "expr.h"
+
+/* build the constraints for each symbol */
+void build_constraints(struct cfdata *data);
+
+/* count the number of all constraints */
+unsigned int count_constraints(void);
+
+/* add a constraint for a symbol */
+void sym_add_constraint(struct symbol *sym, struct pexpr *constraint, struct cfdata *data);
+
+/* add a constraint for a symbol, but check for duplicate constraints */
+void sym_add_constraint_unique(struct symbol *sym, struct pexpr *constraint, struct cfdata *data);
+
+#endif
Signature · 1 line
2.39.5
#7 lore raw

PATCH v7 5/11 kconfig: Add files for handling expressions

In reply to Ole Schuerks

Add files containing functions and macros to deal with propositional formulas, which are used for the translation of the Kconfig-model into propositional logic and in the conflict resolution algorithm.

---
 scripts/kconfig/cf_expr.c | 2003 +++++++++++++++++++++++++++++++++++++
 scripts/kconfig/cf_expr.h |  181 ++++
 2 files changed, 2184 insertions(+)
 create mode 100644 scripts/kconfig/cf_expr.c
 create mode 100644 scripts/kconfig/cf_expr.h
scripts/kconfig/cf_expr.c new file +2003 -0
new file mode 100644
index 000000000000..e4c97439ffdf
@@ -0,0 +1,2003 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * Copyright (C) 2023 Patrick Franz <[email protected]>
+ */
+
+#define _GNU_SOURCE
+#include <assert.h>
+#include <locale.h>
+#include <stdarg.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include <unistd.h>
+
+#include <xalloc.h>
+
+#include "lkc.h"
+#include "list.h"
+#include "cf_expr.h"
+#include "cf_defs.h"
+#include "cf_utils.h"
+
+static void create_fexpr_bool(struct symbol *sym, struct cfdata *data);
+static void create_fexpr_nonbool(struct symbol *sym, struct cfdata *data);
+static void create_fexpr_unknown(struct symbol *sym, struct cfdata *data);
+static void create_fexpr_choice(struct symbol *sym, struct cfdata *data);
+
+static void pexpr_print_util(struct pexpr *e, int prevtoken);
+static void pexpr_shallow_copy(struct pexpr *dest, struct pexpr *org,
+			       unsigned int ref_count);
+
+static struct pexpr *pexpr_move_wrapper(
+	struct pexpr *a, struct pexpr *b, struct cfdata *data,
+	enum pexpr_move move,
+	struct pexpr *(*func)(struct pexpr *, struct pexpr *, struct cfdata *));
+
+static int trans_count;
+
+
+/*
+ *  create a fexpr
+ */
+struct fexpr *fexpr_create(int satval, enum fexpr_type type, char *name)
+{
+	struct fexpr *e = xcalloc(1, sizeof(*e));
+
+	e->satval = satval;
+	e->type = type;
+	e->name = str_new();
+	e->assumption = false;
+	str_append(&e->name, name);
+
+	return e;
+}
+
+/*
+ * create the fexpr for a symbol
+ */
+void sym_create_fexpr(struct symbol *sym, struct cfdata *data)
+{
+	if (sym_is_choice(sym))
+		create_fexpr_choice(sym, data);
+	else if (sym_is_boolean(sym))
+		create_fexpr_bool(sym, data);
+	else if (sym_is_nonboolean(sym))
+		create_fexpr_nonbool(sym, data);
+	else
+		create_fexpr_unknown(sym, data);
+}
+
+/*
+ * create the fexpr for symbols with reverse dependencies
+ */
+static void create_fexpr_selected(struct symbol *sym, struct cfdata *data)
+{
+	struct fexpr *fexpr_sel_y;
+	struct fexpr *fexpr_sel_m;
+
+	/* fexpr_sel_y */
+	fexpr_sel_y =
+		fexpr_create(data->sat_variable_nr++, FE_SELECT, sym->name);
+	str_append(&fexpr_sel_y->name, "_sel_y");
+	fexpr_sel_y->sym = sym;
+	fexpr_add_to_satmap(fexpr_sel_y, data);
+
+	sym->fexpr_sel_y = fexpr_sel_y;
+
+	/* fexpr_sel_m */
+	if (sym->type == S_BOOLEAN)
+		return;
+
+	fexpr_sel_m =
+		fexpr_create(data->sat_variable_nr++, FE_SELECT, sym->name);
+	str_append(&fexpr_sel_m->name, "_sel_m");
+	fexpr_sel_m->sym = sym;
+	fexpr_add_to_satmap(fexpr_sel_m, data);
+
+	sym->fexpr_sel_m = fexpr_sel_m;
+}
+
+/*
+ * create the fexpr for a boolean/tristate symbol
+ */
+static void create_fexpr_bool(struct symbol *sym, struct cfdata *data)
+{
+	struct fexpr *fexpr_y;
+	struct fexpr *fexpr_m;
+
+	fexpr_y = fexpr_create(data->sat_variable_nr++, FE_SYMBOL, sym->name);
+	fexpr_y->sym = sym;
+	fexpr_y->tri = yes;
+	fexpr_add_to_satmap(fexpr_y, data);
+
+	sym->fexpr_y = fexpr_y;
+
+
+	if (sym->type == S_TRISTATE) {
+		fexpr_m = fexpr_create(data->sat_variable_nr++, FE_SYMBOL,
+				       sym->name);
+		str_append(&fexpr_m->name, "_MODULE");
+		fexpr_m->sym = sym;
+		fexpr_m->tri = mod;
+		fexpr_add_to_satmap(fexpr_m, data);
+	} else {
+		fexpr_m = data->constants->const_false;
+	}
+
+	sym->fexpr_m = fexpr_m;
+
+	if (sym->rev_dep.expr)
+		create_fexpr_selected(sym, data);
+}
+
+/*
+ * create the fexpr for a non-boolean symbol
+ */
+static void create_fexpr_nonbool(struct symbol *sym, struct cfdata *data)
+{
+	/* default values */
+	char int_values[][2] = {"n", "0", "1"};
+	char hex_values[][4] = {"n", "0x0", "0x1"};
+	char string_values[][9] = {"n", "", "nonempty"};
+
+	sym->fexpr_y = data->constants->const_false;
+	sym->fexpr_m = data->constants->const_false;
+	sym->nb_vals = xmalloc(sizeof(*sym->nb_vals));
+	INIT_LIST_HEAD(&sym->nb_vals->list);
+
+	for (int i = 0; i < 3; i++) {
+		struct fexpr *e = fexpr_create(data->sat_variable_nr++,
+					       FE_NONBOOL, sym->name);
+
+		e->sym = sym;
+		str_append(&e->name, "=");
+		e->nb_val = str_new();
+
+		switch (sym->type) {
+		case S_INT:
+			str_append(&e->name, int_values[i]);
+			str_append(&e->nb_val, int_values[i]);
+			break;
+		case S_HEX:
+			str_append(&e->name, hex_values[i]);
+			str_append(&e->nb_val, hex_values[i]);
+			break;
+		case S_STRING:
+			str_append(&e->name, string_values[i]);
+			str_append(&e->nb_val, string_values[i]);
+			break;
+		default:
+			break;
+		}
+
+		CF_PUSH_BACK(sym->nb_vals, e, fexpr);
+		fexpr_add_to_satmap(e, data);
+	}
+}
+
+/*
+ * set fexpr_y and fexpr_m simply to False
+ */
+static void create_fexpr_unknown(struct symbol *sym, struct cfdata *data)
+{
+	sym->fexpr_y = data->constants->const_false;
+	sym->fexpr_m = data->constants->const_false;
+}
+
+/*
+ * create the fexpr for a choice symbol
+ */
+static void create_fexpr_choice(struct symbol *sym, struct cfdata *data)
+{
+	struct property *prompt;
+	char *name, *write, *read;
+	struct fexpr *fexpr_y;
+	struct fexpr *fexpr_m;
+
+	if (!sym_is_boolean(sym))
+		return;
+
+	prompt = sym_get_prompt(sym);
+	if (prompt == NULL) {
+		perror("Choice symbol should have a prompt.");
+		return;
+	}
+
+	name = strdup(prompt->text);
+
+	/* remove spaces */
+	write = name;
+	read = name;
+	do {
+		if (*read != ' ')
+			*write++ = *read;
+	} while (*read++);
+
+	fexpr_y = fexpr_create(data->sat_variable_nr++, FE_CHOICE, "Choice_");
+	str_append(&fexpr_y->name, name);
+	fexpr_y->sym = sym;
+	fexpr_y->tri = yes;
+	fexpr_add_to_satmap(fexpr_y, data);
+
+	sym->fexpr_y = fexpr_y;
+
+	if (sym->type == S_TRISTATE) {
+		fexpr_m = fexpr_create(data->sat_variable_nr++, FE_CHOICE,
+				       "Choice_");
+		str_append(&fexpr_m->name, name);
+		str_append(&fexpr_m->name, "_MODULE");
+		fexpr_m->sym = sym;
+		fexpr_m->tri = mod;
+		fexpr_add_to_satmap(fexpr_m, data);
+	} else {
+		fexpr_m = data->constants->const_false;
+	}
+	sym->fexpr_m = fexpr_m;
+	free(name);
+}
+
+/*
+ * evaluate an unequality between a non-Boolean symbol and a constant
+ */
+static struct pexpr *expr_eval_unequal_nonbool_const(struct symbol *sym,
+						     struct symbol *compval,
+						     enum expr_type type,
+						     struct cfdata *data)
+{
+	int base;
+	struct pexpr *c;
+	long val;
+	struct fexpr_node *node;
+	struct fexpr *fe;
+	bool first;
+
+	if (!sym || !compval)
+		return pexpr_alloc_symbol(data->constants->const_false);
+
+	base = 0;
+	switch (sym->type) {
+	case S_INT:
+		base = 10;
+		break;
+	case S_HEX:
+		base = 16;
+		break;
+	default:
+		break;
+	}
+
+	c = pexpr_alloc_symbol(data->constants->const_false);
+	val = strtol(compval->name, NULL, base);
+	first = true;
+	CF_LIST_FOR_EACH(node, sym->nb_vals, fexpr) {
+		long symval;
+
+		if (first) {
+			first = false;
+			continue;
+		}
+		fe = node->elem;
+		symval = strtol(str_get(&fe->nb_val), NULL, base);
+
+		switch (type) {
+		case E_LTH:
+			if (symval < val)
+				c = pexpr_or(c, pexpr_alloc_symbol(fe), data,
+					     PEXPR_ARGX);
+			break;
+		case E_LEQ:
+			if (symval <= val)
+				c = pexpr_or(c, pexpr_alloc_symbol(fe), data,
+					     PEXPR_ARGX);
+			break;
+		case E_GTH:
+			if (symval > val)
+				c = pexpr_or(c, pexpr_alloc_symbol(fe), data,
+					     PEXPR_ARGX);
+			break;
+		case E_GEQ:
+			if (symval >= val)
+				c = pexpr_or(c, pexpr_alloc_symbol(fe), data,
+					     PEXPR_ARGX);
+			break;
+		default:
+			perror("Illegal unequal.");
+		}
+	}
+
+	return c;
+}
+
+/*
+ * evaluate an unequality between 2 Boolean symbols
+ */
+static struct pexpr *expr_eval_unequal_bool(struct symbol *left,
+					    struct symbol *right,
+					    enum expr_type type,
+					    struct cfdata *data)
+{
+	struct pexpr *c;
+
+	if (!left || !right)
+		return pexpr_alloc_symbol(data->constants->const_false);
+
+	if (!sym_is_boolean(left) || !sym_is_boolean(right)) {
+		perror("Comparing 2 symbols that should be boolean.");
+		return pexpr_alloc_symbol(data->constants->const_false);
+	}
+
+	switch (type) {
+	case E_LTH:
+		c = pexpr_and(pexpr_not(sym_get_fexpr_both(left, data), data),
+			      sym_get_fexpr_both(right, data), data,
+			      PEXPR_ARGX);
+		if (left->type == S_TRISTATE)
+			c = pexpr_or(
+				c,
+				pexpr_and(pexpr_alloc_symbol(left->fexpr_m),
+					  pexpr_alloc_symbol(right->fexpr_y),
+					  data, PEXPR_ARGX),
+				data, PEXPR_ARGX);
+		break;
+	case E_LEQ:
+		c = pexpr_and(pexpr_alloc_symbol(left->fexpr_y),
+			      pexpr_alloc_symbol(right->fexpr_y), data,
+			      PEXPR_ARGX);
+		if (left->type == S_TRISTATE)
+			c = pexpr_or(
+				c,
+				pexpr_and(pexpr_alloc_symbol(left->fexpr_m),
+					  sym_get_fexpr_both(right, data), data,
+					  PEXPR_ARGX),
+				data, PEXPR_ARGX);
+		c = pexpr_or(c, pexpr_not(sym_get_fexpr_both(left, data), data),
+			     data, PEXPR_ARGX);
+		break;
+	case E_GTH:
+		c = pexpr_and(sym_get_fexpr_both(left, data),
+			      pexpr_not(sym_get_fexpr_both(right, data), data),
+			      data, PEXPR_ARGX);
+		if (right->type == S_TRISTATE)
+			c = pexpr_or(
+				c,
+				pexpr_and(pexpr_alloc_symbol(left->fexpr_y),
+					  pexpr_alloc_symbol(right->fexpr_m),
+					  data, PEXPR_ARGX),
+				data, PEXPR_ARGX);
+		break;
+	case E_GEQ:
+		c = pexpr_and(pexpr_alloc_symbol(left->fexpr_y),
+			      pexpr_alloc_symbol(right->fexpr_y), data,
+			      PEXPR_ARGX);
+		if (right->type == S_TRISTATE)
+			c = pexpr_or(
+				c,
+				pexpr_and(sym_get_fexpr_both(left, data),
+					  pexpr_alloc_symbol(right->fexpr_m),
+					  data, PEXPR_ARGX),
+				data, PEXPR_ARGX);
+		c = pexpr_or(c,
+			     pexpr_not(sym_get_fexpr_both(right, data), data),
+			     data, PEXPR_ARGX);
+		break;
+	default:
+		fprintf(stderr, "Wrong type - %s", __func__);
+		c = pexpr_alloc_symbol(data->constants->const_false);
+	}
+
+	return c;
+}
+/*
+ * calculate, when expr will evaluate to yes or mod
+ */
+struct pexpr *expr_calculate_pexpr_both(struct expr *e, struct cfdata *data)
+{
+	if (!e)
+		return pexpr_alloc_symbol(data->constants->const_false);
+
+	if (!expr_can_evaluate_to_mod(e))
+		return expr_calculate_pexpr_y(e, data);
+
+	switch (e->type) {
+	case E_SYMBOL:
+		return pexpr_or(expr_calculate_pexpr_m(e, data),
+				expr_calculate_pexpr_y(e, data), data,
+				PEXPR_ARGX);
+	case E_AND:
+		return expr_calculate_pexpr_both_and(e->left.expr,
+						     e->right.expr, data);
+	case E_OR:
+		return expr_calculate_pexpr_both_or(e->left.expr, e->right.expr,
+						    data);
+	case E_NOT:
+		return pexpr_or(expr_calculate_pexpr_m(e, data),
+				expr_calculate_pexpr_y(e, data), data,
+				PEXPR_ARGX);
+	case E_EQUAL:
+		return expr_calculate_pexpr_y_equals(e, data);
+	case E_UNEQUAL:
+		return expr_calculate_pexpr_y_unequals(e, data);
+	case E_LTH:
+	case E_LEQ:
+	case E_GTH:
+	case E_GEQ:
+		return expr_calculate_pexpr_y_comp(e, data);
+	default:
+		// TODO
+		fprintf(stderr, "Unhandled type - %s", __func__);
+		return NULL;
+	}
+}
+
+/*
+ * calculate, when expr will evaluate to yes
+ */
+struct pexpr *expr_calculate_pexpr_y(struct expr *e, struct cfdata *data)
+{
+	if (!e)
+		return NULL;
+
+	switch (e->type) {
+	case E_SYMBOL:
+		return pexpr_alloc_symbol(e->left.sym->fexpr_y);
+	case E_AND:
+		return expr_calculate_pexpr_y_and(e->left.expr, e->right.expr,
+						  data);
+	case E_OR:
+		return expr_calculate_pexpr_y_or(e->left.expr, e->right.expr,
+						 data);
+	case E_NOT:
+		return expr_calculate_pexpr_y_not(e->left.expr, data);
+	case E_EQUAL:
+		return expr_calculate_pexpr_y_equals(e, data);
+	case E_UNEQUAL:
+		return expr_calculate_pexpr_y_unequals(e, data);
+	case E_LTH:
+	case E_LEQ:
+	case E_GTH:
+	case E_GEQ:
+		return expr_calculate_pexpr_y_comp(e, data);
+	default:
+		fprintf(stderr, "Unhandled type - %s", __func__);
+		return NULL;
+	}
+}
+
+/*
+ * calculate, when expr will evaluate to mod
+ */
+struct pexpr *expr_calculate_pexpr_m(struct expr *e, struct cfdata *data)
+{
+	if (!e)
+		return NULL;
+
+	if (!expr_can_evaluate_to_mod(e))
+		return pexpr_alloc_symbol(data->constants->const_false);
+
+	switch (e->type) {
+	case E_SYMBOL:
+		return pexpr_alloc_symbol(e->left.sym->fexpr_m);
+	case E_AND:
+		return expr_calculate_pexpr_m_and(e->left.expr, e->right.expr,
+						  data);
+	case E_OR:
+		return expr_calculate_pexpr_m_or(e->left.expr, e->right.expr,
+						 data);
+	case E_NOT:
+		return expr_calculate_pexpr_m_not(e->left.expr, data);
+	default:
+		perror("Trying to evaluate to mod.");
+		return NULL;
+	}
+}
+
+/*
+ * calculate, when expr of type AND will evaluate to yes
+ * A && B
+ */
+struct pexpr *expr_calculate_pexpr_y_and(struct expr *a, struct expr *b,
+					 struct cfdata *data)
+{
+	return pexpr_and(expr_calculate_pexpr_y(a, data),
+			      expr_calculate_pexpr_y(b, data), data,
+			      PEXPR_ARGX);
+}
+
+/*
+ * calculate, when expr of type AND will evaluate to mod
+ * (A || A_m) && (B || B_m) && !(A && B)
+ */
+struct pexpr *expr_calculate_pexpr_m_and(struct expr *a, struct expr *b,
+					 struct cfdata *data)
+{
+	struct pexpr *topright =
+		pexpr_not(pexpr_and(expr_calculate_pexpr_y(a, data),
+					      expr_calculate_pexpr_y(b, data),
+					      data, PEXPR_ARGX),
+			       data);
+	struct pexpr *ll_left = pexpr_or(expr_calculate_pexpr_y(a, data),
+					 expr_calculate_pexpr_m(a, data), data,
+					 PEXPR_ARGX);
+	struct pexpr *ll_right = pexpr_or(expr_calculate_pexpr_y(b, data),
+					  expr_calculate_pexpr_m(b, data), data,
+					  PEXPR_ARGX);
+	struct pexpr *topleft = pexpr_and(ll_left, ll_right, data, PEXPR_ARGX);
+
+	return pexpr_and(topleft, topright, data, PEXPR_ARGX);
+}
+
+/*
+ * calculate, when expr of type AND will evaluate to mod or yes
+ * (A || A_m) && (B || B_m)
+ */
+struct pexpr *expr_calculate_pexpr_both_and(struct expr *a, struct expr *b,
+					    struct cfdata *data)
+{
+	struct pexpr *left = pexpr_or(expr_calculate_pexpr_y(a, data),
+				      expr_calculate_pexpr_m(a, data), data,
+				      PEXPR_ARGX);
+	struct pexpr *right = pexpr_or(expr_calculate_pexpr_y(b, data),
+				       expr_calculate_pexpr_m(b, data), data,
+				       PEXPR_ARGX);
+
+	return pexpr_and(left, right, data, PEXPR_ARGX);
+}
+
+/*
+ * calculate, when expr of type OR will evaluate to yes
+ * A || B
+ */
+struct pexpr *expr_calculate_pexpr_y_or(struct expr *a, struct expr *b,
+					struct cfdata *data)
+{
+	return pexpr_or(expr_calculate_pexpr_y(a, data),
+			     expr_calculate_pexpr_y(b, data), data, PEXPR_ARGX);
+}
+
+/*
+ * calculate, when expr of type OR will evaluate to mod
+ * (A_m || B_m) && !A && !B
+ */
+struct pexpr *expr_calculate_pexpr_m_or(struct expr *a, struct expr *b,
+					struct cfdata *data)
+{
+	struct pexpr *topright =
+		pexpr_not(expr_calculate_pexpr_y(b, data), data);
+	struct pexpr *lowerleft = pexpr_or(expr_calculate_pexpr_m(a, data),
+						expr_calculate_pexpr_m(b, data),
+						data, PEXPR_ARGX);
+	struct pexpr *topleft = pexpr_and(
+		lowerleft,
+		pexpr_not(expr_calculate_pexpr_y(a, data), data), data,
+		PEXPR_ARGX);
+
+	return pexpr_and(topleft, topright, data, PEXPR_ARGX);
+}
+
+/*
+ * calculate, when expr of type OR will evaluate to mod or yes
+ * (A_m || A || B_m || B)
+ */
+struct pexpr *expr_calculate_pexpr_both_or(struct expr *a, struct expr *b,
+					   struct cfdata *data)
+{
+	struct pexpr *left = pexpr_or(expr_calculate_pexpr_y(a, data),
+				      expr_calculate_pexpr_m(a, data), data,
+				      PEXPR_ARGX);
+	struct pexpr *right = pexpr_or(expr_calculate_pexpr_y(b, data),
+				       expr_calculate_pexpr_m(b, data), data,
+				       PEXPR_ARGX);
+
+	return pexpr_or(left, right, data, PEXPR_ARGX);
+}
+
+/*
+ * calculate, when expr of type NOT will evaluate to yes
+ * !(A || A_m)
+ */
+struct pexpr *expr_calculate_pexpr_y_not(struct expr *e, struct cfdata *data)
+{
+	return pexpr_not(pexpr_or(expr_calculate_pexpr_y(e, data),
+					    expr_calculate_pexpr_m(e, data),
+					    data, PEXPR_ARGX),
+			      data);
+}
+
+/*
+ * calculate, when expr of type NOT will evaluate to mod
+ * A_m
+ */
+struct pexpr *expr_calculate_pexpr_m_not(struct expr *e, struct cfdata *data)
+{
+	return expr_calculate_pexpr_m(e, data);
+}
+
+static struct pexpr *equiv_pexpr_share(struct pexpr *a, struct pexpr *b,
+				       struct cfdata *data)
+{
+	struct pexpr *yes = pexpr_and_share(a, b, data);
+	struct pexpr *not = pexpr_and(pexpr_not_share(a, data),
+					   pexpr_not_share(b, data), data,
+					   PEXPR_ARGX);
+
+	return pexpr_or(yes, not, data, PEXPR_ARGX);
+}
+
+static struct pexpr *equiv_pexpr_move(struct pexpr *a, struct pexpr *b,
+				       struct cfdata *data,
+				       enum pexpr_move move)
+{
+	return pexpr_move_wrapper(a, b, data, move, equiv_pexpr_share);
+}
+
+/*
+ * create the fexpr of a non-boolean symbol for a specific value
+ */
+struct fexpr *sym_create_nonbool_fexpr(struct symbol *sym, char *value,
+				       struct cfdata *data)
+{
+	struct fexpr *e;
+	char *s;
+	struct fexpr_node *first =
+		list_first_entry(&sym->nb_vals->list, struct fexpr_node, node);
+
+	if (!strcmp(value, "")) {
+		if (sym->type == S_STRING)
+			return list_next_entry(first, node)->elem;
+		else
+			return first->elem;
+	}
+
+	e = sym_get_nonbool_fexpr(sym, value);
+
+	/* fexpr already exists */
+	if (e != NULL)
+		return e;
+
+	s = value;
+	if (sym->type == S_INT && !string_is_number(value)) {
+		struct symbol *tmp = sym_find(value);
+
+		if (tmp != NULL)
+			s = (char *) tmp->curr.val;
+	} else if (sym->type == S_HEX && !string_is_hex(value)) {
+		struct symbol *tmp = sym_find(value);
+
+		if (tmp != NULL)
+			s = (char *) tmp->curr.val;
+	} else if (sym->type == S_STRING) {
+		struct symbol *tmp = sym_find(value);
+
+		if (tmp != NULL)
+			s = (char *) tmp->curr.val;
+	}
+
+	if (!strcmp(s, "")) {
+		if (sym->type == S_STRING)
+			return list_next_entry(first, node)->elem;
+		else
+			return first->elem;
+	}
+
+	e = sym_get_nonbool_fexpr(sym, s);
+	if (e != NULL)
+		return e;
+
+	e = fexpr_create(data->sat_variable_nr++, FE_NONBOOL, sym->name);
+	e->sym = sym;
+	str_append(&e->name, "=");
+	str_append(&e->name, s);
+	e->nb_val = str_new();
+	str_append(&e->nb_val, s);
+
+	CF_PUSH_BACK(sym->nb_vals, e, fexpr);
+	fexpr_add_to_satmap(e, data);
+
+	return e;
+}
+
+/*
+ * return the fexpr of a non-boolean symbol for a specific value, NULL if
+ * non-existent
+ */
+struct fexpr *sym_get_nonbool_fexpr(struct symbol *sym, char *value)
+{
+	struct fexpr_node *e;
+
+	CF_LIST_FOR_EACH(e, sym->nb_vals, fexpr) {
+		if (strcmp(str_get(&e->elem->nb_val), value) == 0)
+			return e->elem;
+	}
+
+	return NULL;
+}
+
+/*
+ * return the fexpr of a non-boolean symbol for a specific value, if it exists
+ * otherwise create it
+ */
+struct fexpr *sym_get_or_create_nonbool_fexpr(struct symbol *sym, char *value,
+					      struct cfdata *data)
+{
+	struct fexpr *e = sym_get_nonbool_fexpr(sym, value);
+
+	if (e != NULL)
+		return e;
+	else
+		return sym_create_nonbool_fexpr(sym, value, data);
+}
+
+/*
+ * calculate, when expr of type EQUAL will evaluate to yes
+ * Side effect: May create certain values in e->{left,right}.sym->nb_vals
+ */
+struct pexpr *expr_calculate_pexpr_y_equals(struct expr *e, struct cfdata *data)
+{
+	/* comparing 2 tristate constants */
+	if (sym_is_tristate_constant(e->left.sym) &&
+	    sym_is_tristate_constant(e->right.sym))
+		return e->left.sym == e->right.sym ?
+			       pexpr_alloc_symbol(data->constants->const_true) :
+			       pexpr_alloc_symbol(data->constants->const_false);
+
+	/* comparing 2 nonboolean constants */
+	if (sym_is_nonbool_constant(e->left.sym) &&
+	    sym_is_nonbool_constant(e->right.sym))
+		return strcmp(e->left.sym->name, e->right.sym->name) == 0 ?
+			       pexpr_alloc_symbol(data->constants->const_true) :
+			       pexpr_alloc_symbol(data->constants->const_false);
+
+	/* comparing 2 boolean/tristate incl. yes/mod/no constants */
+	if (sym_is_bool_or_triconst(e->left.sym) &&
+	    sym_is_bool_or_triconst(e->right.sym)) {
+		struct pexpr *yes = equiv_pexpr_move(
+			pexpr_alloc_symbol(e->left.sym->fexpr_y),
+			pexpr_alloc_symbol(e->right.sym->fexpr_y), data,
+			PEXPR_ARGX);
+		struct pexpr *mod = equiv_pexpr_move(
+			pexpr_alloc_symbol(e->left.sym->fexpr_m),
+			pexpr_alloc_symbol(e->right.sym->fexpr_m), data,
+			PEXPR_ARGX);
+
+		return pexpr_and(yes, mod, data, PEXPR_ARGX);
+	}
+
+	/* comparing nonboolean with a constant */
+	if (sym_is_nonboolean(e->left.sym) &&
+	    sym_is_nonbool_constant(e->right.sym))
+		return pexpr_alloc_symbol(sym_get_or_create_nonbool_fexpr(
+			e->left.sym, e->right.sym->name, data));
+
+	if (sym_is_nonbool_constant(e->left.sym) &&
+	    sym_is_nonboolean(e->right.sym))
+		return pexpr_alloc_symbol(sym_get_or_create_nonbool_fexpr(
+			e->right.sym, e->left.sym->name, data));
+
+	/* comparing nonboolean with tristate constant, will never be true */
+	if (sym_is_nonboolean(e->left.sym) &&
+	    sym_is_tristate_constant(e->right.sym))
+		return pexpr_alloc_symbol(data->constants->const_false);
+	if (sym_is_tristate_constant(e->left.sym) &&
+	    sym_is_nonboolean(e->right.sym))
+		return pexpr_alloc_symbol(data->constants->const_false);
+
+	/* comparing 2 nonboolean symbols */
+	if (sym_is_nonboolean(e->left.sym) && sym_is_nonboolean(e->right.sym)) {
+		struct pexpr *c =
+			pexpr_alloc_symbol(data->constants->const_false);
+		struct fexpr *e1, *e2;
+		struct fexpr_node *node1, *node2;
+		bool first1 = true;
+
+		CF_LIST_FOR_EACH(node1, e->left.sym->nb_vals, fexpr) {
+			bool first2 = true;
+
+			if (first1) {
+				first1 = false;
+				continue;
+			}
+			e1 = node1->elem;
+			CF_LIST_FOR_EACH(node2, e->right.sym->nb_vals, fexpr)
+			{
+				if (first2) {
+					first2 = false;
+					continue;
+				}
+
+				e2 = node2->elem;
+				if (!strcmp(str_get(&e1->nb_val),
+					    str_get(&e2->nb_val))) {
+					c = pexpr_or(
+						c,
+						pexpr_and(
+							pexpr_alloc_symbol(e1),
+							pexpr_alloc_symbol(e2),
+							data, PEXPR_ARGX),
+						data, PEXPR_ARGX);
+					break;
+				}
+			}
+		}
+		return c;
+	}
+
+	/*
+	 * comparing boolean item with nonboolean constant, will never be true
+	 */
+	if (sym_is_tristate_constant(e->left.sym) &&
+	    sym_is_nonbool_constant(e->right.sym))
+		return pexpr_alloc_symbol(data->constants->const_false);
+	if (sym_is_nonbool_constant(e->left.sym) &&
+	    sym_is_tristate_constant(e->right.sym))
+		return pexpr_alloc_symbol(data->constants->const_false);
+
+	/* comparing symbol of type unknown with tristate constant */
+	if (e->left.sym->type == S_UNKNOWN &&
+	    sym_is_tristate_constant(e->right.sym))
+		return pexpr_alloc_symbol(data->constants->const_false);
+	if (sym_is_tristate_constant(e->left.sym) &&
+	    e->right.sym->type == S_UNKNOWN)
+		return pexpr_alloc_symbol(data->constants->const_false);
+
+	/* any other comparison is not supported and should not be executed */
+	fprintf(stderr, "Unsupported equality in:");
+	expr_fprint(e, stderr);
+
+	return pexpr_alloc_symbol(data->constants->const_false);
+}
+
+/*
+ * transform an UNEQUAL into a Not(EQUAL)
+ */
+struct pexpr *expr_calculate_pexpr_y_unequals(struct expr *e,
+					      struct cfdata *data)
+{
+	return pexpr_not(expr_calculate_pexpr_y_equals(e, data), data);
+}
+
+struct pexpr *expr_calculate_pexpr_y_comp(struct expr *e, struct cfdata *data)
+{
+	if (!e)
+		return NULL;
+
+	switch (e->type) {
+	case E_LTH:
+	case E_LEQ:
+	case E_GTH:
+	case E_GEQ:
+		/* compare non-Boolean symbol with constant */
+		if (sym_is_nonboolean(e->left.sym) &&
+			e->right.sym->type == S_UNKNOWN &&
+			string_is_number(e->right.sym->name)
+		) {
+			return expr_eval_unequal_nonbool_const(
+				e->left.sym, e->right.sym, e->type, data);
+		}
+		if (sym_is_nonboolean(e->right.sym) &&
+			e->left.sym->type == S_UNKNOWN &&
+			string_is_number(e->left.sym->name)
+		) {
+			return expr_eval_unequal_nonbool_const(
+				e->right.sym, e->left.sym, e->type, data);
+		}
+
+		/* compare 2 Boolean symbols */
+		if (sym_is_boolean(e->left.sym) && sym_is_boolean(e->right.sym))
+			return expr_eval_unequal_bool(e->left.sym, e->right.sym,
+						      e->type, data);
+
+		return pexpr_alloc_symbol(data->constants->const_false);
+	default:
+		fprintf(stderr, "Unhandled type - %s", __func__);
+		return NULL;
+	}
+}
+
+static struct pexpr *pexpr_move_wrapper(
+	struct pexpr *a, struct pexpr *b, struct cfdata *data,
+	enum pexpr_move move,
+	struct pexpr *(*func)(struct pexpr *, struct pexpr *, struct cfdata *))
+{
+	struct pexpr *retval = func(a, b, data);
+
+	switch (move) {
+	case PEXPR_ARG1:
+		pexpr_put(a);
+		break;
+	case PEXPR_ARG2:
+		pexpr_put(b);
+		break;
+	case PEXPR_ARGX:
+		pexpr_put(a);
+		pexpr_put(b);
+		break;
+	default:
+		fprintf(stderr, "%s: invalid value for @move - %d\n", __func__,
+			move);
+	}
+	return retval;
+}
+
+struct pexpr *pexpr_and(struct pexpr *a, struct pexpr *b, struct cfdata *data,
+			enum pexpr_move move)
+{
+	return pexpr_move_wrapper(a, b, data, move, pexpr_and_share);
+}
+
+/*
+ * macro to create a pexpr of type AND
+ */
+struct pexpr *pexpr_and_share(struct pexpr *a, struct pexpr *b,
+			      struct cfdata *data)
+{
+	struct pexpr *e;
+
+	/* A && A -> A */
+	if (a == b || pexpr_test_eq(a, b, data)) {
+		pexpr_get(a);
+		return a;
+	}
+
+	/* simplifications:
+	 * expr && False -> False
+	 * expr && True  -> expr
+	 */
+	if ((a->type == PE_SYMBOL &&
+	     a->left.fexpr == data->constants->const_false) ||
+	    (b->type == PE_SYMBOL &&
+	     b->left.fexpr == data->constants->const_true)) {
+		pexpr_get(a);
+		return a;
+	}
+
+	if ((b->type == PE_SYMBOL &&
+	     b->left.fexpr == data->constants->const_false) ||
+	    (a->type == PE_SYMBOL &&
+	     a->left.fexpr == data->constants->const_true)) {
+		pexpr_get(b);
+		return b;
+	}
+
+	/* (A && B) && C -> A && B if B == C */
+	if (a->type == PE_AND && pexpr_test_eq(a->right.pexpr, b, data)) {
+		pexpr_get(a);
+		return a;
+	}
+
+	/* A && (B && C) -> B && C if A == B */
+	if (b->type == PE_AND && pexpr_test_eq(a, b->left.pexpr, data)) {
+		pexpr_get(b);
+		return b;
+	}
+
+	if (a->type == PE_OR && b->type == PE_OR) {
+		e = NULL;
+		/* (A || B) && (C || D) -> A || (B && D) if A == C */
+		if (pexpr_test_eq(a->left.pexpr, b->left.pexpr, data)) {
+			e = pexpr_or(a->left.pexpr,
+					  pexpr_and_share(a->right.pexpr,
+							  b->right.pexpr, data),
+					  data, PEXPR_ARG2);
+		}
+		/* (A || B) && (C || D) -> B || (A && C) if B == D */
+		else if (pexpr_test_eq(a->right.pexpr, b->right.pexpr, data)) {
+			e = pexpr_or(a->right.pexpr,
+					  pexpr_and_share(a->left.pexpr,
+							  b->left.pexpr, data),
+					  data, PEXPR_ARG2);
+		}
+		/* (A || B) && (C || D) -> A || (B && C) if A == D */
+		else if (pexpr_test_eq(a->left.pexpr, b->right.pexpr, data)) {
+			e = pexpr_or(a->left.pexpr,
+					  pexpr_and_share(a->right.pexpr,
+							  b->left.pexpr, data),
+					  data, PEXPR_ARG2);
+		}
+		/* (A || B) && (C || D) -> B || (A && D) if B == C */
+		else if (pexpr_test_eq(a->right.pexpr, b->left.pexpr, data)) {
+			e = pexpr_or(a->right.pexpr,
+					  pexpr_and_share(a->left.pexpr,
+							  b->right.pexpr, data),
+					  data, PEXPR_ARG2);
+		}
+		if (e)
+			return e;
+	}
+
+	/* general case */
+	e = xmalloc(sizeof(*e));
+	pexpr_get(a);
+	pexpr_get(b);
+	pexpr_construct_and(e, a, b, 1);
+	return e;
+}
+
+struct pexpr *pexpr_or(struct pexpr *a, struct pexpr *b, struct cfdata *data,
+		       enum pexpr_move move)
+{
+	return pexpr_move_wrapper(a, b, data, move, pexpr_or_share);
+}
+
+/*
+ * macro to create a pexpr of type OR
+ */
+struct pexpr *pexpr_or_share(struct pexpr *a, struct pexpr *b,
+			     struct cfdata *data)
+{
+	struct pexpr *e;
+	bool cond1, cond2;
+
+	/* A || A  -> A */
+	if (a == b || pexpr_test_eq(a, b, data)) {
+		pexpr_get(a);
+		return a;
+	}
+
+	/* simplifications:
+	 * A || False -> A
+	 * A || True  -> True
+	 */
+	cond1 = a->type == PE_SYMBOL &&
+		a->left.fexpr == data->constants->const_false;
+	cond2 = b->type == PE_SYMBOL &&
+		b->left.fexpr == data->constants->const_true;
+	if (cond1 || cond2) {
+		pexpr_get(b);
+		return b;
+	}
+	cond1 = b->type == PE_SYMBOL &&
+		b->left.fexpr == data->constants->const_false;
+	cond2 = a->type == PE_SYMBOL &&
+		a->left.fexpr == data->constants->const_true;
+	if (cond1 || cond2) {
+		pexpr_get(a);
+		return a;
+	}
+
+	/* A || (B && C) -> A if (A == B || A == C) */
+	if (b->type == PE_AND && (pexpr_test_eq(a, b->left.pexpr, data) ||
+				  pexpr_test_eq(a, b->right.pexpr, data))) {
+		pexpr_get(a);
+		return a;
+	}
+	/* (A && B) || C -> C if (A == C || B == C) */
+	if (a->type == PE_AND && (pexpr_test_eq(a->left.pexpr, b, data) ||
+				  pexpr_test_eq(a->right.pexpr, b, data))) {
+		pexpr_get(b);
+		return b;
+	}
+
+	/* -A || B -> True if A == B
+	 * A || -B -> True if A == B
+	 */
+	cond1 = a->type == PE_NOT && pexpr_test_eq(a->left.pexpr, b, data);
+	cond2 = b->type == PE_NOT && pexpr_test_eq(a, b->left.pexpr, data);
+	if (cond1 || cond2)
+		return pexpr_alloc_symbol(data->constants->const_true);
+
+	if (a->type == PE_AND && b->type == PE_AND) {
+		e = NULL;
+		/* (A && B) || (C && D) -> A && (B || D) if (A == C) */
+		if (pexpr_test_eq(a->left.pexpr, b->left.pexpr, data)) {
+			e = pexpr_and(a->left.pexpr,
+				      pexpr_or_share(a->right.pexpr,
+						     b->right.pexpr, data),
+				      data, PEXPR_ARG2);
+		}
+		/* (A && B) || (C && D) -> B && (A || C) if (B == D) */
+		if (pexpr_test_eq(a->right.pexpr, b->right.pexpr, data)) {
+			e = pexpr_and(a->right.pexpr,
+				      pexpr_or_share(a->left.pexpr,
+						     b->left.pexpr, data),
+				      data, PEXPR_ARG2);
+		}
+		/* (A && B) || (C && D) -> A && (B || C) if (A == D) */
+		if (pexpr_test_eq(a->left.pexpr, b->right.pexpr, data)) {
+			e = pexpr_and(a->left.pexpr,
+				      pexpr_or_share(a->right.pexpr,
+						     b->left.pexpr, data),
+				      data, PEXPR_ARG2);
+		}
+		/* (A && B) || (C && D) -> B && (A || D) if (B == C) */
+		if (pexpr_test_eq(a->right.pexpr, b->left.pexpr, data)) {
+			e = pexpr_and(a->right.pexpr,
+				      pexpr_or_share(a->left.pexpr,
+						     b->right.pexpr, data),
+				      data, PEXPR_ARG2);
+		}
+		if (e)
+			return e;
+	}
+
+	/* (A && B) || (C || D) -> C || D if
+	 * A == C || A == D || B == C || B == D
+	 */
+	if (a->type == PE_AND && b->type == PE_OR &&
+	    (pexpr_test_eq(a->left.pexpr, b->left.pexpr, data) ||
+	     pexpr_test_eq(a->left.pexpr, b->right.pexpr, data) ||
+	     pexpr_test_eq(a->right.pexpr, b->left.pexpr, data) ||
+	     pexpr_test_eq(a->right.pexpr, b->right.pexpr, data))) {
+		pexpr_get(b);
+		return b;
+	}
+	/* (C || D) || (A && B) -> C || D if
+	 * A == C || A == D || B == C || B == D
+	 */
+	if (a->type == PE_OR && b->type == PE_AND &&
+	    (pexpr_test_eq(a->left.pexpr, b->left.pexpr, data) ||
+	     pexpr_test_eq(a->left.pexpr, b->right.pexpr, data) ||
+	     pexpr_test_eq(a->right.pexpr, b->left.pexpr, data) ||
+	     pexpr_test_eq(a->right.pexpr, b->right.pexpr, data))) {
+		pexpr_get(a);
+		return a;
+	}
+
+	/* general case */
+	e = xmalloc(sizeof(*e));
+	pexpr_get(a);
+	pexpr_get(b);
+	pexpr_construct_or(e, a, b, 1);
+
+	return e;
+}
+
+struct pexpr *pexpr_not(struct pexpr *a, struct cfdata *data)
+{
+	struct pexpr *retval = pexpr_not_share(a, data);
+
+	pexpr_put(a);
+	return retval;
+}
+
+/*
+ * Builds NOT(@a)
+ */
+struct pexpr *pexpr_not_share(struct pexpr *a, struct cfdata *data)
+{
+	struct pexpr *ret_val;
+
+	if (a->type == PE_SYMBOL &&
+	    a->left.fexpr == data->constants->const_false)
+		ret_val = pexpr_alloc_symbol(data->constants->const_true);
+	else if (a->type == PE_SYMBOL &&
+	    a->left.fexpr == data->constants->const_true)
+		ret_val = pexpr_alloc_symbol(data->constants->const_false);
+	/* eliminate double negation */
+	else if (a->type == PE_NOT) {
+		ret_val = a->left.pexpr;
+		pexpr_get(ret_val);
+	}
+	/* De Morgan */
+	else if (a->type == PE_AND) {
+		ret_val = xmalloc(sizeof(*ret_val));
+		pexpr_construct_or(ret_val,
+				   pexpr_not_share(a->left.pexpr, data),
+				   pexpr_not_share(a->right.pexpr, data), 1);
+	} else if (a->type == PE_OR) {
+		ret_val = xmalloc(sizeof(*ret_val));
+		pexpr_construct_and(ret_val,
+				    pexpr_not_share(a->left.pexpr, data),
+				    pexpr_not_share(a->right.pexpr, data), 1);
+	} else {
+		ret_val = xmalloc(sizeof(*ret_val));
+		pexpr_get(a);
+		pexpr_construct_not(ret_val, a, 1);
+	}
+
+	return ret_val;
+}
+
+struct pexpr *pexpr_implies(struct pexpr *a, struct pexpr *b,
+			    struct cfdata *data, enum pexpr_move move)
+{
+	return pexpr_move_wrapper(a, b, data, move, pexpr_implies_share);
+}
+
+/*
+ * macro to construct a pexpr for "A implies B"
+ */
+struct pexpr *pexpr_implies_share(struct pexpr *a, struct pexpr *b,
+				  struct cfdata *data)
+{
+	/* A => B -> True if A == B */
+	if (a == b || pexpr_test_eq(a, b, data))
+		return pexpr_alloc_symbol(data->constants->const_true);
+
+	/* (A => B && C) -> (A => C) if A == B */
+	if (b->type == PE_AND && pexpr_test_eq(a, b->left.pexpr, data))
+		return pexpr_implies_share(a, b->right.pexpr, data);
+	/* (A => B && C) -> (A => B) if A == C */
+	if (b->type == PE_AND && pexpr_test_eq(a, b->right.pexpr, data))
+		return pexpr_implies_share(a, b->left.pexpr, data);
+
+	/* (A => B || C) -> True if (A == B || A == C) */
+	if (b->type == PE_OR && (pexpr_test_eq(a, b->left.pexpr, data) ||
+				 pexpr_test_eq(a, b->right.pexpr, data)))
+		return pexpr_alloc_symbol(data->constants->const_true);
+
+	/* (A && B => C) -> True if (A == C || B == C) */
+	if (a->type == PE_AND && (pexpr_test_eq(a->left.pexpr, b, data) ||
+				  pexpr_test_eq(a->right.pexpr, b, data)))
+		return pexpr_alloc_symbol(data->constants->const_true);
+
+	return pexpr_or(pexpr_not_share(a, data), b, data, PEXPR_ARG1);
+}
+
+/*
+ * check whether a pexpr is in CNF
+ */
+bool pexpr_is_cnf(struct pexpr *e)
+{
+	if (!e)
+		return false;
+
+	switch (e->type) {
+	case PE_SYMBOL:
+		return true;
+	case PE_AND:
+		return false;
+	case PE_OR:
+		return pexpr_is_cnf(e->left.pexpr) &&
+		       pexpr_is_cnf(e->right.pexpr);
+	case PE_NOT:
+		return e->left.pexpr->type == PE_SYMBOL;
+	}
+
+	return false;
+}
+
+/*
+ * check whether a pexpr is in NNF
+ */
+bool pexpr_is_nnf(struct pexpr *e)
+{
+	if (!e)
+		return false;
+
+	switch (e->type) {
+	case PE_SYMBOL:
+		return true;
+	case PE_AND:
+	case PE_OR:
+		return pexpr_is_nnf(e->left.pexpr) &&
+		       pexpr_is_nnf(e->right.pexpr);
+	case PE_NOT:
+		return e->left.pexpr->type == PE_SYMBOL;
+	}
+
+	return false;
+}
+
+/*
+ * return fexpr_both for a symbol
+ */
+struct pexpr *sym_get_fexpr_both(struct symbol *sym, struct cfdata *data)
+{
+	return sym->type == S_TRISTATE ?
+		       pexpr_or(pexpr_alloc_symbol(sym->fexpr_m),
+				pexpr_alloc_symbol(sym->fexpr_y), data,
+				PEXPR_ARGX) :
+		       pexpr_alloc_symbol(sym->fexpr_y);
+}
+
+/*
+ * return fexpr_sel_both for a symbol
+ */
+struct pexpr *sym_get_fexpr_sel_both(struct symbol *sym, struct cfdata *data)
+{
+	if (!sym->rev_dep.expr)
+		return pexpr_alloc_symbol(data->constants->const_false);
+
+	return sym->type == S_TRISTATE ?
+		       pexpr_or(pexpr_alloc_symbol(sym->fexpr_sel_m),
+				pexpr_alloc_symbol(sym->fexpr_sel_y), data,
+				PEXPR_ARGX) :
+		       pexpr_alloc_symbol(sym->fexpr_sel_y);
+}
+
+/*
+ * check, if the fexpr is a symbol, a True/False-constant, a literal symbolizing
+ * a non-boolean or a choice symbol
+ */
+bool fexpr_is_symbol(struct fexpr *e)
+{
+	return e->type == FE_SYMBOL || e->type == FE_FALSE ||
+	       e->type == FE_TRUE || e->type == FE_NONBOOL ||
+	       e->type == FE_CHOICE || e->type == FE_SELECT ||
+	       e->type == FE_NPC;
+}
+
+/*
+ * check whether a pexpr is a symbol or a negated symbol
+ */
+bool pexpr_is_symbol(struct pexpr *e)
+{
+	return e->type == PE_SYMBOL ||
+	       (e->type == PE_NOT && e->left.pexpr->type == PE_SYMBOL);
+}
+
+/*
+ * check whether the fexpr is a constant (true/false)
+ */
+bool fexpr_is_constant(struct fexpr *e, struct cfdata *data)
+{
+	return e == data->constants->const_true ||
+	       e == data->constants->const_false;
+}
+
+/*
+ * add a fexpr to the satmap
+ */
+void fexpr_add_to_satmap(struct fexpr *e, struct cfdata *data)
+{
+	if (e->satval >= data->satmap_size) {
+		data->satmap = xrealloc(data->satmap,
+					data->satmap_size * 2 *
+						sizeof(*data->satmap));
+		data->satmap_size *= 2;
+	}
+
+	data->satmap[e->satval] = e;
+}
+
+/*
+ * print a fexpr
+ */
+void fexpr_print(char *tag, struct fexpr *e)
+{
+	if (!e)
+		return;
+
+	printf("%s: %s\n", tag, str_get(&e->name));
+}
+
+/*
+ * write an fexpr into a string (format needed for testing)
+ */
+void fexpr_as_char(struct fexpr *e, struct gstr *s)
+{
+	if (!e)
+		return;
+
+	switch (e->type) {
+	case FE_SYMBOL:
+	case FE_CHOICE:
+	case FE_SELECT:
+	case FE_NPC:
+	case FE_NONBOOL:
+		str_append(s, "definedEx(");
+		str_append(s, str_get(&e->name));
+		str_append(s, ")");
+		return;
+	case FE_FALSE:
+		str_append(s, "0");
+		return;
+	case FE_TRUE:
+		str_append(s, "1");
+		return;
+	default:
+		return;
+	}
+}
+
+/*
+ * write a pexpr into a string
+ */
+void pexpr_as_char(struct pexpr *e, struct gstr *s, int parent,
+		   struct cfdata *data)
+{
+	if (!e)
+		return;
+
+	switch (e->type) {
+	case PE_SYMBOL:
+		if (e->left.fexpr == data->constants->const_false) {
+			str_append(s, "0");
+			return;
+		}
+		if (e->left.fexpr == data->constants->const_true) {
+			str_append(s, "1");
+			return;
+		}
+		str_append(s, "definedEx(");
+		str_append(s, str_get(&e->left.fexpr->name));
+		str_append(s, ")");
+		return;
+	case PE_AND:
+		if (parent != PE_AND)
+			str_append(s, "(");
+		pexpr_as_char(e->left.pexpr, s, PE_AND, data);
+		str_append(s, " && ");
+		pexpr_as_char(e->right.pexpr, s, PE_AND, data);
+		if (parent != PE_AND)
+			str_append(s, ")");
+		return;
+	case PE_OR:
+		if (parent != PE_OR)
+			str_append(s, "(");
+		pexpr_as_char(e->left.pexpr, s, PE_OR, data);
+		str_append(s, " || ");
+		pexpr_as_char(e->right.pexpr, s, PE_OR, data);
+		if (parent != PE_OR)
+			str_append(s, ")");
+		return;
+	case PE_NOT:
+		str_append(s, "!");
+		pexpr_as_char(e->left.pexpr, s, PE_NOT, data);
+		return;
+	}
+}
+
+/*
+ * write a pexpr into a string
+ */
+void pexpr_as_char_short(struct pexpr *e, struct gstr *s, int parent)
+{
+	if (!e)
+		return;
+
+	switch (e->type) {
+	case PE_SYMBOL:
+		str_append(s, str_get(&e->left.fexpr->name));
+		return;
+	case PE_AND:
+		if (parent != PE_AND)
+			str_append(s, "(");
+		pexpr_as_char_short(e->left.pexpr, s, PE_AND);
+		str_append(s, " && ");
+		pexpr_as_char_short(e->right.pexpr, s, PE_AND);
+		if (parent != PE_AND)
+			str_append(s, ")");
+		return;
+	case PE_OR:
+		if (parent != PE_OR)
+			str_append(s, "(");
+		pexpr_as_char_short(e->left.pexpr, s, PE_OR);
+		str_append(s, " || ");
+		pexpr_as_char_short(e->right.pexpr, s, PE_OR);
+		if (parent != PE_OR)
+			str_append(s, ")");
+		return;
+	case PE_NOT:
+		str_append(s, "!");
+		pexpr_as_char_short(e->left.pexpr, s, PE_NOT);
+		return;
+	}
+}
+
+/*
+ * check whether a pexpr contains a specific fexpr
+ */
+bool pexpr_contains_fexpr(struct pexpr *e, struct fexpr *fe)
+{
+	if (!e)
+		return false;
+
+	switch (e->type) {
+	case PE_SYMBOL:
+		return e->left.fexpr->satval == fe->satval;
+	case PE_AND:
+	case PE_OR:
+		return pexpr_contains_fexpr(e->left.pexpr, fe) ||
+			pexpr_contains_fexpr(e->right.pexpr, fe);
+	case PE_NOT:
+		return e->left.pexpr->left.fexpr->satval == fe->satval;
+	}
+
+	return false;
+}
+
+/*
+ * print a fexpr_list
+ */
+void fexpr_list_print(char *title, struct fexpr_list *list)
+{
+	struct fexpr_node *node;
+	bool first = true;
+
+	printf("%s: [", title);
+
+	CF_LIST_FOR_EACH(node, list, fexpr) {
+		if (first)
+			first = false;
+		else
+			printf(", ");
+		printf("%s", str_get(&node->elem->name));
+	}
+
+	printf("]\n");
+}
+
+/*
+ * print a fexl_list
+ */
+void fexl_list_print(char *title, struct fexl_list *list)
+{
+	struct fexl_node *node;
+
+	printf("%s:\n", title);
+
+	CF_LIST_FOR_EACH(node, list, fexl)
+		fexpr_list_print(":", node->elem);
+}
+
+/*
+ * print a pexpr_list
+ */
+void pexpr_list_print(char *title, struct pexpr_list *list)
+{
+	struct pexpr_node *node;
+
+	printf("%s: [", title);
+
+	CF_LIST_FOR_EACH(node, list, pexpr) {
+		pexpr_print_util(node->elem, -1);
+		if (node->node.next != &list->list)
+			printf(", ");
+	}
+
+	printf("]\n");
+}
+
+/*
+ * free an defm_list (and pexpr_put the conditions of the maps and free the
+ * node->element's)
+ */
+void defm_list_destruct(struct defm_list *list)
+{
+	struct defm_node *node;
+
+	CF_LIST_FOR_EACH(node, list, defm)
+		pexpr_put(node->elem->e);
+	CF_LIST_FREE(list, defm);
+}
+
+/*
+ * free a pexpr_list (and pexpr_put the elements)
+ */
+void pexpr_list_free_put(struct pexpr_list *list)
+{
+	struct pexpr_node *node;
+
+	CF_LIST_FOR_EACH(node, list, pexpr)
+		pexpr_put(node->elem);
+	CF_LIST_FREE(list, pexpr);
+}
+
+/*
+ * simplify a pexpr in-place
+ *	pexpr && False -> False
+ *	pexpr && True  -> pexpr
+ *	pexpr || False -> pexpr
+ *	pexpr || True  -> True
+ */
+static void pexpr_eliminate_yn(struct pexpr *e, struct cfdata *data)
+{
+	struct pexpr *tmp;
+	unsigned int ref_count;
+
+	if (!e)
+		return;
+
+	switch (e->type) {
+	case PE_AND:
+		pexpr_eliminate_yn(e->left.pexpr, data);
+		pexpr_eliminate_yn(e->right.pexpr, data);
+		if (e->left.pexpr->type == PE_SYMBOL) {
+			if (e->left.pexpr->left.fexpr ==
+			    data->constants->const_false) {
+				pexpr_put(e->left.pexpr);
+				pexpr_put(e->right.pexpr);
+				ref_count = e->ref_count;
+				pexpr_construct_sym(
+					e, data->constants->const_false,
+					ref_count);
+				return;
+			} else if (e->left.pexpr->left.fexpr ==
+				   data->constants->const_true) {
+				pexpr_put(e->left.pexpr);
+				tmp = e->right.pexpr;
+				ref_count = e->ref_count;
+				pexpr_shallow_copy(e, tmp, ref_count);
+				pexpr_put(tmp);
+				return;
+			}
+		}
+		if (e->right.pexpr->type == PE_SYMBOL) {
+			if (e->right.pexpr->left.fexpr ==
+			    data->constants->const_false) {
+				pexpr_put(e->left.pexpr);
+				pexpr_put(e->right.pexpr);
+				ref_count = e->ref_count;
+				pexpr_construct_sym(
+					e, data->constants->const_false,
+					ref_count);
+				return;
+			} else if (e->right.pexpr->left.fexpr ==
+				   data->constants->const_true) {
+				pexpr_put(e->right.pexpr);
+				tmp = e->left.pexpr;
+				ref_count = e->ref_count;
+				pexpr_shallow_copy(e, tmp, ref_count);
+				pexpr_put(tmp);
+				return;
+			}
+		}
+		break;
+	case PE_OR:
+		pexpr_eliminate_yn(e->left.pexpr, data);
+		pexpr_eliminate_yn(e->right.pexpr, data);
+		if (e->left.pexpr->type == PE_SYMBOL) {
+			if (e->left.pexpr->left.fexpr ==
+			    data->constants->const_false) {
+				pexpr_put(e->left.pexpr);
+				tmp = e->right.pexpr;
+				ref_count = e->ref_count;
+				pexpr_shallow_copy(e, tmp, ref_count);
+				pexpr_put(tmp);
+				return;
+			} else if (e->left.pexpr->left.fexpr ==
+				   data->constants->const_true) {
+				pexpr_put(e->left.pexpr);
+				pexpr_put(e->right.pexpr);
+				ref_count = e->ref_count;
+				pexpr_construct_sym(
+					e, data->constants->const_true,
+					ref_count);
+				return;
+			}
+		}
+		if (e->right.pexpr->type == PE_SYMBOL) {
+			if (e->right.pexpr->left.fexpr ==
+			    data->constants->const_false) {
+				pexpr_put(e->right.pexpr);
+				tmp = e->left.pexpr;
+				ref_count = e->ref_count;
+				pexpr_shallow_copy(e, tmp, ref_count);
+				pexpr_put(tmp);
+				return;
+			} else if (e->right.pexpr->left.fexpr ==
+				   data->constants->const_true) {
+				pexpr_put(e->left.pexpr);
+				pexpr_put(e->right.pexpr);
+				ref_count = e->ref_count;
+				pexpr_construct_sym(e,
+						    data->constants->const_true,
+						    ref_count);
+				return;
+			}
+		}
+	default:
+		break;
+	}
+}
+
+static void pexpr_shallow_copy(struct pexpr *dest, struct pexpr *org,
+			       unsigned int ref_count)
+{
+	struct pexpr inter;
+
+	inter.type = org->type;
+	inter.left = org->left;
+	inter.right = org->right;
+	if (org->type == PE_OR || org->type == PE_AND) {
+		pexpr_get(org->left.pexpr);
+		pexpr_get(org->right.pexpr);
+	} else if (org->type == PE_NOT) {
+		pexpr_get(org->left.pexpr);
+	}
+	inter.ref_count = ref_count;
+	*dest = inter;
+}
+
+/*
+ * copy a pexpr
+ */
+struct pexpr *pexpr_deep_copy(const struct pexpr *org)
+{
+	struct pexpr *e;
+
+	if (!org)
+		return NULL;
+
+	e = xmalloc(sizeof(*org));
+	memcpy(e, org, sizeof(*org));
+	e->ref_count = 1;
+	switch (org->type) {
+	case PE_SYMBOL:
+		e->left = org->left;
+		break;
+	case PE_AND:
+	case PE_OR:
+		e->left.pexpr = pexpr_deep_copy(org->left.pexpr);
+		e->right.pexpr = pexpr_deep_copy(org->right.pexpr);
+		break;
+	case PE_NOT:
+		e->left.pexpr = pexpr_deep_copy(org->left.pexpr);
+		break;
+	}
+
+	return e;
+}
+
+/*
+ * free a pexpr
+ */
+void pexpr_free_depr(struct pexpr *e)
+{
+	if (!e)
+		return;
+
+	switch (e->type) {
+	case PE_SYMBOL:
+		break;
+	case PE_AND:
+	case PE_OR:
+		pexpr_free_depr(e->left.pexpr);
+		pexpr_free_depr(e->right.pexpr);
+		break;
+	case PE_NOT:
+		pexpr_free_depr(e->left.pexpr);
+		break;
+	}
+
+	free(e);
+}
+
+/*
+ * Increments ref_count and returns @e
+ */
+struct pexpr *pexpr_get(struct pexpr *e)
+{
+	++e->ref_count;
+	return e;
+}
+
+/*
+ * Decrements ref_count and if it becomes 0, it recursively puts the references
+ * to its children and calls ``free(e)``. If @e == NULL, it does nothing.
+ */
+void pexpr_put(struct pexpr *e)
+{
+	if (!e)
+		return;
+
+	if (e->ref_count == 0) {
+		printd("Invalid call to %s - ref_count is zero\n", __func__);
+		return;
+	}
+
+	--e->ref_count;
+	if (e->ref_count > 0)
+		return;
+
+	switch (e->type) {
+	case PE_SYMBOL:
+		break;
+	case PE_AND:
+	case PE_OR:
+		pexpr_put(e->left.pexpr);
+		pexpr_put(e->right.pexpr);
+		break;
+	case PE_NOT:
+		pexpr_put(e->left.pexpr);
+		break;
+	}
+
+	free(e);
+}
+
+/*
+ * calls pexpr_put for a NULL-terminated array of struct pexpr *
+ */
+void _pexpr_put_list(struct pexpr **es)
+{
+	for (; *es != NULL; es++)
+		pexpr_put(*es);
+}
+
+#define e1 (*ep1)
+#define e2 (*ep2)
+/*
+ * pexpr_eliminate_eq() helper
+ */
+static void __pexpr_eliminate_eq(enum pexpr_type type, struct pexpr **ep1,
+				 struct pexpr **ep2, struct cfdata *data)
+{
+	/* recurse down to the leaves */
+	if (e1->type == type) {
+		__pexpr_eliminate_eq(type, &e1->left.pexpr, &e2, data);
+		__pexpr_eliminate_eq(type, &e1->right.pexpr, &e2, data);
+		return;
+	}
+	if (e2->type == type) {
+		__pexpr_eliminate_eq(type, &e1, &e2->left.pexpr, data);
+		__pexpr_eliminate_eq(type, &e1, &e2->right.pexpr, data);
+		return;
+	}
+
+	/* e1 and e2 are leaves. Compare them. */
+	if (e1->type == PE_SYMBOL && e2->type == PE_SYMBOL &&
+	    e1->left.fexpr->satval == e2->left.fexpr->satval &&
+	    (e1->left.fexpr == data->constants->const_true ||
+	     e2->left.fexpr == data->constants->const_false))
+		return;
+	if (!pexpr_test_eq(e1, e2, data))
+		return;
+
+	/* e1 and e2 are equal leaves. Prepare them for elimination. */
+	trans_count++;
+	pexpr_put(e1);
+	pexpr_put(e2);
+	switch (type) {
+	case PE_AND:
+		e1 = pexpr_alloc_symbol(data->constants->const_true);
+		e2 = pexpr_alloc_symbol(data->constants->const_true);
+		break;
+	case PE_OR:
+		e1 = pexpr_alloc_symbol(data->constants->const_false);
+		e2 = pexpr_alloc_symbol(data->constants->const_false);
+		break;
+	default:
+		break;
+	}
+}
+
+/*
+ * rewrite pexpr ep1 and ep2 to remove operands common to both
+ */
+static void pexpr_eliminate_eq(struct pexpr **ep1, struct pexpr **ep2,
+			       struct cfdata *data)
+{
+	if (!e1 || !e2)
+		return;
+
+	switch (e1->type) {
+	case PE_AND:
+	case PE_OR:
+		__pexpr_eliminate_eq(e1->type, ep1, ep2, data);
+	default:
+		break;
+	}
+	if (e1->type != e2->type)
+		switch (e2->type) {
+		case PE_AND:
+		case PE_OR:
+			__pexpr_eliminate_eq(e2->type, ep1, ep2, data);
+		default:
+			break;
+		}
+	pexpr_eliminate_yn(e1, data);
+	pexpr_eliminate_yn(e2, data);
+}
+#undef e1
+#undef e2
+
+/*
+ * check whether 2 pexpr are equal
+ */
+bool pexpr_test_eq(struct pexpr *e1, struct pexpr *e2, struct cfdata *data)
+{
+	bool res;
+	int old_count;
+
+	if (!e1 || !e2)
+		return false;
+
+	if (e1->type != e2->type)
+		return false;
+
+	switch (e1->type) {
+	case PE_SYMBOL:
+		return e1->left.fexpr->satval == e2->left.fexpr->satval;
+	case PE_AND:
+	case PE_OR:
+		e1 = pexpr_deep_copy(e1);
+		e2 = pexpr_deep_copy(e2);
+		old_count = trans_count;
+		pexpr_eliminate_eq(&e1, &e2, data);
+		res = (e1->type == PE_SYMBOL && e2->type == PE_SYMBOL &&
+			e1->left.fexpr->satval == e2->left.fexpr->satval);
+		pexpr_put(e1);
+		pexpr_put(e2);
+		trans_count = old_count;
+		return res;
+	case PE_NOT:
+		return pexpr_test_eq(e1->left.pexpr, e2->left.pexpr, data);
+	}
+
+	return false;
+}
+
+/*
+ * print a pexpr
+ */
+static void pexpr_print_util(struct pexpr *e, int prevtoken)
+{
+	if (!e)
+		return;
+
+	switch (e->type) {
+	case PE_SYMBOL:
+		printf("%s", str_get(&e->left.fexpr->name));
+		break;
+	case PE_AND:
+		if (prevtoken != PE_AND && prevtoken != -1)
+			printf("(");
+		pexpr_print_util(e->left.pexpr, PE_AND);
+		printf(" && ");
+		pexpr_print_util(e->right.pexpr, PE_AND);
+		if (prevtoken != PE_AND && prevtoken != -1)
+			printf(")");
+		break;
+	case PE_OR:
+		if (prevtoken != PE_OR && prevtoken != -1)
+			printf("(");
+		pexpr_print_util(e->left.pexpr, PE_OR);
+		printf(" || ");
+		pexpr_print_util(e->right.pexpr, PE_OR);
+		if (prevtoken != PE_OR && prevtoken != -1)
+			printf(")");
+		break;
+	case PE_NOT:
+		printf("!");
+		pexpr_print_util(e->left.pexpr, PE_NOT);
+		break;
+	}
+}
+void pexpr_print(char *tag, struct pexpr *e, int prevtoken)
+{
+	printf("%s: ", tag);
+	pexpr_print_util(e, prevtoken);
+	printf("\n");
+}
+
+/*
+ * convert a fexpr to a pexpr
+ */
+struct pexpr *pexpr_alloc_symbol(struct fexpr *fe)
+{
+	struct pexpr *pe = xmalloc(sizeof(*pe));
+
+	pexpr_construct_sym(pe, fe, 1);
+	return pe;
+}
+
+void pexpr_construct_or(struct pexpr *e, struct pexpr *left,
+			     struct pexpr *right, unsigned int ref_count)
+{
+	e->type = PE_OR;
+	e->left.pexpr = left;
+	e->right.pexpr = right;
+	e->ref_count = ref_count;
+}
+
+void pexpr_construct_and(struct pexpr *e, struct pexpr *left,
+			     struct pexpr *right, unsigned int ref_count)
+{
+	e->type = PE_AND;
+	e->left.pexpr = left;
+	e->right.pexpr = right;
+	e->ref_count = ref_count;
+}
+
+void pexpr_construct_not(struct pexpr *e, struct pexpr *left,
+			  unsigned int ref_count)
+{
+	e->type = PE_NOT;
+	e->left.pexpr = left;
+	e->right.pexpr = NULL;
+	e->ref_count = ref_count;
+}
+
+void pexpr_construct_sym(struct pexpr *e, struct fexpr *left,
+			  unsigned int ref_count)
+{
+	e->type = PE_SYMBOL;
+	e->left.fexpr = left;
+	e->right.pexpr = NULL;
+	e->ref_count = ref_count;
+}
scripts/kconfig/cf_expr.h new file +181 -0

181 lines not on this page · raw message

Signature · 1 line
2.39.5
#8 lore raw

PATCH v7 6/11 kconfig: Add files for fix generation

In reply to Ole Schuerks

Add files to implement the algorithm that is used to resolve conflicts, i.e., find sets of symbols whose values need to be changed in order to be able to make the desired changes of symbol values.

---
 scripts/kconfig/cf_fixgen.c | 1136 +++++++++++++++++++++++++++++++++++
 scripts/kconfig/cf_fixgen.h |   21 +
 2 files changed, 1157 insertions(+)
 create mode 100644 scripts/kconfig/cf_fixgen.c
 create mode 100644 scripts/kconfig/cf_fixgen.h
scripts/kconfig/cf_fixgen.c new file +1136 -0
new file mode 100644
index 000000000000..88a6a464cccb
@@ -0,0 +1,1136 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * Copyright (C) 2023 Patrick Franz <[email protected]>
+ */
+
+#define _GNU_SOURCE
+#include <assert.h>
+#include <locale.h>
+#include <stdarg.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include <unistd.h>
+
+#include <xalloc.h>
+
+#include "lkc.h"
+#include "cf_defs.h"
+#include "cf_expr.h"
+#include "list.h"
+#include "list_types.h"
+#include "cf_fixgen.h"
+#include "internal.h"
+#include "cf_utils.h"
+#include "cf_defs.h"
+
+#define MAX_DIAGNOSES 3
+#define MAX_SECONDS 120
+#define PRINT_UNSAT_CORE true
+#define PRINT_DIAGNOSES false
+#define PRINT_DIAGNOSIS_FOUND true
+#define MINIMISE_DIAGNOSES false
+#define MINIMISE_UNSAT_CORE true
+
+static struct sfl_list *diagnoses_symbol;
+
+static struct fexl_list *generate_diagnoses(PicoSAT *pico, struct cfdata *data);
+
+static void add_fexpr_to_constraint_set(struct fexpr_list *C,
+					struct cfdata *data);
+static void set_assumptions(PicoSAT *pico, struct fexpr_list *c,
+			    struct cfdata *data);
+static void fexpr_add_assumption(PicoSAT *pico, struct fexpr *e, int satval);
+static struct fexpr_list *get_unsat_core_soft(PicoSAT *pico,
+					      struct cfdata *data);
+static void minimise_unsat_core(PicoSAT *pico, struct fexpr_list *C,
+				struct cfdata *data);
+
+static struct fexpr_list *get_difference(struct fexpr_list *C,
+					 struct fexpr_list *E0);
+static bool has_intersection(struct fexpr_list *e, struct fexpr_list *X);
+static struct fexpr_list *fexpr_list_union(struct fexpr_list *A,
+					   struct fexpr_list *B);
+static struct fexl_list *fexl_list_union(struct fexl_list *A,
+					 struct fexl_list *B);
+static bool is_subset_of(struct fexpr_list *A, struct fexpr_list *B);
+static void print_unsat_core(struct fexpr_list *list);
+static bool diagnosis_contains_fexpr(struct fexpr_list *diagnosis,
+				     struct fexpr *e);
+static bool diagnosis_contains_symbol(struct sfix_list *diagnosis,
+				      struct symbol *sym);
+
+static void print_diagnoses(struct fexl_list *diag);
+static void print_diagnoses_symbol(struct sfl_list *diag_sym);
+
+static struct sfl_list *convert_diagnoses(struct fexl_list *diagnoses,
+					  struct cfdata *data);
+static struct sfix_list *convert_diagnosis(struct fexpr_list *diagnosis,
+					   struct cfdata *data);
+static struct symbol_fix *symbol_fix_create(struct fexpr *e,
+					    enum symbolfix_type type,
+					    struct fexpr_list *diagnosis);
+static struct sfl_list *minimise_diagnoses(PicoSAT *pico,
+					   struct fexl_list *diagnoses,
+					   struct cfdata *data);
+
+static tristate calculate_new_tri_val(struct fexpr *e,
+				      struct fexpr_list *diagnosis);
+static const char *calculate_new_string_value(struct fexpr *e,
+					      struct fexpr_list *diagnosis);
+static bool fexpr_list_has_length_1(struct fexpr_list *list);
+
+/* count assumptions, only used for debugging */
+static unsigned int nr_of_assumptions = 0, nr_of_assumptions_true;
+
+/* -------------------------------------- */
+
+struct sfl_list *fixgen_run(PicoSAT *pico, struct cfdata *data)
+{
+	clock_t start, end;
+	double time;
+	struct fexl_list *diagnoses;
+	struct fexl_node *node;
+
+	printd("Starting fix generation...\n");
+	printd("Generating diagnoses...");
+
+	/* generate the diagnoses */
+	start = clock();
+	diagnoses = generate_diagnoses(pico, data);
+	end = clock();
+
+	time = ((double) (end - start)) / CLOCKS_PER_SEC;
+	printd("Generating diagnoses...done. (%.6f secs.)\n", time);
+
+	if (PRINT_DIAGNOSES) {
+		printd("Diagnoses (only for debugging):\n");
+		print_diagnoses(diagnoses);
+		printd("\n");
+	}
+
+	/* convert diagnoses of fexpr to diagnoses of symbols */
+	if (MINIMISE_DIAGNOSES)
+		diagnoses_symbol = minimise_diagnoses(pico, diagnoses, data);
+	else
+		diagnoses_symbol = convert_diagnoses(diagnoses, data);
+
+	printd("\n");
+
+	CF_LIST_FOR_EACH(node, diagnoses, fexl)
+		CF_LIST_FREE(node->elem, fexpr);
+	CF_LIST_FREE(diagnoses, fexl);
+
+	return diagnoses_symbol;
+}
+
+/*
+ * generate the diagnoses
+ */
+static struct fexl_list *generate_diagnoses(PicoSAT *pico, struct cfdata *data)
+{
+	CF_DEF_LIST(C, fexpr);
+	CF_DEF_LIST(empty_diagnosis, fexpr);
+	CF_DEF_LIST(E, fexl);
+	CF_DEF_LIST(R, fexl);
+	size_t num_diagnoses = 0;
+	struct fexpr_list *X, *e, *E2;
+	struct fexl_list *E_R_Union;
+	clock_t start_t, end_t;
+	double time_t;
+
+	/* create constraint set C */
+	add_fexpr_to_constraint_set(C, data);
+
+	if (PRINT_UNSAT_CORE)
+		printd("\n");
+
+	/* init E with an empty diagnosis */
+	CF_PUSH_BACK(E, empty_diagnosis, fexl);
+
+	/* start the clock */
+	start_t = clock();
+
+	while (!list_empty(&E->list)) {
+		/* get random diagnosis */
+		struct fexl_node *E0_node =
+			list_first_entry(&E->list, struct fexl_node, node);
+		struct fexpr_list *E0 = E0_node->elem;
+
+		/* calculate C\E0 */
+		struct fexpr_list *c = get_difference(C, E0);
+
+		struct fexl_node *node, *next;
+		int res;
+
+		/* set assumptions */
+		nr_of_assumptions = 0;
+		nr_of_assumptions_true = 0;
+		set_assumptions(pico, c, data);
+		CF_LIST_FREE(c, fexpr);
+
+		res = picosat_sat(pico, -1);
+
+		if (res == PICOSAT_SATISFIABLE) {
+			if (PRINT_DIAGNOSIS_FOUND && CFDEBUG)
+				fexpr_list_print("DIAGNOSIS FOUND", E0);
+
+			list_del(&E0_node->node);
+			if (!list_empty(&E0->list)) {
+				CF_PUSH_BACK(R, E0, fexl);
+				++num_diagnoses;
+			} else
+				CF_LIST_FREE(E0, fexpr);
+
+			if (num_diagnoses >= MAX_DIAGNOSES)
+				goto DIAGNOSES_FOUND;
+
+			continue;
+
+		} else if (res == PICOSAT_UNSATISFIABLE) {
+
+		} else if (res == PICOSAT_UNKNOWN) {
+			printd("UNKNOWN\n");
+		} else {
+			perror("Doh.");
+		}
+
+		/* check elapsed time */
+		end_t = clock();
+		time_t = ((double) (end_t - start_t)) / CLOCKS_PER_SEC;
+		if (time_t > (double) MAX_SECONDS)
+			goto DIAGNOSES_FOUND;
+
+		/* abort and return results if cancelled by user */
+		if (stop_fixgen) {
+			stop_fixgen = false;
+			goto DIAGNOSES_FOUND;
+		}
+
+		/* get unsat core from SAT solver */
+		X = get_unsat_core_soft(pico, data);
+
+		/* minimise the unsat core */
+		if (MINIMISE_UNSAT_CORE)
+			minimise_unsat_core(pico, X, data);
+
+		if (PRINT_UNSAT_CORE)
+			print_unsat_core(X);
+
+		list_for_each_entry_safe(node, next, &E->list, node) {
+			struct fexpr_node *fnode;
+
+			/* get partial diagnosis */
+			e = node->elem;
+
+			/* check, if there is an intersection between e and X
+			 * if there is, go to the next partial diagnosis
+			 */
+			if (has_intersection(e, X))
+				continue;
+
+			/* for each fexpr in the core */
+			CF_LIST_FOR_EACH(fnode, X, fexpr) {
+				struct fexpr *x = fnode->elem;
+				bool E2_subset_of_E1;
+				struct fexl_node *lnode;
+				CF_DEF_LIST(E_without_e, fexl);
+				CF_DEF_LIST(x_set, fexpr);
+				struct fexpr_list *E1;
+
+				/* create {x} */
+				CF_PUSH_BACK(x_set, x, fexpr);
+
+				/* create E' = e U {x} */
+				E1 = fexpr_list_union(e, x_set);
+
+				/* create (E\e) U R */
+				CF_LIST_FOR_EACH(lnode, E, fexl) {
+					if (lnode->elem == e)
+						continue;
+					CF_PUSH_BACK(E_without_e,
+							lnode->elem, fexl);
+				}
+				E_R_Union = fexl_list_union(E_without_e, R);
+
+				E2_subset_of_E1 = false;
+
+				/* E" in (E\e) U R */
+				CF_LIST_FOR_EACH(lnode, E_R_Union, fexl) {
+					E2 = lnode->elem;
+
+					/* E" subset of E' ? */
+					if (is_subset_of(E2, E1)) {
+						E2_subset_of_E1 = true;
+						break;
+					}
+				}
+
+				CF_LIST_FREE(E_without_e, fexl);
+				CF_LIST_FREE(E_R_Union, fexl);
+				CF_LIST_FREE(x_set, fexpr);
+
+				/* there exists no E" that is a subset of E' */
+				if (!E2_subset_of_E1)
+					CF_PUSH_BACK(E, E1, fexl);
+				else
+					CF_LIST_FREE(E1, fexpr);
+			}
+
+			CF_LIST_FREE(e, fexpr);
+
+			list_del(&node->node);
+		}
+		CF_LIST_FREE(X, fexpr);
+	}
+
+	struct fexl_node *node;
+DIAGNOSES_FOUND:
+	CF_LIST_FREE(C, fexpr);
+	CF_LIST_FOR_EACH(node, E, fexl)
+		CF_LIST_FREE(node->elem, fexpr);
+	CF_LIST_FREE(E, fexl);
+
+	return R;
+}
+
+/*
+ * add the fexpr to the constraint set C
+ */
+static void add_fexpr_to_constraint_set(struct fexpr_list *C,
+					struct cfdata *data)
+{
+	struct symbol *sym;
+
+	for_all_symbols(sym) {
+		/* must be a proper symbol */
+		if (sym->type == S_UNKNOWN)
+			continue;
+
+		/*
+		 * don't need the conflict symbols they are handled separately
+		 */
+		if (sym_is_sdv(data->sdv_symbols, sym))
+			continue;
+
+		/* must have a prompt and a name */
+		if (!sym->name || !sym_has_prompt(sym))
+			continue;
+
+		if (sym->type == S_BOOLEAN)
+			CF_PUSH_BACK(C, sym->fexpr_y, fexpr);
+		else if (sym->type == S_TRISTATE) {
+			CF_PUSH_BACK(C, sym->fexpr_y, fexpr);
+			CF_PUSH_BACK(C, sym->fexpr_m, fexpr);
+		} else if (sym->type == S_INT || sym->type == S_HEX ||
+			   sym->type == S_STRING) {
+			struct fexpr_node *node;
+
+			CF_LIST_FOR_EACH(node, sym->nb_vals, fexpr)
+				CF_PUSH_BACK(C, node->elem, fexpr);
+		} else {
+			perror("Error adding variables to constraint set C.");
+		}
+	}
+}
+
+/*
+ * check whether the fexpr symbolises the no-value-set fexpr for a non-boolean
+ * symbol
+ */
+static bool fexpr_is_novalue(struct fexpr *e)
+{
+	if (!sym_is_nonboolean(e->sym))
+		return false;
+
+	return e ==
+	       list_first_entry(&e->sym->nb_vals->list, struct fexpr_node, node)
+		       ->elem;
+}
+
+static void set_assumptions_sdv(PicoSAT *pico, struct sdv_list *arr)
+{
+	struct symbol_dvalue *sdv;
+	struct sdv_node *node;
+	struct symbol *sym;
+
+	CF_LIST_FOR_EACH(node, arr, sdv) {
+		int lit_y;
+
+		sdv = node->elem;
+		sym = sdv->sym;
+
+		lit_y = sym->fexpr_y->satval;
+
+		if (sym->type == S_BOOLEAN) {
+			switch (sdv->tri) {
+			case yes:
+				picosat_assume(pico, lit_y);
+				sym->fexpr_y->assumption = true;
+				nr_of_assumptions_true++;
+				break;
+			case no:
+				picosat_assume(pico, -lit_y);
+				sym->fexpr_y->assumption = false;
+				break;
+			case mod:
+				perror("Should not happen.\n");
+			}
+			nr_of_assumptions++;
+		} else if (sym->type == S_TRISTATE) {
+			int lit_m = sym->fexpr_m->satval;
+
+			switch (sdv->tri) {
+			case yes:
+				picosat_assume(pico, lit_y);
+				sym->fexpr_y->assumption = true;
+				picosat_assume(pico, -lit_m);
+				sym->fexpr_m->assumption = false;
+				nr_of_assumptions_true++;
+				break;
+			case mod:
+				picosat_assume(pico, -lit_y);
+				sym->fexpr_y->assumption = false;
+				picosat_assume(pico, lit_m);
+				sym->fexpr_m->assumption = true;
+				nr_of_assumptions_true++;
+				break;
+			case no:
+				picosat_assume(pico, -lit_y);
+				sym->fexpr_y->assumption = false;
+				picosat_assume(pico, -lit_m);
+				sym->fexpr_y->assumption = false;
+			}
+			nr_of_assumptions += 2;
+		}
+	}
+}
+
+/*
+ * set the assumptions for the next run of Picosat
+ */
+static void set_assumptions(PicoSAT *pico, struct fexpr_list *c,
+			    struct cfdata *data)
+{
+	struct fexpr_node *node;
+
+	CF_LIST_FOR_EACH(node, c, fexpr)
+		fexpr_add_assumption(pico, node->elem, node->elem->satval);
+
+	/* set assumptions for the conflict-symbols */
+	set_assumptions_sdv(pico, data->sdv_symbols);
+}
+
+/*
+ * set the assumtption for a fexpr for the next run of Picosat
+ */
+static void fexpr_add_assumption(PicoSAT *pico, struct fexpr *e, int satval)
+{
+	struct symbol *sym = e->sym;
+
+	if (sym->type == S_BOOLEAN) {
+		int tri_val = sym_get_tristate_value(sym);
+
+		if (tri_val == yes) {
+			picosat_assume(pico, satval);
+			e->assumption = true;
+			nr_of_assumptions_true++;
+		} else {
+			picosat_assume(pico, -satval);
+			e->assumption = false;
+		}
+		nr_of_assumptions++;
+	}
+
+	if (sym->type == S_TRISTATE) {
+		int tri_val = sym_get_tristate_value(sym);
+
+		if (e->tri == yes) {
+			if (tri_val == yes) {
+				picosat_assume(pico, satval);
+				e->assumption = true;
+				nr_of_assumptions_true++;
+			} else {
+				picosat_assume(pico, -satval);
+				e->assumption = false;
+			}
+		} else if (e->tri == mod) {
+			if (tri_val == mod) {
+				picosat_assume(pico, satval);
+				e->assumption = true;
+				nr_of_assumptions_true++;
+			} else {
+				picosat_assume(pico, -satval);
+				e->assumption = false;
+			}
+		}
+		nr_of_assumptions++;
+	}
+
+	if (sym->type == S_INT || sym->type == S_HEX || sym->type == S_STRING) {
+
+		char *string_val = (char *) sym_get_string_value(sym);
+
+		if (sym->type == S_STRING && !strcmp(string_val, ""))
+			return;
+
+		/* check, if e symbolises the no-value-set fexpr */
+		if (fexpr_is_novalue(e)) {
+			if (!sym_nonbool_has_value_set(sym)) {
+				picosat_assume(pico, satval);
+				e->assumption = true;
+				nr_of_assumptions_true++;
+			} else {
+				picosat_assume(pico, -satval);
+				e->assumption = false;
+			}
+		}
+		/* check whena string-symbol has value "" */
+		else if (sym->type == S_STRING && !strcmp(string_val, "")) {
+			if (sym_nonbool_has_value_set(sym)) {
+				picosat_assume(pico, satval);
+				e->assumption = true;
+				nr_of_assumptions_true++;
+			} else {
+				picosat_assume(pico, -satval);
+				e->assumption = false;
+			}
+		} else {
+			if (!strcmp(str_get(&e->nb_val), string_val) &&
+					sym_nonbool_has_value_set(sym)) {
+				picosat_assume(pico, satval);
+				e->assumption = true;
+				nr_of_assumptions_true++;
+			} else {
+				picosat_assume(pico, -satval);
+				e->assumption = false;
+			}
+		}
+		nr_of_assumptions++;
+	}
+}
+
+/*
+ * get the unsatisfiable soft constraints from the last run of Picosat
+ */
+static struct fexpr_list *get_unsat_core_soft(PicoSAT *pico,
+					      struct cfdata *data)
+{
+	CF_DEF_LIST(ret, fexpr);
+	struct fexpr *e;
+
+	int lit;
+	const int *i = picosat_failed_assumptions(pico);
+
+	lit = abs(*i++);
+
+	while (lit != 0) {
+		e = data->satmap[lit];
+
+		if (!sym_is_sdv(data->sdv_symbols, e->sym))
+			CF_PUSH_BACK(ret, e, fexpr);
+
+		lit = abs(*i++);
+	}
+
+	return ret;
+}
+
+/*
+ * minimise the unsat core C
+ */
+static void minimise_unsat_core(PicoSAT *pico, struct fexpr_list *C,
+				struct cfdata *data)
+{
+	struct fexpr_node *node, *tmp;
+
+	/* no need to check further */
+	if (fexpr_list_has_length_1(C))
+		return;
+
+	list_for_each_entry_safe(node, tmp, &C->list, node) {
+		CF_DEF_LIST(c_set, fexpr);
+		struct fexpr_list *t;
+		int res;
+
+		if (fexpr_list_has_length_1(C))
+			return;
+
+		/* create C\c */
+		CF_PUSH_BACK(c_set, node->elem, fexpr);
+		t = get_difference(C, c_set);
+
+		/* invoke PicoSAT */
+		set_assumptions(pico, t, data);
+
+		res = picosat_sat(pico, -1);
+
+		if (res == PICOSAT_UNSATISFIABLE) {
+			list_del(&node->node);
+			free(node);
+		}
+
+		CF_LIST_FREE(c_set, fexpr);
+		CF_LIST_FREE(t, fexpr);
+	}
+}
+
+
+/*
+ * Calculate C\E0
+ */
+static struct fexpr_list *get_difference(struct fexpr_list *C,
+					 struct fexpr_list *E0)
+{
+	CF_DEF_LIST(ret, fexpr);
+	struct fexpr_node *node1, *node2;
+
+	CF_LIST_FOR_EACH(node1, C, fexpr) {
+		bool found = false;
+
+		CF_LIST_FOR_EACH(node2, E0, fexpr) {
+			if (node1->elem->satval == node2->elem->satval) {
+				found = true;
+				break;
+			}
+		}
+		if (!found)
+			CF_PUSH_BACK(ret, node1->elem, fexpr);
+	}
+
+	return ret;
+}
+
+/*
+ * check, if there is an intersection between e and X
+ */
+static bool has_intersection(struct fexpr_list *e, struct fexpr_list *X)
+{
+	struct fexpr_node *node1, *node2;
+
+	CF_LIST_FOR_EACH(node1, e, fexpr)
+		CF_LIST_FOR_EACH(node2, X, fexpr)
+			if (node1->elem->satval == node2->elem->satval)
+				return true;
+
+	return false;
+}
+
+/*
+ * get the union of 2 fexpr_list
+ */
+static struct fexpr_list *fexpr_list_union(struct fexpr_list *A,
+					   struct fexpr_list *B)
+{
+	struct fexpr_list *ret = CF_LIST_COPY(A, fexpr);
+	struct fexpr_node *node1, *node2;
+	bool found;
+
+	CF_LIST_FOR_EACH(node2, B, fexpr) {
+		found = false;
+		CF_LIST_FOR_EACH(node1, A, fexpr) {
+			if (node2->elem->satval == node1->elem->satval) {
+				found = true;
+				break;
+			}
+		}
+		if (!found)
+			CF_PUSH_BACK(ret, node2->elem, fexpr);
+	}
+
+	return ret;
+}
+
+/*
+ * get the union of 2 fexl_list
+ */
+static struct fexl_list *fexl_list_union(struct fexl_list *A,
+					 struct fexl_list *B)
+{
+	struct fexl_list *ret = CF_LIST_COPY(A, fexl);
+	struct fexl_node *node1, *node2;
+	bool found;
+
+	CF_LIST_FOR_EACH(node2, B, fexl) {
+		found = false;
+		CF_LIST_FOR_EACH(node1, A, fexl) {
+			if (node2->elem == node1->elem) {
+				found = true;
+				break;
+			}
+		}
+		if (!found)
+			CF_PUSH_BACK(ret, node2->elem, fexl);
+	}
+
+	return ret;
+}
+
+/*
+ * check, whether A is a subset of B
+ */
+static bool is_subset_of(struct fexpr_list *A, struct fexpr_list *B)
+{
+	struct fexpr_node *node1, *node2;
+	bool found;
+
+	CF_LIST_FOR_EACH(node1, A, fexpr) {
+		found = false;
+		CF_LIST_FOR_EACH(node2, B, fexpr) {
+			if (node1->elem->satval == node2->elem->satval) {
+				found = true;
+				break;
+			}
+		}
+		if (!found)
+			return false;
+	}
+
+	return true;
+}
+
+/*
+ * print an unsat core
+ */
+static void print_unsat_core(struct fexpr_list *list)
+{
+	struct fexpr_node *node;
+	bool first = true;
+
+	printd("Unsat core: [");
+
+	CF_LIST_FOR_EACH(node, list, fexpr) {
+		if (first)
+			first = false;
+		else
+			printd(", ");
+		printd("%s", str_get(&node->elem->name));
+		printd(" <%s>", node->elem->assumption == true ? "T" : "F");
+	}
+
+	printd("]\n");
+}
+
+
+/*
+ * check if a diagnosis contains a fexpr
+ */
+static bool diagnosis_contains_fexpr(struct fexpr_list *diagnosis,
+				     struct fexpr *e)
+{
+	struct fexpr_node *node;
+
+	CF_LIST_FOR_EACH(node, diagnosis, fexpr)
+		if (node->elem->satval == e->satval)
+			return true;
+
+	return false;
+}
+
+/*
+ * check if a diagnosis contains a symbol
+ */
+static bool diagnosis_contains_symbol(struct sfix_list *diagnosis,
+				      struct symbol *sym)
+{
+	struct sfix_node *node;
+
+	CF_LIST_FOR_EACH(node, diagnosis, sfix)
+		if (sym == node->elem->sym)
+			return true;
+
+	return false;
+}
+
+/*
+ * print the diagnoses of type fexpr_list
+ */
+static void print_diagnoses(struct fexl_list *diag)
+{
+	struct fexl_node *lnode;
+	unsigned int i = 1;
+
+	CF_LIST_FOR_EACH(lnode, diag, fexl) {
+		struct fexpr_node *node;
+		bool first = true;
+
+		printd("%d: [", i++);
+		CF_LIST_FOR_EACH(node, lnode->elem, fexpr) {
+			char *new_val = node->elem->assumption ? "false" :
+								 "true";
+
+			if (first)
+				first = false;
+			else
+				printd(", ");
+			printd("%s => %s", str_get(&node->elem->name), new_val);
+		}
+		printd("]\n");
+	}
+}
+
+/*
+ * print a single diagnosis of type symbol_fix
+ */
+void print_diagnosis_symbol(struct sfix_list *diag_sym)
+{
+	struct symbol_fix *fix;
+	struct sfix_node *node;
+
+	printd("[");
+
+	CF_LIST_FOR_EACH(node, diag_sym, sfix) {
+		fix = node->elem;
+
+		if (fix->type == SF_BOOLEAN)
+			printd("%s => %s", fix->sym->name,
+			       tristate_get_char(fix->tri));
+		else if (fix->type == SF_NONBOOLEAN)
+			printd("%s => %s", fix->sym->name,
+			       str_get(&fix->nb_val));
+		else
+			perror("NB not yet implemented.");
+
+		if (node->node.next != &diag_sym->list)
+			printd(", ");
+	}
+	printd("]\n");
+}
+
+/*
+ * print the diagnoses of type symbol_fix
+ */
+static void print_diagnoses_symbol(struct sfl_list *diag_sym)
+{
+	struct sfl_node *arr;
+	unsigned int i = 1;
+
+	CF_LIST_FOR_EACH(arr, diag_sym, sfl) {
+		printd("%d: ", i++);
+		print_diagnosis_symbol(arr->elem);
+	}
+}
+
+/*
+ * convert a single diagnosis of fexpr into a diagnosis of symbols
+ */
+static struct sfix_list *convert_diagnosis(struct fexpr_list *diagnosis,
+					   struct cfdata *data)
+{
+	CF_DEF_LIST(diagnosis_symbol, sfix);
+	struct fexpr *e;
+	struct symbol_fix *fix;
+	struct symbol_dvalue *sdv;
+	struct sdv_node *snode;
+	struct fexpr_node *fnode;
+
+	/* set the values for the conflict symbols */
+	CF_LIST_FOR_EACH(snode, data->sdv_symbols, sdv) {
+		sdv = snode->elem;
+		fix = xmalloc(sizeof(*fix));
+		fix->sym = sdv->sym;
+		fix->type = SF_BOOLEAN;
+		fix->tri = sdv->tri;
+		CF_PUSH_BACK(diagnosis_symbol, fix, sfix);
+	}
+
+	CF_LIST_FOR_EACH(fnode, diagnosis, fexpr) {
+		enum symbolfix_type type;
+
+		e = fnode->elem;
+
+		/* diagnosis already contains symbol, so continue */
+		if (diagnosis_contains_symbol(diagnosis_symbol, e->sym))
+			continue;
+
+		if (sym_is_boolean(e->sym))
+			type = SF_BOOLEAN;
+		else if (sym_is_nonboolean(e->sym))
+			type = SF_NONBOOLEAN;
+		else
+			type = SF_DISALLOWED;
+		fix = symbol_fix_create(e, type, diagnosis);
+
+		CF_PUSH_BACK(diagnosis_symbol, fix, sfix);
+	}
+
+	return diagnosis_symbol;
+}
+
+/*
+ * convert the diagnoses of fexpr into diagnoses of symbols
+ * it is easier to handle symbols when applying fixes
+ */
+static struct sfl_list *convert_diagnoses(struct fexl_list *diag_arr,
+					  struct cfdata *data)
+{
+	struct fexl_node *lnode;
+
+	diagnoses_symbol = CF_LIST_INIT(sfl);
+
+	CF_LIST_FOR_EACH(lnode, diag_arr, fexl) {
+		struct sfix_list *fix = convert_diagnosis(lnode->elem, data);
+
+		CF_PUSH_BACK(diagnoses_symbol, fix, sfl);
+	}
+
+	return diagnoses_symbol;
+}
+
+/*
+ * create a symbol_fix given a fexpr
+ */
+static struct symbol_fix *symbol_fix_create(struct fexpr *e,
+					    enum symbolfix_type type,
+					    struct fexpr_list *diagnosis)
+{
+	struct symbol_fix *fix = malloc(sizeof(struct symbol_fix));
+
+	fix->sym = e->sym;
+	fix->type = type;
+
+	switch (type) {
+	case SF_BOOLEAN:
+		fix->tri = calculate_new_tri_val(e, diagnosis);
+		break;
+	case SF_NONBOOLEAN:
+		fix->nb_val = str_new();
+		str_append(&fix->nb_val,
+			   calculate_new_string_value(e, diagnosis));
+		break;
+	default:
+		perror("Illegal symbolfix_type.\n");
+	}
+
+	return fix;
+}
+
+/*
+ * remove symbols from the diagnosis, which will be set automatically:
+ * 1. symbol gets selected
+ * 2. choice symbol gets enabled/disabled automatically
+ * 3. symbol uses a default value
+ */
+static struct sfl_list *minimise_diagnoses(PicoSAT *pico,
+					   struct fexl_list *diagnoses,
+					   struct cfdata *data)
+{
+	clock_t start, end;
+	double time;
+	struct fexpr_list *d;
+	struct sfix_list *diagnosis_symbol;
+	CF_DEF_LIST(diagnoses_symbol, sfl);
+	struct fexpr *e;
+	int satval, deref = 0;
+	struct symbol_fix *fix;
+	struct fexl_node *flnode;
+	CF_DEF_LIST(C, fexpr);
+
+	printd("Minimising diagnoses...");
+
+	start = clock();
+
+	/* create soft constraint set C */
+	add_fexpr_to_constraint_set(C, data);
+
+	CF_LIST_FOR_EACH(flnode, diagnoses, fexl) {
+		struct fexpr_node *fnode;
+		struct sfix_node *snode, *snext;
+		struct fexpr_list *C_without_d;
+		int res;
+
+		d = flnode->elem;
+
+		/*
+		 * set assumptions for those symbols that don't need to be
+		 * changed
+		 */
+		C_without_d = get_difference(C, d);
+		set_assumptions(pico, C_without_d, data);
+		CF_LIST_FREE(C_without_d, fexpr);
+		CF_LIST_FREE(C, fexpr);
+
+
+		/* flip the assumptions from the diagnosis */
+		CF_LIST_FOR_EACH(fnode, d, fexpr) {
+			e = fnode->elem;
+			satval = e->assumption ? -(e->satval) : e->satval;
+			picosat_assume(pico, satval);
+		}
+
+		res = picosat_sat(pico, -1);
+		if (res != PICOSAT_SATISFIABLE)
+			perror("Diagnosis not satisfiable (minimise).");
+
+		diagnosis_symbol = convert_diagnosis(d, data);
+
+		/* check if symbol gets selected */
+		list_for_each_entry_safe(snode, snext, &diagnosis_symbol->list,
+					 node) {
+			fix = snode->elem;
+
+			/* symbol is never selected, continue */
+			if (!fix->sym->fexpr_sel_y)
+				continue;
+
+			/* check, whether the symbol was selected anyway */
+			if (fix->sym->type == S_BOOLEAN && fix->tri == yes)
+				deref = picosat_deref(
+					pico, fix->sym->fexpr_sel_y->satval);
+			else if (fix->sym->type == S_TRISTATE &&
+				 fix->tri == yes)
+				deref = picosat_deref(
+					pico, fix->sym->fexpr_sel_y->satval);
+			else if (fix->sym->type == S_TRISTATE &&
+				 fix->tri == mod)
+				deref = picosat_deref(
+					pico, fix->sym->fexpr_sel_m->satval);
+
+			if (deref == 1)
+				list_del(&snode->node);
+			else
+				deref = 0;
+		}
+		CF_PUSH_BACK(diagnoses_symbol, diagnosis_symbol, sfl);
+	}
+
+	end = clock();
+	time = ((double) (end - start)) / CLOCKS_PER_SEC;
+
+	printd("done. (%.6f secs.)\n", time);
+
+	return diagnoses_symbol;
+}
+
+/*
+ * list the diagnoses and let user choose a diagnosis to be applied
+ */
+struct sfix_list *ask_user_choose_fix(struct sfl_list *diag)
+{
+	int choice;
+	struct sfl_node *ret;
+
+	printd("=== GENERATED DIAGNOSES ===\n");
+	printd("0: No changes wanted\n");
+	print_diagnoses_symbol(diag);
+
+	printd("\n> Choose option: ");
+	scanf("%d", &choice);
+
+	/* no changes wanted */
+	if (choice == 0)
+		return NULL;
+
+	ret = cflist_at_index(choice - 1, &diag->list, struct sfl_node, node);
+	return ret ? ret->elem : NULL;
+}
+
+
+/*
+ * calculate the new value for a boolean symbol given a diagnosis and an fexpr
+ */
+static tristate calculate_new_tri_val(struct fexpr *e,
+				      struct fexpr_list *diagnosis)
+{
+	assert(sym_is_boolean(e->sym));
+
+	/* return the opposite of the last assumption for booleans */
+	if (e->sym->type == S_BOOLEAN)
+		return e->assumption ? no : yes;
+
+	/* new values for tristate must be deduced from the diagnosis */
+	if (e->sym->type == S_TRISTATE) {
+		/* fexpr_y */
+		if (e->tri == yes) {
+			if (e->assumption == true)
+				/*
+				 * if diagnosis contains fexpr_m, fexpr_m was
+				 * false => new value is mod
+				 */
+				return diagnosis_contains_fexpr(
+					       diagnosis, e->sym->fexpr_m) ?
+					       mod :
+					       no;
+			else if (e->assumption == false)
+				/*
+				 * if fexpr_y is set to true, the new value
+				 * must be yes
+				 */
+				return yes;
+		}
+		/* fexpr_m */
+		if (e->tri == mod) {
+			if (e->assumption == true)
+				/*
+				 * if diagnosis contains fexpr_y, fexpr_y was
+				 * false => new value is yes
+				 */
+				return diagnosis_contains_fexpr(
+					       diagnosis, e->sym->fexpr_m) ?
+					       yes :
+					       no;
+			else if (e->assumption == false)
+				/*
+				 * if diagnosis contains fexpr_m, the new value
+				 * must be mod
+				 */
+				return mod;
+		}
+		perror("Should not get here.\n");
+	}
+
+	perror("Error calculating new tristate value.\n");
+	return no;
+}
+
+/*
+ * calculate the new value for a non-boolean symbol given a diagnosis and an
+ * fexpr
+ */
+static const char *calculate_new_string_value(struct fexpr *e,
+					      struct fexpr_list *diagnosis)
+{
+	struct fexpr_node *node;
+	struct fexpr *e2;
+
+	assert(sym_is_nonboolean(e->sym));
+
+	/* if assumption was false before, this is the new value because only 1
+	 * variable can be true
+	 */
+	if (e->assumption == false)
+		return str_get(&e->nb_val);
+
+	/* a diagnosis always contains 2 variables for the same non-boolean
+	 * symbol one is set to true, the other to false
+	 * otherwise you'd set 2 variables to true, which is not allowed
+	 */
+	CF_LIST_FOR_EACH(node, diagnosis, fexpr) {
+		e2 = node->elem;
+
+		/* not interested in other symbols or the same fexpr */
+		if (e->sym != e2->sym || e->satval == e2->satval)
+			continue;
+
+		return str_get(&e2->nb_val);
+	}
+
+	perror("Error calculating new string value.\n");
+	return "";
+}
+
+static bool fexpr_list_has_length_1(struct fexpr_list *list)
+{
+	struct fexpr_node *node;
+	bool first = true;
+
+	CF_LIST_FOR_EACH(node, list, fexpr) {
+		if (first)
+			first = false;
+		else
+			return false;
+	}
+	return true;
+}
scripts/kconfig/cf_fixgen.h new file +21 -0
new file mode 100644
index 000000000000..4526b5e4db06
@@ -0,0 +1,21 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * Copyright (C) 2023 Patrick Franz <[email protected]>
+ */
+
+#ifndef CF_FIXGEN_H
+#define CF_FIXGEN_H
+
+#include "picosat_functions.h"
+#include "cf_defs.h"
+
+/* initialize fixgen and return the diagnoses */
+struct sfl_list *fixgen_run(PicoSAT *pico, struct cfdata *data);
+
+/* ask user which fix to apply */
+struct sfix_list *ask_user_choose_fix(struct sfl_list *diag);
+
+/* print a single diagnosis of type symbol_fix */
+void print_diagnosis_symbol(struct sfix_list *diag_sym);
+
+#endif
Signature · 1 line
2.39.5
#9 lore raw

PATCH v7 7/11 kconfig: Add files with utility functions

In reply to Ole Schuerks

Add various helper functions used in the project.

---
 scripts/kconfig/cf_utils.c | 980 +++++++++++++++++++++++++++++++++++++
 scripts/kconfig/cf_utils.h | 136 +++++
 2 files changed, 1116 insertions(+)
 create mode 100644 scripts/kconfig/cf_utils.c
 create mode 100644 scripts/kconfig/cf_utils.h
scripts/kconfig/cf_utils.c new file +980 -0
new file mode 100644
index 000000000000..8dbcee451209
@@ -0,0 +1,980 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * Copyright (C) 2023 Patrick Franz <[email protected]>
+ */
+
+#define _GNU_SOURCE
+#include <assert.h>
+#include <locale.h>
+#include <stdarg.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include <unistd.h>
+#include <ctype.h>
+
+#include <xalloc.h>
+
+#include "internal.h"
+#include "picosat_functions.h"
+#include "cf_utils.h"
+#include "cf_expr.h"
+#include "list.h"
+
+#define SATMAP_INIT_SIZE 2
+
+static PicoSAT *pico;
+
+static void unfold_cnf_clause(struct pexpr *e);
+static void build_cnf_tseytin(struct pexpr *e, struct cfdata *data);
+
+static void build_cnf_tseytin_top_and(struct pexpr *e, struct cfdata *data);
+static void build_cnf_tseytin_top_or(struct pexpr *e, struct cfdata *data);
+
+static void build_cnf_tseytin_tmp(struct pexpr *e, struct fexpr *t,
+				  struct cfdata *data);
+static void build_cnf_tseytin_and(struct pexpr *e, struct fexpr *t,
+				  struct cfdata *data);
+static void build_cnf_tseytin_or(struct pexpr *e, struct fexpr *t,
+				 struct cfdata *data);
+static int pexpr_get_satval(struct pexpr *e);
+
+/*
+ * parse Kconfig-file and read .config
+ */
+void init_config(const char *Kconfig_file)
+{
+	conf_parse(Kconfig_file);
+	conf_read(NULL);
+}
+
+/*
+ * initialize satmap
+ */
+void init_data(struct cfdata *data)
+{
+	/* create hashtable with all fexpr */
+	data->satmap = xcalloc(SATMAP_INIT_SIZE, sizeof(typeof(*data->satmap)));
+	data->satmap_size = SATMAP_INIT_SIZE;
+
+	printd("done.\n");
+}
+
+/*
+ * create SAT-variables for all fexpr
+ */
+void create_sat_variables(struct cfdata *data)
+{
+	struct symbol *sym;
+
+	printd("Creating SAT-variables...");
+
+	for_all_symbols(sym) {
+		sym->constraints = CF_LIST_INIT(pexpr);
+		sym_create_fexpr(sym, data);
+	}
+
+	printd("done.\n");
+}
+
+/*
+ * create various constants
+ */
+void create_constants(struct cfdata *data)
+{
+	printd("Creating constants...");
+
+	/* create TRUE and FALSE constants */
+	data->constants->const_false =
+		fexpr_create(data->sat_variable_nr++, FE_FALSE, "False");
+	// const_false = fexpr_create(sat_variable_nr++, FE_FALSE, "False");
+	fexpr_add_to_satmap(data->constants->const_false, data);
+
+	data->constants->const_true =
+		fexpr_create(data->sat_variable_nr++, FE_TRUE, "True");
+	fexpr_add_to_satmap(data->constants->const_true, data);
+
+	/* add fexpr of constants to tristate constants */
+	symbol_yes.fexpr_y = data->constants->const_true;
+	symbol_yes.fexpr_m = data->constants->const_false;
+
+	symbol_mod.fexpr_y = data->constants->const_false;
+	symbol_mod.fexpr_m = data->constants->const_true;
+
+	symbol_no.fexpr_y = data->constants->const_false;
+	symbol_no.fexpr_m = data->constants->const_false;
+
+	/* create symbols yes/mod/no as fexpr */
+	data->constants->symbol_yes_fexpr = fexpr_create(0, FE_SYMBOL, "y");
+	data->constants->symbol_yes_fexpr->sym = &symbol_yes;
+	data->constants->symbol_yes_fexpr->tri = yes;
+
+	data->constants->symbol_mod_fexpr = fexpr_create(0, FE_SYMBOL, "m");
+	data->constants->symbol_mod_fexpr->sym = &symbol_mod;
+	data->constants->symbol_mod_fexpr->tri = mod;
+
+	data->constants->symbol_no_fexpr = fexpr_create(0, FE_SYMBOL, "n");
+	data->constants->symbol_no_fexpr->sym = &symbol_no;
+	data->constants->symbol_no_fexpr->tri = no;
+
+	printd("done.\n");
+}
+
+/*
+ * create a temporary SAT-variable
+ */
+struct fexpr *create_tmpsatvar(struct cfdata *data)
+{
+	char *name = get_tmp_var_as_char(data->tmp_variable_nr);
+	struct fexpr *t =
+		fexpr_create(data->sat_variable_nr++, FE_TMPSATVAR, name);
+
+	++data->tmp_variable_nr;
+	fexpr_add_to_satmap(t, data);
+
+	free(name);
+	return t;
+}
+
+/*
+ * return a temporary SAT variable as string
+ */
+char *get_tmp_var_as_char(int i)
+{
+	char *val = malloc(sizeof(char) * 18);
+
+	snprintf(val, 18, "T_%d", i);
+	return val;
+}
+
+/*
+ * return a tristate value as a char *
+ */
+char *tristate_get_char(tristate val)
+{
+	switch (val) {
+	case yes:
+		return "yes";
+	case mod:
+		return "mod";
+	case no:
+		return "no";
+	default:
+		return "";
+	}
+}
+
+/*
+ *check whether an expr can evaluate to mod
+ */
+bool expr_can_evaluate_to_mod(struct expr *e)
+{
+	if (!e)
+		return false;
+
+	switch (e->type) {
+	case E_SYMBOL:
+		return e->left.sym == &symbol_mod ||
+		       e->left.sym->type == S_TRISTATE;
+	case E_AND:
+	case E_OR:
+		return expr_can_evaluate_to_mod(e->left.expr) ||
+		       expr_can_evaluate_to_mod(e->right.expr);
+	case E_NOT:
+		return expr_can_evaluate_to_mod(e->left.expr);
+	default:
+		return false;
+	}
+}
+
+/*
+ * check whether an expr is a non-Boolean constant
+ */
+bool expr_is_nonbool_constant(struct expr *e)
+{
+	if (e->type != E_SYMBOL)
+		return false;
+	if (e->left.sym->type != S_UNKNOWN)
+		return false;
+
+	if (e->left.sym->flags & SYMBOL_CONST)
+		return true;
+
+	return string_is_number(e->left.sym->name) ||
+	       string_is_hex(e->left.sym->name);
+}
+
+/*
+ * check whether a symbol is a non-Boolean constant
+ */
+bool sym_is_nonbool_constant(struct symbol *sym)
+{
+	if (sym->type != S_UNKNOWN)
+		return false;
+
+	if (sym->flags & SYMBOL_CONST)
+		return true;
+
+	return string_is_number(sym->name) || string_is_hex(sym->name);
+}
+
+/*
+ * check, if the symbol is a tristate-constant
+ */
+bool sym_is_tristate_constant(struct symbol *sym)
+{
+	return sym == &symbol_yes || sym == &symbol_mod || sym == &symbol_no;
+}
+
+/*
+ * check, if a symbol is of type boolean or tristate
+ */
+bool sym_is_boolean(struct symbol *sym)
+{
+	return sym->type == S_BOOLEAN || sym->type == S_TRISTATE;
+}
+
+/*
+ * check, if a symbol is a boolean/tristate or a tristate constant
+ */
+bool sym_is_bool_or_triconst(struct symbol *sym)
+{
+	return sym_is_tristate_constant(sym) || sym_is_boolean(sym);
+}
+
+/*
+ * check, if a symbol is of type int, hex, or string
+ */
+bool sym_is_nonboolean(struct symbol *sym)
+{
+	return sym->type == S_INT || sym->type == S_HEX ||
+	       sym->type == S_STRING;
+}
+
+/*
+ * check, if a symbol has a prompt
+ */
+bool sym_has_prompt(struct symbol *sym)
+{
+	struct property *prop;
+
+	for_all_prompts(sym, prop)
+		return true;
+
+	return false;
+}
+
+/*
+ * return the prompt of the symbol if there is one, NULL otherwise
+ */
+struct property *sym_get_prompt(struct symbol *sym)
+{
+	struct property *prop;
+
+	for_all_prompts(sym, prop)
+		return prop;
+
+	return NULL;
+}
+
+/*
+ * return the condition for the property, NULL if there is none. To be pexpr_put
+ * by caller.
+ */
+struct pexpr *prop_get_condition(struct property *prop, struct cfdata *data)
+{
+	if (prop == NULL)
+		return NULL;
+
+	/* if there is no condition, return True */
+	if (!prop->visible.expr)
+		return pexpr_alloc_symbol(data->constants->const_true);
+
+	return expr_calculate_pexpr_both(prop->visible.expr, data);
+}
+
+/*
+ * return the default property, NULL if none exists or can be satisfied
+ */
+struct property *sym_get_default_prop(struct symbol *sym)
+{
+	struct property *prop;
+
+	for_all_defaults(sym, prop) {
+		prop->visible.tri = expr_calc_value(prop->visible.expr);
+		if (prop->visible.tri != no)
+			return prop;
+	}
+	return NULL;
+}
+
+/*
+ * check whether a non-boolean symbol has a value set
+ */
+bool sym_nonbool_has_value_set(struct symbol *sym)
+{
+	/*
+	 * The built constraints make the following constraints:
+	 *
+	 * visible -> not 'n'
+	 * sym->dir_dep not fulfilled -> 'n'
+	 * invisible -> (no default's condition is fulfilled <-> 'n')
+	 */
+	struct property *prompt;
+	struct property *p;
+
+	if (!sym_is_nonboolean(sym))
+		return false;
+
+	/* cannot have a value with unmet dependencies */
+	if (sym->dir_dep.expr && sym->dir_dep.tri == no)
+		return false;
+
+	/* visible prompt => value set */
+	prompt = sym_get_prompt(sym);
+	if (prompt != NULL && prompt->visible.tri != no)
+		return true;
+
+	/* invisible prompt => must get value from default value */
+	p = sym_get_default_prop(sym);
+	return p != NULL;
+}
+
+/*
+ * return pointer to the name of the symbol or the current prompt-text, if it
+ * is a choice symbol
+ */
+const char *sym_get_name(struct symbol *sym)
+{
+	if (sym_is_choice(sym)) {
+		struct property *prompt = sym_get_prompt(sym);
+
+		if (prompt == NULL)
+			return "";
+
+		return prompt->text;
+	} else {
+		return sym->name;
+	}
+}
+
+/*
+ * check whether symbol is to be changed
+ */
+bool sym_is_sdv(struct sdv_list *list, struct symbol *sym)
+{
+	struct sdv_node *node;
+
+	CF_LIST_FOR_EACH(node, list, sdv)
+		if (sym == node->elem->sym)
+			return true;
+
+	return false;
+}
+
+/*
+ * print a symbol's name
+ */
+void print_sym_name(struct symbol *sym)
+{
+	printf("Symbol: ");
+	if (sym_is_choice(sym)) {
+		struct property *prompt = sym_get_prompt(sym);
+
+		printf("(Choice) %s", prompt->text);
+	} else  {
+		printf("%s", sym->name);
+	}
+	printf("\n");
+}
+
+/*
+ * print all constraints for a symbol
+ */
+void print_sym_constraint(struct symbol *sym)
+{
+	struct pexpr_node *node;
+
+	CF_LIST_FOR_EACH(node, sym->constraints, pexpr)
+		pexpr_print("::", node->elem, -1);
+}
+
+/*
+ * print a default map
+ */
+void print_default_map(struct defm_list *map)
+{
+	struct default_map *entry;
+	struct defm_node *node;
+
+	CF_LIST_FOR_EACH(node, map, defm) {
+		struct gstr s = str_new();
+
+		entry = node->elem;
+
+		str_append(&s, "\t");
+		str_append(&s, str_get(&entry->val->name));
+		str_append(&s, " ->");
+		pexpr_print(strdup(str_get(&s)), entry->e, -1);
+		str_free(&s);
+	}
+}
+
+/*
+ * check whether a string is a number
+ */
+bool string_is_number(char *s)
+{
+	int len = strlen(s);
+	int i = 0;
+
+	while (i < len) {
+		if (!isdigit(s[i]))
+			return false;
+		i++;
+	}
+
+	return true;
+}
+
+/*
+ * check whether a string is a hexadecimal number
+ */
+bool string_is_hex(char *s)
+{
+	int len = strlen(s);
+	int i = 2;
+
+	if (len >= 3 && s[0] == '0' && s[1] == 'x') {
+		while (i < len) {
+			if (!isxdigit(s[i]))
+				return false;
+			i++;
+		}
+		return true;
+	} else {
+		return false;
+	}
+}
+
+/*
+ * initialize PicoSAT
+ */
+PicoSAT *initialize_picosat(void)
+{
+	PicoSAT *pico;
+
+	printd("\nInitializing PicoSAT...");
+	pico = picosat_init();
+	picosat_enable_trace_generation(pico);
+	printd("done.\n");
+
+	return pico;
+}
+
+/*
+ * construct the CNF-clauses from the constraints
+ */
+void construct_cnf_clauses(PicoSAT *p, struct cfdata *data)
+{
+	struct symbol *sym;
+
+	pico = p;
+
+	/* adding unit-clauses for constants */
+	sat_add_clause(2, pico, -(data->constants->const_false->satval));
+	sat_add_clause(2, pico, data->constants->const_true->satval);
+
+	for_all_symbols(sym) {
+		struct pexpr_node *node;
+
+		if (sym->type == S_UNKNOWN)
+			continue;
+
+		CF_LIST_FOR_EACH(node, sym->constraints, pexpr) {
+			if (pexpr_is_cnf(node->elem)) {
+				unfold_cnf_clause(node->elem);
+				picosat_add(pico, 0);
+			} else {
+				build_cnf_tseytin(node->elem, data);
+			}
+
+		}
+	}
+}
+
+/*
+ * helper function to add an expression to a CNF-clause
+ */
+static void unfold_cnf_clause(struct pexpr *e)
+{
+	switch (e->type) {
+	case PE_SYMBOL:
+		picosat_add(pico, e->left.fexpr->satval);
+		break;
+	case PE_OR:
+		unfold_cnf_clause(e->left.pexpr);
+		unfold_cnf_clause(e->right.pexpr);
+		break;
+	case PE_NOT:
+		picosat_add(pico, -(e->left.pexpr->left.fexpr->satval));
+		break;
+	default:
+		perror("Not in CNF, FE_EQUALS.");
+	}
+}
+
+/*
+ * build CNF-clauses for a pexpr not in CNF
+ */
+static void build_cnf_tseytin(struct pexpr *e, struct cfdata *data)
+{
+	switch (e->type) {
+	case PE_AND:
+		build_cnf_tseytin_top_and(e, data);
+		break;
+	case PE_OR:
+		build_cnf_tseytin_top_or(e, data);
+		break;
+	default:
+		perror("Expression not a propositional logic formula. root.");
+	}
+}
+
+/*
+ * split up a pexpr of type AND as both sides must be satisfied
+ */
+static void build_cnf_tseytin_top_and(struct pexpr *e, struct cfdata *data)
+{
+	if (pexpr_is_cnf(e->left.pexpr))
+		unfold_cnf_clause(e->left.pexpr);
+	else
+		build_cnf_tseytin(e->left.pexpr, data);
+
+	if (pexpr_is_cnf(e->right.pexpr))
+		unfold_cnf_clause(e->right.pexpr);
+	else
+		build_cnf_tseytin(e->right.pexpr, data);
+
+}
+
+static void build_cnf_tseytin_top_or(struct pexpr *e, struct cfdata *data)
+{
+	struct fexpr *t1 = NULL, *t2 = NULL;
+	int a, b;
+
+	/* set left side */
+	if (pexpr_is_symbol(e->left.pexpr)) {
+		a = pexpr_get_satval(e->left.pexpr);
+	} else {
+		t1 = create_tmpsatvar(data);
+		a = t1->satval;
+	}
+
+	/* set right side */
+	if (pexpr_is_symbol(e->right.pexpr)) {
+		b = pexpr_get_satval(e->right.pexpr);
+	} else {
+		t2 = create_tmpsatvar(data);
+		b = t2->satval;
+	}
+
+	/* A v B */
+	sat_add_clause(3, pico, a, b);
+
+	/* traverse down the tree to build more constraints if needed */
+	if (!pexpr_is_symbol(e->left.pexpr)) {
+		if (t1 == NULL)
+			perror("t1 is NULL.");
+
+		build_cnf_tseytin_tmp(e->left.pexpr, t1, data);
+	}
+
+	if (!pexpr_is_symbol(e->right.pexpr)) {
+		if (t2 == NULL)
+			perror("t2 is NULL.");
+
+		build_cnf_tseytin_tmp(e->right.pexpr, t2, data);
+	}
+}
+
+/*
+ * build the sub-expressions
+ */
+static void build_cnf_tseytin_tmp(struct pexpr *e, struct fexpr *t,
+				  struct cfdata *data)
+{
+	switch (e->type) {
+	case PE_AND:
+		build_cnf_tseytin_and(e, t, data);
+		break;
+	case PE_OR:
+		build_cnf_tseytin_or(e, t, data);
+		break;
+	default:
+		perror("Expression not a propositional logic formula. root.");
+	}
+}
+
+/*
+ * build the Tseytin sub-expressions for a pexpr of type AND
+ */
+static void build_cnf_tseytin_and(struct pexpr *e, struct fexpr *t,
+				  struct cfdata *data)
+{
+	struct fexpr *t1 = NULL, *t2 = NULL;
+	int a, b, c;
+
+	assert(t != NULL);
+
+	/* set left side */
+	if (pexpr_is_symbol(e->left.pexpr)) {
+		a = pexpr_get_satval(e->left.pexpr);
+	} else {
+		t1 = create_tmpsatvar(data);
+		a = t1->satval;
+	}
+
+	/* set right side */
+	if (pexpr_is_symbol(e->right.pexpr)) {
+		b = pexpr_get_satval(e->right.pexpr);
+	} else {
+		t2 = create_tmpsatvar(data);
+		b = t2->satval;
+	}
+
+	c = t->satval;
+
+	/* -A v -B v C */
+	sat_add_clause(4, pico, -a, -b, c);
+	/* A v -C */
+	sat_add_clause(3, pico, a, -c);
+	/* B v -C */
+	sat_add_clause(3, pico, b, -c);
+
+	/* traverse down the tree to build more constraints if needed */
+	if (!pexpr_is_symbol(e->left.pexpr)) {
+		if (t1 == NULL)
+			perror("t1 is NULL.");
+
+		build_cnf_tseytin_tmp(e->left.pexpr, t1, data);
+	}
+	if (!pexpr_is_symbol(e->right.pexpr)) {
+		if (t2 == NULL)
+			perror("t2 is NULL.");
+
+		build_cnf_tseytin_tmp(e->right.pexpr, t2, data);
+	}
+}
+
+/*
+ * build the Tseytin sub-expressions for a pexpr of type
+ */
+static void build_cnf_tseytin_or(struct pexpr *e, struct fexpr *t,
+				 struct cfdata *data)
+{
+	struct fexpr *t1 = NULL, *t2 = NULL;
+	int a, b, c;
+
+	assert(t != NULL);
+
+	/* set left side */
+	if (pexpr_is_symbol(e->left.pexpr)) {
+		a = pexpr_get_satval(e->left.pexpr);
+	} else {
+		t1 = create_tmpsatvar(data);
+		a = t1->satval;
+	}
+
+	/* set right side */
+	if (pexpr_is_symbol(e->right.pexpr)) {
+		b = pexpr_get_satval(e->right.pexpr);
+	} else {
+		t2 = create_tmpsatvar(data);
+		b = t2->satval;
+	}
+
+	c = t->satval;
+
+	/* A v B v -C */
+	sat_add_clause(4, pico, a, b, -c);
+	/* -A v C */;
+	sat_add_clause(3, pico, -a, c);
+	/* -B v C */
+	sat_add_clause(3, pico, -b, c);
+
+	/* traverse down the tree to build more constraints if needed */
+	if (!pexpr_is_symbol(e->left.pexpr)) {
+		if (t1 == NULL)
+			perror("t1 is NULL.");
+
+		build_cnf_tseytin_tmp(e->left.pexpr, t1, data);
+	}
+	if (!pexpr_is_symbol(e->right.pexpr)) {
+		if (t2 == NULL)
+			perror("t2 is NULL.");
+
+		build_cnf_tseytin_tmp(e->right.pexpr, t2, data);
+	}
+}
+
+/*
+ * add a clause to PicoSAT
+ * First argument must be the SAT solver
+ */
+void sat_add_clause(int num, ...)
+{
+	va_list valist;
+	int lit;
+	PicoSAT *pico;
+
+	if (num <= 1)
+		return;
+
+	va_start(valist, num);
+
+	pico = va_arg(valist, PicoSAT *);
+
+	/* access all the arguments assigned to valist */
+	for (int i = 1; i < num; i++) {
+		lit = va_arg(valist, int);
+		picosat_add(pico, lit);
+	}
+	picosat_add(pico, 0);
+
+	va_end(valist);
+}
+
+/*
+ * return the SAT-variable for a pexpr that is a symbol
+ */
+static int pexpr_get_satval(struct pexpr *e)
+{
+	if (!pexpr_is_symbol(e)) {
+		perror("pexpr is not a symbol.");
+		return -1;
+	}
+
+	switch (e->type) {
+	case PE_SYMBOL:
+		return e->left.fexpr->satval;
+	case PE_NOT:
+		return -(e->left.pexpr->left.fexpr->satval);
+	default:
+		perror("Not a symbol.");
+	}
+
+	return -1;
+}
+
+/*
+ * start PicoSAT
+ */
+void picosat_solve(PicoSAT *pico, struct cfdata *data)
+{
+	clock_t start, end;
+	double time;
+	int res;
+
+	printd("Solving SAT-problem...");
+
+	start = clock();
+	res = picosat_sat(pico, -1);
+	end = clock();
+
+	time = ((double) (end - start)) / CLOCKS_PER_SEC;
+	printd("done. (%.6f secs.)\n\n", time);
+
+	if (res == PICOSAT_SATISFIABLE) {
+		printd("===> PROBLEM IS SATISFIABLE <===\n");
+
+	} else if (res == PICOSAT_UNSATISFIABLE) {
+		struct fexpr *e;
+		int lit;
+		const int *i;
+
+		printd("===> PROBLEM IS UNSATISFIABLE <===\n");
+
+		/* print unsat core */
+		printd("\nPrinting unsatisfiable core:\n");
+
+		i = picosat_failed_assumptions(pico);
+		lit = abs(*i++);
+
+		while (lit != 0) {
+			e = data->satmap[lit];
+
+			printd("(%d) %s <%d>\n", lit, str_get(&e->name),
+			       e->assumption);
+			lit = abs(*i++);
+		}
+	} else {
+		printd("Unknown if satisfiable.\n");
+	}
+}
+
+/*
+ * add assumption for a symbol to the SAT-solver
+ */
+void sym_add_assumption(PicoSAT *pico, struct symbol *sym)
+{
+	if (sym_is_boolean(sym)) {
+		int tri_val = sym_get_tristate_value(sym);
+
+		sym_add_assumption_tri(pico, sym, tri_val);
+		return;
+	}
+
+	if (sym_is_nonboolean(sym)) {
+		bool first;
+		struct fexpr *not_set = list_first_entry(&sym->nb_vals->list,
+						   struct fexpr_node, node)
+					  ->elem;
+		struct fexpr_node *node;
+
+		const char *string_val = sym_get_string_value(sym);
+
+		if (sym->type == S_STRING && !strcmp(string_val, ""))
+			return;
+
+		/* symbol does not have a value */
+		if (!sym_nonbool_has_value_set(sym)) {
+			bool first = true;
+
+			/* set value for sym=n */
+			picosat_assume(pico, not_set->satval);
+			not_set->assumption = true;
+
+			CF_LIST_FOR_EACH(node, sym->nb_vals, fexpr) {
+				if (first) {
+					first = false;
+					continue;
+				}
+				picosat_assume(pico, -(node->elem->satval));
+				node->elem->assumption = false;
+			}
+
+			return;
+		}
+
+		/* symbol does have a value set */
+
+		/* set value for sym=n */
+		picosat_assume(pico, -(not_set->satval));
+		not_set->assumption = false;
+
+		first = true;
+		/* set value for all other fexpr */
+		CF_LIST_FOR_EACH(node, sym->nb_vals, fexpr) {
+			if (first) {
+				first = false;
+				continue;
+			}
+
+			if (strcmp(str_get(&node->elem->nb_val), string_val) ==
+			    0) {
+				picosat_assume(pico, node->elem->satval);
+				node->elem->assumption = true;
+			} else {
+				picosat_assume(pico, -(node->elem->satval));
+				node->elem->assumption = false;
+			}
+		}
+	}
+}
+
+/*
+ * add assumption for a boolean symbol to the SAT-solver
+ */
+void sym_add_assumption_tri(PicoSAT *pico, struct symbol *sym, tristate tri_val)
+{
+	if (sym->type == S_BOOLEAN) {
+		int a = sym->fexpr_y->satval;
+
+		switch (tri_val) {
+		case no:
+			picosat_assume(pico, -a);
+			sym->fexpr_y->assumption = false;
+			break;
+		case mod:
+			perror("Should not happen. Boolean symbol is set to mod.\n");
+			break;
+		case yes:
+
+			picosat_assume(pico, a);
+			sym->fexpr_y->assumption = true;
+			break;
+		}
+	}
+	if (sym->type == S_TRISTATE) {
+		int a = sym->fexpr_y->satval;
+		int a_m = sym->fexpr_m->satval;
+
+		switch (tri_val) {
+		case no:
+			picosat_assume(pico, -a);
+			picosat_assume(pico, -a_m);
+			sym->fexpr_y->assumption = false;
+			sym->fexpr_m->assumption = false;
+			break;
+		case mod:
+			picosat_assume(pico, -a);
+			picosat_assume(pico, a_m);
+			sym->fexpr_y->assumption = false;
+			sym->fexpr_m->assumption = true;
+			break;
+		case yes:
+			picosat_assume(pico, a);
+			picosat_assume(pico, -a_m);
+			sym->fexpr_y->assumption = true;
+			sym->fexpr_m->assumption = false;
+			break;
+		}
+	}
+}
+
+/*
+ * add assumptions for the symbols to be changed to the SAT solver
+ */
+void sym_add_assumption_sdv(PicoSAT *pico, struct sdv_list *list)
+{
+	struct symbol_dvalue *sdv;
+	struct sdv_node *node;
+	int lit_y, lit_m;
+
+	CF_LIST_FOR_EACH(node, list, sdv) {
+		sdv = node->elem;
+		lit_y = sdv->sym->fexpr_y->satval;
+
+		if (sdv->sym->type == S_BOOLEAN) {
+			switch (sdv->tri) {
+			case yes:
+				picosat_assume(pico, lit_y);
+				break;
+			case no:
+				picosat_assume(pico, -lit_y);
+				break;
+			case mod:
+				perror("Should not happen.\n");
+			}
+		} else if (sdv->sym->type == S_TRISTATE) {
+			lit_m = sdv->sym->fexpr_m->satval;
+
+			switch (sdv->tri) {
+			case yes:
+				picosat_assume(pico, lit_y);
+				picosat_assume(pico, -lit_m);
+				break;
+			case mod:
+				picosat_assume(pico, -lit_y);
+				picosat_assume(pico, lit_m);
+				break;
+			case no:
+				picosat_assume(pico, -lit_y);
+				picosat_assume(pico, -lit_m);
+			}
+		}
+	}
+}
scripts/kconfig/cf_utils.h new file +136 -0

136 lines not on this page · raw message

Signature · 1 line
2.39.5
#10 lore raw

PATCH v7 8/11 kconfig: Add tools

In reply to Ole Schuerks

Add the actual API to be used from a configurator as well as a tool to export the translation of the kconfig-model into propositional logic to a file.

---
 scripts/kconfig/.gitignore    |   1 +
 scripts/kconfig/cfoutconfig.c | 149 ++++++++++++++
 scripts/kconfig/configfix.c   | 352 ++++++++++++++++++++++++++++++++++
 scripts/kconfig/configfix.h   |  31 +++
 4 files changed, 533 insertions(+)
 create mode 100644 scripts/kconfig/cfoutconfig.c
 create mode 100644 scripts/kconfig/configfix.c
 create mode 100644 scripts/kconfig/configfix.h
scripts/kconfig/.gitignore +1 -0
index 0b2ff775b2e3..23446f70083e 100644
@@ -5,3 +5,4 @@
 /[gmnq]conf-cflags
 /[gmnq]conf-libs
 /qconf-moc.cc
+/cfoutconfig
scripts/kconfig/cfoutconfig.c new file +149 -0

149 lines not on this page · raw message

scripts/kconfig/configfix.c new file +352 -0

352 lines not on this page · raw message

scripts/kconfig/configfix.h new file +31 -0
new file mode 100644
index 000000000000..717f12ec9a2c
@@ -0,0 +1,31 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * Copyright (C) 2023 Patrick Franz <[email protected]>
+ */
+
+#ifndef CONFIGFIX_H
+#define CONFIGFIX_H
+
+/* make functions accessible from xconfig */
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/* include own definitions */
+#include "cf_defs.h"
+
+/* external functions */
+struct sfix_list **run_satconf(struct symbol_dvalue **symbols, size_t n,
+			       size_t *num_solutions);
+struct sfl_list *run_satconf_list(struct sdv_list *symbols);
+int apply_fix(struct sfix_list *fix);
+int run_satconf_cli(const char *Kconfig_file);
+void interrupt_fix_generation(void);
+struct sfix_list *select_solution(struct sfl_list *solutions, int index);
+struct symbol_fix *select_symbol(struct sfix_list *solution, int index);
+
+/* make functions accessible from xconfig */
+#ifdef __cplusplus
+}
+#endif
+#endif
Signature · 1 line
2.39.5
#11 lore raw

PATCH v7 9/11 kconfig: Add xconfig-modifications

In reply to Ole Schuerks

Add the modifications to xconfig to integrate the conflict resolver.

---
 scripts/kconfig/qconf.cc | 676 ++++++++++++++++++++++++++++++++++++++-
 scripts/kconfig/qconf.h  | 111 +++++++
 2 files changed, 785 insertions(+), 2 deletions(-)
scripts/kconfig/qconf.cc +674 -2
index eaa465b0ccf9..d798177a8c26 100644
@@ -19,21 +19,40 @@
 #include <QRegularExpression>
 #include <QScreen>
 #include <QToolBar>
+#include <QListWidget>
+#include <QComboBox>
+#include <QTableWidget>
+#include <QHBoxLayout>
+#include <QMovie>
+#include <QMessageBox>
+#include <QPlainTextEdit>
+#include <QAbstractItemView>
+#include <QMimeData>
+#include <QBrush>
+#include <QColor>
 
+#include <xalloc.h>
+#include "lkc.h"
+#include <vector>
 #include <stdlib.h>
 
-#include <xalloc.h>
 #include "lkc.h"
 #include "qconf.h"
+#include "configfix.h"
+#include "picosat_functions.h"
 
 #include "images.h"
 
+static QString tristate_value_to_string(tristate val);
+static tristate string_value_to_tristate(QString s);
 
 static QApplication *configApp;
 static ConfigSettings *configSettings;
 
 QAction *ConfigMainWindow::saveAction;
 
+static bool picosat_available;
+
 ConfigSettings::ConfigSettings()
 	: QSettings("kernel.org", "qconf")
 {
@@ -404,7 +423,7 @@ void ConfigList::updateSelection(void)
 	ConfigItem* item = (ConfigItem*)selectedItems().first();
 	if (!item)
 		return;
-
+	emit selectionChanged(selectedItems());
 	menu = item->menu;
 	emit menuChanged(menu);
 	if (!menu)
@@ -537,6 +556,7 @@ void ConfigList::changeValue(ConfigItem* item)
 		}
 		if (oldexpr != newexpr)
 			ConfigList::updateListForAll();
+			emit updateConflictsViewColorization();
 		break;
 	default:
 		break;
@@ -878,6 +898,7 @@ void ConfigList::contextMenuEvent(QContextMenuEvent *e)
 			action, &QAction::setChecked);
 		action->setChecked(showName);
 		headerPopup->addAction(action);
+		headerPopup->addAction(addSymbolFromContextMenu);
 	}
 
 	headerPopup->exec(e->globalPos());
@@ -898,6 +919,7 @@ QList<ConfigList *> ConfigList::allLists;
 QAction *ConfigList::showNormalAction;
 QAction *ConfigList::showAllAction;
 QAction *ConfigList::showPromptAction;
+QAction *ConfigList::addSymbolFromContextMenu;
 
 void ConfigList::setAllOpen(bool open)
 {
@@ -1187,7 +1209,11 @@ ConfigSearchWindow::ConfigSearchWindow(ConfigMainWindow *parent)
 		info, &ConfigInfoView::setInfo);
 	connect(list, &ConfigList::menuChanged,
 		parent, &ConfigMainWindow::setMenuLink);
+	connect(list, &ConfigList::menuChanged,
+		parent, &ConfigMainWindow::conflictSelected);
 
+	connect(list, &ConfigList::updateConflictsViewColorization, this,
+		&ConfigSearchWindow::updateConflictsViewColorizationFowarder);
 	layout1->addWidget(split);
 
 	QVariant x, y;
@@ -1210,6 +1236,11 @@ ConfigSearchWindow::ConfigSearchWindow(ConfigMainWindow *parent)
 		this, &ConfigSearchWindow::saveSettings);
 }
 
+void ConfigSearchWindow::updateConflictsViewColorizationFowarder(void)
+{
+	emit updateConflictsViewColorization();
+}
+
 void ConfigSearchWindow::saveSettings(void)
 {
 	if (!objectName().isEmpty()) {
@@ -1296,6 +1327,24 @@ ConfigMainWindow::ConfigMainWindow(void)
 	helpText = new ConfigInfoView(split2, "help");
 	setTabOrder(configList, helpText);
 
+	split3 = new QSplitter(split2);
+	split3->setOrientation(Qt::Vertical);
+	conflictsView = new ConflictsView(split3, "help");
+	/*
+	 * conflictsSelected signal in conflictsview triggers when a conflict is
+	 * selected in the view. this line connects that event to conflictselected
+	 * event in mainwindow which updates the selection to match (in the
+	 * configlist) the symbol that was selected.
+	 */
+	connect(conflictsView, &ConflictsView::conflictSelected, this,
+		&ConfigMainWindow::conflictSelected);
+	connect(conflictsView, &ConflictsView::refreshMenu, this,
+		&ConfigMainWindow::refreshMenu);
+	connect(menuList, &ConfigList::updateConflictsViewColorization,
+		conflictsView, &ConflictsView::updateConflictsViewColorization);
+	connect(configList, &ConfigList::updateConflictsViewColorization,
+		conflictsView, &ConflictsView::updateConflictsViewColorization);
+
 	configList->setFocus();
 
 	backAction = new QAction(QPixmap(xpm_back), "Back", this);
@@ -1362,6 +1411,10 @@ ConfigMainWindow::ConfigMainWindow(void)
 	ConfigList::showAllAction->setCheckable(true);
 	ConfigList::showPromptAction = new QAction("Show Prompt Options", optGroup);
 	ConfigList::showPromptAction->setCheckable(true);
+	ConfigList::addSymbolFromContextMenu =
+		new QAction("Add symbol from context menu");
+	connect(ConfigList::addSymbolFromContextMenu, &QAction::triggered,
+		conflictsView, &ConflictsView::addSymbol);
 
 	QAction *showDebugAction = new QAction("Show Debug Info", this);
 	  showDebugAction->setCheckable(true);
@@ -1417,6 +1470,8 @@ ConfigMainWindow::ConfigMainWindow(void)
 
 	connect(configList, &ConfigList::menuChanged,
 		helpText, &ConfigInfoView::setInfo);
+	connect(configList, &ConfigList::menuChanged,
+		conflictsView, &ConflictsView::menuChanged);
 	connect(configList, &ConfigList::menuSelected,
 		this, &ConfigMainWindow::changeMenu);
 	connect(configList, &ConfigList::itemSelected,
@@ -1425,6 +1480,8 @@ ConfigMainWindow::ConfigMainWindow(void)
 		this, &ConfigMainWindow::goBack);
 	connect(menuList, &ConfigList::menuChanged,
 		helpText, &ConfigInfoView::setInfo);
+	connect(menuList, &ConfigList::menuChanged,
+		conflictsView, &ConflictsView::menuChanged);
 	connect(menuList, &ConfigList::menuSelected,
 		this, &ConfigMainWindow::changeMenu);
 
@@ -1634,6 +1691,13 @@ void ConfigMainWindow::showSplitView(void)
 	menuList->setFocus();
 }
 
+void ConfigMainWindow::conflictSelected(struct menu *men)
+{
+	configList->clearSelection();
+	menuList->clearSelection();
+	emit(setMenuLink(men));
+}
+
 void ConfigMainWindow::showFullView(void)
 {
 	singleViewAction->setEnabled(true);
@@ -1769,6 +1833,536 @@ void ConfigMainWindow::conf_changed(bool dirty)
 		saveAction->setEnabled(dirty);
 }
 
+void ConfigMainWindow::refreshMenu(void)
+{
+	configList->updateListAll();
+}
+
+void QTableWidget::dropEvent(QDropEvent *event)
+{
+}
+
+void ConflictsView::addPicoSatNote(QToolBar &toolbar)
+{
+	QLabel &label = *new QLabel;
+	auto &iconLabel = *new QLabel();
+	iconLabel.setPixmap(
+		style()->standardIcon(
+			       QStyle::StandardPixmap::SP_MessageBoxInformation)
+			.pixmap(20, 20));
+	label.setText(
+		"The conflict resolver requires that PicoSAT is available as a library.");
+	QAction &showDialog = *new QAction();
+	showDialog.setIconText("Install PicoSAT...");
+	toolbar.addWidget(&iconLabel);
+	toolbar.addWidget(&label);
+	toolbar.addAction(&showDialog);
+	connect(&showDialog, &QAction::triggered,
+		[this]() { (new PicoSATInstallInfoWindow(this))->show(); });
+}
+
+ConflictsView::ConflictsView(QWidget *parent, const char *name)
+	: Parent(parent)
+{
+	/*
+	 * 	- topLevelLayout
+	 * 		- picoSatContainer
+	 *  		- picoSatLayout
+	 *  			- ...
+	 *		- conflictsViewContainer
+	 *			- horizontalLayout
+	 *				- verticalLayout
+	 *				- solutionLayout
+	 */
+	currentSelectedMenu = nullptr;
+	setObjectName(name);
+	QVBoxLayout *topLevelLayout = new QVBoxLayout(this);
+	QWidget *conflictsViewContainer = new QWidget;
+	if (!picosat_available) {
+		conflictsViewContainer->setDisabled(true);
+		QWidget *picoSatContainer = new QWidget;
+		topLevelLayout->addWidget(picoSatContainer);
+		QHBoxLayout *picoSatLayout = new QHBoxLayout(picoSatContainer);
+		QToolBar *picoToolbar = new QToolBar(picoSatContainer);
+		picoSatLayout->addWidget(picoToolbar);
+		picoSatLayout->addStretch();
+		addPicoSatNote(*picoToolbar);
+	}
+	topLevelLayout->addWidget(conflictsViewContainer);
+
+	QHBoxLayout *horizontalLayout = new QHBoxLayout(conflictsViewContainer);
+	QVBoxLayout *verticalLayout = new QVBoxLayout;
+	verticalLayout->setContentsMargins(0, 0, 0, 0);
+	conflictsToolBar =
+		new QToolBar("ConflictTools", conflictsViewContainer);
+	// toolbar buttons [n] [m] [y] [calculate fixes] [remove]
+	QAction *addSymbol = new QAction("Add Symbol");
+	QAction *setConfigSymbolAsNo = new QAction("N");
+	QAction *setConfigSymbolAsModule = new QAction("M");
+	QAction *setConfigSymbolAsYes = new QAction("Y");
+	fixConflictsAction_ = new QAction("Calculate Fixes");
+	QAction *removeSymbol = new QAction("Remove Symbol");
+	QMovie *loadingGif = new QMovie("scripts/kconfig/loader.gif");
+	auto loadingLabel = new QLabel;
+
+	if (loadingGif->isValid()) {
+		loadingGif->setScaledSize(loadingGif->scaledSize().scaled(
+			20, 20, Qt::KeepAspectRatioByExpanding));
+		loadingGif->start();
+		loadingLabel->setMovie(loadingGif);
+	} else {
+		loadingLabel->setText("Calculating...");
+	}
+
+	//if you change the order of buttons here, change the code where
+	//module button was disabled if symbol is boolean, selecting module button
+	//depends on a specific index in list of action
+	fixConflictsAction_->setCheckable(false);
+	conflictsToolBar->addAction(addSymbol);
+	conflictsToolBar->addAction(setConfigSymbolAsNo);
+	conflictsToolBar->addAction(setConfigSymbolAsModule);
+	conflictsToolBar->addAction(setConfigSymbolAsYes);
+	conflictsToolBar->addAction(fixConflictsAction_);
+	conflictsToolBar->addAction(removeSymbol);
+	// loadingLabel->setMargin(5);
+	loadingLabel->setContentsMargins(5, 5, 5, 5);
+	loadingAction = conflictsToolBar->addWidget(loadingLabel);
+	loadingAction->setVisible(false);
+
+	verticalLayout->addWidget(conflictsToolBar);
+
+	connect(addSymbol, &QAction::triggered, this,
+		&ConflictsView::addSymbol);
+	connect(setConfigSymbolAsNo, &QAction::triggered, this,
+		&ConflictsView::changeToNo);
+	connect(setConfigSymbolAsModule, &QAction::triggered, this,
+		&ConflictsView::changeToModule);
+	connect(setConfigSymbolAsYes, &QAction::triggered, this,
+		&ConflictsView::changeToYes);
+	connect(removeSymbol, &QAction::triggered, this,
+		&ConflictsView::removeSymbol);
+	connect(this, &ConflictsView::resultsReady, this,
+		&ConflictsView::updateResults);
+	//connect clicking 'calculate fixes' to 'change all symbol values to fix all conflicts'
+	// no longer used anymore for now.
+	connect(fixConflictsAction_, &QAction::triggered, this,
+		&ConflictsView::calculateFixes);
+
+	conflictsTable = (QTableWidget *)new dropAbleView(this);
+	conflictsTable->setRowCount(0);
+	conflictsTable->setColumnCount(3);
+	conflictsTable->setSelectionBehavior(QAbstractItemView::SelectRows);
+	conflictsTable->setEditTriggers(QAbstractItemView::NoEditTriggers);
+
+	conflictsTable->setHorizontalHeaderLabels(
+		QStringList() << "Name" << "Wanted value" << "Current value");
+	verticalLayout->addWidget(conflictsTable);
+
+	conflictsTable->setDragDropMode(QAbstractItemView::DropOnly);
+	setAcceptDrops(true);
+
+	connect(conflictsTable, &QTableWidget::cellClicked, this,
+		&ConflictsView::cellClicked);
+	horizontalLayout->addLayout(verticalLayout);
+
+	// populate the solution view on the right hand side:
+	QVBoxLayout *solutionLayout = new QVBoxLayout();
+	solutionLayout->setContentsMargins(0, 0, 0, 0);
+	solutionSelector = new QComboBox();
+	connect(solutionSelector,
+		QOverload<int>::of(&QComboBox::currentIndexChanged),
+		[=](int index) { changeSolutionTable(index); });
+	solutionTable = new QTableWidget();
+	solutionTable->setRowCount(0);
+	solutionTable->setColumnCount(2);
+	solutionTable->setHorizontalHeaderLabels(QStringList()
+						 << "Name" << "New Value");
+	solutionTable->setEditTriggers(QAbstractItemView::NoEditTriggers);
+
+	applyFixButton = new QPushButton("Apply Selected solution");
+	connect(applyFixButton, &QPushButton::clicked, this,
+		&ConflictsView::applyFixButtonClick);
+
+	numSolutionLabel = new QLabel("Solutions:");
+	solutionLayout->addWidget(numSolutionLabel);
+	solutionLayout->addWidget(solutionSelector);
+	solutionLayout->addWidget(solutionTable);
+	solutionLayout->addWidget(applyFixButton);
+
+	horizontalLayout->addLayout(solutionLayout);
+}
+
+void ConflictsView::applyFixButtonClick()
+{
+	signed int solution_number = solutionSelector->currentIndex();
+
+	if (solution_number == -1 || solution_output == NULL) {
+		return;
+	}
+
+	apply_fix(solution_output[solution_number]);
+
+	ConfigList::updateListForAll();
+	for (int i = 0; i < conflictsTable->rowCount(); i++) {
+		conflictsTable->item(i, 2)->setText(
+			conflictsTable->item(i, 1)->text());
+	}
+	updateConflictsViewColorization();
+	QMessageBox msgBox;
+	msgBox.setText("The solution has been applied.");
+	msgBox.exec();
+}
+
+void ConflictsView::changeToYes()
+{
+	QItemSelectionModel *select = conflictsTable->selectionModel();
+	if (select->hasSelection()) {
+		QModelIndexList rows = select->selectedRows();
+		for (int i = 0; i < rows.count(); i++) {
+			conflictsTable->item(rows[i].row(), 1)
+				->setText(tristate_value_to_string(yes));
+		}
+	}
+}
+
+void ConflictsView::changeToModule()
+{
+	QItemSelectionModel *select = conflictsTable->selectionModel();
+	if (select->hasSelection()) {
+		QModelIndexList rows = select->selectedRows();
+		for (int i = 0; i < rows.count(); i++) {
+			conflictsTable->item(rows[i].row(), 1)
+				->setText(tristate_value_to_string(mod));
+		}
+	}
+}
+
+void ConflictsView::changeToNo()
+{
+	QItemSelectionModel *select = conflictsTable->selectionModel();
+	if (select->hasSelection()) {
+		QModelIndexList rows = select->selectedRows();
+		for (int i = 0; i < rows.count(); i++) {
+			conflictsTable->item(rows[i].row(), 1)
+				->setText(tristate_value_to_string(no));
+		}
+	}
+}
+
+void ConflictsView::menuChanged(struct menu *m)
+{
+	currentSelectedMenu = m;
+}
+
+void ConflictsView::addSymbol()
+{
+	addSymbolFromMenu(currentSelectedMenu);
+}
+
+void ConflictsView::selectionChanged(QList<QTreeWidgetItem *> selection)
+{
+	currentSelection = selection;
+}
+
+void ConflictsView::addSymbolFromMenu(struct menu *m)
+{
+	// adds a symbol to the conflict resolver list
+	if (m != nullptr) {
+		if (m->sym != nullptr) {
+			struct symbol *sym = m->sym;
+			tristate currentval = sym_get_tristate_value(sym);
+			//if symbol is not added yet:
+			QAbstractItemModel *tableModel =
+				conflictsTable->model();
+			QModelIndexList matches = tableModel->match(
+				tableModel->index(0, 0), Qt::DisplayRole,
+				QString(sym->name));
+			if (matches.isEmpty()) {
+				conflictsTable->insertRow(
+					conflictsTable->rowCount());
+				conflictsTable->setItem(
+					conflictsTable->rowCount() - 1, 0,
+					new QTableWidgetItem(sym->name));
+				conflictsTable->setItem(
+					conflictsTable->rowCount() - 1, 1,
+					new QTableWidgetItem(
+						tristate_value_to_string(
+							currentval)));
+				conflictsTable->setItem(
+					conflictsTable->rowCount() - 1, 2,
+					new QTableWidgetItem(
+						tristate_value_to_string(
+							currentval)));
+			} else {
+				conflictsTable->item(matches[0].row(), 2)
+					->setText(tristate_value_to_string(
+						currentval));
+			}
+		}
+	}
+}
+
+void ConflictsView::addSymbolFromContextMenu()
+{
+	struct menu *menu;
+
+	if (currentSelection.count() < 0) {
+		return;
+	}
+	for (auto el : currentSelection) {
+		ConfigItem *item = (ConfigItem *)el;
+		if (!item) {
+			continue;
+		}
+		menu = item->menu;
+		addSymbolFromMenu(menu);
+	}
+}
+
+void ConflictsView::removeSymbol()
+{
+	QItemSelectionModel *select = conflictsTable->selectionModel();
+	QAbstractItemModel *itemModel = select->model();
+	if (select->hasSelection()) {
+		QModelIndexList rows = select->selectedRows();
+		itemModel->removeRows(rows[0].row(), rows.size());
+	}
+}
+
+void ConflictsView::cellClicked(int row, int column)
+{
+	auto itemText = conflictsTable->item(row, 0)->text().toUtf8().data();
+	struct property *prop;
+	struct menu *men;
+	struct symbol *sym = sym_find(itemText);
+
+	if (sym == NULL)
+		return;
+	prop = sym->prop;
+	men = prop->menu;
+	// uncommenting following like somehow disables click signal of 'apply selected solution'
+	if (sym->type == symbol_type::S_BOOLEAN) {
+		//disable module button
+		conflictsToolBar->actions()[2]->setDisabled(true);
+	} else {
+		//enable module button
+		conflictsToolBar->actions()[2]->setDisabled(false);
+	}
+	if (column == 1) {
+		// cycle to new value
+		tristate old_val = string_value_to_tristate(
+			conflictsTable->item(row, 1)->text());
+		tristate new_val = old_val;
+		switch (old_val) {
+		case no:
+			new_val = mod;
+			break;
+		case mod:
+			new_val = yes;
+			break;
+		case yes:
+			new_val = no;
+			break;
+		}
+		if (sym->type == S_BOOLEAN && new_val == mod)
+			new_val = yes;
+		conflictsTable->item(row, 1)->setText(
+			tristate_value_to_string(new_val));
+	}
+	emit(conflictSelected(men));
+}
+
+void ConflictsView::changeSolutionTable(int solution_number)
+{
+	size_t i;
+
+	if (solution_output == nullptr || solution_number < 0) {
+		return;
+	}
+	struct sfix_list *selected_solution = solution_output[solution_number];
+	current_solution_number = solution_number;
+	solutionTable->setRowCount(0);
+	i = 0;
+	for (struct list_head *curr = selected_solution->list.next;
+	     curr != &selected_solution->list; curr = curr->next, ++i) {
+		solutionTable->insertRow(solutionTable->rowCount());
+		struct symbol_fix *cur_symbol =
+			select_symbol(selected_solution, i);
+
+		QTableWidgetItem *symbol_name =
+			new QTableWidgetItem(cur_symbol->sym->name);
+
+		solutionTable->setItem(solutionTable->rowCount() - 1, 0,
+				       symbol_name);
+
+		if (cur_symbol->type == symbolfix_type::SF_BOOLEAN) {
+			QTableWidgetItem *symbol_value = new QTableWidgetItem(
+				tristate_value_to_string(cur_symbol->tri));
+			solutionTable->setItem(solutionTable->rowCount() - 1, 1,
+					       symbol_value);
+		} else if (cur_symbol->type == symbolfix_type::SF_NONBOOLEAN) {
+			QTableWidgetItem *symbol_value =
+				new QTableWidgetItem(cur_symbol->nb_val.s);
+			solutionTable->setItem(solutionTable->rowCount() - 1, 1,
+					       symbol_value);
+		} else {
+			QTableWidgetItem *symbol_value =
+				new QTableWidgetItem(cur_symbol->disallowed.s);
+			solutionTable->setItem(solutionTable->rowCount() - 1, 1,
+					       symbol_value);
+		}
+	}
+	updateConflictsViewColorization();
+}
+
+void ConflictsView::updateConflictsViewColorization(void)
+{
+	auto green = QColor(0, 170, 0);
+	auto red = QColor(255, 0, 0);
+	auto grey = QColor(180, 180, 180);
+
+	if (solutionTable->rowCount() == 0 || current_solution_number < 0)
+		return;
+
+	for (int i = 0; i < solutionTable->rowCount(); i++) {
+		QTableWidgetItem *symbol = solutionTable->item(i, 0);
+		//symbol from solution list
+		struct symbol_fix *cur_symbol = select_symbol(
+			solution_output[current_solution_number], i);
+
+		// if symbol is editable but the value is not the target value from solution we got, the color is red
+		// if symbol is editable but the value is the target value from solution we got, the color is green
+		// if symbol is not editable , the value is not the target value, the color is grey
+		// if symbol is not editable , the value is the target value, the color is green
+		auto editable = sym_string_within_range(
+			cur_symbol->sym,
+			tristate_value_to_string(cur_symbol->tri)
+				.toStdString()
+				.c_str());
+		auto _symbol =
+			solutionTable->item(i, 0)->text().toUtf8().data();
+		struct symbol *sym_ = sym_find(_symbol);
+
+		tristate current_value_of_symbol = sym_get_tristate_value(sym_);
+		tristate target_value_of_symbol = string_value_to_tristate(
+			solutionTable->item(i, 1)->text());
+		bool symbol_value_same_as_target = current_value_of_symbol ==
+						   target_value_of_symbol;
+
+		if (editable && !symbol_value_same_as_target) {
+			symbol->setForeground(red);
+		} else if (editable && symbol_value_same_as_target) {
+			symbol->setForeground(green);
+		} else if (!editable && !symbol_value_same_as_target) {
+			symbol->setForeground(grey);
+		} else if (!editable && symbol_value_same_as_target) {
+			symbol->setForeground(green);
+		}
+	}
+}
+
+void ConflictsView::runSatConfAsync()
+{
+	//loop through the rows in conflicts table adding each row into the array:
+	struct symbol_dvalue *p = nullptr;
+	std::vector<struct symbol_dvalue *> wanted_symbols;
+
+	p = static_cast<struct symbol_dvalue *>(calloc(
+		conflictsTable->rowCount(), sizeof(struct symbol_dvalue)));
+	if (!p) {
+		printf("memory allocation error\n");
+		return;
+	}
+
+	for (int i = 0; i < conflictsTable->rowCount(); i++) {
+		struct symbol_dvalue *tmp = (p + i);
+		auto _symbol =
+			conflictsTable->item(i, 0)->text().toUtf8().data();
+		struct symbol *sym = sym_find(_symbol);
+
+		tmp->sym = sym;
+		tmp->type = static_cast<symboldv_type>(
+			sym->type == symbol_type::S_BOOLEAN ? 0 : 1);
+		tmp->tri = string_value_to_tristate(
+			conflictsTable->item(i, 1)->text());
+		wanted_symbols.push_back(tmp);
+	}
+	fixConflictsAction_->setText("Cancel");
+	loadingAction->setVisible(true);
+
+	solution_output = run_satconf(wanted_symbols.data(),
+				      wanted_symbols.size(), &num_solutions);
+
+	free(p);
+	emit resultsReady();
+	{
+		std::lock_guard<std::mutex> lk{ satconf_mutex };
+		satconf_cancelled = true;
+	}
+	satconf_cancellation_cv.notify_one();
+}
+
+void ConflictsView::updateResults(void)
+{
+	fixConflictsAction_->setText("Calculate Fixes");
+	loadingAction->setVisible(false);
+	if (!(solution_output == nullptr || num_solutions == 0)) {
+		solutionSelector->clear();
+		for (unsigned int i = 0; i < num_solutions; i++)
+			solutionSelector->addItem(QString::number(i + 1));
+		// populate the solution table from the first solution gotten
+		numSolutionLabel->setText(
+			QString("Solutions: (%1) found").arg(num_solutions));
+		changeSolutionTable(0);
+	} else {
+		QMessageBox msgBox;
+		msgBox.setText("All symbols are already within range.");
+		msgBox.exec();
+	}
+	if (runSatConfAsyncThread->joinable()) {
+		runSatConfAsyncThread->join();
+		delete runSatConfAsyncThread;
+		runSatConfAsyncThread = nullptr;
+	}
+}
+
+void ConflictsView::calculateFixes()
+{
+	if (conflictsTable->rowCount() == 0) {
+		printd("table is empty\n");
+		return;
+	}
+
+	if (runSatConfAsyncThread == nullptr) {
+		// fire away asynchronous call
+		std::unique_lock<std::mutex> lk{ satconf_mutex };
+
+		numSolutionLabel->setText(QString("Solutions: "));
+		solutionSelector->clear();
+		solutionTable->setRowCount(0);
+		satconf_cancelled = false;
+		runSatConfAsyncThread =
+			new std::thread(&ConflictsView::runSatConfAsync, this);
+	} else {
+		printd("Interrupting fix generation\n");
+		interrupt_fix_generation();
+		std::unique_lock<std::mutex> lk{ satconf_mutex };
+		satconf_cancellation_cv.wait(lk, [this] {
+			return satconf_cancelled == true;
+		});
+	}
+}
+
+void ConflictsView::changeAll(void)
+{
+	// not implemented for now
+	return;
+}
+
+ConflictsView::~ConflictsView(void)
+{
+}
+
 void fixup_rootmenu(struct menu *menu)
 {
 	struct menu *child;
@@ -1818,6 +2412,8 @@ int main(int ac, char** av)
 	fixup_rootmenu(&rootmenu);
 	//zconfdump(stdout);
 
+	picosat_available = load_picosat();
+
 	configApp = new QApplication(ac, av);
 
 	configSettings = new ConfigSettings();
@@ -1836,3 +2432,79 @@ int main(int ac, char** av)
 
 	return 0;
 }
+
+dropAbleView::dropAbleView(QWidget *parent)
+	: QTableWidget(parent)
+{
+}
+
+dropAbleView::~dropAbleView()
+{
+}
+void dropAbleView::dropEvent(QDropEvent *event)
+{
+	event->acceptProposedAction();
+}
+
+static QString tristate_value_to_string(tristate val)
+{
+	switch (val) {
+	case yes:
+		return QString::fromStdString("Y");
+	case mod:
+		return QString::fromStdString("M");
+	case no:
+		return QString::fromStdString("N");
+	default:
+		return QString::fromStdString("");
+	}
+}
+
+static tristate string_value_to_tristate(QString s)
+{
+	if (s == "Y")
+		return tristate::yes;
+	else if (s == "M")
+		return tristate::mod;
+	else if (s == "N")
+		return tristate::no;
+	else
+		return tristate::no;
+}
+
+PicoSATInstallInfoWindow::PicoSATInstallInfoWindow(QWidget *parent)
+	: QDialog(parent)
+{
+	QVBoxLayout &layout = *new QVBoxLayout(this);
+	QLabel &text = *new QLabel();
+	text.setWordWrap(true);
+	layout.addWidget(&text);
+	text.setTextFormat(Qt::MarkdownText);
+	text.setTextInteractionFlags(Qt::TextSelectableByMouse);
+	text.setTextInteractionFlags(Qt::TextBrowserInteraction);
+	text.setOpenExternalLinks(true);
+	text.setText(R""""(
+Install the picosat package or build the library yourself:
+
+## Debian-based distributions
+
+```sh
+sudo apt install picosat
+```
+
+## Fedora
+
+```sh
+sudo dnf install picosat
+```
+
+## Other
+
+You can also build PicoSAT yourself from the
+[sources](https://fmv.jku.at/picosat/picosat-965.tar.gz). You need to compile
+PicoSAT with tracing enabled as a shared library under the name of
+"libpicosat-trace.so", "libpicosat-trace.so.0" or "libpicosat-trace.so.1".
+Tracing can be enabled using the `configure.sh` script with the `--trace`
+option.
+			  )"""");
+}
scripts/kconfig/qconf.h +111 -0

159 lines not on this page · raw message

Signature · 1 line
2.39.5
#12 lore raw

PATCH v7 10/11 kconfig: Add loader.gif

In reply to Ole Schuerks

Add the GIF used as the loading indicator.

We created the file from scratch using GIMP. It's also available at
https://github.com/delta-one/linux/blob/configfix_20240607-patches-5/scripts/kconfig/loader.gif

---
 scripts/kconfig/loader.gif | Bin 0 -> 4177 bytes
 1 file changed, 0 insertions(+), 0 deletions(-)
 create mode 100644 scripts/kconfig/loader.gif
scripts/kconfig/loader.gif new file binary +0 -0
new file mode 100644
index 0000000000000000000000000000000000000000..54c8bc76cc037ab04dc1d37ddc34384f9714284e
GIT binary patch
Signature · 1 line
2.39.5
#13 lore raw

PATCH v7 11/11 kconfig: Add documentation for the conflict resolver

In reply to Ole Schuerks

Add documentation for the interface of the conflict resolver and instructions for installing PicoSAT. The target audience is everyone using xconfig, in particular, kernel developers, end users, system administrators, and distributors.

---
 Documentation/kbuild/kconfig.rst | 56 ++++++++++++++++++++++++++++++++
 1 file changed, 56 insertions(+)
Documentation/kbuild/kconfig.rst +56 -0
index fc4e845bc249..d49ab303e757 100644
@@ -285,6 +285,62 @@ Searching in xconfig:
     You can also enter a different search string without having
     to return to the main menu.
 
+Conflict resolution
+-------------------
+
+    xconfig has support for conflict resolution. A conflict is in this case any
+    situation where you want to change the value of a symbol, but
+    unfulfilled dependencies prevent this. You can create a list of symbols
+    and their desired values, and the conflict resolver will calculate a series
+    of changes in xconfig, which allows setting the symbols to their desired
+    values.
+
+Requirements:
+
+    To use the conflict resolver, PicoSAT needs to be installed as a library.
+
+    Debian-based distributions::
+
+        sudo apt install picosat
+
+    Fedora::
+
+        sudo dnf install picosat
+
+    You can also build PicoSAT yourself from the `sources
+    <https://fmv.jku.at/picosat/picosat-965.tar.gz>`_. The conflict resolver
+    requires that PicoSAT is built with tracing enabled (e.g., using the
+    configure.sh script with the "--trace" option). It expects the shared
+    library to be named "libpicosat-trace.so", "libpicosat-trace.so.0" or
+    "libpicosat-trace.so.1".
+
+Usage:
+
+    To add a symbol to the list of symbols whose values should be changed (that
+    is, the 'conflict'), you select the symbol in the main view of xconfig. With
+    the button "Add symbol" you add the symbol to the conflict, which makes it
+    appear in a table below the main view. You need to switch to "Show Prompt
+    Options" under the tab "Option" if the symbol is hidden in the main view.
+    You can set the desired value of a symbol by either clicking on the
+    corresponding cell in the column "Wanted Value," or by selecting the
+    symbol's row and using one of the buttons above the table.
+
+    Once the 'conflict' is declared, the solutions can be calculated using the
+    button "Calculate Fixes". Once calculated, they appear in the menu on the
+    bottom right. You can select a solution from up to three candidates. The
+    solutions are presented in a table that shows which values the symbols need
+    to have to resolve the conflict. Using the button "Apply selected solution"
+    the indicated changes can automatically be applied. If you want to change
+    the values manually, the symbols are color-coded to indicate the order in
+    which they need to be set: Green means that a symbol is already set to the
+    calculated value. Gray means that a symbol cannot yet be set to the
+    calculated value and that other symbols' values need to be changed first.
+    Red means that a symbol is not yet set to the calculated value, but that you
+    can set it to the calculated value.
+
+    Note that in rare cases the conflict resolver cannot resolve the conflict
+    even when a solution exists, it suggests unnecessary changes, or it suggests
+    changes that do not resolve the conflict.
 
 gconfig
 =======
Signature · 1 line
2.39.5
#14 lore raw
In reply to Ole Schuerks
Quoted 39 lines · Ole Schuerks

Hi,

This patch series (for next-20250207) provides support to enable users to express their desired target configuration and display possible resolutions to their conflicts. This support is provided within xconfig.

Conflict resolution is provided by translating kconfig's configuration option tree to a propositional formula and allowing our resolution algorithm and PicoSAT to calculate the possible fixes for an expressed target kernel configuration. PicoSAT is the smallest and most robust C SAT solver we could find which is also GPL compatible. PicoSAT is used as a dynamically loaded library. For Debian and Fedora, the apt and dnf packages named "picosat" provide the library. For other distros, we provide instructions on how PicoSAT needs to be compiled from the sources in the documentation.

New UI extensions are made to xconfig with panes and buttons to allow users to express new desired target options, calculate fixes, and apply any of found solutions.

You can see a YouTube video demonstrating this work [2]. This effort is part of the kernelnewbies Kconfig-SAT project [3], the approach and effort is also explained in detail in our paper [4]. The results from the evaluation have significantly improved since then: Around 80 % of the conflicts could be resolved, and 99.9 % of the generated fixes resolved the conflict. It is also our attempt at contributing back to the kernel community, whose configurator researchers studied a lot.

Patches applicable to next-20250207.

[0] https://gsd.uwaterloo.ca/sites/default/files/vamos12-survey.pdf
[1] https://www.linux-magazine.com/Issues/2021/244/Kconfig-Deep-Dive
[2] https://www.youtube.com/watch?v=vn2JgK_PTbc
[3] https://kernelnewbies.org/KernelProjects/kconfig-sat
[4] http://www.cse.chalmers.se/~bergert/paper/2021-icseseip-configfix.pdf

Thanks from the team! (and thanks to Luis Chamberlain for guiding us here)

Quoted 9 lines

Changelog v7:
* improve error handling when loading picosat symbols with dlsym(): use dlerror() instead of checking for NULL
* move list_at_index from scripts/include/list.h to scripts/kconfig/cf_utils.h
* change interface of list_for_each_entry_from and rename list_size to list_count_nodes to more closely match scripts/include/list.h
* change misleading name "rangefix" of fix generation algorithm to "fixgen"

Thanks for this, but I have no plans to merge the SAT solver.

The reason is that my future plan is to move toolchain selection to the Kconfig stage instead of specifying it statically from the command line. This approach was suggested by Linus [1], and to achieve that,
the shell evaluation must be dynamically re-evaluated [2].

The SAT solver would likely conflict with this plan. At least due to the significant amount of additional code, which would be an obstacle.

[1] https://lore.kernel.org/lkml/CAHk-=whdrvCkSWh=BRrwZwNo3=yLBXXM88NGx8VEpP1VTgmkyQ@mail.gmail.com/

[2] https://lore.kernel.org/lkml/CAK7LNATe7Ah-ow9wYGrtL9i4z-VD=MCo=sJjbC_S0ofEoH6CFQ@mail.gmail.com/

Signature · 2 lines
Best Regards
Masahiro Yamada
#15 lore raw
Quoted 4 lines · Masahiro Yamada

Thanks for this, but I have no plans to merge the SAT solver.

The reason is that my future plan is to move toolchain selection to the Kconfig stage instead of specifying it statically from the command line.

That makes sense.

Quoted 2 lines

This approach was suggested by Linus [1], and to achieve that, the shell evaluation must be dynamically re-evaluated [2].

Sure.

Quoted 2 lines

The SAT solver would likely conflict with this plan. At least due to the significant amount of additional code, which would be an obstacle.

I can't see how the toolchain selection, if set on Kconfig can't be leveraged later to enable / disable the SAT solver, however I can see the amount of code shuffling incurred to be an extra hurdle to address and a preference to leave that for later.

In other words, I susepct it is still possible to evaluate to add support for the SAT solver post toolchain kconfig integration.

Thoughts?

Luis

#16 lore raw
Quoted 22 lines · Luis Chamberlain
Quoted 4 lines · Masahiro Yamada

Thanks for this, but I have no plans to merge the SAT solver.

The reason is that my future plan is to move toolchain selection to the Kconfig stage instead of specifying it statically from the command line.

That makes sense.

Quoted 2 lines

This approach was suggested by Linus [1], and to achieve that, the shell evaluation must be dynamically re-evaluated [2].

Sure.

Quoted 2 lines

The SAT solver would likely conflict with this plan. At least due to the significant amount of additional code, which would be an obstacle.

I can't see how the toolchain selection, if set on Kconfig can't be leveraged later to enable / disable the SAT solver, however I can see the amount of code shuffling incurred to be an extra hurdle to address and a preference to leave that for later.

Quoted 4 lines

In other words, I susepct it is still possible to evaluate to add support for the SAT solver post toolchain kconfig integration.

Thoughts?

It depends on how the dynamic shell evaluation is implemented. This is not limited to bool/tristate, but SAT solver only works for those two types.

Signature · 2 lines
Best Regards
Masahiro Yamada
#17 lore raw

Quick follow-up. On our end, our SAT-solver implementations can be easily adapted to accommodate your future toolchain selection refactorings. Also, could you share with us the timelines for your refactorings so we can plan and deliver the adjusted SAT-solver patches. Best Regards, Jude Gyimah

Quoted 31 lines · Masahiro Yamada
Quoted 18 lines · Luis Chamberlain
Quoted 4 lines · Masahiro Yamada

Thanks for this, but I have no plans to merge the SAT solver.

The reason is that my future plan is to move toolchain selection to the Kconfig stage instead of specifying it statically from the command line.

That makes sense.

Quoted 2 lines

This approach was suggested by Linus [1], and to achieve that, the shell evaluation must be dynamically re-evaluated [2].

Sure.

Quoted 2 lines

The SAT solver would likely conflict with this plan. At least due to the significant amount of additional code, which would be an obstacle.

I can't see how the toolchain selection, if set on Kconfig can't be leveraged later to enable / disable the SAT solver, however I can see the amount of code shuffling incurred to be an extra hurdle to address and a preference to leave that for later.

Quoted 4 lines

In other words, I susepct it is still possible to evaluate to add support for the SAT solver post toolchain kconfig integration.

Thoughts?

It depends on how the dynamic shell evaluation is implemented. This is not limited to bool/tristate, but SAT solver only works for those two types.

A message that is not in the archive (sent off-list or not yet received): [email protected]

#19 lore raw
Quoted 5 lines · Jude Gyimah

Quick follow-up.

On our end, our SAT-solver implementations can be easily adapted to accommodate your future toolchain selection refactorings.

OK, we will see.

Quoted 3 lines

Also, could you share with us the timelines for your refactorings so we can plan and deliver the adjusted SAT-solver patches.

There is no timeline in upstream development.

Quoted 41 lines

Best Regards,
Jude Gyimah

On 2/11/25 01:46, Masahiro Yamada wrote:

On Tue, Feb 11, 2025 at 12:43 AM Luis Chamberlain <[email protected]> wrote:

On Mon, Feb 10, 2025 at 02:00:52PM +0900, Masahiro Yamada wrote:

Thanks for this, but I have no plans to merge the SAT solver.

The reason is that my future plan is to move toolchain selection to the Kconfig stage instead of specifying it statically from the command line.

That makes sense.

This approach was suggested by Linus [1], and to achieve that, the shell evaluation must be dynamically re-evaluated [2].

Sure.

The SAT solver would likely conflict with this plan. At least due to the significant amount of additional code, which would be an obstacle.

I can't see how the toolchain selection, if set on Kconfig can't be leveraged later to enable / disable the SAT solver, however I can see the amount of code shuffling incurred to be an extra hurdle to address and a preference to leave that for later.

In other words, I susepct it is still possible to evaluate to add support for the SAT solver post toolchain kconfig integration.

Thoughts?

It depends on how the dynamic shell evaluation is implemented. This is not limited to bool/tristate, but SAT solver only works for those two types.

Signature · 2 lines
Best Regards
Masahiro Yamada
#20 lore raw

+ kdevops

Quoted 8 lines · Masahiro Yamada
Quoted 5 lines · Jude Gyimah

Quick follow-up.

On our end, our SAT-solver implementations can be easily adapted to accommodate your future toolchain selection refactorings.

Quoted 7 lines

OK, we will see.

Quoted 3 lines

Also, could you share with us the timelines for your refactorings so we can plan and deliver the adjusted SAT-solver patches.

There is no timeline in upstream development.

Jude, while Masahiro works on dynamic shell evaluation support and given the SAT solver currently works with bools / tristates, I can think of ways we can likely move forward to experiment with the existing SAT solver integration, and can think of ways we can get ahead by exploring ways to leverage the SAT solver on kdevops which can likely pave the way for its use also later in Linux.

We already carry a small delta on our kdevops kconfig to support yaml output which has proven invaluable to us, we can carry a SAT solver, as things settle with dynamic shell evaluation on Linux.

How can we leverage a SAT solver on kdevops?

1) Feature-driven configuration and scriptable goals

Instead of having the user do the heavy work on figuring out what the heck to enable on make menuconfig, the user just has to writes a requirement. Something like this:

ci-goal:
- filesystem: xfs
- features: [reflink, 4k]
- workload: sysbench-mysql-docker

This can also enable scriptable CI goals:

kconfig-solve --enable sysbench --fs xfs --blocksize 4k --reflink

Generates .config to let us test this.

2) Minimized configs to reproduce a test on our CI

Today if someone wants to reproduce a generic/750 test on xfs reflink 4k profile they can just use the web interface to select just the xfs_reflink_4k defconfig, and we have a kconfig option to let us limit the test to a set specified [0]. That requires adding a defconfig per test profile we support. Wouldn't it be nicer if we can just say:

ci-goal:
- filesystem: xfs
- features: [reflink, 4k]
- testsuite: fstests
- tests: generic/750

3) Generate a set of different tests for a goal

Given a set of features we want to test, we could have the SAT solver look for satisfiable combinations we could have

ci-goal:
- filesystem: xfs
- features: [reflink]
- workload: sysbench-mysql-docker

And so this may generate different .configs to help us run each one as a setup to test test XFS on mysql using docker using all XFS profiles.

Let me know if your team is interested in exploring these things.

[0] https://github.com/linux-kdevops/kdevops/blob/main/docs/kernel-ci/linux-filesystems-kdevops-CI-testing.md

Luis

#21 lore raw
Quoted 1 line · Luis Chamberlain

Let me know if your team is interested in exploring these things.

Hrm, actually there's much more...
Given we support all cloud providers...

This can also be something like:

matrix:
providers: [aws, gcp]
storage: [ebs, nvme]
filesystems: [xfs, ext4]
testsuites: [fstests]

If we could gather data about price...

- cost_limit: $0.50/hr

We then just need a mapping of code to tests.

code_paths:
fs/xfs/: [fstests, ltp, gitr]
block/: [blktets]

Ie, code maps to Kconfig attributes, and so we know what tests to run as code gets updated on each commit.

Luis

#22 lore raw
In reply to Masahiro Yamada
Quoted 26 lines · Masahiro Yamada
Quoted 25 lines · Luis Chamberlain
Quoted 4 lines · Masahiro Yamada

Thanks for this, but I have no plans to merge the SAT solver.

The reason is that my future plan is to move toolchain selection to the Kconfig stage instead of specifying it statically from the command line.

That makes sense.

Quoted 2 lines

This approach was suggested by Linus [1], and to achieve that, the shell evaluation must be dynamically re-evaluated [2].

Sure.

Quoted 2 lines

The SAT solver would likely conflict with this plan. At least due to the significant amount of additional code, which would be an obstacle.

I can't see how the toolchain selection, if set on Kconfig can't be leveraged later to enable / disable the SAT solver, however I can see the amount of code shuffling incurred to be an extra hurdle to address and a preference to leave that for later.

In other words, I susepct it is still possible to evaluate to add support for the SAT solver post toolchain kconfig integration.

Quoted 6 lines
Quoted 1 line

Thoughts?

It depends on how the dynamic shell evaluation is implemented. This is not limited to bool/tristate, but SAT solver only works for those two types.

I just wanted to clarify, configfix already supports string/int/hex values. Configfix uses SAT-variables that correspond to a kconfig-symbol being set to a specific value (e.g., one such variable would be NR_CPUS=1). The sample values for which such a variable is created are currently collected from default and range properties.

This collecting of sample values is going to be the main challenge of integrating configfix with dynamic shell evaluations. I believe the integration is feasible, but even if serious problems should arise, a decent alternative is to have configfix simply ignore the possibility of changing the symbol values that are inputs to or results of dynamic shell evaluations. That should amount to roughly the same capabilities as the current version without dynamic shell evaluations.

Best regards,
Ole Schuerks