xref: /openbmc/linux/scripts/kconfig/symbol.c (revision 82e6fdd6)
1 /*
2  * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org>
3  * Released under the terms of the GNU GPL v2.0.
4  */
5 
6 #include <ctype.h>
7 #include <stdlib.h>
8 #include <string.h>
9 #include <regex.h>
10 #include <sys/utsname.h>
11 
12 #include "lkc.h"
13 
14 struct symbol symbol_yes = {
15 	.name = "y",
16 	.curr = { "y", yes },
17 	.flags = SYMBOL_CONST|SYMBOL_VALID,
18 }, symbol_mod = {
19 	.name = "m",
20 	.curr = { "m", mod },
21 	.flags = SYMBOL_CONST|SYMBOL_VALID,
22 }, symbol_no = {
23 	.name = "n",
24 	.curr = { "n", no },
25 	.flags = SYMBOL_CONST|SYMBOL_VALID,
26 }, symbol_empty = {
27 	.name = "",
28 	.curr = { "", no },
29 	.flags = SYMBOL_VALID,
30 };
31 
32 struct symbol *sym_defconfig_list;
33 struct symbol *modules_sym;
34 tristate modules_val;
35 
36 struct expr *sym_env_list;
37 
38 static void sym_add_default(struct symbol *sym, const char *def)
39 {
40 	struct property *prop = prop_alloc(P_DEFAULT, sym);
41 
42 	prop->expr = expr_alloc_symbol(sym_lookup(def, SYMBOL_CONST));
43 }
44 
45 void sym_init(void)
46 {
47 	struct symbol *sym;
48 	struct utsname uts;
49 	static bool inited = false;
50 
51 	if (inited)
52 		return;
53 	inited = true;
54 
55 	uname(&uts);
56 
57 	sym = sym_lookup("UNAME_RELEASE", 0);
58 	sym->type = S_STRING;
59 	sym->flags |= SYMBOL_AUTO;
60 	sym_add_default(sym, uts.release);
61 }
62 
63 enum symbol_type sym_get_type(struct symbol *sym)
64 {
65 	enum symbol_type type = sym->type;
66 
67 	if (type == S_TRISTATE) {
68 		if (sym_is_choice_value(sym) && sym->visible == yes)
69 			type = S_BOOLEAN;
70 		else if (modules_val == no)
71 			type = S_BOOLEAN;
72 	}
73 	return type;
74 }
75 
76 const char *sym_type_name(enum symbol_type type)
77 {
78 	switch (type) {
79 	case S_BOOLEAN:
80 		return "bool";
81 	case S_TRISTATE:
82 		return "tristate";
83 	case S_INT:
84 		return "integer";
85 	case S_HEX:
86 		return "hex";
87 	case S_STRING:
88 		return "string";
89 	case S_UNKNOWN:
90 		return "unknown";
91 	case S_OTHER:
92 		break;
93 	}
94 	return "???";
95 }
96 
97 struct property *sym_get_choice_prop(struct symbol *sym)
98 {
99 	struct property *prop;
100 
101 	for_all_choices(sym, prop)
102 		return prop;
103 	return NULL;
104 }
105 
106 struct property *sym_get_env_prop(struct symbol *sym)
107 {
108 	struct property *prop;
109 
110 	for_all_properties(sym, prop, P_ENV)
111 		return prop;
112 	return NULL;
113 }
114 
115 static struct property *sym_get_default_prop(struct symbol *sym)
116 {
117 	struct property *prop;
118 
119 	for_all_defaults(sym, prop) {
120 		prop->visible.tri = expr_calc_value(prop->visible.expr);
121 		if (prop->visible.tri != no)
122 			return prop;
123 	}
124 	return NULL;
125 }
126 
127 static struct property *sym_get_range_prop(struct symbol *sym)
128 {
129 	struct property *prop;
130 
131 	for_all_properties(sym, prop, P_RANGE) {
132 		prop->visible.tri = expr_calc_value(prop->visible.expr);
133 		if (prop->visible.tri != no)
134 			return prop;
135 	}
136 	return NULL;
137 }
138 
139 static long long sym_get_range_val(struct symbol *sym, int base)
140 {
141 	sym_calc_value(sym);
142 	switch (sym->type) {
143 	case S_INT:
144 		base = 10;
145 		break;
146 	case S_HEX:
147 		base = 16;
148 		break;
149 	default:
150 		break;
151 	}
152 	return strtoll(sym->curr.val, NULL, base);
153 }
154 
155 static void sym_validate_range(struct symbol *sym)
156 {
157 	struct property *prop;
158 	int base;
159 	long long val, val2;
160 	char str[64];
161 
162 	switch (sym->type) {
163 	case S_INT:
164 		base = 10;
165 		break;
166 	case S_HEX:
167 		base = 16;
168 		break;
169 	default:
170 		return;
171 	}
172 	prop = sym_get_range_prop(sym);
173 	if (!prop)
174 		return;
175 	val = strtoll(sym->curr.val, NULL, base);
176 	val2 = sym_get_range_val(prop->expr->left.sym, base);
177 	if (val >= val2) {
178 		val2 = sym_get_range_val(prop->expr->right.sym, base);
179 		if (val <= val2)
180 			return;
181 	}
182 	if (sym->type == S_INT)
183 		sprintf(str, "%lld", val2);
184 	else
185 		sprintf(str, "0x%llx", val2);
186 	sym->curr.val = xstrdup(str);
187 }
188 
189 static void sym_set_changed(struct symbol *sym)
190 {
191 	struct property *prop;
192 
193 	sym->flags |= SYMBOL_CHANGED;
194 	for (prop = sym->prop; prop; prop = prop->next) {
195 		if (prop->menu)
196 			prop->menu->flags |= MENU_CHANGED;
197 	}
198 }
199 
200 static void sym_set_all_changed(void)
201 {
202 	struct symbol *sym;
203 	int i;
204 
205 	for_all_symbols(i, sym)
206 		sym_set_changed(sym);
207 }
208 
209 static void sym_calc_visibility(struct symbol *sym)
210 {
211 	struct property *prop;
212 	struct symbol *choice_sym = NULL;
213 	tristate tri;
214 
215 	/* any prompt visible? */
216 	tri = no;
217 
218 	if (sym_is_choice_value(sym))
219 		choice_sym = prop_get_symbol(sym_get_choice_prop(sym));
220 
221 	for_all_prompts(sym, prop) {
222 		prop->visible.tri = expr_calc_value(prop->visible.expr);
223 		/*
224 		 * Tristate choice_values with visibility 'mod' are
225 		 * not visible if the corresponding choice's value is
226 		 * 'yes'.
227 		 */
228 		if (choice_sym && sym->type == S_TRISTATE &&
229 		    prop->visible.tri == mod && choice_sym->curr.tri == yes)
230 			prop->visible.tri = no;
231 
232 		tri = EXPR_OR(tri, prop->visible.tri);
233 	}
234 	if (tri == mod && (sym->type != S_TRISTATE || modules_val == no))
235 		tri = yes;
236 	if (sym->visible != tri) {
237 		sym->visible = tri;
238 		sym_set_changed(sym);
239 	}
240 	if (sym_is_choice_value(sym))
241 		return;
242 	/* defaulting to "yes" if no explicit "depends on" are given */
243 	tri = yes;
244 	if (sym->dir_dep.expr)
245 		tri = expr_calc_value(sym->dir_dep.expr);
246 	if (tri == mod)
247 		tri = yes;
248 	if (sym->dir_dep.tri != tri) {
249 		sym->dir_dep.tri = tri;
250 		sym_set_changed(sym);
251 	}
252 	tri = no;
253 	if (sym->rev_dep.expr)
254 		tri = expr_calc_value(sym->rev_dep.expr);
255 	if (tri == mod && sym_get_type(sym) == S_BOOLEAN)
256 		tri = yes;
257 	if (sym->rev_dep.tri != tri) {
258 		sym->rev_dep.tri = tri;
259 		sym_set_changed(sym);
260 	}
261 	tri = no;
262 	if (sym->implied.expr && sym->dir_dep.tri != no)
263 		tri = expr_calc_value(sym->implied.expr);
264 	if (tri == mod && sym_get_type(sym) == S_BOOLEAN)
265 		tri = yes;
266 	if (sym->implied.tri != tri) {
267 		sym->implied.tri = tri;
268 		sym_set_changed(sym);
269 	}
270 }
271 
272 /*
273  * Find the default symbol for a choice.
274  * First try the default values for the choice symbol
275  * Next locate the first visible choice value
276  * Return NULL if none was found
277  */
278 struct symbol *sym_choice_default(struct symbol *sym)
279 {
280 	struct symbol *def_sym;
281 	struct property *prop;
282 	struct expr *e;
283 
284 	/* any of the defaults visible? */
285 	for_all_defaults(sym, prop) {
286 		prop->visible.tri = expr_calc_value(prop->visible.expr);
287 		if (prop->visible.tri == no)
288 			continue;
289 		def_sym = prop_get_symbol(prop);
290 		if (def_sym->visible != no)
291 			return def_sym;
292 	}
293 
294 	/* just get the first visible value */
295 	prop = sym_get_choice_prop(sym);
296 	expr_list_for_each_sym(prop->expr, e, def_sym)
297 		if (def_sym->visible != no)
298 			return def_sym;
299 
300 	/* failed to locate any defaults */
301 	return NULL;
302 }
303 
304 static struct symbol *sym_calc_choice(struct symbol *sym)
305 {
306 	struct symbol *def_sym;
307 	struct property *prop;
308 	struct expr *e;
309 	int flags;
310 
311 	/* first calculate all choice values' visibilities */
312 	flags = sym->flags;
313 	prop = sym_get_choice_prop(sym);
314 	expr_list_for_each_sym(prop->expr, e, def_sym) {
315 		sym_calc_visibility(def_sym);
316 		if (def_sym->visible != no)
317 			flags &= def_sym->flags;
318 	}
319 
320 	sym->flags &= flags | ~SYMBOL_DEF_USER;
321 
322 	/* is the user choice visible? */
323 	def_sym = sym->def[S_DEF_USER].val;
324 	if (def_sym && def_sym->visible != no)
325 		return def_sym;
326 
327 	def_sym = sym_choice_default(sym);
328 
329 	if (def_sym == NULL)
330 		/* no choice? reset tristate value */
331 		sym->curr.tri = no;
332 
333 	return def_sym;
334 }
335 
336 void sym_calc_value(struct symbol *sym)
337 {
338 	struct symbol_value newval, oldval;
339 	struct property *prop;
340 	struct expr *e;
341 
342 	if (!sym)
343 		return;
344 
345 	if (sym->flags & SYMBOL_VALID)
346 		return;
347 
348 	if (sym_is_choice_value(sym) &&
349 	    sym->flags & SYMBOL_NEED_SET_CHOICE_VALUES) {
350 		sym->flags &= ~SYMBOL_NEED_SET_CHOICE_VALUES;
351 		prop = sym_get_choice_prop(sym);
352 		sym_calc_value(prop_get_symbol(prop));
353 	}
354 
355 	sym->flags |= SYMBOL_VALID;
356 
357 	oldval = sym->curr;
358 
359 	switch (sym->type) {
360 	case S_INT:
361 	case S_HEX:
362 	case S_STRING:
363 		newval = symbol_empty.curr;
364 		break;
365 	case S_BOOLEAN:
366 	case S_TRISTATE:
367 		newval = symbol_no.curr;
368 		break;
369 	default:
370 		sym->curr.val = sym->name;
371 		sym->curr.tri = no;
372 		return;
373 	}
374 	sym->flags &= ~SYMBOL_WRITE;
375 
376 	sym_calc_visibility(sym);
377 
378 	if (sym->visible != no)
379 		sym->flags |= SYMBOL_WRITE;
380 
381 	/* set default if recursively called */
382 	sym->curr = newval;
383 
384 	switch (sym_get_type(sym)) {
385 	case S_BOOLEAN:
386 	case S_TRISTATE:
387 		if (sym_is_choice_value(sym) && sym->visible == yes) {
388 			prop = sym_get_choice_prop(sym);
389 			newval.tri = (prop_get_symbol(prop)->curr.val == sym) ? yes : no;
390 		} else {
391 			if (sym->visible != no) {
392 				/* if the symbol is visible use the user value
393 				 * if available, otherwise try the default value
394 				 */
395 				if (sym_has_value(sym)) {
396 					newval.tri = EXPR_AND(sym->def[S_DEF_USER].tri,
397 							      sym->visible);
398 					goto calc_newval;
399 				}
400 			}
401 			if (sym->rev_dep.tri != no)
402 				sym->flags |= SYMBOL_WRITE;
403 			if (!sym_is_choice(sym)) {
404 				prop = sym_get_default_prop(sym);
405 				if (prop) {
406 					sym->flags |= SYMBOL_WRITE;
407 					newval.tri = EXPR_AND(expr_calc_value(prop->expr),
408 							      prop->visible.tri);
409 				}
410 				if (sym->implied.tri != no) {
411 					sym->flags |= SYMBOL_WRITE;
412 					newval.tri = EXPR_OR(newval.tri, sym->implied.tri);
413 				}
414 			}
415 		calc_newval:
416 			if (sym->dir_dep.tri == no && sym->rev_dep.tri != no) {
417 				struct expr *e;
418 				e = expr_simplify_unmet_dep(sym->rev_dep.expr,
419 				    sym->dir_dep.expr);
420 				fprintf(stderr, "warning: (");
421 				expr_fprint(e, stderr);
422 				fprintf(stderr, ") selects %s which has unmet direct dependencies (",
423 					sym->name);
424 				expr_fprint(sym->dir_dep.expr, stderr);
425 				fprintf(stderr, ")\n");
426 				expr_free(e);
427 			}
428 			newval.tri = EXPR_OR(newval.tri, sym->rev_dep.tri);
429 		}
430 		if (newval.tri == mod &&
431 		    (sym_get_type(sym) == S_BOOLEAN || sym->implied.tri == yes))
432 			newval.tri = yes;
433 		break;
434 	case S_STRING:
435 	case S_HEX:
436 	case S_INT:
437 		if (sym->visible != no && sym_has_value(sym)) {
438 			newval.val = sym->def[S_DEF_USER].val;
439 			break;
440 		}
441 		prop = sym_get_default_prop(sym);
442 		if (prop) {
443 			struct symbol *ds = prop_get_symbol(prop);
444 			if (ds) {
445 				sym->flags |= SYMBOL_WRITE;
446 				sym_calc_value(ds);
447 				newval.val = ds->curr.val;
448 			}
449 		}
450 		break;
451 	default:
452 		;
453 	}
454 
455 	sym->curr = newval;
456 	if (sym_is_choice(sym) && newval.tri == yes)
457 		sym->curr.val = sym_calc_choice(sym);
458 	sym_validate_range(sym);
459 
460 	if (memcmp(&oldval, &sym->curr, sizeof(oldval))) {
461 		sym_set_changed(sym);
462 		if (modules_sym == sym) {
463 			sym_set_all_changed();
464 			modules_val = modules_sym->curr.tri;
465 		}
466 	}
467 
468 	if (sym_is_choice(sym)) {
469 		struct symbol *choice_sym;
470 
471 		prop = sym_get_choice_prop(sym);
472 		expr_list_for_each_sym(prop->expr, e, choice_sym) {
473 			if ((sym->flags & SYMBOL_WRITE) &&
474 			    choice_sym->visible != no)
475 				choice_sym->flags |= SYMBOL_WRITE;
476 			if (sym->flags & SYMBOL_CHANGED)
477 				sym_set_changed(choice_sym);
478 		}
479 	}
480 
481 	if (sym->flags & SYMBOL_AUTO)
482 		sym->flags &= ~SYMBOL_WRITE;
483 
484 	if (sym->flags & SYMBOL_NEED_SET_CHOICE_VALUES)
485 		set_all_choice_values(sym);
486 }
487 
488 void sym_clear_all_valid(void)
489 {
490 	struct symbol *sym;
491 	int i;
492 
493 	for_all_symbols(i, sym)
494 		sym->flags &= ~SYMBOL_VALID;
495 	sym_add_change_count(1);
496 	sym_calc_value(modules_sym);
497 }
498 
499 bool sym_tristate_within_range(struct symbol *sym, tristate val)
500 {
501 	int type = sym_get_type(sym);
502 
503 	if (sym->visible == no)
504 		return false;
505 
506 	if (type != S_BOOLEAN && type != S_TRISTATE)
507 		return false;
508 
509 	if (type == S_BOOLEAN && val == mod)
510 		return false;
511 	if (sym->visible <= sym->rev_dep.tri)
512 		return false;
513 	if (sym->implied.tri == yes && val == mod)
514 		return false;
515 	if (sym_is_choice_value(sym) && sym->visible == yes)
516 		return val == yes;
517 	return val >= sym->rev_dep.tri && val <= sym->visible;
518 }
519 
520 bool sym_set_tristate_value(struct symbol *sym, tristate val)
521 {
522 	tristate oldval = sym_get_tristate_value(sym);
523 
524 	if (oldval != val && !sym_tristate_within_range(sym, val))
525 		return false;
526 
527 	if (!(sym->flags & SYMBOL_DEF_USER)) {
528 		sym->flags |= SYMBOL_DEF_USER;
529 		sym_set_changed(sym);
530 	}
531 	/*
532 	 * setting a choice value also resets the new flag of the choice
533 	 * symbol and all other choice values.
534 	 */
535 	if (sym_is_choice_value(sym) && val == yes) {
536 		struct symbol *cs = prop_get_symbol(sym_get_choice_prop(sym));
537 		struct property *prop;
538 		struct expr *e;
539 
540 		cs->def[S_DEF_USER].val = sym;
541 		cs->flags |= SYMBOL_DEF_USER;
542 		prop = sym_get_choice_prop(cs);
543 		for (e = prop->expr; e; e = e->left.expr) {
544 			if (e->right.sym->visible != no)
545 				e->right.sym->flags |= SYMBOL_DEF_USER;
546 		}
547 	}
548 
549 	sym->def[S_DEF_USER].tri = val;
550 	if (oldval != val)
551 		sym_clear_all_valid();
552 
553 	return true;
554 }
555 
556 tristate sym_toggle_tristate_value(struct symbol *sym)
557 {
558 	tristate oldval, newval;
559 
560 	oldval = newval = sym_get_tristate_value(sym);
561 	do {
562 		switch (newval) {
563 		case no:
564 			newval = mod;
565 			break;
566 		case mod:
567 			newval = yes;
568 			break;
569 		case yes:
570 			newval = no;
571 			break;
572 		}
573 		if (sym_set_tristate_value(sym, newval))
574 			break;
575 	} while (oldval != newval);
576 	return newval;
577 }
578 
579 bool sym_string_valid(struct symbol *sym, const char *str)
580 {
581 	signed char ch;
582 
583 	switch (sym->type) {
584 	case S_STRING:
585 		return true;
586 	case S_INT:
587 		ch = *str++;
588 		if (ch == '-')
589 			ch = *str++;
590 		if (!isdigit(ch))
591 			return false;
592 		if (ch == '0' && *str != 0)
593 			return false;
594 		while ((ch = *str++)) {
595 			if (!isdigit(ch))
596 				return false;
597 		}
598 		return true;
599 	case S_HEX:
600 		if (str[0] == '0' && (str[1] == 'x' || str[1] == 'X'))
601 			str += 2;
602 		ch = *str++;
603 		do {
604 			if (!isxdigit(ch))
605 				return false;
606 		} while ((ch = *str++));
607 		return true;
608 	case S_BOOLEAN:
609 	case S_TRISTATE:
610 		switch (str[0]) {
611 		case 'y': case 'Y':
612 		case 'm': case 'M':
613 		case 'n': case 'N':
614 			return true;
615 		}
616 		return false;
617 	default:
618 		return false;
619 	}
620 }
621 
622 bool sym_string_within_range(struct symbol *sym, const char *str)
623 {
624 	struct property *prop;
625 	long long val;
626 
627 	switch (sym->type) {
628 	case S_STRING:
629 		return sym_string_valid(sym, str);
630 	case S_INT:
631 		if (!sym_string_valid(sym, str))
632 			return false;
633 		prop = sym_get_range_prop(sym);
634 		if (!prop)
635 			return true;
636 		val = strtoll(str, NULL, 10);
637 		return val >= sym_get_range_val(prop->expr->left.sym, 10) &&
638 		       val <= sym_get_range_val(prop->expr->right.sym, 10);
639 	case S_HEX:
640 		if (!sym_string_valid(sym, str))
641 			return false;
642 		prop = sym_get_range_prop(sym);
643 		if (!prop)
644 			return true;
645 		val = strtoll(str, NULL, 16);
646 		return val >= sym_get_range_val(prop->expr->left.sym, 16) &&
647 		       val <= sym_get_range_val(prop->expr->right.sym, 16);
648 	case S_BOOLEAN:
649 	case S_TRISTATE:
650 		switch (str[0]) {
651 		case 'y': case 'Y':
652 			return sym_tristate_within_range(sym, yes);
653 		case 'm': case 'M':
654 			return sym_tristate_within_range(sym, mod);
655 		case 'n': case 'N':
656 			return sym_tristate_within_range(sym, no);
657 		}
658 		return false;
659 	default:
660 		return false;
661 	}
662 }
663 
664 bool sym_set_string_value(struct symbol *sym, const char *newval)
665 {
666 	const char *oldval;
667 	char *val;
668 	int size;
669 
670 	switch (sym->type) {
671 	case S_BOOLEAN:
672 	case S_TRISTATE:
673 		switch (newval[0]) {
674 		case 'y': case 'Y':
675 			return sym_set_tristate_value(sym, yes);
676 		case 'm': case 'M':
677 			return sym_set_tristate_value(sym, mod);
678 		case 'n': case 'N':
679 			return sym_set_tristate_value(sym, no);
680 		}
681 		return false;
682 	default:
683 		;
684 	}
685 
686 	if (!sym_string_within_range(sym, newval))
687 		return false;
688 
689 	if (!(sym->flags & SYMBOL_DEF_USER)) {
690 		sym->flags |= SYMBOL_DEF_USER;
691 		sym_set_changed(sym);
692 	}
693 
694 	oldval = sym->def[S_DEF_USER].val;
695 	size = strlen(newval) + 1;
696 	if (sym->type == S_HEX && (newval[0] != '0' || (newval[1] != 'x' && newval[1] != 'X'))) {
697 		size += 2;
698 		sym->def[S_DEF_USER].val = val = xmalloc(size);
699 		*val++ = '0';
700 		*val++ = 'x';
701 	} else if (!oldval || strcmp(oldval, newval))
702 		sym->def[S_DEF_USER].val = val = xmalloc(size);
703 	else
704 		return true;
705 
706 	strcpy(val, newval);
707 	free((void *)oldval);
708 	sym_clear_all_valid();
709 
710 	return true;
711 }
712 
713 /*
714  * Find the default value associated to a symbol.
715  * For tristate symbol handle the modules=n case
716  * in which case "m" becomes "y".
717  * If the symbol does not have any default then fallback
718  * to the fixed default values.
719  */
720 const char *sym_get_string_default(struct symbol *sym)
721 {
722 	struct property *prop;
723 	struct symbol *ds;
724 	const char *str;
725 	tristate val;
726 
727 	sym_calc_visibility(sym);
728 	sym_calc_value(modules_sym);
729 	val = symbol_no.curr.tri;
730 	str = symbol_empty.curr.val;
731 
732 	/* If symbol has a default value look it up */
733 	prop = sym_get_default_prop(sym);
734 	if (prop != NULL) {
735 		switch (sym->type) {
736 		case S_BOOLEAN:
737 		case S_TRISTATE:
738 			/* The visibility may limit the value from yes => mod */
739 			val = EXPR_AND(expr_calc_value(prop->expr), prop->visible.tri);
740 			break;
741 		default:
742 			/*
743 			 * The following fails to handle the situation
744 			 * where a default value is further limited by
745 			 * the valid range.
746 			 */
747 			ds = prop_get_symbol(prop);
748 			if (ds != NULL) {
749 				sym_calc_value(ds);
750 				str = (const char *)ds->curr.val;
751 			}
752 		}
753 	}
754 
755 	/* Handle select statements */
756 	val = EXPR_OR(val, sym->rev_dep.tri);
757 
758 	/* transpose mod to yes if modules are not enabled */
759 	if (val == mod)
760 		if (!sym_is_choice_value(sym) && modules_sym->curr.tri == no)
761 			val = yes;
762 
763 	/* transpose mod to yes if type is bool */
764 	if (sym->type == S_BOOLEAN && val == mod)
765 		val = yes;
766 
767 	/* adjust the default value if this symbol is implied by another */
768 	if (val < sym->implied.tri)
769 		val = sym->implied.tri;
770 
771 	switch (sym->type) {
772 	case S_BOOLEAN:
773 	case S_TRISTATE:
774 		switch (val) {
775 		case no: return "n";
776 		case mod: return "m";
777 		case yes: return "y";
778 		}
779 	case S_INT:
780 	case S_HEX:
781 		return str;
782 	case S_STRING:
783 		return str;
784 	case S_OTHER:
785 	case S_UNKNOWN:
786 		break;
787 	}
788 	return "";
789 }
790 
791 const char *sym_get_string_value(struct symbol *sym)
792 {
793 	tristate val;
794 
795 	switch (sym->type) {
796 	case S_BOOLEAN:
797 	case S_TRISTATE:
798 		val = sym_get_tristate_value(sym);
799 		switch (val) {
800 		case no:
801 			return "n";
802 		case mod:
803 			sym_calc_value(modules_sym);
804 			return (modules_sym->curr.tri == no) ? "n" : "m";
805 		case yes:
806 			return "y";
807 		}
808 		break;
809 	default:
810 		;
811 	}
812 	return (const char *)sym->curr.val;
813 }
814 
815 bool sym_is_changable(struct symbol *sym)
816 {
817 	return sym->visible > sym->rev_dep.tri;
818 }
819 
820 static unsigned strhash(const char *s)
821 {
822 	/* fnv32 hash */
823 	unsigned hash = 2166136261U;
824 	for (; *s; s++)
825 		hash = (hash ^ *s) * 0x01000193;
826 	return hash;
827 }
828 
829 struct symbol *sym_lookup(const char *name, int flags)
830 {
831 	struct symbol *symbol;
832 	char *new_name;
833 	int hash;
834 
835 	if (name) {
836 		if (name[0] && !name[1]) {
837 			switch (name[0]) {
838 			case 'y': return &symbol_yes;
839 			case 'm': return &symbol_mod;
840 			case 'n': return &symbol_no;
841 			}
842 		}
843 		hash = strhash(name) % SYMBOL_HASHSIZE;
844 
845 		for (symbol = symbol_hash[hash]; symbol; symbol = symbol->next) {
846 			if (symbol->name &&
847 			    !strcmp(symbol->name, name) &&
848 			    (flags ? symbol->flags & flags
849 				   : !(symbol->flags & (SYMBOL_CONST|SYMBOL_CHOICE))))
850 				return symbol;
851 		}
852 		new_name = xstrdup(name);
853 	} else {
854 		new_name = NULL;
855 		hash = 0;
856 	}
857 
858 	symbol = xmalloc(sizeof(*symbol));
859 	memset(symbol, 0, sizeof(*symbol));
860 	symbol->name = new_name;
861 	symbol->type = S_UNKNOWN;
862 	symbol->flags |= flags;
863 
864 	symbol->next = symbol_hash[hash];
865 	symbol_hash[hash] = symbol;
866 
867 	return symbol;
868 }
869 
870 struct symbol *sym_find(const char *name)
871 {
872 	struct symbol *symbol = NULL;
873 	int hash = 0;
874 
875 	if (!name)
876 		return NULL;
877 
878 	if (name[0] && !name[1]) {
879 		switch (name[0]) {
880 		case 'y': return &symbol_yes;
881 		case 'm': return &symbol_mod;
882 		case 'n': return &symbol_no;
883 		}
884 	}
885 	hash = strhash(name) % SYMBOL_HASHSIZE;
886 
887 	for (symbol = symbol_hash[hash]; symbol; symbol = symbol->next) {
888 		if (symbol->name &&
889 		    !strcmp(symbol->name, name) &&
890 		    !(symbol->flags & SYMBOL_CONST))
891 				break;
892 	}
893 
894 	return symbol;
895 }
896 
897 /*
898  * Expand symbol's names embedded in the string given in argument. Symbols'
899  * name to be expanded shall be prefixed by a '$'. Unknown symbol expands to
900  * the empty string.
901  */
902 char *sym_expand_string_value(const char *in)
903 {
904 	const char *src;
905 	char *res;
906 	size_t reslen;
907 
908 	/*
909 	 * Note: 'in' might come from a token that's about to be
910 	 * freed, so make sure to always allocate a new string
911 	 */
912 	reslen = strlen(in) + 1;
913 	res = xmalloc(reslen);
914 	res[0] = '\0';
915 
916 	while ((src = strchr(in, '$'))) {
917 		char *p, name[SYMBOL_MAXLENGTH];
918 		const char *symval = "";
919 		struct symbol *sym;
920 		size_t newlen;
921 
922 		strncat(res, in, src - in);
923 		src++;
924 
925 		p = name;
926 		while (isalnum(*src) || *src == '_')
927 			*p++ = *src++;
928 		*p = '\0';
929 
930 		sym = sym_find(name);
931 		if (sym != NULL) {
932 			sym_calc_value(sym);
933 			symval = sym_get_string_value(sym);
934 		}
935 
936 		newlen = strlen(res) + strlen(symval) + strlen(src) + 1;
937 		if (newlen > reslen) {
938 			reslen = newlen;
939 			res = xrealloc(res, reslen);
940 		}
941 
942 		strcat(res, symval);
943 		in = src;
944 	}
945 	strcat(res, in);
946 
947 	return res;
948 }
949 
950 const char *sym_escape_string_value(const char *in)
951 {
952 	const char *p;
953 	size_t reslen;
954 	char *res;
955 	size_t l;
956 
957 	reslen = strlen(in) + strlen("\"\"") + 1;
958 
959 	p = in;
960 	for (;;) {
961 		l = strcspn(p, "\"\\");
962 		p += l;
963 
964 		if (p[0] == '\0')
965 			break;
966 
967 		reslen++;
968 		p++;
969 	}
970 
971 	res = xmalloc(reslen);
972 	res[0] = '\0';
973 
974 	strcat(res, "\"");
975 
976 	p = in;
977 	for (;;) {
978 		l = strcspn(p, "\"\\");
979 		strncat(res, p, l);
980 		p += l;
981 
982 		if (p[0] == '\0')
983 			break;
984 
985 		strcat(res, "\\");
986 		strncat(res, p++, 1);
987 	}
988 
989 	strcat(res, "\"");
990 	return res;
991 }
992 
993 struct sym_match {
994 	struct symbol	*sym;
995 	off_t		so, eo;
996 };
997 
998 /* Compare matched symbols as thus:
999  * - first, symbols that match exactly
1000  * - then, alphabetical sort
1001  */
1002 static int sym_rel_comp(const void *sym1, const void *sym2)
1003 {
1004 	const struct sym_match *s1 = sym1;
1005 	const struct sym_match *s2 = sym2;
1006 	int exact1, exact2;
1007 
1008 	/* Exact match:
1009 	 * - if matched length on symbol s1 is the length of that symbol,
1010 	 *   then this symbol should come first;
1011 	 * - if matched length on symbol s2 is the length of that symbol,
1012 	 *   then this symbol should come first.
1013 	 * Note: since the search can be a regexp, both symbols may match
1014 	 * exactly; if this is the case, we can't decide which comes first,
1015 	 * and we fallback to sorting alphabetically.
1016 	 */
1017 	exact1 = (s1->eo - s1->so) == strlen(s1->sym->name);
1018 	exact2 = (s2->eo - s2->so) == strlen(s2->sym->name);
1019 	if (exact1 && !exact2)
1020 		return -1;
1021 	if (!exact1 && exact2)
1022 		return 1;
1023 
1024 	/* As a fallback, sort symbols alphabetically */
1025 	return strcmp(s1->sym->name, s2->sym->name);
1026 }
1027 
1028 struct symbol **sym_re_search(const char *pattern)
1029 {
1030 	struct symbol *sym, **sym_arr = NULL;
1031 	struct sym_match *sym_match_arr = NULL;
1032 	int i, cnt, size;
1033 	regex_t re;
1034 	regmatch_t match[1];
1035 
1036 	cnt = size = 0;
1037 	/* Skip if empty */
1038 	if (strlen(pattern) == 0)
1039 		return NULL;
1040 	if (regcomp(&re, pattern, REG_EXTENDED|REG_ICASE))
1041 		return NULL;
1042 
1043 	for_all_symbols(i, sym) {
1044 		if (sym->flags & SYMBOL_CONST || !sym->name)
1045 			continue;
1046 		if (regexec(&re, sym->name, 1, match, 0))
1047 			continue;
1048 		if (cnt >= size) {
1049 			void *tmp;
1050 			size += 16;
1051 			tmp = realloc(sym_match_arr, size * sizeof(struct sym_match));
1052 			if (!tmp)
1053 				goto sym_re_search_free;
1054 			sym_match_arr = tmp;
1055 		}
1056 		sym_calc_value(sym);
1057 		/* As regexec returned 0, we know we have a match, so
1058 		 * we can use match[0].rm_[se]o without further checks
1059 		 */
1060 		sym_match_arr[cnt].so = match[0].rm_so;
1061 		sym_match_arr[cnt].eo = match[0].rm_eo;
1062 		sym_match_arr[cnt++].sym = sym;
1063 	}
1064 	if (sym_match_arr) {
1065 		qsort(sym_match_arr, cnt, sizeof(struct sym_match), sym_rel_comp);
1066 		sym_arr = malloc((cnt+1) * sizeof(struct symbol *));
1067 		if (!sym_arr)
1068 			goto sym_re_search_free;
1069 		for (i = 0; i < cnt; i++)
1070 			sym_arr[i] = sym_match_arr[i].sym;
1071 		sym_arr[cnt] = NULL;
1072 	}
1073 sym_re_search_free:
1074 	/* sym_match_arr can be NULL if no match, but free(NULL) is OK */
1075 	free(sym_match_arr);
1076 	regfree(&re);
1077 
1078 	return sym_arr;
1079 }
1080 
1081 /*
1082  * When we check for recursive dependencies we use a stack to save
1083  * current state so we can print out relevant info to user.
1084  * The entries are located on the call stack so no need to free memory.
1085  * Note insert() remove() must always match to properly clear the stack.
1086  */
1087 static struct dep_stack {
1088 	struct dep_stack *prev, *next;
1089 	struct symbol *sym;
1090 	struct property *prop;
1091 	struct expr *expr;
1092 } *check_top;
1093 
1094 static void dep_stack_insert(struct dep_stack *stack, struct symbol *sym)
1095 {
1096 	memset(stack, 0, sizeof(*stack));
1097 	if (check_top)
1098 		check_top->next = stack;
1099 	stack->prev = check_top;
1100 	stack->sym = sym;
1101 	check_top = stack;
1102 }
1103 
1104 static void dep_stack_remove(void)
1105 {
1106 	check_top = check_top->prev;
1107 	if (check_top)
1108 		check_top->next = NULL;
1109 }
1110 
1111 /*
1112  * Called when we have detected a recursive dependency.
1113  * check_top point to the top of the stact so we use
1114  * the ->prev pointer to locate the bottom of the stack.
1115  */
1116 static void sym_check_print_recursive(struct symbol *last_sym)
1117 {
1118 	struct dep_stack *stack;
1119 	struct symbol *sym, *next_sym;
1120 	struct menu *menu = NULL;
1121 	struct property *prop;
1122 	struct dep_stack cv_stack;
1123 
1124 	if (sym_is_choice_value(last_sym)) {
1125 		dep_stack_insert(&cv_stack, last_sym);
1126 		last_sym = prop_get_symbol(sym_get_choice_prop(last_sym));
1127 	}
1128 
1129 	for (stack = check_top; stack != NULL; stack = stack->prev)
1130 		if (stack->sym == last_sym)
1131 			break;
1132 	if (!stack) {
1133 		fprintf(stderr, "unexpected recursive dependency error\n");
1134 		return;
1135 	}
1136 
1137 	for (; stack; stack = stack->next) {
1138 		sym = stack->sym;
1139 		next_sym = stack->next ? stack->next->sym : last_sym;
1140 		prop = stack->prop;
1141 		if (prop == NULL)
1142 			prop = stack->sym->prop;
1143 
1144 		/* for choice values find the menu entry (used below) */
1145 		if (sym_is_choice(sym) || sym_is_choice_value(sym)) {
1146 			for (prop = sym->prop; prop; prop = prop->next) {
1147 				menu = prop->menu;
1148 				if (prop->menu)
1149 					break;
1150 			}
1151 		}
1152 		if (stack->sym == last_sym)
1153 			fprintf(stderr, "%s:%d:error: recursive dependency detected!\n",
1154 				prop->file->name, prop->lineno);
1155 
1156 		if (stack->expr) {
1157 			fprintf(stderr, "%s:%d:\tsymbol %s %s value contains %s\n",
1158 				prop->file->name, prop->lineno,
1159 				sym->name ? sym->name : "<choice>",
1160 				prop_get_type_name(prop->type),
1161 				next_sym->name ? next_sym->name : "<choice>");
1162 		} else if (stack->prop) {
1163 			fprintf(stderr, "%s:%d:\tsymbol %s depends on %s\n",
1164 				prop->file->name, prop->lineno,
1165 				sym->name ? sym->name : "<choice>",
1166 				next_sym->name ? next_sym->name : "<choice>");
1167 		} else if (sym_is_choice(sym)) {
1168 			fprintf(stderr, "%s:%d:\tchoice %s contains symbol %s\n",
1169 				menu->file->name, menu->lineno,
1170 				sym->name ? sym->name : "<choice>",
1171 				next_sym->name ? next_sym->name : "<choice>");
1172 		} else if (sym_is_choice_value(sym)) {
1173 			fprintf(stderr, "%s:%d:\tsymbol %s is part of choice %s\n",
1174 				menu->file->name, menu->lineno,
1175 				sym->name ? sym->name : "<choice>",
1176 				next_sym->name ? next_sym->name : "<choice>");
1177 		} else {
1178 			fprintf(stderr, "%s:%d:\tsymbol %s is selected by %s\n",
1179 				prop->file->name, prop->lineno,
1180 				sym->name ? sym->name : "<choice>",
1181 				next_sym->name ? next_sym->name : "<choice>");
1182 		}
1183 	}
1184 
1185 	fprintf(stderr,
1186 		"For a resolution refer to Documentation/kbuild/kconfig-language.txt\n"
1187 		"subsection \"Kconfig recursive dependency limitations\"\n"
1188 		"\n");
1189 
1190 	if (check_top == &cv_stack)
1191 		dep_stack_remove();
1192 }
1193 
1194 static struct symbol *sym_check_expr_deps(struct expr *e)
1195 {
1196 	struct symbol *sym;
1197 
1198 	if (!e)
1199 		return NULL;
1200 	switch (e->type) {
1201 	case E_OR:
1202 	case E_AND:
1203 		sym = sym_check_expr_deps(e->left.expr);
1204 		if (sym)
1205 			return sym;
1206 		return sym_check_expr_deps(e->right.expr);
1207 	case E_NOT:
1208 		return sym_check_expr_deps(e->left.expr);
1209 	case E_EQUAL:
1210 	case E_GEQ:
1211 	case E_GTH:
1212 	case E_LEQ:
1213 	case E_LTH:
1214 	case E_UNEQUAL:
1215 		sym = sym_check_deps(e->left.sym);
1216 		if (sym)
1217 			return sym;
1218 		return sym_check_deps(e->right.sym);
1219 	case E_SYMBOL:
1220 		return sym_check_deps(e->left.sym);
1221 	default:
1222 		break;
1223 	}
1224 	fprintf(stderr, "Oops! How to check %d?\n", e->type);
1225 	return NULL;
1226 }
1227 
1228 /* return NULL when dependencies are OK */
1229 static struct symbol *sym_check_sym_deps(struct symbol *sym)
1230 {
1231 	struct symbol *sym2;
1232 	struct property *prop;
1233 	struct dep_stack stack;
1234 
1235 	dep_stack_insert(&stack, sym);
1236 
1237 	sym2 = sym_check_expr_deps(sym->rev_dep.expr);
1238 	if (sym2)
1239 		goto out;
1240 
1241 	for (prop = sym->prop; prop; prop = prop->next) {
1242 		if (prop->type == P_CHOICE || prop->type == P_SELECT)
1243 			continue;
1244 		stack.prop = prop;
1245 		sym2 = sym_check_expr_deps(prop->visible.expr);
1246 		if (sym2)
1247 			break;
1248 		if (prop->type != P_DEFAULT || sym_is_choice(sym))
1249 			continue;
1250 		stack.expr = prop->expr;
1251 		sym2 = sym_check_expr_deps(prop->expr);
1252 		if (sym2)
1253 			break;
1254 		stack.expr = NULL;
1255 	}
1256 
1257 out:
1258 	dep_stack_remove();
1259 
1260 	return sym2;
1261 }
1262 
1263 static struct symbol *sym_check_choice_deps(struct symbol *choice)
1264 {
1265 	struct symbol *sym, *sym2;
1266 	struct property *prop;
1267 	struct expr *e;
1268 	struct dep_stack stack;
1269 
1270 	dep_stack_insert(&stack, choice);
1271 
1272 	prop = sym_get_choice_prop(choice);
1273 	expr_list_for_each_sym(prop->expr, e, sym)
1274 		sym->flags |= (SYMBOL_CHECK | SYMBOL_CHECKED);
1275 
1276 	choice->flags |= (SYMBOL_CHECK | SYMBOL_CHECKED);
1277 	sym2 = sym_check_sym_deps(choice);
1278 	choice->flags &= ~SYMBOL_CHECK;
1279 	if (sym2)
1280 		goto out;
1281 
1282 	expr_list_for_each_sym(prop->expr, e, sym) {
1283 		sym2 = sym_check_sym_deps(sym);
1284 		if (sym2)
1285 			break;
1286 	}
1287 out:
1288 	expr_list_for_each_sym(prop->expr, e, sym)
1289 		sym->flags &= ~SYMBOL_CHECK;
1290 
1291 	if (sym2 && sym_is_choice_value(sym2) &&
1292 	    prop_get_symbol(sym_get_choice_prop(sym2)) == choice)
1293 		sym2 = choice;
1294 
1295 	dep_stack_remove();
1296 
1297 	return sym2;
1298 }
1299 
1300 struct symbol *sym_check_deps(struct symbol *sym)
1301 {
1302 	struct symbol *sym2;
1303 	struct property *prop;
1304 
1305 	if (sym->flags & SYMBOL_CHECK) {
1306 		sym_check_print_recursive(sym);
1307 		return sym;
1308 	}
1309 	if (sym->flags & SYMBOL_CHECKED)
1310 		return NULL;
1311 
1312 	if (sym_is_choice_value(sym)) {
1313 		struct dep_stack stack;
1314 
1315 		/* for choice groups start the check with main choice symbol */
1316 		dep_stack_insert(&stack, sym);
1317 		prop = sym_get_choice_prop(sym);
1318 		sym2 = sym_check_deps(prop_get_symbol(prop));
1319 		dep_stack_remove();
1320 	} else if (sym_is_choice(sym)) {
1321 		sym2 = sym_check_choice_deps(sym);
1322 	} else {
1323 		sym->flags |= (SYMBOL_CHECK | SYMBOL_CHECKED);
1324 		sym2 = sym_check_sym_deps(sym);
1325 		sym->flags &= ~SYMBOL_CHECK;
1326 	}
1327 
1328 	if (sym2 && sym2 == sym)
1329 		sym2 = NULL;
1330 
1331 	return sym2;
1332 }
1333 
1334 struct property *prop_alloc(enum prop_type type, struct symbol *sym)
1335 {
1336 	struct property *prop;
1337 	struct property **propp;
1338 
1339 	prop = xmalloc(sizeof(*prop));
1340 	memset(prop, 0, sizeof(*prop));
1341 	prop->type = type;
1342 	prop->sym = sym;
1343 	prop->file = current_file;
1344 	prop->lineno = zconf_lineno();
1345 
1346 	/* append property to the prop list of symbol */
1347 	if (sym) {
1348 		for (propp = &sym->prop; *propp; propp = &(*propp)->next)
1349 			;
1350 		*propp = prop;
1351 	}
1352 
1353 	return prop;
1354 }
1355 
1356 struct symbol *prop_get_symbol(struct property *prop)
1357 {
1358 	if (prop->expr && (prop->expr->type == E_SYMBOL ||
1359 			   prop->expr->type == E_LIST))
1360 		return prop->expr->left.sym;
1361 	return NULL;
1362 }
1363 
1364 const char *prop_get_type_name(enum prop_type type)
1365 {
1366 	switch (type) {
1367 	case P_PROMPT:
1368 		return "prompt";
1369 	case P_ENV:
1370 		return "env";
1371 	case P_COMMENT:
1372 		return "comment";
1373 	case P_MENU:
1374 		return "menu";
1375 	case P_DEFAULT:
1376 		return "default";
1377 	case P_CHOICE:
1378 		return "choice";
1379 	case P_SELECT:
1380 		return "select";
1381 	case P_IMPLY:
1382 		return "imply";
1383 	case P_RANGE:
1384 		return "range";
1385 	case P_SYMBOL:
1386 		return "symbol";
1387 	case P_UNKNOWN:
1388 		break;
1389 	}
1390 	return "unknown";
1391 }
1392 
1393 static void prop_add_env(const char *env)
1394 {
1395 	struct symbol *sym, *sym2;
1396 	struct property *prop;
1397 	char *p;
1398 
1399 	sym = current_entry->sym;
1400 	sym->flags |= SYMBOL_AUTO;
1401 	for_all_properties(sym, prop, P_ENV) {
1402 		sym2 = prop_get_symbol(prop);
1403 		if (strcmp(sym2->name, env))
1404 			menu_warn(current_entry, "redefining environment symbol from %s",
1405 				  sym2->name);
1406 		return;
1407 	}
1408 
1409 	prop = prop_alloc(P_ENV, sym);
1410 	prop->expr = expr_alloc_symbol(sym_lookup(env, SYMBOL_CONST));
1411 
1412 	sym_env_list = expr_alloc_one(E_LIST, sym_env_list);
1413 	sym_env_list->right.sym = sym;
1414 
1415 	p = getenv(env);
1416 	if (p)
1417 		sym_add_default(sym, p);
1418 	else
1419 		menu_warn(current_entry, "environment variable %s undefined", env);
1420 }
1421