scripts/parse_kconfig/cnfexpr.c

   1 #include "cnfexpr.h"
   2
   3 struct cnfexpr *cnf_sym(struct symlist *sl, bool not, struct symbol *sym);
   4 struct cnfexpr *cnf_eql(struct symlist *sl, bool not, struct symbol *sym1,
   5                         struct symbol *sym2);
   6 struct cnfexpr *cnf_or(struct cnfexpr *e1, struct cnfexpr *e2);
   7 struct cnfexpr *cnf_and(struct cnfexpr *e1, struct cnfexpr *e2);
   8 void free_cnf(struct cnfexpr *e);
   9
  10 struct cnfexpr *kconfig_cnfexpr(struct symlist *sl, bool nt, struct expr *expr) {
  11     struct stck {
  12         struct expr *expr;
  13         struct cnfexpr *cnf;
  14     };
  15     struct expr **back;
  16     int back_size = 2, back_pos = -1;
  17     back = malloc((unsigned) back_size * sizeof(struct expr *));
  18     struct stck *stack;
  19     int stack_size = 2, stack_pos = -1;
  20     stack = malloc((unsigned) stack_size * sizeof(struct stck));
  21     struct cnfexpr *rtrn = NULL;
  22
  23     while (expr != NULL) {
  24         if ((back_pos >= 0 && back[back_pos] != expr) || back_pos < 0) {
  25             if (++back_pos == back_size) {
  26                 back_size *= 2;
  27                 back =
  28                     realloc(back,
  29                             (unsigned) back_size * sizeof(struct expr *));
  30             }
  31             back[back_pos] = expr;
  32         }
  33         switch (expr->type) {
  34         case E_SYMBOL:
  35             rtrn = cnf_sym(sl, nt, expr->left.sym);
  36             goto go_up;
  37         case E_NOT:
  38             nt = !nt;
  39             if (rtrn == NULL)
  40                 expr = expr->left.expr;
  41             else
  42                 goto go_up;
  43             break;
  44         case E_OR:
  45         case E_AND:
  46             if (stack_pos < 0 || stack[stack_pos].expr != expr) {
  47                 if (rtrn == NULL) {
  48                     expr = expr->left.expr;
  49                 } else {
  50                     if (stack_size == ++stack_pos) {
  51                         stack_size *= 2;
  52                         stack =
  53                             realloc(stack,
  54                                     (unsigned) stack_size *
  55                                     sizeof(struct stck));
  56                     }
  57                     stack[stack_pos].expr = expr;
  58                     stack[stack_pos].cnf = rtrn;
  59                     expr = expr->right.expr;
  60                     rtrn = NULL;
  61                 }
  62             } else {
  63                 if ((!nt && expr->type == E_OR)
  64                     || (nt && expr->type == E_AND))
  65                     rtrn = cnf_or(stack[stack_pos].cnf, rtrn);
  66                 else
  67                     rtrn = cnf_and(stack[stack_pos].cnf, rtrn);
  68                 stack_pos--;
  69                 goto go_up;
  70             }
  71             break;
  72         case E_EQUAL:
  73             rtrn = cnf_eql(sl, nt, expr->left.sym, expr->right.sym);
  74             goto go_up;
  75         case E_UNEQUAL:
  76             rtrn = cnf_eql(sl, !nt, expr->left.sym, expr->right.sym);
  77             goto go_up;
  78         default:
  79             fprintf(stderr, "ERROR: Unknown expression type.\n");
  80         }
  81         continue;
  82
  83       go_up:
  84         if (--back_pos >= 0)
  85             expr = back[back_pos];
  86         else
  87             expr = NULL;
  88     }
  89
  90     free(back);
  91     free(stack);
  92     return rtrn;
  93 }
  94
  95 void cnf_printf(struct cnfexpr *wcnf) {
  96     if (wcnf == NULL) {
  97         printf("hey NULL\n");
  98         return;
  99     }
 100     switch (wcnf->type) {
 101     case CT_TRUE:
 102         printf("True\n");
 103         return;
 104     case CT_FALSE:
 105         printf("False\n");
 106         return;
 107     case CT_EXPR:
 108         break;
 109     }
 110     unsigned i, r;
 111     for (i = 0; i < wcnf->size; i++) {
 112         for (r = 0; r < wcnf->sizes[i]; r++) {
 113             printf("%d ", wcnf->exprs[i][r]);
 114         }
 115         if (i < wcnf->size - 1)
 116             printf("x ");
 117     }
 118     printf("\n");
 119 }
 120
 121 struct cnfexpr *cnf_sym(struct symlist *sl, bool not, struct symbol *sym) {
 122     struct cnfexpr *w = malloc(sizeof(struct cnfexpr));
 123     struct symlist_el *se = symlist_find(sl, sym->name);
 124     if (se == NULL) {
 125         if (!not)
 126             w->type = CT_FALSE;
 127         else
 128             w->type = CT_TRUE;
 129     } else {
 130         w->type = CT_EXPR;
 131         w->size = 1;
 132         w->sizes = malloc(sizeof(int));
 133         w->sizes[0] = 1;
 134         w->exprs = malloc(sizeof(int *));
 135         w->exprs[0] = malloc(sizeof(int));
 136         w->exprs[0][0] = (int) se->id;
 137         if (not)
 138             w->exprs[0][0] *= -1;
 139     }
 140     return w;
 141 }
 142
 143 struct cnfexpr *cnf_eql(struct symlist *sl, bool not, struct symbol *sym1,
 144                         struct symbol *sym2) {
 145     if (!strcmp(sym2->name, "m")) {
 146         struct cnfexpr *fls = malloc(sizeof(struct cnfexpr));
 147         if (!not)
 148             fls->type = CT_FALSE;
 149         else
 150             fls->type = CT_TRUE;
 151         return fls;
 152     }
 153     if (!strcmp(sym2->name, "n")) {
 154         struct cnfexpr *w = cnf_sym(sl, not, sym1);
 155         w->exprs[0][0] *= -1;
 156         return w;
 157     }
 158     if (!strcmp(sym2->name, "y")) {
 159         return cnf_sym(sl, not, sym1);
 160     }
 161
 162     struct cnfexpr *w1 = cnf_sym(sl, not, sym1);
 163     struct cnfexpr *w2 = cnf_sym(sl, not, sym2);
 164     struct cnfexpr *w3 = cnf_sym(sl, !not, sym1);
 165     struct cnfexpr *w4 = cnf_sym(sl, !not, sym2);
 166     struct cnfexpr *wa = cnf_or(w1, w2);
 167     struct cnfexpr *wb = cnf_or(w3, w4);
 168     struct cnfexpr *w = cnf_and(wa, wb);
 169     return w;
 170 }
 171
 172 struct cnfexpr *cnf_or(struct cnfexpr *e1, struct cnfexpr *e2) {
 173     switch (e1->type) {
 174     case CT_TRUE:
 175         free_cnf(e2);
 176         return e1;
 177     case CT_FALSE:
 178         free_cnf(e1);
 179         return e2;
 180     case CT_EXPR:
 181         switch (e2->type) {
 182         case CT_TRUE:
 183             free_cnf(e1);
 184             return e2;
 185         case CT_FALSE:
 186             free_cnf(e2);
 187             return e1;
 188         case CT_EXPR:
 189             break;
 190         }
 191         break;
 192     }
 193
 194     unsigned oldsize = e1->size;
 195     e1->size *= e2->size;
 196     e1->sizes = realloc(e1->sizes, e1->size * sizeof(int));
 197     e1->exprs = realloc(e1->exprs, e1->size * sizeof(int *));
 198     unsigned i1, i2;
 199     // Duplicate e2->size times e1
 200     for (i2 = 1; i2 < e2->size; i2++) {
 201         memcpy(e1->sizes + (i2 * oldsize), e1->sizes,
 202                oldsize * sizeof(int));
 203         for (i1 = 0; i1 < oldsize; i1++) {
 204             e1->exprs[(i2 * oldsize) + i1] =
 205                 malloc(e1->sizes[i1] * sizeof(int));
 206             memcpy(e1->exprs[(i2 * oldsize) + i1], e1->exprs[i1],
 207                    e1->sizes[i1] * sizeof(int));
 208         }
 209     }
 210     unsigned oldsizes;
 211     // Append e2->exprs to e1->exprs
 212     for (i2 = 0; i2 < e2->size; i2++) {
 213         for (i1 = 0; i1 < oldsize; i1++) {
 214             oldsizes = e1->sizes[(i2 * oldsize) + i1];
 215             e1->sizes[(i2 * oldsize) + i1] += e2->sizes[i2];
 216             e1->exprs[(i2 * oldsize) + i1] =
 217                 realloc(e1->exprs[(i2 * oldsize) + i1],
 218                         e1->sizes[(i2 * oldsize) + i1] * sizeof(int));
 219             memcpy(e1->exprs[(i2 * oldsize) + i1] + oldsizes,
 220                    e2->exprs[i2], e2->sizes[i2] * sizeof(int));
 221         }
 222     }
 223     free_cnf(e2);
 224     return e1;
 225 }
 226
 227 struct cnfexpr *cnf_and(struct cnfexpr *e1, struct cnfexpr *e2) {
 228     switch (e1->type) {
 229     case CT_FALSE:
 230         free_cnf(e2);
 231         return e1;
 232     case CT_TRUE:
 233         free_cnf(e1);
 234         return e2;
 235     case CT_EXPR:
 236         switch (e2->type) {
 237         case CT_FALSE:
 238             free_cnf(e1);
 239             return e2;
 240         case CT_TRUE:
 241             free_cnf(e2);
 242             return e1;
 243         case CT_EXPR:
 244             break;
 245         }
 246         break;
 247     }
 248
 249     unsigned oldsize = e1->size;
 250     e1->size += e2->size;
 251     e1->sizes = realloc(e1->sizes, e1->size * sizeof(int));
 252     e1->exprs = realloc(e1->exprs, e1->size * sizeof(int *));
 253     memcpy(e1->sizes + oldsize, e2->sizes, e2->size * sizeof(int));
 254     unsigned i;
 255     for (i = 0; i < e2->size; i++) {
 256         e1->exprs[oldsize + i] = malloc(e2->sizes[i] * sizeof(int));
 257         memcpy(e1->exprs[oldsize + i], e2->exprs[i],
 258                e2->sizes[i] * sizeof(int));
 259     }
 260     free_cnf(e2);
 261     return e1;
 262 }
 263
 264 void free_cnf(struct cnfexpr *e) {
 265     if (e->type != CT_EXPR) {
 266         free(e);
 267         return;
 268     }
 269     unsigned i;
 270     for (i = 0; i < e->size; i++) {
 271         free(e->exprs[i]);
 272     }
 273     free(e->exprs);
 274     free(e->sizes);
 275     free(e);
 276 }
 277
 278
 279 struct boolexp *printf_original(struct symlist *sl, struct expr *expr) {
 280     switch (expr->type) {
 281     case E_OR:
 282         printf("  OR\n");
 283         printf_original(sl, expr->left.expr);
 284         printf_original(sl, expr->right.expr);
 285         break;
 286     case E_AND:
 287         printf("  AND\n");
 288         printf_original(sl, expr->left.expr);
 289         printf_original(sl, expr->right.expr);
 290         break;
 291     case E_NOT:
 292         printf("  NOT\n");
 293         printf_original(sl, expr->left.expr);
 294         break;
 295     case E_EQUAL:
 296         printf("  = ");
 297         printf("%s ", expr->left.sym->name);
 298         if (!strcmp("y", expr->right.sym->name))
 299             printf("YES\n");
 300         else if (!strcmp("n", expr->right.sym->name))
 301             printf("NO\n");
 302         else if (!strcmp("m", expr->right.sym->name))
 303             printf("MODULE\n");
 304         else
 305             printf("%s\n", expr->left.sym->name);
 306         break;
 307     case E_UNEQUAL:
 308         printf("  != ");
 309         printf("%s ", expr->left.sym->name);
 310         if (!strcmp("y", expr->right.sym->name))
 311             printf("YES\n");
 312         else if (!strcmp("n", expr->right.sym->name))
 313             printf("NO\n");
 314         else
 315             printf("OTHER %s\n", expr->right.sym->name);
 316         break;
 317     case E_LIST:
 318         printf("  list\n");
 319         break;
 320     case E_SYMBOL:
 321         printf("  symbol");
 322         if (expr->left.sym->name != NULL)
 323                 printf(": %s", expr->left.sym->name);
 324         printf("\n");
 325         break;
 326     case E_RANGE:
 327         printf("  range\n");
 328         break;
 329     case E_NONE:
 330         printf("  none\n");
 331         break;
 332     default:
 333         printf("  ERROR\n");
 334         break;
 335     }
 336
 337 }