1
0

expr.c 25 KB

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