expr.c 27 KB

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