1
0

expr.c 27 KB

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