[LTP] [PATCH v2 0/2] Add support for kconfig constraints

[LTP] [PATCH v2 0/2] Add support for kconfig constraints

[Cyril Hrubis]

This patchset adds a support for generic boolean expressions in order to
be able to check for a more complex kernel configurations.

The motivation for this is recent rename in kernel config names that
cannot be checked for by a simplistic approach we previously
implemented.

The boolean expression parser was written as a generic as possible since
I do expect that we will reuse it for different types of assertions in
the future.

Cyril Hrubis (2):
  lib: Add generic boolean expression parser and eval
  lib/tst_kconfig: Make use of boolean expression eval

 doc/test-writing-guidelines.txt  |  21 +-
 include/tst_bool_expr.h          |  80 ++++++
 include/tst_kconfig.h            |  34 +--
 lib/newlib_tests/.gitignore      |   1 +
 lib/newlib_tests/config06        |   1 +
 lib/newlib_tests/test_kconfig.c  |   1 +
 lib/newlib_tests/tst_bool_expr.c | 128 ++++++++++
 lib/tst_bool_expr.c              | 425 +++++++++++++++++++++++++++++++
 lib/tst_kconfig.c                | 362 +++++++++++++++++---------
 9 files changed, 904 insertions(+), 149 deletions(-)
 create mode 100644 include/tst_bool_expr.h
 create mode 100644 lib/newlib_tests/config06
 create mode 100644 lib/newlib_tests/tst_bool_expr.c
 create mode 100644 lib/tst_bool_expr.c

-- 
2.26.2

[LTP] [PATCH v2 1/2] lib: Add generic boolean expression parser and eval

[Cyril Hrubis]

Add a simple and generic boolean expression parser and evaluator. This
is a second step in order to implement more complex kconfig expressions,
but since we are likely to reuse the parser for other purposes in the
future it's implemented as a generic boolean parser.

Signed-off-by: Cyril Hrubis <chrubis@suse.cz>
---

v2:
   - use pointer to the original string + lenght instead of allocation
   - simplified the code a bit
   - renamed a few fucntions and identifiers to make the code easier to
     understand

 include/tst_bool_expr.h          |  80 ++++++
 lib/newlib_tests/.gitignore      |   1 +
 lib/newlib_tests/tst_bool_expr.c | 128 ++++++++++
 lib/tst_bool_expr.c              | 425 +++++++++++++++++++++++++++++++
 4 files changed, 634 insertions(+)
 create mode 100644 include/tst_bool_expr.h
 create mode 100644 lib/newlib_tests/tst_bool_expr.c
 create mode 100644 lib/tst_bool_expr.c

diff --git a/include/tst_bool_expr.h b/include/tst_bool_expr.h
new file mode 100644
index 000000000..cafad3b00
--- /dev/null
+++ b/include/tst_bool_expr.h
@@ -0,0 +1,80 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Copyright (c) 2020 Cyril Hrubis <chrubis@suse.cz>
+ */
+
+#ifndef TST_BOOL_EXPR_H__
+#define TST_BOOL_EXPR_H__
+
+enum tst_op {
+	TST_OP_NOT,
+	TST_OP_AND,
+	TST_OP_OR,
+	TST_OP_VAR,
+	/* Used only internally */
+	TST_OP_LPAR,
+	TST_OP_RPAR,
+};
+
+struct tst_expr {
+	enum tst_op op;
+	const char *tok;
+	size_t tok_len;
+	struct tst_expr *next;
+	const void *priv;
+};
+
+/*
+ * Parses an boolean expression and returns a simplified RPN version.
+ *
+ * If expression is not valid the call prints error into stderr and returns
+ * NULL. On success pointer to an expression is returned which can be evaluated
+ * by the tst_bool_expr_eval() function and has to be later freed by the
+ * caller.
+ *
+ * The boolean expression can consists of:
+ *
+ * - unary negation opeartion !
+ * - two binary operations & and |
+ * - correct sequence of parentheses ()
+ * - strings that are treated as boolean variables
+ *
+ *  e.g. '(A | B) & C' or 'Variable_1 & Variable_2' are both a valid boolean
+ *  expressions.
+ *
+ *  @expr String containing a boolean expression to be parsed.
+ *  @return Pointer to an RPN expression.
+ */
+struct tst_expr *tst_bool_expr_parse(const char *expr);
+
+/*
+ * Prints an string representation of the expression into a FILE.
+ *
+ * @param A FILE to print to.
+ * @expr An expression to print.
+ */
+void tst_bool_expr_print(FILE *f, struct tst_expr *expr);
+
+/*
+ * Evaluates an expression given a map for variables.
+ *
+ * The call will fail if:
+ * - map function returns -1 which indicates undefined variable
+ * - the eval function runs out of stack
+ *
+ * @param expr Boolean expression in RPN.
+ * @param map Mapping function for boolean variables.
+ *
+ * @return Returns 0 or 1 if expression was evaluated correctly and -1 on error.
+ */
+int tst_bool_expr_eval(struct tst_expr *expr,
+                       int (*map)(struct tst_expr *var));
+
+/*
+ * Frees the memory allocated by the tst_bool_expr_parse().
+ *
+ * @param Boolean expression.
+ */
+void tst_bool_expr_free(struct tst_expr *expr);
+
+#endif	/* TST_BOOL_EXPR_H__ */
diff --git a/lib/newlib_tests/.gitignore b/lib/newlib_tests/.gitignore
index 44bc6526f..1e96db1da 100644
--- a/lib/newlib_tests/.gitignore
+++ b/lib/newlib_tests/.gitignore
@@ -33,3 +33,4 @@ test_exec_child
 test_kconfig
 variant
 test_guarded_buf
+tst_bool_expr
diff --git a/lib/newlib_tests/tst_bool_expr.c b/lib/newlib_tests/tst_bool_expr.c
new file mode 100644
index 000000000..49948d85f
--- /dev/null
+++ b/lib/newlib_tests/tst_bool_expr.c
@@ -0,0 +1,128 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Copyright (c) 2017 Cyril Hrubis <chrubis@suse.cz>
+ */
+
+/*
+ * Basic unit test for the bolean expression parser and evaluator.
+ */
+
+#include <string.h>
+#include <stdio.h>
+#include "tst_test.h"
+#include "tst_bool_expr.h"
+
+static int a, b, c;
+
+static int map(struct tst_expr *var)
+{
+	if (!strncmp(var->tok, "A", var->tok_len))
+		return a;
+
+	if (!strncmp(var->tok, "B", var->tok_len))
+		return b;
+
+	if (!strncmp(var->tok, "C", var->tok_len))
+		return c;
+
+	if (!strncmp(var->tok, "True", var->tok_len))
+		return 1;
+
+	if (!strncmp(var->tok, "False", var->tok_len))
+		return 0;
+
+	return -1;
+}
+
+static void parse_fail(const char *expr)
+{
+	struct tst_expr *res;
+
+	tst_res(TINFO, "Parsing '%s'", expr);
+
+	res = tst_bool_expr_parse(expr);
+
+	if (res) {
+		printf("In RPN: ");
+		tst_bool_expr_print(stdout, res);
+		printf("\n");
+		tst_bool_expr_free(res);
+		tst_res(TFAIL, "Expression was parsed");
+	} else {
+		tst_res(TPASS, "Parser returned an error");
+	}
+}
+
+static void do_eval_test(const char *expr_str, int set_a, int set_b, int set_c, int exp_res)
+{
+	struct tst_expr *expr;
+	int res;
+
+	a = set_a;
+	b = set_b;
+	c = set_c;
+
+	tst_res(TINFO, "'%s' A=%i B=%i C=%i == %i", expr_str, a, b, c, exp_res);
+
+	expr = tst_bool_expr_parse(expr_str);
+
+	if (!expr) {
+		tst_res(TFAIL, "Parser returned error");
+		return;
+	}
+
+	printf("In RPN: ");
+	tst_bool_expr_print(stdout, expr);
+	printf("\n");
+
+	res = tst_bool_expr_eval(expr, map);
+
+	if (res == exp_res)
+		tst_res(TPASS, "Got %i", res);
+	else
+		tst_res(TFAIL, "Got %i", res);
+
+	tst_bool_expr_free(expr);
+}
+
+static void do_test(void)
+{
+	do_eval_test("(A | B) & !!C", 0, 0, 0, 0);
+	do_eval_test("(A | B) & !!C", 1, 0, 1, 1);
+	do_eval_test("!A & B", 1, 0, 0, 0);
+	do_eval_test("!A & B", 0, 1, 0, 1);
+	do_eval_test("A & !B", 1, 0, 0, 1);
+	do_eval_test("!!A & !!B", 0, 1, 0, 0);
+	do_eval_test("!!A & !!B", 1, 1, 0, 1);
+	do_eval_test("!(A & B) & C", 1, 1, 0, 0);
+	do_eval_test("A & (B | C)", 1, 1, 0, 1);
+	do_eval_test("A & B | C", 1, 1, 0, 1);
+	do_eval_test("((((A)))&(B))", 1, 1, 0, 1);
+	do_eval_test("   A  \t", 0, 0, 0, 0);
+	do_eval_test("False & A", 1, 0, 0, 0);
+	do_eval_test("! Undefined", 0, 0, 0, -1);
+
+	parse_fail("A!");
+	parse_fail("A &");
+	parse_fail("A B");
+	parse_fail("A ) B");
+	parse_fail("A ( B");
+	parse_fail("A ( B )");
+	parse_fail("A |");
+	parse_fail("A ! B");
+	parse_fail("A! & B");
+	parse_fail("A & | B");
+	parse_fail("A & (B |)");
+	parse_fail("A & ( | B)");
+	parse_fail("A & B &");
+	parse_fail("((A )");
+	parse_fail("& A");
+	parse_fail("! &");
+	parse_fail(")");
+	parse_fail("| A");
+	parse_fail("");
+}
+
+static struct tst_test test = {
+	.test_all = do_test,
+};
diff --git a/lib/tst_bool_expr.c b/lib/tst_bool_expr.c
new file mode 100644
index 000000000..fbcc74c82
--- /dev/null
+++ b/lib/tst_bool_expr.c
@@ -0,0 +1,425 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Copyright (c) 2020 Cyril Hrubis <chrubis@suse.cz>
+ */
+/*
+ * Boolean expression is evaluated in three steps.
+ *
+ * First of all the string containing the expression is tokenized.
+ *
+ * Secondly the the expression is transformed to a postfix (RPN) notation by
+ * the shunting yard algorithm and the correctness of the expression is checked
+ * during the transformation as well. The fact that parenthesis are matched is
+ * asserted by the shunting yard algorithm itself while the rest is checked
+ * simply by checking if the preceding token is in a set of allowed tokens.
+ * This could be thought of as a simple open-coded state machine.
+ *
+ * An expression in the RPN form can be evaluated given a variable mapping
+ * function. The evaluation ignores most of errors because invalid expression
+ * will be rejected in the second step.
+ */
+
+#include <string.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include "tst_bool_expr.h"
+
+struct tok_list {
+	struct tst_expr *first;
+	struct tst_expr *last;
+	unsigned int cnt;
+};
+
+static void tok_list_append(struct tok_list *list, struct tst_expr *val)
+{
+	if (!val)
+		return;
+
+	if (!list->first)
+		list->first = val;
+
+	if (list->last)
+		list->last->next = val;
+
+	list->last = val;
+
+	list->cnt++;
+}
+
+static int char_to_op(char c)
+{
+	switch (c) {
+	case '(':
+		return TST_OP_LPAR;
+	case ')':
+		return TST_OP_RPAR;
+	case '&':
+		return TST_OP_AND;
+	case '|':
+		return TST_OP_OR;
+	case '!':
+		return TST_OP_NOT;
+	default:
+		return TST_OP_VAR;
+	}
+}
+
+static struct tst_expr *tok_alloc(const char *tok, size_t tok_len)
+{
+	struct tst_expr *ret;
+
+	if (!tok_len)
+		return NULL;
+
+	ret = malloc(sizeof(struct tst_expr));
+	if (!ret)
+		return NULL;
+
+	memset(ret, 0, sizeof(*ret));
+
+	ret->tok = tok;
+	ret->tok_len = tok_len;
+	ret->op = char_to_op(ret->tok[0]);
+
+	return ret;
+}
+
+static void tokenize(const char *expr, struct tok_list *ret)
+{
+	size_t i, j;
+
+	for (j = i = 0; expr[i]; i++) {
+		switch (expr[i]) {
+		case '(':
+		case ')':
+		case '!':
+		case '&':
+		case '|':
+			tok_list_append(ret, tok_alloc(&expr[j], i - j));
+			tok_list_append(ret, tok_alloc(&expr[i], 1));
+			j = i+1;
+		break;
+		case '\t':
+		case ' ':
+			tok_list_append(ret, tok_alloc(&expr[j], i - j));
+			j = i+1;
+		break;
+		default:
+		break;
+		}
+	}
+
+	tok_list_append(ret, tok_alloc(&expr[j], i - j));
+}
+
+void tst_bool_expr_print(FILE *f, struct tst_expr *expr)
+{
+	struct tst_expr *i;
+	size_t j;
+
+	for (i = expr; i; i = i->next) {
+		for (j = 0; j < i->tok_len; j++)
+			putc(i->tok[j], f);
+
+		if (i->next)
+			putc(' ', f);
+	}
+}
+
+static void tst_bool_expr_err(FILE *f, struct tst_expr *expr)
+{
+	struct tst_expr *i;
+	unsigned int spaces = 0;
+
+	fprintf(f, "%s", expr->tok);
+	fprintf(f, "\n");
+
+	for (i = expr; i; i = i->next) {
+		if (i->priv)
+			break;
+	}
+
+	spaces = i->tok - expr->tok;
+
+	while (spaces--)
+		putc(' ', f);
+
+	fprintf(f, "^\n");
+	fprintf(f, "%s\n", (const char *)i->priv);
+}
+
+static inline void stack_push(struct tst_expr *stack[], unsigned int *op_stack_pos,
+                              struct tst_expr *op)
+{
+	stack[(*op_stack_pos)++] = op;
+}
+
+static inline int stack_empty(unsigned int op_stack_pos)
+{
+	return op_stack_pos == 0;
+}
+
+static inline struct tst_expr *stack_pop(struct tst_expr *stack[],
+                                          unsigned int *op_stack_pos)
+{
+	if (stack_empty(*op_stack_pos))
+		return NULL;
+
+	return stack[--(*op_stack_pos)];
+}
+
+#define TST_OP_NONE -1
+
+static inline int stack_peek_op(struct tst_expr *stack[],
+                                unsigned int op_stack_pos)
+{
+	if (stack_empty(op_stack_pos))
+		return TST_OP_NONE;
+
+	return stack[op_stack_pos - 1]->op;
+}
+
+/*
+ * This is a complete list of which tokens can happen before any of:
+ *  - variable
+ *  - left parentesis
+ *  - negation
+ *
+ * The -1 represents start of the expression.
+ */
+static inline int check_one(int op)
+{
+	switch (op) {
+	case TST_OP_AND:
+	case TST_OP_OR:
+	case TST_OP_NOT:
+	case TST_OP_NONE:
+	case TST_OP_LPAR:
+		return 0;
+	default:
+		return 1;
+	}
+}
+
+/*
+ * And this checks for tokens that can happen before any of:
+ * - right parentesis
+ * - and
+ * - or
+ *
+ * This is also used to check that the last token in expression is correct one.
+ */
+static inline int check_two(int op)
+{
+	switch (op) {
+	case TST_OP_VAR:
+	case TST_OP_RPAR:
+		return 1;
+	default:
+		return 0;
+	}
+}
+
+/*
+ * Note that we avoid modifying the list until the end so that the caller can
+ * free memory correctly, which is the reason we have a stack for parentesis
+ * that are just freed at the end.
+ */
+static struct tst_expr *shunting_yard(struct tok_list *list)
+{
+	struct tst_expr *op_stack[list->cnt];
+	unsigned int op_stack_pos = 0;
+	struct tst_expr *out[list->cnt + 1];
+	unsigned int out_pos = 0;
+	struct tst_expr *pars[list->cnt];
+	unsigned int pars_pos = 0;
+	struct tst_expr *i;
+	unsigned int j;
+	int prev_op = TST_OP_NONE;
+
+	for (i = list->first; i; i = i->next) {
+		switch (i->op) {
+		case TST_OP_VAR:
+			if (check_one(prev_op)) {
+				i->priv = "Expected operation";
+				goto err;
+			}
+
+			stack_push(out, &out_pos, i);
+
+			while (stack_peek_op(op_stack, op_stack_pos) == TST_OP_NOT)
+				stack_push(out, &out_pos, stack_pop(op_stack, &op_stack_pos));
+		break;
+		case TST_OP_LPAR:
+			if (check_one(prev_op)) {
+				i->priv = "Expected operation";
+				goto err;
+			}
+
+			stack_push(op_stack, &op_stack_pos, i);
+		break;
+		case TST_OP_RPAR:
+			if (!check_two(prev_op)) {
+				i->priv = "Expected variable or )";
+				goto err;
+			}
+
+			stack_push(pars, &pars_pos, i);
+
+			/* pop everything till ( */
+			for (;;) {
+				struct tst_expr *op = stack_pop(op_stack, &op_stack_pos);
+
+				if (!op) {
+					i->priv = "Missing (";
+					goto err;
+				}
+
+				if (op->op == TST_OP_LPAR) {
+					stack_push(pars, &pars_pos, op);
+					break;
+				}
+
+				stack_push(out, &out_pos, op);
+			}
+
+			while (stack_peek_op(op_stack, op_stack_pos) == TST_OP_NOT)
+				stack_push(out, &out_pos, stack_pop(op_stack, &op_stack_pos));
+		break;
+		case TST_OP_NOT:
+			if (check_one(prev_op)) {
+				i->priv = "Expected operation";
+				goto err;
+			}
+			stack_push(op_stack, &op_stack_pos, i);
+		break;
+		case TST_OP_AND:
+		case TST_OP_OR:
+			if (!check_two(prev_op)) {
+				i->priv = "Expected variable or (";
+				goto err;
+			}
+
+			/*
+			 * There can be at most one binary op on the stack
+			 * since we pop the one present on the stack before we
+			 * attempt to push new one they never accumulate.
+			 */
+			switch (stack_peek_op(op_stack, op_stack_pos)) {
+			case TST_OP_AND:
+			case TST_OP_OR:
+				stack_push(out, &out_pos, stack_pop(op_stack, &op_stack_pos));
+			break;
+			}
+
+			stack_push(op_stack, &op_stack_pos, i);
+		break;
+		}
+
+		prev_op = i->op;
+	}
+
+	if (!check_two(list->last->op)) {
+		list->last->priv = "Unfinished expression";
+		goto err;
+	}
+
+	/* pop remaining operations */
+	while ((i = stack_pop(op_stack, &op_stack_pos))) {
+		if (i->op == TST_OP_LPAR) {
+			i->priv = "Missing )";
+			goto err;
+		}
+
+		stack_push(out, &out_pos, i);
+	}
+
+	/* free parentesis */
+	for (j = 0; j < pars_pos; j++)
+		free(pars[j]);
+
+	/* reconstruct the list */
+	out[out_pos] = NULL;
+
+	for (j = 0; j < out_pos; j++)
+		out[j]->next = out[j + 1];
+
+	return out[0];
+err:
+	return NULL;
+}
+
+struct tst_expr *tst_bool_expr_parse(const char *expr)
+{
+	struct tok_list list = {};
+	struct tst_expr *ret;
+
+	tokenize(expr, &list);
+
+	if (!list.first)
+		return NULL;
+
+	ret = shunting_yard(&list);
+
+	if (!ret) {
+		tst_bool_expr_err(stderr, list.first);
+		tst_bool_expr_free(list.first);
+		return NULL;
+	}
+
+	return ret;
+}
+
+#define MAX_STACK 16
+
+int tst_bool_expr_eval(struct tst_expr *expr,
+                       int (*map)(struct tst_expr *var))
+{
+	struct tst_expr *i;
+	int stack[MAX_STACK];
+	int pos = -1;
+
+	for (i = expr; i; i = i->next) {
+		switch (i->op) {
+		case TST_OP_NOT:
+			stack[pos] = !stack[pos];
+		break;
+		case TST_OP_OR:
+			stack[pos-1] = stack[pos] || stack[pos-1];
+			pos--;
+		break;
+		case TST_OP_AND:
+			stack[pos-1] = stack[pos] && stack[pos-1];
+			pos--;
+		break;
+		case TST_OP_VAR:
+			if (pos + 1 >= MAX_STACK) {
+				fprintf(stderr, "Eval out of stack!\n");
+				return -1;
+			}
+
+			stack[++pos] = map(i);
+
+			/* map reported undefined variable -> abort */
+			if (stack[pos] == -1)
+				return -1;
+		break;
+		/* does not happen */
+		default:
+		break;
+		}
+	}
+
+	return stack[0];
+}
+
+void tst_bool_expr_free(struct tst_expr *expr)
+{
+	struct tst_expr *i = expr, *tmp;
+
+	while (i) {
+		tmp = i;
+		i = i->next;
+		free(tmp);
+	}
+}
-- 
2.26.2

[LTP] [PATCH v2 1/2] lib: Add generic boolean expression parser and eval

[Richard Palethorpe]

Cyril Hrubis <chrubis@suse.cz> writes:

> Add a simple and generic boolean expression parser and evaluator. This
> is a second step in order to implement more complex kconfig expressions,
> but since we are likely to reuse the parser for other purposes in the
> future it's implemented as a generic boolean parser.
>
> Signed-off-by: Cyril Hrubis <chrubis@suse.cz>

Still have some comments below, but am very happy with this:
Reviewed-by: Richard Palethorpe <rpalethorpe@suse.com>

> ---
>
> v2:
>    - use pointer to the original string + lenght instead of allocation
>    - simplified the code a bit
>    - renamed a few fucntions and identifiers to make the code easier to
>      understand
>
>  include/tst_bool_expr.h          |  80 ++++++
>  lib/newlib_tests/.gitignore      |   1 +
>  lib/newlib_tests/tst_bool_expr.c | 128 ++++++++++
>  lib/tst_bool_expr.c              | 425 +++++++++++++++++++++++++++++++
>  4 files changed, 634 insertions(+)
>  create mode 100644 include/tst_bool_expr.h
>  create mode 100644 lib/newlib_tests/tst_bool_expr.c
>  create mode 100644 lib/tst_bool_expr.c
>
> diff --git a/include/tst_bool_expr.h b/include/tst_bool_expr.h
> new file mode 100644
> index 000000000..cafad3b00
> --- /dev/null
> +++ b/include/tst_bool_expr.h
> @@ -0,0 +1,80 @@
> +// SPDX-License-Identifier: GPL-2.0-or-later
> +/*
> + * Copyright (c) 2020 Cyril Hrubis <chrubis@suse.cz>
> + */
> +
> +#ifndef TST_BOOL_EXPR_H__
> +#define TST_BOOL_EXPR_H__
> +
> +enum tst_op {
> +	TST_OP_NOT,
> +	TST_OP_AND,
> +	TST_OP_OR,
> +	TST_OP_VAR,
> +	/* Used only internally */
> +	TST_OP_LPAR,
> +	TST_OP_RPAR,
> +};
> +
> +struct tst_expr {
> +	enum tst_op op;
> +	const char *tok;
> +	size_t tok_len;
> +	struct tst_expr *next;
> +	const void *priv;
> +};
> +
> +/*
> + * Parses an boolean expression and returns a simplified RPN version.
> + *
> + * If expression is not valid the call prints error into stderr and returns
> + * NULL. On success pointer to an expression is returned which can be evaluated
> + * by the tst_bool_expr_eval() function and has to be later freed by the
> + * caller.
> + *
> + * The boolean expression can consists of:
> + *
> + * - unary negation opeartion !
> + * - two binary operations & and |
> + * - correct sequence of parentheses ()
> + * - strings that are treated as boolean variables
> + *
> + *  e.g. '(A | B) & C' or 'Variable_1 & Variable_2' are both a valid boolean
> + *  expressions.
> + *
> + *  @expr String containing a boolean expression to be parsed.
> + *  @return Pointer to an RPN expression.
> + */
> +struct tst_expr *tst_bool_expr_parse(const char *expr);
> +
> +/*
> + * Prints an string representation of the expression into a FILE.
> + *
> + * @param A FILE to print to.
> + * @expr An expression to print.
> + */
> +void tst_bool_expr_print(FILE *f, struct tst_expr *expr);
> +
> +/*
> + * Evaluates an expression given a map for variables.
> + *
> + * The call will fail if:
> + * - map function returns -1 which indicates undefined variable
> + * - the eval function runs out of stack
> + *
> + * @param expr Boolean expression in RPN.
> + * @param map Mapping function for boolean variables.
> + *
> + * @return Returns 0 or 1 if expression was evaluated correctly and -1 on error.
> + */
> +int tst_bool_expr_eval(struct tst_expr *expr,
> +                       int (*map)(struct tst_expr *var));
> +
> +/*
> + * Frees the memory allocated by the tst_bool_expr_parse().
> + *
> + * @param Boolean expression.
> + */
> +void tst_bool_expr_free(struct tst_expr *expr);
> +
> +#endif	/* TST_BOOL_EXPR_H__ */
> diff --git a/lib/newlib_tests/.gitignore b/lib/newlib_tests/.gitignore
> index 44bc6526f..1e96db1da 100644
> --- a/lib/newlib_tests/.gitignore
> +++ b/lib/newlib_tests/.gitignore
> @@ -33,3 +33,4 @@ test_exec_child
>  test_kconfig
>  variant
>  test_guarded_buf
> +tst_bool_expr
> diff --git a/lib/newlib_tests/tst_bool_expr.c b/lib/newlib_tests/tst_bool_expr.c
> new file mode 100644
> index 000000000..49948d85f
> --- /dev/null
> +++ b/lib/newlib_tests/tst_bool_expr.c
> @@ -0,0 +1,128 @@
> +// SPDX-License-Identifier: GPL-2.0-or-later
> +/*
> + * Copyright (c) 2017 Cyril Hrubis <chrubis@suse.cz>
> + */
> +
> +/*
> + * Basic unit test for the bolean expression parser and evaluator.
> + */
> +
> +#include <string.h>
> +#include <stdio.h>
> +#include "tst_test.h"
> +#include "tst_bool_expr.h"
> +
> +static int a, b, c;
> +
> +static int map(struct tst_expr *var)
> +{
> +	if (!strncmp(var->tok, "A", var->tok_len))
> +		return a;
> +
> +	if (!strncmp(var->tok, "B", var->tok_len))
> +		return b;
> +
> +	if (!strncmp(var->tok, "C", var->tok_len))
> +		return c;
> +
> +	if (!strncmp(var->tok, "True", var->tok_len))
> +		return 1;
> +
> +	if (!strncmp(var->tok, "False", var->tok_len))
> +		return 0;
> +
> +	return -1;
> +}
> +
> +static void parse_fail(const char *expr)
> +{
> +	struct tst_expr *res;
> +
> +	tst_res(TINFO, "Parsing '%s'", expr);
> +
> +	res = tst_bool_expr_parse(expr);
> +
> +	if (res) {
> +		printf("In RPN: ");
> +		tst_bool_expr_print(stdout, res);
> +		printf("\n");
> +		tst_bool_expr_free(res);
> +		tst_res(TFAIL, "Expression was parsed");
> +	} else {
> +		tst_res(TPASS, "Parser returned an error");
> +	}
> +}
> +
> +static void do_eval_test(const char *expr_str, int set_a, int set_b, int set_c, int exp_res)
> +{
> +	struct tst_expr *expr;
> +	int res;
> +
> +	a = set_a;
> +	b = set_b;
> +	c = set_c;
> +
> +	tst_res(TINFO, "'%s' A=%i B=%i C=%i == %i", expr_str, a, b, c, exp_res);
> +
> +	expr = tst_bool_expr_parse(expr_str);
> +
> +	if (!expr) {
> +		tst_res(TFAIL, "Parser returned error");
> +		return;
> +	}
> +
> +	printf("In RPN: ");
> +	tst_bool_expr_print(stdout, expr);
> +	printf("\n");
> +
> +	res = tst_bool_expr_eval(expr, map);
> +
> +	if (res == exp_res)
> +		tst_res(TPASS, "Got %i", res);
> +	else
> +		tst_res(TFAIL, "Got %i", res);
> +
> +	tst_bool_expr_free(expr);
> +}
> +
> +static void do_test(void)
> +{
> +	do_eval_test("(A | B) & !!C", 0, 0, 0, 0);
> +	do_eval_test("(A | B) & !!C", 1, 0, 1, 1);
> +	do_eval_test("!A & B", 1, 0, 0, 0);
> +	do_eval_test("!A & B", 0, 1, 0, 1);
> +	do_eval_test("A & !B", 1, 0, 0, 1);
> +	do_eval_test("!!A & !!B", 0, 1, 0, 0);
> +	do_eval_test("!!A & !!B", 1, 1, 0, 1);
> +	do_eval_test("!(A & B) & C", 1, 1, 0, 0);
> +	do_eval_test("A & (B | C)", 1, 1, 0, 1);
> +	do_eval_test("A & B | C", 1, 1, 0, 1);
> +	do_eval_test("((((A)))&(B))", 1, 1, 0, 1);
> +	do_eval_test("   A  \t", 0, 0, 0, 0);
> +	do_eval_test("False & A", 1, 0, 0, 0);
> +	do_eval_test("! Undefined", 0, 0, 0, -1);
> +
> +	parse_fail("A!");
> +	parse_fail("A &");
> +	parse_fail("A B");
> +	parse_fail("A ) B");
> +	parse_fail("A ( B");
> +	parse_fail("A ( B )");
> +	parse_fail("A |");
> +	parse_fail("A ! B");
> +	parse_fail("A! & B");
> +	parse_fail("A & | B");
> +	parse_fail("A & (B |)");
> +	parse_fail("A & ( | B)");
> +	parse_fail("A & B &");
> +	parse_fail("((A )");
> +	parse_fail("& A");
> +	parse_fail("! &");
> +	parse_fail(")");
> +	parse_fail("| A");
> +	parse_fail("");
> +}
> +
> +static struct tst_test test = {
> +	.test_all = do_test,
> +};
> diff --git a/lib/tst_bool_expr.c b/lib/tst_bool_expr.c
> new file mode 100644
> index 000000000..fbcc74c82
> --- /dev/null
> +++ b/lib/tst_bool_expr.c
> @@ -0,0 +1,425 @@
> +// SPDX-License-Identifier: GPL-2.0-or-later
> +/*
> + * Copyright (c) 2020 Cyril Hrubis <chrubis@suse.cz>
> + */
> +/*
> + * Boolean expression is evaluated in three steps.
> + *
> + * First of all the string containing the expression is tokenized.
> + *
> + * Secondly the the expression is transformed to a postfix (RPN) notation by
> + * the shunting yard algorithm and the correctness of the expression is checked
> + * during the transformation as well. The fact that parenthesis are matched is
> + * asserted by the shunting yard algorithm itself while the rest is checked
> + * simply by checking if the preceding token is in a set of allowed tokens.
> + * This could be thought of as a simple open-coded state machine.
> + *
> + * An expression in the RPN form can be evaluated given a variable mapping
> + * function. The evaluation ignores most of errors because invalid expression
> + * will be rejected in the second step.
> + */
> +
> +#include <string.h>
> +#include <stdlib.h>
> +#include <stdio.h>
> +#include "tst_bool_expr.h"
> +
> +struct tok_list {
> +	struct tst_expr *first;
> +	struct tst_expr *last;
> +	unsigned int cnt;
> +};
> +
> +static void tok_list_append(struct tok_list *list, struct tst_expr *val)
> +{
> +	if (!val)
> +		return;
> +
> +	if (!list->first)
> +		list->first = val;
> +
> +	if (list->last)
> +		list->last->next = val;
> +
> +	list->last = val;
> +
> +	list->cnt++;
> +}
> +
> +static int char_to_op(char c)
> +{
> +	switch (c) {
> +	case '(':
> +		return TST_OP_LPAR;
> +	case ')':
> +		return TST_OP_RPAR;
> +	case '&':
> +		return TST_OP_AND;
> +	case '|':
> +		return TST_OP_OR;
> +	case '!':
> +		return TST_OP_NOT;
> +	default:
> +		return TST_OP_VAR;
> +	}
> +}
> +
> +static struct tst_expr *tok_alloc(const char *tok, size_t tok_len)
> +{
> +	struct tst_expr *ret;
> +
> +	if (!tok_len)
> +		return NULL;
> +
> +	ret = malloc(sizeof(struct tst_expr));
> +	if (!ret)
> +		return NULL;
> +
> +	memset(ret, 0, sizeof(*ret));
> +
> +	ret->tok = tok;
> +	ret->tok_len = tok_len;
> +	ret->op = char_to_op(ret->tok[0]);
> +
> +	return ret;
> +}
> +
> +static void tokenize(const char *expr, struct tok_list *ret)
> +{
> +	size_t i, j;
> +
> +	for (j = i = 0; expr[i]; i++) {
> +		switch (expr[i]) {
> +		case '(':
> +		case ')':
> +		case '!':
> +		case '&':
> +		case '|':
> +			tok_list_append(ret, tok_alloc(&expr[j], i - j));
> +			tok_list_append(ret, tok_alloc(&expr[i], 1));
> +			j = i+1;
> +		break;
> +		case '\t':
> +		case ' ':
> +			tok_list_append(ret, tok_alloc(&expr[j], i - j));
> +			j = i+1;
> +		break;
> +		default:
> +		break;
> +		}
> +	}
> +
> +	tok_list_append(ret, tok_alloc(&expr[j], i - j));
> +}
> +
> +void tst_bool_expr_print(FILE *f, struct tst_expr *expr)
> +{
> +	struct tst_expr *i;
> +	size_t j;
> +
> +	for (i = expr; i; i = i->next) {
> +		for (j = 0; j < i->tok_len; j++)
> +			putc(i->tok[j], f);
> +
> +		if (i->next)
> +			putc(' ', f);
> +	}
> +}
> +
> +static void tst_bool_expr_err(FILE *f, struct tst_expr *expr)
> +{
> +	struct tst_expr *i;
> +	unsigned int spaces = 0;
> +
> +	fprintf(f, "%s", expr->tok);
> +	fprintf(f, "\n");
> +
> +	for (i = expr; i; i = i->next) {
> +		if (i->priv)
> +			break;
> +	}
> +
> +	spaces = i->tok - expr->tok;
> +
> +	while (spaces--)
> +		putc(' ', f);
> +
> +	fprintf(f, "^\n");
> +	fprintf(f, "%s\n", (const char *)i->priv);
> +}
> +
> +static inline void stack_push(struct tst_expr *stack[], unsigned int *op_stack_pos,
> +                              struct tst_expr *op)
> +{
> +	stack[(*op_stack_pos)++] = op;
> +}
> +
> +static inline int stack_empty(unsigned int op_stack_pos)
> +{
> +	return op_stack_pos == 0;
> +}
> +
> +static inline struct tst_expr *stack_pop(struct tst_expr *stack[],
> +                                          unsigned int *op_stack_pos)
> +{
> +	if (stack_empty(*op_stack_pos))
> +		return NULL;
> +
> +	return stack[--(*op_stack_pos)];
> +}
> +
> +#define TST_OP_NONE -1
> +
> +static inline int stack_peek_op(struct tst_expr *stack[],
> +                                unsigned int op_stack_pos)
> +{
> +	if (stack_empty(op_stack_pos))
> +		return TST_OP_NONE;
> +
> +	return stack[op_stack_pos - 1]->op;
> +}
> +
> +/*
> + * This is a complete list of which tokens can happen before any of:
> + *  - variable
> + *  - left parentesis
> + *  - negation
> + *
> + * The -1 represents start of the expression.
> + */
> +static inline int check_one(int op)
> +{
> +	switch (op) {
> +	case TST_OP_AND:
> +	case TST_OP_OR:
> +	case TST_OP_NOT:
> +	case TST_OP_NONE:
> +	case TST_OP_LPAR:
> +		return 0;
> +	default:
> +		return 1;
> +	}
> +}
> +
> +/*
> + * And this checks for tokens that can happen before any of:
> + * - right parentesis
> + * - and
> + * - or
> + *
> + * This is also used to check that the last token in expression is correct one.
> + */
> +static inline int check_two(int op)
> +{
> +	switch (op) {
> +	case TST_OP_VAR:
> +	case TST_OP_RPAR:
> +		return 1;
> +	default:
> +		return 0;
> +	}
> +}
> +
> +/*
> + * Note that we avoid modifying the list until the end so that the caller can
> + * free memory correctly, which is the reason we have a stack for
> parentesis

If you use a new vector/stack for the output queue instead of an
intrusive list then this problem should go away. We have an upper bound
for any token/expr vector which is the length of the input string. So it
is possible to preallocate an input array instead of using a dynamically
allocated linked list.

> + * that are just freed at the end.
> + */
> +static struct tst_expr *shunting_yard(struct tok_list *list)
> +{
> +	struct tst_expr *op_stack[list->cnt];
> +	unsigned int op_stack_pos = 0;
> +	struct tst_expr *out[list->cnt + 1];
> +	unsigned int out_pos = 0;
> +	struct tst_expr *pars[list->cnt];
> +	unsigned int pars_pos = 0;
> +	struct tst_expr *i;
> +	unsigned int j;
> +	int prev_op = TST_OP_NONE;
> +
> +	for (i = list->first; i; i = i->next) {
> +		switch (i->op) {
> +		case TST_OP_VAR:
> +			if (check_one(prev_op)) {
> +				i->priv = "Expected operation";
> +				goto err;
> +			}
> +
> +			stack_push(out, &out_pos, i);
> +
> +			while (stack_peek_op(op_stack, op_stack_pos) == TST_OP_NOT)
> +				stack_push(out, &out_pos, stack_pop(op_stack, &op_stack_pos));
> +		break;
> +		case TST_OP_LPAR:
> +			if (check_one(prev_op)) {
> +				i->priv = "Expected operation";
> +				goto err;
> +			}
> +
> +			stack_push(op_stack, &op_stack_pos, i);
> +		break;
> +		case TST_OP_RPAR:
> +			if (!check_two(prev_op)) {
> +				i->priv = "Expected variable or )";
> +				goto err;
> +			}
> +
> +			stack_push(pars, &pars_pos, i);
> +
> +			/* pop everything till ( */
> +			for (;;) {
> +				struct tst_expr *op = stack_pop(op_stack, &op_stack_pos);
> +
> +				if (!op) {
> +					i->priv = "Missing (";
> +					goto err;
> +				}
> +
> +				if (op->op == TST_OP_LPAR) {
> +					stack_push(pars, &pars_pos, op);
> +					break;
> +				}
> +
> +				stack_push(out, &out_pos, op);
> +			}
> +
> +			while (stack_peek_op(op_stack, op_stack_pos) == TST_OP_NOT)
> +				stack_push(out, &out_pos, stack_pop(op_stack, &op_stack_pos));
> +		break;
> +		case TST_OP_NOT:
> +			if (check_one(prev_op)) {
> +				i->priv = "Expected operation";
> +				goto err;
> +			}
> +			stack_push(op_stack, &op_stack_pos, i);
> +		break;
> +		case TST_OP_AND:
> +		case TST_OP_OR:
> +			if (!check_two(prev_op)) {
> +				i->priv = "Expected variable or (";
> +				goto err;
> +			}
> +
> +			/*
> +			 * There can be at most one binary op on the stack
> +			 * since we pop the one present on the stack before we
> +			 * attempt to push new one they never accumulate.
> +			 */
> +			switch (stack_peek_op(op_stack, op_stack_pos)) {
> +			case TST_OP_AND:
> +			case TST_OP_OR:
> +				stack_push(out, &out_pos, stack_pop(op_stack, &op_stack_pos));
> +			break;
> +			}
> +
> +			stack_push(op_stack, &op_stack_pos, i);
> +		break;
> +		}
> +
> +		prev_op = i->op;
> +	}
> +
> +	if (!check_two(list->last->op)) {
> +		list->last->priv = "Unfinished expression";
> +		goto err;
> +	}
> +
> +	/* pop remaining operations */
> +	while ((i = stack_pop(op_stack, &op_stack_pos))) {
> +		if (i->op == TST_OP_LPAR) {
> +			i->priv = "Missing )";
> +			goto err;
> +		}
> +
> +		stack_push(out, &out_pos, i);
> +	}
> +
> +	/* free parentesis */
> +	for (j = 0; j < pars_pos; j++)
> +		free(pars[j]);
> +
> +	/* reconstruct the list */
> +	out[out_pos] = NULL;
> +
> +	for (j = 0; j < out_pos; j++)
> +		out[j]->next = out[j + 1];
> +
> +	return out[0];
> +err:
> +	return NULL;
> +}
> +
> +struct tst_expr *tst_bool_expr_parse(const char *expr)
> +{
> +	struct tok_list list = {};
> +	struct tst_expr *ret;
> +
> +	tokenize(expr, &list);
> +
> +	if (!list.first)
> +		return NULL;
> +
> +	ret = shunting_yard(&list);
> +
> +	if (!ret) {
> +		tst_bool_expr_err(stderr, list.first);
> +		tst_bool_expr_free(list.first);
> +		return NULL;
> +	}
> +
> +	return ret;
> +}
> +
> +#define MAX_STACK 16
> +
> +int tst_bool_expr_eval(struct tst_expr *expr,
> +                       int (*map)(struct tst_expr *var))
> +{
> +	struct tst_expr *i;
> +	int stack[MAX_STACK];
> +	int pos = -1;
> +
> +	for (i = expr; i; i = i->next) {
> +		switch (i->op) {
> +		case TST_OP_NOT:
> +			stack[pos] = !stack[pos];
> +		break;
> +		case TST_OP_OR:
> +			stack[pos-1] = stack[pos] || stack[pos-1];
> +			pos--;
> +		break;
> +		case TST_OP_AND:
> +			stack[pos-1] = stack[pos] && stack[pos-1];
> +			pos--;
> +		break;
> +		case TST_OP_VAR:
> +			if (pos + 1 >= MAX_STACK) {
> +				fprintf(stderr, "Eval out of stack!\n");
> +				return -1;
> +			}
> +
> +			stack[++pos] = map(i);
> +
> +			/* map reported undefined variable -> abort */
> +			if (stack[pos] == -1)
> +				return -1;
> +		break;
> +		/* does not happen */
> +		default:
> +		break;
> +		}
> +	}
> +

We could perform a final check on our logic here by asserting pos == 0.

> +	return stack[0];
> +}
> +
> +void tst_bool_expr_free(struct tst_expr *expr)
> +{
> +	struct tst_expr *i = expr, *tmp;
> +
> +	while (i) {
> +		tmp = i;
> +		i = i->next;
> +		free(tmp);
> +	}
> +}
> -- 
> 2.26.2

-- 
Thank you,
Richard.

[LTP] [PATCH v2 1/2] lib: Add generic boolean expression parser and eval

[Cyril Hrubis]

Hi!
> > +/*
> > + * Note that we avoid modifying the list until the end so that the caller can
> > + * free memory correctly, which is the reason we have a stack for
> > parentesis
> 
> If you use a new vector/stack for the output queue instead of an
> intrusive list then this problem should go away. We have an upper bound
> for any token/expr vector which is the length of the input string. So it
> is possible to preallocate an input array instead of using a dynamically
> allocated linked list.

Or we can run the tokenizer twice and first time only record number of
tokens...

-- 
Cyril Hrubis
chrubis@suse.cz

[LTP] [PATCH v2 2/2] lib/tst_kconfig: Make use of boolean expression eval

[Cyril Hrubis]

Now each string in the kconfig[] array in tst_test structure is an
boolean expression which is evaluated. All expressions has to be true in
order for the test to continue.

This also makes the parser for the kernel config a bit more robust as it
was pointed out that there may have been cases where it could be mislead
by hand edited config files.

+ Update the docs.

Signed-off-by: Cyril Hrubis <chrubis@suse.cz>
CC: Pengfei Xu <pengfei.xu@intel.com>
---

v2:
   - squashed the two patches since we are doing more extensive changes
   - made the parser a bit more robust
   - renamed a few fucntions and identifiers to make the code easier to
     understand
   - sprinkled the code with consts

 doc/test-writing-guidelines.txt |  21 +-
 include/tst_kconfig.h           |  34 +--
 lib/newlib_tests/config06       |   1 +
 lib/newlib_tests/test_kconfig.c |   1 +
 lib/tst_kconfig.c               | 362 +++++++++++++++++++++-----------
 5 files changed, 270 insertions(+), 149 deletions(-)
 create mode 100644 lib/newlib_tests/config06

diff --git a/doc/test-writing-guidelines.txt b/doc/test-writing-guidelines.txt
index 1a51ef7c7..3c2ab7166 100644
--- a/doc/test-writing-guidelines.txt
+++ b/doc/test-writing-guidelines.txt
@@ -1643,21 +1643,26 @@ on the system, disabled syscalls can be detected by checking for 'ENOSYS'
 errno etc.
 
 However in rare cases core kernel features couldn't be detected based on the
-kernel userspace API and we have to resort to kernel .config parsing.
+kernel userspace API and we have to resort to parse the kernel .config.
 
-For this cases the test should set the 'NULL' terminated '.needs_kconfigs' array
-of kernel config options required for the test. The config option can be
-specified either as plain "CONFIG_FOO" in which case it's sufficient for the
-test continue if it's set to any value (typically =y or =m). Or with a value
-as "CONFIG_FOO=bar" in which case the value has to match as well. The test is
-aborted with 'TCONF' if any of the required options were not set.
+For this cases the test should set the 'NULL' terminated '.needs_kconfigs'
+array of boolean expressions with constraints on the kconfig variables. The
+boolean expression consits of variables, two binary operations '&' and '|',
+negation '!' and correct sequence of parentesis '()'. Variables are expected
+to be in a form of "CONFIG_FOO[=bar]".
+
+The test will continue to run if all expressions are evaluated to 'True'.
+Missing variable is mapped to 'False' as well as variable with different than
+specified value, e.g. 'CONFIG_FOO=bar' will evaluate to 'False' if the value
+is anything else but 'bar'. If config variable is specified as plain
+'CONFIG_FOO' it's evaluated to true it's set to any value (typically =y or =m).
 
 [source,c]
 -------------------------------------------------------------------------------
 #include "tst_test.h"
 
 static const char *kconfigs[] = {
-	"CONFIG_X86_INTEL_UMIP",
+	"CONFIG_X86_INTEL_UMIP | CONFIG_X86_UMIP",
 	NULL
 };
 
diff --git a/include/tst_kconfig.h b/include/tst_kconfig.h
index 2d2cfd782..1bb21fea8 100644
--- a/include/tst_kconfig.h
+++ b/include/tst_kconfig.h
@@ -6,27 +6,27 @@
 #ifndef TST_KCONFIG_H__
 #define TST_KCONFIG_H__
 
-struct tst_kconfig_res {
-	char match;
-	char *value;
+struct tst_kconfig_var {
+	char id[64];
+	unsigned int id_len;
+	char choice;
+	char *val;
 };
 
 /**
- * Reads a kernel config and parses it for values defined in kconfigs array.
+ *
+ * Reads a kernel config, parses it and writes results into an array of
+ * tst_kconfig_var structures.
  *
  * The path to the kernel config should be autodetected in most of the cases as
  * the code looks for know locations. It can be explicitely set/overrided with
  * the KCONFIG_PATH environment variable as well.
  *
- * The kcofings array is expected to contain strings in a format "CONFIG_FOO"
- * or "CONFIG_FOO=bar". The result array has to be suitably sized to fit the
- * results.
- *
- * @param kconfigs array of config strings to look for
- * @param results array to store results to
- * @param cnt size of the arrays
+ * The caller has to initialize the tst_kconfig_var structure. The id has to be
+ * filled with config variable name such as 'CONFIG_FOO', the id_len should
+ * hold the id string length and the choice and val has to be zeroed.
  *
- * The match in the tst_kconfig_res structure is set as follows:
+ * After a call to this function each choice be set as follows:
  *
  *  'm' - config option set to m
  *  'y' - config option set to y
@@ -34,11 +34,13 @@ struct tst_kconfig_res {
  *  'n' - config option is not set
  *   0  - config option not found
  *
- * In the case that match is set to 'v' the value points to a newly allocated
- * string that holds the value.
+ * In the case that match is set to 'v' the val pointer points to a newly
+ * allocated string that holds the value.
+ *
+ * @param vars An array of caller initalized tst_kconfig_var structures.
+ * @param vars_len Length of the vars array.
  */
-void tst_kconfig_read(const char *const kconfigs[],
-		      struct tst_kconfig_res results[], size_t cnt);
+void tst_kconfig_read(struct tst_kconfig_var vars[], size_t vars_len);
 
 /**
  * Checks if required kernel configuration options are set in the kernel
diff --git a/lib/newlib_tests/config06 b/lib/newlib_tests/config06
new file mode 100644
index 000000000..b7db25411
--- /dev/null
+++ b/lib/newlib_tests/config06
@@ -0,0 +1 @@
+# Empty
diff --git a/lib/newlib_tests/test_kconfig.c b/lib/newlib_tests/test_kconfig.c
index d9c662fc5..183d55611 100644
--- a/lib/newlib_tests/test_kconfig.c
+++ b/lib/newlib_tests/test_kconfig.c
@@ -14,6 +14,7 @@ static const char *kconfigs[] = {
 	"CONFIG_MMU",
 	"CONFIG_EXT4_FS=m",
 	"CONFIG_PGTABLE_LEVELS=4",
+	"CONFIG_MMU & CONFIG_EXT4_FS=m",
 	NULL
 };
 
diff --git a/lib/tst_kconfig.c b/lib/tst_kconfig.c
index d49187b6f..f3159b981 100644
--- a/lib/tst_kconfig.c
+++ b/lib/tst_kconfig.c
@@ -12,6 +12,7 @@
 #define TST_NO_DEFAULT_MAIN
 #include "tst_test.h"
 #include "tst_kconfig.h"
+#include "tst_bool_expr.h"
 
 static const char *kconfig_path(char *path_buf, size_t path_buf_len)
 {
@@ -84,126 +85,108 @@ static void close_kconfig(FILE *fp)
 		fclose(fp);
 }
 
-struct match {
-	/* match len, string length up to \0 or = */
-	size_t len;
-	/* if set part of conf string after = */
-	const char *val;
-	/* if set the config option was matched already */
-	int match;
-};
-
-static int is_set(const char *str, const char *val)
+static inline int kconfig_parse_line(const char *line,
+                                     struct tst_kconfig_var *vars,
+                                     unsigned int vars_len)
 {
-	size_t vlen = strlen(val);
+	unsigned int i, var_len = 0;
+	const char *var;
+	int is_not_set = 0;
 
-	while (isspace(*str))
-		str++;
+	while (isspace(*line))
+		line++;
 
-	if (strncmp(str, val, vlen))
-		return 0;
+	if (*line == '#') {
+		if (!strstr(line, "is not set"))
+			return 0;
 
-	switch (str[vlen]) {
-	case ' ':
-	case '\n':
-	case '\0':
-		return 1;
-	break;
-	default:
-		return 0;
+		is_not_set = 1;
 	}
-}
-
-static inline int match(struct match *match, const char *conf,
-                        struct tst_kconfig_res *result, const char *line)
-{
-	if (match->match)
-		return 0;
 
-	const char *cfg = strstr(line, "CONFIG_");
+	var = strstr(line, "CONFIG_");
 
-	if (!cfg)
+	if (!var)
 		return 0;
 
-	if (strncmp(cfg, conf, match->len))
-		return 0;
-
-	const char *val = &cfg[match->len];
-
-	switch (cfg[match->len]) {
-	case '=':
+	for (;;) {
+		switch (var[var_len]) {
+		case 'A' ... 'Z':
+		case '0' ... '9':
+		case '_':
+			var_len++;
+		break;
+		default:
+			goto out;
 		break;
-	case ' ':
-		if (is_set(val, "is not set")) {
-			result->match = 'n';
-			goto match;
 		}
-	/* fall through */
-	default:
-		return 0;
 	}
 
-	if (is_set(val, "=y")) {
-		result->match = 'y';
-		goto match;
-	}
+out:
 
-	if (is_set(val, "=m")) {
-		result->match = 'm';
-		goto match;
-	}
+	for (i = 0; i < vars_len; i++) {
+		const char *val;
+		unsigned int val_len = 0;
 
-	result->match = 'v';
-	result->value = strndup(val+1, strlen(val)-2);
+		if (vars[i].id_len != var_len)
+			continue;
 
-match:
-	match->match = 1;
-	return 1;
-}
+		if (strncmp(vars[i].id, var, var_len))
+			continue;
 
-void tst_kconfig_read(const char *const *kconfigs,
-                      struct tst_kconfig_res results[], size_t cnt)
-{
-	struct match matches[cnt];
-	FILE *fp;
-	unsigned int i, j;
-	char buf[1024];
+		if (is_not_set) {
+			vars[i].choice = 'n';
+			return 1;
+		}
 
-	for (i = 0; i < cnt; i++) {
-		const char *val = strchr(kconfigs[i], '=');
+		val = var + var_len;
 
-		if (strncmp("CONFIG_", kconfigs[i], 7))
-			tst_brk(TBROK, "Invalid config string '%s'", kconfigs[i]);
+		while (isspace(*val))
+			val++;
+
+		if (*val != '=')
+			return 0;
+
+		val++;
 
-		matches[i].match = 0;
-		matches[i].len = strlen(kconfigs[i]);
+		while (isspace(*val))
+			val++;
 
-		if (val) {
-			matches[i].val = val + 1;
-			matches[i].len -= strlen(val);
+		while (!isspace(val[val_len]))
+			val_len++;
+
+		if (val_len == 1) {
+			switch (val[0]) {
+			case 'y':
+				vars[i].choice = 'y';
+				return 1;
+			case 'm':
+				vars[i].choice = 'm';
+				return 1;
+			}
 		}
 
-		results[i].match = 0;
-		results[i].value = NULL;
+		vars[i].choice = 'v';
+		vars[i].val = strndup(val, val_len);
 	}
 
-	fp = open_kconfig();
+	return 0;
+}
+
+void tst_kconfig_read(struct tst_kconfig_var vars[], size_t vars_len)
+{
+	char line[128];
+	unsigned int vars_found = 0;
+
+	FILE *fp = open_kconfig();
 	if (!fp)
 		tst_brk(TBROK, "Cannot parse kernel .config");
 
-	while (fgets(buf, sizeof(buf), fp)) {
-		for (i = 0; i < cnt; i++) {
-			if (match(&matches[i], kconfigs[i], &results[i], buf)) {
-				for (j = 0; j < cnt; j++) {
-					if (matches[j].match)
-						break;
-				}
-
-				if (j == cnt)
-					goto exit;
-			}
-		}
+	while (fgets(line, sizeof(line), fp)) {
+		if (kconfig_parse_line(line, vars, vars_len))
+			vars_found++;
 
+		if (vars_found == vars_len)
+			goto exit;
 	}
 
 exit:
@@ -219,65 +202,194 @@ static size_t array_len(const char *const kconfigs[])
 	return i;
 }
 
-static int compare_res(struct tst_kconfig_res *res, const char *kconfig,
-                       char match, const char *val)
+static const char *strnchr(const char *s, int c, unsigned int len)
 {
-	if (res->match != match) {
-		tst_res(TINFO, "Needs kernel %s, have %c", kconfig, res->match);
-		return 1;
+	unsigned int i;
+
+	for (i = 0; i < len; i++) {
+		if (s[i] == c)
+			return s + i;
 	}
 
-	if (match != 'v')
-		return 0;
+	return NULL;
+}
+
+static inline unsigned int get_len(const char* kconfig, unsigned int len)
+{
+	const char *sep = strnchr(kconfig, '=', len);
+
+	if (!sep)
+		return len;
+
+	return sep - kconfig;
+}
+
+static inline unsigned int get_var_cnt(struct tst_expr *const exprs[],
+                                       unsigned int expr_cnt)
+{
+	unsigned int i;
+	const struct tst_expr *j;
+	unsigned int cnt = 0;
 
-	if (strcmp(res->value, val)) {
-		tst_res(TINFO, "Needs kernel %s, have %s", kconfig, res->value);
-		return 1;
+	for (i = 0; i < expr_cnt; i++) {
+		for (j = exprs[i]; j; j = j->next) {
+			if (j->op == TST_OP_VAR)
+				cnt++;
+		}
 	}
 
-	return 0;
+	return cnt;
 }
 
-void tst_kconfig_check(const char *const kconfigs[])
+static const struct tst_kconfig_var *find_var(const struct tst_kconfig_var vars[],
+                                        unsigned int var_cnt,
+                                        const char *var)
 {
-	size_t cnt = array_len(kconfigs);
-	struct tst_kconfig_res results[cnt];
 	unsigned int i;
-	int abort_test = 0;
 
-	tst_kconfig_read(kconfigs, results, cnt);
+	for (i = 0; i < var_cnt; i++) {
+		if (!strcmp(vars[i].id, var))
+			return &vars[i];
+	}
 
-	for (i = 0; i < cnt; i++) {
-		if (results[i].match == 0) {
-			tst_res(TINFO, "Missing kernel %s", kconfigs[i]);
-			abort_test = 1;
+	return NULL;
+}
+
+/*
+ * Fill in the kconfig variables array from the expressions. Also makes sure
+ * that each variable is copied to the array exaclty once.
+ */
+static inline unsigned int populate_vars(struct tst_expr *exprs[],
+                                         unsigned int expr_cnt,
+                                    struct tst_kconfig_var vars[])
+{
+	unsigned int i;
+	struct tst_expr *j;
+	unsigned int cnt = 0;
+
+	for (i = 0; i < expr_cnt; i++) {
+		for (j = exprs[i]; j; j = j->next) {
+			const struct tst_kconfig_var *var;
+
+			if (j->op != TST_OP_VAR)
+				continue;
+
+			vars[cnt].id_len = get_len(j->tok, j->tok_len);
+
+			if (vars[cnt].id_len + 1 >= sizeof(vars[cnt].id))
+				tst_brk(TBROK, "kconfig var id too long!");
+
+			strncpy(vars[cnt].id, j->tok, vars[cnt].id_len);
+			vars[cnt].id[vars[cnt].id_len] = 0;
+			vars[cnt].choice = 0;
+
+			var = find_var(vars, cnt, vars[cnt].id);
+
+			if (var)
+				j->priv = var;
+			else
+				j->priv = &vars[cnt++];
+		}
+	}
+
+	return cnt;
+}
+
+static int map(struct tst_expr *expr)
+{
+	const struct tst_kconfig_var *var = expr->priv;
+
+	if (var->choice == 0)
+		return 0;
+
+	const char *val = strnchr(expr->tok, '=', expr->tok_len);
+
+	/* CONFIG_FOO evaluates to true if y or m */
+	if (!val)
+		return var->choice == 'y' || var->choice == 'm';
+
+	unsigned int len = expr->tok_len - (val - expr->tok);
+	char choice = 'v';
+	val++;
+
+	if (!strncmp(val, "n", len))
+		choice = 'n';
+
+	if (!strncmp(val, "y", len))
+		choice = 'y';
+
+	if (!strncmp(val, "m", len))
+		choice = 'm';
+
+	if (choice != 'v')
+		return var->choice == choice;
+
+	return !strncmp(val, var->val, len);
+}
+
+static void dump_vars(const struct tst_expr *expr)
+{
+	const struct tst_expr *i;
+	const struct tst_kconfig_var *var;
+
+	tst_res(TINFO, "Variables:");
+
+	for (i = expr; i; i = i->next) {
+		if (i->op != TST_OP_VAR)
+			continue;
+
+		var = i->priv;
+
+		if (!var->choice) {
+			tst_res(TINFO, " %s Undefined", var->id);
 			continue;
 		}
 
-		if (results[i].match == 'n') {
-			tst_res(TINFO, "Kernel %s is not set", kconfigs[i]);
-			abort_test = 1;
+		if (var->choice == 'v') {
+			tst_res(TINFO, " %s=%s", var->id, var->val);
 			continue;
 		}
 
-		const char *val = strchr(kconfigs[i], '=');
+		tst_res(TINFO, " %s=%c", var->id, var->choice);
+	}
+}
 
-		if (val) {
-			char match = 'v';
-			val++;
+void tst_kconfig_check(const char *const kconfigs[])
+{
+	size_t expr_cnt = array_len(kconfigs);
+	struct tst_expr *exprs[expr_cnt];
+	unsigned int i, var_cnt;
+	int abort_test = 0;
 
-			if (!strcmp(val, "y"))
-				match = 'y';
+	for (i = 0; i < expr_cnt; i++) {
+		exprs[i] = tst_bool_expr_parse(kconfigs[i]);
 
-			if (!strcmp(val, "m"))
-				match = 'm';
+		if (!exprs[i])
+			tst_brk(TBROK, "Invalid kconfig expression!");
+	}
 
-			if (compare_res(&results[i], kconfigs[i], match, val))
-				abort_test = 1;
+	var_cnt = get_var_cnt(exprs, expr_cnt);
+	struct tst_kconfig_var vars[var_cnt];
 
+	var_cnt = populate_vars(exprs, expr_cnt, vars);
+
+	tst_kconfig_read(vars, var_cnt);
+
+	for (i = 0; i < expr_cnt; i++) {
+		int val = tst_bool_expr_eval(exprs[i], map);
+
+		if (val != 1) {
+			abort_test = 1;
+			tst_res(TINFO, "Expression '%s' not satisfied!", kconfigs[i]);
+			dump_vars(exprs[i]);
 		}
 
-		free(results[i].value);
+		tst_bool_expr_free(exprs[i]);
+	}
+
+	for (i = 0; i < var_cnt; i++) {
+		if (vars[i].choice == 'v')
+			free(vars[i].val);
 	}
 
 	if (abort_test)
-- 
2.26.2

[LTP] [PATCH v2 2/2] lib/tst_kconfig: Make use of boolean expression eval

[Xiao Yang]

On 2020/10/27 19:04, Cyril Hrubis wrote:
> Now each string in the kconfig[] array in tst_test structure is an
> boolean expression which is evaluated. All expressions has to be true in
> order for the test to continue.
>
> This also makes the parser for the kernel config a bit more robust as it
> was pointed out that there may have been cases where it could be mislead
> by hand edited config files.
>
> + Update the docs.
>
> Signed-off-by: Cyril Hrubis<chrubis@suse.cz>
> CC: Pengfei Xu<pengfei.xu@intel.com>
> ---
>
> v2:
>     - squashed the two patches since we are doing more extensive changes
>     - made the parser a bit more robust
>     - renamed a few fucntions and identifiers to make the code easier to
>       understand
>     - sprinkled the code with consts
>
>   doc/test-writing-guidelines.txt |  21 +-
>   include/tst_kconfig.h           |  34 +--
>   lib/newlib_tests/config06       |   1 +
>   lib/newlib_tests/test_kconfig.c |   1 +
>   lib/tst_kconfig.c               | 362 +++++++++++++++++++++-----------
>   5 files changed, 270 insertions(+), 149 deletions(-)
>   create mode 100644 lib/newlib_tests/config06
>
> diff --git a/doc/test-writing-guidelines.txt b/doc/test-writing-guidelines.txt
> index 1a51ef7c7..3c2ab7166 100644
> --- a/doc/test-writing-guidelines.txt
> +++ b/doc/test-writing-guidelines.txt
> @@ -1643,21 +1643,26 @@ on the system, disabled syscalls can be detected by checking for 'ENOSYS'
>   errno etc.
>
>   However in rare cases core kernel features couldn't be detected based on the
> -kernel userspace API and we have to resort to kernel .config parsing.
> +kernel userspace API and we have to resort to parse the kernel .config.
>
> -For this cases the test should set the 'NULL' terminated '.needs_kconfigs' array
> -of kernel config options required for the test. The config option can be
> -specified either as plain "CONFIG_FOO" in which case it's sufficient for the
> -test continue if it's set to any value (typically =y or =m). Or with a value
> -as "CONFIG_FOO=bar" in which case the value has to match as well. The test is
> -aborted with 'TCONF' if any of the required options were not set.
> +For this cases the test should set the 'NULL' terminated '.needs_kconfigs'
> +array of boolean expressions with constraints on the kconfig variables. The
> +boolean expression consits of variables, two binary operations '&' and '|',
> +negation '!' and correct sequence of parentesis '()'. Variables are expected
> +to be in a form of "CONFIG_FOO[=bar]".
> +
> +The test will continue to run if all expressions are evaluated to 'True'.
> +Missing variable is mapped to 'False' as well as variable with different than
> +specified value, e.g. 'CONFIG_FOO=bar' will evaluate to 'False' if the value
> +is anything else but 'bar'. If config variable is specified as plain
> +'CONFIG_FOO' it's evaluated to true it's set to any value (typically =y or =m).
>
>   [source,c]
>   -------------------------------------------------------------------------------
>   #include "tst_test.h"
>
>   static const char *kconfigs[] = {
> -	"CONFIG_X86_INTEL_UMIP",
> +	"CONFIG_X86_INTEL_UMIP | CONFIG_X86_UMIP",
>   	NULL
>   };
>
> diff --git a/include/tst_kconfig.h b/include/tst_kconfig.h
> index 2d2cfd782..1bb21fea8 100644
> --- a/include/tst_kconfig.h
> +++ b/include/tst_kconfig.h
> @@ -6,27 +6,27 @@
>   #ifndef TST_KCONFIG_H__
>   #define TST_KCONFIG_H__
>
> -struct tst_kconfig_res {
> -	char match;
> -	char *value;
> +struct tst_kconfig_var {
> +	char id[64];
> +	unsigned int id_len;
> +	char choice;
> +	char *val;
>   };
>
>   /**
> - * Reads a kernel config and parses it for values defined in kconfigs array.
> + *
> + * Reads a kernel config, parses it and writes results into an array of
> + * tst_kconfig_var structures.
>    *
>    * The path to the kernel config should be autodetected in most of the cases as
>    * the code looks for know locations. It can be explicitely set/overrided with
>    * the KCONFIG_PATH environment variable as well.
>    *
> - * The kcofings array is expected to contain strings in a format "CONFIG_FOO"
> - * or "CONFIG_FOO=bar". The result array has to be suitably sized to fit the
> - * results.
> - *
> - * @param kconfigs array of config strings to look for
> - * @param results array to store results to
> - * @param cnt size of the arrays
> + * The caller has to initialize the tst_kconfig_var structure. The id has to be
> + * filled with config variable name such as 'CONFIG_FOO', the id_len should
> + * hold the id string length and the choice and val has to be zeroed.
>    *
> - * The match in the tst_kconfig_res structure is set as follows:
> + * After a call to this function each choice be set as follows:
>    *
>    *  'm' - config option set to m
>    *  'y' - config option set to y
> @@ -34,11 +34,13 @@ struct tst_kconfig_res {
>    *  'n' - config option is not set
>    *   0  - config option not found
>    *
> - * In the case that match is set to 'v' the value points to a newly allocated
> - * string that holds the value.
> + * In the case that match is set to 'v' the val pointer points to a newly
> + * allocated string that holds the value.
> + *
> + * @param vars An array of caller initalized tst_kconfig_var structures.
> + * @param vars_len Length of the vars array.
>    */
> -void tst_kconfig_read(const char *const kconfigs[],
> -		      struct tst_kconfig_res results[], size_t cnt);
> +void tst_kconfig_read(struct tst_kconfig_var vars[], size_t vars_len);
>
>   /**
>    * Checks if required kernel configuration options are set in the kernel
> diff --git a/lib/newlib_tests/config06 b/lib/newlib_tests/config06
> new file mode 100644
> index 000000000..b7db25411
> --- /dev/null
> +++ b/lib/newlib_tests/config06
> @@ -0,0 +1 @@
> +# Empty
> diff --git a/lib/newlib_tests/test_kconfig.c b/lib/newlib_tests/test_kconfig.c
> index d9c662fc5..183d55611 100644
> --- a/lib/newlib_tests/test_kconfig.c
> +++ b/lib/newlib_tests/test_kconfig.c
> @@ -14,6 +14,7 @@ static const char *kconfigs[] = {
>   	"CONFIG_MMU",
>   	"CONFIG_EXT4_FS=m",
>   	"CONFIG_PGTABLE_LEVELS=4",
> +	"CONFIG_MMU&  CONFIG_EXT4_FS=m",
>   	NULL
>   };
>
> diff --git a/lib/tst_kconfig.c b/lib/tst_kconfig.c
> index d49187b6f..f3159b981 100644
> --- a/lib/tst_kconfig.c
> +++ b/lib/tst_kconfig.c
> @@ -12,6 +12,7 @@
>   #define TST_NO_DEFAULT_MAIN
>   #include "tst_test.h"
>   #include "tst_kconfig.h"
> +#include "tst_bool_expr.h"
>
>   static const char *kconfig_path(char *path_buf, size_t path_buf_len)
>   {
> @@ -84,126 +85,108 @@ static void close_kconfig(FILE *fp)
>   		fclose(fp);
>   }
>
> -struct match {
> -	/* match len, string length up to \0 or = */
> -	size_t len;
> -	/* if set part of conf string after = */
> -	const char *val;
> -	/* if set the config option was matched already */
> -	int match;
> -};
> -
> -static int is_set(const char *str, const char *val)
> +static inline int kconfig_parse_line(const char *line,
> +                                     struct tst_kconfig_var *vars,
> +                                     unsigned int vars_len)
>   {
> -	size_t vlen = strlen(val);
> +	unsigned int i, var_len = 0;
> +	const char *var;
> +	int is_not_set = 0;
>
> -	while (isspace(*str))
> -		str++;
> +	while (isspace(*line))
> +		line++;
>
> -	if (strncmp(str, val, vlen))
> -		return 0;
> +	if (*line == '#') {
> +		if (!strstr(line, "is not set"))
> +			return 0;
>
> -	switch (str[vlen]) {
> -	case ' ':
> -	case '\n':
> -	case '\0':
> -		return 1;
> -	break;
> -	default:
> -		return 0;
> +		is_not_set = 1;
>   	}
> -}
> -
> -static inline int match(struct match *match, const char *conf,
> -                        struct tst_kconfig_res *result, const char *line)
> -{
> -	if (match->match)
> -		return 0;
>
> -	const char *cfg = strstr(line, "CONFIG_");
> +	var = strstr(line, "CONFIG_");
>
> -	if (!cfg)
> +	if (!var)
>   		return 0;
>
> -	if (strncmp(cfg, conf, match->len))
> -		return 0;
> -
> -	const char *val =&cfg[match->len];
> -
> -	switch (cfg[match->len]) {
> -	case '=':
> +	for (;;) {
> +		switch (var[var_len]) {
> +		case 'A' ... 'Z':
> +		case '0' ... '9':
> +		case '_':
> +			var_len++;
> +		break;
> +		default:
> +			goto out;
>   		break;
> -	case ' ':
> -		if (is_set(val, "is not set")) {
> -			result->match = 'n';
> -			goto match;
>   		}
> -	/* fall through */
> -	default:
> -		return 0;
>   	}
>
> -	if (is_set(val, "=y")) {
> -		result->match = 'y';
> -		goto match;
> -	}
> +out:
>
> -	if (is_set(val, "=m")) {
> -		result->match = 'm';
> -		goto match;
> -	}
> +	for (i = 0; i<  vars_len; i++) {
> +		const char *val;
> +		unsigned int val_len = 0;
>
> -	result->match = 'v';
> -	result->value = strndup(val+1, strlen(val)-2);
> +		if (vars[i].id_len != var_len)
> +			continue;
>
> -match:
> -	match->match = 1;
> -	return 1;
> -}
> +		if (strncmp(vars[i].id, var, var_len))
> +			continue;
>
> -void tst_kconfig_read(const char *const *kconfigs,
> -                      struct tst_kconfig_res results[], size_t cnt)
Hi Cyril,

New tst_kconfig_read() breaks the compilation of acct02 so we also need 
to update acct02. :-)

Best Regards,
Xiao Yang
> -{
> -	struct match matches[cnt];
> -	FILE *fp;
> -	unsigned int i, j;
> -	char buf[1024];
> +		if (is_not_set) {
> +			vars[i].choice = 'n';
> +			return 1;
> +		}
>
> -	for (i = 0; i<  cnt; i++) {
> -		const char *val = strchr(kconfigs[i], '=');
> +		val = var + var_len;
>
> -		if (strncmp("CONFIG_", kconfigs[i], 7))
> -			tst_brk(TBROK, "Invalid config string '%s'", kconfigs[i]);
> +		while (isspace(*val))
> +			val++;
> +
> +		if (*val != '=')
> +			return 0;
> +
> +		val++;
>
> -		matches[i].match = 0;
> -		matches[i].len = strlen(kconfigs[i]);
> +		while (isspace(*val))
> +			val++;
>
> -		if (val) {
> -			matches[i].val = val + 1;
> -			matches[i].len -= strlen(val);
> +		while (!isspace(val[val_len]))
> +			val_len++;
> +
> +		if (val_len == 1) {
> +			switch (val[0]) {
> +			case 'y':
> +				vars[i].choice = 'y';
> +				return 1;
> +			case 'm':
> +				vars[i].choice = 'm';
> +				return 1;
> +			}
>   		}
>
> -		results[i].match = 0;
> -		results[i].value = NULL;
> +		vars[i].choice = 'v';
> +		vars[i].val = strndup(val, val_len);
>   	}
>
> -	fp = open_kconfig();
> +	return 0;
> +}
> +
> +void tst_kconfig_read(struct tst_kconfig_var vars[], size_t vars_len)
> +{
> +	char line[128];
> +	unsigned int vars_found = 0;
> +
> +	FILE *fp = open_kconfig();
>   	if (!fp)
>   		tst_brk(TBROK, "Cannot parse kernel .config");
>
> -	while (fgets(buf, sizeof(buf), fp)) {
> -		for (i = 0; i<  cnt; i++) {
> -			if (match(&matches[i], kconfigs[i],&results[i], buf)) {
> -				for (j = 0; j<  cnt; j++) {
> -					if (matches[j].match)
> -						break;
> -				}
> -
> -				if (j == cnt)
> -					goto exit;
> -			}
> -		}
> +	while (fgets(line, sizeof(line), fp)) {
> +		if (kconfig_parse_line(line, vars, vars_len))
> +			vars_found++;
>
> +		if (vars_found == vars_len)
> +			goto exit;
>   	}
>
>   exit:
> @@ -219,65 +202,194 @@ static size_t array_len(const char *const kconfigs[])
>   	return i;
>   }
>
> -static int compare_res(struct tst_kconfig_res *res, const char *kconfig,
> -                       char match, const char *val)
> +static const char *strnchr(const char *s, int c, unsigned int len)
>   {
> -	if (res->match != match) {
> -		tst_res(TINFO, "Needs kernel %s, have %c", kconfig, res->match);
> -		return 1;
> +	unsigned int i;
> +
> +	for (i = 0; i<  len; i++) {
> +		if (s[i] == c)
> +			return s + i;
>   	}
>
> -	if (match != 'v')
> -		return 0;
> +	return NULL;
> +}
> +
> +static inline unsigned int get_len(const char* kconfig, unsigned int len)
> +{
> +	const char *sep = strnchr(kconfig, '=', len);
> +
> +	if (!sep)
> +		return len;
> +
> +	return sep - kconfig;
> +}
> +
> +static inline unsigned int get_var_cnt(struct tst_expr *const exprs[],
> +                                       unsigned int expr_cnt)
> +{
> +	unsigned int i;
> +	const struct tst_expr *j;
> +	unsigned int cnt = 0;
>
> -	if (strcmp(res->value, val)) {
> -		tst_res(TINFO, "Needs kernel %s, have %s", kconfig, res->value);
> -		return 1;
> +	for (i = 0; i<  expr_cnt; i++) {
> +		for (j = exprs[i]; j; j = j->next) {
> +			if (j->op == TST_OP_VAR)
> +				cnt++;
> +		}
>   	}
>
> -	return 0;
> +	return cnt;
>   }
>
> -void tst_kconfig_check(const char *const kconfigs[])
> +static const struct tst_kconfig_var *find_var(const struct tst_kconfig_var vars[],
> +                                        unsigned int var_cnt,
> +                                        const char *var)
>   {
> -	size_t cnt = array_len(kconfigs);
> -	struct tst_kconfig_res results[cnt];
>   	unsigned int i;
> -	int abort_test = 0;
>
> -	tst_kconfig_read(kconfigs, results, cnt);
> +	for (i = 0; i<  var_cnt; i++) {
> +		if (!strcmp(vars[i].id, var))
> +			return&vars[i];
> +	}
>
> -	for (i = 0; i<  cnt; i++) {
> -		if (results[i].match == 0) {
> -			tst_res(TINFO, "Missing kernel %s", kconfigs[i]);
> -			abort_test = 1;
> +	return NULL;
> +}
> +
> +/*
> + * Fill in the kconfig variables array from the expressions. Also makes sure
> + * that each variable is copied to the array exaclty once.
> + */
> +static inline unsigned int populate_vars(struct tst_expr *exprs[],
> +                                         unsigned int expr_cnt,
> +                                    struct tst_kconfig_var vars[])
> +{
> +	unsigned int i;
> +	struct tst_expr *j;
> +	unsigned int cnt = 0;
> +
> +	for (i = 0; i<  expr_cnt; i++) {
> +		for (j = exprs[i]; j; j = j->next) {
> +			const struct tst_kconfig_var *var;
> +
> +			if (j->op != TST_OP_VAR)
> +				continue;
> +
> +			vars[cnt].id_len = get_len(j->tok, j->tok_len);
> +
> +			if (vars[cnt].id_len + 1>= sizeof(vars[cnt].id))
> +				tst_brk(TBROK, "kconfig var id too long!");
> +
> +			strncpy(vars[cnt].id, j->tok, vars[cnt].id_len);
> +			vars[cnt].id[vars[cnt].id_len] = 0;
> +			vars[cnt].choice = 0;
> +
> +			var = find_var(vars, cnt, vars[cnt].id);
> +
> +			if (var)
> +				j->priv = var;
> +			else
> +				j->priv =&vars[cnt++];
> +		}
> +	}
> +
> +	return cnt;
> +}
> +
> +static int map(struct tst_expr *expr)
> +{
> +	const struct tst_kconfig_var *var = expr->priv;
> +
> +	if (var->choice == 0)
> +		return 0;
> +
> +	const char *val = strnchr(expr->tok, '=', expr->tok_len);
> +
> +	/* CONFIG_FOO evaluates to true if y or m */
> +	if (!val)
> +		return var->choice == 'y' || var->choice == 'm';
> +
> +	unsigned int len = expr->tok_len - (val - expr->tok);
> +	char choice = 'v';
> +	val++;
> +
> +	if (!strncmp(val, "n", len))
> +		choice = 'n';
> +
> +	if (!strncmp(val, "y", len))
> +		choice = 'y';
> +
> +	if (!strncmp(val, "m", len))
> +		choice = 'm';
> +
> +	if (choice != 'v')
> +		return var->choice == choice;
> +
> +	return !strncmp(val, var->val, len);
> +}
> +
> +static void dump_vars(const struct tst_expr *expr)
> +{
> +	const struct tst_expr *i;
> +	const struct tst_kconfig_var *var;
> +
> +	tst_res(TINFO, "Variables:");
> +
> +	for (i = expr; i; i = i->next) {
> +		if (i->op != TST_OP_VAR)
> +			continue;
> +
> +		var = i->priv;
> +
> +		if (!var->choice) {
> +			tst_res(TINFO, " %s Undefined", var->id);
>   			continue;
>   		}
>
> -		if (results[i].match == 'n') {
> -			tst_res(TINFO, "Kernel %s is not set", kconfigs[i]);
> -			abort_test = 1;
> +		if (var->choice == 'v') {
> +			tst_res(TINFO, " %s=%s", var->id, var->val);
>   			continue;
>   		}
>
> -		const char *val = strchr(kconfigs[i], '=');
> +		tst_res(TINFO, " %s=%c", var->id, var->choice);
> +	}
> +}
>
> -		if (val) {
> -			char match = 'v';
> -			val++;
> +void tst_kconfig_check(const char *const kconfigs[])
> +{
> +	size_t expr_cnt = array_len(kconfigs);
> +	struct tst_expr *exprs[expr_cnt];
> +	unsigned int i, var_cnt;
> +	int abort_test = 0;
>
> -			if (!strcmp(val, "y"))
> -				match = 'y';
> +	for (i = 0; i<  expr_cnt; i++) {
> +		exprs[i] = tst_bool_expr_parse(kconfigs[i]);
>
> -			if (!strcmp(val, "m"))
> -				match = 'm';
> +		if (!exprs[i])
> +			tst_brk(TBROK, "Invalid kconfig expression!");
> +	}
>
> -			if (compare_res(&results[i], kconfigs[i], match, val))
> -				abort_test = 1;
> +	var_cnt = get_var_cnt(exprs, expr_cnt);
> +	struct tst_kconfig_var vars[var_cnt];
>
> +	var_cnt = populate_vars(exprs, expr_cnt, vars);
> +
> +	tst_kconfig_read(vars, var_cnt);
> +
> +	for (i = 0; i<  expr_cnt; i++) {
> +		int val = tst_bool_expr_eval(exprs[i], map);
> +
> +		if (val != 1) {
> +			abort_test = 1;
> +			tst_res(TINFO, "Expression '%s' not satisfied!", kconfigs[i]);
> +			dump_vars(exprs[i]);
>   		}
>
> -		free(results[i].value);
> +		tst_bool_expr_free(exprs[i]);
> +	}
> +
> +	for (i = 0; i<  var_cnt; i++) {
> +		if (vars[i].choice == 'v')
> +			free(vars[i].val);
>   	}
>
>   	if (abort_test)

[LTP] [PATCH v2 2/2] lib/tst_kconfig: Make use of boolean expression eval

[Cyril Hrubis]

Hi!
> > -void tst_kconfig_read(const char *const *kconfigs,
> > -                      struct tst_kconfig_res results[], size_t cnt)
> Hi Cyril,
> 
> New tst_kconfig_read() breaks the compilation of acct02 so we also need 
> to update acct02. :-)

Good catch, will fix that.

-- 
Cyril Hrubis
chrubis@suse.cz

[LTP] [PATCH v2 2/2] lib/tst_kconfig: Make use of boolean expression eval

[Li Wang]

On Tue, Oct 27, 2020 at 7:04 PM Cyril Hrubis <chrubis@suse.cz> wrote:

> Now each string in the kconfig[] array in tst_test structure is an
> boolean expression which is evaluated. All expressions has to be true in
> order for the test to continue.
>
> This also makes the parser for the kernel config a bit more robust as it
> was pointed out that there may have been cases where it could be mislead
> by hand edited config files.
>
> + Update the docs.
>
> Signed-off-by: Cyril Hrubis <chrubis@suse.cz>
> CC: Pengfei Xu <pengfei.xu@intel.com>
> ---
>
> v2:
>    - squashed the two patches since we are doing more extensive changes
>    - made the parser a bit more robust
>    - renamed a few fucntions and identifiers to make the code easier to
>      understand
>    - sprinkled the code with consts
>
>  doc/test-writing-guidelines.txt |  21 +-
>  include/tst_kconfig.h           |  34 +--
>  lib/newlib_tests/config06       |   1 +
>  lib/newlib_tests/test_kconfig.c |   1 +
>  lib/tst_kconfig.c               | 362 +++++++++++++++++++++-----------
>  5 files changed, 270 insertions(+), 149 deletions(-)
>  create mode 100644 lib/newlib_tests/config06
>
> diff --git a/doc/test-writing-guidelines.txt
> b/doc/test-writing-guidelines.txt
> index 1a51ef7c7..3c2ab7166 100644
> --- a/doc/test-writing-guidelines.txt
> +++ b/doc/test-writing-guidelines.txt
> @@ -1643,21 +1643,26 @@ on the system, disabled syscalls can be detected
> by checking for 'ENOSYS'
>  errno etc.
>
>  However in rare cases core kernel features couldn't be detected based on
> the
> -kernel userspace API and we have to resort to kernel .config parsing.
> +kernel userspace API and we have to resort to parse the kernel .config.
>
> -For this cases the test should set the 'NULL' terminated
> '.needs_kconfigs' array
> -of kernel config options required for the test. The config option can be
> -specified either as plain "CONFIG_FOO" in which case it's sufficient for
> the
> -test continue if it's set to any value (typically =y or =m). Or with a
> value
> -as "CONFIG_FOO=bar" in which case the value has to match as well. The
> test is
> -aborted with 'TCONF' if any of the required options were not set.
> +For this cases the test should set the 'NULL' terminated '.needs_kconfigs'
> +array of boolean expressions with constraints on the kconfig variables.
> The
> +boolean expression consits of variables, two binary operations '&' and
> '|',
> +negation '!' and correct sequence of parentesis '()'. Variables are
> expected
> +to be in a form of "CONFIG_FOO[=bar]".
> +
> +The test will continue to run if all expressions are evaluated to 'True'.
> +Missing variable is mapped to 'False' as well as variable with different
> than
> +specified value, e.g. 'CONFIG_FOO=bar' will evaluate to 'False' if the
> value
> +is anything else but 'bar'. If config variable is specified as plain
> +'CONFIG_FOO' it's evaluated to true it's set to any value (typically =y
> or =m).
>
>  [source,c]
>
>  -------------------------------------------------------------------------------
>  #include "tst_test.h"
>
>  static const char *kconfigs[] = {
> -       "CONFIG_X86_INTEL_UMIP",
> +       "CONFIG_X86_INTEL_UMIP | CONFIG_X86_UMIP",
>         NULL
>  };
>
> diff --git a/include/tst_kconfig.h b/include/tst_kconfig.h
> index 2d2cfd782..1bb21fea8 100644
> --- a/include/tst_kconfig.h
> +++ b/include/tst_kconfig.h
> @@ -6,27 +6,27 @@
>  #ifndef TST_KCONFIG_H__
>  #define TST_KCONFIG_H__
>
> -struct tst_kconfig_res {
> -       char match;
> -       char *value;
> +struct tst_kconfig_var {
> +       char id[64];
> +       unsigned int id_len;
> +       char choice;
> +       char *val;
>  };
>
>  /**
> - * Reads a kernel config and parses it for values defined in kconfigs
> array.
> + *
> + * Reads a kernel config, parses it and writes results into an array of
> + * tst_kconfig_var structures.
>   *
>   * The path to the kernel config should be autodetected in most of the
> cases as
>   * the code looks for know locations. It can be explicitely set/overrided
> with
>   * the KCONFIG_PATH environment variable as well.
>   *
> - * The kcofings array is expected to contain strings in a format
> "CONFIG_FOO"
> - * or "CONFIG_FOO=bar". The result array has to be suitably sized to fit
> the
> - * results.
> - *
> - * @param kconfigs array of config strings to look for
> - * @param results array to store results to
> - * @param cnt size of the arrays
> + * The caller has to initialize the tst_kconfig_var structure. The id has
> to be
> + * filled with config variable name such as 'CONFIG_FOO', the id_len
> should
> + * hold the id string length and the choice and val has to be zeroed.
>   *
> - * The match in the tst_kconfig_res structure is set as follows:
> + * After a call to this function each choice be set as follows:
>   *
>   *  'm' - config option set to m
>   *  'y' - config option set to y
> @@ -34,11 +34,13 @@ struct tst_kconfig_res {
>   *  'n' - config option is not set
>   *   0  - config option not found
>   *
> - * In the case that match is set to 'v' the value points to a newly
> allocated
> - * string that holds the value.
> + * In the case that match is set to 'v' the val pointer points to a newly
> + * allocated string that holds the value.
> + *
> + * @param vars An array of caller initalized tst_kconfig_var structures.
> + * @param vars_len Length of the vars array.
>   */
> -void tst_kconfig_read(const char *const kconfigs[],
> -                     struct tst_kconfig_res results[], size_t cnt);
> +void tst_kconfig_read(struct tst_kconfig_var vars[], size_t vars_len);
>
>  /**
>   * Checks if required kernel configuration options are set in the kernel
> diff --git a/lib/newlib_tests/config06 b/lib/newlib_tests/config06
> new file mode 100644
> index 000000000..b7db25411
> --- /dev/null
> +++ b/lib/newlib_tests/config06
> @@ -0,0 +1 @@
> +# Empty
> diff --git a/lib/newlib_tests/test_kconfig.c
> b/lib/newlib_tests/test_kconfig.c
> index d9c662fc5..183d55611 100644
> --- a/lib/newlib_tests/test_kconfig.c
> +++ b/lib/newlib_tests/test_kconfig.c
> @@ -14,6 +14,7 @@ static const char *kconfigs[] = {
>         "CONFIG_MMU",
>         "CONFIG_EXT4_FS=m",
>         "CONFIG_PGTABLE_LEVELS=4",
> +       "CONFIG_MMU & CONFIG_EXT4_FS=m",
>

The patchset looks awesome.

But a tiny issue was found from my test, the tst_kconfig_check() would be
failed to parse expression if reverse the sequence of the above string.

i.e.
-       "CONFIG_MMU & CONFIG_EXT4_FS=m",
+       "CONFIG_EXT4_FS=m & CONFIG_MMU",
(Core dumped here)

But trying with =Num, it gets different errors:

"CONFIG_MMU & CONFIG_PGTABLE_LEVELS=4",
(works well)

"CONFIG_PGTABLE_LEVELS=4 & CONFIG_MMU",
(print Expression not satisfied!)

-- 
Regards,
Li Wang
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linux.it/pipermail/ltp/attachments/20201102/dbf396b6/attachment-0001.htm>

[LTP] [PATCH v2 2/2] lib/tst_kconfig: Make use of boolean expression eval

[Cyril Hrubis]

Hi!
> But a tiny issue was found from my test, the tst_kconfig_check() would be
> failed to parse expression if reverse the sequence of the above string.
> 
> i.e.
> -       "CONFIG_MMU & CONFIG_EXT4_FS=m",
> +       "CONFIG_EXT4_FS=m & CONFIG_MMU",
> (Core dumped here)
> 
> But trying with =Num, it gets different errors:
> 
> "CONFIG_MMU & CONFIG_PGTABLE_LEVELS=4",
> (works well)
> 
> "CONFIG_PGTABLE_LEVELS=4 & CONFIG_MMU",
> (print Expression not satisfied!)

Looks like off by one in the strncmp() in the map() function, I will fix
that as well and send v3.

Thanks a lot for testing.

-- 
Cyril Hrubis
chrubis@suse.cz