parse_kconfig changes before more changes come

This is commit that breaks parse_kconfig program...

7 files changed, 567 insertions, 110 deletions

diff --git a/scripts/parse_kconfig/cnfbuild.c b/scripts/parse_kconfig/cnfbuild.c
new file mode 100644
index 0000000..f9dd15f
--- /dev/null
+++ b/scripts/parse_kconfig/cnfbuild.c
@@ -0,0 +1,272 @@
+#include "cnfbuild.h"
+
+struct cnfexpr *kconfig_expr(struct symlist *sl, struct expr *expr) {
+    struct stck {
+        struct expr *expr;
+        struct cnfexpr *cnf;
+    };
+    struct expr **back;
+    int back_size = 2, back_pos = -1;
+    back = malloc((unsigned) back_size * sizeof(struct expr *));
+    struct stck *stack;
+    int stack_size = 2, stack_pos = -1;
+    stack = malloc((unsigned) stack_size * sizeof(struct stck));
+    struct cnfexpr *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 = cnf_sym(sl, expr->left.sym);
+            goto go_up;
+        case E_NOT:
+            if (rtn == NULL)
+                expr = expr->left.expr;
+            else {
+                rtn = cnf_not(sl, 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_size >= ++stack_pos) {
+                        stack_size *= 2;
+                        stack =
+                            realloc(stack,
+                                    (unsigned) stack_size *
+                                    sizeof(struct stck *));
+                    }
+                    stack[stack_pos].expr = expr;
+                    stack[stack_pos].cnf = rtn;
+                    expr = expr->right.expr;
+                    rtn = NULL;
+                }
+            } else {
+                if (expr->type == E_OR)
+                    rtn = cnf_or(sl, stack[stack_pos].cnf, rtn);
+                else
+                    rtn = cnf_and(sl, stack[stack_pos].cnf, rtn);
+                stack_pos--;
+                goto go_up;
+            }
+            break;
+        case E_EQUAL:
+            rtn = cnf_eql(sl, expr->left.sym, expr->right.sym);
+            goto go_up;
+        case E_UNEQUAL:
+            rtn =
+                cnf_not(sl, cnf_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 cnfexpr *cnfexpr_true(struct symlist *sl) {
+    struct cnfexpr *rtn;
+    rtn = malloc(sizeof(struct cnfexpr));
+    rtn->type = CT_TRUE;
+    rtn->id = 0;
+    rtn->out = NULL;
+    return rtn;
+}
+
+struct cnfexpr *cnfexpr_false(struct symlist *sl) {
+    struct cnfexpr *rtn;
+    rtn = malloc(sizeof(struct cnfexpr));
+    rtn->type = CT_FALSE;
+    rtn->id = 0;
+    rtn->out = NULL;
+    return rtn;
+}
+
+struct cnfexpr *cnf_sym(struct symlist *sl, struct symbol *sym) {
+    struct cnfexpr *rtn;
+    rtn = malloc(sizeof(struct cnfexpr));
+    rtn->type = CT_EXPR;
+    rtn->id = symlist_id(sym->name);
+    rtn->out = NULL;
+    if (rtn->id == 0)
+        rtn->type = CT_FALSE;
+    return rtn;
+}
+
+struct cnfexpr *cnf_eql(struct symlist *sl, struct symbol *sym1,
+                        struct symbol *sym2) {
+    if (!strcmp(sym2->name, "m")) {
+        struct cnfexpr *fls = malloc(sizeof(struct cnfexpr));
+        fls->type = CT_FALSE;
+        return fls;
+    }
+    if (!strcmp(sym2->name, "n"))
+        return cnf_not(sl, cnf_sym(sl, sym1));
+    if (!strcmp(sym2->name, "y"))
+        return cnf_sym(sl, sym1);
+
+    // sym1 <-> sym2
+    // (!sym1 || sym2) && (sym1 || !sym2)
+    return cnf_and(sl,
+                   cnf_or(sl, cnf_not(sl, cnf_sym(sl, sym1)),
+                          cnf_sym(sl, sym2)), cnf_or(sl, cnf_sym(sl,
+                                                                 sym1),
+                                                     cnf_not(sl,
+                                                             cnf_sym
+                                                             (sl, sym2))));
+}
+
+struct cnfexpr *cnf_or(struct symlist *sl, struct cnfexpr *e1,
+                       struct cnfexpr *e2) {
+    switch (e1->type) {
+    case CT_TRUE:
+        cnfexpr_free(e2);
+        return e1;
+    case CT_FALSE:
+        cnfexpr_free(e1);
+        return e2;
+    case CT_EXPR:
+        switch (e2->type) {
+        case CT_TRUE:
+            cnfexpr_free(e1);
+            return e2;
+        case CT_FALSE:
+            cnfexpr_free(e2);
+            return e1;
+        case CT_EXPR:
+            break;
+        }
+        break;
+    }
+
+    unsigned newid = (unsigned) symlist_adddummy(sl);
+    e1->out = output_rules_joinexpr(e1->out, e2->out);
+    if (e1->out == NULL)
+        e1->out = output_rules_newexpr();
+
+    // rtn <-> (e1 || e2)
+    // (!rtn || e1 || e2) && (rtn || !e1) && (rtn || !e2)
+    output_rules_symbol(e1->out, -(int) newid);
+    output_rules_symbol(e1->out, (int) e1->id);
+    output_rules_symbol(e1->out, (int) e2->id);
+    output_rules_endterm(e1->out);
+    output_rules_symbol(e1->out, (int) rtn->id);
+    output_rules_symbol(e1->out, -(int) e1->id);
+    output_rules_endterm(e1->out);
+    output_rules_symbol(e1->out, (int) rtn->id);
+    output_rules_symbol(e1->out, -(int) e2->id);
+    output_rules_endterm(e1->out);
+
+    cnfexpr_free(e2);
+    e1->id = newid;
+    return e1;
+}
+
+struct cnfexpr *cnf_and(struct symlist *sl, struct cnfexpr *e1,
+                        struct cnfexpr *e2) {
+    switch (e1->type) {
+    case CT_FALSE:
+        cnfexpr_free(e2);
+        return e1;
+    case CT_TRUE:
+        cnfexpr_free(e1);
+        return e2;
+    case CT_EXPR:
+        switch (e2->type) {
+        case CT_FALSE:
+            cnfexpr_free(e1);
+            return e2;
+        case CT_TRUE:
+            cnfexpr_free(e2);
+            return e1;
+        case CT_EXPR:
+            break;
+        }
+        break;
+    }
+
+    unsigned newid = (unsigned) symlist_adddummy(sl);
+    e1->out = output_rules_joinexpr(e1->out, e2->out);
+    if (e1->out == NULL)
+        e1->out = output_rules_newexpr();
+
+    // rtn <-> (e1 && e2)
+    // (rtn || !e1 || !e2) && (!rtn || e1) && (!rtn || e2)
+    output_rules_symbol(e1->out, (int) rtn->id);
+    output_rules_symbol(e1->out, -(int) e1->id);
+    output_rules_symbol(e1->out, -(int) e2->id);
+    output_rules_endterm(e1->out);
+    output_rules_symbol(e1->out, -(int) rtn->id);
+    output_rules_symbol(e1->out, (int) e1->id);
+    output_rules_endterm(e1->out);
+    output_rules_symbol(e1->out, -(int) rtn->id);
+    output_rules_symbol(e1->out, (int) e2->id);
+    output_rules_endterm(e1->out);
+
+    cnfexpr_free(e2);
+    e1->id = newid;
+    return e1;
+}
+
+struct cnfexpr *cnf_not(struct symlist *sl, struct cnfexpr *e) {
+    switch (e->type) {
+    case CT_FALSE:
+        e->type = CT_TRUE;
+        return e;
+    case CT_TRUE:
+        e->type = CT_FALSE;
+        return e;
+    case CT_EXPR:
+        break;
+    }
+    unsigned newid = (unsigned) symlist_adddummy(sl);
+
+    // rtn <-> !e
+    // (rtn || e) && (!rtn || !e)
+    output_rules_symbol(e->out, (int) newid);
+    output_rules_symbol(e->out, (int) e->id);
+    output_rules_endterm(e->out);
+    output_rules_symbol(e->out, -(int) newid);
+    output_rules_symbol(e->out, -(int) e->id);
+    output_rules_endterm(e->out);
+
+    e->id = newid;
+    return e;
+}
+
+struct cnfexpr *cnfexpr_copy(struct cnfexpr *e) {
+    struct cnfexpr *rtn;
+    rtn = malloc(sizeof(struct cnfexpr));
+    rtn->type = e->type;
+    rtn->id = e->id;
+    rtn->out = output_rules_copycnf(e->out);
+    return rtn;
+}
+
+void cnfexpr_free(struct cnfexpr *e) {
+    output_rules_freexpr(e->out);
+    free(e);
+}
diff --git a/scripts/parse_kconfig/cnfbuild.h b/scripts/parse_kconfig/cnfbuild.h
new file mode 100644
index 0000000..e042cce
--- /dev/null
+++ b/scripts/parse_kconfig/cnfbuild.h
@@ -0,0 +1,36 @@
+#include <stdlib.h>
+#include <stdbool.h>
+
+#include "symlist.h"
+#include <kconfig/lkc.h>
+#include "output.h"
+
+#ifndef _CNFBUILD_H_
+#define _CNFBUILD_H_
+
+enum cnfexpr_type {
+    CT_EXPR, CT_FALSE, CT_TRUE
+};
+
+struct cnfexpr {
+    enum cnfexpr_type type;
+    unsigned id;
+    struct output_expr *out;
+};
+
+struct cnfexpr *kconfig_expr(struct symlist *sl, struct expr *expr);
+
+struct cnfexpr *cnfexpr_true(struct symlist *sl);
+struct cnfexpr *cnfexpr_false(struct symlist *sl);
+struct cnfexpr *cnfexpr_sym(struct symlist *sl, struct symbol *sym);
+struct cnfexpr *cnfexpr_eql(struct symlist *sl, struct symbol *sym1,
+                        struct symbol *sym2);
+struct cnfexpr *cnfexpr_or(struct symlist *sl, struct cnfexpr *e1,
+                       struct cnfexpr *e2);
+struct cnfexpr *cnfexpr_and(struct symlist *sl, struct cnfexpr *e1,
+                        struct cnfexpr *e2);
+struct cnfexpr *cnfexpr_not(struct symlist *sl, struct cnfexpr *e);
+struct cnfexpr *cnfexpr_copy(struct cnfexpr *e);
+void cnfexpr_free(struct cnfexpr *e);
+
+#endif /* _CNFBUILD_H_ */
diff --git a/scripts/parse_kconfig/output.c b/scripts/parse_kconfig/output.c
index 064d787..3863139 100644
--- a/scripts/parse_kconfig/output.c
+++ b/scripts/parse_kconfig/output.c
@@ -1,61 +1,134 @@
 #include "output.h"
 
-void fprint_rules_cnf(FILE * f, struct cnfexpr *cnf) {
-    unsigned i, y;
-    switch (cnf->type) {
-    case CT_FALSE:
-        // Never satisfiable
-        // This should newer happen
-        fprintf(stderr,
-                "ERROR: Some rule is not satisfiable. But this should never happen.\n");
-        exit(28);
-    case CT_TRUE:
-        // Always satisfiable
-        break;
-    case CT_EXPR:
-        for (i = 0; i < cnf->size; i++) {
-            for (y = 0; y < cnf->sizes[i] - 1; y++) {
-                fprintf(f, "%d ", cnf->exprs[i][y]);
-            }
-            fprintf(f, "%d\n", cnf->exprs[i][cnf->sizes[i] - 1]);
-        }
-        break;
+FILE *frules, *fsymmap;
+
+int output_init(char *rules_file, char *symbolmap_file) {
+    if ((frules = fopen(rules_file, "w")) == NULL)
+        return 1;
+    if ((fsymmap = fopen(symbolmap_file, "w")) == NULL)
+        return 2;
+    return 0;
+}
+
+void output_finish(void) {
+    fclose(frules);
+    fclose(fsymmap);
+}
+
+
+// Functions for symbol_map
+void output_push_symbol(int id, char *name) {
+    fprintf(fsymmap, "%d:%s\n", id, name);
+}
+
+// Functions for rules
+struct output_expr *output_rules_newexpr(void) {
+    struct output_expr *rtn;
+    rtn = malloc(sizeof(struct output_expr));
+    rtn->terms_size = 1;
+    rtn->terms_pos = 0;
+    rtn->terms = malloc(rtn->terms_size * sizeof(int *));
+    rtn->terms_sizes = malloc(rtn->terms_size * sizeof(size_t));
+
+    rtn->w_term_size = 1;
+    rtn->w_term_pos = 0;
+    rtn->w_term = malloc(rtn->w_term_size * sizeof(int));
+
+    return rtn;
+}
+
+void output_rules_symbol(struct output_expr *ex, int id) {
+    if (++(ex->w_term_pos) >= ex->w_term_size) {
+        ex->w_term_size *= 2;
+        ex->w_term = realloc(ex->w_term, ex->w_term_size * sizeof(int));
     }
+    ex->w_term[ex->w_term_pos - 1] = id;
 }
 
-void fprint_rules(struct symlist *sl, char *output) {
-    FILE *f;
-    f = fopen(output, "w");
-    if (f == NULL) {
-        fprintf(stderr, "Can't create file: %s\n", output);
+void output_rules_endterm(struct output_expr *ex) {
+    if (ex->w_term_pos <= 0)
         return;
+    if (++(ex->terms_pos) >= ex->terms_size) {
+        ex->terms_size *= 2;
+        ex->terms = realloc(ex->terms, ex->terms_size * sizeof(int *));
+        ex->terms_sizes =
+            realloc(ex->terms_sizes, ex->terms_size * sizeof(size_t));
     }
-    size_t i;
-    struct symlist_el *el;
-    for (i = 0; i < sl->pos; i++) {
-        if (sl->array[i].be != NULL) {
-            el = sl->array + i;
-            if (el->be != NULL) {
-                fprint_rules_cnf(f, el->be);
-            }
-            if (el->re_be != NULL) {
-                fprint_rules_cnf(f, el->re_be);
-            }
-        }
+    ex->terms_sizes[ex->terms_pos - 1] = ex->w_term_pos;
+    ex->terms[ex->terms_pos - 1] = malloc(ex->w_term_pos * sizeof(int));
+    memcpy(ex->terms[ex->terms_pos - 1], ex->w_term,
+           ex->w_term_pos * sizeof(int));
+    ex->w_term_pos = 0;
+}
+
+struct output_expr *output_rules_joinexpr(struct output_expr *ex1,
+                                          struct output_expr *ex2) {
+    if (ex1 == NULL)
+        if (ex2 == NULL)
+            return NULL;
+        else
+            return ex2;
+    if (ex2 == NULL)
+        return ex1;
+
+    if ((ex1->terms_pos + ex2->terms_pos) >= ex1->terms_size) {
+        ex1->terms_size += ex2->terms_pos;
+        ex1->terms = realloc(ex1->terms, ex1->terms_size * sizeof(int *));
+        ex1->terms_sizes =
+            realloc(ex1->terms_sizes, ex1->terms_size * sizeof(size_t));
     }
-    fclose(f);
+    memcpy(ex1->terms + ex1->terms_pos - 1, ex2->terms,
+           ex2->terms_pos * sizeof(int *));
+    memcpy(ex1->terms_sizes + ex1->terms_size - 1, ex2->terms_sizes,
+           ex2->terms_pos * sizeof(size_t));
+    ex1->terms_pos += ex2->terms_pos;
+
+    ex1->w_term_pos = 0;
+    free(ex2->terms);
+    free(ex2->terms_sizes);
+    free(ex2);
+    return ex1;
 }
 
-void fprint_symbol_map(struct symlist *sl, char *output) {
-    FILE *f;
-    f = fopen(output, "w");
-    if (f == NULL) {
-        fprintf(stderr, "Can't create file: %s\n", output);
-        return;
+struct output_expr *output_rules_copycnf(struct output_expr *ex) {
+    struct output_expr *rtn;
+    rtn = malloc(sizeof(struct output_expr));
+    rtn->terms_size = ex->terms_size;
+    rtn->terms_pos = ex->terms_pos;
+    rtn->terms_sizes = malloc(rtn->terms_size * sizeof(size_t));
+    memcpy(rtn->terms_sizes, ex->terms_sizes,
+           rtn->terms_size * sizeof(size_t));
+    rtn->terms = malloc(rtn->terms_size * sizeof(int *));
+    size_t i;
+    for (i = 0; i < rtn->terms_pos; i++) {
+        rtn->terms[i] = malloc(ex->terms_sizes[i] * sizeof(int));
+        memcpy(rtn->terms[i], ex->terms[i],
+               ex->terms_sizes[i] * sizeof(int));
     }
+
+    ex->w_term_size = 1;
+    ex->w_term_pos = 0;
+    ex->w_term = malloc(ex->w_term_size * sizeof(int));
+    return rtn;
+}
+
+void output_rules_freexpr(struct output_expr *ex) {
     size_t i;
-    for (i = 0; i < sl->pos; i++) {
-        fprintf(f, "%d:%s\n", sl->array[i].id, sl->array[i].name);
+    for (i = 0; i < ex->terms_pos; i++) {
+        free(ex->terms[i]);
+    }
+    free(ex->terms);
+    free(ex->terms_sizes);
+    free(ex->w_term);
+    free(ex);
+}
+
+void output_rules_writexpr(struct output_expr *ex) {
+    size_t i, y;
+    for (i = 0; i < ex->terms_pos; i++) {
+        for (y = 0; y < ex->terms_sizes[i]; y++) {
+            fprintf(frules, "%d ", ex->terms[i][y]);
+        }
+        fprintf(frules, "\n");
     }
-    fclose(f);
 }
diff --git a/scripts/parse_kconfig/output.h b/scripts/parse_kconfig/output.h
index dd70768..a1b43aa 100644
--- a/scripts/parse_kconfig/output.h
+++ b/scripts/parse_kconfig/output.h
@@ -3,10 +3,33 @@
 
 #include <stdlib.h>
 #include <stdio.h>
+
 #include "symlist.h"
 #include <build_files.h>
 
-void fprint_rules(struct symlist *sl, char *output);
-void fprint_symbol_map(struct symlist *sl, char *output);
+int output_init(char *rules_file, char *symbolmap_file);
+void output_finish(void);
+
+// Functions for symbol_map
+void output_push_symbol(int id, char *name);
+
+// Functions for rules
+struct output_expr {
+    int **terms;
+    size_t *terms_sizes;
+    size_t terms_size, terms_pos;
+
+    int *w_term;
+    size_t w_term_size, w_term_pos;
+};
+
+struct output_expr *output_rules_newexpr(void);
+void output_rules_symbol(struct output_expr *ex, int id);
+void output_rules_endterm(struct output_expr *ex);
+struct output_expr *output_rules_joinexpr(struct output_expr *ex1,
+                                          struct output_expr *ex2);
+struct output_expr *output_rules_copycnf(struct output_expr *ex);
+void output_rules_freexpr(struct output_expr *ex);
+void output_rules_writexpr(struct output_expr *ex);
 
 #endif /* _OUTPUT_H_ */
diff --git a/scripts/parse_kconfig/parse.c b/scripts/parse_kconfig/parse.c
index e4e9ec5..e464159 100644
--- a/scripts/parse_kconfig/parse.c
+++ b/scripts/parse_kconfig/parse.c
@@ -4,6 +4,7 @@
 #include <locale.h>
 #include <stdbool.h>
 #include <libintl.h>
+
 #include <kconfig/lkc.h>
 #include "symlist.h"
 #include "output.h"
@@ -52,14 +53,13 @@ int main(int argc, char **argv) {
 
     gsymlist = symlist_create();
 
-    build_symlist();
-    cpy_dep();
-
     char *rules_file, *symbol_map_file;
     asprintf(&rules_file, "%s/%s", folder, DEFAULT_RULES_FILE);
     asprintf(&symbol_map_file, "%s/%s", folder, DEFAULT_SYMBOL_MAP_FILE);
-    fprint_rules(gsymlist, rules_file);
-    fprint_symbol_map(gsymlist, symbol_map_file);
+    output_init(rules_file, symbol_map_file);
+
+    build_symlist();
+
     return 0;
 }
 
@@ -68,23 +68,17 @@ void build_symlist() {
     struct symbol *sym;
     for_all_symbols(i, sym) {
         if (sym->type == S_BOOLEAN || sym->type == S_TRISTATE) {
-            if (sym->name != NULL) {
-                symlist_add(gsymlist, sym->name);
-            } else {
+            if (sym->name == NULL) {
                 sym->name = malloc((9 + 7) * sizeof(char));
                 sprintf(sym->name, "NONAMEGEN%d", noname_num++);
-                symlist_add(gsymlist, sym->name);
             }
+            symlist_add(gsymlist, sym->name);
         }
         struct property *prop;
         for_all_prompts(sym, prop) {
             gsymlist->array[gsymlist->pos - 1].prompt = true;
             break;
         }
-        for_all_defaults(sym, prop) {
-            gsymlist->array[gsymlist->pos - 1].def = true;
-            break;
-        }
     }
 }
 
@@ -92,33 +86,63 @@ void cpy_dep() {
     int i;
     struct symbol *sym;
     struct symlist_el *el;
+    unsigned el_id;
     for_all_symbols(i, sym) {
         if ((sym->type == S_BOOLEAN || sym->type == S_TRISTATE)) {
-            el = symlist_find(gsymlist, sym->name);
-            Iprintf("working: %s(%d)\n", sym->name, el->id);
-
-            if (sym->dir_dep.expr != NULL) {
-                if (verbose_level > 3)
-                    printf_original(gsymlist, sym->dir_dep.expr);
-                el->be =
-                    kconfig_cnfexpr(gsymlist, false, el->def, sym,
-                                    sym->dir_dep.expr);
-                Iprintf("Direct:\n");
-                if (verbose_level > 2)
-                    cnf_printf(el->be);
-            } else
-                el->be = NULL;
-            if (sym->rev_dep.expr != NULL) {
-                if (verbose_level > 3)
-                    printf_original(gsymlist, sym->rev_dep.expr);
-                el->re_be =
-                    kconfig_cnfexpr(gsymlist, true, el->def, sym,
-                                    sym->rev_dep.expr);
-                Iprintf("Revers:\n");
-                if (verbose_level > 2)
-                    cnf_printf(el->re_be);
-            } else
-                el->re_be = NULL;
+            el_id = symlist_id(gsymlist, sym->name);
+            el = &(gsymlist->array[el_id - 1]);
+
+            for_all_defaults(sym, prop) {
+                gsymlist->array[gsymlist->pos - 1].def = true;
+                struct cnfexpr *def =
+                    kconfig_cnfexpr(gsymlist, prop->expr);
+                if (el->def == NULL) {
+                    gsymlist->array[gsymlist->pos - 1].def = def;
+                } else {
+                    gsymlist->array[gsymlist->pos - 1].def =
+                        cnfexpr_or(gsymlist,
+                                   gsymlist->array[gsymlist->pos - 1].def,
+                                   def);
+                }
+            }
+            if (el->def == NULL)
+                el->cnfexpr_false(gsymlist);
+            if (sym->dir_dep.expr != NULL)
+                el->dep = kconfig_cnfexpr(gsymlist, sym->dir_dep.expr);
+            else
+                el->dep = cnfexpr_true(gsymlist);
+            if (sym->rev_dep.expr != NULL)
+                el->re_be = kconfig_cnfexpr(gsymlist, sym->rev_dep.expr);
+            else
+                el->rev_dep = cnfexpr_false(gsymlist);
+
+            if (el->prompt) {
+                struct cnfexpr *pw =
+                    cnfexpr_and(gsymlist,
+                                cnfexpr_or(gsymlist,
+                                           cnfexpr_not(gsymlist,
+                                                       cnfexpr_sym
+                                                       (gsymlist,
+                                                        sym->name)),
+                                           el->dep), cnfexpr_or(gsymlist,
+                                                                cnfexpr_not
+                                                                (gsymlist,
+                                                                 el->
+                                                                 rev_dep),
+                                                                cnfexpr_sym
+                                                                (gsymlist,
+                                                                 sym->
+                                                                 name)));
+                switch (pw->type) {
+                    case CT_EXPR:
+                        break;
+                    case CT_TRUE:
+                        break;
+                    case CT_FALSE:
+                        break;
+                }
+            } else {
+            }
         }
     }
 }
diff --git a/scripts/parse_kconfig/symlist.c b/scripts/parse_kconfig/symlist.c
index b0b90ea..f5f42ab 100644
--- a/scripts/parse_kconfig/symlist.c
+++ b/scripts/parse_kconfig/symlist.c
@@ -5,6 +5,7 @@ struct symlist *symlist_create() {
     ret = malloc(sizeof(struct symlist));
     ret->size = 1;
     ret->pos = 0;
+    ret->lastsym = 0;
     ret->array = malloc(ret->size * sizeof(struct symlist_el));
     return ret;
 }
@@ -15,39 +16,57 @@ void symlist_add(struct symlist *sl, char *name) {
         sl->array =
             realloc(sl->array, sl->size * sizeof(struct symlist_el));
     }
-    sl->array[sl->pos].id = (unsigned) sl->pos + 1;
     sl->array[sl->pos].name = name;
-    sl->array[sl->pos].be = NULL;
     sl->array[sl->pos].prompt = false;
-    sl->array[sl->pos].def = true;
+    sl->array[sl->pos].def = NULL;
+    sl->array[sl->pos].def_size = 0;
+    sl->array[sl->pos].dep = NULL;
+    sl->array[sl->pos].rev_dep = NULL;
     sl->pos++;
 }
 
-void symlist_set_prompt(struct symlist *sl, char *name, bool prompt) {
-    symlist_find(sl, name)->prompt = prompt;
+void symlist_closesym(struct symlist *sl) {
+    sl->lastsym = (unsigned) sl->pos;
+}
+
+unsigned symlist_adddummy(struct symlist *sl) {
+    if (sl->lastsym == 0)
+        fprintf(stderr,
+                "W: symlist adddummy, but lastsym is zero. This shouldn't happen.");
+    return sl->lastsym++;
 }
 
-// TODO faster implementation? Maybe binary search tree?
 struct symlist_el *symlist_find(struct symlist *sl, char *name) {
+    size_t i = symlist_id(sl, name);
+    if (i == 0)
+        return NULL;
+    else
+        return &(sl->array[i - 1]);
+}
+
+// TODO faster implementation? Maybe binary search tree?
+size_t symlist_id(struct symlist * sl, char *name) {
     size_t i = 0;
     while (i < sl->pos) {
         if (!strcmp(name, sl->array[i].name))
-            return &sl->array[i];
+            return i + 1;
         i++;
     }
-    return NULL;
+    return 0;
 }
 
 void symlist_print(struct symlist *sl) {
-    size_t i;
-    for (i = 0; i < sl->pos; i++) {
-        printf("%d:%s\n", sl->array[i].id, sl->array[i].name);
-        if (sl->array[i].be != NULL) {
-            printf("  ");
-            cnf_printf(sl->array[i].be);
-            printf("\n");
-        }
-    }
+    /*
+       size_t i;
+       for (i = 0; i < sl->pos; i++) {
+       printf("%d:%s\n", sl->array[i].id, sl->array[i].name);
+       if (sl->array[i].be != NULL) {
+       printf("  ");
+       cnf_printf(sl->array[i].be);
+       printf("\n");
+       }
+       }
+     */
 }
 
 void symlist_free(struct symlist *sl) {
diff --git a/scripts/parse_kconfig/symlist.h b/scripts/parse_kconfig/symlist.h
index 6f1f32f..7d24bd1 100644
--- a/scripts/parse_kconfig/symlist.h
+++ b/scripts/parse_kconfig/symlist.h
@@ -1,26 +1,36 @@
+#include <stdlib.h>
+#include <stdio.h>
 #include <stdbool.h>
 #include <string.h>
-#include "cnfexpr.h"
+#include <search.h>
+
+#include "cnfbuild.h"
+#include "output.h"
 
 #ifndef _SYMLIST_H_
 #define _SYMLIST_H_
 
 struct symlist_el {
-    unsigned int id;
     char *name;
-    bool prompt, def;
-    struct cnfexpr *be;
-    struct cnfexpr *re_be; // forward dependency
+    bool prompt;
+    struct cnfexpr *def;
+    size_t def_size;
+
+    struct cnfexpr *dep, *rev_dep;
 };
+
 struct symlist {
     struct symlist_el *array;
     size_t size, pos;
+    unsigned lastsym;
 };
 
 struct symlist *symlist_create();
 void symlist_add(struct symlist *sl, char *name);
-void symlist_set_prompt(struct symlist *sl, char *name, bool prompt);
+void symlist_closesym(struct symlist *sl);
+unsigned symlist_adddummy(struct symlist *sl);
 struct symlist_el *symlist_find(struct symlist *sl, char *name);
+size_t symlist_id(struct symlist *sl, char *name);
 void symlist_print(struct symlist *sl);
 void symlist_free(struct symlist *sl);