1
0

expr.c 25 KB

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