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