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