From e0b3ecbe06cb47d14ee64dbf1bdbd9cbc27ac648 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Karel=20Ko=C4=8D=C3=AD?= Date: Sun, 22 Mar 2015 18:53:50 +0100 Subject: kconfig_parser rewritten and now supports revers dependency MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Most of the kconfig_parser is changed. Now dependency are not copied before transfer to CNF and CNF expression is direcly extracted from kconfíg parsed output structures. --- programs/src/kconfig_parser/boolexp.c | 372 +++++++++++++++++++++++++++++++++- 1 file changed, 370 insertions(+), 2 deletions(-) (limited to 'programs/src/kconfig_parser/boolexp.c') diff --git a/programs/src/kconfig_parser/boolexp.c b/programs/src/kconfig_parser/boolexp.c index a41937a..c39b79c 100644 --- a/programs/src/kconfig_parser/boolexp.c +++ b/programs/src/kconfig_parser/boolexp.c @@ -54,6 +54,373 @@ struct boolexp *copy_kconfig_dep(struct symlist *sl, struct expr *expr) { } } +struct boolexp *copy_kconfig_f_dep(struct symlist *sl, struct expr *expr) { + switch (expr->type) { + case E_OR: + printf("OR\n"); + copy_kconfig_f_dep(sl, expr->left.expr); + copy_kconfig_f_dep(sl, expr->right.expr); + break; + case E_AND: + printf("AND\n"); + copy_kconfig_f_dep(sl, expr->left.expr); + copy_kconfig_f_dep(sl, expr->right.expr); + break; + case E_NOT: + printf("NOT\n"); + copy_kconfig_f_dep(sl, expr->left.expr); + break; + case E_EQUAL: + printf("= "); + printf("%s ", expr->left.sym->name); + if (!strcmp("y", expr->right.sym->name)) + printf("YES\n"); + else if (!strcmp("n", expr->right.sym->name)) + printf("NO\n"); + else + printf("PROBLEM\n"); + break; + case E_UNEQUAL: + printf("!= "); + printf("%s ", expr->left.sym->name); + if (!strcmp("y", expr->right.sym->name)) + printf("YES\n"); + else if (!strcmp("n", expr->right.sym->name)) + printf("NO\n"); + else + printf("OTHER %s\n", expr->right.sym->name); + break; + case E_LIST: + printf("list\n"); + break; + case E_SYMBOL: + printf("symbol\n"); + break; + case E_RANGE: + printf("range\n"); + break; + case E_NONE: + printf("none\n"); + break; + default: + printf("ERROR\n"); + break; + } + +} + +/*struct cnfexpr *kconfig_dep(struct symlist *sl, struct expr *expr) { + struct nd { + struct cnfexpr *cnfe; + struct expr *expr; + }; + struct cnfexpr *ret = NULL; + struct nd *wlist; + int wlist_size = 2, wlist_pos = -1; + struct expr **backstack; + int backstack_size = 2, backstack_pos = -1; + bool neg = false; + int ng; + + wlist = malloc((unsigned) wlist_size * sizeof(struct nd)); + backstack = malloc((unsigned) backstack_size * sizeof(struct expr *)); + + while (expr != NULL) { + if (neg) + ng = -1; + else + ng = 1; + if ((backstack_pos >= 0 && backstack[backstack_pos] != expr) + || backstack_pos < 0) { // left + if (++backstack_pos >= backstack_size) { + backstack_size *= 2; + backstack = + realloc(backstack, + (unsigned) backstack_size * + sizeof(struct expr *)); + } + backstack[backstack_pos] = expr; + switch (expr->type) { + case E_SYMBOL: + ret = malloc(sizeof(struct cnfexpr)); + ret->size = 1; + ret->sizes = malloc(sizeof(int)); + ret->sizes[0] = 1; + ret->exprs = malloc(sizeof(int *)); + ret->exprs[0] = malloc(sizeof(int)); + ret->exprs[0][0] = ng * (int) + symlist_find(sl, expr->left.sym->name)->id; + goto back; + case E_OR: + case E_AND: + if (expr->left.expr->type != E_SYMBOL) + expr = expr->left.expr; + break; + case E_NOT: + neg = !neg; // Is it working? + expr = expr->left.expr; + break; + case E_EQUAL: + case E_UNEQUAL: + ng = 1; + if (expr->type == E_UNEQUAL) + ng *= -1; + if (!strcmp("y", expr->right.sym->name)) { + // pass + } else if (!strcmp("n", expr->right.sym->name)) { + ng *= -1; + } else if (!strcmp("m", expr->right.sym->name)) { + ret = NULL; + goto back; + } else { + fprintf(stderr, "ERROR: kconfig_dep unknown equal\n"); + exit(1); + } + ret = malloc(sizeof(struct cnfexpr)); + ret->size = 1; + ret->sizes = malloc(sizeof(unsigned)); + ret->sizes[0] = 1; + ret->exprs = malloc(sizeof(int *)); + ret->exprs[0] = malloc(sizeof(int)); + ret->exprs[0][0] = ng * + (int) symlist_find(sl, expr->left.sym->name)->id; + goto back; + default: + fprintf(stderr, "ERROR: kconfig_dep unknown left state\n"); + exit(1); + } + } else { // right + switch (expr->type) { + case E_OR: + case E_AND: + if (wlist_pos >= 0 && wlist[wlist_pos].expr == expr) { + // navrat z prave strany v ret prava strana + if (ret == NULL) { + if ((!neg && expr->type == E_OR) + || (neg && expr->type == E_AND)) { + ret = wlist[wlist_pos--].cnfe; + } else { + struct cnfexpr *wcnf = wlist[wlist_pos--].cnfe; + unsigned i; + for (i = 0; i < wcnf->size; i++) { + free(wcnf->exprs[i]); + } + free(wcnf->sizes); + free(wcnf->exprs); + free(wcnf); + } + goto back; + } + if ((!neg && expr->type == E_OR) + || (neg && expr->type == E_AND)) { + struct cnfexpr *wcnf = wlist[wlist_pos--].cnfe; + unsigned oldsize = ret->size; + ret->size *= wcnf->size; + ret->sizes = + realloc(ret->sizes, ret->size * sizeof(int)); + ret->exprs = + realloc(ret->exprs, ret->size * sizeof(int *)); + unsigned i1, i2; + for (i1 = 1; i1 < wcnf->size; i1++) { + for (i2 = 0; i2 < oldsize; i2++) { + ret->sizes[(i1 * oldsize) + i2] = + ret->sizes[i2]; + ret->exprs[(i1 * oldsize) + i2] = + malloc(ret->sizes[i2] * sizeof(int)); + memcpy(ret->exprs[(i1 * oldsize) + i2], + ret->exprs[i2], + ret->sizes[i2] * sizeof(int)); + } + } + for (i1 = 0; i1 < wcnf->size; i1++) { + for (i2 = 0; i2 < oldsize; i2++) { + unsigned offset = + ret->sizes[(i1 * oldsize) + i2]; + ret->sizes[(i1 * oldsize) + i2] += + wcnf->sizes[i1]; + ret->exprs[(i1 * oldsize) + i2] = + realloc(ret->exprs + [(i1 * oldsize) + i2], + ret->sizes[(i1 * oldsize) + + i2] * sizeof(int)); + memcpy(ret->exprs[(i1 * oldsize) + i2] + + offset, wcnf->exprs[i1], + wcnf->sizes[i1] * sizeof(int)); + } + } + for (i1 = 0; i1 < wcnf->size; i1++) + free(wcnf->exprs[i1]); + free(wcnf->sizes); + free(wcnf->exprs); + free(wcnf); + } else { + struct cnfexpr *wcnf = wlist[wlist_pos--].cnfe; + unsigned oldsize = ret->size; + ret->size += wcnf->size; + ret->sizes = + realloc(ret->sizes, ret->size * sizeof(int)); + ret->exprs = + realloc(ret->exprs, ret->size * sizeof(int *)); + memcpy(ret->sizes + oldsize, wcnf->sizes, + wcnf->size * sizeof(int)); + memcpy(ret->exprs + oldsize, wcnf->exprs, + wcnf->size * sizeof(int *)); + free(wcnf->sizes); + free(wcnf->exprs); + free(wcnf); + } + goto back; + } else if (expr->left.expr->type == E_SYMBOL) { + if (expr->right.expr->type != E_SYMBOL) { + if (++wlist_pos >= wlist_size) { + wlist_size *= 2; + wlist = + realloc(wlist, + (unsigned) wlist_size * + sizeof(struct nd)); + } + wlist[wlist_pos].expr = expr; + struct cnfexpr *w = malloc(sizeof(struct cnfexpr)); + w->size = 1; + w->sizes = malloc(sizeof(int)); + w->sizes[0] = 1; + w->exprs = malloc(sizeof(int *)); + w->exprs[0] = malloc(sizeof(int)); + w->exprs[0][0] = ng * (int) + symlist_find(sl, + expr->left.expr->left.sym-> + name)->id; + wlist[wlist_pos].cnfe = w; + expr = expr->right.expr; + } else { + ret = malloc(sizeof(struct cnfexpr)); + if ((!neg && expr->type == E_OR) + || (neg && expr->type == E_AND)) { + ret->size = 1; + ret->sizes = malloc(sizeof(int)); + ret->sizes[0] = 2; + ret->exprs = malloc(sizeof(int *)); + ret->exprs[0] = malloc(2 * sizeof(int)); + ret->exprs[0][0] = ng * (int) + symlist_find(sl, + expr->left.expr->left. + sym->name)->id; + ret->exprs[0][1] = ng * (int) + symlist_find(sl, + expr->right.expr->left. + sym->name)->id; + } else { + ret->size = 2; + ret->sizes = malloc(2 * sizeof(int)); + ret->sizes[0] = 1; + ret->sizes[1] = 1; + ret->exprs = malloc(2 * sizeof(int *)); + ret->exprs[0] = malloc(sizeof(int)); + ret->exprs[1] = malloc(sizeof(int)); + ret->exprs[0][0] = + ng * (int) symlist_find(sl, + expr->left.expr-> + left.sym->name)-> + id; + ret->exprs[1][0] = + ng * (int) symlist_find(sl, + expr->right.expr-> + left.sym->name)-> + id; + } + goto back; + } + } else if (ret != NULL) { + if (expr->right.expr->type == E_SYMBOL) { + if ((!neg && expr->type == E_OR) + || (neg && expr->type == E_AND)) { + unsigned i; + for (i = 0; i < ret->size; i++) { + ret->sizes[i]++; + ret->exprs[i] = + realloc(ret->exprs[i], + ret->sizes[i] * sizeof(int)); + ret->exprs[i][ret->sizes[i] - 1] = + ng * (int) + symlist_find(sl, + expr->right.expr-> + left.sym->name)->id; + } + } else { + ret->size++; + ret->exprs = + realloc(ret->exprs, + ret->size * sizeof(int *)); + ret->exprs[ret->size - 1] = + malloc(sizeof(int)); + ret->sizes = + realloc(ret->sizes, + ret->size * sizeof(int)); + ret->sizes[ret->size - 1] = 1; + ret->exprs[ret->size - 1][0] = + ng * (int) symlist_find(sl, + expr->right. + expr->left.sym-> + name)->id; + } + goto back; + } else { + if (++wlist_pos >= wlist_size) { + wlist_size *= 2; + wlist = + realloc(wlist, + (unsigned) wlist_size * + sizeof(struct nd)); + } + wlist[wlist_pos].cnfe = ret; + wlist[wlist_pos].expr = expr; + expr = expr->right.expr; + } + } else { + // navrat z leva, v lefo je false + if (expr->right.expr->type == E_SYMBOL) { + if ((!neg && expr->type == E_OR) + || (neg && expr->type == E_AND)) { + } else + goto back; + } else { + if ((!neg && expr->type == E_OR) + || (neg && expr->type == E_AND)) { + } else { + } + } + } + break; + case E_NOT: + neg = !neg; + goto back; + default: + fprintf(stderr, + "ERROR: kconfig_dep unknown right state\n"); + } + } + continue; + back: + if (backstack_pos > 0) { + expr = backstack[--backstack_pos]; + } else + expr = NULL; + } + + return ret; +} + +void cnfprint(struct cnfexpr *wcnf) { + unsigned i, r; + for (i = 0; i < wcnf->size; i++) { + for (r = 0; r < wcnf->sizes[i]; r++) { + printf("%d ", wcnf->exprs[i][r]); + } + printf("x "); + } + printf("\n"); +}*/ + // This function is leaking memory! TODO struct boolexp *boolexp_cnf(struct boolexp *be) { if (be->type == BE_NOT) { @@ -64,7 +431,7 @@ struct boolexp *boolexp_cnf(struct boolexp *be) { nright = malloc(sizeof(struct boolexp)); if (be->left.be->type == BE_OR) root->type = BE_AND; - else if (be->left.be->type == BE_AND) + else root->type = BE_OR; nleft->type = BE_NOT; nright->type = BE_NOT; @@ -74,7 +441,7 @@ struct boolexp *boolexp_cnf(struct boolexp *be) { nright->left.be = be->right.be; be = root; } - } else if (be->type == BE_OR) + } else if (be->type == BE_OR) { if (be->left.be->type == BE_AND) { struct boolexp *root, *nleft, *nright; root = malloc(sizeof(struct boolexp)); @@ -106,6 +473,7 @@ struct boolexp *boolexp_cnf(struct boolexp *be) { nright->right.be = be->right.be->right.be; be = root; } + } if (be->type == BE_OR || be->type == BE_AND || be->type == BE_NOT) be->left.be = boolexp_cnf(be->left.be); if (be->type == BE_OR || be->type == BE_AND) -- cgit v1.2.3