crosstool-ng: kconfig/expr.c@e11a8a2e225d

     1 /*

     2  * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org>

     3  * Released under the terms of the GNU GPL v2.0.

     4  */

     6 #include <stdio.h>

     7 #include <stdlib.h>

     8 #include <string.h>

    10 #define LKC_DIRECT_LINK

    11 #include "lkc.h"

    13 #define DEBUG_EXPR	0

    15 struct expr *expr_alloc_symbol(struct symbol *sym)

    16 {

    17 	struct expr *e = malloc(sizeof(*e));

    18 	memset(e, 0, sizeof(*e));

    19 	e->type = E_SYMBOL;

    20 	e->left.sym = sym;

    21 	return e;

    22 }

    24 struct expr *expr_alloc_one(enum expr_type type, struct expr *ce)

    25 {

    26 	struct expr *e = malloc(sizeof(*e));

    27 	memset(e, 0, sizeof(*e));

    28 	e->type = type;

    29 	e->left.expr = ce;

    30 	return e;

    31 }

    33 struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e2)

    34 {

    35 	struct expr *e = malloc(sizeof(*e));

    36 	memset(e, 0, sizeof(*e));

    37 	e->type = type;

    38 	e->left.expr = e1;

    39 	e->right.expr = e2;

    40 	return e;

    41 }

    43 struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2)

    44 {

    45 	struct expr *e = malloc(sizeof(*e));

    46 	memset(e, 0, sizeof(*e));

    47 	e->type = type;

    48 	e->left.sym = s1;

    49 	e->right.sym = s2;

    50 	return e;

    51 }

    53 struct expr *expr_alloc_and(struct expr *e1, struct expr *e2)

    54 {

    55 	if (!e1)

    56 		return e2;

    57 	return e2 ? expr_alloc_two(E_AND, e1, e2) : e1;

    58 }

    60 struct expr *expr_alloc_or(struct expr *e1, struct expr *e2)

    61 {

    62 	if (!e1)

    63 		return e2;

    64 	return e2 ? expr_alloc_two(E_OR, e1, e2) : e1;

    65 }

    67 struct expr *expr_copy(const struct expr *org)

    68 {

    69 	struct expr *e;

    71 	if (!org)

    72 		return NULL;

    74 	e = malloc(sizeof(*org));

    75 	memcpy(e, org, sizeof(*org));

    76 	switch (org->type) {

    77 	case E_SYMBOL:

    78 		e->left = org->left;

    79 		break;

    80 	case E_NOT:

    81 		e->left.expr = expr_copy(org->left.expr);

    82 		break;

    83 	case E_EQUAL:

    84 	case E_UNEQUAL:

    85 		e->left.sym = org->left.sym;

    86 		e->right.sym = org->right.sym;

    87 		break;

    88 	case E_AND:

    89 	case E_OR:

    90 	case E_LIST:

    91 		e->left.expr = expr_copy(org->left.expr);

    92 		e->right.expr = expr_copy(org->right.expr);

    93 		break;

    94 	default:

    95 		printf("can't copy type %d\n", e->type);

    96 		free(e);

    97 		e = NULL;

    98 		break;

    99 	}

   101 	return e;

   102 }

   104 void expr_free(struct expr *e)

   105 {

   106 	if (!e)

   107 		return;

   109 	switch (e->type) {

   110 	case E_SYMBOL:

   111 		break;

   112 	case E_NOT:

   113 		expr_free(e->left.expr);

   114 		return;

   115 	case E_EQUAL:

   116 	case E_UNEQUAL:

   117 		break;

   118 	case E_OR:

   119 	case E_AND:

   120 		expr_free(e->left.expr);

   121 		expr_free(e->right.expr);

   122 		break;

   123 	default:

   124 		printf("how to free type %d?\n", e->type);

   125 		break;

   126 	}

   127 	free(e);

   128 }

   130 static int trans_count;

   132 #define e1 (*ep1)

   133 #define e2 (*ep2)

   135 static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2)

   136 {

   137 	if (e1->type == type) {

   138 		__expr_eliminate_eq(type, &e1->left.expr, &e2);

   139 		__expr_eliminate_eq(type, &e1->right.expr, &e2);

   140 		return;

   141 	}

   142 	if (e2->type == type) {

   143 		__expr_eliminate_eq(type, &e1, &e2->left.expr);

   144 		__expr_eliminate_eq(type, &e1, &e2->right.expr);

   145 		return;

   146 	}

   147 	if (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&

   148 	    e1->left.sym == e2->left.sym &&

   149 	    (e1->left.sym == &symbol_yes || e1->left.sym == &symbol_no))

   150 		return;

   151 	if (!expr_eq(e1, e2))

   152 		return;

   153 	trans_count++;

   154 	expr_free(e1); expr_free(e2);

   155 	switch (type) {

   156 	case E_OR:

   157 		e1 = expr_alloc_symbol(&symbol_no);

   158 		e2 = expr_alloc_symbol(&symbol_no);

   159 		break;

   160 	case E_AND:

   161 		e1 = expr_alloc_symbol(&symbol_yes);

   162 		e2 = expr_alloc_symbol(&symbol_yes);

   163 		break;

   164 	default:

   165 		;

   166 	}

   167 }

   169 void expr_eliminate_eq(struct expr **ep1, struct expr **ep2)

   170 {

   171 	if (!e1 || !e2)

   172 		return;

   173 	switch (e1->type) {

   174 	case E_OR:

   175 	case E_AND:

   176 		__expr_eliminate_eq(e1->type, ep1, ep2);

   177 	default:

   178 		;

   179 	}

   180 	if (e1->type != e2->type) switch (e2->type) {

   181 	case E_OR:

   182 	case E_AND:

   183 		__expr_eliminate_eq(e2->type, ep1, ep2);

   184 	default:

   185 		;

   186 	}

   187 	e1 = expr_eliminate_yn(e1);

   188 	e2 = expr_eliminate_yn(e2);

   189 }

   191 #undef e1

   192 #undef e2

   194 int expr_eq(struct expr *e1, struct expr *e2)

   195 {

   196 	int res, old_count;

   198 	if (e1->type != e2->type)

   199 		return 0;

   200 	switch (e1->type) {

   201 	case E_EQUAL:

   202 	case E_UNEQUAL:

   203 		return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym;

   204 	case E_SYMBOL:

   205 		return e1->left.sym == e2->left.sym;

   206 	case E_NOT:

   207 		return expr_eq(e1->left.expr, e2->left.expr);

   208 	case E_AND:

   209 	case E_OR:

   210 		e1 = expr_copy(e1);

   211 		e2 = expr_copy(e2);

   212 		old_count = trans_count;

   213 		expr_eliminate_eq(&e1, &e2);

   214 		res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&

   215 		       e1->left.sym == e2->left.sym);

   216 		expr_free(e1);

   217 		expr_free(e2);

   218 		trans_count = old_count;

   219 		return res;

   220 	case E_LIST:

   221 	case E_RANGE:

   222 	case E_NONE:

   223 		/* panic */;

   224 	}

   226 	if (DEBUG_EXPR) {

   227 		expr_fprint(e1, stdout);

   228 		printf(" = ");

   229 		expr_fprint(e2, stdout);

   230 		printf(" ?\n");

   231 	}

   233 	return 0;

   234 }

   236 struct expr *expr_eliminate_yn(struct expr *e)

   237 {

   238 	struct expr *tmp;

   240 	if (e) switch (e->type) {

   241 	case E_AND:

   242 		e->left.expr = expr_eliminate_yn(e->left.expr);

   243 		e->right.expr = expr_eliminate_yn(e->right.expr);

   244 		if (e->left.expr->type == E_SYMBOL) {

   245 			if (e->left.expr->left.sym == &symbol_no) {

   246 				expr_free(e->left.expr);

   247 				expr_free(e->right.expr);

   248 				e->type = E_SYMBOL;

   249 				e->left.sym = &symbol_no;

   250 				e->right.expr = NULL;

   251 				return e;

   252 			} else if (e->left.expr->left.sym == &symbol_yes) {

   253 				free(e->left.expr);

   254 				tmp = e->right.expr;

   255 				*e = *(e->right.expr);

   256 				free(tmp);

   257 				return e;

   258 			}

   259 		}

   260 		if (e->right.expr->type == E_SYMBOL) {

   261 			if (e->right.expr->left.sym == &symbol_no) {

   262 				expr_free(e->left.expr);

   263 				expr_free(e->right.expr);

   264 				e->type = E_SYMBOL;

   265 				e->left.sym = &symbol_no;

   266 				e->right.expr = NULL;

   267 				return e;

   268 			} else if (e->right.expr->left.sym == &symbol_yes) {

   269 				free(e->right.expr);

   270 				tmp = e->left.expr;

   271 				*e = *(e->left.expr);

   272 				free(tmp);

   273 				return e;

   274 			}

   275 		}

   276 		break;

   277 	case E_OR:

   278 		e->left.expr = expr_eliminate_yn(e->left.expr);

   279 		e->right.expr = expr_eliminate_yn(e->right.expr);

   280 		if (e->left.expr->type == E_SYMBOL) {

   281 			if (e->left.expr->left.sym == &symbol_no) {

   282 				free(e->left.expr);

   283 				tmp = e->right.expr;

   284 				*e = *(e->right.expr);

   285 				free(tmp);

   286 				return e;

   287 			} else if (e->left.expr->left.sym == &symbol_yes) {

   288 				expr_free(e->left.expr);

   289 				expr_free(e->right.expr);

   290 				e->type = E_SYMBOL;

   291 				e->left.sym = &symbol_yes;

   292 				e->right.expr = NULL;

   293 				return e;

   294 			}

   295 		}

   296 		if (e->right.expr->type == E_SYMBOL) {

   297 			if (e->right.expr->left.sym == &symbol_no) {

   298 				free(e->right.expr);

   299 				tmp = e->left.expr;

   300 				*e = *(e->left.expr);

   301 				free(tmp);

   302 				return e;

   303 			} else if (e->right.expr->left.sym == &symbol_yes) {

   304 				expr_free(e->left.expr);

   305 				expr_free(e->right.expr);

   306 				e->type = E_SYMBOL;

   307 				e->left.sym = &symbol_yes;

   308 				e->right.expr = NULL;

   309 				return e;

   310 			}

   311 		}

   312 		break;

   313 	default:

   314 		;

   315 	}

   316 	return e;

   317 }

   319 /*

   320  * bool FOO!=n => FOO

   321  */

   322 struct expr *expr_trans_bool(struct expr *e)

   323 {

   324 	if (!e)

   325 		return NULL;

   326 	switch (e->type) {

   327 	case E_AND:

   328 	case E_OR:

   329 	case E_NOT:

   330 		e->left.expr = expr_trans_bool(e->left.expr);

   331 		e->right.expr = expr_trans_bool(e->right.expr);

   332 		break;

   333 	case E_UNEQUAL:

   334 		// FOO!=n -> FOO

   335 		if (e->left.sym->type == S_TRISTATE) {

   336 			if (e->right.sym == &symbol_no) {

   337 				e->type = E_SYMBOL;

   338 				e->right.sym = NULL;

   339 			}

   340 		}

   341 		break;

   342 	default:

   343 		;

   344 	}

   345 	return e;

   346 }

   348 /*

   349  * e1 || e2 -> ?

   350  */

   351 static struct expr *expr_join_or(struct expr *e1, struct expr *e2)

   352 {

   353 	struct expr *tmp;

   354 	struct symbol *sym1, *sym2;

   356 	if (expr_eq(e1, e2))

   357 		return expr_copy(e1);

   358 	if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)

   359 		return NULL;

   360 	if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)

   361 		return NULL;

   362 	if (e1->type == E_NOT) {

   363 		tmp = e1->left.expr;

   364 		if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)

   365 			return NULL;

   366 		sym1 = tmp->left.sym;

   367 	} else

   368 		sym1 = e1->left.sym;

   369 	if (e2->type == E_NOT) {

   370 		if (e2->left.expr->type != E_SYMBOL)

   371 			return NULL;

   372 		sym2 = e2->left.expr->left.sym;

   373 	} else

   374 		sym2 = e2->left.sym;

   375 	if (sym1 != sym2)

   376 		return NULL;

   377 	if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)

   378 		return NULL;

   379 	if (sym1->type == S_TRISTATE) {

   380 		if (e1->type == E_EQUAL && e2->type == E_EQUAL &&

   381 		    ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||

   382 		     (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) {

   383 			// (a='y') || (a='m') -> (a!='n')

   384 			return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no);

   385 		}

   386 		if (e1->type == E_EQUAL && e2->type == E_EQUAL &&

   387 		    ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||

   388 		     (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) {

   389 			// (a='y') || (a='n') -> (a!='m')

   390 			return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod);

   391 		}

   392 		if (e1->type == E_EQUAL && e2->type == E_EQUAL &&

   393 		    ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||

   394 		     (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) {

   395 			// (a='m') || (a='n') -> (a!='y')

   396 			return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes);

   397 		}

   398 	}

   399 	if (sym1->type == S_BOOLEAN && sym1 == sym2) {

   400 		if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) ||

   401 		    (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL))

   402 			return expr_alloc_symbol(&symbol_yes);

   403 	}

   405 	if (DEBUG_EXPR) {

   406 		printf("optimize (");

   407 		expr_fprint(e1, stdout);

   408 		printf(") || (");

   409 		expr_fprint(e2, stdout);

   410 		printf(")?\n");

   411 	}

   412 	return NULL;

   413 }

   415 static struct expr *expr_join_and(struct expr *e1, struct expr *e2)

   416 {

   417 	struct expr *tmp;

   418 	struct symbol *sym1, *sym2;

   420 	if (expr_eq(e1, e2))

   421 		return expr_copy(e1);

   422 	if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)

   423 		return NULL;

   424 	if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)

   425 		return NULL;

   426 	if (e1->type == E_NOT) {

   427 		tmp = e1->left.expr;

   428 		if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)

   429 			return NULL;

   430 		sym1 = tmp->left.sym;

   431 	} else

   432 		sym1 = e1->left.sym;

   433 	if (e2->type == E_NOT) {

   434 		if (e2->left.expr->type != E_SYMBOL)

   435 			return NULL;

   436 		sym2 = e2->left.expr->left.sym;

   437 	} else

   438 		sym2 = e2->left.sym;

   439 	if (sym1 != sym2)

   440 		return NULL;

   441 	if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)

   442 		return NULL;

   444 	if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) ||

   445 	    (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes))

   446 		// (a) && (a='y') -> (a='y')

   447 		return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);

   449 	if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) ||

   450 	    (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no))

   451 		// (a) && (a!='n') -> (a)

   452 		return expr_alloc_symbol(sym1);

   454 	if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) ||

   455 	    (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod))

   456 		// (a) && (a!='m') -> (a='y')

   457 		return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);

   459 	if (sym1->type == S_TRISTATE) {

   460 		if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) {

   461 			// (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'

   462 			sym2 = e1->right.sym;

   463 			if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))

   464 				return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)

   465 							     : expr_alloc_symbol(&symbol_no);

   466 		}

   467 		if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) {

   468 			// (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'

   469 			sym2 = e2->right.sym;

   470 			if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))

   471 				return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)

   472 							     : expr_alloc_symbol(&symbol_no);

   473 		}

   474 		if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&

   475 			   ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||

   476 			    (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes)))

   477 			// (a!='y') && (a!='n') -> (a='m')

   478 			return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod);

   480 		if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&

   481 			   ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||

   482 			    (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes)))

   483 			// (a!='y') && (a!='m') -> (a='n')

   484 			return expr_alloc_comp(E_EQUAL, sym1, &symbol_no);

   486 		if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&

   487 			   ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||

   488 			    (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod)))

   489 			// (a!='m') && (a!='n') -> (a='m')

   490 			return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);

   492 		if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) ||

   493 		    (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) ||

   494 		    (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) ||

   495 		    (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes))

   496 			return NULL;

   497 	}

   499 	if (DEBUG_EXPR) {

   500 		printf("optimize (");

   501 		expr_fprint(e1, stdout);

   502 		printf(") && (");

   503 		expr_fprint(e2, stdout);

   504 		printf(")?\n");

   505 	}

   506 	return NULL;

   507 }

   509 static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2)

   510 {

   511 #define e1 (*ep1)

   512 #define e2 (*ep2)

   513 	struct expr *tmp;

   515 	if (e1->type == type) {

   516 		expr_eliminate_dups1(type, &e1->left.expr, &e2);

   517 		expr_eliminate_dups1(type, &e1->right.expr, &e2);

   518 		return;

   519 	}

   520 	if (e2->type == type) {

   521 		expr_eliminate_dups1(type, &e1, &e2->left.expr);

   522 		expr_eliminate_dups1(type, &e1, &e2->right.expr);

   523 		return;

   524 	}

   525 	if (e1 == e2)

   526 		return;

   528 	switch (e1->type) {

   529 	case E_OR: case E_AND:

   530 		expr_eliminate_dups1(e1->type, &e1, &e1);

   531 	default:

   532 		;

   533 	}

   535 	switch (type) {

   536 	case E_OR:

   537 		tmp = expr_join_or(e1, e2);

   538 		if (tmp) {

   539 			expr_free(e1); expr_free(e2);

   540 			e1 = expr_alloc_symbol(&symbol_no);

   541 			e2 = tmp;

   542 			trans_count++;

   543 		}

   544 		break;

   545 	case E_AND:

   546 		tmp = expr_join_and(e1, e2);

   547 		if (tmp) {

   548 			expr_free(e1); expr_free(e2);

   549 			e1 = expr_alloc_symbol(&symbol_yes);

   550 			e2 = tmp;

   551 			trans_count++;

   552 		}

   553 		break;

   554 	default:

   555 		;

   556 	}

   557 #undef e1

   558 #undef e2

   559 }

   561 static void expr_eliminate_dups2(enum expr_type type, struct expr **ep1, struct expr **ep2)

   562 {

   563 #define e1 (*ep1)

   564 #define e2 (*ep2)

   565 	struct expr *tmp, *tmp1, *tmp2;

   567 	if (e1->type == type) {

   568 		expr_eliminate_dups2(type, &e1->left.expr, &e2);

   569 		expr_eliminate_dups2(type, &e1->right.expr, &e2);

   570 		return;

   571 	}

   572 	if (e2->type == type) {

   573 		expr_eliminate_dups2(type, &e1, &e2->left.expr);

   574 		expr_eliminate_dups2(type, &e1, &e2->right.expr);

   575 	}

   576 	if (e1 == e2)

   577 		return;

   579 	switch (e1->type) {

   580 	case E_OR:

   581 		expr_eliminate_dups2(e1->type, &e1, &e1);

   582 		// (FOO || BAR) && (!FOO && !BAR) -> n

   583 		tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1)));

   584 		tmp2 = expr_copy(e2);

   585 		tmp = expr_extract_eq_and(&tmp1, &tmp2);

   586 		if (expr_is_yes(tmp1)) {

   587 			expr_free(e1);

   588 			e1 = expr_alloc_symbol(&symbol_no);

   589 			trans_count++;

   590 		}

   591 		expr_free(tmp2);

   592 		expr_free(tmp1);

   593 		expr_free(tmp);

   594 		break;

   595 	case E_AND:

   596 		expr_eliminate_dups2(e1->type, &e1, &e1);

   597 		// (FOO && BAR) || (!FOO || !BAR) -> y

   598 		tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1)));

   599 		tmp2 = expr_copy(e2);

   600 		tmp = expr_extract_eq_or(&tmp1, &tmp2);

   601 		if (expr_is_no(tmp1)) {

   602 			expr_free(e1);

   603 			e1 = expr_alloc_symbol(&symbol_yes);

   604 			trans_count++;

   605 		}

   606 		expr_free(tmp2);

   607 		expr_free(tmp1);

   608 		expr_free(tmp);

   609 		break;

   610 	default:

   611 		;

   612 	}

   613 #undef e1

   614 #undef e2

   615 }

   617 struct expr *expr_eliminate_dups(struct expr *e)

   618 {

   619 	int oldcount;

   620 	if (!e)

   621 		return e;

   623 	oldcount = trans_count;

   624 	while (1) {

   625 		trans_count = 0;

   626 		switch (e->type) {

   627 		case E_OR: case E_AND:

   628 			expr_eliminate_dups1(e->type, &e, &e);

   629 			expr_eliminate_dups2(e->type, &e, &e);

   630 		default:

   631 			;

   632 		}

   633 		if (!trans_count)

   634 			break;

   635 		e = expr_eliminate_yn(e);

   636 	}

   637 	trans_count = oldcount;

   638 	return e;

   639 }

   641 struct expr *expr_transform(struct expr *e)

   642 {

   643 	struct expr *tmp;

   645 	if (!e)

   646 		return NULL;

   647 	switch (e->type) {

   648 	case E_EQUAL:

   649 	case E_UNEQUAL:

   650 	case E_SYMBOL:

   651 	case E_LIST:

   652 		break;

   653 	default:

   654 		e->left.expr = expr_transform(e->left.expr);

   655 		e->right.expr = expr_transform(e->right.expr);

   656 	}

   658 	switch (e->type) {

   659 	case E_EQUAL:

   660 		if (e->left.sym->type != S_BOOLEAN)

   661 			break;

   662 		if (e->right.sym == &symbol_no) {

   663 			e->type = E_NOT;

   664 			e->left.expr = expr_alloc_symbol(e->left.sym);

   665 			e->right.sym = NULL;

   666 			break;

   667 		}

   668 		if (e->right.sym == &symbol_mod) {

   669 			printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name);

   670 			e->type = E_SYMBOL;

   671 			e->left.sym = &symbol_no;

   672 			e->right.sym = NULL;

   673 			break;

   674 		}

   675 		if (e->right.sym == &symbol_yes) {

   676 			e->type = E_SYMBOL;

   677 			e->right.sym = NULL;

   678 			break;

   679 		}

   680 		break;

   681 	case E_UNEQUAL:

   682 		if (e->left.sym->type != S_BOOLEAN)

   683 			break;

   684 		if (e->right.sym == &symbol_no) {

   685 			e->type = E_SYMBOL;

   686 			e->right.sym = NULL;

   687 			break;

   688 		}

   689 		if (e->right.sym == &symbol_mod) {

   690 			printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name);

   691 			e->type = E_SYMBOL;

   692 			e->left.sym = &symbol_yes;

   693 			e->right.sym = NULL;

   694 			break;

   695 		}

   696 		if (e->right.sym == &symbol_yes) {

   697 			e->type = E_NOT;

   698 			e->left.expr = expr_alloc_symbol(e->left.sym);

   699 			e->right.sym = NULL;

   700 			break;

   701 		}

   702 		break;

   703 	case E_NOT:

   704 		switch (e->left.expr->type) {

   705 		case E_NOT:

   706 			// !!a -> a

   707 			tmp = e->left.expr->left.expr;

   708 			free(e->left.expr);

   709 			free(e);

   710 			e = tmp;

   711 			e = expr_transform(e);

   712 			break;

   713 		case E_EQUAL:

   714 		case E_UNEQUAL:

   715 			// !a='x' -> a!='x'

   716 			tmp = e->left.expr;

   717 			free(e);

   718 			e = tmp;

   719 			e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL;

   720 			break;

   721 		case E_OR:

   722 			// !(a || b) -> !a && !b

   723 			tmp = e->left.expr;

   724 			e->type = E_AND;

   725 			e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);

   726 			tmp->type = E_NOT;

   727 			tmp->right.expr = NULL;

   728 			e = expr_transform(e);

   729 			break;

   730 		case E_AND:

   731 			// !(a && b) -> !a || !b

   732 			tmp = e->left.expr;

   733 			e->type = E_OR;

   734 			e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);

   735 			tmp->type = E_NOT;

   736 			tmp->right.expr = NULL;

   737 			e = expr_transform(e);

   738 			break;

   739 		case E_SYMBOL:

   740 			if (e->left.expr->left.sym == &symbol_yes) {

   741 				// !'y' -> 'n'

   742 				tmp = e->left.expr;

   743 				free(e);

   744 				e = tmp;

   745 				e->type = E_SYMBOL;

   746 				e->left.sym = &symbol_no;

   747 				break;

   748 			}

   749 			if (e->left.expr->left.sym == &symbol_mod) {

   750 				// !'m' -> 'm'

   751 				tmp = e->left.expr;

   752 				free(e);

   753 				e = tmp;

   754 				e->type = E_SYMBOL;

   755 				e->left.sym = &symbol_mod;

   756 				break;

   757 			}

   758 			if (e->left.expr->left.sym == &symbol_no) {

   759 				// !'n' -> 'y'

   760 				tmp = e->left.expr;

   761 				free(e);

   762 				e = tmp;

   763 				e->type = E_SYMBOL;

   764 				e->left.sym = &symbol_yes;

   765 				break;

   766 			}

   767 			break;

   768 		default:

   769 			;

   770 		}

   771 		break;

   772 	default:

   773 		;

   774 	}

   775 	return e;

   776 }

   778 int expr_contains_symbol(struct expr *dep, struct symbol *sym)

   779 {

   780 	if (!dep)

   781 		return 0;

   783 	switch (dep->type) {

   784 	case E_AND:

   785 	case E_OR:

   786 		return expr_contains_symbol(dep->left.expr, sym) ||

   787 		       expr_contains_symbol(dep->right.expr, sym);

   788 	case E_SYMBOL:

   789 		return dep->left.sym == sym;

   790 	case E_EQUAL:

   791 	case E_UNEQUAL:

   792 		return dep->left.sym == sym ||

   793 		       dep->right.sym == sym;

   794 	case E_NOT:

   795 		return expr_contains_symbol(dep->left.expr, sym);

   796 	default:

   797 		;

   798 	}

   799 	return 0;

   800 }

   802 bool expr_depends_symbol(struct expr *dep, struct symbol *sym)

   803 {

   804 	if (!dep)

   805 		return false;

   807 	switch (dep->type) {

   808 	case E_AND:

   809 		return expr_depends_symbol(dep->left.expr, sym) ||

   810 		       expr_depends_symbol(dep->right.expr, sym);

   811 	case E_SYMBOL:

   812 		return dep->left.sym == sym;

   813 	case E_EQUAL:

   814 		if (dep->left.sym == sym) {

   815 			if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod)

   816 				return true;

   817 		}

   818 		break;

   819 	case E_UNEQUAL:

   820 		if (dep->left.sym == sym) {

   821 			if (dep->right.sym == &symbol_no)

   822 				return true;

   823 		}

   824 		break;

   825 	default:

   826 		;

   827 	}

   828  	return false;

   829 }

   831 struct expr *expr_extract_eq_and(struct expr **ep1, struct expr **ep2)

   832 {

   833 	struct expr *tmp = NULL;

   834 	expr_extract_eq(E_AND, &tmp, ep1, ep2);

   835 	if (tmp) {

   836 		*ep1 = expr_eliminate_yn(*ep1);

   837 		*ep2 = expr_eliminate_yn(*ep2);

   838 	}

   839 	return tmp;

   840 }

   842 struct expr *expr_extract_eq_or(struct expr **ep1, struct expr **ep2)

   843 {

   844 	struct expr *tmp = NULL;

   845 	expr_extract_eq(E_OR, &tmp, ep1, ep2);

   846 	if (tmp) {

   847 		*ep1 = expr_eliminate_yn(*ep1);

   848 		*ep2 = expr_eliminate_yn(*ep2);

   849 	}

   850 	return tmp;

   851 }

   853 void expr_extract_eq(enum expr_type type, struct expr **ep, struct expr **ep1, struct expr **ep2)

   854 {

   855 #define e1 (*ep1)

   856 #define e2 (*ep2)

   857 	if (e1->type == type) {

   858 		expr_extract_eq(type, ep, &e1->left.expr, &e2);

   859 		expr_extract_eq(type, ep, &e1->right.expr, &e2);

   860 		return;

   861 	}

   862 	if (e2->type == type) {

   863 		expr_extract_eq(type, ep, ep1, &e2->left.expr);

   864 		expr_extract_eq(type, ep, ep1, &e2->right.expr);

   865 		return;

   866 	}

   867 	if (expr_eq(e1, e2)) {

   868 		*ep = *ep ? expr_alloc_two(type, *ep, e1) : e1;

   869 		expr_free(e2);

   870 		if (type == E_AND) {

   871 			e1 = expr_alloc_symbol(&symbol_yes);

   872 			e2 = expr_alloc_symbol(&symbol_yes);

   873 		} else if (type == E_OR) {

   874 			e1 = expr_alloc_symbol(&symbol_no);

   875 			e2 = expr_alloc_symbol(&symbol_no);

   876 		}

   877 	}

   878 #undef e1

   879 #undef e2

   880 }

   882 struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)

   883 {

   884 	struct expr *e1, *e2;

   886 	if (!e) {

   887 		e = expr_alloc_symbol(sym);

   888 		if (type == E_UNEQUAL)

   889 			e = expr_alloc_one(E_NOT, e);

   890 		return e;

   891 	}

   892 	switch (e->type) {

   893 	case E_AND:

   894 		e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);

   895 		e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);

   896 		if (sym == &symbol_yes)

   897 			e = expr_alloc_two(E_AND, e1, e2);

   898 		if (sym == &symbol_no)

   899 			e = expr_alloc_two(E_OR, e1, e2);

   900 		if (type == E_UNEQUAL)

   901 			e = expr_alloc_one(E_NOT, e);

   902 		return e;

   903 	case E_OR:

   904 		e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);

   905 		e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);

   906 		if (sym == &symbol_yes)

   907 			e = expr_alloc_two(E_OR, e1, e2);

   908 		if (sym == &symbol_no)

   909 			e = expr_alloc_two(E_AND, e1, e2);

   910 		if (type == E_UNEQUAL)

   911 			e = expr_alloc_one(E_NOT, e);

   912 		return e;

   913 	case E_NOT:

   914 		return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym);

   915 	case E_UNEQUAL:

   916 	case E_EQUAL:

   917 		if (type == E_EQUAL) {

   918 			if (sym == &symbol_yes)

   919 				return expr_copy(e);

   920 			if (sym == &symbol_mod)

   921 				return expr_alloc_symbol(&symbol_no);

   922 			if (sym == &symbol_no)

   923 				return expr_alloc_one(E_NOT, expr_copy(e));

   924 		} else {

   925 			if (sym == &symbol_yes)

   926 				return expr_alloc_one(E_NOT, expr_copy(e));

   927 			if (sym == &symbol_mod)

   928 				return expr_alloc_symbol(&symbol_yes);

   929 			if (sym == &symbol_no)

   930 				return expr_copy(e);

   931 		}

   932 		break;

   933 	case E_SYMBOL:

   934 		return expr_alloc_comp(type, e->left.sym, sym);

   935 	case E_LIST:

   936 	case E_RANGE:

   937 	case E_NONE:

   938 		/* panic */;

   939 	}

   940 	return NULL;

   941 }

   943 tristate expr_calc_value(struct expr *e)

   944 {

   945 	tristate val1, val2;

   946 	const char *str1, *str2;

   948 	if (!e)

   949 		return yes;

   951 	switch (e->type) {

   952 	case E_SYMBOL:

   953 		sym_calc_value(e->left.sym);

   954 		return e->left.sym->curr.tri;

   955 	case E_AND:

   956 		val1 = expr_calc_value(e->left.expr);

   957 		val2 = expr_calc_value(e->right.expr);

   958 		return EXPR_AND(val1, val2);

   959 	case E_OR:

   960 		val1 = expr_calc_value(e->left.expr);

   961 		val2 = expr_calc_value(e->right.expr);

   962 		return EXPR_OR(val1, val2);

   963 	case E_NOT:

   964 		val1 = expr_calc_value(e->left.expr);

   965 		return EXPR_NOT(val1);

   966 	case E_EQUAL:

   967 		sym_calc_value(e->left.sym);

   968 		sym_calc_value(e->right.sym);

   969 		str1 = sym_get_string_value(e->left.sym);

   970 		str2 = sym_get_string_value(e->right.sym);

   971 		return !strcmp(str1, str2) ? yes : no;

   972 	case E_UNEQUAL:

   973 		sym_calc_value(e->left.sym);

   974 		sym_calc_value(e->right.sym);

   975 		str1 = sym_get_string_value(e->left.sym);

   976 		str2 = sym_get_string_value(e->right.sym);

   977 		return !strcmp(str1, str2) ? no : yes;

   978 	default:

   979 		printf("expr_calc_value: %d?\n", e->type);

   980 		return no;

   981 	}

   982 }

   984 int expr_compare_type(enum expr_type t1, enum expr_type t2)

   985 {

   986 #if 0

   987 	return 1;

   988 #else

   989 	if (t1 == t2)

   990 		return 0;

   991 	switch (t1) {

   992 	case E_EQUAL:

   993 	case E_UNEQUAL:

   994 		if (t2 == E_NOT)

   995 			return 1;

   996 	case E_NOT:

   997 		if (t2 == E_AND)

   998 			return 1;

   999 	case E_AND:

  1000 		if (t2 == E_OR)

  1001 			return 1;

  1002 	case E_OR:

  1003 		if (t2 == E_LIST)

  1004 			return 1;

  1005 	case E_LIST:

  1006 		if (t2 == 0)

  1007 			return 1;

  1008 	default:

  1009 		return -1;

  1010 	}

  1011 	printf("[%dgt%d?]", t1, t2);

  1012 	return 0;

  1013 #endif

  1014 }

  1016 static inline struct expr *

  1017 expr_get_leftmost_symbol(const struct expr *e)

  1018 {

  1020 	if (e == NULL)

  1021 		return NULL;

  1023 	while (e->type != E_SYMBOL)

  1024 		e = e->left.expr;

  1026 	return expr_copy(e);

  1027 }

  1029 /*

  1030  * Given expression `e1' and `e2', returns the leaf of the longest

  1031  * sub-expression of `e1' not containing 'e2.

  1032  */

  1033 struct expr *expr_simplify_unmet_dep(struct expr *e1, struct expr *e2)

  1034 {

  1035 	struct expr *ret;

  1037 	switch (e1->type) {

  1038 	case E_OR:

  1039 		return expr_alloc_and(

  1040 		    expr_simplify_unmet_dep(e1->left.expr, e2),

  1041 		    expr_simplify_unmet_dep(e1->right.expr, e2));

  1042 	case E_AND: {

  1043 		struct expr *e;

  1044 		e = expr_alloc_and(expr_copy(e1), expr_copy(e2));

  1045 		e = expr_eliminate_dups(e);

  1046 		ret = (!expr_eq(e, e1)) ? e1 : NULL;

  1047 		expr_free(e);

  1048 		break;

  1049 		}

  1050 	default:

  1051 		ret = e1;

  1052 		break;

  1053 	}

  1055 	return expr_get_leftmost_symbol(ret);

  1056 }

  1058 void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken)

  1059 {

  1060 	if (!e) {

  1061 		fn(data, NULL, "y");

  1062 		return;

  1063 	}

  1065 	if (expr_compare_type(prevtoken, e->type) > 0)

  1066 		fn(data, NULL, "(");

  1067 	switch (e->type) {

  1068 	case E_SYMBOL:

  1069 		if (e->left.sym->name)

  1070 			fn(data, e->left.sym, e->left.sym->name);

  1071 		else

  1072 			fn(data, NULL, "<choice>");

  1073 		break;

  1074 	case E_NOT:

  1075 		fn(data, NULL, "!");

  1076 		expr_print(e->left.expr, fn, data, E_NOT);

  1077 		break;

  1078 	case E_EQUAL:

  1079 		if (e->left.sym->name)

  1080 			fn(data, e->left.sym, e->left.sym->name);

  1081 		else

  1082 			fn(data, NULL, "<choice>");

  1083 		fn(data, NULL, "=");

  1084 		fn(data, e->right.sym, e->right.sym->name);

  1085 		break;

  1086 	case E_UNEQUAL:

  1087 		if (e->left.sym->name)

  1088 			fn(data, e->left.sym, e->left.sym->name);

  1089 		else

  1090 			fn(data, NULL, "<choice>");

  1091 		fn(data, NULL, "!=");

  1092 		fn(data, e->right.sym, e->right.sym->name);

  1093 		break;

  1094 	case E_OR:

  1095 		expr_print(e->left.expr, fn, data, E_OR);

  1096 		fn(data, NULL, " || ");

  1097 		expr_print(e->right.expr, fn, data, E_OR);

  1098 		break;

  1099 	case E_AND:

  1100 		expr_print(e->left.expr, fn, data, E_AND);

  1101 		fn(data, NULL, " && ");

  1102 		expr_print(e->right.expr, fn, data, E_AND);

  1103 		break;

  1104 	case E_LIST:

  1105 		fn(data, e->right.sym, e->right.sym->name);

  1106 		if (e->left.expr) {

  1107 			fn(data, NULL, " ^ ");

  1108 			expr_print(e->left.expr, fn, data, E_LIST);

  1109 		}

  1110 		break;

  1111 	case E_RANGE:

  1112 		fn(data, NULL, "[");

  1113 		fn(data, e->left.sym, e->left.sym->name);

  1114 		fn(data, NULL, " ");

  1115 		fn(data, e->right.sym, e->right.sym->name);

  1116 		fn(data, NULL, "]");

  1117 		break;

  1118 	default:

  1119 	  {

  1120 		char buf[32];

  1121 		sprintf(buf, "<unknown type %d>", e->type);

  1122 		fn(data, NULL, buf);

  1123 		break;

  1124 	  }

  1125 	}

  1126 	if (expr_compare_type(prevtoken, e->type) > 0)

  1127 		fn(data, NULL, ")");

  1128 }

  1130 static void expr_print_file_helper(void *data, struct symbol *sym, const char *str)

  1131 {

  1132 	xfwrite(str, strlen(str), 1, data);

  1133 }

  1135 void expr_fprint(struct expr *e, FILE *out)

  1136 {

  1137 	expr_print(e, expr_print_file_helper, out, E_NONE);

  1138 }

  1140 static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str)

  1141 {

  1142 	struct gstr *gs = (struct gstr*)data;

  1143 	const char *sym_str = NULL;

  1145 	if (sym)

  1146 		sym_str = sym_get_string_value(sym);

  1148 	if (gs->max_width) {

  1149 		unsigned extra_length = strlen(str);

  1150 		const char *last_cr = strrchr(gs->s, '\n');

  1151 		unsigned last_line_length;

  1153 		if (sym_str)

  1154 			extra_length += 4 + strlen(sym_str);

  1156 		if (!last_cr)

  1157 			last_cr = gs->s;

  1159 		last_line_length = strlen(gs->s) - (last_cr - gs->s);

  1161 		if ((last_line_length + extra_length) > gs->max_width)

  1162 			str_append(gs, "\\\n");

  1163 	}

  1165 	str_append(gs, str);

  1166 	if (sym && sym->type != S_UNKNOWN)

  1167 		str_printf(gs, " [=%s]", sym_str);

  1168 }

  1170 void expr_gstr_print(struct expr *e, struct gstr *gs)

  1171 {

  1172 	expr_print(e, expr_print_gstr_helper, gs, E_NONE);

  1173 }

author	"Yann E. MORIN" <yann.morin.1998@free.fr>
	Tue Mar 11 22:11:43 2014 +0100 (2014-03-11)
changeset 3293	e11a8a2e225d
parent 943	1cca90ce0481
permissions	-rw-r--r--