expr.c 30 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305
  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. fprintf(stderr, "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. break;
  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. fprintf(stderr, "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. /*
  123. * expr_eliminate_eq() helper.
  124. *
  125. * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does
  126. * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared
  127. * against all other leaves. Two equal leaves are both replaced with either 'y'
  128. * or 'n' as appropriate for 'type', to be eliminated later.
  129. */
  130. static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2)
  131. {
  132. /* Recurse down to leaves */
  133. if (e1->type == type) {
  134. __expr_eliminate_eq(type, &e1->left.expr, &e2);
  135. __expr_eliminate_eq(type, &e1->right.expr, &e2);
  136. return;
  137. }
  138. if (e2->type == type) {
  139. __expr_eliminate_eq(type, &e1, &e2->left.expr);
  140. __expr_eliminate_eq(type, &e1, &e2->right.expr);
  141. return;
  142. }
  143. /* e1 and e2 are leaves. Compare them. */
  144. if (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
  145. e1->left.sym == e2->left.sym &&
  146. (e1->left.sym == &symbol_yes || e1->left.sym == &symbol_no))
  147. return;
  148. if (!expr_eq(e1, e2))
  149. return;
  150. /* e1 and e2 are equal leaves. Prepare them for elimination. */
  151. trans_count++;
  152. expr_free(e1); expr_free(e2);
  153. switch (type) {
  154. case E_OR:
  155. e1 = expr_alloc_symbol(&symbol_no);
  156. e2 = expr_alloc_symbol(&symbol_no);
  157. break;
  158. case E_AND:
  159. e1 = expr_alloc_symbol(&symbol_yes);
  160. e2 = expr_alloc_symbol(&symbol_yes);
  161. break;
  162. default:
  163. ;
  164. }
  165. }
  166. /*
  167. * Rewrites the expressions 'ep1' and 'ep2' to remove operands common to both.
  168. * Example reductions:
  169. *
  170. * ep1: A && B -> ep1: y
  171. * ep2: A && B && C -> ep2: C
  172. *
  173. * ep1: A || B -> ep1: n
  174. * ep2: A || B || C -> ep2: C
  175. *
  176. * ep1: A && (B && FOO) -> ep1: FOO
  177. * ep2: (BAR && B) && A -> ep2: BAR
  178. *
  179. * ep1: A && (B || C) -> ep1: y
  180. * ep2: (C || B) && A -> ep2: y
  181. *
  182. * Comparisons are done between all operands at the same "level" of && or ||.
  183. * For example, in the expression 'e1 && (e2 || e3) && (e4 || e5)', the
  184. * following operands will be compared:
  185. *
  186. * - 'e1', 'e2 || e3', and 'e4 || e5', against each other
  187. * - e2 against e3
  188. * - e4 against e5
  189. *
  190. * Parentheses are irrelevant within a single level. 'e1 && (e2 && e3)' and
  191. * '(e1 && e2) && e3' are both a single level.
  192. *
  193. * See __expr_eliminate_eq() as well.
  194. */
  195. void expr_eliminate_eq(struct expr **ep1, struct expr **ep2)
  196. {
  197. if (!e1 || !e2)
  198. return;
  199. switch (e1->type) {
  200. case E_OR:
  201. case E_AND:
  202. __expr_eliminate_eq(e1->type, ep1, ep2);
  203. default:
  204. ;
  205. }
  206. if (e1->type != e2->type) switch (e2->type) {
  207. case E_OR:
  208. case E_AND:
  209. __expr_eliminate_eq(e2->type, ep1, ep2);
  210. default:
  211. ;
  212. }
  213. e1 = expr_eliminate_yn(e1);
  214. e2 = expr_eliminate_yn(e2);
  215. }
  216. #undef e1
  217. #undef e2
  218. /*
  219. * Returns true if 'e1' and 'e2' are equal, after minor simplification. Two
  220. * &&/|| expressions are considered equal if every operand in one expression
  221. * equals some operand in the other (operands do not need to appear in the same
  222. * order), recursively.
  223. */
  224. static int expr_eq(struct expr *e1, struct expr *e2)
  225. {
  226. int res, old_count;
  227. if (e1->type != e2->type)
  228. return 0;
  229. switch (e1->type) {
  230. case E_EQUAL:
  231. case E_GEQ:
  232. case E_GTH:
  233. case E_LEQ:
  234. case E_LTH:
  235. case E_UNEQUAL:
  236. return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym;
  237. case E_SYMBOL:
  238. return e1->left.sym == e2->left.sym;
  239. case E_NOT:
  240. return expr_eq(e1->left.expr, e2->left.expr);
  241. case E_AND:
  242. case E_OR:
  243. e1 = expr_copy(e1);
  244. e2 = expr_copy(e2);
  245. old_count = trans_count;
  246. expr_eliminate_eq(&e1, &e2);
  247. res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
  248. e1->left.sym == e2->left.sym);
  249. expr_free(e1);
  250. expr_free(e2);
  251. trans_count = old_count;
  252. return res;
  253. case E_LIST:
  254. case E_RANGE:
  255. case E_NONE:
  256. /* panic */;
  257. }
  258. if (DEBUG_EXPR) {
  259. expr_fprint(e1, stdout);
  260. printf(" = ");
  261. expr_fprint(e2, stdout);
  262. printf(" ?\n");
  263. }
  264. return 0;
  265. }
  266. /*
  267. * Recursively performs the following simplifications in-place (as well as the
  268. * corresponding simplifications with swapped operands):
  269. *
  270. * expr && n -> n
  271. * expr && y -> expr
  272. * expr || n -> expr
  273. * expr || y -> y
  274. *
  275. * Returns the optimized expression.
  276. */
  277. static struct expr *expr_eliminate_yn(struct expr *e)
  278. {
  279. struct expr *tmp;
  280. if (e) switch (e->type) {
  281. case E_AND:
  282. e->left.expr = expr_eliminate_yn(e->left.expr);
  283. e->right.expr = expr_eliminate_yn(e->right.expr);
  284. if (e->left.expr->type == E_SYMBOL) {
  285. if (e->left.expr->left.sym == &symbol_no) {
  286. expr_free(e->left.expr);
  287. expr_free(e->right.expr);
  288. e->type = E_SYMBOL;
  289. e->left.sym = &symbol_no;
  290. e->right.expr = NULL;
  291. return e;
  292. } else if (e->left.expr->left.sym == &symbol_yes) {
  293. free(e->left.expr);
  294. tmp = e->right.expr;
  295. *e = *(e->right.expr);
  296. free(tmp);
  297. return e;
  298. }
  299. }
  300. if (e->right.expr->type == E_SYMBOL) {
  301. if (e->right.expr->left.sym == &symbol_no) {
  302. expr_free(e->left.expr);
  303. expr_free(e->right.expr);
  304. e->type = E_SYMBOL;
  305. e->left.sym = &symbol_no;
  306. e->right.expr = NULL;
  307. return e;
  308. } else if (e->right.expr->left.sym == &symbol_yes) {
  309. free(e->right.expr);
  310. tmp = e->left.expr;
  311. *e = *(e->left.expr);
  312. free(tmp);
  313. return e;
  314. }
  315. }
  316. break;
  317. case E_OR:
  318. e->left.expr = expr_eliminate_yn(e->left.expr);
  319. e->right.expr = expr_eliminate_yn(e->right.expr);
  320. if (e->left.expr->type == E_SYMBOL) {
  321. if (e->left.expr->left.sym == &symbol_no) {
  322. free(e->left.expr);
  323. tmp = e->right.expr;
  324. *e = *(e->right.expr);
  325. free(tmp);
  326. return e;
  327. } else if (e->left.expr->left.sym == &symbol_yes) {
  328. expr_free(e->left.expr);
  329. expr_free(e->right.expr);
  330. e->type = E_SYMBOL;
  331. e->left.sym = &symbol_yes;
  332. e->right.expr = NULL;
  333. return e;
  334. }
  335. }
  336. if (e->right.expr->type == E_SYMBOL) {
  337. if (e->right.expr->left.sym == &symbol_no) {
  338. free(e->right.expr);
  339. tmp = e->left.expr;
  340. *e = *(e->left.expr);
  341. free(tmp);
  342. return e;
  343. } else if (e->right.expr->left.sym == &symbol_yes) {
  344. expr_free(e->left.expr);
  345. expr_free(e->right.expr);
  346. e->type = E_SYMBOL;
  347. e->left.sym = &symbol_yes;
  348. e->right.expr = NULL;
  349. return e;
  350. }
  351. }
  352. break;
  353. default:
  354. ;
  355. }
  356. return e;
  357. }
  358. /*
  359. * bool FOO!=n => FOO
  360. */
  361. struct expr *expr_trans_bool(struct expr *e)
  362. {
  363. if (!e)
  364. return NULL;
  365. switch (e->type) {
  366. case E_AND:
  367. case E_OR:
  368. case E_NOT:
  369. e->left.expr = expr_trans_bool(e->left.expr);
  370. e->right.expr = expr_trans_bool(e->right.expr);
  371. break;
  372. case E_UNEQUAL:
  373. // FOO!=n -> FOO
  374. if (e->left.sym->type == S_TRISTATE) {
  375. if (e->right.sym == &symbol_no) {
  376. e->type = E_SYMBOL;
  377. e->right.sym = NULL;
  378. }
  379. }
  380. break;
  381. default:
  382. ;
  383. }
  384. return e;
  385. }
  386. /*
  387. * e1 || e2 -> ?
  388. */
  389. static struct expr *expr_join_or(struct expr *e1, struct expr *e2)
  390. {
  391. struct expr *tmp;
  392. struct symbol *sym1, *sym2;
  393. if (expr_eq(e1, e2))
  394. return expr_copy(e1);
  395. if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
  396. return NULL;
  397. if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
  398. return NULL;
  399. if (e1->type == E_NOT) {
  400. tmp = e1->left.expr;
  401. if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
  402. return NULL;
  403. sym1 = tmp->left.sym;
  404. } else
  405. sym1 = e1->left.sym;
  406. if (e2->type == E_NOT) {
  407. if (e2->left.expr->type != E_SYMBOL)
  408. return NULL;
  409. sym2 = e2->left.expr->left.sym;
  410. } else
  411. sym2 = e2->left.sym;
  412. if (sym1 != sym2)
  413. return NULL;
  414. if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
  415. return NULL;
  416. if (sym1->type == S_TRISTATE) {
  417. if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
  418. ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
  419. (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) {
  420. // (a='y') || (a='m') -> (a!='n')
  421. return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no);
  422. }
  423. if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
  424. ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
  425. (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) {
  426. // (a='y') || (a='n') -> (a!='m')
  427. return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod);
  428. }
  429. if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
  430. ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
  431. (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) {
  432. // (a='m') || (a='n') -> (a!='y')
  433. return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes);
  434. }
  435. }
  436. if (sym1->type == S_BOOLEAN && sym1 == sym2) {
  437. if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) ||
  438. (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL))
  439. return expr_alloc_symbol(&symbol_yes);
  440. }
  441. if (DEBUG_EXPR) {
  442. printf("optimize (");
  443. expr_fprint(e1, stdout);
  444. printf(") || (");
  445. expr_fprint(e2, stdout);
  446. printf(")?\n");
  447. }
  448. return NULL;
  449. }
  450. static struct expr *expr_join_and(struct expr *e1, struct expr *e2)
  451. {
  452. struct expr *tmp;
  453. struct symbol *sym1, *sym2;
  454. if (expr_eq(e1, e2))
  455. return expr_copy(e1);
  456. if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
  457. return NULL;
  458. if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
  459. return NULL;
  460. if (e1->type == E_NOT) {
  461. tmp = e1->left.expr;
  462. if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
  463. return NULL;
  464. sym1 = tmp->left.sym;
  465. } else
  466. sym1 = e1->left.sym;
  467. if (e2->type == E_NOT) {
  468. if (e2->left.expr->type != E_SYMBOL)
  469. return NULL;
  470. sym2 = e2->left.expr->left.sym;
  471. } else
  472. sym2 = e2->left.sym;
  473. if (sym1 != sym2)
  474. return NULL;
  475. if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
  476. return NULL;
  477. if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) ||
  478. (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes))
  479. // (a) && (a='y') -> (a='y')
  480. return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
  481. if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) ||
  482. (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no))
  483. // (a) && (a!='n') -> (a)
  484. return expr_alloc_symbol(sym1);
  485. if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) ||
  486. (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod))
  487. // (a) && (a!='m') -> (a='y')
  488. return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
  489. if (sym1->type == S_TRISTATE) {
  490. if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) {
  491. // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
  492. sym2 = e1->right.sym;
  493. if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
  494. return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
  495. : expr_alloc_symbol(&symbol_no);
  496. }
  497. if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) {
  498. // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
  499. sym2 = e2->right.sym;
  500. if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
  501. return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
  502. : expr_alloc_symbol(&symbol_no);
  503. }
  504. if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
  505. ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
  506. (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes)))
  507. // (a!='y') && (a!='n') -> (a='m')
  508. return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod);
  509. if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
  510. ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
  511. (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes)))
  512. // (a!='y') && (a!='m') -> (a='n')
  513. return expr_alloc_comp(E_EQUAL, sym1, &symbol_no);
  514. if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
  515. ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
  516. (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod)))
  517. // (a!='m') && (a!='n') -> (a='m')
  518. return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
  519. if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) ||
  520. (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) ||
  521. (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) ||
  522. (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes))
  523. return NULL;
  524. }
  525. if (DEBUG_EXPR) {
  526. printf("optimize (");
  527. expr_fprint(e1, stdout);
  528. printf(") && (");
  529. expr_fprint(e2, stdout);
  530. printf(")?\n");
  531. }
  532. return NULL;
  533. }
  534. /*
  535. * expr_eliminate_dups() helper.
  536. *
  537. * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does
  538. * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared
  539. * against all other leaves to look for simplifications.
  540. */
  541. static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2)
  542. {
  543. #define e1 (*ep1)
  544. #define e2 (*ep2)
  545. struct expr *tmp;
  546. /* Recurse down to leaves */
  547. if (e1->type == type) {
  548. expr_eliminate_dups1(type, &e1->left.expr, &e2);
  549. expr_eliminate_dups1(type, &e1->right.expr, &e2);
  550. return;
  551. }
  552. if (e2->type == type) {
  553. expr_eliminate_dups1(type, &e1, &e2->left.expr);
  554. expr_eliminate_dups1(type, &e1, &e2->right.expr);
  555. return;
  556. }
  557. /* e1 and e2 are leaves. Compare and process them. */
  558. if (e1 == e2)
  559. return;
  560. switch (e1->type) {
  561. case E_OR: case E_AND:
  562. expr_eliminate_dups1(e1->type, &e1, &e1);
  563. default:
  564. ;
  565. }
  566. switch (type) {
  567. case E_OR:
  568. tmp = expr_join_or(e1, e2);
  569. if (tmp) {
  570. expr_free(e1); expr_free(e2);
  571. e1 = expr_alloc_symbol(&symbol_no);
  572. e2 = tmp;
  573. trans_count++;
  574. }
  575. break;
  576. case E_AND:
  577. tmp = expr_join_and(e1, e2);
  578. if (tmp) {
  579. expr_free(e1); expr_free(e2);
  580. e1 = expr_alloc_symbol(&symbol_yes);
  581. e2 = tmp;
  582. trans_count++;
  583. }
  584. break;
  585. default:
  586. ;
  587. }
  588. #undef e1
  589. #undef e2
  590. }
  591. /*
  592. * Rewrites 'e' in-place to remove ("join") duplicate and other redundant
  593. * operands.
  594. *
  595. * Example simplifications:
  596. *
  597. * A || B || A -> A || B
  598. * A && B && A=y -> A=y && B
  599. *
  600. * Returns the deduplicated expression.
  601. */
  602. struct expr *expr_eliminate_dups(struct expr *e)
  603. {
  604. int oldcount;
  605. if (!e)
  606. return e;
  607. oldcount = trans_count;
  608. while (1) {
  609. trans_count = 0;
  610. switch (e->type) {
  611. case E_OR: case E_AND:
  612. expr_eliminate_dups1(e->type, &e, &e);
  613. default:
  614. ;
  615. }
  616. if (!trans_count)
  617. /* No simplifications done in this pass. We're done */
  618. break;
  619. e = expr_eliminate_yn(e);
  620. }
  621. trans_count = oldcount;
  622. return e;
  623. }
  624. /*
  625. * Performs various simplifications involving logical operators and
  626. * comparisons.
  627. *
  628. * Allocates and returns a new expression.
  629. */
  630. struct expr *expr_transform(struct expr *e)
  631. {
  632. struct expr *tmp;
  633. if (!e)
  634. return NULL;
  635. switch (e->type) {
  636. case E_EQUAL:
  637. case E_GEQ:
  638. case E_GTH:
  639. case E_LEQ:
  640. case E_LTH:
  641. case E_UNEQUAL:
  642. case E_SYMBOL:
  643. case E_LIST:
  644. break;
  645. default:
  646. e->left.expr = expr_transform(e->left.expr);
  647. e->right.expr = expr_transform(e->right.expr);
  648. }
  649. switch (e->type) {
  650. case E_EQUAL:
  651. if (e->left.sym->type != S_BOOLEAN)
  652. break;
  653. if (e->right.sym == &symbol_no) {
  654. e->type = E_NOT;
  655. e->left.expr = expr_alloc_symbol(e->left.sym);
  656. e->right.sym = NULL;
  657. break;
  658. }
  659. if (e->right.sym == &symbol_mod) {
  660. printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name);
  661. e->type = E_SYMBOL;
  662. e->left.sym = &symbol_no;
  663. e->right.sym = NULL;
  664. break;
  665. }
  666. if (e->right.sym == &symbol_yes) {
  667. e->type = E_SYMBOL;
  668. e->right.sym = NULL;
  669. break;
  670. }
  671. break;
  672. case E_UNEQUAL:
  673. if (e->left.sym->type != S_BOOLEAN)
  674. break;
  675. if (e->right.sym == &symbol_no) {
  676. e->type = E_SYMBOL;
  677. e->right.sym = NULL;
  678. break;
  679. }
  680. if (e->right.sym == &symbol_mod) {
  681. printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name);
  682. e->type = E_SYMBOL;
  683. e->left.sym = &symbol_yes;
  684. e->right.sym = NULL;
  685. break;
  686. }
  687. if (e->right.sym == &symbol_yes) {
  688. e->type = E_NOT;
  689. e->left.expr = expr_alloc_symbol(e->left.sym);
  690. e->right.sym = NULL;
  691. break;
  692. }
  693. break;
  694. case E_NOT:
  695. switch (e->left.expr->type) {
  696. case E_NOT:
  697. // !!a -> a
  698. tmp = e->left.expr->left.expr;
  699. free(e->left.expr);
  700. free(e);
  701. e = tmp;
  702. e = expr_transform(e);
  703. break;
  704. case E_EQUAL:
  705. case E_UNEQUAL:
  706. // !a='x' -> a!='x'
  707. tmp = e->left.expr;
  708. free(e);
  709. e = tmp;
  710. e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL;
  711. break;
  712. case E_LEQ:
  713. case E_GEQ:
  714. // !a<='x' -> a>'x'
  715. tmp = e->left.expr;
  716. free(e);
  717. e = tmp;
  718. e->type = e->type == E_LEQ ? E_GTH : E_LTH;
  719. break;
  720. case E_LTH:
  721. case E_GTH:
  722. // !a<'x' -> a>='x'
  723. tmp = e->left.expr;
  724. free(e);
  725. e = tmp;
  726. e->type = e->type == E_LTH ? E_GEQ : E_LEQ;
  727. break;
  728. case E_OR:
  729. // !(a || b) -> !a && !b
  730. tmp = e->left.expr;
  731. e->type = E_AND;
  732. e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
  733. tmp->type = E_NOT;
  734. tmp->right.expr = NULL;
  735. e = expr_transform(e);
  736. break;
  737. case E_AND:
  738. // !(a && b) -> !a || !b
  739. tmp = e->left.expr;
  740. e->type = E_OR;
  741. e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
  742. tmp->type = E_NOT;
  743. tmp->right.expr = NULL;
  744. e = expr_transform(e);
  745. break;
  746. case E_SYMBOL:
  747. if (e->left.expr->left.sym == &symbol_yes) {
  748. // !'y' -> 'n'
  749. tmp = e->left.expr;
  750. free(e);
  751. e = tmp;
  752. e->type = E_SYMBOL;
  753. e->left.sym = &symbol_no;
  754. break;
  755. }
  756. if (e->left.expr->left.sym == &symbol_mod) {
  757. // !'m' -> 'm'
  758. tmp = e->left.expr;
  759. free(e);
  760. e = tmp;
  761. e->type = E_SYMBOL;
  762. e->left.sym = &symbol_mod;
  763. break;
  764. }
  765. if (e->left.expr->left.sym == &symbol_no) {
  766. // !'n' -> 'y'
  767. tmp = e->left.expr;
  768. free(e);
  769. e = tmp;
  770. e->type = E_SYMBOL;
  771. e->left.sym = &symbol_yes;
  772. break;
  773. }
  774. break;
  775. default:
  776. ;
  777. }
  778. break;
  779. default:
  780. ;
  781. }
  782. return e;
  783. }
  784. int expr_contains_symbol(struct expr *dep, struct symbol *sym)
  785. {
  786. if (!dep)
  787. return 0;
  788. switch (dep->type) {
  789. case E_AND:
  790. case E_OR:
  791. return expr_contains_symbol(dep->left.expr, sym) ||
  792. expr_contains_symbol(dep->right.expr, sym);
  793. case E_SYMBOL:
  794. return dep->left.sym == sym;
  795. case E_EQUAL:
  796. case E_GEQ:
  797. case E_GTH:
  798. case E_LEQ:
  799. case E_LTH:
  800. case E_UNEQUAL:
  801. return dep->left.sym == sym ||
  802. dep->right.sym == sym;
  803. case E_NOT:
  804. return expr_contains_symbol(dep->left.expr, sym);
  805. default:
  806. ;
  807. }
  808. return 0;
  809. }
  810. bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
  811. {
  812. if (!dep)
  813. return false;
  814. switch (dep->type) {
  815. case E_AND:
  816. return expr_depends_symbol(dep->left.expr, sym) ||
  817. expr_depends_symbol(dep->right.expr, sym);
  818. case E_SYMBOL:
  819. return dep->left.sym == sym;
  820. case E_EQUAL:
  821. if (dep->left.sym == sym) {
  822. if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod)
  823. return true;
  824. }
  825. break;
  826. case E_UNEQUAL:
  827. if (dep->left.sym == sym) {
  828. if (dep->right.sym == &symbol_no)
  829. return true;
  830. }
  831. break;
  832. default:
  833. ;
  834. }
  835. return false;
  836. }
  837. /*
  838. * Inserts explicit comparisons of type 'type' to symbol 'sym' into the
  839. * expression 'e'.
  840. *
  841. * Examples transformations for type == E_UNEQUAL, sym == &symbol_no:
  842. *
  843. * A -> A!=n
  844. * !A -> A=n
  845. * A && B -> !(A=n || B=n)
  846. * A || B -> !(A=n && B=n)
  847. * A && (B || C) -> !(A=n || (B=n && C=n))
  848. *
  849. * Allocates and returns a new expression.
  850. */
  851. struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)
  852. {
  853. struct expr *e1, *e2;
  854. if (!e) {
  855. e = expr_alloc_symbol(sym);
  856. if (type == E_UNEQUAL)
  857. e = expr_alloc_one(E_NOT, e);
  858. return e;
  859. }
  860. switch (e->type) {
  861. case E_AND:
  862. e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
  863. e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
  864. if (sym == &symbol_yes)
  865. e = expr_alloc_two(E_AND, e1, e2);
  866. if (sym == &symbol_no)
  867. e = expr_alloc_two(E_OR, e1, e2);
  868. if (type == E_UNEQUAL)
  869. e = expr_alloc_one(E_NOT, e);
  870. return e;
  871. case E_OR:
  872. e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
  873. e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
  874. if (sym == &symbol_yes)
  875. e = expr_alloc_two(E_OR, e1, e2);
  876. if (sym == &symbol_no)
  877. e = expr_alloc_two(E_AND, e1, e2);
  878. if (type == E_UNEQUAL)
  879. e = expr_alloc_one(E_NOT, e);
  880. return e;
  881. case E_NOT:
  882. return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym);
  883. case E_UNEQUAL:
  884. case E_LTH:
  885. case E_LEQ:
  886. case E_GTH:
  887. case E_GEQ:
  888. case E_EQUAL:
  889. if (type == E_EQUAL) {
  890. if (sym == &symbol_yes)
  891. return expr_copy(e);
  892. if (sym == &symbol_mod)
  893. return expr_alloc_symbol(&symbol_no);
  894. if (sym == &symbol_no)
  895. return expr_alloc_one(E_NOT, expr_copy(e));
  896. } else {
  897. if (sym == &symbol_yes)
  898. return expr_alloc_one(E_NOT, expr_copy(e));
  899. if (sym == &symbol_mod)
  900. return expr_alloc_symbol(&symbol_yes);
  901. if (sym == &symbol_no)
  902. return expr_copy(e);
  903. }
  904. break;
  905. case E_SYMBOL:
  906. return expr_alloc_comp(type, e->left.sym, sym);
  907. case E_LIST:
  908. case E_RANGE:
  909. case E_NONE:
  910. /* panic */;
  911. }
  912. return NULL;
  913. }
  914. enum string_value_kind {
  915. k_string,
  916. k_signed,
  917. k_unsigned,
  918. k_invalid
  919. };
  920. union string_value {
  921. unsigned long long u;
  922. signed long long s;
  923. };
  924. static enum string_value_kind expr_parse_string(const char *str,
  925. enum symbol_type type,
  926. union string_value *val)
  927. {
  928. char *tail;
  929. enum string_value_kind kind;
  930. errno = 0;
  931. switch (type) {
  932. case S_BOOLEAN:
  933. case S_TRISTATE:
  934. val->s = !strcmp(str, "n") ? 0 :
  935. !strcmp(str, "m") ? 1 :
  936. !strcmp(str, "y") ? 2 : -1;
  937. return k_signed;
  938. case S_INT:
  939. val->s = strtoll(str, &tail, 10);
  940. kind = k_signed;
  941. break;
  942. case S_HEX:
  943. val->u = strtoull(str, &tail, 16);
  944. kind = k_unsigned;
  945. break;
  946. case S_STRING:
  947. case S_UNKNOWN:
  948. val->s = strtoll(str, &tail, 0);
  949. kind = k_signed;
  950. break;
  951. default:
  952. return k_invalid;
  953. }
  954. return !errno && !*tail && tail > str && isxdigit(tail[-1])
  955. ? kind : k_string;
  956. }
  957. tristate expr_calc_value(struct expr *e)
  958. {
  959. tristate val1, val2;
  960. const char *str1, *str2;
  961. enum string_value_kind k1 = k_string, k2 = k_string;
  962. union string_value lval = {}, rval = {};
  963. int res;
  964. if (!e)
  965. return yes;
  966. switch (e->type) {
  967. case E_SYMBOL:
  968. sym_calc_value(e->left.sym);
  969. return e->left.sym->curr.tri;
  970. case E_AND:
  971. val1 = expr_calc_value(e->left.expr);
  972. val2 = expr_calc_value(e->right.expr);
  973. return EXPR_AND(val1, val2);
  974. case E_OR:
  975. val1 = expr_calc_value(e->left.expr);
  976. val2 = expr_calc_value(e->right.expr);
  977. return EXPR_OR(val1, val2);
  978. case E_NOT:
  979. val1 = expr_calc_value(e->left.expr);
  980. return EXPR_NOT(val1);
  981. case E_EQUAL:
  982. case E_GEQ:
  983. case E_GTH:
  984. case E_LEQ:
  985. case E_LTH:
  986. case E_UNEQUAL:
  987. break;
  988. default:
  989. printf("expr_calc_value: %d?\n", e->type);
  990. return no;
  991. }
  992. sym_calc_value(e->left.sym);
  993. sym_calc_value(e->right.sym);
  994. str1 = sym_get_string_value(e->left.sym);
  995. str2 = sym_get_string_value(e->right.sym);
  996. if (e->left.sym->type != S_STRING || e->right.sym->type != S_STRING) {
  997. k1 = expr_parse_string(str1, e->left.sym->type, &lval);
  998. k2 = expr_parse_string(str2, e->right.sym->type, &rval);
  999. }
  1000. if (k1 == k_string || k2 == k_string)
  1001. res = strcmp(str1, str2);
  1002. else if (k1 == k_invalid || k2 == k_invalid) {
  1003. if (e->type != E_EQUAL && e->type != E_UNEQUAL) {
  1004. printf("Cannot compare \"%s\" and \"%s\"\n", str1, str2);
  1005. return no;
  1006. }
  1007. res = strcmp(str1, str2);
  1008. } else if (k1 == k_unsigned || k2 == k_unsigned)
  1009. res = (lval.u > rval.u) - (lval.u < rval.u);
  1010. else /* if (k1 == k_signed && k2 == k_signed) */
  1011. res = (lval.s > rval.s) - (lval.s < rval.s);
  1012. switch(e->type) {
  1013. case E_EQUAL:
  1014. return res ? no : yes;
  1015. case E_GEQ:
  1016. return res >= 0 ? yes : no;
  1017. case E_GTH:
  1018. return res > 0 ? yes : no;
  1019. case E_LEQ:
  1020. return res <= 0 ? yes : no;
  1021. case E_LTH:
  1022. return res < 0 ? yes : no;
  1023. case E_UNEQUAL:
  1024. return res ? yes : no;
  1025. default:
  1026. printf("expr_calc_value: relation %d?\n", e->type);
  1027. return no;
  1028. }
  1029. }
  1030. static int expr_compare_type(enum expr_type t1, enum expr_type t2)
  1031. {
  1032. if (t1 == t2)
  1033. return 0;
  1034. switch (t1) {
  1035. case E_LEQ:
  1036. case E_LTH:
  1037. case E_GEQ:
  1038. case E_GTH:
  1039. if (t2 == E_EQUAL || t2 == E_UNEQUAL)
  1040. return 1;
  1041. case E_EQUAL:
  1042. case E_UNEQUAL:
  1043. if (t2 == E_NOT)
  1044. return 1;
  1045. case E_NOT:
  1046. if (t2 == E_AND)
  1047. return 1;
  1048. case E_AND:
  1049. if (t2 == E_OR)
  1050. return 1;
  1051. case E_OR:
  1052. if (t2 == E_LIST)
  1053. return 1;
  1054. case E_LIST:
  1055. if (t2 == 0)
  1056. return 1;
  1057. default:
  1058. return -1;
  1059. }
  1060. printf("[%dgt%d?]", t1, t2);
  1061. return 0;
  1062. }
  1063. void expr_print(struct expr *e,
  1064. void (*fn)(void *, struct symbol *, const char *),
  1065. void *data, int prevtoken)
  1066. {
  1067. if (!e) {
  1068. fn(data, NULL, "y");
  1069. return;
  1070. }
  1071. if (expr_compare_type(prevtoken, e->type) > 0)
  1072. fn(data, NULL, "(");
  1073. switch (e->type) {
  1074. case E_SYMBOL:
  1075. if (e->left.sym->name)
  1076. fn(data, e->left.sym, e->left.sym->name);
  1077. else
  1078. fn(data, NULL, "<choice>");
  1079. break;
  1080. case E_NOT:
  1081. fn(data, NULL, "!");
  1082. expr_print(e->left.expr, fn, data, E_NOT);
  1083. break;
  1084. case E_EQUAL:
  1085. if (e->left.sym->name)
  1086. fn(data, e->left.sym, e->left.sym->name);
  1087. else
  1088. fn(data, NULL, "<choice>");
  1089. fn(data, NULL, "=");
  1090. fn(data, e->right.sym, e->right.sym->name);
  1091. break;
  1092. case E_LEQ:
  1093. case E_LTH:
  1094. if (e->left.sym->name)
  1095. fn(data, e->left.sym, e->left.sym->name);
  1096. else
  1097. fn(data, NULL, "<choice>");
  1098. fn(data, NULL, e->type == E_LEQ ? "<=" : "<");
  1099. fn(data, e->right.sym, e->right.sym->name);
  1100. break;
  1101. case E_GEQ:
  1102. case E_GTH:
  1103. if (e->left.sym->name)
  1104. fn(data, e->left.sym, e->left.sym->name);
  1105. else
  1106. fn(data, NULL, "<choice>");
  1107. fn(data, NULL, e->type == E_GEQ ? ">=" : ">");
  1108. fn(data, e->right.sym, e->right.sym->name);
  1109. break;
  1110. case E_UNEQUAL:
  1111. if (e->left.sym->name)
  1112. fn(data, e->left.sym, e->left.sym->name);
  1113. else
  1114. fn(data, NULL, "<choice>");
  1115. fn(data, NULL, "!=");
  1116. fn(data, e->right.sym, e->right.sym->name);
  1117. break;
  1118. case E_OR:
  1119. expr_print(e->left.expr, fn, data, E_OR);
  1120. fn(data, NULL, " || ");
  1121. expr_print(e->right.expr, fn, data, E_OR);
  1122. break;
  1123. case E_AND:
  1124. expr_print(e->left.expr, fn, data, E_AND);
  1125. fn(data, NULL, " && ");
  1126. expr_print(e->right.expr, fn, data, E_AND);
  1127. break;
  1128. case E_LIST:
  1129. fn(data, e->right.sym, e->right.sym->name);
  1130. if (e->left.expr) {
  1131. fn(data, NULL, " ^ ");
  1132. expr_print(e->left.expr, fn, data, E_LIST);
  1133. }
  1134. break;
  1135. case E_RANGE:
  1136. fn(data, NULL, "[");
  1137. fn(data, e->left.sym, e->left.sym->name);
  1138. fn(data, NULL, " ");
  1139. fn(data, e->right.sym, e->right.sym->name);
  1140. fn(data, NULL, "]");
  1141. break;
  1142. default:
  1143. {
  1144. char buf[32];
  1145. sprintf(buf, "<unknown type %d>", e->type);
  1146. fn(data, NULL, buf);
  1147. break;
  1148. }
  1149. }
  1150. if (expr_compare_type(prevtoken, e->type) > 0)
  1151. fn(data, NULL, ")");
  1152. }
  1153. static void expr_print_file_helper(void *data, struct symbol *sym, const char *str)
  1154. {
  1155. xfwrite(str, strlen(str), 1, data);
  1156. }
  1157. void expr_fprint(struct expr *e, FILE *out)
  1158. {
  1159. expr_print(e, expr_print_file_helper, out, E_NONE);
  1160. }
  1161. static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str)
  1162. {
  1163. struct gstr *gs = (struct gstr*)data;
  1164. const char *sym_str = NULL;
  1165. if (sym)
  1166. sym_str = sym_get_string_value(sym);
  1167. if (gs->max_width) {
  1168. unsigned extra_length = strlen(str);
  1169. const char *last_cr = strrchr(gs->s, '\n');
  1170. unsigned last_line_length;
  1171. if (sym_str)
  1172. extra_length += 4 + strlen(sym_str);
  1173. if (!last_cr)
  1174. last_cr = gs->s;
  1175. last_line_length = strlen(gs->s) - (last_cr - gs->s);
  1176. if ((last_line_length + extra_length) > gs->max_width)
  1177. str_append(gs, "\\\n");
  1178. }
  1179. str_append(gs, str);
  1180. if (sym && sym->type != S_UNKNOWN)
  1181. str_printf(gs, " [=%s]", sym_str);
  1182. }
  1183. void expr_gstr_print(struct expr *e, struct gstr *gs)
  1184. {
  1185. expr_print(e, expr_print_gstr_helper, gs, E_NONE);
  1186. }
  1187. /*
  1188. * Transform the top level "||" tokens into newlines and prepend each
  1189. * line with a minus. This makes expressions much easier to read.
  1190. * Suitable for reverse dependency expressions.
  1191. */
  1192. static void expr_print_revdep(struct expr *e,
  1193. void (*fn)(void *, struct symbol *, const char *),
  1194. void *data, tristate pr_type, const char **title)
  1195. {
  1196. if (e->type == E_OR) {
  1197. expr_print_revdep(e->left.expr, fn, data, pr_type, title);
  1198. expr_print_revdep(e->right.expr, fn, data, pr_type, title);
  1199. } else if (expr_calc_value(e) == pr_type) {
  1200. if (*title) {
  1201. fn(data, NULL, *title);
  1202. *title = NULL;
  1203. }
  1204. fn(data, NULL, " - ");
  1205. expr_print(e, fn, data, E_NONE);
  1206. fn(data, NULL, "\n");
  1207. }
  1208. }
  1209. void expr_gstr_print_revdep(struct expr *e, struct gstr *gs,
  1210. tristate pr_type, const char *title)
  1211. {
  1212. expr_print_revdep(e, expr_print_gstr_helper, gs, pr_type, &title);
  1213. }