symbol.c

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