home *** CD-ROM | disk | FTP | other *** search
/ PC Welt 2006 November (DVD) / PCWELT_11_2006.ISO / casper / filesystem.squashfs / usr / src / linux-headers-2.6.17-6 / scripts / kconfig / expr.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-11-21  |  24.9 KB  |  1,100 lines
  1. /*
  2.  * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org>
  3.  * Released under the terms of the GNU GPL v2.0.
  4.  */
  5.  
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <string.h>
  9.  
  10. #define LKC_DIRECT_LINK
  11. #include "lkc.h"
  12.  
  13. #define DEBUG_EXPR    0
  14.  
  15. struct expr *expr_alloc_symbol(struct symbol *sym)
  16. {
  17.     struct expr *e = malloc(sizeof(*e));
  18.     memset(e, 0, sizeof(*e));
  19.     e->type = E_SYMBOL;
  20.     e->left.sym = sym;
  21.     return e;
  22. }
  23.  
  24. struct expr *expr_alloc_one(enum expr_type type, struct expr *ce)
  25. {
  26.     struct expr *e = malloc(sizeof(*e));
  27.     memset(e, 0, sizeof(*e));
  28.     e->type = type;
  29.     e->left.expr = ce;
  30.     return e;
  31. }
  32.  
  33. struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e2)
  34. {
  35.     struct expr *e = malloc(sizeof(*e));
  36.     memset(e, 0, sizeof(*e));
  37.     e->type = type;
  38.     e->left.expr = e1;
  39.     e->right.expr = e2;
  40.     return e;
  41. }
  42.  
  43. struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2)
  44. {
  45.     struct expr *e = malloc(sizeof(*e));
  46.     memset(e, 0, sizeof(*e));
  47.     e->type = type;
  48.     e->left.sym = s1;
  49.     e->right.sym = s2;
  50.     return e;
  51. }
  52.  
  53. struct expr *expr_alloc_and(struct expr *e1, struct expr *e2)
  54. {
  55.     if (!e1)
  56.         return e2;
  57.     return e2 ? expr_alloc_two(E_AND, e1, e2) : e1;
  58. }
  59.  
  60. struct expr *expr_alloc_or(struct expr *e1, struct expr *e2)
  61. {
  62.     if (!e1)
  63.         return e2;
  64.     return e2 ? expr_alloc_two(E_OR, e1, e2) : e1;
  65. }
  66.  
  67. struct expr *expr_copy(struct expr *org)
  68. {
  69.     struct expr *e;
  70.  
  71.     if (!org)
  72.         return NULL;
  73.  
  74.     e = malloc(sizeof(*org));
  75.     memcpy(e, org, sizeof(*org));
  76.     switch (org->type) {
  77.     case E_SYMBOL:
  78.         e->left = org->left;
  79.         break;
  80.     case E_NOT:
  81.         e->left.expr = expr_copy(org->left.expr);
  82.         break;
  83.     case E_EQUAL:
  84.     case E_UNEQUAL:
  85.         e->left.sym = org->left.sym;
  86.         e->right.sym = org->right.sym;
  87.         break;
  88.     case E_AND:
  89.     case E_OR:
  90.     case E_CHOICE:
  91.         e->left.expr = expr_copy(org->left.expr);
  92.         e->right.expr = expr_copy(org->right.expr);
  93.         break;
  94.     default:
  95.         printf("can't copy type %d\n", e->type);
  96.         free(e);
  97.         e = NULL;
  98.         break;
  99.     }
  100.  
  101.     return e;
  102. }
  103.  
  104. void expr_free(struct expr *e)
  105. {
  106.     if (!e)
  107.         return;
  108.  
  109.     switch (e->type) {
  110.     case E_SYMBOL:
  111.         break;
  112.     case E_NOT:
  113.         expr_free(e->left.expr);
  114.         return;
  115.     case E_EQUAL:
  116.     case E_UNEQUAL:
  117.         break;
  118.     case E_OR:
  119.     case E_AND:
  120.         expr_free(e->left.expr);
  121.         expr_free(e->right.expr);
  122.         break;
  123.     default:
  124.         printf("how to free type %d?\n", e->type);
  125.         break;
  126.     }
  127.     free(e);
  128. }
  129.  
  130. static int trans_count;
  131.  
  132. #define e1 (*ep1)
  133. #define e2 (*ep2)
  134.  
  135. static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2)
  136. {
  137.     if (e1->type == type) {
  138.         __expr_eliminate_eq(type, &e1->left.expr, &e2);
  139.         __expr_eliminate_eq(type, &e1->right.expr, &e2);
  140.         return;
  141.     }
  142.     if (e2->type == type) {
  143.         __expr_eliminate_eq(type, &e1, &e2->left.expr);
  144.         __expr_eliminate_eq(type, &e1, &e2->right.expr);
  145.         return;
  146.     }
  147.     if (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
  148.         e1->left.sym == e2->left.sym && (e1->left.sym->flags & (SYMBOL_YES|SYMBOL_NO)))
  149.         return;
  150.     if (!expr_eq(e1, e2))
  151.         return;
  152.     trans_count++;
  153.     expr_free(e1); expr_free(e2);
  154.     switch (type) {
  155.     case E_OR:
  156.         e1 = expr_alloc_symbol(&symbol_no);
  157.         e2 = expr_alloc_symbol(&symbol_no);
  158.         break;
  159.     case E_AND:
  160.         e1 = expr_alloc_symbol(&symbol_yes);
  161.         e2 = expr_alloc_symbol(&symbol_yes);
  162.         break;
  163.     default:
  164.         ;
  165.     }
  166. }
  167.  
  168. void expr_eliminate_eq(struct expr **ep1, struct expr **ep2)
  169. {
  170.     if (!e1 || !e2)
  171.         return;
  172.     switch (e1->type) {
  173.     case E_OR:
  174.     case E_AND:
  175.         __expr_eliminate_eq(e1->type, ep1, ep2);
  176.     default:
  177.         ;
  178.     }
  179.     if (e1->type != e2->type) switch (e2->type) {
  180.     case E_OR:
  181.     case E_AND:
  182.         __expr_eliminate_eq(e2->type, ep1, ep2);
  183.     default:
  184.         ;
  185.     }
  186.     e1 = expr_eliminate_yn(e1);
  187.     e2 = expr_eliminate_yn(e2);
  188. }
  189.  
  190. #undef e1
  191. #undef e2
  192.  
  193. int expr_eq(struct expr *e1, struct expr *e2)
  194. {
  195.     int res, old_count;
  196.  
  197.     if (e1->type != e2->type)
  198.         return 0;
  199.     switch (e1->type) {
  200.     case E_EQUAL:
  201.     case E_UNEQUAL:
  202.         return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym;
  203.     case E_SYMBOL:
  204.         return e1->left.sym == e2->left.sym;
  205.     case E_NOT:
  206.         return expr_eq(e1->left.expr, e2->left.expr);
  207.     case E_AND:
  208.     case E_OR:
  209.         e1 = expr_copy(e1);
  210.         e2 = expr_copy(e2);
  211.         old_count = trans_count;
  212.         expr_eliminate_eq(&e1, &e2);
  213.         res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
  214.                e1->left.sym == e2->left.sym);
  215.         expr_free(e1);
  216.         expr_free(e2);
  217.         trans_count = old_count;
  218.         return res;
  219.     case E_CHOICE:
  220.     case E_RANGE:
  221.     case E_NONE:
  222.         /* panic */;
  223.     }
  224.  
  225.     if (DEBUG_EXPR) {
  226.         expr_fprint(e1, stdout);
  227.         printf(" = ");
  228.         expr_fprint(e2, stdout);
  229.         printf(" ?\n");
  230.     }
  231.  
  232.     return 0;
  233. }
  234.  
  235. struct expr *expr_eliminate_yn(struct expr *e)
  236. {
  237.     struct expr *tmp;
  238.  
  239.     if (e) switch (e->type) {
  240.     case E_AND:
  241.         e->left.expr = expr_eliminate_yn(e->left.expr);
  242.         e->right.expr = expr_eliminate_yn(e->right.expr);
  243.         if (e->left.expr->type == E_SYMBOL) {
  244.             if (e->left.expr->left.sym == &symbol_no) {
  245.                 expr_free(e->left.expr);
  246.                 expr_free(e->right.expr);
  247.                 e->type = E_SYMBOL;
  248.                 e->left.sym = &symbol_no;
  249.                 e->right.expr = NULL;
  250.                 return e;
  251.             } else if (e->left.expr->left.sym == &symbol_yes) {
  252.                 free(e->left.expr);
  253.                 tmp = e->right.expr;
  254.                 *e = *(e->right.expr);
  255.                 free(tmp);
  256.                 return e;
  257.             }
  258.         }
  259.         if (e->right.expr->type == E_SYMBOL) {
  260.             if (e->right.expr->left.sym == &symbol_no) {
  261.                 expr_free(e->left.expr);
  262.                 expr_free(e->right.expr);
  263.                 e->type = E_SYMBOL;
  264.                 e->left.sym = &symbol_no;
  265.                 e->right.expr = NULL;
  266.                 return e;
  267.             } else if (e->right.expr->left.sym == &symbol_yes) {
  268.                 free(e->right.expr);
  269.                 tmp = e->left.expr;
  270.                 *e = *(e->left.expr);
  271.                 free(tmp);
  272.                 return e;
  273.             }
  274.         }
  275.         break;
  276.     case E_OR:
  277.         e->left.expr = expr_eliminate_yn(e->left.expr);
  278.         e->right.expr = expr_eliminate_yn(e->right.expr);
  279.         if (e->left.expr->type == E_SYMBOL) {
  280.             if (e->left.expr->left.sym == &symbol_no) {
  281.                 free(e->left.expr);
  282.                 tmp = e->right.expr;
  283.                 *e = *(e->right.expr);
  284.                 free(tmp);
  285.                 return e;
  286.             } else if (e->left.expr->left.sym == &symbol_yes) {
  287.                 expr_free(e->left.expr);
  288.                 expr_free(e->right.expr);
  289.                 e->type = E_SYMBOL;
  290.                 e->left.sym = &symbol_yes;
  291.                 e->right.expr = NULL;
  292.                 return e;
  293.             }
  294.         }
  295.         if (e->right.expr->type == E_SYMBOL) {
  296.             if (e->right.expr->left.sym == &symbol_no) {
  297.                 free(e->right.expr);
  298.                 tmp = e->left.expr;
  299.                 *e = *(e->left.expr);
  300.                 free(tmp);
  301.                 return e;
  302.             } else if (e->right.expr->left.sym == &symbol_yes) {
  303.                 expr_free(e->left.expr);
  304.                 expr_free(e->right.expr);
  305.                 e->type = E_SYMBOL;
  306.                 e->left.sym = &symbol_yes;
  307.                 e->right.expr = NULL;
  308.                 return e;
  309.             }
  310.         }
  311.         break;
  312.     default:
  313.         ;
  314.     }
  315.     return e;
  316. }
  317.  
  318. /*
  319.  * bool FOO!=n => FOO
  320.  */
  321. struct expr *expr_trans_bool(struct expr *e)
  322. {
  323.     if (!e)
  324.         return NULL;
  325.     switch (e->type) {
  326.     case E_AND:
  327.     case E_OR:
  328.     case E_NOT:
  329.         e->left.expr = expr_trans_bool(e->left.expr);
  330.         e->right.expr = expr_trans_bool(e->right.expr);
  331.         break;
  332.     case E_UNEQUAL:
  333.         // FOO!=n -> FOO
  334.         if (e->left.sym->type == S_TRISTATE) {
  335.             if (e->right.sym == &symbol_no) {
  336.                 e->type = E_SYMBOL;
  337.                 e->right.sym = NULL;
  338.             }
  339.         }
  340.         break;
  341.     default:
  342.         ;
  343.     }
  344.     return e;
  345. }
  346.  
  347. /*
  348.  * e1 || e2 -> ?
  349.  */
  350. struct expr *expr_join_or(struct expr *e1, struct expr *e2)
  351. {
  352.     struct expr *tmp;
  353.     struct symbol *sym1, *sym2;
  354.  
  355.     if (expr_eq(e1, e2))
  356.         return expr_copy(e1);
  357.     if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
  358.         return NULL;
  359.     if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
  360.         return NULL;
  361.     if (e1->type == E_NOT) {
  362.         tmp = e1->left.expr;
  363.         if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
  364.             return NULL;
  365.         sym1 = tmp->left.sym;
  366.     } else
  367.         sym1 = e1->left.sym;
  368.     if (e2->type == E_NOT) {
  369.         if (e2->left.expr->type != E_SYMBOL)
  370.             return NULL;
  371.         sym2 = e2->left.expr->left.sym;
  372.     } else
  373.         sym2 = e2->left.sym;
  374.     if (sym1 != sym2)
  375.         return NULL;
  376.     if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
  377.         return NULL;
  378.     if (sym1->type == S_TRISTATE) {
  379.         if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
  380.             ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
  381.              (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) {
  382.             // (a='y') || (a='m') -> (a!='n')
  383.             return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no);
  384.         }
  385.         if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
  386.             ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
  387.              (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) {
  388.             // (a='y') || (a='n') -> (a!='m')
  389.             return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod);
  390.         }
  391.         if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
  392.             ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
  393.              (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) {
  394.             // (a='m') || (a='n') -> (a!='y')
  395.             return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes);
  396.         }
  397.     }
  398.     if (sym1->type == S_BOOLEAN && sym1 == sym2) {
  399.         if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) ||
  400.             (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL))
  401.             return expr_alloc_symbol(&symbol_yes);
  402.     }
  403.  
  404.     if (DEBUG_EXPR) {
  405.         printf("optimize (");
  406.         expr_fprint(e1, stdout);
  407.         printf(") || (");
  408.         expr_fprint(e2, stdout);
  409.         printf(")?\n");
  410.     }
  411.     return NULL;
  412. }
  413.  
  414. struct expr *expr_join_and(struct expr *e1, struct expr *e2)
  415. {
  416.     struct expr *tmp;
  417.     struct symbol *sym1, *sym2;
  418.  
  419.     if (expr_eq(e1, e2))
  420.         return expr_copy(e1);
  421.     if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
  422.         return NULL;
  423.     if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
  424.         return NULL;
  425.     if (e1->type == E_NOT) {
  426.         tmp = e1->left.expr;
  427.         if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
  428.             return NULL;
  429.         sym1 = tmp->left.sym;
  430.     } else
  431.         sym1 = e1->left.sym;
  432.     if (e2->type == E_NOT) {
  433.         if (e2->left.expr->type != E_SYMBOL)
  434.             return NULL;
  435.         sym2 = e2->left.expr->left.sym;
  436.     } else
  437.         sym2 = e2->left.sym;
  438.     if (sym1 != sym2)
  439.         return NULL;
  440.     if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
  441.         return NULL;
  442.  
  443.     if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) ||
  444.         (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes))
  445.         // (a) && (a='y') -> (a='y')
  446.         return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
  447.  
  448.     if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) ||
  449.         (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no))
  450.         // (a) && (a!='n') -> (a)
  451.         return expr_alloc_symbol(sym1);
  452.  
  453.     if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) ||
  454.         (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod))
  455.         // (a) && (a!='m') -> (a='y')
  456.         return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
  457.  
  458.     if (sym1->type == S_TRISTATE) {
  459.         if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) {
  460.             // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
  461.             sym2 = e1->right.sym;
  462.             if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
  463.                 return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
  464.                                  : expr_alloc_symbol(&symbol_no);
  465.         }
  466.         if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) {
  467.             // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
  468.             sym2 = e2->right.sym;
  469.             if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
  470.                 return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
  471.                                  : expr_alloc_symbol(&symbol_no);
  472.         }
  473.         if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
  474.                ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
  475.                 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes)))
  476.             // (a!='y') && (a!='n') -> (a='m')
  477.             return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod);
  478.  
  479.         if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
  480.                ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
  481.                 (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes)))
  482.             // (a!='y') && (a!='m') -> (a='n')
  483.             return expr_alloc_comp(E_EQUAL, sym1, &symbol_no);
  484.  
  485.         if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
  486.                ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
  487.                 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod)))
  488.             // (a!='m') && (a!='n') -> (a='m')
  489.             return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
  490.  
  491.         if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) ||
  492.             (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) ||
  493.             (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) ||
  494.             (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes))
  495.             return NULL;
  496.     }
  497.  
  498.     if (DEBUG_EXPR) {
  499.         printf("optimize (");
  500.         expr_fprint(e1, stdout);
  501.         printf(") && (");
  502.         expr_fprint(e2, stdout);
  503.         printf(")?\n");
  504.     }
  505.     return NULL;
  506. }
  507.  
  508. static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2)
  509. {
  510. #define e1 (*ep1)
  511. #define e2 (*ep2)
  512.     struct expr *tmp;
  513.  
  514.     if (e1->type == type) {
  515.         expr_eliminate_dups1(type, &e1->left.expr, &e2);
  516.         expr_eliminate_dups1(type, &e1->right.expr, &e2);
  517.         return;
  518.     }
  519.     if (e2->type == type) {
  520.         expr_eliminate_dups1(type, &e1, &e2->left.expr);
  521.         expr_eliminate_dups1(type, &e1, &e2->right.expr);
  522.         return;
  523.     }
  524.     if (e1 == e2)
  525.         return;
  526.  
  527.     switch (e1->type) {
  528.     case E_OR: case E_AND:
  529.         expr_eliminate_dups1(e1->type, &e1, &e1);
  530.     default:
  531.         ;
  532.     }
  533.  
  534.     switch (type) {
  535.     case E_OR:
  536.         tmp = expr_join_or(e1, e2);
  537.         if (tmp) {
  538.             expr_free(e1); expr_free(e2);
  539.             e1 = expr_alloc_symbol(&symbol_no);
  540.             e2 = tmp;
  541.             trans_count++;
  542.         }
  543.         break;
  544.     case E_AND:
  545.         tmp = expr_join_and(e1, e2);
  546.         if (tmp) {
  547.             expr_free(e1); expr_free(e2);
  548.             e1 = expr_alloc_symbol(&symbol_yes);
  549.             e2 = tmp;
  550.             trans_count++;
  551.         }
  552.         break;
  553.     default:
  554.         ;
  555.     }
  556. #undef e1
  557. #undef e2
  558. }
  559.  
  560. static void expr_eliminate_dups2(enum expr_type type, struct expr **ep1, struct expr **ep2)
  561. {
  562. #define e1 (*ep1)
  563. #define e2 (*ep2)
  564.     struct expr *tmp, *tmp1, *tmp2;
  565.  
  566.     if (e1->type == type) {
  567.         expr_eliminate_dups2(type, &e1->left.expr, &e2);
  568.         expr_eliminate_dups2(type, &e1->right.expr, &e2);
  569.         return;
  570.     }
  571.     if (e2->type == type) {
  572.         expr_eliminate_dups2(type, &e1, &e2->left.expr);
  573.         expr_eliminate_dups2(type, &e1, &e2->right.expr);
  574.     }
  575.     if (e1 == e2)
  576.         return;
  577.  
  578.     switch (e1->type) {
  579.     case E_OR:
  580.         expr_eliminate_dups2(e1->type, &e1, &e1);
  581.         // (FOO || BAR) && (!FOO && !BAR) -> n
  582.         tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1)));
  583.         tmp2 = expr_copy(e2);
  584.         tmp = expr_extract_eq_and(&tmp1, &tmp2);
  585.         if (expr_is_yes(tmp1)) {
  586.             expr_free(e1);
  587.             e1 = expr_alloc_symbol(&symbol_no);
  588.             trans_count++;
  589.         }
  590.         expr_free(tmp2);
  591.         expr_free(tmp1);
  592.         expr_free(tmp);
  593.         break;
  594.     case E_AND:
  595.         expr_eliminate_dups2(e1->type, &e1, &e1);
  596.         // (FOO && BAR) || (!FOO || !BAR) -> y
  597.         tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1)));
  598.         tmp2 = expr_copy(e2);
  599.         tmp = expr_extract_eq_or(&tmp1, &tmp2);
  600.         if (expr_is_no(tmp1)) {
  601.             expr_free(e1);
  602.             e1 = expr_alloc_symbol(&symbol_yes);
  603.             trans_count++;
  604.         }
  605.         expr_free(tmp2);
  606.         expr_free(tmp1);
  607.         expr_free(tmp);
  608.         break;
  609.     default:
  610.         ;
  611.     }
  612. #undef e1
  613. #undef e2
  614. }
  615.  
  616. struct expr *expr_eliminate_dups(struct expr *e)
  617. {
  618.     int oldcount;
  619.     if (!e)
  620.         return e;
  621.  
  622.     oldcount = trans_count;
  623.     while (1) {
  624.         trans_count = 0;
  625.         switch (e->type) {
  626.         case E_OR: case E_AND:
  627.             expr_eliminate_dups1(e->type, &e, &e);
  628.             expr_eliminate_dups2(e->type, &e, &e);
  629.         default:
  630.             ;
  631.         }
  632.         if (!trans_count)
  633.             break;
  634.         e = expr_eliminate_yn(e);
  635.     }
  636.     trans_count = oldcount;
  637.     return e;
  638. }
  639.  
  640. struct expr *expr_transform(struct expr *e)
  641. {
  642.     struct expr *tmp;
  643.  
  644.     if (!e)
  645.         return NULL;
  646.     switch (e->type) {
  647.     case E_EQUAL:
  648.     case E_UNEQUAL:
  649.     case E_SYMBOL:
  650.     case E_CHOICE:
  651.         break;
  652.     default:
  653.         e->left.expr = expr_transform(e->left.expr);
  654.         e->right.expr = expr_transform(e->right.expr);
  655.     }
  656.  
  657.     switch (e->type) {
  658.     case E_EQUAL:
  659.         if (e->left.sym->type != S_BOOLEAN)
  660.             break;
  661.         if (e->right.sym == &symbol_no) {
  662.             e->type = E_NOT;
  663.             e->left.expr = expr_alloc_symbol(e->left.sym);
  664.             e->right.sym = NULL;
  665.             break;
  666.         }
  667.         if (e->right.sym == &symbol_mod) {
  668.             printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name);
  669.             e->type = E_SYMBOL;
  670.             e->left.sym = &symbol_no;
  671.             e->right.sym = NULL;
  672.             break;
  673.         }
  674.         if (e->right.sym == &symbol_yes) {
  675.             e->type = E_SYMBOL;
  676.             e->right.sym = NULL;
  677.             break;
  678.         }
  679.         break;
  680.     case E_UNEQUAL:
  681.         if (e->left.sym->type != S_BOOLEAN)
  682.             break;
  683.         if (e->right.sym == &symbol_no) {
  684.             e->type = E_SYMBOL;
  685.             e->right.sym = NULL;
  686.             break;
  687.         }
  688.         if (e->right.sym == &symbol_mod) {
  689.             printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name);
  690.             e->type = E_SYMBOL;
  691.             e->left.sym = &symbol_yes;
  692.             e->right.sym = NULL;
  693.             break;
  694.         }
  695.         if (e->right.sym == &symbol_yes) {
  696.             e->type = E_NOT;
  697.             e->left.expr = expr_alloc_symbol(e->left.sym);
  698.             e->right.sym = NULL;
  699.             break;
  700.         }
  701.         break;
  702.     case E_NOT:
  703.         switch (e->left.expr->type) {
  704.         case E_NOT:
  705.             // !!a -> a
  706.             tmp = e->left.expr->left.expr;
  707.             free(e->left.expr);
  708.             free(e);
  709.             e = tmp;
  710.             e = expr_transform(e);
  711.             break;
  712.         case E_EQUAL:
  713.         case E_UNEQUAL:
  714.             // !a='x' -> a!='x'
  715.             tmp = e->left.expr;
  716.             free(e);
  717.             e = tmp;
  718.             e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL;
  719.             break;
  720.         case E_OR:
  721.             // !(a || b) -> !a && !b
  722.             tmp = e->left.expr;
  723.             e->type = E_AND;
  724.             e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
  725.             tmp->type = E_NOT;
  726.             tmp->right.expr = NULL;
  727.             e = expr_transform(e);
  728.             break;
  729.         case E_AND:
  730.             // !(a && b) -> !a || !b
  731.             tmp = e->left.expr;
  732.             e->type = E_OR;
  733.             e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
  734.             tmp->type = E_NOT;
  735.             tmp->right.expr = NULL;
  736.             e = expr_transform(e);
  737.             break;
  738.         case E_SYMBOL:
  739.             if (e->left.expr->left.sym == &symbol_yes) {
  740.                 // !'y' -> 'n'
  741.                 tmp = e->left.expr;
  742.                 free(e);
  743.                 e = tmp;
  744.                 e->type = E_SYMBOL;
  745.                 e->left.sym = &symbol_no;
  746.                 break;
  747.             }
  748.             if (e->left.expr->left.sym == &symbol_mod) {
  749.                 // !'m' -> 'm'
  750.                 tmp = e->left.expr;
  751.                 free(e);
  752.                 e = tmp;
  753.                 e->type = E_SYMBOL;
  754.                 e->left.sym = &symbol_mod;
  755.                 break;
  756.             }
  757.             if (e->left.expr->left.sym == &symbol_no) {
  758.                 // !'n' -> 'y'
  759.                 tmp = e->left.expr;
  760.                 free(e);
  761.                 e = tmp;
  762.                 e->type = E_SYMBOL;
  763.                 e->left.sym = &symbol_yes;
  764.                 break;
  765.             }
  766.             break;
  767.         default:
  768.             ;
  769.         }
  770.         break;
  771.     default:
  772.         ;
  773.     }
  774.     return e;
  775. }
  776.  
  777. int expr_contains_symbol(struct expr *dep, struct symbol *sym)
  778. {
  779.     if (!dep)
  780.         return 0;
  781.  
  782.     switch (dep->type) {
  783.     case E_AND:
  784.     case E_OR:
  785.         return expr_contains_symbol(dep->left.expr, sym) ||
  786.                expr_contains_symbol(dep->right.expr, sym);
  787.     case E_SYMBOL:
  788.         return dep->left.sym == sym;
  789.     case E_EQUAL:
  790.     case E_UNEQUAL:
  791.         return dep->left.sym == sym ||
  792.                dep->right.sym == sym;
  793.     case E_NOT:
  794.         return expr_contains_symbol(dep->left.expr, sym);
  795.     default:
  796.         ;
  797.     }
  798.     return 0;
  799. }
  800.  
  801. bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
  802. {
  803.     if (!dep)
  804.         return false;
  805.  
  806.     switch (dep->type) {
  807.     case E_AND:
  808.         return expr_depends_symbol(dep->left.expr, sym) ||
  809.                expr_depends_symbol(dep->right.expr, sym);
  810.     case E_SYMBOL:
  811.         return dep->left.sym == sym;
  812.     case E_EQUAL:
  813.         if (dep->left.sym == sym) {
  814.             if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod)
  815.                 return true;
  816.         }
  817.         break;
  818.     case E_UNEQUAL:
  819.         if (dep->left.sym == sym) {
  820.             if (dep->right.sym == &symbol_no)
  821.                 return true;
  822.         }
  823.         break;
  824.     default:
  825.         ;
  826.     }
  827.      return false;
  828. }
  829.  
  830. struct expr *expr_extract_eq_and(struct expr **ep1, struct expr **ep2)
  831. {
  832.     struct expr *tmp = NULL;
  833.     expr_extract_eq(E_AND, &tmp, ep1, ep2);
  834.     if (tmp) {
  835.         *ep1 = expr_eliminate_yn(*ep1);
  836.         *ep2 = expr_eliminate_yn(*ep2);
  837.     }
  838.     return tmp;
  839. }
  840.  
  841. struct expr *expr_extract_eq_or(struct expr **ep1, struct expr **ep2)
  842. {
  843.     struct expr *tmp = NULL;
  844.     expr_extract_eq(E_OR, &tmp, ep1, ep2);
  845.     if (tmp) {
  846.         *ep1 = expr_eliminate_yn(*ep1);
  847.         *ep2 = expr_eliminate_yn(*ep2);
  848.     }
  849.     return tmp;
  850. }
  851.  
  852. void expr_extract_eq(enum expr_type type, struct expr **ep, struct expr **ep1, struct expr **ep2)
  853. {
  854. #define e1 (*ep1)
  855. #define e2 (*ep2)
  856.     if (e1->type == type) {
  857.         expr_extract_eq(type, ep, &e1->left.expr, &e2);
  858.         expr_extract_eq(type, ep, &e1->right.expr, &e2);
  859.         return;
  860.     }
  861.     if (e2->type == type) {
  862.         expr_extract_eq(type, ep, ep1, &e2->left.expr);
  863.         expr_extract_eq(type, ep, ep1, &e2->right.expr);
  864.         return;
  865.     }
  866.     if (expr_eq(e1, e2)) {
  867.         *ep = *ep ? expr_alloc_two(type, *ep, e1) : e1;
  868.         expr_free(e2);
  869.         if (type == E_AND) {
  870.             e1 = expr_alloc_symbol(&symbol_yes);
  871.             e2 = expr_alloc_symbol(&symbol_yes);
  872.         } else if (type == E_OR) {
  873.             e1 = expr_alloc_symbol(&symbol_no);
  874.             e2 = expr_alloc_symbol(&symbol_no);
  875.         }
  876.     }
  877. #undef e1
  878. #undef e2
  879. }
  880.  
  881. struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)
  882. {
  883.     struct expr *e1, *e2;
  884.  
  885.     if (!e) {
  886.         e = expr_alloc_symbol(sym);
  887.         if (type == E_UNEQUAL)
  888.             e = expr_alloc_one(E_NOT, e);
  889.         return e;
  890.     }
  891.     switch (e->type) {
  892.     case E_AND:
  893.         e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
  894.         e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
  895.         if (sym == &symbol_yes)
  896.             e = expr_alloc_two(E_AND, e1, e2);
  897.         if (sym == &symbol_no)
  898.             e = expr_alloc_two(E_OR, e1, e2);
  899.         if (type == E_UNEQUAL)
  900.             e = expr_alloc_one(E_NOT, e);
  901.         return e;
  902.     case E_OR:
  903.         e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
  904.         e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
  905.         if (sym == &symbol_yes)
  906.             e = expr_alloc_two(E_OR, e1, e2);
  907.         if (sym == &symbol_no)
  908.             e = expr_alloc_two(E_AND, e1, e2);
  909.         if (type == E_UNEQUAL)
  910.             e = expr_alloc_one(E_NOT, e);
  911.         return e;
  912.     case E_NOT:
  913.         return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym);
  914.     case E_UNEQUAL:
  915.     case E_EQUAL:
  916.         if (type == E_EQUAL) {
  917.             if (sym == &symbol_yes)
  918.                 return expr_copy(e);
  919.             if (sym == &symbol_mod)
  920.                 return expr_alloc_symbol(&symbol_no);
  921.             if (sym == &symbol_no)
  922.                 return expr_alloc_one(E_NOT, expr_copy(e));
  923.         } else {
  924.             if (sym == &symbol_yes)
  925.                 return expr_alloc_one(E_NOT, expr_copy(e));
  926.             if (sym == &symbol_mod)
  927.                 return expr_alloc_symbol(&symbol_yes);
  928.             if (sym == &symbol_no)
  929.                 return expr_copy(e);
  930.         }
  931.         break;
  932.     case E_SYMBOL:
  933.         return expr_alloc_comp(type, e->left.sym, sym);
  934.     case E_CHOICE:
  935.     case E_RANGE:
  936.     case E_NONE:
  937.         /* panic */;
  938.     }
  939.     return NULL;
  940. }
  941.  
  942. tristate expr_calc_value(struct expr *e)
  943. {
  944.     tristate val1, val2;
  945.     const char *str1, *str2;
  946.  
  947.     if (!e)
  948.         return yes;
  949.  
  950.     switch (e->type) {
  951.     case E_SYMBOL:
  952.         sym_calc_value(e->left.sym);
  953.         return e->left.sym->curr.tri;
  954.     case E_AND:
  955.         val1 = expr_calc_value(e->left.expr);
  956.         val2 = expr_calc_value(e->right.expr);
  957.         return E_AND(val1, val2);
  958.     case E_OR:
  959.         val1 = expr_calc_value(e->left.expr);
  960.         val2 = expr_calc_value(e->right.expr);
  961.         return E_OR(val1, val2);
  962.     case E_NOT:
  963.         val1 = expr_calc_value(e->left.expr);
  964.         return E_NOT(val1);
  965.     case E_EQUAL:
  966.         sym_calc_value(e->left.sym);
  967.         sym_calc_value(e->right.sym);
  968.         str1 = sym_get_string_value(e->left.sym);
  969.         str2 = sym_get_string_value(e->right.sym);
  970.         return !strcmp(str1, str2) ? yes : no;
  971.     case E_UNEQUAL:
  972.         sym_calc_value(e->left.sym);
  973.         sym_calc_value(e->right.sym);
  974.         str1 = sym_get_string_value(e->left.sym);
  975.         str2 = sym_get_string_value(e->right.sym);
  976.         return !strcmp(str1, str2) ? no : yes;
  977.     default:
  978.         printf("expr_calc_value: %d?\n", e->type);
  979.         return no;
  980.     }
  981. }
  982.  
  983. int expr_compare_type(enum expr_type t1, enum expr_type t2)
  984. {
  985. #if 0
  986.     return 1;
  987. #else
  988.     if (t1 == t2)
  989.         return 0;
  990.     switch (t1) {
  991.     case E_EQUAL:
  992.     case E_UNEQUAL:
  993.         if (t2 == E_NOT)
  994.             return 1;
  995.     case E_NOT:
  996.         if (t2 == E_AND)
  997.             return 1;
  998.     case E_AND:
  999.         if (t2 == E_OR)
  1000.             return 1;
  1001.     case E_OR:
  1002.         if (t2 == E_CHOICE)
  1003.             return 1;
  1004.     case E_CHOICE:
  1005.         if (t2 == 0)
  1006.             return 1;
  1007.     default:
  1008.         return -1;
  1009.     }
  1010.     printf("[%dgt%d?]", t1, t2);
  1011.     return 0;
  1012. #endif
  1013. }
  1014.  
  1015. void expr_print(struct expr *e, void (*fn)(void *, const char *), void *data, int prevtoken)
  1016. {
  1017.     if (!e) {
  1018.         fn(data, "y");
  1019.         return;
  1020.     }
  1021.  
  1022.     if (expr_compare_type(prevtoken, e->type) > 0)
  1023.         fn(data, "(");
  1024.     switch (e->type) {
  1025.     case E_SYMBOL:
  1026.         if (e->left.sym->name)
  1027.             fn(data, e->left.sym->name);
  1028.         else
  1029.             fn(data, "<choice>");
  1030.         break;
  1031.     case E_NOT:
  1032.         fn(data, "!");
  1033.         expr_print(e->left.expr, fn, data, E_NOT);
  1034.         break;
  1035.     case E_EQUAL:
  1036.         fn(data, e->left.sym->name);
  1037.         fn(data, "=");
  1038.         fn(data, e->right.sym->name);
  1039.         break;
  1040.     case E_UNEQUAL:
  1041.         fn(data, e->left.sym->name);
  1042.         fn(data, "!=");
  1043.         fn(data, e->right.sym->name);
  1044.         break;
  1045.     case E_OR:
  1046.         expr_print(e->left.expr, fn, data, E_OR);
  1047.         fn(data, " || ");
  1048.         expr_print(e->right.expr, fn, data, E_OR);
  1049.         break;
  1050.     case E_AND:
  1051.         expr_print(e->left.expr, fn, data, E_AND);
  1052.         fn(data, " && ");
  1053.         expr_print(e->right.expr, fn, data, E_AND);
  1054.         break;
  1055.     case E_CHOICE:
  1056.         fn(data, e->right.sym->name);
  1057.         if (e->left.expr) {
  1058.             fn(data, " ^ ");
  1059.             expr_print(e->left.expr, fn, data, E_CHOICE);
  1060.         }
  1061.         break;
  1062.     case E_RANGE:
  1063.         fn(data, "[");
  1064.         fn(data, e->left.sym->name);
  1065.         fn(data, " ");
  1066.         fn(data, e->right.sym->name);
  1067.         fn(data, "]");
  1068.         break;
  1069.     default:
  1070.       {
  1071.         char buf[32];
  1072.         sprintf(buf, "<unknown type %d>", e->type);
  1073.         fn(data, buf);
  1074.         break;
  1075.       }
  1076.     }
  1077.     if (expr_compare_type(prevtoken, e->type) > 0)
  1078.         fn(data, ")");
  1079. }
  1080.  
  1081. static void expr_print_file_helper(void *data, const char *str)
  1082. {
  1083.     fwrite(str, strlen(str), 1, data);
  1084. }
  1085.  
  1086. void expr_fprint(struct expr *e, FILE *out)
  1087. {
  1088.     expr_print(e, expr_print_file_helper, out, E_NONE);
  1089. }
  1090.  
  1091. static void expr_print_gstr_helper(void *data, const char *str)
  1092. {
  1093.     str_append((struct gstr*)data, str);
  1094. }
  1095.  
  1096. void expr_gstr_print(struct expr *e, struct gstr *gs)
  1097. {
  1098.     expr_print(e, expr_print_gstr_helper, gs, E_NONE);
  1099. }
  1100.