From 3fb6326fc36c69aa0b66de4823b116d7c0a9486c Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Karel=20Ko=C4=8D=C3=AD?= Date: Fri, 1 May 2015 20:55:43 +0200 Subject: parse_kconfig rewriten parse_kconfig should now generate full dependency. It is not transforming whole expression to CNF, but only pairs. --- scripts/parse_kconfig/boolexpr.c | 296 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 296 insertions(+) create mode 100644 scripts/parse_kconfig/boolexpr.c (limited to 'scripts/parse_kconfig/boolexpr.c') diff --git a/scripts/parse_kconfig/boolexpr.c b/scripts/parse_kconfig/boolexpr.c new file mode 100644 index 0000000..d29d238 --- /dev/null +++ b/scripts/parse_kconfig/boolexpr.c @@ -0,0 +1,296 @@ +#include "boolexpr.h" + +struct boolexpr *boolexpr_eql(struct symlist *sl, struct symbol *sym1, + struct symbol *sym2); + +struct boolexpr *boolexpr_kconfig(struct symlist *sl, struct expr *expr) { + struct stck { + struct expr *expr; + struct boolexpr *bl; + }; + struct expr **back; + int back_size = 2, back_pos = -1; + back = malloc((unsigned) back_size * sizeof(struct expr *)); + struct stck *stack; + unsigned stack_size = 2; + int stack_pos = -1; + stack = malloc((unsigned) stack_size * sizeof(struct stck)); + struct boolexpr *rtn = NULL; + + while (expr != NULL) { + if ((back_pos >= 0 && back[back_pos] != expr) || back_pos < 0) { + if (++back_pos >= back_size) { + back_size *= 2; + back = + realloc(back, + (unsigned) back_size * sizeof(struct expr *)); + } + back[back_pos] = expr; + } + switch (expr->type) { + case E_SYMBOL: + rtn = boolexpr_sym(sl, expr->left.sym); + goto go_up; + case E_NOT: + if (rtn == NULL) + expr = expr->left.expr; + else { + rtn = boolexpr_not(rtn); + goto go_up; + } + break; + case E_OR: + case E_AND: + if (stack_pos < 0 || stack[stack_pos].expr != expr) { + if (rtn == NULL) + expr = expr->left.expr; + else { + if (++stack_pos >= stack_size) { + stack_size *= 2; + stack = + realloc(stack, + stack_size * sizeof(struct stck)); + } + stack[stack_pos].expr = expr; + stack[stack_pos].bl = rtn; + expr = expr->right.expr; + rtn = NULL; + } + } else { + if (expr->type == E_OR) + rtn = boolexpr_or(stack[stack_pos].bl, rtn); + else + rtn = boolexpr_and(stack[stack_pos].bl, rtn); + stack_pos--; + goto go_up; + } + break; + case E_EQUAL: + rtn = boolexpr_eql(sl, expr->left.sym, expr->right.sym); + goto go_up; + case E_UNEQUAL: + rtn = + boolexpr_not(boolexpr_eql + (sl, expr->left.sym, expr->right.sym)); + goto go_up; + default: + fprintf(stderr, "ERROR: Unknown expression type.\n"); + } + continue; + + go_up: + if (--back_pos >= 0) + expr = back[back_pos]; + else + expr = NULL; + } + + free(back); + free(stack); + + return rtn; +} + +struct boolexpr *boolexpr_true() { + struct boolexpr *rtn; + rtn = malloc(sizeof(struct boolexpr)); + rtn->type = BT_TRUE; + rtn->overusage = 0; + rtn->id = 0; + return rtn; +} + +struct boolexpr *boolexpr_false() { + struct boolexpr *rtn; + rtn = malloc(sizeof(struct boolexpr)); + rtn->type = BT_FALSE; + rtn->overusage = 0; + rtn->id = 0; + return rtn; +} + +struct boolexpr *boolexpr_sym(struct symlist *sl, struct symbol *sym) { + struct boolexpr *rtn; + rtn = malloc(sizeof(struct boolexpr)); + rtn->overusage = 0; + rtn->id = symlist_id(sl, sym->name); + if (rtn->id != 0) + rtn->type = BT_SYM; + else + rtn->type = BT_FALSE; + return rtn; +} + +struct boolexpr *boolexpr_eql(struct symlist *sl, struct symbol *sym1, + struct symbol *sym2) { + if (!strcmp(sym2->name, "m")) { + struct boolexpr *rtn = malloc(sizeof(struct boolexpr)); + rtn->overusage = 0; + rtn->id = 0; + rtn->type = BT_FALSE; + return rtn; + } + if (!strcmp(sym2->name, "n")) + return boolexpr_not(boolexpr_sym(sl, sym1)); + if (!strcmp(sym2->name, "y")) + return boolexpr_sym(sl, sym1); + + // sym1 <-> sym2 + // (!sym1 || sym2) && (sym1 || !sym2) + return + boolexpr_and(boolexpr_or + (boolexpr_not(boolexpr_sym(sl, sym1)), + boolexpr_sym(sl, sym2)), boolexpr_or(boolexpr_sym(sl, + sym1), + boolexpr_not + (boolexpr_sym + (sl, sym2)))); +} + +struct boolexpr *boolexpr_or(struct boolexpr *e1, struct boolexpr *e2) { + switch (e1->type) { + case BT_TRUE: + boolexpr_free(e2); + return e1; + case BT_FALSE: + boolexpr_free(e1); + return e2; + default: + switch (e2->type) { + case BT_TRUE: + boolexpr_free(e1); + return e2; + case BT_FALSE: + boolexpr_free(e2); + return e1; + default: + break; + } + break; + } + + struct boolexpr *rtn; + rtn = malloc(sizeof(struct boolexpr)); + rtn->type = BT_OR; + rtn->overusage = 0; + rtn->id = 0; + rtn->left = e1; + rtn->right = e2; + return rtn; +} + +struct boolexpr *boolexpr_and(struct boolexpr *e1, struct boolexpr *e2) { + switch (e1->type) { + case BT_FALSE: + boolexpr_free(e2); + return e1; + case BT_TRUE: + boolexpr_free(e1); + return e2; + default: + switch (e2->type) { + case BT_FALSE: + boolexpr_free(e1); + return e2; + case BT_TRUE: + boolexpr_free(e2); + return e1; + default: + break; + } + break; + } + + struct boolexpr *rtn; + rtn = malloc(sizeof(struct boolexpr)); + rtn->type = BT_AND; + rtn->overusage = 0; + rtn->id = 0; + rtn->left = e1; + rtn->right = e2; + return rtn; +} + +struct boolexpr *boolexpr_not(struct boolexpr *e) { + switch (e->type) { + case BT_FALSE: + e->type = BT_TRUE; + return e; + case BT_TRUE: + e->type = BT_FALSE; + return e; + default: + break; + } + struct boolexpr *rtn; + rtn = malloc(sizeof(struct boolexpr)); + rtn->type = BT_NOT; + rtn->overusage = 0; + rtn->id = 0; + rtn->left = e; + return rtn; +} + +void boolexpr_free(struct boolexpr *e) { + struct boolexpr **stack; + size_t stack_size = 2, stack_pos = 0; + stack = malloc(stack_size * sizeof(struct boolexpr *)); + + struct boolexpr *m; + while (e != NULL) { + m = e; + switch (e->type) { + case BT_OR: + case BT_AND: + if (++stack_pos >= stack_size) { + stack_size *= 2; + stack = + realloc(stack, stack_size * sizeof(struct boolexpr *)); + } + stack[stack_pos - 1] = e->right; + case BT_NOT: + e = e->left; + break; + default: + if (stack_pos > 0) + e = stack[--stack_pos]; + else + e = NULL; + } + if (m->overusage > 0) + m->overusage--; + else + free(m); + } + free(stack); +} + +struct boolexpr *boolexpr_copy(struct boolexpr *e) { + struct boolexpr **stack; + size_t stack_size = 2, stack_pos = 0; + stack = malloc(stack_size * sizeof(struct boolexpr *)); + + while (e != NULL) { + e->overusage++; + switch (e->type) { + case BT_OR: + case BT_AND: + if (++stack_pos >= stack_size) { + stack_size *= 2; + stack = + realloc(stack, stack_size * sizeof(struct boolexpr *)); + } + stack[stack_pos - 1] = e->right; + case BT_NOT: + e = e->left; + break; + default: + if (stack_pos > 0) + e = stack[--stack_pos]; + else + e = NULL; + } + } + free(stack); + return e; +} -- cgit v1.2.3