10 files changed, 659 insertions, 0 deletions

diff --git a/scripts/parse_kconfig/.gitignore b/scripts/parse_kconfig/.gitignore
new file mode 100644
index 0000000..763d456
--- /dev/null
+++ b/scripts/parse_kconfig/.gitignore
@@ -0,0 +1 @@
+parser
diff --git a/scripts/parse_kconfig/Makefile b/scripts/parse_kconfig/Makefile
new file mode 100644
index 0000000..f582673
--- /dev/null
+++ b/scripts/parse_kconfig/Makefile
@@ -0,0 +1,19 @@
+.PHONY: all clean
+.SUFFIXES:
+
+all: parser
+
+KCONFIG_PREFIX = ../shared/kconfig
+include $(KCONFIG_PREFIX)/files.mk
+
+SRC  = parser.c \
+	       cnfexpr.c \
+	       symlist.c \
+	       output.c
+CFLAGS = -O0 -w -ggdb
+
+parser: $(SRC) $(KCONFIG_SRC)
+	gcc $(CFLAGS) -o $@ $^ -I$(KCONFIG_PREFIX)
+
+clean::
+	$(RM) parser
diff --git a/scripts/parse_kconfig/cnfexpr.c b/scripts/parse_kconfig/cnfexpr.c
new file mode 100644
index 0000000..3e1dcd6
--- /dev/null
+++ b/scripts/parse_kconfig/cnfexpr.c
@@ -0,0 +1,337 @@
+#include "cnfexpr.h"
+
+struct cnfexpr *cnf_sym(struct symlist *sl, bool not, struct symbol *sym);
+struct cnfexpr *cnf_eql(struct symlist *sl, bool not, struct symbol *sym1,
+                        struct symbol *sym2);
+struct cnfexpr *cnf_or(struct cnfexpr *e1, struct cnfexpr *e2);
+struct cnfexpr *cnf_and(struct cnfexpr *e1, struct cnfexpr *e2);
+void free_cnf(struct cnfexpr *e);
+
+struct cnfexpr *kconfig_cnfexpr(struct symlist *sl, bool nt, 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 *rtrn = 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:
+            rtrn = cnf_sym(sl, nt, expr->left.sym);
+            goto go_up;
+        case E_NOT:
+            nt = !nt;
+            if (rtrn == NULL)
+                expr = expr->left.expr;
+            else
+                goto go_up;
+            break;
+        case E_OR:
+        case E_AND:
+            if (stack_pos < 0 || stack[stack_pos].expr != expr) {
+                if (rtrn == 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 = rtrn;
+                    expr = expr->right.expr;
+                    rtrn = NULL;
+                }
+            } else {
+                if ((!nt && expr->type == E_OR)
+                    || (nt && expr->type == E_AND))
+                    rtrn = cnf_or(stack[stack_pos].cnf, rtrn);
+                else
+                    rtrn = cnf_and(stack[stack_pos].cnf, rtrn);
+                stack_pos--;
+                goto go_up;
+            }
+            break;
+        case E_EQUAL:
+            rtrn = cnf_eql(sl, nt, expr->left.sym, expr->right.sym);
+            goto go_up;
+        case E_UNEQUAL:
+            rtrn = cnf_eql(sl, !nt, 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 rtrn;
+}
+
+void cnf_printf(struct cnfexpr *wcnf) {
+    if (wcnf == NULL) {
+        printf("hey NULL\n");
+        return;
+    }
+    switch (wcnf->type) {
+    case CT_TRUE:
+        printf("True\n");
+        return;
+    case CT_FALSE:
+        printf("False\n");
+        return;
+    case CT_EXPR:
+        break;
+    }
+    unsigned i, r;
+    for (i = 0; i < wcnf->size; i++) {
+        for (r = 0; r < wcnf->sizes[i]; r++) {
+            printf("%d ", wcnf->exprs[i][r]);
+        }
+        if (i < wcnf->size - 1)
+            printf("x ");
+    }
+    printf("\n");
+}
+
+struct cnfexpr *cnf_sym(struct symlist *sl, bool not, struct symbol *sym) {
+    struct cnfexpr *w = malloc(sizeof(struct cnfexpr));
+    struct symlist_el *se = symlist_find(sl, sym->name);
+    if (se == NULL) {
+        if (!not)
+            w->type = CT_FALSE;
+        else
+            w->type = CT_TRUE;
+    } else {
+        w->type = CT_EXPR;
+        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] = (int) se->id;
+        if (not)
+            w->exprs[0][0] *= -1;
+    }
+    return w;
+}
+
+struct cnfexpr *cnf_eql(struct symlist *sl, bool not, struct symbol *sym1,
+                        struct symbol *sym2) {
+    if (!strcmp(sym2->name, "m")) {
+        struct cnfexpr *fls = malloc(sizeof(struct cnfexpr));
+        if (!not)
+            fls->type = CT_FALSE;
+        else
+            fls->type = CT_TRUE;
+        return fls;
+    }
+    if (!strcmp(sym2->name, "n")) {
+        struct cnfexpr *w = cnf_sym(sl, not, sym1);
+        w->exprs[0][0] *= -1;
+        return w;
+    }
+    if (!strcmp(sym2->name, "y")) {
+        return cnf_sym(sl, not, sym1);
+    }
+
+    struct cnfexpr *w1 = cnf_sym(sl, not, sym1);
+    struct cnfexpr *w2 = cnf_sym(sl, not, sym2);
+    struct cnfexpr *w3 = cnf_sym(sl, !not, sym1);
+    struct cnfexpr *w4 = cnf_sym(sl, !not, sym2);
+    struct cnfexpr *wa = cnf_or(w1, w2);
+    struct cnfexpr *wb = cnf_or(w3, w4);
+    struct cnfexpr *w = cnf_and(wa, wb);
+    return w;
+}
+
+struct cnfexpr *cnf_or(struct cnfexpr *e1, struct cnfexpr *e2) {
+    switch (e1->type) {
+    case CT_TRUE:
+        free_cnf(e2);
+        return e1;
+    case CT_FALSE:
+        free_cnf(e1);
+        return e2;
+    case CT_EXPR:
+        switch (e2->type) {
+        case CT_TRUE:
+            free_cnf(e1);
+            return e2;
+        case CT_FALSE:
+            free_cnf(e2);
+            return e1;
+        case CT_EXPR:
+            break;
+        }
+        break;
+    }
+
+    unsigned oldsize = e1->size;
+    e1->size *= e2->size;
+    e1->sizes = realloc(e1->sizes, e1->size * sizeof(int));
+    e1->exprs = realloc(e1->exprs, e1->size * sizeof(int *));
+    unsigned i1, i2;
+    // Duplicate e2->size times e1
+    for (i2 = 1; i2 < e2->size; i2++) {
+        memcpy(e1->sizes + (i2 * oldsize), e1->sizes,
+               oldsize * sizeof(int));
+        for (i1 = 0; i1 < oldsize; i1++) {
+            e1->exprs[(i2 * oldsize) + i1] =
+                malloc(e1->sizes[i1] * sizeof(int));
+            memcpy(e1->exprs[(i2 * oldsize) + i1], e1->exprs[i1],
+                   e1->sizes[i1] * sizeof(int));
+        }
+    }
+    unsigned oldsizes;
+    // Append e2->exprs to e1->exprs
+    for (i2 = 0; i2 < e2->size; i2++) {
+        for (i1 = 0; i1 < oldsize; i1++) {
+            oldsizes = e1->sizes[(i2 * oldsize) + i1];
+            e1->sizes[(i2 * oldsize) + i1] += e2->sizes[i2];
+            e1->exprs[(i2 * oldsize) + i1] =
+                realloc(e1->exprs[(i2 * oldsize) + i1],
+                        e1->sizes[(i2 * oldsize) + i1] * sizeof(int));
+            memcpy(e1->exprs[(i2 * oldsize) + i1] + oldsizes,
+                   e2->exprs[i2], e2->sizes[i2] * sizeof(int));
+        }
+    }
+    free_cnf(e2);
+    return e1;
+}
+
+struct cnfexpr *cnf_and(struct cnfexpr *e1, struct cnfexpr *e2) {
+    switch (e1->type) {
+    case CT_FALSE:
+        free_cnf(e2);
+        return e1;
+    case CT_TRUE:
+        free_cnf(e1);
+        return e2;
+    case CT_EXPR:
+        switch (e2->type) {
+        case CT_FALSE:
+            free_cnf(e1);
+            return e2;
+        case CT_TRUE:
+            free_cnf(e2);
+            return e1;
+        case CT_EXPR:
+            break;
+        }
+        break;
+    }
+
+    unsigned oldsize = e1->size;
+    e1->size += e2->size;
+    e1->sizes = realloc(e1->sizes, e1->size * sizeof(int));
+    e1->exprs = realloc(e1->exprs, e1->size * sizeof(int *));
+    memcpy(e1->sizes + oldsize, e2->sizes, e2->size * sizeof(int));
+    unsigned i;
+    for (i = 0; i < e2->size; i++) {
+        e1->exprs[oldsize + i] = malloc(e2->sizes[i] * sizeof(int));
+        memcpy(e1->exprs[oldsize + i], e2->exprs[i],
+               e2->sizes[i] * sizeof(int));
+    }
+    free_cnf(e2);
+    return e1;
+}
+
+void free_cnf(struct cnfexpr *e) {
+    if (e->type != CT_EXPR) {
+        free(e);
+        return;
+    }
+    unsigned i;
+    for (i = 0; i < e->size; i++) {
+        free(e->exprs[i]);
+    }
+    free(e->exprs);
+    free(e->sizes);
+    free(e);
+}
+
+
+struct boolexp *printf_original(struct symlist *sl, struct expr *expr) {
+    switch (expr->type) {
+    case E_OR:
+        printf("  OR\n");
+        printf_original(sl, expr->left.expr);
+        printf_original(sl, expr->right.expr);
+        break;
+    case E_AND:
+        printf("  AND\n");
+        printf_original(sl, expr->left.expr);
+        printf_original(sl, expr->right.expr);
+        break;
+    case E_NOT:
+        printf("  NOT\n");
+        printf_original(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 if (!strcmp("m", expr->right.sym->name))
+            printf("MODULE\n");
+        else
+            printf("%s\n", expr->left.sym->name);
+        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");
+        if (expr->left.sym->name != NULL)
+                printf(": %s", expr->left.sym->name);
+        printf("\n");
+        break;
+    case E_RANGE:
+        printf("  range\n");
+        break;
+    case E_NONE:
+        printf("  none\n");
+        break;
+    default:
+        printf("  ERROR\n");
+        break;
+    }
+
+}
diff --git a/scripts/parse_kconfig/cnfexpr.h b/scripts/parse_kconfig/cnfexpr.h
new file mode 100644
index 0000000..1d0edd4
--- /dev/null
+++ b/scripts/parse_kconfig/cnfexpr.h
@@ -0,0 +1,26 @@
+#ifndef _CNFEXPR_H_
+#define _CNFEXPR_H_
+
+#include <stdlib.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include "symlist.h"
+#include "lkc.h"
+
+enum cnfexpr_type {
+    CT_EXPR, CT_FALSE, CT_TRUE
+};
+
+struct cnfexpr {
+    enum cnfexpr_type type; 
+    int **exprs;
+    unsigned *sizes;
+    unsigned size;
+};
+
+struct cnfexpr *kconfig_cnfexpr(struct symlist *sl, bool nt, struct expr *expr);
+void cnf_printf(struct cnfexpr *);
+
+struct boolexp *printf_original(struct symlist *sl, struct expr *expr);
+
+#endif /* _CNFEXPR_H_ */
diff --git a/scripts/parse_kconfig/macros.h b/scripts/parse_kconfig/macros.h
new file mode 100644
index 0000000..95bb16f
--- /dev/null
+++ b/scripts/parse_kconfig/macros.h
@@ -0,0 +1,11 @@
+extern int verbose_level; // Defined in kconfig_parser.c
+
+#define Eprintf(...) fprintf(stderr, __VA_ARGS__)
+#define Wprintf(...) if (verbose_level > 1) printf(__VA_ARGS__)
+#define Iprintf(...) if (verbose_level > 2) printf(__VA_ARGS__)
+
+#ifndef DEBUG
+#define Dprintf(...)
+#else
+#define Dprintf(...) if (verbose_level > 3) printf(a, __VA_ARGS__)
+#endif /* DEBUG */
diff --git a/scripts/parse_kconfig/output.c b/scripts/parse_kconfig/output.c
new file mode 100644
index 0000000..989f4f0
--- /dev/null
+++ b/scripts/parse_kconfig/output.c
@@ -0,0 +1,65 @@
+#include "output.h"
+
+void fprint_rules_cnf(FILE * f, unsigned id, struct cnfexpr *cnf, bool nt) {
+    unsigned i, y;
+    switch (cnf->type) {
+    case CT_FALSE:
+        // Never satisfiable
+        if (!nt)
+            fprintf(f, "-");
+        fprintf(f, "%d\n", id);
+        break;
+    case CT_TRUE:
+        // Always satisfiable
+        break;
+    case CT_EXPR:
+        for (i = 0; i < cnf->size; i++) {
+            if (!nt)
+                fprintf(f, "-");
+            fprintf(f, "%d ", id);
+            for (y = 0; y < cnf->sizes[i] - 1; y++) {
+                fprintf(f, "%d ", cnf->exprs[i][y]);
+            }
+            fprintf(f, "%d ", cnf->exprs[i][cnf->sizes[i] - 1]);
+            fprintf(f, "\n");
+        }
+        break;
+    }
+}
+
+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);
+        return;
+    }
+    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->id, el->be, false);
+            }
+            if (el->re_be != NULL) {
+                fprint_rules_cnf(f, el->id, el->re_be, true);
+            }
+        }
+    }
+    fclose(f);
+}
+
+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;
+    }
+    size_t i;
+    for (i = 0; i < sl->pos; i++) {
+        fprintf(f, "%d:%s\n", sl->array[i].id, sl->array[i].name);
+    }
+    fclose(f);
+}
diff --git a/scripts/parse_kconfig/output.h b/scripts/parse_kconfig/output.h
new file mode 100644
index 0000000..b38c0bc
--- /dev/null
+++ b/scripts/parse_kconfig/output.h
@@ -0,0 +1,14 @@
+#ifndef _OUTPUT_H_
+#define _OUTPUT_H_
+
+#include <stdlib.h>
+#include <stdio.h>
+#include "symlist.h"
+
+#define DEFAULT_RULES_FILE "rules"
+#define DEFAULT_SYMBOL_MAP_FILE "symbol_map"
+
+void fprint_rules(struct symlist *sl, char *output);
+void fprint_symbol_map(struct symlist *sl, char *output);
+
+#endif /* _OUTPUT_H_ */
diff --git a/scripts/parse_kconfig/parser.c b/scripts/parse_kconfig/parser.c
new file mode 100644
index 0000000..933c26c
--- /dev/null
+++ b/scripts/parse_kconfig/parser.c
@@ -0,0 +1,112 @@
+#include <stdio.h>
+#include <ctype.h>
+#include <errno.h>
+#include <fcntl.h>
+#include <limits.h>
+#include <stdarg.h>
+#include <stdlib.h>
+#include <string.h>
+#include <signal.h>
+#include <unistd.h>
+#include <locale.h>
+#include <stdbool.h>
+#include <argp.h>
+#include "lkc.h"
+#include "symlist.h"
+#include "output.h"
+#include "macros.h"
+
+int verbose_level;
+char *file;
+
+struct symlist *gsymlist;
+int noname_num;
+
+void build_symlist();
+void cpy_dep();
+
+int main(int argc, char **argv) {
+    // TODO argp
+    verbose_level = 1;
+    int i;
+    for (i = 0; i < argc; i++) {
+        if (!strcmp(argv[i], "-v"))
+            verbose_level++;
+        else if (file == NULL)
+            file = argv[i];
+    }
+
+    if (argc < 2) {
+        Eprintf("No input file specified\n");
+        exit(1);
+    }
+    if (argc < 3) {
+        Eprintf("No output folder specified\n");
+        exit(2);
+    }
+
+    setlocale(LC_ALL, "");
+    bindtextdomain(PACKAGE, LOCALEDIR);
+    textdomain(PACKAGE);
+
+    conf_parse(argv[1]);
+    //sym_clear_all_valid();
+
+    gsymlist = symlist_create();
+
+    build_symlist();
+    cpy_dep();
+
+    char *rules_file, *symbol_map_file;
+    asprintf(&rules_file, "%s/%s", argv[2], DEFAULT_RULES_FILE);
+    asprintf(&symbol_map_file, "%s/%s", argv[2], DEFAULT_SYMBOL_MAP_FILE);
+    fprint_rules(gsymlist, rules_file);
+    fprint_symbol_map(gsymlist, symbol_map_file);
+    return 0;
+}
+
+void build_symlist() {
+    int i;
+    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 {
+                sym->name = malloc((9 + 7) * sizeof(char));
+                sprintf(sym->name, "NONAMEGEN%d", noname_num++);
+                symlist_add(gsymlist, sym->name);
+            }
+        }
+    }
+}
+
+void cpy_dep() {
+    int i;
+    struct symbol *sym;
+    struct symlist_el *el;
+    for_all_symbols(i, sym) {
+        if ((sym->type == S_BOOLEAN || sym->type == S_TRISTATE)
+            && strstr(sym->name, "NONAMEGEN") == NULL) {
+            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, sym->dir_dep.expr);
+                Iprintf("Direct:\n");
+                if (verbose_level > 2)
+                    cnf_printf(el->be);
+            }
+            if (sym->rev_dep.expr != NULL) {
+                if (verbose_level > 3)
+                    printf_original(gsymlist, sym->rev_dep.expr);
+                el->re_be = kconfig_cnfexpr(gsymlist, true, sym->rev_dep.expr);
+                Iprintf("Revers:\n");
+                if (verbose_level > 2)
+                    cnf_printf(el->re_be);
+            }
+        }
+    }
+}
diff --git a/scripts/parse_kconfig/symlist.c b/scripts/parse_kconfig/symlist.c
new file mode 100644
index 0000000..5423163
--- /dev/null
+++ b/scripts/parse_kconfig/symlist.c
@@ -0,0 +1,49 @@
+#include "symlist.h"
+
+struct symlist *symlist_create() {
+    struct symlist *ret;
+    ret = malloc(sizeof(struct symlist));
+    ret->size = 2;
+    ret->pos = 0;
+    ret->array = malloc(ret->size * sizeof(struct symlist_el));
+    return ret;
+}
+
+void symlist_add(struct symlist *sl, char *name) {
+    if (sl->pos >= sl->size) {
+        sl->size *= 2;
+        sl->array =
+            realloc(sl->array, sl->size * sizeof(struct symlist_el));
+    }
+    sl->array[sl->pos].id = sl->pos + 1;
+    sl->array[sl->pos].name = name;
+    sl->array[sl->pos].be = NULL;
+    sl->pos++;
+}
+
+struct symlist_el *symlist_find(struct symlist *sl, char *name) {
+    int i = 0;
+    while (i < sl->pos) {
+        if (!strcmp(name, sl->array[i].name))
+            return &sl->array[i];
+        i++;
+    }
+    return NULL;
+}
+
+void symlist_print(struct symlist *sl) {
+    int 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) {
+    free(sl->array);
+    free(sl);
+}
diff --git a/scripts/parse_kconfig/symlist.h b/scripts/parse_kconfig/symlist.h
new file mode 100644
index 0000000..88bf4b0
--- /dev/null
+++ b/scripts/parse_kconfig/symlist.h
@@ -0,0 +1,25 @@
+#ifndef _SYMLIST_H_
+#define _SYMLIST_H_
+
+#include <stdbool.h>
+#include <string.h>
+#include "cnfexpr.h"
+
+struct symlist_el {
+    unsigned int id;
+    char *name;
+    struct cnfexpr *be;
+    struct cnfexpr *re_be; // forward dependency
+};
+struct symlist {
+    struct symlist_el *array;
+    size_t size, pos;
+};
+
+struct symlist *symlist_create();
+void symlist_add(struct symlist *sl, char *name);
+struct symlist_el *symlist_find(struct symlist *sl, char *name);
+void symlist_print(struct symlist *sl);
+void symlist_free(struct symlist *sl);
+
+#endif /* _SYMLIST_H_ */