[PATCH v4 05/12] kconfig: Add definitions

[Ole Schuerks]

We need to be able to store constraints for each symbol.
We therefore add several expressions for each such struct which we define
in a header-file.
Finally, we prepare the Makefile.

Co-developed-by: Patrick Franz <deltaone@xxxxxxxxxx>
Signed-off-by: Patrick Franz <deltaone@xxxxxxxxxx>
Co-developed-by: Ibrahim Fayaz <phayax@xxxxxxxxx>
Signed-off-by: Ibrahim Fayaz <phayax@xxxxxxxxx>
Reviewed-by: Luis Chamberlain <mcgrof@xxxxxxxxxx>
Tested-by: Evgeny Groshev <eugene.groshev@xxxxxxxxx>
Suggested-by: Sarah Nadi <nadi@xxxxxxxxxxx>
Suggested-by: Thorsten Berger <thorsten.berger@xxxxxx>
Signed-off-by: Thorsten Berger <thorsten.berger@xxxxxx>
Signed-off-by: Ole Schuerks <ole0811sch@xxxxxxxxx>
---
 scripts/kconfig/Makefile  |  13 +-
 scripts/kconfig/cf_defs.h | 287 ++++++++++++++++++++++++++++++++++++++
 scripts/kconfig/expr.h    |  17 +++
 3 files changed, 315 insertions(+), 2 deletions(-)
 create mode 100644 scripts/kconfig/cf_defs.h

diff --git a/scripts/kconfig/Makefile b/scripts/kconfig/Makefile
index a0a0be38cbdc..53461b609bd2 100644
--- a/scripts/kconfig/Makefile
+++ b/scripts/kconfig/Makefile
@@ -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
@@ -152,6 +153,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'
 	@echo  ''
 	@echo  'Configuration topic targets:'
 	@$(foreach f, $(all-config-fragments), \
@@ -196,10 +198,17 @@ $(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_rangefix.o cf_utils.o picosat.o
+cfoutconfig-objs := cfoutconfig.o $(common-objs) $(cfconf-objs)
+
+HOSTCFLAGS_picosat.o = -DTRACE -Wno-missing-prototypes -Wno-pointer-compare
+
 # 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)
diff --git a/scripts/kconfig/cf_defs.h b/scripts/kconfig/cf_defs.h
new file mode 100644
index 000000000000..8bfff7db5c33
--- /dev/null
+++ b/scripts/kconfig/cf_defs.h
@@ -0,0 +1,287 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * Copyright (C) 2023 Patrick Franz <deltaone@xxxxxxxxxx>
+ */
+
+#ifndef DEFS_H
+#define DEFS_H
+
+/* global variables */
+#include <limits.h>
+#include <stdbool.h>
+#include <stddef.h>
+
+#include "lkc.h"
+#include "expr.h"
+
+extern bool CFDEBUG;
+extern bool stop_rangefix;
+
+#define printd(fmt...) do { \
+	if (CFDEBUG) \
+		printf(fmt); \
+} while (0)
+
+/*
+ * For functions that construct nested pexpr expressions.
+ */
+enum pexpr_move {
+	PEXPR_ARG1,	/* put reference to first pexpr */
+	PEXPR_ARG2,	/* put reference to second pexpr */
+	PEXPR_ARGX	/* put all references to pexpr's */
+};
+
+
+/* different types for f_expr */
+enum fexpr_type {
+	FE_SYMBOL,
+	FE_NPC, /* no prompt condition */
+	FE_TRUE,  /* constant of value True */
+	FE_FALSE,  /* constant of value False */
+	FE_NONBOOL,  /* for all non-(boolean/tristate) known values */
+	FE_CHOICE, /* symbols of type choice */
+	FE_SELECT, /* auxiliary variable for selected symbols */
+	FE_TMPSATVAR /* temporary sat-variable (Tseytin) */
+};
+
+/* struct for a propositional logic formula */
+struct fexpr {
+	/* name of the feature expr */
+	struct gstr name;
+
+	/* associated symbol */
+	struct symbol *sym;
+
+	/* integer value for the SAT solver */
+	int satval;
+
+	/* assumption in the last call to PicoSAT */
+	bool assumption;
+
+	/* type of the fexpr */
+	enum fexpr_type type;
+
+	union {
+		/* symbol */
+		struct {
+			tristate tri;
+		};
+		/* EQUALS */
+		struct {
+			struct symbol *eqsym;
+			struct symbol *eqvalue;
+		};
+		/* HEX, INTEGER, STRING */
+		struct {
+			struct gstr nb_val;
+		};
+	};
+
+};
+
+struct fexpr_list {
+	struct fexpr_node *head, *tail;
+	unsigned int size;
+};
+
+struct fexpr_node {
+	struct fexpr *elem;
+	struct fexpr_node *next, *prev;
+};
+
+struct fexl_list {
+	struct fexl_node *head, *tail;
+	unsigned int size;
+};
+
+struct fexl_node {
+	struct fexpr_list *elem;
+	struct fexl_node *next, *prev;
+};
+
+enum pexpr_type {
+	PE_SYMBOL,
+	PE_AND,
+	PE_OR,
+	PE_NOT
+};
+
+union pexpr_data {
+	struct pexpr *pexpr;
+	struct fexpr *fexpr;
+};
+
+/**
+ * struct pexpr - a node in a tree representing a propositional formula
+ * @type: Type of the node
+ * @left: left-hand-side for AND and OR, the unique operand for NOT, and for
+ * SYMBOL it contains the fpexpr.
+ * @right: right-hand-side for AND and OR
+ * @ref_count: Number of calls to pexpr_put() that need to effectuated with this
+ * pexpr for it to get free'd.
+ *
+ * Functions that return new struct pexpr instances (like pexpr_or(),
+ * pexpr_or_share(), pexf(), ...) set @ref_count in a way that accounts for the
+ * new reference that they return (e.g. pexf() will always set it to 1).
+ * Functions with arguments of type ``struct pexpr *`` will generally keep the
+ * reference intact, so that for example
+ * ``e = pexf(sym); not_e = pexpr_not_share(e)`` would require
+ * ``pexpr_put(not_e)`` before not_e can be free'd and additionally
+ * ``pexpr_put(e)`` for e to get free'd. Some functions take an argument of type
+ * ``enum pexpr_move`` which function as a wrapper of sorts that first executes
+ * a function and then pexpr_put's the argument(s) specified by the
+ * ``enum pexpr_move`` argument (e.g. the normal function for OR is
+ * pexpr_or_share() and the wrapper is pexpr_or()).
+ */
+struct pexpr {
+	enum pexpr_type type;
+	union pexpr_data left, right;
+	unsigned int ref_count;
+};
+
+struct pexpr_list {
+	struct pexpr_node *head, *tail;
+	unsigned int size;
+};
+
+struct pexpr_node {
+	struct pexpr *elem;
+	struct pexpr_node *next, *prev;
+};
+
+/**
+ * struct default_map - Map entry from default values to their condition
+ * @val: value of the default property. Not 'owned' by this struct and
+ * therefore shouldn't be free'd.
+ * @e: condition that implies that the symbol assumes the @val. Needs to be
+ * pexpr_put when free'ing.
+ */
+struct default_map {
+	struct fexpr *val;
+	struct pexpr *e;
+};
+
+/**
+ * struct defm_list - Map from values of default properties of a symbol to their
+ * (accumulated) conditions
+ */
+struct defm_list {
+	struct defm_node *head, *tail;
+	unsigned int size;
+};
+
+struct defm_node {
+	struct default_map *elem;
+	struct defm_node *next, *prev;
+};
+
+enum symboldv_type {
+	SDV_BOOLEAN,	/* boolean/tristate */
+	SDV_NONBOOLEAN	/* string/int/hex */
+};
+
+struct symbol_dvalue {
+	struct symbol *sym;
+
+	enum symboldv_type type;
+
+	union {
+		/* boolean/tristate */
+		tristate tri;
+
+		/* string/int/hex */
+		struct gstr nb_val;
+	};
+};
+
+struct sdv_list {
+	struct sdv_node *head, *tail;
+	unsigned int size;
+};
+
+struct sdv_node {
+	struct symbol_dvalue *elem;
+	struct sdv_node *next, *prev;
+};
+
+enum symbolfix_type {
+	SF_BOOLEAN,	/* boolean/tristate */
+	SF_NONBOOLEAN,	/* string/int/hex */
+	SF_DISALLOWED	/* disallowed non-boolean values */
+};
+
+struct symbol_fix {
+	struct symbol *sym;
+
+	enum symbolfix_type type;
+
+	union {
+		/* boolean/tristate */
+		tristate tri;
+
+		/* string/int/hex */
+		struct gstr nb_val;
+
+		/* disallowed non-boolean values */
+		struct gstr disallowed;
+	};
+};
+
+struct sfix_list {
+	struct sfix_node *head, *tail;
+	unsigned int size;
+};
+
+struct sfix_node {
+	struct symbol_fix *elem;
+	struct sfix_node *next, *prev;
+};
+
+struct sfl_list {
+	struct sfl_node *head, *tail;
+	unsigned int size;
+};
+
+struct sfl_node {
+	struct sfix_list *elem;
+	struct sfl_node *next, *prev;
+};
+
+struct sym_list {
+	struct sym_node *head, *tail;
+	unsigned int size;
+};
+
+struct sym_node {
+	struct symbol *elem;
+	struct sym_node *next, *prev;
+};
+
+struct prop_list {
+	struct prop_node *head, *tail;
+	unsigned int size;
+};
+
+struct prop_node {
+	struct property *elem;
+	struct prop_node *next, *prev;
+};
+
+struct constants {
+	struct fexpr *const_false;
+	struct fexpr *const_true;
+	struct fexpr *symbol_yes_fexpr;
+	struct fexpr *symbol_mod_fexpr;
+	struct fexpr *symbol_no_fexpr;
+};
+
+struct cfdata {
+	unsigned int sat_variable_nr;
+	unsigned int tmp_variable_nr;
+	struct fexpr **satmap; // map SAT variables to fexpr
+	size_t satmap_size;
+	struct constants *constants;
+	struct sdv_list *sdv_symbols; // array with conflict-symbols
+};
+
+#endif
diff --git a/scripts/kconfig/expr.h b/scripts/kconfig/expr.h
index 8849a243b5e7..2582e948f4eb 100644
--- a/scripts/kconfig/expr.h
+++ b/scripts/kconfig/expr.h
@@ -127,6 +127,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; /* used for non-booleans */
+	struct pexpr_list *constraints; /* list of constraints for symbol */
 };
 
 #define SYMBOL_CONST      0x0001  /* symbol is const */
@@ -190,6 +203,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)
-- 
2.39.2