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