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