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